# Decentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2024.

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

- [LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace](https://mlsanity.com/paper/2404.03331/) (2024)
- [A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2410.14115/) (2024)
- [Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning](https://mlsanity.com/paper/2511.19513/) (2025)
- [BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization](https://mlsanity.com/paper/2605.10288/) (2026)
- [S3LDBO: A Snapshot Single-Loop Algorithm for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2605.31311/) (2026)

## Abstract (arXiv)

Stochastic bilevel optimization (SBO) is becoming increasingly essential in machine learning due to its versatility in handling nested structures. To address large-scale SBO, decentralized approaches have emerged as effective paradigms in which nodes communicate with immediate neighbors without a central server, thereby improving communication efficiency and enhancing algorithmic robustness. However, most decentralized SBO algorithms focus solely on asymptotic convergence rates, overlooking transient iteration complexity-the number of iterations required before asymptotic rates dominate, which results in limited understanding of the influence of network topology, data heterogeneity, and the nested bilevel algorithmic structures. To address this issue, this paper introduces D-SOBA, a Decentralized Stochastic One-loop Bilevel Algorithm framework. D-SOBA comprises two variants: D-SOBA-SO, which incorporates second-order Hessian and Jacobian matrices, and D-SOBA-FO, which relies entirely on first-order gradients. We provide a comprehensive non-asymptotic convergence analysis and establish the transient iteration complexity of D-SOBA. This provides the first theoretical understanding of how network topology, data heterogeneity, and nested bilevel structures influence decentralized SBO. Extensive experimental results demonstrate the efficiency and theoretical advantages of D-SOBA.