Research map / Optimization / Nonconvex and smooth optimization
Achieving Linear Convergence with Parameter-Free Algorithms in 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 a parameter-free decentralized optimization algorithm using a novel variable-metric operator splitting with local backtracking line-search, proving linear convergence for strongly convex smooth sums without global Lipschitz/network knowledge.
Problem
Decentralized minimization of a sum of strongly convex, smooth functions over a mesh network without a server, where existing methods need knowledge of the gradient Lipschitz constant and network spectral gap to tune stepsizes; prior adaptive decentralized methods lack linear convergence guarantees.
Approach
Forward-backward operator splitting on a saddle-point reformulation with a novel variable metric (K = I - cL^2) yields a descent direction independent of stepsize, enabling a decentralized backtracking line-search where each agent computes a local stepsize and a min-consensus selects the global one; a local min-consensus variant avoids global communication.
Key results
- Algorithms 1 and 3 consistently outperform EXTRA and NIDS (tuned by grid search) on ridge regression over line and Erdos-Renyi graphs, with the gap widening as the condition number increases.
- Theory establishes linear convergence with rate depending on local condition number and network connectivity, with a separation property in well-connected networks (rate matching centralized gradient or consensus).
- Local min-consensus variant (Algorithm 3) yields nearly the same practical convergence speed as global min-consensus, with only O(diameter) overhead in theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use adaptive backtracking instead of tuned fixed stepsizes | Algorithm 1 and Algorithm 3 · Ridge regression on line and Erdős–Rényi graphs | iterations to convergence | Helped |
| replace global min-consensus with local min-consensus (ablation) | Algorithm 1 · Ridge regression on line and Erdős–Rényi graphs | convergence speed | No clear effect |
| replace global min-consensus with local min-consensus (ablation) | Algorithm 1 · Ridge regression on line and Erdős–Rényi graphs | error monotonicity | Hurt |
Surprising findings
- Local min-consensus produces nonmonotone error dynamics in the iterates, though practical speed is largely unaffected.
Limitations
- Convergence rate in poorly connected networks is worst-case O(kappa/(1-lambda_2)), mixing optimization and network parameters.
- Experiments are preliminary and limited to ridge regression with 20 agents.
- Local min-consensus loses monotonicity of error decrease and requires diameter-dependent extra iterations.
Experimental setup
Datasets: synthetic ridge regression data
Benchmarks: synthetic ridge regression on line, Erdos-Renyi graphs (m=20)
Metrics: number of iterations to reach ||X_N - X*|| <= 1e-5 convergence speed vs condition number
Baselines: EXTRA NIDS
Builds on: forward-backward splitting EXTRA NIDS Barzilai-Borwein stepsize
Closest papers by meaning
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.89)
- DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity (ICLR 2025 · similarity 0.88)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 2024 · similarity 0.88)
- 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)
- Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization (ICML 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.