ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication
  Acceleration! Finally!
  We introduce \algname{ProxSkip} -- a surprisingly simple and provably
efficient method for minimizing the sum of a smooth ($f$) and an expensive
nonsmooth proximable ($\psi$) function. The canonical approach to solving such
problems is via the proximal gradient descent (\algname{ProxGD}) algorithm,
which is based on the evaluation of the gradient of $f$ and the prox operator
of $\psi$ in each iteration. In this work we are specifically interested in the
regime in which the evaluation of prox is costly relative to the evaluation of
the gradient, which is the case in many applications. \algname{ProxSkip} allows
for the expensive prox operator to be skipped in most iterations: while its
iteration complexity is $\cO(\kappa \log \nicefrac{1}{\varepsilon})$, where
$\kappa$ is the condition number of $f$, the number of prox evaluations is
$\cO(\sqrt{\kappa} \log \nicefrac{1}{\varepsilon})$ only. Our main motivation
comes from federated learning, where evaluation of the gradient operator
corresponds to taking a local \algname{GD} step independently on all devices,
and evaluation of prox corresponds to (expensive) communication in the form of
gradient averaging. In this context, \algname{ProxSkip} offers an effective
{\em acceleration} of communication complexity. Unlike other local
gradient-type methods, such as \algname{FedAvg}, \algname{SCAFFOLD},
\algname{S-Local-GD} and \algname{FedLin}, whose theoretical communication
complexity is worse than, or at best matching, that of vanilla \algname{GD} in
the heterogeneous data regime, we obtain a provable and large improvement
without any heterogeneity-bounding assumptions.
