Black-Box Differentially Private Nonparametric Confidence Intervals Under Minimal Assumptions

Tomer Shoham, Moshe Shenfeld, Noa Velner-Harris, Katrina Ligett

Abstract

We introduce a simple, general framework that takes any differentially private estimator of any arbitrary quantity as a black box, and from it constructs a differentially private nonparametric confidence interval of that quantity. Our approach repeatedly subsamples the data, applies the private estimator to each subsample, and then post-processes the resulting empirical CDF to a confidence interval. Our analysis uses the randomness from the subsampling to achieve privacy amplification. Under mild assumptions, the empirical CDF we obtain approaches the CDF of the private statistic as the sample size grows. We use this to show that the confidence intervals we estimate are asymptotically valid, tight, and equivalent to their non-private counterparts. We provide empirical evidence that our method performs well compared with the (less-general) state-of-the-art algorithms.

Introduction

In statistical inference, a point estimate alone is rarely sufficient; researchers require a confidence interval (CI) to understand the margin of error. However, calculating these intervals under the constraints of Differential Privacy (DP)—the gold standard for protecting individual data—is notoriously difficult. Existing DP methods often rely on restrictive parametric assumptions (e.g., assuming data follows a Normal curve) or are custom-built for specific statistics, limiting their utility for general data science tasks.

This paper introduces PrivSub (Private Subsampling), a "black-box" framework that generates DP confidence intervals for any statistical estimator. By leveraging privacy amplification through subsampling, the method provides statistically valid and tight uncertainty bounds without requiring the data to follow a specific distribution.

Methodology

PrivSub operates by wrapping around an existing private estimator using a resampling-based approach:

  1. Full Estimate: Compute a private estimate of the target quantity using the entire dataset.
  2. Subsampling: Randomly draw $T$ subsets of the data, each of a smaller size $m$.
  3. Private Sub-estimates: Apply the private estimator to each of these subsets.
  4. CDF Construction: Use these sub-estimates to build an empirical Cumulative Distribution Function (CDF), representing the sampling distribution.
  5. Rescaling & Quantiles: Because sub-estimates use smaller samples, the authors use a convergence rate to rescale the distribution before picking quantiles to form the CI.

The efficiency of the method relies on Privacy Amplification by Subsampling. Because each private estimate only "looks" at a small random portion of the data, the privacy cost of each iteration is significantly reduced, allowing the algorithm to look at the data many times without exhausting the privacy budget.

Experimental Results

The researchers evaluated PrivSub using synthetic datasets including Truncated Normal, Truncated Exponential (skewed), and Gaussian Mixture (bimodal) distributions.

Performance comparison of PrivSub against state-of-the-art methods. The top row shows CI width (lower is better), and the bottom row shows coverage (closer to 0.90 is better).

As shown in Figure 1, PrivSub demonstrates several key advantages:

  • Validity: PrivSub consistently achieved the target coverage (e.g., 90%), even in complex distributions like Gaussian mixtures where previous methods like BLBquant suffered from under-coverage.
  • Efficiency: While privacy noise naturally makes intervals wider for small sample sizes, the "width penalty" of PrivSub vanishes as the sample size $n$ increases, eventually matching the performance of non-private bootstrapping.
  • Generality: Unlike previous state-of-the-art methods, PrivSub is agnostic to the internal workings of the private estimator, provided it is consistent.

Discussion and Limitations

PrivSub offers a versatile tool for private statistical inference, turning the randomness required for privacy into a statistical asset. However, some limitations remain for future exploration:

  • Convergence Rates: Users must know the convergence rate of their statistic (e.g., $1/\sqrt{n}$) to rescale intervals correctly.
  • Small Sample Performance: In very small datasets, the intervals can be overly conservative (too wide). Future research may focus on optimizing the privacy budget split to sharpen these results.
  • Hyperparameter Tuning: The choice of subset size ($m$) and number of trials ($T$) currently relies on rules of thumb rather than a formal optimization theory.

Despite these challenges, PrivSub represents a significant step toward general-purpose, distribution-free private uncertainty quantification.

Summary updated

Abstract

We introduce a simple, general framework that takes any differentially private estimator of any arbitrary quantity as a black box, and from it constructs a differentially private nonparametric confidence interval of that quantity. Our approach repeatedly subsamples the data, applies the private estimator to each subsample, and then post-processes the resulting empirical CDF to a confidence interval. Our analysis uses the randomness from the subsampling to achieve privacy amplification. Under mild assumptions, the empirical CDF we obtain approaches the CDF of the private statistic as the sample size grows. We use this to show that the confidence intervals we estimate are asymptotically valid, tight, and equivalent to their non-private counterparts. We provide empirical evidence that our method performs well compared with the (less-general) state-of-the-art algorithms.
BibTeX
@misc{shoham2025black,
  author = {Tomer Shoham and Moshe Shenfeld and Noa Velner-Harris and Katrina Ligett},
  title = {{Black-Box Differentially Private Nonparametric Confidence Intervals Under Minimal Assumptions}},
  year = {2025},
  eprint = {2511.01303},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.01303},
}
Figure