Research map / Optimization / Distributed and compressed
Double Stochasticity Gazes Faster: Snap-Shot Decentralized Stochastic Gradient Tracking Methods
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 snap-shot decentralized stochastic gradient tracking (SS DSGT) and an accelerated variant (ASS DSGT) with loopless Chebyshev acceleration, achieving lower iteration complexity than DSGT on general topologies for strongly convex decentralized optimization.
Problem
Decentralized stochastic optimization over networks with heterogeneous data: DSGT's iteration complexity degrades with the spectral gap of the mixing matrix, and its dependence on the topology (C_W) is not tight for general networks.
Approach
Extends the snap-shot gradient tracking idea (SVRG/L-SVRG-style, updating the tracker and snapshot only with probability p) from SS GT to decentralized SGD, yielding iteration complexity depending on (1-λ2(W))^-1 instead of DSGT's (1-λ2(W))^-3/2; adds loopless Chebyshev acceleration for (1-λ2(W))^-1/2 on symmetric PSD mixing matrices.
Key results
- On asymmetric topology W_asy, SS DSGT outperforms DSGT in distance to optimum on banknote, a9a, and ijcnn1 (strongest on a9a).
- On symmetric W_sy, ASS DSGT shows better practical performance than DSGT and SS DSGT across the three datasets.
- Theoretical iteration complexity: SS DSGT O(sigma^2/(mu eps) + sqrt(L) sigma/(mu(1-λ2(W))sqrt(eps))); ASS DSGT matches DSGT's best known rate O(... /(mu sqrt(1-λ2(W)) sqrt(eps))).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add snapshot gradient tracking | DSGT · General communication network, stochastic noise | iteration complexity: ˜O(\bar{σ}²/(mµε) + √L\bar{σ}/(µ(1 − λ₂(W))^{3/2}√ε)) -> O(\bar{σ}²/(µmε) + √L\bar{σ}/((1 − λ₂(W))µ√ε) + L/((1 − λ₂(W))µ | Helped |
| Add loopless Chebyshev acceleration to SS DSGT (ablation) | SS DSGT · Static network, stochastic noise | iteration complexity: O(\bar{σ}²/(µmε) + √L\bar{σ}/((1 − λ₂(W))µ√ε) + L/((1 − λ₂(W))µε^{1/3})) -> O(\bar{σ}²/(µmε) + √L\bar{σ}/(µ√(1 − λ₂(W))√ | Helped |
| Add loopless Chebyshev acceleration to SS DSGT (ablation) | SS DSGT · Static network, deterministic case (\bar{σ}² = 0) | iteration complexity: O(L/(µ(1 − λ₂(W)) log 1/ε)) -> O(L/(µ√(1 − λ₂(W)) log 1/ε)) | Helped |
| Use ASS DSGT instead of DSGT | ASS DSGT and DSGT · Symmetric mixing matrix W sy; banknote, a9a, ijcnn1 | distance to optimum | Helped |
| Use SS DSGT instead of DSGT | SS DSGT and DSGT · Asymmetric mixing matrix W asy; banknote, a9a, ijcnn1 | distance to optimum | Helped |
Limitations
- ASS DSGT requires a symmetric positive semi-definite mixing matrix and is not applicable to asymmetric/time-varying topologies.
- Experiments are small-scale logistic regression with 20 agents; no deep learning evaluation.
- Loopless Chebyshev acceleration only applies to static networks.
Experimental setup
Datasets: banknote a9a ijcnn1
Benchmarks: banknote a9a ijcnn1
Metrics: squared distance ||x_t - x*||^2 versus communication rounds training loss
Baselines: DSGT
Builds on: DSGT SS GT (Song et al., 2023) L-SVRG loopless Chebyshev acceleration
Closest papers by meaning
- Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: Joint Gradient Estimation and Tracking (ICML 2020 · similarity 0.89)
- Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks (ICML 2025 · similarity 0.87)
- Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks (ICLR 2024 · similarity 0.86)
- On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization (NeurIPS 2024 · similarity 0.86)
- Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes (NeurIPS 2024 · similarity 0.86)
- Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (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.