Pith. sign in

REVIEW 3 major objections 4 minor 23 references

Locally Differentially Private Thresholding Bandits

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Thresholding bandits under local differential privacy can match their non-private rates up to logarithmic factors.

desk verdict First LDP thresholding bandit paper with a clean rescaling insight; fixed-confidence radius and a KL inequality need fixing before the theorems hold. read the letter →

arxiv 2507.23073 v2 pith:JMRBUREZ submitted 2025-07-30 cs.LG

Annalisa Barbara , Joseph Lazzaro , Ciara Pike-Burke This is my paper
classification cs.LG
keywords thresholdingbanditslocaldifferentialprivacyBernoullimechanismfixedbudgetconfidencesamplecomplexityminimaxlowerboundspureexploration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tackles the thresholding bandit problem—finding all arms whose expected reward exceeds a known threshold—when the algorithm may only see locally privatized rewards. It shows that replacing raw rewards with Bernoulli privatized responses, and rescaling the threshold accordingly, yields algorithms for both fixed-budget and fixed-confidence settings. The paper's central claim is that this privacy protection is cheap in the high-privacy regime: the fixed-budget expected misclassification decays exponentially in the budget divided by a privacy-adjusted complexity term, and the fixed-confidence algorithm stops after $O(H_\epsilon \log(KH_\epsilon/\delta))$ pulls while returning the correct set with probability at least $1-\delta$. It further proves minimax lower bounds for any $\epsilon$-LDP algorithm and shows both algorithms match these bounds up to logarithmic factors as $\epsilon\to 0$, so the Bernoulli mechanism is essentially optimal for strong privacy.

What carries the argument

The carrying mechanism is the Bernoulli privatization map (PrivBern), which sends a reward $r\in[0,1]$ to a Bernoulli outcome with mean $(r e^\epsilon + (1-r))/(1+e^\epsilon)$, an $\epsilon$-differentially private transform. Applied to an arm with true mean $\mu_i$, it produces observations with shifted mean $\mu_{i,\epsilon}=\tfrac12 + (2\mu_i-1)\tfrac{e^\epsilon-1}{2(e^\epsilon+1)}$; the threshold $\tau$ and tolerance $\zeta$ are shifted the same way, giving a privacy-adjusted complexity $H_\epsilon=\sum_i (|\mu_{i,\epsilon}-\tau_\epsilon|+\zeta_\epsilon)^{-2} = \bigl(\tfrac{e^\epsilon-1}{e^\epsilon+1}\bigr)^{-2} H$. All upper bounds are expressed through $H_\epsilon$, and the lower bounds show this same $H_\epsilon$ characterises the minimax difficulty in the small-$\epsilon$ regime, which is why the algorithms inherit the non-private structure and only pay logarithmic factors for privacy.

What would settle it

Compute or simulate $P(|\hat\mu_{t,i}-\mu_{i,\epsilon}| \ge r_t(i))$ for the radius $r_t(i)=\sqrt{\log(4Kt^3/\delta)/(8T_i(t))}$ with Bernoulli observations; Hoeffding's inequality gives roughly $2(\delta/(4Kt^3))^{1/4}$, which exceeds $\delta/(2Kt^3)$ by a factor on the order of $(Kt^3/\delta)^{3/4}$, so the sum over $t$ does not converge as the proof requires, and the stated $1-\delta$ correctness of Algorithm 2 would fail unless a different radius or proof is used.

Watch

Extended reading notes

Core claim

Algorithm 1 (fixed budget) pulls the arm minimizing $B_k(t)=\sqrt{T_k(t-1)}\,\hat{\Delta}_{k,\epsilon}(t-1)$, where $\hat{\Delta}_{k,\epsilon}$ is the empirical deviation of the privatized mean from the rescaled threshold, and returns arms with privatized empirical mean above $\tau_\epsilon$. Its expected loss is bounded by $E[L(T)] \le \exp(-T/(4H_\epsilon)+2K\log(\log(T)+1))$, and the algorithm is $\epsilon$-LDP. Algorithm 2 (fixed confidence) shrinks a confidence radius around each privatized empirical mean and stops when no arm's interval straddles $\tau_\epsilon$; with probability at least $1-\delta$ it returns the true set using at most $O(H_\epsilon \log(4KH_\epsilon/\delta))$ pulls, and it is $\epsilon$-LDP. The lower bounds hold for any $\epsilon$-differentially private mechanism, not just the Bernoulli mechanism, and their dependence on $H_\epsilon$ matches the upper bounds up to constants and logarithmic factors when $\epsilon$ is small.

Load-bearing premise

The fixed-confidence guarantee rests on the claim that the chosen Hoeffding radius makes the per-round error probability at most $\delta/(2Kt^3)$, a bound stronger than what Hoeffding's inequality actually yields, and the guarantee collapses if that claim does not hold.

Editorial extensions

If this is right

  • In the high-privacy limit $\epsilon\to 0$, the cost of local differential privacy in thresholding bandits is only additive log-log terms in the budget and logarithmic factors in the sample complexity, not a change of the problem's exponential form.
  • The Bernoulli mechanism is minimax near-optimal among all $\epsilon$-LDP mechanisms for small $\epsilon$, so no more sophisticated privatization scheme can dramatically improve the fixed-budget or fixed-confidence guarantees.
  • Existing non-private thresholding algorithms can be made private by rescaling means, thresholds, and tolerances through the PrivBern map, without altering the arm-selection rules.
  • For small $\epsilon$, the complexity term grows roughly as $\epsilon^{-2}$ relative to the non-private $H$, making the privacy cost in extra pulls explicit and quantifiable.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same rescaling argument should extend to other pure-exploration problems under local differential privacy, such as best-arm identification, whenever the non-private algorithm is built from empirical means and confidence intervals; the main work would be verifying that $H_\epsilon$ remains the right difficulty measure.
  • The paper's near-optimality claim is restricted to small $\epsilon$; deriving instance-dependent lower bounds for moderate or large $\epsilon$ would characterize how quickly the gap between the upper and lower bounds grows as privacy weakens.
  • Because the Bernoulli mechanism is a form of randomized response, practitioners could reuse existing non-private implementations and only swap in the privatized reward stream and the rescaled threshold, suggesting a low-friction path to privacy in deployed bandit systems.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies thresholding bandits under local differential privacy (LDP). It proposes two algorithms built on the Bernoulli privatization mechanism: Algorithm 1 for the fixed-budget setting and Algorithm 2 for the fixed-confidence setting. The paper claims an exponential bound on expected misclassification loss for Algorithm 1, an O(H_epsilon log(KH_epsilon/delta)) sample-complexity bound for Algorithm 2, epsilon-LDP guarantees for both, and instance-dependent lower bounds for both settings that match the upper bounds up to poly-logarithmic factors in the high-privacy regime. The fixed-budget upper bound closely follows the non-private analysis of Locatelli et al., rescaled to the privatized mean mu_{i,epsilon}; the fixed-confidence analysis follows the stopping-rule template of Chen et al.

Significance. If the results are correct, the paper provides a useful first characterization of LDP thresholding bandits, a natural pure-exploration setting that has not been studied under local privacy. The use of the Bernoulli mechanism is simple and directly gives epsilon-LDP guarantees, and the claimed matching with the lower bounds in the small-epsilon regime is a meaningful contribution. The paper also ships relatively complete proofs in the appendices, which makes the technical gaps easy to audit. However, one central upper bound is not established as written, and one lower-bound proof contains a reversed inequality; both issues are local and likely repairable, but they currently block the paper's main claims.

major comments (3)
  1. [§4.1 / Appendix D] The confidence radius in Algorithm 2 is too small for the claimed Hoeffding guarantee. The algorithm sets rad_t(i)=sqrt(log(4Kt^3/delta)/(8T_i(t))), and the proof of the high-probability event A_t implicitly treats this radius as satisfying P(|hat mu_i^t - mu_{i,epsilon}| >= rad_t(i)) <= delta/(2Kt^3). For Bernoulli rewards with variance proxy 1/4, Hoeffding gives 2 exp(-2 T_i(t) rad_t(i)^2) = 2(delta/(4Kt^3))^{1/4}, which is not summable over t. Consequently the event A = cap_t A_t is not shown to have probability at least 1-delta, and the stopping rule S_t = tilde S_t is not certified to return the correct set with the claimed confidence. The proof can likely be repaired by taking rad_t(i)=sqrt(log(4Kt^3/delta)/(2T_i(t))) up to constants, which preserves the O(H_epsilon log(KH_epsilon/delta)) sample complexity, but Theorem 4.1 is unproved as written.
  2. [Appendix C, Eq. (18) and Eq. (22)] The inequality KL(nu'_k, nu_k) <= 2 Delta_k^2 is reversed. The exact expression is Delta_k log((1+Delta_k)/(1-Delta_k)) = 2 Delta_k^2 + O(Delta_k^4), which is at least 2 Delta_k^2 for Delta_k > 0. Since Eq. (22) replaces KL_j by the smaller quantity 2 Delta_j^2 inside the exponent of a lower bound, the displayed lower bound is not supported: the exponent in the true expression is larger, so the claimed probability bound may be too optimistic. The proof needs a valid upper bound on the relevant KL term, or a different argument for selecting the arm i, before Theorem 3.2 is established.
  3. [§3.2, Theorem 3.2 vs Appendix C Eq. (23)] The exponent stated in Theorem 3.2 differs from the exponent derived in the proof by a factor of 2. Substituting H = ((e^epsilon-1)^2/(e^epsilon+1)^2) H_epsilon into Eq. (23) yields exp(-16 T min{4,e^{2epsilon}}(e^epsilon+1)^2/H_epsilon), while Theorem 3.2 states exp(-8 T min{4,e^{2epsilon}}(e^epsilon+1)^2/H_epsilon). As written, the theorem claims a stronger bound than the proof establishes. In addition, the proof begins by fixing tau=1/2 and zeta=0 while the theorem claims arbitrary tau in [0,1] and zeta >= 0; the sentence that the construction generalizes easily is not a substitute for a proof. These issues are constant-factor matters for the paper's near-optimality claim, but they need to be reconciled.
minor comments (4)
  1. [§4.2 / Appendix E] In Appendix E, the quantity Delta_i is used in the KL bound but not explicitly defined in terms of the original environment Q before clipping; please define Delta_i and state how clipping affects the KL divergence.
  2. [Algorithm 2 / Appendix D] The notation T is used for both the fixed budget and the random stopping time; in Theorem 4.1 and its proof, T on the left-hand side of the display is a random variable, which should be stated explicitly.
  3. [Theorem 4.2] The statement says K >= 0, but the thresholding bandit problem requires at least one arm; the assumption should be K >= 1.
  4. [§3.1] In the proof of Theorem 3.1, the event Lambda bounds deviations using T in the radius; the presentation would be clearer if the dependence of the constants on the sub-Gaussian parameter were stated explicitly, since the displayed exponent 8T delta^2/H_epsilon appears to rely on a specific sub-Gaussian constant.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation is self-contained and the bounds are not defined in terms of the conclusions.

full rationale

The paper's central claims are upper and lower bounds for LDP thresholding bandits. The fixed-budget upper bound (Theorem 3.1) is proved from a sub-Gaussian concentration event on the privatized rewards and the algorithm's allocation rule; the complexity H_epsilon is defined directly from the rescaled means and threshold (Eqs. 4-8), not from the target loss bound. The fixed-confidence upper bound (Theorem 4.1) is proved by union-bounding a concentration event A_t and showing that under A_t the stopping rule St = tildeSt implies St = S*; the stopping rule is not defined as 'the algorithm is correct', so there is no self-definitional collapse. The lower bounds (Theorems 3.2 and 4.2) use external KL-decomposition lemmas (Basu et al., 2019; Kaufmann et al., 2016) and the Bretagnolle-Huber inequality; none of these are self-citations by the present authors, and no parameter is fitted to force the stated bound. The Bernoulli mechanism is imported from Ren et al. (2020), again external. No cited 'uniqueness' result is invoked to forbid alternatives. There are, however, correctness concerns outside circularity: in Appendix D, the Hoeffding tail bound as written does not give P(|hat mu - mu| >= rad_t(i)) <= delta/(2Kt^3) for rad_t(i)=sqrt(log(4Kt^3/delta)/(8T_i(t))); and in Appendix C, the claimed KL bound KL(nu'_k, nu_k) <= 2 Delta_k^2 is reversed for the stated Bernoulli means. Neither defect makes a conclusion an input to its own derivation, so the circularity score remains 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data; the problem variables µ, τ, ζ, ε are inputs, and the proof constants (δ=(4√2)^-1, C=499) are analytical choices. The analysis rests on external concentration, privacy, and LDP-KL lemmas. No invented entities are introduced.

assumptions (5)
  • standard math The Bernoulli mechanism PrivBern(ε) is ε-DP and maps reward mean µ to µε = 1/2 + (2µ-1)(eε-1)/(2(eε+1)), as given in Ren et al. Lemma 5.
    Used as the privacy primitive in Definitions 2.1 and equations (4)-(5); taken from prior work without proof.
  • domain assumption The KL decomposition for ε-LDP bandit algorithms bounds the information ratio by 2 min{4,e^{2ε}} (eε-1)^2 times the cumulative expected pulls, as stated in Basu et al. 2019 Lemma 4.
    Load-bearing for both lower bounds (Theorems 3.2 and 4.2); imported as a black box with no verification of its constants.
  • standard math Hoeffding and sub-Gaussian concentration inequalities for Bernoulli rewards, with variance proxy 1/4, and the Bretagnolle-Huber inequality.
    Used in the event-based proofs in Appendices B and D; the Hoeffding usage in Appendix D is misapplied in the paper.
  • domain assumption Rewards are bounded in [0,1] and i.i.d. across pulls with fixed means; arms are independent.
    Standard stochastic bandit model stated in Section 2.2; all proofs rely on this.
  • domain assumption The non-private thresholding bandit algorithms (Locatelli et al. 2016 for fixed budget, Chen et al. 2014 for fixed confidence) are correct, and their proof structure can be inherited after the threshold rescaling.
    The upper bound proofs are adaptations of these algorithms; correctness of the private versions depends on this inheritance.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Locally Differentially Private Thresholding Bandits." pith.science (2026). https://pith.science/paper/JMRBUREZ

@misc{pith2026250723073,
  author       = {Pith},
  title        = {Pith review of: Locally Differentially Private Thresholding Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JMRBUREZ}},
  note         = {Machine review of arXiv:2507.23073}
}
read the original abstract

This work investigates the impact of ensuring local differential privacy in the thresholding bandit problem. We consider both the fixed budget and fixed confidence settings. We propose methods that utilize private responses, obtained through a Bernoulli-based differentially private mechanism, to identify arms with expected rewards exceeding a predefined threshold. We show that this procedure provides strong privacy guarantees and derive theoretical performance bounds on the proposed algorithms. Additionally, we present general lower bounds that characterize the additional loss incurred by any differentially private mechanism, and show that the presented algorithms match these lower bounds up to poly-logarithmic factors. Our results provide valuable insights into privacy-preserving decision-making frameworks in bandit problems.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 18 canonical work pages

  1. [1]

    Audibert, S

    J.-Y. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi-armed bandits. pages 41--53, 11 2010

    work page 2010

  2. [2]

    Azize and D

    A. Azize and D. Basu. When privacy meets partial information: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35: 0 32199--32210, 2022

    2022

  3. [3]

    Azize, M

    A. Azize, M. Jourdan, A. A. Marjani, and D. Basu. Differentially private best-arm identification. arXiv preprint:2406.06408, 2024

    arXiv 2024

  4. [4]

    D. Basu, C. Dimitrakakis, and A. Y. Tossou. Privacy in multi-armed bandits: Fundamental definitions and lower bounds. arXiv prerint:1905.12298, 2019

    arXiv 1905

  5. [5]

    D. A. Berry and B. Fristedt. In Bandit problems: Sequential Allocation of Experiments, 1984

    work page 1984

  6. [6]

    S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen. Combinatorial pure exploration of multi-armed bandits. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014

    work page 2014

  7. [7]

    Cheshire, P

    J. Cheshire, P. Menard, and A. Carpentier. The influence of shape constraints on the thresholding bandit problem. In J. Abernethy and S. Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1228--1275. PMLR, 09--12 Jul 2020

    work page 2020

  8. [8]

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th annual symposium on foundations of computer science, pages 429--438. IEEE, 2013

    work page 2013

Show all 23 references
  1. [9]

    Dwork and A

    C. Dwork and A. Roth. The Algorithmic Foundations of Differential Privacy. Foundations and trends in theoretical computer science. 2014. ISBN 9781601988188

    2014

  2. [10]

    Gajane, T

    P. Gajane, T. Urvoy, and E. Kaufmann. Corrupt bandits for preserving local privacy. In F. Janoos, M. Mohri, and K. Sridharan, editors, Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pages 387--412. PMLR, 07--09 Apr 2018

    2018

  3. [11]

    Garivier, P

    A. Garivier, P. M \'e nard, L. Rossi, and P. Menard. Thresholding bandit for dose-ranging: The impact of monotonicity. arXiv preprint:1711.04454, 2017

    2017 arXiv

  4. [12]

    Y. Han, Z. Liang, Y. Wang, and J. Zhang. Generalized linear bandits with local differential privacy. Advances in Neural Information Processing Systems, 34: 0 26511--26522, 2021

    2021

  5. [13]

    T. Jin, K. Huang, J. Tang, and X. Xiao. Optimal streaming algorithms for multi-armed bandits. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5045--5054. PMLR...

    2021

  6. [14]

    Kairouz, S

    P. Kairouz, S. Oh, and P. Viswanath. Extremal mechanisms for local differential privacy. Journal of Machine Learning Research, 17 0 (17): 0 1--51, 2016

    2016

  7. [15]

    S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? SIAM Journal on Computing, 40 0 (3): 0 793--826, 2011

    2011

  8. [16]

    Kaufmann, O

    E. Kaufmann, O. Capp \'e , and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17 0 (1): 0 1--42, 2016

    2016

  9. [17]

    Locatelli, M

    A. Locatelli, M. Gutzeit, and A. Carpentier. An optimal algorithm for the thresholding bandit problem. In M. F. Balcan and K. Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pa...

    2016

  10. [18]

    Pavlovic, S

    N. Pavlovic, S. Salgia, and Q. Zhao. Differentially private kernelized contextual bandits. In The 28th International Conference on Artificial Intelligence and Statistics, 2025

    2025

  11. [19]

    W. Ren, X. Zhou, J. Liu, and N. B. Shroff. Multi-armed bandits with local differential privacy. CoRR, abs/2007.03121, 2020

    2007 arXiv

  12. [20]

    Shariff and O

    R. Shariff and O. Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018

    2018

  13. [21]

    Thuot , A

    V. Thuot , A. Carpentier , C. Giraud , and N. Verzelen . Active clustering with bandit feedback . arXiv e-prints, 2024

    2024

  14. [22]

    S. S. Villar, J. Bowden, and J. Wason. Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges . Statistical Science, 30 0 (2): 0 199 -- 215, 2015

    2015

  15. [23]

    M. Yang, T. Guo, T. Zhu, I. Tjuawinata, J. Zhao, and K.-Y. Lam. Local differential privacy and its applications: A comprehensive survey. Computer Standards & Interfaces, 89: 0 103827, 2024

    2024

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.