Min-max Optimization: From Complexity to Algorithms
summary
Shows that finding an approximate local min‑max equilibrium is PPAD-complete and that any black‑box first‑order method needs an exponential query lower bound (worst‑case). Gives a reduction from Sperner via an Edge–Triangle game, then builds a computationally efficient way to turn the discrete game into a smooth Lipschitz function by designing smooth interpolation coefficients with polynomially bounded derivatives. Uses that construction to produce a second‑order dynamics that converges asymptotically; open cases include product constraints and higher‑order smoothness.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:35Min-max or Multi-agent Optimization GANS
- 1:00Training Oscillations or Chaotic Behavior
- 1:12Min-max Optimization Issues
- 1:42Overview of the Talk
- 2:43Our Focus: Minimization vs Min-Max Optimization
- 5:06Nonconvex-Nonconcave Objectives
- 6:28Minimization vs Min-Max Optimization modern times...
- 9:34The Complexity of Constrained Min-max
- 15:46Sperner's Lemma
- 18:20The SPERNER problem
- 21:06Rough Proof Idea: Edge-Triangle Game
- 23:24Edge-Triangle Game (Min-Max)
- 27:56Edge-Triangle Game (Min-Min ????)
- 30:46Proof Idea: From Discrete to Continuous
- 41:55Sperner Dynamics
- 44:20Summary
related talks
12mEquilibrium Computation and the Foundations of Multi-Agent Machine Learning
01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation II
47mSuccinct Representations and Efficient Algorithms Based on Linear Programming
51mFirst-Order Methods and Hyperbolic Programming
55mLearning Minimax Estimators Via Online Learning
27mTalk by Ali Kavis (UT Austin)
01h 04mSubmodularity: Theory and Applications I
20mThe Complexity of Infinite-Horizon General-Sum Stochastic Games