# Fully First-Order Methods for Decentralized Bilevel Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 75 references that are in the map.
- First posted on arXiv 25 Oct 2024.

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

- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [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)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [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)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications](https://mlsanity.com/paper/1705.06270/) (2017)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Generalized Inner Loop Meta-Learning](https://mlsanity.com/paper/1910.01727/) (2019)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Decentralized Training of Foundation Models in Heterogeneous Environments](https://mlsanity.com/paper/2206.01288/) (2022)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [learn2learn: A Library for Meta-Learning Research](https://mlsanity.com/paper/2008.12284/) (2020)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)

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

- [Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2509.15543/) (2025)

## Abstract (arXiv)

This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis showing that for n agents collaboratively solving the DSBO problem, the sample complexity of finding an ε-stationary point in our algorithm is O(n-1ε-7), which matches the currently best-known results of the single-agent counterpart with linear speedup. The numerical experiments demonstrate both the communication and training efficiency of our algorithm.