Research map / Optimization / Nonconvex and smooth optimization
Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first convergence guarantees for alternating gradient descent-ascent in hidden convex-concave min-max games parameterized by two-layer neural networks under Gaussian initialization and overparameterization, plus an input-optimization variant.
Problem
Explaining why simple gradient methods converge in non-convex non-concave neural min-max games, and what architecture, initialization, and dynamics guarantee global convergence to a Nash equilibrium.
Approach
Combines hidden convex-concave structure with overparameterized two-layer networks: random Gaussian initialization gives non-singular Jacobians via random matrix theory, a path-length bound on AltGDA keeps iterates in a well-conditioned ball, and the two-sided PL condition then yields linear convergence to a Nash equilibrium.
Key results
- Two-layer networks with width scaling as Omega~(mu^2 n^3 / d_input) under Gaussian initialization yield AltGDA convergence to an epsilon-Nash equilibrium with high probability in hidden convex-concave games.
- Input-optimization games with random fixed networks are shown to converge under AltGDA with iteration complexity O~((1/eps) log(1/eps)) with high probability.
- The path-length bound for AltGDA is derived via a Lyapunov potential that interpolates the two players' Nash gaps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AltGDA rather than simultaneous GDA | Hidden convex-concave and two-sided-PL min-max games · Hidden neural min-max games | convergence | Helped |
| Increase both players’ hidden-layer widths to the stated cubic-overparameterization bounds | Neural-parameter min-max games · Hidden convex-concave neural min-max games | convergence | Helped |
| Use suitable Gaussian random initialization and the stated variance constraints | Two-layer neural networks trained with AltGDA · Hidden convex-concave neural min-max games | convergence guarantee | Helped |
Limitations
- Analysis restricted to one-hidden-layer fully connected networks with smooth (twice-differentiable) activations, excluding ReLU.
- Relies on generic data assumptions and an assumed existence of saddle points.
- Overparameterization requirement is cubic in sample size n, larger than the n^{3/2} in minimization settings.
Experimental setup
Builds on: hidden convex-concave games two-sided PL condition (Yang et al. 2020) NTK overparameterization analysis (Song et al. 2021) Gaussian Jacobian spectrum analysis
Closest papers by meaning
- Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent (NeurIPS 2021 · similarity 0.94)
- Generalized Natural Gradient Flows in Hidden Convex-Concave Games and GANs (ICLR 2022 · similarity 0.91)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.90)
- No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation (NeurIPS 2024 · similarity 0.88)
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.88)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.