# decentralized_optimization_with_coupled_constraints__e95a4fde.pdf

Published as a conference paper at ICLR 2025

DECENTRALIZED OPTIMIZATION WITH COUPLED CONSTRAINTS

Demyan Yarmoshik MIPT; Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia yarmoshik.dv@phystech.edu

Alexander Rogozin MIPT; Skoltech aleksander.rogozin@phystech.edu

Nikita Kiselev Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia; MIPT kiselev.ns@phystech.edu

Daniil Dorin MIPT dorin.dd@phystech.edu

Alexander Gasnikov Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia; MIPT; Skoltech gasnikov@yandex.ru

Dmitry Kovalev Yandex Research dakovalev1@gmail.com

We consider the decentralized minimization of a separable objective Pn i=1 fi(xi), where the variables are coupled through an affine constraint Pn i=1 (Aixi bi) = 0. We assume that the functions fi, matrices Ai, and vectors bi are stored locally by the nodes of a computational network, and that the functions fi are smooth and strongly convex. This problem has significant applications in resource allocation and systems control and can also arise in distributed machine learning. We propose lower complexity bounds for decentralized optimization problems with coupled constraints and a first-order algorithm achieving the lower bounds. To the best of our knowledge, our method is also the first linearly convergent first-order decentralized algorithm for problems with general affine coupled constraints.

1 INTRODUCTION

We consider the decentralized optimization problem with coupled constraints

min x1 Rd1,...,xn Rdn

i=1 fi(xi) s.t.

i=1 (Aixi bi) = 0, (1)

where for i {1, . . . , n} functions fi(xi): Rdi R are continuously differentiable, Ai Rm di and bi Rm are constraint matrices and vectors respectively.

Published as a conference paper at ICLR 2025

We are interested in solving problem (1) in a decentralized distributed setting. That is, we assume the existence of a communication network G = (V, E), where V = {1, . . . , n} is the set of compute nodes, and E V V is the set of communication links in the network. Each compute node i V locally stores the objective function fi(xi), the constraint matrix Ai and the vector bi. Compute node i V can send information (e.g., vectors, scalars, etc.) to compute node j V if and only if there is an edge (i, j) E in the communication network.

Coupled constraints arise in various application scenarios, where sharing resources or information takes place. Often, due to the distributed nature of such problems, decentralization is desired for communication and/or privacy related reasons. Let us briefly describe several practical cases of optimization problems with coupled constraints.

Optimal exchange. Also known as the resource allocation problem Boyd et al. (2011); Nedi c et al. (2018), it writes as

min x1,...,xn Rd

i=1 fi(xi) s.t.

i=1 xi = b,

where xi Rd represents the quantities of commodities exchanged among the agents of the system, and b Rd represents the shared budget or demand for each commodity. This problem is essential in economics Arrow and Debreu (1954), and systems control Dominguez-Garcia et al. (2012).

Problems on graphs. In various applications, distributed systems are formed on the basis of physical networks. This is the case for electrical microgrids, telecommunication networks and drone swarms. Distributed optimization on graphs applies to such systems and encompasses, to name a few, optimal power flow Wang et al. (2016) and power system state estimation Zhang et al. (2024) problems.

As an example, consider an electric power network. Let xi R2 denote the voltage phase angle and the magnitude at i-th electric node, and let s be the vector of (active and reactive) power flows for each pair of adjacent electric nodes. Highly accurate linearization approaches Yang et al. (2016); Van den Bergh et al. (2014) allow to formulate the necessary relation between voltages and power flows as a linear system of equations Pn i=1 Aixi = s. An important property of the matrices Ai is that their compatibility with the physical network (but not necessary with the communication network). This means that for each row of the matrix (A1, . . . , An), there is a node k such that Ai can have nonzero elements in this row only if nodes i and k are connected in the physical network, or k = i.

Consensus optimization. Related to the previous example is the consensus optimization Boyd et al. (2011)

min x1,...,xn Rd

i=1 fi(xi) s.t. x1 = x2 = . . . = xn.

It is widely used in horizontal federated learning Kairouz et al. (2021), as well as in the more general context of decentralized optimization of finite-sum objectives Gorbunov et al. (2022); Scaman et al. (2017).

To handle the consensus constraint, decentralized algorithms either reformulate it as Pn i=1 Wixi = 0, where Wi is the i-th vertical block of a gossip matrix (an example of which is the communication graph s Laplacian), or utilize the closely related mixing matrix approach Gorbunov et al. (2022). Mixing and gossip matrices are used because they are communication-friendly: calculating the sum Pn i=1 Wixi only requires each compute node to communicate once with each of its adjacent nodes. Clearly, consensus optimization with gossip matrix reformulation can be reduced to (1) by setting Ai = Wi. However, the principal difference between this example and (1), is that (1) does not assume Ai to be communication-friendly. We discuss the complexity of the reduction from consensus optimization to optimization with coupled constraints in Appendix A.

Vertical federated learning (VFL). In the case of VFL, the data is partitioned by features, differing from the usual (horizontal) federated learning, where the data is partitioned by samples Yang et al. (2019); Boyd et al. (2011). Let F be the matrix of features, split vertically between compute nodes into submatrices Fi, so that each node possesses its own subset of features for all data samples. Let

Published as a conference paper at ICLR 2025

l Rm denote the vector of labels, and let xi Rdi be the vector of model parameters owned by the i-th node. VFL problem formulates as

x1 Rd1,...,xn Rdn ℓ(z, l) +

i=1 ri(xi) s.t.

i=1 Fixi = z, (2)

where ℓis a loss function, and ri are regularizers. The constraints in (2) are coupled constraints, and the objective is separable; therefore, it is a special case of (1). We return to the VFL example in Section 6.

Paper organization. In Section 2 we present a literature review. Subsequently, in Section 3 we introduce the assumptions and problem parameters. Section 4 describes the key ideas of algorithm development and Section 5 presents the convergence rate of the method and the lower complexity bounds. Finally, in Section 6, we provide numerical simulations.

2 RELATED WORK AND OUR CONTRIBUTION

Decentralized optimization algorithms were initially proposed for consensus optimization Nedi c and Ozdaglar (2009), based on earlier research in distributed optimization Tsitsiklis (1984); Bertsekas and Tsitsiklis (1989) and algorithms for decentralized averaging (consensus or gossip algorithms) Boyd et al. (2006); Olshevsky and Tsitsiklis (2009), which assumed the existence of a communication network, as does the present paper. The optimal complexity for consensus optimization was first achieved with a dual accelerated gradient descent in Scaman et al. (2017), where the method required computing gradients of Fenchel conjugates of fi(x). The corresponding complexity lower bounds were also established in the same paper. This result was later generalized to primal algorithms (which use gradients of the functions fi(x) themselves) Kovalev et al. (2020), time-varying communication graphs Li and Lin (2021); Kovalev et al. (2021) and methods that use stochastic gradients Dvinskikh and Gasnikov (2021). Today there also exist algorithms with communication compression Beznosikov et al. (2023), asynchronous algorithms Koloskova (2024), algorithms for saddle-point formulations Rogozin et al. (2021) and gradient-free oracles Beznosikov et al. (2020), making decentralized consensus optimization a quite well-developed field Nedi c (2020); Gorbunov et al. (2022), benefiting systems control Ram et al. (2009) and machine learning Lian et al. (2017).

Beginning with the addition of local constraints to consensus optimization Nedic et al. (2010); Zhu and Martinez (2011), constrained decentralized optimization has been established as a research direction. A zoo of distributed problems with constraints was investigated in Necoara et al. (2011); Necoara and Nedelcu (2014; 2015).

Primarily motivated by the demand from the power systems community, various decentralized algorithms for coupled constraints have been proposed. Generally designed for versatile engineering applications, many of these algorithms assume restricted function domains Wang and Hu (2022); Liang et al. (2019); Nedi c et al. (2018); Gong and Zhang (2023); Zhang et al. (2021); Wu et al. (2022), nonlinear inequality constraints Liang et al. (2019); Gong and Zhang (2023); Wu et al. (2022), time-varying graphs Zhang et al. (2021); Nedi c et al. (2018) or utilize specific problem structure Wang and Hu (2022).

Table 1: Comparison of algorithms for decentralized optimization with coupled constraints

Reference Oracle Rate Doan and Olshevsky (2017) First-order Linear Falsone et al. (2020) Prox Sub-linear Wu et al. (2022) Prox Sub-linear Chang (2016) Prox Sub-linear Li et al. (2018) Prox Linear Gong and Zhang (2023) Inexact prox Linear Nedi c et al. (2018) First-order Accelerated This work First-order Optimal

Applicable only for resource allocation problem

Works of Doan and Olshevsky (2017); Li et al. (2018); Nedi c et al. (2018) focus on the resource allocation problem. For undirected time-varying graphs Doan and Olshevsky (2017) proposes a first-order algorithm with O(Bκfn2 ln 1

ε) communication and derivative computation complexity bound, where B is the time required for the time-varying graph to reach connectivity. Li et al. (2018) applies a combination of gradient

Published as a conference paper at ICLR 2025

tracking and push-sum approaches from Nedic et al. (2017) to obtain linear convergence on directed time-varying graphs in the restricted domain case, i.e., xi Ωi, where Ωi is a nonempty closed convex set. Nedi c et al. (2018) achieves accelerated linear convergence via a proximal point method in the restricted domain case. When Ωi = Rd, they also show that Nesterov s accelerated gradient descent can be applied to achieve optimal O( κW κf ln 1

ε) communication complexity. In Gong and Zhang (2023) an inexact proximal-point method is proposed to solve problems with coupled affine equality and convex inequality constraints. Linear convergence is proved when the inequalities are absent, and Ωi are convex polyhedrons. The papers Wu et al. (2022), Chang (2016), Falsone et al. (2020) present algorithms with sub-linear convergence.

As summarized in Table 1, no accelerated linearly convergent algorithms for general affine-equality coupled constraints were present in the literature prior to our work. Also, most of the algorithms require proximal oracle, which allows to handle more general problem formulations, but has higher computational burden than the first-order oracle. We propose a new first-order decentralized algorithm with optimal (accelerated) linear convergence rate. We prove its optimality by providing lower bounds for the number of objective s gradient computations, matrix multiplications and decentralized communications, which match complexity bounds for our algorithm.

3 MATHEMATICAL SETTING AND ASSUMPTIONS

Let us begin by introducing the notation. The largest and smallest nonzero eigenvalues (or singular values) of a matrix C are denoted by λmax(C) (or σmax(C)) and λmin+(C) (or σmin+(C)), respectively. For vectors xi Rdi we introduce a column-stacked vector x = col(x1, . . . , xm) = (x 1 . . . x m) Rd. We denote the identity matrix by Im Rm m. The symbol denotes the Kronecker product of matrices. By Lm we denote the so-called consensus space, which is given as Lm = {(y1, . . . , yn) (Rm)n : y1, . . . , yn Rm and y1 = = yn}, and L m denotes the orthogonal complement to Lm, which is given as

L m = {(y1, . . . , yn) (Rm)n : y1, . . . , yn Rm and y1 + + yn = 0}. (3)

Assumption 1. Continuously differentiable functions fi(x): Rdi R, i {1, . . . , n} are Lfsmooth and µf-strongly convex, where Lf µf > 0. That is, for all x1, x2 Rdi and i {1, . . . , n}, the following inequalities hold:

2 x2 x1 2 fi(x2) fi(x1) fi(x1), x2 x1 Lf

By κf we denote the condition number κf = Lf/µf.

Assumption 2. There exists x = (x 1, . . . , x n), x i Rdi such that Pn i=1(Aix i bi) = 0. There exist constants LA µA > 0, such that the constraint matrices A1, . . . , An satisfy the following inequalities: σ2 max(A) = max i {1,...,n} σ2 max(Ai) LA, µA λmin+ (S) , (4)

where the matrix S Rm m is defined as S = 1

n Pn i=1 Ai A i . We also define the condition number of the block-diagonal matrix A = diag (A1, . . . , An) Rmn d as κA = LA/µA.

For any matrix M other than A we denote by LM and µM some upper and lower bound on its maximal and minimal positive squared singular values respectively:

λmax(M M) = σ2 max(M) LM, µM σ2 min+(M) = λmin+(M M). (5)

We also assume the existence of a so-called gossip matrix W Rn n associated with the communication network G, which satisfies the following assumption.

Assumption 3. The gossip matrix W is a n n symmetric positive semidefinite matrix such that: 1. Wij = 0 if and only if (i, j) E or i = j. 2. Wy = 0 if and only if y L1, i.e. y1 = . . . = yn. 3. There exist constants LW µW > 0 such that µW λ2 min+(W) and λ2 max(W) LW.

Published as a conference paper at ICLR 2025

We will use a dimension-lifted analogue of the gossip matrix defined as W = W Im. From the properties of the Kronecker product of matrices it follows that λ2 min+(W) = λ2 min+(W) and λ2 max(W) = λ2 max(W). By κW we denote the condition number

LW µW λmax(W)

λmin+(W). (6)

Moreover, the kernel and range spaces of W and W are given by

ker W = L1, range W = L 1 , ker W = Lm, range W = L m. (7)

4 DERIVATION OF THE ALGORITHM

4.1 STRONGLY CONVEX COMMUNICATION-FRIENDLY REFORMULATION

Let W be any positive semidefinite matrix such that

range W = (ker W ) = L m, (8)

and multiplication of a vector y = (y1, . . . , yn) (Rm)n by W can be performed efficiently in the decentralized manner if its i-th block component yi is stored at i-th node of the computation network. Similarly to eq. (6), we define

LW µW λmax(W )

λmin+(W ). (9)

Due to the definition of W and eq. (7), the simplest choice for W might be to set W = W. Later we will specify another way to choose W for optimal algorithmic performance.

Problem (1) can be reformulated as follows:

min x Rd,y (Rm)n G(x, y) s.t. Ax + γW y = b, (10)

where the function G(x, y): Rd (Rm)n R is defined as

G(x, y) = F(x) + r

2 Ax + γW y b 2, (11)

the function F(x): Rd R is defined as F(x) = Pn i=1 fi(xi), where x = (x1, . . . , xn), xi Rdi, the matrix A Rmn d is the block-diagonal matrix A = diag (A1, . . . , An), the vector b is the column-stacked vector b = col (b1, . . . , bn) Rmn, and r, γ > 0 are scalar constants that will be determined later.

From the definitions of A, b and L m (eq. (3)) it is clear that Pn i=1(Aixi bi) = 0 if and only if Ax b L m. Since range W = L m, the constraint in problem (10) is equivalent to the coupled constraint in (1). For all x, y satisfying the constraint, the augmented objective function G(x, y) is equal to the original objective function F(x). Therefore, problem (10) is equivalent to problem (1).

The following Lemma 1 shows that the function G(x, y) is strongly convex and smooth. Lemma 1. Let r and γ be defined as follows:

2LA , γ2 = µA + LA

Then, the strong convexity and smoothness constants of G(x, y) on Rd L m are given by

µG = µf min 1

, LG = max Lf + µf, µf µA + LA

Let the matrix B Rmn (d+mn) be defined as B = [A γW ]. The following Lemma 2 connects the spectral properties of B, A and W .

Published as a conference paper at ICLR 2025

Lemma 2. The following bounds on the singular values of B hold:

σ2 min+(B) µB = µA

2 , σ2 max(B) LB = LA + (LA + µA)LW

and σ2 max(B) σ2 min+(B) LB

µB = κB = 2 κA + LW

µW (1 + κA) . (15)

Proofs of Lemma 1 and Lemma 2 are provided in Appendix B.

4.2 CHEBYSHEV ACCELERATION

Chebyshev acceleration allows us to decouple the number of computations of the objective s gradient F(x) from the properties of the communication network and the constraint matrix specifically, from the condition numbers κW and κA. The Chebyshev trick enables to replace the matrix with a matrix polynomial with a better condition number.

Consider some affine relation Mu = d and let PM be a polynomial such that PM(λ) = 0 λ = 0 for any eigenvalue λ of M M. Note that here we interchangeably use P as a polynomial of a matrix and a polynomial of a scalar. We denote any feasible point for the constraint Mu = d as u0. Then,

Mu = d M(u u0) = 0 (a) M M(u u0) = 0

(b) PM(M M)(u u0) = 0 (c) q

PM(M M)(u u0) = 0

where (a) and (c) is due to ker M M = ker M; (b) is due to ker PM(M M) = ker M M by the assumption about PM(λ).

Following Salim et al. (2022a) and Scaman et al. (2017), we use the translated and scaled Chebyshev polynomials, because they are the best at compressing the spectrum Auzinger and Melenk (2011).

Lemma 3 (Salim et al. (2022a), Section 6.3.2). Consider a matrix M. Let ℓ= lq

λmax(M M) λmin+(M M) m . Define PM(t) = 1 Tℓ((LM+µM 2t)/(LM µM))

Tℓ((LM+µM)/(LM µM)) , where Tℓis the Chebyshev

polynomial of the first kind of degree n defined by Tℓ(t) = 1

Then, PM(0) = 0, and

λmax PM(M M) max t [µM,LM] PM(t) 19

λmin+ PM(M M) min t [µM,LM] PM(t) 11

Results of this section are summarized in the following Lemma 4.

Lemma 4. Define W = P

PB(B B). (19)

Let G(u) = G(x, y), U = Rd L m and b = p

PB(B B)u0. Then, problem

min u U G(u) s.t. Ku = b (20)

is an equivalent preconditioned reformulation of problem (10), and, in turn, of problem (1).

4.3 BASE ALGORITHM

Published as a conference paper at ICLR 2025

Algorithm 1 APAPC

1: Parameters: u0 U η, θ, α > 0, τ (0, 1) 2: Set u0 f = u0, z0 = 0 U 3: for k = 0, 1, 2, . . . do 4: uk g := τuk + (1 τ)uk f 5: uk+ 1

2 := (1 + ηα) 1(uk η( G(uk g) αuk g + zk))

6: zk+1 := zk + θK (Kuk+ 1

2 b ) 7: uk+1 := (1 + ηα) 1(uk η( G(uk g) αuk g + zk+1))

8: uk+1 f := uk g + 2τ 2 τ (uk+1 uk) 9: end for

Our base algorithm, Algorithm 1, is the Proximal Alternating Predictor-Corrector (PAPC) with Nesterov s acceleration, called Accelerated PAPC (APAPC). It was proposed in Salim et al. (2022a) to obtain an optimal algorithm for optimization problems formulated as (20). See Kovalev et al. (2020); Salim et al. (2022b) for the review of related algorithms and history of their development.

APAPC algorithm formulates as Algorithm 1, and its convergence properties are given in Proposition 1. Proposition 1 (Salim et al. (2022a), Proposition 1). Assume that the matrix K in (20) satisfies µK > 0 and b range K, and denote κK = LK µK . Also assume that the function G is LG-

smooth and µG-strongly convex. Set the parameter values of Algorithm 1 as τ = min n 1, 1

η = 1 4τLG , θ = 1 ηLK and α = µG. Denote by u the solution of problem (20) and by z the solution of its dual problem satisfying z range K. Then the iterates uk, zk of Algorithm 1 satisfy 1 η

uk u 2 + ηα θ(1 + ηα)

(K ) zk z 2 (21)

τ DG(uk f, u ) 1 + 1

4 min 1 κGκK , 1

where C := 1 η u0 u 2 + 1

θ z0 z 2 + 2(1 τ)

τ DG(u0 f, u ), and DG denotes the Bregman divergence of G, defined by DG(u , u) = G(u ) G(u) G(u), u u .

5 MAIN RESULTS

5.1 ALGORITHM

Algorithm 2 Main algorithm

1: Parameters: x0 Rd η, θ, α > 0, τ (0, 1) 2: Set y0 := 0 (Rm)n, u0 := (x0, y0), 3: u0 f := u0, z0 := 0 Rd (Rm)n

4: for k = 0, 1, 2, . . . do 5: uk g := τuk + (1 τ)uk f 6: gk := grad_G(uk g) αuk g 7: uk+ 1

2 := (1 + ηα) 1(uk η(gk + zk)) 8: zk+1 := zk + θ K_Chebyshev(uk+ 1

2 ) 9: uk+1 := (1 + ηα) 1(uk η(gk + zk+1)) 10: uk+1 f := uk g + 2τ 2 τ (uk+1 uk) 11: end for

As stated in Lemma 4, problem (20) is equivalent to problem (1). Due to Lemma 1, its objective is strongly convex, allowing us to apply Algorithm 1 to it. Using Lemma 3, we obtain that the condition numbers of W and K are bounded as O(1), but a single multiplication by W and K, K translates to O( κW) multiplications by W and O( κB) multiplications by B, B respectively.

We implement multiplications by W and K, K through numerically stable Chebyshev iteration procedures given in Algorithms 3 and 5, which only use decentralized communications and multiplications by A, A . Lemmas 1 to 3 allow us to express the complexity of Algorithm 1 in terms of the parameters of the initial problem given in Assumptions 1 to 3. All this leads us to the following Theorem 1, a detailed proof of which is provided in Appendix B.3, as well as the derivation of Algorithms 3 and 5 and values of the parameters of Algorithm 2.

Theorem 1. Set the parameter values of Algorithm 2 as τ = min n 1, 1

19 44 max{1+κf ,6} o ,

η = 1 4τ max{Lf +µf ,6µf }, θ = 15 19η and α = µf

4 . Denote by x the solution of problem (1).

Published as a conference paper at ICLR 2025

Algorithm 3 mul W (y): Multiplication by W

1: Parameters: y 2: ρ := LW µW 2 /16 3: ν := LW + µW /2 4: δ0 := ν/2, n := κW 5: p0 := Wy/ν, y1 := y + p0

6: for i = 1, . . . , n 1 do 7: βi 1 := ρ/δi 1

8: δi := (ν + βi 1) 9: pi := Wyi + βi 1pi 1 /δi

10: yi+1 := yi + pi

11: end for 12: Output: y yn

Algorithm 4 grad_G(u): Computation of G(u)

1: Parameters: u = (x, y) 2: z := r (Ax + γ mul W (y) b)

3: Output: F(x) + A z γ mul W (z)

Algorithm 5 K_Chebyshev(u): Computation of K (Ku b )

1: Parameters: u = (x, y) 2: ρ := (LB µB)2 /16 3: ν := (LB + µB) /2 4: δ0 := ν/2, n := κB 5: q0 := Ax + γ mul W (y) b

γ mul W (q0)

7: u1 := u + p0

8: for i = 1, . . . , n 1 do 9: βi 1 := ρ/δi 1

10: δi := (ν + βi 1) 11: (xi, yi) = ui

12: qi := Axi + γ mul W (yi) b

13: pi := 1 δi

γ mul W (qi)

βi 1pi 1/δi

14: ui+1 := ui + pi

15: end for 16: Output: u un

Then, for every ε > 0, Algorithm 2 finds xk for which xk x 2 ε using O( κf log(1/ε)) objective s gradient computations, O( κf κA log(1/ε)) multiplications by A and A , and O( κf κA κW log(1/ε)) communication rounds (multiplications by W).

5.2 LOWER BOUNDS

Let us formulate the lower complexity bounds for decentralized optimization with affine constraints. To do that, we formalize the class of the algorithms of interest. In the literature, approaches with continuous time Scaman et al. (2017) and discrete time Kovalev et al. (2021) are used. We use the latter discrete time formalization. We assume that the method works in synchronized rounds of three types: local objective s gradient computations, local matrix multiplications and communications. At each time step, algorithm chooses one of the three step types.

Since the devices may have different dimensions di of locally held vectors xi, they cannot communicate these vectors directly. Instead, the nodes exchange quantities Aixi Rm. For this reason, we introduce two types of memory Mi(k) and Hi(k) for node i at step k. Set Mi(k) stands for the local memory that the node does not share and Hi(k) denotes the memory that the node exchanges with neighbors. The interaction between Mi(k) and Hi(k) is performed via multiplications by Ai and A i .

Memory is initialized as Mi(0) = {0} , Hi(0) = {0}. Below we describe how the sets Mi(k), Hi(k) are updated.

1. Algorithm performs local gradient comutation round at step k. Gradient updates only operate in Mi(k) and do not affect Hi(k). For all i V we have

Mi(k + 1) = Span {x, fi(x), f i (x) : x Mi(k)} , Hi(k + 1) = Hi(k),

where f i is the Fenchel conjugate of fi. 2. Algorithm performs local matrix multiplication round at step k. Sets Hi(k) and Mi(k) make mutual updates via multiplication by Ai and A i . For all i V we have

Mi(k + 1) = Span A i bi, A i y : y Hi(k) , Hi(k + 1) = Span {bi, Aix : x Mi(k)} .

3. Algorithm performs a communication round at step k. The non-shared local memory Mi(k) stays unchanged, while the shared memory Hi(k + 1) is updated via interaction with neighbors. For all

Published as a conference paper at ICLR 2025

i V we have

Mi(k + 1) = Mi(k), Hi(k + 1) = Span {Hj(k) : (i, j) E} .

Under given memory and computation model, we formulate the lower complexity bounds. Theorem 2. For any Lf > µf > 0, κA, κW > 0 there exist Lf-smooth µf-strongly convex functions {fi}n i=1, matrices Ai such that κA = LA/µA (where LA, µA are defined in (4)), and a communication graph G with a corresponding gossip matrix W such that κW = λmax(W)/λ+ min(W), for which any first-order decentralized algorithm on problem (1) to reach accuracy ε requires at least

Nf = Ω κf log 1

gradient computations,

NA = Ω κf κA log 1

multiplications by A and A ,

NW = Ω κf κA κW log 1

communication rounds (multiplications by W).

A proof of Theorem 2 is provided in Appendix C.

6 EXPERIMENTS

The experiments were run on CPU Intel(R) Core(TM) i9-7980XE, with 62.5 GB RAM.

Synthetic linear regression. In this section we perform numerical experiments on a synthetic linear regression problem with ℓ2-regularization:

min x1,...,xn Rdi

2 Cixi di 2 2 + θ

i=1 (Aixi bi) = 0, (22)

where we randomly generate matrices Ci Rdi di, Ai Rm di and vectors di Rdi, bi Rm from the standard normal distribution. Local variables xi Rdi have the same dimension di, equal for all devices. Regularization parameter θ is 10 3. In the Fig. 1 we demonstrate the performance of the our method on the problem, that has the following parameters: κf = 3140, κA = 27, κW = 89. There we use Erd os Rényi graph topology with n = 20 nodes. Local variables dimension is di = 3 and number of linear constraints is m = 10. We compare performance of Algorithm 2 with Tracking ADMM algorithm Falsone et al. (2020) and DPMM algorithm Gong and Zhang (2023). Note that Tracking-ADMM and DPMM are proximal algorithms that solve a subproblem at each iteration. The choice of objective function in our simulations (linear regression) makes the corresponding proximal operator effectively computable via Conjugate Gradient algorithm Nesterov (2004) that uses gradient computations. Therefore, we measure the computational complexity of these methods in the number of gradient computations, not the number of proximal operator computations.

0.0 0.2 0.4 0.6 0.8 1.0 Gradient calls 104

Tracking-ADMM DPMM Main algorithm

0 1 2 3 4 Mult. by A and AT 105

Tracking-ADMM DPMM Main algorithm

0 1 2 3 4 Communications 105

Tracking-ADMM DPMM Main algorithm

Figure 1: Synthetic, Erd os Rényi graph, n = 20, di = 3, m = 10

VFL linear regression on real data. Now we return to the problem, that we have announced in the introduction section. We apply VFL in the linear regression problem: ℓis a typical mean squared loss

Published as a conference paper at ICLR 2025

function, that is ℓ(z, l) = 1

2 z l 2 2, and ri are ℓ2-regularizers, i.e. ri(xi) = λ xi 2 2. To adapt this from (2) to (1), we redefine x1 := x1 z and x2 := x2, . . . , xn := xn. Thus, we can derive constraints matrices as in the (1):

A1 = (F1 I) , A1x1 = F1w1 z, (23)

Ai = Fi, i = 2, . . . , n,

i=1 Fiwi z. (24)

For numerical simulation, we use mushrooms dataset from Lib SVM library Chang and Lin (2011). We split m = 100 samples subset vertically between n = 7 devices. Regularization parameter λ = 10 2. The results are in the Fig. 2.

0.0 0.2 0.4 0.6 0.8 1.0 Gradient calls 103

Tracking-ADMM DPMM Main algorithm

0.0 0.5 1.0 Mult. by A and AT 105

Tracking-ADMM DPMM Main algorithm

0.0 0.2 0.4 0.6 0.8 1.0 Communications 105

Tracking-ADMM DPMM Main algorithm

Figure 2: VFL, Erd os Rényi graph, n = 7, m = 100

Our algorithm exhibits the best convergence rates, as evidenced by the steepest slopes. The slopes vary for gradient calls, matrix multiplications, and communications. This is due to the fact that Algorithm 2 involves many communications per iteration, in contrast to DPMM and Tracking-ADMM, which make numerous gradient calls per iteration.

7 ACKNOWLEDGEMENTS

The work was supported by MIPT based Center of National Technology Initiatives in the field of Artificial Intelligence for the purposes of the "road map" of Artificial Intelligence development up to 2030 and supported by NTI Foundation (agreement No.70-2021-00207 dated 22.11.2021, identifier 000000S507521QYL0002).

Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 3(1):1 122, January 2011. ISSN 1935-8237. doi:10.1561/2200000016. URL http: //dx.doi.org/10.1561/2200000016.

Angelia Nedi c, Alex Olshevsky, and Wei Shi. Improved convergence rates for distributed resource allocation. In 2018 IEEE Conference on Decision and Control (CDC), pages 172 177. IEEE, 2018.

Kenneth J Arrow and Gerard Debreu. Existence of an equilibrium for a competitive economy. Econometrica: Journal of the Econometric Society, pages 265 290, 1954.

Alejandro D Dominguez-Garcia, Stanton T Cady, and Christoforos N Hadjicostis. Decentralized optimal dispatch of distributed energy resources. In 2012 IEEE 51st IEEE conference on decision and control (CDC), pages 3688 3693. IEEE, 2012.

Yamin Wang, Lei Wu, and Shouxiang Wang. A fully-decentralized consensus-based admm approach for dc-opf with demand response. IEEE Transactions on Smart Grid, 8(6):2637 2647, 2016.

Published as a conference paper at ICLR 2025

Haixiang Zhang, Ying Chen, and Javad Lavaei. Geometric analysis of matrix sensing over graphs. Advances in Neural Information Processing Systems, 36, 2024.

Jingwei Yang, Ning Zhang, Chongqing Kang, and Qing Xia. A state-independent linear power flow model with accurate estimation of voltage magnitude. IEEE Transactions on Power Systems, 32 (5):3607 3617, 2016.

Kenneth Van den Bergh, Erik Delarue, and William D haeseleer. Dc power flow in unit commitment models. no. May, 2014.

Peter Kairouz, H Brendan Mc Mahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and trends in machine learning, 14(1 2):1 210, 2021.

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, pages 253 325. Springer, 2022.

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.

Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1 19, 2019.

Angelia Nedi c and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48 61, 2009.

John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.

Dimitri P Bertsekas and John N Tsitsiklis. Parallel and distributed computation: numerical methods, volume 23. Prentice hall Englewood Cliffs, NJ, 1989.

Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2508 2530, 2006.

Alex Olshevsky and John N Tsitsiklis. Convergence speed in distributed consensus and averaging. SIAM Journal on Control and Optimization, 48(1):33 55, 2009.

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, 2020.

Huan Li and Zhouchen Lin. Accelerated gradient tracking over time-varying graphs for decentralized optimization. ar Xiv preprint ar Xiv:2104.02596, 2021.

Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtarik. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. Advances in Neural Information Processing Systems, 34, 2021.

Darina Dvinskikh and Alexander Gasnikov. Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems. Journal of Inverse and Ill-posed Problems, 29(3):385 405, 2021.

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.

Anastasiia Koloskova. Optimization algorithms for decentralized, distributed and collaborative machine learning. Technical report, EPFL, 2024.

Published as a conference paper at ICLR 2025

Alexander Rogozin, Alexander Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. ar Xiv preprint ar Xiv:2102.07758, 2021.

Aleksandr Beznosikov, Eduard Gorbunov, and Alexander Gasnikov. Derivative-free method for composite optimization with applications to decentralized distributed optimization. IFACPapers On Line, 53(2):4038 4043, 2020.

Angelia Nedi c. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine, 37(3):92 101, 2020.

Sundhar Srinivasan Ram, Venugopal V Veeravalli, and Angelia Nedic. Distributed non-autonomous power control through distributed convex optimization. In IEEE INFOCOM 2009, pages 3001 3005. IEEE, 2009.

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. In Advances in Neural Information Processing Systems, pages 5330 5340, 2017.

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.

Minghui Zhu and Sonia Martinez. On distributed convex optimization under inequality and equality constraints. IEEE Transactions on Automatic Control, 57(1):151 164, 2011.

Ion Necoara, Valentin Nedelcu, and Ioan Dumitrache. Parallel and distributed optimization methods for estimation and control in networks. Journal of Process Control, 21(5):756 766, 2011.

Ion Necoara and Valentin Nedelcu. Distributed dual gradient methods and error bound conditions. ar Xiv preprint ar Xiv:1401.4398, 2014.

Ion Necoara and Valentin Nedelcu. On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems. Automatica, 55:209 216, 2015.

Jianzheng Wang and Guoqiang Hu. Distributed optimization with coupling constraints in multi-cluster networks based on dual proximal gradient method. ar Xiv preprint ar Xiv:2203.00956, 2022.

Shu Liang, George Yin, et al. Distributed smooth convex optimization with coupled constraints. IEEE Transactions on Automatic Control, 65(1):347 353, 2019.

Kai Gong and Liwei Zhang. Decentralized proximal method of multipliers for convex optimization with coupled constraints. ar Xiv preprint ar Xiv:2310.15596, 2023.

Bingru Zhang, Chuanye Gu, and Jueyou Li. Distributed convex optimization with coupling constraints over time-varying directed graphs. Journal of Industrial and Management Optimization, 17(4): 2119 2138, 2021.

Xuyang Wu, He Wang, and Jie Lu. Distributed optimization with coupling constraints. IEEE Transactions on Automatic Control, 68(3):1847 1854, 2022.

Thinh T Doan and Alex Olshevsky. Distributed resource allocation on dynamic networks in quadratic time. Systems & Control Letters, 99:57 63, 2017.

Alessandro Falsone, Ivano Notarnicola, Giuseppe Notarstefano, and Maria Prandini. Tracking-admm for distributed constraint-coupled optimization. Automatica, 117:108962, 2020.

Tsung-Hui Chang. A proximal dual consensus admm method for multi-agent constrained optimization. IEEE Transactions on Signal Processing, 64(14):3719 3734, 2016.

Huaqing Li, Qingguo Lü, Xiaofeng Liao, and Tingwen Huang. Accelerated convergence algorithm for distributed constrained optimization under time-varying general directed graphs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 50(7):2612 2622, 2018.

Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597 2633, 2017.

Published as a conference paper at ICLR 2025

Adil Salim, Laurent Condat, Dmitry Kovalev, and Peter Richtárik. An optimal algorithm for strongly convex minimization under affine constraints. In International conference on artificial intelligence and statistics, pages 4482 4498. PMLR, 2022a.

Winfried Auzinger and J Melenk. Iterative solution of large linear systems. Lecture notes, TU Wien, 2011.

Adil Salim, Laurent Condat, Konstantin Mishchenko, and Peter Richtárik. Dualize, split, randomize: Toward fast nonsmooth optimization algorithms. Journal of Optimization Theory and Applications, 195(1):102 130, 2022b.

Yurii Nesterov. Introductory Lectures on Convex Optimization: a basic course. Kluwer Academic Publishers, Massachusetts, 2004.

Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM Trans. Intell. Syst. Technol., 2(3), may 2011. ISSN 2157-6904. doi:10.1145/1961189.1961199. URL https://doi.org/10.1145/1961189.1961199.

Martin H Gutknecht and Stefan Röllin. The chebyshev iteration revisited. Parallel Computing, 28(2): 263 283, 2002.

Published as a conference paper at ICLR 2025

APPENDIX / SUPPLEMENTAL MATERIAL

A REDUCTION OF CONSENSUS OPTIMIZATION TO COUPLED CONSTRAINTS

As mentioned in Section 1, the consensus optimization problem

min x1,...,xn Rd

i=1 fi(xi) s.t. x1 = x2 = . . . = xn

can be reduced to the problem with coupled constraints (1). During the review process, we were asked whether the complexity of Algorithm 2 could be reduced to match that of optimal algorithms for consensus optimization Scaman et al. (2017).

It turns out that, for a general-purpose first-order decentralized algorithm for problems with coupled constraints (as defined in Section 5.2), the communication complexity is worse by at least a factor of n. This conclusion is based on our complexity lower bounds in Theorem 2 and the following lower bound on κA for any suitable matrix A.

Let d = 1. Consider an arbitrary horizontal-block matrix A = (A1 . . . An) Rm n such that ker A = L1 = Span{ 1n}, which corresponds to the consensus constraint. By definition (4), we have

nλmin+ A A = 1

nσ2 min+(A ),

LA = max i=1...n σ2 max(Ai) = Ai 2,

where i denotes the index of the column achieving the maximum. We can upper bound the minimal positive singular value using a vector v, whose components are all zero except for one 1 and one 1, implying v 2 = 2. Since the sum of its components is zero, v is orthogonal to ker A , thus

σ2 min+(A ) = min v: v >0, v 1

A v 2/ v 2 Ai Aj 2/2 2 Ai 2.

It follows that

2 n Ai 2 = n

This bound is nearly tight, because we can achieve κA = n 1 by setting A to be the Laplacian matrix or the incidence matrix of a complete graph on n nodes.

Substituting this into the complexity lower bounds in Theorem 2, we find that the number of communication rounds is lower bounded by Ω κf n κW log 1

ε for any choice of A, while the optimal complexity for first order decentralized consensus optimization is O κf κW log 1

B MISSING PROOFS FROM SECTION 4

B.1 PROOF OF LEMMA 1

Proof. Let DG(x , y ; x, y) denote the Bregman divergence of G:

DG(x , y ; x, y) = G(x , y ) G(x, y) x G(x, y), x x y G(x, y), y y . (25)

Published as a conference paper at ICLR 2025

The value of µG can be obtained as follows:

DG(x , y ; x, y) = DF (x ; x) + r

2 A(x x) + γW (y y) 2

2 x x 2 + r

2 A(x x) + γW (y y) 2

2 x x 2 + r

2 A(x x) 2 + r A(x x), γW (y y)

2 γW (y y) 2

2 x x 2 + r

4 γW (y y) 2 r

2 x x 2 + rγ2µW

4 y y 2 r LA

4 x x 2 + µfγ2µW

where (a) is due to Assumption 1; (b) is due to Young s inequality; (c) is due to Assumption 2, y y L m, eq. (8) and eq. (5); (d) and (e) is due to eq. (12).

The value of LG can be obtained as follows:

DG(x , y ; x, y) = DF (x ; x) + r

2 A(x x) + γW (y y) 2

2 x x 2 + r

2 A(x x) + γW (y y) 2

2 x x 2 + r γW (y y) 2 + r A(x x) 2

2 x x 2 + rγ2LW y y 2 + r LA x x 2

(d) = Lf + µf

2 x x 2 + µfγ2LW

2 max Lf + µf, µf µA + LA

where (a) is due to Assumption 1; (b) is due to Young s inequality; (c) is due to Assumption 2 and eq. (5); (d) and (e) is due to eq. (12).

B.2 PROOF OF LEMMA 2

Proof. To obtain the formula for LB, consider an arbitrary z (Rm)n:

B z 2 = A z 2 + γW z 2

(a) (LA + γ2LW ) z 2

(b) = LA + (LA + µA)LW

where (a) is due to Assumption 2 and eq. (5); (b) is due to eq. (12).

To derive the formula for µB, first of all, note that by eq. (8)

(ker B ) = range B = range A + range W = range A + L m. (26)

Let z (ker B ) = u+v, where u = (u1, . . . , un), v = (v0, . . . , v0) (Rm)n such that u L m and v Lm.

Published as a conference paper at ICLR 2025

We can show that v0 range S. In order to do that, let us show that v0, w0 = 0 for all w0 ker S. Let w = (w0, . . . , w0) Lm. The fact that w0 ker S and w Lm implies w ker AA = ker A . Hence, it is easy to show that w ker B = (range B) . Then, we obtain

n v0, w0 (a) = v, w (b) = u + v, w = z, w (c) = 0,

where (a) follows from the definition of v and w; (b) follows from the fact that u L m and w Lm; (c) follows from the fact that z range B and w (range B) . Hence, v0 range S.

Further, we get

B z 2 (a) = A (u + v) 2 + γW (u + v) 2

(b) = A (u + v) 2 + γW u 2

(c) A (u + v) 2 + γ2µW u 2

= A u 2 + A v 2 + 2 A u, A v + γ2µW u 2

(d) A u 2 + 1

2 A v 2 + γ2µW u 2

(e) = A u 2 + 1

2 v0, n Sv0 + γ2µW u 2

(f) LA u 2 + nµA

2 v0 2 + γ2µW u 2

= LA u 2 + µA

2 v 2 + γ2µW u 2

2 v 2 + µA u 2

where (a) and (h) is due to the definitions of u and v; (b) is due to the fact that v Lm; (c) is due to eq. (5) and eq. (8); (d) uses Young s inequality; (e) is due to the definitions of v and S, and

A 1 v0 ... A n v0

= Pn i=1 A i v0 2 = v0, Pn i=1 Ai A i v0 = v0, n Sv0 ; (f) is due to

Assumption 2 and the definition of v; (g) is due to eq. (12).

B.3 PROOF OF THEOREM 1

Lemma 5 (Salim et al. (2022a), Section 6.3.2). Let M be a matrix with µM > 0, r range M and Mv0 = r. Then PM(M M)(v v0) = v Chebyshev(v, M, r), where Chebyshev is defined as Algorithm 6.

Published as a conference paper at ICLR 2025

Algorithm 6 Chebyshev(v, M, r): Chebyshev iteration (Gutknecht and Röllin (2002), Algorithm 4)

1: Parameters: v, M, r.

3: ρ := LM µM 2/16, ν := (LM + µM)/2 4: δ0 := ν/2 5: p0 := M (Mv r)/ν 6: v1 := v + p0

7: for i = 1, . . . , n 1 do 8: βi 1 := ρ/δi 1

9: δi := (ν + βi 1) 10: pi := M (Mvi r) + βi 1pi 1 /δi

11: vi+1 := vi + pi

12: end for 13: Output: vn

Proof of Theorem 1

Proof. Applying Lemma 3 to W and B B, we derive that, due to eq. (18), it holds

λ2 max(W ) LW = (19/15)2, λ2 min+(W ) µW = (11/15)2, (27)

and by eq. (6) the polynomial PW has a degree of κW . Similarly, due to eq. (19), it holds

σ2 max(K) = λmax(K K) LK = 19/15, σ2 min+(K) = λmin+(K K) µK = 11/15, (28)

and since κB = LB

µB , the polynomial PB has a degree of κB .

We implement computation of the term K (Ku b ) in line 6 of Algorithm 1 via Algorithm 5 by Lemma 5:

K (Ku b ) = K K(u u0) = PB(B B)(u u0) = u Chebyshev(u, B, b) = K_Chebyshev(u).

Similarly, utilizing Lemma 5, we get

W)(y 0) = y Chebyshev(y,

W, 0) = mul W (y), (29) where mul W is defined as Algorithm 3.

Therefore, Algorithm 2 is equivalent to Algorithm 1.

From eqs. (13) and (27), µA+LA

LA 2 and (19/11)2 3, we get

LG = max Lf + µf, µf µA + LA

µf max {1 + κf, 6} , (30)

µG = µf min 1

µG 4 max {1 + κf, 6} . (32)

From eqs. (15) and (27) we get

µB 2 κA + (19/11)2(1 + κA) 8κA + 6. (33)

From eq. (28) we obtain

µK = 19/11, (34)

Published as a conference paper at ICLR 2025

and substituting eqs. (32) and (33) to Proposition 1, we obtain as its direct corollary that k = O( κf log(1/ε)). Each iteration of Algorithm 2 require O(1) computations of F, O( κB) = O( κA) multiplications by A, A and O( κA κW) multiplications by W, which gives us the statement of Theorem 1. The values of the parameters τ, η, θ, α in Theorem 1 are derived from Proposition 1 as follows. We have τ = min n 1, 1

o = min n 1, 1

19 44 max{1+κf ,6} o due to

eqs. (32) and (34); η = 1 4τLG = 1 4τ max{Lf +µf ,6µf } due to eq. (30); θ = 15 19η due to eq. (28) and α = µG = µf

4 due to eq. (31).

C PROOF OF THEOREM 2

C.1 DUAL PROBLEM

Let us construct the lower bound for the problem dual to the initial one. Consider primal problem with zero r.h.s. in constraints

min x1,...,xn ℓ2

i=1 Aixi = 0.

The dual problem has the form

min x1,...,xn ℓ2 max z

i=1 fi(xi) z, Aixi

max x1,...,xn ℓ2

A i z, xi fi(xi)

i=1 f i (A i z).

Introducing local copies of w at each node, we get

min z1,...,zn

i=1 gi(zi) :=

i=1 f i (A i zi)

s.t. Wz = 0.

C.2 EXAMPLE GRAPH

We follow the principle of lower bounds construction introduced in Kovalev et al. (2021) and take the example graph from Scaman et al. (2017). Let the functions held by the nodes be organized into a path graph with n vertices, where n is divisible by 3. The nodes of graph G = (V, E) are divided into three groups V1 = {1, . . . , n/3} , V2 = {n/3 + 1, . . . , 2n/3} , V3 = {2n/3 + 1, . . . , n} of n/3 vertices each.

Now we recall the construction from Scaman et al. (2017). Maximum and minimum eigenvalues of a

path graph have form λmax(W) = 2 1 + cos π

n , λmin+(W) = 2 1 cos π

n . Let βn = 1+cos( π

n) 1 cos( π

Since βn n + , there exists n = 3m 3 such that βn κW < βn+3. For this n, introduce edge weights wi,i+1 = 1 a I {i = 1}, take the corresponding weighed Laplacian Wa and denote its condition number κ(Wa). If a = 1, the network is disconnected and therefore κ(Wa) = . If a = 0, we have κ(Wa) = βn. By continuity of Laplacian spectra we obtain that for some a [0, 1) it holds κ(Wa) = κW. Note that π/(n + 3) [0, π/3] for x [0, π/3] it holds 1 cos x x2/4. We have

κW βn+3 = 1 + cos π n+3 1 cos π n+3 72(n + 3)2

π2 32n2 κW 4

Published as a conference paper at ICLR 2025

C.3 EXAMPLE FUNCTIONS

We let e1 = (1 0 . . . 0) denote the first coordinate vector and define functions

fi(p, t) = µf

2 t 2. (39)

We immediately note that each fi is Lf-smooth and µf-strongly convex. The first term has the form µf

2 p+ce1 2, and its convex conjugate is µf

2 p + ce1 2 = maxp u, p µf

2 p + ce1 2 . The gradient by p is u µf(p + ce1) = 0, thus p = 1 µf u ce1 and maxp u, p µf

2 p + ce1 2 =

2µf cu1. Correspondingly,

f i (u, v) = 1 2µf u 2 + 1 2Lf v 2

To define matrices Ai, we first introduce

1 0 0 0 0 . . . 0 1 1 0 0 . . . 0 0 0 0 0 . . . 0 0 0 1 1 . . . ... ... ... ... ... ...

1 1 0 0 0 . . . 0 0 0 0 0 . . . 0 0 1 1 0 . . . 0 0 0 0 0 . . . ... ... ... ... ... ...

Let ˆLA = 1

4µA, ˆµA = 3

2µA and introduce

[ pˆLAE 1 ˆµAI], i V1 [ 0 0 ], i V2 [ pˆLAE 2 ˆµAI], i V3

Let us make sure that the choice of Ai guarantees constants LA, µA from (4).

max i λmax(Ai A i ) = λmax ˆLAE 1 E1 + ˆµAI = 2ˆLA + ˆµA = LA,

3(ˆLAE 1 E1 + ˆµAI) + 1

3(ˆLAE 2 E2 + ˆµAI)

3 ˆµA = µA.

Let f M = 1 1 1 1

M1 = E 1 E1 =

1 0 0 . . . 0 f M 0 . . . 0 0 f M . . . ... ... ... ...

, M2 = E 2 E2 =

f M 0 0 . . . 0 f M 0 . . . 0 0 f M . . . ... ... ... ...

The dual functions take the form

gi(z) = f i (A i z) =

1 2µf pˆLAE1z 2 + 1 2Lf ˆµAz 2 ˆLA 2µf z1, i V1 0, i V2 1 2µf pˆLAE2z 2 + 1 2Lf ˆµAz 2 ˆLA 2µf z1, i V3

µf M1 + ˆµA

Lf I z ˆLA 2µf z1, i V1 0, i V2 1 2z ˆLA

µf M2 + ˆµA

Lf I z ˆLA 2µf z1, i V3

Published as a conference paper at ICLR 2025

Therefore, we have

i=1 gi(z) = n

2µf z (M1 + M2)z + ˆµA

Lf z z ˆLA µf z1

" 1 2z Mz z1 + ˆµAµf

M = M1 + M2 =

2 1 0 0 0 . . . 1 2 1 0 0 . . . 0 1 2 1 0 . . . ... ... ... ... ... ...

Now we formulate the lower complexity bounds for Pn i=1 gi(z), where gi(z) are defined in (40).

C.4 DERIVING THE LOWER BOUND

Lemma 6. Function Pn i=1 gi(z) attains its minimum at z = ρk k=1, where

µAµf + 1 1 q

µAµf + 1 + 1 .

Proof. In the lower bound example in (Lemma 1 in Appendix C) Kovalev et al. (2021) it was shown that function

2z Mz + 3µ L µz z z1

attains its minimum at z k = ρk, where

Let us deduce the expression for L/µ in terms of LA, Lf, µA, µf. We enforce h(z) = Pn i=1 gi(z) and set 3µ L µ = µAµf

µ = 1 + 3LALf

Therefore, h(z) attains its minimum at zk = ρk, where

µAµf + 1 1 q

µAµf + 1 + 1 .

Let us first show the lower bound on the number of communications. Without loss of generality we can assume that the initial point chosen by a first-order algorithm is x0 = 0 (otherwise we can shift the variables accordingly), thus Mi(0) = {0}, Hi(0) = {0}. Lemma 7. Let si(k) denote the maximum index of a nonzero component of vector blocks p, t held by i-th node at step k in its local memory Mi(k) and vector z held by i-th node in its local memory Hi(k), i.e.

0, if Mi(k) {0} and Hi(k) {0}

min n s {1, 2, . . .} : Hi(k) Span {e1, . . . , es}

and Mi(k) Span {e1, . . . , es} {e1, . . . , es} o , else.

Published as a conference paper at ICLR 2025

Let kq denote the number of algorithm step by which exactly q communication steps have been performed, where q 0. For any k {1, . . . , kq} we have

max i si(k) 2 + q n 3 + 1

Proof. If the method performs a multiplication by Ai, it transfers the information from Mi(k) to Hi(k). If multiplication by A i is performed, the information is transferred in the opposite direction, i.e. from Hi(k) to Mi(k). If the method performs a matrix multiplication step (either by A or A ), then from the structure of Ai we obtain

si(k + 1) si(k) +

1 (si(k) mod 2), i V1 0, i V2 (si(k) mod 2), i V3 We will prove that 1. For q = 2ℓ(n/3 + 1), ℓ {0, 1, . . .} we have

1 + 2ℓ, i V1 1 + 2ℓ, i V2 2 + 2ℓ, i V3 (43)

2. For q = (2ℓ+ 1)(n/3 + 1), ℓ {0, 1, . . .} we have

2 + (2ℓ+ 1), i V1 1 + (2ℓ+ 1), i V2 1 + (2ℓ+ 1), i V3 (44)

The proof follows by induction.

Induction basis. Let q = 0. From definitions of fi and Ai it follows that

1, i V1 0, i V2 2, i V3 Therefore, for q = 0 our statement holds.

Induction step for q = (2ℓ+ 1)(n/3 + 1). Consider q = q n/3 = 2ℓ(n/3 + 1). From (43) we have that for the spread of nonzero components from V3 to V1 it requires n/3 communication rounds to reach node n/3 + 1. After one more communication round, the information reaches node n/3.

Induction step for q = 2ℓ(n/3 + 1). The proof follows by the same argument as for q = (2ℓ+ 1)(n/3 + 1).

We just proved the statement of lemma, i.e. relation (42), for q divisible by (n/3 + 1). Between such checkpoints, the information (i.e. the number of nonzero components) traverses nodes of V2 and therefore maxi si(k) stays unchanged. Thus the statement of the lemma is proven.

Now we estimate the distance to optimum. Due to the strong duality, the solution of problem (35) can be obtained from the solution of its dual (36) as

x i (z ) = pi ti

ˆLA µf (E(i)z e1) ˆµA

Therefore, denoting α = ˆµA

xk i x i 2 tk i t i 2

ℓ=si(k)+1 (t i,ℓ)2 = α

ℓ=si(k)+1 (z ℓ)2 = α

ℓ=si(k)+1 ρ2ℓ

= αρ2si(k)+2

1 ρ2 = αρ6+2 q n/3+1

(a) αρ6+ 2q 2n/3

1 ρ2 = α ρ6

Published as a conference paper at ICLR 2025

where (a) holds since n/3 1; (b) holds due to (38).

Following Kovalev et al. (2021), we obtain that

xk i x i 2 2 α ρ6

It follows that the number of communications is lower bounded as

and the number of matrix multiplications at each node is lower bounded as

C.5 LOWER BOUND ON THE NUMBER OF GRADIENT COMPUTATIONS

To get the lower bound on local gradient calls, let us consider a problem

min x1,...xn Rd

u1,...,un Rd

i=1 fi(xi) +

i=1 Aixi = 0

where all fi(x) are defined in (39) and all vi(ui) are similar and defined as

vi(ui) = Lf

8 u i Mui + µf

First, note that each vi(ui) is Lf-smooth and µf-strongly convex, i.e. problem (47) satisfies the assumptions of Theorem 2.

Problem (47) falls into two independent parts. The first part is minimization of Pn i=1 fi(xi) subject to constraints and is identical to (35), while the second part is minimization of Pn i=1 vi(ui) without constraints. Therefore, the lower bounds on the number of communications and number of matrix multiplications for problem (47) are inherited from lower bounds for problem (35) and are the given by NW in (45) and NA in (46). It remains to lower bound the number of oracle calls for minimization of Pn i=1 vi(ui).

The structure of vi(ui) is the same as the structure of Pn j=1 gj(z) defined in (41). Therefore, the minimum of each vi(ui) is attained at the same point u i = u , and the k-th component of u is given by (u )k = νk, where

Since there is no communication constraint on ui, each node runs optimization process individually. Following the same arguments as for function Pn j=1 gj(z), we get the lower bound on the number of oracle calls

Lf µf log 1