{"id":"6415298f-438b-4346-b139-d0d7c8e9091d","arxiv_id":"2412.10512","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Differentially private algorithms can generate multiple samples from a distribution with sample complexity that improves over repeated single-sampling, including the first pure-DP Gaussian samplers.","lead":"This paper defines private multi-sampling, generating several synthetic samples from a distribution under differential privacy. It provides algorithms that beat the naive baseline by a factor of m in some settings, and the first pure-DP samplers for Gaussians.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 19's Euclidean-Laplace proof is a factor-of-two off: under replacement neighbors, sum sensitivity is 2B, so scale b=B/ε gives 2ε-DP, not ε-DP; the pure-DP Gaussian theorems need rescaling, though rates survive.","rationale":"The reader's weakest assumption is precisely the factor-of-two sensitivity miscalibration in Theorem 19, and my independent check agrees. This is the single most load-bearing issue because Theorem 21—the paper's headline pure-DP Gaussian sampler—rests directly on Algorithm 3's ε-DP claim; if that claim is false, the theorem's privacy guarantee cannot be verified as written. The issue is concrete and quantifiable: with the replacement neighboring relation chosen in §2.2, replacing one clipped vector by another can change the sum by 2B, making the density ratio e^{2ε} at b=B/ε. I also examined whether a more serious gap exists. The zCDP Corollary 23 is indeed under-derived: it invokes the pure-DP reduction of Lemma 11, which is not stated for zCDP and whose DensestBall overhead (Õ(d log d/ε)) would dominate the claimed Õ(√d/ε) rate; this needs a zCDP-compatible reduction. The lower-bound proof of Theorem 30 is sketchy and would need a careful composition analysis. However, these affect secondary results, whereas the sensitivity error sits inside the main pure-DP Gaussian construction. Because the fix is straightforward—halve the noise scale or state the theorems with ε/2—the asymptotic complexity claims are not endangered; the error changes constants only. The correct disposition is therefore the reader's CONDITIONAL, not a rejection. Verdict unchanged.","tokens_in":20770,"tokens_out":32237,"duration_ms":275775,"concrete_test":"Recompute Theorem 19 for the neighboring pair X=(B,0,...,0), X'=(-B,0,...,0), b=B/ε. At y=(B,0,...,0), the Euclidean-Laplace density ratio is FELap(0)/FELap(2B e1) = exp(2B/b) = e^{2ε}, so the mechanism is not ε-DP at scale b=B/ε. Then re-derive Theorems 20–21 with b=2B/ε and verify all stated sample complexities remain Õ(...) up to constants (Theorem 21 still Õ(d^{3/2}/(αε) log(d/α))).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing issue is in the privacy proof of the Euclidean-Laplace mechanism (Theorem 19), which all pure-DP Gaussian single/multi-sampling results inherit. The paper fixes the replacement neighboring relation (Def. 2, §2.2), so neighboring datasets X,X' differ in exactly one user's vector, and each input vector is clipped to have Euclidean norm at most B (Algorithm 3). For such neighbors, the sum query has ℓ2 sensitivity 2B: one vector can move from B to -B. The proof's density-ratio bound max_y FELap(b)(y-S)/FELap(b)(y-S') ≤ exp(ε||S-S'||_2/B) is therefore ≤ e^{2ε} when b=B/ε, not e^ε as claimed. Concretely, d=1, B=1, X=(1), X'=(-1), y=0 gives density ratio exp(2). Thus Theorem 19, and hence Theorem 20 and Theorem 21 (via Lemma 11), are not ε-DP as stated. This is the most load-bearing concern because Theorem 21 is the headline Gaussian result: if the mechanism is only 2ε-DP, the claimed ε-DP guarantee is unsupported. The damage is limited: setting b=2B/ε restores ε-DP, and the tail bound in Lemma 18 and the sample-complexity calculation in Theorem 20 change only by constants, so all asymptotic bounds in Tables 2–3 should survive after rescaling ε. The zCDP corollary and lower-bound proofs have separate gaps, but the sensitivity miscalibration is the immediate obstruction to the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines two notions of differentially private multi-sampling, weak and strong, and studies their sample complexity for k-ary distributions and for Gaussians with known or bounded covariance. For k-ary distributions it gives a pure-DP single-sampler with sample complexity at most k/(αε), an approximate-DP weak multi-sampler based on amplification by shuffling with complexity O(m + k/(αε²)·log(1/δ)), and a strong multi-sampler via a union bound. For Gaussians with known covariance it introduces a Euclidean-Laplace distribution and mechanism, claiming pure-DP single- and multi-sampling with sample complexity Õ(d^{3/2}/(αε)·log(d/α)), and it claims several zCDP results. It also gives a lower bound for strong multi-sampling of k-ary distributions and a lower bound for weak multi-sampling of bounded-covariance Gaussians.","tokens_in":21158,"tokens_out":14506,"duration_ms":129370,"significance":"If the results hold, the paper is a useful contribution: it formalizes multi-sampling, gives the first pure-DP Gaussian single-sampler, improves over the naive repetition baseline for finite domains via shuffling, and provides lower bounds connecting multi-sampling to single-sampling and to learning. The Euclidean-Laplace distribution and its sampling and tail-bound lemmas are of independent interest. The main asymptotic claims are plausible and the finite-domain half of the paper is largely sound. However, the signature Gaussian results currently rest on a factor-of-two privacy gap in the Euclidean-Laplace mechanism, and the zCDP unbounded-mean corollary is not derived by the cited reduction; these are load-bearing and need correction before the claims as stated are supported.","major_comments":[{"comment":"Under the replacement neighboring relation of Definition 2, the sum query in Algorithm 3 has ℓ2 sensitivity 2B, not B: a single clipped vector can change from B to -B. The density-ratio bound in the proof of Theorem 19 is therefore exp(ε||S-S'||_2/B) ≤ exp(2ε) when b = B/ε, so Algorithm 3 is 2ε-DP as written, not ε-DP. Consequently Theorem 20 and Theorem 21 do not establish the claimed ε-DP guarantees. The fix is to set b = 2B/ε (or run the mechanism with privacy parameter ε/2); this changes only constants in Lemma 18 and in the sample-complexity calculations, so the asymptotic bounds in Tables 2 and 3 are expected to survive after rescaling ε.","section":"Section 4.1.1, Theorem 19"},{"comment":"Corollary 23 is not derived by the cited reduction. Lemma 11 is a reduction for (ε,δ)-DP algorithms, while Theorem 22 is only shown to be zCDP, not pure DP; the remark that every pure-DP algorithm is also zCDP does not make a zCDP algorithm eligible for the pure-DP reduction. Moreover, if one used the pure-DP DensestBall variant to extend to unbounded means, the additive Õ(d log d/ε) sample cost in Lemma 11 would dominate the claimed Õ(√d/ε) bound, whereas the approximate-DP variant with Õ(√d log d/ε) does not preserve zCDP. The zCDP unbounded-mean entries in Table 2, and similarly Corollary 34, therefore need a separate proof or a corrected reduction.","section":"Section 4.2, Corollary 23"},{"comment":"The proof of Theorem 30 is a sketch and its sample accounting is not consistent as written. It says the weak sampler uses s private samples from D and then Bie et al.'s learner is fed n* < s of the private samples; if those are the same samples, they cannot also have been consumed by the sampler, and if they are disjoint the total private sample complexity is s + n*, not s. The inequality s < c_l(...)/2 plus n* < s can yield the desired contradiction only after this accounting is made explicit and the constants relating s, n*, and the lower bound are stated. As written, the claimed lower bound is not established.","section":"Section 5.3, Theorem 30"}],"minor_comments":[{"comment":"The theorem statement says M' is an α/√m-sampler, but the proof establishes only that it is a 25α/(7√m)-sampler; the statement should be corrected to an O(α/√m) bound and the constant in Theorem 26 adjusted accordingly.","section":"Section 5.1, Theorem 25"},{"comment":"The phrase 'the same holds for both variants of (m, α)-sampling' is asserted without argument; for strong multi-sampling one should verify that the shift by the DensestBall center preserves the i.i.d. product-distribution guarantee of the bounded-mean sampler.","section":"Appendix A, Lemma 11"},{"comment":"The definition ε0 = ln(f²(ε)n/ln(4/δ) - 1) is not valid for small n because the logarithm's argument can be negative; the proof should state the n regime in which this argument exceeds 1 before invoking the amplification lemma.","section":"Algorithm 2"},{"comment":"The theorem first states 'for any 0 < ε, δ, α < 1' and then gives a separate guarantee 'for ε > 1'; these two regimes should be stated cleanly, since ε > 1 is not covered by the initial quantifier.","section":"Theorem 13"},{"comment":"The zCDP single-sampling entry Õ(√d/ε) for unbounded-mean Gaussians depends on Corollary 23, whose proof is invalid for the reasons in the major comments; the table should be updated once that corollary is repaired.","section":"Table 2"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a genuine factor-of-two privacy bug in the headline pure-DP Gaussian result and an invalid zCDP reduction, but both appear fixable without changing the asymptotic picture, and the finite-domain algorithms are largely sound. I recommend major revision rather than rejection. The lower-bound proof in Theorem 30 also needs to be rewritten with explicit sample accounting before it can be checked. The novelty of the multi-sampling definitions and the Euclidean-Laplace mechanism justifies another round."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the multi-sampling framework is a real contribution, the k-ary results are solid, but the pure-DP Gaussian half has a factor-of-two sensitivity slip that rescales ε, and the zCDP and lower-bound sections are underbaked. It deserves a serious referee, not a desk reject.\n\nWhat's new: strong vs weak multi-sampling is a genuinely useful formalization for synthetic data. The ShuRR weak multi-sampler for k-ary distributions is a clean application of amplification by shuffling, with a concrete improvement over the naive repeat-the-single-sampler baseline. The lower-bound recipe connecting weak multi-sampling to semi-private learning is interesting, and the Euclidean-Laplace distribution with its tail bound and sampling algorithm is fine as a standalone object.\n\nWhere it breaks: Theorem 19. With the replacement neighboring relation and inputs clipped to norm B, the sum query has ℓ2-sensitivity 2B, not B. The density-ratio bound in the theorem is therefore e^{2ε}, not e^ε. Every pure-DP Gaussian theorem inherits this; Theorem 21's ε-DP claim is unsupported as written. This is repairable by setting b=2B/ε, and the asymptotic rates survive after renaming ε to ε/2, but the paper should say so.\n\nAlso, Corollary 23 is not derived. You can't invoke the pure-DP unbounded-mean reduction when the bounded-mean algorithm is zCDP; you need a zCDP composition argument. And Theorem 30's proof ignores the fact that the generated 'public' samples are functions of the private samples, so they are dependent; Bie et al.'s semi-private guarantee presumably assumes independent public data. That's not a fatal flaw at the level of ideas, but it's a gap.\n\nMinor: Theorem 25's statement says α/√m but the proof only shows 25α/(7√m); constants can be absorbed, but the mismatch should be cleaned up.\n\nNet: the Gaussian results are not ready as stated, but the core ideas are plausible and the k-ary half stands alone. I'd send it to review with a strong request to fix the sensitivity calibration and rework the zCDP and lower-bound sections.","headline":"Multi-sampling is a genuinely useful new framework and the k-ary results are solid, but the pure-DP Gaussian headline has a factor-of-two sensitivity error and the zCDP/lower-bound arguments need real work before the claims hold as stated.","tokens_in":21708,"tokens_out":8185,"would_cite":true,"duration_ms":600553,"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":"This paper defines strong and weak private multi-sampling, gives algorithms for finite-domain distributions that save a factor of m, and constructs the first pure-DP samplers for Gaussians with known covariance using a Euclidean-Laplace…","keywords":["differential privacy","multi-sampling","synthetic data","sample complexity","Gaussian distributions","randomized response","shuffling","Euclidean-Laplace mechanism"],"falsifier":"Evaluate the Euclidean-Laplace mechanism's privacy-loss ratio on the two neighboring inputs $X=(0,\\dots,0,v)$ and $X'=(0,\\dots,0,-v)$ with $\\|v\\|_2=B$, and evaluate the output densities at the point that maximizes the ratio; the maximum ratio is $e^{2B/b}=e^{2\\varepsilon}$ for $b=B/\\varepsilon$, which contradicts the $e^\\varepsilon$ bound of Theorem 19.","tokens_in":20546,"feed_emoji":"🔒","tokens_out":12526,"duration_ms":86469,"temperature":0.7,"pith_summary":"This paper asks how many raw samples a differentially private algorithm needs to output $m$ synthetic samples that look like $m$ fresh draws from the same distribution. It introduces two formal notions of multi-sampling—strong, which requires the joint output distribution to be close, and weak, which only requires the marginal to be close—and analyzes their sample complexity for distributions over a finite domain and for Gaussians. The main positive results show that private multi-sampling is cheaper than private distribution learning, and that in the finite-domain case the cost of the $m$-th extra sample can be made small instead of multiplicative. For Gaussians with known covariance, the paper gives the first pure-differential-privacy single- and multi-samplers, based on a new Euclidean-Laplace noise mechanism. If these bounds hold, generating synthetic data under privacy can be done with sample sizes close to those needed for a single synthetic sample.","feed_headline":"Private multi-sampling beats repeating single-sampling","feed_subtitle":"Finite-domain multi-sampling saves a factor of m in samples; Gaussians gain their first pure-DP samplers.","key_machinery":"The argument is carried by three devices. First, the strong/weak multi-sampling definitions let the paper state exactly what it means for a private algorithm to output samples that are close to $m$ fresh draws, and separate the joint-distance requirement from the marginal one. Second, a Euclidean-Laplace distribution on $\\mathbb{R}^d$ with density proportional to $\\exp(-\\|\\eta\\|_2/b)$ serves as noise for sums of vectors with bounded Euclidean norm; this is the mechanism that extends Gaussian single-sampling from approximate DP to pure DP. Third, amplification-by-subsampling powers the $k$-ary single-sampler while amplification-by-shuffling powers the weak multi-sampler, and a reduction (Lemma 11) removes the bounded-mean assumption on Gaussians by first locating a dense ball with a private clustering step. The lower bounds use a tensorization inequality for total variation and a generic semi-private recipe that feeds generated samples as public data into a known learning algorithm.","core_discovery":"On the paper's own terms, the central claim is that differentially private multi-sampling is a distinct, quantifiable task that is easier than private learning, and that its sample complexity can be sharply characterized. For distributions over $[k]$, the paper proves an $\\varepsilon$-DP single-sampler with sample complexity $O\\left(\\frac{k}{\\alpha\\varepsilon}\\right)$ (Theorem 12), an $(\\varepsilon,\\delta)$-DP weak multi-sampler with $O\\left(m + \\frac{k}{\\alpha\\varepsilon^2}\\log\\frac{1}{\\delta}\\right)$ (Theorem 13), and a strong multi-sampler with $O\\left(\\frac{mk}{\\alpha\\varepsilon^2}\\log\\frac{1}{\\delta}\\right)$ (Theorem 16). It also proves that any strong $(m,\\alpha)$-sampler implies an $\\alpha/\\sqrt{m}$-single-sampler (Theorem 25), yielding an $\\Omega\\left(\\sqrt{m}\\cdot\\frac{k}{\\alpha\\varepsilon}\\right)$ lower bound for strong multi-sampling (Theorem 26). For Gaussians with known covariance, the paper exhibits the first pure-DP single-sampler, with sample complexity $\\tilde{O}\\left(\\frac{d^{3/2}}{\\alpha\\varepsilon}\\log\\frac{d}{\\alpha}\\right)$ for unbounded mean (Theorem 21), and shows that an existing approximate-DP Gaussian sampler actually satisfies zCDP (Theorem 22). A lower bound for weak multi-sampling of bounded-covariance Gaussians, $\\tilde{\\Omega}\\left(\\frac{d^2}{\\alpha^2} + \\frac{d^2}{\\alpha\\varepsilon} + \\frac{1}{\\varepsilon}\\sqrt{\\log\\kappa}\\right)$ when $m > d$, is obtained by turning generated samples into public data for a semi-private learner (Theorem 30).","pith_inferences":["The pure-DP Gaussian results will likely survive a sensitivity correction with $\\varepsilon$ replaced by $2\\varepsilon$, because the asymptotic sample-complexity bounds are unchanged.","The weak/strong taxonomy suggests a spectrum of intermediate multi-sampling guarantees, such as bounding the R\\'enyi divergence of the joint output distribution, which would interpolate between the strong and weak bounds.","The finite-domain shuffling trick might be portable to Gaussians via local additive-noise amplification, which would close the open $m$-factor gap the paper leaves.","A practical implication is that these sample-complexity bounds directly inform how many records a DP synthetic-data pipeline must collect to support $m$ released samples, independent of any downstream analysis."],"forward_implications":["For finite-domain distributions under approximate DP, generating $m$ synthetic samples adds only $O(m)$ to the sample complexity, so the marginal cost of a new sample drops as $m$ grows.","Strong multi-sampling is genuinely harder than weak multi-sampling: the $\\Omega(\\sqrt{m}\\,k/(\\alpha\\varepsilon))$ lower bound for $k$-ary distributions shows that requiring the joint output to be close costs a real factor.","The Euclidean-Laplace mechanism provides a pure-DP way to answer $\\ell_2$-sensitive vector-sum queries, which is the step that carries Gaussian sampling from approximate DP to pure DP.","Because the Gaussian single-sampler's complexity depends only logarithmically on $1/\\alpha$, strong multi-sampling of Gaussians inherits only one factor of $m$, not $m^2$ (Remark 17).","The lower bound for bounded-covariance Gaussians shows that weak multi-sampling with $m > d$ forces a superlinear-in-$d$ sample complexity, so generated samples cannot be used as free public data to circumvent known learning lower bounds."],"supporting_citations":[{"why":"Defines single-sampling, provides the baseline algorithm, and gives the $\\Omega(k/(\\alpha\\varepsilon))$ lower bound that the new $k$-ary single-sampler improves in leading constant.","marker":"Raskhodnikova et al. (2021)"},{"why":"Supplies the approximate-DP Gaussian single-sampler that the paper extends to pure DP and re-analyzes under zCDP.","marker":"Ghazi et al. (2023)"},{"why":"Provides the amplification-by-shuffling bound for randomized response that gives the weak multi-sampler its privacy guarantee.","marker":"Feldman et al. (2021)"},{"why":"DensestBall algorithm used in Lemma 11 to reduce unbounded-mean Gaussians to bounded-mean Gaussians.","marker":"Ghazi et al. (2020)"},{"why":"Tensorization inequality for total variation that yields the strong multi-sampling lower bound.","marker":"Kontorovich (2024)"},{"why":"Lower bound for private learning of bounded Gaussians used in the weak multi-sampling lower bound.","marker":"Kamath et al. (2019)"},{"why":"Semi-private learning algorithm for Gaussians that consumes public samples, used in the lower-bound recipe.","marker":"Bie et al. (2022)"}],"fun_headline_variants":["Private multi-sampling: get m samples at less than m× cost","Pure DP Gaussian sampling: first practical algorithm","Multi-sampling beats m independent private runs","Save a factor of m in private multi-sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The pure-DP Gaussian upper bounds rest on the claim that the Euclidean-Laplace mechanism with scale $b=B/\\varepsilon$ is $\\varepsilon$-DP for a sum of input vectors each of norm at most $B$; because replacing one user's vector can move the sum by up to $2B$, that claim is not supported by the paper's own density-ratio calculation as written.","fun_headline_variants_meta":{"raw":{"variants":["Private multi-sampling: get m samples at less than m× cost","Pure DP Gaussian sampling: first practical algorithm","Multi-sampling beats m independent private runs","Save a factor of m in private multi-sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000985,"raw_usage":{"total_tokens":4328,"prompt_tokens":1247,"completion_tokens":3081,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":863,"completion_tokens_details":{"reasoning_tokens":3018}},"tokens_in":863,"tokens_out":3081,"duration_ms":23090,"temperature":1.0,"reasoning_tokens":3018,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:56:48.167228+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate the Euclidean-Laplace mechanism's privacy-loss ratio on the two neighboring inputs $X=(0,\\dots,0,v)$ and $X'=(0,\\dots,0,-v)$ with $\\|v\\|_2=B$, and evaluate the output densities at the point that maximizes the ratio; the maximum ratio is $e^{2B/b}=e^{2\\varepsilon}$ for $b=B/\\varepsilon$, which contradicts the $e^\\varepsilon$ bound of Theorem 19.","supporting_citations":[{"cited_title":"Smith, and Marika Swanberg","cited_arxiv_id":null,"evidence_quote":"Defines single-sampling, provides the baseline algorithm, and gives the $\\Omega(k/(\\alpha\\varepsilon))$ lower bound that the new $k$-ary single-sampler improves in leading constant."},{"cited_title":"On differentially private sampling from gaussian and product distributions","cited_arxiv_id":null,"evidence_quote":"Supplies the approximate-DP Gaussian single-sampler that the paper extends to pure DP and re-analyzes under zCDP."},{"cited_title":"Differentially private clustering: Tight approximation ratios","cited_arxiv_id":null,"evidence_quote":"DensestBall algorithm used in Lemma 11 to reduce unbounded-mean Gaussians to bounded-mean Gaussians."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Lower bound for private learning of bounded Gaussians used in the weak multi-sampling lower bound."},{"cited_title":"Private estimation with public data","cited_arxiv_id":null,"evidence_quote":"Semi-private learning algorithm for Gaussians that consumes public samples, used in the lower-bound recipe."}],"review_version":1}