On Differentially Private Federated Linear Contextual Bandits
Authors: Xingyu Zhou
Sayak Ray Chowdhury
Venue: ICLR 2024 poster (2024)
Keywords: linear contextual bandits
federated learning
differential privacy
Primary area: reinforcement learning
TL;DR: Identify the fundamental gaps in state-of-the-art and propose a generic framework to not only fix them but achieve improved results

Abstract: We consider cross-silo federated linear contextual bandit (LCB) problem under differential privacy, where multiple silos interact with their respective local users and communicate via a central server to realize collaboration without sacrificing each user's privacy. We identify three issues in the state-of-the-art~\citep{dubey2020differentially}: (i) failure of claimed privacy protection, (ii) incorrect regret bound due to noise miscalculation and (iii) ungrounded communication cost. 
To resolve these issues, we take a two-step 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.

Published as a conference paper at ICLR 2024
ON DIFFERENTIALLY PRIVATE FEDERATED LINEAR CONTEXTUAL BANDITS
Xingyu Zhou
Sayak Ray Chowdhury
Wayne State University, USA Email: xingyu.zhou@ wayne.edu
Microsoft Research, India
Email: t-sayakr @ microsoft.com
ABSTRACT
We consider cross-silo federated linear contextual bandit (LCB) problem under dif- ferential privacy. where multiple silos interact with their respective local users and communicate via a central server to realize collaboration without sacrificing each user's ' privacy. We identify three issues in the state-of-the-art (Dubey & Pentland, 2020): (i) failure of claimed privacy protection, (ii) incorrect regret bound due noise miscalculation and (iii) ungrounded communication cost. To resolve these issues, we take two-step approach. First, we design an algorithmic framework consisting of 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-aa algorithm. To further improve the regret performance, model of differential privacy, under which we show that our algorithm can achieve nearly "optimal" regret without trusted server. We accomplish this via two differ- ent 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.
next consider shuffle
INTRODUCTION
We consider the classic cross-silo Federated Learning (FL) paradigm (Kairouz et al., 2021) applied to linear contextual bandits (LCB). In this setting, 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 E [T]. each local agent i E [M] receives a new user (e.g., patient) with context information C,, E C, (e.g., age, gender, medical history), recommends an action a E Kr; (e.g.. choice of medicine), and then it observes a real-valued reward y/,, (e.g., effectiveness of the prescribed medicine). In linear contextual bandits, the reward yt, is a linear function of the unknown bandit parameter 6" e IR corrupted by i.i.d mean-zero observation noise T7,,i, i.c., Vt, (Z,,,, 0*) 7t,i, where zz, dv(cr, ae,s) and é; : C; K, - d is known function that maps context-action pair to a d-dimensional real-valued feature vector. The goal of federated LCB to minimize the cumulative group pseudo-regre defined
= Σ 111
[max (ox a), (Fr, 0*)
aeK.
To achieve the goal, as in standard cross-silo FI., the agents are allowed to communicate with the central server following 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 i at each silo e.g., the sensitive context information Ct2; and reward ye.i-
To address this privacy risk, we resort to differential privacy (Dwork & Roth, 2014), 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 device. However, it has limitations in cross-silo FL,, where the protection

---

Published as a conference paper at ICLR 2024
Table 1: Summary of main results. <> 0,8 (0, are privacy parameters.
DP model
Privacy cost in regret
Communication
Reference
MT log
(11/))
Central-JDP
NA
Shariff & Sheffet (2018)
Silo-level LDP
Ö
VV VT
(M log (1116)
O(VMT)
Theorem 5.1
SDP
Ö VM log (1/8)
O(VMT)
Theorem 5.3 and 5.5
VE
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 (Lowy & Razaviyayn, 2021; Lowy et al., 2022; Liu et al., 2022; Dobbe et al., 2018) 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!.
Dubey & Pentland (2020) adopt 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 ofate-of-thh-arr for this problem. The proposed algorithm claims to protect the privacy of each user at each silo. Furthermore, given privacy budget E > 0, the claimed regret bound is Ö ((VMT/)) with only (M log communication rounds, which matches the regret of a super-single agent that plays for total MT rounds. Unfortunately, in spite of being the kate-of-the-art the aforementioned privacy, regret and communication cost guarantees have fundamental gaps, as discussed below.
identify privacy, regret, communication gaps in state-of-the-art (Dubey & Pentland, 2020). In Section 3, we first show that the algorithm in (Dubey & Pentland, 2020) could leak privacy from the side channel of adaptive communication schedule, which depends users' non- private local data. Next, we identify a mistake in total injected privacy noise in their regret analysis. Accounting for this miscalculation, the correct regret bound would amount to ((M3/4 /T/E), which is 1/ factor higher than the claimed one, and doesn't '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) communications no longer holds. To resolve these issues, we take the following two-step approach:
Our contributions:
(i) design a generic algorithmic and analytical framework. In Section 4, we propose a generic federated LCB algorithm along with flexible privacy protocol. Our algorithm adopts fixed-bath schedule (rather than an adaptive one in Dubey & Pentland (2020)) that helps avoid privacy leakage from the side channel, well as subtleties in communication analysis. Our privacy protocol builds on a distributed version of the celebrated tree-based algorithm (Chan et al., 2011; Dwork et al., 2010), enabling us to provide different privacy guarantees in a unified way. We further show that our algorithm enjoys simple and generic analytical regret bound that only depends on the total amount of injected privacy noise under the required privacy constraints.
(ii) prove regret guarantees under different privacy notions. We build upon the above framework to study federated LCBs under two different privacy constraints. In Section 5. we consider silo-level LDP (a stronger notion of privacy than Federated DP of Dubey & Pentland (2020)) and establish privacy guarantee with correct regret bound ( /T/E) and communication cost O(V hence fixing the gaps in Dubey & Pentland (2020). Next, to match the regret of a super single agent, we consider shuffle DP (SDP) (Cheu et al., 2019) in Section 5.2 and establish regret bound of MT))). 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 (Cheu et al., 2021) into the tree-based mechanism. See Table for a summary.
Related work. In standard multi-armed bandits, where rewards are only sensitive data, different DP models including central (Mishra & Thakurta, 2015; Azize Basu, 2022; Sajed & Sheffet, 2019),
It appears under different names in prior work, e.g., silo-specific sample-level DP (Liuu al., 2022), inter-silo record-level DP (Lowy& & Razaviyayn, 2021).
2

---

Published as a conference paper at ICLR 2024
local (Ren et al., 2020) and distributed (Chowdhury& & Zhou, 2022a; Tenenbaum al., 2021), have been studied. In linear contextual bandits, where both contexts and rewards are sensitive, there is a line of work under central (Shariff & Sheffet, 2018), local (Zheng et al., 2020) and shuffle (Chowdhury & Zhou, 2022h; Garcelon et al., 2022; Tenenhaum et al., 2023) models of DP. Li et al. (2022); Hanna et al. (2022) study linear bandits without contexts protection. Dubey & Pentland (2020) is the first to consider federated LCBs under item-level privacy while Huang et al. (2023) study user-level privacy under some distributional assumptions; see Appendix A. Federated or distributed LCBs without privacy have also been studied (Wang et al., 2020; He et al., 2022a; Huang et al., 2021), where a common goal is achieve the regret of a super single agent that plays MT rounds while keeping communication cost minimal. Lowy& & Razaviyayn (2021); Liu et al. (2022) study private cross-silo federated learning under supervised setting, whereas we focus on the sequential learning setting.
DIFFERENTIAL PRIVACY IN FEDERATED LCBS
We now formally introduce differential privacy in cross-silo federated contextual bandits. Let dataset D; at each silo be given by a sequence of T unique users .i......, UT... Each user U., is identified by her context information Cr as well as reward responses she would give to all possible actions recommended to her. We say two datasets D, and D' at silo i are adjacent if they differ exactly in one participating user, i..., U # U², for some [T] and Ug = Un, for all * T.
Silo-level local differential privacy (LDP). Consider a multi-round, cross-silo federated learning algorithm Q. At each round t, each silo i communicates randomized message Zi of its data D; to the server, which may depend (due to collaboration) from all other silos j A We allow Z to be empty if there no communication at round t. Let Z, = -Z! ..... 2T") denote the full transcript of silo i's communications with the server over T rounds and 2; the induced local mechanism in this process. Note that Z; is a realization of random messages generated according the local mechanism 2.. We denote by Z_; (Z1..... Zi-1, Zet,,.... ZM) the full transcripts of all but silo i. We assume that Z; is conditionally independent of D2 for all j # given D, and Z_.. With this notation, we have the following definition of silo-level LDP.
previous randomized messages Z). ...... Z,-
Definition 2.1 (Silo-level I.P).. A cross-silo federated learning algorithm Q with M silos is said to be &.) silo-level LDP if for each silo i [M], it holds that
( +0,, for all adjacent datasets D; and D', and for all events & in the range of Q. If = and & = 8 for all i [M], we simply say Q is (e, 8) -illo-eeve LDP.
P [[2,(, E & -))))= P(Q
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 's sensitive information (e.g., context and reward) or determine whether an individual participated in the learning process.?
Remark 2.2 (Federated DP vs. Silo-level LDP). Dubey & Pentland (2020) consider privacy notion called Federated DP (Fed-DP in short). As summarized in Dubey & Pentland (2020), Fed-DP requires "the action chosen by any agent must be sufficiently impervious (in probability) to any single pair (zc 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 stronger notion of privacy. In fact, Dubey & Pentland (2020) claim to achieve Fed-DP by relying on privatizing the communicated data from each silo. However, as we shall see in Section 3, 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). Another common DP notion for FL is SDP (Cheu et al., 2019). which has been widely studied in supervised learning (Lowy & Razaviyayn, 2021; Girgis et al., 2021: Lowy et al., 2022) to match the centralized utility performance. Motivated by this, we adapt it to FL-LCBs. Specifically, each silo E [M] first applies local randomizer R to its raw local data and sends the randomized output to a shuffler S. The shuffler S permutes all the messages from all M silos uniformly at random and sends those to the central server. Roughly speaking, SDP requires
This is notion of item-level DP. A comparison with standard local DP, central (joint)-DP and shuffie DP for single-agent LCBs is presented in Appendix G.2.
3

---

Published as a conference paper at ICLR 2024
all the messages sent by the shuffler to be private ("indistiguuishable)) with respect to a single user change among all MT users. This item-level DP is defined formally as follows.
Definition 2.3 (SDP), Consider a cross-silo federated learning algorithm Q that induces (random- ized) mechanism M whose output is the collection of all messages sent by the shuffler during the entire learning process. Then, the algorithm Q is said to be (e, 6)-SP
P[M(D)) E E] S S P(M(D') E E] + + for all E in the range of M and for all adjacent datasets D = (Di,..., DMs) and D' = (D2, D'rr)
such that Ee i== Een (U,,)+07,)
3 PRIVACY, REGRET AND COMMUNICATION GAPS IN STATE-OF-THE-ARE
Gap in privacy analysis. We take a two-step approach to demonstrate the privacy issue in Dubey & Pentland (2020). To start with, we argue that Algorithm I in Dubey & Pentland (2020) fails to achieve silo-level LDP due to privacy leakage through the side channel of communication schedule (i.e., when agents communicate with the server). The key issue is that the adaptive communication schedule in the algorithm depends on users' non-private data. This fact can be utilized by adversary or malicious silo j to infer another silo i's users' sensitive information, which violates the requirement of silo-level LDP. In that algorithm, all silos synchronously communicate with the server if
3 some silo E [M] ()
(1)
where f is some function, X, is non non-private local data of silo 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 3.1 (Privacy leakage). Consider two silos and j following Algorithm 1 in Dubey & Pentland (2020). After the first round, X; is the data of the first user in silo i (say Alice), X, is the data of the first user in silo (say Bob) and Z is zero Let communication is triggered the end of first round and assume f f(x, 0) < O. Since the rule (1) is public, silo can infer that f(x,,0 0) > O, iee the communication is triggered by silo Since f is also public knowledge, silo j can utilize this to infer some property of X₁. Hence, by observing only the communication signal (even without looking at the data), silo can infer sensitive data of Alice. In fact, the specific form of f in Dubey & Pentland (2020) allows silo j to infer context information of Alice (details in Appendix B).
This example shows that Algorithm in Dubey & Pentland (2020) does not satisfy silo-level LDP. implying their proof for Fed-DP guarantee via post-processing of silo-level LDP does not hold. However, does not imply that this algorithm fails to satisfy Fed-DP, which is weaker notion than silo-level LDP. Nevertheless, by leveraging Example 3.1, one can show that this algorithm indeed fails to guarantee Fed-DP. To see this, recall the definition of Fed-DP from Remark 2.2. In the context of Example 3. 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 must remain "indistinguishable" at silo j for each IE [T]. This is because the actions at silo are chosen deterministically based on its local data as well as on the communicated data from silo i, and the local data at silo j remains unchanged. However, in Algorithm of Dubey & Pentland (2020), the communicated data from silo is not guaranteed to remain "indistinguishable" as synchronization depends on non-private local data (X; in (I)). In other words, without additional privacy noise added to X; in (1), the change from Alice to Tracy could affect the existence of synchronization at round t 2 1. Consequently, under these two neighboring situations (e.g. Alice vs. Tracy), the communicated data from silo i could differ significantly at round I ++1 1. As a result, the action chosen at round & + 1 in silo j can be totally different violating Fed-DP. This holds true even silo i injects noise while communicating its data (as done in Dubey & Pentland (2020) due to large change of non non-private communicated data (see Appendix B for details).
Gaps in regret and communication analysis. We now turn to regret and communication analysis of Dubey& & Pentland (2020), which has fundamental gaps that lead to incorrect conclusions in the end. First, the reported privacy cost in regret bound is Ó( / MT/e) (ignoring dependence on dimension d), which leads to the conclusion that federated LCBs across M silos under sevol LDP can achieve the same order of regret as in the centralized setting (i.e., when a super single agent
4

---

Published as a conference paper at ICLR 2024
Algorithm Private-FeddLinUCB
1: Parameters: Batch size B E N, regularization À > 0, confidence radii {Be, (MM feature
map di C, K; + gd, privacy protocol (R,S, A))
2: Initialize: W; = 0, U, = 0 for all agents E [M]. Wsyn = 0, Üsyn =
3: for 1=1,...,, T do
4: for each agent i = 1,...., M do
5: Receive context Cr, compute Vt,i AI H W syn + W; and O..; - Ve. (U + U:)
6:
Play action a argmax (d)( 0,,i) + Sr, 14.1lll0 (llll (c,, observe reward yr,
7:
Set (C (,,,), Uj U; + it and W; W, + 21,
8:
end for
9:
if mod B then
10:
// Local randomizer R. at all agents i E [M]
11:
Send randomized messages Rh bias (U,) and RE, (W.) S
12:
// Third party S
13:
Shuffle (or, not) all messages Stim S({ JEEMM) and Si = S({ 127,7 )E(())
14:
// Analyzer A at the server
15:
Compute private synchronized statistics Üsy = A and Wyy = A (Str
// All agents i E [M]
17:
Receive W Wsyn and Usyn from the server and reset W; = 0, U, =0
18:
end if
19:
end for
plays MT rounds). However, the proposed analysis, the total amount of injected privacy noise miscaleulated. In particular, variance of total noise needs to be Mo? rather than the proposed value of 0². This is due to the fact that each silo injects Gaussian noise with variance o² when sending out local data which amounts total Mo² noise the server. Accounting for this correction, the cost of privacy becomes 3(M3/4 ((M3/A/T/E) which is 1/41/4) factor worse than the claimed one. Hence, conclude that Algorithm 1 in Dubey & Pentland (2020) cannot achieve the same order of regret as in centralized setting. Second, the proposed analysis to show Ollog T) communication rounds for the data- adaptiva schedule (1) under privacy constraint essentially follows from the non-private one of Wang al. (2020). Unfortunately. due privacy noise, this direct approach no longer holds, and hence the reported logarithmic cost stands ungrounded (details in Appendix B).
4 OUR APPROACH
To address the issues in Dubey & Pentland (2020), we introduce a generic algorithm for private, federated linear contextual bandits (Algorithm and a flexible privacy protocol (Algorithm 2). This helps us (a) derive correct privacy, regret, and communication results under silo-level LDP (and hence under Fed-DP) (Section 5.1), and (b) achieve the same order of regret in centralized setting under SDP (Section 5.2). Throughout the paper, we make the following standard assumptions in LCBs.
Assumption 4.1 (Boundedness (Shariff & Sheffet, 2018)). The rewards are bounded, i.e., yr. E [o, 1] for all t E [T] and i [M]. Moreover, ||0") 1| and sup,,a [lør(c, a) I 1 for all i [M].
4.1 ALGORITHM: PRIVATE FEDERATED LINUCB
We build upon the celebrated LinUCB algorithm (Abbasi-Yadee et al., 2011) by adopting a fixed- batch schedule for synchronization among agents and designing a privacy protocol (Algorithm 2) for both silo-level LDP and SDP At each round f, each agent recommends an action at, to each local user following optimism in the face of uncertainty principle. First, the agent computes local estimate 0z,, based on all available data to her, which includes previously synchronized data from all agents as well her based on the LinUCB decision rule (line 6), where proper radius 3r is chosen to balance between exploration and exploitation. After observing the reward yt each agent accumulates her local data (bias vector &t, and covariance matrix xn, and stores them in U; and W., respectively
local data (line of Algorithm 1). Then, the action dt,; is selected
5

---

Published as a conference paper at ICLR 2024
Algorithm 2 P. privacy protocol used in Algorithm 1
1: Procedure: Local Randomizer R at each agent
2: //Input: stream data (?1....,7k3) ), E 0, 6 E (0. 1]
211
3: for k= K do
4: Express k in binary form: k: = Σ, Bin, (k) -2
1[1
1]5
5: Find index of first one ig mi Bin, (k) =1
6: Compute p-sum 0i2 -E ag +
211.21
313.4]
[
177
7: Output āg - 0ú, +)
8: end for
9: Procedure: Analyzer A at server
10: //Input : data from 8: (āx.,....... MK, Ke [K]
71 Y2
Ts Y6 Y 7
11: for k= k= K do
Figure 1: Illustration of the tree-based algorithm. Each Icaf node is the stream data and cach internal node is p-sum [|. j] Σl ".. The green node cor- responds to the newly computed p-sum at cach k. i.c., 0ig in Algorithm 2.
12: Express k in binary and find index of first one in
13:
Add noisy p-sums of all agents: 0ig = Ei=1 ag.s
M
14: Output: $k = >i,Binn dg
15:
end for
(line 7). A communication is triggered between agents and central server whenever batch ends assume w.l.o.g. total rounds T is divisible by batch size B (line 9). During this process, a protocol p = (R, S, 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 W Wayn Usy from the server (line 17). Here, for any t= t=kB,A h E [J. W syn represents noisy version of all covariance matrices up to round from all agents (i.e., > Σ I,,) and similarly, Üsyn M
represents noisy version of all bias vectors Ei Σd T... Finally, each agent resets W; and U; so that they can be used to accumulate new local data for the next batch. Note that Algorithm I uses a fixed- bathh (data-inde innteeindee)nnnnt communication schedule rather than the adaptive, detendet one in Dubey & Pentland (2020), which allows us to resolve privacy and communication issues.
4.2 PRIVACY PROTOCOL
We now turn to privacy protocol P (Algorithm 2). which helps to aggregate data among all agents under privacy constraints. The key component of P is a distributed version of the classic tree-based algorithm, which was originally designed for continual release of private sum statistics (Chan et al., 2011; Dwork et al., 2010). That is, given a stream of (multivariate) data y= (71....., ".)) one aims to release 8% -Et Ii=1 "i privately for all & [K] The tree-based mechanism constructs a complete binary tree T in online manner. The leaf nodes contain data 711 to Y.K and internal nodes contain the sum of all leaf nodes in its sub-tree, see Fig. for illustration. For any arrival data Yk- it only releases a tree node privately, which corresponds to a noisy partial sum (p-sum) between two time indices. As example, take k = 6, and hence the new arrival is "/- The tree-based mechanism first computes the p-sum 15 6] 76 + To (line 6 in Algorithm 2). Then, it adds a Gaussian noise with appropriate variance of [5, 6] and releases the noisy p-sum (line 7). Finally, to compute the prefix sum statistic E[. 6] privately, it simply adds noisy p-sums for [1, 4] and [5 6), respectively. Reasons behind releasing and aggregating p-sums are that (i) each data point Th only affects at most 1 + log K p-sums (useful for privacy) and (ii) each sum statistic [[, k| only involves at most 1 + log p-sums (useful for utility).
Our privacy protocol P = (R. S, breaks down the above classic mechanism of releasing and aggregating summ into a local randomizer R at each agent and an analyzer A at the server, separately, while allowing for a possible shuffler in between to amplify privacy. For each k; the local randomizer R at each agent computes and releases the noisy p-sum to a third-party S (lines 4-7). S can either be shuffler that permutes the data uniformly at random (for SDP) 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 A 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 discussed in above paragraph (line 14). Finally, we employ P to Algorithm by observing that local data Th, for batch & and agent consists of bias vectors blas AB K,
(1= Ft,WWtt. and covariance matrices 000 = = B)1+1 F which are stored

---

Published as a conference paper at ICLR 2024
in U, and W; respectively. We denote the randomizer and analyzer for bias vectors as Rhias and Abins and for covariance matrices as Rey and .A in Algorithm 1.
THEORETICAL RESULTS
5.1 FEDERATED LCBs UNDER SILO-LEVEL LDP
We first present the performance of Algorithm under silo-level LDP, hence fixing the privacy, regret and communication issues of the state-of-the-ard algorithm in Dubey & Pentland (2020). The key idea is to inject Gaussian noise with proper variance (oū in Algorithm 2) when releasing p-sum such that all the released p-sums up to any batch & E [K] (s, DD for any agent E [M]. Then, by Definition 2.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 S in P is simply an identity mapping, denoted by I. The following result states this formally, with proof deferred to Appendix E.
Theorem 5.1 (Performance under silo-level LDP). Fix batch size B, privacy budgets E>0, 8 (0, 1).
Let P = (R. A) be a protocol given by Algorithm 2 with parameters of 88 (loR(2/6)+e), where + log(T/B). Then, under Assumption 4.1, Algorithm 1 instantiated with P satisfies (e, 6)- silo-level LDP. Moreover, for any E (0, 1}, there exist choices of X and {Be,he. such that, with probability at least a, it enjoys a group regret
(T (dMBlog log T + dv MT log( (TT(M)/))) + (Md)3/ log (1/5) log" (Tg Bei))
VE
The first term in the above regret bound doesn't 't depend privacy budgets e, ō, and serves representative regret bound for federated LCBs without privacy constraint. The second term is the dominant one which depends on e, 6 and denotes the cost of privacy due injected noise.
Corollary 5.2. Setting B = VT/M, Algorithm I achieves Ö(d + +VT (Md) log" 1ogg/1(0 (1//6)
group regret, with total v MT synchromizations under (e, 8--silo-level LDP.
Comparison with Dubey & Pentland (2020). First, we avoid the privacy leakage by adopting data-inde iate-independent synchronization. However, this leads to an O( communication cost. It remains open to design a (correct) data-adaptive schedule with logarithmic cost; details Appendix D. We also show that privacy cost scales as (/M3/4) with number of agents M, correcting the reported VM scaling. Next, we compare our result with that of a super single agent running for MT rounds under the central model of DP (i.e., where the central server is trusted), which serves as a benchmark for our results. As shown in Shariff & Sheffet (2018), the total regret for such single agent ÖdVMMT + +VM 884 (118)) Comparing this with Corollary 5.2, we observe that the privacy cost of federated LCBs under silo-level LDP is multiplicative 114 factor higher than super agent under the central model. This motivates us to consider SDP in next section.
V8
5.2 FEDERATED LCBS UNDER SDP
We now aim close the above 1/ gap in the privacy cost under silo-level LDP compared 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 trusted. Thanks to our flexible protocol P, the only change needed compared to silo-level LDP is the introduction of shuffler S amplify privacy and adjustment of the privacy noise of accordingly. Theorem 5.3 (Performance under SDP via amplification). Fix batch size and let k == 1+log(T B). Let P = (R, A) be a protocol given by Algorithm 2. Then, under Assumption 4.1, there exist constants C₁ C2 > such that for any E C.TVM' 85 n CTT, Algorithm I instantiated with P and = = 20 log(l/ /8) (og(x/((T)) (onda/ Mo/1)) satisfies (e, S)-P.. Moreover, for any E (0, 11, there exist choices of X and (Br,fe, such that, with a probability at least 1 a, it enjoys group regret
VR
2*M
3/1 3/1 (Mx/0)
RM (T)= (dMB log T dd MT log( loggoM///aa)+ +0(8% MT
log (T Ba)
VE
Corollary 5.4. Setting B VT/M, Algorithm I achieves ÓddvMT + 4/4 MT log (Mx/5) group regret, with total / MT synchronizations under (e, SDPP
Ve
7

---

Published as a conference paper at ICLR 2024
Corollary 5.4 asserts that privacy cost of federated LCBs under SDP matches that of super single agent under central DP (up to a log factor in M, 6).
Comparison with existing SDP analysis. Note that the above result doesn't directly follow from prior amplification results (Feldman et al., 2022; Erlingsson et al., 2019; Cheu et al., 2019; Balle et al., 2019), which show that shuffling outputs of M (e. 6)-LDP algorithms achieve roughly 1/vM factor amplification in privacy for small 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, Le., they operate
datasel of size 1. This doesn't 't hold in our case since the dataset each silo is a stream of ' points. Lowy & Razaviyayn (2021) adopt group privacy to handle the case of n > 1, which can amplify any general DP mechanism but comes at the expense of large increase in 8. To avoid this, we prove new amplification lemma specific to Gaussian DP mechanisms operating on datasets with size n >> 1. This helps us achieve the required 1 \/VM amplification in E while keeping the increase in 8 in check. The key idea behind our new lemma is to directly analyze the sensitivity when creating "clones" as in Feldman et al. (2022), but now by accounting for the fact that all n. >>>> points can be different (see Appendix for formal statement and proof of the lemma).
5.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 e, 5 (see Theorem 5.3). In this subection, we propose an alternative privacy protocol to resolute this limitation. This new protocol leverages the same binary tree structure as in Algorithm 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 (āsg in Algorithm 2). Specifically, it applies the vector sum mechanism Pve: of Cheu et al. (2021), which essentially take 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 E, 6 and n.
In our case, one cannot directly aggregate M p-sums using Pise with n = M. This is because each p-sum would then have a large norm (O(T) at the worst case), which would introduce large amount of privacy noise (cf. Theorem 3.2 in Cheu et al. (2021)), resulting in worse utility (regret). Instead, we first expand each p-sum resulting in set of points such that each with O(1) norm. Then, we aggregate all of those data points using Pve: mechanism (one each for bias vectors and covariance matrices). For example, consider summing bias vectors during batch & 6 and refer back to Fig. for illustration. Here, the p-sum for each agent is given by E5, 6) = "s + "/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 Pvee We denote the entire mechanism as PTo- see Algorithm 5 in Appendix F.2 for pseudo-code and a complete description.
Now, the key intuition behind using Pvee as 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 the central model using a shuffler. This, in turn, helps us match the regret of the centralized setting while guaranteeing (strictly stronger) SDP. Specifically, we have the same order of regret as in Theorem 5.3, but now it holds for a wide range of privacy budgets E, 5 as presented below. Proof is deferred to Appendix F.
Theorem 5.5 (Performance under SDP via vector sum). Fix batch size B and let = 11 llogg(T) B). Let The be a privacy protocol given by Algorithm 5. Then, under Assumption 4. I, there exist parameter choices of PT. such that for any E E 60 /2x 1og(2/8) and 8 1, Algorithm 1 instantiated with PT. satisfies (e. 8)-SDP. Moreover, for any a E (0, 1]. there exist choices of X and (Be,)t. such that, with a probability at least O. it enjoys a group regret
3/A (Red 18) log' 1/4 (T/Ba)) RM (T) - (JMB log dd MT logg((T//)) + -O/8 MT log
Ve
Remark 5.6 (Importance of communicating P-sums). A key technique 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 O(log K) shuffle mechanisms (rather than in O(K) mechanisms if we communicate and shuffle prefix-sums). This helps keep the final privacy cost in check after adaptive composition. In other words, one cannot simply use shuffling to amplify privacy of Algorithm in Dubey & Pentland (2020) to close the regret gap (even ignoring its privacy and communication issues), since it communicates prefix sums at each
8

---

Published as a conference paper at ICLR 2024
42.5
SDP-fedt intiC 6 00001
Time-everap Regret
LoR-FedUinuCBy
0.21
Time eeeeeeeeeree age Regret
redlinucn
Time-aveerop Reg
inCC -.001)
SDreed InX 0.2
inneeed 0.2)
LDN-FudlinuCCti 0.0001)
30
LDN-FedlintcBG -1
LDP FedunnCcic 0.001)
LOR-FedLincces
20-
35.0
2000
4000
6000
8000
10000
2000
4000
6000 Round
8000
10000
0
5000
10000 15000 20000 25000 Round
Round
(a) Synthetic data (M 100)
(b) Synthetic data (M = 100)
(c) Real data (M = 10)
Comparison of time-average group regret for LDP-FedLinUCB (silo-level LDP), SDP-FedLinUCT (shuffle model) and FedLinUUB (non-prite noon-private) under varying privacy budgets e, on (a. b) synthetic Gaussian
Figure 2:
bandit instance and (c) bandit instance generated from WISLR-WEBIIR Learning to Rank dataset.
synchronization. This again highlights the algorithmic novelty of our privacy protocols (Algorithms 2 and 5), which could be of independent interest. See Appendix F for further details.
SIMULATION RESULTS AND CONCLUSIONS
We evaluate regret performance of Algorithm under silo-level LDP and SDP, which we abbreviate as
and EDP-FedLinUUCE respectively. We fix confidence level a 0.01, batchsize B 25 and study comparative performances under varying privacy budgets E, 8. We plot time- averaged group regret Reg (T) in Figure 2 by averaging results over 25 parallel runs.
Synthetic bandit instance. We simulate a LCB instance with a parameter 0* of dimension d = 10 and |K,]| 100 actions for each of the M agents. Similar to Vaswani et al. (2020), we generate 0* and feature vectors by sampling (d-1))dimensional vectors of norm 1/v2 uniformly at random, and append it with a 1/ 22 entry. Rewards are corrupted with Gaussian // (0, 0.25) noise.
Real-data bandit instance. We generate bandit instances from Microsoft Learning to Rank dataset (Qin & Liu, 2013). Queries form contexts and actions a are the available documents. The dataset contains 10K queries, each with up to 908 judged documents on scale of rel(c, a) E {0. 1. Each pair (c, a) has feature vector (<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 Φ, and take this model as the parameter 0** with d 57. 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 |CC| S 908.
Observations. In Fig. 2(a), we compare performance of LDP-FedLinUCB and SDP-FedLinUCB (with amplification based privacy protocol P) on synthetic bandit instance with M 100 agents under privacy budget 8 = 0.0001 and 6 0.001 or 0.0001. We observe that regret of less than LDP-FedLLinUBB for both values of E, which is consistent with theoretical results. Here, we only work with small privacy budgets since the privacy guarantee of Theorem 5.3 holds for e, 1. Instead, Fig. 2(b), we consider higher privacy budgets as suggested in Theorem 5.5 (e.g. 8 0.2, 5 0.1.) and compare the regret performance of L.DD-FedLinUCB and SDP- FenLLn (with vecor- sum based privacy protocol P. As expected, we observe that regret of SDP- CDP-FedLinUCB decreases faster than that of L.DP-FeLLinUCK Next, we benchmark the performance of Algorithm under silo-level LDP (i.e. LDDP-FeLLinUCH communication schedule, building on Abbasi- Abbasi-Yadkori et al. (201 and refer as FedLinUCB, In Fig. 2(c), we demonstrate the cost of privacy under silo-level LDP on real-data bandit instance by varying e in the set {0.2, 5) while keeping d fixed 0.1. We observe that regret of LDP-FedLinUCB decreases and comes closer to that of FedLinUCB as E increases (i.e., level of privacy protection decreases). A similar regret behavior is noticed under SDP also (postponed to Appendix H).
is
against a non-private Federated LCB algorithm with fixed
Concluding Remarks. We conclude with some discussions. First, our adversary model behind silo-level LDP excludes malicious users within the same silo. If one also interested in protecting against adversary users within the same silo, simple tweak of Algorithm 1 would suffice (see Appendix G.3). With this, one can not only protect against colluding silos (as in silo-level LDP), but also against colluding users within the same silo (as in central JDP). Next, we assume that all MT users are unique in our algorithms. In practice, a user can participate in multiple rounds within the same silo across different silos; see Appendix G.4. Finally, for future work, a challenging task is to achieve Olog T) communication cost with correct privacy and regret guarantees; see Appendix D for further discussions.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
XZ is supported in part by NSF CNS-2113222) and CNS-2312835. XZ. would like to thank Abhimanyu Dubey for discussions on the work of Dubey & Pentland (2020). XZ would also like thank Andrew Lowy and Ziyu Liu for insightful discussions on the privacy notion for cross-silo federated learning. XZ would thank Vitaly Feldman and Audra McMillan for the discussion some subtleties behind "hiding among the clones" in Feldman et al. (2022).
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Achraf Azize and Debabrota Basu. When privacy meets partial information: refined analysis of differentially private bandits. arXiv preprint arXiv:2209.02570 2022.
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket of the shuffle model. In Anmual International Cryptology Conference, pp. 638-667, Springer, 2019.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 635-658. Springer, 2016.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differ- ential privacy via shuffling. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 375-403. Springer, 2019.
Albert Cheu, Matthew Joseph, Jieming Mao, and Binghui Peng. Shuffle private stochastic convex optimization. arXiv preprint arXiv:2 10t.0:2000..900 2021.
Sayak Ray Chowdhury and Xingyu Zhou. Distributed differential privacy in multi-armed bandits. arXiv preprint arXiv:2206.00772, 2022a.
Sayak Ray Chowdhury and Xingyu Zhou. Shuffle private linear contextual bandits. In Proceedings of the 39th International Conference on Machine Learning, pp. 9984-4009. PMLR, 2022b.
Roel Dobbe, Ye Pu, Jingge Zhu, Kannan Ramchandran, and Claire Tomlin. Customized local differential privacy for multi-agent distributed optimization. arXiv preprint 1rX.iv:806..00 000506 2018.
Abhimanyu Dubey. No-regret algorithms for private gaussian process bandit optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2062-2070. PMLR, 2021.
Abhimanyu Dubey and AlexSandy' Pentland. Diffeerentially-private federated linear bandits. Ad- vances in Neural Information Processing Systems, 33:6003-6011 2020.
John Duchi, Michael Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 429-438. IEEE, 2013.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 93-44)211-400 2014.
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. pp. 715-724, 2010.
Ú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-SIA SIAM Symposium on Discrete Algorithms, pp. 2468- 2479. SIAM, 2019.
10

---

Published as a conference paper at ICLR 2024
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 Anmual Symposium on Foundations of Computer Science (FOCS), pp. 964. IEEE, 2022.
Evrard Garcelon, Kamalika Chaudhuri, Vianney Perchet, and Matteo Pirotta. Privacy amplification via shuffling for linear contextual bandits. In International Conference on Algorithmic Learning Theory, pp. 381-407. PMLR, 2022.
Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of differential privacy in federated learning. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2021.
Osama A Hanna, Antonious M Girgis, Christina Fragouli, and Suhas Diggavi. Differentillly private stochastic linear bandits:(almost) for free. arXiv preprint trXiv:2207003444 2022.
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. arXiv preprint arXiv:2207.03 106, 2022a.
Jiahao He, Jiheng Zhang, and Rachel Zhang. A reduction from linear contextual bandit lower bounds to estimation lower bounds. In International Conference on Machine Learning, pp. 8660-8677. PMLR, 2022b.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34:27057-27068 2021.
Ruiquan Huang, Huanyu Zhang, Luca Melis, Milan Shen, Meisam Hejazinia, and Jing Yang. Feder- ated linear contextual bandits with user- differential privacy. In International Conference on Machine Learning, pp. 14060-14095. PMLR, 2023.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
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, pp. 403-410, 2014.
Fengjiao Li, Xingyu Zhou, and Bo Ji. Differentially private linear bandits with partial distributed feedback. arXiv preprint arXiv:2207.0587 2022.
Fengjiao Li, Xingyu Zhou, and Bo Ji. (private) kernelized bandits with distributed biased feedback. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):1-47, 2023.
Ziyu Liu, Shengyuan Hu, Zhiwei Steven Wu, and Virginia Smith. On privacy and personalization in cross-silo federated learning. arXiv preprint arXiv:2206.07902 2022.
Andrew Lowy and Meisam Razaviyayn. Private federated learning without a trusted server: Optimal algorithms for convex losses. arXiv preprint arXiv:2106.0977) 2021.
Andrew Lowy, Ali Ghafelebashi, and Meisam Razaviyayn. Private non-convex federated learning without a trusted server. arXiv preprint arXiv:2203.067. 2022.
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, pp. 592-601, 2015.
Tao Qin and Tie-Yar Liu. Introducing LETOR 4.0 datasets. CoRR, abs/ 306.2597,, 2013. URL http://arxiss wwwpiivoor///aeeee http///ab././....... 2597.
Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff. Multi-armed bandits with local differential privacy. arXiv preprint arXiv:2007.03121, 2020.
Touqir Sajed and Or Sheffet. An optimal private stochastic-me algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pp. 5579-5588. PMLR, 2019.

---

Published as a conference paper at ICLR 2024
Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018.
Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling, arXiv preprint arXiv:2210.00557, 2022.
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Differentially private multi-armed bandits in the shuffle model. Advances in Neural Information Processing Systems, 34, 2021.
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uni Stemmer. Concurrent shuffle differential privacy under continual observation. arXiv preprint arXiv:2301.12535, 2023.
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, pp. 1988-1998. PMLR, 2020.
Roman Vershynin. High- digeensiinni probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: How much communication is needed achieve (near) optimal regret. ICLR, 2020.
Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 33:12300- 12310, 2020.
Xingyu Zhou and Jian Tan. Local differential privacy for bayesian optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12):11152-11 2021.
12

---

Published as a conference paper at ICLR 2024
A MORE DETAILS ON RELATED WORK
Private bandit learning has also been studied beyond linear settings, such as kernel bandits (Zhou & Tan, 2021; Dubey, 2021; Li et al., 2023). is worth noting that Chowdhury & Zhou (2022a) also presents optimal private regret bounds under all three DP models (i.e., central, local, and distributed) in bandits while only relying on discrete privacy noise, hence avoiding the privacy leakage of continuous privacy noise on finite computers due to floating point arithmetic.
Recently, Huang et al. (2023) took the pioneering step to study user-level privacy for federated LCBs, establishing both regret upper bounds and lower bounds. In contrast to item-level DP (e.g.. silo-level LDP), user-level DP in Huang et al. (2023) roughly requires that even replacing the whole local history at any agent, the central server's s broadeast message should be close across the whole learning period. This notion is more likely to be preferred in cross-device FL settings where the protection target is the device (agent). In addition to this, there several other key differences compared to our work. First, they deal with linear bandits with stochastic contexts under additional distribution coverage assumptions (rather than the arbitrary adversary contexts our case). In fact, has been shown in Huang et al. (2021) that some assumption on the context distribution is necessary for a sublinear regret under user-level DP. Second, due to this stochastic context and some coverage conditions contexts, exponentially growing batch schedule can be applied in their case. In contrast, under the adversary context case, is unclear to us how to apply the same technique to derive sublinear regret.
B MORE DISCUSSIONS ON GAPS IN SOTA
In this section, we provide more details on the current gaps in Dubey & Pentland (2020), especially on privacy violation and communication cost, turns out that both gaps come from the fact that an adaptive communication schedule is employed in Dubey & Pentland (2020).
B. MORE ON VIOLATION OF SILO-LEVEL LDP
As shown in the main paper, Algorithm in Dubey & Pentland (2020) does not satisfy silo-level LDP. To give a more concrete illustration of privacy leakage, we now specify the form of f², local data X; and synchronized data Z in (1) according Dubey & Pentland (2020). In particular, communication is triggered at round / if for any silo i, it holds that
det 2++ Eb= T. Amin!
(t-t') log
> D,
det (Z +Amin))
where t' the latest synchronization time before f, Z is all synchronized (private) covariance matrices up to time t', Amin > 0 is some regularization constant (which depends on privacy budgets 6) and D 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 3.1. A communication is triggered at round t = if det [1,mm=1.m + +mminI) > det (Amin I) eD holds for any silo m. This implies that (Amin || > e e Xainn which, in turn, yields |
Amin(e" - 1) =: C. Now, if || < C, then silo j immediately knows that ||æı,.1|² > C, where C'is known constant. Since Ii, 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 's private and sensitive information to silo j.
Remark B.I. The above result has two implications: (i) the current proof strategy for Fed-DP guarantee in Dubey & Pentland (2020) does not hold since 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 I in Dubey & Pentland (2020) satisfies Fed-DP, still cannot protect Alice's 's information from being inferred by malicious silo (which is typical
'There is some minor issue in the form of f in Dubey & Pentland (2020). The correct one is given by restatement of their Algorithm see line in Algorithm 3.
13

---

Published as a conference paper at ICLR 2024
adversary model in cross-silo FL). Thus, we believe that silo-level LDP is more proper privacy notion for cross-silo federated LCBs.
B.2 MORE ON VIOLATION OF FED-DP
As shown in the main paper, Algorithm in Dubey & Pentland (2020) also does not satisfy its weaker notion of Fed-DP. To give more concrete illustration, recall Example 3.1 and let us define Mayj as the message/data sent from silo to silo after round = 1. Suppose in the case of Alice, there is no synchronization and hence mi.j = 0. On the other hand, in the case of Tracy (i.e., the first user at silo changes from Alice to Tracy), suppose synchronization is triggered by silo i via rule (1) due to Tracy's ss data. Then, according to Dubey & Pentland (2020), Ma.j = 11,.3/.: + W (only consider bias vector here), where A 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 = 2 needs to be "similar" or "indistingusshable" 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 mi,j. via deterministic selection rule (i.e., LinUCB) in Algorithm I of Dubey & Pentland (2020). Thus, Fed-DP essentially requires maj to be close in probability when Alice changes to Tracy, which is definitely not the case (i.e., O vs. 21, + W.) Thus, Algorithm in Dubey & Pentland (2020) also fails Fed-DP.
Remark B.2. One can also think from the following perspective: the non-private data-dependent sync rule (i.e.. (2)) in Dubey & Pentland (2020) 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 result, whether there exists a synchronization would be "indistinuuisablee under Alice or Tracy and hence mij 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 D for a detailed discussion on this approach.
B.3 MORE ON COMMUNICATION COST ANALYSIS
The current analysis in Dubey & Pentland (2020) (cf. Proposition 5) for communication cost (i.e., how many rounds of communication within 2) essentially follows the approach in the non non-private work (Wang et al., 2020) (cf. proof of Theorem 4). However, due to additional privacy noise injected into the communicated data, one key step of the approach in Wang et al. (2020) fails in the private case. In the following, we first point out the issue using notations Dubey & Pentland (2020).
The key issue in its current proof of Proposition 5 in Dubey & Pentland (2020) is that
det((S.t4n))
D
log de.()
n
which appears right above Eq. 4 in Dubey & Pentland (2020) does not hold. More specifically,
[t, + ne'] is the i-th interval between two communication steps and St,44 are corresponding synchronized private matrices. At the time / t',, we know (2) is satisfied by some silo (say j E [M], since there is a new synchronization. In the non-private case, St, simply includes some additional local covariance matrices from silos other than J. which are positive semi-definite (PSD). As result, (3) holds. However, in the private case, St.nn 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.
C A GENERIC REGRET ANALYSIS FOR ALGORITHM
1
In this section, we first establish a generic regret bound for Algorithm I under sub- Gaussian noise condition, i.e.. Lemma C.4. To this end, let us first give the following notations. Fix B, T E N. we let K- T/B be the total number of communication steps. For all i E [M] and all t kB. k E [K], we let No,; = W.,, - Σt TT and ni, Ü, - Ei Is,iNo,i be the cumulative injected noise up to the k-th communication by agent i. We further let H, :- Nl + Exejy] Nos
and he Lie(M] N2
14

---

Published as a conference paper at ICLR 2024
Assumption C.1 (Regularity). Fix any (0, 1], with probability least 1 a, have H2 is positive definite and there exist constants Amax: Amin and y depending on a such that for all kB, k E [K]
H S Amax:
||
1/Amiu:
| Sv.
With the above regularity assumption and the boundedness in Assumption 4.1, we fist establish the following general regret bound of Algorithm 1, which can viewed as a direct generalization the results in Shariff & Sheffet 22; Chowdhury & Zhou (2022b) the federated case.
Lemma C.2. Let Assumptions C.I and 4.1 hold. Fix any a E (0, 11, there exist choices of and { (e(T,)ET) such that, with probability at least a, the group regret of Algorithm satisfies
Re = =0 0 Bry dMTlog
(1+
MT d'Amin
)
ddmin ))
MT
+
M B .dlog
1+
where Br
2 log (2) + dlog
(1+
MT dDmin
Vmmax + V.
Lemma C.4 is corollary of the above result, which holds by bounding Amax, Amin. V/ under sub- Gaussian privacy noise.
Assumption C.3 Gab-Gaassian private noise). There exist constants ō and 32 such that for all t kB, k [K]: (i) E ne random vector whose entries are independent, mean zero, sub-Gaussian with variance at most oी. and (ii) Σ Nr,; is a random symmetric matrix whose entries and above the diagonal are independent sub-Gaussian random variables with variance most 2. Let o² max ).
Now, ready state Lemma C.4 follows.
Lemma C.4 (A generic regret bound of Algorithm 1). Let Assumptions C.3 and 4.1 hold. Fix time horizon T N, batch size B E [T], confidence level a (0, 1]. Set O(max{L, and Br, rithm I achieves group regret
log (2) + dog (1
Mt
+ for all i [M]. Then, Algo- dA
Reg (T) = (dMB (cMBlog'T log + dVMT MT log (MT(/aa)) +0 with probability at least a.
(olo:)))++((V/o/o////o (VoMTlog(MTT)d) log 1/4 (Tgg/((/((Bo))) (B/()
C.1 PROOFS
Proof of Lemma C.2. We divide the proof into the following six steps. Let & be the event given in Assumption C.I, which holds with probability at least 1 a under Assumption C.I. In the following, condition the event E
Step 1: Concentration. In this step, will show that with high probability, ||o- 0.. llv. Se,
for all i E [M] Fix an agent i [M] and t E [2]. let flast be the latest communication round of all agents before By the update rule, have
0i, = Ve,i (Usyn U4)
M tru
M
V
Te
+
Σ
+
Dogilaai
j=l
8 smbrrt+1
tus ΣΣ
Newn
Σ
JaiiMss
Σ
Ia.illasi
1=
j=1
j=1s=1
amtartt
15

---

Published as a conference paper at ICLR 2024
By the linear reward function Ya.j have
(Ia.j. )*) May for all j E [M] and elementary algebra,
M
Apa
t-1
0" -r, ViJi Home 0"
Σ
Σ
L Ta,illas
j=1e=1
where we recall that Hamm AT + Neww and hima
j==l Mened
Thus, multiplying both sides by 1/22 yields
100- 062 -o-s-llms
Σ Ts,
-| 0" Ilv O1ye, + | live
Ve
(a)
Nia
Σ
Tag +
Σ
Na
+110 1 + +IIhessull I1
s=ta++
M
Σ
Ta
Amax
m=1
s=tua+
(Gr
M Eie I. where (a) holds by Vi,i Hise and Vi 2 Gt Aminl with G Σ
Lomturth fam L. 5,8 (i.e., non-private Gram matrix) under event E; (b) holds by the boundedness of 0* and event E.
For the remaining first term, we can use self-normalized inequality (ef. Theorem in Abbasi- Yadkori et al. (2011)) with proper filtration". In particular, we have for any a E (0, 1]. with probability at least 1 - a, for all E [T]
M
Moj
Σ 8=tart
To
2 log
-
+ log
(det(Gr, + Amin
det((miil))
(Gi,:-Aunl Amm
Now, using the determinttnn lemma (cf. Lemma 10 in Abbasi- Yadkori et al. (2011)) and the boundedness condition on ||
for all E [T' and j E [M.]. we have
Mt d
(et Amin S
[Amin
Putting everything together, we have with probability at least 1 2o, for all i E [M] and all e [T]. 0r
0m
Vi. < Br,i
Br, where
- 2
Mt ddmin
B
2 log
+ dloog
1+
Amaa + u.
(4)
Step 2: Per-step regret. With the above concentration result, based on UCB policy for choosing the action, we have the classic bound on the per-step regret Tt.s, that is, with probability at least
1 2a
T1.
10", (0", - (0", 2,,1)
(a)
(0* ;.())) UCB,,;(at,) + UCB,, - (FL.) + UCB,,( (0",x).))
0 + 23,,, | (y $ 2 || Vl
where in (a), we let (C),, = (o.,,, x) + :r ||=lly, (b) holds by the optimistic fact of UCB (from the concentration), greedy action selection, and the concentration result again.
In 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 factor of M.
16

---

Published as a conference paper at ICLR 2024
Step 3: Regret decomposition by good and bad epochs. In Algorithm 1, at the end of each synchronization time t = kB for k E [K], all the agents will communicate with the server by uploading private statisties 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 [x)] where 4 = kB is the k-th syne round. We define Va= Amin/ + Ei= Σi= F,, 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 "good" epoch if dec(VVx)
det(V(-1) I
2; otherwise it "bad" epoch.
Thus, we can divide the group regret into two terms:
Regar (T) = Σ E
Σ
T2 +
Tr,
éE[M] rEgood epochs
*E[M] rEbad opochs
Step 4: Bound the regret in good epochs. imaginary single agent that pulls all the MT actions in the following order: F1,1, AII.M,,2,11111....
To this end, we introduce an
22.M............................ "T..M....ITII................... TT,M- We define a corresponding imagi- nary design matrix Ve, = Amin + -ppet.e((]] Tp.0 + Ep Tp.o p.q" i.c. the design matrix right before zt,i- The key reason behind this construction that one can now use the standard result (i.e.. the elliptical potential lemma (cf. Lemma 11 in Abbasi- Yadkori et al. (2011))) to bound the summation of bonus terms, i.e., Σ.,; ||ar,illl
Suppose that & E [7] within the k-th epoch. One key property we will use that for all i, V22 > V and Gt + Amin I = Vi-1, which simply holds by their definitions. This property enables to see that for any & E good epochs, dct(Vi,)) dct(Gr,; + Amiu S 2. This is important since by the standard "determinant trick", we have
S @2
(5)
In particular, this follows from Lemma 12 in Abbasi- Yadkori et al. (2011), that is, for two positive definite matrices B, E Rdxd satisfying A B, then for any R ||]|| S | / /et (A)/ det(B), Note that here we also use det(A) 1/ dede(A--), Hence, we can bound the regret in good epochs as follows.
Σ Σ
Σ
Σ
m2n | .1}
&Egood epochs
(E[M/
rEgood epochs
Σ
min | (G ( 11
*E[M]] tEguol epochs
Σ
min(2V288 | (
iE[M] (Egood epochs
Σ
2V2,8, min minfllaeeelll.. 11
AE[M] (Egond epochs
Σ Σ
2V23r minfllee.sll ,1]
[E[M] LE|T
( Bry aMTllg
MT
o
1
(6)
ddmin
where (a) holds by the per-step regret bound in Step 2 and the boundedness of reward; (b) follows from the fact that Vz, 2 Gt + T under event ε; (c) holds by (5) when t is in good epochs; (d) is true since 3T 2 1; (c) holds by the elliptical potential lemma (cf. Lemma 11 in Abbasi-Yadkori et al. 12)1
Step 5: Bound the regret in bad epochs. Let Thna be the total number of rounds in all bad epochs. Thus, the total number of bad rounds across all agents M Toad- As result, the cumulative group regret in all these bad rounds are upper bounded by M Thad due to the to the boundedness of reward.
17

---

Published as a conference paper at ICLR 2024
We are left to bound bad All need is to bound the Neud total number of bad epochs. Then, have Thad = Noad B. where the fixed batch size. To this end, recall that K = T and define ik [K] log det(Vi:) - log det det(Vk- (Vx-1)
log 2). i.e., Noad | Thus, we have
log 2 | -
log deg)) log det (ve(
Σ kE|K]
log det (Vx) - log det (Va-1)
KEW
MT
S d doog
1
dAmin
Hence, we have Mbad as follows.
|
S
d log2
log (1
MT ddmnn
Thus we can bound the regret bad epochs
d
MT dAmin
T1, S M Tond M B Noad M B
log
1
1+
(7)
log 2
ME[M] rEhad epochs
Step Putting everything together. Now, we substitute the total regret good epochs given by (6) and total regret in bad epochs given by (7) into the total regret decomposition in Step 3, yields the final cumulative group regret
Reg (T) 0 STy dMTlog (1+
MT d'wain
+ + M. B- d. (1
MT
dAmin
where BT = 2 log (2) + dlog
11
MT ddmin
+
Amax + V. Finally, taking union bound, we
have the required result.
Now, we turn to the proof of Lemma C.4, which is an application of Lemma C.2 we just proved.
Proof of Lemma C.4. To prove the result, thanks to Lemma C.2, we only need to determine the three constants Amax: Ami and under the nab-Gaussian private noise assumption Assumption C.3. To this end, we resort to concentration bounds for sub- mub-Gaussian random vector and random matrix.
To start with, under (i) in Assumption C.3, by the concentration bound for the norm vector containing sub- Gaussian entries (cf. Theorem 3.1.1 in Vershynin (2018)) and union bound over all communication rounds, we have for all f kB where k [T/B] and any a (0, 1], with probability at least 1 - ax22, for some absolute constant CI.
M
Σ
= ||ail| s E, = c . (Vd+ + Vlog(T/(aB)).
nt.i
By (ii) Assumption C.3, the concentration bound for the norm of sub-Gaussian symmetric random matrix (cf. Corollary 4.4.8 in Vershynin (2018)) and union bound over all communication rounds, we have for all kB where [T/B] and any a (0,1), 1]. with probability least 1 - a/2,
M
Σ
N1.4
< EN = 02 02 (Vd + (log(T/(BB))
for some absolute constant C2. Thus, we choose À = NE we have HH = Aaa + MM No.
N.'N i.e. Amax NEN, and Amin Dv. Finally, determine v, note that
[hella, Vmmin |hell c (o (Vd + VTo((T/(BB))
where a = max 32}. The final regret bound is obtained by plugging the three values into the result given by Lemma C.2.
D DISCUSSION ON PRIVATE ADAPTIVE COMMUNICATION
In the main paper and Appendix B, we have pointed out that the gap in privacy guarantee of Algorithm 1 in Dubey & Pentland (2020) is that its adaptive communication schedule leads to privacy leakage
18

---

Published as a conference paper at ICLR 2024
Algorithm 3 Restatement of Algorithm 1 in (Dubey & Pentland, 2020)
1: Parameters: Adaptive communication parameter D. regularization À > 0. confidence radii
(EM feature map Φ C, x K; + R,, privacy budgets & > 0, 8 E [0. 1].
2: Initialize: For all i [M], W; 0, U. = PRIVATIZER with 6, W syn 0, Usyn 0,
3: for 1=1,..., T do
4: for each agent i 1,, ,..., M do
5:
Vi, = Al + Wyn + W,, Oz, = V (Usy Ui)
6: Play arm ot2 argmax (0: a), 0e.e) + Be, (oo,(c,, allly and set Ft,.
di(ct,i ax,))
7:
Observe reward yt
8:
Update W; = W1 Te, T Uj = U; + iz,ittt.
9:
if log (Vi, + =,,,) log det (Van) ايt
D then
10:
Send signal to the server start synchronization round. end if
11:
12:
if synchronization is started then
13:
Send W; and U, to PRIVATIZER
14:
PRIVATIZER sends private cumulative statistics We,i, Up. to server M Server aggregates W syn W Σ3= Wes and Usyn Üngn Ej= M
15:
Uni
16:
Receive W syn and Usy from the server
17:
Reset W; = 0, U₃ O, 4tst and Vin Al + W sgm
18:
end if
19:
end for
end for
due to its dependence non- non-private data. As mentioned in Remark 1.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 Ollog T) communication does not hold. Moreover, this new approach will also lead to new challenges regret analysis, when compared with its current one in Dubey & Pentland (2020) and the standard one in Wang et al. (2020).
To better illustrate the new challenges, let us restate Algorithm in Dubey & Pentland (2020) using our notations and first focus on how 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.
As shown in Algorithm 3, the key difference compared with our exed-batch schedule is highlighted in color. Note that we only focus on silo-level L.P and use PRIVATIZER to represent general protocol that can privatize the communicated data (e.g., P or the standard tree-based algorithm in Dubey & Pentland (2020)).
D. REGRET ANALYSIS UNDER NON-PRIVATE ADAPTIVE SCHEDULE
In this section, we demonstrate the key step in establishing the regret with the non non-private adaptive communication schedule Algorithm 3 (i.e., line 9). It turns that the regret analysis very similar to our proof for Lemma C.2 for the fixed batch case, in that the only key difference lies in Step 5 when bounding the regret in bad epochs². The main idea behind adaptive communication is: whenever the accumulated local regret at any agent exceeds threshold, then synchronization is required to keep the data homogeneous among agents. This idea is directly reflected the following analysis.
'There is another subtle but important difference, which lies in the construction of filtration that is required to apply the standard self normalied inequality to establish the concentration result. We believe that one cannot directly use the standard filtration (c.g., Abhasi-Yadd Yadkori et al. (2011)) in the adaptive case, and hence more care indeed required.
19

---

Published as a conference paper at ICLR 2024
Bound the regret in bad epochs (adaptive communication case). Let's consider arbitrary bad epoch k i.e., (fx-1, fx], where fy is the round for the k-th communication. For all i, we want to bound the total regret between tx],, denoted by R. That is, the local regret between any two communications (in the had epoch) will not be too large. For now, suppose we already have such bound U (which will be achieved by adaptive communication later), i.e., R U for all i, k, we can easily bound the total regret in bad epochs. To see this, recall that v = { E [K] log det(Vi) log det(V=-1) > log 2), i.c., .bad = / , we have
Σ
Σ
Te,i Σ> R = (UV
i tEtad epochs
kEW
Plugging in Noad = | S log? log (1 + dx-), 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
Σ 1
Tei S
Σ
m2n IIre, 13
(8)
IEIISTEE
(b)
Ory. (lx fh-- log
det Venw det Vnnst
0 (3TVD)
where holds by boundedness of reward; (b) follows from the elliptical potential lemma, i.c., Vlass is PSD under event & and V = V,-1, + 22-1,5% for all i E (4x-1. fx); (c) holds by the adaptive
schedule in line of Algorithm 3. As result, we have R O (7 (TVD) + 1, where the regret round t is at most 1 by the boundedness of reward. With proper choice of D, one can obtain final regret bound.
D.2 CHALLENGES IN REGRET ANALYSIS UNDER PRIVATE ADAPTIVE SCHEDULE
Now, we will discuss new challenges when one uses private data for an adaptive communication sched- ule. In this case, one needs to first privatize the new local gram matrices (e.g.. E'= +1 I T before being used in the determinant condition. This can be done by using standard tree- tree-based algorithm with each data point as x. x s,5* becomes
s,i)
With this additional step, now the determinant condition
D
log det (V.,) log det (elet((isn (Viaa)
(10)
where Vi, Vintt + E Ex=hutt Zz.i% schedule up to time t. Now suppose one uses (10) to determine t.- Then, it does not imply
T a + Nlox and N/ac is the new local injected noise for private
det(V).)) S D' does not necessarily mean that that (9) is upper bounded by BTVD. That is, det(Vine det E -i- T. < D'. det(Vine)
One may try work around (8) by first using Gt.; + Amin to lower bound Vr,i. Then, (9) becomes det(Gr a Aminn
o Br (rr/(e (tx 1x-1) log des(Gr, 4 Amin))
which again cannot be bouded based on the rule given
by (10). To see this, note that dee(V dee(Ve,-1.)) det(
D' only implies that det(Gr, + Aminn)) det(Geg Amaxe) $ D'.
<
E ADDITIONAL DETAILS ON FEDERATED LCBs UNDER SILO-LEVEL LDP
In this section, we provide details for Section 5.1. In particular, we present the proof for Theorem 5.1 and the alternative privacy protocol for silo-level LDP.
20

---

Published as a conference paper at ICLR 2024
E.1 PROOF OF THEOREM 5.1
Proof of Theorem 5.1. Privacy. We only need to show that P in Algorithm 2 with proper choice of do satisfies (e, dDD for all l E [K] which implies that the full transcript the communication private in Algorithm for any local agent i.
First, we recall that the (multi-variate) Gaussian mechanism satisfies zero-concentrated differential privacy (zCDP) (Bun & Steinke, 2016). In particular, by Bun & Steinke (2016, Lemma 2.5), we have that computation of each node (p-sum) in the tree is p-zCDP with p 20g
L2² Then, from the
construction of the binary tree in P. one can easily see that one single data point Y (for all E [K]) only impacts at most + log( nodes. Thus, by adaptive composition of zCDP (cf. Lemma 2.3 in Bun & Steinke (2016)), we have that the entire releasing of all p-sums is (1 + log K) p-zCDPP Finally, we will use the conversion lemma from zCDP to approximated DP (cf. Proposition 1.3 in Bun & Steinke (2016)). In particular, we have that Po-zCDP implies (E = Pu + 2 2v log (18))) 8)-DP for all 8 0. In other words, achieve given (e, 6)-DP, it suffices to achieve Pn-2CDP with Po f(e, ;= (vlog(L/8) + Vlog(1/8)) In our case, we have Po (1 + (og(K))p 1.2 (1 + log( ({)) 1.2 Thus, we have of (1 log( K)) L² (1 + log( K)) 2)(2,5) To simply it, one
20g
can lower bound f(e, 5) by 1og((188)448 (cf. Remark 15 in Steinke (2022)). Therefore, to obtain 22
(c, 6)DD, it suffices to set of = 2. I.2 (1+Hog((K)(log(())))+) Note that there are two streams of data in Algorithm 1, and hence it suffices to ensure that each of them is (c/2, 6 6/2)-DP. This gives us the final noise level of = (1++lgg (K) ((og((26)))))) (note that by boundedness assumption L = 1 in our case).
Regret. In order to establish the regret bound, thanks to Lemma C.4, we only need to determine the maximum noise level in the learning process. Recall that of = 8 (1+Hog( (i)log(())))og)22))))+ is the noise level for both streams (i.e., bis and " Now, by the construction of binary tree in P, one can see that each prefix sum [1, k] only involves at most 1 + log(k) tree nodes. Thus, we have that the noise level in n4,; and No,; are upper bounded by (1 + log log(K)) )og. As result, the overall noise level across all M silos is upper bounded by o M(1 + log( K )og Finally, setting o² in Lemma C.4 to be the noise level m yields the required result.
e²
E.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 (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 Dubey & Pentland (2020).
It can be seen that both privacy and regret guarantees under this Palt are the same as Theorem 5.1. To see this, for privacy, the prefix sum 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 5.1, hence the same as the prefix sum. Meanwhile, the total noise level at the server is the same as before. Thus, by Lemma C.4, we have the same regret bound.
F ADDITIONAL DETAILS ON FEDERATED LCBs UNDER SDP
In this section, we provide more detailed discussions SDP and present the proof for Theorem 5.3 (SDP via amplification lemma) and Theorem 5.5 (SDP via vector sum).
First, let 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 P rather than the noisy prefix sum (i.e., the sum from beginming as done in Dubey & Pentland (2020)) plays a key role in achieving optimal regret with shuffling. To see this, both approaches can guarantee selol L.P. By new amplification lemma, privacy guarantee can be amplified by 1/VM in for each
21

---

Published as a conference paper at ICLR 2024
Algorithm 4 Patr. alternative privacy protocol for silo-level LDP
1: Procedure: Local Randomizer R
2: // Input: stream data = (ni)εekki privacy parameters e, Output: private prefix
sum
3: for k= k= K do
4: Express I in binary form: lt E, (k) (k)- -2
5:
Find the index of first one in = min(j Bin,(k) = Compute p-sum Oii, Ejct Cjj 7k.
6:
7: Add noise p-sum ag ai, + (0
8: Output private prefix sum &% Ey:tin āj
9: end for
end procedure
11: Procedure: Analyzer A
// Input: a collection of M data points, y = (Uilvet Output: Aggregated sum Output ÿ = >EEMM] Vi end procedure
of the K shuffled outputs, where K T/B is total communication rounds. Now, if the prefix sum released to the shuffler, then any single data point participates in at most K shuffle mechanisms, which would blow up E by a factor of (VVK) (by advanced composition (Dwork & Roth, 2014)). This would eventually lead to a 1/4 factor blow up in regret due to privacy. Similarly, if we apply Pvec to the data points in the prefix sum, then again single data point participate in most K shuffled outputs.
On the other hand, if only noisy p-sums released for shuffling at each communication round k E [K] (as in our protocol P) or only the data points in each p-sum are used in Pvsc (as in our protocol in PT then due the binary-tree structure, each data point only participates in at most log K shuffled mechanisms, which only leads to O (Vlog K) blow-up of E; hence allowing to achieve the desired ((VMT) regret scaling, and close the gap present under silo-level LDP.
Remark F.1 (Shuffled tree- based mechanism). Both the protocol P in Algorithm 2 along with our new amplification lemma and protocol PT in Algorithm 5 can be treated 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.
F.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 amplifica- tion via shuffling (e.g., Feldman et al. (2022); Erlingsson al. (2019); Cheu al. (2019); Balle et al. (2019)) are only limited to the standard LDP case, i.e., each local dataset has size = 1, which is not applicable our case where each silo runs DP (rather than LDP) mechanism over a dataset size = T: (ii) Although a recent work (Lowy& & Razaviyayn, 2021) establishes general amplification result for the case of 1, introduces very large value for the final 5 that scales linearly with due to group privacy.
We first present the key intuition behind our new lemma. Essentially, as in Lowy & Razaviyayn (2021), we follow the nice idea of hiding among the clones introduced in Feldman al. (2022). That is, the output from silo to n can similar to that of silo 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 and (j > 1) will be larger as in this case all n > 1 data points among two silos could be different. To capture this, Lowy & Razaviyayn (2021) resorts group privacy for
22

---

Published as a conference paper at ICLR 2024
general DP local randomizers. However, group privacy for approximate DP will introduce large value for 8. Thus, since we know that each local randomizer in our case is the Gaussian mechanism, capture the similarity of outputs between silo and j (i > 1) by directly bounding the sensitivity. This helps to avoid the large value for the final 8. Specifically, we have the following result, which can be viewed as a refinement of Theorem D.5 in Lowy & Razaviyayn (2021) when specified to the Gaussian mechanism. We follow the notations in Lowy & Razaviyayn (2021) for easy comparison.
Lemma F.2 (Amplification lemma for Gaussian mechanism). Let X =X1, X xn be a distributed data set, iee, N silos each with n data points. Let r E N and let DP, so E (0,1)', for all = (1-N) E 2(r-1)xN and i E [N], where X is an arbitrary set. Suppose for all i, maX (x,x1) | (Z. (R, R. (R (Z.X)) S n
(X1,'.. (N)
x" + E = gd be a Gaussian mechanism with (e): %))-
maXadjacem X.)) R (Z, X) R R (Z,X') Given Z 2ur-1y consider the shuffled algorithm A XuXN x 2(r-1)xN + N that first samples a random permutation x of [N] and then computes Z, (Z that o < n In
....,,,)) N( where 21") R2O (2, (Z,X+()) Then, for any 8 [0. such
N 16log(2/8)
A² is (E",, "8")" where
e c
8ve log(4/0) SE
e= ln
1+
VN
c
8" =
8 N(E" + 0
c
+
(sV/oo(]/mmna) (
I & 1/n, choosing 8 = Nndz yields Ex O
and 8 = O(N8)), where
VN
% S 1/(n.).
F.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 E. This comes from two factors: one is due to the fact that standard 1/ /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 = T, which further reduces the range of valid e.
In this section, we give the vector sum protocol in Cheu et al. (2021) for easy reference. Let's also give concrete example to illustrate how to combine Algorithm 6 with Algorithm 5. Consider fixed k = 6. Then, for each agent, we have 0i. 7T6 + 76. That is, consider the case of summing bias vectors, for agent E [M]. 7s- Lt=4B41 Ft,, and io >t=bB+1 Lt, Then, D& consists of 2B data points, each of which is a single bias vector. Now, Rvee and Avee (as well the shuffler) work together to compute the noisy sum of 2B M data points. In particular, denote by Pres the whole process, then we have 0; = (D ), where D. is the data set that consists of n = 2B M data points, each of them single bias vector.
Next, we present more details on the implementations, i.e., the parameter choices of b. Let's consider k- 6 again as example. In this case, the total number of data points that participate in Proc is n = 2B M. Then, according to the proof of Theorem C. in Chowdhury & Zhou (2022b),
'This is because it mainly focuses on the lower bound, where one needs to be general to handle any mechanisms.
7 Note that standard Gaussian mechanism only applies to the regime when s < 1. In our case, ep is often less than 1. Gaussian mechanism also works for the regime & >> 1, in this case, x² ~ 1/s rather than 1/62. With minor adjustment of the final e", our proof can be extended.
*This w.l.o.g: one can easily generalize it to any upper bound that is a function of n. In our application, each data point means bias vector or covariance matrix. See Appendix F22 for concrete example.
23

---

Published as a conference paper at ICLR 2024
Algorithm 5 Vec another privacy protocol used Algorithm
1: Procedure: Local Randomizer R at each agent
2: // Input: stream data (71,--. 7kk, privacy budgets 0, E (0,
3: k=r K do
4: Express k in binary form: k 2; (k) -
5: Find index of first one i min Biny (k)
6: Let Dj: be the of all data points that contribute to ai Ejec aj + 7k
7: Output ys (eve((D)) // apply Rive Algorithm to each data point
8: end for
9: Procedure: Analyzer A at server
10: // Imput: stream data from S: {ūx- (Jk,1 DN.M)
11: for k=rk=..... do
12:
Express k in binary and find index of first one
13: Add all messages from agents: Oii = Avec(Tl) // apply Avec in Algorithm
Output: 3%
end for
we have
24 10 g2. (log ((( p= 1/4.
6
m- b
22n
Algorithm Prec, shuffle protocol for vector summation (Cheu al., 2021)
1: Input: Database of d-dimensional vectors (x ;Xa); privacy parameters e, 6; L.
2: procedure: Local Randomizer Rvee (x.)
3: for [d] do
4: Shift component to enforce non-negativity: Waj f- Xi.j L
5: m, < 1-R1((W5.))
6: end for
7: Output labeled messages (UJmm))
8: end procedure
9: procedure: Analyzer (y)
for [d] do
11: Run analyzer on coordinate j's messages zj + AiD(y))
Re-center: 0j + 2j n.
13: end for
14: Output the vector of estimates o = (0 08)
15: end procedure
Algorithm 7 PID, a shuffle protocol for summing scalars (Cheu et al., 2021)
1: Input: Scalar database X [=r,.... ........)))))) xr)) [0, Z,":g,b b N:p E (0, 1))
2: procedure: Local Randomizer (xp(x:)
3: Z [.]
4: Sample rounding value 7) ~ Ber( L Z.).
5: Set 2; 3; 7/1-
6: Sample privacy noise value ~ Bin (b.p).
7: Report y; E (0, 19 containing 3; + 7/2 copies of and g + (3, + 12) copies of
8: end procedure
9: procedure: Analyzer
10: Output estimator 1
(O Ebt((y))) - pbn).
11: end procedure
24

---

Published as a conference paper at ICLR 2024
F.3 PROOFS
First, we present proof of Theorem 5.3.
Proof of T'hhorrm 5.3. Privacy. In this proof, we directly work on approximate DP. By the bound- edness assumption and Gaussian mechanism, we have that with oه 21.² log( (.25/8o)) R. in P is
Eg
(Eo, -DP for each communication round & E [K] (provided En S 1). Now, by our amplification lemma (Lemma F.2). we have that the shuffled output (E, 8)DD with ē o &o GoVlog1//TTMó))
VM
and 8- 0o) (provided Eo < 1/T and do S 1/(MT) Here we note that in our case, N M and n = T. where n = T follows from the fact that there exists a; 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- sewtiiiing-then-shieee then-shuffiig the outputs. Next, we apply the advanced composition theorem (ef. Theorem 3,20 in Dwork & Roth (2014)). In particular, by the binary tree structure, each data point involves only K = + log( K) times the output of R. Thus, to achieve OD,P, it suffices to have E
22 log(2/5) and ā
4 Using all these equations, we can solve 2x
EVM for Eo C1 VN (0 (6T() and 80 = C2 Mx for some constants C1 and C2 > 0. To
satisfy the conditions on Eo and 8g. we have S TVM and 8 S T.T
vk
With the choice of En and Thus, we can apply P
8o. we have the noise variance of = O 22 Bogglog(1/b) (6g()/(67)) log(MM/8)) to the bias and covariance terms (with L 1), respectively.
Regret. Again, we simply resort to our Lemma C.4 for the regret analysis. In particular, we only need to determine the maximum noise level in the learning process. Note that of
O 2L (2L"xlog(1/5) (og(1/)()))))) loggoo( (og(e/((11)) log(Mxx8))
is the noise level injected for both bias and covariance terms.
:²M
Now, by the construction of the binary tree in P. one can see that each prefix sum only involves at most + log(k) tree nodes. As result, the overall noise level across all .M silos is upper bounded
by o M.j.. Finally, setting o² in Lemma C.4 to be the noise level o yields the required result.
Now, we prove Theorem 5.5.
Proof of Theorem 5.5. Privacy. For each calculation of the noisy synchronized p-sum, there exist parameters for Pvve such that it satisfies (Eu, 60D- where eo E (0. 15) and dn (0, 1/2) (see Lemma 3.1 in Cheu et al. (2021) or Theorem 3.5 in Chowdhury & Zhou (2022b)). Then, by the binary tree structure, each single data point (bias vector or covariance matrix) only participates in at most k = 1+ log( K) runs of Pvee Thus, to achieve (e, 6)-DP, it suffices to have Eo
2 2/g2clog(//8
and 6 = 6. by advanced composition theorem. Thus, for any & E (0, 3 2x log(2/8) and 2x
8 (0, 1), there exist parameters for Pvec such that the entire calculations of noisy p-sums are (c, (3.5))5 SDD. Since we have two streams of data (bias and covariance), we finally have that for any
E (0, /2x log(2/0) (2/)) and d e (0, 1), there exist parameters for Pooc such that Algorithm I with PT satisfies (s, SD-SDP
Regret. By the same analysis in the proof of Theorem 3.5 Chowdhury & Zhou (2022b), the injected noise for each calculation of the noisy synchronized p-sum is sub- Gab-Gaussian with the variance
being at most 6² = 0 (dP (60) = =0 (lo[(1/8) (dPw/6) Now, by the binary tree structure, e
each prefix sum only involves at most &S p-sums. Hence, the overall noise level is upper bounded by owall = kō? Finally, setting o² in Lemma C.4 to be the noise level o yields the required result.
Now, we provide proof of amplification Lemma F.2 for completeness. We follow the same idea as in Feldman et al. (2022) and Lowy & Razaviyayn (2021). For easy comparison, we use the same notations in Lowy & Razaviyayn (2021) and highlighted the key difference using color text.
25

---

Published as a conference paper at ICLR 2024
Proof of Lemma F.2. Let Xu, E x=x be adjacent distributed data sets (i.e. 1). Assume WLOG that X (Xp, X2. Xx) and X1 = (X,, .N), where Xi = (1100.122 ;1,,) # (21.1 F1,n) We can also assume WLOG that X3 & (XP, x for all j E {2.... ,N, by re-defining X' and R,0 if necessary.
N 2j=1 1 (
Li=l
Fix i E [N E [R] Z -1r-1 2 (1x-11) E z(r-1)xN, denote R(X) R2 (Z, X) for
X E X", and (x == (2 X). Draw x uniformly from the set of permutations of [N].
R(XT), so by Lowy & Razaviyayn (2021, Lemma D.12), Now, since R. is (c): -DP R(X)) (Eg.g)
there exists local randomizer R' such that R'(X (c).0)
R(XP) and (V)) R(X)) 56-
Hence, by Lowy & Razaviyayn (2021, Lemma D.8), there exist distributions UXP)) and (X}))
such that
e5
R(X)) e U(X))+
U(X)
(11)
e +
and
c
R'(x c + U(X9) + e + 1 ((
(12)
Here, we diverge from the proof (Lowy & Razaviyayn, 2021). We denote Eo == net and
50 = %- Then, by the assumption of R(X), for any X, we have R(x) (E0,50)
R(x))) and
R(X)
R(X))). This is because by the assumption, when the dataset changes from any X to (En.5))
X7 (or X)), the total change in terms of l2 norm can be n times that under an adjacent pair. Thus, one has to scale the o by n while keeping the same o7.
Now, we resume the same idea as in (Lowy & Razaviyayn, 2021). By convexity of hockey-stick (R( + R(x))) == p for all X E X divergence and the above result, we have R(X) (E0.
That is, R is (Eo. 8n) deletion group DP for groups of size n with reference distribution p. Thus, by Lowy& & Razaviyayn (2021, Lemma 1.1,), we have that there exists local randomizer RR such that (X) and p are (Eu. 0) indistinguishable and TV (R" (X). R(X)) < 8 for all X. Then by the definition of (Eg, 0) indistinguishability. for all X there exists a "left-over" distribution LO(X) such that R"xX)= = p + + (1 1/e50 LO(X) = 2oto (R(x)) + R(X))) + ) LO(X..
Now, define randomizer L by L(XP) = R(XX), ((X)) = R'( and 1
1
[(X) = 0 R(X9)= + 00
R' R'(X)) + -1-11) ((1
1
U(X9) 2000 u(}+) + (1
(13)
2000
for all X E xa \ that (VX()X)),
(The eeuuelall follows from (11) and (12).)
Note
0.
(V(R(X)),<())
& %. and for all X E
x
(X9, Xl). TV(R(X),
< TV(R(X), + TV(R"(X), <
o
Zero (XX)) =1
Keeping r fixed (omitting r scripts everywhere), for any i [N] and Z := E 1)x- let 2 (Z. (7() (Z. -). and (+) (Z. -) denote the randomizers resulting from the process described above. Let Ac : X - N be defined exactly the same way as A = A, (same π) but with the randomizers R replaced by L(,), Since A, applies each randomizer (() exactly once
and (2()(Z,)) X ... R(N) X Xx(N)) are independent (conditional on Z = Zirr-1) 10 we have TV (X,) & N(1+ + 26 )ōb and
< N(1+ + " )og Now we
This follows from the assumption that R (Z X) is conditionally independent of X' given Z for all Z and X # X".
26

---

Published as a conference paper at ICLR 2024
claim that Ax(X)) and Ag(X1) ) are (E". indistinguishable for any d > 2E 2e-Ne= Ne 116 Observe that this claim implies that A. and A. (X,, are (=",8") indistinguishable by Lowy & Raza- viyayn (2021, Lemma D.13) (with P := Ac(X)), == Ac(X,), P= A. (Xo). Q (X))))
Therefore, it only remains to prove the claim, i.e. to show that Der (c & 5 for any > 2e De-Ne Ne Ne-" /16.
(Z, i Xi
Now, define 2 X) =
(Z X+)
if X
For any inputs Z, X, let (u, X) be
( (2,
otherwise.
defined exactly the same as A, (Z, X) (same T) but with the randomizers R( replaced by c( Then by (11) and (12),
e
1 Au (Xo) 5 + Au (Xi) and Ac(Xi) e Au (Xo)
e (x
Ax(Xo)=
e +
- +
(14)
Then by (13), for any X X² (xX. } and any Z Zi E 1) we have 4 (Z.X) (1) 20 C (Z, (I) + 1
2c Ly (Z, (1 Eo (Z, Hence, Lowy & Razaviyayn (2021,
Lemma D.10) (with/ p = co = e neb) implies that Ar (Xo) and (Xi)) are
log (1 1+
8 8 e In(4/0)
.
VN
N
indistinguishable for any 5 > 2e -NeNNenn
Here, we also slightly diverge from Lowy & Razaviyayn (2021). Instead of using Lowy & Razaviyayn (2021, Lemma D.14), we can directly follow the proof of Lemma 3.5 in Feldman et al. (2022) and Lemma 2.3 in Feldman et al. (2022) to establish our claim that AX(o)) and Ac(Xi) are indistinguishable (hence the final result). Here, we also slightly improve the 5 term compared to Feldman et al. (2022) by applying amplification via sub-sampling to the 5 term as well. In particular, the key step is rewrite (14) as follows (with T == { (X.) + (X,))
2
e
T e
Ac(Xo) = e0 +1 e +1
Au (Xo) and (x)) = e +
e6 + Au (X1). (15)
Thus, by the convexity of the hockey-stick divergence and Lemma 2.3 in Feldman et al. (2022), we have Ax())) and Ac(X1) are
5
8 e In (4/8r)
S N
5
log
1+
+
8
6 +1
VN
indistinguishable for any > 2e 2eeNe-=th Ne- /16 As decribed before, this leads to the result that A. (X.) and (X1, are (s", 8")) indistinguishable by Lowy & Razaviyayn (2021, Lemma D.13) (original result in Lemma 3.17 of Dwork & Roth (2014)) with (noting that En = nE
666-1
+1)
(8ve e In(4/5)
ex := 1+
+
VN
N
c
8" =
8 N(6
+ + 12200
c +1
G FURTHER DISCUSSIONS
In this section, we provide more details on our upper bounds, privacy notion and algorithm design.
G. DISCUSSION ON TIGHTNESS OF UPPER BOUNDS
In the paper, we have established regrets of ((33/4 VT/E) under silo-level LDP and O /MMT/// under SDP. An essential open question is regarding tightness of these upper bounds. It turns out that
27

---

Published as a conference paper at ICLR 2024
the key to obtain both lower bounds is to first establish tight characterization for single-agent LCB under central JDP (which is still open to the best of our knowledge), as elaborated below:
SDP: The current upper bound aligns with the state-of-the under central JDP. However, the tightness of this bound is still uncertain, as it even remains open whether the upper bound under the centralized setting is tight. To our best knowledge, the only existing lower bound for LCBs under central JDP is QVVT + 1/E) (He et al., 2022b), implying lower bound of D(VMT- + 1/e) for the super single agent case. That is, the privacy cost in the lower bound is only additive rather than multiplicative cost of VE present in the upper bound. It is unclear to us which one of the upper bound or lower bound loose.
result achieved by a super single agent
Silo-level LDP: A lower bound can potentially be established using similar reduction as in Lowy & Razaviyayn (2021), where the authors derive a lower bound for silo-level LDP supervised learning via the central model. To be more specific, for any silo-level LDP algorithm AA with privacy guarantee Eo, one can first "virtually" shuffle all the MT user sequences and then apply A, leading to a shuffled version A.. As shown in Lowy & Razaviyayn (2021),, the shuffled version algorithm A, enjoys an SDP privacy guarantee of roughly E == 5o/ M (here again, one cannot directly use standard amplification lemma). Since SDP implies central JDP in our linear contextual bandit case, then one can conclude that Ag has a lower bound of Lc(E), where (E( denotes the lower bound for LCB under central JDP with privacy guarantee E. Finally, one can note that A and Ag have the same regret performance, hence establishing the regret lower bound Le V /M) for A under silo-level LDP.
Implication: If one can establish a lower bound [=(()) = St (T/e) for standard LCB under central JDP (i.e.. 2 ((VMT/e) for the super single agent case), then by the above argument, it directly implies that our SDP upper bound is tight and moreover, the upper bound under silo-level LDP is also tight.
is worth noting that our new findings in this paper (c.g., identifying existing gaps and establishing new upper bounds) motivate the above interesting questions, which we believe will promote advances in the field.
G.2 SILO-LEVEL LDP/SDP vs. OTHER PRIVACY NOTIONS
In this section, we compare our silo-level LDP and SDP with standard privacy notions for single-agent LCBs, including local, central, and shuffle model for DP, respectively.
Silo-level LDP vs. single-agent local DP. Under standard LDP for single-agent LCBs (Zheng et al., 2020; Duchi et al., 2013; Zhou & Tan, 2021), each user only trusts herself and hence privatizes her response before sending it to the agent. In contrast, under silo-level LDP, each local user trusts the local silo (agent), which aligns with the pratical situations of cross-silo FL, e.g., patients often trust the local hospitals. In such cases, standard LDP becomes unnecessarily stringent, hindering performance/regret and making it less appealing to cross-silo federated LCBs.
Silo-level LDP vs. single-agent central DP. The comparison with standard central DP (in particular central JDP) for single-agent LCB (e.g., Shariff & Sheffet (2018) is delicate. We first note that under both notions, users trust the agent and the privacy burden lies at the agent. Under standard central DP, the agent uses private statistics until round to choose action for each round 1, which ensures that any other users l' * L cannot infer too much about user l's information by observing the actions on rounds t' # t joint differential privacy (JDP) (Kearns et al., 2014)). On the other hand, silo-level LDP does not necessarily require each agent (silo) to use private statistics to recommend actions to users within the silo. Instead, it only requires the agent to privatize its sent messages (both schedule and content). Thus, silo-level LDP may not protect user from the colluding of all other users within the same silo. In other words, the adversary model for silo-level LDP is that the adversary could be any other silos or the central server rather than other users within the same silo. Note that the same adversary model is assumed in a similar notion for federated supervised learning (e.g., inter-silo record-leve differential privacy (ISRL-DP) in Lowy & Razaviyayn (2021)). In fact, with a minor tweak of our Algorithm 1, one can achieve slightly stronger notion of privacy than silo-level LDP in that it now can protect against both other silos/server and users within the same silo.
As shown in Shariff & Sheffet (2018), JDP relaxation is necessary for achieving sub-linear regret for L.BBs under the central model. Otherwise, linear regret lower bound exists for central standard DP.
28

---

Published as a conference paper at ICLR 2024
The key idea is exactly that now each agent will only use private statistics to recommend actions, Appendix G.3.
Silo-level LDP vs. Federated DP in Dubey & Pentland (2020). In Dubey & Pentland (2020), the authors define the so-called notion of federated DP for federated LCBs, which essentially means that "the action chosen by any agent must be sufficiently impervious (in probability) to any single data from any other agent". This privacy guarantee is directly implied by our silo-level LDP. In fact, in order show such a privacy guarantee, Dubey & Pentland (2020) basically tried to show that the outgoing communication is private, which is the idea of silo-level LDP. However, as mentioned in the main paper, Dubey & Pentland (2020) only privatizes the communicated data and fails to privatize the communication schedule, which leads to privacy leakage. Moreover, as already mentioned in Remark B.I, Fed-DP fails to protect a user's privacy even under a reasonable adversary model. Thus, we believe that silo-level LDP is better option for federated LCBs.
SDP vs. single-agent shuffle DP. Under the single-agent shuffle DP (Chowdhury & Zhou, 2022b; Tenenbaum et al., 2023), the shuffler takes as input batch of users' data (i.e., from L to 12), which enables to achieve regret of O(T3/5) (vs. ((T3/4) regret under local model and Ö( regret under central model). In contrast, under our SDP, the shuffler takes as input the DP outputs from all M agents. Roughly speaking, single-agent shuffle DP aims amplify the privacy dependence on T while our SDP amplifies privacy over M. Due to this, single-agent shuffle DP can directly apply standard amplification lemma (e.g., Feldman et al. (2022)) or shuffle protocol (e.g., Cheu et al. (2021)) that works well with LDP mechanism at each user (i.e., the size of dataset is n = 1). In contrast, in order to realize amplification over M agents' DP outputs, we have to carefully modify the standard amplification lemma to handle the fact that now each local mechanism operates on n. > 1 data points, which is one of the key motivations for our new amplification lemma.
Sublinear regret under SDP vs. linear regret lower bound under central standard DP (not JDP).
One may wonder why an even better regret under the shuffle model is possible given that there is a linear regret bound under central model for LCBs. This is not contradicting linear regret is established under standard central DP while SDP in LCBs only implies central JDP. More specifically, in contrast to standard private data analysis and supervised learning, the shuffle model is NOT an intermediate trust model between central standard DP and local DP for LCBs. That is, even if an LCB algorithm satisfies shuffle DP, it can still fail to satisfy central standard DP. Rather, it is only an intermediate trust model between the central joint DP (JDP) and the local model. That is, if an LCB algorithm satisfies shuffle DP, it satisfies central JDP (via Billboard lemma).
the lower bound of
G.3 A SIMPLE TWEAK OF ALGORITHM 1 FOR A STRONGER PRIVACY GUARANTEE
As discussed in the last subsection, the adversary model behind silo-level LDP only includes other silos and the central server, i.e., excluding adversary users within the same silo. Thus, for silo-level LDP, Algorithm 1 can use non-private data to recommend actions within batch (e.g., V2, includes non-private recent local bias vectors and covariance matrices). If one is also interested in protecting against adversary users within the same silo, a simple tweak of Algorithm I suffices.
As shown in Algorithm the only difference is lazy update of 0z,i is adopted (line 5), i.e., it is only computed using private data without any dependence on new non- -riv-riivaeeee local data. In fact, same regret bound as in Theorem 5.1 can be achieved for this new algorithm (though empirical performance could be worse due to the lazy update). In the following, we highlight the key changes in the regret analysis. It basically follows the six steps in the proof of Lemma C.2. One can now define a mapping x(t) that maps any & E [T] to the most recent communication round. That is, for any t E [x] where fy = kB is the k-th communication round, we have x(t) = tx-1- Then, one can replace all in V2,, and G.,, by x(t). The main difference that needs a check is Step 4 when bounding the regret in good epochs. The key is again to establish a similar form as (5). To this end, note that for all E [t tx] V& > Vi, and Gn(t). ; AminI = Vi-1, which enables us to obtain || AllGlllGGGooo aeteG 2) I 2 || Following the same analysis yields the desired regret bound.
29

---

Published as a conference paper at ICLR 2024
Algorithm 8 Priv-FedLLinUBB-LLaz
1: Parameters: Batch size B e N, regularization À > 0, confidence radii {Be, (MM feature map d; C, K; Rd, privacy protocol (R, S, A))
2: Initialize: For all i E [M] W; = 0, U: = 0, W syn = 0, Usn = 0
3: for 1= 1=1,..., do
4: for each agent i = 1, ,..., M do
5: Vt, AI W sy, O Vi,i 1 Usn
6:
Play arm dei argmax,ex, (di(ce,s, a), Be,s) + Be, (ei, and set Ft,i oi(C,,;; az,s)
7:
Observe reward Yru
8: Update U, = U₁ & and W; We + 31,,
9:
end for
if' mod = then
11:
// Local randomizer R. at all agents i E [M]
Send randomized messages Rhias bins (U,) and R RRo((W)) the shuffler // Third party
14:
S S ( He(()) and St = 5(R,, hE(()
15:
// Analyzer A at the server
16:
Construct private cumulative statisties Üsg = A ahins(Shingg (Shins) and W - (Stt)))
// All agents i E [M]
18:
Receive W Wsy and Usy from the server
Reset W; 0,
20:
end if
21:
end for
G.4 NON-UNIQUE USERS
In the main paper, assume all users across all silos and T rounds unique. Here, we briefly discuss how to handle the case of non-unique users.
The same user appears multiple times in the same silo. One example of this could be one patient visiting the same hospital multiple times. In such cases, needs carefully apply group privacy or other technique (e.g., Chowdhury & Zhou (2022b)) to characterize the privacy loss of these returning users.
The same user appears multiple times across different silos. One example of this could be patient who has multiple records across different hospitals. Then, needs adaptive advanced composition to characterize the privacy loss of these returning users.
H ADDITIONAL DETAILS ON SIMULATION RESULTS
In Figure 3, we compare regret performance of LDP-FeeLLnUCB with FedLinUCB under varying privacy budgets." 12 sub-figure (a), we plot results for 8 0.1 and varying level of E (0.2, 1,5) on synthetic Gaussian bandit instance, wherein sub-figure (b), we plot results for 5 and varying level of E {0.1, 0.01, 0.001}. In sub-figure (c), we plot results for å 0.1 and varying level of E {0.2, 5} on bandit instance generated from MSLR-WEB 10K data by training a lasso model on bodyfeatures (d 78). In all these plots, we observe that regret LDP-FedLinUCB decreases and, comes closer to that of FedLinUCB as E, 5 increases (i.e., level of privacy protection decreases), which support our theoretical results. Here, we don't 't compare SDP-LinUCB (with privacy amplification) since its privacy guarantee holds for e, 6 1. Instead, we do so in sub-figure (d) with è = 0.0001. Here also, we observe drop in regret of AnP-FeeLLiUUCB compared to that of LDP-FedLinUCB.
All existing non-private federated LCB algorithms (e.g., Wang et al. (2020) adopts adaptive communication. We refrain from comparing with those maintain consistency in presentation.
30

---

Published as a conference paper at ICLR 2024
Time-ave average Regret
4
FedLinUCB
Time-average Regret
FedLinUCB
LDP-FeaLInUCBIe= 0.2)
(DP-FedLiNUCB(6=0.11 (OPFFeoLinUCC(6=0000)) (B-FFeLLIUUCB((=0000)
LDR-FedLLnUCB(e-
LDP-FedLinUCBle=
2000
4000
6000 Round
8000
10000
2000
4000 Round
6000
8000
10000
(a) Synthetic data (varying e, 0.1)
(b) Synthetic data (varying s 5)
Time-aven aene-vveagge Regret
FedLinUCe
Time-average Regret
FedLinUCB
LDP-FedLinUCB(e= 0.2)
45
SDP-FedLinUCBie 0.0001) LDP-FedLinUCBIE 0.0001)
LDP-FedLinUCBIE=1 1)
LDP-FedLinUCCle 5)
40
35
5000 10000 15000 20000 25000 Round
0
5000
10000 15000 20000 25000
Round
(c) Real data (varying s, 5 = 0.1)
(d) Real data (M = 100)
Figure 3: Comparison time-average group regret FedLinUCB (non-private) and LDP-FedLinUCB (i.e., under silo-level LDP) on (a, b) synthetic Gaussian bandit instance and (c,d) bandit instance generated from MSLR-WES IOK Learning to Rank dataset.
31


Reviews:
[{"review_id": "k8w7ySu0Fl", "reviewer": "Reviewer_SUqu", "summary": "This work studies the problem of differentially private federated linear contextual bandits. Especially, it first identifies the potential privacy leaking from the adaptive communication strategy adopted in previous works, and the incorrect regret bound. To resolve these issues, this work proposes the Private-FedLinUCB framework, which can flexibly enable both silo-level local DP and shuffle DP. Especially, the shuffle DP guarantee is achieved via two different approaches. Theoretical analyses demonstrated the provable efficiency of the proposed framework. In particular, under SDP, the centralized performance can be approached.", "questions": "I would love to hear the authors' opinions on my concerns in the weakness part. If I missed or misunderstood anything, please feel free to let me know.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This work identifies the existing issues in the previous study on differentially private federated contextual bandits, which I believe is valuable. Especially, since adaptive communication schemes are widely adopted in studies of federated contextual bandits, it is important to highlight its potential risk of privacy leaking.\n\n- This work nicely combines DP with federated contextual bandits, where the techniques, especially, two types of approaches to obtain shuffle DP, may be of interest for future studies in this line.\n\n- The overall presentation is satisfactory and the study is thorough and complete. Theoretical results are sound based on my understanding.", "weaknesses": "- The discussion from federated LDP to SDP is a bit unsmooth in my mind. From the reading, it seems that the authors cannot remove the additional $M^{1/4}$ gap from centralized performance and then the focus is turned to a slightly weaker DP notion of SDP (instead of studying whether the gap can be closed in LDP). I would suggest the authors first justify both DP notions in federated contextual bandits (especially SDP), and then state their corresponding results.\n\n- Related to the first point, it would be nice to add some discussions on whether the $M^{1/4}$ gap from centralized performance can be closed; otherwise, the significance of the result is hard to measure.\n\n- In terms of the DP techniques, I understand that there are many different choices and this work adopts two certain ones. It would be nice to clarify whether the adopted ones are necessary or if there are other feasible choices.\n\n- The fixed batch size selection potentially can be improved. Although performing adaptive communication protocol is no longer feasible, it might still be a good choice to have the batch length exponentially growing (as in many low-switching bandit studies) instead of being a fixed one.\n\n- A recent work [R1] studies a different kind of DP notion in federated contextual bandits. It would be nice to include and discuss it.\n\n[R1] Huang et al. ICML 2023 \"Federated Linear Contextual Bandits with User-level Differential Privacy\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BlucddBit2", "reviewer": "Reviewer_kYUa", "summary": "This paper considers silo-level LDP and SDP in federated contextual bandit problems. It points out the existing gap in previous LDP federated bandit works and provides new approaches with regret and communication cost analysis under LDP and SDP.", "questions": "It appears that the algorithm design in this paper heavily relies on a binary-tree-based mechanism, which can only be applied to linear setting. Is it possible to generalize the algorithm or the analysis to nonlinear models, such as Generalized Linear Models (GLM)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper identifies a significant gap in the existing literature on federated linear bandits.\n2. The discussion of related works and the comparison of theoretical results are detailed and clear.\n3. The algorithm design appears to be reasonable, and while I haven't reviewed the proof in detail, it seems that the theoretical results align with the algorithm's design.", "weaknesses": "I don't find any obvious weakness of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5xCBVCMYrO", "reviewer": "Reviewer_Gszt", "summary": "This paper Investigates linear contextual bandits user the cross-silo DP. It seems that this paper is motivated by clear holes in the work of Dubey and Petland (2020), which is a highly cited paper. This work succinctly identifies the errors in that paper, as well as proposes their own solution. It is quite remarkable, since that work is well cited, but the arguments of the authors seem convincing to me. \n\nIn addition to showing the errors with that work, this work further develops a variant of LinUCB that provides the required level of privacy, and computes the regret bound. Another variant is considered where shuffle DP is used, which enables regret equal to the regret achieved by the super node.", "questions": "Since there is so much discussion of Dubey and Petland (2020), I would like to see some if the information related to it included in the abstract.\n\nI find Section 3 to be a bit prose heavy.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Important to set the record straight if errors in Dubey and Petland (2020) is not well known\n* Intuitive algorithms that build on well studied baselines\n* Generally good flow and writing\n* Thorough treatment, including shuffle DP setting as well", "weaknesses": "I think related work sections should be in the main body of the paper for a 9 page paper", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RWESmcwNVP", "reviewer": "Reviewer_cqha", "summary": "This paper delves into the exploration of federated learning in the context of linear contextual bandits (LCBs) while incorporating the principles of differential privacy (DP). The proposed algorithmic framework encompasses several key components, including LinUCB exploration, a distributed variant of the tree-based mechanism, privacy amplification, and a fixed batch update approach. This comprehensive approach offers compelling solutions for addressing both silo-level local DP and shuffle DP concerns. Additionally, the authors have identified and rectified an error pertaining to the total injected privacy noise, as previously reported in Dubey & Pentland 2020, contributing to the advancement of this field.", "questions": "None.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "1. The analysis in this paper is notably meticulous, particularly in its identification of the mistake in the previous results. The presentation of the findings is commendable, as it effectively illustrates the potential privacy vulnerabilities present in Dubey & Pentland 2020. Furthermore, it compellingly highlights the necessity of a more robust silo-level local DP setting. The comparison with related work is both thorough and detailed, contributing to a well-rounded understanding of the research landscape.\n\n2. The paper provides a comprehensive narrative that encompasses regret and communication guarantees under varying privacy constraints. Impressively, the authors extend these guarantees to a broader range of privacy parameters, demonstrating a thorough exploration of the subject matter. Moreover, the novel extension of the current amplification analysis to their specific case adds a valuable dimension to the research.", "weaknesses": "1. The paper, while containing valuable insights, may benefit from some improvements in terms of clarity and presentation. Firstly, the algorithmic design, which incorporates several components and explores various privacy settings, could be made more accessible by summarizing the results in a table format. This would provide readers with a quick and clear overview of corresponding regret, communication, and algorithmic elements across different settings. Additionally, in terms of organization, it might be helpful to reconsider the placement of the concluding remarks, which currently reside under the simulation results. Furthermore, there appears to be a spacing issue in the section discussing the tree-based mechanism, possibly resulting from the authors' use of the vspace command in LaTeX.\n\n2. While the paper offers valuable contributions, the novelty and inspiration of the problem itself could be further developed. The concept of silo-level Local Differential Privacy (LDP), while important and rigorous, may be considered relatively straightforward to formulate. Additionally, the solutions presented in the paper largely draw upon existing results and algorithmic designs, rather than introducing fundamentally new insights or modifications to established findings, which limits the potential of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)