PaperlayerView exact revision on arXiv

Source-linked AI summary

One-Shot Private Confidence Regions via Resampling

Shourya Pandey, Purnamrita Sarkar, Po-Ling Loh, Debepsita Mukherjee

arXiv:2610.08460v1stat.MLcs.CR

TL;DR

Resampling can estimate confidence-region quantiles without model-specific variance formulas, but privatizing statistics across many resamples accumulates privacy loss. This paper adds noise to the final resampling quantile instead, with privacy loss logarithmic in B for with-replacement sampling and independent of B for subsampling. It provides nonasymptotic privacy and utility guarantees for supported estimator classes and resampling schemes.

  • Problem

    Resampling-based confidence regions use quantiles, but releasing statistics from many resamples incurs privacy loss that grows with B.

    Source: §1 · p. 4

  • Method

    The method adds noise once to the final resampling quantile rather than privatizing each resample statistic.

    Source: §1 · p. 4, §4 · p. 12

  • Results

    The approach provides nonasymptotic privacy and utility guarantees, with privacy loss logarithmic in B for with-replacement sampling and independent of B for subsampling.

    Source: §1.2 · p. 7, §8 · p. 24

  • Takeaways & Limitations

    The framework provides private uncertainty quantification for common resampling schemes without privatizing many intermediate resample statistics.

    Source: §8 · p. 24

    The smooth-sensitivity results concern estimators with efficiently computable bounds that are small with high probability over the data.

    Source: §1.1 · p. 6

Abstract

from arXiv · show

We propose a simple framework for constructing differentially private confidence regions \textit{in one shot}, i.e., by adding noise only to the final resampling quantile instead of privatizing the estimator computed on each resample. The cost of privacy of our procedure is only logarithmic in the number of resamples $B$ under with-replacement ($m$-out-of-$n$) sampling and independent of $B$ under without replacement sampling (subsampling), avoiding the $\sqrt{B}$ factor that arises in previous works. We provide nonasymptotic Gaussian Differential Privacy (GDP) and utility guarantees for both subsampling and $m$-out-of-$n$ resampling, covering mean-like estimators with small global sensitivity as well as estimators admitting efficiently computable smooth sensitivity bounds, including quantiles and degenerate U-statistics. This allows us to also obtain private confidence regions for degenerate U-statistics where the private error is much smaller than the non-private error. In all, we provide a toolbox for widely applicable DP uncertainty quantification procedures under popular resampling strategies while avoiding the computational and privacy costs of privatizing many intermediate resample statistics.

1 Introduction

Resampling estimates confidence-region quantiles without model-specific variance formulas or asymptotic normality, but privatizing many resample statistics incurs privacy costs that grow with the number of resamples. The paper instead privatizes the final quantile, with privacy loss growing logarithmically in B and utility guarantees for estimator classes including mean-like and smooth-sensitivity-friendly estimators.

1 Introduction

  • Resampling estimates confidence-region quantiles without requiring analytic variance formulas or model-specific asymptotic normality assumptions.The ordinary bootstrap can be computationally intensive and inconsistent in some settings; subsampling and m-out-of-n methods cover broader validity conditions.Source: §1 · p. 4
  • The final-quantile approach replaces privacy costs that accumulate across resamples with privacy loss growing only logarithmically in B.The paper compares this with approaches that privatize each resample or use private threshold search.Source: §1 · p. 4

1.1 Our contributions

  • The approach targets estimators with small global sensitivity or efficiently computable smooth-sensitivity bounds, including quantiles and degenerate U-statistics.The ordinary nonparametric bootstrap can be inconsistent for degenerate U-statistics.Source: §1.1 · p. 6

1.2 Comparison with existing works

  • For m close to n, the method’s squared-length penalty depends on the resampling overlap quantity rather than the linear-in-B factors paid by [DG25] and [SSVHL25].The stated comparison is for the privacy penalty; Table 1 covers mean squared radius and computational considerations for with-replacement sampling.Source: §1.2 · pp. 7–8, Table 1 · p. 7

2 Related Work

Prior private inference work includes methods for asymptotically normal estimators, finite-sample guarantees in selected settings, and private bootstrap procedures. The paper situates its resampling approach against these strands of work.

2 Related Work

  • Earlier work studies private estimators with asymptotic efficiency and uncertainty methods whose utility is often evaluated empirically or justified under restrictive asymptotic assumptions.Finite-sample guarantees have been established in selected settings, including regression confidence intervals and discrete-distribution hypothesis tests.Source: §2 · pp. 8–9
  • Private confidence intervals for Gaussian means have finite-sample coverage guarantees and expected-length lower bounds, while zero-concentrated privacy permits conservative intervals by post-processing bootstrap replicates.The cited bootstrap result incurs no additional privacy cost beyond releasing the point estimator.Source: §2 · p. 9
  • A parametric private-bootstrap method simulates datasets from a fitted private model, reruns the private estimator, and proves asymptotic consistency in broad settings.The cited work states that this captures uncertainty from both sampling and the privacy mechanism.Source: §2 · p. 9

3 Preliminaries

The preliminaries frame differential privacy through distinguishability of outputs on neighboring datasets and state the assumptions used for resampling utility guarantees. Gaussian differential privacy supplies the privacy framework, while the resampling assumptions specify validity and regularity conditions.

3.1 f-Differential Privacy

  • f-differential privacy expresses privacy through hypothesis-testing distinguishability between output distributions for neighboring datasets.The paper defines trade-off functions through the minimum type II error at a constrained type I error.Source: §3.1 · pp. 9–10

3.1.1 Gaussian Differential Privacy

  • Gaussian differential privacy benchmarks neighboring-dataset outputs against distinguishing N(0, 1) from N(µ, 1), and the Gaussian mechanism adds noise scaled to global sensitivity.GDP also admits an exact composition rule for mechanisms released as a joint transcript.Source: §3.1.1 · pp. 10–11

3.2 Assumptions on subsampling and m-out-of-n sampling

  • Utility results assume standard subsampling conditions, including a non-degenerate continuous limiting distribution and resampling validity at the target quantile.The stated assumptions can be checked with probabilistic arguments for subsampling and m-out-of-n sampling.Source: §3.2 · pp. 11–12

4 Private confidence regions for mean-like estimators

The section constructs private confidence regions by privatizing the final resampling quantile and full-sample estimator, rather than the individual resample estimates. For with-replacement sampling, it controls quantile sensitivity through a bound on resample multiplicities, then establishes privacy and utility guarantees for CR-GS.

4 Private confidence regions for mean-like estimators

  • CR-GS computes resampling errors without releasing individual resample estimates, then separately perturbs the full-sample estimator and final empirical quantile.It supports both with- and without-replacement resampling.Source: §4 · p. 12, §4.2 · pp. 14–15
  • The section covers estimator classes with global sensitivity scaling as ℓ_n/n, including bounded averages, Lipschitz transforms, and strongly convex regularized M-estimators.The examples also include bounded-kernel U-statistics.Source: §4 · pp. 12–13

4.1 Bounding the multiplicity for sampling with replacement

  • With replacement, one observation can occur multiple times in a resample, making its effect on the resampling quantile depend on the maximum multiplicity.A high-probability bound controls multiplicity across all B resamples; its stated size is sub-logarithmic in B and n.Source: §4.1 · pp. 13–14

4.2 Algorithm for mean-like estimators

  • Theorem 4.2 states that Algorithm 2 (CR-GS) is µ-GDP; its utility result applies when Assumptions 3.8 hold, with failure probability ρ = on(1) and γ = on(1).Source: §4.2 · p. 16

5 Private confidence regions for S-friendly estimators

This section extends private confidence regions to estimators with efficiently computable smooth-sensitivity bounds. It develops a Gaussian PTR mechanism and CR-SS, with privacy and utility guarantees for the resulting regions.

5.1 Approximate Gaussian Differential Privacy

  • Approximate GDP allows a small total-variation perturbation of one output distribution, and its privacy parameters compose across adaptive releases.The composition rule combines squared µ parameters and multiplies the complements of the δ parameters.Source: §5.1 · p. 16

5.2 Smooth sensitivity and Propose-Test-Release (PTR)

  • PTR-GDP uses Gaussian noise to privatize a smooth upper bound on local sensitivity and yields approximate µ-GDP when that bound is computable.Smooth sensitivity can be much smaller than global sensitivity on typical datasets, and it is efficiently computable for some quantiles and U-statistics.Source: §5.2 · p. 17

5.3 Private confidence regions for S-friendly estimators in Definition 1.2

  • CR-SS privatizes the full-data center and resampling quantile using PTR-GDP, with the quantile sensitivity bounded using smooth sensitivities from the resamples.Theorem 5.6 states (µ, δ)-GDP and controls the confidence radius using a high-probability upper bound on estimator smooth sensitivity.Source: §5.3 · pp. 17–19

6 Applications

The applications use smooth-sensitivity bounds to construct private intervals for population quantiles and degenerate U-statistics. For quantiles, privacy adds an overhead to the resampling radius; for degenerate U-statistics, the stated privacy overhead is asymptotically smaller than the non-private error.

6.1 Confidence intervals for population quantiles

  • Quantile intervals use smooth sensitivity bounded through nearby order-statistic spacings, under a density lower bound around the target quantile.The confidence radius is the non-private resampling radius plus a Gaussian privacy overhead of ˜O(1/√mn).Source: §6.1 · p. 19

6.2 Degenerate U-statistics

  • Degenerate U-statistics are relevant to tests and subgraph counts, and the ordinary nonparametric bootstrap can be inconsistent for their limiting distribution.The section uses m-out-of-n subsampling for private asymptotically valid intervals in this setting.Source: §6.2 · p. 20
  • For first-order degenerate bounded kernels, CR-SS yields an asymptotically valid confidence interval under Assumption 3.8 and Theorem 5.6’s sensitivity conditions.For fixed r, C, and privacy parameters, the non-private radius is order n^-1 while the privacy overhead is order eO((n√m)^-1), hence asymptotically smaller as m grows.Source: §6.2 · pp. 20–21

7 Experiments

The experiments compare private confidence intervals for bounded means, a degenerate U-statistic, and a population median across resampling methods. Reported coverage findings distinguish the mean and U-statistic settings; the median passage gives its experimental setup.

7 Experiments

  • Experiments use 400 datasets per sample size, B = 500 resamples, nominal coverage 0.90, and total privacy parameter µ = 8; Figure 1 reports mean runtime across three problems.The bounded-mean table reports coverage, mean interval width, and runtime; its width values are scaled by 10^3.Source: §7 · p. 21, Figure 1 · p. 21, Table 3 · p. 22

7.1 Mean estimation

  • In the skewed Bernoulli mean experiment, BLBQuant and CR-GS achieve near-nominal coverage for smaller sample sizes.Source: §7.1 · pp. 22–23

7.3 Median

  • The median experiment targets the Uniform[−1, 1] population median of 0 and uses √n scaling for the empirical median.For CR-SS, m = ⌈n/log n⌉; the described WR and WOR settings use miscoverage parameters 0.09 and 0.10, respectively.Source: §7.3 · p. 24

7.2 Degenerate U-statistic

  • For the degenerate U-statistic, m-out-of-n bootstrap and BLBQuant overcover, while the proposed methods are closer to nominal 0.9 coverage.The text attributes the closer coverage to adapting to the statistic’s natural τ_n = n scaling.Source: Table 4 · p. 23, §7.3 · p. 24, §7.2 · p. 24

8 Conclusion

The conclusion presents a one-shot approach that privatizes the resampling quantile rather than the statistics from individual resamples, with privacy dependence logarithmic in B instead of B-type accumulation. The auxiliary result establishes a local-sensitivity bound for an order statistic.

8 Conclusion

  • The proposed confidence-region method privatizes the resampling quantile and replaces B-type privacy dependence with logarithmic dependence on B.The conclusion also reports nonasymptotic privacy and utility guarantees and says the approach avoids privatizing many intermediate resample statistics.Source: §8 · p. 24

A Auxiliary Results

  • For an order statistic of B mechanisms, its local sensitivity is bounded by the maximum local sensitivity among those mechanisms.The proof bounds changes in the kth-largest value by the largest change among the inputs.Source: A Auxiliary Results · p. 29

B More details on subsampling validity results for m-out-of-n and subsampling

This appendix establishes validity results for subsampling and with-replacement m-out-of-n procedures under convergence and quantile conditions, including a subsampling bound obtained by transferring a Gaussian trade-off guarantee through a distribution within total variation distance δ. It also compares the squared-length privacy penalty with repeated privatization and provides a GDP guarantee for Algorithm 2.

B More details on subsampling validity results for m-out-of-n and subsampling

  • Subsampling coverage is 1−α+o(1), while with-replacement m-out-of-n resampling is consistent when m→∞, m/n→0, and τm/τn→0 under the stated regularity conditions.Quantile convergence and an empirical quantile based on B resamples yield the validity condition as B→∞.Source: B More details on subsampling validity… · p. 30

B.1 Proof of Proposition 4.1

  • The Proposition 4.1 proof controls with-replacement sample multiplicities using a Bin(m, 1/n) Chernoff bound and a two-regime lower bound on g(M).It splits at M=4 log 4 and uses convexity for the smaller regime and log M≤M/2 for the larger regime.Source: §B.1 · pp. 31–32

C Comparison with related works

  • κ⋆=O(log(Bn)) with replacement and κ⋆=1 without replacement, replacing B-type accumulation with logarithmic dependence on B in the squared-length penalty.For m close to n, the prior approach pays essentially a factor linear in B, whereas this procedure’s penalty depends on κ⋆².Source: C Comparison with related works · p. 34

D Privacy and Utility for CR-GS

E.1 Proof of Proposition 5.1

  • T(P,Q)(α) ≥ max{G_mu(α) - δ, 0} = G_mu,δ(α) when T(P,R) ≥ G_mu and TV(Q,R) ≤ δ.Total variation bounds the difference in test expectations by δ; taking the infimum over tests with Type I error at most α yields the bound.Source: §E.1 · p. 39

E.2 Proof of Proposition 5.3

These proofs establish composition and sensitivity bounds used in the privacy analysis: sequential GDP mechanisms compose, while resampling multiplicity controls sensitivity growth. The final proof applies these bounds to the privacy of the proposed procedure.

E.2 Proof of Proposition 5.3

  • Sequential GDP mechanisms compose by combining their privacy parameters, and Proposition 5.3 follows by repeated application of the composition result.Source: §E.2 · pp. 39–40

E.3 Proof of Lemma 5.4

  • PTR-GDP uses a smooth-sensitivity-based bound that upper-bounds local sensitivity with probability at least 1 − δ.The proof also states that the resulting bound mechanism is µ-GDP.Source: §E.3 · p. 42

F.1 Proof of Lemma 5.5

  • When a resampled dataset contains at most κ⋆ copies of a modified point, β-smooth sensitivity bounds its local sensitivity by a factor governed by κ⋆.The proof bounds the growth by e^(qβ) after q adjacent-dataset changes.Source: §F.1 · p. 42

F.2 Proof of privacy of Theorem 5.6

  • The privacy proof accepts only resampling-index realizations satisfying the multiplicity constraint, then applies two PTR-GDP calls and post-processing.The indices and accept/reject decision are data-independent, and dropping the indices is post-processing.Source: §F.2 · p. 43

F.3 Proof of utility of Theorem 5.6

The proofs bound the quantile’s smooth sensitivity and establish when auxiliary outputs agree with Algorithm 4. For quantiles, the sensitivity argument uses an order-statistic window around the target index.

F.3 Proof of utility of Theorem 5.6

  • With failure probability at most ρ=o_n(1), the auxiliary outputs agree with Algorithm 4 whenever the multiplicity check succeeds.This is the proof’s link between the auxiliary-output utility argument and the algorithm’s actual outputs.Source: §F.3 · p. 45

G Proofs for Confidence Intervals of Quantiles (Section 6.1)

G.1 Proof of Lemma 6.1

  • For a quantile index that shifts by at most k positions, the worst-case order-statistic change is captured by the largest difference across that k-position window.The proof then truncates the window using k⋆ and derives a simplified bound.Source: §G.1 · pp. 45–46

G.2 Proof of Theorem G.1

The proof controls the order-statistic window around the target quantile, then applies the resulting smooth-sensitivity bound to quantify the confidence interval’s private error.

G.2 Proof of Theorem G.1

  • Mapping the samples through F gives uniform order statistics, enabling concentration bounds for the window around index h.The proof relates the window to the distribution’s quantile neighborhood under its stated assumptions.Source: §G.2 · pp. 46–47
  • With probability at least 1−4ρ, the uniform order-statistic window U(h+k)−U(h−k) is bounded by 6k/n.This window bound is used in the proof of the quantile smooth-sensitivity result.Source: §G.2 · p. 47

G.3 Calculating the confidence radius

  • ˜O(1/√(mn)) private error scale contrasts with O(1/√n) non-private quantile error; CR-SS yields an asymptotically 1−α interval with probability at least 1−8ρ.The interval half-length is the non-private radius plus Gaussian private noise.Source: §G.3 · p. 48

H Proofs for Degenerate U-statistics (Section 6.2)

The appendix applies smooth-sensitivity bounds to degenerate U-statistics and proves private confidence-region guarantees for averaged SGD. The SGD result covers both resampling modes under its stated assumptions.

H Proofs for Degenerate U-statistics (Section 6.2)

  • For degenerate U-statistics, the proof specializes the smooth-sensitivity guarantee; with its stated choice, L(D)=1 with probability at least 1−ρ and t_n,β=O_β(1/n^2) for fixed r.The cited smooth-sensitivity bound is used to characterize the private overhead of the confidence radius.Source: H Proofs for Degenerate U-statistics… · p. 49

H.1 Confidence regions for averaged SGD

  • For averaged SGD, the estimator is mean-like with ℓ_N=4G/λ conditional on the permutation, supporting the global-sensitivity analysis.The sensitivity lemma applies under the stated assumptions on the loss and optimization setup.Source: §H.1 · p. 50
  • CR-GS is µ-GDP for either resampling mode and gives asymptotic 1−α coverage under the stated conditions.Its confidence radius includes the private-noise contribution; the proof derives coverage for the actual outputs despite the multiplicity check.Source: §H.1 · pp. 51, 53

Related papers

Loading 2610.08460v1…