Exact Worst-case Convergence Rates of Distributed Gradient Tracking Methods
arXiv:2607.23601
2026
Optimization
2 ideas extracted · analyzed Aug 30, 2026
What the math gives to ML
The paper converts distributed gradient tracking from a matrix-valued stability problem into independent scalar network-eigenmode feedback systems, yielding an exact minimax convergence rate rather than a conservative sufficient bound. The transferable asset is the explicit dependence of each mode's poles on the optimizer step size, objective curvature interval [\mu,L], and communication eigenvalues \lambda_i. For multi-GPU, federated, or decentralized neural-network training, this enables selecting the communication matrix, tracking variant, and step size by directly minimizing the worst pole radius on an estimated curvature and graph spectrum. The most practical first transfer is a spectral line-search and method-selection tool for gradient tracking.
Ideas from this paper
✗ Failed on benchmark
2026
Replace generic learning-rate selection in decentralized or federated gradient tracking with a low-dimensional minimax search over the exact scalar-mode pole radius. The optimizer chooses the step size that minimizes the worst predicted contraction over the observed graph spectrum and an estimated curvature interval, rather than relying only on conservative global bounds.
Useful7/10
Difficulty5/10
Novelty6/10
Unverified
2026
Use the paper's mode decomposition to choose between ordinary DIGing and augmented ATC-DIGing/AugDGM according to the communication spectrum and curvature. The augmented scheme changes the disagreement feedback gain mode by mode, which can reduce the dominant pole radius on well-connected graphs without changing the neural-network architecture.
Useful6/10
Difficulty5/10
Novelty5/10