acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Quantile Inference: Phase Transitions and a Gaussianization Mechanism

Abstract

Private quantile inference requires the distribution of sampling error together with the randomization used for privacy. We characterize this distribution for the rank exponential mechanism under local density regularity and a public bounded output interval. As with , averaging its length-weighted order-statistic gaps yields a conditional Laplace limit independent of the sample fluctuation. This identifies the Gaussian, Gaussian–Laplace, and Laplace regimes, with privacy scale and no logarithmic factor. Neighboring private quantiles estimate the common local scale, giving feasible intervals across regimes. We then change the error distribution through a one-step correction with Gaussian noise added to a bounded quantile score. Under explicit pilot and nuisance conditions, this construction under approximate differential privacy has a Gaussian pivot at every relative noise level. Simulations illustrate the phase laws and show how public range and budget allocation determine the width of feasible rank-based intervals, including the tradeoff between center accuracy and scale estimation.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential privacy, Gaussian-Laplace law, Phase transition, Quantile

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_oxHMOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper studies differentially private quantile estimation, focusing on characterizing the distribution of the estimation error and constructing valid confidence intervals. The authors establish asymptotic Gaussian, Gaussian--Laplace, and Laplace regimes for the rank-based exponential mechanism. They further propose a Gaussian-noise correction that yields an asymptotically Gaussian pivot under approximate differential privacy, enabling confidence interval construction across different privacy regimes.

Critical strengths

The paper provides an interesting characterization of the asymptotic distribution of private quantile estimation errors, identifying different regimes depending on the relative magnitude of sampling and privacy noise. Beyond the theoretical analysis, the paper proposes methods for constructing confidence intervals and provides simulations supporting the theoretical findings, demonstrating the potential practical applicability of the results.

Critical weaknesses

The paper lacks a direct comparison with existing work, either theoretically or experimentally. Although several relevant studies are discussed in the related work section, it remains unclear how the proposed approach compares to previous methods in terms of theoretical guarantees and practical performance. I encourage the authors to provide a more detailed comparison, particularly with Drechsler et al. (2022) and Lalanne et al. (2023), to better highlight the novelty and advantages of their results.

Questions for authors

Could the authors clarify the main theoretical advantages of their approach compared to Lalanne et al. (2023) and Drechsler et al. (2022)? In particular, how do the resulting confidence interval guarantees compare?

3 comments

Thank you for your time and valuable comments. We address the concerns below.

W1. We expanded the endpoint comparison with public-widening sensitivity and evaluated the feasible score procedures, reporting coverage, interval width, and computation.

ExpMech-C uses the widened rank-exponential endpoint construction with an explicit conservative binomial-tail rule. We also evaluate a tighter conservative calibration, keeping the sampler and total pure privacy EE unchanged. The public widening ratios are θ/R∈10−2,10−3,10−4,10−5\theta/R\in\\{10^{-2},10^{-3},10^{-4},10^{-5}\\}, where R=B−AR=B-A. The following representative entries report coverage / mean length at normal n=32000n=32000, E=0.5E=0.5:

RangeQExp-SCOriginal ExpMech-C, θ/R=10−3\theta/R=10^{-3}Original, 10−410^{-4}Tightened, 10−310^{-3}Tightened, 10−410^{-4}
[−8,8][-8,8]0.957 / 0.02860.999 / 0.07010.997 / 0.04371.000 / 0.06910.997 / 0.0427
[−32,32][-32,32]0.957 / 0.02861.000 / 0.16811.000 / 0.05351.000 / 0.16320.999 / 0.0522

These configurations show a precision benefit from private local-scale calibration, while exposing part of the endpoint method's resolution cost. ExpMech-C targets finite-sample coverage at least nominal, while QExp-SC targets asymptotically exact coverage at each regular distribution. Width depends on the widening choice: at standard normal n=32000n=32000, critical E=2/(0.6n)E=2/(0.6\sqrt n), tightened widths across all four choices are 0.6049, 0.3916, 0.4423, and 0.5210. The opposite method ranking also occurs: at wide-range normal n=4000n=4000 and critical privacy, QExp-SC gives 0.983/2.4260, while all four tightened endpoint choices have coverage 1.000 and widths 2.1056, 1.1952, 1.3514, and 1.7244. The wide lognormal configuration has the same reversal.

The complete score-method experiments likewise distinguish computational gains from precision costs; the primary design uses equal-third pilot/nuisance/score blocks, with 20/20/60 as the sensitivity split. The results discussed here use the primary equal-third split. In the large-sample study, GOS is 2.09–3.76 times faster than QExp-SC but 1.76–2.96 times wider; standard lognormal n=32000n=32000, E=0.5E=0.5 retains GOS coverage 0.924. Gaussianization provides a common asymptotic Gaussian calibration under the stated preliminary-estimation conditions.

Q1.

ResultGuarantee and targetInformation used
Drechsler et al. (2022)Finite-sample median coverage at least nominal under its conditions, accounting for sampling and mechanism randomnessPublic output range and privacy/tuning inputs
Lalanne, Garivier and Gribonval (2023), Theorem 3.3Finite-sample quantile value-error tail control within its admissible rangeDensity/regularity constants for direct inversion to a confidence radius
Our feasible private-quantile intervalCoverage tends to 1−α1-\alpha for each fixed locally regular distribution and fixed quantilePublic range, allocated budgets, privately estimated local scale, and a critical value tracking privacy noise

Our conditional privacy-noise limits identify QExp's first-order conditional privacy law and its asymptotic independence from sampling fluctuation. This yields the Gaussian, Gaussian–Laplace, and privacy-dominated laws. Neighboring private quantiles estimate their common local scale, producing feasible distributional calibration without knowing the population density. The resulting calibration addresses each fixed quantile at a locally regular distribution.

Lalanne et al.'s Theorem 3.3 can be inverted when its constants are available and the proposed radius satisfies its applicability conditions. We state this applicability restriction explicitly. Their Remark 3.6 already discusses localizing the lower-density condition. Our log-free 1/(nϵn)1/(n\epsilon_n) scale describes pointwise stochastic error for a fixed quantile and regular distribution; Lalanne et al. analyze many-quantile tail control. Our positive local density assumption also separates this setting from Lalanne et al. (2023).

Our bounded-score one-step correction controls the leading law: the linear pilot error cancels, leaving products with nuisance error and local remainders. Gaussian score noise gives a standard-normal pivot under approximate DP; Laplace score noise retains pure DP and supports the matched-budget leading-component comparison. These guarantees require the stated preliminary-estimation conditions. The matched-budget efficiency comparison assumes N/n→1N/n\to1, while the displayed experiments use fixed-fraction splits. Thus the new inferential law and the measured implementation-speed benefit are distinct contributions.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

Thank you for the detailed response and the additional comparisons. The new experimental results and theoretical discussion substantially address my main concerns.

Thank you very much for reading our response and for letting us know that the new comparisons and the theoretical discussion address your main concerns. We have now uploaded the revised paper, with the changed passages marked in blue, so that these comparisons can be read in context. The comparison with the widened endpoint construction based on Drechsler et al. (2022) is in Section 6.2 (Table 4), and the public-widening sensitivity together with the tightened conservative calibration is in Appendix B.4 (Table 9). The relation of our guarantees to Lalanne et al. (2023) is stated in the Introduction and made explicit in Appendix E.1, where their tail inequality is inverted into a value-error bound.

We would be grateful if you could take a look at the revised version. The discussion period is still open, and if any concern remains we would be glad to address it in the remaining time. If the revision resolves your main concerns, we would greatly appreciate it if you would consider reflecting this in your assessment.

Reviewer_D6B8OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies DP quantile estimation with confidence intervals. The paper studies the interplay between the sampling noise and the DP noise in the total estimation error for the confidence interval. They identify three regimes: (1) ϵn→∞\epsilon \sqrt{n} \to \infty: sampling noise dominates privacy noise, so the estimation error distribution is Gaussian, (2) ϵn→c\epsilon \sqrt{n} \to c, for some constant cc: both contribute, so distribution is a convolution of Gaussian and Laplace, and (3) ϵn→0\epsilon \sqrt{n} \to 0: privacy noise dominates, so final distribution is Laplace. Using this insight, the authors design an algorithm called QExp-SC that computes the exact quantile with confidence intervals, and smoothly interpolates between the three regimes. Unfortunately, QExp-SC's exact calculation requires doing numerical integration, so instead the authors also present GOS, a Gaussianized version of the confidence interval that is cleaner to reason about. They empirically validate that the QExp-SC method produces tighter confidence intervals than prior work.

Critical strengths

This paper has nice results and interesting insights for an important aspect of DP data analysis that's remained stubbornly hard to solve.

S1. New phase transition results for the interplay between sampling error and privacy error.

S2. Novel algorithm for computing DP quantiles with confidence intervals. Critically with shorter--but still valid--confidence intervals than prior methods.

S3. Algorithm for computing DP quantiles with confidence intervals that doesn't require doing numerical integration for convolutions of Gaussian and Laplace and is instead all Gaussian.

Critical weaknesses

The results are interesting and promising, and the main weakness I am concerned about is how practical the algorithms are.

W1. The experimental section lists the improvement in the confidence interval width over prior methods, specifically for the QExp-SC algorithm, but it doesn't list any other empirical considerations like compute cost compared to prior methods. There also weren't any empirical results (accuracy or compute costs) for GOS or LOS, which requires splitting the dataset into 3.

W2. The analysis relies on asymptotic assumptions (like Gaussian sampling error) that generally break when nn is small. Both the QExp-SC and GOS algorithms have different failure modes for small datasets

Questions for authors

Q1. Did you evaluate GOS or LOS empirically? How does it perform in practice, and how does that performance compare to QExp-SC and ExpMech (both in compute cost and interval length/coverage)? At what point (in terms of nn, ϵ\epsilon, any other factors) does GOS outperform QExp-SC in practice given the data splitting that it requires?

1 comment

Thank you for your time and valuable comments. We address the concerns below.

W1. We evaluated the feasible procedures with private pilot/scale estimation and interval construction. The primary design assigns equal thirds of the observations to pilot, nuisance and score estimation; the sensitivity design uses 20/20/60. The results below use the primary equal-third split. For normal data on [−8,8][-8,8], n=4000n=4000, E=0.1E=0.1:

MethodCoverageMean lengthCenter MAE
QExp-SC0.9600.1600.028
GOS0.9540.3990.082
LOS0.9420.2010.042
ExpMech-C1.0000.5880.025

ExpMech-C MAE measures its interval-midpoint error. GOS uses (E,n−2)(E,n^{-2})-DP; the others use pure EE-DP. GOS/LOS use equal-third pilot/nuisance/score blocks.

At normal n=16000n=16000, E=0.1E=0.1, complete-procedure times for QExp-SC/GOS/LOS/ExpMech-C are 2.829/1.571/1.587/2.115 ms (medians of nine batch means). Each procedure includes its own sorting, private preliminary releases, randomness, and interval construction. Public calibration is cached and measured separately. The score implementations sort smaller preliminary blocks and scan the score block; fixed fractions leave both approaches O(nlog⁡n)O(n\log n). GOS and LOS share this computational structure. Convolution critical values depend only on public inputs and are cached per configuration.

W2. At normal n=250n=250, E=0.1E=0.1, on [−8,8][-8,8]:

MethodCoverageMean length
QExp-SC0.6808.212
GOS0.66612.864
LOS0.5876.809
ExpMech-C1.00016.000

QExp-SC's nuisance releases select an endpoint gap in 82.8% of runs, versus 86.9% for the one-step nuisance releases; lower sparsity truncation is active in 21.8% and 26.5%, respectively. The actual privately standardized GOS pivot has 2.5%/97.5% quantiles −83.489/81.985 here, versus the Gaussian reference −1.960/1.960. Thus poor localization, scale estimation, and nonlinear remainders matter before the local approximation becomes accurate. The submitted population-density diagnostic also gives coverage 0.827 at n=2000n=2000, κ0=0.5\kappa_0=0.5 even with the population density in that diagnostic. ExpMech-C maintains its finite-sample coverage guarantee in the displayed small-sample case by returning the full public range.

Q1. The strongest observed advantage is runtime. At standard normal n=128000n=128000, E=0.5E=0.5, the independent extension gives:

MethodCoverageMean lengthMean runtime (ms)
QExp-SC0.9600.0140540.207
GOS0.9620.0247112.453
LOS0.9600.0245712.230
ExpMech-C0.9980.0481427.212

In the large-sample study, GOS is 2.09–3.76 times faster than QExp-SC, with intervals 1.76–2.96 times wider. Standard lognormal n=32000n=32000, E=0.5E=0.5 gives GOS coverage 0.924, and standard normal n=128000n=128000 at E=2/(0.6n)E=2/(0.6\sqrt n) gives 0.936 versus QExp-SC's 0.954.

Sample splitting has a measurable cost. For wide-range lognormal n=16000n=16000 at that critical budget, moving from equal thirds to 20/20/60 lowers GOS coverage 0.952 to 0.891 and LOS coverage 0.943 to 0.742. Less accurate preliminary estimates offset the larger score block. These percentages allocate observations to the three blocks; QExp-SC uses the same sample with a 60/20/20 privacy-budget allocation. Disjoint pilot/nuisance/score blocks each spend at most EE, and the two nuisance releases divide their block budget. The displayed splits have N/n→1/3N/n\to1/3 or 0.60.6; the matched-budget leading-law efficiency result assumes N/n→1N/n\to1 for its efficiency comparison.

The actual public tuning satisfies the stated remainder conditions. At critical privacy with δn=n−2\delta_n=n^{-2}, analytic Gaussian calibration has Nσn→∞\sqrt N\sigma_n\to\infty while σn→0\sigma_n\to0: the standardized theorem applies in this growing noise-ratio regime. QExp's “exact” sampling refers to its randomized mechanism distribution, with asymptotic coverage under the theorem's conditions; its phase parameter uses the center budget ϵ0,nn\epsilon_{0,n}\sqrt n, with ϵ0,n=0.6En\epsilon_{0,n}=0.6E_n here.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

Reviewer_i4bcOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Provides a study between privacy induced noise and sampling noise in the domain of quantile inference. This paper works with rank based exponential mechanism (QExp) and based on the privacy budget characterizes the total error (privacy induced + sampling) distribution into gaussian, gaussian-laplace and laplace. This is because the sampling error is gaussian and privacy induced noise is laplace and depending on the budget, one or the other dominates or we need both to correctly determine the error. Then it proposes confidence intervals using neighboring private quantiles to estimate the local density. It also introduces a one-step correction mechanism that adds Gaussian noise to a bounded quantile score, which they call gaussianization of privacy noise. They provide empirical results corresponding to the theoretical formulations.

Critical strengths

The theorems 3.1 and 3.2 are really useful in the sense that they describe quite precisely how sampling error and privacy induced noise interact with each other depending on the privacy budget. I found the one-step correction mechanism to gaussianize the privacy noise also quite interesting. It provides a better control of the privacy induced errors.The proposed QExp-SC method also provides an useful way to estimate unknown local densities, valid across all three regimes without explicitly identifying the regime.

Critical weaknesses

I feel the experiments do not capture the gaussianization idea too well. It primarily evaluates QExp and QExp-SC. There is no direct finite-sample evaluation of the Gaussian or Laplace one-step estimators against QExp-SC. The baseline results seem to be providing a potentially unfair comparison. It achieves 100% empirical coverage in the reported experiments, making the results vacuous and hence direct interval-length comparisons difficult to interpret. The paper assumes bounds containing the true quantiles are publicly known and the experimental results show substantial sensitivity to this choice. My concern is what would happen if appropriate public bounds are unavailable or overly conservative. Overall I would like to see more detailed experiments on how the Gaussian one-step mechanism offers a meaningful practical advantage.

Questions for authors

See weakness

1 comment

Thank you for your time and valuable comments. We address the concerns below.

W1. We evaluated feasible GOS/LOS procedures, including private pilot and scale estimation, for normal and lognormal medians under fixed and critical privacy budgets and standard/fourfold public ranges. The primary design assigns equal thirds of the observations to pilot, nuisance and score estimation; the sensitivity design uses 20/20/60. The results below use the primary equal-third split.

For normal data on [−8,8][-8,8], n=4000n=4000, E=0.1E=0.1, the nominal 95% intervals give:

MethodCoverageMean lengthCenter MAE
QExp-SC0.9600.1600.028
GOS0.9540.3990.082
LOS0.9420.2010.042
ExpMech-C1.0000.5880.025

ExpMech-C's center is its interval midpoint. GOS uses (E,n−2)(E,n^{-2})-DP and equal-third sample splitting; the other methods use pure EE-DP. The strongest demonstrated GOS benefit is computation with a common Gaussian calibration. At normal n=128000n=128000, E=0.5E=0.5, GOS/QExp-SC take 12.453/40.207 ms, with coverage 0.962/0.960 and width 0.024714/0.014052. In the large-sample study, GOS is 2.09–3.76 times faster and 1.76–2.96 times wider. Standard-range lognormal n=32000n=32000, E=0.5E=0.5 gives GOS coverage 0.924, illustrating the finite-sample calibration cost alongside the runtime benefit.

The following empirical quantiles describe the GOS pivot standardized using its private scale estimate. Standard ranges are [−8,8][-8,8] and [0,16][0,16]; c=2/(0.6n)c=2/(0.6\sqrt n). The standard-normal reference is (−1.960,0,1.960)(-1.960,0,1.960).

LawnnEE2.5% quantileMedian97.5% quantile
Normal2500.1-83.4890.00481.985
Normal40000.1-1.958-0.0081.881
Normal16000cc-1.9770.0022.050
Lognormal2500.1-4.4691.656198.387
Lognormal40000.1-1.9670.0131.990
Lognormal16000cc-1.9300.0061.921

The small-sample departures are substantial; the larger-sample quantiles are much closer, with remaining tail differences. The theorem describes the asymptotic standardized law under the stated regularity and preliminary-estimation conditions.

For the endpoint comparison, the submitted endpoint experiment gives width 1.102 and 100% observed coverage on a range of length 16. The full-range fallback occurs at n=250n=250, E=0.1E=0.1. ExpMech-C is our explicitly conservative calibration of the widened rank-exponential construction of Drechsler et al. (2022). Its finite-sample guarantee is coverage at least nominal; QExp-SC targets asymptotically exact coverage at each regular distribution. Coverage and width describe the practical consequences of these two calibration objectives.

We evaluated our original and tighter conservative calibrations at public widening ratios θ/R∈10−2,10−3,10−4,10−5\theta/R\in\\{10^{-2},10^{-3},10^{-4},10^{-5}\\}, with R=B−AR=B-A. At normal n=32000n=32000, E=0.5E=0.5, θ/R=10−4\theta/R=10^{-4}, original/tightened ExpMech-C give coverage/width 0.997/0.0437 and 0.997/0.0427, versus QExp-SC's 0.957/0.0286. At wide-range normal n=4000n=4000, E=cE=c, QExp-SC gives 0.983/2.4260, while all four tightened endpoint choices cover 1.000 with widths 2.1056, 1.1952, 1.3514, and 1.7244. The wide lognormal configuration has the same reversal. Widening affects both endpoint resolution and conservative rank calibration.

The public interval must contain the population quantile; this permits unbounded observation distributions. For overly conservative bounds, the submitted normal n=16000n=16000, E=cE=c comparison gives standard/fourfold widths 0.134/0.137 and coverages 0.959/0.953. A public budget reallocation also helps: on [−32,32][-32,32], n=4000n=4000, changing center/upper/lower percentages from 60/20/20 to 40/30/30 reduces width 2.419 to 0.912 and side-endpoint frequency 51.6% to 9.4%, with coverage 0.980/0.967 but center MAE 0.043/0.062. This allocation improves interval width while increasing center error. When an appropriate range is unavailable publicly, private localization requires additional privacy/sample costs and failure control. The current guarantee uses a fixed public interval containing the target.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.