Adam+: A Stochastic Method with Adaptive Variance Reduction

Mingrui Liu, Wei Zhang, Francesco Orabona, Tianbao Yang

TL;DR

This paper introduces Adam$^+$, a novel optimization algorithm for deep learning that addresses theoretical convergence issues with the popular Adam optimizer. Adam$^+$ achieves provable convergence guarantees while maintaining Adam's ease of use and demonstrating superior or comparable performance to state-of-the-art methods across various deep learning tasks.

What Problem Does This Paper Address?

The Adam optimizer is a go-to choice for deep learning practitioners due to its effectiveness and minimal hyperparameter tuning. However, Adam suffers from a critical theoretical flaw: it's not guaranteed to converge for all objective functions. While researchers have developed variants of Adam with theoretical convergence guarantees, these often fall short in practical performance compared to the original Adam. This creates a dilemma: choose a theoretically sound but less performant optimizer, or a practically excellent but theoretically shaky one. This paper aims to bridge this gap by proposing an optimizer that offers both theoretical robustness and practical effectiveness.

Methods

The core innovation of Adam$^+$ lies in its modifications to Adam's update mechanism. Instead of using the moving average of the second moment estimate (as in Adam), Adam$^+$ computes the moving average of the first moment estimate at "extrapolated" points. Furthermore, its adaptive step size is derived from the norm of the first moment estimate, rather than the square root of the second moment estimate. These changes are designed to achieve "adaptive variance reduction," meaning the noise in the gradient estimates decreases as the algorithm progresses, leading to more stable and faster convergence. The authors also introduce a generalized version of Adam$^+$ with flexible step sizes, which achieves state-of-the-art convergence rates.

Datasets

The paper evaluates Adam$^+$ on three distinct deep learning tasks using the following datasets:

  • Image Classification: CIFAR-10 and CIFAR-100.
  • Language Modeling: Wiki-Text-2.
  • Automatic Speech Recognition: SWB-300.

Key Insights and Ideas

  • Bridging Theory and Practice: The most significant insight is the successful creation of an optimizer that is both theoretically sound (guaranteed convergence) and practically superior to its predecessor (Adam) in many scenarios. This addresses a long-standing tension in optimization research.
  • Adaptive Variance Reduction: The paper highlights a novel mechanism for achieving adaptive convergence through variance reduction of the first moment estimate. This is achieved by carefully computing the moving average at extrapolated points, which effectively smooths out noise without requiring large mini-batches or complex variance reduction techniques.
  • Data-Dependent Complexity: Adam$^+$ exhibits a "data-dependent adaptive convergence" property. This means its convergence rate is influenced by the characteristics of the data and the gradients encountered, rather than relying on assumptions like gradient sparsity, making it more broadly applicable.
  • Generalization Benefits: By avoiding coordinate-wise learning rates (unlike Adam), Adam$^+$ is expected to offer better generalization performance, a crucial aspect for real-world deep learning applications.

Key Results

  • Outperforms Adam: Across image classification, language modeling, and automatic speech recognition tasks, Adam$^+$ consistently outperformed the standard Adam optimizer in terms of both training and testing accuracy/perplexity.
  • Competitive with Best-Tuned SGD: Adam$^+$ achieved performance comparable to well-tuned SGD and momentum SGD, which are often considered the gold standard for generalization.
  • Theoretical Guarantees: The paper provides theoretical analysis demonstrating Adam$^+$'s provable convergence guarantees, including adaptive convergence and fast convergence rates for its generalized variant.
  • Empirical Verification: Extensive experiments on diverse tasks validated the theoretical findings, showing Adam$^+$'s effectiveness in practice. For instance, on VGG19 training for CIFAR100, Adam$^+$ converged much faster in the early stages than other methods.

Limitations and Future Work

  • Hyperparameter Tuning: While Adam$^+$ requires fewer parameters than some other adaptive methods, it still has parameters like $\alpha$ and $\beta$ that need to be tuned. The paper provides default settings, but optimal performance might still require some tuning.
  • Generalization of Variance Reduction: The paper focuses on variance reduction of the first moment estimate. Future work could explore extending this to other moment estimates or different types of variance reduction techniques.
  • Further Theoretical Exploration: While the paper establishes convergence for non-convex settings, further theoretical analysis could explore its behavior on specific classes of complex objective functions or its performance under different assumptions.
  • Broader Applications: While tested on common deep learning tasks, exploring Adam$^+$'s efficacy on other machine learning domains (e.g., reinforcement learning, recommendation systems) would be valuable.

Summary updated

Abstract

Adam is a widely used stochastic optimization method for deep learning applications. While practitioners prefer Adam because it requires less parameter tuning, its use is problematic from a theoretical point of view since it may not converge. Variants of Adam have been proposed with provable convergence guarantee, but they tend not be competitive with Adam on the practical performance. In this paper, we propose a new method named Adam$^+$ (pronounced as Adam-plus). Adam$^+$ retains some of the key components of Adam but it also has several noticeable differences: (i) it does not maintain the moving average of second moment estimate but instead computes the moving average of first moment estimate at extrapolated points; (ii) its adaptive step size is formed not by dividing the square root of second moment estimate but instead by dividing the root of the norm of first moment estimate. As a result, Adam$^+$ requires few parameter tuning, as Adam, but it enjoys a provable convergence guarantee. Our analysis further shows that Adam$^+$ enjoys adaptive variance reduction, i.e., the variance of the stochastic gradient estimator reduces as the algorithm converges, hence enjoying an adaptive convergence. We also propose a more general variant of Adam$^+$ with different adaptive step sizes and establish their fast convergence rate. Our empirical studies on various deep learning tasks, including image classification, language modeling, and automatic speech recognition, demonstrate that Adam$^+$ significantly outperforms Adam and achieves comparable performance with best-tuned SGD and momentum SGD.
BibTeX
@misc{liu2020adam,
  author = {Mingrui Liu and Wei Zhang and Francesco Orabona and Tianbao Yang},
  title = {{Adam+: A Stochastic Method with Adaptive Variance Reduction}},
  year = {2020},
  eprint = {2011.11985},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.11985},
}
Figure