Research map / Optimization / Distributed and compressed
Exploiting Similarity for Computation and Communication-Efficient Decentralized 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 SPDO and Accelerated-SPDO, proximal decentralized optimization methods whose subproblems can be solved coarsely while keeping communication complexity tied to the average dissimilarity δ, with refined convex and strongly convex analyses.
Problem
Decentralized optimization needs low communication complexity, and existing proximal decentralized methods (SONATA-style) require highly accurate local proximal subproblem solutions, causing high computation; their communication analysis also depends on the maximum dissimilarity δ_max rather than av
Approach
Modify the proximal decentralized update (stabilized variable update with an added gradient-tracking term) so that subproblems need only coarse accuracy that does not tighten over rounds; combine with Monteiro-Svaiter acceleration and fast gossip, and bound communication by average similarity δ instead of δ_max.
Key results
- Accelerated-SPDO achieves communication complexity Õ(sqrt(δ/(μ(1-ρ)))) and computation Õ(sqrt(L/μ) log(1/ε)) in the strongly convex case, versus Õ((log 1/ε)^2) computation for Inexact Accelerated SONATA.
- SPDO matches Inexact-PDO communication complexity while needing fewer local computations, per the MNIST experiments.
- Analysis reduces the communication dependence from δ_max to average dissimilarity δ, which can be up to sqrt(n) times smaller.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SPDO instead of Inexact-PDO | PDO methods · Strongly-convex decentralized optimization | computation complexity: \mathcal{O} \left( \tfrac{\sqrt{\delta L}}{\mu} \log \left( \tfrac{1}{\epsilon} \right) \right) vs. \mathcal{O} \left( \ | Helped |
| Use Accelerated-SPDO instead of Inexact Accelerated SONATA | Accelerated decentralized optimization · Strongly-convex decentralized optimization | computation complexity: \tilde{\mathcal{O}} (\log (\tfrac{1}{\epsilon})) vs. \tilde{\mathcal{O}}((\log (\tfrac{1}{\epsilon}))^2) | Helped |
| Use average functional similarity \delta rather than maximum dissimilarity \delta_max | SONATA communication analysis · Strongly-convex decentralized optimization | communication complexity: \tilde{\mathcal{O}} (\tfrac{\delta_\text{max}}{\mu (1 - \rho)} \log ( \tfrac{1}{\epsilon} ) ) -> \tilde{\mathcal{O}} (\t | Helped |
| Increase dataset similarity across nodes | SPDO · MNIST with different Dirichlet \alpha | convergence speed | Helped |
| Increase dataset similarity across nodes | Gradient Tracking · MNIST with different Dirichlet \alpha | convergence behavior | No clear effect |
Surprising findings
- A naive adaptation of the hybrid projection proximal-point method to PDO does not recover PDO when subproblems are solved exactly, requiring a modified update.
Limitations
- Experiments are limited to a single MNIST logistic regression setup with 25 nodes on a ring.
- Accelerated-SPDO's communication bound is only optimal up to log factors and holds when δ ≥ μ for lower-bound matching.
- Some results rely on the assumption that subproblem solvers reach a specified accuracy condition, which may be hard to verify in practice.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST logistic regression with L2 regularization (n=25 ring network, Dirichlet-partitioned data)
Metrics: gradient norm vs. communication rounds gradient norm vs. computation (gradient oracle) queries
Baselines: Gradient Tracking Exact-PDO (SONATA) Inexact-PDO Accelerated SONATA Inexact Accelerated SONATA
Builds on: SONATA Hybrid Projection Proximal-point Method Monteiro-Svaiter acceleration Gradient Tracking DANE
Closest papers by meaning
- Stabilized Proximal-Point Methods for Federated Optimization (NeurIPS 2024 · similarity 0.88)
- Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization (NeurIPS 2024 · similarity 0.88)
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.87)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.86)
- DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity (ICLR 2025 · similarity 0.86)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 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.