Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition

Abstract

We consider optimizing a function smooth convex function $f$ that is the average of a set of differentiable functions $f_i$, under the assumption considered by Solodov [1998] and Tseng [1998] that the norm of each gradient $f_i^{\prime }$ is bounded by a linear function of the norm of the average gradient $f^{\prime }$. We show that under these assumptions the basic stochastic gradient method with a sufficiently-small constant step-size has an $O(1/k)$ convergence rate, and has a linear convergence rate if $g$ is strongly-convex.

Cited by in corpus (15)

• Federated Optimization in Heterogeneous Networks
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Accelerating SGD with momentum for over-parameterized learning
• A globally convergent incremental Newton method
• SGD: General Analysis and Improved Rates
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Stochastic Sign Descent Methods: New Algorithms and Better Theory
• Trading-off variance and complexity in stochastic gradient descent
• Stochastic Gradient Descent for Linear Systems with Missing Data
• Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD