arXiv CSopen access

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization Demyan Yarmoshik #  MIRAI, Russia

Maxim Klimenko # MIPT, Russia

arXiv:2606.12675v1 [math.OC] 10 Jun 2026

Abstract We study the communication complexity of convex decentralized optimization over time-varying networks, where n nodes hold private functions and must agree on the global minimizer using only synchronous exchanges with neighbors. The cost is the number of communication rounds to reach accuracy ε – a measure akin to round complexity in the LOCAL model, but constrained   √ by nodes sharing only oracle responses. We prove a new lower bound of Ω χG κg log χnG log 1ε communication rounds, where χG is the condition number of the network Laplacians and κg that of the global objective, showing the round complexity attainable under uniform regularity cannot be matched in the nonuniform regime. The construction rests on spectral graph theory: we embed time-rotating star gadgets into the edges of an expander and patch them to preserve spectral connectivity. 2012 ACM Subject Classification Theory of computation → Distributed algorithms; Theory of computation → Convex optimization Keywords and phrases Decentralized optimization, Lower bounds, Time-varying graphs

1

Introduction

Decentralized optimization is an active research direction in machine learning and distributed computing. The area’s core problem is to minimize the sum of locally stored functions fi n

1X fi (x), x∈Rd n i=1 min

(1)

by means of peer-to-peer communications. These functions are stored by the nodes of the communication network, whose edges can change over time. Problem (1) is usually called the consensus optimization problem, since all nodes must find the same global minimizer x∗ up to desired accuracy. The problem can, for example, represent federated learning tasks, in which multiple independent parties aim to train a common model’s parameters x on the combined set of data from all parties without actually sharing the data. In that case fi (x) is the empirical loss over the training samples in the i-th party’s private dataset. Theoretical analysis of distributed algorithms usually focuses on communication complexity, which is the number of synchronous communication rounds (e.g. gradient transfers) between all adjacent computation nodes, and computation complexity, which is abstracted by the number of oracle calls (e.g. computations of gradients ∇fi (xi ) at each node). While the notion of communication complexity reveals similarities with the LOCAL model, in decentralized optimization nodes are not allowed to share all information about their functions fi . They can only exchange the oracle’s responses to their queries and results of arithmetic manipulations of these responses. We formally define the computation model in Section 3.2. So-called centralized distributed algorithms, which utilize a central parameter-server (star communication topology) or all-reduce communication schemes, converge at a rate depending

2

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

on the global condition number κg = Lg /µg of the objective. This parameter quantifies Pn the ratio between the rates at which the global objective n1 i=1 fi (x) changes in different directions, using global smoothness Lg and strong convexity µg parameters, see definitions in Section 3.1. When a problem is parametrized by the global parameters κg , Lg , µg , we call this the nonuniform setup, since it does not impose uniform restrictions on properties of functions fi . In contrast, decentralized algorithms usually depend on the local condition number κl = Ll /µl which is the ratio of the worst (largest) smoothness parameter Ll and the worst (smallest) strong convexity parameter µl over all local objective functions fi . In general, a globally µg -strongly convex objective can have non-convex local terms fi , thus µl can be infinitely worse than µg . The same holds for the smoothness parameters Lg , Ll , therefore the local condition number κl can be arbitrarily larger than the global condition number κg , or can even be undefined. This motivates the search for decentralized algorithms whose complexity is parametrized by κg instead of κl .

1.1

Contribution

In this work we establish a new lower bound on the communication complexity of distributed algorithms over time-varying communication networks with smooth, strongly convex deterministic objectives. ▶ Theorem 1. For any network condition number χG ≥ 8861 , global objective condition number κg > 1, and accuracy ε > 0, there is a decentralized optimization problem on n ≥ 4χG nodes such that the communication complexity of any distributed algorithm is lower bounded as   n 1 √ NG = Ω χG κg log log . (2) χG ε While there are decentralized algorithms that partially replace the dependence on κl with κg , until recently there were no tighter communication complexity lower bounds for the nonuniform setup. A brief note [13] announced an improved lower bound NG =  √ Ω χG κg log LLgl log 1ε for nonuniform decentralized optimization in static communication
√ networks, showing that optimal complexity in uniform setup NG = O χG κg log 1ε [30] is not achievable in the nonuniform model. We provide the same impossibility result for  time-varying networks. Lower bound (2) can  √ Ll 1 also be restated as NG = Ω χG κg log Lg log ε , matching the result of [13] up to a square
√ root of χG , which corresponds to the optimal complexity NG = O χG κg log 1ε of uniform decentralized optimization on time-varying graphs [12]. The construction of our lower bound is based on expander graphs and spectral graph theory, which differs from classical lower bounds for the uniform setup that rely on trivial path and star graph constructions [30, 12, 31]. The idea of using expander graphs to introduce a log n dependence on the number of nodes into communication lower bounds was also mentioned in a blogpost of S. Bubeck2 accompanying [30]. That argument, however, only √ yields a lower bound of the form Ω(max{ χG , log n}), whereas both [13] and the present

1

In the complementary regime χG ∈ (1, 886) the factor χG in the bound is bounded by an absolute constant; this range can be covered by a separate construction tailored to this case, which we omit since it does not affect the asymptotic lower bound. 2 https://blogs.princeton.edu/imabandit/2017/07/05/smooth-distributed-convex-optimization/.

D. Yarmoshik and M. Klimenko

3

√ work obtain the stronger multiplicative bounds Ω( χG log n) and Ω(χG log n), respectively, which require more involved graph-theoretical analysis.

2

Related Work

Minimizing communication complexity is in high demand among practitioners training large models. The performance of this essentially distributed process is often limited by network capacity [18], motivating the development of communication compression techniques [32, 27, 3] and optimization of communication schemes [4, 15, 19, 39]. Decentralized optimization is an approach to this problem which is rooted in gossip consensus algorithms [24, 25, 9]. The framework of decentralized algorithms utilizes communication matrices (or gossip matrices) W for the atomic communication operation of taking P a weighted sum of vectors from immediate neighbors: vi = j:(i,j)∈EG Wij vj . This approach is favorable due to its simplicity of implementation and robustness, which allow it to be generalized to the time-varying setup, where edges in the communication graph can change between communication rounds [12, 23, 29]. The standard model of communication complexity in decentralized optimization simply counts the number of communication rounds required to solve a problem for a given accuracy [9, 38, 30]. Up to privacy constraints, this is similar to the LOCAL model [20, 28]. Our model captures only a structural form of privacy: a node never shares its function fi directly, but exposes oracle responses. A stronger, quantitative notion is differential privacy [7, 8], which additionally bounds how much the shared responses can reveal about any individual data point and has been studied for decentralized learning [1]. While no major works on decentralized optimization seem to mention the connection, there are explicit comparisons of the LOCAL and “gossip” models in the literature on distributed bandits and reinforcement learning [6, 33, 16]. There are also more practical network models where communication time depends on heterogeneous link delays and/or bandwidths [21, 35]. In the standard communication-round model there is a well-established complexity theory for both static and time-varying setups with matching upper and lower bounds in many setups [30, 12, 31, 37, 11, 36, 17]. Yet there is a gap in communication complexity in the nonuniform smooth and strongly convex setup. A prominent result here   is the Mudag √ Lg Ll 1 algorithm [38], which achieves NG = O χG κg log Lg + log µg log ε communication complexity. Comparing with the optimal complexity of first-order decentralized algorithms
√ in the uniform setup O χG κl log 1ε [30, 14], we see that Mudag is optimal up to the L log LLgl + log µgg term. It was recently shown [13] that the log LLgl term cannot be removed. We extend this result to the case of time-varying communication networks.

3

Preliminaries

3.1

Basic Definitions

Communication graphs. By λi (G) we denote the i-th eigenvalue of the Laplacian LG of graph G = (VG , EG ), |VG | = n, so that λ2 (G) and λn (G) are the minimum nonzero and maximum eigenvalues respectively. AG denotes the adjacency matrix of G. EG (S, T ) denotes the set of edges between S ⊂ VG and T ⊂ VG in graph G. Smoothness and strong convexity. A differentiable function h : Rd → R is called L-smooth if its gradient is L-Lipschitz continuous: ∥∇h(x) − ∇h(y)∥ ≤ L ∥x − y∥ ,

∀x, y ∈ Rd ,

(3)

4

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

and µ-strongly convex if for all x, y ∈ Rd , h(y) ≥ h(x) + ⟨∇h(x), y − x⟩ +

µ 2 ∥y − x∥ . 2

(4)

If h is twice continuously differentiable, equivalent definitions are L = supx λmax (∇2 h(x)) and µ = inf x λmin (∇2 h(x)). We denote by Li , µi the smoothness and strong convexity constants of fi , Ll = maxi∈[n] Li , µl = mini∈[n] µi , and by Lg , µg the corresponding constants of f . If µg > 0 then the minimizer x∗ of (1) is unique. Time-varying communication matrices. Communication rounds are indexed by t = 1, 2, . . . and are associated with a (finite or infinite) sequence of undirected connected graphs G = {G(t) }t≥1 on the same node set of size n. For each communication graph G(t) we are given a compatible communication matrix W (t) , i.e. W (t) is symmetric positive semidefinite; (t) Wij > 0 ⇒ (i, j) ∈ E(G(t) ); ker W (t) = span({1n }). For our lower bound we will set W (t) =LG(t) . We assume uniform spectral bounds for communication matrices: there exist λ > 0 and λ̄ < ∞ such that for all t,         (5) λmin+ W (t) = λ2 G(t) ≥ λ, λmax W (t) = λn G(t) ≤ λ̄. We denote the condition number of the sequence of graphs as χG = λ̄/λ. For a fixed graph G we also write χG =λn (G)/λ2 (G). ε-solution. We say that {xki ∈ Mi,k }ni=1 is an ε-solution of (1) if max xki − x∗ ≤ ε.

(6)

i∈[n]

We introduce the notion of infection as an intuitive reference to the information spread. In our worst-case problem a distributed algorithm cannot improve approximate solution at any node until information obtained via computation round in one node reaches another node. To measure communication complexity we will track the number of communication rounds (or infection steps) required to spread the infection by bounding an effective distance. Formally, we define effective distance ρ(S, T ) between node subsets S, T in a sequence of graphs G, s, t ∈ V (G) as the minimal number of communication rounds that is enough to spread infection from any s ∈ S to any t ∈ T . A similar notion was also introduced in [23] under the name of information flow.

3.2

Computation Model

Decentralized first-order algorithms. We use the standard first-order oracle model [30], closely related to the class of zero-respecting algorithms [5]. Each node i ∈ [n] maintains a memory set Mi,k ⊂ Rd . Initially, each node has the same starting point, without loss of generality we assume it to be the zero vector: Mi,0 = {0d }. At step k a decentralized first-order algorithm performs either a local first-order computation at every node,   Mi,k+1 = span Mi,k ∪ {∇fi (x) : x ∈ Mi,k } , (7) or a communication round t in which every node updates its memory with its neighbors’ memory using communication matrix    n X  (t) Mi,k+1 = span Mi,k ∪ Wij xj : xj ∈ Mj,k  . (8)   j=1

D. Yarmoshik and M. Klimenko

5

The number of communication rounds is denoted by NG . Actually, we will bound communication complexity of more general distributed first-order algorithms, which are not restricted by a communication matrix during the communication step:      [ Mi,k+1 = span Mi,k ∪ Mj,k  . (9)   (t) j:(i,j)∈E(G

)

This model of communication complexity is reminiscent of the round complexity of the LOCAL model, familiar in distributed computing, with one defining distinction. In LOCAL the nodes may exchange arbitrary messages, so within a number of rounds equal to the graph diameter every node can learn the entire topology together with all inputs, and the round complexity of any problem is bounded by O(n). In our model the nodes are restricted to sharing oracle responses and their linear combinations (8)–(9), which cannot reveal the local functions fi in full. Consequently the communication complexity is no longer bounded by the number of vertices: as our lower bound (2) shows, NG can substantially exceed n, since √ the factors κg and log 1ε grow independently of the network size.

4

Main Result

A worst-case communication network for the time-varying setup under the assumption of local Ll -smoothness and µl -strong convexity is a star graph whose center changes cyclically at each communication round over a subset of intermediate vertices [12]. We extend the corresponding lower bound on communication complexity for the nonuniform strongly convex setup (the stricter µl -assumption is relaxed to the more general µg -assumption) by embedding the star construction into each edge of an expander graph and applying an edge patch procedure using another expander graph on top of this to neutralize the reduction of spectral connectivity. This approach follows the idea of the lower bound for static graphs [13], where each edge √ of an expander graph was replaced with the path of length Ω( χG ). However, we cannot directly follow this approach for time-varying setup: replacing each edge with a star not only reduces the spectral connectivity λ proportionally to the increase in diameter, but also √ increases maximum degree (related to λ̄), leading to the same ∆(G) = Ω( χG ) relation as in the static case. To achieve the desired ∆(G) = Ω(χG ) relation, we develop the edge patch technique which restores spectral connectivity without harming the maximum degree.

4.1

Graph Construction

To construct a sequence of communication graphs, we take a (d = 8)-regular Margulis expander H on |VH | = m2 ∼ LLgl vertices [10, Theorem 8.2]. Since the condition number of the Laplacian matrix of the graph H does not depend on m, in order to obtain a lower bound in terms of χ we construct, based on the graph H, its τ -star extension G0 , in which each edge (v, w) is replaced by a star graph consisting of the leaves v, w and τ additional new vertices. To slow down the infection process (information spread), when the star center is infected, we replace the center with an uninfected leaf by changing the edges as shown in Figure 1. Consider vertices s, t ∈ VH whose distance in the graph H is equal to its diameter ∆(H). This construction guarantees that in order to transmit information from s to t at least (τ + 1)∆(H) communication rounds are required. Indeed, to transmit information from vertex v to vertex w such that (v, w) ∈ EH , two consecutive communications with the same central vertex are needed, which requires τ + 1 communication rounds / infection steps.

6

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

1

v

v

w

2

(a) Original edge

2

3

4

5

(b) Before infection step

1

v

3

w

w

4

5

(c) After infection step

2

v

1

3

w

4

5

(d) Center replacement

Figure 1 τ -star extension construction for τ = 5. (a) Edge (v, w) of the initial graph H. (b,c) Infection step in the star subgraph of G0 embedded in edge (v, w). (d) Infected center 1 is replaced with uninfected leaf 2 to delay infection of w.

Denote by n = |VG0 | = |VH |(1 + dτ /2) the number of nodes in graph G0 as well as in graphs G1 and G, which will be built on the same node set. Let U ⊂ VG be the subset of infected nodes, and define UH as its restriction on the nodes from H. Define ∂G0 U = B ⊂ Ū the set of nodes that will be infected at the next step (node boundary of U in G0 ), see Figure 2.

4.1.1

Patch Procedure

The patch procedure G0 → G adds edges to G0 to increase its spectral connectivity without supporting infection spread. Let F be an expander on VG0 with maximum degree dF . Define G1 = (VG0 , EG0 ∪ EF ). An edge (v, w) ∈ EF is called bad if it extends node boundary, i.e. v ∈ U , w ∈ Ū \ B. Construct G by replacing each bad edge (v, w) with two edges (v, b), (b, w), where nodes b ∈ B are assigned to bad edges uniformly, e.g., in a cyclic order. ▷ Claim 2. Any (not necessarily uniform) assignment of nodes b to bad edges does not decrease the size of any edge cut: |EG (A, Ā)| ≥ |EG1 (A, Ā)| ∀A ⊂ VG . Proof. EG1 (A, Ā) \ EG (A, Ā) includes only bad edges (v, w) : v ∈ U , w ∈ Ū \ B. Since each bad edge (v, w) ∈ EG1 is replaced with two new edges (v, b), (b, w) ∈ G (parallel edges allowed), the loss of (v, w) in EG1 (A, Ā) is either compensated by (v, b) if b ∈ Ā, or by (b, w) otherwise. ◀ F ▷ Claim 3. max deg(G) ≤ d + 32 dF + (dτ + 2) λ2d(H) + 1.

Proof. We begin with a lower bound on the number of nodes in the boundary B. By the isoperimetric inequality [34, Theorem 20.1.1] applied to the smaller side of the cut (UH , ŪH ),

|B| = |EH (UH , ŪH )| ≥

λ2 (H) min{|UH |, |ŪH |}. 2

(10)

D. Yarmoshik and M. Klimenko

7

B

U \B

U

H

B

G0

B

U \B

U

U \B

U

F

F after patch

Figure 2 Stages of constructing the communication graph. The figure illustrates: the initial graph H (C4 in our example); its extension G0 with the highlighted information spread boundary B = ∂G0 U (boundary vertices are denoted by ✩); the overlaid multigraph F (here, a torus graph) containing bad edges (highlighted in red); and the final state of graph F after applying the patch procedure to prevent premature information spread (new edges added during the patch procedure are marked in violet).

Then, denote M the number of bad edges. It is upper bounded as |EF (U, Ū )| + |EF (U ∪ B, Ū \ B)| − |EF (B, B̄)| 2 |EF (U, Ū )| + |EF (U ∪ B, Ū \ B)| ≤ 2 dF ≤ (min{|U |, |Ū |} + min{|U ∪ B|, |Ū \ B|}) 2 dF = (2 min{|U |, |Ū \ B|} + |B|) 2

M=

(11)

Since the assignment of boundary nodes b ∈ B to bad edges is uniform, the replacement of

8

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

bad edges increases the degree of each node in B at most by 

M |B|

 (11)   dF (2 min{|U |, |Ū \ B|} + |B|) ≤ 2|B| ≤

dF min{|U |, |Ū |} dF + +1 |B| 2

(12)

dF 2dF min{|U |, |Ū |} + +1 2 λ2 (H) min{|UH |, |ŪH |}   dτ dF dF ≤2 +1 + + 1. 2 λ2 (H) 2 (10)

≤

◀ We summarize the properties of G in the following lemma ▶ Lemma 4. By adding edges to G0 we can obtain graph G with λ2 (G) ≥ λ2 (F )/2, λn (G) ≤ F 2(d + 32 dF + (dτ + 2) λ2d(H) + 1) without extending node boundary of U : ∂G0 U = ∂G U = B. Proof. The node boundary B is preserved by the bad edges replacement procedure. Each bad edge (v, w) ∈ E(F ) is replaced by two edges (v, b) and (b, w). For any vector x ∈ Rn , the inequality (xv − xb )2 + (xb − xw )2 ≥ 12 (xv − xw )2 holds. Thus, the Laplacian of the replaced edges dominates half the Laplacian of the original edge, giving LG ⪰ 12 LF . Consequently: λ2 (G(k) ) ≥

λ2 (F ) 2

(13)

The bound for λn follows from Claim 3 and the fact that the maximum eigenvalue of a Laplacian is not greater than the maximum degree multiplied by 2. ◀ ▷ Claim 5. Let H be the (d = 8)-regular Margulis expander on m2 nodes. Then √ d − 5 2 ≤ λi (H) ≤ 2d,

i ∈ {2, . . . , m2 },

(14)

and its diameter ∆(H) > log m − 0.15. √ Proof. It holds for any m ≥ 1 that maxi∈{2,...,m2 } |λi (AH )| ≤ 5 2, where λi (A) denote eigenvalues of adjacency matrix ordered from the largest to the smallest [10, Theorem 8.2]. Since H is d-regular, we have LH = dIm2 − AH , therefore √ λmin+ (H) ≥ d − 5 2.

(15)

Similarly, in each row a⊤ i of adjacency matrix AH all elements are nonnegative and their sum is equal to d, thus its eigenvalue moduli are upper-bounded by d: let x be any eigenvector, then 2

|λ||xi | = |a⊤ i x| ≤

m X j=1

2

aij |xj | ≤ max2 |xj | j∈[m ]

m X j=1

aij = d max2 |xj |.

(16)

j∈[m ]

In turn, λmax (H) ≤ d + max |λi (AH )| ≤ 2d. i

(17)

D. Yarmoshik and M. Klimenko

9

Counting the number of vertices at distance at most ∆(H) from any fixed vertex (including itself), we have the Moore bound m2 ≤ 1 + d + d(d − 1) + d(d − 1)2 + . . . + d(d − 1)∆(H)−1 =1+d

d (d − 1)∆(H) − 1 ≤ (d − 1)∆(H) , d−2 d−2

log m2 ≤ log

∆(H) ≥

d + ∆(H) log (d − 1) , d−2

d=8 1 log d−2 log m2 d > + log m2 − 0.15 = log m − 0.15. log (d − 1) log (d − 1) 2

(18) ◀

▶ Lemma 6. Let M be an undirected d-regular graph on n′ vertices, and let F be a multigraph on n > 5 vertices (n < n′ ) obtained by merging k = n′ − n disjoint pairs of vertices in M . Assume that all edges of M are preserved in F (edges between merged vertices become self-loops, and edges to the same neighbor become parallel edges). Then the second eigenvalue of the Laplacian LF is bounded as: λ2 (F ) ≥ λ2 (M )

(19)

Proof. Let LM and LF be the Laplacians corresponding to graphs M and F . By the CourantFischer theorem, the second eigenvalue of F is the minimum of the Rayleigh quotient over zero-mean vectors: λ2 (F ) =

x⊤ LF x . x⊥1,x̸=0 ∥x∥2 min

(20)

Let x ∈ Rn be the eigenvector achieving this minimum, so n

2

P

v∈V (F ) xv = 0 and x

⊤

LF x =

′

λ2 (F )∥x∥ . We define a lifted vector x̃ ∈ R for the graph M by assigning to each vertex in M the exact value of its corresponding merged vertex in F . Because the edge sets perfectly correspond (with internal merged edges becoming loops and adjacent edges becoming parallel), the quadratic forms are exactly equal: x⊤ LF x = x̃⊤ LM x̃. P Let µ = n1′ u∈V (M ) x̃u be the mean of x̃. Since x sums to zero, the sum of x̃ comes exclusively from the k duplicated vertices. Let xm1 , . . . , xmk be the values on these vertices. Pk Thus µ = n1′ i=1 xmi . Then vector x̃ − µ1 is orthogonal to 1. From the properties of Laplacian and Courant-Fischer theorem: x̃⊤ LM x̃ = (x̃ − µ1)⊤ LM (x̃ − µ1) ≥ λ2 (M )∥x̃ − µ1∥2 .

(21)

Expanding the norm of x̃: ∥x̃ − µ1∥2 = ∥x̃∥2 − n′ µ2 = ∥x∥2 +

k X i=1

k

x2mi − n′

1 X xm i n′ i=1

!2 .

(22)

Pk Pk Applying the Cauchy-Schwarz inequality yields n1′ ( i=1 xmi )2 ≤ nk′ i=1 x2mi . Since k < n′ , P k it follows that n′ µ2 ≤ i=1 x2mi . Therefore, ∥x̃ − µ1∥2 ≥ ∥x∥2 . Combining these relations yields: λ2 (F )∥x∥2 = x⊤ LF x = x̃⊤ LM x̃ ≥ λ2 (M )∥x̃ − µ1∥2 ≥ λ2 (M )∥x∥2 .

(23)

Dividing by ∥x∥2 establishes λ2 (F ) ≥ λ2 (M ) which concludes the proof.

◀

10

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

▶ Lemma 7. Let τ ≥ 1, m ≥ 2 be integer parameters. For any n = m2 (1 + 4τ ), n > 5 ∆(G) there exists a sequence of graphs G = {G(k) }k=1 on |VG | = n nodes, and two sets of nodes S, T ⊂ VG with effective distance between them bounded as ρ (S, T ) ≥ (τ + 1)(log m − 2.15)

(24)

and the condition number of the sequence is χG ≤ 291 + 595τ . Proof. The sequence G is constructed as follows. We start by setting H to be the (d = 8)regular Margulis expander on |VH | = m2 nodes [10, Theorem 8.2]. We take s and t — two nodes in VH such that the distance between them is the diameter ∆(H) of graph H. At (1) the initial moment the communication graph G0 = G(1) is just the τ -star extension of H, and the set of infected nodes consists of the single node: U = {s}. Note that the condition m ≥ 2 was required only for H to have more than one node, so that the effective diameter could be increased by the star extension. After the k-th timestep (communication round) (k) (k+1) we change centers of each star in G0 in cyclic order, obtaining G0 , and then we apply (k+1) the patch procedure, obtaining G . By Lemma 4 the patch procedure does not affect information (infection) spread. Due to the cyclic change of star centers for each (v, w) ∈ EH it takes τ + 1 timesteps to transmit infection from v to w, thus t becomes infected only after (τ + 1)∆(H) timesteps, yielding ρ ({s}, {t}) ≥ (τ + 1)∆(H).

(25) √

By Claim 5 Margulis expander H has ∆(H) > log m − 0.15, and λ2 (H) ≥ d −5 2 > 0.928 regardless of m. For an integer n > 5, consider a Margulis expander M such that n′ = |VM | > n and n′ is the minimum possible. Let k = n′ − n. From our choice of M , k ≤ n2 . We construct a multigraph F on n vertices by merging k pairs of vertices of M . By Lemma 6 this merge does not decrease second eigenvalue. Additionally, after performing all such identifications, the degree of each vertex in F is bounded by dF = 2d = 16. Now we bound the spectrum of the final graph G(k) . By Lemma 4: √ 1 d−5 2 (k) λ2 (G ) ≥ λ2 (F ) ≥ > 0.464. (26) 2 2 For the maximum eigenvalue, using the degree bounds with dH = d = 8 and dF = 16:     3 dF 16(8τ + 2) λn (G(k) ) ≤ 2 dH + dF + (dH τ + 2) + 1 ≤ 2 8 + 24 + + 1 < 135+276τ. 2 λ2 (H) 0.928 (27) Thus, the condition number of the sequence is bounded by: χG =

λn (G(k) ) 135 + 276τ ≤ < 291 + 595τ. (k) 0.464 λ2 (G )

(28)

Finally, we define S as the union of s, its neighbors in H, and all stars inserted into all edges incident to s in H by the τ -star extension. Accordingly, T is the union of t and all its neighbors and adjacent stars. We obtain: ρ(S, T ) ≥ ρ({s}, {t}) − 2(τ + 1) ≥ (τ + 1)(∆(H) − 2) > (τ + 1)(log m − 2.15).

(29) ◀

D. Yarmoshik and M. Klimenko

11

Proof of Theorem 1. The objective is constructed in a standard way by splitting Nesterov’s “worst function” f (x) zero-chain [5, 26] into two additive terms [2] 1 (φ1 (x) + φ2 (x)) , n
nµg n(Lg − µg ) ⊤ 2 x M1 x − 2x1 + φ1 (x) = ∥x∥ , 8 4 n(Lg − µg ) ⊤ nµg 2 φ2 (x) = x M2 x + ∥x∥ , 8 4 f (x) =

(30) (31) (32)

where  M1 = diag (M0 , M0 , . . .) ,

M2 = diag (1, M0 , M0 , . . .) ,

M0 =

1 −1

 −1 . 1

(33)

Both φ1 and φ2 are nLg /2-smooth, f is µg -strongly convex, and Lg is the exact constant of Lipschitz smoothness of f . Let φ1 (x) and φ2 (x) be evenly distributed between two subsets of nodes S, T ⊂ V (G) defined below, i.e.  1    |S| φ1 (x), i ∈ S, fi (x) =

1

|T |   0,

φ2 (x),

(34)

i ∈ T,

otherwise.

Each set S (resp. T ) consists of s (resp. t), its d neighbors in H, and the τ internal vertices of each of the d stars inserted on the incident edges, so that |S| = |T | = 1 + d + dτ ≥ 2 + dτ . This guarantees that all fi have Lipschitz constant of gradient being at most nLg /2 nLg /2 m2 (1 + 4τ )Lg /2 m2 Lg ≤ = = |S| 2 + dτ 2 + 8τ 4

(35)

≤ Ll ,

where we used n = m2 (1 + dτ /2) = m2 (1 + 4τ ) with d = 8, if we set $s % Ll . m= Lg

(35)

By requirement Ll /Lg ≥ 4 we have m ≥ 2. We take τ = ⌊ χ−291 595 ⌋, which is the inverse of the bound χG ≤ 291 + 595τ of Lemma 7: this guarantees χG ≤ 291 + 595⌊ χ−291 595 ⌋ ≤ χ. Since χ−291 τ + 1 > χ−291 , Lemma 7 also gives ρ(S, T ) ≥ (τ + 1)(log m − 2.15) > 595 595 (log m − 2.15). The construction requires τ ≥ 1, i.e. χG ≥ 886, which holds by the hypothesis of Theorem 1. The idea of zero-chain-based lower bounds in convex optimization is to obtain an objective function such that (a) all components of its minimum x∗ are nonzero; (b) each oracle call (e.g. gradient computation) can increase the number of nonzero components q at most by 1. Since this part of the proof is standard, we simply refer here to the classical result about the properties of Nesterov’s zeros chain and its adaptation to distributed algorithms. By [26, Theorem 2.1.13] p √ !q Lg − µg k ∗ x −x ≥ p x0 − x ∗ , (36) √ Lg + µg k 0 where q is the index of the last nonzero component j k of x . Assuming w.l.o.g. that x = 0, for NG any first-order distributed algorithm q ≤ ρ(S,T ) + 1 [30, Lemma 1].

12

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

Thus if xk − x∗ / x0 − x∗ ≤ ε, then q ≥ log

−1

! p √ √ 2 µg Lg − µg 1 1 1 1+ p log ≥ log = √ √ ε 2 µg ε 2 Lg − µg

s

! Lg 1 − 1 log , µg ε

(37)

and  NG ≥ ρ(S, T )·(q−1) ≥

χ − 291 595

s

 log

Ll −1 Lg

!

! − 2.15

1 2

s

! ! Lg 1 − 1 log − 1 . µg ε (38)

It remains to reduce (38) to the form stated in Theorem 1. Recall that n = |VG | = m2 (1 + 4τ ) is the number of nodes. By the choice τ = ⌊ χ−291 595 ⌋ we have 595τ + 291 ≤ χ ≤ 595τ + 886, so χG = χ = Θ(τ ) and therefore   n m2 (1 + 4τ ) Ll 2 = = Θ(m ) = Θ , (39) χG χ Lg jp k  p  using m = Ll /Lg . Consequently log χnG = Θ(log m) = Θ log Ll /Lg , which matches p the factor log( Ll /Lg − 1) − 2 in (38). The side condition n/χG ≥ 4 of Theorem 1 is, up to the constants absorbed in (39), the requirement m ≥ 2, i.e. Ll /Lg ≥ 4, which is exactly the regime in which the τ-star extension is nontrivial. Substituting χ−291 595 = Ω(χG ),  p √ Ll n Lg /µg = κg , and log χG = Θ log Lg into (38), we obtain   n 1 √ NG = Ω χG κg log log , χG ε which is the claimed bound.

5

(40) ◀

Conclusion

In this paper we showed that, similar to the static setup, simple replacement of µl with µg in the communication complexity of decentralized algorithms cannot be achieved, due to the log LLgl factor, because the diameter of expander graphs with fixed χG can be as large as log(|VG |). Using the τ -star extension construction and the edge patch procedure we obtained the natural NG = Ω(χG ) scaling of communication complexity with the condition number of communication graph. L The main open questions in this research direction are removing the log µgg term in the best known communication upper bound in static setup (Mudag), and obtaining similar upper bounds in the time-varying setup. It is also interesting if a similar lower bound to Theorem 1 could be obtained for the slowly time-varying setup, where the number of edges that can be added or removed between communication rounds is limited [23, 22]. References 1

Youssef Allouah, Anastasia Koloskova, Aymane El Firdoussi, Martin Jaggi, and Rachid Guerraoui. The privacy power of correlated noise in decentralized learning. In International Conference on Machine Learning, pages 1115–1143. PMLR, 2024.

D. Yarmoshik and M. Klimenko

2 3

4 5 6 7

8 9

10 11 12

13

14

15

16 17 18

19

20 21

Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances in neural information processing systems, 28, 2015. Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 24(276):1–50, 2023. Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on a graph. SIAM review, 46(4):667–689, 2004. Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71–120, 2020. Abhimanyu Dubey et al. Kernel methods for cooperative multi-agent contextual bandits. In International Conference on Machine Learning, pages 2740–2750. PMLR, 2020. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265–284. Springer, 2006. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and trends® in theoretical computer science, 9(3-4):211–487, 2014. Eduard Gorbunov, Alexander Rogozin, Aleksandr Beznosikov, Darina Dvinskikh, and Alexander Gasnikov. Recent theoretical advances in decentralized distributed convex optimization. In High-Dimensional Optimization and Probability: With a View Towards Data Science, pages 253–325. Springer, 2022. S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561, 2006. Anastasiia Koloskova. Optimization algorithms for decentralized, distributed and collaborative machine learning. PhD thesis, EPFL, 2024. D. Kovalev, E. Gasanov, A. Gasnikov, and P. Richtárik. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. In Advances in Neural Information Processing Systems, volume 34, pages 22325–22335, 2021. D. A. Kovalev, A. B. Kupavskii, A. V. Rogozin, and D. V. Yarmoshik. On the complexity of decentralized optimization via global function parameters. Uspekhi Mat. Nauk, 81(3(489)):163– 164, 2026. http://mi.mathnet.ru/eng/rm10278. Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33:18342–18352, 2020. Kartik Lakhotia, Maciej Besta, Laura Monroe, Kelly Isham, Patrick Iff, Torsten Hoefler, and Fabrizio Petrini. Polarfly: A cost-effective and flexible low-diameter topology. In SC22: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–15. IEEE, 2022. John Lazarsfeld and Dan Alistarh. Simple opinion dynamics for no-regret learning. arXiv preprint arXiv:2306.08670, 2023. Huan Li and Zhouchen Lin. Accelerated gradient tracking over time-varying graphs for decentralized optimization. Journal of Machine Learning Research, 25(274):1–52, 2024. Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017. Heng Liao, Bingyang Liu, Xianping Chen, Zhigang Guo, Chuanning Cheng, Jianbing Wang, Xiangyu Chen, Peng Dong, Rui Meng, Wenjie Liu, et al. Ub-mesh: a hierarchically localized nd-fullmesh datacenter network architecture. IEEE Micro, 2025. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on computing, 21(1):193–201, 1992. Othmane Marfoq, Chuan Xu, Giovanni Neglia, and Richard Vidal. Throughput-optimal topology design for cross-silo federated learning. Advances in Neural Information Processing Systems, 33:19478–19487, 2020.

13

14

A Communication Complexity Lower Bound for Nonuniformly Convex Consensus Optimization

22

23

24 25 26 27

28 29

30

31

32

33 34 35 36

37

38 39

Dmitry Metelev, Aleksandr Beznosikov, Alexander Rogozin, Alexander Gasnikov, and Anton Proskurnikov. Decentralized optimization over slowly time-varying graphs: Algorithms and lower bounds. arXiv preprint arXiv:2307.12562, 2023. Dmitry Metelev, Alexander Rogozin, Dmitry Kovalev, and Alexander Gasnikov. Is consensus acceleration possible in decentralized optimization over slowly time-varying networks? In International Conference on Machine Learning, pages 24532–24554. PMLR, 2023. Angelia Nedić and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009. Angelia Nedic, Asuman Ozdaglar, and Pablo A Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4):922–938, 2010. Yurii Nesterov. Introductory Lectures on Convex Optimization: a basic course. Kluwer Academic Publishers, Massachusetts, 2004. Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34:4384–4396, 2021. Vaclav Rozhon. Local Complexity: New Results and Bridges to Other Fields. PhD thesis, ETH Zurich, 2024. Max Ryabinin, Eduard Gorbunov, Vsevolod Plokhotnyuk, and Gennady Pekhimenko. Moshpit sgd: Communication-efficient decentralized training on heterogeneous unreliable devices. Advances in Neural Information Processing Systems, 34:18195–18211, 2021. Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 3027–3036. JMLR. org, 2017. Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, 20(159):1–31, 2019. Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Interspeech, volume 2014, pages 1058–1062. Singapore, 2014. Ibne Farabi Shihab. Locality, not spectral mixing, governs direct propagation in distributed offline dynamic programming. arXiv preprint arXiv:2604.18615, 2026. Daniel Spielman. Spectral graph theory. Combinatorial scientific computing, 18(18), 2012. Alexander Tyurin. Optimality in decentralized optimization under bandwidth constraints. arXiv preprint arXiv:2603.20735, 2026. Alexander Tyurin and Peter Richtárik. On the optimal time complexities in decentralized stochastic asynchronous optimization. Advances in Neural Information Processing Systems, 37:122652–122705, 2024. Demyan Yarmoshik, Alexander Rogozin, Nikita Kiselev, Daniil Dorin, Alexander Gasnikov, and Dmitry Kovalev. Decentralized optimization with coupled constraints. In International Conference on Learning Representations, volume 2025, pages 63369–63390, 2025. Haishan Ye, Luo Luo, Ziang Zhou, and Tong Zhang. Multi-consensus decentralized accelerated gradient descent. Journal of machine learning research, 24(306):1–50, 2023. Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34:13975–13987, 2021.