🤖 machine learning

Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions

Original authors: Tomer Shoham, Moshe Shenfeld, Noa Velner-Harris, Katrina Ligett

Published 2026-05-14

📖 5 min read🧠 Deep dive

Original authors: Tomer Shoham, Moshe Shenfeld, Noa Velner-Harris, Katrina Ligett

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out the average height of everyone in a city, but you can't ask everyone directly because their data is sensitive. You have a list of names, but you can't look at the whole list at once without risking a privacy leak. Instead, you have a special tool (a "privacy shield") that lets you peek at small groups of people, but every time you peek, the tool adds a little bit of "static" or "fog" to the numbers to protect the individuals.

The problem is: How do you know how much to trust your estimate? In statistics, we usually draw a "Confidence Interval" (a range of numbers) to say, "We are 95% sure the true answer is somewhere in here." But when you add that "fog" for privacy, the math gets messy. The fog makes your range either too wide (useless because it covers everything) or too narrow (dangerous because it might miss the truth).

Existing methods for solving this are like trying to fix a leaky boat by bailing water with a cup that has holes in it. They often rely on the assumption that the data behaves in a very predictable, "bell-curve" way. If the data is weird or the sample size is small, these methods fail, giving you a false sense of security or a useless, giant range.

The Paper's Solution: "PrivSub" (Private Subsampling)

The authors propose a new method called PrivSub. Think of it as a clever way to use a magnifying glass without burning the paper.

Here is how it works, using a simple analogy:

1. The "Taste Test" Approach (Subsampling)
Imagine you have a giant pot of soup (your full dataset) and you want to know if it's salty enough.

Old Way (Bootstrap): You try to taste the whole pot, but to protect the chef's secret recipe, you have to add a lot of salt (noise) to your spoon every time you taste. If you taste it 100 times, you've added so much salt that the soup is inedible.
The Paper's Way (Subsampling): Instead of tasting the whole pot, you take a small ladle of soup (a small subset of data). You taste that ladle, add a tiny bit of salt (privacy noise), and write down the result. You do this many times with different ladles. Because the ladles are small, the "salt" you add is much less noticeable.

2. The "Magic Scale" (Rescaling)
Here is the tricky part: A ladle of soup tastes different than the whole pot. A small group of people has a different average height than the whole city.

The authors use a "magic scale" (a mathematical factor based on how big the ladle is compared to the pot). They take the results from all their small ladle-tastes, shrink or stretch them using this scale, and combine them.
This creates a map of uncertainty. Instead of guessing the range, they build a picture of what the answer could be based on all those small, noisy tastes.

3. The "Black Box" Advantage
The best part about this method is that it's a black box.

Imagine you have a mysterious machine that gives you a private estimate of anything (the median, a regression slope, or even a weird statistical test).
You don't need to know how the machine works inside, or if the data follows a perfect bell curve. You just feed your private estimates into this "PrivSub" framework.
The framework automatically builds a valid confidence interval around your answer, no matter how weird the data is.

Why is this better?

The paper tested this against other methods (like "Private Bootstrap" and "BLB") using three different scenarios:

Finding the Median: (The middle value of a list).
Logistic Regression: (Predicting a yes/no outcome, like "will this email be spam?").
KS Statistic: (A test to see if data matches a specific pattern, which is very "bumpy" and unpredictable).

The Results:

The Competitors: The old methods often gave intervals that were either too wide (conservative, like saying "the answer is between 0 and 100") or too narrow (invalid, missing the true answer). They struggled especially when the data wasn't a perfect bell curve or when the sample size wasn't huge.
PrivSub: It consistently found the "Goldilocks" zone. The intervals were tight enough to be useful but wide enough to be correct. It worked well even for the "bumpy" KS statistic where other methods failed.

The Bottom Line

The authors created a universal tool that lets statisticians build reliable "confidence intervals" for sensitive data without needing to make strong assumptions about how the data behaves.

Analogy: If other methods are like trying to guess the weather by looking at a single, foggy window, PrivSub is like taking hundreds of quick snapshots through small cracks in the curtains, stitching them together, and using a smart algorithm to clear up the fog. It gives you a clear, accurate picture of the weather (the true statistic) while keeping the view from the outside (the individual data points) completely hidden.

The paper proves mathematically that as you get more data, this method becomes perfectly accurate, and in real-world tests with smaller datasets, it outperforms the current state-of-the-art methods.

Technical Summary: Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions

Problem Statement
The paper addresses the challenge of constructing differentially private (DP) nonparametric confidence intervals (CIs) for arbitrary statistical quantities. While CIs are fundamental for quantifying uncertainty in statistical inference, existing DP methods face significant limitations. Current approaches often rely on strong assumptions, such as asymptotic normality of the statistic, or are tied to specific privacy mechanisms (e.g., Gaussian noise addition). Furthermore, methods based on bootstrapping or Bag-of-Little-Bootstrap (BLB) can be impractical in finite-sample regimes, often resulting in intervals that are either invalid (under-covering) or overly conservative (excessively wide). The authors aim to develop a general framework that converts any DP estimator satisfying mild conditions into a valid nonparametric CI without requiring specific limiting distributions or smoothness assumptions on the target functional.

Methodology: PrivSub (Private Subsampling)
The proposed solution, PrivSub, leverages the statistical technique of subsampling rather than bootstrapping. The algorithm operates as follows:

Full Estimation: Compute a differentially private estimate of the target quantity on the full dataset using a mechanism $M_{full}$ .
Subsampling: Draw $T$ subsets of size $m$ from the dataset without replacement.
Private Sub-Estimation: Apply a differentially private estimator $M_{sub}$ to each of the $T$ subsets.
Post-Processing: Construct the empirical Cumulative Distribution Function (CDF) of the centered and rescaled private statistics. Specifically, the method centers the subset estimates around the full-dataset estimate and rescales them by the ratio of convergence rates $\tau_m / \tau_n$ (where $\tau_n$ is the convergence rate of the statistic).
Interval Construction: The final CI is derived by taking the $\alpha/2$ and $1-\alpha/2$ quantiles of this empirical CDF.

The framework is "black-box," meaning it does not require knowledge of the specific form of the limiting distribution, only the existence of one and a known convergence rate. The privacy guarantee is achieved by applying standard DP mechanisms to the subset computations and utilizing privacy amplification by subsampling, followed by composition over the $T$ iterations.

Key Contributions

General Framework: The authors propose a method that transforms any DP estimator into a nonparametric CI under minimal distributional assumptions. It does not require the statistic to be asymptotically normal or the functional to be smooth.
Theoretical Guarantees: The paper proves that the empirical CDF induced by PrivSub converges to the true sampling distribution of the private statistic (Theorem 3.3). Consequently, the resulting CI is proven to be asymptotically valid and tight (Corollary 3.4), provided the privacy mechanism is $\tau_n$ -consistent (i.e., the privacy-induced error is of a lower order than the statistical error).
Privacy Analysis: The authors provide rigorous privacy bounds for the algorithm, accounting for both pure DP ( $\delta=0$ ) and approximate DP ( $\delta > 0$ ), utilizing subsampling amplification and advanced composition theorems.
Heuristic Guidance: While optimal finite-sample hyperparameters ( $m$ and $T$ ) cannot be derived under minimal assumptions, the paper offers heuristic guidance. It suggests a constraint $m \cdot T \gtrsim n$ to balance data usage and privacy cost, and recommends $m \propto n^{2/3}$ and $T=60$ for practical stability.

Empirical Results
The authors evaluate PrivSub against existing general nonparametric DP CI methods, specifically BLBquant (based on BLB) and PrivBoot (based on private bootstrap), across three tasks:

Median Estimation: Under a truncated normal distribution.
Logistic Regression Slope Estimation: A parametric setting with a normal limiting distribution.
Kolmogorov-Smirnov (KS) Statistic: A non-smooth functional with a non-normal limiting distribution.

Findings:

Validity and Tightness: PrivSub consistently produces CIs with coverage close to the nominal level (e.g., 90%). In contrast, BLBquant frequently under-covers (invalid) in finite samples, while PrivBoot is consistently overly conservative, producing significantly wider intervals.
Robustness: PrivSub performs well across both smooth (median, regression) and non-smooth (KS) functionals. It notably outperforms competitors in the KS experiment, where non-normal limiting distributions challenge other methods.
Finite-Sample Performance: The method achieves widths competitive with, and often smaller than, the corresponding non-private baselines, whereas competing private methods often suffer from excessive width due to privacy composition costs or invalidity.

Significance and Claims
The paper claims that PrivSub offers a modular and general approach to private statistical inference. Its primary significance lies in relaxing the assumptions required for valid DP CIs. Unlike prior works that necessitate asymptotic normality or specific noise mechanisms, PrivSub relies only on the existence of a limiting distribution and a known convergence rate. This makes the framework applicable to a broader class of statistical problems, particularly those involving non-smooth functionals or complex distributions where traditional bootstrap or normal-approximation methods fail. The authors emphasize that their theoretical guarantees translate into practical performance, offering a robust alternative for uncertainty quantification in privacy-sensitive data analysis.

The Paper's Solution: "PrivSub" (Private Subsampling)

Why is this better?

The Bottom Line

Technical Summary: Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions

More like this