Research map / Optimization / Nonconvex and smooth optimization
Problem-Parameter-Free 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 AdaSDBO, a single-loop, problem-parameter-free decentralized bilevel optimizer that uses cumulative gradient-norm adaptive stepsizes with gradient-norm-accumulator tracking, achieving O(log^4(T)/T) convergence.
Problem
Decentralized bilevel optimization typically requires problem-specific constants (smoothness, strong convexity, spectral gap) to set stepsizes, which are usually unavailable in practice, forcing manual tuning.
Approach
A single-loop decentralized bilevel method where primal, dual, and auxiliary variables use AdaGrad-norm-style stepsizes built from accumulated local gradient norms (hierarchically ordered via max of accumulators), with the accumulators themselves consensus-tracked over the network so stepsize inconsistencies are controlled.
Key results
- Theoretical convergence rate O(log^4(T)/T) and gradient complexity O(1/eps log^4(1/eps)) without problem-specific parameters, matching well-tuned single-loop methods up to polylog factors.
- On hyperparameter optimization with MNIST/FMNIST and synthetic data, AdaSDBO reaches competitive or faster convergence than SLDBO, MA-DSBO, MDBO, and DBO.
- Test accuracy remains stable across stepsizes from 1e-3 to 1e2, while baselines have narrower stable regions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use AdaSDBO instead of FSLA | Decentralized bilevel optimization · Theoretical comparison | convergence rate | Helped |
| use AdaSDBO instead of FSLA | Decentralized bilevel optimization · Theoretical comparison | gradient complexity | Helped |
| use AdaSDBO instead of AID | Decentralized bilevel optimization · Theoretical comparison | convergence rate | No clear effect |
| use AdaSDBO instead of AID | Decentralized bilevel optimization · Theoretical comparison | gradient complexity | No clear effect |
| use AdaSDBO instead of DBO and MA-DSBO | Decentralized bilevel optimization · Synthetic data, low heterogeneity; p=50 and p=200 | convergence speed | Helped |
| use AdaSDBO across a wider range of initial stepsizes | Decentralized bilevel optimization methods · Synthetic, MNIST, and FMNIST | stepsize robustness | Helped |
| use AdaSDBO instead of SLDBO | Decentralized meta-learning · CIFAR-10 | training accuracy | Helped |
Limitations
- Analysis restricted to deterministic full-gradient settings
- Assumes strongly convex lower-level problem
- Stochastic and generally convex lower-level extensions left open
Experimental setup
Datasets: MNIST FMNIST CIFAR-10 synthetic Gaussian data
Benchmarks: MNIST FMNIST CIFAR-10 synthetic data
Metrics: test accuracy convergence rate gradient complexity robustness across stepsizes
Baselines: SLDBO MA-DSBO MDBO DBO
Builds on: AdaGrad-Norm SLDBO MA-DSBO MDBO DBO
Closest papers by meaning
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.91)
- DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity (ICLR 2025 · similarity 0.91)
- SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization (NeurIPS 2024 · similarity 0.90)
- A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation (NeurIPS 2025 · similarity 0.89)
- Locally Differentially Private Decentralized Stochastic Bilevel Optimization with Guaranteed Convergence Accuracy (ICML 2024 · similarity 0.89)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (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.