English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We introduce ProxSkip -- a surprisingly simple and provably efficient methodfor minimizing the sum of a smooth ($f$) and an expensive nonsmooth proximable($\psi$) function. The canonical approach to solving such problems is via theproximal gradient descent (ProxGD) algorithm, which is based on the evaluationof the gradient of $f$ and the prox operator of $\psi$ in each iteration. Inthis work we are specifically interested in the regime in which the evaluationof prox is costly relative to the evaluation of the gradient, which is the casein many applications. ProxSkip allows for the expensive prox operator to beskipped in most iterations: while its iteration complexity is$\mathcal{O}\left(\kappa \log \frac{1}{\varepsilon}\right)$, where $\kappa$ isthe condition number of $f$, the number of prox evaluations is$\mathcal{O}\left(\sqrt{\kappa} \log \frac{1}{\varepsilon}\right)$ only. Ourmain motivation comes from federated learning, where evaluation of the gradientoperator corresponds to taking a local GD step independently on all devices,and evaluation of prox corresponds to (expensive) communication in the form ofgradient averaging. In this context, ProxSkip offers an effective accelerationof communication complexity. Unlike other local gradient-type methods, such asFedAvg, SCAFFOLD, S-Local-GD and FedLin, whose theoretical communicationcomplexity is worse than, or at best matching, that of vanilla GD in theheterogeneous data regime, we obtain a provable and large improvement withoutany heterogeneity-bounding assumptions.

ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!