On the Computation-Communication Trade-Off with A Flexible Gradient
  Tracking Approach
Yan Huang Jinming Xu
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.