On the linear convergence of the stochastic gradient method with constant step-size

By Volkan Cevher, Bang Công Vu. 2017

31 citations recorded by the source corpus.

The strong growth condition (SGC) is known to be a sufficient condition for linear convergence of the stochastic gradient method using a constant step-size $$\gamma $$γ (SGM-CS). In this paper, we provide a necessary condition, for the linear convergence of SGM-CS, that is weaker than SGC. Moreover, when this necessary is violated up to a additive perturbation $$\sigma $$σ, we show that both the projected stochastic gradient method using a constant step-size, under the restricted strong convexity assumption, and the proximal stochastic gradient method, under the strong convexity assumption, exhibit linear convergence to a noise dominated region, whose distance to the optimal solution is proportional to $${\gamma {\sigma }}$$γσ.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “Its stronger variant (strong growth condition) when δ = 0 has been used in several recent papers (Schmidt and Roux, 2013; Cevher and Vũ, 2019; Vaswani et al., 2019a,b).”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “Additionally, it can match the deterministic rates in the convex (Vaswani et al., 2019a; Schmidt and Roux, 2013; Cevher and Vũ, 2019) and nonconvex (Bassily et al.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, background): “Indeed, recent works [5, 13, 33, 47, 52, 73, 83] have shown that when training over-parameterized models, classic SGD with a constant step-size and without VR can achieve the convergence rates of full-batch gradient descent.”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “There has been some related work that takes advantage of the interpolation property in order to obtain faster rates of convergence for SGD [32, 22, 5].”
SGD: General Analysis and Improved Rates (2019, background): “Based on a strong growth condition ( c 1 = 0 ), Schmidt & Roux (2013) were the ﬁrst to establish linear convergence of SGD, with Cevher & Vu (2017) later giving sufﬁcient and necessary conditions for the linear convergence of SGD under this condition.”