# Detailed Derivations of “A Privacy-Preserving Finite-Time Push-Sum based
Gradient Method for Distributed Optimization over Digraphs”

Xiaomeng Chen1, Wei Jiang2, Themistoklis Charalambous3, , and Ling Shi1 1X.
Chen and L. Shi are with the Department of Electronic and Computer
Engineering, Hong Kong University of Science and Technology, Clear Water Bay,
Kowloon, Hong Kong (email<EMAIL_ADDRESS>eesling@ust.hk).2W. Jiang
e-mail<EMAIL_ADDRESS>3T. Charalambous is with the Department of
Electrical and Computer Engineering, School of Engineering, University of
Cyprus, Nicosia, Cyprus. He is also a Visiting Professor at Aalto University,
Espoo, Finland, and FinEst Centre for Smart Cities, Tallinn, Estonia. (e-mail:
charalambous.themistoklis@ucy.ac.cy).

###### Abstract

This paper addresses the problem of distributed optimization, where a network
of agents represented as a directed graph (digraph) aims to collaboratively
minimize the sum of their individual cost functions. Existing approaches for
distributed optimization over digraphs, such as Push-Pull, require agents to
exchange explicit state values with their neighbors in order to reach an
optimal solution. However, this can result in the disclosure of sensitive and
private information. To overcome this issue, we propose a state-decomposition-
based privacy-preserving finite-time push-sum (PrFTPS) algorithm without any
global information, such as network size or graph diameter. Then, based on
PrFTPS, we design a gradient descent algorithm (PrFTPS-GD) to solve the
distributed optimization problem. It is proved that under PrFTPS-GD, the
privacy of each agent is preserved and the linear convergence rate related to
the optimization iteration number is achieved. Finally, numerical simulations
are provided to illustrate the effectiveness of the proposed approach.

###### Index Terms:

Distributed optimization, privacy-preserving, finite-time consensus, directed
graph.

##  I INTRODUCTION

In this paper, we consider an optimization problem in a multi-agent system of
$n$ agents. Each agent $i$ has a private cost function $f_{i}$, which is known
to itself only. All the agents aim to collaboratively solve the following
optimization problem

$\min\limits_{x\in\mathbb{R}^{p}}F(x):=\sum_{i=1}^{n}f_{i}(x),$ (1)

where $x$ is the global decision variable. The agents are connected through a
communication graph and can only transmit messages to their neighbors. By
local computation and communication, each agent seeks a solution that
minimizes the sum of all the local objective functions. Such a distributed
paradigm facilitates breaking large-scale problems into sequences of smaller
ones. That is why it has been widely adopted in several applications, such as
power grids [1], sensor networks [2] and vehicular networks [3].

To solve problem (1), decentralized gradient descent (DGD) is the most
commonly used algorithm, requiring diminishing stepsizes to ensure optimality
[4]. To overcome the challenge of slow convergence caused by diminishing
stepsizes, Xu et al.[5] adopted the dynamic average consensus [6] to propose a
gradient tracking (GT) method with a constant stepsize. Recently, Xin et al.
[7] and Pu et al. [8] devised a modified GT algorithm called AB/Push-Pull
algorithms for distributed optimization, which can be applied to a general
digraph. A comprehensive survey on distributed optimization algorithms is
provided by Yang et al. [9].
The aforementioned distributed algorithms share state values in each
iteration, which can compromise the privacy of agents if they have private
information. By hacking into communication links, an adversary could
potentially access to transmitted messages among agents and potentially gather
private information using an inferring algorithm. Mandal[10] presented
theoretical analysis of privacy disclosure in distributed optimization, where
the parameters of cost functions and generation power can be correctly
inferred by an adversary. As the number of privacy leakage events is
increasing, there is an urgent need to preserve privacy of each agent in
distributed systems.

Recently, many results have been reported on the topic of privacy-preserving
distributed optimization. One commonly used approach is differential privacy
(DP) [11] due to its rigorous mathematical framework, proven privacy
preservation properties and ease of implementation [12]. However, DP-based
approaches face a fundamental trade-off between privacy and accuracy, which
may result in suboptimal solutions [13]. To address this challenge, Lu et al.
[14] combined distributed optimization methods with partially homomorphic
encryption. Nonetheless, this approach has limitations due to high computation
complexity and communication costs. To overcome these limitations and achieve
accurate results, Wang [15] proposed a privacy-preserving average consensus
using a state decomposition mechanism that divides the state of a node into
two sub-states.

It is worth noting that none of the aforementioned approaches is suitable for
agents over digraphs. To preserve privacy of nodes interacting on a digraph,
Charalambous et al. [16] proposed an offset-adding privacy-preserving push-
sum, and Gao et al. [17] protected privacy by adding randomness on edge
weights, both of which are only effective against honest-but-curious nodes
(see Definition 3). To improve resilience to external eavesdroppers (see
Definition 4), Chen et al. [18] extended the state decomposition mechanism to
digraphs and introduced an uncertainty-based privacy notion. In terms of
privacy-preserving distributed optimization over digraphs, Mao et al. [19]
designed a privacy-preserving algorithm based on the push-gradient method with
a decaying stepsize, which lacked a formal privacy notion. Wang and Nedić [20]
designed a DP-oriented gradient tracking based algorithm (DPGT) that can
ensure both differential privacy and optimality. However, it adopted a
diminishing stepsize to ensure convergence, resulting in a slow convergence
rate. To speed up the convergence, Chen et al. [21] proposed a state-
decomposition-based push-pull (SD-Push-Pull) algorithm, which guarantees both
linear convergence and differential privacy for digraphs. Nevertheless, SD-
Push-Pull only converges to a suboptimal value.

Inspired by recent results that privacy can be enabled in consensus over
digraphs by state decomposition [18] and that finite-time push-sum can be used
in distributed optimization to deliver the optimal solution [22], this paper
presents a novel PrFTPS algorithm that accurately computes the average value
for digraphs in a finite time, as opposed to the asymptotic average consensus
achieved in [18]. Then, combined with gradient decent, PrFTPS-GD is proposed
to solve problem (1) allowing each node in a digraph to achieve optimal value
linearly while preserving its privacy. The main contributions of this paper
are summarized as follows:

  1. 1.

We propose PrFTPS (Algorithm III-A1) based GD algorithm (Algorithm III-B) to
solve problem (1) over digraphs. Moreover, we show that Algorithm III-A1 can
compute the exact average value in finite time and Algorithm III-B guarantees
the linear convergence to the optimal value of problem (1) (Theorem 1).

  2. 2.

We analyze the privacy-preserving performance of PrFTPS-GD against honest-but-
curious nodes and eavesdroppers (Theorem 2). Specifically, we adopt the
uncertainty-based privacy notion [18] and show that the adversary has infinite
uncertainty about agents’ private information under certain topological
conditions.

  3. 3.

PrFTPS-GD performance is evaluated via simulations and compared with other
state-of-the-art privacy-preserving approaches (e.g., [20, 21]) over digraphs.
It is shown that our approach apart from adopting an easily tuned constant
stepsize (unlike the diminishing stepsize in [20]), it computes the optimal
solution instead of the suboptimal one in [21].

Notations: In this paper, $\mathbb{R}^{n}$ and $\mathbb{R}^{n\times p}$
represent the set of $n$ dimensional vectors and $n\times p$ dimensional
matrices. $\mathbb{Z}_{++}$ denotes the set of positive integers.
$\mathbf{1}_{n}\in\mathbb{R}^{n}$, $\mathbf{I}_{n}\in\mathbb{R}^{n\times n}$
and $\mathbf{0}_{n}\in\mathbb{R}^{n\times n}$ represent the vector of ones,
the identity matrix and the zero matrix, respectively. For an arbitrary vector
$\bm{x},$ we denote its $i$th element by $\bm{x}_{i}$. For an arbitrary matrix
$\bm{M},$ we denote its element in the $i$th row and $j$th column by
$[\bm{M}]_{ij}$. $\otimes$ denotes the Kronecker product. The spectral radius
of matrix $\mathbf{A}$ is denoted by $\rho(\mathbf{A})$. Matrix $\mathbf{A}$
is called row-stochastic if the sum of each row equals to $1$ and the entries
of $\mathbf{A}$ are non-negative. Similarly, matrix $\mathbf{A}$ is called
column-stochastic if the sum of each column equals to $1$ and the entries of
$\mathbf{A}$ are non-negative.

##  II PRELIMINARIES AND PROBLEM STATEMENT

###  II-A Network Model

We consider a digraph $\mathcal{G}\triangleq(\mathcal{V},\mathcal{E})$ with
$n$ nodes, where the set of nodes and edges are $\mathcal{V}=\\{1,\ldots,n\\}$
and $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$, respectively. A
communication link from node $i$ to node $j$ is denoted by
$\varepsilon_{ji}=(j,i)\in\mathcal{E}$, indicating that node $i$ can send
messages to node $j$. The nodes who can send messages to node $i$ are denoted
as in-neighbours of node $i$ and the set of these nodes is denoted as
$N_{i}^{-}=\\{j\in\mathcal{V}\mid\varepsilon_{ij}\in\mathcal{E}\\}$.
Similarly, the nodes who can receive messages from node $i$ are denoted as
out-neighbours of node $i$ and the set of these nodes is denoted as
$N_{i}^{+}=\\{j\in\mathcal{V}\mid\varepsilon_{ji}\in\mathcal{E}\\}$. The
cardinality of $N_{j}^{+}$ , is called the out-degree of node $j$ and is
denoted as $\mathcal{D}^{+}_{j}=|N_{j}^{+}|$. A digraph is called strongly
connected if there exists at least one directed path from any node $i$ to any
node $j$ with $i\neq j$.

###  II-B Push-Sum Algorithm

The push-sum algorithm, introduced originally in [23], aims at achieving
average consensus for each node communicating over a digraph which satisfies
the following assumption.

###### Assumption 1

The digraph $\mathcal{G}$ is assumed to be strongly connected.

Consider a network of $n$ nodes, where each node has a private initial state,
termed as $x_{i}(0)$. The push-sum algorithm introduces two auxiliary
varaibles, $x_{i,1}(k)$ and $x_{i,2}(k)$, and assumes the out-degree is known
for each node. The details are as follows: for each node $i$,

$x_{i,l}(k+1)=\sum\limits_{j\in
N^{-}_{i}\cup\\{i\\}}p_{ij}(k)x_{j,l}(k),\qquad k\geq 0,l=1,2,$

where $p_{ij}(k)=1/(1+\mathcal{D}^{+}_{j}),\forall i\in N_{j}^{+}\cup\\{j\\}$
and $x_{i,1}(0)=x_{i}(0),x_{i,2}(0)=1$ for $i\in\mathcal{V}$.
Proposition 1. [23] If a digraph $\mathcal{G}(\mathcal{V},\mathcal{E})$ with
$n$ nodes satisfies Assumption 1, then the ratio
$r_{i}(k):=x_{i,1}(k+1)/x_{i,2}(k+1)$ asymptotically converges to the average
of the initial values, i.e., we have

$\lim\limits_{k\rightarrow\infty}r_{i}(k)=\frac{\sum_{i\in\mathcal{V}}x_{i}(0)}{n},\forall
i\in\mathcal{V}.$

###  II-C Information Set and Privacy Inferring Model

Before defining privacy, we first introduce the privacy inferring model. The
adversary set $\mathcal{A}$ is assumed to obtain some online data by
eavesdropping on some edges $\mathcal{E}_{r}\subseteq\mathcal{E}$ and nodes
$\mathcal{V}_{a}\subseteq\mathcal{V}$. The information set accessible to
$\mathcal{A}$ at time $k$ is denoted as $\mathcal{I}_{\mathcal{A}}(k)$, which
contains all transmitted information accessible to $\mathcal{A}$.

Then all the information accessible to $\mathcal{A}$ at time iteration $K$ is
denoted as
$\mathcal{I}_{\mathcal{A}}(0:K)\triangleq\\{\mathcal{I}_{\mathcal{A}}(0),\mathcal{I}_{\mathcal{A}}(1),\ldots,\mathcal{I}_{\mathcal{A}}(K)\\}$.

With the above model, we adopt an uncertainty-based notion of privacy, which
is proposed in [18]. Denote the private information of node $i$ as
$x_{p,i}\in\mathbb{R}^{p}$ and define a set
$\Delta\mathcal{I}_{\mathcal{A}}({\color[rgb]{0,0,0}x_{p,i}})$ as

$\Delta\mathcal{I}_{\mathcal{A}}({\color[rgb]{0,0,0}x_{p,i}})=\\{\bar{x}_{p,i}\mid\text{the
adversary's information set }=\mathcal{I}_{\mathcal{A}}(0:K)\\},$

which contains all possible states that can correspond to $x_{p,i}$ when the
information set accessible to $\mathcal{A}$ is
$\mathcal{I}_{\mathcal{A}}(0:K)$.

The diameter of $\Delta\mathcal{I}_{\mathcal{A}}(x_{p,i})$ is defined as

$\text{Diam}\\{\Delta\mathcal{I}_{\mathcal{A}}(x_{p,i})\\}=\sup\limits_{\bar{x}_{p,i},\bar{x}_{p,i}^{\prime}\in\
\Delta\mathcal{I}_{\mathcal{A}}(x_{p,i})}|\bar{x}_{p,i}-\bar{x}_{p,i}^{\prime}|,$

where $\bar{x}_{p,i}$ and $\bar{x}_{p,i}^{\prime}$ are two different states
that belong to set $\Delta\mathcal{I}_{\mathcal{A}}(x_{p,i})$.

###### Definition 1

The privacy of $x_{p,i}$ is preserved against $\mathcal{A}$ if
$\text{Diam}\\{\Delta\mathcal{I}_{\mathcal{A}}(x_{p,i})\\}=\infty$.

In this paper, we consider distributed optimization problems, where local
objective gradients usually carry sensitive information. For example, in
distribited-optimization-based localization and rendezvous, directly
exchanging the gradient of an agent leads to disclosing its position [13].
Recent work shows that gradients are directly calculated from and embed
sensitive information of training learning data [24]. Hence, the private
information is the gradient of each agent at all time iteration. Then, we
define the privacy preservation of each agent as follow.

###### Definition 2

For a network of $n$ agents in distributed optimization, the privacy of agent
$j$ is preserved against $\mathcal{A}$ if the privacy of its gradient value
$\nabla f_{j}(x_{j})$ evaluated at any point $x_{j}$ is preserved.

We consider two types of adversaries, defined as follows.

###### Definition 3

An honest-but-curious adversary is a node or a group of nodes which knows the
network topology and follows the system’s protocol, attempting to infer the
private information of other nodes.

###### Definition 4

An eavesdropper is an external adversary who has the knowledge of network
topology, and is able to eavesdrop on a portion of coupling weights and
transmitted data.

##  III Main results

In this section, we first propose a privacy-preserving finite-time push-sum
algorithm via a state decomposition mechanism. Then, we adopt the proposed
privacy-preserving approach to address problem (1) based on a gradient descent
approach.

###  III-A Privacy-Preserving Finite-Time Push-Sum Algorithm

The main idea of our privacy-preserving approach is a state decomposition
mechanism.

Decomposition Mechanism: Let each node decompose its state $x_{i,l}(k)$ into
two substates $x^{\alpha}_{i,l}(k)$ and $x^{\beta}_{i,l}(k)$, $l=1,2$. The
initial values $x^{\alpha}_{i,l}(0)$ and $x^{\beta}_{i,l}(0)$ can be randomly
chosen from the set of all real numbers under the following constraint

$x_{i,1}^{\beta}(0)+x_{i,1}^{\alpha}(0)=2x_{i}(0),x_{i,2}^{\alpha}(0)=0,x_{i,2}^{\beta}(0)=2,\forall
i\in\mathcal{V},$

where $x_{i}(0)$ denotes the private initial state of node $i$.

Under the state decomposition mechanism, the overall dynamics become

$\left\\{\begin{aligned} &x_{i,l}^{\alpha}(k+1)=\sum\limits_{j\in
N^{-}_{i}\cup\\{i\\}}p_{ij}(k)x^{\alpha}_{j,l}(k)+a_{i}^{\alpha,\beta}(k)x^{\beta}_{i,l}(k),\\\
&x^{\beta}_{i,l}(k+1)=a_{i}^{\beta,\alpha}(k)x^{\alpha}_{i,l}(k)+a_{i}^{\beta,\beta}(k)x^{\beta}_{i,l}(k),\end{aligned}\right.$
(2)

with $i\in\mathcal{V}$, $l=1,2$. In this decomposition scheme, the substate
$x^{\alpha}_{i,l}(k)$ is exchanged with other nodes while $x^{\beta}_{i,l}(k)$
is never shared with other nodes. The coupling weights between the two
substates $x^{\alpha}_{i,l}(k)$ and $x^{\beta}_{i,l}(k)$ are asymmetric and
denoted as $a_{i}^{\alpha,\beta}(k)$ and $a_{i}^{\beta,\alpha}(k)$. The update
weights for substate $x^{\beta}_{i,l}(k)$ is denoted as
$a_{i}^{\beta,\beta}(k)$. The outgoing link weight from agent $i$ to agent $j$
is denoted as $p_{ji}(k)$. These are design parameters and will be designed in
the following weight mechanism (Section III-A1).

We next introduce details of the weight mechanism to enable algorithm
convergence and privacy preservation.

####  III-A1 Weight mechanism

For $k=0,\forall i\in\mathcal{V}$, we set
$a_{i}^{\beta,\beta}(0)=0,a_{i}^{\alpha,\beta}(0)=1$ and $p_{ji}(0)=0,\forall
j\notin N_{i}^{+}$. Also, we allow $p_{ji}(0),\forall j\in
N_{i}^{+}\cup\\{i\\}$ and $a_{i}^{\beta,\alpha}(0)$ to be arbitrarily chosen
from the set of all real numbers under the constraint

$\sum_{j=1}^{n}p_{ji}(0)+a_{i}^{\beta,\alpha}(0)=1.$

For $k\geq 1$, we let $p_{ji}(k)=1(2+\mathcal{D}_{i}^{+})$ for $j\in
N_{i}^{+}\cup\\{i\\}$ and $p_{ji}(k)=0$, otherwise. Also,

$a_{i}^{\beta,\alpha}(k)=\frac{1}{2+\mathcal{D}_{i}^{+}},\quad
a_{i}^{\beta,\beta}(k)=a_{i}^{\alpha,\beta}(k)=\frac{1}{2}.$

###### Remark 1

Under the above weight mechanism, the state-decomposition-based push-sum (2)
still preserves the property of conventional push-sum. Rigorous theoretical
analysis will be provided in Section III-C.

To obtain the exact average value in finite time, we use the minimal
polynomial associated with iteration (2), in conjunction with the final value
theorem [25, 26]. Next, we provide definitions on minimal polynomials.

###### Definition 5

(Minimal Polynomial of a Matrix.) The minimal polynomial of matrix $P$,
denoted by

$Q(t)=t^{D+1}+\sum\limits_{i=0}^{D}\alpha_{i}t^{i},$

is the monic polynomial of minimum degree $D+1$ that satisfies $Q(P)=0_{n}$
and $\alpha_{i}$ is the polynomial coefficient.

###### Definition 6

(Minimal Polynomial of a Matrix Pair.) The minimal polynomial associated with
$[P,e^{\top}_{j}]$, denoted by

$Q_{j}(t)=t^{D_{j}+1}+\sum_{i=0}^{D_{j}}\alpha_{j,i}t^{i}=0,\alpha_{j,i}\in\mathbb{R},$

is the monic polynomial of minimum degree $D_{j}+1$ that satisfies
$e^{\top}_{j}Q_{j}(P)=0$.

In what follows, we will show how to use the coefficients of the minimal
polynomial to obtain the final value in finite time. By using the iteration in
(2), we have

$\sum_{i=0}^{D_{j}+1}\alpha_{j,i}x_{j,1}^{\alpha}(k+i)=0,\forall
k\in\mathbb{Z}_{++},$

where $\alpha_{j,D_{j}+1}=1$. Thus, the minimal polynomial of a matrix is
unique due to the monic property. We denote the $\mathcal{Z}$-transform of
$x_{j,1}(k)$ as $X_{j,1}=\mathcal{Z}(x_{j,1}(k))$. By the time-shift property
of the $\mathcal{Z}$-transform, it is easy to obtain that

$X_{j,1}(z)=\frac{{\sum_{i=1}^{D_{j}+1}\alpha_{j,i}\color[rgb]{0,0,0}\sum_{l=1}^{i}}x_{j,1}^{\alpha}(l)z^{i-l}}{Q_{j}(z)}.$

Since the communication topology of the networked system is strongly
connected, the minimal polynomial $Q_{j}(z)$ does not have any unstable poles
apart from one. Hence, we can define polynomial

$p_{j}(z)\triangleq\frac{Q_{j}(z)}{z-1}\triangleq\sum\limits_{i=0}^{D_{j}}\beta_{i}^{(j)}z^{i}.$

By the final value theorem [25] and [26], the final state values of (2) are
computed as

$\displaystyle\phi^{\alpha}_{x_{l}}(j)=\lim\limits_{k\rightarrow\infty}x_{j,l}^{\alpha}(k)=\lim\limits_{z\rightarrow
1}(z-1)X_{j,l}^{\alpha}(z)=\frac{(x_{l,{D_{j}}}^{\alpha})^{\top}\bm{\beta}_{j}}{\bm{1}^{\top}\bm{\beta}_{j}},$

where

$(x_{l,{D_{j}}}^{\alpha})^{\top}=(x_{j,l}^{\alpha}(1),x_{j,l}^{\alpha}(1),\ldots,x_{j,l}^{\alpha}(D_{j}+1)),l=1,2,$

and $\bm{\beta}_{j}$ is the coefficient vector of the polynomial $p_{j}(z)$.

Denote the following vectors of $2k+1$ successive discrete-time values for the
two iterations $x_{j,l}^{\alpha}(k),l=1,2$ at node $j$ as

$(x_{l,{2k}}^{\alpha})^{\top}=(x_{j,l}^{\alpha}(1),x_{j,l}^{\alpha}(1),\ldots,x_{j,l}^{\alpha}(2k+1)),l=1,2.$

Moreover, define the associated Hankel matrix and the difference vectors
between successive values for $l=1,2$ as

$\displaystyle\Gamma\\{(x_{l,{2k}}^{\alpha})^{\top}\\}$
$\displaystyle\triangleq$
$\displaystyle\begin{bmatrix}x_{j,l}^{\alpha}(1)&x_{j,l}^{\alpha}(2)&\cdots&x_{j,l}^{\alpha}(k+1)\\\
x_{j,l}^{\alpha}(2)&x_{j,l}^{\alpha}(3)&\cdots&x_{j,l}^{\alpha}(k+2)\\\
\vdots&\vdots&\ddots&\vdots\\\
x_{j,l}^{\alpha}(k+1)&x_{j,l}^{\alpha}(k+2)&\cdots&x_{j,lt}^{\alpha}(2k+1)\\\
\end{bmatrix},$ $\displaystyle(\bar{x}_{l,{2k}}^{\alpha})^{\top}$
$\displaystyle\triangleq$
$\displaystyle(x_{j,l}^{\alpha}(2)-x_{j,l}^{\alpha}(1),\ldots,x_{j,l}^{\alpha}(2k+2)-x_{j,l}^{\alpha}(2k+1)).$

It is shown in [26] that for arbitrary initial conditions
$x_{j,1}^{\alpha}(1)$ and $x_{j,2}^{\alpha}(1)$, $\bm{\beta_{j}}$ can be
computed as the kernel of the first defective Hankel matrices
$\Gamma\\{(\bar{x}_{1,{2k}}^{\alpha})^{\top}\\}$ and
$\Gamma\\{(\bar{x}_{2,{2k}}^{\alpha})^{\top}\\}$, except a set of initial
conditions with Lebesgue measure zero.

From the above analysis, we know $\bm{\beta_{j}}$ and $D_{j}$ can be different
for node $j$. Thus, in existing works [22],[25], all nodes are assumed to know
the upper bound of the network size. To relax this assumption, Charalambous
and Hadjicostis [27] proposed a distributed termination mechanism, allowing
all nodes to agree when to terminate their iterations, given they have all
computed the average. The procedure is as follows:

  * •

Once iterations (2) are initiated, each node $j$ also initiates two counters
$c_{j}$, $c_{j}(0)=0$, and $r_{j}$, $r_{j}(0)=0$. Counter $c_{j}$ increments
by one at every time step, i.e., $c_{j}(k+1)=c_{j}(k)+1$. The way counter
$r_{j}$ updates is described next.

  * •

Alongside iterations (2) a $\max$-consensus algorithm is initiated as well,
given by

$\displaystyle\theta_{j}(k+1)=\max_{v_{i}\in\mathcal{N}_{j}\cup\\{v_{j}\\}}\big{\\{}\max\\{\theta_{i}(k),c_{i}(k)\\}\big{\\}},$
(3)

with $\theta_{j}(0)=0$. Then, $r_{j}$ is updated as follows:

$\displaystyle r_{j}(k+1)=\begin{cases}0,&\text{if
}\theta_{j}(k+1)\neq\theta_{j}(k),\\\
r_{j}(k)+1,&\text{otherwise}.\end{cases}$ (4)

  * •

Once the Hankel matrices $\Gamma\\{(\bar{x}_{1,{D_{j}}}^{\alpha})^{\top}\\}$
and $\Gamma\\{(\bar{x}_{2,{D_{j}}}^{\alpha})^{\top}\\}$ lose rank, node $j$
saves the count of the counter $c_{j}$ at that time step, denoted by
$k^{o}_{j}$, as $c^{o}_{j}$, i.e., $c^{o}_{j}\triangleq c_{j}[k^{o}_{j}]$, and
it stops incrementing the counter, i.e., $\forall k^{\prime}\geq
k^{o}_{j},c[k^{\prime}]=c_{j}[k^{o}_{j}]=c^{o}_{j}$. Note that
$c^{o}_{j}=2(D_{j}+1)+1$.

  * •

Node $j$ can terminate iterations (2) when $r_{j}$ reaches $c^{o}_{j}$.

Therefore, based on the distributed termination mechanism [27, 28], we design
a privacy-preserving finite-time push-sum algorithm (PrFTPS) as presented in
Algorithm III-A1, which guarantees the minimum number of iteration steps to
obtain the exact average without any global information.

Algorithm 1 A Privacy-Preserving Finte-Time Push-Sum Algorithm (PrFTPS)

1:Input: Initial state $x_{j}(0)$, step $t$, graph
$\mathcal{G}(\mathcal{V},\mathcal{E})$.

2:if $t=0$ then

3:Run the privacy-preserving iteration (2) and the max-consensus algorithm
(3), store the vectors $(\bar{x}_{1,{D_{j}}}^{\alpha})^{\top}$,
$(\bar{x}_{2,{D_{j}}}^{\alpha})^{\top}$, increment the value of the counter
$c_{j}(k)$ and find the value of the counter $r_{j}(k)$ via (4).

4:Increase the dimension $k$ of the Hankel matrices
$\Gamma\\{(\bar{x}_{1,{D_{j}}}^{\alpha})^{\top}\\}$ and
$\Gamma\\{(\bar{x}_{2,{D_{j}}}^{\alpha})^{\top}\\}$ until $k_{j}^{o}$ at which
they lose rank. Once this happens, store the kernel $\bm{\beta}_{j}$ of the
first defective matrix and the value $c^{o}_{j}=2(D_{j}+1)+1$.

5:Continue iteration (2) until iteration $k_{j,t}$ where
$r_{j}(k_{j,t})=c^{o}_{j}$ and store
$D_{\text{max}}=\frac{k_{j,t}-2D_{j}-2}{2}-1.$

6:else

7:Run the privacy-preserving algoirthm (2) for $k_{\max}=D_{\max}+2$ steps
with the same $\bm{\beta_{j}}$.

8:end if

9:Compute the average value as
$\hat{x}_{j}^{ave}=\frac{(x_{1,{D_{j}}}^{\alpha})^{\top}\bm{\beta}_{j}}{(x_{2,{D_{j}}}^{\alpha})^{\top}\bm{\beta}_{j}}$.

10:Output: Node $j\in\mathcal{V}$ outputs $\hat{x}_{j}^{ave}$.

###### Remark 2

Compared to existing state-decomposition-based privacy-preserving average
consensus in [15] and [18], PrFTPS is applicable to general digraphs, while
the method in [15] is limited to undirected graphs with doubly-stochastic
methods. Moreover, our innovative weight mechanism (Section III-A1) maintains
constant weights in the privacy-preserving iteration (2) for $k\geq 1$, as
opposed to the time-varying weights in [15] and [18]. These constant weights
play a crucial role in the final value theorem [26], allowing PrFTPS to
compute an exact average consensus in finite time using the coefficients of
the minimal polynomial associated with iteration (2). In contrast, the weight
mechanisms in [15] and [18] only permit asymptotic average consensus, which
limits their application to solving distributed optimization problems. Our
proposed weight mechanism overcomes this limitation and facilitates the
application of our PrFTPS algorithm to solve distributed optimization problems
while preserving privacy, as shown in Algorithm III-B.

###  III-B Finite-Time Privacy-Preserving Push-Sum based Gradient Descent
Algorithm

In this subsection, we design a PrFTPS based gradient method to address
problem (1). We first assume the following conditions about Problem (1).

###### Assumption 2

Each objective function $f_{i}$ is $\mu-$strongly convex with $L-$Lipschitz
continuous gradients, i.e.,

$\displaystyle\langle\nabla f_{i}(\mathbf{x})-\nabla
f_{i}(\mathbf{y}),\mathbf{x}-\mathbf{y}\rangle\geq\mu||\mathbf{x}-\mathbf{y}||^{2},$
$\displaystyle||\nabla f_{i}(\mathbf{x})-\nabla f_{i}(\mathbf{y})||\leq
L||\mathbf{x}-\mathbf{y}||,\quad\forall\mathbf{x},\mathbf{y}\in\mathbb{R}^{p}.$

Under Assumption 2, Problem (1) has a unique optimal solution
$x^{\star}\in\mathbb{R}^{p}$ [8].

To address problem (1) distributively, we propose the following PrFTPS based
GD algorithm inspired by the distributed structure in [7, 8, 22]. Starting
from the initial condition $x_{i}(0)\in\mathbb{R}^{p}$ and $y_{i}(0)=\nabla
f_{i}(x_{i}(0))$, for all $t\geq 0$, we have

$\displaystyle y_{i}(t)\leftarrow\text{Algorithm \ref{alg1}}(\nabla
f_{i}(x_{i}(t)),t),$ (5a) $\displaystyle x_{i}(t+1)=\sum\limits_{j\in
N_{i}^{-}\cup\\{i\\}}\bar{a}_{ij}x_{j}(t)-\eta y_{i}(t),$ (5b)

where $\eta$ is the stepsize and
$\mathbf{\bar{A}}=[\bar{a}_{ji}]\in\mathbb{R}^{n}$ is row-stochastic. The
details are summarized in Algorithm III-B in the following.

Algorithm 2 A Privacy-Preserving Finte-Time Push-Sum based GD Algorithm
(PrFTPS-GD)

1:Initialization:  Stepsize $\eta$, maximum optimization iteration number $T$,
graph $\mathcal{G}(\mathcal{V},\mathcal{E})$.

2:Input: Node $i\in\mathcal{V}$ sets the initial value
$x_{i}(0),y_{i}(0)=\nabla f_{i}(x_{i}(0))$ and $t=0$.

3:for $t\leq T$ do

4: Put $\nabla f_{i}(x_{i}(t)),t$ as input to Algorithm III-A1 and get output
$\hat{x}^{ave}$; design $y_{i}(t)=\hat{x}^{ave}$.

5: Compute $x_{i}(t+1)$ using (5b) with $y_{i}(t)$.

6: $t\leftarrow t+1$

7:end for

8:Output: Node $i\in\mathcal{V}$ obtains the solution $x^{\star}$.

Algorithm III-B guarantees that the number of iterations needed at every
optimization step $t\geq 1$ is the minimum. Fig. 1 shows the number of
iterations needed at every optimization step.

Figure 1: The finite-time consensus algorithm is terminated after
$k_{1}=4(D_{\text{max}}+1)$ iterations in the first step of the optimization.
After the first step, the consensus is terminated after
$k_{\text{max}}=D_{\text{max}}+1$ iterations.

###### Remark 3

Compared to conventional distributed optimization algorithms, such as AB [7]
and Push-Pull [8], PrFTPS-GD requires additional communication rounds for each
optimization step, as illustrated in Fig. 1. Although the separate time-scales
for optimization and consensus steps may slow down the convergence speed, they
are crucial for ensuring privacy preservation and accuracy of PrFTPS-GD, as
demonstrated by the rigorous theoretical analysis presented in Sections III-C
and III-D.

###  III-C Convergence Analysis

In this subsection, we provide the proof of the convergence and accuracy of
Algorithm 1 and Algorithm 2.

From the weight mechanism, it can be seen that for $k\geq 1$, the coupling
weights are constants. Hence, iteration (2) can be written by using matrix-
vector notation as follows:

$\bm{x_{l}}(k+1)=\bm{\hat{P}}\bm{x_{l}}(k),\quad\forall k\geq 1,l=1,2,$ (6)

where

$\bm{x_{l}}(k)=[x_{1,l}^{\alpha}(k),\ldots,x_{n,l}^{\alpha}(k),x_{1,l}^{\beta}(k),\ldots,x_{n,l}^{\beta}(k)]^{\top},$
$\bm{\hat{P}}=\left[\begin{array}[]{cc}\bm{P}&\frac{1}{2}\bm{I}_{n}\\\
\bm{\Lambda}&\frac{1}{2}\bm{I}_{n}\end{array}\right]$

with
$\bm{\Lambda}=\text{diag}(a_{1}^{\beta,\alpha},\ldots,a_{n}^{\beta,\alpha})$
and $\bm{P}=[p_{ij}]$.

Moreover, equation (5b) can be rewritten as

$\bm{x}(t+1)=\mathbf{A}\bm{x}(t)-\eta\bm{y}(t),$ (7)

where
$\mathbf{A}=\mathbf{\bar{A}}\otimes\mathbf{I}_{p},\bm{x}(t)=[x_{1}(t)^{\top},\ldots,x_{n}(t)^{\top}]^{\top}$
and $\bm{y}(t)=[y_{1}(t)^{\top},\ldots,y_{n}(t)^{\top}]^{\top}.$

Before presenting Theorem 1, the following lemmas are needed.

###### Lemma 1

(Theorem 8.4.4 in [29]) Under Assumption 1, the matrix $A$ has a unique
nonnegative left eigenvector $u^{\top}$ (with respect to eigenvalue $1$) with
$u^{\top}\mathbf{1}_{np}=np.$

###### Lemma 2

(Adapted from Lemma 4 in [8]) Under Assumptions 1, there exists a matrix norm
$||\cdot||_{A}$, defined as $||M||_{A}=AMA^{-1}$ for all
$M\in\mathbb{R}^{np\times np}$, where $A\in\mathbb{R}^{{np}\times{np}}$ is
invertible, such that
$\sigma_{A}:=||\mathbf{A}-\frac{\mathbf{1}_{np}u^{\top}}{n}||_{A}<1$, where
$\mathbf{A}$ is the update matrix defined in (7), and $\sigma_{A}$ is
arbitrarily close to the spectral radius
$\rho(\mathbf{A}-\frac{\mathbf{1}_{np}u^{\top}}{n})<1$.

Now, we present Theorem 1 in the following.

###### Theorem 1

Under Assumptions 1 and 2, for each node $j\in\mathcal{V}$,

1) Algorithm III-A1 outputs the exact average of initial values of all nodes,
i.e., $\forall
j\in\mathcal{V},\hat{x}_{j}^{ave}=\frac{1}{n}\sum_{i\in\mathcal{V}}x_{i}(0).$

2) When $0<\eta<\frac{1}{\mu+L}$, where $\mu,L$ are defined in Assumption 2,
Algorithm III-B converges linearly related to the optimization iteration
number to the global optimal, i.e., $||\bm{x}(t)-\bm{1}\otimes
x^{\star}||_{2}$ converges to $0$ linearly.

###### Proof:

See Appendix -A. ∎

###  III-D Privacy-preserving Performance Analysis

In this subsection, we analyze the privacy-preserving performance of Algorithm
III-B against honest-but-curious nodes and eavesdroppers. First, the following
assumption is needed.

###### Assumption 3

Considering a digraph $\mathcal{G}(\mathcal{V},\mathcal{E})$, each agent
$i,\forall i\in\mathcal{V}$, does not know the structure of the whole network,
i.e., the Laplacian of the network.

This assumption shows that agent $i$ has no access to the whole consensus
dynamics in (2), which is very natural in distributed systems since agent $i$
is only aware of its outgoing link weights $p_{ji}(k),j\in
N_{i}^{-}\cup\\{i\\}$. Without other agents’ weights, matrix $\bm{\hat{P}}$ in
$\eqref{e2}$ is inaccessible to agent $i$.

Note that only local gradient information is exchanged in Algorithm III-A1,
and the outputs of Algorithm III-A1 are the same for each agent. Hence, if
Algorithm III-A1 is able to preserve privacy of each agent in the network, we
can deduce that Algorithm III-B can preserve privacy of each agent.

Next, we show the privacy preservation of Algorithm III-A1.

Under Algorithm III-A1, the information set accessible to the set of honest-
but-curious nodes $\mathcal{N}$ at time $k$ can be defined as

$\displaystyle\mathcal{I}_{\mathcal{N}}(k)=\\{$ $\displaystyle
x_{a,l}^{\alpha}(k),x_{a,l}^{\beta}(k),p_{ja}(k),p_{ap}(k),x_{p,l}^{\alpha}(k),$
$\displaystyle\mid p\in N_{a}^{-},a\in\mathcal{N},j\in\mathcal{V},l=1,2\\}.$

Similar, an eavesdropper $\mathcal{R}$ is assumed to eavesdrop some edges
$\varepsilon_{ij}\in\mathcal{E}_{\mathcal{R}}$ and its information set is
denoted by

$\mathcal{I}_{\mathcal{R}}(k)\triangleq\\{x_{j,l}^{\alpha}(k),p_{ij}(k)\mid\forall\varepsilon_{ij}\in\mathcal{E}_{\mathcal{R}},j\in\mathcal{V},l=1,2\\}.$

###### Theorem 2

Under Assumptions 1 and 3, for each node $j\in\mathcal{V}$, under Algorithm
III-A1, the privacy of agent $j$ can be preserved:

1) Against a set of honest-but-curious nodes $\mathcal{N}$ if at least one
neighbor of node $j$ does not belongs to $\mathcal{N}$, i.e., $N_{j}^{+}\cup
N_{j}^{-}\nsubseteq\mathcal{N}$.

2) Against eavesdropper $\mathcal{R}$ if there exists one edge
$\varepsilon_{mj}$ or $\varepsilon_{jm}$ that eavesdropper $\mathcal{R}$
cannot eavesdrop, where $m\in N_{j}^{+}$ or $m\in N_{j}^{-}$.

###### Proof:

See Appendix -B. ∎

##  IV SIMULATIONS

Consider a strongly connected digraph containing $n=5$ agents. The following
distributed least squares problem is considered:

$\min\limits_{x\in\mathbb{R}^{p}}F(x)=\frac{1}{{\color[rgb]{0,0,0}n}}\sum\limits_{i=1}^{n}f_{i}(x)=\frac{1}{5}\sum\limits_{i=1}^{5}||A_{i}x-b_{i}||^{2},$
(8)

where $A_{i}\in\mathbb{R}^{q\times p}$ is only known to node $i$,
$b_{i}\in\mathbb{R}^{q}$ is the measured data and $x\in\mathbb{R}^{p}$ is the
common decision variable. In this simulation, we set $q=p=3$ and $\eta=0.1$.
All elements of $A_{i}$ and $b_{i}$ are set from independent and identically
distributed samples of standard normal distribution $\mathcal{N}(0,1)$. The
finite-time consensus (Algorithm 1) stage consists of $k_{1}=64$ $(t=0)$ and
$k_{\text{max}}=17$ $(t\geq 1)$ communication steps inside each PrFTPS-GD
optimization iteration, i.e., the optimization variable ${\bm{x}(0)}$ takes
$64$ steps to become $\bm{x}(1)$ and then variable ${\bm{x}(t)}$ is updated
every $17$ iterations for $t\geq 1$.

Figure 2: Performance comparison among our proposed PrFTPS-GD, DPGT [20] and
SD-Push-Pull [21].

The normalized residual
$\sum_{i}^{5}(||x_{i}(t)-x^{\star}||/||x_{i}(0)-x^{\star}||)$ is illustrated
in Fig. 2 to compare PrFTPS-GD with DPGT[20] and SD-Push-Pull [21]. Notice
that as we have multiple consensus steps in Algorithm III-A1 inside our
PrFTPS-GD while there is only one step in DPGT and SD-Push-Pull, we have
scaled each PrFTPS-GD optimization iteration number to include the consensus
number (i.e., $k_{1}$ and $k_{\text{max}}$) directly. It is shown that the
proposed PrFTPS-GD converges linearly related to optimization iteration
number. The stepsizes of all algorithms are manually tuned to obtain the
corresponding best convergence performance. For SD-Push-Pull, the stepsize is
set to be $\eta=0.1$ and it can be seen that SD-Push-Pull only converge to
suboptimality while PrFTPS-GD can converge to the optimal point. In terms of
DPGT, we choose the stepsize with the diminishing sequence as

$\lambda^{k}=\frac{0.02}{1+0.1k},\quad\gamma_{1}^{k}=\frac{1}{1+0.1k^{0.9}},\quad\gamma_{2}^{k}=\frac{1}{1+0.1k^{0.8}}.$

Fig. 2 demonstrates clearly that PrFTPS-GD converges faster to the optimal
solution than DPGT.

##  V CONCLUSION AND FUTURE WORK

In this paper, a privacy-preserving finite-time push-sum based gradient
descent algorithm is proposed to solve the distributed optimization problem
over a directed graph. Compared to existing privacy-preserving algorithms in
the literature, the proposed one can converge linearly to the global optimum.
Moreover, privacy of each agent is preserved via a state decomposition
mechanism.

Future work includes considering constrained optimization problems in large-
scale. Moreover, privacy-preserving distributed optimiation algorithm with
quantization communication is a potential research direction.

###  -A Proof of Theorem 1

1) By the weight mechanism and the iteration in (2) at iteration $k=0$, we
have
$\bm{1}^{\top}\bm{x_{1}}(1)=\bm{1}^{\top}\bm{x_{1}}(0)=2\sum_{i=1}^{n}x_{i}(0)$
and $\bm{1}^{\top}\bm{x_{2}}(1)=\bm{1}^{\top}\bm{x_{2}}(0)=2n.$

Since $\bm{\hat{P}}$ is irreducible, column-stochastic with positive
diagonals, from Perron-Frobenius theorem, we have $\rho(\bm{\hat{P}})=1$.
Denote $\bm{v}=[v_{i}]$ as the right eigenvector corresponding to the
eigenvalue of $1$, we have
$\lim_{k\rightarrow\infty}\bm{\hat{P}}^{k}=\bm{v1}^{\top}$. Then,

$\displaystyle\frac{x^{\alpha}_{j,1}(\infty)}{x^{\alpha}_{j,2}(\infty)}$
$\displaystyle=\frac{[\bm{\hat{P}}^{\infty}\bm{x_{1}}({1})]_{j}}{[\bm{\hat{P}}^{\infty}\bm{x_{2}}({1})]_{j}}=\frac{[\bm{v1}^{\top}\bm{x_{1}}({1})]_{j}}{[\bm{v1}^{\top}\bm{x_{2}}({1})]_{j}}=\frac{\sum_{i=1}^{n}x_{i}(0)}{n}.$

Since the coefficient $\bm{\beta}_{j}$ is independent of the initial node
state,

$\hat{x}_{j}^{ave}=\frac{(x_{1,{D_{j}}}^{\alpha})^{\top}\bm{\beta}_{j}}{(x_{2,{D_{j}}}^{\alpha})^{\top}\bm{\beta}_{j}}=\frac{x^{\alpha}_{j,1}(\infty)}{x^{\alpha}_{j,2}(\infty)}=\frac{\sum_{i=1}^{n}x_{i}(0)}{n}.$
(9)

2) Denote
$\bar{x}(t)=u^{\top}\bm{x}(t)/n,\bar{y}(t)=\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(x_{i}(t))$ and $g(t)=\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(\bar{x}(t))$.
From the above analysis, we know that at time iteration $t$, each agent can
obtain the average gradient at time $t$ via Algorithm III-A1, i.e,
$y_{i}(t)=\bar{y}(t),\bm{y}(t)=\bm{1}\bar{y}(t)$. Hence, from iteration (7),
we have

$\displaystyle\bar{x}(t+1)-x^{\star}$
$\displaystyle=\bar{x}(t)-\eta\bar{y}(t)-x^{\star}$
$\displaystyle=\bar{x}(t)-\eta g(t)-x^{\star}-\eta(\bar{y}(t)-g(t)),$
$\displaystyle\bm{x}(t+1)-\bm{1}\bar{x}(t+1)$
$\displaystyle=\mathbf{A}\bm{x}(t)-\eta\bm{y}(t)-\bm{1}\bar{x}(t)+\eta\bm{1}\bar{y}(t)$
$\displaystyle=(\mathbf{A}-\mathbf{1}_{n}u^{\top}/n)(\bm{x}(t)-\bm{1}\bar{x}(t)).$

Based on [30, Lemma 8(c) and 10], if $\eta<1/(\mu+L)$, we have

$\displaystyle||\bar{x}(t+1)-x^{\star}||_{2}\leq(1-\eta\mu)||\bar{x}(t)-x^{\star}||_{2}+\eta||\bar{y}(t)-g(t)||$
(10) $\displaystyle\leq(1-\eta\mu)||\bar{x}(t)-x^{\star}||_{2}+\frac{\eta
L}{\sqrt{n}}||\bm{x}(t)-\bm{1}\bar{x}(t)||_{2}.$

Moreover, from the result of Lemma 2, we can obtain that

$||\bar{x}(t+1)-x^{\star}||_{2}\leq(1-\eta\mu)||\bar{x}(t)-x^{\star}||_{2}+\frac{\eta
qL}{\sqrt{n}}||\bm{x}(t)-\bm{1}\bar{x}(t)||_{A}.$

Denote
$V(t)=[||\bar{x}(t+1)-x^{\star}||_{2},||\bm{x}(t)-\bm{1}\bar{x}(t)||_{A}]^{\top}$,
we have

$V(t+1)\leq\bm{M}V(t),$ (11)

where the transition matrix
$\bm{M}=\begin{bmatrix}1-\eta\mu&{\color[rgb]{0,0,0}\eta}qL/\sqrt{n}\\\
0&\sigma_{A}\\\ \end{bmatrix}$.

Since $0<1-\eta\mu<1$ and $0<\sigma_{A}<1$, we can obtain that the spectral
radius of $\bm{M}$ is strictly less than $1$ and therefore
$||\bm{x}(t)-\bm{1}\otimes x^{\star}||_{2}$ converges to zero linearly.

###  -B Proof of Theorem 2

Since under Algorithm III-A1, the maximum communication round equals to
$k_{1}$, the information set $\mathcal{I}_{\mathcal{N}}(0:k_{1})$ and
$\mathcal{I}_{\mathcal{R}}(0:k_{1})$ denote all the information accessible to
the adversary. From Algorithm III-B, it can be seen that the private
information $\nabla f_{j}(x_{j}(t)),\forall t\geq 0$ is regarded as the input
of Algorithm III-A1. Hence, it suffices to prove that the privacy of initial
value of agent $j$, $x_{j}(0)$ is preserved under Algorithm III-A1.

1) Denote $\mathcal{L}=\mathcal{V}\backslash\mathcal{A}$ as the set of
legitimate nodes. Since $N_{j}^{+}\cup N_{j}^{-}\nsubseteq\mathcal{A}$, there
exists at least one node $m$ that belongs to $N_{j}^{+}\cup N_{j}^{-}$ but not
$\mathcal{A}$. Fix any feasible information set
$\mathcal{I}_{\mathcal{N}}(0:k_{1})$. We denote
$\\{x_{n,1}^{\alpha}(0)^{\prime},x_{n,1}^{\beta}(0)^{\prime},p_{in}(0)^{\prime}\mid
n\in\mathcal{L},i\in\mathcal{V}\\}$ as an arbitrary set of initial substate
values and weights that satisfies $\mathcal{I}_{\mathcal{N}}(0:k_{1})$. Hence,
we have
$x_{j}(0)^{\prime}=(x_{j,1}^{\alpha}(0)^{\prime}+x_{j,1}^{\beta}(0)^{\prime})/2.$
We then denote $x_{j}(0)^{\prime\prime}$ as
$x_{j}(0)^{\prime\prime}=x_{i}(0)^{\prime}+e$, where $e$ is an arbitrary real
number. Next we show that there exists a set of values
$\\{x_{n,1}^{\alpha}(0)^{\prime\prime},x_{n,1}^{\beta}(0)^{\prime\prime},p_{in}(0)^{\prime\prime},n\in\mathcal{L},i\in\mathcal{V}\\}$
which makes
$x_{j}(0)^{\prime\prime}\in\Delta_{j}(\mathcal{I}_{\mathcal{N}}(0:k_{1})).$
The initial substate values
$x_{n,1}^{\alpha}(0)^{\prime\prime},x_{n,1}^{\beta}(0)^{\prime\prime}$ are
denoted as follows.

$\displaystyle
x_{q,1}^{\alpha}(0)^{\prime\prime}=x_{q,1}^{\alpha}(0)^{\prime},x_{q,1}^{\beta}(0)^{\prime\prime}=x_{q,1}^{\beta}(0)^{\prime},\forall
q\in\mathcal{L}\backslash{\color[rgb]{0,0,0}\\{j,m\\}},$ (12) $\displaystyle
x_{m,1}^{\alpha}(0)^{\prime\prime}=x_{m,1}^{\alpha}(0)^{\prime},x_{m,1}^{\beta}(0)^{\prime\prime}=x_{m,1}^{\beta}(0)^{\prime}-2e,$
$\displaystyle
x_{j,1}^{\alpha}(0)^{\prime\prime}=x_{j,1}^{\alpha}(0)^{\prime},x_{j,1}^{\beta}(0)^{\prime\prime}=x_{j,1}^{\beta}(0)^{\prime}+2e.$

Then we consider the following two situations.

Situation I: Consider $m\in N^{-}_{j}$, then the information set sequence
accessible to set $\mathcal{N}$ equals to $\mathcal{I}_{\mathcal{N}}(0:k_{1})$
under the initial substate values in (12) and the following weights:

$\displaystyle
a_{n}^{(\beta,\alpha)}(0)^{\prime\prime}=a_{n}^{(\beta,\alpha)}(0)^{\prime},\forall
n\in\mathcal{L},$ (13) $\displaystyle
p_{mm}(0)^{\prime\prime}=(p_{mm}(0)^{\prime}x_{m,1}^{\alpha}(0)^{\prime}+2e)/x_{m,1}^{\alpha}(0)^{\prime},$
$\displaystyle
p_{jm}(0)^{\prime\prime}=(p_{jm}(0)^{\prime}x_{m,1}^{\alpha}(0)^{\prime}-2e)/x_{m,1}^{\alpha}(0)^{\prime},$
$\displaystyle p_{qm}(0)^{\prime\prime}=p_{qm}(0)^{\prime},\forall
q\in\mathcal{L}\backslash{\color[rgb]{0,0,0}\\{j,m\\}},$ $\displaystyle
p_{np}(0)^{\prime\prime}=p_{np}(0)^{\prime},\forall n\in\mathcal{L},\forall
p\in\mathcal{L}\backslash\\{m\\}.$

Situation II: Consider $m\in N^{+}_{j}$, then the information set sequence
accessible to set $\mathcal{N}$ equals to $\mathcal{I}_{\mathcal{N}}(0:k_{1})$
under the initial substate values in (12) and the following weights:

$\displaystyle
a_{n}^{(\beta,\alpha)}(0)^{\prime\prime}=a_{n}^{(\beta,\alpha)}(0)^{\prime},\forall
n\in\mathcal{L},$ (14) $\displaystyle
p_{jj}(0)^{\prime\prime}=(p_{jj}(0)^{\prime}x_{j,1}^{\alpha}(0)^{\prime}-2e)/x_{j,1}^{\alpha}(0)^{\prime},$
$\displaystyle
p_{mj}(0)^{\prime\prime}=(p_{mj}(0)^{\prime}x_{j,1}^{\alpha}(0)^{\prime}+2e)/x_{j,1}^{\alpha}(0)^{\prime},$
$\displaystyle p_{qj}(0)^{\prime\prime}=p_{qj}(0)^{\prime},\forall
q\in\mathcal{L}\backslash{\color[rgb]{0,0,0}\\{j,m\\}},$ $\displaystyle
p_{np}(0)^{\prime\prime}=p_{np}(0)^{\prime},\forall n\in\mathcal{L},\forall
p\in\mathcal{L}\backslash\\{j\\}.$

Summarizing Situations I and II, we have that
$x_{j}(0)^{\prime\prime}=x_{j}(0)^{\prime}+e\in\Delta_{j}(\mathcal{I}_{\mathcal{N}}(0:k_{1}))$,
then

$\text{Diam}(\Delta_{j}(\mathcal{I}_{\mathcal{N}}(0:k_{1})))\geq\sup\limits_{e\in\mathbb{R}}|x_{j}(0)^{\prime}-(x_{j}(0)^{\prime}+e)|=\infty.$

From Definition 1, the first statement is proved.

2) For the second statement, due to the topology constraints, the eavesdropper
$\mathcal{R}$ can not eavesdrop on $\varepsilon_{mj}$ or $\varepsilon_{jm}$,
where $m\in N_{j}^{+}$ or $m\in N_{j}^{-}$, i.e., $p_{mj}(0)$ or $p_{jm}(0)$
is inaccessible to $\mathcal{R}$. Moreover, since the self-weights
$p_{jj}(0),p_{mm}(0)$ are not transmitted over the communication network, the
eavesdropper $\mathcal{R}$ can not obtain any information of
$p_{jm}(0),p_{mm}(0)$ or $p_{mj}(0),p_{jj}(0))$. Then, similar to the proof in
the first statement, we have
$\text{Diam}(\Delta_{j}(\mathcal{I}_{\mathcal{R}}(0:k_{1})))=\infty$, i.e.,
the privacy of $x_{j}(0)$ is preserved.

## References

  * [1] P. Braun, L. Grüne, C. M. Kellett, S. R. Weller, and K. Worthmann, “A distributed optimization algorithm for the predictive control of smart grids,” IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 3898–3911, 2016\.
  * [2] S. Dougherty and M. Guay, “An extremum-seeking controller for distributed optimization over sensor networks,” IEEE Transactions on Automatic Control, vol. 62, no. 2, pp. 928–933, 2016.
  * [3] R. Mohebifard and A. Hajbabaie, “Distributed optimization and coordination algorithms for dynamic traffic metering in urban street networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 5, pp. 1930–1941, 2018.
  * [4] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009\.
  * [5] J. Xu, S. Zhu, Y. C. Soh, and L. Xie, “Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes,” in Proceedings of the 54th IEEE Conference on Decision and Control (CDC), 2015, pp. 2055–2060.
  * [6] S. S. Kia, B. Van Scoy, J. Cortes, R. A. Freeman, K. M. Lynch, and S. Martinez, “Tutorial on dynamic average consensus: The problem, its applications, and the algorithms,” IEEE Control System Magazine, vol. 39, no. 3, pp. 40–72, 2019.
  * [7] R. Xin and U. A. Khan, “A linear algorithm for optimization over directed graphs with geometric convergence,” IEEE Control System Letters, vol. 2, no. 3, pp. 315–320, 2018.
  * [8] S. Pu, W. Shi, J. Xu, and A. Nedić, “Push–pull gradient methods for distributed optimization in networks,” IEEE Transactions on Automatic Control, vol. 66, no. 1, pp. 1–16, 2020.
  * [9] T. Yang, X. Yi, J. Xu, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, W. Hong, Z. Lin and K. Johansson, “A survey of distributed optimization,” Annual Reviews in Control, vol. 47, pp. 278–305, 2019.
  * [10] A. Mandal, “Privacy preserving consensus-based economic dispatch in smart grid systems,” in Future Network Systems and Security: Second International Conference (FNSS), 2016, pp. 98–110.
  * [11] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of Cryptography: Third Theory of Cryptography Conference, pp. 265–284, 2006.
  * [12] E. Nozari, P. Tallapragada, and J. Cortés, “Differentially private average consensus: Obstructions, trade-offs, and optimal algorithm design,” Automatica, vol. 81, pp. 221–231, 2017.
  * [13] Z. Huang, S. Mitra, and N. Vaidya, “Differentially private distributed optimization,” in Proceedings of the 16th International Conference on Distributed Computing and Networking, 2015, pp. 1–10.
  * [14] Y. Lu and M. Zhu, “Privacy preserving distributed optimization using homomorphic encryption,” Automatica, vol. 96, pp. 314–325, 2018.
  * [15] Y. Wang, “Privacy-preserving average consensus via state decomposition,” IEEE Transactions on Automatic Control, vol. 64, no. 11, pp. 4711–4716, 2019\.
  * [16] T. Charalambous, N. E. Manitara, and C. N. Hadjicostis, “Privacy-preserving average consensus over digraphs in the presence of time delays,” in Proceedings of the 57th IEEE Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2019, pp. 238–245.
  * [17] H. Gao, C. Zhang, M. Ahmad, and Y. Wang, “Privacy-preserving average consensus on directed graphs using push-sum,” in IEEE Conference on Communications and Network Security (CNS), 2018, pp. 1-9.
  * [18] X. Chen, L. Huang, K. Ding, S. Dey, and L. Shi, “Privacy-preserving push-sum average consensus via state decomposition,” IEEE Transactions on Automatic Control, 2023, doi: 10.1109/TAC.2023.3256479.
  * [19] S. Mao, Y. Tang, Z. wei Dong, K. Meng, Z. Y. Dong, and F. Qian, “A privacy preserving distributed optimization algorithm for economic dispatch over time-varying directed networks,” _IEEE Transactions on Industrial Informatics_ , vol. 17, no. 3, pp. 1689–1701, 2021.
  * [20] Y. Wang and A. Nedić, “Tailoring gradient methods for differentially-private distributed optimization,” IEEE Transactions on Automatic Control, 2023, doi: 10.1109/TAC.2023.3272968.
  * [21] X. Chen, L. Huang, L. He, S. Dey, and L. Shi, “A differential private method for distributed optimization in directed networks via state decomposition,” IEEE Transactions on Control of Network Systems, 2023, doi: 10.1109/TCNS.2023.3264932.
  * [22] W. Jiang and T. Charalambous, “A fast finite-time consensus based gradient method for distributed optimization over digraphs,” in Proceedings of the 61st IEEE Conference on Decision and Control (CDC), 2022, pp. 6848–6854.
  * [23] D. Kempe, A. Dobra, and J. Gehrke, “Gossip-based computation of aggregate information,” in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2003 pp. 482–491.
  * [24] L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” Advances in neural information processing systems, vol. 32, 2019.
  * [25] T. Charalambous, Y. Yuan, T. Yang, W. Pan, C. N. Hadjicostis, and M. Johansson, “Distributed finite-time average consensus in digraphs in the presence of time delays,” IEEE Transactions on Control of Network Systems, vol. 2, no. 4, pp. 370–381, 2015.
  * [26] Y. Yuan, G.-B. Stan, L. Shi, and J. Gonçalves, “Decentralised final value theorem for discrete-time LTI systems with application to minimal-time distributed consensus,” in Proceedings of the 48th IEEE Conference on Decision and Control (CDC), 2009, pp. 2664–2669.
  * [27] T. Charalambous and C. N. Hadjicostis, “When to stop iterating in digraphs of unknown size? An application to finite-time average consensus,” in IEEE European Control Conference (ECC), 2018, pp. 1–7.
  * [28] W. Jiang and T. Charalambous, “Fully distributed alternating direction method of multipliers in digraphs via finite-time termination mechanisms,” arXiv:2107.02019, 2021.
  * [29] R. A. Horn and C. R. Johnson, Matrix analysis.  Cambridge University Press, 2012.
  * [30] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1245–1260, 2017.