Research map / Optimization / Distributed and compressed
Distributed Bilevel Optimization with Communication Compression
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.
Introduces the first distributed stochastic bilevel algorithms with unbiased communication compression (C-SOBA, CM-SOBA, EF-SOBA, and multi-step-compression variants), with convergence guarantees and ~10x communication reduction in experiments.
Problem
Distributed stochastic bilevel optimization suffers high communication overhead from transmitting full-dimensional hypergradient information each iteration, and no compressed bilevel algorithms existed; compression plus the nested-structure bias is hard to handle.
Approach
Adapt SOBA to the distributed setting with unbiased compressors (C-SOBA), then add a momentum step (CM-SOBA), error feedback on upper and lower levels (EF-SOBA), and multi-step compression to reach single-level compressed complexities, relaxing bounded-gradient and data-heterogeneity assumptions.
Key results
- Compressed algorithms (C-SOBA, CM-SOBA, EF-SOBA) achieve about 10x reduction in communicated bits without substantial accuracy loss on hyper-representation (MNIST MLP) and hyperparameter optimization under homogeneous data.
- Under heterogeneous data (Dirichlet alpha=0.1), C-SOBA and CM-SOBA degrade, while EF-SOBA's convergence and test accuracy are close to non-compressed NC-SOBA.
- EF-SOBA-MSC converges at O(sqrt(Delta) sigma/sqrt(nT) + (1+w_l+w_u)Delta/T) rate, matching the best-known single-level compressed complexities (EF21-SGDM, NEOLITHIC).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use communication compression in place of non-compressed distributed SOBA | C-SOBA, CM-SOBA, and EF-SOBA · Hyper-representation on MNIST and CIFAR-10; hyperparameter optimization on MNIST | communicated bits: 10× reduction | Helped |
| Use communication compression instead of non-compressed SOBA under homogeneous data | C-SOBA, CM-SOBA, and EF-SOBA · Hyper-representation and hyperparameter optimization | test accuracy: 10× reduction in communicated bits | No clear effect |
| Use C-SOBA or CM-SOBA under heterogeneous rather than homogeneous data | C-SOBA and CM-SOBA · Hyper-representation and hyperparameter optimization | convergence | Hurt |
| Add error feedback to CM-SOBA | CM-SOBA · Heterogeneous hyper-representation and hyperparameter optimization | convergence | Helped |
| Add error feedback to the compressed bilevel method | EF-SOBA · Heterogeneous hyper-representation on MNIST | test accuracy | Helped |
| Add momentum to C-SOBA (ablation) | C-SOBA · Distributed bilevel optimization | convergence rate: C-SOBA: $\mathcal{O}(1/\sqrt{nK})$; CM-SOBA: $\mathcal{O}(1/\sqrt{nK})$ | Helped |
| Add momentum to C-SOBA (ablation) | C-SOBA · Distributed bilevel optimization | assumption strength | Helped |
| Add error feedback to CM-SOBA (ablation) | CM-SOBA · Distributed bilevel optimization with heterogeneous data | dependence on data heterogeneity | Helped |
| Add multi-step compression to CM-SOBA (ablation) | CM-SOBA · Asymptotic computational complexity | gradient/Jacobian evaluations per worker: $\frac{(1+\omega)\sigma^2+\omega b^2}{n\epsilon^2}$ -> $\frac{\sigma^2}{n\epsilon^2}$ | Helped |
| Add multi-step compression to CM-SOBA (ablation) | CM-SOBA · Asymptotic communication complexity | communication rounds: $\frac{\omega b^2}{n\epsilon^2}+\frac{1+\omega/n}{\epsilon}$ -> $\frac{1+\omega}{\epsilon}$ | Helped |
| Add multi-step compression to EF-SOBA (ablation) | EF-SOBA · Asymptotic computational complexity | gradient/Jacobian evaluations per worker: $\frac{(1+\omega)^7\sigma^2}{n\epsilon^2}$ -> $\frac{\sigma^2}{n\epsilon^2}$ | Helped |
| Add multi-step compression to EF-SOBA (ablation) | EF-SOBA · Asymptotic communication complexity | communication rounds: $\frac{1+\omega+\omega^5/n}{\epsilon}$ -> $\frac{1+\omega}{\epsilon}$ | Helped |
Surprising findings
- Naively applying error feedback to lower-level compressors fails; the lower-level variables require unbiased gradient estimates, motivating a modified error feedback scheme.
Limitations
- Only compatible with unbiased compressors; biased contractive compressors such as Top-K are excluded.
- C-SOBA and CM-SOBA convergence depends on data heterogeneity bounds; EF-SOBA is harder to implement due to error feedback.
- Experiments are limited to small-scale MNIST and CIFAR-10 settings with MLP and CNN models.
Experimental setup
Datasets: MNIST CIFAR-10
Benchmarks: MNIST CIFAR-10
Metrics: test accuracy communicated bits running time
Baselines: NC-SOBA EF21-SGDM NEOLITHIC
Builds on: SOBA EF21-SGDM momentum-based variance reduction multi-step compression
Closest papers by meaning
- SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization (NeurIPS 2024 · similarity 0.89)
- Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- Locally Differentially Private Decentralized Stochastic Bilevel Optimization with Guaranteed Convergence Accuracy (ICML 2024 · similarity 0.88)
- DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity (ICLR 2025 · similarity 0.88)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.88)
- Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates (NeurIPS 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.