Nearly Tight Black-Box Auditing of
Differentially Private Machine Learning^††thanks: To appear at NeurIPS 2024, please cite accordingly

Differentially Private Stochastic Gradient Descent (DP-SGD) [1] is a popular algorithm for training machine learning models while satisfying DP. In this paper, we consider classification tasks on samples from the domain $\mathcal{X}\times\mathcal{Y}$, where $\mathcal{X}$ is the features domain and $\mathcal{Y}$ is the labels domain.

DP-SGD, reviewed in Algorithm 1, introduces two hyper-parameters: gradient clipping norm $C$ and noise multiplier $\sigma$. Typically, $C$ is set to 1, while $\sigma$ is calibrated to the required privacy level $(\varepsilon,\delta)$ based on the number of iterations, $T$, and batch size, $B$. Early DP-SGD work [1] set batch sizes to be small and similar to those of non-private SGD; however, recent work has highlighted the advantage of setting large batch sizes [13, 16] by training state-of-the-art models with them. Following this trend, and to ease auditing, we set $B=N$, as also done in prior work [31]. Finally, while the initial set of model parameters $\theta_{0}$ is typically sampled randomly (e.g., using Xavier initialization [20]), it can also be set arbitrarily (and even adversarially), without affecting the privacy guarantees provided by DP-SGD.

In this setting, one first pre-trains a model on a (large) public dataset and then fine-tunes it on the private data. When a suitable public dataset is available, prior work has shown that fine-tuning can achieve much higher utility than training from scratch using DP-SGD [13].

There are two methods for fine-tuning: doing it for all layers or only the last one. In both cases, the initial model parameters, $\theta_{0}$, are set to the pre-trained model parameters (rather than randomly) before running DP-SGD. However, while the former updates all model parameters during DP-SGD, with the latter, the model parameters until the last (fully connected) layer are “frozen” and not updated during DP-SGD. This setting treats the pre-trained model as a feature extractor and trains a Logistic Regression model using DP-SGD based on the extracted features. As prior work shows [13] that this setting produces models with accuracy closer to the non-private state of the art (while also incurring smaller computational costs), we also do fine-tuning of just the last layer.

When auditing a DP mechanism $\mathcal{M}$, one runs $\mathcal{M}$ repeatedly on two neighboring inputs, $D$ and $D^{\prime}$, $R$ times each and the outputs $\left(O=\{o_{1},...,o_{R}\}\text{ and }O^{\prime}=\{o^{\prime}_{1},...,o^{\prime}_{R}\}\right)$ are given to an adversary $\mathcal{A}$. Next, $\mathcal{A}$ tries to distinguish between $O$ and $O^{\prime}$, which determines a false positive rate (FPR) and false negative rate (FNR). For a given number of outputs $2R$ and confidence level $\alpha$, empirical upper bounds $\overline{\text{FPR}}$ and $\overline{\text{FNR}}$ can be computed using Clopper-Pearson confidence intervals [32, 31]. Finally, the empirical upper bounds are converted to an empirical lower bound $\varepsilon_{emp}$ using the privacy region of $\mathcal{M}$ (see below) and $\varepsilon_{emp}$ can be compared to the theoretical $\varepsilon$. We consider an audit tight if $\varepsilon_{emp}\approx\varepsilon$. To ease presentation, we abstract away the details and use $\varepsilon_{emp}\leftarrow\text{EstimateEps}(\text{FPR},\text{FNR},2R,\alpha,\delta)$ to denote the process of estimating an $\varepsilon_{emp}$ from a given FPR and FNR.¹¹1Please refer to https://github.com/spalabucr/bb-audit-dpsgd for details.

Given a mechanism $\mathcal{M}$, the privacy region of the mechanism, $\mathcal{R}_{\mathcal{M}}(\varepsilon,\delta)=\{(\text{FPR},\text{FNR})|\cdot\}$ defines the FPR and FNR values attainable for any adversary aiming to distinguish between $\mathcal{M}(D)$ and $\mathcal{M}(D^{\prime})$. Nasr et al. [31] note that the privacy region of DP-SGD corresponds (tightly) to that of $\mu$-Gaussian Differential Privacy [15], which can be used to first compute a lower bound on $\mu$:

Then, a lower bound on $\mu$ corresponds to a lower bound on $\varepsilon$ by means of the following theorem:

We experiment with the MNIST [26] and CIFAR-10 [25] datasets. The former includes 60,000 training and 10,000 testing 28x28 grayscale images in one of ten classes (hand-written digits), Often referred to as a “toy dataset,” is commonly used to benchmark DP machine learning models. CIFAR-10 is a more complex dataset containing 50,000 training and 10,000 testing 32x32 RGB images, also consisting of ten classes. Note that the accuracy of DP models trained on CIFAR-10 has only recently started to approach non-private model performance [13, 38]. Whether on MNIST or CIFAR-10, prior black-box audits (using average-case initial parameters) have not been tight. More precisely, for theoretical $\varepsilon=8.0$, De et al. [13] and Nasr et al. [31] only achieve empirical estimates of $\varepsilon_{emp}\approx 2$ and $\varepsilon_{emp}\approx 1.6$, respectively, on MNIST and CIFAR-10.

To ensure a fair comparison between the average-case and worst-case initial parameter settings, we split the training data in two and privately train on only half of each dataset (30,000 images for MNIST and 25,000 for CIFAR-10). The other half of the training dataset is used as the auxiliary dataset to non-privately pre-train the models and craft the worst-case initial parameters (see Section 4). We note that for CIFAR-10, we additionally augment the pre-training dataset with the CIFAR-100 dataset to boost the model accuracy further (see Appendix A for further details).

When training the model fully, we use a (shallow) Convolutional Neural Network (CNN) for both datasets. We do so as we find accuracy to be poor with models like Logistic Regression and Fully Connected Neural Networks, and training hundreds of deep neural networks is impractical due to large computational cost. Therefore, we draw on prior work by Dörmann et al. [16] and train shallow CNNs that achieve acceptable model accuracy while being relatively fast to train. (We report exact model architectures in Appendix A). Whereas, for the last layer-only fine-tuning setting, we follow [13] and use the Wide-ResNet (WRN-28-10) [44] model pre-trained on ImageNet-32 [14].

All our experiments are run on a cluster using 4 NVIDIA A100 GPUs, 64 CPU cores, and 100GB of RAM. Auditing just one model took approximately 16 GPU hours on MNIST and 50 GPU hours on CIFAR-10.

In Table 1, we report the accuracy of the final models for the different values of $\varepsilon$-s we experiment with. While accuracy on MNIST is very good ($\geq 95\%$ for all $\varepsilon$), for CIFAR-10, we are relatively far from the state of the art (${\approx}50\%$ at $\varepsilon=10.0$ vs. ${\approx}80\%$ at $\varepsilon=8.0$ in [13]). This is due to two main reasons. First, as we need to train hundreds of models, we are computationally limited to using shallow CNNs rather than deep neural networks. Second, we need to consider a much larger batch size to ease auditing [31]; thus, the models converge much more slowly. In Appendix B, we show that, given enough iterations ($T=1{,}000$), the model reaches an accuracy of ${\approx}70\%$ at $\varepsilon=10.0$, almost approaching state-of-the-art. As a result, we audit models striking a reasonable trade-off between utility and computational efficiency, as discussed above.

In Figure 1, we compare the difference in $\varepsilon_{emp}$ between worst-case initial parameters and average-case parameters (as done in prior work [13, 22, 31]). In the latter, all models are initialized to the same, randomly chosen $\theta_{0}$ (using Xavier initialization [20]), while, in the former, to a $\theta_{0}$ from a model pre-trained on an auxiliary dataset. In the rest of this section, the target sample is set as the blank sample, which is known to produce the tightest audits in previous work [13, 31].

With worst-case initial parameters, we achieve significantly tighter audits for both MNIST and CIFAR-10. Specifically, at $\varepsilon=1.0,2.0,4.0,10.0$, the empirical privacy leakage estimates reach $\varepsilon_{emp}=0.08,0.54,1.89,6.48$ and $\varepsilon_{emp}=0.00,0.18,1.43,4.96$ for MNIST and CIFAR-10, respectively. In comparison, with average-case initial parameters as in prior work, the empirical privacy leakage estimates were significantly looser, reaching only $\varepsilon_{emp}=0.00,0.06,0.61,3.41$ and $\varepsilon_{emp}=0.07,0.02,0.20,0.69$ for MNIST and CIFAR-10, respectively. Notably, at larger privacy levels $\varepsilon=4.0$ and $\varepsilon=10.0$, for both MNIST and CIFAR-10, the empirical privacy leakage estimates when auditing with worst-case initial parameters are not only larger than the average-case, but are outside of the $\pm$ s.d. range. This shows that our auditing procedure not only produces significantly tighter audits than prior work, especially at larger $\varepsilon$s, but also that, at lower $\varepsilon$-s, our evaluations are currently limited by the number of models used to audit (resulting in large s.d.).

To shed light on why worst-case initial parameters improve tightness, we vary the amount of pre-training done to craft $\theta_{0}$ and, in Figure 2, plot the corresponding $\varepsilon_{emp}$-s and the average gradient norm of all samples (after clipping) in the first iteration of DP-SGD. For computational efficiency, we focus on MNIST and set the theoretical $\varepsilon$ to $10.0$. Recall that, regardless of the initial model parameters, all models achieve $\geq 95\%$ accuracy on the test set. As the number of pre-training epochs increases from 0 (no pre-training) to 5, the average gradient norm steadily decreases from $1.00$ to $0.51$, as expected. On the other hand, the empirical privacy leakage increases from $3.41$ to $6.48$. In other words, with more pre-training, the impact of the other samples in the dataset reduces, making the target sample much more distinguishable, thus yielding tighter audits. Although there appears to be an anomaly in the $\varepsilon_{emp}$ obtained when the model is pre-trained for 3 epochs, this is within the standard deviation.

In the auditing literature, empirical privacy leakage is often commonly estimated on (smaller) dataset samples both to achieve tighter audits and for computational efficiency reasons [13]. In Figure 3, we evaluate the impact of the dataset size ($n$) on the tightness of auditing. While smaller datasets generally yield tighter audits, the size’s impact also depends on the dataset itself. For instance, at $\varepsilon=10.0$, auditing with $n=100$ results in $\varepsilon_{emp}=7.41$ and $7.01$, for MNIST and CIFAR-10, respectively, compared to $\varepsilon_{emp}=6.48$ and $4.96$ on the full dataset. In other words, with MNIST, the dataset size does not significantly affect tightness. However, for CIFAR-10, smaller datasets significantly improve the audit’s tightness significantly.

Finally, we evaluate the impact of the hyper-parameters on the tightness of black-box audits. In the black-box setting, unlike in white-box, the adversary cannot arbitrarily insert gradients that are of the same scale as the gradient clipping norm, $C$ [31]. Thus, they are restricted to gradients that naturally arise from samples. In Figure 4, we report the $\varepsilon_{emp}$ values obtained with varying clipping norms, $C$. For computational efficiency, the results on CIFAR-10 are for models trained on datasets of size $n=1{,}000$.

When the gradient clipping norm is small ($C=0.1,1.0$), the audits are tighter. This is because the gradient norms are typically very small in the worst-case initial parameter setting, leading to a much higher “signal-to-noise” ratio. While this might suggest that black-box audits may not be as effective with larger gradient clipping norms, we observe that, with $C=10.0$, model accuracy is poor too—more precisely, with $\varepsilon=1.0,2.0,4.0,10.0$, accuracy reaches $85.6\%,93.1\%,95.0\%,96.1\%$, respectively, compared to $97.2\%,97.4\%,97.5\%,97.5\%$ with $C=1.0$ on MNIST. This indicates that audits are looser with $C=10.0$ because the model is not learning effectively, as there is too much noise. In fact, this could suggest that the privacy analysis for the $C=10.0$ setting could be further tightened in the black-box threat model, which we leave to future work.