DSA: decentralized double stochastic averaging gradient algorithm
From MaRDI portal
Abstract: This paper considers convex optimization problems where nodes of a network have access to summands of a global objective. Each of these local objectives is further assumed to be an average of a finite set of functions. The motivation for this setup is to solve large scale machine learning problems where elements of the training set are distributed to multiple computational elements. The decentralized double stochastic averaging gradient (DSA) algorithm is proposed as a solution alternative that relies on: (i) The use of local stochastic averaging gradients. (ii) Determination of descent steps as differences of consecutive stochastic averaging gradients. Strong convexity of local functions and Lipschitz continuity of local gradients is shown to guarantee linear convergence of the sequence generated by DSA in expectation. Local iterates are further shown to approach the optimal argument for almost all realizations. The expected linear convergence of DSA is in contrast to the sublinear rate characteristic of existing methods for decentralized stochastic optimization. Numerical experiments on a logistic regression problem illustrate reductions in convergence time and number of feature vectors processed until convergence relative to these other alternatives.
Recommendations
- On the convergence of decentralized gradient descent
- Communication-efficient algorithms for decentralized and stochastic optimization
- Primal-dual stochastic distributed algorithm for constrained convex optimization
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Decentralized consensus algorithm with delayed and stochastic gradients
Cited in
(30)- Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method
- On the linear convergence of two decentralized algorithms
- Fully asynchronous policy evaluation in distributed reinforcement learning over networks
- Dualize, split, randomize: toward fast nonsmooth optimization algorithms
- Linear convergence of primal-dual gradient methods and their performance in distributed optimization
- Primal-dual stochastic distributed algorithm for constrained convex optimization
- Multi-cluster distributed optimization via random sleep strategy
- Differentially private distributed optimization for multi-agent systems via the augmented Lagrangian algorithm
- On the convergence of decentralized gradient descent
- Primal-dual algorithm for distributed constrained optimization
- Revisiting EXTRA for Smooth Distributed Optimization
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Decentralized consensus algorithm with delayed and stochastic gradients
- Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate
- Graph-dependent implicit regularisation for distributed stochastic subgradient descent
- GADMM: fast and communication efficient framework for distributed machine learning
- A class of parallel doubly stochastic algorithms for large-scale learning
- A randomized incremental primal-dual method for decentralized consensus optimization
- On the convergence of exact distributed generalisation and acceleration algorithm for convex optimisation
- Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
- scientific article; zbMATH DE number 7307473 (Why is no real title available?)
- An Optimal Algorithm for Decentralized Finite-Sum Optimization
- Decentralized dictionary learning over time-varying digraphs
- Optimal convergence rates for convex distributed optimization in networks
- A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
- Decentralized learning over a network with Nyström approximation using SGD
- Distributed SGD in overparametrized linear regression
- A decentralized Nesterov gradient method for stochastic optimization over unbalanced directed networks
- An accelerated decentralized stochastic optimization algorithm with inexact model
- Distributed policy gradient with variance reduction in multi-agent reinforcement learning
This page was built for publication: DSA: decentralized double stochastic averaging gradient algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2810864)
