{"id":"ab8f7ce8-f1af-4f1b-a1ec-8da7da9656aa","arxiv_id":"2505.01197","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A private m-out-of-n bootstrap under Gaussian Differential Privacy gives asymptotically valid confidence intervals with less added noise and lower computation than the existing n-out-of-n private bootstrap.","lead":"This paper proposes a differentially private way to run the empirical bootstrap: draw small subsamples of size m instead of full-size resamples, then add less noise while keeping the same asymptotic privacy guarantee. The method is faster and gives shorter confidence intervals in simulations than the existing n-out-of-n private bootstrap.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equation (13) inverts the mu_B^* scaling required by the proof of Theorem 3.1, so Algorithm 2 as printed adds too little noise and is not mu-GDP even in the B-to-infinity limit.","rationale":"The reader's weakest_assumption identifies exactly the reciprocal scaling error in equation (13), and my independent derivation confirms it. The proof of Theorem 3.1 requires mu_B^* ~ 1/sqrt{B(1-p0)(m/n)(1+(m-1)/n)}, while the printed equation defines mu_B^* as the reciprocal of this quantity. Since Algorithm 2 uses the printed definition to set the Gaussian noise variance, an implementer following the paper would add far less noise than the analysis assumes, and the composition would not satisfy mu-GDP; the privacy guarantee, which is the paper's main contribution, is therefore invalid as written. This is a clear typo rather than a conceptual flaw, because equation (12), the limiting condition in the proof, and Remark 3.1(1) all point to the reciprocal, so a conditional acceptance with a mandatory correction is appropriate. I also note a secondary issue that the reader did not raise: even with the corrected scaling, Theorem 3.2's consistency proof requires sqrt(m)Y to vanish, which needs m = o(n), not merely m = O(n); with m a constant fraction of n the bootstrap noise variance is O(1) and coverage fails. The recommended rule of thumb gives m = o(n), so the main method survives, but the theorem statement should be strengthened. This does not change the verdict: CONDITIONAL remains correct, and the reciprocal error is the more fundamental blocking issue.","tokens_in":22254,"tokens_out":16899,"duration_ms":156776,"concrete_test":"Re-derive the noise scale by equating the variance in (12) with Delta_theta(m)^2 / mu_B^{*2}; the solution is the reciprocal of the right-hand side of (13). Then substitute the printed mu_B^* into the condition of Remark 3.1(1) and verify that mu_B^* sqrt(B) sqrt{(1-p0)(m/n)(1+(m-1)/n)} diverges as B goes to infinity, violating the CLT condition. Optionally, simulate the trade-off function of the B-fold composition for n=1000, m=10, B=1000 with the printed and corrected scales and compare with G_mu; the printed scale shows a much weaker trade-off that keeps degrading with B.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central privacy claim rests on Theorem 3.1, whose proof (Appendix B.1) requires lim_{B->infinity} mu_B^{*2} B (1-p0) (m/n) (1+(m-1)/n) = mu^2. Solving for mu_B^* gives mu / sqrt{B (1-p0) (m/n) (1+(m-1)/n)}. Equation (13) prints mu times that square root, i.e., the reciprocal. The proof text itself later states the correct limiting condition with mu_B^{*2} B (...) -> mu^2, confirming that (13) is a typo. Because Algorithm 2 uses variance Delta_theta(m)^2 / mu_B^{*2}, the printed definition makes the added noise a factor [B (1-p0) (m/n) (1+(m-1)/n)]^2 too small. For B large, the per-step kl divergence grows, so the B-fold composition has unbounded privacy loss instead of converging to G_mu; Corollary 3.1's sqrt(2)mu-GDP claim is unsupported as written. A second, related fragility: even after fixing (13), the proof of Theorem 3.2 needs sqrt(m) Y -> 0, i.e., B (1-p0) (1+m/n)/n -> 0. With m = c n and B = O(n), this is a positive constant, so the privatized bootstrap distribution does not converge to the non-private one and coverage fails; the authors' own rule of thumb (17) yields m ~ n/B = o(n), so the recommended regime is safe, but the stated assumption m = O(n) is too weak.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22561,"tokens_out":14868,"duration_ms":139560,"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":[{"comment":"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.","section":"Section 3, Eqs. (12)-(13), Algorithm 2, and Remark 3.1(1)"},{"comment":"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.","section":"Appendix B.2 / Theorem 3.2"}],"minor_comments":[{"comment":"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.","section":"Section 3, before Algorithm 2"},{"comment":"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.","section":"Section 3, 'Choice of m and B'"},{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The core construction is promising, and the intended definition of mu_star_B is recoverable from Remark 3.1(1) and from the proof of Theorem 3.1, so I do not see this as a reject. The main risk is that the simulations may have been run with the printed (wrong) noise scale; if so, the empirical comparisons do not reflect the intended mechanism. Please ask the authors to confirm which scale was used and to re-run or verify the tables after the fix. The consistency issue in Theorem 3.2 also affects the n-out-of-n case, so the authors should tighten the assumptions rather than claiming that m=O(n) suffices."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, what's worth reading here: Dette and Graw propose an m-out-of-n empirical bootstrap under Gaussian differential privacy. That is a genuinely useful extension of Wang et al.'s n-out-of-n analysis: subsampling makes it unlikely any given individual appears in a bootstrap resample, so the per-iteration noise can be much smaller, and B no longer has to be proportional to n*mu^2. The privacy proof is a clean adaptation of the CLT for trade-off functions, and the rule of thumb m ~ n/B is analytically derived, not fitted. The simulations are extensive and show large computational gains and better finite-sample coverage than both the n-out-of-n bootstrap and BLBQuant. Good, honest work.\n\nNow the problems. Equation (13) as printed inverts the scaling that the proof of Theorem 3.1 actually requires. Appendix B.1 needs mu_B^* = mu / sqrt{B(1-p0)(m/n)(1+(m-1)/n)}; (13) prints mu times that sqrt. Because Algorithm 2 draws Y_b with variance Delta^2/mu_B^{*2}, the printed version adds noise that is a factor R^-4 larger (not smaller - your note has the direction flipped) than the sigma^2_{m,B} in (12). With the printed definition, the composed mechanism does not converge to G_mu; its privacy loss grows with B. (12) is consistent with the reciprocal, so the fix is unambiguous, but the manuscript as written does not make its own central claim.\n\nSecond, Theorem 3.2 states m = O(n), but the proof needs sqrt(m)Y -> 0. Using the corrected variance, Var(sqrt(m)Y) ~ B(1-p0)(n+m-1)/n^2. If m ~ c n and B ~ b n, this tends to b(1-e^{-c}) l^2/mu^2, a positive constant, so coverage fails. The rule of thumb gives m = o(n), so the recommended regime is safe; the theorem should say m = o(n) (keeping B = O(n) is fine). As stated, the theorem is false.\n\nMinor: no code is released, but the simulation setup is described in enough detail to reimplement.\n\nBottom line: the core idea is solid and the package is useful, but the two load-bearing quantities are wrong as printed. Both are easy to fix. This deserves a serious referee - send it out, but with the explicit instruction that the scaling in (13) and the m assumption in Theorem 3.2 must be checked and corrected. I would not accept the current version.","headline":"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.","tokens_in":23146,"tokens_out":10515,"would_cite":true,"duration_ms":90110,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["differential privacy","Gaussian differential privacy","f-differential privacy","bootstrap","m-out-of-n bootstrap","subsampling","privacy amplification","confidence intervals"],"falsifier":"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$.","tokens_in":21943,"feed_emoji":"🔒","tokens_out":20826,"duration_ms":172855,"temperature":0.7,"pith_summary":"Drawing bootstrap samples of size $m<n$ rather than size $n$ is usually a way to fix bootstrap consistency failures; this paper uses it to amplify privacy, because a record is more likely to be absent from a small bootstrap sample and, when absent, the bootstrap estimator leaks nothing about it. The central claim is that, under Gaussian differential privacy, privatising each m-out-of-n bootstrap draw with Gaussian noise whose variance follows the subsampling-aware formula (12) yields, after $B$-fold composition, asymptotically $\\sqrt{2}\\mu$-GDP intervals with coverage $1-2\\alpha$. The payoff is that the m-out-of-n scheme needs less noise per bootstrap iteration and less computation than the n-out-of-n bootstrap at the same asymptotic privacy level, which should produce shorter and cheaper differentially private confidence intervals.","feed_headline":"Subsampled private bootstrap cuts noise and matches privacy level","feed_subtitle":"m-out-of-n bootstrap intervals need less per-draw noise and run faster at the same Gaussian-DP level.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Defines Gaussian differential privacy and supplies the trade-off-function CLT (Theorem B.1) used for the $B$-fold composition.","marker":"Dong et al. (2022)"},{"why":"Supplies the f-DP bootstrap composition theorem (Theorem B.2) and the mixture lemma that privatize each bootstrap draw; the m=n case is the baseline the paper improves on.","marker":"Wang et al. (2022)"},{"why":"Gives the privacy-amplification-by-subsampling principle that justifies using $m<n$ bootstrap samples.","marker":"Balle et al. (2018)"},{"why":"Introduces the non-private m-out-of-n bootstrap from which the private algorithm is built.","marker":"Politis and Romano (1994)"},{"why":"Establishes the consistency condition (16) and the regimes where the m-out-of-n bootstrap is consistent, which Theorem 3.2 assumes.","marker":"Bickel et al. (1997)"},{"why":"Introduces differential privacy and the sensitivity-based Gaussian mechanism used to privatize the estimator and each bootstrap draw.","marker":"Dwork et al. (2006)"}],"fun_headline_variants":["m-out-of-n bootstrap: less noise, same GDP","Subsampled bootstrap trims noise, holds privacy","Gaussian DP through subsampled bootstrap: less noise","Private bootstrap: smaller samples, smaller noise","m-out-of-n BS: efficient privacy with less perturbation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["m-out-of-n bootstrap: less noise, same GDP","Subsampled bootstrap trims noise, holds privacy","Gaussian DP through subsampled bootstrap: less noise","Private bootstrap: smaller samples, smaller noise","m-out-of-n BS: efficient privacy with less perturbation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000404,"raw_usage":{"total_tokens":2190,"prompt_tokens":1121,"completion_tokens":1069,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":737,"completion_tokens_details":{"reasoning_tokens":992}},"tokens_in":737,"tokens_out":1069,"duration_ms":10475,"temperature":1.0,"reasoning_tokens":992,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:26:27.570146+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the privacy-amplification-by-subsampling principle that justifies using $m<n$ bootstrap samples."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the non-private m-out-of-n bootstrap from which the private algorithm is built."},{"cited_title":"J., Götze, F., and van Zwet, W","cited_arxiv_id":null,"evidence_quote":"Establishes the consistency condition (16) and the regimes where the m-out-of-n bootstrap is consistent, which Theorem 3.2 assumes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces differential privacy and the sensitivity-based Gaussian mechanism used to privatize the estimator and each bootstrap draw."}],"review_version":1}