Privacy Auditing with One (1) Training Run

Thomas Steinke; Milad Nasr; Matthew Jagielski

Source-linked AI summary

Privacy Auditing with One (1) Training Run

Thomas Steinke, Milad Nasr, Matthew Jagielski

arXiv:2305.08846v1May 15, 2023cs.LGcs.CRcs.DS

TL;DR

Privacy audits typically require hundreds of algorithm runs to estimate outcome probabilities, raising whether one training run can suffice. This paper shows that auditing can be done in a single run and can produce meaningful lower bounds on ε, although tightness depends on the setting.

Problem
Privacy auditing typically estimates outcome probabilities by running the algorithm hundreds of times, motivating the question of whether one run can suffice.
Method
The method audits multiple examples within one training run, leveraging the iterative structure of DP-SGD and distinguishing randomized auditing examples from always-included examples.
Results
The method can provide meaningful lower bounds on ε in practical settings; in an idealized randomized-response setting, 10,000 guesses yield ε ≥3.87 with 95% confidence.
Takeaways & Limitations
Single-run auditing can substantially reduce the computational burden of privacy auditing compared with methods requiring hundreds or thousands of runs.
Takeaways & Limitations
In a Gaussian-noise setting, the lower bound can remain substantially below the upper bound, with a 393× gap in δ.

Abstract

from arXiv · show

We propose a scheme for auditing differentially private machine learning systems with a single training run. This exploits the parallelism of being able to add or remove multiple training examples independently. We analyze this using the connection between differential privacy and statistical generalization, which avoids the cost of group privacy. Our auditing scheme requires minimal assumptions about the algorithm and can be applied in the black-box or white-box setting.

1 Introduction

Privacy auditing empirically lower-bounds an algorithm’s privacy parameters, but conventional audits require hundreds of runs. This paper replaces repeated runs with independently including or excluding multiple examples in one run, analyzed through DP and generalization.

Motivation: Conventional audits estimate output probabilities by running the algorithm hundreds of times, making auditing computationally expensive.They construct neighboring inputs and estimate the probabilities of an outcome under each input.
Motivation: The paper asks whether privacy auditing can be performed using a single algorithm run.
Approach: The auditing scheme independently includes or excludes multiple examples in one training dataset and infers their selections from the algorithm’s output.The auditor can guess or abstain for each auditing example.
Approach: The analysis uses the connection between differential privacy and statistical generalization instead of relying naively on group privacy.Independent inclusion or exclusion makes one run comparable, roughly, to multiple independent runs when δ is small.
Scope: The framework applies to black-box and white-box auditing and is demonstrated on DP-SGD training.The supplied contribution passage reports meaningful empirical lower bounds on ε in practical settings.

2 Our Auditing Procedure

The auditor randomizes membership for selected examples, scores them after one run, and converts correct guesses into privacy lower bounds. The analysis controls these guesses under DP, while accounting for a δ-dependent error term.

Procedure: The auditor includes each of the first m examples with 50% probability, scores them after running the algorithm, and guesses inclusion for the highest and lowest scores.It abstains on the remaining m − k+ − k− auditing examples.
Procedure: Auditing examples, also called canaries, are randomized while the remaining training examples stay included and are not guessed.Choosing m < n can reduce score-computation costs or preserve real training data for model utility.
Procedure: The score vector should correlate with the true selections, but excessive correlation would violate differential privacy; postprocessing transfers DP to the guesses.
Analysis: Ignoring δ, the number of correct guesses is stochastically dominated by a binomial distribution corresponding to DP randomized response.The randomized-response comparison identifies the worst-case algorithm for the number of correct guesses and makes the theorem tight when δ = 0.
Analysis: The guarantee includes an additional O(δ) term, bounded by 2mδ and potentially smaller for reasonable parameters.
Analysis: A number of correct guesses exceeding the DP upper bound enables rejection of the corresponding hypothesis and conversion to a confidence-based lower bound on ε.The bound has the form r·eε/(eε+1) + O(√r) with high probability.

3 Related Work

Prior privacy audits commonly use membership inference and repeated or iterative analyses. This work formally justifies auditing multiple examples simultaneously, removing the independence assumption used by earlier applications of that heuristic.

Existing audits: Membership inference attacks can yield a lower bound ε ≥ loge(TPR/FPR) after statistically validating the TPR and FPR estimates.
Existing audits: Prior auditing work evaluates privacy analyses using standard or stronger membership inference attacks across different threat models.
Existing audits: Other improvements audit individual DP-SGD steps or use sharper statistical techniques for estimating ε.
Multiple-example auditing: Earlier work proposed membership inference on multiple examples simultaneously as an efficiency heuristic, but its TPR and FPR estimates were not based on independent samples.
Multiple-example auditing: This paper proves the validity of multiple-example membership inference for auditing, enabling auditing analysis to use progress in membership inference methods.The authors describe this as the first proof supporting standard attacks that target multiple examples per training run.

4 Background

The paper reviews differential privacy, postprocessing, DP-SGD, and statistical estimation of privacy parameters. Its auditing guarantee is frequentist: with high probability, the reported lower bound on ε does not exceed the algorithm’s true privacy parameter.

Privacy background: Differential privacy protects against changes formed by adding or removing one data element, with variants including Rényi and concentrated differential privacy.
Privacy background: Differential privacy is preserved when an arbitrary function postprocesses an algorithm’s output.This property supports analyzing score-derived guesses as private functions of the algorithm output.
DP-SGD: DP-SGD repeatedly samples records, clips gradients, adds Gaussian noise, updates model weights, and outputs the weight sequence.
Auditing interpretation: The auditing goal is to estimate a statistical lower bound on the privacy parameters accompanying a formal privacy guarantee.
Auditing interpretation: If the algorithm satisfies (εtrue, δ)-DP, the auditor’s output εLB is at most εtrue with probability at least 1 − β.The confidence is frequentist because probability is taken over the auditing procedure, not beliefs about the algorithm.
Auditing interpretation: The lower-bound estimator can be viewed as repeatedly testing null hypotheses that the algorithm satisfies (εnull, δ)-DP.Rejecting a null hypothesis yields εLB = εnull.

5 Theoretical Analysis

The analysis derives sharp generalization-based bounds that turn correct guesses from a single audit into privacy tests and lower bounds. It covers pure, approximate, and ternary-guess settings, with extensions that adapt to the observed output.

General framework: The analysis develops sharp differential-privacy generalization guarantees because existing bounds have non-optimal constants for auditing.The resulting bounds support the paper’s single-run auditing scheme without relying on group privacy.
General framework: The audit randomizes inclusion of multiple examples independently, then uses the algorithm’s output to guess each inclusion bit and infer privacy from correct guesses.The same formalism represents both the audited algorithm and the auditor; examples are hardcoded into the abstraction.
Pure DP analysis: The observed weighted number of correct guesses produces a p-value for testing ε-DP and a high-confidence lower bound on ε by inverting the bound.The null hypothesis is rejected when the p-value is sufficiently small, such as 0.05.
Pure DP analysis: Under pure (ε, 0)-DP, each guess is bounded by e^ε/(e^ε+1) correctness probability, yielding a product-distribution worst-case benchmark.The bound is tight when each input bit receives an independent randomized-response mechanism.
Approximate DP analysis: Approximate-DP guarantees require bounded guesses and add a failure probability depending on δ because some outputs can have unbounded privacy loss.Theorem 5.2 provides the main approximate-DP bound, while Corollary 5.3 gives an analytic form under norm constraints.
Extensions: The framework extends to ternary guesses and biased independent input bits, and can dynamically adjust the number of guesses to the observed output.The general proposition allows the inclusion probability to be p rather than one-half; the variant supports output-dependent auditing choices.

6 Experiments

Experiments evaluate the auditing framework across white-box and black-box settings, varying auditing examples, additional data, iterations, and attack access. White-box audits achieve meaningful privacy lower bounds with one training run, while black-box effectiveness is more sensitive to the amount of training data.

Experimental setup: The experiments use DP-SGD on CIFAR-10 with a Wide ResNet and evaluate gradient and input attacks in white-box and black-box settings.The setup follows prior auditing work and reports lower bounds with 95% confidence unless otherwise specified.
White-box gradient-space attacks: Increasing the number of auditing examples tightens white-box empirical lower bounds, although the benefit eventually diminishes.The experiments vary the number of inserted auditing examples to assess bound tightness.
White-box gradient-space attacks: Adding non-auditing training examples does not materially affect white-box auditing tightness.The result is attributed primarily to gradient attacks generating near-worst-case datasets irrespective of other data points.
White-box gradient-space attacks: Changing the number of DP-SGD iterations does not significantly change white-box auditing results when overall privacy is held constant by increasing noise.This comparison covers one iteration versus multiple iterations under equivalent privacy guarantees.
White-box gradient-space attacks: On CIFAR-10 models, the white-box framework obtains meaningful empirical privacy lower bounds while requiring only one end-to-end training run.For theoretical ε values of 1, 2, 4, and 8, the reported empirical lower bounds are 0.7, 1.2, 1.8, and 3.5, respectively.
Black-box input-space attacks: In black-box input-space auditing, increasing auditing examples does not produce a monotonic relationship with auditing tightness, while adding superfluous training data significantly reduces effectiveness.The black-box setting permits insertion of actual images but restricts the auditor to observing the final model.

7 Discussion

The method achieves meaningful and sometimes tight privacy lower bounds from a single training run, but computational efficiency comes with reduced tightness in realistic settings. The gap is especially sensitive to the number of guesses, abstentions, confidence, and δ.

A single training run can produce meaningful lower bounds on ε, avoiding the hundreds or thousands of runs required by prior auditing methods.
Black-box auditing is sensitive to the number of auditing examples, while adding additional training examples significantly loosens the results.
With 10,000 guesses, the idealized audit obtains ε ≥3.87 with 95% confidence for a setting whose compatible maximum is ε = 4.
The lower bound improves with more guesses because sampling error becomes relatively smaller at fixed confidence.
In the Gaussian setting, the best lower bound is ε ≥2.675 versus an upper bound of ε = 4.38 at δ = 10−5, leaving a 393× gap in δ.
The lower bound is inherently sensitive to guesses, abstentions, δ, and confidence because realistic algorithms differ from pathological cases where the analysis is nearly tight.
Future work includes stronger attack methods, algorithm-specific analyses, combining multiple examples with multiple runs, and extending auditing beyond empirical lower bounds.

A Sampling a Fixed-Size Dataset

The framework can be modified to keep dataset size fixed by replacing one example with another, rather than independently adding or removing examples. This preserves the theoretical analysis but changes the privacy notion and auditing procedure.

Randomly including or excluding m examples independently makes the dataset size random.Each example x_i is included when S_i = +1 and excluded when S_i = −1.
The fixed-size approach leaves the theoretical analysis unchanged but requires more examples and a replacement-based DP definition.The auditor also needs a slight modification to guess which paired example was included.
Starting with 2m examples and selecting one from each pair ensures that exactly m examples are included.For each i, S_i selects x_2i or x_2i−1.
Under this fixed-size construction, flipping S_i corresponds to replacing one example rather than adding or removing one.The audited algorithm must therefore satisfy DP with respect to replacement.

B Generalization from Differential Privacy

The paper extends the DP–generalization connection to derive auditing results for binary inputs and uniform sampling. Its analysis uses randomized rounding, ghost-sample symmetrization, and a binomial weighting induced by differential privacy.

The analysis restricts inputs to i.i.d. binary values with a uniform distribution, unlike prior work allowing arbitrary sets and distributions.This restriction specializes the general DP–generalization framework to the auditing setting.
Ghost-sample symmetrization is the technical basis for the generalization theorem.The proof averages a fixed-sample lemma over independent samples drawn from the data distribution.
Randomized rounding converts bounded algorithm outputs into binary coordinates while preserving their expectations.The resulting mechanism remains differentially private by postprocessing, allowing Theorem 5.2 to be applied.
The resulting bounds use a binomial random variable with parameter e^ε/(e^ε + 1).This weighting appears in the main theorem and its supporting generalization results.
The proofs combine coordinate-wise inequalities, independence, and concentration bounds to obtain the final guarantees.Hoeffding’s inequality contributes a failure term of e^−r²/2n for randomized rounding.

B.1 Comparison to Prior Work on DP & Generalization

Compared with prior DP–generalization work, the paper improves the dominant accuracy term and can remain non-vacuous for every ε. A concrete parameter setting also yields a smaller error guarantee than the comparison bound.

The comparison targets prior work on adaptive data analysis, whose setting differs mainly in requiring a private estimate of correct guesses.The paper presents a theorem and corollary arranged for direct comparison in the auditing setting.
The paper replaces the prior e^ε−1 accuracy term with e^ε−1/(e^ε+1).The cited comparison describes this as an improvement by a factor of at least two.
For ε ≥ log 2, the prior bound can be vacuous, whereas the paper’s bound can remain non-vacuous for any ε.The latter follows from e^ε−1/(e^ε+1) < 1.
With ε = 1/3, n = 2000, β = δ = 10^−5, and target failure probability 0.05, the compared guarantees are α + 0.397 and α + 0.308.Theorem B.4 gives α + 0.397, while Corollary B.5 gives α + 0.308.

C Mutual Information Bounds from DP

This section derives mutual-information bounds from differential privacy for uniformly sampled binary inputs and extends them to approximate DP. The extension improves the stated bound but retains an explicit dependence on δ.

The analysis studies mutual information when a DP mechanism receives a uniformly random binary vector.The framework is inspired by prior work connecting DP and information-theoretic quantities.
The paper improves the prior bound for (ε, δ)-DP mechanisms on uniformly random binary inputs.The stated improved bound includes terms proportional to ε²m and δm.
For Bernoulli sampling, the analysis introduces the binary entropy function h(p) and uses KL-divergence convexity.The proof applies the chain rule to obtain the corresponding information bound.
The paper uses natural logarithms throughout, while restating results to remain valid under consistent choices of logarithm base.This convention affects the information-theoretic quantities appearing in the section.
The proof decomposes each pair of neighboring output distributions into randomized-response components and residual δ components.Postprocessing and the data-processing inequality then transfer the resulting information bound to the mechanism output.

D Implementation of Theorem 5.2

The implementation provides pseudocode for computing a differential-privacy audit p-value and inverting it to obtain a lower bound on ε. Examples show how confidence, δ, and abstentions affect the resulting bound.

Example audits: ε ≥0.702 is obtained at 95% confidence when v = 75 correct guesses occur among m = r = 100 examples with δ = 0.For the same outcome, the null ε ≤ log 3 has p-value 0.553; setting δ = 10^-4 weakens the bound to ε ≥0.699.
Example audits: ε ≥0.673 is obtained at 95% confidence when v = 75 correct guesses are made among r = 100 guesses from m = 1000 examples with δ = 10^-4.This setting has 900 abstentions and yields a slightly weaker bound than the ε ≥0.699 result with no abstentions.
P-value computation: The p-value routine models auditor accuracy with q = 1/(1+exp(-ε)) and evaluates the probability of at least v correct guesses, including the δ adjustment across m examples.It computes a binomial survival probability and adds an αδ2m term before capping the result at 1.
Inputs and output: The audit takes m examples, r non-abstaining guesses, v correct guesses, δ, and p=1-confidence, then returns a lower bound on ε.The implementation validates 0 ≤ v ≤ r ≤ m, 0 ≤ δ ≤ 1, and 0 < p < 1.
Lower-bound search: The lower-bound routine increases an upper ε bracket until the audit p-value reaches p, then uses 30 binary-search iterations to locate the boundary.The maintained conditions are p_value_DP_audit(ε_min) < p and p_value_DP_audit(ε_max) ≥ p.