Asynchronous Stochastic Optimization Robust to Arbitrary Delays

2021/06/22 by Alon Cohen, Amit Daniely, Cohen, Alon +7 · 5 citations
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2106.11879

openalex publication_date 2021/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider stochastic optimization with delayed gradients where, at each time step t, the algorithm makes an update using a stale stochastic gradient from step t - d_t for some arbitrary delay d_t. This setting abstracts asynchronous distributed optimization where a central server receives gradient updates computed by worker machines. These machines can experience computation and communication loads that might vary significantly over time. In the general non-convex smooth optimization setting, we give a simple and efficient algorithm that requires O( σ²/ε⁴ + τ/ε² ) steps for finding an ε-stationary point x, where τ is the average delay \smash(1)/(T)∑_t=1^T d_t and σ² is the variance of the stochastic gradients. This improves over previous work, which showed that stochastic gradient decent achieves the same rate but with respect to the maximal delay max_t d_t, that can be significantly larger than the average delay especially in heterogeneous distributed systems. Our experiments demonstrate the efficacy and robustness of our algorithm in cases where the delay distribution is skewed or heavy-tailed.

Citations

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Learning Multiple Layers of Features from Tiny Images

Cited by

• Performance and Stability of Barrier Mode Parallel Systems with Heterogeneous and Redundant Jobs
• A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
• Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning
• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity
• Partial Parameter Updates for Efficient Distributed Training

Related

• Distributed Delayed Stochastic Optimization
• Distributed stochastic optimization with large delays
• Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching
• AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization
• Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays