Are Single-Loop Algorithms Sufficient for Unbalanced Minimax Optimization?
summary
A constructive claim: a primal‑dual lifting converts FX and HY to dual variables and yields a single‑loop first‑order algorithm (extrapolation + gradient updates) that attains the lower bound rates for bilinearly coupled, smooth problems with strong convexity on both sides. The method matches the LXY / sqrt(µXµY) dependence from the lower bound, extends to separable and stochastic variants, and empirically beats plain GDA; extension to general nonseparable or nonconvex cases remains open.
AI-written summary · about
chapters (17)
- 0:00Intro
- 2:27Problem Class. Oracles, Complexity
- 3:56Smooth Minimax Optimization
- 5:08Critical Regimes
- 6:07The Classical (Balanced) Setting
- 7:32The (Unbalanced) Strongly-Convex-Strongly-Concave Seting
- 19:00Motivation
- 19:54Short Answer
- 23:30Example: Quadratic Minimax Problems
- 24:06Inspiration : Primal-Dual for Bilinear Problems
- 26:01Inspiration It: Primal-Dual for Convex Minimization
- 30:40Our Approach: Acceleration via Lifting
- 33:24Main Result for SC-SC Setting
- 35:50Extension to C-SC Setting
- 38:36Summary and Open Questions
- 44:34NC-PL Problems: Stochastic Case
- 49:39Supplementary: Catalyst Acceleration
related talks
51mFirst-Order Methods and Hyperbolic Programming
12mEquilibrium Computation and the Foundations of Multi-Agent Machine Learning
01h 00mContinuous Methods 4
54mPrimal-Dual Algorithms for Hyperbolic Programming Problems
01h 23mImplicit Regularization II
01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms
01h 18mOptimization I
52mFrom the Ball-proximal (Broximal) Point Method to Efficient Training of LLM