$f$-Differential Privacy Auditing without Distributional Assumptions

Empirical auditing of differential privacy guarantees commonly reduces a mechanism's output to a one-dimensional score and sweeps a threshold to infer whether a sample was used in training. Such a sweep is able to recover the full trade-off curve if and only if the score distributions have a monotone likelihood ratio. This is a property of the chosen score, not of the mechanism, and arbitrary post-processing need not preserve it. Moreover, fitting an entire parametric $f$-DP curve to one test point can produce invalid privacy lower bounds. Due to these reasons, most of the existing auditing methods may either lead to pessimistic lower bounds or give false lower bounds. We propose an auditing method that assumes neither monotonicity nor smoothness nor a parametric trade-off family, is able to accurately approximate the trade-off function and comes with high-confidence guarantees. A selection sample may be used arbitrarily to propose likelihood-ratio level sets and independent evaluation samples certify their error rates, and convexification gives a high-confidence upper bound on the score trade-off function.