Sequentially Auditing Differential Privacy
Tomás González, Mateo Dulce-Rubio, Aaditya Ramdas, Mónica Ribero · 2025
Read Sequentially Auditing Differential Privacy by Tomás González, Mateo Dulce-Rubio, Aaditya Ramdas, Mónica Ribero (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07055.txt.
Introduction
Tomás González and 3 co-authors propose sequentially auditing differential privacy in a 2025 paper. Differential privacy is a formal guarantee that a mechanism's output reveals little about any single. Auditing whether a black-box mechanism actually satisfies that guarantee is major, but earlier batch auditing methods are limited by fixed sample size.
Their practical sequential test processes streams of a mechanism's outputs, providing anytime-valid inference while controlling type one error. Experiments show the test detects violations with sample sizes orders of magnitude smaller than current methods, reducing the number from tens of thousands to a few hundred examples across diverse real-life mechanisms. Notably, it identifies privacy violations in a differentially private training algorithm in under one training run, unlike prior methods needing full model training.
Catalog record
| CREATOR | Tomás González, Mateo Dulce-Rubio, Aaditya Ramdas, Mónica Ribero |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-07055
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sequentially Auditing Differential Privacy Tomás González, Mateo Dulce-Rubio, Aaditya Ramdas, Mónica Ribero 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. 1 Introduction Auditing privacy guarantees of algorithms that process sensitive data, prevalent in domains like finance, healthcare, and users’ behavior on the web, is crucial for building and deploying reliable and trustworthy software. While rigorous privacy protections like Differential Privacy (DP) dwork2006 have been adopted by industry Apple ; GoogleDP ; LinkedInEng and government agencies USCensusBureau , the promised theoretical guarantees rely on both correct algorithmic design (e.g., avoiding flaws or errors in mathematical proofs, like those demonstrated with the Sparse Vector Technique LSL17 ) and correct implementation, where subtle bugs can compromise privacy (e.g., missing constants, incorrect sampling, or fixed seeds). Furthermore, theoretical privacy parameters \varepsilon and \delta often represent worst-case upper bounds, motivating the need for empirical privacy auditing to assess practical privacy leakage and gain intuition about algorithms’ vulnerabilities 2023tightauditingDPML . Auditing privacy can be framed as a statistical hypothesis test: distinguishing the null hypothesis H_{0} : “the algorithm satisfies a claimed privacy guarantee”, from the alternative H_{1} : “the algorithm violates the claimed privacy guarantee”. Current approaches to this testing problem generally fall into two categories, each with significant drawbacks. First, parametric tests can achieve high statistical power but rely on strong, often unverifiable, assumptions about the specific workings and output distribution of the mechanism or the specific flaw 2023tightauditingDPML ; DMNS06 . Second, black-box tests, where the auditor observes only the mechanism’s outputs without knowledge of its internal functioning, make fewer assumptions but requires an unknown and typically large number of samples to draw statistically meaningful conclusions dpsniper ; 2024DPAuditorium . This makes them impractical for auditing complex, resource-intensive algorithms such as differentially private stochastic gradient descent (DP-SGD), where obtaining even one sample often requires significant computation (e.g., backpropagation through millions of model parameters). In this paper, we propose a new framework for approximate DP auditing that leverages recent advances in sequential hypothesis testing to overcome these limitations. Our approach uses e-values 2024e-vals-book , non-negative random variables that (when multiplied) sequentially accumulate evidence against the null hypothesis. Under the null H_{0} , the expectation of an e-value is bounded by 1; under the alternative H_{1} , 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 \alpha is reached. Notably, sequential tests automatically adapt to the unknown sample complexity of the problem, eliminating the need to fix the test’s sample size a priori and avoiding unnecessary computation. Our specific test statistics are built upon the Maximum Mean Discrepancy (MMD) gretton2012kernel , a powerful kernel-based metric for comparing probability distributions. MMD is particularly well-suited for the two-sample tests emerging in privacy auditing, as bounds on MMD can be easily translated to approximate DP parameters 2024DPAuditorium . Further, MMD is highly flexible. It can incorporate prior knowledge in white-box settings —such as access to intermediate gradients or the noise distribution family— or, as our experiments show, operate effectively in a black-box manner. The main contributions of this work are summarized as follows: • We introduce a new general MMD-based one-sided sequential testing framework. As a key application, we instantiate this framework for auditing approximate DP (see Section 3 ). Our method enables anytime valid inference while controlling Type I error, eliminating the need for pre-defined test sample sizes, and ensuring a bounded expected stopping time under the alternative. We establish these theoretical guarantees in Theorems 3.2 and 3.3 . • We present a new connection between MMD and Hockey-Stick divergence in Theorem 3.1 that allows for the translation of MMD-based hypothesis tests to approximate DP auditing tests. The connection presented is tighter than previous bounds, increasing test power. Our experiments show that previous tests requiring hundreds of thousands of samples while still failing to reject, now reject with under a thousand samples. • We validate our methods on common DP mechanisms with Gaussian and Laplace noise. We further demonstrate efficacy on auditing benchmark algorithms ( 2024DPAuditorium ; dpsniper ) and provide results for the challenging case of DP-SGD abadi2016deep ; song2013stochastic , showcasing the practical benefits of early failure detection enabled by our sequential approach. Related work. At the core of approximate DP auditing is the estimation of the effective privacy loss from samples of the mechanism. There is substantial prior work on this, primarily situated within the batch setting, where a fixed number of samples are drawn GM18 ; DJT13 ; DGKK22 ; StatDP ; dpsniper ; niu2022dp ; lokna2023group ; lu2022eureka . Also in the batch setting, a significant body of work specializes on auditing machine learning models, particularly those trained with DP-SGD. This includes membership inference attacks (MIA) JE19 ; ROF21 ; CYZF20 ; jagielski2020auditing ; 2023tightauditingDPML and data reconstruction attacks Guo22 ; Balle22 ; mahloujifar24auditingFDP . Our approach relies on sequential testing with kernel methods, specifically the Maximum Mean Discrepancy (MMD) gretton2012kernel , to construct test statistics. Prior work on privacy auditing has also used kernel methods, such as estimating regularized kernel Rényi divergence DM22 , but often requires strong assumptions (e.g., knowledge of covariance matrices) impractical in black-box settings or for mechanisms beyond Gaussian or Laplace. To the best of our knowledge, applying modern sequential hypothesis testing techniques, particularly those based on e-values or test supermartingales testingBetting ; ramdas2020admissible , to the general problem of black-box DP auditing is novel. However, sequential testing by betting ideas have been successfully applied for auditing in other settings like elections waudby2021rilacs , finance shekhar2023risk , fairness chugg2023auditing , and language models richter2024auditing . The most closely related work is richter2024auditing as they also propose a one-sided test, although for detecting distribution shifts in language models. While their setting is similar, their testing procedure differs from ours in key ways, allowing us to establish results they do not—such as bounds on the expected number of samples until rejection under the alternative. We elaborate on these differences in Section 3.2 . In Appendix H we discuss in detail more references and how they compare to our work. 2 Preliminaries Notation. Throughout the paper we let \mathcal{D}\subseteq\cup_{d\in\mathbb{N}}\mathbb{R}^{p\times d} be a set of datasets; datasets D\in\mathcal{D} have a finite but arbitrary number of p -dimensional records. We denote by \mathcal{A}:\mathcal{D}\mapsto\mathcal{X} randomized mechanisms that map datasets to a range \mathcal{X} . We say that S,S^{\prime}\in\mathcal{D} are neighboring datasets (denoted by S\sim S^{\prime} ) if they differ by at most one data point. While our framework is agnostic to the definition of “neighboring”, for simplicity (and in our experiments) we assume S\sim S^{\prime} in the add/remove