On Almost Sure Convergence Rates of Stochastic Gradient Methods

2022/02/09 by Jun Liu, Ye Yuan, Liu, Jun +1 · 7 citations
Computer Science · Engineering · Medicine · #Advanced Neuroimaging Techniques and Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2202.04295

openalex publication_date 2022/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The vast majority of convergence rates analysis for stochastic gradient methods in the literature focus on convergence in expectation, whereas trajectory-wise almost sure convergence is clearly important to ensure that any instantiation of the stochastic algorithms would converge with probability one. Here we provide a unified almost sure convergence rates analysis for stochastic gradient descent (SGD), stochastic heavy-ball (SHB), and stochastic Nesterov's accelerated gradient (SNAG) methods. We show, for the first time, that the almost sure convergence rates obtained for these stochastic gradient methods on strongly convex functions, are arbitrarily close to their optimal convergence rates possible. For non-convex objective functions, we not only show that a weighted average of the squared gradient norms converges to zero almost surely, but also the last iterates of the algorithms. We further provide last-iterate almost sure convergence rates analysis for stochastic gradient methods on weakly convex smooth functions, in contrast with most existing results in the literature that only provide convergence in expectation for a weighted average of the iterates.

Cited by

• Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective
• Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods
• Towards Formalizing Reinforcement Learning Theory
• Statistical Inference for Linear Functionals of Online Least-squares SGD when t \gtrsim d^1+δ
• Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
• Convergence of Stochastic Gradient Methods for Wide Two-Layer Physics-Informed Neural Networks for the Poisson Equation
• Convergence of Momentum-Based Optimization Algorithms with Time-Varying Parameters

Related

• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
• Lp and almost sure rates of convergence of averaged stochastic gradient algorithms: locally strongly convex objective
• Accelerated Almost-Sure Convergence Rates for Nonconvex Stochastic Gradient Descent using Stochastic Learning Rates
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems
• Stochastic gradient descent algorithms for strongly convex functions at O(1/T) convergence rates