We introduce 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 (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. ProxSkip allows for the expensive prox operator to be
skipped in most iterations: while its iteration complexity is
$\mathcal{O}\left(\kappa \log \frac{1}{\varepsilon}\right)$, where $\kappa$ is
the condition number of $f$, the number of prox evaluations is
$\mathcal{O}\left(\sqrt{\kappa} \log \frac{1}{\varepsilon}\right)$ only. Our
main motivation comes from federated learning, where evaluation of the gradient
operator corresponds to taking a local GD step independently on all devices,
and evaluation of prox corresponds to (expensive) communication in the form of
gradient averaging. In this context, ProxSkip offers an effective acceleration
of communication complexity. Unlike other local gradient-type methods, such as
FedAvg, SCAFFOLD, S-Local-GD and FedLin, whose theoretical communication
complexity is worse than, or at best matching, that of vanilla GD in the
heterogeneous data regime, we obtain a provable and large improvement without
any heterogeneity-bounding assumptions.

ProxSkip 是一种简单且高效的方法，用于减小平滑函数 (f) 和昂贵的不平滑的可逼近函数 (psi) 函数的总和。 这种方法可以有效地加速通信复杂度，特别适用于联邦学习的情况。