One-Shot Private Confidence Regions via Resampling

One-Shot Private Confidence Regions via Resampling Shourya Pandey∗

Purnamrita Sarkar†

Po-Ling Loh‡

Debepsita Mukherjee§

arXiv:2610.08460v1 [stat.ML] 6 Oct 2026

Abstract We propose a simple framework for constructing differentially private confidence regions 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 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.

∗

University of Texas at Austin, shouryap@utexas.edu University of Texas at Austin, purna.sarkar@austin.utexas.edu ‡ University of Cambridge, pll28@dpmms .cam.ac.uk § University of Texas at Austin, debepsitamukherjee@utexas.edu †

1

Contents 1 Introduction

4

1.1

Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2

Comparison with existing works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2 Related Work

8

3 Preliminaries

9

3.1

f -Differential Privacy

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2

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

11

4 Private confidence regions for mean-like estimators

12

4.1

Bounding the multiplicity for sampling with replacement . . . . . . . . . . . . . . . . . . . . . . . . . .

13

4.2

Algorithm for mean-like estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

5 Private confidence regions for S-friendly estimators

16

5.1

Approximate Gaussian Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

5.2

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

17

5.3

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

17

6 Applications

19

6.1

Confidence intervals for population quantiles

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

6.2

Degenerate U-statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

7 Experiments

21

7.1

Mean estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

7.2

Degenerate U-statistic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

7.3

Median

24

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Conclusion

24

A Auxiliary Results

29

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

29

C Comparison with related works

32

D Privacy and Utility for CR-GS

35

E Proofs of Proposition, 5.1, 5.3 and Lemma 5.4

38

2

F Proofs related to CR-SS

42

G Proofs for Confidence Intervals of Quantiles (Section 6.1)

45

H Proofs for Degenerate U-statistics (Section 6.2)

48

3

1

Introduction

Consider the problem of parameter estimation: given a dataset D of n i.i.d. samples from an unknown distribution D and a functional θ(.), the goal is to design an estimator for the target parameter θ(D). Uncertainty quantification goes beyond point estimates by providing valid confidence regions for the parameter of interest. A classical approach treats the observed dataset as a proxy for the underlying distribution, and uses it to generate many auxiliary datasets whose distributions approximate that of the original sample. The estimator is then applied to each auxiliary dataset, producing an ensemble of parameter estimates {θ̂n∗ }. These methods are broadly known as resampling methods, a standard and influential topic in statistics, such as the Quenouille-Tukey Jackknife [Que49, Tuk58], bootstrap [Efr79], subsampling [PRW99b], and m-out-of-n bootstrap [BGvZ11]. In particular, many classical confidence sets can be expressed in terms of quantiles of a suitably scaled estimation error. Resampling provides a generic plug-in approach for estimating these quantiles, avoiding the need for analytic variance formulas or asymptotic normality assumptions tailored to a specific model. Now, the nonparametric bootstrap can be computationally intensive since it requires drawing many size-n with-replacement resamples from the size-n dataset. Moreover, there are several settings in which the bootstrap is not consistent [Ath87, And00]. Roughly speaking, the √ bootstrap works when n(θ̂n −θ) is asymptotically Gaussian (see [van98a] for sufficient conditions). A more general procedure is subsampling [PRW99b] and the m-out-of-n bootstrap [BGvZ11]. These methods sample m points from the dataset of size n, with or without replacement, where m = o(n) and m = ω(1). They are valid as long as τn (θ̂n − θ) converges to some nondegenerate asymptotic distribution, for an appropriate scaling factor τn . In this paper, we study uncertainty quantification under differential privacy (DP), a problem that has received growing attention. [KV17] provides one of the first private confidence intervals for the mean under the Gaussian model and proves lower bounds on the expected length of any (1−α)-level (ε, δ)-DP confidence set. A central challenge for DP resampling is that releasing statistics from many resamples incurs privacy loss that grows with the number of resamples B through composition. Several recent works address this issue through variants of private resampling. [CDK24] uses the Bag of Little Bootstraps (BLB) [KTSJ14] on disjoint data blocks to control the sensitivity, but still privatizes each bootstrap replicate. They then apply a noisy median/order-statistic mechanism together with sparse vector/AboveThreshold [DR14] to search over a grid of candidate regions and √ return the first region achieving the target coverage. For statistics converging at the 1/ n rate, this √ approach requires at least n candidate intervals, increasing the computational cost by a factor of √ n. [DG25] analyzes m-out-of-n resampling under GDP and obtains an effective privacy loss scaling √ B. Their privacy guarantees are asymptotic and rely on the Central Limit Theorem as µtot ≈ µB m n (CLT) and composition arguments of [DRS22] together with the mixture-of-mechanisms framework of [WCA25]. [SSVHL25] obtains (ε, δ) private CIs by running a private estimator on B subsamples and combining the √ privacy loss via subsampling amplification plus (basic/advanced) composition (also incurring a B-type dependence). In contrast, we add noise only once to the final resampling quantile/radius, yielding a privacy loss that grows only logarithmically in B. How large is B? In practice, the bootstrap uses a Monte Carlo approximation based on B resamples; by the DKW inequality, supt∈R FbB (t) − F ∗ (t) = Op (B −1/2 ), so bootstrap quantiles 4

converge as B → ∞ [van98a]. Empirically, one typically takes B ≈ 1000 or 2000 for “rough” CI’s, and B ≈ 104 to make Monte Carlo error negligible [Hes15, Efr79]. In the private resampling setting, for each of s disjoint blocks of size m, [CDK24] use n n n1.5 oo B = min 10,000, max 100, . log n While distribution-privatizing methods can release many quantiles, standard resampling CIs typically use only one or two to set the endpoints. This is the motivation of our work.

1.1

Our contributions

We consider two resampling schemes and two classes of statistics for which we provide confidence regions for the relevant parameter. Resampling schemes. Two subsampling methods are particularly relevant: • Sampling without replacement (WOR) [PRW99b] Each set Si is drawn uniformly from the
n m m-element subsets of [n]. • Sampling with replacement (WR) [BGvZ11] Each multiset Si is formed by drawing m (notnecessarily-distinct) indices independently and uniformly from [n]. We consider two broad regimes of estimators for private resampling. Let D = (X1 , . . . , Xn ) denote a dataset. Let θ(.) be a functional that can be applied to the population distribution to obtain an unknown parameter of interest, or applied to the data to obtain an estimator. For an estimator θ : X n → Rd , define its (global) ℓ2 -sensitivity as ∆2 (θ) := sup θ(D) − θ(D′ ) 2 , D∼D′

where D ∼ D′ denotes neighboring datasets that differ in exactly one record. Definition 1.1 (Mean-like estimators). We call θ mean-like if ∆2 (θ) ≤ ℓn /n for some sequence {ℓn }n≥1 (typically, ℓn = C for a constant C or ℓn = polylog(n)). In DP literature, one often captures statistics with large (possibly unbounded) global sensitivity by using local sensitivity, defined as LS(θ; D) := sup θ(D) − θ(D′ ) 2 . D′ ∼D

(1)

Since the local sensitivity can itself leak privacy, one may instead compute a β-smooth upper bound SSβ (θ; ·) : X n → R+ . This function upper-bounds the local sensitivity and varies smoothly across neighbors: LS(θ; D) ≤ SSβ (θ; D)

and

SSβ (θ; D) ≤ eβ SSβ (θ; D′ ) for all D ∼ D′

[NRS07]. Equivalently, the map D 7→ log SSβ (θ; D) has global sensitivity at most β. 5

(2)

Definition 1.2 (S-friendly estimators). We call an estimator θ smooth-sensitivity-friendly if there exists a parameter β > 0 and an efficiently computable β-smooth sensitivity upper bound SSβ (θ; ·) such that, with high probability over the data, SSβ (θ; D) is small even when ∆2 (θ) is large (or unbounded). We pose the following question for both mean-like (Definition 1.1) and S-friendly (Definition 1.2) estimators: Can we design a differentially private confidence interval for a fixed coverage level, based on subsampling or m-out-of-n resampling, that uses B resamples for statistical accuracy while incurring only logarithmic growth of privacy loss in B? To answer the above question, we propose a novel approach: rather than making each resample private or performing a private iterative search, we add noise directly to the resampling quantile that determines the confidence set. A key technical point is that, under sampling with replacement, the sensitivity of the resampling-based quantile is governed by a single overlap quantity: the maximum number of times a modified data point can reappear across the resamples. Inspired by this, we propose a simple (white-box) alteration to the resampling methods that yields the same utility with a stronger privacy guarantee. The advantage of this method is that, for a large class of statistics, it yields nonasymptotic GDP privacy guarantees. Our contributions are as follows: • We provide an algorithm for privatizing confidence regions (CR) resulting from both the subsampling and the m-out-of-n resampling schemes. Our method only leads to privacy loss logarithmic in B. • Our approach is most effective in settings where the estimator has small global sensitivity (Definition 1.1), or admits a small (data-dependent) smoothed sensitivity bound (Definition 1.2). This enables constructing private CRs for a broad class of mean-like functionals including U -statistics and empirical risk minimizers for strongly convex losses, as well as nonstandard targets such as quantiles and degenerate U -statistics. Degenerate U -statistics are a canonical example where classical asymptotic normality may fail, and the usual nonparametric (Efron) bootstrap can be inconsistent [Bre83, AG92]. In such cases, consistent inference can still be obtained via m-out-of-n resampling or subsampling, which motivates our work. • We give utility guarantees that separate the non-private resampling error from the privacyinduced error and discuss how the privacy term compares to prior private bootstrap approaches that compose across B resamples or rely on DP threshold-search procedures.

1.2

Comparison with existing works

In Table 1, we compare our method to existing work. When the estimator admits an asymptotically normal distribution, bootstrap and BLB both consistently estimate its sampling distribution [Hal92, KTSJ14]. Interior sample quantiles (i.e., for quantiles between, say, the 0.05 and 0.95 quantiles) are asymptotically normal under mild regularity conditions [e.g. van98a]. 6

Method

√

Scale τn Nonprivate sq. radius r2 Our work [CDK24] [DG25]

Quantiles (d = 1)

Mean-like √

n

2 q1−α 1 +O n nB log2 (Bn)d r2 + mnµ2 ! √ d d 2 + 2 2 r + Õ ε n εn3/2 Bmd r2 + 3 2 n µ





n

2 q1−α 1 +O n nB log2 (Bn) r2 + mnµ2





Degenerate U -stats (d = 1)

# Nonasymp. Resamples Privacy?

n

—

—

0

—

B

Yes

2 q1−α 1 +O 2 n2 n B log2 (Bn) r2 + mn2 µ2





Empirical

×

√ B n

Yes

×

×

B

No

Table 1: Comparison of the mean squared radius of the confidence region across estimator classes, and computational considerations for WR-sampling. We note that [SSVHL25]’s algorithm is similar to that of [DG25] and so we exclude it for brevity. For simplicity, for mean-like statistics we assume √ the global sensitivity to be Θ(ℓ/n) for ℓ = d. The results of [CDK24] for quantile estimation are empirical; Moreover, their paper assumes the resamples to be private already. Likewise, the method of [CDK24] to quantify uncertainty privately applies to a large family of mean-like estimators and quantiles. Since BLB-Quant privatizes each resample, the length of the confidence interval depends on the privacy budget. Also, while this method achieves the lower √ bound for Gaussian means [KV17], it can be computationally expensive, requiring O(B n) resample evaluations (cf. Table 1). [DG25] analyze private m-out-of-n resampling for estimators with global sensitivity of the form O(ℓ/n). Let q1−α be the target non-private resampling quantile of the pivot τn d(θbn , θ), so the 2 leading squared confidence radius (non-private) is 4q1−α /τn2 . Ignoring truncation at zero, with some regularity conditions on the resampling distribution (see Lemma C.1 in the Appendix), the non-private confidence radius r(α) satisfies 4q 2 E[r(α) ] = 1−α +O τn2 2



1 Bτn2

 .

Our method. Algorithm 2 forms the empirical resampling quantile Qn,m , privatizes it once, e n,m = max{Qn,m + σm Z, 0} for Z ∼ N (0, 1) and reports θen ± Qen,m . For comparison, we isolate the Q τn contribution of the noisy quantile. For mean-like statistics with global sensitivity ∆m on samples of size m, σm = τm κµ⋆ ∆m , up to universal constants using Theorem 4.2. Therefore   4q 2 EZ Lenours (α)2 ≈ 1−α +O τn2



1 Bτn2

 +

2 κ2 ∆2 4τm ⋆ m . τn2 µ2

Since κ⋆ = O(log(Bn)) under with-replacement sampling and κ⋆ = 1 under sampling without √ replacement, our procedure replaces the B-type accumulation from repeatedly privatizing resample √ statistics by a logarithmic dependence on B in the squared-length penalty. In the n-regime, where 7

Category

Condition

Role

If the condition fails

Classical resampling

Classical resampling validity

Makes Qn,m approximate the target quantile

The non-private CI may Use estimator-specific be miscalibrated resampling theory

Choice of m

Controls the quality If m is too small, of the resampling subsampled estimators approximation are poor in quality; if m is too close to n, classical resampling validity fails

To start, use m ≈ nη , e.g. η ∈ [0.7, 0.8] (this works well for m-out-of-n and subsampling in [KTSJ14])

Choice of B

Larger B reduces Monte Carlo error

If B is small, the estimated CIs may be more variable

Increase B subject to computational constraints

Density bounded below near the target quantile (e.g. median)

Controls nearby order-statistic spacings and hence the smooth sensitivity

Private noise may be large

Low-density regions and tail quantiles are more challenging

Smooth sensitivity scales as o(1/τn )

Makes the private noise negligible

Still private, but nominal coverage not guaranteed

Use global/smooth sensitivity bounds as applicable

Enables one-shot privatization of the final resampling quantile

Our framework may not apply directly

Use a problem-specific DP method (e.g. DP-SGD)

Privacy

Applicability Tractable and small global or smooth sensitivity

Practical recommendation

Table 2: Conditions and practical recommendations for private resampling confidence intervals. τn =

√

n, τm =

√

m, and ∆m = ℓ/m, the privacy term becomes ∆ours ≈

4κ2⋆ ℓ2 . mnµ2

Thus, for m close to n our approach pays only through κ2⋆ , whereas the approaches of [DG25] and [SSVHL25] pay a factor linear in B. Appendix section C has more details on the entries of Table 1, and Appendices G as well as H explain the table entries for confidence lengths for quantiles and degenerate U-statistics.

2

Related Work

Resampling poses additional challenges under differential privacy, since privatizing statistics computed on many resamples leads to privacy losses that accumulate under composition. [Smi11] shows that for a broad class of asymptotically normal estimators, one can construct differentially private 8

estimators that converge to the same asymptotic distribution as their non-private counterparts. As a result, differential privacy can be achieved with no asymptotic loss in statistical efficiency, including for parametric estimation and regression problems. Several methods have been proposed in [VS09, WM10, KS12, VKK14, VKS15, KS16, KSGB23, YWJK15, KR16] to account for the combined uncertainty due to sampling variability and the additional noise introduced for privacy in differentially private algorithms. However, the utility of these approaches—measured, for example, by the expected length of confidence intervals or the power of hypothesis tests—is generally evaluated empirically, or their conservativeness is established only under restrictive asymptotic assumptions. Finite-sample guarantees for conservative differentially private inference have been established in a limited number of settings. In particular, [She17] studies confidence intervals for ordinary leastsquares regression coefficients, which may be interpreted as a multivariate Gaussian generalization of the problem considered here, and [CBP17] consider hypothesis testing for discrete distributions. [BH18] showed that, under zero-concentrated differential privacy, bootstrap-based estimation of standard errors can be performed without additional privacy cost beyond that of releasing the point estimator. This allows the construction of conservative confidence intervals via post-processing of bootstrap replicates. [KV17] study the construction of differentially private confidence intervals for the mean of a normal distribution, providing explicit finite-sample coverage guarantees for both known and unknown variance cases. They also establish lower bounds on the expected length of any DP confidence interval, showing near-optimal privacy–utility tradeoffs without assuming bounded data. [FWS22] fit a (DP) estimator once, then simulate synthetic datasets from the fitted parametric model, re-run the (private) estimator on simulated data, and form a CI from the bootstrap distribution. They explicitly argue that it captures uncertainty from both sampling and the DP mechanism, and prove asymptotic consistency in broad settings (including a special adaptation for linear regression).

3

Preliminaries

3.1

f -Differential Privacy

Given a positive integer n and domain X , a dataset D of size n is a finite collection of n elements from X . Two datasets are neighbors if they differ in exactly one element. Throughout this paper, we consider randomized algorithms whose input is a dataset D ∈ X n and output lies in a measurable space Y. A mechanism (or algorithm) is a randomized function A : X n → Y. Formally, such an algorithm induces, for each dataset D, an output distribution A(D) on Y. The notion of differential privacy we consider is f -differential privacy [DRS22], which is based on hypothesis testing between pairs of output distributions. Suppose P and Q are two probability distributions on Y. Given an observation Y drawn from either P or Q, consider the hypothesis testing problem with null and alternative hypotheses H0 : Y ∼ P ; H1 : Y ∼ Q, respectively. A test is any (possibly randomized) function ϕ : Y → {0, 1}. The type I error αϕ := EY ∼P [ϕ(Y )] of a test ϕ is the probability that the test outputs 1 when Y ∼ P , thereby 9

incorrectly concluding that Y was drawn from Q, and the type II error βϕ := EY ∼Q [1 − ϕ(Y )] of the test ϕ is the probability that the test outputs 0 when Y ∼ Q, thereby incorrectly concluding that Y was drawn from P . Definition 3.1 (Trade-Off function). Given two probability distributions P and Q on the same measurable space X , the trade-off function between P and Q is the function T (P, Q) : [0, 1] → [0, 1] defined as T (P, Q)(α) = inf βϕ . ϕ:αϕ ≤α

A function f : [0, 1] → [0, 1] is called a trade-off function if f = T (P, Q) for some distributions P and Q on the same measurable space. By an abuse of notation, for random variables X and Y , we write T (X, Y ) for the trade-off function between their distributions. Proposition 3.2 ([DRS22]). A function f : [0, 1] → [0, 1] is a trade-off function (between some two distributions P and Q) if and only if f is convex, continuous, and non-increasing in [0, 1], and satisfies f (α) ≤ 1 − α for α ∈ [0, 1]. Proposition 3.2 characterizes the functions that can arise as trade-off functions, and hence the functions that can serve as benchmarks for indistinguishability. To apply this hypothesis-testing framework to privacy, consider a randomized algorithm A whose input is a dataset. Each dataset D induces a distribution over outputs, represented by the random variable A(D). For neighboring datasets D and D′ , the trade-off function T (A(D), A(D′ )) describes how well an observer can distinguish the corresponding output distributions. Definition 3.3 (f -differential privacy). Let f : [0, 1] → [0, 1] be a trade-off function. An algorithm A is f -DP if for all neighboring datasets D and D′ and all α ∈ [0, 1], T (A(D), A(D′ ))(α) ≥ f (α). In other words, if f = T (P, Q) for distributions P and Q, then distinguishing between (the outputs of) any two neighboring datasets is at least as difficult as distinguishing between the distributions P and Q based on a single sample. f -differential privacy captures the standard notion of central privacy [Dwo06, DRS22]. Definition 3.4 ((ε, δ)-DP). For any ε ≥ 0 and δ ∈ [0, 1], algorithm A is (ε, δ)-DP if and only if it is fε,δ -DP, where fε,δ (α) := max{1 − δ − eε α, e−ε (1 − δ − α), 0} 3.1.1

∀α ∈ [0, 1].

Gaussian Differential Privacy

Gaussian differential privacy [DRS22] (GDP) measures privacy by comparing the distinguishability of the outputs on neighboring datasets to a canonical Gaussian hypothesis-testing problem. Let µ ≥ 0, and consider the problem of distinguishing between the distributions P = N (0, 1)

and 10

Q = N (µ, 1).

The corresponding trade-off function Gµ := T N (0, 1), N (µ, 1) has the explicit form
Gµ (α) = Φ Φ−1 (1 − α) − µ for all α ∈ [0, 1], where Φ denotes the CDF of the standard normal distribution.1 An algorithm A is said to be µ-GDP if distinguishing the outputs of A on neighboring datasets is no easier than distinguishing N (0, 1) from N (µ, 1) using a single sample. Definition 3.5 (Gaussian Differential Privacy). For any µ ≥ 0, an algorithm A is said to be µ-Gaussian differentially private (µ-GDP) if it is Gµ -GDP. In other words, for every pair of neighboring datasets D and D′ and all α ∈ [0, 1],
T A(D), A(D′ ) (α) ≥ Φ(Φ−1 (1 − α) − µ). Privacy composition. Gaussian differential privacy admits an exact composition rule. Let Yi = Ai (D; Y1 , . . . , Yi−1 ),

i = 1, . . . , k,

be the outputs of k mechanisms A1 , . . . , Ak and suppose that, for every fixed realization y1:(i−1) of the previous outputs, the conditional mechanism D 7→ Ai (D; y1 , . . . , yi−1 ) is µi -GDP. Then, the mechanism A that releases the joint transcript Y1:k = (Y1 , . . . , Yk ) is µ-GDP with q µ = µ21 + · · · + µ2k . (3) Proposition 3.6 (Equivalence between GDP and DP). For any µ > 0, an algorithm A is µ-GDP if and only if it is (ε, δµ (ε))-DP for all ε ≥ 0, where     ε µ ε µ ε δµ (ε) = Φ − + −e Φ − − . µ 2 µ 2 Proposition 3.7 (Gaussian mechanism). Suppose A : X n → Rd has ℓ2 -global sensitivity at most ∆, that is, ∥A(D) − A(D′ )∥2 ≤ ∆ for all neighboring datasets D and D′ . Then, for any µ > 0, the mechanism à that samples Z ∼ N (0, Id ) and outputs Ã(S) = A(S) +

∆ ·Z µ

is µ-GDP.

3.2

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

For all our utility results, we will need the following standard assumptions from [BGvZ11, PRW99b]. √ Let τn be a scaling factor (typically, it is equal to n). Let Fn (t) := P (τn d(θbn , θ) ≤ t) and F (t) := limn→∞ Fn (t) denote the CDF of the empirical distribution and the limiting distribution respectively. For x, y ∈ Rd , we use d(x, y) = ∥x − y∥2 . For each α ∈ [0, 1], the test ϕα that rejects the null if and only if the observed sample exceeds Φ−1 (1 − α) has type I error α and achieves the minimum type II error Φ(Φ−1 (1 − α) − µ). 1

11

Assumption 3.8. We assume that 1. F is non-degenerate and continuous. 2. supt |Fn (t) − F (t)| → 0. 3. τm /τn → 0, m/n → 0, and B → ∞. 4. (Resampling validity.) P(τn d(θbn , θ) ≤ Qn,m ) = 1 − α + on (1), where Qn,m denotes the scaled p quantile defined in Algorithm 2. In particular, Qn,m → F −1 (1 − α). These assumptions can be verified using straightforward probabilistic arguments for both m-out-of-n sampling and subsampling. For completeness, we provide a detailed discussion in Appendix B.

4

Private confidence regions for mean-like estimators

In this section, we develop a one-shot procedure for constructing differentially private confidence regions for the mean-like estimators introduced in Definition 1.1. Our construction applies to both sampling without replacement and m-out-of-n sampling with replacement. As in standard resampling-based inference, we compute the estimator on the full dataset and on B resamples of size m, and use an empirical quantile of the resulting resampling errors to determine the radius of the confidence region. The main difference is that we do not privatize the individual resample estimates. Instead, we add noise only to the final resampling quantile, together with a separate perturbation of the full-sample estimator. A technical issue that arises is controlling the sensitivity of this empirical quantile. Under sampling without replacement, a changed observation can appear at most once in each resample. Under sampling with replacement, the same observation may occur multiple times, and the sensitivity is governed by the maximum multiplicity of any original observation within the resamples. We first give several examples of mean-like estimators. We then establish a high-probability bound on the maximum multiplicity under with-replacement sampling and introduce a multiplicity-conditioned sampling procedure. Finally, we present the resulting confidence-region algorithm CR-GS and establish its privacy and utility guarantees. Several standard classes of estimators satisfy the sensitivity condition ∆2 (θn ) ≤ ℓn /n in Definition 1. We state three representative examples. (i) Bounded averages and their Lipschitz transforms. Suppose n

1X θn (D) = ψn (Xi ) ∈ Rd n

and ∥ψn (x)∥2 ≤ Rn,d ∀x,

i=1

where D is the dataset {X1 , X2 , . . . , Xn }. Then, for any neighboring datasets D and D′ , ∥θn (D) − θn (D′ )∥2 ≤ 2Rn,d /n. It follows that ∆2 (θn ) ≤ 12

2Rn,d . n

For instance, if ψ is the identity function (capturing the mean-estimation problem) and √ ∥Xi ∥∞ ≤ cn for all i, then Rn,d = 2cn d. This can also be applied to light-tailed distributions by first clipping the data: for instance, if it is known that with vari√ the Xi ’s are sub-Gaussian √ 2 2 ance proxy σproxy , we can clip each coordinate at σproxy log n to get Rn,d = Θ(σproxy d log n). ℓ2 -Lipschitz functions of averages also have global sensitivity of the same form with the sensitivity multiplied by the Lipschitz constant; if g is L-Lipschitz in the ℓ2 norm, then ∆2 (g ◦ θn ) ≤

2LRn,d . n

(ii) Strongly convex regularized M -estimators. Let ℓ(·; x) be a convex loss function which is GLipschitz in y (in the ℓ2 norm). Then, the M -estimator ) ( n λ 1X 2 ℓ(y; Xi ) + ∥y∥2 , θ(D) = arg min n 2 y∈Rd i=1

has global sensitivity ∆2 (θ(D)) ≤ 2G/λn (see Lemma 7 in [CMS11]). (iii) U -statistics with a bounded kernel. Let  −1 n θn (D) = r

X

hn (Xi1 , . . . , Xir )

1≤i1 <···<ir ≤n

be a U -statistic of order r, where r may depend on n. Suppose the range of hn has ℓ2 -diameter at most bn , that is, supz,z ′ ∈X r ∥hn (z) − hn (z ′ )∥2 ≤ bn .
Note that changing one observation affects at most n−1 r−1 of the summands. Therefore,    n − 1 n −1 rbn ∆2 (θn ) ≤ bn = . r−1 r n Thus, θn is mean-like with ℓn = rbn .

4.1

Bounding the multiplicity for sampling with replacement

Under with-replacement sampling, an index j ∈ [n] may appear multiple times in a subsample S. Even if D and D′ differ only on the data point Xj , the resampled datasets D[S] = {Xi }i∈S and D′ [S] can differ in as many as m entries; if κ(S) is the maximum multiplicity of any data point in S and ∆m is the global sensitivity of θ on datasets of size m, then the worst-case change on one subsample can be ∆m κ(S), which is large in the worst case. To control the sensitivity uniformly over B subsamples S1 , . . . , SB , we work on the event that all κ(Si ) ≤ κ∗ , for i ∈ [B]. Under this event, D[Si ] and D′ [Si ] differ in at most κ⋆ data points. Proposition 4.1 (Multiplicity bound for sampling with replacement). Let m < n, B ∈ Z+ , and ρ ∈ (0, 1). For each i ∈ [B], suppose we draw Si = {Si,t }t∈[m] , where Si,t are iid draws from [n], independently across i. Let κ(Si ) := max #{t ∈ [m] : Si (t) = j}, j∈[n]

13

and Eκ := ∩B i=1 {κ(Si ) ≤ κ}. Then, the constant ( &

)  −1 '  n Bn Bn κ⋆ (n, m, B, ρ) := min m, log · W0 log −1 ρ me ρ

(4)

satisfies P(Eκc⋆ ) ≤ ρ.2 To get an idea for the size of κ⋆ in Proposition 4.1, let A := log(Bn/ρ) and M := log(An/m). Then, W0 (An/me) = M − 1 − log(M − 1) + o(1). For M ≥ 2, this implies   log(Bn/ρ) , κ⋆ = Θ log(n/m) + log log(Bn/ρ) which is sub-logarithmic in both B and n. The proof of Proposition 4.1 is deferred to Appendix B. Algorithm 1 generates B m-out-of-n withreplacement indices S1 , . . . , SB and returns failure iff some j ∈ [n] is sampled more than κ times in some Si . By Proposition 4.1, the algorithm fails with probability at most ρ if κ ≥ κ⋆ (n, m, B, ρ). Algorithm 1 Multiplicity-Conditioned m-out-of-n Sampling Input: Sample size n, resample size m, number of resamples B, threshold κ for i ← 1 to B do iid

Draw the multi-set Si = {Si1 , . . . , Sim }, where Si1 , . . . , Sim ∼ Unif([n]) κi ← maxj∈[n] {t ∈ [m] : Sit = j} if κi > κ then return ⊥ end end return (S1 , . . . , SB )

4.2

Algorithm for mean-like estimators

We now present CR-GS, a procedure for constructing differentially private confidence sets using subsampling-based quantile estimation when the statistic θ has bounded global ℓ2 -sensitivity. Let θbn = θ(D) be the estimator computed on the full dataset, and let ∆n and ∆m denote the global sensitivities of θ on datasets of sizes n and m, respectively. CR-GS proceeds as follows: 1. Draw B resamples S1 , . . . , SB of size m each. For sampling without replacement, set κ⋆ = 1. For sampling with replacement, set κ⋆ = κ⋆ (n, m, B, ρ) (equation (4)) and accept the resamples only when the multiplicity of every observation in every resample is at most κ⋆ . 2. Compute the resample estimates θi⋆ = θ(D[Si ]) for i = 1, 2, . . . , B. These estimates are used only in the algorithm and are not released. 2

The function W0 denotes the principal branch of the Lambert W function. For any positive real number x, W0 (x) is the unique positive real number such that W0 (x)eW0 (x) = x.

14

3. Compute the τm -scaled empirical resampling quantile   ⋆ Qn,m = τm · Quantile1−α ∥θ1⋆ − θbn ∥2 , ∥θ2⋆ − θbn ∥2 , . . . , ∥θB − θbn ∥2 . 4. Privatize the center and the radius by releasing θen = θbn + νn Z2 ,

e n,m = max{Qn,m + σm Z1 , 0}, Q

where Z1 ∼ N (0, 1) and Z2 ∼ N (0, Id ) are independent, and the noise scales νn and σm are calibrated to the sensitivities of the full-sample estimator and the resampling quantile, respectively. 5. Return the confidence region ( Cn,α =

e n,m Q u ∈ Rd : ∥u − θen ∥2 < τn

) .

The sensitivity of each resampling distance ∥θi⋆ − θbn ∥2 is at most κ⋆ ∆m + ∆n . Consequently, the empirical quantile has the same sensitivity bound, since any order statistic is 1-Lipschitz with respect to the maximum change in its inputs. Thus, up to the allocation of the privacy budget between the
center and the radius, the required noise scale for the quantile is proportional to τm κ⋆ ∆m + ∆n . Algorithm 2 Confidence Regions via Global Sensitivity (CR-GS) Input: Dataset D, GDP parameter µ, functional θ(·), confidence parameter α, global sensitivity ∆(·), scale function τ (·), number of subsamples B, subsample size m, failure probability ρ, subsampling mode Mode ∈ {WR, WOR}) if Mode = WR then κ⋆ ← κ⋆ (n, m, B, ρ) of equation (4) (S1 , S2 , . . . , SB ) ← MCS(n, m, B, κ⋆ ) if (S1 , S2 , . . . , SB ) = ⊥ then return ⊥ end end

if Mode = WOR then κ⋆ ← 1 (S1 , S2 , . . . , SB ) ← Subsample(n, m, B) end

θbn ← θ(D) for i ← 1 to B do θi∗ ← θ(D[Si ]) end

▷ Estimator on full dataset

  ⋆ −θ bn ∥2 Qn,m ← τm Quantile1−α ∥θ1⋆ − θbn ∥2 , . . . , ∥θB

▷ Empirical quantile (scaled)

Z1 ∼ N (0, 1); Z2 ∼ N (0, Id ) √ n θen ← θbn + νn Z2 , where νn = 2∆ µ e n,m ← max(Qn,m + σm Z1 , 0), where σm = Q

▷ Resample estimates

√

2τm (κ⋆ ∆m + ∆n ) µ

e n,m ) return (θen , Q 15

e n,m ) of Theorem 4.2 (Privacy and utility of CR-GS). Algorithm 2 is µ-GDP. The output (θen , Q Algorithm 2 satisfies   1 e P ∥θ − θen ∥2 < Q n,m = 1 − α + on (1), τn as p long as assumptions√3.8 p hold, the failure probability γ := √ ρ = on (1), and γ = on (1), where √ σm 2 log(1/ρ) + τn νn ( d + 2 log(1/ρ)). Here, σm = 2τm µ−1 (κ⋆ ∆m + ∆n ) and νn = 2µ−1 ∆n . The confidence radius has a private overhead with scale τn−1 σm = Θ(τm τn−1 µ−1 (κ⋆ ∆m + ∆n )). The proof of Theorem 4.2 can be found in Appendix D.

5

Private confidence regions for S-friendly estimators

5.1

Approximate Gaussian Differential Privacy

µ-GDP requires the output distributions on neighboring datasets to be at least as difficult to distinguish as the Gaussian pair N (0, 1) and N (µ, 1). We consider an approximate version in which one of the output distributions may first be perturbed by a small amount δ in total variation. For µ ≥ 0 and δ ∈ [0, 1), define the trade-off function Gµ,δ (α) := max{Gµ (α) − δ, 0},

α ∈ [0, 1].

(5)

The following proposition gives an interpretable, equivalent definition of this trade-off function. Proposition 5.1 (Equivalent characterizations of approximate GDP). Let P and Q be probability e µ,δ if and only if there exists a distributions on the same measurable space. Then T (P, Q) ≥ G probability distribution R such that T (P, R) ≥ Gµ

and

TV(Q, R) ≤ δ.

Definition 5.2 (Approximate Gaussian differential privacy). A mechanism M is said to satisfy (µ, δ)-Gaussian differential privacy ((µ, δ)-GDP) if, for every pair of neighboring datasets D and D′ ,
T M(D), M(D′ ) (α) ≥ Gµ,δ (α) for all α ∈ [0, 1]. Since Gµ,0 = Gµ , (µ, 0)-GDP coincides with ordinary µ-GDP. The class of (µ, δ)-GDP mechanisms is closed under composition. Proposition 5.3 (Adaptive composition). Let Ai : X × Y1 × · · · × Yi−1 → Yi for i ∈ [k] be mechanisms such that Ai (·, y1 , y2 , . . . , yi−1 ) is (µi , δi )-GDP for every y1 ∈ Y1 , . . . , yi−1 ∈ Yi−1 for all i ∈ [k]. Then, the k-fold adaptive composition A : X → Y1 × · · · × Yk that jointly releases the outputs of all k mechanisms is (µ, δ)-GDP, where µ2 = µ21 + µ22 + · · · + µ2k and 1 − δ = (1 − δ1 )(1 − δ2 ) . . . (1 − δk ). The proofs of Propositions 5.1 and 5.3 are deferred to Appendix E. 16

5.2

Smooth sensitivity and Propose-Test-Release (PTR)

Algorithm 3 PTR-GDP Input: Dataset D, statistic θ(·), smoothness parameter β, smooth sensitivity SSβ , privacy parameters µ and δ Compute the smooth sensitivity bound SSβ (D) Draw Z1 ∼ N (0, 1), Z2∼ N (0, Id )  B(D) ← SSβ (D) · exp βµ · Z1 + βµ · Φ−1 (1 − δ) , θ̃(D) ← θ(D) + B(D) µ · Z2 return θ̃(D) Let f : X n → R be a statistic with some local sensitivity bound LSf (equation 1). Recall that a function SSβ is said to be a β-smooth upper bound on if LSf (D) ≤ SSβ (D) and SSβ (D) ≤ eβ SSβ (D′ ) for all adjacent D ∼ D′ , In this section, we adapt the Propose-Test-Release (PTR) framework [DL09] for GDP, leveraging the facts that smooth sensitivity bounds become Lipschitz after taking logarithms. The smooth sensitivity can be much smaller than the global sensitivity on typical datasets. While the smooth sensitivity may not be efficiently computable in general, there are many estimators such as the sample quantile or U -statistics where one can compute it efficiently [NRS07, FI17, CLPS24]. Algorithm 3 is a PTR-style algorithm that uses Gaussian noise and yields an approximate µ-GDP guarantee, as long a smooth upper bound SSβ for LS is computable. The PTR step above is an analog of the private sensitivity framework of [KRSY11, Lemma 4.4]. We state the corresponding GDP version below. Lemma 5.4 (PTR-GDP is private). Suppose µ1 , µ2 > 0 and let B : X n → (0, ∞) be a µ1 -GDP mechanism such that P[B(D) ≥ LS(θ, D)] ≥ 1 − δ for every dataset D. Then, the output   B(D) B(D), θ(D) + · N (0, Id ) µ2 p √ is ( µ21 + µ22 , δ)-GDP. In particular, Algorithm 3 is ( 2µ, δ)-GDP. The proof of Lemma 5.4 can be found in Appendix E.

5.3

Private confidence regions for S-friendly estimators in Definition 1.2

Let θ : X n → Rd be an estimator and SSβ be a β-smooth upper bound on the local sensitivity of θ. Consider a (multi)-set of indices Si of size m drawn uniformly from [n]. Let si = SSβ (θ, D[Si ]) be the smooth sensitivity for the dataset D[Si ] (where the m samples in D[Si ] are viewed as distinct elements when computing the smooth sensitivity, regardless of the sampling method). Lemma 5.5. Let s(D) := max SSβ (θ, D[Si ]) · i∈[B]

eκ⋆ β − 1 + SSβ (θ, D). eβ − 1

Then, τm s(D) is a κ⋆ β-smooth upper bound on the local sensitivity of Qn,m of Algorithm 4. 17

Algorithm 4 Confidence Regions via Smoothed Sensitivity (CR-SS) Input: Dataset D, statistic θ(·), confidence parameter α, smoothness parameter β, smooth sensitivity SSβ , privacy parameters µ and δ, failure probability ρ, subsampling method Mode ∈ {WR, WOR} if Mode = WR then κ⋆ ← κ⋆ (n, m, B, ρ) of equation (4) (S1 , S2 , . . . , SB ) ← MCS(n, m, B, κ⋆ ) if (S1 , S2 , . . . , SB ) = ⊥ then return ⊥ end end

if Mode = WOR then κ⋆ ← 1 (S1 , S2 , . . . , SB ) ← Subsample(n, m, B) end

θbn ← θ(D) θen ← PTR-GDP(D, θ, β, SSβ , µ/2, δ/2) for i ← 1 to B do θi∗ ← θ(D[Si ]) end   ⋆ −θ bn ∥2 Qn,m ← τm Quantile1−α ∥θ1⋆ − θbn ∥2 , . . . , ∥θB Define the function s(D) := maxi∈[B] SSβ (D[Si ]) · (eκ⋆ β − 1)/(eβ − 1) + SSβ (D) e n,m ← PTR-GDP(D, Qn,m , κ⋆ β, τm · s(D), µ/2, δ/2) Q e n,m ← max{Q e n,m , 0} Q e n,m ) return (θen , Q The proof of Lemma 5.5 is in Appendix F. Theorem 5.6. CR-SS(Algorithm 4) is (µ, δ)-GDP. Suppose for any N ∈ Z+ and η ∈ (0, 1), the smooth sensitivity function SSβ satisfies SSβ (θ, D) ≤ ΓN,η with probability at least 1 − η for datasets D of size N . Then, with the choice of the smoothness parameter ! µ 1 min 1, p β := , (6) 2κ⋆ 4 log(B/(δρ)) e n,m ) of Algorithm 4 satisfies the output (θen , Q e n,m ) = 1 − α + on (1) P(d(θ, θen ) < τn−1 Q provided Assumption 3.8 holds, the failure probability ρ = on (1), and ! ! µ µ p p √ Γn,ρ = o , Γm,ρ/B = o . τn ( d + log(1/ρ)) τm κ⋆ log(1/ρ) Moreover, the confidence radius  e n,m = max  τn−1 Q 

 τn−1 Qn,m | {z }

non-private bootstrap radius

+

σpriv · G | {z }

 , 0 ,

private overhead

where G ∼ N (0, 1) and σpriv ≤ 2τm τn−1 µ−1 (Γm,ρ/B κ⋆ e2 + Γn,ρ e) with probability at least 1 − O(ρ). 18

Theorem 5.6 shows that under mild assumptions on the smooth sensitivity of an estimator of interest, the radius of the confidence region output by Algorithm 4 can be controlled using a high probability upper bound on the smoothed sensitivity of the estimator. The proof of Theorem 5.6 can be found in Appendix F.

6

Applications

6.1

Confidence intervals for population quantiles

Although sample quantiles are consistent, their global sensitivity can be large, making private resampling methods that require small global sensitivity difficult to apply directly. We use CR-SS to obtain private confidence intervals for population quantiles, by bounding the smooth sensitivity of the 1 − ζ sample quantile in terms of the spacings between appropriate order statistics in the neighborhood of the quantile. The privacy guarantee follows from Theorem 5.6, and the utility guarantee reduces to controlling these spacings. The proofs are given in Appendix Section G. Lemma 6.1 (Smooth sensitivity of a sample quantile). Let D = (x1 , . . . , xn ) ∈ [ℓ, u]n and let  x(1) ≤ · · · ≤ x(n) be the order statistic of D. Fix a quantile level 1−ζ ∈ (0, 1) and let h := (1−ζ)n . Then, for any β > 0, there exists a β-smooth upper bound on the local sensitivity of q1−ζ = x(h) . Moreover, for any C > 0 and k ⋆ ≥ max{β −1 (log(C −1 (u − ℓ)) + 3 log n), 0}, the smooth sensitivity is bounded as (1−ζ) SSβ (θ, D) ≤ x(h+k⋆ +1) − x(h−k⋆ −1) + C/n3 . Suppose D is a distribution supported on [ℓ, u] such that its density f satisfies f (x) ≥ λ for x around the 1 − ζ quantile (see the statement of Theorem G.1 for the precise characterization). By using Lemma 6.1, we can show that for any positive integer N , the smooth sensitivity of the sample (1−ζ) C N quantile with N samples is bounded as SSβ (θ, D) ≤ 6K N λ + N 3 with probability at least 1−O(ρ), where KN = max{β −1 (log(C −1 (u − ℓ)) + 3 log N ), 0}. C N For such distributions D, Theorem 5.6 applies with ΓN,ρ = 6K N λ + N 3 and we can show that with high e n,m of the algorithm is equal to the non-private confidence probability, the confidence radius τn−1 Q radius τn−1 Qn,m obtained by resampling, plus a private overhead σpriv · G, where G is a standard √ normal and σpriv = Õ(1/ mn). This leads to the bound on the radius in Table 1. See Appendix G for the exact statement and calculations.

6.2

Degenerate U-statistics i.i.d.

Let X1 , . . . , XN ∼ P, and let h : X r → R be a bounded symmetric kernel of fixed order r. The corresponding U -statistic estimates θ := E[h(X1 , . . . , Xr )] by averaging h over all r-tuples of distinct observations:  −1 X N UN := h(Xi1 , . . . , Xir ). r 1≤i1 <···<ir ≤N

19

The variance of a U -statistic is generally governed by its first Hoeffding projection h1 (x) := E[h(x, X2 , . . . , Xr )] − θ. When h1 (X1 ) is nonzero with √ positive probability, the U statistic is called non-degenerate and −1 Var(UN ) = Θ(N ). Moreover, N · (UN − θ) is asymptotically normal. We say that h is first-order degenerate if E[h(X1 , . . . , Xr ) | X1 ] = θ

almost surely,

or equivalently h1 (X1 ) = 0 almost surely. In this case the first-order variance contribution in the Hoeffding decomposition vanishes. Hence, for fixed r, Var(UN ) = O(N −2 ). Moreover, if the variance of the second-order projection3 is nonzero, then Var(UN ) = Θ(N −2 ). Thus, in the usual first-order degenerate but second-order non-degenerate case, the appropriate asymptotic scaling is τN = N . In this case, N · (UN − θ) converges to a sum of centered chi-squared random variables. Degenerate U-statistics arise in hypothesis tests such as Pearson goodness-of-fit tests [Gre77, AD52] and uniformity tests [DGPP16], model misspecfication [LF20, LG14], and subgraph counts [RR10]. In contrast to non-degenerate U-statistics, which converge to a normal distribution, degenerate Ustatistics converge weakly to an infinite sum of chi-squared random variables [Lee19]. This makes them a perfect candidate for m-out-of-n subsampling, since the bootstrap has been shown to be an inconsistent estimator of their limiting distribution [Bre83, AG92]. Our goal in this subsection is to show how CR-SS can be used for this class of statistics to obtain a private asymptotically valid confidence interval for θ. To obtain the required sensitivity control, b rw of [CLPS24]. Suppose that h has bounded additive range, we use the reweighted U-statistic U N meaning that sup |h(x) − h(x′ )| ≤ C x,x′

b rw admits a β-smooth sensitivity bound satisfying for some C. [CLPS24] show that the estimator U N !   3/2 C log(1/η) r rw U U bN ; DN ) ≤ ΓN,η ≥ 1 − η, P SSβ (U ΓN,η = O . (7) N 3/2 Under Assumption 3.8 and the sensitivity conditions of Theorem 5.6, CR-SS therefore produces an asymptotically valid confidence interval. The following lemma records its confidence radius. Lemma 6.2 (Confidence radius for degenerate kernels). Let X1 , . . . , XN be IID samples from a distribution P over X , and let h : X r → R be a first-order degenerate, bounded symmetric kernel of order r. Then, the smooth-sensitivity bound of equation (7) holds with ΓU n,ρ for the original sample 3

The second-order projection is the function h2 (x, y) = E[h(x, y, X3 , . . . , Xr )] − θ − h1 (x) − h2 (y).

20

and ΓU m,ρ/B for each resample. Run CR-SS with τN = N and β as in equation 6. Then, with n o e Qn,m Q probability at least 1 − O(ρ), n,m = max + σ G, 0 , where G ∼ N (0, 1) and priv n n  2m  2 U σpriv ≤ κ⋆ e Γm,ρ/B + eΓU n,ρ = O nµ

κ⋆ r3/2 C log(1/ρ) √ µn m

! .

(8)

The proof sketch is given in Appendix H. For fixed r, C, and privacy parameters, the non-private e √m)−1 ). Hence, as confidence radius is of order n−1 whereas the privacy overhead is of order O((n m → ∞, the privacy overhead is asymptotically smaller than the nonprivate statistical error. The square the privacy overhead is  2 3 2 κ⋆ r C e O , µ2 mn2 which is the corresponding entry in Table 1.

7

Experiments

We evaluate private confidence intervals for three estimands: a bounded mean, a first-order degenerate U-statistic, and a population median. We compare BLBQuant [CDK24], the GDP m-out-of-n bootstrap [DG25], and our method using sampling with replacement (WR) and without replacement (WOR). All experiments use sample sizes n ∈ {2000, 5000, 10000, 20000, 40000, 50000}, with 400 independent datasets generated for each value of n. We use B = 500 resamples, Nmc = 100 inner Monte Carlo repetitions for BLBQuant, nominal coverage 0.90, and total privacy parameter µ = 8. We report empirical coverage, mean interval width over finite outputs, and mean runtime. Privacy budgets are √calibrated consistently across methods. The m-out-of-n bootstrap assigns a privacy budget of µ/ 2 to each of its two blocks. The two pure-DP mechanisms used by BLBQuant are converted to GDP and composed to match the same total GDP parameter.

(a) Bernoulli mean.

(b) Population median.

(c) Degenerate U-statistic.

Figure 1: Mean runtime across three estimation problems. Results are averaged over 400 independent trials for n ∈ {2000, 5000, 10000, 20000, 40000, 50000}. We use B = 500, Nmc = 100, and total privacy parameter µ = 8.

21

7.1

Mean estimation Algorithm

cov 103 ×len time (ms)

n

Algorithm

cov 103 ×len time (ms)

n

BLBQuant 0.93 Dette-Graw 0.66 CR-GS (WR) 0.90 CR-GS (WOR) 0.90

16.39 11.39 15.92 14.90

32.21 1.35 9.91 5.23

2000 2000 2000 2000

BLBQuant 0.91 Dette-Graw 0.91 CR-GS (WR) 0.89 CR-GS (WOR) 0.87

42.50 42.54 42.38 39.61

29.78 1.24 9.01 4.78

2000 2000 2000 2000

BLBQuant 0.90 Dette-Graw 0.77 CR-GS (WR) 0.90 CR-GS (WOR) 0.86

10.26 8.95 10.17 9.46

72.53 1.22 20.71 8.78

5000 5000 5000 5000

BLBQuant 0.88 Dette-Graw 0.89 CR-GS (WR) 0.87 CR-GS (WOR) 0.86

26.70 26.81 26.71 25.22

72.44 1.27 20.08 8.76

5000 5000 5000 5000

BLBQuant 0.89 Dette-Graw 0.82 CR-GS (WR) 0.89 CR-GS (WOR) 0.88

7.18 6.63 7.12 6.76

145.11 1.40 31.47 15.31

10000 10000 10000 10000

BLBQuant 0.88 Dette-Graw 0.89 CR-GS (WR) 0.88 CR-GS (WOR) 0.87

18.88 18.99 18.93 17.85

142.71 1.28 31.01 15.13

10000 10000 10000 10000

BLBQuant 0.92 Dette-Graw 0.90 CR-GS (WR) 0.92 CR-GS (WOR) 0.91

5.08 4.91 5.05 4.78

344.29 1.68 62.77 29.88

20000 20000 20000 20000

BLBQuant 0.92 Dette-Graw 0.92 CR-GS (WR) 0.92 CR-GS (WOR) 0.90

13.29 13.44 13.41 12.65

339.56 1.60 62.33 28.15

20000 20000 20000 20000

BLBQuant 0.90 Dette-Graw 0.89 CR-GS (WR) 0.90 CR-GS (WOR) 0.88

3.56 3.55 3.57 3.39

665.86 1.74 126.34 59.07

40000 40000 40000 40000

BLBQuant 0.90 Dette-Graw 0.90 CR-GS (WR) 0.90 CR-GS (WOR) 0.89

9.37 9.49 9.47 9.01

661.87 1.73 125.23 58.70

40000 40000 40000 40000

BLBQuant 0.91 Dette-Graw 0.89 CR-GS (WR) 0.91 CR-GS (WOR) 0.89

3.18 3.12 3.18 3.04

812.03 1.81 156.78 73.74

50000 50000 50000 50000

BLBQuant 0.90 Dette-Graw 0.90 CR-GS (WR) 0.90 CR-GS (WOR) 0.89

8.37 8.50 8.47 8.07

817.64 1.85 156.44 73.65

50000 50000 50000 50000

(b) Uniform[−1, 1] mean.

(a) Bernoulli(0.05) mean.

Table 3: Results for the bounded-mean experiments. Here, cov is empirical coverage, len is the mean interval width over finite outputs, and time is the mean runtime in milliseconds. The table reports 103 times the mean interval width. Bold coverage values lie in [0.88, 0.92] after rounding. We consider two bounded distributions representing qualitatively different finite-sample regimes: X ∼ Bernoulli(0.05),

X ∼ Unif[−1, 1].

Their population means are 0.05 and and 0, respectively. For observations supported on [a, b], the sample mean has global sensitivity (b − a)/n. Moreover, the sample mean is asymptotically normal √ as long as the variance is finite and non-zero, so the scaling parameter τn = n. For CR-GS and BLBQuant, we set the miscoverage parameter to α = 0.1. The m-out-of-n bootstrap l m procedure a 1−2αDG interval, so we use αDG = 0.05. For CR-GS, the resample size is mGS = logn n . The WR variant uses multiplicity-check failure probability ρ = 1/n. The WOR variant uses the same mGS and B, but has κ⋆ = 1 and also does not require a multiplicity check. For m-out-of-n n o log(1−1/B) bootstrap, we use their recommended resample size mDG = round log(1−1/n) [DG25]. Table 3 summarizes the results of both mean experiments. All methods approach the nominal coverage of 0.9 when the sample size n is large. For the Uniform experiment, all methods other than CR-GS without replacement achieve nominal coverage for smaller values of n too, and for the 22

Bernoulli experiment, where the mean is skewed, both BLBQuant and CR-GS achieve near-nominal coverage for smaller values of n.

7.2

Degenerate U-statistic Algorithm

cov 103 ×len

time

n

Algorithm

cov 104 ×len

time

n

BLBQuant 0.93 Dette-Graw 0.06 CR-SS (WR) 0.88 CR-SS (WOR) 0.85

101.14 45.04 164.35 86.14

117.77 1.30 33.38 25.89

2000 2000 2000 2000

BLBQuant 1.00 Dette-Graw 1.00 CR-SS (WR) 0.90 CR-SS (WOR) 0.81

11.24 7.37 4.08 1.48

21.77 2.76 22.43 13.65

2000 2000 2000 2000

BLBQuant Dette-Graw CR-SS (WR) CR-SS (WOR)

0.94 0.12 0.81 0.86

66.94 44.15 78.84 54.40

590.56 1.45 65.41 51.25

5000 5000 5000 5000

BLBQuant Dette-Graw CR-SS (WR) CR-SS (WOR)

4.90 2.65 1.21 0.58

66.71 4.12 32.39 18.11

5000 5000 5000 5000

BLBQuant Dette-Graw CR-SS (WR) CR-SS (WOR)

0.93 0.10 0.85 0.87

48.34 39.48 60.64 39.29

2083.63 10000 1.63 10000 135.78 10000 113.22 10000

BLBQuant 1.00 Dette-Graw 1.00 CR-SS (WR) 0.86 CR-SS (WOR) 0.88

2.63 134.81 10000 1.23 6.63 10000 0.56 46.92 10000 0.29 25.52 10000

BLBQuant 0.97 Dette-Graw 0.08 CR-SS (WR) 0.82 CR-SS (WOR) 0.88

38.55 28.88 35.91 27.73

7523.76 20000 2.26 20000 221.00 20000 188.57 20000

BLBQuant Dette-Graw CR-SS (WR) CR-SS (WOR)

1.00 0.99 0.85 0.93

1.38 242.96 20000 0.58 11.46 20000 0.23 71.72 20000 0.14 40.79 20000

BLBQuant 0.98 Dette-Graw 0.03 CR-SS (WR) 0.85 CR-SS (WOR) 0.88

30.18 27427.77 40000 20.59 3.39 40000 22.71 382.88 40000 19.54 338.46 40000

BLBQuant 1.00 Dette-Graw 0.98 CR-SS (WR) 0.87 CR-SS (WOR) 0.89

0.73 521.04 40000 0.27 26.01 40000 0.11 124.95 40000 0.07 85.54 40000

BLBQuant Dette-Graw CR-SS (WR) CR-SS (WOR)

26.93 42386.22 50000 18.43 3.87 50000 20.52 465.20 50000 17.50 414.23 50000

BLBQuant 1.00 Dette-Graw 1.00 CR-SS (WR) 0.84 CR-SS (WOR) 0.92

0.59 656.71 50000 0.21 32.79 50000 0.07 155.00 50000 0.06 108.17 50000

0.97 0.04 0.85 0.87

(a) Population median.

1.00 0.99 0.87 0.84

(b) Degenerate U-statistic.

Table 4: Results for the median and degenerate U-statistic experiments. Here, cov is empirical coverage, len is mean interval width over finite outputs, and time is mean runtime in milliseconds. The median panel reports 103 times the interval width, while the U-statistic panel reports 104 times the interval width. For CR-SS (WR) in the U-statistic experiment, coverage is conditional on return. Bold coverage values lie in [0.88, 0.92] after rounding. i.i.d.

We generate X1 , . . . , Xn ∼ Unif[−1/2, 1/2] and use the degree-two kernel h(x, y) = xy. The resulting U-statistic is P P  −1 X ( i Xi )2 − i Xi2 n Un = Xi Xj = . 2 n(n − 1) i<j

Because E[Xi ] = 0, the target parameter is θ = (E[Xi ])2 = 0. The statistic is first-order degenerate, so the appropriate scaling is τn = n. For CR-SS, we use m = ⌈n/log n⌉, δ = 10−6 , and ρ = 1/n, together with the product-statisticspecific smooth-sensitivity bound. Because the statistic is degenerate, the resampling pivots are constructed on the m-scale, and the resulting interval radii are converted back to the n-scale. Table 4 summarizes the results of the experiment. We observe that m-out-of-n bootstrap undercovers significantly, because the global sensitivity of the median is a constant, which is not consistent 23

with what they expect in their experiments. BLBQuant overcovers, whereas our methods slightly undercover.

7.3

Median i.i.d.

We generate X1 , . . . , Xn ∼ Unif[−1, 1]. The target parameter is the population median, which √ equals 0. Since the empirical median is asymptotically normal, we use the scaling τn = n. For CR-SS, we use m = ⌈n/log n⌉, δ = 10−6 , and ρ = 1/n, together with the quantile smoothsensitivity bound. For WR, the miscoverage parameter is set to 0.09, reserving ρ = 0.01 for the multiplicity-check failure probability. For WOR, the miscoverage parameter is 0.10. The global sensitivity of the empirical median on [−1, 1] is 2, which is the value used by m-out-of-n bootstrap. Table 4 summarizes the results of the experiment. We observe that m-out-of-n bootstrap and BLBQuant both overcover, with a coverage close to 1. Since our methods adapt to the natural τn = n scaling of a degenerate U-statistic, we obtain coverages closer to the nominal 0.9 coverage.

8

Conclusion

We provide GDP guarantees for private confidence regions for a large family of estimators arising from widely used resampling procedures such as subsampling and m-out-of-n sampling. We provide a simple algorithm that privatizes the quantile instead of privatizing estimators computed on each √ resample. This leads to a logarithmic dependence on B instead of the B dependence incurred in previous work. Our estimators do not need to be asymptotically normal or have small global sensitivity, making it widely applicable. We provide both utility and nonasymptotic privacy guarantees. Overall, we develop private uncertainty quantification methods for common resampling schemes that sidestep the computational and privacy costs of privatizing many intermediate resample statistics.

24

References [AD52] T. W. Anderson and D. Darling. Asymptotic theory of certain "goodness of fit" criteria based on stochastic processes. Annals of Mathematical Statistics, 23:193–212, 1952. [AG92] Miguel A. Arcones and Evarist Giné. On the bootstrap of u and v statistics. The Annals of Statistics, 20(2):655–674, 1992. [And00] Donald W. K. Andrews. Inconsistency of the bootstrap when a parameter is on the boundary of the parameter space. Econometrica, 68(2):399–405, 2000. [Ath87] K. B. Athreya. Bootstrap of the Mean in the Infinite Variance Case. The Annals of Statistics, 15(2):724 – 731, 1987. [Ber84] R. Beran. Bootstrap methods in statistics. Deutsch. Math.-Verein, 86(1):14–30, 1984. [BGvZ11] Peter J Bickel, Friedrich Götze, and Willem R van Zwet. Resampling fewer than n observations: gains, losses, and remedies for losses. In Selected works of Willem van Zwet, pages 267–297. Springer, 2011. [BH18] Thomas Brawner and James Honaker. Bootstrap inference and differential privacy: Standard errors for free. Unpublished Manuscript, 2018. [Bla51] David Blackwell. Comparison of experiments. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pages 93–102, 1951. [Bla53] David Blackwell. Equivalent comparisons of experiments. The annals of mathematical statistics, pages 265–272, 1953. [Bre83] J. Bretagnolle. Lois limites du bootstrap de certaines fonctionnelles. Annales de l’I.H.P. Probabilités et statistiques, 19(3):281–296, 1983. [CBP17] Daskalakis Bryan Cai Bryan and Gautam Kamath. Privit. Private and sample efficient identity testing. arXiv preprint arXiv:1703.10127, 2017. [CDK24] Karan Chadha, John Duchi, and Rohith Kuditipudi. Resampling methods for private statistical inference. arXiv preprint arXiv:2402.07131, 2024. [CLPS24] Kamalika Chaudhuri, Po-Ling Loh, Shourya Pandey, and Purnamrita Sarkar. On differentially private u statistics. Advances in Neural Information Processing Systems, 37:23078–23122, 2024. [CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(29):1069–1109, 2011. [DG25] Holger Dette and Carina Graw. Gaussian Differential Private Bootstrap by Subsampling. arXiv preprint arXiv:2505.01197, 2025. [DGPP16] I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. Collision-based testers are optimal for uniformity and closeness. arXiv preprint arXiv:1611.03579, 2016. 25

[DL09] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371–380, 2009. [DN04] Herbert A David and Haikady N Nagaraja. Order statistics. John Wiley & Sons, 2004. [DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3–4):211–407, August 2014. [DRS22] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 2022. [Dwo06] Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pages 1–12. Springer, 2006. [Efr79] B. Efron. Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics, 7(1):1 – 26, 1979. [FI17] Sam Fletcher and Md Zahidul Islam. Differentially private random decision forests using smooth sensitivity. Expert systems with applications, 78:16–31, 2017. [FWS22] Cecilia Ferrando, Shufan Wang, and Daniel Sheldon. Parametric bootstrap for differentially private confidence intervals. International Conference on Artificial Intelligence and Statistics, 2022. [Gre77] G. Gregory. Large sample theory for U -statistics and tests of fit. Annals of Statistics, 5:110–123, 1977. [Hal92] Peter Hall. The Bootstrap and Edgeworth Expansion. Springer, 1992. [Hes15] TC Hesterberg. What teachers should know about the bootstrap: Resampling in the undergraduate statistics curriculum. The american statistician, 2015. [KR16] Daniel Kifer and Ryan Rogers. New class of private chi-square tests. Proceedings of the 20th International Conference on Artificial Intelligence, 2016. [KRSY11] Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. Proc. VLDB Endow., 4(11):1146–1157, August 2011. [KS12] Vishesh Karwa and Aleksandra Slavkovć. Differentially private graphical degree sequences and synthetic graphs. Privacy in Statistical Databases, 2012. [KS16] Vishesh Karwa and Aleksandra Slavkovć. Inference using noisy degrees: Differentially private β-model and synthetic graphs. The Annals of Statistics, 44(1):87–112, 2016. [KSGB23] Zeki Kazan, Kaiyan Shi, Adam Groce, and Andrew P Bray. The test of tests: A framework for differentially private hypothesis testing. In International Conference on Machine Learning, pages 16131–16151. PMLR, 2023. [KTSJ14] Ariel Kleiner, Ameet Talwalkar, Purnamrita Sarkar, and Michael I Jordan. A scalable bootstrap for massive data. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(4):795–816, 2014. 26

[KV17] Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. In Information Technology Convergence and Services, 2017. [Lee19] Lee. U-statistics: Theory and Practice. Routledge, 2019. [LF20] C. Li and X. Fan. On nonparametric conditional independence tests for continuous variables. WIREs Computational Statistics, 12(3):e1489, 2020. [LG14] O. Linton and P. Gozalo. Testing conditional independence restrictions. Econometric Reviews, 33(5-6):523–552, 2014. [NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75–84, 2007. [PJ92] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992. [PRW99a] Dimitris Politis, Joseph P. Romano, and Michael Wolf. Weak convergence of dependent empirical measures with application to subsampling in function spaces. Journal of Statistical Planning and Inference, 79(2):179–190, July 1999. [PRW99b] Dimitris N. Politis, Joseph P. Romano, and Michael. Wolf. Subsampling / by Dimitris N. Politis, Joseph P. Romano, Michael Wolf. Springer Series in Statistics. Springer New York, New York, NY, 1st ed. 1999. edition, 1999. [PRW01] Dimitris N. Politis, Joseph P. Romano, and Michael Wolf. On the asymptotic theory of subsampling. Statistica Sinica, 11(4):1105–1124, 2001. [Que49] M. H. Quenouille. Approximate tests of correlation in time-series. Journal of the Royal Statistical Society. Series B (Methodological), 11(1):68–84, 1949. [Rén53] Alfréd Rényi. On the theory of order statistics. Acta Math. Acad. Sci. Hung, 4(2):48–89, 1953. [RR10] Gesine Reinert and Adrian Röllin. Random subgraph counts and u-statistics: multivariate normal approximation via exchangeable pairs and embedding. Journal of applied probability, 47(2):378–393, 2010. [She51] Seymour Sherman. On a theorem of hardy, littlewood, polya, and blackwell. Proceedings of the National Academy of Sciences, 37(12):826–831, 1951. [She17] Or Sheffet. Differentially private ordinary least squares. Proceedings of the 34th International Conference on Machine Learning, 2017. [Smi11] A Smith. Privacy-preserving statistical estimation with optimal convergence rates. Proceedings of the forty-third annual ACM symposium on Theory of computing, 2011. [SSVHL25] Tomer Shoham, Moshe Shenfeld, Noa Velner-Harris, and Katrina Ligett. Black-box differentially private nonparametric confidence intervals under minimal assumptions. arXiv preprint arXiv:2511.01303, 2025. 27

[Ste51] C Stein. Notes on a seminar on theoretical statistics. i. comparison of experiments. Report, University of Chicago, 1951. [Tuk58] John W. Tukey. Bias and confidence in not-quite large samples. In The Annals of Mathematical Statistics, volume 29, page 614, 1958. [van98a] A. W. van der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. [van98b] Aad W. van der Vaart. Asymptotic Statistics. Cambridge University Press, 1998. [VKK14] Aleksandra B Slavković Vishesh Karwa and Pavel Krivitsky. Differentially private exponential random graphs. International Conference on Privacy in Statistical Databases, 2014. [VKS15] Dan Kifer Vishesh Karwa and Aleksandra B Slavković. Private posterior distributions from variational approximations. arXiv preprint arXiv:1511.07896, 2015. [VS09] Duy Vu and Aleksandra Slavkovć. Differential privacy for clinical trial data: Preliminary evaluations. In IEEE International Conference on Data Mining Workshops, pages 138– 143, 2009. [Wai19] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019. [WCA25] Zhanyu Wang, Guang Cheng, and Jordan Awan. Differentially private bootstrap: New privacy analysis and inference strategies, 2025. arXiv:2210.06140v4. [WM10] Oliver Williams and Frank McSherry. robabilistic inference and differential privacy. Advances in Neural Information Processing Systems, 2010. [YWJK15] Lee Yue Wang Jaewoo and Daniel Kifer. Differentially private hypothesis testing, revisited. arXiv preprint arXiv:1511.03376, 2015.

28

The appendix is organized as follows. 1. Section A contains some known auxiliary results. 2. Section B contains details of subsampling validity. 3. Section C has detailed calculations that led to Table 1. 4. Section D has the privacy and utility guarantees for DP-QuantS. 5. Section E proves the privacy of PTR-GDP. 6. Section F has the privacy and utility guarantees for Quant-SS. 7. Section G has the guarantees for confidence intervals for quantiles. 8. Section H has the guarantees for degenerate U-statistics.

A

Auxiliary Results

Proposition A.1 (ℓ2 -norm concentration of standard Gaussian [Wai19]). If Z ∼ N (0, Id ), then for any β ∈ (0, 1), p √ P(∥Z∥2 ≤ d + 2 log(1/β)) ≥ 1 − β. Proposition A.2 (Local Sensitivity of Order Statistics). Let 1 ≤ k ≤ B. Let A1 , A2 , . . . , AB : X m → R be arbitrary mechanisms and define gk (D) to be the kth largest element in {A1 (D), . . . , AB (D)}. Then, LS(gk , D) ≤ max LS(Ai , D). i∈[B]

Proof. Fix a neighboring dataset D′ ∼ D, and let δ := maxi∈[B] |Ai (D) − Ai (D′ )| . At least k of the values Ai (D) are at least gk (D). Their corresponding values at D′ are therefore at least gk (D) − δ, so gk (D′ ) ≥ gk (D) − δ. Interchanging D and D′ gives gk (D) ≥ gk (D′ )−δ. Therefore, |gk (D)−gk (D′ )| ≤ δ ≤ maxi∈[B] LS(Ai , D). Taking the supremum over all D′ ∼ D yields LS(gk , D) ≤ max LS(Ai , D). i∈[B]

B

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

Let Fn (t) := P(τn d(θbn , θ) ≤ t) and let F (t) := limn→∞ Fn (t) denote the CDF of the limiting distribution. 29

Assumption B.1. We assume that 1. F is non-degenerate and continuous. 2. supt |Fn (t) − F (t)| → 0. 3. qn = c1−α + o(1) where qn is the true 1 − α quantile of the distribution of τn d(θbn , θ) and c1−α is the 1 − α quantile of the limiting distribution. 4. τm /τn → 0, m/n → 0, B → ∞. 5. (Resampling validity) P(τn d(θbn , θ) ≤ Qn,m ) = 1 − α + on (1), where Qn,m denotes the scaled quantile defined in Algorithm 2 Remark B.2. Let Jn (P ) denote the limit law of τn (θbn − θ). The standard assumption for subsampling validity [PRW99a, PRW01] is that there exists a limit law J(P ) so that Jn (P ) converges to J(P ) weakly as n → ∞. Note that the continuous mapping theorem shows that this immediately implies that there exists a limit law of the sampling distribution of τn ∥θbn − θ∥ (Assumption B.1 (1) and (2). All that remains to be checked is Assumption B.1 (3) and (5). Lemma 21.2 in [van98b] establishes that if F −1 (.) is continuous at 1 − α, the 1 − α quantile qn converges to the true quantile c1−α . As for Assumption B.1 (5), note that Theorem 2.1 (iv) in [PRW01] directly yields (5) for infinite B. When B → ∞, one can show condition (5) via the DKW inequality and quantile convergence (see Lemma B.4 in the Appendix). A similar argument also applies to m-out-of-n resampling. For simplicity, we move it to the appendix. Remark B.3 (With-replacement m-out-of-n validity). Let Jn (P ) denote the law of τn (θ̂n − θ(P )), and suppose Jn (P ) ⇒ J(P ) for a nondegenerate limit law J(P ) with continuous CDF F . For with∗ be the estimator computed on a size-m bootstrap resample replacement m-out-of-n resampling, let θ̂m drawn i.i.d. from P̂n , and define the ideal (infinite-resample) conditional CDF   ∗ , θ(P )) ≤ t Dn , Bm,n (t) := P∗ τm d(θ̂m where P∗ (· | Dn ) is probability over the resampling randomness conditional on the data. Under the standard m-out-of-n conditions m → ∞, m/n → 0, and τm /τn → 0, together with the regularity assumptions in Theorem 2 of [BGvZ11] (see in particular (3.10)–(3.14)), the m-out-of-n bootstrap is consistent in the sense that p sup Bm,n (t) − F (t) → − 0. t∈R

Consequently, if qn,m (1 − α) := inf{t : Bm,n (t) ≥ 1 − α} and F is continuous at c1−α , then qn,m (1 − α) → c1−α , and   P τn d(θ̂n , θ(P )) ≤ qn,m (1 − α) = 1 − α + on (1), by the standard quantile-continuity argument (e.g. Lemma 21.2 in [van98a] or Theorem 1 in [Ber84]). bm,n,B deFinally, Assumption B.1 uses the empirical quantile Qn,m from B i.i.d. resamples. Let B B ∗ note the empirical CDF of {τm d(θ̂m,i , θ(P ))}i=1 . Conditional on Dn , by the DKW inequality, bm,n,B (t) − Bm,n (t) = Op (B −1/2 ), sup B t

so Qn,m − qn,m (1 − α) = op (1) provided B → ∞ (and the target quantile is a continuity point). 30

Lemma B.4 (Coverage with an estimated quantile cutoff). Let Tn be a real-valued statistic with d

Tn → T , where T has CDF F . Fix α ∈ (0, 1) and let q := F −1 (1 − α) = inf{t : F (t) ≥ 1 − α}. Assume that F is continuous at q (equivalently, P(T = q) = 0). Let Qn be any (possibly random) p cutoff such that Qn → − q. Then


P Tn ≤ Qn → 1 − α, and P Tn ≤ Qn − P Tn ≤ q → 0. Proof. Fix η > 0. Using {Tn ≤ Qn } ⊆ {Tn ≤ q + η} ∪ {Qn > q + η} and {Tn ≤ q − η} ⊆ {Tn ≤ Qn } ∪ {Qn < q − η} gives P(Tn ≤ q − η) − P(Qn < q − η) ≤ P(Tn ≤ Qn ) ≤ P(Tn ≤ q + η) + P(Qn > q + η). p

Since Qn → − q, the tail probabilities on the right vanish as n → ∞. By definition of convergence in distribution, P(Tn ≤ q ±η) → F (q ±η). Taking lim inf and lim sup yields F (q −η) ≤ lim inf n P(Tn ≤ Qn ) ≤ lim supn P(Tn ≤ Qn ) ≤ F (q + η). Letting η ↓ 0 and using continuity of F at q gives P(Tn ≤ Qn ) → F (q) = 1 − α. Finally, P(Tn ≤ q) → F (q) by definition, so the difference also converges to 0.

B.1

Proof of Proposition 4.1

Fix i ∈ [B] and j ∈ [n]. Since Si consists of m i.i.d. draws from [n] with replacement,   1 m κi,j ∼ Bin m, , µ := E[κi,j ] = . n n By a union bound over all (i, j) ∈ [B] × [n],     B X n X  c  1 ≥k . P Eκ⋆ ≤ P[κi,j ≥ k] = Bn · P Bin m, n

(9)

i=1 j=1

Let X ∼ Bin(m, 1/n) with mean µ = m/n. For any integer k ≥ 1, a standard Chernoff bound gives  eµ k  k P[X ≥ k] ≤ . (10) = exp − k log k eµ Recall A := log

 Bn  ρ

,

A0 := max{A, 1},

M := log

n m

 + log A0 ,

κ⋆ :=

 4A0 . M

Let k = κ⋆ . Since k ≥ 4A0 /M and µ = m/n, we have log

k n = log k + log −1 eµ m  4A  n 0 ≥ log + log −1 M m n
= log A0 + log + log 4 − log M − 1 m = M + log 4 − log M − 1. 31

(11)

Define g(M ) := M + log 4 − log M − 1 = (M − log M ) + (log 4 − 1). We lower bound g(M ) in two regimes. 1 Case 1: M ≤ 4 log 4. Since g ′ (M ) = 1 − M and g ′′ (M ) = M12 > 0, the function g is convex and attains its minimum at M = 1, where g(1) = log 4. Hence g(M ) ≥ log 4 for all M > 0, and in particular for M ≤ 4 log 4,

k log

k 4A0 4A0 ≥ · g(M ) ≥ · log 4 ≥ A0 , eµ M M

where the last inequality uses M ≤ 4 log 4. Case 2: M > 4 log 4. In this case M ≥ 2, so log M ≤ M/2, and thus g(M ) = M + log 4 − log M − 1 ≥ M − log M − 1 ≥ M/2 − 1. Since M/2 − 1 > M/4, k log

4A0 4A0 k ≥ · (M/2 − 1) ≥ · (M/4) = A0 . eµ M M

Combining the two cases, we have shown k log

k ≥ A0 ≥ A. eµ

(12)

Plugging (12) into (10) yields     ρ 1 ≥ k ≤ e−A = . P Bin m, n Bn Finally, substitute this into (9) to obtain P[Eκc⋆ ] ≤ Bn ·

ρ = ρ, Bn

as claimed.

C

Comparison with related works

Lemma C.1 ( Finite-B error of the empirical resampling quantile). Let Yi = τm d(θbi∗ , θbn ),

i = 1, . . . , B,

denote the scaled resampling pivots, conditional on the data D, and let Fn,m be their conditional CDF. Set p = 1 − α, −1 q1−α := Fn,m (p),

Qn,m := Y(k) , 32

k = ⌈Bp⌉.

−1 is twice continuously differentiable in a neighborhood of p, with derivatives bounded Assume that Fn,m independently of B. Then, conditional on D, 2 E[Q2n,m | D] = q1−α + O(B −1 ).

Consequently, the non-private squared length satisfies   2 4q1−α 1 2 . E[Lnp | D] = +O 2 τn2 τn B Proof. Let Ui = Fn,m (Yi ). Conditional on D, U1 , . . . , UB are i.i.d. Unif(0, 1), and Fn,m (Qn,m ) = U(k) . By the standard order-statistic representation [DN04, Example 2.3], U(k) ∼ Beta(k, B − k + 1). Hence E[U(k) | D] = and Var(U(k) | D) = Therefore

k = p + O(B −1 ), B+1

k(B − k + 1) = O(B −1 ). (B + 1)2 (B + 2)

E[(U(k) − p)2 | D] = O(B −1 ).

Now define

−1 h(u) := {Fn,m (u)}2 .

Since h is twice continuously differentiable near p, Taylor expansion around p gives
h(U(k) ) = h(p) + h′ (p)(U(k) − p) + O (U(k) − p)2 . Taking conditional expectations,
E[Q2n,m | D] = h(p) + h′ (p) E[U(k) − p | D] + O E[(U(k) − p)2 | D] . Using the bounds above, 2 E[Q2n,m | D] = h(p) + O(B −1 ) = q1−α + O(B −1 ).

Finally, since Lnp = 2Qn,m /τn , E[L2np | D] =

  2 4q1−α 4 1 2 E[Qn,m | D] = +O 2 . τn2 τn2 τn B

33

Let q1−α denote the target non-private resampling quantile for the pivot τn d(θbn , θ). Thus the leading 4q 2

non-private confidence radius is q1−α /τn , and the true squared length is τ1−α 2 . Under standard n regularity conditions on the sampling distribution (see Lemma C.1) the expected squared length of the nonprivate confidence region is   2 ) 2   4(Q2n,m + σm 4q1−α 1 2 E r(α) = E . = +O τn2 τn2 Bτn2 [DG25]’s squared confidence interval length is approximately 4q 2 LenDG (α) ≈ 1−α +O τn2 2



1 Bτn2

 +

2 2 Bℓ2 4q1−α τm · . τn2 n2 µ2

Our method. Algorithm 2 forms the empirical resampling quantile Qn,m , privatizes it once, e n,m = max{Qn,m + σm Z, 0}, Q and reports θen ±

Z ∼ N (0, 1),

e n,m Q τn . For the comparison here, we isolate the contribution of the noisy quantile.

Moreover, for mean-like statistics with global sensitivity ∆m on samples of size m, σm = τm κµ⋆ ∆m , up to universal constants using Theorem 4.2. Therefore   2 2 κ2 ∆2  4q1−α  1 4τm ⋆ m 2 EZ Lenours (α) ≈ + O + . τn2 Bτn2 τn2 µ2 Since κ⋆ = O(log(Bn)) under with-replacement sampling and κ⋆ = 1 under sampling without √ replacement, our procedure replaces the B-type accumulation from repeatedly privatizing resample statistics by a logarithmic dependence on B in the squared-length penalty. √ √ In the root-n regime, where τn = n, τm = m, and ∆m = ℓ/m, the privacy terms become ∆DG ≈

2 Bmℓ2 4q1−α , n3 µ2

∆ours ≈

4κ2⋆ ℓ2 . mnµ2

Thus, for m close to n, the prior approach pays essentially a factor linear in B, whereas our approach pays only through κ2⋆ . √ Chadha et al. [CDK24]. Consider a mean-like statistic with ∆n ≤ nℓ and τn = n. The length calculation for [CDK24] is less direct because their method privatizes resampling-based coverage estimates through a private threshold search. We will use B for their number of Monte Carlo resamples Nmc . Let t⋆ be the smallest radius for which the empirical coverage function satisfies p(t⋆ ) ≥ 1 − α, and let b t be the radius returned by their private threshold search. Their guarantee implies, with high probability, 1 − α − ωcdf ≤ p(b t) ≤ 1 − α + 2ωcdf . 34

If p is differentiable near t⋆ and p′ (t) is bounded away from 0 in a neighborhood of t⋆ , then r   1 ℓ 1 .. |b t − t⋆ | = O (ωcdf ) = Õ √ + √ + Nmc n ε n Thus



ℓ e √1 + √ b t = q1−α + O + n ε n

r

1 Nmc





ℓ √ + ε n

.

Since LChadha = 2b t/τn , 4q 2 1 L2Chadha = 1−α + 2 Õ τn2 τn

 q1−α

ℓ √ + ε n

r

1 Nmc

and the private error for the squared radius is of the order Õ

D

 +



r

ℓ 1 + n√N εn3/2 mc

1 Nmc 

2 !

.

Privacy and Utility for CR-GS

Lemma D.1 (Privacy Guarantee). Algorithm 2 is µ-GDP. Proof. First, the probability that algorithm MCS outputs ⊥ is independent of the data. It suffices to show that the algorithm is µ-GDP conditioned on the event that (S1 , . . . , SB ) ̸= ⊥. Since θbn = θ(D) ∈ Rd has global sensitivity ∆n , Proposition 3.7 implies that the statistic θen defined as ∆n θen (D) = θbn (D) + √ Z2 , Z2 ∼ N (0, Id ) µ/ 2 √ is µ/ 2-GDP. Moreover, each d(θi∗ , θbn ) has global sensitivity κ⋆ ∆m + ∆n ; indeed, each data point Xj ∈ D appears at most κ⋆ times in D[Si ], so the global sensitivity of θi∗ is bounded by κ⋆ ∆m . ∗ ,θ bn )) is also bounded By Proposition A.2, the global sensitivity of Quantile1−α (d(θ1∗ , θbn ), . . . , d(θB above by κ⋆ ∆m + ∆n . Therefore, ! √ 2τ (κ ∆ + ∆ ) m ⋆ m n e n,m = max Qn,m + · Z1 , 0 , Q µ

√ where Z1 ∼ N (0, 1), is µ/ 2-GDP. By basic composition (equation (3)), Algorithm 2 is µ-GDP. Lemma D.2. Let

√ σm =

2τm (κ⋆ ∆m + ∆n ) µ

as in Algorithm 2. Suppose (i) assumption B.1 holds, 35

and

√ 2∆n νn = µ

(ii) the failure probability ρ = on (1), and (iii) γ = on (1), where γ := σm

p p √ 2 log(1/ρ) + τn νn ( d + 2 log(1/ρ)).

e n,m ) of Algorithm 2 satisfies Then, output (θen , Q e n,m ) = α + on (1). P(τn d(θ, θen ) ≥ Q Proof. Let En denote the event that Algorithm 2 does not abort. By Proposition 4, P(Enc ) ≤ ρ = on (1). For the purposes of the proof, regard all B resamples as being drawn before the multiplicity check, and define Qn,m from these resamples regardless of whether En occurs. Sample Z1 and Z2 independently and define the auxiliary outputs θ̄n := θbn + νn Z2 ,

Q̄n,m := max{Qn,m + σm Z1 , 0}.

e n,m ) of Algorithm 2. On Enc , extend On En , these auxiliary outputs agree with the outputs (θen , Q the output of Algorithm 2 by any fixed value; the choice of extension affects the probability in the statement by at most ρ = on (1). Define Tn := τn d(θ, θbn ), and let

T̄n := τn d(θ, θ̄n ),

q1−α := F −1 (1 − α).

By triangle inequality, |T̄n − Tn | ≤ τn d(θ̄n , θbn ) = τn νn ∥Z2 ∥2 . Moreover, since Qn,m ≥ 0 and projection onto [0, ∞) is 1-Lipschitz, |Q̄n,m − Qn,m | ≤ σm |Z1 |. By Gaussian concentration,   p √ P ∥Z2 ∥2 > d + 2 log(1/ρ) ≤ ρ,

P(|Z1 | >

p 2 log(1/ρ)) ≤ 2ρ.

Consequently, P (τn νn ∥Z2 ∥2 + σm |Z1 | > γ)   p p √ ≤ P ∥Z2 ∥2 > d + 2 log(1/ρ) + P(|Z1 | > 2 log(1/ρ)) ≤ 3ρ = on (1). Since γ = on (1), it follows that T̄n − Tn = op (1),

Q̄n,m − Qn,m = op (1). 36

By Assumption 2,

p

d

→ T, Tn −

Qn,m → − q1−α ,

where T has CDF F . By Slutsky’s theorem, p

d

→ T, T̄n −

Q̄n,m → − q1−α .

To handle the possibly dependent random cutoff, fix ε > 0. We have P(T̄n < q1−α − ε) − P(Q̄n,m < q1−α − ε) ≤ P(T̄n < q1−α − ε, Q̄n,m ≥ q1−α − ε) ≤ P(T̄n < Q̄n,m ). p

Now, take lim inf on both sides. Since Q̄n,m → − q1−α , P(Q̄n,m < q1−α − ε) → 0. Also, since F is continuous, P(T̄n < q1−α − ε) → P(T < q1−α − ε) = F (q1−α − ε). It follows that F (q1−α − ε) ≤ lim inf P(T̄n < Q̄n,m ). n→∞

Similarly, it can be shown that lim sup P(T̄n < Q̄n,m ) ≤ F (q1−α + ε). n→∞

Letting ε ↓ 0 yields P(T̄n < Q̄n,m ) = F (q1−α ) + on (1) = 1 − α + on (1). Hence, P(T̄n ≥ Q̄n,m ) = α + on (1). Finally, the actual and auxiliary outputs agree on the event En , and  
e n,m − P T̄n ≥ Q̄n,m ≤ P(Enc ) ≤ ρ. P τn d(θ, θen ) ≥ Q Since ρ = on (1), we conclude that   e n,m = α + on (1). P τn d(θ, θen ) ≥ Q

37

E

Proofs of Proposition, 5.1, 5.3 and Lemma 5.4

E.1

Proof of Proposition 5.1

For any distribution ν and set A, we let ν(A) denote the probability Px∼ν (x ∈ A). Let P0 := N (0, 1) and R0 := N (µ, 1), viewed as distributions on the enlarged space R := R ∪ {⊥}, with zero mass assigned to the atom ⊥. Clearly, T (P0 , R0 ) = Gµ . We first construct a distribution Rδ such that T (P0 , Rδ ) = Gµ,δ

and

TV(Rδ , R0 ) = δ.

(13)

If δ = 0, simply take Rδ = R0 . Suppose therefore that δ > 0. Define cδ := µ + Φ−1 (δ), so that R0 ((−∞, cδ ]) = δ. Define Rδ by moving this lower-tail mass to the additional point ⊥:
Rδ (A) := R0 A ∩ (cδ , ∞) + δ 1{⊥ ∈ A}. It follows immediately that TV(Rδ , R0 ) = δ. Next, we calculate T (P0 , Rδ ). The likelihood ratio of Rδ with respect to P0 is infinite at ⊥, zero on (−∞, cδ ], and equal to   (x−µ)2   √1 exp − 2 µ2 2π  = exp µx −  2 2 √1 exp − x 2 2π on (cδ , ∞), which is non-decreasing in x. By the Neyman–Pearson lemma, an optimal test first rejects at ⊥ and then rejects for sufficiently large values of x. Fix α ∈ [0, 1] and let zα := Φ−1 (1 − α). (i) If zα ≥ cδ , the rejection region {⊥} ∪ [zα , ∞) has Type I error α and Type II error Rδ ((−∞, zα )) = R0 ((cδ , zα )) = Φ(zα − µ) − δ = Gµ (α) − δ. The condition zα ≥ cδ is equivalent to Gµ (α) ≥ δ. (ii) If zα < cδ , rejecting on {⊥} ∪ (cδ , ∞) has Type I error at most α and Type II error zero. Consequently, T (P0 , Rδ )(α) = max{Gµ (α) − δ, 0} = Gµ,δ (α).

38

This proves equation (13). Next, we prove the two implications of the proposition. (⇒) Suppose T (P, Q) ≥ Gµ,δ . By equation (13), T (P, Q) ≥ T (P0 , Rδ ). By Blackwell-Sherman-Stein informativeness theorem [Bla51, She51, Ste51, Bla53], there exists a randomized algorithm K such that K(P0 ) = P and K(Rδ ) = Q. Let R := K(R0 ). By the data-processing inequality for trade-off functions, T (P, R) = T (K(P0 ), K(R0 )) ≥ T (P0 , R0 ) = Gµ . Moreover, by the data-processing inequality, TV(Q, R) = TV(K(Rδ ), K(R0 )) ≤ TV(Rδ , R0 ) = δ. (⇐) Suppose there exists a distribution R such that T (P, R) ≥ Gµ

and

TV(Q, R) ≤ δ.

Fix α ∈ [0, 1], and let ϕ be any possibly randomized test satisfying EP [ϕ] ≤ α. The variational characterization of total variation gives |EQ [ϕ] − ER [ϕ]| ≤ δ. Therefore, 1 − EQ [ϕ] ≥ 1 − ER [ϕ] − δ ≥ T (P, R)(α) − δ ≥ Gµ (α) − δ. Taking the infimum over all tests with Type I error at most α gives T (P, Q)(α) ≥ Gµ (α) − δ. Since a trade-off function is nonnegative, T (P, Q)(α) ≥ max{Gµ (α) − δ, 0} = Gµ,δ (α).

E.2

Proof of Proposition 5.3

We restate the proposition for k = 2 here. Proposition E.1. Suppose M1 : X → Y1 is (µ1 , δ1 )-GDP and M2 : X × Y1 → Y2 is such that M2 (·, y1 ) is (µ2 , δ2 )-GDP for any y1 ∈ Y1 . Then the mechanism M(D) = (Y1 , Y2 ), where  p 2 2 µ1 + µ2 , δ1 + δ2 − δ1 δ2 -GDP. Y1 = M1 (D) and Y2 = M2 (D, Y1 ), is Note that Proposition 5.3 follows by a repeated application of Proposition E.1. Proof. Fix neighboring datasets D and D′ . Let P1 and Q1 be the distributions of M1 (D) and M1 (D′ ), respectively. For any y1 ∈ Y1 , let P2y1 and Qy21 be the distributions of M2 (D, y1 ) and M2 (D′ , y1 ), respectively. Then, the distribution P of MD has marginal distribution P1 on Y∞ and P2y1 on Y∈ for any y1 ∈ Y1 , and the distribution Q of MD has marginal distribution Q1 on Y∞ and Qy21 on Y∈ for any y1 ∈ Y1 39

Since M1 is (µ1 , δ1 )-GDP, there exists a probability distribution R1 on Y1 such that TV(Q1 , R1 ) ≤ δ1 .

T (P1 , R1 ) ≥ Gµ1 ,

Similarly, because M2 (·, y1 ) is (µ2 , δ2 )-GDP for every y1 ∈ Y1 , there exists, for each such y1 , a probability distribution R2y1 on Y2 such that TV(Qy21 , R2y1 ) ≤ δ2 .

T (P2y1 , R2y1 ) ≥ Gµ2 ,

Define the distribution R on Y1 × Y2 that has marginal distribution R1 of Y∞ and R2y1 over Y∈ for any y1 ∈ Y1 . The composition formula for GDP (equation (3)) implies that T (P, R) ≥ G√µ2 +µ2 . 1

2

It remains to compare the distributions Q and R. Take a maximal coupling π1 of Q1 and R1 . Moreover, for every y1 ∈ Y1 , take a maximal coupling γy1 of Qy21 and R2y1 . Consider the following coupling Γ between Q and R: 1. Sample (y1 , y1′ ) from π1 . 2. If y1 = y1′ , then sample (y2 , y2′ ) from γy1 . Otherwise, sample (y2 , y2′ ) from the product distriy′

bution Qy21 × R21 . Clearly, the distribution of (y1 , y2 ) is that of Q, and the distribution of (y1′ , y2′ ) is that of R. Moreover, P((y1 , y2 ) ̸= (y1′ , y2′ )) = P(y1 ̸= y1′ ) + P(y1 = y1′ and y2 ̸= y2′ ). = P(y1 ̸= y1′ ) + P(y2 ̸= y2′ |y1 = y1′ )P(y1 = y1′ ) ≤ P(y1 ̸= y1′ ) + δ2 P(y1 = y1′ ) = (1 − δ2 )P(y1 ̸= y1′ ) + δ2 ≤ δ1 (1 − δ2 ) + δ2 = δ1 + δ2 − δ1 δ2 . Consequently, T V (Q, R) ≤ δ1 +δ2 −δ1 δ2 . We have constructed an auxiliary distribution R satisfying T (P, R) ≥ G√µ2 +µ2 , 1

2

TV(Q, R) ≤ δ1 + δ2 − δ1 δ2 .

Since P and Q are the distributions of M(D) and M(D)′ respectively, the result follows.

E.3

Proof of Lemma 5.4

Proof. Fix neighboring datasets D and D′ . Let θ = θ(D) and θ′ = θ(D′ ). By the definition of local sensitivity, ∥θ − θ′ ∥2 ≤ LS(D′ ), where the local sensitivity is with respect to the statistic θ(·). Define L′ = LS(D′ ) and ∆ = ∥θ − θ′ ∥2 . Then, ∆ ≤ L′ Let P1 and Q1 be the distributions of B(D) and B(D′ ) respectively, which is supported on R>0 . For every positive real number b, define the normal distributions     2 b2 (b) (b) ′ b P2 = N θ, 2 Id , Q 2 = N θ , 2 Id . µ2 µ2 40

  · Z , where Z is the dThen, the distribution P on R × Rd of the tuple B(D), θ(D) + B(D) µ2 dimensional standard normal distribution, can be described by sampling a positive real b from (b) B(D) and then sampling a vector v ∈ Rd from P2 . Define the distribution Q similarly. To compare the laws P and Q, we introduce an auxiliary distribution R that will be shown to be close to both. The distribution R supported on R>0 × Rd is defined through the following sampling procedure. First, draw B ∼ Q1 . Conditional on B = b, draw V according to ( (b) P2 , b < L ′ , (V | B = b) ∼ (14) (b) Q2 , b ≥ L′ . The joint law of (B, V) is denoted by R. First, Q and R are close in total variation. Indeed, consider any measurable set E ⊆ R>0 × Rd . For each b > 0, let Eb be the set of vectors v ∈ Rd such that (b, v) ∈ E. Then, Z   (b) (b) |Q(E) − R(E)| = Q2 (Eb ) − R2 (Eb ) Q1 (b) db b>0 Z   (b) (b) Q2 (Eb ) − P2 (Eb ) Q1 (b) db = ′ Z b<L (b) (b) ≤ Q2 (Eb ) − P2 (Eb ) Q1 (b) db b<L′ Z ≤ Q1 (b) db = P(B(D′ ) < L′ ), b<L′

which is at most δ by the definition of B. Taking a supremum over all such E, it follows that TV(Q, R) ≤ δ. Next, we show that T (P, R) ≥ G√µ2 +µ2 . The first-marginals of P and R are P1 and Q1 . Since B is µ1 -GDP, T (P1 , Q1 ) ≥ Gµ1 .

1

2

(b)

Conditioned on the first marginal b > 0, the conditional law of the second marginal of P is P2 (b) (b) (b) that of R is R2 , which is equal to P2 if b < L′ and Q2 if b ≥ L′ (b)

If b < L′ , then the conditional distributions P2

and

(b)

and R2 are identical.

If b ≥ L′ , then ∆ ≤ L′ ≤ b. Consider the normal distributions     2 b2 (b) (b) ′ b P2 = N θ, 2 Id versus Q2 = N θ , 2 Id . µ2 µ2 ∆ The trade-off curve between these two distributions is Gµ′ for µ′ = b/µ ≤ µ2 . 2

Either way, the conditional second coordinate is µ2 -GDP for every b. By composition of GDP mechanisms (equation (3)), T (P, R) ≥ G√µ2 +µ2 . In all, the distribution R satisfies 1

T (P, R) ≥ G√ 2

µ1 +µ22

2

and

TV(Q, R) ≤ δ.

Therefore, T (P, Q)(α) ≥ G√µ2 +µ2 ,δ (α), and the output 1 2   B(D) B(D), θ(D) + · N (0, Id ) µ2 41

is (

p µ21 + µ22 , δ)-GDP.

Finally, consider PTR-GDP (Algorithm 3), which defines   β β −1 B(D) ← SSβ (D) · exp · Z1 + · Φ (1 − δ) . µ µ Note that B(D) as defined above is µ-GDP. Indeed, since SSβ is β-smooth, log SSβ has global sensitivity at most β. It follows that log SSβ + βµ · Z1 is µ-GDP, so B(D) is also µ-GDP by postprocessing. By the definition of smooth sensitivity, SSβ (D) ≥ LS(θ, D). Also, Z1 ≥ Φ−1 (1 − δ) with probability equal to 1 − δ. Therefore, B(D) ≥ LS(θ, D) with p probability at least √ 1 − δ. In all, it follows that 2 2 PTR-GDP is approximately GDP with parameters ( µ + µ , δ) = ( 2µ, δ).

F

Proofs related to CR-SS

F.1

Proof of Lemma 5.5

Proof. Consider two neighboring datasets D and D′ . Since any index appears at most κ⋆ times in Si , the subsampled datasets D[Si ] and D′ [Si ] differ in at most κ⋆ elements. Consider a sequence of adjacent datasets D0 = D[Si ] ∼ D1 ∼ D2 , . . . , ∼ Dr = D′ [Si ], where r ≤ κ⋆ . Let d(x, y) = ∥x − y∥2 . By the triangle inequality, d(θ(D[Si ]), θ(D′ [Si ])) = d(θ(D0 ), θ(Dr )) ≤

r−1 X

d(θ(Dq ), θ(Dq+1 )) ≤

q=0

r−1 X

LS(θ, Dq ).

q=0

Now, LS(θ, D0 ) ≤ SSβ (θ, D[Si ]) =: si when D[Si ] is viewed as a dataset on m “distinct” elements. Moreover, since SSβ is β-smooth, LS(θ, D1 ) ≤ eβ si , LS(θ, D2 ) ≤ e2β si , and in general LS(θ, Dq ) ≤ eqβ si for all 0 ≤ q ≤ r − 1. Thus, d(θ(D[Si ]), θ(D′ [Si ])) ≤

r−1 X q=0

eqβ si ≤

eκ⋆ β − 1 si . eβ − 1

Finally, note that the local sensitivity of the function   ⋆ b Quantile1−α d(θ1⋆ , θbn ), d(θ2⋆ , θbn ), . . . , d(θB , θn ) is bounded by the maximum of the local sensitivities of d(θi⋆ , θbn ), which is further upper bounded by the sum of the local sensitivities of θi⋆ and θbn due to triangle inequality. Therefore,   eκ⋆ β − 1 ⋆ b LS(Quantile1−α d(θ1⋆ , θbn ), d(θ2⋆ , θbn ), . . . , d(θB , θn ) ) ≤ max SSβ (D[Si ])· β +SSβ (D) = s(D), e −1 i∈[B] and LS(Qn,m (D)) ≤ τm s(D). 42

F.2

Proof of privacy of Theorem 5.6

Proof. The resampling indices are drawn independently of the data. It is therefore enough to prove privacy for every fixed realization of the resampling indices satisfying the multiplicity constraint. For a realization that does not satisfy the constraint, the algorithm returns the fixed symbol ⊥ κ⋆ β −1 and is trivially private. Fix an (accepted) realization (S1 , . . . , SB ), and define rβ,κ⋆ := e eβ −1 . ′ ′ For neighboring datasets D ∼ D , the datasets D[Si ] and D [Si ] differ in at most κ⋆ entries. The telescoping argument in Lemma 5.5 therefore gives
d θ(D[Si ]), θ(D′ [Si ]) ≤ rβ,κ⋆ SSβ (θ, D[Si ]).
Moreover, d θ(D), θ(D′ ) ≤ SSβ (θ, D). Consequently, if
ai (D) := d θ(D[Si ]), θ(D) , then |ai (D) − ai (D′ )| ≤ rβ,κ⋆ SSβ (θ, D[Si ]) + SSβ (θ, D). Since an empirical quantile, viewed as an order statistic, is 1-Lipschitz with respect to the ℓ∞ norm of its inputs,   LS(Qn,m ; D) ≤ τm rβ,κ⋆ max SSβ (θ, D[Si ]) + SSβ (θ, D) = τm s(D). i∈[B]

It remains to verify the smoothness of this upper bound. Note that D[Si ] and D′ [Si ] differ in at most κ⋆ entries, so SSβ (θ, D[Si ]) ≤ eκ⋆ β SSβ (θ, D′ [Si ]). Also,

SSβ (θ, D) ≤ eβ SSβ (θ, D′ ) ≤ eκ⋆ β SSβ (θ, D′ ).

It follows that s(D) ≤ eκ⋆ β s(D′ ), and the reverse inequality follows by interchanging D and D′ . Thus, τm s is a κ⋆ β-smooth upper bound on LS(Qn,m ; ·). The first call to PTR-GDP uses the β-smooth upper bound SSβ (θ, ·) and privacy parameters √
(µ/2, δ/2). By Lemma 5.4 and post-processing, its output θen is µ/ 2, δ/2 -GDP. The second e call √ uses the
κ⋆ β-smooth upper bound τm s and the same privacy parameters. Hence Qn,m is also µ/ 2, δ/2 -GDP. The final projection onto [0, ∞) is post-processing. By Proposition 5, the joint output is r   !   µ2 µ2 δ 2 δ2 + ,1 − 1 − = µ, δ − -GDP. 2 2 2 4 Since δ − δ 2 /4 ≤ δ, the conditional mechanism is (µ, δ)-GDP. Since the resampling indices and the accept/reject decision are independent of the data, releasing them first costs no privacy. For each realization, the subsequent mechanism is (µ, δ)-GDP. Dropping the indices is post-processing.

43

F.3

Proof of utility of Theorem 5.6

As in the proof of Theorem 1, regard all resamples as drawn before the multiplicity check and define the auxiliary outputs   2Cn,m 2Bn b θ̄n = θn + G1 , Q̄n,m = max Qn,m + G2 , 0 , µ µ where G1 ∼ N (0, Id ), G2 ∼ N (0, 1), and 
2β −1 Bn = SSβ (θ, D) exp Z1 + Φ (1 − δ/2) , µ  
2κ⋆ β −1 Cn,m = τm s(D) exp Z2 + Φ (1 − δ/2) . µ 

Here Z1 , Z2 ∼ N (0, 1) are independent of G1 , G2 . By the assumptions on the smooth sensitivities, the choice of β, and a union bound, with probability at least 1 − O(ρ), Bn ≤ eΓn,ρ and

Cn,m ≤ τm κ⋆ e2 Γm,ρ/B + eΓn,ρ .

Indeed,

κ −1

⋆ X eκ⋆ β − 1 = ejβ ≤ κ⋆ eκ⋆ β ≤ κ⋆ e. eβ − 1

j=0

Let Tn := τn d(θ, θbn ),

T̄n := τn d(θ, θ̄n ).

Since projection onto [0, ∞) is 1-Lipschitz, |T̄n − Tn | ≤

2τn Bn ∥G1 ∥2 , µ

|Q̄n,m − Qn,m | ≤

2Cn,m |G2 |. µ

Gaussian concentration and the assumptions Γn,ρ = o

µ p √ τn ( d + log(1/ρ))

! ,

Γm,ρ/B = o

µ p τm κ⋆ log(1/ρ)

therefore imply T̄n − Tn = op (1),

Q̄n,m − Qn,m = op (1).

By Assumption 3.8, d

Tn − → T,

p

where q1−α := F −1 (1 − α).

Qn,m → − q1−α ,

By Slutsky’s theorem, d

T̄n − → T,

p

Q̄n,m → − q1−α . 44

!

Lemma B.4 now gives P(T̄n < Q̄n,m ) = 1 − α + on (1). The auxiliary outputs agree with the outputs of Algorithm 4 whenever the multiplicity check succeeds, whose failure probability is at most ρ = on (1). Therefore, ! e n,m Q P d(θ, θen ) < = 1 − α + on (1). τn Finally,   e n,m Q Qn,m = max + σpriv G2 , 0 , τn τn

σpriv =

2Cn,m , µτn

where G2 is independent of σpriv . Thus, with probability at least 1 − O(ρ), σpriv ≤ Moreover,

2τm κ⋆ e2 Γm,ρ/B + eΓn,ρ . µτn 2Cn,m G2 = op (1). µ

p

Since Qn,m → − q1−α > 0, the truncation is inactive with probability 1 − on (1).

G

Proofs for Confidence Intervals of Quantiles (Section 6.1)

Theorem G.1. Let ρ, ζ, ζ ′ ∈ (0, 1) with ζ ′ + n2 ≤ ζ ≤ 1 − ζ ′ − n2 , and suppose D is a distribution supported on [ℓ, u] such that the density f of D is continuous and satisfies n h io p p min f (x) : F (x) ∈ 1 − ζ − ζ ′ − (log 1/ρ)/2n, 1 − ζ + ζ ′ + (log 1/ρ)/2n ≥ λ. x

Let m = ⌊n(1 − ζ)⌋ and k = ⌈nζ ′ ⌉, and assume ζ ′ satisfies   8 log(1/ρ)  2 1  u−ℓ 1 1 + 8 log(1/ρ) max + log + 3 log n , ≤ ζ′ ≤ − . n nβ C n 2 2n (1−ζ)

Then, with probability at least 1 − 4ρ, the β-smooth function SSβ

G.1

6k (θ, D) ≤ nλ + nC3 .

Proof of Lemma 6.1 (1−ζ)

The expression for SSβ (θ, D) is the smooth sensitivity construction of [NRS07] for the median and the minimum generalized to quantiles. For a dataset D′ which has Hamming distance at most k from D, the index of the (1 − ζ)-quantile can shift by at most k positions, and the worst-case shift of the order statistic within this window is captured by maxk+1 t=0 (x(h+t) − x(h+t−k−1) ). This yields a β-smooth upper bound on the local sensitivity.

45

For the truncation, note that for any k and t we always have 0 ≤ x(h+t) − x(h+t−k−1) ≤ u − ℓ, by the extension x(j) ∈ [ℓ, u]. Hence, for k ≥ k ⋆ , e−kβ max



0≤t≤k+1

 C ⋆ x(h+t) − x(h+t−k−1) ≤ e−k β (u − ℓ) ≤ 3 , n

where the last inequality is exactly the definition of k ⋆ . Therefore, (1−ζ)

SSβ

(θ, D) ≤ max ⋆ e−kβ 0≤k≤k

max

0≤t≤k+1



x(h+t) − x(h+t−k−1)



+

C . n3

Finally, since e−kβ ≤ 1 and enlarging k enlarges the index range,     x(h+t) − x(h+t−k⋆ −1) ≤ x(h+k⋆ +1) − x(h−k⋆ −1) , max ⋆ max x(h+t) − x(h+t−k−1) ≤ max⋆ 0≤t≤k +1

0≤k≤k 0≤t≤k+1

which gives the stated simplified bound.

G.2

Proof of Theorem G.1

Lemma G.2. Let ρ ∈ (0, 1), and suppose ζ, ζ ′ ∈ (0, 1) satisfy ζ′ +

2 2 ≤ ζ ≤ 1 − ζ′ − , n n

8 log(1/ρ) n − 1 − 8 log(1/ρ) ≤ ζ′ ≤ . n 2n

Suppose D is a distribution supported on [ℓ, u] and let X1 , . . . , Xn be i.i.d draws from D. Let X(1) ≤ X(2) ≤ . . . X(n) denote the order statistics and let h = ⌊n(1 − ζ)⌋. Define a neighborhood of p the 1 − ζ quantile F −1 (1 − ζ) as the set W = {x : |F (x) − (1 − ζ)| ≤ ζ ′ + (log 1/ρ)/2n}. If the density f of D is continuous and satisfies min f (x) ≥ λ,

x∈W

then, for k = ⌈nζ ′ ⌉,   6k ≤ 4ρ. P X(h+k) − X(h−k) ≥ nλ Proof. With the constraint on ζ and ζ ′ , we know that 1 ≤ h − k ≤ h + k ≤ n. Define Uj := F (Xj ) and note that Uj is distributed as Uniform([0, 1]). By mean value theorem, X(h+k) − X(h−k) = F −1 (U(h+k) ) − F −1 (U(h−k) ) = for some ξ ∈ [F −1 (U(h−k) ), F −1 (U(h+k) )].

46

U(h+k) − U(h−k) f (ξ)

For any index j and t, P[U(j) ≥ t] is equal to P[Bin(n, t) ≤ j − 1] (the probability that at most j − 1 of the n independent samples from Uniform([0, 1]) exceed q j − 1). Since E[Bin(n, t)] = nt, applying a Chernoff bound with j = h + k and t = h+k n + ε for ε =

log 1/ρ gives 2n

h+k 2 + ε] ≤ e−2nε = ρ n A similar lower tail bound for U(h−k) implies P[U(h+k) ≥

P[U(h−k) ≤

h−k 2 − ε] ≤ e−2nε = ρ n

Consequently, with probability at least 1 − 2ρ the value F (ξ) ∈ [1 − ζ − ζ ′ − q log 1/ρ 2n ].

q

log 1/ρ ′ 2n , 1 − ζ + ζ +

Under this event and by assumption, X(h+k) − X(h−k) ≤

U(h+k) − U(h−k) . λ

Now, define the random variables {Gi }0≤i≤n as G0 = U(1) , Gi = U(i+1) − U(i) for i ∈ [1, n − 1], and Gn = 1 − U(n) . By the Rényi representation of order statistics [Rén53, DN04],   Yn Y0 d ,..., (15) (G0 , G1 , . . . , Gn ) = S S P where Yi ∼ Exp(1) i.i.d for 0 ≤ i ≤ n and let S = i Yi . Therefore Ph+k−1 A i=h−k Gi U(h+k) − U(h−k) = P = , n G A + B i=0 i where A ∼ Γ(2k, 1) and B ∼ Γ(n − 2k + 1, 1) are independent. By a Chernoff bound, P[A > 3k] ≤ e−k/8 ,

P[B < (n − 2k + 1)/2] ≤ e−(n−2k+1)/8 .

By assumption on ζ ′ , both k/8 and (n − 2k + 1)/8 are at least log 1/ρ. Overall, with probability at least 1 − 4ρ, 3k 6k 6k U(h+k) − U(h−k) ≤ = < . 3k + (n − 2k + 1)/2 n + 4k + 1 n Since Theorem G.1 has the assumptions of Lemma G.2, we have with probability at least 1 − 4ρ that 6k . X(h+k) − X(h−k) ≤ nλ

We also have k − 1 ≥ nζ ′ − 1 ≥ 1 +

 1  1 u−ℓ u−ℓ log + 3 log n ≥ log + 3 log n β C β C

so Lemma 6.1 implies that (1−ζ)

SSβ

(θ, D) ≤ X(h+k) − X(h−k) + 47

C 6k C ≤ + . n3 nλ n3

G.3

Calculating the confidence radius

C N We now apply Theorem 5.6 with ΓN,ρ := 6K N λ + N 3 for all N, ρ as the upper bound on the smooth sensitivity above (the failure probability ρ is pushed into the condition on the density around the 1 − ζ quantile) and KN := max{β −1 (log(C −1 (u − ℓ)) + 3 log N ), 0}.

We use Theorem G.1 to obtain a utility guarantee for confidence intervals for quantiles. As in the theorem, let ! 1 µ β= min 1, p . 2κ⋆ 4 log B/(δρ) Suppose

s f (x) ≥ λ for all F (x) ∈ 1 − ζ ±

′

ζ +

max



log(B/ρ) log(1/ρ) , 2m 2n

! .

If Assumption 3.8 holds, ρ = on (1), and √  p p (log n) d + log(1/ρ) (log m) log(1/ρ) √ √ + = on (1), nλµ mλµ then with probability at least 1−8ρ, CR-SS (Algorithm 4) outputs an asymptotically 1−α confidence e n,m /τn for the 1 − ζ quantile of the distribution D. Moreover, the half-length of this interval θen ± Q confidence interval is equal to the non-private radius Qn,m /τn plus the private noise σpriv G, where G is a standard normal with scale σpriv given by !   1/2
κ k 2τm m Cκ 1 ⋆ ⋆ 2 √ σpriv ≤ Γ κ⋆ e + Γn,ρ e = O + . + = Õ √ µτn m,ρ/B µ mnλ n3/2 λ m5/2 n1/2 mn √ Note that the non-private error of a quantile when using n samples is O(1/ n) whereas the private √ error we obtain has scale Õ(1/ mn).

H

Proofs for Degenerate U-statistics (Section 6.2)

Private estimation for non-degenerate and degenerate U -statistics bn ) that satisfies β-smooth upper bound on LS(U bn ) ≤ r SSβ (U n

[CLPS24] provide a

   2   rC(1/β + L) r2 2 2 r ξ+ (1 + β(1 + L)) + 2 C + L min r, + L β+ . n n β β n

where C is the diameter of the support of the distribution, L = L(D) is a positive integer which is an upper bound on the number of bad data points in D (we omit the exact details on what a bad data point is here) and ξ is a concentration parameter. This bound works for any statistic, not necessarily degenerate U-statistics. 48

The parameter ξ is such that the n U statistics A1 , . . . , An , which they call Hájek projections, each satisfy |Ak − Un | ≤ ξ ∀ k with high probability. The Hâjek projections Ai are defined as X 1 Ak := n−1
h(Xk , Xi1 , . . . , Xir−1 ), r−1

1≤i1 <i2 <···<ir−1 ≤n,ij ̸=k∀j

which fixes Xk to be one of the inputs of h and sums over other r − 1 out of n − 1 possible inputs. In general, ξ can always be taken as C, which is the range pof the kernel h. For degenerate U -statistics, Lemma 6 of [CLPS24] shows that ξ can be taken as C r/n log(2n/ρ) + 8Cr/3n log(2n/ρ). Therefore, we can apply Theorem 5.6 with β as in the theorem and    2   r rC(1/β + L) r2 2 2 r Γn,ρ := ξ+ (1 + 2β(1 + L)) + 2 C + L min r, + L β+ . n n n β β n Therefore, we can apply Theorem 5.6 with β as in the Theorem and τN = N (assuming the statistic is degenerate of order 1). Another point to note is that with the beforementioned choice of ξ, L(D) = 1 with probability at least 1 − ρ (where the randomness is over the data distribution, not the algorithm). In this case, the smooth sensitivity at a typical input is is bounded above as Γn,ρ ≤

r3/2 C log(2n/ρ)(1 + 2β) + tn,β , n3/2

where tn,β = Oβ (1/n2 ) for a fixed r. It follows that with probability 1 − O(ρ) the private overhead of the confidence radius is equal to σpriv · G where ! 3/2 log(Bn) 2m r √ σpriv ≤ . (Γ κ⋆ e2 + Γn,ρ e) = Õ nµ m,ρ/B n m

H.1

Confidence regions for averaged SGD

Let K ⊂ Rd be a public compact convex set with nonempty interior. Suppose that ℓ(·; x) is twice continuously differentiable on a neighborhood of K and, for every x ∈ X and w ∈ K, λId ⪯ ∇2 ℓ(w; x) ⪯ LId ,

(16)

∥∇ℓ(w; x)∥2 ≤ G,

where 0 < λ ≤ L and G > 0 are public constants. For DN = (X1 , . . . , XN ) and a permutation π of [N ], define
wt = ΠK wt−1 − ηt ∇ℓ(wt−1 ; Xπ(t) ) ,

t ∈ [N ],

1 θbN = θ(DN ; π) := N

N X

wt ,

(17)

t=1

where w0 ∈ K is public. Take ηt = c(t + t0 )−a , with c > 0, a ∈ (1/2, 1), and a fixed t0 ≥ 1 sufficiently large that −1 ηt ≤ L−1 , ηt+1 − ηt−1 ≤ λ/2, t ≥ 0. (18) Each estimator evaluation uses an independent uniform permutation, independent of the data, and restarts from the same w0 and step schedule. Thus, there is one pass through the input positions, including repeated observations in a with-replacement resample. 49

Lemma H.1 (Global sensitivity of averaged SGD). Under (16)–(18), for every fixed permutation π,
4G ∆2 θ(·; π) ≤ ∆N := . λN In particular, conditional on the permutation, averaged SGD is mean-like with ℓN = 4G/λ. Proof. Fix neighboring datasets and use the same permutation. Suppose that the changed record is visited at time j, and let δt := ∥wt − wt′ ∥2 . The Hessian bounds and nonexpansiveness of ΠK imply that each unchanged update is (1 − ληt )-Lipschitz. Hence δt ≤ (1 − ληt )δt−1 + 2Gηt 1{t = j},

t Y

δt ≤ 2Gηj

(1 − ληs ) (t ≥ j).

s=j+1

Set Aj,N := 2/(ληN ), and

PN Qt t=j

s=j+1 (1 − ληs ).

Backward induction gives Aj,N ≤ 2/(ληj ): AN,N = 1 ≤

Aj,N = 1 + (1 − ληj+1 )Aj+1,N ≤

2 2 −1≤ , ληj+1 ληj

where the last inequality uses (18). Therefore, N

′ ∥θ(DN ; π) − θ(DN ; π)∥2 ≤

2Gηj 1 X 4G δt ≤ Aj,N ≤ . N N λN t=1

Fact H.2 (Asymptotic normality of averaged SGD; [PJ92]). Suppose that d is fixed, X1 , . . . , XN are i.i.d. from P , and (16)–(18) hold. Assume that f (w) := EP [ℓ(w; X)] is finite on K, its minimizer θ := arg minw∈K f (w) lies in int(K), and ∥∇2 ℓ(u; x) − ∇2 ℓ(v; x)∥op ≤ M ∥u − v∥2

(u, v ∈ K, x ∈ X )

for a finite constant M . Let H := ∇2 f (θ),

h i V := EP ∇ℓ(θ; X)∇ℓ(θ; X)⊤ ,

If V ≻ 0, then

√

Σ := H −1 V H −1 .

d

N (θbN − θ) − → N (0, Σ).

More precisely, √

N

1 X N (θbN − θ) = −H −1 √ ∇ℓ(θ; Xt ) + RN , N t=1

E∥RN ∥2 ≤ C N (a−1)/2 + N 1/2−a .

(19)

The constant C is uniform over distributions satisfying the same bounds and a common positive lower bound on dist(θ, ∂K).

50

Proof. Since a data-independent permutation preserves the i.i.d. law, take π to be the identity. Write et = wt − θ. Nonexpansiveness, strong convexity, and (18) give E∥et ∥22 ≤ (1 − ληt )E∥et−1 ∥22 + G2 ηt2 ≤ Cηt , where the last inequality follows by induction. Decompose ∇ℓ(wt−1 ; Xt ) = Het−1 + gt + ξt + rt ,

gt := ∇ℓ(θ; Xt ),

rt := ∇f (wt−1 ) − Het−1 .

Then ξt is a martingale difference and E∥ξt ∥22 ≤ L2 E∥et−1 ∥22 ,

∥rt ∥2 ≤ (M/2)∥et−1 ∥22 .

Let pt := ηt−1 (wt − wt−1 ) + ∇ℓ(wt−1 ; Xt ) be the projection correction. If r0 := dist(θ, ∂K), then ∥pt ∥2 ≤ G, and, for all sufficiently large t, pt = 0 whenever ∥et−1 ∥2 < r0 /2. Consequently, E∥pt ∥2 ≤ Cηt−1 for all sufficiently large t. It follows that N

1 X E √ ξt N t=1

= O(N

−a/2

),

2

N  1 X  √ E ∥rt ∥2 + ∥pt ∥2 = O(N 1/2−a ). N t=1

Also, summation by parts gives N X et−1 − et t=1

ηt

N −1

=

X e0 eN −1 − ηt−1 )et , + (ηt+1 − η1 ηN t=1

a/2 whose expected norm the recursion√et − et−1 = −ηt (Het−1 + gt + ξt + rt − pt ), PN is O(N √). Summing −1/2 b e = and using N N ( θ − θ) + (e0 − eN )/ N , proves (19). All bounds are uniform N t=1 t−1 under the stated restrictions. Finally, Egt = 0, Cov(gt ) = V , and the multivariate central limit theorem and Slutsky’s theorem give the result.

Lemma H.3 (Private confidence regions for averaged SGD). Suppose that the assumptions of Fact H.2 hold. Fix α ∈ (0, 1) and µ > 0. Run CR-GS (Algorithm 2) with √ 4G θbn = θ(D; π0 ), θi⋆ = θ(D[Si ]; πi ), τN = N , ∆N = . λN Use κ⋆ = 1 for WOR and κ⋆ = κ⋆ (n, m, B, ρ) from equation (4) for WR. Then the algorithm is µ-GDP. If m → ∞, m/n → 0, B → ∞, ρ = on (1), and ! p p √ d + log(1/ρ) κ⋆ log(1/ρ) G √ √ + = on (1), (20) λµ n m then, for either resampling mode, ( P(θ ∈ Cn,α ) = 1 − α + on (1),

Cn,α :=

e n,m Q u ∈ Rd : ∥u − θen ∥2 < √ n

Set Cn,α = ∅ if the algorithm returns ⊥. On return, its confidence radius satisfies   e n,m Q Qn,m √ = max √ + σpriv Z1 , 0 , Z1 ∼ N (0, 1), n n where

√    √  4 2G κ⋆ m Gκ⋆ √ √ + σpriv = =O . λµ mn n3/2 λµ mn 51

) .

Proof. For privacy, fix the resampling indices and permutations. On an accepted realization, changing one original record changes each resample in at most κ⋆ positions. Lemma H.1 and the ℓ∞ Lipschitz property of order statistics therefore give √ ∆2 (Qn,m ) ≤ m(κ⋆ ∆m + ∆n ). The noise scales in Algorithm 2 are consequently √ √  √  4 2G 4 2G κ⋆ m √ + . νn = , σm = λµn λµ n m

(21)

Proposition 3.7 and GDP composition imply µ-GDP for the joint release. The indices, permutations, and abort decision are data-independent, so averaging over them preserves this guarantee. We next verify resampling validity. Define all resamples before the multiplicity check, and let
√ Ln,m (t) := P⋆ m∥θ(D[S]; π) − θ∥2 ≤ t | D , F (t) := P(∥Z∥2 ≤ t), Z ∼ N (0, Σ). Here P⋆ averages over the resampling indices and permutation. For WOR, Ln,m (t) is a bounded symmetric U-statistic of order m, with the kernel averaged over π. Averaging over disjoint blocks yields 1 ELn,m (t) = Fm (t), Var(Ln,m (t)) ≤ . 4⌊n/m⌋ √ Here Fm (t) := P( m∥θbm − θ∥2 ≤ t). Fact H.2, m/n → 0, and continuity of F therefore imply p supt |Ln,m (t) − F (t)| → − 0. P For WR, put fn (w) := n−1 nj=1 ℓ(w; Xj ) and ϑn := arg minw∈K fn (w). Strong convexity gives ∥ϑn − θ∥2 ≤ λ−1 ∥∇fn (θ)∥2 = Op (n−1/2 ). Thus ϑn has an interior margin bounded away from zero with probability tending to one. Moreover, by the law of large numbers and the Lipschitz assumptions, 2

n

1X p Vn := ∇ℓ(ϑn ; Xj )∇ℓ(ϑn ; Xj )⊤ → − V. n

p

Hn := ∇ fn (ϑn ) → − H,

j=1

Conditional on D, the resampled observations are i.i.d. from the empirical distribution. The uniform bound in (19), applied to this distribution, and the conditional Lindeberg central limit theorem apply: the scores have mean zero on the interior event, are bounded by G, and have covariance √ Vn . Hence the conditional law of m(θ(D[S]; π) − ϑn ) converges in probability to N (0, Σ). Since √ p m∥ϑn − θ∥2 = op (1), this again gives supt |Ln,m (t) − F (t)| → − 0. √ For either p mode, centering at θbn instead of θ changes every resampling pivot by at most m∥θbn − θ∥2 = Op ( m/n) = op (1). Conditional on D and π0 , the B resampling pivots are independent. The DKW inequality and B → ∞ therefore imply p

Qn,m → − q1−α := F −1 (1 − α). Since Σ ≻ 0, F is continuous and strictly increasing on [0, ∞), and q1−α > 0. This verifies Assumption 3.8. 52

Substituting (21) into the definition of γ in Theorem 4.2, condition (20) gives γ = on (1). Gaussian concentration and the 1-Lipschitz property of truncation imply √ e n,m − Qn,m = op (1). n∥θen − θbn ∥2 = op (1), Q Fact H.2 and Lemma B.4 now yield the claimed coverage for the auxiliary outputs defined before the multiplicity check. The actual outputs agree with them except on an event of probability at most ρ = on (1), proving the coverage statement for CR-GS. Finally, the radius formula follows from √ σpriv = σm / n.

53

Related documents

• One-Shot Private Confidence Regions via Resampling#1218195
• Privacy for free in the overparameterized regime#211268
• Contraction and Statistical Inference under Privacy for Uniformly Bounded Distributions#1064841
• DiffMI: Breaking Face Recognition Privacy via Diffusion-Driven Training-Free Model Inversion#189259
• Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy#266105