On the Performance of Gradient Tracking with Local Updates
This work addresses communication bottlenecks in decentralized optimization for distributed systems, but it is incremental as it builds on existing gradient tracking methods.
The paper tackles the problem of reducing communication costs in decentralized optimization for networks of agents with heterogeneous non-convex functions by analyzing a locally updated gradient tracking method (LU-GT). It shows that local updates do not degrade solution quality and can lower communication costs in certain regimes, such as well-connected graphs.
We study the decentralized optimization problem where a network of $n$ agents seeks to minimize the average of a set of heterogeneous non-convex cost functions distributedly. State-of-the-art decentralized algorithms like Exact Diffusion~(ED) and Gradient Tracking~(GT) involve communicating every iteration. However, communication is expensive, resource intensive, and slow. In this work, we analyze a locally updated GT method (LU-GT), where agents perform local recursions before interacting with their neighbors. While local updates have been shown to reduce communication overhead in practice, their theoretical influence has not been fully characterized. We show LU-GT has the same communication complexity as the Federated Learning setting but allows arbitrary network topologies. In addition, we prove that the number of local updates does not degrade the quality of the solution achieved by LU-GT. Numerical examples reveal that local updates can lower communication costs in certain regimes (e.g., well-connected graphs).