#  Uldp-FL: Federated Learning with Across Silo User-Level Differential
Privacy

Fumiyuki Kato  Kyoto University
<EMAIL_ADDRESS>Li Xiong  Emory University
<EMAIL_ADDRESS>Shun Takagi  Yang Cao  Kyoto University
<EMAIL_ADDRESS>Hokkaido University
<EMAIL_ADDRESS>Masatoshi Yoshikawa  Osaka Seikei University
<EMAIL_ADDRESS>
###### Abstract

Differentially Private Federated Learning (DP-FL) has garnered attention as a
collaborative machine learning approach that ensures formal privacy. Most DP-
FL approaches ensure DP at the record-level within each silo for cross-silo
FL. However, a single user’s data may extend across multiple silos, and the
desired user-level DP guarantee for such a setting remains unknown. In this
study, we present Uldp-FL, a novel FL framework designed to guarantee user-
level DP in cross-silo FL where a single user’s data may belong to multiple
silos. Our proposed algorithm directly ensures user-level DP through per-user
weighted clipping, departing from group-privacy approaches. We provide a
theoretical analysis of the algorithm’s privacy and utility. Additionally, we
enhance the algorithm’s utility and showcase its private implementation using
cryptographic building blocks. Empirical experiments on real-world datasets
show substantial improvements in our methods in privacy-utility trade-offs
under user-level DP compared to baseline methods. To the best of our
knowledge, our work is the first FL framework that effectively provides user-
level DP in the general cross-silo FL setting.

###### Index Terms:

Federated Learning, Differential Privacy, User-level DP

##  I Introduction

Federated Learning (FL) [1] is a collaborative machine learning (ML) scheme in
which multiple parties train a single global model without sharing training
data. FL has attracted industry attention [2, 3] as concerns about the privacy
of training data have become more serious, as exemplified by GDPR [4]. It
should be noted that FL itself does not provide privacy protection for the
trained model [5, 6], which motivates for Differentially Private FL (DP-FL)
[7, 8], which guarantees a formal privacy for trained models based on
differential privacy (DP) [9].

Figure 1: In cross-silo FL, in general, records belonging to the same user can
exist across silos, e.g., a user can use several credit card companies. In
this study, we investigate how to train models satisfying user-level DP in
this setting.

Although DP is the de facto standard in the field of statistical privacy
protection, it has a theoretical limitation. The standard DP definition takes
a single record as a unit of privacy. This can easily break down in a
realistic setting where one user may provide multiple records, and can
deteriorate the privacy loss bound of DP. To this end, the notion of user-
level DP has been studied [10, 11, 12, 13]. In user-level DP, instead of a
single record, all records belonging to a single user are considered as a unit
of privacy, which is a stricter definition than standard DP. Note that we
distinguish user-level DP from group-privacy [14] which considers any $k$
records as privacy units. User-level DP has also been studied in the FL
context [15, 7, 16, 17, 8]. However, these studies focus on the cross-device
FL setting, where one user’s data belongs to a single device only.

Cross-silo FL [18, 19, 20, 21] is a practical variant of FL in which a
relatively small number of silos (e.g., hospitals or credit card companies)
participate in the training rounds. In contrast to cross-device FL, in cross-
silo FL, a single user can have multiple records across silos, as shown in
Figure 1. Existing cross-silo DP-FL studies [19, 20, 21] have focused on
record-level DP for each silo; user-level DP across silos has not been
studied. Therefore, our research question is: How do we design a FL framework
guaranteeing user-level DP across silos in cross-silo FL?

A naive design for an algorithm that guarantees user-level DP is a combination
of bounding user contributions (number of records) as those in [12, 13] and
group-privacy property of DP [14]. Group-privacy simply extends the
indistinguishability of the record-level DP to multiple records. We can
convert any DP algorithm to group-privacy version of DP (Lemma 1, 5), which we
formally define as Group DP (GDP) later. However, this approach can be
impractical due to the super-linear privacy bound degradation of conversion to
GDP and the need to appropriately limit the maximum number of user records
(group size) in a distributed environment. In particular, the former problem
is a fundamental issue for DP and highlights the need to develop algorithms
that directly satisfy user-level DP without requiring a conversion to GDP.

In this study, we present a novel cross-silo FL framework named Uldp-FL,
designed to directly guarantee user-level DP through the incorporation of per-
user weighted clipping. The contributions of our work are summarized as
follows:

  * •

We introduce a problem setting for cross-silo FL under user-level DP across
silos, as illustrated in Figure 1.

  * •

We propose the Uldp-FL framework and design baseline algorithms capable of
achieving user-level DP across silos. The baseline algorithms combine limiting
the maximum number of records per user and using group-privacy with DP-SGD
[22] for each silo.

  * •

Our proposed algorithm ULDP-AVG/SGD directly satisfy user-level DP by
implementing user-level weighted clipping within each silo, which can
effectively bound user-level sensitivity for unlimited number of a single
user’s records across silos. We provide theoretical analysis on the ULDP-AVG,
showing a user-level DP bound and a convergence analysis.

  * •

We evaluate our proposed method and baseline approaches through comprehensive
experiments on various real-world datasets. The results underscore that our
proposed method yields superior trade-offs between privacy and utility
compared to the baseline approaches.

  * •

We further design an effective method by refining the weighting strategy for
user-level clipping bounds. Since this approach may lead to additional privacy
leakage of the training data, we develop a private protocol employing
cryptographic techniques. We evaluate the extra computational overhead of the
proposed private protocol using real-world benchmark scenarios.

##  II Background & Preliminaries

###  II-A Cross-silo Federated learning

In this work, we consider the following cross-silo FL scenario. We have a
central aggregation server and silo set $S$ participating in all rounds. In
each round, the server aggregates models from all silos and then redistributes
the aggregated models. Each silo $s\in S$ optimizes a local model $f_{s}$,
which is the expectation of a loss function $F(x;\xi)$ that may be non-convex,
where $x\in\mathbb{R}^{d}$ denotes the model parameters and $\xi$ denotes the
data sample, and the expectation is taken over local data distribution
$\mathcal{D}_{s}$. In cross-silo FL, we optimize this global model parameter
cooperatively across all silos. Formally, the overarching goal in FL can be
formulated as follows:

$\displaystyle\min_{x}\,\left\\{f(x):=\frac{1}{|S|}\sum_{s\in
S}{f_{s}(x)}\right\\},\,f_{s}(x):=\mathbb{E}_{\xi\sim\mathcal{D}_{s}}F(x;\xi).$
(1)

In our work, we introduce additional notations. We have user set $U$ across
all datasets across silos, where each record belongs to one user $u\in U$, and
each user may have multiple records in one silo and across multiple silos.
Each silo $s$ has local objectives for each user $u$,
$f_{s,u}:=\mathbb{E}_{\xi\sim\mathcal{D}_{s,u}}F(x;\xi)$, where
$\mathcal{D}_{s,u}$ is the data distribution of $s$ and $u$. In round
$t\in[T]$ in FL, the global model parameter is denoted as $x_{t}$.

Note that this modeling is clearly different from cross-device FL in that
there is no constraint that one user should belong to one device. Records from
one user can belong to multiple silos. For example, the same customer may use
several credit card companies, etc. Additionally, all silos participate in all
training rounds, unlike the probabilistic participation in cross-device FL
[17], and the number of silos $|S|$ is small, around 2 to 100.

###  II-B Differential Privacy

DP [9] is a rigorous mathematical privacy definition that quantitatively
evaluates the degree of privacy protection when publishing outputs.

######  Definition 1 ($(\epsilon,\delta)$-DP).

A randomized mechanism $\mathcal{M}:\mathcal{D}\rightarrow\mathcal{Z}$
satisfies $(\epsilon,\delta)$-DP if, for any two input databases
$D,D^{\prime}\in\mathcal{D}$ s.t. $D^{\prime}$ differs from $D$ in at most one
record and any subset of outputs $Z\subseteq\mathcal{Z}$, it holds that

$\displaystyle\Pr[\mathcal{M}(D)\in
Z]\leq\exp(\epsilon)\Pr[\mathcal{M}(D^{\prime})\in Z]+\delta.$ (2)

We call databases $D$ and $D^{\prime}$ as neighboring databases. The maximum
difference of the output for any neighboring database is referred to as
sensitivity, as defined in Definition 4. We label the original definition as
record-level DP because the neighboring databases differ in only one record.

To extend privacy guarantees to multiple records, group-privacy [14] has been
explored as a solution. We refer to the group-privacy version of DP as Group
DP (GDP) and define it as follows:

######  Definition 2 ($(k,\epsilon,\delta)$-GDP).

A randomized mechanism $\mathcal{M}:\mathcal{D}\rightarrow\mathcal{Z}$
satisfies $(k,\epsilon,\delta)$-GDP if, for any two input databases
$D,D^{\prime}\in\mathcal{D}$, s.t. $D^{\prime}$ differs from $D$ in at most
$k$ records and any subset of outputs $Z\subseteq\mathcal{Z}$, Eq. (2) holds.

GDP is a versatile privacy definition, as it can be applied to existing DP
mechanisms without modification. To convert $(\epsilon,\delta)$-DP to
$(k,\epsilon,\delta)$-GDP, it is known that any $(\epsilon,0)$-DP mechanism
satisfies $(k,k\epsilon,0)$-GDP [14]. However, in the case of any $\delta>0$,
$\delta$ increases super-linearly [23], leading to a much larger $\epsilon$
(Lemma 1). Also, we can compute GDP using group-privacy property of Rényi DP
[24]. First, we calculate the RDP of the algorithm, then convert it to group
version of RDP, and subsequently to GDP (Lemma 5).

Figure 2: Group-privacy conversion results.

Figure 2 illustrates a numerical comparison of the group-privacy conversion
from DP to GDP with normal DP (Lemma 1) and RDP (Lemma 5). We repeatedly
execute the Gaussian mechanism and calculate the final GDP. We plot various
group sizes, $k$, on the x-axis and $\epsilon$ of GDP at fixed
$\delta=10^{-5}$ on the y-axis. The conversion of normal DP with fixed
$\delta$ is complex and elaborated in Appendix -D1. Significantly, the result
indicates that as the group size, $k$, increases, $\epsilon$ grows rapidly,
underscoring a considerable degradation in the privacy bound of GDP. For
instance, with $\epsilon=2.85$ in record-level ($k=1$), the value reaches 2100
for only $k=32$, and 11400 at $k=64$. While there might be some looseness in
the group-privacy conversion of RDP compared to normal DP for some small group
sizes, the difference is relatively minor (roughly three times at most). And
the RDP’s conversion is easier to compute with a fixed $\delta$. Hence, we
utilize RDP’s conversion in our experiments.

###  II-C Differentially Private FL

DP has been applied to the FL paradigm, where the goal is to ensure that the
trained model satisfies DP. A popular DP variant in the context of cross-
device FL is user-level DP (also known as client-level DP) [7, 25, 8].
Informally, this definition ensures indistinguishability for device
participation and has demonstrated a favorable privacy-utility trade-off even
with large-scale models [17]. These studies often employ secure aggregation
[26, 27] to mitigate the need for trust in other parties during FL model
training. This is achieved by allowing the server and other silos to only
access appropriately perturbed models after aggregation. This is often known
as Distributed DP [8, 28]. In particular, shuffling-based variants have
recently attracted a great deal of attention [28, 29, 30] and are being
deployed in FL [31], which also provides user-level DP. All of these studies
assume that a single device holds all records for a single user, i.e., cross-
device FL. However, in a cross-silo setting, this definition does not extend
meaningful privacy protection to individual users when they possess multiple
records across silos.

Another DP definition in cross-silo FL is a variant offering record-level DP
within each silo [19, 20, 21], which is referred to as Silo-specific sample-
level or Inter-silo record-level DP. These studies suggest that record-level
DP can guarantee user-level DP through group-privacy [14]. However, they
cannot account for settings where a single user may have records across
multiple silos. To the best of our knowledge, there exists no method for
training models that satisfy user-level DP in cross-silo FL where a single
user records may extend across multiple silos.

##  III Uldp-FL Framework

###  III-A Trust model and Assumptions

We assume that all (two or more) silos and aggregation servers are semi-
honest, meaning they observe the information but do not deviate from the
protocol. This is a typical assumption in prior works [26, 32]. In our study,
aggregation is performed using secure aggregation to ensure that the server
only gains access to the model after aggregation [8]. All communications
between the server and silos are encrypted with SSL/TLS, and third parties
with the ability to snoop on communications cannot access any information
except for the final trained model. We assume that there is no collusion,
which is reasonable given that silos are socially separate institutions (such
as different hospitals or companies). Additionally, in our scenario, we assume
that record linkage [33] across silos has already been completed, resulting in
shared common user IDs. Both the server and the silos are aware of the total
number of users $|U|$ with at least one record and the number of silos $|S|$.

###  III-B Privacy definition

In contrast to GDP, which offers indistinguishability for any $k$ records,
user-level DP [11, 7] provides a more reasonable user-level
indistinguishability. While [7] focuses solely on a cross-device FL context,
we re-establish user-level DP (ULDP) in the cross-silo setting as follows:

######  Definition 3 ($(\epsilon,\delta)$-ULDP).

A randomized mechanism $\mathcal{M}:\mathcal{D}\rightarrow\mathcal{Z}$
satisfies $(\epsilon,\delta)$-ULDP if, for any two input databases across
silos $D,D^{\prime}\in\mathcal{D}$, s.t. $D^{\prime}$ differs from $D$ in at
most one user’s records, and any $Z\subseteq\mathcal{Z}$, Eq. (2) holds.

The fundamental difference from record-level DP lies in the definition of the
neighboring databases, which inherently defines user-level sensitivity.
Additionally, it is important to emphasize that the input database $D$
represents the comprehensive database spanning across silos.

If the number of records per user in the database is less than or equal to
$k$, it is clear that GDP is a generalization of ULDP, and the following
proposition holds.

######  Proposition 1.

If a randomized mechanism $\mathcal{M}$ is $(k,\epsilon,\delta)$-GDP with
input database $D$ in which any user has at most $k$ records, the mechanism
$\mathcal{M}$ with input database $D$ also satisfies $(\epsilon,\delta)$-ULDP.

One drawback of GDP is the challenge of determining the appropriate value for
$k$. Setting $k$ to the maximum number of records associated with any
individual user could lead to introducing excessive noise to achieve the
desired privacy protection level. On the other hand, if a smaller $k$ is
chosen, the data of users with more than $k$ records must be excluded from the
dataset, potentially introducing bias and compromising model utility. In this
context, while several studies have analyzed the theoretical utility for a
given $k$ [10, 11] and theoretical considerations for determining $k$ have
been partially explored in [13], it still remains an open problem. In
contrast, ULDP does not necessitate the determination of $k$. Instead, it
requires designing a specific ULDP algorithm.

###  III-C Baseline methods: ULDP-NAIVE/GROUP-$k$

We begin by describing two baseline methods. The first method is ULDP-NAIVE
(described in Algorithm 3), a straightforward approach using substantial
noise. It is an extension of DP-FedAVG [17], where each silo locally optimizes
with multiple epochs, computing the model delta, clipping by $C$ and adding a
Gaussian noise with variance $\sigma^{2}C^{2}$. In contrast, in ULDP-NAIVE,
since a single user may contribute to the model delta of all silos, the
sensitivity across silos is $|C|*S$ for the aggregated model delta (Line 15).
Moreover, compared to DP-FedAVG focusing on cross-device FL, the number of
model delta samples (number of silos as versus number of devices) is very
small, which also results in larger variance. Hence, ULDP-NAIVE satisfies ULDP
at a significant sacrifice in utility. Note that any following algorithm uses
secure aggregation and all of proofs of the following theorems are shown in
Appendix -A5.

######  Theorem 1.

For any $0<\delta<1$ and $\alpha>1$, given noise multiplier $\sigma$, ULDP-
NAIVE satisfies
$(\epsilon=\frac{T\alpha}{2\sigma^{2}}+\log{((\alpha-1)/\alpha)}-(\log{\delta}+\log{\alpha})/(\alpha-1),\delta)$-ULDP
after $T$ rounds. (The actual value of $\epsilon$ is numerically calculated by
selecting the optimal $\alpha$ so that $\epsilon$ is minimized.)

Algorithm 1 ULDP-GROUP-${k}$

1:$S$: silo set (silo $s\in S$), $\eta_{l}$: local learning rate, $\eta_{g}$:
global learning rate, $\sigma$: noise parameter, $D_{s}$: training dataset of
silo $s$, $C$: clipping bound, $T$: total round, $Q$: #local epochs, $k$:
group size, $\gamma$: sampling rate, $\mathbf{B}$: flags for limit
contribution s.t. for each matrix $\mathbf{b}^{s}\in\mathbf{B}$ if
$b^{s}_{u,i}=1$ the user $u$’s $i$-th record in silo $s$ is used in training
dataset, otherwise the record is excluded

2:procedure Server

3: Initialize model $x_{0}$

4: for each round $t=0,1,\ldots,T-1$ do

5: for each silo $s\in S$ do

6: $\Delta^{s}_{t}\leftarrow$
Client$(x_{t},C,\sigma,\eta_{l},\gamma,\mathbf{b}^{s})$

7: $\theta_{t+1}\leftarrow\theta_{t}+\eta_{g}\frac{1}{|S|}\sum_{s\in
S}{\Delta^{s}_{t}}$

8:procedure Client($x_{t},C,\sigma,\eta_{l},\gamma,\mathbf{b}^{s}$)

9: $D^{\prime}_{s}\leftarrow$ filter $D_{s}$ by $\mathbf{b}^{s}$

10: $x^{Q}_{t}\leftarrow$DP-
SGD$(\theta_{t},D^{\prime}_{s},C,\sigma,\eta_{l},\gamma,Q)$

11:$\triangleright$ Algorithm 1 in [22]

12: $\Delta_{t+1}\leftarrow x^{Q}_{t}-x_{t}$

13: return $\Delta_{t+1}$

Secondly, we introduce the baseline algorithm ULDP-GROUP-$k$ (described in
Algorithm 1), which combines the constraint of limiting each user’s records to
a given $k$ while satisfying $(k,\epsilon,\delta)$-GDP. As proposition1
implies, this ensures $(\epsilon,\delta)$-ULDP. The algorithm achieves GDP by
implementing DP-SGD [22] within each silo. The algorithm’s core principle is
akin to that of [19], except for the global setting of a single privacy budget
across silos. Before executing DP-SGD, it is essential to constrain the number
of records per user to $k$ (Line 8). We accomplish this by employing flags,
denoted as $\mathbf{B}$, which indicates the records to be used for training
(i.e., $b^{s}_{u,i}=1$), with a total of $k$ records for each user across all
silos (i.e., $\forall{u},\sum_{s,i}{b^{s}_{u,i}}\leq k$). This flag must be
the same for all rounds for privacy guarantee. We ignore the privacy concerns
in generating the flags because this is the baseline method. The, we perform
DP-SGD to satisfy record-level DP (Line 9), which is subsequently converted to
GDP.

######  Theorem 2.

For any $0<\delta<1$, any integer $k$ to the power of 2 and $\alpha>2^{k+1}$,
ULDP-GROUP-${k}$ satisfies
$(3^{k}\rho+\log{((\frac{\alpha}{2^{k}}-1)/\frac{\alpha}{2^{k}})}-(\log{\delta}+\log{\frac{\alpha}{2^{k}}})/(\frac{\alpha}{2^{k}}-1),\delta)$-ULDP
where $\rho=\max_{s\in S}\rho_{s}$ s.t. for each silo $s\in S$, DP-SGD of
local subroutine satisfies $(\alpha,\rho_{s})$-RDP.

While ULDP-GROUP shares algorithmic similarities with the existing record-
level DP cross-silo FL framework [19], it does present weaknesses from several
perspectives: (1) It presents significant degradation of privacy bounds due to
the group-privacy conversion (DP to GDP). (2) Determining the appropriate
group size $k$ is a challenging task [13]. Moreover, this process demands
substantial insights into the data distribution across silos and might even
breach the trust model as well as the determination of the flags $\mathbf{B}$.
(3) Using group-privacy to guarantee ULDP requires removing records from the
training dataset. This can introduce a bias and can cause a degradation in the
utility [13, 34]. Our next proposed method aims to overcome these challenges.

###  III-D Advanced methods: ULDP-AVG/SGD

Algorithm 2 ULDP-AVG

1:$U$: user set (user $u\in U$), $S$: silo set (silo $s\in S$), $\eta_{l}$:
local learning rate, $\eta_{g}$: global learning rate, $\sigma$: noise
parameter, $C$: clipping bound, $T$: total round, $Q$: #local epochs,
$\mathbf{W}=(\mathbf{w}_{1},...,\mathbf{w}_{|S|})$: matrix with weight for
user $u$ and silo $s$, and $\forall u\in U$, $w_{s,u}\in\mathbf{w}_{s}$ and
$\sum_{s\in S}{w_{s,u}}=1$

2:procedure Server

3: Initialize model $x_{0}$

4: for each round $t=0,1,\ldots,T-1$ do

5: for each silo $s\in S$ do

6: $\Delta^{s}_{t}\leftarrow$ Client$(x_{t},\mathbf{w}_{s},C,\sigma,\eta_{l})$

7: $x_{t+1}\leftarrow x_{t}+\eta_{g}\frac{1}{|U||S|}\sum_{s\in
S}{\Delta^{s}_{t}}$

8:procedure Client($x_{t},\mathbf{w}_{s},C,\sigma,\eta_{l}$)

9: for user $u\in U$ do $\triangleright$ per-user training with
$\mathcal{D}_{s,u}$

10: $x^{s,u}_{t}\leftarrow x_{t}$

11: for epoch $q=0,1,\ldots,Q-1$ do

12: Compute stochastic gradients $g^{s,u}_{t,q}$

13:$\triangleright$ $\mathbb{E}[g^{s,u}_{t,q}]=\nabla f_{s,u}(x^{s,u}_{t})$

14: $x^{s,u}_{t}\leftarrow x^{s,u}_{t}-\eta_{l}g^{s,u}_{t,q}$

15: $\Delta^{s,u}_{t}\leftarrow x^{s,u}_{t}-x_{t}$

16: $\tilde{\Delta}^{s,u}_{t}\leftarrow
w_{s,u}\cdot\Delta^{s,u}_{t}\cdot\min{\left(1,\frac{C}{\lVert\Delta^{s,u}_{t}\rVert_{2}}\right)}$
$\triangleright$ per-user weighted clipping

17: $\Delta^{s}_{t}\leftarrow\sum_{u\in
U}{\tilde{\Delta}^{s,u}_{t}}+\mathcal{N}(0,I\sigma^{2}C^{2}/|S|)$

18: return $\Delta^{s}_{t}$

To directly satisfy ULDP without using group-privacy, we design ULDP-AVG
(Algorithm 2) and ULDP-SGD (Algorithm 4). These can be seen as variants of DP-
FedAVG and DP-FedSGD [17]. In most cases, DP-FedAVG is preferred in terms of
privacy-utility trade-off and communication-cost while DP-FedSGD might be
preferable only when we have fast networks [17], which is also the case for
ULDP-AVG and ULDP-SGD. In the following analysis, we focus on ULDP-AVG.

Intuitively, ULDP-AVG limits each user’s contribution to the model by training
the model for each user in each silo and perform per-user per-silo clipping
across all silos with globally prepared clipping weights. In each round, ULDP-
AVG computes parameter deltas using a per-user dataset in each silo to achieve
ULDP: selecting a user (Line 8), training local model with $Q$ epochs using
only the selected user’s data (Lines 10-13), calculating model delta (Line 14)
and clipping the delta (Line 15). These clipped deltas $\Delta^{s,u}_{t}$ are
then weighted by $w_{s,u}$ (Line 15) and summed for all users (Line 16). As
long as the weights $w_{s,u}$ satisfies constraints $\forall u\in U$,
$w_{s,u}>0$ and $\sum_{s\in S}{w_{s,u}}=1$, each user’s contribution, or
sensitivity, to the delta aggregation $\sum_{s\in S}{\Delta^{s}_{t}}$ is
limited to $C$ at most. This allows ULDP-AVG to provide user-level privacy. We
will discuss better ways to determine $\mathbf{W}$ later, but a simple way is
to set $w_{s,u}=1/|S|$. Compared to DP-FedAVG, ULDP-AVG increases the
computational cost due to per-user local training iteration but keeping
communication costs the same, which is likely acceptable in the cross-silo FL
setting.

######  Theorem 3.

For any $0<\delta<1$ and $\alpha>1$, given noise multiplier $\sigma$, ULDP-AVG
satisfies
$(\epsilon=\frac{T\alpha}{2\sigma^{2}}+\log{((\alpha-1)/\alpha)}-(\log{\delta}+\log{\alpha})/(\alpha-1),\delta)$-ULDP
after $T$ rounds.

######  Remark 1.

For further privacy amplification, we introduce user-level sub-sampling, which
can make RDP smaller according to sub-sampled amplification theorem [35].
User-level sub-sampling must be done globally across silos. The sub-sampling
can be implemented in the central server by controlling the weight
$\mathbf{W}$ for each round, i.e., all of users not sub-sampled are set to 0.
This may violate privacy against the server but does not affect the DP when
the final model is provided externally as discussed in C.3 of [25]. We have
the detailed algorithm and experimental results to show the effectiveness of
user-level sub-sampling in Appendix -D4.

######  Theorem 4 (Convergence analysis on ULDP-AVG).

For ULDP-AVG, with assumptions 1, 2 and 3 and $\min_{x}{f(x)}\geq f^{*}$, let
local / global learning rates $\eta_{l}$ / $\eta_{g}$ be chosen as s.t.
$\eta_{g}\eta_{l}\leq\frac{1}{3QL\bar{\alpha}_{t}}$ and
$\eta_{l}<\frac{1}{\sqrt{30}QL}$, we have,

$\displaystyle\cfrac{1}{T}$
$\displaystyle\sum_{t=0}^{T-1}{\mathbb{E}\left[\left\lVert\nabla
f(x_{t})\right\rVert^{2}\right]}$ $\displaystyle\leq\;\;$
$\displaystyle\cfrac{1}{cT\eta_{g}\eta_{l}Q|S|}\left(\mathbb{E}\left[\frac{f(x_{0})}{\underline{C}}\right]-\mathbb{E}\left[\frac{f^{*}}{\bar{C}}\right]\right)$
$\displaystyle+$
$\displaystyle\frac{5}{2c}L^{2}Q\eta_{l}^{2}(\sigma_{l}^{2}+6Q\sigma_{g}^{2})+\cfrac{3\bar{C}L\eta_{g}\eta_{l}\sigma_{l}^{2}}{2c|S|^{2}|U|}+\cfrac{L\eta_{g}\sigma^{2}C^{2}d}{2c\underline{C}\eta_{l}Q|S||U|^{2}}$
$\displaystyle+$ $\displaystyle
A_{1}\sum_{t=0}^{T-1}{\mathbb{E}\left[\sum_{s\in S}\sum_{u\in
U}{\left(\left|\alpha^{s,u}_{t}-\tilde{\alpha}^{s,u}_{t}\right|+\left|\tilde{\alpha}^{s,u}_{t}-\bar{\alpha}_{t}\right|\right)}\right]}$
$\displaystyle+$ $\displaystyle
A_{2}\sum_{t=0}^{T-1}{\mathbb{E}\left[\sum_{s\in S}\sum_{u\in
U}{\left(\left|\alpha^{s,u}_{t}-\tilde{\alpha}^{s,u}_{t}\right|^{2}+\left|\tilde{\alpha}^{s,u}_{t}-\bar{\alpha}_{t}\right|^{2}\right)}\right]}$
(3)

where $c>0$,
$\bar{C}:=\smash{\displaystyle\max_{s,u,t}}{\left(\frac{C}{\max{(C,\eta_{l}\lVert\mathbb{E}\left[\sum_{q\in[Q]}g^{s,u}_{t,q}\right]\rVert)}}\right)}$,
$\underline{C}:=\smash{\displaystyle\min_{s,u,t}}{\left(\frac{C}{\max{(C,\eta_{l}\lVert\mathbb{E}\left[\sum_{q\in[Q]}g^{s,u}_{t,q}\right]\rVert)}}\right)}$,
$\alpha^{s,u}_{t}:=\frac{w_{s,u}C}{\max{(C,\eta_{l}\lVert\sum_{q\in[Q]}g^{s,u}_{t,q}\rVert)}}$,
$\tilde{\alpha}^{s,u}_{t}:=\frac{w_{s,u}C}{\max{(C,\eta_{l}\lVert\mathbb{E}\left[\sum_{q\in[Q]}g^{s,u}_{t,q}\right]\rVert)}}$,
$\bar{\alpha}_{t}:=\frac{1}{|S||U|}\sum_{s\in S}\sum_{u\in
U}{\tilde{\alpha}^{s,u}_{t}}$, $A_{1}:=\frac{G^{2}}{c\underline{C}|U|T}$ and
$A_{2}:=\frac{3L\eta_{g}\eta_{l}QG^{2}}{2c\underline{C}|U|T}$.

######  Remark 2.

The first three terms recover the standard convergence bound up to constants
for FedAVG [36] when considering participants in the FL as user-silo pairs
(i.e., we have $|S||U|$ participants). The asymptotic bound is
$O(\frac{1}{\sqrt{|S||U|QT}}+\frac{1}{T})$. Theorem 4 achieves this when we
choose the global and local learning rates $\eta_{g}=|S|\sqrt{|S||U|Q}$ and
$\eta_{l}=\frac{1}{\sqrt{T}QL}$, respectively. This requires a learning rate
$|S|$ times larger than the usual FedAVG with $|S||U|$ participants, which can
be interpreted as coming from the constraint on the weights $W$. The fourth
term is the convergence overhead due to Gaussian noise addition, and the last
fifth and sixth terms are the overhead due to bias from the clippings. If both
of the noise and the clipping bias are zero, the convergence rate is
asymptotically the same as the FedAVG convergence rate.

######  Remark 3.

The fourth term, which accounts for the overhead due to noise, differs
slightly from DP-FedAVG. This term is inversely proportional to $|S||U|^{2}$.
As highlighted in the previous remark, if the global learning rate is set as
$\eta_{g}=|S|\sqrt{|U|Q}$ in ULDP-AVG, this term becomes proportional to
$\sqrt{|U|}/|U|^{2}$, which is consistent with the case of DP-FedAVG with
$|U|$ participants.

######  Remark 4.

The fifth and sixth terms correspond to the overhead due to the clipping
biases $\left|\alpha^{s,u}_{t}-\tilde{\alpha}^{s,u}_{t}\right|$ and
$\left|\tilde{\alpha}^{s,u}_{t}-\bar{\alpha}_{t}\right|$, respectively. The
quantity $\left|\alpha^{s,u}_{t}-\tilde{\alpha}^{s,u}_{t}\right|$ represents
the local gradient variance across all users in all silos and can be made zero
by full-batch gradient decent. The noteworthy term is
$\left|\tilde{\alpha}^{s,u}_{t}-\bar{\alpha}_{t}\right|$. As discussed in the
analysis of [37], this term is influenced by structures of the neural network
and data heterogeneity. It roughly quantifies how much the magnitudes of all
gradients deviate from the global mean gradient. We may be able to minimize
these values by selecting appropriate weights $\mathbf{W}$, guided by the
following optimization problem:

$\displaystyle\min_{\mathbf{W}}{\sum_{s\in S}\sum_{u\in
U}\left|\tilde{\alpha}^{s,u}_{t}-\bar{\alpha}_{t}\right|},\;\text{s.t.,}\;w_{s,u}>0,\forall{u},\sum_{s\in
S}{w_{s,u}}=1$ $\displaystyle\left(=\sum_{s\in S}\sum_{u\in
U}\left|w_{s,u}C_{s,u}-\frac{1}{|S||U|}\sum_{s^{\prime}\in
S}\sum_{u^{\prime}\in
U}{w_{s^{\prime},u^{\prime}}C_{s^{\prime},u^{\prime}}}\right|\right)$

where
$C_{s,u}:=\frac{C}{\max{(C,\eta_{l}\lVert\mathbb{E}\left[\sum_{q\in[Q]}g^{s,u}_{t,q}\right]\rVert)}}$.

However, it is hard to determine the optimal weights because we cannot predict
the gradients norm in advance, which also can cause another privacy issue.

Comparison to baselines. Compared to ULDP-GROUP, ULDP-AVG satisfies ULDP
without group-privacy, thus avoiding the large privacy bound caused from
group-privacy conversion, choosing group size $k$ and removing the records.
ULDP-AVG can be used for an arbitrary number of records per user. Also, it
differs from ULDP-NAIVE in the following point. Fundamentally, per-user
clipping can be viewed as cross-user FL (instead of cross-silo FL), which
ensures that each user contributes to only the user-specific portion of the
aggregated model updates (i.e., $\sum_{s\in S}{\tilde{\Delta}^{s,u}_{t}}$)
instead of entire aggregated update (i.e., $\sum_{s\in S}{\Delta^{s}_{t}}$),
thereby reducing sensitivity (as illustrated in Figure 7). The user
contributes only $1/|U|$ of the entire aggregated model update, which is
especially effective when $|U|$ is large as in cross-silo FL (i.e.,
$|S|\ll|U|$). Moreover, compute model delta in user-level leads to lower
Gaussian noise variances because of large $|U|$ while it also introduces new
biases.

###  III-E Better weighting strategy with private protocol

Here we consider the bias described in Remark 4. In our ULDP-AVG algorithm, we
have employed uniform clipping weights, i.e. for any $s\in S$ and $u\in U$,
$w_{s,u}=1/|S|$, as a feasible solution to the problem without privacy
violation. However, for more sophisticated solution, we propose following
weighting strategy. We set a weight $w^{opt}_{s,u}$ for $C_{s,u}$ according to
the number of records, following the heuristic that a gradient computed from a
large number of records yields a better estimation that is closely aligned
with the average. This results in the smaller bias. That is, let $n_{s,u}$ be
the number of records for user $u$ in silo $s$, we set the weight as

$\displaystyle w^{opt}_{s,u}:=\frac{n_{s,u}}{\sum_{s\in|S|}{n_{s,u}}}.$ (4)

We empirically demonstrate the effectiveness of this strategy in the
experiments. However, the crucial question arises: how can it be implemented
without privacy violation?

For the aforementioned better weighting strategy, a central server could
aggregate histograms encompassing the user population (number of records per
user) within each silo’s dataset. Subsequently, the server could compute the
appropriate weights for each silo and distribute these weights back to the
respective silos. However, this approach raises significant privacy concerns.
It leads to a privacy breach as the silo histograms are directly shared with
the server. Additionally, when the server broadcasts the weights back to the
silos, it enables an estimation of the entire histogram of users across all
the silos, posing a similar privacy risk against other silos. In essence, the
privacy protection necessitates preserving confidentiality in both of these
directions. This is challenging because additive homomorphic encryption
techniques such as Paillier cryptosystem cannot handle inverses to compute
weights as in Eq. (4), and the raw weights are disclosed to the party with the
secret key when encrypting the weights.

To address this privacy issue, we design a novel private weighting protocol to
securely aggregate the user histograms from silos, compute the per-user
clipping weight for each user in each silo, and aggregate the weighted sum
from all silos. Our protocol leverages well-established cryptographic
techniques, including secure aggregation [26, 32], the Paillier cryptosystem
[38] and multiplicative blinding [39]. Intuitively, our protocol employs
multiplicative blinding to hide user histograms against the server while
server can compute inverses of blinded histogram to compute the weights (Eq.
(4)). Subsequently, the server employs the Paillier encryption to conceal the
inverses of blinded histograms because silo knows the blinded masks. Also it
enables the server and silos to compute private weighted sum aggregation with
its additive homomorphic property. The complete protocol and its correctness
and privacy are described in Appendix -B.

##  IV Experiments

In this section, we evaluate the privacy-utility trade-offs of the proposed
methods (ULDP-AVG/SGD), along with the previously mentioned baselines (ULDP-
NAIVE/GROUP-$k$) and a non-private baseline (FedAVG with two-sided learning
rates [36], denoted by DEFAULT). In ULDP-AVG/SGD, we set the weights as
$w_{s,u}=1/|S|$ for all $s$ and $u$, the one using $w^{opt}_{s,u}$ is referred
to as ULDP-AVG-w. Regarding ULDP-GROUP-$k$, flags $\mathbf{B}$ are generated
for existing records to minimize waste on filtered out records, despite the
potential privacy concerns. Various values, including the maximum number of
user records, the median, 2, and 8, are tested as group size $k$ and we report
GDP using group-privacy conversion of RDP. In cases where $k$ is not a power
of 2, the computed $\epsilon$ is reported for the largest power of 2 below
$k$, showcasing the lower bound of GDP to underscore $\epsilon$ is large. The
hyperparameters, including global and local learning rates $\eta_{g}$,
$\eta_{l}$, clipping bound $C$, and local epoch $Q$, are set individually for
each method. Execution times are measured on macOS Monterey v12.1, Apple M1
Max Chip with 64GB memory with Python 3.9 and 3072-bit security. Most of
results are averaged over 5 runs and the colored area in the graph is the
standard deviation. All of implementations and experimental settings are
available at https://github.com/FumiyukiKato/uldp-fl.

Datasets used in our evaluation comprise real-world open datasets, including
Credicard [40] and two medical datasets, HeartDisease and TcgaBrca from [18],
a benchmark datasets for cross-silo FL. We also use MNIST in Appendix.
Creditcard is a popular tabular dataset for credit card fraud detection from
Kaggle. We undersample the dataset and use about 25K training data and a
neural network with about 4K parameters. For HeartDisease and TcgaBrca, we use
the same setting such as number of silos (i.e., 4 and 6), data assignments to
the silos, models, loss functions, etc. as shown in the original paper. These
two datasets are quite small and the model has less than 100 parameters. For
all datasets, how to allocate the records to users and silos are explained in
Appendix -D2.

(a) $n\approx 246$ ($|U|=100$), uniform, Test Accuracy and Privacy.

(b) $n\approx 246$ ($|U|=100$), zipf, Test Accuracy and Privacy.

(c) $n\approx 25$ ($|U|=1000$), uniform, Test Accuracy and Privacy.

(d) $n\approx 25$ ($|U|=1000$), zipf, Test Accuracy and Privacy.

Figure 4: Privacy-utility trade-offs on Creditcard dataset.

Figure 5: Test loss of Creditcard: Weighting method is effective, especially
in skewed distribution in many silos.

Figure 6: With a small model, the private weighting protocol has a practical
execution time.

Privacy-utility trade-offs under ULDP. Figures 4 show the utility and privacy
evaluation results on Creditcard. The other results on MNIST, HeartDisease and
TcgaBrca are shown in Appendix -D4. The average number of records per user
(denoting as $n$) in entire silos and the distribution (uniform or zipf, as
described in Appendix -D2) changes for each figure. All experiments used a
fixed noise parameter $\sigma=5.0$ and $\delta=10^{-5}$, utility metrics
(Accuracy for Creditcard) are displayed in left side and accumulated privacy
consumption $\epsilon$ for ULDP are depicted in right side. Note that the
privacy bounds for ULDP-GROUP-$k$ are derived from the local DP-SGD and depend
on not only the group size $k$ but also the size of the local training
dataset.

Overall, the proposed method ULDP-AVG/SGD achieves competitive utility with
fast convergence and high accuracy, while achieving considerably small privacy
bounds, which means the significantly better privacy-utility trade-offs
compared to other baselines. We see that the baseline method, ULDP-NAIVE, has
low accuracy and that ULDP-GROUP-$k$ requires much larger privacy budgets,
which is consistent with the analysis on the conversion of group privacy
described earlier. The convergence speed of ULDP-AVG is faster than that of
ULDP-SGD, which is the same as that of DP-FedAVG/SGD. Nevertheless, there is
still a gap between ULDP-AVG and the non-private method (DEFAULT) in terms of
convergence speed and ultimately achievable accuracy, as a price for privacy.
Also, as shown in Figure 4(c), for small $n$ (i.e., large number of users),
ULDP-GROUP-max/median show higher accuracy than ULDP-AVG. This is likely due
to the overhead from finer datasets at user-level, which increases the bias
compared to DP-FedAVG, as seen in the theoretical convergence analysis for
ULDP-AVG.

To highlight the effectiveness of the better weighting strategy, Figure 5
shows the test losses of Creditcard on different record distributions with
ULDP-AVG and ULDP-AVG-w. We show the results with various number of silos 5,
20 and 50. The need for the better weight strategy is emphasized by the
distribution of the records and number of silos $|S|$. When there is large
skews in the user records, as in zipf, giving equal weights (i.e., ULDP-AVG)
results in waste and opens up a large gap from ULDP-AVG-w. This trend becomes
even more significant as $|S|$ increases because all weights become smaller in
ULDP-AVG.

Overhead of private weighting protocol. We evaluate the overheads of execution
time with the private weighting protocol. Figure 6 shows the execution times
following HeartDisease and TcgaBrca with the number of users 10 and 100,
respectively, with a skewed (zipf) distribution. The left figure shows the
time required for a local training in each silo, and the right figure shows
the execution time for key exchange, preparation of blinded histograms, and
aggregation. As shown in the figure, the execution time of the local training
is dominant and it increases with the larger number of users. Overall, it
shows realistic execution times under these benchmark scenarios [18]. However,
it still causes non-negligible overhead with room for improvement in
efficiency. We have more analysis with artificial dataset in Appendix -D4.

##  V Conclusion

In this paper, we proposed the first cross-silo user-level DP FL framework
where a user may have multiple records across silos and designed an algorithm
using per-user clipping to directly satisfy ULDP instead of group-privacy. In
addition, we developed a better weighting strategy that improves utility of
our proposed method and a novel protocol that performs it privately. Finally,
we demonstrated the effectiveness of the proposed method on several real-world
datasets and showed that it performs significantly better than existing
methods. We also verified that our proposed private protocol works in
realistic time in existing cross-silo FL benchmark scenarios. Further
improving the efficiency of the private protocol and the utility of ULDP
algorithms to a level comparable to non-private method are future work.

## References

  * [1] H. B. McMahan, E. Moore, D. Ramage, and B. A. y Arcas, “Federated learning of deep networks using model averaging,” _arXiv preprint arXiv:1602.05629_ , 2016.
  * [2] M. Paulik, M. Seigel, H. Mason, D. Telaar, J. Kluivers, R. van Dalen, C. W. Lau, L. Carlson, F. Granqvist, C. Vandevelde _et al._ , “Federated evaluation and tuning for on-device personalization: System design & applications,” _arXiv preprint arXiv:2102.08503_ , 2021.
  * [3] S. Ramaswamy, R. Mathews, K. Rao, and F. Beaufays, “Federated learning for emoji prediction in a mobile keyboard,” _arXiv preprint arXiv:1906.04329_ , 2019.
  * [4] M. Goddard, “The eu general data protection regulation (gdpr): European regulation that has a global impact,” _International Journal of Market Research_ , vol. 59, no. 6, pp. 703–705, 2017.
  * [5] M. Nasr, R. Shokri, and A. Houmansadr, “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)_. IEEE, 2019, pp. 739–753.
  * [6] B. Zhao, K. R. Mopuri, and H. Bilen, “idlg: Improved deep leakage from gradients,” _arXiv preprint arXiv:2001.02610_ , 2020.
  * [7] R. C. Geyer, T. Klein, and M. Nabi, “Differentially private federated learning: A client level perspective,” _NIPS 2017 Workshop: Machine Learning on the Phone and other Consumer Devices_ , 2017.
  * [8] P. Kairouz, Z. Liu, and T. Steinke, “The distributed discrete gaussian mechanism for federated learning with secure aggregation,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 5201–5212.
  * [9] C. Dwork, “Differential privacy,” in _Proceedings of the 33rd international conference on Automata, Languages and Programming-Volume Part II_. Springer-Verlag, 2006, pp. 1–12.
  * [10] Y. Liu, A. T. Suresh, F. X. X. Yu, S. Kumar, and M. Riley, “Learning discrete distributions: user vs item-level privacy,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 20 965–20 976, 2020.
  * [11] D. Levy, Z. Sun, K. Amin, S. Kale, A. Kulesza, M. Mohri, and A. T. Suresh, “Learning with user-level privacy,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 12 466–12 479, 2021.
  * [12] R. J. Wilson, C. Y. Zhang, W. Lam, D. Desfontaines, D. Simmons-Marengo, and B. Gipson, “Differentially private sql with bounded user contribution,” _Proceedings on privacy enhancing technologies_ , vol. 2020, no. 2, pp. 230–250, 2020.
  * [13] K. Amin, A. Kulesza, A. Munoz, and S. Vassilvtiskii, “Bounding user contributions: A bias-variance trade-off in differential privacy,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 263–271.
  * [14] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [15] Ú. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, S. Song, K. Talwar, and A. Thakurta, “Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation,” _arXiv preprint arXiv:2001.03618_ , 2020.
  * [16] H. B. McMahan, G. Andrew, U. Erlingsson, S. Chien, I. Mironov, N. Papernot, and P. Kairouz, “A general approach to adding differential privacy to iterative training procedures,” _arXiv preprint arXiv:1812.06210_ , 2018.
  * [17] H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang, “Learning differentially private recurrent language models,” _arXiv preprint arXiv:1710.06963_ , 2017\.
  * [18] J. Ogier du Terrail, S.-S. Ayed, E. Cyffers, F. Grimberg, C. He, R. Loeb, P. Mangold, T. Marchand, O. Marfoq, E. Mushtaq, B. Muzellec, C. Philippenko, S. Silva, M. Teleńczuk, S. Albarqouni, S. Avestimehr, A. Bellet, A. Dieuleveut, M. Jaggi, S. P. Karimireddy, M. Lorenzi, G. Neglia, M. Tommasi, and M. Andreux, “Flamby: Datasets and benchmarks for cross-silo federated learning in realistic healthcare settings,” in _Advances in Neural Information Processing Systems_ , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., vol. 35. Curran Associates, Inc., 2022, pp. 5315–5334.
  * [19] K. Liu, S. Hu, S. Z. Wu, and V. Smith, “On privacy and personalization in cross-silo federated learning,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 5925–5940, 2022.
  * [20] A. Lowy and M. Razaviyayn, “Private federated learning without a trusted server: Optimal algorithms for convex losses,” in _The Eleventh International Conference on Learning Representations_ , 2023. [Online]. Available: https://openreview.net/forum?id=TVY6GoURrw
  * [21] A. Lowy, A. Ghafelebashi, and M. Razaviyayn, “Private non-convex federated learning without a trusted server,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2023, pp. 5749–5786.
  * [22] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016, pp. 308–318.
  * [23] G. Kamath, “Cs 860 : Algorithms for private data analysis fall 2020 lecture 5 — approximate differential privacy,” http://www.gautamkamath.com/CS860notes/lec5.pdf, 2020, [Online; accessed 23-June-2023].
  * [24] I. Mironov, “Rényi differential privacy,” in _2017 IEEE 30th computer security foundations symposium (CSF)_. IEEE, 2017, pp. 263–275.
  * [25] N. Agarwal, P. Kairouz, and Z. Liu, “The skellam mechanism for differentially private federated learning,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 5052–5064, 2021.
  * [26] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in _proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1175–1191.
  * [27] J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova, “Secure single-server aggregation with (poly) logarithmic overhead,” in _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 1253–1269.
  * [28] A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev, “Distributed differential privacy via shuffling,” in _Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part I 38_. Springer, 2019, pp. 375–403.
  * [29] S. P. Liew, T. Takahashi, S. Takagi, F. Kato, Y. Cao, and M. Yoshikawa, “Network shuffling: Privacy amplification via random walks,” in _Proceedings of the 2022 International Conference on Management of Data_ , ser. SIGMOD ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 773–787. [Online]. Available: https://doi.org/10.1145/3514221.3526162
  * [30] S. Takagi, F. Kato, Y. Cao, and M. Yoshikawa, “From bounded to unbounded: Privacy amplification via shuffling with dummies,” in _2023 2023 IEEE 36th Computer Security Foundations Symposium (CSF) (CSF)_. Los Alamitos, CA, USA: IEEE Computer Society, jul 2023, pp. 520–535. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/CSF57540.2023.00034
  * [31] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. T. Suresh, “Shuffled model of differential privacy in federated learning,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 2521–2529.
  * [32] J. So, R. E. Ali, B. Güler, J. Jiao, and A. S. Avestimehr, “Securing secure aggregation: Mitigating multi-round privacy leakage in federated learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 37, no. 8, 2023, pp. 9864–9873.
  * [33] D. Vatsalan, Z. Sehili, P. Christen, and E. Rahm, “Privacy-preserving record linkage for big data: Current approaches and research challenges,” _Handbook of big data technologies_ , pp. 851–895, 2017.
  * [34] A. Epasto, M. Mahdian, J. Mao, V. Mirrokni, and L. Ren, “Smoothly bounding user contributions in differential privacy,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 13 999–14 010, 2020.
  * [35] Y.-X. Wang, B. Balle, and S. P. Kasiviswanathan, “Subsampled rényi differential privacy and analytical moments accountant,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 1226–1235.
  * [36] H. Yang, M. Fang, and J. Liu, “Achieving linear speedup with partial worker participation in non-iid federated learning,” _Proceedings of ICLR_ , 2021\.
  * [37] X. Zhang, X. Chen, M. Hong, Z. S. Wu, and J. Yi, “Understanding clipping for federated learning: Convergence and client-level differential privacy,” in _International Conference on Machine Learning, ICML 2022_ , 2022.
  * [38] A. B. Alexandru and G. J. Pappas, “Private weighted sum aggregation,” _IEEE Transactions on Control of Network Systems_ , vol. 9, no. 1, pp. 219–230, 2022.
  * [39] I. Damgård, M. Geisler, and M. Krøigaard, “Efficient and secure comparison for on-line auctions,” in _Information Security and Privacy: 12th Australasian Conference, ACISP 2007, Townsville, Australia, July 2-4, 2007\. Proceedings 12_. Springer, 2007, pp. 416–430.
  * [40] Kaggle, “Credit card fraud detection dataset,” https://www.kaggle.com/datasets/mlg-ulb/creditcardfraud, 2018, accessed: 2023-08-03.
  * [41] B. Balle, G. Barthe, M. Gaboardi, J. Hsu, and T. Sato, “Hypothesis testing interpretations and renyi differential privacy,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 2496–2506.
  * [42] F. D. McSherry, “Privacy integrated queries: an extensible platform for privacy-preserving data analysis,” in _Proceedings of the 2009 ACM SIGMOD International Conference on Management of data_ , 2009, pp. 19–30.
  * [43] I. Mironov, K. Talwar, and L. Zhang, “R$\backslash$’enyi differential privacy of the sampled gaussian mechanism,” _arXiv preprint arXiv:1908.10530_ , 2019\.
  * [44] K. Chaudhuri, J. Imola, and A. Machanavajjhala, _Capacity Bounded Differential Privacy_. Red Hook, NY, USA: Curran Associates Inc., 2019.
  * [45] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 1999, pp. 223–238.
  * [46] Z. Yang, S. Hu, and K. Chen, “Fpga-based hardware accelerator of homomorphic encryption for efficient federated learning,” _arXiv preprint arXiv:2007.10560_ , 2020.
  * [47] F. Mo, H. Haddadi, K. Katevas, E. Marin, D. Perino, and N. Kourtellis, “Ppfl: privacy-preserving federated learning with trusted execution environments,” in _Proceedings of the 19th annual international conference on mobile systems, applications, and services_ , 2021, pp. 94–108.
  * [48] F. Kato, Y. Cao, and M. Yoshikawa, “Olive: Oblivious federated learning on trusted execution environment against the risk of sparsification,” _Proc. VLDB Endow._ , vol. 16, no. 10, p. 2404–2417, aug 2023. [Online]. Available: https://doi.org/10.14778/3603581.3603583
  * [49] S. Reddi, Z. B. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečný, S. Kumar, and B. McMahan, Eds., _Adaptive Federated Optimization_ , 2021. [Online]. Available: https://openreview.net/forum?id=LkFG3lB13U5

###  -A Omitted Statements

####  -A1 Definitions

######  Definition 4 (Sensitivity).

The sensitivity of a function $f$ for any two neighboring inputs
$D,D^{\prime}\in\mathcal{D}$ is:

$\Delta_{f}=\sup_{D,D^{\prime}\in\mathcal{D}}\|f(D)-f(D^{\prime})\|.$

where $\lVert\cdot\rVert$ is a norm function defined in $f$’s output domain.

We consider $\ell 2$-norm ($\lVert\cdot\rVert_{2}$) as $\ell 2$-sensitivity
for following analysis due to adding a Gaussian noise.

We use Rényi DP (RDP) [24] because of the tightness of the analysis of the
privacy composition. The following definitions are original definitions for
record-level neighboring database, but are the same for user-level neighboring
database.

######  Definition 5 ($(\alpha,\rho)$-RDP [24]).

Given a real number $\alpha\in(1,\infty)$ and privacy parameter $\rho\geq 0$,
a randomized mechanism $\mathcal{M}$ satisfies $(\alpha,\rho)$-RDP if for any
two neighboring datasets $D,D^{\prime}\in\mathcal{D}$ s.t. $D^{\prime}$
differs from $D$ in at most one client’s record set, we have that
$D_{\alpha}(\mathcal{M}(D)||\mathcal{M}(D^{\prime}))\leq\rho$ where
$D_{\alpha}(\mathcal{M}(D)||\mathcal{M}(D^{\prime}))$ is the Rényi divergence
between $\mathcal{M}(D)$ and $\mathcal{M}(D^{\prime})$ and is given by

$D_{\alpha}(\mathcal{M}(D)||\mathcal{M}(D^{\prime})):=\cfrac{1}{\alpha-1}\log{\mathbb{E}\left[\left(\cfrac{\mathcal{M}(D)}{\mathcal{M}(D^{\prime})}\right)^{\alpha}\right]}\leq\rho,$

where the expectation is taken over the output of $\mathcal{M}(D)$.

####  -A2 Lemmas

######  Lemma 1 (Group privacy conversion (record-level DP to GDP) [23]).

If $f$ is $(\epsilon,\delta)$-DP, for any two input databases
$D,D^{\prime}\in\mathcal{D}$ s.t. $D^{\prime}$ differs from $D$ in at most $k$
records and any subset of outputs $Z\subseteq\mathcal{Z}$, it holds that

$\Pr[f(D)\in Z]\leq\exp(k\epsilon)\Pr[f(D^{\prime})\in
Z]+ke^{(k-1)\epsilon}\delta.$

It means when $f$ is $(\epsilon,\delta)$-DP, $f$ satisfies
$(k,k\epsilon,k\exp^{(k-1)\epsilon}\delta)$-GDP.

######  Lemma 2 (RDP composition [24]).

If $\mathcal{M}_{1}$ satisfies $(\alpha,\rho_{1})$-RDP and $\mathcal{M}_{2}$
satisfies $(\alpha,\rho_{2})$, then their composition
$\mathcal{M}_{1}\circ\mathcal{M}_{2}$ satisfies
$(\alpha,\rho_{1}+\rho_{2})$-RDP.

######  Lemma 3 (RDP to DP conversion [41]).

If $\mathcal{M}$ satisfies $(\alpha,\rho)$-RDP, then it also satisfies
$(\rho+\log{((\alpha-1)/\alpha)}-(\log{\delta}+\log{\alpha})/(\alpha-1),\delta)$-DP
for any $0<\delta<1$.

######  Lemma 4 (RDP Gaussian mechanism [24]).

If $f:D\rightarrow\mathbb{R}^{d}$ has $\ell 2$-sensitivity $\Delta_{f}$, then
the Gaussian mechanism
$G_{f}(\cdot):=f(\cdot)+\mathcal{N}(0,I\sigma^{2}\Delta_{f}^{2})$ is
$(\alpha,\alpha/2\sigma^{2})$-RDP for any $\alpha>1$.

######  Lemma 5 (Group-privacy of RDP (record-level DP to GDP) [24]).

If $f:D\rightarrow\mathbb{R}^{d}$ is $(\alpha,\rho)$-RDP,
$g:D^{\prime}\rightarrow D$ is $k$-stable and $\alpha\geq 2^{k+1}$, then
$f\circ g$ is $(\alpha/2^{k},3^{k}\rho)$-RDP.

Here, group-privacy property is defined using a notion of $k$-stable
transformation [42]. $g:D^{\prime}\rightarrow D$ is $k$-stable if $g(A)$ and
$g(B)$ are neighboring in $D$ implies that there exists a sequence of length
$c+1$ so that $D_{0}=A,...,D_{c}=B$ and all $(D_{i},D_{i+1})$ are neighboring
in $D^{\prime}$. This privacy notion corresponds to $(k,\cdot,\cdot)$-GDP in
Definition 2.

####  -A3 Assumptions

Each of these is a standard assumption in non-convex optimization. In
particular, the second assumption, $\sigma_{g}$, quantifies the heterogeneity
of non-i.i.d. between silos in FL and is used in many previous studies.
$\sigma_{g}=0$ corresponds to the i.i.d. setting. For each $s\in S$ and $u\in
U$, we assume access to an unbiased stochastic gradient $g^{s,u}_{t,q}$ of the
true local gradient $\nabla f_{s,u}(x)$ for $s$ and $u$.

######  Assumption 1 (Lipschitz Gradient).

The function $f_{s,u}$ is L-smooth for all silo $s\in S$ and user $u\in U$,
i.e., $\lVert\nabla f_{s,u}(x)-\nabla f_{s,u}(y)\rVert\leq L\lVert x-y\rVert$,
for all $x,y\in\mathbb{R}^{d}$.

######  Assumption 2 (Bounded Local and Global Variance).

The function $f_{s,u}$ is $\sigma_{l}$-locally-bounded, i.e., the variance of
each local gradient estimator is bounded as $\mathbb{E}[\lVert
g^{s,u}_{t,q}-\nabla f_{s,u}(x^{s,u}_{t,q})\rVert^{2}]\leq\sigma_{l}^{2}$ for
all $s$, $u$ and $t,q$. And the functions are $\sigma_{g}$-globally-bounded,
i.e., the global gradient variance is bounded as $\lVert\nabla
f_{s,u}(x_{t})-f(x_{t})\rVert^{2}\leq\sigma_{g}^{2}$ for all $s,u,t$.

######  Assumption 3 (Globally Bounded Gradients).

For all $s,u,t,q$, gradient is $G$-bounded, i.e., $\lVert
g^{s,u}_{t,q}\rVert\leq G$.

####  -A4 Algorithms

Algorithm 3 provides a detailed description of ULDP-NAIVE, Algorithm 4 shows
ULDP-SGD. The details of the algorithm of ULDP-AVG with user-level sub-
sampling is shown in Algorithm 5. The difference from ULDP-AVG highlights in
red letters. Algorithm 6 shows Encode and Decode that are used in the private
weighting protocol described in Protocol -B. These are used for conversions
from floating-point values to fixed-point values to be handled on a finite
finite field, and vice versa.

Algorithm 3 ULDP-NAIVE

1:$S$: silo set (silo $s\in S$), $\eta_{l}$: local learning rate, $\eta_{g}$:
global learning rate, $\sigma$: noise parameter, $C$: clipping bound, $T$:
total round, $Q$: #local epochs

2:procedure Server

3: Initialize model $x_{0}$

4: for each round $t=0,1,\ldots,T-1$ do

5: for each silo $s\in S$ do

6: $\Delta^{s}_{t}\leftarrow$ Client$(x_{t},C,\sigma,\eta_{l})$

7: $x_{t+1}\leftarrow x_{t}+\eta_{g}\frac{1}{|S|}\sum_{s\in
S}{\Delta^{s}_{t}}$

8:procedure Client($x_{t},C,\sigma,\eta_{l}$)

9: $x_{s}\leftarrow x_{t}$

10: for epoch $q=0,1,\ldots,Q-1$ do

11: Compute stochastic gradients $g^{(s)}_{t,q}$

12:$\triangleright$ $\mathbb{E}[g^{(s)}_{t,q}]=\nabla f_{s}(x_{s})$

13: $x_{s}\leftarrow x_{s}-\eta_{l}g^{(s)}_{t,q}$

14: $\Delta_{t}\leftarrow x_{t}-x_{s}$

15:
$\tilde{\Delta}_{t}\leftarrow\Delta_{t}\cdot\min{\left(1,\frac{C}{\lVert\Delta_{t}\rVert_{2}}\right)}$
$\triangleright$ clipping with $C$

16:
$\Delta^{\prime}_{t}\leftarrow\tilde{\Delta}_{t}+\mathcal{N}(0,I\sigma^{2}C^{2}|S|)$

17: return $\Delta^{\prime}_{t}$

Algorithm 4 ULDP-SGD

1:$U$: user set (user $u\in U$), $S$: silo set (silo $s\in S$), $\eta_{g}$:
global learning rate, $\sigma$: noise parameter, $C$: clipping bound, $T$:
total round, $\mathbf{W}=(\mathbf{w}_{1},...,\mathbf{w}_{|S|})$: matrix with
weight for user $u$ and silo $s$, and $\forall u\in U$,
$w_{s,u}\in\mathbf{w}_{s}$ and $\sum_{s\in S}{w^{(u)}_{s}}=1$

2:procedure Server

3: Initialize model $x_{0}$

4: for each round $t=0,1,\ldots,T-1$ do

5: for each silo $s\in S$ do

6: $g^{s}_{t}\leftarrow$ Client$(x_{t},\mathbf{w}_{s},C,\sigma)$

7: $x_{t+1}\leftarrow x_{t}-\eta_{g}\frac{1}{|U||S|}\sum_{s\in S}{g^{s}_{t}}$

8:procedure Client($x_{t},\mathbf{w}_{s},C,\sigma$)

9: for user $u\in U$ do $\triangleright$ per-user training

10: Compute stochastic gradients $g^{s,u}_{t}$

11:$\triangleright$ $\mathbb{E}[g^{s,u}_{t}]=\nabla f_{s,u}(x_{s})$

12: $\tilde{g}^{s,u}_{t}\leftarrow w_{s,u}\cdot
g^{s,u}_{t}\cdot\min{\left(1,\frac{C}{\lVert g^{s,u}_{t}\rVert_{2}}\right)}$

13: $g^{s}_{t}\leftarrow\sum_{u\in
U}{\tilde{g}^{s,u}_{t}}+\mathcal{N}(0,I\sigma^{2}C^{2}/|S|)$

14: return $g^{s}_{t}$

Algorithm 5 ULDP-AVG with user-level sub-sampling

1:$U$: user set (user $u\in U$), $S$: silo set (silo $s\in S$), $\eta_{l}$:
local learning rate, $\eta_{g}$: global learning rate, $\sigma$: noise
parameter, $C$: clipping bound, $T$: total round, $Q$: #local epochs,
$\mathbf{W}=(\mathbf{w}_{1},...,\mathbf{w}_{|S|})$: matrix with weight for
user $u$ and silo $s$, and $\forall u\in U$, $w_{s,u}\in\mathbf{w}_{s}$ and
$\sum_{s\in S}{w_{s,u}}=1$, $q$: user-level sub-sampling probability

2:procedure Server

3: Initialize model $x_{0}$

4: for each round $t=0,1,\ldots,T-1$ do

5: $U_{t}\leftarrow$ Poisson sampling from $U$ with probability $q$

6: for each silo $u\in U_{t}$ do

7: for each silo $s\in S$ do

8: $w_{s,u}\leftarrow 0$

9: for each silo $s\in S$ do

10: $\Delta^{s}_{t}\leftarrow$
Client$(x_{t},\mathbf{w}_{s},C,\sigma,\eta_{l})$

11: $x_{t+1}\leftarrow
x_{t}+\eta_{g}\frac{1}{{\color[rgb]{1,0,0}q}|U||S|}\sum_{s\in
S}{\Delta^{s}_{t}}$

12:procedure Client($x_{t},\mathbf{w}_{s},C,\sigma,\eta_{l}$)

13: for user $u\in U$ do $\triangleright$ per-user training

14: $x^{s,u}_{t}\leftarrow x_{t}$

15: for epoch $q=0,1,\ldots,Q-1$ do

16: Compute stochastic gradients $g^{s,u}_{t,q}$

17:$\triangleright$ $\mathbb{E}[g^{s,u}_{t,q}]=\nabla f_{s,u}(x^{s,u}_{t})$

18: $x^{s,u}_{t}\leftarrow x^{s,u}_{t}-\eta_{l}g^{s,u}_{t,q}$

19: $\Delta^{s,u}_{t}\leftarrow x^{s,u}_{t}-x_{t}$

20: $\tilde{\Delta}^{s,u}_{t}\leftarrow
w_{s,u}\cdot\Delta^{s,u}_{t}\cdot\min{\left(1,\frac{C}{\lVert\Delta^{s,u}_{t}\rVert_{2}}\right)}$
$\triangleright$ per-user weighted clipping

21: $\Delta^{s}_{t}\leftarrow\sum_{u\in
U}{\tilde{\Delta}^{s,u}_{t}}+\mathcal{N}(0,I\sigma^{2}C^{2}/|S|)$

22: return $\Delta^{s}_{t}$

Algorithm 6 Encode and Decode functions in the private weighting protocol

1:procedure Encode($x,P,n$) $\triangleright$ e.g., $P=10^{-10}$

2: /* to turn floating point into fixed point */

3: $x\leftarrow x/P$ $\triangleright$ compute as floating point

4: $x\leftarrow x$ as integer

5: /* to map integer $\mathbb{Z}$ into finite field $\mathbb{F}_{n}$*/

6: $x\leftarrow x\,(\mathrm{mod}\,n)$

7: return $x$

8:procedure Decode($x,P,C_{\text{LCM}},n$)

9: /* to map finite field $\mathbb{F}_{n}$ number into integer $\mathbb{Z}$ */

10: if $x>n//2$ then $\triangleright$ $//$ means integer division

11: $x\leftarrow x-n$

12: else

13: $x\leftarrow x$

14: /* to remove $C_{\text{LCM}}$ factor*/

15: $x\leftarrow x/C_{\text{LCM}}$ $\triangleright$ compute as floating point

16: /* to recover original magnitude */

17: $x\leftarrow xP$

18: return $x$

####  -A5 Proofs

Proof of Theorem 1

###### Proof.

At the round $t$, due to the clipping operation (Line 14 in Algorithm 3), for
each $s\in S$ any user’s contribution to $\Delta^{s}_{t}$ (Line 6) is limited
to at most $C$ (regardless of the number of user records). And since a single
user may exist in any silo, he/she contributes at most $|S|C$ to $\sum_{s\in
S}{\Delta^{s}_{t}}$, which means user-level sensitivity is $|S|C$. Therefore,
when the each silo adds the Gaussian noise with variance $\sigma^{2}C^{2}|S|$,
$\sum_{s\in S}{\Delta^{s}_{t}}$ includes the Gaussian noise with variance
$\sigma^{2}C^{2}|S|^{2}$. Then, by Lemma 4, it satisfies
$(\alpha,\frac{\alpha}{2\sigma^{2}})$-RDP for $\alpha>1$. And after $T$
rounds, it satisfies $(\alpha,\frac{T\alpha}{2\sigma^{2}})$-RDP by Lemma 2.
Finally, by Lemma 3, we get the final result. ∎

Proof of Theorem 2

###### Proof.

In each silo $s\in S$, by DP-SGD with $Q$ epochs and $T$ rounds, we have
record-level $(\alpha,\rho_{s}=\rho(\sigma,\gamma,QT))$-RDP. The actual value
of $\rho_{s}$ is calculated numerically as described in [43]. RDP is known to
satisfy parallel composition [44]. That is, for disjoint database $D_{1}$ and
$D_{2}$, their combined release
$(\mathcal{M}_{1}(D_{1}),\mathcal{M}_{2}(D_{2}))$ such that $\mathcal{M}_{1}$
with $(\alpha,\rho_{1})$-RDP and $\mathcal{M}_{2}$ with
$(\alpha,\rho_{2})$-RDP satisfies
$(\alpha,\mathrm{max}\\{\rho_{1},\rho_{2}\\})$-RDP. For any silo $s\in S$,
input database $D_{s}$ is disjoint with others. Therefore, after $T$ rounds,
the trained model satisfies $(\alpha,\rho=\max_{s\in S}\rho_{s})$-RDP for
across silo entire database $D=D_{1}\oplus...\oplus D_{|S|}$. Then, by Lemma 5
and Lemma 3, for any integer $k$ to the power of 2 and any $\alpha\geq
2^{k+1}$, it also satisfies
$(k,3^{k}\rho+\log{((\frac{\alpha}{2^{k}}-1)/\frac{\alpha}{2^{k}})}-(\log{\delta}+\log{\frac{\alpha}{2^{k}}})/(\frac{\alpha}{2^{k}}-1),\delta)$-GDP.
Finally, by filtering with $\mathbf{B}$, we guarantee that any user has at
most $k$ records in $D$. Finally, we get the final result by Proposition 1.
(Another method to compute $\epsilon$ is to use Lemma 1 instead of Lemma 5.) ∎

Proof of Theorem 3

###### Proof.

For any round $t$, due to the clipping operation (Line 15), for each $s\in S$
any user’s contribution to $\Delta^{s}_{t}$ (Line 6) is limited to at most
$w_{s,u}C$ (regardless of the number of user records). Therefore, for
$\sum_{s\in S}{\Delta^{s}_{t}}$ (Line 6), any user’s contribution is at most
$\sum_{s\in S}w_{s,u}C=C$ since $\sum_{s\in S}{w_{s,u}}=1$. That means the
user-level sensitivity is just $C$. And since the each silo adds the Gaussian
noise with variance $\sigma^{2}C^{2}/|S|$, $\sum_{s\in S}{\Delta^{s}_{t}}$
includes Gaussian noise with variance $\sigma^{2}C^{2}$. Then, by Lemma 4, it
satisfies $(\alpha,\frac{\alpha}{2\sigma^{2}})$-RDP for $\alpha>1$ in a user-
level manner. And after $T$ rounds, it satisfies
$(\alpha,\frac{T\alpha}{2\sigma^{2}})$-RDP by Lemma 2. Finally, by Lemma 3, we
get the result. ∎

###  -B Details of private weighting protocol

Protocol 1 Private Weighting Protocol
---
Inputs: Silo $s\in S$ that holds an dataset with $n_{s,u}$ records for each
user $u\in U$. $\mathcal{A}$ is central aggregation server. $N_{\text{max}}$
is upper bound on the number of records per user, e.g., 2000. $P$ is precision
parameter, e.g, $10^{-10}$. $\lambda$ is security parameter, e.g., $3072$-bit
security. 1. Setup. (a) $\mathcal{A}$ generates Paillier keypairs ($PK$, $SK$)
with the given security parameter $\lambda$ and sends the public key $PK$ to
all silos. All $s$ generate DH keypairs ($pk_{s}$, $sk_{s}$) with the same
parameter $\lambda$ and transmit their respective public key $pk_{s}$ to
$\mathcal{A}$. Both $\mathcal{A}$ and all silos compute $C_{\text{LCM}}$ which
is the least common multiple of all integers up to $N_{\text{max}}$. The
modulus $n$ included in $PK$ is used for finite field $\mathbb{F}_{n}$ by
$\mathcal{A}$ and all silos. (b) After receiving all $pk_{s}$, $\mathcal{A}$
broadcasts all DH public keys $pk_{s}$ to all $s$. All $s$ compute shared keys
$sk_{s,s^{\prime}}$ from $sk_{s}$ and received public keys $pk_{s^{\prime}}$
for all $s^{\prime}\in S$. (c) Silo $0$ ($\in S$) generates a random seed $R$
and encrypts $R$ using $sk_{0,s^{\prime}}$ to obtain $Enc(R)$ and sends
$Enc(R)$ to $s^{\prime}$ via $\mathcal{A}$ for all $s^{\prime}$. All $s\in
S\setminus 0$ receive and decrypt $Enc(R)$ with $sk_{s,0}$ and get $R$ as a
shared random seed. (d) All $s$ generate multiplicative blind masks
$r_{u}\in\mathbb{F}_{n}$ with the same $R$ and compute blinded histogram as
$B(n_{s,u})\equiv r_{u}n_{s,u}\,(\mathrm{mod}\,n)$ for all $u\in U$. (e) All
$s$ generate pair-wise additive masks $r^{u}_{s,s^{\prime}}\in\mathbb{F}_{n}$
employing $sk_{s,s^{\prime}}$ for all $s^{\prime}$ and $u$, with
$r^{u}_{s,s^{\prime}}=r^{u}_{s^{\prime},s}$. Subsequently, they calculate the
doubly blinded histogram as $B^{\prime}(n_{s,u})\equiv
B(n_{s,u})+\sum_{s<s^{\prime}}{r^{u}_{s,s^{\prime}}}-\sum_{s>s^{\prime}}{r^{u}_{s,s^{\prime}}}\,(\mathrm{mod}\,n)$.
All $s$ send $B^{\prime}(n_{s,u})$ to $\mathcal{A}$. $\mathcal{A}$ aggregates
these contributions to compute $B(N_{u})\equiv\sum_{s\in
S}{B^{\prime}(n_{s,u})}\,(\mathrm{mod}\,n)$ for each $u$, denoting
$N_{u}=\sum_{s\in S}{n_{s,u}}$. (f) $\mathcal{A}$ computes the inverse of
$B(N_{u})$ as $B_{\text{inv}}(N_{u})=B(N_{u})^{-1}$ for each $u$. This is the
multiplicative inverse on $\mathbb{F}_{n}$, which is efficiently computed by
the Extended Euclidean algorithm. 2. Weighting for each training round $t$.
(a) $\mathcal{A}$ encrypts $B_{\text{inv}}(N_{u})$ using Paillier’s public key
$PK$, resulting in $Enc_{\text{p}}(B_{\text{inv}}(N_{u}))$ for all $u$. If
user-level sub-sampling is required, the server performs Poisson sampling with
a given probability $q$ for each user before the encryption. For non-selected
users, $B_{\text{inv}}(N_{u})$ is set to 0. If we require user-level sub-
sampling, we perform Poisson sampling with given probability $q$ on the server
for each user before the Paillier’s encryption and set
$B_{\text{inv}}(N_{u})=0$ for all users not selected. Subsequently,
$\mathcal{A}$ broadcasts all $Enc_{\text{p}}(B_{\text{inv}}(N_{u}))$ to all
silos. (b) In each $s$, following the approach of ULDP-AVG, the clipped model
delta $\tilde{\Delta}^{s,u}_{t}$ is computed for each user $u$. The weighted
clipped model delta is then calculated as $\displaystyle
Enc_{\text{p}}(\tilde{\Delta}^{s,u}_{t})$ $\displaystyle=$ Encode
$\displaystyle(\tilde{\Delta}^{s,u}_{t},P,n)n_{s,u}r_{u}C_{\text{LCM}}Enc_{\text{p}}(B_{\text{inv}}(N_{u})).$
Let the Gaussian noise be $z^{s}_{t}$, we then compute
$z^{\prime}_{s}=\textsc{Encode}(z^{s}_{t},P,n)C_{\text{LCM}}$. Note that we
need to approximate real number $\tilde{\Delta}^{s,u}_{t}$ and $z^{s}_{t}$ on
a finite field using Encode (described in Algorithm 6). Lastly, we compute the
summation $Enc_{\text{p}}(\Delta^{s}_{t})=\sum_{u\in
U}{Enc_{\text{p}}(\tilde{\Delta}^{s,u}_{t})}+z^{\prime}_{s}$. (c) In each $s$,
random pair-wise additive masks are generated, and secure aggregation is
performed on $Enc_{\text{p}}(\Delta^{s}_{t})$ mirroring the steps in 1.(f).
Then, $\mathcal{A}$ gets $\sum_{s\in S}{Enc_{\text{p}}(\Delta^{s}_{t})}$.
$\mathcal{A}$ decrypts it with Paillier’s secret key $SK$ and decodes it by
Decode$(\sum_{s\in S}{\Delta^{s}_{t}},P,C_{\text{LCM}},n)$ and recovers the
aggregated value. (d) Steps 2.(a) through 2.(c) are repeated for each training
round.

The details of the private weighting protocol are explained in Protocol -B.
Our protocol consists of a setup phase, which is executed only once during the
entire training process, and a weighting phase, which is executed in each
round of training. In the setup phase, as depicted in (a-c) of Protocol -B,
the server generates a keypair for Paillier encryption, while the silos
establish shared random seeds through a Diffie–Hellman (DH) key exchange via
the server. Subsequently, (d-f) the blinded inverses of the user histogram are
computed. In the weighting phase, (a) the server prepares the encrypted
weights, (b) the silos compute user-level weighted model deltas in the
encrypted world, and (c) the server recovers the aggregated value. It’s
important to note that in the Paillier cryptosystem, the plaintext data $x$
exists within the additive group modulo $n$, while encrypted data (denoted as
$Enc_{\text{p}}(x)$) belongs to the multiplicative group modulo $n^{2}$ with
an order of $n$. The system allows for operations such as addition of
ciphertexts and scalar multiplication and addition of ciphertexts.

We provide a theoretical analysis of this private weighting protocol in terms
of correctness and privacy as outlined below.

####  -B1 Correctness

The protocol must compute the correct result as the same result as non-secure
method. To this end, we consider the correctness of the aggregated data
obtained in each round. Let $\sum_{s\in S}\Delta^{s}_{t}$ with non-secure
method be $\Delta$ and the one with the Protocol -B be $\Delta_{\text{sec}}$,
our goal is formally stated as
$\Pr[|\Delta-\Delta_{\text{sec}}|_{\infty}>P]<negl$, where $P$ is a precision
parameter and $negl$ signifies a negligible value.

Initially, with regards to secure aggregation, the additive pair-wise masks
cancel out as shown in [26]. For the difference, silo must participate in any
rounds in our cross-silo FL. When collecting the histogram, additive masks are
canceled out as follows:

$\displaystyle B(N_{u})$ $\displaystyle=\sum_{s\in S}{B(n_{s,u})}$
$\displaystyle\quad+\sum_{s<s^{\prime}}{\underbrace{(r^{u}_{s,s^{\prime}}-r^{u}_{s^{\prime},s})}_{\text{canceled
out}}}-\sum_{s>s^{\prime}}{\underbrace{(r^{u}_{s,s^{\prime}}-r^{u}_{s^{\prime},s})}_{\text{canceled
out}}}$

The same applies to secure aggregation for model delta. Note that the mask is
not directly added to the ciphertext (within the multiplication group of
$n^{2}$); instead scalar addition within $\mathbb{F}_{n}$ that takes advantage
of homomorphic property of Paillier cryptosystem is utilized. As secure
aggregation doesn’t result in any degradation of the aggregation outcome when
all terms are within $\mathbb{F}_{n}$, our focus shifts to other components.
Note hat there are errors due to the handling of fixed-point numbers on a
finite field.

From the protocol description, $Enc_{\text{p}}(\Delta_{\text{sec}})$ is
analyzed as follows:

$\displaystyle Enc_{\text{p}}(\Delta_{\text{sec}})=\sum_{s\in
S}{Enc_{\text{p}}(\Delta^{s}_{t})}=\sum_{s\in S}{\sum_{u\in
U}{Enc_{\text{p}}(\tilde{\Delta}^{s,u}_{t})}+z^{\prime}_{s}}$
$\displaystyle=\sum_{s\in S}{\sum_{u\in
U}E^{s,u}_{t}n_{s,u}r_{u}C_{\text{LCM}}Enc_{\text{p}}(B_{\text{inv}}(N_{u}))+Z^{s}_{t}C_{\text{LCM}}}$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{=}}Enc_{\text{p}}(\sum_{s\in
S}{(\sum_{u\in
U}{(E^{s,u}_{t}n_{s,u}r_{u}C_{\text{LCM}}B_{\text{inv}}(N_{u}))})+Z^{s}_{t}C_{\text{LCM}}})$
$\displaystyle=Enc_{\text{p}}(\sum_{s\in S}{(\sum_{u\in
U}{(E^{s,u}_{t}n_{s,u}r_{u}C_{\text{LCM}}(r_{u}N_{u})^{-1}})+Z^{s}_{t}C_{\text{LCM}}}))$
$\displaystyle\stackrel{{\scriptstyle(2)}}{{=}}Enc_{\text{p}}(\sum_{s\in
S}{(\sum_{u\in U}{(E^{s,u}_{t}n_{s,u}C_{-N_{u}}})+Z^{s}_{t}C_{\text{LCM}}}))$

where $C_{-N_{u}}$ is the result of modular multiplication between
$C_{\text{LCM}}$ and the modular multiplicative inverse of $N_{u}$,
$E^{s,u}_{t}=\textsc{Encode}(\tilde{\Delta}^{s,u}_{t},P,n)$ and
$Z^{s}_{t}=\textsc{Encode}(z^{s}_{t},P,n)$. Equation (1) is because all of
$B_{\text{inv}}$, $E^{s,u}_{t}$, $n_{s,u}$, $r_{u}$ and $C_{\text{LCM}}$
$\in\mathbb{F}_{n}$. At (2), the modulo inverse of $r_{u}$ is canceled out
because $r_{u}\in\mathbb{F}_{n}$ and $r_{u}$ almost always has modulo inverse.
However, this does not hold when $r_{u}$ and $n$ are not coprime. Let $p$ and
$q$ be two large primes used in the Paillier cryptosystem, such that $n=pq$,
then the probability of a random $r_{u}\in\mathbb{F}_{n}$ and $n$ are not
coprime is

$\frac{n-1-\phi(n)}{n-1}=\frac{n-1-(p-1)(q-1)}{n-1},$ (5)

where $\phi$ is Euler’s totient function. This probability is negligibly small
when n is sufficiently large. In the case of user-level sub-sampling,
$B_{\text{inv}}(N_{u})$ is set 0 and we see that only the model delta for user
$u$ is all zeros, which produces exactly the same result as if the unselected
users did not participate in the training round. The important condition is
that if $N_{u}\leq N_{\text{max}}$ and $N_{u}$ is a factor of
$C_{\text{LCM}}$, $C_{\text{LCM}}/N_{u}$ is always divisible on $\mathbb{Z}$
and the result is the same as on $\mathbb{F}_{n}$. Also if $\sum_{s\in
S}{(\sum_{u\in
U}{(E^{s,u}_{t}n_{s,u}C_{-N_{u}}})+Z^{s}_{t}C_{\text{LCM}}})\in\mathbb{Z}$ is
smaller than $n$, it yields the same results on $\mathbb{Z}$ and
$\mathbb{F}_{n}$. Hence, when these conditions are satisfied, decrypted value
$\Delta_{\text{sec}}\in\mathbb{F}_{n}$ obtains the same result on
$\Delta_{\text{sec}}\in\mathbb{Z}$. After decryption, we consider
$\Delta_{\text{sec}}\in\mathbb{R}$. The final result is decoded by
$\textsc{Decode}(\Delta_{\text{sec}},P,C_{\text{LCM}},n)\in\mathbb{R}$ as
follows:

$\displaystyle\textsc{Decode}(\Delta_{\text{sec}},P,C_{\text{LCM}},n)=\sum_{s\in
S}{(\sum_{u\in
U}{(\frac{n_{s,u}}{N_{u}}\tilde{\Delta}^{\prime}_{s,u,t})}+Z^{\prime}_{s,t}})$

where, from Algorithm 6, $\tilde{\Delta}^{\prime}_{s,u,t}$ is the same as the
result of computing $\tilde{\Delta}^{s,u}_{t}$ in fixed-point with precision
$P$, and $Z^{\prime}_{s,t}$ is the same as $z^{s}_{t}$.

Therefore, the correctness of these calculations is satisfied when two
conditions (1) $N_{u}\leq N_{\text{max}}$ and (2) $\sum_{s\in S}{(\sum_{u\in
U}{(E^{s,u}_{t}n_{s,u}C_{-N_{u}}})+Z^{s}_{t}C_{\text{LCM}}})<n$, are
satisfied. To satisfy (1), $N_{\text{max}}$ must be sufficiently large, and a
larger $N_{\text{max}}$ leads to a larger $C_{\text{LCM}}$. Hence, when we
take $n$ is large, these conditions can be satisfied unless the parameters or
noise take on unrealistic values.

For example, suppose the range of the noise and aggregated model parameters is
$[-10^{10},10^{10}]$, $P=10^{-10}$, $N_{\text{max}}=2000$ and $\lambda$ is
3072-bit security, we have $n>10^{924}$ by Paillier cryptosystem,
$E^{s,u}_{t}<10^{20}$ , $Z^{s}_{t}<10^{20}$ and $C_{\text{LCM}}<10^{867}$.
Then, $\sum_{s\in S}{(\sum_{u\in
U}{(E^{s,u}_{t}n_{s,u}C_{-N_{u}}})+Z^{s}_{t}C_{\text{LCM}}})<10^{888}<n$ and
we satisfy the condition (2). $C_{\text{LCM}}$ grows exponentially with
respect to $N_{\text{max}}$. One possible solution for this is that we can
make it very small by limiting the number of records per user to several
values. For example, $\\{10^{1},10^{2},10^{3},10^{4}\\}$ then
$C_{\text{LCM}}=10^{4}$.

####  -B2 Privacy

Privacy in this protocol means that both the central server and the silos do
not get more information than is available in the original ULDP-AVG while we
perform the better weighting strategy. Our approach relies on a private
weighted sum aggregation technique employing the Paillier cryptosystem [45,
19] and secure aggregation [26]. Formal security arguments for these
methodologies are available in their respective sources. Our protocol is fully
compatible with these works because all data exchanged is handled on
$\mathbb{F}_{n}$ including random masks for secure aggregation.

A different view of the server from these basic methods is $B(N_{u})$ for all
$u$ which is multiplicatively blinded aggregated histogram. Since $B(n_{s,u})$
for $s$ and $u$ is securely hidden by secure aggregation, only $B(N_{u})$ is
the meaningful server view. $B(N_{u})$ is $r_{u}N_{u}\,(\text{mod}\,n)$ and
this is randomly distributed on $\mathbb{F}_{n}$ if $r_{u}$ is uniformly
distributed on $\mathbb{F}_{n}$. Also, the inverse of $B_{\text{inv}}(N_{u})$
is uniformly distributed as well. This is because the multiplication operation
in a finite field is closed and bijective. Therefore, it is information-
theoretically indistinguishable and private. Such multiplicative blinding has
been also used in [39]. The view of the silos is the same as that of [19] even
though the contents of the weights are sensitive, and privacy is protected by
Paillier encryption. Note that the security of the initial DH key exchange and
the security of the Paillier cryptosystem follows the security parameter
$\lambda$, which is the protocol input.

###  -C Omitted Figures

We illustrate an intuitive difference between ULDP-NAIVE and ULDP-AVG in
Figure 7. In ULDP-NAIVE, every single user can contribute to all model deltas.
On the other hand, in ULDP-AVG, one user’s contribution is limited to a small
portion, i.e., $1/|U|$ of the whole model delta. This reduces sensitivity.
When $|U|$ is large, which often happens in cross-silo FL, it can be a
particular advantage.

Figure 7: An intuitive illustration of the difference between ULDP-NAIVE and
ULDP-AVG. In ULDP-NAIVE, every single user can contribute to all model deltas.
On the other hand, in ULDP-AVG, one user’s contribution is limited to a small
portion, i.e., $1/|U|$ of the whole model delta. This reduces sensitivity.
When $|U|$ is large, which often happens in cross-silo FL, it can be a
particular advantage.

###  -D Omitted Experiments and details

For ease of access, all of our experimental code and datasets are available at
the open repository: https://github.com/FumiyukiKato/uldp-fl.

####  -D1 GDP comparison: RDP vs Normal DP

For the experiment in Figure 2, we ran the Gaussian mechanism with
$\sigma=5.0$ and sampling rate$=0.01$ for $10^{5}$ iterations, which emulates
a typical DP-SGD execution setup. We use fixed $\delta=10^{-5}$ and varies
group size $k=1,2,4,8,16,32,64$.

To compute GDP, RDP for sub-sampled Gaussian mechanism was calculated
according to [35]. Then, for group-privacy of RDP, we compute GDP by Lemma 5.

For normal DP, the computed RDP is converted to normal DP by Lemma 3, and then
converted to GDP by Lemma 1. When converting to normal DP to GDP, computing
final $\epsilon$ at fixed $\delta$ is not easy. In Lemma 3, output $\epsilon$
(denoting $\epsilon_{\ref{lemma:rdp_conversion}}$) depends on input $\delta$
(denoting $\delta_{\ref{lemma:rdp_conversion}}$), and the final $\delta$
(denoting $\delta_{\ref{lemma:normaldp_group_privacy}}$) output by Lemma 1
depends on the $\epsilon_{\ref{lemma:rdp_conversion}}$ and
$\delta_{\ref{lemma:rdp_conversion}}$. Therefore, we repeatedly select
$\delta_{\ref{lemma:rdp_conversion}}$ in a binary search manner, and compute
$\epsilon_{\ref{lemma:rdp_conversion}}$ and
$\delta_{\ref{lemma:rdp_conversion}}$, and finally report the $\epsilon$ when
difference of $\delta_{\ref{lemma:rdp_conversion}}$ and $\delta=10^{-5}$ are
sufficiently small (accuracy by $10^{-8}$) as the $\epsilon$ of GDP. The
implementation is a function get_normal_group_privacy_spent() in
https://github.com/FumiyukiKato/uldp-fl/blob/main/src/noise_utils.py.

Note that there is no guarantee that this method will achieve optimal
$\epsilon$ with given $\delta$ but find reasonable $\epsilon$.

####  -D2 Record allocation

(a) MNIST and Creditcard.

(b) HeartDisease and TcgaBrca.

Figure 8: Record distribution across users and silos.

(a) uniform.

(b) zipf.

Figure 9: Example of record allocation on Creditcard.

MNIST and Creditcard. We designed two different record distribution patterns,
uniform and zipf, to model how user records are scattered across silos in the
MNIST and Creditcard datasets. Both distributions take the number of users
$|U|$ and the number of silos $|S|$. It associates each record with a user and
a silo.

(1) In uniform, every record is assigned to a user with equal probability, and
likewise, each record is assigned to a silo with equal probability. (2) zipf
combines two types of Zipf distributions as shown in Figure 8(a). First, the
distribution of the number of records per user follows a a Zipf distribution.
Then, for each user, the numbers of records are assigned to different silos
based on an another Zipf distribution. Each of the two Zipf distributions
takes a parameter $\alpha$ that determines the concentration of the numbers.
In our experiments, we used $\alpha=0.5$ for the first distribution and
$\alpha=2.0$ for the second distribution. This choice is rooted in the
observation that the concentration of user records is not as high as the
concentration in the silos selected by each user.

For Creditcard and MNIST, the number of silos $|S|$ is fixed at 5. We used
100, 1000 for Creditcard as $|U|$ and 100, 10000 for MNIST. For MNIST, we can
require each user to have only 2 labels at most in the non-i.i.d. setting. For
example, when $|U|=100$ and $|S|=5$, the record distribution of Creditcard
dataset is shown in Figure 9. The number of records is plotted for each user
and color-coded for each silo.

HeartDisease and TcgaBrca. For the HeartDisease and TcgaBrca datasets, we
adopted the same two distributions uniform and zipf as above-mentioned ones.
In, the benchmark datasets HeartDisease and TcgaBrca, all records are already
allocated to silos and the number of records of each silo is fixed. Therefore,
the design of the user-record allocation is slightly different.

(1) In uniform, all records belong to one of the users with equal probability
without allocation to silos. (2) In zipf, as shown in Figure 8(b), the number
of records for a user is first generated according to a Zipf distribution, and
80% of the records are assigned to one silo, and the rest to the other silos
with equal probability. The priority of the silo is chosen randomly for each
user. $\alpha=0.5$ was used for the parameter of the Zipf. In TcgaBrca, Cox-
Loss is used for loss function [18], which needs more than two records for
calculating valid loss and we set more than two records for each silo and user
for per-user clipping of ULDP-AVG.

####  -D3 Hyperparameters

All scripts used in the experiments, including hyperparameters, can be
accessed here: https://github.com/FumiyukiKato/uldp-
fl/blob/main/exp/script/privacy_utility.sh.

(a) $n\approx 10$ ($|U|=50$), uniform.

(b) $n\approx 10$ ($|U|=50$), zipf.

(c) $n\approx 2.5$ ($|U|=200$), uniform.

(d) $n\approx 2.5$ ($|U|=200$), zipf.

Figure 11: Privacy-utility trade-offs on HeartDisease dataset. Test Accuracy
(Left), Privacy (Right).

(a) $n\approx 17$ ($|U|=50$) uniform.

(b) $n\approx 17$ ($|U|=50$), zipf.

(c) $n\approx 4$ ($|U|=200$), uniform.

(d) $n\approx 4$ ($|U|=200$), zipf.

Figure 13: Privacy-utility trade-offs on TcgaBrca dataset. Test Accuracy
(Left), Privacy (Right).

(a) $n\approx 600$ ($|U|=100$), uniform.

(b) $n\approx 600$ ($|U|=100$), zipf, iid.

(c) $n\approx 600$ ($|U|=100$), zipf, non-iid.

(d) $n\approx 6$ ($|U|=10000$), uniform, iid.

(e) $n\approx 6$ ($|U|=10000$), zipf, iid.

(f) $n\approx 6$ ($|U|=10000$), zipf, non-iid.

Figure 15: Privacy-utility trade-offs on MNIST dataset: Test Loss (Left),
Accuracy (Middle), Privacy (Right). Figure 16: Test loss of TcgaBrca: the
better weighting is effective especially in biased distribution.

Figure 17: In Creditcard, user-level sub-sampling achieves a more competitive
privacy-utility trade-off.

Figure 18: In MNIST, user-level sub-sampling achieves a more competitive
privacy-utility trade-off.

d, user-level sub-sampling might

Figure 19: The dominant execution time of training grows linearly with
parameter size and/or the number of users.

####  -D4 Additional experiments

We provide additional experimental results to support the claims made in the
paper. In addition to the three dataset mentioned in the paper, we evaluate
our method on a well-known image dataset MNIST. For MNIST, we use a CNN model
about 20K parameters, 60K training data and 10K evaluation data, and assigned
silos and users to all of the training data. The default setting of all of the
following experiments is the same as specified in the paper.

Privacy-utility trade-offs under ULDP. Figure 11, 13 and 15 shows a privacy-
utility trade-offs on HeartDisease, TcgaBrca and MNIST, respectively. All
experiments used a fixed noise parameter (noise multiplier) $\sigma=5.0$ and
$\delta=10^{-5}$, utility metrics (Accuracy for HeartDisease and MNIST,
C-index for TcgaBrca) are plotted in left side and accumulated privacy
consumption $\epsilon$ for ULDP are plotted in right side. For clarity, the
test loss is shown on the left hand side on MNIST. The average number of
records per user (denoting as $n$) in entire silos and the distribution
(uniform/zipf) changes for each figure.

In all datasets, consistently, ULDP-AVG is competitive in terms of utility,
ULDP-AVG-w shows much faster convergence, and ULDP-SGD shows slower
convergence. ULDP-NAIVE achieves low privacy bound; however, its utility is
much lower than other methods. The group-privacy methods such as ULDP-
GROUP-$k$ show reasonably high utility especially in settings where $n$ is
small. This is because the records to be removed due to the number of records
per user being over group size $k$ is small. However, the ULDP privacy bound
ULDP-GROUP-$k$ achieves ends up being very large. Note that the privacy bounds
for ULDP-GROUP-$k$ are derived from the local DP-SGD and depend on not only
the group size $k$ but also the size of the local training dataset. The
exceptions are cases where the local data set size is large and the number of
records per user is very small as Figures 15(d), 15(e) and 15(f). In these
case, ULDP-GROUP-2 achieves a reasonably small privacy bound. In other words,
if the number of user records is fixed at one or two in the scenario, and the
number of training records is large (it is advantageous for ULDP-GROUP because
the record-level sub-sampling rate in DP-SGD becomes small), it could be
better to use ULDP-GROUP.

The results for the MNIST, non-i.i.d and $|U|=100$ case highlight a weak point
of ULDP-AVG. Note that non-i.i.d here is at user-level and DEFAULT and ULDP-
GROUP are less affected by non-i.i.d because they do train per silo rather
than per user. As Figure 15(c) shows, the convergence of ULDP-AVG is worse
compared to other results. It suggests that ULDP-AVG may emphasize the bad
effects of user-level non-i.i.d. distribution that were not an issue with
normal cross-silo FL because the gradient is not computed at the user level as
in ULDP-AVG. On the other hand, this is less problematic when the number of
users is large as shown in Figure 15(f). This is due to the relatively smaller
effect of individual user over fitting caused from non-i.i.d. distribution as
the sample size (the number of users) increases.

Figure 16 shows the effect of the better weighting strategy (i.e., ULDP-AVG vs
ULDP-AVG-w) on TcgaBrca dataset. Both uniform and zipf have greatly improved
in convergence speed with the better weighting strategy. In particular, since
the better weighting is adapted to the distribution of the records, it also
shows little variance of the results.

User-level sub-sampling effect. We evaluate the effect of user-level sub-
sampling. The details of the algorithm of ULDP-AVG with user-level sub-
sampling is shown in Algorithm 5. The difference from ULDP-AVG highlights in
red letters. Figure 17 illustrates that how user-level sub-sampling affects
the privacy-utility trade-offs on Creditcard with 1000 users. We report the
test accuracy and ULDP privacy bounds for various sampling rates
$q=0.1,0.3,0.5,0.7,1.0$. Basically, tight privacy bound is obtained at the
expense of utility. As the result shows, the degradation of utility due to the
sub-sampling could be acceptable to some extent (e.g., $q=0.7$) and there
could be an optimal point for each setting. Figure 18 illustrates that how
user-level sub-sampling affects the privacy-utility trade-offs on MNIST with
10000 users with sampling rates $q=0.1,0.3,0.5,1.0$. The result shows that
while privacy is greatly improved, there is less degradation in utility. This
is due to the fact that there are a sufficient number of users i.e., 10000. In
the case of larger users, the effect of sub-sampling is even greater and is
likely to become an important technique.

Overhead of private weighting protocol.

Figure 19 describes the execution times of the proposed private weighting
protocol (Protocal -B) with artificial dataset with 10000 samples and model
with 16 parameters, 20 users and 3 silos as default. Note that these are on a
considerably small scale. The major time-consuming parts of the protocol are
key exchange, training in each silo and aggregation on the server. The upper
figure shows the execution times on each part of the protocol with various
parameter size 16 to 107 and the bottom figure shows the various number of
users 10 to 40. The execution time of local training is averaged by silos. The
dominant part is the local training part, which is considered to be an
overhead due to the computation with the Paillier encryption, which grows
linearly with parameter size and/or the number of users. The larger parameter
size increases the aggregation time on the server as well. Our implementation
is based on the Python 3.9 library (https://github.com/data61/python-paillier)
with 3072-bit security, which itself could be made faster by software
implementation or hardware accelerators [46]. However, it can be difficult to
apply to larger models, such as DNNs, because the execution time increases
linearly on a non-negligible scale with parameter size. Therefore, extending
the proposed method to deep models with millions of parameters is a future
challenge. It may be possible to replace such software-based encryption
methods by using hardware-assisted Trusted Execution Environment, which has
recently attracted attention in the FL field [47, 48].

Proof of Theorem 4

###### Proof.

The many of techniques in the following proof are seen in [36, 37, 49].

For convenience, we define following quantities:

$\displaystyle\alpha^{s,u}_{t}$
$\displaystyle:=\cfrac{w_{s,u}C}{\max{(C,\eta_{l}\lVert\sum_{q\in[Q]}g^{s,u}_{t,q}\rVert)}},\;\tilde{\alpha}^{s,u}_{t}:=\cfrac{w_{s,u}C}{\max{(C,\eta_{l}\lVert\mathbb{E}\left[\sum_{q\in[Q]}g^{s,u}_{t,q}\right]\rVert)}},\;\bar{\alpha}_{t}:=\cfrac{1}{|S||U|}\sum_{s\in
S}\sum_{u\in U}{\tilde{\alpha}^{s,u}_{t}},$ $\displaystyle\Delta^{s,u}_{t}$
$\displaystyle:=-\eta_{l}\sum_{q\in[Q]}{g^{s,u}_{t,q}}\cdot\alpha^{s,u}_{t},\;\tilde{\Delta}^{s,u}_{t}:=-\eta_{l}\sum_{q\in[Q]}{g^{s,u}_{t,q}}\cdot\tilde{\alpha}^{s,u}_{t},\;\bar{\Delta}^{s,u}_{t}:=-\eta_{l}\sum_{q\in[Q]}{g^{s,u}_{t,q}}\cdot\bar{\alpha}_{t},$
(6) $\displaystyle\breve{\Delta}^{s,u}_{t}$
$\displaystyle:=-\eta_{l}\sum_{q\in[Q]}{\nabla
f_{s,u}(x^{s,u}_{t,q})}\cdot\bar{\alpha}_{t},\;\Delta^{s}_{t}:=\sum_{u\in
U}{\Delta^{s,u}_{t}},\;\tilde{\Delta}^{s}_{t}:=\sum_{u\in
U}{\tilde{\Delta}^{s,u}_{t}},\;\bar{\Delta}^{s}_{t}:=\sum_{u\in
U}{\bar{\Delta}^{s,u}_{t}},\;\breve{\Delta}^{s}_{t}:=\sum_{u\in
U}{\breve{\Delta}^{s,u}_{t}}.$ (7)

where expectation in $\tilde{\alpha}^{s,u}_{t}$ is taken over all possible
randomness. Due to the smoothness in Assumption 1, we have

$\displaystyle f(x_{x+1})\leq f(x_{t})+\langle\nabla
f(x_{t}),x_{t+1}-x_{t}\rangle+\frac{L}{2}\lVert x_{t+1}-x_{t}\rVert^{2}.$ (8)

The model difference between two consecutive iterations can be represented as

$\displaystyle x_{x+1}-x_{t}=\eta_{g}\frac{1}{|S||U|}\sum_{s\in
S}{(\Delta^{s}_{t}+z^{s}_{t})}$ (9)

with random noise $z^{s}_{t}\sim\mathcal{N}(0,I\sigma^{2}C^{2}/|S|)$. Taking
expectation of $f(x_{t+1})$ over the randomness at communication round $t$, we
have:

$\displaystyle\mathbb{E}\left[f(x_{x+1})\right]$ $\displaystyle\leq
f(x_{t})+\langle\nabla
f(x_{t}),\mathbb{E}\left[x_{t+1}-x_{t}\right]\rangle+\frac{L}{2}\mathbb{E}\left[\lVert
x_{t+1}-x_{t}\rVert^{2}\right]$ $\displaystyle=f(x_{t})+\eta_{g}\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\Delta^{s}_{t}+z^{s}_{t})}\right]\rangle+\frac{L}{2}\eta_{g}^{2}\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{(\Delta^{s}_{t}+z^{s}_{t})}\right\rVert^{2}\right]$
$\displaystyle=f(x_{t})+\eta_{g}\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}}\right]\rangle+\frac{L}{2}\eta_{g}^{2}\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}}\right\rVert^{2}\right]+\frac{L}{2}\eta_{g}^{2}\frac{1}{|S|^{2}|U|^{2}}\sigma^{2}C^{2}d$
(10)

where $d$ in the last expression is dimension of $x_{t}$ and in the last
equation we use the fact that $z^{s}_{t}$ is zero mean normal distribution.

Firstly, we evaluate the first-order term of Eq. (-D4),

$\displaystyle\langle\nabla$ $\displaystyle
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}}\right]\rangle$ $\displaystyle=\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t})}\right]\rangle+\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t})}\right]\rangle+\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{\bar{\Delta}^{s}_{t}}\right]\rangle,$ (11)

and the last term of Eq. (-D4) can be evaluated as follows:

$\displaystyle\langle\nabla$ $\displaystyle
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{\bar{\Delta}^{s}_{t}}\right]\rangle$
$\displaystyle=-\cfrac{\eta_{l}\bar{\alpha}_{t}Q}{2}\lVert\nabla
f(x_{t})\rVert^{2}-\cfrac{\eta_{l}\bar{\alpha}_{t}}{2Q}\mathbb{E}\left[\left\lVert\cfrac{1}{\eta_{l}|S||U|\bar{\alpha}_{t}}\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\cfrac{\eta_{l}\bar{\alpha}_{t}}{2}\mathbb{E}\left[\left\lVert\sqrt{Q}\nabla
f(x_{t})+\cfrac{1}{\sqrt{Q}\eta_{l}|S||U|\bar{\alpha}_{t}}\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right].$ (12)

This is because $\mathbb{E}\bar{\Delta}^{s}_{t}=\breve{\Delta}^{s}_{t}$ and
$\langle a,b\rangle=-\frac{1}{2}\lVert a\rVert^{2}-\frac{1}{2}\lVert
b\rVert^{2}+\frac{1}{2}\lVert a+b\rVert^{2}$ for any vector $a$, $b$.

We further upper bound the last term of Eq. -D4 as:

$\displaystyle\mathbb{E}\left[\left\lVert\sqrt{Q}\nabla
f(x_{t})+\cfrac{1}{\sqrt{Q}\eta_{l}|S||U|\bar{\alpha}_{t}}\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]$
$\displaystyle=Q\mathbb{E}\left[\left\lVert\nabla
f(x_{t})+\cfrac{1}{Q\eta_{l}|S||U|\bar{\alpha}_{t}}\sum_{s\in S}{(\sum_{u\in
U}{(-\eta_{l}\sum_{q\in[Q]}{\nabla
f_{s,u}(x^{s,u}_{t,q})}\cdot\bar{\alpha}_{t}}))}\right\rVert^{2}\right]$
$\displaystyle=Q\mathbb{E}\left[\left\lVert\cfrac{1}{Q|S||U|}\sum_{s\in
S}\sum_{u\in U}\sum_{q\in[Q]}{\nabla f_{s,u}(x_{t})-\nabla
f_{s,u}(x^{s,u}_{t,q})}\right\rVert^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle(a1)}}{{\leq}}Q\cdot\cfrac{1}{Q|S||U|}\mathbb{E}\left[\sum_{s\in
S}\sum_{u\in U}\sum_{q\in[Q]}{\lVert\nabla f_{s,u}(x_{t})-\nabla
f_{s,u}(x^{s,u}_{t,q})\rVert^{2}}\right]$
$\displaystyle\stackrel{{\scriptstyle(a2)}}{{\leq}}\cfrac{1}{|S||U|}\sum_{s\in
S}\sum_{u\in U}\sum_{q\in[Q]}{L^{2}\mathbb{E}\left[{\lVert
x_{t}-x^{s,u}_{t,q}\rVert^{2}}\right]}$
$\displaystyle\stackrel{{\scriptstyle(a3)}}{{\leq}}L^{2}5Q^{2}\eta_{l}^{2}(\sigma_{l}^{2}+6Q\sigma_{g}^{2})+L^{2}30Q^{3}\eta_{l}^{2}\lVert\nabla
f(x_{t})\rVert^{2},$ (13)

where we use $\mathbb{E}\left[\lVert X_{1}+...+X_{n}\rVert^{2}\right]\leq
n\mathbb{E}\left[\lVert X_{1}\rVert^{2}+...+\lVert X_{n}\rVert^{2}\right]$ at
(a1), L-smoothness (Assumption 1) at (a2), and Lemma 3 of [49] at (a3).

Secondly, we evaluate the second-order term in Eq. (-D4) as follows:

$\displaystyle\mathbb{E}$
$\displaystyle\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}}\right\rVert^{2}\right]$ $\displaystyle\leq
3\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t}}\right\rVert^{2}\right]+3\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}-\bar{\Delta}^{s}_{t}}\right\rVert^{2}\right]+3\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\bar{\Delta}^{s}_{t}}\right\rVert^{2}\right].$ (14)

This is because $(a+b+c)^{2}\leq 3a^{2}+3b^{2}+3c^{2}$ holds when $a=A-B$,
$b=B-C$, $c=C$ for all vector $A,B,C$. We can bound the expectation in the
last term of Eq. (-D4) as follows:

$\displaystyle\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\bar{\Delta}^{s}_{t}}\right\rVert^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\sum_{u\in
U}{(\eta_{l}\sum_{q\in[Q]}{g^{s,u}_{t,q}}\cdot\bar{\alpha}_{t})}}\right\rVert^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle(a4)}}{{=}}\eta_{l}^{2}\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\sum_{u\in U}{\sum_{q\in[Q]}{\nabla
f_{s,u}(x^{s,u}_{t,q})\cdot\bar{\alpha}_{t}}}}\right\rVert^{2}+\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\sum_{u\in U}{\sum_{q\in[Q]}{(\nabla
f_{s,u}(x^{s,u}_{t,q})-g^{s,u}_{t,q})\cdot\bar{\alpha}_{t}}}}\right\rVert^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\cfrac{\eta_{l}^{2}\bar{\alpha}_{t}^{2}}{|S|^{2}|U|^{2}}\mathbb{E}\left[\left\lVert\sum_{s\in
S}{\sum_{u\in U}{\sum_{q\in[Q]}{(\nabla
f_{s,u}(x^{s,u}_{t,q})-g^{s,u}_{t,q})}}}\right\rVert^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle(a5)}}{{\leq}}\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\cfrac{\eta_{l}^{2}\bar{\alpha}_{t}^{2}}{|S|^{2}|U|^{2}}\mathbb{E}\left[\sum_{s\in
S}{\sum_{u\in U}{\sum_{q\in[Q]}{\left\lVert\nabla
f_{s,u}(x^{s,u}_{t,q})-g^{s,u}_{t,q}\right\rVert^{2}}}}\right]$
$\displaystyle\leq\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\cfrac{\eta_{l}^{2}\bar{\alpha}_{t}^{2}}{|S|^{2}|U|^{2}}\sum_{s\in
S}{\sum_{u\in U}{\sum_{q\in[Q]}{\sigma_{l}^{2}}}}$
$\displaystyle\leq\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\cfrac{\eta_{l}^{2}\bar{\alpha}_{t}^{2}}{|S||U|}Q\sigma_{l}^{2},$
(15)

where we use $\mathbb{E}\left[\lVert X\rVert^{2}\right]=\mathbb{E}\left[\lVert
X-\mathbb{E}\left[X\right]\rVert^{2}\right]+\lVert\mathbb{E}\left[X\right]\rVert^{2}$
at (a4), and $\mathbb{E}\left[\lVert
X_{1}+...+X_{n}\rVert^{2}\right]\leq\mathbb{E}\left[\lVert
X_{1}\rVert^{2}+...+\lVert X_{n}\rVert^{2}\right]$ when $\forall i,j,i\not=j$,
$X_{i}$ and $X_{j}$ are independent and $\mathbb{E}\left[X_{i}\right]=0$ and
Assumption 2 at (a5).

Lastly, combining all of above, we have

$\displaystyle\mathbb{E}\left[f(x_{x+1})\right]$ $\displaystyle\leq
f(x_{t})+\eta_{g}\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t})}\right]\rangle+\eta_{g}\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t})}\right]\rangle$
$\displaystyle\;\;\;\;-\frac{1}{2}\eta_{g}\eta_{l}\bar{\alpha}_{t}Q\lVert\nabla
f(x_{t})\rVert^{2}-\frac{1}{2}\cfrac{\eta_{g}}{Q|S|^{2}|U|^{2}\eta_{l}\bar{\alpha}_{t}}\mathbb{E}\left[\left\lVert\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]$
$\displaystyle\;\;\;\;+\cfrac{\eta_{g}\eta_{l}\bar{\alpha}_{t}}{2}\left(L^{2}5Q^{2}\eta_{l}^{2}(\sigma_{l}^{2}+6Q\sigma_{g}^{2})+L^{2}30Q^{3}\eta_{l}^{2}\lVert\nabla
f(x_{t})\rVert^{2}\right)$
$\displaystyle\;\;\;\;+\frac{3}{2}L\eta_{g}^{2}\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\frac{3}{2}L\eta_{g}^{2}\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\frac{3}{2}L\eta_{g}^{2}\frac{1}{|S|^{2}|U|^{2}}\mathbb{E}\left[\left\lVert\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]$
$\displaystyle\;\;\;\;+\frac{3}{2}\cfrac{\eta_{g}^{2}\eta_{l}^{2}\bar{\alpha}_{t}^{2}LQ\sigma_{l}^{2}}{|S||U|}+\frac{1}{2}\cfrac{L\eta_{g}^{2}\sigma^{2}C^{2}d}{|S|^{2}|U|^{2}}$
$\displaystyle=f(x_{t})-\left(\frac{1}{2}\eta_{l}\eta_{g}\bar{\alpha}_{t}Q-\cfrac{\eta_{g}\eta_{l}\bar{\alpha}_{t}}{2}L^{2}30Q^{3}\eta_{l}^{2}\right)\lVert\nabla
f(x_{t})\rVert^{2}$
$\displaystyle\;\;\;\;-\left(\frac{1}{2}\cfrac{\eta_{g}}{Q|S|^{2}|U|^{2}\eta_{l}\bar{\alpha}_{t}}-\frac{3}{2}L\eta_{g}^{2}\frac{1}{|S|^{2}|U|^{2}}\right)\mathbb{E}\left[\left\lVert\sum_{s\in
S}{\breve{\Delta}^{s}_{t}}\right\rVert^{2}\right]$
$\displaystyle\;\;\;\;+\cfrac{\eta_{g}\eta_{l}\bar{\alpha}_{t}}{2}L^{2}5Q^{2}\eta_{l}^{2}(\sigma_{l}^{2}+6Q\sigma_{g}^{2})+\frac{3}{2}\cfrac{\eta_{g}^{2}\eta_{l}^{2}\bar{\alpha}_{t}^{2}LQ\sigma_{l}^{2}}{|S||U|}+\frac{1}{2}\cfrac{L\eta_{g}^{2}\sigma^{2}C^{2}d}{|S|^{2}|U|^{2}}$
$\displaystyle\;\;\;\;+\underbrace{\eta_{g}\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t})}\right]\rangle+\eta_{g}\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t})}\right]\rangle}_{A_{1}}$
$\displaystyle\;\;\;\;+\underbrace{\frac{3}{2}L\eta_{g}^{2}\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\frac{3}{2}L\eta_{g}^{2}\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t}}\right\rVert^{2}\right]}_{A_{2}}$
$\displaystyle\stackrel{{\scriptstyle(a6)}}{{\leq}}f(x_{t})-\eta_{l}\eta_{g}\bar{\alpha}_{t}Q\left(\frac{1}{2}-15L^{2}Q^{2}\eta_{l}^{2}\right)\lVert\nabla
f(x_{t})\rVert^{2}$
$\displaystyle\;\;\;\;+\cfrac{\eta_{g}\eta_{l}\bar{\alpha}_{t}}{2}L^{2}5Q^{2}\eta_{l}^{2}(\sigma_{l}^{2}+6Q\sigma_{g}^{2})+\frac{3}{2}\cfrac{\eta_{g}^{2}\eta_{l}^{2}\bar{\alpha}_{t}^{2}LQ\sigma_{l}^{2}}{|S||U|}+\frac{1}{2}\cfrac{L\eta_{g}^{2}\sigma^{2}C^{2}d}{|S|^{2}|U|^{2}}+A_{1}+A_{2}$
$\displaystyle\stackrel{{\scriptstyle(a7)}}{{\leq}}f(x_{t})-c\eta_{l}\eta_{g}\bar{\alpha}_{t}Q\lVert\nabla
f(x_{t})\rVert^{2}+\cfrac{\eta_{g}\eta_{l}\bar{\alpha}_{t}}{2}L^{2}5Q^{2}\eta_{l}^{2}(\sigma_{l}^{2}+6Q\sigma_{g}^{2})+\frac{3}{2}\cfrac{\eta_{g}^{2}\eta_{l}^{2}\bar{\alpha}_{t}^{2}LQ\sigma_{l}^{2}}{|S||U|}+\frac{1}{2}\cfrac{L\eta_{g}^{2}\sigma^{2}C^{2}d}{|S|^{2}|U|^{2}}+A_{1}+A_{2}$
(16)

where (a6) follows from
$\left(\frac{1}{2}\frac{\eta_{g}}{Q|S|^{2}|U|^{2}\eta_{l}\bar{\alpha}_{t}}-\frac{3}{2}L\eta_{g}^{2}\frac{1}{|S|^{2}|U|^{2}}\right)\geq
0$ if $\eta_{g}\eta_{l}\leq\frac{1}{3QL\bar{\alpha}_{t}}$ and replacing the
last terms with $A_{1}$ and $A_{2}$, and (a7) holds because there exists a
constant $c>0$ satisfying
$\left(\frac{1}{2}-15L^{2}Q^{2}\eta_{l}^{2}\right)>c>0$ if
$\eta_{l}<\frac{1}{\sqrt{30}QL}$. Divide both sides of (-D4) by
$c\eta_{l}\eta_{g}Q\bar{\alpha}_{t}$, sum over $t$ from $0$ to $T-1$, divide
both sides by $T$, and rearrange, we have

$\displaystyle\cfrac{1}{T}\sum_{t=0}^{T-1}{\mathbb{E}\left[\left\lVert\nabla
f(x_{t})\right\rVert^{2}\right]}\leq\;$
$\displaystyle\cfrac{1}{cT\eta_{g}\eta_{l}Q}\left(\mathbb{E}\left[\frac{f(x_{0})}{\bar{\alpha}_{0}}\right]-\mathbb{E}\left[\frac{f(x_{T})}{\bar{\alpha}_{T-1}}\right]\right)$
$\displaystyle\;\;\;+\frac{5}{2c}L^{2}Q\eta_{l}^{2}(\sigma_{l}^{2}+6Q\sigma_{g}^{2})+\cfrac{3L\eta_{g}\eta_{l}\sigma_{l}^{2}}{2c|S||U|}\cfrac{1}{T}\sum_{t=0}^{T-1}{\bar{\alpha}_{t}}+\cfrac{L\eta_{g}\sigma^{2}C^{2}d}{2c\eta_{l}Q|S|^{2}|U|^{2}}\cfrac{1}{T}\sum_{t=0}^{T-1}{\frac{1}{\bar{\alpha}_{t}}}$
$\displaystyle\;\;\;+\underbrace{\cfrac{1}{c\eta_{l}Q}\cfrac{1}{T}\sum_{t=0}^{T-1}{\frac{1}{\bar{\alpha}_{t}}}{\mathbb{E}\left[\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t})}\right]\rangle+\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t})}\right]\rangle\right]}}_{B_{1}}$
$\displaystyle\;\;\;+\underbrace{\cfrac{3L\eta_{g}}{2c\eta_{l}Q}\cfrac{1}{T}\sum_{t=0}^{T-1}{\frac{1}{\bar{\alpha}_{t}}}{\left(\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t}}\right\rVert^{2}\right]\right)}}_{B_{2}}.$
(17)

Let $\smash{\displaystyle\max_{s\in S,u\in
U,t\in[T]}}{\left(\frac{C}{\max{(C,\eta_{l}\lVert\mathbb{E}\left[\sum_{q\in[Q]}g^{s,u}_{t,q}\right]\rVert)}}\right)}$
be $\bar{C}$, and $\smash{\displaystyle\min_{s\in S,u\in
U,t\in[T]}}{\left(\frac{C}{\max{(C,\eta_{l}\lVert\mathbb{E}\left[\sum_{q\in[Q]}g^{s,u}_{t,q}\right]\rVert)}}\right)}$
be $\underline{C}$,
$\frac{1}{|S|}\underline{C}\leq\bar{\alpha}_{t}\leq\frac{1}{|S|}\bar{C}$ since
$\bar{\alpha}_{t}$’s definition and $\frac{1}{|S|}\sum_{s\in
S}w_{s,u}=\frac{1}{|S|}$. Using this, (-D4) is evaluated as follows:

$\displaystyle\cfrac{1}{T}\sum_{t=0}^{T-1}{\mathbb{E}\left[\left\lVert\nabla
f(x_{t})\right\rVert^{2}\right]}\leq\;$
$\displaystyle\cfrac{1}{cT\eta_{g}\eta_{l}Q|S|}\left(\mathbb{E}\left[\frac{f(x_{0})}{\underline{C}}\right]-\mathbb{E}\left[\frac{f(x_{T})}{\bar{C}}\right]\right)$
$\displaystyle\;\;\;+\frac{5}{2c}L^{2}Q\eta_{l}^{2}(\sigma_{l}^{2}+6Q\sigma_{g}^{2})+\cfrac{3\bar{C}L\eta_{g}\eta_{l}\sigma_{l}^{2}}{2c|S|^{2}|U|}+\cfrac{L\eta_{g}\sigma^{2}C^{2}d}{2c\underline{C}\eta_{l}Q|S||U|^{2}}$
$\displaystyle\;\;\;+\underbrace{\cfrac{|S|}{c\underline{C}\eta_{l}Q}\cfrac{1}{T}\sum_{t=0}^{T-1}{\mathbb{E}\left[\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t})}\right]\rangle+\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}{(\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t})}\right]\rangle\right]}}_{B_{1}}$
$\displaystyle\;\;\;+\underbrace{\cfrac{3L\eta_{g}|S|}{2c\underline{C}\eta_{l}Q}\cfrac{1}{T}\sum_{t=0}^{T-1}{\left(\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\Delta^{s}_{t}-\tilde{\Delta}^{s}_{t}}\right\rVert^{2}\right]+\mathbb{E}\left[\left\lVert\frac{1}{|S||U|}\sum_{s\in
S}{\tilde{\Delta}^{s}_{t}-\bar{\Delta}^{s}_{t}}\right\rVert^{2}\right]\right)}}_{B_{2}}.$
(18)

$B_{1}$ and $B_{2}$ is upper-bounded as follows:

$\displaystyle B_{1}$
$\displaystyle\leq\cfrac{|S|}{c\underline{C}\eta_{l}Q}\cfrac{1}{T}\sum_{t=0}^{T-1}{\mathbb{E}\left[\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in S}\sum_{u\in
U}{\left|\Delta^{s,u}_{t}-\tilde{\Delta}^{s,u}_{t}\right|}\right]\rangle+\langle\nabla
f(x_{t}),\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in S}\sum_{u\in
U}{\left|\tilde{\Delta}^{s,u}_{t}-\bar{\Delta}^{s,u}_{t}\right|}\right]\rangle\right]}$
$\displaystyle\leq\cfrac{G^{2}}{c\underline{C}|U|}\cfrac{1}{T}\sum_{t=0}^{T-1}{\mathbb{E}\left[\sum_{s\in
S}\sum_{u\in
U}{\left(\left|\alpha^{s,u}_{t}-\tilde{\alpha}^{s,u}_{t}\right|+\left|\tilde{\alpha}^{s,u}_{t}-\bar{\alpha}_{t}\right|\right)}\right]},$
$\displaystyle B_{2}$
$\displaystyle\stackrel{{\scriptstyle(a8)}}{{\leq}}\cfrac{3L\eta_{g}|S|}{2c\underline{C}\eta_{l}Q}\cfrac{1}{T}\sum_{t=0}^{T-1}{\left(\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}\sum_{u\in
U}\left|{\Delta^{s,u}_{t}-\tilde{\Delta}^{s,u}_{t}}\right|^{2}\right]+\mathbb{E}\left[\frac{1}{|S||U|}\sum_{s\in
S}\sum_{u\in
U}\left|{\tilde{\Delta}^{s,u}_{t}-\bar{\Delta}^{s,u}_{t}}\right|^{2}\right]\right)}$
$\displaystyle\leq\cfrac{3L\eta_{g}\eta_{l}QG^{2}}{2c\underline{C}|U|}\cfrac{1}{T}\sum_{t=0}^{T-1}{\mathbb{E}\left[\sum_{s\in
S}\sum_{u\in
U}{\left(\left|\alpha^{s,u}_{t}-\tilde{\alpha}^{s,u}_{t}\right|^{2}+\left|\tilde{\alpha}^{s,u}_{t}-\bar{\alpha}_{t}\right|^{2}\right)}\right]}$
(19)

with

$\displaystyle\left|\Delta^{s,u}_{t}-\tilde{\Delta}^{s,u}_{t}\right|$
$\displaystyle\leq\eta_{l}QG\left|\alpha^{s,u}_{t}-\tilde{\alpha}^{s,u}_{t}\right|,$
$\displaystyle\left|\tilde{\Delta}^{s,u}_{t}-\bar{\Delta}^{s,u}_{t}\right|$
$\displaystyle\leq\eta_{l}QG\left|\tilde{\alpha}^{s,u}_{t}-\bar{\alpha}_{t}\right|,$
(20)

by Assumption 3 of globally bounded gradients, and we use the same technique
at (a8) as (a1).

∎