Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise
Not on the map. Why?
Abstract (arXiv)
This paper studies decentralized stochastic nonconvex optimization problem over row-stochastic networks. We consider the heavy-tailed gradient noise which is empirically observed in many popular real-world applications. Specifically, we propose a decentralized normalized stochastic gradient descent with Pull-Diag gradient tracking, which achieves approximate stationary points with the optimal sample complexity and the near-optimal communication complexity. We further follow our framework to study the setting of undirected networks, also achieving the nearly tight upper complexity bounds. Moreover, we conduct empirical studies to show the practical superiority of the proposed methods.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 52 of its 68 references that are in the map. First posted on arXiv 16 Jan 2026.
Builds on
52 of 68 references.
References · 52
- 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,850
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
- 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
- 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
- 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
- 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
- 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 150
- 2018D2: Decentralized Training over Decentralized Datacited by 140
- 2020Momentum Improves Normalized SGDcited by 139
- 2017Network Topology and Communication-Computation Tradeoffs in Decentralized Optimizationcited by 122
- 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
38 more
- 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
- 2013Distributed optimization over time-varying directed graphscited by 78
- 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 69
- 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
- 2020Optimal Complexity in Decentralized Trainingcited by 60
- 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
- 2018Push-Pull Gradient Methods for Distributed Optimization in Networkscited by 46
- 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
- 2021DecentLaM: Decentralized Momentum SGD for Large-batch Deep Trainingcited by 40
- 2023Revisiting the Noise Model of Stochastic Gradient Descentcited by 36
- 2021On Proximal Policy Optimization's Heavy-tailed Gradientscited by 31
- 2017Accelerated Distributed Nesterov Gradient Descentcited by 25
- 2018A linear algorithm for optimization over directed graphs with geometric convergencecited by 25
- 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 23
- 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 21
- 2020Multi-consensus Decentralized Accelerated Gradient Descentcited by 20
- 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
- 2021Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networkscited by 19
- 2016ADD-OPT: Accelerated Distributed Directed Optimizationcited by 14
- 2018Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient trackingcited by 14
- 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 14
- 2020S-ADDOPT: Decentralized stochastic first-order optimization over directed graphscited by 13
- 2016Linear convergence in optimization over directed graphs with row-stochastic matricescited by 12
- 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
- 2018FROST -- Fast row-stochastic optimization with uncoordinated step-sizescited by 8
- 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
- 2019Distributed Nesterov gradient methods over arbitrary graphscited by 6
- 2022Heavy-Tail Phenomenon in Decentralized SGDcited by 6
- 2021Decentralized Asynchronous Non-convex Stochastic Optimization on Directed Graphscited by 5
- 2022Robust Federated Learning with Connectivity Failures: A Semi-Decentralized Framework with Collaborative Relayingcited by 5
- 2024Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimizationcited by 5
- 2025Decentralized Nonconvex Optimization under Heavy-Tailed Noise: Normalization and Optimal Convergencecited by 5
- 2015ExtraPush for convex smooth decentralized optimization over directed networkscited by 4
- 2018Distributed Optimization over Directed Graphs with Row Stochasticity and Constraint Regularitycited by 4
- 2021A Fast Row-Stochastic Decentralized Method for Distributed Optimization Over Directed Graphscited by 4
- 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 4
- 2023Understanding the Influence of Digraphs on Decentralized Optimization: Effective Metrics, Lower Bound, and Optimal Algorithmcited by 3
50 most cited of 52 All 52 (JSON)
Built on by
Citing papers per year: 2026: 1.
1 paper.