Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case

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.

References in corpus (10)

• Adaptive Gradient Methods with Dynamic Bound of Learning Rate
• Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
• Stability and Generalization of Learning Algorithms that Converge to Global Optima
• Last-iterate convergence analysis of stochastic momentum methods for neural networks
• Adam Can Converge Without Any Modification On Update Rules
• Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions
• A Unified Convergence Theorem for Stochastic Optimization Methods
• Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization
• On Almost Sure Convergence Rates of Stochastic Gradient Methods
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize