# Echo of Neighbors: Privacy Amplification for Personalized Private
Federated Learning with Shuffle Model

Yixuan Liu1,2,3, Suyun Zhao1,2,3, Li Xiong4, Yuhan Liu1,2,3, Hong Chen1,2,3
Corresponding author: Hong Chen<EMAIL_ADDRESS>
###### Abstract

Federated Learning, as a popular paradigm for collaborative training, is
vulnerable against privacy attacks. Different privacy levels regarding users’
attitudes need to be satisfied locally, while a strict privacy guarantee for
the global model is also required centrally. Personalized Local Differential
Privacy (PLDP) is suitable for preserving users’ varying local privacy, yet
only provides a central privacy guarantee equivalent to the worst-case local
privacy level. Thus, achieving strong central privacy as well as personalized
local privacy with a utility-promising model is a challenging problem. In this
work, a general framework (APES) is built up to strengthen model privacy under
personalized local privacy by leveraging the privacy amplification effect of
the shuffle model. To tighten the privacy bound, we quantify the heterogeneous
contributions to the central privacy user by user. The contributions are
characterized by the ability of generating “echos” from the perturbation of
each user, which is carefully measured by proposed methods Neighbor Divergence
and Clip-Laplace Mechanism. Furthermore, we propose a refined framework
(S-APES) with the post-sparsification technique to reduce privacy loss in
high-dimension scenarios. To the best of our knowledge, the impact of
shuffling on personalized local privacy is considered for the first time. We
provide a strong privacy amplification effect, and the bound is tighter than
the baseline result based on existing methods for uniform local privacy.
Experiments demonstrate that our frameworks ensure comparable or higher
accuracy for the global model.

## Introduction

Federated Learning (FL) (McMahan et al. 2017) is an emerging machine learning
paradigm that allows multiple clients to train a global model collaboratively
while keeping the private raw data of each client locally. While not directly
sharing private data, recent works indicate that FL by itself is insufficient
to preserve privacy of users’ data. By observing the global model or
intermediate parameters during the training process, adversaries can infer the
membership of users or even reconstruct training records (Fredrikson, Jha, and
Ristenpart 2015; Zhu, Liu, and Han 2019; Nasr, Shokri, and Houmansadr 2019;
Xiong et al. 2021). These attacks can lead to severe data leakage, hence it is
necessary to provide additional protection with strict privacy guarantees for
both the global model and local parameters. Moreover, in practice, different
local privacy levels may be desired depending on users’ privacy preferences. A
one-size-fits-all approach would either downgrade the model utility or
sacrifice privacy protection for certain users. Thus, an open problem in FL is
how to provide strong central privacy as well as personalized local privacy
while maintaining model utility.

Methods | Personalization |  FL Process
---|---|---
Local |  Central
PLDP |  ✓ |  ✓ |  Weak
Uni-Shuffle |  ✗ |  ✓ |  ✓
APES |  ✓ |  ✓ |  ✓
S-APES |  ✓ |  ✓ |  Strong
Table 1: Comparison of related work. ✓denotes protected, ✗denotes unprotected.

Several recent works have attempted to address this problem. Personalized
Local Differential Privacy (PLDP) protects both local gradients and the global
model by perturbing gradients with heterogeneous parameters (Chen et al. 2016;
Li et al. 2020). The central privacy of the global model is equivalent to the
weakest local privacy. For achieving both strong central and local privacy, a
potential solution is the shuffle model (Bittau et al. 2017). It amplifies
central privacy by permuting data points randomly after local perturbation.
However, existing studies on shuffle model only focus on the scenarios where
local privacy requirements are assumed uniform (Uni-Shuffle for short)
(Erlingsson et al. 2019; Balle et al. 2019; Girgis et al. 2021; Feldman,
McMillan, and Talwar 2022). To the best of our knowledge, there is no work
that provides both strong central privacy for the global model and
personalized local privacy guarantees, while achieving strong utility of
global model (cf. Tab.1).

To narrow this gap, we propose APES, a privacy Amplification framework for
PErsonalized private federated learning with Shuffle model (cf. Fig. 1). APES
gains a strong privacy amplification effect. Unlike previous works that just
permute data, both data points and privacy parameters are randomly shuffled in
APES. Clip-Laplace Mechanism is also introduced to implement the framework
without damaging model utility. In order to mitigate the privacy-loss
explosion problem caused by high dimensions, we propose S-APES which improves
APES with the post-Sparsification. The basic idea is to select only
informative dimensions of gradients after perturbation and pad the rest, which
saves privacy cost.

To bound the privacy of APES and S-APES, we carefully quantify the obfuscation
effects contributed by users with heterogeneous privacy parameters. First,
inspired by Feldman, McMillan, and Talwar, the central privacy of a specific
user is boosted by the rest of the users who generate “echos” of her with
heterogeneous probabilities; next, to measure the probabilities, we propose
Neighbor Divergence and Clip-Laplace Mechanism for limited output range and
bounded divergence among distinct output distributions by users’ local
randomizers; then “echos” are transformed into certain form, and a tight
privacy bound is derived.

Our main contributions are summarized as follows:

(i) We propose privacy amplification frameworks via shuffle model for
personalized private federated learning. APES strikes a better balance between
central privacy and model utility with Neighbor Divergence and Clip-Laplace
Mechanism. Based on it, improved S-APES enhances the privacy for the high-
dimension scene.

(ii) We provide theoretical analysis for both privacy and convergence bound of
the proposed frameworks. To the best of our knowledge, the shuffling effect on
personalized local differential privacy is considered for the first time and a
strong privacy amplification effect is yielded. The central privacy bound is
tighter than the bound derived by naïvely adopting existing methods for
unified privacy.

(iii) Comprehensive experiments are conducted to confirm that APES and S-APES
achieve comparable or higher accuracy for the global model with stronger
central privacy compared to the state-of-the-art methods without downgrading
personalized local privacy guarantee.

## Preliminaries

In this section, we illustrate the privacy definition, shuffle model and
several properties of differential privacy, all of which are prepared for the
proposed methods.

### Central and Local Differential Privacy

Differential privacy (DP) (Dwork, Roth et al. 2014) is a _de facto_ standard
that is widely accepted to preserve privacy in FL. The notion is typically
built up in a central setting where a trusted server can access the raw data.
Local differential privacy (LDP) (Erlingsson, Pihur, and Korolova 2014), on
the other hand, offers users a stronger privacy guarantee for the settings
without assumption of trusted server.

######  Definition 1 (Differential Privacy).

For any $\epsilon,\delta\geq 0$, a randomized algorithm
$M:\mathcal{D}\rightarrow\mathcal{Z}$ is $(\epsilon,\delta)$-differential
privacy if for any neighboring datasets $D,D^{\prime}\in\mathcal{D}$ and any
subsets $S\subseteq\mathcal{Z}$,

$\Pr[M(D)\in S]\leq e^{\epsilon}\Pr[M(D^{\prime})\in S]+\delta$

######  Definition 2 (Local Differential Privacy).

For any $\epsilon,\delta\geq 0$, an algorithm
$M:\mathcal{D}\rightarrow\mathcal{Z}$ is $(\epsilon,\delta)$-local
differential privacy if $\forall g,g^{\prime}\in\mathcal{D}$ and $\forall
z\in\mathcal{Z}$,

$\Pr[M(g)=z]\leq e^{\epsilon}\Pr[M(g^{\prime})=z]+\delta$

Figure 1: Procedure of APES. Gradients $g_{i}$ trained by user data $x_{i}$
are randomized locally, then privacy parameters $\epsilon_{i}$ and $g_{i}$ are
shuffled separately. Analyzer acts as the curator to aggregate and calibrate
gradients $\tilde{g}_{i}$ for global model.

### Shuffle-based Privacy

Shuffle model (Bittau et al. 2017) was proposed to strengthen central privacy
while preserving local user privacy. Given $n$ datapoints as the dataset
$D=\\{g_{1},g_{2},...,g_{n}\\}$, each $g_{i}\in D$ owned by user $i$ is
perturbed locally by a randomizer $M:\mathcal{D}\rightarrow\mathcal{Z}$ to
ensure $(\epsilon^{l},\delta^{l})$-LDP before being sent to shuffler.
Shuffler, a trusted third party, permutes and releases all the datapoints by
algorithm $S:Z\rightarrow Z$ to analyzer. Untrusted analyzer aggregates all
the datapoints. The process $P=S\circ M$ satisfies at least
$(\epsilon^{l},\delta^{l})$-DP against analyzer (cf. Lemma 1). Recent works
(Erlingsson et al. 2019; Balle et al. 2019; Girgis et al. 2021; Feldman,
McMillan, and Talwar 2022) achieve a much stronger central privacy guarantee,
which is considered as privacy amplification effect by shuffling. Among
existing works, Feldman, McMillan, and Talwar provides a tight privacy upper
bound for single-message summation. Take neighboring datasets $D$ and
$D^{\prime}$ that only differ at $g_{1}$ (or $g^{\prime}_{1}$), any perturbed
datapoint $\tilde{g}_{i}$ can be regarded as a sampling from the distribution
of a specific perturbed point $\tilde{g}_{1}$ or $\tilde{g}^{\prime}_{1}$ with
probability $\exp(-\epsilon^{l})$. By this observation, the privacy bound is
yielded.

### Privacy Tools

As a general technique to implement DP, Laplace Mechanism (Dwork, Roth et al.
2014) perturbs numerical values.

######  Definition 3 (Laplace Mechanism).

Given any function $f:\mathcal{D}\rightarrow\mathcal{Z}^{d}$ and neighboring
datasets $D$ and $D^{\prime}$, let $\Delta f=\max||f(D)-f(D^{\prime})||_{1}$
be the sensitivity function, Laplace mechanism $M(D)=f(D)+Y^{d}$ satisfies
$\epsilon$-DP, where $Y^{d}$ is random variable $i.i.d$ drawn from
distribution $Lap(0,\frac{\Delta f}{\epsilon})$.

Composition theorems provide tight bounds for the algorithm combined with
several DP blocks.

######  Lemma 1 (Parallel Composition).

(Yu et al. 2019) Given an $(\epsilon_{i},\delta_{i})$-DP algorithm
$M_{i}:\mathcal{D}\rightarrow\mathcal{Z}$ for $i\in[m]$, a class of
$\\{M_{i}\\}_{i\in[m]}$ on disjoint subsets of $D$ is
$(\max{\epsilon_{i}},\max{\delta_{i}})$-DP.

######  Lemma 2 (Advanced Composition).

(Dwork, Roth et al. 2014) Given an $(\epsilon_{i},\delta_{i})$-DP algorithm
$M_{i}:\mathcal{D}\rightarrow\mathcal{Z}$ for $i\in[m]$, the sequence of
$\\{M_{i}\\}_{i\in[m]}$ on the same dataset $D$ under m-fold composition is
$(\epsilon^{\prime},\delta^{\prime}+m\delta)$-DP where
$\epsilon^{\prime}=\epsilon\sqrt{2m\log{1/\delta^{\prime}}}+m\epsilon(e^{\epsilon}-1)$.

No matter what dataset or query is adopted, any privacy mechanism can be
reduced to a basic random response with the same privacy level (Kairouz, Oh,
and Viswanath 2015).

######  Lemma 3 (Degraded Privacy).

For any $\epsilon$-DP mechanism $M$, for $X:\\{x,\bar{x}\\}$,
$\exists\tilde{M}$ dominates $M$ where:

$\Pr[\tilde{M}(x)=z]=\left\\{\begin{array}[]{rcl}\frac{e^{\epsilon}}{1+e^{\epsilon}},&z=x\\\
\frac{1}{1+e^{\epsilon}},&z=\bar{x}\end{array}\right.$

## Proposed Methods

This section illustrates our methods for a strong privacy amplification
effect. We first introduce Clip-Laplace Mechanism to implement the effect.
Then two frameworks are proposed. APES is a general framework which shuffles
both privacy parameters and gradients, the improved S-APES sparsifies
dimensions without downgrading shuffling effect.

### Clip-Laplace Mechanism

To make bounding privacy while maintaining model accuracy possible, it is
necessary to introduce a mechanism for LDP with a finite and fixed output
range. Existing works on this task provide non-fixed output ranges (Geng et
al. 2018), or increase noise scale when ranges of input and output are not
overlapped (Holohan et al. 2018; Croft, Sack, and Shi 2022). To address this
issue, we introduce a variant of Laplace Mechanism, _Clip-Laplace_ , which
provides $\epsilon$-DP for continuous real values with the same finite output
ranges.

######  Definition 4 (Clip-Laplace Mechanism).

Given any function $f:\mathcal{X}\rightarrow\mathcal{Y}^{d}$ and sensitivity
$\Delta f=\max||f(X)-f(X^{\prime})||_{1}$ for any neighboring datasets $X$ and
$X^{\prime}$. Clip-Laplace Mechanism is
$M:\mathcal{Y}^{d}\rightarrow\mathcal{Z}^{d}$. Each $Z\in\mathcal{Z}^{d}$ is a
r.v. i.i.d. drawn from distribution $CLap(f(x),\lambda,A)$ of which the
probability density function is defined as follows:

$p(z)=\left\\{\begin{array}[]{rcl}\frac{1}{2\lambda
S}\exp{(-\frac{|z-f(x)|}{\lambda})},&-A\leq z\leq A\\\
0,&otherwise\end{array}\right.$

where normalization factor
$S=1-\frac{1}{2}\exp(\frac{-A+f(x)}{\lambda})-\frac{1}{2}\exp(\frac{-A-f(x)}{\lambda})$
and $A\geq\Delta f/2$.

######  Theorem 1.

Clip Laplace mechanism preserves $\epsilon$-LDP when the $f(x)\in[-\Delta
f/2,\Delta f/2]$, and $\lambda=\Delta f/\epsilon$.

The proof is provided in Appendix A.

_Discussion._ (i) When achieving the same level of $\epsilon$-LDP, the
variance of Clip-Laplacian outputs is smaller than classic Laplacian outputs.
This property is based on the assumption of symmetric limited range of inputs
(cf. Theorem 1), which is reasonable for many fields such as gradients
aggregation, location statistics, financial analysis and so on. (ii) The Clip-
Laplacian outputs are biased. A feasible solution for correction is to
calibrate the outputs with the expectation, which can be estimated when
privacy parameters are given.

### APES Framework

We formalize APES, a privacy Amplification framework for PErsonalized private
federated learning with Shuffle Model. The framework includes three
procedures: local updating, shuffling and analyzing process with three parties
separately. Convergence upper bound of APES is given at last.

#### Architecture

Consider 3 parties: (i) $n$ users, each holds a dataset $X_{i}$ and a
randomizer $M_{i}$ satisfying $\epsilon^{l}_{i}$-LDP. (ii) A shuffler with
algorithm $S$. (iii) An analyzer, trains global model with shuffled messages.
The process $P=S\circ M$ ensures $(\epsilon^{c},\epsilon^{c})$-DP for global
model, where $M=(M_{1},...,M_{n})$ with
$\epsilon^{l}=(\epsilon^{l}_{1},...,\epsilon^{l}_{n})$ for dimension level.

#### Basic Framework

Algorithm 1 outlines the procedures of APES. We denote clip bound by $C$,
learning rate by $\alpha$ and training epochs by $T$. Main procedures are as
follows:

  * •

_Local Updating_. Each user randomizes each dimension of model gradient
$g_{i}$ with $\epsilon^{l}_{i}$ by applying Clip-Laplace Mechanism. Both
perturbed gradient $\tilde{g}_{i}$ and $\epsilon_{i}^{l}$ are sent to
Shuffler. To keep the order of dimensions, dimension index $k$ of
$\tilde{g}_{i}$ is sent as well.

  * •

_Shuffling Process_. Shuffler shuffles $\\{\tilde{g}_{i}\\}_{i\in[n]}$ within
the same dimension, $\\{\epsilon_{i}^{l}\\}_{i\in[n]}$ is also permuted.

  * •

_Analyzing Process_. Considering Clip-Laplace Mechanism is biased, the average
gradient $\tilde{g}$ needs to be calibrated. We cannot calibrate
$\tilde{g}_{i}$ one by one as the correspondence of $\epsilon^{l}_{i}$ and
$g_{i}$ is invisible to analyzer. Empirically, we observe that the value of
$\tilde{g}$ is close to the value of $\mathbb{E}[\tilde{\bar{g}}]$ (cf. Fig. 4
in Appendix C), where $\bar{g}=\frac{1}{n}\sum_{i=1}^{n}{g_{i}}$,
$\mathbb{E}[\tilde{\bar{g}}]=\frac{1}{n}\sum_{i=1}^{n}{\mathbb{E}[\tilde{\bar{g}}_{i}]}$
and $\tilde{\bar{g}}_{i}\sim CLap(\bar{g},2C/\epsilon^{l}_{i},C)$. Hence we
can estimate the clean gradients $\bar{g}$ by approximating
$\mathbb{E}[\tilde{g}]$ with $\mathbb{E}[\tilde{\bar{g}}]$. Specifically,
$\mathbb{E}[\tilde{g}]$ is estimated by $\tilde{g}$, and each term of
$E[\tilde{\bar{g}}]$ with $\epsilon^{l}_{i}$ is as follows:

$\mathbb{E}[\tilde{\bar{g}}_{i}]=\frac{(C+\lambda_{i})\cdot(e_{1}-e_{2})+2\bar{g}}{2-e_{1}-e_{2}}$
(1)

where $e_{1}=e^{\frac{-C-\bar{g}}{\lambda_{i}}}$,
$e_{2}=e^{\frac{-C+\bar{g}}{\lambda_{i}}}$ and
$\lambda_{i}=2C/\epsilon^{l}_{i}$.

Algorithm 1 Basic Framework: APES

$T$, $\\{(X_{i},\epsilon^{l}_{i})\\}_{i\in[n]}$, $h(w)$, $C$, $\alpha$.

model $w$

Analyzer initializes and broadcasts $w^{(0)}$.

for $t=1,2,...,T$ do

$\triangleright$ Local Updating

for each user $i\in[n]$ do

$w_{i}\leftarrow w^{(t)}$ $\triangleright$ Update local model

$g_{i}\leftarrow\nabla_{w_{i}}h(w_{i},X_{i})$

$\bar{g_{i}}\leftarrow{\rm Clip}(g_{i},-C,C)$

$\tilde{g_{i}}\leftarrow{Randomize(\cdot)}$ $\triangleright$ Local
perturbation

user $i$ uploads $(\tilde{g_{i}},\epsilon^{l}_{i})$ to Shuffler

$\triangleright$ Shuffling Process

for each dimension $k\in[d]$ do

generate permutation $\pi_{k}$ over $[d]$

$\\{(\tilde{g}_{i,\pi_{k}(k)},k)\\}_{i\in[n]}\leftarrow{\rm
Shuffle}(\pi_{k},\\{\tilde{g}_{i,k}\\}_{i\in[n]})$

generate permutation $\pi$ over $[n]$

$\\{\epsilon_{\pi(i)}^{l}\\}_{i\in[n]}\leftarrow{\rm
Shuffle}(\pi,\\{\epsilon_{i}^{l}\\}_{i\in[n]})$ $\triangleright$ Shuffle
$\epsilon$

send $\\{\\{(\tilde{g}_{i,\pi_{k}(k)},k)\\}_{i\in[n]}\\}_{k\in[d]}$ and
$\\{\epsilon_{\pi(i)}^{l}\\}_{i\in[n]}$

$\triangleright$ Analyzing Process

for each dimension $k\in[d]$ do

$\tilde{g}_{k}\leftarrow\frac{1}{n}\sum_{i}\tilde{g}_{i,k}$ $\triangleright$
Aggregate by dimension

$\hat{g}\leftarrow{\rm Calibrate}(\tilde{g},\\{\epsilon_{i}\\}_{i\in[n]})$

$w^{(t+1)}\leftarrow w^{(t)}-\alpha\hat{g}$ and broadcast. return $w^{(T)}$

#### Convergence Analysis

To demonstrate the performance of global model under Clip-Laplace
perturbation, we provide the upper bound of convergence of Algorithm 1 with
the objective function $h(w;w^{(0)})=F(w)+\frac{\mu}{2}||w-w^{(0)}||^{2}$. The
regularization term $\frac{\mu}{2}||w-w^{(0)}||^{2}$ of $h$ is introduced for
the ease of calculation (Li et al. 2020).

######  Theorem 2 (Convergence Upper Bound).

After T aggregations, the expected decrease in the global loss function
$f(w)=\frac{1}{n}\sum_{i}F_{i}(w)$ of APES is bounded as follows:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]\leq
a_{1}^{T}(\mathbb{E}[f(\tilde{w}^{(0)})]-f(w^{*}))$
$\displaystyle+\frac{a_{1}^{T}-1}{a_{1}-1}(O(a_{2}C/\min(\epsilon^{l}_{i}))+O(a_{3}C^{2}/\min(\epsilon^{l}_{i})^{2}))$

where $a_{1}=1+\frac{2\beta(\alpha B-1)}{\mu}+\frac{2\beta
LB(\alpha+1)}{\mu\bar{\mu}}+\frac{2\beta
LB^{2}(1+\alpha)^{2}}{\bar{\mu}^{2}},a_{2}=L(\frac{1}{\mu}+\frac{BL(1+\alpha)}{\bar{\mu}}),a_{3}=\frac{L}{2}$.

The proof refers to Appendix B.

_Discussion._ The convergence upper bound increases as the bias and variance
(the second and the third term) of Clip-Laplace perturbation grow, of which
the influence is the same as classic Laplace Mechanism.

### S-APES Framework

To strengthen privacy in the high-dimension scenario, we propose S-APES
framework, which improves APES with post-Sparsification technique.

Since gradients are usually high-dimensional, limiting the number of
dimensions helps to save the privacy cost (Ye and Hu 2020; Duan, Ye, and Hu
2022). Selecting part of dimensions with large magnitude keeps majority of
information (Aji and Heafield 2017) and reduces privacy loss, but needs extra
protection since the selection itself is data-dependent process. To select
informative dimensions without breaching privacy, we propose post-
parsification technique.

#### Post Sparsification

Algorithm 2 demonstrates the local process of S-APES with post-sparsification.
Concretely, each user $i$ is asked to select the largest $b$ absolute values
over $d$ dimensions of $\tilde{g}_{i}$. To keep the selected dimension index
private, the selection is executed after local perturbation. For avoiding the
shuffling effect degradation caused by members reduction, each user pads the
rest of $(d-b)$ dimensions with perturbed $0$. Denote sparsification process
by $K$, the whole process of S-APES is defined as $P_{s}=S\circ K\circ M$.

Algorithm 2 $Randomize(\cdot)$ for S-APES

$\\{(g_{i},\epsilon^{l}_{i})\\}_{i\in[n]}$, $C$.

perturbed gradient $\tilde{g}_{i}$

$\tilde{g}_{i}\leftarrow{\rm CLap}(0,(d\Delta f)/\epsilon_{i}^{l},C)$
$\triangleright$ Clip-Laplace perturbing

$I_{b}\leftarrow\\{k|k\in max({|\tilde{g}_{i,k}|}_{k\in[d]})\\}^{b}$
$\triangleright$ Post-top-b index set

for each index $k\notin I_{b}$ do

$\tilde{g}_{i,k}\leftarrow{\rm CLap}(0,(d\Delta f)/\epsilon_{i}^{l},C)$
$\triangleright$ Dummy padding return $\tilde{g_{i}}$

## Privacy Analysis

In this section, we first derive a naïve privacy bound based on existing
works, then show the local and central privacy bound of our frameworks. The
sketch of privacy amplification effect analysis is provided at last.

### Baseline Results

To analyze the privacy amplification effect of shuffling under personalized
LDP, the most naïve way is applying existing shuffling bounds (Erlingsson et
al. 2019; Balle et al. 2019; Girgis et al. 2021; Feldman, McMillan, and Talwar
2022) on heterogeneous local privacy budgets, i.e., $\epsilon^{l}_{i}$, with
classic Laplace Mechanism. However, different $\epsilon^{l}_{i}$ lead to
different scales of the Laplacian distributions and their divergence may be
infinite. As a result, the central privacy may be unbounded. Hence based on
the previous work (Feldman, McMillan, and Talwar 2022) we can only approximate
the true bound by using the same maximum $\epsilon^{l}_{i}$ for all users:

$\epsilon^{c}\leq\ln(1+\frac{e^{\max(\epsilon_{i}^{l})}-1}{e^{\max(\epsilon_{i}^{l})}+1}(\frac{8(e^{\max(\epsilon_{i}^{l})}\log(4/\delta))^{1/2}}{n^{1/2}}+\frac{8e^{\max(\epsilon^{l}_{i})}}{n}))$
(2)

### Main Results

Proposed techniques Clip-Laplace Mechanism and Neighbor Divergence make
analyzing privacy amplification effect possible. Without loss of generality,
we suppose two neighboring datasets $D=\\{g_{1},g_{2},...,g_{n}\\}$ and
$D^{\prime}=\\{g^{\prime}_{1},g_{2},...,g_{n}\\}$ that only differs at $g_{1}$
or $g^{\prime}_{1}$ of user $1$, and provide privacy bounds of our frameworks
as follows.

######  Theorem 3 (Local Bound).

Given $\epsilon^{l}=(\epsilon^{l}_{1},...,\epsilon^{l}_{n})$, the local
process $M=(M_{1},...,M_{n})$ of APES on $d$-dimension gradients satisfies
$\epsilon^{l}_{i}$-LDP in dimension level, $d\epsilon^{l}_{i}$-LDP in user
level for each user $i$.

_Discussion._ Our frameworks achieve personalized LDP for each user. This
comes from Theorem 1.

######  Theorem 4 (Central Upper bound).

Let $i,j\in[n]$, $\delta_{s}\in[0,1]$,
$\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}\geq 16\ln(4/\delta_{s})$,
$P=S\circ M$ of APES satisfies $(\epsilon^{c},\delta^{c})$-DP where
$\delta^{c}\leq\frac{e^{\epsilon^{l}_{j}}-1}{e^{\epsilon^{l}_{j}}+1}\delta_{s}$,

$\epsilon^{c}\leq\ln(1+\frac{e^{\max(\epsilon^{l}_{j})}-1}{e^{\max(\epsilon^{l}_{j})}+1}(\frac{8(\ln(4/\delta_{s}))^{1/2}}{(\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n})^{1/2}}+\frac{8}{\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n}}))$

when $\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}\geq 16\ln(4/\delta_{s})$,
$\delta_{s}\in[0,1]$ and
$p_{ij}=\frac{\epsilon^{l}_{i}}{\epsilon^{l}_{j}}\cdot\frac{1-e^{-\epsilon^{l}_{j}}}{1-e^{-\epsilon^{l}_{i}}}\cdot
e^{-\max(\epsilon^{l}_{i},\epsilon^{l}_{j})}$.

_Discussion._ APES gains a strong central privacy for dimension level. Theorem
4 indicates most users are provided with a much stricter central privacy as
$\epsilon^{c}$ than their local privacy $\epsilon^{l}_{i}$. A sketch of the
proof is provided in the following section.

######  Proposition 1 (User Level Central Bound).

With ${\delta^{\prime}}^{uc}>0$ and $0<b\leq d$, the process $P_{s}=S\circ
K\circ M$ of S-APES with $b$-dimension sparsification is
$(\epsilon^{uc},\delta^{uc})$-DP where
$\epsilon^{uc}=\epsilon^{c}\sqrt{4b\ln(1/\delta^{uc})}+2b\epsilon^{c}(\exp{(\epsilon^{c})}-1)$
and $\delta^{uc}={\delta^{\prime}}^{{uc}}+2b\delta^{c}$.

_Discussion._ S-APES achieves the same dimension-level $\epsilon^{c}$ as APES.
Considering dimensions of a gradient are not independent and extracting $b$
dimensions leads to $2b$ sensitivity, we derive the user-level privacy
amplification effect by composition theorems. Note that $\epsilon^{uc}$ grows
linearly with $b$, which implies privacy loss reduces when fewer dimensions
are uploaded by post-sparsification.

### EoN: Privacy Amplification Analysis

To analyze privacy of proposed frameworks, we first introduce Neighbor
Divergence, then present the sketch of Echo of Neighbors (EoN) analysis for
privacy amplification effect.

#### Neighbor Divergence

We introduce _Neighbor Divergence_ to characterize how well a user’s output
distribution closes the gap between itself and other users’ distributions.
Concretely, it defines the distance among output distributions of local
randomizers of users with heterogeneous privacy budgets and different raw
datapoints.

######  Definition 5 (Neighbor Divergence).

Consider any $g_{s}$, $g_{t}\in\mathcal{D}$ and randomizers $M_{i}$, $M_{j}$
satisfying $\epsilon^{l}_{i}$, $\epsilon^{l}_{j}$-LDP separately. Let
$\mu^{(s)}_{i}$ and $\mu^{(t)}_{j}$ be distributions of $M_{i}(g_{s})$ and
$M_{j}(g_{t})$ respectively, $U^{(s)}_{i}\sim\mu^{(s)}_{i}$,
$U^{(t)}_{j}\sim\mu^{(t)}_{j}$, the neighbor divergence between
$\mu^{(s)}_{i}$ and $\mu^{(t)}_{j}$ is defined as:

$D_{N}(\mu^{(s)}_{i}||\mu^{(t)}_{j})=\max\limits_{S\subseteq
Supp(U^{(s)}_{i})}[\ln\frac{\Pr[U^{(s)}_{i}\in S]}{\Pr[U^{(t)}_{j}\in S]}]$

In particular, the neighbor divergence under Clip-Laplace Mechanism is
demonstrated as follows.

######  Lemma 4.

Let $f(x)\in[-C,C]$, $\lambda=\Delta f/\epsilon^{l}$ and $\Delta f=2C$, the
neighbor divergence between distribution $\mu^{(s)}_{i}$ and $\mu^{(t)}_{j}$
under Clip-Laplace Mechanism is
$D_{N}(\mu^{(s)}_{i}||\mu^{(t)}_{j})\leq\ln(\alpha\frac{\epsilon^{l}_{i}}{\epsilon^{l}_{j}}e^{(\frac{(\epsilon^{l}_{i}+\epsilon^{l}_{j})}{2}+\frac{A|\epsilon^{l}_{i}-\epsilon^{l}_{j}|}{2C})})$.
Specifically,
$D_{N}(\mu^{(s)}_{i}||\mu^{(t)}_{j})\leq\ln(\frac{\epsilon^{l}_{i}}{\epsilon^{l}_{j}}\cdot\frac{1-e^{-\epsilon^{l}_{j}}}{1-e^{-\epsilon^{l}_{i}}}\cdot
e^{\max(\epsilon^{l}_{i},\epsilon^{l}_{j})})$ when $A=C$. $\alpha$ denotes
$\frac{({1-\frac{1}{2}\exp(\frac{{\epsilon^{l}_{j}(-A+C)}}{2C})-\frac{1}{2}\exp(\frac{\epsilon^{l}_{j}(-A-C)}{2C})})}{(1-\frac{1}{2}\exp(\frac{{\epsilon^{l}_{i}(-A+C)}}{2C})-\frac{1}{2}\exp(\frac{\epsilon^{l}_{i}(-A-C)}{2C}))}$.

#### A sketch of EoN Analysis

We analyze the central privacy bound in Theorem 4 with the observation of
_Echos of Neighbors_. There are three main steps: (i) After shuffling, output
distributions of the rest users are converted into the same distribution of
user $1$ which can be seen as “echos” by neighbor divergence. (ii) Then all
the “echos” are transformed into certain distributions which disentangle from
different $\epsilon^{l}_{i}$ by degraded privacy. These distributions form a
mixed distribution. (iii) Finally, we measure the divergence between the mixed
distributions on $D$ and $D^{\prime}$.

Step (i). Recall that LDP mechanism $M_{i}:\mathcal{Y}\rightarrow\mathcal{Z}$
satisfying $\epsilon^{l}_{i}$-LDP for any $i\in[n]$. Based on neighbor
divergence, for any $\mu_{i}^{(s)}$ and $\mu_{j}^{(t)}$ we have
$p_{ij}\leq{\mu_{i}^{(s)}}/{\mu_{j}^{(t)}}\leq
e^{-D_{N}(\mu_{j}^{(t)}||\mu^{(s)}_{i})}$ by Definition 5. Specifically, for
any user’s distribution $\mu_{i}^{(i)}$ on $g_{i}\in
D\backslash\\{g_{1},g^{\prime}_{1}\\}$, “echo” $\mu_{j}^{(1)}$(or
${\mu^{\prime}}_{j}^{(1)}$) of user $1$ with $g_{1}$ (or $g^{\prime}_{1}$) is
generated as follows:

$\mu_{i}^{(i)}=\frac{p_{ij}}{2}\mu_{j}^{(1)}+\frac{p_{ij}}{2}{\mu^{\prime}}_{j}^{(1)}+(1-p_{ij})\gamma_{i}^{(i)}$
(3)

The distribution
$\gamma_{i}^{(i)}=\mu_{i}^{(i)}-p_{ij}/2\cdot(\mu_{j}^{(1)}+{\mu^{\prime}}_{j}^{(1)})/(1-p_{ij})$.
The idea is inspired by a prior work (Feldman, McMillan, and Talwar 2022).
Consider the situation that both $g$ and $\epsilon^{l}$ are shuffled, the
correspondence between $g_{i}$ and $\epsilon^{l}_{i}$ is broken. An adversary
cannot decide which $\epsilon^{l}_{j}$ is used for perturbing $g_{1}$, hence
any value in $\\{\epsilon^{l}_{i}\\}$ is possible. Based on it we derive a
general bound, then consider the worst-case situation with the largest
$\epsilon^{l}_{j}$ on $g_{1}$ for the upper bound at step (iii).

Step (ii). Except for user $1$, the mixed distribution of multiple
$\mu_{j}^{(1)}$ with different $\epsilon^{l}_{j}$ from $n-1$ users is still
hard to bound. Hence, with the help of degraded privacy (cf. Lemma 3) we
transform $(\mu_{j}^{(1)}+{\mu^{\prime}}_{j}^{(1)})$ into
$(\rho^{(1)}+{\rho^{\prime}}^{(1)})$ for any $j\in[n]$, then
$\epsilon^{l}_{j}$ is disentangled from $\mu_{j}^{(1)}$.

######  Lemma 5 (Transformation).

Let $\rho^{(1)}$ and ${\rho^{\prime}}^{(1)}$ denote the distribution of
function $\tilde{M}:\\{g_{1},g^{\prime}_{1}\\}\rightarrow\mathcal{Z}$,
$\mu_{i}^{(i)}$ be the distribution of $M_{i}(g_{i})$, and $\gamma_{i}^{(i)}$
be the rest part of $\mu_{i}^{(i)}$ except ${\rho}^{(1)}$ and
${\rho^{\prime}}^{(1)}$, then $\mu_{i}^{(i)}$ is mapped as follows:

$\mu_{i}^{(i)}=\frac{1}{n}\sum_{j=1}^{n}(\frac{p_{ij}}{2}\rho^{(1)}+\frac{p_{ij}}{2}{\rho^{\prime}}^{(1)}+(1-p_{ij})\gamma_{i}^{(i)})$
(4)

where $p_{ij}=\exp(-D_{N}(\mu^{(1)}_{j}||\mu^{(i)}_{i}))$.

######  Proof.

By Lemma 3, we have
$\mu_{j}^{(1)}=({e^{\epsilon^{l}_{j}}}/({1+e^{\epsilon^{l}_{j}}}))\rho^{(1)}+({1}/({1+e^{\epsilon^{l}_{j}}})){\rho^{\prime}}^{(1)}$
and
${\mu^{\prime}}_{j}^{(1)}=({1}/({1+e^{\epsilon^{l}_{j}}}))\rho^{(1)}+({e^{\epsilon^{l}_{j}}}/({1+e^{\epsilon^{l}_{j}}})){\rho^{\prime}}^{(1)}$.
The influence of $\epsilon^{l}_{j}$ on $\mu_{i}^{(i)}$ is isolated:

$\displaystyle\mu_{i}^{(i)}=\frac{1}{n}\sum_{j=1}^{n}(\frac{p_{ij}}{2}\mu_{j}^{(1)}+\frac{p_{ij}}{2}{\mu^{\prime}}_{j}^{(1)}+(1-p_{ij})\gamma_{i}^{(i)})$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}(\frac{p_{ij}}{2}\rho^{(1)}+\frac{p_{ij}}{2}{\rho^{\prime}}^{(1)}+(1-p_{ij})\gamma_{i}^{(i)})$

Step (iii). Now we can bound the divergence of the transformed distributions
on $D$ and $D^{\prime}$.

######  Lemma 6 (Generalized Central Bound).

Let $i,j\in[n]$, $\delta_{s}\in[0,1]$,
$\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}\geq 16\ln(4/\delta_{s})$,
$P=S\circ M$ of APES on $D$ and $D^{\prime}$ is
$(\epsilon^{c},\delta^{c})$-distinguishable where
$\delta^{c}\leq\frac{e^{\epsilon^{*}}-1}{e^{\epsilon^{*}}+1}\delta_{s}$ and
$p_{ij}=\frac{\epsilon_{i}^{l}}{\epsilon_{j}^{l}}\cdot\frac{1-e^{-\epsilon_{j}^{l}}}{1-e^{-\epsilon_{i}^{l}}}\cdot
e^{-\max(\epsilon^{l}_{i},\epsilon^{l}_{j})}$,

$\epsilon^{c}\leq\ln(1+\frac{e^{\epsilon^{*}}-1}{e^{\epsilon^{*}}+1}(\frac{8(\ln(4/\delta_{s}))^{1/2}}{(\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n})^{1/2}}+\frac{8}{\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n}}))$

######  Proof.

By Lemma 5, any output distribution $\mu_{i}^{(i)}$ can be mapped into
$\rho^{(1)}$ or ${\rho^{\prime}}^{(1)}$ with probability $p_{ij}/2n$, into
$\gamma_{i}^{(i)}$ with $(1-p_{ij})/n$. Consider outputs of $n-1$ users, we
get a set of mapping distributions including $n(n-1)$ elements.

With any $T\subseteq[n(n-1)]$, $\Gamma=[n(n-1)]\backslash T$, we define an
mapping event $U=\\{u_{1},...u_{n(n-1)}\\}$ where

$u_{t}=\left\\{\begin{array}[]{rcl}\rho^{(1)}\text{\rm or
}{\rho^{\prime}}^{(1)},&t\in T\\\
\gamma_{t}^{(t)},&t\in\Gamma\end{array}\right.$

The effect of $\gamma_{i}$ can be removed in process $P$ under the same
$U_{T}$ since all the $u_{t}\in U_{\Gamma}$ are the same in $D$ and
$D^{\prime}$:

$\displaystyle\frac{\Pr[P(D)=\mathbf{z}]}{\Pr[P(D^{\prime})=\mathbf{z}]}\leq\frac{\Pr[U_{T}\cup{\rho}^{(1)}]\Pr[U_{\Gamma}]}{\Pr[U_{T}\cup{\rho^{\prime}}^{(1)}]\Pr[U_{\Gamma}]}$
(5)

Then we define $T_{0}\subseteq T$ and $T_{1}=T\backslash T_{0}$, $\forall
u_{t}\in U_{T_{0}}$ is $\rho^{(1)}$, $\forall u_{t}\in U_{T_{1}}$ is
${\rho^{\prime}}^{(1)}$ on $D$; $T^{\prime}_{0}\subseteq T$ and
$T^{\prime}_{1}=T\backslash T^{\prime}_{0}$, $\forall u_{t}\in
U_{T^{\prime}_{0}}$ is $\rho^{(1)}$, $\forall u_{t}\in U_{T^{\prime}_{1}}$ is
${\rho^{\prime}}^{(1)}$ on $D^{\prime}$. Put aside the randomness on $g_{1}$
and $g^{\prime}_{1}$ for now (which means the output of user $1$ can be
regarded as ${\rho}^{(1)}$ or ${\rho^{\prime}}^{(1)}$), when reaching the
mixed output $\mathbf{z}$ with the same number of $\rho^{(1)}$ or
${\rho^{\prime}}^{(1)}$, $U_{T_{0}}$ on $D$ and $U_{T^{\prime}_{0}}$ on
$D^{\prime}$ should be different as $|T^{\prime}_{0}|-|T_{0}|=1$. Recall that
$|T|\sim\sum_{i=2}^{n}\sum_{j=1}^{n}{\rm Bern}(p_{ij}/n)$ and $|T_{0}|\sim{\rm
Bin}(1/2,|T|)$ according to Lemma 5, we can bound Eq.(5) by deriving following
equation:

$\displaystyle\frac{\Pr[U_{T}\cup{\rho}^{(1)}]}{\Pr[U_{T}\cup{\rho^{\prime}}^{(1)}]}=\frac{\Pr[U_{T_{0}}\cup
U_{T_{1}}|U_{T}]\cdot\Pr[U_{T}]}{\Pr[U_{T^{\prime}_{0}}\cup
U_{T^{\prime}_{1}}|U_{T}]\cdot\Pr[U_{T}]}$
$\displaystyle=\frac{\tbinom{|T|}{|T_{0}|}(\frac{1}{2})^{|T_{0}|}(\frac{1}{2})^{|T|-|T_{0}|}}{\tbinom{|T|}{|T^{\prime}_{0}|}{(\frac{1}{2})}^{|T^{\prime}_{0}|}{(\frac{1}{2})}^{|T|-|T^{\prime}_{0}|}}=\frac{|T_{0}|+1}{|T|-|T_{0}|}$
(6)

With Chernoff bound and Hoeffding’s inequality, when
$\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}\geq 16\ln(4/\delta_{s})$,
Eq.(Proof) is bounded as
$\frac{|T_{0}|+1}{|T|-|T_{0}|}\leq\ln(1+\frac{8(\ln(4/\delta_{s}))^{1/2}}{(\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n})^{1/2}}+\frac{8}{\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}})$.

At last, we consider the randomness on $g_{1}$ and $g^{\prime}_{1}$ with
certain privacy budget $\epsilon^{*}$, the rest of the proof follows existing
work (Feldman, McMillan, and Talwar 2022) and the general bound is proved. The
full proof of Lemma 6 is provided to Appendix A.

From the analysis above, it is realized that which $\epsilon^{*}$ adopted by
$g_{1}$ or $g_{1}^{\prime}$ is crucial for the bound. For the worst case that
$\epsilon^{*}=\max(\epsilon^{l}_{j})$ for ${j\in[n]}$, the divergence is upper
bounded as Theorem 4. The proof refers to Appendix A.

## Experiments

We conduct comprehensive experiments on APES and S-APES with the public
dataset and various privacy settings.

### Experiment Settings

##### Dataset and Implementation

QMNIST (Yadav and Bottou 2019) is an extended version of MNIST dataset (LeCun
et al. 1998), which consists of 120,000 28-by-28-pixel images with 10 classes.
We set users as $n$=10,000 and partition the dataset evenly for users. The
frameworks are evaluated with a Logistic Regression model with $d$=7850. All
the experiments are implemented on a workstation with an Intel(R) Xeon(R)
E5-2640 v4 CPU at 2.40GHz and a NVIDIA Tesla P40 GPU running on Ubuntu.

##### Baselines

We compare the proposed methods with the following schemes. (i) Baseline
frameworks include: Non-Private: FedProx (Li et al. 2020) without privacy
protection. LDP-Min: all users adopt $\min\epsilon^{l}_{i}$ as privacy budget
compulsively, which preserves privacy of all the users. PLDP: FedProx with
personalized LDP. UniS: FedProx with shuffle model under personalized LDP, the
privacy bound refers to Eq. (2). All the baseline frameworks exploit classic
Laplace Mechanism as local randomizer. (ii) Baseline bounds of privacy
amplification effect include: the numerical generic result of BBGN’19 (Balle
et al. 2019), the nemurical result of FMT’22 (Feldman, McMillan, and Talwar
2022), the upper bound of GDDTK’21 (Girgis et al. 2021) and Erlingsson’19
(Erlingsson et al. 2019).

##### Parameter Selection

We stimulate the personalized privacy preference $\epsilon^{l}$ for several
situations as Tab. 2. $\delta^{s}$ for shuffling is set to $10^{-8}$ and
$\delta^{uc}$ after dimension composition is $3.6\times 10^{-5}$, smaller than
$1/n$.

### Experiment Results

We first show the effectiveness of the total frameworks, then confirm the
privacy amplification effect, Clip-Laplace, and post-sparsification adopted in
frameworks separately.

##### Effectiveness of frameworks

Tab. 3 demonstrates that our frameworks achieve stronger central privacy with
comparable or higher utility under the same personalized LDP. we compare the
model accuracy and central privacy budgets of one epoch under Uniform2. (i)
APES gains stricter privacy and the highest accuracy than baseline private
frameworks. Dimension-level $\epsilon^{c}$ and user-level $\epsilon^{uc}$
reduce by more than 21% compared to UniS and PLDP. LDP-min gets tighter bound,
yet the model performs poorly. There is no baseline framework achieves both
better sides. The performance of APES benefits from privacy amplification
effect of EoN and Clip-Laplace perturbation. (ii) S-APES provides the same
$\epsilon^{c}$ as APES and further enhances user-level privacy.
$\epsilon^{uc}$ diminishes by 55.6%, 66.7%, 99.6% compared to APES, UniS, and
PLDP separately, It is noticed that local $\epsilon^{ul}$ also drops by
dimension reduction. Though S-APES sacrifices accuracy of APES by 1.8%, it is
still higher than baselines. The post-sparsification in S-APES substantially
boosts privacy with this tolerable utility reduction.

Fig. 2(b) confirms that our frameworks perform well on multiple distributions
and ranges of $\epsilon^{l}$ locally (cf. Tab. 2). (i) Accuracy of APES and
S-APES is higher than UniS for the most settings. An exception is in Gauss1
LDP, which implies that S-APES may bot be appropriate for small
$\epsilon^{l}$. Too much perturbation strengthens the privacy, but makes
selecting informative dimensions harder. (ii) APES performs more stable than
UniS for different $\epsilon^{l}$. A reasonable deduction is outputs of Clip-
Laplace is not as sensitive as Laplace to varying parameters, which is
verified in Fig. 7 in Appendix C.

Name | Distribution of $\epsilon^{l}=(\epsilon^{l}_{1},...,\epsilon^{l}_{n})$ | Clip range
---|---|---
Uniform1 | $\mathcal{U}(0.05,0.5)$ | $[0.05,0.5]$
Uniform2 | $\mathcal{U}(0.05,1)$ | $[0.05,1]$
Gauss1 | $\mathcal{N}(0.1,1)$ | $[0.05,0.5]$
Gauss2 | $\mathcal{N}(0.2,1)$ | $[0.05,1]$
MixGauss1 |  $\mathcal{N}(0.1,1)$ $90\%$, $\mathcal{N}(0.5,1)$ $10\%$ | $[0.05,0.5]$
MixGauss2 |  $\mathcal{N}(0.2,1)$ $90\%$, $\mathcal{N}(1,1)$ $10\%$ | $[0.05,1]$
Table 2: Distributions of Personalized LDP Budgets $\epsilon^{l}$. $\mathcal{U}$, $\mathcal{N}$ represents Uniform and Gaussian Distribution respectively. Clip range $[a,b]$ denotes any value $g$ outside the range $[a,b]$ is clipped by $\max(a,g)$ or $\min(b,g)$. Frameworks |  $\epsilon^{ul}$ | $\epsilon^{c}$ | $\epsilon^{uc}$ | Accuracy
---|---|---|---|---
Non-Private | $\quad\infty$ | $\infty$ | $\infty$ |  84.35%
LDP-Min |  392.5 | 0.05 | 40.1 | 56.11%
PLDP | 392.5 $\sim$ 7850 | 1 | 7850 | 77.54%
UniS | 392.5 $\sim$ 7850 | 0.069111 Since the true central privacy under classic Laplace Mechanisms with varied $\epsilon^{l}_{i}$ is unbounded, $\epsilon^{c}$ of UniS in Tab. 3 is best considered as an approximation when the $\epsilon^{l}_{i}$ of different users are very similar to each other. | 76.9 | 77.54%
APES | 392.5 $\sim$ 7850 | 0.057 | 57.6 |  79.67%
S-APES | 78.5 $\sim$ 1570 | 0.057 | 25.6 | 78.14%
Table 3: Privacy and Utility under Unifrom2 LDP. $\epsilon^{ul}$: local user
level, $\epsilon^{c}$: central dimension level, $\epsilon^{uc}$: central user
level privacy budgets.

##### Privacy Amplification Effect

In Fig. 2(a), we provide numerical evaluations for privacy amplification
effect under fixed personalized LDP settings. Given dimension-level local
privacy $\epsilon^{l}\in[0.05,1]$, we observe following results: (i) our
bounds achieve the strongest central privacy with the smallest value of
$\epsilon^{c}$ compared to baseline bounds under the same $n$. The bound gets
sharper especially when $\epsilon^{l}$ concentrates on smaller values. E.g.,
for the same range that $\epsilon^{l}\in[0.05,1]$, most $\epsilon^{l}_{i}$ in
Gauss2 are smaller than $\epsilon^{l}_{i}$ in Uniform2, which leads to lower
$\epsilon^{c}$. This effect comes from the EoN analysis, by which privacy
contribution of each local perturbation is taken into consideration. (ii) The
amplification effect gets stronger when more datapoints are shuffled, as more
randomness is introduced for obfuscation. When $n$ grows, almost all the
privacy bounds $\epsilon^{c}$ reduce. Moreover, Fig. 5 and 6 in Appendix C
demonstrate EoN gives a more obvious amplification effect when the range of
$\epsilon^{l}$ gets larger.

##### Stability of Clip-Laplace Mechanism

Fig. 3(a) shows a relatively mild impact of clip bound $C$ on Clip-Laplace
perturbation. We compare model accuracy by adopting Clip-Laplace Mechanism
(CLap for short) and classic Laplace mechanism (Lap for short) in APES
separately. Overall, the highest accuracy is obtained with CLap when $C=0.1$.
CLap performs well especially for large $C$, while Lap is only good at small
$C$. It implies CLap may be suitable for perturbing gradients with larger
norms. Fig. 7 in Appendix C explores why CLap adapts to varying parameters.
The variance of CLap is more stable compared to Lap for the same level of LDP
when $C$ changes. As a price of low variance resulting from the limited output
range, a larger bias is introduced into perturbation (cf. Fig. 8 in Appendix
C).

##### Performance of Post-Sparsification

We evaluate the parameters and the effectiveness of post-sparsification
technique (_ps_ for short) with Uniform2. (i) The trade-off between accuracy
and privacy of _ps_ is discussed above, while the knob is sparsification ratio
$b/d$. In Fig. 3(b), the model with _ps_ achieves almost optimal accuracy as
APES when $b/d=0.2$, hence only smaller ratios are evaluated. As $b/d$ grows,
fewer dimensions are uploaded and the accuracy falls. In return, privacy cost
is saved. (ii) Then we observe that _ps_ is more effective than random-
sparification (_rs_ for short) which randomly select dimensions with $b/d$.
Specifically, model accuracy based on _rs_ is lower than _ps_ for all the
ratios, and dramatically drops when $b/d$ gets larger, as fewer informative
dimensions are uploaded by _rs_.

(a) Privacy Bounds

(b) Impact of $\epsilon^{l}$

Figure 2: Privacy Bounds and Utility

(a) Impact of $C$

(b) Impact of _ps_

Figure 3: Mechanisms and Strategies

## Conclusion

This work focuses on personalized private federated learning. To balance
privacy and utility, we propose privacy amplification frameworks with shuffle
model under personalized LDP. Comprehensive evaluations on the public dataset
confirm that our frameworks improve central privacy by reducing
$\epsilon^{uc}$ up to 66.7% compared to existing work with comparable or
higher accuracy.

In the future, we intend to extend the work in several directions. First, we
will explore the effectiveness of the work for larger models as sharing more
parameters requires higher standards for both LDP performance and
communication efficiency. Future improvements on sparsification techniques may
alleviate the concern. Second, it may be possible to adapt the work to non-IID
data distribution settings, hence more elaborate calibration for skewed
gradients is required.

## Acknowledgments

We would like to thank all the anonymous reviewers for their time and efforts
on our manuscript, their insightful comments and valuable suggestions help us
shape the final draft. Our work is supported by National Natural Science
Foundation of China (62072460, 62076245, 62172424,62276270), Beijing Natural
Science Foundation (4212022), National Science Foundation (NSF) CNS-2124104,
CNS-2125530, CNS-1952192, National Institute of Health (NIH) R01LM013712,
R01ES033241, UL1TR002378, Cisco Research University Award #2738379,
Fundamental Research Funds for the Central Universities, and Research Funds of
Renmin University of China (21XNH180).

## References

  * Aji and Heafield (2017) Aji, A. F.; and Heafield, K. 2017.  Sparse communication for distributed gradient descent.  _arXiv preprint arXiv:1704.05021_.
  * Balle et al. (2019) Balle, B.; Bell, J.; Gascón, A.; and Nissim, K. 2019.  The privacy blanket of the shuffle model.  In _Annual International Cryptology Conference_ , 638–667. Springer.
  * Bittau et al. (2017) Bittau, A.; Erlingsson, Ú.; Maniatis, P.; Mironov, I.; Raghunathan, A.; Lie, D.; Rudominer, M.; Kode, U.; Tinnes, J.; and Seefeld, B. 2017.  Prochlo: Strong privacy for analytics in the crowd.  In _Proceedings of the 26th symposium on operating systems principles_ , 441–459.
  * Chen et al. (2016) Chen, R.; Li, H.; Qin, A. K.; Kasiviswanathan, S. P.; and Jin, H. 2016.  Private spatial data aggregation in the local setting.  In _2016 IEEE 32nd International Conference on Data Engineering (ICDE)_ , 289–300. IEEE.
  * Croft, Sack, and Shi (2022) Croft, W.; Sack, J.-R.; and Shi, W. 2022.  Differential privacy via a truncated and normalized laplace mechanism.  _Journal of Computer Science and Technology_ , 37(2): 369–388.
  * Duan, Ye, and Hu (2022) Duan, J.; Ye, Q.; and Hu, H. 2022.  Utility Analysis and Enhancement of LDP Mechanisms in High-Dimensional Space.  In _2022 IEEE 38nd International Conference on Data Engineering (ICDE)_ , 407–419. IEEE.
  * Dwork, Roth et al. (2014) Dwork, C.; Roth, A.; et al. 2014.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4): 211–407.
  * Erlingsson et al. (2019) Erlingsson, Ú.; Feldman, V.; Mironov, I.; Raghunathan, A.; Talwar, K.; and Thakurta, A. 2019.  Amplification by shuffling: From local to central differential privacy via anonymity.  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2468–2479. SIAM.
  * Erlingsson, Pihur, and Korolova (2014) Erlingsson, Ú.; Pihur, V.; and Korolova, A. 2014.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In _Proceedings of the 2014 ACM SIGSAC conference on computer and communications security_ , 1054–1067.
  * Feldman, McMillan, and Talwar (2022) Feldman, V.; McMillan, A.; and Talwar, K. 2022.  Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling.  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , 954–964. IEEE.
  * Fredrikson, Jha, and Ristenpart (2015) Fredrikson, M.; Jha, S.; and Ristenpart, T. 2015.  Model inversion attacks that exploit confidence information and basic countermeasures.  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , 1322–1333.
  * Geng et al. (2018) Geng, Q.; Ding, W.; Guo, R.; and Kumar, S. 2018.  Truncated Laplacian mechanism for approximate differential privacy.  _arXiv preprint arXiv:1810.00877_.
  * Girgis et al. (2021) Girgis, A. M.; Data, D.; Diggavi, S.; Suresh, A. T.; and Kairouz, P. 2021.  On the renyi differential privacy of the shuffle model.  In _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ , 2321–2341.
  * Holohan et al. (2018) Holohan, N.; Antonatos, S.; Braghin, S.; and Mac Aonghusa, P. 2018.  The bounded laplace mechanism in differential privacy.  _arXiv preprint arXiv:1808.10410_.
  * Kairouz, Oh, and Viswanath (2015) Kairouz, P.; Oh, S.; and Viswanath, P. 2015.  The composition theorem for differential privacy.  In _International conference on machine learning_ , 1376–1385. PMLR.
  * LeCun et al. (1998) LeCun, Y.; Bottou, L.; Bengio, Y.; and Haffner, P. 1998.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11): 2278–2324.
  * Li et al. (2020) Li, T.; Sahu, A. K.; Zaheer, M.; Sanjabi, M.; Talwalkar, A.; and Smith, V. 2020\.  Federated optimization in heterogeneous networks.  _Proceedings of Machine Learning and Systems_ , 2: 429–450.
  * McMahan et al. (2017) McMahan, B.; Moore, E.; Ramage, D.; Hampson, S.; and y Arcas, B. A. 2017.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , 1273–1282. PMLR.
  * Nasr, Shokri, and Houmansadr (2019) Nasr, M.; Shokri, R.; and Houmansadr, A. 2019.  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.  In _2019 IEEE symposium on security and privacy (SP)_ , 739–753. IEEE.
  * Wei et al. (2020) Wei, K.; Li, J.; Ding, M.; Ma, C.; Yang, H. H.; Farokhi, F.; Jin, S.; Quek, T. Q.; and Poor, H. V. 2020.  Federated learning with differential privacy: Algorithms and performance analysis.  _IEEE Transactions on Information Forensics and Security_ , 15: 3454–3469.
  * Xiong et al. (2021) Xiong, Z.; Cai, Z.; Takabi, D.; and Li, W. 2021.  Privacy threat and defense for federated learning with non-iid data in AIoT.  _IEEE Transactions on Industrial Informatics_ , 18(2): 1310–1321.
  * Yadav and Bottou (2019) Yadav, C.; and Bottou, L. 2019.  Cold case: The lost mnist digits.  _Advances in neural information processing systems_ , 32.
  * Ye and Hu (2020) Ye, Q.; and Hu, H. 2020.  Local differential privacy: Tools, challenges, and opportunities.  In _International Conference on Web Information Systems Engineering_ , 13–23. Springer.
  * Yu et al. (2019) Yu, L.; Liu, L.; Pu, C.; Gursoy, M. E.; and Truex, S. 2019.  Differentially private model publishing for deep learning.  In _2019 IEEE symposium on security and privacy (SP)_ , 332–349. IEEE.
  * Zhu, Liu, and Han (2019) Zhu, L.; Liu, Z.; and Han, S. 2019.  Deep leakage from gradients.  _Advances in neural information processing systems_ , 32.

## Appendix

This Appendix includes: (i) Section A: omitted proofs of privacy theorems.
(ii) Section B: omitted proofs of convergence analysis. (iii) Section C:
additional experiment results.

### A Privacy Analysis

#### Proof of Theorem 1

Let $x$ and $x^{\prime}\in\mathcal{D}^{d}$ be such that $||x-x^{\prime}||\leq
1$, $f(x)$ and $f(x^{\prime})\in[-\Delta f/2,\Delta f/2]$,
$f(x^{\prime})=f(x)+a$.

$\displaystyle\frac{\Pr[M(x)=z]}{\Pr[M(x^{\prime})=z]}$
$\displaystyle=\prod_{k=1}^{d}(\frac{1/S\cdot\exp(-|f(x)_{k}-z_{k}|/\lambda)}{1/S^{\prime}\cdot\exp(-|f(x^{\prime})_{k}-z_{k}|/\lambda)})$
$\displaystyle=\prod_{k=1}^{d}(\frac{1-\frac{1}{2}\exp(\frac{\epsilon(-A+f(x)_{k}+a_{k})}{\Delta
f})-\frac{1}{2}\exp(\frac{\epsilon(-A-f(x)_{k}-a_{k})}{\Delta
f})}{1-\frac{1}{2}\exp(\frac{\epsilon(-A+f(x)_{k})}{\Delta
f})-\frac{1}{2}\exp(\frac{\epsilon(-A-f(x)_{k})}{\Delta f})}$
$\displaystyle\cdot\exp(\frac{\epsilon|f(x)_{k}-f(x^{\prime})_{k}|}{\Delta
f}))$ $\displaystyle\leq\exp(\frac{\epsilon\cdot||\Delta f/2-(-\Delta
f/2)||_{1}}{\Delta f}))$ $\displaystyle\leq\exp(\epsilon)$

#### Proof of Lemma 4

Let $g_{s}$ and $g_{t}\in\mathcal{D}^{d}$ be such that $||g_{s}-g_{t}||\leq
1$, $f(g_{s})$ and $f(g_{t})\in[-C,C]$ and $\Delta f=2C$, we have

$\displaystyle\frac{\Pr[M_{i}(g_{s})=z]}{\Pr[M_{j}(g_{t})=z]}=\prod_{k=1}^{d}(\frac{1/(b_{i}S^{(0)}_{i})\cdot\exp(-|f(g_{s})_{k}-z_{k}|/b_{i})}{1/(b_{j}S^{(1)}_{j})\cdot\exp(-|f(g_{t})_{k}-z_{k}|/b_{j})})$
$\displaystyle\leq\prod_{k=1}^{d}(\frac{1-\frac{1}{2}\exp(\frac{\epsilon^{l}_{j}(-A+f(g_{t})_{k})}{\Delta
f})-\frac{1}{2}\exp(\frac{\epsilon^{l}_{j}(-A-f(g_{t})_{k})}{\Delta
f})}{1-\frac{1}{2}\exp(\frac{\epsilon^{l}_{i}(-A+f(g_{s})_{k})}{\Delta
f})-\frac{1}{2}\exp(\frac{\epsilon^{l}_{i}(-A-f(g_{s})_{k})}{\Delta f})}$
$\displaystyle\cdot\exp(\frac{|\epsilon^{l}_{j}f(g_{t})_{k}-\epsilon^{l}_{i}f(g_{s})_{k}|+|z_{k}(\epsilon^{l}_{i}-\epsilon^{l}_{j})|}{\Delta
f})\cdot\frac{\epsilon^{l}_{i}}{\epsilon^{l}_{j}})$ (7)

When $\epsilon^{l}_{j}f(g_{t})_{k}\geq\epsilon^{l}_{i}f(g_{s})_{k}$, we define
$l(u)=(1-\frac{1}{2}\exp(\frac{\epsilon{(-A+u)}}{\Delta
f})-\frac{1}{2}\exp(\frac{\epsilon(-A-u)}{\Delta f}))\cdot\exp(\frac{\epsilon
u}{\Delta f})$, the maximum and minimum of $l(u)$ is $l(C)$ and $l(-C)$
separately when $C\leq A$. Then the right hand of Eq. (7) is bounded:

$\displaystyle\frac{\Pr[M_{i}(g_{s})=z]}{\Pr[M_{j}(g_{t})=z]}\leq\frac{1-\frac{1}{2}\exp(\frac{{\epsilon^{l}_{j}(-A+C)}}{2C})-\frac{1}{2}\exp(\frac{\epsilon^{l}_{j}(-A-C)}{2C})}{1-\frac{1}{2}\exp(\frac{{\epsilon^{l}_{i}(-A+C)}}{2C})-\frac{1}{2}\exp(\frac{\epsilon^{l}_{i}(-A-C)}{2C})}$
$\displaystyle\cdot\frac{\epsilon^{l}_{i}}{\epsilon^{l}_{j}}\cdot\exp(\frac{(\epsilon^{l}_{i}+\epsilon^{l}_{j})}{2}+\frac{A|\epsilon^{l}_{i}-\epsilon^{l}_{j}|}{2C})$

In particular, when $A=C$, the bound is tight as follows:

$\displaystyle\frac{\Pr[M_{i}(g_{s})=z]}{\Pr[M_{j}(g_{t})=z]}\leq\exp(\frac{|\epsilon^{l}_{i}-\epsilon^{l}_{j}|}{2})\cdot\frac{\exp(\epsilon^{l}_{j}/2)-\exp(-\epsilon^{l}_{j}/2)}{\exp(\epsilon^{l}_{i}/2)-\exp(-3\epsilon^{l}_{i}/2)}$
$\displaystyle\cdot\frac{\epsilon^{l}_{i}}{\epsilon^{l}_{j}}\leq\frac{\epsilon^{l}_{i}}{\epsilon^{l}_{j}}\cdot\frac{1-e^{-\epsilon^{l}_{j}}}{1-e^{-\epsilon^{l}_{i}}}\cdot
e^{\max(\epsilon^{l}_{i},\epsilon^{l}_{j})}$ (8)

Similarly, we get the same bound as Eq. (8) when
$\epsilon^{l}_{j}f(g_{t})_{k}<\epsilon^{l}_{i}f(g_{s})_{k}$. Thus, the proof
is completed. This Lemma allows us to transform echos in the following part.

#### Proof of Lemma 6

From the proof in main body, we have the intermediate result as Eq. (5), which
is the following equation:

$\displaystyle\frac{\Pr[P(D)=\mathbf{z}]}{\Pr[P(D^{\prime})=\mathbf{z}]}=\frac{|T_{0}|+1}{|T|-|T_{0}|}$
(9)

Recall that $|T|\sim\sum_{i=2}^{n}\sum_{j=1}^{n}{\rm Bern}(p_{ij}/n)$ and
$|T_{0}|\sim{\rm Bin}(1/2,|T|)$, by Chernoff bound and Hoeffding’s inequality
, $T$ and $T_{0}$ are concentrated to certain values. Specifically, when
$\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}\geq 3\ln(4/\delta_{s})$,

$\displaystyle|T-\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}|\leq(3\ln(4/\delta)\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n})^{\frac{1}{2}}$
(10) $\displaystyle|T_{0}-T/2|\leq(T/2\ln(4/\delta))^{\frac{1}{2}}$ (11)

Based on Eq. (10) and (11), if let
$\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}\geq 16\ln(4/\delta_{s})$, the
following equation is established with the probability $(1-\delta_{s})$.

$\displaystyle\frac{|T_{0}|+1}{|T|-|T_{0}|}\leq\frac{|T|/2+(|T|/2\ln(4/\delta_{s}))^{\frac{1}{2}}+1}{|T|/2-(|T|/2\ln(4/\delta_{s}))^{\frac{1}{2}}}$
$\displaystyle\leq
1+\frac{8(\ln(4/\delta_{s}))^{\frac{1}{2}}}{(\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n})^{\frac{1}{2}}}+\frac{8}{\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n}}$
(12)

Hence the divergence between $P(D)$ and $P(D^{\prime})$ is bounded without
considering the randomness of user 1. For briefness, we set
$1+\frac{8(\ln(4/\delta_{s}))^{\frac{1}{2}}}{(\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n})^{\frac{1}{2}}}+\frac{8}{\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n}}=e^{\epsilon_{0}}$.

Next, we take the randomness of the mechanism on $g_{1}$ and $g^{\prime}_{1}$
with certain privacy budget $\epsilon^{*}$ into consideration, according to
previous work (Kairouz, Oh, and Viswanath 2015; Feldman, McMillan, and Talwar
2022). Formally, we assume $G$ (or $G^{\prime}$) as the index of the mapping
element from $\tilde{g}_{1}$ (or $\tilde{g}^{\prime}_{1}$), and also apply
degraded privacy (cf. Lemma 3) on $\tilde{g}_{1}$ and
$\tilde{g}^{\prime}_{1}$. The mapping event on the $\tilde{g}_{1}$ (or
$\tilde{g}^{\prime}_{1}$) is defined as $U_{G}=\\{\rho^{(1)}\text{ for
}p_{1}\text{, }{\rho^{\prime}}^{(1)}\text{ for }1-p_{1}\\}$ and
$U^{\prime}_{G}=\\{\rho^{(1)}\text{ for }p^{\prime}_{1}\text{,
}{\rho^{\prime}}^{(1)}\text{ for }1-p^{\prime}_{1}\\}$, where
$p_{1}={e^{\epsilon^{*}}}/({1+e^{\epsilon^{*}}})$ and
$p^{\prime}_{1}={1}/({1+e^{\epsilon^{*}}})$.

Then we consider the mapping event $U_{S}$ from $(n-1)$ users of process $P$
except for $\tilde{g}_{1}$ (or $\tilde{g}^{\prime}_{1}$). To reach the mixed
output z with the same number of $\rho^{(1)}$ or ${\rho^{\prime}}^{(1)}$,
$U_{S}$ needs to satisfy the following situation:

$\displaystyle U_{S}=\\{U_{T}\text{ with }p_{1}\text{, }U^{\prime}_{T}\text{
with }1-p_{1}\\}$ $\displaystyle U^{\prime}_{S}=\\{U_{T}\text{ with
}p^{\prime}_{1}\text{, }U^{\prime}_{T}\text{ with }1-p^{\prime}_{1}\text{,
}\\}$

which can be written as:

$\displaystyle U_{S}=\\{U_{T}\cup U^{\prime}_{T}\text{ with }1-p_{1}\text{,
}U_{T}\text{ with }2p_{1}-1\\}$ $\displaystyle U^{\prime}_{S}=\\{U_{T}\cup
U^{\prime}_{T}\text{ with }p^{\prime}_{1}\text{, }U^{\prime}_{T}\text{ with
}1-2p^{\prime}_{1}\\}$

Hence we can bound the divergence between $U_{S}$ and $U^{\prime}_{S}$:

$\displaystyle\frac{\Pr[P(D)=\textbf{z}]-\delta^{c}}{\Pr[P(D^{\prime})=\textbf{z}]}=\frac{\Pr[U_{G}]\Pr[U_{S}|U_{G}]-\delta^{c}}{\Pr[U^{\prime}_{G}]\Pr[U^{\prime}_{S}|U^{\prime}_{G}]}$
$\displaystyle=\frac{p_{1}(2(1-p_{1})(\frac{1}{2})\Pr[U_{T}\cup
U^{\prime}_{T}]+(2p_{1}-1)\Pr[U_{T}])-\delta^{c}}{(1-p^{\prime}_{1})((2p^{\prime}_{1}(\frac{1}{2})\Pr[U_{T}\cup
U^{\prime}_{T}]+(1-2p^{\prime}_{1})\Pr[U^{\prime}_{T}]))}$ (13)

For convenience, we define the probabilities as
$A_{1}=(\frac{1}{2})\Pr[U_{T}\cup U^{\prime}_{T}]$, $A_{2}=\Pr[U_{T}]$,
$A^{\prime}_{2}=\Pr[U^{\prime}_{T}]$, $2(1-p_{1})=2p^{\prime}_{1}=(1-p)$ and
$(2p_{1}-1)=(1-2p^{\prime}_{1})=p$. Consider the bound by Eq. (12) that
$A_{2}\leq e^{\epsilon_{0}}A^{\prime}_{2}+\delta_{s}$, and $A_{2}\leq
e^{\epsilon_{0}}A_{1}+\delta_{s}$ according to hockey-stick divergence, we can
rewrite Eq. (13) as

$\displaystyle\frac{\Pr[P(D)=\textbf{z}]-\delta^{c}}{\Pr[P(D^{\prime})=\textbf{z}]}=\frac{p_{1}((1-p)A_{1}+pA_{2})-p\delta_{s}}{(1-p^{\prime}_{1})((1-p)A_{1}+pA^{\prime}_{2})}$
$\displaystyle\leq\frac{p_{1}((1-p)A_{1}+p(\min\\{A_{1},A^{\prime}_{2}\\}+e^{\epsilon_{0}}\min\\{A_{1},A^{\prime}_{2}\\}))-p\delta_{s}}{(1-p^{\prime}_{1})((1-p)A_{1}+pA^{\prime}_{2})}$
$\displaystyle\leq\frac{p_{1}((1-p)A_{1}+p(A^{\prime}_{2}+e^{\epsilon_{0}}((1-p)A_{1}+pA^{\prime}_{2})))-p\delta_{s}}{(1-p^{\prime}_{1})((1-p)A_{1}+pA^{\prime}_{2})}$
$\displaystyle\leq\frac{(1+p(e^{\epsilon_{0}}-1))((1-p)A_{1}+pA^{\prime}_{2}))}{(1-p)A_{1}+pA^{\prime}_{2}}$
$\displaystyle=1+p(e^{\epsilon_{0}}-1)$
$\displaystyle=1+\frac{e^{\epsilon^{*}}-1}{e^{\epsilon^{*}}+1}(\frac{8(\ln(4/\delta_{s}))^{1/2}}{(\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n})^{1/2}}+\frac{8}{\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n}})$

As
$\epsilon^{c}\leq\ln(\frac{\Pr[P(D)=\textbf{z}]-\delta^{c}}{\Pr[P(D^{\prime})=\textbf{z}]})$,
the general bound of process $P$ in APES is proved, and
$\delta^{c}\leq\frac{e^{\epsilon^{*}}-1}{e^{\epsilon^{*}}+1}\delta_{s}$.

#### Proof of Theorem 4

For the worst case, user 1 adpots $\max(\epsilon^{l}_{j})$ as her privacy
budget $\epsilon^{*}$, which leads to an upper bound $\epsilon^{c}$ derived
from Lemma 6. Therefore, $P(D)$ and $P(D^{\prime})$ are
$(\epsilon^{c},\delta^{c})$-DP:

$\epsilon^{c}\leq\ln(1+\frac{e^{\max(\epsilon^{l}_{j})}-1}{e^{\max(\epsilon^{l}_{j})}+1}(\frac{8(\ln(4/\delta_{s}))^{1/2}}{(\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n})^{1/2}}+\frac{8}{\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{n}\frac{p_{ij}}{n}}))$

when $\sum_{i=2}^{n}\sum_{j=1}^{n}\frac{p_{ij}}{n}\geq 16\ln(4/\delta_{s})$,
$\delta_{s}\in[0,1]$ and
$\delta^{c}\leq\frac{e^{\max(\epsilon^{l}_{j})}-1}{e^{\max(\epsilon^{l}_{j})}+1}\delta_{s}$.
Given Lemma 4, $p_{ij}$ equals
$(\frac{\epsilon^{l}_{i}}{\epsilon^{l}_{j}}\cdot\frac{1-e^{-\epsilon^{l}_{j}}}{1-e^{-\epsilon^{l}_{i}}}\cdot
e^{-\max(\epsilon^{l}_{i},\epsilon^{l}_{j})})$.

### B Convergence Analysis

To give the final convergence upper bound of the frameworks after $T$
aggregations, we make the following analysis: (i) Show the assumptions on loss
function. (ii) Derive a general form for APES with general perturbation. (iii)
Consider the perturbation of Clip-Lalpalce Mechanism in bound. (iv) Bring the
effect of calibration into the bound.

#### Step (i) Assumptions

To analyze the convergence of APES, we first make following assumptions of
loss function (Li et al. 2020; Wei et al. 2020).

  1. 1.

The function $\\{F_{i}\\}$ of user $i$ for $i\in[n]$ is non-convex,
$L$-Lipschitz smooth, and there exists $L>0$, such that
$\nabla^{2}F_{i}\succeq L\mathcal{I}$ with $\bar{\mu}:=L+\mu>0$.

  2. 2.

The functions $\\{F_{i}\\}$ satisfy $\beta$-Polyak-Lojasiewicz (PL) condition,
which implies $f(\tilde{w})-f(w^{*})\leq\frac{1}{2\beta}\|\nabla
f(\tilde{w})\|^{2}$, and $w^{*}$ is the optimal parameters for loss function.

  3. 3.

$f(\cdot)$ satisfies $l$-Lipschitz continuous condition.

  4. 4.

$w^{*}$ is the optimal solution for minimum objective function:
$w^{*}=\min_{w}h(w;w_{t})$. We assume $h(w;w_{t})$ is $\alpha$-close to
minimum function: $\|\nabla h(w^{*};w_{t})\|\leq\alpha\|\nabla h(w;w_{t})\|$
where $h(w;w_{t})=F_{i}(w)+\frac{\mu}{2}\|w-w_{t}\|^{2}$.

We also measure the dissimilarity between users in Definition (6), which is
also assumed in previous works that we refers above.

######  Definition 6 (User Dissimilarity).

The local loss functions $F_{i}$ of users are B-locally dissimilar at $w$ if
$\mathbb{E}_{i}[{\|\nabla F_{i}(w)\|^{2}}]\leq\|\nabla f(w)\|^{2}B^{2}$. Here
$B(w)=\sqrt{\frac{\mathbb{E}_{i}[{\|\nabla F_{i}(w)\|^{2}}]}{\|\nabla
f(w)\|^{2}}}$ for $\|\nabla f(w)\|\neq 0$.

#### Step (ii) Proof of General Form

We give the general for of convergence upper bound by yielding the bound in
one aggregation and inducting to T aggregations.

######  Lemma 7 (Bound of Single Aggregation).

For a global function $f(w)=\mathbb{E}[F_{i}(w)]$ in analyzer, the expectation
of difference of $f(w)$ for a single aggregation between $t$-th and $(t+1)$-th
round is bounded as follows:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(t+1)})-f(\tilde{w}^{(t)})]$
$\displaystyle\leq(\frac{\alpha
B-1}{\mu}+\frac{LB(\alpha+1)}{\mu\bar{\mu}}+\frac{LB^{2}(1+\alpha)^{2}}{2\bar{\mu}^{2}})\mathbb{E}[\|\nabla
f(\tilde{w}^{(t)})\|^{2}]$
$\displaystyle+(\frac{1}{\mu}+\frac{BL(1+\alpha)}{\bar{\mu}})\mathbb{E}[\|\nabla
f(\tilde{w}^{(t)})\|\|\eta^{(t+1)}\|]+\frac{L}{2}\mathbb{E}[\|\eta^{(t+1)}\|^{2}]$

where $\eta$ denotes the perturbation term introduced by DP mechanisms, and
$\eta^{(t)}=\frac{1}{n}\sum_{i}(\tilde{w_{i}}^{(t)}-w_{i}^{(t)})$.

######  Proof.

According to the assumption 1, $F_{i}$ is $L$-Lipschitz smooth,

$\displaystyle f(\tilde{w}^{(t+1)})\leq f(\tilde{w}^{(t)})+<\nabla
f(\tilde{w}^{(t)}),\tilde{w}^{(t+1)}-\tilde{w}^{(t)}>$
$\displaystyle+\frac{L}{2}\|\tilde{w}^{(t+1)}-\tilde{w}^{(t)}\|^{2}$ (14)

where
$\tilde{w}^{(t+1)}=\mathbb{E}[F_{i}(\tilde{w}^{(t+1)})]$,$\tilde{w}^{(t)}=\frac{1}{\eta}\sum^{n}_{i=1}{w_{i}^{(t+1)}}+\eta^{(t+1)}$
and $\eta^{(t)}=\sum^{n}_{i=1}{\eta_{i}^{(t)}}$. To bound
$f(\tilde{w}^{(t+1)})-f(\tilde{w}^{(t)})$, we have to bound
$\|\tilde{w}^{(t+1)}-\tilde{w}^{(t)}\|$ and
$(\tilde{w}^{(t+1)}-\tilde{w}^{(t)})$ separately.

First, we focus on $\|\tilde{w}^{(t+1)}-\tilde{w}^{(t)}\|$.

From assumption 3 with $\alpha$-clossness we have

$\|\nabla h_{k}(w^{(t+1)};\tilde{w}^{(t)})\|\leq\alpha\|\nabla
F_{k}(\tilde{w}^{(t)})\|$ (15)

Since $\nabla^{2}h_{k}(w;\tilde{w}^{(t)})=\bar{\mu}>0$, $h_{k}$ is
$\bar{\mu}$-strong convex. Let
$w^{*}_{k}=\mathop{\arg\min}_{w}h_{k}(w;\tilde{w}^{(t)})$, we have

$\displaystyle\bar{\mu}\|{w^{*}_{i}}^{(t+1)}-w^{(t+1)}_{i}\|$
$\displaystyle\leq\|\nabla h_{i}({w^{*}}^{(t+1)};\tilde{w}^{(t)})-\nabla
h_{i}(w^{(t+1)};\tilde{w}^{(t)})\|$ $\displaystyle=\|0-\nabla
h_{i}(w^{(t+1)};\tilde{w}^{(t)})\|=\alpha\|\nabla F_{i}(\tilde{w}^{(t)})\|$
(16)

From the strong convexity of $h_{k}$, we also know that

$\displaystyle\bar{\mu}\|{w^{*}}^{(t+1)}_{i}-\tilde{w}^{(t)}_{i}\|$
$\displaystyle\leq\|\nabla h_{i}(w^{(t+1)^{*}};\tilde{w}^{(t)})-\nabla
h_{i}(\tilde{w}^{(t)};\tilde{w}^{(t)})\|$ $\displaystyle=\|0-\nabla
h_{i}(\tilde{w}^{(t)};\tilde{w}^{(t)})\|$ $\displaystyle=\|\nabla
F_{i}(\tilde{w}^{(t)})+\mu(\tilde{w}^{(t)}-\tilde{w}^{(t)})\|$
$\displaystyle=\|\nabla F_{i}(\tilde{w}^{(t)})\|$ (17)

Based on triangle inequality, B-user dissimilarity and Eq.
(Proof)(Proof)(Proof), $\|\tilde{w}^{(t+1)}-\tilde{w}^{(t)}\|$ is bounded:

$\displaystyle\|\tilde{w}^{(t+1)}-\tilde{w}^{(t)}\|$
$\displaystyle\leq\|\tilde{w}^{(t+1)}-\tilde{w^{*}}^{(t+1)}\|+\|\tilde{w^{*}}^{(t+1)}-w^{(t)}\|+\|\eta^{(t+1)}\|$
$\displaystyle\leq\mathbb{E}_{i}[\|w^{(t+1)}_{i}-{w^{*}}^{(t+1)}_{i}\|+\|{w^{*}}^{(t+1)}_{i}-w^{(t)}_{i}\|]+\|\eta^{(t+1)}\|$
$\displaystyle\leq\frac{1+\alpha}{\bar{\mu}}\mathbb{E}_{i}[\|\nabla
F_{i}(\tilde{w}^{(t)})\|]+\|\eta^{(t+1)}\|$ (18)

Then, let us bound $(\tilde{w}^{(t+1)}-\tilde{w}^{(t)})$. Differentiate
$h_{i}$, we obtain

$\displaystyle\tilde{w}^{(t+1)}-\tilde{w}^{(t)}=w^{(t+1)}-\tilde{w}^{(t)}+\eta^{(t+1)}$
$\displaystyle\leq\frac{1}{\mu}(\mathbb{E}[\nabla
h_{i}(w^{(t+1)};\tilde{w}^{(t)})-\nabla F_{i}(w^{(t+1)})])+\eta^{(t+1)}$
$\displaystyle=\frac{1}{\mu}(\mathbb{E}[\nabla
h_{i}(w^{(t+1)};\tilde{w}^{(t)})-\nabla F_{i}(w^{(t+1)})+\nabla
F_{i}(\tilde{w}^{(t)})$ $\displaystyle-\nabla
F_{i}(\tilde{w}^{(t)}))]+\eta^{(t+1)}$ (19)

By triangle inequality and Eq. (15)(Proof), Lemma 6 and the L-Lipschitz
condition on $F_{i}$, We can bound the part $(\nabla
h_{i}(w^{(t+1)};\tilde{w}^{(t)})-\nabla F_{i}(w^{(t+1)})+\nabla
F_{i}(\tilde{w}^{(t)}))$ of Eq.(19).

$\displaystyle\|(\mathbb{E}[\nabla h_{i}(w^{(t+1)};\tilde{w}^{(t)})-\nabla
F_{i}(w^{(t+1)})+\nabla F_{i}(\tilde{w}^{(t)})]\|$
$\displaystyle\leq\mathbb{E}[\|\nabla
h_{i}(w^{(t+1)};\tilde{w}^{(t)})\|+\|\nabla F_{i}(w^{(t+1)})-\nabla
F_{i}(\tilde{w}^{(t)})\|]$ $\displaystyle=(\alpha
B+\frac{LB(1+\alpha)}{\bar{\mu}})\mathbb{E}[\|\nabla F_{i}(w^{(t+1)})|]$
$\displaystyle=(\alpha
B+\frac{LB(1+\alpha)}{\bar{\mu}})\|f(\tilde{w}^{(t)})\|$ (20)

At last, substitute Eq. (Proof), (19), and (Proof) into (Proof), Lemma 7 is
proved.

$\displaystyle\mathbb{E}[f(\tilde{w}^{(t+1)})-f(\tilde{w}^{(t)})]$
$\displaystyle\leq(\frac{\alpha
B-1}{\mu}+\frac{LB(\alpha+1)}{\mu\bar{\mu}}+\frac{LB^{2}(1+\alpha)^{2}}{2\bar{\mu}^{2}})\mathbb{E}[\|\nabla
f(\tilde{w}^{(t)})\|^{2}]$
$\displaystyle+(\frac{1}{\mu}+\frac{BL(1+\alpha)}{\bar{\mu}})\mathbb{E}[\|\nabla
f(\tilde{w}^{(t)})\|\|\eta^{(t+1)}\|]$
$\displaystyle+\frac{L}{2}\mathbb{E}[\|\eta^{(t+1)}\|^{2}]$ (21)

The proof is completed.

By lemma 7, we can derive the convergence upper bound for T aggregations.

######  Lemma 8 (General Form of Convergence Upper Bound).

The expected decrease in the global loss function
$f(w)=\frac{1}{n}\sum_{i}F_{i}(w)$ after T aggregations is bounded as follows:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]\leq
a_{1}^{T}\mathbb{E}[f(\tilde{w}^{(0)})-f(w^{*})]$
$\displaystyle+\frac{a_{1}^{T}-1}{a_{1}-1}(a_{2}\mathbb{E}[\|\eta\|]+a_{3}\mathbb{E}[\|\eta\|^{2}])$
(22)

where $a_{1}=1+\frac{2\beta(\alpha B-1)}{\mu}+\frac{2\beta
LB(\alpha+1)}{\mu\bar{\mu}}+\frac{2\beta
LB^{2}(1+\alpha)^{2}}{\bar{\mu}^{2}},a_{2}=l(\frac{1}{\mu}+\frac{BL(1+\alpha)}{\bar{\mu}}),a_{3}=\frac{L}{2}$.

######  Proof.

To bound $\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]$, we first transform it as
follows:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})+f(w^{*})-f(\tilde{w}^{(t)})]$
$\displaystyle\leq(\frac{\alpha
B-1}{\mu}+\frac{LB(\alpha+1)}{\mu\bar{\mu}}+\frac{LB^{2}(1+\alpha)^{2}}{2\bar{\mu}^{2}})\mathbb{E}[\|\nabla
f(\tilde{w}^{(t)})\|^{2}]$
$\displaystyle+(\frac{1}{\mu}+\frac{BL(1+\alpha)}{\bar{\mu}})\mathbb{E}[\|\nabla
f(\tilde{w}^{(t)})\|\|\eta^{(t+1)}\|]+\frac{L}{2}\mathbb{E}[\|\eta^{(t+1)}\|^{2}]$

From assumption 3 and 4, we have
$\mathbb{E}[f(\tilde{w}^{(t)})-f(w^{*})]\leq\frac{1}{2\beta}\|\nabla
f(\tilde{w}^{(t)})\|^{2}$ and $\|\nabla f(\cdot)\|\leq l$. Substract
$f(w^{*})$ from Eq.(Proof) on both sides, we have

$\displaystyle\mathbb{E}[f(\tilde{w}^{(t)})-f(w^{*})]$
$\displaystyle\leq(1+\frac{2\beta(\alpha B-1)}{\mu}+\frac{2\beta
LB(\alpha+1)}{\mu\bar{\mu}}+\frac{2\beta
LB^{2}(1+\alpha)^{2}}{\bar{\mu}^{2}})$
$\displaystyle\cdot\mathbb{E}[f(\tilde{w}^{(t)})-f(w^{*})]+l(\frac{1}{\mu}+\frac{BL(1+\alpha)}{\bar{\mu}})\mathbb{E}[\|\eta^{(t+1)}\|]$
$\displaystyle+\frac{L}{2}\mathbb{E}[\|\eta^{(t+1)}\|^{2}]$ (23)

Considering expectations of perturbation term $\eta$ is the same in each
epoch, we define $\mathbb{E}[\|\eta^{(t)}\|]=\mathbb{E}[\|\eta\|]$ for
$t\in[0,T]$. By Eq. (Proof) we have

$\displaystyle\mathbb{E}[f(\tilde{w}^{(t)})-f(w^{*})]\leq
a_{1}\mathbb{E}[f(\tilde{w}^{(t)})-f(w^{*})]+a_{2}\mathbb{E}[\|\eta^{(t+1)}\|]$
$\displaystyle+a_{3}\mathbb{E}[\|\eta^{(t+1)}\|^{2}]$ (24)

where $a_{1}=1+\frac{2\beta(\alpha B-1)}{\mu}+\frac{2\beta
LB(\alpha+1)}{\mu\bar{\mu}}+\frac{2\beta
LB^{2}(1+\alpha)^{2}}{\bar{\mu}^{2}},a_{2}=l(\frac{1}{\mu}+\frac{Bh(\alpha+1)}{\bar{\mu}}),a_{3}=\frac{L}{2}$.

The bound of T aggregations is inducted with Eq.(Proof).

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]$ $\displaystyle\leq
a_{1}(...(a_{1}(a_{1}(\mathbb{E}[f(\tilde{w}^{(0)})-f(w^{*})]))))$
$\displaystyle+(a_{1}^{0}+a_{1}^{1}+...+a_{1}^{T-1})(a_{2}\mathbb{E}[\|\eta\|]+a_{3}\mathbb{E}[\|\eta\|^{2}])$
$\displaystyle=a_{1}^{T}\mathbb{E}[f(\tilde{w}^{(0)})-f(w^{*})]+\sum_{t=0}^{T-1}a_{1}^{t}(a_{2}\mathbb{E}[\|\eta\|]+a_{3}\mathbb{E}[\|\eta\|^{2}])$
$\displaystyle=a_{1}^{T}\mathbb{E}[f(\tilde{w}^{(0)})-f(w^{*})]+\frac{a_{1}^{T}-1}{a_{1}-1}(a_{2}\mathbb{E}[\|\eta\|]+a_{3}\mathbb{E}[\|\eta\|^{2}])$

Theorem 8 is proved.

#### Step (iii) Proof after CLap perturbation

The specific perturbation bias and variance introduced by Clip-Laplace
Mechanism is considered in this section. We have $\tilde{g_{i}}\sim
CLap(g_{i},\lambda_{i},C)$ where $\lambda_{i}=\Delta f/\epsilon_{i}$, and
$g_{i}=\nabla f(x_{i};w)$. Thus, local perturbed term $\eta_{i}$ equals
$\tilde{g_{i}}-g_{i}$, and aggregated perturbed term $\eta$ is
$\frac{1}{n}\sum_{i}\eta_{i}$.

######  Lemma 9 (Bound with Clip-Laplacian perturbation).

By personalized privacy level
$\epsilon^{l}=(\epsilon^{l}_{1},...,\epsilon^{l}_{n})$, the convergence bound
of APES with Clip-laplacian noises is given as:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]\leq a_{1}^{T}\Delta$
$\displaystyle+\frac{a_{1}^{T}-1}{a_{1}-1}(O(a_{2}C/\min(\epsilon^{l}_{i}))+O(a_{3}C^{2}/\min(\epsilon^{l}_{i})^{2}))$

where $\mathbb{E}[f(\tilde{w}^{(0)})-f(w^{*})]$ is denoted by $\Delta$.

######  Proof.

Consider local perturbation for each user $i$,

$\displaystyle\mathbb{E}[\eta_{i}^{2}]=\frac{1}{2S}((\lambda_{i}^{2}-(g_{i}+C+\lambda_{i})^{2})e^{\frac{-C-g_{i}}{\lambda_{i}}}$
$\displaystyle+(\lambda_{i}^{2}-(-g_{i}+C+\lambda_{i})^{2})e^{\frac{-C+g_{i}}{\lambda_{i}}})+2\lambda_{i}^{2}$
$\displaystyle\leq\frac{(-4C^{2}-4\lambda_{i}C)e^{\frac{-2C}{\lambda_{i}}}}{1-e^{\frac{-2C}{\lambda_{i}}}}+2\lambda_{i}^{2}$

We can obtain the bound of $\mathbb{E}[\|\eta\|^{2}]$.

$\displaystyle\mathbb{E}[\|\eta\|^{2}]=\mathbb{E}[\frac{1}{n}\sum_{i=1}^{n}\eta_{i}^{2}]=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\eta_{i}^{2}]\leq\mathbb{E}[\eta_{i}^{2}]_{max}$
$\displaystyle=\frac{-4C^{2}-8C/{\min(\epsilon^{l}_{i}})}{e^{\min(\epsilon^{l}_{i})}-1}+\frac{8C^{2}}{\min(\epsilon^{l}_{i})^{2}}$
(25)

Then $\mathbb{E}[\|\eta\|]$ is also bounded as:

$\displaystyle\mathbb{E}[\|\eta\|])=(\mathbb{E}[\|\eta\|^{2}])-\mathbb{D}[\|\eta\|]))^{\frac{1}{2}}\leq(\mathbb{E}[\|\eta\|^{2}]))^{\frac{1}{2}}$
$\displaystyle=(\frac{-4C^{2}-8C/{\min(\epsilon^{l}_{i}})}{e^{\min(\epsilon^{l}_{i})}-1}+\frac{8C^{2}}{\min(\epsilon^{l}_{i})^{2}})^{\frac{1}{2}}$
(26)

Substituting equation (Proof) and (Proof) into (8), the convergence bound is
provided:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]\leq
a_{1}^{T}\mathbb{E}[f(\tilde{w}^{(0)})-f(w^{*})]$
$\displaystyle+\frac{a_{1}^{T}-1}{a_{1}-1}(a_{2}(\frac{-4C^{2}-8C/{\min(\epsilon^{l}_{i}})}{e^{\min(\epsilon^{l}_{i})}-1}+\frac{2C^{2}}{\min(\epsilon^{l}_{i})^{2}})^{\frac{1}{2}})$
$\displaystyle+a_{3}(\frac{-4C^{2}-8C/{\min(\epsilon^{l}_{i}})}{e^{\min(\epsilon^{l}_{i})}-1}+\frac{8C^{2}}{\min(\epsilon^{l}_{i})^{2}})))$

The proof is completed.

#### Step (iv) Proof after Calibration

Besides local perturbation, analyzer will also calibrate the noisy gradients
centrally, which increases the convergence rate empirically. We provide the
theoretical bound in this section.

######  Lemma 10 (Bound after Calibration).

After Clip Laplacian perturbation with $\epsilon^{l}$ and Calibration in
server, the convergence rate of APES is bounded as:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]\leq a_{1}^{T}\Delta$
$\displaystyle+\frac{a_{1}^{T}-1}{a_{1}-1}(O(a_{2}C/\min(\epsilon^{l}_{i}))+O(a_{3}C^{2}/\min(\epsilon^{l}_{i})^{2}))$

######  Proof.

In calibration, we estimate $\bar{g}$ by approximating $\mathbb{E}[\tilde{g}]$
with $\mathbb{E}[\tilde{\bar{g}}_{i}]$ for $i\in[n]$. The bias introduced by
$\tilde{g}$ is removed with estimated $\bar{g}$ mostly, we denote the residual
bias for each user by $\Delta\eta_{i}$, which equals to
$\eta_{i}-\eta(\bar{g})$. Note that $\eta(\bar{g})\in[-C,C]$, the norm of
$\Delta\eta_{i}$ is bounded:

$\displaystyle\mathbb{E}[\Delta\eta_{i}^{2}]=\mathbb{E}[\eta_{i}^{2}]+\mathbb{E}[\eta_{i}^{2}]-2\mathbb{E}[\eta_{i}]\mathbb{E}[\eta_{i}]\leq\frac{(-8C^{2}-8\lambda_{i}C)e^{\frac{-2C}{\lambda_{i}}}}{1-e^{\frac{-2C}{\lambda_{i}}}}$
$\displaystyle+\frac{(-8C^{2}+8\lambda_{i}C)e^{\frac{-4C}{\lambda_{i}}}-8\lambda_{i}Ce^{\frac{-2C}{\lambda_{i}}}}{(1-e^{\frac{-2C}{\lambda_{i}}})^{2}}+6\lambda_{i}^{2}$

Therefore we obtain the bound of $\mathbb{E}[\|\Delta\eta_{i}\|^{2}]$.

$\displaystyle\mathbb{E}[\|\Delta\eta_{i}\|^{2}]=\mathbb{E}[\frac{1}{n}\sum_{i=1}^{n}\Delta\eta_{i}^{2}]=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\Delta\eta_{i}^{2}]\leq\mathbb{E}[\Delta\eta_{i}^{2}]_{max}$
$\displaystyle=-\frac{8C^{2}}{e^{\min(\epsilon^{l}_{i})}-1}+\frac{8C^{2}}{(e^{\min(\epsilon^{l}_{i})}-1)^{2}}+\frac{24C^{2}}{\min(\epsilon^{l}_{i})^{2}}$
(27)

Then $\mathbb{E}[\|\Delta\eta_{i}\|]$ is also bounded as:

$\displaystyle\mathbb{E}[\|\Delta\eta_{i}\|])=(\mathbb{E}[\|\eta\|^{2}])-\mathbb{D}[\|\eta\|]))^{\frac{1}{2}}\leq(\mathbb{E}[\|\eta\|^{2}]))^{\frac{1}{2}}$
$\displaystyle=(-\frac{8C^{2}}{e^{\min(\epsilon^{l}_{i})}-1}+\frac{8C^{2}}{(e^{\min(\epsilon^{l}_{i})}-1)^{2}}+\frac{24C^{2}}{\min(\epsilon^{l}_{i})^{2}})^{\frac{1}{2}}$
(28)

Substituting Eq. (Proof) and (Proof) into (8), the bound is provided:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]\leq
a_{1}^{T}\mathbb{E}[f(\tilde{w}^{(0)})-f(w^{*})]$
$\displaystyle+\frac{a_{1}^{T}-1}{a_{1}-1}(a_{2}(-\frac{8C^{2}}{e^{\min(\epsilon^{l}_{i})}-1}+\frac{8C^{2}}{(e^{\min(\epsilon^{l}_{i})}-1)^{2}}+\frac{24C^{2}}{\min(\epsilon^{l}_{i})^{2}})^{\frac{1}{2}})$
$\displaystyle+a_{3}(-\frac{8C^{2}}{e^{\min(\epsilon^{l}_{i})}-1}+\frac{8C^{2}}{(e^{\min(\epsilon^{l}_{i})}-1)^{2}}+\frac{24C^{2}}{\min(\epsilon^{l}_{i})^{2}})$

Ideally, when estimated gradient $\bar{g}$ is accurate, we have a better bound
as follows:

$\displaystyle\mathbb{E}[f(\tilde{w}^{(T)})-f(w^{*})]\leq
a_{1}^{T}\mathbb{E}[f(\tilde{w}^{(0)})-f(w^{*})]+\frac{(a_{1}^{T}-1)a_{2}}{a_{1}-1}$
$\displaystyle\cdot(\frac{-8C^{2}-\frac{32C^{2}}{\min(\epsilon^{l}_{i})}}{e^{\min(\epsilon^{l}_{i})}-1}-\frac{8C^{2}}{(e^{\min(\epsilon^{l}_{i})}-1)^{2}}+\frac{4C^{2}}{\min(\epsilon^{l}_{i})^{2}})^{\frac{1}{2}}$
$\displaystyle+a_{3}(\frac{-8C^{2}-\frac{32C^{2}}{\min(\epsilon^{l}_{i})}}{e^{\min(\epsilon^{l}_{i})}-1}-\frac{8C^{2}}{(e^{\min(\epsilon^{l}_{i})}-1)^{2}}+\frac{4C^{2}}{\min(\epsilon^{l}_{i})^{2}})$
$\displaystyle\leq
a_{1}^{T}\Delta+\frac{a_{1}^{T}-1}{a_{1}-1}(O(a_{2}C/\min(\epsilon^{l}_{i}))+O(a_{3}C^{2}/\min(\epsilon^{l}_{i})^{2}))$

The proof is completed.

Given Lemma 10, the upper bound of convergence of the whole APES framework is
obtained, as demonstrated in Theorem 2.

### C Experiment Supplements

In this section, we provide error evaluation for calibration during analyzing
process of APES and S-APES (Fig. 4), additional comparison on privacy
amplification effects (Fig. 5, 6), and the output evaluation of Clip-Laplace
Mechanism (Fig. 7, 8). At last, the model accuracy and $\epsilon^{uc}$ for all
the LDP settings is demonstrated in Tab. 4.

Framework |  Uniform1 |  Gauss1 |  MixGauss1 |  Uniform2 |  Gauss2 |  MixGauss2
---|---|---|---|---|---|---
$\epsilon^{uc}$ | acc | $\epsilon^{uc}$ | acc | $\epsilon^{uc}$ | acc | $\epsilon^{uc}$ | acc | $\epsilon^{uc}$ | acc | $\epsilon^{uc}$ | acc
Non-Private | $\infty$ | 84.35% | $\infty$ | 84.35% | $\infty$ | 84.35% | $\infty$ | 84.35% | $\infty$ | 84.35% | $\infty$ | 84.35%
LDP-min | 40.1 | 56.11% | 40.1 | 56.11% | 40.1 | 56.11% | 40.1 | 56.11% | 40.1 | 56.11% | 40.1 | 56.11%
PLDP | 3925 | 75.64% | 3925 | 63.77% | 3925 | 67.75% | 7850 | 77.54% | 7850 | 64.81% | 7850 | 73.84%
UniS | 17.4 | 75.64% | 17.4 | 63.77% | 17.5 | 67.75% | 79.6 | 77.54% | 76.9 | 64.81% | 76.9 | 73.84%
APES | 15.5 | 78.77% | 15.3 | 78.33% | 15.4 | 79.06% | 57.6 | 79.67% | 52.7 | 79.29% | 53.7 | 79.97%
S-APES | 8.5 | 75.7% | 8.5 | 56.64% | 8.5 | 77.01% | 25.6 | 78.14% | 23.6 | 73.4% | 23.9 | 76.12%
Table 4: Comparison with baseline frameworks on user-level central privacy
budget and accuracy under the all the personalized privacy budget settings.
$\delta^{uc}=3.6\times 10^{-5}$. Total epochs: 40. Figure 4: Error of
approximation for calibrating noisy gradients. Most values of
$(\tilde{g_{i}}-\mathbb{E}[\tilde{\bar{g_{i}}}])$ concentrate around zero.
Figure 5: Privacy Bounds with smaller privacy budget range. The difference
between EoN and baselines becomes smaller, but absolute value of
$\epsilon^{c}$ of EoN is lower than larger range. Figure 6: Privacy Bounds
with larger privacy budget range. EoN gains more obvious amplification effect.
Uniform3 denotes $\mathcal{U}(0.05,3)$, Gauss3 denotes $\mathcal{N}(0.5,1)$,
MixGauss3 denotes 90% $\mathcal{N}(0.5,1)$ and 10% $\mathcal{N}(3,1)$. All the
clip range of $\epsilon^{l}$ is in $[0.05,3]$. Figure 7: Variance of outputs
of CLap on different $C$ and $\epsilon^{l}$. Smaller variance leads makes CLap
more stable for varying parameters, which benefits from limited output ranges
. Figure 8: Bias of CLap outputs on different $C$ and $\epsilon^{l}$. Bias of
CLap perturbation is larger than Lap perturbation, hence calibration is
necessary.