Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

By Sharan Vaswani, Francis R. Bach, Mark W. Schmidt. 2018

345 citations recorded by the source corpus.

Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition, we prove that constant step-size stochastic gradient descent (SGD) with Nesterov acceleration matches the convergence rate of the deterministic accelerated method for both convex and strongly-convex functions. We also show that this condition implies that SGD can find a first-order stationary point as efficiently as full gradient descent in non-convex settings. Under interpolation, we further show that all smooth loss functions with a finite-sum structure satisfy a weaker growth condition. Given this weaker condition, we prove that SGD with a constant step-size attains the deterministic convergence rate in both the strongly-convex and convex settings. Under additional assumptions, the above results enable us to prove an O(1/k^2) mistake bound for k iterations of a stochastic perceptron algorithm using the squared-hinge loss. Finally, we validate our theoretical findings with experiments on synthetic and real datasets.

Subfields: Artificial Intelligence, 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 Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…a recent line work that these assumptions might be restrictive or never be satisﬁed 5 and proposed alternative conditions [Nguyen et al., 2018, Vaswani et al., 2018, Gower et al., 2019, 2021, Khaled et al., 2020, Khaled and Richtárik, 2020, Assran et al., 2019, Koloskova et al., 2020, Patel…”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “For this set of experiments, we also plot how the stepsize varies across iterations for SLS, SPS and ALI-G.”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Furthermore, a modest batch-growth strategy and stochastic line-search (Vaswani et al., 2019b) scheme ensure that R-SSN is computationally eﬃcient and competitive with stochastic ﬁrst-order methods and L-BFGS variants in terms of both the number of iterations and wall-clock time required for…”
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).”
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “The performance of MimeLite can be attributed to the observation that the SVRG correction may not be necessary in deep learning [5, 34].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “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]. However, these metrics cannot be easily calculate”
SGD: General Analysis and Improved Rates (2019, background): “If ( f, D ) ∼ ES ( ) and if σ = 0 , then f satisﬁes the weak growth condition This corollary should be contrasted with Proposition 2 in (Vaswani et al., 2018) and Lemma 1 in (Nguyen et al., 2018), where it is shown, by assuming the f i functions to be smooth and convex, that the weak growth…”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, methodology): “Vaswani et al. (2019) obtain linear convergence under a strong growth condition using an alternative formulation of ASG which has multiple momentum parameters by keeping the step-size constant and having the momentum parameters vary.”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, neutral): “2 relies on the two-level nested iterations of M-ASG, we believe that more simple algorithms may also lead to similar convergence rates, e.g. directly using Nesterov’s gradient descent and its recent stochastic analysis by Vaswani et al. (2019).”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, methodology): “We selected the kernel band-width 0.05 following Vaswani et al. (2019b).”
Linear Lower Bounds and Conditioning of Differentiable Games (2019, background): “Conditions of this type can be satisfied in over-parameterised neural networks (Vaswani et al., 2019).”
Accelerating Stochastic Training for Over-parametrized Learning (2018, result): “During preparing this work, we note that a parallel work (Vaswani et al., 2018) also analyzes the first-order algorithm with momentum and obtained a similar accelerated convergence over SGD.”
SGD without Replacement: Sharper Rates for General Smooth Convex Functions (2019, background): “SGD has been extensively studied in literature and a vast number of results are known in many different settings, most prominent being that of convex optimization (Benaı̈m, 1999; Borkar, 2009; Kushner & Yin, 2003; Bubeck, 2015; Bottou et al., 2018; Schmidt & Roux, 2013; Gower et al., 2019; Nguyen et”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “Assumptions 3* with σ(2) = 0 is referred to as the weak growth condition in (Vaswani et al., 2018).”
Loss landscapes and optimization in over-parameterized non-linear systems and neural networks (2020, methodology): “To give just one example, we expect that accelerated methods, such as the Nesterov’s method [26] and its stochastic gradient extensions in the over-parameterized case [22, 35] to have faster convergence rates for non-linear systems in terms of the condition numbers defined in this work.”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, background): “[40] Sharan Vaswani, Francis Bach, and Mark Schmidt.”
Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path? (2018, background): “PL condition is particularly suited for analyzing overparameterized problems and has been utilized by several recent papers (Bassily et al., 2018; Karimi et al., 2016; Lei et al., 2017; Ma et al., 2017; Vaswani et al., 2018).”