Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization

Junchi Yang, Xiang Li, Niao He

Abstract

Adaptive algorithms like AdaGrad and AMSGrad are successful in nonconvex optimization owing to their parameter-agnostic ability—requiring no a priori knowledge about problem-specific parameters nor tuning of learning rates. However, when it comes to nonconvex minimax optimization, direct extensions of such adaptive optimizers without proper time-scale separation may fail to work in practice. We provide an example proving that the simple combination of Gradient Descent Ascent (GDA) with adaptive stepsizes can diverge if the primal-dual stepsize ratio is not carefully chosen. To address this, we introduce a Nested Adaptive framework (NeAda) that carries an inner loop for adaptively maximizing the dual variable with controllable stopping criteria and an outer loop for adaptively minimizing the primal variable. NeAda achieves near-optimal $\tilde{O}(\epsilon^{-2})$ and $\tilde{O}(\epsilon^{-4})$ gradient complexities in deterministic and stochastic settings, respectively, without prior information on smoothness or strong concavity. This represents the first algorithm to simultaneously achieve near-optimal convergence and parameter-agnostic adaptation in the nonconvex minimax setting.

Introduction: The Rise and Limits of Adaptive Optimization

Adaptive algorithms such as Adam and AdaGrad have become the workhorses of modern machine learning. Their primary appeal is their "parameter-agnostic" nature: they generally perform well without requiring researchers to manually tune learning rates based on obscure mathematical constants like Lipschitz smoothness or strong concavity.

However, the transition from simple minimization to minimax optimization—the mathematical foundation of Generative Adversarial Networks (GANs) and Distributionally Robust Optimization (DRO)—has proven difficult. In these settings, we seek to find a point that minimizes a function with respect to one variable ($x$) while maximizing it with respect to another ($y$). Despite the success of adaptive methods in standard training, they often exhibit instability, oscillations, or outright divergence when applied to minimax problems.

The Minimax Dilemma: Why Simple Adaptation Fails

The standard theoretical solution for stabilizing minimax problems is "time-scale separation," which involves making the max-player move significantly faster than the min-player. Mathematically, this requires setting a learning rate ratio proportional to the "condition number" of the problem.

In practice, the condition number is rarely known. This forces practitioners into exhaustive hyperparameter searches, undermining the very "set-it-and-forget-it" benefit that adaptive optimizers are supposed to provide. In the paper "Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization," authors Junchi Yang, Xiang Li, and Niao He provide a rigorous counterexample (Lemma 2.1) proving that a simple adaptive Gradient Descent Ascent (GDA) can diverge if this ratio is not precisely tuned. This explains why "just using Adam" frequently fails in complex GAN architectures.

The NeAda Framework: Stability Through Nesting

To resolve this instability, the authors introduce the Nested Adaptive (NeAda) framework. Rather than updating the primal ($x$) and dual ($y$) variables simultaneously, NeAda employs a hierarchical structure that automatically balances progress:

  1. Inner Loop: An adaptive optimizer (specifically a newly proposed Generalized AdaGrad) maximizes the dual variable $y$. This loop continues until a self-adjusting stopping criterion is met.
  2. Outer Loop: An adaptive optimizer updates the primal variable $x$ based on the results of the inner loop.

Key Innovations

  • Adaptive Stopping Criteria: In deterministic settings, the inner loop terminates when the gradient mapping norm falls below a threshold that shrinks as the outer loop progresses ($1/(t+1)$). In stochastic settings, the loop runs for a fixed $t+1$ iterations, ensuring sufficient progress without manual intervention.
  • Generalized AdaGrad: The framework utilizes a version of AdaGrad designed for the inner loop that achieves logarithmic regret in strongly convex settings without needing to know the strong concavity parameter.
  • Automatic Balancing: NeAda’s nested structure acts as a regulator, effectively "discovering" the necessary time-scale separation on its own.

Theoretical Guarantees: Near-Optimality Without Tuning

NeAda is the first framework to be provably convergent and near-optimal without requiring knowledge of the objective function's smoothness or concavity constants. It matches the best-known gradient complexities for nonconvex-strongly-concave (NC-SC) problems:

  • Deterministic Setting: $\tilde{O}(\epsilon^{-2})$
  • Stochastic Setting: $\tilde{O}(\epsilon^{-4})$

These rates are achieved while remaining entirely parameter-agnostic, filling a significant gap in minimax optimization theory.

Experimental Validation

The authors validated NeAda across synthetic and real-world tasks to test its robustness against non-nested adaptive methods:

  • Synthetic Functions: On the complex McCormick function (with added Gaussian noise), non-nested Adam and AMSGrad failed to converge when the learning rate ratio was small (e.g., 0.01). NeAda converged reliably regardless of the initial ratio.
  • Distributionally Robust Optimization (DRO) on MNIST: The authors applied NeAda to a DRO task using Multi-Layer Perceptrons (MLP) and Convolutional Neural Networks (CNN) to classify digits under adversarial perturbations. NeAda achieved higher test accuracy and faster convergence than non-nested Adam. Notably, when learning rates were set to the same scale, Adam’s performance plummeted, while NeAda remained robust.

Conclusion and Future Directions

NeAda provides a path toward making minimax optimization as accessible and stable as standard minimization. By nesting adaptive loops, the framework bypasses the need for manual time-scale tuning.

While the current theoretical guarantees focus on nonconvex-strongly-concave regimes—covering many practical use cases like DRO—future work remains to address the even more volatile nonconvex-nonconcave regime. Additionally, while NeAda is gradient-efficient, the computational overhead of nested loops in specific deep learning architectures offers an interesting avenue for further empirical optimization. NeAda stands as a significant step toward a truly parameter-agnostic future for adversarial machine learning.

Summary updated

Abstract

Adaptive algorithms like AdaGrad and AMSGrad are successful in nonconvex optimization owing to their parameter-agnostic ability -- requiring no a priori knowledge about problem-specific parameters nor tuning of learning rates. However, when it comes to nonconvex minimax optimization, direct extensions of such adaptive optimizers without proper time-scale separation may fail to work in practice. We provide such an example proving that the simple combination of Gradient Descent Ascent (GDA) with adaptive stepsizes can diverge if the primal-dual stepsize ratio is not carefully chosen; hence, a fortiori, such adaptive extensions are not parameter-agnostic. To address the issue, we formally introduce a Nested Adaptive framework, NeAda for short, that carries an inner loop for adaptively maximizing the dual variable with controllable stopping criteria and an outer loop for adaptively minimizing the primal variable. Such mechanism can be equipped with off-the-shelf adaptive optimizers and automatically balance the progress in the primal and dual variables. Theoretically, for nonconvex-strongly-concave minimax problems, we show that NeAda can achieve the near-optimal $\tilde{O}(\epsilon^{-2})$ and $\tilde{O}(\epsilon^{-4})$ gradient complexities respectively in the deterministic and stochastic settings, without prior information on the problem's smoothness and strong concavity parameters. To the best of our knowledge, this is the first algorithm that simultaneously achieves near-optimal convergence rates and parameter-agnostic adaptation in the nonconvex minimax setting. Numerically, we further illustrate the robustness of the NeAda family with experiments on simple test functions and a real-world application.
BibTeX
@inproceedings{yang2022nest,
  author = {Junchi Yang and Xiang Li and Niao He},
  title = {{Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=MXX18i8puEk},
}
Figure