On the Interaction of Noise, Compression Role, and Adaptivity under ( L 0 , L 1 ) (L_{0},L_{1}) -Smoothness: An SDE-based Approach

Enea Monzio Compagnoni, Rustem Islamov, Antonio Orvieto, Eduard Gorbunov · 2025

Read On the Interaction of Noise, Compression Role, and Adaptivity under ( L 0 , L 1 ) (L_{0},L_{1}) -Smoothness: An SDE-based Approach by Enea Monzio Compagnoni, Rustem Islamov, Antonio Orvieto, Eduard Gorbunov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00181.txt.

Introduction

Enea Monzio Compagnoni and co-authors build a unified theory of distributed training that treats gradient noise, data compression, and adaptive updates together, in a 2025 paper. Large models are trained across many machines that must compress what they send, and each of these three factors is usually studied alone. Their joint behavior under a flexible smoothness condition was not well understood.

Using equations borrowed from stochastic calculus, the team derives continuous models that respect step-size limits more faithfully than earlier ones. Their results show that normalizing updates emerges naturally as the stable choice, with the right degree set by noise, landscape shape, and compression. A sign-based variant, they find, still converges even when the noise has heavy tails.

Catalog record

CREATOREnea Monzio Compagnoni, Rustem Islamov, Antonio Orvieto, Eduard Gorbunov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-00181

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Interaction of Noise, Compression Role, and Adaptivity under ( L 0 , L 1 ) (L_{0},L_{1}) -Smoothness: An SDE-based Approach Thanks: This manuscript is a work in progress: We welcome comments. Enea Monzio Compagnoni, Rustem Islamov, Antonio Orvieto, Eduard Gorbunov Abstract Using stochastic differential equation (SDE) approximations, we study the dynamics of Distributed SGD, Distributed Compressed SGD, and Distributed SignSGD under ( L 0 , L 1 ) (L_{0},L_{1}) -smoothness and flexible noise assumptions. Our analysis provides insights – which we validate through simulation – into the intricate interactions between batch noise, stochastic gradient compression, and adaptivity in this modern theoretical setup. For instance, we show that adaptive methods such as Distributed SignSGD can successfully converge under standard assumptions on the learning rate scheduler, even under heavy-tailed noise. On the contrary, Distributed (Compressed) SGD with pre-scheduled decaying learning rate fails to achieve convergence, unless such a schedule also accounts for an inverse dependency on the gradient norm – de facto falling back into an adaptive method. 1 Introduction Understanding the dynamics of stochastic optimization algorithms is crucial, especially in distributed machine learning settings where batch noise, compression, and adaptivity significantly impact convergence and generalization. Despite extensive studies in the literature, the interplay among these three aspects under the general condition of (L_{0},L_{1}) -smoothness remains underexplored. Contributions. Our key contributions include: • Establishing convergence bounds for Distributed SGD (DSGD), Distributed Compressed SGD (DCSGD), and Distributed SignSGD (DSignSGD) under the (L_{0},L_{1}) -smoothness condition; • Showcasing how normalizing the update step of D(C)SGD naturally emerges as a design strategy to ensure convergence, thus confirming the superiority of adaptive methods for ill-conditioned loss landscapes, especially for pathological batch noise or when unbiased compression is used; • Highlighting that an adaptive method such as DSignSGD converges even under heavy-tailed noise with standard assumptions on the learning rate scheduler. 2 Related work SDE Approximations and Applications. In ( Li et al. 2017 ) , a rigorous theoretical framework was introduced to derive SDEs that faithfully model the stochastic behavior intrinsic to optimization algorithms widely employed in machine learning. Since then, such SDE-based formulations have found application across several domains, including stochastic optimal control for tuning stepsizes ( Li et al. 2017 ; Li et al. 2019 ) and batch sizes ( Zhao et al. 2022 ) . Notably, SDEs have been instrumental in analyzing convergence bounds and stationary distributions ( Compagnoni et al. 2023 ; Compagnoni et al. 2024 ; Compagnoni et al. 2025b ) , scaling laws ( Jastrzebski et al. 2018 ; Compagnoni et al. 2025b ; Compagnoni et al. 2025a ) , implicit regularization effects ( Smith et al. 2021 ; Compagnoni et al. 2023 ) , and implicit preconditioning ( Xiao et al. 2024 ; Marshall et al. 2025 ) . Interplay of noise, compression, and adaptivity under (L_{0},L_{1}) -smoothness Previous research has extensively studied the effect of batch noise, compression, and adaptivity on the convergence of optimizers. Batch noise significantly influences stochastic gradient algorithms, affecting their convergence speed and stability Simsekli et al. 2019 ; Zhang et al. 2020a ; Kunstner et al. 2024 ; Compagnoni et al. 2025b . Noise characteristics such as heavy-tailed distributions have been shown to profoundly impact the optimization trajectories, necessitating robust algorithmic strategies Şimşekli et al. 2019 ; Gorbunov et al. 2021 . Compression methods, including unbiased techniques such as sparsification and quantization Alistarh et al. 2017 ; Stich et al. 2018 ; Mishchenko et al. 2024 and biased approaches like SignSGD Bernstein et al. 2018 ; Balles and Hennig 2018 , are critical for reducing communication overhead in distributed training. These compression techniques come with theoretical guarantees under various smoothness assumptions Alistarh et al. 2017 ; Gorbunov et al. 2020 ; Mishchenko et al. 2024 ; Compagnoni et al. 2025a . Adaptive methods such as SignSGD normalize gradient elements to cope effectively with large or heavy-tailed gradient noise, thus demonstrating improved empirical robustness Safaryan and Richtarik 2021 ; Compagnoni et al. 2025b ; Compagnoni et al. 2025a ; Kornilov et al. 2025 . However, most of the aforementioned works rely on restrictive assumptions such as L -smoothness, i.e., the L -Lipschitz continuity of the gradient. To relax this condition, Zhang et al. 2020a introduces and empirically validates the (L_{0},L_{1}) -smoothness assumption, which allows the norm of the Hessian to be bounded by an affine function of the gradient norm, thereby significantly expanding the class of admissible problems. Various (stochastic) first-order methods have been analyzed under (L_{0},L_{1}) -smoothness, including Clip-SGD and its variants Zhang et al. 2020a ; Zhang et al. 2020b ; Koloskova et al. 2023 ; Reisizadeh et al. 2025 ; Gorbunov et al. 2025 ; Vankov et al. 2025 , Normalized SGD and its variants Zhao et al. 2021 ; Chen et al. 2023 ; Hübler et al. 2024 , SignSGD Crawshaw et al. 2022 , AdaGrad Faw et al. 2023 ; Wang et al. 2023 , Adam Wang et al. 2022 ; Li et al. 2024 , and SGD Li et al. 2023 . In the context of compressed communication, Khirirat et al. 2024 proposed and analyzed a momentum-based variant of normalized EF21-SGD Richtárik et al. 2021 under the assumption of bounded noise variance. To the best of our knowledge, no study has jointly considered all these aspects, namely, batch noise, communication compression, and adaptivity, under the (L_{0},L_{1}) -smoothness condition. In particular, we consider flexible noise assumptions ranging from bounded to unbounded variance, and even encompassing heavy-tailed noise. Our work closes this gap by providing a comprehensive analysis of their interplay within a unified theoretical framework. 3 Preliminaries Distributed Setup. Let us consider the problem of minimizing an objective function expressed as an average of N functions: \min_{x\in\mathbb{R}^{d}}\left[f(x)\coloneqq\frac{1}{N}\sum_{i=1}^{N}f_{i}(x)\right] , where each f_{i}:\mathbb{R}^{d}\to\mathbb{R} is lower bounded and twice continuously differentiable, and represents the loss over the local data of the i -th agent. In our stochastic setup, each agent only has access to gradient estimates: let n_{i} be the number of datapoints accessible to agent i ; at a given x\in\mathbb{R}^{d} , agent i estimates \nabla f_{i}(x) using a batch of data \gamma_{i}\subseteq\{1,\dots,n_{i}\} , sampled uniformly with replacement and uncorrelated from the previously sampled batches. Given the sampling properties above, this estimate, which we denote by \nabla f_{i,\gamma_{i}}(x) , can be modeled as a perturbation of the global gradient: \nabla f_{i,\gamma_{i}}(x)=\nabla f(x)+Z_{i}(x) . Noise assumptions. We assume the sampling process and agent configurations are such that, for all x\in\mathbb{R}^{d} and each agent pair (i,j) with i\neq j , Z_{i}(x) is independent of Z_{j}(x) . Regarding assumptions on the noise structure, we always assume that at each x\in\mathbb{R}^{d} , Z_{i}(x) is absolutely continuous and with coordinate-wise symmetric distribution. If we discuss the setting Z_{i}(x)\in L^{1}(\mathbb{R}^{d}) , then we assume \mathbb{E}[Z_{i}(x)]=0 . Last, if Z_{i}(x)\in L^{2}(\mathbb{R}^{d}) , we denote \Sigma_{i}(x):=Cov(Z_{i}(x)) . Next, we define our two structural assumptions. The first one strictly concerns the global landscape; the second concerns how global landscape features affect the noise distribution of each agent. Definition 3.1 ( Zhang et al. 2020a ) . f is \left(L_{0},L_{1}\right) -smooth ( L_{0},L_{1}\geq 0 ) if, \forall x\in\mathbb{R}^{d} , \left\|\nabla^{2}f(x)\right\|\leq L_{0}+L_{1}\|\nabla f(x)\| . Definition 3.2 (Mod. of the assumptions from Schmidt and Roux 2013 ; Vaswani et al. 2019 )

Read the complete text