SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients

Feihu Huang, Junyi Li, Heng Huang

TL;DR

SUPER-ADAM is a universal framework that unifies popular adaptive gradient methods (like Adam and Adagrad) into a single theoretical structure. By integrating momentum-based variance reduction, it achieves the best-known convergence rate for nonconvex optimization ($\tilde{O}(\epsilon^{-3})$), effectively hitting the theoretical "speed limit" for these types of problems while remaining highly effective in practice.

Introduction: The Theoretical Gap in Adaptive Optimizers

In the world of deep learning, optimizers like Adam are the default choice because they automatically adjust learning rates for different parameters, making them easier to tune than standard Stochastic Gradient Descent (SGD). However, these "adaptive" methods face three major hurdles:

  1. Theoretical Gap: Most adaptive methods have a "worst-case" convergence complexity of $O(\epsilon^{-4})$, which is slower than the theoretical lower bound of $O(\epsilon^{-3})$ for stochastic nonconvex optimization.
  2. Lack of Unity: Different algorithms (Adam, Adagrad, AMSGrad) are often treated as distinct entities with their own specific proofs and conditions.
  3. Generalization: Adaptive methods sometimes generalize poorly to unseen data compared to SGD.

To bridge these gaps, researchers have introduced SUPER-ADAM, providing a single framework that is both faster in theory and more robust in practice.

Comparison of Algorithm Complexities

The SUPER-ADAM Framework

The core of SUPER-ADAM is the introduction of a Universal Adaptive Matrix ($H_t$). Instead of hard-coding a specific update rule, the authors frame the optimization as a Mirror Descent problem.

Key technical components include:

  • The Universal Adaptive Matrix: By changing how $H_t$ is constructed, SUPER-ADAM can "mimic" almost any existing adaptive optimizer, whether it uses coordinate-wise learning rates (like Adam) or global ones (like AdaGrad-Norm). This unification allows researchers to apply the same convergence proofs to a whole family of algorithms.
  • Variance Reduction ($\tau = 1$): This is the framework's "secret sauce." SUPER-ADAM can incorporate a STORM-style gradient estimator. This technique uses information from previous steps to reduce the "noise" in the current gradient estimate. This variance reduction is precisely what allows the algorithm to reach the optimal $\tilde{O}(\epsilon^{-3})$ complexity.
  • Weighted Updates: Unlike standard Adam, which uses a fixed momentum parameter, SUPER-ADAM uses a decreasing weight ($\mu_t$) to combine the current solution with the new proposal. This allows the algorithm to converge under much milder mathematical assumptions (e.g., it doesn't require the strict "bounded gradient" assumption that many other proofs rely on).

Empirical Validation

The authors validated SUPER-ADAM across several standard benchmarks to ensure it works for both vision and language tasks:

  • Image Classification: Tested on CIFAR-10 and CIFAR-100 (using ResNet-18 and VGG-19 architectures), as well as the large-scale ImageNet dataset (using ResNet-34).
  • Language Modeling: Evaluated on WikiText-2 using both a 2-layer LSTM and a Transformer architecture.

Key Results

  • Superior Convergence: In head-to-head tests on CIFAR-10 and CIFAR-100, SUPER-ADAM ($\tau=1$) consistently reached lower training loss and higher test accuracy faster than Adam, AMSGrad, AdaBelief, and STORM.
  • ImageNet Performance: On the challenging ImageNet dataset, SUPER-ADAM outperformed state-of-the-art variants like Adam+ and AdaBelief, demonstrating its scalability to massive datasets.
  • Stability through Geometry: The authors show that the "condition number" of their adaptive matrix improves over time. Essentially, the algorithm "learns" the geometry of the loss surface, becoming more stable as it nears a solution.

Limitations and Future Work

While SUPER-ADAM represents a significant theoretical and practical leap, it does come with trade-offs:

  • Hyperparameter Complexity: While the framework is universal, the "faster" variance-reduced version ($\tau=1$) introduces several new hyperparameters. While the authors provide theoretical ranges for these, practical users may still find them more complex to tune than vanilla Adam.
  • Computational Cost: The variance-reduced version requires two stochastic gradient evaluations per iteration. While this leads to fewer total iterations to converge, each individual iteration is slightly more computationally expensive.
  • Sparse Data: The theoretical analysis focuses on the "worst-case" dense gradient setting. Exploring how this universal framework specifically handles extremely sparse data (like large-scale recommendation systems) remains an open area for further empirical study.

Summary updated

Abstract

Adaptive gradient methods have shown excellent performances for solving many machine learning problems. Although multiple adaptive gradient methods were recently studied, they mainly focus on either empirical or theoretical aspects and also only work for specific problems by using some specific adaptive learning rates. Thus, it is desired to design a universal framework for practical algorithms of adaptive gradients with theoretical guarantee to solve general problems. To fill this gap, we propose a faster and universal framework of adaptive gradients (i.e., SUPER-ADAM) by introducing a universal adaptive matrix that includes most existing adaptive gradient forms. Moreover, our framework can flexibly integrate the momentum and variance reduced techniques. In particular, our novel framework provides the convergence analysis support for adaptive gradient methods under the nonconvex setting. In theoretical analysis, we prove that our SUPER-ADAM algorithm can achieve the best known gradient (i.e., stochastic first-order oracle (SFO)) complexity of $\tilde{O}(\epsilon^{-3})$ for finding an $\epsilon$-stationary point of nonconvex optimization, which matches the lower bound for stochastic smooth nonconvex optimization. In numerical experiments, we employ various deep learning tasks to validate that our algorithm consistently outperforms the existing adaptive algorithms. Code is available at https://github.com/LIJUNYI95/SuperAdam
BibTeX
@inproceedings{huang2021super,
  author = {Feihu Huang and Junyi Li and Heng Huang},
  title = {{SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=nFdJSm9dy83},
}
Figure