Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale

on YouTube ↗31m

" summary

Claim: gradient descent–ascent with a constructed finite tau_star provably makes the only locally attracting fixed points the strict local minimax (local Stackelberg) equilibria. Proof uses the continuous‑time limit, local linearization via the game Jacobian, Schur complements and Lyapunov criteria, plus a polynomial guard map built from Kronecker sums to find the exact tau threshold. Consequences: spurious attractors become unstable as tau grows, a concrete convergence rate for small step size, and almost‑sure local convergence under stochastic (noisy gradient) feedback.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:38Games as Abstractions for ML/OPT Problems
3. 1:48Local Min-Max & Zero-Sum Continuous Games
4. 3:44Do First Order Methods Provably Converge?
5. 4:36The Punchline: Yes, they do!
6. 6:09Local Equilibrium Notions and Optimality Conditio
7. 8:31Properties and Taxonomy
8. 9:46Analyzing T-GDA via Limiting CT Dynamical Syste !
9. 11:41Understanding Locally Stability of Equilibria via J.
10. 12:56Answer Q1: Differential Stackelberg Unstable for 1- Q1. Do unstable differential Stackelberg for T = 1 become stable as 7 grows? Yes!
11. 14:27Answer to Q2: Spurious Stable Points Become Unst Q2. Do spurious stable points of 1-GDA become unstable for finite r? Yes!
12. 15:33Summarizing Warm-Up: What's it Mean?
13. 17:20Constructing T via Guardian Map
14. 19:04Answer Q1: Yet, becomes stable for 7 2
15. 20:14Polynomial to Guard the Open Left Half Complex P Intuition via Lyapunov
16. 23:36Critical points w/o game theoretic meaning are unst
17. 24:26CT Stability Implies DT Convergence
18. 24:39T-GDA Convergence Rate
19. 25:42Extensions: Implications for Online Learning online learning r* results combine with
20. 27:59Take-Aways

" related talks

• 01h 00mMin-Max Optimization from a Dynamical Systems ViewpointPanayotis Mertikopoulos · Adversarial Approaches in Machine Learning 2022
• 05mNon-monotonic convergence of gradient descent with large stepsizeJingfeng Wu · 9th Annual Simons Institute Industry Day
• 12mLearning In The Presence Of Strategic Agents: Dynamics, Equilibria, And ConvergenceEric Mazumdar · Meet the Fellows Welcome Event
• 54mExact Asymptotics and Universality for Gradient Flows and Empirical Risk MinimizersAndrea Montanari · Deep Learning Theory Symposium 2021
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient DescentRaphaël Berthier · Deep Learning Theory Symposium 2021
• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013