Gaussian Differential Private Bootstrap by Subsampling
Holger Dette, Carina Graw · 2025
Read Gaussian Differential Private Bootstrap by Subsampling by Holger Dette, Carina Graw (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01197.txt.
Introduction
Holger Dette and Carina Graw make bootstrap methods safe for private data. Their 2025 paper tackles a clash: the bootstrap resamples data many times to gauge uncertainty. Under differential privacy, each extra look at the data costs privacy budget. Heavy reuse can wreck either privacy or accuracy.
Older fixes assume a parametric model, which fails when the model is wrong. The pair instead study an empirical bootstrap that resamples only part of the data each time. They prove it stays consistent and private under Gaussian differential privacy. Their version beats the full-size private bootstrap on several counts. The result opens honest uncertainty checks for sensitive datasets.
Catalog record
| CREATOR | Holger Dette, Carina Graw |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01197
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Gaussian Differential Private Bootstrap by Subsampling Holger Dette, Carina Graw 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 m out of n n bootstrap and validate its consistency and privacy guarantees under Gaussian Differential Privacy. Compared to the the private n n out of n 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. 1 Introduction In the era of big data enormous amounts of - possible sensible - information is collected about individuals and over the last decades privacy concerns became more and more important. In the past, successful de-anonymisation attacks have been performed leaking private, possible sensitive data of individuals ( Narayanan and Shmatikov,, 2006 ; Gambs et al.,, 2014 ; Eshun and Palmieri,, 2022 , see, for example, ) . Differential Privacy (DP) is a framework that has been introduced by Dwork et al., (2006) to protect an individual against such attacks while still being able to learn something about the population. Nowadays, Differential Privacy has become a state-of-the-art framework which has been implemented by the US Census and large companies like Apple, Microsoft and Google ( Ding et al.,, 2017 ; Abowd,, 2018 , see) . Since its introduction, numerous differentially private algorithms have been developed for many applications and we refer the reader to the recent survey papers by Wang et al., (2020) ; Xiong et al., (2020) ; Yang et al., (2023) and the references therein. Nowadays, numerous DP tools are available, but from a statistical perspective there is a lack of general techniques for conducting inference under DP such as the uncertainty quantification of DP estimates or the derivation of DP confidence intervals. In the non-private setting, bootstrap is a widely used method to address this question, and parametric bootstrap for private statistical inference have been widely studied (see, for example, Wang and Awan,, 2023 ; Ferrando et al.,, 2022 ; Awan and Wang,, 2023 , and the references therein) . However, this method relies on strong (parametric) model assumptions and might yield to invalid inference if these assumptions are violated. The non-parametric bootstrap is less sensitive but its application for statistical inference under DP is very challenging as it requires multiple, say B , queries to the private data. As a consequence, it is very difficult to balance the trade-off between privacy and statistical accuracy, and non-parametric bootstrap under DP is not so widely studied. Brawner and Honaker, (2018) considered the empirical bootstrap under zero concentrated DP and Wang et al., (2022) investigated empirical bootstrap under f -DP. Furthermore, Chadha et al., (2024) proposed a DP non-parametric bootstrap procedure called Bag of little Bootstraps (BLBQuant). Our contribution: In this paper we present a general non-parametric f -DP bootstrap procedure that - in comparison to previous approaches - adds less noise to each bootstrap estimator while guaranteeing the same level of privacy. This leads to an increased accuracy of the obtained confidence intervals, especially for high privacy and small sample sizes. Our approach utilizes the fact that sub-sampling can improve privacy guarantees ( Balle et al.,, 2018 ; Koga et al.,, 2022 , see, for example,) and is based on the m out of n bootstrap, which draws a subsample of m<n observations with replacement from the full sample of n observations. On the one hand, this can be used to decrease the noise due to privatization, and on the other hand, it can significantly reduce computational time. We validate the statistical consistency of the m out of n bootstrap and provide a privacy guarantee. Furthermore, we investigate the finite sample performance of this new approach by means of a simulation study. Compared to previous work our approach has (at least) three advantages. First, it comes with much 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 (with respect to coverage and length of confidence intervals) compared to the currently available procedures. Structure of the paper: In Section 2 we give a brief overview of f -Differential Privacy and the empirical bootstrap. In Section 3 we present the m out of n bootstrap and state its consistency and privacy guarantees. Finally, we evaluate the new procedure in Section 4 by means of a simulation study while proofs and additional material can be found in the appendix. 2 Background We start by giving a short overview on f -Differential Privacy as introduced in Dong et al., (2022) and the bootstrap under Gaussian Differential Privacy proposed by Wang et al., (2022) , which is important for our work. 2.1 f -Differential Privacy Let (\mathcal{X},\mathbb{X}) , (\mathcal{Y},\mathbb{Y}) be measurable spaces. We call a randomized mapping M:\mathcal{X}^{n}\to\mathcal{Y} a mechanism that maps a dataset S\in\mathcal{X}^{n} onto a random variable M(S) . With abuse of notation we will denote its distribution by M(S) as well. We call two data sets S , S^{\prime}\in\mathcal{X}^{n} neighboring if they differ in exactly one entry. A first notion of privacy, (\epsilon,\delta) -Differential Privacy , was introduced by Dwork et al., (2006) : Definition 2.1 . A mechanism M is (\epsilon,\delta) - differentially private (DP), if P(M(S)\in\mathcal{S})\leq e^{-\epsilon}P(M(S^{\prime})\in\mathcal{S})+\delta for all events \mathcal{S}\in\mathbb{Y} and for all neighboring datasets S,S^{\prime}\in\mathcal{X}^{n} . However, the meaning of the parameters \epsilon,\delta and their interpretation is not obvious (see Wasserman and Zhou,, 2010 , for a statistical interpretation in terms of testing) . f -Differential Privacy as recently introduced by Dong et al., (2022) is an alternative definition of privacy, that is more natural from a statistical point of view. It is given in terms of type I and type II errors of the testing problem whether the input of the mechanism M was S or S^{\prime} . Definition 2.2 . For