Distributed Differential Privacy in Multi-Armed Bandits
Authors: Sayak Ray Chowdhury
Xingyu Zhou
Venue: ICLR 2023 poster (2023)
Keywords: Multi-armed Bandits
Differential Privacy

Abstract: We consider the standard $K$-armed bandit problem under a distributed trust model of differential privacy (DP), which enables to guarantee privacy without a trustworthy server.  Under this trust model, previous work largely focus on achieving privacy using a shuffle protocol, where a batch of users data are randomly permuted before sending to a central server. This protocol achieves ($\epsilon,\delta$) or approximate-DP guarantee by sacrificing an additive $O\!\left(\!\frac{K\log T\sqrt{\log(1/\delta)}}{\epsilon}\!\right)\!$ factor in $T$-step cumulative regret. In contrast, the optimal privacy cost to achieve a stronger ($\epsilon,0$) or pure-DP guarantee under the widely used central trust model is only $\Theta\!\left(\!\frac{K\log T}{\epsilon}\!\right)\!$, where, however, a trusted server is required. In this work, we aim to obtain a pure-DP guarantee under distributed trust model while sacrificing no more regret than that under central trust model. We achieve this by designing a generic bandit algorithm based on successive arm elimination, where privacy is guaranteed by corrupting rewards with an equivalent discrete Laplace noise ensured by a secure computation protocol. We also show that our algorithm, when instantiated with Skellam noise and the secure protocol, ensures \emph{R\'{e}nyi differential privacy} -- a stronger notion than approximate DP -- under distributed trust model with a privacy cost of $O\!\left(\!\frac{K\sqrt{\log T}}{\epsilon}\!\right)\!$. Finally, as a by-product of our techniques, we also recover the best-known regret bounds for bandits under central and local models while using only \emph{discrete privacy noise}, which can avoid the privacy leakage due to floating point arithmetic of continuous noise on finite computers.

Published as a conference paper at ICLR 2023
DISTRIBUTED DIFFERENTIAL PRIVACY IN MULTI-ARNE BANDITS
Sayak Ray Chowdhury Microsoft Research Bengaluru, Karnataka, India t t-sayakr remi crosoft.ccom www.rremmm.c.cccommmmmmmmmm com
Xingyu Zhou
Department of Electrical and Computer Engineering Wayne State University Detroit, USA xingyu. whw.://yoowwwwwweeeee.m
ABSTRACT
We consider the standard K'armed bandit problem under a distributed trust model of differential privacy (DP), which enables guarantee privacy without trust- worthy server. Under this trust model, previous work on private bandits largely focus on achieving privacy using a shuffle protocol, where batch of users data are randomly permuted before sending to a central server. This protocol achieves
(e, 6) or approximate- guarantee by sacrificing an additive K log T /lgg(1//))
factor in T'step cumulative regret. In contrast, the optimal privacy cost to achieve a stronger (e, 0) or pure-DP guarantee under the widely used central trust model is only θ to obtain pure-DP guarantee under distributed trust model while sacrificing no more regret than that under the central trust model. We achieve this by designing generic bandit algorithm based successive arm elimination, where privacy is guaranteed by corrupting rewards with an equivalent discrete Laplace noise en- sured by secure computation protocol. We also show that algorithm, when instantiated with Skellam noise and the secure protocol, ensures Rényi differential privacy stronger notion than approximate DP under distributed trust model with privacy cost of O K KVoog T
K Tog where, however, a trusted server required. In this work, aim 5
Our theoretical findings are corroborated by numerical evaluations on both synthetic and real-world data.
INTRODUCTION
The multi-armed bandit (MAB) problem provides simple but powerful framework for sequential decision-making under uncertainty with bandit feedback, which has attracted a wide range of prac- tical applications such as online advertising (Abe et al., 2003), product recommendations (Li al., 2010), clinical trials (Tewari & Murphy, 2017), to name a few. Along with its broad applicability, however, there an increasing concern of privacy risk in MAB due its intrinsic dependence on users' feedback, which could leak users' sensitive information (Pan et al., 2019).
To alleviate the above concern, the notion of differential privacy, introduced by Dwork et al. (2006) in the field of computer science theory, has recently been adopted to design anvacc-preserving bandit algorithms (see, e.g., Mishra Thakurta (2015); Tossou & Dimitrakakis (2016); Shariff & Sheffet (2018)). Differential privacy (DP) provides a principled way to mathematically prove privacy guarantees against adversaries with arbitrary auxiliary information about users. To achieve this, differentially private bandit algorithm typically relies well-tuned random noise obscure each user's ' contribution to the output, depending on privacy levels E, smaller values lead to stronger protection but also suffer worse utility (i.e., regret). For example, the central server of recommendation system can use random noise to perturb its statistics on each item after receiving feedback (i.e., clicks/ratings) from users. This is often termed central model (Dwork et al., 2014), since the central server has the trust its users and hence has a direct access to their raw
"Equal contributions

---

Published as a conference paper at ICLR 2023
Best-known performance of private MAB under different privacy models (K number of arms, T = time horizon, A.= reward gap of arm a w.r.t best arm, E, 6, a privacy parameters)
Table 1:
Trust Model
Privacy Guarantee
Best-Known Regret Bounds
Central
θ
Σ LaElK]:A.>0
log T D.
K Ing
(Sajed & Sheffet, 2019)
Local
(c, DD-
θ
1 E
log
(Ren et al., 2020)
A.
Distributed
(e, 6)P
o
T Σ
A.
+
K log ToRTylog
(Tenenbaum et al., 2021)
a: A>
Distributed
(E, OD-
θ
Σ =E((K)
ToRT
K log e K Kvlog T e
(Theorem 1)
Do
Distributed
ac?) ((a; 2 RDD
0
E ZEEKK]A,,>0
logT D.
(Theorem 2)
data. Under this model, an optimal private MAB algorithm with pure DP guarantee (i.e., when 5 = 0) is proposed in Sajed & Sheffet (2019), which only incurs an additive O Tog term in the cumulative regret compared to the standard setting when privacy is not sought after (Auer, 2002). However, this high trust model is not always feasible in practice since users may not be willing to share their raw data directly to the server. This motivates to employ a local model (Kasiviswanathan et al., 2011) 1) of trust, where DP is achieved without a trusted server as each user perturbs her data prior to sharing with the server. This ensures stronger privaey protection, but leads to a high cost in utility due to large aggregated noise from all users. As shown in Ren et al. (2020), under the local model, private MAB algorithms have to incur a multiplicative 1/e² factor in the regret rather than the additive one in the central model.
In attempts to recover the same utility of central model while without a trustworthy server like the local model, an intermediate DP trust model called distributed model has gained increasing interest, especially in the context of (federated) supervised learning (Kairouz et al., 2021b; Agarwal al., 2021; Kairouz al., 2021a; Girgis al., 2021; Lowy & Razaviyayn, 2021). Under this model, each user first perturbs her data via a local randomizer, and then sends the randomized data secure computation function. This secure function
be leveraged to guarantee privacy through aggregated noise from distributed users. There are two popular secure computation functions: secure aggregation (Bonawitz et al., 2017) and secure shuffling (Bittau al., 2017). The former often relies on cryptographic primitives to securely aggregate users' data so that the central server only learns the aggregated result, while the latter securely shuffle users' messages hide their source. To the best of our knowledge, distributed DP model is far less studied in online learning as compared to supervised learning, with only known results for standard K Kaareed bandits in Tenenbaum et al. (2021), where secure shuffling is adopted. Despite being pioneer work, the results obtained in this paper have several limitations: (i) The privacy guarantee is obtained only for approximate DP (6 0) - a stronger pure DP (ō = 0) guarantee is not achieved; (ii) The cost of privacy is multiplicative / (1og(1/)) factor away from that of central model, leading to higher regret bound; (iii) The secure protocol works only for binary rewards (or communication intensive for real rewards)."
Our contributions. In this work, we design the first communication-efin efffccien MAB algorithm that satisfies pure DP in the distributed model while attaining the same regret bound in the central model (see Table 1). We overcome several key challenges that arise in the design and analysis of distributed DP algorithms for bandits. We now list the challenges and our proposed solutions below.
(a) Private and communication efficient algorithm design. Secure aggregation (SecAgg) works inherent modular operation (Bonawitz et al., 2017). Hence,
only in the integer domain due leveraging this in bandits to achieve distributed DP with real rewards needs adopting data quanti- zation, discrete privacy noise and modular summation arithmetic in the algorithm design. To this end, we take batch version of the successive arm elimination technique as building block of our algorithm, and on top of it, employ a privacy protocol tailored to discrete privacy noise and modular operation (see Algorithm 1). Instantiating the protocol at each user with Polya random noise, we
Forr more general linear bandits under distributed DP via shuffling, see Chowdhury & Zhou (2022b); Garcelon al. (2022), which also have similar limitations.
2

---

Published as a conference paper at ICLR 2023
ensure that our algorithm satisfies pure DP in the distributed model. Moreover, the communication bits per-user scale only logarithmicaly with the number of participating users in each batch.
(b) Regret analysis under pure DP with SecAgg. While our pure DP guarantee exploits known results for discrete Laplace mechanism, the utility analysis gets challenging due to modular clipping of SecAgg. In fact, in supervised learning, no known convergence rate exists for SGD under pure DP with SecAgg (although the same is well-known under central model). This is because modular clipping makes gradient estimates biased, and hence, standard convergence guarantees using unbi- ased estimates do not hold, In bandits, however, we work with zeroth order observations to build estimates of arms' rewards, and require high-confidence tight tail bounds for the estimates to anal- yse convergence. To this end, relying on tail properties of discrete Laplace and careful analysis of modular operation, we prove a sublinear regret rate of our algorithm, which matches the optimal one in the central model, and thus, achieves the optimal rate under pure DP (see Theorem 1).
(c) Improved regret bound under RDP. While our main focus were to design the first bandit algo- rithm with pure distributed DP that achieves the same regret rate under central model, our template protocol is general enough to obtain different privacy guarantees by tuning the noise at each user. We demonstrate this by achieving Rényi disferential privacy (RDP) (Mironov, 2017) using Skellam random noise. RDP is a weaker notion of privacy compared to pure DP, but it is still stronger than approximate DP. It also provides tighter privacy accounting for composition compared to approx- imate DP. This is particularly useful for bandit algorithms, when users may participate in multiple rounds, necessitating the need for privacy composition. Hence, and show that tighter regret bound compared to pure DP can be achieved (see Theorem 2) by prov- ing novel tail-bound for Skellam distribution. We support our theoretical findings with extensive numerical evaluation over bandit instances generated from both synthetic and real-life data.
focus RDP with SecAgg and
Finally, our analysis technique also general enough to recover best-known regrets under central and local DP models while only using discrete privacy noise (see Appendix H). This is important in practice since continuous Laplace noise might leak privacy on finite computers due to floating point arithmetic (Mironov, 2012), which is drawback of existing central and local DP MAB algorithms.
2 PRELIMINARIES
In this section, we formally introduce the distributed differential privacy model in bandits. Before that we recall the learning paradigm in multi- bandits and basic differential privacy definitions.
Learning model and regret in MAB. At each time slot E [T] == fl..... T}. the agent (e.g., recommender system) selects arm E [K] (e.g.. an advertisement), recommends it to new user l and obtains an i.i.d reward r. (e.g., a rating indicating how much she likes it), which is sampled from distribution over [0, 1] with mean given by Ma. Let a* = argmax,e K] Pa be the arm with the highest mean and denote μ²" := Maa for simplicity. Let A. := 1z 1oa be the gap of the expected reward between the optimal arm a' and any other arm a. Further, let (t) be the total number of times that arm has been recommended to first t users. The goal of the agent is to maximize its total reward, or equivalently to minimize the cumulative expected pseudo-regret, defined as
Σ T
E Reg (T)] = T p -
=E
Differential privacy. Let D [0, 1] be the data universe, and r E N be the number of unique users. we say D, D' E DD' are neighboring datasets if they only differ in one user's reward preference for some i E [m]. We have the following standard definition of differential privacy (Dwork et al., 2006). Definition (Differential Privacy). For e, 5 > O. a randomized mechanism M satisfies (c, () if for all neighboring datasets D. D' and all events E in the range of M, we have
TP (MM(D) E S e P (D') E E 8.
The special case of (s, 0)-DP is often referred to as pure differential privacy, whereas, for 5 > O, (e, referred as approximate differential privacy. We also consider related notion of pri- vacy called Rényi differential privacy (RDP) Mironov (2017), which allows for a tighter composition compared to approximate differential privacy.
Definition 2 (Rényi Differential Privacy). For a > 1, a randomized mechanism M satisfies (o,é(a))-RDP if for all neighboring datasets D, D', we have D.(M(D).M(())) $ E()), where
3

---

Published as a conference paper at ICLR 2023
Qa(P,Q) is the Rényi divergence (of order a:) of the distribution P from the distribution Q, and is given by Da Q) := - log [Ex~Q
[
P(a)
((())
Distributed differential privacy. A distributed bandit learning protocol P = (R, A) consists of three parts: (i) a (local) randomizer at each user's side, (ii) an intermediate secure protocol S, and (iii) an analyzer A at the central server. Each user i first locally apply the randomizer R on its raw data (i.e., reward) Ds, and sends the randomized data to secure computation protocol S (e.g., secure aggregation or shuffling). This intermediate secure protocol S takes batch of users' randomized data and generates inputs to the central server, which utilizes an analyzer A to compute the output (e.g., action) using received messages from S.
The secure computation protocol S has two main variations: secure shuffling and secure aggre- gation. Both of them essentially work with batch of users' randomized data and guarantee that the central server cannot infer any individual's data while the total noise in the inputs to the ana- lyzer provides a high privacy level. To adapt both into our MAB protocol, it is natural to divide participating users into batches. For each batch b E [B] with ny users, the outputs of S is given by S R (D) == S(R(D)),.... R(Dm,)).
The goal is to guarantee that the the view of all B batches' outputs satisfy DP. To this end, we define a (composite) mechanism
Mp = (S Rm R".....,,S So SoR") R*").
where each individual mechanism So RD operates on n4 users' rewards, i.e., on a dataset from Dno. With this notation, have the following definition of distributed differential privacy.
Definition 3 (Distributed DP). A protocol P = S, is said to satisfy DP (or RDP) in the distributed model if the mechanism Mp satisfies Definition I (or Definition 2).
In the central DP model, the privacy burden lies with a central server (in particular, analyzer A), which needs to inject necessary random noise to achieve privacy. On the other hand, in the local DP model, each user's data is privatized by local randomizer R. In contrast, in the distributed DP model, privacy without trusted central server is achieved by ensuring that the inputs to the analyzer A already satisfy differential privacy. Specifically, by properly designing the intermediate protocol S and the noise level in the randomizer R. one can ensure that the final added noise in the aggregated data over a batch of users matches the noise that would have otherwise been added in the central model by the trusted server. Through this, distributed DP model provides the possibility achieve the same level of utility as the central model while without trustworthy central server.
3 A GENERIC ALGORITHM FOR PRIVATE BANDITS
In this section, we propose a generic algorithmic framework (Algorithm 1) for multi-armed bandits under the distributed privacy model.
Batch-based successive arm elimination. Our algorithm builds upon the classic idea of successive arm elimination (Even-Dat et al., 2006) with the additional incorporation of batches and black- box protocol P = (R, A) to achieve distributed differential privacy. It divides the time horizon T into batches of exponentially increasing size and eliminates sub-optimal arms successively. To this end, for each active arm a at batch b, it first prescribes arm a to a batch of I(b) 2 new users. After pulling the prescribed action a, each user applies the local randomizer R her reward and sends the randomized reward to the intermediary function S, which runs a secure computation protocol (e.g., secure aggregation
secure shuffling) over the total ((b) number of randomized rewards. Then, upon receiving the outputs of S, the server applies the analyzer A to compute the the sum of rewards for batch when pulling arm (i.e., R. (b)). which in turn gives the new mean estimate i., (b) of arm a after being divided by the total pulls ((b). Then, upper and lower confidence bounds, UCB,, (b) and I.B,, (b), respectively, are computed around the mean estimate P.a with properly chosen confidence width (b). Finally, after the iteration over all active arms in batch b (denoted by the set (b)). ). it adopts the standard arm elimination criterion to remove all obviously sub-op sub-optimal arms, i.e., it removes arm from (bb) if UCB, (b) falls below LCB,, (b) of any other arm a' E (b). It now only remains to design a distributed DP protocol P.
There is one key difference between our algorithm and the VB-SDP-AE algorithm in Tenenbaum et al. (2021). At the start of a batch, VB-SDP-AE uses all the past data to compute reward estimates. In contrast, adopt the idea of forgetting and use only the data of the last completed batch.
4

---

Published as a conference paper at ICLR 2023
Algorithm Private Batch-Based Successive Arm Elimination
1: Parameters: # arms K, Time horizon T, privacy level 0, Confidence radii {3(6)
2: Initialize: Batch count b= 1, Active arm set ((b) {1..... ., K} ),, Estimate (1)= 00, Va [K]
3: for batch 1, 2,,,... do
4: Set batch size 1(b)=
5: for each active arm
(bbb do
6:
for each new user i from I to ((6) do
7:
Pull arm a and generate reward r
8:
Send randomized data v. (b) = RR(r (b)) to S
// randomizer
9:
If total number of pulls reaches T, exit
10:
end for
Send messages Ta (b) S (5))1s))))) to
secure computation
Compute the sum of rewards R., (b) ( A(ū,
analyzer
13: Compute mean estimate Pla (b) R. (b)/((b)
Compute confidence bounds UCB, (b) and (P) (Bb)
15: end for
16: Update active set arms: -
UCB.(b) maxx LCB. (b)
17: end for
18: Subroutine: Local Randomizer R (Input: x; E [0, 1]. Output: y:)
19: Require: precision N, modulo m N, batch size n E N, privacy level
20: Encode 2y as 3. = [r:g]] + Ber( - [xg]]
Generate discrete noise 7/s (depending on n, E,
|/ random noise generator
22: Add noise and modulo clip y/4 (T: 17:) mod m
23: Subroutine: Secure Aggregation S (Input: :1.....M.. Mn. Output: 3
24: Require: modulo m N
25: Securely compute ÿ = (Ei= yt) mod m
// black-box function
Subroutine: Analyzer A (Input: y. Output: 2)
27: Require: precision
N, modulo N, batch size E N, accuracy level e R
28: if y > ng + T then
29: set (1) (5-m)) mm/g
correction for underflow
30: else set = = 9/9
Distributed DP protocol via discrete privacy noise. Inspired by Balle et al. (2020); Cheu & Yan (2021), provide a general template protocol P for the distributed DP model, which relies only on discrete privacy noise.
Local randomizer RR receives each i's real-valued data i; and encodes it integer via fixed-point encoding with precision > 0 and randomized rounding. Then, it generates a discrete noise, which depends on the specific privacy-regret trade-off requirement (to be discussed later under specific mechanisms). Next, it adds the random noise to the encoded reward, clips the sum with modulo m and sends the final integer y4 as input secure computation function S.
We mainly focus secure aggregation (SecAgg) for S here. 2 SecAgg is treated as black-box function as in previous work on supervised learning (Kairouz al., 2021a). which implements the following procedure: given users and their randomized messages E Σ, (i.c., integer in (0, 1...., m 1a-mmm111 1)) obtained via R, the SecAgg function S securely computes the modular sum of the messages, ÿ = (>
i- Fi) mod m, while revealing no further information on individual messages to potential attacker, ensuring that it perfectly secure. Details engineering implementations of SecAgg is beyond the scope of this paper, see Appendix G for a brief discussion on this.
The job of analyzer A is to compute the sum of rewards within batch as accurately as possible. E and correct for possible underflow due to modular operation
uses accuracy parameter and bias due to encoding. To sum it up, the end goal of our protocol P = (R, S, A) is to ensure that it provides the required privacy protection while guaranteeing an output probability, which is the key to our privacy and regret analysis in the following sections.
Diz 2; with high
IInstedd of SecAgg. we can also use secure shuffling S (see Appendix D.2), since each has advantages over the other. The high-level idea is same for both techniques; i.c., to ensure that after receiving messages from S, the server cannot distinguish each individual's message.
5

---

Published as a conference paper at ICLR 2023
4 ACHIEVING PURE DP IN THE DISTRIBUTED MODEL
In this section, we show that Algorithm achieves pure-DP in the distributed DP model via secure aggregation. To do so, we need to carefully determine the amount of (discrete) noise in R that the total noise a batch provides (e, O)-DP. One natural choice is the discrete Laplace noise.
Definition 4 (Discrete Laplace Distribution). Let b 0. A random variable X has discrete Laplace distribution with scale parameter b, denoted by Lapz(b), if has a p.m.f. given by
e\/b --
Vr ErEZ, Z, P = 2] e +1
A key property of discrete Laplace that we will use is its infinite divisibility, which allows us to simulate it in distributed way (Goryezka Xiong, 2015, Theorem 5.1).
Fact (Infinite Divisibility of Discrete Laplace). A random variable X has a Pólya distribution with parameters r r>0,, 0,36 [0, 1}, denoted by Pólya(r, (r. (3), if has a p.m.f. given by
F(z +r) (1 By.
E P =
x![(rr
Now, for any 71 E N, (7t 7/4 Jve[n) be 2n i.i.d samples from Pólya(1/n, e e1/b), then the random variable 2h - -75 is distributed as (b).
Armed with the above fact and the properties of discrete Laplace noise (see Fact 3 in Appendix K), we are able to obtain the following main theorem, which shows that the same regret as in the central model is achieved under the distributed model via SecAgg.
Theorem (Pure-DP via SecAgg). Fix > O and T E N. For each batch b, let noise for the i-th user in the batch be t 7 %, where ,,,7% 7/ Lid. Pólya(1//n, e n I(b), (nyn), - log(2T)) and m = ng + 2T + 1. Then, Algorithm achieves (e. 0y-D in the distributed model. Moreover, setting ((b) -0 (
logi ((0]66))))))T)) 2((b)
21og(10 el(b)
it enjoys expected regret
(E DE(K
log T log T
E Reg [T)] O
A
Theorem achieves optimal regret under pure DP. Theorem achieves the same regret bound as the one achieved in Sajed & Sheffet (2019) under the central trust model with continuous Laplace noise. Moreover, it matches the lower bound obtained under pure DP Shariff Sheffet (2018), indicating the bound is indeed tight. Note that, we achieve this rate under distributed trust model a stronger notion privacy protection than the central model - while using only discrete noise.
Communication bits. Algorithm I needs to communicate Ollog m) bits per user to the secure protocol S, i.e., communicating bits scales logarithmically with the batch size. contrast, the number of communication bits required in existing distributed DP bandit algorithms that work with real-valued rewards (as we consider here) scale polynomially with the batch size (Chowdhury & Zhou, 2022b; Garcelon al., 2022).
Remark (Pure DP via Secure Shuffling). It turns out that one can achieve same privacy and regret guarantees (orderwise) using relaxed SecAgg protocol. Building on this result, we also establish pure DP under shuffling while again maintaining the same regret bound as the central model (see Theorem 3 in Appendix D.2). This improves the thtee-rf result for MAB with shuffling (Tenenbaum et al., 2021) in terms of both privacy and regret.
5 ACHIEVING RDP IN THE DISTRIBUTED MODEL
A natural question to ask is whether one can get a better regret performance by sacrificing a small amount of privacy. We consider the notion of RDP (see Definition 2), which is weaker notion of privacy than pure DP. However, it avoids the possible catastrophic privacy failure in approximate DP, and also provides tighter privacy accounting for composition (Mironov, 2017).
One can sample from Pólya follows. First, sample À ~ Gamma(r, 8/ -)) and then use it sample X Poisson(A) A), which known to follow Polya(r, 8) distribution (Goryezka Xiong, 2015).

---

Published as a conference paper at ICLR 2023
To achieve RDP guarantee using discrete noise, consider the Skellam distribution which has recently been introduced in private federated learning (Agarwal et al., 2021). A key challenge in the regret analysis of our bandit algorithm is characterize the tail property of Skellam distribution. This is different from federated learning, where characterizing the variance renders sufficient. In Proposition 1, we prove that Skellam has sub-exponential tails, which not only is the key to our regret analysis, but could also be of independent interest. Below is the formal definition of Skellam.
Definition 5 (Skellam Distribution). A random variable X has a Skellam distribution with mean and variance o², denoted by Sk(p, o²), if it has probability mass function given by
Vx E Z, P = x] - I==
where 12()) is the modified Bessel finntion of the first kind.
To sample from Skellam distribution, one can rely on existing procedures for Poisson samples. This
iid. is because if X = N2 - N2. where N1, ~ Poisson(o (22)), then X is Sk(0, o²) distributed. Moreover, due this fact, Skellam is closed under summation, i.e., if X1 Sk(U1,, of) and X2 Sk(u2, oB), then X3 + X2 ~ Sk(/11 + P2, of + 03))
Proposition 1 (Sab-exponential Tail of Skellam). Let X Sk(O, Then, X is (20², v/2 )uub- exponential. Hence, for any p E (0, 11. with probubility at least 1 p.
| S 20 /lgg((()/ /2log(2/p)
With the above result, can establish the following privacy and regret guarantec of Algorithm 1. Theorem 2 (RDP via SecAgg). Fix & > 0, T N and a scaling factor 2 1. For each batch b, let noise for the i-th user be :i= Sk(O, A ). set n 1(b).g g [SE/TT]. T = [ /log(2T)) + V2 log(2l)) and m = ng + 2T + 1. Then, Algorithm achieves (o,, {a)) - in the distributed model for all a = 2,3,.... with ē(a) = az" min
3=2 }. 12a-1)s + 2 2x
Moreover, setting
4
B(b)= = 0
(P)) 2((6)
(1+1/6) log( (b)00TT it enjoys the expected regret al(b)
log T
KvlogT
T
K Klog
E (Reg(T) O
A.
E
SE
Privacy-Regree SaggretCCommuniattoon Trade-off. Observe that the scaling factor allows us to achieve different trade-offs. If s increases, both privacy and regret performances improve. In fact, for a suffi- ciently large value of the third term in the regret bound becomes sufficiently small, and we obtain an improved regret bound compared to Theorem 1. Moreover, the RDP privacy guarantee improves oz?
to ē(a) R 2. which is the standard RDP rate for Gaussian mechanism (Mironov, 2017). However, a larger s leads to an increase of communicating bits per user, but only grows logarithmically, since Algorithm needs to communicate Ollog m) bits to the secure protocol S.
RDP to Approximate DP. To shed more insight on Theorem 2, we convert our RDP guarantee to approximate DP for a sufficiently large It holds that under the setup of Theorem 2, for suf-
To K KVlog Tlog! ficiently large 8, one can achieve (O(e), 8)P with regret 0 O(E.s,>0 2.
(via Lemma 10 in Appendix K). Implication of this conversion is three-fold. First, this regret bound is O(VTog ) factor tighter than that achieved by Tenenbaum et al. (2021) using a shuffle protocol. Second, it yields better regret performance compared to the bound achieved under (s, DDP in Theorem I when the privacy budget 8 > 1/T. This observation is consistent with the fact that weaker privacy guarantee typically warrants a better utility bound. Third, this conversion via RDP also yields gain of O(vlog (/))) in the regret when dealing with privacy composition (e.g.. when participating users across different batches are not unique) as compared to Tenenbaum et al. (2021) that only relies on approximate DP (see Appendix for details). This results from the fact that RDP provides a tighter composition compared to approximate DP.
Remark 2 (Achieving RDP with discrete Gaussian). One can also achieve RDP using discrete Gaussian noise (Canonne et al., 2020). Here, we work with Skellam noise since it is closed under summation and enjoys efficient sampling procedure as opposed to discrete Gaussian (Agarwal et al., 2021). Nevertheless, as a proof of flexibility of our proposed framework, we show in Appendix that Algorithum I with discrete Gaussian noise can guarantee RDP with a similar regret bound.
7

---

Published as a conference paper at ICLR 2023
6 KEY TECHNIQUES: OVERVIEW
Now, we provide an overview of the key techniques behind our privacy and regret guarantees. We show that the results of Theorem and can be obtained via a clean generic analytical framework, which not only covers the analysis of distributed pure DP/RDP with SecAgg, but also offers a unified view of private MAB under central, local and distributed DP models.
As in many private learning algorithms, the key is to characterize the impact of added privacy noise on the utility. In our case, this reduces to capturing the tail behavior of total noise no == Ra (b)
Li=1 ra (b) added at each batch b for each active arm The following lemma gives generic regret bound of our algorithm under mild tail assumptions on na na(b).
Lemma (Generic regret). Lel there exist constants o, > such that, with probability 2 1-p. (KT (b)) =- (a (oog(KT/D))HHHHt log(///pp)))) for all b 2 1, E [K]. Then, setting confidence (N)(()(())N(())) and p = L/T, Algorithm I enjoys expected regret E [Reg(T)] 0 00 [E[]]AA
radius 3(6)=0 O
logT + Ko /ov/ooTT + KhlogT)
A.
An acute reader may note that the / on the noise is the tail bound of sub-exponential distribu- tion and it reduces to the bound for aab-Gaussian tail if h 0. Our SecAgg protocol P with discrete Laplace noise (as in Theorem 1) satisfy this bound with
v2/e, h = 1/e. Similarly, our protocol with Skellam noise (as in Theorem 2) satisfy this bound with o = O(1/E), h = 1/(sE). Therefore, can build on the above general result to directly obtain our regret bounds. In the following, we present the high-level idea behind privacy and regret analysis in distributed DP model.
Privacy. For distributed DP, by definition, the view of the server during the entire algorithm needs to be private. Since each user only contributes once, 4 by parallel-copooitionn of DP, it suffices to ensure that each view Yo (b) (line 11 in Algorithm 1) private. To this end, under SecAgg, the distri- bution of F. can be simulated via (E, Vi) mod m, which further reduces to (E, G. + 7)) mod m by the distributive property of modular sum. Now, consider a mechanism AM that accepts an input dataset (3. j and outputs ( + n.). By post-processing, it suffices to show that M satisfies pure DP or RDP. To this end, the variance ofat of the total noise E; 17, needs to scale with the sensitivity of E, R. Thus, each user within a batch only needs to add proper noise with variance of oi /n. Finally, by the particular distribution properties of the noise, one can show that M is pure DP or RDP, and hence, obtain the privacy guarantees.
Regret. Thanks to Lemma 1, we only need to focus on the tail of (b). To this end, fix any batch b and arm a. We have ÿ = Du (b). x, = r'a (b). n = l(b) for P in Algorithm I and we need to establish that with probability at least - p. for some a and h,
A(()) Σ x4 <<
( (oVlog(11D)) + h log(l/p))
To get the bound, inspired by Balle et al. (2020); Cheu & Yan (2021), we divide the LHS into 2:/9//91 Term (i) AAO) E, Tz/gl and Term (ii) = E:/9/ Σ, xzI. where Term (i) captures the er- ror due to privacy noise and modular operation, while Term (ii) captures the error due to random rounding. In particular, Term (ii) can be easily bounded via sub-Gaussian tail since the noise is bounded. Term (i) needs care for the possible underflow due to modular operation by considering two different cases (see line 28-30 in Algorithm 1). In both cases, one can show that Term (i) is upper bounded by 7/g with high probability, where is the tail bound on the total privacy noise Σ, m)- Thus, depending on particular privacy noise and parameter choices, one can find o and such that equation holds, and hence, obtain the corresponding regret bound by Lemma 1.
Remark 3. As by-prrduct of our generic analysis technique, Algorithm I and privacy protocol P along with Lemma provide a new and structured way to design and analyze private MAB algo- rithms under central and local models with discrete private noise (see Appendix H for details). This enables us to reap the benefits of working with discrete noise (e.g., finite- fiite-computer representations, bit conmunications) in all three trust models (central, local and distributed).
"This assumption that users only contributes once is adopted in nearly all previous works for privacy analysis in bandits. We also provide privacy analysis for returning users via RDP, see Appendix I.
8

---

Published as a conference paper at ICLR 2023
0.20
DP-5F
11:0
DP-FF
0.01
3P-SE
Tmm-sveng Regre
Dau-O--SE
Time Regie
D-LOP-SSE
0.15
Dau-RPP555 -00
0.15
Dis-RDP
8033
D.s. RWW.RD--SBB R0P-SE//-10
100)
180)
Dis. RDP (E)))=10000
0.10
0.10
0.02
0.00
0.05
0.01
0.00
1100
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0,4
1.6
0.5
1.0
0.0
0.2
0.4
0.6
0.5
1.0
Round
X13
Round
X10
Round
X30
(a)
0.1, K
(b) 5
0.5, K
10
(c) E 0.1,
10
0.5
0.3
DR.SE
0.3
Time veenge Regret
Die-3P-SE
Time Regret
Die-ORSE
Dua-OP-SE
Oww-RDP-SBB 10)
Dva-RDP-SE)--00)
Dua S1g-10)
Die. -UP-SE
0.2
Dris HLIPSEt 191)
0.2
Dua Ror 1M)
0.1
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.66
0.55
1.0
0.0
0.2
0.4
0.5
0.55
1.0
Round
x10P
Round
10
Round
X100
(d) 5 1,
(c) 5,
(f) 10,
Figure 1: Comparison of tvme-average regret for DEst-DP-SE, DDS--RD and DP-SE. Top: Synthetic
Gaussian bandit instances (a. large reward gap (easy instance) and (c) small reward gap (hard instance). Bottom: Bandit instances generated from 1.B.R-WB10KK learning to rank dataset.
7 SIMULATION RESULTS
We empirically evaluate the regret performance of our successive elimination scheme with SecAgg protocol (Algorithm 1) under distributed trust model, which we abbreviate as Dist-DP-SE and Dist- RDP-SE when the randomizer R is instantiated with Pólya noise (for pure DP) and Skellam noise (for RDP), respectively. We compare them with the DP-SE algorithm of Sajed & Sheffet (2019) that achieves optimal regret under pure DP in the central model, but works only with continuous Laplace noise. We fix confidence level = 0.1 and study comparative performances under varying privacy levels (8 < for synthetic data, ε > for real data). We plot time-average regret Reg(T)/T in Figure by averaging results over 20 randomly generated bandit instances.
Bandit instances. In the top panel, similar Vaswani et al. (2020), we consider easy and hard MAB instances with K = 10 arms: in the former, arm means are sampled uniformly in [0.25, 0.75), while in the latter, those are sampled [0.45, 0.55]. We consider real rewards sampled from Gaussian distribution with aforementioned means and projected to JO, 17. In the bottom panel, we generate bandit instances from Microsoft Learning to Rank dataset ASSL-WEBB 10K (Qin & Liu, 2013). The dataset consists of 1,200,199 rows and 138 columns, where each row corresponds to query-url pair. The first column is relevance label O. 1, ..... 4 of the pair, which we take as rewards. The second column denotes the query id, and the rest 136 columns denote contexts of query-url pair. We cluster the data by running K-means algorithm with K = 50. We treat each cluster as a bandit arm with mean reward the empirical mean of the individual ratings in the cluster. This way, we obtain a bandit setting with number of arms K = 50.
Observations. We observe that as T becomes large, the regret performance of Dist-DP-SE matches the regret of DP-SE. The slight gap in small T regime is the cost that we pay to achieve distributed privacy using discrete noise without access smaller). In addition, we find that relatively small scaling factor (s = 10) provides considerable gain in regret under RDP compared pure DP, especially when small (i.c., when the cost of privacy is not dominated by the non-private part of regret). The experimental findings are consistent with our theoretical results. Here, we note that our simulations are proof-of-concep only and we did not tune any hyperparameters. More details and additional plots are given in Appendix J.5
trusted server (for higher value, this gap is even
Concluding remarks. We show that MAB under distributed trust model can achieve pure DP while maintaining the same regret under central model. In addition, RDP is also achieved in MAB under distributed trust model for the first time. Both results are obtained via a unified algorithm design and performance analysis. More importantly, interesting research direction private online learning with distributed DP guarantees, including contextual bandits and reinforcement learning.
work also opens the door to promising and
*oode is available httpp: //gtthbb//bb///////// wwt.chhwwcooomeeeeooooeeooeeeeee htt.aauw...oomaaarr/eeeeeeeeeeee wwwmm//sayarrr///ffeeeetttaaaaaa ptw.://feeeerreiiillaaaeeetaeee

---

Published as a conference paper at ICLR 2023
8 ACKNOWLEDGEMENTS
XZ is supported in part by NSF CNS-2153220. XZ would like to thank Albert Cheu for insightful discussion achieving pure DP via shuffling.
REFERENCES
Naoki Abe, Alan W Biermann, and Philip M Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4):263-293, 2003.
Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Interna- tional Conference on Machine Learning, pp. 32-40. PMLR, 2017.
Naman Agarwal, Peter Kairouz, and Ziyu Liu. The skellam mechanism for differentially private federated learning. Advances in Neural Information Processing Systems, 34, 2021.
Peter Auer. Using confidence bounds for exploitation-exploraaion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 2002.
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket the shuffle model. In Anmual International Cryptology Conference, pp. 638-667. Springer, 2019.
Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim. Private summation in the multi-message shuffle model. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Commu- nications Security, pp. 657-676, 2020.
Amos Beimel, Kobbi Nissim, and Eran Omri. Distributed private data analysis: Simultancously solving how and what. In Annual International Cryptology Conference, pp. 451 458-468. Springer, 2008.
James Henry Bell, Kallista A Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1253-1269, 2020.
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong pri- vacy for analytics in the crowd. In Proceedings of the 26th Symposium Operating Systems Principles, pp. 441 441-459, 2017.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Kam Seth. Practical secure aggregation for privacy- preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 635-658. Springer, 2016.
Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:15676-15588 2020.
TH Hubert Chan, Elaine Shi, and Dawn Song. Optimal lower bound for differentially private multi- party aggregation. European Symposium on Algorithms,, pp. 277-288. Springer, 2012.
Wei-Ning Chen, Christopher A Choquette Choo, Peter Kairouz, and Ananda Theertha Suresh. The fundamental price of secure aggregation in differentially private federated learning. In Interna- tional Conference on Machine Learning, pp. 3056-3089, PMLR, 2022a.
Wei-Ning Chen, Ayfer Ozgur, and Peter Kairouz. The poisson binomial mechanism for unbiased federated learning with secure aggregation. In International Conference on Machine Learning, pp. 3490-3506. PMLR, 2022b.
Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang, Wei Chen, and Liwei Wang. (locally) differ- entially private combinatorial semi-bandits. In International Conference on Machine Learning, pp. 1757-1767. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2023
Albert Cheu and Chao Yan. Pure differential privacy from secure intermediaries. arXiv preprint arXiv:2112.10032, 2021.
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differ- ential privacy via shuffling. In 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 100.::2000.09000, 2021.
Sayak Ray Chowdhury and Xingyu Zhou. Differentially private regret minimization in episodic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6375-6383, 2022a.
Sayak Ray Chowdhury and Xingyu Zhou. Shuffle private linear contextual bandits. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 3984-4009, PMLR, 17-23 Jul 2022b.
Sayak Ray Chowdhury, Xingyu Zhou, and Ness Shroff. Adaptive control of differentially private linear quadratic systems. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 485-490. IEEE, 2021.
Roger Dingledine. Nick Mathewson, and Paul Syverson. Tor: The second-generation onion router. Technical report, Naval Research Lab Washington DC, 2004.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-4077 2014.
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algo- rithms, pp. 1468-2479) SIAM, 2019.
Eyal Even-Dar, Shie Mannor, Yishay Mansour. and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pp. 954-964. IEEE, 2022.
Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, and Matteo Pirotta. Local differential privacy for regret minimization reinforcement learning. Advances Neural Information Processing Systems, 34, 2021.
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.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Vel- ingker. Pure differentially private summation from anonymous messages. arXiv preprint 2rXiv:2002.01919, 2020a
Badih Ghazi. Pasin Manurangsi. Rasmus Pagh, and Ameya Velingker. Private aggregation from fewer anonymous messages. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 798-822 827. Springer, 2020b.
Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuf- fled model of differential privacy in federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 2521-2529. PMLR, 2021.

---

Published as a conference paper at ICLR 2023
Slawomir Goryezka and Li Xiong. A comprchensive comparison of multiparty secure additions with differential privacy. IEEE transactions on dependable and secure computing, 14(5):463- 477,2015. 2015.
Christopher Hillar and Andre Wibisono. Maximum entropy distributions on graphs. arXiv preprint arXiv:1301.3321, 2013.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning. pp. 5201-5212. PMLR, 2021a.
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-200, 2021b.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing. 40(3):793-88) 2011.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. contextual-bandt approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Chonghua Liao, Jiafan He, and Quanquan Gu. Locally differentially private reinforcement learning for linear mixture markov decision processes. arXiv preprint arXiv:2110.10133 2021.
Andrew Lowy and Meisam Razaviyayn. Private federated learning without trusted server: Optimal algorithms for convex losses. arXiv preprint arXiv:2106.09779, 2021. 2021.
Paul Luyo, Evrard Garcelon, Alessandro Lazaric, and Matteo Pirotta. Differentially private explo- ration in reinforcement learning with linear representation. arXiv preprint arXiv:2112.01585, 2021.
Ilya Mironov. On significance the least significant bits for differential privacy. In Proceedings of the 2012 ACM conference on Computer and communications security, pp. 650-661, 2012.
llya Mironov. Rényi differential privacy. In IEEE 30th computer security foundations symposium (CSF), pp. 263-275, IEEE, 2017.
Nikita Mishra and Abhradeep Thakurta. (nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings of the Thirly-First Conference on Uncertainty in Artificial Intelligence, pp. 5-25592-111 2015.
Xinlei Pan, Weiyao Wang, Xiaoshuai Zhang, Bo Li, Jinfeng Yi, and Dawn Song. How you act tells a lot: Privacy-leaking attack on deep reinforcement learning. In Proceedings of the 18th International Conference on Autonomous Agents and MulliAgent Systems, pp. 368-376, 2019.
Tao Qin and Tie-Yan Liu, Introducing LETOR 4.0 datasets. CoRR, abs/130666 tbs//300.2597, 2013. URL http: /atxxvv..vv///////////./////wav/ wwwrrii...og/bab. www//bs./////.oooooo..o...oo..er /0006. 2597.
Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff. Multi-armed bandits with local differential privacy. arXiv preprint urXiv:2007.03121 2020.
Touqir Sajed and Or Sheffet. An optimal private stochastic-mab algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pp. 5579-5588. PMLR, 2019.
Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018.
Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially pri- vate heavy-tailed multi-armed bandits. In International Conference on Artificial Intelligence and Statisties, pp. 1546-1574. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2023
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Differentially private multi- armed bandits the shuffle model. Advances in Neural Information Processing Systems, 34, 2021.
Ambuj Tewari and Susan A Murphy, From ads interventions: Contextual bandits in mobile health. In Mobile Health, pp. 495-517. Springer, 2017.
Aristide Charles Yedia Tossou and Christos Dimitrakakis. Achieving privacy in the adversarial multi-armed bandit. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Aristide CY Tossou and Christos Dimitrakakis. Algorithmss for differentially private multi-armed bandits. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
Sharan Vaswani, Abbas Mehrabian, Audrey Durand, and Branislav Kveton. Old dog learns new tricks: Randomized ueb for bandit problems. In International Conference on Artificial Intelli- gence and Statistics, pp. 1988-1998. PMLR, 2020.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Giuseppe Vietri, Borja Balle, Akshay Krishnamurthy, and Steven Wu. Private reinforcement learn- ing with pac and regret guarantees. In International Conference on Machine Learning, pp. 9754 9764. PMLR, 2020.
Kun Wang, Jing Dong, Baoxiang Wang, and Shuai Li. Cascading bandit under differential privacy. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4418 4422. IEEE, 2022.
Huiming Zhang and Song Xi Chen. Concentration inequalities for statistical inference. arXiv preprint arXiv:2011.02258. 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. Differentially private reinforcement learning with linear function approximation. Proc. ACM Meas. Anal. Comput. Syst., 6(1), Feb 2022.
Xingyu Zhou. Differential privacy for bandits and rl, 2023. URL http:///// www.eaaaccooooobaaoooaaaaaeeaeee te-ittt----dndd
/
Xingyu Zhou and Jian Tan. Local differential privacy for bayesian optimization. Proceedings of the AAAI Conference Artificial Intelligence, 35(12):11152 11159, May 2021.
13

---

Published as a conference paper at ICLR 2023
A OTHER RELATED WORK
Private Multi-Armed Bandits. In addition to stochastic multi-armed bandits under the central model Mishra & Thakurta (2015); Tossou & Dimitrakakis (2016); Sajed & Sheffet (2019), differ- ent variants of differentially private bandits have been studied, including adversarial bandits (Tossou & Dimitrakakis, 2017: Agarwal & Singh, 2017), heavy-tailed bandits (Tao et al., 2022), combina- torial semi-bandits (Chen et al., 2020), and cascading bandits (Wang et al., 2022). MAB under the local model is first studied in Ren et al. (2020) for pure DP and in Zheng et al. (2020) for appromix- ate DP. The local model have also been considered in Tao al. (2022); Chen et al. (2020); Wang et al. (2022); Zhou & Tan (2021). Motivated by the regret gap between the central model and local model (see Table 1), Tenenbaum et al. (2021) consider MAB in the distributed model via secure shuffling where, however, only approximate DP is achieved and the resultant regret bound still has a gap with respect to the one under the central model.
Private Contextual Bandits. In contextual bandits, in addition to the reward, the contexts are also sensitive information that need to be protected. However, a straightforward adaptation of the standard central DP in contextual bandits will lead to linear regret, as proved in Shariff & Sheffet (2018). Thus, to provide a meaningful regret under the central model for contextual bandits, relaxed version of DP called joint differential privacy is considered, which rougly means that the change of any user would not change the actions prescribed all other users, but it allows the change of the action prescribed to herself. Under this central JDP, Shariff & Sheffet (2018) establishes regret bound of Ö(VT) for private variant of LinUCB. On the other hand, contextual linear bandits under the local model incurs a regret bound of O(T3/4) (Zheng et al., 2020). Very recently, motivated by the regret gap between the central and local model, two concurrent works consider contextual linear bandits the distributed model (via secure shuffling only) (Chowdhury Zhou, 2022b; Garcelon et al., 2022). In particular, Chowdhury & Zhou (2022b) show that a ((T3/5) regret bound is achieved under the distributed model via secure shuffling.
Private Reinforcement Learning (RL). RL is a generalization of contextual bandits in that contex- tual bandits can be viewed finite-horizon RL with horizon H 1. This not only directly means that one also has to consider JDP in the central model for RI. but implies that RL becomes harder for privacy protection due to the additional state transition (i.c., H 1). Tabular episodic RL under central JDP is first studied in Vietri et al. (2020) with an additive privacy cost while under the local model, a multiplicative privacy cost is shown to be necessary (Garcelon et al., 2021). In addition to valued-based algorithms considered in Vietri et al. (2020); Garcelon et al. (2021), similar perfor- mance is established for policy-based algorithms in tabular episodic RL under the central and local model (Chowdhury & Zhou, 2022a). Beyond the tabular setting, differentially private LQR control studied in Chowdhury et al. (2021). More recently, private episodic RL with linear function ap- proximation has been investigated in Luyo et al. (2021); Zhou (2022); Liao et al. (2021) under both central and local models, where similar regret gap as in contextual bandits exist (i.e., Ö(VT) vs. Ö(T3/4).
We have also given more discussions on private (federated) supervised learning under the distributed model in Appendix G. For readers who are interested in the subtlety of DP definitions for bandits and RL, we refer to the blog post (Zhou, 2023).
B A POSSIBLE APPROACH TO REDUCE THE COMMUNICATION COST
We first recall that the communication cost for RDP with SecAgg is roughly is the batch size and is the scaling factor. A large leads to better privacy and regret as shown in Theorem 2, but incurs a larger communication.
where
One can observe that the current communication cost is inverse with respect to e. However, we tend to believe that one can break the privacy-commuuiicatoo trade-off above using a very re- cent technique proposed in Chen et al. (2022a). In particular, Chen et al. (2022a) shows that the fundamental communication cost for RDP with SecAgg for the mean estimation task scales with ((max(log(n??=))) 1)), where is the batch size. That is, for a stronger privacy guarantee (i.e., smaller E), each user should send less number of bits. The intuition is that if a user sends less bits, then she communicates less information about her local data (hence natural protection of privacy).
14

---

Published as a conference paper at ICLR 2023
To achieve this improvement, Chen al. (2022a) proposes to use linear compression scheme based on sparse random projections and distributed discrete Gaussian noise. Now, to apply the same tech- needs to handle different utility metric that is, instead
nique to the private bandit problem, of the mean-square error in Chen et al. (2022a), one now needs to examine the tail concentration behavior. We leave it interesting future work.
C A GENERAL REGRET BOUND OF ALGORITHM
In this section, we present the proof of our generic regret bound Lemma
Recall that na (b) == (b) ((b)
(b) is the total noise injected in the sum of rewards for arm during batch We consider the following tail property on (b).
Assumption (Concentration of Private Noise). Fix any E (0, E [K] b 2 1, there exist non-negative constants o, h (possibly depending on b) such that, with probability least 1 2p.
na (b) S (ogl + log(2/p).
We remark that this assumption naturally holds for single (a², -u)-suub-epponnttial noise and single P-suub-Gaussia noise where constants adjustment.
0 (cf. Lemma and Lemma Appendix K) with
Lemma (Formal statement of Lemma
Let Assumption hold and choose confidence radius
log (4)((b)bbb/)) (=/g(((1(())))))) hlog(2 ((b) (22)////10 /p)
B(b) =
21(b)
((b)
((b)
where | (b)l is the number of active arms in batch b. Then, for any E (0, 1]. with probability at least 1 3p, the regret of Algorithm I satisfies
log(KT/p) + Ko hor.//gg(////p/// + Kh Khlog((T))
Σ
Reg(T) (T) =0
Da
aE(K
Taking p 1/T and assuming T 2 K, yields the expected regre!
log T
E [Reg(T)) =0
Σ
Ko KovlogT Khlog
Aa
<E|K]AA0
Proof. Let & be the event that for all active arms (T. (b) Mal S B(b) and & Up &s. Then, we first show that with the choice of B(b) given equation 2, have P [[ 3p for any p [0 under Assumption 1. To see this, we note that
(b) + Σ ((b)
D (b)
Pa Ma
I(b)
Pa.
By Hoeffeding's inequality (cf. Lemma 8), we have for any p (0, 1), with probability at least 1-p.
I1(b) 1(b)
(b ((b)
log(2/p)
Ma =
21(b)
Then, by the concentration of noise n. (b) in Assumption and triangle inequality, obtain for given arm a and batch b, with probability at least 1 - 133p
log(2/p) 21(b)
+ oVlog(1/p) hlog(1/p)
(b( - Hal
((b)
((b)
Thus, by the choice of B(b) and union bound, we have P > 1 3p.
In the following, we condition on the good event E. We first show that the optimal arm a" will always be active. We show this by contradiction. Suppose the end of some batch b, a" will be
15

---

Published as a conference paper at ICLR 2023
eliminated, i.e., UCB (6) < LCBBB (b) for some a'. This implies that under good event &
IAo S Na- (b) + 3(6) Te (b) - (b)) S Pa's
which contradicts the fact that a is the optimal arm.
Then, we show that at the end batch b, all arms such that A. 4,(66) will be eliminated. To show this, have that under good event 3
(b) + (bb) & pa (b) + 23(6) < Ma- (6) 43(b) + 23(6) - Pa. (b) - B(b),
which implies that arm will be eliminated by the rule. Thus, for each sub-optimal arm let by be the last batch that arm is not eliminated. By the above result, we have
o (V lloggKTT (TTp)) + @Vlog(KT/p)
log
hlog(KTHH) 1(ba)
Au S 48(6.)
1(ba)
1(ba)
Hence, we have for some absolute constants C1, C2. C3.
((b.)= S max e1 (og(KT/p) C2a /lo((K//p)) eah log( (T/p))
47
Aa
A
Since the batch size doubles, we have Na(T) & 4l(ba) for each sub-optimal arm a. Therefore, Reg(T) = Eee(K] (a(T)aa < 4l(b,) Moreover, choose 1/T and assume T 2 K, we have that the expected regret satisties
Reg(T)
E
Σ aE(K]
(a))(T)
P
[
T+O
Σ (E|AT]A>0
log T
+ (KooVoogT) O (Khlog T)
+0
Ao
log
+ Ko Kovllo
Khlog T
Aa
RE(R]]AS0
Remark 4. stead of a doubling batch schedule, one can also set ((b) v/² for some absolute constant 1) > 1 while attaining the same order of regret bound.
D APPENDIX FOR PURE DP IN SECTION 4
In this section, we provide proofs for Theorem 1 and Theorem 3, which show that pure DP can be achieved under the distributed model via SecAgg and secure shuffling, respectively. Both results build on the generic regret bound in Lemma 2.
D. PROOF OF THBOREM ]
Proof. Privacy: We need to show that the server's view at each batch has already satisfies (e, 0)-DP, which combined with the fact of unique users and parallel composition, yields that Algorithm satisfies (s, DD in the distributed model. To this end, in the following, fix a batch b and arm a, and hence H; = r (b) and n = I(b). Note that the server's view for each batch is given by
Σ yi FEIn
mod m
(b)
Σ S + #EIm
mod m,
where (a) holds by SecAgg function; (b) holds by the distributive property: (a + b) mod (a mod + mod c) mod e for any a, b, E Z. Thus, the view of the server can be simulated as post-proe processins of mechanism 7. that accepts Hence, it suffices to show that H is (s, 0)- by post- post-processing of DP. To this end, we note that the sensitivity of 3; 3; is g, which, by Fact 3, implies that E, ?/ needs to be distributed Lgpz(g/e)
input dataset (2,); and outputs Σ, 2 + Σ, m/-
16

---

Published as a conference paper at ICLR 2023
in order to guarantee e-DP. Finally, by Fact 1, it suffices to generate 7) % % where 7 and 7 are i.i.d samples from (
Regret: Thanks to the generic regret bound Lemma 2, we only need to verify Assumption 1. To this end, fix any batch and arm a, we have ÿ (b), (b) and 1(b). Then, in the following we will show that with probability at least
2p
( /og (log(1/)) + 1og(1/p))
A Σ x 2
(4)
which implies that Assumption 1 holds with o O(1/e) and h O(1/E).
Inspired by Cheu Yan (2021); Balle et al. (2020), we first divide the LHS of equation 4 as follows.
A(o)
Σ Ti S A
+
Σ T
Σ Zi
9
g
Term (
Term (ii)
where Term (i) captures the error due to private noise and modular operation, and Term (ii) captures the error due to random rounding.
To start with, we will bound Term (ii). More specifically, we will show that for any E (0, 1}, with probability least 1 p.
( Vlog(1/p))
Term (ii) 0
(5)
Let R. == I. then T; = ह, Ber(x; -. = 2gg +3; Ber 24) ) x.g = x:g +:g++4. 4, where
+ Ber 2 T2) zig. We have E [4] = 0 and |- 1, 1]. Hence, is nuu--Guussian
and as a result, > Fi - E; xz = >i 4 is n / Sussssa-Ganssaan Therefore, by the concentration
of sub-Gaussian (cf. Lemma 6), we have
P
Σ
Σ r
2 log log(2/p)
S.p
Hence, by the choice of g [svn]] we establish equation 5.
Now, we turn to bound Term (i). Recall the choice of parameters: g ( -= = =[ log(2/p)]
and ng 2r + 1. We would like to show that
P
A
-
1
5
S
(6)
which implics that for any p e (0, 1], with probability at least 1 - pp
Term S 2 (=10g(2/p)
To show equation 6, the key is to bound the error due to private noise and handle the possible underflow carefully. First, we know that the total private noise Σ, 7 is distributed as Lg/e) Hence, by the concentration of discrete Laplace (cf. Fact 3), we have
P
Σ 7
1 Sp.
Let Envise denote the event that Σ, R4 + E we have P [Enoise] > 1 p. In the following, we condition the event of Enoiee to analyze the output A(D). As already shown in equation 3, the input , (Σ, ã. + m)) mod m already an integer. We will consider two cases of y as in the analyzer subroutine A.
E, + T], then by the above inequality,
We let
Case 1: > ng + F. We argue that this happens only when Σ, Z4 + T E [-r, 0). i.c., underflow. This is because for all i [m). &, g0. m ng + 2r + and the total privacy noise is at most
17

---

Published as a conference paper at ICLR 2023
under Enosee Therefore,
m (
Σ Ty + 118
mod m
m
m + Σ Ty. + 7/8 -
T N
That is, y |E₁ - E, with high probability. In other words, we have shown that when y > ng + T. A(g) y-m satisfies equation
Case 2: S ng + т. Here, we have noisy sum Σ, H. + 1J [0, [0,ng r]. Hence, E, Ts + since ng 2r + 1, which implies that A(r) satisfies equation 6.
Hence, we have shown that the output of the analyzer under both cases satisfies equation 6, which implies equation Combined with the bound in equation 5, yields the bound equation Finally, plugging in O(1/s), h O(1/z) into the generic regret bound in Lemma yields the required regret bound and completes the proof.
D.2 PURE DP VIA SHUFFLING
As stated in the main paper (see Remark 1), one can achieve same privacy and regret guarantees (orderwise) using relaxed SecAgg protocol, which relaxes the SecAgg protocol mentioned above in the following sense: (i) relaxed correctness the output of S can be used to compute the correct modular sum except at most a small probability (denoted by T): (ii) relaxed security the output of reveals only é more information than the modular sum result. Putting the two aspects together, one obtains relaxed protocol denoted by (E, -)-eecAgg. One important benefit of using this relaxation that it allows us to achieve the same results of Theorem via secure shuffling. More specifically, as shown in Cheu & Yan (2021), there exists shuffle protocol that can simulate an (ě, -)-SecAgg. Hence, we can directly instantiate using this shuffle protocol to achieve pure DP in the distributed model while obtaining the same regret bound as in the central model. We provide more details on this shuffle protocol below.
To facilitate discussion, briefly give more formal definitions of relaxed SecAgg based on Cheu Yan (2021), which will also be used in our next proof. We denote a perfect SecAgg as Σ.
To start with, we first need the following two distance metrics between two probability distributions. As in Cheu & Yan (2021), for given distribution D and event E, write PP [D E] for P PI E]. We let supp(D, D. D') be the union of their supports.
Definition 6 (Statistical Distance). For any pair of distributions D, D', the statistical distance is given by
SD(D, D')
max (Esip((D.D)
IP P EJI.
Definition (Log-Lue Likelihood Ratio (LLR) Distance). For any pair of distributions D, D', the LLR distance is given by
P E log
P F )
LLR(D, = max
FESDPp(D.))
Pure DP can be defined using LLR distance.
Definition 8. A randomized mechanism M is O)-D) if for any two neighboring datasets D, D', (DRMM(D),M(()))) Se
Definition (Relaxed SecAgg). We say is an (E, ② rrelaxation of (iee,, (E, rellaxed SecAgg) it satisfies the following two conditions for any input
1. (g-relaxed correctness) There exists some post-processing function POST such that SD(POST(S(y)) E(y)) q.
18

---

Published as a conference paper at ICLR 2023
2. (E-relaxed security) There exists simulator SIM such that (IM S.
Cheu & Yan (2021) show that briefly talk about the high-level idea behind this idea and refer readers to Cheu & Yan (2021) for details. To simulate an (E, -SSecAg via shuffling, the key is introduce another local randomizer on top of the original R. More specifically, we let S == S R in Algorithm with
simulate relaxed SecAgg via shuffle protocol. We now
[(6). b 2 1, where denotes the additional local randomizer at each user i [nx] that maps the output of (i.e., y:) into a random binary vector of particular length d. Then, S denotes a standard shuffler that uniformly at random permutes all the received bits from users (i.e., a total of d bits). The nice construction of R in Cheu & Yan (2021) ensures that S = S o R can simulate an (č, ( -ggeAggg for any ` 7 E 1).
The following theorem says that relaxed SecAgg is sufficient for the same order of expected regret bound while guaranteeing pure DP.
Theorem 3 (Pure-DP via Shuffling). Fix & > 0 and T E N and consider an (E, - (e.g.. simulated via shuffling) for Algorithm 1 Let noise i-th user be Ti
7i 7 where 7,t 7/3 itd Polya( 1 n/nee e =/9)). For each batch b. choose n = 1(b).9 = [nl r = _ log(2 2/p')l and m = ng + 2T + E = e/4,e' = e/2, q p' = 27 Then, Algorithm 1 achieves (e, D)-
in the distributed model. Moreover, setting 3(b) = 0 |og (00))T) 20()
2 log log( (0((6])(TT)
enjoys
el(b)
expected regret
(E
log
T
K KlggT
E RRg((T)) =
A.
Moreover, the communication per user before S is Ollog m) bits.
This proof shares the same idea as in the proof of Theorem 1. We only need to highlight the difference.
Proof.
Privacy: As before, we need ensure that the view of the server already satisfies s-DP for each batch b 2 1. In the following, we fix any batch and arm a, we have 2; = = and n = I(b).
Thus, by Definition 8, suffices to show that for any neighboring datasets (LR()(R(<))).) R(x,)) ((R()))
R(x,))) S E.
To this end, by the é-relaxed security of S used in Algorithm and triangle inequality, we have LLR(S(R((1),..... R(..))) (((()))) R(x()))
22 LLR(SSMM
Σ R(x,) mod m), SIM( Σ R(x)) mod m))
<2 + LLR( Σ R(x,) mod m. Σ Σ R(x') mod mo)
where the last inequality follows from data processing inequality. The remaining step to bound the second term above is the same as in the proof of Theorem 1. With E = e/4 and e' e/2, have the total privacy loss is e.
Regret: As before, the key is establish that with high probability
A
Σ x; 000
log(2/v)) + 1og(2/p')
(8)
where ÿ (b).
SSince the output of a shuffling protocols is a multiset, we need to first compute ( Φ) mod the for the subroutine A in Algorithm 1.
19

---

Published as a conference paper at ICLR 2023
We again can divide the LHS of equation 8 into
A(T) Σ zi S A
Σ
T4
+
Σ 34
Σ
Ti
9
In particular, Term (ii) can be bounded by using the same method, i.c., for any p' E (0, 1], with probability least 1 p',
Term (ii) S V108(2/71))
For Term (i), we would like to show that
P A
Σ
2
7
S 1タ+
9
This can be established by the same steps in the proof of Theorem while conditioning on the high probability event that S is ?-relaxed SecAgg. More specifically, compared to the proof of Theorem 1, the key difference here is that ÿ = (2:3)) B6) mod m only holds with high probability 7 by the definition of g-relaxed SecAgg.
Thus, for any p' E (0, 1), let ① = p/, we have with probability at least 3p', (A(ī) - Σ, zz S (+ (log(///)) + & log(2/p/)). which implies that Assumption holds with = O(1/e) and O(1/E).
E APPENDIX FOR RDP IN SECTION 5
E.1 PROOF OF PROPOSITION
Proof. We first establish the following result.
Claim 1. For all X E R, we have
cosh(A) S e²122
To show this, by the infinite product representation of the hyperbolic cosine function, we have
(osh(A) = II
1
412
(a)
S
exp
412
(b)
exp(A2/2),
2 - 1)2
n 2
1)2
k=1
where (a) holds by the fact that + S ex for all x and (b) follows from Σk=l
2
(2k-17 17
8
Then, note that X Sk(0, o²), then its moment generating function (MGF) is given by E [eAx]] exp(o"(cosh(f - 1)). Hence, by the above claim, we have E [e>x] S e Further, note that T < 2r for E [0, 1]. Thus, for A V2, have
E [c
202 22y02
Hence, by the definition of sub-exponentic random variable (cf. Lemma 7). X is (2o2 v2 yub- exponential, which again by Lemma implies the required concentration result, i.e., for any p (0, 1J, with probability at least 1 1 p.
X < 20 20 /og((/1) /2log(2/p).
E.2 PROOF OF THEOREM 2
We will leverage the following result in (Agarwal et al., 2021, Theorem 3.5 ) to prove privacy guarantee.
20

---

Published as a conference paper at ICLR 2023
Lemma 3. For E Z, 1, let X ok( Then, algorithm M that adds X sensitivity-A query satisfies (a, ((a)))()RDD)) RDP with E((:) given by
a
(2a 1)
6A
3A
e(a) - 2 + min
40
2
Proof of Theorem 2. Privacy: As before, we fix any batch b and arm a, for simplicity, we let æ; ra (b) and n = 1(b). Then, suffices to show that the mechanism H. that accepts an input dataset (2:); and outputs >, 2. >: is private. To this end, since each local randomizer R generates noise ~ Sk(O, /Ez) and Skellam is closed under summation, we have that the total noise E, ~ Sk(0, 5). Thus, by Lemma 3 with A
we have that for each batch b with n - ((b) and 88 vn) Algorithm is ( with En (ax) given by
age
+ min {
(2a 1)e²
3c
3e2
(a) = 2
4s2n 2/
2
Since 1(b) 1, we have that for all batches b
1,
as²
(2a
1)
35
3=a
(a) < a(a)
+
min
4.2
25
28
Regret: We will establish the following high probability bound so that we can apply our generic regret bound in Lemma 2
Σ x4 0 (
log(1/p) (og((1))))))
1og(2/n)
A(T)
(9)
where y = No (b) for each batch and arm a.
We again divide the LHS of equation 9 into
A(T)
Σ Fz <
A
9
g
Term
Term (ii)
In particular, Term (ii) can be bounded by using the same method before, i.c..
P
Σ
2 n log(2/p)
S.p.
Hence, by the choice of [SEVn] establish that with high probability
Term (ii) < 0 log(1/p)
For Term (i), as the previous proof, the key is to show that
IP
Σ
mh
<
To this end, we will utilize our established result in Proposition 1. Note that the total noise E. 17 ~
Sk(0, g ) and hence by Proposition and the choice of 22 /log(2/p) + (2 //pp we have the above result. Following previous proof, this result implies that with high probability
Term (i) < <
/log(1/p) + log(1/p)
Combining the bounds Term (i) and Term (ii), have that the private noise satisfies Assump- tion I with constants o = (1/zz) and à = 0 + Hence, by the generic regret bound in Lemma 2, have established the required result.
21

---

Published as a conference paper at ICLR 2023
F ACHIEVING CDP IN THE DISTRIBUTED MODEL VIA DISCRETE GAUSSIAN
We first introduce the following definition of concentrated differential privacy Bun & Steinke (2016). Definition 10 (Concentrated Differential Privacy). A randomized mechanism M satisfies CDP for all neighboring datasets D, D' and all a (1,,0), we have Da(M(D).MMD)) Remark 5 (CDP vs. RDP), From the definition, we can see that 2 CCDP is equivalent to satisfying (a, 3) simultaneously for all a > 1.
The discrete Gaussian mechanism is first proposed and investigated by Canonne et al. (2020) and has been recently applied to federated learning Kairouz et al. (2021a), We apply it to bandit learning to demonstrate the flexibility of our proposed algorithm and analysis.
Definition 11 (Discrete Gaussian Distribution). Let p. o E R with a > O. A random variable X has discrete Gaussian distribution with location μ and scale o, denoted by Nz(u, if it has probability mass function given by
(2-n))
Vx E
P =
ΣyEZ (u- 10-10/220
The following result from Canonne et al. (2020) will be useful in our privacy and regret analysis.
Fact 2 (Discrete Gaussian Privacy and Utility). Let A, > O. Let q X" + satisfy [g(x)) - 9(x')l < A for all x. x' differing on a single entry. Define a randomized algorithm : + by M(x) = q(x)+Y, where Y ~ NZ,00, A2/=²). Then, M satisfies _=² see-concentrated differential privacy (CDP). Moreover, Y is A2/=2-sub- 2ee2-sub-Gaussae Gaussian and hence for all t 2 0.
P[| 2 < 2e 1(20))
However, a direct application of above results does not work. This is because the sum of discrete Gaussian is not discrete Gaussian, and hence one cannot directly apply the privacy guarantee of discrete Gaussian when analyzing the view of the analyzer via summing all the noise from users. To overcome this, we will rely on a recent result in Kairouz et al. (2021a), which shows that under reasonable parameter regimes, the sum of discrete Gaussian is close to a discrete Gaussian. The regret analysis will again build on the generic regret bound for Algorithm 1.
Theorem 4 (CDP via SecAgg). Fix a E (0, 1) and scaling factor 2 1. Let noise for i-th user be T ~ (0, /² For each 2 1, choose n = ((b), g = [ T = [ /2 log(2/ (2/p)) = 1/T and m = ng + 2T + 1. Then, Algorithm I achieves ECD with ε given by
E min + +
where & ===10 10. E e 2n 3 कt. Meanwhile, the regret is given by
(eg(T) =
Σ
logT
+ KllogT
A.
and the communication messages per user before S are O(log bits.
Remark 6 (Prmuic-Communicatioo Trade-off). We can observe an interesting trade-off between privacy and communication cost. In particular, as s increases, & approaches zero and hence the privacy loss approaches the one under continuous Gaussian. However, a larger leads to a larger m and hence a larger communication overhead.
We will leverage the following result in (Kairouz al., 202 Proposition 13) to prove privacy.
Lemma 4 (Privacy for the sum of discrete Gaussian). Let o 2 1/2. Let X, ~ N2 o²) indepen- dently for each i. Let Z, Em= X,. Then, an algorithm M that adds Zn to a sensitiviry- A query satisfies } 2CCDP with given by
A2 no² +
A Vno
min
+5J
2
22

---

Published as a conference paper at ICLR 2023
where & = 10 Ek=l -2m'd' E+I.
Proof of Theorem 4. Privacy: As before, we fix any batch b and arm for simplicity, we let T; r (6) and 1(b). Then, suffices show that the mechanism H that accepts an input dataset {2, and outputs Σ; 2 + Σ, 7/ is private. To this end, each local randomizer R generates noise 7 N220,, e² and hence by Lemma 4 with g. we have that H. 122 -onccennntt differential privacy with en given by
n = min Vee 0
1 25n + En 6n
where En 10 Σx=
2x ne* F Note that g [1 we have Ta S 10
Σ e 2= से since l(b) v T/2. Thus, we have that Algorithm is is 2 concenttratd
differential privacy with & given by
- + +5.+5
where { = 10 ER e
Regret: We will establish the following high probability bound that apply generic regret bound in Lemma 2
Σ 24 <0 { (Vog(L//))
A(D)
(10)
where ÿ (a
We again divide the LHS of equation 10 into
A -
Σ xq <
A
Σ 54 Σ
T
9
Term (
Term (i))
In particular, Term (ii) can be bounded by using the same method before, i.e.,
P
Σ
Σ xz
/2 log(2/p)
S p.
g2
Hence, by the choice of g [ssV we establish that with high probability
( vlog(1p))
Term (ii) s O
For Term (i), as in the previous proof, the key is to show that
IP
Σ m EE|M
>
T
S p.
This follows from the fact that discrete Gaussian is Lub--Gussiin and sum of Bub-Gaussian is still sub-Gan Gaussian. Thus, by Lemma and the choice of 2 /2 log(2/p). have the above result, which implies that with high probability
Term (i) -
Since 2 1, combining the bounds on Term (i) and Term (ii), we have that the private noise satisfies Assumption 1 with constants o = O(1/e) and h 0. Hence, by the generic regret bound in Lemma 2, have established the required result.
23

---

Published as a conference paper at ICLR 2023
G MORE DETAILS ON SECURE AGGREGATION AND SECURE SHUFFLING
In this section, we provide more details about secure aggregation (SecAgg) and secure shufiling including practical implementations and recent theoretical results for DP guarantees. We will also discuss some limitations of both protocols, which in turn highlights that both have some advantages over the other and thus how to select them really depends on particular applications.
G.1 SECURE AGGREGATION
SecAgg is lightweight instance of secure multi-party computation (MPC) based on cryptographic primitives such that the server only learns the aggregated result (e.g., sum) of all participating users' values. This is often achieved via additive masking over a finite group (Bonawitz et al., 2017; Bell et al., 2020). The high-level idea is that participating users add randomly sampled zero-sum mask values by working in the space of integers modulo m, which guarantees that each user's masked value is indistinguishable from random value. However, when all masked values are summed modulo m by the server, all the masks will be cancelled out and the server observes the true modulo sum. Bonawitz et al. (2017) proposed the first scalable SecAgg protocol where both communication and computation costs of each user scale linearly with the number of all participating users. Recently, Bell et al. (2020) presents further improvement where both client computation and communication depend logarithmically on the number of participating clients.
Practical implementations:
SecAgg for distributed DP: First note that the fact that the server only learns the sum of values un- der SecAgg does not necessarily imply differential privacy since this aggregated result still has the risk of leaking each user's s sensitive information. To provide a formal DP guarantee under SecAgg, each participating user can first perturb her own data with a moderate random noise such that in the aggregated sum, the total noise is large enough to provide a high privacy guarantee. Only until recently, SecAgg with DP has been systematically studied, mainly in the context of private (feder- ated) supervised learning (Kairouz et al., 2021a; aa; Agarwal et al., 2021) while SecAgg in the context of private online learning remains open until our work. More importantly, there exist no formal convergence guarantees of SGD in Kairouz et al. (2021a): Agarwal et al. (2021) due to the biased gradient estimates. To the best of our knowledge, the very recent work (Chen et al., 2022b) is the only one that derives upper bound on the convergence rate when working with SecAgg in private supervised learning. However, the privacy guarantee in it is only approximated DP rather than pure DP considered in our paper.
Limitations of SecAgg: As pointed out in Kairouz et al. (2021b), several limitations of SecAgg still exist despite of recent advances. For example, it assumes semi-honest server and allows it to the per-round aggregates. Moreover, it is not efficient for sparse vector aggregation.
G.2 SECURE SHUFFLING
Secure shuffling ensures that the server only learns an unordered collec- tion (i.e., multiset) of the messages sent by all the participating users. This is often achieved by third party shuffling function via cryptographic onion routing or mixnets (Dingledine et al., 2004) or oblivious shuffling with a trusted hardware (Bittau et al., 2017).
Practical implementations:
Secure shuffling for distributed DP: The additional randomness introduced by the shuffling function can be utilized to achieve similar utility as the central model while without trustworthy server. This particular distributed model via secure shuffling is also often called shuffle model. In partic- ular, Cheu et al. (2019) first show that for the problem of summing n real-valued numbers within [0, 1], the expected eтror under shuffle model with (a, 6)- guarantee is O( log ). For compar- ison, under the central model, the standard Laplace mechanism achieves (s. ODPP (i.e., pure DP) with an error O(1/e) (Dwork et al., 2006) while an error Ω D((n//)) is necessary under the local model (Chan et al., 2012: Beimel et al., 2008). Subsequent works on private scalar sum under the shuffle model have improved both the communication cost and accuracy in Cheu et al. (2019). More specifically, instead of sending (n) bits per user as in Cheu et al. (2019), the protocols proposed in Balle et al. (2020); Ghazi et al. (2020b) achieve (e, DDP with an error O(1/E) while each user only sends (log n + log(1/6)) bits. A closely related direction in the shuffle model is privacy amplification bounds (Frlingsson et al., 2019; Balle et al., 2019; Feldman et al., 2022). That is,
24

---

Published as a conference paper at ICLR 2023
Algorithm 2 Local Randomizer R. (Central Model)
1: Input: Each user data x; E [0, 1]
2: Parameters: precision g E N, modulo m E N, batch size n E N, privacy parameter Φ
3: Encode 2;; F [ + Ber(aag [xgg])
4: Modulo clip yi = T; mod m // no local noise
5: Output: y:
the shufiling of locally private data yields gain in privacy guarantees. In particular, Feldman
et al. (2022)' show that randomly shuffling of n en-DP locally randomized data yields an (c,5)-DP
guarantee with E 0 /lo(1155) when en S 1 and e = V e log(1/8)
when Eo >
Vn
V
Shuffle model has also been studied in the context of empirical risk minimization (ERM) (Girgis et al., 2021) and stochastic convex optimization (Cheu et al., 2021; Lowy & Razaviyayn, 2021), in an attempt to recover some of the utility under the central model while without trusted server. To the best of our knowledge, Tenenbaum et al. (2021); Chowdhury & Zhou (2022b); Garcelon et al. (2022) are the only works that study shuffle model in the context of bandit learning.
In all the above mentioned works on shuffle model, only approximate DP achieved. To the best of our knowledge, there are only two existing shuffling protocols that can attain pure DP (Ghazi et al., 2020a; Cheu & Yan, 2021). In particular, by simulating a relaxed SecAgg via a shuffle protocol, Cheu & Yan (2021) are the first to show that there exists shuffle protocol for bounded sums that satisfies (e, D)-D with an expected error of O(1/e). This is main inspiration for us to achieve pure DP in MAB with secure shuffling.
Limitations secure shuffling: As pointed out in Kairouz et al. (202Ib), one of the limitations is the requirement of a trusted intermediary for the shuffling function. Another that the privacy guarantee under the shuffle model degrades in proportion to the number of adversarial users.
H ALGORITHM 1 UNDER CENTRAL AND LOCAL MODELS
In this section, will show that Algorithm 1 and variants of our template protocol P allow to achieve central and local DP using only discrete noise while attaining the same optimal regret bound in previous works using continuous noise (Sajed & Sheffet, 2019; Ren et al., 2020).
H.1 CENTRAL MODEL
For illustration, we will mainly consider S as SecAgg, while secure shuffling can be applied using the same way as the main paper. In the central model, we just need to set 7/i in the local randomizer R and add central noise in the analyzer A (see Algorithm 2 and Algorithm 3). Then, have the following privacy and regret guarantees.
Theorem (Central Pure-DP SecAgg). Let P = S, be a protocol such that R given by (g/e). Fix any E E (0, 1), for each b 2 L, choose n = ((b).g g = [ T = [ log((/p))] p 1/T and ng 2r + 1. Then, Algorithm I instantiated with protocol P is able to achieve (s. 0) in
Algorithm 2, S is any SecAgg protocol and A is given by Algorithm 3 with
the central model with expected regret given by
Tog A.
K log
E [Reg(T)) [Teg(T)]
Σ
aE(K):A.>0
Moreover, the communication messages per user before S are O(log m) bits.
Remark 7. We can generate 1) Lapz(g/E) as r) 1h2 122 where m, 122 is independent and polya(1,e 1, e e/9) distributed.
'The results in Feldman et al. (2022) hold for adaptive randomizers, but then it needs first to shuffle and then apply the local randomizer. For fixed randomizer, shuffl-thee-randdmiizz is equivalent to randomize- then shuffle.
25

---

Published as a conference paper at ICLR 2023
Algorithm 3 Analyzer A (Central Model)
1: Input: (output of SecAgg)
2: Parameters: precision E N, modulo m E N. batch size n E N, accuracy parameter
3: Generate discrete Laplace noise and set fj 17 mod m
4: Set (T + 9) mod m
5: yf ng then
6: set z = (y) mm/g // correction for underflow
7: else z g/g
8: Output: 2
Proof of Theorem 5. Privacy: By the definition central DP and post-processing, suffices to show that y in Algorithm 3 is private. To this end, we again apply the distributive property of modular sum to obtain that
1 (1) mod m)) mod m ((= x4 +1)
mod m.
Since the sensitivity of Σ; 3y is g and Lapz(g/e), by Fact 3, we have obtained (e, 0)-DP the central model.
Regret: As before, the key is to establish that with high probability
A(T)
Σ 2 S 2
(log(l//)) + 1og(1/p)
(11)
where ÿ (b). Then, we can apply our generic regret bound Lemma We again can divide the LHS of equation 11 into
A
Σ Ti S A
24
T2
Term
Term
In particular, Term (ii) can bounded by using the same method, i.e. for any p E (0, 1], with probability at least 1
Term (ii) 0 Vlo((1/p)
(
For Term (i), would like to show that
A(T) Σ 3
7
Sp
As before, let Enosse denote the event that (E, 34 concentration of discrete Laplace, we have IP [noise]]
r). then by the > 1 - p. In the following, condition on the
+ E E. 3h -
E.
event Emsise to analyze the output A(ÿ). Note that = ((E, 2,) + 17) mod m and hence we can
use the same steps in the proof of Theorem I to conclude that
Term (i) S ( (H00(1/)))
(12)
Finally, by our generic regret bound in Lemma have the regret bound.
H.2 LOCAL MODEL
In the local model, each local randomizer R needs to inject discrete Laplace noise to guarantee pure DP while the analyzer simply the same as the main paper (see Algorithm 4 and Algorithm 5).
To analyze the regret, we need the concentration of the sum of discrete Laplace. To this end, have the following result.
Lemma 5 (Concentration of discrete Laplace). Let (X1) be i.i.d random variable distributed for
according (1/e). Then, have X, is (c² 3z, sub-epppeeel (eeeecceeeee
absolute
26

---

Published as a conference paper at ICLR 2023
Algorithm 4 Local Randomizer R. (Local Model)
1: Input: Each user data [0, 1]
2: Parameters: precision g E N, modulo m E N, batch size n E N,, privacy parameter &
3: Encode 24; 32 [ + Ber( [zgg])
4: Generate discrete Laplace noise f/s
5: Add noise and modulo clip y, (Ā, + m7) mod
6: Output: y; // for SecAgg S
Algorithm Analyzer A (Local Model)
1: Input: 7 (output of SecAgg)
2: Parameters: precision g E N, modulo m N, batch size N, accuracy parameter
3: Set y
4: if ng + r then
5: set z = (y mm/g g // correction for underflow
6: else = g/g
7: Output: 2
stant > 0. As result, we have for any p E (0, 1], with probability at least 1 p. |E X,
where u 2 max { /22/22nlggg (2 2ogg 1og(2/p))-
Proof.
First, we note that if X Lap, then can rewritten as N₁ N2 where N1. N2 geometrically distributed, i.e., [[N = = P [N2 k] 8 B) with 3 - We also write it X N₂ N2.. where N₁ N1 - E [N]]] and N; N₂ E [22], since [Ng = E [N2]. Then, by (Hillar & Wibisono, 2013, Lemma 4.3) and the equivalence of different definitions of sub-exponential (cf. Proposition 2.7.1 in Vershynin (2018)), we have N1, are
exponential for some absolute constant Ci O. Now, since X Ñ -N2. by the weighted sum of zero-mean sub-exponential (cf. Corollary 4.2 in Zhang & Chen (2020)), we have X is (c² 14,,,ck c,)))- sub-exponential for some absolute constant c > Thus, by Lemma 9, we have for any p (0, 1],
let 2 max
( /2n (2g(2/p), 25 log(2/p)), with probability least p. 1E X, S v.
Theorem (Local Pure-DP via SecAgg). P (R A) be protocol such that R given by Algorithm 4 with π7 Lapz(g/E), S is any SecAgg protocol and A is given by Algorithm S. Fix any E (0, 1). for each b 2 1, choose
[Ev/n,, T /2n log(2/p)) (c is the constant in Lemma 5), = 1/T and m ng + 2r + 1. Then, Algorithm 1 instantiated with protocol P is able to achieve (e, DD in the local model with expected regret given by
I(b),
log T A
E Reg 0
RE(K]-A,,0
Moreover, the communication messages per user before S are Oloog m) bits.
Proof. Privacy: By the privacy guarantee discrete Laplace and the sensitivity of 2,, we directly have the local pure DP for our algorithm.
Regret: The first step is to show that with high probabilit, for large batch size n = ((b) 2 2 log(2/p)
Σ 24 0o ( (1b) (ob(l)))()/))
A(T)
(13)
where y Ta (b).
27

---

Published as a conference paper at ICLR 2023
We again divide the LHS of equation 13 into
A(T)
Σ Ii S
A
1 9
Σ
+
Σ 34
Σ
Ti
In particular, Term (ii) can be bounded by using the same method, i.., for any p E (0, 1], with probability least 1 p.
Term (ii S ( (oVlo((/p))
To bound Term (i), the key is again to bound the total noise E; Thi i.c.,
P
Σ
M > T
Sp.
EEIM
To this end, by Lemma 5, when n = I(b) 2
(2/p) and r = og v log(p)/ the above concentration holds. Then, following the same steps before, can conclude that Term(i) S v (1 log(1/p) when [(b) 2 2og(22/p)
2 log((2/p)
We then make a minor modification of the proof of Lemma 2. The idea is simple: we divide the batches into two cases one that ((b) 2 2log(2T)) (noting p 1/T) and the other is that ((b) < log"))"). First, one can easily bound the total regret for the second case. In particular, during all the batches such that I(b) s 2og((2 the total regret is bounded by O((K - 1) log T)- For the first case where 1(b) is large, by equation 13 and the same steps in the proof of Lemma 2, we can conclude that
C1 log(K/pp) C2 (Kg(KL/p)
((.)) max
A
EAA
where bg is the last batch such that the suboptimal arm a is still active. Thus, putting everything together and noting that A. S and E E (0, 1). we have
E Reg((T) =
Σ
log T =ZA
aE[K];A,,>0
I TIGHT PRIVACY ACCOUNTING FOR RETURNING USERS VIA RDP
In this section, we demonstrate the key advantages of obtaining RDP guarantees compared to ap- proximate DP in the context of MAB. The key idea here is standard privacy literature and we provide the details for completeness. The key message is that using the conversion from RDP to approximate allows us to save additional logarithmic factor 8 in the composition compared to using advanced composition theorem.
In the main paper, as in all the previous works on private bandit learning, we focus on the case where the users unique, i.c., returning users. However, if some returns and participates in multiple batches, then the total privacy loss needs to resort to composition. In particular, let us consider the following returning situations.
Assumption 2 (Returning Users), Any user can participate in at most B batches, but within each batch b, she only contributes once.
Note that the total batches can even span multiple learning process, each of which consists of T-round MAB online learning.
Let's first consider approximate DP in the distributed model, e.g. binomial noise in Tenenbaum et al. (2021) via secure shuffling. To guarantee that each user is (c, 8DP during the entire learning process, by advanced composition thcorem (cf. Theorem 7), we need to guarantee that each batch b E [B]. it is (st, dD), where E; 2BBB (185)
6, 2
8 and 8' Thus, for each batch the
28

---

Published as a conference paper at ICLR 2023
variance of the privacy noise is
B (1/) log (3/))
of - 00log(1/0)//3))
(14)
8²
Now, we turn the case of RDP, (e.g., obtained via Skellam mechanism in Theorem 2 or via discrete Gaussian in Theorem 4). To gain the insight, we again consider the case that the scaling factor is large enough such that for each batch b, it is (a, og" )-DD for all a, i... it is approximately 2
2 CDP. Thus B composition of it yields that it is now Bs CDP, and by the conversion lemma (cf.
2
Lemma 10), it is (s', 6)P with e' O log(1 1/))). Thus, in order guarantee (e, ()DP) in the distributed model, the variance of the privacy noise at each batch
= B log(1/0)
(15)
Comparing equation 14 and equation 15, one can immediately see the gain of log(B/8) in the variance, which will translate gain of O O in the regret bound.
Remark 8. For more accurate privacy accounting, a better way is to consider using numeric evaluation rather than the above loose bound.
Remark 9. If one is interested in pure DP, then by simple composition, the privacy loss scales linearty with respect to B rather than v B.
J MORE DETAILS ON SIMULATIONS
We numerically compare the performance of Algorithm under pure-DP and RDP guarantees the distributed model (named Dist-DP-SE and Dist-RDP-SE, respectively) with the DP-SE algorithm of Sajed Sheffet (2019), which achieves pure-DP under the central model. We vary the privacy level as {0.1, 0.5, 1}. where lower value of & indicates higher level of privacy.
In Figure 2, we consider the easy instance, i.e., where arm means are sampled uniformly in J0.25, 0.75]. In Figure 3, consider the hard instance, i.e., where arm means sampled uni- formly in [0.45, 0.55). The sampled rewards are Gaussian distributed with the given means and truncated [0, 1]. We plot results for K 10 arms.
We see that, for higher value of time horizon T. the time-average regret of Dist-DP-SE. is order-wind same to that of DP-SE, i.e., we able to achieve similar regret performance in the distributed trust model as that is achieved in the central trust model. As mentioned before, we observe a gap for small value of T, which is the price we pay for discrete privacy noise (i.e., additional data quantization error on the order of O /log(1/p)) and not requiring trusted central server. Hence, if lower the level of privacy (i.e., higher value of e), this gap becomes smaller, which indicates an inherent trade-off between privacy and utility.
We also observe that if we relax the requirement of privacy from pure-DP to RDP, then we can achieve a considerable gain in regret performance; more so when privacy level high (i.c., is small). This gain depends on the scaling factor s the higher the scale, the higher the gain in regret.
In Figure 4, we compare regret achieved by our generic batch-based successive arm elimination algo- rithm (Algorithm 1) instantiated with different protocols P under different trust models and privacy guarantees: (i) central model with pure-Dr DP (CDP-SE), (ii) local model with pure-DP (LDP-SE), (iii) Distributed model with DP (Dist-DP-She SE), Renyi-DP (Dist-RDP-SH) and Concentrated- DP (Dist-CDD-SEE), First, consider the pure-DP algorithmis. We observe that regret performance of CDP-SE and Dist-DP-SE is similar (with much better regret than LDP-SE). Now, if we relax the pure-DP requirement, then we achieve better regret performance both for Dist-RDP-S. and Dist- CDP-SE. Furthermore, Dist-CDP- SE performs better in terms of regret than Dist-RDP-SC This is due to the fact that under CDP, we use discrete Gaussian noise (which has aab-Gaussian tails) as opposed to the Skellam noise (which has sub-exponential tails) used under RDP.
In Figure 5, we show clear plots for our experiment on bandit instances generated from Microsoft Learning to Rank dataset MSLR-WEB100 (Qin & Liu, 2013).
29

---

Published as a conference paper at ICLR 2023
0.20
DP-SE
Time-average Regret
Dist-DP-SE
0.15
Dist-RDP-SE(s-10 Dist-RDP-SE(s-100)
0.10
0.05
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
x106
0.20
DP-SE
Time-average Regret
Dist-DP-SE
0.15
Dist-RDP-SE(s=0)
Dist-RDP-SE(s=100
0.10
0.05
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
100
0.20
DP-SE
Time-average Regret
Dist-DP-SE
0.15
Dist-RDP-SE(s-10 10)
Dist-RDP-SE(s-100
0.10
0.05
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
x 100
Figure 2: Comparison of time-average regret for Dist-DP-SE, Dist-RDP-SE, and DP-SE in Gaussian bandit instances under large reward gap (easy instance) with privacy level g 0.1 (top), = 0.5 (mid) and (bottom)
30

---

Published as a conference paper at ICLR 2023
0.04
DP-SE
Time-average Regret
Dist-DP-SE
Dist-RDP-SE(s=0)) Dist-RDP-SE(s-100)
0.03
0.02
0.01
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
x107
0.04
DP-SE
Time-average Regret
Dist-DP-SE
Dist-RDP-SE(s10)
0.03
Dist-RDP-SE(s=100)
0.02
0.01
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
x10
0.04
DP-SE
Time-average Regret
Dist-DP-SE
Dist-RDP-SE(s-10 10)
0.03
Dist-RDP-SE(s-100
0.02
0.01
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
x x10
Figure 3: Comparison of time-average regret for Dist-DP-SE, Dist-RDP-SE, and DP-SE in Gaussian bandit instances under small reward gap (hard instance) with privacy level e 0.1 (top), = 0.5 (mid) and (bottom)
31

---

Published as a conference paper at ICLR 2023
0.20
Time-average Regret
0.15
CDP-SE
LDP-SE
Dist-DP-SE
0.10
Dist-RDP-SE(s=10
Dist- Dist-CDP-SE(s-11
0.05
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
x106
0.20
CDP-SE
Time-average Regret
LDP-SE
0.15
Dist-DP-SE
Dist-RDP-SE(s=00)
0.10
Dist-CDP- SEDP-SE(ss--) 10)
0.05
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
x10
0.20
CDP-SE
Time-average Regret
LDP-SE
0.15
Dist-DP-SE
Dist SEtt-RDP-SEss-111 Dist-CDP-SE(s=10)
0.10
0.05
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Round
100
Figure 4: Comparison of time-average regret for CDP-SE, LDP-SE, Dist-DP-SE, Dist-RDP-SE. and Dist-CDP-SE in Gaussian bandit instances under large reward gap (easy instance) with privacy level = 0.1 (top). 0.5 (mid) and (bottom)
32

---

Published as a conference paper at ICLR 2023
0.3
DP-SE
lime-average Regret
Dist-DP-SE
Dist-RDP-SE
0.2
Dist-RDP-SE(s=100)
0.1
0.0
0.2
0.4
0.6
0.8
1.0
Round
x106
0.3
DP-SE
Time- lvme-average Regret
Dist-DP-SE
Dist-RDP-SE 10)
0.2
Dist-RDP-SE(s=1000
0.1
0.0
0.2
0.4
0.6
0.8
1.0
Round
X 10
0.3
DP-SE
Time-average Regret
Dist-DP-SE
Dist Dist-RDP-SE(s=10)
0.2
Dist-RDP-SE(s- 100)
0.1
0.0
0.2
0.4
0.6
0.8
1.0
Round
X 10
Figure 5: Comparison of time-average regret for Dist-DP-SE, Dist-RDP-SE and DP-SE in bandit instances generated from real data with privacy level (top), E (mid) and 10 (bottom)
33

---

Published as a conference paper at ICLR 2023
K AUXILIARY LEMMAS
In this section, we summarize some useful facts that have been used in the paper.
Fact 3 (Discrete Laplace Mechanism). Let A,E > O. Let q D + Z satisfy (q(D) (DD) E for all D'D' differing single user's data. Define mechansim M DD 2 by M(D) ((D) + Y, where Y Lap (/E). Then, M satisfies (c, D)-D.. Moreover, for all m E N,
P > ml = = < m e +1
Lemma (Concentration of sub-Gaussian). mean-zero random variable X is gi-sub-Gaussian Gaussian for all X E R
x²
Ax < exp
2
Then, satisfiex that for any p (0, 11, with probability at least p,
X & 22a / /lo((2/D).
Lemma 7 (Concentration of sub-cxponential). A mean-zero random variable X is (o² h)) exponential for |^| S 1/h
(2202
[E S exp
2
Then, have
t
})
[| > t] 5 2 exp
-minn
min
2 2h
Thus, it satisfies that for any p (0, 1]. with probability least 1 p.
[X] S /2o//oo((2
log(2/p).
Lemma 8 (Hoeffding's Inequality). Let X,,..., X, be independent and identically distributed (i.i.)) random variables and X; E [0, 1] with probability one. Then, for any p E (0, 1), with proba- bility at least P.
1
log(2/p)
Σ
Xn
E[x1] $
2n
1=1
Lemma (Sum of sub-exponential), Let {x.3 be independent zero-mean (o,, hi) hub- exponential random variables. Then, Σ, X; is E,;; h. Thus, we have
where h == max; h4.
P
Σ
X;
> 1
< 2exp
(-min-
t2
t
2
2
of
2h
In other words, for any p E (0, 11, if > max 22 ; of log (0g(2/p), 2h, log(2/p)). with probability
at least - p. Σ, X Sv. v.
Lemma 10 (Conversion Lemma). M satisfies (a, =(x)=(())-)))) RDP, for any E (0, 1), M satisfies (e, 8DDP where
= inf <(a) + log(1/(a6)) log(1 - 1/a).
a>1
a-1
M satisfies 2 then for for any ő E (0, 1), M satisfies Oe'D where
e' inf 2 log(1/(a0)) log(1 1/a) se (V2 ( +e/2)
a>1 5
a
Moreover, if M satisfies (e, 0)-DP, then it satisfies (a, 2 simultaneously for all a E (1)
Theorem 7 (Advanced composition). Given target privacy parameters E (0,1) and 8' O, to ensure (E', kg + DDDDDD for the composition of (adaptive) mechanisms, suffices that each mechanism is (c, 8)-DP with E 2 log(188
34


Reviews:
[{"review_id": "kk0NRMYjGx4", "reviewer": "Reviewer_PLdo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work proves regret bounds for multi-arm bandit under distributed pure DP and RDP only using discrete noise. The theoretical results are verified by experiments.", "summary_of_the_review": "This work provides new regret bounds in MAB under distributed DP verified by experiments. The main drawback is that lower bound is missing for RDP, and technical novelty is unclear.", "strength_and_weaknesses": "Strength\n- This work fills in the gap for distributed pure DP in previous works and the result is tight (matches the central DP lower bound)\n- The RDP upper bound is promising, and the result is relevant in practice as RDP is often used for tight privacy accounting. \n- The algorithm uses discrete noise which is more relevant in practice.\n- The theoretical bounds are verified by experiment results.\n\nWeakness\n- I was wondering if the distributed DP bounds can be obtained from LDP bound + privacy amplification by shuffling.\n- Lower bound is not provided for RDP.\n- Technically the work seems to mainly use existing techniques (discrete Laplace, Skellam noise, etc.). Perhaps the authors could better explain the technical novelties, e.g. why $(\\varepsilon, 0)$ bound could not be obtained in previous works and how it is obtained in this work\n\n\nMinor comments:\nSince the upper bound for distributed $(\\varepsilon, 0)-$DP matches that of central DP, row 4 in Table 1 could be changed to $\\Theta$ instead of $O$", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KjwMejP--v", "reviewer": "Reviewer_Z6zL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the multi-armed bandit (MAB) problem under the constraint of *distributed* differential privacy (DP). The goal here is to match the optimal utility guarantees under *central* DP, whilst being able to achieve stronger privacy guarantees in the model where we don't have a central, trustworthy server for aggregation and analysis. This paper overcomes the following limitations of prior work in this distributed setting (albeit via *shuffle* DP): (1) it only provides approximate DP guarantees; (2) the cost of privacy is a factor of $\\sqrt{\\log(1/\\delta)}$ away from the optimal regret under pure DP in the central model; and (3) this works only for binary rewards or leads to high communication costs for real rewards.\n\nThere are two algorithms provided here: one for pure DP and one for Renyi DP (RDP). The four main challenges overcome and goals achieved here are: communication cost while achieving DP; achieving the best results so far under pure distributed DP; much better bounds under RDP, especially on real-world data; and overcoming the issue of privacy loss on finite computers due to floating point errors by using discrete noise distributions. Both theoretical and empirical results are provided.", "summary_of_the_review": "I think it's a decent paper, with potential improvements out there in the writing. Based on what I've said so far, I feel accepting it should be alright, but I would be taking the authors' response into account before sending my final recommendation.\n\nEdit: updated my score now.", "strength_and_weaknesses": "Strengths:\n1. The results for distributed DP provided here achieve the strongest privacy guarantees with utility matching that of the optimal, pure, central DP algorithm. The prior work in this distributed setting only offered approximate DP guarantees with utility worse by a multiplicative factor of $\\sqrt{\\log(1/\\delta)}$. The idea of using Polya noise is quite nice!\n2. The communication complexity of the above is also not too high -- $\\log(m)$ bits.\n3. The above could be extended to shuffle DP setting, as well.\n4. The RDP guarantee is much better in terms of the utility, and the algorithm does well empirically on real-world datasets, too.\n5. The above has asymptotically better utility than that of the prior work, has better guarantee than this paper's pure DP analogue for the setting where $\\delta > 1/T$, and has better guarantees under composition than that of the prior work.\n6. The experimental results indicate that these algorithms do almost as well as the central DP algorithm on both synthetic and real-world datasets.\n\nWeaknesses:\n1. The algorithmic framework is heavily inspired by those of the prior work of Balle et al' 2020 and Cheu et al' 2021. Even for the RDP algorithm, the idea of using Skellam noise is borrowed. So, I'm not sure how much the algorithmic novelty is here.\n2. As acknowledged by the authors (which I appreciate), the communication cost gets worse in the RDP setting with better privacy and utility demands. Is that a necessity? Some discussion of that could be useful!\n3. I have some complaints with the writing quality of this paper, which I will describe in the next section.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IQtG_5E0N3", "reviewer": "Reviewer_V7G1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers the (stochastic) multiarmed bandits problems in the setting of distributed differential privacy, where each individual’s reward function needs to be protected, and the central server running the bandits algorithm is not fully trusted to receive private information in the clear.  The setting studied in the paper does, however, allow for a secure intermediary, such as secure aggregation, or shuffling.\n\nThe main result of the paper is an algorithm with excess regret of $O(\\varepsilon^{-1} k \\log T)$, where $k$ is the number of arms, $T$ is the number of time steps, and $\\varepsilon$ is the privacy parameter. This is optimal for pure differential privacy even in the central model, and effectively removes a $\\sqrt{log 1/\\delta}$ factor from prior work. The prior work also offered somewhat weaker privacy guarantees.", "summary_of_the_review": "The paper has a nice result, which builds on prior work, but also adds new ideas.", "strength_and_weaknesses": "Getting a tight bound for a fundamental problem, in a distributed model of differential and yet matching the central model lower bound, is certainly nice. \n\nThe paper builds on ideas from prior works. The main algorithm is very similar but different from the VB-SDP-AE algorithm from the Tenebaum, Kaplan, Mansour, Stemmer [TMMS] paper. Part of the improvement over [TMMS] comes from using a better primitive for private binary summation, either by using a different secure intermediary primitive (secure aggregation) or by utilizing a more recent private summation protocol for the shuffle model, from a preprint of Cheu and Yan. Nevertheless, this is not enough to get the tight bound, and the additional tweak added to the TMMS algorithm seems to be essential.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster