Efficient Public Verification of Private ML via Regularization
Zoë Ruha Bell, Anvith Thudi, Olive Franzese-McLaughlin, Nicolas Papernot, Shafi Goldwasser · 2025
Read Efficient Public Verification of Private ML via Regularization by Zoë Ruha Bell, Anvith Thudi, Olive Franzese-McLaughlin, Nicolas Papernot, Shafi Goldwasser (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-2512-04008.txt.
Introduction
Differential privacy promises people in a training dataset that a released model cannot identify them, but the public must take that promise on faith. Zoë Ruha Bell and colleagues design a private learning algorithm whose guarantees can be checked cheaply, in a 2025 preprint. Until now, verification cost about as much computing as training itself.
The team works on differentially private stochastic convex optimisation, where the best trade-offs are known. Their method privately minimises a sequence of regularised objectives and leans only on the standard composition bound for privacy accounting. That structure keeps utility near optimal while making the guarantee auditable with far less computation than training. On large datasets the saving is significant. The authors call it the first algorithm of its kind whose verification scales better than training, a property that could make privacy claims publicly testable.
Catalog record
| CREATOR | Zoë Ruha Bell, Anvith Thudi, Olive Franzese-McLaughlin, Nicolas Papernot, Shafi Goldwasser |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-04008
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Public Verification of Private ML via Regularization Zoë Ruha Bell, Anvith Thudi, Olive Franzese-McLaughlin, Nicolas Papernot, Shafi Goldwasser Abstract Training with differential privacy (DP) provides a guarantee to members in a dataset that they cannot be identified by users of the released model. However, those data providers, and, in general, the public, lack methods to efficiently verify that models trained on their data satisfy DP guarantees. The amount of compute needed to verify DP guarantees for current algorithms scales with the amount of compute required to train the model. In this paper we design the first DP algorithm with near optimal privacy-utility trade-offs but whose DP guarantees can be verified cheaper than training. We focus on DP stochastic convex optimization (DP-SCO), where optimal privacy-utility trade-offs are known. Here we show we can obtain tight privacy-utility trade-offs by privately minimizing a series of regularized objectives and only using the standard DP composition bound. Crucially, this method can be verified with much less compute than training. This leads to the first known DP-SCO algorithm with near optimal privacy-utility whose DP verification scales better than training cost, significantly reducing verification costs on large datasets. 1 Introduction Machine learning models are known to reveal sensitive information in their training dataset ( Shokri et al. 2017 ; Carlini et al. 2021 ) . Differential privacy ( Dwork et al. 2006 ) (DP) is the standard framework to mitigate leakage of sensitive information, providing a guarantee that users of the model cannot learn what datapoints were in the dataset. Nevertheless, data providers, e.g., a member of the public, must still trust that the model trainer used a DP training algorithm to protect their privacy. In this paper we investigate how a member of the public can efficiently establish that a model was trained with DP guarantees. A common framework is “black-box” auditing ( Jagielski et al. 2020 ; Nasr et al. 2021 ; Steinke et al. 2024 ) , where an auditor queries the model trainer with different datasets and inspects the returned models. However, it is known that verifying tight DP guarantees with such black-box approaches can be statistically hard ( Gilbert & McMillan 2018 ; Haghifam et al. 2025 ) . We first show that black-box auditing cannot verify a training algorithm satisfies any DP guarantees. We prove this by showing a model trainer can always plant an undetectable backdoor that can leak the dataset to certain entities. Our backdoor follows the approach of ( Goldwasser et al. 2022 ) to use digital signatures, i.e., a function that’s hard to reproduce without access to a secret input parameter, as the trigger to activate the backdoor: by the definition of digital signatures this is computationally undetectable to a “black-box” auditor. Upon activation our backdoor then outputs the training dataset instead of the normal training algorithm’s outputs. This means an algorithm can have no DP guarantees despite passing any “black-box” audit. Theorem 1.1 (Undetectable DP Backdoor (Informal)) . Under the assumption that digital signatures exist, for any (\epsilon,\delta) -DP algorithm 1 1 1 See Definition 1 . T there exists an algorithm T^{\prime} which is computationally indistinguishable from T when queried post-training, but reveals the dataset to privileged entities who know the backdoor (and so does not satisfy any DP guarantee). Given the insufficiency of only inspecting the released model, we investigate how to efficiently interact with the model trainer to verify their training algorithm satisfies the assumptions for a proof of DP ( Shamsabadi et al. 2024 ; Bell et al. 2024 ) . For example, in deep learning we could verify the model trainer clipped the per-example gradients and added noise for each training step ( Abadi et al. 2016 ) . We will require the interaction during the verification protocol to preserve the confidentiality of the dataset and model ( Bell et al. 2024 ) , removing the need to trust some third-party “verifier” and hence making the algorithm publicly verifiable. Common proofs of “tight” DP guarantees require hard-to-verify constraints ( Shamsabadi et al. 2024 ) . To illustrate this, consider training with mini-batch updates—a wide-spread privacy amplification technique ( Kasiviswanathan et al. 2011 ; Beimel et al. 2014 ; Abadi et al. 2016 ; Feldman et al. 2020 ) . To verify the mini-batch update was done correctly one would need to determine that the data-points were sampled randomly, and that the final gradient is the gradient for that mini-batch: checking this requires a-priori knowing what the correct gradient is, meaning the verifier must also compute all the training steps. In this paper we initiate a study of proofs of DP guarantees that can be publicly verified cheaper than training (efficient to verify) . Specifically, we focus on DP stochastic convex optimization (DP-SCO), where the optimal privacy-utility trade-off ( Feldman et al. 2020 ) . Importantly for us, when training on a dataset of size n and inputs of dimension d , these optimal DP training algorithms currently require at least \tilde{O}(\min(n^{1.5},n^{2}/\sqrt{d})) gradients and \Omega(dn) Gaussian random variables (RVs) ( Asi et al. 2021 ) or O(n^{2}) gradients and d\cdot\lceil\log_{2}(n)\rceil Gaussian RVs during training ( Feldman et al. 2020 ) 2 2 2 In low-dimensions, better rates can be achieved ( Carmon et al. 2023 ) . . Our main result of this paper is showing there is a near-optimal DP-SCO algorithm whose optimal DP guarantees can be verified cheaper than the fastest known training algorithm, needing only n gradients and d\cdot\log_{2}(n) Gaussian RVs for verification. Theorem 1.2 (Faster Convex DP Certification (Informal)) . There exists an (\epsilon,\delta) -DP SCO algorithm, with near-optimal privacy-utility rates, whose certification requires verifying only n gradients and d\cdot\lceil\log_{2}(n)\rceil Gaussian RVs, where n is the dataset size and d is the dimension parameter. To show this, we made novel connections between several privacy techniques and efficient verification, and how together they can allow for checking fewer gradients to deduce near optimal privacy guarantees. We first note that regularization provides stability which can then allow for better privacy, which is the basis of the phased ERM algorithm ( Feldman et al. 2020 ) . In particular, this algorithm requires finding a series of approximate minimizers to a series of increasingly regularized objectives and then adding noise. The consequence of this for verification is that we can verify a solution is an approximate minimizer faster than it takes to find the minimizer (training cost). However the phased ERM requires parallel composition ( Feldman et al. 2020 ; McSherry 2009 ) to derive its tight privacy guarantees which is hard to verify; verifying parallel composition requires showing the approximate minimizer is only computed using a subset of the training dataset which is hard to check efficiently. We hence modified the phased ERM algorithm by changing the conditions on the approximate minimizers. With this modification we showed that we could still derive near optimal privacy-utility with only standard composition, which is much easier to verify. To investigate what parts of verification dominate runtime in practice, we implemented our DP verification on binary logistic regression using the EMP-toolkit ( Wang et al. 2016 ) 3 3 3 Due to how we use the EMP-toolkit, our implementation does not provide public verifiability.