Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
Year: 2022

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 the first lower bounds on the number of decentralized communication rounds and the number of local computations required to find an ε-accurate solution. Second, we design two 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.

heading: 1 Introduction
text: In this work we are solving the decentralized optimization problem
min x∈Rd n∑ i=1 fi(x), (1)
where each function fi : Rd → Rd is stored on a compute node i ∈ {1, . . . , n}. We assume that the 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 fi to be smooth and strongly convex.
Such decentralized optimization problems arise in many applications, including estimation by sensor networks (Rabbat and Nowak, 2004), network resource allocation (Beck et al., 2014), cooperative control (Giselsson et 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
∗King 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 (NeurIPS 2021).
learning models through empirical risk minimization from the data stored across the nodes of a network as a special case. Finally, while the current federated learning (Konečný et al., 2016; McMahan et al., 2017) systems rely on a star network topology, with a 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).

heading: 1.1 Time-varying Networks
text: 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 (Zadeh, 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 a similar regime will be supported in future-generation federated learning systems (Konečný et 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.

heading: 1.2 Contributions
text: 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 (1) over time-varying networks. Our results are summarized in Table 1, and detailed in Section 3 (see Theorems 2 and 3 therein).
2. Optimal algorithms. Further, we prove that these bounds are tight by providing two new optimal algorithms4 which match these lower bounds:
(i) a variant of the recently proposed algorithm ADOM (Kovalev et al., 2021) enhanced via a multi-consensus subroutine, and
(ii) a novel algorithm, called ADOM+ (Algorithm 1), also featuring multi-consensus. The former method is optimal in the case when access to the dual gradients is assumed, and the latter one is optimal in the case when access to the primal gradients is assumed. See Sections 4 and 5 for details. To the best of our knowledge, ADOM with multi-consensus is 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 in the appendix) we demonstrate that our methods are implementable, and that they perform competitively when compared to existing baseline methods APM-C (Rogozin et al., 2020; Li et al., 2018) and Acc-GT (Li and Lin, 2021).
Related Work. When the communication network is fixed in time, decentralized distributed optimization in the strongly convex and smooth regime is relatively well studied. In particular, Scaman et al. (2017) 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 a 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., 2020).
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 of Pu et al. (2020), that assume a 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
4As a byproduct of our lower bounds, we show that the recently proposed method Acc-GT of Li and Lin (2021) is also optimal. This method appeared on arXiv in April 2021, at the time when we already had a first draft of this paper, including all results. Their work does not offer any lower bounds.
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: a dual based algorithm ADOM (Kovalev et al., 2021), and a primal based algorithm Acc-GT (Li and Lin, 2021).

heading: 2 Notation and Assumptions

heading: 2.1 Smooth and Strongly Convex Regime
text: Throughout this paper we restrict each function fi(x) to be L-smooth and µ-strongly convex. That is, we require the following inequalities to hold for all x, y ∈ Rd and i ∈ {1, . . . , n}:
fi(y) + ⟨∇fi(y), x− y⟩+ µ2 ∥x− y∥ 2 ≤ fi(x) ≤ fi(y) + ⟨∇fi(y), x− y⟩+ L2 ∥x− y∥ 2. (2)
This naturally leads to the quantity κ = Lµ known as the condition number of function fi. Strong convexity implies that problem (1) has a unique solution.

heading: 2.2 Primal and Dual Oracle
text: In our work we consider two types of gradient oracles. By primal oracle we denote the situation when the gradients ∇fi of the objective functions fi are available. By dual oracle we denote the situation when the gradients ∇f∗i of the Fenchel conjugates5 f∗i of the objective functions fi are available.

heading: 2.3 Decentralized Communication
text: Let V = {1, . . . , n} denote the set of the compute nodes. We assume that decentralized communication is split into communication rounds. At each round q ∈ {0, 1, 2, . . .}, nodes are connected through a communication network represented by a graph Gq = (V, Eq), where Eq ⊂ {(i, j) ∈ V×V : i ̸= j} is the set of links at round q. For each node i ∈ V we consider a set of its immediate neighbors at round q: N qi = {j ∈ V : (i, j) ∈ Eq}. At round q, each node i ∈ V can communicate with nodes from the set N qi only. This type of communication is known in the literature as decentralized communication.
5Recall that the Fenchel conjugate of fi is given as f∗i (x) = supy∈Rd [⟨x, y⟩ − fi(y)]. Note, that f∗i is 1/µ-smooth and 1/L-strongly convex (Rockafellar, 2015).

heading: 2.4 Gossip Matrices
text: Decentralized communication between nodes is typically represented via a matrix-vector multiplication with a gossip matrix. For each decentralized communication round q ∈ {0, 1, 2, . . .}, consider a matrix W(q) ∈ Rn×n satisfying the following assumption. Assumption 1. For any q ∈ {0, 1, 2, . . .} matrix W(q) ∈ Rn×n satisfies the following relations:
1. W(q)i,j = 0 if i ̸= j and (i, j) /∈ Eq ,
2. kerW(q) ⊃ {(x1, . . . , xn) ∈ Rn : x1 = . . . = xn}, 3. rangeW(q) ⊂ {(x1, . . . , xn) ∈ Rn : ∑n i=1 xi = 0},
4. There exists χ ≥ 1, such that ∥Wx− x∥2 ≤ (1− χ−1)∥x∥2 for all x ∈ {(x1, . . . , xn) ∈ Rn : ∑n i=1 xi = 0} . (3)
Throughout this paper we will refer to the matrix W(q) as the gossip matrix. A typical example of a gossip matrix is W(q) = λ−1max(L(q)) · L(q), where L(q) the Laplacian of an undirected connected graph Gq . Note that in this case W(q) is symmetric and positive semi-definite, and χ can be chosen as an upper-bound on the condition number of the matrix L(q) defined by χ = supq λmax(L(q))
λ+min(L(q)) ,
where λmax(L(q)) and λ+min(L(q)) denote the largest and the smallest positive eigenvalue of L(q), respectively. With a slight abuse of language, we will call χ the condition number of time-varying network even when the gossip matrices W(q) are not necessarily symmetric.
While the notion of a gossip matrix is typically used in 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, it turns out that there is 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.

heading: 3 Lower Complexity Bounds
text: In this section we obtain lower bounds on the decentralized communication and local computation complexities for solving problem (1). These lower bounds apply to algorithms which belong to a certain class, which we call First-order Decentralized Algorithms. Algorithms from this class need to satisfy the following assumptions:
1. Each compute node can calculate first-order characteristics, such as gradient of the function it stores, or its Fenchel conjugate.
2. Each compute node can communicate values, such as vectors from Rd, with its neighbors. Note that the set of neighbors for each node is not fixed in 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. (2017).

heading: 3.1 First-order Decentralized Algorithms
text: Here we give a formal definition of the class of algorithms for which we provide lower bounds on the complexity of solving problem (1). At each time step k ∈ {0, 1, 2, . . .}, each node i ∈ V maintains a finite local memory Hi(k) ⊂ Rd. For simplicity, we assume that the local memory is initialized as Hi(k) = {0}. At each time step k, an algorithm either performs a decentralized communication round, or a local computation round that can update the memory Hi(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 Hi(k + 1) ⊂ Span({x,∇fi(x),∇f∗i (x) : x ∈ Hi(k)})
for all i ∈ V , where f∗i is the Fenchel conjugate of fi.
2. If an algorithm performs a decentralized communication round at time step k, then Hi(k + 1) ⊂ Span ( ∪j∈N qi ∪{i}Hj(k) ) for all i ∈ V , where q ∈ {0, 1, 2, . . .} refers to the number of decentralized communication round performed so far, counting from the first one, for which we set q = 0. See Figure 1 for a graphical illustration of our time step (k) and decentralized communication (q) counters.
At time step k, each node i ∈ V must specify an output value xoi (k) ∈ Hi(k). In the case of time-invariant networks, Scaman et al. (2017) presented lower complexity bounds for a class of algorithms called Black-box Optimization Procedures. This class is slightly more general than our First-order Decentralized Algorithms. In particular, we use discrete time k ∈ {0, 1, 2, . . .} 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 of our work, since our results can be easily extended to Black-box Optimization Procedures. However, we are of the opinion that such an extension would not give any new substantial insights.

heading: 3.2 Main Theorems
text: We are now ready to present our 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 (1). In order to simplify the proofs, and following the approach used by Nesterov (2003), we consider the limiting case d → +∞. More precisely, we will work in the infinite dimensional space ℓ2 = { x = (x[l]) ∞ l=1 : ∑∞ l=1(x[l]) 2 < +∞ }
rather than Rd. Theorem 1. Let χ ≥ 3, L > µ ≥ 0. There exists a sequence of graphs {Gq}∞q=0, a corresponding sequence of gossip matrices {W(q)}∞q=0 ⊂ Rn×n satisfying the Assumption 1, and µ-strongly convex and L-smooth functions fi : ℓ2 → R, i ∈ V , such that for any first-order decentralized algorithm and any k ∈ {0, 1, 2 . . .}
∥xoi (k)− x∗∥2 ≥ C ( max { 0, 1− 24 √ 6µ√ L })q/χ , (4)
where q is the number of decentralized communication rounds performed by the algorithm before time step k, x∗ is the solution of the problem (1) and C > 0 is some constant.
Our proof is inspired by the proof of Scaman et al. (2017) for time-invariant networks, which in its turn is based on the proof of oracle complexities for strongly convex and smooth optimization by Nesterov (2003). Here we give a short outline of our proof.
We choose n = |V| ≈ χ nodes and split them into three disjoint sets, V1,V2 and V3, of equal size n/3. Further, we split the function used by Nesterov (2003) onto the nodes belonging to V1 and V3. One then needs to show that most dimensions of the output vectors xoi (k) will remain zero, while local computations may only increase the number of non-zero dimensions by one. In contrast to (Scaman et al., 2017), we need to have |V2| ≈ χ rather than |V2| ≈ √ χ, and still ensure that at least |V2| decentralized communication rounds are necessary to share information between node groups V1 and V3. We achieve this by choosing a sequence of star graphs with the center node cycling through the nodes from V2. Theorem 2. For any χ ≥ 3, L > µ ≥ 0 there exists a sequence of graphs {Gq}∞q=0, a corresponding sequence of gossip matrices {W(q)}∞q=0 ⊂ Rn×n satisfying the Assumption 1, and µ-strongly convex
and L-smooth functions fi : ℓ2 → R, i ∈ V , such that for any first order decentralized algorithm, the number of decentralized communication rounds to find an ϵ-accurate solution of the problem (1) is lower bounded by
Ω ( χ √
L/µ log 1ϵ
) . (5)
We also provide a lower bound on the local computation complexity. The proof is similar to the proof of Theorem 1. Theorem 3. For any χ ≥ 3, L > µ ≥ 0 there exists a sequence of graphs {Gq}∞q=0, a corresponding sequence of gossip matrices {W(q)}∞q=0 ⊂ Rn×n satisfying the Assumption 1, and µ-strongly convex and L-smooth functions fi : ℓ2 → R, i ∈ V , such that for any first order decentralized algorithm, the number of local computation rounds to find an ϵ-accurate solution of the problem (1) is lower bounded by
Ω (√
L/µ log 1ϵ
) . (6)
The detailed proofs are available in the appendix.

heading: 4 Primal Algorithm with Optimal Communication Complexity
text: In this section we develop a novel algorithm for decentralized optimization over time-varying networks with optimal decentralized communication complexity. This is a primal algorithm, meaning that it uses the primal gradient oracle. The design of this algorithm relies on a sequence of specific reformulations of the problem (1), which we now describe.

heading: 4.1 Reformulation via Lifting
text: Consider a function F : (Rd)V → R defined by F (x) = ∑ i∈V fi(xi), (7)
where x = (x1, . . . , xn) ∈ (Rd)V . This function is L-smooth and µ-strongly convex since the individual functions fi are. Consider also the so called consensus space L ⊂ (Rd)V defined by
L = {(x1, . . . , xn) ∈ (Rd)V : x1 = . . . = xn}. (8)
Using this notation, we arrive at the equivalent formulation of problem (1)
min x∈L F (x). (9)
Due to strong convexity, this reformulation has a unique solution, which we denote as x∗ ∈ L.

heading: 4.2 Saddle Point Reformulation
text: Next, we introduce a reformulation of problem (9) using a parameter ν ∈ (0, µ) and a slack variable w ∈ (Rd)V :
min x,w∈(Rd)V w=x,w∈L
F (x)− ν2∥x∥ 2 + ν2∥w∥ 2.
Note that the function F (x)− ν2∥x∥ 2 is (µ− ν)-strongly convex since ν < µ. The latter problem is a minimization problem with linear constraints. Hence, it has the equivalent saddle-point reformulation
min x,w∈(Rd)V max y∈(Rd)V max z∈L⊥
F (x)− ν2∥x∥ 2 + ν2∥w∥ 2 + ⟨y, w − x⟩+ ⟨z, w⟩,
where L⊥ ⊂ (Rd)V is an orthogonal complement to the space L, defined by L⊥ = {(z1 . . . , zn) ∈ (Rd)V : ∑n i=1zi = 0}. (10)
Minimization in w gives the final saddle-point reformulation of the problem (9):
min x∈(Rd)V max y∈(Rd)V max z∈L⊥
F (x)− ν2∥x∥ 2 − ⟨y, x⟩ − 12ν ∥y + z∥ 2. (11)
Further, by E we denote the Euclidean space E = (Rd)V × (Rd)V × L⊥. One can show that the saddle-point problem (11) has a unique solution (x∗, y∗, z∗) ∈ E, which satisfies the following optimality conditions:
0 = ∇F (x∗)− νx∗ − y∗, (12) 0 = ν−1(y∗ + z∗) + x∗, (13) L ∋ y∗ + z∗. (14)

heading: 4.3 Monotone Inclusion Reformulation
text: Consider two monotone operators A,B : E → E, defined via
A(x, y, z) = ∇F (x)− νxν−1(y + z) Pν−1(y + z)  , B(x, y, z) = [−yx 0 ] , (15)
where P is an orthogonal projection matrix onto the subspace L⊥. Matrix P is given as
P = (In − 1n1n1 ⊤ n )⊗ Id, (16)
where Ip denotes p × p identity matrix, 1n = (1, . . . , 1) ∈ Rn, and ⊗ is the Kronecker product. Then, solving problem (11) is equivalent to finding (x∗, y∗, z∗) ∈ E, such that
A(x∗, y∗, z∗) +B(x∗, y∗, z∗) = 0. (17)
Indeed, optimality condition (14) is equivalent to projL⊥(y ∗+z∗) = 0 or Pν−1(y∗+z∗) = 0. Now, it is clear that (17) is just another way to write the optimality conditions for problem (11).

heading: 4.4 Primal Algorithm Design and Convergence
text: A common approach to solving problem (17) is to use the Forward-Backward algorithm. The update rule of this algorithm is (x+, y+, z+) = JωB [(x, y, z) − ωA(x, y, z)], where ω > 0 is a stepsize, the operator JωB : E → E is called the resolvent, and is defined as the inverse of the operator (I + ωB) : E → E, where I : E → E is the identity mapping. One can observe that the resolvent JωB is easy to compute.
Following (Kovalev et al., 2020), we use an accelerated version of the Forward-Backward algorithm. This can indeed be done, since the operator A : E → E is the gradient of the smooth and convex function (x, y, z) 7→ F (x)− ν2∥x∥ 2 + 12ν ∥y + z∥ 2 on the Euclidean space E. Note that the operator A + B is not strongly monotone, while strong monotonicity is usually required to achieve linear convergence. However, we can still obtain a linear convergence rate by carefully utilizing the L-smoothness property of the function F (x). Similar issue appeared in the design of algorithms for solving linearly-constrained minimizations problems, including the non-accelerated algorithms (Condat et al., 2019; Salim et al., 2020) and the optimal algorithm (Salim et al., 2021). However, the authors of these works considered a different problem reformulation from (11), and hence their results can not be applied here.
However, one issue still remains: to compute the operator A, it is necessary to perform a matrixvector 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 it with the multiplication via the gossip matrix W(q)⊗ Id, which requires one decentralized communication round only. That is, we replace the last component Pν−1(y + z) of the operator A defined by (15) with (W(q) ⊗ Id)ν−1(y + z). Kovalev et al. (2021) showed that multiplication with the gossip matrix can be seen as a compression on 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 et al., 2020) can be applied to obtain linear convergence. We use this insight in the design of our algorithm.
Armed with all these ideas, we are ready to present our method ADOM+; see Algorithm 1.
Algorithm 1 ADOM+ 1: input: x0, y0,m0 ∈ (Rd)V , z0 ∈ L⊥ 2: x0f = x 0, y0f = y 0, z0f = z 0
3: for k = 0, 1, 2, . . . do 4: xkg = τ1x
k + (1− τ1)xkf 5: xk+1 = xk + ηα(xkg − xk+1)− η [ ∇F (xkg)− νxkg − yk+1 ] 6: xk+1f = x k g + τ2(x
k+1 − xk) 7: ykg = σ1y
k + (1− σ1)ykf 8: yk+1 = yk + θβ(∇F (xkg)− νxkg − yk+1)− θ [ ν−1(ykg + z k g ) + x k+1 ] 9: yk+1f = y k g + σ2(y
k+1 − yk) 10: zkg = σ1z
k + (1− σ1)zkf 11: zk+1 = zk + γδ(zkg − zk)− (W(k)⊗ Id) [ γν−1(ykg + z k g ) +m k ] 12: mk+1 = γν−1(ykg + z k g ) +m k − (W(k)⊗ Id) [ γν−1(ykg + z k g ) +m k ] 13: zk+1f = z k g − ζ(W(k)⊗ Id)(ykg + zkg ) 14: end for
We now establish the convergence rate of Algorithm 1. Theorem 4 (Convergence of ADOM+). To reach precision ∥xk − x∗∥2 ≤ ϵ, Algorithm 1 requires the following number of iterations
O ( χ √
L/µ log 1ϵ
) .
Note that Algorithm 1 performs O(1) decentralized communication and local computation rounds. Hence, its decentralized communication and local computation complexities are O ( χ √
L/µ log 1ϵ
) .

heading: 5 Optimal Algorithms
text: 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 is to incorporate the multi-consensus procedure into the algorithms with optimal decentralized communication complexity.

heading: 5.1 Multi-consensus Procedure
text: As discussed in Section 2.4, a decentralized communication round cab be represented as the multiplication with the gossip matrix W(q). The main idea behind the multi-consensus procedure is to replace the matrix W(q) with another matrix, namely
W(k;T ) = In − (k+1)T−1∏
q=kT
(In −W(q)), (18)
where k ∈ {0, 1, 2, . . .} is the iteration counter, and T ∈ {1, 2, . . .} is the number of consensus steps. One can show that this matrix satisfies the Assumption 1, including the contraction property (3):
∥W(k;T )x− x∥2 ≤ (1− χ−1)T ∥x∥2 for all x ∈ L⊥. (19)
One can also observe that multiplication with the matrix W(k;T ) requires to perform multiplication with T gossip matrices W(kT ),W(kT +1), . . . ,W(kT +T −1), hence it requires T decentralized communication rounds.

heading: 5.2 Optimal Algorithms: ADOM and ADOM+ with multi-consensus
text: Now, we are ready to describe our optimal algorithms for smooth and strongly decentralized optimization over time-varying networks. As mentioned before, we start with algorithms with optimal
decentralized communication complexity. In the case when access to the primal oracle is assumed, ADOM+ (Algorithm 1) is 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) to be symmetric. However, the generalization of this proof to the case when the gossip matrix satisfies Assumption 1, and is not necessarily symmetric, is straightforward.
Both ADOM and ADOM+ require O ( χ √
L/µ log 1ϵ
) iterations to obtain an ϵ-accurate solution of
problem (1), and at each iteration they perform O(1) local computation and decentralized communication rounds, i.e., multiplications with the gossip matrix W(q). We now incorporate a multi-consensus procedure into both algorithms. That is, we replace matrix W(q) with the matrix W(k;T ) defined in (18), where k ∈ {0, 1, 2, . . .} is the iteration counter. As mentioned before, this is equivalent to performing O(T ) decentralized communication rounds at each iteration. Choosing the number of consensus steps T = ⌈χ ln 2⌉ together with (19) implies
∥W(k;T )x− x∥2 ≤ 12∥x∥ 2 for all x ∈ L⊥. (20)
This means that W(k;T ) satisfies (3) with χ replaced by 12 and hence both ADOM and ADOM+ with multi-consensus require O (√
L/µ log 1ϵ
) iterations to obtain an ϵ-accurate solution. Taking into
account that these algorithms still perform O(1) local computations and O(T ) = O(χ) decentralized communication rounds at each iteration, we arrive at the following theorems.
Theorem 5. Let the functions f1, . . . , fn be L-smooth and µ-strongly convex and let the Assumption 1 hold. Then, ADOM with multi-consensus requires O (√ L/µ log 1ϵ ) local computation rounds
and O ( χ √
L/µ log 1ϵ
) decentralized communication rounds to find an ϵ-accurate solution of the
distributed optimization problem (1).
Theorem 6. Let the functions f1, . . . , fn be L-smooth and µ-strongly convex and let the Assumption 1 hold. Then, ADOM+ with multi-consensus requires O (√ L/µ log 1ϵ ) local computation rounds
and O ( χ √
L/µ log 1ϵ
) decentralized communication rounds to find an ϵ-accurate solution of the
distributed optimization problem (1).

heading: 5.3 Comparison with Acc-GT (Li and Lin, 2021)
text: To the best of our knowledge ADOM with multi-consensus 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-consensus, there is 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 is not used, its iteration complexity is O ( χ3/2 √ L/µ log 1ϵ ) , which is worse than the complexity of ADOM+, by the factor χ1/2. Since communication is known to be the main bottleneck in distributed training systems, multi-consensus is unlikely to be used in practice, which may limit the practical performance of Acc-GT in comparison to ADOM+.

heading: 6 Experiments
text: In this section we perform an illustrative experiment with logistic regression. We take 10, 000 samples from the covtype LIBSVM6 dataset and distribute them across n = 100 nodes of a network, 100 samples per node. We use two types of networks: a sequence of random geometric graphs with χ ≈ 30, and a sequence which alternates between the ring and star topology, with χ ≈ 1, 000. We choose the regularization parameter µ such that the condition number becomes κ = 105. We compare ADOM+ with multi-consensus with two state-of-the art decentralized algorithms for time-varying networks: Acc-GT with multi-consensus (Li and Lin, 2021), and a variant of APM-C for time-varying networks (Rogozin et al., 2020; Li et 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 see that ADOM+ has similar empirical behavior to the recently proposed Acc-GT method. Both these methods are better than APM-C in 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.

heading: Acknowledgments
text: The work of D. Kovalev, E. Gasanov and P. Richtárik was supported by the KAUST Baseline Research Funding Scheme. The work of A. Gasnikov was supported by the Russian Science Foundation (project 21-71-30005), a 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 000000D730321P5Q0002 ) and the agreement with the Ivannikov Institute for System Programming of the Russian Academy of Sciences dated November 2, 2021 No. 70-2021-00142.

Review summaries:
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. 

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.

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.