An (ε, δ)-Differential Privacy Analysis of Adaptive Noise Calibration via Hockey-Stick Divergence
TL;DR
A two-stage adaptive mechanism that first obtains a privacy-preserving estimate of how spread out the data are, using the interquartile range (IQR) as the measure of dispersion, and then uses that estimate to shrink the noise added to the query answer whenever the data are concentrated.
Abstract
Standard differentially private mechanisms calibrate noise to the worst-case sensitivity of a query, which wastes utility whenever the actual data are well concentrated. This paper studies a two-stage adaptive mechanism that first obtains a privacy-preserving estimate of how spread out the data are, using the interquartile range (IQR) as the measure of dispersion, and then uses that estimate to shrink the noise added to the query answer whenever the data are concentrated. A tunable safety-floor parameter prevents the noise from being reduced below a prescribed minimum, so that the mechanism cannot become arbitrarily leaky even if the private dispersion estimate is itself inaccurate.The paper makes four contributions, all established with complete proofs rather than heuristic argument. First, we derive the exact (tight) failure probability of the second stage using the hockey-stick divergence framework, and we show that a shortcut formula used in informal treatments of similar mechanisms systematically understates this failure probability and therefore does not constitute a valid privacy guarantee. Second, we prove a new “monotone-pinching” lemma showing that, under a mild regularity condition on how the data are spread across their range, the private IQR estimate obtained via the Exponential Mechanism cannot be off by more than one rank position, which yields an explicit and tight accuracy guarantee for the estimate. Third, we prove an adaptive composition theorem showing that combining the two stages incurs an unavoidable multiplicative penalty in the overall failure probability, and we give a precise, checkable condition under which the adaptive mechanism nonetheless achieves strictly lower estimation variance than the standard (non-adaptive) Laplace mechanism operating at the same total privacy budget. Fourth, we solve the resulting budget-allocation problem in closed form, characterising how the total privacy budget should be split between the two stages to minimise variance, together with an explicit condition under which a prescribed accuracy target is achievable at a given sample size. All theoretical bounds are illustrated numerically, and the accuracy guarantee for the private IQR estimate is validated against Monte Carlo simulation.