We revisit two fundamental decentralized optimization methods, Decentralized
Gradient Tracking (DGT) and Decentralized Gradient Descent (DGD), with multiple
local updates. We consider two settings and demonstrate that incorporating $K >
1$ local update steps can reduce communication complexity. Specifically, for
$\mu$-strongly convex and $L$-smooth loss functions, we proved that local DGT
achieves communication complexity $\tilde{\mathcal{O}} \Big(\frac{L}{\mu K} +
\frac{\delta}{\mu (1 - \rho)} + \frac{\rho }{(1 - \rho)^2} \cdot \frac{L+
\delta}{\mu}\Big)$, where $\rho$ measures the network connectivity and $\delta$
measures the second-order heterogeneity of the local loss. Our result reveals
the tradeoff between communication and computation and shows increasing $K$ can
effectively reduce communication costs when the data heterogeneity is low and
the network is well-connected. We then consider the over-parameterization
regime where the local losses share the same minimums, we proved that employing
local updates in DGD, even without gradient correction, can yield a similar
effect as DGT in reducing communication complexity. Numerical experiments
validate our theoretical results.

在本文中，我们研究了两种基础的分散式优化方法：分散式梯度跟踪（DGT）和分散式梯度下降（DGD），并考虑了多次本地更新。我们证明了增加本地更新步骤可以降低通信复杂性，并揭示了通信与计算之间的权衡关系。在数据异质性较低且网络连接良好时，增加本地更新可以有效降低通信成本。我们还证明了在超参数化的情况下，即使没有梯度修正，DGD 中使用本地更新也可以降低通信复杂性。数值实验验证了我们的理论结果。