Tight Auditing of Differentially Private Machine Learning

1. 01What problem does this paper attempt to solve?

   Improving DP-SGD privacy auditing: obtaining a tight ε lower bound on natural datasets and reducing the required number of training runs to two.

   Core question: How can empirical privacy auditing of DP-SGD be tight against the theoretical upper bound even on natural (non-adversarially constructed) datasets, while requiring only very few training runs.

   • Background and motivation: The authors point out that the theoretical analysis of DP-SGD is conjectured to be overly conservative, while Nasr et al. [21] proved the analysis tight only on the worst-case dataset (D=∅); meanwhile, existing audits require thousands to millions of training runs, which is too costly for large models. The paper poses two questions: Q1, whether the analysis of DP-SGD is tight only for the worst-case dataset; Q2, whether privacy leakage can be tightly estimated with a small number of training runs.
   • Shortcomings of existing methods: The authors state that existing audits [12, 17, 21, 30] are "universal" and do not exploit information about the privacy mechanism itself; (ε,δ)-DP concerns rare events of probability O(δ), which require a large number of observations to see once, leading to loose lower bounds or excessive cost.
   • Core observation: Different mechanisms with the same (ε,δ) guarantee have different trade-off functions (Figure 1); auditing with f-DP matched to the mechanism (GDP for the Gaussian mechanism) allows inferring rare events from common events, avoiding the looseness of the (ε,δ) conversion.
   • Contributions of the paper: An auditing scheme based on f-DP, which the authors state yields tight estimates with only two training runs; it is used to detect DP-SGD implementation bugs and to analyze the effect of hyperparameters and model selection on privacy leakage.
   • Threat models (Section 3, in decreasing order of attack capability):
     • White-box access with gradient canaries: The adversary can see the privatized gradients and model parameters at each step, and can insert arbitrary canary gradients at each step with probability q; this is the standard threat model of DP theoretical analysis.
     • White-box access with input-space canaries: The adversary can see intermediate updates but can only insert arbitrary training samples (canary samples), and cannot directly specify gradients; the authors state this matches the federated learning setting.
     • Black-box access: The adversary can only insert a sample at the start of training and observe the model after training ends; the authors state this is the most restricted for the attacker but the most realistic from a practical perspective, and is not the setting DP usually analyzes.
     • Goal: Design D and z (D′=D∪{z}) to make distinguishing M(D) from M(D′) easiest; in the paper, the terms trainer, auditor, and attacker are used interchangeably.

   Collapse this answer

2. 02What related research exists?

   Related work falls into three categories: DP and f-DP theory, DP-SGD composition analysis, and existing audit methods (CP, Bayesian, Katz-log).

   Differential privacy and f-DP theory

   • Dwork et al. [10]—proposed (ε,δ)-DP; Abadi et al. [2]—proposed DP-SGD (gradient clipping plus Gaussian noise).
   • Dong et al. [9]—proposed f-DP and Gaussian DP (GDP), gave the hypothesis testing interpretation and the conversion from µ-GDP to (ε,δ)-DP (Corollary 5); this paper's audit framework is built directly on f-DP.
   • Kairouz et al. [14], Wasserman and Zhou [26]—hypothesis testing interpretation of DP and the privacy region (Equation 8).

   Composition analysis of DP-SGD

   • Mironov [19] (Rényi DP), Koskela et al. [16] (Privacy Loss Distribution, PLD)—gave DP-SGD accounting methods tighter than naive composition; this paper uses PLD to approximate the trade-off function of the subsampled Gaussian mechanism.
   • Altschuler and Talwar [3], Ye and Shokri [27]—privacy leakage saturates with convergence on convex models; the authors empirically test in Appendix D.1 whether this phenomenon holds on deep models.

   DP audit methods (the direct comparison targets of this paper)

   • Nasr et al. [21]—derive an ε lower bound from the attack's FPR/FNR using Clopper-Pearson confidence intervals (Equation 9), proving tightness on the worst-case dataset D=∅; the paper points out that its limitation is tightness only on the worst-case dataset and the need for thousands of training runs.
   • Zanella-Béguelin et al. [30]—compute a credible interval for ε using a Bayesian method (with an uninformative prior on (α,β)), reducing the number of training runs needed; the paper points out that its comparison with Clopper-Pearson has statistical-caliber issues in its approximation, but acknowledges its practicality and extends it to f-DP.
   • Lu et al. [17]—audit using Katz-log confidence intervals, set δ=0, and propose the conjecture that "empirical privacy leakage depends on the dataset"; the paper explicitly refutes this conjecture, stating that its observations mainly come from using attacks weaker than the DP threat model allows.
   • Jagielski et al. [12]—early DP-SGD audit work; Tramèr et al. [24, 25]—used black-box auditing to debug DP implementations, finding the implementation error of Stevens et al. [23]; Maddock et al. [18]—canary construction under federated learning, with an idea similar to this paper's step-by-step to end-to-end conversion.

   Baselines and benchmarks: the comparison baselines are the four lower-bound methods above—(ε,δ)-DP (CP) [12, 21], (ε,δ)-DP (ZB) [30], ε-DP (Katz) [17], together with this paper's f-DP (CP) and f-DP (ZB); the experimental datasets are CIFAR-10, Purchase, and a randomly initialized dataset.

   Positioning: the authors state that this paper's distinction is "opening the black box" and auditing the specific mechanism of DP-SGD (Gaussian/GDP), thereby simultaneously addressing the two issues of tightness on natural datasets and the number of training runs.

   Collapse this answer

3. 03How does the paper address this problem?

   Audit using f-DP matched to the mechanism instead of (ε,δ)-DP: use GDP for the Gaussian mechanism, PLD approximation for subsampled composition, and then convert attack error into an ε lower bound.

   Overall approach: auditing as hypothesis testing—distinguishing whether the model was trained on D or D′=D∪{z}. Existing work uses the privacy region of (ε,δ)-DP to convert the attack's FPR/FNR into an ε lower bound; this paper instead uses f-DP matched to the true trade-off function of the audited mechanism to perform this conversion, which is GDP when the mechanism is Gaussian, thereby eliminating the slack introduced by definition conversion.

   From (ε,δ)-DP auditing to f-DP auditing

   • Problem: different mechanisms with the same (ε,δ) have different trade-offs (Figure 1: under ε=1, δ=1e-5, the Sampled-Gaussian, Gaussian, Laplace, and RandResp curves differ); when auditing the Gaussian mechanism with (ε,δ)-DP, the attack needs an extremely low FPR or FNR to approach the upper bound (in Figure 2, the point with FPR≈0.23 can only yield ε≈0.3).
   • Approach: directly lower-bound the mechanism's trade-off function. For the Gaussian mechanism, the empirical lower bound on µ is μ_emp^lower = Φ⁻¹(1−ᾱ) − Φ⁻¹(β̄), where ᾱ and β̄ are confidence upper bounds on FPR/FNR; then the µ lower bound is converted via Corollary 5 into the largest ε lower bound over each α.
   • Two kinds of intervals: f-DP (CP) uses Clopper-Pearson (following [21]); f-DP (ZB) extends the Bayesian credible interval of [30] to f-DP (Definition 6, using a Beta posterior).

   Trade-off function approximation for DP-SGD

   • Single step: each DP-SGD step is a subsampled Gaussian mechanism; when qc=1 (the canary is included every step), it degenerates to the Gaussian mechanism, characterized exactly by GDP.
   • Multi-step composition: PLD [16] is used to approximate the trade-off function (Appendix A, Algorithm 4 approximates with n supporting lines, and the authors state the error is on the order of 1e-1); step-by-step lower bounds are composed into an end-to-end lower bound via tight GDP composition or PLD composition.
   • Threshold independence: when qc=1 and observations are sufficient, the GDP lower bound is independent of the decision threshold (Figure 4, under 5,000 observations the lower bounds are approximately the same across thresholds), whereas (ε,δ)-DP (CP) is sensitive to the threshold; the authors state that this removes the need to hold out observations to select a threshold.

   Audit procedure and observation construction

   • White-box (Algorithm 2): at each step, independently sample two batches B and B′, with B′ including the canary with probability qc (gradient or input sample); the observation is the dot product of the privatized gradient and the canary gradient. After normalization, O=N(0,σ²I), O′=N(1,σ²I), exactly corresponding to the hypothesis testing of GDP.
   • Black-box (Algorithm 1): train 2T models (T with D, T with D∪{z}), use the loss of the canary sample (or log(p/(1−p))) as the observation, and select a threshold to compute FPR/FNR.
   • Canary design: the gradient canary uses the Dirac canary (only one coordinate is at the clipping norm C, the rest are zero, slightly better than constant and random canaries in Appendix C.2); the input canary uses Algorithm 3 to construct a sample whose gradient is orthogonal to the average gradient of the training batch (Appendix C.3, compared against three kinds: wrong label, blank, and adversarial example).

   Key parameters and settings

   • Defaults: qc=1 (focusing on the privacy mechanism itself rather than subsampling); unless otherwise stated, lower bounds are given as 95% confidence/credible intervals; by default, auditing uses Algorithm 2 under White-box access with Gradient Canaries.
   • Training configuration (Appendix B): on CIFAR-10, WRN-16 is trained for 2,500 steps with batch 4,096, reaching about 79% test accuracy under (ε=8, δ=1e-5)-DP; ConvNet with batch 256 and 20,000 steps reaches about 60% accuracy; Purchase uses a three-layer fully connected network.
   • Success criterion: the gap between the empirical ε lower bound and the theoretical upper bound given by accounting; in debugging scenarios, if the lower bound exceeds the claimed upper bound, the implementation is judged to be in violation.

   Collapse this answer

4. 04What experiments did the paper conduct?

   Under white-box, f-DP approaches the theoretical ε on three datasets; it can detect three types of implementation bugs (some missed by previous methods); the black-box lower bound is noticeably looser.

   Experimental setup

   • Models under test: WRN-16 and ConvNet on CIFAR-10, a three-layer fully connected network on Purchase, WRN-16 on a random dataset (random pixels and labels, same scale as CIFAR-10); Appendix D.2 additionally tests WRN-40.
   • Datasets: CIFAR-10, Purchase, randomly initialized dataset (Section 6.1).
   • Baselines: (ε,δ)-DP (CP) [12, 21], (ε,δ)-DP (ZB) [30], ε-DP (Katz) [17]; this paper's methods are f-DP (CP) and f-DP (ZB).
   • Metric: empirical ε lower bound, 95% confidence interval (CP) or credible interval (ZB); the default threat model is White-box access with Gradient Canaries (Algorithm 2).
   • Number of repetitions: Figure 3 uses 20 independent runs; Figure 6 uses 10 independent runs and reports standard deviation; the black-box experiment (Figure 11) trains 1,000 models with the canary and 1,000 models without the canary.

   Main results

   Table 1 (white-box gradient canary, 95% intervals, empirical ε lower bounds; theoretical ε is the accounting upper bound):

   Swipe horizontally to read the table

   Method	Theoretical ε	CIFAR-10 WRN-16	CIFAR-10 ConvNet	Purchase	Random WRN-16
   f-DP (CP)	8	5.80	6.12	6.40	7.14
   f-DP (ZB)	8	7.09	7.12	6.94	7.12
   (ε,δ)-DP (CP)	8	3.63	3.85	3.25	4.09
   (ε,δ)-DP (ZB)	8	5.07	5.15	4.65	5.09
   ε-DP (Katz)	8	4.17	3.95	4.24	4.15
   f-DP (ZB)	16	13.95	13.80	13.80	15.14

   (According to Table 1; the full table also contains rows for theoretical ε=1 and 4, omitted here)

   • The authors state that, whether using CP or ZB intervals, the main gain comes from auditing with f-DP; in Figure 6 (CIFAR-10, theoretical ε=8), f-DP is nearly tight, whereas the previous strongest lower bound was about 5.
   • The authors state that the results refute the conjecture of Lu et al. [17] that "privacy leakage depends on the dataset": under white-box gradient canary, the lower bounds on the three datasets and the random dataset all approach the theoretical value.
   • Figure 3: when auditing with GDP, 1,000 observations suffice to be tight, whereas (ε,δ)-DP (CP) needs 100 million observations to be tight (20 independent runs, δ=1e-5).

   Debugging DP-SGD implementations (Section 6.3, CIFAR-10, claimed upper bound ε=1.27, auditing a single step)

   • Clipping order bug (Figure 7): averaging before clipping. All methods can detect the violation, but only f-DP can give a lower bound of ε>35, which the authors state shows the implementation is "completely broken", whereas other methods give lower bounds below 10, which might lead one to mistakenly believe that some privacy is still preserved.
   • Biased noise bug (Figure 8): the noise seed has only 100 possible values. f-DP and the Katz method of Lu et al. [17] can detect it; using (ε,δ)-DP directly (CP or ZB) fails to detect it.
   • Too-small noise scale bug (Figure 9): the f-DP lower bound is tight against the true upper bound, detecting the violation already at true ε=1.57; the (ε,δ)-DP methods fail to detect it even when the true ε reaches 2.17.

   Threat models and leakage analysis (Section 6.4 and Appendix D)

   • Input-space canary (Figure 10, white-box): when only samples can be inserted, a tight lower bound can still be obtained within the range ε<10; WRN is nearly tight on all datasets, whereas on CIFAR-10 there is a large gap between ConvNet and WRN, and the authors state that model architecture clearly affects input-space auditing. The lower bound obtained using only the first 250 steps is higher than the lower bound over the full 2,500 steps.
   • Clipping only without adding noise (Table 2, black-box, CIFAR-10 WRN-16, 2,000 models): with clipping norms C=0.1, 1.0, 10.0, the ε lower bounds are 23.4, 26.8, 41.0 respectively (the maximum possible lower bound under this number of observations is 44.0), and the authors state that clipping only provides no privacy.
   • Black-box threat model (Figure 11, trained to ε=8, 1,000 models each): on CIFAR-10 WRN, the f-DP (ZB) lower bound is about 1.6; on other datasets/architectures it is noticeably lower, and no non-trivial lower bound can be obtained on the random dataset. The authors point out that under black-box there is still a gap between theory and empirical results, and that the size of the gap depends on the dataset and model architecture; they also point out that it is difficult to separate the effects of the black-box limitation and subsampling (Figure 5 shows that when qc=1/4, both GDP and PLD overestimate the trade-off).

   Other ablations and analyses

   • Canary gradient shape (Figure 14a, Appendix C.2): the Dirac canary is slightly better than constant and random canaries; the difference between static and per-step resampled (moving) canaries is very small (Figure 14b).
   • Input canary type (Figure 15, Appendix C.3, CIFAR-10 WRN): the canary constructed by Algorithm 3 gives the tightest lower bound, better than wrong label, blank, and PGD adversarial examples.
   • Early vs. late training (Figure 16, Appendix D.1, input-space attack): on CIFAR-10, early iterations leak more, and this phenomenon is not observed on the random dataset; the authors state that the reason is left for future research.
   • Model scale (Figure 17, Appendix D.2): under f-DP auditing, the WRN-40 lower bound is slightly higher than WRN-16; the authors point out that using non-f-DP methods would lead to the opposite conclusion that WRN-16 leaks more.
   • Augmentation diversity Augmult (Figure 18, Appendix D.3): for Augmult from 1 to 16, the lower bound shows no clear trend.

   Collapse this answer

5. 05What are some points that can be further explored?

   The only follow-up direction the authors explicitly state is the reason why the lower bound becomes looser in the later stages of input-space attacks; the experiments cover three datasets, four architectures, and three types of bugs.

   Limitations and follow-up directions pointed out by the authors

   • Reason for the loosening of input-space attacks in later stages unknown (Appendix D.1): the authors write that the reason why the audit lower bound becomes looser in later training "requires further study and is left for future work".
   • Slack in auditing the subsampling mechanism (Section 5.4): Figure 5 shows that when qc=1/4, both GDP and PLD overestimate the FPR-FNR trade-off of the subsampled Gaussian mechanism; the authors believe that accurately auditing the subsampling mechanism may require attacks with more precise FPR and better thresholds.
   • Slack introduced by the PLD approximation (Appendix A): PLD has no closed-form trade-off function, and the approximation in Algorithm 4 makes the ε lower bound looser; the authors state the error is on the order of 1e-1.
   • Residual gap under black-box (Section 6.4): the authors state that under the black-box setting there is still a gap between the theoretical upper bound and the empirical lower bound, and that the size of the gap depends on the dataset and model architecture.
   • The paper has no separate Limitations section; the above are the shortcomings and open problems explicitly stated in the main text and appendices.

   Scope of experimental coverage

   • Models under test: WRN-16, ConvNet, three-layer fully connected network, WRN-40, four architectures in total (Section 6.1, Appendix D.2).
   • Datasets: CIFAR-10, Purchase, randomly initialized dataset (same scale as CIFAR-10).
   • Threat models: all three are covered—white-box gradient canary (default), white-box input-space canary (Figure 10), black-box (Figure 11, Table 2).
   • Debugging experiments: cover three types of bugs (clipping order, biased noise, noise scale), all under the setting of CIFAR-10, claimed ε=1.27, auditing a single step; the authors point out that this type of auditing cannot capture bugs caused by biased subsampling (Section 6.3).
   • Unreported items: the specific number of observations for each audit (except for the 1,000/100 million in Figure 3, the 5,000 in Figure 4, and the 1,000 models each in the black-box) is mostly not given per experiment; the paper does not report specific numbers for runtime or computational cost (only stating that the overhead becomes twice as much).

   Collapse this answer

6. 06Summarize the main content of the paper

   Auditing DP-SGD with f-DP: on natural datasets, two training runs suffice to obtain a tight ε lower bound, and implementation bugs missed by previous audits can be found.

   This is a paper on a differential privacy auditing method, answering two questions: whether the theoretical analysis of DP-SGD is tight only for the worst-case dataset, and whether a tight audit can be completed with a small number of training runs.

   • Method: Replace (ε,δ)-DP with f-DP matched to the mechanism—GDP for the Gaussian mechanism, PLD to approximate the trade-off function for subsampled composition—then convert the attack's FPR/FNR into an ε lower bound using Clopper-Pearson or Bayesian intervals; in the white-box setting, use Dirac canary gradients and dot-product observations, and when qc=1 the GDP lower bound is independent of the decision threshold.
   • Tightness: Under white-box gradient canaries, the f-DP lower bounds on CIFAR-10, Purchase, and random datasets are all close to the theoretical values—at theoretical ε=8, f-DP (ZB) obtains 7.09 on CIFAR-10 WRN-16, whereas the strongest prior method (ε,δ)-DP (ZB) obtains 5.07 (Table 1); the GDP audit is tight with 1,000 observations, while (ε,δ)-DP (CP) requires 100 million (Figure 3). The authors state this refutes the conjecture that "privacy leakage depends on the dataset."
   • Cost: The authors state that the audit requires only two training runs, with computational overhead only twice the original.
   • Debugging application: On an implementation claiming ε=1.27, f-DP detects three types of bugs—incorrect clipping order (lower bound ε>35), biased noise, and too-small noise scale (detected at true ε=1.57); of these, the latter two types were not detected by some prior methods (Figures 7–9).
   • Boundaries: Under the black-box threat model, the lower bound for CIFAR-10 WRN at ε=8 is about 1.6, and on random datasets there is no non-trivial lower bound; clipping without adding noise provides no privacy (lower bound 41.0 at C=10, close to the upper limit 44.0, Table 2).
   • Authors' conclusion: The authors recommend that DP machine learning developers incorporate this auditing tool into their testing pipeline, and state that it can be integrated into libraries such as TF-privacy, Opacus, and JAX privacy for online estimation.

   Collapse this answer

Related papers