Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
Authors: Dmitry Kovalev
Elnur Gasanov
Alexander Gasnikov
Peter Richtárik
Venue: NeurIPS 2021 Poster (2021)
Keywords: decentralized optimization
time-varying networks
ADOM
optimal algorithms
lower bounds
convex optimization

Abstract: We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network whose links are allowed to change in time. We solve two fundamental problems for this task. First, we establish {\em the first lower bounds} on the number of decentralized communication rounds and the number of local computations required to find an $\epsilon$-accurate solution. Second, we design two {\em optimal algorithms} that attain these lower bounds: (i) a variant of the recently proposed algorithm ADOM (Kovalev et al, 2021) enhanced via a multi-consensus subroutine, which is optimal in the case when access to the dual gradients is assumed, and (ii) a novel algorithm, called ADOM+, which is optimal in the case when access to the primal gradients is assumed. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.

Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time- Varying Networks
Dmitry Kovalev
Elnur Gasanoy
KAUST* Dakovalevv@@gail.com
KAUST
elnur, www.ggassaaass.eeeoomm eeu.eastttdud.... sa
Alexander Gasnikov MIPTi and ISP RAS
Peter Richtárik
KAUST
gasnikov@yandex.
richtarik@gmail.. com
Abstract
We consider the task of minimizing the sum of smooth and strongly convex fune- tions stored a decentralized manner across the nodes a communication network whose links allowed to change in time. We solve two fundamental problems for this task. First, we establish the first lower bounds on the numher of decentralized communication rounds and the number of local computations required to find (-accurate solution. Second, we design two optimal algorithms that attain these lower bounds: variant of the recently proposed algorithm ADOM (Kovalev) et al. 2021) enhanced via a multi-consensus subroutine, which is optimal in the case when access the dual gradients is assumed, and (ii) novel algorithm, called ADOM+, which is optimal in the case when access to the primal gradients is as- sumed. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of- of-the-art methods.
Introduction
In this work we are solving the decentralized optimization problem
min 2 E
f((x),
where each function f:: TRdd Rdd is stored on a compute node E {1,....n) nodes are connected through a communication network. Each node can perform local computations based on its local state and data, and can directly communicate with its neighbors only. Further, we assume the functions f; to be smooth and strongly convex.
.n). We assume that the
Such decentralized optimization problems arise in many applications, including estimation by sensor networks (Rabbat and Nowak 2004), network resource allocation (Beck et al., 22014), cooperative control (Giselsson al. [2013), distributed spectrum sensing (Bazerque and Giannakis, 2009) and power system control (Gan et al. 2012).. Moreover, problems of this form draw attention of the machine learning community (Scaman et al. 2017). since they cover training of supervised machine
Kiin Abdullah University of Science and Technology. Thuwal, Saudi Arabia. Moscow Institute of Physics and Technology, Moscow, Russia $ Institute for System Programming of the Russian Academy of Sciences, Research Center for Trusted Artificial Intelligence, Moscow, Russia
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

learning models through empirical risk minimization from the data stored across the nodes of a net- work as a special case. Finally, while the current federated learning (Konečný et al. 2016 McMahan et al. 2017) systems rely star network topology, with trusted server performing aggregation and coordination placed at the center of the network, advances in decentralized optimization could be useful in new-generation federated learning formulations that would rely on fully decentralized computation (Li et al. 2020).
1.1 Time-varying Networks
In this work, we focus on the practically highly relevant and theoretically challenging situation when the links in the communication network are allowed to change over time. Such time-varying networks (Zadch 1961; Kolar et al. 2010) are ubiquitous in many complex systems and practical applications. In sensor networks, for example, changes in the link structure occur when the sensors are in motion, and due to other disturbances in the wireless signal connecting pairs of nodes. We envisage that similar regime will be supported in future-genen geurreegnnattonn federated learning systems (Konečný al.) 2016, McMahan et al.) 2017), where the communication pattern among pairs of mobile devices or mobile devices and edge servers will be dictated by their physical proximity, which naturally changes over time.
1.2 Contributions
In this work we present the following key contributions:
1. Lower bounds. We establish the first lower bounds on decentralized communication and local computation complexities for solving problem ( over time-varying networks. Our results are summarized in Table 1 and detailed in Section (see Theorems 2 and B therein).
2. Optimal algorithms. Further, we prove that these bounds are tight by providing two new optimal algorithms which match these lower bounds:
(i) variant of the recently proposed algorithm ADOM (Kovalev et al., 2021 enhanced via a multi-consensus subroutine, and
iii a novel algorithm, called ADOM+ (Algorithm D. also featuring multi-consensus.
The former method optimal in the case when access to the dual gradients assumed, and the latter one is optimal in the case when access to the primal gradients is assumed. See Sections [5d for details. To the best of our knowledge, ADOM with multi-consensus the first dual based optimal decentralized algorithm for time-varying networks
3. Experiments. Through illustrative numerical experiments (see Section 6 and the extra experiments contained the appendix) we demonstrate that our methods are implementable, and that they perform comperitively when compared to existing bascline methods APM-C
(Rogozin et al. 2020 Li al. 2018) and Acc-GT (Li and Lin 2021).
Related Work. When the communication network is fixed in time, decentralized distributed opti- mization in the strongly convex and smooth regime relatively well studied. In particular, [Scaman et al. (201)) established lower decentralized communication and local computation complexities for solving this problem, and proposed an optimal algorithm called MSDA in the case when an access to the dual oracle (gradient of the Fenchel transform of the objective function) is assumed. Under primal oracle (gradient of the objective function), current state of the art includes the near-optimal
algorithms APM-C (Li et al. 2018 Dvinskikh and Gasnikov 2019) and Mudag (Ye et al. 2020). and
a recently proposed optimal algorithm OPAPC (Kovalev et al. 20200).
The situation is worse in the time-varying case. To the best of our knowledge, no lower decentralized communication complexity bound exists for this problem. There are a few linearly-convergent algorithms, such as those of Nedic et al. (2017) and Push- Pull Gradient Method Pf et al. (2020). that assume primal oracle, and the dual oracle based algorithm PANDA due to Maros and Jaldén (2018). These algorithms have complicated theoretical analyses, which results in slow convergence rates. There are also several accelerated algorithms, which were originally developed for the fixed
4 "s a byproduct of our lower bounds, we show that the recently proposed method Acc-GT of Li and Lin 1021) is also optimal. This method appeared on arXiv in April 2021, at the time when we already had first draft of this paper, including all results. Their work does not offer any lower bounds.

---

Table 1: Current theoretical statc-of-the-art methods for solving problem over time-varying networks, and our contributions: lower bounds (first lower bounds for this problem), and two new optimal algorithms, ADOM and ADOM+ with multi-consensus.
Local computation
Decentralized communication
Gradient oracle
Algorithm
complexity
complexity
Known Results
APM-C
12 12//log log
O XM
log"
primal
(Rogozin el al.
2020
Mudag
0
K
log
o
(xx' 1/rl/1lgg (og((()) log
primal
Yc
2020
Acc-G1 with mu li-consensus
2/2 log
(xx=1 log
primal
Li and Lin
2021
Our Results
ADOM with multi-consensus
(x11 11112108
0 xmx 1/21// (rwl/2log/ log 2)
dual
This Paper, Theorem
ADOM+ with multi-consensus
k 1/2 log :)
X (xal122 1/x1/2100 log !)
primal
This Paper, Theorem
Lower Bounds
1/2 log
o
[xx'122 log ))
both
This Paper, Theorems and
network case, and can be extended to the time-varying case. These include Acc-DNGD (Qu and Li 2019), Mudag (Ye et al. (2020) and a variant of APM-C which was extended to the time-varying case by Rogozin et al. (2020). Finally, there are two algorithms with state-of-the-art decentralized communication complexity: dual based algorithm ADOM (Kovalev et al. (202I). ) and primal based algorithm Acc-GT (Li and Lin 2021).
2 Notation and Assumptions
2.1 Smooth and Strongly Convex Regime
Throughout this paper we restrict each function fi(x) to L-smooth and μ-strongly convex. That is, we require the following inequalities hold for x, y E IRd and E {1....,.1) n):
fi(y) + (V)))) v) + y/12 [+xx) < f(()) (VS()), v) + v112.
(2)
This naturally leads the quantity x & known as the condition number of function f.. Strong convexity implies that problem (T) has unique solution.
2.2 Primal and Dual Oracle
In our work we consider two types of gradient oracles. By primal oracle we denote the situation when the gradients Ví of the objective functions fa available. By dual oracle we denote the situation when the gradients V.f" of the Fenchel conjugates S of the objective functions fi are available.
2.3 Decentralized Communication
Let V= (1,...... n denote the set the compute nodes. We assume that decentralized communica-
tion is split into communication rounds. At each round E (0. ..., nodes connected through a communication network represented by graph g = (V, E"), where C {(i.j) E V x : i j] is the set of links round q. For each node
V consider set of its immediate neighbors at round q: No = {j E V : (i.j) E Ed). At round each node E V can communicate with nodes from the set N, only. This type of communication is known in the literature as decentralized communication.
Recall that the Fenchel conjugate fo is given as fi (x) = sup,ers (xx, v) -f())). Note, that fr 1/2 smooth and l/z-strongly convex (Rockafellar 2015).

---

2.4 Gossip Matrices
Decentralized communication between nodes typically represented via matrix-vector vector multiplica- tion with gossip matrix. For each decentralized communication round q E 1.. consider matrix (()) IR xx* satisfying the following assumption.
Assumption 1. For any E {0, 2...... matrix (gg) E R satisfies the following relations:
1. W(g)a = 0 if # and (i,j) & E4,
2. ker W(1) > { In) E R 21 _... = =zn
3. rangeW(g) C ((11....,,,, Rn) E TR Eis 2i = 0}.
4. There exists X 2 such that
[W œ < (1 x || for all a E ((11, E ER" : =; 0}. (3)
Throughout this paper we will refer the matrix W(q) the gossip matrix. typical example of gossip matrix is (g)) X (L(q)) L(q), where L(g) the Laplacian of an undirected connected graph 9o. Note that in this case ((q) symmetric and positive semi-definite, and X can be chosen
as an upper-bound on the condition number of the matrix L(q) defined by = sup, A (L(o))
Amas (L(g))
where Amax (L(g)) and (Lg)) denote the largest and the smallest positive eigenvalue of L(g), respectively. With a slight abuse of language, we will call the condition number of time-varying network even when the gossip matrices W(4) not necessarily symmetric.
(L(g))
While the notion of a gossip matrix is typically used the fixed network setting (Scaman et al. 2017). we adapt this notion to the time-varying regime in which the so-called mixing matrices (Nedic et al. 2017) are typically used instead. However, turns out that there no major difference between these notions. While we decided to present our main results in the language of gossip matrices, they can alternatively be described in the language of mixing matrices instead. We provide a detailed discussion of this in the appendix.
3 Lower Complexity Bounds
In this section we obtain lower bounds on the decentralized communication and local computation complexities for solving problem (I). These lower bounds apply to algorithms which belong to certain class, which we call First-order Decentralized Algorithmss Algorithms from this class need to satisfy the following assumptions:
1. Each compute node can calculate first-order characteristics, such gradient of the function it stores, or its Fenchel conjugate.
2. Each compute node communicate values, such as vectors from Rd. with its neighbors. Note that the set of neighbors for each node is not fixed time.
We repeat here that when the network is fixed in time, lower decentralized communication and local computation complexity bounds were obtained by Scaman et al. (0117).
3.1 First-order Decentralized Algorithms
Here we give formal definition of the class of algorithms for which we provide lower bounds on the complexity of solving problem (1). At each time step & E {0, 1, 1,2,...) each node i E V maintains finite local memory (k) C gd For simplicity, we assume that the local memory is initialized as Hk(k) (0).
At each time step k. an algorithm either performs a decentralized communication round, or local computation round that update the memory H, (k). The update of the local memory satisfies the following rules:
1. If an algorithm performs a local computation round at time step k then Ha(k + 1) C Span((x, (x))), V (a) x E H4)))) for all i E V. where f is the Fenchel conjugate of ft.

---

local computation
x
x
decentralized communication
x
/
/
x
x
/ / 3
x
communication round number 4 time step l
2
4
6
Figure 1: The way count decentralized communication rounds (q) and iterations (k).
2. If algorithm performs decentralized communication round at time step k then
Hi(k + 1) C Span (UJENTURO)
for all i V. where q {0, .,.. refers to the number of decentralized communication round performed so far, counting from the first one, for which we set = 0. See Figure for graphical illustration of our time step (k) and decentralized communication (q) counters.
At time step k each node E V must specify an output value (k) E (k)..
In the case of time-invariant networks, (Scaman et al. (2017) presented lower complexity bounds for class of algorithms called Black-box Optimization Procedures. This class slightly more general than our First-order Decentralized Algorithms. In particular, rather than continuous time, and do not allow decentralized communications and local computations to be performed in parallel and asynchronously. We have done this for the sake of simplicity and clarity. This should not be seen as a weakness our work, since our results can be easily extended to Black-box Optimization Procedures. However, not give any new substantial insights.
discrete time & E f0, 1,
of the opinion that such extension would
3.2
Main Theorems
We now ready present main theorems describing the first lower bounds on the number of decentralized communication rounds and local computation rounds that are necessary to find an approximate solution of the problem (T). In order to simplify the proofs, and following the approach used by /esterov| (2003), we consider the limiting case + +00. More precisely, we will work in the infinite dimensional space E2 { (rq))==1 (x)) +00 rather than Rd
q= corresponding Theorem 1. Let 2 L > p 2 There exists a sequence of graphs {G")
sequence of gossip matrices (W(g)) ] 0 C R=xx satisfying the Assumption 7 and p-strongly convex and L-soooth functions fi l + IR, d V, such that for any first-order decentrulized algorithm and any k [0, ..
[k](k)) 22
24/6p maxx (0.
))ux
VI
where q is the number of decentralized communication rounds performed by the algorithm before time step k x² is the solution of the problem ( and C is some constant.
Our proof is inspired by the proof of Scaman et al. (207)) for time- inme-invrriant networks, which in its turn is based on the proof oracle complexities for strongly convex and smooth optimization by Nesterov (2003). Here give short outline of our proof.
We choose n = | R X nodes and split them into three disjoint sets, V1, V22 and V3. of equal size n/3. Further, we split the function used by Nesterov (2003) onto the nodes belonging to V and V/- One then needs to show that most dimensions of the output vectors (k) will remain zero, while local computations may only increase the number of non-zero dimensions by one. In contrast to (Seaman et al., 2017), we need to have V2 RS x rather than V2/l RS Vx. and still ensure that at least [2] decentralized communication rounds necessary share information between node groups V1 and Vg. We achieve this by choosing a sequence star graphs with the center node cycling through the nodes from V22
Theorem 2. For any 2 3, L 2 0 there exists a sequence of graphs po corresponding sequence of gossip matrices W (g) C. ga satisfying the Assumption 7 and p-strongly convex
5

---

and L-smooth functtions f: R.ie V, such that for any first order decentralized algorithm. the number of decentralized communication rounds find an e-accurate solution of the problem (T) is lower bounded by
Ω
(5)
We also provide lower bound on the local computation complexity. The proof is similar to the proof of Theorem [
Theorem For any X X23, 3,
μ 2 there exists a sequence of graphs { 1==0- corresponding sequence of gossip matrices { (4) C BRxx satisfying the Assumption 7 and p-strongly convex
and L-smooth functions f; l2 + R, V. such that for any first order decentralized algorithm. the number of local computation rounds to find an e-accurate solution of the problem ① is lower bounded by
Ω 1 log
(6)
The detailed proof' are available in the appendix.
4 Primal Algorithm with Optimal Communication Complexity
In this section we develop novel algorithm for decentralized optimization over time-varying networks with optimal decentralized communication complexity. This primal algorithm, meaning that it uses the primal gradient oracle. The design of this algorithm relies on sequence of specific reformulations the problem [T) which we now describe.
4.1 Reformulation via Lifting
Consider function F: (IR)) - R defined by
F(x) = 1 f(x))) iEV
where = (zi,.... )n) E (Rd) This function is L-smooth and μ-strongly convex since the individual functions /; are. Consider also the so called consensus space C (IRd)V defined by
C [ [(Z1,...,,,) v.) E (Rd)²= I J.
(8)
Using this notation, we arrive the equivalent formulation of problem II)
min
F(x).
(9)
zEC
Due to strong convexity, this reformulation has unique solution, which we denote x² E L.
4.2 Saddle Point Reformulation
Next, we introduce reformulation of problem 9 using a parameter v E (0, (1) and slack variable E (IR)):
min (
F(x) || + [|
W=
Note that the function F(x) |=||| is (μ -ttonngyy convex since v < The latter problem is minimization problem with linear constraints. Hence, has the equivalent saddle-point reformulation
min max max F(r) - ~| + / ||ll + (y. x) + (z, w))
W vE(RA) =EL-
where L+ (Rd)) is orthogonal complement the space L, defined by
k [(z) ... 2n) (R Σm 2 0}.
(10)
Minimization in w gives the final saddle-poing reformulation of the problem 9
min max max F(x) / |||=||| (y, x) 2 11 2|| zE(3d) (R #EL+
(11)

---

Further, by E we denote the Euclidean space E = (RR x (I x L' One can show that the
saddle-point problem (TT) has unique solution (x" yy 2²) which satisfies the following optimality conditions:
= VF(x*) vx yf,
(12)
0 == v (v" + +2" +
(13)
L y" +
(14)
4.3 Monotone Inclusion Reformulation
Consider two monotone operators A, B:: E + E, defined via
VF(x) vE V (y +2) Pv (y +2)
y B(x,
A v,)
(15)
0
where P is an orthogonal projection matrix onto the subspace L Matrix is given as
P = (I, 11 2 Id.
(16)
where Ip denotes p x p identity matrix, 1, = (L...., 1) E I", and @ is the Kronecker product. Then, solving problem (TT) is equivalent to finding (x", V² 2*)
E, such that
A(x", .V, 2²) + B(x", /0' ,,,
0.
(17)
Indeed, optimality condition (14 is equivalent to proje= - (y" +2*) = orr Py- +-" 0. Now, it is clear that is just another way to write the optimality conditions for problem 11
4.4 Primal Algorithm Design and Convergence
common approach to solving problem (17) is the Forward- Backward algorithm. The update rule of this algorithm is (xt, yt, _ = Jw y, z) wA(x, z)] where >> O is a stepsize, the operator J.B: E + E is called the resolvent, and is defined as the inverse of the operator wB): E E, where /: E + E is the identity mapping. One can observe that the resolvent JwB easy to compute.
Following (Kovalev et al. 2020), we use an accelerated version of the -ackwa-- algorithm. This can indeed be done, since the operator A: E - is the gradient of the smooth and convex function (I. y, 2) Fxx) || + lly + =|| on the Euclidean space E. Note that the operator A + B is not strongly monotone, while strong monotonicity is usually required to achieve línear convergence. However, we can still obtain a linear convergence rate by carefully utilizing the L-smoothness property of the function F(z). Similar issue appeared in the design of algorithms for solving (Condat et al. 2019; (aalm et al. 2020) and the optimal algorithm (Salim al. 202T). However, the authors of these works considered a different problem reformulation from (11). and hence their
minimizations problems, including the non-accelerated algorithms
results can not be applied here.
However, one issue still remains: to compute the operator A, it is necessary to perform a matrix- vector multiplication with the matrix P. which requires full averaging, i.e, consensus over all nodes of the network. Following the approach of Kovalev et al. (2021), we replace with the decentralized communication round only. That is, we replace the last component P (y + 2) of the operator A defined by (15) with (W (g) LA)=> -t + 2). Kovalev al. 2021 showed that multiplication with the gossip matrix be
multiplication via the gossip matrix (g) Ia, which requires
compression the Euclidean space L i.e., condition (3) holds, and hence the so-called error- feedback mechanism (Stich and Karimireddy 2019; Karimireddy et al. 2019 Gorbunov al.) 2020) can be applied obtain linear convergence. We use this insight in the design of our algorithm.
Armed with all these ideas, are ready to present our method ADOM+; Algorithm
7

---

Algorithm ADOM+
1: input: x0 y/. m E (Rd)
20
E C
2: z x² 177 1//
y of 0
20
3: for k = =0 1,1,2
do
4:
z = Tjax +
Ti )
5:
** ++1 x² + na( xx+1)
(V( - very yx
6:
k ++1 F4 + 12(a k+1 x/)
7:
" = 01y R + (1 )
8:
++ J¹ + +V8(FF(2))
1r y x 113 + 2/) + x
9:
f *+1 11 + (2
k+1 - -1²)
g 01 2 + (1 0
11:
# *+1 2 + (0(2) k
=²) - [WW)))) & Ia) 1
[uf + = + m
12:
m m k-
(u + 2g) + +m (W(() @ Ia) [-p- (u, + 2 + m
k+1 2 (IW( s La) + +
end for
We now establish the convergence rate of Algorithm Theorem 4 (Convergence of ADOM+). To reach precision 1 - x²1² S Algorithm 7 requires the following number of iterations
o (xV
Note that A (11) decentralized communication and local computation rounds. Hence, its decentralized communication and local computation complexities are 0 log
Optimal Algorithms
In this section we develop decentralized algorithms for time-varying networks with optimal local computation and decentralized communication complexities. We develop both primal and dual algorithms that use primal and dual gradient oracle, respectively. The key mechanism to obtain optimal algorithms to incorporate the multi-consensus procedure into the algorithms with optimal decentralized communication complexity.
5.1 Multi-consensus Procedure
As discussed in Section 2.4 decentralized communication round cab represented as the multi- plication with the gossip matrix W(g). The main idea behind the multi-consensus procedure is to replace the matrix (g)) with another matrix, namely
(A+1)T-1 II Q=
W(k; In
(I, WW))),
(18)
where & E {0, 1, ... is the iteration counter, and T E (1,2....) is the number of consensus steps. One can show that this matrix satisfies the Assumption 1 including the contraction property {
WW: 7)x x1 < ")) for all x L
(19)
One can also observe that multiplication with the matrix W Wk;;T') requires to perform multiplication with T gossip matrices WKKT), +1)++11). W(K + - hence it requires decentralized communication rounds.
5.2 Optimal Algorithms: ADOM and ADOM+ with multi-consensus
Now, we are ready to describe our optimal algorithms for smooth and strongly decentralized opti- mization over time-varying networks. As mentioned before, start with algorithms with optimal

---

peometiicc grazis
Qecinetnc gtadfs
10"1
10
APMC
10-
1073
Acc-T
ADOM+
APMCC
137
APMC
12
10'44
10
19
cesloso 5930999 12800000
communmeaaiioo rounds
or gradiett cals
communiiciins Tounds
of gradietz cats
Figure 2: Comparison of our method ADOM+ and the baselines Acc-GT and APM-C.
decentralized communication complexity. In the case when access to the primal oracle is assumed, ADOM+ (Algorithm TT the algorithm of choice. In the case when access to the dual oracle is assumed, Kovalev et al. (2021) proposed the dual based accelerated decentralized algorithm ADOM. The original convergence proof of this algorithm requires the gossip matrix W(k) be symmetric. However, the generalization of this proof to the case when the gossip matrix satisfies Assumption and is not necessarily symmetric, is straightforward.
Both ADOM and ADOM+ require O (XV/%/ log iterations to obtain an e-accurate solution of
problem T. and at each iteration they perform (11) local computation and decentralized communica- tion rounds, i.e., multiplications with the gossip matrix ((g). We now incorporate multi-consensus procedure into both algorithms. That is, we replace matrix (()) with the matrix ((k; (T) defined (18), where {0, 1, ... the iteration counter. As mentioned before, this equivalent to performing ((")) decentralized communication rounds at each iteration. Choosing the number of consensus steps = Ix 2] together with (19) implies
[W: xr12 s || for all æ e C.L.
(20)
This means that W(k:)) satisfies (3) with x replaced by 1 and hence both ADOM and ADOM+ with multi-consensus require (VL/uu log iterations to obtain an e-accurate solution. Taking into account that these algorithms still perform ((1) local computations and O(T) O(x) decentralized communication rounds at each iteration, we arrive at the following theorems.
Theorem 5. Let the functions fI...., be L-smooth and j-strongly convex and let the Assump- tion 1 hold. Then, ADOM with malti-consensus requires O VT//ulog :) local computation rounds decentralized communication rounds to find an e-accurate solution of the distributed optimization problem (
and (xV%/ulog logg :)
Theorem 6. Let the functions fi...., fn be L-smooth and u-strongly convex and let the Assumption 7 hold. Then, ADOM+ with multi-consensus requires O (Vilu log !) local computation rounds and O (xvT//log) decentralized communication rounds to find an e-accurate solution of the distributed optimization problem
5.3 Comparison with Ace-GT (Li and Lin 2021
To the best of our knowledge ADOM with
is the first dual based optimal decentralized algorithm for time- varying networks. In the case when the primal oracle is assumed, besides ADOM+ with multi- conlli-consensus, there only one previously existing algorithm, Acc-GT with multi-consensus Li and Lin, 2021), which achieves optimal local computation and decentralized communication complexities. However, in the case when multi-consensus not used, its iteration complexity is o 3/2 lo/ 4). which is worse than the complexity of ADOM+, by the factor x 1/2, Since communication is known to be the main bottleneck in distributed training systems, multi-consensus is unlikely to used in practice, which may limit the practical performance Acc-GT in comparison to ADOM+

---

Experiments
In this section we perform an illustrative experiment with logistic regression. We take 10, 000 samples from the covtype A and distribute them across = 100 nodes of network, 100 samples per node. We use two types of networks: a sequence of random geometric graphs with s 30, and a sequence which alternates between the ring and star topology, with x ~ 1, 000. We choose the regularization parameter μl such that the condition number becomes & = 10 We compare ADOM+ with multi-consensun with two state-of- the art decentralized algorithms for time-varying networks: Acc-GT with multi contei-s (Li and Lin 202T). and a variant of APM-C for time-varying
dataset
networks (Rogozin et al. 2020 Li al. [2018). We set all parameters of Acc-GT and APM-C to those used in the experimental sections of the corresponding papers, and tune the parameters of ADOM+ The results are presented in Figure 2 We that ADOM+ has similar empirical behavior to the recently proposed Acc-GT method. Both these methods are better than APM-C terms of the number of decentralized communication rounds (this is expected, since this method has sublinear communication complexity), and worse in terms of the number of gradient calls. We provide more details and additional experiments in the appendix.
Acknowledgments
The work of D. Kovalev, E. Gasanov and P. Richtárik supported by the KAUST Baseline Research Funding Scheme. The work of A. Gasnikov was supported by the Russian Science Foundation (project 21-71-30005). 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 (00000D73032IPSQMM Institute for System Programming of the Russian Academy of Sciences dated November 2, 2021 No. 70-2021-00142.
and the agreement with the Ivannikov
References
Bazerque, J. A. and Giannakis, G. B. (2009). Distributed spectrum sensing for cognitive radio networks by exploiting sparsity. IEEE Transactions Signal Processing, 1873).2877-186..
Beck, A., Nedić, A., Ozdaglar, A., and Teboulle, M. (2014). An o(1/k) gradient method for network
resource allocation problems. JEEE Transactions Control of Network Systems, 1(1):64-73.
Chang, C.-C. and Lin, C.-J. (2011). Libsvm: a library for support vector machines. ACM transactions intelligent systems and technology (TIST), 2(3):1-27.
Condat, L., Kitahara, D., Contreras, A., and Hirabayashi, A. (2019). Proximal splitting algorithms: tour of recent advances, with new twists. arXiv preprint arXiv: 192.0179/..00137
Dvinskikh, D. and Gasnikov, A. (2019), Decentralized and parallelized primal and dual accelerated methods for stochastic convex programming problems. arXiv preprint vrXiv:1904.000 09015.
Gan, L., Topeu, U., and Low, H. (2012). Optimal decentralized protocol for electric vehicle charging. IEEE Transactions Power Systems, 28(2)940-951.
Giselsson, P., Doan, M. D., Keviezky, T., De Schutter, B., and Rantzer, (2013). Accelerated gradient methods and dual decomposition in distributed model predictive control. Automatica, 49(3):829-833.
Gorbunov, E., Kovalev, D., Makarenko, D., and Richtárik, P. (2020). Linearly converging error compensated SGD. In Neural Information Processing Systems.
Karimireddy, S. P., Rebjock, Q., Stich, S., and Jaggi. M. (2019). Error feedback fixes SignSGD and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR.
'The LIBSVM (Chang and Lin 2011 dataset collection is available http::/wwwwww.i..t.eee....
10

---

Kolar, M., Song, L., Ahmed, A.. Xing, E. P., et al. (2010). Estimating time-vane tareiig networks. Annals of Applied Statistics, :(1):94-
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. (2016). Federated learning: Strategies for improving communication efficiency. arXiv preprint arxiv: 1610.05492.
Kovalev, D., Salim, A., and Richtárik, P. (2020). Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33.
Kovalev, D., Shulgin, E., Richtárik, P., Rogozin, A., and Gasnikov, (2021). ADOM: Accelerated decentralized optimization method for tine-varying networks. arXiv preprint arXiv:2102.09234.
Li, H., Fang. C., Yin, W., and Lin, Z. (2018). A sharp convergence rate analysis for distributed accelerated gradient methods. arXiv preprint arXiv: 181001003.
Li, H. and Lin, Z. (2021). Accelerated gradient tracking over time-varying graphs for decentralized optimization. arXiv preprint urXiv:2104.02590
Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. (2020). Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3)500-60.
Maros, M. and Jaldén, J. (2018). Panda: A dual linearly converging method for distributed optimiza- tion over time-varying undirected graphs. In 2018 IEEE Conference Decision and Control (CDC), pages 6520-6525. IEEE.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, (2017). Communication efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR.
Nedic, A., Olshevsky, A., and Shi, W. (2017). Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2633,
Nesterov, (2003). Introductory lectures on convex optimization: A basic course, volume 87.
Springer Science & Business Media.
Pu, S., Shi, W., Xu, J., and Nedic, A. (2020). Push-pull gradient methods for distributed optimization in networks, IEEE Transactions on Automatic Control.
Qu, G. and Li, N. (2019). Accelerated distributed nesterov gradient descent. IEEE Transactions on Automatic Control, 65(6):2566-2)
Rabbat, M. and Nowak, R. (2004). Distributed optimization sensor networks. In Proceedings of the 3rd International Symposium Information Processing in Sensor Networks, pages 20-27.
Rockafellar, R. T. (2015). Convex analysis. Princeton university press.
Rogozin, A., Lukoshkin, V., Gasnikov, A., Kovalev, D., and Shulgin, E. (2020). Towards accelerated rates for distributed optimization over time-varying networks. arXiv preprint 2rXiv: 10069.
Salim, A., Condat, I.., Kovalev, D., and Richtárik, P. (2021). An optimal algorithm for strongly convex minimization under affine constraints. arXiv preprint arXiv:2102.11079,
Salim, A., Condat, L., Mishchenko, K., and Richtárik, P. (2020). Dualize, split, randomize: fast nonsmooth optimization algorithms. arXiv preprint arXiv:2004.0263:
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L. (2017). Optimal algorithms for smooth and strongly convex distributed optimization in networks. In international conference machine learning, pages 3027-3036. PMLR.
Stich, S. U. and Karimireddy. S. P. (2019). The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv: /909009900035
Ye, H., Luo, L.,, Zhou, Z., and Zhang, T. (2020). Multi-consensus decentralized accelerated gradient descent. arXiv preprint arXiv:2005.00797.
Zadeh, L. A. (1961). Time-varying networks, i. Proceedings of the IRE, (00(10))14881111


Reviews:
[{"review_id": "rlVuczilo7", "reviewer": "Reviewer_isKt", "summary": "This work studies the problem of smooth and strongly convex decentralized optimization problems in time-varying networks and it is relevant to the conference. The paper provides both lower bound and optimal algorithms for decentralized optimization that combines several existing works, then apply them in time-varying networks. The paper prove its algorithm is optimal, in sense of the computation and communication complexity. There are some light experiments associated with the paper, thus the practical performance of the approach is somehow validated.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The main contribution of this paper is to offer both lower bound and rate optimal algorithms for smooth and strongly convex decentralized optimization problems in time-varying networks. The problem is well-motivated and the writing is clear. There are some light simulation results thus the proposed algorithm seems work from both the theory and simulations perspective.\n\nDecentralized distributed optimization in the strongly convex and smooth regime is relatively well studied. In particular, [1] established lower decentralized communication and local computation complexities for solving this problem, and proposed an optimal algorithm called MSDA in the case when an access to the dual oracle is assumed. Under a primal oracle, current state of the art includes the near-optimal algorithms [2], and a recently proposed optimal algorithm OPAPC [3]. The main contribution of this work is an extension of above works into time-varying networks. Thus the obtained lower bound is not surprise. Build up on that, the authors further introduce a rate optimal algorithm which match the rate of lower bound and the results are validated by light simulations. However, the simulation is based on logistic regression which is way too simple in current deep learning era. I don't see any points of an experiments using only 100 data points per node. \n\nIn short, the paper is technically sound and the developments are clear. The derived algorithm and rates seems to be a useful contribution to the literature on decentralized composite convex optimization, showing a modest improvement over the state of the art. ​However, the paper is still a combine-then-twist work based on top of several existing works and could be strengthened by demonstrating more significant results instead of incremental. It could be accepted if there is room, but should not warrant a strong accept due to the lack of novelty and experiments.\n\n[1] Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L. (2017). Optimal algorithms for smooth and strongly convex distributed optimization in networks. In international conference on machine learning, pages 3027–3036. PMLR.\n\n[2] Dvinskikh, D. and Gasnikov, A. (2019). Decentralized and parallelized primal and dual accelerated methods for stochastic convex programming problems. arXiv preprint arXiv:1904.09015.\n\n[3] Kovalev, D., Salim, A., and Richtárik, P. (2020). Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33.\n\n---\nafter thoroughly and carefully read the paper and response after rebuttal, the best I can do is to keep my score unchanged (if not lower it). Basically, the response said nothing, and the paper is a trivial combination work with only limited experimental results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Have the authors adequately addressed the limitations and potential negative societal impact of their work? \nYes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "iQDtwQr2Q1o", "reviewer": "Reviewer_jE4H", "summary": "This paper considers the problem of minimizing the finite-sum of smooth and strongly convex functions in decentralized time-varying networks. The authors establish the first lower bounds on the number of decentralized communication rounds and the number of local computations required to find an approximate solution. They also designed two optimal algorithms that attain these lower bounds. Experiment results of the proposed methods are also presented.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: The obtained result of lower bound is new, though its proof appears to be a straightforward extension of that in Scaman et al. (2017). The multi-concensus procedure is new to the best of my knowledge. \n\nQuality: The paper is technically sound. All the claims are equipped with solid proof. The technical results are correct.\n\nClarity: The paper is well written and organized. \n\nSignificance: I have some concerns on the significance and potential impact of this paper. First, the authors claim that the obtained lower bound is for time-varying networks, but I cannot see how the time-varying property plays a role in the main theorems. Also, what is the lower bound for time-invariant networks? In general, we are expecting the lower bound for time-varying networks to be larger than the lower bound for time-invariant networks, and we are interested in how the time-varying property affects the bound. Second, it is interesting to see that multi-consensus leads to optimal local computation rounds. However, it might be only of theoretical interest because it significantly increases the communication rounds (although the bound on communication rounds remains the same). Since in practice the communication cost is usually the bottleneck, the practical impact of multi-consensus strategy is rather limited. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no foreseeable negative societal impact of this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Sg78VxLWBd", "reviewer": "Reviewer_6mM6", "summary": "This paper studies the decentralized optimization ove time-varying networks. Lower bounds for smooth and strongly convex problems are proved at the first time and optimal algorithms that attain these lower bounds are provided.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: This paper establishes the first lower bounds for decentralized optimization over time-varying networks. The task is more challenging than the case of fixed network. I think it is a novel contribution. Optimal algorithms are provided which attain these lower bounds. The presented method ADOM+ is a novel extention of the one in Kovalev 2020. \n\nQuality: The theory is technically solid. Both lower bounds and upper bounds are provided. This is a complete work. The authors discuss both the strengths and weaknesses of the proposed methods.\n\nClarity: This paper is written well.\n\nSignificance: Decentralized optimization over time-varying networks is an important task in signal processing, automatic control, and federated learning. This paper provides the state-of-the-art results to this task. I think the contributions are important.\n\nComments:\n\n1. The third assumption on line 102 means that the elements of each column of W(q) sum to 0, which is equivalent to the assumption that I-W(q) is column stochastic. What about the rows? We often assume the double stochastic mixing matrices for undirected graphs, and column (or row) stochastic ones for directed graphs. I suggest the authors to check it carefully whether the row stochastic assumption is really avoided.\n \n2. The presented ADOM+ algorithm is not implementable because step 5 dependes on $y^{k+1}$, which is computed in step 8, whle step 8 dependes on $x^{k+1}$, which is computed in step 5. This is a little problem and can be easily addressed. However, I suggest to give a detailed explanation after the presentation of the algorithm.\n\n3. In the experiment, the authors only test the performance of ADOM+ with multi-consensus. According to my experience, the multi-consensus are not working in practice. I suggest to compare ADOM+ with multi-consensus, ADOM+ without multi-consensus, Acc-GT with multi-consensus, and Acc-GT without multi-consensus in the final version. This is not a compulsion in the rebuttal because the time is limited to redo the experiment.\n\n4. Both the ADOM+ algorithm and its analysis are complex. I have read the proof, but I cannot get the ideas. I suggest to provide more intuitions and explanations of the proofs.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper discusses the limitations in Section 5.3. I am interested in whether the primal-dual framework can be applied to nonstrongly convex problems. This may be another limination.", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "-dFWG5lbYBP", "reviewer": "Reviewer_qUuQ", "summary": "This paper studies a decentralized optimization problem. There is a set of nodes that collectively want to find the minimum of an objective function that is the sum of local costs. The nodes can communicate on underlying communication graph.  The authors study the trade-off communication v.s. precision. They show a lower bound on the quality of a solution that can be attained given a certain communication budget. They then provide two algorithms that attain this lower bound.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I must say that I have very limited knowledge on this topic so my review has to be taken with a grain of salt. Yet, I find the paper not easy to read in the many technical part. For instance, I am not sure to understand exactly what is the matrix $W(q)$ defined in section 2.4 and what are the implication of Equation (3) -> in section 5.1, it is written \"as discussed in Section 2.4, a decentralized communication round can be represented by a multiplication by [...] W(q)\". I would have appreciated more details there. On the other hand, I believe that some part can be shorten (what is the interest of Figure 1? Would not it be better to merge Theorem 2 and 3 into one?)\n\nThe lower bound (Theorem 1) seem to be the main contribution of the paper. The authors could comment on the impact of choosing $d=+\\infty$ here?  Would it change anything?\n\nThe algorithmic part is harder to understand for me. For instance, is it obvious that the multi-consensus algorithm falls into the category of algorithms used in the lower bound of Theorem 1? Also, the contribution with respect to ADOM (Kovalev et al 2021) is unclear.\n\nFinally, the results presented in the paper looks promising but lack details. For instance: what is shown on the y-axis of Figure 2?\n\n**Rebuttal** \nAfter reading the rebuttal, I am not convinced that the new version will be more accessible.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "To be more accessible to a non-expert like me, the assumption behind the communication model and the contribution with respect to related work could be better explained.", "review_text": "", "extra_scores": {"ethical_concerns": "NA.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a significant contribution to distributed optimization over time-varying networks. In particular it establishes a lower-bound on complexity  by identifying a specific pattern of time-varying networks, and proposes two schemes (one, ADOM+, requiring access to dual gradients, and another one avoiding the need to access such dual gradients) that are proven to match this lower bound. This thus gives a rather complete treatment of the problem of distributed convex optimization for time-varying networks as those considered in the paper. 
While the paper's analysis is made for specific assumptions (eg on the type of time varying networks) and the lower bound is of a worst-case nature, the authors clarified these points, and proposed to develop discussions of these and other points in the final version which should put the paper in a correct perspective. 
Decision: Accept (Poster)