- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The goal of privacy auditing is to estimate the actual information leaked by a model. Ideally, this leakage would match the theoretical privacy guarantees. The authors study privacy auditing for differentially private (DP) machine learning, focusing on efficient one-run methods for mechanisms (specifically, DP-SGD). Prior one-run approaches threshold training examples (i.e., ``canaries'') into binary membership guesses, which discards useful information. The authors show that, in the white-box DP-SGD setting, canary-aligned signals naturally form a sequence of random variables whose normalized sum is asymptotically Gaussian. Leveraging this distributional perspective, they then develop an auditing framework that leads to tighter privacy lower bounds from a single training run.
The authors of the paper propose a scalable privacy auditing method for training algorithms that add Gaussian noise, with a main focus on DP-SGD and an application to DP-FTRL. Unlike existing scalable auditing methods, the proposed approach uses the distributional properties of the Gaussian noise added during training. The authors model the distribution of the audit scores under idealized assumptions and construct a confidence region for the noise parameters for privacy auditing.
Critical strengths
(1) The method shows high practical utility in auditing DP-SGD, as shown in the experiments on the CIFAR-10 dataset.
(2) The paper provides a nice theoretical analysis for the proposed method, including CLT error analysis with the justification of the Gaussian approximation. Specifically, they show, under the idealized model, the CLT approximation error is dominated by the optimization error. While the paper relies on the ideal modeling assumption, the authors provide a justifying experiment.
Critical weaknesses
(1) The finite-sample confidence guarantee does not yet cover the implemented procedure under Model 1: Algorithm 1 is presented as an auditor under Model 1, but the finite- present score in that model is a binomial–Gaussian mixture. Proposition 3 assumes Gaussian score populations and a confidence region with the required coverage. The implementation instead uses an asymptotically justified bootstrap ellipsoid. Theorem 1 and Corollary 2 retain an (unquantified) remainder and the concrete numerical calculation on page 20 uses only the leading term. Neither approximation error nor background-model error is propagated into the hockey-stick divergence and confidence guarantee.
Consider the observation mechanism specified by Model 1 with $T=2500,\quad q=10^{-9},\quad C=1,\quad \sigma=10^{-6},\quad \delta=10^{-5}.$ Coupling the absent and present observation sequences with identical randomness shows that they differ only if the canary is sampled. Hence $\operatorname{TV}(P_0,P_1) \le 1-(1-q)^T \approx 2.5\times10^{-6}<\delta,$ so this observation mechanism satisfies -DP. Its moment-matched Gaussian pair instead has means and , and variances and . The Gaussian pair’s hockey-stick divergence at is approximately 0.925. With sufficiently many independent canaries, parameter-estimation uncertainty can shrink around this incorrect surrogate without repairing the approximation error.
(2) The DP-FTRL transcript and recovery argument are not specified consistently: Section 4.3 describes access to , while Appendix F claims that can be recovered from decoded releases because is invertible. For the full binary-tree encoder described there, has rows and the prefix decoder has rows, so cannot be invertible. Observing all noisy tree nodes can justify the proposed statistic, but that is different from observing only decoded prefix/model updates. This affects the scope of the extension and whether the baseline comparison grants equivalent access.
Questions for authors
(1) Auditor calibration: What quantitative guarantee applies to Algorithm 1 with finite , the implemented bootstrap confidence region, and Gaussian approximation error? Can an explicit correction be incorporated into the returned bound? Repeated simulations from the inexpensive exact Model 1 generator could lead to empirical coverage and false-rejection rates over a range of sampling and noise regimes.
(2) Applicability conditions: What checkable restrictions exclude sparse-sampling/small-noise cases such as the example above? How is any nonzero background contribution bounded or included in the guarantee, rather than assessed only through a Q–Q plot?
(3) DP-FTRL access: Does the auditor observe all noisy tree-node releases or only decoded prefix/model updates? Please specify the dimensions of and , justify any claimed recovery, and clarify whether the comparator receives exactly the same transcript.
We thank the reviewer for the feedback and for recognizing the practical utility and theoretical contributions of our method. We have addressed the main comment by incorporating an explicit finite-T Gaussian approximation correction into Algorithm 1 (see also response to Rev nbcR). Importantly, our updated experiments confirm that the proposed auditor continues to outperform existing one-run methods, retaining its advantages in both auditing tightness and detecting privacy violations. We elaborate on these revisions and address other points below.
Q1. Finite-T Correction and Auditor Calibration
We have revised Algorithm 1 to explicitly incorporate the finite-T Gaussian approximation error into the returned bound (Section 3.1, Theorem 1, and Appendix E of the updated manuscript).
Specifically, the correction uses an explicit, non-asymptotic Kolmogorov-distance bound between the true binomial–Gaussian mixture and its Gaussian approximation under Model 1. Unlike our previous analysis, this bound holds for finite T without an unquantified remainder. Since the absent-canary distribution is exactly Gaussian and the optimal distinguishing region for two one-dimensional Gaussians has at most two boundary points, the newly derived Kolmogorov-distance bound implies that the true directional hockey-stick divergence is at least the Gaussian divergence minus r=2ηT. Accordingly, Algorithm 1 now evaluates the privacy lower bound at δ+r instead of δ, where r is chosen uniformly over the applicable parameter region. Consequently, under Model 1, the revised auditor yields an asymptotically valid 95% privacy lower confidence bound, while explicitly controlling the Gaussian approximation error for finite T.
We rerun the experiments (updated Figure 1 and Table 1) using the revised auditor. The experiments show that our method continues to outperform previous one-run auditors, achieving an empirical privacy lower bound of 6.234 at the theoretical ϵ=8, compared with 4.697 for Mahloujifar et al. and 3.330 for Steinke et al. Furthermore, our revised auditor still detects all three tested DP-SGD implementation errors. These results still support our central message: exploiting the distributional information in real-valued canary scores, rather than reducing them to binary membership guesses, yields substantially tighter privacy lower bounds.
Q1 (Cont’d) : Empirical Coverage and False-Rejection Rates
We have provided the empirical evidence the reviewer requested confirming our original results are correct: Across 500 exact Model 1 simulations at our ε = 8 experimental setting, the nominal 95% bootstrap ellipsoid covered the true parameters in 474 runs (94.8%, 95% Wilson CI 92.49%–96.43%). At the rounded-up Model 1 score threshold of ε = 7.517485, the corrected auditor falsely rejected in 0 of 500 runs (95% Wilson CI 0%–0.76%).
Q2. Applicability conditions The revised auditor addresses the reviewer's concern regarding sparse-sampling and small-noise regimes. Specifically, the correction r is computed uniformly over a DP-SGD parameter region (Section 3.1 and Appendix E). If this region is sufficiently broad to include such extreme configurations, the correction can become large enough that the revised auditor returns a vacuous privacy lower bound. In particular, for the reviewer's counterexample, the correction renders the lower bound vacuous, preventing an unjustified privacy violation claim. Conversely, for more realistic configurations, the correction remains small, as quantified in Appendix E, Table 2, allowing the auditor to retain meaningful privacy lower bounds. The theoretical guarantee is established under Model 1, which assumes exact background suppression. We provide empirical evidence supporting this assumption in the evaluated DP-SGD settings through Q–Q plots.
Q3. DP-FTRL and DP-MF-FTRL: Our MF mechanism factors A=BC, computes Cx+Z with i.i.d. N(0,σ2) entries in Z, releases g=By, and decodes By=Ax+BZ. The auditor observes the noisy prefix-sums g.
What are the dimensions of Encoder/Decoder?
Our streaming DP-FTRL implementation generates one noisy dyadic block per round, so its encoder C and decoder B are both T×T. The noisy node created in round n is yn=gn−gn−ℓn, where ℓn is the largest power of two dividing n and g0=0. In DP-MF-FTRL, the square decoder B is invertible, so the auditor can recover y by solving for By=g. The per-canary statistic of Andrew et al. is the round-wise max cosine s̃ᵢ = max over t ∈ [0, T) of ⟨e[cᵢ], gₜ⟩ / ‖gₜ‖₂, where gₜ is the same g described above. Given the new page limit of 10, we have added a Section 4 to introduce the mechanisms, the auditors view on the canary scores and the privacy relevant score distribution before the experimental section and added implementation details in Section 5.3.