Min-Max Optimization from a Dynamical Systems Viewpoint
summary
Shows that first-order min–max methods (gradient descent-ascent, extra-gradient/optimistic, proximal-point and their stochastic variants) are asymptotic pseudo-trajectories of a single mean dynamical flow, so discrete algorithms track continuous dynamics; uses Robbins–Monro formalism, APT theory, Poincaré–Bendixson and Kupka–Smale arguments. Conclusion: algorithms converge to internally chain transitive (ICT) sets (including attracting limit cycles) so tiny perturbations of bilinear games trap every method with high probability, and noise often does not help.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 1:47Why MinMax Optimization
- 9:43NonMonotone MinMax Optimization
- 13:04Objectives
- 17:17Assumptions
- 20:39Unifying Umbrella
- 24:38Template
- 25:32Holding Method
- 29:18T Capital
- 34:40When is a sequence generated
- 37:09Convergence properties
- 41:35Is there a fundamental difference
- 42:50The original linear game
- 43:59The result
- 46:00Conclusions
- 47:40Questions
- 51:12merit function
related talks
31mGradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale
54mExact Asymptotics and Universality for Gradient Flows and Empirical Risk Minimizers
12mEquilibrium Computation and the Foundations of Multi-Agent Machine Learning
01h 18mOptimization I
42mA Primal-dual Analysis of Margin Maximization by Steepest Descent Methods
27mTalk by Ali Kavis (UT Austin)
01h 01mRobustness, Stochastics, Uncertainty 2
55mLearning Minimax Estimators Via Online Learning