Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noises
Xinwen Zhang, Yihan Zhang, Hongchang Gao · 2025
Read Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noises by Xinwen Zhang, Yihan Zhang, Hongchang Gao (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-2509-15543.txt.
Introduction
Xinwen Zhang leads a team that trains models across many machines under harsh noise. Their problem has two levels: an outer choice shapes an inner training task. Past methods assumed the inner task was nicely curved and the noise was tame. Real language data breaks both hopes, with wild, heavy tailed noise.
Their method is a two level descent that steadies its steps by scaling, with no clipping tricks. It cuts noise by mixing past steps across machines that hold split data. They prove it converges, with new bounds for the tangled step sequences. This is the first such method with firm proof under heavy tailed noise. Tests confirm it handles that noise well.
Catalog record
| CREATOR | Xinwen Zhang, Yihan Zhang, Hongchang Gao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-15543
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noises Xinwen Zhang, Yihan Zhang, Hongchang Gao Abstract Existing decentralized stochastic optimization methods assume the lower-level loss function is strongly convex and the stochastic gradient noise has finite variance. These strong assumptions typically are not satisfied in real-world machine learning models. To address these limitations, we develop a novel decentralized stochastic bilevel optimization algorithm for the nonconvex bilevel optimization problem under heavy-tailed noises. Specifically, we develop a normalized stochastic variance-reduced bilevel gradient descent algorithm, which does not rely on any clipping operation. Moreover, we establish its convergence rate by innovatively bounding interdependent gradient sequences under heavy-tailed noises for nonconvex decentralized bilevel optimization problems. As far as we know, this is the first decentralized bilevel optimization algorithm with rigorous theoretical guarantees under heavy-tailed noises. The extensive experimental results confirm the effectiveness of our algorithm in handling heavy-tailed noises. 1 Introduction Stochastic bilevel optimization consists of two levels of optimization subproblems, where the upper-level subproblem depends on the optimal solution of the lower-level subproblem. It has received a surge of attention in recent years because it lays the optimization foundation for a series of machine learning models, such as model-agnostic meta-learning [ 9 ] , hyperparameter optimization [ 10 , 32 ] , imbalanced data classification [ 45 ] , reinforcement learning [ 37 , 22 ] , large language models [ 35 , 23 ] , etc. To facilitate stochastic bilevel optimization for distributed machine learning models, where data are distributed across different devices, a series of decentralized stochastic bilevel optimization algorithms have been developed in recent years. Specifically, in a decentralized setting, each device computes stochastic gradients based on its local training data to update the variables of both the upper-level and lower-level subproblems, and then communicates these updates with neighboring devices in a peer-to-peer manner. Compared to traditional single-level optimization problems, a unique challenge in decentralized stochastic bilevel optimization lies in computing the stochastic hypergradient—that is, the stochastic gradient of the upper-level loss function with respect to its variable. This challenge is caused by the unique characteristic of bilevel optimization: the upper-level subproblem relies on the optimal solution of the lower-level problem, which requires the global Hessian inverse matrix. To address this challenge, three categories of decentralized stochastic bilevel optimization algorithms [ 44 , 11 , 4 , 5 , 48 , 17 , 49 , 29 , 26 , 27 , 41 , 33 ] have been developed. The first category, such as [ 44 ] , uses the Neumann series expansion to approximate the Hessian inverse on each device and then communicates it between devices, suffering from high communication costs. The second category, such as [ 48 , 49 ] , estimates the Hessian-inverse-vector product by solving an auxiliary quadratic optimization problem on each device and then communicating this estimator, which helps reduce communication costs. However, both the first and second categories incur significant computational overhead due to the need to compute second-order Hessian information. The third category, such as [ 41 ] , addresses this challenge by reformulating the decentralized stochastic bilevel problem as a single-level optimization problem and then solving it with only first-order gradients. By avoiding the computation of second-order gradients, this category significantly reduces computational overhead. However, existing decentralized stochastic bilevel optimization algorithms suffer from significant limitations. First, these algorithms require the loss function of the lower-level subproblem to be strongly convex. This strong assumption is not satisfied by most practical machine learning models, such as deep neural networks, which are inherently nonconvex. Second, they assume the stochastic noise in the gradient has finite variance. However, existing studies [ 38 , 46 ] have demonstrated that this bounded variance assumption does not hold for the commonly used deep neural networks. In practice, the stochastic noise often follows a heavy-tailed distribution. Hence, these practical scenarios make existing algorithmic designs and theoretical foundations for decentralized bilevel optimization ineffective. It is therefore necessary to develop new decentralized stochastic bilevel optimization algorithms that can accommodate a broader range of machine learning models and establish solid theoretical guarantees. To this end, the goal of this paper is to develop an efficient decentralized stochastic bilevel optimization algorithm that avoids high communication costs and excessive computational overhead, and to establish its theoretical convergence rate for nonconvex bilevel optimization problems under heavy-tailed noise . Since the first-order methods in the aforementioned third category offer low computational overhead and communication costs, this paper focuses on the first-order method. For standard single-level optimization problems in the single-machine setting, a commonly used approach to handling heavy-tailed noise is Clipped SGD [ 46 ] , which mitigates the effect of heavy-tailed noise by clipping the norm of the stochastic gradient below a predefined threshold. Nevertheless, tuning the clipping threshold can be challenging. Recently, several works [ 28 , 15 , 40 ] have shown that the gradient normalization technique is sufficient to guarantee the convergence of stochastic gradient descent in-expectation under heavy-tailed noises without assuming bounded gradients. For instance, [ 15 ] proves that the batched normalized SGD (batched-NSGD) can converge in-expectation for a smooth nonconvex minimization problem under heavy-tailed noises, while [ 40 ] achieves a similar conclusion for NSGD using a stronger assumption, the individual Lipschitz smoothness. Additionally, [ 28 ] established the in-expectation convergence rate of the batched normalized stochastic gradient descent with momentum (batched-NSGDM) algorithm under heavy-tailed noises by innovatively bounding the accumulated noise from an online learning perspective. Since the aforementioned approaches only focus on the single-level optimization problem in the single-machine setting, they cannot be applied to decentralized stochastic bilevel optimization problems. In reality, there are several unique challenges as follows. 1. In bilevel optimization, multiple gradients interact with one another. Each of these gradients is affected by the heavy-tailed noise, which in turn impacts convergence. Therefore, it is challenging to control all of them and establish a convergence rate under heavy-tailed noises. 2. In the decentralized setting, the consensus error with respect to gradients is also affected by heavy-tailed noises. It remains unclear how to design algorithms and analyses that effectively control this noise to ensure convergence. 3. The aforementioned first-order method for bilevel optimization requires advanced gradient estimators, such as the variance-reduced gradient, to avoid the quite slow convergence rate under the finite variance assumption, as shown in [ 19 ] . However, no existing work for both single-level and bilevel problems has demonstrated that the advanced gradient estimator can ensure convergence under heavy-tailed noises without assuming bounded gradients. In summary, it is challenging to achieve a fast convergence rate for the first-order gradient-based decentralized bilevel optimization algorithm under heavy-tailed noises. To address these unique challenges, we develop a novel decentralized normalized stochastic gradient with variance reduction algorithm to solve Eq. ( 3.1 ). This algorithm only requires normalized first order gradients, making it more efficient and effective in handling heavy-tailed noise, which is lacking in existing second-order-based methods. Importantly, our algorithm demonstrates when gradient normalization should be applied in decentralized bilevel optimization. To the best of our knowledge, this is the first algorithm capable of handling heavy-tailed noise in bilevel optimization. We further establish the convergence rate of the developed algorithm under heavy-tailed noises. Specifically, to address challenges arising