Decentralized Optimization with Coupled Constraints

## Abstract

Abstract We consider the decentralized minimization of a separable objective ∑ i = 1 n f i ⁢ ( x i ) superscript subscript 𝑖 1 𝑛 subscript 𝑓 𝑖 subscript 𝑥 𝑖 \sum_{i=1}^{n}f_{i}(x_{i}) ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT italic_f start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_x start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) , where the variables are coupled through an affine constraint ∑ i = 1 n ( 𝐀 i ⁢ x i − b i ) = 0 superscript subscript 𝑖 1 𝑛 subscript 𝐀 𝑖 subscript 𝑥 𝑖 subscript 𝑏 𝑖 0 \sum_{i=1}^{n}\left(\mathbf{A}_{i}x_{i}-b_{i}\right)=0 ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT ( bold_A start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_x start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT - italic_b start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) = 0 .
We assume that the functions f i subscript 𝑓 𝑖 f_{i} italic_f start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , matrices 𝐀 i subscript 𝐀 𝑖 \mathbf{A}_{i} bold_A start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , and vectors b i subscript 𝑏 𝑖 b_{i} italic_b start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT are stored locally by the nodes of a computational network, and that the functions f i subscript 𝑓 𝑖 f_{i} italic_f start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT 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. (); Nedić et al. (), 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 (), and systems control Dominguez-Garcia et al. ().

$\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. () and power system state estimation Zhang et al. () 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. (); Van den Bergh et al. () 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. ()

$$ $\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. (), as well as in the more general context of decentralized optimization of finite-sum objectives Gorbunov et al. (); Scaman et al. ().

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. ().
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. (); Boyd et al. ().
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 (), based on earlier research in distributed optimization Tsitsiklis (); Bertsekas and Tsitsiklis () and algorithms for decentralized averaging (consensus or gossip algorithms) Boyd et al. (); Olshevsky and Tsitsiklis (), 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. (), 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 (); Kovalev et al. () and stochastic gradients Dvinskikh and Gasnikov ().
Today there also exist algorithms with communication compression Beznosikov et al. (), asynchronous algorithms Koloskova (), algorithms for saddle-point formulations Rogozin et al. () and gradient-free oracles Beznosikov et al. (), making decentralized consensus optimization a quite well-developed field Nedić (); Gorbunov et al. (), benefiting systems control Ram et al. () and machine learning Lian et al. ().

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

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 (); Liang et al. (); Nedić et al. (); Gong and Zhang (); Zhang et al. (); Wu et al. (), nonlinear inequality constraints Liang et al. (); Gong and Zhang (); Wu et al. (), time-varying graphs Zhang et al. (); Nedić et al. () or utilize specific problem structure Wang and Hu ().

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

Works of Doan and Olshevsky (); Li et al. (); Nedić et al. () focus on the resource allocation problem.
For undirected time-varying graphs Doan and Olshevsky () 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. () applies a combination of gradient tracking and push-sum approaches from Nedic et al. () 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. () 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 () 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. (), Chang (), Falsone et al. () 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}$. We denote the identity matrix by $\mathbf{I}_{m}\in\mathbb{R}^{m\times m}$. 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}}$.

We will use a dimension-lifted analogue of the gossip matrix defined as $\mathbf{W}=W\otimes\mathbf{I}_{m}$.
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}}=\sqrt{\frac{L_{\mathbf{W}}}{\mu_{\mathbf{W}}}}\geq\frac{ \lambda_{\max}(\mathbf{W})}{\lambda_{\min^{+}}(\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) $$

###### Assumption 1 .

###### Assumption 2 .

###### Assumption 3 .

## 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}}}=\sqrt{\frac{L_{\mathbf{W^{\prime}}}}{\mu_{\mathbf {W^{\prime}}}}}\geq\frac{\lambda_{\max}(\mathbf{W^{\prime}})}{\lambda_{\min^{+ }}(\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}_{m}^{\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}}}{4 L_{\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+mn)}$ 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.

###### Lemma 1 .

###### Lemma 2 .

### 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 $\mathbf{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:lifted}$ equivalently as $\mathbf{K}u=\mathbf{b}^{\prime}$.

Following Salim et al. () and Scaman et al. (), 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 ().

###### 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}$ is the Chebyshev polynomial of the first kind of degree $n$ defined by $T_{n}(t)=\frac{1}{2}\left(\left(t+\sqrt{t^{2}-1}\right)^{n}+\left(t-\sqrt{t^{2
}-1}\right)^{n}\right)$.
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).

###### Lemma 3 ( Salim et al. ( 2022a ) , Section 6.3.2) .

###### Lemma 4 .

### 4.3 Base algorithm

Figure: Algorithm 1 APAPC

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. () to obtain an optimal algorithm for optimization problems formulated as (21).
See Kovalev et al. (); Salim et al. () for the review of related algorithms and history of their development.

APAPC algorithm formulates as Algorithm 1, and its convergence properties are given in Proposition 1.

###### Proposition 1 ( Salim et al. ( 2022a ) , Proposition 1) .

Assume that the matrix $\mathbf{K}$ in (21) satisfies $\mu_{\mathbf{K}}>0$ and $\mathbf{b}^{\prime}\in\operatorname{\mathrm{range}}\mathbf{K}$, and denote $\kappa_{\mathbf{K}}=\frac{L_{\mathbf{K}}}{\mu_{\mathbf{K}}}$.
Also assume that the function $G$ is $L_{G}$-smooth and $\mu_{G}$-strongly convex.
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$, defined by $D_{G}(u^{\prime},u)=G(u^{\prime})-G(u)-\langle\nabla G(u),u^{\prime}-u\rangle$.

###### Proposition 1 ( Salim et al. ( 2022a ) , Proposition 1) .

## 5 Main results

### 5.1 Algorithm

Figure: Algorithm 2 Main algorithm

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, as well as the derivation of Algorithms 3 and 5 and values of the parameters of Algorithm 2.

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

###### Theorem 1 .

Set the parameter values of Algorithm 2 as $\tau=\min\left\{1,\frac{1}{2}\sqrt{\frac{19}{44\max\left\{1+\kappa_{f},6\right
\}}}\right\}$, $\eta=\frac{1}{4\tau\max\left\{L_{f}+\mu_{f},6\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}$).

###### Theorem 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 et al. () and discrete time Kovalev et al. () 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)=\mathrm{Span}\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)=\mathrm{Span}\left\{\mathbf{A}_{i}^{\top}b_{ i},~{}\mathbf{A}_{i}^{\top}y:~{}y\in\mathcal{H}_{i}(k)\right\},~{}\mathcal{H}_ {i}(k+1)=\mathrm{Span}\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)= \mathrm{Span}\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_{f}$ $\displaystyle=\Omega\left(\sqrt{\kappa}_{f}\log\left(\frac{1}{\varepsilon} \right)\right)~{}\text{gradient computations},$ $\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}$)}.$ $$

A proof of Theorem 2 is provided in Appendix B.

###### Theorem 2 .

## 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. () and DPMM algorithm Gong and Zhang ().
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 () 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: Figure 1: Synthetic, Erdős–Rényi graph, $n=20$, $d_{i}=3$, $m=10$
Refer to caption: x1.png

$\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 (). We split $m=100$ samples subset vertically between $n=7$ devices. Regularization parameter $\lambda=10^{-2}$. The results are in the Fig. 2.

Figure: Figure 2: VFL, Erdős–Rényi graph, $n=7$, $m=100$
Refer to caption: x2.png

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.

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

###### Proof.

### 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 $w\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)}{=}-\|\mathbf{A}^{\top}u\|^{2}+\frac{1}{2}\langle v_ {0},n\mathbf{S}v_{0}\rangle+\gamma^{2}\mu_{\mathbf{W^{\prime}}}\|u\|^{2}$ $\displaystyle\overset{(f)}{\geq}-L_{\mathbf{A}}\|u\|^{2}+\frac{n\mu_{\mathbf{A }}}{2}\|v_{0}\|^{2}+\gamma^{2}\mu_{\mathbf{W^{\prime}}}\|u\|^{2}$ $\displaystyle=-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}$, and
$\|\mathbf{A}^{\top}v\|^{2}=\left\|\begin{pmatrix}\mathbf{A}_{1}^{\top}v_{0}\\
\vdots\\
\mathbf{A}_{n}^{\top}v_{0}\end{pmatrix}\right\|^{2}=\sum_{i=1}^{n}\|\mathbf{A}
_{i}^{\top}v_{0}\|^{2}=\langle v_{0},\sum_{i=1}^{n}\mathbf{A}_{i}\mathbf{A}_{i
}^{\top}v_{0}\rangle=\langle v_{0},n\mathbf{S}v_{0}\rangle$; (f) is due to Assumption 2 and the definition of $v$; (g) is due to eq. 13.

∎

###### Proof.

### A.3 Proof of Theorem 1

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

Let $\mathbf{M}$ be a matrix with $\mu_{\mathbf{M}}>0$, $\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.

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

Proof of Theorem 1

###### Proof.

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 and 28, $\frac{\mu_{\mathbf{A}}+L_{\mathbf{A}}}{L_{\mathbf{A}}}\leq 2$ and $(19/11)^{2}\leq 3$, we get

$$ $\displaystyle L_{G}$ $\displaystyle=\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\}\leq\mu_{f}\max\left\{1+\kappa_{f},6\right\},$ (31) $\displaystyle\mu_{G}$ $\displaystyle=\mu_{f}\min\left\{\frac{1}{2},\frac{\mu_{\mathbf{A}}+L_{\mathbf{ A}}}{4L_{\mathbf{A}}}\right\}\geq\frac{\mu_{f}}{4},$ (32) $\displaystyle\kappa_{G}$ $\displaystyle=\frac{L_{G}}{\mu_{G}}\leq 4\max\left\{1+\kappa_{f},6\right\}.$ (33) $$

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 8\kappa_{\mathbf{A} }+6.$ (34) $$

From eq. 29 we obtain

$$ $\kappa_{\mathbf{K}}=\frac{L_{\mathbf{K}}}{\mu_{\mathbf{K}}}=19/11,$ (35) $$

and substituting eqs. 34 and 33 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.
The values of the parameters $\tau,\eta,\theta,\alpha$ in Theorem 1 are derived from Proposition 1 as follows. We have $\tau=\min\left\{1,\frac{1}{2}\sqrt{\frac{\kappa_{\mathbf{K}}}{\kappa_{G}}}
\right\}=\min\left\{1,\frac{1}{2}\sqrt{\frac{19}{44\max\left\{1+\kappa_{f},6
\right\}}}\right\}$ due to eqs. 35 and 33;
$\eta=\frac{1}{4\tau L_{G}}=\frac{1}{4\tau\max\left\{L_{f}+\mu_{f},6\mu_{f}
\right\}}$ due to eq. 31;
$\theta=\frac{15}{19\eta}$ due to eq. 29 and $\alpha=\mu_{G}=\frac{\mu_{f}}{4}$ due to eq. 32.
∎

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

###### Proof.

## 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 z,\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}z,x_{i}\right\rangle-f_{i}(x_{i})\right]$ $\displaystyle\quad=-\min_{w}\sum_{i=1}^{n}f_{i}^{*}(\mathbf{A}_{i}^{\top}z).$ $$

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

$$ $\displaystyle\min_{z_{1},\ldots,z_{n}}~{}$ $\displaystyle\sum_{i=1}^{n}g_{i}(z_{i}):=\sum_{i=1}^{n}f_{i}^{*}(\mathbf{A}_{i }^{\top}z_{i})$ (36) $\displaystyle\text{s.t. }\mathbf{W}z=0$ (37) $$

### B.2 Example graph

We follow the principle of lower bounds construction introduced in Kovalev et al. [] and take the example graph from Scaman et al. []. Let the functions be held by the nodes be organized into a path graph with $n$ vertices, where $n$ is divisible by $3$. The nodes of graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ 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.

Now we recall the construction from Scaman et al. []. Let $\gamma_{n}=\frac{1-\cos\left(\frac{\pi}{3n}\right)}{1+\cos\left(\frac{\pi}{3n}
\right)}$. Since $\gamma_{n}\overset{n\to\infty}{\rightarrow}0$, there exists $n\geq 1$ such that $\gamma_{n}\geq\frac{1}{\chi}>\gamma_{n+1}$. Introduce edge weights $w_{i,i+1}=1-a\mathbb{I}\left\{i=1\right\}$, take the corresponding weighed Laplacian $W_{a}$ and denote its condition number $\chi$. If $a=1$, the network is disconnected and therefore $\chi(W_{a})=\infty$. If $a=0$, we have $\chi(W_{a})=1/\gamma_{n}$. By continuity of Laplacian spectra we obtain that for some $a\in[0,1)$ it holds $\chi(W_{a})=\chi$. Note that

$$ $\displaystyle\gamma_{n}=\frac{1-\cos\frac{\pi}{3n}}{1+\cos\frac{\pi}{3n}}\leq \frac{\pi^{2}}{9n^{2}}~{}~{}\Rightarrow~{}~{}\chi\geq\frac{9n^{2}}{\pi^{2}} \geq n^{2}.$ (38) $$

### B.3 Example functions

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}}}}{\mu_{f}}u_{1}.$ $$

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

$$ $\displaystyle\mathbf{E}_{1}=\begin{pmatrix}1&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},~{}~{}~{}~{}\mathbf{E}_{2}=\begin{pmatrix}1&-1&0&0&0&\ldots&\\ 0&0&0&0&0&\ldots&\\ 0&0&1&-1&0&\ldots&\\ 0&0&0&0&0&\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 }\\ [~{}~{}~{}\mathbf{0}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\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}}\mathbf{I}\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=\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})\right)$ $\displaystyle=\frac{2}{3}\hat{\mu}_{\mathbf{A}}=\mu_{\mathbf{A}}.$ $$

Let $\widetilde{\mathbf{M}}=\begin{pmatrix}~{}~{}~{}1&-1\\
-1&~{}~{}~{}1\end{pmatrix}$ and

$$ $\displaystyle\mathbf{M}_{1}$ $\displaystyle=\mathbf{E}_{1}^{\top}\mathbf{E}_{1}=\begin{pmatrix}1&0&0&\ldots \\ 0&\widetilde{\mathbf{M}}&0&\ldots\\ 0&0&\widetilde{\mathbf{M}}&\ldots\\ \vdots&\vdots&\vdots&\ddots\end{pmatrix},~{}~{}~{}~{}\mathbf{M}_{2}=\mathbf{E} _{2}^{\top}\mathbf{E}_{2}=\begin{pmatrix}\widetilde{\mathbf{M}}&0&0&\ldots\\ 0&\widetilde{\mathbf{M}}&0&\ldots\\ 0&0&\widetilde{\mathbf{M}}&\ldots\\ \vdots&\vdots&\vdots&\ddots\end{pmatrix}$ $$

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{\hat{L}_{\mathbf{A}}}{2\mu_{f}}z_{1},&i\in\mathcal{V}_{1}\\ 0,&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{\hat{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{M}_{1}+\frac{\hat{\mu}_{\mathbf{A}}}{L_{f}}\mathbf{I}\right) z-\frac{\hat{L}_{\mathbf{A}}}{2\mu_{f}}z_{1},&i\in\mathcal{V}_{1}\\ 0,&i\in\mathcal{V}_{2}\\ \frac{1}{2}z^{\top}\left(\frac{\hat{L}_{\mathbf{A}}}{\mu_{f}}\mathbf{M}_{2}+ \frac{\hat{\mu}_{\mathbf{A}}}{L_{f}}\mathbf{I}\right)z-\frac{\hat{L}_{\mathbf{ A}}}{2\mu_{f}}z_{1},&i\in\mathcal{V}_{3}\end{cases}$ (39) $$

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{M}_{1}+\mathbf{M}_{2})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{\hat{\mu}_{\mathbf{A}}\mu_{f}}{\hat{L}_{ \mathbf{A}}L_{f}}z^{\top}z\right],$ $$

where

$$ $\displaystyle\mathbf{M}=\mathbf{M}_{1}+\mathbf{M}_{2}=\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}.$ $$

Now we formulate the lower complexity bounds for $\sum_{i=1}^{n}g_{i}(z)$, where $g_{i}(z)$ are defined in (39).

### B.4 Deriving the lower bound

Let us introduce the local memory $\mathcal{Z}_{i}(k)$ which is updated as follows.
1. If the algorithm performs a local gradient computation, then

$$ $\displaystyle\mathcal{Z}_{i}(k+1)=\mathrm{Span}\left\{x,\nabla f_{i}(x),\nabla f _{i}^{*}(x):~{}x\in\mathcal{Z}_{i}(k)\right\}.$ $$

2. If the algorithm performs a communication rounds, then

$$ $\displaystyle\mathcal{Z}_{i}(k+1)=\mathrm{Span}\left\{x:~{}x\in\mathcal{Z}_{j} (k),~{}(i,j)\in\mathcal{E}\right\}.$ $$

###### Lemma 6 .

Function $\sum_{i=1}^{n}g_{i}(z)$ attains its minimum at $z^{*}=\left\{\rho^{k}\right\}_{k=1}^{\infty}$, where

$$ $\displaystyle\rho=\frac{\sqrt{\frac{2}{3}\frac{L_{A}L_{f}}{\mu_{A}\mu_{f}}+1}- 1}{\sqrt{\frac{2}{3}\frac{L_{A}L_{f}}{\mu_{A}\mu_{f}}+1}+1}.$ $$

###### Proof.

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

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

attains its minimum at $z_{k}^{*}=\rho^{k}$, where

$$ $\displaystyle\rho=\frac{\sqrt{\frac{2L}{3\mu}+\frac{1}{3}}-1}{\sqrt{\frac{2L}{ 3\mu}+\frac{1}{3}}+1}$ $$

Let us deduce the expression for $L,\mu$ in terms of $L_{A},L_{f},\mu_{A},\mu_{f}$. We enforce $h(z)=\sum_{i=1}^{n}g_{i}(z)$ and get

$$ $\displaystyle\frac{3\mu}{L-\mu}=\frac{\mu_{A}\mu_{f}}{L_{A}L_{f}}\Rightarrow \frac{L}{\mu}=1+\frac{L_{A}L_{f}}{\mu_{A}\mu_{f}}.$ $$

Therefore, for $\rho$ we obtain

$$ $\displaystyle\rho=\frac{\sqrt{\frac{2}{3}\frac{L_{A}L_{f}}{\mu_{A}\mu_{f}}+1}- 1}{\sqrt{\frac{2}{3}\frac{L_{A}L_{f}}{\mu_{A}\mu_{f}}+1}+1}.$ $$

∎

Let us first show the lower bound on the number of communications.

###### Lemma 7 .

Let $s_{i}(k)$ denote the maximum index of a nonzero component of vector held by $i$-th node at step $k$, i.e.

$$ $\displaystyle s_{i}(k)=\begin{cases}0,&\mathcal{Z}_{i}(k)\subseteq\left\{0 \right\}\\ \min\left\{s\in\left\{1,2,\ldots\right\}:\mathcal{Z}_{i}(k)\subseteq\mathrm{ Span}\left\{e_{1},\ldots,e_{s}\right\}\right\},&\text{else}.\end{cases}$ $$

Let $k_{q}$ denote the the number of algorithm step by which exactly $q$ communication steps have been performed, where $q\geq 0$. For any $k\in\left\{1,\ldots,k_{q}\right\}$ we have

$$ $\displaystyle\max_{i}s_{i}(k)\leq 2+\left\lfloor\frac{q}{\frac{n}{3}+1}\right\rfloor$ (40) $$

###### Proof.

Note that from the structure of $g_{i}(z)$, if the method performs a computation step, then

$$ $\displaystyle s_{i}(k+1)\leq s_{i}(k)+\begin{cases}1-(s_{i}(k)\mod 2),&i\in \mathcal{V}_{1}\\ 0,&i\in\mathcal{V}_{2}\\ (s_{i}(k)\mod 2),&i\in\mathcal{V}_{3}\end{cases}$ $$

Due to the structure of network, if the method makes a communication round, it follows

$$ $\displaystyle s_{i}(k+1)\leq\begin{cases}\max\left(s_{i-1}(k),s_{i}(k),s_{i+1} (k)\right),&i\in\left\{2,\ldots,n-1\right\}\\ \max\left(s_{1}(k),s_{2}(k)\right),&i=1\\ \max\left(s_{n-1}(k),s_{n}(k)\right),&i=n\end{cases}$ (41) $$

We will prove that
1. For $q=2\ell(n/3+1),~{}\ell\in\left\{0,1,\ldots\right\}$ we have

$$ $\displaystyle s_{i}(k_{q})\leq\begin{cases}1+2\ell,~{}~{}i\in\mathcal{V}_{1}\\ 1+2\ell,~{}~{}i\in\mathcal{V}_{2}\\ 2+2\ell,~{}~{}i\in\mathcal{V}_{3}\end{cases}$ (42) $$

2. For $q=(2\ell+1)(n/3+1),~{}\ell\in\left\{0,1,\ldots\right\}$ we have

$$ $\displaystyle s_{i}(k_{q})\leq\begin{cases}2+(2\ell+1),~{}~{}i\in\mathcal{V}_{ 1}\\ 1+(2\ell+1),~{}~{}i\in\mathcal{V}_{2}\\ 1+(2\ell+1),~{}~{}i\in\mathcal{V}_{3}\end{cases}$ (43) $$

The proof follows by induction.

Induction basis. Let $q=0$. From definitions of $g_{i}(z)$ it follows that

$$ $\displaystyle s_{i}(k_{0})\leq\begin{cases}1,~{}~{}i\in\mathcal{V}_{1}\\ 0,~{}~{}i\in\mathcal{V}_{2}\\ 2,~{}~{}i\in\mathcal{V}_{3}\end{cases}$ $$

Therefore, for $q=0$ our statement holds.

Induction step for $q=(2\ell+1)(n/3+1)$. Consider $q_{-}=q-n/3=2\ell(n/3+1)$. From (42) we have that for the spread of nonzero components from $\mathcal{V}_{3}$ to $\mathcal{V}_{1}$ it requires $n/3$ communication rounds to reach node $n/3+1$. After one more communication round, the information reaches node $n/3$.

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

We just proved the statement of lemma, i.e. relation (40), for $q$ divisible by $(n/3+1)$. Between such checkpoints, the information (i.e. the number of nonzero components) traverses nodes of $\mathcal{V}_{2}$ and therefore $\max_{i}s_{i}(k)$ stays unchanged. Thus the statement of the lemma is proven.
∎

Now we estimate the distance to optimum.

$$ $\displaystyle\|z_{i}(k)-z^{*}\|_{2}^{2}$ $\displaystyle\geq\sum_{\ell=s_{i}(k)+1}^{\infty}(z_{i}(k)-z^{*})^{2}=\sum_{ \ell=s_{i}(k)+1}^{\infty}\rho^{2\ell}=\frac{\rho^{2s_{i}(k)+2}}{1-\rho^{2}}= \frac{\rho^{6+2\left\lfloor\frac{q}{n/3+1}\right\rfloor}}{1-\rho^{2}}$ $\displaystyle\overset{(a)}{\geq}\frac{\rho^{6+\frac{2q}{2n/3}}}{1-\rho^{2}}= \frac{\rho^{6}}{1-\rho^{2}}\cdot\rho^{\frac{3q}{n}}\overset{(b)}{=}\frac{\rho^ {6}}{1-\rho^{2}}\cdot\rho^{\frac{3q}{\sqrt{\chi}}},$ $$

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

Following Kovalev et al. [], we obtain that

$$ $\displaystyle\rho\geq\max\left(0,1-\sqrt{\frac{6\mu_{A}\mu_{f}}{L_{A}L_{f}}} \right).$ $$

Therefore,

$$ $\displaystyle\|z_{i}(k)-z^{*}\|_{2}^{2}\geq\frac{\rho^{6}}{1-\rho^{2}}\left( \max\left(0,1-\sqrt{\frac{6\mu_{A}\mu_{f}}{L_{A}L_{f}}}\right)\right)^{\frac{3 q}{\sqrt{\chi}}}.$ $$

It follows that the number of communications is lower bounded as

$$ $\displaystyle N_{\mathbf{W}}\geq\Omega\left(\sqrt{\chi}\sqrt{\frac{L_{A}L_{f}} {\mu_{A}\mu_{f}}}\log\left(\frac{1}{\varepsilon}\right)\right)$ $$

and the number of oracle calls of $g_{i}(z)$ at each node (that is, the number of local matrix multiplications by $A_{i}$) is lower bounded as

$$ $\displaystyle N_{\mathbf{A}}\geq\Omega\left(\sqrt{\frac{L_{A}L_{f}}{\mu_{A}\mu _{f}}}\log\left(\frac{1}{\varepsilon}\right)\right).$ $$

###### Lemma 6 .

###### Proof.

###### Lemma 7 .

###### Proof.

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

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

$$ $\displaystyle\min_{x_{1},\ldots x_{n}\in\mathbb{R}^{d}}~{}$ $\displaystyle\sum_{i=1}^{n}f_{i}(x_{i})+\sum_{i=1}^{n}v_{i}(u_{i})$ s.t. $\displaystyle\sum_{i=1}^{n}A_{i}x_{i}=0$ $$

where all $v_{i}(u)$ are the same and $v_{i}(u_{i})=g(u)=\sum_{j=1}^{n}g_{j}(u)$ and $g_{j}(u)$ are defined in (39). All $v_{i}(u)$ are the same and are defined as

$$ $\displaystyle v_{i}(u_{i})=\frac{1}{2}u_{i}^{\top}\mathbf{M}u_{i}+\frac{\mu_{f }}{L_{f}}u^{\top}u-u_{1}.$ $$

Since there is no communication constraint on $u_{i}$, each node runs optimization process individually. Following the same arguments as for function $g(z)$, we get the lower bound on the number of oracle calls

$$ $\displaystyle N_{f}\geq\Omega\left(\sqrt{\frac{L_{f}}{\mu_{f}}}\log\left(\frac {1}{\varepsilon}\right)\right).$ $$

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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)?

2. In the simulation section, how do you tune the hyperparameters?

3. 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$.

4. It is recommended to evaluate the algorithm using more real-world datasets and more complex experiments, such as logistic regression.
soundness: 3
strengths: This paper is well-written and presents several key strengths:

1. The reformulation from problem (1) to problem (20) is novel and insightful, providing a strong foundation for the development of an optimal algorithm.

2. It establishes the first lower bound for decentralized optimization under affine constraints.

3. 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.
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.
weaknesses: However, this paper has several notable weaknesses:

1. 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.

2. 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.

3. The numerical experiments are too trivial.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
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?
soundness: 4
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.

The theoretical results offered by the authors, if correct, is tight and optimal.

The 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.
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.
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.

The 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. 

A 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.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
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?  
- Have you tried tuning the value of r in the experiments? What would be the impact?
soundness: 3
strengths: - Tight analysis (optimal algorithm + lower bound) 
- Efficient off-the-shelf algorithm
- Authors clearly state their contributions and how they leverage previous work

I 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.
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.
weaknesses: - Rather incremental contribution. All results directly derive from existing ones on the reformulation from (10), which is rather natural (though not straightforward).

In 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.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: See weakness.
soundness: 3
strengths: 1. first order iterations.
2. match the lower bound.
3. suitable for different kinds of problems.
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.
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.

2. 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.

3.  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. 

[1] Distributed Optimization With Coupling Constraints.

[2] EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization

Meta-review: The paper addresses decentralized optimization of a separable objective with affine coupled constraints, relevant to resource allocation, systems control, and distributed machine learning. It establishes lower complexity bounds and proposes a first-order algorithm that achieves these bounds, with linear convergence for general affine constraints—marking a first in this setting.

Most of the reviewers believe that the paper makes substantial contributions, and the AC also agrees with this assessment.

Decision: Accept (Poster)