# Communication-efficient and Differentially-private Distributed Nash
Equilibrium Seeking with Linear Convergence

Xiaomeng Chen  Wei Huo  Kemi Ding  Subhrakanti Dey  and Ling Shi X. Chen, W.
Huo and L. Shi are with the Department of Electronic and Computer Engineering,
Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong
Kong (email<EMAIL_ADDRESS><EMAIL_ADDRESS>eesling@ust.hk).K.
Ding is with the School of System Design and Intelligent Manufacturing,
Southern University of Science and Technology, Shenzhen, 518055, China (email:
dingkm@sustech.edu.cn).S. Dey is with the Department of Electrical
Engineering, Uppsala University, 751 03 Uppsala, Sweden. (email:
subhrakanti.dey@angstrom.uu.se).

###### Abstract

The distributed computation of a Nash equilibrium (NE) for non-cooperative
games is gaining increased attention recently. Due to the nature of
distributed systems, privacy and communication efficiency are two critical
concerns. Traditional approaches often address these critical concerns in
isolation. This work introduces a unified framework, named CDP-NES, designed
to improve communication efficiency in the privacy-preserving NE seeking
algorithm for distributed non-cooperative games over directed graphs.
Leveraging both general compression operators and the noise adding mechanism,
CDP-NES perturbs local states with Laplacian noise and applies difference
compression prior to their exchange among neighbors. We prove that CDP-NES not
only achieves linear convergence to a neighborhood of the NE in games with
restricted monotone mappings but also guarantees $\epsilon$-differential
privacy, addressing privacy and communication efficiency simultaneously.
Finally, simulations are provided to illustrate the effectiveness of the
proposed method.

Nash equilibrium seeking, information compression, differential privacy,
distributed networks

##  1 INTRODUCTION

Non-cooperative games have been extensively studied due to their broad
applications in various fields, including congestion control in traffic
networks [1], charging of electric vehicles [2] and demand-side management in
smart grids [3]. In such games, each agent is endowed with a local cost
function to be optimized, which depends on other agents’ decisions. The NE has
emerged as a critical solution concept, reflecting the outcomes of decision-
making by multiple agents in a non-cooperative setting. However, in
decentralized networks where no central server exists, individual agents do
not have access to the joint action profile to optimize its decision. As a
result, agents should share their local information with neighbors in a
distributed manner to reach the NE.

Although significant advancements have been made in distributed NE seeking [4,
5, 6], these methods have a spot in common that they all involve agents
broadcasting messages. However, directly exchanging data will raise two main
challenges: (1) the absence of privacy protections, risking vulnerability to
inference attacks [7, 8], and (2) significant communication costs associated
with transmitting high-dimensional states in large-scale systems. These issues
often co-occur in distributed systems, highlighting the need for integrated
solutions that address both privacy and communication efficiency.

Currently, communication efficiency and privacy issues are often explored
separately in distributed NE seeking. In terms of privacy, various strategies
have been implemented, such as adding diminishing Laplacian noise [9] and
using globally correlated perturbation [10] to conceal agents’ actions, though
these measures may compromise convergence accuracy. To deal with the tradeoff
between accuracy and privacy, Wang et al. [11] proposed a differentially
private (DP) NE seeking method for stochastic aggregative games by perturbing
the gradient used for optimization instead of transmitting data. For general
non-cooperative games, Wang and Basar [12] developed an approach that ensures
both provable convergence and differential privacy by employing diminishing
step sizes, albeit at the cost of reduced convergence speed.

In terms of communication efficiency, event-triggered mechanisms have been
suggested in the literature to reduce the frequency of information exchanges
between agents for distributed NE seeking [13, 14]. Furthermore, the
efficiency of communication can be further improved by reducing the size of
the transmitted data. This is achieved through various compression techniques,
including uniform quantizations [15], deterministic quantizations [16], and
general compressors [17]. A recent algorithm [18] notably improved
communication efficiency in distributed NE seeking problems by combining
reduced transmission frequency and a reduction in data size. While effective
in reducing communication overhead, these methods have not simultaneously
tackled privacy concerns within their designs. Recently, Xie et al. [19]
proposed a compressed differentially private gradient descent algorithm for
distributed optimization (DO) problems on undirected graphs. However, privacy-
preserving NE seeking differs fundamentally: (1) agents in DO are cooperative
in minimizing the sum of functions, whereas players in games are competitive
in striving to minimize their distinct cost functions, which depends on the
actions of others; (2) noise in games can easily alter the NE (as shown in
[9]), necessitating careful design of the noise-adding mechanism and inter-
player interaction to ensure convergence.

Motivated by the above observations, this paper designs a Compressed,
Differentially Private Nash Equilibrium Seeking (CDP-NES) algorithm, a novel
approach designed to enhance communication efficiency and preserve privacy
simultaneously.  Instead of naively compressing the transmitted data in
existing privacy-preserving NE seeking methods that use diminishing stepsizes,
our approach uses a difference compression technique inspired by our previous
work [17] with constant stepsizes to enhance both communication efficiency and
convergence speed. However, the introduction of several variables within the
compression framework [17] presents challenges for integrating noise injection
for privacy. Improper noise injection could result in algorithm divergence or
privacy breaches. To address these issues, our paper proposes a joint design
of difference compression and noise injection techniques that ensure linear
convergence while preserving privacy. The main contributions are as follows:

  * •

We propose a novel algorithm (CDP-NES) that integrates differential privacy
within a compressed communication framework for distributed non-cooperative
games over directed graphs. By jointly designing the difference compression
method for noise-perturbed data, our approach can be applied to a general
class of compressors, instead of the specific compressors in [15, 16].

  * •

By employing a constant stepsize, our approach achieves linear convergence to
a neighborhood of the NE and achieves $\epsilon$-differential privacy
simultaneously, significantly enhancing the convergence speed compared to
methods that use diminishing step size [9, 10, 11, 12].

  * •

Moreover, we demonstrate that the mean squared error of the convergence is
upper bounded by a finite value inversely proportional to the privacy level
$\epsilon$, providing a clear quantification of the trade-off involved.

Notations: We denote $\bm{e}_{i}\in\mathbb{R}^{n}$ as the $i$-th unit vector
which takes zero except for the $i$-th entry that equals to $1$. The spectral
radius of matrix $\mathbf{A}$ is denoted by $\rho(\mathbf{A})$. Given a matrix
$\mathbf{A}$, we denote its element in the $i$-th row and $j$-th column by
$[\bm{A}]_{ij}$. We denote $||\mathbf{x}||$ and $||\mathbf{X}||_{\text{F}}$
respectively as $l_{2}$ norm of vector $\mathbf{x}$ and the Frobenius norm of
matrix $\mathbf{X}$. $\bm{x}\preceq\bm{y}$ is denoted as component-wise
inequality between vectors $\bm{x}$ and $\bm{y}$. The smallest nonzero
eigenvalue of a positive semidefinite matrix $\mathbf{M}\neq\mathbf{0}$ is
denoted as $\tilde{\lambda}_{\min}(\mathbf{M})$. For a vector
$\mathbf{a}\in\mathbb{R}^{n}$, we denote $\text{Diag}(\mathbf{a})$ as the
diagonal matrix with the vector $\mathbf{a}$ on its diagonal. For a given
constant $\theta>0$, Lap($\theta$) is the Laplace distribution with
probability function
$f_{L}(x,\theta)=\frac{1}{2\theta}e^{-\frac{|x|}{\theta}}$. $\mathbb{E}(x)$
denotes the expectation of a random variable $x$.

##  2 PRELIMINARIES AND PROBLEM STATEMENT

###  2.1 Network Model

We consider a group of agents communicating over a directed graph
$G\triangleq(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{1,2,3\ldots,n\\}$ denotes the agent set and
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ denotes the edge set,
respectively. A communication link from agent $j$ to agent $i$ is denoted by
$(j,i)\in\mathcal{E}$. The agents who can send messages to node $i$ are
denoted as in-neighbours of agent $i$ and the set of these agents is denoted
as $\mathcal{N}_{i}^{-}=\\{j\in\mathcal{V}\mid(j,i)\in\mathcal{E}\\}$.
Similarly, the agents who can receive messages from node $i$ are denoted as
out-neighbours of agent $i$ and the set of these agents is denoted as
$\mathcal{N}_{i}^{+}=\\{j\in\mathcal{V}\mid(i,j)\in\mathcal{E}\\}$. The
adjacency matrix of the graph is denoted as $W=[w_{ij}]_{n\times n}$ with
$w_{ij}>0$ if $(i,j)\in\mathcal{E}$ or $i=j$, and $w_{ij}=0$ otherwise. The
graph $G$ is called strongly connected if there exists at least one directed
path from any agent $i$ to any agent $j$ in the graph with $i\neq j$.

###### Assumption 1

The directed graph $G\triangleq(\mathcal{V},\mathcal{E})$ is strongly
connected. Moreover, the adjacency matrix $W$ associated with $G$ is row-
stochastic, i.e., $\sum_{l=1}^{n}w_{il}=1,\forall i\in\mathcal{V}$.

###  2.2 Compressors

To improve the communication efficiency, we consider the situation where
agents compress the information before sending it. For any
$\mathbf{x}\in\mathbb{R}^{d}$, we consider a general class of stochastic
compressors $\mathcal{C}(\mathbf{x},\zeta)$ and use $f_{c}(\mathbf{x},\zeta)$
to denote the corresponding probability density functions, where ${\zeta}$ is
a random variable. Note that the realizations $\zeta$ of the compressor
$\mathcal{C}(\cdot)$ are independent among different agents and time steps.
Hereafter, we drop $\zeta$ and write $\mathcal{C}(\mathbf{x})$ for notational
simplicity.

###### Assumption 2

The compressor $\mathcal{C}(\cdot):\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$
satisfies

$\mathbb{E}[||\mathcal{C}(\mathbf{x})-\mathbf{x}||^{2}]\leq
C||\mathbf{x}||^{2},\qquad\forall\mathbf{x}\in\mathbb{R}^{d},$ (1)

where $C\geq 0$ and the $r$-scaling of $\mathcal{C}(\cdot)$ satisfies

$\mathbb{E}[||\mathcal{C}(\mathbf{x})/r-\mathbf{x}||^{2}]\leq(1-\delta)||\mathbf{x}||^{2},\qquad\forall\mathbf{x}\in\mathbb{R}^{d},$
(2)

where $\delta\in(0,1]$ and $r>0$.

###### Remark 1

Equation (2) is equivalent to Equation (1) with
$C=2r^{2}(1-\delta)+2(1-r)^{2}$ [20]. The $r$-scaling version of compressor
$\mathcal{C}(\cdot)$ ensures the compression ratio, $1-\delta$, stays within
the range of $[0,1)$ even when $C>1$.

The above class of compressors incorporate the widely used unbiased
compressors and biased but contractive compressors, such as stochastic
quantization [21] and Top-$k$ [22]. They also cover non-contractive
compressors like the norm-sign [17].

###  2.3 Differential Privacy

Differential privacy serves as a mathematical notion which quantifies the
degree of involved individuals’ privacy. We give the following definitions for
differential privacy.

###### Definition 1

(Adjacency [23]) Two function sets
$\mathcal{S}^{(1)}=\\{J_{i}^{(1)}\\}^{n}_{i=1}$ and
$\mathcal{S}^{(2)}=\\{J_{i}^{(2)}\\}^{n}_{i=1}$, where
$J_{i}^{(l)}:\mathbb{R}^{n}\rightarrow\mathbb{R},\forall i\in\\{1,2,\ldots
n\\},l\in{1,2},$ are said to be adjacent if there exists some
$i_{0}\in\\{1,2\ldots,n\\}$ such that $J_{i}^{(1)}(x)=J_{i}^{(2)}(x),\forall
i\neq i_{0}$ and $J_{i_{0}}^{(1)}(x)\neq J_{i_{0}}^{(2)}(x)$ for all
$x\in\mathbb{R}^{n}$.

###### Definition 2

(Differential privacy [23]) Given $\epsilon>0,$ for any pair of adjacent
function sets $\mathcal{S}^{(1)}$ and $\mathcal{S}^{(2)}$ and any observation
$\mathcal{O}\subseteq\text{Range}(\mathcal{A})$, a randomized algorithm
$\mathcal{A}$ keeps $\epsilon$-differential privacy if
$P\\{\mathcal{A}(\mathcal{S}^{(1)})\in\mathcal{O}\\}\leq
e^{\epsilon}P\\{\mathcal{A}(\mathcal{S}^{(2)})\in\mathcal{O}\\}$, where
$\text{Range}(\mathcal{A})$ denotes the output codomain of $\mathcal{A}$.

###  2.4 Problem Definition

Consider a noncooperative game in a multi-agent system of $n$ agents, where
each agent has an unconstrained action set $\Omega_{i}=\mathbb{R}$. Without
loss of generality, we assume that each agent’s decision variable is a scalar.
Let $J_{i}$ denote the cost function of the agent $i$. Then, the game is
denoted as $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}\\})$. The goal of each agent
$i\in\mathcal{V}$ is to minimize its objective function $J_{i}(x_{i},x_{-i})$,
which depends on both the local variable $x_{i}$ and the decision variables of
the other agents $x_{-i}$. The concept of NE is given below.

###### Definition 3

A vector
$\mathbf{x}^{\star}=[x_{1}^{\star},x_{2}^{\star},\ldots,x_{n}^{\star}]^{\top}$
is an NE if for any $i\in\mathcal{V}$ and $x_{i}\in\mathbb{R}$,
$J_{i}(x_{i}^{\star},x_{-i}^{\star})\leq J_{i}(x_{i},x_{-i}^{\star}).$

We then make the following assumptions about game $\Gamma$.

###### Assumption 3

For all $i\in\mathcal{V}$, the cost function $J_{i}(x_{i},x_{-i})$ is strongly
convex and continuously differentiable in $x_{i}$ for fixed $x_{-i}$.

###### Definition 4

The mapping $\mathbf{F}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ of the form

$\mathbf{F(x)}\triangleq[\nabla_{1}J_{1}(x_{1},x_{-1}),\ldots,\nabla_{n}J_{n}(x_{n},x_{-n})]^{\top},$
(3)

is called the game mapping of $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}\\})$, where
$\nabla_{i}J_{i}(x_{i},x_{-i})=\frac{\partial J_{i}(x_{i},x_{-i})}{\partial
x_{i}},\forall i\in\mathcal{V}$.

###### Assumption 4

The game mapping $\mathbf{F(x)}$ is restricted strongly monotone to any NE
$\mathbf{x}^{\star}$ with constant $\mu_{r}>0$, i.e.,

$\langle\mathbf{F(x)}-\mathbf{F(\mathbf{x}^{\star})},\mathbf{x}-\mathbf{\mathbf{x}^{\star}}\rangle\geq\mu_{r}||\mathbf{x-\mathbf{x}^{\star}}||^{2},\forall\mathbf{x}\in\mathbb{R}^{n}.$

In this paper, we relax the strongly monotone mapping condition in [24, 9, 11]
to a restricted one as in Assumption 4. Thus, a wider variety of games are
taken into consideration [6].

###### Assumption 5

Each function $\nabla_{i}J_{i}(x_{i},x_{-i})$ is uniformly Lipschitz
continuous, i.e., there exists a fixed constant $L_{i}\geq 0$ such that
$\|\nabla_{i}J_{i}(\mathbf{x})-\nabla_{i}J_{i}(\mathbf{y})\|\leq
L_{i}\|\mathbf{x}-\mathbf{y}\|$ for all
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$.

In this paper, we are interested in distributed seeking of an NE in a game
$\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}=\mathbb{R}\\})$ where Assumptions 1,3,4
and 5 hold. Note that given Assumptions 3 and 4, there exists a unique NE in
the game $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}=\mathbb{R}\\})$ [17]. To be
specific, $\mathbf{x}^{\star}\in\mathbb{R}^{n}$ is an NE if and only if
$\mathbf{F(x^{\star})}=0.$

##  3 CDP-NES Algorithm

In this section, we introduce CDP-NES, the proposed differentially private NE
seeking algorithm with compression communication, where compression is
achieved by the compressors $\mathcal{C}(\cdot)$ satisfying Assumption 2. In a
distributed network, we assume that each agent maintains a local variable
$\mathbf{x}_{(i)}=[\tilde{x}_{(i)1},\ldots,\tilde{x}_{(i)i-1},x_{i},\tilde{x}_{(i)i+1},\ldots,\tilde{x}_{(i)n}]^{\top}\in\mathbb{R}^{n},$
which is his estimation of the joint action profile
$\mathbf{x}=[x_{1},x_{2},\ldots,x_{n}]^{\top}$, where $\tilde{x}_{(i)j}$
denotes agent $i$’s estimate of $x_{j}$ and $\tilde{x}_{(i)i}=x_{i}$.

We describe CDP-NES in Algorithm 1. Different from most differentially private
algorithms that directly inject noise on the transmitted data, to improve
communication efficiency and achieve differential privacy, we first add noise
$\xi_{i}^{k}$ to the local state $\mathbf{x}_{(i)}^{k}$ of each agent $i$,
thus generating a noisy version $\mathbf{\tilde{x}}^{k}_{(i)}$. We then
introduce an auxiliary variable $\mathbf{h}_{i}^{k}$ as a reference point of
$\mathbf{\tilde{x}}_{(i)}^{k}$, initialized arbitrarily in $\mathbb{R}^{n}$.
Compression is applied to the difference between
$\mathbf{\tilde{x}}_{(i)}^{k}$ and $\mathbf{h}_{i}^{k}$ and then we transmit
the compressed data $\mathbf{q}_{i}^{k}$. This ensures that only compressed
information is transmitted between agents, effectively reducing the bandwidth
used. Additionally, as $\mathbf{h}_{i}^{k}$ approaches
$\mathbf{\tilde{x}}_{(i)}^{k}$, the compression error correspondingly
diminishes based on Assumption 2. The introduction of $\mathbf{h}_{i}^{k}$ is
motivated from DIANA [25], which eliminates the compression error,
particularly for a relatively large constant $C$ in Assumption 2.

After receiving the compressed value, each agent $i$ constructs an estimation
of $\mathbf{x}_{(i)}$, denoted as $\mathbf{\hat{x}}_{(i)}$, and utilizes this
estimation to update their local variable $\mathbf{x}_{(i)}^{k}$ for
mitigating the compression error. This innovative mechanism is designed to
ensure linear convergence and maintain differential privacy within a
compressed communication framework, with its effectiveness theoretically
validated in Sections 4–5.

Algorithm 1 A Compressed and Differentially Private Distributed Nash
Equilibrium Seeking (CDP-NES) Algorithm

Input: Stopping time $K$, stepsize $\eta$, consensus stepsize $\gamma$,
scaling parameter $\alpha>0$, noise variance $\theta_{i}>0$ and initial values
$\mathbf{x}_{(i)}^{0},\mathbf{h}_{i}^{0}$
Output: $\mathbf{x}_{(i)}^{K}$

1:for each agent $i\in\mathcal{V}$ do

2:
$\mathbf{h}_{i,w}^{0}=\sum\limits_{j\in\mathcal{N}_{i}}w_{ij}\mathbf{h}_{j}^{0}$

3:for $k=0,1,2,\ldots,K-1$ do locally at each agent $i\in\mathcal{V}$

4: $\mathbf{\tilde{x}}^{k}_{(i)}=\mathbf{x}_{(i)}^{k}+\xi_{i}^{k}$, where
$\xi_{i}^{k}$ is a random vector consisting of $n$ Laplacian noise
independently drawn from Lap($\theta_{i}$) $\triangleright$ Noise perturbation

5:
$\mathbf{q}_{i}^{k}=\mathcal{C}(\mathbf{\tilde{x}}_{(i)}^{k}-\mathbf{h}_{i}^{k})$
$\triangleright$ Difference compression

6: $\mathbf{\hat{x}}_{(i)}^{k}=\mathbf{h}_{i}^{k}+\mathbf{q}_{i}^{k}$

7:
$\mathbf{h}_{i}^{k+1}=(1-\alpha)\mathbf{h}_{i}^{k}+\alpha\mathbf{\hat{x}}_{(i)}^{k}$

8: Send $\mathbf{q}_{i}^{k}$ to agent $l\in\mathcal{N}_{i}^{-}$ and then
receive $\mathbf{q}_{j}^{k}$ from agent $j\in\mathcal{N}_{i}^{+}$
$\triangleright$ Communication

9:
$\mathbf{\hat{x}}_{(i),w}^{k}=\mathbf{h}_{i,w}^{k}+\sum_{j=1}^{n}w_{ij}\mathbf{q}_{j}^{k}$

10:
$\mathbf{h}_{i,w}^{k+1}=(1-\alpha)\mathbf{h}_{i,w}^{k}+\alpha\mathbf{\hat{x}}_{(i),w}^{k}$

11:
$\mathbf{x}_{(i)}^{k+1}=\mathbf{\tilde{x}}_{(i)}^{k}-\gamma(\mathbf{\hat{x}}_{(i)}^{k}-\mathbf{\hat{x}}_{(i),w}^{k})-\gamma\eta\nabla_{i}J_{i}(\mathbf{x}_{(i)}^{k})\mathbf{e}_{i}$

Denote the compact form of local state variable as
$\mathbf{X}=[\mathbf{x}_{(1)},\mathbf{x}_{(2)},\ldots,\mathbf{x}_{(n)}]^{\top}\in\mathbb{R}^{n\times
n},$ where the $i$th row is the vector $\mathbf{x}_{(i)},i\in\mathcal{V}$.
Auxiliary variables of the agents in compact form
$\bm{\xi},\mathbf{\tilde{X}},\mathbf{H},\mathbf{H}_{w},\mathbf{Q},\mathbf{\hat{X}}$
and $\mathbf{\hat{X}}_{w}$ are defined similarly. At $k-$th iteration, their
values are denoted by
$\mathbf{X}^{k},\bm{\xi}^{k},\mathbf{\tilde{X}}^{k},\mathbf{H}^{k},\mathbf{H}_{w}^{k},\mathbf{Q}^{k},\mathbf{\hat{X}}^{k}$
and $\mathbf{\hat{X}}_{w}^{k}$ , respectively. Moreover, for any given action-
profile estimates, we define a diagonal matrix
$\mathbf{\tilde{F}}(\mathbf{X})\triangleq\text{Diag}(\nabla_{1}J_{1}(\mathbf{x}_{(1)}),\ldots,\nabla_{n}J_{n}(\mathbf{x}_{(n)})).$

Algorithm 1 can be written in compact form as follows:

$\displaystyle\mathbf{\tilde{X}}^{k}=\mathbf{X}^{k}+\bm{\xi}^{k},$ (4a)
$\displaystyle\mathbf{Q}^{k}=\mathcal{C}(\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}),$
(4b) $\displaystyle\mathbf{\hat{X}}^{k}=\mathbf{H}^{k}+\mathbf{Q}^{k},$ (4c)
$\displaystyle\mathbf{\hat{X}}^{k}_{w}=\mathbf{H}_{w}^{k}+W\mathbf{Q}^{k},$
(4d)
$\displaystyle\mathbf{H}^{k+1}=(1-\alpha)\mathbf{H}^{k}+\alpha\mathbf{\hat{X}}^{k},$
(4e)
$\displaystyle\mathbf{H}^{k+1}_{w}=(1-\alpha)\mathbf{H}^{k}_{w}+\alpha\mathbf{\hat{X}}^{k}_{w},$
(4f)
$\displaystyle\mathbf{X}^{k+1}=\mathbf{\tilde{X}}^{k}-\gamma(\mathbf{\hat{X}}^{k}-\mathbf{\hat{X}_{w}}^{k})-\gamma\eta\mathbf{\tilde{F}}(\mathbf{X}^{k}),$
(4g)

where $\mathbf{X}^{0}$ and $\mathbf{H}^{0}$ are arbitrary chosen.

Since $\mathbf{H}^{k}_{w}=W\mathbf{H}^{k}$ and
$\mathbf{\hat{X}}^{k}_{w}=W\mathbf{\hat{X}}^{k}$ for all $k$ [17], the state
variable update in (4g) becomes

$\displaystyle\mathbf{X}^{k+1}=\mathbf{\tilde{X}}^{k}-\gamma(\mathbf{\hat{X}}^{k}-W\mathbf{\hat{X}}^{k})-\gamma\eta\mathbf{\tilde{F}}(\mathbf{X}^{k})$
(5)
$\displaystyle=\mathbf{X}^{k}-\gamma\mathbf{F}_{a}(\mathbf{X}^{k})+\gamma(I-W)\mathbf{E}^{k}+\bm{\xi}^{k},$

where
$\mathbf{F}_{a}(\mathbf{X}^{k})=(I-W)\mathbf{X}^{k}+\eta\mathbf{\tilde{F}}(\mathbf{X}^{k})$
denotes the augmented mapping [6] of game $\Gamma$, and
$\mathbf{E}^{k}=\mathbf{X}^{k}-\mathbf{\hat{X}}^{k}$.

##  4 Convergence Analysis

In this section, we analyze the convergence performance of CDP-NES. The main
idea of our strategy is to bound the NE-seeking error
$\mathbb{E}[||\mathbf{X}^{k}-\mathbf{X}^{\star}||^{2}_{\text{F}}]$ and the
compression error
$\mathbb{E}[||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}]$ on the
basis of the linear combinations of their previous values. Let
$\mathcal{F}^{k}$ be the $\sigma-$algebra generated by
$\\{\mathbf{E}^{0},\bm{\xi}^{0},\mathbf{E}^{1},\bm{\xi}^{1},\ldots,\mathbf{E}^{k-1},\bm{\xi}^{k-1}\\}$,
and denote $\mathbb{E}[\cdot|\mathcal{F}^{k}]$ as the conditional expectation
given $\mathcal{F}^{k}$.

###  4.1 Supporting Lemmas

###### Lemma 1

(Lemma 1 in [6]) Given Assumption 5, the augmented mapping $\mathbf{F}_{a}$ of
game $\Gamma$ is Lipschitz continuous with $L_{F}=\eta
L_{m}+||I-W||_{\text{F}}$, where $L_{m}=\max_{i}L_{i}$.

###### Lemma 2

(Lemma 3 in [6]) Given Assumptions 1, 4 and 5, the augmented mapping
$\mathbf{F}_{a}$ of game $\Gamma(n,\\{J_{i}\\},\\{\Omega_{i}\\})$ is
restricted strongly monotone to any NE $\mathbf{X}^{\star}$ with the constant
$\mu_{F}=\min\\{b_{1},b_{2}\\}>0$, where
$b_{1}=\eta\mu_{r}/2n,b_{2}=(\beta^{2}\tilde{\lambda}_{\text{min}}(I-W)/(\beta^{2}+1))-\eta^{2}L_{m}$
and $\beta$ is a positive constant such that
$\beta^{2}+2\beta=\frac{\mu_{r}}{2n\eta L_{m}}$.

###  4.2 Main results

###### Lemma 3

Suppose Assumption 2 holds, the variables $\mathbf{X}^{k},\mathbf{H}^{k}$ are
measurable respect to $\mathcal{F}^{k}$. Furthermore, we have

$\mathbb{E}[||\mathbf{E}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\leq
2C||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}+4n^{2}\bar{\theta}^{2},$
(6)

where $\bar{\theta}=\max_{i\in\mathcal{V}}\theta_{i}$ and $\theta_{i}$ denotes
the Laplacian noise variance of agent $i$.

Proof: By expanding (4a)-(4g) recursively, $\mathbf{X}^{k}$ and
$\mathbf{H}^{k}$ can be represented by linear combinations of
$\mathbf{X}^{0},\mathbf{H}^{0}$ and random variables
$\\{\mathbf{E}^{j}\\}_{j=0}^{k-1}$ and $\\{\bm{\xi}^{j}\\}_{j=0}^{k-1}$, i.e,
$\mathbf{X}^{k},\mathbf{H}^{k}$ are measurable respect to $\mathcal{F}^{k}$.
Moreover, from (4c) and (1), we have

$\displaystyle\mathbb{E}[||\mathbf{E}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]=\mathbb{E}[||\mathbf{X}^{k}-\mathbf{\hat{X}}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]$
$\displaystyle=\mathbb{E}[||\mathbf{\tilde{X}}^{k}-\bm{\xi}^{k}-\mathbf{H}^{k}-\mathcal{C}(\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k})||^{2}_{\text{F}}\mid\mathcal{F}^{k}]$
$\displaystyle\leq
2\mathbb{E}[||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}-\mathcal{C}(\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k})||^{2}_{\text{F}}\mid\mathcal{F}^{k}]+2\mathbb{E}[||\bm{\xi}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]$
$\displaystyle\leq
2C||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}+4n^{2}\bar{\theta}^{2}.\qquad\qquad\qquad\qquad\qquad\qquad{\hfill\blacksquare}$

###### Lemma 4

Given Assumptions 1–5, when $\alpha\in(0,\frac{1}{r}]$, the following linear
system of component-wise inequalities holds

$\mathbf{V}^{k+1}\preceq\mathbf{A}\mathbf{V}^{k}+\mathbf{b},\ $ (7)

where
$\mathbf{V}^{k}=\begin{bmatrix}\mathbb{E}[||\mathbf{X}^{k}-\mathbf{X}^{\star}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]&\mathbb{E}[||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
\end{bmatrix}^{\top}$ and the elements of $\mathbf{A}$ and $\mathbf{b}$ are
respectively given by

$\displaystyle\mathbf{A}=\begin{bmatrix}c_{1}(1+L_{F}^{2}\gamma^{2}-2\mu_{F}\gamma)&c_{2}\gamma^{2}\\\
c_{4}\gamma^{2}L_{F}^{2}&c_{x}+c_{5}\gamma^{2}\\\ \end{bmatrix},$ (8)
$\displaystyle\mathbf{b}=\begin{bmatrix}c_{3}\bar{\theta}^{2}&c_{6}\bar{\theta}^{2}\end{bmatrix}^{\top},$

where
$c_{1}=\frac{2L_{F}^{2}-\mu_{F}^{2}}{2L_{F}^{2}-2\mu_{F}^{2}},c_{2}=\frac{4c_{1}||I-W||_{\text{F}}^{2}C}{c_{1}-1},c_{3}=\frac{8c_{1}||I-W||_{\text{F}}^{2}n^{2}}{c_{1}-1}+\frac{4c_{1}n^{2}}{c_{1}-1},c_{4}=\frac{6(1+\alpha
r\delta)}{\alpha
r\delta},c_{5}=2c_{4}C||I-W\textdagger||^{2}_{\text{F}},c_{6}=(2c_{4}+6)n^{2}$
and $c_{x}=1-\alpha^{2}r^{2}\delta^{2}$ .

Proof: See Appendix 8.1.

###### Theorem 1

Suppose Assumptions 1–5 hold. When $\gamma=\mu_{F}/L_{F}^{2}$, the parameter
$\alpha$ and gradient stepsize $\eta$ satisfy

$\alpha\in\Big{(}0,\frac{1}{r}\Big{]},\quad\eta\leq\min\Big{\\{}\frac{2n}{\mu_{r}}\sqrt{\frac{(1-c_{x})}{m_{1}}},\frac{\tilde{\lambda}_{\text{min}}(I-W)m_{2}^{2}}{L_{m}(m_{2}^{2}+1)}\Big{\\}},$

with $m_{1},m_{2}$ are defined in (11a) and (11b), then $\sup_{l\geq
k}\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||^{2}_{\text{F}}]$ and
$\sup_{l\geq
k}\mathbb{E}[||\mathbf{\tilde{X}}^{k+1}-\mathbf{H}^{k+1}||^{2}_{\text{F}}]$
converge to
$\lim\sup_{k\rightarrow\infty}\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||^{2}_{\text{F}}]$
and
$\lim\sup_{k\rightarrow\infty}\mathbb{E}[||\mathbf{\tilde{X}}^{k+1}-\mathbf{H}^{k+1}||^{2}_{\text{F}}]$,
respectively, at the linear rate $\mathcal{O}(\rho(\mathbf{A})^{k})$ with
$\rho(\mathbf{A})<1$. In addition, the NE-seeking error is bounded by

$\limsup_{k\rightarrow\infty}\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||^{2}_{\text{F}}]\leq
c_{7}\bar{\theta}^{2},\vspace*{-2mm}$ (9)

where
$c_{7}=((1-c_{x}-c_{5}\gamma^{2})c_{3}+c_{2}\gamma^{2})/\text{det}\mathbf{(I-A)}.$

Proof: In terms of Lemma 4, by induction we have

$\mathbf{V}^{k}\preceq\mathbf{A}^{k}\mathbf{V}^{0}+\sum_{l=0}^{k-1}\mathbf{A}^{l}\mathbf{b}.$
(10)

From equation (10), we can see that if $\rho(\mathbf{A})<1$, then
$\limsup_{k\rightarrow\infty}\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||^{2}_{\text{F}}]$
and
$\limsup_{k\rightarrow\infty}\mathbb{E}[||\mathbf{\tilde{X}}^{k+1}-\mathbf{H}^{k+1}||^{2}_{\text{F}}]$
all converge to a neighborhood of $0$ at the linear rate
$\mathcal{O}(\rho(\mathbf{A})^{k})$. Similar to the proof of Theorem 1 in
[17], we can obtain that
$\rho(\mathbf{A})\leq(1-\frac{\mu_{F}^{2}}{4L_{F}^{2}})<1$, if the positive
constants $\epsilon_{1},\epsilon_{2}$ and the stepsize $\eta$ satisfy the
following conditions,

$\begin{split}&\epsilon_{1}=\frac{4c_{2}\epsilon_{2}}{L_{F}^{2}},\eta\leq\min\Big{\\{}\frac{2n}{\mu_{r}}\sqrt{\frac{(1-c_{x})\epsilon_{2}}{m_{1}}},\frac{\tilde{\lambda}_{\text{min}}(I-W)m_{2}^{2}}{L_{m}(m_{2}^{2}+1)}\Big{\\}},\end{split}$

where

$\displaystyle
m_{1}=\frac{4c_{2}c_{4}}{||I-W||_{\text{F}}^{4}}+\frac{1}{4||I-W||_{\text{F}}^{2}}+\frac{c_{5}}{||I-W||_{\text{F}}^{4}},$
(11a) $\displaystyle
m_{2}=-1+\sqrt{1+\frac{\mu_{r}^{2}}{4n^{2}L_{m}}\sqrt{\frac{m_{1}}{(1-c_{x})\epsilon_{2}}}}.$
(11b)

Moreover, since
$\lim\limits_{k\rightarrow\infty}\sum_{l=0}^{k-1}\mathbf{A}^{l}=\mathbf{(I-A)}^{-1}$,
we have
$\limsup_{k\rightarrow\infty}\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||^{2}_{\text{F}}]\leq[\mathbf{(I-A)^{-1}b}]_{1}=c_{7}\bar{\theta}^{2}.\hfill\blacksquare$

###### Remark 2

Theorem 1 shows that CDP-NES achieves linear convergence to a neighborhood of
the NE with a linear convergence rate $\mathcal{O}(\rho(\mathbf{A})^{k})$,
where $\rho(\mathbf{A})\leq 1-\mu_{F}^{2}/4L_{F}^{2}$. Based on the definition
of $\mu_{F}$ and $L_{F}$ in Lemmas 1 and 2, the convergence rate is dependent
on the stepsize $\eta$, the number of players, properties of the game, and the
connectivity of the communication graph. Moreover, the convergence accuracy is
inversely related to the maximum noise variance $\bar{\theta}$. Specifically,
a smaller $\bar{\theta}$ leads to a more accurate convergence point. If there
is no Laplacian noise, i.e., $\bar{\theta}=0$, Algorithm 1 converges linearly
to the NE. However, as discussed in Section 5, reducing the noise variance
compromises the degree of differential privacy, indicating an inherent trade-
off between convergence accuracy and differential privacy.

##  5 Privacy analysis

In this section, we demonstrate that the CDP-NES algorithm ensures the
differential privacy of all agents’ cost functions.

We use $\mathcal{O}^{k}$ to denote the information transmitted between agents
at time step $k$, i.e.,
$\mathcal{O}^{k}=\\{\mathcal{C}(\mathbf{\tilde{x}}_{(i)}^{k}-\mathbf{h}_{i}^{k})\mid\forall
i\in\mathcal{V}\\}$. Consider any two adjacent function sets
$\mathcal{S}^{(1)}$ and $\mathcal{S}^{(2)}$, and only the cost function
$J_{i_{0}}$ is different between the two sets, i.e., $J_{i_{0}}^{(1)}\neq
J_{i_{0}}^{(2)}$ and $J_{i}^{(1)}=J_{i}^{(2)},\forall i\neq i_{0}.$ Prior to
presenting the privacy result, we introduce the following assumption:

###### Assumption 6

The gradient of agent $i$’s objective function is uniformly bounded, i.e.,
there exists a positive constant $M$ such that
$||\nabla_{i}J_{i}(\mathbf{x})||_{1}\leq M$ for all
$\mathbf{x}\in\mathbb{R}^{n},i\in\mathcal{V}$.

Assumption 6 is widely used in existing differentially private works [9, 11]
and it is crucial for privacy analysis.

###### Theorem 2

For any finite number of iterations $K$, under Assumption 6, CDP-NES preserves
$\epsilon_{i}$-differential privacy for a given $\epsilon_{i}>0$ of each agent
$i$’s cost function if the noise parameter satisfies $\theta_{i}>2\gamma\eta
KM/\epsilon_{i}$, where $\epsilon_{i}$ denotes the cumulative privacy budget
over $K$ iterations for agent $i$.

Proof: See Appendix 8.2.

###### Remark 3

The privacy analysis in Theorem 2 relaxes the assumption of uniform second-
order gradients (Assumption 4 in [19]), demonstrating that our privacy-
preserving algorithm can be applied to a wider class of problems. Furthermore,
unlike the decaying noise approach in [19], which risks privacy as convergence
is reached, Algorithm 1 maintains constant noise variance, enhancing privacy
protection.

###### Remark 4

In this paper, we consider that each agent has an unconstrained action set. If
$\Omega=\Omega_{1}\times\Omega_{2}\cdots\times\Omega_{n}$ is a nonempty,
convex and compact set, agent can update their local variable using a
projection operator

$\mathbf{x}_{(i)}^{k+1}=P_{\Omega}\\{\mathbf{\tilde{x}}_{(i)}^{k}-\gamma(\mathbf{\hat{x}}_{(i)}^{k}-\mathbf{\hat{x}}_{(i),w}^{k})-\gamma\eta\nabla_{i}J_{i}(\mathbf{x}_{(i)}^{k})\mathbf{e}_{i}\\}$
(12)

where $P_{\Omega}$ denotes the Euclidean projection operator onto $\Omega$ and
updates for other variables are the same in Algorithm 1. In this case, the
corresponding analyses are similar to the presented ones by utilizing the non-
expansive property of the projection operators [6]. By imposing a constraint
on $\Omega$, the bounded gradient requirement in Assumption 6 can be
satisfied. Additionally, the proposed algorithm can be directly adapted to
scenarios where agents’ actions are multi-dimensional.

##  6 SIMULATIONS

Figure 1: Residual
($\mathcal{R}=||\mathbf{X}^{k}-\mathbf{X}^{\star}||_{\text{F}}$) v.s. number
of iterations for the differential-private NE seeking in Wang and Başar [12],
the compressed NE seeking (C-DNES) [17] and the proposed CDP-NES algorithm
with different privacy budgets.

Consider a randomly generated directed communication network consisting of
$n=50$ agents. The connectivity control game [26] is considered, where the
sensors try to find a tradeoff between the local objective, e.g., source
seeking, and the global objective, e.g., maintaining connectivity with other
sensors. The cost function of agent $i$ is defined as follows,

$\displaystyle J_{i}(\mathbf{x})=l_{i}^{c}(x_{i})+l_{i}^{g}(\mathbf{x}),$ (13)

where $l_{i}^{c}(x_{i})=r_{ii}x_{i}^{\top}x_{i}+x_{i}^{\top}r_{i}+b_{i}$,
$l_{i}^{g}(\mathbf{x})=\sum\limits_{j\in S_{i}}c_{ij}||x_{i}-x_{j}||^{2}$,
$S_{i}\subseteq V$ denotes the physical neighbor set of sensor $i$, and
$x_{i}=[x_{i1},x_{i2}]^{\top}\in\mathbb{R}^{2}$ denotes the position of sensor
$i$, $r_{ii},r_{i},b_{i},c_{ij}>0$ are constants.

In this simulation, the parameters are set as
$r_{ii}=b_{i}=i,r_{i}=\begin{bmatrix}i&i\end{bmatrix}^{\top}$ and
$c_{ij}=1,\forall i,j\in V$. Furthermore, there is $S_{i}=\\{i+1\\}$ for
$i\in\\{1,2,\ldots,49\\}$ and $S_{50}=\\{1\\}$. Moreover, we consider that
$x_{i}\in[-10,10]^{2},\forall i\in\mathcal{V}$. To address the box
constraints, a projection operator is included in the proposed approach as in
(12). The unique Nash equilibrium of the game is $x^{\star}_{ij}=-0.5$ for
$i\in\\{1,2,\ldots,50\\},j\in\\{1,2\\}$. Meanwhile, $\mathbf{x}_{(i)}^{0}$ are
randomly generated in $[0,1]^{100}$, $\mathbf{h}_{i}^{0}=\mathbf{0}$, the
scaling paramater $\alpha$ and the consensus stepsize $\gamma$ are set to
$0.01$. For data compression, we adopt the stochastic quantization compressor
with $b=2$ and $q=\infty$ as shown in [21]. As shown in [17], transmitting
this compressed message needs $(b+1)d+l$ bits if a scalar can be transmitted
with $l$ bits while maintaining sufficient precision. In contrast, each agent
sends $dl$ bits at each iteration when adopting NE seeking algorithm without
compression. In this simulation, we choose $l=32$.

By setting the gradient stepsize as $\eta=0.01$ and experimenting with
different cumulative privacy budgets $\epsilon_{i}=\epsilon=1,2,5,\forall
i\in\mathcal{V}$ over $K=8000$ iterations, Fig. 1 demonstrates that compared
to the compressed NE seeking (C-DNES) [17] without privacy preservation, CDP-
DNES maintains a similar linear convergence rate as C-DNES but converges to a
neighborhood of the NE due to the effect of perturbed noise. Notably, a
reduction in $\epsilon$ results in an increased residual error, indicating
that enhanced privacy levels compromise accuracy.

Additionally, we compare the proposed CDP-DNES with the existing
differentially-private NE seeking algorithm by Wang and Başar [12]. By
aligning the stepsize and diminishing sequence with those utilized in [12] and
setting the differential privacy degree to $\epsilon=1$, Fig. 1 illustrates
that within the same time iteration, CDP-DNES converges faster and generates
smaller residual than Wang and Başar [12].

Furthermore, the effectiveness of compression mechanism is illustrated in Fig.
2. To reach a specific level of error, our proposed CDP-NES matches C-DNES in
communication efficiency measured by total number of transmitted bits.
Comparing to Wang and Başar’s approach [12], CDP-NES significantly reduces the
number of transmitted bits, enhancing communication efficiency by two order of
magnitude.

Figure 2: Total numbers of transmitted bits of different algorithms to obtain
$\mathcal{R}\leq 0.02$.

##  7 CONCLUSION AND FUTURE WORK

In this paper, we studied differentially private distributed Nash equilibrium
seeking over directed networks with compressed communication. By injecting
random noise before difference compression, a novel compressed and
differentially private distributed NE seeking approach is proposed to save
communication efficiency and achieve differential privacy simultaneously.
Moreover, linear convergence and $\epsilon$-differential privacy is rigorously
proved. Future works may focus on distributed NE seeking with coupling
equality constraints. In addition, it is of interest to rigorously investigate
the relationship between compressors and privacy performance.

## References

  * [1] Z. Ma, D. S. Callaway, and I. A. Hiskens, “Decentralized charging control of large populations of plug-in electric vehicles,” _IEEE Trans. Control Syst. Technol._ , vol. 21, no. 1, pp. 67–78, 2011.
  * [2] S. Grammatico, “Dynamic control of agents playing aggregative games with coupling constraints,” _IEEE Trans. Autom. Control_ , vol. 62, no. 9, pp. 4537–4548, 2017.
  * [3] W. Saad, Z. Han, H. V. Poor, and T. Basar, “Game-theoretic methods for the smart grid: An overview of microgrid systems, demand-side management, and smart grid communications,” _IEEE Signal Processing Magazine_ , vol. 29, no. 5, pp. 86–105, 2012.
  * [4] J. Koshal, A. Nedić, and U. V. Shanbhag, “Distributed algorithms for aggregative games on graphs,” _Oper Res._ , vol. 64, no. 3, pp. 680–704, 2016.
  * [5] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking: A gossip-based algorithm,” _Automatica_ , vol. 72, pp. 209–216, 2016.
  * [6] T. Tatarenko, W. Shi, and A. Nedić, “Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking,” _IEEE Trans. Autom. Control_ , vol. 66, no. 11, pp. 5342–5353, 2020.
  * [7] R. Dong, W. Krichene, A. M. Bayen, and S. S. Sastry, “Differential privacy of populations in routing games,” in _Proc. 54th IEEE Conf. Decis. Control (CDC)_ , 2015, pp. 2798–2803.
  * [8] T. A. Gerhart and A. Steinberg, “Proposition 24: Protecting california consumers by expanding protections, ensuring governmental oversight, and safeguarding the law from special interests,” _California Initiative Review (CIR)_ , vol. 2020, no. 1, p. 12, 2020.
  * [9] M. Ye, G. Hu, L. Xie, and S. Xu, “Differentially private distributed nash equilibrium seeking for aggregative games,” _IEEE Trans. Autom. Control_ , vol. 67, no. 5, pp. 2451–2458, 2021.
  * [10] Y. Lin, K. Liu, D. Han, and Y. Xia, “Statistical privacy-preserving online distributed nash equilibrium tracking in aggregative games,” _IEEE Trans. Autom. Control_ , vol. 69, no. 1, pp. 323–330, 2023.
  * [11] J. Wang, J.-F. Zhang, and X. He, “Differentially private distributed algorithms for stochastic aggregative games,” _Automatica_ , vol. 142, p. 110440, 2022.
  * [12] Y. Wang and T. Basar, “Ensuring both accurate convergence and differential privacy in nash equilibrium seeking on directed graphs,” _IEEE Trans. Autom. Control_ , pp. 1–8, 2024.
  * [13] C.-X. Shi and G.-H. Yang, “Distributed Nash equilibrium computation in aggregative games: An event-triggered algorithm,” _Inf. Sci._ , vol. 489, pp. 289–302, 2019.
  * [14] W. Huo, K. F. E. Tsang, Y. Yan, K. H. Johansson, and L. Shi, “Distributed Nash equilibrium seeking with stochastic event-triggered mechanism,” _Automatica_ , vol. 162, p. 111486, 2023.
  * [15] Z. Chen, J. Ma, S. Liang, and L. Li, “Distributed Nash equilibrium seeking under quantization communication,” _Automatica_ , vol. 141, p. 110318, 2022\.
  * [16] M. Ye, Q.-L. Han, L. Ding, S. Xu, and G. Jia, “Distributed Nash equilibrium seeking strategies under quantized communication,” _IEEE/CAA J. Autom. Sin._ , vol. 11, no. 1, pp. 103–112, 2024.
  * [17] X. Chen, Y. Wu, X. Yi, M. Huang, and L. Shi, “Linear convergent distributed nash equilibrium seeking with compression,” _arXiv preprint arXiv:2211.07849_ , 2022.
  * [18] X. Chen, W. Huo, Y. Wu, S. Dey, and L. Shi, “An efficient distributed Nash equilibrium seeking with compressed and event-triggered communication,” _arXiv preprint arXiv:2311.13994_ , 2023.
  * [19] A. Xie, X. Yi, X. Wang, M. Cao, and X. Ren, “Compressed differentially private distributed optimization with linear convergence,” _IFAC-PapersOnLine_ , vol. 56, no. 2, pp. 8369–8374, 2023.
  * [20] X. Yi, S. Zhang, T. Yang, T. Chai, and K. H. Johansson, “Communication compression for distributed nonconvex optimization,” _IEEE Trans. Autom. Control_ , vol. 68, no. 9, pp. 5477–5492, 2023.
  * [21] X. Liu and Y. Li, “Linear convergent decentralized optimization with compression,” in _Proc. 9th Int. Conf. Learn. Repr. (ICLR)_ , 2021.
  * [22] A. Beznosikov, S. Horváth, P. Richtárik, and M. Safaryan, “On biased compression for distributed learning,” _arXiv preprint arXiv:2002.12410_ , 2020.
  * [23] X. Chen, L. Huang, L. He, S. Dey, and L. Shi, “A differentially private method for distributed optimization in directed networks via state decomposition,” _IEEE Trans. Control Netw. Syst._ , vol. 10, no. 4, pp. 2165–2177, 2023.
  * [24] C.-K. Yu, M. Van Der Schaar, and A. H. Sayed, “Distributed learning for stochastic generalized Nash equilibrium problems,” _IEEE Trans. Signal Proces._ , vol. 65, no. 15, pp. 3893–3908, 2017.
  * [25] K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik, “Distributed learning with compressed gradient differences,” _arXiv preprint arXiv:1901.09269_ , 2019.
  * [26] M. Ye, “Distributed robust seeking of Nash equilibrium for networked games: An extended state observer-based approach,” _IEEE Trans. Cybern._ , vol. 52, no. 3, pp. 1527–1538, 2020.
  * [27] Y. Liao, Z. Li, K. Huang, and S. Pu, “A compressed gradient tracking method for decentralized optimization with linear convergence,” _IEEE Trans. Autom. Control_ , vol. 67, no. 10, pp. 5622–5629, 2022.

##  8 Appendix

###  8.1 Proof of Lemma 4

We derive two inequalities in terms of NE-seeking error and compression error,
respectively.

NE-seeking error:

Based on Proposition 1 in [6], we conclude that
$\mathbf{X}^{\star}=\mathbf{X}^{\star}-\gamma\mathbf{F}_{a}(\mathbf{X}^{\star}),\forall\gamma>0$.
Thus, we can obtain

$\displaystyle||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||_{\text{F}}^{2}$ (14)
$\displaystyle=||\mathbf{X}^{k}-\gamma\mathbf{F}_{a}(\mathbf{X}^{k})+\gamma(I-W)\mathbf{E}^{k}+\bm{\xi}^{k}-\mathbf{X}^{\star}+\gamma\mathbf{F}_{a}(\mathbf{X}^{\star})||_{\text{F}}^{2}$
$\displaystyle\leq
c_{1}||\mathbf{X}^{k}-\gamma\mathbf{F}_{a}(\mathbf{X}^{k})-\mathbf{X}^{\star}+\gamma\mathbf{F}_{a}(\mathbf{X}^{\star})||_{\text{F}}^{2}$
$\displaystyle+\frac{c_{1}}{c_{1}-1}(2\gamma^{2}||I-W||_{\text{F}}^{2}||\mathbf{E}^{k}||_{\text{F}}^{2}+2||\bm{\xi}||^{2}_{\text{F}}),$

where the last equality comes from Lemma 5 in [27] with $c_{1}>1$.

Next, we bound

$\displaystyle||\mathbf{X}^{k}-\gamma\mathbf{F}_{a}(\mathbf{X}^{k})-\mathbf{X}^{\star}+\gamma\mathbf{F}_{a}(\mathbf{X}^{\star})||_{\text{F}}^{2}$
(15)
$\displaystyle=||\mathbf{X}^{k}-\mathbf{X}^{\star}||_{\text{F}}^{2}+\gamma^{2}||\mathbf{F}_{a}(\mathbf{X}^{k})-\mathbf{F}_{a}(\mathbf{X}^{\star})||_{\text{F}}^{2}$
$\displaystyle-2\gamma\langle\mathbf{F}_{a}(\mathbf{X}^{k})-\mathbf{F}_{a}(\mathbf{X}^{\star}),\mathbf{X}^{k}-\mathbf{X}^{\star}\rangle$
$\displaystyle\leq(1+\gamma^{2}L_{F}^{2}-2\gamma\mu_{F})||\mathbf{X}^{k}-\mathbf{X}^{\star}||_{\text{F}}^{2},$

where the last inequality is based on Lemma 1 and Lemma 2.

From (15), we have
$\min\\{1+\gamma^{2}L_{F}^{2}-2\gamma\mu_{F}\\}=(1-\mu_{F}^{2}/L_{F}^{2})>0$.
Combining (14) and (15) after taking taking
$c_{1}=\frac{2L_{F}^{2}-\mu_{F}^{2}}{2L_{F}^{2}-2\mu_{F}^{2}}$, we have

$\displaystyle||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||_{\text{F}}^{2}$
$\displaystyle\leq
c_{1}(1+\gamma^{2}L_{F}^{2}-2\gamma\mu_{F})||\mathbf{X}^{k}-\mathbf{X}^{\star}||_{\text{F}}^{2}$
(16)
$\displaystyle+\frac{2c_{1}\gamma^{2}||I-W||_{\text{F}}^{2}}{c_{1}-1}||\mathbf{E}^{k}||_{\text{F}}^{2}+\frac{2c_{1}}{c_{1}-1}||\bm{\xi}^{k}||_{\text{F}}^{2},$

Then, from Lemma 3, we can obtain

$\displaystyle\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{\star}||_{\text{F}}^{2}\mid\mathcal{F}^{k}]$
(17) $\displaystyle\leq
c_{1}(1+\gamma^{2}L_{F}^{2}-2\gamma\mu_{F})\mathbb{E}[||\mathbf{X}^{k}-\mathbf{X}^{\star}||_{\text{F}}^{2}\mid\mathcal{F}^{k}]$
$\displaystyle+c_{2}\gamma^{2}\mathbb{E}[||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]+c_{3}\bar{\theta}^{2},$

where
$c_{2}=\frac{4c_{1}||I-W||_{\text{F}}^{2}C}{c_{1}-1},c_{3}=\frac{8c_{1}||I-W||_{\text{F}}^{2}n^{2}}{c_{1}-1}+\frac{4c_{1}n^{2}}{c_{1}-1}$.

Compression error:

Denote $\mathcal{C}_{r}(\mathbf{X}^{k})=\mathcal{C}(\mathbf{X}^{k})/r$,
according to (4e), for $0<\alpha\leq\frac{1}{r}$,

$\begin{split}&||\mathbf{\tilde{X}}^{k+1}-\mathbf{H}^{k+1}||^{2}_{\text{F}}\\\
=&||\mathbf{\tilde{X}}^{k+1}-\mathbf{\tilde{X}}^{k}+\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}-\alpha
r\frac{\mathbf{Q}^{k}}{r}||^{2}_{\text{F}}\\\
=&||\mathbf{\tilde{X}}^{k+1}-\mathbf{\tilde{X}}^{k}+\alpha
r(\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}-\mathcal{C}_{r}(\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}))||^{2}_{\text{F}}\\\
\leq&\tau_{1}\Big{[}\alpha
r||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}-\mathcal{C}_{r}(\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k})||^{2}_{\text{F}}\\\
&+(1-\alpha
r)||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}\Big{]}+\frac{\tau_{1}}{\tau_{1}-1}||\mathbf{\tilde{X}}^{k+1}-\mathbf{\tilde{X}}^{k}||^{2}_{\text{F}},\\\
\end{split}$ (18)

where in the first inequality we use the result of Lemma 5 in [27] with
$\tau_{1}=1+\alpha r\delta$.

Taking conditional expectation on both sides of (18), we obtain

$\begin{split}&\mathbb{E}[||\mathbf{\tilde{X}}^{k+1}-\mathbf{H}^{k+1}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&\leq\tau_{1}[\alpha r(1-\delta)+(1-\alpha
r)]\mathbb{E}[||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&+\frac{\tau_{1}}{\tau_{1}-1}\mathbb{E}[||\mathbf{\tilde{X}}^{k+1}-\mathbf{\tilde{X}}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}],\\\
\end{split}$ (19)

where the inequality holds based on Assumption 2.

Moreover, we have

$\begin{split}&\mathbb{E}[||\mathbf{\tilde{X}}^{k+1}-\mathbf{\tilde{X}}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&=\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{k}-(\bm{\xi}^{k+1}-\bm{\xi}^{k})||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&\leq
2\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]+2\mathbb{E}[||\bm{\xi}^{k+1}-\bm{\xi}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&\leq
2\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]+8n^{2}\bar{\theta}^{2}.\\\
\end{split}$ (20)

Next, we bound
$\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]$.

$\begin{split}&\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{X}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&=\mathbb{E}[||\gamma(I-W)\mathbf{E}^{k}-\gamma(\mathbf{F}_{a}(\mathbf{X}^{k})-\mathbf{F}_{a}(\mathbf{X}^{\star}))+\bm{\xi}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&\leq
3\gamma^{2}||(I-W)||^{2}_{\text{F}}\mathbb{E}[||\mathbf{E}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&+3\gamma^{2}L_{F}^{2}\mathbb{E}[||\mathbf{X}^{k}-\mathbf{X}^{\star}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]+3\mathbb{E}[||\bm{\xi}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&\leq
6C\gamma^{2}||(I-W)||^{2}_{\text{F}}\mathbb{E}[||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&+3\gamma^{2}L_{F}^{2}\mathbb{E}[||\mathbf{X}^{k}-\mathbf{X}^{\star}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]+(12\gamma^{2}||(I-W)||^{2}_{\text{F}}+6)n^{2}\bar{\theta}^{2}.\end{split}$
(21)

Bringing (20) and (21) into (19) and denoting $c_{4}=\frac{6(1+\alpha
r\delta)}{\alpha r\delta}>1,c_{x}=\tau_{1}[\alpha r(1-\delta)+(1-\alpha
r)]=1-\alpha^{2}r^{2}\delta^{2}<1$, we have

$\begin{split}&\mathbb{E}[||\mathbf{X}^{k+1}-\mathbf{H}^{k+1}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]\\\
&\leq
c_{4}\gamma^{2}L^{2}_{F}\mathbb{E}[||\mathbf{X}^{k}-\mathbf{X}^{\star}||_{\text{F}}^{2}\mid\mathcal{F}^{k}]\\\
&+(c_{x}+c_{5}\gamma^{2})\mathbb{E}[||\mathbf{\tilde{X}}^{k}-\mathbf{H}^{k}||^{2}_{\text{F}}\mid\mathcal{F}^{k}]+c_{6}\bar{\theta}^{2},\\\
\end{split}$ (22)

where $c_{5}=2c_{4}C||(I-W)||^{2}_{\text{F}}$ and $c_{6}=(2c_{4}+6)n^{2}$.

###  8.2 Proof of Theorem 2

From CDP-NES, it is clear that the observation sequence
$\mathcal{O}=\\{\mathcal{O}^{k}\\}_{k=0}^{K}$ is uniquely determined by the
noise sequences $\bm{\xi}=\\{\bm{\xi}^{k}\\}_{k=0}^{K}$ and compression
randomness sequence $\bm{\zeta}=\\{\bm{\zeta}^{k}\\}_{k=0}^{K}$, where
$\bm{\zeta}^{k}=[\bm{\zeta}_{1}^{k},\bm{\zeta}_{2}^{k},\ldots,\bm{\zeta}_{n}^{k}]\in\mathbb{R}^{n\times
n}$ is a matrix and its row denotes the compression perturbation of
$\mathbf{\tilde{x}}_{i}^{k}-\mathbf{h}_{i}^{k}$. We use function
$\mathcal{Z}_{\mathcal{F}}$ to denote the relation, i.e.,
$\mathcal{O}=\mathcal{Z}_{\mathcal{F}}(\bm{\xi},\bm{\zeta})$, where
$\mathcal{F}=\\{\mathbf{X}^{0},\mathbf{H}^{0},W,\mathcal{S}\\}$. From
Definition 2, to show the differential privacy of the cost function
$J_{i_{0}}$, we need to show that the following inequality holds for any
observation $\mathcal{O}$ and any pair of adjacent cost function sets
$\mathcal{S}^{(1)}$ and $\mathcal{S}^{(2)}$,

$\displaystyle P\\{(\bm{\xi},\bm{\zeta})$
$\displaystyle\in\Psi\mid\mathcal{Z}_{\mathcal{F}}^{(1)}((\bm{\xi},\bm{\zeta})\in\mathcal{O}\\}$
$\displaystyle\leq
e^{\epsilon}P\\{(\bm{\xi},\bm{\zeta})\in\Psi\mid\mathcal{Z}_{\mathcal{F}}^{(2)}(\bm{\xi},\bm{\zeta})\in\mathcal{O}\\},$

where
$\mathcal{F}^{(l)}=\\{\mathbf{X}^{0},\mathbf{H}^{0},W,\mathcal{S}^{(l)}\\}$,
$l=1,2$, and $\Psi$ denotes the sample space.

Then it is indispensable to guarantee
$\mathcal{Z}_{\mathcal{F}}^{(1)}(\bm{\xi},\bm{\zeta})=\mathcal{Z}_{\mathcal{F}}^{(2)}(\bm{\xi},\bm{\zeta})$,
i.e.,

$\mathcal{C}(\mathbf{\tilde{x}}_{i}^{k,(1)}-\mathbf{h}_{i}^{k,(1)},\bm{\zeta}_{i}^{k})=\mathcal{C}(\mathbf{\tilde{x}}_{i}^{k,(2)}-\mathbf{h}_{i}^{k,(2)},\bm{\zeta}_{i}^{k}),$
(23)

$\forall i\in V,0\leq k\leq K.$

Since $\mathbf{h}^{0,(1)}_{i}=\mathbf{h}^{0,(2)}_{i}$, from the dynamics of
CDP-NES algorithm, we have
$\mathbf{h}^{k,(1)}_{i}=\mathbf{h}^{k,(2)}_{i},0\leq k\leq K,\forall
i\in\mathcal{V}$ if equation (23) is satisfied.

Then if the following equation holds

$\mathbf{\tilde{x}}_{i}^{k,(1)}=\mathbf{\tilde{x}}_{i}^{k,(2)},\bm{\zeta}_{i}^{k,(1)}=\bm{\zeta}_{i}^{k,(2)},\forall
i\in\mathcal{V},0\leq k\leq K,$ (24)

one obtains that

$\displaystyle
f_{c}(\mathbf{\tilde{x}}_{i}^{k,(1)}-\mathbf{h}_{i}^{k,(1)},\bm{\zeta}_{i}^{k,(1)})=f_{c}(\mathbf{\tilde{x}}_{i}^{k,(2)}-\mathbf{h}_{i}^{k,(2)},\bm{\zeta}_{i}^{k,(2)}).$
(25)

In order to ensure equation (24), the Laplace noise should satisfy

$\xi_{i}^{k,(1)}=\xi_{i}^{k,(2)},0\leq k\leq K,\forall i\neq i_{0}.$ (26)

Similarly, for agent $i_{0}$, at iteration $k=0$, we have

$\xi_{i_{0}}^{0,(1)}=\xi_{i_{0}}^{0,(2)}.$ (27)

For $k\geq 1$, since $J_{i_{0}}^{(1)}\neq J_{i_{0}}^{(2)}$, the noise should
satisfy

$\Delta\xi_{i_{0}}^{k}=-\Delta\mathbf{x}_{(i_{0})}^{k},1\leq k\leq K,$ (28)

where $\Delta\xi_{i_{0}}^{k}=\xi_{i_{0}}^{k,(1)}-\xi_{i_{0}}^{k,(2)}$ and
$\Delta\mathbf{x}_{(i_{0})}^{k}=\mathbf{x}_{(i_{0})}^{k,(1)}-\mathbf{x}_{(i_{0})}^{k,(2)}$.

In light of dynamics of variable $\mathbf{x}_{(i)}^{k}$ in CDP-NES and
Assumption 6, we have for all $k\geq 1$

$\displaystyle\|\Delta\mathbf{x}_{(i_{0})}^{k}\|_{1}$
$\displaystyle\leq\|\gamma\eta\nabla_{i_{0}}J_{i_{0}}(\mathbf{x}_{(i_{0})}^{k-1,(1)})-\gamma\eta\nabla_{i_{0}}J_{i_{0}}(\mathbf{x}_{(i_{0})}^{k-1,(2)})\|_{1}$
(29) $\displaystyle\leq 2\gamma\eta M.$

Denote
$\mathcal{R}^{(l)}=\\{(\bm{\xi}^{(l)},\bm{\zeta}^{(l)})|\mathcal{Z}_{\mathcal{F}^{(l)}}(\bm{\xi}^{(l)},\bm{\zeta}^{(l)})\in\mathcal{O}\\}$,
$l=1,2,$ then

$\displaystyle
P\\{(\bm{\xi}^{(l)},\bm{\zeta}^{(l)})\in\Psi|\mathcal{Z}_{\mathcal{F}^{(l)}}(\bm{\xi}^{(l)},\bm{\zeta}^{(l)})\in\mathcal{O}\\}$
(30)
$\displaystyle=\int_{\mathcal{R}^{(l)}}f_{\xi}(\bm{\xi}^{(l)})f_{c}(\mathbf{\tilde{X}}^{(l)}-\mathbf{H}^{(l)},\bm{\zeta}^{(l)})d\bm{\xi}^{(l)}d\bm{\zeta}^{(l)},$

where
$f_{\xi}(\bm{\xi}^{(l)})=\prod_{k=0}^{K}\prod_{i=1}^{n}\prod_{r=1}^{n}f_{L}([\xi_{i}^{k,(l)}]_{r},\theta_{i})$
and
$f_{c}(\mathbf{\tilde{X}}^{(l)}-\mathbf{H}^{(l)},\bm{\zeta}^{(l)})=\prod_{k=0}^{K}\prod_{i=1}^{n}f_{c}(\mathbf{\tilde{x}}_{i}^{k,(l)}-\mathbf{h}_{i}^{k,(1)},\bm{\zeta}_{i}^{k,(l)})$

According to the above relation (26)-(28), we can obtain for any
$\bm{\xi}^{(1)}$, there exists a $\bm{\xi}^{(2)}$ such that
$\mathcal{Z}_{\mathcal{F}^{(1)}}(\bm{\xi}^{(1)},\bm{\zeta}^{(1)})=\mathcal{Z}_{\mathcal{F}^{(2)}}(\bm{\xi}^{(2)},\bm{\zeta}^{(2)})$.
As the converse argument is also true, the above defines a bijection. Hence,
for any $\bm{\xi}^{(2)}$, there exists a unique
$(\bm{\xi}^{(1)},\Delta\bm{\xi})$ such that
$\bm{\xi}^{(2)}=\bm{\xi}^{(1)}+\Delta\bm{\xi}$. Since $\Delta\bm{\xi}$ is
fixed and is not dependent on $\bm{\xi}^{(2)}$, we can use a change of
variables to obtain
$P\\{(\bm{\xi}^{(2)},\bm{\zeta}^{(2)})\\}\in\mathcal{R}^{(2)}\\}=\int_{\mathcal{R}^{(1)}}f_{\xi}(\bm{\xi}^{(1)}+\Delta\bm{\xi})f_{c}(\mathbf{\tilde{X}}^{(1)}-\mathbf{H}^{(1)},\bm{\zeta}^{(1)})d\bm{\xi}^{(1)}d\bm{\zeta}^{(1)}.$

Hence, we have

$\displaystyle\frac{P\\{(\bm{\xi},\bm{\zeta})\in\Psi|\mathcal{Z}_{\mathcal{F}^{(1)}}(\bm{\xi},\bm{\zeta})\in\mathcal{O}\\}}{P\\{(\bm{\xi},\bm{\zeta})\in\Psi|\mathcal{Z}_{\mathcal{F}^{(2)}}(\bm{\xi},\bm{\zeta})\in\mathcal{O}\\}}=\frac{P\\{(\bm{\xi}^{(1)},\bm{\zeta}^{(1)})\in\mathcal{R}^{(1)}\\}}{P\\{(\bm{\xi}^{(2)},\bm{\zeta}^{(2)})\in\mathcal{R}^{(2)}\\}}$
(31)
$\displaystyle=\frac{\int_{\mathcal{R}^{(1)}}f_{\xi}(\bm{\xi}^{(1)})f_{c}(\mathbf{\tilde{X}}^{(1)}-\mathbf{H}^{(1)},\bm{\zeta}^{(1)})d\bm{\xi}^{(1)}d\bm{\zeta}^{(1)}}{\int_{\mathcal{R}^{(1)}}f_{\xi}(\bm{\xi}^{(1)}+\Delta\bm{\xi})f_{c}(\mathbf{\tilde{X}}^{(1)}-\mathbf{H}^{(1)},\bm{\zeta}^{(1)})d\bm{\xi}^{(1)}d\bm{\zeta}^{(1)}}.$

Since

$\displaystyle\frac{f_{\xi}(\bm{\xi}^{(1)})d\bm{\xi}^{(1)}}{\
f_{\xi}(\bm{\xi}^{(1)}+\Delta\bm{\xi})d\bm{\xi}^{(1)}}=\prod_{k=0}^{K}\prod_{i=1}^{n}\prod_{r=1}^{n}\frac{f_{L}([\xi_{i}^{k,(1)}]_{r},\theta_{i})}{f_{L}([\xi_{i}^{k,(1)}+\Delta\xi_{i}^{k}]_{r},\theta_{i})}$
(32)
$\displaystyle\leq\prod\limits_{k=0}^{K}\prod\limits_{r=1}^{n}\exp\Big{(}\frac{\Big{|}[\Delta\xi_{i_{0}}^{k}]_{r}\Big{|}}{\theta_{i_{0}}}\Big{)}$
$\displaystyle=\exp\Big{(}\sum\limits_{k=0}^{K}\frac{||\Delta\xi_{i_{0}}^{k}||_{1}}{\theta_{i_{0}}}\Big{)}\leq\exp\Big{(}\frac{2\gamma\eta
KM}{\theta_{i_{0}}}\Big{)}=e^{\epsilon_{i_{0}}},$

we have

$\displaystyle P\\{(\bm{\xi},\bm{\zeta})\in$
$\displaystyle\Psi|\mathcal{Z}_{\mathcal{F}^{(1)}}(\bm{\xi},\bm{\zeta})\in\mathcal{O}\\}$
(33) $\displaystyle\leq
e^{\epsilon_{i_{0}}}P\\{(\bm{\xi},\bm{\zeta})\in\Psi|\mathcal{Z}_{\mathcal{F}^{(2)}}(\bm{\xi},\bm{\zeta})\in\mathcal{O}\\},$

which establishes the $\epsilon_{i_{0}}$-differential privacy of agent
$i_{0}$. The fact that $i_{0}$ can be arbitrary without loss of generality,
guarantees $\epsilon_{i}$-differential privacy of each agent $i$.


11institutetext: Department of Electrical Engineering, University of Kentucky,
Lexington, USA
11email<EMAIL_ADDRESS>
# Skin Lesion Segmentation Improved by Transformer-based Networks with Inter-
scale Dependency Modeling

Sania Eskandari  Janet Lumpp  Luis Sanchez Giraldo

###### Abstract

Melanoma, a dangerous type of skin cancer resulting from abnormal skin cell
growth, can be treated if detected early. Various approaches using Fully
Convolutional Networks (FCNs) have been proposed, with the U-Net architecture
being prominent To aid in its diagnosis through automatic skin lesion
segmentation. However, the symmetrical U-Net model’s reliance on convolutional
operations hinders its ability to capture long-range dependencies crucial for
accurate medical image segmentation. Several Transformer-based U-Net
topologies have recently been created to overcome this limitation by replacing
CNN blocks with different Transformer modules to capture local and global
representations. Furthermore, the U-shaped structure is hampered by semantic
gaps between the encoder and decoder. This study intends to increase the
network’s feature re-usability by carefully building the skip connection path.
Integrating an already calculated attention affinity within the skip
connection path improves the typical concatenation process utilized in the
conventional skip connection path. As a result, we propose a U-shaped
hierarchical Transformer-based structure for skin lesion segmentation and an
Inter-scale Context Fusion (ISCF) method that uses attention correlations in
each stage of the encoder to adaptively combine the contexts from each stage
to mitigate semantic gaps. The findings from two skin lesion segmentation
benchmarks support the ISCF module’s applicability and effectiveness. The code
is publicly available at https://github.com/saniaesk/skin-lesion-segmentation.

###### Keywords:

Deep learning Transformer Skin lesion segmentation Inter-scale context fusion.

##  1 Introduction

The skin comprises three layers: the epidermis, dermis, and hypodermis [13].
When exposed to ultraviolet radiation from the sun, the epidermis produces
melanin, which can be produced at an abnormal rate if too many melanocytes are
present. Malignant melanoma is a deadly form of skin cancer caused by the
abnormal growth of melanocytes in the epidermis; in 2023, it was estimated
that there would be 97,610 new cases of melanoma with a mortality rate of
8.18% [21]. The survival rate drops from 99% to 25% when melanoma is diagnosed
at an advanced stage due to its aggressive nature [22, 1]. Therefore, early
diagnosis is crucial in reducing the number of deaths from this disease.
Dermoscopy has been introduced to improve the diagnosis procedure; it is a
non-invasive technique that produces lighted and improved pictures of skin
patches. Dermatologists use this method to detect skin cancer, which was
formerly done by visual examination and manual screening, which was
ineffective and time-consuming [28]. Size, symmetry, boundary definition, and
irregularity of lesion shape are essential for identifying skin cancer.
Localization and delineation of lesions are required for both surgical
excision and radiation treatment [22]. Manual delineation is a tedious and
laborious task. Therefore, automatic segmentation becomes essential for
developing pre and post-diagnosis processes in computer-aided diagnosis (CAD);
however, automatic segmentation is challenging. Lighting and contrast
difficulties, underlying inter-class similarities and intra-class variations,
occlusions, artifacts, and various imaging tools impede automated skin lesion
segmentation. The scarcity of large datasets with expert-generated ground-
truth segmentation masks exacerbates the situation, hindering both model
training and trustworthy assessment.

Before the Deep Learning (DL) era, most of the segmentation algorithms were
based on hand-crafted and classical vision-based and conventional machine
learning-based techniques. Celebi et al. [10] utilized adaptive thresholding,
and in another study, [9], they investigated a region growing strategy, Erkol
et al. [11] applied the active contour method, and Hwang et al. [15] proposed
a hybrid segmentation pipeline with an unsupervised clustering remedy where a
hierarchical k-means with a level set technique was used. The aforementioned
algorithms rely on human-engineered features, which may be challenging to
construct and frequently have low invariance and discriminative ability. As a
result, the inadequacies of classic ML-based segmentation approaches emphasize
the need for more advanced DL-based methods capable of handling complex data
and producing more accurate results.

U-Net [19] is the de facto in segmentation tasks. This DL-based framework is a
cornerstone in medical image segmentation. U-Net is a hierarchical encoder-
decoder framework comprising successive convolution operations in the encoding
path, which downsample the spatial resolution while embedding the input space
in a high dimensional space. The encoder provides a highly semantic
representation, which is gradually upsampled in the decoding path to recover
the input’s spatial dimensions. Skip connections between the encoder and
decoder in this design are used to mitigate the loss of spatial information,
which is vital for segmentation tasks. Due to the modular design of the U-Net,
thousands of variants of this network have been introduced that alleviate any
shortcomings of the U-Net [3], e.g., U-Net++ [29], H-DenseUNet [16], Attention
U-Net [18], etc. U-Net++ [29] takes advantage of embedding nested U-Net
structures in each stage by using a dense flow of semantic information from
the encoder to the decoder with skip connections. Li et al. [16] replaced each
naive convolutional encoder block with residual blocks besides using dense
skip connections to extract more semantic information. However, applying
successive convolution operations in dense structures still could not prevent
the CNN-based U-shaped frameworks from suffering from having a limited
receptive field. Attention U-Net [18] utilized the image-grid-based gating
module that includes skip connections to let signals pass through and capture
the gradient of relevant localization information from the encoder path before
it merges with decoder features on the same scale. This strategy was the first
seminal medical image segmentation study investigating the attention
mechanism.

Transformer models in language translation tasks have been a huge success.
This is related to its ability to calculate the self-affinity between the
input tokens [23]. Dosovitskiy et al. [8] proposed a Vision Transformer (ViT)
which implements the attention mechanism on an image by partitioning the input
images into a 1D sequence of patches to address the lack of globality of
convolution operations. Soon, the Vision Transformer’s ability to capture
long-range dependencies in encoding the object’s shape information inspired
several studies that utilize the ViT for various tasks such as classification
[8] and segmentation [5]. However, due to the lack of intrinsic spatial
inductive bias (impeding the ViT from capturing local representation) and the
quadratic computational complexity of ViT (making ViT to be data hungry) with
respect to the number of patches, the vanilla ViT performs poorly in dense
prediction tasks like segmentation and object detection in comparison with the
CNN models. Therefore, to mitigate the loss of local interactions within ViT,
TransUNet [5], TransBTS [25], UCTransNet [24], and FAT-Net [26] successfully
bridge the CNN and Transformer designs in hybrid models. Due to the U-shaped
design’s success [5, 25, 26] hierarchical CNN-Transformer models tried
capturing long and local dependencies simultaneously. The main drawbacks of
these methods are that they still suffer from a high number of parameters and
are dependent on the pre-trained weights to perform competitively. UCTransNet
[24] investigated the semantic gap between encoder and decoder by designing a
new Transformer-based module over skip connections to fuse the multi-scale
spatial semantic information, but their method still requires pre-training
weights.

Thus, various studies, such as the Efficient Transformer [27] and the Swin
Transformer [17], have explored minimizing this computational burden to make
ViTs suited for segmentation tasks by delving into the inner structure of the
Transformer’s multi-head self-attention (MHSA) calculation or by changing the
tokenization process. Swin-Unet [4] is a hierarchical U-shaped pure
Transformer structure that successfully utilized a Linear Swin Transformer as
a main counterpart to segment the abdominal computer tomography inputs. Due to
the shifting window strategy in Swin blocks, Swin-Unet captures the contextual
information locally and is heavily dependent on pre-training weights. Huang et
al. [14] applied the Efficient Transformer from [27] for medical image
segmentation as a pure Transformer design, namely MISSFormer. Efficient
Transformer [27] utilizes the irreversible downsampling step after the patch
embedding to lessen the computational complexity, but this method suffers from
loss of spatial information.

Our Contribution – To address the aforementioned deficiencies, we propose a
new pure Transformer-based U-shaped structure that utilizes the efficient
attention mechanism by Shen et al. [20] to capture the global context in
linear complexity without redundant context extraction. Moreover, to shield
the U-Net-like structures from the semantic gaps between the encoder and
decoder, we devised a new module that uses an already calculated attention
correlation at various scales to fuse the attention information for better
localization. Our contributions are as follows: ❶ A novel Transformer-based
structure in a U-shaped framework to capture the global dependency in an
efficient manner without the need for pre-training weights (see Figure 1). ❷
The design of a new skip connection module that integrates the multi-scale
attention maps to lessen the encoder-decoder gap rather than the plain copy-
and-paste skip connection paradigm, namely Inter-Scale Context Fusion (ISCF).
It is noteworthy that this study is the extended abstract version of [12]. ❸
SOTA results on two public skin lesion segmentation datasets and publicly
available implementation source code via GitHub.

(a)

(b)

Figure 1: (a) Proposed method. Our U-shaped structure comprises modified
Efficient attention. (b) Our Efficient Transformer block.

##  2 Proposed Method

Our overall framework proposed in Figure 1 is a convolution-free hierarchical
U-shaped pure Transformer, designed for skin lesion segmentation. For an input
image $\textrm{Im}\in\mathbb{R}^{H\times W\times C}$, where $H$, $W$, and $C$
denote the spatial dimensions and channels, respectively, our structure, as in
Figure 1(a), uses the patch merging and patch expanding strategies from [17,
4]. The patch embedding module extracts overlapping patch tokens of size
$4\times 4$ from the embedded tokens ($X\in\mathbb{R}^{n\times d}$) and then
passes them through an encoder module with three stacked encoder blocks. Each
block has two consecutive Efficient Transformer blocks and a patch merging
layer that reduces spatial dimension (by merging $2\times 2$ tokens) while
doubling the channel dimension. The decoder expands the tokens by a factor of
two in each block and integrates the output of each patch-expanding layer with
the features forwarded by the fusion of the skip connection from the parallel
encoder layer using ISCF. This approach enables the network to obtain a
hierarchical representation.

###  2.1 Efficient Attention

Let $\mathbf{Q}$, $\mathbf{K}$, and $\mathbf{V}$ denote the Query, Key, and
Value matrices that are produced by the embedded tokens $X$ in each stage, and
$d$ is the embedding dimension. The standard self-attention equation is given
by:

$\displaystyle
S(\mathbf{Q},\mathbf{K},\mathbf{V})=\operatorname{softmax}\left(\frac{\mathbf{QK^{T}}}{\sqrt{d}}\right)\mathbf{V}.$
(1)

The standard self-attention mechanism has a quadratic computational complexity
($\mathcal{O}(n^{2})$), which limits its applicability in high-resolution
tasks. Shen et al. [20] proposed an approach called “Efficient Attention” that
takes advantage of the fact that regular self-attention creates repetitive
context matrix entries. They suggested a more efficient method for computing
self-attention, as follows:

$\displaystyle
E(\mathbf{Q},\mathbf{K},\mathbf{V})=\mathbf{\rho_{q}}(\mathbf{Q})(\mathbf{\rho_{k}}(\mathbf{K})^{\mathbf{T}}\mathbf{V}),$
(2)

where $\rho_{q}$ and $\rho_{k}$ are Softmax, normalization functions for the
Queries and Keys. Shifting the order of multiplication drastically decreases
the computation complexity to $\mathcal{O}(d^{2}n)$ when
$d_{v}=d,d_{k}=\frac{d}{2}$, which is a typical setting (see Figure 1(b)). In
contrast to naive dot-product attention (self-attention), efficient attention
does not first compute pairwise similarities between points. Instead, the keys
are represented as $d_{k}$ attention maps $\mathbf{k^{T}}_{j}$, with $j$
referring to position $j$ in the input feature. To sum up, according to Figure
1(b), our Efficient Transformer block applies the following operations:

$\displaystyle X_{1}$ $\displaystyle=E(\mathbf{Q},\mathbf{K},\mathbf{V})+X$
(3) $\displaystyle X^{\prime}$ $\displaystyle=\operatorname{Mix-
FFN}(\operatorname{LN}(X_{1}))+X_{1},$ (4)

where $\operatorname{LN}$ is a LayerNorm operation, and $\operatorname{Mix-
FFN}$ is an enhanced Feed Forward Network (FFN) operation. It has been proven
such a design can align features and make discriminative representations [14,
27], that mixes a $3\times 3$ convolution and an MLP into each FFN. This
operation actually plays as the dynamic positional encoding for each stage’s
Efficient transformer.

Figure 2: An overview of the Inter-Scale Context Fusion (ISCF) module. This
module applies to already calculated attention maps in each stage’s
Transformer block and produces a general context over stages to compensate for
the inter and intra-semantic gaps within the U-shaped design to improve the
performance.

###  2.2 Inter-scale Context Fusion

The ISCF module is displayed in Figure 2. Instead of simply concatenating the
features from the encoder and decoder layers, we devised a context fusion
module to decrease the encoder-decoder semantic gap. Our proposed module not
only can effectively provide spatial information to each decoder to recover
fine-grained details when producing output masks, but also it does not require
additional parameters for the model. Our proposed U-shaped structure is
defined as a three stage multi-scale representation coupled with an ISCF
module. Due to the hierarchical design of the structure, the attention maps’
shape at each level differs from the next one. Therefore, we used a Linear
layer in the first two stages two make the attention map sizes the same as the
last stage. This operation is done at the output of the ISCF module to remap
the attention maps to their original sizes. In the ISCF module, we utilize the
Global Pooling (GP) operation to produce a single value for each stage’s
attention correlation and concatenate them, followed by an FFN to amalgamate
the contribution of each global value into a scaling factor. Then each
attention map applies the point-wise production with the corresponding scaling
value and concatenates the resulting attention maps. Further, to adaptively
fuse these global contexts to lessen the mentioned semantic gaps, a $3\times
1\times 1$ convolution is used. Finally, the resulting context fusion tensor
adds to each plain skip connection from the encoder to the decoder to
highlight the spatial localization for better segmentation results.

##  3 Experimental Setup

The PyTorch library was used to implement our proposed architecture and was
run on a single RTX 3090 GPU. A batch size of 24 and an Adam solver with an
empirically chosen learning rate of $1e-4$ were used for a $100$ epochs
training. The loss function for the segmentation task was binary cross-
entropy.

###  3.1 Datasets

ISIC 2017 – The ISIC 2017 dataset [7] comprises 2,000 skin dermoscopic images
(cancer-positive and negative samples) with their corresponding annotations.
We used 600 samples for the test set, 150 samples for data validation, and
1,250 samples for training. Each sample has an original size of $576\times
767$ pixels. Images that are larger than $224\times 224$ pixels are resized
using the same pre-processing as [2].

ISIC 2018 – ISIC 2018 [6] provides independent datasets for the classification
and segmentation tasks for the first time, with 2,594 training (20% melanomas,
72% nevi, and 8% seborrheic keratoses). Like prior approaches [2], we used
1,815 samples for training, 259 for validation, and 520 for testing. We
downsize each sample image to $224\times 224$ pixels from its original size of
$2016\times 3024$ pixels.

###  3.2 Quantitative and Qualitative Results

In Table 1, the quantitative results for our proposed method are displayed. We
reported the performance of the model on the Dice score (DSC), sensitivity
(SE), specificity (SP), and accuracy (ACC). Our results show that the proposed
design can outperform SOTA methods without pre-training weights and having
fewer parameters. In addition, Figure 3 provides qualitative results that show
the network performs well with respect to the ground truth segmentation and
preserves the high-frequency details such as boundary information. It is
evident that the boundary information with an Efficient Transformer and the
ISCF module preserve high-frequency details effectively in comparison to the
naive Swin U-Net [4] and highlights the efficacy of the ISCF module in
compensating the information gap between encoder and decoder.

Figure 3: Qualitative results on ISIC 2018 dataset. Green represents the
ground truth contour and blue corresponds to the prediction mask contour.
Table 1: Performance comparison of the proposed method against SOTA approaches
on the ISIC 2017, and ISIC 2018 skin lesion segmentation tasks.

Methods | # Params(M) | ISIC 2017 | ISIC 2018
---|---|---|---
DSC | SE | SP | ACC | DSC | SE | SP | ACC
U-Net [19] | 14.8 | 0.8159 | 0.8172 | 0.9680 | 0.9164 | 0.8545 | 0.8800 | 0.9697 | 0.9404
Att U-Net [18] | 34.88 | 0.8082 | 0.7998 | 0.9776 | 0.9145 | 0.8566 | 0.8674 | 0.9863 | 0.9376
TransUNet [5] | 105.28 | 0.8123 | 0.8263 | 0.9577 | 0.9207 | 0.8499 | 0.8578 | 0.9653 | 0.9452
FAT-Net [26] | 28.75 | 0.8500 | 0.8392 | 0.9725 | 0.9326 | 0.8903 | 0.9100 | 0.9699 | 0.9578
Swin U-Net [4] | 82.3 | 0.9183 | 0.9142 | 0.9798 | 0.9701 | 0.8946 | 0.9056 | 0.9798 | 0.9645
Efficient Transformer (without ISCF) | 22.31 | 0.8998 | 0.8834 | 0.9530 | 0.9578 | 0.8817 | 0.8534 | 0.9698 | 0.9519
Efficient Transformer (with ISCF) | 23.43 | 0.9257 | 0.9321 | 0.9793 | 0.9698 | 0.9136 | 0.9284 | 0.9723 | 0.9630

###  3.3 Ablation Study

To investigate how various settings affect the performance of our model, we
conducted ablation studies on the number of times our proposed attention
strategy was used in skip connections, as well as on different input sizes. We
examined the effects of incorporating our proposed attention module at 1/4,
1/8, and 1/16 resolution scales. We studied the impact on our model by
selecting which pairs of scales $SL_{i}$ and $SL^{\prime}_{i}$ for
$i\in\left\\{{1,2,3}\right\\}$. As shown in Table 2, the segmentation
performance improved as we increased the number of skip connection modules
(scales), supporting our attention module’s efficacy in capturing a rich
representation. We also evaluated the impact of increasing the input size to
$384\times 384$ and found that while it led to slightly improved segmentation
results, it also incurred a higher computational cost.

Table 2: Ablation study on the ISIC 2018 skin lesion segmentation benchmark.

Setting | DSC | SE | SP | ACC
---|---|---|---|---
Using only $SL_{i}$ and $SL^{\prime}_{i}$ pairs ($i\in\\{1\\}$) | 0.9025 | 0.9305 | 0.9490 | 0.9451
Using $SL_{i}$ and $SL^{\prime}_{i}$ pairs ($i\in\\{1,2\\}$) | 0.9065 | 0.9274 | 0.9683 | 0.9597
Using $SL_{i}$ and $SL^{\prime}_{i}$ pairs ($i\in\\{1,2,3\\}$) | 0.9136 | 0.9284 | 0.9723 | 0.9630
Input image size $384\times 384$ | 0.9189 | 0.9265 | 0.9799 | 0.9659

##  4 Conclusion

The semantic gap between the encoder and decoder in a U-shaped Transformer-
based network can be mitigated by carefully recalibrating the already
calculated attention maps from each stage. In this study, not only do we
address the hierarchical semantic gap drawback, but also, our ISCF module
highlights the importance of spatial attention. ISCF module is a plug-and-play
and computation-friendly module that can effectively be applied to any
Transformer-based architecture. The qualitative and quantitative results
endorse the applicability of the proposed module.

## References

  * [1] Aghdam, E.K., Azad, R., Zarvani, M., Merhof, D.: Attention swin u-net: Cross-contextual attention mechanism for skin lesion segmentation. arXiv preprint arXiv:2210.16898 (2022)
  * [2] Alom, M.Z., Hasan, M., Yakopcic, C., Taha, T.M., Asari, V.K.: Recurrent residual convolutional neural network based on u-net (r2u-net) for medical image segmentation. arXiv preprint arXiv:1802.06955 (2018)
  * [3] Azad, R., Aghdam, E.K., Rauland, A., Jia, Y., Avval, A.H., Bozorgpour, A., Karimijafarbigloo, S., Cohen, J.P., Adeli, E., Merhof, D.: Medical image segmentation review: The success of u-net. arXiv preprint arXiv:2211.14830 (2022)
  * [4] Cao, H., Wang, Y., Chen, J., Jiang, D., Zhang, X., Tian, Q., Wang, M.: Swin-unet: Unet-like pure transformer for medical image segmentation. In: Computer Vision–ECCV 2022 Workshops: Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part III. pp. 205–218. Springer (2023)
  * [5] Chen, J., Lu, Y., Yu, Q., Luo, X., Adeli, E., Wang, Y., Lu, L., Yuille, A.L., Zhou, Y.: Transunet: Transformers make strong encoders for medical image segmentation. arXiv preprint arXiv:2102.04306 (2021)
  * [6] Codella, N., Rotemberg, V., Tschandl, P., Celebi, M.E., Dusza, S., Gutman, D., Helba, B., Kalloo, A., Liopyris, K., Marchetti, M., et al.: Skin lesion analysis toward melanoma detection 2018: A challenge hosted by the international skin imaging collaboration (isic). arXiv preprint arXiv:1902.03368 (2019)
  * [7] Codella, N.C., Gutman, D., Celebi, M.E., Helba, B., Marchetti, M.A., Dusza, S.W., Kalloo, A., Liopyris, K., Mishra, N., Kittler, H., et al.: Skin lesion analysis toward melanoma detection: A challenge at the 2017 international symposium on biomedical imaging (isbi), hosted by the international skin imaging collaboration (isic). In: 2018 IEEE 15th international symposium on biomedical imaging (ISBI 2018). pp. 168–172. IEEE (2018)
  * [8] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., Houlsby, N.: An image is worth 16x16 words: Transformers for image recognition at scale. In: International Conference on Learning Representations (2021), https://openreview.net/forum?id=YicbFdNTTy
  * [9] Emre Celebi, M., Alp Aslandogan, Y., Stoecker, W.V., Iyatomi, H., Oka, H., Chen, X.: Unsupervised border detection in dermoscopy images. Skin research and technology 13(4), 454–462 (2007)
  * [10] Emre Celebi, M., Wen, Q., Hwang, S., Iyatomi, H., Schaefer, G.: Lesion border detection in dermoscopy images using ensembles of thresholding methods. Skin Research and Technology 19(1), e252–e258 (2013)
  * [11] Erkol, B., Moss, R.H., Joe Stanley, R., Stoecker, W.V., Hvatum, E.: Automatic lesion boundary detection in dermoscopy images using gradient vector flow snakes. Skin Research and Technology 11(1), 17–26 (2005)
  * [12] Eskandari, S., Lumpp, J.: Inter-scale dependency modeling for skin lesion segmentation with transformer-based networks. In: Medical Imaging with Deep Learning, short paper track (2023), https://openreview.net/forum?id=JExQEfV5um
  * [13] Gordon, R.: Skin cancer: an overview of epidemiology and risk factors. In: Seminars in oncology nursing. vol. 29, pp. 160–169. Elsevier (2013)
  * [14] Huang, X., Deng, Z., Li, D., Yuan, X., Fu, Y.: Missformer: An effective transformer for 2d medical image segmentation. IEEE Transactions on Medical Imaging (2022)
  * [15] Hwang, Y.N., Seo, M.J., Kim, S.M.: A segmentation of melanocytic skin lesions in dermoscopic and standard images using a hybrid two-stage approach. BioMed Research International 2021, 1–19 (2021)
  * [16] Li, X., Chen, H., Qi, X., Dou, Q., Fu, C.W., Heng, P.A.: H-denseunet: hybrid densely connected unet for liver and tumor segmentation from ct volumes. IEEE transactions on medical imaging 37(12), 2663–2674 (2018)
  * [17] Liu, Z., Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang, Z., Lin, S., Guo, B.: Swin transformer: Hierarchical vision transformer using shifted windows. In: Proceedings of the IEEE/CVF international conference on computer vision. pp. 10012–10022 (2021)
  * [18] Oktay, O., Schlemper, J., Folgoc, L.L., Lee, M., Heinrich, M., Misawa, K., Mori, K., McDonagh, S., Hammerla, N.Y., Kainz, B., et al.: Attention u-net: Learning where to look for the pancreas. arXiv preprint arXiv:1804.03999 (2018)
  * [19] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical image computing and computer-assisted intervention. pp. 234–241. Springer (2015)
  * [20] Shen, Z., Zhang, M., Zhao, H., Yi, S., Li, H.: Efficient attention: Attention with linear complexities. In: Proceedings of the IEEE/CVF winter conference on applications of computer vision. pp. 3531–3539 (2021)
  * [21] Siegel, R.L., Miller, K.D., Wagle, N.S., Jemal, A.: Cancer statistics, 2023. CA: A Cancer Journal for Clinicians 73(1), 17–48 (2023). https://doi.org/https://doi.org/10.3322/caac.21763, https://acsjournals.onlinelibrary.wiley.com/doi/abs/10.3322/caac.21763
  * [22] Society, A.C.: Cancer facts and figures, 2023. https://www.cancer.org/content/dam/cancer-org/research/cancer-facts-and-statistics/annual-cancer-facts-and-figures/2023/slideshow-2023-cancer-facts-and-figures.pptx (2023), accessed: 2023-03-10
  * [23] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. Advances in neural information processing systems 30 (2017)
  * [24] Wang, H., Cao, P., Wang, J., Zaiane, O.R.: Uctransnet: rethinking the skip connections in u-net from a channel-wise perspective with transformer. In: Proceedings of the AAAI conference on artificial intelligence. vol. 36, pp. 2441–2449 (2022)
  * [25] Wang, W., Chen, C., Ding, M., Yu, H., Zha, S., Li, J.: Transbts: Multimodal brain tumor segmentation using transformer. In: Medical Image Computing and Computer Assisted Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France, September 27–October 1, 2021, Proceedings, Part I 24. pp. 109–119. Springer (2021)
  * [26] Wu, H., Chen, S., Chen, G., Wang, W., Lei, B., Wen, Z.: Fat-net: Feature adaptive transformers for automated skin lesion segmentation. Medical Image Analysis 76, 102327 (2022)
  * [27] Xie, E., Wang, W., Yu, Z., Anandkumar, A., Alvarez, J.M., Luo, P.: Segformer: Simple and efficient design for semantic segmentation with transformers. Advances in Neural Information Processing Systems 34, 12077–12090 (2021)
  * [28] Yu, L., Chen, H., Dou, Q., Qin, J., Heng, P.A.: Automated melanoma recognition in dermoscopy images via very deep residual networks. IEEE transactions on medical imaging 36(4), 994–1004 (2016)
  * [29] Zhou, Z., Siddiquee, M.M.R., Tajbakhsh, N., Liang, J.: Unet++: A nested u-net architecture for medical image segmentation. In: Deep learning in medical image analysis and multimodal learning for clinical decision support, pp. 3–11. Springer (2018)