Research map / Optimization / Distributed and compressed
Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity
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 OLGA and EF-OLGA, the first accelerated distributed methods combining unbiased/biased compression, local steps and Hessian similarity, with communication-time complexity improvements over prior SOTA.
Problem
Distributed optimization of strongly convex finite-sum objectives where communication is the bottleneck; prior methods combine at most two of compression, similarity and acceleration, and none combines all three for both unbiased and biased compressors.
Approach
Combines variance reduction (Katyusha/KatyushaX-style interpolation with a Bregman divergence) using gradient differences that exploit Hessian similarity, with compressed gradient-difference communication (unbiased compressors) or error feedback (biased compressors), yielding accelerated methods OLGA and EF-OLGA.
Key results
- For unbiased compressors, OLGA achieves communication time O~(1+[M^{-1/4}+omega^{-1/2}]sqrt(delta/mu)), dominating prior accelerated and similarity-based methods in CC-3.
- For biased compressors, EF-OLGA achieves communication time O~(1+beta^{1/4} sqrt(delta/mu)).
- Experiments on ridge and logistic regression (a9a, mushrooms) with varying M show OLGA outperforming AccSVRS, Accelerated ExtraGradient, ADIANA and LoCoDL in communication time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine unbiased compression, similarity, local steps, and acceleration | OLGA vs. AccExtraGradient · Distributed optimization | communication time (CC-3): $\tilde{\mathcal{O}} \left( 1+ M^{-\nicefrac{1}{4}}\sqrt{\nicefrac{\delta}{\mu}}\right)$ vs. $\tilde{\mathcal{O}}\left( | Helped |
| combine biased compression, similarity, local steps, and acceleration | EF-OLGA · Distributed optimization | communication time complexity: $\tilde{\mathcal{O}}\left( 1 + \beta^{\nicefrac{1}{4}}\sqrt{\frac{\delta}{\mu}}\right)$ | Helped |
| use client sampling with similarity and local steps | AccSVRS vs. OLGA · Distributed optimization | communication time (CC-3): $\tilde{\mathcal{O}} \left( 1+M^{-\nicefrac{1}{4}}\sqrt{\nicefrac{\delta}{\mu}} \right)$ vs. $\tilde{\mathcal{O}}\left( | Hurt |
Limitations
- Assumes strong convexity of the mean objective and Hessian similarity across nodes; experiments limited to linear models.
- For biased compressors, no lower bound is known and the analysis does not match the unbiased rate in terms of M.
- Experiments restricted to RandK sparsification and small LibSVM datasets.
Experimental setup
Datasets: a9a mushrooms
Benchmarks: a9a mushrooms
Metrics: communication time (CC-3) communication rounds (CC-1) client-server communications (CC-2)
Baselines: ADIANA ECLK LoCoDL TAMUNA Accelerated ExtraGradient AccSVRS Three Pillars Algorithm Optimistic MASHA
Builds on: KatyushaX DIANA ADIANA EF21 Accelerated ExtraGradient
Closest papers by meaning
- EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization (NeurIPS 2022 · similarity 0.93)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.91)
- Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.90)
- Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (NeurIPS 2024 · similarity 0.90)
- Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.90)
- Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning (ICML 2025 · similarity 0.89)
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.