# Dynamics based Privacy Preservation in Decentralized Optimization

Huan Gao<EMAIL_ADDRESS>Yongqiang Wang<EMAIL_ADDRESS>Angelia Nedić
<EMAIL_ADDRESS>School of Automation, Northwestern Polytechnical
University, Xi’an 710129, China  Department of Electrical and Computer
Engineering, Clemson University, Clemson, SC 29634, USA  School of Electrical,
Computer and Energy Engineering, Arizona State University, Tempe, AZ 85281,
USA

###### Abstract

With decentralized optimization having increased applications in various
domains ranging from machine learning, control, sensor networks, to robotics,
its privacy is also receiving increased attention. Existing privacy-preserving
approaches for decentralized optimization achieve privacy preservation by
patching decentralized optimization with information-technology privacy
mechanisms such as differential privacy or homomorphic encryption, which
either sacrifices optimization accuracy or incurs heavy
computation/communication overhead. We propose an inherently privacy-
preserving decentralized optimization algorithm by exploiting the robustness
of decentralized optimization to uncertainties in optimization dynamics. More
specifically, we present a general decentralized optimization framework, based
on which we show that privacy can be enabled in decentralized optimization by
adding randomness in optimization parameters. We further show that the added
randomness has no influence on the accuracy of optimization, and prove that
our inherently privacy-preserving algorithm has $R$-linear convergence when
the global objective function is smooth and strongly convex. We also
rigorously prove that the proposed algorithm can avoid the gradient of a node
from being inferable by other nodes. Numerical simulation results confirm the
theoretical predictions.

###### keywords:

Privacy preservation; decentralized optimization.

1ALG@line

††thanks: The work was supported in part by the National Science Foundation
under Grants ECCS-1912702 and CCF-2106293.

, , ††thanks: Huan Gao was with the Department of Electrical and Computer
Engineering, Clemson University, Clemson, SC 29634, USA. He is now with the
School of Automation, Northwestern Polytechnical University, Xi’an 710129,
China. The work was done when Huan Gao was with Clemson University. ††thanks:
Corresponding author.

##  1 Introduction

Decentralized optimization has received increased attention due to its vast
applications in online learning [48], distributed sensing [2], formation
control [34], source localization [51], and power system control [7]. In many
of these applications, a network of nodes collectively solve the following
problem

$\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{d}}\ \
F(\mathbf{x})\triangleq\sum_{i=1}^{n}f_{i}(\mathbf{x})$ (1)

where $f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is a local objective
function accessible only to node $i$.

Over the past decade, a number of gradient-based first order algorithms have
been developed to solve the problem. Early results include the decentralized
subgradient (DGD) algorithm [26] which combines average consensus with
(sub)gradient descent under diminishing stepsizes. Its convergence rate is
$\mathcal{O}({(\ln k)}/{\sqrt{k}})$ for general convex functions and
$\mathcal{O}((\ln k)/{k})$ for strongly convex functions, where $k$ is the
number of iterations. [49] shows that the convergence rate of DGD can be
improved under a fixed stepsize but at the expense of optimization accuracy.
To guarantee both fast convergence and exact solution under fixed stepsizes,
many algorithms propose to replace the local gradients in DGD with an
auxiliary variable which tracks the global gradient, with typical examples
include Aug-DGM [46], DIGing [33, 24], ATC-DIGing [25], AsynDGM [47],
$\mathcal{A}\mathcal{B}$ [45], and Push-Pull [32, 4, 53]. These algorithms can
achieve $R$-linear convergence.111Suppose that a sequence
$\\{\mathbf{x}^{k}\\}$ converges to $\mathbf{x}^{*}$ in some norm $||\cdot||$.
Then the convergence is $R$-linear with decay parameter $\rho\in(0,1)$ if
there exists a positive constant $c$ such that
$||\mathbf{x}^{k}-\mathbf{x}^{*}||\leq c\rho^{k}$ holds for any $k$ [24].
While most of existing algorithms assume a constant interaction graph,
convergence of such gradient-tracking based algorithms on time-varying graphs
have also been discussed in [24], [47], and [38]. Other relevant algorithms
include [41, 44, 27, 11, 5].

However, none of the aforementioned algorithms consider the privacy of
individual nodes, which is unacceptable in many applications. For example, in
the rendezvous problem where a group of nodes use decentralized optimization
to agree on the optimal assembly position, individual nodes may want to keep
their initial positions private, which is important in hostile environments.
As indicated in [15], without protection by an appropriate privacy mechanism,
a node’s initial position can be easily inferred by an adversary in gradient-
decent based rendezvous algorithms. Another example illustrating the
importance of privacy in decentralized optimization is collaborative machine
learning where gradients/model updates exchanged among participating machines
may contain sensitive information such as personal medical record and salary
[48].

To address the pressing need of privacy in decentralized optimization,
recently results have emerged on privacy-preserving decentralized
optimization. For example, differential-privacy based approaches are proposed
in [28, 15, 42]. However, such approaches will unavoidably compromise the
accuracy of optimization results. To enable privacy protection with guaranteed
optimization accuracy, partially homomorphic encryption based approaches have
been proposed in our own prior results [52, 50] as well as others’ [20].
However, such approaches will incur heavy computation and communication
overhead. [48] and [19] showed that privacy can be obtained by incorporating a
projection step or injecting constant uncertainties in stepsizes. However,
both approaches have limitations in privacy protection: projection based
defense requires individual agents to have a priori knowledge of the optimal
solution, whereas constant uncertainties in stepsizes are unable to cover
arbitrarily large variations on the gradients. Other approaches include [6,
18, 43]. However, they are only applicable to undirected graphs.

Recently, through using random coefficients and/or initial conditions, others
as well as our group have proposed several private consensus algorithms [21,
3, 30, 10, 16, 22, 9, 12, 8, 37, 36]. These algorithms can protect the initial
value of a node from being inferable by adversaries. Inspired by this line of
research, in this paper, we propose to protect the gradient of participating
nodes in decentralized optimization by leveraging the robustness of
decentralized optimization dynamics. More specifically, by judiciously
injecting uncertainties in optimization dynamics, we obfuscate exchanged
information without affecting convergence to the exact optimal solution. We
rigorously prove that the proposed algorithm can avoid the gradient of a node
from being inferable by other nodes. Since protecting the gradient means
protecting the values of the gradient function over the entire domain (or
protecting both function types and function parameters), it is much more
challenging than protecting a single initial value considered in the private
consensus problem.

The main contributions of the paper are as follows: 1) We propose a dynamics
based privacy protection approach for decentralized optimization that neither
sacrifices optimization accuracy nor incurs heavy computation/communication
overhead. This is in distinct difference from existing approaches based on
differential privacy (which compromise optimization accuracy) and approaches
based on homomorphic encryption (which incur heavy computation and
communication overhead); 2) Our approach is also different from the multi-
party secure computation approach in [13] which requires each node to
communicate with two non-colluding external servers. By introducing randomness
into interaction parameters, our approach is implementable in a fully
decentralized manner without the assistance of any external servers; 3) We
propose a new privacy definition based on the indistinguishability of
gradient’s arbitrary variations to adversaries from the viewpoint of
accessible information, which is stricter than the
unobservability/unsolvability based privacy definitions; 4) To facilitate the
dynamics based privacy design, we propose a general framework for gradient-
tracking based decentralized optimization which includes as special cases many
existing decentralized optimization algorithms, such as Aug-DGM [46], DIGing
[33, 24], ATC-DIGing [25], AsynDGM [47], $\mathcal{A}\mathcal{B}$ [45], and
Push-Pull [32, 4, 53]; 5) We analytically prove that despite the time-varying
randomness injected into interaction parameters and the general framework, our
proposed approach can still maintain $R$-linear convergence when the global
objective function is strongly convex.

The rest of this paper is organized as follows. Sec. 2 formally introduces the
problem and reviews some key concepts. A general framework for gradient-
tracking based decentralized optimization is introduced in Sec. 3, followed by
the inherently privacy-preserving algorithm in Sec. 4. In Sec. 4 we also
analyze the convergence of the proposed algorithm and rigorously characterize
its privacy-preserving performance. Examples and comparison with existing
results are presented in Sec. 5. Finally we conclude this paper in Sec. 6.

Notations: $\mathbb{R}$ and $\mathbb{Z}_{\geq 0}$ denote real numbers and
nonnegative integers, respectively. $\mathbb{R}^{n}$ denotes the Euclidean
space of dimension $n$, and $\mathbb{R}^{m\times n}$ denotes the set of
$m\times n$ matrices with real coefficients. $\mathbf{0}_{n}\in\mathbb{R}^{n}$
and $\mathbf{0}_{m\times n}\in\mathbb{R}^{m\times n}$ denote zero vector and
$m\times n$ zero matrix, respectively. $\mathbf{1}_{n}\in\mathbb{R}^{n}$
denotes the $n\times 1$ all-ones vector, $\mathbf{1}_{m\times
n}\in\mathbb{R}^{m\times n}$ denotes the $m\times n$ all-ones matrix, and
$\mathbf{I}_{n}\in\mathbb{R}^{n\times n}$ denotes the $n\times n$ identity
matrix. For matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$, its transpose is
denoted as $\mathbf{A}^{T}\in\mathbb{R}^{n\times m}$. The notation $\|\cdot\|$
denotes the Euclidean norm of vectors and the spectral norm of matrices. The
notation $\otimes$ represents the Kronecker product.

##  2 Problem Formulation

We characterize the interaction among nodes as a directed graph
$\mathcal{G}=(\mathcal{V},\,\mathcal{E})$, where
$\mathcal{V}=\\{1,2,\ldots,n\\}$ is the index set of nodes.
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the set of edges, whose
elements are such that an ordered pair $(i,\,j)$ belongs to $\mathcal{E}$ if
and only if there exists a directed link from node $j$ to node $i$, i.e., node
$j$ can send messages to node $i$. For notational convenience, we assume no
self edges, i.e., $(i,\,i)\notin\mathcal{E}$ for all $i\in\mathcal{V}$. The
out-neighbor set of node $i$, which represents the set of nodes that can
receive messages from node $i$, is denoted as
$\mathcal{N}_{i}^{out}=\\{j\in\mathcal{V}\,|\,\forall\,(j,\,i)\in\mathcal{E}\\}$.
Similarly, the in-neighbor set of node $i$, which represents the set of nodes
that can send messages to node $i$, is denoted as
$\mathcal{N}_{i}^{in}=\\{j\in\mathcal{V}\,|\,\forall\,(i,\,j)\in\mathcal{E}\\}$.
From the above definitions, one can obtain that $i\in\mathcal{N}_{j}^{out}$
and $j\in\mathcal{N}_{i}^{in}$ are equivalent to each other.

######  Assumption 1.

We assume that the directed graph $\mathcal{G}$ is strongly connected, i.e.,
for any $i,j\in\mathcal{V}$ with $i\neq j$, there exists at least one directed
path from $i$ to $j$ in $\mathcal{G}$, where the directed path respects the
direction of the edges.

We use the following standard definitions to characterize objective functions:

######  Definition 1.

A differentiable function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is convex if
$f(\mathbf{x}^{\prime})\geq f(\mathbf{x})+\nabla
f(\mathbf{x})^{T}(\mathbf{x}^{\prime}-\mathbf{x})$ holds for any $\mathbf{x}$
and $\mathbf{x}^{\prime}$ in $\mathbb{R}^{d}$.

######  Definition 2.

A differentiable function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is
$\alpha$-strongly convex with $\alpha>0$ if $(\nabla f(\mathbf{x})-\nabla
f(\mathbf{x}^{\prime}))^{T}(\mathbf{x}-\mathbf{x}^{\prime})\geq\alpha\|{\mathbf{x}-\mathbf{x}^{\prime}}\|^{2}$
holds for any $\mathbf{x}$ and $\mathbf{x}^{\prime}$ in $\mathbb{R}^{d}$.

######  Definition 3.

A differentiable function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is
$\beta$-smooth with $\beta>0$ if $\|\nabla f(\mathbf{x})-\nabla
f(\mathbf{x}^{\prime})\|\leq\beta\|{\mathbf{x}-\mathbf{x}^{\prime}}\|$ holds
for any $\mathbf{x}$ and $\mathbf{x}^{\prime}$ in $\mathbb{R}^{d}$.

######  Assumption 2.

We assume that each local objective function $f_{i}$ is differentiable,
convex, and $\beta_{i}$-smooth. We also assume that the global objective
function $F=\sum_{i=1}^{n}f_{i}(\mathbf{x})$ is $\alpha_{F}$-strongly convex.

Under Definitions 1-3 and Assumption 2, one can verify that the global
objective function $F$ is $\beta_{F}$-smooth with
$\beta_{F}=\sum_{i=1}^{n}\beta_{i}$, and $\alpha_{F}$ is always less than or
equal to $\beta_{F}$. Moreover, problem (1) has a unique optimal solution,
which is denoted by $\mathbf{x}^{*}$.

##  3 A General Decentralized Optimization Framework

###  3.1 A New Framework for Decentralized Optimization

As discussed in Sec. 1, most existing decentralized optimization algorithms do
not consider the privacy of individual nodes. In this paper, we propose to
enable privacy preservation in decentralized optimization by exploiting the
robustness of decentralized optimization dynamics. To this end, we first
propose a new framework for gradient-tracking based decentralized optimization
in Algorithm 1.

Algorithm 1 A new decentralized optimization framework

Each node $i$ initializes $\mathbf{x}_{i}^{0}$ randomly in $\mathbb{R}^{d}$
and sets $\mathbf{y}_{i}^{0}=\nabla f_{i}(\mathbf{x}_{i}^{0})$. At iteration
$k$:

1:Node $i$ computes and sends $\mathbf{x}_{i}^{k}$ as well as
$\mathbf{\Lambda}_{i}^{k}\mathbf{y}_{i}^{k}$ to its out-neighbors
$l\in\mathcal{N}_{i}^{out}$, where $\mathbf{\Lambda}_{i}^{k}$ is a diagonal
matrix denoting the stepsize.

2:After receiving $\mathbf{x}_{j}^{k}$ and
$\mathbf{\Lambda}_{j}^{k}\mathbf{y}_{j}^{k}$ from its in-neighbors
$j\in\mathcal{N}_{i}^{in}$, node $i$ updates $\mathbf{x}_{i}$ as:
$\displaystyle\mathbf{x}_{i}^{k+1}={\textstyle\sum_{j\in\mathcal{N}_{i}^{in}\cup\\{i\\}}}\big{(}{\mathbf{R}_{ij}^{k}\mathbf{x}_{j}^{k}-\mathbf{A}_{ij}^{k}\mathbf{\Lambda}_{j}^{k}\mathbf{y}_{j}^{k}}\big{)}$
(2) where $\mathbf{R}_{ij}^{k}$ and $\mathbf{A}_{ij}^{k}$ are coupling weight
matrices.

3:After updating $\mathbf{x}_{i}$, node $i$ computes and sends
$\mathbf{C}_{li}^{k}\mathbf{y}_{i}^{k}+\mathbf{B}_{li}^{k}\big{(}\nabla
f_{i}(\mathbf{x}_{i}^{k+1})-\nabla f_{i}(\mathbf{x}_{i}^{k})\big{)}$ to its
out-neighbors $l\in\mathcal{N}_{i}^{out}$, where $\mathbf{C}_{li}^{k}$ and
$\mathbf{B}_{li}^{k}$ are coupling weight matrices.

4:After receiving
$\mathbf{C}_{ij}^{k}\mathbf{y}_{j}^{k}+\mathbf{B}_{ij}^{k}\big{(}\nabla
f_{j}(\mathbf{x}_{j}^{k+1})-\nabla f_{j}(\mathbf{x}_{j}^{k})\big{)}$ from its
in-neighbors $j\in\mathcal{N}_{i}^{in}$, node $i$ updates $\mathbf{y}_{i}$ as:
$\displaystyle\mathbf{y}_{i}^{k+1}=$
$\displaystyle{\textstyle\sum_{j\in\mathcal{N}_{i}^{in}\cup\\{i\\}}}\big{(}\mathbf{C}_{ij}^{k}\mathbf{y}_{j}^{k}$
(3) $\displaystyle\quad+\mathbf{B}_{ij}^{k}\big{(}\nabla
f_{j}(\mathbf{x}_{j}^{k+1})-\nabla f_{j}(\mathbf{x}_{j}^{k})\big{)}\big{)}$

Note that by setting
$\mathbf{R}_{ij}^{k}=\mathbf{A}_{ij}^{k}=\mathbf{0}_{d\times d}$ for
$j\notin\mathcal{N}_{i}^{in}\cup\\{i\\}$ and
$\mathbf{C}_{ji}^{k}=\mathbf{B}_{ji}^{k}=\mathbf{0}_{d\times d}$ for
$j\notin\mathcal{N}_{i}^{out}\cup\\{i\\}$, the update rules in (2)-(3) can be
rewritten as

$\displaystyle\mathbf{x}_{i}^{k+1}$
$\displaystyle={\textstyle\sum_{j=1}^{n}}\big{(}{\mathbf{R}_{ij}^{k}\mathbf{x}_{j}^{k}-\mathbf{A}_{ij}^{k}\mathbf{\Lambda}_{j}^{k}\mathbf{y}_{j}^{k}}\big{)}$
(4) $\displaystyle\mathbf{y}_{i}^{k+1}$
$\displaystyle={\textstyle\sum_{j=1}^{n}}\big{(}\mathbf{C}_{ij}^{k}\mathbf{y}_{j}^{k}+\mathbf{B}_{ij}^{k}\big{(}\nabla
f_{j}^{k+1}-\nabla f_{j}^{k}\big{)}\big{)}$

where $\nabla f_{j}^{k}=\nabla f_{j}(\mathbf{x}_{j}^{k})$ is the gradient of
$f_{j}$ evaluated at $\mathbf{x}_{j}^{k}$, which is typically nonlinear in
nature. (4) can be rewritten into a more compact matrix form

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=\mathbf{R}^{k}\mathbf{x}^{k}-\mathbf{A}^{k}\mathbf{\Lambda}^{k}\mathbf{y}^{k}$
(5) $\displaystyle\mathbf{y}^{k+1}$
$\displaystyle=\mathbf{C}^{k}\mathbf{y}^{k}+\mathbf{B}^{k}\big{(}\nabla
f^{k+1}-\nabla f^{k}\big{)}$

where
$\mathbf{x}^{k}=[(\mathbf{x}_{1}^{k})^{T}\,\cdots\,(\mathbf{x}_{n}^{k})^{T}]^{T}$,
$\mathbf{y}^{k}=[(\mathbf{y}_{1}^{k})^{T}\,\cdots\,(\mathbf{y}_{n}^{k})^{T}]^{T}$,
$\nabla f^{k}=[(\nabla f_{1}^{k})^{T}\,\cdots\,(\nabla f_{n}^{k})^{T}]^{T}$,
and $\mathbf{R}^{k}$, $\mathbf{A}^{k}$, $\mathbf{C}^{k}$, and $\mathbf{B}^{k}$
are block matrices with the $(ij)$-th block entry being $\mathbf{R}_{ij}^{k}$,
$\mathbf{A}_{ij}^{k}$, $\mathbf{C}_{ij}^{k}$, and $\mathbf{B}_{ij}^{k}$,
respectively. $\mathbf{\Lambda}^{k}$ is a block diagonal matrix with the
$i$-th diagonal block being $\mathbf{\Lambda}_{i}^{k}$.

###  3.2 Relationship with Existing Decentralized Optimization Algorithms

The proposed decentralized optimization framework is very general and includes
as special cases many popular decentralized optimization algorithms, such as
Aug-DGM [46], DIGing [33, 24], ATC-DIGing [25], AsynDGM [47],
$\mathcal{A}\mathcal{B}$ [45], and Push-Pull [32, 4, 53]. Table I summarizes
the particular selections of parameters $\mathbf{R}^{k}$, $\mathbf{A}^{k}$,
$\mathbf{B}^{k}$, $\mathbf{C}^{k}$, and $\mathbf{\Lambda}^{k}$ in (5) to
obtain some commonly used decentralized optimization algorithms.

Table I. Particular selections of parameters in the
proposed framework to obtain some existing algorithms.

| $\mathbf{R}^{k}$ | $\mathbf{A}^{k}$ | $\mathbf{C}^{k}$ | $\mathbf{B}^{k}$ | $\mathbf{\Lambda}^{k}$
---|---|---|---|---|---
Aug-DGM [46] | $\mathbf{W}$ | $\mathbf{W}$ | $\mathbf{W}$ | $\mathbf{W}$ | $\mathbf{\Lambda}$
DIGing [33] | $\mathbf{W}$ | $\mathbf{I}$ | $\mathbf{W}$ | $\mathbf{I}$ | $\lambda\mathbf{I}$
DIGing [24] | $\mathbf{W}^{k}$ | $\mathbf{I}$ | $\mathbf{W}^{k}$ | $\mathbf{I}$ | $\lambda\mathbf{I}$
ATC-DIGing [25] | $\mathbf{W}$ | $\mathbf{W}$ | $\mathbf{W}$ | $\mathbf{W}$ | $\mathbf{\Lambda}$
AsynDGM [47] | $\mathbf{W}^{k}$ | $\mathbf{W}^{k}$ | $\mathbf{W}^{k}$ | $\mathbf{I}$ | $\mathbf{\Lambda}$
$\mathcal{A}\mathcal{B}$ [45] | $\mathbf{R}$ | $\mathbf{I}$ | $\mathbf{C}$ | $\mathbf{C}$ | $\lambda\mathbf{I}$
Push-Pull [32] | $\mathbf{R}$ | $\mathbf{R}$ | $\mathbf{C}$ | $\mathbf{C}$ | $\lambda\mathbf{I}$
Push-Pull [4] | $\mathbf{R}$ | $\mathbf{I}$ | $\mathbf{C}$ | $\mathbf{I}$ | $\lambda\mathbf{I}$
Push-Pull [53] | $\mathbf{R}$ | $\mathbf{R}$ | $\mathbf{C}$ | $\mathbf{I}$ | $\lambda\mathbf{I}$

  * $\mathbf{W}$ and $\mathbf{W}^{k}$ are doubly stochastic, $\mathbf{R}$ is time-invariant and row-stochastic, $\mathbf{C}$ is time-invariant and column-stochastic, and $\lambda\mathbf{I}$ and $\mathbf{\Lambda}$ represent homogeneous and heterogeneous stepsize matrices, respectively. Note that Kronecker product with $\mathbf{I}_{d}$ is needed for these matrices when $d>1$.

In fact, by setting $\mathbf{R}^{k}$, $\mathbf{A}^{k}$, $\mathbf{C}^{k}$,
$\mathbf{B}^{k}$, and $\mathbf{\Lambda}^{k}$ to $\mathbf{R}$, $\mathbf{I}$,
$\mathbf{C}$, $\mathbf{I}$, and $\mathbf{\Lambda}$, respectively, our proposed
algorithm in (5) can be rewritten as
$\mathbf{x}^{k+1}=(\mathbf{R}+\mathbf{C})\mathbf{x}^{k}-\mathbf{C}\mathbf{R}\mathbf{x}^{k-1}-\mathbf{\Lambda}\big{(}\nabla
f^{k}-\nabla f^{k-1}\big{)}$ which becomes EXTRA [41].

As indicated in Table I, our proposed framework reduces to existing algorithms
when the parameters are selected appropriately. Moreover, it can also give
rise to new algorithms with special properties. In particular, in what follows
we show that it results in new algorithms having inherent privacy-preserving
capabilities.

##  4 Privacy-preserving Decentralized Optimization

Based on the general decentralized optimization framework proposed in Sec. 3,
we can enable privacy-preservation in decentralized optimization without
compromising optimization accuracy.

###  4.1 Privacy-preserving Design

To enable privacy, we propose to add randomness in stepsize
$\mathbf{\Lambda}^{k}$ and coupling weights $\mathbf{R}^{k}$,
$\mathbf{A}^{k}$, $\mathbf{C}^{k}$, and $\mathbf{B}^{k}$ for iterations $k<K$,
where $K$ is a positive integer. The detailed parameter design for each node
$i$ is given in Table II. More specifically, for iterations $k<K$, each node
$i$ selects the coupling weights
$\mathbf{C}_{ji}^{k}=\text{diag}\left\\{c_{ji}^{k}(1),\ldots,c_{ji}^{k}(d)\right\\}$
and
$\mathbf{B}_{ji}^{k}=\text{diag}\left\\{b_{ji}^{k}(1),\ldots,b_{ji}^{k}(d)\right\\}$
for $j\in\mathcal{N}_{i}^{out}$ following any chosen random distributions with
support $\mathbb{R}$ such as Gaussian or Laplace distribution (so the coupling
weights can be negative, positive, or zero). To guarantee the column-
stochastic property of both $\mathbf{C}^{k}$ and $\mathbf{B}^{k}$, each node
$i$ sets $\mathbf{C}_{ii}^{k}$ and $\mathbf{B}_{ii}^{k}$ as
$\mathbf{C}_{ii}^{k}=\mathbf{I}_{d}-\sum_{j\in\mathcal{N}_{i}^{out}}\mathbf{C}_{ji}^{k}$
and
$\mathbf{B}_{ii}^{k}=\mathbf{I}_{d}-\sum_{j\in\mathcal{N}_{i}^{out}}\mathbf{B}_{ji}^{k}$,
respectively. In this way, the column-stochastic property of both
$\mathbf{C}^{k}$ and $\mathbf{B}^{k}$ for iterations $k<K$ is guaranteed in a
fully decentralized manner. Since we do not require $\mathbf{R}^{k}$ or
$\mathbf{A}^{k}$ to be row-stochastic for iterations $k<K$, each node $i$ can
select $\mathbf{R}_{ij}^{k}$ and $\mathbf{A}_{ij}^{k}$ for
$j\in\mathcal{N}_{i}^{in}\cup\\{i\\}$ following any random distributions.

Table II. Parameter design for each node $i$ in our proposed framework.

| Iterations $k<K\,^{\dagger}$ | Iterations $k\geq K$
---|---|---
$\mathbf{\Lambda}_{i}^{k}$ |  $\mathbf{\Lambda}_{i}^{k}=\text{diag}\\{\lambda_{i}^{k}(1),\cdots,\lambda_{i}^{k}(d)\\}$, where $\lambda_{i}^{k}(1),\ldots,\lambda_{i}^{k}(d)$ are chosen following selected distributions with support $\mathbb{R}$ |  $\mathbf{\Lambda}_{i}^{k}=\lambda\mathbf{I}_{d}$, $\lambda>0$
$\mathbf{R}_{ij}^{k}$ |  $\mathbf{R}_{ij}^{k}=\text{diag}\\{r_{ij}^{k}(1),\cdots,r_{ij}^{k}(d)\\}$, where $r_{ij}^{k}(l)$ are chosen from $\mathbb{R}$ for $j\in\mathcal{N}_{i}^{in}\cup\\{i\\}$ and $l=1,\ldots,d$ following selected distributions with support $\mathbb{R}$ |  $\mathbf{R}_{ij}^{k}=r_{ij}^{k}\mathbf{I}_{d}$, where $r_{ij}^{k}$ are selected from $[\eta,\,1]$ for $j\in\mathcal{N}_{i}^{in}\cup\\{i\\}$ subject to $\sum_{j=1}^{n}r_{ij}^{k}=1$
$\mathbf{A}_{ij}^{k}$ |  $\mathbf{A}_{ij}^{k}=\text{diag}\\{a_{ij}^{k}(1),\cdots,a_{ij}^{k}(d)\\}$, where $a_{ij}^{k}(l)$ are chosen from $\mathbb{R}$ for $j\in\mathcal{N}_{i}^{in}\cup\\{i\\}$ and $l=1,\ldots,d$ following selected distributions with support $\mathbb{R}$ |  $\mathbf{A}_{ij}^{k}=a_{ij}^{k}\mathbf{I}_{d}$, where $a_{ij}^{k}$ are selected from $[\eta,\,1]$ for $j\in\mathcal{N}_{i}^{in}\cup\\{i\\}$ subject to $\sum_{j=1}^{n}a_{ij}^{k}=1$
$\mathbf{C}_{ji}^{k}$ |  $\mathbf{C}_{ji}^{k}=\text{diag}\\{c_{ji}^{k}(1),\cdots,c_{ji}^{k}(d)\\}$, where $c_{ji}^{k}(l)$ are chosen from $\mathbb{R}$ for $j\in\mathcal{N}_{i}^{out}$ and $l=1,\ldots,d$ following selected distributions with support $\mathbb{R}$, and $\mathbf{C}_{ii}^{k}$ is set as $\mathbf{C}_{ii}^{k}=\mathbf{I}_{d}-\sum_{j\in\mathcal{N}_{i}^{out}}\mathbf{C}_{ji}^{k}$ |  $\mathbf{C}_{ji}^{k}=c_{ji}^{k}\mathbf{I}_{d}$, where $c_{ji}^{k}$ are selected from $[\eta,\,1]$ for $j\in\mathcal{N}_{i}^{out}\cup\\{i\\}$ subject to $\sum_{j=1}^{n}c_{ji}^{k}=1$
$\mathbf{B}_{ji}^{k}$ |  $\mathbf{B}_{ji}^{k}=\text{diag}\\{b_{ji}^{k}(1),\cdots,b_{ji}^{k}(d)\\}$, where $b_{ji}^{k}(l)$ are chosen from $\mathbb{R}$ for $j\in\mathcal{N}_{i}^{out}$ and $l=1,\ldots,d$ following selected distributions with support $\mathbb{R}$, and $\mathbf{B}_{ii}^{k}$ is set as $\mathbf{B}_{ii}^{k}=\mathbf{I}_{d}-\sum_{j\in\mathcal{N}_{i}^{out}}\mathbf{B}_{ji}^{k}$ |  $\mathbf{B}_{ji}^{k}=b_{ji}^{k}\mathbf{I}_{d}$ select $b_{ji}^{k}$ from $[\eta,\,1]$ for $j\in\mathcal{N}_{i}^{out}\cup\\{i\\}$ subject to $\sum_{j=1}^{n}b_{ji}^{k}=1$

  * † $K$ can be any positive integer. Its influence will be discussed in detail in Remark 2 and Remark 5.

Furthermore, as indicated in Table II, the column stochastic property of
$\mathbf{C}^{k}$ and $\mathbf{B}^{k}$ and the row stochastic property of
$\mathbf{R}^{k}$ and $\mathbf{A}^{k}$ are required for iterations $k\geq K$.
Let us take $\mathbf{C}^{k}$ as an example to show how to ensure these
properties in a fully decentralized manner. To meet the requirements of Table
II, each node $i$ selects a set of real values
$\left\\{c_{ji}^{k}\in[\eta,\,1]\,\big{|}\,j\in\mathcal{N}_{i}^{out}\cup\\{i\\}\right\\}$
with their sum equal to one, then sets $\mathbf{C}_{ji}^{k}$ as
$\mathbf{C}_{ji}^{k}=c_{ji}^{k}\mathbf{I}_{d}$ for
$j\in\mathcal{N}_{i}^{out}\cup\\{i\\}$. Note that there are many ways to
obtain such a set of real values with sum equal to one. For example, node $i$
first randomly selects a set of real values
$\left\\{p_{ji}^{k}\,\big{|}\,j\in\mathcal{N}_{i}^{out}\cup\\{i\\}\right\\}$
from $[0,\,1]$, then it determines $c_{ji}^{k}$ by normalizing these values
$\\{p_{ji}^{k}\\}$ via
$c_{ji}^{k}=\frac{[1-(|\mathcal{N}_{i}^{out}|+1)\eta][(1-\eta)p_{ji}^{k}+\eta]}{(1-\eta)\sum_{l\in\mathcal{N}_{i}^{out}\cup\\{i\\}}p_{li}^{k}+(|\mathcal{N}_{i}^{out}|+1)\eta}+\eta$
for $j\in\mathcal{N}_{i}^{out}\cup\\{i\\}$. One can verify
$\sum_{j\in\mathcal{N}_{i}^{out}\cup\\{i\\}}c_{ji}^{k}=1$ and
$c_{ji}^{k}\in[\eta,\,1]$ for $j\in\mathcal{N}_{i}^{out}\cup\\{i\\}$, and
hence the column stochastic property of $\mathbf{C}^{k}$ is guaranteed in a
fully decentralized manner.

######  Remark 1.

We allow each agent $i$ to randomly choose its associated coupling weights and
stepsizes for iterations $k<K$ following any distributions. These
distributions can be any continuous probability distribution with support
$\mathbb{R}$, e.g., Gaussian distribution, Laplace distribution, etc.

###  4.2 Convergence Analysis

In this subsection, inspired by the work in [38], we prove that our privacy-
preserving algorithm has $R$-linear convergence. Since the parameters in
iterations $0\leq k\leq K-1$ vary randomly with time, we first analyze their
influence on states $\mathbf{x}_{i}^{K}$ and $\mathbf{y}_{i}^{K}$, based on
which we can characterize the evolution of state variables after iteration
$K-1$. From the parameter design in Table II, we have
$\sum_{i=1}^{n}\mathbf{C}_{ij}^{k}=\mathbf{I}_{d}$ and
$\sum_{i=1}^{n}\mathbf{B}_{ij}^{k}=\mathbf{I}_{d}$, which, in combination with
(4) leads to

$\displaystyle\big{(}{\textstyle\sum_{i=1}^{n}}\mathbf{y}_{i}^{k+1}\big{)}^{T}=\big{(}{\textstyle\sum_{i=1}^{n}}(\mathbf{y}_{i}^{k}+\nabla
f_{i}^{k+1}-\nabla f_{i}^{k})\big{)}^{T}$ (6)

for $k\leq K-1$, where we used the property
$\big{(}\mathbf{C}_{ij}^{k}\big{)}^{T}=\mathbf{C}_{ij}^{k}$ and
$\big{(}\mathbf{B}_{ij}^{k}\big{)}^{T}=\mathbf{B}_{ij}^{k}$ due to their
diagonal structure. We can further rewrite (6) as
$\sum_{i=1}^{n}\mathbf{y}_{i}^{k+1}-\sum_{i=1}^{n}\nabla
f_{i}^{k+1}=\sum_{i=1}^{n}\mathbf{y}_{i}^{k}-\sum_{i=1}^{n}\nabla f_{i}^{k}$.
Given $\mathbf{y}_{i}^{0}=\nabla f_{i}^{0}$, one can obtain

$\displaystyle{\textstyle\sum_{i=1}^{n}}\big{(}\mathbf{y}_{i}^{K}-\nabla
f_{i}^{K}\big{)}=\cdots={\textstyle\sum_{i=1}^{n}}\big{(}\mathbf{y}_{i}^{0}-\nabla
f_{i}^{0}\big{)}=\mathbf{0}_{d}$ (7)

The equality constraint in (7) reflects the influence of random time-varying
parameters in iterations $0\leq k\leq K-1$ on the dynamics. Next, under this
constraint, we study the system dynamics after iteration $K-1$.

For our parameter design in Table II, we have
$\mathbf{\Lambda}_{i}^{k}=\lambda\mathbf{I}_{d}$,
$\mathbf{R}_{ij}^{k}=r_{ij}^{k}\mathbf{I}_{d}$,
$\mathbf{A}_{ij}^{k}=a_{ij}^{k}\mathbf{I}_{d}$,
$\mathbf{C}_{ij}^{k}=c_{ij}^{k}\mathbf{I}_{d}$, and
$\mathbf{B}_{ij}^{k}=b_{ij}^{k}\mathbf{I}_{d}$ for $k\geq K$. Constructing
$n\times n$ matrices $\mathbf{\bar{R}}^{k}$, $\mathbf{\bar{A}}^{k}$,
$\mathbf{\bar{C}}^{k}$, and $\mathbf{\bar{B}}^{k}$ with the $(ij)$-th elements
being $r_{ij}^{k}$, $a_{ij}^{k}$, $c_{ij}^{k}$, and $b_{ij}^{k}$,
respectively, we have
$\mathbf{R}^{k}=\mathbf{\bar{R}}^{k}\otimes\mathbf{I}_{d}$,
$\mathbf{A}^{k}=\mathbf{\bar{A}}^{k}\otimes\mathbf{I}_{d}$,
$\mathbf{C}^{k}=\mathbf{\bar{C}}^{k}\otimes\mathbf{I}_{d}$, and
$\mathbf{B}^{k}=\mathbf{\bar{B}}^{k}\otimes\mathbf{I}_{d}$ for $k\geq K$. Then
for $k\geq K$, we can rewrite the system dynamics (5) as

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=(\mathbf{\bar{R}}^{k}\otimes\mathbf{I}_{d})\mathbf{x}^{k}-\lambda(\mathbf{\bar{A}}^{k}\otimes\mathbf{I}_{d})\mathbf{y}^{k}$
(8) $\displaystyle\mathbf{y}^{k+1}$
$\displaystyle=(\mathbf{\bar{C}}^{k}\otimes\mathbf{I}_{d})\mathbf{y}^{k}+(\mathbf{\bar{B}}^{k}\otimes\mathbf{I}_{d})\big{(}\nabla
f^{k+1}-\nabla f^{k}\big{)}$

To facilitate convergence analysis, we introduce a state transformation,
$\mathbf{s}^{k}=((\mathbf{\bar{V}}^{k})^{-1}\otimes\mathbf{I}_{d})\mathbf{y}^{k}$,
where $\mathbf{\bar{V}}^{k}=\text{diag}(\mathbf{v}^{k})$ with the evolution of
$\mathbf{v}^{k}$ governed by

$\mathbf{v}^{k+1}=\mathbf{\bar{C}}^{k}\mathbf{v}^{k}$ (9)

for $k\geq K$. The value of $\mathbf{v}^{k}$ at iteration $K$ is set as
$\frac{1}{n}\mathbf{1}_{n}$, i.e., $\mathbf{v}^{K}=\frac{1}{n}\mathbf{1}_{n}$.
Then (8) can be rewritten as

$\displaystyle\mathbf{x}^{k+1}$
$\displaystyle=\mathbf{R}^{k}\mathbf{x}^{k}-\lambda(\mathbf{\bar{A}}^{k}\mathbf{\bar{V}}^{k}\otimes\mathbf{I}_{d})\mathbf{s}^{k}$
(10) $\displaystyle\mathbf{s}^{k+1}$
$\displaystyle=\mathbf{P}^{k}\mathbf{s}^{k}+((\mathbf{\bar{V}}^{k+1})^{-1}\mathbf{\bar{B}}^{k}\otimes\mathbf{I}_{d})\big{(}\nabla
f^{k+1}-\nabla f^{k}\big{)}$

for $k\geq K$ where $\mathbf{P}^{k}=\mathbf{\bar{P}}^{k}\otimes\mathbf{I}_{d}$
and
$\mathbf{\bar{P}}^{k}=(\mathbf{\bar{V}}^{k+1})^{-1}\mathbf{\bar{C}}^{k}\mathbf{\bar{V}}^{k}$.
As proven in Lemma 4 in Appendix A, $\mathbf{\bar{P}}^{k}$ is row-stochastic
and the sequence $\\{\mathbf{\bar{P}}^{k}\\}$ is ergodic for $k\geq K$.
Furthermore, the sequence of $\\{\mathbf{v}^{k}\\}$ for $k\geq K$ is an
absolute probability sequence for $\\{\mathbf{\bar{P}}^{k}\\}$ (see Appendix A
for the definitions of ergodic sequence and absolute probability sequence.) We
define $\mathbf{\bar{x}}_{\text{w}}^{k}$, $\mathbf{\tilde{x}}_{\text{w}}^{k}$,
$\mathbf{r}^{k}$, and $\mathbf{\tilde{s}}_{\text{w}}^{k}$ as

$\displaystyle\mathbf{\bar{x}}_{\text{w}}^{k}$
$\displaystyle=((\boldsymbol{\phi}^{k})^{T}\otimes\mathbf{I}_{d})\mathbf{x}^{k},\quad\
\mathbf{r}^{k}=\mathbf{1}_{n}\otimes\mathbf{\bar{x}}_{\text{w}}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}$
$\displaystyle\mathbf{\tilde{x}}_{\text{w}}^{k}$
$\displaystyle=\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{\bar{x}}_{\text{w}}^{k},\qquad\mathbf{\tilde{s}}_{\text{w}}^{k}=\mathbf{s}^{k}-(\mathbf{1}_{n}(\mathbf{v}^{k})^{T}\otimes\mathbf{I}_{d})\mathbf{s}^{k}$

where for $k\geq K$, $\\{\boldsymbol{\phi}^{k}\\}$ is an absolute probability
sequence for the ergodic sequence of row-stochastic matrices
$\\{\mathbf{\bar{R}}^{k}\\}$. Before presenting our main result, we introduce
some auxiliary lemmas.

######  Lemma 1.

Under Assumptions 1 and 2, and the parameter design in Table II, the following
inequality holds for $k\geq K+\bar{N}-1$:

$\displaystyle\|\mathbf{\tilde{x}}_{\text{w}}^{k+1}\|$ (11)
$\displaystyle\leq\big{(}r_{R}+\lambda
Q_{R}n\sqrt{n}\bar{\beta}\big{)}\|\mathbf{\tilde{x}}_{\text{w}}^{k-\bar{N}+1}\|+\lambda
Q_{R}n\sqrt{n}\bar{\beta}\sum_{l=0}^{\bar{N}-2}\|\mathbf{\tilde{x}}_{\text{w}}^{k-l}\|$
$\displaystyle\quad+\lambda
Q_{R}n\sqrt{n}\bar{\beta}\|\mathbf{r}^{k-\bar{N}+1}\|+\lambda
Q_{R}n\sqrt{n}\bar{\beta}\sum_{l=0}^{\bar{N}-2}\|\mathbf{r}^{k-l}\|$
$\displaystyle\quad+\lambda
Q_{R}\sqrt{n}\|\mathbf{\tilde{s}}_{\text{w}}^{k-\bar{N}+1}\|+\lambda
Q_{R}\sqrt{n}\sum_{l=0}^{\bar{N}-2}\|\mathbf{\tilde{s}}_{\text{w}}^{k-l}\|$

where $\bar{\beta}=\max\\{\beta_{1},\cdots,\beta_{n}\\}$,
$Q_{R}=2n(1+\eta^{-(n-1)})/(1-\eta^{n-1})$,
$r_{R}=Q_{R}(1-\eta^{n-1})^{\frac{N_{R}-1}{n-1}}$, and
$\bar{N}=\max\\{N_{R},N_{P}\\}$ (see Lemmas 4 and 5 in Appendix A for more
details on parameters $N_{R}$, $N_{P}$, $r_{R}$, and $Q_{R}$.)

Proof: The proof is given in Appendix B. $\blacksquare$

######  Lemma 2.

Under Assumptions 1 and 2, and the parameter design in Table II, the following
inequality holds for $k\geq K$:

$\displaystyle\|\mathbf{r}^{k+1}\|\leq\lambda
n\bar{\beta}\|\mathbf{\tilde{x}}_{\text{w}}^{k}\|+\big{(}1-\lambda
n^{-1}\eta^{n-1}\alpha_{F}\big{)}\|\mathbf{r}^{k}\|+\lambda
n\|\mathbf{\tilde{s}}_{\text{w}}^{k}\|$ (12)

if the stepsize $\lambda$ satisfies $\lambda\leq{1}/\beta_{F}$.

Proof: The proof is given in Appendix C. $\blacksquare$

######  Lemma 3.

Under Assumptions 1 and 2, and the parameter design in Table II, the following
inequality holds for $k\geq K+\bar{N}-1$:

$\displaystyle\|\mathbf{\tilde{s}}_{\text{w}}^{k+1}\|$ (13)
$\displaystyle\leq\big{(}\frac{2n^{2}\bar{\beta}Q_{P}}{\eta^{n-1}}+\lambda\frac{n^{3}\bar{\beta}^{2}Q_{P}}{\eta^{n-1}}\big{)}\big{(}\|\mathbf{\tilde{x}}_{\text{w}}^{k-\bar{N}+1}\|+\sum_{l=0}^{\bar{N}-2}\|\mathbf{\tilde{x}}_{\text{w}}^{k-l}\|\big{)}$
$\displaystyle\quad+\lambda\frac{n^{3}\bar{\beta}^{2}Q_{P}}{\eta^{n-1}}\big{(}\|\mathbf{r}^{k-\bar{N}+1}\|+\sum_{l=0}^{\bar{N}-2}\|\mathbf{r}^{k-l}\|\big{)}$
$\displaystyle\quad+\big{(}r_{P}+\lambda\frac{n^{2}\bar{\beta}Q_{P}}{\eta^{n-1}}\big{)}\|\mathbf{\tilde{s}}_{\text{w}}^{k-\bar{N}+1}\|+\lambda\frac{n^{2}\bar{\beta}Q_{P}}{\eta^{n-1}}\sum_{l=0}^{\bar{N}-2}\|\mathbf{\tilde{s}}_{\text{w}}^{k-l}\|$

where
$Q_{P}=2n\big{(}1+(n\eta^{-n})^{n-1}\big{)}/\big{(}1-(n^{-1}\eta^{n})^{n-1}\big{)}$
and $r_{P}=Q_{P}\big{(}1-(n^{-1}\eta^{n})^{n-1}\big{)}^{\frac{N_{P}-1}{n-1}}$
(see Lemma 4 in Appendix A for more details on parameters $Q_{P}$ and
$r_{P}$.)

Proof: The proof is given in Appendix D. $\blacksquare$

Now we are in position to present our main convergence result.

######  Theorem 1.

Under Assumptions 1 and 2, and the parameter design in Table II, our algorithm
has $R$-linear convergence when the stepsize parameter $\lambda$ is
sufficiently small.

Proof: Denoting $\boldsymbol{\xi}^{k}$ as
$\boldsymbol{\xi}^{k}=\big{[}\|\mathbf{\tilde{x}}_{\text{w}}^{k}\|,\,\|\mathbf{r}^{k}\|,\,\|\mathbf{\tilde{s}}_{\text{w}}^{k}\|\big{]}^{T}$
and invoking the results of Lemmas 1, 2, and 3, we have the following
inequality for $k\geq K+\bar{N}-1$

$\displaystyle\begin{bmatrix}\boldsymbol{\xi}^{k+1}\\\ \vdots\\\
\boldsymbol{\xi}^{k-\bar{N}+2}\end{bmatrix}\leq\underbrace{(\mathbf{M}^{1}+\lambda\mathbf{M}^{2})}_{\mathbf{M}(\lambda)}\begin{bmatrix}\boldsymbol{\xi}^{k}\\\
\vdots\\\ \boldsymbol{\xi}^{k-\bar{N}+1}\end{bmatrix}$ (14)

where $\mathbf{M}^{1}$ and $\mathbf{M}^{2}$ are given by

$\displaystyle\ \,\mathbf{M}^{1}=\qquad\qquad\qquad\qquad\quad\
\mathbf{M}^{2}=$ (15)
$\displaystyle\begin{bmatrix}\mathbf{M}^{1}_{a}&\mathbf{M}^{1}_{b}&\cdots&\mathbf{M}^{1}_{b}&\mathbf{M}^{1}_{c}\\\
\mathbf{I}_{3}&&&&\\\ &&\ddots&&\\\ &&&\mathbf{I}_{3}&\\\ \end{bmatrix},\quad\
\begin{bmatrix}\mathbf{M}^{2}_{a}&\mathbf{M}^{2}_{b}&\cdots&\mathbf{M}^{2}_{b}&\mathbf{M}^{2}_{c}\\\
\mathbf{0}_{3\times 3}&&&&\\\ &&\ddots&&\\\ &&&\mathbf{0}_{3\times 3}&\\\
\end{bmatrix}$

respectively, with

$\displaystyle\mathbf{M}^{1}_{a}$ $\displaystyle=\begin{bmatrix}0&0&0\\\
0&1&0\\\ 2t&0&0\\\ \end{bmatrix},\ \
\quad\mathbf{M}^{2}_{a}=\begin{bmatrix}n\bar{\beta}q&n\bar{\beta}q&q\\\
n\bar{\beta}&-\eta^{n-1}m&n\\\ n\bar{\beta}t&n\bar{\beta}t&t\\\ \end{bmatrix}$
(16) $\displaystyle\mathbf{M}^{1}_{b}$ $\displaystyle=\begin{bmatrix}0&0&0\\\
0&0&0\\\ 2t&0&0\end{bmatrix},\ \
\quad\mathbf{M}^{2}_{b}=\begin{bmatrix}n\bar{\beta}q&n\bar{\beta}q&q\\\
0&0&0\\\ n\bar{\beta}t&n\bar{\beta}t&t\\\ \end{bmatrix}$
$\displaystyle\mathbf{M}^{1}_{c}$ $\displaystyle=\begin{bmatrix}r_{R}&0&0\\\
0&0&0\\\
2t&0&r_{P}\end{bmatrix},\quad\mathbf{M}^{2}_{c}=\begin{bmatrix}n\bar{\beta}q&n\bar{\beta}q&q\\\
0&0&0\\\ n\bar{\beta}t&n\bar{\beta}t&t\\\ \end{bmatrix}$ $\displaystyle t$
$\displaystyle={n^{2}\bar{\beta}Q_{P}}/{\eta^{n-1}},\quad
q=Q_{R}\sqrt{n},\quad m={\alpha_{F}}/{n}$

To establish the $R$-linear convergence of our algorithm, it is sufficient to
show that the spectral radius of $\mathbf{M}(\lambda)$ is less than $1$ when
$\lambda$ is small enough. To this end, we first prove that the spectral
radius of $\mathbf{M}^{1}$ is $1$, i.e., $\rho(\mathbf{M}^{1})=1$. Following
Theorem 3.2 in [31], the determinant of $z\mathbf{I}-\mathbf{M}^{1}$ is given
by
$\det(z\mathbf{I}-\mathbf{M}^{1})=(z^{\bar{N}}-r_{R})(z^{\bar{N}}-r_{P})(z-1)z^{\bar{N}-1}$.
Since $r_{R},r_{P}\in(0,\,1)$ holds, we have $\rho(\mathbf{M}^{1})=1$.
Moreover, the eigenvalue $1$ is simple, and its corresponding right and left
eigenvectors are $\mathbf{u}=\mathbf{1}_{\bar{N}}\otimes[0\ 1\ 0]^{T}$ and
$\mathbf{w}=[0\ 1\ 0\ \cdots\ 0]^{T}$, respectively. Denote the simple
eigenvalue of $\mathbf{M}(\lambda)$ as a function of $\lambda$, i.e.,
$p(\lambda)$. Given
$\mathbf{M}(\lambda)=\mathbf{M}^{1}+\lambda\mathbf{M}^{2}$, we have $p(0)=1$.
Using the matrix perturbation theory in Theorem 6.3.12 in [14], one can obtain
$\frac{dp(\lambda)}{d\lambda}\Big{|}_{\lambda=0}=\frac{\mathbf{w}^{T}\mathbf{M}^{2}\mathbf{u}}{\mathbf{w}^{T}\mathbf{u}}=-n^{-1}\eta^{n-1}\alpha_{F}<0$.
Since eigenvalues are continuous functions of the elements of a matrix, the
simple eigenvalue $p(\lambda)$ is strictly less than $1$ when $\lambda$ is
sufficiently small, implying that the spectral radius of $\mathbf{M}(\lambda)$
is less than $1$ when $\lambda$ is sufficiently small. Noting that
$\mathbf{M}(\lambda)$ has nonnegative entries and
$\mathbf{M}(\lambda)^{\bar{N}+1}$ has all positive entries, from Theorem 8.5.1
and Theorem 8.5.2 in [14], we can obtain that each entry of
$\mathbf{M}(\lambda)^{k}$ will converge to zero at the rate of
$\mathcal{O}(\rho(\mathbf{M}(\lambda))^{k})$. Therefore, when $\lambda$ is
sufficiently small, $\|\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}\|$
converges to $0$ at the rate of $\mathcal{O}(\rho(\mathbf{M}(\lambda))^{k})$,
implying that our algorithm has $R$-linear convergence. $\blacksquare$

######  Remark 2.

Although adding randomness in optimization parameters in the first $K$
iterations may delay the convergence of our algorithm (as shown in our
numerical simulations in Fig. 4), it has no influence on the $R$-linear
convergence rate. The added randomness in optimization parameters in the first
$K$ iterations is key to enable privacy protection, as elaborated in the
following subsection.

###  4.3 Privacy Analysis

To protect $f_{i}(\cdot)$, it suffices to protect the gradient function
$\nabla f_{i}(\cdot)$. In decentralized optimization, every participating node
receives messages from its neighbors, and hence could exploit them to infer
other nodes’ private gradients. We denote all information accessible to node
$j$ as $\mathcal{I}_{j}$, which contains the coupling weights, stepsizes, and
states associated with node $j$, sent information from node $j$ to its out-
neighbors, and received information from node $j$’s in-neighbors to itself. A
mathematical representation of $\mathcal{I}_{j}$ is given as follows:

$\displaystyle\mathcal{I}_{j}=$
$\displaystyle\big{\\{}\mathcal{I}_{j}^{\text{state}}(k)\cup\mathcal{I}_{j}^{\text{send}}(k)\cup\mathcal{I}_{j}^{\text{receive}}(k)\,\big{|}\,k=0,1,\ldots\big{\\}}$
(17)
$\displaystyle\cup\big{\\{}\boldsymbol{\Lambda}_{j}^{k},\mathbf{R}_{jj}^{k},\mathbf{A}_{jj}^{k},\mathbf{C}_{jj}^{k},\mathbf{B}_{jj}^{k}\big{|}\,k<K\big{\\}}$
$\displaystyle\cup\big{\\{}\mathbf{R}_{jl}^{k},\mathbf{A}_{jl}^{k}\big{|}\,k<K,\forall\,l\in\mathcal{N}_{j}^{in}\big{\\}}$
$\displaystyle\cup\big{\\{}\mathbf{C}_{mj}^{k},\mathbf{B}_{mj}^{k}\big{|}\,k<K,\forall\,m\in\mathcal{N}_{j}^{out}\big{\\}}$
$\displaystyle\cup\big{\\{}\boldsymbol{\Lambda}_{l}^{k},\mathbf{R}_{lm}^{k},\mathbf{A}_{lm}^{k},\mathbf{C}_{lm}^{k},\mathbf{B}_{lm}^{k}\big{|}\,k\geq
K,\forall\,l,m\in\mathcal{V}\big{\\}}$

where

$\displaystyle\mathcal{I}_{j}^{\text{state}}(k)=\big{\\{}\mathbf{x}_{j}^{k},\mathbf{y}_{j}^{k},\boldsymbol{\Lambda}_{j}^{k}\mathbf{y}_{j}^{k},\mathbf{C}_{jj}^{k}\mathbf{y}_{j}^{k}+\mathbf{B}_{jj}^{k}(\nabla
f_{j}^{k+1}-\nabla f_{j}^{k})\big{\\}}$ (18)
$\displaystyle\mathcal{I}_{j}^{\text{send}}(k)=\big{\\{}\mathbf{x}_{j}^{k},\boldsymbol{\Lambda}_{j}^{k}\mathbf{y}_{j}^{k},$
$\displaystyle\qquad\qquad\quad\mathbf{C}_{mj}^{k}\mathbf{y}_{j}^{k}+\mathbf{B}_{mj}^{k}(\nabla
f_{j}^{k+1}-\nabla
f_{j}^{k})\big{|}\,\forall\,m\in\mathcal{N}_{j}^{out}\big{\\}}$
$\displaystyle\mathcal{I}_{j}^{\text{receive}}(k)=\big{\\{}\mathbf{x}_{l}^{k},\boldsymbol{\Lambda}_{l}^{k}\mathbf{y}_{l}^{k},$
$\displaystyle\qquad\qquad\qquad\mathbf{C}_{jl}^{k}\mathbf{y}_{l}^{k}+\mathbf{B}_{jl}^{k}(\nabla
f_{l}^{k+1}-\nabla
f_{l}^{k})\big{|}\,\forall\,l\in\mathcal{N}_{j}^{in}\big{\\}}$

represent the respective state information, sent information, and received
information of node $j$ at iteration $k$.

Using the defined information set, we are in position to introduce the
attacker model and our definition of privacy.

######  Definition 4.

A node $j$ is called honest-but-curious if it follows all protocol steps
correctly but is curious and tries to infer the gradient functions of other
participating nodes using the information $\mathcal{I}_{j}$ accessible to
itself.

######  Definition 5.

For a decentralized network of $n$ nodes, the privacy of node $i$ is preserved
if honest-but-curious adversaries cannot distinguish the actual gradient
$\nabla f_{i}(\cdot)$ of node $i$ from an arbitrarily large variation of the
gradient $\nabla\tilde{f}_{i}(\cdot)=\nabla f_{i}(\cdot)+\boldsymbol{\delta}$
where $\boldsymbol{\delta}$ can be any vector in $\mathbb{R}^{d}$. That is to
say, there exist feasible coupling weights and step-sizes satisfying the
requirements in Table II that make the information accessible to honest-but-
curious adversaries exactly unchanged under arbitrary variations of node $i$’s
gradient, which results in the unidentifiability of node $i$’s actual
gradient.

Definition 5 means that an honest-but-curious adversary cannot even identify a
range for a private function’s values and thus is more stringent than the
privacy definition used in unobservability based approaches in [29, 1] which
define privacy as the inability of an adversary to uniquely determine a
protected value. Note that opacity has also been used to protect information
in discrete-event systems [39, 17], which was recently extended to continuous-
state dynamical systems [35]. In contrast to unobservability based approaches
which consider adversaries having access to the entire output and control
histories, opacity based approaches only consider adversaries having access to
snapshots of the output and the set of controls. So opacity based privacy is
weaker than unobservability based privacy [35], and hence is also weaker than
the privacy defined here. Furthermore, in contrast to unobservability and
opacity based approaches focusing on protecting some state values, we protect
participating nodes’ gradient function values over the entire domain (or
protecting both function types and function parameters), which is more
challenging.

Before analyzing the privacy-preserving performance of our proposed algorithm,
we first show that using deterministic parameters may easily cause privacy
breaches in existing decentralized algorithms. We take the
$\mathcal{A}\mathcal{B}$ algorithm in [45] as an example. In the
$\mathcal{A}\mathcal{B}$ algorithm, node $i$ updates its states
$\mathbf{x}_{i}^{k}$ and $\mathbf{y}_{i}^{k}$ as follows:

$\displaystyle\mathbf{x}_{i}^{k+1}$
$\displaystyle={\textstyle\sum_{j\in\mathcal{N}_{i}^{in}\cup\\{i\\}}}r_{ij}\mathbf{x}_{j}^{k}-\lambda\mathbf{y}_{i}^{k}$
(19) $\displaystyle\mathbf{y}_{i}^{k+1}$
$\displaystyle={\textstyle\sum_{j\in\mathcal{N}_{i}^{in}\cup\\{i\\}}}c_{ij}\big{(}\mathbf{y}_{j}^{k}+\nabla
f_{j}^{k+1}-\nabla f_{j}^{k}\big{)}$

At the initial iteration $k=0$, node $i$ computes $\mathbf{x}_{i}^{1}$ and
$\nabla f_{i}^{1}$, and then sends $c_{ji}\big{(}\mathbf{y}_{i}^{0}+\nabla
f_{i}^{1}-\nabla f_{i}^{0}\big{)}=c_{ji}\nabla f_{i}^{1}$ to its out-neighbor
$j$ where $\mathbf{y}_{i}^{0}=\nabla f_{i}^{0}$. At iteration $k=1$, node $i$
sends $\mathbf{x}_{i}^{1}$ to its out-neighbor $j$. Note that in [45], node
$i$ sets its corresponding coupling weights $c_{ji}$ as
$c_{ji}=1/(|\mathcal{N}_{i}^{out}|+1)$ where $|\mathcal{N}_{i}^{out}|$
represents the number of node $i$’s out-neighbors. As a result, using
$c_{ji}\nabla f_{i}^{1}$ obtained at $k=0$ and state $\mathbf{x}_{i}^{1}$
received at $k=1$, node $j$ can uniquely determine the gradient of node $i$ at
$\mathbf{x}_{i}^{1}$ as long as it knows the number of node $i$’s out-
neighbors. Therefore, only employing deterministic or constant parameters
makes the gradients of participating nodes easily inferable by their
respective neighboring nodes. Following a similar argument, one can also see
that other commonly used algorithms have the same issue of breaching
individual nodes’ privacy.

Next, we show that by adding randomness in interaction parameters, our
algorithm can protect the privacy of gradients. We consider two different
scenarios: 1) a single adversary acting on its own (i.e., without collusion
with other adversaries) and 2) multiple adversaries colluding with each other.

####  4.3.1 Non-colluding case

In this case, we assume that there are $1\leq q\leq n-1$ honest-but-curious
nodes which try to infer node $i$’s gradient function without sharing
information with each other.

######  Theorem 2.

In our decentralized optimization algorithm, the privacy of node $i$ can be
preserved if $|\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in}|\geq 2$ holds.

Proof: Our idea is based on the indistinguishability of $\nabla
f_{i}(\cdot)$’s arbitrary variations to any honest-but-curious node $j$.
According to Definitions 4 and 5, all the information available to node $j$ to
infer $\nabla f_{i}(\cdot)$ is $\mathcal{I}_{j}$ (cf. (17)), and we have to
prove that when $\nabla f_{i}(\cdot)$ is altered to
$\nabla\tilde{f}_{i}(\cdot)$ (could have an arbitrarily large difference from
$\nabla f_{i}(\cdot)$), the information accessible to node $j$, i.e.,
$\tilde{\mathcal{I}}_{j}$, could be exactly the same as $\mathcal{I}_{j}$ in
(17). Therefore, we only need to prove that there exists such
$\nabla\tilde{f}_{i}(\cdot)$ that makes
$\tilde{\mathcal{I}}_{j}=\mathcal{I}_{j}$ hold. Given
$|\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in}|\geq 2$, there must exist a
node $m\in\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in}$ such that $m\neq j$
holds. So we only need to show that there exist feasible parameters (coupling
weights and stepsizes satisfying the requirements in Table II) making
$\tilde{\mathcal{I}}_{j}=\mathcal{I}_{j}$ hold under
$\nabla\tilde{f}_{i}(\cdot)=\nabla f_{i}(\cdot)+\boldsymbol{\delta}$ and
$\nabla\tilde{f}_{m}(\cdot)=\nabla f_{m}(\cdot)-\boldsymbol{\delta}$ for any
$\boldsymbol{\delta}=[\delta_{1},\cdots,\delta_{d}]^{T}\in\mathbb{R}^{d}$.

We consider $m\in\mathcal{N}_{i}^{out}$ and $m\in\mathcal{N}_{i}^{in}$,
separately (note that if $m\in\mathcal{N}_{i}^{out}\cap\mathcal{N}_{i}^{in}$
holds, either of the considered cases can be used in the argument to draw a
same conclusion):

Case I: If $m\in\mathcal{N}_{i}^{out}$ holds, it can be proven that
$\tilde{\mathcal{I}}_{j}=\mathcal{I}_{j}$ holds for any
$\boldsymbol{\delta}\in\mathbb{R}^{d}$ under
$\nabla\tilde{f}_{i}(\cdot)=\nabla f_{i}(\cdot)+\boldsymbol{\delta}$,
$\nabla\tilde{f}_{m}(\cdot)=\nabla f_{m}(\cdot)-\boldsymbol{\delta}$, and the
following parameters

$\left\\{\begin{aligned}
&\mathbf{\tilde{\Lambda}}_{p}^{0}=\mathbf{\Lambda}_{p}^{0}\quad\forall\,p\in\mathcal{V}\setminus\\{i,\,m\\}\\\
&\tilde{\lambda}_{i}^{0}(l)=\lambda_{i}^{0}(l)\mathbf{y}_{i}^{0}[l]/(\mathbf{y}_{i}^{0}[l]+\delta_{l})\\\
&\tilde{\lambda}_{m}^{0}(l)=\lambda_{m}^{0}(l)\mathbf{y}_{m}^{0}[l]/(\mathbf{y}_{m}^{0}[l]-\delta_{l})\\\
&\tilde{\mathbf{R}}_{pq}^{0}=\mathbf{R}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\\\
&\tilde{\mathbf{A}}_{pq}^{0}=\mathbf{A}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\\\
&\tilde{\mathbf{C}}_{pq}^{0}=\mathbf{C}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\setminus\\{i,\,m\\}\\\
&\tilde{c}_{pi}^{0}(l)=c_{pi}^{0}(l)\mathbf{y}_{i}^{0}[l]/(\mathbf{y}_{i}^{0}[l]+\delta_{l})\quad\forall\,p\in\mathcal{V}\setminus\\{m\\}\\\
&\tilde{c}_{mi}^{0}(l)=(c_{mi}^{0}(l)\mathbf{y}_{i}^{0}[l]+\delta_{l})/(\mathbf{y}_{i}^{0}[l]+\delta_{l})\\\
&\tilde{c}_{pm}^{0}(l)=c_{pm}^{0}(l)\mathbf{y}_{m}^{0}[l]/(\mathbf{y}_{m}^{0}[l]-\delta_{l})\quad\forall\,p\in\mathcal{V}\setminus\\{m\\}\\\
&\tilde{c}_{mm}^{0}(l)=(c_{mm}^{0}(l)\mathbf{y}_{m}^{0}[l]-\delta_{l})/(\mathbf{y}_{m}^{0}[l]-\delta_{l})\\\
&\tilde{\mathbf{C}}_{pq}^{0}=\mathbf{C}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\\\
&\tilde{\mathbf{B}}_{pq}^{0}=\mathbf{B}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\\\
&\mathbf{\tilde{\Lambda}}_{p}^{k}=\mathbf{\Lambda}_{p}^{k}\quad\forall\,p\in\mathcal{V},\,k=1,2,\ldots\\\
&\tilde{\mathbf{R}}_{pq}^{k}=\mathbf{R}_{pq}^{k}\quad\forall\,p,q\in\mathcal{V},\,k=1,2,\ldots\\\
&\tilde{\mathbf{A}}_{pq}^{k}=\mathbf{A}_{pq}^{k}\quad\forall\,p,q\in\mathcal{V},\,k=1,2,\ldots\\\
&\tilde{\mathbf{C}}_{pq}^{k}=\mathbf{C}_{pq}^{k}\quad\forall\,p,q\in\mathcal{V},\,k=1,2,\ldots\\\
&\tilde{\mathbf{B}}_{pq}^{k}=\mathbf{B}_{pq}^{k}\quad\forall\,p,q\in\mathcal{V},\,k=1,2,\ldots\\\
\end{aligned}\right.$ (20)

where $l=1,\cdots,d$ and “$\setminus$” represents set subtraction.

Case II: If $m\in\mathcal{N}_{i}^{in}$ holds, it can be verified that
$\tilde{\mathcal{I}}_{j}=\mathcal{I}_{j}$ is true for any
$\boldsymbol{\delta}\in\mathbb{R}^{d}$ under
$\nabla\tilde{f}_{i}(\cdot)=\nabla f_{i}(\cdot)+\boldsymbol{\delta}$,
$\nabla\tilde{f}_{m}(\cdot)=\nabla f_{m}(\cdot)-\boldsymbol{\delta}$, and the
following parameters

$\left\\{\begin{aligned}
&\mathbf{\tilde{\Lambda}}_{p}^{0}=\mathbf{\Lambda}_{p}^{0}\quad\forall\,p\in\mathcal{V}\setminus\\{i,\,m\\}\\\
&\tilde{\lambda}_{i}^{0}(l)=\lambda_{i}^{0}(l)\mathbf{y}_{i}^{0}[l]/(\mathbf{y}_{i}^{0}[l]+\delta_{l})\\\
&\tilde{\lambda}_{m}^{0}(l)=\lambda_{m}^{0}(l)\mathbf{y}_{m}^{0}[l]/(\mathbf{y}_{m}^{0}[l]-\delta_{l})\\\
&\tilde{\mathbf{R}}_{pq}^{0}=\mathbf{R}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\\\
&\tilde{\mathbf{A}}_{pq}^{0}=\mathbf{A}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\\\
&\tilde{\mathbf{C}}_{pq}^{0}=\mathbf{C}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\setminus\\{i,\,m\\}\\\
&\tilde{c}_{pi}^{0}(l)=c_{pi}^{0}(l)\mathbf{y}_{i}^{0}[l]/(\mathbf{y}_{i}^{0}[l]+\delta_{l})\quad\forall\,p\in\mathcal{V}\setminus\\{m\\}\\\
&\tilde{c}_{ii}^{0}(l)=(c_{ii}^{0}(l)\mathbf{y}_{i}^{0}[l]+\delta_{l})/(\mathbf{y}_{i}^{0}[l]+\delta_{l})\\\
&\tilde{c}_{pm}^{0}(l)=c_{pm}^{0}(l)\mathbf{y}_{m}^{0}[l]/(\mathbf{y}_{m}^{0}[l]-\delta_{l})\quad\forall\,p\in\mathcal{V}\setminus\\{m\\}\\\
&\tilde{c}_{im}^{0}(l)=(c_{im}^{0}(l)\mathbf{y}_{m}^{0}[l]-\delta_{l})/(\mathbf{y}_{m}^{0}[l]-\delta_{l})\\\
&\tilde{\mathbf{C}}_{pq}^{0}=\mathbf{C}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\\\
&\tilde{\mathbf{B}}_{pq}^{0}=\mathbf{B}_{pq}^{0}\quad\forall\,p,q\in\mathcal{V}\\\
&\mathbf{\tilde{\Lambda}}_{p}^{k}=\mathbf{\Lambda}_{p}^{k}\quad\forall\,p\in\mathcal{V},\,k=1,2,\ldots\\\
&\tilde{\mathbf{R}}_{pq}^{k}=\mathbf{R}_{pq}^{k}\quad\forall\,p,q\in\mathcal{V},\,k=1,2,\ldots\\\
&\tilde{\mathbf{A}}_{pq}^{k}=\mathbf{A}_{pq}^{k}\quad\forall\,p,q\in\mathcal{V},\,k=1,2,\ldots\\\
&\tilde{\mathbf{C}}_{pq}^{k}=\mathbf{C}_{pq}^{k}\quad\forall\,p,q\in\mathcal{V},\,k=1,2,\ldots\\\
&\tilde{\mathbf{B}}_{pq}^{k}=\mathbf{B}_{pq}^{k}\quad\forall\,p,q\in\mathcal{V},\,k=1,2,\ldots\\\
\end{aligned}\right.$ (21)

where $l=1,\cdots,d$.

To see why the parameter setting in (20) can ensure
$\tilde{\mathcal{I}}_{j}=\mathcal{I}_{j}$ in the case
$m\in\mathcal{N}_{i}^{out}$, we consider $k=0$ and $k\geq 1$, separately.
Under the feasible parameters for $k=0$, it can be verified that the
information accessible to node $j$ at the initial iteration $k=0$ keeps
unchanged and the states of each node $p\in\mathcal{V}$ satisfy
$\mathbf{\tilde{x}}_{p}^{1}=\mathbf{x}_{p}^{1}$ and
$\mathbf{\tilde{y}}_{p}^{1}=\mathbf{y}_{p}^{1}$. Then by setting feasible
parameters for iterations $k\geq 1$ the same as the original ones without
gradient variations, it is apparent that the information accessible to node
$j$ keeps unchanged for iterations $k\geq 1$. Following a similar argument,
one can verify that the parameter setting in (21) can ensure
$\tilde{\mathcal{I}}_{j}=\mathcal{I}_{j}$ in the case
$m\in\mathcal{N}_{i}^{in}$.

In summary, we have $\tilde{\mathcal{I}}_{j}=\mathcal{I}_{j}$ for
$\nabla\tilde{f}_{i}(\cdot)=\nabla f_{i}(\cdot)+\boldsymbol{\delta}$ under any
$\boldsymbol{\delta}\in\mathbb{R}^{d}$, which means that node $j$ cannot
distinguish arbitrarily large variations on $\nabla f_{i}(\cdot)$ based on its
accessible information. Therefore, our proposed algorithm can protect the
privacy of node $i$ if $|\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in}|\geq 2$
holds. $\blacksquare$

######  Remark 3.

Note that if we view the feasible parameters as solutions to guaranteeing
$\tilde{\mathcal{I}}_{j}=\mathcal{I}_{j}$, then there exist infinitely many
solutions. The proof of Theorem 2 just provides one such solution.

Next we show that if the condition in Theorem 2 is not met, then the privacy
of node $i$ can be breached.

######  Theorem 3.

In our decentralized optimization algorithm, the privacy of node $i$ cannot be
preserved against node $j$ if node $j$ is the only in-neighbor and out-
neighbor of node $i$, i.e.,
$\mathcal{N}_{i}^{out}=\mathcal{N}_{i}^{in}=\\{j\\}$.

Proof: When $\mathcal{N}_{i}^{out}=\mathcal{N}_{i}^{in}=\\{j\\}$ holds, one
can get the dynamics of $\mathbf{y}_{i}^{k}$ from (3) as follows:

$\displaystyle\mathbf{y}_{i}^{k+1}$
$\displaystyle=\mathbf{C}_{ii}^{k}\mathbf{y}_{i}^{k}+\mathbf{B}_{ii}^{k}\big{(}\nabla
f_{i}^{k+1}-\nabla f_{i}^{k}\big{)}+\mathbf{C}_{ij}^{k}\mathbf{y}_{j}^{k}$
(22) $\displaystyle\qquad+\mathbf{B}_{ij}^{k}\big{(}\nabla f_{j}^{k+1}-\nabla
f_{j}^{k}\big{)}$

According to the parameter design in Table II, we have
$\mathbf{y}_{i}^{k}=\mathbf{C}_{ii}^{k}\mathbf{y}_{i}^{k}+\mathbf{C}_{ji}^{k}\mathbf{y}_{i}^{k}$
and $\nabla f_{i}^{k+1}-\nabla
f_{i}^{k}=(\mathbf{B}_{ii}^{k}+\mathbf{B}_{ji}^{k})(\nabla f_{i}^{k+1}-\nabla
f_{i}^{k})$ for $k\in\mathbb{Z}_{\geq 0}$ based on the facts
$\mathbf{C}_{ii}^{k}+\mathbf{C}_{ji}^{k}=\mathbf{I}_{d}$ and
$\mathbf{B}_{ii}^{k}+\mathbf{B}_{ji}^{k}=\mathbf{I}_{d}$. So we can rewrite
(22) as

$\displaystyle\mathbf{y}_{i}^{k+1}=$
$\displaystyle\mathbf{y}_{i}^{k}-\mathbf{C}_{ji}^{k}\mathbf{y}_{i}^{k}+(\nabla
f_{i}^{k+1}-\nabla f_{i}^{k})+\mathbf{C}_{ij}^{k}\mathbf{y}_{j}^{k}$ (23)
$\displaystyle-\mathbf{B}_{ji}^{k}(\nabla f_{i}^{k+1}-\nabla
f_{i}^{k})+\mathbf{B}_{ij}^{k}(\nabla f_{j}^{k+1}-\nabla f_{j}^{k})$

Denote $\mathbf{m}_{j}^{k}$ as

$\displaystyle\mathbf{m}_{j}^{k}$
$\displaystyle=-\mathbf{C}_{ji}^{k}\mathbf{y}_{i}^{k}+\mathbf{C}_{ij}^{k}\mathbf{y}_{j}^{k}-\mathbf{B}_{ji}^{k}(\nabla
f_{i}^{k+1}-\nabla f_{i}^{k})$ (24)
$\displaystyle\qquad+\mathbf{B}_{ij}^{k}(\nabla f_{j}^{k+1}-\nabla f_{j}^{k})$

Note that $\mathbf{m}_{j}^{k}$ is accessible to the honest-but-curious node
$j$ because $\mathbf{C}_{ji}^{k}\mathbf{y}_{i}^{k}+\mathbf{B}_{ji}^{k}(\nabla
f_{i}^{k+1}-\nabla f_{i}^{k})$ is the information node $i$ sends to node $j$,
and $\mathbf{C}_{ij}^{k}\mathbf{y}_{j}^{k}+\mathbf{B}_{ij}^{k}(\nabla
f_{j}^{k+1}-\nabla f_{j}^{k})$ is the information computed by node $j$.
Plugging (24) into (23), node $j$ can obtain
$\mathbf{y}_{i}^{k+1}-\mathbf{y}_{i}^{k}=\nabla f_{i}^{k+1}-\nabla
f_{i}^{k}+\mathbf{m}_{j}^{k}$ and further (note $\mathbf{y}_{i}^{0}=\nabla
f_{i}^{0}$)

$\displaystyle\mathbf{y}_{i}^{k+1}=\nabla
f_{i}^{k+1}+{\textstyle\sum_{l=0}^{k}}\mathbf{m}_{j}^{l}$ (25)

Since $\lim_{k\rightarrow\infty}\mathbf{y}_{i}^{k+1}=\mathbf{0}_{d}$ holds as
$k$ goes to infinity, we have $\lim_{k\rightarrow\infty}\nabla
f_{i}^{k+1}=\lim_{k\rightarrow\infty}\nabla
f_{i}(\mathbf{x}_{i}^{k+1})=-\lim_{k\rightarrow\infty}\sum_{l=0}^{k}\mathbf{m}_{j}^{l}$.
Given
$\lim_{k\rightarrow\infty}\mathbf{x}_{i}^{k+1}=\lim_{k\rightarrow\infty}\mathbf{x}_{j}^{k+1}$
$=\mathbf{x}^{*}$, node $j$ also knows
$\lim_{k\rightarrow\infty}\mathbf{x}_{i}^{k+1}$, meaning that an honest-but-
curious node $j$ can infer the gradient of node $i$ at the global optimal
solution $\mathbf{x}^{*}$ using (25). Therefore, the privacy of node $i$
cannot be preserved against node $j$ when node $j$ is the only in-neighbor and
out-neighbor of node $i$. $\blacksquare$

####  4.3.2 Colluding case

When a set of honest-but-curious nodes $\mathcal{A}$ collude, they can share
information with each other to infer node $i$’s gradient function.

######  Theorem 4.

In our decentralized optimization algorithm, the privacy of node $i$ can be
preserved against a set of honest-but-curious nodes $\mathcal{A}$ if
$(\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in})\not\subset\mathcal{A}$ holds,
i.e., there exits at least one node that belongs to
$\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in}$ but not $\mathcal{A}$.

Proof: To show that the privacy of node $i$ can be preserved, we have to show
that no honest-but-curious node $j\in\mathcal{A}$ can distinguish arbitrary
variations on $\nabla f_{i}(\cdot)$. In the colluding case, each node in
$\mathcal{A}$ has access to the information accessible to any node in
$\mathcal{A}$. So we represent the set of accessible information as

$\displaystyle\mathcal{I_{A}}=\big{\\{}\mathcal{I}_{j}\,\big{|}\,\forall\,j\in\mathcal{A}\big{\\}}$
(26)

where $\mathcal{I}_{j}$ is given by (17). Following the same line of reasoning
in Theorem 2, to prove that node $j\in\mathcal{A}$ cannot distinguish
arbitrary variations on $\nabla f_{i}(\cdot)$, it suffices to prove when
$\nabla f_{i}(\cdot)$ is altered to $\nabla\tilde{f}_{i}(\cdot)$ with any
$\boldsymbol{\delta}\in\mathbb{R}^{d}$, the information accessible to the set
of nodes in $\mathcal{A}$, i.e., $\tilde{\mathcal{I}}_{\mathcal{A}}$, could be
exactly the same as $\mathcal{I_{A}}$ in (26).

If $(\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in})\not\subset\mathcal{A}$ is
true, there must exist a node
$m\in\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in}$ such that
$m\notin\mathcal{A}$ holds. It can be verified that under
$\nabla\tilde{f}_{i}(\cdot)=\nabla f_{i}(\cdot)+\boldsymbol{\delta}$ and
$\nabla\tilde{f}_{m}(\cdot)=\nabla f_{m}(\cdot)-\boldsymbol{\delta}$, there
exist respective feasible parameters in (20) (for the case
$m\in\mathcal{N}_{i}^{out}$) and (21) (for the case
$m\in\mathcal{N}_{i}^{in}$) that satisfy the requirements in Table II and make
$\tilde{\mathcal{I}}_{\mathcal{A}}=\mathcal{I_{A}}$ hold under any
$\boldsymbol{\delta}\in\mathbb{R}^{d}$. Therefore, our proposed algorithm can
preserve the privacy of node $i$ against the set of honest-but-curious nodes
$\mathcal{A}$ if
$(\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in})\not\subset\mathcal{A}$ holds.
$\blacksquare$

Next we show that if the condition in Theorem 4 is not met, then the privacy
of node $i$ can be breached.

######  Theorem 5.

In our decentralized optimization algorithm, the privacy of node $i$ cannot be
preserved when all the in-neighbors and out-neighbors belong to $\mathcal{A}$,
i.e., $(\mathcal{N}_{i}^{out}\cup\mathcal{N}_{i}^{in})\subset\mathcal{A}$.

Proof: Following a similar line of reasoning for Theorem 3, Theorem 5 can be
easily obtained and hence we omit the proof here. $\blacksquare$

######  Remark 4.

It is worth noting that even using time-varying parameters, the $\mathcal{AB}$
algorithm cannot guarantee the privacy defined in Definition 5. This is
because the $\mathcal{AB}$ algorithm does not allow negative coupling weights,
leading to no feasible solutions for the parameters required in (20) and (21),
which are necessary to make adversaries’ accessible information unchanged
under arbitrary variations on the gradient.

######  Remark 5.

From Theorem 1, one can see that the parameter $K$ does not affect
optimization accuracy. Furthermore, from (20) and (21), we can see that only
changing the coupling weights/stepsizes in the initial iteration $k=0$ is
enough to cover gradient variations. In other words, any $K\geq 1$ is
sufficient to protect the defined privacy for gradients. However, a larger $K$
does provide additional privacy protection to more intermediate states, if the
privacy of intermediate states is of concern. This is because each node $i$
sends $\mathbf{\Lambda}_{i}^{k}\mathbf{y}_{i}^{k}$ and
$\mathbf{C}_{ji}^{k}\mathbf{y}_{i}^{k}+\mathbf{B}_{ji}^{k}\big{(}\nabla
f_{i}(\mathbf{x}_{i}^{k+1})-\nabla f_{i}(\mathbf{x}_{i}^{k})\big{)}$ to its
out-neighbors $j\in\mathcal{N}_{i}^{out}$. In the first $K$ iterations, as
randomness is injected into the coupling weights ($\mathbf{C}_{ji}^{k}$ and
$\mathbf{B}_{ji}^{k}$) and stepsizes ($\mathbf{\Lambda}_{i}^{k}$), the
intermediate states $\mathbf{y}_{i}^{k}$ and $\nabla
f_{i}(\mathbf{x}_{i}^{k+1})-\nabla f_{i}(\mathbf{x}_{i}^{k})$ are uninferable
by receiving nodes (note that in our algorithm $\mathbf{x}_{i}^{0}$ is
randomly initialized in $\mathbb{R}^{d}$ and hence does not carry sensitive
information). Therefore, if intermediate states in the first $M$ iterations
need to be protected, we can set $K$ to $M$ to achieve this goal without
compromising accuracy (note that the gradient will always be protected for any
$K\geq 1$). It is also worth noting that although the randomness added in the
first $K$ iterations does not affect the convergence rate (as proven in
Theorem 1), it does delay the convergence since the algorithm only starts to
converge after iteration $K$ (see Fig. 4). Of course, if the privacy of
intermediate states is not of concern and only gradients need to be protected,
it is preferable to set $K=1$ to minimize the delay in the convergence
process.

######  Remark 6.

In the case where an adversary has side information such as a range of
coefficients of the objective function, we cannot prove the adversary’s
inability to distinguish $\nabla f_{i}(x_{i})$ from
$\nabla\tilde{f}_{i}(x_{i})=\nabla f_{i}(x_{i})+\boldsymbol{\delta}$ under an
arbitrary $\boldsymbol{\delta}$. Although it is difficult to quantify the
influence of side information (e.g., a certain range of parameters) on enabled
privacy due to possible complicated ways that the side information can affect
the gradient, we can show that in specific cases, such as in the rendezvous
problem, the adversary’s side information on parameter range could not be
tightened after running the algorithm. For the sake of simple exposition, we
consider the one-dimensional rendezvous problem. Each node $i$ has a local
objective function $f_{i}(x_{i})=\frac{1}{2}(x_{i}-p_{i})^{2}$. The gradient
function of node $i$ is $\nabla f_{i}(x_{i})=x_{i}-p_{i}$. Following our
analysis in Theorem 2 and Theorem 4, the privacy of node $i$ can be preserved
if it has an in-neighbor or out-neighbor not colluding with the adversarial
node, i.e., the adversary cannot distinguish whether the gradient function of
node $i$ is $\nabla f_{i}(x_{i})=x_{i}-p_{i}$ or
$\nabla\tilde{f}_{i}(x_{i})\triangleq x_{i}-p_{i}+\delta=x_{i}-\tilde{p}_{i}$
($\tilde{p}_{i}\triangleq p_{i}-\delta$) under any $\delta$ in $\mathbb{R}$.
If the adversary has side information of the function type (i.e., quadratic)
and parameter range $p_{i}\in[a,b]$, then the range of $\delta$ has to be
reduced to $[p_{i}-b,p_{i}-a]$. This is because otherwise $\tilde{p}_{i}$ in
$\nabla\tilde{f}_{i}(x_{i})$ will not be within the initial range $[a,b]$
known to the adversary. However, for any $\delta\in[p_{i}-b,p_{i}-a]$ (i.e.,
$\tilde{p}_{i}\in[a,b]$), following our analysis in Theorem 2 and Theorem 4,
there always exist feasible parameters making all information known to the
adversarial node under $\nabla\tilde{f}_{i}(x_{i})$ exactly the same as under
$\nabla f_{i}(x_{i})$. Therefore, the adversarial node cannot distinguish
$\nabla f_{i}(x_{i})$ from $\nabla\tilde{f}_{i}(x_{i})$ for any
$\delta\in[p_{i}-b,p_{i}-a]$, meaning that the adversarial node cannot get a
tighter range of $p_{i}$ than the initial knowledge (i.e., $[a,b]$) after
running the algorithm.

######  Remark 7.

Our approach can be extended to enable privacy against adversaries wiretapping
all communication links without compromising algorithmic accuracy by patching
partially homomorphic encryption. For example, in our prior work [50] and
[52], we can let each node generate and flood its public key before the
optimization iteration starts. Then in decentralized implementation, a node
encrypts its messages to be sent, which can be decrypted by a legitimate
recipient without the help of any third party.

##  5 Numerical Simulations

###  5.1 Privacy Protection in the Rendezvous Problem

First let’s consider the distributed rendezvous problem where a group of nodes
want to agree on the nearest meeting point without revealing each other’s
initial position [15]. Mathematically this can be modeled as the problem
$\min_{x\in\mathbb{R}^{d}}\,\
F(\mathbf{x})=\sum_{i=1}^{n}f_{i}(\mathbf{x})=\sum_{i=1}^{n}\frac{1}{2}\|\mathbf{x}-\mathbf{p}_{i}\|^{2}$,
where $\mathbf{p}_{i}$ represents the initial position of node $i$.

For the simplicity of exposition, we consider the $d=1$ case but similar
results can be obtained when $d\neq 1$. We consider three nodes connected in a
directed cycle as shown in Fig. 1 (a). Let node $3$ be an honest-but-curious
node which collects received data in an attempt to learn the gradient function
of node $1$. Node $2$ does not collude with node $3$. Parameter $K$ was set to
$3$. In the simulation, we first ran our algorithm and recorded
$\mathcal{I}_{3}$, the information accessible to node $3$ (cf. (17)). Then we
show that information accessible to node $3$ can be exactly the same under a
completely different gradient function $\nabla\tilde{f}_{1}(\mathbf{x}_{1})$.

We represent the information accessible to node $3$ in the new implementation
as $\tilde{\mathcal{I}}_{3}$. Fig. 2 shows $\mathbf{x}_{1}^{k}$,
$\mathbf{\Lambda}_{1}^{k}\mathbf{y}_{1}^{k}$, and
$\mathbf{C}_{31}^{k}\mathbf{y}_{1}^{k}+\mathbf{B}_{31}^{k}(\nabla
f_{1}^{k+1}-\nabla f_{1}^{k})$ in $\mathcal{I}_{3}$ and
$\tilde{\mathbf{x}}_{1}^{k}$,
$\mathbf{\tilde{\Lambda}}_{1}^{k}\tilde{\mathbf{y}}_{1}^{k}$, and
$\mathbf{\tilde{C}}_{31}^{k}\tilde{\mathbf{y}}_{1}^{k}+\mathbf{\tilde{B}}_{31}^{k}(\nabla\tilde{f}_{1}^{k+1}-\nabla\tilde{f}_{1}^{k})$
in $\tilde{\mathcal{I}}_{3}$, respectively. It can be seen that the trajectory
of the observations of node $3$ in both cases are identical. Fig. 3 shows the
corresponding $\nabla f_{1}(\mathbf{x}_{1})$ and
$\nabla\tilde{f}_{1}(\mathbf{x}_{1})$, which are clearly different. Since node
$3$ receives the same information under
$\nabla\tilde{f}_{1}(\mathbf{x}_{1})\neq\nabla f_{1}(\mathbf{x}_{1})$, it has
no way to infer the real gradient function of node $1$.

Figure 1: Graphs used in simulations: (a) a directed cycle graph with $3$
nodes; (b) a strongly connected graph with $5$ nodes. Figure 2: The
information accessible to node $3$ are the same under two different gradient
functions of node $1$ depicted in Fig. 3. Figure 3: The two different gradient
functions of node $1$ that lead to identical observations at node $3$.

###  5.2 Distributed Estimation Problem

In this subsection we focus on the convergence performance of our algorithm
and compare our algorithm with other decentralized optimization algorithms. We
consider the canonical distributed estimation problem
$\min_{\begin{subarray}{c}\mathbf{x}\in\mathbb{R}^{d}\end{subarray}}\,\
F(\mathbf{x})=\sum_{i=1}^{n}\big{(}\|\mathbf{z}_{i}-\mathbf{Q}_{i}\mathbf{x}\|^{2}+\sigma_{i}\|\mathbf{x}\|^{2}\big{)}$
in [47], where $n$ nodes cooperatively measure a certain unknown parameter
$\mathbf{x}\in\mathbb{R}^{d}$. In this problem, each node $i$ has access to
its local cost function
$f_{i}(\mathbf{x}_{i})=\|\mathbf{z}_{i}-\mathbf{Q}_{i}\mathbf{x}_{i}\|^{2}+\sigma_{i}\|\mathbf{x}_{i}\|^{2}$
with $\mathbf{Q}_{i}\in\mathbb{R}^{s\times d}$ being its measurement matrix
and $\mathbf{z}_{i}\in\mathbb{R}^{s}$ being its measurement data. The
regularization parameter $\sigma_{i}$ can be set to $0$ (resp. a positive
value) to make $f_{i}$ general convex (resp. strongly convex) under
appropriate $\mathbf{Q}_{i}$.

We considered a network of $n=5$ nodes interacting on a strongly connected
graph illustrated in Fig. 1 (b). Dimension parameters $d$ and $s$ were set to
$2$ and $3$, respectively. Parameter $K$ was set to $3$.

####  5.2.1 Comparison with Other Decentralized Optimization Algorithms

We compared our algorithm with DIGing [25], $\mathcal{A}\mathcal{B}$ [45],
ADD-OPT [44], and Subgradient-Push [27] to evaluate the influence of privacy
design on optimization performance. The stepsize was set to $0.06$ for all of
the considered algorithms except Subgradient-Push whose stepsize was set to a
diminishing sequence $\lambda^{k}=1/k$. The simulation results on optimization
error $\|\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}\|$ are depicted in
Fig. 4.

From Fig. 4, it can be seen that all algorithms with a fixed stepsize had
$R$-linear convergence, including our algorithm with guaranteed privacy. This
corroborates our statement in Remark 2 that the added randomness has no
influence on the $R$-linear convergence of our algorithm. Of course, it is
worth noting that in our algorithm, the privacy-induced randomness delayed
convergence to iteration step $k\geq 4$.

Figure 4: Comparison of convergence rates of different optimization
algorithms.

####  5.2.2 Comparison with [15]

We also compared our algorithm with the differential privacy based privacy-
preserving approach for decentralized optimization proposed in [15]. We ran
the algorithm in [15] under four different privacy levels, i.e.,
$\epsilon=0.1,1,10,100$, respectively. The domain of optimization in [15] was
set to $\mathcal{X}=\\{\mathbf{x}\in\mathbb{R}^{2}|\|\mathbf{x}\|\leq 10\\}$.
Note that the optimal solution $\mathbf{x}^{*}=[0.6881,\,0.5103]^{T}$ resides
in $\mathcal{X}$. For each privacy level $\epsilon$, we repeated the
simulation for $1,000$ times, and averaged the optimization error
trajectories. Under a stepsize $0.06$, we also measured the mean optimization
error of our algorithm over $1,000$ repetitions. The comparison results in
Fig. 5 confirm the trade-off between privacy and accuracy for differential-
privacy based approaches and demonstrate the advantage of our algorithm in
ensuring optimization accuracy.

Figure 5: Comparison of mean optimization error over $1,000$ repetitions
between our algorithm and the differential-privacy based approach in [15].

####  5.2.3 Comparison with [19]

Then we compared our algorithm with the privacy-preserving optimization
algorithm in [19]. The closed convex projection set $\mathcal{X}$ was set to
$\mathcal{X}=\\{\mathbf{x}\in\mathbb{R}^{2}|\|\mathbf{x}\|\leq 10\\}$ for the
algorithm in [19]. The other parameters for the algorithm in [19] were set as
follows: each node $i$ randomly chose $c_{i}$ from $(0,\,5)$, and updated its
state with its subgradient once every $T_{i}$ iterations where $T_{i}$ was
randomly chosen from $\\{1,2,3,4,5\\}$. The stepsize of our algorithm was set
to $0.06$. The results are shown in Fig. 6. Clearly our algorithm has a
$R$-linear convergence whereas the convergence rate of [19] is much slower.

Figure 6: Comparison of optimization error
$\|\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}\|$ between our algorithm
and the algorithm in [19].

####  5.2.4 Numerical Simulations on Large-scale Networks

Finally, we conducted numerical simulations to verify the scalability of our
proposed algorithm using a network of $n=100$ nodes. Each agent $i$ was
assumed to have two out-neighbors, i.e.,
$\mathcal{N}_{i}^{out}=\left\\{\overline{i}+1,\,\overline{i+1}+1\right\\}$,
where the superscript “$\bar{\quad}$” represents modulo operation on $n$,
i.e., $\overline{i}\triangleq i\mod n$. The evolution of optimization error
$\|\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}\|$ is shown in Fig. 7.
It can be seen that the convergence rate is still linear, meaning that our
proposed algorithm can guarantee the convergence of all nodes to the global
optimal solution even when the network size is large.

Figure 7: The optimization error trajectory of our algorithm in a network of
$n=100$ nodes.

##  6 Conclusions

In this paper we proposed a dynamics based privacy approach for decentralized
optimization. Our approach can enable privacy without compromising
optimization accuracy or incurring heavy computation/communication overhead.
This is in distinct difference from differential-privacy based approaches
which compromise optimization accuracy and encryption based approaches which
incur heavy computation/communication overhead. We rigorously characterized
the convergence properties of our algorithm and its privacy-preserving
performance. In addition, to facilitate the privacy design, we also proposed a
general framework of gradient-tracking based decentralization optimization,
which includes many commonly used algorithms as special cases. Finally, we
provided numerical simulation results to confirm the effectiveness and
efficiency of our proposed algorithm.

## Appendix A: Absolute Probability Sequence

######  Definition 6.

[38] Let $\\{\mathbf{A}^{k}\\}$ be a sequence of row-stochastic matrices. A
sequence of vectors $\\{\boldsymbol{\pi}^{k}\\}$ is an absolute probability
sequence for $\\{\mathbf{A}^{k}\\}$ if
$(\boldsymbol{\pi}^{k})^{T}=(\boldsymbol{\pi}^{k+1})^{T}\mathbf{A}^{k}$ holds
for $k\geq 0$.

######  Definition 7.

[40] A sequence of row-stochastic matrices $\\{\mathbf{A}^{k}\\}$ is ergodic
if the following limit exists for $k\geq 0$

$\displaystyle\lim\limits_{t\rightarrow\infty}\mathbf{A}^{t}\mathbf{A}^{t-1}\cdots\mathbf{A}^{k+1}\mathbf{A}^{k}=\mathbf{1}(\boldsymbol{\pi}^{k})^{T}$
(27)

where $\\{\boldsymbol{\pi}^{k}\\}$ is an absolute probability sequence for
$\\{\mathbf{A}^{k}\\}$.

For the absolute probability sequences $\\{\mathbf{v}^{k}\\}$ and
$\\{\boldsymbol{\phi}^{k}\\}$ (associated with $\\{\mathbf{\bar{P}}^{k}\\}$
and $\\{\mathbf{\bar{R}}^{k}\\}$, respectively) in Sec. 4.2, we have the
following lemmas.

######  Lemma 4.

Under Assumptions 1 and 2, and the parameter design in Table II, the sequence
of matrices $\\{\mathbf{\bar{P}}^{k}\\}$ for $k\geq K$ is row-stochastic and
ergodic, and the sequence $\\{\mathbf{v}^{k}\\}$ is the unique absolute
probability sequence for $\\{\mathbf{\bar{P}}^{k}\\}$. Denote $Q_{P}$ as
$Q_{P}=2n(1+(n\eta^{-n})^{n-1})/(1-(n^{-1}\eta^{n})^{n-1})$ and define a
positive integer $N_{P}$ such that $r_{P}\triangleq
Q_{P}(1-(n^{-1}\eta^{n})^{n-1})^{\frac{N_{P}-1}{n-1}}<1$ holds. Then for any
$k\geq K+N_{P}-1$ and any vector $\mathbf{b}\in\mathbb{R}^{nd}$, vector
$\mathbf{a}\triangleq\mathbf{P}^{k}\mathbf{P}^{k-1}\cdots\mathbf{P}^{k-N_{P}+1}\mathbf{b}$
always satisfies
$\|[(\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k+1})^{T})\otimes\mathbf{I}_{d}]\mathbf{a}\|\leq
r_{P}\|[(\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k-N_{P}+1})^{T})\otimes\mathbf{I}_{d}]\mathbf{b}\|$.

Proof: Given
$\mathbf{\bar{P}}^{k}=(\mathbf{\bar{V}}^{k+1})^{-1}\mathbf{\bar{C}}^{k}\mathbf{\bar{V}}^{k}$,
it can be verified that $\mathbf{\bar{P}}^{k}$ is row-stochastic since
$\sum_{j=1}^{n}p_{ij}^{k}=1$ holds for all $i=1,\cdots,n$. Using Lemma 4 in
[26], we can see that the sequence of matrices $\\{\mathbf{\bar{P}}^{k}\\}$
for $k\geq K$ is ergodic since the limit in (27) exists under Assumptions 1
and 2, and the parameter design in Table II. Combing
$\mathbf{\bar{V}}^{k}=\text{diag}(\mathbf{v}^{k})$ and
$\mathbf{\bar{P}}^{k}=(\mathbf{\bar{V}}^{k+1})^{-1}\mathbf{\bar{C}}^{k}\mathbf{\bar{V}}^{k}$
leads to $(\mathbf{v}^{k})^{T}=(\mathbf{v}^{k+1})^{T}\mathbf{\bar{P}}^{k}$ for
$k\geq K$, meaning that $\\{\mathbf{v}^{k}\\}$ is the absolute probability
sequences for $\\{\mathbf{\bar{P}}^{k}\\}$. Further using Lemma 1 in [23], we
have that $\\{\mathbf{v}^{k}\\}$ is the unique absolute probability sequence
for $\\{\mathbf{\bar{P}}^{k}\\}$ due to the ergodicity of
$\\{\mathbf{\bar{P}}^{k}\\}$.

Now we show that the positive entries of $\mathbf{\bar{P}}^{k}$ has a lower
bound $\eta^{n}/n$, i.e., $p_{ij}^{k}\geq\eta^{n}/n$ for any
$j\in\mathcal{N}_{I}^{out}\cup\\{i\\}$ where $p_{ij}^{k}$ represents the
$ij$-th entry of $\mathbf{\bar{P}}^{k}$. To this end, we first prove that all
entries of $\mathbf{v}^{k}$ have a lower bound $\eta^{n-1}/n$, i.e.,
$v_{i}^{k}\geq\eta^{n-1}/n$ for $i=1,\cdots,n$ and $k\geq K$. Denoting
$\mathbf{\bar{C}}_{k:K}$ as
$\mathbf{\bar{C}}_{k:K}=\mathbf{\bar{C}}^{k}\cdots\mathbf{\bar{C}}^{K}$, from
(9) we have

$\displaystyle\mathbf{v}^{k}=\mathbf{\bar{C}}_{k-1:K}\mathbf{v}^{K}=\mathbf{\bar{C}}_{k-1:K}\mathbf{1}_{n}/{n}$
(28)

for $k\geq K$. Then we divide the proof into two parts: $K\leq k\leq K+n-1$
and $k\geq K+n$, respectively.

Part 1: $v_{i}^{k}\geq\eta^{n-1}/n$ for $K\leq k\leq K+n-1$. Given
$c_{ii}^{k}\geq\eta$ for $k\geq K$, one can verify that the inequality
$v_{i}^{k}\geq\frac{1}{n}[\mathbf{\bar{C}}_{k-1:K}]_{ii}\geq\eta^{k-K}/n\geq{\eta^{n-1}}/{n}$
holds for $i=1,\cdots,n$ and $K\leq k\leq K+n-1$.

Part 2: $v_{i}^{k}\geq\eta^{n-1}/n$ for $k\geq K+n$. Under Assumptions 1 and
2, and the parameter design in Table II, following the arguments in Lemma 2 in
[26], we can obtain $[\mathbf{\bar{C}_{k-1:k-n+1}}]_{ij}\geq\eta^{n-1}$ for
$i,j=1,\cdots,n$. Since $\mathbf{\bar{C}}^{k}$ is column-stochastic,
$\mathbf{\bar{C}}_{k-n:K}$ is also column-stochastic. Further using the fact
$\mathbf{\bar{C}}_{k-1:K}=\mathbf{\bar{C}}_{k-1:K-n+1}\mathbf{\bar{C}}_{k-n:K}$
yields $[\mathbf{\bar{C}}_{k-1:K}]_{ij}\geq\eta^{n-1}$ for $i,j=1,\cdots,n$.
Therefore, we have
$v_{i}^{k}={1}/{n}\sum_{j=1}^{n}[\mathbf{\bar{C}}_{k-1:K}]_{ij}\geq\eta^{n-1}\geq{\eta^{n-1}}/{n}$
for $i=1,\cdots,n$ and $k\geq K+n$.

In summary, we have $v_{i}^{k}\geq\eta^{n-1}/n$ for $i=1,\cdots,n$ and $k\geq
K$. Since $\mathbf{\bar{C}}_{k-1:K}$ is column-stochastic, it follows
naturally from (28) that
$\mathbf{1}_{n}^{T}\mathbf{v}^{k}=\sum_{i=1}^{n}v_{i}^{k}=1$ holds for $k\geq
K$, which implies $v_{i}^{k}\in[\eta^{n-1}/n,1]$ for $i=1,\cdots,n$ and $k\geq
K$.

Given
$\mathbf{\bar{P}}^{k}=(\mathbf{\bar{V}}^{k+1})^{-1}\mathbf{\bar{C}}^{k}\mathbf{\bar{V}}^{k}$,
we have $p_{ij}^{k}=c_{ij}^{k}{v_{j}^{k}}/{v_{i}^{k+1}}$. Further using
$v_{i}^{k}\in[\eta^{n-1}/n,1]$, we have $p_{ij}^{k}\geq\eta^{n}/n$ for
$j\in\mathcal{N}_{I}^{out}\cup\\{i\\}$ and $p_{ij}^{k}=0$ for
$j\notin\mathcal{N}_{I}^{out}\cup\\{i\\}$.

Denote $\mathbf{P}_{t:k}$ as
$\mathbf{P}_{t:k}=\mathbf{P}^{t}\mathbf{P}^{t-1}\cdots\mathbf{P}^{k}$, one can
obtain

$\displaystyle[(\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k+1})^{T})\otimes\mathbf{I}_{d}]\mathbf{P}_{k:k-N_{P}+1}$
$\displaystyle=[(\mathbf{\bar{P}}_{k:k-N_{P}+1}-\mathbf{1}_{n}(\mathbf{v}^{k-N_{P}+1})^{T})(\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k-N_{P}+1})^{T})]$
$\displaystyle\quad\otimes\mathbf{I}_{d}$

Therefore, following Lemma 4 in [26], we have

$\displaystyle\|[(\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k+1})^{T})\otimes\mathbf{I}_{d}]\mathbf{a}\|$
$\displaystyle\leq\|(\mathbf{\bar{P}}_{k:k-N_{P}+1}-\mathbf{1}_{n}(\mathbf{v}^{k-N_{P}+1})^{T})\otimes\mathbf{I}_{d}\|$
$\displaystyle\quad\
\cdot\|[(\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k-N_{P}+1})^{T})\otimes\mathbf{I}_{d}]\mathbf{b}\|$
$\displaystyle\leq
r_{P}\|[(\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k-N_{P}+1})^{T})\otimes\mathbf{I}_{d}]\mathbf{b}\|$

for any $k\geq K+N_{P}-1$ and any vector $\mathbf{b}\in\mathbb{R}^{nd}$.
$\blacksquare$

######  Lemma 5.

Under Assumptions 1 and 2, and the parameter design in Table II, the sequence
of row-stochastic matrices $\\{\mathbf{\bar{R}}^{k}\\}$ for $k\geq K$ is
ergodic, and $\\{\boldsymbol{\phi}^{k}\\}$ is the unique absolute probability
sequence for $\\{\mathbf{\bar{R}}^{k}\\}$. Denote $Q_{R}$ as
$Q_{R}=2n(1+\eta^{-(n-1)})/(1-\eta^{n-1})$ and define a positive integer
$N_{R}$ such that $r_{R}\triangleq
Q_{R}(1-\eta^{n-1})^{\frac{N_{R}-1}{n-1}}<1$ holds. Then for any $k\geq
K+N_{R}-1$ and any vector $\mathbf{b}\in\mathbb{R}^{nd}$, vector
$\mathbf{a}\triangleq\mathbf{R}^{k}\mathbf{R}^{k-1}\cdots\mathbf{R}^{k-N_{R}+1}\mathbf{b}$
always satisfies
$\|[(\mathbf{I}_{n}-\mathbf{1}_{n}(\boldsymbol{\phi}^{k+1})^{T})\otimes\mathbf{I}_{d}]\mathbf{a}\|\leq
r_{R}\|[(\mathbf{I}_{n}-\mathbf{1}_{n}(\boldsymbol{\phi}^{k-N_{R}+1})^{T})\otimes\mathbf{I}_{d}]\mathbf{b}\|$.

Proof: Following a similar line of reasoning for Lemma 4, Lemma 5 can be
easily obtained and hence we omit the proof here. $\blacksquare$

## Appendix B: Proof of Lemma 1

Proof: From (8), we have
$\mathbf{x}^{k+1}=\mathbf{R}_{k:k-\bar{N}+1}\mathbf{x}^{k-\bar{N}+1}-\lambda(\mathbf{A}^{k}\mathbf{y}^{k}+\sum_{l=1}^{\bar{N}-1}\mathbf{R}_{k:k-l+1}\mathbf{A}^{k-l}\mathbf{y}^{k-l})$
for $k\geq K+\bar{N}-1$ where
$\mathbf{R}_{k:k-\bar{N}+1}=\mathbf{R}^{k}\mathbf{R}^{k-1}\cdots\mathbf{R}^{k-\bar{N}+1}$.
Then, it follows

$\displaystyle\|\mathbf{\tilde{x}}_{\text{w}}^{k+1}\|\leq\big{\|}\big{[}\big{(}\mathbf{I}_{n}-\mathbf{1}_{n}(\boldsymbol{\phi}^{k+1})^{T}\big{)}\otimes\mathbf{I}_{d}\big{]}\mathbf{R}_{k:k-\bar{N}+1}\mathbf{x}^{k-\bar{N}+1}\big{\|}$
(29) $\displaystyle\
+\lambda\big{\|}\big{[}\big{(}\mathbf{I}_{n}-\mathbf{1}_{n}(\boldsymbol{\phi}^{k+1})^{T}\big{)}\otimes\mathbf{I}_{d}\big{]}\mathbf{A}^{k}\mathbf{y}^{k}\big{\|}$
$\displaystyle\
+\lambda\sum_{l=1}^{\bar{N}-1}\big{\|}\big{[}\big{(}\mathbf{I}_{n}-\mathbf{1}_{n}(\boldsymbol{\phi}^{k+1})^{T}\big{)}\otimes\mathbf{I}_{d}\big{]}\mathbf{R}_{k:k-l+1}\mathbf{A}^{k-l}\mathbf{y}^{k-l}\big{\|}$
$\displaystyle\leq
r_{R}\|\mathbf{\tilde{x}}_{\text{w}}^{k-\bar{N}+1}\|+\lambda
Q_{R}\sqrt{n}{\textstyle\sum_{l=0}^{\bar{N}-1}}\|\mathbf{y}^{k-l}\|$

where in the derivation we used Lemma 5 and the facts
$\|\mathbf{I}_{n}-\mathbf{1}_{n}(\boldsymbol{\phi}^{k+1})^{T}\|\leq
2\sqrt{n}$, $\|\mathbf{A}^{k}\|\leq\sqrt{n}$, and $2\sqrt{n}\leq Q_{R}$.
Following Lemma 1 in [38], we can obtain

$\displaystyle\|\mathbf{y}^{k}\|\leq
n\bar{\beta}\|\mathbf{\tilde{x}}_{\text{w}}^{k}\|+n\bar{\beta}\|\mathbf{r}^{k}\|+\|\mathbf{\tilde{s}}_{\text{w}}^{k}\|$
(30)

for $k\geq K$. Further combing (29) and (30) leads to the result in (11) for
$k\geq K+\bar{N}-1$. $\blacksquare$

## Appendix C: Proof of Lemma 2

Proof: Given
$\mathbf{r}^{k}=\mathbf{1}_{n}\otimes\mathbf{\tilde{x}}_{\text{w}}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}=\big{[}\mathbf{1}_{n}(\boldsymbol{\phi}^{k})^{T}\otimes\mathbf{I}_{d}\big{]}\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}$,
for $k\geq K$ we have

$\displaystyle\|\mathbf{r}^{k+1}\|\leq\big{\|}\big{[}\mathbf{1}_{n}(\boldsymbol{\phi}^{k+1})^{T}\otimes\mathbf{I}_{d}\big{]}\mathbf{R}^{k}\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}$
(31)
$\displaystyle\qquad-\lambda\big{[}(\mathbf{1}_{n}(\boldsymbol{\phi}^{k+1})^{T}\mathbf{\bar{A}}^{k}\mathbf{v}^{k}\mathbf{1}_{n}^{T})\otimes\mathbf{I}_{d}\big{]}\mathbf{y}^{k}\big{\|}$
$\displaystyle\qquad+\lambda\big{\|}\mathbf{1}_{n}(\boldsymbol{\phi}^{k})^{T}\otimes\mathbf{I}_{d}\big{\|}\cdot\|\mathbf{A}^{k}\|\cdot\big{\|}\mathbf{y}^{k}-(\mathbf{v}^{k}\mathbf{1}_{n}^{T}\otimes\mathbf{I}_{d})\mathbf{y}^{k}\big{\|}$
$\displaystyle\leq\big{\|}\big{[}\mathbf{1}_{n}(\boldsymbol{\phi}^{k})^{T}\otimes\mathbf{I}_{d}\big{]}\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}-\lambda\delta^{k}(\mathbf{1}_{n\times
n}\otimes\mathbf{I}_{d})\mathbf{y}^{k}\big{\|}$ $\displaystyle\qquad+\lambda
n\|\mathbf{\tilde{s}}_{\text{w}}^{k}\|$

where
$\delta^{k}=(\boldsymbol{\phi}^{k+1})^{T}\mathbf{\bar{A}}^{k}\mathbf{v}^{k}$,
and in the derivation we used the facts
$\|\mathbf{1}_{n}(\boldsymbol{\phi}^{k})^{T}\otimes\mathbf{I}_{d}\|\leq\sqrt{n}$,
$\|\mathbf{A}^{k}\|\leq\sqrt{n}$,
$\mathbf{y}^{k}-(\mathbf{v}^{k}\mathbf{1}_{n}^{T}\otimes\mathbf{I}_{d})\mathbf{y}^{k}=(\mathbf{\bar{V}}^{k}\otimes\mathbf{I}_{d})\mathbf{\tilde{s}}_{\text{w}}^{k}$,
and $\|\mathbf{\bar{V}}^{k}\otimes\mathbf{I}_{d}\|\leq 1$.

Now we show that $\delta^{k}\in[\eta^{n-1}/n,\,1]$. From the proof of Lemma 4
in Appendix A, we have $v_{i}^{k}\in[\eta^{n-1}/n,\,1]$ for $k\geq K$ where
$v_{i}^{k}$ denotes the $i$-th entry of vector $\mathbf{v}^{k}$. Given
$\sum_{j=1}^{n}a_{ij}^{k}=1$ for $k\geq K$, one can obtain
${\eta^{n-1}}/{n}\leq\sum_{j=1}^{n}a_{ij}^{k}v_{j}^{k}\leq 1$ for each
$i=1,\cdots,n$. Therefore, we have
$\delta^{k}=\sum_{i=1}^{n}\phi_{i}^{k}\sum_{j=1}^{n}a_{ij}^{k}v_{j}^{k}\in[{\eta^{n-1}}/{n},\,1]$
based on the fact $\sum_{i=1}^{n}\phi_{i}^{k}=1$.

Next we focus on the second last term on the right hand side of (31), which
can be expressed as follows

$\displaystyle\big{\|}\big{[}\mathbf{1}_{n}(\boldsymbol{\phi}^{k})^{T}\otimes\mathbf{I}_{d}\big{]}\mathbf{x}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}-\lambda\delta^{k}(\mathbf{1}_{n\times
n}\otimes\mathbf{I}_{d})\mathbf{y}^{k}\big{\|}$ (32)
$\displaystyle\leq\big{\|}\mathbf{1}_{n}\otimes\mathbf{\bar{x}}_{\text{w}}^{k}-\mathbf{1}_{n}\otimes\mathbf{x}^{*}-\lambda\delta^{k}(\mathbf{1}_{n\times
n}\otimes\mathbf{I}_{d})\nabla
f(\mathbf{1}_{n}\otimes\mathbf{\bar{x}}_{\text{w}}^{k})\big{\|}$
$\displaystyle\quad+\lambda\delta^{k}\big{\|}(\mathbf{1}_{n\times
n}\otimes\mathbf{I}_{d})(\nabla f^{k}-\nabla
f(\mathbf{1}_{n}\otimes\mathbf{\bar{x}}_{\text{w}}^{k}))\big{\|}$
$\displaystyle\leq\sqrt{n}\big{\|}\mathbf{\bar{x}}_{\text{w}}^{k}-\mathbf{x}^{*}-\lambda\delta^{k}\nabla
F(\mathbf{\bar{x}}_{\text{w}}^{k})\big{\|}+\lambda
n\bar{\beta}\|\mathbf{\tilde{x}}_{\text{w}}^{k}\|$

As the global objective function $F$ is $\alpha_{F}$-strongly convex and
$\beta_{F}$-smooth with $\alpha_{F}\leq\beta_{F}$, from Lemma 10 in [33], we
obtain

$\displaystyle\big{\|}\mathbf{\bar{x}}_{\text{w}}^{k}-\mathbf{x}^{*}-\lambda\delta^{k}\nabla
F(\mathbf{\bar{x}}_{\text{w}}^{k})\big{\|}\leq\frac{1}{\sqrt{n}}\big{(}1-\lambda
n^{-1}\eta^{n-1}\alpha_{F}\big{)}\|\mathbf{r}^{k}\|$ (33)

if $\lambda\leq 1/\beta_{F}$ holds. Therefore, combining (31), (32), and (33),
we have that the inequality in (12) holds for $k\geq K$ if $\lambda$ satisfies
$\lambda\leq{1}/\beta_{F}$. $\blacksquare$

## Appendix D: Proof of Lemma 3

Proof: Denoting $\mathbf{z}^{k}$ as $\mathbf{z}^{k}=\nabla f^{k+1}-\nabla
f^{k}$, from (10) we have
$\mathbf{s}^{k+1}=\mathbf{P}_{k:k-\bar{N}+1}\mathbf{s}^{k-\bar{N}+1}+((\mathbf{\bar{V}}^{k})^{-1}\otimes\mathbf{I}_{d})\mathbf{B}^{k}\mathbf{z}^{k}+\sum_{l=1}^{\bar{N}-1}\mathbf{P}_{k:k-l+1}((\mathbf{\bar{V}}^{k-l+1})^{-1}\otimes\mathbf{I}_{d})\mathbf{B}^{k-l}\mathbf{z}^{k-l}$
for $k\geq K+\bar{N}-1$. Given
$\mathbf{\tilde{s}}_{\text{w}}^{k}=\mathbf{s}^{k}-(\mathbf{1}_{n}(\mathbf{v}^{k})^{T}\otimes\mathbf{I}_{d})\mathbf{s}^{k}$,
one can obtain the following inequality for $k\geq K+\bar{N}-1$

$\displaystyle\|\mathbf{\tilde{s}}_{\text{w}}^{k+1}\|\leq
r_{P}\big{\|}\big{[}\big{(}\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k-\bar{N}+1})^{T}\big{)}\otimes\mathbf{I}_{d}\big{]}\mathbf{s}^{k-\bar{N}+1}\big{\|}$
(34)
$\displaystyle\qquad+\big{\|}\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k+1})^{T}\big{\|}\cdot\big{\|}(\mathbf{\bar{V}}^{k})^{-1}\big{\|}\cdot\big{\|}\mathbf{B}^{k}\big{\|}\cdot\big{\|}\mathbf{z}^{k}\big{\|}$
$\displaystyle\qquad+{\textstyle\sum_{l=1}^{\bar{N}-1}}Q_{P}\big{\|}(\mathbf{\bar{V}}^{k-l+1})^{-1}\big{\|}\cdot\big{\|}\mathbf{B}^{k-l}\big{\|}\cdot\big{\|}\mathbf{z}^{k-l}\big{\|}$
$\displaystyle\leq
r_{P}\|\mathbf{\tilde{s}}_{\text{w}}^{k-\bar{N}+1}\|+(n\sqrt{n}Q_{P}/\eta^{n-1}){\textstyle\sum_{l=0}^{\bar{N}-1}}\|\mathbf{z}^{k-l}\|$

where we used the facts
$\big{\|}\mathbf{I}_{n}-\mathbf{1}_{n}(\mathbf{v}^{k+1})^{T}\big{\|}\leq
2\sqrt{n}\leq Q_{P}$,
$\big{\|}(\mathbf{\bar{V}}^{k})^{-1}\big{\|}\leq{n}/{\eta^{n-1}}$,
$\big{\|}\mathbf{B}^{k}\big{\|}\leq\sqrt{n}$, and Lemma 4 in Appendix A.

Using the relationship $\mathbf{z}^{k}=\nabla f^{k+1}-\nabla f^{k}$, we can
obtain the following relationship for $k\geq K$

$\displaystyle\|\mathbf{z}^{k}\|\leq\big{(}{\textstyle\sum_{i=1}^{n}}\beta_{i}^{2}\big{\|}\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\big{\|}^{2}\big{)}^{1/2}\
\leq\ \bar{\beta}\big{\|}\mathbf{x}^{k+1}-\mathbf{x}^{k}\big{\|}$ (35)
$\displaystyle\leq\bar{\beta}\big{\|}(\mathbf{R}^{k}-\mathbf{I})\mathbf{x}^{k}\big{\|}+\lambda\bar{\beta}\big{\|}\mathbf{A}^{k}\mathbf{y}^{k}\big{\|}$
$\displaystyle\leq\bar{\beta}\big{\|}(\mathbf{R}^{k}-\mathbf{I})\big{[}(\mathbf{I}_{n}-\mathbf{1}_{n}(\boldsymbol{\phi}^{k})^{T})\otimes\mathbf{I}_{d}\big{]}\mathbf{x}^{k}\big{\|}+\lambda\bar{\beta}\big{\|}\mathbf{A}^{k}\mathbf{y}^{k}\big{\|}$
$\displaystyle\leq(2\sqrt{n}\bar{\beta}+\lambda
n\sqrt{n}\bar{\beta}^{2})\|\mathbf{\tilde{x}}_{\text{w}}^{k}\|+\lambda
n\sqrt{n}\bar{\beta}^{2}\|\mathbf{r}^{k}\|+\lambda\sqrt{n}\bar{\beta}\|\mathbf{\tilde{s}}_{\text{w}}^{k}\|$

where we used the facts $\big{\|}\mathbf{R}^{k}-\mathbf{I}\big{\|}\leq
2\sqrt{n}$,
$\big{(}(\mathbf{I}_{n}-\mathbf{1}_{n}(\boldsymbol{\phi}^{k})^{T})\otimes\mathbf{I}_{d}\big{)}\mathbf{x}^{k}=\mathbf{\tilde{x}}_{\text{w}}^{k}$,
and (30) in the derivation.

Therefore, from (34) and (35), we can obtain the inequality in (13) for $k\geq
K+\bar{N}-1$. $\blacksquare$

## References

  * [1] A. Alaeddini, K. Morgansen, and M. Mesbah.  Adaptive communication networks with privacy guarantees.  In Proc. 2017 American Contr. Conf., pages 4460–4465, 2017.
  * [2] J. A. Bazerque and G. B. Giannakis.  Distributed spectrum sensing for cognitive radio networks by exploiting sparsity.  IEEE Trans. Signal Process., 58(3):1847–1862, 2010.
  * [3] T. Charalambous, N. E. Manitara, and C. N. Hadjicostis.  Privacy-preserving average consensus over digraphs in the presence of time delays.  In Proc. 57th Annu. Allerton Conf. Commun. Control Comput., pages 238–245, 2019.
  * [4] W. Du, L. Yao, D. Wu, X. Li, G. Liu, and T. Yang.  Accelerated distributed energy management for microgrids.  In Proc. IEEE Power Energy Soc. Gen. Meeting, pages 1–5, 2018.
  * [5] M. Fazlyab, A. Ribeiro, M. Morari, and V. M. Preciado.  Analysis of optimization algorithms via integral quadratic constraints: Nonstrongly convex problems.  SIAM J. Optim., 28(3):2654–2689, 2018.
  * [6] S. Gade and N. H. Vaidya.  Private optimization on networks.  In Proc. 2018 American Contr. Conf., pages 1402–1409, 2018.
  * [7] L. Gan, U. Topcu, and S. H. Low.  Optimal decentralized protocol for electric vehicle charging.  IEEE Trans. Power Syst., 28(2):940–951, 2013.
  * [8] H. Gao, C. Zhang, M. Ahmad, and Y. Wang.  Privacy-preserving average consensus on directed graphs using push-sum.  In Proc. IEEE Conf. Commun. Netw. Security, 2018.
  * [9] N. Gupta, J. Katz, and N. Chopra.  Privacy in distributed average consensus.  IFAC-PapersOnLine, 50(1):9515–9520, 2017.
  * [10] C. N. Hadjicostis and A. D. Dominguez-Garcia.  Privacy-preserving distributed averaging via homomorphically encrypted ratio consensus.  IEEE Trans. Autom. Control, 65(9):3887–3894, 2020.
  * [11] M. T. Hale and M. Egerstedt.  Cloud-enabled differentially private multiagent optimization with constraints.  IEEE Trans. Control Netw. Syst., 5(4):1693–1706, 2017.
  * [12] J. He, L. Cai, P. Cheng, J. Pan, and L. Shi.  Distributed privacy-preserving data aggregation against dishonest nodes in network systems.  IEEE Internet Things J., 6(2):1462–1470, 2018.
  * [13] L. He, S. P. Karimireddy, and M. Jaggi.  Secure byzantine-robust machine learning.  arXiv preprint arXiv:2006.04747, 2020.
  * [14] R. A. Horn and C. R. Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [15] Z. Huang, S. Mitra, and N. Vaidya.  Differentially private distributed optimization.  In Proc. Int. Conf. Distrib. Comput. Netw., pages 4:1–4:10, 2015\.
  * [16] S. S. Kia, J. Cortés, and S. Martinez.  Dynamic average consensus under limited control authority and privacy requirements.  Int. J. Robust Nonlinear Control, 25(13):1941–1966, 2015.
  * [17] D. Lefebvre and C. N. Hadjicostis.  Privacy and safety analysis of timed stochastic discrete event systems using markovian trajectory-observers.  Discret. Event Dyn. Syst., pages 1–28, 2020.
  * [18] Q. Li, R. Heusdens, and M. G. Christensen.  Privacy-preserving distributed optimization via subspace perturbation: a general framework.  IEEE Trans. Signal Process., 68:5983–5996, 2020.
  * [19] Y. Lou, L. Yu, S. Wang, and P. Yi.  Privacy preservation in distributed subgradient optimization algorithms.  IEEE Trans. Cybern., 48(7):2154–2165, 2018.
  * [20] Y. Lu and M. Zhu.  Privacy preserving distributed optimization using homomorphic encryption.  Automatica, 96:314–325, 2018.
  * [21] N. E. Manitara and C. N. Hadjicostis.  Privacy-preserving asymptotic average consensus.  In 2013 Eur. Control Conf., pages 760–765, 2013.
  * [22] Y. Mo and R. M. Murray.  Privacy preserving average consensus.  IEEE Trans. Autom. Control, 62(2):753–765, 2017.
  * [23] A. Nedić and J. Liu.  On convergence rate of weighted-averaging dynamics for consensus problems.  IEEE Trans. Autom. Control, 62(2):766–781, 2016.
  * [24] A. Nedić, A. Olshevsky, and W. Shi.  Achieving geometric convergence for distributed optimization over time-varying graphs.  SIAM J. Optim., 27(4):2597–2633, 2017.
  * [25] A. Nedić, A. Olshevsky, W. Shi, and C. A. Uribe.  Geometrically convergent distributed optimization with uncoordinated step-sizes.  In Proc. 2017 American Contr. Conf., pages 3950–3955, 2017.
  * [26] A. Nedić and A. Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  IEEE Trans. Autom. Control, 54(1):48–61, 2009.
  * [27] A. Nedić and A. Ozdaglar.  Distributed optimization over time-varying directed graphs.  IEEE Trans. Autom. Control, 60(3):601–615, 2015.
  * [28] E. Nozari, P. Tallapragada, and J. Cortés.  Differentially private distributed convex optimization via functional perturbation.  IEEE Trans. Control Netw. Syst., 5(1):395–408, 2016.
  * [29] S. Pequito, S. Kar, S. Sundaram, and A. P. Aguiar.  Design of communication networks for distributed computation with privacy guarantees.  In Proc. IEEE 53rd Conf. Decis. Control, pages 1370–1376, 2014\.
  * [30] A. B. Pilet, D. Frey, and F. Taiani.  Robust privacy-preserving gossip averaging.  In Proc. 21st Int. Symp. Stabilization, Saf., Secur. Distrib. Syst., pages 38–52. Springer, 2019.
  * [31] P. D. Powell.  Calculating determinants of block matrices.  arXiv preprint arXiv:1112.4379, 2011.
  * [32] S. Pu, W. Shi, J. Xu, and A. Nedić.  A push-pull gradient method for distributed optimization in networks.  In Proc. IEEE 57th Conf. Decis. Control, pages 3385–3390, 2018\.
  * [33] G. Qu and N. Li.  Harnessing smoothness to accelerate distributed optimization.  IEEE Trans. Control Netw. Syst., 5(3):1245–1260, 2017.
  * [34] R. L. Raffard, C. J. Tomlin, and S. P. Boyd.  Distributed optimization for cooperative agents: Application to formation flight.  In Proc. IEEE 43rd Conf. Decis. Control, volume 3, pages 2453–2459, 2004.
  * [35] B. Ramasubramanian, W. R. Cleaveland, and S. Marcus.  Notions of centralized and decentralized opacity in linear systems.  IEEE Trans. Autom. Control, 65(4):1442–1455, 2019.
  * [36] I. D. Ridgley, R. A. Freeman, and K. M. Lynch.  Simple, private, and accurate distributed averaging.  In Proc. 57th Annu. Allerton Conf. Commun. Control Comput., pages 446–452, 2019.
  * [37] M. Ruan, H. Gao, and Y. Wang.  Secure and privacy-preserving consensus.  IEEE Trans. Autom. Control, 64(10):4035–4049, 2019.
  * [38] F. Saadatniaki, R. Xin, and U. A. Khan.  Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices.  IEEE Trans. Autom. Control, 65(11):4769–4780, 2020.
  * [39] A. Saboori and C. N. Hadjicostis.  Verification of initial-state opacity in security applications of discrete event systems.  Inform. Sciences, 246:115–132, 2013.
  * [40] E. Seneta.  Non-negative matrices and Markov chains.  Springer Science & Business Media, 2006.
  * [41] W. Shi, Q. Ling, G. Wu, and W. Yin.  Extra: An exact first-order algorithm for decentralized consensus optimization.  SIAM J. Optim., 25(2):944–966, 2015.
  * [42] Y. Wang and A. Nedić.  Tailoring gradient methods for differentially-private distributed optimization.  arXiv preprint arXiv:2202.01113, 2022.
  * [43] Y. Wang and V. Poor.  Decentralized stochastic optimization with inherent privacy protection.  IEEE Trans. Autom. Control, 2022.
  * [44] C. Xi, R. Xin, and U. A. Khan.  Add-opt: Accelerated distributed directed optimization.  IEEE Trans. Autom. Control, 63(5):1329–1339, 2018.
  * [45] R. Xin and U. A. Khan.  A linear algorithm for optimization over directed graphs with geometric convergence.  IEEE Control Syst. Lett., 2(3):315–320, 2018.
  * [46] J. Xu, S. Zhu, Y. C. Soh, and L. Xie.  Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes.  In Proc. IEEE 54th Conf. Decis. Control,, pages 2055–2060, 2015\.
  * [47] J. Xu, S. Zhu, Y. C. Soh, and L. Xie.  Convergence of asynchronous distributed gradient methods over stochastic networks.  IEEE Trans. Autom. Control, 63(2):434–448, 2017.
  * [48] F. Yan, S. Sundaram, S. V. N. Vishwanathan, and Y. Qi.  Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties.  IEEE Trans. Knowl. Data Eng., 25(11):2483–2493, 2012.
  * [49] K. Yuan, Q. Ling, and W. Yin.  On the convergence of decentralized gradient descent.  SIAM J. Optim., 26(3):1835–1854, 2016.
  * [50] C. Zhang, M. Ahmad, and Y. Wang.  Admm based privacy-preserving decentralized optimization.  IEEE Trans. Inf. Forensic Secur., 14(3):565–580, 2018.
  * [51] C. Zhang and Y. Wang.  Distributed event localization via alternating direction method of multipliers.  IEEE Trans. Mob. Comput., 17(2):348–361, 2018.
  * [52] C. Zhang and Y. Wang.  Enabling privacy-preservation in decentralized optimization.  IEEE Trans. Control Netw. Syst., 6(2):679–689, 2018.
  * [53] S. Zhang, X. Yi, J. George, and T. Yang.  Computational convergence analysis of distributed optimization algorithms for directed graphs.  In Proc. IEEE 15th Int. Conf. Control Autom., pages 1096–1101, 2019\.