Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters
and Non-ergodic Case
- URL: http://arxiv.org/abs/2307.11782v1
- Date: Thu, 20 Jul 2023 12:02:17 GMT
- Title: Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters
and Non-ergodic Case
- Authors: Meixuan He, Yuqing Liang, Jinlan Liu and Dongpo Xu
- Abstract summary: This paper focuses on exploring the convergence of vanilla Adam and the challenges of non-ergodic convergence.
These findings build a solid theoretical foundation for Adam to solve non-godic optimization problems.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Adam is a commonly used stochastic optimization algorithm in machine
learning. However, its convergence is still not fully understood, especially in
the non-convex setting. This paper focuses on exploring hyperparameter settings
for the convergence of vanilla Adam and tackling the challenges of non-ergodic
convergence related to practical application. The primary contributions are
summarized as follows: firstly, we introduce precise definitions of ergodic and
non-ergodic convergence, which cover nearly all forms of convergence for
stochastic optimization algorithms. Meanwhile, we emphasize the superiority of
non-ergodic convergence over ergodic convergence. Secondly, we establish a
weaker sufficient condition for the ergodic convergence guarantee of Adam,
allowing a more relaxed choice of hyperparameters. On this basis, we achieve
the almost sure ergodic convergence rate of Adam, which is arbitrarily close to
$o(1/\sqrt{K})$. More importantly, we prove, for the first time, that the last
iterate of Adam converges to a stationary point for non-convex objectives.
Finally, we obtain the non-ergodic convergence rate of $O(1/K)$ for function
values under the Polyak-Lojasiewicz (PL) condition. These findings build a
solid theoretical foundation for Adam to solve non-convex stochastic
optimization problems.
Related papers
- Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance [23.112775335244258]
We first analyze RMSProp, which is a special case of Adam with adaptive learning rates but without first-order momentum.
We develop a new upper bound first-order term in the descent lemma, which is also a function of the gradient norm.
Our results for both RMSProp and Adam match with the complexity established in citearvani2023lower.
arXiv Detail & Related papers (2024-04-01T19:17:45Z) - On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond [35.65852208995095]
We demonstrate that Adam achieves a faster convergence compared to SGDM under the condition of non-uniformly bounded smoothness.
Our findings reveal that: (1) in deterministic environments, Adam can attain the known lower bound for the convergence rate of deterministic first-orders, whereas the convergence rate of Gradient Descent with Momentum (GDM) has higher order dependence on the initial function value.
arXiv Detail & Related papers (2024-03-22T11:57:51Z) - Closing the Gap Between the Upper Bound and the Lower Bound of Adam's
Iteration Complexity [51.96093077151991]
We derive a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption.
Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate.
arXiv Detail & Related papers (2023-10-27T09:16:58Z) - UAdam: Unified Adam-Type Algorithmic Framework for Non-Convex Stochastic
Optimization [20.399244578926474]
We introduce a unified framework for Adam-type algorithms (called UAdam)
This is equipped with a general form of the second-order moment, such as NAdamBound, AdaFom, and Adan.
We show that UAdam converges to the neighborhood of stationary points with the rate of $mathcalO (1/T)$.
arXiv Detail & Related papers (2023-05-09T13:07:03Z) - Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions.
We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
arXiv Detail & Related papers (2023-04-27T06:27:37Z) - A Novel Convergence Analysis for Algorithms of the Adam Family [105.22760323075008]
We present a generic proof of convergence for a family of Adam-style methods including Adam, AMSGrad, Adabound, etc.
Our analysis is so simple and generic that it can be leveraged to establish the convergence for solving a broader family of non- compositional optimization problems.
arXiv Detail & Related papers (2021-12-07T02:47:58Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO.
We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size.
Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
arXiv Detail & Related papers (2021-06-30T18:32:46Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
In this paper, we demonstrate the power of a widely used estimator based on moving average (SEMA) problems.
For all these-the-art results, we also present the results for all these-the-art problems.
arXiv Detail & Related papers (2021-04-30T08:50:24Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
We show a proof of convergence between the Adam Adagrad and $O(d(N)/st)$ algorithms.
Adam converges with the same convergence $O(d(N)/st)$ when used with the default parameters.
arXiv Detail & Related papers (2020-03-05T01:56:17Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.