Pith. sign in

REVIEW 2 major objections 4 minor 21 references

Gaussian Differential Private Bootstrap by Subsampling

T0 review · 2 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A private m-out-of-n bootstrap can build asymptotically valid confidence intervals at the same Gaussian-DP level as the n-out-of-n bootstrap while adding less noise per iteration.

desk verdict Useful m-out-of-n private bootstrap idea, but Equation (13) inverts the key scaling and Theorem 3.2 overstates the allowed m; both are fixable. read the letter →

arxiv 2505.01197 v1 pith:J5Y27O5H submitted 2025-05-02 stat.ML cs.LGmath.STstat.COstat.TH

Holger Dette , Carina Graw This is my paper · ORCID
classification stat.MLcs.LGmath.STstat.COstat.TH MSC 62F40
keywords differentialprivacyGaussianf-differentialbootstrapm-out-of-nsubsamplingamplificationconfidenceintervals
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Drawing bootstrap samples of size $m

What carries the argument

The engine of the construction is the $B$-fold composition of privacy guarantees for one bootstrap estimator, analysed with the CLT for trade-off functions. For a single m-out-of-n draw, the target record is absent with probability $p_0=(1-1/n)^m$, in which case the bootstrap estimator is perfectly private, and it is included $i$ times with probability $p_{m,i}=\binom{m}{i}(1/n)^i(1-1/n)^{m-i}$, in which case the Gaussian mechanism is $i\mu^*_B$-GDP by group privacy. The resulting single-iteration trade-off function is $f_{B,b}^{\mathrm{boot}}=C_{1-p_0}(\mathrm{mix}((p_{m,1}/(1-p_0),\ldots,p_{m,m}/(1-p_0)),(G_{\mu^*_B},G_{2\mu^*_B},\ldots,G_{m\mu^*_B})))$, where $G_\mu$ is the trade-off function of $N(0,1)$ versus $N(\mu,1)$. The load-bearing identity is the limit $\lim_{B\to\infty}\mu^*_B\sqrt{B(1-(1-1/n)^m)\frac{m}{n}(1+\frac{m-1}{n})}=\mu$, which makes the $B$-fold composition converge to $G_\mu$ in the trade-off-function CLT, and the paper chooses the noise variance $\sigma^2_{m,B}=B(1-(1-1/n)^m)\frac{n+m-1}{n}\frac{\ell^2}{mn\mu^2}$ so that this is the condition the proof needs. As printed, however, equation (13) states the reciprocal of the sequence that satisfies this identity, so the noise schedule actually implemented in Algorithm 2 does not meet the theorem's hypothesis.

What would settle it

Compute the left-hand side of the limit in Remark 3.1(1) with the $\mu^*_B$ printed in (13): for fixed $n,m$ it equals $\mu^2\left(B(1-(1-1/n)^m)\frac{m}{n}(1+\frac{m-1}{n})\right)^2$, which diverges as $B\to\infty$ instead of converging to $\mu^2$. A numerical counterpart is to fix $n,m$, run Algorithm 2 as printed on two neighboring databases for increasing $B$, and estimate the trade-off function; the estimated trade-off function should move toward greater distinguishability as $B$ grows, rather than settling at $G_\mu$.

Watch

Extended reading notes

Core claim

The paper's central assertion is Corollary 3.1: whenever the non-private m-out-of-n bootstrap is consistent, $m=O(n)$, the limiting distribution of $\sqrt{n}(\hat\theta_n-\theta)$ is continuous, the estimator's sensitivity is $O(1/n)$, and $B=O(n)$ with $B\to\infty$, the interval $C_{m,n}(\alpha)=[\bar\theta_n-q^*_{1-\alpha}/\sqrt{n},\bar\theta_n-q^*_{\alpha}/\sqrt{n}]$ computed by Algorithm 2 is asymptotically $\sqrt{2}\mu$-GDP and has asymptotic coverage $1-2\alpha$, where $q^*_{\alpha}$ is the empirical quantile of the privatized bootstrap sample. The privacy guarantee is argued through Theorem 3.1, which composes the $B$ privatized bootstrap estimators and shows the composition converges to the Gaussian trade-off function $G_\mu$ as $B\to\infty$. The statistical guarantee rests on the observation that the extra Gaussian noise in $\bar\theta_n$ and in each bootstrap draw vanishes in probability under the $O(1/n)$ sensitivity condition, so the privatization does not change the limit distribution. The interval therefore improves on the n-out-of-n bootstrap in two ways at once: each bootstrap draw is cheaper because $m$ can be much smaller than $n$, and each draw needs less privacy noise because a record is typically absent from a small subsample.

Load-bearing premise

The privacy argument collapses unless the per-bootstrap privacy parameter follows the scaling limit in Remark 3.1(1); equation (13) as printed multiplies by $\sqrt{B(1-(1-1/n)^m)\frac{m}{n}(1+\frac{m-1}{n})}$ where the proof requires division by it, so the noise schedule actually used in Algorithm 2 does not satisfy the theorem's hypothesis.

Editorial extensions

If this is right

  • If the claims hold, differentially private confidence intervals can be run with many more bootstrap replications at a fixed privacy budget, because choosing $m$ near $n/B$ keeps the per-iteration noise at the level of the asymptotic-normal Gaussian-mechanism interval.
  • The rule of thumb $m\approx n/B$ makes the second-order length of the private bootstrap interval equal to the second-order length of a confidence interval based on the asymptotic normal approximation, matching a target that the n-out-of-n bootstrap overshoots.
  • Estimators with sensitivity $O(1/n)$ whose non-private m-out-of-n bootstrap is consistent inherit the coverage guarantee without parametric model assumptions, covering means and regularized empirical-risk minimizers in the settings studied.
  • The simulation results in Section 4 report coverage near the nominal 90% level with intervals roughly an order of magnitude shorter and runtimes much lower than the n-out-of-n bootstrap and BLBQuant for $n=500$ to $5000$ and $\mu=0.5,1$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same subsampling-amplified composition argument should generalize to privacy mechanisms other than the Gaussian mechanism, as long as the single-iteration trade-off functions satisfy the CLT conditions; a natural stress test is Laplace or Student-t noise.
  • The m-out-of-n bootstrap could be combined with the deconvolution step used for the n-out-of-n bootstrap; the paper deliberately omits it, but at larger $m$ the residual noise may make deconvolution worthwhile.
  • A cost-aware optimal choice of $m$ could be derived by balancing the privacy-noise term against the bootstrap approximation error under a fixed total compute budget $B\cdot c(m)$; the paper balances them under the length criterion (17) but not under a full cost criterion.
  • Because the consistency condition (16) fails for some statistics, the interesting boundary case is the private m-out-of-n bootstrap for statistics with non-normal limits; Theorem 3.2 assumes only a continuous limiting distribution, not normality, so the boundary case is a direct test of how far the method extends.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes a differentially private m-out-of-n empirical bootstrap under Gaussian Differential Privacy (GDP). The main algorithmic object is Algorithm 2, which privatizes each bootstrap estimator with Gaussian noise whose variance is calibrated through a per-bootstrap privacy parameter mu_star_B. The paper claims that the resulting interval C_{m,n}(alpha) is asymptotically sqrt(2)mu-GDP and has asymptotic coverage 1-2alpha whenever the non-private m-out-of-n bootstrap is consistent, m=O(n), B=O(n), B -> infinity, and the estimator sensitivity is O(1/n). It further claims improvements over the n-out-of-n bootstrap of Wang et al. (2022) in terms of noise, computation, and finite-sample coverage, and supports this with simulations for a truncated normal mean and regularized logistic regression.

Significance. If made correct, the proposed construction would be a useful practical contribution: it gives a privacy accounting for the m-out-of-n bootstrap based on established f-DP composition results, provides a simple rule of thumb for choosing m, and demonstrates substantial computational savings over existing private bootstrap procedures. The paper's reliance on external composition and CLT theorems (Dong et al. 2022; Wang et al. 2022) is appropriate and not circular. However, as written, the central privacy statement is undermined by an inconsistency in the definition of mu_star_B, and the consistency theorem is stated under assumptions that do not ensure its proof's key step. These issues are fixable but currently block acceptance.

major comments (2)
  1. [Section 3, Eqs. (12)-(13), Algorithm 2, and Remark 3.1(1)] There is a load-bearing inversion in the definition of mu_star_B. Algorithm 2 draws Y_b with variance Delta_theta(m)^2 / mu_star_B^2. For this variance to equal sigma^2_{m,B} in Eq. (12), mu_star_B must be mu divided by sqrt{B(1-p0)(m/n)(1+(m-1)/n)}. Equation (13) instead prints mu times that square root. The proof in Appendix B.1 and Remark 3.1(1) both require the reciprocal limiting condition lim_{B->infinity} mu_star_B^2 B (1-p0) (m/n) (1+(m-1)/n) = mu^2. With Eq. (13) as printed, that product diverges for fixed n and m, so Theorem 3.1 and Corollary 3.1 are unsupported and Algorithm 2 adds far too little bootstrap noise. The notation B(m,n) is also used inconsistently between Eqs. (12) and (13). Please correct Eq. (13) and the definition in Algorithm 2, align Eq. (12), and state explicitly whether the simulations were run with the corrected scaling.
  2. [Appendix B.2 / Theorem 3.2] The proof of Theorem 3.2 asserts that sqrt(m)Y converges to zero in probability 'by the assumption on the sensitivity, on B and on m', but this is not implied by Delta=O(1/n), m=O(n), and B=O(n). With the corrected mu_star_B, Var(sqrt(m)Y) equals (l^2/mu^2) (B/n) (1-p0) (1+(m-1)/n). For m=n and B=n, this converges to 2(1-e^{-1}) l^2/mu^2 > 0, so the privatized bootstrap distribution does not converge to the non-private one and the claimed coverage can fail. The rule of thumb (17), which gives m approximately n/B, does satisfy the needed condition B(1-p0)(1+(m-1)/n)=o(n), but that condition should be stated as an assumption in Theorem 3.2 (e.g., m=o(n), or the displayed o(n) condition) so that the theorem holds as stated.
minor comments (4)
  1. [Section 3, before Algorithm 2] The text says the interval 'preserves (for large B) 2µ-GDP'; this should be sqrt(2)µ-GDP, or the total privacy guarantee should be stated precisely for the split-budget construction used in the simulations.
  2. [Section 3, 'Choice of m and B'] In the length table, the second-order term for the m-out-of-n bootstrap omits the factor (1+(m-1)/n) that appears in sigma^2_{m,B}; this is harmless for m=o(n), but the table should state that it is an approximation.
  3. [Throughout] There are numerous typos and grammatical slips, including 'avoidng', 'the the', 'different', 'm out or n bootstrap', and 'standard derivation' for 'standard deviation'; these should be corrected.
  4. [Section 4.1] The simulation section should clarify the privacy-budget accounting: the estimator is mu/sqrt(2)-GDP and the bootstrap is mu/sqrt(2)-GDP, so the whole procedure is mu-GDP, whereas Corollary 3.1 states sqrt(2)mu-GDP for the unsplit budget.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the privacy and consistency arguments rest on external composition/CLT results, and algorithm parameters are chosen analytically rather than fitted to the target claims.

full rationale

The central derivation is self-contained and built on external results, not on the paper's own outputs. Theorem 3.1 applies Dong et al. (2022) Theorem B.1 (the f-DP CLT) and Wang et al. (2022) Theorem B.2/Lemma 29 to the mixture-of-tradeoff-functions representation of one m-out-of-n bootstrap estimator. The limiting privacy level is computed from the B-fold composition, and the paper does not cite its own prior work; Dette and Graw have no self-citations, so no self-citation chain loads the argument. The parameter mu_star_B in Eq. (13) is a mechanism design choice: it is the per-bootstrap privacy parameter that the CLT condition in the proof of Theorem 3.1 requires (with the printed value apparently being the reciprocal of the required scaling, which is a correctness/typographical risk, not a circular reduction). The consistency theorem explicitly assumes the non-private m-out-of-n bootstrap is consistent and then shows the private version inherits that property by controlling the added noise, so it does not assume the conclusion. The rule of thumb for m, Eq. (17), is derived from the CI length expansion rather than fitted to simulations, and the simulation study is a finite-sample evaluation, not an input to the proof. No fitted parameter is renamed as a prediction, and no uniqueness or ansatz is imported from the authors' own prior work. Accordingly, there is no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on four assumptions: the known 1/n sensitivity scaling, the non-private m-out-of-n bootstrap consistency condition, the external GDP composition and subsampling CLT theorems, and a corrected reciprocal definition for mu_star_B. No data-driven parameters are fitted; B and m are chosen by an analytic rule of thumb rather than by fitting to simulation outcomes. No new entities are postulated.

assumptions (5)
  • domain assumption The statistic theta has sensitivity Delta_theta(n) = l/n for some constant l > 0 on datasets of size n, and hence Delta_theta(m) = l/m on bootstrap samples.
    Invoked before equation (9) to calibrate Gaussian noise; if sensitivity decays slower than 1/n, the added noise does not vanish and Theorem 3.2's consistency fails.
  • domain assumption The non-private m-out-of-n bootstrap is consistent in sup norm, condition (16).
    Assumed in Theorem 3.2; it holds for many statistics but is not proven for the classes covered here.
  • standard math The f-DP composition CLT (Theorem B.1 of Dong et al. 2022) and the subsampling mixture theorem (Theorem 8 of Wang et al. 2022) apply, including the kl, kappa2, kappa3 conditions and the C_{1-p0} convex-conjugate operation.
    Used in Appendix B.1 to prove Theorem 3.1; the paper quotes these external results rather than reproving them.
  • ad hoc to paper The per-bootstrap privacy budget mu_star_B must satisfy the reciprocal scaling mu_star_B = mu / sqrt(B(1-p0)((n+m-1)/n)(m/n)) for the privacy proof to work.
    Needed to reconcile equation (12), Algorithm 2, and the proof's assumption; the printed equation (13) gives the reciprocal of this, so this corrected scaling is load-bearing.
  • domain assumption The growth conditions m = O(n), B = O(n), B goes to infinity, and continuity of the limiting distribution in Theorem 3.2.
    Standard growth conditions for bootstrap consistency; the manuscript does not prove they hold for the rule of thumb (17) in all simulation scenarios.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Gaussian Differential Private Bootstrap by Subsampling." pith.science (2026). https://pith.science/paper/J5Y27O5H

@misc{pith2026250501197,
  author       = {Pith},
  title        = {Pith review of: Gaussian Differential Private Bootstrap by Subsampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J5Y27O5H}},
  note         = {Machine review of arXiv:2505.01197}
}
abstract

Bootstrap is a common tool for quantifying uncertainty in data analysis. However, besides additional computational costs in the application of the bootstrap on massive data, a challenging problem in bootstrap based inference under Differential Privacy consists in the fact that it requires repeated access to the data. As a consequence, bootstrap based differentially private inference requires a significant increase of the privacy budget, which on the other hand comes with a substantial loss in statistical accuracy. A potential solution to reconcile the conflicting goals of statistical accuracy and privacy is to analyze the data under parametric model assumptions and in the last decade, several parametric bootstrap methods for inference under privacy have been investigated. However, uncertainty quantification by parametric bootstrap is only valid if the the quantities of interest can be identified as the parameters of a statistical model and the imposed model assumptions are (at least approximately) satisfied. An alternative to parametric methods is the empirical bootstrap that is a widely used tool for non-parametric inference and well studied in the non-private regime. However, under privacy, less insight is available. In this paper, we propose a private empirical $m$ out of $n$ bootstrap and validate its consistency and privacy guarantees under Gaussian Differential Privacy. Compared to the the private $n$ out of $n$ bootstrap, our approach has several advantages. First, it comes with less computational costs, in particular for massive data. Second, the proposed procedure needs less additional noise in the bootstrap iterations, which leads to an improved statistical accuracy while asymptotically guaranteeing the same level of privacy. Third, we demonstrate much better finite sample properties compared to the currently available procedures.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 14 canonical work pages

  1. [1]

    Abowd, J. M. (2018). The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining , pages 2867--2867

    2018

  2. [2]

    and Wang, Z

    Awan, J. and Wang, Z. (2023). Simulation-based, finite-sample inference for privatized data. arXiv preprint arXiv:2303.05328

    arXiv 2023

  3. [3]

    Balle, B., Barthe, G., and Gaboardi, M. (2018). Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems , 31

    work page 2018

  4. [4]

    J., Götze, F., and van Zwet, W

    Bickel, P. J., Götze, F., and van Zwet, W. R. (1997). Resampling fewer than n observations: Gains, losses, and remedies for losses. Statistica Sinica , 7(1):1--31

    work page 1997

  5. [5]

    and Honaker, J

    Brawner, T. and Honaker, J. (2018). Bootstrap inference and differential privacy: Standard errors for free. Unpublished Manuscript

    work page 2018

  6. [6]

    Chadha, K., Duchi, J., and Kuditipudi, R. (2024). Resampling methods for private statistical inference. arXiv preprint arXiv:2402.07131

    arXiv 2024

  7. [7]

    Ding, B., Kulkarni, J., and Yekhanin, S. (2017). Collecting telemetry data privately. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems , volume 30. Curran Associates, Inc

    work page 2017

  8. [8]

    Dong, J., Roth, A., and Su, W. J. (2022). Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology , 84(1):3--37

    2022

Show all 21 references
  1. [9]

    Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006). Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3 , pages 265--284. Springer

    2006

  2. [10]

    Eshun, S. N. and Palmieri, P. (2022). Two de-anonymization attacks on real-world location data based on a hidden markov model. In 2022 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW) , pages 01--09. IEEE

    2022

  3. [11]

    Ferrando, C., Wang, S., and Sheldon, D. (2022). Parametric bootstrap for differentially private confidence intervals. In International Conference on Artificial Intelligence and Statistics , pages 1598--1618. PMLR

    2022

  4. [12]

    Gambs, S., Killijian, M.-O., and del Prado Cortez, M. N. (2014). De-anonymization attack on geolocated data. Journal of Computer and System Sciences , 80(8):1597--1614

    2014

  5. [13]

    Koga, T., Meehan, C., and Chaudhuri, K. (2022). Privacy amplification by subsampling in time domain. In International Conference on Artificial Intelligence and Statistics , pages 4055--4069. PMLR

    2022

  6. [14]

    and Shmatikov, V

    Narayanan, A. and Shmatikov, V. (2006). How to break anonymity of the netflix prize dataset. arXiv preprint cs/0610105

    2006 arXiv

  7. [15]

    Politis, D. N. and Romano, J. P. (1994). Large sample confidence regions based on subsamples under minimal assumptions. The Annals of Statistics , pages 2031--2050

    1994

  8. [16]

    Wang, T., Zhang, X., Feng, J., and Yang, X. (2020). A comprehensive survey on local differential privacy toward data statistics and analysis. Sensors , 20(24):7030

    2020

  9. [17]

    and Awan, J

    Wang, Z. and Awan, J. (2023). Debiased parametric bootstrap inference on privatized data. TPDP 2023 - Theory and Practice of Differential Privacy

    2023

  10. [18]

    Wang, Z., Cheng, G., and Awan, J. (2022). Differentially private bootstrap: New privacy analysis and inference strategies. arXiv preprint arXiv:2210.06140

    2022

  11. [19]

    and Zhou, S

    Wasserman, L. and Zhou, S. (2010). A statistical framework for differential privacy. Journal of the American Statistical Association , 105(489):375--389

    2010

  12. [20]

    Xiong, X., Liu, S., Li, D., Cai, Z., and Niu, X. (2020). A comprehensive survey on local differential privacy. Security and Communication Networks , 2020:1--29

    2020

  13. [21]

    Yang, M., Guo, T., Zhu, T., Tjuawinata, I., Zhao, J., and Lam, K.-Y. (2023). Local differential privacy and its applications: A comprehensive survey. Computer Standards & Interfaces , page 103827

    2023

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.