# Decentralized Gradient Tracking with Local Steps

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 40 references that are in the map.
- First posted on arXiv 3 Jan 2023.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [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)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [The Non-IID Data Quagmire of Decentralized Machine Learning](https://mlsanity.com/paper/1910.00189/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Accelerating Gossip SGD with Periodic Global Averaging](https://mlsanity.com/paper/2105.09080/) (2021)
- [On the Performance of Gradient Tracking with Local Updates](https://mlsanity.com/paper/2210.04757/) (2022)
- [Linear Convergence of Primal-Dual Gradient Methods and their Performance in Distributed Optimization](https://mlsanity.com/paper/1904.01196/) (2019)
- [Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?](https://mlsanity.com/paper/2003.00816/) (2020)
- [A Distributed Stochastic Gradient Tracking Method](https://mlsanity.com/paper/1803.07741/) (2018)

## Built on by (most cited first, 30 of 32)

- [Decentralized Low-Rank Fine-Tuning of Large Language Models](https://mlsanity.com/paper/2501.15361/) (2025)
- [DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates](https://mlsanity.com/paper/2307.07652/) (2023)
- [Robust Decentralized Learning with Local Updates and Gradient Tracking](https://mlsanity.com/paper/2405.00965/) (2024)
- [The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity](https://mlsanity.com/paper/2403.15654/) (2024)
- [Hierarchical Federated Learning with Multi-Timescale Gradient Correction](https://mlsanity.com/paper/2409.18448/) (2024)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approach](https://mlsanity.com/paper/2306.07159/) (2023)
- [Differentiated Aggregation to Improve Generalization in Federated Learning](https://mlsanity.com/paper/2404.11754/) (2024)
- [Communication-Efficient Stochastic Distributed Learning](https://mlsanity.com/paper/2501.13516/) (2025)
- [Differential error feedback for communication-efficient decentralized learning](https://mlsanity.com/paper/2406.18418/) (2024)
- [Communication-Efficient Federated Optimization over Semi-Decentralized Networks](https://mlsanity.com/paper/2311.18787/) (2023)
- [A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization](https://mlsanity.com/paper/2312.11861/) (2023)
- [Gradient Correction in Federated Learning with Adaptive Optimization](https://mlsanity.com/paper/2502.02727/) (2025)
- [Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization](https://mlsanity.com/paper/2310.07983/) (2023)
- [Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization](https://mlsanity.com/paper/2506.05791/) (2025)
- [Jointly Computation- and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2508.15509/) (2025)
- [A Communication-Efficient Decentralized Actor-Critic Algorithm](https://mlsanity.com/paper/2510.19199/) (2025)
- [Subspace Optimization for Efficient Federated Learning under Heterogeneous Data](https://mlsanity.com/paper/2604.25467/) (2026)
- [MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods](https://mlsanity.com/paper/2403.02589/) (2024)
- [Fast Decentralized Gradient Tracking for Federated Minimax Optimization with Local Updates](https://mlsanity.com/paper/2405.04566/) (2024)
- [Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps](https://mlsanity.com/paper/2407.02689/) (2024)
- [A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks](https://mlsanity.com/paper/2410.18774/) (2024)
- [Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum](https://mlsanity.com/paper/2504.12742/) (2025)
- [Diffusion Learning with Partial Agent Participation and Local Updates](https://mlsanity.com/paper/2505.11307/) (2025)
- [CoCoL: A Communication Efficient Decentralized Collaborative Method for Multi-Robot Systems](https://mlsanity.com/paper/2508.20898/) (2025)
- [Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking](https://mlsanity.com/paper/2509.18129/) (2025)
- [Beyond Scaffold: A Unified Spatio-Temporal Gradient Tracking Method](https://mlsanity.com/paper/2512.01732/) (2025)
- [Accelerating Decentralized Optimization via Overlapping Local Steps](https://mlsanity.com/paper/2601.01493/) (2026)
- [Local Updates in Distributed Optimization: Provable Acceleration and Topology Effects](https://mlsanity.com/paper/2601.03442/) (2026)
- [Sporadic Gradient Tracking over Directed Graphs: A Theoretical Perspective on Decentralized Federated Learning](https://mlsanity.com/paper/2602.00791/) (2026)

## Abstract (arXiv)

Gradient tracking (GT) is an algorithm designed for solving decentralized optimization problems over a network (such as training a machine learning model). A key feature of GT is a tracking mechanism that allows to overcome data heterogeneity between nodes. We develop a novel decentralized tracking mechanism, K-GT, that enables communication-efficient local updates in GT while inheriting the data-independence property of GT. We prove a convergence rate for K-GT on smooth non-convex functions and prove that it reduces the communication overhead asymptotically by a linear factor K, where K denotes the number of local steps. We illustrate the robustness and effectiveness of this heterogeneity correction on convex and non-convex benchmark problems and on a non-convex neural network training task with the MNIST dataset.