Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise
Not on the map. Why?
Abstract (arXiv)
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. For example, learning on language data typically leads to heavy-tailed gradient. To address these limitations, we develop a novel decentralized stochastic bilevel optimization algorithm for the nonconvex bilevel optimization problem under heavy-tailed noise. 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 noise 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 noise. The extensive experimental results confirm the effectiveness of our algorithm in handling heavy-tailed noise.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 45 of its 64 references that are in the map. First posted on arXiv 19 Sep 2025.
Builds on
45 of 64 references.
References · 45
- 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,897
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
- 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
- 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
- 2016Hyperparameter optimization with approximate gradientcited by 233
- 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
- 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
- 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
- 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 105
- 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 100
- 2023Linear attention is (maybe) all you need (to understand transformer optimization)cited by 98
- 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
33 more
- 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
- 2024SEAL: Safety-enhanced Aligned LLM Fine-tuning via Bilevel Data Selectioncited by 64
- 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
- 2022Advancing Model Pruning via Bi-level Optimizationcited by 56
- 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 51
- 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
- 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 43
- 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
- 2023First-order penalty methods for bilevel optimizationcited by 41
- 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
- 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
- 2023Revisiting the Noise Model of Stochastic Gradient Descentcited by 36
- 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
- 2024Getting More Juice Out of the SFT Data: Reward Learning from Human Demonstration Improves SFT for LLM Alignmentcited by 32
- 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
- 2023High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noisecited by 24
- 2022Decentralized Bilevel Optimizationcited by 23
- 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
- 2022On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Networkcited by 14
- 2024On the Complexity of First-Order Methods in Stochastic Bilevel Optimizationcited by 12
- 2022Taming Fat-Tailed ("Heavier-Tailed'' with Potentially Infinite Variance) Noise in Federated Learningcited by 10
- 2022Algorithmic Foundations of Empirical X-risk Minimizationcited by 8
- 2022INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networkscited by 8
- 2023A Single-Loop Algorithm for Decentralized Bilevel Optimizationcited by 7
- 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
- 2022Heavy-Tail Phenomenon in Decentralized SGDcited by 6
- 2025Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimizationcited by 5
- 2023Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problemscited by 4
- 2023Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimizationcited by 4
- 2024Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignmentcited by 4
- 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 4
- 2024SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimizationcited by 3
- 2024Fully First-Order Methods for Decentralized Bilevel Optimizationcited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.