Sequentially Auditing Differential Privacy

Tomás González, Mateo Dulce Rubio, Aaditya Ramdas, Mónica Ribero

We propose a new framework for approximate DP auditing using e-values, non-negative random variables that (when multiplied) sequentially accumulate evidence against the null hypothesis. Under the null H0, the expectation of an e-value is bounded by 1; under the alternative H1, well-designed (products of) e-values can grow exponentially fast, allowing for early stopping and efficient detection of privacy violations. This sequential methodology allows testing to proceed adaptively: samples are collected and evaluated iteratively, and the test stops as soon as a significance level α is reached

Abstract

We propose a practical sequential test for auditing differential privacy guarantees of black-box mechanisms. The test processes streams of mechanisms’ outputs providing anytime-valid inference while controlling Type I error, overcoming the fixed sample size limitation of previous batch auditing methods. Experiments show this test detects violations with sample sizes that are orders of magnitude smaller than existing methods, reducing this number from 50K to a few hundred examples, across diverse realistic mechanisms. Notably, it identifies DP-SGD privacy violations in under one training run, unlike prior methods needing full model training.

Reference

Sequentially Auditing Differential Privacy
Tomás González, Mateo Dulce Rubio, Aaditya Ramdas, Mónica Ribero
Neural Information Processing Systems (NeurIPS,). 2025.
PDF