AI & ML
On the Spectral Dependence of Decentralized Stochastic Gradient Tracking
arXiv eess.SY0 views
arXiv:2611.07958v1 Announce Type: cross 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 $\Delta_\lambda^{-3}$ in the higher-order stochastic term, where $\Delta_\lambda$ 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 $\alpha^2\sigma^2\Delta_\lambda^{-3}$ as the nontrivial eigenvalue approaches $-1$, provided the stepsize $\alpha$ is sufficiently small relative to the gap. Here $\sigma^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 $\nu$ at $-1$, the weighted sum $\theta_1/p+\theta_2/\nu^3$ replaces the prior factor $(\Delta_\lambda\nu^2)^{-1}$. For $N$ agents, $N\theta_1$ and $N\theta_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}+\nu^{-3}$ up to universal constants. Numerical experiments confirm the predicted scaling.
Source:https://arxiv.org/abs/2611.07958PreviousEnergyBench: a live, gate-aligned benchmark of day-ahead forecasts for European power marketsNextA Unified Fractal Impedance Control Framework
Related posts
EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
0arXiv cs.DB
Typed Knowledge over Constructive Institutions
0arXiv cs.DB
CascadeFilter: Cost-Efficient Semantic Filtering with Joint Threshold Selection
0arXiv cs.DB
Cleaning or Recalling? Knowledge Dependence in LLM-based Data Cleaning [Experiment, Analysis & Benchmark]
0arXiv cs.DB
Selective Retrieval Routing for Multi-Violation Knowledge Graph Repair
0arXiv cs.DB
DiagDBench: Evaluating Agentic LLMs on Interactive Database Diagnosis and Anomaly Remediation
0arXiv cs.DB