{"id":"7bf0a8f0-17e8-47f5-9ccb-0e91f0cdd82c","arxiv_id":"2502.02990","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Adaptive local privacy can estimate any quantile over a domain of size B with O(log B/(epsilon^2 alpha^2)) users, which is optimal and a log B factor better than nonadaptive protocols.","lead":"This paper gives faster private quantile estimation algorithms that adaptively query users one at a time, using only O(log B / (epsilon^2 alpha^2)) users under local differential privacy, and proves matching lower bounds. It also shows nonadaptive private algorithms must pay an extra log B factor, so adaptivity is provably more sample-efficient.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Adaptive LDP upper bound rests on an unproved adversarial-drift generalization of BayeSS; the median-case proof is sketched but not fully self-contained.","rationale":"The paper's headline contribution is the adaptive LDP sample complexity O(log B/(ε^2 α^2)) for quantile estimation. The proof of Theorem 1.1 reduces the median problem to AdvMonotonicNBS and invokes Theorem 3.2/E.2, which is a generalization of Gretta & Price's BayeSS to coin probabilities that drift by c·α per query. The full proof of this generalization is omitted, and the included median-case proof leans on Lemma E.3 plus unstated lemmas from the external paper. This is precisely the load-bearing point identified by the reader: if the adversarial-robustness lemma fails, the main upper bound collapses. I found no internal contradiction in the sketched argument; the martingale potential analysis and the median-case proof are plausible, and the reduction from drift to the randomized-response process is consistent. The lower bounds and the nonadaptive separation are less central and appear adequately supported, modulo the usual sketched parameter regimes. Given the reader's conditional-accept verdict, the appropriate disposition is unchanged: keep the conditional accept with a request to provide a complete, self-contained proof of Theorem E.2 or at least of Lemma E.3 with the imported Gretta & Price bounds stated and verified. The concrete re-derivation above would settle whether the concern actually lands, without requiring a change of the verdict at this stage.","tokens_in":34629,"tokens_out":29933,"duration_ms":355214,"concrete_test":"Independently re-derive Lemma E.3 from Gretta & Price's Lemma 7 with per-query adversarial drift. Specifically, verify the good-query case (the derivation of Equations 14–17 in Appendix E) and the imported inequalities α(log d10 − log d00) ≤ (6 log 2)·C_{τ,α} and the analogous bound for d01 − d11, under the stated assumptions c ≤ 1 and α ≤ (1/2)min{τ, 1 − τ}. If the expected potential increase is not at least (1 − 12γ)C_{τ,α}, Theorem 3.2 needs repair. A complementary computational check: run BayeSS on random monotone coin sequences with per-query biases adversarially perturbed by ±cα and verify it returns a (1/2, α(1+c))-good coin with high probability for α = 0.05, c = 1, B = 2^20.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, Theorem 1.1, depends on Theorem 3.2, which asserts that BayeSS remains correct when each queried coin's bias may drift by up to c·α. The general adversarial statement, Theorem E.2, is not proved: Appendix E says 'the proof is identical (see Lemma 6 and Theorem 1 of Gretta & Price), we omit it.' The provided proof of the median case (Theorem E.4) relies on Lemma E.3, whose 'good queries' analysis imports Lemma 9, 10, and 13 of Gretta & Price without stating them and uses bounds such as α(log d10 − log d00) ≤ (6 log 2)·C_{τ,α} to conclude an expected potential increase of at least (1 − 12γ)C_{τ,α}. If this adaptation to adversarial drift fails — for example, if the good-query potential drop is worse than −11C_{τ,α} or the bad-query drift bound is violated — then the O(log B/(ε^2 α^2)) upper bound for adaptive LDP median estimation has no support. This is a completeness and external-verification concern rather than a demonstrated internal contradiction: the median case is sketched and the argument is plausible. A secondary, non-fatal issue is the indexing slip at the end of the proof of Theorem 1.1, where the output should be j*, not j* + 1; the definitions of q_j and good coins make j* the α-approximate median.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed quantile estimation under local differential privacy (LDP) and shuffle differential privacy. It proposes a sequentially adaptive LDP protocol based on the BayeSS noisy binary search algorithm of Gretta and Price, and claims that any quantile can be estimated with error alpha using O(log B / (epsilon^2 alpha^2)) users, each sending one bit. It further claims a matching lower bound for adaptive LDP protocols, a lower bound for non-adaptive protocols showing a logarithmic-in-B separation, and a shuffle-DP protocol with r = log_2 B adaptive rounds. The technical core is a martingale argument controlling the drift of the empirical CDF under sampling without replacement (Lemma 3.1), an adversarial-drift generalization of BayeSS (Theorem 3.2), and reductions to existing lower bounds of Duchi et al. and Edmonds et al.","tokens_in":34815,"tokens_out":22117,"duration_ms":182736,"significance":"If the main theorems are correct, the paper resolves the sample complexity of sequentially adaptive LDP quantile estimation up to constant factors and establishes a separation between adaptive and non-adaptive local privacy. The paper has several strengths: the martingale argument in Lemma 4.1 is clean, the upper bounds use external results rather than self-citations, the lower-bound reduction from the empirical to the statistical setting is plausible, and the experimental code is released. However, the adversarial-drift generalization of BayeSS is not proved in a self-contained way, the shuffle-DP guarantee is defined per-round rather than for the joint transcript, and the extension of the Edmonds et al. lower bound to the parameter regime needed here is asserted rather than proved. These issues are load-bearing for the paper's central claims, so the manuscript needs substantial revision before the results can be accepted.","major_comments":[{"comment":"Theorem 3.2 underpins the proof of Theorem 1.1, but its proof via Theorem E.4 is not self-contained. Lemma E.3's good-query analysis imports Lemmas 9, 10, and 13 of Gretta and Price without stating them, and it uses the unstated estimate alpha(log_2 d_{1,0} - log_2 d_{0,0}) <= (6 log 2) C_{tau,alpha} to conclude that the expected potential drop on good queries is at least -11 C_{tau,alpha}. Theorem E.2, the advertised general adversarial-drift statement, is explicitly not proved: the text says 'the proof is identical (see Lemma 6 and Theorem 1 of (Gretta & Price, 2024)), we omit it.' Because the adversarial-drift analysis is the novel component on which the LDP upper bound depends, the authors should provide a complete proof of Theorem E.4 (or Theorem E.2), including statements of all imported lemmas and a verification that their constants remain valid when each queried coin's bias may drift by up to c alpha.","section":"Appendix E, Lemma E.3 and Theorem E.2"},{"comment":"The shuffle-DP definition in Definition 2.4 only requires each round's shuffled batch to be (epsilon, delta)-DP, not the joint transcript. In the proof of Theorem G.6, each of the r = log_2 B rounds is made (epsilon, delta)-DP via Lemma G.5, and no composition step is given; under standard composition the whole protocol is therefore only (r epsilon, r delta)-DP for a user whose data is used in one round and whose influence propagates through later adaptive mechanism choices. Either the theorem must be stated for the weaker per-round guarantee (which would not match the abstract's 'shuffle DP' claim), or the proof must split the privacy budget across rounds, which will change the stated sample complexity.","section":"Definition 2.4 and Appendix G, proof of Theorem G.6"},{"comment":"Theorem 1.3 uses a lower bound of Edmonds et al. (2020, Theorem 23) extended from Omega(log^2 B) to general epsilon and alpha. The paper only says 'it is relatively simple to check that their proof extends' and then restates the extension as Theorem F.4. Since this extension is load-bearing for the non-adaptive lower bound and for the claimed separation result, the derivation should either be included in the appendix or the precise conditions on epsilon, alpha, and B under which the extension holds should be proved.","section":"Section 3.2, footnote 5, and Theorem F.4"}],"minor_comments":[{"comment":"The last sentence of the proof says 'j* + 1 is an alpha-approximate median', but the displayed inequalities q^0_{j*} <= 1/2 + alpha and q^0_{j*+1} >= 1/2 - alpha make j* the alpha-approximate median; the output index should be j*, not j* + 1.","section":"Section 4, proof of Theorem 1.1"},{"comment":"The proof writes Y_t = |{t < i <= 2n : c_i = 0}|, but there are only n users; this should be t < i <= n. Also, applying Lemma 4.1 to n bits gives a tail bound of 2 exp(-alpha^2 n / 4), not 2 exp(-alpha^2 n / 2); the discrepancy is absorbed by the constant C, but the proof should be corrected.","section":"Lemma 3.1, proof"},{"comment":"The condition on epsilon is typeset ambiguously: if it is intended as epsilon <= (1/64) sqrt(log B), the proof's requirement epsilon^2 <= log B / 4096 is satisfied, but if it is intended as epsilon <= 1/(64 sqrt(log B)), the condition is much stronger and does not match the proof. Please clarify the typesetting.","section":"Theorem F.2"},{"comment":"There are several typos that should be corrected, including 'Denote the the private mechanism' in Section 2, 'randomized responze' in Appendix C, 'cocnluding' in the proof of Lemma E.3, and 'succes rate' in Section 5.","section":"Throughout"},{"comment":"The hyperparameter c = 0.6 is selected empirically on the same experimental setup used in the main experiments; Section 5 should state clearly that the reported DpBayeSS success rates use this tuned constant, which is separate from the universal constant c in Theorem 1.1.","section":"Appendix I.1"}],"recommendation":"major_revision","confidential_remarks":"The main LDP theorem is plausible and the martingale argument is a solid contribution, but the manuscript currently has an unproved adversarial-drift theorem, a non-self-contained proof of the version that is actually used, and a shuffle-DP definition that is weaker than the standard joint-transcript guarantee advertised in the abstract. These are fixable with a substantial revision, but they are not purely presentational. I would not reject the paper, but I would not accept it in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the main result is real and the proof is mostly in hand; the one piece that is not fully in hand is the adversarial robustness of the BayeSS search, and that is a completeness problem, not a fatal one.\n\nThe genuinely new things: the without-replacement drift lemma (Lemma 3.1) is a clean martingale argument bounding how much the empirical CDF of the remaining users can move; the adaptation of BayeSS to adversarial drift is the technical core; and the nonadaptive lower bound separation (Theorem 1.3) is the conceptual headline. The statistical warmup is folklore, as they say. The adaptive lower bound via Duchi et al. plus the statistical-to-empirical reduction is plausible, and the shuffle protocol is a nice demonstration of the trade-off between rounds and amplification.\n\nThe weak spots, in proportion. (1) The general adversarial BayeSS theorem (Theorem E.2) is stated, then waved at with \"identical to Gretta & Price.\" The median case (Theorem E.4) is proved, and that is what Theorem 1.1 needs, but the proof of Lemma E.3 imports three lemmas from Gretta & Price without stating them, so a referee cannot check it without the other paper open. I would ask the authors to either reproduce the full argument or state the imported lemmas and their exact conditions. (2) At the end of the proof of Theorem 1.1, they say j*+1 is the approximate median; the inequalities they just derived show j* is. The output should be j*. Minor but worth fixing. (3) The experiments tune the constant c in the update rule on the same kind of data used for reporting (Section I.1); the theory doesn't use this constant, so it only weakens the empirical claim, not the theory. (4) The shuffle proof has a parameter-regime patch in Theorem G.6 that is rough but the final bound is believable.\n\nBottom line: this is a carefully written theory paper, the main theorems are significant, and the gaps are omissions rather than contradictions. It deserves a serious referee. I'd suggest a conditional accept: require the authors to provide the full adversarial BayeSS proof or explicitly scope Theorem E.2 to the median case with the imported lemmas stated, and to fix the j* slip. The nonadaptive lower bound's parameter regime should also be spelled out more carefully.\n\nFor the reading group: bring it up; the without-replacement martingale argument and the adaptive/nonadaptive separation are worth discussing.","headline":"Clean adaptive LDP quantile result with a solid main proof and one completeness gap in the adversarial BayeSS extension; worth refereeing but needs a fuller Appendix E.","tokens_in":35431,"tokens_out":2976,"would_cite":true,"duration_ms":63189,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive local differential privacy settles the sample complexity of private quantile estimation at $\\Theta(\\log B/(\\varepsilon^2\\alpha^2))$ users, each sending one bit.","keywords":["local differential privacy","quantile estimation","noisy binary search","adaptive protocols","shuffle differential privacy","sample complexity","randomized response","median estimation"],"falsifier":"Implement $\\mathrm{AdvMonotonicNBS}$ with $B=10^6$ coins, $\\alpha=0.01$, $c=1$, and $\\tau=1/2$, and run the Bayesian Screening Search for $T = C\\log B/\\alpha^2$ flips with an adversary that sets each realized bias to $p_j + c\\alpha$ when $j$ is right of the true $\\tau$-coin and to $p_j - c\\alpha$ when left; if over 1000 independent runs the fraction of outputs that are $(1/2, 2\\alpha)$-good drops well below 0.99, Theorem 3.2 would be refuted. A direct analytical falsifier would be an explicit drift schedule making the expected potential gain on a good query drop below $(1-12\\gamma)C_{\\tau,\\alpha}$, which would break Lemma E.3 and hence the main theorem.","tokens_in":34341,"feed_emoji":"🔒","tokens_out":13234,"duration_ms":109383,"temperature":0.7,"pith_summary":"This paper claims that a server can estimate any quantile of a distributed dataset with only $O(\\log B/(\\varepsilon^2 \\alpha^2))$ users, each sending one bit, provided the server is allowed to choose queries adaptively and each user answers under local differential privacy with budget $\\varepsilon$. The protocol achieves this by converting median estimation into a noisy binary search over the empirical cumulative distribution, then proving that the search routine still succeeds when the coins' biases drift because users are sampled without replacement. A matching lower bound shows no adaptive protocol can use asymptotically fewer users in the high-privacy regime, so the result is optimal. The same machinery yields a shuffle-differential-privacy protocol using $O((1/\\alpha^2 + 1/\\varepsilon^2)\\log B \\sqrt{\\log(1/\\delta)\\log\\log B/\\beta})$ users with $\\log_2 B$ rounds. A separate lower bound shows non-adaptive protocols must pay an extra $\\log B$ factor, establishing that adaptivity is what buys the improvement.","feed_headline":"One bit per user finds any quantile at optimal privacy cost","feed_subtitle":"Adaptive queries let each user answer once; non-adaptive protocols must spend a whole log B factor more.","key_machinery":"The central object is the adversarial noisy binary search problem $\\mathrm{AdvMonotonicNBS}$: an ordered list of $B$ coins has unknown monotone head probabilities $p_1 \\leq \\cdots \\leq p_B$, and each time the algorithm queries coin $j$ an adversary may replace the realized bias by any $p$ with $|p-p_j| \\leq c\\alpha$; the goal is to return a coin whose interval $[p_i, p_{i+1}]$ intersects $[\\tau-\\alpha(1+c), \\tau+\\alpha(1+c)]$. The paper proves (Theorem 3.2) that the Bayesian Screening Search algorithm solves this with $O(\\log B/\\alpha^2)$ coin flips and high probability. The proof machinery is a potential function $\\Phi$ over the Bayesian posterior: on a 'bad' query the potential gains at least $(1-12\\gamma)C_{\\tau,\\alpha}$ in expectation, while on a 'good' query it loses at most $11C_{\\tau,\\alpha}$, and Azuma's inequality then shows the potential crosses zero only with probability $B^{-\\lambda}$. The companion Lemma 3.1, proved by a martingale difference argument, bounds the drift of the remaining-users CDF by $\\alpha$ over the first $n/2$ steps, which is exactly the adversarial condition the search needs.","core_discovery":"The central claim is Theorem 1.1: for every $\\alpha \\in (0,1/4)$ and $\\varepsilon \\in (0,1)$, there exists a sequentially adaptive $\\varepsilon$-LDP protocol that, with probability at least $1-1/B$, returns an $\\alpha$-approximate empirical median of any $n$-user dataset over $[B]$ as long as $n \\geq c\\log B/(\\varepsilon^2\\alpha^2)$. Each user is queried once and responds with a single randomized-response bit; the server runs a noisy binary search in which the queried coin is the threshold $[x \\leq j]$ after clamping to $\\{0,1\\}$ and flipping with probability $1/(1+e^\\varepsilon)$. The paper's key move is to run this search over users in a random order and to treat the changing empirical CDF as an adversary that may shift each coin's bias by at most $c\\alpha$; Theorem 3.2 shows the Bayesian Screening Search still returns a good coin in $O(\\log B/\\alpha^2)$ flips under such drift. Combined with the lower bound of Theorem 1.2, the sample complexity $\\Theta(\\log B/(\\varepsilon^2\\alpha^2))$ is optimal for adaptive protocols, and Theorem 1.3 proves non-adaptive protocols need a strictly larger poly-log factor in $B$.","pith_inferences":["If the drift-robustness of Theorem 3.2 holds generally, analogous adaptations could improve adaptive LDP algorithms for other sequential estimation problems where sampling without replacement shifts the target, such as repeated range queries or adaptive CDF approximation.","The $\\log B$ separation between adaptive and non-adaptive protocols likely reflects a general principle: non-interactive local privacy forces each user's message to be usable for all possible queries, while adaptivity lets the server concentrate privacy budget on relevant thresholds; this intuition may transfer to private selection and learning problems.","A systematic sweep of $n$ below the constant $c\\log B/(\\varepsilon^2\\alpha^2)$ threshold would calibrate the universal constant for deployment and reveal whether the success probability degrades gracefully or sharply.","The shuffle protocol's analysis requires $n = \\Omega(\\log(1/\\delta)/\\varepsilon^2)$ for amplification; if shuffling could amplify with smaller batches, the $1/\\alpha^2+1/\\varepsilon^2$ trade-off would improve to a $1/(\\alpha\\varepsilon)$ dependence, which the paper identifies as an open direction."],"forward_implications":["Adaptive local differential privacy solves quantile estimation with $\\Theta(\\log B/(\\varepsilon^2\\alpha^2))$ users, matching the information-theoretic lower bound up to constants in the high-privacy regime $\\varepsilon<1$.","Non-adaptive LDP protocols provably need at least $\\Omega(\\log^2 B/(\\alpha^2\\varepsilon^2\\log^4(1/\\alpha)))$ users in the stated regime, so adaptation buys a factor of $\\log B$ in sample complexity.","The padding reduction shows the median is the hardest quantile: any quantile $q \\in (2\\alpha, 1-2\\alpha)$ inherits the upper and lower bounds up to constants.","Shuffle differential privacy can keep most of the benefit: with $r=\\log_2 B$ shuffled rounds, $n = O((1/\\alpha^2+1/\\varepsilon^2)\\log B \\sqrt{\\log(1/\\delta)\\log\\log B/\\beta})$ users suffice.","Communication stays at one bit per user and $O(\\log B)$ server-side update time per round, which is why the protocol is described as lightweight."],"supporting_citations":[{"why":"Supplies the Bayesian Screening Search algorithm for monotone noisy binary search whose potential-function analysis is adapted to drifting coin biases in Theorem 3.2.","marker":"(Gretta & Price, 2024)"},{"why":"Introduces noisy binary search and its $\\Theta(\\log B/\\alpha^2)$ query complexity, the benchmark the statistical reduction and the shuffle-DP binary search build on.","marker":"(Karp & Kleinberg, 2007)"},{"why":"Provides the mutual-information bound for $\\varepsilon$-LDP protocols used to prove the adaptive lower bound of Theorem 1.2.","marker":"(Duchi et al., 2013)"},{"why":"Establishes the non-interactive LDP lower bound for CDF learning with $\\ell_\\infty$ error, to which the non-adaptive quantile lower bound of Theorem 1.3 reduces.","marker":"(Edmonds et al., 2020)"},{"why":"Gives the privacy amplification by shuffling analysis used to make the batched binary search satisfy $(\\varepsilon,\\delta)$-shuffle DP in Theorem 1.4.","marker":"(Feldman et al., 2021)"},{"why":"Defines randomized response, the one-bit $\\varepsilon$-LDP mechanism that realizes each coin flip in the adaptive protocol.","marker":"(Warner, 1965)"}],"fun_headline_variants":["Adaptive one-bit protocol hits optimal private quantile bound","Non-adaptive private quantiles need extra log factor, proofs show","Single random bit per user yields optimal adaptive private median","Adaptive private quantile estimation beats non-adaptive sample count","Optimal private quantile via adaptive single-bit responses"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the noisy binary search routine still finds a $\\tau$-good coin in $O(\\log B/\\alpha^2)$ queries even when an adversary may shift every coin's bias by up to $c\\alpha$ at each query; the paper's proof adapts a previously known potential-function argument and omits the full general proof, so this drift-robustness is the point where the main upper bound would fail if the adaptation is wrong.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive one-bit protocol hits optimal private quantile bound","Non-adaptive private quantiles need extra log factor, proofs show","Single random bit per user yields optimal adaptive private median","Adaptive private quantile estimation beats non-adaptive sample count","Optimal private quantile via adaptive single-bit responses"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000769,"raw_usage":{"total_tokens":3462,"prompt_tokens":1055,"completion_tokens":2407,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":671,"completion_tokens_details":{"reasoning_tokens":2325}},"tokens_in":671,"tokens_out":2407,"duration_ms":17558,"temperature":1.0,"reasoning_tokens":2325,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T10:18:35.999716+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement $\\mathrm{AdvMonotonicNBS}$ with $B=10^6$ coins, $\\alpha=0.01$, $c=1$, and $\\tau=1/2$, and run the Bayesian Screening Search for $T = C\\log B/\\alpha^2$ flips with an adversary that sets each realized bias to $p_j + c\\alpha$ when $j$ is right of the true $\\tau$-coin and to $p_j - c\\alpha$ when left; if over 1000 independent runs the fraction of outputs that are $(1/2, 2\\alpha)$-good drops well below 0.99, Theorem 3.2 would be refuted. A direct analytical falsifier would be an explicit drift schedule making the expected potential gain on a good query drop below $(1-12\\gamma)C_{\\tau,\\alpha}$, which would break Lemma E.3 and hence the main theorem.","supporting_citations":[{"cited_title":"and Price, E","cited_arxiv_id":null,"evidence_quote":"Supplies the Bayesian Screening Search algorithm for monotone noisy binary search whose potential-function analysis is adapted to drifting coin biases in Theorem 3.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces noisy binary search and its $\\Theta(\\log B/\\alpha^2)$ query complexity, the benchmark the statistical reduction and the shuffle-DP binary search build on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines randomized response, the one-bit $\\varepsilon$-LDP mechanism that realizes each coin flip in the adaptive protocol."}],"review_version":1}