PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of Adam and Beyond

Sashank J. Reddi, Satyen Kale, Sanjiv Kumar

arXiv:1904.09237v1cs.LGmath.OCstat.ML

TL;DR

Adaptive methods based on exponential moving averages can fail to converge even on simple convex problems. The paper proves this failure, identifies the role of limited gradient history, and proposes long-term-memory ADAM variants that retain practical efficiency while often improving performance.

  • Problem

    Exponential-moving-average variants of ADAGRAD can exhibit undesirable convergence behavior, raising concerns about their theoretical guarantees and practical use.

  • Method

    The paper analyzes exponential-moving-average adaptive methods, constructs convex counterexamples, examines ADAM’s convergence proof, and designs long-term-memory variants.

  • Results

    RMSPROP and ADAM can converge to highly suboptimal solutions, while the proposed long-term-memory fixes retain good practical performance and sometimes improve it.

  • Takeaways & Limitations

    Adaptive methods using an essentially fixed window of past gradients require caution, while long-term gradient memory is a supported design direction for convergence.

  • Takeaways & Limitations

    The theoretical analysis uses α_t = 1/t, although more aggressive constant step sizes can work well in practice.

Abstract

from arXiv · show

Several recently proposed stochastic optimization methods that have been successfully used in training deep networks such as RMSProp, Adam, Adadelta, Nadam are based on using gradient updates scaled by square roots of exponential moving averages of squared past gradients. In many applications, e.g. learning with large output spaces, it has been empirically observed that these algorithms fail to converge to an optimal solution (or a critical point in nonconvex settings). We show that one cause for such failures is the exponential moving average used in the algorithms. We provide an explicit example of a simple convex optimization setting where Adam does not converge to the optimal solution, and describe the precise problems with the previous analysis of Adam algorithm. Our analysis suggests that the convergence issues can be fixed by endowing such algorithms with `long-term memory' of past gradients, and propose new variants of the Adam algorithm which not only fix the convergence issues but often also lead to improved empirical performance.

1 INTRODUCTION

Adaptive gradient methods improve per-feature learning rates, but exponential moving averages can create convergence failures. The paper analyzes this issue and proposes long-term-memory variants to address it.

  • Motivation: Adaptive SGD variants scale gradient coordinates using averages of past squared gradients to adjust learning rates per feature.ADAGRAD can outperform vanilla SGD when gradients are sparse or generally small.
  • Motivation: ADAGRAD’s learning-rate decay can deteriorate performance for dense, nonconvex, and high-dimensional gradients.Its use of all past gradients causes rapid decay in these settings.
  • Motivation: RMSPROP, ADAM, ADADELTA, and NADAM use exponential moving averages to limit updates’ reliance to recent gradients.These variants were proposed to mitigate ADAGRAD’s rapid learning-rate decay.
  • Contributions: The paper proves that restricting gradient history to essentially a fixed recent window can cause significant convergence issues.The analysis specifically targets exponential moving averages and extends conceptually to other fixed-window averaging schemes.
  • Contributions: The proposed ADAM variants retain long-term memory of past gradients while preserving the original algorithm’s time and space requirements.The paper provides convex-setting convergence analysis for these variants.

2 PRELIMINARIES

The paper frames adaptive optimization through online learning, where gradient history determines the update’s momentum and coordinate scaling. It situates SGD, ADAGRAD, and exponential-moving-average methods within one generic framework.

  • Optimization setup: Online optimization selects x_t, observes loss f_t, and evaluates performance through cumulative regret over T rounds.The feasible set has bounded diameter, and gradients are assumed bounded in the infinity norm.
  • Optimization setup: Online gradient descent updates x_t opposite the minibatch gradient while projecting back onto the feasible set.The update uses x_t+1 = Π_F(x_t − α_tg_t).
  • Optimization setup: Vanishing average regret connects online optimization to stochastic empirical-risk minimization.Online algorithms with vanishing average regret yield stochastic optimization algorithms for ERM.
  • Generic adaptive methods: A generic adaptive method computes a gradient g_t, an averaged momentum m_t, and a positive-definite scaling matrix V_t from gradient history.The framework uses averaging functions φ_t and ψ_t; diagonal variants set V_t = diag(v_t).
  • Adaptive methods: SGD uses the current gradient and identity scaling, whereas ADAGRAD uses accumulated squared gradients for coordinate-wise adaptation.ADAGRAD can yield substantial convergence gains when gradients are sparse.
  • Adaptive methods: RMSPROP, ADAM, NADAM, and ADADELTA replace ADAGRAD’s simple average with exponential moving averages of squared gradients.ADAM’s recursions use β1 and β2 to update momentum and second-moment estimates, commonly with β1 = 0.9 and β2 = 0.999.
  • Adaptive methods: The theoretical presentation uses α_t = 1/t, although more aggressive constant step sizes can work well in practice.The exposition also omits ADAM’s debiasing step, while the authors state that their arguments apply to the debiased version.

3 THE NON-CONVERGENCE OF ADAM

The paper shows that exponential moving averages can make ADAM and related methods fail to converge, even on simple convex problems. The failure stems from adaptive learning-rate behavior and persists under broad parameter choices and regularization.

  • ADAM can fail to converge to an optimal solution even in a simple one-dimensional convex setting.
  • The adaptive quantity Γ_t can become indefinite for ADAM and RMSPROP, unlike SGD and ADAGRAD, whose corresponding quantities remain positive semidefinite.
  • For a periodic linear-function sequence, ADAM converges to x = +1 although x = −1 minimizes regret, because the large gradient is scaled down while smaller opposing gradients dominate.
  • Adding any constant ϵ > 0 to the denominator does not eliminate the problem: an online setting still exists where ADAM has non-zero asymptotic average regret.
  • For any constant β1, β2 ∈ [0, 1) satisfying β1 < √β2, an online convex problem exists where ADAM has non-zero average regret asymptotically.
  • Avoiding bad convergence behavior may require problem-dependent ϵ, β1, and β2, potentially one parameter set per dimension, undermining adaptive methods’ tuning simplicity.

4 A NEW EXPONENTIAL MOVING AVERAGE VARIANT: AMSGRAD

AMSGRAD modifies exponential-moving-average methods to preserve long-term information through a maximum of past second-moment estimates. This enforces non-increasing step sizes and supports convergence guarantees while retaining adaptive normalization.

  • AMSGRAD modifies ADAM by maintaining the maximum of all past v_t values for normalization instead of using the current v_t.
  • The maximum-based normalization keeps Γ_t positive semidefinite and produces a non-increasing step size, avoiding ADAM and RMSPROP’s learning-rate pitfalls.
  • When a new squared gradient exceeds the previous estimate, ADAM can increase its learning rate, whereas AMSGRAD avoids that increase by retaining the historical maximum.
  • Figure 1 compares ADAM and AMSGRAD on a synthetic one-dimensional convex problem in online and stochastic settings.
  • The AMSGRAD analysis assumes bounded feasible-set diameter and bounded gradients, with β1/√β2 < 1, and establishes a regret bound for its iterates.
  • A simple average of previous v_t values yields an ADAGRAD-like method with convergence behavior similar to ADAGRAD.

5 EXPERIMENTS

Experiments compare ADAM and AMSGRAD on synthetic convex optimization, MNIST classification, and CIFAR-10 convolutional classification, while also analyzing ADAMNC’s convergence guarantees. Across these settings, AMSGRAD avoids ADAM’s synthetic failure and generally achieves better empirical performance, while ADAMNC obtains regret bounds under suitable parameter conditions.

  • Experiments: Figure 2 compares ADAM and AMSGRAD on MNIST logistic regression, a one-hidden-layer feedforward network, and CIFARNET training and test loss across iterations.The CIFARNET experiment uses the CIFAR-10 dataset and a convolutional architecture with convolutional, pooling, normalization, and fully connected layers.
  • Synthetic Experiments: In the synthetic convex setting, ADAM’s average regret does not converge to 0 and its iterates converge to the worst point x = 1, whereas AMSGRAD reaches the optimum x = −1.The stochastic version similarly has ADAM converge to x = 1 despite the optimal solution being x = −1.
  • Logistic Regression: AMSGRAD performs better than ADAM on both training and test loss for MNIST logistic regression and is relatively more robust to parameter changes.The experiment uses minibatches of size 128 and β2 values selected from {0.99, 0.999}.
  • CIFARNET: AMSGRAD performs considerably better than ADAM on CIFARNET training loss and accuracy, with the gain also appearing in test loss.
  • ADAMNC: ADAMNC uses an increasing β2 schedule and can achieve good convergence rates without changing ADAM’s algorithmic structure.Its regret analysis assumes bounded feasible-set diameter and gradients, together with parameter conditions ensuring Γt ⪰ 0.
  • ADAMNC: When β2t = 1 − 1/t, ADAMNC effectively becomes a momentum-based variant of ADAGRAD with data-dependent regret that can outperform the O(√dT) regret of SGD.

6 DISCUSSION

The discussion identifies fixed-window exponential averaging as a source of undesirable convergence behavior and motivates long-term memory as a remedy. The proposed fixes retain the original methods’ practical performance and sometimes improve it.

  • Discussion: Algorithms using an essentially fixed-sized window of past gradients to scale updates can suffer the convergence problem identified for exponential moving-average variants.
  • Discussion: The proposed modifications give the algorithms long-term memory of past gradients while retaining their good practical performance and sometimes improving it.
  • Discussion: The paper’s primary goal is to rigorously highlight theoretical problems in popular exponential moving-average variants of ADAGRAD and identify design principles for stochastic optimization.

A PROOF OF THEOREM 1

The proof constructs a one-dimensional convex online optimization sequence on F = [−1, 1] and shows by induction that ADAM repeatedly returns to x = 1. This behavior yields persistent linear regret despite the optimum being x = −1.

  • Construction: The proof considers linear loss functions over the feasible set F = [−1, 1].
  • Construction: The point x = −1 minimizes regret, while the proof assumes x1 = 1 without loss of generality and uses β1 = 0, β2 = 1/(1 + C^2).The step size is αt = α/√t with α < √(1 − β2), and the stated ADAM parameter conditions are satisfied.
  • Inductive argument: Induction establishes that all iterates remain positive and x3t+1 = 1 for every t.The proof shows the intermediate iterates are positive and then proves x3t+4 = 1 by considering whether the unprojected iterate is at least 1.
  • Inductive argument: The proof bounds the terms T1 and T2 to establish T2 ≥ T1, which implies the unprojected iterate satisfies ˆx3t+4 ≥ 1.Projection onto F then gives x3t+4 = 1.
  • Regret consequence: ADAM incurs regret of at least 2C − 4 every three steps, so RT ≥ (2C − 4)T/3 and RT/T does not approach 0.Because C ≥ 2, the average regret remains non-vanishing as T grows.

B PROOF OF THEOREM 2

The proof analyzes ADAM on a periodic one-dimensional linear-function construction, showing that its iterates can remain at a suboptimal boundary and incur persistent regret.

  • The proof assumes β1 < √β2 and uses linear functions over F = [−1, 1].
  • For the periodic gradient sequence, the proof establishes that ADAM’s momentum at cycle boundaries remains nonpositive.
  • A cycle preserves x_t = 1 once reached, and some cycle boundary eventually reaches x_t = 1.
  • After that boundary is reached, ADAM incurs regret of at least 2 every C steps, yielding persistent nonvanishing average regret.

C PROOF OF THEOREM 3

The proof constructs a one-dimensional stochastic convex setting in which ADAM’s expected update is nonnegative, so its iterates drift away from the optimum and retain a positive expected suboptimality gap.

  • The construction uses i.i.d. linear losses on [−1, 1], with gradient C occurring with probability p and −1 otherwise.
  • The optimum is x⋆ = −1, but the expected suboptimality gap remains at least δ > 0.
  • For sufficiently large C as a function of β1, β2, and δ, the conditional expected update satisfies E[∆t] ≥ 0.
  • Because expected iterates are nondecreasing, an initialization x1 ≥ 0 keeps E[xt] ≥ 0 for all t.

D PROOF OF THEOREM 4

The proof addresses flaws in the earlier ADAM convergence analysis and derives regret bounds for the corrected analysis, including AMSGRAD’s dependence on the time horizon.

  • The earlier ADAM proof incorrectly assumed that Γt is positive semidefinite and also contains problems in Lemmas 10.3 and 10.4.
  • The proof omits projection steps for simplicity, although projections can be handled with additional work and a messier analysis.
  • The corrected proof uses intermediate bounds, convexity, Cauchy–Schwarz, Young’s inequality, and telescoping sums to control the regret terms.
  • AMSGRAD’s regret is bounded by O(G∞√T) in the analyzed setting and can be combined with the theorem’s bound through a minimum.

E PROOF OF THEOREM 5

This proof develops the regret analysis for Theorem 5 using update-rule bounds, parameter conditions, convexity, and telescoping sums to obtain the stated result.

  • The proof begins from bounds analogous to those used for Theorem 4 and introduces an intermediate lemma under Theorem 5’s parameter conditions.
  • Convexity converts the iterate-distance inequalities into per-step regret bounds.
  • It bounds the update-dependent terms using the algorithm’s update rule, Cauchy–Schwarz, and the constraint β1^k ≤ β1.
  • The proof applies the theorem’s conditions on (αt, β2t), uses the L∞ bound on the feasible region, and telescopes the resulting sum.

F PROOF OF THEOREM 6

Theorem 6 constructs a convex linear-function setting in which Adam’s modified update can retain nonzero average regret despite satisfying the stated parameter conditions. The proof uses a periodic construction and induction, then extends the result to general ϵ by rescaling.

  • For any ϵ > 0, Adam with the modified update can have nonzero average regret on convex losses under the stated parameter conditions.
  • The proof considers linear functions over F = [−1, 1], initializes x1 = 1, and selects β1, β2, and αt under specified constraints.
  • The induction aims to keep x3t+2 and x3t+3 positive while returning x3t+4 to 1 after every three updates.The argument establishes the base case and propagates these properties through the update sequence.
  • For ϵ = 1, Adam incurs regret of at least 2C − 4 every three steps, yielding RT ≥ (2C − 4)T/3.Because C ≥ 2, the resulting average regret does not converge to zero and can be very large.
  • For general ϵ, rescaling the function sequence gives RT ≥ (2C − 4)√ϵT/3, so the average regret remains nonzero asymptotically.The rescaled updates correspond to the optimization setting used in the proof.
Loading 1904.09237v1…