# Beyond Scaffold: A Unified Spatio-Temporal Gradient Tracking Method

arXiv: https://arxiv.org/abs/2512.01732 · HTML: https://mlsanity.com/paper/2512.01732/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 32 references that are in the map.
- First posted on arXiv 1 Dec 2025.

## Builds on (most cited first, 24 of 24)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Preservation of the Global Knowledge by Not-True Distillation in Federated Learning](https://mlsanity.com/paper/2106.03097/) (2021)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [On the Performance of Gradient Tracking with Local Updates](https://mlsanity.com/paper/2210.04757/) (2022)
- [FedAudio: A Federated Learning Benchmark for Audio Tasks](https://mlsanity.com/paper/2210.15707/) (2022)
- [Federated Optimization with Doubly Regularized Drift Correction](https://mlsanity.com/paper/2404.08447/) (2024)
- [Composite federated learning with heterogeneous data](https://mlsanity.com/paper/2309.01795/) (2023)
- [The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity](https://mlsanity.com/paper/2403.15654/) (2024)
- [On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approach](https://mlsanity.com/paper/2306.07159/) (2023)
- [Distributed Riemannian Optimization with Lazy Communication for Collaborative Geometric Estimation](https://mlsanity.com/paper/2203.00851/) (2022)
- [On graphs with finite-time consensus and their use in gradient tracking](https://mlsanity.com/paper/2311.01317/) (2023)

## Abstract (arXiv)

In distributed and federated learning algorithms, communication overhead is often reduced by performing multiple local updates between communication rounds. However, due to data heterogeneity across nodes and the local gradient noise within each node, this strategy can lead to the drift of local models away from the global optimum. To address this issue, we revisit the well-known federated learning method Scaffold (Karimireddy et al., 2020) under a gradient tracking perspective, and propose a unified spatio-temporal gradient tracking algorithm, termed ST-GT, for distributed stochastic optimization over time-varying graphs. ST-GT tracks the global gradient across neighboring nodes to mitigate data heterogeneity, while maintaining a running average of local gradients to substantially suppress noise, with slightly more storage overhead. Without assuming bounded data heterogeneity, we prove that ST-GT attains a linear convergence rate for strongly convex problems and a sublinear rate for nonconvex cases. Notably, ST-GT achieves the first linear speed-up in communication complexity with respect to the number of local updates per round τ for the strongly-convex setting. Compared to traditional gradient tracking methods, ST-GT reduces the topology-dependent noise term from σ2 to σ2/τ, where σ2 denotes the noise level, thereby improving communication efficiency.