Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with an Inexact Prox
Authors: Abdurakhmon Sadiev
Dmitry Kovalev
Peter Richtárik
Venue: NeurIPS 2022 Accept (2022)
Keywords: ProxSkip
Communication Acceleration
Federated Learning
Local Gradient Descent
Federated Averaging
Primal-Dual Methods

Abstract: 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 or Fast GD), 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 ($\mathcal{O}(\kappa^{1/3})$ or $\mathcal{O}(\kappa^{1/4})$, compared to $\mathcal{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.

Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox
Abdurakhmon Sadiev* KAUST! MIPT! ISP RAS abdurakhmon.c sadievakauusue edu.
Dmitry Kovaley KAUST dakovalev1@@maill com
Peter Richtárik
KAUST
richtarik@gmail.com
Abstract
Inspired by recent breakthrough of Mishchenko et al. (2022). who for the first time showed that local gradient steps can lead to provable communication accelera- tion, propose alternative algorithm which obtains the same communication accelcration as their method (ProxSkip). Our approach very different, however: it is based the celebrated method of Chambolle and Pock [20TT]. with several nontrivial modifications: we allow for an inexact computation of the prox op- erator of certain smooth strongly convex function via suitable gradient- based method (e.g., GD, Fast GD or FSFOM), ii) we perform a careful modification the dual update step in order to retain linear convergence. Our general results offer the new state-of-the-ard 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(1//3) or (rx compared to O of ProxSkip). and performs 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.
Introduction
Communication efficiency of distributed stochastic gradient descent (SGD) can be improved, often dramatically, via a simple trick: instead of synchronizing the parameters across the parallel workers after every SGD step, let the workers perform multiple optimization steps using their local loss and data only before synchronizing. This trick dates back at least to two or three decades ago MMangasarian 1995), and may be much older. Due its simplicity, it has been repeatedly rediscovered [Povey et al.
Moritz et al. 20166] Ma et al.) 2017). is the basis of the famous federated averaging (FedAvg) algorithm of McMahan al. [2016] 2017], which is the workhorse of federated learning (Konečný
2014
et al. 2016b see also the recent surveys on federated learning [Li et al. 2020a Kairouz et al.
2019
and federated optimization [Wang al. 2021b).
"This work was written while A. Sadiev was a research intern at KAUSS during the last semester of his MS studies at the Moscow Institute of Physics and Technology, Dolgoprudny, Russia.
Kiing Abdullah University of Science and Technology, Thuwal, Saudi Arabia i "Moscow Institute of Physies and Technology, Dolgoprudny, Russia
$ Institute for System Programming of the Russian Academy of Sciences, Research Center for Trusted Artificial Intelligence, Mascow, Russia
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Towards provable communication acceleration via delayed parameter synchronization
Until recently, this simple trick resisted all attempts at an appropriate theoretical justification. Through collective effort of the federated learning community, the bounds of various local SGD methods were
progressively getting hetter [Haddadpour and Mahdavi (209 Li ei et al. 2019a b Khaled et al. 2211aa]h
2020
Li et al. [2020b Woodworth al.[[2020] [Stihh] [2200] Gorbunov al. 2020a Malinovsky et al.
2020
Pathak and Wainwright 2020 Karimireddy et al. [0200] Malinovsk et al. [202]] Mishchenko
al. 2021a| Wang and Joshi 2021 Horváth al. [022]. J. and the assumptions required achieve
them weaker. A brief overview of the progress is provided in [Mishchenko et al. 2022]. However,
all known theoretical rates are worse than the rate of gradient descent, which synchronizes after
every gradient step. In recent breakthrough. Mishhhenko et al. (2022) developed a novel local SGD method, called ProxSkip. which performs random number local gradient (or stochastic gradient) steps before synchromization, and proved that it enjoys strong communication acceleration properties. In particular, while the method needs (1s log !)) iterations, only (VV log !) involve communication.
of them
1.2 Problem formulation
In this paper, we consider the composite optimization problem
min ZER
(I)
where G : Rd + R is smooth and strongly convex function, F; Rd + R (+oo} is a proper, closed and convex function, and K Rd - Rd a linear map. Let us define
Lay def max { E Rd= ||-|||| =1],
(2)
where ||-|| refers to the standard Euclidean norm. Note that L 2 Amax (KKT) = Amax (K (KT)).
It will be useful to formalize our assumptions at this point as we will refer to the various constants involved them throughout the text.
Assumption 1. Function G Rd - R is p22 -t-sonnggly convex, i.e.,
G(x') -0))GG(")) (VG(a"), - x²) Mz 1I' x"11
Val,=" " Rdo
(3)
Assumption 2. The function G Rd + R is L -moothhh i.e.
|[V((z') V || S Lu 1| - r"Il.
Va' x" E Rd=
(4)
Assumption 3. Function F R. + R U { is proper, closed and convex.
Assumption (See Kovalev et al. (021aa), There exists a constant Hay > such that
x (KKT),
OF) E rangeK for all y E Rdd,
May 5
Amin [KK]
otherwise.
1.3 ProxSkip
The most general version of the ProxSkip method Mishchenko et al. 2022
designed to solve problems of the form ( In each iteration, ProxSkip evaluates the gradient of G and then flips biased coin: with probability p. it additionally evaluates the proximity operator of [+, and performs matrix-vector multiplication involving K. The method becomes relevant to the standard optimization formulation of federated learning (FL.), i.e., the finite-sum optimization problem
min EER
Sc(w),
(5)
through its application to its consensus reformulation
min
Σ
+ (5 ((I....,
xt))
min G(x) + F(x),
(6)
RR
TThis variant is called SplitSkip in their paper.

---

Table I: Summary of the key complexity results obtained by our methods APDA (Algorithm) Theorem and APDA with Inexact Prox (Algorithm 2 problem
!
Theorem
2
for solving the saddle-point
Lincar
No G
No F
Works
Algorithm
with
with
rate
Outer Iterations (1)
Inner Iterations" (I)
Ly
My
CPds
Lay Pt
peox of G
AIrGAA ho
X
max
Lu px
-12
APDG
x
max
Vireh
pay
Auay
(3)
Alg
Azv" 12
uses prox of
Alg
Asy"
max
King
66 K K2y (1)
Alg
Asy (
max
b/4
2/ kay Pazy
Alg
Aay
May 1 may 1691
Chambolle and Pack
2011 assume that and got ure jay and stmougly-commss, respectively. We do not assume F to be strougly conves. aeaume that the functions and g T-smooth (Le., = max lyg Fuzy }), and
Zhang et 2022]
Kovalev 2021a
asoume that functions and are La Ly smyotoot respectively, and
pay stoonglly
Kzy. x J. We cmnt constant factors and log 1 factor in all expressions, for brevity. So, for example, the expression Azy in the case of the method of our methods should be inserpeesed as O (Azy log t).
For brevity, we let de Laz. del Liz and Azy del max 1/2
Pay"
evaluatoos the prox F outer operator and hence no inner ieenioon.
There
The itenative method M evalunting the pros of G inexactly this case is: M = (sce Lemma 0
The ttentiie methed evaluniing pres G inexactly this
PGD (Fist Gradient Descent)
cmmm
The iterttvve method M evalunting the pros of G incsaclly in this case is: M FSFOM + FGD (Fust Gradient Desuent). See Lemma
where dg nd, (I1, 2nd Rnd, G(z) function of the constraint T1 = In, i...
Eis f((xs), and F vb is the indicator
def 10 if 11= In
((
Fnn +00 otherwise
The evaluation of the proximity operator of F is equivalent to averaging of the vectors Ti..... Zn. which necessitates communication. Therefore, if p is small, ProxSkip communicates very rarely. Since G' is block separable, the gradient steps involving G, taken in between two communications, correspond to gradient steps with respect the local loss functions {fi} taken by the clients. See [Mishchenko et al.] 2022 for the details; we will elaborate on this as well in Section 6
ProxSkip inexactly solves problem ( in O (w log t/e) iterations, out of which only O (vFx log !) involve communication, where is a condition number measuring the connectivity of the graph (the standard setup in FL corresponds a fully connected graph, in which case X = see (26 for definition).
2 Summary of Contributions
Inspired by the results of Mishchenko et al. [2022] we propose an alternative and substantially different algorithm which obtains the same guarantees for the number of prox evaluations (wrt F) as ProxSkip, but has better guarantees for the number of gradient steps (wrt G)) in between the prox evaluations. Below summarize the main contributions:
Saddle-point formulation. Unlike Mishchenko et al. 2002 we consider the saddle-point refor-
mulation of I|
min Ze vERds
max {G(z) + (y. Kx) FY))
where F* (v) del supye (v. vz) - F(y') is the convex conjugate of F. Since F is proper, closed and convex, is F*. We assume throughout that 7 is solvable, i.c., there exists at least one solution
3

---

(xt ,y"), Such solution then satisfies the first-oder optimality condition 6
0 E (=(²") + y" 0 (F* - Kx',
(8)
where & denotes the subdifferential. By working with this reformulation, we can tap into the rich and powerful philosophical and technical toolbox offered by proximal-pon point theory, fixed point theory, and primal-dual methods, which facilitates the algorithm development and analysis. This ultimately enables us shed new light the nature of local gradient-type steps as inexact computations of the prox operator of G in a new appropriately designed Accelerated Primal-Dual Algorithm (APDA; see Algorithm| T.
Modifications of Chambolle-Pock Our Algorithms and are inspired by the celebrated Chambolle-Pock method [Chambolle and Pock 2011]. but with several important and nontriv- ial modifications. While Chambolle-Pock achieves linear convergence when both and F are strongly convex, F is merely convex in our setting. Our modifications are:
i) Inspired by the ideas of Kovalev et al. [02 we perform a careful modification of the dual update step (update of y)) in order to retain linear convergence despite lack of strong convexity in F*. On the other hand, in contrast to the method of Kovalev et al. (2021a), we do not assume F to be smooth. This modification leads to a new method, which we call APDA (Algorithm[] APDA relies on the evaluation of the prox operators of both and F*.
ii) Next, we remove the reliance on the prox operator of G. and instead allow for its inexact evaluation via suitable user-defined gradient-based method, which we call M (see (2) and Lemma [T. We call the resulting method "APDA with Inexact Prox" (Algorithm
The
choice of method MM will have a strong impact on the number of inexact/local steps. and this is one of the places in which we improve upon the results of Mishchenk et al. 2022
General theory Our general complexity results for Algorithms I and
covered in Theorems 7 and
respectively, contrasted with the key baselines, are summarized in Table While the method of
[Camboole and Pock 2011] needs F" to be strongly convex to obtain linear rate, we only need convexity. While the AIIDA [Zhang al. [022] and APDG [Kovalev et al., [2021a] methods enjoy linear rates without strong convexity of F*, both require F* to be Ly -smooh... In contrast, we do not need this assumption (i.e., we allow T.y = oo). Our methods are the first to obtain linear convergence rates in the regime when G is -mooohh and wu--strongly-convex and F is merely proper, closed and convex, without requiring it to be -yy-moothh, nor /4y-strongly-conver This important in some applications. Our two methods offer two alternative ways of dealing with this regime: while APDA (Algorithm D relies on the evaluation the prox of G. APDA with Inexact Prox (Algorithm) not. As we shall see, the latter method has an important application in federated learning.
2 does
Federated learning and third method When applied the distributeedfeddrraee problem (5) (see Section 6). APDA with Inexact Prox (Algorithm 2 turns out to be theoretically better alternative to ProxSkip Mishchenno et al., 2022]. In the centralized case, our method requires the same optimal number of communication rounds (V(K), where x = L=/ux) as ProxSkip, but requires fewer local gradient-type steps (k.1/) or (x*1/1), compared to (x:1/2) of ProxSkip, depending on the choice of the inner method M). Like ProxSkip. our method can be applied to optimization over connected network, and we obtain theoretical improvements in this decentralized scenario as well. However, in the decentralized regime, neither ProxSkip nor Algorithm 2 obtain the optimal bound for the number of communication rounds. For this reason, we propose a third method (Algorithm 5) which employs ProxSkip uses a random number of local steps, all our methods perform a deterministic number of local steps. Our complexity results are summarized in Table 2
accelerated gossip routine to remedy this situation. It is also notable that while
3 From Proximal Point Method to Chambolle-Pock
In this section, we briefly motivate the development of the celebrated Chambolle-Pock method which acts as starting point of our algorithm design.
WWhenever we invoke Assumption 2 (LLo-tomts of G), we have aG(x) = (VG(=)), and hence the first condition can be replaced by VG(x*) + K TT

---

Table 2: Summary of our general convergence results provided by Theorem 2 for Algorithm 2 (APDA with Inexact Prox) and Theorem for A (APPAA with Inexact Prox and Accelerated Gossip) for solving the saddle-point reformulation
25
of the federated learning problem (5)
Contralized case
Decetralized case
Method M
Deter- ministic # comm. rounds
Algorithm
Ior Inexact
#comm. rounds?
Optimal
oocal
steps
Optimal
#comm. munds?
#l
steps
round
per round
Mishchenko al.
ProxSkip
2022
GD
(V
(VR)
GD
δ (v
Ö (VR)
Thm
RGD+GD
Ô ( (())
X
Ö ( ((K)
FGD+FSFOM
Ô (x)
( (<x)
GD
Ö (vR)
Ö (V*)
Thm
FGD+GD
Ô (())
( (m)
FGD+FSFOM
Ô (W)
( (R)
true only x-
GD Gradiest Descent; HGD Fast Gradiemt Descent (Le., Nestroo'ss acceterated GDY; FSFOM fixed-stop first-ocder method from Kim and Fessles 2023
3.1 Proximal-Poinn Method for finding zeros of monotone operators
Our starting point is the general problem of finding a zero of an (set-valued) operator A H - 2 where H is Hilbert space, i.e., find H such that
0 E A(z).
(9)
If A is maximally monotone, its resolvent (Id + n,4)-1 1 is single valued, nonexpansive, and has full domain. Moreover, O A(2) iff (Id + 17-4))-(-3 (2). The corresponding fixed point iteration, i.e., =+1 (Id 1yA)-1(2h ), is called the proximal point method (PPM) [Rockafellar 1976). This can be equivalently written as * (Id + +=)(=*+1)) and subsequently as
gt+1 2 A
From now on, for simplicity only, we will ignore the fact that in general, A(=*t1) is set, and will write 2+1 z
n1(=+t1 instead to mean the same thing, i.e., that there exists u E A(2*t1)
such that 26+1 z* nyu.
3.2 PPM applied to the saddle-point problem
The optimality conditions K) of the saddle point problem can be written in the form 9 with v) E T2 x Rd as follow??
2
(0)
(
② def
(oG())+KT) (FF KI
(10)
y
Allowing for different stepsizes 7r Mly for each block the vector 2 = (x; PPM applied to (10) takes the form kt1 E - ell E - (ar (1 ) K kx++1).
T (BG + K x
The main advantage of this method is its unboundedly fast convergence rate under weak assumptions. According to Theorem 4 the proof of which we provide in the appendix for completeness, if G and F* are proper and closed, G is Mr strongly convex and F* is My strongly convex, then any choice of stepsizes 1h2 >> 0 and Byy (yes, without an upper bound!), PPM find an e-accurate solution in
((1 mnn nnp
1
log E
(11)
iterations, Unfortunately, PPM is not implementable since in order to compute x+1 we need to know 1+1, and vice versa.
We replaced VG 0G here the beginning of our story does not require G to be smooth.
5

---

Algorithm APDA
1: Input: Initial point (x", )²) 1Rd x Rdy, 70 yr: Step sizes 1/ fly By 0. [0,
2: for k == 0,1,-- ..... do
3: Iktl xx The (VG(x K yz)
4: y E nh Th (DF(yttt) kattt) Th Sy (KT y VG(x
5: g = y + 1 (yh+1 - -²²)
6: end for
3.3 Chambolle-Pock: Making PPM implementable, and fast
In order overcome the above problem, Chambolle and Pock [01 proposed replace y^ with y (see Algorithm in [Chmmboll and Pock 2011)). which leads to
x+1 E - (aG( + K y*) Ty (aF* (1 11) Kxtt1).
g E -
Although this method is implementable, has its own disadvantages, of which is its weak iteration complexity bound
L2 1 o
( Haffy
log
(12)
E)
Chambolle and Pock [201]] proposed to fix this problem via an extrapolation step of the dual variable (see Algorithm in Chambolle and Pock 2011)):
k+1 x² nu (0G(x + K g²) 1²² - fl (aF (1/ k+1) ) - ksttl)
1 k+1
ghtl
y g + O )²)
This new method enjoys the much better iteration complexity bound
Lay (Leey Pa
log 1
O
(13)
Accelerated Primal-Dual Algorithm (Algorithm I
Recall that the Chambolle-Podd method requires F* be strongly-convex obtain linear conver- gence rate. However, in our setting, F* is not strongly convex (see Assumption 3 and Chambolle- Pock method does not converge linearly in this scenario.
4.1 Modifying Chambolle-Pock to preserve linear rate without strong convexity of F*
To obtain linear rate, we modify the dual update step of the algorithm using a trick proposed by Kovalev et al. [2021a] that was shown to work in the regime when F* is smooth; the innovation here
that we do not need this assumption (see Table [ From this point onwards, we will also need to assume G to be -m-soh (see Assumption 2. particular, we propose to modify the update step
for y in the Chambolle-Pook method as follows:
k+1 r² - 7/ (VG(x K T
h+1 k - (OF (y k+1 K kakt1) 1y (K yt VG(x+t1))
getl
y g++ + 0ly - )t)
This is new method, which we call APDA (formalized as Algorithm D
We would need to assume F' to be smooth to ensure that F* is strongly convex. However, we do not want to do this as this is not satisfied in many scenarios, in particular, in our key application to federated learning.

---

4.2
APDA converges linearly
Our first result shows that APDA indeed converges linearly, without the need for F" to be strongly convex.
Theorem 1 (Convergence of APDA; informal). Let Assumptions suitable selection of stepsizes, APDA (Algorithm [7) solves problem
and hold. Then, with a
m
{
La Laz
1 log
max
(V
(14)
Pz
Pay
1zg
8
iterations.
The formal statement and proof can be found the appendix (see Theorem
7
5 Accelerated Primal-Dual Algorithm with Inexact Prox (Algorithm 2
The key disadvantage of APDA is that it requires the evaluations of the proximity operator of G, which can be very expensive in some applications. To remedy the situation, we first notice that Line 3 of APDA can be equivalently written in the form
A++1
arg
min zERds
(x) def G(x) +
21h -| - -1- -a g ||
(15)
that is, this step involves the evaluation of the prox of G. The key idea of this section to replace this by inexact prox computation via suitably selected iterative method M (this is the method performing the inner iterations in T.. This leads to our next method: APDA with Inexact Prox (Algorithm 2)
Algorithm 2 APDA with Inexact Prox
1: Input: Initial point (z. .y) E Rd x RR,,," 5 = yy; Step sizes 112 Fg Byy > 0, 0 E [0, 1]; # inner iterations T
2: for k = 0. do
3: Find j as a final point of T iteration of some method M for following problem:
k arg min #cR
1 (x) def
G(z) +
1 || (x n 2t) 1??
21/
4: gtll 1² - (VG(**) + KK' TT
5:
gb+1 E nh My (0 (1++1) )- K(*) ny (KT +G(*))
6: g++1 + + 1 (yt+1 y*)
7:
end for
5.1 Gradient methods for finding stationary point of convex functions
key feature of Algorithm 2 is its reliance on a subroutine M for an inexact evaluation of the prox of G via solving the auxiliary problem (15). Our theory requires the method M to be able to output, after T iterations, point &* such that
(
[ T
5
(16)
where a 2 In other words, we require reduction of the squared norm of the gradient with fast sublinear rate. In the next lemma, we present three examples of such methods.
Lemma 1. Let Rdd= R be an L-smooth convex function, and let w* be minimizer of V. Then there exists gradient- based method M which after T iterations outputs a point w satisfying
AL w1
IV
(17)
To
for all starting points d E Rddz and some universal constant > O. In particular,
7

---

(i) if M. is GD, then vV(w))12 v 41² Ii00 w
(ii if M is a combination of Fast GD Nesterov 2004 and GD, then \V((w)) <
641.||u 1 =
1
(in) M is a combination then (V
10 of Fast GD
Nesterov 2004 and FSFOM Kimm and Fessler 2021
ww='"ll 256L
7
Let wht = arg min T (w). Since T is (Ig + th -mmooth, Lemma implies that 7 iterations weRda of a method M satisfying (17) applied to the auxiliary problem (13) with starting point w" x² yield point w" = for which
|/ A (vE= + L1x) 1| wt
A Tr I=r 11+ w0
(18)
To
TTT
5.2 APDA with Inexact Prox converges linearly
Now we can provide the main theorem with the total complexity of gradient computation VG and proximity operator computation OF*
hold. Then there exist parameters of Algorithm 2 such that the total # of evaluations of prox F and the total number evaluations of the gradient of VG find an solution of problem 7 are
Theorem 2.
Let Assumptions) !
2
3
L. Luy
L
Le
Lay Hay
Lu L2g Me Mlyy
max
(V
He Pry
play
log
&
0 max
log
(19)
respectively. In particular.
(i) the inner method M is GD, then the total number of VG computations is equal to
La Lay.
Lg L2
O
maax
log
(20)
Per Pay
(ii) if the inner method M is combination of Fast GD and GD, then the total number of VG computations is equal
Lix
Lay
La
2
maxx
log
(21)
Pay
Pzz Pay
(iii) if the inner method M is combination of Fast GD and FSFOM, then the total number of VG computations is equal to
Lx
Lay
2 La
max
log
(22)
Mx
Pay
Me
play
The proof relies on several lemmas; their statements and the proof of the theorem can be found the appendix.
Note that our way of performing inexact computation of prox of G allows us to keep the same complexity as APDA (Algorithm T in terms of the number of evaluations of the prox of F*. When
"The first half of the iterations is solved via the Fast Gradient Descent (FGD) method of Nesterov 2004 the second half via Gradient Descent (GD).
Whee first half of the iterations is solved via the Fast Gradient Descent (FGD) method of Nesterov and the second half via the fixed-stey step first-order method (FSFOM) of Kim and Fessler 2021
2004

---

M is chosen be Gradient Decent (a = 2), the number of computations of the gradient of VG, given by (20), is larger than the number of computations of the prox of G for APDA. Fortunately, we can reduce this GD is replaced with faster method. For example, if choose M be simple combination of Fast GD (FGD) and GD, in which case a 3. Theorem 2 says that the number of computations of the gradient of VG is can be reduced to (2T) (this choice is mentioned in the second-to-last row of Table 2) A further reduction is possible if we instead employ combination of FSFOM and Fast GD; see and the last row of Taable 2
Accelerated Primal Dual Algorithm with Inexact Prox and Accelerated Gossip (Algorithm 5)
In this section, we consider the most significant applications Algorithm 2 decentralized optimiza- tion over a network g = (V,E), and federated learning. In particular, we consider the finite-sum optimization problem
min WER
f((x)
(see (5) interpreted as follows: n = =V] is the number of clients/agents in the network. Communica- tion can only happen between clients connected by edge. The prevalent paradigm in federated learning, where a single server orchestrates communication in rounds, arises as a special case of this with G being the fully connected network.
If W is the Laplaciar |I of graph G, and let W W X Idn. Then problem ( can be rewritten in following equivalent way:
min P(x) = min P(x) + (VWW)) XERdn
(23)
W
>x -i fi(z;) and (xx) 0 iff x = 0, and (xx) to0 otherwise. Problem (23 is a special case of (T). By dualizing the nonsmooth (but proper, closed and
where x = [x] 2. ).
P(x)
convex) penalty, we get the equivalent saddle point formulation
(P(x)+ + (y, (y, (y))
min P(x)
min max xgR yERen
(24)
vxx=0
As see, this problem 24 is the particular case of the problem It means that solve it by Algorithm 2 for example. Moreover, we do not have to compute the prox of g) due to the fact that 2i* (-) 0, because (b(-) is the indicator function of {0}. We thus arrive at the final formulation
(P(x) + (y, [W
min max
(25)
xER yeRdn
6.1 Application of Algorithm 2 to (25)
Before providing the complexity results related the application of Algorithm 2 to problem (5)). note that Lyn />max and pay
V X (W) and define
Amax (W)
X
(26)
min (W)
According to Theorem 2 the total number of evaluations of the prox of v* i.e., the communication complexity, and the total number of evaluations of VP, i.c., computation complexity, are
#comm ō (max (VEX, x)), icomp Ō (max
2a
X, virx))
(27)
respectively. For example, in centralized case, when G is the complete graph (x 1) and M is chosen be GD (a 2), obtain the same complexities ProxSkip (Mishchenko al. 2022
#comm δ (VR).
#comp Ô (k).
(28)
In fact, it is enough for W/ to satisfy the less restrictive Assumption 6

---

However, this be improved by using either FGD + GD (a = 3) or FGD + FSFOM (a = 4) in place of M, the number communication rounds will be the same in the case of ProxSkip (or Algorithm ussed with .M GD). However, the total number of gradient computations gets improved to fcomp = O ( in the first case, and to #comp
elaborate subroutine M. If instead of GD
Ö k
in the second case.
6.2 Improvement on Algorithm 2 via accelerated gossip
Compared to the ProxSkip computation complexity Ö ( (Vxx), in the general decentralized case (i.e., > 1), complexity (27) of our Algorithm is worse if K I X. To tackle this problem, we propose to enhance Algorithm using the accelerated gossip technique [Scaman et al. 2017]. Based on this approach, we propose one more (and final) method: Algorithm 5 For this method, we prove the following result.
Theorem Let Assumptions 7 Z hold for function P. Then there exist parameters of Algorithm 5
such that in order find e-solution of problem 77) the total number of communications and the total number of gradient computations can be bounded by
#comm Ô (Vrx),
ccomp = Ô (N
2+a 20
(29)
respectively. In particular, if the inner method M is
(i) GD,, then the number of local steps is equal Ö (x-/2) and the total number of gradient computations is equal to Ö (x);
(ii) FGD GD, then the number of local steps is equal to Ö (1)+5) and the total number of gradient computations is equal to Ö (k=)0);
(iii) FGD FSFOM, then the number of local steps is equal to Ô (154t) and the total number of gradient computations is equal to (k²)
The communication complexities obtained this way are substantially better than those of decentralized ProxSkipp see Table and the commentary the next subsection.
Recall that in Table 2 we already compared Prox and our Algorithm 2 in the centralized case. In Table 3 we add to this comparison in the decentralized case, and include our Algorithm 5 as well. In particular, in Table we compare the complexity results of our methods (Algorithms 2 and 5) for solving the decentralized optimization problem (5)
selected benchmarks: D-SGD Koloskoval
et al. 2020 and ProxSkip [Mishchenko et al. 2022
First, observe that ProxSkip has vastly superior communication complexity to D-SGD, both in the centralized case (i.e., for fully-connected network; x = 1), where the improvement is from ((k) to Ö(vR) and the decentralized case (x > 1), where the improvement is from Ō(xx) to ((vx)).
In the decentralized case, both methods match the Ö communication complexity of ProxSkip. However, Algorithm 2 does so only when /FX 2 (i.e., when k > X). On the other hand, both our methods have improved bound on the number of local gradient computations, depending on what subroutine M they employ. The improvement from ((vR) to (VR) (when M FGD + GD) to Ö (VR) (when M FGD + FSFOM).
Acknowledgments and Disclosure of Funding
The work of all authors was supported by the KAUST Baseline Research Grant awarded to P. Richtárik. The work of Sadiev was supported by the Visiting Student Research Program (VSRP) at KAUST. The work of A. Sadiev was also partially supported by grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D730321 1 P5Q0002 and the agreement with the Ivannikov Institute for System Programming of the Russian Academy of Sciences dated November 2, 2021 No. 70-2021-000 1001422..
10

---

References
D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-effici SGD) via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pages 1709-1720, 2017.
D. Alistarh, T. Hoefler, M. Johansson, S. Khirirat, N. Konstantinov, and C. Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, 2018.
A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40011:120-145, 20-145, 2011.
L. Condat, K. Yi, and P. Richtárik. EF-BV: A unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization. arXiv preprint wrXiv:2205.04/10 08000, 2022.
I. Fatkhullin, I. Sokolov, E. Gorbunov, Z. Li, and P. Richtárik. Ef21 with bells & whistles: practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:21 2021.
E. Gorbunov, F. Hanzely, and P. Richtárik. Local SGD: unified theory and new efficient methods. In The 34th Conference on Neural Information Processing Systems (NeurIPS), 2020a.
E. Gorbunov, F. Hanzely, and P. Richtárik. A unified theory of sgd: Variance reduction, sampling, quantization and coordinate descent. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020b.
E. Gorbunov, D. Kovalev, D. Makarenko, and P. Richtárik. Linearly converging error compensated SGD. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020), 2020c.
E. Gorbunov, K. Burlachenko. Z. Li, and P. Richtárik. MARINA: Faster non-convex distributed learning with compression. In 38th International Conference on Machine Learning, 2021.
F. Haddadpour and M. Mahdavi. On the convergence of local descent methods infederated learning. arXiv preprint 1XX1:19900.14225 2019.
Hanzely, K. Mishchenko, and P. Richtárik. SEGA: variance reduction via gradient sketching. In Advances in Neural Information Processing Systems 31, pages 2082-2093, 2018.
S. Horváth and P. Richtárik. A better alternative to error feedback for communication- -fffeiiinn distributed learning. In 9th International Conference on Learning Representations (ICLR), 2021.
Horváth, C.-Y. Y. Ho, L'udovít Horváth, N. Sahu, M. Canini, and P. Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv: 10988, 2019a.
S. Horváth, D. Kovalev, K. Mishchenko, S. Stich, and P. Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint 0rXiv:1904.05/13 2019b.
Horváth, M. Sanjabi, L. Xiao, P. Richtárik, and M. Rabbat. FedShuffle: Recipes for better use of local work in federated learning. arXiv preprint WxXiv:2204133166 2022.
R. Islamov, X. Qian, and P. Richtárik. Distributed second order methods with fast rates and com- pressed communication. In International Conference on Machine Learning, 2021.
R. Islamov, X. Qian, S. Hanzely, M. Safaryan, and P. Richtárik. Distributed Newton-type methods with communication compression and bernoulli aggregation. arXiv preprint arXiv:2206.033: 2022.
Kairouz, H. McMahan, B. Avent, Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings. R. G. D'Oliveira, H. Eichner, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning, arXiv preprint arXiv 1wt.:ii:i1........ 1912.04977 2019.

---

S. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. In The 27th International Conference on Machine Learning (ICML), 2020.
A. Khaled, K. Mishchenko, and P. Richtárik. First analysis of local GD on heterogeneous data. In NeurIPS Workshop on Federated Learning for Data Privacy and Confidentialityy pages 1-11, 2019a.
A. Khaled, K. Mishchenko, and P. Richtárik. Better communication complexity for local SGD, In NeurIPS Workshop on Federated Learning for Data Privacy and Confidentialityy pages 1-11, 2019b.
A. Khaled, K. Mishchenko, and P. Richtárik. Tighter theory for local SGD identical and het- erogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
D. Kim and J. A. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of Optimization Theory and Applications (JOTA), 188(1): 192-219, 2021.
A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference Machine Learning (ICML), pages 5381-5393. PMLR, 2020.
J. Konečny, H. B. McMahan, D. Ramage, and P. Richtárik. Federated optimization: distributed machine learning for on-device intelligence. arXiv:1610.02527, 2016a.
J. Konečný, H. B. McMahan, F. Yu, P. Richtárik, A. T. Suresh, and D. Bacon. Federated learning: strategies for improving communication efficiency, In NIPS Private Multi-Party Machine Learning Workshop, 2016b.
D. Kovalev, A. Salim, and P. Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33: 19342-18355 2020.
D. Kovalev, A. Gasnikov, and P. Richtárik. Accelerated primal-dua gradient method for smooth and convex-concave saddle-point problems with bilinear coupling. arXiv preprint arXiv:2 12..1999,, 202
D. Kovalev, A. Koloskova, M. Jaggi, P. Richtárik, and S. Stich, A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In The 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021), 2021b.
T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization for heterogeneous networks. In Proceedings of the 1st Adaptive Multitask Learning Workshop, 2019a.
Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50 -00 2020a. doi: 10. 10.1109/MSP.2020. 2975749.
X. Li, W. Yang, S. Wang, and 2. Zhang, Communication--fficeenn local decentralized SGD methods. arXiv preprint arXiv: 1910.0916,, 2019b.
X. Li, K. Huang, W. Yang, S. Wang, and Z.. Zhang. On the conver-gence of FedAvg on non-IID data. In International Conference on Learning Representations (ICLR), 2020b.
Z. Li, D. Kovalev, X. Qian, and P. Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, 2020c.
C. Ma, J. Konečný, M. Jaggi, V. Smith, M. I. Jordan, P. Richtárik, and M. Takáč. Distributed optimization with arbitrary local solvers. Optimization Methods and Software 32(4):813-845 2017.
12

---

G. Malinovsky, D. Kovalev, E. Gasanov, I.. Condat, and P. Richtárik. From local SGD to local fixed point methods for federated learning. In International Conference on Machine Learning (ICML), 2020.
G. Malinovsky, K. Mishchenko, and P. Richtárik. Server-side stepsizes and sampling without replacement provably help in federated optimization. arXiv preprint arXiv:2201. 2021.
O. L. Mangasarian. Parallel gradient distribution in unconstrained optimization. SIAM Journal on Control and Optimization, 33(6):116-1125,, 1995.
B. McMahan, Moore, D. Ramage, and B. Agüera y Arcas. Federated learning of deep networks using model averaging. arXiv preprint 1o2.::162.00569, 2016.
H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Proceedings of the 20th Interna- tional Conference Artificial Intelligence and Statistics (AISTATS), 2017.
K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 092699990999....... 2019.
K. Mishchenko, F. Hanzely, and P. Richtárik. 99% worker-master communication distributed optimization is not needed. In Proceedings of the 36th Conference Uncertainty in Artificial Intelligence (UAI), volume 124, pages 979-988, 2020.
K. Mishchenko, A. Khaled, and P. Richtárik. Proximal and federated random reshuffling, arXiv preprint arXiv:2102.06704, 2021a.
K. Mishchenko, D. Kovalev, B. Wang, and P. Richtárík. Intsgd: Floatless compression of stochastic gradients. preprint, 2021b.
K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtárik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In 39th International Conference Machine Learning (ICML 2022), 2022.
P. Moritz, R. Nishihara, I. Stoica, and M. I. Jordan. SparkNet: International Conference on Learning Representations (ICLR), 2016.
Training deep networks in Spark, In
Y. Nesterov. Introductory lectures on convex optimization: a basic course (Applied Optimization). Kluwer Academic Publishers, 2004.
R. Pathak and M. J. Wainwright. FedSplit: An algorithmic framework for fast federated optimization. arXiv preprint arXiv:2005.0 05238, 2020.
C. Philippenko and A. Dieuleveut, Bidircctional compression in heterogeneous settings for distributed federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006. /4591, 2020.
D. Povey, X. Zhang, and S. Khudanpur. Parallel training of DNNs with natural gradient and parameter averaging. In ICLR 2015 Workshop (arXiv preprint arXiv:1410.7455) 2014.
X. Qian, P. Richtárik, and T. Zhang. Error compensated distributed SGD can be accelerated. arXiv preprint arXiv:2010.00091, 2020.
X. Qian, R. Islamov, M. Safaryan, and P. Richtárik. Basis matters: better communication-effcceentt second order methods for federated learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
P. Richtárik, I. Sokolov, and I. Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems 34, 2021.
P. Richtárik, I. Sokolov, I. Fatkhullin, E. Gasanov, Z. Li, and E. Gorbunov. 3pc: Three point com- pressors for communication-effiieee distributed training and better theory for lazy aggregation. arXiv preprint
2022.
13

---

R. T.. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898, 1976.
M. Safaryan, F. Hanzely, and P. Richtárik. Smoothness matrices beat smoothness constants: bet- ter communication compression techniques for distributed optimization. In ICLR Workshop: Distributed and Private Machine Learning, 2021.
M. Safaryan, R. Islamov, X. Qian, and Richtárik. FedNL: Making Newton-type methods applicable to federated learning. In Internatioanl Conference on Machine Learning. 2022.
K. Scaman, Bach, Bubeck, Y. T. Lee, and L. Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Learning (ICML), pages 3027-3036. PMLR, 2017.
E. Shulgin and P. Richtárik. Shifted compression framework: Generalizations and improvements. In OPT2021: 13th Anmual Workshop on Optimization for Machine Learning, 2021.
S. U. Stich. Local SGD converges fast and communicates little. International Conference on Learning Representations (ICLR), 2020.
S. U. Stich and P. Karimireddy. The frror-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint S.K.v::99090033500 2019.
S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, 2018.
R. Szlendak, A. Tyurin, and P. Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. In 10th International Conference on Learning Representations, 2022.
H. Tang, C. Yu, X. Lian, T. Zhang, and J. Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6155-6165, Long Beach, California, USA, 09-15 Jun 2019, PMLR. URL http://proceediinn/
mlr, wttppp/e/ess/sssl..... html
A. Tyurin and P. Richtárik. Distributed nonconvex optimization with communication compression, optimal oracle complexity, and no client synchronization. arXiv preprini arXiv:2202.012268 2022.
T. Vogels, S. P. Karimireddy, and M. Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Newral Information Processing Systems, 2019.
B. Wang, M. Safaryan, and P. Richtárik. Smoothness quantiiiaat techniques. arXiv preprint arXiv:2106.03524 2021a
H. Wang, S. Sievert, Z. Charles, D. Papailiopoulos, and S. Wright. Atomo: Communication-effcieent learning via atomic sparsification. arXiv preprint /rXivv:8006 (00.000000000000 2018
J. Wang and G. Joshi. Cooperative SGD: A unified framework for the design andanalysis of local- update SGD algorithms. Journal of Machine Learning Research (JMLR), 21:1-50, 2021.
J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, B. A. y Arcas, M. Al-Shedivat, G. An- drew, S. Avestimehr, K. Daly, D. Data, S. Diggavi, H. Eichner, A. Gadhikar, Z. Garrett, A. M. Girgis, F. Hanzely, A. Hard, C. He, S. Horvath, Z. Huo, A. Ingerman, M. Jaggi, T. Javidi, P. Kairouz, S. Kale, S. P. Karimireddy, J. Konečný. S. Koyejo, T. Li, L. Liu, M. Mohri, H. Qi, S. J. Reddi, P. Richtárik, K. Singhal, V. Smith, M. Soltanolkotabi. W. Song, A. T. Suresh, S. U. Stich, A. Talwalkar, H. Wang, B. Woodworth, S. Wu, F. X. Yu, H. Yuan, M. Zaheer, M. Zhang, T. Zhang, C. Zheng, C. Zhu, and W. Zhu. A field guide to federated optimization. arXiv preprini 1rXiv:2107.06917. 2021b.
Wangni, J. Wang, J. Liu, and T. Zhang. Gradient sparsification for communication-effiiient distributed optimization. arXiv preprint arXiv:1710.0985. 2017.
14

---

B. Woodworth, K. K. Patel, S. U. Stich, Z. Dai, B. Bullins, H. B. McMahan, O. Shamir, and N. Srebro. Is local SGD hetter than minibatch SGD? arXiv preprint arXiv:2002.07833) 2020.
H. Xu, C.-Y. Ho, A. M. Abdelmoniem, A. Dutta, E. H. Bergou, K. Karatsenidis, M. Canini, and P. Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, KAUST, 2020.
G. Zhang, Y. Wang, L. Lessard, and R. B. Grosse. Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 7659-7679. PMLR, 2022.
C. Zhu, S. Han, H. Mao, and W. J. Dally. Trained ternary quantization. In ICLR, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We crearly state all theorem
(b) Did you describe the limitations of your work? [Yes] Assumptions are our limitations.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work mainly theoretical, with no foreseeable negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 1.2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "XNHQprVrpe", "reviewer": "Reviewer_qFrD", "summary": "This paper presents three algorithms for finding approximate solutions of a strongly convex composition optimization problem with objective function $G(x) + F(Kx)$ for linear operator $K$. More specifically, each algorithm is based on the classic Chambolle-Pock primal-dual algorithm under different assumptions on the problem of interest. Specifically, the first one deals with the case where the resolvents of $F$ and $G$ are both simple, the second one is for the case where only the resolvent of $F$ is simple, and the third deals with an extension of the second one for federated learning. In particular, the third one makes use of a known technique (accelerated gossip) in order to improve some dependencies on certain universal constants. It is then shown that some versions of the proposed algorithms improve on existing communication efficient methods, such as ProxSkip, from various theoretical angles.", "questions": "1. Assumption 4 seems to imply that $K$ has full row rank in the case of general $F$. Perhaps a comment should be made about this to the reader?\n\n2. Line 66 says that ProxSkip \"solves\" (1), which normally means that an *exact* solution is found. Since the tolerance $\\varepsilon$ is considered in this work, the authors should change this to mean \"inexactly solves\" (1) and precisely define what an $\\varepsilon$-inexact solution is.\n\n3. Line 71 references the number of prox evaluations wrt $F$, but the algorithms use the prox of $F^*$. While these are equivalent, a remark should be made about this with appropriate references, e.g., using the Moreau Decomposition Theorem.\n\n4. Theorem 2 should be slightly more self-contained. Specifically, both $\\alpha$ and $\\cal M$ should be described there so that the reader does not need to read Lemma 1 or the beginning of Section 5 in order to understand these quantities.\n\n5. In line 228, the assertion of $\\psi^{*}(\\cdot)\\equiv 0$ for every indicator function $\\psi(\\cdot)$ is false. For a closed convex set $S$, the conjugate of the indicator function of $S$ is called the support function of $S$, which is generally not the zero function. It just so happens to be the case that when $S=${$0$}, the support function is also identically zero.\n\n6. The replacement of $\\in$ with $=$ mentioned in lines 129-130 is confusing in this paper, as the notation $=$ in algorithms is typically interpreted as assignment. I would prefer (at least in Algorithms 1-3) that $=$ be replaced with $\\in$ and appropriate adjustments, e.g., $x = A(x)$ becomes ${\\bf \\rm find\\ } x \\in A(x)$. \n\n7. Some small typos:\n* line 59: The part \"Letting $d_x=$...$ is a sentence fragment. \n* line 78: oder -> order", "limitations": "The authors have sufficiently addressed the possible limitations (assumptions) of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Disclaimer**: I have not read the appendices of this work and, hence, I am limiting my review to the 9-page main body of this work.\n\n*Strengths*: \n\n1. The improved complexity bounds are novel and significant. I especially like the connections of the techniques to existing literature.\n\n2. The literature review and comparisons in Table 1-2 are much appreciated. This gives clarity to how it fit into other state-of-art methods.\n\n3.  The overall presentation of the material is well-organized and easy to read. I especially like the summary in Section 2 and the review in Section 3. The writing style is clean and there are very few grammatical issues.\n\n*(Minor) Weaknesses*:\n\n1. Some parts of the technical results lack clarity or require further discussion and elaboration (see the *Questions* section below).\n\n2. There are a few minor technical mistakes (see the *Questions* section below).\n\nAs the strengths of this paper greatly outweigh its few minor weaknesses, I recommend its acceptance to NeurIPS, under the mild condition that the simple comments in the  *Questions* section below are sufficiently addressed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VlHNVVqcvRX", "reviewer": "Reviewer_EGED", "summary": "\nThis paper aims to develop a similar method as ProxSkip, but based on PDHG instead. The proposed algorithm allows inexact $Prox_G$, as well as the non-strongly convexity of $F$. ", "questions": "\nPlease see above.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n\n1. The theory for inexact evaluation of prox of G at each iteration is nice. The possible difficulty in $Prox_G$ is often an overlooked factor.\n2. The avoidance of the strong convexity of $F$ is also novel. This makes the convergence proof non-trivial.\n\nMajor concerns:\n\n1. My first concern is on Assumption 4, where a constant $\\mu_{xy}$ is defined. Although it is from another work, the validity of this assumption should still be discussed in detail. \n\nFor example, why is this assumption reasonable? What specific problems satisfy this assumption? It would be much better if some examples of $K$ and $F$ arising from real-world applications can be provided.\n\nHow small can  $\\mu_{xy}$ be? It appears in the denominator of the complexities. Although it is a constant, it would be better if we know its magnitude.\n\n2. There are no numerical comparisons with other methods, especially ProxSkip. The claimed superiority in gradient complexities should be accompanied by numerical evidence. \n\nMinor concerns:\n\n1. In Assumption 4, the paper you cited uses $\\mu^2_{xy}$ instead of $\\mu_{xy}$, should it be  $\\mu^2_{xy}$?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QgHrJ76OP0D", "reviewer": "Reviewer_zYvm", "summary": "Authors develop a new method for the problem G(x) + F(Kx), with G being strongly convex and smooth, F being convex and K being a matrix. Via a saddle point reformulation and accelerated minmax algorithms, they improve upon previous approaches and can remove some assumptions. They apply their framework to federated learning and improve on the number of local steps that are required between communication rounds.\n", "questions": "This work shows that one does not need the smoothness condition on F* if one has a prox access to F*. In L107 it is said that this is important for some applications (it also talks about \\mu_x strongly convex, but that was an issue that was also addressed in previous work). My question is, what are some applications that do not require F* to be smooth. In the federated learning application, after the saddle point reformulation F* is 0, so this does not apply. Authors should provide such an example and reference it in L107\n", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general I am positive about this work. The paper obtains some improvements on solutions for problem (1) and also to federated learning, as a consequence of their framework plus some modifications. The paper is written in a self contained way that allows to follow the analysis well. But on the other hand this paper needs to state and cite clearly the theoretical analyses and ideas that are taken from previous works. It is hard to pinpoint the new ideas this paper introduces and I think the paper does not do a good job on explaining these. Everything is re-proved (which is not a bad thing per se) but without clear indications of what was already done and what is new, see below for examples, but for instance the results of lemma 1 were known and there is no direct reference to these, only to the subalgorithms that are used.\n\nLet me elaborate on my interpretation of the work and how many of these ideas could be better attributed:\n    \nThis method solves problem (1) by combining the structure of the accelerated algorithm in (Kovalev, Gasnikov, Richtárik 2021) and the method in (Chambolle, Pock, 2011) but substituting the gradient update step with a subgradient of F* by an approximate implicit step. The former work already considered a problem with the structure (1) among its applications and the optimization of the saddle point problem and how this applies to distributed setting. Such work already had the techniques to accelerate with linear rates when F* is not strongly convex, provided that the matrix K satisfies some regularity conditions, as it is assumed in this work as well. This *is* mentioned in the main paper.\n\nIn accelerated algorithms of this kind, it is known how to obtain a similar accelerated algorithm by means of computing an approximate proximal operator, which intuitively means that one substitutes an explicit (sub)gradient step that occurs in the algorithm by a sufficiently precise aproximate implicit step. Indeed, an inexact implicit step of this exact kind has been used previously for general convex smooth optimization in \"Adaptive Catalyst for Smooth Convex Optimization, Ivanova et al\" (effectively allowing a Catalyst-like reduction without incurring an extra logarithmic factor, as it happened with the original Catalyst paper) and has been improved in several works like in \"Contracting proximal methods for smooth convex optimization\" by allowing constrained problems, among other works. All these works require a subroutine to minimize the norm of the gradient of a function coming from the objective of the proximal subroutine. There is no comment on this. Also, L461 \"the result is not new of course, but we could not find a source for the proof we include here\". Citations to the closest works should be provided\n\nThe problem of minimizing gradient norm for solving the subroutine for a smooth and convex function is already known. Also, explaining all the possible different suboptimal variants seems redundant to me.\n\nThe accelerated gossip is already known as well. And how to apply it to this setting was already studied in (Kovalev et al 2020)\n\nSo one wonders what is left. There is certainly some value in having put together all of these things, and on combining the techniques of (Kovalev et al 2021) with Chambolle Pock. But it is hard to pinpoint any other contribution beyond this (and the work certainly does not explain this clearly) except for maybe not assuming that F* is smooth, although forgoing this assumption seems to come simply from the fact that one assumes access to the exact prox of F*.\n\nI can see how the writing of this paper can make many people that are not so familiar with the related literature wonder what is the contribution of this work and what were already known things. \n    \nThese are concrete things that I think would help to make the presentation more \n+ There should be more citations about where to find the original analyses of several things that are re-proven, like the closest approximation to the results in section B\n+ state clearly which parts of the analysis of Chambolle-Pock in appendix C are re-proven in that \n+ it would be nice to have a comparison of appendix D with (Kovalev et al, \n+ sections E and F seem fine to \n+ Then again appendix G needs to state clearly that all these methods were known and provide references for all, only Kim and Fessler is being cited and it seems it is only cited when the paper refers to FSFOM, but Kim and Fessler 2021 also had essentially the same final result, like in (29) of the arxiv version of their paper.\n    \nI don't think the reduction in font size in the tables is allowed, according to the NeurIPS style guidelines: \"do not change font sizes (except perhaps in the References section; see below)\". It only happens in some (extensive) footnotes for the tables, but strictly speaking this can be an argument for desk rejection.\n\nMinor:\n\nL72 \"for the number gradient steps\" missing 'of'.\nL171 \"Step 3\" it would be better if you write \"Line 3\" (since line 1 is not a step) and even better if you use \\ref by having a label in that line in the algorithm\nL208 \"Gradient Decent\"\nfootnote in page 8 \"Assumtion\". Also, the sentence should be rephrased, as it does not make a lot of sense, as is.\nL131 \"in line 8\" The pseudocode of Algorithm does not have numbers. Please add them\nL478 the text assumes that F^\\star is convex but it should say it is \\mu_y strongly convex\nL607 \"be a exact solution\" -> \"be an exact solution\"\nL677 Fix sentence \"The main idea of the proof is this methods is to show two following things\"\nL689 typo \"requared\"\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Msr898Goqpa", "reviewer": "Reviewer_bWvi", "summary": "The paper considers convex-concave saddle-point problems. The proposed methods are a combination of multiple techniques such as inexact proximal evaluation and acceleration. In particular, the method builds heavily on Chambolle-Pock splitting with the scheme studied in [Kovalev et. al, 2021].", "questions": "Since this is a theory paper, I would expect more elaborated statements in the main results. For example, many specific constants in the complexity formulas are ignored. It is important to explicitly provide the parameters required to achieve the rate in the theorems. For example, what is \"a suitable selection of stepsizes\" in Theorem 1 and \"there exist parameters of Algorithm 2...\" in Theorem 2? Do they depend on unknown parameters? While the linear rate is nice theoretically, it can be much slower than sublinear rates if the convergence factor is close to 1, unless the number of iterations tends to infinity. All these parameters are important for practitioners to implement the methods.\n\nThe author mentioned in Line 107 that relaxing the convexity condition on $F^\\star$ is important in some applications. Can the authors specify some of such applications in which convexity of $F^\\star$ is critical but not strong convexity?\n\nInstead of Chambolle-Pock splitting, one can also use Douglas-Rachford splitting for such a structured problem. How would we compare the two in the current paper's setting?\n\nAny recommendation on how to efficiently implement the proposed methods?", "limitations": "see above", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main contribution is the relaxation of the strong convexity and smoothness assumptions on the conjugate function $F^\\star$. The first relaxation has been achieved in several previous works such as [Kovalev et. al, 2021] and [Du and Hu, 2019]. The contribution of allowing inexactness in the proximal evaluation is quite incremental as such a feature is abundant in proximal-type methods.\n\nIt should also be emphasized that to relax such assumptions on $F$ (in the function $F(Kx)$), the paper requires an extra assumption on the linear map $K$ [Assumption 4]. So it is not quite clear if moving a more restricted assumption from $F$ to $K$ is such a large gain. This deserves more clarification in the paper.\n\n\nReferences:\n----------\n\n[1] Du, S. S. and Hu, W. Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity. AISTATS, 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept