Research map / Optimization / Nonconvex and smooth optimization
Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes D-NSVRGDA, a decentralized normalized stochastic variance-reduced bilevel algorithm (no clipping) with convergence guarantees for nonconvex (PL lower-level) decentralized bilevel optimization under heavy-tailed noise.
Problem
Decentralized stochastic bilevel optimization with nonconvex (PL) lower-level problems and heavy-tailed gradient noise, where standard finite-variance and strong convexity assumptions fail.
Approach
Combines normalized (not clipped) STORM-style variance-reduced gradient estimators with gradient tracking across workers, using a penalty-based minimax reformulation of the bilevel problem; analysis bounds optimization errors via function-value gaps rather than variable distances to handle normalized updates.
Key results
- Theorem gives O(1/T^{...}) iteration complexity scaling with 1/K (linear speedup) and 1/(1-λ)^2 spectral-gap dependence; recovers O(κ^10/ε^5) when s=2, K=1.
- Experiments on synthetic heavy-tailed data show D-NSVRGDA outperforms D-SVRGDA and D-SVRGDA-Clip across noise levels α in {0.2, 0.1, 0.05}, with clipping threshold hard to tune.
- On MLP and RNN pruning tasks (80% pruning), D-NSVRGDA consistently outperforms baselines in loss and accuracy/AUC.
Limitations
- Convergence bound only for expected gradient norm under PL and bounded-smoothness assumptions; does not match single-level STORM rate 1/T^{1/3}.
- Experiments are small-scale (synthetic data, small networks) with limited real-world evaluation.
- Clipping baseline sensitivity shows tuning difficulty; normalized method still requires many hyperparameters (step sizes, penalty, batch sizes).
Experimental setup
Datasets: synthetic Cauchy-noise binary classification synthetic Bernoulli common/rare features a9a covtype IMDB Sentiment140
Benchmarks: a9a covtype IMDB Sentiment140 synthetic Cauchy-noise dataset synthetic Bernoulli dataset
Metrics: upper-level loss value test accuracy test AUC
Baselines: D-SVRGDA D-SVRGDA-Clip D-F2BSA-1 D-F2BSA-5 D-F2BSA-10 D-F2BSA-VR DSBO MA-DSBO Gossip-DSBO VRDBO DSVRBGD DSGDA-GT
Builds on: STORM F2BSA clipped SGD batched-NSGDM
Closest papers by meaning
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.90)
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (NeurIPS 2024 · similarity 0.89)
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.89)
- Locally Differentially Private Decentralized Stochastic Bilevel Optimization with Guaranteed Convergence Accuracy (ICML 2024 · similarity 0.88)
- Distributed Bilevel Optimization with Communication Compression (ICML 2024 · similarity 0.88)
- Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.