PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Gradient Methods with Dynamic Bound of Learning Rate

Liangchen Luo, Yuanhao Xiong, Yan Liu, Xu Sun

arXiv:1902.09843v1cs.LGstat.ML

TL;DR

Adaptive methods can train rapidly but may generalize poorly or fail to converge because of extreme learning rates. The paper introduces dynamically bounded variants of Adam and AMSGrad that transition smoothly toward SGD, and reports faster early learning with strong final generalization. The authors also provide convergence analysis and identify remaining scope for improving simple models and understanding SGD.

  • Problem

    Adaptive methods often generalize worse than SGD or fail to converge, while AMSGrad has not closed the performance gap.

  • Method

    AdaBound and AMSBound dynamically bound Adam- and AMSGrad-style learning rates to transition smoothly from adaptive optimization to SGD or momentum SGD.

  • Results

    Across computer vision and natural-language tasks, the proposed methods show faster early learning, strong generalization, and improvements over their prototypes, especially on complex deep networks.

  • Takeaways & Limitations

    Dynamic bounds retain adaptive methods’ rapid initial progress while supporting a smooth transition to SGD and its reported final-generalization properties.

  • Takeaways & Limitations

    The paper reports limited improvement on simple models and leaves alternative transition strategies, such as designed decay, for future work.

Abstract

from arXiv · show

Adaptive optimization methods such as AdaGrad, RMSprop and Adam have been proposed to achieve a rapid training process with an element-wise scaling term on learning rates. Though prevailing, they are observed to generalize poorly compared with SGD or even fail to converge due to unstable and extreme learning rates. Recent work has put forward some algorithms such as AMSGrad to tackle this issue but they failed to achieve considerable improvement over existing methods. In our paper, we demonstrate that extreme learning rates can lead to poor performance. We provide new variants of Adam and AMSGrad, called AdaBound and AMSBound respectively, which employ dynamic bounds on learning rates to achieve a gradual and smooth transition from adaptive methods to SGD and give a theoretical proof of convergence. We further conduct experiments on various popular tasks and models, which is often insufficient in previous work. Experimental results show that new variants can eliminate the generalization gap between adaptive methods and SGD and maintain higher learning speed early in training at the same time. Moreover, they can bring significant improvement over their prototypes, especially on complex deep networks. The implementation of the algorithm can be found at https://github.com/Luolc/AdaBound .

1 INTRODUCTION

Adaptive methods train quickly but can generalize worse than SGD, while AMSGrad has not closed the performance gap. The paper attributes these issues to extreme learning rates and proposes bounded variants that transition toward SGD.

  • Motivation: Adaptive methods scale gradients using averages of past squared gradients and often train faster initially than SGD.Examples include Adam, AdaGrad, and RMSprop.
  • Motivation: Adaptive methods can generalize worse than SGD, with performance often plateauing quickly on unseen data.The passage describes this pattern across development and test sets.
  • Motivation: AMSGRAD provides a convergence guarantee, but its unseen-data performance remains similar to Adam and below SGD.The cited passage reports a considerable remaining gap between AMSGrad and SGD.
  • Problem diagnosis: Adam can exhibit both extremely large and small learning rates by the end of training, motivating analysis of their effects.The paper links these rates to unstable learning behavior and possible generalization problems.
  • Proposed approach: AdaBound and AMSBound impose dynamic learning-rate bounds that smoothly transform adaptive methods into SGD or momentum SGD.The bounds begin at zero and infinity and converge to a constant final step size.
  • Evaluation: Experiments across computer vision and natural-language tasks report faster early learning, strong final generalization, and improvements over the prototype methods.The improvements are especially pronounced on complex deep networks.

2 NOTATIONS AND PRELIMINARIES

This section defines notation and an online-convex-optimization framework that represents adaptive and non-adaptive methods through gradient-moment functions and scaling terms. It also distinguishes theoretical decreasing step sizes from constant step sizes used empirically.

  • Notation: Vectors use coordinate, element-wise power, norm, inner-product, product, division, maximum, and minimum notation.The notation also defines coordinate indexing for iterates.
  • Notation: The framework uses positive-definite matrices for division and projection, with bounded feasible-set diameter assumed.The projection minimizes a matrix-weighted distance.
  • Online convex programming: Online convex programming models repeated play where the algorithm selects x_t, receives a convex loss f_t, and incurs f_t(x_t).The feasible set is convex.
  • Online convex programming: Regret compares cumulative algorithmic loss with the best fixed decision, and the goal is sublinear regret RT = o(T).Vanishing average regret implies convergence to optimal performance in the stated framework.
  • Generic optimization framework: Algorithm 1 abstracts optimization methods through φ_t for momentum-like quantities and ψ_t for gradient-scaling quantities.Its update computes a gradient, forms m_t and V_t, steps using α_t m_t/√V_t, and projects onto F.
  • Step-size schemes: Theoretical analysis uses decreasing step sizes, while empirical studies use a constant step size because aggressive decay can hurt performance.The paper states that α_t = α is typically effective in practice.
  • Method comparison: SGD uses identity scaling, whereas adaptive methods average squared past gradients; Adam and RMSprop use exponential moving averages.RMSprop is described as a special case of Adam with β1 = 0.

3 THE NON-CONVERGENCE CAUSED BY EXTREME LEARNING RATE

The paper argues that both excessively large and small adaptive learning rates can impair convergence and generalization. Experiments and convex counterexamples show that Adam may fail even with larger initial step sizes or standard parameter conditions.

  • Problem diagnosis: Adaptive methods can perform worse than SGD, and AMSGrad has not shown evident improvement over Adam in reported prior work.The paper therefore examines both large and small learning rates as possible causes.
  • Empirical observation: A ResNet-34 experiment on CIFAR-10 samples learning rates from nine convolutional kernels and one bias near convergence.The sampled rates are visualized with a heatmap.
  • Theoretical analysis: The analysis shows that extremely small learning rates can cause undesirable convergence in Adam and RMSprop.The result also covers cases where increasing Adam’s initial step size does not prevent failure.
  • Theoretical analysis: In a convex construction, a later gradient of 2 cannot counteract an earlier gradient of −1 because its learning rate is scaled much lower.The resulting Adam trajectory moves toward increasingly larger x values.
  • Interpretation: The proposed failure can arise late in training, when near-zero gradients and exponential averaging prevent infrequent corrective gradients from redirecting the algorithm.The paper contrasts this behavior with vanilla SGD, which has a range of initial step sizes yielding convergence.
  • Theoretical analysis: For any initial step size α, Adam can have non-zero average regret asymptotically on an online convex optimization problem.The theorem states RT/T does not converge to zero as T approaches infinity.
  • Theoretical analysis: A stochastic convex problem exists where Adam does not converge to the optimal solution under β1 < √β2.The paper notes this condition is typically satisfied in practice and is also used in prior convergence analysis.
  • Interpretation: The results support the claim that algorithms may need to address both huge and tiny learning rates to achieve good generalization.This conclusion follows the paper’s stated interpretation of the analysis.

4 ADAPTIVE MOMENT ESTIMATION WITH DYNAMIC BOUND

The paper develops adaptive optimizers with time-varying learning-rate bounds, preserving adaptive behavior early and smoothly approaching SGD at later steps. AdaBound and AMSBound receive regret-based convergence guarantees under stated boundedness and momentum conditions.

  • AdaBound: AdaBound clips Adam’s element-wise learning rates within time-dependent lower and upper bounds.The clipping constrains each output learning rate to [ηl, ηu].
  • Dynamic transition: The lower bound increases from 0 toward α* while the upper bound decreases from infinity toward α*, producing a smooth transition from Adam to SGD(M).At the beginning, the bounds have little effect; as they tighten, the method behaves increasingly like SGD with momentum.
  • Convergence analysis: AdaBound’s convergence analysis assumes bounded feasible-set diameter and gradients, monotone bounds, asymptotic convergence to α*, and β1/√β2 < 1.Under these conditions, the algorithm has a stated regret bound.
  • Convergence analysis: With β1t = β1/t, the analysis still ensures regret O(T).
  • AMSBound: AMSBound incorporates the same dynamic-bound idea into AMSGrad and also achieves regret O(T).Its convergence proof is described as almost the same as AdaBound’s, and similar performance is reported for the two methods across several tasks.
  • Comparison with prior work: The proposed continuous transformation avoids a fixed Adam-to-SGD switching point and removes the extra switching-time hyperparameter used by prior work.The method instead introduces two bound functions; the paper reports that their convergence target and speed are not very important to final results.

5 EXPERIMENTS

Experiments across image classification and language modeling compare AdaBound and AMSBound with established adaptive and non-adaptive optimizers. The proposed methods retain rapid or smooth optimization behavior while improving test performance, especially on deeper architectures.

  • Experimental setup: Experiments cover MNIST, CIFAR-10, and Penn Treebank using perceptron, convolutional, and recurrent models.The evaluation includes a feedforward network, DenseNet-121, ResNet-34, and LSTMs with one to three layers.
  • Feedforward neural network: On MNIST, all methods approach 100% training accuracy, while AdaBound and AMSBound slightly improve test accuracy over Adam and AMSGrad.SGD performs slightly better than the original adaptive methods, but the proposed variants visibly improve over their prototypes.
  • Convolutional neural networks: AdaBound and AMSBound converge as fast as adaptive methods and finish slightly above SGDM on DenseNet-121, with approximately 2% higher test accuracy than their prototypes.On ResNet-34, they surpass SGDM by 1% and obtain almost the best test accuracy on both deep CNNs.
  • Recurrent neural network: Across LSTM models, Adam makes the fastest initial progress but stagnates below SGD and the proposed methods, whose perplexity curves are smoother than SGD’s.The experiments use one-, two-, and three-layer LSTMs on Penn Treebank and evaluate perplexity on the test set.
  • Analysis: The improvement over Adam increases with LSTM complexity, from 1.1% for one layer to over 2.8% for three layers in perplexity.The authors interpret this pattern as evidence relating model complexity to improvement degree.

6 FUTURE WORK

The paper identifies several unresolved directions, including improving gains on simple models, explaining SGD’s broad effectiveness, and exploring alternatives to dynamic learning-rate bounds.

  • Future work: Improvements on simple models are not very inspiring and require further investigation.The authors specifically leave open how to achieve higher improvement on such models.
  • Future work: Why SGD performs well across diverse machine-learning applications remains uncertain.The paper discusses weak generalization in adaptive methods but does not resolve SGD’s broad effectiveness.
  • Future work: Dynamic bounds are only one route for gradually transforming adaptive methods into SGD, leaving designed decay schemes and other approaches unexplored.The authors identify alternative transition mechanisms as an open direction.

7 CONCLUSION

The paper attributes poor convergence to extreme learning rates, introduces dynamically bounded variants of Adam and AMSGrad, and reports smooth transitions toward SGD with strong benchmark performance.

  • Conclusion: Extremely large or small learning rates can cause poor convergence, and the paper provides a rigorous proof of Adam’s non-convergence.This analysis motivates constraining adaptive learning rates.
  • Conclusion: AdaBound and AMSBound constrain Adam and AMSGrad with dynamic learning-rate bounds that smoothly transition their behavior to SGD.The bounds avoid violent oscillation while preserving rapid initial progress and hyperparameter insensitivity.
  • Conclusion: The proposed methods show strong efficacy on several standard benchmarks while maintaining adaptive methods’ rapid initial progress.The conclusion presents the transition and benchmark performance as the main practical outcomes.

B PROOF OF THEOREM 1

The proof constructs a one-dimensional linear-function sequence showing that ADAM remains nonnegative for every iteration, despite any initial step size. Consequently, its regret grows linearly and average regret does not vanish.

  • Setup: The construction uses linear functions on F = [−2, 2], with zero initialization for the first- and second-moment estimates.The gradients are defined piecewise over time, with a constant C chosen according to β2.
  • Inductive argument: For any initial step size α, induction proves that x_t ≥ 0 for every t.The proof considers separately whether the iterate after the first update exceeds 1 or remains at most 1, then propagates nonnegativity across the following C updates.
  • Inductive argument: When the iterate exceeds 1, projection keeps it within F and subsequent zero gradients preserve its nonnegative value.In one dimension, the projection is the ordinary Euclidean projection, yielding x_{Ct+2} = min(ˆx_{Ct+2}, 2) > 1.
  • Conclusion: Every C steps, ADAM incurs regret 100C, so its total regret satisfies R_T ≥ 100T.Thus R_T/T does not converge to zero as T approaches infinity.

C PROOF OF THEOREM 2

Theorem 2 extends the nonconvergence construction to a broader optimization setting. Under the stated parameter conditions, ADAM's average regret still fails to vanish.

  • Generalization: The theorem generalizes the optimization setting used in Theorem 1 and includes the example of Reddi et al. (2018).The cited example already satisfies the constraints imposed by Theorem 2.
  • Setting: For linear functions over F = [−1, 1], the construction uses a sufficiently large constant C depending on β1 and β2.The parameter condition γ = β1/√β2 < 1 is also assumed.
  • Conclusion: The resulting sequence has R_T/T ↛ 0 as T →∞, so ADAM does not achieve vanishing average regret in this setting.This conclusion follows from the proof pattern of Reddi et al. (2018).

D PROOF OF THEOREM 3

Theorem 3 analyzes a one-dimensional stochastic optimization construction over [−1, 1]. It shows that ADAM's expected update can drift away from the optimal point.

  • Setting: The stochastic setting uses linear functions over [−1, 1], with C chosen as a large constant depending on β1, β2, and δ.δ is an arbitrary small positive constant.
  • Optimization objective: The expected objective is F(x) = δx, whose optimum over the domain is x* = −1.The proof evaluates ADAM's step under this expected objective.
  • Conclusion: For sufficiently large C, E[∆t] ≥ 0, implying that ADAM's steps keep drifting away from x* = −1.The conclusion holds without restricting the initial step size α.

E PROOF OF THEOREM 4

The proof derives a regret bound for AdaBound under bounded gradients and feasible-region diameter, using the algorithm's clipped adaptive learning rates and telescoping inequalities. AMSBound has the same upper bound.

  • Proof strategy: The proof bounds one-step regret through convexity, norm inequalities, and a lemma controlling the momentum terms.The derivation then simplifies the resulting expression using a telescopic sum.
  • AdaBound bound: AdaBound's regret is upper bounded by O(...), as obtained after applying the telescoping argument to the intermediate inequality.The supplied passage displays the asymptotic form but does not include its complete expression.
  • Algorithm: Algorithm 3 maintains first- and second-moment estimates, applies AMSGrad's maximum operation, and clips α/√V_t between η_l(t) and η_u(t).The resulting learning-rate bounds are dynamic rather than fixed.
  • Assumptions: Theorem 5 assumes β1/√β2 < 1, positive non-decreasing lower bounds, non-increasing upper bounds, and convergence of both bounds to α*.It also assumes bounded feasible-region diameter D∞ and gradient norm G2.
  • AMSBound: The regret of AMSBound has the same upper bound as that of AdaBound.This extends the theorem's regret guarantee to the AMSBound variant.

G EMPIRICAL STUDY ON BOUND FUNCTIONS

The study examines how bound-function convergence speed and target affect AdaBound, finding limited sensitivity to the bound form but strong sensitivity differences between AdaBound and SGDM. Learning rates rise early, then transition toward the final SGD step size.

  • Bound-function factors: Bound functions are evaluated by convergence speed and convergence target, with larger β producing lower convergence speed toward α∗.The convergence target reflects the final SGD(M) step size, while convergence speed controls the transition from adaptive optimization to SGD(M).
  • Convergence speed: Across tested β values, AdaBound achieves almost identical final performance for a fixed α∗ on CIFAR-10 with ResNet-34.The study tests β ∈ {1 − 1/10, 1 − 1/50, 1 − 1/100, 1 − 1/500, 1 − 1/1000} and α∗ ∈ {1, 0.1}.
  • Convergence target: SGDM is highly sensitive to its step size, with α = 0.1 performing best and other settings showing large performance gaps.The comparison uses α or α∗ ∈ {1, 0.1, 0.03, 0.01, 0.003, 0.001} and β = 0.99.
  • Convergence target: AdaBound maintains stable performance across different final step sizes, indicating low sensitivity to its convergence target.This contrasts with the strong step-size sensitivity observed for SGDM under the same ResNet-34 and CIFAR-10 setting.
  • Comparison with SGDM: AdaBound outperforms SGDM at every tested step size and is likely to beat SGDM without careful hyperparameter tuning.The bound-function form has only a minor effect on AdaBound’s performance.
  • Learning-rate evolution: AdaBound learning rates increase rapidly early in training, then decrease gradually and converge to the final step size, reflecting a transition from Adam to SGD.The early increase is attributed to Adam’s exponential moving average, while the later decrease indicates the adaptive-to-SGD transition.
Loading 1902.09843v1…