A Second-order Equilibrium in Nonconvex-Nonconcave Min-max Optimization: Existence and Algorithm

Oren Mangoubi, Nisheeth K. Vishnoi

Abstract

Min-max optimization of an objective function $f: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$ is an important model for robustness in an adversarial setting, with applications to many areas including optimization, economics, and deep learning. In many applications $f$ may be nonconvex-nonconcave, and finding a global min-max point may be computationally intractable. There is a long line of work that seeks computationally tractable algorithms for alternatives to the min-max optimization model. However, many of the alternative models have solution points which are only guaranteed to exist under strong assumptions on $f$, such as convexity, monotonicity, or special properties of the starting point. We propose an optimization model, the $\varepsilon$-greedy adversarial equilibrium, and show that it can serve as a computationally tractable alternative to the min-max optimization model. Roughly, we say that a point $(x^\star, y^\star)$ is an $\varepsilon$-greedy adversarial equilibrium if $y^\star$ is an $\varepsilon$-approximate local maximum for $f(x^\star,\cdot)$, and $x^\star$ is an $\varepsilon$-approximate local minimum for a "greedy approximation" to the function $\max_z f(x, z)$ which can be efficiently estimated using second-order optimization algorithms. We prove the existence of such a point for any smooth function which is bounded and has Lipschitz Hessian. To prove existence, we introduce an algorithm that converges from any starting point to an $\varepsilon$-greedy adversarial equilibrium in a number of evaluations of the function $f$, the max-player's gradient $\nabla_y f(x,y)$, and its Hessian $\nabla^2_y f(x,y)$, that is polynomial in the dimension $d$, $1/\varepsilon$, and the bounds on $f$ and its Lipschitz constant.

Introduction

Min-max optimization serves as the mathematical foundation for several critical domains in artificial intelligence, including Generative Adversarial Networks (GANs) and robust machine learning. The objective is to identify a point $(x, y)$ that minimizes a function $f$ with respect to $x$ while simultaneously maximizing it with respect to $y$. While this problem is well-understood in the convex-concave setting, modern deep learning applications typically involve nonconvex-nonconcave functions. In these scenarios, finding a global min-max point is often NP-hard.

Existing "local" versions of min-max points frequently fail to exist for general functions or require restrictive assumptions like monotonicity. This work addresses the gap between theoretical intractability and the practical requirement for stable, efficient adversarial training by introducing a new solution concept: the $\epsilon$-greedy adversarial equilibrium.

The $\epsilon$-Greedy Adversarial Equilibrium

The core innovation of this paper is the departure from the assumption of an "all-powerful" adversary. Instead, the authors propose a model where the adversary is computationally bounded. This is formalized through two primary concepts:

  1. Greedy Paths: The max-player (adversary) is assumed to update their variable $y$ by following a trajectory where the function value increases or the second derivative is positive. This behavior mimics standard optimization algorithms like gradient ascent.
  2. The Greedy Max Function ($g_\epsilon$): This function represents the maximum value attainable by the max-player starting from a point $y$ using only greedy paths.
Illustration of greedy paths from a starting point $A$ to various local maxima $B, C, D$ in a non-convex landscape.

As shown in the figure above, a small change in the min-player's variable $x$ can cause the max-player to converge to a different local peak (e.g., jumping from $B$ to $C$ or $D$). To handle the resulting discontinuities in the greedy max function, the authors employ Gaussian smoothing. By convolving the function with a Gaussian distribution, they create a smooth approximation that the min-player can optimize effectively.

Algorithmic Approach

The proposed algorithm utilizes second-order information (Hessians) for the max-player to guarantee convergence to a local maximum. For the min-player, a stochastic gradient descent (SGD) approach is used to navigate the smoothed landscape and escape saddle points. Notably, the algorithm does not require the gradient of the function with respect to the min-player's variable $x$, making it applicable in certain "black-box" settings.

Key Results and Theoretical Guarantees

The authors provide several significant theoretical contributions:

  • Guaranteed Existence: The $\epsilon$-greedy adversarial equilibrium is proven to exist for any smooth, bounded function with a Lipschitz Hessian, a major improvement over previous local Nash equilibrium definitions.
  • Polynomial Complexity: The algorithm finds an $\epsilon$-equilibrium in a number of function and gradient evaluations that is polynomial in the dimension $d$, the accuracy $1/\epsilon$, and the function's smoothness constants.
  • Global Convergence: Unlike many local methods, this algorithm is guaranteed to converge from any starting point.
  • Duality Gap: In the convex-concave case, the equilibrium point is shown to be near-optimal, with a duality gap of $O(\epsilon^2)$.

Synthetic evaluations on highly non-convex functions, such as mixtures of Gaussians and periodic trigonometric functions, demonstrate the algorithm's ability to identify stable points where traditional methods might oscillate or fail.

Limitations and Future Work

While the complexity is polynomial, the current exponents are high, suggesting room for optimization. Future research directions include extending the framework to constrained optimization settings and developing more efficient approximation techniques for Gaussian convolution to facilitate scaling to high-dimensional neural network parameters.

Summary updated

Abstract

Min-max optimization of an objective function $f: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$ is an important model for robustness in an adversarial setting, with applications to many areas including optimization, economics, and deep learning. In many applications $f$ may be nonconvex-nonconcave, and finding a global min-max point may be computationally intractable. There is a long line of work that seeks computationally tractable algorithms for alternatives to the min-max optimization model. However, many of the alternative models have solution points which are only guaranteed to exist under strong assumptions on $f$, such as convexity, monotonicity, or special properties of the starting point. We propose an optimization model, the $\varepsilon$-greedy adversarial equilibrium, and show that it can serve as a computationally tractable alternative to the min-max optimization model. Roughly, we say that a point $(x^\star, y^\star)$ is an $\varepsilon$-greedy adversarial equilibrium if $y^\star$ is an $\varepsilon$-approximate local maximum for $f(x^\star,\cdot)$, and $x^\star$ is an $\varepsilon$-approximate local minimum for a "greedy approximation" to the function $\max_z f(x, z)$ which can be efficiently estimated using second-order optimization algorithms. We prove the existence of such a point for any smooth function which is bounded and has Lipschitz Hessian. To prove existence, we introduce an algorithm that converges from any starting point to an $\varepsilon$-greedy adversarial equilibrium in a number of evaluations of the function $f$, the max-player's gradient $\nabla_y f(x,y)$, and its Hessian $\nabla^2_y f(x,y)$, that is polynomial in the dimension $d$, $1/\varepsilon$, and the bounds on $f$ and its Lipschitz constant.
BibTeX
@misc{mangoubi2020second,
  author = {Oren Mangoubi and Nisheeth K. Vishnoi},
  title = {{A Second-order Equilibrium in Nonconvex-Nonconcave Min-max Optimization: Existence and Algorithm}},
  year = {2020},
  eprint = {2006.12363},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.12363},
}
Figure