Certification for Differentially Private Prediction in Gradient-Based Training

We thank the reviewer for their time and consideration of our work.

• Could you also give the memory overhead for the Algorithm 1? For example, when running gpt2, what's the memory consumption compared to DP-SGD?

Both DP-SGD and AGT require the computation of per-sample gradients, incurring a large memory overhead compared to standard pytorch training. However, much like DP-SGD, AGT can employ “virtual batches” to separate physical steps (gradient computation) and logical steps (parameter updates) (see https://opacus.ai/docs/faq, for example). This means that memory overhead can be managed by only storing per-sample gradients for a subset of a batch at a time. Computing SEMin/SEMax independently over each virtual batch amounts to storing the top-k per-sample gradients, incurring a memory overhead of O(k * no. parameters) during training. We thank the reviewer for the questions and will reference this in a revised version of our main text or if there is not space to do so will have a discussion of this in our Appendix.

• Given this substantial overhead, the improvement over DP-SGD is relatively modest, which may lead users to question whether adopting the new algorithm is worthwhile.

We first point out that the computational cost of our approach actually compares favorably with other private prediction methods that use ensembles. When compared with DP-SGD we do acknowledge that it requires additional overheads, but the privacy analyses are not exactly comparable. Additionally, as we point out in our global response, there are many avenues for future works to sharpen the bounds that we provide using the current instantiation of our framework. With many future directions for improvement we hope that this line of research yields privacy guarantees that are competitive with DP-SGD.

• Another limitation, as stated in the paper, is that the current method is restricted to binary classification.

We agree with the reviewer that our current practical instantiation of the framework is only practically validated on binary classification, however, the framework itself is general and future works will be able to extend this to regression and multi-class classification by leveraging tighter or use-case specific bounds.

• Its performance in PATE is effective only when the number of queries is small.

We would like to highlight that in our initial submission we do not use our bounds directly in the student-teacher set up of PATE, but only compare the mechanisms in the context of private prediction. However, as indicated in our response to reviewer dcek, using our private prediction mechanism to train a student allows the privacy budget to be fixed for an unlimited number of future queries.

With regards to ensemble approaches to private prediction, however, it is necessarily true that as the number of queries grows so does the expended privacy budget. However, we emphasize that the tighter privacy bounds of our approach are an orthogonal development to other private prediction methods and in theory can tighten other approaches enabling us to answer more queries within the same budget. For example, if the ensemble is using the global sensitivity in order to privatize its predictions, then there are cases (as we show in our paper) where our bound makes things strictly tighter thus allowing for more queries to be answered at the same privacy budget. We thank the reviewer for the comment and will try to clarify this in future works.

We thank the reviewer for their time and careful review of our work.

• The authors claim that fewer than 10 runs of the AGT algorithm are ... sufficient ... [this] lacks a more systematic sensitivity analysis.

We appreciate the reviewer's point that, though empirically we find a small number of AGT runs is sufficient and we believe this is a general result, we cannot rule out the need for many runs of AGT. We would like to stress that in Appendix C we explicitly study how different numbers of AGT runs result in tighter bounds, which is in fact an attempt to study the robustness of this claim. As this message may have been unclear, in our revision we will more explicitly reference this section to the main text.

• The computational overhead (reported as 20–40× standard training) may limit the practicality ... any avenues or potential for reducing this?

The computational overhead of our method as presented is indeed a practical hurdle of its adoption; however, we note that this paper is the first instantiation of a new approach to private predictions and we hope that -- as with other approaches to privacy -- future research will improve our bounds and reduce this overhead.

To reduce this we highlight the tightness of our smooth sensitivity bounds depends on the tightness of the local sensitivity bound and the number of values of k at which AGT is run for. Given sufficiently tight bounds on the local sensitivity (e.g., with future advancements), running AGT for even a single value of k may be sufficient to realise significant privacy benefits. Tighter bounds and careful choice of k values will be a direction for future work. Similarly, particular models may have tighter local sensitivity bounds (i.e., particular architecture or learning choices) may also be valuable directions of study.

• Interval bound propagation (IBP) ... may be sensitive to the choice of activation functions and loss functions.

One benefit of our proposed approach is that any bound propagation technique (e.g., one chosen to match the model) can be used to tighten our bounds. his will also be a future direction of work to tighten bounds in particular cases.

• It is not entirely clear how sensitive the performance is to choices like batch size, number of epochs

In the current version of our submission we highlight that batch size is typically taken to be the maximum possible size as this results in the tightest bounds. In a revised version we will include an ablation of the batch size in Appendix E.

• More explicit comparisons with the smooth sensitivity framework introduced by Nissim et al. (2007), ... Wong and Kolter (2018) ...Tjandraatmadja et al. (2020)

Our approach to tightened privacy explicitly uses the framework of Nissim et al. (2007); however, adapting our approach to further developments in local DP is an important future work. With regards to further convex relaxations, our framework is general and can use any propagation method. We thank the reviewer and will clarify this and we add references to the works the reviewer mentions.

• There are a few papers that I feel the authors might have missed in this area, [1] ... and [2].

We do have citation of [1], however, we are aware that there are multiple versions online, though each has the same theoretical framework that we reference and use extensively. We did not cite [2] and will do so in a revision of our submission.

• Might the element wise clipping have a different bias-variance tradeoff ...?

Yes, the element-wise clipping may introduce different biases in the final model. The preliminary results in this paper, particularly Figure 5, highlight that we actually observe better utility than DP-SGD indicating that this is not substantial.

• Cauchy noice has been used ... advantages over Laplace noise?

Smooth sensitivity requires the use of an “admissible” noise distribution, each of which comes with its own theoretical privacy loss. Of these choices discussed by Nissim et al., only Cauchy noise satisfies pure (delta=0) differential privacy.

• ... quantify or characterise what level of data separability ... to provide meaningful advantages over global sensitivity approaches?

We thank the reviewer for the questions as it raises a very interesting point. We present Figure 3 which visualizes this phenomenon and in our GPT experiment we hypothesize that separability is the reason for the strong bounds. However, characterizing separability itself in a general way is non-trivial and therefore characterizing the relationship between our bounds and separability is also non-trivial and an interesting future work.

• Have any automatic approached been explored for selecting optimal k values ...?

Selecting optimal k values is a challenging problem with many potential heuristic approaches that may be effective in reducing the computational overhead of our method and may be explored in future works.

We thank the reviewer for their kind words and for the careful work of checking the proof and technical steps of our work. In their review they did not necessarily provide a strong signal of the weaknesses they would like to see addressed in relation to their score. We hope that both our response to other reviewers and promised updates that we have address any concerns that they may have such that they are confident in recommending acceptance.

We thank the reviewer for their time and consideration of our work.

• It is quite strange to not see a comparison with PATE. Indeed, this looks like one additional step of training student models on top of the experiment in Fig. 5.

Fig. 4 illustrates the privacy-utility tradeoff of our method compared to the subsample and aggregate mechanism employed by PATE. As a result, any gains in tightness of privacy analysis here directly translate into the privacy-utility costs of training subsequent student models using the PATE framework. While the comparison with DP-SGD in Fig. 5 would be more favourable following a student-teacher framework, this trade-off has been well studied in previous works. Further, this would require consideration of modified training settings, e.g. having access to an unlabelled public dataset. Nonetheless, we agree with the reviewer that understanding how the gains in our approach translate to improved trade-offs in student models is an interesting and potentially valuable future contribution. In this direction, we provide some preliminary results below, that will accompany a more thorough discussion in our appendix.

• I would be happy to increase my score if such results were available.

In a revised version of the paper, we will incorporate this discussion into the main text and reference an appendix section that presents preliminary results on applying our mechanism in a teacher-student training setting. Specifically, we re-run the experimental setup from Figure 5, using a privacy budget of (\epsilon, \delta) = (10, 10^{-5}) to label Q = 100 data points held out from the training dataset (which we assume to be our "public" unlabeled dataset). We emphasize that training a student model does fix the privacy budget and which privacy budget is selected will have a significant effect on the results. Once this is done, resulting teacher-generated labels are then used to train a student model. Our findings indicate that the student model's performance under each mechanism aligns with the accuracy levels observed at the corresponding inference budget in Figure 5. We hope this increases the reviewer's confidence in our contribution.

• Moreover, PATE also relies on smooth sensitivity (specifically, the 2018 version) and data-dependent privacy bounds.

We thank the reviewer for highlighting this variant of PATE that leverages tighter, data-dependent privacy analysis. We will be sure to cite it in the revised version of our submission. While we currently do not include comparisons with such methods, we highlight to the reviewer that the tightening approach introduced in our work is orthogonal to those used in subsequently developed PATE mechanisms. We emphasize that this suggests that our bounds could potentially be combined with these tighter privacy analyses to enable even stronger privacy guarantees. We are grateful for this insightful suggestion and will make it clear in our revision that more advanced mechanisms exist beyond those we evaluate, and that integrating our approach with them represents a promising direction for future research.