Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification

By Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford. 2016

188 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Measuring the Effects of Data Parallelism on Neural Network Training (2018, background): “Focusing on linear least-squares regression, Jain et al. (2018) also derive a threshold batch size, here in terms of (i) the operator norm of the objective’s Hessian and (ii) a constant from a fourth-moment bound on example inputs.”
Is Local SGD Better than Minibatch SGD? (2020, background): “[10] study a similar setting and analyze our “minibatch SGD” for M = 1 and fixed KR, but varying K and R.”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, methodology): “[48, 31, 11, 16] represent statistical convergence analysis with only one-pass over the training data which usually is not enough for the training error to converge.”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “[24] study one-shot averaging on quadratic functions and Bijral et al.”
Local SGD Converges Fast and Communicates Little (2018, background): “[13] give concise speedup results in terms of bias and variance for one-shot SGD with constant stepsizes for the optimization of quadratic least squares problems.”
On the Convergence of Local Descent Methods in Federated Learning (2019, background): “Additionally, for one-shot averaging [11] provides speedup with respect to bias and variance for the special case of quadratic square optimization problems.”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, methodology): “[For e.g. Appendix A.2.2 from Jain et al. (2016)] Bias-Variance tradeoff: Running SGD for T − steps starting from w 0 and a stepsize sequence { η t } T t =1 presents a ﬁnal iterate w T whose excess risk is upper-bounded as: where, Proof.”
Gradient Diversity: a Key Ingredient for Scalable Distributed Learning (2017, methodology): “In particular, for least square problems, Jain et al. (2016) propose a bound on batch-size similar to our measure of gradient diversity; however, as mentioned in Section 1, our result holds for a wider range of problems including nonconvex setups, and can be used to motivate heuristics that result…”
Bridging the gap between constant step size stochastic gradient descent and Markov chains (2017, background): “Analysis has been extended to “tail averaging” [28], to improve the dependence on the initial conditions.”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, methodology): “COMPARISONS WITH PREVIOUS RESULTS In the following, we compare our Theorem 1 and Corollary 2 with related work in SA (Ghadimi and Lan, 2012; Dieuleveut et al., 2017; Jain et al., 2018; Moulines and Bach, 2011; Needell et al., 2014) and SAA (Zhang et al.”
On the Effectiveness of Richardson Extrapolation in Machine Learning (2020, unknown): “While Jain et al. (2018) focuses on a non-asymptotic analysis for stochastic problems for leastsquares regression, we now provide an asymptotic analysis for general convex objective functions and non-stochastic problems (see proof in Appendix B).”
The Effect of Network Width on the Performance of Large-batch Training (2018, background): “Several theoretical results [23, 20, 24, 21, 19, 20] suggest that, when the batch size B becomes larger than a problem-dependent threshold B ∗ , the total number of iterations to converge signiﬁcantly increases, rendering the use of larger B a less viable option.”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “We see that Assumption 3* in the form of (8) is slightly more general, though we like to point out that for least squares problems the analyses typically also consider the structure of covariance of the noise to get more fine-grained results (Dieuleveut et al., 2017; Jain et al., 2018), a refinement”