{"id":"2a1d7d47-ce41-4206-914a-c857e1ed3fdb","arxiv_id":"2509.24173","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The exact asymptotic worst-case mean squared error for discrete distribution estimation under utility-optimized local differential privacy is characterized as a saddle-point optimization, and uBD schemes achieve it.","lead":"Researchers proved an exact formula for the most accurate possible estimate of a population's categories when only sensitive answers are protected. The result settles the leading constant and introduces a scheme family that attains it.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 9's key trace identity (58) is inverted: as printed it gives 1/M_i in the AM-HM step and would break the converse; the corrected identity tr(B_i)=d_i^2/M_i restores the proof.","rationale":"The paper's central claim is an exact minimax constant for distribution estimation under ULDP. The reader identified Theorem 8, the reduction to extremal ULDP mechanisms, as the weakest assumption. I examined that proof and found it structurally sound: the conic-hull decomposition in (90)–(91), the construction of γ and T, and the row-sum verification all check out. The load-bearing problem I found is instead an internal algebraic inconsistency in Proposition 9. Equation (58) as printed cannot be correct: if tr(B_i)=d_i^2 M_i, the AM-HM line gives tr^{-1}(B_i)≥1/M_i, so the claimed inequality tr^{-1}(J)≥Σ M_i does not follow. A concrete scalar evaluation (v=2, w=3, ε=ln2, α=1/2, t=δ(1;v)) gives M3=15/8 and tr(B3)=8/15, so the intended identity is tr(B_i)=d_i^2/M_i. With that one-character fix, the proof chain in Proposition 9 works and is consistent with Proposition 10's d_i/M_i coefficient. Thus the issue is real but almost certainly typographical; it does not overturn the reader's CONDITIONAL verdict, but it strengthens the need for a careful independent check of Appendix C-F. I therefore recommend no verdict change.","tokens_in":30020,"tokens_out":26983,"duration_ms":193530,"concrete_test":"Recompute (58) for the scalar case i=3, v=2, w=3, ε=ln2, α=1/2, t=δ(1;v). Use (26) to get M3=15/8; use Table I with Q_{P^{(α)}}(Y_P)=5/6 and Q_{P^{(α)}}(Y_I)=1/6 to compute tr(B3)=8/15. If tr(B3)=1/M3, then Equation (58) should read tr(B_i)=d_i^2/M_i. As a second check, re-derive Appendix C-F from tr(B_i)=E∥Π_i η_{P^{(α)},Q}∥^2 and verify the corrected identity for i=1,2 as well. If the manuscript's (58) is retained verbatim, substitute it into (57)–(59) and confirm that the lower bound collapses to Σ 1/M_i rather than Σ M_i.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The converse lower bound in Proposition 9 hinges on the block trace identity (58). The text states tr(B_i)=d_i^2 M_i(α,t(Q)). Combining with the preceding AM-HM inequality tr^{-1}(B_i)≥d_i^2/tr(B_i) gives tr^{-1}(B_i)≥1/M_i, not M_i. The desired inequality (59), namely tr^{-1}(J)≥Σ M_i(α,t(Q)), therefore does not follow from the displayed equations. A direct check shows the correct identity is tr(B_i)=d_i^2/M_i. For example, take v=2, w=3, ε=ln2, α=1/2, t=δ(1;v). From (26), M3=15/8, while Table I and (102)–(108) give tr(B3)=8/15=1/M3. With the corrected identity, AM-HM yields tr^{-1}(B_i)≥M_i and the sum in (59) is exactly M(α,t(Q)). This is very likely a typographical inversion in (58), not a conceptual failure; nevertheless, as printed the central converse proof is internally inconsistent, and the discrepancy must be fixed or independently re-derived before the result is considered verified. I also checked the reader's weakest assumption, Theorem 8's extremal-ULDP reduction; its conic-hull post-processing argument appears coherent, so that is not where I find the main problem.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies discrete distribution estimation under utility-optimized local differential privacy (ULDP). Its main claim is a complete characterization of the asymptotic minimax mean-squared-error constant: for all w > v >= 1 and epsilon > 0, M*(w,v,epsilon) = sup_{alpha in [0,1]} inf_{t in Delta_v} M(alpha,t), where M is the sum of the three components in (24)-(26). The converse is built from a uniform asymptotic Cramer-Rao lower bound, a reduction of the ULDP class to a newly defined class of extremal ULDP mechanisms, and a decomposition of the distribution space into three orthogonal subspaces. The achievability side introduces utility-optimized block design (uBD) schemes, mixing block-design mechanisms and using score-based linear estimators, and proves that an optimized uBD scheme attains the saddle-point value. Closed-form saddle points are given in some regimes, identifying when uRR is optimal and when uSS is strictly suboptimal, and numerical experiments on ACS data support the theoretical results.","tokens_in":30333,"tokens_out":8503,"duration_ms":92749,"significance":"If correct, this is a substantial result: it gives the exact leading constant of the privacy-utility tradeoff under ULDP for all w > v and epsilon > 0, closing a gap left by prior order-optimal analyses. The authors make several genuinely useful technical contributions: a uniform asymptotic CRLB that is not tied to LDP-specific structure, a reduction to extremal ULDP mechanisms that makes the minimax problem finite-dimensional, and an explicit concave-convex saddle-point optimization formulation. The proposed uBD schemes are constructive and the paper includes reproducible code for the experiments. However, the main converse proof as printed contains a load-bearing algebraic inversion in the trace identity used in Proposition 9; this must be corrected and the surrounding calculations updated before the central claim can be considered verified.","major_comments":[{"comment":"The identity as printed is inverted. Combining tr(B_i)=d_i^2 M_i(alpha,t(Q)) with the preceding AM-HM inequality tr^{-1}(B_i) >= d_i^2/tr(B_i) gives tr^{-1}(B_i) >= 1/M_i, not M_i, so the desired bound (59) does not follow. A numerical check for v=2, w=3, epsilon=ln 2, alpha=1/2, t=delta(1;v) gives M_3=15/8 from (26), while Table I and (102)-(108) give tr(B_3)=8/15=1/M_3. The corrected identity tr(B_i)=d_i^2/M_i restores the AM-HM step. Please fix (58) and the surrounding calculation in Appendix C-F, or re-derive independently; as printed, Proposition 9 is internally inconsistent.","section":"§V-C, Eq. (58)"},{"comment":"The saddle-point existence proof is not rigorous as written. The text sets dom(M)=[0,1] x (Delta_v \\ {delta(v;v)}) and then claims M is continuous everywhere in [0,1] x Delta_v and invokes Sion's theorem on the compact set [0,1]. But M_1(alpha,delta(v;v))=infinity, so M is not real-valued continuous there, and Delta_v \\ {delta(v;v)} is not compact. Since Corollary 12 relies on existence of a saddle point, please replace this paragraph by an extended-real or restricted-domain minimax argument (e.g., lower semicontinuity on the compact simplex) or prove directly that the t-minimizer avoids the singular vertex.","section":"Appendix B"},{"comment":"The reduction of all ULDP mechanisms to extremal mechanisms is the load-bearing step for the uniform-CRLB lower bound (49), but the proof is highly compressed. The conic-hull decomposition of an arbitrary protected column via (90)-(91) and the verification that the gamma defined in (93) satisfies the normalization (48) are asserted rather than derived. Please expand these steps; a gap here would invalidate the converse bound even after the trace-identity correction.","section":"Appendix C-D / Theorem 8"}],"minor_comments":[{"comment":"The prior term changes notation from pi^2 n^{1/2} I in (39) to pi^2 n^{-1/2} I in (42). Please align these expressions with the Bayesian CRLB convention used.","section":"§V-A, Eqs. (39)-(42)"},{"comment":"The continuous extension of the estimator at alpha=0,1 is left implicit. For reproducibility, give the explicit limiting formula, especially in the cases where M_i(alpha,t) is singular.","section":"Definition 10"},{"comment":"The quantity f(gamma)=1-sum_{y' in Y_P} gamma(y') is used in the display and figure before being formally named. Define it in Definition 8.","section":"Definition 8 / Fig. 3"},{"comment":"The table is dense; a short sentence explaining the column grouping, particularly the Y_I columns for x in y versus x not in y, would improve readability.","section":"Table I"}],"recommendation":"major_revision","confidential_remarks":"The trace-identity error in Eq. (58) is the main blocking issue; it appears to be a typographical inversion that is fixable within the manuscript's scope, but it must be corrected and checked before the result is accepted. The saddle-point existence proof in Appendix B also needs tightening. I do not see a circularity problem: the saddle-point value is derived analytically, not fitted, and no free parameter is tuned to data."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is honest: this paper resolves the exact leading constant for discrete distribution estimation under ULDP, and the machinery is genuinely new. The saddle-point characterization, the uniform asymptotic CRLB, the reduction to extremal ULDP mechanisms, and the uBD achievability construction all fit together into a coherent whole. I also think the corollaries are real results: first proof that uRR is optimal in a regime, and a clean demonstration that uSS is suboptimal.\n\nThat said, the stress-test note found a real landmine. Equation (58) as printed says tr(B_i)=d_i^2·M_i, but the AM-HM step then gives tr^{-1}(B_i)>=1/M_i, not M_i, so the sum in (59) does not follow. The corrected identity is tr(B_i)=d_i^2/M_i. I checked the v=2,w=3,eps=ln2 example myself: for i=3, M3=15/8 and Table I, eqs. (102)-(108) give tr(B3)=8/15=1/M3. So the stress-test is right, and the fix restores the proof. This is almost certainly a harmless inversion typo, but it sits in a load-bearing step, and as printed the converse is internally inconsistent. It must be fixed before the proof is trusted.\n\nThe weaker spots beyond that are minor. The appendices lean heavily on direct calculations, which is uncomfortable for a result of this precision; a referee should verify at least (58) and the saddle-point treatment on the punctured simplex. The experiments lack error bars and use only one dataset, but that is not what the paper is about. The reduction in Theorem 8, which the reader flagged as the weakest assumption, appears coherent to me on inspection; the conic-hull argument is standard and I don't see a gap there. I also don't see circularity: [29] and [30] are published tools, not assumptions smuggled into the theorem.\n\nWho gets value from this: anyone working on local differential privacy or private distribution estimation. It deserves a serious referee, and after the typo is corrected I would be happy to cite it.","headline":"Real advance on the exact ULDP constant, but equation (58) has an inverted trace identity that must be fixed before the converse proof is credible.","tokens_in":30831,"tokens_out":1885,"would_cite":true,"duration_ms":15836,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62B10","62F12","68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes the exact asymptotic privacy–utility tradeoff for discrete distribution estimation under utility-optimized local differential privacy, giving the precise worst-case mean-squared-error constant as the value of a finite-","keywords":["local differential privacy","utility-optimized local differential privacy","discrete distribution estimation","privacy-utility tradeoff","Cramér-Rao lower bound","block design","minimax estimation","saddle-point optimization"],"falsifier":"Construct a ULDP mechanism whose protected-output matrix is not dominated by the staircase pattern and show that none of its rows can be written as a convex combination of extremal-ULDP rows; if such a mechanism exists, Theorem 8 fails and the converse bound (49) collapses. Alternatively, for a specific (w,v,epsilon) in the intermediate regime, solve the saddle-point problem and exhibit a ULDP estimator scheme whose asymptotic error is strictly smaller than M(alpha*,t*), a direct counterexample to Theorem 3.","tokens_in":29899,"feed_emoji":"🔒","tokens_out":4542,"duration_ms":94175,"temperature":0.7,"pith_summary":"The paper claims to settle the exact asymptotic privacy–utility tradeoff for discrete distribution estimation under utility-optimized local differential privacy (ULDP), where only some categories are sensitive. It characterizes the optimal worst-case mean squared error (scaled by n) as the value of a finite-dimensional concave–convex saddle-point problem, sup over alpha and inf over t of M(alpha,t), with M a sum of three terms corresponding to estimating the relative frequencies over sensitive categories, the relative frequencies over non-sensitive categories, and the total sensitive mass. The converse builds on a uniform asymptotic Cramér–Rao lower bound and a reduction to a newly defined class of extremal ULDP mechanisms. The achievability side constructs utility-optimized block design (uBD) schemes that mix multiple block design mechanisms and use score-based linear estimators. If correct, this gives the exact leading constant for all w>v and epsilon>0, resolving an open gap left by earlier order-optimal and rate-optimal results.","feed_headline":"Exact privacy-utility limit found for ULDP estimation","feed_subtitle":"Theorem gives the precise leading constant of minimax error for every sensitive-set size and privacy budget.","key_machinery":"The load-bearing object is the saddle-point function M(alpha,t) — the sum of three Fisher-information terms M1, M2, M3 — together with two structural results: a uniform asymptotic Cramér–Rao lower bound (Theorem 7) that upgrades pointwise CRLB to a uniform bound over a compact degrading class, and a reduction (Theorem 8) showing that every ULDP mechanism is degraded by an extremal ULDP mechanism whose protected outputs follow the staircase pattern matrix. The achievability side is built from uBD schemes, which mix block design mechanisms with proportions t_k and use a score-based linear estimator derived from the same H1⊕H2⊕H3 decomposition of the tangent space.","core_discovery":"The central discovery is Theorem 3: for w>v and epsilon>0, the asymptotically optimal worst-case mean squared error (scaled by n) equals sup_{alpha in [0,1]} inf_{t in Delta_v} M(alpha,t), where M is the sum of the three terms in (24)–(26). Each term is the Cramér–Rao lower bound for one component of a decomposition of the unknown distribution: the relative values over sensitive categories, the relative values over non-sensitive categories, and the total probability of sensitive data. Since M is concave–convex on a compact domain, the sup-inf is a genuine saddle-point value, and Corollary 12 shows that a uBD scheme built from a saddle point (alpha*, t*) attains this value. Thus the formula i","pith_inferences":["Editorial extension: the numerical observation that the optimal mixture t* concentrates on k=1 and k=2 in the intermediate regime suggests a structural conjecture — optimal extremal ULDP mechanisms may only need to mix two block designs — which, if proven, would simplify implementation and sharpen Theorem 4.","Editorial extension: the same template — uniform asymptotic CRLB plus an extremal-mechanism reduction plus distribution decomposition — should transfer to neighboring models such as (epsilon,delta)-ULDP, high-low LDP, or input-discriminative LDP; the H1,H2,H3 split indicates that the minimax error separates into per-component Fisher terms in these settings too.","Editorial extension: the exact constants have finite-sample consequences: for fixed n, the optimal unbiased scheme has error R1(Q,hat P)/n with R1 exactly characterized, so practitioners can choose (alpha,t) by the same saddle-point computation rather than by tuning heuristics.","Editorial extension: the paper leaves open a complete closed form in the intermediate regime epsilon in (epsilon_L, epsilon_H); an analytic characterization there would complete the story and could reveal whether the two-point support of t* is exact."],"forward_implications":["For any (w,v,epsilon), the optimal leading constant becomes computable: it is the value of a finite-dimensional concave–convex saddle-point problem solvable by standard convex optimization solvers.","In the Case (a) regime of Theorem 4, the earlier uRR scheme is asymptotically optimal, giving the first proof of optimality for uRR in any regime.","In the Case (b) regime (v≥4 and epsilon below E(v,1)), the previously proposed uSS scheme is strictly suboptimal, so the uBD class genuinely improves on known schemes.","In that same Case (b), the optimal error equals the LDP-only error on the v sensitive categories, meaning the non-sensitive categories can be disclosed at no asymptotic privacy cost (Remark 3).","In several regimes the optimal uBD scheme can be implemented with only log2 w bits of communication per client, the minimum needed for consistent estimation."],"fun_headline_variants":["Exact minimax risk pinned for ULDP estimation","Saddle-point formula settles privacy-utility trade-off","Sharp bound: uBD schemes hit fundamental limit","ULDP estimation error fully characterized"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The converse lower bound rests on Theorem 8's claim that every ULDP mechanism can be simulated by post-processing some extremal ULDP mechanism; if a single ULDP mechanism escapes this reduction, the claimed minimax constant could be lower than the formula predicts.","fun_headline_variants_meta":{"raw":{"variants":["Exact minimax risk pinned for ULDP estimation","Saddle-point formula settles privacy-utility trade-off","Sharp bound: uBD schemes hit fundamental limit","ULDP estimation error fully characterized"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000151,"raw_usage":{"total_tokens":1030,"prompt_tokens":731,"completion_tokens":299,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":241}},"tokens_in":475,"tokens_out":299,"duration_ms":27155,"temperature":1.0,"reasoning_tokens":241,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T14:39:37.832726+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a ULDP mechanism whose protected-output matrix is not dominated by the staircase pattern and show that none of its rows can be written as a convex combination of extremal-ULDP rows; if such a mechanism exists, Theorem 8 fails and the converse bound (49) collapses. Alternatively, for a specific (w,v,epsilon) in the intermediate regime, solve the saddle-point problem and exhibit a ULDP estimator scheme whose asymptotic error is strictly smaller than M(alpha*,t*), a direct counterexample to Theorem 3.","supporting_citations":[],"review_version":1}