On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence

Summary

The paper considers the best arm identification (BAI) problem under differential privacy (DP) constraints, where the goal is to privately identify the arm with the highest expected reward with probability at least $1 - \delta$. The paper proposes a DP variant of the top two algorithm, which achieves near-optimal performance in the high privacy regime. The paper also proves an information-theoretic instance-dependent lower bound for the DP-BAI problem. The paper also conducts experiments on synthetic data to demonstrate the efficiency of the proposed algorithm.

Strengths

The proposed upper and lower bounds match each other in the high-privacy regime when the true means are away from 0 or 1. This provides an up-to-constant characterization of the asymptotic sample complexity for DP-BAI. The proposed algorithm empirically outperforms a natural DP variant of the successive elimination algorithm. The paper is also nicely written and easy to read.

Weaknesses

While DP-BAI is an interesting problem to study, the techniques used in the paper are primarily natural variants of previous work. In particular, nonprivate-BAI and the closely related DP regret minimization in the bandit setting have been studied. Hence the technical novelty of the paper is restricted. It would be nice if the authors could comment on the non-asymptotic optimality of the proposed algorithm. Minor comments: 1. Not sure if colored texts are supported for NeurIPS submissions. 2. Definition 1: The letter d is a bit overloaded. Maybe it is better to use $D$ or $\mathcal{D}$ to refer to datasets, which is used later in the paper. 3. Line 207: Might be good to have parentheses after sup. 4. Can you comment on how $T^*_{TV}(\nu)$ and $T^*_{KL}(\nu)$ relate to each other? 5. Algorithm 2: $L_n$'s are not initialized.

Questions

See comments above.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes.

Summary

This work provides some insight into using the Laplace mechanism on the algorithms concerning the best arm identification problem bandits with a constraint of fixed confidence. The analysis carried out in this work enumerates general properties of differentially private FC-BAI and then proposes an algorithm based on those bounds.

Strengths

Analysis carried out in this work is general to all algorithms that are designed to solve the BAI problem where there are some guarantees presented on the sample complexity of such class of algorithms.

Weaknesses

No weaknesses found in this paper, as per the knowledge of the reviewer.

Questions

-

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

No additional limitations can be seen in this work. All the limitations, to the reviewer's knowledge, have been addressed properly in the paper.

Summary

This paper studies the problem of Best Arm Identification (BAI) for bandit problems under the constraints of differential privacy. There are some $K$ distributions and the solver interacts with the arms over a sequence of rounds. In each round they choose a distribution and receive a reward according to that distribution. The goal is to identify the arm with the highest expected reward with certainty $1-\delta$ where $\delta$ is a Fixed Confidence (FC) parameter given to the solver. Motivated by real-world problems like clinical trials for testing doses/efficacy of drugs, the authors suggest studying this problem under the constraint of differential privacy - this is relevant when the rewards received might be private information, such as the medical data of a patient's response to the drug/dose they were administered. The contributions of this paper are as follows: 1. The authors derive a lower bound on the sample complexity for DP-FC-BAI problem - their results suggest that the problem can be characterized in the low-privacy and high privacy regimes. In the former it seems that the sample complexity of the problem is unaffected by the DP constraint. 2. They present an algorithm, AdaP-TT, which is a differentially private version of the Top Two Upper Confidence Bound (TTUCB) algorithm from prior work. The sample complexity of this algorithm matches the lower bound asymptotically in the high-privacy regime. 3. The conduct some experiments showing that their algorithm has lower sample complexity compared to another differentially private approach (DP Successive-Elimination).

Strengths

1. The problem being studied is very well-motivated - in particular the example of dose finding and the necessity of privacy preserving BAI is compelling. 2. The authors provide a lower bound and characterize the hardness of the problem. 3. The algorithm they provide (privatizing the optimal sample complexity achieving method in the non-private setting) seems to work well in practice based on their experiments. At a cursory look the performance of the algorithms seem to corroborate the constant factors in the sample complexity terms that the authors derived.

Weaknesses

1. I found this paper very hard to read - the questions being considered by the authors make sense but the expressions derived are not easy to make sense of. The presentation is hard to follow - some terms are introduced without much context (such as ``Top Two algorithms" on the second page) and this paper seems hard for non-experts to follow. 2. On page 2 the authors say "A calibrated amount of noise, from a Laplace [DR14] or Gaussian distribution [DRS22], is injected into an algorithm to ensure DP. The noise scale is set to be proportional to the algorithm’s sensitivity and inversely proportional to the privacy budget $\varepsilon$." I think this statement is somewhat misleading - DP can be achieved in many ways and obfuscating noise is routinely drawn from many distributions (including the Gumbel distribuion, Poisson distributions, or other ad-hoc methods depending on the setting). Indeed, as the authors themselves find in their lower bound, sometimes privacy can be achieved for free. Similarly, the way the scale of the noise is chosen can be very involved - it is not always possible to derive a uniform bound on the sensitivity of an algorithm or such a method could give a very sub-optimal result. It is also important to note that not all problems admit DP solutions - there is no meaningful DP way to compute the XOR of $n$ private bits, for instance. 3. The expressions in the lower bound are hard to interpret - ideally one might want to characterize them only in terms of the problem parameters i.e. the number of arms $K$, the confidence parameter $\delta$ and the privacy parameter $\varepsilon$ - the given bound seems to be more general which is great (as it describes the hardness in terms of the expected rewards), but is it possible to instead substitute a hard instance for the $\mu_i$ and $\Delta_a$ values and derive a more readable corollary? 4. The approach does not seem to be very novel as it reduces to essentially just applying the Laplace mechanism at one point of the TTUCB algorithm from prior work. The sensitivity admits a straightforward bound as well.

Questions

1. You define a low and high privacy regime based on $\varepsilon$, $T_{KL}^*$ and $T_{TV}^*$, but the expressions for these depend upon $\mu_i$ which the solver does not have access to. Operationally, is there any way for the solver to know whether they are in the low privacy or high privacy regime? 2. The claim that there is no additional cost of privacy in terms of sample complexity for the low-privacy regime seems to need some more justification - there is a matching upper bound in the high-privacy regime but since there is no matching upper bound for the low-privacy regime, couldn't there just be a stronger lower bound which holds that we are not yet aware of?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

1 poor

Contribution

3 good

Limitations

Potential negative societal impacts do not need to be discussed here as this is primarily a theoretical paper.

Summary

This work provides novel theoretical guarantees to quantify the cost of privacy in DP-FC-BAI (and $\epsilon$ global DP). Specifically, the authors show that the complexity depends on an information theoretic total variation metric. Although, this holds in the high privacy regime, this is reasonable and possibly connected with results on strong data processing inequalities in prior works. Through their lower bound ,the authors show consistency and recover the non-private regime as well. Additionally, the authors propose a variant of existing algorithms with asymptotically matching upper bound.

Strengths

The originality of the paper is clear. The presentation is clear and the contributions are significant. The total variation characteristic time is a novel quantity that it is introduced in this work. The proposed algorithm (AdaP-TT) is also novel and achieves matching guarantees with the proposed lower bound. The authors manage to characterize a phase transition effect: in the low privacy regime the privacy can be achieved for free. This is correct and has been observed in prior works as well (but for Thomson sampling). The results of the work are the first lower bounds for DP BAI, and they successfully characterize the hardness of the problem.

Weaknesses

The proof techniques appear to be mostly applications of known proof techniques. Sketches of proofs for the lower and upper bounds can potentially improve further the quality of the paper. The sketches should provide details on the novelty of the proof technique and several steps of the proof (similarly to proof of Lemma 1 in the Appendix). A few references are missing, for instance "On the Renyi differential privacy of the shuffle model" by Girgis et al., "Secure best arm identification in multi-armed bandits" by Ciucanu at al. Finally, the format of some references in the bibliography can be improved, some references point to older version of prior works on arxiv, while the papers have been published, for instance see [KNSS20].

Questions

Which parts of the proofs technique are novel? Could you please include proof sketches that emphasize on the proof technique? Does the total variation uniquely characterize the hardness of the problem? Can the lower bounds be expressed in terms of the KL divergence instead?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

The authors adequately addressed the limitations.

Summary

This paper studies the problem of BAI with fixed confidence under ϵ-global Differential Privacy (DP). The authors derive a lower bound on the sample complexity of any δ-correct BAI algorithm satisfying ϵ-global DP. In addition, the authors also design an ϵ-global DP variant of the Top Two algorithm, named AdaP-TT. AdaP-TT runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utility trade-off. The authors provide an asymptotic upper bound on the sample complexity of AdaP-TT, which matches the lower bound up to multiplicative constants in the high-privacy regime. Finally, the authors also conduct experiments to validate their theoretical results.

Strengths

1. The studied problem, differential privacy in best arm identification, is interesting and finds applications such as clinical trials and hyper-parameter tuning. 2. The provided lower bound result is very interesting. The authors give a deep discussion on the problem hardness in two regimes. In the high-privacy regime, the hardness depends on a coupled effect of privacy and a novel information-theoretic quantity, i.e., total variation characteristic time. In the low-privacy regime, the sample complexity lower bound is the same as that in classic (non-private) best arm identification.

Weaknesses

1. The writing of this paper should be improved. This paper is very dense and difficult to follow. 2. The authors only provide asymptotic sample complexity for their algorithm AdaP-TT. Can the authors provide a non-asymptotic sample complexity, or give some ideas? 3. Can the authors discuss the technical novelty compared to existing works on DP with regret minimization? What is the unique challenge brought by the best arm identification setting?

Questions

Please see the weaknesses above.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

1 poor

Contribution

3 good

Limitations

Please see the weaknesses above.

Summary

This paper studies the problem of best arm identification with fixed confidence under ϵ-global Differential Privacy. First, they provide a lower bound of the BAI-DP problem showing that two different regimes depend on the privacy budget of $\epsilon$. They propose an ϵ-global DP variant of the Top Two algorithm, called AdaP-TT, and provide its asymptotic sample complexity. They also conduct experiments that confirm the theoretical validity.

Strengths

(originality) -They first derive the hardness result giving a lower bound for the problem of best arm identification with fixed confidence under ϵ-global Differential Privacy. For the high-private regime, the lower bound depends on the Total Variation Characteristic Time, which shares a similar spirit with the regret minimization with ϵ-global DP [AB22]. For low-private regimes, the lower bound reduces to the classical no-private lower bound. -As an algorithmic contribution, they devise variants of Top Two algorithms, called AdaP-TT, based on non-private TTUCB[JD22]. They propose a sample complexity in an asymptotic regime, which is the order-optimal up to some constants. (quality) The paper is well-structured and easy to follow.

Weaknesses

-As discussed in the paper, in BAI setting the only Information is leaked when publishing all the sequence of actions $\{a_s\}_{s<t}$ and the final recommendation a^*, which might not be frequently common situations, since BAI setting, the decision of final output is more interested. The presented problem is more of an artificial problem, although theoretical results are valid and new insights. -Related above, the privacy issues should be more important for the case where multiple players may exist rather than only a single player is involved, as in federated learning. With regard to multi-agent bandit problems, recently the following paper studied the best arm identification with DP setting and propose the DP successive elimination based on [SS19]. [Rio et al 2023] Multi-Agent Best Arm Identification with Private Communications. Alexandre Rio, Merwan Barlier, Igor Colin, Marta Soare. Proceedings of the 40th International Conference on Machine Learning, PMLR 202:29082-29102, 2023. I believe that a comparison with this paper should be required before the publication, even though [Rio et al 2023] might have been public after the NeurIPS submission date (So lacking this comparison in the current is not the reason for rejection). [Rio et al 2023] consider a lower bound but only for the extreme non-private setting, where agents share all their raw reward samples with the central coordinator. Therefore, the submitted paper’s analysis for lower bound might be still novel. However, DP successive elimination proposed in [Rio et al 2023] could cover the single agent BAI-DP. Therefore the authors could do a comparison with this paper. ======After rebuttal====== My concerns are fully addressed. Hence I changed my score from 5 to 7.

Questions

Could you provide comparison with [Rio et al 2023]?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Response to the Rebuttal

Thank you for your detailed response. I have another question regarding the tightness of the bound in the high privacy regime. This property seems to hold for other settings as well. For instance in hidden probabilistic graphical models, where only noisy observations are available there exist similar properties. For instance, in the work "Optimal Rates for Learning Hidden Tree Structures" by Nikolakakis et al. the upper and lower bounds appear to match for the highly noisy regime (only) as well. I think that the role of the privacy cost $\epsilon$ has the quantity noisy information threshold as it is defined in the paper "Optimal Rates for Learning Hidden Tree Structures". Thus the property of tightness in the highly noisy regime can go beyond the setting of differential privacy and raise other information theoretic questions. Could the authors please verify if this is the case. If there is indeed a connection, it would be useful to compare this phenomenon with noisy probabilistic models in prior work "Optimal Rates for Learning Hidden Tree Structures" and highlight such similar properties.

Thank the authors for their response.

Thank the authors for their response. I tend to keep my score.

Response to rebuttal

Thank you for your detailed response. After reading your meta rebuttal and the discussions with the other reviewers I would be happy to change my score from a 4 to a 5. As suggested elsewhere some more work could be done on general readability and highlighting the novelty of your work.

Thanks for the feedback

Thank you very much for your detailed feedback. I am grateful for the authors to discuss the theoretical and empirical comparison with Multi-Agent DP-BAI-FC [Rio et al 2023]. Also, I acknowledge the motivation for DP-BAI problem in real-world scenarios. I read other reviewers' points and believe that this submission is in good form.