PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite Sample Differentially Private Confidence Intervals

Vishesh Karwa, Salil Vadhan

arXiv:1711.03908v1cs.CRmath.ST

TL;DR

The paper asks how to construct finite-sample confidence intervals for a normal mean under differential privacy without assuming bounded samples. It develops private procedures for known and unknown variance, analyzes their lengths, and proves lower bounds showing near-optimality up to polylogarithmic factors.

  • Problem

    Differentially private inference needs confidence intervals for population means with finite-sample coverage, but prior bounded-range approaches conflict with normal data on the real line.

  • Method

    The paper constructs conservative differentially private confidence intervals for normal means with known and unknown variance, using range-partitioning and private histograms to locate the mean without bounded samples.

  • Results

    The algorithms’ privacy-induced interval-length cost is O(σ/(εn)) up to polylogarithmic factors, and lower bounds show this cost and associated sample complexity are nearly necessary.

  • Takeaways & Limitations

    The paper provides finite-sample private confidence intervals for normal means without sample-domain boundedness, while identifying the near-optimal privacy cost.

  • Takeaways & Limitations

    The algorithms are not optimized for practical performance, and alternative approaches may be needed for reasonably sized intervals at sample sizes in the 1000s.

Abstract

from arXiv · show

We study the problem of estimating finite sample confidence intervals of the mean of a normal population under the constraint of differential privacy. We consider both the known and unknown variance cases and construct differentially private algorithms to estimate confidence intervals. Crucially, our algorithms guarantee a finite sample coverage, as opposed to an asymptotic coverage. Unlike most previous differentially private algorithms, we do not require the domain of the samples to be bounded. We also prove lower bounds on the expected size of any differentially private confidence set showing that our the parameters are optimal up to polylogarithmic factors.

1 Introduction

The paper frames differentially private confidence intervals as a basic statistical-inference problem, requiring finite-sample coverage while accounting for privacy noise. It studies normal-mean intervals with known and unknown variance and compares their expected size with classical procedures.

  • Differentially private inference must account for both sampling uncertainty and noise introduced to protect privacy.
  • The paper studies (1−α)-level confidence intervals for the mean of normal data with either known or unknown variance.
  • Given a target coverage probability, the objective is to minimize the interval’s expected length.
  • Known Variance: For known variance, the classical normal interval has the smallest expected size among all 1−α-level confidence sets.
  • Unknown Variance: For unknown variance, the classical interval estimates variance from the data and uses a t-distribution quantile.
  • Confidence intervals also induce hypothesis tests, such as rejecting a nonnegative-mean null when the interval excludes the positive real line.

1.3 Differential Privacy

Differential privacy limits how much an algorithm’s output distribution can change when one dataset entry changes. The Laplace mechanism achieves this by adding noise calibrated to global sensitivity, with bounded-data assumptions governing mean-estimation accuracy.

  • Two datasets are neighbors when they differ in one element, and differential privacy bounds output probabilities on neighboring datasets.
  • The privacy definition uses ε and δ, with δ=0 denoting pure differential privacy and δ>0 denoting approximate differential privacy.
  • Differentially private algorithms must be randomized because privacy is defined over the algorithm’s output randomness.
  • The Laplace mechanism releases f(x) plus Laplace noise scaled by the global sensitivity GS_f divided by ε.
  • The released approximation to an empirical mean has additive error O(B/εn) with high probability when data lie in a bounded range.

1.4 Statistical Inference with Differential Privacy

A basic approach to private population inference estimates empirical statistics privately, then combines sampling uncertainty with privacy noise. For the normal mean, privacy noise decreases as 1/n, but bounded-range assumptions and parameter dependence can make intervals impractical.

  • The standard approach privately estimates the sample mean as a proxy for the population mean.
  • Privacy noise vanishes linearly in 1/n, while sampling uncertainty decreases at a slower square-root rate, yielding asymptotically negligible privacy cost.
  • The usual error comparison depends materially on σ, ε, and B rather than only on n.
  • The bounded range B conflicts with a normal-population model supported on the entire real line.

1.5 Conservative Statistical Inference with DP

The paper advocates conservative differentially private inference: confidence intervals must retain coverage at every finite sample size and parameter value, even if small samples or aggressive privacy require very wide outputs. A Laplace-based example illustrates both the coverage adjustment and the cost of bounded-range assumptions.

  • Conservative inference requires P(I(X1, . . . , Xn) ∋µ) ≥ 1−α for all sample sizes, population parameters, and privacy parameters.
  • When samples are too small or privacy is too aggressive, the method may output an extremely large interval rather than sacrifice coverage.
  • A private confidence interval can be formed by expanding the classical interval to account for likely Laplace-noise magnitude.
  • The Laplace-noise adjustment preserves coverage up to an O(α) change when noise magnitude is bounded by (B/εn)·log(1/α) with probability 1−O(α).
  • Using a large B increases interval length linearly, while clamping unbounded normal data can bias the empirical mean and compromise coverage.
  • Conservative confidence intervals support hypothesis tests whose significance accounts for the required coverage guarantee.

1.6 Our Results

The paper develops finite-sample differentially private confidence intervals for normal means with known or unknown variance, including algorithms for unbounded data under approximate DP. It also proves lower bounds showing near-optimal expected lengths and sample-complexity requirements.

  • General guarantees: The algorithms provide (1−α)-level coverage for normal data, without assuming bounded sample values; pure DP requires bounded parameter ranges, whereas approximate DP does not.The pure-DP algorithms assume bounded µ and σ^2, while the approximate-DP algorithms allow unbounded data and parameters.
  • Known variance: For known variance, the confidence interval has fixed width, and its privacy contribution decreases at approximately 1/n up to polylogarithmic factors.The non-private component matches the classical interval up to constants, while the privacy-dependent term is O(σ/(εn)) up to polylogarithmic factors.
  • Known variance: The required sample complexity depends only logarithmically on R/σ, and for δ>0 it has no dependence on R because R can be set to infinity.The sample complexity is the minimum of O((1/ε) log(R/(ασ))) and O((1/ε) log(1/(αδ))).
  • Known variance: A refined known-variance algorithm achieves only an additive, asymptotically vanishing increase over the non-private interval length.This requires an additive sample-complexity increase of (1/ε)·log(1/ε), and the first length term exactly matches the non-private interval.
  • Unknown variance: For unknown variance, the algorithm also guarantees coverage for every n, with a non-private-length term and a faster-vanishing privacy term.The parameter-range dependence is logarithmic; under approximate DP, the parameter bounds can be removed.
  • Lower bounds: The lower bounds require a privacy-dependent interval-length term and establish sample-complexity requirements that nearly match the proposed algorithms.The algorithms are close to the first lower bound up to an extra polylogarithmic factor, while the sample-complexity lower bound matches the unknown-variance result in the stated regime.

1.7 Techniques

The paper builds private confidence intervals by first estimating the data range, then privately estimating the mean and, when necessary, the variance. These techniques exploit normal-data concentration while avoiding dependence on the sample domain in key settings.

  • Known Variance Algorithms: Known-variance algorithms privately estimate a suitable data-dependent range before applying a Laplace-mechanism confidence interval.The range estimator outputs an interval containing all datapoints with high probability and has controlled width.
  • Known Variance Algorithms: After range estimation, clamping enables private mean estimation with Laplace noise of scale O(σ · log(n/α)/(εn)).The range bound makes the clamped mean’s sensitivity manageable while usually leaving normal data unchanged.
  • Known Variance Algorithms: The range estimator partitions the domain into bins of width O(σ) and uses a private approximate histogram to identify the bin near the mean.Normal concentration implies that most observations fall in the mean bin or neighboring bins.
  • Unknown Variance Algorithms: Unknown-variance algorithms first obtain a private constant-factor variance estimate, then reuse range finding and private mean estimation.For tighter bounds, the sample variance is also privately estimated because a constant-factor estimate alone is insufficient.
  • Lower Bounds: The lower-bound argument integrates coverage probabilities over possible means and transfers them using differential privacy and total-variation distance.This yields lower bounds on expected confidence-set length.

1.8 Directions for Future Work

The paper identifies unresolved gaps between private confidence-interval upper and lower bounds and emphasizes that its algorithms are not yet practical for modest sample sizes. It also points to broader extensions and cautions against assuming asymptotic relationships on non-normal data.

  • Open theoretical questions: The lower and upper bounds have small gaps, and the lower bound does not establish whether privacy must increase interval length additively.For sufficiently large n, it leaves open whether private and non-private intervals could have exactly the same length.
  • Practical algorithms: The algorithms are optimized for asymptotic interval-length analysis rather than practical performance, especially at sample sizes in the 1000s.Initial experiments suggest alternative approaches may be needed for intervals no more than twice the non-private length.
  • Broader extensions: Future work could extend the techniques to other population statistics and distribution families, including Bernoulli and multivariate settings.The paper describes these as natural generalizations of the normal-mean problem.
  • Inference assumptions: The safety of assuming ε ≥ Ω(1/√n) for asymptotic significance procedures on non-normal data is unclear.The paper notes that standard unknown-variance normal procedures are often applied heuristically beyond the normal model.

1.9 Organization

The paper introduces differential-privacy preliminaries, develops private range-estimation algorithms, presents confidence-interval algorithms for known and unknown variance, and proves lower bounds.

  • Section 2 reviews differential privacy and tools such as the Laplace mechanism and histogram learners.
  • Section 3 presents differentially private algorithms for estimating the data range as building blocks for private confidence intervals.
  • Sections 4 and 5 present (ε, δ)-differentially private algorithms for the confidence-interval problem.The supplied passage ends before specifying the complete section descriptions.

2 Preliminaries

The preliminaries define notation and privacy composition, review Laplace noise and histogram learning, and explain how private histograms estimate population bin probabilities with sampling and privacy error.

  • The paper distinguishes randomness from the data and from the privacy mechanism when stating probabilities and expectations.Privacy guarantees condition on a fixed dataset, whereas accuracy guarantees account for both sources of randomness.
  • Differential privacy supports composition: a private computation using a dataset and a previous private output remains differentially private.
  • The Laplace mechanism releases a function with global sensitivity Δ by adding independent Laplace noise with scale Δ/ε, providing (ε, 0)-differential privacy.
  • Histogram Learner: A histogram learner privately estimates the population probabilities of disjoint bins and controls maximum generalization error with high probability.The error is measured against population probabilities, so it includes both sampling error and privacy noise.
  • Histogram Learner: Sampling error decreases as O(1/√n), while privacy error decreases linearly in n through O(log(K)/(εn)) and O(log(1/δ)/(εn)) terms.For δ > 0, choosing K = ∞ removes dependence on the parameter range.
  • Histogram Learner: Selecting a very low-probability bin as the noisy maximum is controlled only when its expected count is much smaller than one.The wrong-bin probability bound is useful for pj ≪ 1/n.
  • Histogram Learner: When K < 2/δ the learner uses pure differential privacy, while for K ≥ 2/δ it uses approximate differential privacy.The construction combines private mechanisms with concentration inequalities and a union bound.

3 A differentially private estimate of the range of Gaussian random variables

The paper develops differentially private algorithms for estimating Gaussian sample ranges with known or unknown variance, without bounded sample domains. These range estimates support confidence-interval construction and achieve high-probability containment of all observations.

  • Overview: The algorithms estimate Gaussian sample ranges under known and unknown variances without assuming bounded data.For pure DP, the mean and variance parameters must lie in bounded domains; approximate DP removes these boundedness assumptions.
  • Coverage guarantee: With probability at least 1 − α, the estimated range includes all Gaussian observations.The guarantee follows by combining the noisy-bin localization and Gaussian-tail bounds with a union bound.
  • Known variance: The known-variance algorithm partitions the parameter domain into bins, privately learns bin masses, and outputs the extrema of the data using the selected range.The largest noisy bin is used to locate the data region, followed by outputting (Xmin, Xmax).
  • Unknown variance: The unknown-variance construction first privately estimates the standard deviation, then uses that estimate to estimate the sample range.The estimated standard deviation serves as an upper bound on the true standard deviation for the subsequent range algorithm.
  • Parameter domains: When δ > 0, the required sample complexity remains finite even with unbounded mean and variance domains.When δ = 0, boundedness conditions on the mean and variance domains are required, with logarithmic parameter dependence.

4 Estimating a confidence interval of a mean with known variance

For known variance, the paper constructs differentially private confidence intervals for a Gaussian mean with finite-sample coverage. The refined construction achieves nearly optimal width by adding a privacy term to the classical non-private width rather than multiplying it by a hidden constant.

  • Coverage: The output is a fixed-width (1 − α)-level confidence interval for every sample size.The coverage proof combines the classical Gaussian mean event, range containment, and Laplace-tail events.
  • Optimality: The privacy-dependent width contribution is σ/(ǫn) · log(1/α) up to polylogarithmic factors and cannot be significantly improved.The paper later proves a matching lower bound for this privacy cost.
  • Construction: The algorithm privately estimates the data range, truncates observations to that range, releases a noisy truncated mean, and accounts for all randomness in the interval width.The privacy budget and failure probability are split across range estimation, mean release, and coverage events.
  • Width: The refined interval has additive rather than multiplicative privacy overhead, with the first term matching the non-private interval length.The additional term vanishes faster than the non-private length, while dependence on other parameters worsens mildly.

5 Estimating a confidence interval of a mean with unknown variance

For unknown variance, the paper privately estimates the variance and range before constructing a conservative mean interval using a t-quantile. The resulting intervals have finite-sample coverage and nearly optimal additive width.

  • Statistical calibration: The method replaces the known-variance z-quantile with a t-quantile because the sample variance estimates σ2.Unlike the known-variance interval, the unknown-variance interval is not generally fixed in length.
  • Construction: The unknown-variance algorithm privately estimates σ, estimates the data range, truncates the observations, and releases a noisy truncated mean.It also privately constructs a conservative sample-variance estimate for the final t-based interval.
  • Coverage: The output achieves (1 − α)-level coverage for every sample size, and its width becomes non-trivial when n is sufficiently large.Coverage combines the non-private confidence event, Laplace noise events, variance control, and range containment.
  • Privacy: The algorithm is (ǫ, δ)-differentially private by composing privacy-preserving range, mean, and variance computations.The variance estimate is handled in addition to the privacy accounting used in the known-variance construction.
  • Width and optimality: The unknown-variance interval has additive privacy overhead, with the non-private width as one term and a privacy term that decreases with n.The paper describes this as nearly optimal, matching lower bounds up to polylogarithmic factors.

6 Lower Bounds for confidence intervals with known variance

The lower-bound analysis compares private confidence-set sizes with non-private benchmarks for the normal mean. It shows that privacy necessarily adds a σ/(ǫn) · log(1/α)-type cost, while sample-size requirements align with the proposed upper bounds.

  • Non-private lower bound: Without privacy, when R = Ω(σ), the expected confidence-set size is at least the classical interval length minus a term vanishing at rate 1/n up to logarithmic factors.This establishes the relevant non-private benchmark in the bounded-mean regime.
  • Private lower bound: Any (1 − α)-level differentially private confidence set—not only an interval—must pay either a large range-scale size or a privacy-dependent lower bound.The lower bound applies to arbitrary measurable sets produced by a DP algorithm.
  • Privacy cost: The privacy-dependent lower bound is σ/(24ǫn) · log(1/(4α)) in one case, up to the alternative of size proportional to R.Thus the σ/(ǫn) · log(1/α) contribution in the upper bound is unavoidable up to polylogarithmic factors.
  • Sample complexity: The lower bound requires n ≥ (c1/ǫ) · log(1/4α) or n ≥ (c2/ǫ) · log(1/δ) under the stated alternatives.These sample-size conditions match the requirements needed by the proposed known-variance construction for a non-trivial interval.

7 Appendix: Basic distributions and tail bounds

This appendix defines the normal, χ2, t-, and Laplace distributions used in the paper and collects tail bounds for these distributions. It also relates tail bounds to quantiles and proves t-distribution quantile bounds using density and component-tail arguments.

  • Basic distributions: A standard Gaussian has mean 0 and variance 1; Φ denotes its cdf and φ its pdf.
  • Basic distributions: A χ2 variable with k degrees of freedom is the sum of squares of k independent standard normal variables.
  • Basic distributions: A t variable with k degrees of freedom is represented as Z divided by the square root of Y/k, with Z standard normal and Y χ2 with k degrees of freedom.
  • Tail bounds: The appendix states Chernoff, Laplace, Gaussian, χ2, and t-distribution tail bounds, including a t-density-based bound and a χ2 result attributed to Laurent and Massart.
  • Quantiles: If P(X ≥ t) ≤ α, then the 1 − α quantile q(α) satisfies q(α) ≤ t.The proof uses F(q(α)) = 1 − α and monotonicity of the cdf.
Loading 1711.03908v1…