Research map / Optimization / Nonconvex and smooth optimization
Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks
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.
Establishes the first lower complexity bounds for non-smooth convex decentralized optimization over time-varying networks and proposes an optimal saddle-point accelerated forward-backward algorithm that matches them.
Problem
Minimizing a sum of non-smooth convex functions stored across nodes of a time-varying communication network; prior work had no lower bounds or optimal algorithms in this setting.
Approach
Derives lower bounds using a star topology with a time-varying center (giving chi rather than sqrt(chi) communication dependence) and designs an accelerated forward-backward method on a saddle-point reformulation with error-feedback gossip and an inner subgradient/Chambolle-Pock solver for the resolvent, achieving matching communication and subgradient complexities.
Key results
- Lower bounds of Omega(t_com * chi M/sqrt(r eps) + t_loc * M^2/(r eps)) for strongly convex and Omega(t_com * chi MR/eps + t_loc * M^2R^2/eps^2) for convex non-smooth time-varying decentralized problems.
- The proposed algorithm matches these bounds in both strongly convex and convex cases, improving on ZO-SADOM by factors d^{1/4} log(1/eps) in communication and d log(1/eps) in subgradient computations.
- The lower bound shows communication complexity scales with chi rather than sqrt(chi) as in fixed networks, resolving a long-standing conjecture for the non-smooth case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed algorithm instead of ZO-SADOM | Strongly-convex non-smooth decentralized optimization over time-varying networks · Strongly-convex case | communication complexity: \chi M d^{1/4}\log\tfrac{1}{\epsilon} -> \frac{\chi M}{\sqrt{r\epsilon}} | Helped |
| Use the proposed algorithm instead of ZO-SADOM | Strongly-convex non-smooth decentralized optimization over time-varying networks · Strongly-convex case | subgradient computation complexity: \frac{M^2 d\log\tfrac{1}{\epsilon}}{r\epsilon} -> \frac{M^2}{r\epsilon} | Helped |
| Use the proposed algorithm instead of ZO-SADOM | Convex non-smooth decentralized optimization over time-varying networks · Convex case | communication complexity: \frac{\chi MR d^{1/4}\log\tfrac{1}{\epsilon}}{\epsilon} -> \frac{\chi MR}{\epsilon} | Helped |
| Use the proposed algorithm instead of ZO-SADOM | Convex non-smooth decentralized optimization over time-varying networks · Convex case | subgradient computation complexity: \frac{M^2R^2 d\log\tfrac{1}{\epsilon}}{\epsilon^2} -> \frac{M^2R^2}{\epsilon^2} | Helped |
| Use the proposed algorithm | Non-smooth convex decentralized optimization over time-varying networks · Strongly-convex and convex cases | communication and subgradient computation complexity | Helped |
Surprising findings
- Time-varying networks require communication complexity proportional to chi, a strictly worse dependence than the sqrt(chi) for fixed networks.
Limitations
- Theoretical contribution only; no experiments reported in the provided text.
- Inner subproblem solved approximately, adding algorithmic complexity.
Experimental setup
Metrics: communication complexity subgradient computation complexity execution time
Baselines: D-SubGD SubGD-Push ZO-SADOM
Builds on: Forward-Backward algorithm Nesterov acceleration Chambolle-Pock ZO-SADOM Error feedback for decentralized communication
Closest papers by meaning
- Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks (NeurIPS 2021 · similarity 0.97)
- Decentralized Optimization with Coupled Constraints (ICLR 2025 · similarity 0.90)
- On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization (NeurIPS 2024 · similarity 0.89)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 2024 · similarity 0.89)
- Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization (NeurIPS 2024 · similarity 0.89)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 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.