REVIEW 2 minor 142 references
Gradient clipping removes the maximum delay dependence from the oracle complexity of asynchronous SGD.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.3
2026-06-27 07:21 UTC pith:OQKJTO36
load-bearing objection Clipping removes max delay from async SGD rates under sub-Weibull noise and delivers the first high-probability bound, but the tail assumption carries the result.
Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By clipping gradients before they are applied, the oracle complexity of asynchronous SGD becomes independent of the maximum delay among workers, yielding both expectation and high-probability convergence guarantees under a sub-Weibull model of gradient noise.
What carries the argument
Gradient clipping applied to asynchronous updates, paired with a sub-Weibull model of gradient noise.
Load-bearing premise
Gradient noise is modeled as sub-Weibull distributed to derive the delay-independent bound.
What would settle it
An experiment that measures oracle complexity with clipping and shows the rate still grows with the maximum delay.
If this is right
- Asynchronous training can proceed without waiting for any worker, raising hardware utilization.
- Convergence rates remain stable even when some workers are much slower than others.
- High-probability bounds become available for the first time in this setting.
- The same clipping step applies equally in distributed and federated environments.
Where Pith is reading between the lines
- The same clipping step could be tested in other asynchronous first-order methods to check for similar delay independence.
- Empirical checks of gradient tail behavior in large models would test whether the noise model fits observed data.
- Scheduling policies that tolerate variable worker speeds might become preferable once clipping is in place.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims that gradient clipping in asynchronous SGD (ASGD), including distributed and federated variants, removes the dependence on the maximum delay au_max from the oracle complexity. This holds under a sub-Weibull model of gradient noise that generalizes sub-Gaussian and sub-exponential tails. The authors establish convergence in expectation and, for the first time in asynchronous optimization, convergence with high probability.
Significance. If the central claims hold, the work supplies a theoretical account for the empirical stabilization effect of clipping in asynchronous deep learning training on heterogeneous hardware. The sub-Weibull noise model is motivated by observed heavy-tailed gradients and enables both the delay-independent bound and the novel high-probability guarantee. These strengths—machine-checked-style theoretical results under a realistic noise model and the first HP convergence in the async setting—would make the contribution notable for robust parallel optimization.
minor comments (2)
- [Abstract] Abstract: states the main results but supplies no derivation details, error bounds, or explicit assumptions beyond the sub-Weibull model; adding a brief statement of the achieved rate (e.g., dependence on clipping threshold and tail parameter) would improve readability.
- [Introduction] The sub-Weibull assumption is load-bearing for both the delay-independent claim and the high-probability result; a short remark clarifying what happens under weaker moment conditions (even if outside the paper's scope) would help readers assess the result's robustness.
Simulated Author's Rebuttal
We thank the referee for their positive evaluation of the manuscript and for recommending minor revision. The referee's summary correctly reflects our central claims regarding the effect of gradient clipping on the oracle complexity of asynchronous SGD under a sub-Weibull noise model, as well as the high-probability convergence result.
Circularity Check
No circularity: standard convergence analysis under explicit noise assumption
full rationale
The paper derives delay-independent oracle complexity and high-probability convergence for clipped async SGD by applying standard martingale and concentration arguments to the clipped gradient updates under an explicit sub-Weibull noise model. No equations reduce to self-definitions, no fitted parameters are relabeled as predictions, and no load-bearing steps rely on self-citations or imported uniqueness theorems. The sub-Weibull tail parameter is stated as an assumption motivated by DL observations, not derived from the target bound, so the derivation chain remains independent of its own outputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Gradient noise follows a sub-Weibull distribution
read the original abstract
In modern machine learning, parallelization of training is an important strategy for increasing scale. Asynchronous stochastic gradient descent (ASGD), which maximizes the utilization of available hardware by avoiding waiting for slow workers. However, with constant step sizes, the convergence of ASGD is nonetheless affected negatively by slow workers due to large delays in updates. At the same time, it has been empirically observed in asynchronous training of deep learning models that gradient clipping "stabilizes" training. In this work, we provide a theoretical justification for this behavior, as we show that clipping removes the dependence of the maximum delay in the oracle complexity. We employ a sub-Weibull model of gradient noise which generalizes sub-Gaussian and sub-exponential distributions to more heavy-tailed distributions, motivated by empirical observations in deep learning. We show convergence in expectation, and the first time in asynchronous optimization, convergence with high probability.
Figures
Reference graph
Works this paper leans on
-
[1]
Sharper Convergence Guarantees for Asynchronous
Koloskova, Anastasiia and Stich, Sebastian U and Jaggi, Martin , booktitle =. Sharper Convergence Guarantees for Asynchronous
-
[2]
Proceedings of the 39th International Conference on Machine Learning , pages =
Delay-Adaptive Step-sizes for Asynchronous Learning , author =. Proceedings of the 39th International Conference on Machine Learning , pages =. 2022 , editor =
2022
-
[3]
Asynchronous Stochastic Optimization Robust to Arbitrary Delays , url =
Cohen, Alon and Daniely, Amit and Drori, Yoel and Koren, Tomer and Schain, Mariano , booktitle =. Asynchronous Stochastic Optimization Robust to Arbitrary Delays , url =
-
[4]
Proceedings of the 34th International Conference on Machine Learning , pages =
Asynchronous Stochastic Gradient Descent with Delay Compensation , author =. Proceedings of the 34th International Conference on Machine Learning , pages =. 2017 , editor =
2017
-
[6]
Revisiting Distributed Synchronous
Jianmin Chen and Rajat Monga and Samy Bengio and Rafal Jozefowicz , year =. Revisiting Distributed Synchronous
-
[7]
International Conference on Learning Representations , year =
Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity , author =. International Conference on Learning Representations , year =
-
[8]
Improved Analysis of Clipping Algorithms for Non-convex Optimization , url =
Zhang, Bohang and Jin, Jikai and Fang, Cong and Wang, Liwei , booktitle =. Improved Analysis of Clipping Algorithms for Non-convex Optimization , url =
-
[9]
Proceedings of the 40th International Conference on Machine Learning , pages =
Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees , author =. Proceedings of the 40th International Conference on Machine Learning , pages =. 2023 , editor =
2023
-
[10]
Proceedings of the 38th International Conference on Machine Learning , pages =
Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness , author =. Proceedings of the 38th International Conference on Machine Learning , pages =. 2021 , editor =
2021
-
[11]
Personalized Federated Learning with Theoretical Guarantees: A Model-Agnostic Meta-Learning Approach , url =
Fallah, Alireza and Mokhtari, Aryan and Ozdaglar, Asuman , booktitle =. Personalized Federated Learning with Theoretical Guarantees: A Model-Agnostic Meta-Learning Approach , url =
-
[12]
2017 , editor =
McMahan, Brendan and Moore, Eider and Ramage, Daniel and Hampson, Seth and Arcas, Blaise Aguera y , booktitle =. 2017 , editor =
2017
-
[13]
arXiv preprint arXiv:2306.08393 , year =
Provably personalized and robust federated learning , author =. arXiv preprint arXiv:2306.08393 , year =
-
[14]
2022 IEEE International Smart Cities Conference (ISC2) , pages =
Personalized federated learning via convex clustering , author =. 2022 IEEE International Smart Cities Conference (ISC2) , pages =. 2022 , organization =
2022
-
[15]
Electronics , volume =
A Personalized Federated Learning Method Based on Clustering and Knowledge Distillation , author =. Electronics , volume =. 2024 , publisher =
2024
-
[16]
Advances in Neural Information Processing Systems , volume =
An efficient framework for clustered federated learning , author =. Advances in Neural Information Processing Systems , volume =
-
[17]
arXiv preprint arXiv:2003.13461 , year =
Adaptive personalized federated learning , author =. arXiv preprint arXiv:2003.13461 , year =
-
[18]
Ando, Rie and Zhang, Tong , journal =
-
[19]
arXiv preprint arXiv:2310.01973 , year =
Federated wasserstein distance , author =. arXiv preprint arXiv:2310.01973 , year =
-
[20]
Cédric Villani , title =
-
[21]
Asynchronous
Mishchenko, Konstantin and Bach, Francis and Even, Mathieu and Woodworth, Blake E , booktitle =. Asynchronous
-
[22]
Stat , volume =
Sub-Weibull distributions: Generalizing sub-Gaussian and sub-Exponential properties to heavier tailed distributions , author =. Stat , volume =. 2020 , publisher =
2020
-
[23]
Localized Upper and Lower Bounds for Some Estimation Problems
Zhang, Tong. Localized Upper and Lower Bounds for Some Estimation Problems. Learning Theory. 2005
2005
-
[24]
Better Theory for
Ahmed Khaled and Peter Richt. Better Theory for. Transactions on Machine Learning Research , issn =. 2023 , url =
2023
-
[25]
IEEE Transactions on Automatic Control , volume =
An asynchronous mini-batch algorithm for regularized stochastic optimization , author =. IEEE Transactions on Automatic Control , volume =. 2016 , publisher =
2016
-
[26]
Advances in neural information processing systems , volume =
Hogwild!: A lock-free approach to parallelizing stochastic gradient descent , author =. Advances in neural information processing systems , volume =
-
[27]
Advances in Neural Information Processing Systems , volume =
Why are adaptive methods good for attention models? , author =. Advances in Neural Information Processing Systems , volume =
-
[28]
The heavy-tail phenomenon in
Gurbuzbalaban, Mert and Simsekli, Umut and Zhu, Lingjiong , booktitle =. The heavy-tail phenomenon in. 2021 , organization =
2021
-
[29]
Proceedings of the 39th International Conference on Machine Learning , pages =
High Probability Guarantees for Nonconvex Stochastic Gradient Descent with Heavy Tails , author =. Proceedings of the 39th International Conference on Machine Learning , pages =. 2022 , editor =
2022
-
[30]
Journal of Machine Learning Research , year =
Liam Madden and Emiliano Dall'Anese and Stephen Becker , title =. Journal of Machine Learning Research , year =
-
[31]
2018 , editor =
Nguyen, Lam and NGUYEN, PHUONG HA and van Dijk, Marten and Richtarik, Peter and Scheinberg, Katya and Takac, Martin , booktitle =. 2018 , editor =
2018
-
[32]
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16) , year =
Wei Zhang and Suyog Gupta and Xiangru Lian and Ji Liu , title =. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16) , year =
-
[33]
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics , pages =
AdaDelay: Delay Adaptive Distributed Stochastic Optimization , author =. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics , pages =. 2016 , editor =
2016
-
[34]
Advances in Neural Information Processing Systems , volume =
Delay-tolerant algorithms for asynchronous distributed online learning , author =. Advances in Neural Information Processing Systems , volume =
-
[35]
Bertsekas and John N
Dimitri P. Bertsekas and John N. Tsitsiklis , title =
-
[36]
Advances in neural information processing systems , volume =
Distributed delayed stochastic optimization , author =. Advances in neural information processing systems , volume =
-
[38]
IEEE transactions on automatic control , volume =
Distributed asynchronous deterministic and stochastic gradient optimization algorithms , author =. IEEE transactions on automatic control , volume =. 2003 , publisher =
2003
-
[39]
International conference on artificial intelligence and statistics , pages =
Federated learning with buffered asynchronous aggregation , author =. International conference on artificial intelligence and statistics , pages =. 2022 , organization =
2022
-
[40]
Federated learning and analytics in practice: algorithms, systems, applications, and opportunities , year =
Tackling the data heterogeneity in asynchronous federated learning with cached update calibration , author =. Federated learning and analytics in practice: algorithms, systems, applications, and opportunities , year =
-
[41]
Forty-second International Conference on Machine Learning , year =
Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching , author =. Forty-second International Conference on Machine Learning , year =
-
[42]
Journal of Machine Learning Research , volume =
Hamid Reza Feyzmahdavian and Mikael Johansson , title =. Journal of Machine Learning Research , volume =
-
[43]
ACM Computing Surveys (CSUR) , volume =
Demystifying parallel and distributed deep learning: An in-depth concurrency analysis , author =. ACM Computing Surveys (CSUR) , volume =. 2019 , publisher =
2019
-
[44]
Proceedings of Machine Learning and Systems , volume =
Papaya: Practical, private, and scalable federated learning , author =. Proceedings of Machine Learning and Systems , volume =
-
[45]
OPT2020: 12th Annual Workshop on Optimization for Machine Learning , year =
Asynchronous Federated Optimization , author =. OPT2020: 12th Annual Workshop on Optimization for Machine Learning , year =
-
[46]
2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages =
Unbounded gradients in federated learning with buffered asynchronous aggregation , author =. 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages =. 2022 , organization =
2022
-
[47]
Proceedings of the 41st International Conference on Machine Learning , series =
FADAS: Towards Federated Adaptive Asynchronous Optimization , author =. Proceedings of the 41st International Conference on Machine Learning , series =. 2024 , address =
2024
-
[48]
Understanding Priors in
Vladimirova, Mariia and Verbeek, Jakob and Mesejo, Pablo and Arbel , Julyan , booktitle =. Understanding Priors in. 2019 , editor =
2019
-
[49]
Information and Inference: A Journal of the IMA , volume =
Moving beyond sub-Gaussianity in high-dimensional statistics: Applications in covariance estimation and linear regression , author =. Information and Inference: A Journal of the IMA , volume =. 2022 , publisher =
2022
-
[50]
Presentation at Google, Mountain View, 2nd April , volume =
Statistical language models based on neural networks , author =. Presentation at Google, Mountain View, 2nd April , volume =
-
[51]
Mathematical Programming , volume =
On the projected subgradient method for nonsmooth convex optimization in a Hilbert space , author =. Mathematical Programming , volume =. 1998 , publisher =
1998
-
[52]
Book in preparation for MIT Press , author =
Deep learning. Book in preparation for MIT Press , author =
-
[53]
Proceedings of the 30th International Conference on Machine Learning , pages =
On the difficulty of training recurrent neural networks , author =. Proceedings of the 30th International Conference on Machine Learning , pages =. 2013 , editor =
2013
-
[54]
IEEE transactions on neural networks , volume =
Learning long-term dependencies with gradient descent is difficult , author =. IEEE transactions on neural networks , volume =. 1994 , publisher =
1994
-
[55]
Proceedings of the 2016 ACM SIGSAC conference on computer and communications security , pages =
Deep learning with differential privacy , author =. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security , pages =
2016
-
[56]
Advances in Neural Information Processing Systems , volume =
Differentially private empirical risk minimization revisited: Faster and more general , author =. Advances in Neural Information Processing Systems , volume =
-
[57]
International colloquium on automata, languages, and programming , pages =
Differential privacy , author =. International colloquium on automata, languages, and programming , pages =. 2006 , organization =
2006
-
[58]
Journal of the ACM (JACM) , volume =
Privacy aware learning , author =. Journal of the ACM (JACM) , volume =. 2014 , publisher =
2014
-
[59]
arXiv preprint arXiv:2406.04443 , year =
Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed , author =. arXiv preprint arXiv:2406.04443 , year =
-
[60]
Advances in Neural Information Processing Systems , volume =
Stochastic optimization with heavy-tailed noise via accelerated gradient clipping , author =. Advances in Neural Information Processing Systems , volume =
-
[61]
International Conference on Machine Learning , pages =
A tail-index analysis of stochastic gradient noise in deep neural networks , author =. International Conference on Machine Learning , pages =. 2019 , organization =
2019
-
[62]
Science Meets Engineering of Deep Learning (SEDL) Workshop at the 33rd Conference on Neural Information Processing Systems (NeurIPS) , year =
Non-Gaussianity of Stochastic Gradient Noise , author =. Science Meets Engineering of Deep Learning (SEDL) Workshop at the 33rd Conference on Neural Information Processing Systems (NeurIPS) , year =
-
[63]
From Gradient Clipping to Normalization for Heavy Tailed
H. From Gradient Clipping to Normalization for Heavy Tailed. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics , pages =. 2025 , editor =
2025
-
[64]
High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails , url =
Cutkosky, Ashok and Mehta, Harsh , booktitle =. High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails , url =
-
[65]
Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise , volume =
Nguyen, Ta Duy and Nguyen, Thien H and Ene, Alina and Nguyen, Huy , booktitle =. Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise , volume =
-
[66]
2014 IEEE 55th annual symposium on foundations of computer science , pages =
Private empirical risk minimization: Efficient algorithms and tight error bounds , author =. 2014 IEEE 55th annual symposium on foundations of computer science , pages =. 2014 , organization =
2014
-
[67]
Foundations and trends
The algorithmic foundations of differential privacy , author =. Foundations and trends. 2014 , publisher =
2014
-
[68]
Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data , booktitle =
Nicolas Papernot and Mart. Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data , booktitle =
-
[69]
Brendan McMahan and Daniel Ramage and Kunal Talwar and Li Zhang , title =
H. Brendan McMahan and Daniel Ramage and Kunal Talwar and Li Zhang , title =. Proceedings of the 6th International Conference on Learning Representations (ICLR) , year =
-
[70]
, title =
Mania, Horia and Pan, Xinghao and Papailiopoulos, Dimitris and Recht, Benjamin and Ramchandran, Kannan and Jordan, Michael I. , title =. SIAM Journal on Optimization , volume =. 2017 , doi =
2017
-
[71]
Stich and Sai Praneeth Karimireddy , title =
Sebastian U. Stich and Sai Praneeth Karimireddy , title =. Journal of Machine Learning Research , year =
-
[72]
Advances in neural information processing systems , volume =
Large scale distributed deep networks , author =. Advances in neural information processing systems , volume =
-
[73]
Understanding gradient clipping in private
Chen, Xiangyi and Wu, Steven Z and Hong, Mingyi , journal =. Understanding gradient clipping in private
-
[74]
Advances in Neural Information Processing Systems , volume =
Optimal time complexities of parallel stochastic optimization methods under a fixed computation model , author =. Advances in Neural Information Processing Systems , volume =
-
[75]
Learning multiple layers of features from tiny images.(2009) , author =
2009
-
[76]
2015 , howpublished =
Karpathy, Andrej , title =. 2015 , howpublished =
2015
-
[77]
Proceedings of the IEEE conference on computer vision and pattern recognition , pages =
Deep residual learning for image recognition , author =. Proceedings of the IEEE conference on computer vision and pattern recognition , pages =
-
[78]
Neural computation , volume =
Long short-term memory , author =. Neural computation , volume =. 1997 , publisher =
1997
-
[80]
2024 , howpublished =
Muon: An Optimizer for Hidden Layers in Neural Networks , author =. 2024 , howpublished =
2024
-
[81]
International Conference on Learning Representations (ICLR) , year =
Adam: A Method for Stochastic Optimization , author =. International Conference on Learning Representations (ICLR) , year =
-
[82]
Ringmaster
Arto Maranjyan and Alexander Tyurin and Peter Richt. Ringmaster. Forty-second International Conference on Machine Learning , year =
-
[83]
Ringleader
Arto Maranjyan and Peter Richt. Ringleader. The Fourteenth International Conference on Learning Representations , year =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.