1
$\begingroup$

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?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.