{"id":"fcd6e80d-7776-43ff-b2c3-247613b1a1b5","arxiv_id":"2411.08791","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For finite discrete distributions, a recursive mechanism that preserves the public prior is exactly minimax optimal for every f-divergence, and reduces to randomized response when the prior is uniform.","lead":"This paper designs a way for a user to release one private data point that approximates their own data distribution while leaving publicly known patterns unchanged. It proves the best such scheme, for any f-divergence measure, depends only on the least-likely public category, and gives a fast recursive algorithm to build it.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 1–2 silently assume q is strictly positive on X; with any q_i=0 the feasible set Q_ε∩{qK=q} is empty under the paper's ratio definition, and for TV the qmin→0 value 0.5 is not attained (example q=(0,1/2,1/2)).","rationale":"The reader's weakest_assumption already identifies the full-support boundary, and my read agrees: the stated theorems are false or undefined when q has zero atoms, and the paper does not flag this. The core construction for strictly positive q appears sound: Lemma 3's diagonal bound is correct, Algorithm 1 produces a row-stochastic, positive, ε-LDP kernel preserving q, and Proposition 4's induction shows the minimal diagonal equals the lower bound. The universal optimality across f-divergences therefore holds in the full-support regime, which is the mathematically substantial part of the paper. The missing hypothesis is nevertheless load-bearing because the boundary case is not merely a convention issue: under the paper's ratio definition the feasible set can be empty, and under a relaxed zero-column reading the numerical optimum changes (TV drops from 1 to 0.5 in the limit qmin→0). Since the reader already issued CONDITIONAL for exactly this reason, no verdict change is needed; the revision should add an explicit full-support or support-restriction assumption in Theorem 1, Theorem 2, Algorithm 1, and Corollaries 1–2, and either reject zero entries in the input or reduce X to supp(q). The abstract's omission of 'linear' is a separate presentational concern that reinforces CONDITIONAL but is not the main correctness risk.","tokens_in":19613,"tokens_out":20236,"duration_ms":204007,"concrete_test":"Set n=3, q=(0,1/2,1/2), ε=1, TV. Write the feasibility LP with variables K_ij, row sums 1, qK=q, and LDP constraints K_ij ≤ e^ε K_lj for all i,l,j, treating a column as allowed only if all its entries are zero. Show the LP is infeasible, which is what Definition 4 demands. Separately, relax the LDP constraint to allow zero columns; solve sup_i (1−K_ii) over the remaining constraints and verify the minimum is 1, not 0.5, the value one would get by substituting qmin=0 into Corollary 1. This pinpoints the missing full-support hypothesis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is correct for full-support priors, but the paper never states that condition. Theorem 1 says 'finitely supported' and sets qmin = min_x q(x); if X contains an atom with q_i=0, the proof and the algorithm both break. From qK=q, column i has sum_j q_j K_ji = 0, so K_ji=0 for every j≠i (q_j>0). Under Definition 4's ratio condition, a column with any positive entry and any zero entry gives an infinite supremum, so K_ii must also be 0; the whole column is zero, and then the ratio 0/0 for output i is undefined. Hence no mechanism in Q_ε preserves q, and Γ_f in (4) is not well-defined. Algorithm 1 does not check this: for q1=0 it returns a zero column. If one instead relaxes the definition to allow zero output columns, Lemma 1 ceases to hold: D_f(δ_i || δ_iK) is not g(K_ii), because δ_iK(i)=0 while δ_i(i)=1 makes the divergence infinite for many f. The failure is quantitative, not cosmetic: for q=(0,1/2,1/2), ε=1 and TV, any feasible mechanism gives sup_p TV(p||pK) ≥ TV(δ_1||δ_1K)=1, while the formal qmin→0 limit of Corollary 1 is 1/2. Thus Theorems 1–2 require the explicit assumption that q is supported on all of X (equivalently, that the domain is restricted to supp(q) and adversarial p are also confined to supp(q)).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a framework for locally private sampling in which each user holds a private distribution p and a public prior q, and the goal is to output a sample from a distribution pK that is close to p while satisfying qK = q. The main theoretical contribution is a minimax characterization of the best worst-case f-divergence over all ε-LDP Markov kernels that preserve q, together with an O(n^3) recursive algorithm that outputs a mechanism attaining the bound. The paper further shows that the optimal mechanism is independent of the choice of f-divergence, recovers randomized response when q is uniform, and validates the sampler empirically against the relative-mollifier baseline on synthetic data, the Avazu CTR dataset, and MovieLens.","tokens_in":19987,"tokens_out":5698,"duration_ms":53952,"significance":"If the main result is taken in its intended domain, it is a clean and useful characterization: the worst-case f-divergence depends on the public prior only through its smallest atom, and a single mechanism is simultaneously optimal for every f-divergence. The lower-bound part (Proposition 2, via Lemmas 1--3) is self-contained and sound, and recovering Park et al.'s uniform-prior utility from the new theorem is a meaningful consistency check. The availability of code and the explicit O(n^3) construction are also strengths. The main caveat is that the theorem statements omit a strict-positivity assumption on q, and the proof of Proposition 3 is incomplete for general columns; both issues are fixable but are load-bearing for the stated claims.","major_comments":[{"comment":"The theorems state only that q is finitely supported and define qmin = min_x q(x), but they require qmin > 0. If q has an atom with q_i = 0, the feasible set {K ∈ Q_ε : qK = q} is empty under Definition 4. For example, with q = (0, 1/2, 1/2), the invariance qK = q forces K_{j1} = 0 for j = 2, 3, so for output 1 the ratio pK(1)/p'K(1) is either undefined or infinite for suitable p, p'; no ε-LDP mechanism exists. Algebraically, qK = q and nonnegativity give zero off-diagonal entries in the zero-mass column, and Definition 4's ratio condition then forbids any positive diagonal entry in that column, making the column identically zero and the ratio 0/0. Algorithm 1 does not detect this case, and the formal qmin → 0 value in Corollary 1 is not attained: for this q with ε = 1 and TV, the true minimax value would be at least the infinite divergence at a Dirac mass on the zero-probability atom. The fix is to state explicitly that supp(q) = X, or equivalently to replace X by supp(q) throughout including the supremum over p; this assumption must appear in Theorem 1, Theorem 2, Corollary 1, and Algorithm 1.","section":"§3.1, Theorem 1; Algorithm 1; Corollary 1"},{"comment":"The proof that the mechanism output by Algorithm 1 is ε-LDP is incomplete. The induction verifies the first column and then treats only column j = 2 in detail, deriving (46) and (48), and the bounds for the remaining columns are dismissed with 'With minimal changes'. The missing general-column argument is not a purely cosmetic repetition: for a general column j, one must control K_{1j} against m e^{±ε} times the minimum or maximum of the j-th column of the recursively constructed M, which uses the sortedness of q and the invariant structure of M in a way that is not sketched. Since Theorem 2's validity depends on K being ε-LDP, this gap must be closed. The same proof also contains an obvious typo, 'qK = K' at the end of the LDP verification, which should read 'qK = q'.","section":"Appendix A.5, proof of Proposition 3"},{"comment":"The paper states that f is convex on (0, ∞) with f(1)=0, and permits f(0)=f(0+) to be infinite, but Lemma 1 and Proposition 2 use the expression g(x)=f(0)+x(f(1/x)-f(0)), which is not well-defined as a difference when f(0)=∞. The proof of Proposition 4 begins 'Assume that f(0) < ∞, since otherwise Γf(q,ε)=∞', but this assumption is not carried into Theorem 1's statement that the characterization holds for 'general f-divergences'. The manuscript should either state the condition f(0)<∞ for the finite closed-form expression or spell out the separate degenerate case f(0)=∞. This is a real mismatch between the theorem statement and the proof, even though it does not affect the main examples (KL, TV) used in the paper.","section":"Lemma 1 and Theorem 1; Appendix A.6"}],"minor_comments":[{"comment":"The input description says 'increasingly sorted pulic prior'; 'pulic' should be 'public'.","section":"Algorithm 1 caption"},{"comment":"In the displayed utility formula, 'eε + k − 1' should be 'eε + n − 1'; 'k' is not defined in that context.","section":"Appendix A.7, Corollary 2 proof"},{"comment":"Definition 4 writes the ratio pK(x)/p'K(x) without requiring the denominator to be positive. The authors should either define the convention for zero denominators or restrict the supremum to outputs with positive probability, since this ambiguity is the source of the qmin=0 infeasibility noted above.","section":"Definition 4"},{"comment":"The paper calls the relative mollifier framework the 'state-of-the-art private sampler', but Park et al. (2024), whose linear setting is the direct precursor, is not included in the experimental comparison. The scope statement says the paper considers only linear samplers, so a short clarifying sentence that the empirical baseline is the relevant prior linear-sampler method would prevent overclaiming.","section":"§5 and related-work discussion"}],"recommendation":"major_revision","confidential_remarks":"The central construction is correct for the intended full-support case, and the lower bound is sound, so I do not see a fundamental flaw that would warrant rejection. The main revision task is to add the strict-positivity assumption to every theorem and algorithm and to complete the LDP verification in Proposition 3. Once those are in place, the paper should be publishable. The missing support condition is surprising given the checklist's claim that all assumptions are stated, and I would ask the authors to audit the statement checklist for the revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Core result is real and clean: for a finite alphabet and a strictly positive public prior q, this paper gives the first exact minimax optimal linear ε-LDP sampler that keeps q invariant, and the mechanism is universal across f-divergences. The lower bound in Proposition 2 and the attainment proof for Algorithm 1 check out—I spot-checked the recursion and the LDP constraints. The risk depending only on qmin is a neat characterization, and the uniform-prior case recovering randomized response is a sensible consistency check.\n\nThe main problem is an unstated boundary condition. Theorem 1 and Algorithm 1 say \"finitely supported\" but actually require q_i > 0 for every atom. If some q_i = 0, the combination of qK = q and finite-ε LDP over the full simplex is infeasible under Definition 4's ratio condition, and the formal qmin → 0 limit is not attained. For q = (0, 1/2, 1/2) with TV, any feasible mechanism has worst-case risk 1, not 1/2. This is a genuine gap in the theorem statement, but it is fixable: add the full-support assumption, or restrict both X and the adversarial p to supp(q). The abstract also overclaims by omitting \"linear\"—this is optimality over Markov kernels, not over the non-linear samplers from Park et al.\n\nTwo smaller issues: Proposition 3's proof skips the general-column verification with \"with minimal changes,\" and there are typos (e.g., \"qK = K\"). The experiments compare only against Husain et al.'s relative mollifier; adding Park et al. as a baseline would be more informative.\n\nBottom line: this deserves a serious referee. The math is correct for the intended domain, the problem is new, and the flaw is an omitted assumption, not a broken derivation. I'd ask for the support condition to be stated, the abstract qualified, and the proof of Proposition 3 tightened.","headline":"A clean minimax LDP-sampling result with a public prior, correct for full-support priors but missing a stated support assumption; worth a serious referee after revision.","tokens_in":20514,"tokens_out":2794,"would_cite":true,"duration_ms":23540,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","62B10","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that, for finite discrete distributions, one ε-locally-private Markov kernel built from a public prior q is simultaneously minimax optimal for every f-divergence, with worst-case utility depending only on qmin.","keywords":["local differential privacy","private sampling","f-divergence","minimax optimality","public prior","Markov kernel","randomized response","privacy-utility tradeoff"],"falsifier":"Solve the minimax problem in (4) by linear programming for a fixed small q and ε, say q = (0.3, 0.7) with ε = 1, over all ε-LDP Markov kernels K satisfying qK = q; compare the resulting worst-case TV distance with the value in (6). A strict gap would refute Theorem 1, and running Algorithm 1 on a prior with qmin = 0 would expose whether the boundary case is covered.","tokens_in":19397,"feed_emoji":"🎯","tokens_out":10682,"duration_ms":92841,"temperature":0.7,"pith_summary":"This paper asks how a user can release one sample that approximates their private data distribution p while leaving a public prior distribution q untouched, under ε-local differential privacy. The authors prove that the best possible tradeoff over all ε-LDP Markov kernels that preserve q is exactly a value that depends on the prior only through its smallest atom qmin and on the privacy budget ε. They then give a recursive algorithm that constructs a kernel achieving this bound, and show that the same kernel is optimal no matter which f-divergence is used to measure utility. This matters because a public prior is often available—demographics, aggregate click rates, genre preferences—and the paper's experiments indicate that using it can sharply reduce worst-case distortion compared to private sampling without it.","feed_headline":"One private sampler is optimal for every f-divergence","feed_subtitle":"A recursive LDP mechanism preserves public priors and cuts worst-case sampling error using only qmin.","key_machinery":"The central object is an ε-LDP Markov kernel K on the probability simplex that satisfies qK = q, meaning the public prior is a fixed point of the mechanism. The load-bearing identity is Lemma 1: sup_p D_f(p||pK) = max_i D_f(δ_i||δ_i K) = f(0)(1 − Kmin) + Kmin f(1/Kmin), with Kmin = min_i K_ii, which reduces an infinite worst case over all user distributions to a single diagonal entry. A companion bound shows that any ε-LDP kernel preserving q must have K_ii ≤ e^ε q_i/(e^ε q_i + 1 − q_i), hence min_i K_ii ≤ e^ε qmin/(e^ε qmin + 1 − qmin), and equality is achieved by the recursive construction in Algorithm 1. The mechanism is universal across f-divergences because both the reduction and the diagonal bound are independent of f, which enters only through the convex function used to evaluate the divergence.","core_discovery":"For a finitely supported public prior q with qmin > 0, the minimax value over ε-LDP Markov kernels K satisfying qK = q is Γ_f(q,ε) = ((1−qmin)/(e^ε qmin + 1 − qmin)) f(0) + ((e^ε qmin)/(e^ε qmin + 1 − qmin)) f((e^ε qmin + 1 − qmin)/(e^ε qmin)). Algorithm 1 constructs K_q,ε recursively: it sets the first diagonal entry to e^ε qmin/(e^ε qmin + 1 − qmin), fills the first column with qmin/(e^ε qmin + 1 − qmin), recursively builds the lower-right block from the renormalized tail of q scaled by m = 1 − qmin/(e^ε qmin + 1 − qmin), and sets the rest of the first row to q_j/(e^ε qmin + 1 − qmin). The proof hinges on the reduction showing that the worst case over p is attained at a Dirac distribution and equals f(0)(1 − Kmin) + Kmin f(1/Kmin), so only the smallest diagonal entry of K matters. Theorem 2 verifies that the construction is ε-LDP, preserves q, and attains Γ_f(q,ε), making it simultaneously optimal for every f-divergence.","pith_inferences":["Editorial inference: because Γ depends on q only through qmin, an applied user could rebalance or merge the smallest atoms of a raw public prior before invoking Algorithm 1 to obtain a better guarantee; this preprocessing is not discussed in the paper.","Editorial inference: the universality holds within the linear Markov-kernel class; the nonlinear samplers identified in the preceding minimax work are outside the minimization, so whether a nonlinear sampler could beat Γ_f(q, ε) while preserving q remains open.","Editorial inference: nothing in the discrete proof transfers directly to continuous distributions, so a natural next step—quantizing continuous public and private data and tracking the resulting minimax value—is a testable extension rather than a result of this paper.","Editorial inference: the boundary qmin = 0 is silently excluded; checking whether any finite-ε LDP kernel preserving such a prior satisfies the paper's sup-ratio definition would clarify the scope of Theorem 2."],"forward_implications":["One mechanism K_q,ε solves the design problem for every f-divergence, so changing the utility measure from TV distance to KL or another divergence does not require re-optimizing.","With a uniform public prior, the optimal mechanism reduces to the n-ary randomized response mechanism, recovering the no-prior result as a special case.","The worst-case utility is governed only by qmin and ε; priors with a larger smallest atom yield a strictly smaller worst-case divergence.","Algorithm 1 runs in O(n^3) time, versus O(n^5 log(n/δ)) for a naive linear-programming solution of the TV version.","The invariance qK = q means a user whose private distribution equals the public prior suffers no distortion, and users close to the prior are guaranteed small TV error."],"supporting_citations":[{"why":"Supplies the minimax locally private sampling formulation and the linear-sampler setting that this paper extends with a public prior.","marker":"Park et al. (2024)"},{"why":"Defines private samplers and relative mollifiers, and provides the projection baseline used in the experiments.","marker":"Husain et al. (2020)"},{"why":"Introduces the randomized response mechanism shown here to be optimal when the public prior is uniform.","marker":"Warner (1965)"},{"why":"Gives the linear-programming complexity benchmark that Algorithm 1 improves on.","marker":"Cohen et al. (2021)"},{"why":"Introduces local differential privacy, the privacy model the mechanisms must satisfy.","marker":"Kasiviswanathan et al. (2011)"}],"fun_headline_variants":["Universal LDP sampler achieves minimax for all f-divergences","One recursive LDP mechanism optimal for every f-divergence","Public data makes a single LDP sampler minimax-optimal universally","Minimax-optimal LDP sampling for any f-divergence using public data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction assumes the public prior q assigns strictly positive probability to every outcome (qmin > 0), because Algorithm 1 and the formula divide by qmin, and the optimality claim is restricted to linear ε-LDP Markov-kernel samplers rather than all conceivable private samplers.","fun_headline_variants_meta":{"raw":{"variants":["Universal LDP sampler achieves minimax for all f-divergences","One recursive LDP mechanism optimal for every f-divergence","Public data makes a single LDP sampler minimax-optimal universally","Minimax-optimal LDP sampling for any f-divergence using public data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000997,"raw_usage":{"total_tokens":4273,"prompt_tokens":1046,"completion_tokens":3227,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":3149}},"tokens_in":662,"tokens_out":3227,"duration_ms":20954,"temperature":1.0,"reasoning_tokens":3149,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T21:21:13.804628+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve the minimax problem in (4) by linear programming for a fixed small q and ε, say q = (0.3, 0.7) with ε = 1, over all ε-LDP Markov kernels K satisfying qK = q; compare the resulting worst-case TV distance with the value in (6). A strict gap would refute Theorem 1, and running Algorithm 1 on a prior with qmin = 0 would expose whether the boundary case is covered.","supporting_citations":[{"cited_title":"Local differential privacy for sampling","cited_arxiv_id":null,"evidence_quote":"Defines private samplers and relative mollifiers, and provides the projection baseline used in the experiments."},{"cited_title":"Randomized response: A survey technique for eliminating evasive answer bias","cited_arxiv_id":null,"evidence_quote":"Introduces the randomized response mechanism shown here to be optimal when the public prior is uniform."},{"cited_title":"Solving linear programs in the current matrix multiplication time","cited_arxiv_id":null,"evidence_quote":"Gives the linear-programming complexity benchmark that Algorithm 1 improves on."},{"cited_title":"Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith","cited_arxiv_id":null,"evidence_quote":"Introduces local differential privacy, the privacy model the mechanisms must satisfy."}],"review_version":1}