Asynchronous stochastic convex optimization

Abstract

We show that asymptotically, completely asynchronous stochastic gradient procedures achieve optimal (even to constant factors) convergence rates for the solution of convex optimization problems under nearly the same conditions required for asymptotic optimality of standard stochastic gradient procedures. Roughly, the noise inherent to the stochastic approximation scheme dominates any noise from asynchrony. We also give empirical evidence demonstrating the strong performance of asynchronous, parallel stochastic optimization schemes, demonstrating that the robustness inherent to stochastic approximation problems allows substantially faster parallel and asynchronous solution methods.

38 pages, 8 figures

References in corpus (3)

• Searching for Exotic Particles in High-Energy Physics with Deep Learning
• Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
• An optimal algorithm for stochastic strongly-convex optimization

Cited by in corpus (18)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Delay and Cooperation in Nonstochastic Bandits
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation
• Adaptive Gradient Quantization for Data-Parallel SGD
• Communication trade-offs for synchronized distributed SGD with large step size
• The Convergence of Sparsified Gradient Methods
• Asymptotic Optimality in Stochastic Optimization
• NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization
• On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms
• On the convergence of mirror descent beyond stochastic convex programming
• Layered gradient accumulation and modular pipeline parallelism: fast and efficient training of large language models
• Consistent Lock-free Parallel Stochastic Gradient Descent for Fast and Stable Convergence
• The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
• Asynchronous Decentralized Stochastic Optimization in Heterogeneous Networks
• Distributed Networked Real-time Learning