Interpreting the Error of Differentially Private Median Queries through Randomization Intervals
2026-04-08 • Cryptography and Security
Cryptography and SecurityDatabases
AI summaryⓘ
The authors explain that when adding privacy-protecting noise to statistics like the median, it can be hard to tell how much error was introduced. They study a tool called a Randomization Interval (RI), which shows the range of possible errors due to this noise. Previous methods lowered the quality of the median itself to get a better RI, but the authors propose PostRI, which creates the RI after estimating the median. This approach keeps the median more accurate while still providing a reliable error bound.
differential privacyrandomization intervalmedian estimationconfidence intervalnoise distributionutilitypost-processingstatistical error
Authors
Thomas Humphries, Tim Li, Shufan Zhang, Karl Knopf, Xi He
Abstract
It can be difficult for practitioners to interpret the quality of differentially private (DP) statistics due to the added noise. One method to help analysts understand the amount of error introduced by DP is to return a Randomization Interval (RI), along with the statistic. A RI is a type of confidence interval that bounds the error introduced by DP. For queries where the noise distribution depends on the input, such as the median, prior work degrades the quality of the median itself to obtain a high-quality RI. In this work, we propose PostRI, a solution to compute a RI after the median has been estimated. PostRI enables a median estimation with 14%-850% higher utility than related work, while maintaining a narrow RI.