Smooth Nonconvex Min-Max Optimization
summary
Gives concrete solvable cases and iteration counts rather than vague promises: when f is smooth and strongly concave in the adversary coordinate a provable projected gradient scheme needs about O(ε⁻²) gradient evaluations up to logs, while the concave but not strongly concave case requires roughly O(ε⁻³.5) (Nash) or O(ε⁻⁴) (Stackelberg) by smoothing plus proximal tricks and accelerated inner solvers, and small adversary radius or weak theta–alpha coupling is handled via Taylor approximations (K=1 needs D_a = Θ(ε), K=2 uses trust‑region style inner solves) and experiments show min‑max often fails on MNIST using naive simultaneous GD.
AI-written summary · about
chapters (5)
- 0:00Start
- 14:59Nonconvex-(strongly) concave setting
- 17:37Nonconvex-concave scenario
- 18:57Iteration complexity analysis
- 20:03Why do we observe significant rate drop?
related talks
46mCan Non-Convex Optimization be Robust?
01h 18mOptimization I
01h 01mRobustness, Stochastics, Uncertainty 2
42mOptimization Crash Course
27mTalk by Ali Kavis (UT Austin)
01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms
01h 07mOptimization Crash Course (continued)
51mFirst-Order Methods and Hyperbolic Programming