Min-Max Optimization Requires Exponentially Many Queries

2026/05/13 by Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1 · 1 voice
Computer Science · Mathematics · #cs.CC #cs.DS #cs.GT #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.2605.13806

Abstract

We study the query complexity of min-max optimization of a nonconvex-nonconcave function f over [0,1]^d × [0,1]^d. We show that, given oracle access to f and to its gradient ∇ f, any algorithm that finds an ε-approximate stationary point must make a number of queries that is exponential in 1/ε or d.

Citations

• The Complexity of Min-Max Optimization with Product Constraints
• Safety Alignment of LMs via Non-cooperative Games
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
• On the Role of Constraints in the Complexity of Min-Max Optimization
• COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences
• Game Theory Meets Large Language Models: A Systematic Survey with Taxonomy and New Frontiers
• A Minimaximalist Approach to Reinforcement Learning from Human Feedback
• Nash Learning from Human Feedback
• Beyond first-order methods for non-convex non-concave min-max optimization
• Pure-Circuit: Tight Inapproximability for PPAD
• Newton and interior-point methods for (constrained) nonconvex-nonconcave minmax optimization with stability and instability guarantees
• Subgradient Ellipsoid Method for Nonsmooth Convex Problems
• The Complexity of Constrained Min-Max Optimization
• Newton-type Methods for Minimax Optimization
• Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Stable Opponent Shaping in Differentiable Games
• The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
• The Mechanics of n-Player Differentiable Games
• Lower bounds for finding stationary points I
• Cycles in adversarial regularized learning
• Towards Deep Learning Models Resistant to Adversarial Attacks
• Settling the complexity of computing approximate two-player Nash equilibria
• Inapproximability of Nash Equilibrium

Discussions

• For me, perhaps the technically most surprising aspect of this paper is that the PPAD-hardness result did not translate to a query complexity lower bound in the black box setting. At least this gap is [bsky, 0 points, 0 comments]

Related

• The Complexity of Constrained Min-Max Optimization
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
• Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss