Accelerated Convex Optimization with Stochastic Gradients: Generalizing the Strong-Growth Condition

2022/07/24 by Víctor Valls, Shiqiang Wang, Valls, Víctor +5
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2207.11833

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

Abstract

This paper presents a sufficient condition for stochastic gradients not to slow down the convergence of Nesterov's accelerated gradient method. The new condition has the strong-growth condition by Schmidt & Roux as a special case, and it also allows us to (i) model problems with constraints and (ii) design new types of oracles (e.g., oracles for finite-sum problems such as SAGA). Our results are obtained by revisiting Nesterov's accelerated algorithm and are useful for designing stochastic oracles without changing the underlying first-order method.

Related

• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation
• Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming
• Accelerated and nonaccelerated stochastic gradient descent with model conception
• Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Condition
• Accelerated and nonaccelerated stochastic gradient descent with inexact model