# On Differentially Private Federated Linear Contextual Bandits

Xingyu Zhou Sayak Ray Chowdhury Wayne State University, Detroit, USA. Email:
<EMAIL_ADDRESS>Research, Bengaluru, Karnataka, India. Email:
<EMAIL_ADDRESS>
###### Abstract

We consider cross-silo federated linear contextual bandit (LCB) problem under
differential privacy, where multiple silos (agents) interact with the local
users and communicate via a central server to realize collaboration while
without sacrificing each user’s privacy. We identify three issues in the
state-of-the-art: (i) failure of claimed privacy protection and (ii) incorrect
regret bound due to noise miscalculation and (iii) ungrounded communication
cost. To resolve these issues, we take a two-step principled approach. First,
we design an algorithmic framework consisting of a generic federated LCB
algorithm and flexible privacy protocols. Then, leveraging the proposed
framework, we study federated LCBs under two different privacy constraints. We
first establish privacy and regret guarantees under silo-level local
differential privacy, which fix the issues present in state-of-the-art
algorithm. To further improve the regret performance, we next consider shuffle
model of differential privacy, under which we show that our algorithm can
achieve nearly “optimal” regret without a trusted server. We accomplish this
via two different schemes – one relies on a new result on privacy
amplification via shuffling for DP mechanisms and another one leverages the
integration of a shuffle protocol for vector sum into the tree-based
mechanism, both of which might be of independent interest. Finally, we support
our theoretical results with numerical evaluations over contextual bandit
instances generated from both synthetic and real-life data.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions
  2. 2 Related Work
  3. 3 Differential Privacy in Federated LCBs
  4. 4 Privacy, Regret and Communication Gaps in State-of-the-Art
    1. 4.1 Gap in Privacy Analysis
    2. 4.2 Gaps in Regret and Communication Analysis
  5. 5 Our Approach
    1. 5.1 Algorithm: Private Federated LinUCB
    2. 5.2 Privacy Protocol
  6. 6 Theoretical Results
    1. 6.1 Federated LCBs under Silo-level LDP
    2. 6.2 Federated LCBs under SDP
      1. 6.2.1 SDP guarantee for a wide range of privacy parameters
    3. 6.3 Key Techniques: Overview
  7. 7 Simulation Results
  8. 8 Concluding Remarks
  9. 9 Acknowledgements
  10. A More Discussions on Gaps in SOTA
    1. A.1 More on violation of silo-level LDP
    2. A.2 More on violation of Fed-DP
    3. A.3 More on communication cost analysis
  11. B A Generic Regret Analysis for Algorithm 1
    1. B.1 Proofs
  12. C Discussion on Private Adaptive Communication
    1. C.1 Regret Analysis under Non-private Adaptive Schedule
    2. C.2 Challenges in Regret Analysis under Private Adaptive Schedule
  13. D Additional Details on Federated LCBs under Silo-Level LDP
    1. D.1 Proof of Theorem 6.1
    2. D.2 Alternative Privacy Protocol for Silo-Level LDP
  14. E Additional Details on Federated LCBs under SDP
    1. E.1 Amplification lemma for SDP
    2. E.2 Vector Sum Protocol for SDP
    3. E.3 Proofs
  15. F Further Discussions
    1. F.1 Silo-level LDP/SDP vs. Other Privacy Notions
    2. F.2 A Simple Tweak of Algorithm 1 for a Stronger Privacy Guarantee
    3. F.3 Non-unique Users
  16. G Additional Details on Simulation Results

##  1 Introduction

We consider the classic _cross-silo_ Federated Learning (FL) paradigm
[KMABBBBCCC+21] applied to linear contextual bandits (LCB). In this setting, a
set of $M$ local silos or agents (e.g., hospitals) communicate with a central
server to learn about the unknown bandit parameter (e.g., hidden vector
representing values of the user for different medicines). In particular, at
each round $t\in[T]$, each local agent $i\in[M]$ receives a new user (e.g.,
patient) with context information $c_{t,i}\in\mathcal{C}_{i}$ (e.g., age,
gender, medical history), recommends an action $a_{t,i}\in\mathcal{K}_{i}$
(e.g., a choice of medicine), and then it observes a real-valued reward
$y_{t,i}$ (e.g., effectiveness of the prescribed medicine). In linear
contextual bandits, the reward $y_{t,i}$ is a linear function of the unknown
bandit parameter $\theta^{*}\in\mathbb{R}^{d}$ corrupted by $i.i.d$ mean-zero
observation noise $\eta_{t,i}$, i.e., $y_{t,i}=\langle
x_{t,i},\theta^{*}\rangle+\eta_{t,i}$, where
$x_{t,i}=\phi_{i}(c_{t,i},a_{t,i})$ and
$\phi_{i}:\mathcal{C}_{i}\times\mathcal{K}_{i}\to\mathbb{R}^{d}$ is a known
function that maps a context-action pair to a $d$-dimensional real-valued
feature vector. The goal of federated LCB is to minimize the cumulative
_group_ pseudo-regret defined as

$\displaystyle
R_{M}(T)=\sum_{i=1}^{M}\sum_{t=1}^{T}\left[\max_{a\in\mathcal{K}_{i}}\langle\phi_{i}(c_{t,i},a),\theta^{*}\rangle-\langle
x_{t,i},\theta^{*}\rangle\right].$

To achieve the goal, as in standard cross-silo FL, the agents are allowed to
communicate with the central server following a star-shaped communication,
i.e., each agent can communicate with the server by uploading and downloading
data, but agents cannot communicate with each other directly. However, the
communication process (i.e., both data and schedule) could also possibly incur
privacy leakage for each user $t$ at each silo $i$, e.g., the sensitive
context information $c_{t,i}$ and reward $y_{t,i}$.

To address this privacy risk, we resort to _differential privacy_ [DR14], a
principled way to prove privacy guarantee against adversaries with arbitrary
auxiliary information. In standard _cross-device_ FL, the notion of privacy is
often the client-level DP, which protects the identity of each participating
client or device. However, it has limitations in the setting of cross-silo FL,
where the protection targets are users (e.g., patients) rather than
participating silos or agents (e.g., hospitals). Also, in order to adopt
client-level DP to cross-silo FL, one needs the server and other silos to be
trustworthy, which is often not the case. Hence, recent studies [LR21, LGR22,
LHWS22, DPZRT18] on cross-silo federated supervised learning have converged to
a new privacy notion, _which requires that for each silo, all of its
communication during the entire process is private (“indistinguishable”) with
respect to change of one local user of its own._ This allows one to protect
_each user_ within each silo without trustworthy server and other silos. In
this paper, we adapt it to the setting of cross-silo federated contextual
bandits and call it _silo-level LDP_.

[DP20] adopt a similar but somewhat weaker notion of privacy called _Federated
DP_ and takes the first step to tackle this important problem of private and
federated linear contextual bandits (LCBs). In fact, the performance
guarantees presented by the authors are currently the state-of-the-art for
this problem. The proposed algorithm _claims_ to protect the privacy of each
user at each silo. Furthermore, given a privacy budget $\varepsilon>0$, the
claimed regret bound is $\widetilde{O}(\sqrt{MT/\varepsilon})$ with only
$O(M\log T)$ communication cost, which matches the regret of a super-single
agent that plays for total $MT$ rounds. Unfortunately, in spite of being the
state-of-the-art, the aforementioned privacy, regret and communication cost
guarantees have fundamental gaps, as discussed below.

###  1.1 Our Contributions

Identify privacy, regret and communication gaps in state-of-the-art [DP20]. In
Section 4, we first show that the proposed algorithm in [DP20] could leak
privacy from the side channel of adaptive communication schedule, which
depends on users’ _non-private_ local data. Next, we identify a mistake in
total injected privacy noise in the current regret analysis. Accounting for
this miscalculation, the correct regret bound would amount to
$\widetilde{O}(M^{3/4}\sqrt{T/\varepsilon})$, which is $M^{1/4}$ factor higher
than the claimed one, and doesn’t match regret performance of the super agent.
Finally, we observe that due to the presence of privacy noise, its current
analysis for $O(M\log T)$ communication cost no longer holds. To resolve these
issues, we take the following two-step principled approach:

(i) design a generic algorithmic and analytical framework. In Section 5, we
propose a generic federated LCB algorithm along with a flexible privacy
protocol. Our algorithm adopts a fixed-batch schedule (rather than an adaptive
one in [DP20]) that helps avoid privacy leakage from the side channel, as well
as subtleties in communication analysis. Our privacy protocol builds on a
distributed version of the celebrated tree-based algorithm [CSS11, DNPR10],
enabling us to provide different privacy guarantees in a unified way. We
further show that our algorithm enjoys a simple and generic analytical regret
bound that only depends on the total amount of injected privacy noise under
the required privacy constraints.

(ii) prove performance guarantees under different privacy notions. We build
upon the above framework to study federated LCBs under two different privacy
constraints. In Section 6.1, we consider silo-level LDP (a stronger notion of
privacy than Federated DP of [DP20]) and establish privacy guarantee with a
correct regret bound $\widetilde{O}(M^{3/4}\sqrt{T/\varepsilon})$ and
communication cost $O(\sqrt{MT})$, hence fixing the gaps in [DP20]. Next, to
match the regret of a super single agent, we consider shuffle DP (SDP)
[CSUZZ19] in Section 6.2 and establish a regret bound of
$\widetilde{O}(\sqrt{MT/\varepsilon})$. We provide two different techniques to
achieve this – one that relies on a new result on privacy amplification via
shuffling for DP mechanisms and the other that integrates a shuffle protocol
for vector sums [CJMP21] into the tree-based mechanism, both of which might be
of independent interest. In Section 7, we support our theoretical results with
simulations on contextual bandit instances generated from synthetic and real-
life data.

##  2 Related Work

Private bandit learning has recently received increasing attention under
various notion of DP. For multi-armed bandits (MAB) where rewards are the
sensitive data, different DP models including the central model [MT15, AB22,
SS19], local model [RZLS20] and distributed model [CZ22, TKMS21] have been
studied. Among them, we note that [CZ22] also presents optimal private regret
bounds under the above three DP models while only relying on discrete privacy
noise, hence avoiding the privacy leakage of continuous privacy noise on
finite computers due to floating point arithmetic. For linear bandits (without
contexts protection), [LZJ22] establishes the first near-optimal private
regret bounds for central, local, and shuffle models of approximate DP. The
same problem has also been studied under pure-DP in [HGFD22]. In the specific
case of linear contextual bandits, where both the contexts and rewards need to
be protected, there are recent line of work under the central [SS18], local
[ZCHLW20] and shuffle model [CZ22a, GCPP22, TKMS23] of DP. Private bandit
learning has also been studied beyond linear settings, such as kernel bandits
[ZT21, Dub21, LZJ23].

All the above papers consider learning by a single agent. To the best of our
knowledge, [DP20] is the first to consider cross-silo federated linear
contextual bandits (LCBs). Non-private federated or distributed LCBs have also
been well studied [WHCW20, HWMG22, HWYS21]. One common goal is to match the
regret achieved by a super single agent that plays $MT$ rounds while keeping
communication among agents as low as possible. Our work shares the same spirit
in that we aim to match the regret achieved by a super single agent under
differential privacy.

Broadly speaking, our work also draws inspiration from recent advances in
private cross-silo federated supervised learning [LR21, LHWS22]. In
particular, our silo-level local and shuffle DP definitions for federated LCBs
in the main paper can be viewed as counterparts of the ones proposed for
cross-silo federated supervised learning (see, e.g., [LR21]).

##  3 Differential Privacy in Federated LCBs

We now formally introduce differential privacy in cross-silo federated
contextual bandits. Let a dataset $D_{i}$ at each silo $i$ be given by a
sequence of $T$ _unique_ users $U_{1,i},\ldots,U_{T,i}$. Each user $U_{t,i}$
is identified by her context information $c_{t,i}$ as well as reward responses
she would give to all possible actions recommended to her. We say two datasets
$D_{i}$ and $D_{i}^{\prime}$ at silo $i$ are adjacent if they differ exactly
in one participating user, i.e., $U_{\tau,i}\neq U^{\prime}_{\tau,i}$ for some
$\tau\in[T]$ and $U_{s,i}=U^{\prime}_{s,i}$ for all $s\neq\tau$.

Silo-level local differential privacy (LDP). Consider a multi-round, cross-
silo federated learning algorithm $\mathcal{Q}$. At each round $t$, each silo
$i$ communicates a randomized message $Z_{i}^{t}$ of its data $D_{i}$ to the
server, which may depend (due to collaboration) on previous randomized
messages $Z_{j}^{1},\ldots,Z_{j}^{t-1}$ from all other silos $j\neq i$. We
allow $Z_{i}^{t}$ to be empty if there is no communication at round $t$. Let
$Z_{i}=(Z_{i}^{1},\ldots,Z_{i}^{T})$ denote the full transcript of silo $i$’s
communications with the server over $T$ rounds and $\mathcal{Q}_{i}$ the
induced local mechanism in this process. Note that $Z_{i}$ is a realization of
random messages generated according to the local mechanism $\mathcal{Q}_{i}$.
We denote by $Z_{-i}=(Z_{1},\ldots,Z_{i-1},Z_{i+1},\ldots,Z_{M})$ the full
transcripts of all but silo $i$. We assume that $Z_{i}$ is conditionally
independent of $D_{j}$ for all $j\neq i$ given $D_{i}$ and $Z_{-i}$. With this
notation, we have the following definition of silo-level LDP.

######  Definition 3.1 (Silo-level LDP).

A cross-silo federated learning algorithm $\mathcal{Q}$ with $M$ silos is said
to be $(\varepsilon_{i},\delta_{i})_{i\in M}$ silo-level LDP if for each silo
$i\\!\in\\![M]$, it holds that

$\displaystyle\mathbb{P}\Big{[}\mathcal{Q}_{i}(Z_{i}\\!\in\\!\mathcal{E}_{i}|D_{i},\\!Z_{-i})\Big{]}\\!\leq\\!e^{\varepsilon_{i}}\mathbb{P}\Big{[}\mathcal{Q}_{i}(Z_{i}\\!\in\\!\mathcal{E}_{i}|D^{\prime}_{i},\\!Z_{-i})\Big{]}\\!+\\!\delta_{i}~{},$

for all adjacent datasets $D_{i}$ and $D^{\prime}_{i}$, and for all events
$\mathcal{E}_{i}$ in the range of $\mathcal{Q}_{i}$. If
$\varepsilon_{i}=\varepsilon$ and $\delta_{i}=\delta$ for all $i\in[M]$, we
simply say $\mathcal{Q}$ is $(\varepsilon,\delta)$-silo-level LDP.

Roughly speaking, a silo-level LDP algorithm protects the privacy of each
individual user (e.g., patient) within each silo in the sense that an
adversary (which could either be the central server or other silos) cannot
infer too much about any individual’s sensitive information (e.g., context and
reward) or determine whether an individual participated in the learning
process.111This is indeed a notion of item-level DP. It appears under
different names in prior work, e.g., silo-specific sample-level DP [LHWS22],
inter-silo record-level DP [LR21]. A comparison of this notion of privacy with
standard local DP, central DP and shuffle DP for single-agent LCBs is
presented in Appendix F.1.

######  Remark 3.2 (Federated DP vs. Silo-level LDP).

[DP20] consider a privacy notion called Federated DP (Fed-DP in short). As
summarized in [DP20], Fed-DP requires “the action chosen by any agent must be
sufficiently impervious (in probability) to any single pair $(x,y)$ from any
other agent”. Both silo-level LDP and Fed-DP are item-level DP as the
neighboring relationship is defined by differing in one participating user.
The key here is to note that silo-level DP implies Fed-DP by the post-
processing property of DP, and thus it is a stronger notion of privacy. In
fact, [DP20] claim to achieve Fed-DP by relying on privatizing the
communicated data from each silo. However, as we shall see in Section 4, its
proposed algorithm fails to privatize the adaptive synchronization schedule,
which is the key reason behind privacy leakage in their algorithm.

Shuffle differential privacy (SDP). Next, we consider the notion of SDP
[CSUZZ19], which builds upon a trusted third-party (shuffler) to amplify
privacy. This provides us with the possibility to achieve a better regret
compared to the one under silo-level LDP while still without a trusted server.
Under the shuffle model of DP in FL, each silo $i\in[M]$ first applies a local
randomizer $\mathcal{R}$ to its raw local data and sends the randomized output
to a shuffler $\mathcal{S}$. The shuffler $\mathcal{S}$ permutes all the
messages from all $M$ silos uniformly at random and sends those to the central
server. Roughly speaking, SDP requires all the messages sent by the shuffler
to be private (“indistinguishable”) with respect to a single user change among
all $MT$ users. This item-level DP is defined formally as follows.

######  Definition 3.3 (SDP).

Consider a cross-silo federated learning algorithm $\mathcal{Q}$ that induces
a (randomized) mechanism $\mathcal{M}$ whose output is the collection of all
messages sent by the shuffler during the entire learning process. Then, the
algorithm $\mathcal{Q}$ is said to be $(\varepsilon,\delta)$-SDP if

$\displaystyle\mathbb{P}\Big{[}\mathcal{M}(D)\in\mathcal{E}\Big{]}\leq
e^{\varepsilon}\,\mathbb{P}\Big{[}\mathcal{M}(D^{\prime})\in\mathcal{E}\Big{]}+\delta~{},$

for all $\mathcal{E}$ in the range of $\mathcal{M}$ and for all adjacent
datasets $D=(D_{1},\ldots,D_{M})$ and
$D^{\prime}=(D^{\prime}_{1},\ldots,D^{\prime}_{M})$ such that
$\sum_{i=1}^{M}\sum_{t=1}^{T}\mathbbm{1}_{\\{U_{t,i}\neq
U^{\prime}_{t,i}\\}}=1$.

##  4 Privacy, Regret and Communication Gaps in State-of-the-Art

In this section, we discuss the gaps present in privacy, regret and
communication cost guarantees of the state-of-the-art algorithm proposed in
[DP20].

###  4.1 Gap in Privacy Analysis

We take a two-step approach to demonstrate the privacy issue in [DP20]. To
start with, we argue that the proposed technique (i.e., Algorithm 1 in [DP20])
fails to achieve silo-level LDP due to privacy leakage through the side
channel of communication schedule (i.e., when the agents communicate with the
server). The key issue is that the adaptive communication schedule in their
proposed algorithm depends on users’ _non-private_ data. This fact can be
utilized by an adversary or malicious silo $j$ to infer another silo $i$’s
users’ sensitive information, which violates the requirement of silo-level
LDP. Specifically, in the proposed algorithm of [DP20], _all_ silos
communicate with the server (which is termed as _synchronous_ setting) if

$\displaystyle\exists\;\text{some silo}\;i\in[M]:f(X_{i},Z)>0~{},$ (1)

where $f$ is some function, $X_{i}$ is the non-private local data of silo $i$
since the last synchronization and $Z$ is all previously synchronized data.
Crucially, the form of $f$ and the rule (1) are public information, known to
all silos even before the algorithm starts. This local and non-private data-
dependent communication rule in (1) causes privacy leakage, as illustrated
below with a toy example.

######  Example 4.1 (Privacy leakage).

Consider there are two silos $i$ and $j$ following the algorithm in [DP20].
After the first round, $X_{i}$ in (1) includes the data of the first user in
silo $i$ (say Alice), $X_{j}$ includes the data of the first user in silo $j$
(say Bob) and $Z$ is empty (zero). Let communication be triggered at the end
of first round and assume $f(X_{j},0)\leq 0$. Since the rule (1) is public,
silo $j$ can infer that $f(X_{i},0)>0$, i.e. the communication is triggered by
silo $i$. Since $f$ is also public knowledge, silo $j$ can utilize this to
infer some property of $X_{i}$. Hence, by observing the communication signal
_only_ (even without looking at the data), silo $j$ can infer some sensitive
data of Alice.222 In fact, given the specific form of $f$ in [DP20], silo $j$
gets to know that
$\log\det\left(I+\lambda_{\min}^{-1}x_{1,i}x_{1,i}^{\top}\right)>D$, where
$\lambda_{\min}>0$ is a regularizer (which depends on privacy budgets
$\varepsilon,\delta$) and $D>0$ is some suitable threshold (see Appendix A for
the specific form of $f$). This in turn implies that $\left\lVert
x_{1,i}\right\rVert>C$, where $C$ is some constant. Since $x_{1,i}$ contains
the context information of the user, this information could immediately reveal
that some specific features in the context vector are active, which can be
inferred by the adversary silo (e.g., silo $j$).

The above example demonstrates that the proposed algorithm in [DP20] does not
satisfy silo-level LDP, implying (i) their current proof for Fed-DP guarantee
via post-processing of silo-level LDP does not hold anymore and (ii) Fed-DP is
weak privacy protection. However, it does not necessarily imply that this
algorithm also does not satisfy the weaker notion of Fed-DP (as considered in
[DP20]). Nevertheless, one can show that this algorithm indeed also fails to
guarantee Fed-DP by leveraging Example 4.1.

To see this, recall the definition of Fed-DP from Remark 3.2. In the context
of Example 4.1, it translates to silo $j$ selecting similar actions for its
users when a single user in silo $i$ changes. Specifically, if the first user
in silo $i$ changes from Alice to say, Tracy, Fed-DP mandates that all $T$
actions suggested by silo $j$ to its local $T$ users remain
“indistinguishable”. This, in turn, implies that the communicated data from
silo $i$ must remain “indistinguishable” at silo $j$ for each $t\\!\in\\![T]$.
This is because the actions at silo $j$ are chosen _deterministically_ based
on its local data as well as communicated data from silo $i$, and the local
data at silo $j$ remains unchanged. However, in Algorithm 1 of [DP20], the
communicated data from silo $i$ is not guaranteed to remain
“indistinguishable” as synchronization depends on non-private local data (e.g.
$X_{i}$ in (1)). In other words, without additional privacy noise added to
$X_{i}$ in (1), the change from Alice to Tracy could affect the _existence of
synchronization_ at round $t\geq 1$ a lot. Consequently, under these two
neighboring situations (e.g. Alice vs. Tracy), the communicated data from silo
$i$ could differ significantly at round $t+1$. As a result, the action chosen
at round $t+1$ in silo $j$ can be totally different, which violates the Fed-DP
definition. This holds true even if silo $i$ injects noise while communicating
its data (as done in Algorithm 1 of [DP20]) due to a large change of non-
private communicated data (see Appendix A).

###  4.2 Gaps in Regret and Communication Analysis

We now turn to regret and communication analysis of [DP20], which has
fundamental gaps that lead to incorrect conclusions in the end. First, the
reported cost of privacy in regret bound is $\tilde{O}(\sqrt{MT/\varepsilon})$
(ignoring dependence on dimension $d$ for simplicity), which leads to the
(incorrect) conclusion that federated LCBs across $M$ silos under silo-level
LDP can achieve the same order of regret as a super single agent that plays
$MT$ rounds. However, in the proposed analysis, the total amount of injected
privacy noise is miscalculated. In particular, variance of total noise needs
to be $M\sigma^{2}$ rather than the proposed value of $\sigma^{2}$. This comes
from the fact that each silo injects Gaussian noise with variance $\sigma^{2}$
when sending out local data and hence the total amount of noise at the server
is $M\sigma^{2}$. Accounting for this correction, the cost of privacy becomes
$\tilde{O}(M^{3/4}\sqrt{T/\varepsilon})$, which is $O(M^{1/4})$ factor worse
than the claimed cost. Hence, we conclude that Algorithm 1 in [DP20] cannot
achieve the same order of regret as a super single agent. Second, the proposed
analysis in [DP20] to show $O(\log T)$ communication cost for the _data-
adaptive_ schedule (1) under privacy constraint essentially follows from the
non-private analysis of [WHCW20]. Unfortunately, due to additional privacy
noise, this direct approach no longer holds, and hence the reported
logarithmic communication cost stands ungrounded (see Appendix A for more
details on this).

##  5 Our Approach

To address all three issues in [DP20], we introduce a generic algorithm for
private and federated linear contextual bandits (Algorithm 1) along with a
flexible privacy protocol (Algorithm 2), which not only allows us to present
the correct privacy, regret, and communication results under silo-level LDP
(and hence under Fed-DP) (Section 6.1), but also helps us achieve the same
order of regret as a super single agent under SDP (Section 6.2). Throughout
the paper, we make following assumptions.

######  Assumption 5.1 (Boundedness [SS18, CZ22a]).

The rewards are bounded, i.e., $y_{t,i}\in[0,1]$ for all $t\in[T]$ and
$i\in[M]$. Moreover, the parameter vector and the context-action features have
bounded norms, i.e., $\left\lVert\theta^{*}\right\rVert_{2}\leq 1$ and
$\sup_{c,a}\left\lVert\phi_{i}(c,a)\right\rVert_{2}\leq 1$ for all $i\in[M]$.

###  5.1 Algorithm: Private Federated LinUCB

Algorithm 1 Private-FedLinUCB

1: Parameters: Batch size $B\in\mathbb{N}$, regularization $\lambda>0$,
confidence radii $\\{\beta_{t,i}\\}_{t\in[T],i\in[M]}$, feature map
$\phi_{i}:\mathcal{C}_{i}\times\mathcal{K}_{i}\to\mathbb{R}^{d}$, privacy
protocol $\mathcal{P}=(\mathcal{R},\mathcal{S},\mathcal{A})$

2: Initialize: $W_{i}=0,U_{i}=0$ for all agents $i\in[M]$,
$\widetilde{W}_{\text{syn}}=0$, $\widetilde{U}_{\text{syn}}=0$

3: for $t\\!=\\!1,\ldots,T$ do

4: for each agent $i=1,\ldots,M$ do

5: Receive context $c_{t,i}$; compute $V_{t,i}=\lambda
I+\widetilde{W}_{\text{syn}}+W_{i}$ and
$\widehat{\theta}_{t,i}=V_{t,i}^{-1}(\widetilde{U}_{\text{syn}}+U_{i})$

6: Play action
$a_{t,i}\\!=\\!\mathop{\mathrm{argmax}}_{a\in\mathcal{K}_{i}}\langle\phi_{i}(c_{t,i},\\!a),\widehat{\theta}_{t,i}\rangle\\!+\\!\beta_{t,i}\\!\left\lVert\phi_{i}(c_{t,i},\\!a)\right\rVert_{V_{t,i}^{-1}}$;
observe reward $y_{t,i}$

7: Set $x_{t,i}\\!=\\!\phi_{i}(c_{t,i},a_{t,i})$, $U_{i}=U_{i}+x_{t,i}y_{t,i}$
and $W_{i}=W_{i}+x_{t,i}x_{t,i}^{\top}$

8: end for

9: if $t\ \mathrm{mod}\ B=0$ then

10: // Local randomizer $\mathcal{R}$ at _all_ agents $i\in[M]$

11: Send randomized messages
$R_{t,i}^{\text{bias}}=\mathcal{R}^{\text{bias}}(U_{i})$ and
$R_{t,i}^{\text{cov}}=\mathcal{R}^{\text{cov}}(W_{i})$ to $\mathcal{S}$

12: // Third party $\mathcal{S}$

13: Shuffle (or, not) all messages
$S_{t}^{\text{bias}}=\mathcal{S}(\\{R_{t,i}^{\text{bias}}\\}_{i\in[M]})$ and
$S_{t}^{\text{cov}}=\mathcal{S}(\\{R_{t,i}^{\text{cov}}\\}_{i\in[M]})$

14: // Analyzer $\mathcal{A}$ at the server

15: Compute private synchronized statistics
$\widetilde{U}_{\text{syn}}=\mathcal{A}^{\text{bias}}(S_{t}^{\text{bias}})$
and $\widetilde{W}_{\text{syn}}=\mathcal{A}^{\text{cov}}(S_{t}^{\text{cov}})$

16: // _All_ agents $i\in[M]$

17: Receive $\widetilde{W}_{\text{syn}}$ and $\widetilde{U}_{\text{syn}}$ from
the server and reset $W_{i}=0$, $U_{i}=0$

18: end if

19: end for

We build upon the celebrated LinUCB algorithm [APS11] by adopting a _fixed-
batch_ schedule for synchronization among agents and designing a privacy
protocol $\mathcal{P}$ (Algorithm 2) for both silo-level LDP and SDP . At each
round $t$, each agent $i$ recommends an action $a_{t,i}$ to each local user
following _optimism in the face of uncertainty_ principle. First, the agent
computes a local estimate $\widehat{\theta}_{t,i}$ based on _all_ available
data to her, which includes previously synchronized data from all agents as
well as her own new local data (line 5 of Algorithm 1). Then, the action
$a_{t,i}$ is selected based on the LinUCB decision rule (line 6), where a
proper radius $\beta_{t,i}$ is chosen to balance between exploration and
exploitation. After observing the reward $y_{t,i}$, each agent accumulates her
own local data (bias vector $x_{t,i}y_{t,i}$ and covariance matrix
$x_{t,i}x_{t,i}^{\top}$) and stores them in $U_{i}$ and $W_{i}$, respectively
(line 7). A communication is triggered between agents and central server
whenever a batch ends – we assume w.l.o.g. total rounds $T$ is divisible by
batch size $B$ (line 9). During this process, a protocol
$\mathcal{P}=(\mathcal{R},\mathcal{S},\mathcal{A})$ assists in aggregating
local data among all agents while guaranteeing privacy properties (to be
discussed in detail soon). After communication, each agent receives latest
synchronized data $\widetilde{W}_{\text{syn}},\widetilde{U}_{\text{syn}}$ from
the server (line 17). Here, for any $t\\!=\\!kB,k\in[T/B]$,
$\widetilde{W}_{\text{syn}}$ represents noisy version of all covariance
matrices up to round $t$ from all agents (i.e.,
$\sum_{i=1}^{M}\sum_{s=1}^{t}x_{s,i}x_{s,i}^{\top}$) and similarly,
$\widetilde{U}_{\text{syn}}$ represents noisy version of all bias vectors
$\sum_{i=1}^{M}\sum_{s=1}^{t}x_{s,i}y_{s,i}$. Finally, each agent resets
$W_{i}$ and $U_{i}$ so that they can be used to accumulate new local data for
the next batch. Note that Algorithm 1 uses a fixed-batch (data-independent)
communication schedule rather than the adaptive, data-dependent one in [DP20].
This allows us to resolve privacy and communication issues in [DP20] (to be
discussed in Section 6).

###  5.2 Privacy Protocol

We now turn to our privacy protocol $\mathcal{P}$ (Algorithm 2), which helps
to aggregate data among all agents under privacy constraints. The key
component of $\mathcal{P}$ is a _distributed_ version of the classic tree-
based algorithm, which was originally designed for continual release of
private sum statistics [CSS11, DNPR10]. That is, given a stream of
(multivariate) data $\gamma\\!=\\!(\gamma_{1},\ldots,\gamma_{K})$, one aims to
release $s_{k}\\!=\\!\sum_{l=1}^{k}\gamma_{l}$ _privately_ for all
$k\\!\in\\![K]$. The tree-based mechanism constructs a complete binary tree
$\mathcal{T}$ in online manner. The leaf nodes contain data $\gamma_{1}$ to
$\gamma_{K}$, and internal nodes contain the sum of all leaf nodes in its sub-
tree, see Fig. 1 for an illustration. For any new arrival data $\gamma_{k}$,
it only releases a tree node privately, which corresponds to a noisy partial
sum (p-sum) between two time indices. As an example, take $k=6$, and hence the
new arrival is $\gamma_{6}$. The tree-based mechanism first computes the p-sum
$\sum[5,6]=\gamma_{5}+\gamma_{6}$ (line 6 in Algorithm 2). Then, it adds a
Gaussian noise with appropriate variance $\sigma_{0}^{2}$ to $\sum[5,6]$ and
releases the noisy p-sum (line 7). Finally, to compute the prefix sum
statistic $\sum[1,6]$ privately, it simply adds noisy p-sums for $\sum[1,4]$
and $\sum[5,6]$, respectively. Reasons behind releasing and aggregating p-sums
are that (i) each data point $\gamma_{k}$ only affects at most $1+\log K$
p-sums (useful for privacy) and (ii) each sum statistic $\sum[1,k]$ only
involves at most $1+\log k$ p-sums (useful for utility).

Algorithm 2 $\mathcal{P}$, a privacy protocol used in Algorithm 1

1: Procedure: Local Randomizer $\mathcal{R}$ at each agent

2: //Input: stream data $(\gamma_{1},\ldots,\gamma_{K})$,
$\varepsilon\\!>\\!0,\delta\\!\in\\!(0,1]$

3: for $k\\!=\\!1,\ldots,K$ do

4: Express $k$ in binary form: $k=\sum_{j}\text{Bin}_{j}(k)\cdot 2^{j}$

5: Find index of first one $i_{k}\\!=\\!\min\\{j:\text{Bin}_{j}(k)\\!=\\!1\\}$

6: Compute p-sum
$\alpha_{i_{k}}\\!=\\!\sum_{j<i_{k}}\alpha_{j}\\!+\\!\gamma_{k}$

7: Output
$\widehat{\alpha}_{k}\\!=\\!\alpha_{i_{k}}\\!+\\!\mathcal{N}(0,\\!\sigma_{0}^{2}I)$

8: end for

9: Procedure: Analyzer $\mathcal{A}$ at server

10: //Input : data from
$\mathcal{S}\\!:\\!(\widehat{\alpha}_{k,1},\ldots,\widehat{\alpha}_{k,M}),k\\!\in\\![K]$

11: for $k\\!=\\!1,\ldots,K$ do

12: Express $k$ in binary and find index of first one $i_{k}$

13: Add noisy p-sums of all agents:
$\widetilde{\alpha}_{i_{k}}=\sum_{i=1}^{M}\widehat{\alpha}_{k,i}$

14: Output:
$\widetilde{s}_{k}=\sum_{j:\text{Bin}_{j}(k)=1}\widetilde{\alpha}_{j}$

15: end for

Figure 1: Illustration of the tree-based algorithm. Each leaf node is the
stream data and each internal node is a p-sum
$\Sigma[i,j]=\sum_{l=i}^{j}\gamma_{l}$. The green node corresponds to the
newly computed p-sum at each $k$, i.e., $\alpha_{i_{k}}$ in Algorithm 2.

Our privacy protocol $\mathcal{P}\\!=\\!(\mathcal{R},\mathcal{S},\mathcal{A})$
breaks down the above classic mechanism of releasing and aggregating p-sums
into a local randomizer $\mathcal{R}$ at each agent and an analyzer
$\mathcal{A}$ at the server, separately, while allowing for a possible
shuffler in between to amplify privacy. For each $k$, the local randomizer
$\mathcal{R}$ at each agent computes and releases the noisy p-sum to a third-
party $\mathcal{S}$ (lines 4-7). $\mathcal{S}$ can either be a shuffler that
permutes the data uniformly at random (for SDP) or can simply be an identity
mapping (for silo-level LDP). It receives a total of $M$ noisy p-sums, one
from each agent, and sends them to the central server. The analyzer
$\mathcal{A}$ at the server first adds these $M$ new noisy p-sums to
synchronize them (line 13). It then privately releases the synchronized prefix
sum by adding up all relevant synchronized p-sums as discussed in above
paragraph (line 14). Finally, we employ $\mathcal{P}$ to Algorithm 1 by
observing that local data $\gamma_{k,i}$ for batch $k$ and agent $i$ consists
of bias vectors
$\gamma_{k,i}^{\text{bias}}\\!=\\!\sum_{t=(k-1)B+1}^{kB}x_{t,i}y_{t,i}$ and
covariance matrices
$\gamma_{k,i}^{\text{cov}}\\!=\\!\sum_{t=(k-1)B+1}^{kB}x_{t,i}x_{t,i}^{\top}$,
which are stored in $U_{i}$ and $W_{i}$ respectively. We denote the randomizer
and analyzer for bias vectors as $\mathcal{R}^{\text{bias}}$ and
$\mathcal{A}^{\text{bias}}$, and for covariance matrices as
$\mathcal{R}^{\text{cov}}$ and $\mathcal{A}^{\text{cov}}$ in Algorithm 1.

######  Remark 5.2 (Sensitivity vs. norm).

Although the $l_{2}$ norm of each $\gamma_{k}$ in Algorithm 1 scales linearly
with batch size $B$, its sensitivity is only one, i.e., changing one user’s
data only changes Euclidean norm of the vector $\gamma_{k,i}^{\text{bias}}$
and Frobenius norm of the matrix $\gamma_{k,i}^{\text{cov}}$ by at most one,
due to our boundedness assumption. It is this sensitivity that determines the
noise level for privacy in Algorithm 2.

##  6 Theoretical Results

We now show that our generic algorithmic framework (Algorithms 1 and 2)
enables us to establish regret bounds of federated LCBs under both silo-level
LDP and SDP in a simple and unified way. Proofs of all the results are
deferred to Appendices D and E due to space constraint.

###  6.1 Federated LCBs under Silo-level LDP

We first present the performance of Algorithm 1 under silo-level LDP, hence
fixing the privacy, regret and communication issues of the state-of-the-art
algorithm in [DP20]. The key idea is to inject Gaussian noise with proper
variance ($\sigma_{0}^{2}$ in Algorithm 2) when releasing a p-sum such that
all the released p-sums up to any batch $k\\!\in\\![K]$ is
$(\varepsilon,\delta)$-DP for any agent $i\\!\in\\![M]$. Then, by Definition
3.1, it achieves silo-level LDP. Note that in this case, there is no shuffler,
which is equivalent to the fact that the third party $\mathcal{S}$ in
$\mathcal{P}$ is simply an identity mapping, denoted by $\mathcal{I}$. The
following result states this formally.

######  Theorem 6.1 (Performance under silo-level LDP).

Fix batch size $B$, privacy budgets $\varepsilon\\!>\\!0$,
$\delta\\!\in\\!(0,1)$. Let
$\mathcal{P}\\!=\\!(\mathcal{R},\mathcal{I},\mathcal{A})$ be a protocol given
by Algorithm 2 with parameters
$\sigma_{0}^{2}\\!=\\!8\kappa\cdot\frac{(\log(2/\delta)+\varepsilon)}{\varepsilon^{2}}$,
where $\kappa\\!=\\!1\\!+\\!\log(T/B)$. Then, under Assumption 5.1, Algorithm
1 instantiated with $\mathcal{P}$ satisfies $(\varepsilon,\delta)$-silo-level
LDP. Moreover, for any $\alpha\\!\in\\!(0,1]$, there exist choices of
$\lambda$ and $\\{\beta_{t,i}\\}_{t,i}$ such that, with probability at least
$1-\alpha$, it enjoys a group regret

$\displaystyle R_{M}(T)\\!=\\!O\left({dMB}\log
T\\!+\\!d\sqrt{MT}\log(MT/\alpha)\right)\\!+\\!\widetilde{O}\\!\left(\\!\sqrt{T}\frac{(Md)^{3/4}\log^{1/4}(1/\delta)}{\sqrt{\varepsilon}}\log^{1/4}\\!\left(\frac{T}{B\alpha}\\!\right)\\!\right).$

The first term in the above regret bound doesn’t depend on privacy budgets
$\varepsilon,\delta$, and serves as a representative regret bound for
federated LCBs without privacy constraint. The second term is the dominant one
which depends on $\varepsilon,\delta$ and denotes the cost of privacy due to
injected noise.

######  Corollary 6.2.

Setting $B\\!=\\!\sqrt{T/M}$, Algorithm 1 achieves
$\widetilde{O}\left(d\sqrt{MT}+\\!\sqrt{T}\frac{(Md)^{3/4}\log^{1/4}(1/\delta)}{\sqrt{\varepsilon}}\right)$
group regret, with total $\sqrt{MT}$ synchronizations under
$(\varepsilon,\delta)$-silo-level LDP.

Comparisons with related work. First, we avoid privacy leakage and gap in
communication analysis of [DP20] by adopting data-independent synchronization.
This, however, leads to an $O(\sqrt{T})$ communication cost rather than the
reported $O(\log T)$ cost of [DP20]. It remains open to design an data-
adaptive communication schedule with a correct performance analysis (see
Appendix C for more details). We also show that privacy cost scales as
$O(M^{3/4})$ with number of agents $M$, correcting the reported $\sqrt{M}$
scaling of [DP20]. Next, we compare our result with that of a (super) single
agent running for $MT$ rounds under the central model DP (i.e., where central
server is trusted), which serves as a benchmark for our results. As shown in
[SS18, CZ22a], the total regret for such a single agent is
$\widetilde{O}\left(d\sqrt{MT}+\\!\sqrt{MT}\frac{d^{3/4}\log^{1/4}(1/\delta)}{\sqrt{\varepsilon}}\right)$.
Comparing this bound with Corollary 6.2, we observe that the privacy cost of
federated LCBs under silo-level LDP is a multiplicative $M^{1/4}$ factor
higher than a super agent under central DP. This observation motivates us to
consider SDP in the next section.

###  6.2 Federated LCBs under SDP

We now close the above $M^{1/4}$ gap in the privacy cost under silo-level LDP
compared to that achieved by a super single agent (with a truseted central
server). To do so, we consider federated LCBs under SDP, which still enjoys
the nice feature of silo-level LDP that the central server is not trusted.
Thanks to our flexible privacy protocol $\mathcal{P}$, the only change needed
compared to silo-level LDP is the introduction of a shuffler $\mathcal{S}$ to
amplify privacy and adjustment of the privacy noise $\sigma_{0}^{2}$
accordingly.

######  Theorem 6.3 (Performance under SDP via amplification).

Fix batch size $B$ and let $\kappa\\!=\\!1\\!+\\!\log(T/B)$. Let
$\mathcal{P}\\!=\\!(\mathcal{R},\mathcal{S},\mathcal{A})$ be a protocol given
by Algorithm 2. Then, under Assumption 5.1, there exist constants
$C_{1},C_{2}>0$ such that for any
$\varepsilon\\!\leq\\!\frac{\sqrt{\kappa}}{C_{1}T\sqrt{M}}$,
$\delta\\!\leq\\!\frac{\kappa}{C_{2}T}$, Algorithm 1 instantiated with
$\mathcal{P}$ and
$\sigma_{0}^{2}\\!=\\!O\left(\frac{2\kappa\log(1/\delta)\log(\kappa/(\delta
T))\log(M\kappa/\delta)}{\varepsilon^{2}M}\right)$, satisfies
$(\varepsilon,\delta)$-SDP. Moreover, for any $\alpha\in(0,1]$, there exist
choices of $\lambda$ and $\\{\beta_{t,i}\\}_{t,i}$ such that, with a
probability at least $1-\alpha$, it enjoys a group regret

$\displaystyle R_{M}(T)\\!=\\!O\left({dMB}\log
T\\!+\\!d\sqrt{MT}\log(MT/\alpha)\right)\\!+\\!\widetilde{O}\\!\left(\\!d^{3/4}\sqrt{MT}\frac{\log^{3/4}(M\kappa/\delta)}{\sqrt{\varepsilon}}\log^{1/4}\\!\left(\frac{T}{B\alpha}\\!\right)\\!\right).$

######  Corollary 6.4.

Setting $B=\sqrt{T/M}$, Algorithm 1 achieves
$\widetilde{O}\left(d\sqrt{MT}+\\!d^{3/4}\sqrt{MT}\frac{\log^{3/4}(M\kappa/\delta)}{\sqrt{\varepsilon}}\right)$
group regret, with total $\sqrt{MT}$ synchronizations under
$(\varepsilon,\delta)$-SDP.

Corollary 6.4 asserts that privacy cost of federated LCBs under SDP matches
that of a super single agent under central DP (up to a log factor in
$T,M,\delta$).

Comparison with existing SDP analysis. A crucial observation here is that the
above result doesn’t directly follow from existing amplification lemmas. In
particular, prior results on privacy amplification [FMT22, EFMRTT19, CSUZZ19,
BBGN19] show that shuffling the outputs of $M$ $(\varepsilon,\delta)$-LDP
algorithms achieve roughly $1/\sqrt{M}$ factor amplification in privacy for
small $\varepsilon$ – the key to close the aforementioned gap in privacy cost.
However, these amplification results apply _only_ when each mechanism is LDP
_in the standard sense, i.e., they operate on a dataset of size $n=1$_. This
doesn’t hold in our case since the dataset at each silo is a stream of $T$
points. [LR21] adopt group privacy to handle the case of $n>1$, which can
amplify any general DP mechanism but comes at the expense of a large increase
in $\delta$. To avoid this, we prove a _new amplification lemma_ specific to
Gaussian DP mechanisms operating on datasets with size $n\\!>\\!1$. This helps
us achieve the required $1/\sqrt{M}$ amplification in $\varepsilon$ while
keeping the increase in $\delta$ in check. The key idea behind our new lemma
is to directly analyze the sensitivity when creating “clones” as in [FMT22],
but now by accounting for the fact that all $n\\!>\\!1$ points can be
different (see Appendix E for a formal statement of the lemma).

####  6.2.1 SDP guarantee for a wide range of privacy parameters

One limitation of attaining SDP via amplification is that the privacy
guarantee holds only for small values of $\varepsilon,\delta$ (see Theorem
6.3). In this section, we propose an alternative privacy protocol to resolute
this limitation. This new protocol leverages the same binary tree structure as
in Algorithm 2 for releasing and aggregating p-sums, but it employs different
local randomizers and analyzers for computing (noisy) synchronized p-sums of
bias vectors and covariance matrices ($\widetilde{\alpha}_{i_{k}}$ in
Algorithm 2). Specifically, it applies the vector sum mechanism
$\mathcal{P}_{\text{Vec}}$ of [CJMP21], which essentially take $n$ vectors as
inputs and outputs their noisy sum. Here privacy is ensured by injecting
suitable binomial noise to a fixed-point encoding of each vector entry, which
depends on $\varepsilon,\delta$ and $n$.

In our case, one cannot directly aggregate $M$ p-sums using
$\mathcal{P}_{\text{Vec}}$ with $n=M$. This is because each p-sum would then
have a large norm ($O(T)$ at the worst case), which would introduce a large
amount of privacy noise (cf. Theorem 3.2 in [CJMP21]), resulting in worse
utility (regret). Instead, we first expand each p-sum resulting in $O(B)$ data
points (bias vectors and covariance matrices) each with $O(1)$ norm, where $B$
is the size of each batch. Then, we aggregate all $n=O(BM)$ of those data
points using $\mathcal{P}_{\text{Vec}}$ mechanism (one each for bias vectors
and covariance matrices). For example, consider summing bias vectors during
batch $k=6$ and refer back to Fig. 1 for illustration. Here, the p-sum for
each agent is given by $\sum[5,6]=\gamma_{5}+\gamma_{6}$ (see line 6 in
Algorithm 2), the expansion of which results in $2B$ bias vectors ($B$ each
for batch 5 and 6). A noisy sum of $n=2BM$ bias vectors is then computed using
$\mathcal{P}_{\text{Vec}}$. We denote the entire mechanism as
$\mathcal{P}^{\mathcal{T}}_{\text{Vec}}$ – see Algorithm 5 in Appendix E.2 for
pseudo-code and complete description.

Now, the key intuition behind using $\mathcal{P}_{\text{Vec}}$ as a building
block is that it allows us to compute private vector sums under the shuffle
model using nearly the same amount of noise as in the central model. In other
words, it “simulates” the privacy noise introduced in vector summation under
central model using a shuffler. This, in turn, helps us match the regret of a
super single agent under central DP while guaranteeing (strictly stronger)
SDP. Specifically, we have the same order of regret as in Theorem 6.3, but now
it holds for a wide range of privacy budgets $\varepsilon,\delta$ as presented
below formally.

######  Theorem 6.5 (Performance under SDP via vector sum).

Fix batch size $B$ and let $\kappa\\!=\\!1\\!+\\!\log(T/B)$. Let
$\mathcal{P}_{\text{Vec}}^{\mathcal{T}}$ be a privacy protocol given by
Algorithm 5. Then, under Assumption 5.1, there exist parameter choices of
$\mathcal{P}_{\text{Vec}}^{\mathcal{T}}$ such that for any
$\varepsilon\\!\leq\\!60\sqrt{2\kappa\log(2/\delta)}$ and $\delta\\!\leq\\!1$,
Algorithm 1 instantiated with $\mathcal{P}_{\text{Vec}}^{\mathcal{T}}$
satisfies $(\varepsilon,\delta)$-SDP. Moreover, for any $\alpha\in(0,1]$,
there exist choices of $\lambda$ and $\\{\beta_{t,i}\\}_{t,i}$ such that, with
a probability at least $1-\alpha$, it enjoys a group regret

$\displaystyle R_{M}(T)\\!=\\!O\left({dMB}\log
T\\!+\\!d\sqrt{MT}\log(MT/\alpha)\right)\\!+\\!\widetilde{O}\\!\left(\\!d^{3/4}\sqrt{MT}\frac{\log^{3/4}(\kappa
d^{2}/\delta)}{\sqrt{\varepsilon}}\log^{1/4}\\!\left(\frac{T}{B\alpha}\\!\right)\\!\right).$

######  Remark 6.6 (Importance of communicating P-sums).

One of our key techniques behind closing the regret gap under SDP is to
communicate and shuffle _only_ the p-sums rather than prefix sums. With this
we can ensure that each data point (bias vector/covariance matrix)
participates only in at most $\log K$ shuffle mechanisms (rather than in
$O(K)$ mechanisms if we communicate and shuffle prefix-sums). This helps us to
keep the final privacy cost in check after adaptive composition. In other
words, one cannot simply use shuffling to amplify privacy of the proposed
algorithm in [DP20] to close the regret gap (even ignoring its privacy and
communication issues), since it communicates prefix sums at each
synchronization. This again highlights the algorithmic novelty of our privacy
protocols (Algorithms 2 and 5), which could be of independent interest. See
Appendix E for further details.

###  6.3 Key Techniques: Overview

Our first key tool is a generic regret bound for Algorithm 1 under a mild
condition on injected noise. Let $t=kB$, and $N_{t,i},n_{t,i}$ denote total
noise injected up to the $k$-th communication by agent $i$ to covariance
matrices $\sum_{s=1}^{t}x_{s,i}x_{s,i}^{\top}$ and bias vectors
$\sum_{s=1}^{t}x_{s,i}y_{s,i}$, respectively. Moreover, let (i)
$\sum_{i=1}^{M}n_{t,i}$ be a random vector whose entries are independent, mean
zero, sub-Gaussian with variance at most $\sigma_{1}^{2}$, and (ii)
$\sum_{i=1}^{M}N_{t,i}$ be a random symmetric matrix whose entries on and
above the diagonal are independent sub-Gaussian random variables with variance
at most $\sigma_{2}^{2}$. Let $\sigma\\!=\\!\max\\{\sigma_{1},\sigma_{2}\\}$.
Then, we have the following result.

######  Lemma 6.7 (Informal regret bound).

With high probability, the regret of Algorithm 1 satisfies

$\displaystyle\hskip
28.45274pt\\!R_{M}(T)\\!=\\!\widetilde{O}\left(\\!{dMB}+d\sqrt{MT}+\sqrt{\sigma
MT}d^{3/4}\\!\right).$

Armed with the above lemma, one only needs to determine the noise variance
$\sigma^{2}$ under different privacy constraints. For silo-level LDP, we use
concentrated differential privacy [BS16] to obtain a tighter privacy
accounting. In this process, we also utilize the nice properties of the tree-
based mechanism. The final total noise level is
$\sigma^{2}=8M\kappa^{2}\cdot\frac{(\log(2/\delta)+\varepsilon)}{\varepsilon^{2}}$
with $\kappa:=1+\log K$. For SDP, the key idea is to leverage privacy
amplification of $1/\sqrt{M}$ by shuffling. Hence, the noise variance by each
agent is roughly $1/M$ of the noise under LDP. By Lemma 6.7, we thus shave an
$M^{1/4}$ factor from the regret under silo-level LDP. However, as mentioned
before, the key technique to achieve this is our new amplification lemma in
Appendix E. For SDP via vector sum, we utilize the property of
$\mathcal{P}_{\text{Vec}}$ to compute each noisy synchronized p-sum under SDP
using noise level $\widetilde{O}(\kappa/\varepsilon^{2})$ (where we use the
fact that each data point only participates at most $\kappa$ times and
advanced composition). Then, by the binary tree structure again, each private
prefix sum only requires at most $\kappa$ noisy synchronized p-sums. Thus, the
total amount of noise is $\widetilde{O}(\kappa^{2}/\varepsilon^{2})$.

##  7 Simulation Results

We evaluate regret performance of Algorithm 1 under silo-level LDP and SDP,
which we abbreviate as LDP-FedLinUCB and SDP-FedLinUCB, respectively. We fix
confidence level $\alpha\\!=\\!0.01$, batchsize $B\\!=\\!25$ and study
comparative performances under varying privacy budgets $\varepsilon,\delta$.
We plot time-averaged group regret $\text{Reg}_{M}(T)/T$ in Figure 2 by
averaging results over 25 parallel runs. Our simulations are proof-of-concept
only; we do not tune any hyperparameters.

Synthetic bandit instance. We simulate a LCB instance with a parameter
$\theta^{*}$ of dimension $d=10$ and $|\mathcal{K}_{i}|=100$ actions for each
of the $M$ agents. Similar to [VMDK20], we generate $\theta^{*}$ and feature
vectors by sampling a $(d\\!-\\!1)$-dimensional vectors of norm $1/\sqrt{2}$
uniformly at random, and append it with a $1/\sqrt{2}$ entry. Rewards are
corrupted with Gaussian $\mathcal{N}(0,0.25)$ noise.

Real-data bandit instance. We generate bandit instances from Microsoft
Learning to Rank dataset [QL13]. Queries form the contexts $c$ and actions $a$
are the available documents. The dataset contains 10K queries, each with up to
908 judged documents, where the query-document pairs are judged on a 3-point
scale, $\text{rel}(c,a)\in\\{0,1,2\\}$. Each pair $(c,a)$ has a feature vector
$\phi(c,a)$, which is partitioned into title and body features of dimensions
57 and 78, respectively. We first train a lasso regression model on title
features to predict relevances from $\phi$, and take this model as the bandit
parameter $\theta^{*}$ with $d=57$ (similar experiment with body features is
reported in Appendix G). Next, we divide the queries equally into $M\\!=\\!10$
agents and assign corresponding feature vectors to the agents. This way, we
obtain a federated LCB instance with $10$ agents, each with number of actions
$|\mathcal{K}_{i}|\leq 908$.

Observations. In sub-figure (a), we compare performance of LDP-FedLinUCB and
SDP-FedLinUCB (with amplification based privacy protocol $\mathcal{P}$) on
synthetic Gaussian bandit instance with $M\\!=\\!100$ agents under privacy
budget $\delta\\!=\\!0.0001$ and $\varepsilon\\!=\\!0.001$ or $0.0001$. We
observe that regret of SDP-FedLinUCB is less than LDP-FedLinUCB for both
values of $\varepsilon$, which is consistent with our theoretical results.
Here, we only work with small privacy budgets since the privacy guarantee of
Theorem 6.3 holds for $\varepsilon,\delta\\!\ll\\!1$. Instead, in sub-figure
(b), we consider higher privacy budgets as suggested in Theorem 6.5 (e.g.
$\varepsilon\\!=\\!0.2$, $\delta\\!=\\!0.1$) and compare the regret
performance of LDP-FedLinUCB and SDP-FedLinUCB (with vecor-sum based privacy
protocol $\mathcal{P}_{\text{vec}}^{\mathcal{T}}$). As expected, here also we
observe that regret of SDP-FedLinUCB decreases faster than that of LDP-
FedLinUCB.

Next, we benchmark the performance of Algorithm 1 under silo-level LDP (i.e.
LDP-FedLinUCB) against a non-private Federated LCB algorithm with fixed
communication schedule, which we build upon the algorithm of [APS11] and refer
as FedLinUCB. In sub-figure (c), we demonstrate the cost of privacy under
silo-level LDP on real-data bandit instance by varying $\varepsilon$ in the
set $\\{0.2,1,5\\}$ while keeping $\delta$ fixed to 0.1. We observe that
regret of LDP-FedLinUCB decreases and comes closer to that of FedLinUCB as
$\varepsilon$ increases (i.e., level of privacy protection decreases). A
similar regret behavior is noticed under SDP also (postponed to Appendix G).

(a) Synthetic data ($M=100$)

(b) Synthetic data ($M=100$)

(c) Real data ($M=10$)

Figure 2: Comparison of time-average group regret for LDP-FedLinUCB (silo-
level LDP), SDP-FedLinUCB (shuffle model) and FedLinUCB (non-private) under
varying privacy budgets $\varepsilon,\delta$ on (a, b) synthetic Gaussian
bandit instance and (c) bandit instance generated from MSLR-WEB10K Learning to
Rank dataset.

##  8 Concluding Remarks

Silo-level LDP/SDP vs. other privacy notions. It is helpful to compare silo-
level LDP and SDP with other existing privacy notions. In Appendix F.1, we
compare it with the standard local model, central model and shuffle model for
single-agent LCBs. As a by-product, via a simple tweak of Algorithm 1, we also
show how to achieve a slightly stronger privacy guarantee than silo-level LDP
in the sense that now the action selection is also based on private data only.
With this, we can not only protect against colluding among other silos (as in
silo-level LDP), but against colluding among users within the same silo (as in
standard central DP).

Non-unique users. In this theoretical work, we assume that all $MT$ users are
unique. In practice, it is often the case that the same user can participate
in multiple rounds within the same silo or across different silos. For
example, the same patient can have multiple medical tests at the same hospital
or across different types of hospitals. We discuss how to handle the case of
non-unique users in Appendix F.3.

Future work. One immediate future work is to reduce communication costs by
overcoming the challenges in private adaptive communication, see Appendix C.
Another direction could be considering similar cross-silo federated learning
for private RL, especially with linear function approximation (cf. [Zho22].)

##  9 Acknowledgements

XZ is supported in part by NSF CNS-2153220. XZ would like to thank Abhimanyu
Dubey for discussions on the work [DP20]. XZ would also like to thank Andrew
Lowy and Ziyu Liu for insightful discussions on the privacy notion for cross-
silo federated learning. XZ would also thank Vitaly Feldman and Audra McMillan
for the discussion on some subtleties behind “hiding among the clones”.

## References

  * [AB22] Achraf Azize and Debabrota Basu  “When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits”  In _arXiv preprint arXiv:2209.02570_ , 2022
  * [APS11] Yasin Abbasi-Yadkori, Dávid Pál and Csaba Szepesvári  “Improved algorithms for linear stochastic bandits”  In _Advances in neural information processing systems_ 24, 2011
  * [BBGN19] Borja Balle, James Bell, Adrià Gascón and Kobbi Nissim  “The privacy blanket of the shuffle model”  In _Annual International Cryptology Conference_ , 2019, pp. 638–667  Springer
  * [BS16] Mark Bun and Thomas Steinke  “Concentrated differential privacy: Simplifications, extensions, and lower bounds”  In _Theory of Cryptography Conference_ , 2016, pp. 635–658  Springer
  * [CJMP21] Albert Cheu, Matthew Joseph, Jieming Mao and Binghui Peng  “Shuffle private stochastic convex optimization”  In _arXiv preprint arXiv:2106.09805_ , 2021
  * [CSS11] T-H Hubert Chan, Elaine Shi and Dawn Song  “Private and continual release of statistics”  In _ACM Transactions on Information and System Security (TISSEC)_ 14.3 ACM New York, NY, USA, 2011, pp. 1–24
  * [CSUZZ19] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber and Maxim Zhilyaev  “Distributed differential privacy via shuffling”  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , 2019, pp. 375–403  Springer
  * [CZ22] Sayak Ray Chowdhury and Xingyu Zhou  “Distributed Differential Privacy in Multi-Armed Bandits”  In _arXiv preprint arXiv:2206.05772_ , 2022
  * [CZ22a] Sayak Ray Chowdhury and Xingyu Zhou  “Shuffle Private Linear Contextual Bandits”  In _Proceedings of the 39th International Conference on Machine Learning_ PMLR, 2022, pp. 3984–4009
  * [DJW13] John C Duchi, Michael I Jordan and Martin J Wainwright  “Local privacy and statistical minimax rates”  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , 2013, pp. 429–438  IEEE
  * [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi and Guy N Rothblum  “Differential privacy under continual observation”  In _Proceedings of the forty-second ACM symposium on Theory of computing_ , 2010, pp. 715–724
  * [DP20] Abhimanyu Dubey and AlexSandy’ Pentland  “Differentially-private federated linear bandits”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 6003–6014
  * [DPZRT18] Roel Dobbe, Ye Pu, Jingge Zhu, Kannan Ramchandran and Claire Tomlin  “Customized local differential privacy for multi-agent distributed optimization”  In _arXiv preprint arXiv:1806.06035_ , 2018
  * [DR14] Cynthia Dwork and Aaron Roth  “The algorithmic foundations of differential privacy.”  In _Found. Trends Theor. Comput. Sci._ 9.3-4, 2014, pp. 211–407
  * [Dub21] Abhimanyu Dubey  “No-regret algorithms for private gaussian process bandit optimization”  In _International Conference on Artificial Intelligence and Statistics_ , 2021, pp. 2062–2070  PMLR
  * [EFMRTT19] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar and Abhradeep Thakurta  “Amplification by shuffling: From local to central differential privacy via anonymity”  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2019, pp. 2468–2479  SIAM
  * [FMT22] Vitaly Feldman, Audra McMillan and Kunal Talwar  “Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling”  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 954–964  IEEE
  * [GCPP22] Evrard Garcelon, Kamalika Chaudhuri, Vianney Perchet and Matteo Pirotta  “Privacy Amplification via Shuffling for Linear Contextual Bandits”  In _International Conference on Algorithmic Learning Theory_ , 2022, pp. 381–407  PMLR
  * [HGFD22] Osama A Hanna, Antonious M Girgis, Christina Fragouli and Suhas Diggavi  “Differentially Private Stochastic Linear Bandits:(Almost) for Free”  In _arXiv preprint arXiv:2207.03445_ , 2022
  * [HWMG22] Jiafan He, Tianhao Wang, Yifei Min and Quanquan Gu  “A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits”  In _arXiv preprint arXiv:2207.03106_ , 2022
  * [HWYS21] Ruiquan Huang, Weiqiang Wu, Jing Yang and Cong Shen  “Federated linear contextual bandits”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 27057–27068
  * [KMABBBBCCC+21] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode and Rachel Cummings  “Advances and open problems in federated learning”  In _Foundations and Trends® in Machine Learning_ 14.1–2 Now Publishers, Inc., 2021, pp. 1–210
  * [KPRU14] Michael Kearns, Mallesh Pai, Aaron Roth and Jonathan Ullman  “Mechanism design in large games: Incentives and privacy”  In _Proceedings of the 5th conference on Innovations in theoretical computer science_ , 2014, pp. 403–410
  * [LGR22] Andrew Lowy, Ali Ghafelebashi and Meisam Razaviyayn  “Private Non-Convex Federated Learning Without a Trusted Server”  In _arXiv preprint arXiv:2203.06735_ , 2022
  * [LHWS22] Ziyu Liu, Shengyuan Hu, Zhiwei Steven Wu and Virginia Smith  “On Privacy and Personalization in Cross-Silo Federated Learning”  In _arXiv preprint arXiv:2206.07902_ , 2022
  * [LR21] Andrew Lowy and Meisam Razaviyayn  “Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses”  In _arXiv preprint arXiv:2106.09779_ , 2021
  * [LZJ22] Fengjiao Li, Xingyu Zhou and Bo Ji  “Differentially Private Linear Bandits with Partial Distributed Feedback”  In _arXiv preprint arXiv:2207.05827_ , 2022
  * [LZJ23] Fengjiao Li, Xingyu Zhou and Bo Ji  “(Private) Kernelized Bandits with Distributed Biased Feedback”  In _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ 7.1 ACM New York, NY, USA, 2023, pp. 1–47
  * [MT15] Nikita Mishra and Abhradeep Thakurta  “(Nearly) optimal differentially private stochastic multi-arm bandits”  In _Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence_ , 2015, pp. 592–601
  * [QL13] Tao Qin and Tie-Yan Liu  “Introducing LETOR 4.0 Datasets”  In _CoRR_ abs/1306.2597, 2013  URL: http://arxiv.org/abs/1306.2597
  * [RZLS20] Wenbo Ren, Xingyu Zhou, Jia Liu and Ness B Shroff  “Multi-armed bandits with local differential privacy”  In _arXiv preprint arXiv:2007.03121_ , 2020
  * [SS18] Roshan Shariff and Or Sheffet  “Differentially private contextual linear bandits”  In _Advances in Neural Information Processing Systems_ 31, 2018
  * [SS19] Touqir Sajed and Or Sheffet  “An optimal private stochastic-mab algorithm based on optimal private stopping rule”  In _International Conference on Machine Learning_ , 2019, pp. 5579–5588  PMLR
  * [Ste22] Thomas Steinke  “Composition of Differential Privacy & Privacy Amplification by Subsampling”  In _arXiv preprint arXiv:2210.00597_ , 2022
  * [TKMS21] Jay Tenenbaum, Haim Kaplan, Yishay Mansour and Uri Stemmer  “Differentially private multi-armed bandits in the shuffle model”  In _Advances in Neural Information Processing Systems_ 34, 2021
  * [TKMS23] Jay Tenenbaum, Haim Kaplan, Yishay Mansour and Uri Stemmer  “Concurrent Shuffle Differential Privacy Under Continual Observation”  In _arXiv preprint arXiv:2301.12535_ , 2023
  * [Ver18] Roman Vershynin  “High-dimensional probability: An introduction with applications in data science”  Cambridge university press, 2018
  * [VMDK20] Sharan Vaswani, Abbas Mehrabian, Audrey Durand and Branislav Kveton  “Old Dog Learns New Tricks: Randomized UCB for Bandit Problems”  In _International Conference on Artificial Intelligence and Statistics_ , 2020, pp. 1988–1998  PMLR
  * [WHCW20] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen and Liwei Wang  “Distributed bandit learning: How much communication is needed to achieve (near) optimal regret”  In _ICLR_ , 2020
  * [ZCHLW20] Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li and Liwei Wang  “Locally differentially private (contextual) bandits learning”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 12300–12310
  * [Zho22] Xingyu Zhou  “Differentially Private Reinforcement Learning with Linear Function Approximation”  In _Proc. ACM Meas. Anal. Comput. Syst._ 6.1 New York, NY, USA: Association for Computing Machinery, 2022
  * [ZT21] Xingyu Zhou and Jian Tan  “Local Differential Privacy for Bayesian Optimization”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 35.12, 2021, pp. 11152–11159

##  Appendix A More Discussions on Gaps in SOTA

In this section, we provide more details on the current gaps in [DP20],
especially on privacy violation and communication cost. It turns out that both
gaps come from the fact that an adaptive communication schedule is employed in
[DP20].

###  A.1 More on violation of silo-level LDP

As shown in the main paper, Algorithm 1 in [DP20] does not satisfy silo-level
LDP. To give a more concrete illustration of privacy leakage, we now specify
the form of $f$333There is some minor issue in the form of $f$ in [DP20]. The
correct one is given by our restatement of their Algorithm 1, see line 9 in
Algorithm 3., local data $X_{i}$ and synchronized data $Z$ in (1) according to
[DP20]. In particular, a communication is triggered at round $t$ if for any
silo $i$, it holds that

$\displaystyle\\!(t\\!-\\!t^{\prime})\log\left[\frac{\det\left(Z\\!+\\!\sum_{s=t^{\prime}+1}^{t}x_{s,i}x_{s,i}^{\top}\\!+\\!\lambda_{\min}I\right)}{\det\left(Z\\!+\\!\lambda_{\min}I\right)}\right]\\!>\\!D,\\!$
(2)

where $t^{\prime}$ is the latest synchronization time before $t$, $Z$ is all
synchronized (private) covariance matrices up to time $t^{\prime}$,
$\lambda_{\min}>0$ is some regularization constant (which depends on privacy
budgets $\varepsilon,\delta$) and $D>0$ is some suitable threshold (which
depends on number of silos $M$).

With the above explicit form in hand, we can give a more concrete discussion
of Example 4.1. A communication is triggered at round $t=1$ if
$\det\left(x_{1,m}x_{1,m}^{\top}\\!+\\!\lambda_{\min}I\right)>\det\left(\lambda_{\min}I\right)e^{D}$
holds for any silo $m$. This implies that $(\lambda_{\min}+\left\lVert
x_{1,m}\right\rVert^{2})\lambda_{\min}^{d-1}>e^{D}\lambda_{\min}^{d}$, which,
in turn, yields $\left\lVert
x_{1,m}\right\rVert^{2}>\lambda_{\min}(e^{D}-1)=:C$. Now, if $\left\lVert
x_{1,j}\right\rVert^{2}\leq C$, then silo $j$ immediately knows that
$\left\lVert x_{1,i}\right\rVert^{2}>C$, where $C$ is a known constant. Since
$x_{1,i}$ contains the context information of the user (Alice), this norm
condition could immediately reveal that some specific features in the context
vector are active (e.g., Alice has both diabetes and heart disease), thus
leaking Alice’s private and sensitive information to silo $j$.

######  Remark A.1.

The above result has two implications: (i) the current proof strategy for Fed-
DP guarantee in [DP20] does not hold since it essentially relies on the post-
processing of DP through silo-level LDP; (ii) Fed-DP could fail to handle
reasonable adversary model in cross-silo federated LCBs. That is, even if
Algorithm 1 in [DP20] satisfies Fed-DP, it still cannot protect Alice’s
information from being inferred by a malicious silo (which is a typical
adversary model in cross-silo FL). Thus, we believe that silo-level LDP is a
more proper privacy notion for cross-silo federated LCBs.

###  A.2 More on violation of Fed-DP

As shown in the main paper, Algorithm 1 in [DP20] also does not satisfy its
weaker notion of Fed-DP. To give a more concrete illustration, recall Example
4.1 and let us define $m_{i,j}$ as the message/data sent from silo $i$ to silo
$j$ after round $t=1$. Suppose in the case of Alice, there is no
synchronization and hence $m_{i,j}=0$. On the other hand, in the case of Tracy
(i.e., the first user at silo $i$ changes from Alice to Tracy), suppose
synchronization is triggered by silo $i$ via rule (1) due to Tracy’s data.
Then, according to [DP20], $m_{i,j}=x_{1,i}y_{1,i}+\mathcal{N}$ (consider bias
vector here), where $\mathcal{N}$ is the injected noise when silo $i$ sends
out its data. Now, based on the requirement of Fed-DP, the recommended action
at silo $j$ in round $t=2$ needs to be “similar” or “indistinguishable” in
probability under the change from Alice to Tracy. Note that silo $j$ chooses
its action at round $t=2$ based on its local data (which is unchanged) and
$m_{i,j}$, via _deterministic_ selection rule (i.e., LinUCB) in Algorithm 1 of
[DP20]. Thus, Fed-DP essentially requires $m_{i,j}$ to be close in probability
when Alice changes to Tracy, which is definitely not the case (i.e., $0$ vs.
$x_{1,i}y_{1,i}+\mathcal{N}$). Thus, Algorithm 1 in [DP20] also fails Fed-DP.

######  Remark A.2.

One can also think from the following perspective: the non-private data-
dependent sync rule (i.e., (2)) in [DP20] impacts the communicated
messages/data as well, which cannot be made private by injecting noise when
sending out data. To rescue, a possible approach is to use _private (noisy)_
data in rule (2) when determining synchronization (while still injecting noise
when sending out data). As a result, whether there exists a synchronization
would be “indistinguishable” under Alice or Tracy and hence $m_{i,j}$ now
would be similar. However, this approach still suffers the gap in
communication cost analysis (see below) and moreover it will incur new
challenges in regret analysis, see Appendix C for a detailed discussion on
this approach.

###  A.3 More on communication cost analysis

The current analysis in [DP20] (cf. Proposition 5) for communication cost
(i.e., how many rounds of communication within $T$) essentially follows the
approach in the non-private work [WHCW20] (cf. proof of Theorem 4). However,
due to additional privacy noise injected into the communicated data, one key
step of the approach in [WHCW20] fails in the private case. In the following,
we first point out the issue using notations in [DP20].

The key issue in its current proof of Proposition 5 in [DP20] is that

$\displaystyle\log\frac{\det(\mathbf{S}_{i,t+n^{\prime}})}{\det(\mathbf{S}_{i,t})}>\frac{D}{n^{\prime}}$
(3)

which appears right above Eq. 4 in [DP20] does not hold. More specifically,
$[t,t+n^{\prime}]$ is the $i$-th interval between two communication steps and
$\mathbf{S}_{i,t},\mathbf{S}_{i,t+n^{\prime}}$ are corresponding synchronized
private matrices. At the time $t+n^{\prime}$, we know (2) is satisfied by some
silo (say $j\in[M]$), since there is a new synchronization. In the non-private
case, $\mathbf{S}_{i,t+n^{\prime}}$ simply includes some additional local
covariance matrices from silos other than $j$, which are positive semi-
definite (PSD). As a result, (3) holds. However, in the private case,
$\mathbf{S}_{i,t+n^{\prime}}$ includes the _private_ messages from silos other
than $j$, which may not be positive semi-definite (PSD), since there are some
new covariance matrices as well as _new Gaussian privacy noise_ (which could
be negative definite). Thus, (3) may not hold anymore.

##  Appendix B A Generic Regret Analysis for Algorithm 1

In this section, we formally establish Lemma 6.7, i.e., our generic regret
bound of Algorithm 1 under sub-Gaussian noise condition. To this end, let us
first recall the following notations. Fix $B,T\in\mathbb{N}$, we let $K=T/B$
be the total number of communication steps. For all $i\in[M]$ and all $t=kB$,
$k\in[K]$, we let
$N_{t,i}=\widetilde{W}_{t,i}-\sum_{s=1}^{t}x_{s,i}x_{s,i}^{\top}$ and
$n_{t,i}=\widetilde{U}_{t,i}-\sum_{s=1}^{t}x_{s,i}y_{s,i}$ be the cumulative
injected noise up to the $k$-th communication by agent $i$. We further let
$H_{t}:=\lambda I_{d}+\sum_{i\in[M]}N_{t,i}$ and
$h_{t}:=\sum_{i\in[M]}n_{t,i}$.

######  Assumption B.1 (Regularity).

Fix any $\alpha\in(0,1]$, with probability at least $1-\alpha$, we have
$H_{t}$ is positive definite and there exist constants
$\lambda_{\text{max}},\lambda_{\text{min}}$ and $\nu$ depending on $\alpha$
such that for all $t=kB$, $k\in[K]$

$\displaystyle\left\lVert H_{t}\right\rVert\leq\lambda_{\max},\quad\left\lVert
H_{t}^{-1}\right\rVert\leq 1/\lambda_{\min},\quad\left\lVert
h_{t}\right\rVert_{H_{t}^{-1}}\leq\nu.$

With the above regularity assumption and the boundedness in Assumption 5.1, we
fist establish the following general regret bound of Algorithm 1, which can be
viewed as a direct generalization of the results in [SS18, CZ22a] to the
federated case.

######  Lemma B.2.

Let Assumptions B.1 and 5.1 hold. Fix any $\alpha\in(0,1]$, there exist
choices of $\lambda$ and $\\{\beta_{t,i}\\}_{t\in[T],i\in[M]}$ such that, with
probability at least $1-\alpha$, the group regret of Algorithm 1 satisfies

$\displaystyle\text{Reg}_{M}(T)=O\left(\beta_{T}\sqrt{dMT\log\left(1+\frac{MT}{d\lambda_{\min}}\right)}\right)+O\left(M\cdot
B\cdot{d}\log\left(1+\frac{MT}{d\lambda_{\min}}\right)\right),$

where
$\beta_{T}:=\sqrt{2\log\left(\frac{2}{\alpha}\right)+d\log\left(1+\frac{MT}{d\lambda_{\min}}\right)}+\sqrt{\lambda_{\max}}+\nu.$

Lemma 6.7 is a corollary of the above result, which holds by bounding
$\lambda_{\max},\lambda_{\min},\nu$ under sub-Gaussian privacy noise.

######  Assumption B.3 (sub-Gaussian private noise).

There exist constants $\widetilde{\sigma}_{1}$ and $\widetilde{\sigma}_{2}$
such that for all $t=kB$, $k\in[K]$: (i) $\sum_{i=1}^{M}n_{t,i}$ is a random
vector whose entries are independent, mean zero, sub-Gaussian with variance at
most $\widetilde{\sigma}_{1}^{2}$, and (ii) $\sum_{i=1}^{M}N_{t,i}$ is a
random symmetric matrix whose entries on and above the diagonal are
independent sub-Gaussian random variables with variance at most
$\widetilde{\sigma}_{2}^{2}$. Let
$\sigma^{2}\\!=\\!\max\\{\widetilde{\sigma}_{1}^{2},\widetilde{\sigma}_{2}^{2}\\}$.

Now, we are ready to state the formal version of Lemma 6.7 as follows.

######  Lemma B.4 (Formal statement of Lemma 6.7).

Let Assumptions B.3 and 5.1 hold. Fix time horizon $T\in\mathbb{N}$, batch
size $B\in[T]$, confidence level $\alpha\in(0,1]$. Set
$\lambda=\Theta(\max\\{1,\sigma(\sqrt{d}+\sqrt{\log(T/(B\alpha))}\\})$ and
$\beta_{t,i}=\sqrt{2\log\left(\frac{2}{\alpha}\right)+d\log\left(1+\frac{Mt}{d\lambda}\right)}+\sqrt{\lambda}$
for all $i\in[M]$. Then, Algorithm 1 achieves group regret

$\displaystyle\text{Reg}_{M}(T)=O\left({dMB}\log
T+d\sqrt{MT}\log(MT/\alpha)\right)+O\left(\sqrt{\sigma
MT\log(MT)}d^{3/4}\log^{1/4}(T/(B\alpha))\right)$

with probability at least $1-\alpha$.

###  B.1 Proofs

###### Proof of Lemma B.2.

We divide the proof into the following six steps. Let $\mathcal{E}$ be the
event given in Assumption B.1, which holds with probability at least
$1-\alpha$ under Assumption B.1. In the following, we condition on the event
$\mathcal{E}$.

Step 1: Concentration. In this step, we will show that with high probability,
$\left\lVert\theta^{*}-\widehat{\theta}_{t,i}\right\rVert_{V_{t,i}}\leq\beta_{t,i}$
for all $i\in[M]$. Fix an agent $i\in[M]$ and $t\in[T]$, let $t_{\text{last}}$
be the latest communication round of all agents before $t$. By the update
rule, we have

$\displaystyle\widehat{\theta}_{t,i}$
$\displaystyle=V_{t,i}^{-1}(\widetilde{U}_{\text{syn}}+U_{i})$
$\displaystyle=V_{t,i}^{-1}\left(\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}y_{s,j}+\sum_{j=1}^{M}n_{t_{\text{last}},j}+\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}y_{s,i}\right)$
$\displaystyle=\left(\lambda
I+\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}x_{s,j}^{\top}+\sum_{j=1}^{M}N_{t_{\text{last}},j}+\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}x_{s,i}^{\top}\right)^{-1}\left(\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}y_{s,j}+\sum_{j=1}^{M}n_{t_{\text{last}},j}+\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}y_{s,i}\right).$

By the linear reward function $y_{s,j}=\langle
x_{s,j},\theta^{*}\rangle+\eta_{s,j}$ for all $j\in[M]$ and elementary
algebra, we have

$\displaystyle\theta^{*}-\widehat{\theta}_{t,i}=V_{t,i}^{-1}\left(H_{t_{\text{last}}}\theta^{*}-\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}\eta_{s,j}-\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}\eta_{s,i}-h_{t_{\text{last}}}\right),$

where we recall that $H_{t_{\text{last}}}=\lambda
I+\sum_{j=1}^{M}N_{t_{\text{last}},j}$ and
$h_{t_{\text{last}}}=\sum_{j=1}^{M}n_{t_{\text{last}},j}$.

Thus, multiplying both sides by $V_{t,i}^{1/2}$, yields

$\displaystyle\left\lVert\theta^{*}-\widehat{\theta}_{t,i}\right\rVert_{V_{t,i}}$
$\displaystyle\leq\left\lVert\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}\eta_{s,j}+\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}\eta_{s,i}\right\rVert_{V_{t,i}^{-1}}+\left\lVert
H_{t_{\text{last}}}\theta^{*}\right\rVert_{V_{t,i}^{-1}}+\left\lVert
h_{t_{\text{last}}}\right\rVert_{V_{t,i}^{-1}}$
$\displaystyle\mathop{\leq}\limits^{(a)}\left\lVert\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}\eta_{s,j}+\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}\eta_{s,i}\right\rVert_{(G_{t,i}+\lambda_{\text{min}}I)^{-1}}+\left\lVert\theta^{*}\right\rVert_{H_{t_{\text{last}}}}+\left\lVert
h_{t_{\text{last}}}\right\rVert_{H_{t_{\text{last}}}^{-1}}$
$\displaystyle\mathop{\leq}\limits^{(b)}\left\lVert\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}\eta_{s,j}+\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}\eta_{s,i}\right\rVert_{(G_{t,i}+\lambda_{\text{min}}I)^{-1}}+\sqrt{\lambda_{\text{max}}}+\nu$

where (a) holds by $V_{t,i}\succeq H_{t_{\text{last}}}$ and $V_{t,i}\succeq
G_{t,i}+\lambda_{\text{min}}I$ with
$G_{t,i}:=\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}x_{s,j}^{\top}+\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}x_{s,i}^{\top}$
(i.e., non-private Gram matrix) under event $\mathcal{E}$; (b) holds by the
boundedness of $\theta^{*}$ and event $\mathcal{E}$.

For the remaining first term, we can use self-normalized inequality (cf.
Theorem 1 in [APS11]) with a proper filtration444In particular, by the i.i.d
noise assumption across time and agents, one can simply construct the
filtration sequentially across agents and rounds, which enlarges the single-
agent filtration by a factor of $M$.. In particular, we have for any
$\alpha\in(0,1]$, with probability at least $1-\alpha$, for all $t\in[T]$

$\displaystyle\left\lVert\sum_{j=1}^{M}\sum_{s=1}^{t_{\text{last}}}x_{s,j}\eta_{s,j}+\sum_{s=t_{\text{last}}+1}^{t-1}x_{s,i}\eta_{s,i}\right\rVert_{(G_{t,i}+\lambda_{\text{min}}I)^{-1}}\leq\sqrt{2\log\left(\frac{1}{\alpha}\right)+\log\left(\frac{\det(G_{t,i}+\lambda_{\min}I)}{\det(\lambda_{\min}I)}\right)}.$

Now, using the trace-determinant lemma (cf. Lemma 10 in [APS11]) and the
boundedness condition on $\left\lVert x_{s,j}\right\rVert$ for all $s\in[T]$
and $j\in[M]$, we have

$\displaystyle\det(G_{t,i}+\lambda_{\min}I)\leq\left(\lambda_{\min}+\frac{Mt}{d}\right)^{d}.$

Putting everything together, we have with probability at least $1-2\alpha$,
for all $i\in[M]$ and all $t\in[T]$,
$\left\lVert\theta^{*}-\widehat{\theta}_{m}\right\rVert_{V_{t,i}}\leq\beta_{t,i}=\beta_{t}$,
where

$\displaystyle\beta_{t}:=\sqrt{2\log\left(\frac{1}{\alpha}\right)+d\log\left(1+\frac{Mt}{d\lambda_{\min}}\right)}+\sqrt{\lambda_{\max}}+\nu.$
(4)

Step 2: Per-step regret. With the above concentration result, based on our UCB
policy for choosing the action, we have the classic bound on the per-step
regret $r_{t,i}$, that is, with probability at least $1-2\alpha$

$\displaystyle r_{t,i}$
$\displaystyle=\langle\theta^{*},x_{t,i}^{*}\rangle-\langle\theta^{*},x_{t,i}\rangle$
$\displaystyle\mathop{=}\limits^{(a)}\langle\theta^{*},x_{t,i}^{*}\rangle-\text{UCB}_{t,i}(x_{t,i}^{*})+\text{UCB}_{t,i}(x_{t,i}^{*})-\text{UCB}_{t,i}(x_{t,i})+\text{UCB}_{t,i}(x_{t,i})-\langle\theta^{*},x_{t,i}\rangle$
$\displaystyle\mathop{\leq}\limits^{(b)}0+0+2\beta_{t,i}\left\lVert
x_{t,i}\right\rVert_{V_{t,i}^{-1}}\leq 2\beta_{T}\left\lVert
x_{t,i}\right\rVert_{V_{t,i}^{-1}}$

where in (a), we let
$\text{UCB}_{t,i}(x):=\langle\widehat{\theta}_{t,i},x\rangle+\beta_{t,i}\left\lVert
x\right\rVert_{V_{t,i}^{-1}}$; (b) holds by the optimistic fact of UCB (from
the concentration), greedy action selection, and the concentration result
again.

Step 3: Regret decomposition by good and bad epochs. In Algorithm 1, at the
end of each synchronization time $t=kB$ for $k\in[K]$, all the agents will
communicate with the server by uploading private statistics and downloading
the aggregated ones from the server. We then divide time horizon $T$ into
epochs by the communication (sync) rounds. In particular, the $k$-th epoch
contains rounds between $(t_{k-1},t_{k}]$, where $t_{k}=kB$ is the $k$-th sync
round. We define
$V_{k}:=\lambda_{\text{min}}I+\sum_{i=1}^{M}\sum_{t=1}^{t_{k}}x_{t,i}x_{t,i}^{\top}$,
i.e., all the data at the end of the $k$-th communication plus a regularizer.
Then, we say that the $k$-th epoch is a “good” epoch if
$\frac{\det(V_{k})}{\det(V_{k-1})}\leq 2$; otherwise it is a “bad” epoch.
Thus, we can divide the group regret into two terms:

$\text{Reg}_{M}(T)=\sum_{i\in[M]}\sum_{t\in\text{good
epochs}}r_{t,i}+\sum_{i\in[M]}\sum_{t\in\text{bad epochs}}r_{t,i}.$

Step 4: Bound the regret in good epochs. To this end, we introduce an
_imaginary_ single agent that pulls all the $MT$ actions in the following
order:
$x_{1,1,},x_{1,2},\ldots,x_{1,M},x_{2,1},\ldots,x_{2,M},\ldots,x_{T,1},\ldots,x_{T,M}$.
We define a corresponding _imaginary_ design matrix
$\bar{V}_{t,i}=\lambda_{\text{min}}I+\sum_{p<t,q\in[M]}x_{p,q}x_{p,q}^{\top}+\sum_{p=t,q<i}x_{p,q}x_{p,q}^{\top}$,
i.e., the design matrix right _before_ $x_{t,i}$. The key reason behind this
construction is that one can now use the standard result (i.e., the elliptical
potential lemma (cf. Lemma 11 in [APS11])) to bound the summation of bonus
terms, i.e., $\sum_{t,i}\left\lVert x_{t,i}\right\rVert_{\bar{V}_{t,i}^{-1}}$.

Suppose that $t\in[T]$ is within the $k$-th epoch. One key property we will
use is that for all $i$, $V_{k}\succeq\bar{V}_{t,i}$ and
$G_{t,i}+\lambda_{\min}I\succeq V_{k-1}$, which simply holds by their
definitions. This property enables us to see that for any $t\in\text{good
epochs}$, $\det(\bar{V}_{t,i})/\det(G_{t,i}+\lambda_{\min}I)\leq 2$. This is
important since by the standard “determinant trick”, we have

$\displaystyle\left\lVert
x_{t,i}\right\rVert_{(G_{t,i}+\lambda_{\min}I)^{-1}}\leq\sqrt{2}\left\lVert
x_{t,i}\right\rVert_{\bar{V}_{t,i}^{-1}}.$ (5)

In particular, this follows from Lemma 12 in [APS11], that is, for two
positive definite matrices $A,B\in\mathbb{R}^{d\times d}$ satisfying $A\succeq
B$, then for any $x\in\mathbb{R}^{d}$, $\left\lVert
x\right\rVert_{A}\leq\left\lVert
x\right\rVert_{B}\cdot\sqrt{\det(A)/\det(B)}$. Note that here we also use
$\det(A)=1/\det(A^{-1})$. Hence, we can bound the regret in good epochs as
follows.

$\displaystyle\sum_{i\in[M]}\sum_{t\in\text{good epochs}}r_{t,i}$
$\displaystyle\mathop{\leq}\limits^{(a)}\sum_{i\in[M]}\sum_{t\in\text{good
epochs}}\min\\{2\beta_{T}\left\lVert x_{t,i}\right\rVert_{V_{t,i}^{-1}},1\\}$
$\displaystyle\mathop{\leq}\limits^{(b)}\sum_{i\in[M]}\sum_{t\in\text{good
epochs}}\min\\{2\beta_{T}\left\lVert
x_{t,i}\right\rVert_{(G_{t,i}+\lambda_{\min}I)^{-1}},1\\}$
$\displaystyle\mathop{\leq}\limits^{(c)}\sum_{i\in[M]}\sum_{t\in\text{good
epochs}}\min\\{2\sqrt{2}\beta_{T}\left\lVert
x_{t,i}\right\rVert_{\bar{V}_{t,i}^{-1}},1\\}$
$\displaystyle\mathop{\leq}\limits^{(d)}\sum_{i\in[M]}\sum_{t\in\text{good
epochs}}2\sqrt{2}\beta_{T}\min\\{\left\lVert
x_{t,i}\right\rVert_{\bar{V}_{t,i}^{-1}},1\\}$
$\displaystyle\leq\sum_{i\in[M]}\sum_{t\in[T]}2\sqrt{2}\beta_{T}\min\\{\left\lVert
x_{t,i}\right\rVert_{\bar{V}_{t,i}^{-1}},1\\}$
$\displaystyle\mathop{\leq}\limits^{(e)}O\left(\beta_{T}\sqrt{dMT\log\left(1+\frac{MT}{d\lambda_{\min}}\right)}\right),$
(6)

where (a) holds by the per-step regret bound in Step 2 and the boundedness of
reward; (b) follows from the fact that $V_{t,i}\succeq
G_{t,i}+\lambda_{\text{min}}I$ under event $\mathcal{E}$; (c) holds by (5)
when $t$ is in good epochs; (d) is true since $\beta_{T}\geq 1$; (e) holds by
the elliptical potential lemma (cf. Lemma 11 in [APS11]).

Step 5: Bound the regret in bad epochs. Let $T_{\text{bad}}$ be the total
number of rounds in all bad epochs. Thus, the total number of bad rounds
across _all_ agents are $M\cdot T_{\text{bad}}$. As a result, the cumulative
group regret in all these bad rounds are upper bounded by $M\cdot
T_{\text{bad}}$ due to the to the boundedness of reward.

We are left to bound $T_{\text{bad}}$. All we need is to bound the
$N_{\text{bad}}$ – total number of bad epochs. Then, we have
$T_{\text{bad}}=N_{\text{bad}}\cdot B$, where $B$ is the fixed batch size. To
this end, recall that $K=T/B$ and define
${\Psi}:=\\{k\in[K]:\log\det(V_{k})-\log\det(V_{k-1})>\log 2\\}$, i.e.,
$N_{\text{bad}}=|{\Psi}|$. Thus, we have

$\displaystyle\log
2\cdot|{\Psi}|\leq\sum_{k\in{\Psi}}\log\det(V_{k})-\log\det(V_{k-1})\leq\sum_{k\in[K]}\log\det(V_{k})-\log\det(V_{k-1})\leq
d\log\left(1+\frac{MT}{d\lambda_{\min}}\right)$

Hence, we have $N_{\text{bad}}=|{\Psi}|\leq\frac{d}{\log
2}\log\left(1+\frac{MT}{d\lambda_{\min}}\right)$. Thus we can bound the regret
in bad epochs as follows.

$\displaystyle\sum_{i\in[M]}\sum_{t\in\text{bad epochs}}r_{t,i}$
$\displaystyle\leq M\cdot T_{\text{bad}}=M\cdot B\cdot N_{\text{bad}}\leq
M\cdot B\cdot\frac{d}{\log 2}\log\left(1+\frac{MT}{d\lambda_{\min}}\right).$
(7)

Step 6: Putting everything together. Now, we substitute the total regret in
good epochs given by (B.1) and total regret in bad epochs given by (7) into
the total regret decomposition in Step 3, yields the final cumulative group
regret

$\displaystyle\text{Reg}_{M}(T)=O\left(\beta_{T}\sqrt{dMT\log\left(1+\frac{MT}{d\lambda_{\min}}\right)}\right)+O\left(M\cdot
B\cdot{d}\log\left(1+\frac{MT}{d\lambda_{\min}}\right)\right),$

where
$\beta_{T}:=\sqrt{2\log\left(\frac{1}{\alpha}\right)+d\log\left(1+\frac{MT}{d\lambda_{\min}}\right)}+\sqrt{\lambda_{\max}}+\nu$.
Finally, taking a union bound, we have the required result. ∎

Now, we turn to the proof of Lemma B.4, which is an application of Lemma B.2
we just proved.

###### Proof of Lemma B.4.

To prove the result, thanks to Lemma B.2, we only need to determine the three
constants $\lambda_{\max},\lambda_{\min}$ and $\nu$ under the sub-Gaussian
private noise assumption in Assumption B.3. To this end, we resort to
concentration bounds for sub-Gaussian random vector and random matrix.

To start with, under (i) in Assumption B.3, by the concentration bound for the
norm of a vector containing sub-Gaussian entries (cf. Theorem 3.1.1 in
[Ver18]) and a union bound over all communication rounds, we have for all
$t=kB$ where $k=[T/B]$ and any $\alpha\in(0,1]$, with probability at least
$1-\alpha/2$, for some absolute constant $c_{1}$,

$\displaystyle\left\lVert\sum_{i=1}^{M}n_{t,i}\right\rVert=\left\lVert
h_{t}\right\rVert\leq\Sigma_{n}:=c_{1}\cdot\widetilde{\sigma}_{1}\cdot(\sqrt{d}+\sqrt{\log(T/(\alpha
B)}).$

By (ii) in Assumption B.3, the concentration bound for the norm of a sub-
Gaussian symmetric random matrix (cf. Corollary 4.4.8 in [Ver18]) and a union
bound over all communication rounds, we have for all $t=kB$ where $k=[T/B]$
and any $\alpha\in(0,1]$, with probability at least $1-\alpha/2$,

$\displaystyle\left\lVert\sum_{i=1}^{M}N_{t,i}\right\rVert\leq\Sigma_{N}:=c_{2}\cdot\widetilde{\sigma}_{2}\cdot(\sqrt{d}+\sqrt{\log(T/(\alpha
B)})$

for some absolute constant $c_{2}$. Thus, if we choose $\lambda=2\Sigma_{N}$,
we have $\left\lVert H_{t}\right\rVert=\left\lVert\lambda
I_{d}+\sum_{i=1}^{M}N_{t,i}\right\rVert\leq 3\Sigma_{N}$, i.e.,
$\lambda_{\max}=3\Sigma_{N}$, and $\lambda_{\min}=\Sigma_{N}$. Finally, to
determine $\nu$, we note that

$\displaystyle\left\lVert
h_{t}\right\rVert_{H_{t}^{-1}}\leq\frac{1}{\sqrt{\lambda_{\min}}}\left\lVert
h_{t}\right\rVert\leq c\cdot\left(\sigma\cdot(\sqrt{d}+\sqrt{\log(T/(\alpha
B)})\right)^{1/2}:=\nu,$

where $\sigma=\max\\{\widetilde{\sigma}_{1},\widetilde{\sigma}_{2}\\}$. The
final regret bound is obtained by plugging the three values into the result
given by Lemma B.2. ∎

##  Appendix C Discussion on Private Adaptive Communication

In the main paper and Appendix A, we have pointed out that the gap in privacy
guarantee of Algorithm 1 in [DP20] is that its adaptive communication schedule
leads to privacy leakage due to its dependence on non-private data. As
mentioned in Remark A.1, one possible approach is to use private data to
determine the sync in (2). This will resolve the privacy issue. However, the
same issue in communication cost still remains (due to privacy noise), and
hence $O(\log T)$ communication does not hold. Moreover, this new approach
will also lead to new challenges in regret analysis, when compared with its
current one in [DP20] and the standard one in [WHCW20].

To better illustrate the new challenges, let us restate Algorithm 1 in [DP20]
using our notations and first focus on how to establish the regret based on
its current adaptive schedule (which has the issue of privacy leakage). After
we have a better understanding of the idea, we will see how new challenges
come up when one uses private data for an adaptive schedule.

Algorithm 3 Restatement of Algorithm 1 in [DP20]

1: Parameters: Adaptive communication parameter $D$, regularization
$\lambda>0$, confidence radii $\\{\beta_{t,i}\\}_{t\in[T],i\in[M]}$, feature
map $\phi_{i}:\mathcal{C}_{i}\times\mathcal{K}_{i}\to\mathbb{R}^{d}$, privacy
budgets $\varepsilon>0,\delta\in[0,1]$.

2: Initialize: For all $i\in[M]$, $W_{i}=0,U_{i}=0$, Privatizer with
$\varepsilon,\delta$, $\widetilde{W}_{\text{syn}}=0$,
$\widetilde{U}_{\text{syn}}=0$,

3: for $t\\!=\\!1,\ldots,T$ do

4: for each agent $i=1,\ldots,M$ do

5: $V_{t,i}=\lambda I+\widetilde{W}_{\text{syn}}+W_{i}$,
$\widehat{\theta}_{t,i}=V_{t,i}^{-1}(\widetilde{U}_{\text{syn}}+U_{i})$

6: Play arm
$a_{t,i}\\!=\\!\mathop{\mathrm{argmax}}_{a\in\mathcal{K}_{i}}\langle\phi_{i}(c_{t,i},a),\widehat{\theta}_{t,i}\rangle+\beta_{t,i}\left\lVert\phi_{i}(c_{t,i},a)\right\rVert_{V_{t,i}^{-1}}$
and set $x_{t,i}=\phi_{i}(c_{t,i},a_{t,i})$

7: Observe reward $y_{t,i}$

8: Update $W_{i}=W_{i}+x_{t,i}x_{t,i}^{\top}$, $U_{i}=U_{i}+x_{t,i}y_{t,i}$

9: if
$\log\det({V}_{t,i}+x_{t,i}x_{t,i}^{\top})-\log\det(V_{\text{last}})>\frac{D}{t-t_{\text{last}}}$
then

10: Send a signal to the server to start a synchronization round.

11: end if

12: if a synchronization is started then

13: Send $W_{i}$ and $U_{i}$ to Privatizer

14: Privatizer sends private cumulative statistics
$\widetilde{W}_{t,i},\widetilde{U}_{t,i}$ to server

15: Server aggregates
$\widetilde{W}_{\text{syn}}=\widetilde{W}_{\text{syn}}+\sum_{j=1}^{M}\widetilde{W}_{t,j}$
and
$\widetilde{U}_{\text{syn}}=\widetilde{U}_{\text{syn}}+\sum_{j=1}^{M}\widetilde{U}_{t,j}$

16: Receive $\widetilde{W}_{\text{syn}}$ and $\widetilde{U}_{\text{syn}}$ from
the server

17: Reset $W_{i}=0$, $U_{i}=0$, $t_{\text{last}}=t$ and
$V_{\text{last}}=\lambda I+\widetilde{W}_{syn}$

18: end if

19: end for

20: end for

As shown in Algorithm 3, the key difference compared with our fixed-batch
schedule is highlighted in color. Note that we only focus on silo-level LDP
and use Privatizer to represent a general protocol that can privatize the
communicated data (e.g., $\mathcal{P}$ or the standard tree-based algorithm in
[DP20]).

###  C.1 Regret Analysis under Non-private Adaptive Schedule

In this section, we demonstrate the key step in establishing the regret with
the non-private adaptive communication schedule in Algorithm 3 (i.e., line 9).
It turns out that the regret analysis is very similar to our proof for Lemma
B.2 for the fixed batch case, in that the only key difference lies in Step 5
when bounding the regret in bad epochs555There is another subtle but important
difference, which lies in the construction of filtration that is required to
apply the standard self-normalized inequality to establish the concentration
result. We believe that one cannot directly use the standard filtration (e.g.,
[APS11]) in the adaptive case, and hence more care is indeed required.. The
main idea behind adaptive communication is: _whenever the accumulated local
regret at any agent exceeds a threshold, then synchronization is required to
keep the data homogeneous among agents._ This idea is directly reflected in
the following analysis.

Bound the regret in bad epochs (adaptive communication case). Let’s consider
an arbitrary bad epoch $k$, i.e., $(t_{k-1},t_{k}]$, where $t_{k}$ is the
round for the $k$-th communication. For all $i$, we want to bound the total
regret between $(t_{k-1},t_{k}]$, denoted by $R_{i}^{k}$. That is, the local
regret between any two communications (in the bad epoch) will not be too
large. For now, suppose we already have such a bound $U$ (which will be
achieved by adaptive communication later), i.e., $R_{i}^{k}\leq U$ for all
$i,k$, we can easily bound the total regret in bad epochs. To see this, recall
that ${\Psi}:=\\{k\in[K]:\log\det(V_{k})-\log\det(V_{k-1})>\log 2\\}$, i.e.,
$N_{bad}=|{\Psi}|$, we have

$\displaystyle\sum_{i}\sum_{t\in\text{bad
epochs}}r_{t,i}=\sum_{i}\sum_{k\in\Psi}R_{i}^{k}=O\left(|\Psi|MU\right).$

Plugging in $N_{bad}=|{\Psi}|\leq\frac{d}{\log
2}\log\left(1+\frac{MT}{d\lambda}\right)$, we have the total regret for bad
epochs. Now, we are only left to find $U$. Here is the place where the
adaptive schedule in the algorithm comes in. First, note that

$\displaystyle\sum_{t_{k-1}<t<t_{k}}r_{t,i}$
$\displaystyle\mathop{\leq}\limits^{(a)}\sum_{t_{k-1}<t<t_{k}}\min\\{2\beta_{T}\left\lVert
x_{t,i}\right\rVert_{V_{t,i}^{-1}},1\\}$ (8)
$\displaystyle\mathop{\leq}\limits^{(b)}O\left(\beta_{T}\sqrt{(t_{k}-t_{k-1})\log\frac{\det
V_{t_{k},i}}{\det V_{{\text{last}}}}}\right)$ (9)
$\displaystyle\mathop{\leq}\limits^{(c)}O\left(\beta_{T}\sqrt{D}\right),$

where (a) holds by boundedness of reward; (b) follows from the elliptical
potential lemma, i.e., $V_{\text{last}}$ is PSD under event $\mathcal{E}$ and
$V_{t,i}=V_{t-1,i}+x_{t-1,i}x_{t-1,i}^{\top}$ for all $t\in(t_{k-1},t_{k})$;
(c) holds by the adaptive schedule in line 9 of Algorithm 3. As a result, we
have $R_{i}^{k}\leq O\left(\beta_{T}\sqrt{D}\right)+1$, where the regret at
round $t_{k}$ is at most $1$ by the boundedness of reward. With a proper
choice of $D$, one can obtain a final regret bound.

###  C.2 Challenges in Regret Analysis under Private Adaptive Schedule

Now, we will discuss new challenges when one uses private data for an adaptive
communication schedule. In this case, one needs to first privatize the new
local gram matrices (e.g.,
$\sum_{s=t_{\text{last}}+1}^{t}x_{s,i}x_{s,i}^{\top}$) before being used in
the determinant condition. This can be done by using standard tree-based
algorithm with each data point as $x_{s,i}x_{s,i}^{\top}$. With this
additional step, now the determinant condition becomes

$\displaystyle\log\det(\widetilde{V}_{t,i})-\log\det(V_{\text{last}})>\frac{D}{t-t_{\text{last}}},$
(10)

where
$\widetilde{V}_{t,i}:=V_{\text{last}}+\sum_{s=t_{\text{last}}+1}^{t}x_{s,i}x_{s,i}^{\top}+N^{\text{loc}}_{t,i}$
and $N_{t,i}^{\text{loc}}$ is the new local injected noise for private
schedule up to time $t$. Now suppose one uses (10) to determine $t_{k}$. Then,
it does not imply that (9) is upper bounded by $\beta_{T}\sqrt{D}$. That is,
$\frac{\det(\widetilde{V}_{t,i})}{\det(V_{\text{last}})}\leq D^{\prime}$ does
not necessarily mean that
$\frac{\det(V_{\text{last}}+\sum_{s=t_{\text{last}}+1}^{t}x_{s,i}x_{s,i}^{\top})}{\det(V_{\text{last}})}\leq
D^{\prime}$.

One may try to work around (8) by first using $G_{t,i}+\lambda_{\min}I$ to
lower bound $V_{t,i}$. Then, (9) becomes
$O\left(\beta_{T}\sqrt{(t_{k}-t_{k-1})\log\frac{\det(G_{t_{k},i}+\lambda_{\min}I)}{\det(G_{t_{k-1},i}+\lambda_{\min}I)}}\right)$,
which again cannot be bouded based on the rule given by (10). To see this,
note that $\frac{\det(\widetilde{V}_{t_{k}-1,i})}{\det(V_{\text{last}})}\leq
D^{\prime}$ only implies that
$\frac{\det(G_{t_{k},i}+\lambda_{\min}I)}{\det(G_{t_{k-1},i}+\lambda_{\max}I)}\leq
D^{\prime}$.

##  Appendix D Additional Details on Federated LCBs under Silo-Level LDP

In this section, we provide details for Section 6.1. In particular, we present
the proof for Theorem 6.1 and the alternative privacy protocol for silo-level
LDP.

###  D.1 Proof of Theorem 6.1

###### Proof of Theorem 6.1.

Privacy. We only need to show that $\mathcal{P}$ in Algorithm 2 with a proper
choice of $\sigma_{0}$ satisfies $(\varepsilon,\delta)$-DP for all $k\in[K]$,
which implies that the full transcript of the communication is private in
Algorithm 1 for any local agent $i$.

First, we recall that the (multi-variate) Gaussian mechanism satisfies zero-
concentrated differential privacy (zCDP) [BS16]. In particular, by [BS16,
Lemma 2.5], we have that computation of each node (p-sum) in the tree is
$\rho$-zCDP with $\rho=\frac{L^{2}}{2\sigma_{0}^{2}}$. Then, from the
construction of the binary tree in $\mathcal{P}$, one can easily see that one
single data point $\gamma_{i}$ (for all $i\in[K]$) only impacts at most
$1+\log(K)$ nodes. Thus, by _adaptive_ composition of zCDP (cf. Lemma 2.3 in
[BS16]), we have that the entire releasing of all p-sums is $(1+\log
K)\rho$-zCDP. Finally, we will use the conversion lemma from zCDP to
approximated DP (cf. Proposition 1.3 in [BS16]). In particular, we have that
$\rho_{0}$-zCDP implies
$(\varepsilon=\rho_{0}+2\sqrt{\rho_{0}\cdot\log(1/\delta)},\delta)$-DP for all
$\delta>0$. In other words, to achieve a given $(\varepsilon,\delta)$-DP, it
suffices to achieve $\rho_{0}$-zCDP with
$\rho_{0}=f(\varepsilon,\delta):=(\sqrt{\log(1/\delta)+\varepsilon}-\sqrt{\log(1/\delta)})^{2}$.
In our case, we have
$\rho_{0}=(1+\log(K))\rho=(1+\log(K))\frac{L^{2}}{2\sigma_{0}^{2}}$. Thus, we
have
$\sigma_{0}^{2}=(1+\log(K))\frac{L^{2}}{2\rho_{0}}=(1+\log(K))\frac{L^{2}}{2f(\varepsilon,\delta)}$.
To simply it, one can lower bound $f(\varepsilon,\delta)$ by
$\frac{\varepsilon^{2}}{4\log(1/\delta)+4\varepsilon}$ (cf. Remark 15 in
[Ste22]). Therefore, to obtain $(\varepsilon,\delta)$-DP, it suffices to set
$\sigma_{0}^{2}=2\cdot
L^{2}\cdot\frac{(1+\log(K))(\log(1/\delta)+\varepsilon)}{\varepsilon^{2}}$.
Note that there are two streams of data in Algorithm 1, and hence it suffices
to ensure that each of them is $(\varepsilon/2,\delta/2)$-DP. This gives us
the final noise level
$\sigma_{0}^{2}=8\frac{(1+\log(K))(\log(2/\delta)+\varepsilon)}{\varepsilon^{2}}$
(note that by boundedness assumption $L=1$ in our case).

Regret. In order to establish the regret bound, thanks to Lemma B.4, we only
need to determine the maximum noise level in the learning process. Recall that
${\sigma}_{0}^{2}=8\cdot\frac{(1+\log(K))(\log(2/\delta)+\varepsilon)}{\varepsilon^{2}}$
is the noise level for both streams (i.e., $\gamma^{\text{bias}}$ and
$\gamma^{\text{cov}}$). Now, by the construction of binary tree in
$\mathcal{P}$, one can see that each prefix sum $\sum[1,k]$ only involves at
most $1+\log(k)$ tree nodes. Thus, we have that the noise level in $n_{t,i}$
and $N_{t,i}$ are upper bounded by $(1+\log(K)){\sigma}_{0}^{2}$. As a result,
the overall noise level across all $M$ silos is upper bounded by
$\sigma_{\text{total}}^{2}=M(1+\log(K)){\sigma}_{0}^{2}$. Finally, setting
$\sigma^{2}$ in Lemma B.4 to be the noise level $\sigma_{\text{total}}^{2}$ ,
yields the required result. ∎

###  D.2 Alternative Privacy Protocol for Silo-Level LDP

For silo-level LDP, each local randomizer can simply be the standard tree-
based algorithm, i.e., releasing the prefix sum at each communication step $k$
(rather than p-sum in Algorithm 2). The analyzer now becomes a simple
aggregation. As before, no shuffler is required in this case. This alternative
protocol is given by Algorithm 4, which is essentially the main protocol used
in [DP20].

It can be seen that both privacy and regret guarantees under this
$\mathcal{P}_{\text{alt}}$ are the same as Theorem 6.1. To see this, for
privacy, the prefix sum is a post-processing of the p-sums. Thus, since we
have already shown that the entire releasing of p-sums is private in the proof
of Theorem 6.1, hence the same as the prefix sum. Meanwhile, the total noise
level at the server is the same as before. Thus, by Lemma B.4, we have the
same regret bound.

Algorithm 4 $\mathcal{P}_{\text{alt}}$, an alternative privacy protocol for
silo-level LDP

1: Procedure: Local Randomizer $\mathcal{R}$

2: // Input: stream data $\gamma=(\gamma_{i})_{i\in[K]}$; privacy parameters
$\varepsilon,\delta$; Output: private prefix sum

3: for $k\\!=\\!1,\ldots,K$ do

4: Express $k$ in binary form: $k=\sum_{j}\text{Bin}_{j}(k)\cdot 2^{j}$

5: Find the index of first one $i_{k}:=\min\\{j:\text{Bin}_{j}(k)=1\\}$

6: Compute p-sum $\alpha_{i_{k}}=\sum_{j<i}\alpha_{j}+\gamma_{k}$.

7: Add noise to p-sum
$\widehat{\alpha}_{i_{k}}=\alpha_{i_{k}}+\mathcal{N}(0,\sigma_{0}^{2}I)$

8: Output private prefix sum
$\widetilde{s}_{k}=\sum_{j:\text{Bin}_{j}(k)=1}\widehat{\alpha}_{j}$

9: end for

10: end procedure

11: Procedure: Analyzer $\mathcal{A}$

12: // Input: a collection of $M$ data points, $y=\\{y_{i}\\}_{i\in[M]}$;
Output: Aggregated sum

13: Output $\widetilde{y}=\sum_{i\in[M]}y_{i}$

14: end procedure

##  Appendix E Additional Details on Federated LCBs under SDP

In this section, we provide more detailed discussions on SDP and present the
proof for Theorem 6.3 (SDP via amplification lemma) and Theorem 6.5 (SDP via
vector sum).

First, let us start with some general discussions.

Importance of communicating P-sums. For SDP, it is important to communicate
P-sums rather than prefix sum. Note that communicating noisy p-sums in our
privacy protocol $\mathcal{P}$ rather than the noisy prefix sum (i.e., the sum
from beginning as done in [DP20]) plays a key role in achieving optimal regret
with shuffling. To see this, both approaches can guarantee silo-level LDP. By
our new amplification lemma, privacy guarantee can be amplified by
$1/\sqrt{M}$ in $\varepsilon$ for each of the $K$ shuffled outputs, where
$K=T/B$ is total communication rounds. Now, if the prefix sum is released to
the shuffler, then any single data point participates in at most $K$ shuffle
mechanisms, which would blow up $\varepsilon$ by a factor of $O(\sqrt{K})$ (by
advanced composition [DR14]). This would eventually lead to a $K^{1/4}$ factor
blow up in regret due to privacy. Similarly, if we apply
$\mathcal{P}_{\text{Vec}}$ to the data points in the prefix sum, then again a
single data point can participate in at most $K$ shuffled outputs.

On the other hand, if only noisy p-sums are released for shuffling at each
communication round $k\in[K]$ (as in our protocol $\mathcal{P}$) or only the
data points in each p-sum are used in $\mathcal{P}_{\text{Vec}}$ (as in our
protocol in $\mathcal{P}^{\mathcal{T}}_{\text{Vec}}$), then due to the binary-
tree structure, each data point only participates in at most $\log K$ shuffled
mechanisms, which only leads to $O(\sqrt{\log K})$ blow-up of $\varepsilon$;
hence allowing us to achieve the desired $\widetilde{O}(\sqrt{MT})$ regret
scaling, and close the gap present under silo-level LDP.

######  Remark E.1 (Shuffled tree-based mechanism).

Both the protocol $\mathcal{P}$ in Algorithm 2 along with our new
amplification lemma and protocol $\mathcal{P}_{\text{Vec}}^{\mathcal{T}}$ in
Algorithm 5 can be treated as a black-box method, which integrates shuffling
into the tree-based mechanism while providing formal guarantees for continual
release of sum statistics. Hence, it can be applied to other federated online
learning problems beyond contextual bandits.

###  E.1 Amplification lemma for SDP

We first formally introduce our new amplification lemma, which is the key to
our analysis, as mentioned in the main paper.

The motivation for our new amplification result is two-fold: (i) Existing
results on privacy amplification via shuffling (e.g., [FMT22, EFMRTT19,
CSUZZ19, BBGN19]) are only limited to the standard LDP case, i.e., each local
dataset has size $n=1$, which is not applicable in our case where each silo
runs a DP (rather than LDP) mechanism over a dataset of size $n=T$; (ii)
Although a recent work [LR21] establishes a general amplification result for
the case of $n>1$, it introduces a very large value for the final $\delta$
that scales linearly with $n$ due to group privacy.

We first present the key intuition behind our new lemma. Essentially, as in
[LR21], we follow the nice idea of hiding among the clones introduced in
[FMT22]. That is, the output from silo $2$ to $n$ can be similar to that of
silo $1$ by the property of DP (i.e., creating clones). The key difference
between $n=1$ and $n>1$ is that in the latter case, the similarity distance
between the output of silo $1$ and $j$ ($j>1$) will be larger as in this case
all $n>1$ data points among two silos could be different. To capture this,
[LR21] resorts to group privacy for general DP local randomizers.666This is
because it mainly focuses on the lower bound, where one needs to be general to
handle any mechanisms. However, group privacy for approximate DP will
introduce a large value for $\delta$. Thus, since we know that each local
randomizer in our case is the Gaussian mechanism, we can capture the
similarity of outputs between silo $1$ and $j$ ($j>1$) by directly bounding
the sensitivity. This helps to avoid the large value for the final $\delta$.
Specifically, we have the following result, which can be viewed as a
refinement of Theorem D.5 in [LR21] when specified to the Gaussian mechanism.
We follow the notations in [LR21] for easy comparison.

######  Lemma E.2 (Amplification lemma for Gaussian mechanism).

Let $\mathbf{X}=(X_{1},\cdots,X_{N})\in\mathcal{X}^{N\times n}$ be a
distributed data set, i.e., $N$ silos each with $n$ data points. Let
$r\in\mathbb{N}$ and let
$\mathcal{R}^{(i)}_{r}(\mathbf{Z},\cdot):\mathcal{X}^{n}\to\mathcal{Z}:=\mathbb{R}^{d}$
be a Gaussian mechanism with $(\varepsilon_{0}^{r},\delta_{0}^{r})$-DP,
$\varepsilon_{0}^{r}\in(0,1)$777Note that standard Gaussian mechanism only
applies to the regime when $\varepsilon<1$. In our case, $\varepsilon_{0}^{r}$
is often less than $1$. Gaussian mechanism also works for the regime
$\varepsilon>1$, in this case, $\sigma^{2}\approx 1/\varepsilon$ rather than
$1/\varepsilon^{2}$. With minor adjustment of the final $\varepsilon^{r}$, our
proof can be extended. , for all
$\mathbf{Z}=Z_{(1:r-1)}^{(1:N)}\in\mathcal{Z}^{(r-1)\times N}$ and $i\in[N],$
where $\mathcal{X}$ is an arbitrary set. Suppose for all $i$, $\max_{\text{any
pair}(X,X^{\prime})}\left\lVert\mathcal{R}^{(i)}_{r}(\mathbf{Z},X)-\mathcal{R}^{(i)}_{r}(\mathbf{Z},X^{\prime})\right\rVert\leq
n\cdot\max_{\text{adjacent
pair}(X,X^{\prime})}\left\lVert\mathcal{R}^{(i)}_{r}(\mathbf{Z},X)-\mathcal{R}^{(i)}_{r}(\mathbf{Z},X^{\prime})\right\rVert$.888This
is w.l.o.g; one can easily generalize it to any upper bound that is a function
of $n$. Given $\mathbf{Z}=Z_{(1:r-1)}^{(1:N)}$, consider the shuffled
algorithm $\mathcal{A}^{r}_{s}:\mathcal{X}^{n\times
N}\times\mathcal{Z}^{(r-1)\times N}\to\mathcal{Z}^{N}$ that first samples a
random permutation $\pi$ of $[N]$ and then computes
$Z_{r}=(Z^{(1)}_{r},\cdots,Z^{(N)}_{r}),$ where
$Z^{(i)}_{r}:=\mathcal{R}^{(i)}_{r}(\mathbf{Z},X_{\pi(i)}).$ Then, for any
$\delta\in[0,1]$ such that
$\varepsilon^{r}_{0}\leq\frac{1}{n}\ln\left(\frac{N}{16\log(2/\delta)}\right)$,
$\mathcal{A}^{r}_{s}$ is $(\varepsilon^{r},{\delta}^{r})$-DP, where

$\displaystyle\varepsilon^{r}$
$\displaystyle:=\ln\left[1+\left(\frac{e^{\varepsilon_{0}^{r}}-1}{e^{\varepsilon_{0}^{r}}+1}\right)\left(\frac{8\sqrt{e^{n\varepsilon_{0}^{r}}\log(4/\delta)}}{\sqrt{N}}+\frac{8e^{n\varepsilon_{0}^{r}}}{N}\right)\right]$
$\displaystyle\delta^{r}$
$\displaystyle:=\left(\frac{e^{\varepsilon_{0}^{r}}-1}{e^{\varepsilon_{0}^{r}}+1}\right)\delta+N(e^{\varepsilon^{r}}+1)(1+e^{-\varepsilon_{0}^{r}}/2)\delta_{0}^{r}.$

If $\varepsilon_{0}^{r}\leq 1/n$, choosing $\delta=Nn\delta_{0}^{r}$ yields
$\varepsilon^{r}=O\left(\frac{\varepsilon_{0}^{r}\sqrt{\log(1/(nN\delta_{0}^{r}))}}{\sqrt{N}}\right)$
and $\delta^{r}=O(N\delta_{0}^{r})$, where $\delta_{0}^{r}\leq 1/(Nn)$.

###  E.2 Vector Sum Protocol for SDP

One limitation of our first scheme for SDP is that the privacy guarantee holds
only for very small values of $\varepsilon$. This comes from two factors: one
is due to the fact that standard $1/\sqrt{M}$ amplification result requires
the local privacy budget to be close to one; the other one comes from the fact
that now the local dataset could be $n=T$, which further reduces the range of
valid $\varepsilon$.

Algorithm 5 $\mathcal{P}_{\text{Vec}}^{{\mathcal{T}}}$, another privacy
protocol used in Algorithm 1

1: Procedure: Local Randomizer $\mathcal{R}$ at each agent

2: // Input: stream data $(\gamma_{1},\ldots,\gamma_{K})$, privacy budgets
$\varepsilon>0,\delta\in(0,1]$

3: for $k\\!=\\!1,\ldots,K$ do

4: Express $k$ in binary form: $k=\sum_{j}\text{Bin}_{j}(k)\cdot 2^{j}$

5: Find index of first one $i_{k}\\!=\\!\min\\{j:\text{Bin}_{j}(k)\\!=\\!1\\}$

6: Let $\mathcal{D}_{k}$ be the set of all data points999In our application,
each data point means a bias vector or a covariance matrix. See Appendix E.2
for a concrete example.that contribute to
$\alpha_{i_{k}}=\sum_{j<i_{k}}\alpha_{j}+\gamma_{k}$

7: Output $y_{k}=\mathcal{R}_{\text{Vec}}(\mathcal{D}_{k})$ // apply
$R_{\text{Vec}}$ in Algorithm 6 to each data point

8: end for

9: Procedure: Analyzer $\mathcal{A}$ at server

10: // Input: stream data from $\mathcal{S}$:
$\\{\bar{y}_{k}=(\bar{y}_{k,1},\ldots,\bar{y}_{k,M})\\}_{k\in[K]}$

11: for $k\\!=\\!1,\ldots,K$ do

12: Express $k$ in binary and find index of first one $i_{k}$

13: Add all messages from $M$ agents:
$\widetilde{\alpha}_{i_{k}}=\mathcal{A}_{\text{Vec}}(\bar{y}_{k})$ // apply
$A_{\text{Vec}}$ in Algorithm 6

14: Output:
$\widetilde{s}_{k}=\sum_{j:\text{Bin}_{j}(k)=1}\widetilde{\alpha}_{j}$

15: end for

In this section, we give the vector sum protocol in [CJMP21] for easy
reference. Let’s also give a concrete example to illustrate how to combine
Algorithm 6 with Algorithm 5. Consider a fixed $k=6$. Then, for each agent, we
have $\alpha_{i_{6}}=\gamma_{5}+\gamma_{6}$. That is, consider the case of
summing bias vectors, for agent $i\in[M]$,
$\gamma_{5}=\sum_{t=4B+1}^{5B}x_{t,i}y_{t,i}$ and
$\gamma_{6}=\sum_{t=5B+1}^{6B}x_{t,i}y_{t,i}$. Then, $\mathcal{D}_{6}$
consists of $2B$ data points, each of which is a single bias vector. Now,
$\mathcal{R}_{\text{vec}}$ and $\mathcal{A}_{\text{vec}}$ (as well the
shuffler) work together to compute the noisy sum of $2B\cdot M$ data points.
In particular, denote by $\mathcal{P}_{\text{vec}}$ the whole process, then we
have
$\widetilde{\alpha}_{i_{6}}=\mathcal{P}_{\text{vec}}(\mathcal{D}_{6}^{M})$,
where $\mathcal{D}_{6}^{M}$ is the data set that consists of $n=2B\cdot M$
data points, each of them is a single bias vector.

Next, we present more details on the implementations, i.e., the parameter
choices of $g,b,p$. Let’s consider $k=6$ again as an example. In this case,
the total number of data points that participate in $\mathcal{P}_{\text{vec}}$
is $n=2B\cdot M$. Then, according to the proof of Theorem C.1 in [CZ22a], we
have

$\displaystyle g=\max\\{2\sqrt{n},d,4\\},\quad b=\frac{24\cdot 10^{4}\cdot
g^{2}\cdot\left(\log\left(\frac{4\cdot(d^{2}+1)}{\delta}\right)\right)^{2}}{\varepsilon^{2}n},\quad
p=1/4.$

Algorithm 6 ${P}_{\text{vec}}$, a shuffle protocol for vector summation
[CJMP21]

1: Input: Database of $d$-dimensional vectors
$\mathbf{X}=(\mathbf{x}_{1},\cdots,\mathbf{x}_{n}$); privacy parameters
$\varepsilon,\delta$; $L$.

2: procedure: Local Randomizer ${R}_{\text{vec}}(\mathbf{x}_{i})$

3: for $j\in[d]$ do

4: Shift component to enforce non-negativity:
$\mathbf{w}_{i,j}\leftarrow\mathbf{x}_{i,j}+L$

5: $\mathbf{m}_{j}\leftarrow\mathcal{R}_{1D}(\mathbf{w}_{i,j})$

6: end for

7: Output labeled messages $\\{(j,\mathbf{m}_{j})\\}_{j\in[d]}$

8: end procedure

9: procedure: Analyzer ${A}_{\text{vec}}(\mathbf{y})$

10: for $j\in[d]$ do

11: Run analyzer on coordinate $j$’s messages
$z_{j}\leftarrow\mathcal{A}_{\text{1D}}(\mathbf{y}_{j})$

12: Re-center: $o_{j}\leftarrow z_{j}-n\cdot L$

13: end for

14: Output the vector of estimates $\mathbf{o}=(o_{1},\cdots o_{d})$

15: end procedure

Algorithm 7 $\mathcal{P}_{\text{1D}}$, a shuffle protocol for summing scalars
[CJMP21]

1: Input: Scalar database $X=(x_{1},\cdots x_{n})\in[0,L]^{n}$;
$g,b\in\mathbb{N};p\in(0,\frac{1}{2})$.

2: procedure: Local Randomizer $\mathcal{R}_{1D}(x_{i})$

3: $\bar{x}_{i}\leftarrow\lfloor x_{i}g/L\rfloor$.

4: Sample rounding value $\eta_{1}\sim\textbf{Ber}(x_{i}g/L-\bar{x}_{i})$.

5: Set $\widehat{x}_{i}\leftarrow\bar{x}_{i}+\eta_{1}$.

6: Sample privacy noise value $\eta_{2}\sim\textbf{Bin}(b,p)$.

7: Report $\mathbf{y}_{i}\in\\{0,1\\}^{g+b}$ containing
$\widehat{x}_{i}+\eta_{2}$ copies of $1$ and $g+b-(\widehat{x}_{i}+\eta_{2})$
copies of $0$.

8: end procedure

9: procedure: Analyzer
$\mathcal{A}_{\text{1D}}(\mathcal{S}(\mathbf{y}_{1},\ldots,\mathbf{y}_{n}))$

10: Output estimator
$\frac{L}{g}((\sum_{i=1}^{n}\sum_{j=1}^{b+g}(\mathbf{y}_{i})_{j})-pbn)$.

11: end procedure

###  E.3 Proofs

First, we present proof of Theorem 6.3.

###### Proof of Theorem 6.3.

Privacy. In this proof, we directly work on approximate DP. By the boundedness
assumption and Gaussian mechanism, we have that with
${\sigma}_{0}^{2}=\frac{2L^{2}\log(1.25/\widehat{\delta}_{0})}{\widehat{\varepsilon}_{0}^{2}}$,
$\mathcal{R}$ in $\mathcal{P}$ is
$(\widehat{\varepsilon}_{0},\widehat{\delta}_{0})$-DP for each communication
round $k\in[K]$ (provided $\widehat{\varepsilon}_{0}\leq 1$) . Now, by our
amplification lemma (Lemma E.2), we have that the shuffled output is
$(\widehat{\varepsilon},\widehat{\delta})$-DP with
$\widehat{\varepsilon}=O\left(\frac{\widehat{\varepsilon}_{0}\sqrt{\log(1/(TM\widehat{\delta}_{0}))}}{\sqrt{M}}\right)$
and $\widehat{\delta}=O(M\widehat{\delta}_{0})$ (provided
$\widehat{\varepsilon}_{0}\leq 1/T$ and $\widehat{\delta}_{0}\leq 1/(MT)$).
Here we note that in our case, $N=M$ and $n=T$, where $n=T$ follows from the
fact that there exists $\alpha_{i}$ in the tree that corresponds to the sum of
$T$ data points. Moreover, since the same mechanism is run at all silos,
shuffling-then-privatizing is the same as first privatizing-then-shuffling the
outputs. Next, we apply the advanced composition theorem (cf. Theorem 3.20 in
[DR14]). In particular, by the binary tree structure, each data point involves
only $\kappa:=1+\log(K)$ times in the output of $\mathcal{R}$. Thus, to
achieve $(\varepsilon,\delta)$-DP, it suffices to have
$\widehat{\varepsilon}=\frac{\varepsilon}{2\sqrt{2\kappa\log(2/\delta)}}$ and
$\widehat{\delta}=\frac{\delta}{2\kappa}$. Using all these equations, we can
solve for
$\widehat{\varepsilon}_{0}=C_{1}\cdot\frac{\varepsilon\sqrt{M}}{\sqrt{\kappa\log(1/\delta)\log(\kappa/(\delta
T))}}$ and $\widehat{\delta}_{0}=C_{2}\cdot\frac{\delta}{M\kappa}$, for some
constants $C_{1}>0$ and $C_{2}>0$. To satisfy the conditions on
$\widehat{\varepsilon}_{0}$ and $\widehat{\delta}_{0}$, we have
$\varepsilon\leq\frac{\sqrt{\kappa}}{C_{1}T\sqrt{M}}$ and
$\delta\leq\frac{\kappa}{C_{2}T}$. With the choice of
$\widehat{\varepsilon}_{0}$ and $\widehat{\delta}_{0}$, we have the noise
variance
$\sigma_{0}^{2}=O\left(\frac{2L^{2}\beta\log(1/\delta)\log(\kappa/(\delta
T))\log(M\kappa/\delta)}{\varepsilon^{2}M}\right)$. Thus, we can apply
$\mathcal{P}$ to the bias and covariance terms (with $L=1$), respectively.

Regret. Again, we simply resort to our Lemma B.4 for the regret analysis. In
particular, we only need to determine the maximum noise level in the learning
process. Note that
$\sigma_{0}^{2}=O\left(\frac{2L^{2}\kappa\log(1/\delta)\log(\kappa/(\delta
T))\log(M\kappa/\delta)}{\varepsilon^{2}M}\right)$ is the noise level injected
for both bias and covariance terms. Now, by the construction of the binary
tree in $\mathcal{P}$, one can see that each prefix sum only involves at most
$1+\log(k)$ tree nodes. As a result, the overall noise level across all $M$
silos is upper bounded by $\sigma_{\text{total}}^{2}=M\kappa{\sigma}_{0}^{2}$.
Finally, setting $\sigma^{2}$ in Lemma B.4 to be the noise level
$\sigma_{\text{total}}^{2}$ , yields the required result. ∎

Now, we prove Theorem 6.5.

###### Proof of Theorem 6.5.

Privacy. For each calculation of the noisy synchronized p-sum, there exist
parameters for $\mathcal{P}_{\text{Vec}}$ such that it satisfies
$(\varepsilon_{0},\delta_{0})$-SDP where $\varepsilon_{0}\in(0,15]$ and
$\delta_{0}\in(0,1/2)$ (see Lemma 3.1 in [CJMP21] or Theorem 3.5 in [CZ22a]).
Then, by the binary tree structure, each single data point (bias vector or
covariance matrix) only participates in at most $\kappa:=1+\log(K)$ runs of
$\mathcal{P}_{\text{Vec}}$. Thus, to achieve $(\varepsilon,\delta)$-DP, it
suffices to have
${\varepsilon_{0}}=\frac{\varepsilon}{2\sqrt{2\kappa\log(2/\delta)}}$ and
${\delta_{0}}=\frac{\delta}{2\kappa}$ by advanced composition theorem. Thus,
for any $\varepsilon\in(0,30\sqrt{2\kappa\log(2/\delta)})$ and
$\delta\in(0,1)$, there exist parameters for $\mathcal{P}_{\text{Vec}}$ such
that the entire calculations of noisy p-sums are $(\varepsilon,\delta)$-SDP.
Since we have two streams of data (bias and covariance), we finally have that
for any $\varepsilon\in(0,60\sqrt{2\kappa\log(2/\delta)})$ and
$\delta\in(0,1)$, there exist parameters for $\mathcal{P}_{\text{Vec}}$ such
that Algorithm 1 with $\mathcal{P}_{\text{Vec}}^{\mathcal{T}}$ satisfies
$(\varepsilon,\delta)$-SDP.

Regret. By the same analysis in the proof of Theorem 3.5 in [CZ22a], the
injected noise for each calculation of the noisy _synchronized_ p-sum is sub-
Gaussian with the variance being at most
$\widehat{\sigma}^{2}=O\left(\frac{\log^{2}(d^{2}/\delta_{0})}{\varepsilon_{0}^{2}}\right)=O\left(\frac{\kappa\log(1/\delta)\log^{2}(d^{2}\kappa/\delta)}{\varepsilon^{2}}\right)$.
Now, by the binary tree structure, each prefix sum only involves at most
$\kappa$ p-sums. Hence, the overall noise level is upper bounded by
$\sigma_{\text{total}}^{2}=\kappa\widehat{\sigma}^{2}$. Finally, setting
$\sigma^{2}$ in Lemma B.4 to be the noise level $\sigma_{\text{total}}^{2}$ ,
yields the required result. ∎

Now, we provide proof of amplification Lemma E.2 for completeness. We follow
the same idea as in [FMT22] and [LR21]. For easy comparison, we use the same
notations as in [LR21] and highlighted the key difference using color text.

###### Proof of Lemma E.2.

Let $\mathbf{X}_{0},\mathbf{X}_{1}\in\mathcal{X}^{n\times N}$ be adjacent
distributed data sets (i.e.
$\sum_{i=1}^{N}\sum_{j=1}^{n}\mathbbm{1}_{\\{x_{i,j}\neq x_{i,j}\\}}=1$).
Assume WLOG that $\mathbf{X}_{0}=(X_{1}^{0},X_{2},\cdots,X_{N})$ and
$\mathbf{X}_{1}=(X_{1}^{1},X_{2},\cdots,X_{N}),$ where
$X_{1}^{0}=(x_{1,0},x_{1,2},\cdots,x_{1,n})\neq(x_{1,1},x_{1,2},\cdots,x_{1,n}).$
We can also assume WLOG that $X_{j}\notin\\{X_{1}^{0},X_{1}^{1}\\}$ for all
$j\in\\{2,\cdots,N\\}$ by re-defining $\mathcal{X}$ and
$\mathcal{R}^{(i)}_{r}$ if necessary.

Fix
$i\in[N],r\in[R],\mathbf{Z}=\mathbf{Z}_{1:r-1}=Z_{(1:r-1)}^{(1:N)}\in\mathcal{Z}^{(r-1)\times
N}$, denote $\mathcal{R}(X):=\mathcal{R}^{(i)}_{r}(\mathbf{Z},X)$ for
$X\in\mathcal{X}^{n},$ and
$\mathcal{A}_{s}(\mathbf{X}):=\mathcal{A}_{s}^{r}(\mathbf{Z}_{1:r-1},\mathbf{X}).$
Draw $\pi$ uniformly from the set of permutations of $[N]$. Now, since
$\mathcal{R}$ is $(\varepsilon_{0}^{r},\delta_{0}^{r})$-DP,
$\mathcal{R}(X_{1}^{1})\underset{(\varepsilon_{0}^{r},\delta_{0}^{r})}{\simeq}\mathcal{R}(X_{1}^{0})$,
so by [LR21, Lemma D.12], there exists a local randomizer
$\mathcal{R}^{\prime}$ such that
$\mathcal{R}^{\prime}(X_{1}^{1})\underset{(\varepsilon_{0}^{r},0)}{\simeq}\mathcal{R}(X_{1}^{0})$
and
$TV(\mathcal{R}^{\prime}(X_{1}^{1}),\mathcal{R}(X_{1}^{1}))\leqslant\delta_{0}^{r}.$

Hence, by [LR21, Lemma D.8], there exist distributions $U(X_{1}^{0})$ and
$U(X_{1}^{1})$ such that

$\mathcal{R}(X_{1}^{0})=\frac{e^{\varepsilon_{0}^{r}}}{e^{\varepsilon_{0}^{r}}+1}U(X_{1}^{0})+\frac{1}{e^{\varepsilon_{0}^{r}}+1}U(X_{1}^{1})$
(11)

and

$\mathcal{R}^{\prime}(X_{1}^{1})=\frac{1}{e^{\varepsilon_{0}^{r}}+1}U(X_{1}^{0})+\frac{e^{\varepsilon_{0}^{r}}}{e^{\varepsilon_{0}^{r}}+1}U(X_{1}^{1}).$
(12)

Here, we diverge from the proof in [LR21]. We denote
$\widetilde{\varepsilon_{0}}:=n\varepsilon_{0}^{r}$ and
$\widetilde{\delta_{0}}:=\delta_{0}^{r}.$ Then, by the assumption of
$\mathcal{R}(X)$, for any $X$, we have
$\mathcal{R}(X)\underset{(\widetilde{\varepsilon_{0}},\widetilde{\delta_{0}})}{\simeq}\mathcal{R}(X_{1}^{0}))$
and
$\mathcal{R}(X)\underset{(\widetilde{\varepsilon_{0}},\widetilde{\delta_{0}})}{\simeq}\mathcal{R}(X_{1}^{1}))$.
This is because by the assumption, when the dataset changes from any $X$ to
$X_{1}^{0}$ (or $X_{1}^{1}$), the total change in terms of $l_{2}$ norm can be
$n$ times that under an adjacent pair. Thus, one has to scale the
$\varepsilon_{0}^{r}$ by $n$ while keeping the same $\delta_{0}^{r}$.

Now, we resume the same idea as in [LR21]. By convexity of hockey-stick
divergence and the above result, we have
$\mathcal{R}(X)\underset{(\widetilde{\varepsilon_{0}},\widetilde{\delta_{0}})}{\simeq}\frac{1}{2}(\mathcal{R}(X_{1}^{0})+\mathcal{R}(X_{1}^{1})):=\rho$
for all $X\in\mathcal{X}^{n}.$ That is, $\mathcal{R}$ is
$(\widetilde{\varepsilon_{0}},\widetilde{\delta_{0}})$ deletion group DP for
groups of size $n$ with reference distribution $\rho.$ Thus, by [LR21, Lemma
D.11], we have that there exists a local randomizer
$\mathcal{R}^{\prime\prime}$ such that $\mathcal{R}^{\prime\prime}(X)$ and
$\rho$ are $(\widetilde{\varepsilon_{0}},0)$ indistinguishable and
$TV(\mathcal{R}^{\prime\prime}(X),\mathcal{R}(X))\leqslant\widetilde{\delta_{0}}$
for all $X.$ Then by the definition of $(\widetilde{\varepsilon_{0}},0)$
indistinguishability, for all $X$ there exists a “left-over” distribution
$LO(X)$ such that
$\mathcal{R}^{\prime\prime}(X)=\frac{1}{e^{\widetilde{\varepsilon_{0}}}}\rho+(1-1/e^{\widetilde{\varepsilon_{0}}})LO(X)=\frac{1}{2e^{\widetilde{\varepsilon_{0}}}}(\mathcal{R}(X_{1}^{0})+\mathcal{R}(X_{1}^{1}))+(1-1/e^{\widetilde{\varepsilon_{0}}})LO(X).$

Now, define a randomizer $\mathcal{L}$ by
$\mathcal{L}(X_{1}^{0}):=\mathcal{R}(X_{1}^{0}),~{}\mathcal{L}(X_{1}^{1}):=\mathcal{R}^{\prime}(X_{1}^{1}),$
and

$\displaystyle\mathcal{L}(X)$
$\displaystyle:=\frac{1}{2e^{\widetilde{\varepsilon_{0}}}}\mathcal{R}(X_{1}^{0})+\frac{1}{2e^{\widetilde{\varepsilon_{0}}}}\mathcal{R}^{\prime}(X_{1}^{1})+(1-1/e^{\widetilde{\varepsilon_{0}}})LO(X)$
$\displaystyle=\frac{1}{2e^{\widetilde{\varepsilon_{0}}}}U(X_{1}^{0})+\frac{1}{2e^{\widetilde{\varepsilon_{0}}}}U(X_{1}^{1})+(1-1/e^{\widetilde{\varepsilon_{0}}})LO(X)$
(13)

for all $X\in\mathcal{X}^{n}\setminus\\{X_{1}^{0},X_{1}^{1}\\}.$ (The equality
follows from (11) and (12).) Note that
$TV(\mathcal{R}(X_{1}^{0}),\mathcal{L}(X_{1}^{0}))=0,~{}TV(\mathcal{R}(X_{1}^{1}),\mathcal{L}(X_{1}^{1}))\leqslant\delta_{0}^{r},$
and for all $X\in\mathcal{X}^{n}\setminus\\{X_{1}^{0},X_{1}^{1}\\}$,
$TV(\mathcal{R}(X),\mathcal{L}(X))\leqslant
TV(\mathcal{R}(X),\mathcal{R}^{\prime\prime}(X))+TV(\mathcal{R}^{\prime\prime}(X),\mathcal{L}(X))\leqslant\widetilde{\delta_{0}}+\frac{1}{2e^{\widetilde{\varepsilon_{0}}}}TV(\mathcal{R}^{\prime}(X_{1}^{1}),\mathcal{R}(X_{1}^{1}))=(1+\frac{1}{2e^{n\varepsilon_{0}^{r}}})\delta_{0}^{r}$.

Keeping $r$ fixed (omitting $r$ scripts everywhere), for any $i\in[N]$ and
$\mathbf{Z}:=\mathbf{Z}_{1:r-1}\in\mathcal{Z}^{(r-1)\times N},$ let
$\mathcal{L}^{(i)}(\mathbf{Z},\cdot)$, $U^{(i)}(\mathbf{Z},\cdot)$, and
$LO^{(i)}(\mathbf{Z},\cdot)$ denote the randomizers resulting from the process
described above. Let $\mathcal{A}_{\mathcal{L}}:\mathcal{X}^{n\times
N}\to\mathcal{Z}^{N}$ be defined exactly the same way as
$\mathcal{A}_{s}^{r}:=\mathcal{A}_{s}$ (same $\pi$) but with the randomizers
$\mathcal{R}^{(i)}$ replaced by $\mathcal{L}^{(i)}$. Since $\mathcal{A}_{s}$
applies each randomizer $\mathcal{R}^{(i)}$ exactly once and
$\mathcal{R}^{(1)}(\mathbf{Z},X_{\pi(1)},\cdots\mathcal{R}^{(N)}(\mathbf{Z},X_{\pi(N)})$
are independent (conditional on $\mathbf{Z}=\mathbf{Z}_{1:r-1}$) 101010This
follows from the assumption that $\mathcal{R}^{(i)}(\mathbf{Z}_{1:r-1},X)$ is
conditionally independent of $X^{\prime}$ given $\mathbf{Z}_{1:r-1}$ for all
$\mathbf{Z}_{1:r-1}$ and $X\neq X^{\prime}$., we have
$TV(\mathcal{A}_{s}(\mathbf{X}_{0}),\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0}))\leqslant
N(1+\frac{1}{2e^{n\varepsilon_{0}^{r}}})\delta_{0}^{r}$ and
$TV(\mathcal{A}_{s}(\mathbf{X}_{1}),\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})\leqslant
N(1+\frac{1}{2e^{n\varepsilon_{0}^{r}}})\delta_{0}^{r}$. Now we claim that
$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})$ and
$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})$ are $(\varepsilon^{r},\delta)$
indistinguishable for any $\delta\geqslant
2e^{-Ne^{-n\varepsilon_{0}^{r}}/16}.$ Observe that this claim implies that
$\mathcal{A}_{s}(\mathbf{X}_{0})$ and $\mathcal{A}_{s}(\mathbf{X}_{1})$ are
$(\varepsilon^{r},\delta^{r})$ indistinguishable by [LR21, Lemma D.13] (with
$P^{\prime}:=\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0}),Q^{\prime}:=\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1}),P:=\mathcal{A}_{s}(\mathbf{X}_{0}),Q:=\mathcal{A}_{s}(\mathbf{X}_{1})$.)
Therefore, it only remains to prove the claim, i.e. to show that
$D_{e^{\varepsilon^{r}}}(\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0}),\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})\leqslant\delta$
for any $\delta\geqslant 2e^{-Ne^{-n\varepsilon_{0}^{r}}/16}.$

Now, define
$\mathcal{L}_{U}^{(i)}(\mathbf{Z},X):=\begin{cases}U^{(i)}(\mathbf{Z},X_{1}^{0})&\mbox{if}~{}X=X_{1}^{0}\\\
U^{(i)}(\mathbf{Z},X_{1}^{1})&\mbox{if}~{}X=X_{1}^{1}\\\
\mathcal{L}^{(i)}(\mathbf{Z},X)&\mbox{otherwise}.\end{cases}.$ For any inputs
$\mathbf{Z},\mathbf{X}$, let $\mathcal{A}_{U}(\mathbf{Z},\mathbf{X})$ be
defined exactly the same as $\mathcal{A}_{s}(\mathbf{Z},\mathbf{X})$ (same
$\pi$) but with the randomizers $\mathcal{R}^{(i)}$ replaced by
$\mathcal{L}_{U}^{(i)}$. Then by (11) and (12),

$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})=\frac{e^{\varepsilon_{0}^{r}}}{e^{\varepsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{0})+\frac{1}{e^{\varepsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{1})~{}\text{and}~{}\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})=\frac{1}{e^{\varepsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{0})+\frac{e^{\varepsilon_{0}^{r}}}{e^{\varepsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{1}).$
(14)

Then by (E.3), for any $X\in\mathcal{X}^{n}\setminus\\{X_{1}^{0},X_{1}^{1}\\}$
and any $\mathbf{Z}=\mathbf{Z}_{1:r-1}\in\mathcal{Z}^{(r-1)\times N},$ we have
$\mathcal{L}_{U}^{(i)}(\mathbf{Z},X)=\frac{1}{2e^{\widetilde{\varepsilon_{0}}}}\mathcal{L}^{(i)}_{U}(\mathbf{Z},X_{1}^{0})+\frac{1}{2e^{\widetilde{\varepsilon_{0}}}}\mathcal{L}^{(i)}_{U}(\mathbf{Z},X_{1}^{1})+(1-e^{-\widetilde{\varepsilon_{0}}})LO^{(i)}(\mathbf{Z},X).$
Hence, [LR21, Lemma D.10] (with
$p:=e^{-\widetilde{\varepsilon_{0}}}=e^{-n\varepsilon_{0}^{r}}$) implies that
$\mathcal{A}_{U}(\mathbf{X}_{0})$ and $\mathcal{A}_{U}(\mathbf{X}_{1})$) are

$\left(\log\left(1+\frac{8\sqrt{e^{\widetilde{\varepsilon_{0}}}\ln(4/\delta)}}{\sqrt{N}}+\frac{8e^{\widetilde{\varepsilon_{0}}}}{N}\right),\delta\right)$

indistinguishable for any $\delta\geqslant
2e^{-Ne^{-n\varepsilon_{0}^{r}}/16}.$

Here, we also slightly diverge from [LR21]. Instead of using [LR21, Lemma
D.14]111111We think that its restatement of [FMT22, Lemma 2.3] is not correct
(which can be easily fixed though)., we can directly follow the proof of Lemma
3.5 in [FMT22] and Lemma 2.3 in [FMT22] to establish our claim that
$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})$ and
$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})$ are indistinguishable (hence the
final result). Here, we also slightly improve the $\delta$ term compared to
[FMT22] by applying amplification via sub-sampling to the $\delta$ term as
well. In particular, the key step is to rewrite (14) as follows (with
$T:=\frac{1}{2}({\mathcal{A}_{U}}(\mathbf{X}_{0})+{\mathcal{A}_{U}}(\mathbf{X}_{1}))$

$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})=\frac{2}{e^{\varepsilon_{0}^{r}}+1}T+\frac{e^{\varepsilon_{0}^{r}}-1}{e^{\varepsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{0})~{}\text{and}~{}\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})=\frac{2}{e^{\varepsilon_{0}^{r}}+1}T+\frac{e^{\varepsilon_{0}^{r}}-1}{e^{\varepsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{1}).$
(15)

Thus, by the convexity of the hockey-stick divergence and Lemma 2.3 in
[FMT22], we have $\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})$ and
$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})$ are

$\left(\log\left(1+\frac{\varepsilon_{0}^{r}-1}{\varepsilon_{0}^{r}+1}\left(\frac{8\sqrt{e^{\widetilde{\varepsilon_{0}}}\ln(4/\delta^{r})}}{\sqrt{N}}\right)+\frac{8e^{\widetilde{\varepsilon_{0}}}}{N}\right),\frac{\varepsilon_{0}^{r}-1}{\varepsilon_{0}^{r}+1}\delta\right)$

indistinguishable for any $\delta\geqslant
2e^{-Ne^{-n\varepsilon_{0}^{r}}/16}.$ As decribed before, this leads to the
result that $\mathcal{A}_{s}(\mathbf{X}_{0})$ and
$\mathcal{A}_{s}(\mathbf{X}_{1})$ are $(\varepsilon^{r},\delta^{r})$
indistinguishable by [LR21, Lemma D.13] (original result in Lemma 3.17 of
[DR14]) with (noting that $\widetilde{\varepsilon_{0}}=n\varepsilon_{0}^{r}$)

$\displaystyle\varepsilon^{r}$
$\displaystyle:=\ln\left[1+\left(\frac{e^{\varepsilon_{0}^{r}}-1}{e^{\varepsilon_{0}^{r}}+1}\right)\left(\frac{8\sqrt{e^{n\varepsilon_{0}^{r}}\ln(4/\delta)}}{\sqrt{N}}+\frac{8e^{n\varepsilon_{0}^{r}}}{N}\right)\right],$
$\displaystyle\delta^{r}$
$\displaystyle:=\left(\frac{e^{\varepsilon_{0}^{r}}-1}{e^{\varepsilon_{0}^{r}}+1}\right)\delta+N(e^{\varepsilon^{r}}+1)(1+e^{-\varepsilon_{0}^{r}}/2)\delta_{0}^{r}.$

∎