An idea for convex-concave saddle-point problem

57 Views Asked by At

For the following convex-concave problem $$ \min_{x\in\mathbb{R}^n}\max_{y\in\mathbb{R}^n} f(x)+\langle y,x\rangle-g(y) $$ Does the following algorithm achieve convergence? Under what conditions?

$x_{t+1}=(1-\alpha_t)x_t+\alpha_t\nabla g(y_t)$

$y_{t+1}=(1-\beta_t)y_t-\beta_t\nabla f(x_{t+1})$

The intuition is based on the first-order optimality condition:

$y^*=-\nabla f(x^*)$

$x^*=\nabla g(y^*)$

1

There are 1 best solutions below

2
On

I don't think the algorithm you proposed will converge in general, because of two reasons. First, we can rewrite you algorithm as

$x_{t+1}=x_t - \alpha_t (x_t - \nabla g(y_t) )$

$y_{t+1}=y_t + \beta_t (-y_t - \nabla f(x_{t+1}) )$.

It resembles a gradient descent-ascend algorithm, but it looks strange. For instance, $g$ is a function of $y$, but you use it to update $x_{t+1}$. We have the same issue with $f$ and $y_{t+1}$. The signs of the gradients also look strange. Do you have any motivation behind proposing this algorithm? Maybe this paper can be useful for you: "A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach" by Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil.

The second issue is that, except for convexity and concavity, you have not imposed any conditions on $f$ and $g$ (e.g., smoothness or strong-convexity). For instance, it could be the case that $f(x) = g(y) = 0$ for all $x$ and $y$. In this case, you would be solving a pure bilinear saddle-point problem, for which as far as I known, simple gradient descent-ascend algorithms do not guarantee last-iterate convergence.