Equilibrium Computation and the Foundations of Multi-Agent Machine Learning

on YouTube ↗12m

" summary

Shows an exponential query lower bound for any first order method to find an approximate local solution of nonconvex min max problems even with Lipschitz continuous gradients and functions, while convex concave min max remains solvable by first order methods. Proof sketches a reduction to fixed point finding that makes local min max points accuracy equivalent to continuous fixed points, explaining the hardness, and suggests using topological algorithms based on fixed point theorems for asymptotic convergence instead of potential based methods.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:44Gradient Descent and Deep Learni
3. 2:33already in two-agent settings
4. 3:39Min-Max Optimization
5. 5:31Training Oscillations and/or Garbage Solution the simplest oscillating example
6. 7:03Minimization vs Min-Max Optimizat modern times...
7. 8:29Proof Idea
8. 10:09General Direction: Multi-Agent Lear

" related talks

• 51mMin-max Optimization: From Complexity to AlgorithmsEmmanouil Zampetakis · Adversarial Approaches in Machine Learning 2022
• 01h 00mMin-Max Optimization from a Dynamical Systems ViewpointPanayotis Mertikopoulos · Adversarial Approaches in Machine Learning 2022
• 57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max OptimizationNisheeth Vishnoi · Adversarial Approaches in Machine Learning 2022
• 27mTalk by Ali Kavis (UT Austin)Ali Kavis · Joint IFML/MPG Symposium 2024
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation IIJason Hartline · Economics and Computation Boot Camp 2015
• 51mAre Single-Loop Algorithms Sufficient for Unbalanced Minimax Optimization?Niao He · Adversarial Approaches in Machine Learning 2022
• 51mFirst-Order Methods and Hyperbolic ProgrammingJames Renegar · Hyperbolic Polynomials and Hyperbolic Programming