Distributed stochastic optimization with large delays
From MaRDI portal
Abstract: One of the most widely used methods for solving large-scale stochastic optimization problems is distributed asynchronous stochastic gradient descent (DASGD), a family of algorithms that result from parallelizing stochastic gradient descent on distributed computing architectures (possibly) asychronously. However, a key obstacle in the efficient implementation of DASGD is the issue of delays: when a computing node contributes a gradient update, the global model parameter may have already been updated by other nodes several times over, thereby rendering this gradient information stale. These delays can quickly add up if the computational throughput of a node is saturated, so the convergence of DASGD may be compromised in the presence of large delays. Our first contribution is that, by carefully tuning the algorithm's step-size, convergence to the critical set is still achieved in mean square, even if the delays grow unbounded at a polynomial rate. We also establish finer results in a broad class of structured optimization problems (called variationally coherent), where we show that DASGD converges to a global optimum with probability under the same delay assumptions. Together, these results contribute to the broad landscape of large-scale non-convex stochastic optimization by offering state-of-the-art theoretical guarantees and providing insights for algorithm design.
Recommendations
- A distributed flexible delay-tolerant proximal gradient algorithm
- On the convergence of asynchronous parallel iteration with unbounded delays
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
- On unbounded delays in asynchronous parallel fixed-point algorithms
Cites work
- A Distributed, Asynchronous, and Incremental Algorithm for Nonconvex Optimization: An ADMM Approach
- Accelerated, parallel, and proximal coordinate descent
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
- Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
- Asymptotic pseudotrajectories and chain recurrent flows, with applications
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Coordinate descent algorithms
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- Distributed block coordinate descent for minimizing partially separable functions
- Ergodic properties of weak asymptotic pseudotrajectories for semiflows
- Foundations of mathematical economics
- scientific article; zbMATH DE number 3723610 (Why is no real title available?)
- scientific article; zbMATH DE number 1206370 (Why is no real title available?)
- scientific article; zbMATH DE number 1321699 (Why is no real title available?)
- scientific article; zbMATH DE number 2121076 (Why is no real title available?)
- scientific article; zbMATH DE number 1405930 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- On the convergence of mirror descent beyond stochastic convex programming
- Optimization of stochastic virus detection in contact networks
- Perturbed iterate analysis for asynchronous stochastic optimization
- Revisiting Asynchronous Linear Solvers
- Stochastic approximation. A dynamical systems viewpoint.
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
Cited in
(14)- On the convergence of asynchronous parallel iteration with unbounded delays
- On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
- ADVANCES IN DISTRIBUTED OPTIMIZATION USING PROBABILITY COLLECTIVES
- Group stochastic gradient descent: a tradeoff between straggler and staleness
- The error-feedback framework: SGD with delayed gradients
- A distributed flexible delay-tolerant proximal gradient algorithm
- Delay reduction via Lagrange multipliers in stochastic network optimization
- Distributed stochastic inertial-accelerated methods with delayed derivatives for nonconvex problems
- Improving the Transient Times for Distributed Stochastic Gradient Methods
- No-regret learning for repeated non-cooperative games with lossy bandits
- Asynchronous SGD with stale gradient dynamic adjustment for deep learning training
- Numerical methods for stochastic optimization problems with decision-dependent distributions under large delays
- Learning-based fast alternating direction method of multipliers for multi-agent path finding using temporary variable-fixing
- Age-of-information in distributed systems caused by asynchronous computing modeled as parallel renewal processes
This page was built for publication: Distributed stochastic optimization with large delays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5868949)
