On the rates of convergence of parallelized averaged stochastic gradient algorithms

By Antoine Godichon-Baggioni, Sofiane Saadane. 2017

16 citations recorded by the source corpus.

ABSTRACT The growing interest for high-dimensional and functional data analysis led in the last decade to important research developing a consequent amount of techniques. Parallelized algorithms, which consist of distributing and treat the data into different machines, for example, are a good answer to deal with large samples taking values in high-dimensional spaces. We introduce here a parallelized averaged stochastic gradient algorithm, which enables to treat efficiently and recursively the data, and so, without taking care if the distribution of the data into the machines is uniform. The rate of convergence in quadratic mean, as well as the asymptotic normality of the parallelized estimates are given, for strongly and locally strongly convex objectives.

Subfields: Artificial Intelligence, 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

Is Local SGD Better than Minibatch SGD? (2020, neutral): “(Zinkevich et al., 2010; Zhang et al., 2012; Li et al., 2014; Rosenblatt and Nadler, 2016; Godichon-Baggioni and Saadane, 2017; Jain et al., 2017).”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “[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.”
Local SGD Converges Fast and Communicates Little (2018, background): “[49] show statistical convergence (see also [10, 13, 33]), but the analysis restricts the algorithm to at most one pass over the data, which is in general not enough for the training error to converge.”
On the Convergence of Local Descent Methods in Federated Learning (2019, background): “[6,11,29,38] analyze convergence from statistical point of view with only one-pass over the training data which usually is not suﬃcient for the convergence of training error.”
Communication trade-offs for Local-SGD with large step size (2019, methodology): “…approaches have received attention: 1) workers run SGD independently and at the end aggregate their results, called one-shot averaging ( OSA ) [13, 15] or parameter mixing , and 2) mini-batch averaging ( MBA ) [16–20], where workers communicate after every iteration: all gradients are thus…”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “Early analyses focused on variants with only one averaging step (McDonald et al., 2009; Zinkevich et al., 2010; Zhang et al., 2013; Shamir and Srebro, 2014; Godichon-Baggioni and Saadane, 2017; Jain et al., 2018).”