Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise
Not on the map. Why?
Abstract (arXiv)
This paper considers the problem of asynchronous stochastic nonconvex optimization with heavy-tailed gradient noise and arbitrarily heterogeneous computation times across workers. We propose an asynchronous normalized stochastic gradient descent algorithm with momentum. The analysis show that our method achieves the optimal time complexity under the assumption of bounded pth-order central moment with p∈(1,2]. We also provide numerical experiments to show the effectiveness of proposed method.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 38 of its 49 references that are in the map. First posted on arXiv 27 Jan 2026.
Builds on
38 of 49 references.
References · 38
- 2019Advances and Open Problems in Federated Learningcited by 3,046
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2017Ray: A Distributed Framework for Emerging AI Applicationscited by 527
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
- 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
- 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
- 2021FjORD: Fair and Accurate Federated Learning under heterogeneous targets with Ordered Dropoutcited by 192
- 2017Asynchronous Decentralized Parallel Stochastic Gradient Descentcited by 159
- 2020The Heavy-Tail Phenomenon in SGDcited by 124
- 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
- 2023Linear attention is (maybe) all you need (to understand transformer optimization)cited by 98
26 more
- 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
- 2018Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGDcited by 68
- 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 63
- 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
- 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
- 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
- 2020Advances in Asynchronous Parallel and Distributed Optimizationcited by 40
- 2015An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimizationcited by 38
- 2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
- 2023Revisiting the Noise Model of Stochastic Gradient Descentcited by 36
- 2021On Proximal Policy Optimization's Heavy-tailed Gradientscited by 31
- 2023Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Modelcited by 24
- 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 21
- 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
- 2025Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexitycited by 18
- 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 14
- 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
- 2023Provably Robust Temporal Difference Learning for Heavy-Tailed Rewardscited by 9
- 2024Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamicscited by 9
- 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
- 2024Ordered Momentum for Asynchronous SGDcited by 5
- 2025Decentralized Nonconvex Optimization under Heavy-Tailed Noise: Normalization and Optimal Convergencecited by 5
- 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 4
- 2023Distributed Stochastic Optimization under Heavy-Tailed Noisescited by 3
- 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 2
- 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.