Research map / Optimization / Nonconvex and smooth optimization
Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic 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 convergence lower bound for nonconvex decentralized stochastic optimization over row-stochastic networks, shows Pull-Diag-GT achieves linear speedup, and proposes multi-gossip Pull-Diag-GT achieving near-optimal complexity.
Problem
Decentralized stochastic nonconvex optimization over directed networks with row-stochastic mixing matrices (Row-Only setting): the optimal convergence rate is unknown and existing Row-Only algorithms (Pull-Diag-GT) do not achieve linear speedup or the lower bound.
Approach
Adopts the generalized spectral gap and equilibrium skewness to characterize row-stochastic mixing; proves a lower bound; shows Pull-Diag-GT attains linear speedup via a new analysis of descent deviation and consensus error; and adds multiple gossip rounds per iteration so that the diagonal of A^R is bounded away from zero, removing the instability and matching the lower bound up to a log(n) gap.
Key results
- Proves the first lower bound for row-stochastic nonconvex stochastic decentralized optimization, of order sigma*sqrt(L Delta)/sqrt(nK) + (1+ln kappa_A) L Delta/((1-beta_A)K).
- Pull-Diag-GT is shown to achieve linear speedup (rate sigma sqrt(L Delta)/sqrt(nK) + C_A L Delta/K), the first such result for Row-Only algorithms.
- MG-Pull-Diag-GT with R = ceil(3(1+ln kappa_A+ln n)/(1-beta_A)) gossip rounds matches the lower bound up to a ln(n) term, and empirically converges faster than vanilla Pull-Diag-GT on MNIST and CIFAR-10 over ring, grid, geometric and nearest-neighbor graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multiple gossip steps instead of a single gossip step (ablation) | Pull-Diag-GT · MNIST | training loss | Helped |
| Use multiple gossip steps instead of a single gossip step (ablation) | Pull-Diag-GT · CIFAR-10, especially sparse ring and grid topologies | training loss | Helped |
| Increase the number of nodes while holding the directed graph topology family and communication rounds fixed | Pull-Diag-GT · Synthetic nonconvex logistic regression on exponential and ring graphs | gradient norm | Helped |
Limitations
- The explicit network impact of theta_A on Pull-Diag-GT remains unclear.
- MG-Pull-Diag-GT matches the lower bound only up to a logarithmic ln(n) gap (near-optimal rather than optimal).
- Pull-Diag-GT requires Assumption of bounded diagonals (theta_A), which holds only if every node has a self-loop.
Experimental setup
Datasets: synthetic nonconvex logistic regression dataset MNIST CIFAR-10
Benchmarks: MNIST CIFAR-10 synthetic nonconvex logistic regression
Metrics: gradient norm averaged training loss test accuracy consensus error
Baselines: Pull-Diag-GT Pull-Diag protocol
Builds on: Pull-Diag gossip protocol gradient tracking generalized spectral gap and equilibrium skewness (column-stochastic analysis)
Closest papers by meaning
- Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning (ICML 2026 · similarity 0.89)
- Decentralized Non-convex Stochastic Optimization with Heterogeneous Variance (AAAI 2026 · similarity 0.89)
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (ICML 2019 · similarity 0.89)
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.88)
- Double Stochasticity Gazes Faster: Snap-Shot Decentralized Stochastic Gradient Tracking Methods (ICML 2024 · similarity 0.87)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.87)
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.