PaperlayerView exact revision on arXiv

Source-linked AI summary

A Sufficient Condition for Convergences of Adam and RMSProp

Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, Wei Liu

arXiv:1811.09358v3cs.LGcs.CVmath.NAmath.OCstat.ML

TL;DR

Adam and RMSProp can diverge even in convex settings, while existing convergence remedies impose modifications or restrictive requirements. The paper introduces an easy-to-check sufficient condition based on the base learning rate and historical second-order moments, reformulates Adam as weighted AdaGrad with exponential moving average momentum, and reports convergence implications and experimental agreement with the theory.

  • Problem

    Adam and RMSProp are practically influential but have been shown to diverge even for convex optimization, motivating more accessible convergence guarantees.

  • Method

    The paper proposes a sufficient condition based on the base learning rate and historical second-order-moment parameters, and reformulates Adam as weighted AdaGrad with exponential moving average momentum.

  • Results

    The condition directly implies non-convex stochastic convergence for variants including AdamNC, AdaEMA, and RMSProp, while experiments on a counterexample and deep networks match the theoretical results.

  • Takeaways & Limitations

    The condition provides an alternative way to assess convergence and interpret divergence in Adam and RMSProp through learning-rate and historical-moment parameter settings.

  • Takeaways & Limitations

    Vanilla SGD can converge under its sufficient learning-rate condition yet still stagnate empirically because effective learning-rate tuning is difficult.

Abstract

from arXiv · show

Adam and RMSProp are two of the most influential adaptive stochastic algorithms for training deep neural networks, which have been pointed out to be divergent even in the convex setting via a few simple counterexamples. Many attempts, such as decreasing an adaptive learning rate, adopting a big batch size, incorporating a temporal decorrelation technique, seeking an analogous surrogate, etc., have been tried to promote Adam/RMSProp-type algorithms to converge. In contrast with existing approaches, we introduce an alternative easy-to-check sufficient condition, which merely depends on the parameters of the base learning rate and combinations of historical second-order moments, to guarantee the global convergence of generic Adam/RMSProp for solving large-scale non-convex stochastic optimization. Moreover, we show that the convergences of several variants of Adam, such as AdamNC, AdaEMA, etc., can be directly implied via the proposed sufficient condition in the non-convex setting. In addition, we illustrate that Adam is essentially a specifically weighted AdaGrad with exponential moving average momentum, which provides a novel perspective for understanding Adam and RMSProp. This observation coupled with this sufficient condition gives much deeper interpretations on their divergences. At last, we validate the sufficient condition by applying Adam and RMSProp to tackle a certain counterexample and train deep neural networks. Numerical results are exactly in accord with our theoretical analysis.

1. Introduction

The paper studies why adaptive stochastic methods such as Adam and RMSProp can diverge despite their practical success, and proposes an easier convergence condition for non-convex stochastic optimization. It also reformulates Adam and validates the analysis theoretically and experimentally.

  • Motivation: Adam and related adaptive methods use historical second-order moments to tune coordinate-wise learning rates, but Adam and Nadam can diverge even on convex problems.This motivates convergence conditions beyond direct, unmodified use of these algorithms.
  • Existing approaches: Prior remedies modify learning rates, require very large batches, decorrelate temporal moments, or replace Adam and RMSProp with surrogate algorithms.The paper characterizes these as four categories of modifications or restrictions.
  • Proposed condition: The proposed sufficient condition depends on the base learning rate and historical second-order-moment parameters, avoiding positive-definiteness checks and impractical batch-size requirements.It is presented as easier to verify and more practical than several existing conditions.
  • Main results: The condition directly implies convergence for variants including AdamNC, AdaEMA, and RMSProp in the non-convex stochastic setting.These variants can be covered without checking the positive definiteness of Γt step by step.
  • Reformulation: Adam is reformulated as weighted AdaGrad with exponential moving average momentum, offering a new perspective on Adam and RMSProp.The reformulation introduces a new momentum mechanism and base-learning-rate interpretation.
  • Interpretation and validation: The paper links divergence to potentially incorrect settings of the base learning rate and combinations of historical second-order moments, then validates the condition on a counterexample and deep networks.Experiments include LeNet and ResNet, and their results match the theoretical analysis.

2. Generic Adam

Generic Adam unifies adaptive SGD methods through momentum and exponential second-moment averaging, while exposing both their equivalence to Weighted AdaEMA and the divergence problem of Adam and RMSProp.

  • Generic Adam: Generic Adam uses base learning rates, momentum parameters, and second-moment parameters to update each coordinate using historical stochastic gradients.Its notation defines αt as the base learning rate, βt as the momentum parameter, and coordinate-wise operations with ε stabilization.
  • Generic Adam: RMSProp is recovered by setting βt = 0, while bias-corrected Adam is represented through constant momentum parameters and a modified base learning rate.The generic scheme therefore includes both RMSProp and bias-corrected Adam as special cases.
  • Weighted AdaGrad Perspective: Generic Adam can be reformulated as Weighted AdaEMA, a weighted AdaGrad algorithm with exponential moving average momentum.The paper states that the two algorithmic formulations are equivalent.
  • Divergence Issue: Adam and RMSProp may diverge even in convex settings, with proposed explanations involving the definiteness of Γt and correlations between adaptive learning rates and squared gradients.The paper notes that these explanations do not account for all convergent Adam-type algorithms.

3. Main Results

The paper derives convergence bounds for Generic Adam under parameter restrictions and proposes an easy-to-check sufficient condition based on learning-rate and second-moment parameters. The results cover several Adam-type methods and yield non-asymptotic rates in the non-convex stochastic setting.

  • Convergence Analysis: The analysis bounds the gradient residual of Generic Adam as a function of the second-moment parameters θt and base learning rates αt.The framework assumes a lower-bounded objective, Lipschitz gradients, unbiased stochastic gradients, bounded stochastic-gradient second moments, and restrictions on βt, θt, and αt.
  • Parameter Restrictions: Restriction (R3) allows χt to be represented by a non-increasing sequence multiplied by a bounded sequence, covering common Adam-type parameterizations.For AdaGrad with EMA momentum, αt = η/√t and θt = 1 − 1/t yield constant χt; bias correction motivates allowing this broader form.
  • Convergence Rates: If limt→∞θt = θ < 1, the bound is only O(1), so convergence is not guaranteed; the analysis indicates that convergence requires limt→∞θt = 1.This follows the paper’s discussion of constant-θ Adam and the resulting convergence-bound behavior.
  • Sufficient Condition: The sufficient condition (SC) guarantees Generic Adam convergence using conditions on αt, βt, and θt, without requiring Γt ≻ 0 or batch sizes comparable to the iteration count.The paper presents SC as easier to verify than existing restrictions and applicable in non-convex stochastic settings.
  • Convergence Rates: For parameters satisfying 0 < r ≤ 2s < 2, Generic Adam converges with the non-asymptotic rate stated in Corollary 10.The parameterized family recovers and extends results for AdaGrad with EMA momentum and RMSProp.
  • Covered Variants: The sufficient condition directly covers convergent variants including AdamNC, AdaEMA, AdaGrad with momentum, and extensions of RMSProp restrictions.AdamNC’s O(log(T)/T) rate is derived through Corollary 10.
  • Weighted AdaEMA: Weighted AdaEMA with polynomial-growth weights wt = t^r achieves an O(log(T)/T) non-asymptotic convergence rate.This complements earlier weighted AdaGrad results by extending the rate to exponential moving average momentum.

4. Constant θt case: insights for divergence

The analysis explains why constant θ_t can leave Adam without a convergence guarantee and relates convergence behavior to parameter choices and weighted-AdaGrad structure.

  • Constant θ_t: Constant θ_t = θ < 1 yields an O(1) bound, so convergence is not guaranteed for Adam.The paper connects this bound to the known divergence issue in convex settings.
  • Parameter dependence: With α_t = η/t^s and constant θ_t, the bound decreases as s decreases, with the best bound at s = 0.The paper states that a constant base learning rate can produce a better bound than a decaying one in this case.
  • Parameter dependence: The principal bound term is linear in 1 − θ, so it decreases toward zero as θ approaches 1.This provides the paper’s explanation for why values of θ close to 1 often perform better in practice.
  • Continuous parameter family: For the family θ_t^(r), r = 1 gives AdaEMA with O(log T/√T), while 0 < r < 1 gives O(T^−r/2) and r = 0 gives only O(1).The theoretical rate deteriorates continuously as r decreases from 1 to 0.
  • Weighted AdaEMA: The weighted-AdaGrad reformulation assigns exponentially growing weights when θ_t is constant, whereas polynomially growing weights yield convergence at O(log T/√T).The paper interprets the exponential-moving-average weighting as potentially assigning too aggressive a weight to the current gradient.

5. Experiments

Experiments test the sufficient-condition parameterization on a synthetic counterexample and in neural-network training, with outcomes matching the predicted dependence on r and θ_t.

  • Synthetic Counterexample: Generic Adam converges for r = 1.0, 0.75, and 0.5, while r = 0 and 0.25 show no visible convergence within 10^7 iterations.The paper attributes the r = 0.25 behavior to its very slow O(T^−r/2) rate rather than a contradiction of the theory.
  • Synthetic Counterexample: With the numerator fixed while changing r, Generic Adam with r = 0.25 is observed to converge.This complementary experiment supports the explanation that the earlier apparent divergence resulted from slow convergence.
  • Synthetic Counterexample: For fixed s, smaller r produces faster and better convergence on the counterexample, consistent with Corollary 10.The experiment evaluates r = 0.8 with s ∈ {0.4, 0.6, 0.8}.
  • Deep Neural Networks: Figures 2 and 3 compare Generic Adam across five r values with RMSProp and AMSGrad using training loss, test accuracy, and test loss.The comparisons cover LeNet on MNIST and ResNet-18 on CIFAR-100.
  • Deep Neural Networks: AMSGrad and Generic Adam with r = 0 decrease training loss slowest and have the worst test accuracy among the compared optimizers.Generic Adam’s convergence is highly sensitive to θ_t, and larger r produces faster convergence.

6. Conclusions

The paper presents a sufficient condition for Adam and RMSProp convergence, reframes Adam as weighted AdaGrad with exponential moving-average momentum, and validates the analysis experimentally.

  • 6. Conclusions: The proposed sufficient condition guarantees convergence in non-convex stochastic settings using the base learning rate α_t and second-order-moment combination parameter θ_t.The paper attributes possible divergence to inappropriate settings of these parameters.
  • 6. Conclusions: Adam is reformulated as weighted AdaGrad with exponential moving-average momentum, offering a perspective on Adam and RMSProp divergences.The theoretical conclusions are verified on a counterexample and real-world neural-network datasets.

Supplementary Material for “ A Sufficient Condition for Convergences of Adam and RMSProp ”

The supplementary material supplies notation, lemmas, and detailed proofs for the paper’s theoretical results, alongside descriptions of experimental architectures and datasets.

  • Notation: The supplement introduces vector notation, coordinate-wise operations, inner products, and weighted norms used in the analysis.It defines vector comparisons and the ℓ1 and ℓ2 norms before presenting the proofs.
  • Proofs: The proof material develops lemmas involving weighted sequences, momentum recursions, non-decreasing θ_t, learning-rate restrictions, and summation by parts.These lemmas support estimates used in the main theoretical results.
  • Supplementary contents: The supplement provides complete proofs of the main propositions, theorems, and corollaries.It also contains experimental architecture and dataset-statistics descriptions for LeNet, ResNet-18, MNIST, and CIFAR-100.

B.1. Proof of Proposition 3

The appendix establishes equivalence between two algorithms and derives expectation and high-probability convergence estimates for Generic Adam under assumptions (A1)–(A4).

  • Proposition 3: Algorithm 1 and Algorithm 2 are equivalent under corresponding parameter transformations.The proof maps θt to wt and wt to θt, converting Eq. (77) and Eq. (76) into each other.
  • Theorem: Generic Adam satisfies an expectation-based estimate for a uniformly random iterate τ under assumptions (A1)–(A4).The theorem uses initial values x1, m0 = 0, and v0 = ϵ, with τ sampled uniformly from {1, 2, . . . , T}.
  • Proof: The expectation estimate follows by summing one-step descent inequalities and applying bounds from Lemmas 24, 25, and 27.The proof uses Lipschitz continuity of the gradient, the descent lemma, a lower bound f(x) ≥ f*, and rearrangement of the resulting terms.
  • Theorem: A high-probability convergence bound is obtained for the same uniformly sampled iterate τ.For any δ > 0, the bound holds with probability at least 1 − δ^2/3, using Theorem 4 and Chebyshev’s inequality.

B.4. Proof of Corollary 7

For base learning rates αt = η/t^s with 0 ≤ s < 1, the appendix characterizes Bound(T) when θt approaches or equals a constant θ < 1.

  • Corollary 7: When αt = η/t^s with 0 ≤ s < 1 and limt→∞θt = θ < 1, Bound(T) is bounded below by constants.The result applies to the parameter family specified in the corollary.
  • Corollary 7: For constant θt = θ < 1, the appendix gives more detailed lower and upper bounds for Bound(T).The proof uses 1 − θt ≥ 1 − θ and applies Theorem 5 for the limiting and constant-parameter cases.

B.5. Proof of Corollary 10

For the stated parameter family, Generic Adam converges when 0 < r ≤ 2s < 2, with a rate determined by r/2 + s.

  • Corollary 10: Generic Adam converges for 0 < r ≤ 2s < 2 under the specified family of parameters.This condition is stated as sufficient for convergence.
  • Corollary 10: The non-asymptotic rate is O(T^(1−(r/2+s))) when r/2 + s < 1.The rate is part of the piecewise estimate used in the corollary.
  • Corollary 10: The non-asymptotic rate is O(log(T)) when r/2 + s = 1.This is the boundary case of the stated piecewise rate.

B.6. Proof of Corollary 12

Weighted AdaEMA with polynomial weights and αt = η/t achieves an O(log(T)/T) non-asymptotic convergence rate, supported by the Generic Adam conditions and neural-network settings described for experiments.

  • Corollary 12: Weighted AdaEMA with weights wt = t^r for r ≥ 0 and αt = η/t has an O(log(T)/T) non-asymptotic convergence rate.The proof represents the method as Generic Adam using θt = Wt−1/Wt and verifies the relevant restrictions.
  • Proof: The equivalent Generic Adam parameters satisfy limt→∞θt = 1 > β, with θt increasing and χt bounded.These properties are used to apply Theorem 5.
  • Experimental setup: The experiments describe MNIST and CIFAR-100 datasets together with LeNet and ResNet-18 training configurations.MNIST has 60,000 training and 10,000 validation examples; CIFAR-100 has 50,000 training and 10,000 validation examples.

C.3. Additional Experiments of ResNet-18 on CIFAR-100

The experiment evaluates Generic Adam variants, RMSProp, and AMSGrad on ResNet-18 trained on CIFAR-100. Using a non-increasing learning rate with an initial cutoff, the profiles align with the theoretical prediction that larger r trains faster.

  • Additional Experiments of ResNet-18 on CIFAR-100: The experiment trains ResNet-18 on CIFAR-100 using Generic Adam with r values from 0 to 1, RMSProp, and AMSGrad.The base learning rate is α = 0.01, with αt = 0.001 for t < 2500.
  • Additional Experiments of ResNet-18 on CIFAR-100: The learning-rate schedule remains non-increasing after applying the initial cutoff.The cutoff sets αt = 0.001 during the first 2500 iterations.
  • Additional Experiments of ResNet-18 on CIFAR-100: Performance profiles agree with the theoretical analysis: larger r leads to a faster training process.The comparison includes Generic Adam, RMSProp, and AMSGrad.
  • Additional Experiments of ResNet-18 on CIFAR-100: Figure 4 reports training loss, test accuracy, and test loss as functions of epochs.Panels (a), (b), and (c) show these three metrics, respectively.
Loading 1811.09358v3…