{"id":"b8edb24a-bf0a-4c50-9838-151b9a75388e","arxiv_id":"1908.11358","paper_version":4,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Single-message shuffled-model frequency estimation has optimal error about min(n^{1/4}, sqrt(B)); multi-message protocols achieve polylogarithmic error with polylogarithmic communication.","lead":"Shuffled-model differential privacy behaves very differently for one message per user versus many. This paper proves nearly tight error bounds in the single-message case and gives multi-message protocols that are exponentially more accurate, establishing the first separation between the two settings.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the single-message lower bound is intricate but internally coherent, and the multi-message constructions check out.","rationale":"The reader correctly identified Lemma 3.15 and the surrounding anti-concentration argument as the most delicate part of the proof. I agree that this is where a hidden assumption would be most damaging: if accuracy did not force the per-user distributions P_v and Q to be nearly disjoint, the mutual-information bound in Lemma 3.14 would fail, and with it the intermediate-sample lower bound (7) and hence Theorem 1.1. However, on full inspection the lemma is supported by a coherent argument: the reduction from arbitrary ranges to the binary case is done via two applications of the data processing inequality; the binomial anti-concentration step invokes a published bound of Roos with the correct parameter regime; and condition (38) is precisely what is needed to make the Chernoff probabilities small. The constants in the displayed equations are internally consistent (the apparent '12B' in (56) is a typographical slip for 3B, given the definition of λ and the claim that follows). The multi-message side also appears sound: the Hadamard-response protocol's privacy proof uses a multinomial coupling with a Chernoff bound, and the Count-Min protocol's privacy proof reduces to smoothness of the binomial distribution via the k-incremental sensitivity lemma. I therefore find no load-bearing objection, and the reader's ACCEPT verdict stands. My partial rather than full agreement is because the reader framed Lemma 3.15 as a live risk, whereas I view it as delicate but ultimately sound; the proposed concrete test is still worth running as a cheap verification of the pivotal sub-step.","tokens_in":69602,"tokens_out":17492,"duration_ms":177829,"concrete_test":"Independently verify Lemma 3.20 by computing, for a binary randomizer with overlap ρ0, whether the claimed implication Δ(histogram mixtures) ≥ c implies ρ0 ≤ O(γ²n), using Roos's binomial TV bound with the stated constants. This is the pivotal sub-step of Lemma 3.15, and a clean re-derivation or small numerical check for n ∈ {8, 16, 32} and γ ∈ {0.1, 0.2, 0.3} would settle the only delicate point in the lower-bound chain.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claim rests on the single-message lower bound (Theorem 3.1), which is built from the local-model reduction (Lemma 3.5), the mutual-information bound (Lemma 3.14), and the anti-concentration lemma (Lemma 3.15). I checked the dependency chain: Lemma 3.15's condition (38) is satisfied in the intended parameter regime, the DPI reduction to the three-point case is legitimate, and the binomial comparison uses Roos's bound in a standard way. The multi-message protocols are supported by their own self-contained privacy proofs (Lemmas 4.4 and 4.10) and accuracy analyses. No internal inconsistency or missing proof that would overthrow the separation result was found.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies frequency estimation and selection in the shuffled model of differential privacy. For single-message protocols it proves a nearly tight lower bound on the error of frequency estimation, namely \\tilde{\\Omega}(\\min(n^{1/4},\\sqrt{B})) up to polylogarithmic factors, together with a nearly tight \\Omega(B) lower bound on the number of users required for selection. It then constructs multi-message protocols for frequency estimation with polylogarithmic error and polylogarithmic per-user communication, in both private-coin and public-coin settings, and applies them to heavy hitters, range counting, median/quantile estimation, and simulation of sparse non-adaptive statistical query algorithms. The combination of these results gives the first separations between single-message and multi-message protocols in the shuffled model for frequency estimation and for selection.","tokens_in":69723,"tokens_out":8024,"duration_ms":79681,"significance":"If the results hold, they essentially settle the single-message frequency-estimation error up to polylog factors and provide a clean separation between single-message and multi-message shuffled-model protocols. The main contribution is the lower-bound technology: a low-privacy, approximate-DP local-model bound built on a structural total-variation lemma for accurate randomizers (Lemma 3.15) and a mutual-information analysis (Lemma 3.14), plus the multi-message constructions based on Hadamard response and a differentially private Count-Min sketch. The proofs are detailed and structured, with supporting lemmas and appendices; I found no circular parameter fitting or post-hoc exclusion of cases. The dependency chain from Lemma 3.5 through Lemma 3.14 and Lemma 3.15 to Theorem 3.1 is coherent, and the anti-concentration argument in Lemma 3.15 is nontrivial and potentially of independent interest. The matching upper and lower bounds in each parameter regime give additional confidence in the central claim.","major_comments":[],"minor_comments":[{"comment":"In the proof of Lemma 3.8, the sentence stating that the distribution of R(V) is P_v is confusing: P_v was defined as the conditional distribution of R(v), whereas the marginal distribution of R(V) is the mixture P-bar = (1/B) \\sum_{v} P_v. Please correct this notation.","section":"Section 3.2, proof of Lemma 3.8"},{"comment":"There are a few typographical slips in the informal discussion, for example \\alpha! 1/\\sqrt{n} should presumably be \\alpha \\ll 1/\\sqrt{n}, and a later expression appears to contain a garbled operator. These do not affect the formal statements but should be cleaned up.","section":"Section 1.2 / Remark 3.4"},{"comment":"In the row for communication per user, the entry \"any\" in the single-message lower-bound column is ambiguous. Consider clarifying that the lower bound holds regardless of the message length or total communication.","section":"Table 1"},{"comment":"Lemma 4.4 states privacy parameters (k\\varepsilon, \\delta \\exp(k\\varepsilon)/\\varepsilon) while Theorem 4.3 states (\\varepsilon,\\delta). The rescaling of \\varepsilon and \\delta that converts the lemma into the theorem is not made explicit in the text; please spell it out for readability.","section":"Theorem 4.3 / Lemma 4.4"}],"recommendation":"minor_revision","confidential_remarks":"This is a strong paper with a substantial technical contribution, and the novelty and citation practices appear appropriate. My main editorial note is that the paper is long and some proofs are intricate; a proof-dependency diagram or a short table of notation would help future readers, but this is not a correctness concern. The lower-bound proof is the part most worth re-checking carefully, and I did not find a flaw in the dependency chain involving Lemma 3.15."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper settles the main open question it targets: the optimal error for private frequency estimation in the single-message shuffled model is Theta-tilde(min(n^{1/4}, sqrt(B))), and selection needs Theta(B) users. The multi-message protocols achieve polylog error and communication, giving the first separations for both problems. The lower-bound technique is genuinely new: a mutual-information bound that uses accuracy of the protocol in addition to privacy, plus a structural anti-concentration lemma (Lemma 3.15) that forces the local randomizer's output distributions to be far in total variation. That lemma is proved in the paper, and the dependency chain from it to the main theorems checks out. I read the proof of the intermediate-sample regime carefully; the reduction to the three-point distribution and the binomial comparison use standard tools correctly. The upper bounds combine known amplification results with RAPPOR and B-ary randomized response, and the multi-message constructions are self-contained.\n\nSoft spots are minor and mostly about presentation. The paper is long and the definitions are dense; the lower bound has several regimes that each need their own argument, so it is easy to get lost. The proofs are not machine-checked, and Lemma 3.15 is load-bearing, so a referee should verify that lemma's condition (38) in the regimes where it is applied – but it does hold in the intended parameter ranges. The multi-message protocols have polylogarithmic factors that could be optimized, but that is not a correctness issue. The citation pattern looks honest: prior work by Cheu et al., Erlingsson et al., Balle et al., Duchi et al., and Bassily-Smith is credited appropriately, and the improvement over the polynomial gaps in Cheu et al. is real.\n\nThis is a strong theory paper for anyone working on the shuffled model or on lower bounds for distributed DP. I would bring it to a reading group and cite it. It deserves a serious referee, not a desk rejection. My own verdict: accept after a careful check of Lemma 3.15 and the reduction in Lemma 3.5, both of which appear correct to me.","headline":"Near-tight single-message lower bounds and first single-vs-multi-message separations for frequency estimation and selection in the shuffled model; the proofs are long but internally coherent and worth serious referee time.","tokens_in":70210,"tokens_out":1035,"would_cite":true,"duration_ms":12298,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The optimal error for private frequency estimation in the single-message shuffled model is $\\widetilde{\\Theta}(\\min(n^{1/4}, \\sqrt{B}))$, and multi-message protocols achieve $\\widetilde{O}(1)$ error, giving the first separation between…","keywords":["differential privacy","shuffled model","frequency estimation","selection","single-message protocols","multi-message protocols","Hadamard response","privacy amplification"],"falsifier":"Run any candidate single-message shuffled protocol with $n=B^2$ users, constant $\\varepsilon$, and $\\delta=n^{-2}$, and measure the maximum frequency-estimation error; Theorem 1.1 predicts error $\\widetilde{\\Omega}(n^{1/4})$, so an error of $o(n^{1/4})$ refutes the characterization. For a more local test of Lemma 3.15, fix $v$, compare the distribution of $R(v)$ with $R(U)$ under the protocol's local randomizer, and check whether an accurate protocol can exist with total variation distance between these two distributions bounded away from 1.","tokens_in":69437,"feed_emoji":"🔀","tokens_out":11913,"duration_ms":101880,"temperature":0.7,"pith_summary":"This paper asks how much accuracy the shuffled model of differential privacy can buy when each user may send several anonymous messages instead of exactly one. For frequency estimation it establishes that the single-message optimum is $\\widetilde{\\Theta}(\\min(n^{1/4}, \\sqrt{B}))$ for constant privacy parameters, so no single-message protocol can escape polynomial error even with unbounded communication. It then constructs multi-message protocols with error $\\widetilde{O}(1)$ and $\\widetilde{O}(1)$ bits of communication per user, and a nearly tight $\\Omega(B)$ user lower bound for the related selection problem. Combined with known multi-message selection bounds, this yields the first separation between single-message and multi-message shuffled protocols. A sympathetic reader would care because the results mark exactly how much the anonymous channel can hide when each user speaks only once.","feed_headline":"More anonymous messages cut private frequency error to O~(1)","feed_subtitle":"Single-message shuffled DP is nearly optimal; multi-message protocols reach polylog error and communication.","key_machinery":"The load-bearing object for the single-message lower bound is a structural lemma (Lemma 3.15) stating that any accurate local randomizer must have total variation distance close to 1 between the distribution of its output on a fixed input $v$ and its output on a uniformly random input; the proof uses binomial anti-concentration and the data-processing inequality. This feeds a mutual-information bound for an $\\alpha$-accurate, $(\\varepsilon_L,\\delta_L)$-locally private randomizer of the form $I(V;R(X)) \\le \\widetilde{O}(\\gamma^2 \\alpha^2 n e^{\\varepsilon_L}(1+\\varepsilon_L) + \\gamma \\alpha^2 n + \\gamma^2)$, which Fano's inequality converts into the $\\widetilde{\\Omega}(n^{1/4})$ error bound. A reduction from the shuffled model to the local model lifts the local-model lower bound to the single-message shuffled model. On the multi-message side, the machinery is a multi-message Hadamard response, in which each user sends a logarithmic number of indices from its Hadamard codeword together with blanket noise, and a public-coin Count Min sketch with binomial noise that achieves polylogarithmic query time.","core_discovery":"The paper's central claim is a near-complete characterization: for $(\\varepsilon,\\delta)$-differentially private frequency estimation in the single-message shuffled model, the optimal error is $\\widetilde{\\Theta}(\\min(n^{1/4}, \\sqrt{B}))$, up to polylogarithmic factors. The lower bound is proved through a new local-model lower bound that works in the low-privacy regime $\\varepsilon_L \\approx \\ln n$ and with $\\delta_L>0$, going beyond the pure-privacy, small-$\\varepsilon_L$ techniques of previous work. The matching upper bound comes from applying privacy amplification by shuffling to RAPPOR and to $B$-ary randomized response. In the multi-message model the paper gives protocols with polylogarithmic error and communication for frequency estimation, and a lower bound of $\\Omega(B)$ users for selection in the single-message model, which together with an existing $\\tilde{O}(\\sqrt{B})$-user multi-message protocol gives the first separation between the two message regimes.","pith_inferences":["The structural total-variation lemma likely applies beyond frequency estimation: any single-message shuffled protocol for a family of counting queries whose local randomizer is accurate should force near-disjoint output distributions, which would extend the $n^{1/4}$-type barrier to distribution testing and clustering tasks that call a frequency oracle as a subroutine.","The nearly tight lower bound suggests a clean separation between what anonymity can hide with one message versus several: multi-message protocols effectively emulate a curator with polylog overhead, so further gains for single-message protocols would need to exploit correlations across users' messages rather than the structure of the local randomizer alone.","A natural testable extension is to check whether the same mutual-information machinery yields tight bounds for real-valued summation in the single-message shuffled model when the domain is continuous; the paper's techniques are stated for finite domains and would require new discretization arguments."],"forward_implications":["Single-message shuffled protocols for frequency estimation are near-optimal: the known amplification-by-shuffling upper bounds from RAPPOR and $B$-ary randomized response cannot be improved without leaving the single-message regime.","Multi-message protocols achieve exponentially smaller error than any single-message protocol, with polylogarithmic per-user communication, for frequency estimation and, by known reductions, for heavy hitters.","For selection, any single-message protocol needs $\\Omega(B)$ users, while a multi-message protocol uses only $\\tilde{O}(\\sqrt{B})$ users, giving the first separation for this problem.","The multi-message frequency oracle transfers to range counting, $M$-estimation of the median, quantiles, and simulation of sparse non-adaptive statistical query algorithms with improved sample and communication costs."],"supporting_citations":[{"why":"Supplies the reduction from shuffled-model privacy to local privacy with $\\varepsilon_L=\\varepsilon+\\ln n$, the earlier $\\Omega(B^{1/17})$ selection lower bound, and the $\\tilde{O}(\\sqrt{B})$-user multi-message selection protocol used for the separation.","marker":"[CSU`19]"},{"why":"Introduces the privacy-amplification-by-shuffling framework that yields the single-message upper bounds.","marker":"[EFM`19]"},{"why":"Provides the amplification theorem (used as Theorem A.1) that converts local-DP randomizers into single-message shuffled private protocols with the accuracy levels needed for the upper bound.","marker":"[BBGN19c]"},{"why":"Gives the prior local-model frequency-estimation lower bound in the high-privacy regime whose techniques the paper extends to low privacy and approximate differential privacy.","marker":"[BS15]"},{"why":"Provides local-model lower bounds and minimax analysis for frequency estimation, including the low-privacy pure-DP regime that the paper generalizes.","marker":"[DJW18]"},{"why":"The $B$-ary randomized response protocol used both as a matching single-message upper bound and as the counterexample showing privacy alone cannot yield the paper's mutual-information bound.","marker":"[War65]"},{"why":"RAPPOR supplies the local randomizer that, after amplification, yields the $n^{1/4}$ single-message upper bound.","marker":"[EPK14]"},{"why":"The Hadamard response is the starting point for the private-coin multi-message protocol, which modifies it to send several indices plus blanket noise.","marker":"[ASZ19]"},{"why":"The Count Min sketch underlies the public-coin multi-message protocol and its polylogarithmic query time.","marker":"[CM05a]"}],"fun_headline_variants":["Multi-message shuffle cuts private frequency error to polylog","Single-message shuffle near-optimal; multi-message improves","Exponential gain in private frequency estimation from extra messages","First separation between single- and multi-message shuffled DP","Shuffled DP: single-message error tight, multi-message polylog"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The single-message lower bound rests on the claim that an accurate local randomizer must make its output on a fixed input nearly statistically disjoint from its output on a uniform input; if an accurate protocol could keep those distributions close while still recovering frequencies by correlating messages across users, the mutual-information bound and the $n^{1/4}$ error lower bound would fail.","fun_headline_variants_meta":{"raw":{"variants":["Multi-message shuffle cuts private frequency error to polylog","Single-message shuffle near-optimal; multi-message improves","Exponential gain in private frequency estimation from extra messages","First separation between single- and multi-message shuffled DP","Shuffled DP: single-message error tight, multi-message polylog"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000968,"raw_usage":{"total_tokens":4203,"prompt_tokens":1112,"completion_tokens":3091,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":728,"completion_tokens_details":{"reasoning_tokens":3003}},"tokens_in":728,"tokens_out":3091,"duration_ms":21861,"temperature":1.0,"reasoning_tokens":3003,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:17:02.353844+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run any candidate single-message shuffled protocol with $n=B^2$ users, constant $\\varepsilon$, and $\\delta=n^{-2}$, and measure the maximum frequency-estimation error; Theorem 1.1 predicts error $\\widetilde{\\Omega}(n^{1/4})$, so an error of $o(n^{1/4})$ refutes the characterization. For a more local test of Lemma 3.15, fix $v$, compare the distribution of $R(v)$ with $R(U)$ under the protocol's local randomizer, and check whether an accurate protocol can exist with total variation distance between these two distributions bounded away from 1.","supporting_citations":[],"review_version":1}