Back

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

Konstantin MishchenkoGrigory MalinovskySebastian U. StichPeter Richtárik

article2022ICML214 citations

Proves that taking multiple local gradient steps provably accelerates communication complexity in heterogeneous federated learning to the optimal square-root condition number rate without requiring data homogeneity assumptions.

Listen

In modern distributed data science and machine learning applications, such as federated learning, training large models across decentralized networks of compute nodes encounters a severe bottleneck: network communication overhead. While local computation on individual devices is fast and inexpensive, synchronizing model parameters across slow and constrained communication channels is slow and costly. To mitigate this issue, distributed algorithms often execute multiple local computation steps between rounds of synchronization. However, when data across nodes is heterogeneous (drawn from different distributions), standard local algorithms suffer from severe "client drift," which degrades convergence speed and undermines theoretical performance guarantees.

The main objective of the article is to introduce and evaluate ProxSkip, a generalized optimization algorithm designed to skip expensive proximity and synchronization operations, and to demonstrate that local gradient steps can provably accelerate communication complexity in federated learning without requiring restrictive data similarity assumptions.

The authors develop a mathematical convergence framework for smooth and strongly convex optimization problems by introducing a probabilistic skipping mechanism stabilized by dynamic control variates. To validate the theoretical findings, the authors conduct parallelized numerical experiments on standard machine learning benchmark data (specifically, logistic regression on the LIBSVM w8a dataset using the RAY framework), evaluating deterministic and stochastic configurations alongside comparisons against established algorithms such as LocalGD, Scaffold, FedLin, and S-Local-GD.

The article yields several key findings. First, ProxSkip achieves an optimal communication complexity proportional to the square root of the condition number—substantially reducing the required communication rounds relative to the standard condition number scaling seen in classical gradient descent and competing local methods. Second, the algorithm maintains full linear convergence without requiring any data-homogeneity or similarity assumptions between client nodes. Third, the dynamic control variates provably eliminate client drift by converging to the exact gradient at the optimal solution. Fourth, the authors demonstrate that the framework extends effectively to settings with stochastic gradients as well as fully decentralized, mesh-network topologies. Finally, empirical evaluations confirm that ProxSkip (adapted to federated learning as Scaffnew) dramatically reduces communication rounds, matching its theoretical predictions when optimal skipping probabilities are employed.

These findings have direct operational and economic implications for large-scale machine learning deployments. By reducing the number of required communication rounds to the theoretical lower limit, organizations can substantially lower bandwidth costs, decrease network energy consumption, and compress training timelines on distributed edge devices. Unlike previous techniques that only matched standard gradient descent rates theoretically or relied on unprovable data homogeneity, this approach offers mathematically guaranteed acceleration under realistic, heterogeneous operating conditions.

Engineering and data science teams should consider piloting this skipping mechanism within distributed training pipelines, particularly in federated learning architectures where communication channels are constrained. When implementing the method, teams should tune the skipping probability toward the inverse square root of the condition number to maximize efficiency gains. Further research and engineering work should investigate theoretical extensions to achieve linear speedup with respect to client count under stochastic conditions, as well as testing on broader neural network workloads.

The primary limitations of this work stem from its theoretical foundations in smooth, strongly convex settings, which may not directly capture all non-convex deep learning dynamics. Additionally, the stochastic analysis does not yet theoretically establish linear speedup as client count increases. Nevertheless, the mathematical proofs are rigorous, and the empirical validations strongly support the core conclusion that skipping expensive synchronization steps accelerates distributed convergence.

CISPA Helmholtz Center for Information SecurityCNRSEcole Normale SupérieureINRIAKing Abdullah University of Science and TechnologycommunicationProxSkipcommunication accelerationlocal gradient steps
arXiv: 2202.09357
Cover for ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!

Abstract

We introduce ProxSkip—a surprisingly simple and provably efficient method for minimizing the sum of a smooth (f) and an expensive nonsmooth proximal (ψ) 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 ψ 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 O(κ log 1/ε), where κ is the condition number of f, the number of prox evaluations is O(√κ log 1/ε) 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.

Topics

communication

Keywords

ProxSkipcommunication accelerationlocal gradient stepsproximal gradient descentcommunication complexityclient driftgradient trackingiteration complexityconsensus reformulation

Table of Contents

  • 1. Introduction
  • 1.1. Proximal gradient descent
  • 1.2. Expensive proximity operators
  • 1.3. Distributed machine learning and consensus constraints
  • 1.4. Federated learning
  • 2. Contributions
  • 2.1. ProxSkip: a general prox skipping algorithm
  • 2.2. Scaffnew: ProxSkip applied to federated learning
  • 2.3. Extensions
  • 3. Theory
  • 3.1. Assumptions
  • 3.2. Firm nonexpansiveness
  • 3.3. Two technical lemmas
  • 3.4. Main theorem
  • 3.5. How often should one skip the prox?
  • 4. Application to Federated Learning
  • 4.1. Convergence
  • 5. Extensions
  • 5.1. Stochastic gradients
  • 5.2. Decentralized training
  • 6. Experiments
  • 7. Acknowledgements
  • References
  • Appendix
  • A. Basic Facts
  • B. Analysis of ProxSkip (Algorithm 1)
  • B.1. Proof of Lemma 3.4
  • B.2. Proof of Lemma 3.5
  • C. Analysis of SProxSkip (Algorithm 4)
  • C.1. The algorithm
  • C.2. Two lemmas
  • C.3. Proof of Theorem 5.5
  • C.4. Proof of Corollary 5.6
  • D. Decentralized Analysis
  • D.1. Proof of Theorem 5.7

Knowls

  1. Knowl 1 — Control-variate randomized proximal skipping

    model/method

    ProxSkip minimizes the composite objective

    min⁡x∈RdF(x):=f(x)+ψ(x),\min_{x\in\mathbb{R}^d} F(x):=f(x)+\psi(x),

    where f:Rd→Rf:\mathbb{R}^d\to\mathbb{R} is differentiable and ψ:Rd→R∪{+∞}\psi:\mathbb{R}^d\to\mathbb{R}\cup\{+\infty\} is proper, closed, and convex. For α>0\alpha>0, define

    prox⁡αψ(z):=arg⁡min⁡y∈Rd{12∥y−z∥2+αψ(y)}.\operatorname{prox}_{\alpha\psi}(z):=\arg\min_{y\in\mathbb{R}^d}\left\{\frac12\lVert y-z\rVert^2+\alpha\psi(y)\right\}.

    Given stepsize γ>0\gamma>0, prox-evaluation probability p∈(0,1]p\in(0,1], iterate xt∈Rdx_t\in\mathbb{R}^d, and control variate ht∈Rdh_t\in\mathbb{R}^d, ProxSkip performs

    x^t+1=xt−γ(∇f(xt)−ht).\widehat{x}_{t+1}=x_t-\gamma\bigl(\nabla f(x_t)-h_t\bigr).

    It then samples an independent Bernoulli variable θt\theta_t with Pr⁡(θt=1)=p\Pr(\theta_t=1)=p. If θt=1\theta_t=1, it evaluates the expensive proximity operator using

    xt+1=prox⁡(γ/p)ψ(x^t+1−γpht), x_{t+1}=\operatorname{prox}_{(\gamma/p)\psi}\left(\widehat{x}_{t+1}-\frac{\gamma}{p}h_t\right),

    whereas if θt=0\theta_t=0, it skips the prox evaluation and sets xt+1=x^t+1x_{t+1}=\widehat{x}_{t+1}. In both cases it updates the control variate by

    ht+1=ht+pγ(xt+1−x^t+1). h_{t+1}=h_t+\frac{p}{\gamma}\bigl(x_{t+1}-\widehat{x}_{t+1}\bigr).

    Thus, the control variate remains unchanged during consecutive skipped-prox iterations and corrects the drift caused by replacing the proximal-gradient step with a gradient-type step. The expected number of iterations between prox evaluations is 1/p1/p. When p=1p=1, the method reduces to ordinary proximal gradient descent.

  2. Knowl 2 — Linear convergence of ProxSkip

    theoretical result

    Assume that f:Rd→Rf:\mathbb{R}^d\to\mathbb{R} is LL-smooth and μ\mu-strongly convex with 0<μ≤L0<\mu\le L, and that ψ\psi is proper, closed, and convex. Let x∗x^* be the unique minimizer of f+ψf+\psi, define h∗:=∇f(x∗)h^*:=\nabla f(x^*), and let ProxSkip use 0<γ≤1/L0<\gamma\le 1/L and 0<p≤10<p\le 1. Define the Lyapunov function

    Ψt:=∥xt−x∗∥2+γ2p2∥ht−h∗∥2.\Psi_t:=\lVert x_t-x^*\rVert^2+\frac{\gamma^2}{p^2}\lVert h_t-h^*\rVert^2.

    The expectation is over the random prox-skipping decisions. ProxSkip satisfies

    E[ΨT]≤(1−ζ)TΨ0,ζ:=min⁡{γμ,p2}.\mathbb{E}[\Psi_T]\le (1-\zeta)^T\Psi_0, \qquad \zeta:=\min\{\gamma\mu,p^2\}.

    Consequently, both the primal iterate and the control variate converge linearly in the Lyapunov metric; in particular, the control variate is driven toward h∗=∇f(x∗)h^*=\nabla f(x^*), which makes the optimum a fixed point even when ∇f(x∗)≠0\nabla f(x^*)\ne 0.

  3. Knowl 3 — Optimal trade-off between iterations and prox evaluations

    theoretical result

    For the strongly convex setting of ProxSkip, achieving E[ΨT]≤εΨ0\mathbb{E}[\Psi_T]\le\varepsilon\Psi_0 requires, up to logarithmic factors,

    T=O(max⁡{1γμ,1p2}log⁡1ε)T=O\left(\max\left\{\frac{1}{\gamma\mu},\frac{1}{p^2}\right\}\log\frac{1}{\varepsilon}\right)

    iterations. Since a prox is evaluated with probability pp in every iteration, the expected number of prox evaluations is

    E[Nprox]=O(max⁡{pγμ,1p}log⁡1ε).\mathbb{E}[N_{\mathrm{prox}}] =O\left(\max\left\{\frac{p}{\gamma\mu},\frac{1}{p}\right\}\log\frac{1}{\varepsilon}\right).

    Choosing the largest permitted stepsize, γ=1/L\gamma=1/L, and the probability

    p=μL=1κ,κ:=Lμ, p=\sqrt{\frac{\mu}{L}}=\frac{1}{\sqrt{\kappa}}, \qquad \kappa:=\frac{L}{\mu},

    preserves the proximal-gradient iteration complexity while reducing the prox complexity to

    T=O(κlog⁡1ε),E[Nprox]=O(κlog⁡1ε).T=O\left(\kappa\log\frac{1}{\varepsilon}\right), \qquad \mathbb{E}[N_{\mathrm{prox}}]=O\left(\sqrt{\kappa}\log\frac{1}{\varepsilon}\right).

    Hence, the expensive proximal operator can be skipped on most iterations without worsening the iteration rate.

  4. Knowl 4 — Scaffnew as randomized-communication consensus optimization

    model/method

    For federated optimization, the finite-sum problem

    min⁡x∈Rd1n∑i=1nfi(x)\min_{x\in\mathbb{R}^d}\frac{1}{n}\sum_{i=1}^n f_i(x)

    is written using client copies x1,…,xn∈Rdx_1,\ldots,x_n\in\mathbb{R}^d and the consensus regularizer

    ψ(x1,…,xn)={0,x1=⋯=xn,+∞,otherwise.\psi(x_1,\ldots,x_n)= \begin{cases} 0,&x_1=\cdots=x_n,\\ +\infty,&\text{otherwise}. \end{cases}

    The associated proximal operation is averaging the client models. Applying ProxSkip to this formulation gives Scaffnew. Each client ii maintains a model xi,tx_{i,t} and a control variate hi,th_{i,t}; initially all models are equal and the control variates satisfy ∑i=1nhi,0=0\sum_{i=1}^n h_{i,0}=0. At iteration tt, all clients compute in parallel

    x^i,t+1=xi,t−γ(∇fi(xi,t)−hi,t).\widehat{x}_{i,t+1}=x_{i,t}-\gamma\bigl(\nabla f_i(x_{i,t})-h_{i,t}\bigr).

    A shared Bernoulli decision with probability pp determines whether communication occurs. If communication occurs, the client models are averaged,

    xi,t+1=1n∑j=1nx^j,t+1, x_{i,t+1}=\frac{1}{n}\sum_{j=1}^n\widehat{x}_{j,t+1},

    and otherwise xi,t+1=x^i,t+1x_{i,t+1}=\widehat{x}_{i,t+1}. Every client then updates

    hi,t+1=hi,t+pγ(xi,t+1−x^i,t+1). h_{i,t+1}=h_{i,t}+\frac{p}{\gamma}\bigl(x_{i,t+1}-\widehat{x}_{i,t+1}\bigr).

    Thus, Scaffnew performs local gradient steps between randomly selected averaging rounds. At a communication round, the control-variate update is proportional to the accumulated deviation of client ii from the client average, scaled by the stepsize and expected local-phase length.

  5. Knowl 5 — Communication acceleration for heterogeneous federated learning

    theoretical result

    Suppose every local objective fi:Rd→Rf_i:\mathbb{R}^d\to\mathbb{R} is LL-smooth and μ\mu-strongly convex, with no assumption that the client functions are similar or that their gradients or Hessians have bounded dissimilarity. For deterministic Scaffnew, set γ=1/L\gamma=1/L and p=1/κp=1/\sqrt{\kappa}, where κ=L/μ\kappa=L/\mu. Then the method converges linearly with iteration complexity

    O(κlog⁡1ε),O\left(\kappa\log\frac{1}{\varepsilon}\right),

    while its expected communication complexity is only

    O(κlog⁡1ε).O\left(\sqrt{\kappa}\log\frac{1}{\varepsilon}\right).

    The expected number of local gradient steps between communications is 1/p=κ1/p=\sqrt{\kappa}. The result holds despite data heterogeneity: at the common optimum x∗x^*, the individual gradients ∇fi(x∗)\nabla f_i(x^*) need not vanish because the local control variates converge to these local gradients. The communication rate matches the stated first-order distributed lower bound up to logarithmic factors.

  6. Knowl 6 — Stochastic ProxSkip under expected smoothness

    theoretical result

    SProxSkip replaces the exact gradient in ProxSkip by a stochastic estimator gt(xt)g_t(x_t) and uses

    x^t+1=xt−γ(gt(xt)−ht),\widehat{x}_{t+1}=x_t-\gamma\bigl(g_t(x_t)-h_t\bigr),

    followed by the same Bernoulli prox decision and control-variate update as ProxSkip. Assume conditional unbiasedness,

    E[gt(xt)∣xt]=∇f(xt),\mathbb{E}[g_t(x_t)\mid x_t]=\nabla f(x_t),

    and expected smoothness: for constants A,C≥0A,C\ge 0, every tt satisfies

    E[∥gt(xt)−∇f(x∗)∥2∣xt]≤2ADf(xt,x∗)+C,\mathbb{E}\left[\left\lVert g_t(x_t)-\nabla f(x^*)\right\rVert^2\mid x_t\right] \le 2A D_f(x_t,x^*)+C,

    where Df(x,y):=f(x)−f(y)−⟨∇f(y),x−y⟩D_f(x,y):=f(x)-f(y)-\langle\nabla f(y),x-y\rangle. If ff is LL-smooth and μ\mu-strongly convex, ψ\psi is proper, closed, and convex, and 0<γ≤1/A0<\gamma\le 1/A, then with ζ:=min⁡{γμ,p2}\zeta:=\min\{\gamma\mu,p^2\},

    E[ΨT]≤(1−ζ)TΨ0+γ2Cζ.\mathbb{E}[\Psi_T] \le (1-\zeta)^T\Psi_0+\frac{\gamma^2 C}{\zeta}.

    The stochastic method therefore converges geometrically to a neighborhood whose size is controlled by the noise term CC. For a target 0<ε<10<\varepsilon<1, choosing

    γ=min⁡{1A,εμ2C},p=γμ\gamma=\min\left\{\frac1A,\frac{\varepsilon\mu}{2C}\right\}, \qquad p=\sqrt{\gamma\mu}

    is sufficient, with

    T=O(max⁡{Aμ,2Cεμ2}log⁡2Ψ0ε)T=O\left(\max\left\{\frac{A}{\mu},\frac{2C}{\varepsilon\mu^2}\right\}\log\frac{2\Psi_0}{\varepsilon}\right)

    iterations and the same expression with square roots in place of the two terms for the expected number of prox evaluations.

  7. Knowl 7 — Decentralized Scaffnew with intermittent graph communication

    model/method

    For a connected communication graph, let W∈Rn×nW\in\mathbb{R}^{n\times n} be symmetric, positive semidefinite, and doubly stochastic, with Wij≠0W_{ij}\ne0 only when nodes ii and jj communicate. Each node maintains xi,t,hi,t∈Rdx_{i,t},h_{i,t}\in\mathbb{R}^d, starts from a common model xi,0x_{i,0} and hi,0=0h_{i,0}=0, and uses stepsizes γ>0\gamma>0 and τ>0\tau>0. At every iteration, node ii first computes

    x^i,t+1=xi,t−γ(∇fi(xi,t)−hi,t).\widehat{x}_{i,t+1}=x_{i,t}-\gamma\bigl(\nabla f_i(x_{i,t})-h_{i,t}\bigr).

    With probability pp, nodes communicate and update

    xi,t+1=(1−γτp)x^i,t+1+γτp∑j=1nWijx^j,t+1, x_{i,t+1}=\left(1-\frac{\gamma\tau}{p}\right)\widehat{x}_{i,t+1} +\frac{\gamma\tau}{p}\sum_{j=1}^n W_{ij}\widehat{x}_{j,t+1}, hi,t+1=hi,t+pγ(xi,t+1−x^i,t+1). h_{i,t+1}=h_{i,t}+\frac{p}{\gamma}\bigl(x_{i,t+1}-\widehat{x}_{i,t+1}\bigr).

    With probability 1−p1-p, communication is skipped and the updates are xi,t+1=x^i,t+1x_{i,t+1}=\widehat{x}_{i,t+1} and hi,t+1=hi,th_{i,t+1}=h_{i,t}. The method is the graph-consensus specialization of a more general primal-dual prox-skipping construction for objectives of the form f(x)+ψ(Lx)f(x)+\psi(Lx), where L⊤L=I−WL^\top L=I-W; graph communication implements multiplication by I−WI-W.

  8. Knowl 8 — Decentralized convergence and spectral-gap trade-off

    theoretical result

    Let each local objective fif_i be LL-smooth and μ\mu-strongly convex. Let x∗x^* minimize the average objective, let xˉT:=n−1∑i=1nxi,T\bar{x}_T:=n^{-1}\sum_{i=1}^n x_{i,T}, and let

    δ:=1−λ2(W)∈(0,1)\delta:=1-\lambda_2(W)\in(0,1)

    be the spectral gap of the symmetric mixing matrix WW. For decentralized Scaffnew, if 0<p≤10<p\le1, γ≤1/L\gamma\le1/L, and τ≤p/γ\tau\le p/\gamma, then

    E[∥xˉT−x∗∥2]≤(1−min⁡{γμ,pγτδ})TΦ0,\mathbb{E}\left[\lVert\bar{x}_T-x^*\rVert^2\right] \le \left(1-\min\{\gamma\mu,p\gamma\tau\delta\}\right)^T\Phi_0,

    where the initial Lyapunov bound can be taken as

    Φ0≤∥x0−x∗∥2+γpτδn∑i=1n∥∇fi(x∗)∥2.\Phi_0\le \lVert x_0-x^*\rVert^2 +\frac{\gamma}{p\tau\delta n}\sum_{i=1}^n\lVert\nabla f_i(x^*)\rVert^2.

    Setting τ=p/γ\tau=p/\gamma gives an iteration rate proportional to

    O~(κ+1p2δ),κ:=Lμ.\widetilde{O}\left(\kappa+\frac{1}{p^2\delta}\right), \qquad \kappa:=\frac{L}{\mu}.

    For a sufficiently well-connected network, the probability p=1/δκp=1/\sqrt{\delta\kappa} balances optimization and communication effects. If δ≤1/κ\delta\le1/\kappa, this choice exceeds one, so the best admissible choice is p=1p=1, meaning communication at every iteration.

  9. Knowl 9 — Logistic-regression experiments on communication skipping

    empirical result

    The experiments reported on page 9 evaluate Scaffnew and competing local-update methods on the LIBSVM ``w8a'' dataset using regularized logistic regression,

    f(x)=1N∑i=1Nlog⁡(1+exp⁡(−biai⊤x))+λ2∥x∥2, f(x)=\frac1N\sum_{i=1}^N\log\left(1+\exp\bigl(-b_i a_i^\top x\bigr)\right)+\frac{\lambda}{2}\lVert x\rVert^2,

    where ai∈Rda_i\in\mathbb{R}^d, bi∈{−1,+1}b_i\in\{-1,+1\}, and λ=10−4L\lambda=10^{-4}L. Implementations used Python and Ray on a 24-core Intel Xeon Gold 6146 workstation. The deterministic experiments compare LocalGD, Scaffold, Scaffnew, FedLin, and S-Local-GD by objective gap versus communication rounds. With tuned hyperparameters, LocalGD approaches only a neighborhood because of data heterogeneity, while Scaffold and Scaffnew have similar and better communication-round convergence than the other methods. With theoretically prescribed hyperparameters, Scaffnew substantially outperforms the baselines because its analysis permits a large stepsize; the number of local steps is set near κ^\sqrt{\widehat{\kappa}}, with κ^=L/λ\widehat{\kappa}=L/\lambda. Varying the communication probability shows that communicating too often (1/p=1001/p=100) or too rarely (1/p=10001/p=1000) hurts convergence, while 1/p=3001/p=300 is best in this experiment and is close to the theoretical choice p=1/κp=1/\sqrt{\kappa}. Stochastic experiments show that increasing the number of clients produces a speedup, stronger than the speedup predicted by the stochastic convergence bound.

  10. Knowl 10 — Limitation of the stochastic federated-learning analysis

    limitation

    When the stochastic ProxSkip analysis is applied to federated learning, its bound does not establish linear speedup as the number of clients increases. The authors attribute this limitation to the analysis technique rather than to a demonstrated failure of the algorithm; the same issue appears in the cited FedLin analysis but not in the cited Scaffold analysis. The deterministic communication-acceleration result does not require a client-similarity assumption, but the stochastic theorem retains a noise-dependent neighborhood term and does not provide a client-count speedup guarantee.

Coverage note — Proof-only lemmas and derivations, acknowledgements, background, and redundant baseline-comparison details were omitted; the contributed deterministic, stochastic, federated, decentralized, and empirical results are covered.

References

  1. 1.Arjevani, Y. and Shamir, O. Communication complexity of distributed convex learning and optimization. In Advances in Neural Information Processing Systems, 2015. (Cited on pages 4 and 7)
  2. 2.Bauschke, H. H., Moursi, W. M., and Wang, X. Generalized monotone operators and their averaged resolvents. Mathematical Programming, 189(1):55–74, 2021. (Cited on page 5)
  3. 3.Beck, A. First order methods in optimization. MOS-SIAM Series on Optimization, 2017. (Cited on page 1)
  4. 4.Chang, C.-C. and Lin, C.-J. LIBSVM: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1–27, 2011. (Cited on page 9)
  5. 5.Chen, P., Huang, J., and Zhang, X. A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Problems, 29(2):025011, 2013. (Cited on page 18)
  6. 6.Combettes, P. L. and Pesquet, J.-C. Proximal splitting methods in signal processing. arXiv preprint arXiv:0912.3522, 2009. (Cited on page 1)
  7. 7.Combettes, P. L., Condat, L., Pesquet, J.-C., and Vu, B. C. A ˜ forward-backward view of some primal-dual optimization methods in image recovery. In 2014 IEEE International Conference on Image Processing (ICIP), pp. 4141–4145. IEEE, 2014. (Cited on page 18)
  8. 8.Condat, L., Kitahara, D., Contreras, A., and Hirabayashi, A. Proximal splitting algorithms for convex optimization: A tour of recent advances, with new twists. arXiv preprint arXiv:1912.00137, 2019. (Cited on page 18)
  9. 9.Condat, L., Malinovsky, G., and Richtarik, P. Distributed proximal splitting algorithms with rates and acceleration. Frontiers in Signal Processing, pp. 12, 2022. (Cited on page 18)
  10. 10.Dekel, O., Gilad-Bachrach, R., Shamir, O., and Xiao, L. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1):165–202, January 2012. (Cited on page 7)
  11. 11.Drori, Y., Sabach, S., and Teboulle, M. A simple algorithm for a class of nonsmooth convex–concave saddle-point problems. Operations Research Letters, 43(2):209–214, 2015. (Cited on page 18)
  12. 12.Friedlander, M. and Goh, G. Efficient evaluation of scaled proximal operators. Electronic Transactions on Numerical Analysis, 46:1–23, 03 2016. (Cited on page 2)
  13. 13.Gorbunov, E., Hanzely, F., and Richtarik, P. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556–3564. PMLR, 2021. (Cited on pages 2, 3, and 7)
  14. 14.Gower, R. M., Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E., and Richtarik, P. SGD: General analysis and improved rates. In International Conference on Machine Learning, pp. 5200–5209. PMLR, 2019. (Cited on pages 4 and 7)
  15. 15.Gower, R. M., Richtarik, P., and Bach, F. Stochastic quasi-gradient methods: Variance reduction via Jacobian sketching. Mathematical Programming, 188(1):135–192, 2021. (Cited on pages 4 and 7)
  16. 16.Hanzely, F. and Richtarik, P. Federated learning of a mixture of global and local models. arXiv:2002.05516, 2020. (Cited on page 7)
  17. 17.Hanzely, F., Hanzely, S., Horvath, S., and Richt arik, P. Lower bounds and optimal algorithms for personalized federated learning. volume 33, pp. 2304–2315, 2020. (Cited on page 7)
  18. 18.Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D’Oliveira, R. G. L., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z., Gascon, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Harchaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konecnˇ y, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Ozg ur, A., Pagh, R., Raykova, M., Qi, H., Ramage, D., Raskar, R., Song, D., Song, W., Stich, S. U., Sun, Z., Suresh, A. T., Tramer, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q., Yu, F. X., Yu, H., and Zhao, S. Advances and open problems in federated learning. Foundations and Trends® in Machine Learning, 14(1–2):1–210, 2021. (Cited on pages 2, 3, and 6)
  19. 19.Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S. U., and Suresh, A. T. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132–5143. PMLR, 2020. (Cited on pages 2, 3, 4, and 7)
  20. 20.Karimireddy, S. P., Jaggi, M., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. Breaking the centralized barrier for cross-device federated learning. In Advances in Neural Information Processing Systems 34 (NeurIPS). Curran Associates, Inc., 2021. (Cited on page 7)
  21. 21.Khaled, A., Mishchenko, K., and Richtarik, P. First analysis of local GD on heterogeneous data. In NeurIPS Workshop on Federated Learning for Data Privacy and Confidentiality, pp. 1–11, 2019. (Cited on pages 2 and 3)
  22. 22.Khaled, A., Mishchenko, K., and Richtarik, P. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020. (Cited on pages 2, 3, and 7)
  23. 23.Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. U. A unified theory of decentralized SGD with changing topology and local updates. In 37th International Conference on Machine Learning (ICML). PMLR, 2020. (Cited on pages 2 and 7)
  24. 24.Koloskova, A., Lin, T., and Stich, S. U. An improved analysis of gradient tracking for decentralized machine learning. In Advances in Neural Information Processing Systems 34 (NeurIPS), volume 34. Curran Associates, Inc., 2021. (Cited on page 5)
  25. 25.Konecnˇ y, J., McMahan, H. B., Yu, F., Richt arik, P., Suresh, A. T., and Bacon, D. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016. (Cited on page 2)
  26. 26.Kovalev, D., Salim, A., and Richtarik, P. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Neural Information Processing Systems (NeurIPS), 33:18342–18352, 2020. (Cited on pages 5 and 8)
  27. 27.Kovalev, D., Gasanov, E., Richtarik, P., and Gasnikov, A. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. In Advances in Neural Information Processing Systems 34, 2021a. (Cited on page 5)
  28. 28.Kovalev, D., Shulgin, E., Richtarik, P., Rogozin, A., and Gasnikov, A. ADOM: Accelerated decentralized optimization method for time-varying networks. In International Conference on Machine Learning, pp. 5784–5793. PMLR, 2021b. (Cited on page 5)
  29. 29.Lan, G. An optimal method for stochastic composite optimization. Mathematical Programming, 133:365–397, 2012. (Cited on page 3)
  30. 30.Lin, T., Stich, S. U., and Jaggi, M. Don’t use large mini-batches, use local SGD. In International Conference on Learning Representations (ICLR), 2018. (Cited on page 2)
  31. 31.Lin, T., Karimireddy, S. P., Stich, S., and Jaggi, M. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pp. 6654–6665. PMLR, 2021. (Cited on page 7)
  32. 32.Lorenzo, P. D. and Scutari, G. NEXT: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016. (Cited on page 5)
  33. 33.Loris, I. and Verhoeven, C. On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty. Inverse Problems, 27(12), 2011. (Cited on page 18)
  34. 34.Luke, D. R. Proximal Methods for Image Processing, pp. 165–202. Springer International Publishing, Cham, 2020. ISBN 978-3-030-34413-9. (Cited on page 1)
  35. 35.Malinovskiy, G., Kovalev, D., Gasanov, E., Condat, L., and Richtarik, P. From local SGD to local fixed-point methods for federated learning. In International Conference on Machine Learning, pp. 6692–6701. PMLR, 2020. (Cited on page 7)
  36. 36.Mangasarian, O. L. and Solodov, M. V. Backpropagation convergence via deterministic nonmonotone perturbed minimization. In Cowan, J., Tesauro, G., and Alspector, J. (eds.), Advances in Neural Information Processing Systems, volume 6. Morgan-Kaufmann, 1994. (Cited on page 2)
  37. 37.McDonald, R., Hall, K., and Mann, G. Distributed training strategies for the structured perceptron. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 456–464. Association for Computational Linguistics, 2010. (Cited on page 2)
  38. 38.McMahan, H. B., Moore, E., Ramage, D., and y Arcas, B. A. Federated learning of deep networks using model averaging. arXiv preprint arXiv:1602.05629, 2016. (Cited on pages 2 and 6)
  39. 39.Mitra, A., Jaafar, R., Pappas, G., and Hassani, H. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34, 2021. (Cited on pages 2, 3, and 7)
  40. 40.Moritz, P., Nishihara, R., Wang, S., Tumanov, A., Liaw, R., Liang, E., Elibol, M., Yang, Z., Paul, W., Jordan, M. I., and Stoica, I. Ray: A distributed framework for emerging AI applications. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pp. 561–577, 2018. (Cited on page 9)
  41. 41.Nedic, A., Olshevsky, A., and Shi, W. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27, 07 2016. (Cited on page 5)
  42. 42.Nesterov, Y. Introductory lectures on convex optimization: a basic course (Applied Optimization). Kluwer Academic Publishers, 2004. (Cited on page 3)
  43. 43.Nesterov, Y. Gradient methods for minimizing composite functions. Mathematical Programming, 140(1):125–161, 2013. (Cited on page 1)
  44. 44.Parikh, N. and Boyd, S. Proximal algorithms. Foundations and Trends in Optimization, 1(3):127–239, jan 2014. (Cited on pages 1 and 2)
  45. 45.Salim, A., Condat, L., Mishchenko, K., and Richtarik, P. Dualize, split, randomize: Fast nonsmooth optimization algorithms. arXiv preprint arXiv:2004.02635, 2020. (Cited on page 18)
  46. 46.Shalev-Shwartz, S. and Ben-David, S. Understanding machine learning: from theory to algorithms. Cambridge University Press, 2014. (Cited on pages 1 and 2)
  47. 47.Stich, S. U. Local SGD converges fast and communicates little. In International Conference on Learning Representations (ICLR), 2019. (Cited on page 2)
  48. 48.Tang, H., Lian, X., Yan, M., Zhang, C., and Liu, J. D2: Decentralized training over decentralized data. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pp. 4848–4856. PMLR, 2018. (Cited on page 5)
  49. 49.Vogels, T., He, L., Koloskova, A., Lin, T., Karimireddy, S. P., Stich, S. U., and Jaggi, M. Relaysum for decentralized deep learning on heterogeneous data. In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc., 2021. (Cited on page 5)
  50. 50.Woodworth, B., Patel, K. K., Stich, S. U., Dai, Z., Bullins, B., McMahan, H. B., Shamir, O., and Srebro, N. Is local SGD better than minibatch SGD? In 37th International Conference on Machine Learning (ICML). PMLR, 2020a. (Cited on page 7)
  51. 51.Woodworth, B. E., Patel, K. K., and Srebro, N. Minibatch vs local SGD for heterogeneous distributed learning. volume 33, pp. 6281–6292, 2020b. (Cited on page 3)
  52. 52.Woodworth, B. E., Bullins, B., Shamir, O., and Srebro, N. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 4386–4437. PMLR, 15–19 Aug 2021. (Cited on page 3)
  53. 53.Yuan, H. and Ma, T. Federated accelerated stochastic gradient descent. In Larochelle, H., Ranzato, Hadsell, R., Balcan, M. F., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5332–5344. Curran Associates, Inc., 2020. (Cited on page 7)
  54. 54.Yuan, K. and Alghunaim, S. A. Removing data heterogeneity influence enhances network topology dependence of decentralized SGD. arXiv preprint arXiv:2105.08023, 2021. (Cited on page 5)
  55. 55.Zhang, J., De Sa, C., Mitliagkas, I., and Re, C. Parallel SGD: When does averaging help? arXiv preprint arXiv:1606.07365, 2016. (Cited on page 2)
  56. 56.Zhou, H. and Hastie, T. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society B, 67:301–320, 2005. (Cited on page 1)

Citation

MLA
Mishchenko, K., et al. “ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!”. International Conference on Machine Learning, vol. 162, 2022, pp. 15750–69, https://proceedings.mlr.press/v162/mishchenko22b.html.
APA
Mishchenko, K., Malinovsky, G., Stich, S., & Richtarik, P. (2022). ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!. International Conference on Machine Learning, 162, 15750–15769. https://proceedings.mlr.press/v162/mishchenko22b.html
Chicago
Mishchenko, K., G. Malinovsky, S. Stich, and P. Richtarik. 2022. “ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!”. International Conference on Machine Learning 162: 15750–69. https://proceedings.mlr.press/v162/mishchenko22b.html.
Harvard
Mishchenko, K. et al. (2022) “ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!”, International Conference on Machine Learning. PMLR, pp. 15750–15769. Available at: https://proceedings.mlr.press/v162/mishchenko22b.html.
Vancouver
1. Mishchenko K, Malinovsky G, Stich S, Richtarik P (2022) ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!. In: International Conference on Machine Learning. PMLR, pp 15750–15769

BibTeX

@InProceedings{pmlr-v162-mishchenko22b,
  title = 	 {{P}rox{S}kip: Yes! {L}ocal Gradient Steps Provably Lead to Communication Acceleration! {F}inally!},
  author =       {Mishchenko, Konstantin and Malinovsky, Grigory and Stich, Sebastian and Richtarik, Peter},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {15750--15769},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/mishchenko22b/mishchenko22b.pdf},
  url = 	 {https://proceedings.mlr.press/v162/mishchenko22b.html},
  abstract = 	 {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}(\kappa \log \nicefrac{1}{\varepsilon})$, where $\kappa$ is the condition number of $f$, the number of prox evaluations is $\mathcal{O}(\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 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.}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/