Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise

Menglian Wang, Zhuanghua Liu, Luo Luo · 2026

Read Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise by Menglian Wang, Zhuanghua Liu, Luo Luo (2026) 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-2601-11435.txt.

Introduction

Menglian Wang, Zhuanghua Liu, and Luo Luo speed learning across split machines. Their 2026 preprint tackles decentralized stochastic nonconvex optimization. The machines form a network with row-stochastic links. Each holds part of the data and part of the work.

Gradient noise in real tasks is often heavy-tailed. Wild outliers can wreck plain averaging across machines. The team gives a normalized stochastic gradient method for the case. It adds Pull-Diag gradient tracking to keep nodes in sync. The method reaches near-stationary points with optimal sample use. Communication cost stays near-optimal as well in their bounds. The work serves federated learning on messy real data.

Catalog record

CREATORMenglian Wang, Zhuanghua Liu, Luo Luo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-11435

Browse the full library · About the Tower of Babel

Full text

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

Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise Menglian Wang, Zhuanghua Liu, Luo Luo Abstract This paper studies decentralized stochastic nonconvex optimization problem over row-stochastic networks. We consider the heavy-tailed gradient noise which is empirically observed in many popular real-world applications. Specifically, we propose a decentralized normalized stochastic gradient descent with Pull-Diag gradient tracking, which achieves approximate stationary points with the optimal sample complexity and the near-optimal communication complexity. We further follow our framework to study the setting of undirected networks, also achieving the nearly tight upper complexity bounds. Moreover, we conduct empirical studies to show the practical superiority of the proposed methods. 1 Introduction This paper studies the decentralized stochastic nonconvex optimization problem \displaystyle\min_{{\bf{x}}\in\mathbb{R}^{d}}f({\bf{x}}):=\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}}) (1) over a connected network with n agents, where f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}} is the smooth local function on the i th agent with the form \displaystyle f_{i}({\bf{x}}):=\mathbb{E}_{{\bm{\xi}}_{i}\sim\mathcal{D}_{i}}[F({\bf{x}};{\bm{\xi}}_{i})]. We focus on the scenario that the local data \{{\bm{\xi}}_{i}\}_{i=1}^{n} exhibits the heterogeneous distributions \{{\mathcal{D}}_{i}\}_{i=1}^{n} and all n agents are connected by the topology of the directed graph [ 50 , 67 , 3 , 5 ] . Specifically, we consider local stochastic gradients with the heavy-tailed noise [ 49 , 70 , 14 ] , which is more general than the bounded variance assumption. Decentralized stochastic nonconvex optimization is widely employed for training large-scale machine learning models. However, most of the existing analyses are based on the assumption of bounded variance [ 68 , 19 , 54 , 33 , 18 , 24 ] , which has limitations in machine learning applications. For example, the stochastic gradient in the centralized training for language model [ 22 , 4 , 70 , 1 ] , and reinforcement learning [ 9 , 6 , 71 ] typically exhibits heavy-tailed noise, rather than bounded variance. Recently, the heavy-tailed gradient noise has also been observed in decentralized training [ 14 ] . Later, 66 proposed normalized stochastic gradient descent with momentum and gradient tracking for decentralized nonconvex optimization with heavy-tailed noise, while their results are restricted to undirected graphs. In real-world applications, the bidirectional communication protocol in a directed network may be difficult to implement because of the issues of nonuniform communication powers [ 63 ] and connectivity failures [ 65 ] . This motivates us to study decentralized optimization associated problems with the topology of directed graphs. Rather than doubly-stochastic mixing matrices for the undirected graph [ 48 , 52 , 20 , 33 , 68 ] , the communication in the directed graph is typically characterized by the column-stochastic or row-stochastic mixing matrices, leading to the efficient gossip protocols such as Push-Sum [ 38 , 39 , 55 , 69 , 56 , 58 , 3 , 46 , 50 , 17 , 21 ] , Push-Pull [ 43 , 60 , 61 , 59 , 45 ] , and Pull-Diag [ 35 , 62 , 10 , 32 , 57 ] . Based on these techniques, the recent works [ 25 , 26 ] establish the efficient stochastic first-order methods that achieve the optimal sample complexity for decentralized nonconvex optimization over directed graphs, while their results cannot address the heavy-tailed noise. Table 1: We compare the overall sample complexity and the communication complexity of existing decentralized stochastic first-order methods with our results, where we use the notations \tilde{\mathcal{O}}(\cdot) and \tilde{\Omega}(\cdot) to hide logarithmic factors, and 1-\beta denotes the (generalized) spectral gap of the mixing matrix. The expressions for the complexity of 66 are complicated, and a detailed discussion is deferred to Appendix D . Methods Sample Complexity Communication Complexity Networks Noise MG- Pull-Diag -GT [ 25 ] \mathcal{O}\!\left(\dfrac{L\sigma^{2}\Delta}{\epsilon^{4}}+\dfrac{L\Delta}{(1-\beta)\epsilon^{2}}\right) \tilde{\mathcal{O}}\!\left(\dfrac{L\sigma^{2}\Delta}{\epsilon^{4}}+\dfrac{L\Delta}{(1-\beta)\epsilon^{2}}\right) row-stochastic p=2 DeTAG [ 33 ] \mathcal{O}\!\left(\dfrac{L\sigma^{2}\Delta}{\epsilon^{4}}\right) \tilde{\mathcal{O}}\!\left(\dfrac{L\Delta}{(1-\beta)^{\frac{1}{2}}\epsilon^{2}}\right) doubly-stochastic p=2 DNSGD-PD (Theorem 1 ) \mathcal{O}\!\left(\dfrac{L\sigma^{\frac{p}{p-1}}\Delta}{\epsilon^{\frac{3p-2}{p-1}}}\right) \tilde{\mathcal{O}}\!\left(\dfrac{L\Delta}{(1-\beta)\epsilon^{2}}\right) row-stochastic p\in(1,2] DNSGD (Theorem 2 ) \mathcal{O}\!\left(\dfrac{L\sigma^{\frac{p}{p-1}}\Delta}{\epsilon^{\frac{3p-2}{p-1}}}\right) \tilde{\mathcal{O}}\!\left(\dfrac{L\Delta}{(1-\beta)^{\frac{1}{2}}\epsilon^{2}}\right) doubly-stochastic p\in(1,2] Lower Bounds [ 25 , 30 ] \Omega\!\left(\dfrac{L\sigma^{\frac{p}{p-1}}\Delta}{\epsilon^{\frac{3p-2}{p-1}}}\right) \tilde{\Omega}\!\left(\dfrac{L\Delta}{(1-\beta)\epsilon^{2}}\right) row-stochastic p\in(1,2] Lower Bounds [ 30 , 33 , 68 ] \Omega\!\left(\dfrac{L\sigma^{\frac{p}{p-1}}\Delta}{\epsilon^{\frac{3p-2}{p-1}}}\right) \Omega\!\left(\dfrac{L\Delta}{(1-\beta)^{\frac{1}{2}}\epsilon^{2}}\right) doubly-stochastic p\in(1,2] In this paper, we study the decentralized stochastic nonconvex optimization with heavy-tailed noise, i.e., the noise of the local stochastic gradient satisfies the p -th bounded central moment ( p -BCM) with p\in(1,2] . Specifically, we propose a normalized stochastic gradient descent with Pull-Diag gradient tracking for finding the \epsilon -stationary points over the row-stochastic network. Our method successfully captures the heavy-tailed local gradient noise to achieve the linear speedup with respect to the number of agents n , while the previous results of linear speedup only work for bounded variance setting, i.e., the special case of p -BCM with p=2 [ 33 , 68 , 25 ] . Concretely, we provide a theoretical analysis to show that the proposed method requires the overall sample complexity of \mathcal{O}(L\sigma^{\frac{p}{p-1}}\epsilon^{-\frac{3p-2}{p-1}}\Delta) and the communication complexity of \tilde{\mathcal{O}}(L(1-\beta)^{-1}\epsilon^{-2}\Delta) , where L is the smoothness parameter of local functions, \sigma is the noise level, \Delta is the initial function value gap, and 1-\beta is the generalized spectral gap of the mixing matrix for the row-stochastic network. It is worth noting that both our sample complexity and communication complexity (nearly) match the corresponding lower bounds [ 25 , 30 ] . For the specific bounded variance setting (i.e., p=2 ), the communication complexity of our method is even sharper than the result achieved by the best-known result [ 25 , 26 ] . We additionally follow the framework of our algorithm and analysis to address the problem over the undirected network, also achieving the optimal sample complexity and the near-optimal communication complexity. The comparison on the complexity bounds of our methods and existing results are summarized in Table 1 . We further conduct experiments on training the language models to demonstrate the superiority of proposed methods. 2 Related Work Decentralized stochastic optimization has been widely used in training the large-scale machine learning models, which allows the agent only communicates with its neighbors during the iterations [ 37 ] . Most of existing works focus on the assumption of bounded variance for local stochastic gradients [ 68 , 33 , 24 , 19 , 18 , 54 ] . For example, 33 and 68 combined the standard gradient tracking [ 38 , 44 , 40 ] with Chebyshev acceleration [ 27 , 2 ] to achieve nearly tight upper bounds on the sample complexity and the communication complexity for undirected networks. More recently, 26 , 25 introduced the extended gradient tracking technique such as PUSH-SUM [ 38 , 39 , 55 , 69 , 56 , 58 , 3 , 46 , 50 , 17 , 21 ] , and PULL-DIAG [ 35 , 62 , 10 , 32 , 57 ] to attain the optimal sample complexity for decentralized stochastic nonconvex first-order optimization over directed networks, while the communication complexity of these methods are not tight. The heavy-tailed gradient noise is empirically observed in many popular machine learning applications [ 22 , 4 , 70 , 1 , 9 , 6 , 71 ] , also in the decentralized training [ 14 ] . The algorithms and theory based on gradient clipping and normalization have been extensively studied to address the heavy-tailed noise in the centralized setting [ 12 , 11 , 47 , 13 , 70 , 41 , 7 , 29 , 16 , 31

Read the complete text