REVIEW 3 major objections 5 minor 15 references
Differentially Private Multi-Sampling from Distributions
T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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).
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 4.1.1, Theorem 19] 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 4.2, Corollary 23] 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 5.3, Theorem 30] 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.
minor comments (5)
- [Section 5.1, Theorem 25] 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.
- [Appendix A, Lemma 11] 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.
- [Algorithm 2] 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.
- [Theorem 13] 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.
- [Table 2] 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.
Circularity Check
No circularity: every load-bearing step is either proved in-place or rests on external prior work; no fitted parameter is renamed as a prediction.
full rationale
The paper is not circular. The primary algorithmic claims are proved in-place from the randomizer definitions and from external prior analyses. Theorems 12, 13 and 16 give explicit privacy and accuracy derivations: privacy follows from randomized response and the Feldman et al. (2021) amplification-by-shuffling lemma, while accuracy is an explicit mixture-weight calculation; no quantity is fitted to data and then reported as a prediction. The Gaussian upper bounds introduce the Euclidean-Laplace mechanism and prove its density is normalized (Lemma 35), that it can be sampled (Lemma 36), and that its norm tail is bounded (Lemma 18); the DP proof (Theorem 19) is the paper's own argument. The accuracy proof of Theorem 20 compares to Ghazi et al. (2023, Theorem 4.2), an external published benchmark, and the unbounded-mean reduction (Lemma 11) is attributed to Ghazi et al. (2020/2023) with a proof sketch in Appendix A; neither is a self-citation. The zCDP and lower-bound sections rely on Ghazi et al., Kamath et al., Bie et al., Raskhodnikova et al. and Kontorovich, all external. The reference list contains no self-citation. The honest limitations (Section 1.2, Remark 15) are structural open questions, not circular moves. The only load-bearing weakness is a correctness gap in Theorem 19: under the replacement neighboring relation adopted in Section 2.2, the clipped sum has l2 sensitivity 2B, so the proof's bound exp(eps*||S-S'||_2/B) establishes 2eps-DP rather than eps-DP at b=B/eps; rescaling b=2B/eps repairs it with only constant-factor changes to the rates. That is a proof error, not a circular reduction, and is therefore not scored as circularity.
Assumptions & free parameters
free parameters (4)
- Clipping radius B in Algorithm 4 =
R + c·√d·log(1/α)
- Euclidean-Laplace scale b in Algorithm 3 =
B/ε
- ShuRR noise parameter ε0 =
ln(f²(ε)·n/ln(4/δ) − 1)
- Gaussian noise parameters σ² in zCDP analyses =
(n−1)/n (Alg. 1) and α/(4√d) (Alg. 8)
assumptions (5)
- domain assumption Amplification-by-shuffling bound for randomized response (Feldman et al. 2021, Lemma 14)
- domain assumption DensestBall algorithm guarantee (Ghazi et al. 2020, Theorem 6)
- domain assumption Tensorization of variational distance (Kontorovich 2024, Theorem 24)
- domain assumption Single-sampling lower bound for k-ary distributions (Raskhodnikova et al. 2021)
- domain assumption zCDP learning lower bound (Kamath et al. 2019) and semi-private learning upper bound (Bie et al. 2022)
invented entities (1)
-
Euclidean-Laplace distribution ELap(b)
independent evidence
Cite this review
Pith. "Pith review of Differentially Private Multi-Sampling from Distributions." pith.science (2026). https://pith.science/paper/5NMLFOAF
@misc{pith2026241210512,
author = {Pith},
title = {Pith review of: Differentially Private Multi-Sampling from Distributions},
year = {2026},
howpublished = {\url{https://pith.science/paper/5NMLFOAF}},
note = {Machine review of arXiv:2412.10512}
}
abstract
Many algorithms have been developed to estimate probability distributions subject to differential privacy (DP): such an algorithm takes as input independent samples from a distribution and estimates the density function in a way that is insensitive to any one sample. A recent line of work, initiated by Raskhodnikova et al. (Neurips '21), explores a weaker objective: a differentially private algorithm that approximates a single sample from the distribution. Raskhodnikova et al. studied the sample complexity of DP \emph{single-sampling} i.e., the minimum number of samples needed to perform this task. They showed that the sample complexity of DP single-sampling is less than the sample complexity of DP learning for certain distribution classes. We define two variants of \emph{multi-sampling}, where the goal is to privately approximate $m>1$ samples. This better models the realistic scenario where synthetic data is needed for exploratory data analysis. A baseline solution to \emph{multi-sampling} is to invoke a single-sampling algorithm $m$ times on independently drawn datasets of samples. When the data comes from a finite domain, we improve over the baseline by a factor of $m$ in the sample complexity. When the data comes from a Gaussian, Ghazi et al. (Neurips '23) show that \emph{single-sampling} can be performed under approximate differential privacy; we show it is possible to \emph{single- and multi-sample Gaussians with known covariance subject to pure DP}. Our solution uses a variant of the Laplace mechanism that is of independent interest. We also give sample complexity lower bounds, one for strong multi-sampling of finite distributions and another for weak multi-sampling of bounded-covariance Gaussians.
Reference graph
Works this paper leans on
-
[1]
Private learning and sanitization: Pure vs
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and Jos \' e D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th I...
2013
-
[2]
Private estimation with public data
Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022,...
work page 2022
-
[3]
Simultaneous private learning of multiple concepts
Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016 , pages 369--380. ACM , 2016. doi:10.1145/2840728.2840747. URL https://doi.org/10.1145/2840728.2840747
arXiv 2016
-
[4]
Differential privacy and robust statistics
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 , pages 371--380. ACM , 2009. doi:10.1145/1536414.1536466. URL https://doi.org/10.1145/1536414.1536466
arXiv 2009
-
[5]
The algorithmic foundations of differential privacy
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9 0 (3-4): 0 211--407, 2014. doi:10.1561/0400000042. URL https://doi.org/10.1561/0400000042
-
[6]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings , volume 3876 of Lecture Notes in Computer Science, pages 265--284. Spri...
doi:10.1007/11681878 2006
-
[7]
Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 954--964. IEEE , 2021. doi:10.1109/FOCS52979.2021.00096. URL https://doi.org/10.1109...
arXiv 2021
-
[8]
Differentially private clustering: Tight approximation ratios
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria - Florina Balcan, and Hsuan - Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, Dec...
work page 2020
Show all 15 references
-
[9]
On differentially private sampling from gaussian and product distributions
Badih Ghazi, Xiao Hu, Ravi Kumar, and Pasin Manurangsi. On differentially private sampling from gaussian and product distributions. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Sy...
2023
-
[10]
Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high-dimensional distributions. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA , volume 99 of Proceedings of Machine ...
2019
-
[11]
Gautam Kamath, Vikrant Singhal, and Jonathan R. Ullman. Private mean estimation of heavy-tailed distributions. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria] , volume 125 of Proceeding...
2020
-
[12]
Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA , volume 94 of LIPIcs, pages 44:1--44:9. Schl...
2018 doi
-
[13]
On the tensorization of the variational distance, 2024
Aryeh Kontorovich. On the tensorization of the variational distance, 2024. URL https://arxiv.org/abs/2409.10368
2024 arXiv
-
[14]
Smith, and Marika Swanberg
Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, and Marika Swanberg. Differentially private sampling from distributions. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Proce...
2021
-
[15]
Randomized response: A survey technique for eliminating evasive answer bias
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60 0 (309): 0 63--69, 1965
1965
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.