On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approach
This work addresses optimization efficiency in non-i.i.d. distributed settings, offering a tunable method to balance costs based on network and function properties, though it is incremental as it builds on existing gradient tracking techniques.
The paper tackles the trade-off between computation and communication in distributed stochastic optimization over networks by proposing a flexible gradient tracking approach that allows adjustable local updates and communications per round, achieving arbitrary accuracy with derived complexities for smooth and strongly convex functions.
We propose a flexible gradient tracking approach with adjustable computation and communication steps for solving distributed stochastic optimization problem over networks. The proposed method allows each node to perform multiple local gradient updates and multiple inter-node communications in each round, aiming to strike a balance between computation and communication costs according to the properties of objective functions and network topology in non-i.i.d. settings. Leveraging a properly designed Lyapunov function, we derive both the computation and communication complexities for achieving arbitrary accuracy on smooth and strongly convex objective functions. Our analysis demonstrates sharp dependence of the convergence performance on graph topology and properties of objective functions, highlighting the trade-off between computation and communication. Numerical experiments are conducted to validate our theoretical findings.