Research map / Optimization / Nonconvex and smooth optimization
DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DUET, a single-loop decentralized bilevel algorithm that handles non-unique lower-level solutions (no LLSC) via a diminishing quadratic regularization of the LL objective plus gradient tracking for heterogeneous data, with KKT-based stationarity analysis.
Problem
Decentralized bilevel optimization where lower-level objectives are convex but not strongly convex, so the LL solution may be non-unique and the hypergradient is ill-defined, with non-i.i.d. data across agents.
Approach
Augments each agent's LL objective with a diminishing quadratic regularizer (mu_t * (||x||^2+||y||^2)/2 + (1-mu_t) g_i), restoring strong convexity per iteration; reformulates the problem as a constrained problem with LL stationarity constraints and uses a KKT residual as stationarity measure, combined with gradient tracking for UL variables.
Key results
- DUET reaches iteration complexity O(1/T^{1-5p-11tau/4}) for approximate KKT stationarity, and O(1/T^{1-3p-11tau/4}) under a bounded-multiplier assumption; with p=1/7 this gives O(1/T^{2/7}) (about 3.5/eps communication rounds in the corollary).
- On decentralized MNIST meta-learning with i.i.d. data, DUET's test accuracy is reported as 6% higher than the DSGD baseline.
- With non-i.i.d. data, gradient tracking improves test accuracy for both DUET and DSGT versus their GT=0 counterparts.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DUET instead of decentralized stochastic gradient descent | Decentralized meta-learning · MNIST test accuracy, i.i.d. | test accuracy: 6% higher | Helped |
| Add gradient tracking (ablation) | DUET · MNIST test accuracy, non-i.i.d. | test accuracy | Helped |
| Add gradient tracking (ablation) | DSGT · MNIST test accuracy, non-i.i.d. | test accuracy | Helped |
| Add gradient tracking (ablation) | DUET · Pedagogical example | gradient convergence speed | Helped |
| Increase edge connection probability | DUET · Five-agent network, i.i.d. and non-i.i.d. | convergence | Helped |
Surprising findings
- On a toy problem, DSGT (which assumes ULSC) selects an LL solution that is good for the UL objective, whereas DUET selects one with a good LL objective value.
Limitations
- Convergence rates depend on bounded-multiplier assumption for the stronger O(1/T^{1-3p-11tau/4}) result, otherwise only the weaker rate holds.
- Rate is slower than LLSC-based DBO methods (e.g. O(1/T^{2/5}) and O(1/T^{2/7}) vs. standard rates), and the analysis requires step-size and parameter restrictions (p<1/6, tau<2/33).
- Experiments are small-scale (toy problem and MNIST with 5 agents) and do not include large-scale models.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: test accuracy gradient norm KKT residual
Baselines: DSGT DSGD SLDBO INTERACT
Builds on: SOBA sl-BAMM gradient tracking INTERACT
Closest papers by meaning
- SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization (NeurIPS 2024 · similarity 0.91)
- Problem-Parameter-Free Decentralized Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
- Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization (NeurIPS 2024 · similarity 0.88)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.88)
- Distributed Bilevel Optimization with Communication Compression (ICML 2024 · similarity 0.88)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.