On the convergence of asynchronous parallel iteration with unbounded delays
From MaRDI portal
Publication:2422607
Abstract: Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we call delay, is the number of times it has been updated since its creation. Almost all recent works prove convergence under the assumption of a finite maximum delay and set their stepsize parameters accordingly. However, the maximum delay is practically unknown. This paper presents convergence analysis of an async-parallel method from a probabilistic viewpoint, and it allows for large unbounded delays. An explicit formula of stepsize that guarantees convergence is given depending on delays' statistics. With identical processors, we empirically measured that delays closely follow the Poisson distribution with parameter , matching our theoretical model, and thus the stepsize can be set accordingly. Simulations on both convex and nonconvex optimization problems demonstrate the validness of our analysis and also show that the existing maximum-delay induced stepsize is too conservative, often slowing down the convergence of the algorithm.
Recommendations
- On unbounded delays in asynchronous parallel fixed-point algorithms
- Convergence analysis of asynchronous linear iterations with stochastic delays
- Asymptotic behavior of asynchronous stochastic approximation
- Distributed stochastic optimization with large delays
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Cites work
- A case study in programming for parallel-processors
- A coordinate gradient descent method for nonsmooth separable minimization
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- A probabilistic analysis of asynchronous iteration
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Asynchronous parallel algorithms for nonconvex optimization
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Augmented _1 and nuclear-norm models with a globally linearly convergent algorithm
- Block stochastic gradient iteration for convex and nonconvex optimization
- Chaotic relaxation
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Distributed asynchronous computation of fixed points
- Efficiency of coordinate descent methods on huge-scale optimization problems
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Iteration complexity analysis of block coordinate descent methods
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- On asynchronous iterations
- On the complexity analysis of randomized block-coordinate descent methods
- On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
- On the convergence of the coordinate descent method for convex differentiable minimization
- On unbounded delays in asynchronous parallel fixed-point algorithms
- Partially Asynchronous, Parallel Algorithms for Network Flow and Other Problems
- Probability: a graduate course
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- Support-vector networks
- Tensor Regression with Applications in Neuroimaging Data Analysis
- Variational Analysis
Cited in
(9)- On unbounded delays in asynchronous parallel fixed-point algorithms
- Asynchronous parallel algorithms for nonconvex optimization
- Markov chain block coordinate descent
- On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- Distributed stochastic inertial-accelerated methods with delayed derivatives for nonconvex problems
- Distributed stochastic optimization with large delays
- Parallel and distributed asynchronous adaptive stochastic gradient methods
- Parallel asynchronous iterations of least fixed points
This page was built for publication: On the convergence of asynchronous parallel iteration with unbounded delays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2422607)
