Asynchronous Coordinate Descent under More Realistic Assumptions

Abstract

Asynchronous-parallel algorithms have the potential to vastly speed up algorithms by eliminating costly synchronization. However, our understanding to these algorithms is limited because the current convergence of asynchronous (block) coordinate descent algorithms are based on somewhat unrealistic assumptions. In particular, the age of the shared optimization variables being used to update a block is assumed to be independent of the block being updated. Also, it is assumed that the updates are applied to randomly chosen blocks. In this paper, we argue that these assumptions either fail to hold or will imply less efficient implementations. We then prove the convergence of asynchronous-parallel block coordinate descent under more realistic assumptions, in particular, always without the independence assumption. The analysis permits both the deterministic (essentially) cyclic and random rules for block choices. Because a bound on the asynchronous delays may or may not be available, we establish convergence for both bounded delays and unbounded delays. The analysis also covers nonconvex, weakly convex, and strongly convex functions. We construct Lyapunov functions that directly model both objective progress and delays, so delays are not treated errors or noise. A continuous-time ODE is provided to explain the construction at a high level.

Cited by in corpus (18)

• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• VAFL: a Method of Vertical Asynchronous Federated Learning
• Asynchronous and Parallel Distributed Pose Graph Optimization
• Asynchronous Federated Learning with Differential Privacy for Edge Intelligence
• Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
• Non-ergodic Convergence Analysis of Heavy-Ball Algorithms
• Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning
• Async-RED: A Provably Convergent Asynchronous Block Parallel Stochastic Method using Deep Denoising Priors
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
• Markov Chain Block Coordinate Descent
• An Analysis of Asynchronous Stochastic Accelerated Coordinate Descent
• Toward Creating Subsurface Camera
• Non-ergodic Complexity of Convex Proximal Inertial Gradient Descents
• Stability and Generalization for Randomized Coordinate Descent
• A generic coordinate descent solver for nonsmooth convex optimization
• Fully Asynchronous Stochastic Coordinate Descent: A Tight Lower Bound on the Parallelism Achieving Linear Speedup
• A Nonlinear Bregman Primal-Dual Framework for Optimizing Nonconvex Infimal Convolutions
• Asynchronous Delay-Aware Accelerated Proximal Coordinate Descent for Nonconvex Nonsmooth Problems