Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization

Junchi Yang, Xiang Li, Niao He

TL;DR

Adaptive gradient methods like Adam and AdaGrad often fail in nonconvex minimax optimization (e.g., GANs, adversarial training) unless the learning rates for the min and max players are carefully tuned to a specific ratio. This paper introduces NeAda, a nested adaptive framework that automatically balances these updates without requiring prior knowledge of problem parameters. It achieves near-optimal convergence rates for nonconvex-strongly-concave problems, making minimax optimization truly parameter-agnostic and robust.

What Problem Does This Paper Address?

Minimax optimization—formulated as finding the saddle point of $\min_x \max_y f(x,y)$—is the mathematical engine behind generative adversarial networks (GANs), adversarial training, and distributionally robust optimization. In standard deep learning (pure minimization), adaptive optimizers like Adam and AdaGrad are beloved because they are "parameter-agnostic": they dynamically adjust their stepsizes, saving practitioners from manually tuning learning rates based on the mathematical smoothness of the loss landscape.

However, applying these adaptive methods directly to nonconvex minimax problems often leads to training instability. Theoretical research shows that minimax optimization requires a strict "time-scale separation"—a specific ratio between the learning rates of the $x$ (primal) and $y$ (dual) variables. This ratio depends heavily on unknown problem parameters like the condition number. If you don't know these parameters, you have to guess the ratio. If you guess wrong, the algorithm diverges. Therefore, existing adaptive methods are not truly parameter-agnostic when applied to minimax problems.

Methods

To solve this, the authors propose the Nested Adaptive (NeAda) framework. Instead of updating $x$ and $y$ simultaneously (which the authors term "non-nested" methods), NeAda uses a double-loop structure:

  1. Inner Loop: Maximizes the dual variable $y$ using an adaptive optimizer until a specific, easily checkable stopping criterion is met (e.g., the gradient norm drops below a threshold that gradually tightens over time).
  2. Outer Loop: Updates the primal variable $x$ using an adaptive step (like AdaGrad) based on the optimized $y$.
Comparison of Non-nested and Nested Adaptive (NeAda) algorithms

By nesting the updates and dynamically controlling the inner-loop accuracy, NeAda automatically balances the progress of both variables without needing a hard-coded time-scale separation.

As a bonus contribution, the authors also introduce a Generalized AdaGrad algorithm for strongly-convex subproblems. This subroutine can adaptively solve the inner loop without needing to know the problem's strong convexity parameter.

Datasets

The authors evaluate NeAda on:

  • Simple 2D Test Functions: Including a modified McCormick function to visually demonstrate divergence in non-nested methods.
  • Synthetic 2D Dataset: Used for a Distributionally Robust Optimization (DRO) task.
  • MNIST: Used for a real-world DRO task (training a 3-layer Convolutional Neural Network against adversarial perturbations).

Key Insights and Ideas

  • Mathematical proof of divergence: The authors provide a formal proof showing that standard, non-nested adaptive methods will diverge on a simple deterministic problem if the stepsize ratio isn't strictly greater than the problem's condition number. This proves that standard Adam/AdaGrad are fundamentally not parameter-agnostic in minimax settings.
  • Nesting replaces time-scale separation: By fully optimizing the inner loop to a dynamic threshold, NeAda effectively bypasses the need for a fixed learning rate ratio. The inner loop does the heavy lifting of finding the optimal dual variable, allowing the outer loop to safely take adaptive steps.
  • Generalized AdaGrad is parameter-free: The authors show that by tweaking the decay rate of AdaGrad, it can achieve logarithmic or sub-linear regret on strongly convex problems without requiring the user to input the strong convexity parameter.

Key Results

  • Theoretical Guarantees: NeAda-AdaGrad is the first adaptive framework to achieve near-optimal gradient complexities for nonconvex-strongly-concave (NC-SC) problems without knowing problem parameters. It achieves $\tilde{\mathcal{O}}(\epsilon^{-2})$ in deterministic settings and $\tilde{\mathcal{O}}(\epsilon^{-4})$ in stochastic settings.
  • Empirical Robustness: On the MNIST DRO task, standard non-nested Adam requires a carefully tuned learning rate ratio to achieve high accuracy. If the ratio is set to 1:1, standard Adam overfits and test accuracy plummets.
  • NeAda's Stability: Under that exact same "bad" 1:1 learning rate ratio, NeAda-Adam maintains stability, avoids overfitting, and still achieves high test accuracy, proving its parameter-agnostic robustness in practice.
Convergence comparison showing NeAda's robustness across different stepsize ratios

Limitations and Future Work

  • Theoretical Scope: The convergence proofs are currently limited to the nonconvex-strongly-concave (NC-SC) regime. While this covers many robust optimization tasks, it does not fully cover the nonconvex-nonconcave regimes often seen in complex GANs.
  • Future Work: The authors suggest extending parameter-agnostic algorithms to more general nonconvex-concave or nonconvex-nonconcave minimax problems. They also highlight the need to further investigate the convergence behavior of Adam-type algorithms with general decaying rates in strongly convex online optimization.

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 with AdaGrad stepsizes can achieve the near-optimal $\widetilde{O}(\epsilon^{-2})$ and $\widetilde{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