# DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 59 references that are in the map.
- First posted on arXiv 5 Dec 2022.

## Builds on (most cited first, 26 of 26)

- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [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)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [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)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [Bi-level Actor-Critic for Multi-agent Coordination](https://mlsanity.com/paper/1909.03510/) (2019)
- [Penalty Method for Inversion-Free Deep Bilevel Optimization](https://mlsanity.com/paper/1911.03432/) (2019)
- [Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1905.05920/) (2019)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [A Decentralized Proximal Point-type Method for Saddle Point Problems](https://mlsanity.com/paper/1910.14380/) (2019)
- [BOML: A Modularized Bilevel Optimization Library in Python for Meta Learning](https://mlsanity.com/paper/2009.13357/) (2020)
- [INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks](https://mlsanity.com/paper/2207.13283/) (2022)
- [Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks](https://mlsanity.com/paper/1812.04048/) (2018)

## Built on by (most cited first, 7 of 7)

- [Network Utility Maximization with Unknown Utility Functions: A Distributed, Data-Driven Bilevel Optimization Approach](https://mlsanity.com/paper/2301.01801/) (2023)
- [DePRL: Achieving Linear Convergence Speedup in Personalized Decentralized Learning with Shared Representations](https://mlsanity.com/paper/2312.10815/) (2023)
- [Argus: Federated Non-convex Bilevel Learning over 6G Space-Air-Ground Integrated Network](https://mlsanity.com/paper/2505.09106/) (2025)
- [A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization](https://mlsanity.com/paper/2605.09094/) (2026)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)
- [First-order Constrained Trilevel Optimization Over Distributed Networks for Robust Coreset Selection](https://mlsanity.com/paper/2607.27632/) (2026)
- [Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level](https://mlsanity.com/paper/2608.12704/) (2026)

## Abstract (arXiv)

Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys O(ε-3/2) in sample and communication complexities for achieving an ε-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.