Inspired by a recent breakthrough of Mishchenko et al (2022), who for the
first time showed that local gradient steps can lead to provable communication
acceleration, we propose an alternative algorithm which obtains the same
communication acceleration as their method (ProxSkip). Our approach is very
different, however: it is based on the celebrated method of Chambolle and Pock
(2011), with several nontrivial modifications: i) we allow for an inexact
computation of the prox operator of a certain smooth strongly convex function
via a suitable gradient-based method (e.g., GD, Fast GD or FSFOM), ii) we
perform a careful modification of the dual update step in order to retain
linear convergence. Our general results offer the new state-of-the-art rates
for the class of strongly convex-concave saddle-point problems with bilinear
coupling characterized by the absence of smoothness in the dual function. When
applied to federated learning, we obtain a theoretically better alternative to
ProxSkip: our method requires fewer local steps ($O(\kappa^{1/3})$ or
$O(\kappa^{1/4})$, compared to $O(\kappa^{1/2})$ of ProxSkip), and performs a
deterministic number of local steps instead. Like ProxSkip, our method can be
applied to optimization over a connected network, and we obtain theoretical
improvements here as well.

本文提出一种新的算法，基于 Chambolle 和 Pock (2011) 的方法，在一些非平滑的强凸共轭鞍点问题上的表现优于 ProxSkip。该算法在联邦学习中的应用需要较少的本地步骤，并且是一种确定性方法，而且也适用于连接网络上的优化。