Abstract:We consider the problem of constructing differentially private nonparametric confidence intervals (CIs) for an arbitrary quantity using resampling. A growing body of work has adapted resampling ideas to the private setting, including private bootstrap methods \cite{brawner2018bootstrap, wang2025differentially,dette2025gaussian} and BLB-based subsample-and-aggregate approaches \cite{covington2025unbiased, chadha2024resampling}. However, existing methods typically rely on strong assumptions, such as asymptotic normality, or are tied to specific privacy mechanisms such as noise addition, and can be impractical in finite-sample regimes. We address these problems by introducing a simple, general framework that can convert any differentially private estimator satisfying mild conditions into a differentially private nonparametric CI for arbitrary target quantities. Our method repeatedly subsamples the data, applies the private estimator to each subset, and post-processes the resulting empirical CDF into a CI. The framework is black-box, and does not require a specific limiting distribution. We prove that the empirical CDF induced by our procedure converges to the sampling distribution of the private statistic, which implies that the resulting CI is asymptotically valid and tight, and provide heuristic guidance for choosing the hyperparameters. Empirically, our method outperforms competing general approaches, especially for non-smooth functionals and more challenging distributions.
| Subjects: | Cryptography and Security (cs.CR); Machine Learning (cs.LG) |
| Cite as: | arXiv:2511.01303 [cs.CR] |
| (or arXiv:2511.01303v2 [cs.CR] for this version) | |
| https://doi.org/10.48550/arXiv.2511.01303 arXiv-issued DOI via DataCite |
Submission history
From: Tomer Shoham [view email]
[v1]
Mon, 3 Nov 2025 07:38:30 UTC (3,141 KB)
[v2]
Wed, 13 May 2026 08:47:17 UTC (6,688 KB)