PaperlayerView exact revision on arXiv

Source-linked AI summary

ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION

arXiv:1412.6980v9

TL;DR

Stochastic objective functions require efficient gradient-based optimization, particularly for large-scale and high-dimensional machine-learning problems. Adam addresses this with adaptive first- and second-moment-based learning rates, and experiments find it robust and well-suited across a wide range of non-convex optimization problems.

  • Problem

    Stochastic objective functions create a need for efficient gradient-based optimization in large-scale and high-dimensional settings.

  • Method

    Adam uses first-order gradients and adaptive per-parameter learning rates computed from estimates of gradient first and second moments.

  • Results

    Experiments find Adam consistently outperforms other methods across varied models and datasets and is robust across a wide range of non-convex optimization problems.

  • Takeaways & Limitations

    Adam is a straightforward, memory-efficient optimizer suited to machine-learning problems with large datasets or high-dimensional parameter spaces.

  • Takeaways & Limitations

    Sparse gradients may require a small β2 for reliable second-moment estimates, making initialization-bias correction important to avoid excessively large initial steps.

Abstract

from arXiv · show

1 INTRODUCTION

The introduction presents Adam as an efficient stochastic optimization method requiring only first-order gradients and little memory. It uses adaptive learning rates from gradient moments, combines advantages associated with AdaGrad and RMSProp, and is reported to perform consistently across models and datasets.

  • Motivation: Stochastic gradient-based optimization addresses differentiable scalar objectives in science and engineering, where gradient descent provides a relatively efficient approach.The introduction frames these problems as maximizing or minimizing parameterized objective functions.
  • Contribution: Adam requires only first-order gradients and little memory while computing parameter-specific adaptive learning rates from first- and second-moment estimates.Its name derives from adaptive moment estimation.
  • Contribution: Adam is designed to combine AdaGrad’s effectiveness with sparse gradients and RMSProp’s adaptive learning-rate behavior.The introduction identifies AdaGrad and RMSProp as the motivating methods.
  • Scope and claims: Adam is presented as versatile for large-scale, high-dimensional machine learning, with reported consistent empirical improvements across models and datasets.The paper also introduces an initialization bias correction technique and analyzes Adam’s convergence in online convex programming.

2 ALGORITHM

Adam minimizes the expected value of a differentiable noisy objective by adaptively updating first- and second-moment estimates of stochastic gradients. Bias correction addresses their zero initialization, while the normalized update keeps effective steps approximately bounded by the base stepsize α.

  • 2 ALGORITHM: Adam minimizes the expected value of a differentiable stochastic objective using realizations observed over successive timesteps.Stochasticity may arise from evaluating random minibatches or other sources.
  • 2 ALGORITHM: The algorithm maintains exponential moving averages of gradients and squared gradients, controlled by β1 and β2, estimating the first and second raw moments.Because both averages start at zero, Adam corrects their initial bias toward zero.
  • 2 ALGORITHM: Adam’s normalized update usually has effective magnitude approximately bounded by α, establishing a trust region around the current parameter value.This makes the appropriate scale of α relatively easy to determine in advance for many machine-learning models.

3 INITIALIZATION BIAS CORRECTION

Adam corrects initialization bias in its exponential moving averages by deriving how the expected second-moment estimate differs from the true second moment and dividing by the resulting zero-initialization factor. This correction is especially important for sparse gradients, where small β2 is needed but otherwise causes overly large initial steps.

  • 3 INITIALIZATION BIAS CORRECTION: Adam derives the second-moment initialization-bias correction from the exponential moving average of squared stochastic gradients; the first-moment derivation is analogous.The running estimate is initialized at zero, so its early expected value does not equal the true second raw moment.
  • 3 INITIALIZATION BIAS CORRECTION: Dividing by (1 − β2^t) corrects the bias caused by initializing the second-moment running average with zeros.The correction is introduced in Adam’s algorithm after isolating the zero-initialization term.
  • 3 INITIALIZATION BIAS CORRECTION: For sparse gradients, reliable second-moment estimates require averaging over many gradients with a small β2.Without initialization-bias correction, this same small-β2 setting produces initial steps that are much larger.

4 CONVERGENCE ANALYSIS

The analysis casts Adam as an online-learning algorithm and establishes regret guarantees under bounded-gradient and bounded-iterate assumptions. It also shows that adaptive methods benefit from sparse features and that decaying the first-moment coefficient is important for convergence.

  • Adam is analyzed in the online-learning framework of Zinkevich (2003), evaluating performance through regret on an unknown sequence of convex cost functions.
  • Under bounded gradients, bounded parameter distances, and suitable β1, β2 conditions, Theorem 4.1 gives Adam a regret bound comparable to the best known general convex online-learning bound.The theorem applies with a decaying learning rate and exponentially decaying β1,t.
  • For sparse data with bounded gradients, Adam’s summation term can be substantially smaller than its generic upper bound, as in the feature setting of Duchi et al. (2011).Their expected-norm results also apply to Adam.
  • Adaptive methods such as Adam and Adagrad can achieve O(log d) dependence, improving over O(√d) for non-adaptive methods.
  • Decaying β1,t toward zero is important to the theoretical analysis and agrees with empirical findings that reducing momentum late in training can improve convergence.
  • The analysis proves that Adam’s average regret converges under bounded gradients and bounded parameter distances.The result follows from Theorem 4.1.

5 RELATED WORK

Adam is related to RMSProp, AdaGrad, and other curvature-adaptive stochastic optimizers, while differing in its moment-based updates, bias correction, and memory profile. It also resembles natural gradient descent through a data-geometry-adaptive preconditioner.

  • Adam is directly related to RMSProp and AdaGrad, alongside vSGD, AdaDelta, and natural Newton methods that set stepsizes by estimating curvature from first-order information.
  • Natural gradient descent: Adam resembles natural gradient descent (NGD) because its preconditioner adapts to data geometry, with b_vt approximating the Fisher’s diagonal.
  • SFO: SFO is a minibatch quasi-Newton method, but its memory grows linearly with the number of minibatch partitions, often making it infeasible on memory-constrained GPUs.
  • RMSProp: Unlike RMSProp with momentum, Adam estimates updates from running averages of the gradient’s first and second moments and includes bias correction.RMSProp with momentum instead applies momentum to the rescaled gradient, and RMSProp lacks bias correction.
  • AdaGrad: AdaGrad corresponds to Adam with β1 = 0, infinitesimal (1 − β2), and an annealed α, but this correspondence fails without bias correction.Without bias correction, β2 approaching 1 would produce infinitely large bias and parameter updates.

6 EXPERIMENTS

Experiments across logistic regression, multilayer networks, and deep CNNs show that Adam is effective on both sparse-feature and practical deep-learning problems. Its advantages depend on the model: Adam matches or exceeds specialized optimizers, while CNN behavior reveals limitations of its second-moment estimate.

  • Experimental setup: The evaluation covers logistic regression, multilayer fully connected networks, and deep CNNs using common initialization and best settings selected by dense hyper-parameter searches.Large models and datasets were used to assess Adam on practical deep-learning problems.
  • Logistic regression: On MNIST logistic regression, Adam converges similarly to SGD with momentum, and both converge faster than Adagrad.The experiment uses minibatches of 128 and compares optimizers on a convex objective, avoiding local-minimum concerns.
  • Logistic regression: On sparse IMDB bag-of-words features, Adam converges as fast as Adagrad and faster than SGD with Nesterov momentum, with or without dropout noise.Adagrad outperforms SGD by a large margin, while Adam matches Adagrad’s convergence, consistent with Adam exploiting sparse features.
  • Multilayer neural networks: Adam shows better convergence than other stochastic first-order methods with dropout and trains faster than SFO on deterministic multilayer-network objectives.SFO failed to converge when stochastic regularization made its subfunctions nondeterministic.
  • Convolutional neural networks: Adam and SGD converge considerably faster than Adagrad on CNNs after the initial training stage, because Adam’s second-moment estimate vanishes and becomes dominated by ϵ.This contrasts with their similarly rapid initial cost reduction and indicates that the second-moment estimate poorly captures CNN cost geometry.
  • Bias correction: With VAE training, Adam performs equal to or better than RMSProp across hyper-parameter settings, while bias correction prevents early instabilities when β2 is close to 1.The best results used bias correction and small values of (1−β2), especially late in optimization as gradients became sparser.

7 EXTENSIONS

The extensions generalize Adam to AdaMax, obtained from the infinity-norm limit and offering a simpler, stable update with bounded parameter changes. They also propose averaging iterates or parameters to improve generalization in stochastic approximation.

  • AdaMax: AdaMax arises as a surprisingly simple and stable variant of Adam by taking the limit p →∞ in the Lp-norm update rule.Unlike finite large-p variants, which can be numerically unstable, AdaMax uses the infinity norm and does not require initialization-bias correction for its norm estimate.
  • AdaMax: AdaMax updates parameters using a bias-corrected first-moment estimate divided by an exponentially weighted infinity norm of the gradients.The norm estimate follows ut ← max(β2 · ut−1, |gt|), while the parameter update uses mt/ut.
  • AdaMax: AdaMax bounds the magnitude of parameter updates by |∆t| ≤α.This gives AdaMax a simpler update-magnitude bound than Adam.
  • Parameter averaging: Averaging can improve generalization because the last iterate is noisy under stochastic approximation.The paper describes Polyak-Ruppert averaging and an alternative exponential moving average that weights recent parameter values more heavily, with initialization-bias correction available for the latter.

8 CONCLUSION

Adam is presented as a simple, computationally efficient stochastic optimization algorithm for large datasets and high-dimensional parameter spaces. It combines AdaGrad’s sparse-gradient handling with RMSProp’s ability to address non-stationary objectives, while experiments support its convex convergence analysis and robustness across non-convex optimization.

  • 8 CONCLUSION: Adam is a simple, computationally efficient algorithm for gradient-based optimization of stochastic objective functions.It is aimed at machine learning problems involving large datasets and/or high-dimensional parameter spaces.
  • 8 CONCLUSION: Adam combines AdaGrad’s ability to handle sparse gradients with RMSProp’s ability to handle non-stationary objectives.The method is straightforward to implement and requires little memory.
  • 8 CONCLUSION: Experiments confirm the convergence-rate analysis for convex problems and indicate that Adam is robust and well-suited to a wide range of non-convex optimization problems.

10 APPENDIX

The appendix develops the convexity lemmas and bounded-gradient assumptions used to prove Adam’s regret guarantee. It then derives the theorem by substituting Adam’s updates into the convex regret analysis and bounding the resulting terms.

  • 10 APPENDIX: The appendix establishes convexity lemmas that lower-bound functions by tangent hyperplanes, enabling regret analysis through Adam’s update rules.The main proof substitutes the Adam updates for the tangent-hyperplane terms.
  • 10 APPENDIX: The supporting lemmas assume bounded gradients, with ∥g_t∥_2 ≤ G and ∥g_t∥_∞ ≤ G_∞, and analyze running-average terms under β_2 and decaying β_1,t.The theorem additionally assumes bounded parameter distances and β_1,t = β_1λ^(t−1), with λ ∈ (0, 1).
  • 10 APPENDIX: The proof applies the auxiliary lemma coordinate-wise, uses Young’s inequality and arithmetic-geometric-series bounds, and sums across dimensions and iterations to obtain Adam’s regret bound.The derivation first bounds each coordinate’s update contribution before aggregating the resulting upper bounds.
Loading 1412.6980v9…