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

Differentially private statistical inference has largely focused on dataset statistics rather than population inference. This paper constructs finite-sample differentially private confidence intervals for normal means and shows that their lengths approach lower bounds up to polylogarithmic factors.

  • Problem

    Most differential privacy work studies empirical dataset statistics rather than inference about the population that generated the data.

    Source: §1.1 · p. 1

  • Method

    The paper constructs conservative differentially private confidence-interval estimators for normal means with known and unknown variance, with finite-sample coverage and no bounded-data assumption.

    Source: §1.6 · p. 5

  • Results

    Ω(σ/(εn)·log(1/α)) is a lower bound on interval length when R is very large, and the algorithms approach it within a polylog(n/α) factor.

    Source: §1.6 · p. 8

  • Takeaways & Limitations

    For large n, the increase in confidence-interval length due to privacy is mild, with a privacy term of O(σ/(εn)) up to polylogarithmic factors.

    Source: §1.6 · p. 6

    The algorithms are not optimized for practical performance, but rather for asymptotic analysis of confidence-interval length.

    Source: §1.8 · p. 10

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 · 1.1 Overview · 1.2 Confidence Intervals for a Normal Mean

The paper pursues differentially private inference, conservative uncertainty quantification, and rigorous privacy–utility analysis through the case study of confidence intervals for a normal mean. The classical problem requires coverage across population parameters while minimizing expected interval length.

1.1 Overview

  • Differentially private inference should address population statistics, not only empirical properties of the dataset, which have dominated prior work.The passage argues that inference about the underlying population is the ultimate goal of most data analysis.Source: §1.1 · p. 1
  • Private inference should be conservative, accounting for privacy noise and limiting incorrect conclusions even at small sample sizes and across parameter settings.The passage frames this as erring on the side of underestimating statistical significance.Source: §1.1 · p. 1
  • The privacy–utility tradeoff for conservative private inference calls for both procedure design and lower bounds, benchmarked against the best non-private procedures.Source: §1.1 · p. 2
  • The paper studies all three goals using confidence intervals for a normal mean, a basic inferential problem that remains nontrivial under differential privacy.The authors expect their modeling and methods to have analogues for hypothesis testing, Bayesian credible intervals, non-normal data, and statistics beyond the mean.Source: §1.1 · p. 2

1.2 Confidence Intervals for a Normal Mean

  • A (1−α)-level interval should cover the mean for all μ and σ, while minimizing its expected length.The coverage probability is 1−α; expected length is E[|I(X1, . . . , Xn)|].Source: §1.2 · p. 2
  • With known variance, the classic normal-mean interval has the smallest expected size among all 1−α-level confidence sets, and its length is fixed.Source: §1.2 · p. 2
  • With unknown variance, the classic interval estimates variance from the sample and uses a t-distribution quantile; its length is random.The passage identifies the t-distribution as having n−1 degrees of freedom and describes the interval length’s expectation.Source: §1.2 · p. 2
  • A confidence interval also defines hypothesis tests: its intersection with the positive real line determines whether to reject a nonnegative-mean null, and shorter intervals can enable rejection of closer alternatives.The passage states the test’s significance level is at least 1−α and gives a condition for rejection probability of at least 1−α.Source: §1.2 · p. 3

1.3 Differential Privacy

The section defines differential privacy through neighboring datasets and randomized output distributions, then describes Laplace noise as a basic mechanism for private statistical computation.

Differential Privacy

  • Differential privacy requires a randomized algorithm’s output probabilities on neighboring datasets to satisfy the (ε, δ) condition for every measurable output set.The probability is taken over the algorithm’s randomness; neighboring datasets differ by one element.Source: §1.3 · p. 3
  • When δ = 0, the guarantee is pure differential privacy; when δ > 0, it is approximate differential privacy.The section describes ε as typically a small constant and δ as cryptographically small, in particular much smaller than 1/n.Source: §1.3 · p. 3
  • The Laplace Mechanism approximates a function by adding Laplace noise with scale GS_f/ε, where GS_f is its global sensitivity.Global sensitivity is the maximum change in the function over neighboring datasets.Source: §1.3 · p. 3
  • With high probability, the private approximation of the empirical mean has additive error O(B/(εn)).Source: §1.3 · p. 3

1.4 Statistical Inference with Differential Privacy

Differentially private inference can use empirical statistics to estimate population quantities, but finite-sample performance depends on parameters and assumptions that asymptotic analysis can obscure.

Statistical inference with differential privacy

  • Much of differential privacy research estimates empirical statistics, while basic inference remains understudied beyond early DP PAC-learning work (Blum et al. (2005); Kasiviswanathan et al. (2011)).The passage also cites work seeking the best asymptotic approximations for population statistics under differential privacy: Dwork and Lei (2009); Smith (2011); Wasserman and Zhou (2010); Wasserman (2012); Hall et al. (2013); Duchi et al. (2013a,b); Barber and Duchi (2014).Source: §1.4 · pp. 3–4
  • For a normal population, estimate μ by the sample mean X plus Laplace noise Z ∼ Lap(2B/ǫn), exploiting empirical approximation for private population-mean estimation.The passage presents this as a natural approach when population statistics are well approximated by empirical statistics.Source: §1.4 · p. 3
  • Privacy noise falls linearly in 1/n, making privacy asymptotically free relative to the optimal non-private estimator X.The passage cautions that this asymptotic comparison can conceal important finite-sample parameter effects.Source: §1.4 · p. 4
  • n ≫ (B/ǫσ)^2 is needed before σ/√n ≫ B/ǫn, and the bounded-range assumption B conflicts with normal populations’ unbounded support.Thus, the sample size at which the asymptotic comparison becomes meaningful may be very large.Source: §1.4 · p. 4

1.5 Conservative Statistical Inference with DP

The section advocates conservative differentially private inference that accounts for both sampling and privacy noise and guarantees finite-sample coverage. It motivates a theoretical analysis of confidence intervals for a normal mean, including whether bounded-data assumptions and their utility costs are necessary.

1.5 Conservative Statistical Inference with DP

  • Ignoring privacy noise in significance calculations can produce severely incorrect finite-sample conclusions, with potentially serious consequences.The passage cites unsafe warfarin dosing as an example of the risks of naive differential privacy use, while cautioning that life-or-death decisions require statistical-significance analysis.Source: §1.5 · p. 4
  • Conservative inference requires P(I(X1, . . . , Xn) ∋µ) ≥ 1 −α for all sample sizes, population parameters, and privacy parameters, even if some intervals must be extremely large.What counts as a sample size that is too small can depend on unknown population parameters, such as variance, and their interaction with privacy ε.Source: §1.5 · p. 4
  • For the known-variance normal mean, expanding a classical interval for Laplace noise yields a (1 −O(α))-level confidence interval.With probability 1 −O(α), the noise magnitude is at most (B/ǫn) · log(1/α), so expanding the interval by that amount preserves coverage up to an O(α) change.Source: §1.5 · p. 4
  • The Laplace approach requires data in [−B, B]; clamping can bias the mean and compromise coverage, while larger B increases interval length linearly.This motivates asking whether choosing a large bound, and paying its resulting interval-size cost, is necessary.Source: §1.5 · pp. 4–5
  • Prior methods combined sampling and privacy uncertainty, but utility was generally evaluated empirically or conservativeness held only asymptotically; this work analyzes normal-mean intervals and lower bounds without bounded-data assumptions.Sheffet (2017) gives finite-sample regression confidence intervals but requires bounded data, while neither it nor Cai et al. (2017) provides matching lower bounds.Source: §1.5 · p. 5

1.6 Our Results

The paper constructs differentially private confidence intervals for normal means with known or unknown variance, guaranteeing finite-sample coverage and nearly optimal expected length. Approximate-DP algorithms need no boundedness assumptions on the data or parameters, while pure-DP algorithms assume bounded mean and variance.

Overall guarantees

  • The algorithms provide (1−α)-level coverage for every sample size without assuming bounded data; approximate-DP algorithms also allow unbounded parameters.Pure-DP algorithms assume bounded mean and variance, and the paper shows such an assumption is necessary; interval length is asymptotically at most a 1 + o(1) factor above the non-private length.Source: §1.6 · p. 5

Known Variance

  • For known variance, the algorithm outputs a fixed-width (1−α)-level interval for any n, with a non-trivial width once n is large enough and no dependence on the data range or R.For large n, the width combines a term matching the non-private interval up to constants with a privacy term that vanishes faster.Source: §1.6 · p. 6
  • Theorem 1.2 achieves only an additive increase over the non-private interval length, at the cost of an additive (1/ε)·log(1/ε) increase in sample complexity.Its first length term exactly matches the non-private length, and the second vanishes faster with n; the first term retains n rather than εn.Source: §1.6 · pp. 6–7

Unknown Variance

  • For unknown variance, the algorithm always outputs a (1−α)-level interval, and for sufficiently large n its length combines the non-private length with a faster-vanishing term.The sample-complexity dependence on R/σmin and σmax/σmin is logarithmic; when δ > 0, the parameters can be unbounded.Source: §1.6 · p. 7
  • For unknown variance, a variant achieves only an additive, asymptotically vanishing increase over the non-private interval length at a minor increase in sample complexity.The non-private length is the first term, while the second vanishes faster with n.Source: §1.6 · p. 7

Lower Bounds

  • When R is very large, any private interval must incur length at least Ω(σ/(εn)·log(1/α)); the algorithms come within an extra polylog(n/α) factor.The lower bounds also show the sample complexity in Theorem 1.1 is necessary to save more than a factor of 2 over the trivial interval.Source: §1.6 · pp. 7–8

1.7 Techniques

The techniques privately find a data range under the Gaussian assumption, then use it to construct confidence intervals with known or unknown variance. The lower-bound analysis combines differential privacy with the intervals’ coverage guarantees.

Known Variance Algorithms

  • For known variance, Mrange uses private histograms over O(σ)-width bins to find a heavy bin, then expands the range and clamps data before estimating the mean with Laplace noise.The histogram identifies a heavy bin with probability 1 − α when n ≥ O(min{log(K/α), log(1/(δα))})/ε, where K = O(R/σ). Mrange contains all data points with probability at least 1 − α.Source: §1.7 · p. 8

Unknown Variance Algorithms

  • For unknown variance, paired absolute differences feed a private geometric-bin histogram to estimate σ, after which range finding and mean estimation proceed as in the known-variance case.The analysis requires the estimate to be within a constant factor of σ in expectation as well as with high probability; a private sample-variance estimate supports the tighter additive-length bound.Source: §1.7 · p. 9

Lower Bounds

  • The lower-bound argument combines confidence-set coverage with differential privacy, comparing probabilities across Gaussian means using their total variation distance.The passage identifies that distance as d ≤ min{1, |µ − µ′|/σ} and says the argument yields a lower bound on expected length after further calculations.Source: §1.7 · pp. 9–10

1.8 Directions for Future Work

The paper identifies open directions in tightening privacy-related bounds and making private confidence intervals practical, while extending the methods and clarifying when asymptotic inference is safe.

Directions for Future Work

  • The bounds leave open whether privacy must add to interval length, especially when large-sample non-private intervals already exceed the privacy lower bound.The lower bound is only the maximum of the privacy term and non-private length, and the authors consider equality with non-private length unlikely.Source: §1.8 · p. 10
  • Practical differentially private confidence intervals remain an open problem because current algorithms are not optimized for modest sample sizes or reasonably short intervals.The target is length at most twice the non-private length for sample sizes in the 1000s; alternative approaches beyond parameter tuning may be needed.Source: §1.8 · p. 10
  • Future work could extend private inference to other statistics and distributions, including multivariate Gaussian parameters related to ordinary least-squares regression (Sheffet (2017)).Examples include other continuous and Bernoulli variables, as well as multivariate families.Source: §1.8 · p. 10
  • The authors ask how to determine when asymptotic inference is safe and whether privacy can use only the asymptotics used without privacy, as in Kifer and Rogers (2016).Kifer and Rogers analyze hypothesis tests under a constraint relating the privacy parameter to sample size, but the authors say its general safety is unclear.Source: §1.8 · p. 10

1.9 Organization

The paper progresses from differential privacy preliminaries and range-estimation building blocks to confidence-interval algorithms for known and unknown variance, then lower bounds.

Sections 2–3

  • Section 3 presents differentially private data-range estimation algorithms that serve as building blocks for confidence-interval estimation.Section 2 first introduces preliminary differential privacy results and techniques, including the Laplace mechanism and histogram learners.Source: §1.9 · p. 10

Sections 4–5

  • Sections 4 and 5 present (ε, δ)-differentially private algorithms for estimating a (1 − α)-level confidence interval of µ with known and unknown variance, respectively.Source: §1.9 · p. 10

Section 6

2 Preliminaries

The preliminaries distinguish mechanism randomness from sampling randomness and establish the differential privacy and histogram-learning tools used later.

2.1 Notation

  • Accuracy probabilities average over both mechanism randomness and data sampling, whereas privacy guarantees are defined for a fixed dataset.The notation conditions probabilities and expectations on the dataset when measuring mechanism randomness and uses distribution-based expectations for sampling randomness.Source: §2.1 · p. 11

2.2 Differential Privacy

  • Composing a differentially private computation with one that uses its output preserves privacy, and Laplace noise at scale Δ/ε privatizes a function with global sensitivity Δ.The Laplace mechanism is stated for a function whose global sensitivity is at most Δ.Source: §2.2 · p. 11
  • The histogram learner estimates bin probabilities from iid samples with high-probability maximum error measured against population probabilities, incorporating sampling and privacy noise.It applies to collections of disjoint bins, including countably infinite collections.Source: §2.2 · p. 12
  • Histogram-learning privacy error decreases linearly with sample size, faster than sampling error, and bin-count dependence is logarithmic or absent when δ > 0.For δ > 0, allowing K = ∞ yields algorithms with no dependence on the parameter range.Source: §2.2 · p. 12
  • The probability of selecting bin j as the largest is bounded roughly by np_j, a useful bound when p_j ≪ 1/n.This bounds selection of bins with very few expected points, with probability taken over sampling and privacy noise.Source: §2.2 · p. 13

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

The section develops differentially private estimators of Gaussian-sample ranges with known and unknown variance, intended as building blocks for confidence intervals. The algorithms provide high-probability range coverage without requiring bounded sample values; boundedness requirements depend on the privacy guarantee.

3.1 Estimation of range with known variance

  • With known variance, the private estimator covers all sample points with high probability and returns a range within a constant factor of the true range.For δ > 0, the guarantee has no dependence on a bound for µ; for δ = 0, µ must be bounded and the sample-size requirement depends logarithmically on R/(σα).Source: §3.1 · pp. 15–16

3.2 An estimate of variance

  • The private variance estimator returns a value between σ and 8σ with high probability, and an expected squared-estimate bound is also established at increased sample complexity.The expected-bound analysis uses α = α0/log² n and requires n ≥ Õ(1/ǫ); its stated dependence is logarithmic rather than doubly logarithmic in σmin/σmax.Source: §3.2 · pp. 18–19

3.3 Estimation of range with unknown variance

  • With unknown variance, the private algorithm combines variance estimation with known-variance range estimation to obtain a high-probability range of the same order as the Gaussian expected range.For δ > 0, µ and σ² may be unbounded without dependence of the sample size on R, σmin, or σmax; for δ = 0, they must be bounded, with logarithmic parameter dependence.Source: §3.3 · pp. 23–24

4 Estimating a confidence interval of a mean with known variance

For a normal population with known variance, the section constructs differentially private confidence intervals with finite-sample coverage and fixed width. It also presents a width bound that adds a privacy cost to the exact non-private interval length.

4 Estimating a confidence interval of a mean with known variance

  • For every sample size, Theorem 4.1 gives an (epsilon, delta)-DP fixed-width interval with 1-alpha coverage; for sufficiently large n, its width is the maximum of the non-private width and a privacy term vanishing linearly in n.The theorem assumes iid N(mu, sigma^2) samples with mu in (-R, R).Source: §4 · pp. 24–25
  • The algorithm privately estimates the data range, truncates observations to it, releases a Laplace-noised truncated mean, and accounts for all randomness when setting the interval.It allocates the total confidence error across the normal-sampling, range-estimation, and Laplace-noise terms.Source: §4 · p. 25

Nearly optimal width for finite sample sizes

  • The nearly optimal-width construction adds a privacy term to the exact non-private interval length, with no hidden constant in that first term; a lower bound gives a necessary privacy cost of Omega(sigma/(epsilon n) * log(1/alpha)).The lower bound shows that the privacy-dependent term cannot be significantly improved.Source: §4 · pp. 25, 27

5 Estimating a confidence interval of a mean with unknown variance

The section develops a differentially private confidence interval for a normal mean with unknown variance, with finite-sample coverage and a width whose privacy cost is necessary up to polylogarithmic factors. It also describes a finite-sample refinement that makes the increase in interval length additive rather than multiplicative, at a minor increase in sample complexity.

5 Estimating a confidence interval of a mean with unknown variance

  • For unknown variance, the algorithm estimates σ, estimates the data range, adds Laplace noise to the truncated mean and sample variance, and accounts for all randomness to ensure coverage.The procedure combines confidence-error allocations across range estimation, mean estimation, and variance estimation.Source: §5 · pp. 28–30
  • The algorithm gives a differentially private (1−α)-confidence interval with finite-sample coverage; for sufficiently large n, its width is non-trivial and matches lower bounds up to polylogarithmic factors.The width is the maximum of the non-private interval width and a privacy-dependent term; the lower bound establishes that the privacy term is necessary.Source: §5 · p. 29
  • The finite-sample refinement achieves an additive increase in interval length rather than a multiplicative one, with a minor increase in sample complexity.The section introduces this result as a nearly optimal width guarantee for finite sample sizes.Source: §5 · p. 35

6 Lower Bounds for confidence intervals with known variance

The section derives expected-size lower bounds for confidence sets without privacy and for differentially private confidence sets. The private bounds quantify the cost of privacy and constrain the sample size needed for a nontrivial interval.

6.1 Lower bounds on Confidence Intervals without privacy

  • When R = Ω(σ), the non-private expected-size lower bound is the classic interval length minus a term vanishing at rate 1/n, up to logarithmic factors.This result concerns the bounded normal mean when R is on the order of or larger than σ.Source: §6.1 · p. 37

6.2 Lower bounds on confidence sets with privacy

  • β > R/2 or β > σ/(24ǫn) · log(1/(4α)) for any differentially private confidence set, unless its expected size is proportional to the original range.The lower bound applies to arbitrary measurable sets, not only intervals; its privacy-dependent term is unavoidable unless the set is large relative to the range.Source: §6.2 · pp. 39, 40, 45
  • n ≥ (c1/ǫ) · log(1/(4α)) or n ≥ (c2/ǫ) · log(1/δ); these sample-size bounds match the stated upper-bound requirements for known and unknown variance.For unknown variance, the match holds when R ≥ Ω(σmax) and σ = σmin.Source: §6.2 · pp. 40, 45

7 Appendix: Basic distributions and tail bounds

The appendix defines distributions used in the paper and collects tail bounds, including a derivation of t-distribution quantile bounds from tail inequalities.

7.1 Basic Distributions

  • The appendix defines standard Gaussian, χ2, t, and Laplace distributions, including the t-distribution’s representation using a standard normal and a χ2 random variable.It denotes the standard normal cdf by Φ(·) and pdf by φ(·).Source: §7.1 · p. 46

7.2 Tail bounds

  • The appendix states Chernoff, Laplace, Gaussian, χ2, and t-distribution tail bounds, including results attributed to Laurent and Massart (2000) and Soms (1976).It also gives a relation for converting a tail-probability bound into an upper bound on a quantile.Source: §7.2 · pp. 46–47
  • The t-quantile bounds are obtained by applying the tail-to-quantile relation to t-distribution tail bounds.One proof controls the t-distribution upper tail by a union bound using normal and χ2 tail bounds, under a stated condition on n and α.Source: §7.2 · pp. 47–48

Related papers

Loading 1711.03908v1…