Research map / Optimization / Nonconvex and smooth optimization
Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers
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 CESAR, a decentralized stochastic variance-reduced accelerated method with node-specific non-uniform mini-batch sampling (Bernoulli sampling with probabilities depending on smoothness), whose complexity depends on the global condition number rather than local ones.
Problem
Decentralized convex finite-sum optimization where each node's local objective is an average of convex component functions and the global objective is strongly convex; prior stochastic methods' complexity depends only on local condition numbers.
Approach
Each node draws its stochastic variance-reduced gradient estimator with node- and component-specific Bernoulli sampling probabilities (proportional to component smoothness), so different nodes use different mini-batch sizes per iteration; combined with Katyusha-like acceleration, multi-consensus Chebyshev steps and gradient tracking, this yields complexity bounds that depend on global condition nu
Key results
- CESAR achieves computation time complexity of about Õ((sqrt(n·κ̄max/m) + sqrt(κ) + n) log(1/ε)), communication Õ(sqrt(κ/γ) log(1/ε)), and LIFO complexity O((sqrt(mn·κ̄max) + mn) log(1/ε)).
- In logistic regression experiments on a9a and w6a with m=300 nodes, CESAR outperforms Acc-VR-DIGing and Acc-VR-EXTRA on all measures and beats Mudag on computation and LIFO with comparable communication.
- Lower bounds match the communication and computation upper bounds up to log factors; the LIFO lower bound depends on κ̄ rather than κ̄max, leaving a gap.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CESAR's non-uniform sampling with node-specific stochastic gradient batch sizes | Decentralized convex finite-sum optimization · Decentralized convex finite-sum optimization | computation time complexity: ˜O((√(n¯κmax/m) + √κ + n) log(1/ε)) | Helped |
| Use CESAR's non-uniform sampling with node-specific stochastic gradient batch sizes | Decentralized convex finite-sum optimization · Decentralized convex finite-sum optimization | communication rounds: ˜O(√(κ/γ) log(1/ε)) | Helped |
| Use CESAR's non-uniform sampling with node-specific stochastic gradient batch sizes | Decentralized convex finite-sum optimization · Decentralized convex finite-sum optimization | LIFO calls: O((√(mn¯κmax) + mn) log(1/ε)) | Helped |
| Use CESAR instead of Acc-VR-DIGing or Acc-VR-EXTRA | Decentralized logistic regression · a9a | optimal gap versus computation | Helped |
| Use CESAR instead of Acc-VR-DIGing or Acc-VR-EXTRA | Decentralized logistic regression · w6a | optimal gap versus communication | Helped |
| Use CESAR instead of Mudag | Decentralized logistic regression · a9a and w6a | optimal gap versus computation and LIFO calls | Helped |
| Use CESAR instead of Mudag | Decentralized logistic regression · a9a and w6a | communication cost | No clear effect |
Surprising findings
- The LIFO lower bound depends on the average smoothness κ̄ while the CESAR upper bound depends on κ̄max, so LIFO optimality is not established.
Limitations
- LIFO lower bound (depends on κ̄) does not match the upper bound (depends on κ̄max); gap left open.
- Communication complexity is only comparable to Mudag (Õ(sqrt(κ/γ)) with a log factor), not strictly better.
- Experiments are limited to two logistic regression datasets with a single network configuration.
Experimental setup
Datasets: a9a w6a
Benchmarks: a9a w6a
Metrics: optimality gap versus # computation optimality gap versus # communication optimality gap versus # LIFO calls
Baselines: Mudag Acc-VR-DIGing Acc-VR-EXTRA ADFS DSA GT-SVRG
Builds on: Katyusha L-Katyusha Mudag ADFS Acc-VR-EXTRA FastMix
Closest papers by meaning
- A Near-Optimal Algorithm for Decentralized Convex-Concave Finite-Sum Minimax Optimization (NeurIPS 2025 · similarity 0.93)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 2024 · similarity 0.90)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.90)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.89)
- Decentralized Sum-of-Nonconvex Optimization (AAAI 2024 · similarity 0.89)
- Enhancing Parallelism in Decentralized Stochastic Convex Optimization (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.