Research map / Optimization / Nonconvex and smooth optimization
SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization
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 SPARKLE, a unified single-loop primal-dual framework for decentralized stochastic bilevel optimization that supports EXTRA, Exact Diffusion, and gradient-tracking variants with distinct strategies per level, with a unified convergence analysis.
Problem
x
Approach
A unified primal-dual framework with moving-average momentum on the upper-level gradient and separate communication matrices (A, B, C) for upper, lower, and auxiliary variables, so that EXTRA, Exact Diffusion, and GT variants can be plugged in and mixed across levels; the analysis covers all variants without bounded-gradient or bounded-heterogeneity assumptions.
Key results
- Theory: SPARKLE variants achieve O(1/sqrt(nK)) asymptotic rate and transient iteration complexity n^3/(1-rho)^2 for SPARKLE-EXTRA and SPARKLE-ED, versus max{n^3/(1-rho)^2, n^3b^2/(1-rho)^4} for D-SOBA under bounded heterogeneity.
- Analysis indicates EXTRA and Exact Diffusion outperform GT for decentralized bilevel optimization in transient iteration complexity.
- On FashionMNIST hyper-cleaning, SPARKLE-ED and SPARKLE-EXTRA achieve higher test accuracy than D-SOBA, MA-DSBO-GT, and MDBO, with ED and EXTRA outperforming GT.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EXTRA instead of GT for the upper-, lower-, and auxiliary-level updates | SPARKLE · Decentralized bilevel optimization | transient iteration complexity: \max\left\{ \frac{ n^3}{(1-\rho)^2}, \frac{ n}{(1-\rho)^{8/3}}\right\} -> \frac{ n^3}{(1-\rho)^2} | Helped |
| Use ED instead of GT for the upper-, lower-, and auxiliary-level updates | SPARKLE · Decentralized bilevel optimization | transient iteration complexity: \max\left\{ \frac{ n^3}{(1-\rho)^2}, \frac{ n}{(1-\rho)^{8/3}}\right\} -> \frac{ n^3}{(1-\rho)^2} | Helped |
| Use ED for lower- and auxiliary-level updates while retaining GT for the upper-level update | SPARKLE · Decentralized bilevel optimization | transient iteration complexity: \max\left\{ \frac{ n^3}{(1-\rho)^2}, \frac{ n}{(1-\rho)^{8/3}}\right\} -> \frac{n^3}{(1-\rho)^2} | Helped |
| Use a less connected topology for the upper-level variable while retaining connectivity for lower- and auxiliary-level variables | SPARKLE-EXTRA · FashionMNIST hyper-cleaning | test accuracy | No clear effect |
| Reduce connectivity of the lower- and auxiliary-level topology while keeping the upper-level topology fixed | SPARKLE-EXTRA · FashionMNIST hyper-cleaning | test accuracy | Hurt |
| Use ED or EXTRA rather than GT | SPARKLE · FashionMNIST hyper-cleaning | test accuracy | Helped |
| Use mixed ED-GT or EXTRA-GT updates rather than GT at all levels | SPARKLE · FashionMNIST hyper-cleaning | test accuracy | Helped |
| Use SPARKLE rather than MDBO or stochastic SLDBO | Distributed policy evaluation · Policy evaluation in reinforcement learning | sample complexity | Helped |
| Use SPARKLE rather than D-SOBA or MAML | Decentralized meta-learning · miniImageNet | training accuracy | Helped |
Surprising findings
- Using ED or EXTRA at the lower level with GT at the upper level improves transient iteration complexity over GT-only at all levels.
- Reducing topology connectivity for the upper variable x has little effect on performance, while reducing it for y and z degrades performance.
Limitations
- Only strongly-convex lower-level problems are supported.
- Performance depends on the condition number of the lower-level problem.
Experimental setup
Datasets: FashionMNIST miniImageNet
Benchmarks: FashionMNIST hyper-cleaning multi-agent MDP policy evaluation miniImageNet decentralized meta-learning
Metrics: test accuracy upper-level loss stationarity gap transient iteration complexity
Baselines: D-SOBA MA-DSBO-GT MDBO SLDBO MAML DSBO Gossip DSBO SLAM LoPA
Builds on: SOBA D-SOBA SUDA EXTRA Exact Diffusion
Closest papers by meaning
- DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity (ICLR 2025 · similarity 0.91)
- Problem-Parameter-Free Decentralized Bilevel Optimization (NeurIPS 2025 · similarity 0.90)
- Distributed Bilevel Optimization with Communication Compression (ICML 2024 · similarity 0.89)
- Locally Differentially Private Decentralized Stochastic Bilevel Optimization with Guaranteed Convergence Accuracy (ICML 2024 · similarity 0.88)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.87)
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling (NeurIPS 2024 · similarity 0.86)
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.