Computationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max Optimization
summary
Proposes a new solution concept called epsilon-greedy adversarial equilibrium that limits the maximizer to greedy paths and proves such equilibria exist for bounded smooth functions with Lipschitz Hessian. Gives an algorithm using gradient and Hessian oracles plus smoothing that finds an equilibrium in time roughly poly(D,1/epsilon,B,L), notes Gaussian smoothing causes the polynomial-in-D bottleneck, and offers a first-order variant with near-logarithmic dimension dependence that empirically avoids cycling and improves multimodal GAN training.
AI-written summary · about
chapters (21)
- 0:00Introduction
- 2:07Learning and minimization
- 3:38Epsilon local minima
- 6:20Nonconcave minima
- 10:37GANs
- 11:30Local Equilibrium
- 13:35Local Predictions
- 15:35Theoretical Issues
- 17:09Key Idea
- 23:06Greedy Paths
- 24:41G Function
- 28:16Equilibrium
- 31:41Randomization
- 34:06Discontinuity
- 37:28Algorithm
- 40:56Computing G
- 42:33First Order
- 44:48Conclusion
- 47:13Boundedness
- 48:48Guarantee
- 51:08Dependence
related talks
12mEquilibrium Computation and the Foundations of Multi-Agent Machine Learning
27mTalk by Ali Kavis (UT Austin)
49mDiscrete Optimization using Log-Concave Polynomials
46mCan Non-Convex Optimization be Robust?
55mLearning Minimax Estimators Via Online Learning
01h 01mRobustness, Stochastics, Uncertainty 2
51mFirst-Order Methods and Hyperbolic Programming
01h 04mSubmodularity: Theory and Applications II