# Decentralized Optimization with Coupled Constraints

Demyan Yarmoshik
MIPT, IITP
<EMAIL_ADDRESS>Dmitry Kovalev
Yandex Research
<EMAIL_ADDRESS>Alexander Rogozin
MIPT, Skoltech
<EMAIL_ADDRESS>Nikita Kiselev
MIPT
<EMAIL_ADDRESS>Daniil Dorin
MIPT
<EMAIL_ADDRESS>Alexander Gasnikov
Innopolis University, MIPT, IITP
<EMAIL_ADDRESS>
###### 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.

##  1 Introduction

We consider the decentralized optimization problem with coupled constraints

$\min_{x_{1}\in\mathbb{R}^{d_{1}},\ldots,x_{n}\in\mathbb{R}^{d_{n}}}\sum_{i=1}^{n}f_{i}(x_{i})\quad\text{s.t.}\quad\sum_{i=1}^{n}(\mathbf{A}_{i}x_{i}-b_{i})=0,$
(1)

where for $i\in\\{1,\ldots,n\\}$ functions
$f_{i}(x_{i})\colon\mathbb{R}^{d_{i}}\to\mathbb{R}$ are continuously
differentiable, $\mathbf{A}_{i}\in\mathbb{R}^{m\times d_{i}}$ and
$b_{i}\in\mathbb{R}^{m}$ are constraint matrices and vectors respectively.

We are interested in solving problem (1) in a decentralized distributed
setting. That is, we assume the existence of a communication network
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\\{1,\ldots,n\\}$
is the set of compute nodes, and
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the set of communication
links in the network. Each compute node $i\in\mathcal{V}$ locally stores the
objective function $f_{i}(x_{i})$, the constraint matrix $\mathbf{A}_{i}$ and
the vector $b_{i}$. Compute node $i\in\mathcal{V}$ can send information (e.g.,
vectors, scalars, etc.) to compute node $j\in\mathcal{V}$ if and only if there
is an edge $(i,j)\in\mathcal{E}$ in the communication network.

Coupled constraints arise in various application scenarios, where sharing of
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.

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

$\displaystyle\min_{x_{1},\ldots,x_{n}\in\mathbb{R}^{d}}\sum_{i=1}^{n}f_{i}(x_{i})\quad\text{s.t.}\quad\sum_{i=1}^{n}x_{i}=b,$

where $x_{i}\in\mathbb{R}^{d}$ represents the quantities of commodities
exchanged among the agents of the system, and $b\in\mathbb{R}^{d}$ 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).

$\bullet$ 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
$x_{i}\in\mathbb{R}^{2}$ 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 $\sum_{i=1}^{n}\mathbf{A}_{i}x_{i}=s$. An important property of the
matrices $\mathbf{A}_{i}$ is that their compatibility with the physical
network (but not necessary with the communication network). This means that
for each row of the matrix
$\left(\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\right)$, there is a node $k$ such
that $\mathbf{A}_{i}$ can have nonzero elements in this row only if nodes $i$
and $k$ are connected in the physical network, or $k=i$.

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

$\displaystyle\min_{x_{1},\ldots,x_{n}\in\mathbb{R}^{d}}\sum_{i=1}^{n}f_{i}(x_{i})\quad\text{s.t.}\quad
x_{1}=x_{2}=\ldots=x_{n}.$

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 $\sum_{i=1}^{n}\mathbf{W}_{i}x_{i}=0$, where
$\mathbf{W}_{i}$ 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
$\sum_{i=1}^{n}\mathbf{W}_{i}x_{i}$ 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
$\mathbf{A}_{i}=\mathbf{W}_{i}$. However, the principial difference between
this example and (1), is that (1) does not assume $\mathbf{A}_{i}$ to be
communication-friendly.

$\bullet$ 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 $\mathbf{F}$ be the matrix of features, split vertically
between compute nodes into submatrices $\mathbf{F}_{i}$, so that each node
possesses its own subset of features for all data samples. Let
$l\in\mathbb{R}^{m}$ denote the vector of labels, and let
$x_{i}\in\mathbb{R}^{d_{i}}$ be the vector of model parameters owned by the
$i$-th node. VFL problem formulates as

$\displaystyle\min_{\begin{subarray}{c}z\in\mathbb{R}^{m}\\\
x_{1}\in\mathbb{R}^{d_{1}},\ldots,x_{n}\in\mathbb{R}^{d_{n}}\end{subarray}}\ell(z,l)+\sum_{i=1}^{n}r_{i}(x_{i})\quad\text{s.t.}\quad\sum_{i=1}^{n}\mathbf{F}_{i}x_{i}=z,$
(2)

where $\ell$ is a loss function, and $r_{i}$ 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ć 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
(accelerated) $O(\sqrt{\kappa_{f}}\ln\frac{1}{\varepsilon})$ complexity for
consensus optimization was first achieved with a dual (requiring to compute
gradients of Fenchel conjugates of $f_{i}(x)$) accelerated gradient descent in
Scaman et al. (2017), where the corresponding complexity lower bounds were
also established. This result was later generalized to primal algorithms
(which use gradients of the functions $f_{i}(x)$ themselves), time-varying
communication graphs Li and Lin (2021); Kovalev et al. (2021) and 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ć
(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), see also 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 versatile for engineering applications, many of these algorithms
assume restricted function domains Wang and Hu (2022); Liang et al. (2019);
Nedić 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ć 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) $\dagger$ | 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) $\dagger$ | Prox | Linear
Gong and Zhang (2023) | Inexact prox | Linear
Nedić et al. (2018) $\dagger$ | First-order | Accelerated
This work | First-order | Optimal

  * $\dagger$

Applicable only for resource allocation problem

Works of Doan and Olshevsky (2017); Li et al. (2018); Nedić et al. (2018)
focus on the resource allocation problem. For undirected time-varying graphs
Doan and Olshevsky (2017) proposes a first-order algorithm with
$N=O(\frac{\kappa_{f}n^{2}}{B}\ln\frac{1}{\varepsilon})$ complexity bound,
where $B$ is the time the graph takes to reach connectivity. Li et al. (2018)
applies a combination of gradient 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., $x_{i}\in\Omega_{i}$, where $\Omega_{i}$ is
a nonempty closed convex set. Nedić et al. (2018) achieve accelerated linear
convergence via a proximal point method in the restricted domain case. When
$\Omega_{i}=\mathbb{R}^{d}$, they also show that Nesterov’s accelerated
gradient descent can be applied to achieve optimal
$O(\sqrt{\kappa_{f}}\ln\frac{1}{\varepsilon})$ 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 $\Omega_{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, there is no accelerated linearly convergent
algorithms for general affine-equality coupled constraints. 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 $\mathbf{C}$ are denoted by
$\lambda_{\max}(\mathbf{C})$ (or $\sigma_{\max}(\mathbf{C})$) and
$\lambda_{\min^{+}}(\mathbf{C})$ (or $\sigma_{\min^{+}}(\mathbf{C})$),
respectively. For vectors $x_{i}\in\mathbb{R}^{d_{i}}$ we introduce a column-
stacked vector
$x=\operatorname{\mathrm{col}}(x_{1},\ldots,x_{m})=(x_{1}^{\top}\ldots
x_{m}^{\top})^{\top}\in\mathbb{R}^{d}$. The symbol $\otimes$ denotes the
Kronecker product of matrices. By $\mathcal{L}_{m}$ we denote the so-called
consensus space, which is given as
$\mathcal{L}_{m}=\\{(y_{1},\ldots,y_{n})\in(\mathbb{R}^{m})^{n}:y_{1},\ldots,y_{n}\in\mathbb{R}^{m}\;\text{
and }\;y_{1}=\cdots=y_{n}\\}$, and $\mathcal{L}_{m}^{\perp}$ denotes the
orthogonal complement to $\mathcal{L}_{m}$, which is given as

$\mathcal{L}_{m}^{\perp}=\\{(y_{1},\ldots,y_{n})\in(\mathbb{R}^{m})^{n}:y_{1},\ldots,y_{n}\in\mathbb{R}^{m}\;\text{
and }\;y_{1}+\cdots+y_{n}=0\\}.$ (3)

######  Assumption 1.

Continuously differentiable functions
$f_{i}(x)\colon\mathbb{R}^{d_{i}}\to\mathbb{R},\ i\in\\{1,\ldots,n\\}$ are
$L_{f}$-smooth and $\mu_{f}$-strongly convex, where $L_{f}\geq\mu_{f}>0$. That
is, for all $x_{1},x_{2}\in\mathbb{R}^{d_{i}}$ and $i\in\\{1,\ldots,n\\}$, the
following inequalities hold:

$\frac{\mu_{f}}{2}\|x_{2}-x_{1}\|^{2}\leq
f_{i}(x_{2})-f_{i}(x_{1})-\langle\nabla
f_{i}(x_{1}),x_{2}-x_{1}\rangle\leq\frac{L_{f}}{2}\|x_{2}-x_{1}\|^{2}.$

By $\kappa_{f}$ we denote the condition number

$\kappa_{f}=\frac{L_{f}}{\mu_{f}}.$ (4)

######  Assumption 2.

There exists
$x^{*}=(x^{*}_{1},\ldots,x^{*}_{n}),x^{*}_{i}\in\mathbb{R}^{d_{i}}$ such that
$\sum_{i=1}^{n}(\mathbf{A}_{i}x^{*}_{i}-b_{i})=0$. There exist constants
$L_{\mathbf{A}}\geq\mu_{\mathbf{A}}>0$, such that the constraint matrices
$\mathbf{A}_{1},\ldots,\mathbf{A}_{n}$ satisfy the following inequalities:

$\sigma_{\max}^{2}(\mathbf{A})=\max_{i\in\\{1,\ldots,n\\}}\sigma_{\max}^{2}(\mathbf{A}_{i})\leq
L_{\mathbf{A}},\qquad\mu_{\mathbf{A}}\leq\lambda_{\min^{+}}\left(\mathbf{S}\right),$
(5)

where the matrix $\mathbf{S}\in\mathbb{R}^{m\times m}$ is defined as
$\mathbf{S}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{A}_{i}\mathbf{A}_{i}^{\top}$. We
also define the condition number of the matrix $\mathbf{A}$ as
$\kappa_{\mathbf{A}}=L_{\mathbf{A}}/\mu_{\mathbf{A}}$.

For any matrix $\mathbf{M}$ other than $\mathbf{A}$ we denote by
$L_{\mathbf{M}}$ and $\mu_{\mathbf{M}}$ some upper and lower bound on its
maximal and minimal positive squared singular values respectively:

$\lambda_{\max}(\mathbf{M}^{\top}\mathbf{M})=\sigma_{\max}^{2}(\mathbf{M})\leq
L_{\mathbf{M}},\qquad\mu_{\mathbf{M}}\leq\sigma_{\min^{+}}^{2}(\mathbf{M})=\lambda_{\min^{+}}(\mathbf{M}^{\top}\mathbf{M}).$
(6)

We also assume the existence of a so-called Gossip matrix
$W\in\mathbb{R}^{n\times n}$ associated with the communication network
$\mathcal{G}$, which satisfies certain assumptions.

######  Assumption 3.

The gossip matrix $W$ is a $n\times n$ symmetric positive semidefinite matrix
such that:
1\. $W_{ij}\neq 0$ if and only if $(i,j)\in\mathcal{E}$ or $i=j$.
2\. $Wy=0$ if and only if $y\in\mathcal{L}_{1}$, i.e. $y_{1}=\ldots=y_{n}$.
3\. There exist constants $L_{\mathbf{W}}\geq\mu_{\mathbf{W}}>0$ such that
$\mu_{\mathbf{W}}\leq\lambda_{\min^{+}}^{2}(W)$ and $\lambda_{\max}^{2}(W)\leq
L_{\mathbf{W}}$.

From the properties of the Kronecker product of matrices it follows that
$\lambda_{\min^{+}}^{2}(\mathbf{W})=\lambda_{\min^{+}}^{2}(W)$ and
$\lambda_{\max}^{2}(\mathbf{W})=\lambda_{\max}^{2}(W)$. By
$\kappa_{\mathbf{W}}$ we denote the condition number

$\kappa_{\mathbf{W}}=\frac{\lambda_{\max}(\mathbf{W})}{\lambda_{\min^{+}}(\mathbf{W})}=\sqrt{\frac{L_{\mathbf{W}}}{\mu_{\mathbf{W}}}}.$
(7)

Moreover, the kernel and range spaces of $W$ and $\mathbf{W}$ are given by

$\displaystyle\ker W=\mathcal{L}_{1},\
\operatorname{\mathrm{range}}W=\mathcal{L}_{1}^{\perp},\quad\ker\mathbf{W}=\mathcal{L}_{m},\
\operatorname{\mathrm{range}}\mathbf{W}=\mathcal{L}_{m}^{\perp}.$ (8)

##  4 Derivation of the algorithm

###  4.1 Strongly convex communication-friendly reformulation

Let $\mathbf{W^{\prime}}$ be any positive semidefinite matrix such that

$\operatorname{\mathrm{range}}\mathbf{W^{\prime}}=(\ker\mathbf{W^{\prime}})^{\perp}=\mathcal{L}_{m}^{\perp},$
(9)

and multiplication of a vector $y=(y_{1},\ldots,y_{n})\in(\mathbb{R}^{m})^{n}$
by $\mathbf{W^{\prime}}$ can be performed efficiently in the decentralized
manner if its $i$-th block component $y_{i}$ is stored at $i$-th node of the
computation network. Similarly to eq. 7, we define

$\kappa_{\mathbf{W^{\prime}}}=\frac{\lambda_{\max}(\mathbf{W^{\prime}})}{\lambda_{\min^{+}}(\mathbf{W^{\prime}})}=\sqrt{\frac{L_{\mathbf{W^{\prime}}}}{\mu_{\mathbf{W^{\prime}}}}}.$
(10)

Due to the definition of $\mathbf{W}$ and eq. 8, the simplest choice for
$\mathbf{W^{\prime}}$ might be to set $\mathbf{W^{\prime}}=\mathbf{W}$. Later
we will specify another way to choose $\mathbf{W^{\prime}}$ for optimal
algorithmic performance.

Problem (1) can be reformulated as follows:

$\min_{x\in\mathbb{R}^{d},y\in(\mathbb{R}^{m})^{n}}G(x,y)\quad\text{s.t.}\quad\mathbf{A}x+\gamma\mathbf{W^{\prime}}y=\mathbf{b},$
(11)

where the function
$G(x,y)\colon\mathbb{R}^{d}\times(\mathbb{R}^{m})^{n}\to\mathbb{R}$ is defined
as

$G(x,y)=F(x)+\frac{r}{2}\|\mathbf{A}x+\gamma\mathbf{W^{\prime}}y-\mathbf{b}\|^{2},$
(12)

the function $F(x)\colon\mathbb{R}^{d}\to\mathbb{R}$ is defined as
$F(x)=\sum_{i=1}^{n}f_{i}(x_{i})$, where
$x=(x_{1},\ldots,x_{n}),x_{i}\in\mathbb{R}^{d_{i}}$, the matrix
$\mathbf{A}\in\mathbb{R}^{mn\times d}$ is the block-diagonal matrix
$\mathbf{A}=\mathrm{diag}\left(\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\right)$,
the vector $\mathbf{b}$ is the column-stacked vector
$\mathbf{b}=\operatorname{\mathrm{col}}\left(b_{1},\ldots,b_{n}\right)\in\mathbb{R}^{mn}$,
and $r,\gamma>0$ are scalar constants that will be determined later.

From the definitions of $\mathbf{A}$, $\mathbf{b}$ and $\mathcal{L}^{\bot}$
(eq. 3) it is clear that $\sum_{i=1}^{n}(\mathbf{A}_{i}x_{i}-b_{i})=0$ if and
only if $\mathbf{A}x-\mathbf{b}\in\mathcal{L}_{m}^{\perp}$. Since
$\operatorname{\mathrm{range}}\mathbf{W^{\prime}}=\mathcal{L}^{\perp}_{m}$,
the constraint in problem (11) 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 (11) 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 $\gamma$ be defined as follows:

$r=\frac{\mu_{f}}{2L_{\mathbf{A}}},\quad\gamma^{2}=\frac{\mu_{\mathbf{A}}+L_{\mathbf{A}}}{\mu_{\mathbf{W^{\prime}}}}.$
(13)

Then, the strong convexity and smoothness constants of $G(x,y)$ on
$\mathbb{R}^{d}\times\mathcal{L}_{m}^{\perp}$ are given by

$\mu_{G}=\mu_{f}\min\left\\{\frac{1}{2},\frac{\mu_{\mathbf{A}}+L_{\mathbf{A}}}{4L_{\mathbf{A}}}\right\\},\quad
L_{G}=\max\left\\{L_{f}+\mu_{f},\mu_{f}\frac{\mu_{\mathbf{A}}+L_{\mathbf{A}}}{L_{\mathbf{A}}}\frac{L_{\mathbf{W^{\prime}}}}{\mu_{\mathbf{W^{\prime}}}}\right\\}.$
(14)

Let the matrix $\mathbf{B}\in\mathbb{R}^{mn\times(d+m)n}$ be defined as
$\mathbf{B}=\left[\begin{matrix}\mathbf{A}&\gamma\mathbf{W^{\prime}}\end{matrix}\right]$.
The following Lemma 2 connects the spectral properties of $\mathbf{B}$,
$\mathbf{A}$ and $\mathbf{W^{\prime}}$.

######  Lemma 2.

The following bounds on the singular values of $\mathbf{B}$ hold:

$\sigma_{\min^{+}}^{2}(\mathbf{B})\geq\mu_{\mathbf{B}}=\frac{\mu_{\mathbf{A}}}{2},\quad\sigma_{\max}^{2}(\mathbf{B})\leq
L_{\mathbf{B}}=L_{\mathbf{A}}+(L_{\mathbf{A}}+\mu_{\mathbf{A}})\frac{L_{\mathbf{W^{\prime}}}}{\mu_{\mathbf{W^{\prime}}}},$
(15)

and

$\frac{\sigma_{\max}^{2}(\mathbf{B})}{\sigma_{\min^{+}}^{2}(\mathbf{B})}\leq\frac{L_{\mathbf{B}}}{\mu_{\mathbf{B}}}=\kappa_{\mathbf{B}}=2\left(\kappa_{\mathbf{A}}+\frac{L_{\mathbf{W^{\prime}}}}{\mu_{\mathbf{W^{\prime}}}}(1+\kappa_{\mathbf{A}})\right).$
(16)

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

###  4.2 Chebyshev acceleration

Chebyshev acceleration allows us to decouple the number of computations of the
objective’s gradient $\nabla F(x)$ from the properties of the communication
network and the constraint matrix — specifically, from the condition numbers
$\kappa_{\mathbf{W}}$ and $\kappa_{\mathbf{A}}$.

First, we choose $\mathbf{W^{\prime}}$ as a polynomial
$P_{\mathbf{W}}(\mathbf{W})$ to make its condition number
$\kappa_{\mathbf{W^{\prime}}}$ be bounded by some small constant. Require
$P_{\mathbf{W}}(\lambda)=0\Leftrightarrow\lambda=0$ for every eigenvalue
$\lambda$ of $W$. Then, by eq. 8,
$\operatorname{\mathrm{range}}P_{\mathbf{W}}(\mathbf{W})=\operatorname{\mathrm{range}}\mathbf{W}=\mathcal{L}_{m}^{\bot}$,
and we can set $\mathbf{W^{\prime}}=P_{\mathbf{W}}(\mathbf{W})$.

Next, we aim to reduce $\kappa_{\mathbf{B}}$. Let $P_{\mathbf{B}}$ be a
polynomial such that $P_{\mathbf{B}}(\lambda)=0\Leftrightarrow\lambda=0$ for
every eigenvalue $\lambda$ of $\mathbf{B}^{\top}\mathbf{B}$. For compactness,
we denote by $u=(x,y)$ the stacked primal variable of problem (11). We denote
any feasible point for the affine constraint $\mathbf{B}u_{0}=\mathbf{b}$ as
$u_{0}$. Then,

$\displaystyle\mathbf{B}u=\mathbf{b}$
$\displaystyle\Leftrightarrow\mathbf{B}(u-u_{0})=0\overset{(a)}{\Leftrightarrow}\mathbf{B}^{\top}\mathbf{B}(u-u_{0})=0$
$\displaystyle\overset{(b)}{\Leftrightarrow}P_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})(u-u_{0})=0\overset{(c)}{\Leftrightarrow}\sqrt{P_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})}(u-u_{0})=0$

where (a) and (c) is due to $\ker\mathbf{M}^{\top}\mathbf{M}=\ker\mathbf{M}$
for any matrix $\mathbf{M}$; (b) is due to $\ker
P_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})=\ker\mathbf{B}^{\top}\mathbf{B}$
by the assumption about $P_{\mathbf{B}}(\lambda)$. This implies that by
denoting $\mathbf{K}=\sqrt{P_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})}$ and
$\mathbf{b^{\prime}}=\sqrt{P_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})}u_{0}$
we can reformulate the constraint in problem $\eqref{eq:compact}$ equivalently
as $\mathbf{K}u=\mathbf{b}^{\prime}$.

Following Salim et al. (2022a) and Scaman et al. (2017), we choose
$P_{\mathbf{W}},P_{\mathbf{B}}$ to be 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 $\mathbf{M}$. Let
$n=\left\lceil\sqrt{\frac{L_{\mathbf{M}}}{\mu_{\mathbf{M}}}}\right\rceil\geq\left\lceil\sqrt{\frac{\lambda_{\max}(\mathbf{M}^{\top}\mathbf{M})}{\lambda_{\min^{+}}(\mathbf{M}^{\top}\mathbf{M})}}\right\rceil$.
Define
$\mathcal{P}_{\mathbf{M}}(t)=1-\frac{T_{n}\left((L_{\mathbf{M}}+\mu_{\mathbf{M}}-2t)/(L_{\mathbf{M}}-\mu_{\mathbf{M}})\right)}{T_{n}\left((L_{\mathbf{M}}+\mu_{\mathbf{M}})/(L_{\mathbf{M}}-\mu_{\mathbf{M}})\right)}$,
where $T_{n}(t)$ is the Chebyshev polynomial of the first kind of degree $n$.
Then, $\mathcal{P}_{\mathbf{M}}(0)=0$, and

$\displaystyle\lambda_{\max}\left(\mathcal{P}_{\mathbf{M}}(\mathbf{M}^{\top}\mathbf{M})\right)$
$\displaystyle\leq\max_{t\in[\mu_{\mathbf{M}},L_{\mathbf{M}}]}\mathcal{P}_{\mathbf{M}}(t)\leq\frac{19}{15},$
(17)
$\displaystyle\lambda_{\min^{+}}\left(\mathcal{P}_{\mathbf{M}}(\mathbf{M}^{\top}\mathbf{M})\right)$
$\displaystyle\geq\min_{t\in[\mu_{\mathbf{M}},L_{\mathbf{M}}]}\mathcal{P}_{\mathbf{M}}(t)\geq\frac{11}{15}.$
(18)

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

######  Lemma 4.

Define

$\mathbf{W^{\prime}}=P_{\mathbf{W}}(\mathbf{W})=\mathcal{P}_{\sqrt{\mathbf{W}}}(\mathbf{W})$
(19)

and

$\mathbf{K}=\sqrt{P_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})}=\sqrt{\mathcal{P}_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})}.$
(20)

Let $G(u)=G(x,y)$, ${\mathcal{U}}=\mathbb{R}^{d}\times\mathcal{L}_{m}^{\perp}$
and
$\mathbf{b^{\prime}}=\sqrt{\mathcal{P}_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})}u_{0}$.
Then, problem

$\min_{u\in{\mathcal{U}}}G(u)\quad\text{s.t.}\quad\mathbf{K}u=\mathbf{b^{\prime}}$
(21)

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

###  4.3 Base algorithm

Algorithm 1 APAPC

1:Parameters: $u^{0}\in\mathcal{U}$ $\eta,\theta,\alpha>0$, $\tau\in(0,1)$

2:Set $u_{f}^{0}=u^{0}$, $z^{0}=0\in\mathcal{U}$

3:for $k=0,1,2,\ldots$ do

4: $u_{g}^{k}\coloneqq\tau u^{k}+(1-\tau)u_{f}^{k}$

5: $u^{k+\frac{1}{2}}\coloneqq(1+\eta\alpha)^{-1}(u^{k}-\eta(\nabla
G(u_{g}^{k})-\alpha u_{g}^{k}+z^{k}))$

6: $z^{k+1}\coloneqq
z^{k}+\theta\mathbf{K}^{\top}(\mathbf{K}u^{k+\frac{1}{2}}-\mathbf{b^{\prime}})$

7: $u^{k+1}\coloneqq(1+\eta\alpha)^{-1}(u^{k}-\eta(\nabla G(u_{g}^{k})-\alpha
u_{g}^{k}+z^{k+1}))$

8: $u_{f}^{k+1}\coloneqq u_{g}^{k}+\tfrac{2\tau}{2-\tau}(u^{k+1}-u^{k})$

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 (21). 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).

Denote $\kappa_{\mathbf{K}}=\frac{L_{\mathbf{K}}}{\mu_{\mathbf{K}}}$. Set the
parameter values of Algorithm 1 as
$\tau=\min\left\\{1,\frac{1}{2}\sqrt{\frac{\kappa_{\mathbf{K}}}{\kappa_{G}}}\right\\}$,
$\eta=\frac{1}{4\tau L_{G}}$, $\theta=\frac{1}{\eta L_{\mathbf{K}}}$ and
$\alpha=\mu_{G}$. Denote by $u^{*}$ the solution of problem (21) and by
$z^{*}$ the solution of its dual problem satisfying
$z^{*}\in\operatorname{\mathrm{range}}\mathbf{K}$. Then the iterates
$u^{k},z^{k}$ of Algorithm 1 satisfy

$\displaystyle\frac{1}{\eta}\left\|u^{k}-u^{\star}\right\|^{2}+\frac{\eta\alpha}{\theta(1+\eta\alpha)}\left\|(\mathbf{K}^{\top})^{\dagger}z^{k}-z^{\star}\right\|^{2}$
(22)
$\displaystyle+\frac{2(1-\tau)}{\tau}\mathrm{D}_{G}(u_{f}^{k},u^{\star})\leq\left(\\!1+\frac{1}{4}\min\left\\{\frac{1}{\sqrt{\kappa_{G}\kappa_{\mathbf{K}}}},\frac{1}{\kappa_{\mathbf{K}}}\right\\}\\!\right)^{-k}C,$

where
$C\coloneqq\frac{1}{\eta}\left\|u^{0}-u^{\star}\right\|^{2}+\frac{1}{\theta}\|z^{0}-z^{\star}\|^{2}+\frac{2(1-\tau)}{\tau}\mathrm{D}_{G}(u_{f}^{0},u^{\star})$,
and $\mathrm{D}_{G}$ denotes the Bregman divergence of $G$.

##  5 Main results

###  5.1 Algorithm

Algorithm 2 Main algorithm

1:Parameters: $x^{0}\in\mathbb{R}^{d}$ $\eta,\theta,\alpha>0$, $\tau\in(0,1)$

2:Set $y^{0}\coloneqq 0\in(\mathbb{R}^{m})^{n}$,
$u^{0}\coloneqq(x^{0},y^{0})$,

3: $u_{f}^{0}\coloneqq u^{0}$, $z^{0}\coloneqq
0\in\mathbb{R}^{d}\times(\mathbb{R}^{m})^{n}$

4:for $k=0,1,2,\ldots$ do

5: $u_{g}^{k}\coloneqq\tau u^{k}+(1-\tau)u_{f}^{k}$

6: $g^{k}\coloneqq\mathrm{\mathbf{grad\\_G}}(u_{g}^{k})-\alpha u_{g}^{k}$

7: $u^{k+\frac{1}{2}}\coloneqq(1+\eta\alpha)^{-1}(u^{k}-\eta(g^{k}+z^{k}))$

8: $z^{k+1}\coloneqq
z^{k}+\theta\cdot\mathrm{\mathbf{K\\_Chebyshev}}(u^{k+\frac{1}{2}})$

9: $u^{k+1}\coloneqq(1+\eta\alpha)^{-1}(u^{k}-\eta(g^{k}+z^{k+1}))$

10: $u_{f}^{k+1}\coloneqq u_{g}^{k}+\tfrac{2\tau}{2-\tau}(u^{k+1}-u^{k})$

11:end for

As stated in Lemma 4, problem (21) 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 $\mathbf{W^{\prime}}$
and $\mathbf{K}$ are bounded as $O(1)$, but a single multiplication by
$\mathbf{W^{\prime}}$ and $\mathbf{K},\mathbf{K}^{\top}$ translates to
$O(\sqrt{\kappa_{\mathbf{W}}})$ multiplications by $\mathbf{W}$ and
$O(\sqrt{\kappa_{\mathbf{B}}})$ multiplications by
$\mathbf{B},\mathbf{B}^{\top}$ respectively.

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

Algorithm 3 $\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}(y)$: Multiplication by
$\mathbf{W^{\prime}}$

1:Parameters: $y$

2:$\rho\coloneqq\left(\sqrt{L_{\mathbf{W}}}-\sqrt{\mu_{\mathbf{W}}}\right)^{2}/16$

3:$\nu\coloneqq\left(\sqrt{L_{\mathbf{W}}}+\sqrt{\mu_{\mathbf{W}}}\right)/2$

4:$\delta^{0}\coloneqq-\nu/2$,
$n\coloneqq\lceil\sqrt{\kappa_{\mathbf{W}}}\rceil$

5:$p^{0}\coloneqq-\mathbf{W}y/\nu$, $y^{1}\coloneqq y+p^{0}$

6:for $i=1,\ldots,n-1$ do

7: $\beta^{i-1}\coloneqq\rho/\delta^{i-1}$

8: $\delta^{i}\coloneqq-(\nu+\beta^{i-1})$

9: $p^{i}\coloneqq\left(\mathbf{W}y^{i}+\beta^{i-1}p^{i-1}\right)/\delta^{i}$

10: $y^{i+1}\coloneqq y^{i}+p^{i}$

11:end for

12:Output: $y-y^{n}$

Algorithm 4 $\mathrm{\mathbf{grad\\_G}}(u)$: Computation of $\nabla G(u)$

1:Parameters: $u=(x,y)$

2:$z\coloneqq
r\left(\mathbf{A}x+\gamma\cdot\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}(y)-\mathbf{b}\right)$

3:Output: $\begin{pmatrix}\nabla F(x)+\mathbf{A}^{\top}z\\\
\gamma\cdot\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}(z)\end{pmatrix}$

Algorithm 5 $\mathrm{\mathbf{K\\_Chebyshev}}(u)$: Computation of
$\mathbf{K}^{\top}(\mathbf{K}u-\mathbf{b^{\prime}})$

1:Parameters: $u=(x,y)$

2:$\rho\coloneqq\left({L_{\mathbf{B}}}-{\mu_{\mathbf{B}}}\right)^{2}/16$

3:$\nu\coloneqq\left({L_{\mathbf{B}}}+{\mu_{\mathbf{B}}}\right)/2$

4:$\delta^{0}\coloneqq-\nu/2$,
$n\coloneqq\lceil\sqrt{\kappa_{\mathbf{B}}}\rceil$

5:$q^{0}\coloneqq\mathbf{A}x+\gamma\cdot\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}(y)-\mathbf{b}$

6:$p^{0}\coloneqq-\dfrac{1}{\nu}\begin{pmatrix}\mathbf{A}^{\top}q^{0}\\\
\gamma\cdot\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}(q^{0})\end{pmatrix}$

7:$u^{1}\coloneqq u+p^{0}$

8:for $i=1,\ldots,n-1$ do

9: $\beta^{i-1}\coloneqq\rho/\delta^{i-1}$

10: $\delta^{i}\coloneqq-(\nu+\beta^{i-1})$

11: $(x^{i},y^{i})=u^{i}$

12:
$q^{i}\coloneqq\mathbf{A}x^{i}+\gamma\cdot\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}(y^{i})-\mathbf{b}$

13:
$p^{i}\coloneqq\dfrac{1}{\delta^{i}}\begin{pmatrix}\mathbf{A}^{\top}q^{i}\\\
\gamma\cdot\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}(q^{i})\end{pmatrix}+\beta^{i-1}p^{i-1}/\delta^{i}$

14: $u^{i+1}\coloneqq u^{i}+p^{i}$

15:end for

16:Output: $u-u^{n}$

######  Theorem 1.

Set the parameter values of Algorithm 2 as
$\tau=\min\left\\{1,\frac{1}{2}\sqrt{\frac{19}{60\max\left\\{1+\kappa_{f},8\right\\}}}\right\\}$,
$\eta=\frac{1}{4\tau\max\left\\{L_{f}+\mu_{f},8\mu_{f}\right\\}}$,
$\theta=\frac{15}{19\eta}$ and $\alpha=\frac{\mu_{f}}{4}$. Denote by $x^{*}$
the solution of problem (1). Then, for every $\varepsilon>0$, Algorithm 2
finds $x^{k}$ for which $\|x^{k}-x^{*}\|^{2}\leq\varepsilon$ using
$O(\sqrt{\kappa_{f}}\log(1/\varepsilon))$ objective’s gradient computations,
$O(\sqrt{\kappa_{f}}\sqrt{\kappa_{\mathbf{A}}}\log(1/\varepsilon))$
multiplications by $\mathbf{A}$ and $\mathbf{A}^{\top}$, and
$O(\sqrt{\kappa_{f}}\sqrt{\kappa_{\mathbf{A}}}\sqrt{\kappa_{\mathbf{W}}}\log(1/\varepsilon))$
communication rounds (multiplications by $\mathbf{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 $d_{i}$ of locally held
vectors $x_{i}$, they cannot communicate these vectors directly. Instead, the
nodes exchange quantities $\mathbf{A}_{i}x_{i}\in\mathbb{R}^{m}$. For this
reason, we introduce two types of memory $\mathcal{M}_{i}(k)$ and
$\mathcal{H}_{i}(k)$ for node $i$ at step $k$. Set $\mathcal{M}_{i}(k)$ stands
for the local memory that the node does not share and $\mathcal{H}_{i}(k)$
denotes the memory that the node exchanges with neighbors. The interaction
between $\mathcal{M}_{i}(k)$ and $\mathcal{H}_{i}(k)$ is performed via
multiplications by $\mathbf{A}_{i}$ and $\mathbf{A}_{i}^{\top}$.

Below we describe how the sets $\mathcal{M}_{i}(k),\mathcal{H}_{i}(k)$ are
updated.

1\. Algorithm performs local gradient comutation round at step $k$. Gradient
updates only operate in $\mathcal{M}_{i}(k)$ and do not affect
$\mathcal{H}_{i}(k)$. For all $i\in\mathcal{V}$ we have

$\displaystyle\mathcal{M}_{i}(k+1)=$$\displaystyle\left\\{x,\nabla
f_{i}(x),\nabla f_{i}^{*}(x):~{}x\in
M_{i}(k)\right\\},~{}\mathcal{H}_{i}(k+1)=\mathcal{H}_{i}(k),$

where $f_{i}^{*}$ is the Fenchel conjugate of $f_{i}$.
2\. Algorithm performs local matrix multiplication round at step $k$. Sets
$\mathcal{H}_{i}(k)$ and $\mathcal{M}_{i}(k)$ make mutual updates via
multiplication by $\mathbf{A}_{i}$ and $\mathbf{A}_{i}^{\top}$. For all
$i\in\mathcal{V}$ we have

$\displaystyle\mathcal{M}_{i}(k+1)=$$\displaystyle(\mathbf{A}_{i}^{\top}b_{i},~{}\mathbf{A}_{i}^{\top}y:~{}y\in\mathcal{H}_{i}(k)),~{}\mathcal{H}_{i}(k+1)=$$\displaystyle\left\\{b_{i},\mathbf{A}_{i}x:~{}x\in\mathcal{M}_{i}(k)\right\\}.$

3\. Algorithm performs a communication round at step $k$. The non-shared local
memory $\mathcal{M}_{i}(k)$ stays unchanged, while the shared memory
$\mathcal{H}_{i}(k+1)$ is updated via interaction with neighbors. For all
$i\in\mathcal{V}$ we have

$\displaystyle\mathcal{M}_{i}(k+1)=\mathcal{M}_{i}(k),~{}\mathcal{H}_{i}(k+1)=$$\displaystyle\left\\{\mathcal{H}_{j}(k):~{}(i,j)\in\mathcal{E}\right\\}.$

Under given memory and computation model, we formulate the lower complexity
bounds.

######  Theorem 2.

For any $L_{f}>\mu_{f}>0,~{}\kappa_{\mathbf{A}},\kappa_{\mathbf{W}}>0$ there
exist $L_{f}$-smooth $\mu_{f}$-strongly convex functions
$\left\\{f_{i}\right\\}_{i=1}^{n}$, matrices $\mathbf{A}_{i}$ such that
$\kappa_{\mathbf{A}}=L_{\mathbf{A}}/\mu_{\mathbf{A}}$ (where
$L_{\mathbf{A}},\mu_{\mathbf{A}}$ are defined in (5)), and a communication
graph $\mathcal{G}$ with a corresponding gossip matrix $\mathbf{W}$ such that
$\kappa_{\mathbf{W}}=\lambda_{\max}(\mathbf{W})/\lambda_{\min}^{+}(\mathbf{W})$,
for which any first-order decentralized algorithm on problem (1) to reach
accuracy $\varepsilon$ requires at least

$\displaystyle N_{\mathbf{A}}$
$\displaystyle=\Omega\left(\sqrt{\kappa_{f}}\sqrt{\kappa_{\mathbf{A}}}\log\left(\frac{1}{\varepsilon}\right)\right)~{}\text{multiplications
by $\mathbf{A}$ and $\mathbf{A}^{\top}$},$ $\displaystyle N_{\mathbf{W}}$
$\displaystyle=\Omega\left(\sqrt{\kappa_{f}}\sqrt{\kappa_{\mathbf{A}}}\sqrt{\kappa_{\mathbf{W}}}\log\left(\frac{1}{\varepsilon}\right)\right)~{}\text{communication
rounds (multiplications by $\mathbf{W}$)}.$

Moreover, there exists a different set of $L_{f}$-smooth $\mu_{f}$-strongly
convex functions $\left\\{f_{i}^{\prime}\right\\}_{i=1}^{n}$, matrices
$\mathbf{A}_{i}^{\prime}$ and a communication graph $\mathcal{G}^{\prime}$
with gossip matrix $\mathbf{W}^{\prime}$ such that
$\kappa_{\mathbf{A}}=L_{\mathbf{A}^{\prime}}/\mu_{\mathbf{A}^{\prime}},~{}\kappa_{\mathbf{W}}=\lambda_{\max}(\mathbf{W}^{\prime})/\lambda_{\min}^{+}(\mathbf{W}^{\prime})$,
for which any first-order decentralized algorithm requires at least

$\displaystyle
N_{f}=\Omega\left(\sqrt{\kappa}_{f}\log\left(\frac{1}{\varepsilon}\right)\right)~{}\text{gradient
computations}.$

A proof of Theorem 2 is provided in Appendix B.

##  6 Experiments

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

$\bullet$ Synthetic linear regression. In this section we perform numerical
experiments on a synthetic linear regression problem with
$\ell_{2}$-regularization:

$\min_{x_{1},\ldots,x_{n}\in\mathbb{R}^{d_{i}}}\sum_{i=1}^{n}\left(\frac{1}{2}\|C_{i}x_{i}-d_{i}\|_{2}^{2}+\frac{\theta}{2}\|x_{i}\|_{2}^{2}\right)\quad\text{s.t.}\quad\sum_{i=1}^{n}(\mathbf{A}_{i}x_{i}-b_{i})=0,$
(23)

where we randomly generate matrices $C_{i}\in\mathbb{R}^{d_{i}\times d_{i}}$,
$\mathbf{A}_{i}\in\mathbb{R}^{m\times d_{i}}$ and vectors
$d_{i}\in\mathbb{R}^{d_{i}}$, $b_{i}\in\mathbb{R}^{m}$ from the standard
normal distribution. Local variables $x_{i}\in\mathbb{R}^{d_{i}}$ have the
same dimension $d_{i}$, equal for all devices. Regularization parameter
$\theta$ is $10^{-3}$. In the Fig. 1 we demonstrate the performance of the our
method on the problem, that has the following parameters: $\kappa_{f}=3140$,
$\kappa_{\mathbf{A}}=27$, $\kappa_{\mathbf{W}}=89$. There we use Erdős–Rényi
graph topology with $n=20$ nodes. Local variables dimension is $d_{i}=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.

Figure 1: Synthetic, Erdős–Rényi graph, $n=20$, $d_{i}=3$, $m=10$

$\bullet$ 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: $\ell$ is a typical mean squared loss function, that is
$\ell(z,l)=\frac{1}{2}\|z-l\|_{2}^{2}$, and $r_{i}$ are
$\ell_{2}$-regularizers, i.e. $r_{i}(x_{i})=\lambda\|x_{i}\|_{2}^{2}$. To
adapt this from (2) to (1), we redefine $x_{1}:=\binom{x_{1}}{z}$ and
$x_{2}:=x_{2},\ldots,x_{n}:=x_{n}$. Thus, we can derive constraints matrices
as in the (1):

$\displaystyle\mathbf{A}_{1}=\begin{pmatrix}\mathbf{F}_{1}&-\mathbf{I}\end{pmatrix},\qquad\mathbf{A}_{1}x_{1}=\mathbf{F}_{1}w_{1}-z,$
(24) $\displaystyle\mathbf{A}_{i}=\mathbf{F}_{i},\quad
i=2,\ldots,n,\qquad\sum\limits_{i=1}^{n}\mathbf{A}_{i}x_{i}=\sum\limits_{i=1}^{n}\mathbf{F}_{i}w_{i}-z.$
(25)

For numerical simulation, we use mushrooms dataset from LibSVM library Chang
and Lin (2011). We split $m=100$ samples subset vertically between $n=7$
devices. Regularization parameter $\lambda=10^{-2}$. The results are in the
Fig. 2.

Figure 2: VFL, Erdő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 2 involves many
communications per iteration, in contrast to DPMM and Tracking-ADMM, which
make numerous gradient calls per iteration.

## References

  * Boyd et al. [2011] 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.
  * Nedić et al. [2018] Angelia Nedić, 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.
  * Arrow and Debreu [1954] Kenneth J Arrow and Gerard Debreu.  Existence of an equilibrium for a competitive economy.  _Econometrica: Journal of the Econometric Society_ , pages 265–290, 1954.
  * Dominguez-Garcia et al. [2012] 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.
  * Wang et al. [2016] 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.
  * Zhang et al. [2024] Haixiang Zhang, Ying Chen, and Javad Lavaei.  Geometric analysis of matrix sensing over graphs.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Yang et al. [2016] 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.
  * Van den Bergh et al. [2014] Kenneth Van den Bergh, Erik Delarue, and William D’haeseleer.  Dc power flow in unit commitment models.  _no. May_ , 2014.
  * Kairouz et al. [2021] 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.  Advances and open problems in federated learning.  _Foundations and trends® in machine learning_ , 14(1–2):1–210, 2021.
  * Gorbunov et al. [2022] 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.
  * Scaman et al. [2017] 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.
  * Yang et al. [2019] 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.
  * Nedić and Ozdaglar [2009] Angelia Nedić and Asuman Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1):48–61, 2009.
  * Tsitsiklis [1984] John Nikolas Tsitsiklis.  Problems in decentralized decision making and computation.  Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
  * Bertsekas and Tsitsiklis [1989] Dimitri P Bertsekas and John N Tsitsiklis.  _Parallel and distributed computation: numerical methods_ , volume 23.  Prentice hall Englewood Cliffs, NJ, 1989.
  * Boyd et al. [2006] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah.  Randomized gossip algorithms.  _IEEE transactions on information theory_ , 52(6):2508–2530, 2006.
  * Olshevsky and Tsitsiklis [2009] Alex Olshevsky and John N Tsitsiklis.  Convergence speed in distributed consensus and averaging.  _SIAM Journal on Control and Optimization_ , 48(1):33–55, 2009.
  * Li and Lin [2021] Huan Li and Zhouchen Lin.  Accelerated gradient tracking over time-varying graphs for decentralized optimization.  _arXiv preprint arXiv:2104.02596_ , 2021.
  * Kovalev et al. [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.
  * Dvinskikh and Gasnikov [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.
  * Beznosikov et al. [2023] 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.
  * Koloskova [2024] Anastasiia Koloskova.  Optimization algorithms for decentralized, distributed and collaborative machine learning.  Technical report, EPFL, 2024.
  * Rogozin et al. [2021] Alexander Rogozin, Alexander Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov.  Decentralized distributed optimization for saddle point problems.  _arXiv preprint arXiv:2102.07758_ , 2021.
  * Beznosikov et al. [2020] Aleksandr Beznosikov, Eduard Gorbunov, and Alexander Gasnikov.  Derivative-free method for composite optimization with applications to decentralized distributed optimization.  _IFAC-PapersOnLine_ , 53(2):4038–4043, 2020.
  * Nedić [2020] Angelia Nedić.  Distributed gradient methods for convex machine learning problems in networks: Distributed optimization.  _IEEE Signal Processing Magazine_ , 37(3):92–101, 2020.
  * Ram et al. [2009] 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.
  * Lian et al. [2017] 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.
  * Nedic et al. [2010] 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.
  * Zhu and Martinez [2011] Minghui Zhu and Sonia Martinez.  On distributed convex optimization under inequality and equality constraints.  _IEEE Transactions on Automatic Control_ , 57(1):151–164, 2011.
  * Necoara et al. [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.
  * Necoara and Nedelcu [2014] Ion Necoara and Valentin Nedelcu.  Distributed dual gradient methods and error bound conditions.  _arXiv preprint arXiv:1401.4398_ , 2014.
  * Necoara and Nedelcu [2015] 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.
  * Wang and Hu [2022] Jianzheng Wang and Guoqiang Hu.  Distributed optimization with coupling constraints in multi-cluster networks based on dual proximal gradient method.  _arXiv preprint arXiv:2203.00956_ , 2022.
  * Liang et al. [2019] Shu Liang, George Yin, et al.  Distributed smooth convex optimization with coupled constraints.  _IEEE Transactions on Automatic Control_ , 65(1):347–353, 2019.
  * Gong and Zhang [2023] Kai Gong and Liwei Zhang.  Decentralized proximal method of multipliers for convex optimization with coupled constraints.  _arXiv preprint arXiv:2310.15596_ , 2023.
  * Zhang et al. [2021] 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.
  * Wu et al. [2022] Xuyang Wu, He Wang, and Jie Lu.  Distributed optimization with coupling constraints.  _IEEE Transactions on Automatic Control_ , 68(3):1847–1854, 2022.
  * Doan and Olshevsky [2017] Thinh T Doan and Alex Olshevsky.  Distributed resource allocation on dynamic networks in quadratic time.  _Systems & Control Letters_, 99:57–63, 2017.
  * Falsone et al. [2020] Alessandro Falsone, Ivano Notarnicola, Giuseppe Notarstefano, and Maria Prandini.  Tracking-admm for distributed constraint-coupled optimization.  _Automatica_ , 117:108962, 2020.
  * Chang [2016] Tsung-Hui Chang.  A proximal dual consensus admm method for multi-agent constrained optimization.  _IEEE Transactions on Signal Processing_ , 64(14):3719–3734, 2016.
  * Li et al. [2018] 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.
  * Nedic et al. [2017] 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.
  * Salim et al. [2022a] 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.
  * Auzinger and Melenk [2011] Winfried Auzinger and J Melenk.  Iterative solution of large linear systems.  _Lecture notes, TU Wien_ , 2011.
  * Kovalev et al. [2020] 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.
  * Salim et al. [2022b] 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.
  * Nesterov [2004] Yurii Nesterov.  _Introductory Lectures on Convex Optimization: a basic course_.  Kluwer Academic Publishers, Massachusetts, 2004.
  * Chang and Lin [2011] 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.
  * Gutknecht and Röllin [2002] Martin H Gutknecht and Stefan Röllin.  The chebyshev iteration revisited.  _Parallel Computing_ , 28(2):263–283, 2002.

## Appendix / supplemental material

##  Appendix A Missing proofs from Section 4

###  A.1 Proof of Lemma 1

###### Proof.

Let $D_{G}(x^{\prime},y^{\prime};x,y)$ denote the Bregman divergence of $G$:

$D_{G}(x^{\prime},y^{\prime};x,y)=G(x^{\prime},y^{\prime})-G(x,y)-\langle\nabla_{x}G(x,y),x^{\prime}-x\rangle-\langle\nabla_{y}G(x,y),y^{\prime}-y\rangle.$
(26)

The value of $\mu_{G}$ can be obtained as follows:

$\displaystyle\mathrm{D}_{G}(x^{\prime},y^{\prime};x,y)$
$\displaystyle=\mathrm{D}_{F}(x^{\prime};x)+\frac{r}{2}\|\mathbf{A}(x^{\prime}-x)+\gamma\mathbf{W^{\prime}}(y^{\prime}-y)\|^{2}$
$\displaystyle\overset{(a)}{\geq}\frac{\mu_{f}}{2}\|x^{\prime}-x\|^{2}+\frac{r}{2}\|\mathbf{A}(x^{\prime}-x)+\gamma\mathbf{W^{\prime}}(y^{\prime}-y)\|^{2}$
$\displaystyle=\frac{\mu_{f}}{2}\|x^{\prime}-x\|^{2}+\frac{r}{2}\|\mathbf{A}(x^{\prime}-x)\|^{2}+r\langle\mathbf{A}(x^{\prime}-x),\gamma\mathbf{W^{\prime}}(y^{\prime}-y)\rangle$
$\displaystyle\quad+\frac{r}{2}\|\gamma\mathbf{W^{\prime}}(y^{\prime}-y)\|^{2}$
$\displaystyle\overset{(b)}{\geq}\frac{\mu_{f}}{2}\|x^{\prime}-x\|^{2}+\frac{r}{4}\|\gamma\mathbf{W^{\prime}}(y^{\prime}-y)\|^{2}-\frac{r}{2}\|\mathbf{A}(x^{\prime}-x)\|^{2}$
$\displaystyle\overset{(c)}{\geq}\frac{\mu_{f}}{2}\|x^{\prime}-x\|^{2}+\frac{r\gamma^{2}\mu_{\mathbf{W^{\prime}}}}{4}\|y^{\prime}-y\|^{2}-\frac{rL_{\mathbf{A}}}{2}\|x^{\prime}-x\|^{2}$
$\displaystyle\overset{(d)}{=}\frac{\mu_{f}}{4}\|x^{\prime}-x\|^{2}+\frac{\mu_{f}\gamma^{2}\mu_{\mathbf{W^{\prime}}}}{8L_{\mathbf{A}}}\|y^{\prime}-y\|^{2},$
$\displaystyle\overset{(e)}{\geq}\frac{\mu_{f}}{2}\min\left\\{\frac{1}{2},\frac{\mu_{\mathbf{A}}+L_{\mathbf{A}}}{4L_{\mathbf{A}}}\right\\}\left\|\begin{pmatrix}x^{\prime}-x\\\
y^{\prime}-y\end{pmatrix}\right\|^{2},$

where (a) is due to Assumption 1; (b) is due to Young’s inequality; (c) is due
to Assumption 2, $y^{\prime}-y\in\mathcal{L}_{m}^{\perp}$, eq. 9 and eq. 6;
(d) and (e) is due to eq. 13.

The value of $L_{G}$ can be obtained as follows:

$\displaystyle\mathrm{D}_{G}(x^{\prime},y^{\prime};x,y)$
$\displaystyle=\mathrm{D}_{F}(x^{\prime};x)+\frac{r}{2}\|\mathbf{A}(x^{\prime}-x)+\gamma\mathbf{W^{\prime}}(y^{\prime}-y)\|^{2}$
$\displaystyle\overset{(a)}{\leq}\frac{L_{f}}{2}\|x^{\prime}-x\|^{2}+\frac{r}{2}\|\mathbf{A}(x^{\prime}-x)+\gamma\mathbf{W^{\prime}}(y^{\prime}-y)\|^{2}$
$\displaystyle\overset{(b)}{\leq}\frac{L_{f}}{2}\|x^{\prime}-x\|^{2}+r\|\gamma\mathbf{W^{\prime}}(y^{\prime}-y)\|^{2}+r\|\mathbf{A}(x^{\prime}-x)\|^{2}$
$\displaystyle\overset{(c)}{\leq}\frac{L_{f}}{2}\|x^{\prime}-x\|^{2}+r\gamma^{2}L_{\mathbf{W^{\prime}}}\|y^{\prime}-y\|^{2}+rL_{\mathbf{A}}\|x^{\prime}-x\|^{2}$
$\displaystyle\overset{(d)}{=}\frac{L_{f}+\mu_{f}}{2}\|x^{\prime}-x\|^{2}+\frac{\mu_{f}\gamma^{2}L_{\mathbf{W^{\prime}}}}{2L_{\mathbf{A}}}\|y^{\prime}-y\|^{2},$
$\displaystyle\overset{(e)}{\leq}\frac{1}{2}\max\left\\{L_{f}+\mu_{f},\mu_{f}\frac{\mu_{\mathbf{A}}+L_{\mathbf{A}}}{L_{\mathbf{A}}}\frac{L_{\mathbf{W^{\prime}}}}{\mu_{\mathbf{W^{\prime}}}}\right\\}\left\|\begin{pmatrix}x^{\prime}-x\\\
y^{\prime}-y\end{pmatrix}\right\|^{2},$

where (a) is due to Assumption 1; (b) is due to Young’s inequality; (c) is due
to Assumption 2 and eq. 6; (d) and (e) is due to eq. 13. ∎

###  A.2 Proof of Lemma 2

###### Proof.

To obtain the formula for $L_{\mathbf{B}}$, consider an arbitrary
$z\in(\mathbb{R}^{m})^{n}$:

$\displaystyle\|\mathbf{B}^{\top}z\|^{2}$
$\displaystyle=\|\mathbf{A}^{\top}z\|^{2}+\|\gamma\mathbf{W^{\prime}}z\|^{2}$
$\displaystyle\overset{(a)}{\leq}(L_{\mathbf{A}}+\gamma^{2}L_{\mathbf{W^{\prime}}})\|z\|^{2}$
$\displaystyle\overset{(b)}{=}\left(L_{\mathbf{A}}+(L_{\mathbf{A}}+\mu_{\mathbf{A}})\frac{L_{\mathbf{W^{\prime}}}}{\mu_{\mathbf{W^{\prime}}}}\right)\|z\|^{2},$

where (a) is due to Assumption 2 and eq. 6; (b) is due to eq. 13.

To derive the formula for $\mu_{\mathbf{B}}$, first of all, note that by eq. 9

$(\ker\mathbf{B}^{\top})^{\bot}=\operatorname{\mathrm{range}}\mathbf{B}=\operatorname{\mathrm{range}}\mathbf{A}+\operatorname{\mathrm{range}}\mathbf{W^{\prime}}=\operatorname{\mathrm{range}}\mathbf{A}+\mathcal{L}_{m}^{\perp}.$
(27)

Let $z\in(\ker\mathbf{B}^{\top})^{\bot}=u+v$, where
$u=(u_{1},\ldots,u_{n}),v=(v_{0},\ldots,v_{0})\in(\mathbb{R}^{m})^{n}$ such
that $u\in\mathcal{L}_{m}^{\perp}$ and $v\in\mathcal{L}_{m}$.

We can show that $v_{0}\in\operatorname{\mathrm{range}}\mathbf{S}$. In order
to do that, let us show that $\langle v_{0},w_{0}\rangle=0$ for all
$w_{0}\in\ker\mathbf{S}$. Let $w=(w_{0},\ldots,w_{0})\in\mathcal{L}_{m}$. The
fact that $w_{0}\in\ker\mathbf{S}$ and $w\in\mathcal{L}_{m}$ implies
$w\in\ker\mathbf{A}\mathbf{A}^{\top}=\ker\mathbf{A}^{\top}$. Hence, it is easy
to show that
$w\in\ker\mathbf{B}^{\top}=(\operatorname{\mathrm{range}}\mathbf{B})^{\perp}$.
Then, we obtain

$n\langle v_{0},w_{0}\rangle\overset{(a)}{=}\langle
v,w\rangle\overset{(b)}{=}\langle u+v,w\rangle=\langle
z,w\rangle\overset{(c)}{=}0,$

where (a) follows from the definition of $v$ and $w$; (b) follows from the
fact that $u\in\mathcal{L}_{m}^{\perp}$ and $v\in\mathcal{L}_{m}$; (c) follows
from the fact that $z\in\operatorname{\mathrm{range}}\mathbf{B}$ and
$w\in(\operatorname{\mathrm{range}}\mathbf{B})^{\perp}$. Hence,
$v_{0}\in\operatorname{\mathrm{range}}\mathbf{S}$.

Further, we get

$\displaystyle\|\mathbf{B}^{\top}z\|^{2}$
$\displaystyle\overset{(a)}{=}\|\mathbf{A}^{\top}(u+v)\|^{2}+\|\gamma\mathbf{W^{\prime}}(u+v)\|^{2}$
$\displaystyle\overset{(b)}{=}\|\mathbf{A}^{\top}(u+v)\|^{2}+\|\gamma\mathbf{W^{\prime}}u\|^{2}$
$\displaystyle\overset{(c)}{\geq}\|\mathbf{A}^{\top}(u+v)\|^{2}+\gamma^{2}\mu_{\mathbf{W^{\prime}}}\|u\|^{2}$
$\displaystyle=\|\mathbf{A}^{\top}u\|^{2}+\|\mathbf{A}^{\top}v\|^{2}+2\langle\mathbf{A}^{\top}u,\mathbf{A}^{\top}v\rangle+\gamma^{2}\mu_{\mathbf{W^{\prime}}}\|u\|^{2}$
$\displaystyle\overset{(d)}{\geq}-\|\mathbf{A}^{\top}u\|^{2}+\frac{1}{2}\|\mathbf{A}^{\top}v\|^{2}+\gamma^{2}\mu_{\mathbf{W^{\prime}}}\|u\|^{2}$
$\displaystyle\overset{(e)}{=}-\|u\|^{2}_{\mathbf{A}\mathbf{A}^{\top}}+\frac{1}{2}\|v_{0}\|^{2}_{\mathbf{S}}+\gamma^{2}\mu_{\mathbf{W^{\prime}}}\|u\|^{2}$
$\displaystyle\overset{(f)}{\geq}-L_{\mathbf{A}}\|u\|^{2}+\frac{\mu_{\mathbf{A}}}{2}\|v\|^{2}+\gamma^{2}\mu_{\mathbf{W^{\prime}}}\|u\|^{2}$
$\displaystyle\overset{(g)}{=}\frac{\mu_{\mathbf{A}}}{2}\|v\|^{2}+\mu_{\mathbf{A}}\|u\|^{2}$
$\displaystyle\overset{(h)}{\geq}\frac{\mu_{\mathbf{A}}}{2}\|z\|^{2},$

where (a) and (h) is due to the definitions of $u$ and $v$; (b) is due to the
fact that $v\in\mathcal{L}_{m}$; (c) is due to eq. 6 and eq. 9; (d) uses
Young’s inequality; (e) is due to the definitions of $v$ and $\mathbf{S}$; (f)
is due to Assumption 2 and the definition of $v$; (g) is due to eq. 13.

∎

###  A.3 Proof of Theorem 1

######  Lemma 5 (Salim et al. [2022a], Section 6.3.2).

Let $\mathbf{M}$ be a matrix,
$\mathbf{r}\in\operatorname{\mathrm{range}}\mathbf{M}$ and
$\mathbf{M}v_{0}=\mathbf{r}$. Then
$\mathcal{P}_{\mathbf{M}}(\mathbf{M}^{\top}\mathbf{M})(v-v_{0})=v-\mathrm{\mathbf{Chebyshev}}(v,\mathbf{M},\mathbf{r})$,
where $\mathrm{\mathbf{Chebyshev}}$ is defined as Algorithm 6.

Algorithm 6 $\mathrm{\mathbf{Chebyshev}}(v,\mathbf{M},\mathbf{r})$: Chebyshev
iteration (Gutknecht and Röllin [2002], Algorithm 4)

1:Parameters: $v,\mathbf{M},\mathbf{r}.$

2:$n\coloneqq\left\lceil\sqrt{\frac{L_{\mathbf{M}}}{\mu_{\mathbf{M}}}}\right\rceil$

3:$\rho\coloneqq\big{(}L_{\mathbf{M}}-\mu_{\mathbf{M}}\big{)}^{2}/16$,
$\nu\coloneqq(L_{\mathbf{M}}+\mu_{\mathbf{M}})/2$

4:$\delta^{0}\coloneqq-\nu/2$

5:$p^{0}\coloneqq-{\mathbf{M}}^{\top}({\mathbf{M}}v-\mathbf{r})/\nu$

6:$v^{1}\coloneqq v+p^{0}$

7:for $i=1,\ldots,n-1$ do

8: $\beta^{i-1}\coloneqq\rho/\delta^{i-1}$

9: $\delta^{i}\coloneqq-(\nu+\beta^{i-1})$

10:
$p^{i}\coloneqq\big{(}\mathbf{M}^{\top}(\mathbf{M}v^{i}-\mathbf{r})+\beta^{i-1}p^{i-1}\big{)}/\delta^{i}$

11: $v^{i+1}\coloneqq v^{i}+p^{i}$

12:end for

13:Output: $v^{n}$

Applying Lemma 3 to $\mathbf{W}$ and $\mathbf{B}^{\top}\mathbf{B}$, we derive
that, due to eq. 19, it holds

$\lambda_{\max}^{2}(\mathbf{W^{\prime}})\leq
L_{\mathbf{W^{\prime}}}=(19/15)^{2},\quad\lambda_{\min^{+}}^{2}(\mathbf{W^{\prime}})\geq\mu_{\mathbf{W^{\prime}}}=(11/15)^{2},$
(28)

and by eq. 10 the polynomial $\mathcal{P}_{\mathbf{W}}$ has a degree of
$\lceil\sqrt{\kappa}_{\mathbf{W}}\rceil$. Similarly, due to eq. 20, it holds

$\sigma_{\max}^{2}(\mathbf{K})=\lambda_{\max}(\mathbf{K}^{\top}\mathbf{K})\leq
L_{\mathbf{K}}={19/15},\quad\sigma_{\min^{+}}^{2}(\mathbf{K})=\lambda_{\min^{+}}(\mathbf{K}^{\top}\mathbf{K})\geq\mu_{\mathbf{K}}={11/15},$
(29)

and since $\kappa_{\mathbf{B}}=\frac{L_{\mathbf{B}}}{\mu_{\mathbf{B}}}$, the
polynomial $\mathcal{P}_{\mathbf{B}}$ has a degree of
$\lceil\sqrt{\kappa}_{\mathbf{B}}\rceil$.

We implement computation of the term
$\mathbf{K}^{\top}(\mathbf{K}u-\mathbf{b^{\prime}})$ in line 6 of Algorithm 1
via Algorithm 5 by Lemma 5:

$\displaystyle\mathbf{K}^{\top}(\mathbf{K}u-\mathbf{b^{\prime}})$
$\displaystyle=\mathbf{K}^{\top}\mathbf{K}(u-u_{0})=\mathcal{P}_{\mathbf{B}}(\mathbf{B}^{\top}\mathbf{B})(u-u_{0})$
$\displaystyle=u-\mathrm{\mathbf{Chebyshev}}(u,\mathbf{B},\mathbf{b})=\mathrm{\mathbf{K\\_Chebyshev}}(u).$

Similarly, utilizing Lemma 5, we get

$\mathbf{W^{\prime}}y=\mathcal{P}_{\sqrt{\mathbf{W}}}(\mathbf{W})y=\mathcal{P}_{\sqrt{\mathbf{W}}}(\sqrt{\mathbf{W}}^{\top}\sqrt{\mathbf{W}})(y-0)=y-\mathrm{\mathbf{Chebyshev}}(y,\sqrt{\mathbf{W}},0)=\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}(y),$
(30)

where $\mathrm{\mathbf{mul}\mathbf{W^{\prime}}}$ is defined as Algorithm 3.

Therefore, Algorithm 2 is equivalent to Algorithm 1.

From eqs. 14, 4 and 28 we get

$\kappa_{G}=\frac{L_{G}}{\mu_{G}}=\frac{\max\left\\{\kappa_{f}+1,\frac{\mu_{\mathbf{A}}+L_{\mathbf{A}}}{L_{\mathbf{A}}}\frac{L_{\mathbf{W^{\prime}}}}{\mu_{\mathbf{W^{\prime}}}}\right\\}}{\min\left\\{\frac{1}{2},\frac{\mu_{\mathbf{A}}+L_{\mathbf{A}}}{4L_{\mathbf{A}}}\right\\}}\leq
4\max\left\\{1+\kappa_{f},2\cdot(19/11)^{2}\right\\}\leq
4\max\left\\{1+\kappa_{f},8\right\\}.$ (31)

From eqs. 16 and 28 we get

$\kappa_{\mathbf{B}}=\frac{L_{\mathbf{B}}}{\mu_{\mathbf{B}}}\leq
2\left(\kappa_{\mathbf{A}}+(19/11)^{2}(1+\kappa_{\mathbf{A}})\right)\leq
10\kappa_{\mathbf{A}}+8.$ (32)

From eq. 29 we obtain
$\kappa_{\mathbf{K}}=\frac{L_{\mathbf{K}}}{\mu_{\mathbf{K}}}=19/11$, and
substituting eqs. 32 and 31 to Proposition 1, we obtain as its direct
corollary that $k=O(\sqrt{\kappa_{f}}\log(1/\varepsilon))$. Each iteration of
Algorithm 2 require $O(1)$ computations of $\nabla F$,
$O(\sqrt{\kappa_{\mathbf{B}}})=O(\sqrt{\kappa_{\mathbf{A}}})$ multiplications
by $\mathbf{A},\mathbf{A}^{\top}$ and
$O(\sqrt{\kappa_{\mathbf{A}}}\sqrt{\kappa_{\mathbf{W}}})$ multiplications by
$\mathbf{W}$, which gives us the statement of Theorem 1.

##  Appendix B Proof of Theorem 2

###  B.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.

$\displaystyle\min_{x_{1},\ldots,x_{n}\in\mathbb{R}^{d}}~{}$
$\displaystyle\sum_{i=1}^{n}f_{i}(x_{i})$ s.t.
$\displaystyle\sum_{i=1}^{n}\mathbf{A}_{i}x_{i}=0$

The dual problem has the form

$\displaystyle\min_{x_{1},\ldots,x_{n}\in\mathbb{R}^{d}}\max_{w}\left[\sum_{i=1}^{n}f_{i}(x_{i})-\left\langle
w,\mathbf{A}_{i}x_{i}\right\rangle\right]=\max_{w}\left[-\max_{x_{1},\ldots,x_{n}\in\mathbb{R}^{d}}\sum_{i=1}^{n}\left\langle\mathbf{A}_{i}^{\top}w,x_{i}\right\rangle-
f_{i}(x_{i})\right]$
$\displaystyle\quad=-\min_{w}\sum_{i=1}^{n}f_{i}^{*}(\mathbf{A}_{i}^{\top}w).$

Introducing local copies of $w$ at each node, we get

$\displaystyle\min_{w_{1},\ldots,w_{n}}~{}$
$\displaystyle\sum_{i=1}^{n}f_{i}^{*}(\mathbf{A}_{i}^{\top}w_{i})$
$\displaystyle\text{s.t. }\mathbf{W}w=0$

###  B.2 Example construction

We follow the principle of lower bounds construction introduced in Scaman et
al. [2017]. Let the functions be held by the nodes organized into a path graph
with $n$ vertices, where $n$ is divisible by $3$. The nodes are divided into
three groups
$\mathcal{V}_{1}=\left\\{1,\ldots,n/3\right\\},\mathcal{V}_{2}=\left\\{n/3+1,\ldots,2n/3\right\\},\mathcal{V}_{3}=\left\\{2n/3+1,\ldots,n\right\\}$
of $n/3$ vertices each. We let $e_{1}=(1~{}0~{}\ldots~{}0)^{\top}$ denote the
first coordinate vector and define functions

$\displaystyle
f_{i}(p,t)=\frac{\mu_{f}}{2}\left\|p-\frac{\sqrt{\hat{L}_{\mathbf{A}}}}{2\mu_{f}}e_{1}\right\|^{2}+\frac{L_{f}}{2}\|t\|^{2}.$

Correspondingly,

$\displaystyle
f_{i}^{*}(u,v)=\frac{1}{2\mu_{f}}\|u\|^{2}+\frac{1}{2L_{f}}\|v\|^{2}-\frac{\sqrt{\hat{L}_{\mathbf{A}}}}{2\mu_{f}}u_{1}.$

To define matrices $\mathbf{A}_{i}$, we first introduce

$\displaystyle\mathbf{E}_{1}=\begin{pmatrix}1&-1&0&0&\ldots&\\\
0&0&0&0&\ldots&\\\ 0&0&1&-1&\ldots&\\\ \vdots&\vdots&\vdots&\vdots&\ddots&\\\
\end{pmatrix},~{}~{}~{}\mathbf{E}_{2}=\begin{pmatrix}0&0&0&0&0&\ldots&\\\
0&1&-1&0&0&\ldots&\\\ 0&0&0&0&0&\ldots&\\\ 0&0&0&1&-1&\ldots&\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\\\ \end{pmatrix}.$

Let
$\hat{L}_{\mathbf{A}}=\frac{1}{2}L_{\mathbf{A}}-\frac{3}{4}\mu_{\mathbf{A}},~{}\hat{\mu}_{\mathbf{A}}=\frac{3}{2}\mu_{\mathbf{A}}$
and introduce

$\displaystyle\mathbf{A}_{i}=\begin{cases}[\sqrt{\hat{L}_{\mathbf{A}}}\mathbf{E}_{1}^{\top}~{}~{}\sqrt{\hat{\mu}_{\mathbf{A}}}\mathbf{I}],&i\in\mathcal{V}_{1}\\\
[\sqrt{\hat{L}_{\mathbf{A}}}e_{1}e_{1}^{\top}~{}~{}~{}~{}~{}~{}~{}\mathbf{0}],&i\in\mathcal{V}_{2}\\\
[\sqrt{\hat{L}_{\mathbf{A}}}\mathbf{E}_{2}^{\top}~{}~{}\sqrt{\hat{\mu}_{\mathbf{A}}}\mathbf{I}],&i\in\mathcal{V}_{3}\end{cases}$

Let us make sure that the choice of $\mathbf{A}_{i}$ guarantees constants
$L_{\mathbf{A}},\mu_{\mathbf{A}}$ from (5).

$\displaystyle\max_{i}\lambda_{\max}(\mathbf{A}_{i}\mathbf{A}_{i}^{\top})$
$\displaystyle=\lambda_{\max}\left(\hat{L}_{\mathbf{A}}\mathbf{E}_{1}^{\top}\mathbf{E}_{1}+\hat{\mu}_{\mathbf{A}}\right)=2\hat{L}_{\mathbf{A}}+\hat{\mu}_{\mathbf{A}}=L_{\mathbf{A}},$
$\displaystyle\lambda_{\min}^{+}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbf{A}_{i}\mathbf{A}_{i}^{\top}\right)$
$\displaystyle=6\lambda_{\min}^{+}\left(\frac{1}{3}(\hat{L}_{\mathbf{A}}\mathbf{E}_{1}^{\top}\mathbf{E}_{1}+\hat{\mu}_{\mathbf{A}}\mathbf{I})+\frac{1}{3}(\hat{L}_{\mathbf{A}}\mathbf{E}_{2}^{\top}\mathbf{E}_{2}+\hat{\mu}_{\mathbf{A}}\mathbf{I})+\frac{1}{3}\hat{L}_{\mathbf{A}}e_{1}e_{1}^{\top}\right)$
$\displaystyle=\frac{2}{3}\hat{\mu}_{\mathbf{A}}=\mu_{\mathbf{A}}.$

The dual functions take the form

$\displaystyle g_{i}(z)=f_{i}^{*}(\mathbf{A}_{i}^{\top}z)$
$\displaystyle=\begin{cases}\frac{1}{2\mu_{f}}\|\sqrt{\hat{L}_{\mathbf{A}}}\mathbf{E}_{1}z\|^{2}+\frac{1}{2L_{f}}\|\sqrt{\hat{\mu}_{\mathbf{A}}}z\|^{2}-\frac{L_{\mathbf{A}}}{2\mu_{f}}z_{1},&i\in\mathcal{V}_{1}\\\
\frac{1}{2\mu_{f}}\|\sqrt{\hat{L}_{\mathbf{A}}}e_{1}e_{1}^{\top}z\|^{2},&i\in\mathcal{V}_{2}\\\
\frac{1}{2\mu_{f}}\|\sqrt{\hat{L}_{\mathbf{A}}}\mathbf{E}_{2}z\|^{2}+\frac{1}{2L_{f}}\|\sqrt{\hat{\mu}_{\mathbf{A}}}z\|^{2}-\frac{L_{\mathbf{A}}}{2\mu_{f}}z_{1},&i\in\mathcal{V}_{3}\end{cases}$
$\displaystyle=\begin{cases}\frac{1}{2}z^{\top}\left(\frac{\hat{L}_{\mathbf{A}}}{\mu_{f}}\mathbf{E}_{1}^{\top}\mathbf{E}_{1}+\frac{\hat{\mu}_{\mathbf{A}}}{L_{f}}\mathbf{I}\right)z-\frac{L_{\mathbf{A}}}{2\mu_{f}}z_{1},&i\in\mathcal{V}_{1}\\\
\frac{\hat{L}_{\mathbf{A}}}{2\mu_{f}}z_{1}^{2},&i\in\mathcal{V}_{2}\\\
\frac{1}{2}z^{\top}\left(\frac{\hat{L}_{\mathbf{A}}}{\mu_{f}}\mathbf{E}_{2}^{\top}\mathbf{E}_{2}+\frac{\hat{\mu}_{\mathbf{A}}}{L_{f}}\mathbf{I}\right)z-\frac{L_{\mathbf{A}}}{2\mu_{f}}z_{1},&i\in\mathcal{V}_{3}\end{cases}$

Therefore, we have

$\displaystyle\sum_{i=1}^{n}g_{i}(z)$
$\displaystyle=\frac{n}{3}\left[\frac{\hat{L}_{\mathbf{A}}}{2\mu_{f}}z^{\top}(\mathbf{E}_{1}^{\top}\mathbf{E}_{1}+\mathbf{E}_{2}^{\top}\mathbf{E}_{2}+e_{1}e_{1}^{\top})z+\frac{\hat{\mu}_{\mathbf{A}}}{L_{f}}z^{\top}z-\frac{\hat{L}_{\mathbf{A}}}{\mu_{f}}z_{1}\right]$
$\displaystyle=\frac{n}{3}\frac{\hat{L}_{\mathbf{A}}}{\mu_{f}}\left[\frac{1}{2}z^{\top}\mathbf{M}z-z_{1}+\frac{\mu_{\mathbf{A}}\mu_{f}}{L_{\mathbf{A}}L_{f}}z^{\top}z\right],$

where

$\displaystyle\mathbf{M}=\begin{pmatrix}~{}~{}~{}2&-1&~{}~{}~{}0&~{}~{}~{}0&0&\ldots\\\
-1&~{}~{}~{}2&-1&~{}~{}~{}0&0&\ldots\\\
~{}~{}~{}0&-1&~{}~{}~{}2&-1&0&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{pmatrix}.$

In the lower bound example in Scaman et al. [2017] it was shown that function

$\displaystyle
h(z)=\frac{1}{2}z^{\top}\mathbf{M}z+\frac{2\alpha}{\beta-\alpha}\|z\|^{2}-z_{1}$

attains its minimum at
$z_{k}^{*}=\left(\frac{\sqrt{\beta}-\sqrt{\alpha}}{\sqrt{\beta}+\sqrt{\alpha}}\right)^{k}$.
Adapting it for our case, we get

$\displaystyle\frac{2\alpha}{\beta-\alpha}$
$\displaystyle=\frac{\mu_{\mathbf{A}}\mu_{f}}{L_{\mathbf{A}}L_{f}}$
$\displaystyle\frac{\alpha}{\beta}$
$\displaystyle=\left(1+2\frac{L_{\mathbf{A}}L_{f}}{\mu_{\mathbf{A}}\mu_{f}}\right)^{-1}$

and therefore $z_{k}^{*}=q^{k}$, where

$\displaystyle
q=\frac{1-\sqrt{\frac{\mu_{\mathbf{A}}\mu_{f}}{\mu_{\mathbf{A}}\mu_{f}+2L_{\mathbf{A}}L_{f}}}}{1+\sqrt{\frac{\mu_{\mathbf{A}}\mu_{f}}{\mu_{\mathbf{A}}\mu_{f}+2L_{\mathbf{A}}L_{f}}}}.$
(33)

It remains to show the lower bound on the number of matrix multiplications and
communications. Following the proof of Theorem 2 in Scaman et al. [2017], we
construct a gossip matrix $\mathbf{W}$ such that
$\chi(\mathbf{W})\leq(n+1)^{2}/2$. After that, let $s_{i}(k)$ denote the
number of nonzero coordinates at node $i$ at step $k$ (such notation was used
in Kovalev et al. [2021]). According to the rules for updating the sets
$\mathcal{M}_{i}(k),\mathcal{H}_{i}(k)$ in section 5.2, primal and dual
variables have the same block-structure and thus the same upper bound for the
number of nonzero coordinates. Also denote $k_{t}$ the number of algorithm
step at which $t$-th communication round happens. Due to the structure of
functions corresponding to $\mathcal{V}_{1},\mathcal{V}_{2},\mathcal{V}_{3}$,
it holds $s_{i}(k_{t})\leq O(t/n)$. To lower bound the distance to consensus,
we write

$\displaystyle\|x_{k_{t}}-x^{*}\|^{2}\geq\Omega\left(\sum_{k=s_{i}(k_{t})}^{\infty}q^{k}\right)=\Omega\left(q^{s_{i}(k_{t})}\right)=\Omega\left(q^{\lfloor
t/n\rfloor}\right).$

Using the expression for $q$ in (33) and noting that $q\sim
1-\sqrt{\frac{\mu_{\mathbf{A}}\mu_{f}}{L_{\mathbf{A}}L_{f}}}$, we can lower
bound the number of communications needed to yield $\hat{x}$ such that
$\|\hat{x}-x^{*}\|^{2}\leq\varepsilon$, that is:

$\displaystyle
N_{\mathbf{W}}=\Omega\left(n\sqrt{\frac{L_{\mathbf{A}}L_{f}}{\mu_{\mathbf{A}}\mu_{f}}}\log\left(\frac{1}{\varepsilon}\right)\right)=\Omega\left(\sqrt{\kappa_{f}}\sqrt{\kappa_{\mathbf{A}}}\sqrt{\kappa_{\mathbf{W}}}\log\left(\frac{1}{\varepsilon}\right)\right).$

Analogously, we get a lower bound on matrix multiplication rounds:

$\displaystyle
N_{\mathbf{A}}=\Omega\left(\sqrt{\kappa_{f}}\sqrt{\kappa_{\mathbf{A}}}\log\left(\frac{1}{\varepsilon}\right)\right).$

###  B.3 Lower bound on the number of gradient computations

For the lower bound on the number of gradient computations, we simply recall
the lower bounds from Corollary 2 of Scaman et al. [2017].

## NeurIPS Paper Checklist

  1. 1.

Claims

  2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

  3. Answer: [Yes]

  4. Justification: the algorithm for decentralized optimization with coupled constraints is the main contribution of the paper, which is mentioned in the abstract.

  5. Guidelines:

     * •

The answer NA means that the abstract and introduction do not include the
claims made in the paper.

     * •

The abstract and/or introduction should clearly state the claims made,
including the contributions made in the paper and important assumptions and
limitations. A No or NA answer to this question will not be perceived well by
the reviewers.

     * •

The claims made should match theoretical and experimental results, and reflect
how much the results can be expected to generalize to other settings.

     * •

It is fine to include aspirational goals as motivation as long as it is clear
that these goals are not attained by the paper.

  6. 2.

Limitations

  7. Question: Does the paper discuss the limitations of the work performed by the authors?

  8. Answer: [Yes]

  9. Justification: the paper uses standard assumptions for decentralized convex optimization: smoothness and strong convexity of the objective functions (Assumption 1) and properties of gossip matrix (Assumption 3).

  10. Guidelines:

     * •

The answer NA means that the paper has no limitation while the answer No means
that the paper has limitations, but those are not discussed in the paper.

     * •

The authors are encouraged to create a separate "Limitations" section in their
paper.

     * •

The paper should point out any strong assumptions and how robust the results
are to violations of these assumptions (e.g., independence assumptions,
noiseless settings, model well-specification, asymptotic approximations only
holding locally). The authors should reflect on how these assumptions might be
violated in practice and what the implications would be.

     * •

The authors should reflect on the scope of the claims made, e.g., if the
approach was only tested on a few datasets or with a few runs. In general,
empirical results often depend on implicit assumptions, which should be
articulated.

     * •

The authors should reflect on the factors that influence the performance of
the approach. For example, a facial recognition algorithm may perform poorly
when image resolution is low or images are taken in low lighting. Or a speech-
to-text system might not be used reliably to provide closed captions for
online lectures because it fails to handle technical jargon.

     * •

The authors should discuss the computational efficiency of the proposed
algorithms and how they scale with dataset size.

     * •

If applicable, the authors should discuss possible limitations of their
approach to address problems of privacy and fairness.

     * •

While the authors might fear that complete honesty about limitations might be
used by reviewers as grounds for rejection, a worse outcome might be that
reviewers discover limitations that aren’t acknowledged in the paper. The
authors should use their best judgment and recognize that individual actions
in favor of transparency play an important role in developing norms that
preserve the integrity of the community. Reviewers will be specifically
instructed to not penalize honesty concerning limitations.

  11. 3.

Theory Assumptions and Proofs

  12. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

  13. Answer: [Yes]

  14. Justification: main results for the algorithm convergence are given in Theorem 1 and the lower complexity bounds are given in Theorem 2. Assumption 1 describes objective functions, Assumption 2 refers to constraint matrices and Assumption 3 describes the gossip matrix.

  15. Guidelines:

     * •

The answer NA means that the paper does not include theoretical results.

     * •

All the theorems, formulas, and proofs in the paper should be numbered and
cross-referenced.

     * •

All assumptions should be clearly stated or referenced in the statement of any
theorems.

     * •

The proofs can either appear in the main paper or the supplemental material,
but if they appear in the supplemental material, the authors are encouraged to
provide a short proof sketch to provide intuition.

     * •

Inversely, any informal proof provided in the core of the paper should be
complemented by formal proofs provided in appendix or supplemental material.

     * •

Theorems and Lemmas that the proof relies upon should be properly referenced.

  16. 4.

Experimental Result Reproducibility

  17. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

  18. Answer: [Yes]

  19. Justification: Section 6 describes the problem statements and gives the references to the algorithms which we compare with.

  20. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

If the paper includes experiments, a No answer to this question will not be
perceived well by the reviewers: Making the paper reproducible is important,
regardless of whether the code and data are provided or not.

     * •

If the contribution is a dataset and/or model, the authors should describe the
steps taken to make their results reproducible or verifiable.

     * •

Depending on the contribution, reproducibility can be accomplished in various
ways. For example, if the contribution is a novel architecture, describing the
architecture fully might suffice, or if the contribution is a specific model
and empirical evaluation, it may be necessary to either make it possible for
others to replicate the model with the same dataset, or provide access to the
model. In general. releasing code and data is often one good way to accomplish
this, but reproducibility can also be provided via detailed instructions for
how to replicate the results, access to a hosted model (e.g., in the case of a
large language model), releasing of a model checkpoint, or other means that
are appropriate to the research performed.

     * •

While NeurIPS does not require releasing code, the conference does require all
submissions to provide some reasonable avenue for reproducibility, which may
depend on the nature of the contribution. For example

       1. (a)

If the contribution is primarily a new algorithm, the paper should make it
clear how to reproduce that algorithm.

       2. (b)

If the contribution is primarily a new model architecture, the paper should
describe the architecture clearly and fully.

       3. (c)

If the contribution is a new model (e.g., a large language model), then there
should either be a way to access this model for reproducing the results or a
way to reproduce the model (e.g., with an open-source dataset or instructions
for how to construct the dataset).

       4. (d)

We recognize that reproducibility may be tricky in some cases, in which case
authors are welcome to describe the particular way they provide for
reproducibility. In the case of closed-source models, it may be that access to
the model is limited in some way (e.g., to registered users), but it should be
possible for other researchers to have some path to reproducing or verifying
the results.

  21. 5.

Open access to data and code

  22. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

  23. Answer: [Yes]

  24. Justification: we provide the code in supplementary material.

  25. Guidelines:

     * •

The answer NA means that paper does not include experiments requiring code.

     * •

Please see the NeurIPS code and data submission guidelines
(https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.

     * •

While we encourage the release of code and data, we understand that this might
not be possible, so “No” is an acceptable answer. Papers cannot be rejected
simply for not including code, unless this is central to the contribution
(e.g., for a new open-source benchmark).

     * •

The instructions should contain the exact command and environment needed to
run to reproduce the results. See the NeurIPS code and data submission
guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more
details.

     * •

The authors should provide instructions on data access and preparation,
including how to access the raw data, preprocessed data, intermediate data,
and generated data, etc.

     * •

The authors should provide scripts to reproduce all experimental results for
the new proposed method and baselines. If only a subset of experiments are
reproducible, they should state which ones are omitted from the script and
why.

     * •

At submission time, to preserve anonymity, the authors should release
anonymized versions (if applicable).

     * •

Providing as much information as possible in supplemental material (appended
to the paper) is recommended, but including URLs to data and code is
permitted.

  26. 6.

Experimental Setting/Details

  27. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?

  28. Answer: [Yes]

  29. Justification: the experiments in Section 6 include the optimization problem and optimization methods. The parameters of methods are described in our paper or in the papers that the methods appeared.

  30. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The experimental setting should be presented in the core of the paper to a
level of detail that is necessary to appreciate the results and make sense of
them.

     * •

The full details can be provided either with the code, in appendix, or as
supplemental material.

  31. 7.

Experiment Statistical Significance

  32. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

  33. Answer: [N/A]

  34. Justification: the paper studies deterministic algorithms and does not include error bars.

  35. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The authors should answer "Yes" if the results are accompanied by error bars,
confidence intervals, or statistical significance tests, at least for the
experiments that support the main claims of the paper.

     * •

The factors of variability that the error bars are capturing should be clearly
stated (for example, train/test split, initialization, random drawing of some
parameter, or overall run with given experimental conditions).

     * •

The method for calculating the error bars should be explained (closed form
formula, call to a library function, bootstrap, etc.)

     * •

The assumptions made should be given (e.g., Normally distributed errors).

     * •

It should be clear whether the error bar is the standard deviation or the
standard error of the mean.

     * •

It is OK to report 1-sigma error bars, but one should state it. The authors
should preferably report a 2-sigma error bar than state that they have a 96%
CI, if the hypothesis of Normality of errors is not verified.

     * •

For asymmetric distributions, the authors should be careful not to show in
tables or figures symmetric error bars that would yield results that are out
of range (e.g. negative error rates).

     * •

If error bars are reported in tables or plots, The authors should explain in
the text how they were calculated and reference the corresponding figures or
tables in the text.

  36. 8.

Experiments Compute Resources

  37. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

  38. Answer: [Yes]

  39. Justification: in Section 6 we write about the needed computational resources.

  40. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The paper should indicate the type of compute workers CPU or GPU, internal
cluster, or cloud provider, including relevant memory and storage.

     * •

The paper should provide the amount of compute required for each of the
individual experimental runs as well as estimate the total compute.

     * •

The paper should disclose whether the full research project required more
compute than the experiments reported in the paper (e.g., preliminary or
failed experiments that didn’t make it into the paper).

  41. 9.

Code Of Ethics

  42. Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

  43. Answer: [Yes]

  44. Justification: the research does not violate Ethics Guidelines.

  45. Guidelines:

     * •

The answer NA means that the authors have not reviewed the NeurIPS Code of
Ethics.

     * •

If the authors answer No, they should explain the special circumstances that
require a deviation from the Code of Ethics.

     * •

The authors should make sure to preserve anonymity (e.g., if there is a
special consideration due to laws or regulations in their jurisdiction).

  46. 10.

Broader Impacts

  47. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

  48. Answer: [N/A]

  49. Justification: this is a mostly theoretical paper on convex optimization.

  50. Guidelines:

     * •

The answer NA means that there is no societal impact of the work performed.

     * •

If the authors answer NA or No, they should explain why their work has no
societal impact or why the paper does not address societal impact.

     * •

Examples of negative societal impacts include potential malicious or
unintended uses (e.g., disinformation, generating fake profiles,
surveillance), fairness considerations (e.g., deployment of technologies that
could make decisions that unfairly impact specific groups), privacy
considerations, and security considerations.

     * •

The conference expects that many papers will be foundational research and not
tied to particular applications, let alone deployments. However, if there is a
direct path to any negative applications, the authors should point it out. For
example, it is legitimate to point out that an improvement in the quality of
generative models could be used to generate deepfakes for disinformation. On
the other hand, it is not needed to point out that a generic algorithm for
optimizing neural networks could enable people to train models that generate
Deepfakes faster.

     * •

The authors should consider possible harms that could arise when the
technology is being used as intended and functioning correctly, harms that
could arise when the technology is being used as intended but gives incorrect
results, and harms following from (intentional or unintentional) misuse of the
technology.

     * •

If there are negative societal impacts, the authors could also discuss
possible mitigation strategies (e.g., gated release of models, providing
defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms
to monitor how a system learns from feedback over time, improving the
efficiency and accessibility of ML).

  51. 11.

Safeguards

  52. Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?

  53. Answer: [N/A]

  54. Justification: the paper does not use pretrained models. It only uses open-source data.

  55. Guidelines:

     * •

The answer NA means that the paper poses no such risks.

     * •

Released models that have a high risk for misuse or dual-use should be
released with necessary safeguards to allow for controlled use of the model,
for example by requiring that users adhere to usage guidelines or restrictions
to access the model or implementing safety filters.

     * •

Datasets that have been scraped from the Internet could pose safety risks. The
authors should describe how they avoided releasing unsafe images.

     * •

We recognize that providing effective safeguards is challenging, and many
papers do not require this, but we encourage authors to take this into account
and make a best faith effort.

  56. 12.

Licenses for existing assets

  57. Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

  58. Answer: [Yes]

  59. Justification: we cite the sources of data that we use.

  60. Guidelines:

     * •

The answer NA means that the paper does not use existing assets.

     * •

The authors should cite the original paper that produced the code package or
dataset.

     * •

The authors should state which version of the asset is used and, if possible,
include a URL.

     * •

The name of the license (e.g., CC-BY 4.0) should be included for each asset.

     * •

For scraped data from a particular source (e.g., website), the copyright and
terms of service of that source should be provided.

     * •

If assets are released, the license, copyright information, and terms of use
in the package should be provided. For popular datasets,
paperswithcode.com/datasets has curated licenses for some datasets. Their
licensing guide can help determine the license of a dataset.

     * •

For existing datasets that are re-packaged, both the original license and the
license of the derived asset (if it has changed) should be provided.

     * •

If this information is not available online, the authors are encouraged to
reach out to the asset’s creators.

  61. 13.

New Assets

  62. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

  63. Answer: [N/A]

  64. Justification: our work does not release new assets.

  65. Guidelines:

     * •

The answer NA means that the paper does not release new assets.

     * •

Researchers should communicate the details of the dataset/code/model as part
of their submissions via structured templates. This includes details about
training, license, limitations, etc.

     * •

The paper should discuss whether and how consent was obtained from people
whose asset is used.

     * •

At submission time, remember to anonymize your assets (if applicable). You can
either create an anonymized URL or include an anonymized zip file.

  66. 14.

Crowdsourcing and Research with Human Subjects

  67. Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

  68. Answer: [N/A]

  69. Justification: the paper gives theoretical results in convex optimization and their numerical validation, it does not include crowdsourcing.

  70. Guidelines:

     * •

The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.

     * •

Including this information in the supplemental material is fine, but if the
main contribution of the paper involves human subjects, then as much detail as
possible should be included in the main paper.

     * •

According to the NeurIPS Code of Ethics, workers involved in data collection,
curation, or other labor should be paid at least the minimum wage in the
country of the data collector.

  71. 15.

Institutional Review Board (IRB) Approvals or Equivalent for Research with
Human Subjects

  72. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

  73. Answer: [N/A]

  74. Justification: the work does not include interaction with human subjects and crowdsourcing.

  75. Guidelines:

     * •

The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.

     * •

Depending on the country in which research is conducted, IRB approval (or
equivalent) may be required for any human subjects research. If you obtained
IRB approval, you should clearly state this in the paper.

     * •

We recognize that the procedures for this may vary significantly between
institutions and locations, and we expect authors to adhere to the NeurIPS
Code of Ethics and the guidelines for their institution.

     * •

For initial submissions, do not include any information that would break
anonymity (if applicable), such as the institution conducting the review.