Decentralized Optimization with Coupled Constraints
Authors: Demyan Yarmoshik
Alexander Rogozin
Nikita Kiselev
Daniil Dorin
Alexander Gasnikov
Dmitry Kovalev
Venue: ICLR 2025 Poster (2025)
Keywords: decentralized optimization
convex optimization
affine constraints
Primary area: optimization
TL;DR: Optimal algorithm and lower bound for smooth strongly convex setup

Abstract: We consider the decentralized minimization of a separable objective $\sum_{i=1}^{n} f_i(x_i)$, where the variables are coupled through an affine constraint $\sum_{i=1}^n\left(\mathbf{A}_i x_i - b_i\right) = 0$.
We assume that the functions $f_i$, matrices $\mathbf{A}_i$, and vectors $b_i$ are stored locally by the nodes of a computational network, and that the functions $f_i$ 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.

Published as a conference paper at ICLR 2025
DECENTRALIZED OPTIMIZATION WITH COUPLED CON- STRAINTS
Demyan Yarmoshik
MIPT; Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia ya Farmoshik www..k..dvdedeehhheeheec edu
Alexander Rogozin
MIPT; Skoltech
aleksander www.oogssysssssshhcccccooo
Nikita Kiselev
Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia; MIPT kiselev.ns www.:ss.wnddpsstechhhhmm
Daniil Dorin
MIPT borin..d@phystech. .ddu
Alexander Gasnikov
Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia; MIPT; Skoltech gasnikovE gasnikov@yandex.cx yandex. ru
Dmitry Kovalev
Yandex Research
dakovalev1@gmail com
ABSTRACT
We consider the decentralized minimization separable objective Σ (I(;; where the variables are coupled through an affine constraint Σ (A, - b,) = 0. We assume that the functions fú, matrices A,, and vectors b; stored locally by the nodes of a computational network, and that the functions f. 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.
INTRODUCTION
We consider the decentralized optimization problem with coupled constraints
min
Σ f((e)) s.t.
Σ (A,,, - b.) = 0,
(I)
ER
i=1
where for i E {l...., n functions fa R4 + R are continuously differentiable, A, E mgmxd and by I are constraint matrices and vectors respectively.

---

Published as a conference paper at ICLR 2025
We are interested in solving problem L in decentralized distributed setting. That is, we assume the existence of a communication network 9 = (V, E)) where V [1....,7, n is the set of compute nodes, and & C V V is the set of communication links in the network. Each compute node i E V locally stores the objective function fi(x;), the constraint matrix A; and the vector b;. Compute node i V can send information (e.g.. vectors, scalars, etc.) compute node j V if and only if there is an edge ji 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 al. (2011) Nedić et al. 2018), it writes as
n S.t. Σ
min Σ fi(x))
2 b,
where x; E R represents the quantities of commodities exchanged among the agents of the system, and b E 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 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, 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 x; E IR2 denote the voltage phase angle and the magnitude at i-th electric node, and let 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 formulate the necessary relation between voltages and power flows as a linear system of equations Σ;=1 A 8. An important property of the matrices A; that their compatibility with the physical network (but not necessary with the communication network). This means that for each row of the matrix .A....., An), there is node k such that A; k
can have nonzero elements in this row only if nodes and & are connected in the physical network, or
Consensus optimization. Related to the previous example is the consensus optimization Boyd et al. (2011)
min
fe(w))
s.t. I1
D2
Fn-
It is widely used in horizontal federated learning Kairouz et al. context of decentralized optimization of finite-sum objectives Gorbunov et al. (2022); Scaman et al. (2017).
(202). ) as well in the more general
To handle the consensus constraint, decentralized algorithms either reformulate it as Er W va, 0, where W, is the i-th vertical block of a gossip matrix (an example of which is the communication graph's 's Laplacian), or utilize the closely related mixing matrix approach Gorbunov et al. (022). Mixing and gossip matrices are used because they are communication-friente
calculating the sum E W 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 (T) by setting A, W, However, the principal difference between this example and (I) is that (1) does not assume A; to be communication-fie -frenddl.. We discuss the complexity of the reduction from consensus optimization to optimization with coupled constraints in Appendix
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. (20TT). Let F be the matrix of features, split vertically between compute nodes into submatrices F., so that each node possesses its own subset of features for all data samples. Let
2

---

Published as a conference paper at ICLR 2025
I E R denote the vector of labels, and let 24 E Rd be the vector of model parameters owned by the 2-th node. VFL problem formulates as
((211)+ + Σ ra(a)))
Σ F =
min
s.t.
FI E3
where l is 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 ( 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 30ononn3prreee preeennts the convergence rate of the method and the lower complexity we provide numerical simulations.
bounds. Finally, in Section
RELATED WORK AND OUR CONTRIBUTION
Decentralized optimization algorithms were initially proposed for consensus optimization Nedić and Ozdaglar (2009). based on earlier research in distributed optimization Tiitsiklis (1984); Bertsekas and Tsitsiklis (1999) and algorithms for decentralized averaging (consensus or gossip algorithms) Boyd et al. (2006); Olshevsky and T Tisisiklis (2009), which assumed the existence of a communica- tion network, as does the present paper. The optimal complexity for consensus optimization was first achieved with dual accelerated gradient descent in Scaman et al. (2017), where the method required computing gradients of Fenchel conjugates of fz). The corresponding complexity lower bounds were also established in the same paper. This result was later generalized to primal algo- rithms (which use gradients of the functions fx(x) themselves) Kovalev et al. (2020), time-varying communication graphs Li and Lin (2021; Kovalev al. (2021) and methods that use stochastic gradients Dvinskikh and Gasnikov (202T). Today there also exist algorithms with communication compression Beznosikov et al. (2023), asynchronous algorithms Koloskova (2024), algorithms for saddle-point formulations Rogozin et al. (202T) and gradient-free oracles Beznosikov et al. (2020),
making decentralized consensus optimization a quite dell-developed field Nedić (2020); Gorbunov et al. (022). 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 research direction. A 70o of distributed problems with constraints was investigated in Necoara et al. (201
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 these algorithms assume restricted function domains Wang and Hu (0022);
Liang al. (2019); Nedié al. (2018); Gong and Zhang (2023); /Zhang al. (2021 Wu al.
(2022). nonlinear incquality constraints Liang et al. (2019); Gong and Zhang (2023 Wu et al. (2022).
varevngrying graphs /Zhang al. 2021 Nedič al. (2018) or utilize specific problem structure Wang
and Hu (202)).
Works of Doan and Olshevsky (201)); Li et al. (2018); Nedić al. 2018) focus the resource allocation problem. For undirected time-varying graphs Doan and Olshevsky (2017) proposes first-order algorithm with O(Bryn') in communication and derivative computation complexity bound, where is the time required for the time-varying varying graph to reach connectivity. Li et al. (2018) applies combination of gradient
Table 1: Comparison of algorithms for decentralized optimiza- tion with coupled constraints
Reference
Oracle
Rate
Doan and Olshevsky (2017)
First-order
Linear
Falsone et al. (2020)
Prox
Sub-linear
Wu al. (2022)
Prox
Sub-linear
Chang (2016)
Prox
Sub-linear
at (2018)
Prox
Linear
Gong and Zhang 2023)
Inexact prox
Linear
Nedic et al. (001
First-order
Accelerated
This work
First-order
Optimal
Applicable only for resource allocation problem
3

---

Published as a conference paper at ICLR 2025
tracking and push-sum approaches from Nedic et al. (0177) obtain linear convergence directed time-varying graphs in the restricted domain case, i.e., 2, E Q2 where Ω2 is a nonempty closed convex set. Nedić et al. (2018) achieves accelerated linear convergence via proximal point method in the restricted domain case. When Ω = TR', they also show that Nesterov's accelerated gradient descent can be applied to achieve optimal O /Ve yKy In = communication complexity. In Gong method is proposed to solve problems with coupled affine equality and convex inequality constraints. Linear convergence is proved when the inequalities are absent, and S2 are convex polyhedrons. The papers Wu et al. (2022) Chang (2016), Falsone et al. (2020) present algorithms with sub-linear convergence.
and Zhang (2023) an inexact proximal-pone
As summarized in Table I no accelerated linearly convergent algorithms for general uffine-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 Amax (or (C)) and Amiin (C) (or miin+ (C). respectively. For vectors x; Rdd introduce a column-stacked vector col(z))..... Tmm (i] x T E R4. We denote the identity matrix by I E |R The symbol @ denotes the Kronecker product of matrices. By Cm we denote the so-called consensus space, which is given as Lm = {(11..... Vn) E (R"*)" : y1..... E 1 and = =... = }n and C.. denotes the orthogonal complement to L.m. which given as
(3) Assumption 1. Continuously differentiable functions f((z): Rd + R, i E {l...., n) are Ls- smooth and μ stronnyy convex, where L1 Z μt > That is, for all æ1, 02 E Rdd and i {1. .I....,n,, the following inequalities hold:
C (1y1,...,, -.un,,..,,,a Un) ) (RR"))" 91..... Un R. and y1 + yn -3.
H1 2
| - 2 =1122 (((o))))-((()))))) - (Vf((xi), - -xi) S Li x - x 111
By Ky we denote the condition number Kj L1/My.
Assumption 2. There exists x² = "ai...., IT)); xt E Bd. such that Σ (A b,) = 0. There
exist constants LA 2 PA > O, such that the constraint matrices A....., An satisfy the following inequalities:
max (A)
2 (Ai) S LA, iE(L......
max
PA S Amin (S)
where the matrix E Rmxm is defined as = IN A,A.. We also define the condition number of the block dick-diagonal matrix A = diag (A1...., An) E Ruaxd as KA LA/PA.
For any matrix M other than A we denote by T. and μM some upper and lower bound on its maximal and minimal positive squared singular values respectively:
Xmax (M M) omax (M)- < LM,
AM S o (M) Amin+ (M M).
(5)
We also assume the existence of a so-called gossip matrix W E R associated with the communi- cation network G, which satisfies the following assumption.
Assumption 3. The gossip matrix W is a n x n symmetric positivee semidefintte matrix such that:
1. We g # if if and only if (i.j) E or i j.
Wy = 0 if and only if y E L, i.e. y1
= yn-
3. There exist constants Law 2 po such that pww S X2 2 -W) and X2 N (W) T.w
4

---

Published as a conference paper at ICLR 2025
We will use dimension-lifter analogue of the gossip matrix defined W W Im- From
the properties of the Kronecker product of matrices it follows that X min' (W) = min (W) and
X Xmax = m (W). By kw we denote the condition number
Lww
Xmax (W)
(6)
Pow
m (W)
Moreover, the kernel and range spaces of W and W are given by
ker W = Li, range W Lt, ker W =Lm range L/
(7)
DERIVATION OF THE ALGORITHM
4.1 STRONGLY CONVEX COMMUNICATION REFORMULATION
Let W' be any positive semidefinite matrix such that
range W' (ker W') C.
(8)
and multiplication of a vector = ...,..., yn) E (R"" decentralized manner if its i-th block component yi stored at i-th node of the computation network. Similarly to eq. (6), we define
S by W' can be performed efficiently in the
Lw MoW
Amax W
KW
Amin (W')
Due to the definition of W and eq. 7 the simplest choice for W' might be to set W W. Later will specify another way choose W for optimal algorithmic performance.
Problem TT can be reformulated as follows:
min G(x, v) s.t. Ar + W b
(10)
ZER" (E(("))))
where the function G(v, :): Rd x (R + R is defined as
G(r, v) = F(x) + 2 Ar + + bl1
(11)
the function F(x:): Rd + R is defined as F(x)= E fi(x;). where x (x1,..., E Rdd the matrix A E mg is the block-diagonal matrix A diag (Ai...., A,). the vector b is the column-stacked vector b = col (bI....,bl, b,) ) E R and r, y > are scalar constants that will be determined later.
From the definitions A, b and C,,, (eq. 3 it is clear that (A,z, - b.) = if and only Az - b E C_ Since range W = C, the constraint in problem (TO) is equivalent to the coupled constraint in (1) For all x. satisfying the constraint, the augmented objective function G(x, is equal to the original objective function F(x). Therefore, problem (1O) is equivalent to problem (I.
The following Lemma shows that the function G(æ.y) y) is strongly convex and smooth.
Lemma 1. Let and be defined as follows:
PA LA
(12)
2L
Then, the strong convexity and smoothness constants of G(x, y) on RRd x Cu are given by
(1 rA + LA)
LA Lw
pG = My min
}
LG max Lj Hs.H
(13)
4LA
LA
pw:
Let the matrix B E mm (d+mm) be defined as B = [A 7 W']. The following Lemma connects the spectral properties of B, A and W
5

---

Published as a conference paper at ICLR 2025
Lemma 2. The following bounds on the singular values of B hold:
2 min
B
MB
PA
2
max
(B) S LB
LA (LA + HA)
Lw
pw
(14)
and
0
B
LB
Lw
(1 + HAi)
max
KB
=2
KA + j'w'
(15)
min+
(B)
JBB
Proofs of Lemma I and Lemma
2 are provided in Appendix B
4.2 CHEBYSHEV ACCELERATION
Chebyshev acceleration allows to decouple the number of computations of the objective's gradient F()) from the properties of the communication network and the constraint matrix - specifically, from the condition numbers Kw and KA- The Chebyshev trick enables to replace the matrix with matrix polynomial with better condition number.
Consider some affine relation Mu and let PM be a polynomial such that PM = A for any eigenvalue À of M M. Note that here we interchangeably use P as a polynomial of a matrix and polynomial of a scalar. We denote any feasible point for the constraint Mu d as uy- Then,
Mu = d + M(u uo) 0 ( M MMMMME M(u un) 0
PM M) un) = @ PM(MMM)(u - ua)
where (a) and (c) is due to ker M MM= ker M: (b) is due ker PM (MMM) ker M M by the assumption about (A).
Following (aaim al. (2022a) and Scaman al. 2017)
the translated and scaled Chebyshev polynomials, because they are the best at compressing the spectrum (Auzinerr and Melenk (011)).
Lemma 3 (Salim al. (022a)), Section 6.3.2). Consider matrix M. Let &
[
Lma
PM
V Domaz
A min' (M M) Define (ta(t) 1 ([LLMttM-22/(Lxxt
Amaax ( M)
Th((LM+ppa) (MM) where Te is the Chebyshev
polynomial of the first kind of degree n defined by Te(t) = (1++ + v -V-V--1))
Then, (0) 0, and
19
Amax (PM(M - max PM(1)=
(16)
15'
11
Amin
(PM(M' M))
min Leal
PM(()=
(17)
15
Results of this section are summarized in the following Lemma
Lemma 4. Define
W P VW WW) (W)
(18)
and
K V P
(19)
Let G(u) G(z, Rd chh and b' (Pa(B B)u Then, problem
min NEU
G(u) S.l. Ku=b'
(20)
an equivalent preconditioned reformulation of problem 10 and, in turn, of problem
4.3 BASE ALGORITHM

---

Published as a conference paper at ICLR 2025
Our base algorithm, Algorithm 1
Algorithm 1 APAPC
the Proximal Alternating Predictor-Correctorr (PAPC) with
1: Parameters: v E a. 0, (0,1)
2: Set ul = u.. 20 =EE
Nesterov's acceleration, called
Accelerated PAPC (APAPC).
3: for k = 0,1,2,... do
It was proposed in Salim et al. (2022a) to obtain an optimal algorithm for optimization problems formulated as (20).
4:
u = =ru + (1 (0-T)am u
+ = (1 + n1a) - (u (VV((u)) auf + 2*))
6:
*+1 = =² + 0K (K + b))
u+1 (1 n0) (u* 17 VVG((u)) - only 2()))
See Kovalev et al. (2020); Salim
8:
k+1 = u + 2r
(u k+1 - u*)
ett al. (2022b) for the review of related algorithms and history of
-
9:
end for
their development.
APAPC algorithm formulates as Algorithm D and its convergence properties are given in Proposi- tion |
Proposition (Salim al. 2022a). Proposition 1). Assume that the matrix K in 20 satisfies
μK and b' range K, and denote KK
Lx. Also assume that the function G is LG
smooth and stronnyy corvex. Set the parameter values of Algorthim 1 as = min
2 KK
1 TFLa 0 = wp and P.g. Denote by u² the solution of problem 20 and by z the solution
of its dual problem satisfying 2" E range K. Then the iterates u², 2tth of Algorithm 1 satissy
L wz 0(1 + nn)
n1
[|(KT) - =211
(21)
2(1 T) -T - u²) s 1+ -min VVECKK
11 KK
1)
x
min
C.
where C= = 1 b11=00 - 2(1-)) Do(u,,"", u²), and DG denotes the Bregman divergence ofG, G. defined by DG(u',u) G(u') - G(u) (VG(u), -
MAIN RESULTS
5.1 ALGORITHM
As stated in Lemma problem (20)
Algorithm 2 Main algorithm
is equivalent to problem
Due
1: Parameters: n0 E RRdd n. a 0, E (0,
to Lemma I its objective is strongly con-
2: Set y = - (RRm), yn u = (x )²),
vex. allowing us to apply Algorithm M to
3: u² = uu, 20 =0 Rd x (Rm)a
it. Using Lemma 3 we obtain that the con- dition numbers W' and K are bounded as O()), but single multiplication by W and K, KT translates to O( /tw) multi- plications by W and O( ((/FB) multiplica- tions by B. respectively.
for k 0. 1, do
5:
" = =ru* + (1-r)up
g = grad _ - only
7:
" = (1 + na.) 1
ng + +)
8:
++1 = z² +0 +..K.
K Chebyshevlu
We implement multiplications by W' and K, K" through numerically stable Cheby- shev iteration procedures given in Algo- rithms 3 5 which only use decentral- ized communications and multiplications
9:
u k+1 = (1 + +na)== I n615 + 2 xk1))
10:
uf
k+1 = up + 2x (u
k+1 - w²)
11:
end for
by A, AT. Lemmas L to allow us to express the complexity of Algorithm 1 terms of the parame-
ters of the initial problem given in Assumptions t All this leads us to the following Theorem
detailed proof of which is provided in Appendix B.3 as well as the derivation of Algorithms
and values of the parameters of Algorithm
Theorem 1. Set the parameter values of Algorithm 2 as = min {1,
2
14 max
7 47 max Bu 0
15.
and 41 Denote by x² the solution of problem
19y
7

---

Published as a conference paper at ICLR 2025
Algorithm 3 mul (y): Multiplication by W
Algorithm 5K Chebyshev(u)) Computation
I: Parameters: y
of K (Ku -b)
2: p = (VLW
//W) 2 /16
1: Parameters:
(z,
3: V == (VLw + (PW) /2
2: p = (LB μBB /
4: 8 = -V/2, n= kRw
3: V = (Ln + pBB
4: 8 -v/2, n = VEB
5: p = Wy/v, y² == + +p
5: q" Ax + mulw' (1)
6: for I..... 1 do
7:
8 = p/8'
6: p =
A A
8:
8 = (v + B(-1)
mulw' (4")
9:
p' (Wy' 3i-1pp
pppp"" 1 18
7: u u + p
y yy +pp
8: for = 1,..., n1
1 do
11: end for
9:
8- p/8-11 -
Output: y y"
10:
8¹ = (v (1+8+-1 1i
(x'
u²
Algorithm grad_Gaaa_a G(u): Computation of VG(u)
12:
O' = Ar + mul
(y)) - b q'
13:
p =
8 mulw (q¹)
+
1: Parameters: u = (I,
2: := 7. mulW (y) b)
8 1--1p-1188
3: Output: (F(x)) + A
14:
" == u² + p
x (7-mul mulW' (z)
15: end for
16: Output: t
Then, for every > 0, Algorithm objective's '' gradient computations, O ( /RA log(1/E)) multiplications by A and AT, and ( FKw log(1/e) communication rounds (mulliplications by W).
2 finds xe for which 1| x²1 S using (V log(1
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 al. (2017) and discrete time Kovalev et al. (202I) are used. We use the latter discrete time formalization. We assume that the method works in synchronized rounds of three types: local objective's '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 d, locally held vectors Iy, they cannot commu- nicate these vectors directly. Instead, the nodes exchange quantities A;æ; Imm.. For this reason, we introduce two types of memory M,(k) and Hk(k) for node at step k. Set MM:k) stands for local memory that the node does not share and (4))) denotes the memory that the node exchanges with neighbors. The interaction between (A) and (k) is performed via multiplications by A; and A."
Memory is initialized as M,(0) = {0}. H.( = {0}. Below we describe how the sets M,(k), (k))) are updated.
Algorithm performs local gradient comutation round at step k. Gradient updates only operate in M2(k) and do not affect (k). For all e V we have
Mi(k + Span {z, ff((z), (z) z ZE M((k). H4(k HH,(k)
where f the Fenchel conjugate of ft.
2. Algorithm performs local matrix multiplication round at step k. Sets H4(k) and Mz(k) make mutual updates via multiplication by A, and A,T. For all E V we have
Mi(k + 1) Span (A. b,, A, y E H.(K)) H2(k 1) Span Ar: M,(k))
Algorithm performs a communication round at step k. The non-shared local memory M,(k) stays unchanged, while the shared memory Hi(k + 1) is updated via interaction with neighbors. For all
8

---

Published as a conference paper at ICLR 2025
i V we have
M, = -M,(k) Hi(k + 1) Span (H2(k): (i.5) EJ.
Under given memory and computation model, we formulate the lower complexity bounds.
Theorem 2. For any L5 > 2 > 0, Kw 0 there exist L μ1 sst-oongy conve
{f.)= matrices A; such that KA = L μA (where LA PA are defined in (4)), and a communi-
cation graph 9 with corresponding gossip matrix W such that kw = Amax ( (W) min (W),for which any first-order decentralized algorithm on problem ① to reach accuracy requires least
)))
NN =Ω
Vky log
-
gradient computations,
)
NA = Ω
VieyVRA log
multiplications by and AT,
(
Nw = Ω
(VETVRA Kiw log
communication rounds (multiplicaaiios by W).
A proof of Theorem 2 is provided in Appendix
EXPERIMENTS
The experiments were run on CPU Intel(R) Core(TM) 19-7980XE, with 62.5 GB RAM.
Synthetic linear regression. In this section we perform numerical experiments a synthetic linear regression problem with Ezrreullarizatio:
min Be ERA;
s.t. (A - b;) = 0, 1 Caa - d:13 1
(22)
where we randomly generate matrices C, E xd: A, Rondd and vectors d, R. b, R" from the standard normal distribution. Local variables zj E Rd. have the same dimension d. equal for all devices. Regularization parameter 0 10-3, In the Fig. we demonstrate the performance of the our method the problem, that has the following parameters: Ky = 3140, KA 27, Kw 89. There we use Erdōs-Rényi graph topology with n = 20 nodes. Local variables dimension is d, = and number of linear constraints is
10. We compare performance of A Algorithm| 2 with Tracking- ADMM algorithm Falsone et al. (020) and DPMM algorithm Gong and Zhang (2023). Note that Tracking-ADMMi and DPMM proximal algorithms that solve subproblem 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.
10a
10a
10a
Traekeng-AMMI
Treckig-ADMMi
Tradkigg-DMMt
10-1
DPMM
10-1
DPXM
10-1
DPMM
10-1
Main alporithm
10-3
Main alg
10-5
algorithm
10-9
10-31
10
10-18
10-
10-
10-
0.0
0.2
0.6 Gradleen calls
0.4
0.8
1.0
2 Mult. by A and A
Commoun
Figure 1: Synthetic, Erdös- graph, n = 20, d, = 3, m = 10
VFL linear regression on real data. Now we return to the problem, that we have announced the introduction section. We apply VFL in the linear regression problem: is typical mean squared loss

---

Published as a conference paper at ICLR 2025
function, that is (221 1 21.2 and fg-regularizers, i.e. rz(2;)
2 To adapt this
from (2) to D redefine 21 and x2 22..... , In = Fnn Thus, derive constraints
matrices as in the T
A F1 I),
A 1 =
FiwI
(23)
n
= i 2....;
A
Σ
(24)
For numerical simulation, we use mushrooms dataset from LibSVM library Chang and Lin (001T).
We split m = 100 samples subset vertically between 7 devices. Regularization parameter 10-2,
The results are in the Fig.
10'
10
108
TYacking-ADMMM
Tracking-AIMMI
Trocking-ADMM
10
DPMM
10-2
DPMM
10-2
DPMM
Main algorithm
Main algorizhm
Main algarithm
10"1-
10.1
10"
10-
10
10-10 50
10-24
10-14
10-14
10-14
10-15
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.5
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Gradient
x100
Mult. by and A
x10P
Communications
x10
Figure 2: VFI., Frdös-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 involves many communications per iteration, in contrast to DPMM and Tracking-ADMM, which make numerous gradient calls per iteration.
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-20-222100020 dated 22.11. 11.201,, identifier 0000005507521QQL00000)
REFERENCES
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) Jamuary 2011. ISSN 9935-8237 10111..1561/2200000001 URL http:
doi //ot:ccl..orr/00.1555//0000000.0
Angelia Nedić, Alex Olshevsky, and Wei Shi. Improved convergence rates for distributed resource allocation. In 2018 IEEE Conference Decision and Control (CDC), pages 172-177. IEEE, 2018.
Kenneth J Anrow and Gerard Debreu. Existence of an equilibrium for competitive economy. Econometrica: Journal of the Econometric Society, pages 265-290, 1954.
Alejandro D Nominguez-Garriin Stanton T Cady, and Christoforos N Hadjicostis. Decentralized optimal dispatch of distributed energy resources. In 2012 IEEE 51 IEEE conference on decision and control (CDC), pages 3688-3693. IEFF, 2012.
Yamin Wang, Lei WU, and Shouxiang Wang. fully- delltddecettrllized consensus- based admm approach for dc- with demand response. IEEE Transactions on Smart Grid, 866)2633722677, 2016.
10

---

Published as a conference paper at ICLR 2025
Haixiang Zhang, Ying Chen, and Javad Lavaei. Geometric analysis of matrix sensing graphs. Advances in Neural Information Processing Systems, 36, 2024.
Jingwei Yang, Ning Zhang, Chongqing Kang, and Qing Xia. A state- snte-independent linear power flow model with accurate estimation voltage magnitude. IEEE Transactions on Power Systems, 32 (5):3607-3617, 2016.
Kenneth Van den Bergh, Erik Delarue, and William D'haeseleer. De power flow in unit commitment models. no. May, 2014.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances 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 Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
Angelia Nedić and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions 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 Bertsekas and John 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, 5256)22500 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. arXiv preprint urXiv:2104..0 (tti:::22042259900 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 Ill-posed Problems, (9(3):355-055 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. arXiv preprint arXiv:2102.00755: 2021.
Aleksandr Beznosikov, Eduard Gorbunov, and Alexander Gasnikov. Derivative-free method for composite optimization with applications to decentralized distributed optimization. IFAC- PupersOnLine, (3(2):408-40443 2020.
Angelia Nedić. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine, 37(3):22-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? 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 Automatic Control, 57(1):151-164 2011.
Ion Necoara, Valentin Nedeleu, 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. arXiv preprint 1XXX:44401.439 2014.
Ion Necoara and Valentin Nedelcu. On linear convergence of 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. arXiv preprint arXiv:2203.00955. 2022.
Shu Liang, George Yin, al. Distributed smooth convex optimization with coupled constraints.
IEEE Transactions on Automatic Control, 65(1):347-355 2019.
Kai Gong and Liwei Zhang. Decentralized proximal method of multipliers for convex optimization with coupled constraints. arXiv preprint arXiv: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 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- for distributed constraint-couple optimization. Automatica, 117: 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. Accelcrated convergence algorithm for distributed constrained optimization under time-varying general directed graphs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 50(7):2612-222,, 2018.
Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization time-varee varying graphs. SIAM Journal Optimization, 27(4))2597-2633, 2017.
12

---

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-4499 PMLR, 2022a.
Winfried Auzinger and 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):002-330 2022b.
Yurii Nesterov. Introductory Lectures Convex Optimization: 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. 20910000144///61111119111110 URL
https: //ttps///oi... wwg.oogggoooooooo /10. 1145/1961189.... 19611999.9999999
Martin H Gutknecht and Stefan Röllin. The chebyshev iteration revisited. Parallel Computing, 28(2): 263-283, 2002.
13

---

Published as a conference paper at ICLR 2025
APPENDIX / SUPPLEMENTAL MATERIAL
A REDUCTION OF CONSENSUS OPTIMIZATION TO COUPLED CONSTRAINTS
As mentioned in Section the consensus optimization problem
min EIR fi(mi)
s.t.
During the review process, we were asked whether the complexity of Algorithm 2 could be reduced to match that of optimal algorithms
can reduced to the problem with coupled constraints T
for consensus optimization Scaman et al. 2017)
It turns that, for 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 complexity lower bounds in Theorem 2 and the following lower
vn. This conclusion is based bound on KA for any suitable matrix A.
Let d 1. Consider arbitrary horizontal- matrix A' = (A1 ... An) R such that ker A' Li Span(Ta) which corresponds the consensus constraint. By definition 44. have
HA
-mmin+ 71
Σ
a
Amin' - (A'AT)) 02
min (A'),
n
72
and
LA max o (=1... max (A,) ||A
where i" denotes the index of the column achieving the maximum. We can upper bound the minimal positive singular value using vector v, whose components all zero except for one and one 1, implying |||² 2. Since the sum of its components is zero, is orthogonal to ker A', thus
min+ (A') =
min ||
|A'ul//|lulf S | - A/1l - A 112
III
follows that
LA
A 1
RA
PA
A |
This bound is nearly tight, because we can achieve KΛ matrix or the incidence matrix of complete graph on nodes.
by setting A' be the Laplacian
Substituting this into the complexity lower bounds in Theorem communication rounds is lower bounded by Ω (/FrVn log for any choice of A, while the optimal complexity for first order decentralized consensus optimization is O (yns new log (t))
we find that the number of
B
MISSING PROOFS FROM SECTION
B. PROOF LEMMA I
Proof. Let Da(a', s/: xx,yy) y) denote the Bregman divergence of G::
Dola', v'; G(x',v) G(x, (V.G(z, -x) -VV -)) (25)
14

---

Published as a conference paper at ICLR 2025
The value of PG be obtained follows:
Da(x' ,3:;,,)) = (=(x';x)= + 2 A - -)) + 7 - 3]1
(a) μ4 |0' =1|2 || 7W w)11
2
1 | - x|I2 + r
Al - -x)ll =r([2+r(AA( +r( - 2), ,), v))
2
+ 2 12 W''0 -y]
1 1z' z112 + 4 11 11:W'(' (v' - w)12
2 A - x)
r
2
(c) 11 1/' z|12 2 pw 11 y/1
PLA
1| x1
2
2
(
14 |0
x11? +
"y? pw
11 ull?.
4
8LA
( Pf min
1 2'
PA + LA
2
2
4LA
1/
where (a) is due to Assumption (b) is due to Young's s inequality; (c) is due to Assumption 2 y' y C, eq. and eq. 5 (d) and (e) is due to eq. 12
The value of La can be obtained as follows:
Da(#' 1o(1/,8/22. v)
(=((<;)) + 2/2 A - x) +
+) W 9)12
(a) Lf | x/12 + - A - x) >w' - y)1
2
2
(6) Li
$
||
11 + r|1 W (3/ 1)11 A - x))1
(c) Ly || arl2 + m Tww 110 - v112 + rTAll x11
2
(4) L Ms | x/| -x11?
2 11 y11
2LA
( maxx Ls + WJ
PA +
LA
Lw
x x
LA
pww
y
where (a) due Assumption 1 (b) is due to Young's inequality; (c) is due Assumption 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 E (Rm"):
B T 2|| = ||T =11 + W'> 12
(a) (LA + 72 ]w
( LA + (LA PA)
Lw pw,
||
where (a) is due to Assumption 2 and eq.
5): (b) is due eq.
To derive the formula for μıB, first of all, note that by eq.
(ker B ) range B = range A + range W' = range A + C.h.
(26)
Let 2 E (ker BT) = u + v. where (u....., u,,, 0 = (vg...., E (R"")" such that u E C
and
L.--
15

---

Published as a conference paper at ICLR 2025
We can show that vo range S. In order to do that, let show that (Vo, wo) 0 for all wo ker S.
Let w = (w...... wo) E Cm- The fact that wy E ker S and w E Lm implies w E ker AA
ker A Hence, it is easy to show that ker B (range B) L. Then, we obtain
(u +u w) = (2, w) ( 0,
novo, wo) (v, w)
where (a) follows from the definition of v and w; (b) follows from the fact that u E f. and Lmi (c) follows from the fact that range B and E (range B)+, Hence, uo E range S.
Further, we get
B =||
(a)
| (u + + Ih +)ll
A
(u v))2 2 I
|| A T (u + u) + + uw ||/1|
|| T "Il + || u11 + 2(A T u, A v) + ||/l
(4)
| T u/1 #
A u11 + + |/112
@ | T
u1
+
(uD. nSvo) + +>2
ww ||/1|
2
S
2
+ 1UAAA
| 2 + ww ||u||
LA
|1/2 2 +
μA
||a|| P 22222p0 (/ww
MA
||0|2
+ 1//
2
PA
||
2
where (a) and (h) is due to the definitions of and (b) is due to the fact that Lmi (c) is
due to eq. (5) and eq. (8); (d) uses Young's 's inequality; (c) is due to the definitions of v and S, and
A
|A (ATul]) u/|2
20 = (vo. Ei A.A, vo) (Su)): (f) is due to Σm
A
Assumption and the definition of e; (g) is due eq. 12
B.3 PROOF OF THEOREM I
Lemma (Salim al. 2022a). Section 6.3.2). Let M be matrix with μM > E range M and
Mu = r. Then PM M M) - vn) = = Cheeysshe(y,MM)) where Chebyshev defined
Algorithm 6
16

---

Published as a conference paper at ICLR 2025
Algorithm 6 Chebyshev(1, M,, Chebyshev iteration (Gutknecht and Röllin 2002 Algorithm
4)
1: Parameters: v, M.
2: n == V PM
3: p = (LM - UMM) 2
/16, == (LM + uN)/22
4: 8 = -V/2
5: pd
M (Mu -r)/v
6: r = U + pd
7: for 1, ,,..,
do
8:
-- = p/6'-1
9:
8' (V + Bi-1)
10:
p¹ = M (Mv'
r) + 11-1p-11)/1
wit1 o² pd
12: end for
Output: T
Proof of Theorem [
Proof. Applying Lemma to W and B B, derive that, due eq. 18). holds
max W') S Lw = (19/15)²,
(ain-(W") 2 pw = (11/15)²
(27)
and by eq. 66) the polynomial Pw has degree of [ Similarly, due to eq.
(19 holds
max Amax
K KKK- S LK 19/15,
o2 min-- (K) Amiu (K K
k 11/15, (28)
and since KB
La
the polynomial PB has a degree of [v MB
We implement computation of the term K (Ku - b') in line of Algorithm Lemma
1 via Algorithm
5 by
5
K T (Ku b') K K(u un) PB(B B) uo) Chebyshev(u, b) K Chebyshev(u).
Similarly, utilizing Lemma
we get
W'y = PWw(Wyy Pww VW)
= y- Chebyshee(y,, WW0) 0) = mulW (3). (29)
where mulW" is defined as Algorithm
Therefore, Algorithm is equivalent Algorithm
From eqs.
13 and (27
LA+LA < 2 and (19/11) I 3, get
LG max
Ly uS
"A +
LA L
pw. }
S ny max {1 + kg, 6).
(30)
LA
(1 ar LA
nG = My min
(31)
2 4LA
LG
KG
< 4max (1 + Kg, kg, 6).
(32)
NG
From eqs. 15 and 27 get
LB
KB
< 2 (NA + (19/11)(( < SEA +6.
(33)
PB
From eq.
we obtain
LK
KK
19/11.
(34)
PK
17

---

Published as a conference paper at ICLR 2025
and substituting eqs. 32) and (33) to Proposition 1 obtain as its direct corollary that i
O Olyny log(1/E)) Each iteration Algorithm 2 require O(1) computations of VF, O(vBB) = multiplications by A, A and Oly multiplications by W. which gives us the The values of the parameters T, in Theorem are derived from
O(YRA) RA
statement of Theorem I
Proposition follows. We have min {
AK Na
min 1, 2/ 44 ++
due to
2
eqs. 32) and 334 7
due to eq. (30;; 0 19g
15 due to eq. 28 and
4rLG
max (1yt15.0pp Gpz
PG due eq. 31
C PROOF OF THEOREM! 2
C.I DUAL PROBLEM
Let us construct the lower bound for the problem dual the initial one. Consider primal problem with zero r.h.s. in constraints
Σ fi(es)
min Ele
(35)
s.t.
A
= 0.
i=1
The dual problem has the form
min #i El2
max
Σ f((m)) (z, Arti)
=
max
max
Σ
[A] 2, - fi(ees)
Fi Rn El2
1=1
(36)
min
=).
Introducing local copies of u each node, we get
n
(x(()) = Σ = (A 2)
min
(37)
i=1
i=1
s.t. W =0
C.2 EXAMPLE GRAPH
We follow the principle of lower bounds construction introduced in Kovalev example graph from Scaman et al. (0177). Let the functions held by the nodes be organized into path graph with n vertices, where divisible by 3. The nodes of graph G (V, E) are divided into three groups V = f1....,,n// 1/2 {n/3 .n..,,n./33 V2 {2n/3 + 1. n) of n/3 vertices each.
2021 and take the
Now we recall the construction from Scaman et al. (017). Maximum and minimum eigenvalues of 1+
path graph have form Amax (W)
+ cos I A (W) 2 (1 cos F). Let Bn 1-cos
Since 3n, "="" +o0, there exists n. 3m such that 8, Kw 8.43. For this n, introduce edge weights w1,++ = al {i = 1}. take the corresponding weighed Laplacian W, and denote its 1, the network is disconnected and therefore x(
condition number 1: (W.). we have x(W,) = 3 By continuity of Laplacian spectra we obtain that for some E [0, 1) it holds
cc. If a
<(W.) kw. Note that π7 z1/(n + 3) E [0, 1/33 for x E [0, x/3) it holds
cos x 2 x² /4. We have
π + cos
72(n 3)2
288n²
NW S Bx43
n+3
I 32n
VEW S 4 = O(n).
cos
n+3
2
n2
(38)
18

---

Published as a conference paper at ICLR 2025
C.3 EXAMPLE FUNCTIONS
We let e = (10 0)* denote the first coordinate vector and define functions
f((,,)) - Hf
LA el
L |1!1.
p
(39)
2
We immediately note that each f. is -smoooh and μu stronnyy convex. The first term has the form
2 I|p+ ceill and its convex conjugate (44 |pp + cei c=ill²)* max, {(u, p) M1 |pp cei | The
gradient by p 1y + ce1) O, thus p My u - Del and maxp (u,p) 4 lp + ce 11 = [ull" 2ps
cu1 Correspondingly.
VLA
1
(u,
|1212
1
u1
2p
2L,
2p1
To define matrices A, we first introduce
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
-1
E
E2
0
0
0
1
-1
0
0
0
0
Let LA = L
3ua, A
2
LA and introduce
VLA VAAll, ie V1 A O
0 l. iE V/2
WLLAT VPAT,
iE V/3
Let us make sure that the choice of Ar guarantces constants LA HA from
max Amnax ( (A,AT)= Amax (IΛE EI 24. + PiA L.A.
1 (1AE, E2 + +BA)) min (H Ei + +
A
= A
min
1=1
2
3 LA PAA
Let M = (-1 -
and
0
0
M
0
M E E
M2 = E.J Eg
0
M
0
M
The dual functions take the form
Bpy
LA 2 + 1 2
2L,
24F
LA
21,
iE V1
(x=)= (AT
0,
i V/2
LA 22 21,
1 1V
LA 21
i V/3
3py
24r
LAM, + 24T) 2-
L.
14
My
2pr
21,
iE V1
0,
iE V2
(40)
12
LA M, + BA1) 2-
La 21,
i V/3
My
2p
19

---

Published as a conference paper at ICLR 2025
Therefore, have
10 Σ 9x(2)
n
LA
2T (M1 + -M)2+
PA 2
L
21
24s
Ls
Ms
1=1
(41)
LA
jAPS 2T22
M 21
3 P
La
where
2 -1
0
0
-1
1
0
M M1 + M2
0
1 2
-1 0
Now we formulate the lower complexity bounds for Ei=1 96(2), where ge (2) are defined in (40
C.4 DERIVING LOWER BOUND
Lemma 6. Function E 9i(z) attains its minimum at 2² = { k= where
2L 1
PAPT
2ALL P
+1+1
PAPS
Proof. In the lower bound example in (Lemma 1 in Appendix C) Kovalev et al. 2021 it was shown that function
3p
h(2)
2"
M2
L- p
21
attains its minimum at 2 = p², where
21
+ 3
34
2L
+ 1/4 +
3p
Let us deduce the expression for L/ in terms of LA, Ly.HA.My. We enforce h(2)= = - 9:(2) and set
3p PARS # = LaIg
L- 1 LaL,
PAPS
Therefore, h12)) attains its minimum at ph, where
2LALi
PAPS
p
2LAL
+1+1
PAPI
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 σ0 = (otherwise we can shift
the variables accordingly). thus M,(0) = (0), H.(0) = {0).
Lemma Let (k) denote the maximum index of a nonzero component of vector blocks p, t held by i-th node step k in its local memory M,(k) and vector held by i-th node in its local memory Hk(k), ie.
M,() S (0) and H.(k) S (0)
min {s E (1,2....) H,()) S Span ees
sk())
and Mc(k)) Span (c1, .c.....,ee ex) fei,..., es) } else.
20

---

Published as a conference paper at ICLR 2025
Let Kig denote the number of algorithm step by which exactly q communication steps have been performed, where q 2 0. For any k E {l....,ku :.g) we have
4
max 8: (l) S 2
(42)
+1
Proof. If the method performs a multiplication by A,, it transfers the information from M,(k) to
(k)k). If multiplication by A! performed, the information is transferred the opposite direction,
i.e. from (k) Mi(k). If the method performs matrix multiplication step (either by A or A )
then from the structure of A; we obtain
- (si(k) mod 2),
E Vi
8; + 1) S sk()) +
0,
i E 1/2
(si(k) mod 2),
E V/3
We will prove that 1. For 2 + 1), E {0, 1, 1.... we have
1 + 20, iE Vi
s((ky)
1 1 28, E V/2
(43)
2 22, iE V/3
For g = (26 + 1)(n/3++))))1 + 1), Le {0, (0,1,....
we have
2 (28+1), +1, iEVi
(k₂) -
(26 + iE V/2
(44)
(26 iE V/3
The proof follows by induction.
Induction basis. Let = 0. From definitions of fi and A; it follows that
1. i V1
sk(o)) 5
0, i i V/2
2, i V/3
Therefore, for q = 0 our statement holds.
Induction step for (2f + () + 1). Consider = n/3 20(n/3++
1). From 45) we
have that for the spread of nonzero components from V/3 V 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 26(n/3 1). The proof follows by the same argument as for q (2l 1)(n/3 1).
We just proved the statement of lemma, i.e. relation 42 for divisible by (n/3 + 1). Between such checkpoints, the information (i.e. the number of nonzero components) traverses nodes of 1/2 and therefore max; (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 be obtained from the solution of its dual (36)
Viaa P1
(E(e)2* -c1) -())
-11)
<=(=)) = P: (A xn)
Vāa T.5
Therefore, denoting
رi T.7.
8
80
|
z 2 ||t
1
(t.))
Σ
(27)² ==
=a
2
(1)1
(k)
(k)(
2s, 2s,(k)+ (k)+2
6+2
n78
1
(a)
0
6+ 2g
2n73
(6)
12g
1
p2
p
a
1
p2
p
P
0
p2
0
21

---

Published as a conference paper at ICLR 2025
where (a) holds since n/3 2 1; (b) holds due
38
Following Kovalev et al. 2021 D, we obtain that
2UAR LALS
p 2 max 0, 0,11-3
Therefore,
30 v'W
2RAp Labj
|
2:122 a
max
0, -3
p²
follows that the number of communications is lower bounded as
LALS log
Nw 2 Ω
Vew
(45)
and the number of matrix multiplications at each node is lower bounded as
LALI
log (t)
NA 2
(46)
C.5 LOWER BOUND ON THE NUMBER OF GRADIENT COMPUTATIONS
To get the lower bound on local gradient calls, let us consider a problem
Σ f((x)) + Σ (u()
min Zi ye My ERR
(47)
S.t. Σ A,4 =0
where all fx()) are defined in and all (u:)) are similar and defined as
39
L u, Mu,
H1 "
Lg u1
v. (w,)
8
2
4
First, note that each (u, is Lm-shh and uy-strongly convex, i.c. problem (47 satisfies the assumptions of Theorem 2
Problem (47) falls into two independent parts. The first part is minimization of Em fe(x;) subject to constraints and is identical to (35), while the second part is minimization Σi=1 0/ (1()) 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 of E
by Nw in 45) and NA in 46). It remains to lower bound the number of oracle calls for minimization
1= (u.).
The structure of (u;), the same the structure of ΣØ= gj (2) defined in Therefore, the minimum of each vi (u;) is attained at the same point un u², and the k-th component u" is given by (u" )x 2 where
L1
PJ 3
Lt + 2 +1
PJ
Since there is no communication constraint on u; each node runs optimization process individually. Following the same arguments as for function Σn Ij (=),, we get the lower bound on the number of oracle calls
Lا log Hl
( )
N₂ 2 Ω
22


Reviews:
[{"review_id": "lR3NOhLaPH", "reviewer": "Reviewer_Rp6n", "summary": "This paper studies decentralized optimization with constraints. It establishes the lower bound for this problem, and develops algorithms to attain such lower bound. The main idea is to transform the original constrained decentralized problem into (20), and then rely on the algorithm APAPC to develop the optimal algorithm. Numerical algorithms are established to validate the theoretical findings.", "questions": "1. As noted in the introduction, unconstrained consensus optimization is a special case of problem (1). For this special case, can the complexity of Algorithm 2 be reduced to match the optimal complexity of the unconstrained consensus algorithm in (Scaman et al., 2017)?\n\n2. In the simulation section, how do you tune the hyperparameters?\n\n3. The simulation results appear somewhat limited. It is difficult to observe whether the complexity scales proportionally with $\\sqrt{\\kappa_f}$, $\\sqrt{\\kappa_A}$, and $\\sqrt{\\kappa_W}$, as established by Theorem 1. It would be beneficial to empirically validate the complexity of the proposed algorithm, particularly with respect to $\\kappa_f$, $\\kappa_A$, and $\\kappa_W$.\n\n4. It is recommended to evaluate the algorithm using more real-world datasets and more complex experiments, such as logistic regression.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well-written and presents several key strengths:\n\n1. The reformulation from problem (1) to problem (20) is novel and insightful, providing a strong foundation for the development of an optimal algorithm.\n\n2. It establishes the first lower bound for decentralized optimization under affine constraints.\n\n3. The paper also develops an algorithm that attains this lower bound, demonstrating both the tightness of the bound and the optimal complexity of the proposed algorithm.", "weaknesses": "However, this paper has several notable weaknesses:\n\n1. The novelty is limited. The core idea for constructing the optimal algorithm draws heavily from the APAPC algorithm (Salim et al. 2022a) and Chebyshev acceleration, a common technique in accelerated algorithms for unconstrained decentralized optimization. The authors combine these two techniques to create the proposed algorithm.\n\n2. Another concern is the practical applicability of the proposed algorithm. While it achieves theoretical optimality, it is significantly more complex to implement than existing baselines. As shown in Algorithms 2-5, the proposed algorithm consists of multiple algorithmic blocks and introduces numerous hyperparameters—such as ρ, ν, δ, and p—that require tuning. These factors collectively detract from its practical value.\n\n3. The numerical experiments are too trivial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nylVa5gvDS", "reviewer": "Reviewer_HQPK", "summary": "This paper studies the task of decentralized optimization under the coupled constraints setting. This setting is quite general, which recovers a wide range of existing problems such as the consensus problem, optimal exchange problem, etc. Using a multi-communication subroutine, the paper proposed a dual-loop algorithm that provably converges with fast and tight convergence guarantees.", "questions": "Currently, the lower bound is based on the algorithmic structure of the proposed algorithm, where the communication round lower bound is dependent on all three condition numbers. Is there a way to get an algorithm that only requires operations that only depend on their own respective condition number?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors provided a solid discussion on the related literature, which clearly explained the relative position of this paper with respect to multiple approaches in the prior works. The introduction also was able to convince me the generalizability and significance of this work.\n\nThe theoretical results offered by the authors, if correct, is tight and optimal.\n\nThe connection between FL and decentralized optimization has long been established. The coupled constraints setting considered in this paper can be a good starting point for technical understanding of VFL.", "weaknesses": "Although the upper bounds and lower bounds are provided in this paper and is shown to be tight. The lower bounds is only applicable to a narrow class of algorithms represented by the proposed algorithm. There are other class of algorithms which could have been discussed.\n\nThe proposed algorithm uses a multi-communication algorithm in a dual-loop approach, where a subproblem must be solved with communication. Although the process is accelerated such that it is optimal, there exist studies in the decentralized consensus literature that utilize tools such as gradient tracking, ADMM, etc., and prove convergence with single-loop algorithms. This is also preferable in practice since the communication bottleneck is more apparent for modern optimization tasks. \n\nA more complex experiment with real data and even neural networks would be appreciated for VFL. Though it is understandably omitted since it would not satisfy any of the technical assumptions, it would still be nicer to see.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "v8nrcVrUwa", "reviewer": "Reviewer_ieaZ", "summary": "This paper studies decentralized optimization with (affine) coupled constraints. This general formulation encompasses different applications, from energy networks to vertical (model-partitioned) federated learning. A complexity lower bound is given for this problem, as well as a matching (and thus optimal) algorithm. Both the algorithm and the lower bound are obtained through a reduction to the standard decentralized case, which is usually solved by introducing coupled constraints (the parameters from different nodes should be equal), and solving the constrained problem with a (primal-)dual approach. As such, the algorithm is based on APAPC (Salim et. al., 2022), and the lower bound directly proceeds from standard lower bounds. Adding extra coupling constraints is extremely natural in this case, and it is not surprising that using the same approach as for decentralized unconstrained optimization leads to similar results. The only care should be taken in how these extra constraints are added to ensure that the right quantities are communicated. Experiments demonstrate the (expected) superiority of the approach.", "questions": "- Could you precise the results obtained on vertical federated learning (giving a simple corollary in some standard specific case for instance) so that people can compare their results directly with yours? Does it just correspond to $\\kappa_A = 1$? How does this result compare with existing work in model-partitioned distributed optimization then?  \n- Have you tried tuning the value of r in the experiments? What would be the impact?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Tight analysis (optimal algorithm + lower bound) \n- Efficient off-the-shelf algorithm\n- Authors clearly state their contributions and how they leverage previous work\n\nI believe the main strength of the paper is that it uses the right tools to close a gap in the existing literature, so that non-experts can then use the algorithms.", "weaknesses": "- Rather incremental contribution. All results directly derive from existing ones on the reformulation from (10), which is rather natural (though not straightforward).\n\nIn the end, I have mixed feelings about this paper. The contribution is not particularly innovative or technically challenging, but it has the merit of existing, and gives a well-rounded solution to this problem that people can then use. Therefore, I believe it should be published somewhere, though I am not completely sure this is the right venue, which is why I slightly lean towards acceptance. However, I am not too familiar with ICLR standards so I am looking forward to the discussion phase.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CUP56pSp2P", "reviewer": "Reviewer_qaH7", "summary": "In this paper, the authors propose an algorithm for decentralized optimization with coupled constrains. Compared by most methods with proximal oracle, it is a first-order approach with a lower computational burden. The algoorithm is motivated on Chebyshev acceleration and Proximal Alternating Predictor-Corrector. The authors also provide the convergence analysis of the proposed algorithm in strongly-convex scenario and also proves that the proposed algorithm can reach the lower bound.", "questions": "See weakness.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. first order iterations.\n2. match the lower bound.\n3. suitable for different kinds of problems.", "weaknesses": "1. The presentation need to be improved. The contribution of the paper should be highlighted. And maybe it is more friendly for readers if the main algorithm is in Section 4, followed by the introduction of Chebyshev acceleration and Proximal Alternating Predictor-Corrector.\n\n2. It seems that some existing results like [1] do not need the strongly-convex assumption. And the author fails to provide the convergence analysis without strongly-convex assumption.\n\n3.  More experiments should be involved, including more problems with different coupled constraints. Some necessary comparison with algorithms developed for one kinds of constraints, like EXTRA in consensus optimization, should also be taken. \n\n[1] Distributed Optimization With Coupling Constraints.\n\n[2] EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)