Greedy Adversarial Equilibrium: An Efficient Alternative to\n Nonconvex-Nonconcave Min-Max Optimization

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. In many applications, such as deep learning, $f$ may be nonconvex-nonconcave, making global min-max points computationally intractable. We propose the $\varepsilon$-greedy adversarial equilibrium as a computationally tractable alternative. We prove that such a point exists for any smooth, bounded function with a Lipschitz Hessian and introduce an algorithm that converges to it in polynomial time.

Introduction

Min-max optimization, formulated as $\min_x \max_y f(x,y)$, is fundamental to robust machine learning and Generative Adversarial Networks (GANs). However, in the nonconvex-nonconcave regime typical of deep learning, traditional solution concepts face significant hurdles. Global solutions are NP-hard to find, and local min-max points often do not exist. Existing algorithms frequently rely on strong assumptions like convexity or monotonicity that are rarely met in practice.

This work addresses the need for a "tractable alternative"—an equilibrium concept that is both meaningful for robustness and guaranteed to exist and be findable efficiently. By restricting the adversary to "greedy" behavior, the model more closely matches how GANs are actually trained in the real world.

The Greedy Adversarial Equilibrium

The core innovation is the $\epsilon$-greedy adversarial equilibrium. Instead of assuming an omnipotent adversary capable of finding a global maximum, the authors model the max-player as a computationally bounded agent using greedy updates (following gradients and directions of high curvature).

Greedy Max Function and Paths

The "best response" of this bounded adversary is captured by the Greedy Max Function ($g_\epsilon$). This function represents the value achieved by the max-player starting from a given point and following an $\epsilon$-greedy path to a local maximum.

Illustration of greedy paths on a non-convex landscape. Starting from point A, the max-player follows different greedy paths to reach local maxima like B, C, or D, defining the greedy max function.

Because the max-player's local maximum can jump discontinuously as the min-player moves, the authors employ Gaussian convolution to smooth the objective. This enables the min-player to utilize gradient-based updates even on a landscape that is inherently discontinuous.

Algorithmic Approach

The proposed algorithm operates in two levels:

  1. Inner Loop (Max-player): Employs second-order optimization (gradients and Hessians) to locate an approximate local maximum.
  2. Outer Loop (Min-player): Uses a "noisy SGD" approach to minimize the smoothed greedy max function.

Notably, the algorithm only requires first and second-order information for the max-player's variables ($y$), while requiring only zeroth-order information (function values) for the min-player ($x$).

Key Results

The primary contribution is Theorem 3.1, which establishes both the existence of the equilibrium and the efficiency of the proposed algorithm. Key findings include:

  • Existence: An $\epsilon$-greedy adversarial equilibrium is guaranteed to exist for any smooth, bounded function with a Lipschitz Hessian.
  • Polynomial Efficiency: The equilibrium can be found in a number of evaluations (function, gradient, and Hessian) that is polynomial in the dimension $d$, the accuracy $1/\epsilon$, and the function's bounds.
  • Global Convergence: Unlike many local optimization methods, this algorithm is proven to converge from any starting point.
  • Duality Gap: In the specific case of strongly convex-concave functions, the equilibrium is shown to be near-optimal, with a duality gap of $O(\epsilon^2)$.

Discussion and Limitations

While the polynomial complexity is a significant theoretical milestone, the high exponents currently make the algorithm more of a theoretical proof-of-concept than a practical replacement for standard optimizers like Adam in large-scale settings. The requirement for Hessian information ($\nabla^2_y f$) also poses a computational challenge for very large models.

Future work aims to develop first-order versions of this equilibrium to enhance practicality. By providing a stable target for optimization in complex landscapes where traditional targets might be "ghosts," this research bridges the gap between optimization theory and deep learning practice.

Summary updated

Abstract

Min-max optimization of an objective function $f: \\mathbb{R}^d \\times\n\\mathbb{R}^d \\rightarrow \\mathbb{R}$ is an important model for robustness in an\nadversarial setting, with applications to many areas including optimization,\neconomics, and deep learning. In many applications $f$ may be\nnonconvex-nonconcave, and finding a global min-max point may be computationally\nintractable. There is a long line of work that seeks computationally tractable\nalgorithms for alternatives to the min-max optimization model. However, many of\nthe alternative models have solution points which are only guaranteed to exist\nunder strong assumptions on $f$, such as convexity, monotonicity, or special\nproperties of the starting point. We propose an optimization model, the\n$\\varepsilon$-greedy adversarial equilibrium, and show that it can serve as a\ncomputationally tractable alternative to the min-max optimization model.\nRoughly, we say that a point $(x^\\star, y^\\star)$ is an $\\varepsilon$-greedy\nadversarial equilibrium if $y^\\star$ is an $\\varepsilon$-approximate local\nmaximum for $f(x^\\star,\\cdot)$, and $x^\\star$ is an $\\varepsilon$-approximate\nlocal minimum for a "greedy approximation" to the function $\\max_z f(x, z)$\nwhich can be efficiently estimated using second-order optimization algorithms.\nWe prove the existence of such a point for any smooth function which is bounded\nand has Lipschitz Hessian. To prove existence, we introduce an algorithm that\nconverges from any starting point to an $\\varepsilon$-greedy adversarial\nequilibrium in a number of evaluations of the function $f$, the max-player's\ngradient $\\nabla_y f(x,y)$, and its Hessian $\\nabla^2_y f(x,y)$, that is\npolynomial in the dimension $d$, $1/\\varepsilon$, and the bounds on $f$ and its\nLipschitz constant.\n
BibTeX
@misc{mangoubi2020greedy,
  author = {Oren Mangoubi and Nisheeth K. Vishnoi},
  title = {{Greedy Adversarial Equilibrium: An Efficient Alternative to\textbackslash\{\}n Nonconvex-Nonconcave Min-Max Optimization}},
  year = {2020},
  eprint = {2006.12363},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.12363},
}
Figure