Differentially Private Quantiles with Smaller Error

In the approximate quantiles problem, the goal is to output m quantile estimates, the ranks of which are as close as possible to m given quantiles 0 ≤ q1 ≤dots ≤ qm ≤ 1. We present a mechanism for approximate quantiles that satisfies varepsilon-differential privacy for a dataset of n real numbers where the ratio between the distance between the closest pair of points and the size of the domain is bounded by psi. As long as the minimum gap between quantiles is sufficiently large, |qi-qi-1|≥ Omegaleft(fracmlog(m)log(psi)nvarepsilonright) for all i, the maximum rank error of our mechanism is Oleft(fraclog(psi) + log2(m)varepsilonright) with high probability. Previously, the best known algorithm under pure DP was due to Kaplan, Schnapp, and Stemmer~(ICML '22), who achieved a bound of Oleft(fraclog(psi)log2(m) + log3(m)varepsilonright). Our improvement stems from the use of continual counting techniques which allows the quantiles to be randomized in a correlated manner. We also present an (varepsilon,δ)-differentially private mechanism that relaxes the gap assumption without affecting the error bound, improving on existing methods when δ is sufficiently close to zero. We provide experimental evaluation which confirms that our mechanism performs favorably compared to prior work in practice, in particular when the number of quantiles m is large.