2020

The limits of min-max optimization algorithms: convergence to spurious non-critical sets

Hsieh, Ya-Ping, Mertikopoulos, Panayotis, Cevher, Volkan

Understand

Compared to ordinary function minimization problems, min-max optimization algorithms encounter far greater challenges because of the existence of periodic cycles and similar phenomena.

Even though some of these behaviors can be overcome in the convex-concave regime, the general case is considerably more difficult.
On that account, we take an in-depth look at a comprehensive class of state-of-the art algorithms and prevalent heuristics in non-convex / non-concave problems, and we establish the following general results: a) generically, the algorithms' limit points are contained in the ICT sets of a common, mean-field system; b) the attractors of this system also attract the algorithms in question with arbitrarily high probability; and c) all algorithms avoid the system's unstable sets with probability 1.
On the surface, this provides a highly optimistic outlook for min-max algorithms; however, we show that there exist spurious attractors that do not contain any stationary points of the problem under study.

Built on

Mokhtari A, Ozdaglar A, Pattathil S (2019a) A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach. https://arxiv.org/abs/1901.08511v2
Original
1901
Earlier work this paper cites.
Robbins H, Monro S (1951) A stochastic approximation method. Annals of Mathematical Statistics 22:400–407
1951
Earlier work this paper cites.
Kiefer J, Wolfowitz J (1952) Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics 23(3):462–466
1952
Earlier work this paper cites.
Arrow KJ, Hurwicz L, Uzawa H (1958) Studies in linear and non-linear programming. Stanford University Press
1958
Earlier work this paper cites.
Kupka I (1963) Contributiona la théorie des champs génériques. Contributions to differential equations 2:457–484
1963
Earlier work this paper cites.
Smale S (1963) Stable manifolds for differential equations and diffeomorphisms. Annali della Scuola Normale Superiore di Pisa-Classe di Scienze 17(1-2):97–116
1963
Earlier work this paper cites.
Burkholder DL (1973) Distribution function inequalities for martingales. Annals of Probability 1(1):19–42
1973
Earlier work this paper cites.
Bowen R (1975) Omega limit sets of Axiom A diffeomorphisms. Journal of Differential Equations 18:333–339
1975
Earlier work this paper cites.
Rockafellar RT (1976) Monotone operators and the proximal point algorithm. SIAM journal on control and optimization 14(5):877–898
1976
Earlier work this paper cites.
Ljung L (1977) Analysis of recursive stochastic algorithms. IEEE Trans Autom Control 22(4):551–575
1977
Earlier work this paper cites.
Conley CC (1978) Isolated Invariant Set and the Morse Index. American Mathematical Society, Providence, RI
1978
Earlier work this paper cites.
Kushner HJ, Clark DS (1978) Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer
1978
Earlier work this paper cites.
Hall P, Heyde CC (1980) Martingale Limit Theory and Its Application. Probability and Mathematical Statistics, Academic Press, New York
1980
Earlier work this paper cites.
Popov LD (1980) A modification of the Arrow–Hurwicz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR 28(5):845–848
1980
Earlier work this paper cites.
Kushner HJ, Huang H (1981) Asymptotic properties of stochastic approximations with constant coefficients. SIAM Journal on Control and Optimization 19(1):87–105
1981
Earlier work this paper cites.
Shub M (1987) Global Stability of Dynamical Systems. Springer-Verlag, Berlin
1987
Earlier work this paper cites.
Benveniste A, Métivier M, Priouret P (1990) Adaptive Algorithms and Stochastic Approximations. Springer
1990
Earlier work this paper cites.
Pemantle R (1990) Nonconvergence to unstable points in urn models and stochastic aproximations. Annals of Probability 18(2):698–712
1990
Earlier work this paper cites.
Pemantle R (1992) Vertex-reinforced random walk. Probability Theory and Related Fields 92:117–136
1992
Earlier work this paper cites.
Spall JC (1992) Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans Autom Control 37(3):332–341
1992
Earlier work this paper cites.
Phelps RR (1993) Convex Functions, Monotone Operators and Differentiability, 2nd edn. Lecture Notes in Mathematics, Springer-Verlag
1993
Earlier work this paper cites.
Pearlmutter BA (1994) Fast exact multiplication by the hessian. Neural computation 6(1):147–160
1994
Earlier work this paper cites.
Benaïm M, Hirsch MW (1995) Dynamics of Morse-Smale urn processes. Ergodic Theory and Dynamical Systems 15(6):1005–1030
1995
Earlier work this paper cites.
Benaïm M, Hirsch MW (1996) Asymptotic pseudotrajectories and chain recurrent flows, with applications. Journal of Dynamics and Differential Equations 8(1):141–176
1996
Earlier work this paper cites.
Kushner HJ, Yin GG (1997) Stochastic approximation algorithms and applications. Springer-Verlag, New York, NY
1997
Earlier work this paper cites.
Robinson C (1998) Dynamical systems: stability, symbolic dynamics, and chaos. CRC press
1998
Earlier work this paper cites.

Similar

Benaïm M (1999) Dynamics of stochastic approximation algorithms. In: Azéma J, Émery M, Ledoux M, Yor M (eds) Séminaire de Probabilités XXXIII, Lecture Notes in Mathematics, vol 1709, Springer Berlin Heidelberg, pp 1–68
1999
Cited alongside, same era.
Bertsekas DP, Tsitsiklis JN (2000) Gradient convergence in gradient methods with errors. SIAM Journal on Optimization 10(3):627–642
2000
Cited alongside, same era.
Facchinei F, Pang JS (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research, Springer
2003
Cited alongside, same era.
Lee JM (2003) Introduction to Smooth Manifolds. No. 218 in Graduate Texts in Mathematics, Springer-Verlag, New York, NY
2003
Cited alongside, same era.
Wiggins S (2003) Introduction to applied nonlinear dynamical systems and chaos, vol 2. Springer Science & Business Media
2003
Cited alongside, same era.
Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course. No. 87 in Applied Optimization, Kluwer Academic Publishers
2004
Cited alongside, same era.
Christopher C, Li C (2007) Limit cycles of differential equations. Springer Science & Business Media
2007
Cited alongside, same era.
Borkar VS (2008) Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press and Hindustan Book Agency
2008
Cited alongside, same era.
Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision 40(1):120–145
2011
Cited alongside, same era.
Juditsky A, Nemirovski A, Tauvel C (2011) Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems 1(1):17–58
2011
Cited alongside, same era.
Chiang CK, Yang T, Lee CJ, Mahdavi M, Lu CJ, Jin R, Zhu S (2012) Online optimization with gradual variations. In: COLT ’12: Proceedings of the 25th Annual Conference on Learning Theory
2012
Cited alongside, same era.
Teschl G (2012) Ordinary differential equations and dynamical systems, vol 140. American Mathematical Soc
2012
Cited alongside, same era.

Then

Daskalakis C, Panageas I (2018) The limit points of (optimistic) gradient descent in min-max optimization. In: Advances in Neural Information Processing Systems, pp 9236–9246
2018
Later among the works it cites.
Daskalakis C, Ilyas A, Syrgkanis V, Zeng H (2018) Training GANs with optimism. In: ICLR ’18: Proceedings of the 2018 International Conference on Learning Representations
2018
Later among the works it cites.
Karras T, Aila T, Laine S, Lehtinen J (2018) Progressive growing of gans for improved quality, stability, and variation. In: International Conference on Learning Representations
2018
Later among the works it cites.
Madry A, Makelov A, Schmidt L, Tsipras D, Vladu A (2018) Towards deep learning models resistant to adversarial attacks. In: ICLR ’18: Proceedings of the 2018 International Conference on Learning Representations
2018
Later among the works it cites.
Abernethy J, Lai KA, Wibisono A (2019) Last-iterate convergence rates for min-max optimization. arXiv preprint arXiv:190602027
2019
Later among the works it cites.
Adolphs L, Daneshmand H, Lucchi A, Hofmann T (2019) Local saddle point optimization: A curvature exploitation approach. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp 486–495
2019
Later among the works it cites.
Chavdarova T, Gidel G, Fleuret F, Lacoste-Julien S (2019) Reducing noise in GAN training with variance reduced extragradient. In: NeurIPS ’19: Proceedings of the 33rd International Conference on Neural Information Processing Systems
2019
Later among the works it cites.
Fiez T, Chasnov B, Ratliff LJ (2019) Convergence of learning dynamics in stackelberg games. arXiv preprint arXiv:190601217
2019
Later among the works it cites.
Flokas L, Vlatakis-Gkaragkounis EV, Piliouras G (2019) Poincaré recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games. In: NeurIPS ’19: Proceedings of the 33rd International Conference on Neural Information Processing Systems
2019
Later among the works it cites.
Gidel G, Berard H, Vignoud G, Vincent P, Lacoste-Julien S (2019a) A variational inequality perspective on generative adversarial networks. In: ICLR ’19: Proceedings of the 2019 International Conference on Learning Representations
2019
Later among the works it cites.
Jin C, Netrapalli P, Jordan MI (2019) What is local optimality in nonconvex-nonconcave minimax optimization? arXiv preprint arXiv:190200618
2019
Later among the works it cites.
Mertikopoulos P, Lecouat B, Zenati H, Foo CS, Chandrasekhar V, Piliouras G (2019) Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In: ICLR ’19: Proceedings of the 2019 International Conference on Learning Representations
2019
Later among the works it cites.
Naveiro R, Insua DR (2019) Gradient methods for solving stackelberg games. In: International Conference on Algorithmic DecisionTheory, Springer, pp 126–140
2019
Later among the works it cites.
Schäfer F, Anandkumar A (2019) Competitive gradient descent. In: Advances in Neural Information Processing Systems, pp 7623–7633
2019
Later among the works it cites.
Daskalakis C, Skoulakis S, Zampetakis M (2020) The complexity of constrained min-max optimization. arXiv preprint arXiv:200909623
2020
Closest in time.
Domingo-Enrich C, Jelassi S, Mensch A, Rotskoff G, Bruna J (2020) A mean-field analysis of two-player zero-sum games. arXiv preprint arXiv:200206277
2020
Closest in time.
Fiez T, Ratliff L (2020) Gradient descent-ascent provably converges to strict local minmax equilibria with a finite timescale separation. arXiv preprint arXiv:200914820
2020
Closest in time.
Hsieh YG, Iutzeler F, Malick J, Mertikopoulos P (2020) Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In: NeurIPS ’20: Proceedings of the 34th International Conference on Neural Information Processing Systems
2020
Closest in time.
Kamalaruban P, Huang YT, Hsieh YP, Rolland P, Shi C, Cevher V (2020) Robust reinforcement learning via adversarial training with langevin dynamics. arXiv preprint arXiv:200206063
2020
Closest in time.
Letcher A (2020) On the impossibility of global convergence in multi-loss optimization. arXiv preprint arXiv:200512649
2020
Closest in time.
Malitsky Y, Tam MK (2020) A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization 30(2):1451–1472
2020
Closest in time.
Mazumdar E, Ratliff LJ, Sastry SS (2020) On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science 2(1):103–131
2020
Closest in time.
Mertikopoulos P, Hallak N, Kavis A, Cevher V (2020) On the almost sure convergence of stochastic gradient descent in non-convex problems. Advances in Neural Information Processing Systems 33
2020
Closest in time.
Peng W, Dai YH, Zhang H, Cheng L (2020) Training gans with centripetal acceleration. Optimization Methods and Software pp 1–19
2020
Closest in time.
Flokas L, Vlatakis-Gkaragkounis EV, Piliouras G (2021) Solving min-max optimization with hidden structure via gradient descent ascent. arXiv preprint arXiv:210105248
2021
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…