On the Spectral Dependence of Decentralized Stochastic Gradient Tracking
Abstract
We study how the spectral geometry of the mixing matrix enters the convergence of decentralized stochastic gradient tracking (GT) for smooth strongly convex problems. General bounds contain the factor Δλ−3 in the higher-order stochastic term, where Δλ is the absolute spectral gap. We show that, even for two agents with identical quadratic objectives, the exact steady-state mean-square disagreement scales as α2σ2Δλ−3 as the nontrivial eigenvalue approaches −1, provided the stepsize α is sufficiently small relative to the gap. Here σ2 is the gradient-noise variance. By unrolling the disagreement recursion, we establish a stochastic bound that averages all nontrivial eigenvalue contributions for diagonalizable mixing matrices, up to an eigenvector conditioning factor. As a real or complex eigenvalue approaches the unit circle away from $1$, its contribution grows as the inverse cube of its distance to the circle; growth can be slower near $1$. For symmetric mixing with gaps p at $1$ and ν at −1, the weighted sum θ1/p+θ2/ν3 replaces the prior factor (Δλν2)−1. For N agents, Nθ1 and Nθ2 count the nonnegative and negative nontrivial eigenvalues, respectively. On a symmetric family, a finite-horizon lower bound for the average iterate matches the worst-case factor p−1+ν−3 up to universal constants. Numerical experiments confirm the predicted scaling.
Related
- Composite and Stochastic Smoothed Decentralized Bregman Proximal-Gradient Methods
- Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks
- Exact Average Consensus under Noisy Communication Links: A Decentralized Gradient Perspective
- Budget-Constrained Multi-Consensus Decentralized Gradient Descent
- Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
BibTeX
@misc{alghunaim2026spectral,
title = {{On the Spectral Dependence of Decentralized Stochastic Gradient Tracking}},
author = {Sulaiman A. Alghunaim and Haoyuan Cai and Ali H. Sayed},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07958},
eprint = {2611.07958},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07958},
}
RIS
TY - UNPB
TI - On the Spectral Dependence of Decentralized Stochastic Gradient Tracking
AU - Sulaiman A. Alghunaim
AU - Haoyuan Cai
AU - Ali H. Sayed
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07958
UR - https://arxiv.org/abs/2611.07958
AB - We study how the spectral geometry of the mixing matrix enters the convergence of decentralized stochastic gradient tracking (GT) for smooth strongly convex problems. General bounds contain the factor Δ_λ^−3 in the higher-order stochastic term, where Δ_λ is the absolute spectral gap. We show that, even for two agents with identical quadratic objectives, the exact steady-state mean-square disagreement scales as α^2σ^2Δ_λ^−3 as the nontrivial eigenvalue approaches −1, provided the stepsize α is sufficiently small relative to the gap. Here σ^2 is the gradient-noise variance. By unrolling the disagreement recursion, we establish a stochastic bound that averages all nontrivial eigenvalue contributions for diagonalizable mixing matrices, up to an eigenvector conditioning factor. As a real or complex eigenvalue approaches the unit circle away from $1$, its contribution grows as the inverse cube of its distance to the circle; growth can be slower near $1$. For symmetric mixing with gaps p at $1$ and ν at −1, the weighted sum θ_1/p+θ_2/ν^3 replaces the prior factor (Δ_λν^2)^−1. For N agents, Nθ_1 and Nθ_2 count the nonnegative and negative nontrivial eigenvalues, respectively. On a symmetric family, a finite-horizon lower bound for the average iterate matches the worst-case factor p^−1+ν^−3 up to universal constants. Numerical experiments confirm the predicted scaling.
ER -