Unleashing the Power of Randomization in Auditing Differentially Private ML

Summary

The use of canaries is a very intuitive strategy to evaluate the DP mechanism (which can subsequently attract a broader non-DP specialist audience to this area). The paper is structured well, has comprehensive details on both the method and the corresponding experimental results and shows clear motivation and conclusions. This work presents methodology for auditing of DP trained models through the introduction of Lifted DP and canary-based auditing techniques.

Strengths

The use of canaries is a very intuitive strategy to evaluate the DP mechanism (which can subsequently attract a broader non-DP specialist audience to this area). The paper is structured well, has comprehensive details on both the method and the corresponding experimental results and shows clear motivation and conclusions.

Weaknesses

While the method show promise, the evaluation results are not very representative: FMNIST is a rather small dataset and so is Purchase-100. Given that the models associated with these are also rather small too, I do not see how well can this method scale to larger architectures and more complex datasets (especially as the canary-generation process can heavily depend on it). It is not very clear to me what the advantage is over the work of https://arxiv.org/abs/2305.08846. Here model auditing can be performed in a single training run, rendering other methods of auditing significantly less efficient. I would like the authors to comment on why their work is a substantial contribution given the existence of this method.

Questions

What is the dependency with epsilon level? There does not seem to be a clear trend of how well the method performs with more noise being added. I would like the authors to discuss this further and hypothesise what the trend is and why. Could the authors elaborate on what they mean by ‘poisoning’ canaries? What is the methodology like on non-image modalities?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

I described most of the limitations in the weaknesses section, but to summarise: A) it is not clear how the method performs in non-trivial settings (e.g. ImageNet), B) the improvements compared to the work I linked above are not clear. Overall, this work shows promise, but I would like the authors to clarify the points I raised above before I can recommend acceptance.

Summary

The authors propose a principled improvement over existing privacy auditing techniques. Privacy auditing through the binary hypothesis testing formulation implies gathering samples on the success of the adversary when trying to correctly guess the membership game against a mechanism $M$. All auditing techniques involve switching to a high-probability argument via confidence intervals to be able to provide lower bounds. These CIs converge with a rate of $O(\frac{1}{\sqrt{N}})$, where N is the number of auditing samples. The goal of this paper is to improve this convergence rate by testing multiple (possibly correlated) samples at a time, providing an improvement for the convergence of up to $O(\frac{1}{\sqrt{NK}})$, where K is the number of inserted canaries. Their proposed technique is as follows: 1. Run the mechanism $M$ on $D \cup ( c_1, .., c_K ) $ and $D \cup (c_1, .., c_{K-1}) $, where the canaries are iid samples drawn from a fixed canary distribution. Through a clever randomisation argument, using the property that the canaries are iid from the same distribution, the authors propose testing multiple iid canaries by testing other iid canaries by exchanging the missing $c_K$ with other iid canaries. By doing this, the authors can test $K$ test statistics for the alternative hypothesis and $M$ test statistics for the null hypothesis. Now, the goal is to integrate this new information into the confidence interval. The authors do not make an independence assumption as in previous work and derive a tailored confidence interval that accounts for the possible correlation between the K tests. Their analysis shows how their confidence interval converges with a rate of $O(\frac{1}{\sqrt{N }})$ when the statistics are correlated to a rate of $O(\frac{1}{\sqrt{NK}})$ when the statistics are independent.

Strengths

* The paper has a nice structure, it solves a clearly stated problem known in the privacy auditing community, for which they introduce all the needed formalism and they make the necessary experiments to back up their results. * The authors propose an algorithm that could be used as a drop-in replacement for other auditing techniques. * Formally accounting for the correlation between hypotheses fills an existing gap in auditing literature when multiple samples are used for auditing purposes. All the literature I am aware of makes an independence assumption, which might be strong in some cases. This work recovers that case but accounts for others as well, framing and formalising in a principled way the multisample testing problem.

Weaknesses

* in the experimental section, the authors show a bias/variance tradeoff when auditing a mechanism M that computes a noisy sum/mean. The same argument does not hold against differentially private machine learning models, and it would be interesting to show if the proposed technique can achieve tightness when auditing a (possibly simple) machine learning pipeline.

Questions

* The proposed auditing technique is not tailored for the Gaussian mechanism but for any mechanism $M$. For example, one could audit a Laplace Mechanism or a Subsampled Gaussian Mechanism with it. I think the authors could stress this out for the reader, as improving auditing sample complexity in the general case is a truly desirable property, and this work does that. Would the authors want to add some details or employ their technique to audit more diverse mechanisms? * The bias/variance argument in section 4 holds against a mechanism that averages over a list of gradients, as it is easy to observe how inserting noisy samples will yield privacy amplification in that scenario. Yet, when we audit a machine learning model with input poisoning (so, actual samples need to be inserted, not the gradients), the relationship is not so clear anymore. How many sample canaries could we use for auditing purposes against a machine-learning model? Is there any scenario in which we can hope to audit correctly by training only two models, for example? (n=1, k=?) What is the performance in that scenario?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

-

Summary

This work studies the sample complexity (in terms of sampled models) of auditing differential privacy. It proposes a new approach to usage of canaries in auditing via hypothesis test, breaking an existing sample complexity barrier by making use of multiple, randomized canaries. These randomized canaries are used to audit a new, but equivalent formulation of approximate differential privacy called lifted DP, which states a privacy condition for neighboring datasets and rejection sets sampled from a distribution. Sampled models are reused to compute test statistics for each of the multiple canaries included in the dataset, and confidence intervals for the average test statistic are computed using techniques introduced in the paper, tailored to the distribution of test statistics produced by the new auditing method. Empirical evaluation of the proposed method is also given.

Strengths

The paper makes progress in improving the sample complexity of DP auditing by introducing new techniques that should be compatible with future progress in strengthening canaries. The usage of multiple, randomized canaries is innovative and novel tools were used to adapt their usage to existing hypothesis testing frameworks for auditing. The empirical results in Section 4 and 6 were quite helpful in interpreting the expected sample complexity improvements from various choices of K and order of confidence interval.

Weaknesses

The sample complexity improvements seem notable, but I'm curious about how large of a bottleneck sample complexity is to practical auditing efforts. I'd expect it to be a significant obstacle, but additional discussion of the extent to which sample complexity impedes privacy auditing could help further motivate this work. Notes: pg 5 - "in practice, it depends on how correlated the K test are" In the caption of figure 3 - "provides significant gain in the require number of trials to achieve a desired level of lower bound" pg 9 - "For deployment in production, it worth further studying approaches with minimal computational overhead"

Questions

See comments in weaknesses.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Yes, the authors adequately addressed potential societal impact.

Summary

This paper presents a methodology for calculating lower bounds for the parameter $\\varepsilon$ of an $(\\varepsilon,\\delta)$-differentially private (DP) mechanism. When applied to machine learning algorithms, the methodology can be used to audit the privacy guarantees of popular training algorithms such as DP-SGD. The paper builds on existing methods that audit DP guarantees by testing the presence of a canary in the input of the mechanism. Given an $(\\varepsilon,\\delta)$-DP mechanism $\\mathcal{A}$, two neighboring datasets $D_0$ and $D_1 = D_0 \\cup \\{c\\}$ and a measurable set $R$, a lower bound for $\\varepsilon$ is given by $$ \\varepsilon \\geq \\log (\\mathbb{P}(\\mathcal{A}(D_1) \\in R) - \\delta) - \\log \\mathbb{P}(\\mathcal{A}(D_0) \\in R) . $$ A lower bound for $\\varepsilon$ can be derived from a lower bound $\\underline{\\boldsymbol{p}}_1 \\leq \\mathbb{P}(\\mathcal{A}(D_1) \\in R)$ and an upper bound $\\overline{\\boldsymbol{p}}_0 \\geq \\mathbb{P}(\\mathcal{A}(D_0) \\in R)$ estimated from samples. This lower bound can be made tighter by choosing a canary $c$ whose presence in the training dataset can be easily tested with a rejection set $R$. However, using Bernoulli confidence intervals computed from $n$ samples, the bounds $\\underline{\\boldsymbol{p}}_1, \\overline{\\boldsymbol{p}}_0$ are loose by a factor of $1/\\sqrt{n}$. Since each sample requires evaluating $\\mathcal{A}$ on a different dataset $D_0$, decreasing this factor is expensive. The key idea of the paper is to instead audit a probabilistic lifting of DP (LiDP) using counterexamples sampled from a joint distribution $( \\boldsymbol{D_0}, \\boldsymbol{D_1}, \\boldsymbol{R})$. While entirely equivalent to DP, thanks to the exchangeability of random i.i.d canaries LiDP allows reusing samples $\\mathcal{A}(D \\cup \\{c_1,\\ldots,c_K\\})$ and $\\mathcal{A}(D \\cup \\{c_1,\\ldots,c_{K-1}\\})$ to gather multiple correlated test statistics $\\boldsymbol{x}_k$, one for each canary $c_k$. A lower bound for $\\varepsilon$ can be then calculated similarly as for DP from bounds of the mean of these statistics. The paper analyzes the correlation between the statistics to derive higher-order exact (Bernstein) and asymptotic (Wilson) confidence intervals. Importantly, the authors prove that $\\ell$-th order bounds are loose by a factor of $n^{(1-2\\ell)/(2\\ell)}$ when choosing $K = \\lceil n^{(\\ell-1)/\\ell} \\rceil$ and so e.g. second-order bounds reduce the number of samples required to attain a given confidence because their looseness decreases as $1/n^{3/2}$ rather than $1/n^{1/2}$ for first-order bounds (and previous methods auditing DP). The authors evaluate the methodology on a Gaussian mechanism showing a 4x gain in sample efficiency when using second-order confidence intervals with $n=1000$ compared to a baseline using Bernoulli confidence intervals. They also evaluate the method on linear and 2-layer MLP classifiers trained with DP-SGD on FMNIST and Purchase-100 using either random or clipping-aware poisoned canaries [31]. This evaluation shows an average improvement in sample efficiency of up to 3x also with $n=1000$. The supplemental material includes proofs of the results in the paper, algorithmic descriptions of the methodology, a derivation of asymptotic Wilson intervals, and comprehensive ablation studies varying the privacy budget $\\varepsilon$, the number of canaries $K$, samples $n$, and dimension (for the Gaussian mechanism).

Strengths

1. A novel method for auditing differential privacy that can be combined with existing canary design strategies and improve sample efficiency. 2. First formal analysis of previously used heuristics reusing trained models to obtain multiple samples. 3. Technically solid theoretical foundations. Detailed proofs. Derivation of exact and asymptotic confidence intervals. 4. Great high-level intuition for why the method improves sample efficiency and the reasons for the bias/variance trade-off in selecting the number of canaries to use. 5. Extensive algorithmic descriptions of the method in the supplemental material that make the paper fairly self-contained and enable reproducibility. Authors promise to open-source their code to replicate results.

Weaknesses

1. The evaluation on ML scenarios uses very simple models: a linear model and MLPs with 2 hidden layers with 256 units (269k and 245k parameters for FMNIST and Purchase-100, respectively). 2. Evaluation baselines are limited to approaches using Bernoulli confidence intervals and not to more recent approaches using credible regions [66] which also claim improved sample efficiency.

Questions

1. Using the form of Bernstein's bound I am familiar with (Dudley, Richard M. Uniform central limit theorems. Vol. 142. CUP, 2014) would give a slightly tighter bound than in Equation (6). The bound in the paper seems to use $\\sqrt{a+b} \\leq \\sqrt{a} + \\sqrt{b}$ to simplify it, making it looser. Can you clarify whether you use this simplification, or else provide a detailed derivation? 2. In your evaluation, do you set $m = K$ in Algorithm 1? 3. There seems to be a qualitative difference between $\\underline{\\boldsymbol{p}}_1$ and $\\overline{\\boldsymbol{p}}_0$ in Algorithm 1 that is not discussed in the paper. The former is calculated from statistics $\\boldsymbol{x}^{(i)}$ using canaries $c_1,\\ldots,c_K$ inserted into the training set while the latter is calculated from statistics $\\boldsymbol{y}^{(i)}$ depending on canaries $c'_1,\\ldots,c'_m$ not in the training set that are independent of the output of the mechanism (the statistics themselves are correlated because they all use the same model). The bias-variance tradeoffs that you discuss in §4 seem to apply only to $c_k$. Are there tradeoffs that make increasing the number of out-canaries $m$ not always beneficial? ### Details - The paper presents exact Bernstein confidence intervals but then uses asymptotic Wilson intervals exclusively in the evaluation. The two are only compared in Figure 2. I would have liked to see an additional comparison in at least some selected empirical results for bounds on $\varepsilon$. - In Eq.1 $D,D'$ should be $D_0,D_1$. This has been fixed in the PDF in the supplemental material. - l.119: "the canary has the freedom" => "the **adversary** has the freedom"? - l.197: "applying probabilistic method" => "applying **a heuristic** method"? - Figure 1 is not referenced. I think it is supposed to support the analysis in the paragraph starting at line 271. - In Figure 3 caption: "require number" => "required number" - l.243: "find §4 that" => "find **in** §4 that" - l.346: "it worth" => "it **is** worth" - l.710: $k$ => $K$ - In Algorithm 3 in steps 4 and 5, and in Algorithm 4 in steps 5 and 6, I believe that there is a missing $\frac{K-1}{K}$ multiplying $\overline{\boldsymbol{\mu}}_2$ as in Equation (17).

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors discuss some limitations of the auditing methodology throughout the paper and discuss the need to balance the tightness/computation trade-off in practice. It could be a good idea to complement this with a discussion of how the lower bounds for $\\varepsilon$ depend on the canary design and detection strategy, how to interpret the gap between lower bounds and the theoretical guarantee of a mechanism, and the impact of deciding whether a mechanism provides enough privacy based on a lower bound alone. I also believe that given the size and variety of the ML models used in the evaluation, the paper should discuss how the results may extrapolate to other architectures and larger number of parameters. Figure 4 (right) shows the method may benefit as the dimension increases; it would be great if this effect could be backed with experimental results on ML models.

Response to the rebuttal

I would like to thank the authors for responding to my comments. A lot of their responses have really clarified certain aspects of the work (particularly the part on different levels of epsilon and the comparison to the method I have linked above). You are right in saying that this work was overlapping with this submission, so I will remove this issue from consideration. I am still not entirely happy with the comment on larger datasets, as in my mind, any canary-based method could suffer significantly from more complex datasets, potentially rendering these methods infeasible. I will, nonetheless, raise the score in light of my first comment, but would ideally still like an extended discussion (if not experimental evidence) on how well the method scales with some examples. Score has been raised accordingly and happy to update it further if this comment is addressed in detail.

Thank you for your review! Could you please check the rebuttal?

Thank you again for your thorough review! As the discussion period draws to a close, could you please take a look at the rebuttal and make sure that we have answered all your questions? Thank you!