Abstract
Adaptive gradient methods have become the standard for training modern deep learning architectures due to their ability to automatically adjust learning rates. However, existing methods often suffer from fragmented theoretical foundations, suboptimal gradient complexity, and inconsistent generalization. This paper introduces SUPER-ADAM, a unified optimization framework that integrates variance reduction techniques with a flexible adaptive matrix. SUPER-ADAM achieves the theoretical lower bound for gradient complexity in nonconvex optimization—$\tilde{O}(\epsilon^{-3})$—while providing a "universal" framework applicable to a wide range of adaptive rules. Empirical results on ImageNet and WikiText-2 demonstrate that SUPER-ADAM outperforms state-of-the-art optimizers in both convergence speed and final performance.
Introduction
Modern deep learning relies heavily on adaptive gradient methods like Adam and Adagrad. These methods simplify hyperparameter tuning by scaling updates based on historical gradient information. Despite their empirical success, they face significant challenges:
- Fragmentation: A lack of a unified theory for different adaptive rules.
- Suboptimal Complexity: Most standard methods exhibit a gradient complexity of $O(\epsilon^{-4})$ to reach an $\epsilon$-stationary point.
- Generalization Gaps: Some adaptive methods fail to match the generalization performance of SGD.
SUPER-ADAM addresses these issues by providing a robust, theoretically optimal framework that bridges the gap between adaptive gradients and variance reduction.
The SUPER-ADAM Framework
The SUPER-ADAM framework is built upon three core pillars:
- Universal Adaptive Matrix ($H_t$): By abstracting the adaptive learning rate into a flexible matrix $H_t$, the framework can recover various existing algorithms (e.g., Adam, AMSGrad, Adagrad) or implement new quasi-Newton approaches.
- Mirror Descent Formulation: The update step is framed as a generalized projection, enabling the algorithm to handle constrained optimization problems that were previously difficult for variance-reduced methods.
- Momentum-based Variance Reduction (STORM): SUPER-ADAM incorporates a recursive gradient estimator. In its $\tau = 1$ mode, it significantly reduces stochastic noise, accelerating convergence to the theoretical lower bound.
Theoretical and Empirical Results
The theoretical strength of SUPER-ADAM is summarized in the comparison table above. Notably, SUPER-ADAM ($\tau=1$) achieves a complexity of $\tilde{O}(\epsilon^{-3})$, matching the known lower bound for stochastic smooth nonconvex optimization. Unlike previous methods that require specific learning rate rules and numerous conditions, SUPER-ADAM offers a universal approach with minimal constraints.
Experimental Validation
The researchers evaluated SUPER-ADAM across diverse benchmarks:
- Computer Vision: On ImageNet (ResNet-34) and CIFAR-10/100, SUPER-ADAM demonstrated faster training loss decay and higher top-1 accuracy than Adam, AdaBelief, and STORM.
- Natural Language Processing: In WikiText-2 experiments using LSTMs and Transformers, SUPER-ADAM achieved lower perplexity, indicating superior generalization capabilities.
A key observation from the experiments was the stability of the adaptive matrix $H_t$. The condition number of this matrix was shown to decrease over time, suggesting that the algorithm becomes more stable as it approaches a local minimum.
Conclusion and Future Directions
SUPER-ADAM provides a powerful, unified perspective on adaptive optimization. While it achieves optimal theoretical complexity, practical implementation of the $\tau=1$ mode requires careful hyperparameter tuning. Future work may explore automated ways to design the adaptive matrix $H_t$ for specific architectures or investigate the impact of gradient sparsity on the framework's performance.
Summary updated