Research map / Optimization / Nonconvex and smooth optimization
Decentralized Optimization with Coupled Constraints
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.
Proves lower complexity bounds for decentralized optimization with general affine coupled constraints and proposes an accelerated primal-dual PAPC-based first-order method with Chebyshev-accelerated communication that attains them, the first linearly convergent first-order decentralized method for general affine coupling.
Problem
Decentralized minimization of a separable strongly convex smooth objective subject to a network-wide affine coupling constraint sum_i (A_i x_i - b_i) = 0, where each node stores f_i, A_i, b_i and communicates only with neighbors.
Approach
Reformulates the coupled-constraint problem as a strongly convex augmented objective with a gossip-based dual variable, applies accelerated PAPC to the preconditioned problem, and implements the required matrix products via Chebyshev polynomial iterations so that gradient, A-multiplication and communication counts match matching lower bounds.
Key results
- The proposed method achieves O(sqrt(kappa_f) log(1/eps)) gradient computations, O(sqrt(kappa_f kappa_A) log(1/eps)) multiplications by A, and O(sqrt(kappa_f kappa_A kappa_W) log(1/eps)) communication rounds, matching the derived lower bounds.
- In experiments on synthetic linear regression (n=20 Erdos-Renyi nodes, kappa_f=3140, kappa_A=27, kappa_W=89) and VFL on mushrooms (n=7, m=100), the method shows the steepest convergence slopes versus Tracking-ADMM and DPMM in gradient, multiplication and communication counts.
- Applying the method to consensus optimization via the gossip reduction yields communication complexity worse by a factor of sqrt(n) than optimal consensus methods, since kappa_A >= n/2 for consensus constraints.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed APAPC method instead of Tracking-ADMM or DPMM | Synthetic linear regression · Synthetic linear regression, Erdős–Rényi graph (n = 20) | gradient computations | Helped |
| Use the proposed APAPC method instead of Tracking-ADMM or DPMM | Synthetic linear regression · Synthetic linear regression, Erdős–Rényi graph (n = 20) | matrix multiplications | Helped |
| Use the proposed APAPC method instead of Tracking-ADMM or DPMM | Synthetic linear regression · Synthetic linear regression, Erdős–Rényi graph (n = 20) | communication rounds | Helped |
| Use the proposed APAPC method instead of Tracking-ADMM or DPMM | VFL linear regression · mushrooms dataset (100 samples, 7 devices) | convergence rate | Helped |
Surprising findings
- Reducing consensus optimization to the general coupled-constraint setting loses a factor of sqrt(n) in communication complexity compared with optimal consensus algorithms.
Limitations
- Consensus reduction is suboptimal by sqrt(n) in communication relative to dedicated consensus methods
- Experiments are limited to small synthetic and single real dataset setups with simple linear regression objectives
- Requires the communication-unfriendly matrices A_i to be handled via local multiplications with Chebyshev iterations, adding inner-loop cost
Experimental setup
Datasets: mushrooms (LibSVM)
Benchmarks: synthetic linear regression with coupled constraints VFL linear regression on mushrooms
Metrics: convergence versus gradient computations matrix multiplications communication rounds
Baselines: Tracking-ADMM DPMM
Builds on: APAPC (accelerated proximal alternating predictor-corrector) Chebyshev acceleration Scaman et al. optimal decentralized consensus lower bounds
Closest papers by meaning
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.90)
- Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence (AAAI 2025 · similarity 0.88)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.88)
- Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization (NeurIPS 2024 · similarity 0.87)
- Decentralized Sum-of-Nonconvex Optimization (AAAI 2024 · similarity 0.87)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 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.