Source-linked AI summary
On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
Xiangyi Chen, Sijia Liu, Ruoyu Sun, Mingyi Hong
TL;DR
Adaptive gradient methods such as Adam, AMSGrad, and AdaGrad are widely used, but their convergence for non-convex optimization was theoretically unresolved. The paper establishes sufficient conditions for a generalized Adam-type class, showing O(log T/√T) convergence under those conditions while identifying divergence and worst-case-analysis boundaries.
Problem
The convergence of adaptive gradient methods including Adam, AMSGrad, and AdaGrad remained open for non-convex optimization despite their practical popularity.
Method
The paper analyzes a generalized Adam-type class using sufficient conditions on stepsizes and algorithm parameters, including adaptive effective stepsizes based on past gradients.
Results
O(log T/√T) convergence is established for the Adam-type class under the derived conditions, including constant-momentum AMSGrad and the proposed AdaFom variant.
Takeaways & Limitations
The conditions can certify or monitor convergence in practice, and their tightness shows that violating them may make an algorithm diverge.
Takeaways & Limitations
The analysis focuses on worst-case non-convex convergence rates, so sharper theory quantifying adaptive methods’ benefits remains open; the paper also focuses on unconstrained problems.
Abstract
from arXiv · showhide
This paper studies a class of adaptive gradient based momentum algorithms that update the search directions and learning rates simultaneously using past gradients. This class, which we refer to as the "Adam-type", includes the popular algorithms such as the Adam, AMSGrad and AdaGrad. Despite their popularity in training deep neural networks, the convergence of these algorithms for solving nonconvex problems remains an open question. This paper provides a set of mild sufficient conditions that guarantee the convergence for the Adam-type methods. We prove that under our derived conditions, these methods can achieve the convergence rate of order $O(\log{T}/\sqrt{T})$ for nonconvex stochastic optimization. We show the conditions are essential in the sense that violating them may make the algorithm diverge. Moreover, we propose and analyze a class of (deterministic) incremental adaptive gradient algorithms, which has the same $O(\log{T}/\sqrt{T})$ convergence rate. Our study could also be extended to a broader class of adaptive gradient methods in machine learning and optimization.
1 INTRODUCTION
Adaptive gradient methods such as Adam are widely used, but their convergence for non-convex optimization remained theoretically unresolved. The paper develops sufficient conditions for a broad Adam-type class and analyzes variants including AMSGrad, AdaGrad, and new algorithms.
- Adam combines adaptive descent directions and learning rates, making it popular for deep learning despite unresolved non-convex convergence theory.
- AMSGrad addressed convergence issues for Adam in convex optimization, but its analysis remained restrictive because it did not cover non-convex problems.
- The paper provides mild sufficient conditions under which a generalized Adam-type class converges to first-order stationary solutions at O(log T/√T).
- The analyzed class includes AMSGrad, AdaGrad, and stochastic heavy-ball methods, along with two proposed algorithms.
- Constant-momentum AMSGrad converges under the paper’s analysis, separating convergence from the use of diminishing momentum parameters.
- The conditions are presented as practically checkable and essential, since violating them can cause divergence and effective-stepsize oscillation can affect convergence.
2 PRELIMINARIES AND ADAM-TYPE ALGORITHMS
The paper formulates generalized Adam as exponentially weighted stochastic gradient descent with adaptive weighting based on past gradients. It relates this framework to established variants and motivates analysis of its stationarity convergence.
- Stochastic optimization uses mini-batch gradient evaluation, with noisy gradients modeled as unbiased estimates under smoothness and bounded-noise assumptions.
- Generalized Adam updates momentum using current gradients, constructs a weighting vector from all past gradients, and applies an adaptively scaled step.
- The vector αt/√v̂t is the effective stepsize, while mt/√v̂t uses element-wise division to form the update direction.
- AdaFom adds momentum only to the first moment and uses AdaGrad’s second-moment estimate, whereas Adam adds momentum to both estimates.
- If β2 = 1 − 1/t in Adam’s second-moment expression, the resulting method is AdaFom; Adam can instead be viewed as using exponentially decaying weights on squared gradients.
- The framework applies to finite-sum objectives and mini-batches, where uniformly sampled component gradients provide unbiased estimators.
- The subsequent analysis seeks sufficient conditions for generalized Adam to converge to first-order stationary solutions at a sublinear rate.
3 CONVERGENCE ANALYSIS FOR GENERALIZED ADAM
The analysis gives sufficient conditions for generalized Adam-type methods to converge in non-convex optimization, expressed through effective-step-size growth and bounded update conditions. It also shows these conditions are tight: excessive growth or oscillation can cause divergence, while AMSGrad and AdaFom attain sublinear rates under stated assumptions.
- Assumptions: The analysis assumes a differentiable function with Lipschitz gradient and lower-bounded objective, bounded true and noisy gradients, and unbiased independent gradient noise.These are assumptions A1–A3 used throughout the stochastic non-convex analysis.
- Convergence conditions: Theorem 3.1 requires bounded normalized updates, ∥αtmt/√ˆvt∥≤G, alongside non-increasing momentum parameters bounded by β1.For bounded gradients, this condition is automatically satisfied by AdaGrad and AMSGrad; adding a numerical-stability constant preserves the result.
- Convergence conditions: The main convergence condition is s1(T) = o(s2(T)), which ensures the bound in Theorem 3.1 yields convergence.The requirement compares terms controlling possible ascent against the accumulated effective stepsizes.
- Interpretation of the bound: Term A measures curvature-related objective increase, while Term B captures oscillation from skewed update directions; either can grow too quickly and prevent convergence.The effective-step-size accumulation must dominate these quantities for the theorem’s bound to vanish.
- Tightness and examples: In the toy problem, AMSGrad converges while SGD and Adam do not when Term A grows as fast as effective-step-size accumulation.For Adam, constant stepsizes in [10^-4, 0.1] produce oscillation in this example, whereas AMSGrad’s normalization keeps both terms smaller.
- Tightness and examples: Adam also fails in the stochastic example because Term B can grow as fast as accumulated effective stepsizes, while AMSGrad converges with smaller effective-step-size oscillation.This matches the theoretical non-convergence condition O(s1(T)/s2(T)) ≠ o(1).
- AMSGrad and AdaFom: The AMSGrad rate’s additional log T factor can be eliminated by using a constant rather than diminishing stepsize, such as αt = 1/√T.The paper nevertheless notes that sharper worst-case theory quantifying adaptive methods’ benefits remains open.
4 EMPIRICAL PERFORMANCE OF ADAM-TYPE ALGORITHMS ON MNIST
The paper compares Adam-type algorithms on MNIST and reports training-loss and testing-accuracy behavior across iterations. Adam and AMSGrad perform similarly, while AdaFom improves over AdaGrad but generally trails Adam and AMSGrad.
- Experimental setup: The experiments train convolutional neural networks on MNIST and CIFAR-10 using AMSGrad, Adam, AdaFom, and AdaGrad.The MNIST model has three convolutional and two fully connected layers; the CIFAR experiment uses CIFARNET.
- MNIST results: Figure 3 compares the algorithms by training loss and testing accuracy versus the number of iterations.
- MNIST results: On MNIST, AMSGrad performs similarly to Adam, while AdaGrad performs worse than the other algorithms.The paper attributes AdaGrad’s weaker performance to lacking momentum and/or using a significantly different second-moment estimate.
- MNIST results: On MNIST, AdaFom performs between AMSGrad or Adam and AdaGrad.AdaFom is described as a momentum version of AdaGrad with a simpler adaptive learning rate independent of β2.
- CIFAR-10 results: On CIFAR-10, Adam and AMSGrad achieve the best accuracy, while AdaFom outperforms AdaGrad in both training and testing.The CIFAR comparison is shown in Figure 4.
5 CONCLUSION AND DISCUSSION
The paper gives mild conditions for convergence of a broad Adam-type class on non-convex problems and notes that these conditions can also be monitored empirically.
- Mild conditions guarantee convergence for Adam-type algorithms, including Adam, AMSGrad, AdaGrad, AdaFom, SGD, and SGD with momentum.
- The convergence conditions can be checked in practice to monitor empirical convergence.
6.1 RELATED WORK
Adaptive gradient methods combine momentum and adaptive learning rates, but their behavior depends on the algorithm and setting. Experiments illustrate both their flexible stepsizes and cases where SGD or adaptive methods perform better.
- Background: Adaptive gradient methods update descent directions and learning rates simultaneously using past information, combining momentum and learning-rate adaptation.The family includes RMSProp, Nadam, and Adam.
- Motivation: Theoretical analysis remained incomplete because existing Adam and AMSGrad convergence results addressed convex problems, while nonconvex convergence was still open.This motivates studying adaptive methods in nonconvex optimization.
- Advantages and disadvantages: Adaptive normalization can provide flexible stepsizes that reduce oscillation and overshoot from large stepsizes and ease hyperparameter tuning.The paper presents this as a possible practical advantage of adaptive gradient methods.
- Advantages and disadvantages: Performance depends on the stepsize and problem: SGD converges faster in one tested case, and Figure A3 shows a case where AMSGrad does not perform well.The paper interprets the key quantity as informative about convergence speed in several figures, but not uniformly.
- Experimental details: The MNIST and CIFAR-10 experiments use tuned algorithm-specific learning-rate schedules and neural-network architectures.MNIST uses a CNN; CIFARNET uses convolutional layers, pooling, dropout, and a fully connected layer.
6.2 CONVERGENCE PROOF FOR GENERALIZED ADAM (ALGORITHM 1)
The convergence proof decomposes expected descent into auxiliary terms and bounds them under the theorem’s assumptions. The resulting bounds are then verified for AMSGrad and AdaFom through their specific update rules and normalization properties.
- Convergence proof: The proof of Algorithm 1 combines Lemmas 6.2–6.7 to bound the overall expected descent of the objective.The argument rearranges the resulting inequality to obtain the theorem’s convergence bound.
- Auxiliary decomposition: The analysis introduces an auxiliary sequence zt to rewrite the iterates and isolate descent, bias, and momentum-related terms.The sequence is defined from xt and the momentum parameter, while the stochastic gradient is decomposed into the true gradient plus zero-mean noise.
- Auxiliary lemmas: Several lemma bounds rely on bounded gradients, bounded normalized updates, monotonic momentum parameters, Lipschitz smoothness, and telescoping sums.The proof explicitly invokes these assumptions and inequalities when bounding T1, T2, T3, and T4.
- AMSGrad corollary: For AMSGrad, nondecreasing second-moment normalization and a positive initial coordinatewise scale support lower effective-stepsize bounds and logarithmic terms.The proof assumes min_j(√v̂_1)_j ≥ c > 0 and verifies ||αtm_t/√v̂_t|| ≤ H/c.
- AdaFom corollary: AdaFom uses a momentum first-moment update with an AdaGrad-style running second-moment average, and its proof follows the same general bounding strategy.The derivation uses an initial coordinatewise gradient lower bound and bounds the terms in the theorem’s right-hand side.