On the rates of convergence of parallelized averaged stochastic gradient algorithms

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.

• Publication year

  2017

• Venue

  Statistics (Berlin)

• Publication date

  2017-10-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1080/02331888.2020.1764557arXiv 1710.07926
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Online estimation of the asymptotic variance for averaged stochastic gradient algorithms

  2017cited by this paper
• A Central Limit Theorem for averaged stochastic gradient algorithms in Hilbert spaces and online estimation of the asymptotic variance. Application to the Geometric Median and Quantiles

  2017cited by this paper
• On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression

  2017cited by this paper
• Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression

  2016cited by this paper
• On projected stochastic gradient descent algorithm with weighted averaging for least squares regression

  2016cited by this paper
• Stochastic Heavy ball

  2016cited by this paper
• Lp and almost sure rates of convergence of averaged stochastic gradient algorithms: locally strongly convex objective

  2016cited by this paper
• Estimating the geometric median in Hilbert spaces with stochastic gradient algorithms: Lp and almost sure rates of convergence

  2016cited by this paper
• $L^{p}$ and almost sure rates of convergence of averaged stochastic gradient algorithms with applications to online robust estimation

  2016cited by this paper
• Online estimation of the geometric median in Hilbert spaces : non asymptotic confidence balls

  2015cited by this paper
• Statistical decision making for optimal budget allocation in crowd labeling

  2014cited by this paper
• Online Asynchronous Distributed Regression

  2014cited by this paper
• An asynchronous parallel stochastic coordinate descent algorithm

  2013cited by this paper
• Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression

  2013cited by this paper
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

  2013cited by this paper
• Parallel stochastic gradient algorithms for large-scale matrix completion

  2013cited by this paper
• Performance of a Distributed Stochastic Approximation Algorithm

  2012influential reference
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework

  2012cited by this paper
• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm

  2011cited by this paper
• Parallelized Stochastic Gradient Descent

  2010cited by this paper
• Stochastic Approximation and Recursive Algorithms and Applications

  2003cited by this paper
• Asymptotic Almost Sure Efficiency of Averaged Stochastic Algorithms

  2000cited by this paper
• On the almost sure asymptotic behaviour of stochastic algorithms

  1998cited by this paper
• Random iterative models

  1996cited by this paper
• Acceleration of stochastic approximation by averaging

  1992cited by this paper
• TIGHTNESS CRITERIA FOR RANDOM MEASURES WITH APPLICATION TO THE PRINCIPLE OF CONDITIONING IN I-ULBEWT SPACES

  1988cited by this paper
• Efficient Estimations from a Slowly Convergent Robbins-Monro Process

  1988cited by this paper
• Problem Complexity and Method Efficiency in Optimization

  1984cited by this paper
• Problem Complexity and Method Efficiency in Optimization

  1983cited by this paper
• A Stochastic Approximation Method

  1951cited by this paper
• Note on the median of a multivariate distribution

  1948cited by this paper

• An Accelerated Second-Order Method for Distributed Stochastic Optimization

  2021cites this paper
• Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems

  2021cites this paper
• Communication-efficient SGD: From Local SGD to One-Shot Averaging

  2021cites this paper
• Local SGD With a Communication Overhead Depending Only on the Number of Workers

  2020cites this paper
• Is Local SGD Better than Minibatch SGD?

  2020cites this paper
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks

  2020cites this paper
• Federated Accelerated Stochastic Gradient Descent

  2020cites this paper
• Parallel and Distributed algorithms for ML problems

  2020cites this paper
• Federated Composite Optimization

  2020cites this paper
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization

  2019cites this paper
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication

  2019cites this paper
• On the Convergence of Local Descent Methods in Federated Learning

  2019cites this paper
• Communication trade-offs for Local-SGD with large step size

  2019influential citation
• Communication trade-offs for synchronized distributed SGD with large step size

  2019cites this paper
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication

  2019cites this paper
• Local SGD Converges Fast and Communicates Little

  2018cites this paper