# DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 38 references that are in the map.
- First posted on arXiv 19 Jun 2026.

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

- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [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)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [First-order penalty methods for bilevel optimization](https://mlsanity.com/paper/2301.01716/) (2023)
- [Bi-level Actor-Critic for Multi-agent Coordination](https://mlsanity.com/paper/1909.03510/) (2019)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [Will Bilevel Optimizers Benefit from Loops](https://mlsanity.com/paper/2205.14224/) (2022)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee](https://mlsanity.com/paper/2009.00690/) (2020)
- [Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2302.03407/) (2023)
- [Decentralized Bilevel Optimization](https://mlsanity.com/paper/2206.05670/) (2022)
- [Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity](https://mlsanity.com/paper/2210.12839/) (2022)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm](https://mlsanity.com/paper/2401.16164/) (2024)
- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network](https://mlsanity.com/paper/2206.15025/) (2022)
- [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023)
- [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)
- [DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization](https://mlsanity.com/paper/2212.02376/) (2022)
- [Convex Bi-Level Optimization Problems with Non-smooth Outer Objective Function](https://mlsanity.com/paper/2307.08245/) (2023)
- [A Single-Loop Algorithm for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2311.08945/) (2023)
- [Penalty-based Methods for Simple Bilevel Optimization under H"olderian Error Bounds](https://mlsanity.com/paper/2402.02155/) (2024)
- [CoBo: Collaborative Learning via Bilevel Optimization](https://mlsanity.com/paper/2409.05539/) (2024)
- [Achieving optimal complexity guarantees for a class of bilevel convex optimization problems](https://mlsanity.com/paper/2310.12247/) (2023)
- [An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization](https://mlsanity.com/paper/2402.08097/) (2024)

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

- [To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity](https://mlsanity.com/paper/2609.30501/) (2026)

## Abstract (arXiv)

Decentralized bilevel optimization (DBO) provides a powerful framework for multi-agent systems to solve local bilevel tasks in a decentralized fashion without the need for a central server. However, most existing DBO methods rely on lower-level strong convexity (LLSC) to guarantee unique solutions and a well-defined hypergradient for stationarity measure, hindering their applicability in many practical scenarios not satisfying LLSC. To overcome this limitation, we introduce a new single-loop DBO algorithm called diminishing quadratically-regularized bilevel decentralized optimization (DUET), which eliminates the need for LLSC by introducing a diminishing quadratic regularization to the lower-level (LL) objective. We show that DUET achieves an iteration complexity of O(1/T^1-5p-frac114τ) for approximate KKT-stationary point convergence under relaxed assumptions, where p and τ  are control parameters for LL learning rate and averaging, respectively. In addition, our DUET algorithm incorporates gradient tracking to address data heterogeneity, a key challenge in DBO settings. To the best of our knowledge, this is the first work to tackle DBO without LLSC under decentralized settings with data heterogeneity. Numerical experiments validate the theoretical findings and demonstrate the practical effectiveness of our proposed algorithms.