# Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks

arXiv: https://arxiv.org/abs/2206.10870 · HTML: https://mlsanity.com/paper/2206.10870/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 66 references that are in the map.
- First posted on arXiv 22 Jun 2022.

## Builds on (most cited first, 30 of 32)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization](https://mlsanity.com/paper/2105.02266/) (2021)
- [Multi-Level Stochastic Gradient Methods for Nested Composition Optimization](https://mlsanity.com/paper/1801.03600/) (2018)
- [Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems](https://mlsanity.com/paper/2106.13781/) (2021)
- [A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization](https://mlsanity.com/paper/2001.10669/) (2020)
- [Finite-sum Composition Optimization via Variance Reduced Gradient Descent](https://mlsanity.com/paper/1610.04674/) (2016)
- [Random gradient extrapolation for distributed and stochastic optimization](https://mlsanity.com/paper/1711.05762/) (2017)
- [Periodic Stochastic Gradient Descent with Momentum for Decentralized Training](https://mlsanity.com/paper/2008.10435/) (2020)

## Built on by (most cited first, 30 of 32)

- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity](https://mlsanity.com/paper/2210.12839/) (2022)
- [Achieving Linear Speedup in Non-IID Federated Bilevel Learning](https://mlsanity.com/paper/2302.05412/) (2023)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network](https://mlsanity.com/paper/2206.15025/) (2022)
- [SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learning](https://mlsanity.com/paper/2305.19442/) (2023)
- [Asynchronous Distributed Bilevel Optimization](https://mlsanity.com/paper/2212.10048/) (2022)
- [Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiation](https://mlsanity.com/paper/2302.04969/) (2023)
- [Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimization](https://mlsanity.com/paper/2211.07096/) (2022)
- [Communication-Efficient Federated Bilevel Optimization with Local and Global Lower Level Problems](https://mlsanity.com/paper/2302.06701/) (2023)
- [Network Utility Maximization with Unknown Utility Functions: A Distributed, Data-Driven Bilevel Optimization Approach](https://mlsanity.com/paper/2301.01801/) (2023)
- [A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2306.02422/) (2023)
- [Stochastic Bilevel Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2509.14952/) (2025)
- [A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming](https://mlsanity.com/paper/2211.04088/) (2022)
- [Argus: Federated Non-convex Bilevel Learning over 6G Space-Air-Ground Integrated Network](https://mlsanity.com/paper/2505.09106/) (2025)
- [DICE: Data Influence Cascade in Decentralized Learning](https://mlsanity.com/paper/2507.06931/) (2025)
- [Decentralized Hyper-Gradient Computation over Time-Varying Directed Networks](https://mlsanity.com/paper/2210.02129/) (2022)
- [Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning](https://mlsanity.com/paper/2307.05384/) (2023)
- [Fully First-Order Methods for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2410.19319/) (2024)
- [Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2509.15543/) (2025)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)
- [Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimation](https://mlsanity.com/paper/2306.01648/) (2023)
- [Achieving Linear Speedup in Decentralized Stochastic Compositional Minimax Optimization](https://mlsanity.com/paper/2307.13430/) (2023)
- [On the Communication Complexity of Decentralized Stochastic Bilevel Optimization](https://mlsanity.com/paper/2311.11342/) (2023)
- [Communication-Efficient and Privacy-Preserving Decentralized Meta-Learning](https://mlsanity.com/paper/2406.13183/) (2024)
- [A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2410.14115/) (2024)
- [Lossless Privacy-Preserving Aggregation for Decentralized Federated Learning](https://mlsanity.com/paper/2501.04409/) (2025)
- [CO-DEFEND: Continuous Decentralized Federated Learning for Secure DoH-Based Threat Detection](https://mlsanity.com/paper/2504.01882/) (2025)
- [From Federated Learning to X-Learning: Breaking the Barriers of Decentrality Through Random Walks](https://mlsanity.com/paper/2509.03709/) (2025)
- [A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2510.24710/) (2025)

## Abstract (arXiv)

Bilevel optimization have gained growing interests, with numerous applications found in meta learning, minimax games, reinforcement learning, and nested composition optimization. This paper studies the problem of distributed bilevel optimization over a network where agents can only communicate with neighbors, including examples from multi-task, multi-agent learning and federated learning. In this paper, we propose a gossip-based distributed bilevel learning algorithm that allows networked agents to solve both the inner and outer optimization problems in a single timescale and share information via network propagation. We show that our algorithm enjoys the O(frac1K ε2) per-agent sample complexity for general nonconvex bilevel optimization and O(frac1K ε) for strongly convex objective, achieving a speedup that scales linearly with the network size. The sample complexities are optimal in both ε and K. We test our algorithm on the examples of hyperparameter tuning and decentralized reinforcement learning. Simulated experiments confirmed that our algorithm achieves the state-of-the-art training efficiency and test accuracy.