Decentralized Gradient Tracking with Local Steps
Authors:
- Anastasia KoloskovaAKAnastasia Koloskova
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- On the Performance of Gradient Tracking with Local Updates2023
- Variance-Reduced Decentralized Stochastic Optimization With Accelerated ConvergenceIEEE Transactions on Signal Processing, 2020
- Can Primal Methods Outperform Primal-Dual Methods in Decentralized Dynamic Optimization?IEEE Transactions on Signal Processing, 2020
- Linear convergence of primal–dual gradient methods and their performance in distributed optimizationAutomatica, 2020
- Distributed stochastic gradient tracking methodsMathematical Programming, 2020
- ImageNet Training in Minutes2018
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying GraphsSIAM Journal on Optimization, 2017
- EXTRA: An Exact First-Order Algorithm for Decentralized Consensus OptimizationSIAM Journal on Optimization, 2015
- The MNIST Database of Handwritten Digit Images for Machine Learning Research [Best of the Web]IEEE Signal Processing Magazine, 2012
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009