Optimal Gradient Sliding and its Application to Optimal Distributed Optimization Under Similarity
Authors: Dmitry Kovalev
Aleksandr Beznosikov
Ekaterina Dmitrievna Borodich
Alexander Gasnikov
Gesualdo Scutari
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
composite optimization
data similarity
optimal algorithms
sliding

Abstract: We study structured convex  optimization problems, with additive objective   $r:=p + q$, where $r$ is ($\mu$-strongly) convex, $q$ is $L_q$-smooth and convex, and $p$ is $L_p$-smooth, possibly nonconvex. For such a class of problems, we proposed an inexact accelerated gradient sliding method that can skip the gradient computation for one of these   components while still achieving optimal   complexity of gradient calls of $p$ and $q$, that is, $\mathcal{O}(\sqrt{L_p/\mu})$ and $\mathcal{O}(\sqrt{L_q/\mu})$, respectively. This result is much sharper than the classic black-box  complexity $\mathcal{O}(\sqrt{(L_p+L_q)/\mu})$,   especially when  the difference between $L_p$ and $L_q$ is large. We then apply the proposed method to solve distributed optimization problems over master-worker architectures, under agents' function similarity, due to statistical data similarity or otherwise. The distributed algorithm achieves for the first time lower complexity bounds on both communication and local  gradient calls, with the former having being a long-standing open problem. Finally the method is extended to distributed saddle-problems (under function similarity) by means of solving a class of variational inequalities, achieving lower communication and computation complexity bounds.

Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity
Dmitry Kovalev KAUST, Saudi Arabia dakovalevv@gmail. com
Aleksandr Beznosikov
MIPTÍ HSE University and Yandex, Russia
anbeznosikov@gmiil.com
Ekaterina Borodich MIPT and HSE University, Russia borodich. edw..ysehhddpyyyeeh.......
Alexander Gasnikov
MIPT, HSE University and IITP RAS; Russia
gasnikov@yandex.rg
Gesualdo Scutari
Purdue University, USA
gscutari @purdue ascutarippurdue..
edu
Abstract
We study structured convex optimization problems, with additive objective p + q. where r is (u-strongly) convex, is Lm-sth and convex, and is Lp- smooth, possibly nonconvex. For such a class of problems, we proposed inexact accelerated gradient sliding method that can skip the gradient computation for one of these components while still achieving optimal complexity of gradient calls of p and that is, P(VLp/ p)) and ((VLg/H) /)), respectively. This result is much sharper than the classic black-box complexity ( ((., + I.g)/p), especially when the difference between I.p and Lng is large. We then apply the proposed method to solve distributed optimization problems over master-words worker architectures, under agents' function similarity, due to statistical data similarity otherwise. The distributed algorithm achieves for the first time lower complexity bounds on both communication and local gradient calls, with the former having being long- standing open problem. Finally the method is extended to distributed saddle- problems (under function similarity) by means of solving class of variational incqualities, achieving lower communication and computation complexity bounds.
1 Introduction
We consider structured convex programming in the form 6
13 35
min r(x) g(x) p(x);
EERd
where r is assumed to be convex and decomposed as the sum of a smooth, possibly nonconvex function and smooth convex function q. First order information of p and is accessible separately, are interested in scenarios where the cost of evaluating the gradient the two functions is not even, but computing, say Vp, is much more resource demanding than Vg. The motivating application for this scenario is distributed optimization over master master-worker systems, as discussed next.
"King Abdullah University of Science and Technology
Moscow Institute of Physics and Technology Institute for Information Transmission Problems RAS
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Consider the following distributed optimization problem over a network of n agents:
1 zER T1 Σ f(()),
min
r(x)
where fü is the loss function of agent assumed to be convex, which is not known to other agents. Agents are embedded in a star-topology, with agent being the master node, without loss of generality-this is the typical federated learning setup [24]. An instance of (2) of particular interest is the empirical risk minimization (ERM) whereby the goal is to minimize the average loss over some dataset, distributed across the nodes of the network, with being the empirical risk of agent i, the set of m samples owned by agent i, and
i... [1(x) = 1 Σド= (xx;²) where zi
(1) ;
(m))
=() measures the loss of the model x on the sample z/-
Several solutions methods have been proposed to solve 2b: the prototype approach consists in interleaving local computations at the workers sides (nodes L.... n) with communications to/from the master node (i = 1), which maintains and updates the authoritative copy of the optimization variables, producing eventually the final solution estimate. Since the cost of communications is often the bottleneck in distributed computing (e.g.. i [32] ) a lot of research has been devoted to designing distributed algorithms that communication efficient. Acceleration (in the sense of Nesterov) has been extensively investigated as a procedure to reduce the communication burden. For L-smooth and p-strongly convex functions r in ( linear convergence certified by employing first-order methods, with computation (gradient evaluations) and communication complexities proportional to VK (xx - T./p is the condition number of r). For ill-conditioned functions (I very large), the polynomial dependence on may be unsatisfactory. This is, e.g., the typical setting of many ERM problems wherein the optimal regularization parameter for test predictive performance is very small.
Further improvements the communication complexity be obtained exploiting the extra structure typical in ERM problems, also known as function similarity (see, e.g., 4 51 44 48)): ): f()))
f' S 8, for all x in a proper domain of interest and all i * j 1, ..... where 8 >> 0 measures
the degree of similarity between the Hessian matrices of the local losses. When data are i.i.d.
among agents. fi's reflect statistical similarities in local data, resulting in 5 = 0(1 /m) with high- probability (Ô hides log-factors and dependence on d). In this scenario, in general, 1 + 5/ppp < 4 This motivated surge of studies aiming at exploiting function similarity coupled with acceleration to boost communication efficiency (see Sec. 1.2 for an overview of relevant works): linear convergence
is certified with a number of communication steps (for nonquadratic losses) scaling with Ö /8/pu,
where Ô hides log-factors. This matches lower (communication) complexity bounds 4 it only up to log-factors. Furthermore, these methods are not computationally optimal, yielding local gradients calls larger than lower complexity bounds ((vR), In fact, Table [ shows that, to the date, there exists no distributed algorithm achieving the best of the two worlds, that is, optimal (lower bound) communication complexity and local gradient (oracle) complexity.
This paper fills this gap. Our starting point is the reformulation of 2 in the equivalent form
min r(x) ZER
fi (())
[f(x)) fi
which exploits function similarity the agents' side via preconditioning. Problem is instance of [ all fi (thus q) are convex but is nonconvex. Also, evaluating Vq and Vp has different costs; the former involves only local computations at the master node while the latter requires communications from/to master and workers nodes. At high-level the idea is then clear: one would like to design distributed algorithm for (3) [or more generally for [ that skips gradient computations of Vp (saving thus communications) without slowing down the overall optimal rate of convergence.
This naturally suggests the use of gradient- sliding techniques 1 [C, yielding algorithms that skip from time to time computation of the gradient of one function in the summand objective. However, existing gradient-sliding algorithms are not applicable to ① [and thus 3 because they all require p and q to be convex. This calls for new designs, accounting for the nonconvexity of p.
1.1 Main contributions
Our contribution is threefold:

---

A new gradient-sliding algorithm for Dr We propose a new Accelerated ExtraGradient sliding method that skips the computation of Vp from time to time. The method builds on an inexact acceleration of proximal envelop (outer-loop) coupled with a suitable termination criterion and inner-loop algorithm to approximately solve the proximal subproblem. When applied to ( with r being (μ-Strrongly) convex, q being T. smooth and convex, and being I.p -sooohhh (possibly nonconvex), the proposed algorithm achieves optimal complexity of gradient calls of and p. that is,
V4
Vp
strongly convex
O
Lg log
O
Le log
CONVEX
La 1| xx
1/ -x"1
Notice that the above complexity bounds are sharper than the complexity bound obtained by the Nesterov's optimal first-order method for smooth (strongly) convex optimization applied to (I). For instance for strongly convex r, that would yield Vg. Vp complexity scaling as O ( (hg + Lp)/u). which is less favorable than our separate complexity bounds above. To the best of our knowledge, this is the first time that such bounds are achieved for nonconvex
Optimal complexity bounds for under function similarity: We customize the proposed accelerated gradient- sliding algorithm to the distributed optimization problem 2 under ò-function similarity. As showed in Table for strongly convex (see Sec. B for the case of convex r). the new distributed algorithm achieves lower complexity bounds on both the number of communications ! and the number of gradient computations (without logarithmic factors!) +v Achieving optimal communication complexity (for nonquadratic losses) was a long-standing open problem.
Gradient sliding for variational inequalities: We extend the proposed gradient-sliding machinery to solve distributed saddle-points under similarity by means of solving a class of strongly-monotone
Variational Inequalities (VI). We improve cxisting complexity bounds for such problems [ achieving for the first time both optimal communication complexity and gradient oracle complexity sce Table
Table 1: Existing convergence results for distributed (saddle point) optimization under d-similarity,
Reference
Communication complexity
Local gradicnt complexity
Order
I Limitatiios
DAKE 344
log
oVT log" !) 12
1st
quadratic
D18CO S1
2 (v/ E (log + of OPArn)loo +
@ (log 1 + +C CRAPoeoog b
2nd
C² w-tssetffoeee self-enseoodann
AIDE 10
o (v/ 1/ log 2los b))
(V log 2 b)
1st
quadratic
DA
(# log #)
v
2372 log
23/2
1s//2od
quadmaicc Av
DANE-HE
40
[ log +)
(v log
1st/lod
quadratic My
Upper
SONATA 151
log 2)
v log"
1st
decentralized
Mininiatta
SPAC HH
0 (v E log $)
1 log"!
1st
Ad Lipsbitz bessian
DiRagIKA |M
log 1 +
V log" o A + Se Jog
2nd
L.ipshitte hessian
P
ACN
VB log 1
VV H log' " marpii
log t
2nd
-Lipshitz bession
AcCSUNATA
(Vv log Alog +)
( 7 log" Alog A) 19
1st
decentrliiedd
This poper
② (v/ [ log
( f log #
1se
Lower
f1
( log
(v 7 lox !)
non ire-distrbuuted
Upper
SYNDBA
$ lug t))
o log blog #)
1st
Soddles
This papper
$ lng t)
o # log +)
1st
Lower
X
A log 2)
log !)
noo distributed
(1) This is the worst-case complexity, as pointed the puper. the convergence of the method might better, bused upon an additional sequence G. 211: proximal local computations (exact solution of local subproblems), we filled these cells assuming that the proximal operator is computed using Acceleratdd Gradient Descent [i]] with accuracy z², from Lipschitzness of the
Hessian and strong convexity follows self coffcconcodaacc: (4) gradient complexity not provided. we derived it using (37], (9) gradient complexity not provided, derived it using [8] gradient complexity holds for nonquadratic functions;
Notation: 5 similarity parameter, Lesmooothess constant of f., P - strong convexity constant of r. E =accuracy of the
solution, Ro = - xx" AF = -(x²) r(*").
3

---

1.2 Related works
the idea of gradient-sliding for structured convex optimization such as ( has received significant attention as tool to skip gradient computations of one function in the summand; examples and generalization include first-order accelerated methods
Gradient-Sliding:
Since the seminal paper 28
128 29
31, zero-order (derivative-free) schemes [4] 22 4
high-order methods [25] 20
and slidings for saddle point problems and variational inequalities
Albeit applicable to
more general classes of optimization problems than ① (e.g., allowing either and to be nonsmooth), none of the existing methods provide guarantees when p nonconvex. The proposed algorithm fills this gap. Furthermore, it achieves optimal lower complexity bounds on the calls of Vp and Vg.
Distributed optimization under function similarity: The literature of distributed optimization is vast; given the focus of this work, we comment next solution methods exploiting function similarity via proper preconditioning-Taan solving either minimization problems or saddle-point formulations, and is commented next.
summarizes complexity results of existing distributed methods
The seminal paper 4 established lower communication complexity bounds for 2 under d-similarity; e-optimality cannot be achieve in less than D2 28 log 1/2) communication rounds. Since then, lot of effort has been devoted to design distributed schemes aiming at achieving optimal communication complexity. The authors in [2] proposed DANE, mirror-descent based algorithm whereby workers perform a local data preconditioning via a suitably chosen Bregman divergence, and the master averages the solutions of the workers. For quadratic losses, DANE achieves communication complexity ((6/p)² log 1/E); this was later improved ((68/p) log 1/e) for nonquadratic losses in where the SONATA algorithm was proposed (also implementable over mesh neehhns
Improvements achieved employing acceleration; effoors include: DiSCO [5]], inexact damped Newton method coupled with a preconditioned conjugate gradient (to compute the Newton direction),
which achieves communication complexity Ō 55//) log 1/E) for self-concordant losses (see Table
for the log-factors hidden in the Ō): AIDE 40 which uses the Catalyst framework [3), matching
the rate of DiSCO for quadratic losses; DANE HB [50]] variant of DANE equipped with Heavy Ball momentum and matching for quadratic functions the communication complexity of DiSCO and
AIDE; and SPAG [21], preconditioned direct accelerated method, achieving for nonquadradic losses asymptotically the convergence rate O(11 - /B/))² (k is the iteration index) the worst-case rate is still ((VL/u) log 1/e).
Finally, higher order methods employing preconditioning have been studied in proposed DiRegINA, a decentralization of the cubic regularization of the Newton method, where workers build Newton direction sampling local Hessians; ( introduced ACN, an inexact accelerated cubic-regularized Newton's method, with improved complexity with respect to [12] and Ad extended the Catalyst framework [3 to the distributed setting (including mesh networks), proposing Acc
46
SONATA-the communication complexity of these methods is reported in Table I
In summary, the above tour on the relevant literature shows that none of the existing methods can match lower communication complexity bounds for (non quadratic) optimization problems 2 under function similarity (all complexity bounds contain log-factors). The proposed distributed method achieves lower communication and computation complexity bounds.
2 Optimal Gradient Sliding for Minimization Problems
We study the minimization problem ① under the following blanket assumptions. Assumption 1. r(z): ddd + F. is p-strongly convex on RRd.
Assumption 2. g(x): : R + R. is convex and La-smooth on Rdd
Assumption 3. p(r): gd IR is L. -mooth on Rdd
The proposed Accelerated ExtraGradient sliding formally introduced Algorithm D Convergence of the outer loop is established in Theorem [ while Theorem 2 determines complexity of solving the inner loop up to suitable termination. Finally Theorem provides the overall complexity merging inner and outer loop results. The proof of all the theorems can be found in Appendix A.I

---

Algorithm Accelerated Extragradient
Input: x² = F
2: Parameters: (0. 11. n, n.8.a 0,K (1.
3: for = -0.122..... K
do
4: Fy TI + +)
5: If k+1 arg min (*)))) = p(ag)) + (Vp(ag), 25)) + 1| 2511² 2 + [xx)]]
6:
gk+1= = x² + na(a))
k+1 x²) 1)Vr(ztt1)
7: end for
8: Output: x²
Theorem 1. Consider Algorithm for Problem underr Assumptions
with the following tuning:
== min
1, 2 Lpp
0 2
min
1
2p
2
and let a//t1 in line satisfy
( 11 < 4 || arg min (x))
(4)
Then, for any
K max {I, V log
((xx)) r(=")
(5)
we have the following estimate for the distance to the solution x²:
||x x= 22
(6)
2.1 Solving the auxiliary subproblems
At each iteration of Algorithm D one needs solve the subproblem:
min (x) p(a+)) (Vp( ,nh)) 20 x + q(x).
According to Theorem need not be solved to arbitrary precision; inexact solutions k+1 satisfying condition suffice. Condition means that gradient norm (/) |>]| should be sufficiently small. Notice that (x) in (2Lp + smoooot and convex.
Problem can be solved up to the termination using any of the algorithms in obtain the following complexity.
We
Theorem 2 (B3 Remark 1). There exists certain algorithm such that, when applied to problem
with the starting point uyy. returns k+1 satisfying
D max Lp. Lg 11 arg min Ab(x))
(z
T
where D O is universal constant (independent of Teps Tug T etc) and T is the number of calls of q by the algorithm.
2.2 Overall complexity of the optimal gradient-sliding
Theorem suggests that, satisfy condition T of iterations of the inner algorithm as
Theorem | is sufficient to choose the number
T V3D max 1
L Lp
We can now determine the overal complexity of Algorithm 1. At each iteration of Algorithm Iwe
call Up twice (at 2 line 5 and at k+1 line 6. and Vg computed T + 1 times (I' times in the

---

auxiliary problem - line 5 and at ff .+1 line 6 find x. Rd that satisfies
Hence, to find an E-solution of problem i.e., to iterations as given in S
Algorithm
requires
2 K O
max
log )
calls of Vp(x), and
(T (T+1)
x
maxx
1,
Ly L
log
calls of Vg(x).
Putting everything together obtain the following final convergence result.
Theorem 3. Consider Problem under Assumptions ro with S Lp S Lug Then, to reach an e-solution, Algorithm requires
O
( Lag log calls of Vq(z) and O (v Lx ! calls of Vp(z). 14
This matches optimal complexity for the individual gradient calls.
We conclude this section providing convergence of variant of the proposed algorithm suitable for convex in ① (Assumption I with μ 0). The algorithm is described in Appendix A._ Here only provide the final convergence result, the analogous of Theorem
Theorem 4, Consider Problem I under Assumptions (with/ = 0 with Top S Tup Then, to find an e-solution of ①
(in objective value), Algorithm
in Appendix A.2
requires
o (V
calls of Vg(x) and o (1
calls of Vp(x).
3 Application to Distributed Optimization Under Similarity
In this section, we apply the proposed algorithm the the distributed optimization problem under the following assumptions.
Assumption 4. Each fi(x): IRd + R is convex and L-smooth.
Assumption 5. r(z): Rd + R is p-strongly convex.
Assumption f1(r),...... fn (x) are 8-related: [1V2 - S 6, for all i + j and
Rdd and some
From the last assumption it is easy to get that for all and x E Idd we have ( (v)()))))((((()) = || VV f(()) V (+)]] S
Σ / f((z) v 5.
We leverage now Algorithm to solve Q using the equivalent reformulation applied to the distributed system can be described as follows. The server computes x and sends it to all the workers (line 4h. Workers compute V f((()) and send it to the server. After collecting all V (arg), the server builds Vp(=)) vr(x f (xrt), and then solves (inexactly) the local problem A5 (line 5b. The inexact solution k+1 then broadcast to the workers, which update their own receives (ar and send back the server, which can then evaluate Vr(n (line
The algorithm
Using Assumptions and we infer that is p-strongly convex; and fi is Ly -mooth and convex, with L, = L. follows from Assumption that / < 8. Therefore, has Lp LppLisichitz gradient, with Lp = 8. This shows that we can leverage Theorems and 4 to establish convergence for strongly convex and convex as given next.
Theorem 5. Let Assumptions to be satisfied with μ < 8 S L. Then, to find E-solution of the distributed optimization problem Algorithm requires
o (V log communication rounds and O ( 1ogg local gradient computations.
Theorem Let Assumptions f 5 with ja = 0), be satisfied and L. Then, to find e-solution of the distributed optimization problem Algorithm Senttthmmrruuue requires
(VElla a*1)
communication rounds and (V x²1l) local computations.

---

Such estimates are optimal from both communications 4 and local computations point of views B7 is important remark that Algorithm T solves the local subproblem Ag with some precision, while most of existing works (see Table D assume that local problems are solved with infinite precision (column Local gradient complexity). which is not practical. Note also that the subproblems in line of Algorithm| [ do not necessarily have to be solved by deterministic algorithm as in Theorem Stochastic methods can also be used, as long as they guarantee that condition is met.
Optimal Gradient Sliding for VIs
In this section we consider the composite variational incquality [16 5 in the form:
Find x² Rd R(x=) = 0 with R(x)) := Q(z) + P(æ),
(10)
where Q(z), P(z): Rd Rd. Variational inequalities are unified umbrella for variety of problems-two examples follow.
Example [Minimization]. Consider problem choose Q(x) Vg(x) and P(x) = Vp(x).
Then the solution of the variational inequality (TO) means that we need to find the point x where the
operator R(x*) Vr(="). For the convex function r, this is equivalent to finding the minimum.
Example [Saddle point problems). Consider the convex-concave saddle point problem
min max rly. =) qyy. 2) p(y,
(11)
(v, = [V =). V vv =)] and P(a) Ply. 2) [V Vep(y,2 2), VVp(y. =)}. then it can be proved that only if x-' = (v", =²) 3) is solution for i.e
If we take (xx)
20) is solution for 410 and
r(y",)) S r(y",=") r(y,2") for all y E R2 and E Rd.
While minimization problems widely considered separately from variational inequalities, saddle point problems are often analyzed under the VI lens. In recent years the popularity of saddles has
grown, this is due the fact that they have both classical [15] and new ML [8 34] applications.
We study problem 10 under the following assumptions.
Assumption 7. R(x) is p-strongly monotone: (R(x)) R(x2), 21 x2) 2 u||2 x2 all
#2 E R²
Assumption 8. (xx) is monotone and Lgg Lipschhhtt::: (Q(x))) Qx22), 01 x2) 2 and [1Q(x1)
Q(x2)] Lg || z2ll. for all Z1, 22 Rd.
Assumption 9. P(z) Ly- Lipschit:::: [|(())) P(x2) s Lp for all æ 22 Rd
For saddle point problems these assumptions are equivalent to (strong) convexity-(strong) concavity and Lipschitzness of gradients.
4.1 Sliding via Extragradient
This algorithm is non-accelerated version of Algorithm | A similar non-accelerated sliding is used in [9. Our version however has better theoretical and practical guarantees because of the effective stopping criterion [2 Convergence of the outer loop is established in Theorem 7 Theorem establishes convergence of the inner loop up to the required termination; and finally Theorem combine the two-loop complexity. The proofs of the theorems can be found in Appendix [.I
Algorithm 2 Extragradient Sliding for VIs
1: Input: x0 E Rd
2: Parameters: n, 0, 0, 21.
2.....K 4: Find a = ã where " is solution for
3: for k == 0.
do
Find ãt E Rd (**) with ((())=P(>>)) +((x)) - (x x²
5: 1+++ = th + na(u" x²) - nn((2*)
6: end for
7: Output: ,

---

Theorem 7. Consider Algorithu for Problem tuning:
I0 under Assumptions
with the following
0 2
n min
2ps. 4pc 4hpp
Assume that uh (line satisfies
| (u=
(12)
Then, for any we have the following estimate for the distance to the solution x²:
K max {1, t log -
(13)
|| x x²112 S E.
(14)
The proof is given in Appendix B.1
4.2 Solving the auxiliary problem
As for Algorithm ! we need an auxiliary solver for the subproblem in line which ensures that (22
is met. One can observe that B (a) is (2L, + Lipp-sipc and monotone. For this type of problem, the authors in 14
proposes approach that guarantees convergence on [IB[(("))]
(u*)
Theorem 8
49
Corollary 2). There exists a certain algorithm that, applied to the subproblem [22
with starting point x", returns ut satisfying
D.. DP.max (1. L. -1
(15)
where D > O is some universal numerical constant (independent of L,p Lap T etc) and T is the number of calls of the operator Q
4.3 Complexity of the optimal gradient sliding
Leveraging Theorems and while following the same reasoning as Section 2.2 we obtain the following convergence (inner plus outer loops) for Algorithm 2
Theorem 9, Let Assumptions
7 to 9
be satisfied with S Lp S Lg Then, Algorithm requires
o Lg log
calls of (xx) and o 8 La ! calls of P(x)
find an e-solution of problem (T)
We also consider the case of monotone VIs (Assumption with 0). For this we modify Algorithm
as Appendix B.2 and obtain the following convergence result.
Theorem 10. Let Assumption (with μ 0), g be satisfied and Lp S Lg. Then, Algorithm requires
described in Appendix B.2
1 =11)
calls of (x) and (-21 x² IP) calls of P(x)
to find an e-solution of the problem 10 Here e-solution is measured by the value of the gap function.
4.4 Application to distributed saddle-point problem under similarity
We apply now Algorithm 2 to solve distributed saddle-point problem under statistical similarity, as introduced in :
mingeR*s max.ER*= r(y, 2) E (1( S.y,
(16)
Assumption 10. Each f((y,)): R&d x RRd= - is convex-concave and L-smooth on Rdd x Rdd
Assumption 11. r(2.1) :)) is j-strongly corvex (first argument) p-stronggy concave (second argument).
Assumption 12. fi :),.,,, fn(y,)) are 8-related: for all i + and for all y E Rdy and E RRd,,
f(y, 2)ll < 6, P 2) Vyrfs 2)1l < 6, 2 V (y. 2)1l 8.
8

---

Casting 16 into the VI formulation 10 by taking -V,
=)]
fy) - we have that Q is monotone and T=-Lipschitz, P is 8-Lipschitz R is u-strongly monotone. Therefore, we can apply Theorems and 10 and obtain the following convergence results for Algorithm appliee to (T6).
and P(r Ply.2) 2) 1 f.ly.2).
Theorem 11. Let Assumptions 10 to 12 be satisfied with 5 L. Then, to find E-solution of the distributed saddle problem [6. Algorithm requires
O (+ log !) communication rounds and O (+ log local gradient computations.
Theorem 12. Let Assumptions To 77 (with μs 0). T2 be satisfied and 6 L. Then, to find
E-solution of the distributed saddle problem (16), Algorithm requires
O (g
1²) communication rounds and O 12 x²1)²) local computations.
Our communication estimates are optimal, as in 19. but our algorithm also achieve optimal local complexity (see Table
5 Experiments
5.1 Minimization
We consider the Ridge Regression problem
1
min
f(w)
Σ (w x; y,)2 ++21111 2|101
(17)
2N
where w the vector of weights of the model, {x,, y/ ) the training dataset, and >> 0 is the regularization parameter.
We consider a network with workers (simulated on a Single-CPU machine), and use two types of datasets, namely: synthetic and real data. Synthetic data permit to control the similarity constant d. To do so, we generate data on the server, say {&r, Ds | 1n=100 Data on the workers are generated by adding unbiased Gaussian noise to the server data. The lower the variance of this noise, the more similar the data, and thus the smaller 8. For simulations with real data, we considered the LIBSVM library [1I] and give each agent full dataset. Then, each device selects random part of size m from the full dataset. In Section C.2 we explain how the parameters and are estimated. For the synthetic dataset we choose the noise level and the regularization parameter such that L/ 200 and L/> X = 10 For the real datasets the regularization parameter is chosen such that L/X = 106. See Table For all values of L, 6, μ and m.
For comparison, we use distributed version of Accelerated Gradient Descent (AcGD) t as the basic, classical and optimal method for minimization problems without additional similarity assumptions, as well as of-te-of-the-art schemes for the similarity condition: DANE 42]. DANE- HB [50]. SPAG 21 and AccSONATA [А The settings of the methods made described in the original papers. For algorithms that assume an absolutely accurate solution of local problems (DANE, SPAG, AcCSONATA),
AcGD with accuracy of 10-12 subsolver.
Results are summarized in Figure T-the first two figures from the top left correspond synthetic data while the other on real data.
The results show that our method outperforms almost all methods in terms of communication (only in one experiment SPAG is slightly faster), In terms of local iterations, our method is slightly inferior AcGD, but superior all other methods.
In Appendix C.T one can find a comparison of our method with a competitor for distributed saddle point problems under similarity assumption.
Acknowledgments
The research Sections 1-3 was supported by Russian Science Foundation (project No. 21-71- 30005). The work in Section 4 was prepared within the framework of the HSE University Basic Reaearch Programm. The research of A. Scutari was partially supported by the ONR Grant N. N00014-21-1-2673.

---

DAKE
DMR
(a) synthetic
(b) real: w8a
DAKE
de Aecooura
(c) real: w7a
(d) real: a9a
Figure 1: Ridge regression problem 17 Comparison of tfate-of-the-arr methods, under similarity; synthetic data (a) and real data (b.c.d). Distance from optimality vs. number of communications (first/third panel from the left in the both lines) and vs. number of local iterations (second/fourth panel from the left in the both lines).
References
[1] Artem Agafonov, Pavel Dvurechensky, Gesualdo Scutari, Alexander Gasnikov, Dmitry Kam- zolov, Aleksandr Lukashevich, and Amir Daneshmand. An accelerated second-order method for distributed stochastic optimization. arXiv preprint arXiv:2/03. /4392, 2021.
[2] Masoud Ahookhosh and Yurii Nesterov. High-order methods beyond the classical complexity bounds, ir: inexact high-order proximal-point methods with segment search. arXiv preprint DOXi:2219.112033 2021.
[3] Mohammad S Alkousa, Alexander Vladimirovich Gasnikov, Darina Mikhailovna Dvinskikh, Dmitry A Kovalev, and Fedor Sergeevich Stonyakin. Accelerated methods for saddle- saddle-point problem. Computational Mathematics and Mathematical Physics, 60(11):1787-180) 2020.
[4] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances neural information processing systems, 28. 2015.
[5] Heinz Bauschke and Patrick Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. 01 2017.
[6] Amir Beck and Mare Teboulle. A fast iterative shrinkage-threshholinng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-202, 2009.
[7] R. Bekkerman, M. Bilenko, and J. Langford. Scaling up Machine Learning: Parallel and Distributed Approuches. Cambridge University Press, 2011.
[8] Aleksandr Beznosikov, Eduard Gorbunov, and Alexander Gasnikov. Derivative-free method for composite optimization with applications to decentralized distributed optimization. IFAC- PapersOnLine,, 53(2):4038 4043, 2020.
[9] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Dis- tributed saddle-point problems under data similarity. Advances Neural Information Processing Systems, 34, 2021.
[10] Ekaterina Borodich, Aleksandr Beznosikov, Abdurakhmon Sadiev, Vadim Sushko, Nikolay Savelyev, Martin Takáč, and Alexander Gasnikov. Decentralized personalized federated min- max problems. arXiv preprint 2tt.:::20060028829 2021.
[11] Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions intelligent systems and technology (TIST), 2(3):1-27, 2011.
[12] Amir Daneshmand, Gesualdo Scutari, Pavel Dvurechensky, and Alexander Gasnikov. Newton method over networks is fast up to the statistical precision, International Conference on Machine Learning, pages
PMLR, 2021.
10

---

[13] John C Duchi, Shai Shalev-Shwartz, Yoram Singer. and Ambuj Tewari. Composite objective mirror descent. In COLT, volume 10, pages 14-26. Citeseer, 2010.
[14] Darina Dvinskikh, Sergey Omelchenko, Alexander Gasnikov, and Alexander Tyurin. Acceler- ated gradient sliding for minimizing a sum of functions. In Doklady Mathemalics, volume 101, pages 244-246. Springer, 2020.
[15] Facchinei and J.S. Pang. Fiitt--Dimessonal Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. Springer New York, 2007.
[16] Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Prohlems. Springer Series Operations Research. Springer, 2003.
[17] Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurechensky, Dmitry Kamzolov, Vladislav Matyukhin, Dmitry Pasechnyuk, Nazary Tupitsa, and Alexey Chernov. Accelerated meta- algorithm for convex optimization problems. Computational Mathematics and Mathematical Physics, 67-1), 2021.
(18) Ian Goodfellow, Jean Pouget-Abadic Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems (NIPS), 2014.
[19] Eduard Gorbunov, Darina Dvinskikh, and Alexander Gasnikov. Optimal decentralized dis- tributed algorithms for stochastic convex optimization. arXiv preprint arXiv:1911.07362 2019.
[20] Geovani Nunes Grapiglia and Yurii Nesterov. Adaptive third-order methods for composite convex optimization. arXiv preprint (rXiv:2202.127535 2022.
[21] Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, and Laurent Massoulie. Statisti- cally preconditioned accelerated gradient method for distributed optimization. In International Conference on Machine Learning, pages 4203 4227. PMLR, 2020.
[22] Anastasiya Ivanova, Evgeniya Vorontsova, Dmitry Pasechnyuk, Alexander Gasnikov, Pavel Dvurechensky, Darina Dvinskikh, and Alexander Tyurin. Oracle complexity separation in convex optimization. arXiv preprint arXiv:2002.002706 2020.
[23] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox proxo algorithm. Stochastic Systems, 111::17-58, 2011.
[24] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode. Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1 1-210, 2021.
[25] Dmitry Kamzolov, Alexander Gasnikov, and Pavel Dvurechensky. Optimal combination of tensor optimization methods. In International Conference on Optimization and Applications, pages 166-183. Springer, 2020.
[26] Donghwan Kim and Jeffrey Fessler. Generalizing the optimized gradient method for smooth convex minimization. SIAM Journal on Optimization, 28(2): 2018. 8.
[27] Donghwan Kim and Jeffrey A Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient smooth convex functions. Journal of optimization theory and applications, 188(1):192-219 2021.
[28] Guanghui Lan. Gradient sliding for composite optimization. Mathematical Programming, 159(1)200--235, 2016.
[29] Guanghui Lan and Yuyuan Ouyang. Accelerated gradient sliding for structured convex opti- mization. arXiv preprint (00vv:66000090000 2016.
[30] Guanghui Lan and Yuyuan Ouyang. Mirror-prox sliding methods for solving class of monotone variational inequalities. arXiv preprint arXhv:2111.00990 2021.

---

[31] Guanghui Lan and Yi Zhou. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26(2):1379-1409, 2016.
[32] X. Lian, C. Zhang, H. Zhang, C.-J. Hsich, W. Zhang, and Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330-5340, 2017.
[33] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui, Catalyst acceleration for first-order convex optimization: from theory to practice. Journal of Machine Learning Research, 18(1):7554-9077, 2018.
[34] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations (ICLR), 2018.
[35] Yu Nesterov. Gradient methods for minimizing composite functions. Mathematical program- ming, (40(1)) 2013.
[36] Yurii Nesterov. Dual extrapolation and its upplications to solving variational incqualities and related problems. Mathematical Programming, 109(2)3119-344 2007.
[37] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[38] Yurii Nesterov, Alexander Gasnikov, Sergey Guminov, and Pavel Dvurechensky. Primal- accelerated gradient methods with small-dimensional relaxation oracle. Optimization Methods and Software, pages 1-38, 2020.
[39] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1):1-35, 2021.
[40] Sashank J Reddi, Jakub Konečný, Peter Richtárik, Barnabás P6ezós, and Alex Smola. Aide: Fast and communication efficient distributed optimization. arXiv preprint arXiv: (600:::000777 2016.
[41] Abdurakhmon Sadiev, Darina Dvinskikh, Alcksandr Beznosikov, and Alexander Gasnikov. Decentralized and personalized federated learning. arXiv preprint 107.v:2 190, 2021.
[42] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication--fficiee using approximate newton-type method. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1000-1008, Bejing, China, 22-24 Jun 2014. PMLR.
distributed optimization
[43] Ivan Stepanov, Artyom Voronov, Aleksandr Beznosikov, and Alexander Gasnikov. One-point gradient-free methods for composite optimization with applications to distributed optimization. arXiv preprini 1rXiv:2107..05511 2021.
[44] Sebastian U Stich. Local sgd converges fast and communicates little. 2018.
arXiv preprint
[45] Ying Sun, Amir Daneshmand, and Gesualdo Scutari. Distributed optimization based on gradient-Iracking revisited: Enhancing convergence rate via surrogation. arXiv preprint arXiv:1905.02637, 2019.
[46] Ye Tian, Gesualdo Scutari, Tianyu Cao, and Alexander Gasnikov. Acceleration in distributed optimization under similarity. arXiv preprint 10.11477, 2021.
[47] Vladislav Tominin, Yaroslav Tominin, Ekaterina Borodich, Dmitry Kovalev, Alexander Gas- nikov, and Pavel Dvurechensky. On accelerated methods for saddle-point problems with composite structure. arXiv preprint 1xXiv:2103309344 2021.
[48] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. local sgd better than minibatch sgd? In International Conference Machine Learning, pages 10344. PMLR, 2020.
12

---

[49] TaeHo Yoon and Ernest K Ryu. Accelerated algorithms for smooth convex concave minimax problems with o (1/k" rate on squared gradient norm. In International Conference on Machine Learning, pages 12098-12109. PMLR, 2021.
[50] Xiao-Tong Yuan and Ping Li. On convergence of distributed approximate newton methods: Globalization, sharper bounds and beyond. arXiv preprint arXiv:1908.02244 2019.
[51] Yuchen Zhang and Xiao Lin. Disco: Distributed optimization for self-concordant empirical loss.
In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 362-370, Lille, France, 07-09 Jul 2015. PMLR.
13

---

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]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A], theoreti-
cal paper
(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]
(b) Did you include complete proofs of all theoretical results? [Yes]
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 a URL)? [N/A], we work with small models and simple optimisers, the experiments are easy to reproduce on any PC, but will try make the code user friendly and put it out in the public domain (b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]. Section 5 gives information about the problem setup, all methods are tuned how is done in the original papers
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A], methods are deterministic
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes], Appendix C, but we make small experiments, they can be run on any PC
4. If you 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? [Yes], Section 5.1, cite LIBSVM
(b) Did you mention the license of the assets? [N/A] open assets
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "uy-zmzhBKW3", "reviewer": "Reviewer_xSX2", "summary": "The author studied a convex optimization problem, where the objective function can be decomposed into a smooth convex function and a possible nonconvex function. There are three major contributions: 1. the author proposed gradient sliding algorithm which achieves optimal complexity of gradient calls of each component functions; 2. the author proved the algorithm achieves optimal communication complexity under $\\delta$-similarity; 3. the author applied the proposed method to a class of distributed saddle-point optimization problem. ", "questions": "I am wondering what is the author's thoughts on the comparison between the proposed methods and the so-called local SGD studied in [1],\nand any thoughts on the proposed methods for deep learning.\n\n[1] Stich, Sebastian U. \"Local SGD converges fast and communicates little.\" arXiv preprint arXiv:1805.09767 (2018). ", "limitations": "the authors have adequately addressed the limitations ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is a good one with strong theoretical results and clear presentation.", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "rh9efOzqPbr", "reviewer": "Reviewer_21CM", "summary": "The paper combines extra gradient, gradient sliding, and acceleration to propose an accelerated extragradient sliding methods for convex composite optimization that achieves improved gradient complexity. When applied to distributed optimization problem under agents' function similarity, the method achieves lower bounds on communication and gradient complexities. The method is further extended to variational inequality setting.", "questions": "1. Line 23, \"a network of $m$ agents.\" For Equation (2), is it $1/m$ or $1/n$? See also Line 47, line 45 line 56.\n\n2. Line 44, why one would use the second order information for similarity notation? What would happen if one uses first/zeroth-order information for similarity notation. How to verify that function similarity holds.\n\n3. If there is similarity, does it reduce back to the stochastic setting? For example, if using first-order similarity notation, one may rewrite the problem as a stochastic optimization with a discrete distribution and bounded variance of the first-order information. \n\n4. For second-order similarity, how to evaluate it numerically?\n\n5. The proposed method combines acceleration, extragradient, and gradient sliding. It is unclear which component improves the complexity bound, comparing to the existing literature. Please specify with a more detailed comparison with existing literature on the methodology. \n\n## Minor Comments:\n1. Line 6, 7, missing bracket. \n2. Line 23, is it $m$ or $n$?\n3. Line 29, there are $m$ agents or $m$ samples? \n4. Line 30, what does it mean by mismatch between parameter and sample?\n5. Assumption 1 with $\\mu=0$ is normally treated as convexity while $\\mu<0$ is weakly convex in the literature. It would be nice to stay consistent. \n6. Example 2 Line 201, is it $\\min_z$ or $\\max_z$ as it is a saddle point problem. \n7. Line 114,  120, missing bracket", "limitations": "N.A. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n\n1. The paper combines extra gradient, gradient sliding, and acceleration that achieves $O(\\sqrt{L_p/\\mu})$ and $O(\\sqrt{L_q/\\mu})$ gradient call for $\\nabla p$ and $\\nabla q$ respectively, improving over the condition number for minimization problem. It well suits the unbalanced problem.\n2. The method is further extends to obtain optimal gradient sliding for VIs.\n3. When applied to distribution optimization and distributed minimax optimization under similarity assumption, the proposed methods achieve the lower bounds on both communication and gradient complexities.\n\n\n## Weakness\n\n1. Presentation needs serious improvements. See questions below.\n\n2. The numerical results are relatively less informative. On real datasets, the proposed method only achieves comparable performance with the state-of-the-art method. \n\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "Lvk8v68M8oc", "reviewer": "Reviewer_disq", "summary": "Paper considers convex minimization of sum of smooth functions r(x) = p(x) + q(x) with Lipschtiz-smoothness constants Lp and Lq (Lp < Lq). Here they assume that p can be non-convex and q is convex. This paper provides a gradient sliding algorithm which only uses O(\\sqrt{Lp}) gradients of p and O(\\sqrt{Lq}) gradients of q. This kind of separation is useful when first order oracle of p is much more costlier than that of q. Paper provides these results when r is convex, or strongly convex.\n\nThis algorithm is then used to obtain optimal communication and gradient complexities for distribution finite sum optimization under similarity Hessian assumption. Paper also extends the sliding scheme to the setting of solving a monotonic variation inequality of sum of two Lipschitz continuous operators.", "questions": "1. Why does the algorithm work? Why is this called “accelerated extragradient”\n2. What are examples where r is mu-strongly convex, p is nonconvex and q is convex?  It looks like the one in simulations doesn’t satisfy this. If there are no such examples, can step 5 of algorithm be solved using accelerated smooth strongly convex optimization?\n3. Function similarity assumption and the assumption 6 different (notice j in former). What is the relation between the two and why does the paper use a different assumption?\n4. Acc SONATA [44], what is the complexity to solve proximal steps? Is it O(\\sqrt{L_i/\\mu} \\log(1/eps)) because of strong convexity? If yes, this should be noted in the table as well.\n\n5. In experiments, what are the r, p and q, and Lp, Lq and \\mu?\n6. In experimental section what does lambda=0,1 mean? What was used for the experiments and why were these choices made?\n7. Please provide comparison to AccSONATA which has the SOTA communication complexity. The sub problems should be easy to compute if they are convex or strongly-convex.\t\n8. In Synthetic minimization dataset how much noise was added?\n\nMinor comments\n\n9. Lq >= Lp >= mu assumption should be more prominant\n10. “Weakly convex” function also has another meaning of mu < 0. May be use “convex”?\n", "limitations": "No limitations are provided. Authors may discuss the challenges of extending results to to nonconvex settings", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Gradient sliding results seems novel\n- Results seem to pass quick checking of logic\n- Paper provides results for two different settings and applies them to distributed optimization to obtain optimal guarantees\n- Experiments section\n\nWeakness\n- Paper does not explain the intuition behind the algorithm. The exposition should also make it clear how they are related to known ideas. These help the community assimilate the results and build on top of them to produce future scientific output.\n- No proper examples are provided for the settings studied in the paper.\n- Not enough experiment details are provided and there seems to be missing baselines\n- It is not clear whether the missing entries in the “Local gradient complexity” column of the table actually means these oracles are hard to solve. The best complexity for solving the oracle sub-problems should be mentioned here.\n\nAfter rebuttal\n- Authors addressed almost all of my concerns. Assuming authors will take action on my suggestions, including the new ones about the intuition and rewording the claim, I am increasing my score.", "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": "F7iPpsR-9-", "reviewer": "Reviewer_3MZq", "summary": "This paper considers a gradient sliding approach for distributed optimization. The idea is that by interleaving the computations between past and future iterates, the distributed optimization system is more robust to noise and convergence can be accelerated.", "questions": "It is possible that all the rest of the issues are misunderstandings, and if we can clarify them (and discuss how they can be clarified in the paper), I can increase my score.\n\nBroad strokes questions\n\n - Why is it called extragradient method? Extragradient usually implies taking two gradient calls and then using the second one, in order to get a \"midpoint discretization\" scheme and improve performance, but at a 2x overhead. None of the algorithms seem to be doing this.\n\n - It seems like the method mainly focuses on an outer loop / inner loop approach, where the outer loop achieves linear convergence and the inner loop borrows from other SOTA methods to get good guarantees. This seems appropriate for optimal rates, but I don't see the clear benefit to *distributed* optimization. Is this a noise variance controlling technique, or straggler mitigation technique? I guess what I'm asking is, if A = gradient sliding and B = optimal method, is this paper just A + B (arbitrary mix and match), or are there deeper ramifications for using this combination?\n\n - There is the big question also of what is hidden in the constants. For example, the scale of delta may be big in practice. More to the point, if delta is small in practice, to the point where the rates are tight, wouldn't the competitor methods work pretty well? A more extensive numerical experiments comparison would show if this is really a practical method.\n\n - What's the big idea behind using the prox operations in step 5 of alg 1? Is it just to achieve optimal rates? I ask because it seems prox operations are used, but aren't really discussed in terms of key benefits and numerical insights here, and the standard is usually just gradient descent. \n\nTechnical questions\n - In (8), I see a dependency of error on 1/T^2. However, in (9), T is a constant. This doesn't seem logical, since later inner iterations should require higher precision (and thus larger T) than initial ones. This of course affects the main final results (Thm 5)\n\n - Theorems 4 and 10 seem to better match the inner / outer loop issues, but they are kind of terrible rates then. How do they compare against competitors?\n", "limitations": "n/a", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n - The paper does a pretty thorough related works review, and seems to be integrating sophisticated methods.\n\nWeaknesses\n - It is a bit unwieldy to have 2 theorem boxes, which are referred to in the paper, in the appendix. In general I have a hard time understanding why each one is contributing something different, and something like this should be discussed more clearly in the main text.\n\n - The second set of numerical results are extremely inconclusive, and does not show consistent advantage at all. ", "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