Research map / Optimization / Distributed and compressed
Locally Differentially Private Decentralized Stochastic Bilevel Optimization with Guaranteed Convergence Accuracy
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 a locally differentially private decentralized stochastic bilevel optimization algorithm (LDP-DSBO) that avoids nested consensus loops, achieving finite cumulative privacy budget and convergence accuracy under decaying Laplace noise.
Problem
Decentralized stochastic bilevel optimization leaks sensitive data through shared updates, and nested-loop consensus makes differential privacy budgets explode, while existing DP methods sacrifice convergence accuracy.
Approach
A single-loop decentralized bilevel algorithm (no nested consensus) that estimates the Hessian-inverse-vector product locally and injects decaying Laplace noise per agent, so the cumulative local DP budget stays finite while the optimization error still vanishes.
Key results
- Under DP noise on a 10-agent ring with the synthetic dataset, the proposed algorithm reaches lower training loss and higher test accuracy than MA-DSBO and GBDSBO.
- On MNIST under DP constraints, GBDSBO fails to train (losses diverge) while the proposed method trains; on CIFAR-10 meta-learning, MA-DSBO fails to train while the proposed method achieves better accuracy.
- Convergence rates O(T^-(1-vx)) for convex and nonconvex F and O(T^-beta1) for strongly convex F, with privacy budget finite as T grows to infinity; complexity O(max{p,q} delta^-2.6) in nonconvex case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LDP-DSBO instead of MA-DSBO or GBDSBO | Hyperparameter optimization on the synthetic dataset · Synthetic dataset | training loss | Helped |
| Use LDP-DSBO instead of MA-DSBO or GBDSBO | Hyperparameter optimization on the synthetic dataset · Synthetic dataset | test accuracy | Helped |
| Use LDP-DSBO instead of MA-DSBO | Hyperparameter optimization · MNIST | training loss | Helped |
| Use LDP-DSBO instead of MA-DSBO | Hyperparameter optimization · MNIST | test accuracy | Helped |
| Use LDP-DSBO instead of MA-DSBO | Decentralized meta-learning · CIFAR-10 | test accuracy | Helped |
| Use LDP-DSBO instead of VRDSBO | Hyperparameter optimization · Heterogeneous lower-level objectives | performance | Helped |
| Change network topology | LDP-DSBO · Synthetic and MNIST datasets | performance | No clear effect |
| Increase data-distribution heterogeneity | LDP-DSBO · Synthetic dataset | test accuracy | Hurt |
| Increase data-distribution heterogeneity | LDP-DSBO · MNIST | test accuracy | Mixed |
| Avoid estimating the full Hessian or Jacobian matrix | LDP-DSBO · DSBO problem | computational complexity: O(pq log(δ−1)δ−3) -> O(max{p, q}δ−2.6) | Helped |
| Avoid nested consensus loops | LDP-DSBO · DSBO problem | cumulative privacy budget | Helped |
Surprising findings
- The proposed algorithm's convergence accuracy is not sacrificed for privacy: the optimization error vanishes despite DP noise, unlike single-level LDP methods.
- GBDSBO and MA-DSBO diverge under DP noise on MNIST and CIFAR-10 settings where the proposed method still trains.
Limitations
- Privacy is achieved at the cost of a reduced convergence rate, which depends on the privacy budget (Corollary 4.7).
- Requires Lipschitz gradient-norm style assumptions for DP sensitivity (Assumption 4.4), stricter than the convergence assumptions.
- Experiments are limited to a 10-agent ring network with small-scale models and datasets.
Experimental setup
Datasets: synthetic logistic regression data MNIST CIFAR-10
Benchmarks: synthetic dataset MNIST CIFAR-10
Metrics: training loss test loss test accuracy convergence rate
Baselines: MA-DSBO GBDSBO VRDSBO
Builds on: Chen et al. 2023 MA-DSBO Ghadimi & Wang 2018 BSA Huang et al. 2015 differential privacy sensitivity lemma Wang & Nedić 2023 Chen & Wang 2023
Closest papers by meaning
- Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates (NeurIPS 2025 · similarity 0.93)
- Problem-Parameter-Free Decentralized Bilevel Optimization (NeurIPS 2025 · similarity 0.89)
- Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- Distributed Bilevel Optimization with Communication Compression (ICML 2024 · similarity 0.88)
- SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization (NeurIPS 2024 · similarity 0.88)
- DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity (ICLR 2025 · 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.