{"id":"01bf6e7d-ec9b-46f4-8b2b-4065c7e07c9d","arxiv_id":"2505.23620","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"New private and non-private estimators achieve per-instance KL error within constant factors of the best possible error over a new additive local neighborhood.","lead":"This paper constructs private and non-private estimators that are near-optimal for each individual distribution, not just the worst case, in KL divergence. Its sampling-twice algorithms are simple private Good-Turing variants and achieve the first instance-optimal bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (4) defines N+ with min instead of the max the text and proofs require; as printed, N+ excludes Nstat and unseen-symbol alternatives, so the claimed lower bound (5) is false and Corollary G.7's instance-optimality target is vacuous.","rationale":"The reader's weakest assumption was that the additive neighborhood might be too small or conceptually wrong. My stress-test finds a more concrete, internal failure: the printed Eq. (4) uses min where the paper's own rationale and the appendix's sub-neighborhood decomposition require max. This is not a matter of disagreeing with the chosen notion of locality; it is an inconsistency inside the manuscript that invalidates the central lower bound as stated. The claimed lower bound (5) cannot hold for the printed N+, since for a concentrated distribution with zero-probability symbols the printed neighborhood restricts to a two-symbol problem with O(1/n) minimax KL error, whereas (5) gives Omega(ln d/n). Because Corollary G.7's instance-optimality statement is exactly an upper bound matching lower(p,n,N+ union N<=t/(n epsilon)), the central claim is unsupported unless Eq. (4) is amended. The fix is simple and the surrounding proofs indicate the intended definition, so this warrants a conditional verdict rather than rejection. I also note the Algorithm 2 pseudocode has undefined/incorrect variables (e.g., output uses bar{x}'_i and a normalization N that does not match), which is a separate reproducibility barrier; however, the neighborhood-definition inconsistency is more load-bearing because it affects the meaning of the theorem, not just its verification.","tokens_in":49855,"tokens_out":18987,"duration_ms":183994,"concrete_test":"Analytically verify the set inclusion used in Appendix D: for p=(1/2,1/2), t=1, n>4, the point q=(1/2+sqrt(1/(2n)), 1/2-sqrt(1/(2n))) is in Nstat (Eq. 137) but violates the printed |q_1-p_1|<=t/n condition of Eq. (4). If it is not in N+, Theorem D.3 and D.4 cannot be combined to bound lower(p,n,N+), and the claimed bound (5) for p=(1/3,2/3,0,...,0) contradicts the trivial two-symbol upper bound O(1/n). Then repeat the same check after replacing min with max in Eq. (4); if the inclusion Nstat and N<=t/n into N+ holds, Corollary G.7's comparison to lower(p,n,N+ union N<=t/(n epsilon)) is supported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's own motivation says that symbols with large p_i > t/n should be allowed a 'larger' sqrt(p_i/n) perturbation, but Eq. (4) prints |q_i-p_i| <= min{t/n, sqrt(p_i/n)}. With this min, for every p_i > t^2/n the allowed perturbation is t/n, which is smaller than sqrt(p_i/n); for p_i=0 it is 0. Hence the statistical-variance neighborhood Nstat (Eq. 137) is not contained in the printed N+, and no alternative with mass on p_i=0 symbols lies in N+. The lower bounds in Appendix D are proved for the larger sub-neighborhoods N<=t/n (Eq. 136) and Nstat, then combined as if lower(p,n,N+) >= (1/2)lower(p,n,N<=t/n)+(1/2)lower(p,n,Nstat); this combination is false under the printed definition. Concretely, for p=(1/3,2/3,0,...,0), the printed N+ has support only on symbols {1,2}, so a two-symbol estimator gives lower(p,n,N+) <= O(1/n), while Eq. (5) claims Omega(ln(1+d)/n). Thus the central instance-optimality guarantee, which matches Algorithm 1/2 to lower(p,n,N+) (or N+ union N<=t/(n epsilon)), is not established for the neighborhood as written. If Eq. (4) is corrected to max{t/n, sqrt(p_i/n)} -- as the surrounding discussion and the Appendix D decomposition presuppose -- the stated rates become plausible; but the submitted text is internally inconsistent.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies KL divergence estimation of discrete distributions under differential privacy. It first establishes minimax optimal rates for private KL estimation, showing that a Laplace-perturbed add-constant estimator is optimal up to constants. It then introduces additive local neighborhoods of a distribution, N+(p) and N≤t/(nε)(p), and proposes 'sampling-twice' Good-Turing-style estimators (Algorithm 1 non-private, Algorithm 2 private) that are claimed to be instance-optimal up to constant factors relative to these neighborhoods. The lower bounds use a generalized Assouad method for decomposable statistical distances, and the upper bounds analyze false-positive/false-negative errors under calibrated thresholding. Experiments on power-law and token distributions show improvement over the minimax add-constant baseline.","tokens_in":50171,"tokens_out":7539,"duration_ms":72530,"significance":"If the results hold as stated, this is a significant contribution: it appears to be the first tight minimax analysis of private KL distribution estimation, and the first instance-optimality guarantees for private KL estimation under a notion of local neighborhood. The proofs are parameter-free in the sense that the bounds are explicit functions of p, n, and ε, and the algorithms are concrete and reproducible from the pseudocode. The paper also correctly identifies limitations of permutation and multiplicative neighborhoods for KL loss. However, the central neighborhood definition N+ is printed inconsistently with the surrounding discussion and with the proofs in Appendix D, which is load-bearing for the instance-optimality claims; the paper should be revised to fix this definition and to reconcile the Algorithm 2 pseudocode with its analysis.","major_comments":[{"comment":"The printed definition of N+(p) uses |qi-pi| ≤ min{t/n, sqrt(pi/n)}, but the prose immediately above it says that symbols with pi > t/n should allow the larger sqrt(pi/n) perturbation, and Appendix D defines Nstat (Eq. 137) and N<=t/n (Eq. 136) as sub-neighborhoods of N+. With the printed min, Nstat is not contained in N+: for pi > t^2/n the allowed perturbation is t/n, which is smaller than sqrt(pi/n), and for pi=0 the allowed perturbation is 0, so no distribution with positive mass on a zero-probability symbol lies in N+. Consequently the claim lower(p,n,N+) ≥ (1/2)lower(p,n,N<=t/n) + (1/2)lower(p,n,Nstat) is false under the printed definition. Concretely, for p=(1/3,2/3,0,...,0), the printed N+ has support only on {1,2}, so lower(p,n,N+) ≤ O(1/n), whereas Eq. (5) with L' containing zero-probability symbols claims Ω(ln(1+d)/n). Since Theorem G.6 and Corollary G.7 match Algorithm 2 against lower(p,n,N+ ∪ N≤t/(nε)), the central instance-optimality result is not established for the neighborhood as written. The intended definition appears to be max{t/n, sqrt(pi/n)} (or an equivalent two-regime definition), which is what the proofs and the surrounding discussion presuppose; the manuscript must correct Eq. (4) and re-verify the subsequent lower-bound decomposition.","section":"Section 2, Eq. (4); Appendix D; Corollary G.7"},{"comment":"The pseudocode of Algorithm 2 is internally inconsistent. The truncation step defines \\bar{x}_i for i in L and for i not in L, but the return statement uses \\bar{x}'_i in both branches, and the normalizing constant is N = \\tilde{c} + sum_{i notin L} \\bar{x}_i, while the returned mass for i not in L is (1/N)\\bar{x}'_i. As printed, \\bar{x}'_i is undefined and the output is not a probability vector. The lemmas in Appendix G (e.g., Lemma G.3, Lemma G.4, Lemma G.5) and Theorem G.6 analyze the estimator in terms of \\bar{x}_i, so the pseudocode does not match the analyzed estimator. The pseudocode should be rewritten consistently, presumably replacing \\bar{x}'_i with \\bar{x}_i in both branches and using a single normalization sum, and the DP sensitivity argument in Theorem G.6 should be rechecked with the corrected expression.","section":"Section 3.1, Algorithm 2"},{"comment":"Even setting aside the min/max typo, the sentence 'their average is a lower bound ... because one can construct a distribution over hard instances, choosing the hard instance(s) in N<=t/n and Nstat with 1/2 probability respectively' is imprecise. The correct valid step is that for a union N = N1 ∪ N2, max_{q∈N} ≥ (1/2)max_{q∈N1} + (1/2)max_{q∈N2}, which implies the claimed inequality without constructing a mixture over hard instances. The paper should replace the vague averaging argument with this direct inequality, and should also state explicitly that the inclusion N1, N2 ⊆ N+ is required for the decomposition.","section":"Appendix D, decomposition of lower(p,n,N+)"}],"minor_comments":[{"comment":"In the proof, the citation 'lower(p, n, Nstat) in Theorem F.2' is incorrect: Theorem F.2 is the DP lower bound for N≤t/(nε), while the relevant non-DP Nstat lower bound is Theorem D.4 in Appendix D. Please fix the cross-reference.","section":"Appendix E, Corollary E.3"},{"comment":"In the proof of Theorem G.9, the text 'by ε = ln d / 2n' does not match the theorem statement's ε = ln(d)/(16n). With the stated value, the displayed bound still holds because 2γ ln d/(nε) + γ(ln d)^2/(nε) = 32γ ln d + 16γ ln d = 48γ ln d, so the factor is consistent after correcting the typo in the proof.","section":"Section 3.1, Theorem G.9"},{"comment":"The statement of the per-instance lower bound (5) says 'for any set L′', but in the matching results (e.g., Corollary G.7) the relevant quantity is the maximum over L′ of the displayed expression. Please clarify in the text that the instance-optimality matching uses sup_{L′⊆[d]} of the right-hand side.","section":"Section 2, Eq. (5)"},{"comment":"There is a typo in the experimental setup: 'MacOS intergrated CPU' should be 'MacOS integrated CPU'. Also, the figure captions reference 'Reddit Token Distribution Estimation' but do not describe error bars or the number of trials beyond the text; adding this to the captions would improve reproducibility.","section":"Section 4"},{"comment":"The pseudocode sets τ = 4 ln d, but Theorem G.6 states a general bound without explicitly displaying τ; the proof uses τ = 4 ln d. Please make the dependence of the upper bound on τ explicit in the theorem statement, and state the final choice τ = 4 ln d there.","section":"Section 3.1, Algorithm 2 and Theorem G.6"}],"recommendation":"major_revision","confidential_remarks":"No concerns about novelty disclosure: the relation to FMST24 is clearly cited and the additive-neighborhood framework is a genuine extension to KL loss. The main risk is that the Eq. (4) min/max inconsistency and the Algorithm 2 pseudocode error are both central and must be fixed before the claims are verifiable; both are local fixes, so major revision rather than rejection is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this is an important paper with a fixable but real flaw in its central definition. The contribution is genuinely new—first DP minimax KL rates, first DP instance-optimal estimators under additive neighborhoods, and a sampling-twice Good-Turing variant that keeps sensitivity at one. The generalized Assouad framework for decomposable distances is a useful tool. The upper and lower bound machinery is parameter-free and not fitted to data; that's real evidence of honest work.\n\nThe problem: Eq. (4) defines N+(p) with |q_i-p_i| ≤ min{t/n, sqrt(p_i/n)}. The surrounding text and every proof in Appendix D assume max. With min, the statistical-variance neighborhood Nstat (Eq. 137) is not contained in N+, and no alternative that puts mass on an unseen symbol is in N+. So the lower bound (5) and the matching guarantee in Corollary G.7 are not established for the neighborhood as written. For p=(1/3,2/3,0,...), the printed N+ only moves mass between symbols 1 and 2, giving lower(p,n,N+) = O(1/n), while the paper claims Ω(ln(1+d)/n). The headline instance-optimality claim therefore doesn't hold as printed. This is fixable—change min to max in Eq. (4)—but it is load-bearing, not a typo in a footnote.\n\nSecond issue: Algorithm 2's pseudocode is inconsistent. The return line uses \\bar{x}'_i, which is never defined, and the normalization N uses \\bar{x}_i for i∉L while the returned estimate uses \\bar{x}'_i. As printed, the DP estimator is not well-defined. Again fixable, but a reader cannot reproduce the algorithm from the text.\n\nMinor: the experiments grid-search α and τ on the evaluation distributions, so the empirical comparison is weaker than the theory suggests.\n\nBottom line: if the min/max and the pseudocode are corrected, this is a strong paper. As submitted, the central theorem needs a major revision. It deserves a serious referee, not a desk reject. I would not cite the main guarantee in its current form, but I would watch for the revision.","headline":"First DP KL minimax rates and a clever sampling-twice estimator, but the printed neighborhood definition contradicts the proofs; the headline instance-optimality theorem needs a fix before it is established.","tokens_in":50728,"tokens_out":3551,"would_cite":false,"duration_ms":33500,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62B10","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that private KL distribution estimation can be instance-optimal: a differentially private 'sampling twice' Good-Turing estimator achieves per-instance KL error within a constant factor of the per-instance minimax…","keywords":["differential privacy","KL divergence","distribution estimation","instance-optimality","Good-Turing estimator","minimax optimality","additive neighborhoods","Poisson sampling"],"falsifier":"Run Algorithm 2 on a power-law distribution $p_i \\propto i^{-\\beta}$ with $d=50{,}000$, $n=10^4$, and $\\varepsilon=1$; estimate $\\mathbb{E}[\\mathrm{KL}(p,A(x))]$ by repeated Poisson sampling and compare it with $\\mathrm{lower}(p,n,\\mathcal{N}^+ \\cup \\mathcal{N}_{\\le 24\\ln d/(n\\varepsilon)})$ evaluated from the formulas in the paper. If the empirical error is more than a large constant factor above this bound, or if the ratio grows with $d$, the claimed constant-factor instance-optimality fails.","tokens_in":49603,"feed_emoji":"📊","tokens_out":12320,"duration_ms":112464,"temperature":0.7,"pith_summary":"This paper studies the KL error of estimating a discrete distribution from Poisson counts, and argues that minimax optimality is the wrong lens: add-constant estimators that are minimax optimal in $\\ln(1+d/n)$ often perform poorly on skewed real-world distributions. The goal is per-instance guarantees, in which the error on a fixed unknown $p$ is compared to the minimum error achievable by any estimator that only knows $p$ lies in a small additive neighborhood. The paper introduces such additive neighborhoods (perturbing each probability by roughly $\\min\\{t/n,\\sqrt{p_i/n}\\}$, with a $1/\\varepsilon$ inflation in the private case) and proves that a differentially private variant of Good-Turing's 'sampling twice' estimator matches the resulting per-instance lower bound up to constant factors. A non-private version of the same estimator is also instance-optimal. If the characterization is right, practitioners get automatic adaptation: concentrated or heavy-tailed distributions are estimated far below the worst-case rate, and differential privacy only costs on small-probability symbols.","feed_headline":"Private Good-Turing matches per-instance KL limits","feed_subtitle":"A DP estimator now provably adapts to each distribution's difficulty, beating worst-case rates on skewed data.","key_machinery":"Two mechanisms carry the argument. First, the 'sampling twice' estimator: split the Poisson sample into two halves, use one half to decide which symbols have small counts, use the other half to estimate the combined mass of those symbols, and truncate individual noisy counts at a floor $\\max\\{\\cdot, 1/\\min\\{\\varepsilon,1\\}\\}$. This reduces the sensitivity to adjacent datasets to one, which is what makes a Good-Turing-style bias correction privatizable. Second, the lower-bound analysis is driven by a generalized Assouad's method (Theorems A.3 and A.4) that applies to any decomposable statistical distance; KL is decomposable in the sense that $\\mathrm{KL}(p,q) \\ge \\sum_j p(B_j)\\,\\mathrm{KL}(p|_{B_j}, q|_{B_j})$ over disjoint symbol blocks. For the DP algorithm, a calibrated threshold $\\tau = 4\\ln d$ (equivalently neighborhood size $t=24\\ln d$) balances false positives (small-probability symbols treated as large) against false negatives (large-probability symbols treated as small), which is the quantitative core of the instance-optimality proof.","core_discovery":"Central claim: under the additive neighborhoods $\\mathcal{N}^+(p) = \\{q: |q_i-p_i| \\le \\min\\{t/n,\\sqrt{p_i/n}\\}, \\sum_{i:p_i\\le t/n} q_i \\le \\max\\{t/n,\\sum p_i\\}\\}$ (and the privacy-scaled $\\mathcal{N}_{\\le t/(n\\varepsilon)}$ version), per-instance KL error is tightly characterized. Concretely, Algorithm 2 is $\\varepsilon$-DP and satisfies $\\mathbb{E}_{x\\sim \\mathrm{Poi}(np)}[\\mathrm{KL}(p,A(x))] \\le O(\\mathrm{lower}(p,n,\\mathcal{N}^+ \\cup \\mathcal{N}_{\\le 24\\ln d/(n\\varepsilon)}))$, i.e. it is competitive with any estimator that knows the truth lies in that small additive ball; Algorithm 1 achieves the non-private analogue. The lower bounds are proved for any estimator via a generalized Assouad's method for decomposable statistical distances, exploiting that KL divergence is decomposable. The paper further shows this neighborhood scale is necessary up to constants: no $(\\varepsilon,\\delta)$-DP estimator can be instance-optimal with respect to neighborhoods of size $\\gamma \\ln d/(n\\varepsilon)$ for $\\gamma=o(1)$.","pith_inferences":["The sensitivity reduction from splitting the sample is not KL-specific, so a similar 'sampling twice' construction could plausibly yield private instance-optimal estimators for other decomposable losses such as total variation or $\\ell^2$ error under the same additive-neighborhood framework.","The threshold $\\tau=4\\ln d$ acts as an automatic, privacy-aware smoothing schedule: symbols whose noisy counts fall below threshold are pooled and their mass is estimated from fresh data; this suggests a testable recipe for language-model smoothing against fixed add-constant baselines.","The necessity theorem draws a sharp boundary: any stronger instance-level guarantee for private KL estimation would have to change what the hypothetical knowledgeable estimator is allowed to know (a different neighborhood definition), not merely tighten constants."],"forward_implications":["For each fixed $p$, the DP algorithm's expected KL error is bounded by a constant times $\\mathrm{lower}(p,n,\\mathcal{N}^+\\cup\\mathcal{N}_{\\le t/(n\\varepsilon)})$; distributions with a few heavy symbols or small combined mass on rare symbols are therefore estimated far below the worst-case $\\ln(1+d/n)$ rate.","Privacy is essentially free for symbols with large $p_i$: their contribution to the private bound is $1/(n^2\\varepsilon^2 p_i)$, smaller than the non-private $1/n$ term, so the DP penalty concentrates on rare symbols.","The neighborhood size $\\Theta(\\ln d/(n\\varepsilon))$ is necessary for worst-case DP instance-optimality: for any $\\gamma=o(1)$, no DP estimator can match a baseline that knows a neighborhood of size $\\gamma \\ln d/(n\\varepsilon)$.","The non-private 'sampling twice' algorithm matches the per-instance lower bound up to constants under additive neighborhoods, and in experiments it is competitive with the prior Good-Turing baseline while being easier to privatize.","The experiments show the DP algorithm outperforming the minimax-optimal add-constant DP baseline on power-law and real token distributions, which the instance-optimality guarantee predicts."],"supporting_citations":[{"why":"Supplies the prior near-instance-optimal Good-Turing estimator under permutation neighborhoods, which the sampling-twice algorithm simplifies and privatizes.","marker":"[OS15]"},{"why":"Introduces the per-instance neighborhood framework (equation 2) that defines instance-optimality relative to a hypothetical estimator knowing the neighborhood.","marker":"[FMST24]"},{"why":"Origin of the Good-Turing bias-correction idea for unseen and low-count symbols on which both algorithms rely.","marker":"[Goo53]"},{"why":"Defines differential privacy and the Laplace mechanism used to privatize the sampling-twice estimator and justify its epsilon-DP guarantee.","marker":"[DMNS06]"},{"why":"Provides the private Assouad method and prior DP distribution-estimation lower bounds generalized to decomposable distances in this paper.","marker":"[ASZ21]"},{"why":"Original Assouad's method for lower bounds, extended here to decomposable statistical distances via Theorem A.3.","marker":"[Yu97]"},{"why":"Gives the non-private minimax KL lower bounds that set the worst-case benchmark the per-instance bounds refine.","marker":"[Pan04]"},{"why":"Supplies the KL divergence formula between Poisson distributions used in the coupling and total-variation calculations in lower bounds.","marker":"[Sho13]"}],"fun_headline_variants":["DP Good-Turing hits instance-optimal KL","Instance-optimal privacy for KL distribution estimation","Per-instance KL bounds under differential privacy","Private KL estimation that beats worst-case rates","Good-Turing with DP matches per-instance limits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that additive perturbation of each symbol's probability—by $\\min\\{t/n,\\sqrt{p_i/n}\\}$ in the non-private case and $t/(n\\varepsilon)$ under privacy—is the right way to measure how hard a distribution is; if the genuinely hard alternatives require changing symbol identities or reordering, the instance-optimality guarantees would be measuring the wrong kind of difficulty.","fun_headline_variants_meta":{"raw":{"variants":["DP Good-Turing hits instance-optimal KL","Instance-optimal privacy for KL distribution estimation","Per-instance KL bounds under differential privacy","Private KL estimation that beats worst-case rates","Good-Turing with DP matches per-instance limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000868,"raw_usage":{"total_tokens":3785,"prompt_tokens":995,"completion_tokens":2790,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":2721}},"tokens_in":611,"tokens_out":2790,"duration_ms":20291,"temperature":1.0,"reasoning_tokens":2721,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:42:25.744165+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a power-law distribution $p_i \\propto i^{-\\beta}$ with $d=50{,}000$, $n=10^4$, and $\\varepsilon=1$; estimate $\\mathbb{E}[\\mathrm{KL}(p,A(x))]$ by repeated Poisson sampling and compare it with $\\mathrm{lower}(p,n,\\mathcal{N}^+ \\cup \\mathcal{N}_{\\le 24\\ln d/(n\\varepsilon)})$ evaluated from the formulas in the paper. If the empirical error is more than a large constant factor above this bound, or if the ratio grows with $d$, the claimed constant-factor instance-optimality fails.","supporting_citations":[],"review_version":1}