2019

A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach

Mokhtari, Aryan, Ozdaglar, Asuman, Pattathil, Sarath

Understand

In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA) methods.

We show that both of these algorithms admit a unified analysis as approximations of the classical proximal point method for solving saddle point problems.
This viewpoint enables us to develop a new framework for analyzing EG and OGDA for bilinear and strongly convex-strongly concave settings.
Moreover, we use the proximal point approximation interpretation to generalize the results for OGDA for a wide range of parameters.

Built on

Brève communication. régularisation d’inéquations variationnelles par approximations successives
Martinet, B · 1970
Earlier work this paper cites.
The extragradient method for finding saddle points and other problems
Korpelevich, G · 1976
Earlier work this paper cites.
Finite termination of the proximal point algorithm
Ferris, M. C · 1991
Earlier work this paper cites.
On the convergence of the proximal point algorithm for convex minimization
Güler, O · 1991
Earlier work this paper cites.
On the douglas rachford splitting method and the proximal point algorithm for maximal monotone operators
Eckstein, J. and Bertsekas, D. P · 1992
Earlier work this paper cites.
On linear convergence of iterative methods for the variational inequality problem
Tseng, P · 1995
Earlier work this paper cites.
Convergence rates in forward–backward splitting
Chen, G. H. and Rockafellar, R. T · 1997
Earlier work this paper cites.
Dynamic noncooperative game theory , volume 23
Basar, T. and Olsder, G. J · 1999
Earlier work this paper cites.
Nonlinear programming
Bertsekas, D. P · 1999
Earlier work this paper cites.
Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems
Nemirovski, A · 2004
Earlier work this paper cites.
Finite-dimensional variational inequalities and complementarity problems
Facchinei, F. and Pang, J.-S · 2007
Earlier work this paper cites.

Similar

Robust optimization , volume 28
Ben-Tal, A., El Ghaoui, L., and Nemirovski, A · 2009
Cited alongside, same era.
Subgradient methods for saddle-point problems
Nedić, A. and Ozdaglar, A · 2009
Cited alongside, same era.
Robust stochastic approximation approach to stochastic programming
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A · 2009
Cited alongside, same era.
On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
Monteiro, R. D. and Svaiter, B. F · 2010
Cited alongside, same era.
Convex analysis and monotone operator theory in Hilbert spaces , volume 408
Bauschke, H. H., Combettes, P. L., et al · 2011
Cited alongside, same era.
A first-order primal-dual algorithm for convex problems with applications to imaging
Chambolle, A. and Pock, T · 2011
Cited alongside, same era.
Solving variational inequalities with stochastic mirror-prox algorithm
Juditsky, A., Nemirovski, A., and Tauvel, C · 2011
Cited alongside, same era.
Online optimization with gradual variations
Chiang, C., Yang, T., Lee, C., Mahdavi, M., Lu, C., Jin, R., and Zhu, S · 2012
Cited alongside, same era.
Pid design by convex-concave optimization
Hast, M., Astrom, K., Bernhardsson, B., and Boyd, S · 2013
Cited alongside, same era.
Introductory lectures on convex optimization: A basic course , volume 87
Nesterov, Y · 2013
Cited alongside, same era.
Online learning with predictable sequences
Rakhlin, A. and Sridharan, K · 2013
Cited alongside, same era.
Optimization, learning, and games with predictable sequences
Rakhlin, S. and Sridharan, K
Cited in the paper.

Then

Optimal primal-dual methods for a class of saddle point problems
Chen, Y., Lan, G., and Ouyang, Y · 2014
Later among the works it cites.
Generative adversarial nets
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y · 2014
Later among the works it cites.
Proximal algorithms
Parikh, N., Boyd, S., et al · 2014
Later among the works it cites.
Stochastic variance reduction methods for saddle-point problems
Palaniappan, B. and Bach, F · 2016
Later among the works it cites.
Wasserstein generative adversarial networks
Arjovsky, M., Chintala, S., and Bottou, L · 2017
Later among the works it cites.
First-Order Methods in Optimization , volume 25
Beck, A · 2017
Later among the works it cites.
Training gans with optimism
Original
Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H · 2017
Later among the works it cites.
Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity
Original
Du, S. S. and Hu, W · 2018
Later among the works it cites.
A variational inequality perspective on generative adversarial nets
Original
Gidel, G., Berard, H., Vincent, P., and Lacoste-Julien, S · 2018
Later among the works it cites.
Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks
Original
Liang, T. and Stokes, J · 2018
Later among the works it cites.
Reducing noise in gan training with variance reduced extragradient
Original
Chavdarova, T., Gidel, G., Fleuret, F., and Lacoste-Julien, S · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…