Efficient Distributed Optimization under Heavy-Tailed Noise
Authors: Su Hyeong Lee
Manzil Zaheer
Tian Li
Venue: ICML 2025 poster (2025)
Keywords: distributed optimization
adaptive optimization
scalable algorithms
Primary area: optimization

Abstract: Distributed optimization has become the default training paradigm in modern machine learning due to the growing scale of models and datasets. To mitigate communication overhead, local updates are often applied before global aggregation, resulting in a nested optimization approach with inner and outer steps. However, heavy-tailed stochastic gradient noise remains a significant challenge, particularly in attention-based models, hindering effective training. In this work, we propose TailOPT, an efficient framework designed to address heavy-tailed noise by leveraging adaptive optimization and novel clipping techniques. We establish convergence guarantees for the TailOPT framework under heavy-tailed noise with local updates and potentially unbounded gradient variance. 
Among its variants, we propose a memory- and communication-efficient instantiation (named $Bi^2Clip$) that performs coordinate-wise clipping from both above and below at both the inner and outer optimizers. $Bi^2Clip$ brings about benefits of adaptive optimization (e.g., Adam) without the cost of maintaining or transmitting additional gradient statistics. Empirically, TailOPT, including $Bi^2Clip$, demonstrates superior performance on various tasks and models compared with state-of-the-art methods, while being more efficient.

Efficient Distributed Optimization under -leavy-Tailed Noise
Su Hyeong Lee' Manzil Z Tian Li
Abstract
training processes across multiple compute nodes such as GPUs or datacenters. However, this paradigm introduces new bottleneck of communication overhead, especially as the progress in compute power has outpaced that of network infrastructure (Wu et al., 2023; DeepSeek-Al, 2024).
Distributed optimization has become the default training paradigm in modern machine learning due to the growing scale of models and datasets. To mitigate communication overhead, local up- dates are often applied before global aggregation, resulting in a nested optimization approach with inner and outer steps. However, heavy-tailed stochastic gradient noise remains a significant challenge, particularly in attention- based models, hindering effective training. In this work, we pro- pose TailOPT, an efficient framework designed to address heavy-tailed noise by leveraging adaptive optimization and novel clipping techniques. We establish convergence guarantees for the таilOPT framework under heavy-tailed noise with local updates and potentially unbounded gradient vari- ance. Among its variants, we propose a memory- and communication--fficciee instantiation (named Bia Clip) that performs coordinate-wir clipping from both above and below at both the inner and outer optimizers. Clip brings about benefits of adaptive optimization (e.g.. Adam) without the cost of maintaining transmitting additional gra- dient statistics. Empirically, TailOPT, including Clip, demonstrates superior performance on various tasks and models compared with state-of- the-art methods, while being more efficient.
To mitigate these communication challenges, one promising strategy the utilization of local updates. By allowing each compute node to perform multiple gradient updates locally before aggregation, the frequency and volume of inter-node communication can be significantly reduced (Smith et al., 2018; Stich, 2018; McMahan et al., 2017; Lee et al., 2024; Liu et al., 2024a; Jaghouar et al., 2024). For instance, the recent DiLoCo algorithm for training LLMs datacenter en- vironments can apply several hundred local gradient updates prior to aggregation reduce communication costs (Douil- lard et al., 2024). This approach naturally formulates nested optimization problem, where inner optimization oc- curs within each compute node, and outer optimization is orchestrated by the coordinating node(s).
However, training attention- models like L.MS intro- duce an additional challenge due to the properties of their stochastic gradient distributions. Empirical and theoreti- cal investigations have consistently demonstrated that the gradient noise in these models follows heavy-tailed dis- tribution (Ahn et al., 2024; Nguyen et al., 2019; Simsekli et al., 2019; 2020; Kunstner et al., 2024; Gorbunov et al., 2020). This heavy-tailed behavior, characterized by high or infinite variance and potentially very large deviations, poses significant challenges to the stability and convergence of existing optimization algorithms (Zhang et al., 2020b; Lee et al., 2024). Addressing these challenges necessitates the development of novel optimization strategies and a more principled understanding of their theoretical underpinnings.
1. Introduction
The training of deep learning models including large lan- guage models (LLMs) has become increasingly resource- intensive, driven by expansive datasets and models with billions parameters (Rosa et al., 2022: Liu al., 2024b; Sriram et al., 2022: Dehghani et al., 2023). As the computa- tional demands escalate, distributed learning has emerged as the default approach, enabling the parallel activation of
In this work, we propose TailOPT, an efficient and theo- retically principled nested training framework, designed to address the challenges posed by heavy-tailed gradient noise in distributed training with local updates. TailOPT intro- duces several key strategies, including clipping mechanisms (such as moordinate-wist or L2-clipping) and adaptivity, ap- plied at both inner and outer optimizers, to mitigate the adverse effects of heavy-tailed noise. We note that the pre- conditioning step in adaptive optimizers (e.g., Streeter McMahan, 2010) may be viewed form of soft clipping.
'Department of Statistics, University of Chicago MMeta e "Department of Computer Science, University of Chicago. Corre- spondence to: Su Hyeong Lee <sulee @ @uchicug..ccuou.......
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Efficient Distributed Optimization under Heavy-Tailed Noise
We analyze the convergence of TailOPT while incorporat- ing such adaptive methods, while allowing for heavy-tailed noise with unbounded variance. Among the various instan- tiations of the TailOPT framework, we highlight BiPClip, a particularly scalable method that applies coordinate-win clipping to gradients during inner iterations, and to model pa- rameter updates at outer communication rounds, enforcing thresholding from both above and below on a per-coordinate basis. Our empirical and theoretical results demonstrate that TailOPT is strongly effective in mollifying heavy-tailed noise, enhancing the stability and convergence of the train- ing dynamics across several language benchmarks as well as synthetic data.
Recent advancements have explored centralized adaptive op- timization techniques and robust gradient aggregation meth- ods to mitigate the adverse effects of heavy-tailed noise, including gradient clipping (Simsekli et al., 2019; Juditsky et al., 2019a; Gorbunov et al., 2024a; Sadiev et al., 2023; Cutkosky & Mchta, 2021; Nguyen et al., 2023a) or adap- tive clipping strategies (Chezhegov et al., 2024a), However, the complexities of handling heavy-tailed noise in nested distributed optimization environments often prevent these algorithms and their convergence bounds from extending to scenarios with multiple nodes training in parallel. Ad- ditionally, algorithms utilizing adaptive updates generally require preconditioner maintenance that incurs substantial memory costs. To our knowledge, developing an efficient distributed algorithm that provably converges under heavy- tailed stochastic gradient noise has remained an open chal- lenge For example, although DiLoCo (Douillard al., 2024; Jaghouar et al., 2024; Liu et al., 2024a) is a recent algorithmic development with local updates for communi- cation efficiency that demonstrates competitive empirical performance. it noticeably lacks theoretical guarantees, and incurs non-trivial overheads when using adaptive optimizers. Our method addresses these gaps by introducing nested and principled optimization framework, where particular instantiation (Bi² Clip) brings about benefits of adaptivity without the added overhead of maintaining preconditioners, which also outperforms Dil empirically (Section 6).
Our contributions may be summarized as follows.
We introduce TailOPT, a general distributed training framework for large-scale models under communication- efficient local updates and heavy-tailed gradient distribu- tions. Among its instantiations, we highlight Bi Clip, which adjusts to gradient geometry similar to adaptive op- timizers (e.g., Adam (Kingma & Ba, 2015)) while avoid- ing additional memory and communication overhead for maintaining or transmitring preconditioners.
We provide convergence guarantees for a class of TailOPT algorithms that leverage adaptive optimizers and various clipping strategies, effectively addressing heavy-tailed noise with potentially infinite gradient variance. This is achieved using nested optimization framework, where the inner optimizer employs clipping operations to miti- gate heavy-tailed gradient noise, while the outer optimizer utilizes either fully adaptive or efficient approximations of adaptive updates to guide the optimization process.
Clipping for Stabilizing Training Dynamics. Due to its success in stabilizing model updates. gradient clipping is a common technique that has been extensively studied em- pirically (Gehring et al., 2017; Merity et al., 2018; Peters et al., 2018; Mikolov, 2012) and theoretically (Gorbunov et al., 2020; Zhang al., 2020b; Chezhegov et al.,, 2024a; Cutkosky & Mehta, 2021; Menon et al., 2020; Zhang et al., 2020a; Chen et al., 2020; Koloskova et al., 2023; Das et al., 2024). The majority of results study the centralized set- ting (c.g., Gorbunov et al., 2024a; Puchkin et al., 2024; Zhang & Cutkosky, 2022: Liu et al., 2023; Nguyen et al., 2023b; Parletta al., 2024; Li & Liu, 2022), as moving to the distributed setting with local updates for communication efficiency provides significant added analytical challenges such as multiple inner optimizer updates prior to outer op- timizer synchronization. Additionally, it was shown that using a constant clipping threshold can induce gradient bias, preventing the algorithm from ever converging (Chen et al., 2020; Koloskova et al., 2023). Therefore, some works have attempted to circumvent this issue by debiasing via error feedback (Khirirat et al., 2023; Zhang et al., 2024). Other works in distributed optimization have imposed strong dis- tributional stochastic gradient structures in the analysis. For instance, Qian et al. (2021) assume a well-behaved angular dependence between the stochastic and deterministic gra- dients throughout training, and Liu et al. (2022) assume
We validate the practicality and effectiveness of TailOPT through extensive experiments on synthetic and real-world datasets in large-scale settings. Our experiments demon- strate that TailOPT produces several algorithmic instanti- ations that consistently outperform state-of-the-art base- lines while being more efficient.
2. Related Works
We cite the most related work in this section, and provide an extended literature review in Appendix A.
Heavy- Gradient Noise. Training transformers and LLMs is complicated by heavy-tailed stochastic gradient dis- tributions with very large variance, often theoretically and empirically modeled as Lévy a-stable processes (Ahn et al., 2024; Nguyen et al., 2019; Simsekli et al., 2019; 2020; Gor- bunov et al., 2020; Kunstner et al., 2024; Chezhegov et al., 2024a). In such scenarios, vanilla SGD-based optimization methods have been shown to destabilize during training in both centralized as well as distributed settings (Gorbunov et al., 2020; Zhang et al., 2020b; Lee et al., 2024).
2

---

Efficient Distributed Optimization under Heavy-Tailed Noise
symmetric gradient noise, almost surely bounded stochastic gradients, as well as homogeneous data.
recovers the integrability condition of the noise, the minimal assumption necessary to form expectations. Furthermore, we note that EE|| < 00 = E| < for V < a, a E R. Therefore, we let a := [ E (1, 2) in the proceeding analysis for notational convenience.
Our proposed clipping mechanism, realized as an instantia- tion of TailOPT (i.e.. BiClip). fundamentally differs from prior approaches by integrating per-coordinate clipping from both above and below. The inner optimization steps em- ploy clipping operations to adapt to the gradient geometry, complemented by the outer optimizers which enhance rare signals through adaptivity or adaptive approximations. In addition, in the analysis of TailOPT (Section 5), we do not impose any conditions on the noise nor data distributions except for finite noise a-moment for some a E (1, Our algorithm and analysis also accommodate local updates and allow for potentially unbounded stochastic gradient variance. We provide an extended review of distributed algorithms under heavy-tailed noise in Appendix A.
We note that this is strictly weaker than a conventional heavy-tailed assumption on the stochastic gradients, which is commonly given (e.g. Zhang et al., 2020b)) as
BIIV Fi (2). 119 < B,"
which implies that VA, (af) is bounded. By contrast, this cannot be implied by Assumption 2. We also note that some works in the literature also define heavy-tailed distributions with bounded variance when establishing algorithm conver- gence bounds (e.g.. Gorbunov et al., 2020; Parletta et al., 2024; Li & Liu, 2022; Das et al., 2024), which differs from our definition. We carry out our convergence proofs which subsumes the more general infinite variance setting, which naturally implies convergence under bounded stochastic gradients or variance.
3. Problem Formulation
In distributed optimization, the global objective is con- structed by taking a weighted average over the local node objectives (z) for model parameters E Rd and node i. In scenarios where data sizes each node are unbalanced or sampling probabilities vary, the objective becomes:
4. TailOPT: An Efficient Heavy-Tailed Optimization Framework
N-1
F(x)
= Σ P.F.()) ==
(1)
In this section, we begin by motivating the heavy-tailed op- timization framework (TailOPT), a scalable training frame- work for heavy-tailed noise. SGD is strong candidate given its simplicity and efficiency, but it has been shown to diverge under heavy-tailed noise in both centralized (Zhang et al., 2020b) and distributed settings (Lee et al., 2024). Therefore, modifications are necessary to stabilize the noisy updates.
where pi is proportional to the local data size of node i. Here, F((x) is defined as BE-D, [F((z,)) {)). where (z, = Fz(x) + (5,z) represents the stochastic lo- cal objective, and D; is the noise distribution of node This term comes from integrating the gradient noise model V.,(,, < = (=
where x². E are the parameter weights and stochastic gradient noise of node i at timestep f. In our formulation and theoretical analysis (Section 5), we allow for both independent and identically distributed (IID) data across N nodes, as commonly observed in dat- acenter environments, and more challenging non-IID data distributions. We now present the assumptions used in the convergence analysis.
Gradient clipping is widely adopted technique to mitigate the impact of large gradients (Menon et al., 2020; Zhang et al., 2020a; Chen et al., 2020; Koloskova et al., 2023; Yang et al., 2022). Typically, the clipping operator rescales the gradient uniformly to ensure its L2 norm remains below a predefined threshold. This procedure is mathematically equivalent to applying a dynamically adjusted, lower learn- ing rate when large stochastic gradients are encountered. Therefore, we first include and analyze the usage of L2 clip- ping (LzClip) in TailOPT to stabilize heavy-tailed noisy updates. More specifically, we use L2 clipping on the gradi- ents prior to standard gradient descent updates on each node, while global model weight projection strategy is utilized on the outer optimizer after synchronizing all the collected updates. For additional clarity, the precise pseudocode (AI- gorithm 2) and analysis are given in Appendix C.I.
Assumption 1 (L-smoothheess), For all x. X and E [N]. the local objectives (x) satisfy F,(x) S (x y. V (v)) + Lill /
Assumption 2 (Bounded a-moment). For all nodes i E [N] with noise distribution D, there exists 04 E 21, B, > 0 such that B]]|s[||*+ < B
Assumption 2 expresses that the noise distribution can be heavy-tailed. In particular, we note that the variance of the noise can be infinite (a;- = 2), a setting in which distributed SGD was shown to fail to converge, both empirically and the- oretically (Yang et al., 2022; Lee et al., 2024) This condition on the og optimally weakest', in that sending 0;- -> +
Interpolating Adaptivity: BiClip. However, previous works on Le clipping of gradients or model updates (e.g.. Yang et al., 2022) do not adapt to gradient geometry, as
3

---

Efficient Distributed Optimization under Heavy-Tailes Noise
they proportionally and uniformly downscale each gradi- ent coordinate. Therefore, smaller signals become even more difficult to detect and propagate. Adaptive optimizers have consistently demonstrated superior performance for training modern architectures (Zhang et al., 2020b; Reddi et al., 2021; Lee et al., 2024). Key among adaptive methods such as Adam (Kingma & Ba, 2015) and Adagrad (Duchi et al., 2011: I; Streeter & McMahan, 2010) is the use of pre- conditioning, where preconditioners that are estimated from historical gradients effectively result in per-coordinate learn- ing rates. This process amplifies rare yet important gradient coordinates, while scales down uninformative gradients, speeding up the convergence. The trade-off, however, lies in the increased systems requirements to compute and main- tain preconditioners. For instance, deploying Adam can triple the memory demand to host model parameters during minibatch backpropagatton. due to the maintenance of first and second moment exponentially decaying moving average statistics compared to vanilla SGD.
Ag by treating them as pseudogradients, We present multi- ple instantiations of TailOPT along with their convergence bounds under heavy-tailed noise in Section 5, as well as in Appendix C.
Algorithm Heavy-Tailed Optimization (TailOPT)
Require:
Initial model æ1. learning rate schedule n)
Clipping schedules 2, 2 d; 2 0,
Synchronization timestep = E Z
1: for / = ,,..,, T do
2: for each node i E [N]] in parallel do
r/.00 <- Fz
4:
for each local step k E [2] do
5:
Draw gradient gh.x ( St,
si, + ohe "t TailClip( (ut, de, kh.k)
end for
8: end for
9: A & EiE(N (uf,- - x1-1)
10: 3G = Ouler Opplmmizer (se-1; At)
To take advantage of adaptivity without incurring additional memory or communication overhead, we propose a new clipping mechanism, BiClip, that performs coordinate- wise clipping from both above and below. BiClip is moti- vated by an interpolation between clipped-SGD and adaptive methods. It relies on two clipping thresholds (scalars) to dynamically rescale gradients in a per-coordinate fashion, while climinating the overhead of preconditioner mainte- nance. For a model parameter x E RTmh, parameter coordi- nate j E [m]] lower clipping threshold d, and upper clipping threshold u (0 S d S u). BiClip is defined as!
11: end for
Among those, we propose and highlight one efficient method that achieves superior empirical performance which utilizes the BiClip(-) operator (Eq. (2)) in both the inner and outer optimizers, called Clip. The exact pseu- docode is presented in Algorithm 4 (Appendix C.3). Intu- itively, Bi² Clip mitigates the effects of heavy-tailed noise across all inner as well as outer optimizers, while mimick- ing adaptive updates to amplify rare gradient signals. In Section 6, we empirically demonstrate that BiC out- performs state-of-the-art baselines without transferring or maintaining preconditioners in the distributed setting.
BiClip(u, d, m) == sign(x;) [d x (|=y) S d)] + (z,) [u x (|æz) 2 u) + 1x (d < |2z] < u)),
(2)
where x is the indicator function.
For clarity, throughout the paper, we list the outer opti- mizer followed by the inner optimizer when referencing al- gorithms. For example, Adam-BiClipp instantiates Adam as the outer optimizer and BiClip as the inner optimizer. Similarly, RRMSProp-TailChi refers to RMSProp as outer optimizer. and T TailClip (either LyClip or BiClip) as the inner optimizer. Finally, 'Bi BBpClipp' refers to the algorithm with BiClip both inner and outer optimizers.
BiClip draws the intuition of adaptive methods by se- lectively amplifying small gradient coordinates ([2z] S d) while clipping down large ones (ızş) 2 u). In contrast to typical adaptive optimizers, BiClip does not require precon- ditioner maintenance, with significantly reduced optimizer requirements identical to SGD. While our focus is on the distributed setting which aligns with practical applications, we note that BiClip itself can also be beneficial for cen- tralized training (empirically validated in Section 6.4). In the next paragraph, we discuss our general TailOPT frame- work (Algorithm 1), where one instance of TailOPT applies BiClip as both the inner and outer optimizers.
5. Convergence of the TailOPT Framework
Due to space constraints, we present convergence results for only a subset of TailOPT instantiations in the main text. For comprehensive analysis, Appendices C.1 and C.2 provide detailed convergence bounds for Avg-LyClip, and Appen- dices C.3-C.6 include additional convergence analyses and precise pseudocodes for various (adaptive) algorithms of the TailOPT framework incorporating Adagrad, RMSProp. or Adam. Additionally, we note that the convergence of Cipp subsumes that of
TailOPT. In the TailOPT framework (Algorithm 1), the inner optimization strategy, denoted as TailClip, refers to either BiClip Tz2Clip. In Line 10, the outer optimization strategy can be either adaptive or non-adaptive methods that incorporate clipping, adaptivity, or momentum on top of
For clarity in notation, we define 0/0 0.
4

---

Efficient Distributed Optimization under Heavy-Tailed Noise
While clipping offers the benefit of stabilization, it intro- duces non-zero bias on the stochastic gradients, rendering them to be no longer unbiased estimators of the true gradient. Theorems 1 and 2 demonstrate that with appropriately cho- sen (increasing) upper clipping u2 and (decreasing) learning rate 1/ and lower clipping de schedules, convergence of Algorithm 1 is nevertheless attainable. Up to O(d), the presented convergence bounds hold for both gradient-wise clipping as well as coordinate-we -iise clipping. Generalization to layer-wise clipping with varying thresholds specific to each layer or model weight tensor slice is straightforward.
heavy-tailed noise with local updates where the rate is de- pendent on the a-moment condition, which is consistent with prior convergence results in the heavy-tailed setting (e.g., Zhang et al. (2020b)). As a + 17, we see that conver- gence is nullified. We also attain the identical convergence rate for an alternate instantiation Aadagrad-TaailCUee provide the exact algorithm in Algorithm 5 and convergence result in Theorem of the appendix.
and
When deploying distributed optimization, adaptive optimiz- ers such as Adam can considerably increase the memory requirements on each compute node due to preconditioner storage, which matches the model parameter tensor size. This issue gets magnified when one deploys adaptive opti- mizers at both local compute notes and outer coordinating nodes, as preconditioners may be transmitted from outer to inner optimizers to maximize performance, incurring addi- tional communication overhead (Wang et al., 2021b; Sun et al., 2023). This naturally motivates us to apply BiClip (Eq. (2)) at both inner and outer optimizers, resulting in Bi Cipppip, retaining the benefits of adaptivity with minimal overhead. In general, all instantiations of our framework do not require to transmit preconditioners or extra gradient statisties. Convergence results of Bi²Clip are given below.
We carry out our analysis for possibly non-convex problems where the model weights 2t E X are contained within a sufficiently large, compact set X' C IRdd In such settings, finding the global minimum is known to be NP-Hard, and the standard convergence metric is the stabilization of the minimum gradient. We then obtain the following theorems, where the pseudocode for each algorithm instantiation is detailed in Appendix C.
Theorem 1. Let Assumptions 1-2 hold. Instantiating the outer optimizer in Algorithm I with RMSProp gives Algorithm 6 (RMSProp-T
Let the clipping and learning rate thresholds satisfy n; = =tt",, ni = O(t"), de = )t"), and us = Ott)) Impose the rate schedule conditions Ç >> 0, y < 112 and w - 1/2 > O. Then, we have that
Theorem 2. Let the learning rate and clipping schedules satisfy T)2 = O(t"). ni ((")), de O(7"), u, O(t)), J, = ((7). and we = e For Bip (Algorithm 4), we have that the minimum gradient satisfies
6
E (VF (
min
Vi
1=1
min ElI 2 EE(T]
Σ V: 1=1
where the v; are upper bounded by
1 s w+t V2 S ((TT+
where the v are given
3/3 S O +(3
WA s ((
v. = 0 (T (T-W---))
1/2 = 0 (Twttzz-r)
V3 OTT),
1 S O(T Vo ((
1 = O (Ti-"),
V. = 0 0 (Tlo-))o+(100))
which guarantees convergence via an inversely proportional power law decay with respect T. Here, the exponential moving average parameter of the second pseudogrudient moment is fixed within the range B3 E [0. 1).
vo O (TO aellak). 1 (1V11))
To attain convergence, we impose 5,ō > 0 3, for w. I 0, well as -1 < w + Then, for 5 small enough and
In particular, the proof of this result immediately implies the following summarizing corollary.
α
1
Corollary 1. Algorithm 6 (RMSProp- TaillCppp conver- gences under heavy-tailed stochastic gradient noise. The convergence rate can be attained for
4a - 2'
<=
2' 4a
= 2'
Bi² converges with rate ( where a = (a: 1)/(4xx 2) in the limit +
1
a 1
<
This gives the following corollary.
2a
2a
Corollary 2. Algorithm 4 (Bi² (Bi"Clip) converges with respect
as stabilizing the minimum expected gradient norm squared at rate (T()-)))22)
to heavy-tailed stochastic gradient noise (a > 1). For instance, if the moment is further constrained by a 2 1.5. the algorithm converges with a rate of at least O a = 1/8.
The full proofs of all results in this section are given in Appendix C. which holds for both convex and non-convex functions. This achieves convergence in the presence of
Similar as RMSProp-TailClip, the results here hold for
5

---

Efficient Distributed Optimization under Heavy-Tailld Noise
both convex and non-convex functions long as the as- sumptions satisfied. The convergence rate given in Corollary 2 represents a lower bound on the maximal achiev- able rate, obtained by a selection of hyperparameters. In- terestingly, our empirical results demonstrate that Clip outperforms other methods, suggesting that the current con- vergence bounds could be further refined.
Section 6 by sweeping over a hyperparameter grid defined in Appendix D.7. For this result, we extremize the noise tails such that there do such that the a-moment is finite for Va > 1, under which uy stabilizes the gradient dynamics.
6. Experiments
We assess the performance of various TaiOOPT instanti- ations across range of empirical tasks, benchmarking them against oftte-of-the-ar algorithms from the litera- ture. Our experiments include syntheric tasks with heavy- tailed noise injection and real-worid benchmarks, includ- ing GLUE (Wang et al., 2019) for natural language un- derstanding, WMT (Foundation, 2019) for machine trans- lation, Qwen2.5 (Yang et al., 2025) for question answer- ing, and ViT (Dosovitskiy et al., 2021) for image classi- fication. We present brief summary of each experimen- tal setup in the corresponding subsections. Extended de- tails of the experimental setup, dataset descriptions, and extensive hyperparameter tuning procedures (including the best hyperparameters for each method and dataset) are pro- vided in Appendix D. Our code are publicly available at github.com/suleee/Heeaay Tails.
Discussions. To ensure convergence and mitigate bias in the derived bound, it is necessary for the upper clipping threshold it - oo and the lower clipping threshold d, -> 0 as t + oc, consistent with established counterexamples that occur due to unmitigated clipping bias (Koloskova et al., 2023; Chen et al., 2020). In cases where stochastic gradients are sampled from large-variance distributions, this necessi- tates a continual warm-up phase that is continuously relaxed, akin to learning rate warm-up schemes that conclude after finite period (Kosson et al., 2024).
The clipping schedules prescribed by Theorems 1, 2 grow polynomially with respect to f, which depict the realization of model weights throughout training. This effectively de- activates gradient clipping after an initial warm-up phase that is shaped by the noise distribution's 's tail behavior and the clipping thresholds. This may help to explain why learn ing rate warm-ups are observed to significantly improve training (Kalra& & Barkeshli, 2024; Ma & Yarats, 2021) in the presence of heavy-tailes stochastic gradients. Finally, as the maximal bounded moment condition a approaches the integrability threshold (a = 1), or as y nears O-, the convergence bound mollified. Despite this, in our exper- iments, we set < = 7 = 0 (i.e., fixing learning rates and clipping thresholds), which yielded strong empirical performance. Intuitively, this setup corresponds to a contin- ual amplification of informative coordinates and attenuation of uninformative covariates.
6.1. Convex Models
Syuthetic Pure
Syuthetic Gaussian
log 2e, - (il
Aey 860
log([] ue.
Aex- lattte
Auy: meciip
Adams slchip
Adans"
4
log( Outter Node Steps)
log(Outer Node Steps)
(a) No Noise Synthetic Gaussian
(b) Light- Liiht-Tailed& (scale 1) Synthetic t-Dist.
Other Instantiations and Extensions. As noted previ- ously, we extend our analysis to support an Adagrad- based outer optimizer (Algorithm 5) and provide a convergence guarantee under heavy-taiied noise, detailed in Theorem 6 in Appendix C. In Appendix C.6, we further generalize our framework by incorporating momentum into the first-order stochastic pseudogradient statistics, resulting in an outer optimizer Adam instantiation. While we establish that the expected minimum gradient is asymptotically bounded even under restarting (Theorem 8), proving formal convergence to 0 remains an open challenge. The difficulty arises from the moving average applied to the first moment, which re- tains all historical gradient information and complicates the analytical proof structure. We also extend convergence results for certain instantiations to allow for node drop or failures at each round (Appendix C.2). Our bound further highlights that the dominating terms are influenced by the upper clipping threshold uy, which we tune empirically in
2.5
log( Iu
2,0
log
1.5
log (Outer Node Steps)
log(Outer Outer Node Steps)
(c) LighttTTaile Tailed (scale 3)
(d) Heavy-Tailed
Figure I: Impact of heavy-tailed noise on synthetic datasets. With- out gradient noise, Avg-SGD achieves good performance (c.f., (a)). As the noise tails grow heavier (from (a) to (d)), the performance of Svg deteriorates considerably. By contrast, both clipping mechanisms and adaptive updates demonstrate improved perfor- mance learning the ground truth w.. and effectively miligates the adverse effects of heavy-tailed noise. BiClip as the inner optimizer outperforms other options (Adam, CzClip, and SGD) with haived nose (sec (d)). See Appendix D.I for full results.
6

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Table 1:
Test results on the GLUE Benchmark. Metric descriptions are given in Appendix D.3, and the full results are reported as Table 3 in the appendix, Entries marked with 0.0 indicate failure to learn. Top first, second, and third best- best-peerorming algorithms are highlighted. For Adam", 2, preconditioners are transmitted between the inner and outer optimizers, whereas DiLoCo requires maintaining preconditioners on the inner optimizers, both of which incur significant communication or memory overhead than Br Clip. Our experiments show that Bid Clip achieves the best performance with the smallest overhead.
Algorithm
MNLI
QNLI
QQP (Acc/F1)
RTE
SST-2
MRPC (Acc/F1)
CoLA
STS-B (S/P)
Average
Avg-SGD (McMahan al., 2017)
81.13
83,21
78.71/78.69
57.40
90.94
67.30/80.52
0.0
26.76/28.20
61.17
Avg-LzClipp (Yang et al., 2022)
81.82
85.68
80.00/79.82
54.51
91977
68.38/81.22 .22
0.0
41.27/40.96
64.15
Avg-Adagrad
84.70
88.79
87.09/83.34
64.26
93.34
71.56/82.66 63
27.72
81.93/81. 1.26
76.97
Avg-Adam
84.97
89.47
87. 87.66/84.09
64.62
93,80
81.86/87.74
41.41
86.21/86.55
80.76
Avg-BiClip
85.08
89.45
87.83/84.12
66.06
94.03
71.32/82.45
41.40
84.08/84.48
79.12
Adagrad-SGD (Reddi al., 2021)
82,40
86.61
82.51/77.66 6.6
71.48
92.08
85.53/89.52
47.80
40.37/42.24
72.69
Adagrad-BiClip
85,54
90,02
88, 68.66/85.05
73.36
93.23
85.78/89.86
48.87
84.03/85.90
82.75
RMSProp-SGD (Reddi et al., 2021)
84,20
88,46
87.12/83.30
72.56
91.85
85.50/89.17 .17
52.39
45.72/41880
74.73
RMSProp-BiClip
85.56
89.82
88. 50/50084.44
70.75
93.69
80/880889 92
50.99
87 87.65/87.79
82,99
Adam-SGD (Reddi et al., 2021)
82.93
86.98
85. 99/99998
66.78
90.71
87.01/90.09
49.93
44.48/41.22
73.37
Adim
82.54
86.69
85. 88/8870777
59,92
89.67
85.29/89.90 90
48.54
69. 19919/67.16
76.86
Adam-BiClip
84,26
89.20
88.64/84.74
69.67
92.43
86.52/90.09
56.12
82.83/79.71
82,20
Adam² (Wang al., 2021b)
85.11
88,87
89. 89.04/85.51
71.48
92.66
87.50/91.03
52.70
84.47/83.82
82,93
DiLoCo (Douillard et al., 2024)
85.68
89.87
88.78/85.19
67.87
91.89
87.99/91.20
54.77
85.93/84.76
83.08
CiClipp
85.06
89.73
84.93/83.97
76.53
93.80
89.21/92.44
60.08
87.07/86.89
84.52
We designed our convex, synthetic dataset setup to explicitly control and inject heavy-tailed noise, enabling a focused study of its effects. In language tasks, the frequencies of words or tokens typically follows heavy-tailed distribution, where a small subset of tokens occurs with high frequency, while the majority appear infrequently yet carry significant contextual information. To mirror this phenomenon, emu- lating a similar setup in Li et al. (2022), we partitioned the input feature space into common and rare features. Specifi- cally, we set the first p- 10% features (or tokens) from data X common features, with each feature activated accord- ing to a Bernoulli distribution (0r9.. The remaining 90% of the features are configured as rare, each sampled from (orn(..1). The weight vector w, is drawn from a standard multivariate normal distribution, w. ~ (O, Jm), and the labels are generated as ÿ = Xw,, + Enoise: A neu- ral network with model weight úē is then trained to learn the ground truth w.. A comprehensive explanation of the dataset construction and experimental setup is provided in Appendix D.I. We inject noise Énoise sampled from a heavy- tailed distribution, which implies that the induced stochastic gradients must be heavy-tailed under the MSE loss. In Figure 1, we sample from the Gaussian and Student t dis- tributions for the non-heavy-tailee and heavy-tailed Enoises respectively. By default, we multiply the noise by scale unless otherwise specified.
6.2. Transformer Encoders
To evaluate the effectiveness of our approach, we finetune RoBERTa (Liu et al., 2019) on the General Language Un- derstanding Evaluation (GLUE) benchmark (Wang et al., 2019), a widely-used suite of natural language understand- ing tasks. The GLUE benchmark includes diverse tasks such as sentiment analysis, sentence similarity, textual entailment, and natural language inference, providing a comprehensive evaluation of model performance across multiple linguis- tic phenomena. We follow standard finetuning protocols for RoBERTa, leveraging pretrained weights and optimiz- ing task-specific objectives for each dataset in GLUE. Our results demonstrate that BiClip (B:2Clip) attains compet- itive or superior performance similar to Adam (Adam²), while only requiring SGD-like memory and compute.
Table presents the performance of the algorithms of inter- est on the GLUE benchmark. Our results show that CzClip enhances performance on real-world data. Adaptive meth- ods further improve upon these results, consistently out- performing LyClip (c.g., convergence curves in Figure 2). Notably, the newly proposed clipping method in TailOPT, BiClip, demonstrates superior performance compared to L2Clip and, in some cases, even surpasses Adam during test time (c.f., comparing BipClip and Adam?), highlight- ing its potential as an efficient and effective optimizer in real-world applications. Additionally, instantiations of Tai- IOPT achieving 80% average accuracy generally em- play adaptive or addativveapproxximatin optimizers across all nodes. In particular, adaptivity on the inner optimizer appears crucial for performance, as SGD-based methods perform considerably worse (< 75%). By contrast, both BiClip or Adam reach 80% even when combined with a
We observe that while SGD demonstrates strong perfor- mance in non-noisy settings, its effectiveness diminishes as noise tails become heavier-a scenario where adaptive methods and BiClip excel. Similarly, L2Cliip shows some ability to mitigate heave- noise but exhibits compa- rable decline in performance under htave- conditions.
7

---

Efficient Distributed Optimization under Heavy-Tailed Noise
0.9
0.9
Test Accuracy
0.88
Test Accuracy
Test. Accuracy
0.8-
0.8
0.7
0.7
0.7
LgClop
0.6
Ang SGD
Ang
0.6
Adan?
Avg Lgp
Adum SGD
Adam- DiClopp
Adem L,CNip
Adora
BPCCiip
0.5
0.5
0.5
10
2
10
10
Onter Node Steps
Outer Node Steps
Outer Node Steps
(a) Effects L2 clipping
(b) Effects of Adaptivity
(c) Effects of BiClip
Figure 2: Convergence curves on the QNLI dataset. In (a), we see that L2Clip (one option of ('lallp) can help to improve performance under different outer optimizers. Middle Figure (h) demonstrates that adaptivity also helps to mitigate the negative effects heavy-tailed noise. In all three plots (a)-(c), Clip performs worse than adaptive methods, but the coordinate-wise BiClip optimizer performs comparably or even better than adaptive optimization frameworks, manifesting Adam-like performance. We note that the Adam haseline, which applies Adam both in inner and outer optimization, requires transmitting preconditioners of the same size the model weights inner optimizers. resulting substantial communication memory overhead to deploy. By contrast, Bi Clip removes necessity preconditioner maintenance, sidestepping this bottleneck entirely.
simple averaging outer optimizer strategy. We include full results of more baselines in Appendix D.3.
aiming to utilize mimic adaptivity in both the inner and outer optimizers generally achieve superior results, surpass- ing 80% average performance across all benchmarks, No- tably, performance is highly sensitive to the choice of inner optimizers, with SGD and L2 clipping yielding the lowest results. For machine translation, however, the performance variance across different optimizer strategies can be rela- tively smaller when optimal hyperparameters are selected.
6.3. Generative Models
We also evaluate Таi on machine translation tasks uti- lizing the WMT datasets, widely used benchmark for translation research (Foundation, 2019). Specifically, we finetune the T5 (Raffel et al., 2020) generative model on the TED Talks and News Commentary parallel training datasets. The TED Talks dataset, originally sourced from IWSLT 2017 (Cettolo et al., 2017), comprises multilingual transla- tions of TED Talk transcripts, while the News Commentary dataset includes parallel text from news articles across vari- ous languages. We report both BLEU and METEOR scores across several variants of source and target language trans- lations in Table 2. An expanded table with more extensive evaluation provided in Table in the appendix.
We observe that Bi some settings. While its design aims to emulate adaptiv- ity under heavy-tailed noise, BiClip exhibits characteris- ties that can interpolate between non-adaptive and adaptive methods, capturing benefits from both without necessar- ily fully belonging either paradigm (Figure 5 in the ap- pendix). Further, BiClip retains the same memory and com- pute overheads as standard SGD, which cements highly resource-efficient adaptive approximation.
outperform even Adam 2 in
In addition, federated learning is a special distributed learn- ing paradigm designed to train machine learning models jointly without the transmission of raw data (McMahan et al., 2017: et al., 2020a; Wang et al., 2021a). TailOPT can also be applied to federated learning with limited client participation, especially when the local data shards induce heavy-tailed stochastic gradients. See Appendix D.5 for experiments on effects of TailOPT in this setting.
Table 2: Evaluation results machine translation benchmarks. Metrics reported are formatted as BLEU/METEOR for various language pairs across the TED and News Commentary datasets. The final column represents the average score across all metrics for each algorithm See Table 4 for expanded results.
Algorithm TED (en-de)
NewsComm (en-fr)
Avg
Avg-SGD
28.02/58.52
30.07/54.13
42.68
Avg-LaClip
28.99/58.94
31.02/56.73
43.92
Adam?
28. 28.06/58.0s
30.97/55.85
43.23
BiC
19.41/59.18
31.79/57.69
44.51
6.4. BiClip for Centralized Learning
While we focus on modern distributed settings, the BiClip optimizer itself can be readily used in centralized learning with similar benefits- -cchieiiiaaciiiinnggg Adam-like performance without maintaining any gradient statistics. We empiri- cally demonstrate the convergence and test performance of BiClip compared with SGD and Adam on both text and
For language reasoning benchmarks, the per- formance differences across algorithmic instantiations are particularly pronounced. While L2 clipping is a common stabilization strategy, exhibits limited effectiveness. In contrast, coordinate-wis. BiClip demonstrates significantly better stability and performance. Moreover, frameworks
Discussions.
8

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Qwen22:5 SQuAD
VIT CIFARI00
Impact Statement
This paper presents work whose goal is to advance the field of machine learning. As our work primarily focusing on optimization algorithms, we do not believe that there are many potential societal consequences of our work.
Texl Accurccy
Tesl Ascurasy
22-
SGD
Adax
References
Train Steps (10")
Tain Supps (10")
Ahn, K., Cheng, X., Song, M., Yun, C., Jadbabaie, A., and Sra, S. Linear attention is (maybe) all you need (to understand transformer optimization). International Conference on Learning Representations, 2024.
Figure 3: Effects of BiClip in centralized training. We see that BiClip (only relying on clipping thresholds) achieves the same accuracies and convergence speed as Adam without main- taining any preconditioners or their compressed versions.
Anil, R., Gupta, V., Koren, T., and Singer, Memory efficient adaptive optimization. Advances in Neural In- formation Processing Systems, 32, 2019.
image datasets. We finetune Qwen2.5 (Yang et al., 2025) on the SQuAD dataset (Rajpurkar et al., 2016). and finetune ViT-base model (Dosovitskiy et al., 2021) (pretrained ImageNet) CIFAR (Krizhevsky et al., 2009). We use the same hyperparameter tuning protocol as in other experi- ments, discussed in Appendix D.7. In Figure 3, we see that both BiClip and Adam outperform SGD on two tasks in terms final accuracies and/or convergence speed, whereas BiClip only requires the same memory and compute as SGD, which is significantly more efficient than Adam.
Caldas, S., Duddu, S. M. K., Wu, P., Li, T., Konecny, J., McMahan, H. B., Smith, V., and Talwalkar, A. Leaf: A benchmark for federated settings. Arxiv, 2018
Cettolo, M.. Federico, M., Bentivogli, L., Nichues, J.. Stuker, S., Sudoh, K., Yoshino, K., and Federmann, C. Overview of the iwslt 2017 evaluation campaign. Pro- ceedings of the 14th International Conference on Spoken Language Translation, 2017.
Chen, X., Wu, Z. S., and Hong, M. Understanding gradient clipping in private sgd: A geometric perspective. Ad- vances in Neural Information Processing Systems, 2020.
7. Conclusion
In this work, we have introduced TailOPT, a framework for efficient heavy-tailed optimization. We have proposed the BiClip optimizer based on coordinate-wiz clipping from above and below, which utilizes nearly identical mem- ory and compute resources vanilla SGD yet manifests Adam-like performance. We have established convergence guarantees for our TalOOPT under potentially unbounded variance and provide a thorough empirical evaluation with real-world as well as synthetic datasets. Our experiments indicate that BiClip stabilizes training under heavy-tailed noise and achieves the benefits of efficient adaptive opti- mization, exceeding the state-of-the-art performance.
Chezhegov, S., Klyukin, Y., ndrei Semenov, Beznosikov, A.,
Gasnikov, A., Horvath, S. S., Takac, M., and Gorbunov, E. Gradient clipping improves adagrad when the noise is heavy-tailed. ArXiv, 2024a.
Chezhegov, S., Klyukin, Y., Semenov, A., Beznosikov, A..
Gasnikov, A., Horváth, S., Takac, M., and Gorbunov, E. Gradient clipping improves adagrad when the noise is heavy-tailed. Arxiv, 2024b.
Cutkosky, A. and Mehta, H.
bounds for non-convex stochastic optimization with heavy tails. Ad- vances in Neural Information Processing Systems, 2021.
Future work could explore automatic selection of and de based on initial statistics or bespoke estimators, which could provide more practical solutions. Alternatively, allowing the clipping thresholds to vary depending on coordinate parti- tion subsets (e.g., across tensor slices) may further enhance performance. An extended conclusion with possible future directions is provided in Appendix B.
Das, A., Nagaraj, D. M., Pal, S., Suggala, A., and Varshney, P. Near-optimal streaming heavy-tailed statistical estima- tion with clipped sgd. Advances in Neural Information Processing Systems, 2024.
Davis, D., Drusvyatskiy, D., Xiao, I.., and Zhang, J. From low probability to high contidence in stochastic convex optimization. Journal of Machine Learning Research, 22: 1 1-38, 2021.
Acknowledgements
We thank anonymous reviewers for their feedback. We are grateful to Xiyuan Yang for valuable discussions and contributions Section 6.4 of this paper.
DeepSeek-AL Deepseek-v3 v3 technical report. ArXiv, 2024.

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Dehghani, M., Djolonga, J., Mustafa, B., Padlewski, P., Heek, J., Gilmer, J., Steiner, A. P., Caron, M., Geirhos, R., Alabdulmohsin, I., Jenatton, R., Beyer, L.,, Tschan- nen, M., Arnab, A., Wang, X., Ruiz. C. R., Minderer, M., Puigcerver, J., Evci, U., Kumar, M., Steenkiste, S. V., Elsayed, G. F., Mahendran, A., Yu, F., Oliver, A., Huot, F, Bastings, J., Collier, M., Gritsenko, A. A., Birodkar, V. Vasconcelos, C. N.. Tay, Y., Mensink, T., Kolesnikov, A., Pavetic, F., Tran, D., Kipf, T., Lucic, M., Zhai, X., Keysers, D., Harmsen, J. J., and Houlsby, N. Scaling vi- sion transformers to 22 billion parameters. International Conference on Machine Learning, 2023.
High-probabie probbbbbbbbbitty convergence for composite and dis- tributed stochastic minimization and variational inequali- ties with heavy-tailed noise. International Conference on Machine Learning. 2024b.
Jaghouar, S., Ong, J. M., and Hagemann, J. Opendiloco:
An open-source framework for globally distributed low- communication training. ArXiv, 2024.
Juditsky, A., Nazin, A., Nemirovsky, A., and Tsybakov, A. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80:1607-1627, 2019a.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenbom, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M.. Heigold, G., Gelly. S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. International Conference on Learning Representations, 2021.
Juditsky. A., Nazin, A., Nemirovsky, A., and Tsybakov, A. A Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 2019b.
Kalra, D. S. and Barkeshli, M. Why warmup the learning rate? underlying mechanisms and improvements. Ad- vances in Neural Information Processing Systems, 2024.
Douillard, A., Feng, Q., Rusu, A. A., Chhaparia, R., Donchev, Y., Kuncoro, A.. Ranzato, M., Szlam, A., and Shen, J. Diloco: Distributed low-communication train- ing of language models. ICML Workshop on Advancing Neural Network Training, 2024.
Karimireddy, S. P., Jaggi, M., Kale, S., Mohri, M., Reddi, S., Stich, S. U., and Suresh, A. T. Breaking the centralized barrier for cross-device federated learning. Advances in Neural Information Processing Systems, 2021.
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
Khirirat, S., Gorbunov, E., Horváth, S., Islamov, R., Karray, F., and Richtarik, P. Clip21: Error feedback for gradient clipping. ArXiv, 2023.
Foundation, W. Shared task: Machine translation of news. Association for Computational Linguistics Conference on Machine Translation, 2019.
Kingma, D. P. and Ba, J. Adam: A method for stochas- tic optimization. International Conference for Learning Representations, 2015.
Gehring, J., Auli, M., Grangier, D., Yarats, D., and Dauphin, N. Convolutional sequence to sequence learning. In- ternational Conference on Machine Learning, 2017.
Koloskova, A., Hendrikx, H., and Stich, S. U. Revisiting gradient clipping:
Stochastic bias and tight convergence guarantees. International Conference on Learning Repre- sentations, ArXiv, 2023.
Gorbunov, E., Danilova, M., and Gasnikov, A. Stochas- tic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Pro- cessing Systems, 2020.
Kosson, A., Messmer, B., and Jaggi, M. Analyzing and reducing the need for learning rate warmup in gpt train- ing. Advances in Neural Information Processing Systems, 2024.
Gorbunov, E., Danilova, M., Dobre, D., Dvurechensky, P., Gasnikov, A., and Gidel, G. Clipped stochastic methods for variational inequalities with heavy-tailed noise. Ad- vances in Neural Information Processing Systems, 2022.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Gorbunov, E., Danilova, M., Shibaev, I., Dvurechensky, P., and Gasnikov, A. high--robbbillty complexity bounds for non-smooth stochastic convex optimization with heavy- tailed noise. Journal of Optimization Theory and Appli- cutions, 2024a.
Kunstner, F., Yadav, R., Milligan, A., Schmidt, M., and Bietti, A. Heavy-tailed class imbalance and why adam outperforms gradient descent on language models. ArXiv, 2024.
Lee, S. H., Sharma, S., Zaheer, M., and Li, T. Efficient adaptive federated optimization. ICML Workshop on Advancing Neural Network Training, 2024.
Gorbunov, E.., Sadiev, A., Danilova, M., Horvath, S., Gidel, G., Dvurechensky, P., Gasnikov, A., and Richtarik,
10

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Li, S. and Liu, Y. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. International Conference on Machine Learning, 2022.
Menon, A. K., Rawat, A. S., Reddi, S. J., and Kumar, S.
Can gradient clipping mitigate label noise? International Conference on Learning Representations, 2020.
Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Feder- ated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60) 60, 2020a.
Merity, S., Keskar, N. S., and Socher, R. Regularizing and optimizing Istm language models. International Confer- ence Learning Representations, 2018.
Mikolov, T. Statistical language models based neural networks. Ph.D. thesis, Brno University of Technology, 2012.
Li, T., Zaheer, M., Reddi, S. J., and Smith, V. Private adap- tive optimization with side information. International Conference on Machine Learning, 2022.
Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. L. High probability convergence of clipped-sgd under heavy- tailed noise. Arxiv, 2023a.
Li, T., Zaheer, M., Liu, Z., Reddi, S., McMahan, B., and Smith, V. Differentially private adaptive optimization with delayed preconditioners. International Conference on Learning Representations, 2023.
Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. L. Improved convergence in high probability of clipped gra- dient methods with heavy tailed noise. Advances in Neu- ral Information Processing Systems, 2023b.
Li, X., Huang, K., Yang, W., Wang, S., and Zhang, Z. On the convergence of fedavg on non-iid data. International Conference on Learning Representations, 2020b.
Nguyen, T. H., Simsekli, U., Gurbuzbalaban, M., and Richard, G. First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise. Advances in Neural Information Processing Systems, 2019.
Liu, B., Chhaparia, R., Douillard, A., Kale, S., Rusu, A. A., Shen, J.. Szlam, A., and Ranzato, M. Asynchronous local- sgd training for language modeling. ICML Workshop on Advancing Neural Network Training, 2024a.
Parletta, D. A., Paudice, A., Pontil, M., and Salzo, S. High probability bounds for stochastic subgradient schemes with heavy tailed noise. SIAM Journal on Mathematics of Data Science, 6:953 2024.
Liu, M., Zhuang, Z., Lei, Y., and Liao, C. A communication- efficient distributed gradient clipping algorithm for train- ing deep neural networks. Advances in Neural Informa- tion Processing Systems, 2022.
Peters, M. E., Neumann, M., Iyyer. M., Gardner, M., Clark, C., Lee, K., and Zettlemoyer, L. Deep contextualized word representations. International Conference on Learn- ing Representations, 2018.
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V. Roberta: A robustly optimized bert pretraining approach. Arxiv, 2019.
Puchkin, N., Gorbunov, E.,, Kutuzov, N., and Gasnikov, A. Breaking the heavy-tailed noise barrier in stochastic optimization problems. AISTATS, 2024.
Liu, Z., Zhang, J., and Zhou, Z. Breaking the lower bound with (little) structure: Acceleration in non-convex stochas- tic optimization with heavy-tailed noise. Proceedings of Thirty Sixth Conference on Learning Theory, 195:2266- 2290, 2023.
Qian, J., Wu, Y., Zhuang. B., Wang, S., and Xiao, J. Under- standing gradient clipping in incremental gradient meth- ods. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, 2021.
Liu, Z., Zhao, C., landola, F., Lai, C., Tian, Y., Fedorov, I., Xiong, Y., Chang, E., Shi, Y., Krishnamoorthi, R., Lai, L., and Chandra, V. Mobilellm: Optimizing sub-billion parameter language models for on-device use cases. In- ternational Conference on Machine Learning, 2024b.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W. and Liu, J. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 2020.
Ma, J. and Yarats, D. On the adequacy of untuned warmup for adaptive optimization. Association for the Advance- ment of Artificial Intelligence, 2021.
Rajpurkar, P., Zhang, J., Lopyrev. K., and Liang, P. Squad: 100,000+ questions for machine comprehension of text. 2016.
arXiv preprint
McMahan, B., Moore, E., Ramage, D.,. Hampson, S., and Arcas, B. A. Communication-efficiia. learning of deep networks from decentralized data. In International Con- ference on Artificial Intelligence and Statistics, 2017.
Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konecný, J., Kumar, S., and McMahan, B. Adaptive feder- ated optimization. International Conference on Learning Representations, 2021.

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Rosa, G. M., Bonifacio, L.,, Jeronymo, V., Abonizio, H., Lotufo, R.,, and Nogueira, R. Billions of parameters are worth more than in-domain training data: A case study in the legal case entailment task. ArXiv, 2022.
Wang, J., Charles, Z., Xu, Z., Joshi, G., McMahan, H. B., Al-Shedivat, M., Andrew, G., Avestimehr, S., Daly, K., Data, D., et al. A field guide to federated optimization. 2021a.
arXiv preprint arXiv:2107.068:
Sadiev, A., Danilova, M., Gorbunov, E.,, Horvath, S., Gidel,
Wang, J., Xu, Z., Garrett, Z., Charles, Z., Liu, L.,, and Joshi, G. Local adaptivity in federated learning: Conver- gence and consistency. arXiv preprint arXiv:2106.02300 2021b.
G., Dvurechensky, P., Gasnikov, A., and Richtarik, P. High- probaabbbbbb bounds for stochastic optimization and variational inequalities: the case of unbounded variance. International Conference Machine Learning, 2023.
Wang, Y., Lin, L., and Chen, J. Communication--fffiieee adaptive federated learning. International Conference on Machine Learning, 2022.
Simsekli, U., Sagun, L.,, and Gurbuzbalaban, M. A tail-index analysis of stochastic gradient noise in deep neural net- works. International Conference on Machine Learning, 2019.
Wu, C., Zhang, H., Ju, I.., Huang, J., Xiao, Y., Huan, 7.,, Li, S., Meng, F., Liang, L., Zhang, X., et al. Rethinking memory and communication cost for efficient large lan- guage model training. arXiv preprint urXiv:2310.06003 2023.
Simsekli, U., Zhu, L., Teh, Y. W., and Gurbuzbalaban, M. Fractional underdamped langevin dynamics: Retargeting sgd with momentum under heavy-tailed gradient noise. International Conference on Machine Learning, 2020.
Xie, C., Koyejo, O., Gupta, I., and Lin, H. Local adaalter: Communication-efficiii stochastic gradient descent with adaptive learning rates. OPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2020.
Smith, V., Forte, S., Ma, C., Takáč, M., Jordan, M. I., and Jaggi, M. Cocoa: A general framework for caamuunicatioo-fffcienn distributed optimization. Jour- nal of Machine Learning Research, 18(230):1-49, 2018.
Yang, A., Li, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Gao, C., Huang, C., Lv, C.,, et al. Qwen3 technical report. arXiv preprint arXiv:2505. 250.055800088, 2025.
Sriram, A., Das, A., Wood, B. M. Goyal, S., and Zitnick, L. Towards training billion parameter graph neural net- works for atomic simulations. International Conference on Learning Representations, 2022.
Yang, H., Qiu, P., and Liu, J. Taming fat-tailed (heavier- tailed with potentially infinite variance) noise in federated learning. Advances in Neural Information Processing Systems, 2022.
Stich, S. U. Local sgd converges fast and communicates little. arXiv preprint vrXiv:880.009667 2018
Yu, C., Tang. H., Renggli, C., Kassing, S., Singla, A., Al- istarh, D... Zhang, C., and Liu, J. Distributed learning over unreliable networks. In International Conference on Machine Learning, pp. 7202-7212. PMLR, 2019.
Streeter, M. and McMahan, B. Less regret via online condi- tioning. ArXiv, 2010.
Sun, C. and Chen, B. Distributed stochastic strongly con- vex optimization under heavy-tailed noises. 2024 IEEE International Conference on Cybernetics and Intelligent Systems (CIS) and IEEE International Conference on Robotics, Automation and Mechatronics (RAM), 2024.
Yu, S., Jakovetic, D., and Kar, S. Smoothed gradient clip- ping and error feedback for decentralized optimization under symmetric heavy-tailed noise. Arxiv, 2024.
Zhang, B., Jin, J., Fang, C., and Wang, L. Improved analysis of clipping algorithms for non-convex optimization. Ad- vances in Neural Information Processing Systems, 2020a.
Sun, Y., Shen, L., Sun, H., Ding, L., and Tao, D. Efficient federated learning via local adaptive amended optimizer with linear speedup. IEEE Transactions on Pattern Analy- sis and Machine Intelligence, 45(12): (5(11):14433-1111 1444-14644, 2023.
Zhang, J. and Cutkosky, A. Parameter-free regret in high probability with heavy tails. Advances in Neural Infor- mation Processing Systems, 2022.
Wang, A., Singh, A., Michael, J., Hill, F., Levy, O.,, and Bowman, S. R. Glue: A multi-task benchmark and analy- sis platform for natural language understanding. Interna- tional Conference for Learning Representations, 2019.
Zhang, J., Karimireddy, S., Veit, A., Kim. S., Reddi, S.,
Kumar, S., and Sra, S. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 2020b.
Wang, J., Liu, Q. Liang, H., Joshi, G., and Poor, H. V. Tack- ling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, 2020.
Zhang, X., Bu, Z., Wu, Z. S.,, and Hong, M. Differentially private sgd without clipping bias: An frror-feedback ap- proach. International Conference on Learning Represen- tations, 2024.
12

---

Efficient Distributed Optimization under Heavy-Taile Noise
Contents
Additional Related Works
14
Future Directions and Possible Extensions
15
Convergence of TailOPT
15
C.1 Convergence of Avg-LyClip
15
C.2 Dynamics of Avg-L under Failing Compute Nodes
21
C.3 Convergence of Bi²Clip
24
C.4 Convergence of Adagrad-TaalCllip
27
C.5 Convergence of RMSProp-Taill
31
C.6 Convergence of Adam-TailClipp
33
D Experiment Setup & Full Results
39
D.1 Convex Models
39
D.2 Synthetic Data Experiments Discussion
40
D.3 Transformer Encoders
................................
41
D.4 Generative Models
42
D.5 Performance under Non-IID Data
43
D.6 Gradient Distributions
44
D.7 Hyperparameter Sweep Grids
45
D.8 Optimal Hyperparameters.
46
13

---

Efficient Distributed Optimization under Heavy-Tailed Noise
A. Additional Related Works
Clipping for Stabilizing Training Dynamics. Due to its success in stabilizing model updates, gradient clipping has been extensively studied empirically (Gehring et al., 2017: Merity et al., 2018; Peters et al.. 2018; Mikolov, 2012) and theoretically (Chezhegov et al., 2024a; Zhang et al., 2020b; Menon et al., 2020; Zhang et al., 2020a; Chen et al., 2020; Koloskova al., 2023; Gorbunov et al., 2020; Cutkosky & Mehta, 2021). The majority of results study the centralized setting (e.g., Liu et al., 2023; Zhang & Cutkosky, 2022; Parletta et al., 2024; Li & Liu, 2022; Puchkin et al., 2024; Nguyen et al., 2023b; Gorbunov et al., 2024a). Additionally, it was shown that using constant clip threshold can induce gradient bias, preventing the algorithm from ever converging (Koloskova et al., 2023; Chen et al., 2020). Therefore, some works have attempted to circumvent this issue by debiasing via error feedback (Khirirat et al., 2023; Zhang et al., 2024). Other works in distributed optimization have imposed strong distributional stochastic gradient structures in the analysis. For instance, Qian al. (2021) assume a well-behaved angular dependence between the stochastic and deterministic gradients throughout training, and Liu et al. (2022) assume symmetric gradient noise, almost surely bounded stochastic gradients, as well as homogencous data. In contrast with these works, we do not impose any conditions on the noise nor data distributions except for bounded noise a-moments for a E (1, This also sharpens the sensitivity of our bounds to gradient distributions, as a may be selected as the minimal (or close to infimum) a-moment value such that the moment is bounded.
There are some recent results studying the dynamics of heavy-tailed clipped- in the distributed setting, without local updates (Sun & Chen, 2024; Gorbunov et al., 2024b; Yu et al., 2024). In particular, Sun & Chen (2024) study the convergence of distributed clipped-sgd for strongly-convex objectives in the absence of central server, where smaller nodes communicate with their neighbors according to a strongly connected graph. By contrast, Yu et al. (2024) propose 'smooth--lipping' the difference between local gradient estimator and the local stochastic gradient, which is shown to converge under only the integrability condition (finite first moment) for strongly convex objectives when assuming symmetric noise distributions. The work by Yang et al. (2022) studies L2 clipping with local updates (compared against in our paper as the 'Avg + L2Clip' baseline in Table 1). Our proposed clipping mechanism, BiClip, fundamentally differs from these approaches by incorporating coordinate-win wise clipping from both above and below, bringing about benefits of adaptive optimizers. An added advantage of TailOPT is significant communication efficiency, as we do not transmit preconditioners from the inner and outer optimizers under iterative local updates. Our analysis covers both convex and non-convex functions without additional assumptions on the noise distribution except for heavy-tailedness with potentially unbounded variance. It also holds for variety of adaptive optimizers and different clipping methods.
Convergence Bounds under Heavy-Tailesd Gradient Noise. There are two primary types of convergence bounds: in- probability bounds (Juditsky et al., 2019b; Davis et al., 2021; Gorbunov et al., 2022: 2020; Sadiev et al., 2023; Cutkosky & Mehta, 2021; Gorbunov et al., 2024a;b) and in-expectation bounds (Wang et al., 2022; Li et al., 2020b; Reddi et al., 2021; Xie al., 2020; Wang et al., 2020; Karimireddy et al., 2021: Li et al., 2023; 2022). In-probability bounds provide an upper limit on the number of timesteps required to achieve model parameters such that P(M((z) S $) 2 1 - 5 for given evaluation metric/ M(x) (e.g., min F(z))). As 5 + 0+, the required communication complexity or number of timesteps may diverge. The key challenge is to mitigate this divergence as effectively as possible through novel algorithm designs or refined mathematical analysis, such as by deriving a polylogarithmic dependence on rather than a more severe inverse power-law dependence. A recent work (Sadiev et al., 2023) provides the first nigh-probabiine results under unbounded variance for clipped-SGD applied to star-convex or quasi-convex objectives in a distributed setting without local updates. Their analysis reveals inverse logarithmic dependence on the confidence level.
By contrast, en-exeectation bounds complement in- probabibiiiyyy bounds by ensuring that convergence to an optimal point is guaranteed under expectations, without confidence level. However, the majority of such analyses assume a bounded noise variance, typically denoted by an upper bound G (Gorbunov et al., 2020; Parletta et al., 2024; Li & Liu, 2022). Due to this dependence, some works (e.g., those studying high-probability results (Davis et al., 2021; Gorbunov et al., 2020; 2024a)) argue that in-expectation bounds are insensitive to the underlying distributional structures of the stochastic gradients, due being compressed or approximated away by G. Relaxing this assumption is particularly challenging because unbounded noise adds significant uncertainty to controlling model updates. Furthermore, works such as (Lee et al., 2024) have demonstrated that under stochastic gradient descent, unbounded noise is instantaneously transmitted to the model parameters in both centralized and distributed settings, leading to instability and divergence in expectation. Such results elucidate the additional difficulties induced by efforts to remove the bounded gradient condition. In this paper, we develop a more efficient and general ТаilOPT framework, and study the dynamics of TailOPT under heavy-tailed stochastic gradient distributions. Specifically, we provide the in-expectation convergence guarantees under infinite variance and local
14

---

Efficient Distributed Optimization under Heavy-Tailed Noise
updates for potentially non-convex functions, offering new bounds that are more sensitive distributional structures of minibatch noise.
B. Future Directions and Possible Extensions
Efficient and effective tuning of the clipping thresholds d; and un in BiClip remains an open avenue for research. One potential approach is to segment the thresholds into coordinate subsets (e.g., row-wise or column-wise), similar to the memory -effeceeffficinttt partitioning strategies employed in approximate optimizers such as SM3 (Anil et al., 2019). Alternatively, autonomous selection of ut and de based on initial statistics or bespoke estimators could provide practical solutions. Our experiments indicate that coordinate- wise BiClip, rather than standard L2 clipping, achieves the benefits of adaptive optimization without incurring any additional memory overhead compared to SGD. Notably, methods like Adam at least double memory usage, whereas BiClip maintains parity with non-adaptive methods, This suggests that uniformly amplifying small updates can contribute to optimization efficiency. Furthermore, layer-wise BiClip can be readily generalized, with proofs extending naturally.
Another intriguing direction for future research is the integration of Adam on top of BiClip to enhance optimization stability in either centralized or distributed training. Notably, when employing the Adam optimizer, some studies apply L2 clipping to gradients prior to plugging in Adam updates to improve stability of the optimization dynamics (Chezhegov et al., 2024b). A natural extension of this approach is to substitute BiClip for L2 clipping before passing updates to the Adam adaptive optimizer. This modification could not only enhance stability but also potentially reduce dependence on the hyperparameters of Adam, offering a more robust optimization framework.
C. Convergence of TailOPT
In this section, we rigorously analyze the convergence of TailOPT under heavy-tailed noise, beginning with the case of Avg- La ClCpip to enhance readability before progressively advancing to more sophisticated TailOPT variants incorporating BiClip and other adaptive outer optimizers. We first establish the convergence proof for Avg-LyClip in Appendix C.I, which serves as the basis for subsequent analyses. The proof for Avg-I=2Clip studies a virtual history of model weights synthesized by inner optimizers, which is inaccessible in real-world settings except when the model updates are communicated to the outer optimizer. However, by analyzing the virtual history, we are able to attain convergence of moving average of accessible model weights to the optimum, which can be materialized in practice. In Appendix C.2, we extend this proof to settings with partial participation and failing compute nodes, examining the resulting dynamics under heavy-tailed noise. In Appendix C.3, we further generalize the analysis to the BiC instantiation, where BiClip is applied to both the inner and outer optimizers. Notably, Bi Clip encompasses wyg-BiClip as a special case under specific hyperparameter choices, which in turn subsumes AvgpL2Clip. Finally, in Appendices C.4, C.5, and C.6, we investigate the convergence properties of TailOPT when the outer optimizer is instantiated with Adagrad, RMSProp. and Adam, respectively.
C.1. Convergence of AvgiL
We aim to model contemporary, large-scale neural network training across multiple powerful compute nodes (datacenters or GPU clusters), in which data is typically preprocessed IID to optimize for training. However, for fullest generality, we conduct our theoretical analysis the more challenging, non-lID setting. Our setup identical to Section 3, with some added notation. We denote x² to represent the global optimum of F(x) with a minimum value F F F(x*). and additionally, we let xt be the global optimum of (x( = E&g (x,, with minimum value F F(x)).
For model weight or stochastic gradient averages, we use the following notation
N
N Pro 0 9t Σ p: Clip(c,, Fi, (ef.o.si,)) Clip(c,u) == min 1,, |lvll y-
Σ
The use of the notation æñ., instead of xt carefully reflects the flow of the proof, which studies a 'virtual synchronization' of the model weights synthesized by the inner optimizer at each time t E [T'] (see Algorithm 2). In other words, we first analyze the virtual average T, which is not materially realized except at outer optimizer synchronization steps, before modifying the proof to procure a moving average of weights which is solely dependent on those communicated to the outer optimizer, which can now be obtained.
15

---

Efficient Distributed Optimization under Heavy-Tailed Noise
We now present some assumptions used in the convergence analysis for this section. We take the model weight projection domain be X' B(0, B) IRd where B(0, B) is the closed ball centered at the origin with radius B. Clearly, B 0 needs to be large enough to contain x² z X' for convergence. However, we note that the convergence analysis holds for X' any large enough compact, convex set.
Assumption 3 (u-strong convexity). For all 2, y X and e [NT, F((x) satisfies F((2) 2 F((1) (r y. VF(()) + /4||æ //
Gradient clipping is widely adopted technique to stabilize model updates by mitigating the impact of large gradients (Menon et al., 2020; Zhang et al., 2020a; Chen et al., 2020; Koloskova et al., 2023). The Clip(-) operator rescales the gradient uniformly to ensure it remains below predefined threshold. This procedure is mathematically equivalent to applying a dynamically adjusted, lower learning rate when large stochastic gradients are encountered. Another related technique projection, which operates the model weight space rather than the gradient space, effectively stabilizing the model parameters themselves instead of acting on the updates. These observations motivate Algorithm 2, which may be interpreted as dynamically modulating the learning rates as well backtracking toward the model origin 0 when heavy-tailed stochastic gradient updates realized.
Algorithm 2 Avg-L
Require: Initial model Iı, learning rate schedule 7) clipping schedule et Synchronization timestep E 2, projection domain X
1: for t 1...., T do
2: for each node E [N]
3: Draw minibatch gradient 9h.0 = V Fe Si,0)
4:
24.0
1++ + =xi,0 Th Clip(ce.gio.
5: end for
6: if 1E z Z
[+1 Proix EEe . Vi E [N]
7: 24,0
8: end for
Theorem demonstrates that distributed Avg-LaClip converges in expectation under heavy-tailed noise, despite potential clipping-induced induced bias. We also offer the first proof demonstrating convergence under extension of these results to accommodate failing nodes for additional utility in Appendix C.2. To proceed with the analysis, we first provide proposition.
Proposition If Fx(x)) is p-strooggy convex (or L-smooth), then so is Fi(x, E) for the identical μ (or T.).
While clipping offers the benefit of stabilization, it introduces complexities that complicate the convergence analysis. In particular, clipping induces a non-zero bias on the stochastic gradients, rendering them to be no longer unbiased estimators of the true gradient. Furthermore, unlike previous analyses, our work also considers scenarios involving distributions with infinite variance, where the clipping bias is exacerbated by the presence of heavy tails. Despite these challenges, Theorem demonstrates that with appropriately chosen (increasing) clipping and (decreasing) learning rate schedules, convergence of Algorithm 2 is nevertheless attainable in expectation.
Theorem 3. Let Assumptions 1-3 hold, and the clipping threshold in Avg-In2lip (Algorithm 2) sutisfy = ezt for c >> O and 1/2 > 7 > O. Decay the learning rate with schedule =t((t+ + 1) for r > 2/p, where μ minse[[]] pL and = ma Lg. Then, we have for ăJ Er 21
(x)) + 1) that
F(TT) - F(x") S V, + 12
V + VA,
16

---

Efficient Distributed Optimization under Mlaay-Taiiled Noise
where
T22
1 (2 + 1)T(T++1) +1)
(M +
+
2
(M 2/r) 2a + (TT
e rzu + 1
3 (n 2/r) a)y + +
( +1)
11 27(1 - 2/r)T((T++ +1)
Here, we have used the notation
2L (F((z) - F((2))), a min ak
2 1
M
max LE
max Bk, B
kE[N]
RE[N]
2
where & is compact domain constructed by uniformly closed extension of X' with To2 distance Ei=1 rct"-1
Let us bound the distance between the averaged model weights xy and the global optimum x². Assume that t 2 Z. We consider the following function
Proof.
[(1) = ||0 - Projx (1e7/))))) + (1= Fz + megt + (Te
for which
(0()) = 2(x (Projx(Te- - Th.tt, - + Tegt + (T. - 7).g))
Now, consider the function
g(t) [(1 - t) Projx - -199)) + +tProxx
- It + me
By the projective property,
o(t) 2 Projx - 7/:tt) (xre m19e)l--
holds for t [0, 1] via convexity of X. Additionally, g(t)² meets its minimum at 0. Therefore, we have that dg(t)) 2 0 due to y() being quadratic with respect to t. Noting that f0(0) dg(())/dllc=o. we have that [(() is monotonically increasing for t 2 0, again due to properties of quadratic. Then, f(1) 2 f(0) gives that
[rrojx (z, 7.g.)) x= 11? I Ir, nh.r- x
Therefore, we may conclude
N
|e+1 - x x²
Σ
p: Projx (T. - Thgh)) - x²"
||rroxx (3. - 719))) - x='
< || niStt x² x²1 = 1| x= 11
21/1 (Te - xx' xx"9t) + 1/2 1!
1|T x² 1|2 2nt (Te - x² 9t VF 21/ (T, - ,", FF()))
A2
Ag
Note that the final inequality LHS < RHS also holds for i $ Z. In bounding A2, we aim derive term that decays [Z, x²1| by inducing coefficient (1 ēπ)) || x² 1|2 for some ē > 0 to be determined. By j--troon convexity of F(x),
F(x") 2 F(T,) (T, x,, (..))) + I1a"" - Izl1
= -F(()) - - 1/ |ل x0 - (T. I¹, VF(T.).
17

---

Efficient Distributed Optimization under Mlcayy-Tailed Noise
To bound A1, we consider conditional expectations
-2n (म+ x², [9d - VF( I 2mp |0 x² 11 (T,)))
where [:]
conditions on realizations up to time Unraveling definitions gives
E [oc]
VF(Ta) = 1 Σ
pr(F,[Clip(er, (P (R(( + V.(( - (T(()
N
Pr P:llBc(Cipppee VPr (,,)) (r, (1 Σ - (3)
[E[N]
SEIN]
ElClippe CellCCClpcc..VFccc.... (,,)) VF 0,0)) + Σ
P.LII - Tell.
ME[N]
SEIN]
where the second line used Jensen and triangle incquality, and the third line used L-smoothness as well as Jensen. Now, we note that clipping biases the expectation in A4, and we seek to ease out measure of the clipping bias. For this purpose, we quantify the a e-moment of the stochastic gradient:
V (x) + cho
E
2 (E, (VA + E. l(e 2 (1V]))))) + B
Here, have used the notation B; < for readability, but strictly speaking this is not identical to the B; given in Assumption 2 as := min 0g, Finally, the projection in each outer optimizer synchronization step ensures that the =ioo remain in a compact set &., Therefore, to bound gradients, we use L-smoothness and j-sttrong convexity of F; (x) as follows:
[V)(1 < L>> 2;
where of is the optimum of (x)). Then, convexity gives that
1 1| xz 112 F1(x) Fz(2))
2
from which we conclude
2L2 (F((c) P.(x;)) S M
2L (F((s)-B((2))
|VA())) S
max kE(N),rE P
(4)
Piecewise continuity of Fz() is clear due to the existence of VF((). Therefore,
E, VF.(ot,)) + st.ol < (M + B²)
2
Now, note that if || F <1,0)ll S ct, clipping has no effect in A4. Thus, we focus on the case ( (1o) > a Additionally, clipping only downscales each stochastic gradient by a scalar, which preserves direction. Therefore,
A4 E. [[[Clip(e, VF(el, (l,)) V (f,))) x (IVVA( (()) > ct)]
< E, [| ( x (IV 4)]
(5)
S E. VV (t /VF -V ( (IVVF(a st,0)l > c)] & (M 2 + BBa)c-a
Putting these inequalities together, obtain intermediary step for > 0:
A S 2nd Ft x" II((M B²)a--
Σ
PrLl| -
VE(N]
pame [T+ x² 112
Th pa
((M + B
L
Σ p:l1=f x. [E[N]
Thus, our next step is to ease out ||=5,0 - Eell = (n)) For this purpose, our intuition is that the drift in model weights from local updates are bounded by the update size, as well as by taking a maximum of local steps after global synchronization.
18

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Therefore, we naturally consider the timestep (L) of the latest synchronization round up and observe that if the random variable X = 24,0 F then E&g [X] z2 Ft,-- Noting that the variance of X is greater than its second moment, proceed as follows via telescoping:
Ex 111 Tzll
Pal Pall0% Σ
x11l
E&|1X
E
Σ
pillot.. Te.112
1=1
Σ
Pi
2i,0
Σ (-x
o + x²/) It,
(6)
i=te-1
Pi to 1)² max Th. CCippl,,, VFr oF
('E(t..t)
N P1d Ti, of = = q - 22 u.n
The final inequality was obtained by noting that To + 0+ monotonically from above and that 2 Ct-1. The above
holds for all E Zzo. as if t is synchronization step, Eg | - xzll = 0. The final inequality used that the monotonic near-harmonic decay of mh allows Te, I 4Tμ for u = (2 1)/2. Finally, by
N Σ
N
pa J
Σ Pi
Σ
pa I - 2t.011) )
from which we conclude
A1 S pame |
x²1
Tt 1|2+
((M + Ba a mczzuL)2
(7)
pa
now remains to bound A3. which can be done straightforwardly via Jensen:
N
A3 = nhe |19ell S Th
Σ
||Clip(e, VI, (zt,0: 610)) S n...
Collecting all inequalities gathered thus far gives the simple form
Te ((M" + + + mmezzL)) [.[| x² 111 s (1 - (1 a)m) [ - 11 21 (F(z.) - F(x))) + n +
paa
which under tower law of expectations is amenable to telescoping. Intuitively, we want to control the learning rate and form quadratically decaying average the LHS, which by Jensen and convexity will give desired near-optimal point. The rest is matter of carefully easing out rate schedule that enables averaging, which also converges. Rearranging gives
(n (1 a)a) Blllor x=1
1 Elll x0112
m 2
B[F(x:)) F(x*)=
2n
(8)
+ 2pa
((M + 33 + 2(M + ) 2-2 mmzuL + 2
Letting 7/. r/((t 1), 1 (T(z for 2/H, we have
(E(F(z,)) - LF(x*) < t(t -
Blliz, - x-11]] (t+ 1)t
B[[ - x11 + tmic
2
2
2
(9)
t (Ma+Ba)222 + 2(M Ba 2 2 + 2222)
+ 2ua
19

---

Efficient Distributed Optimization under Heavy-Tailled Noise
Setting ot = cl for 1/2 7 0, 0 gives after telescoping
E 21 1))
TC -1=1 122 + (M + 200 20: Σ (12-20)++1
F(x*)
T(T +1)
(1 (/-2//]T(T +1)
rzu(( + LB= 1
1² r² L 21=1 P
(M (/r/
( (/-2/r)((T+)
Standard integral bounds give
r22
(M* 219222211122 1)
F(x") S (2 + +1) (/r - 22hh + 1]T +1)
T(T+1)
r- B + (T
(p- (/r)( .)7 + 1) + 222
+1)
1 (/r) +1)
Finally, note that by Jensen and convexity, the left hand side is lower bounded by
0 S F(Tr) - F(x)) < Σ (x)( -F(x*) 1(
where žT = ET= 2tE[F///T(T + 1) is quadratically decaying average. This concludes the proof. It is straightforward to extend to the case in which the learning rate is scheduled to decay in each outer optimizer synchronization step instead of at each local step, by letting = r </[tt/=] + 1) in equation (8).
The value of the moment a has a significant impact on the convergence behavior. When a is close to 1, the convergence becomes substantially slower due to the heavy-tailed nature of the induced stochastic gradients and the increased variance they introduce. Conversely, when a approaches 2, the variance more controlled, leading to faster convergence rates, Importantly, our results demonstrate that even in the presence of infinite variance (i.e., a < 2). convergence can still be achieved, showcasing the robustness of the clipping approach under extreme heavy-tailed conditions.
The averages TV are virtual constructs used for theoretical analysis of Algorithm 2, which are not accumulated during the execution phase. That is, these quantities are only available at the outer optimizer synchronization steps, t E Zzo, and are not collected otherwise (as models are not saved for every local timestep prior to synchronization). As a result, the application of Avg-L2Clip creates a virtual history on the compute node models, where the aggregation of ephemeral model weights can theoretically induce convergence. However, practice, this conflicts with the use of local epochs for communication efficiency, necessitating adjustments to the convergence theorem. This leads to the development of Corollary 3.
Corollary 3. Let the conditions of Theorem 3 hold. Then, we have that
E F Eiez(t - ) (-relt--D)))
F(x*) < (T + 1)2
(11 + 1/2 + 2hs + th4),
Etez(t-1) (t-
2T)
where the vhs are defined as in the statement of Theorem 3 and Z is the set of all outer optimizer synchronization steps.
Proof. We may start with equation (9), where we use the same notation the proof of Theorem 3. Recall that 0 < F(x)= F(x*) for all x. Therefore, we have for Z = {1,2 + =T//2] 1} for T & Z and 7 {1, + 1,..., 2 [[T/2] 1) + 13 otherwise,
Σ 1EFF(.))1-((r) te2
Σ (E(T)
t(t 1)
E x=11
(t + 1)t
E Bl| B11 -104411110 x-(())
2
2
b
Σ
t
((M B 20x + 2(M
B Bo 2 muzul + +,222' 2112)
2μa
Noting that
Σ (t--1 - 1) (B[F(z))) -((*)) < Σe t (E[F(Zz)) F(z*)),
1EZ
20

---

Efficient Distributed Optimization under Heavy-Tailed Noise
(T- (T-2)2 -)=TT= 1
-1)//// x([T/z] + [
2z
2
2
we obtain
-nez(1-1)a 1]
+1+1) )} F(x")
E
(T 2) (4/1 + 2/2 + 1/3 + 1/4)
E1e2(t-1) -
As before, extension to the case where the learning rate decays at each outer optimizer synchronization step is straightforward. Therefore, the asymptotic convergence rate is identical that give Theorem
In particular, we immediately deduce the following corollary.
Corollary 4. Let the conditions of Theorem 3 hold. Then, Avg-Ir2Clip converges under heavy-tailed noise with rate (1T-(2a-2)y for E (0, (/2). That is, the algorithm recovers a point ör which is materialized during training such that
B|F(GT) - F(*)) x OTT (2a-(()))))))
Proof. The maximal rate of convergence is attained due the dominating term 22 We note that in the limit a + 1+ which revokes the integrability of the heavy-tailed noise, convergence is nullified.
C.2. Dynamies of Clipp under Failing Compute Nodes
Node failures can happen in both datacenter training (Yu al., 2019) or federated learning (Li al., 2020a). Consequently, is crucial conduct a theoretical performance analysis of CoCipp within environments accommodate the presence of failing compute nodes partial participation.
In this setting, we modify Line 2 of Avg-LgClip to sample subset of participating nodes, S C [NV rather than selecting S = [N]. Additionally, normalized averaging is performed across only the participating compute nodes in Line 7. However, we assume all compute nodes remain active, as described in Algorithm 3 below. We refer to this algorithm as SludgeClip to emphasize its impracticality, despite being functionally equivalent to a variant of Avg-LoClip aggregating over a subset of nodes. By analyzing SludgeClip, we are able to establish convergence of Avg-L2Clip when several datacenters or compute nodes fail to partake training.
Algorithm SludgeClip
Require: Initial model Tı, learning rate schedule Ve- clipping schedule c; Synchronization timestep E Z,o, projection domain X'
1: for ,,...,T'
T do
2: Sample participating compute nodes 5 C [N] according to p:
3: for each node E [N] do
4: Draw minibatch gradient 9h.0 = VFF ((,0)
5: xf+1 f- 2 - m LaClip(ce, sh.))
6: end for
7: if - 1 2 ZzO
for 8: ott + Projx (EEreSPi) EEvesirttt)) for Vk e [N]
9:
end for
Theorem 4. Let the clipping threshold in SludgeClip (Algorithm 3) satisfy a ent for e> 0 and 1/2 0. Decay the learning rate with schedule T)- rt((t + for > 2/p. If the sampling scheme preserves the global objective?, that is,
Es
Σ PxF = Σ CPP((s)== F(x), iEis]
RE(N)
then we have fore Z the set of synchronization steps up to T that
-x - s2.0)sz.000
(nnest-1)zz 1tEz(t-1) 11)
- 1)
F -
- F(x"((())))))))))))
For example, Pt 1/N satisfies this condition. That is, given any selection of p: and F((x), may rescale the local objectives (x( such that p, = 1/N by controlling the influence of each local gradient update.
21

---

Efficient Distributed Optimization under Heavy-Tailes Noise
where now w satisfies
w - 2%, (2 1
(22
1)}-
If the subsampling scheme fails to preserve the global objective (e.g., by sampling only a strict subset of avaliable nodes repeatedly), then Algorithm 3 asymptotes toward biased minimizer points within an increasing region determined by the clipping threshold E [F (irr) F(=") x O(12T).
We note that convergence is not clearly guaranteed when subsampling procedures violate the global objective in expectation. Specifically, we evaluate the algorithm's 's output relative to x², the global optimum of the true objective F(x). However, when subsampling alters the objective, the algorithm no longer optimizes for F(x)), thereby clearly undermining convergence toward x². We then measure the propensity of the algorithm output to x", the global optimum of the true objective F(r) which is longer the objective of the subsampled algorithm.
Proof. We first analyze the case in which the subsampling strategy preserves the correct global objective, which allows for convergence to z². Recall that SludgeClip-SGD constructed to allow the analysis for non-synchronization steps full-participation AvgpL Therefore, we focus outer optimizer synchronization steps while
to be analogous incorporating the elements of the previous analysis for Theorem 3. We now use the following notation for subsampled averages of participating compute node devices:
Lies PiPko
9: EiesPi Clipler, VI; (zh,0) (1,0)
82
Eies Pt
EiesPs
For added clarity, we denote 9e as 9, to indicate that normalized averages are taken over all inner compute nodes, and not solely participating nodes in Gt. Then for t synchronization step, have that
| - 11 S || x²" - -1:gel 7 + (3+ - Fee) x Th:rt + (NKT - 11te))1
|| x²1 112 + 2 xx, Iz - It- n1 + (n.Ge mTTe)) + BB
< 10 x² 112 2np (0r: - x², x²,9, 9: V
2npe (Ta x,, vF(x:))
A
A2
Tt +2( x² .t Iit) + + (Te xx 9t (t) + |
m7:
Ba
Bs
B.
In this form, the A, terms are therefore shared with the previous analysis, and A2 may be bounded by p-strong convexity before. This gives that
A2 < pmllaa x11 27 (F(az)) F(x")).
A is once again bounded under conditional expectations E.I-] by equation (7), though with different value of a' >>>>>>>>> 0 than in the previous proof.
A S pa ne Ee - x01 + Th ((M + ye --a + mezuL)).
paa
Now, as Bg is climinated under expectations under subsampling, we focus on the remaining terms. It is clear that we must bound and lgg, dell to proceed. Intuitively, this is controlled by normalized averages and model drift across participating nodes. Therefore, we consider the nearest or most recent synchronization timestep (,(()) as before and rearrange to incorporate elements of our previous amalysis. Assuming interchangeability between the integrals Es (integrating over the randomness of node subsampling) and E, (integrating over randomness of E(,u).
E [E [0c]
9.l
E,
Es
Eres Pe (Clip(ce, VF, (h.o)) VP((1.)) -90 ((9L-VF(a))
Pi
Es Ex
Di
(Clipler, F. (oh,os <(,0) VR. (h,0))
Ee [g. VF(+.))
En Eves Pv
LiES
< Eg Σ Pi
E, Elippiip VF, ( (1,0)) (f.
+ Exlllz. VF $ 2(M + +B*),/-
LiES Eves Pv
22

---

Efficient Distributed Optimization under Heavy-Tailes Noise
where obtain the final line we used Jensen and analogous reasoning in equation (5). Therefore, we have for b > 0 that
B3 - bT - =x-1 44:(M + (110)
It now remains to bound B,, which can be done straightforwardly:
B4 S 2 2 211 + 21 || S 422 16 21/
Collecting all inequalities gathered under the tower law of expectation, we have
Billă - x= 11 S (1 - ((1- 1 a)μ + b) E - 2 (F())) F(x*)]
+ Tht ((M* + B + m,.uu))) + 422 + 27 + 47, (M + 20)22211-0)
pa
Recall the learning rate schedule Th = r/((t + 1), while setting a', 6 such that r((1 ( + b) = 2. Then, we have for Z the set of all synchronization steps,
Σ (B[F(TT)] F(x))) S
Σ
t(t - 1)
Bi[ x x²11" (t 1)t
B Bl|[a++1 - x x117]
2
1EZ
++1E2
+
Σ 2(M + te
2(1-a)
Σ
1
((M + B²)ct + mczuL)2 +
Σ
tn (222222
2ua
1-EE
Hlez
B,
~ +.
~1
For +++11 1 & Z. we use the standard telescoping sum in equation (9) while noting that Ø4+1 = . due to the synchronization step. We do not repeat mechanical calculation steps here not obseure the intuitions behind the proof, and instead indicate asympototically equivalent terms V, under 1/(T"2 + T) averaging on the right hand side. remains to bound the residual term B3 under the averaging step, which gives
Bs T(T 1)
S (((
which concludes the proof for the first case.
In the setting in which the subsampling procedure fails to preserve the global objective, we bound || Z,|l as follows:
Σ Eigss Ph
|
Σ
pirio- Σ proto
Σ VE(S) Dv
RETST
1S[[
Rels Pke Evelst ps
pillotu Jr, |l
Σ
Pe pillzt
Je,ll S 2zumiet:
KE(S)
[E[
due to triangle inequality and Jensen. That is, by the synchronization step, we have 2t, = Ic,,, Ak E [N] via to full available node activation in SludgeClip. This gives
| Fr,11= 2/.0 +
Σ (-2 x +2))
It,
1a z S 2urie
N't,+1
f=,,+1
as in equation (6). Similarly, we have by Jensen and convexity of the norm that
llă: J.l I 2ct-
Therefore, we obtain for b,, by > 0
1
22 222u2cn
B2 < b17te [T+ x² 112 +
1/00 -Ill? s b1n.
2²1
b177
b
By < b2m
|o+ x 21 + 4n.
23

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Following analogous caleulations in the where the subsampling does not violate the global objective, we arrive at new residual term
Bs T(T +
S O(t?))
which controls the expansion of the bias due to the incorrect sampling strategy.
C.3. Convergence of BiClip
In this section, analyze the convergence of BipClip under heavy-tailed noise. By employing BiClip both the inner and outer optimizers, Clip is efficient algorithm realized by TaiOOPT that brings about benefits of adaptivity without maintaining gradient (or model update) statistics. Unlike Adam which applies Adam at both the inner and outer optimizers, Bi Clip achieves comparable or even superior empirical performance while requiring additional memory or computational overhead (Table 1). This highlights its efficiency and practicality, particularly in resource-constrained settings. We begin with the pseudocode for Clip in Algorithm
Algorithm& 4 CiCplip
Require: Initial model T1, learning rate schedule ?ho clipping schedules un de, To de Synchronization timestep E Z
1: for = I,..., T ,, do
2: for each node E [N] parallel do
3: <².00 f- 24
4: for each local step & [a] do
5: Draw minibatch gradient gi.k V (1,
6: Jhet1 sh. ' BiClip(u,, des si,))
7:
end for
8: end for
9: A. = N EEEN (zi,; - -1-1),, mr t A.
10:
= Zt-1 + BBiClip(üu de, m²)
11: end for
We carry out the analysis over a sufficiently large, compact domain X. Let VF be the deterministic gradient, obtained by integrating over (1 {), the stochastic gradient with heavy-tailed distribution. The existence of VF(x) implies F F(x) is continuous, which gives boundedness via the extremal value theorem. Therefore, from onward, formally assume VF(x) is coordinatewise bounded by G in absolute value. We have the following theorem.
Theorem 5. Let Assumptions 1-2 hold, and the learning rate and clipping schedules satisfy Th O(8), o O(t)) d. O(77), O(tS), d, = Ot)), and ui = (15)). Imposing ç. > 0 > 7, 7, for w, S 0, as well as -1 < w +v. for BiCCipp (Algorithm 4), we have that
min B|I v U2 + V3 + V1 + V. + vo + 17. NET
where the v are given
1/2 O (IW+zi=U), v O O0T0OTToo (I-W-V-1),
V/3 v/== = 0 (Iī-T)) 01")( = o (T(L-a)s), v7= (TTUS).
V o (Tla-1)ot(1-ap)
Proof. We provide the proof for Lz-wise BiClip(-) for illustrative purposes and notational convenience. The extension coordinate-wise BiClip(-) is straightforward described in the comments following the proof of Theorem 6, Remark 2. For completeness and readability, we formally provide the definition of L--wise BiClip(-) as
BiClip(ur, x) x
de
x (122) S de) x
We
x (||=)| 2 u.) + x (de < ||]||| ue).
|
|
24

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Here, X is the indicator function, and ", 2 de 0 are the clipping thresholds. By default, we take a/0 a= 0 for Va E R. Now, we begin by noting that due to I-smoothness, we have where [e[ takes expectation up 2t-1 that
L $ (VF(I+-1), Balexx =]) + - -
2 E. [1,ee xz- 119)
S m -B, de -Ail) + Line E, [| BiClip(u, ā. A0)l
2
Now, we expand to obtain the following form
A1 = BBCliti
- -.) + A Fré Σ E
iE(N) wE[K]-1
B, -Ai) - Arl)
VF(
Σ
Σ
PVF. -
iE(N] DE[K] -1
B1
B2
VF(E)-1); Σ Σ
Kn/VF((t-1))
Kni V (2
KE|N PE[K]-I
Ba
Using the convexity of compositions (via 2 1) and Jensen, we deduce
E E.
Σ
Σ
BBBlBipllupudde de, V. )1
EE|N] PE[K]-1
E
Σ P BiClip(u, dr (F (
K
iE[N] WE[K]-1
(11) Kaa1
Σ
P.E, [ICClppll de
NE[N] VE[K]
Ka-)
Σ
Σ
prldf [ V. 119)
iE(N WE[K] -1
Ka
Σ
Σ
p:d (1)))k=11 Σ Σ
p.B.I VFi 119
NE[N
WE[K]
NE(M) kE|K]-1
Note that the term C' can be bounded as
VF 11
||
C S (ni)a
Σ
Σ
E,
2
2
NEIN ME[K]
< (n)) K
Σ
P:20-1 (M
TM + B²) =(n))a Ka-1
2 20-1 (M + B*),
ME
where M := iiI [x((I] and 8 = maxie[N] =E[K]-1 E ||] < suPiE (B:)aa, We note that this
results holds also under distribution shift for the stochastic noise E, where / E [T] and i E [N]. long as the a-moment remains universally bounded. Therefore, we conclude
[1 |1 1 S (n)) K0-1
Σ di (al)a-a-
Σ (M Ba) (ni)a M. -E[K|-1
-1
25

---

Efficient Distributed Optimization under Mlcayy-Tailed Noise
This gives by the Cauchy-Sehwarcd inequality that
B s (
de -.)] + Dell
< G. B, A. S d.) de x S ||A+|] II) || -
G P(1A: d.) d +P S ||)+)) (Tb M
Now, B2 may be bounded as follows:
B2 G
1/ ΣΣX
Σ
ic[N] PE[R]-1
G E, Ink
Σ Σ (. A.] ME|N]
S GE,
ni [E[N]<E[K]]
(1p) +
where we used convexity, Jensen, and that the stochastic gradient noise unbiased. Unraveling the definition of the pseudogradient A gives
||
B2 S G
Σ |E[N] WE[K]-1
Σ
P.
E Σ P.BiClip(ur,d de, VE(a, (1,0))
KEINUE,
S Grfi Σ
Σ P.
( BiClip(us, de, Ve
NE(N] [E
S Gril Σ
Σ Di [dPPIIVRR 2.DI d.) + (E) [(20i1 2 uu) + +B))
(E(N) VE[KI-1
S Gri -
Σ
dd + u aul-a2a-1 (M + B
Additionally, B3 may be bounded via L smoothness and telescoping:
Bg S G
Σ
Σ P.V..(o),.)) KVF(
NE[N] -E(K
S G/G
Σ
Σ (.V.) Σ Σ (VV
AE(M) WE[K]-1
[E[N]
S G/G Σ
Σ
P. - x
iE|N] wE k]
S G Σ
Σ
PiL
Df Σ
( - - a1.00
1-1
(n))GLKZ
< GL Σ Pi. (E[M]
Σ
| - of -.,-
5
2
-1
Collecting all inequalities gathered thus far, we have
Laj uZ
[xF((x)]] - F((r-1) <
V + Gride + ( MM
2
(M + BBy] + 11 GT.K)
+ Grien
Σ
[de+ + aa--aa--1
2
vE -
26

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Telescoping under the law of iterated expectations gives
Tnf
Σ LE(2]
Knim F(zo) F [[F((r)) +
+ +Gnide + Gn(lk) M M
2
1Ef2
(e(r)) GLK
Σ tE[T]
TE
[de + ui 14-0220-1 +B)]+
Ba)]+
ME(K] -1
tE|T]
Now, we move to the asymptotic regime. Let 7л: O(t", T/2 = O(t"), di = =(()), dt = O(t5), de = O(t%), and
do = O(tS). This gives after routine calculations that
min B|I O (T- (T Tw v + v ((o-1))-(1-0))) T T(1 + Tutt).
T
To attain convergence of the RHS, it is clear that we must impose S. > 0 > 7, for w. v/ S 0. Additionally, we have further constrained -1 < w + v, which ensures that the LHS diverges at a scale faster than logarithmic, validating the asymptotic regime and concluding the proof. To obtain the rate of convergence, we may let
1,
= - - --2 v,
r4 (a 1)(5 v). T6 = (ax -15: 17 -
(10)
-7,
for a min (ri...., r7) and
min E VF (21-1)]1 (T 9) tE(T]
Equalizing re and gives that ( -v/a > 1, < 0,5 > 0. Similarly, equalizing 11 and ra gives = -(1 (1 + +2)/22
yielding rı r2 1/2 + Ç. By letting - 0++
1 {= (a 1) - E+o
1
1)
1
1
<
a
4ax
4a
2
For suitably small y, 7,7, we therefore have
a
0
4a 2
concluding the proof.
Remark We note that setting 0, ū = =0, - and ni. = at the outer optimizer recovers a special case of BiP i.e., nig-BiClip. Similarly, for specific hyperparameter choices, BipClip collapses into BiClip-SGD, with upper and lower thresholding applied by the outer optimizers only to accumalated model updates from the inner compute nodes.
Now, in the following subsections, we further analyze the convergence behavior of ТailOP under additional varying adaptive optimizer instantiations. The Adagrad instantiation (Algorithm 5) collects pseudogradients and sums their squares, effectively implementing form of implicit clipping. However, aggressively decays coordinate-wise learning rates, which can limit performance. To address this, introduce RMSProp- ailpp (Algorithm 6), which relaxes the preconditioning by employing an exponentially decaying moving average of the second moment. In both cases, we prove that the minimum expected gradient converges to O. Additionally, by incorporating moving average of the first pseudogradient moment as a form of momentum, we derive Algorithm 7. For this variant, we show that the expected minimal gradient does not diverge even under restarting of the algorithm, which in practice translates to the update of any singular step not diverging in expectation. As in the main paper, TailClip refers to either BiClip or L2Clip, and we provide our proofs for BiClip for added generality over L2Clip.
C.4. Convergence of Adagrad-TailClip
We begin by providing the pseudocode of -hagrad-Tailllip (Algorithm 5). Then, we have the following result.
27

---

Efficient Distributed Optimization under Heavy-Tailes Noise
Algorithm 5 Adagrad-TaulClip
Require: Initial model 1i, learning rate schedule Vi, clipping schedules we, de Synchronization timestep E Zzo. adaptivity parameter
1: for t = 1,..., do
2: for each node E [N] in parallel do
3: <².0 <- 2t
4:
for each local step & E [z] do
5:
Draw minibatch gradient g... -
6:
2,,41 t - - Th TailClippuu de g(,k)
7:
end for end for
8:
9:
A. N DIEIN]
(1/,e= -I--1), me A.
10:
er = U- + A?
11:
2y = It-1 + Vin+T
12: end for
Theorem 6. Let the clipping and learning rate thresholds satisfy O(t)), m/ = O(t"), d. = O(t)), and = O(tt) for the conditions Ç > 0, < 11/2, and w - 1-1 0. Then, we have that
min E V v + U2 + v/3 + U4 + 4 Ve. T
where the v are upper bounded by
v S O(T
12 O
V. S O
1 S ((
V, ((T
Ve S O
which guarantees convergence via an inversely proportional power law decay with respect to T. The maximal convergence rate given by (
Proof. We analyze the convergence of the global objective, where model weights are updated in a distributed fashion via local BiClip under heavy-tailed noise. By L-smoothness, have
F(x+) S F(x--1) + (VF(1; 24-1) 1)- +
||,re Ft-1 1|
= F( + (VF(I-1))
4
L
b
V +
Cr +
A1
which we further decompose via noting that
Arly 0-1 24)
A
A V VF(x,-)) 1),
+ VF(I--)),
(Ver + T)(v U. +
1U-1 +
-4,
A
VF( ( U-- + T)(
+
(F(It-)),
1 Vub)
V Vi--1
A
A
< [V((+-1)] (Vo.+ + 1-
+
VF 1);
1z- v
v
1z +T
To bound B1, extract negative gradient nomm
2
A
Kmf VF
VF VF(x.-1)
Bi W VF(#=1))
Knent
Vū.
+
V +r
V +
B3
28

---

Efficient Distributed Optimization under Heavy- Tailed Noise
where B2 decomposes further into
A
EiElN] -I VFP((E))))
Kn/VF(xt-)
B2 T
(F(L--))
1
+
0 +
vūt-1 +
Here, we use the convention [K] - 1 = {0,..., K - 1}. and that summation over null indices are zero (c.g. Σø=k| 11= 0),
Now, recall
A =
p
Σ
-4)0) p - - - Σ Σ
pode gi.0
NE[
iE[N]
KE[N] -)
Σ
Σ
pone
BiClip(ue, de, VF Cl,))
VE[N] -E[K]-1
which implies B2 = C1 + C2 for
EIENNT EvEjK]- Panh (V. BiClip(u,, de, VF((.).)) + tl,w))
C = 1/ ()(
0--1 77
E E Pan/ (VF V.F((t
C2 = 7
VF(()-)).
Vē-+t +
Letting [-[ condition over all stochasticity up global step we have that E,[Ci] is equal
EiE[N]
+ Et. - BiClip(u, d. V..().))) + (l
(((x-)),
Th
For D1 Ex V. Et.. BiClip(ue, de, VF((T,))) (.,)), have by convexity and Jensen that
|D1I| & (. + Ei,u BiClip(u,, d, (F st,)l
[EIEE + -iCllipuu de, V.((E,))) + llx ( stell 2 u))
D2
Piecewise continuity of (z) is clear via the existence of (.) This gives that
E
ft 11 VI
u.)l I
VF + &
FV
||
E,
E
-20 + Ba),
2
2
2
where now, M = max [F((T)| Thus, we may bound D2 via reduction the a-moment:
D2 x 2a- + BI + - (IVVE + 4(.) 2 u.)
< (M + Bd)u, up (1V m.)
Collecting inequalities gives
||DI| < d.P( VF (.,00 d.) 2
1M Bd 'M (IVF (IVEGtt)))) m))
Therefore,
GcG
E, Cil
Σ Σ
P.T :f. sf,,)) <d,
2 Gd
Σ
pmi(MM (IVF
s(,)) u))
M
K
29

---

Efficient Distributed Optimization under Heavy- Tailed Noise
To bound C2. note that via Lssoothhess, we have
GLd
C2 ~
Σ
Σ
potilaato sile
SE[N]
-E|K]-1
GLd
Σ
Σ
Potil +
- -
SEIN] -E[K]-1
==1
GLd
n.GLK2d
Σ
Σ
Σ
Potél - -2/2r-11 5
(TTé) ue.
2r
NE[N] -E]
Noting that ||A,|| S n,u,K, K, we thus obtain
[.[F(a))] S F(x--1) - P
mGdK""u)(h)" 73
vx(x
Knol
272
/V +7
GLL2dd
TrGd
(nt) ur
Σ
pol.dF((IVF(((..ss... s (d) NE[K]-1
Σ
2r
T
iE[N]
2a-1 Gc
Σ
Σ
(M + Ba TP (IVV
( uz)
T
iE[N]
=E|K]-1
Taking expectations both sides and telescoping gives via the tower law of expectation.
F
GGGK (166)3
Σ K
E (((T)))
F(xo))
+
27
1E|2
+
Ex
6E[2]
[E[2]
Ei
Eg
G
m.Gd
(nt)²
uu +
Σ
S1,) S d.)
2T
6E/2
iE[N] 0E[K]-1
Es
Es
2a-1 1 The Gd
Σ
PM + BB) "P (IV (.,))) ui)
T
LE[T]
NE[N] -1
E7
where we have enumerated each term from Ej E, for clarity. To simplify notation, regime. Letting = ((1)), v/ = ((!"), d, ((7), and on =(()), we have via standard integral bounds that
move to the asymptotic
E1 Ω Twttttl . - Cーーー min EI|V((2)))1 Ω T stb min B(IVF(())))
[E]7]
[E(T]
Eg < max F (x) min F(y) = O(1, Eg S O O(T22224222t) EE
E. S O(T
yEX
Es < 2
Eg < O
E, < OyTutota-aktt)
where any E, residues of 011 for i 2 2 have been incorporated into the upper bound for Eg. We note that the bound may be sharpened as the probabilistic terms must necessarily decay if de + 0, ue + co, which further diminishes Es. E,. Now, to attain convergence of the minimal gradient, we impose the conditions
1
w 2v +36 + 1 < 0,
< > 0 and << 0, Ag w < 0,
1
1
1 -o:
A : 4Ç + 3v
< 0,
: 2v + 2Ç
< 0,
0,
2
2
A7: (2 (2) +
0.
2
30

---

0x --1 2a Efficient Distributed Optimization under Heavy-Tailed Noise
We note that each condition A22 comes from E,/E, 0, T - xc, any residual terms subsumed by 0(1) which decays via A2. To derive the convergence rate, equalize the bottlenecks by letting A2 A3 A7 a. This gives system of equations:
1
w + 2v + +36-
2
4 (2 a)s
+
2
which gives that
V
(11)
2a
Letting = (a - 1)/2a gives the slackness of A4, As, and As for y < -1/2. Therefore, the minimum expected gradient norm squared stabilizes at rate O(T
Remark 2. In the case of coordinate-wise clipping, all major adjustments up to a scaling factor of Vd are made in the terms bounding E[ In this case, the proof proceeds as follows.
Defining
to act coordinatewise, [ri] is now less than equal to
nh [F(I--))) EiE[N] E P. E. + E BiClipp(u,,dd de VF((),) (2,0
Therefore by Jensen,
[x[Ci] & B T
Σ Σ
Σ
R. (VF((t) + G BiClip(ue, de (x(())))) + (.)
iE(N)
[E[]] - jE(d
Dis
We note that E,, [D. can be upper bounded by D2.5 D3.5 where
D2, E, Di. x (IVF s d))) s d. ((P((VVo d:))
D3.5 E, ( ( (IVF (l 2 ut)]]
It follows that
D3j < E, [V.
G1,1i u))
2 (M + BB (IV ft, 2 ut).
Note that we used coordinate-wise bounded alpha moments for some a E (1, Eilsil9 s B We therefore define the M and B to be
M
max JEE
(((())) and B = max
Bij-
iE[N]jE[
Comparing terms gives the identical asymptotic order of convergence to L.2 clipping in Theorem
C.5. Convergence of RMSProp-TaiiClip
For Algorithm 6, we have the following convergence bound.
Theorem 7. For clipping and learning rate thresholds satisfying ni = O = d and u ((S)) let the conditions listed in Theorem 6 hold. Then, local BiClip with outer optimizer RMSProp stabilizes the expected minimum gradient minterr E[[[V [(+) + 0+ with maximal rate (1-3)a)2) Here, the exponential moving average parameter of the second pseudogradient moment is fixed within the range B2 E (0,
31

---

Efficient Distributed Optimization under Heavy-Tailee Noise
Algorithm 6 RMS-TailClip
Require: Initial model 1ı, learning rate schedule ?e. clipping schedules ue. dj
Synchronization timestep Zo., adaptivity/EMA parameters 0, B2 [0. 1)
1: for -........ ,...,, do
2: for each node [N] in parallel do
3: <4.0 <-
4: for each local step & E [=] do
5:
Draw minibatch gradient J.,x (
6:
21,411 + - m1 TailClip(us. de, ki,,)
7:
end for
8:
end for
9:
A: N LiE[N] (0/ 12-1), mn c A.
10: oo = - + (1 (1-B2) A2)
2t zt-1 + Vostr
12: end for
Proof. The proof for outer optimizer RMSProp builds on the prior proof for BiClip with outer optimizer Adagrad. We skip repeated details for clarity of exposition, and concisely present only the main steps and ideas central to the proof for readability. T-smoothness gives before
L
F(x1) - +((o))) - xx-1) +
|1
x1-
1l
-((x-1) + (FF(E)1))
A,
--+
L
A
(12)
V0x +
2
v +
We note the decomposition
A:
A.
4.
VF(1111):
(F(1)-1):
(F(()-1);
Vo +
Vue
+
128 +
B2 +T
B2
To form an upper bound, we use that
A.
Km M Fx
V VF(xt-1)
B₂ =
(F(
-Knb
1200-14 +T
/B20-1+ +
V B2 +7
Co
where Co = C1 + C2 for
C (F(+-))) EieiN Eve[K]-1PRR (VF. BiClúp(u, de, VF(( + (l,,))
/ /BuT- +
ELEINI EVETK K Derl (V (F. - v.((o((.)))
C2
VF(I+1));
V
32

---

Efficient Distributed Optimization under Heavy-Tailed Noise
By the tower law and conditioning on stochastic realizations up ( have as before
Gd
GLK?d
[[Co]
Σ
Σ
de)
(nb)²ux
T
2r
iE|M]
VE [K(K--1
Gd
Σ
Σ
PM + B" )
(1,l we)
T
VE[NI
DE[K]-1
Gd
GLK
20 Go
Kndde
+
(ni)
ut
Kn/( +B
5
2T
7
To bound B1, have
D
A
(32 - 1)42 (Vor+ v Batr-1
B1 VF(2(11)
VF(I)-1).
32
(V +
(V (
We prepare the global inequality (12) for telescoping. is straightforward to see that collecting inequalities gives
n uk?(2(?(
VF(I1-1)
B[F(z)) s B[F
Knof
2T²
v 32 +
Gd Knotede
GLK2d
Ga-IGd
dG(1 (uent)))
11 (n/)))
Knot(M + BB)ut +
2r
73
Rearranging and telescoping gives
T
VF(I--1)
I
Mi
LKL un?
E
< [[)() - B[F(rT)] +
27
V 8 +
1=1
Gd
GLK?d 2r
2 2a-IGd t/ Uq +
Knot + Ba)ut + dG(1 B2) (u)nt))
Knnndd
+
T
73
By non-negativity of squared pseudogradients, we immediately obtain 320,-1 S 51- Therefore up to constants, the convergence bound collapses to asymptotically equivalent bounds than that of Theorem 6, up constant multiples from the exponentially decaying moving average of the second moment pseudogradient. The modification to coordinate-wie clipping instead of L2 clipping follows analogous steps.
Incorporating momentum into the first pseudogradient moment further complicates the analysis. and yields the results presented in Section C.6.
C.6. Convergence of Adam-TailClip
By incorporating moving average of the first pseudogradient moment as form of momentum, we derive Algorithm 7. For this variant, we demonstrate that the expected minimal gradient does not diverge, even when the algorithm undergoes restarts. Practically, this ensures that the located gradient value update of any single step remains bounded in expectation. Investigating the conditions required to guarantee convergence to under this framework presents a promising avenue for future research. Our bound highlights that the dominating terms are influenced by the upper clipping threshold u,, suggesting that the algorithm's convergence behavior may be closely related the choice of this threshold and can be tuned in practice.
Theorem 8. Let the exponentially decaying moving average parameters satisfy 31 E (0, Br E 10 for the outer optimizer first and second order pseudogradient moments, respectively. Extremize the unbiased stochastic noise such
33

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Algorithm 7 Adam-TailClipp
Require: Initial model 2ı, learning rate schedule ?e. clipping schedules ue. de
Synchronization timestep Zo. adaptivity/EMA parameters 0. 31, B2 E [0, 1)
1: for 1,....... ,...,, do
2: for each node [N] in parallel do
3: <4.0 <-
4: for each local step & E [=] do
5:
Draw minibatch gradient J.,x = -VE
6:
2,,411 + - m1 TailClip(u de H.
7:
end for
8:
end for
9:
A: N LiE[N] ( 12-1)
10:
mh = + + -1-31144
11:
ūr - + (1-1-) B2)
12: Ft = It-1 + 17 VoLt
The
13:
end for
that Don E (1,2) for which 1 < B% for integrable Ex- Then, Algorithm 7 gives under constant upper clipping threshold invariant to global timestep (Ç 0) that
min E
where for Th2 O(!"), oi ((')), and d, O(77), impose
v VE (-1,0,
-レ ww ww <7<0.
(13)
Proof. As in the case of outer optimizer Adagrad, we analyze the convergence of the global objective. By L-smoothness, we have
L
F(x)) F(I--1) + (V -e -- + |10 Ft 112
3/ + (1 31) Σr 3
L
=F 11 (F(I
|| 11
(14)
V0 +
2
A1
To proceed with the proof, we note that
(VF(I(-))AA))>
VF(xL1)),
m
(1 B1) Σ
31
-
VF(I=-1),
A
Vor
+7
+
1=1
which we further decompose by using
A VF(2-1),
A
A
(F(1-1),
Vor
+T
p3u +
V
gatl=
12
-
Ai.g
VF(x+-1-
+ (F(x)-1),
rt-
Up
+
51-r+1
+
8.
34

---

Efficient Distributed Optimization under Heavy-Tailed Noise
We have that
(V B2
4r
V B5
A1.
V F((c-1)),
B1,4
18 + :) (V
32 04- +
-(1 - 32)3228. A.
VF(I
(V
Ba +T)
(V52*
24 g- +T)
(v [89
1 B500-g
9-
To upper bound B2, we observe
A
Kn/ V FF(
F ((
B2 = (F(
KKn
D
+
B2
1- 0r- 1
32 r+
+7
Co.r
where Co, = C1,r C2. for
C₁,- = (F(I ENEIN Eve[k]-1 POTE (VF, - BiClii((u, de, VF((2T) + +
-1-1 +7
C2 V((rr-)), EIENN EVEKKI-1 POTE (1,, VFF(o.,)))
8-
Noting that [E[ [ [E [.] by the tower law, we have as before
Gd
( sd) + GLK
E <
Σ
Σ
(r/))
T
2r
2 Ga
Σ
Σ (M + Bd)
mr)
T
iE[N]
=E|K1-1
Gd $ T =nEdd
GLK?d
Gd
(m))
(M B )z
2r
T
We retain the a for clarity and to draw comparision to previous proofs, however we note that a = as higher moments do not exist. Now, to bound B1, we use I-smoothness:
TofE uy K
Taf u, K diam (2)
11--1 - xy-1ll S
T
T
Collecting all inequalities gathered thus far gives
E[F(x,)] < (x, 1)1
D 2
E[|l E|||A|
B
VF(x=-1)) 1),
mg
Von +
VF(1r-1)
Luf u, K diam
+(1 31
E Bi.gl Kif
T
1=0
r+++ 35
U0-1 +
Gd
GLK?d
2a Ga
+ (1 (1-33)) B1)1% Σ ター
Kifed,
(1F)
+
Kiff (M + BB) 1-a
2r
T
35

---

Efficient Distributed Optimization under Heavy-Tailed Noise
We note the of Jensen and convexity ensure ||[ s <B[]]
We now rearrange and telescope / E [1, T):
V (2r-111)
M 2 L
(1 - 31)
K E
[[ [(F(())))
[1 A
0-
Fa
Fi
mo
Lmf u diam(X))
+
Th.
E
+ +(1 31)
116
11
Σ E
Vūx +
Fr
f6
T
Gd
GLK?d
20 Gd
+ (1
31)
17t
31
Knf d,
(1/ )
uu,
K
(M + Baa B
ut-a
2T
T
Fg
Fio
F5
We now aim to bound each term in the left hand side from below, and right hand side from above. Letting nt = O(t)), T/t (t"), de = ((*),, and u, (t5), we move the asymptotic regime to simplify notation and suppress auxiliary constants for readability. We have that
T
T
(1- - 31)
Th T Tr (1 31)
Σ
Σ
3
me
2
(1
31)
Σ
31
dr.
(15)
1=1
1=1
t=1
Then, L''ôôpitll's 'ss rule allows us to derive an asymptotically sharp bound as follows:
1 3- dr=
J.
3-'2" log, (31)
dr 2
(16)
log (B1)
log, (31)
r=1
Here, used that s and 0 < B1 Asymptotic equivalence is verified via
logg (3)) r" dr)
log, lloge (3))) loge (3)) 13-
lim 8-000
lim 1-
Therefore, the rightmost side of (16) is asymptotically sharp approximation, relieving the condition 0 for validity of the approximation. Within 31 (0, 1), the approximation diverges expected, validating the asymptotic analysis. Recall that A, < Knp which now gives via (16)
32 st-+llg
3
Σ 3r ( max (ox( ((()ss)
(17)
1=1
Here, we used B2 < 1 and < T. We thus obtain
T
21 - Bi) L"
guto
(1 3 w
(1 B1) nh T/e 2 (1 - 31)
T
log (3))
(3))
(w + v + 1) (B))
Therefore as v + < < O, we conclude that
(1 1-31) B1)
Fi Q
min t
E| ((
(w + 1) log. (31)
36

---

Efficient Distributed Optimization under Mlcayy-Tailed Noise
Clearly, F2 S 0(1). To bound F3, we have
T Σ F3
7 L
Aio (1 (1-3ip -1-
A
2
2
B 2 + (1 31)
2
Vū +T
72
r=1
t=l
t=1
((1)
(1 - (1- Σ 1= f2022+2
011)
(1
)2 T
72 +
x
+
72 (log. (3)))
72
72 (31)) (1:))2
F4 is bounded similarly after using Jensen,
B K KIVE(EC-D)
mol Vor +T
mo
F S
The 3 dG
max jE
x O(1)
j 7
Bounding Fs and Fg is more complex. We begin by noting that
G(1 G(1-32)) 32)33
A راا
72
G(1 32)
A 7 /r
E
j=1
72
V m 100xx(111-000 V50 + (1 - 3²) Ee= 32 41-4-0
A 72
32)
2 Σ
E
[A o |p.
jm1
Therefore,
PSR S (1 B1)
1)t
8--011
B3) Σ
32 E 14
1=1
q=0
T
S - 31)
1
8-
-21-
Σ
( u
1=1
9=
Under the substitution g f t
q. we have that
T
FvFo $ (1-31)
31)
3 (11 - 32 up 33
31-((1
Σ B (nā q=r
1=1
1=1
T
-1- (1 32) 20tc (2(v+5)
((1-3))
logg (32)
1=1
T'
(x+)(
<11-3) - 31)
71(1 - 32) 8 uus
loge (32)
S (1 31) Σ (1 32)
(w++)(++
(1 B,)(1 32)
-max (0(1), ( Tw+S(o+tHH1
log. (31) (ogg(
(32)
log, (3:)ll log (32)
As (1) terms are subsumed by FA, F3Fr is bounded via
T
Luf u, K diam
T
Wh WT
(1 - 31) Σ 1/t
31
S1 - 31)
1=1
r=
1=1
(1 - Br yrwtttttt
S (1- - 31) Σ
7 log (B1)
7 log, (3:)1
37

---

Efficient Distributed Optimization under Heavy-Tailed Noise
The remaining terms may also be bounded follows:
(1 31
T
(1
31)
F5F8
m/
x
17t
pptty
T
5
(1 31)
T
(1 31)
max(TTuutytt,.om
log.
(31)
log (31)
1=11
where Fg and Fio can be bounded via
1
( (16)2ur
(1 31)
1101-12244
Tautetitu
S1 31)
2
2
T
loge
(81)
T
T
3 nu a
T
F3 S (1 - (1)
neP1
21 - (1)
r=1
T
(1 31) ++((11-a)
(1 - 31 (
loge (31)
(31)
Standard calculations imply that under the conditions (13), the dominating terms are F7, F10 with order (1)) Within the derived upper bound, ç > 0 destabilizes F7 and decays Pio to O, while Ç < 0 gives the analogous properties with F7 and Fio swapped.
38

---

Efficient Distributed Optimization under Heavy-Tailed Noise
D. Experiment Setup & Full Results
In this section, we present the experimental setups and results across two primary domains: synthetic data and natural language processing tasks. More precisely, we evaluate the performance of TailOPT instantiations with state-of-the- benchmarks on convex models (with synthetic data), transformer encoders, as well as generative models. For convex, synthetic experiments, we construct datasets to emulate heavy-tailed stochastic gradients, focusing on linear regression models trained under contaminated label noise. The design includes generating feature matrices and labels while injecting noise from heavy-tailed distributions to study convergence behaviors. Additionally, we introduce the SynToken dataset, which models the heavy-tailed distribution of token frequencies observed in natural language processing. For brevity, we only include the results of the SynToken dataset, denoted 'Synthetic data', in the main text (Figure 1). This allows us to evaluate learning algorithms in controlled settings, easing out and exploring the effects of both common and rare features.
For assessing the optimization of transformer encoders on natural language processing tasks, we evaluate RoBERTa (Liu al., 2019) the General Language Understanding Evaluation (GLUE) benchmark (Wang al., 2019), which encompasses diverse range of tasks such as sentiment analysis, paraphrase detection, and natural language inference. By finetuning RoBERTa on GLUE, we assess its generalization capabilities and robustness. The benchmark's 's inclusion of multiple datasets ensures a comprehensive evaluation of model performance across various linguistic phenomena. Additionally, we also evaluate the capabilities of the T5 (Raffel et al., 2020) generative model on WMT machine translation tasks (Foundation, 2019). These experiments provide insights into the behavior of optimization algorithms and pretrained models under realistic and challenging conditions. For RoBERTa, we optimize over GLUE across 10 simulated compute nodes, whereas for T5, model compute node finetuning WMT benchmark datasets.
D.I. Convex Models
D.1.1. DATA GENERATION PROCESS
To simulate heavy-tailed stochastic gradients simple yet controlled linear regression setting, we generated synthetic dataset as follows. The feature matrix X E IR xmm was constructed with entries drawn independently from standard normal distribution, Xij ~ ((0, 1). The true weight vector Wrme E m m x identity matrix.
was sampled from (N0,, Im), where Im is the
The true labels were computed using:
Vtrue
X
Winee
To induce heavy-tailed stochastic gradients, injected noise into the label vector by adding noise term &, resulting in contaminated labels:
V/me +
where & E R is noise vector with entries drawn independently from a heavy-tailed distribution D. For simplicity, we assume coordinate-wise independence of the noise components.
After generating the dataset, we distributed the data across n 10 datacenters in an IID fashion. Notably, the heavy-tailed noise injected once prior to distribution, and additional data were generated afterward. This approach ensured that the same contaminated training data are used locally throughout the training process.
1.1.2. LINEAR REGRESSION MODEL
We consider a single-layer neural network without biases, parameterized by w E Rm, which is equivalent to linear regression. Training is performed using the contaminated labels (X, Ø) with the mean-squared error (MSE) loss function:
((w) = - Xw|
The gradient of the loss with respect to w is given by:
Vul(w)= = - -..)..
Substituting : = -truc + = Wime + E, we have:
VwL(w)) X (Xurme + -- Xw)= X X (Wine - - XTC.
39

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Simplifying, we obtain:
VwL(w)= X X Winue) x-
The term -X" & reflects the influence of the heavy-tailed noise on the gradient. Given that X has Gaussian entries and g follows a heavy-tailed distribution, the stochastic gradients V (w)(w) are also heavy-tailed.
D.1.3. THE SYNTOKEN DATASET
To model the heavy-tailed nature of token frequencies observed in natural language processing, we created the synthetic SynToken dataset. In natural language, word or token usage often follows a heavy-tailed distribution. That is, small number of tokens appear very frequently, while large number of tokens appear infrequently but carry significant contextual information. In our dataset, we partitioned the feature space into common and rare features to reflect this phenomenon. Specifically, we designated the first p 10% of the columns of X as common features and the remaining 90% as rare features. The common features were generated by sampling from a Bernoulli distribution with high probability of success:
X Common Bernoulli(0.9),
resulting in features that are frequently active. The rare features were sampled from a Bernoulli distribution with a low probability of success:
Xun Bernoull((O.1).
introducing sparsity and emulating infrequently occurring tokens. The complete feature matrix X was formed by concate- nating X coommon and X
X X commonn Xyave
The weight vector w was sampled from a standard multivariate normal distribution, w ~ NO, Im). consistent with the previous setup. Noise injection was analogously applied to the labels as before. This approach was taken to mimic the key characteristics of tokenization and word embeddings in natural language processing, via minimal yet effective model. One benefit of synthetic datasets is that by simulating the distribution of common and rare tokens, the SynToken dataset allows us to study the effects of heavy-tailed data distributions on learning algorithms in a controlled setting. Additionally, note that the problem being studied is p-strongly convex.
D.2. Synthetic Data Experiments Discussion
Does the heavy-tailed distribution of covariates matter? Figure 4 (a) and (c) illustrate that heavy-tailed distribution of token frequencies has significant impacts on the performance of optimization strategies. In (a), AMSSrro-BiiCL performs competitively under standard tokenization. However, in (c), heavy-tailed tokenization applied to the feature matrix destabilizes CiiSProp-BiClip Interestingly, under tokenized conditions without noise, RMSProp exhibits oscillatory behavior, whereas Adam maintains relative stability. This is consistent with the interpretation of Adam as incorporating an exponentially decaying moving average of the gradient's first moment, which augments optimization stability. Upon noise injection, best performing hyperparameters for RMSProp-BiClip does not show oscillatory behavior, but is larger in terms of distance ||w, u| than the case without noise.
Does noise matter? When noise is injected into the labels, the performance dynamics shift considerably. outer optimizer adaptive or non-adaptive methods combined with inner optimizer SGD perform poorly, which may indicate that inner optimizers should take a focal role in addressing the challenges posed by heavy-tailed noise. While the choice of the outer optimizer may appear to a limited impact on the binary question of Icarnability for this specific synthetic data (i.c., "Can the algorithm decrease distance to the true w. or not?"), under tokenized conditions with heavy-tailed noise (Figure 4(d)), outer optimizer Adam demonstrates the best performance. Figure 4 reveals that heavy-tailed noise generally destabilizes all algorithms, including adaptive methods, clipped approaches, and pure SGD (c.f., minimum values in (a) and (c) to (b) and (d)). Notably, coordinate-wis BiClip consistently outperforms Le clipping, aligning with the results in Table 1.
How far should these results generalize? A word of caution is warranted against overgeneralization. These results are derived from a simplified regression model, limiting the ability to generalize the observed trends. Nevertheless, the experiments underscore the pronounced effects of heavy-tailed noise in a controlled synthetic environment and highlight the woise-mitigating capabilities of optimizers such as Adam, RMSProp, and BiClip. Additionally, it is important to note that real-world transformer models often comprise tens of millions to billions of parameters.
40

---

Efficient Distributed Optimization under Heavy-Tailld Noise
Syuthetic Pure (Non-Tolee Tokenized)
Synthetic t-Distribution (Non- Tokenized]
2.0
log 111, vi
(sa)
log( 10 x
1.5
1,0
Aug. 90.3
90D
Aog. Rccly B4
Akgual
Man 3GD
0.5
Aup Aan-
Mkes mit
Aog Aagul
sabe?
0.0
16
3
log(One Outer Node Steps)
log(Outer Node Steps)
Pure non-tokenized task
(b) Noised non-tokenized task
Synthetic Pure (Tokenized)
Synthetic t-Distribution (Tokenized)
2.5
log log(1lec vcc wi
2.5
Ang.
-5.0
BeCht (sa)
log 000
Ang- DiChp
Ang-
Macaal SGD
Abgall diCTt
Maga- S0Chip
Man 3G2
Ader- 5U21
10.0
Man BuCh
1.5
Mae Battyy
mapra- DiCla
BStthpp- BiC
12.5
Mere
log(Ounn Outer Node Steps)
log OOtee Node Steps)
(c) Pure tokenized task
(d) Noised tokenized task
Figure 4: (Top) The results the non-tokenized synthetic dataset presented. the absence of noise injection, Avg-Adam, Avg-SGD, and PiiSProo-BiClle demonstrate the most competitive performance. However, under heavy-tailed noise injection, CASProo--iClly and Adam- Adam-BiClip Biplip achieve the highest performance, while Avg-SGD exhibits among the poorest outcomes. Notably, oscillations observed in Adam-BiClip BiClip may reflect the impact of amplified update learning rates in the outer optimizer, potentially enabling finer- grained exploration of the optimization landscape. (Bottom) Tokenization drastically alters algorithmic performance. Without noise, Avg-SGD decays the fastest, while Avg-Adam converges to superior optimum. However, when synthetic, unbiased heavy-tailed noise introduced. Avg-St SGD becomes highly unstable, whereas Adam- BiClip and RMSProp- MiSProp-BiCllip consistently deliver the best results.
D.3. Transformer Encoders
The General Language Understanding Evaluation (GLUE) benchmark (Wang et al., 2019) serves a comprehensive framework for evaluating natural language understanding (NLU) models across diverse range of tasks. By incorporating datasets that span various linguistic challenges, GLUE provides rigorous testbed for assessing the generalization capabilities of NLP models. RoBERTa is state-of-the-art transformer-based model designed to enhance the performance of the original BERT architecture through improved pretraining strategies. Proposed by Liu et al. (2019), RoBERTa optimizes BERT by refining its training setup, enabling more robust natural language understanding (NLU) across diverse tasks.

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Table 3: Evaluation results on GLUE Benchmark datasets during test time. Metrics: CoLA (Matthews Correlation Coefficient, MCC), SST-2 (Accuracy), MRPC (AccuracyFI), STS-B (peearman/Peerson)) QQP (Accuracy/FI), MNLI (Accuracy), QNLI (Accuracy), RTE (Accuracy). Entries marked with 0.0 indicate the actual metric value (averaged across the granularity of each datapoint in the baseline dataset), which implies random guessing or failure to learn. Top first, second, and third best- perffornfgnnng algorithms are highlighted. We note that nested optimization algorithms utilizing adaptivity coordinate-wise BiClip both inner and outer optimizers generally achieve greater than 80% averaged performance (out of 100%). For Adam', " preconditioners are transmitted between the inner and outer optimizers, whereas DiLoCo requires maintaining preconditioners on the inner optimizers, both of which incur significant communication or memory overhead.
Algorithm
MNLI
QNLI
QQP (Aco/FI)
RTE
SST-2
MRPC (Acc/F1)
CoLA
STS-B (S/P)
Average
Avg-SGD (McMahan et al., 2017)
81.13
83.21
78.71/78.66 69
$7.40
90.94
67.30/80.52
0.0
26.76/28.20
61.17
Avg-L (Yang et al., 2022)
81.82
85.68
80. 80,00/79.8 82
54,51
91.97
68.38/81.22 .22
0.0
41.27/40.96 96
64.15
Arg-BiClip (L2)
81.95
86.16
84. 64.62/79.89
55,59
92.31
68.38/81.23
0.0
36,93/37 .22
64.03
Avg-Adagrad
84,70
88.79
87.09/83.34
64,26
93.34
71.56/82.63
27.72
81,93/8 133/1.22 2,26
76.97
Avg-Adam
84.97
89.47
87.66/84.09 .09
64,62
93.80
81.86/8777 74
41.41
86.21//6.55
80.76
AggBBiClip
85.08
89.45
87.8M84.1 12
66.06
94.03
71 71.32/82.45
41,40
48..8/84,48
79.12
Bi BiCClip (La)
84.31
89,20
86.36/82.60
72.20
93.34
52/99.29
60,02
82.41/83.00
82.74
Adagrad-SGD (Reddi al., 2021)
82.40
86.61
82.51/77.68
71.48
92.08
85.53/89.55 5252
47.80
40.37/42.24
72.69
RMSProp-SGD (Reddi et al., 2021)
84.20
88,46
87.12/83.30
72.56
91.85
85.50/89.11 17
$2.39
45.72/41.80
74.73
Adam-SGD (Reddi al., 2021)
82.93
86.98
85,99/80.85 87
66.78
90.71
87.01/90.08 09
49.93
44, 44/48/11.2 .26
73.37
Adam-L,Clip
82.54
86.69
85.88/80.72
59,92
89.67
85,29/89.99 90
48.54
69. 19/19.66.16
76.86
Adagrad-BiCly
85.54
90.02
88. 38.60/85.05 .5
73.36
93.23
85.78/89.88
48.87
84.03/85.00
82.75
RMSProp-BiClip
85.56
89.82
88. 38.50/88.44
70.75
93.69
84, 80V888 92
$0,99
87. 87.65/887.7
82.99
Adam-BiClip
84.26
89.20
88.64/84.74
69.67
92.43
86.52/90.09
56.12
82.83/79.71
82.20
Adam-BiClip (I2)
83.18
86.47
85.63/80.27
67.50
89.56
86.02/89.66
53.17
74.73/73.48
79.06
Adam² (Wang et al., 2021b)
85.11
88.87
89.04/85.51
71.48
92.66
87.50/91.00 1.03
$2.70
84.47/83.82
82.93
DiL,CCo (Douillard et al., 2024)
85.68
89.87
88.78/85.19
67.87
91.89
87.99/91.20
$4.77
85.93/84.76
83.08
CPipip
85.06
89.73
84.93/83.97
76.53
93.80
89.21/92.44
60.08
87.077886.89
84.52
D.4. Generative Models
We additionally evaluate our method using T5 (Raffel et al., 2020), a state-of-the-art text-to-text transformer model developed by Google Research. T5 unifies natural language processing tasks under a text-to-text framework, where both inputs and outputs are text strings, making it highly versatile across tasks such as summarization, translation, and classification. The model pretrained on the Colossal Clean Crawled Corpus (C4) using a span corruption objective and is available in multiple sizes, ranging from T5-Small (60M parameters) to T5-XXL (IBB parameters). This unified framework and scalability allow T5 to excel in wide range of tasks, making it strong baseline for evaluating our proposed method.
To evaluate machine translation tasks, we utilize the WMT datasets, a widely recognized benchmark for translation research (Foundation, 2019). Specifically, we finetune T5 on the TED Talks and News Commentary datasets. The TED Talks dataset, originally sourced from IWSLT 2017 (Cettolo et al., 2017), provides multilingual translations of TED Talk transcripts, offering diverse linguistic and domain-specifer challenges. In contrast, the News Commentary dataset contains parallel text derived from news articles in various languages, presenting more formal and structured domain. These datasets represent distinct styles and linguistic features, providing a rigorous evaluation of algorithm agility in optimizing across various domains or tasks.
Table 4: Evaluation results on machine translation benchmarks. Metrics reported are BLEU and METEOR scores for various language pairs across the TED Talks and News Commentary datasets. The final column represents the average score across all metrics for each algorithm.
Algorithm
TED Talks (en-de)
TED Talks (en-fr)
News Commentary (en-fr)
Average
BLEU
METEOR
BLEU
METEOR
BLEU
METEOR
Avg-SGD
28.02
58.52
27.48
54.67
30.07
54.13
42.15
Avg-L
28.99
58.94
29.66
57.40
31.02
56.73
43.79
29.41
59.18
30.70
58.13
31.79
57.69
44.48
Adam?
28.06
58.05
30.94
57.48
30.97
55.85
43.56
42

---

Efficient Distributed Optimization under Heavy-Tailld Noise
D.5. Performance under Non-IID Data
D.5.1. CUSTOM SHAKESPEARE DATASET
Though not the main focus of this work, in this section, we aim briefly evaluate the performance of TailOPT and baselines under non-datacenter, distributed environments. We utilized the LEAF repository (Caldas al., 2018), originally benchmark suite for federated learning, which provides datasets, tools, and baselines to evaluate algorithms under real- world conditions. LEAF emphasizes non-IlD data distributions, enabling the study of federated systems where data is naturally heterogeneous across smaller compute nodes. Among the datasets in LEAF, we modified the Shakespeare dataset, originally designed for next-character prediction, where each user now represented a character from Shakespeare's 's works. After preprocessing, the dataset contained 144 inner compute nodes, each corresponding to character's dialogue, with substantial variations sample sizes, vocabulary, and syntax across compute nodes. This structure mirrors the imbalanced, domain-specific data distributions often encountered federated learning. We modify the Shakespeare dataset by redefining the prediction task from next-character prediction to next-token predictions.
Table 5: Perplexity scores the Federated Shakespeare Next Word Prediction Task at 0.1 1 participation rate, for distilIGPT-2 architecture finetuning after 3 communication rounds.
Algorithm Avg-SGD
Avg-L,Clip
Avg-BiClip
RMSProp-BiClip
BiClip Adam?
Perplexity Score
1.9813
2.0126
1.7827
2.0054
1.9112
1.9445
D.5.2. CUSTOM PHILOSOPHER DATASET
To mitigate potential data leakage, we constructed a custom dataset, termed the Philosopher Dataset, to evaluate the non-IID setting and facilitate training from scratch. The Philosopher Dataset was syuthesized by allocating each literary work to one of eight compute nodes, followed by an 80-20 train-test split. These texts were open sourced from Project Gutenberg'. an extensive online repository offering over 75,000 classic or traditional books while strietly adhering to copyright protections.
Table Composition the Philosopher Dataset.
Title
Author
Translator
The Critique of Pure Reason
Immanuel Kant
J. Mciklejohn
The Collected Works of William Hazlitt, Volume One
William Hazlitt
The Works Jane Austen
Jane Austen
The Republic
Plato
Benjamin Jowett
War and Peace
Leo Tolstoy
The Federalist Papers
Alexander Hamilton, John Jay, James Madison
The Count of Monte Cristo
Alexandre Dumas
The Brothers Kuramazov
Fyodor Dostoevsky
Constance Garnett
We instantiated a shallower GPT-2 architecture comprising 2 layers, 256 embedding dimensions, and attention heads. This model was trained from scratch on the Philosopher Dataset. The training results are summarized Table
Table 7: Perplexity scores on the Philosopher Next Word Prediction Task at a 100% participation rate for the compressed GPT-2 architecture after 3 communication rounds.
Algorithm
Avg-SGD
Avg-L2Clip
Avg-BiClip
RMSProp-BiCUip
BPClip
Adam?
Perplexity Score
2.6361
2.1183
1.6266
1.7983
2.3488
2.5861
Discussion. In the synthesized non-III setting, we observe that algorithmic instantiations employing joint adaptivity or adaptive approximations-ic.. incorporating adaptivity or its efficient approximations at both the inner and outer optimizers- tend to underperform slightly. This aligns with the theoretical intuition that highly sensitive, rapidly adapting optimizers are more susceptible to unmitigated client drift, effectively overfitting to the biases of local data shards at the inner optimizers. However, Avg-BiClipg which integrates a clipping mechanism to regulate noise variance and stabilize optimization dynamics, exhibits notably robust performance. particular, Avg-BiCll achieves the strongest results in settings with high
Phttps://wwe http://www..tebbbe..orrggg
43

---

Efficient Distributed Optimization under Heavy-Tailed Noise
data heterogeneity across compute nodes, suggesting that BiClip mitigates not only noise variance but also client drift. We further compare these findings to results on the synthetic dataset (Appendix D.1) where noise-injected data were distributed IID across nodes, contrasting with the Shakespeare and Philosopher datasets. We note that the perplexities obtained are lower compared to those achieved on larger text datasets, such as WikiText- 103 or large-scale Common Crawl subsets (e.g.. distilIGPT' reportedly achieves a perplexity of around 16 on the WikiText- 103 benchmark, a long-term dependency language modeling dataset)*. This arises from the smaller size of the Shakespeare and Philosopher datasets in comparison to larger benchmarks. We provide the optimal hyperparameters for the non-IID experiments in Table 15.
D.6. Gradient Distributions
Figure highlights how gradient distributions can be distinctly altered by adaptive or clipping operations.
Avg-SD
Svg
Avg-SGD
Avg-GD
Avg
LogTFeonneng
Log (egTreeoeer))
Logt Teoopemar)))
Gradicat Nocm
Gindoat Nomm
Gradica
21
Crudlaat Numm
Gondant Norm
BPClip
BFCCip
BPCCiip
BFClip
BF-Clip
Log Leggeeennns)
Log Foggurnmo
Goullind
Chadiot
201
Gualiad
Coulina Nan
Gonlant Nam
Br"Ciip
B:CCii
BiCCkp
B:CClp
LogeEequen))
(eequeee))
"Gradeet Lg Noctn Adem!
Gradicns Norm Adlams?
Gradient h. North
Gradient Norm
Graebezz Nort Adlann?
Adamns
Adham
Logd LoofFroommm)) 22
Logf receeeny)) 2
Logg (rooreomme)))
Logi resuussc
Logd Froquemey))
Gralient Lg Nocm Adam?
Gradiaut Lg Noam Adamm
Gradient Lg Nocm Ademm!
Gradiaat Lg Norm Adimm!
Gontbet Lg Norm Aduam
Ton Prepueenn 1g.
Loo (eopueeee
500
12400
Grozzent Xg Norm
Gradbent I, Norm
Gradiezz Lg Norm
Gradienz I. Norm
Gradbent Ig Norm
Figure 5: Gradient statistics for MNLI across different algorithms for the first communication rounds, where rounds increase from left to right. (Top) We visualize local minihatch stochastic gradient distributions, where the outliers can dominate model updates upon outer aggregation. The BiClip and Adam optimizers mitigate this phenomenon. (Middle) Row 2 displays the local gradients accumulated from all inner optimizers during Clip prior to clipping. which uncovers the presence of outliers akin to those visible in Avg -GD. Row 3, the identical gradients are plotted after applying the coordinate- wise BiClip operation. We observe that BiClip stabilizes updates by rescaling large and small gradient coordinates, constraining model update lengths within a defined range. (Bottom) Similar to above, Row 4 shows the accumulated gradient lengths across all inner optimizers while training via Adama. Optimal inner optimizer learning rates are 0.0059, 0.5, and 1.8e-5 for Svg- Bi Clip, and Adam", respectively, with corresponding outer optimizer learning rates of and 3.2e-4 for the latter two algorithms. Test-time results show that Bi² Clip outperforms Adam². 2 which in turn outperforms Avg-SGD (Table 1). Finally, we note that upon centering, the aggregate update gradient histograms red depict the stochastic gradient noise distributions upon application of the optimizer strategy. BiClip attenuates the pure gradient noise (in blue) by projecting the noise distribution to an almost bell-shaped curve (in red), while Adam implicitly samples gradient noise from skewed distribution.
'https: / http//gtttttttttt//////////hht thub. com httts//ccco/gggggggggeee wwwpggiinnnaaeeeaaaaaaroo wtweeeerr/eeeeeeeeeeeeeeeeeeee distillation
44

---

Efficient Distributed Optimization under Heavy-Tailed Noise
D.7. Hyperparameter Sweep Grids
The sweep grids in Tables 8, 9 were determined by first performing a coarser sweep using an approximate grid, then localizing near the discovered well-perrogning hyperparameters.
Table 8: Hyperparameter sweeps gradient clipping parameters. u, i d inner optimizer u, d. o.u, d = outer optimizer u, d.
Algorithm
i.u
i.d
o_d
Avg-SGD
Aug-L,ClipSSGD
np.linspace(10 (10 1.5, 12)
0.0
Avg-BiClip
up. applinspace(10) (10m 1.5, 4)
np. app.lisspace11 4)
Avg-BiClip(La)
up. up.linspace (10 1.5, 4)
up mp.linspace(1U) 7, i.u, 4)
Avg-Adagrad
Avg-Adam
Adagrad-SGD
RMSProp-SGD
Adam-SGD
Adagrad-Bisd BiClip
ap.linspace(1011 1.5, 3)
np 1ppllinspace110 i.u,
RMSProp-BiCCH
np.linspace(10) (10 1.5, 3)
np.linspace( 10 7, u,
Adam-L,Clip
np.linspace(10) (10" 1.5, 12)
0.0
Adam-BiClip
np.logspace(-22 1, 5)
ap.llnspace(10 i_u, 3)
Adam-BiClip (L2)
up.linspacc(10 1.5, 3)
up ap.llispaace110= i.u, 3)
Adam?
CPC (Coordinate-wise)
up.linspacee10-11 1.5, 3)
ap.linspacee10- u. 3)
np.linsacce110 1.5, 3)
iinspaspcee110 u.
BPClip (Ta)
up.logspace 1, 0.5, 3)
up.linspace(11 7, i.u, 3)
up. up.logspace( -1, 0.5, 3)
np.linspace (10 o.u. 3)
DiLoCo
Table 9: Hyperparameter sweeps. ilr inner optimizer learning rate, outer optimizer learning rate, i inner optimizer e, seps = outer optimizer e. Additionally, oCo swept over the nesterov learning rates (0.9, 0.95), and inner optimizer weight decay parameters (10 10 1.10),,, *) as reported in prior works.
Algorithm
ilr
olr
ieps
oeps
Avg-SGD
up.logspace( 9, 1, 100)
Avg-L,Clip SGD
np.linspuce (10-) 10)
Avg-BiClip
np.linspace(10-9, 1, 10)
Avg-BiClip (Lz)
apllispacce100 10)
Avg-Adagrad
np.linspace(10 30)
(10-8, 10 10 10-2)
Avg-Adam
np.linspace(10-" 1,1,30)
[10-8, 10-0, 10-400440000 10-0,100-9 10-
Adagrad-SGD
np.linspace(11 0.1, 7)
np.logspace(-55 -1, 7)
{10- 10-5, 10-3)
RMSProp-SGD
np.linspace(10-3 0.1, 7)
mp.linspacc(10 10-5, 0.1, 7)
{10-7, 10-5, 10-3)
Adam-SGD
sp.linspace(10-11 0.1, 7)
np.logspace( -5, -1, 7)
10-5,,10-5,10 10-3)
Adagrad-BiClip
np.linspace(10) (10-5, 0.1, 4)
no.logspace( 5, -1, 4)
[10-7,1099, 10-3)
RMSProp-BiCkp
up.linspace(11 0.1, 4)
np.logspace( 5, 4)
(10-7,10-9, 10-
Adam-L;Clip
up.linspace(101 (100 0.1, 4)
np.linspace(1U) (10 0.1, 4)
1007,1002 10-3)
Adam-BiClip
np.logspuce( 6, -1,
np.logspace( 6, -1,
{10-7, 10-9, 10-3)
Adam- Blam-BiClipCC (L2)
ni.linspace 10-5, 0.1, 4)
hi.linnpace(10 10-5, 0.1, 4)
{10-?, 10-5, 10-3)
Adam?
logsopa) -1,
logsaacc
{10-7, 10 10-3)
(10- 10- 10
Bi Clip (Coordinate-wise)
np 1ppliispace(100 1, 3)
up.linspace (10spp 1, 3)
Bi BiClip (La)
logspucc (1,, 0.5,
np.logspace( 0.5,
DiLoCo
no.logspaco(- -5, -1, 5)
0.5. 1011. 10-110101 10-2)
{10- 10 10-3)
45

---

Efficient Distributed Optimization under Heavy-Tailed Noise
D.8. Optimal Hyperparameters
In this subsection, display the optimal hyperparameters located during our extensive sweep.
Table 10: Best hyperparameter selection over sweep of various parameter grids. 'ilr' inner optimizer learning rate, 'olr' optimizer learning rate, 'iep'' inner optimizer E, 'oeps' = outer optimizer e, 'o.u', 'o.d' outer optimizer u, d, 'iu', inner optimizer u, Here, is the adaptivity parameter in the denominator of adaptive optimizers to enhance stability of learning dynamics.
Algorithm
Dataset
ilr
oir
ieps
ocps
o_d
i.d
Avg-SGD
STS-B
0.019
RTE
0.095
QNLI
0.0059
QQP
0.0074
CoLA 0,019
SST-2
0.0074
MRPC
0.038
MNLI
0.0059
Clip
STS-B 0.56
RTE
0.14
0.0
QNLI 0.33
0.14
QQP
0.44
0.14
0.0
CoLA
0.33
0.14
SST-2
0.11
0.27
0.0
MRPC
0.22
0.41
0.0
MNLI
0.11
0.41
0.0
Avg-BiClip
STS-B
0.44
0.0001
0.0001
RTE
0.0001
6.7c-5
QNLI 0.44
0.0001
6.7e-5
QQP
0.56
0,0001
3.3e-5
CoLA 0.89
0.0001
0.0001
SST-2
0.56
0.0001
6.7e-5
MRPC
0.89
0.0001
6.7c-5
MNLI
0.56
0.0001
3.3c-5
Avg-BiClip (I2)
STS-B
0.067
0.75
0.75
RTE
0.0001
6.7e-5
QNLI 0.067
0.75
0.75
QQP
0.11
0.5
CoLA
0.067
0.75
0.75
SST-2
0.75
MRPC
0.11
1
MNLI
0.033
1.5
1.5
BrClip
STS-B
0.5
0.5
0.0001
0.0001
0.0001
1c-7
RTE
0.0001
0.0001
0.001
5e-5
QNLI
0.5
0.0001
0.0001
0.0001
5e-5
QQP
0.5
1.5
1c-7
0.0001
5e-5
CoLA
0.5
0.0001
0.0001
0.0001
0.0001
SST-2
0.5
0.75
1c-7
0.0001
1e-7
MRPC
0.0001
0.0001
0.0001
lc-7
MNLI
0.5
0.75
1c-7
0.0001
1c-7
(L2)
STS-B
0.56
0.05
0.1
0.05
RTE
0.1
0.56
0.1
0.1
0.56
0.56
QNLI
3.2
0.56
le-7
QQP
0.1
3.2
0.56
1e-7
0.56
0.56
CoLA
0.05
0.56
le-7
SST-2
0.56
0.1
3.2
3.2
0.1
le-7
MRPC
0.56
0.56
0.56
0.1
MNLI
0.1
0.56
3,2
1.6
0.56
le-7
46

---

Efficient Distributed Optimization under Heavy-Tailes Noise
Table 11: Best hyperparameter selection over a sweep of various parameter grids. 'ilr' inner optimizer learning rate, 'olr' = outer optimizer learning rate, 'ieps' inner optimizer 'oeps" outer optimizer 'o.u', 'o.d' outer optimizer u, d, 'i.',, 'idd' inner optimizer d. Here, e is the adaptivity s-smoothing parameter employed in the denominator of adaptive optimizers enhance stability of learning dynamics.
Algorithm
Dataset
ilr
oir
ieps
oeps
o_u
o.d
i.d
Adam-SGD
STS-B
0.017
4.6e-5
le-7
RTE
0.033
4.6e-5
le-7
QNLI
0.017
2.2e-4
le-7
QQP
0.017
2.2c-4
le-7
CoLA 0.033
0.001
le-5
SST-2
0.017
4.6e-5
1e-7
MRPC
0.017
4.6e-5
le-7
MNLI
0.017
2.2e-4
le-7
Adam-I-Clipp
STS-B 0.067
0.033
0.001
0.75
0.0
RTE
0.033
le-5
lc-7
1.5
0.0
QNLI
0.067
0.067
0.001
0.75
0.0
QQP
0.067
0.033
0.001
1.5
0.0
CoLA
0.1
0.033
0.001
0.75
0.0
SST-2
0.1
0,033
0.001
1.5
0.0
MRPC
0.033
0.033
0.001
0.75
0.0
MNLI
0.067
0.033
0.001
0.75
0.0
Adam-BiClip
STS-B
0.0056
3.2e-4
le-5
0.01
0,0067
RTE
3.2e-4
1.8e-5
le-7
0.01
0,0067
QNLI
0.0056
3.2e-4
1e-7
0.01
0.0067
QQP
0.0056
0.00032
le-7
0.01
0.0033
CoLA
0.0056
1.8e-5
1e-7
0.01
0.01
SST-2
0.0056
1.8e-5
1e-7
0.01
0.0067
MRPC
0.0056
0.0056
0.001
0.056
0.019
MNLI
0.0056
3.2e-4
le-5
0.01
0.0033
Adam-BiClip (T2)
STS-B
0.033
0.033
0.001
1.5
0.75
RTE
0.033
0.067
0.001
0.75
0.38
QNLI 0.033
0.067
0.001
1.5
0.75
QQP 0.067
0.033
0.0001
0.75
0.38
CoLA 0.033
0.033
0.001
1.5
0.75
SST-2 0.067
0,033
0.001
1.5
le-7
MRPC
0.033
0.033
0.001
1.5
1e-7
MNLI
0.067
0.033
0.001
1.5
0.75
Adam²
STS-B
1.8e-5
1.8e-5
le-5
le-7
RTE
1.8e-5
1.8e-5
le-5
le-7
QNLI
1.8e-5
3.2e-4
le-5
le-5
QQP
1.8e-5
3.2c-4
le-5
le-7
CoLA
1.8e-5
0.0056
le-5
0.001
SST-2
1.8e-5
1.8e-5
0.001
1e-7
MRPC
1.8e-5
1.8e-5
1e-5
1e-7
MNLI
1.8e-5
3.2e-4
le-5
le-7
47

---

Efficient Distributed Optimization under Hlaayy-Tailed Noise
Table 12: The notational setup is analogous to Table 11. For DiLoCo", provide the Nesterov learning rate and weight decay parameter the iu, id entries, respectively.
Algorithm
Dataset
ilr
olr
ieps
oeps
o.u
o.d
i.u
i.d
Adagrad-SGD
STS-B
0.017
0.0046
0.001
RTE
0.033
0.001
le-5
QNLI
0.017
0.001
le-5
QQP
0.017
0.0001
le-5
CoLA
0.017
2.2c-4
le-7
SST-2
0.017
2.2c-4
le-5
MRPC
0.017
2.2c-4
le-7
MNLI
0.017
0.0001
le-7
RMSProp-SGD
STS-B
0.017
le-5
1e-7
RTE
0.017
le-5
le-7
QNLI
0.033
0.001
le-5
QQP
0.017
le-5
le-7
CoLA 0.017
le-5
1e-7
SST-2
0.017
le-5
le-7
MRPC
0.033
le-5
le-7
MNLI
0.017
le-5
le-7
Adagrad-BiClip
STS-B
le-5
2.2c-4
le-7
1.5
1.5
RTE
0.033
2.2c-4
le-7
1.5
le-7
QNLI
1e-5
0.0046
0.001
1.5
1.5
QQP
le-5
0.0046
0.0001
1.5
1.5
CoLA
0.1
2.2c-4
le-7
0.0001
5e-5
SST-2
le-5
0.0046
0.001
1.5
1.5
MRPC
le-5
2.2c-4
1e-7
1.5
0.75
MNLI
le-5
0.0046
0.001
1.5
1.5
BiClip
STS-B
le-5
le-5
1e-7
1.5
1.5
RTE
0.067
le-5
1e-7
0.0001
5e-5
QNLI
0.1
le-5
le-7
0.0001
0.0001
QQP
0.1
0.0046
le-7
0.0001
5e-5
CoLA
0.1
0.0046
0.001
0.0001
1e-7
SST-2
0.1
le-5
le-7
0.0001
0.0001
MRPC
le-5
0.0046
0.001
0.75
0.75
MNLI
0.1
0.0046
0.001
0.0001
0.0001
DiLoCo*
STS-B
1.8e-5
0.7
le-5
0.9
0.1
RTE
1.8e-5
1
le-5
0.95
0.0001
QNLI
1.8e-5
le-5
0.9
0.0001
QQP
1.8e-5
le-5
0.95
0.0001
CoLA
1.8e-5
le-5
0.95
0.1
SST-2
1.8e-5
0.1
le-5
0.9
0.0001
MRPC
1.8e-5
0.7
le-5
0.9
0.1
MNLI
1.8e-5
1
le-5
0.9
0.1
48

---

Efficient Distributed Optimization under Hicayy-Tailed Noise
Table 13: Best hyperparameter selection over a sweep of various parameter grids for GLUE tasks. The notation is analogous to Table 11.
Algorithm
Dataset
ilr
olr
ieps
oeps
ou
iu id o
Avg-Adagrad
STS-B
3e-5
1e-8
RTE
1.5e-4
le-6
QNLI
3,3c-4
0.001
QQP
3.3e-4
0.001
CoLA
6.7e-5
le-6
SST-2
3.3e-4
0.001
MRPC
1.5c-4
le-6
MNLI
3.3e-4
0.001
Avg-Adam
STS-B
1.4e-5
le-6
RTE
3c-5
le-8
QNLI
6,2e-6
le-8
QQP
1.4e-5
1e-8
CoLA
6.2c-6
le-8
SST-2
6.2c-6
le-8
MRPC
3e-5
lc-8
MNLI
3e-5
0.0001
Table 14; Best hyperparameter selection sweep of various parameter grids for WMT. The conventions are identical with Tables 11-
13.
Algorithm
Dataset
ilr
olr
ieps
oeps
iu
idd
Avg-SGD
TED-T (en-de)
0.03
TED-T (en-fr)
0.015
NewsComm (cn-fr)
0.015
Avg-L2Clip
TED-T (en-de)
0.89
1.4
0.0
TED-T (en-fr)
0.89
0.55
0.0
NewsComm (en-fr)
0.78
0.41
0.0
BiClip
TED-T (en-de)
1
0.0001
0.0001
0.75
1e-7
TED-T (en-fr)
1
0.0001
0.0001
0.75
1e-7
NewsComm (en-fr)
0.5
1.5
1e-7
0.0001
5e-5
Adam2
TED-T (en-de)
3.2e-4
0.0056
le-7
0.001
TED-T (en-fr)
1.8e-5
1.8e-5
le-5
le-7
NewsComm (en-fr)
3.2e-4
0.0056
le-5
0.001
49

---

Efficient Distributed Optimization under Heavy-Tailed Noise
Table 15: Best hyperparameter selection over a sweep various parameter grids. conventions are identical with Tables 11-14.
Algorithm
Dataset
ilr
olr
ieps
oeps
d
Avg-SGD
Shakespeare 0.012
Philosopher
0.15
Avg-T.CClip
Shakespeare
0.56
0.55
0
Philosopher 1
0.41
0
Avg-BiClip
Shakespeare
1
0.0001
3.3e-5
Philosopher
1
0.0001
3.3e-5
RMSProp-BiClip
Shakespeare 0.067
2.2c-4
le-5
0.75
le-7
Philosopher
0.067
0.0046
0.001
0.75
le-7
BiiC
Shakespeare
1.5
le-7
0.0001
0.0001
Philosopher
1
1.5
1c-7
0.0001
5c-5
Adam?
Shakespeare
1.8c-5
0.0056
le-7
0.001
Philosopher
1.8e-5
0.0056
le-5
1e-5
50


Reviews:
[{"review_id": "M197VB9lor", "reviewer": "Reviewer_6e8Q", "summary": "The paper introduces TailOPT, a distributed optimization framework designed to handle heavy-tailed gradient noise in large-scale machine learning models. The authors propose a novel clipping mechanism, \\(BiClip\\), which performs coordinate-wise clipping to mitigate the effects of heavy-tailed noise without the memory and communication overhead of adaptive optimizers like Adam. The paper provides theoretical convergence guarantees for TailOPT under heavy-tailed noise and demonstrates its empirical effectiveness on several language tasks and models, outperforming state-of-the-art methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 6e8Q for their review. We appreciate the reviewer's acknowledgements about the strengths of our paper, particularly the novelty and efficiency of our proposed algorithm. \n\n**[Proof Challenges]** The challenges in the analysis lie in heavy-tailed noise with unbounded gradient variance and bias introduced by clipping. The core idea is to decompose model updates into descent directions and clipping bias. We carefully design clipping thresholds so that the bias introduced by thresholding diminishes asymptotically. We will incorporate the reviewer's feedback and further clarify key insights. \n\n**[Ablation Studies]** In our submission, we already conducted ablation studies on all components of TailOPT and explored most combinations (e.g., Avg-L2Clip vs Avg-BiClip to explore clipping strategies, Adam-SGD vs Avg-SGD to explore effects of outer optimizers, etc) in Section 6. For instance, Table 1 (or Table 10, Appendix H.1) shows the performance of many methods differing by inner/outer optimizers. We see that (a) our $BiClip$ can mitigate the negative effects of heavy-tailed noise while achieving Adam-like performance, and (b) $BiClip$ applied to both inner/outer optimizers ($Bi^2Clip$) outperforms all baselines. \n\nAdditionally, we include a summary table comparing communication/memory requirements for gradient statistics of different algorithms. The communication cost includes model parameters (dimension d). In particular, $Bi^2Clip$ achieves best performance, without incurring extra memory/communication cost compared with baselines. \n\n| Optimizer                  | Inner Memory | Outer Memory | Communication | Avg. GLUE |\n|---------------------------|-----------|-----------|-----------|-----------------|\n| Avg-SGD                   | d         | d         | d         | 61.17           |\n| RMSProp-SGD               | d         | 2d        | d         | 74.73           |\n| RMSProp-BiClip (TailOPT)  | d         | 2d        | d         | 82.99           |\n| $Adam^2$                     | 3d        | 3d        | 2d        | 82.93           |\n| DiLoCo                    | 3d        | 2d         | d         | 83.08           |\n| **$Bi^2Clip$ (TailOPT)**     | d         | d         | d         | **84.52**       |\n\n**[Practical Implementation]**  Our goal is not to develop distributed optimization methods that handle varying network latency or heterogeneous hardware. Instead, we focus on developing, analyzing, and evaluating a communication- and memory-efficient framework (TailOPT) that addresses heavy-tailed gradient noise. That said, we do evaluate TailOPT with node failures theoretically (Appendix D) and empirically (Appendix H.3). We see that under partial participation (e.g., Table 12), algorithms using BiClip achieve the top accuracies. Additionally, the lightweight and modular nature of TailOPT (e.g., table above) ensures ease of TailOPT deployment at scale in practical distributed systems. TailOPT is a stateless algorithm---no algorithm states need be maintained across communication rounds, which also makes it suitable for large-scale potentially resource-constrained settings. \n\n**[Bounded Deterministic Gradients]**  \nWe assume only the deterministic gradient $\\nabla F(x)$ is bounded, while the stochastic gradient $\\nabla F(x) + \\xi$ is unbounded due to heavy-tailed $\\xi$. The former is a common assumption in distributed optimization (e.g., [1-2]), where even the stochastic gradient variance is assumed bounded, a much stronger assumption. Additionally, our assumptions are much weaker than prior works which assume bounded variance on the heavy-tailed stochastic gradient (e.g., see lines 110-124) whereas we allow it to be unbounded. \n\n**[Other Questions & Related Work]**  \n- The additive form $F_i(x,\\xi) = F_i(x) + \\langle \\xi, x \\rangle$ follows from integrating $\\nabla F_i(x,\\xi) = \\nabla F(x) + \\xi$ where $\\xi$ models heavy-tailed noise (lines 134-140).  \n- Theorem 1 holds for all $\\beta_2 \\in [0,1)$, thus extending RMSProp-style results as the reviewer noted.  \n- We assume a fixed small $\\varepsilon$ in the analysis. For readability, we presented only the schedule-dependent terms in the theorem statement. In Theorem 6, setting $\\tau = 0$ invalidates convergence by exploding bounds (lines 1681-1694), which is consistent with empirical results highlighting the importance of the adaptivity parameter.\n- We will include discussions on the suggested references, which covers Adagrad-type algorithms. [3] assumes bounded variance and almost surely bounded gradients, a much stronger assumption, and [4] studies affine variance which is different from heavy-tailed.\n\n[1] Zaheer et al., Adaptive methods for nonconvex optimization, 2018\n\n[2] Reddi et al., Adaptive Federated Optimization, 2021\n\n[3] Kavis et al., High Probability Bounds for a Class of Non-Convex Algorithms with Adagrad Stepsize, 2022\n\n[4] Faw et al., Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD Affine variance, 2023", "claims_and_evidence": "seems OK", "methods_and_evaluation_criteria": "seems OK", "theoretical_claims": "I did not check the proof.", "experimental_designs_or_analyses": "It seems OK.", "relation_to_broader_scientific_literature": "The paper introduces TailOPT, a distributed optimization framework designed to handle heavy-tailed gradient noise (rather than the light-tailed gradient noise) in large-scale machine learning models.", "essential_references_not_discussed": "Some recent works related to AdaGrad could be discussed in the paper:\n\nKavis, Ali, Kfir Yehuda Levy, and Volkan Cevher. \"High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize.\" International Conference on Learning Representations.\nHong Y, Lin J. Revisiting convergence of AdaGrad with relaxed assumptions[C]//Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence. 2024: 1727-1750.\nFaw M, Rout L, Caramanis C, et al. Beyond uniform smoothness: A stopped analysis of adaptive sgd[C]//The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023: 89-160.", "other_strengths_and_weaknesses": "**Strengths:**\n1.  The proposed \\(BiClip\\) mechanism appears to be a new approach to handling heavy-tailed noise in distributed optimization, offering a memory-efficient alternative to adaptive optimizers.\n2. The paper provides rigorous convergence guarantees for TailOPT under heavy-tailed noise.\n3.  The authors conduct extensive experiments on synthetic and real-world datasets, demonstrating the practical effectiveness of TailOPT, particularly in large-scale settings.\n\n**Weaknesses:**\n1.  The paper is dense and difficult to follow, particularly in the theoretical sections. The presentation of the convergence proofs is overly complex, and the key insights are often buried under heavy notation and technical details. A more intuitive explanation of the main ideas would greatly improve readability.\n2. While the empirical results are promising, the paper lacks a thorough ablation study to isolate the impact of different components of TailOPT. Additionally, the comparison with state-of-the-art methods could be more comprehensive, particularly in terms of computational efficiency and scalability.\n3.  The paper does not sufficiently address the practical challenges of implementing TailOPT in real-world distributed systems. For example, the impact of network latency, node failures, and heterogeneous hardware on the performance of TailOPT is not discussed.\n4.  \"All the results implicitly assume that the gradient (or the function value gaps) is bounded, which is a somewhat strong assumption.\"", "other_comments_or_suggestions": "Line138Column1, the form $F_{i}(x,\\xi) = F_i(x) + \\langle \\xi,x \\rangle$ is a bit strange to me.\n\nTheorem 1, use \"Assumptions 1-2\", instead of \"assumptions 1-2\".", "questions_for_authors": "Does Theorem 1 hold for any $\\tilde{\\beta_2} \\in [0,1)$? Traditional convergence results for RMSProp typically requires that $\\beta$ is close to 1.\n\nIs it possible to remove the bounded gradient assumption in all the results?\n\nWhat is the dependency on $\\tau$ in the upper bound of Theorem 6?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vKHcb0nJVt", "reviewer": "Reviewer_QUNM", "summary": "The paper studies distributed optimization under commonly used schemes of local steps followed by global synchronization, and specifically addresses the issue of heavy-tailed gradient variance in this setting, which is a very relevant problem.\nAs a solutions clipping techniques are proposed to stabilize both inner and outer optimizers, achieving communication efficient training without the need to exchange gradient statistics.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer QUNM for the feedback and for finding our theoretical and empirical results convincing. We fully agree that addressing heavy-tailed gradient variance is a critical challenge, particularly in the context of training large-scale models such as LLMs. As the reviewer notes, the empirical performance of the novel $BiClip$ method (an instantiation of our proposed TailOPT framework) matches or exceeds that of Adam, while avoiding the substantial memory, communication, and compute costs associated with maintaining extra gradient statistics. Moreover, TailOPT is equipped with theoretical guarantees in the heavy-tailed regime with unbounded variance and local updates. We answer the reviewer’s clarification questions below.\n\n**[Clarification of Theory Sections]** \n\n- In response to the reviewer’s suggestions, we will clarify the “maximal rate at least” terminology to align with the formal statement in Theorem 6. Thank you for this feedback.\n- As discussed after Corollary 1, we compare our results with existing convergence rates of other algorithms. We will further expand the discussion comparing TailOPT to existing baselines, such as Avg+SGD, Adam+SGD, and Adagrad+SGD, which are currently known to converge only under bounded gradient noise. Furthermore, we note that the convergence of the advanced $Adam^2$ and DiLoCo algorithms under heavy-tailed noise remain unknown in prior works. Due to space constraints, we moved discussions around convergence of L2 Clip to Appendix C and Appendix D, but we will discuss connections in the main text in the next version. \n- We will also move the discussion from the Appendix (lines 1516-1522) regarding the generalization of BiClip to standard L2 Clipping into the main text, and expand it for clarity. We note that for proving the framework-wide convergence for TailOPT, we prove the bounds separately for various instantiations, including $Bi^2Clip$, RMSProp-$BiClip$, etc. That is, the $Bi^2Clip$ theoretical result does recover other TailOPT instantiations such as Adagrad-$BiClip$, as they are based on different inner and outer optimizers.", "claims_and_evidence": "The paper provides convincing theory and empirical results on relevant language modelling tasks (including finetuning Roberta and T5 respectively). Empirical results show Adam-like performance without the need to exchange gradient statistics, which is a valuable contribution.", "methods_and_evaluation_criteria": "yes, on both theory and experimental side", "theoretical_claims": "The clarity of the theoretical sections should be improved a bit:\n- clarifying terminology or \"maximal rate at least\" (it was more clear for Thm 6)\n- more closely putting it in context with the existing results for same algorithms in the case of more basic bounded noise, and for simple clipping instead of bi-clip\n- clarify how the bi-clip result recovers (or not) the tail-clip result (as it includes this setting as a special case?)\n\nI was not able to check the proofs, would have appreciated a brief comment on proof intuition/overview and related literature techniques", "experimental_designs_or_analyses": "The experimental results to me look convincing, and hyperparameter selection schedules in appendix are reasonable", "relation_to_broader_scientific_literature": "The work cites relevant sources appropriately as far as I can see", "essential_references_not_discussed": "(other reviewers might comment)", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "-", "questions_for_authors": "see theory section above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CCZepPJYsC", "reviewer": "Reviewer_y2B4", "summary": "The paper proposes a new optimization algorithm BiClip, for heavy-tailed stochastic optimization. Instead of bounding the upper bound of the gradient, the authors also propose to bound the gradient from below. Combining the clipping method with distributed SGD, the authors propose $Bi^2Clip$. The performance of the proposed method is good in the experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer y2B4 for their review. As the reviewer noted, TailOPT can be readily combined with a wide range of optimization strategies, which greatly enhances its practical applicability.  We propose several novel instantiations of TailOPT (such as $Bi^2Clip$) that achieves the strongest empirical performance without the extra memory/compute/communication overhead compared with baselines. Additionally, the TailOPT framework provides theoretical convergence guarantees under heavy-tailed noise with unbounded gradient variance and local updates, and these results have not appeared in prior works. \n\n**[No Decoder-Based Transformers?]** We clarify that our evaluations already include encoder-only (RoBERTa), encoder-decoder (T5), and decoder-only (GPT-2, DistillGPT) transformers. Results on decoder-based architectures (T5, GPT) are included in both Section 6 and Appendix H. For clarity, we summarize key empirical results below:\n\n- Section 6.1 (Synthetic Experiments, Full results in Appendix G.1): We carefully inject heavy-tailed noise into gradients via corrupted labels, simulating both a controlled heavy-tailed and non-heavy-tailed regime. Results show that TailOPT significantly outperforms Adam, with the performance gap widening under heavy-tailed conditions. Notably, we show that heavy-tailed noise destabilizes conventional training methods, a setting in which TailOPT instantions consistently demonstrate optimal performance.\n\n- Section 6.2 (GLUE Benchmark): Table 10 (expanded Table 1) extensively evaluates ~150 optimizer-dataset pairs. $Bi^2Clip$, which applies adaptivity to both inner/outer optimizers, consistently achieves the best performance. We find that the action of simply switching the inner optimizer from SGD to $BiClip$ yields approximately *10% gain on GLUE* ** *average* ** *with identical memory and communication cost*, highlighting the importance of TailOPT and heavy-tailed convergence in training modern transformer models.\n\n- Section 6.3 and Appendix H.2 (Machine Translation/Generation): TailOPT variants outperform $Adam^2$, DiLoCo, and FedAdam across nearly all machine translation tasks, while being more resource-efficient. Table 11 (expanded Table 2) confirms optimal performance of $Bi^2Clip$ on generative tasks via T5, and Appendix H.3 explores robustness under partial participation using GPT-2 and DistillGPT. Across all settings, algorithmic instantiations from TailOPT consistently achieve state-of-the-art performance.\n\n**[Other Questions]** We use $d$ to denote the coordinate dimension, following optimization literature conventions. The variables $u_t$ and $d_t$ represent “up” and “down” clipping thresholds, respectively. We are happy to revise notation to avoid confusion. \n\nRegarding hyperparameter tuning, TailOPT, particularly $Bi^2Clip$, is easy to tune. We use fixed clipping values across all iterations (lines 290-306) and sweep over only *three* grid values each for $u_t$ and $d_t$ for $Bi^2Clip$ (Table 3, Appendix G.5). For example, for MNLI, we sweep $d_t$ over {1e-7, 5e-5, 1e-4}, and the best performing validation accuracies are 0.850, 0.849, and 0.850, with barely any difference. Despite this minimal tuning effort, $Bi^2Clip$ exceeds state-of-the-art performance. In contrast, other baselines (such as Adam) requires careful tuning of more hyperparameters, that is, the learning rate, $\\beta_1$, $\\beta_2$, and $\\varepsilon$. Moreover, $BiClip$ requires only 33% of the memory used by Adam to store gradient statistics and even avoids the need to store or compute auxiliary gradient statistics at all, leading to significant improvements in memory, compute efficiency, and communication cost.\n\n**[Theoretical Results]** Assumptions are listed in Sections 3, 5, lines 145-164, 226-234 (L-smoothness, bounded $\\alpha$-moment) for the theorems and corollaries mentioned. We also believe the reviewer may have unintentionally interpreted our setting through the lens of the bounded stochastic gradient literature, where the state-of-the-art convergence rate for non-convex objectives is $\\mathcal{O}(T^{-1/2})$. However, these results **do not** generalize to the heavy-tailed regime with local updates (under the **unbounded** stochastic gradient variance assumption), which is the focus of our work. TailOPT is, to our knowledge, **the first general framework** to provably achieve this optimal rate under heavy-tailed noise, a setting that is highly relevant to training modern models such as large language models and large-scale transformers. Due to the unbounded variance in this regime, both the theoretical analysis and algorithmic design are significantly more challenging, which TailOPT addresses theoretically with convergence guarantees which are rigorously validated by empirical results. Our extensive evaluations further support these theoretical advantages, demonstrating consistent improvements over state-of-the-art baselines.\n\nWe are happy to answer any further questions.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, but only for the sketch of the proof.\n\n\n1. The assumptions used in Theorem 2 is unclear.\n\n2. The proposed algorithm does not seem to have theoretical benifit.", "experimental_designs_or_analyses": "Yes.\n\n1. The experiments on the Transfoemers are for encoder-based one. It would be better to have the experiments on decoder-based transformers.", "relation_to_broader_scientific_literature": "Powerful distributed algorithms can highly improve the model's ability for all model training in machine learning problems.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength:\n\n1. The proposed method can be easily combined with other optimization algorithms.\n\n2. the authors give the theorectical analysis to show the convergence of proposed method.\n\nWeakness: \n\n1. The algorithm introduce two more schedulers on the upper bound of gradient and lower bound for the gradient.", "other_comments_or_suggestions": "The notation $d_t$ for lower bound and notatin $d$ for the dimension of $x$ are confusing.", "questions_for_authors": "1. Can authors clearly state the assumptions in both theorem and corollaries in Section 5?\n\n2.Is the algorithm hard to tune? Can the author provide sentivity analysis for the $d_t$ and $u_t$.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces TailOPT, a distributed optimization framework for handling heavy-tailed gradient noise, along with a novel clipping mechanism (BiClip) that operates without incurring the memory and communication overhead of adaptive optimizers. The authors provide theoretical convergence guarantees under unbounded noise which is new to the best of my knowledge is new and validate their method on a range of language tasks, showing Adam-like performance with lower resource cost. There are no new hteoretical tools introduced, but the analysis and the presented results are interesting.

The technical contribution is clear and well-motivated, tackling a real problem in large-scale optimization where gradient variance could be heavy-tailed. The analysis is rigorous, though dense at times, and the empirical results are strong, well-structured, and comprehensive — including ablations, scalability analysis, and comparisons against both baselines and strong adaptive methods.
One reviewer questioned clarity and requested ablations, but the rebuttal shows these were already included in the submission.  Other reviewers found the work sound and practically relevant.  

I recommend acceptance but encourage the authors to address the minor clarity issues that were raised by the reviewers.
Decision: Accept (poster)