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.
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:
- Inner Loop (Max-player): Employs second-order optimization (gradients and Hessians) to locate an approximate local maximum.
- 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