Skip to main content
MathOverflow

Return to Question

added 272 characters in body
Source Link
user85361
user85361
  • 121
  • 2

As we know, for solving saddle point problems, the forward-backward algorithm is generally not guaranteed to converge. But the extragradient method converges Structured Prediction via the Extragradient Method

Suppose that $L(w,z)$ is a convex in $w$-concave in $z$ function. Can we express the extragradient, \begin{align} w^{k+1/2}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^k,z^k))\cr z^{k+1/2}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^k,z^k))\cr w^{k+1}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^{(k+1/2)},z^{(k+1/2)}))\cr z^{k+1}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^{(k+1/2)},z^{(k+1/2)}))\cr \end{align} with only proximal steps? I mean without using the gradient of the function $L$. Sorry for asking the same question on MATH.SE.

EDIT: In this paper, Gradient Descent Only Converges to Minimizers, it is proved that proximal point algorithm does not converges to saddles. Does this mean that the answer to this question is negative?

As we know, for solving saddle point problems, the forward-backward algorithm is generally not guaranteed to converge. But the extragradient method converges Structured Prediction via the Extragradient Method

Suppose that $L(w,z)$ is a convex in $w$-concave in $z$ function. Can we express the extragradient, \begin{align} w^{k+1/2}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^k,z^k))\cr z^{k+1/2}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^k,z^k))\cr w^{k+1}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^{(k+1/2)},z^{(k+1/2)}))\cr z^{k+1}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^{(k+1/2)},z^{(k+1/2)}))\cr \end{align} with only proximal steps? I mean without using the gradient of the function $L$. Sorry for asking the same question on MATH.SE.

As we know, for solving saddle point problems, the forward-backward algorithm is generally not guaranteed to converge. But the extragradient method converges Structured Prediction via the Extragradient Method

Suppose that $L(w,z)$ is a convex in $w$-concave in $z$ function. Can we express the extragradient, \begin{align} w^{k+1/2}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^k,z^k))\cr z^{k+1/2}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^k,z^k))\cr w^{k+1}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^{(k+1/2)},z^{(k+1/2)}))\cr z^{k+1}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^{(k+1/2)},z^{(k+1/2)}))\cr \end{align} with only proximal steps? I mean without using the gradient of the function $L$. Sorry for asking the same question on MATH.SE.

EDIT: In this paper, Gradient Descent Only Converges to Minimizers, it is proved that proximal point algorithm does not converges to saddles. Does this mean that the answer to this question is negative?

spelling, grammar
Source Link
Ben McKay
Ben McKay
  • 26.3k
  • 7
  • 67
  • 102

Is Extragradient Can the extragradient method can be computed only based on proximal steps?

As we know, for solving saddle point problems, the forward-backward algorithm is generally not guaranteed to converge. But the extragradient method convergeconverges Structured Prediction via the Extragradient Method

Suppose that $L(w,z)$ is a convex in $w$-concave in $z$ function. Can we express the extragradient, \begin{align} w^{k+1/2}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^k,z^k))\cr z^{k+1/2}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^k,z^k))\cr w^{k+1}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^{(k+1/2)},z^{(k+1/2)}))\cr z^{k+1}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^{(k+1/2)},z^{(k+1/2)}))\cr \end{align} with only proximal steps? I mean without using the gradient of the function $L$. Sorry for asking the same question on MATH.SE.

Is Extragradient method can be computed only based on proximal steps?

As we know, for solving saddle point problems, forward-backward algorithm is generally not guaranteed to converge. But extragradient method converge Structured Prediction via the Extragradient Method

Suppose $L(w,z)$ is a convex in $w$-concave in $z$ function. Can we express extragradient, \begin{align} w^{k+1/2}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^k,z^k))\cr z^{k+1/2}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^k,z^k))\cr w^{k+1}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^{(k+1/2)},z^{(k+1/2)}))\cr z^{k+1}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^{(k+1/2)},z^{(k+1/2)}))\cr \end{align} with only proximal steps? I mean without using gradient of function $L$. Sorry for asking the same question on MATH.SE.

Can the extragradient method be computed only based on proximal steps?

As we know, for solving saddle point problems, the forward-backward algorithm is generally not guaranteed to converge. But the extragradient method converges Structured Prediction via the Extragradient Method

Suppose that $L(w,z)$ is a convex in $w$-concave in $z$ function. Can we express the extragradient, \begin{align} w^{k+1/2}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^k,z^k))\cr z^{k+1/2}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^k,z^k))\cr w^{k+1}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^{(k+1/2)},z^{(k+1/2)}))\cr z^{k+1}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^{(k+1/2)},z^{(k+1/2)}))\cr \end{align} with only proximal steps? I mean without using the gradient of the function $L$. Sorry for asking the same question on MATH.SE.

Source Link
user85361
user85361
  • 121
  • 2

Is Extragradient method can be computed only based on proximal steps?

As we know, for solving saddle point problems, forward-backward algorithm is generally not guaranteed to converge. But extragradient method converge Structured Prediction via the Extragradient Method

Suppose $L(w,z)$ is a convex in $w$-concave in $z$ function. Can we express extragradient, \begin{align} w^{k+1/2}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^k,z^k))\cr z^{k+1/2}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^k,z^k))\cr w^{k+1}&=P_{W}(w^k-\beta \bigtriangledown_w L(w^{(k+1/2)},z^{(k+1/2)}))\cr z^{k+1}&=P_{Z}(z^k+\beta \bigtriangledown_z L(w^{(k+1/2)},z^{(k+1/2)}))\cr \end{align} with only proximal steps? I mean without using gradient of function $L$. Sorry for asking the same question on MATH.SE.