Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 
The 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. 
The submission is clearly written and well organized. 
The results are important and does advance the state of art. 
There maybe some typos. Such as Line 115, what is this sigma?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper combines generalized linear bandits and local differential privacy. Empirical experiments demonstrate that new method is superb in real datasets.
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.

I 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?

Also Equation (3) has a typo: it should be inverse of $M_t$.

I am no expert in contextual bandit so I cannot comment on this part.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Originality: 
LDP 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. 

Quality:
The 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.

Clarity:
This submission is clearly stated in two different settings (single and multi-parameter) and well organized along with theoretical result and then numerical experiments.

Significance:
LDP 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.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

 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?
 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. 

I have some clarifying questions and comments about the specifics:
1. Is the dependence on T the right dependence, meaning it matches the respective dependence without privacy, across all settings in Table 1?
2. What is the intuition behind the covariance offset in equation (4) scaling as sqrt(t)?
3. 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?
4. Do you know if the dependence on d in the theorems is (sub)optimal?
5. Sometimes when you use $O$ you actually mean $\tilde O$. Please use these symbols consistently.
6. In line 127, please clarify which norm the context is bounded in (I guess $\ell_2$).
7. In Theorem 3.3, you use C1 and C2 in the text, but in the equation lines you use C in both cases.
8. 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.
9. 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).
10. 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.
11. 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.
12. In lines 26/27, you say “jointly DP”/“locally DP”. I believe the standard terms are “joint DP”/“local DP”.
13. 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.

---------------------------------------------------------------------------------------------------------------------------------------------------

I 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.
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_title: null

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