Generalized Linear Bandits with Local Differential Privacy 
Authors: Yuxuan Han
Zhipeng Liang
Yang Wang
Jiheng Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Local Differential Privacy
Contextual Bandits
Online Decision Making

Abstract: Contextual bandit algorithms are useful in personalized online decision-making. However, many applications such as personalized medicine and online advertising require the utilization of individual-specific information for effective learning, while user's data should remain private from the server due to privacy concerns. This motivates the introduction of local differential privacy (LDP), a stringent notion in privacy, to contextual bandits. In this paper, we design LDP algorithms for stochastic generalized linear bandits to achieve the same regret bound as in non-privacy settings. Our main idea is to develop a stochastic gradient-based estimator and update mechanism to ensure LDP. We then exploit the flexibility of stochastic gradient descent (SGD), whose theoretical guarantee for bandit problems is rarely explored, in dealing with generalized linear bandits. We also develop an estimator and update mechanism based on Ordinary Least Square (OLS) for linear bandits. Finally, we conduct experiments with both simulation and real-world datasets to demonstrate the consistently superb performance of our algorithms under LDP constraints with reasonably small parameters $(\varepsilon, \delta)$ to ensure strong privacy protection. 

Generalized Linear Bandits with Local Differential Privacy
Yuxuan Han yhanat@connect. ust hk
Zhipeng Liang?* 21 iaiagao@comeect. ust hk
Yang Wang yangwangoust. hkk
Jiheng Zhang
j jihengSust,
Department of Mathematics'
Department of Industrial Engineering and Decision Analytics The Hong Kong University of Science and Technology
Abstract
Contextual bandit algorithms are useful in personalized online decision crrisiion-maiing However, many applications such as personalized medicine and online advertising require the utilization of individual-specific information for effective learning, while user's data should remain private from the server due to privacy concerns. This motivates the introduction of local differential privacy (LDP), stringent notion privacy, contextual bandits. this paper, we design LDP algorithms for stochastic generalized linear bandits to achieve the same regret bound as in non-privacy settings. Our main idea to develop stochastic gradient-bass bbssed estimator and update mechanism to ensure LDP. We then exploit the flexibility of stochastic gradient descent (SGD), whose theoretical guarantee for bandit problems is rarely explored, in dealing with generalized linear bandits. We also develop estimator and update mechanism based on Ordinary Least Square (OLS) for linear bandits. Finally, conduct experiments with both simulation and real-world datasets to demonstrate the consistently superb performance of our algorithms under LDP constraints with reasonably small parameters (c, 5) to ensure strong privacy protection.
Introduction
Contextual bandit algorithms have received extensive attention for their efficacy for online decision making in many applications such as recommendation system, clinic trials, and online advertisement Despite their success in many applications, intensive utilization of user-specific informa- tion, especially in privacy-sensitive domains such as clinical trials and e-commerce promotions, raises concerns about data privacy protection. Differential privacy, as a provable protection against identifi- cation from attackers [8, 19], has been put forth as a competitive candidate for a formal definition of
7 135 24
privacy and has received considerable attention from both academic research 33 17 43 336 & and
industry adoption 200 12 37 While increasing attention has been paid to bandit algorithms with
joint differential privacy 34 we introduce in this paper a more stringent notion. local differential
privacy (LDP), in which users even distrust the server collecting the data, to contextual bandits.
'Equal contributions.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In contextual bandit, at each time round t with cadividual-speciffe context X,, the decision maker can take an action a; from a finite set (arms) to receive reward randomly generated from the distribution depending on the context X, and the chosen arm through its parameter 0a, which is not unknown to the decision maker. We use the standard notion of expected regret to measure the difference between expected rewards obtained by the action 0r and the best achievable expected reward in this round. While several papers consider the adversarial setting (i.e., Xx can be arbitrary determined in each round), this paper considers the stochastic contextual case where X, is generated i.i.d. from a distribution Px. The goal is to maximize the rewards accumulated over the time horizon. An algorithm achieves LDP guarantee if every user involved in this algorithm is guaranteed that anyone else can only access her context (and related information such as the arm chosen and the reward) with limited advantage over random guess. Recently there is an emerging steam of works combining bandit and design algorithms to achieve the same regret as in the non-privacy setting. For contextual bandits, 44] considers the adversarial setting, Despite their pioneering work, their regret bounds ((T3/4) leave gap from the corresoonding non-privacy results O(T1/2), which is conjectured to be inevitable. A natural question arises: can we close this gap for stochastic contextual bandits? In this paper, we design several algorithms and show that they can achieve the same regret rate in terms of T as in the non- non-private settings.
LDP and bandit. 16 29 10 consider the LDP contextual-frn
If we don't assume any structure on the arms' parameters, the above formulation is referred to as contextual bandits. If we impose structural assumptions such as all arms share the same parameter (see Section 2.2 for details), then the formulation is referred to as single- parameter contextual bandits. Although multi-parameter and single-parameter settings can be shown to be equivalent, they need independent analysis and design of algorithms because of their distinct properties based on different modeling assumptions (e.g.. (27]). In this paper, we consider the privacy guarantee in both settings. In fact, the parameters for all K arms with sufficient accuracy to make good decisions. However, privacy protection also requires protecting the information about which arm is pulled in each round. Such a requirement hinders the identification of optimal arm and may incur considerable regret in the decision process. A proper balance between privacy protection and estimation accuracy is the key to design algorithms with desired performance guarantee in this setting.
setting is more difficult since need to estimate
Result
Regret
Context
Parameter
8-Margin
Theorem
10
44
Ö(T3/4/E)
Adversary
Both
No Margin
Theorem
3.1
O(T1/2/e)
Stochastic
Single
No Margin
Theorem
Ologg
Stochastic
Single
B =
Theorem 3.3
Ô /e1+9)
Stochastic
Single
0 S , <1
Theorem
O(llg T/E)?)
Stochastic
Multiple
8=
Theorem 4.1
O /2/+8)
Stochastic
Multiple
0< <1
Table 1: Summary of our main results in (E, DDDL where O(-) omits poly-logarithmic factors.
Contributions. We organize results for various settings in Table Our main contributions can be summarized as follows:
1. We develop a framework for implementing LDP algorithms by integrating greedy algorithms with a private OLS estimator for linear bandits and a private SGD estimator for generalized linear bandits. We prove that our algorithms achieve regret bound matching the corresponding non- privacy results.
In the pallmmerrrreterr setting, to ensure the privacy of the arm pulled in each round, we design novel LDP strategy by simultaneously updating all the arms with synthetic information instead of releasing the pulled arm. By conducting such synthetic updates for unselected arms, we protect the information of the pulled arm from being identified by the server or other users. This is at the cost of corrupting the estimation of the un-selected arms. To deal with this issue, we design an elimination method that is only based on data collected during a short warm up period. We show that such mechanism can be combined with the OLS and SGD estimators to achieve the desired performance guarantees.

---

3. We introduce the SGD estimator to bandit algorithms to tackle generalized linear reward structure. To the best of our knowledge, few papers have ever considered SGD-based bandit algorithms. Theoretical regret bounds are established in [13 by combining SGD and Thompson Sampling, while most of the others are limited to empirical studies 32 We establish such theoretical regret bounds for SGD-based bandit algorithms. Our private SGD estimator for bandits is highly computationally efficient, and more importantly, greatly simplifies the data processing mechanism for LDP guarantee.
Preliminaries
Notations. We start by fixing some notations that will be used throughout this paper. For positive integer n, [n] denotes the set {1,...,, ,n]. |A| denotes the cardinality of the set A. l1- Euclidean norm. W(1, (i, denotes the element in the i-th row and j-th column of matrix W. We write W > O if the matrix W is symmetric and positive definite. We denote Ia as the d-dimensional identity matrix. Let & denote the Kronecker product. Let B; denote the d-dimensional ball with radius and 54-1 denotes the (d 1) )ddimensional sphere for the bull. Given set A, Unift A) denote the uniform distribution over A. For a tuple (Z..3)ssN.35) and S kj < l2 S M, we denote Z k, = (Zi,k,'" k2 We adopt the standard asymptotic notations: for two non-negative sequences {ax} and {ba}. {an] = O((ba)) iff lim sup an/br < 00, an = ((bb)) iff bn = (an)) an = ((b,) iff an = (b,,) and b,, = =(an). We also write Ö(), (2(-) and θ()) to denote the respective meanings within multiplicatiie logarithmic factors in
2.1 Local Differential Privacy
Definition 2.1 (Local differential privacy). We say a (randomized) mechanism M : X + Z is (c, O)-DP, for every + x' E X and any measurable set C C Z we have
P(M(x) E C) S P(M(2') CC)
When 8 = 0, we simply denote E-LDP.
We now present some tools that will be useful for our analysis.
Lemma 2.1 (Gaussian Mechanism [16 19). For any f X RR" let σ2,5 = a lf(z))
fa'' /2 (n 1.25/5). The Gaussian mechanism, which adds random noise independently drawn from distribution N N(0, o². to each output of f. ensures (e, (LD.).
Besides the Gaussian mechanism, we also use the following privacy mechanism for bounded vectors.
Lemma 2.2 (Privacy Mechanism for lalball 14). For any R > 0, let Ts.d = R V e d) d+1
2 e - 1 +1)
where T is the Gamma fonnmafunctinn function. For any x By consider the mechanism Ve.R : B 5d-1 of generating Ze as the follows. First, generate random vector X (2b - 1)x where b is Bernoulli
Fe.d
random variable with success probability + ||r|||, Next, generate random vector Zg via 2ft.
{ Uniffz E Rd = 0. 0.12=l1z re,d} with probability e /(1 ([1+0)) t Unif(= E Rdd : X < 0, ||=||2 la re.d) with probability 1/(1 + ef).
Za
Then Ve,n is c-LDP and E [x)] = x.
Lemma 2.3 PPost-Processing property 19).. M X - y (E,5)-LD and f y - Z is a fixed
X + 2 is (c, LD-LP map, then f o :
Lemma 2.4 (Composition property 19)). M : X + Zi (EI, (1),81)-LD0 LDP and M2 : X + Zg is
(22,5))-LDP. then M = (M1, M2) X 21 Zg is (51 82 L.DP.
2.2 Local Differential Privacy in Bandit
We consider contextual bandits with LDP guarantee the context of the user-server communication protocol described in Figure 1 The user in round / with context X, E Rd receives (processed) historical information S. from the server, and chooses an action a, E [K] to obtain random reward v(X,, a.) E Define F, as the filtration of all historical information up to time
3

---

,t-1),, and we require 6, is bounded and B[e = 0. Then the user processes the tuple (X,, by some mechanism with LDP guarantee and send the processed information Ze = v rt) to the server. After receiving Ze, the server updates the historical information St to get S1+1- We consider the generalized linear bandits by allowing v(x,,a)) 0z) = ((X; 0 o.)) where u IR + R is a link function and f; E IR is the underlying parameter of the i-th arm. For fix time I, denote oj arg [a ( The regret over time
t, i.e. -X
horizon is Reg(T) = Ei= (M(X722) - ox))) If we don't assume any structure on {0) he(K], we refer the multi parametee setting. We also consider d- d-dimensional single-param setting by assuming 0 = e, @ l for some 0* E Ra where fer hejk is canonical basis of R In this case, Tt E IRd is the i-th segment of X E IRdK and X? 0; = 07,00 0" so choosing arm becomes choosing the i-th segment Jt, of the context.
Geal
Zet3
User Side
X
Server Side
S
Figure I: User communication protocol
In the rest of paper, we always assume that |00 S 1, E [K], the reward is bounded by c-- and the Euclidean norm of the context is bounded by CB. our analysis can be easily generalized to the case where e, and the context follow uub-gaussian distributions. subgaussian, it is guaranteed by the subgaussian concentration that there are at least T - O(log T') users have contexts and rewards bounded by CI.T, C2, with overwhelming probability, so we can still use above LDP mechanisms to protect their privacy. For users whose contexts and reward are out of range C1,r, C2,r, they can send a private version (0, 0) vector so that there is no privacy leakage. We also impose regularize assumptions the link function, which common in previous work 44 [1 33) and the corresponding family contains a lot commonly-use model, c.g., linear model, logistic model.
fact, when the context and noise are
Assumption 1. The link function μ is continuously differentiable, Lipschitz and there exists some <> such that Cnfre(-CuuCCl (z) Ç
3 Single-Paramettr Setting
In this section, we develop a LDP contextual bandit framework (Algorithm[] T by combining statistical estimation and privacy mechanisms in the single-param bandit setting to achieve optimal regret bound in various cases. We use an abstract privacy mechanism &b in ( and estimator in (2) to allow the plug-in of various components.
3.1 Privacy Guarantee
For the linear case where the link function (zx) = I, we can use the following ordinary least square (OLS) estimator. Let with de 2 lm(1.25/0) Define Mr = 2i, + W2 where W, is random matrix with Wi(i,) ~ (0 of s) and Wi(j.i) = Wi and TsCt. + & where & is random vector following distribution (0, C2 C2 TT). The OLS privacy mechanism and the corresponding estimator
1/ OLS
(It Fr; 0-11) (Mr, u)),
(3)
O0.5 (Z Ze; 0- = [ M, oVi1) Pt
Uii
(4)
i=1
where > is determined. We have the following LDP guarantee using the Gaussian mechanism (Lemma 2.1 and post-procsssing (Lemma 2.3

---

Algorithm 1: LDP panalerp Contextual Bandit
Input: Time horizon T; Privacy Level s,
Initialization: Setting 0g 0.
for t <- 1 to 7' do
User side:
Receive - from the server.
Pull arm a; argmaxue(K] d: and receive 7t.
Generate Z, by
Z: = Wel Te; 11)
(1)
Server side:
Receive Ze from the user. Update the estimation via
0, = (r(61...... Zz; Zz;0,-1 01
(2)
end
Proposition 3.1. Algorithm 7 with the private OLS update mechanism &OLS and estimator 4OLS is (c.6)-LDP E (0,1].
For the general link function μa, its non-linearity adds the difficulty in terms of both privacy- preserving and bandits. To estimate parameters in generalized linear bandits, one common approach use maximum likelihood estimator (MLE) each step. In contrast to OLS solution, MLE does not have close form solution with simple sufficient statistics in general. Thus, solving an MLE optimization procedure requires using all the previous data points and conducting costly operations at each round, resulting in time complexity and memory usage increasing with time. Instead, we use one-step stochastic gradient approximation to incrementally update the estimator with the new observation at each round. To obtain LDP version of this approximation, we use the LDP ball mechanism in Lemma
2.2
SGD (t re; 1) = Ve.1 (1(zzT,a. (e)
(5)
SGD (Z Ze: 0.11) 0 UDDD
where 7/s 0 is the stepsize be determined and R Cc, Similarly, we can prove the following LDP guarrantee using the la-ball mechanism Lemma 2.2 and post-processing Lemma 2.3
Proposition 3.2. Algorithum i with the private SGD update mechanism v SSD and estimator up is ED...
SGD
3.2 Regret Analysis
To derive the regret bound of our framework, we need the following assumptions on the marginal distribution Px of the stochastic contexts {araa
Assumption 2. There exists some K., > 0 such that Amax (E.) S fiy where En is the covariance matrix of Px and (Ea) is the largest eigenvalues of En.
Assumption 3. For every ||ul|2 1, denote a" = arg max xT_0 u, there exist some 1a > O.p+ such that Pu PT((TTo) > s//d 1)= 2 p. holds for any u, v E Sil-1, where P.(-) is the distribution of Tt
Similar assumptions are common the analysis of single-pane parammer contextual bandits, e.g. 13, 22
and our conditions contain wide range of distributions, including sub- gobs-gassian with bounded density. See appendix A for discussion. Now we can show that our framework indeed achieves optimal regret bound.
Theorem 3.1. Under Assumptions 2 and
with the choice of ē 20 2 logg(TT /a)) in and estimator COLS achieve the following regret with
Algorithm 1 with OLS mechanism 10
5

---

probability at least foror some constant C,
(Tg S CVT(CBlos. oo.dd / (d log (a) log KT/aa + +(())
kip-
Under Assumptions with SGD mechanism bi least 1 - a for some constant C,
B3 with the choice of nt ddd for some d' > 1 in (6). Algorithm /
WD and estimator ip: DpD achieves the following regret with probability at
Reg(T)- S CCVC Te,aVd log log (og(T
Ckipa
with o(1) means some factor that turns 0 as T co.
In the algorithm we shift the sample covariance matrix by ēvi to ensure the positive-definiteness of the noise matrix in 34 Such shift guarantee the estimation accuracy in the early stage. Note that the optimal worst-case regret bound in the non-privacy case is ((T1/2), our results show that can achieve the same regret bound as in the non-privacy case in terms of time T. In fact, we can show a (2( (e) lower bound in this setting even when = 2, which verified our optimal dependence on both T' and
Theorem 3.2. For E Rd and an algorithm τ, we denote E[Reg, - (T; 8) the expectation regret of when the underlying parameter is O. When K 2 and Ft,a N(, Ia/d) are independent over E [K], we have for any possible c-LDP algorithm x, supa $1 [R[ (T; (E(T//E).
Given the best known ((T3/4) regret bound of adversarial contextual LDP bandit in 44 our O(vT/e) result points out a possible gap between stochastic contextual bandits and adversarial contextual bandits under the LDP constriant.
The bounds given above are wooblem-indepeneen which do not dependent on the underlying parameters. If we consider additional assumption that there is gap between the optimal arm and the rest, which is usually the case when the number of contexts small, then we can obtain sharper bounds than the problem-independee
ones in Theorems 3.1
Assumption ((,, 3) -mmagin condition). We say Px satisfies the (7, -)strnn margin condition with y 0,0 < < 1, for D, := u( 0*) maxj40; ulxt, 0*) and h [0, with some positive constant b, we have P(D S h) S 5nh.
Theorem 3.3. Under Assumptions 20 with the same choice of é in Theorems 3.1
Algorithm D with OLS achieves the following regret with probability at least
OLS mechanism VOSS and estimator oi 1 a for some constant C,
BBB To CBd(CBO,
)² +03, (1),
8 8=1, 1,
RT) (T) SC
ktP.
BBB T + CBd(C + 0 +g.s)) d log(T/a) )+8 03,, (1),,
0 0
kiP+
Under Assumptions 7 and with the same choice of ni in Theorems Algorithm 7 with SGD mechanism v sSGD and estimator yi SGD achieves the following regret with probability at least a
for some constant C,
re.d L..LdCB (log(log(T)/a)) )² 03, (1)),
LCC (CCglogTe log T((
(Tg(T) SC.
Srip, 7LCB T - Fe LdC (log (T)/a) 1++ + 03, (1)), 0 3 <.
1-3 3
CRIPA
with (9,7(1) being a factor depending on B, that converges to 0 as T
Unlike in the worst-case bound, is more challenge to establish corresponding lower under the margin condition. A possible roadmap to show the ?(log T lower bound is to follow the argument in (1] Their argument uses the Van-Tree inequality to bound the mean squared estimation error from below for each time to show the 2(log T') bound in non-private setting. To consider the influence of private noise, possible to combine the IDP-version Van-Tree inequality 2 with the above argument to get O(log T/E3) bound.

---

Multi-parameter Setting
In this section, we present our LDP framework for the multiple parameter setting. Compared with the single parameter setting, this framework introduces three non-trivial components to match classical regret bounds while still guarantee LDP: warm up, synthetic update and climination.
Algorithm 2: LDP Multi Multi-parameter Contextual Bandit
Input: Time horizon 7: Warm up period length 80; Privacy Level E, 6.
Initialization: Setting du - 0, E [K].
for t < 1 to Kss do
User side:
Receiving 0.-1,1:K from the server.
Pulling arm 0₁ == (t mod K) + 1 and receive rt.
Generate and update Zt, = 1 ilvoeXX, rei 0 [K] to the server.
Server side:
Receive the update Zt,::K from the user.
Re-estimate parameters via 0₁, = (e Ze,)) Vi E [K].
end for
11
t Ks0 + 1 to T do
12
User side:
Receive - 0 from the server.
13
Determine subset K, of [K] by setting
14
K, {a E [K] X Ks.a
0 Ksa.a X [E[R]
max
2
Pulling a, argmax K (X? 0. and receive rt. Generating information for all arms (Zetk by setting
Zi {
v) r.; 01-1.)) (0,00,; otherwise.
if i,
Server side:
18
Receive the update (Ze,))e((k) from the user. Re-estimate parameters via
19
0., = (2((1,1) Zr.)).
20 end
Warm up. In the warm up stage, all arms are given equal opportunities to be explored for preliminary estimation of their parameters. Such estimation does aim for the accuracy to the optimal arm with high probability. Instead, we only need accuracy at the level of ruling out the substantially inferior arms. Thus, this stage only needs Ollog T) steps.
select
Since the actions in this stage are independent of the contexts, there no need to protect the pulled arm. However, we still need protect the contexts by using privacy mechanism similar in the Lingle-parameter setting.
Synthetic update. After the warm up, need to make decisions based the contexts achieve vanishing regret. In order to obtain the privacy guarantee, we introduce our synthetic update mecha- nism. Although in each time only arm is pulled, create synthetic data for all unselected arms. In this way, the server receives synthetic feedback about all arms, regardless whether is selected not, and thus cannot figure out which one is selected.
Another method to provide L.P protection for the selected arm is to ensure the action at satisfies LDP. However, the regret will grow linearly, shown in (34].

---

Elimination. We use the information obtained during warm up to exclude obviously inferior arms. Such method has been applied in [5] to guarantee certain kind of independence of the information in each round. However, we use this method for a different purpose. The necessity of such an elimination strategy comes from protecting privacy in the multi-parameter setting. Although we have obtained an estimation to a certain level of accuracy in the warm up stage, our knowledge on un-selected arms will be gradually corrupted by the noise incurred in the synthetic update in each round. Such corruption will make fail to distinguish arms that are possibly optimal from the surely sub-optimal ones. To avoid corruption, we may need to pick the sub-optimal arms frequently but this will result in large regret. That is why use the warm up information to eliminate the arms with extremely poor performance as in
4.1 Privacy Guarantee
The OLS/SGD mechanisms and estimators are the same as 3 (6) in the single-parament setting. To prevent the server from distinguishing the selected arm from the other K arms, straightforward idea is to use (=/K, 8/K) J-LDP mechanism for the synthetic update by composition property in lemma 2.4 However, we can prove that our algorithm can still achieve the same LDP guarantee with much less stringent privacy mechanism, say (e (e/2,6 8 6/2)-LDP, in Propositions and 4.2
Proposition 4.1. Algorithm 2
with the private OLS update mechanism vo and estimator OLS
(e, L.DP.
Proposition 4.2. Algorithm with the private SGD update mechanism x/. SCD and estimator 4i SGD e-LDP.
4.2 Regret Analysis
Assumption (Diversity condition). Let Kopt and Koub be a partition of [K] such that for any i E Kubb pb (.) max ((TT8,) hgub for some hug > and every X X. For any
i E Kopt define the set U, = (X ((X > max u(TT0,) There exists K4 > 0. such that for all E Kopt and unit vector v.P((u" (X E U,} 2 K1 (//Kpt)) > >p'.
Assumption 6 ((7,3))margee condition). This is almost identical to Assumption 4 exxeppt that replace Dr with D = p(( - max (x,
In our algorithm, diversity condition guarantees that conditioning on the arm i is pulled, the distribu- tion of X, still can provide enough information about 0,. We would remark here that we need no longer any deterministic gap in the definition of U,, which weakens the assumption made in [4. 5 Now we are in the suited position to present our theoretical guarantee of the algorithm.
Theorem 4.1. Under Assumptions
ond with the choice of ė = 20 2 (TK/a))
in So C KY CB.. + 0E.6 (d + log(TK/a)) and = h do = (2 1 Algorithm
)10,,
min No, hpp/k)
2 with OLS mechanism VOLS and estimator pOLS achieve the following regret with
probability least a for some constant C,
log T.
B=1,
RTg(T) & xCCBB
[
KCn(Cno, + aa.s) log (oggooo//()))))))o (TK)/a) 143 + A
T _
kipl
0 0<
1
Under Assumptions
anddo with the choice of step-size
Ti : (1 mod K) + 1) (() (K 1K- - Kopt (Srup') for any 2' and h hid Algorithm 2 with SGD mechanism v.SGD and estimator SGD achieve the following regret with probability at least 1 for some constant C,
log T, T
B = 1,
KreaLCB (T (TK log log ) 1+8 + Oh B (1)
Reg(TT) S LLCBB
(kipl
0 1<
1- 3'
Theorem 4.1
recovers the non-privacy bound in (5) under similar condition up to a logarithmic factor. Notice that unlike Theorem 3.3 in the single- parameter case, we cannot establish the regret when
8

---

3 = 0. The reason is that in our analysis, we need the probability of 4, > h vanish as h + 0 to guarantee the estimation error for 0 2 Kopt converges. The corresponding theoretical result in this setting when 3 = O is left as an open question.
5 Experiment
To the best of our knowledge, the contextual bandit algorithms with LDP guarantee has only been studied by 4 who propose variant of LinUCB algorithm for linear bandits and variant of Generalized Linear Online-to-confidencess Conversion (GLOC) framework [23] for generalized linear bandits. We refer their methods LDP-UCB and LDP-GLOC. We call our method LDP-OLS we plug in the OLS mechanism and estimator into Algorithms | aad and LDP-SGD if we plug in the SGD ones. We evaluate all the four methods synthetic datasets, which are industry standards. For example, Apple uses = 4 in their projects on Emojis and Safari usage [38]. Similar choices of the privacy parameter can be found in [3] 20] We also demonstrate the efficacy of our algorithmss with real data on Auto Lending in Appendix G For the sake of comparison, the learning step parameter for I.DP-GI LDP-GLOC and I.P-SGID are tuned in the same way |
different privacy levels & 0.5 and in
The first and second columns in Figure 4 are for single- param and multi-param settings, respectively, which are simulation studies on linear bandits. The context is generated from Uni at each round.
In conclusion, our methods significantly outperform existing ones in all settings consistently. LDP- SGD achieves better performance under more strigent privacy requirements.
10 Singlo-param (8 = 0.5, K 10, =d
10a Multi-param (e 0.5, K = =3 2)
Cumulative Regret
01
0.2
0.6
0.8
0.2
0.4
0.6
Time
-106
Time
-109
I.P--UCB
100
Single-param =
10,
2)
-10
Multiple (5 1,
2.5
Cumulative Rogret
4
1-
0.5
0
0.2
0.4
0.6
01.8
0..2
0.4
0.6
0.8
Time
Time
-106
Figure 2: We perform 10 replications for each case and plot the mean and 0.5 standard deviation of their regrets.
'On-Line Auto Lending dataset ERPM-12-001 provided by Columbia University https:: //we:////wwwwee. .sb columbia. cchu//prm/aa edu/cptm/researchh dadaatstta and has been used the study contextual handits by 26
"The source code reproduce all the results is available the GitHub repo Bearepp/DP-BBadle

---

6 Conclusion
In this paper, we propose LDP contextual bandit frameworks in both single-parameter and multi- parameter settings with f to deal generalized linear reward structure, and establish theoretical guarantee of our algorithms based on the frameworks. Our algorithms are highly efficient and have superior empirical performance. There are still some open questions to be explored. Whether our regret bounds are optimal terms of in the multi-paramenn interesting to explore estimators and mechanisms beyond the private OLS and SGD ones to study the optimality in terms of e. Moreover, whether there a fundamental limit adversarial contextual bandit under LDP constraints is still an open question. It also remains an open question to analyze the regret bound the parali-pr setting when 3 0 in the margin condition.
setting is still unknown. will be
Acknowledgments and Disclosure of Funding
This work was supported by Hong Kong Research Grant Council (Grants 16317416, 16204718. 16214121) and Guangdong-Hong Kong-Macao Joint Laboratory for Data-Driven Fluid Mechanics and Engineering Applications.
References
[1] G.-Y. Ban and N. B. Keskin. Personalized dynamic pricing with machine learning: High dimensional features and heterogeneous elasticity. Forthcoming, Management Science, 2020.
[2] L. P. Barnes, W.-N. Chen, and A. Özgür. Fisher information under local differential privacy.
IEEE Journal on Selected Areas in Information Theory, 13)):445-55, 2020.
[3] R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta. Practical locally private heavy hitters. 1etp::007.099993 2017.
arXiv preprint
2017.
[4] H. Bastani and M. Bayati. Online decision making with high dinensiieenii covariates. Operations Research, 68(1):276-2944 2020.
[5] H. Bastani, M. Bayati, and K. Khosravi. Mostly exploration-free algorithms for contextual bandits. arXiv, pages 1-62, 2017.
[6] D. Basu, C. Dimitrakakis, and A. Tossou. Differential privacy for multi-armed bandits: What is it and what its cost? arXiv, pages 1-27, 2019.
[7] A. Bietti, Agarwal, and J. Langford. A Contextual Bandit Bake-off. pages 1-45, 2018.
[8] K. Chaudhuri, Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 12(3), 2011.
[9] X. Chen, D. Simchi-Levi, and Y. Wang. Privacy-preseriing dynamic personalized pricing with demand learning. arXiv, pages 1-35, 2020.
[10] X. Chen, K. Zheng, Z. Zhou, Y. Yang, W. Chen, and L. Wang. (Locally) Differentially Private Combinatorial Semi-Bandits. arXiv, 2020.
[11] W. C. Cheung, D. Simchi-Levi, and R. Zhu. Hedging the drift: Learning to optimize under non-stationarity. Available at SSRN 3261050, 2018.
[12] B. Ding, J. Kulkarni, and S. Yekhanin. Collecting telemetry data privately. arXiv preprint arXiv: 171.001524 2017.
[13] Q. Ding, C.-J. Hsich, and J. Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference Artificial Intelligence and Statistics, pages 1585-1593, PMLR, 2021.
[14] J. C. Duchi and M. Jordan. Minimax Optimal Procedures for Locally Private Estimation.
[15] C. Duchi, M. Jordan, and M. Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-- 182-201, 2018.
10

---

[16] C. C.Dorkk, K. Kenthapadi, F. McSherry. I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486-503. Springer, 2006.
[17] C. Dwork and J. Lei. Differential privacy and robust statistics. In Proceedings of the forty-first anmual ACM symposium on Theory of computing, pages 371 371-380, 2009.
[18] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[19] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4) 2013.
[20] Ó. Erlingsson, V. Pihur, and A. Korolova. Rappor: Randomized aggregatable privacy-presee rivacc-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference computer and communications security, pages 1054-1067, 2014.
[21] A. Goldenshluger and A. Zeevi. A linear response bandit problem. Stochastic Systems, 3(1):230- 261, 2013.
[22] Y. Han, Z. Zhou, Z. Zhou, J. Blanchet, P. W. Glynn, and Y. Ye. Sequential batch learning in finite-action lincar contextual bandits. arXiv, 2020.
[23] K. S. Jun, A. Bhargava, R. Nowak, and R. Willett. Scalable generalized linear bandits: On- line computation and hashing. Advances in Neural Information Processing Systems, 2017- 1 2017.
[24] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[25] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2833 -2330. 2011.
[26] R. Phillips, A. Şimsek, and G. Van Ryzin. The effectiveness of field price discretion: Empirical evidence from auto lending. Management Science, 61(8):1741-1759, 2015.
[27] M. Raghavan, A. Slivkins, J. W. Vaughan, and Z. S. Wu. The externalities of exploration and how data diversity helps exploitation. arXiv, 2018.
[28] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv: 109.55///09964777 2011.
[29] W. Ren, X. Zhou, J. Liu, and N. B. Shroff. Multi-Armed Bandits with Local Differential Privacy. arXiv, 2020.
[30] Z. Ren and Z. Zhou. Dynamic batch learning in high-dimensional sparse linear contextual bandits. arXiv, pages 1-33, 2020.
[31] Z. Ren, Z. Zhou, and J. R. Kalagnanam. Batched learning in generalized linear contextual bandits with general decision sets. IEEE Control Systems Letters, 2020.
[32] C. Riquelme, G. Tucker, and J. Snoek. Deep bayesian bandits showdown: An empirical com- parison of bayesian deep networks for thompson sampling. arXiv preprint 1802.00802.090 2018.
[33] B. I. Rubinstein, P. L. Bartlett, L. Huang, and N. Taft. Learning in large function space: Privacy-preserving mechanisms for svm learning. arXiv preprint arXiv:0911.5708, 2009.
[34] R. Shariff and O. Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 2015-Decembbr:4296-40000 2018
[35] A. Slivkins. Introduction to multi-armed bandits. Foundations and Trends Machine Learning, 12(1-2):1-286, 2019.

---

[36] A. Smith. Privacy preserving statistical estimation with optimal convergence rates. In Pro- ceedings of the forty-third third annual ACM symposium on Theory of computing, pages 813-822, 2011.
[37] J. Tang, A. Korolova, X. Bai, X. Wang, and X. Wang. Privacy loss in apple's implementation of differential privacy on macos 10.12. 12. arXiv preprint arXiv:1799.02553, 2017.
[38] D. Team. Learning with privacy at scale. 2017.
[39] Toulis, R. Airoldi, and J. Rennie. Statistical analysis of stochastic gradient methods for generalized linear models. In International Conference on Machine Learning, pages 667-675. PMLR, 2014.
[40] J. A. Tropp. User-friendly tail bounds for matrix martingales. 2011.
[41] A. B. Tsybakov. Introduction to nonparametric estimation. Springer Science & Business Media,
2008.
[42] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[43] L.. Wasserman and S. Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-38, 2010.
[44] K. Zheng, T. Cai, W. Huang, Z. Li, and L. Wang. Locally Differentially Private (Contextual) Bandits Learning. arXiv, (NeurIPS))1-201 2020.
12


Reviews:
[{"review_id": "kwzxgsknDPt", "reviewer": "Reviewer_5SWK", "summary": "This work considers local differential privacy in stochastic generalized linear bandits with both single and multiple parameters, and thus develops LDP algorithms for both settings and analyzed the same regret bounds as in privacy-free setups.", "questions": "", "limitations": "", "rating": 7, "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": "Originality: \nLDP framework for multi-parameter setting seems novel and sophisticatedly designed so that it creates synthetic data for unselected arm to protect privacy from the server, and eliminates some inferior arms to avoid corruption caused by the synthetic update. \n\nQuality:\nThe regret bounds for LDP algorithms seem theoretically well-grounded, and corresponding assumptions such as diversity and margin are the standard up to my knowledge.  It provides a complete piece in that it points out a clear theoretical gap in existing result by proving the lower bound, and closes this gap by proposing LDP algorithms. The numerical experiments also provides fair comparison to existing algorithms such as LDP-UCB and LDP-GLOC.\n\nClarity:\nThis submission is clearly stated in two different settings (single and multi-parameter) and well organized along with theoretical result and then numerical experiments.\n\nSignificance:\nLDP is a state-of-the-art approach among those which allows statistical computations and protects each user's privacy. This is because unlike standard DP no trust in a server is necessary as noise is added to user inputs locally. It clearly solves the open problem : “can we close the gap between existing privacy result and non-privacy results?” by providing several LDP algorithm and obtaining the same regret bounds as non-private setup.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work provides a complete piece of story with well-grounded theoretical result and experiments. I cannot find limitations on this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "bi4G2j9DsS0", "reviewer": "Reviewer_ydgj", "summary": "This paper combines generalized linear bandits and local differential privacy. Empirical experiments demonstrate that new method is superb in real datasets.", "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": "This paper is well-written and very clear in its motivation. The DP part of this paper looks legit though I didn't go through the details of the proof.\n\nI have one questions: Lemma 2.1 seems incomplete to Theorem 3.22 [17], which holds only for $\\epsilon\\leq 1$. But in your experiments I see $\\epsilon=5$ which should be guaranteed by Gaussian mechanism. Did I miss anything?\n\nAlso Equation (3) has a typo: it should be inverse of $M_t$.\n\nI am no expert in contextual bandit so I cannot comment on this part.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "NgvaokWHioN", "reviewer": "Reviewer_SZ1X", "summary": "The paper studies (generalized) linear contextual bandits in the context of local differential privacy (DP). At every time step a single user’s sensitive data point arrives, which serves as a context, and a reward is sampled as a function of this context and an unknown (generalized) linear reward-generating function. The difficulty with minimizing regret with local DP is that one has to learn the reward-generating function without compromising users’ privacy. The analysis is split by cases: in the setting of linear rewards, an OLS-based solution is proposed, and in the setting of generalized linear rewards, an SGD-based solution is proposed. In addition, two different bandit models are considered depending on whether the rewards from different arms are related.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "I am not very familiar with the works most closely related to this paper (e.g. [36]), but it appears that this paper is the first one to combine (1) local DP (2) stochastic generalized linear bandits. Prior work has studied joint DP + generalized linear bandits [8] or local DP + generalized linear bandits [36], but in an adversarial setting. So in the context of recent work the problem studied in this submission arises naturally.\n\n I am not sure if there is a significant complication in the linear case, where an OLS-based solution is proposed. In particular, the solution is based on perturbing the sufficient statistics, similar to, e.g., [29] and [36]. What is the main technical difference here?\n The SGD solution is elegant and arguably more interesting. Even without privacy concerns, it seems that theoretical regret bounds have been elusive for SGD-based approaches. In either case, the proof technique makes conceptual sense. \n\nI have some clarifying questions and comments about the specifics:\n1. Is the dependence on T the right dependence, meaning it matches the respective dependence without privacy, across all settings in Table 1?\n2. What is the intuition behind the covariance offset in equation (4) scaling as sqrt(t)?\n3. Can you clarify this point - “Although multi-parameter and single-parameter settings can be shown to be equivalent, they need independent analysis”? Why can one analysis not be translated into the other setting if they are equivalent?\n4. Do you know if the dependence on d in the theorems is (sub)optimal?\n5. Sometimes when you use $O$ you actually mean $\\tilde O$. Please use these symbols consistently.\n6. In line 127, please clarify which norm the context is bounded in (I guess $\\ell_2$).\n7. In Theorem 3.3, you use C1 and C2 in the text, but in the equation lines you use C in both cases.\n8. In line 115, you set the problem up as having subgaussian noise, but then in line 127 you say that you can generalize to subgaussian and that the noise is bounded. Please make the problem setup consistent with these latter assumptions.\n9. The notation paragraph defines a lot of standard concepts (such as the asymptotic notation). I think you could make it significantly shorter (and maybe save the extra space to add more details elsewhere).\n10. There are some problems with the statement of Assumption 3. You define a* but don’t use it (note also the way it’s stated a* is a function of u), you also use v in the probability statement but it’s not defined.\n11. There is something strange about the formulation of the single-parameter problem in line 123, as the outer product of e_i and \\theta* is a matrix. The formulation in line 124 is clear.\n12. In lines 26/27, you say “jointly DP”/“locally DP”. I believe the standard terms are “joint DP”/“local DP”.\n13. In Theorem 3.2, you define Reg_\\pi notation for an algorithm \\pi, but then you don’t use this subscript notation in the end, in line 188.\n\n---------------------------------------------------------------------------------------------------------------------------------------------------\n\nI thank the authors for their thorough response. I think it would be helpful to add many of these details in the final version for the sake of clarity.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discusses several limitations (as natural directions for future work). It doesn't discuss potential negative societal impacts, but the work is largely theoretical and builds on well-studied models in the literature, so I do not see potential societal concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "F0GulrAuTvL", "reviewer": "Reviewer_9jC7", "summary": "Authors design LDP algorithms for stochastic generalized linear bandits to achieve the same regret bound as in non-privacy settings. The main idea is to develop a stochastic gradient-based estimator and update mechanism to ensure LDP. They also develop an estimator and update mechanism based on Ordinary Least Square (OLS) for linear bandits. Finally, they conduct experiments with both simulation and real-world datasets to demonstrate the consistently superb performance of algorithms to ensure strong privacy protection. ", "questions": "", "limitations": "", "rating": 7, "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": "The method is new and a combination of well-known techniques. The related works are adequately cited and it is clear for the comparison. \nThe submission is technically sound, and claims are well supported. Methods are used appropriately and it’s a complete work. The authors are careful and honest about evaluating both the strengths and weaknesses of their work. \nThe submission is clearly written and well organized. \nThe results are important and does advance the state of art. \nThere maybe some typos. Such as Line 115, what is this sigma?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for the submission; the reviewers were all positive about this paper. 
Decision: Accept (Poster)