Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition

By Mark W. Schmidt, Nicolas Le Roux. 2013

175 citations recorded by the source corpus.

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'$ is bounded by a linear function of the norm of the average gradient $f'$. 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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “In this setting, SGD with constant step-size can been shown to converge to the exact optimum at the deterministic rate (Schmidt and Roux, 2013; Ma et al., 2018; Vaswani et al., 2019a,b; Gower et al., 2019; Berrada et al., 2020).”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “The high expressivity of these models enables them to interpolate the training data, meaning that the gradient for each component function in the finite sum can become zero at the solution of the overall objective (Schmidt and Roux, 2013; Vaswani et al., 2019a,b; Ma et al., 2018; Bassily et al., 201”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “To prove convergence results in the non-convex case, we additionally require the strong growth condition (SGC) [73, 83] to hold.”
Federated Optimization in Heterogeneous Networks (2018, methodology): “Interestingly, similar assumptions (e.g., Schmidt & Roux, 2013; Vaswani et al., 2019; Yin et al., 2018) have been explored elsewhere but for differing purposes; we provide a discussion of these works in Appendix B. Definition 3 (B-local dissimilarity).”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “Our re-sults show that in overparametrized settings no drift effects occur and linear convergence can be achieved similar as to the centralized setting (Schmidt & Roux, 2013; Needell et al., 2016; Ma et al., 2018).”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Recent works have aimed to quantify statistical heterogeneity through metrics such as local dissimilarity (as deﬁned in the context of federated learning in [65] and used for other purposes in works such as [100, 116, 130]) and earth mover’s distance [138].”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “Schmidt and Le Roux’s work [32] derives optimal convergence rates for constant step-size SGD under the above condition for both convex and strongly-convex functions.”
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.”
Linear Convergence of Adaptive Stochastic Gradient Descent (2019, background): “However, this assumption is much weaker than (Strong or Weak) Growth Condition in [35, 36] where it assumes that for all We are the ﬁrst to use this weaker assumption and characterize a better convergence rate of AdaGrad-Norm for many optimization problems that satisfy Assumption (A4).”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “SGC + L –smooth = ⇒ WGC .”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, methodology): “Under a strong growth condition, Schmidt and Roux (2013) prove that SGD could achieve a global linear rate.”
MaSS: an Accelerated Stochastic Method for Over-parametrized Learning (2018, background): “This observation underlies exponential convergence of SGD in certain convex settings [20, 12, 19, 13, 11].”
Better Theory for SGD in the Nonconvex World (2020, methodology): “…literature we are aware of (see Figure 1), including assumptions such as bounded variance (BV) (Ghadimi & Lan, 2013), uniform strong growth (U-SG) (Schmidt & Roux, 2013), strong growth (SG) (Vaswani et al., 2019), relaxed growth (RG) (Bottou et al., 2018), and gradient confusion (GC)…”
Unified Optimal Analysis of the (Stochastic) Gradient Method (2019, background): “(Grimmer, 2019), though very similar conditions have been studied in the literature (Bertsekas and Tsitsiklis, 1996; Schmidt and Roux, 2013; Needell et al., 2016; Bottou et al., 2018; Gower et al., 2019).”
On the Convergence of Federated Optimization in Heterogeneous Networks (2018, methodology): “A similar assumption has been previously used to analyze variants of SGD for strongly convex problems (Schmidt & Roux, 2013).”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “These insights in the problem structure were first discussed in (Bach and Moulines, 2011) and refined in (Schmidt and Roux, 2013; Needell et al., 2016) and allowed to derive the first linear convergence rates for SGD on finite sum problems in the special case when σ(2) = 0.”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, background): “It has been observed in some settings that stronger convergence guarantees can also be obtained when interpolation or a related assumption holds; e.g., Schmidt & Le Roux (2013); Loizou & Richt´arik (2017); Ma et al. (2018); Vaswani et al. (2019).”