On the convergence analysis of asynchronous SGD for solving consistent linear systems
From MaRDI portal
Publication:2685380
asynchronous communicationdistributed optimizationiterative methodslinear systemsparallel algorithmsstochastic optimization
Linear equations (linear algebraic aspects) (15A06) Iterative numerical methods for linear systems (65F10) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Quadratic programming (90C20)
Abstract: In the realm of big data and machine learning, data-parallel, distributed stochastic algorithms have drawn significant attention in the present days.~While the synchronous versions of these algorithms are well understood in terms of their convergence, the convergence analyses of their asynchronous counterparts are not widely studied. In this paper, we propose and analyze a {it distributed, asynchronous parallel} SGD in light of solving an arbitrary consistent linear system by reformulating the system into a stochastic optimization problem as studied by Richt'{a}rik and Tak'{a}~{c} in [35]. We compare the convergence rates of our asynchronous SGD algorithm with the synchronous parallel algorithm proposed by Richt'{a}rik and Tak'{a}v{c} in [35] under different choices of the hyperparameters---the stepsize, the damping factor, the number of processors, and the delay factor. We show that our asynchronous parallel SGD algorithm also enjoys a global linear convergence rate, similar to the {em basic} method and the synchronous parallel method in [35] for solving any arbitrary consistent linear system via stochastic reformulation. We also show that our asynchronous parallel SGD improves upon the {em basic} method with a better convergence rate when the number of processors is larger than four. We further show that this asynchronous approach performs asymptotically better than its synchronous counterpart for certain linear systems. Moreover, for certain linear systems, we compute the minimum number of processors required for which our asynchronous parallel SGD is better, and find that this number can be as low as two for some ill-conditioned problems.
Recommendations
- Revisiting Asynchronous Linear Solvers
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
- On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem
Cites work
- A Stochastic Approximation Method
- Accelerated, parallel, and proximal coordinate descent
- Chaotic relaxation
- Distributed block coordinate descent for minimizing partially separable functions
- Distributed coordinate descent method for learning with big data
- Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
- scientific article; zbMATH DE number 6508162 (Why is no real title available?)
- On asynchronous iterations
- Optimal distributed online prediction using mini-batches
- Parallel coordinate descent methods for big data optimization
- Perturbed iterate analysis for asynchronous stochastic optimization
- Randomized iterative methods for linear systems
- Stochastic reformulations of linear systems: algorithms and convergence theory
Cited in
(5)- Revisiting Asynchronous Linear Solvers
- On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
- Convergence rate analysis of an asynchronous space decomposition method for convex Minimization
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
This page was built for publication: On the convergence analysis of asynchronous SGD for solving consistent linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2685380)
