Certification for Differentially Private Prediction in Gradient-Based Training
Authors: Matthew Robert Wicker
Philip Sosnin
Igor Shilov
Adrianna Janik
Mark Niklas Mueller
Yves-Alexandre de Montjoye
Adrian Weller
Calvin Tsay
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Convex Optimization
Deep Learning
Primary area: social_aspects->privacy
TL;DR: We utilize novel bound propagation algorithms to upper-bound local sensitivity of machine learning predictions and leverage this bound for improved private prediction.

Abstract: We study private prediction where differential privacy is achieved by adding noise to the outputs of a non-private model. Existing methods rely on noise proportional to the global sensitivity of the model, often resulting in sub-optimal privacy-utility trade-offs compared to private training. We introduce a novel approach for computing dataset-specific upper bounds on prediction sensitivity by leveraging convex relaxation and bound propagation techniques. By combining these bounds with the smooth sensitivity mechanism, we significantly improve the privacy analysis of private prediction compared to global sensitivity-based approaches. Experimental results across real-world datasets in medical image classification and natural language processing demonstrate that our sensitivity bounds are can be orders of magnitude tighter than global sensitivity. Our approach provides a strong basis for the development of novel privacy preserving technologies.

Certification for Differentially Private Prediction in tradient-Based Training
Matthew Wicker 12 Philip Sosnin
Igor Shilov'
Adrianna Janik? 3 Mark N. Mueller Adrian Weller Calvin Tsay' !
Yves-Alexandre de Montjoye'
Abstract
Differential privacy (DP) has emerged as primary tool for understanding and mitigating the leakage of private user in- formation when deploying machine learning models (Dwork et al., 2006). Differential privacy provides probabilistic guarantee on the amount of information an adversary can ex- tract from model predictions or parameters (Ji et al., 2014). The most popularly deployed algorithm for achieving DP in machine learning is private training, e.g., with DP-SGD (Abadi et al., 2016), which privatizes the learning process such that the final model parameters come with DP guar- antee. Private training does come with some considerable drawbacks: privacy parameters must be fixed prior to train- ing, leading to potentially costly training re-runs, and DP training may bias model performance in unintended (and po- tentially harmful) ways, e.g., with respect to diserimination (Fioretto et al., 2022).
We study private prediction where differential pri- vacy is achieved by adding noise to the outputs of non-private model. Existing methods rely on noise proportional to the global sensitivity of the model, often resulting in sub-optimal privacy- utility trade-offs compared private training. We introduce novel approach for computing dataset- specific upper bounds on prediction sensitivity by leveraging convex relaxation and bound propa- gation techniques. By combining these bounds with the smooth sensitivity mechanism, we signif- icantly improve the privacy analysis of private pre- diction compared to global censitivity-based ap- proaches. Experimental results across real-world datasets in medical image classification and nat- ural language processing demonstrate that our sensitivity bounds are can be orders of magnitude tighter than global sensitivity. Our approach pro- vides a strong basis for the development of novel privacy preserving technologies.
One alternative to private training is private prediction, which achieves differential privacy by adding noise to the outputs of non-private model (Dwork & Feldman, 2018). Unlike private training, private prediction allows users to dynamically adjust their privacy budget depending on the privilege of the user or sensitivity of the application. Ad- ditionally, private prediction can be readily applied to even the most complex training configurations such as federated learning. Despite these appealing properties, current private prediction algorithms have been observed to have an em- pirically unfavorable privacy-utility trade-off compared to differentially private training (van der Maaten & Hannun, 2020). Yet, recent studies have concluded that the privacy analysis given by current private prediction algorithms can be substantially improved (Chadha et al., 2024).
1. Introduction
Modern machine learning systems have shown significant promise across diverse domains such medical imaging, autonomous driving, and sentiment analysis (Bommasani et al., 2021). The potential use of such systems in situations that require the use of human data for training has led to an increase in data privacy concerns (Song et al., 2017; Carlini et al., 2023). Ensuring that machine learning models meet rigorous privacy guarantees is a necessary prerequisite for responsible deployment (Gadotti et al., 2024).
In this work, we present a novel framework that enables tighter privacy analysis when employing private prediction. We observe that a primary source of looseness in private prediction the use of the global prediction sensitivity- the largest change in prediction between any two observable datasets-when privatizing model outputs. Our approach addresses this by using advances in non-convex optimiza- tion and bound propagation (Wicker et al., 2022) in order to compute upper-bounds on the local sensitivity of a given prediction. This involves computing the set of all reachable predictions when any arbitrary set of is points is added or removed from the provided dataset. Using our bounds on
"Equal contribution 'Department of Computing, Imperial Col- lege London, London, UK "The Alan Turing Institute, Lon- don, UK "Accenture Labs, Dublin, Ireland "Department of Com- puter Science, ETH Zurich, Zurich, Switzerland StaricStar.ai, Zurich, Switzerland Department of Engineering, University of Cambridge, Cambridge, UK. Correspondence to: Calvin Tsay <c.tsay @ imperial.ac.us ac.uk>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Certification for Differentially Private Prediction
Model Training
Trained Parameters
Model Predictions
Queries
(SGD)
Private
Privatized
Dataset
Predictions
Abstract Gradient
Parameter-Sye Bounds
Smooth Sensitivity
Training
Bounds
Triining Time
Inference Timee
Figure 1. Overview the approach (1) A model is trained using stochastic gradient descent. (2) AGT is used to compute parameter space bounds for up & arbitrary removals/additions the dataset. (3) A certification procedure is used to bound the smooth sensitivity of model prediction. (4) The smooth sensitivity is used to release the model prediction privately.
prediction's 's local sensitivity, we show that we are able to leverage bounds from smooth sensitivity (Nissim et al., 2007) to provide tighter guarantees of differential privacy compared with the standard approach of using the global sensitivity. Empirically, we compare our approach to private prediction with private training using DP-SGD (Abadi et al., 2016) and ensemble-based private prediction approaches similar to PATE (Papernot et al., 2016). We consider series of synthetic and real-world benchmarks including medical imaging and natural language processing. Across all tested datasets we find cases where our approach enables substantially tighter privacy analysis. We believe that this novel verification-centee framework represents promising avenue for tightening the privacy analysis of private predic- tion methods and for the development of new of privacy preserving technologies. In summary this paper makes the following contributions:
Yu et al., 2022). As a result, several works seek more spe- cific, and thus sharper, privacy guarantees. For example, Nissim et al. (2007) and Liu et al. (2022) use notions of local sensitivity to produce tighter bounds. In Ligett et al. (2017), the authors privately search the space of preeecciee parameters tune performance
given dataset, while in Yu et al. (2022) the authors propose individual differential privacy, which can compute tighter privacy bounds for given individuals in the dataset. Unlike this work, these rely solely on private training e.g.. DP-SGD (Abadi et al., 2016).
We consider private prediction where one is interested in privatizing the output predictions of model (Liu al., 2019). While PATE's noisy softmax may be interpreted in this light (Papernot et al., 2016), private prediction has been investigated largely in the context of learning theory (Bassily et al., 2018; Nandi & Bassily, 2020). In practice, it is found that training-ting -imen privacy such as DP-SGD is preferable to prediction-time privacy (van der Maaten Hamnun, 2020). However, recent audits have discussed significant lack of tightness in private prediction approaches (Chadha al., 2024). Our framework presents novel tightening of the privacy analysis of private prediction and, to the best of our knowledge, this work provides the first verification-centiic approach to private prediction which will hopefully enable even more progress in this direction. We detail further related works in Appendix A.
We provide a novel algorithm for bounding the reachable set of model parameters given a bound & on the num- ber of individuals that can be added/removed from the dataset. These bounds may be of independent interest to developing new privacy preserving technologies.
We use our bound on reachable model parameters bound the local sensitivity of any model prediction, and we prove necessary upper bounds on the smooth sensitiv- ity to provide tighter privacy analysis.
We validate our bounds with extensive experiments on variety of datasets from medical imaging and sentiment classification including fully connected, convolutional, and large language models. We find that our approach offers bounds that can be orders magnitude tighter than global sensitivity.
3. Preliminaries
3.1. Differential Privacy
Differential privacy has become widely recognized stan- dard that offers robust privacy guarantees for algorithms that analyze databases.
Definition 3.1 ((c, Diffferrnnti Privacy (Dwork al., 2014)). randomized mechanism M (e, d)diifferentially private if, for all pairs of adjacent datasets x, D and any S C Range(M).
2. Related Works
DP has enabled the adoption of trivacy-preseviing machine learning in a variety of industries (Dwork et al., 2014), yet post-hoc audits have revealed a gap between attacker strength and guarantees offered by DP (Carlini al., 2022;
P(M(x) ES) <cP(M() E ES)+ +
(1)
2

---

Certification for Differentially Private Prediction
In this work, we define distances between datasets using the Hamming distance d(æ; y), which equals the number of entries in which and y differ. Adjacent datasets are those where d(z,, y) = 1. The parameter e, known as the privacy budget, controls the privacy loss of M.
3.2. Private Prediction
The private prediction setting focuses on ensuring the pri- vacy of machine learning model's 's predictions. Specifically, this approach assumes that a potential adversary does not have direct access to the model itself but is limited to making a fixed number of queries, Q. to the model.
deterministic query f on a database x E 'D can be made differentially private by adding noise calibrated the sensi- tivity of the function.
We denote a machine learning model as a para- metric function f E - y/ with parameters E θ which maps from features E IK" to labels y E V We consider supervised learning in the classification setring with labeled dataset D = {(x!!() } The model parameters are trained, starting from some initialization 0' using a gradient-based algorithm, denoted as M, as = [f, D). In other words, given a model, initial- ization, and dataset, the training function M returns the "trained" parameters In this paper, we consider only the binary classification setting of y {0, 1), though the re- sults can be generalized to the multi-class setting.
Notation.
Definition 3.2 (Global Sensitivity (Dwork et al., 2014)). A function f :: + R" has global (l1) sensitivity
GS(F) max
[[(()) - f())l a.yd(aay/s
(2)
Relcasing the result of the query plus additive noise drawn from a Laplace distribution with scale Gf(f)/c satisfies (c,0) differential privacy. Although this mechanism en- sures differential privacy, the global sensitivity represents the worst case sensitivity over all datasets, which may not reflect the function's 's sensitivity at particular instance. Al- ternative measures of sensitivity have been proposed, such as the local sensitivity:
For a given query point x, the private prediction setting is concerned with releasing the prediction (M)) while satisfying Definition 3.1. For ease of exposition, we will use the shorthand f=(D) = f (x) to denote the prediction of the model at a point æ, where differential privacy must be ensured with respect to the training dataset D.
Definition 3.3 (Local Sensitivity (Dwork al., 2014)). For
J: + R,,, the local sensitivity at a point x: E D is
LS(f,>)=
max y:d(-.))11
[f(x) - f(yila
(3)
Prediction Sensitivity. To release the predictions of the model while preserving privacy, one can employ the follow- ing response mechanism. We assume a no-box setting, i.c., we take the output of the model, fz),,, be a binary label of the model's prediction. To privatize the response, one releases
Unfortunately, the local sensitivity is not itself private quantity and cannot be used directly to achieve differential privacy. However, Nissim et al. (2007) proposed a smooth upper bound on the local sensitivity that can be used to cali- brate noise while satisfying differential privacy. Formally, the maximum local sensitivity distance le is:
- {
if fa Lap(1/c) 0.5, otherwise.
R(x) =
(6)
Definition 3.4 (Maximum Local Sensitivity, (Nissim et al., 2007)). The maximum local sensitivity at a distance & is given by
This mechanism satisfies Definition 3.1, as the global sensi- tivity GS(fa) is equal to 1.
A², = max v) Sk
(4)
Subsample-and-Aggreet Aggregate. Subsample-and-aggrens mechanisms, such as the one employed by PATE (Papernot et al., 2016), are the current state-of-the-art in private predic- tion. In this setting, the data are partitioned into T disjoint subsets, with T models { trained separately on each subset. The models are then deployed as an ensemble voting classifier g with the following private aggregation mechanism,
We can now define the smooth sensitivity in terms of xf)
Definition 3.5 (Smooth Sensitivity, (Nissim et al., 2007)).
The 3-smooth sensitivity of a function f at a point x E is
SS (f.x)) = max e -Bk AkA*(())))
(5)
KEN
{ (n((x) + Lap (
g(x) = arg max
Taking directly from Nissim et al. (2007), the randomized algorithm that returns f(z) + Cauchy (6SS (f)z)/e) is
j
where (x) = Hi i e (T) = jil are the label counts for a class j. This response mechanism satisfies (c, diiffferret privacy.
(c, differrrrentlllllyy private' for B S c/6.
Foor a I-dimensional query f.
3

---

Certification for Differentially Private Prediction
Composition. For given inference budget of Q queries, the total privacy loss can be computed using composition theorems (Dwork et al., 2014). Standard composition states that the repeated application of Q (e. didiferernyy pri- vate queries satisfies (Qr, -6)-diffferential privacy. Ad- vanced composition allows the same queries to satisfy (e',8' + Q6) differential privacy, where d' > and e' /2Q In (1/8")e + Qe (ee (e-- 1). When Q is small, standard composition may yield smaller privacy loss than advanced composition. In our experiments, we choose the composi- tion theorem that results in the smallest privacy loss.
Formally, we wish to upper-bound the following optimiza- tion problem:
max Ilfa fa s.t. d(D, D') S k (8)
If the above problem is upper bounded by O, then we can con- clude that the prediction is stable at a distance k. However, optimizing over the space of all datasets D' is practically intractable. Rather than working in the space of datasets, we introduce the concept of valid parameter-space bounds, which enables efficient certification of the above optimiza- tion problem.
Definition 4.3 (Valid Parameter- Bounds). Let f be model trained on a dataset via a training algorithm M with parameter initialization O'. A domain T C ④ is said to be a valid parameter-spen spacce bound at a distance &s if and only if: Mf, 0' D') E T for all D' D') S k.
4. Methodology and Computations
In this section, we outline a novel framework, termed Ab- stract Gradient Training (AGT), for bounding the sensitivity of predictions made by trained machine learning model. Proofs of all theorems are given in Appendix D. In particu- lar, AGT uses reachability analysis of the training process to certify the following property:
This definition requires that the parameters obtained by training on a dataset D', located at a distance I k from D, must lie within the set T However, the converse does not hold, as T may over-approximate the true reachable parameter space.
Definition 4.1 (Prediction Stability). Let f be machine learning model trained on dataset D and queried at point x. The prediction (D) is said to be stable at a distance k if (l) - (D)Ill = O for all datasets D' with (D, k.
Using this definition we can shift the certification from rely- ing on computations over the set of all perturbed datasets to being over an (over-approximated) parameter-space domain T In particular we have:
Intuitively, this means that adding removing up to k entries in the training dataset cannot change the outcome of the prediction at the point x. Any distance k for which a prediction is stable implies the following result.
Lemma 4.4. For any valid parameter-space bounds T sat- isfying Definition 4.3, proving that v0 E T* [1 (x) fār(f.00' 00, .D) (x)]la = O suffices as proof that WD' D") S k, (.IMM....D'')))) - pMMs. (z))) 0.
Lemma 4.2. For any l satisfying Definition 4.1, the maxi- mum local sensitivity at distance of k is zero. That is, A (fz, D) = O.
While it is infeasible to bound (8) by working in the space of datasets, Lemma 4.4 defines corresponding properties that can be bounded straightforwardly starting with a parameter set T. Certifying for a given æ that (xx) is constant for any 0 T is discussed in more detail in Section 4.3.
In the remainder of this section, we first introduce the notion of valid parameter space bounds, and show how they can be used to certify whether given distance k satisfies Defi- nition 4. We then present an algorithmic framework for efficiently computing parameter-space bounds. In Section 5, we show how these results can be used to improve privacy accounting or performance in the private prediction setting.
4.2. Computing Valid Parameter-Space Bounds
This section presents the core of our framework: an algo- rithm that can compute valid parameter space bounds for any gradient-based training algorithm². We call this algorithm Abstract Gradient Training and present it in Algorithm 1.
4.1. Certification of Prediction Stability via Parameter Space Bounds
We start by introducing two assumptions. First, for expo- sitional purposes, we assume that parameter bounds T take the form of an interval: [0z, Bu] s.t. Vi, [0L]; S [0v]. This can be relaxed to linear constraints for more expressive parameter bounds at the cost of increased computational complexity. Second, we assume that the parameter initial- ization 0' and data ordering are both arbitrary, but fixed. The
Determining whether a prediction from a general machine learning model satisfies Definition 4.1 is a non-trivial task and may be computationally intractable for many classes of models. Instead, our focus is on soundly answering the question "Is the prediction (z) stable at a distance k?? Importantly, this approach allows us only to certify that the property holds for a given k; it does not enable us to conclude that the property fails to hold when certification is not possible.
Here we present AGT only for stochastic gradient descent, but our framework is applicable to other first-order training procedures, such as those based on momentum.

---

Certification for Differentially Private Prediction
Algorithm 1 ABSTRACT GRADIENT TRAINING FOR COMPUTING VALID TRAAMETER-SPACE BOUNDS
1: imput: [ model, 0' init. params.. D dataset, E epochs, a learning rale, k # of addittionsrremovals.. 7 clipping parameter.
output: nominal SGD parameter. (Oz, Ov] valid parameter space bound up to additions/removvls. // Initialize nominad parumeter and interval bounds.
3: 0 <- 0'; [0z, Ou] < [0',0'
4: for E-many epochs do
5: for each batch B C
D do
1
6:
AA
Σ
Clip, (f())))
II Compute the nominal SGD parameter update.
B
(E.))ER
7:
0
0
aAd
II Update the nominal parameter.
8:
Σ (2.0)E 9: Compute 20L, Adu s.t. 202 3 A0 3 AdV
AO
Clip, Vof (f) d( B) kk (02, 0ul
II Define the set of descent directions.
A2N E AO
// Compute bounds on the possible descent directions. // Update the reachable parameter interval.
10: 0r. < 02. addu; By + Bu aAo
end for
12:
end for
13:
return 9, (0,, 0vl
latter assumption on data ordering is purely an expositional convenience that is relaxed in Appendix D.3.
Theorem 4.6 (Bounding the descent direction). Given
nominal batch B {x((), } with batch size b, parameter set [O1, Ov) and clipping level y, the parameter update vector
Algorithm 1 proceeds by soundly bounding the effect of the worst-case removals and/or additions for each batch en- countered during training. We therefore have the following theorem, which is proved in Appendix D:
A
Σ
Clip, VoL (
B
Theorem 4.5. Given a model f, dataset D, arbitrary but fixed initialization, 0', bound on the number of added or removed individuals, k and learning hoper-parameter in- cluding: batch size b, number of epochs E., and learning rate a, Algorithm I returns valid parameter-space bounds on the stochastic gradient training algorithm, M, that sat- isfy Definition 4.3.
is bounded element-wise by
1
(0(1)
AO, = 1
SEMin b-k
sim1 kyld
1
(000 b-k
A0V i
SEMax
+ kylld
1=1
We note that the clipping procedure Clip,, in Algorithm is a truncation operator that clamps all elements of its input to be between -y and 7. while leaving those within the range unchanged. This is distinct from the f2-norm clipping typically employed by wwwccy-preserving mechanisms such as DP-SGD (Abadi et al., 2016). In this work, we chose to use the truncation operator as more amenable to Nound-propagation.
for any perturbed batch B derived from B by adding up to k and removing up to k data-points. The terms g(3) g66 are sound bounds that account for the worst-case effect of additions/eemovlls in any previous iterations. That is, they bound the gradient given any parameter 0" [11, Ou] in
the reachable set, i.e. 81 < <gt)) < <66) for all
800 E {Clli,, [o (
Ø 10 Brl)
The set AO = {- B) < k E [0,,0r]] (line 8) represents the set of all possible descent directions that can be reached at this iteration under up to l additions or re- movals from each batch. In particular, accounts for any removals from and/or additions to each previously seen batch (via valid parameter-space bounds), while repre- sents the effect of i removals/addition. from the current batch. Computing this set exactly is not tractable, so we instead compute an element-wise, over-approximated, lower and upper bound A0,, A0r using the procedure in Theo- rem 4.6. These bounds are then combined with 0z, fy using sound interval arithmetic to produce a new valid parameter- space bound.
The operations SEMax, and SEMin, in the above the- orem correspond to taking the sum of the element-wise top/bottom-a elements. These operations are discussed in more detail in Appendix D.4.
Computing Gradient Bounds. Many of the computations in Algorithm are typical computations performed during stochastic gradient descent. However, lines 8-9 involve bounding non-convex optimization problems. In particular, bounding the descent directions using Theorem 4.6 requires bounds 8(4) glt) on the gradients of a machine learning model f(x, 0) w.r.t. perturbations about We note that
5

---

Certification for Differentially Private Prediction
solving problems of the form min {- | x E [yg) has been well-studied in the context of adversarial robustness certification (Huchette et al., 2023; Tsay et al., 2021) with extensions that are applicable to our setting (Gowal et al., 2018; Wicker et al., 2020; 2022). All details of computing gradient bounds for neural network models using IBP can be found in Appendix B. This approach can also be generalized to cover non-neural network machine learning models.
times that of standard approaches.
Limitations. Algorithm I can derive valid bounds for the parameter space of any gradient-based based training algorithm. However, the tightness of these bounds depends heavily on the specific architecture, hyperparameters, and training process employed. In particular, the bound propagation between consecutive iterations assumes the worst-case ad- ditions and removals at every parameter index. As result, achieving meaningful guarantees with this method may ne- cessitate training with larger batch sizes or fewer epochs than usual. Moreover, some loss functions, such as multi- class cross-entropy. result in especially loose interval re- laxations. Consequently, AGT tends to provide weaker guarantees for multi-class problems compared to binary classification tasks, We anticipate that future developments in tighter bound puod-prooagttion methods, such as those lever- aging more expressive abstract domains, could address these limitations.
4.3. Algorithm Analysis and Discussion
Certification of Prediction Stability. Lemma 4.4 estab- lishes that once we have our parameter bounds (i.e., from Al- gorithm 1), we can bound (8) and therefore decide whether the given prediction is stable at a distance k. This is done by propagating the input x through the neural network with the interval from Algorithm 1 as the networks parameters (e.g., as in Wicker et al. (2020). which produces an interval over output space. It is then straightforward to compute the largest distance between elements of this output inter- val, or, in the case of classification, the largest change in the prediction, e.g., if the prediction changes (Gowal al., 2018). Following Lemma 4.4, these computations produce an upper bound on the optimization problem (8), which we will use for tighter privacy analysis in subsequent sections.
5. Improved Private Prediction using Smooth Sensitivity
The previous section outlined a framework for certifying whether a prediction from a model f at a point x is stable for up to i removals or additions to the training dataset. In this section, we outline how these certificates can be used to bound the smooth sensitivity, and improve the performance of private prediction mechanisms. Proofs of all theorems are given in Appendix D.
Computing the Maximum Stable Distance. As we will discuss below, finding any & for which Definition 4.1 holds suffices to improve the performance of private prediction mechanisms. However, the tightest privacy guarantees are obtained by computing the largest distance i satisfying Definition 4.1. Therefore, it seems that one must run Algo- rithm 1 for all & E {1..... DI], which incurs a significant computational cost. In practice, however, we find that the majority of the privacy benefits can be achieved with fewer than 10 runs of Algorithm 1. We explore this relationship further in Appendix C.
5.1. Prediction Sensitivity using Smooth Sensitivity
In this section, we describe how use certificates of pre- diction stability to upper-bound the smooth sensitivity of binary classifier f. In particular, we have the following result:
Computational Complexity. To analyze the time complex- ity of our algorithm in comparison to standard stochastic gra- dient descent (SGD), we focus on the operations described in Theorem 4.6. First, computing the gradient bounds (/ and 562 for each sample i in the batch using interval propa- gation requires at most four times the cost of regular training (see Appendix B). Once the bounds are computed, selecting the top bottom k gradient bounds has time complexity of (bb). where is the batch size. Thus, the time complex- ity for a single run of Algorithm 1 is a constant factor times the complexity of standard training.
Theorem 5.1. Let fz(D) denote the prediction of a binary classifier trained on a dataset D at a point x. If (D) is stable at a distance of W, then the following provides an upper bound on the B-smooth sensitivity:
SS SS& (fz, = -maxx E KEN+
-Ak A',, D) 8k'
(9)
To establish this result, we observe that A* D) is a monotonically increasing function of k and assumes values only in {0. 1). meaning it behaves as a step function with respect to k. Since the exponential term 99 is monoton- ically decreasing, their product achieves its maximum at k+ = mingk: A (Ja, D) = 1}. By Lemma 4.2, if k is sta- ble, then k > k' - 1. Consequently, the smooth sensitivity is bounded above by
Empirically, we observe that a single run of AGT incurs a wall-clock time that is 2-4 times that of regular training. As noted above, fewer than 10 runs of Algorithm I are generally sufficient achieve most of the privacy benefits, leading to total training and inference penalty of 20-40
For the detailed proof of Theorem 5.1, refer to Appendix D.
Theorem 5.1 is trivially satisfied when K' = 0, resulting
6

---

Certification for Differentially Private Prediction
Blobs
OctMNIST
IMDB
1.0
Accuracy
0.8
0.7
Non-private
0.6
Pred. Sens. (GS)
0.6
Pred. Sens, (SS)
0.5
10
10
10
10
10
10
10
10- 10
10
10a
10
Privary Loss per Query (e)
Figure Private prediction accuracy single model using global sensitivity vs our smooth sensitivity bounds.
in SS (fr. GS(fz). However, significantly tighter bounds on the smooth sensitivity can be achieved for any prediction certified as stable distance N' using Algo- rithm 1. These tighter bounds can then be leveraged to calibrate noise and release predictions through the follow- ing response mechanisms.
of the dataset D. Let 9z denote the (non-prite (non-private) ensemble aggregation function as defined in (11), queried at a point z. If the prediction of each classifier (() is stable at distance of k(0,, then:
AK (g =)
(12)
Corollary 5.2. Suppose prediction fD) is stable distance of W. Then, the following response mechanism satisfies (e, O)ddifferential privacy:
where K = EvEs, 1:19 + n - and Sn is the set of in- dices corresponding to the n classifiers with the smallest stable distances k(0, Here, distance between the vote counts.
[mn =n((=]] is half the
2
R(x) [1 fz)) + 0.5,
(10) Combining Corollary 5.2 and Theorem 5.3, we find that we can privatize the ensemble response function (11) adding noise drawn from a Cauchy (Geplyy@@xp(---ee cxxp(-eK/6//e distribu- tion.
otherwise,
where: 2 Cauchy (6 exp((ckk/6)//
When k' >> Corollary 5.2 enables substantial reduction in the noise added to predictions compared to mechanisms that rely global sensitivity.
5.2. Subsample and Aggregate using Smooth Sensitivity
In this section, propose private aggregation mechanism using the smooth sensitivity. As before, first partition the dataset into T disjoint subsets and train binary classifier (() on each. At any query point æ, we compute the (non- private) ensemble voting response g. defined as:
10
10
{
if ni (I)) 2 no(x)) otherwise
Smooth Sensitivity Bound
((x)
(11)
Figure 3. We use the "blobs" datasct to visualize our smooth sensi- tivity hounds for 1.0. The red line shows the model's decision boundary.
where (1) (i i (T], (x) j}l the label counts for a class
Consider the stable distance of the response g. In particular, we note that at least n (=)) votes must 2
6. Experiments
In this section, we present experimental validation of our proposed private prediction mechanisms, Comprehensive details on datasets, models, training configurations, and additional results can be found in Appendix E. We evaluate our approach across three binary classification tasks:
flipped cause the overall ensemble response g change. Suppose that each prediction (x)) is stable up to some distance k(() Then, the number of entries in the original dataset D that must be changed to cause n votes to flip at least the sum of the n smallest stable distances 166) Formally, we have the following result:
Blobs - Training a logistic regression on a "blobs" dataset generated from isotropic Gaussian distributions. Medical Imaging Fine-tuning the final dense layers of convolutional neural network to distinguish an unseen
Theorem 5.3. Consider an ensemble comprising T classi- fiers (0) 1, 1,..., each trained on disjoint subset

---

Certification for Differentially Private Prediction
Blobs
OctMNIST
IMDB
1.00
c= (= 1.00
Non-private
Subs. & Ags. (GS)
0.75
0.60
Subs. & Age. (SS)
Accuracy
0.60
1.00
0.70
0.75
0.00
0.50
0.50
0.50
10
20
30
50
20
40
10
30
50
Ensemble Size (T)
Figure 4. Private prediction accuracy as a function of ensemble size using global vs smooth sensitivity.
Blobs
OcLMNIST
IMDB
1.0
DP-SGD
A Accuracy
0.8
0.7
Subs. & Age (GS)
0.8
Pred. Sens. (GS)
0.6
Sube. Age (SS)
Pred. Seas. (SS)
0.5
10
10'
10
10
10a
10a
10
10'
10a
Inference Budget (Q)
Figure 5. Private accuracy as function of number of queries (Q) for a total privacy budget of (c, = (10.0, 10 10-9), An ensemble size
T 25 is used for both subsample and aggregate mechanisms.
diseased class in retinal OCT images.
argmax mechanism. However, as the ensemble size grows, the amount of data available each member decreases, re- sulting in Algorithm 1 yielding relatively weaker bounds for each individual member. This effect is somewhat mit- igated by the summation of certified stable distances in Theorem 5.3, causing our method's performance to remain relatively stable or degrade only gradually as ensemble size increases. Future work could address this limitation by incorporating tighter bound propagation procedures by proposing mechanism that takes advantage of our bounds only when they are tighter than global sensitivity.
Sentiment Classification Training neural network to perform sentiment analysis using GPT-2 embeddings of the IMDB movie reviews dataset.
Smooth Sensitivity Visualization. Figure 3 we plot our bounds on smooth sensitivity for two different datasets: one where the data are easily separable (left panel) and one where the data are overlapping (right panel). Given that bounds are dataset specific, find that our bounds smooth sensitivity generally suffer when the data are non- separable or when little data are available. We will observe these two factors throughout our experimental evaluation.
Comparison with Private Training. Finally, we com- pare the accuracy of our private prediction mechanisms to differentially private training (DP-SGD). Previous re- search has found that differentially private training generally achieves better privacy-utilit trade-off than private pre- diction (van der Maaten & Hannun, 2020). Consequently, private prediction is often reserved for tings, where only a limited number of queries are made to the Teacher model to conserve the privacy budget (Paper- not et al., 2016). This trend evident in Figure 5, which depicts model accuracy as a function of inference budget for fixed privacy loss. Private prediction performs well for a small number of queries and outperforms private train- ing OctMNIST and IMDB for fewer than 100 queries, but deteriorates rapidly as the number of queries increases. In the single-model setting, our smooth sensitivity bounds offer significant improvements over global sensitivity and
Tightening Private Prediction in a Single Model. Fig- shows the performance of the prediction sensitivity mechanism using both global sensitivity and smooth sensitivity bounds. We observe that our bounds can maintain noise-free accuracy levels for a privacy budget up to an order of magnitude lower than the accuracy obtained using global sensitivity. The effect is most pronounced when the data are separable ("Blobs") or when the dataset contains large number of training examples ("IMDB").
set-
Tightening Private Prediction in Ensembles. We illus- trate the performance of our proposed private aggregation mechanism in Figure 4. The plots show private accuracy for с = 1.0 (top) and c = 0.1 (bottom) as function of ensemble size. For smaller ensembles (T < 20), our mech- anism performs comparably to, or better than, the noisy
8

---

Certification for Differentially Private Prediction
using them increases the maximum number by order of magnitude compared with any other method on IMDB. Nonetheless, the highest accuracy is typically achieved with large ensembles using global sensitivity.
proach to other privacy settings (Jordon al., 2018; Yu et al., 2022). Additionally, highlight that advances in aggregation mechanisms in improved certification tech- niques may lead to even greater improvements when used in the framework we present.
Use In Teacher Models. While we focus on the setting of issuing private predictions, our tighter bounds may be used in the superviiee private learning setting proposed in PATE (Papemot al., 2016). To understand our approach in this setting we re-run the experimental setup from Fig- ure 5, using a privacy budget of (e, 6) = (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, result- ing saacher-generatee labels are then used to train student model. Our findings indicate that the student model's s per- formance under each mechanism aligns with the accuracy levels observed at the corresponding inference budget in Fig- ure 5, thus confirming that our bounds are effective in this setting. We highlight that this preliminary results could be strengthened and expanded by considering the combination of our approach with other tighter accounting approaches (Papernot et al., 2018; Malek Esmaeili et al., 2021).
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Abadi, M.. Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016.
Bassily, R., Thakkar, O., and Guha Thakurta, A. Model- agnostic private learning. Advances in Neural Information Processing Systems, 31, 2018.
Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosse- lut, A., Brunskill, E., et al. On the opportunities and risks foundation models. arXiv preprint arXiv:2108.07258 2021.
Table Performance of different teacher mechanisms across datasets.
Teacher Mechanism
Blobs
OctMNIST
IMDB
Single model, GS
82.8
12.7
54.4
Bourtoule, I.., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159. IEEE, 2021.
Single model, SS
99.8
18.7
73.5
Subsample & agg.. GS
99.5
14.1
73.0
Subsample & agg.. SS
98.1
19.8
71.7
DP-SGD
1.0
81.2
70.5
Carlini, N., Chien, S., Nasr, M., Song, S., Terzis, A., and Tramer, F. Membership inference attacks from first prin- ciples. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914. IEEE, 2022.
7. Conclusion
In this work, we propose a framework for computing valid bounds a machine learning model's parameters under the addition removal of up to k data points. By certify- ing prediction stability, we leverage these parameter-space bounds to derive upper bounds on the smooth sensitivity of model predictions. Our results demonstrate the use of our bounds in improving the performance of private predic- tion. This framework represents a foundational step towards developing new certification-butt based techniques for privacy preserving machine learning.
Carlini. N., Ippolito, D.,, Jagielski, M., Lee, K., Tramer, F., and Zhang, C. Quantifying memorization across neural language models. In The Eleventh International Confer- ence on Learning Representations, 2023.
Chadha, K., Jagielski, M., Papernot, N., Choquette-Chie C., and Nasr, M. Auditing private prediction. arXiv preprint arXiv:2402.09400, 2024.
Dwork, C. and Feldman, Privacy-preserving predic- tion. In Conference On Learning Theory, pp. 1693-1702. PMLR, 2018.
Future Directions. While in this work we establish the use of certification to improve privacy analysis, there are many important future directions to explore including the combination of certification with tighter aggregation mech- anisms (Papernot al., 2018) or the adoption of this ap-
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography

---

Certification for Differentially Private Prediction
Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284, Springer, 2006.
accuracy constrained erm. Advances in Neural Informa- tion Processing Systems, 30, 2017.
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3 (13-4):211-2 19:211-407, 2014.
Liu, A., Shen, X., Li, Z.,, Liu, G., Xu, J., Zhao, L.., Zheng, K., and Shang, S. Differential private collaborative web services qos prediction. World Wide Web, 22:2697-2720, 2019.
Fioretto, F., Tran, C., Van Hentenryck, P., and Zhu, K. Dif- ferential privacy and fairesss in decisions and learning tasks: A survey. arXiv preprint arXiv:2202.08/87, 2022.
Liu, X., Kong, W., and Oh, S. Differential privacy and robust statisties in high dimensions. In Conference On Learning Theory, pp. 1167-1246. PMLR, 2022.
Gadotti, A., Rocher, L., Houssiau, F., Crequ, A.-M., and de Montjoye, Y.-A. Anonymization: The imperfect sci- ence of using data while preserving privacy. Science Advances, 10(29):eadn7033, 2024.
Maas. A. L.. Daly, R. E., Pham, P. T.,, Huang, D., Ng, A. Y., and Potts, C. Learning word vectors for sen- timent analysis. In Proceedings of the 49th Anmual Meeting of the Association for Computational Linguis- tics: Human Language Technologies, pp. 142-150, Port- land, Oregon, USA, June 2011. Association for Com- putational Linguistics. URL http:://tt//ttt /tww:awwwww.......././....... org/
Gehr, T., Mirman, M., Drachsler- Cohen, D., Tsankov, P., Chaudhuri. S., and Vechev, M. Ai2: Safety and robustness certification of neural networks with abstract interpreta- tion. In 2018 IEEE Symposium Security and Privacy (SP), pp. 3-18. IEEE, 2018.
Malek Esmaeili, M., Mironov, I., Prasad, K., Shilov, I., and Tramer, F. Antipodes label differential privacy: Pate and alibi. Advances in Neural Information Processing Systems, 34:6934-6945, 2021.
Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovic, R., Mann, T., and Kohli, P. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.1221 2018
Müller, M. N., Eckert, F., Fischer, M., and Vechev, M. Certi- fied training: Small boxes are all you need. arXiv preprint arXiv:2210.0487/ 2022.
Guo, C., Goldstein, T., Hannun, A., and Van Der Maaten, L. Certified data removal from machine learning models. arXiv preprint
2019.
Nandi, A. and Bassily, R. Privately answering classifica- tion queries in the agnostic pac model. Algorithmic Learning Theory, pp. 687-703. PMLR, 2020.
Huang, Y. and Canonne, C. L. Tight bounds for ma- chine unlcarning via diffcrential privacy, arXiv preprint arXiv:2309.008: 00886, 2023.
Neel, S., Roth, A., and Sharifi-Malvajeee Malvajerdi, S. Descent-to- delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Huchette, J., Muñoz, G., Serra, T., and Tsay, C. When deep learning meets polyhedral theory: A survey, arXiv preprint ar 2xvv:2335.00244 2023.
Ji, Z.,, Lipton, Z. C., and Elkan, C. Differential privacy and machine learning: survey and review. arXiv preprint arXiv: 1412.744 2014.
Nguyen, T. T., Huynh, T. T., Nguyen, L., Liew, A. W.-C., Yin, H., and Nguyen, Q. V. H. A survey of machine unlearning. arXiv preprint arXiv:2209.02299, 2022.
Jordon, J., Yoon, J., and Van Der Schaar, M. PATE-GAN:
Nissim, K., Raskhodnikova, S., and Smith, A. Smooth
generating synthetic data with differential privacy guar- antees. In International Conference on Learning Repre- sentations, 2018.
sensitivity and sampling in private data analysis. In Pro- ceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 75-84, 2007.
Katz, G., Barrett, C., Dill, D. L., Julian, K., and Kochender- fer, M. J. Reluplex: An efficient SMT solver for verifying deep neural networks. Computer Aided Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I 30, pp. 97-117. 2017.
Papernot, N., Abadi, M., Erlingsson, U., Goodfellow, I., and Talwar, K. Semi-supervised knowledge transfer for deep learning from private training data. arXiv preprint 2016.
Papernot, N., Song, S., Mironov, I., Raghunathan, A., Tal- war, K., and Erlingsson, U. Scalable private learning with pate. In International Conference on Learning Represen- tations, 2018
Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, S. Z. Accuracy first: Selecting a differential privacy level for
10

---

Certification for Differentially Private Prediction
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D.,
Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj, A., Zhao, J., Cormode, G., and Mironov, I. Opacus: User- friendly differential privacy library in PyTorch. arXiv preprint arXiv:2 12298, 2021.
Rump, S. M. Fast and parallel interval arithmetic. BIT Numerical Mathematics, 39:534-554, 1999.
Yu, D., Kamath, G., Kulkami, J., Liu, T.-Y., Yin, J., and Zhang, H. Individual privacy accounting for differen- tially private stochastic gradient descent. arXiv preprint arXi::2206.02617 2022.
Sckhari, A., Acharya, J., Kamath, G., and Suresh, A. T. Re- member what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34: 8075-180866 2021.
Song, C., Ristenpart, T., and Shmatikov, V. Machine learn- ing models that remember too much. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp- 587-601, 2017.
Sosnin, and Tsay, C. Scaling mixed-intege program- ming for certification of neural network controllers using bounds tightening. arXiv preprint arXiv:2403.1785 2024.
Tsay, C., Kronqvist, J. Thebelt, A., and Misener, R. Partition- based formulations for mixed-integer optimiza- tion of trained ReLU neural networks. Advances in Neural Information Processing Systems, 34:3068-3080, 2021.
van der Maaten, L. and Hamnun, A. The trade-offs private prediction. arXiv preprint Stt:::2007.00089 2020.
Wicker, M., Huang, X., and Kwiatkowska, M. Feature- guided black-box safety testing of deep neural networks. In Tools and Algorithmms for the Construction and Anal- ysis of Systems: 24th International Conference, TACAS 2018, Held as Part of the European Joint Conferences Theory and Practice of Software, ETAPS 2018, Thessa- loniki, Greece, April 14-20, 2018, Proceedings, Part 24, pp. 408-426 Springer, 2018
Wicker, M., Laurenti, L., Patane, A., and Kwiatkowska, M. Probabilistic safety for Bayesian neural networks. In Conference on Uncertainty in Artificial Intelligence, pp- 1207. PMLR, 2020.
Wicker, M., Heo, J., Costabello, I., and Weller, A. Ro- bust explanation constraints for neural networks, arXiv preprint arXiv:22/2.08500 2022.
Xu, K., Shi, Z., Zhang, H., Wang, Y., Chang, K., Huang, M.. Kailkhura, B., Lin, X., and Hsieh, C. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 2020.
Yang. J.. Shi, R., and Ni, B. MedMNIST classification de- cathlon: A lightweight AutoML benchmark for medical image analysis. In IEEE 18th International Symposium on Biomedical Imaging (ISBI), pp. 191-195, 2021.

---

Certification for Differentially Private Prediction
A. Related Works
DP has enabled the adoption of privacy-preserving machine learning in a variety of industries (Dwork et al., 2014), yet post-hoc audits have revealed a gap between attacker strength and guarantees offered by DP (Carlini al., 2022; Yu et al., 2022). As result, several works seek more specific, and thus sharper, privacy guarantees. For example, Nissim al. (2007) and Liu et al. (2022) notions of local sensitivity produce tighter bounds. In (Ligett et al., 2017), the authors privately search the space of privacy-preservin authors propose individual differential privacy, which can compute tighter privacy bounds for given individuals in the dataset. Unlike this work, these rely solely on private training e.g., DP-SGD (Abadi et al., 2016).
parameters to tune performance on given dataset, while in (Yu et al., 2022) the
On the other hand, DP can additionally provide bounds in the setting of machine unlearning (Sekhari et al., 2021; Huang Canonne, 2023). In such cases, is more likely that guarantees are not tight due to the assumption that individuals can be both added and removed, rather than just removed (Huang & Canonne, 2023). The gold standard for unlearning (which incurs error) is retraining. Yet. keeping the data on hand poses a privacy concern (Dwork et al., 2014), and retraining can be prohibitively costly (Nguyen et al., 2022). If one admits the privacy cost of storing and tracking all data, then retraining costs can be limited (Bourtoule et al., 2021). Existing unlearning without retraining are either restricted to linear (Guo et al., 2019) or strongly convex models (Neel et al., 2021).
The privacy setting most similar to the one adopted in this paper the differential private prediction setting where we are interested in only privatizing the output predictions of a model (Liu et al., 2019). The PATE method may be interpreted in this light (Papernot al., 2016), but largely this setting has been investigated in the context of learning theory (Bassily et al., 2018; Nandi & Bassily, 2020). In practice, it is found that training- time privacy such as DP-SGD is preferable to prediction time privacy (van der Maaten & Hannun, 2020). This work can be viewed as proving tighter bounds on the private prediction setting, which allows private prediction to display some benefits over training-time privacy.
The approaches that are computationally similar to the framework established in this paper come from adversarial robustness certification (Katz et al., 2017: Gehr et al., 2018) or robust training (Gowal al., 2018; Müller et al., 2022). These approaches typically utilize methods from formal methods (Katz et al., 2017: Wicker et al., 2018) or optimization (Huchette et al., 2023; Tsay al., 2021). Most related to this work are strategies that provide guarantees over varying both model inputs and parameters (Wicker et al., 2020; Xu et al., 2020), as well as work robust explanations that bound the input gradients of a model (Wicker et al., 2022). Despite some methodological relationships, none of the above methods can apply to the general training setting without the proposed framework and are unable to make statements about differential privacy.
B. Interval Bound Propagation
In this section, we provide details of the interval bound propagation procedure required to compute the gradient bounds required by Theorem 4.6 in the context of neural network models. We define neural network model fd Ro R with K parameters 0 = {(W(), b60)) to be a function composed of K layers:
{(k) (1)
(x-)) + +0(), 2(0) =0 (2())
where (0) = x, (z) = 2(x), and a is the activation function, which we take to be ReLU.
The standard back-propagation procedure for computing the gradients of the loss L w.r.t. the parameters of the neural network is given by
dc 12 = (W(())
T dc
kg(h) = H (3(h)
OC
dc 0z(k)
O
dc OC
(2(t-1))
OC dL
aW(K) 0g(k)
Ob(kk 02(k)
where H.()) is the Heaviside function, and o is the Hadamard product.
12

---

Certification for Differentially Private Prediction
Interval Arithmetic Let denote intervals matrices A := [uL C Raxm such that for all A An A S Av. We define the following interval matrix arithmetic operations:
Addition: A B A C B BA B
AAA A, B B Elementwise mul.: o B [A O B| AA
Matrix mul.: A E A & B
Each of these operations be computed using standard interval arithmetic in at most 4x the computational cost of its non-interval counterpart. For example, interval matrix multiplication can be computed efficiently using Rump's 's algorithm (Rump, 1999). We denote interval vectors as := [az, au] with analogous operations.
We will now describe the procedure for propagating intervals through the forward and backward passes of a neural network to compute valid gradient bounds.
Bounding the Forward Pass Given these interval operations, for any input x E x and parameters ((k) E W()) ((k) b == 1...., K, we can compute intervals
(k)
W (k)
(k-1) ((b), =(x) = (2(k))
(((()))
such that (x) (K)) The monotonic activation function is applied element- wise to both the lower and upper bound of its input interval to obtain valid output interval. Here we consider only neural networks with ReLU activations, although the interval propagation framework is applicable to many other architectures.
Bounding the Loss Gradient Since we are in a classification setting, we will consider a standard cross entropy loss, Given the output logits of the neural network, {(K) = (x)) the categorical cross entropy loss function is given by
C (2()) = Σ Mi log Ps
where
Σ exp (2( - 2(()))
=
the output the softmax function and y a one-hot encoding of the true label. The gradient of the cross entropy loss with respect to ((K) is given by
ac (2(K),))
0z(K)
p
The output of p softmax(2(K)) given any {(K)
((( (K)
is bounded by
2
[PL.;
Eexp
exp
[22K3]]
[S(K)]
I.)
1
[Pr],
Σ exp
[[8/0]]
[
Therefore, an interval over the gradient of the loss L with respect to {(K) is given by
ac (2, v)
[PL - y.Pu - yl
02
13

---

Certification for Differentially Private Prediction
Bounding the Backward Pass Wicker al. (2022) use interval arithmetic bound derivatives of the form OC/0z(0) and here extend this additionally compute bounds on the derivatives w.r.t. the parameters. Specifically, we can back-propagate /C/80 /C/02(K) (computed above) to obtain
ac
ac
(W(L))
(2
(2))
(2(h) H (x(K)
0C
dc
0z(k)
0C
0C
(2(1-1)) T
OW(k)
(g(k)
ac ac
ab(k) (g(k)
where H-) applies the Heaviside function to both the lower and upper bounds of the interval, and o is the Hadamard product. The resulting intervals are valid bounds for each partial derivative, that is
Oc OW(K)
Oc Oc ac
(W))) 0b(k) Ob(k)
for all W(k (kk), ((0) ((k) and I,.....A K.
C. Bounding the Smooth Sensitivity
Test Set Sensitivity
1.00
Avg. Smooth Sensitivity
0.75
Global sensitivity
0.50
0.25
10
20
30
40
50
Number of & values, ICI
Figure 6. Effect of KC] the tightness of the smooth sensitivity bound for the GTP-2 sentiment classification task (e 1.0).
Theorem 5.1 provides a procedure for bounding the smooth sensitivity of binary classifier f queried at point Specifically, any k for which the prediction fa is certified to be stable provides an upper bound on the smooth sensitivity (S D) I e-0k", It is clear that the tightest upper bound obtained by certifying the prediction to be stable for the largest possible k'. Therefore, we employ the following procedure for finding the largest stable using AGT:
1. Choose a set of values = {k and compute the corresponding parameter-space bounds using Algorithm 1.
2. At query point x, find the largest k K. for which (D) is stable (e.g. via binary linear search).
The set IC should be chosen according to the available computational budget. A more fine-grained set of k's will achieve tighter sensitivity bounds, as will fall closer to k*, on average. On the other hand, increasing the number values increases the computational complexity both training time (running Algorithm 1 for each k) and inference time (finding K' via binary search).
In practice, the set K. should be chosen with greater density for smaller values of k; as the improvement in the tightness of the bound is more pronounced for lower values of & due to the exponential decay. Specifically, going from k' = to K' = 2 results in a significantly greater improvement than, for example, refining the bound between A'' 51 and k' = 52.
Furthermore, for sufficiently large values of k; it is often the case that the resulting bounds do not certify any points within the domain, rendering the inclusion of such large values unnecessary. Consequently, is advantageous to prioritize smaller
14

---

Certification for Differentially Private Prediction
k values in the K. where the improvement in the bound is substantial, while avoiding the inclusion of excessively large values that offer diminishing returns both in terms of bound improvement and computational efficiency.
Figure 6 illustrates how increasing the number of k values affects the tightness of our bounds. Even when KC] = 1 (i.e., AGT is run for single value of k), the smooth sensitivity bound is already tighter than the global sensitivity. As the number of k values increases, the smooth sensitivity bound becomes progressively tighter. However, after [K] R 10, the gains diminish, indicating that running AGT for a small number of values is sufficient to capture most of the privacy benefits.
D. Proofs
D.1. Proof of Lemma 4.2
Proof. Suppose Ak-1(fa, D) > 0. Then, by the definition of 1 BY: d(D, k with LS(f,, > 0. This implies By the triangle inequality, we have
A. " (1,100 - Jx(Y")ll > 0.
(13)
d d(D d(D,Y) d(Y,Y') s k.
(14)
Since both Y, Y' are a distance I k from D. we have that fD(D) = fz(Y) = f2(Y') by Definition 4.1. Therefore, IV - f+(Y)) = 0, which is contradiction.
D.2. Proof of Lemma 4.4
Proof. Let
v0 E TK (1) -
(2..0 (ML =0.
(15)
Now, suppose there exists a dataset D' such that d(D, D') I l and ('MU,...'' - pMiso (M))) > 0. By Definition 4.3, the parameters of the model trained on D' must lie within the valid parameter space bounds T i.e. M(f. H¹ D') E T However, this would contradict (15), as it requires (f - fa = 0 for all E T Therefore, (15) suffices as proof that [ ( (x) - fM (z)]l1 = 0 for all D' d(D, s k.
D.3. Proof of Theorem 4.5
Here we provide a proof of correctness for our algorithm (i.e., proof of Theorem 4.5) as well as a detailed discussion of the operations therein.
First, we recall the definition of valid parameter space bounds (Detinition 4.3 in the main text):
0
< min M(f,0' 0' D'); s M(J,0', D); S max M(f,0' 0' D'), s g D'ET(D)
(16)
D'E
As well the iterative equations for stochastic gradient descent:
0- 0 aAd,
A
VoL (F)(()))
(17)
B
(2:8)BB
For ease of notation, we assume fixed data ordering (one may always take the element-wise maximuns/minimums over the entire dataset rather than each batch relax this assumption).
Now, we proceed to prove by induction that Algorithm 1 maintains valid parameter space bounds on each step of gradient descent. We start with the base case of 0z = d² = 0' according to line 1, which are valid parameter-space bounds. Our inductive hypothesis is that, given valid parameter space bounds satisfying Definition 4.3, each iteration of Algorithm I (lines 4-8) produces a new 0² and 8 that satisfy also Definition 4.3.
First, we observe that lines 4-5 simply compute the normal forward pass. Second, we note that lines 6-7 compute valid bounds the descent direction for all possible poisoning attacks within T(D). In other words, the inequality AOL < AO < A holds element-wise for any possible batch B E T(D). Combining this largest and smallest possible update with the smallest and largest previous parameters yields the following bounds:
gb AA < aAd < 8 A44
15

---

Certification for Differentially Private Prediction
which, by definition, constitute valid parameter-space bounds and, given that these bounds are exactly those in Algorithm have that Algorithm provides valid parameter space bounds as desired.
D.4. Proof of Theorem 4.6
Proof. The nominal clipped descent direction for a parameter is the averaged, clipped gradient over a training batch B, defined as
AO = Σ Clip, ((0)
where each gradient term is given by 8(1) VoL (fo (z(1) ,)))) Our goal is to bound this descent direction for the case when (up to) & points are removed or added to the training data, for any & E [01. fu]. We begin by bounding the descent direction for fixed, scalar 0, then generalize to all 0 & [O,, 0v) and to the multi-dimensional case (i.e., multiple parameters). We present only the upper bounds here; analogous results apply for the lower bounds.
Bounding the descent direction for a fixed, scalar 9. Consider the effect of removing up to it data points from batch B. Without loss of generality, assume the gradient terms sorted in descending order, i.e., 5(1) 2 8(2) the average clipped gradient over all points can be bounded above by the average the largest b i terms:
8(0) Then,
k
A# Σ
Clip
[00]
E
Clip, (00)
This bound corresponds removing the k points with the smallest gradients.
Next, consider adding l arbitrary points the training batch. Since each added point contributes most y due clipping, the descent direction with up to k removals and & additions is bounded by
Clip,
(
Clip, 8(0)
1 S
ky
Σ Clip,
[oro)
where the bound now accounts for replacing the j smallest gradient terms with the maximum possible value of from the added samples.
Bounding the effect of a variable parameter interval. We extend this bound to any 0 E 10z, 0u]. Assume the existence of upper bounds 8l4 on the clipped gradients for each data point over the interval, such that
> Clip,, Vor (1(0))
0 E [0,, Ov)
Then, using these upper bounds, we further bound 20 as
A0 S ky + Σ
Clip,
b
where, as before, we assume o indexed in descending order.
Extending to the multi-dimensional case. To generalize to the multi-dimensional case, we apply the above bound component-wise. Since gradients are not necessarily ordered for each parameter component, we introduce the SEMax, operator, which selects and sums the largest n terms at each index. This yields the following bound on the descent direction:
A $
1
SEMax b-k
{ (86)
(50))
1
Jim i=1
+ kyld
which holds for any E [Oz, 0v and to k removed and replaced points.
We have established the upper bound on the descent direction. The corresponding lower bound can be derived by reversing the inequalities and substituting SEMax with the analogous minimization operator, SEMin.
16

---

Certification for Differentially Private Prediction
D.5. Proof of Theorem 5.1
Proof. We start by noting the following properties of the maximum local sensitivity of the prediction of binary classifier at point
^ (Fa, D)
LS(Ja, D))
(18)
D'd(DD.D)Sk
A* D) takes only values in {0, 1). since - e (0,
(fa, D) is monotonically increasing in
Therefore, (f2, D) takes the form of step function:
1 i
A (²,,,, D)
(19)
0 otherwise,
for some k* = min (Sa, D) = =1. We now relate this to the definition of 8-smooth sensitivity.
SS (J.. D) = max
0k A D)
max s(k)
(20)
KEN
kEN!
where
- if A*;
skk)
(21)
otherwise.
Note that the exponential term monotonically decreasing since B O. Therefore, the maximum value s(k) is attained k*, giving SS (fz, D) = - Now, we have that
vi: s SS (),,D)= = - 3K*
S -e- Bk
(22)
Suppose the prediction fz (D) is stable at a distance V. By Lemma 4.2, this tells us that D) = Therefore, 1s* K' - K- 2 K'. By (22), this gives us the following valid upper bound
S D) Bk" ee-ak 9K
(23)
D.6. Proof of Corollary 5.2
Proof. We recall from Section 3 the following response mechanism for 1-dimensional query fz(D):
If 3 e/6, the algorithm that returns (z) + Cauchy (6SS is (e, O)ddifferretially private.
We note that any upper bound on SS D) can be used in place of the true smooth sensitivity, as increasing the scale of the noise cannot degrade the privacy of the mechanism. By Theorem 5.1, if (D) is stable for some distance k', then 8 (fz, D) & e-Bk', Setting to its maximum value in the above mechanisms, and substituting our bound gives that (D) + Cauchy (Sexp(-ak)) ck//6) satisfies (c, difffrerett privacy.
D.7. Proof of Theorem 5.3
Proof. Let g be a non-private voting ensemble made up of T'' binary classifiers f(i,, i = 1,..., T' each trained on disjoint subsets of the dataset D. We assume that each binary classifier prediction at the point æ is stable to some distance k(0) We define the binary vote counts at a query point x as
no(x) = (i:iE (L,...,T},,(( 0H
(24)
ni ni(x) (i:iE (1....,
(25)
17

---

Certification for Differentially Private Prediction
such that n1(x)) my (x)) T. Let the response of the ensemble classifier trained on the dataset D at the point x be
(x( {
if f1 2 (2 if mz) < no(2)
(26)
We wish to lower bound the distance for which ds is stable with respect to additions removals from the dataset D.
The number of votes that must be flipped to cause IR to change is given by n = In. [=)(a)=no=x)
i.e. at least half the distance
between the vote counts, Now consider the number of additions or removals from D that is required to cause least n votes to flip.
Since each individual classifier f()) is stable at distance of k((t, an adversary has to modify at least K = Eies, 1: entries of D to cause n votes to flip. Here S, is the set of indices corresponding to the n classifiers with the smallest stable distances k(())
This suffices as a proof that gs is stable a distance of K. Additionally, by Lemma 4.2, (D) being stable a distance of K implies
A (gz: D) 0.
(27)
E. Experimental Details and Further Results
In this section, we provide the full experimental details for the results Section 6. All experiments are run on a server with 2x AMD EPYC 9334 CPUs and 2x NVIDIA L40 GPUs. Code reproduce our experiments is available at [redacted for anonymity]. Where stated, all DP-SGD (c, 5) values computed using the Opacus libary (Yousefpour et al., 2021).
For each dataset, we provide the number of epochs, learning rate (ax), learning rate decay factor (r)), and batchsize (b). Learning rate decay is applied using standard learning rate schedule a, = a/(1 + mpn).
E.1. Blobs Dataset
In Figure 3, we examine dataset consisting of 3,000 samples drawn from two distinct isotropic Gaussian distributions. The objective is to predict the distribution of origin for each sample in a supervised learning task. To highlight the dataset- dependent nature of our bounds, we vary both the cluster means and standard deviations. We train a single-layer neural network with 128 hidden neurons using AGT and visualise the resulting smooth sensitivity bounds. The model trained for four epochs with hyperparameters set to b = 3000, a = 1.0, 1) = 0.6, and y = 0.06. A full set of bounds is computed for values of in K [l...., 100}. As discussed in Appendix C, running the complete range of l values is unnecessary for achieving privacy gains; carefully selected subset would be preferable in practical applications. Using these privacy bounds, we determine the maximum stable A** IC for each point in grid over the domain. This value is then used to compute a bound on the smooth sensitivity, which we present as heat map.
In Figures 2, 4, and 5, our goal is to use the smooth sensitivity bounds computed above to improve private prediction in both the single model and ensemble settings. Here we use the "separable" blobs dataset with 5000 samples and train a logistic regression classifier. To facilitate tight bound propagation, we use the maximum batchsize of 5000/7 / for each of the T' members of the ensemble and other hyperparameters the same as the above. We apply the global sensitivity or smooth sensitivity mechanisms to the same nominal models/ ensembles.
E.2. Retinal OCT Image Classification
Next, we consider another dataset with larger scale inputs: classification of medical images from the retinal OCT (OetMNIST) dataset of MEDMNIST (Yang al., 2021). We consider binary classification over this dataset, where a model is tasked with predicting whether an image is normal or abnormal (the latter combines three distinct abnormal classes from the original dataset).
The model comprises two convolutional layers of 16 and 32 filters and an ensuing 100-node dense layer, corresponding to the 'small' architecture from (Gowal et al., 2018). To demonstrate our framework, we consider a base model pre-trained on public data and then fine-tuned on new, privacy-sensitio data, corresponding to the 7754 Drusen samples (a class of
18

---

Certification for Differentially Private Prediction
1.0
Proportion of Stable Predictions
0.1
0.88
0.88
0.84
0.8
0.76
Accuracy
0.6
0.56
0.5
0.4
7=
0.2
7=
4.0
7
2.0
0.2
Pre-trained accuracy
0.0
50
100
200
4.0
2.0
1.0
0.5
0.1
Distance (k)
Clipping Level (7)
Figure 7. Performance of the fine-tuned classifier on the unseen diseased class (Drusen). Left: Proportion of the test set queries certified to be stable a distance of k. Performance on new diseased class OCT-MNIST Fine-Right: Prediction accuracy on the Drusen class.
abnormality omitted from initial training). First, we train the complete model excluding this using standard stochastic gradient descent. We then fine-tune only the dense layer weights to recognise the new class, with a mix of 50% Drusen samples per batch. We aim to ensure privacy only with respect the fine-tuning data. The hyper-pul apeer-paraettrss used for fine-tuning using AGT are E = 4, 0.06, 17 0.5; the batchsize chosen to be the maximum possible for each ensemble size T.
Figure shows the performance of the fine-tuned classifier on the (previously unseen) Drusen class. The pre-trained model achieves around 50% on the new disease (i.e. akin to random guessing). After fine-tuning, the accuracy on the Drusen data ranges from approximately 0.6 up to 0.88 after fine-tumm ane-tuning. The final utility is highly dependent on the value of the clipping level 7. Decreasing the value of y reduces the accuracy of the model, but increases the proportion of points for which we can provide certificates of stability. In our experiments in the main text, we choose value of y 1.0, trade-off between utility and certification tightness. We note that for small values of k, framework is able to provide certificates of prediction stability for well over 90% of test-set queries.
E.3. IMDB Movie Reviews
Finally, consider fine-tuning GPT-2 (Radford al., 2019) for sentiment analysis the large-scale (40,000 samples) IMDb movie review dataset (Maas et al., 2011). In this setup, we assume that GPT-2 was pre-trained on publicly available data, distinct from the data used for fine-tuning, which implies no privacy risk from the pre- trained embeddings themselves. Under this assumption, we begin by encoding each movie review into f68-dimensional vector using GPT-2's embeddings.
Proportion w/ Guarantees
1.0
k 10
[+ Accuracy)
0.8
0.6
0.4
k: 50
0.2
Nominal accuracy
k: 100
0.0
30
40
50
We then train a fully connected neural network consisting of x 100 nodes, to perform binary sentiment classification (positive vs negative reviews). Figure shows how the nominal accuracy and the proportion of certified data points evolve over the course of training. Although the initial accuracy is equivalent to random chance, fine-tuning allows us to reach an accuracy close to 0.80, while simultaneously preserving strong privacy guarantees using AGT. Each training of the sentiment classification model with AGT takes approximately 55 seconds, compared to 25 seconds when using standard, un-certified, training in pytorch. We note that guarantees weaken with increased training time, indicating that stronger privacy guarantees can be obtained by terminating training
Training Iteration
Figure 8. Proportion set queries certified be stable at distance of & for the IMDB sentiment classi- fication task.
early. In our experiments in the main text we choose to train with hyperparameters E 3, a 0.2, n = 0.5, y = 0.04, using the maximum possible batchsize available to each ensemble member.
19

---

Certification for Differentially Private Prediction
E.4. Additional Ablations: American Express Default Prediction
In order to understand the performance of Algorithm I in deeper net- works, turn the American Express default prediction task. This tabular dataset comprising 5.4 million total entries of real customer data asks models to predict whether customer will default on their credit card debt. We train networks of varying depth with each layer having 128 hidden nodes. We highlight that fully connected neural networks are generally not competitive in these tasks, thus their ac- curacy is significantly below competitive entries in the competition. However, this massive real-world dataset in privacy-critical domain enables us to test the scalability of our approach. In particular, we note in Section 4.3 that as batch size tends to infinity, our bounds become arbitrarily tight. On the other hand, since we employ interval bound propagation to bound the model gradients in Algorithm 1, our bounds weaken super-linearly as they propagate through deeper networks (Wicker al., 2020).
10
Batch Size
10
1
2
4
Network Depth
Figure 9. Minimum batch size required provide certin- cates of prediction stability at distance of & 50 for least 95% of AMEX test data.
Figure 9 shows the smallest batch sizes that allow to train networks of varying depth with guarantees of prediction stability at distance of k 50 for at least 95% of test set inputs. Our approach requires batch size of over one million to provide these guarantees for 4-layer neural networks. Ignoring the effect of this large batch size performance for the sake of this particular case study, this example highlights that tightly bounding the model gradients, c.g., though bounds-tightening approaches (Sosnin& Tsay, 2024), will prove an important line of future research.
'See www. www.kaggle e. com/ compet wttpeeeittiioosaeeedeeeee t- ion/: accessed 05/2024
20


Reviews:
[{"review_id": "L7kOMtMYBF", "reviewer": "Reviewer_dcek", "summary": "The paper proposes to bound local sensitivity of predictions of models learned with gradient-based methods using interval bound propagation. Further, the paper uses the result to construct a sample-and-aggregate procedure for prediction ensembles. The paper then demonstrates that using the proposed bounds enables to significantly improve utility for the same query budget over global sensitivity.\n\n## Update after rebuttal\n\nI strongly suggest to quantitatively compare the data-dependent bounds obtained with IBP and the standard data-dependent bounds for report-noisy-max from Papernot et al., 2016, 2017, key baseline data-dependent analyses not compared to in the current version.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and consideration of our work. \n\n* 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. \n\nFig. 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.\n\n* I would be happy to increase my score if such results were available.\n\nIn 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.\n\n| Teacher Mechanism                           | Blobs | OctMNIST | IMDB |\n| ------------------------------------------- | ----- | -------- | ---- |\n| Single model, global sensitivity            | 82.8  | 12.7     | 54.4 |\n| Single model, smooth sensitivity            | 99.8  | 18.7     | 73.5 |\n| Subsample and aggregate, global sensitivity | 99.5  | 14.1     | 73.0 |\n| Subsample and aggregate, smooth sensitivity | 98.1  | 19.8     | 71.7 |\n| DP-SGD                                      | 1.0   | 81.2     | 70.5 |\n\n\n* Moreover, PATE also relies on smooth sensitivity (specifically, the 2018 version) and data-dependent privacy bounds. \n\nWe 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.", "claims_and_evidence": "The claims are well supported by theory and experimental evaluation.", "methods_and_evaluation_criteria": "The experimental settings in the paper make sense to show that the proposed local sensitivity framework outperforms global sensitivity in single-model private prediction and ensemble prediction.\n\nConsidering that PATE is mentioned several times as a motivation for the ensemble setting, 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. Moreover, PATE  also relies on smooth sensitivity (specifically, the [2018 version](https://arxiv.org/abs/1802.08908)) and data-dependent privacy bounds. The present paper does not seem to compare the bounds obtained with IBP to these standard simpler bounds, only comparing with global sensitivity. This seems to be a significant drawback in the evaluation setting. I would be happy to increase my score if such results were available.", "theoretical_claims": "To the best of my understanding, the claimed results seem correct, given the IBP propagation bounds are correctly applied.", "experimental_designs_or_analyses": "See the \"Methods and Evaluation Criteria\" section.", "relation_to_broader_scientific_literature": "The paper introduces a new way of computing local sensitivity applicable to machine learning by using interval bound propagation. This establishes a new intersection between adversarial robustness certification and differential privacy.", "essential_references_not_discussed": "The [2018 version of PATE](https://arxiv.org/pdf/1802.08908) also uses smooth sensitivity. To be completely well-positioned with respect to the prior work on private prediction in machine learning, the paper should (1) compare the IBP bounds to PATE data-dependent bounds, and (2) have a new experiment comparing student-teacher pipeline when using the proposed approach and the PATE approach.", "other_strengths_and_weaknesses": "Connecting the literature on adversarial robustness certification and DP is valuable, and might be an avenue for a fruitful future direction of research.", "other_comments_or_suggestions": "- L693: GTP -> GPT\n- Fig 2 and 3 have a different order than referenced in the text.", "questions_for_authors": "---", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7hGhiqdPEz", "reviewer": "Reviewer_BNAf", "summary": "This paper studies upper bounds on the sensitivity of prediction in machine learning models. By doing that, the paper presents tighter privacy analysis. After which, experimental results showing a wide improvement in the tightness of the privacy bounds.\n## update after rebuttal\nI raised my score to a 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.", "claims_and_evidence": "The claims are all clear and convincing.", "methods_and_evaluation_criteria": "The paper uses on multiple datasets, and the results show a large improvement in tightening the privacy predictions.", "theoretical_claims": "I checked the proofs and discussions in both the main paper and the appendices, and to the best of my knowledge, there are no issues.", "experimental_designs_or_analyses": "The experiments done are extensive and support the result of the paper. The experiments are sound.", "relation_to_broader_scientific_literature": "Privacy is a very important topic in real world scenarios, and offering tighter bounds and privacy prediction stability moves us a step closer to being able to deploy DP in more applications.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is well written and easy to read. The methods used are not the most novel, but the work has significance.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x1CTLgiSf5", "reviewer": "Reviewer_VLat", "summary": "This paper introduces a new approach for improving differential privacy in machine learning predictions. The authors propose a method to compute tighter dataset-specific upper bounds on prediction sensitivity by using convex relaxation and bound propagation techniques. Their approach called abstract gradient training analyses how model parameters change when data points are added or removed from the training set. By combining these bounds with smooth sensitivity mechanisms, they achieve significantly better privacy-utility trade-offs compared to methods based on global sensitivity. The authors evaluate their approach on medical images and sentiment analysis. The method allows users to dynamically adjust privacy budgets and works with complex training configurations like federated learning.\n\n## Update after rebuttal\n\nI originally recommended accept and had some non-urgent comments. The authors responded well to those and I kept my score (4).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and careful review of our work. \n\n* The authors claim that fewer than 10 runs of the AGT algorithm are ... sufficient ... [this] lacks a more systematic sensitivity analysis. \n\nWe 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. \n\n* The computational overhead (reported as 20–40× standard training) may limit the practicality ... any avenues or potential for reducing this?\n\nThe 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. \n\nTo 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.\n\n* Interval bound propagation (IBP) ... may be sensitive to the choice of activation functions and loss functions.\n\nOne 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.\n\n* It is not entirely clear how sensitive the performance is to choices like batch size, number of epochs\n\nIn 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.\n\n* More explicit comparisons with the smooth sensitivity framework introduced by Nissim et al. (2007), ... Wong and Kolter (2018) ...Tjandraatmadja et al. (2020)\n\nOur 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. \n\n* There are a few papers that I feel the authors might have missed in this area, [1] ... and [2].\n\nWe 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.\n\n* Might the element wise clipping have a different bias-variance tradeoff ...?\n\nYes, 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. \n\n* Cauchy noice has been used ... advantages over Laplace noise?\n\nSmooth 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. \n\n* ... quantify or characterise what level of data separability ... to provide meaningful advantages over global sensitivity approaches?\n\nWe 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.\n\n* Have any automatic approached been explored for selecting optimal k values ...?\n\nSelecting 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.", "claims_and_evidence": "- The authors claim that fewer than 10 runs of the AGT algorithm are typically sufficient to capture most privacy benefits. Although preliminary experimental results support this claim for the chosen tasks, the paper lacks a more systematic sensitivity analysis. The robustness of this claim in more diverse settings is not explored.\n- The computational overhead (reported as 20–40× standard training) may limit the practicality claims of the method despite the improved sensitivity bounds.", "methods_and_evaluation_criteria": "- The authors test on both imaging and natural language data, which demonstrates the versatility of the approach.\n- However, the experimental validation is limited to a few binary tasks. It remains unclear whether these tighter bounds extend practically to more complex models (e.g. deep multi-class networks) or larger scale real world applications. That remains more of a theoretical promise.", "theoretical_claims": "- The method development is thorough and mathematically grounded. However, many proofs are deferred to appendices with some key assumptions.\n- interval bound propagation (IBP) to compute gradient bounds, while innovative, may be sensitive to the choice of activation functions and loss functions. \n- Algorithm 1 is grounded, some proofs are deferred to the appendix which I checked and did not see any issues with", "experimental_designs_or_analyses": "While the experiments compare the proposed method against baselines across various privacy budgets and even examine ensemble size effects, the discussion of hyperparameter tuning is relatively brief. It is not entirely clear how sensitive the performance is to choices like batch size, number of epochs, or the precise method used for bound propagation.", "relation_to_broader_scientific_literature": "Overall, the paper provides a reasonably good discussion of how its contributions build on and extend prior work in both differential privacy and neural network verification. But a few areas could benefit from deeper contextualization. For example, more explicit comparisons with the smooth sensitivity framework introduced by Nissim et al. (2007) and with recent advances in multi-neuron convex relaxations for neural network verification e.g. Wong and Kolter (2018) and Tjandraatmadja et al. (2020)", "essential_references_not_discussed": "There are a few papers that I feel the authors might have missed in this area, [1] for the background of smoothness in privacy and [2] for inclusion in the discussion about inaccurate estimation in privacy. \n\n\n[1] Nissim, Kobbi, Sofya Raskhodnikova, and Adam Smith. \"Smooth sensitivity and sampling in private data analysis.\" Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. 2007.\n\n[2] Casacuberta, Sílvia, et al. \"Widespread underestimation of sensitivity in differentially private libraries and how to fix it.\" Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022.", "other_strengths_and_weaknesses": "Strengths: \n- The authors present a novel approach that bridges verification-based techniques with differential privacy theory\n- The work provides rigorous mathematical proofs and analysis throughout\n- The authors test their approach across various datasets and model architectures\n\nWeaknesses:\n- The method’s performance is sensitive to hyperparameter choices such as batch size and the number of training epochs. These dependencies, along with the assumption of a fixed data ordering, might restrict the practical applicability of the method in more dynamic training scenarios.\n- The method's effectiveness diminishes as datasets become less separable or when limited data is available, so potential fragility under challenging data conditions.\n- Some of the technical details of bound propagation and sensitivity certification might benefit from additional explanation but this is not a requirement.", "other_comments_or_suggestions": "- The operators SEMin and SEMax are only briefly described, a clearer definition would be better\n- PATE is also mentioned without description or definition", "questions_for_authors": "1. Might the element wise clipping have a different bias-variance tradeoff compared to the more standard l2 clipping? What effect could this have\n2. 40x overhead would be impractical for many real world applications, do the authors see any avenues or potential for reducing this?\n3. Cauchy noice has been used in some previous work, but do the authors see any specific advantages over Laplace noise?\n4. Could it be possible to quantify or characterise what level of data separability is needed for the method to provide meaningful advantages over global sensitivity approaches? \n5. Have any automatic approached been explored for selecting optimal k values that might reduce the need for multiple training runs while still achieving tight bounds?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ChYW7eh4do", "reviewer": "Reviewer_g645", "summary": "This paper presents a certification algorithm for assessing the stability of model predictions, which helps reduce the smooth sensitivity of the predictions. By providing a tighter bound on smooth predictions, the algorithm enhances the accuracy of private predictions. Empirical experiments demonstrate that this certification improves private binary classification and enhances the accuracy of noisy aggregation.\n\n## update after rebuttal\nI will keep my score unchanged.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and consideration of our work.\n\n\n* 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?\n\nBoth 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.\n\n* 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.\n\nWe 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.\n\n* Another limitation, as stated in the paper, is that the current method is restricted to binary classification.\n\nWe 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. \n\n* Its performance in PATE is effective only when the number of queries is small.\n\nWe 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.\n\nWith 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.", "claims_and_evidence": "The claims are valid. I appreciate how the authors introduce prediction stability—ensuring a stable prediction naturally leads to a reduction in smooth sensitivity. This insight effectively motivates the development of an algorithm to verify prediction stability.", "methods_and_evaluation_criteria": "The experiments are well designed. The reduced smooth sensitivity helps improves performance on two application, private binary classification and PATE.", "theoretical_claims": "I didn't fully checked the proofs. But the results make sense to me.", "experimental_designs_or_analyses": "Yes. The smooth sensitivity is reduced using the certification. Model prediciton accuracy is improved under certain cases.", "relation_to_broader_scientific_literature": "The paper gives an alternative way for private prediction with improved accuracy. This also motivates more investigation into private predictions which might be more accesiable compared to DP-SGD.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength: The use of certification for prediction stability to reduce smooth sensitivity is an innovative idea. The paper presents two important applications: private binary classification and PATE. Additionally, the writing is clear, and the motivations are well articulated.\n\nWeakness: My primary concern is the efficiency of the algorithm. The certification process involves clipping (similar to DP-SGD) and incurs additional overhead for bounding stability. As the authors acknowledge, the algorithm requires 20 times more computation time. 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.\n\nAnother limitation, as stated in the paper, is that the current method is restricted to binary classification. Additionally, its performance in PATE is effective only when the number of queries is small.", "other_comments_or_suggestions": "No.", "questions_for_authors": "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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers collectively recognize the paper's valuable contribution in proposing tighter data-dependent privacy bounds using interval bound propagation for gradient-based learning models. The theoretical analysis is thorough, rigorous, and successfully bridges adversarial robustness certification techniques with differential privacy, a promising interdisciplinary direction. Despite noted concerns about computational overhead and limited experimental scope, the authors' rebuttal effectively addressed these points, clarifying future directions and providing additional experimental validations. Overall, the reviewers were positive about the paper.
Decision: Accept (poster)