The complexity of constrained min-max optimization

By Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis. 2020

169 citations recorded by the source corpus.

Despite its important applications in Machine Learning, min-max optimization of objective functions that are nonconvex-nonconcave remains elusive. Not only are there no known first-order methods converging to even approximate local min-max equilibria (a.k.a. approximate saddle points), but the computational complexity of identifying them is also poorly understood. In this paper, we provide a characterization of the computational complexity as well as of the limitations of first-order methods in this problem. Specifically, we show that in linearly constrained min-max optimization problems with nonconvex-nonconcave objectives an approximate local min-max equilibrium of large enough approximation is guaranteed to exist, but computing such a point is PPAD-complete. The same is true of computing an approximate fixed point of the (Projected) Gradient Descent/Ascent update dynamics, which is computationally equivalent to computing approximate local min-max equilibria. An important byproduct of our proof is to establish an unconditional hardness result in the Nemirovsky-Yudin 1983 oracle optimization model, where we are given oracle access to the values of some function f : P → [−1, 1] and its gradient ∇ f, where P ⊆ [0, 1]d is a known convex polytope. We show that any algorithm that uses such first-order oracle access to f and finds an ε-approximate local min-max equilibrium needs to make a number of oracle queries that is exponential in at least one of 1/ε, L, G, or d, where L and G are respectively the smoothness and Lipschitzness of f. This comes in sharp contrast to minimization problems, where finding approximate local minima in the same setting can be done with Projected Gradient Descent using O(L/ε) many queries. Our result is the first to show an exponential separation between these two fundamental optimization problems in the oracle model.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Mathematical Optimization

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “The recent works of Daskalakis et al. [2021] and Diakoniko-las et al. [2021] show that, for general smooth objectives, the computation of even approximate ﬁrst-order locally optimal min-max solutions is intractable, motivating the identiﬁcation of structural assumptions on the objective function…”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “As already discussed, recent work of [16] shows that for general smooth objectives the computation of even approximate ﬁrst-order locally optimal min-max solutions is intractable, motivating the identiﬁcation of structural assumptions on the objective function for which these intractability…”