Bounding training data reconstruction in DP-SGD
Authors: Jamie Hayes
Borja Balle
Saeed Mahloujifar
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential privacy
reconstruction
TL;DR: We develop reconstruction bounds for DP-SGD and attacks that show these bounds are near tight

Abstract: Differentially private training offers a protection which is usually interpreted as a guarantee against membership inference attacks. By proxy, this guarantee extends to other threats like reconstruction attacks attempting to extract complete training examples. Recent works provide evidence that if one does not need to protect against membership attacks but instead only wants to protect against a training data reconstruction, then utility of private models can be improved because less noise is required to protect against these more ambitious attacks. We investigate this question further in the context of DP-SGD, a standard algorithm for private deep learning, and provide an upper bound on the success of any reconstruction attack against DP-SGD together with an attack that empirically matches the predictions of our bound. Together, these two results open the door to fine-grained investigations on how to set the privacy parameters of DP-SGD in practice to protect against reconstruction attacks. Finally, we use our methods to demonstrate that different settings of the DP-SGD parameters leading to same DP guarantees can results in significantly different success rates for reconstruction, indicating that the DP guarantee alone might not be a good proxy for controlling the protection against reconstruction attacks.

Bounding Training Data Reconstruction in DP-SGD
Jamie Hayes Google DeepMind j jamhay@goggee.o com
Saeed Mahloujifar'
Borja Balle Google DeepMind bballe@google.c com
Meta Al saeedm@meta,co com
Abstract
Differentially private training offers a protection which is usually interpreted as a guarantee against membership inference attacks. By proxy, this guarantee extends to other threats like reconstruction attacks attempting to extract complete training examples. Recent works provide evidence that if one does not need protect against membership attacks but instead only wants to protect against training data reconstruction, then utillity of private models can be improved because less noise is required to protect against these more ambitious attacks. We investigate this further in the context of DP-SGD, standard algorithm for private deep learning, and provide an upper bound on the success of any reconstruction attack against DP-SGD together with an attack that empirically matches the predictions of our bound. Together, these two results open the door to fine-grained investigations how to set the privacy parameters of DP-SGD in practice to protect against reconstruction attacks. Finally, we use our methods to demonstrate that different settings of the DP-SGD parameters leading to the same DP guarantees can result in significantly different success rates for reconstruction, indicating that the DP guarantee alone might not good proxy for controlling the protection against reconstruction attacks.
Introduction
Machine learning models can and do leak training data (Ippolito et al. 2022 Kandpal et al. 2022
Carlini et al. 2019 Yeom al. 2018 Song & Shmatikov 2019 Tirumala al. 2022). If the training
data contains private or sensitive information, this can lead to information leakage via a variety of
different privacy attacks (Balle al. 2022 Carlini et al., 2022 Fredrikson al. [205 Carlini et al.)
2021) Perhaps the most commonly studied privacy attack, membership inference (Homer et al.
2008 Shokri al. 2017), aims to infer if sample was included in the training set, which can lead to a privacy violation if inclusion in the training set is in and of itself sensitive. Membership inference leaks single bit of information about sample whether that sample was
not in the training set - and so any mitigation against this attack also defends against attacks that aim to reconstruct more information about sample, such training data reconstruction attacks (Balle et al. 2022 Carlini et al. 2021] Zhu et al. 2019).
Differential privacy (DP) (Dwork et al. 2006) provides effective mitigation that provably bounds the success of any membership inference attack, and so consequently any training data reconstruction attack. The strength of this mitigation is controlled by privacy parameter which, informally, represents the number of bits that can be leaked about training data sample, and so must be small guarantee the failure of membership inference attack (Sablayrolles et al. 2019 Nasr et al.) 2021). Unfortunately, training machine learning models with DP in the small regime usually produces models that perform significantly worse than their non-private counterpart (Tramer & Boneh 2021 De et al. 2022).
"Equal contribution.
1 Work done at Princeton University.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Membership inference may not always be the privacy attack that is of most concern. For example, in social networks, participation is usually public; recovering privately shared photos or messages from a model trained on social network data is the privacy violation. These kinds of attacks are referred to as training data reconstruction attacks, and have been successfully demonstrated against a number of machine learning models including language models (Carlini et al. [021] Mireshghallah et al. 2022). generative models (Somepalli et al., 2022, Carlini et al., 2023) and image classifiers (Balle et al. 2022; Haim et al. 2022). Recent work (Bhowmick et al. 2018 Balle et al. 2022 Guo et al. 2022a bj Stock et a 2022) has begun to provide evidence that if one is willing to forgo protection against membership inference, then the regime that protects against training data reconstruction is far larger, as predicted by the intuitive reasoning that successful reconstruction requires a significant number of bits about individual example to be leaked by the model. This also has the benefit that models trained to protect against training data reconstruction but not membership inference do not suffer as large a drop in performance, less noise is added during training. Yet, the implications of choosing a concrete for a particular application remain unclear since the success of reconstruction attacks can vary greatly depending the details of the threat model, the strength of the attack, and the criteria of what constitutes a successful reconstruction.
In this paper we re-visit the question of training data reconstruction against image classification models trained with DP-SGD (Song et al. 2013 AAbadi et al.) 2016), the workhorse of differentially analysis DP-SGD because state-of of of-the-art art
private deep learning. We choose to concentrate
results are almost exclusively obtained with DP-SGD or other privatized optimizers (De et al. 2022] Cattan et al., 2022] Mehta al., 2022). Our investigation focuses on attacks performed under strong threat model where the adversary has access to intermediate gradients and knowledge of all the training data except the target of the reconstruction attacks. This threat model is consistent with the privacy analysis of DP-SGD (Abadi et al. (016) and the informed adversary implicit in the definition of differential privacy (Nasr et al. 2021 Balle al. 2022), and implies that conclusions about the impossibility of attacks in this model will transfer to weaker, more realistic threat models involving real-world attackers. Our investigation focuses on three main questions.
How do variations in the threat model (e.g. access to gradients and side knowledge available to the adversary) affect the success of reconstruction attacks? 2) possible to obtain upper bounds on reconstruction success for DP-SGD that match the best known attacks and thus provide actionable insights into how to tune the privacy parameters in practice? 3) Does the standard DP parameter provide enough information to characterize vulnerability against reconstruction attacks?
Our contributions are summarized follows:
We illustrate how changes in the threat model for reconstruction attacks against image classification models can significantly influence their success by comparing attacks with access to the final model parameters, access to intermediate gradients, and access to prior information.
We obtain tight upper bound on the success of any reconstruction attack against DP-SGD with access to intermediate gradients and prior information. Tightness is shown by providing attack whose reconstruction success closely matches our bound's predictions.
We provide evidence that the DP parameter is not sufficient to capture the success of reconstruction attacks on DP-SGD by showing that different configurations of DP-SGD's hyperparameters leading to the same DP guarantee lead to different rates of reconstruction success.
2 Training Data Reconstruction in DP-SGD
We start by introducing DP-SGD, the algorithm we study throughout the paper, and then discuss reconstruction attacks with access to either only the final trained model, or all intermediate gradients. Then we empirically compare both attacks and show that gradient-based attacks are more powerful than model-based attacks, and we identify a significant gap between the success of the best attack and a known lower bound. As a result, we propose the problem of closing the gap between theoretical bounds and empirical reconstruction attacks.
Differential privacy and DP-SGD. Differential privacy (Dwork et al. 2006) formalizes the idea that data analysis algorithms whose output does not overly depend on any individual input data point

---

can provide reasonable privacy protections. Formally, we say that randomized mechanism M satisfies (e, -ddiifeerettial privacy (DP) if, for any two datasets D. D' that differ by one point, and any subset S of the output space we have P(M(D) E S] < E PDM(D)) E S] + 8. Informally, this means that DP mechanisms bound evidence an adversary can collect (after observing the output) about whether the point where D and D' differ was used in the analysis. For the bound to provide a meaningful protection against an adversary interested in this membership question it is necessary to take 2 1 and ó z I/1D).
differentially private version of stochastic gradient descent useful for training ML models can be obtained by bounding the influence of any individual sample in the trained model and masking it with noise. The resulting algorithm is called DP-SGD (Abadi et al.) (016) and proceeds by iteratively updating parameters with privatized gradient descent step. Given sampling probability q. current model parameters and loss function ((O, ), the privatized gradient g is obtained by first creating a mini-batch B including each point in the training dataset with probability q. summing the L-2-clipped gradient for each point in B, and adding Gaussian noise with standard deviation a C to all coordinates of the gradient: g ΣEER clipe (V)((0,=)) + (0, C²o21). Running DP-SGD for
T training steps yields an (c, 6)-DP mechanism with = T (og()))))))
Abadi et al. 2016) in
practice, tighter numerical bounds on e are often used (Gopi et al. [021] Google DP Team 2022).
For analytic purposes it is often useful to consider alternatives to (c, 0 to capture the differences
between distributions M (D) and M (D'). Rényi differential privacy (RDP) (Mironov 2017) is one such alternative often used in the context of DP-SGD. It states that the mechanism is (a, RDDD
for > 1 and 2 0 if BW~M(D)) [(
(P(M(D)-W) "1 S e(a-1)e, In particular, T iterations of
full-batch DP-SGD (i.e. q= 1) with noise multiplier a give (a, 20t2 RDDP for every 1.
Ultimately, we are interested understanding how the privacy guarantee of DP-SGD affects recon- struction attacks and, in particular, whether e >> 1 still provides some protection against these more ambitious attacks. The first step is to understand what the most idoneous threat model to investigating this question is, and then to instantiate powerful attack in that model.
2.1 Comparing reconstruction attacks under intermediate and final model access
In the case of DP-SGD, the privacy guarantee for the final model is obtained by analyzing the privacy loss incurred by releasing the T private gradients used by the algorithm. Thus, the guarantee applies both to the intermediate gradients and the final model (by virtue of the post-processing property of DP). has been shown through membership inference attacks that the guarantee obtained through this analysis for the collection of intermediate gradients can be numerically tight (Nast et al. (021I). However, in some specific settings amenable to mathematical treatment, it has also been shown that the final model produced by DP-SGD can enjoy a stronger DP guarantee than the collection of all intermediate gradients (Ye & Shokri 2022 Altschuler & Talwar 2022).
Although these observations apply the standard membership formulation of DP, they motivate an important question for trying to understand the implications of DP guarantees for reconstruction attacks: how does access to intermediate grudients affect the success of reconstruction altacks against DP-SGD? We investigate this question by introducing and comparing the success of model-based and gradient-based attacks. We assume the adversary receives the output of a DP mechanism M and all the input data in D except for one point ="; the adversary's goal is then to produce a reconstruction 2 of the unknown point. This adversary is referred to as the informed adversary in Balle et al. (2022).
Model-based training data reconstruction. Suppose we consider the output of DP- to be only the final model 0 = (D). Under the informed adversary threat model, Ballle et al. (002 propose a to train
reconstruction attack in which the adversary uses their knowledge of M and 1)_ = D a reconstructor neural network (RecoNN) capable of mapping model parameters 0 to reconstructed points E. The training dataset for this network consists of model-point pairs (0',.)) where the z; are auxiliary points representing side knowledge the adversary might possess about the distribution of the target point 2", and the so-called shadow model 6¹ is obtained by applying M to the dataset D. U {2,} obtained by replacing 2 by z; in the original dataset. Despite its computational cost, this attack is effective in reconstructing complete training examples from image classification models
The clipping operation is detined as (lipo(v) v/ [,, [c]l/CC)
3

---

10a
10-1
10"2
Gradient-based attack
+
(Ours)
Gradient-based attack
Model-basee attack
MSE
(Ours)
10
(Balle
10-2
Model-based attack (Balle
Noise
(baseline)
Noise (baseline)
10-1
Gue al. (Lower bound)
Gue al. (Lower bound)
Nearest neighbor (baseline)
Nearest neighbor (baseline)
10
10:
10a
10
10a
10a
10
10a
10"
10a
10a
10a
10a
10
10
10
(a) Average MSE between targets and reconstructions (b) Average MSE between targets and reconstructions on CIFAR-10.
on MNIST.
Figure I: Comparison of model-based and gradient-base reconstruction attacks. We run the attacks over 1K different images for both MNIST and CIFAR-10 for a range of c. In Fa and Figure Th plot the average MSE between reconstruction and target images for both attacks. To help calibrate a reader's interpretation of good and bad reconstructions we plot a nearest neighbor (NN) baseline, marking the average Læ-distance between NN images over the entire dataset, and baseline corresponding to the average distance between random uniform vectors. We also plot a lower bound for MSE given by Guo et (2022a). We give qualitative examples of reconstructions in Appendix
trained without DP on MNIST and CIFAR-10, but fails to produce correct reconstructions when the model is trained with any reasonable setting of DP parameters.
Gradient-based training data reconstruction. Suppose now that the adversary gets access to all the intermediate gradients (g1...... 9r) MD) produced by DP-SGD when training model
We can instantiate reconstruction attack for this scenario by leveraging gradient inversion attacks
found in the federated learning literature (Yim al. [02T; Huang et al.) 202T] Jeon al., [021 [in et al. 2021: Zhu et al. 2019; Geiping et al. 2020). In particular, we use the gradients produced by DP-SGD to construct a loss function [(=) for which the target point 2" would be optimal the gradients contained no noise, and then optimize it to obtain our candidate reconstruction. An important difference between our attack and previous works in the federated learning setting is that we use gradients from multiple steps to perform the attack and only attempt to recover single point.
More formally, we start by removing from each privatized gradient gi the gradients of the known points in D. For simplicity, in this section we only consider the full batch case (g 1) where every training point in D included in every gradient step. Thus, we set Ht 9t - - sED. (Vgl(( z)). where 6, are the model parameters at step t. Note these can be inferred from the gradients and knowledge of the model initialization, which we also assume is given to the adversary. Similar (but not identical) to Geiping et al. (2020). we use the loss L(z) = Σ/= (z(2) with
(=(=) - (clipc z)). 9x) + [ (Vo((0., 9t
This loss was selected after exhaustively trying all other losses suggested in the aforementioned literature; empirically, Equation (I) performed best.
Comparing reconstruction attacks. We now compare the success of model-based and gradient- based reconstruction attacks against classification models trained with DP-SGD MNIST and CIFAR-10. We refer to Appendix A for experimental details.
Following Balle et al. (2022). and target as a functiin of e for both attacks. Results are shown in Figure where we include two baselines to help calibrate how MSE corresponds to good and bad reconstructions. Firstly, include a threshold representing the average distance between target points and their nearest neighbor in the remaining of the dataset. An MSE below this line indicates near-perfect reconstruction. Secondly, we include a threshold representing the average distance between random uniform vectors of the same data dimensionality. An MSE above close this line indicates poor reconstruction.
report the mean squared error (MSE) between the reconstruction
We make the following observations. First, the gradient-based attack outperforms the model-based attack by orders of magnitude at larger values. Second, the best attack starts to perform well on

---

MNIST and C1 between 102 < << 102 and 10ah <<< 10 respectively. This indicates that attack success is affected by the complexity of the underlying data, including its dimension and geometry. Finally, the attacks give an upper bound for reconstruction error (MSE), however it is not clear if this bound tight (i.e., whether a better attack could reduce MSE). Guo et al. (2022a) report 1), which is very far from the upper bound.
a lower bound for MSE of the form -14
The experiment above illustrates how change in threat model can make a significant difference in the success of reconstruction attacks. In particular, it shows that the attack from Balle et al. (0022) is far from optimal, potentially because of its lack of information about intermediate gradients. Thus, while optimal attacks for membership inference are known (Nast et al., 2021) and can be used to empirically evaluate the strength of DP guarantees (e.g. for auditing purposes (Tramèr et al., 2022)), the situation is far less clear in the case of reconstruction attacks. Gradient- braddent-based attacks improve over model-based attacks, but are they (near) optimal? Optimality of attacks important for applications where one would like to calibrate the privacy parameters of DP-SGI to provide demonstrable, pre-specified amount of protection against any reconstruction attacks.
3 Bounding Training Data Reconstruction
We will now formalize the reconstruction problem further and then provide bounds on the success probability of reconstruction attacks against DP-SGD. We will also develop improvements to the reconstruction attack introduced in Section from which to benchmark the tightness of our bound.
3.1
Threat models for reconstruction
Balle et al. 2022) introduce a formal definition for reconstruction that attempts to capture the success probability of any reconstruction attack against given mechanism. The definition involves an informed adversary with knowledge of the mechanism M, the fixed part of the training dataset D., and a prior distribution from which the target x" is sampled the prior encodes the adversary's side knowledge about the target.
Let i by prior over target points and p a reconstruction error function. A randomized mechanism M is (1) Reeeo (reconstruction robust) with respect to æ and p for any fixed dataset D. and any reconstruction attack R we have Pz-=, (>=,, (pz))p(( R R(w)) S n) S.
Definition 1.
Note that the output of the mechanism does not necessarily need to be final model parameters - indeed, the definition also applies attacks operating on intermediate gradients when those are included in the output of the mechanism. Balle et al. (022) also proved that any (a, e RDDD mechanism
is (17. ReRRRRo with ? = (Kiz,
where (1) = sup=,e2 P2- [p( (Z z0) S n)). In
particular, using the RDP guarantees of DP SGD, one obtains that in the full-batch case, running the algorithm for iterations with noise multiplier a is (17 -))ReRo with y bounded by
T
exp
max O,
log
Ki
20
The quantity Kx,p can be thought of as the prior probability of reconstruction by an adversary who outputs fixed candidate 2p based only on their knowledge of the prior (i.e. without observing the output of the mechanism).
we described two variants of reconstruction attack, one where the adversary has access to intermediate model updates (gradient-based reconstruction) and one where the adversary has access to the final model only (model-basse -ased reconstruction). In the language of (7. -ReRo, both the gradient-basee model--ased reconstruction attacks introduced in Section about the target point, D. the training dataset excluding the target point, w the output of the mechanism M, and side information about DP-SGD such as hyperparameters used in training and how to the model was initialized. The model-based reconstruction attack assumes that w = 0r, the parameters of the final model, whereas for gradient-baset attacks, w = (gi,-..,gT), and so the adversary has access to all intermediate privatized model parameter updates.
Instantiating threat models within the (1,, -ReeRo framework In Section 2.1
and as arguments: π - prior information
5

---

The gradient-basee based attack optimizing Equation [ does not make use of any potential prior knowledge the adversary might have about the target point 2", beyond input bounds (the imput is bound between [0.I]) and the dimensionality of target (28 x 28 for an MNIST digit). On the other hand, the model- based attack makes use of a prior in the form of the auxiliary points 2; used in the construction of shadow models; these points represent the adversary's 's knowledge about the distribution from which the target points z" is sampled.
Going forward in our investigation we will assume the adversary has access to more "reliable" side knowledge: their prior is a uniform distribution over finite set of candidate points {21..... } one of which corresponds to the true target point. This setting is favorable towards the adversary: the points in the prior represent a shortlist of candidates the adversary managed to narrow down using side knowledge about the target. In this case it is also reasonable to use the error function p(2,z') = T[= & z') since the adversary's 8 goal is to identify which point from the prior is the target. As DP assumes the adversary knows (and can influence) all but one record in the training set, the assumption that the adversary has prior knowledge about the target aligned with the DP threat model. The main distinction between membership inference and reconstruction with uniform prior is that in the former the adversary (implicitly) managed to narrow down the target point to two choices, while in the latter they managed to narrow down the target to choices. This enables us to smoothly interpolate between the exceedingly strong DP threat model of membership inference (where the goal is to infer single bit) and a relaxed setting where the ad adversary's 's side knowledge is less refined: here n controls the amount of prior knowledge the adversary is privy to, and requires the adversary to infer log(n) bits to achieve successful reconstruction.
The discrete prior setup, we argue, provides a better alignment between the success of resconstruction attacks and what actually constitutes privacy leakage. In particular, it allows us to move away from (approximate) verbatim reconstruction as modelled, e.g., by an l reconstruction criteria success, and model more interesting situations. For example, if the target image contains a car, attacker might be interested in the digits of the license plate, not the pixels of the image of the car and its background. Thus, if the license plate contains 4 digits, the attacker's goal is to determine which of the possible 10,000 combinations was present in the in the training image.
In Appendix L we also conduct experiments where the adversary has less background knowl- edge about the target point, and so the prior probability of reconstruction extremely small (e.g. O (1/25)) 32x32x33 for CIFAR-10 image).
3.2 Reconstruction Robustness of DP-SGD
ReRo bounds from blow-up functions We now state novel reconstruction robustness bound that, instead of using the (R)DP guarantees of the mechanism, is directly expressed in terms of its output distributions. The bound depends on the blow-up function between two distributions, Js and Ds
Br, v) = sup
E s.t. Py S k}
(3)
In particular, let vpD = (D.) denote the output distribution of the mechanism on a fixed dataset D., and μpp (D. U (z]) for any potential target 2. Then we have the following (see Appendix M. for the full statement).
Theorem 2 (Informal). Fix n and p. Suppose that for every fixed dataset D. there exists a pair of distributions Pb. v'b. such that supzesupp(r) Ba (HD, VD.) S (x(,,, vb.) for all K E [0, 1). Then M is (1. ReRRo with 7 supp, Bx.../n) (H.. v.
This result basically says that the probability of successful reconstruction for an adversary that does observe the output of the mechanism can be bounded by the maximum probability under vb, over all events that have probability (T)) under V/. when we take the worst-case setting over all fixed datasets D. and all target points in the support of the prior. If M satisfies O)-P (i.e. (DO, RDD) then Pwn, [E] < e uad [E] for any event E, in which case Theorem 2 gives with 7 (n)e.. This recovers the case a oo of the bound from Balle et al. (2022) stated above.
Remark 3. The blow-up function is tightly related to the notion of trade-off function defined in Dong el al. (2019). Precisely, the trade-off function between two probability distributions μ and v is defined as The (1, v) inl y [E] E s.1. [F[ S k). The trade-off function is usually introduced in terms of Type and Type II errors; it defines the smallest Type error achievable given constraint on the maximum Type error, and we have the following relationship: Tn(H,)) v) = 1 Bal v).

---

ReRo for DP-SGD
Next we apply this bound directly to DP-SGD without an intermediate appeal its RDP guarantees: in Section 4.1 we will empirically demonstrate that in practice this new bound is vastly superior to the bound in Balle et al. (2022).
Let M be the mechanism that outputs all the intermediate gradients produced by running DP-SGD for '"' steps with noise multiplier o and sampling rate Our analysis relies on the observation from Mahloujifar al. (2022) that comparing the output distributions of M on two neighbouring datasets can be reduced to comparing the 7 f'-dimensional Gaussian distribution VT,0 = =N(0,o²1 with the Gaussian mixture PT,0. = Ene (o.1) P[B(g. T) = w]N(w, I) where B(q, is a random binary vector obtained by sampling each coordinate independently from a Bernoulli distribution with success probability q.
Corollary 4. For any prior π and error function p. M is (1), -ReRo with 7 = Ber (MT, VT,a).
We defer proofs and discussion to Appendix M (2022b) also provides an upper bound on the success of training data reconstruction under DP. We compare this to our own upper bound in Appendix
We note that the concurrent work of Guo et al.
3.3 Upper bound estimation via reconstruction robustness
To estimate the bound in Corollary 4 in practice we first estimate the baseline probability (T) and then the blow-up Bx VT,)).
Estimating n. All our experiments deal with uniform discrete prior т - Σ3 1,, over a finite set of points { } In this case, compute it suffices to find the p-bail of radius 17 containing the largest number of points from the prior. one is further interested in exact reconstruction (i.e. p(2,=') T[ * z'] and 1) 1) then immediately have 1/n. Although this already covers the setting from our experiments, we show in Appendix that more generally is possible to estimate only using samples from the prior. We use this calculate for some non-uniform settings where we relax the condition to be on a close reconstruction instead of exact reconstruction.
Estimating 7 Note that it is easy both sample and evaluate the density of J Fraa and = Vr.o- Any time these two operations are feasible we can estimate BB (1., v) using a non- parametric approach find the event E that maximizes Equation 33. The key idea
observe that,
as long as //v 5o then change of measure gives Pn = Ew-
((W) I[W E E]] For fixed v(W)
E this expectation can be approximated using samples from v. Furthermore, since we are interested in the event of probability less than under that maximizes the expectation, we can take N samples from y and keep the kNN samples that maximize the ratio μ/v to obtain a suitable candidate for the maximum event. This motivates the Monte-Came approximation of in Algorithm I
Proposition 5. For μ Pr,a. and v Vr,a we have lim ÿ (p, v) almost surely.
Algorithm 1 Estimating
Algorithm 2 Prior-aware attack
Input:
Prior probability number of sam-
Input: Discrete prior π (z),.... ... Zn
ples N, sampling and density evaluation access to v and μ.
Model parameters (0,, 0,,..., 0r), Priva- tized gradients (with known gradients sub- tracted) (ō.......7) .r.
Output: Estimate n of reconstruction ro- bustness probability.
Observations: O +
Sample W1, 10 independently from v Calculate the ratios r; = ((w:)/vil //(m))
Output: Reconstruction guess & E I for E [1, 2,..., do
Sort the ratios in decreasing order: ri Z
O +- Σ (clipe (V,l 2))
end for
Let N = [R.]] and return 7
+- arg max O
DE
return x- π
'This is satisfied by μ pr.a and VT.0.

---

Estimation guarantees Although Proposition 4 is only asymptotic, we can provide confidence intervals around this estimate using two types of inequalities. A two points of error, the gap between the empirical quantile and the population quantile, and the error from mean estimation 9. The first source of error can be bounded using the DKW inequality (Dvoretzky al., 1956) which provides a uniform concentration for each quantile. In particular, we can show that the error of quantile estimation is at most 2e 2e-2nn" 2nn², where is the number of samples and 1j is the error in calculation of the quantile. Specifically, with a million samples, we can make sure that with probability 0.999 the error of quantile estimation is less than 0.002, and we can make this smaller by increasing the number of samples. We can account for the second source of error with Bennett's inequality, that leverages the bounded variance of the estimate. In all our bounds, we can show that the error of this part is also less than 0.01 with probability 0.999, We provide an analysis on the computational cost of estimating 7 in Appendix A
3.4 Lower bound estimation via a prior-aware attack
We now present a prior-aware attack whose success can be directly compared to the reconstruction upper bound from Corollary 4
In addition to the uniform prior π == n E; 1; from which we assume the target sampled from, our prior-aware attack has access to the same information as the gradient-based attack from Section [ all the privatized gradients (and therefore, intermediate models) produced by DP-SGD, and knowledge of the fixed dataset D. that can be used to remove all the known datapoints from the privatized gradients. The attack given in Algorithm 2 For simplicity, in this section we present and experiment with the version of the attack corresponding to the full-batch setting in DP-SGD (i.e. q 1). We present an extension of the algorithm to the mini-batch setting in Section 4.3
The rationale for the attack is as follows. Suppose, for simplicity. that all the gradients are clipped so they have norm exactly C. If 2" is the target sampled from the prior, then Gr ~ clipe (V Vol(()) (0, 2 00.2
(0, C2 T)). Then the inner products (clipa(Vo 2z)). 9t) follow a distribution N(C2 Cooy & = and (A, C²)2) for some A C2 otherwise (assuming no two gradients are in the exact same direction). In particular, A z 0 if the gradients of the different 2; in the prior are mutually orthogonal. Thus, finding the z; that maximizes this sum of inner products likely to produce a good guess for the target point. This attack gives lower bound on the probability of successful reconstruction, which we can compare with the upper bound estimate derived in Section 3.3
Experimental Evaluation
We now evaluate both our upper bounds for reconstruction success and our empirical privacy attacks (which gives us lower bounds on reconstruction success). We show that our attack has a success probability nearly identical to the bound given by theory. We conclude this section by inspecting how different variations on our threat models change both the upper bound and the optimality of our new attack.
4.1 Attack and Bound Evaluation on CIFAR-10
We now evaluate our upper bound (Corollary 4 and prior-aware reconstruction attack (Algorithm 2 on full-batch DP-SGD, and compare it to the gradient-based (prior-oblivious) attack optimizing Equation
11 and the RDP upper bound obtained from previous work (Equation ( To perform our evaluation on CIFAR-10 10 models with relatively high accuracy despite being trained with DP-SGD, we follow De et al. 2022)) and use DP-SGD to fine-tune the last layer of a WideResNet model (Zagoruyko & Komodakis 2016) pre-trained ImageNet. In this section and throughout the paper, we use a prior with uniform support over 10 randomly selected points unless we specify the contrary. Further experimental details are deferred to Appendix A
The results of our evaluation are presented in Figure which reports the upper and lower bounds on the probability of successful reconstruction produced by the four methods at three different values of (e, 10-5)-DP. The first important observation that our new ReRo bound for DP-SGD is a significant improvement over the RDP-based bound obtained in Balle et al. (2022), which gives trivial bound for E (10, 100) in this setting. On the other hand, we also observe that the prior-aware attack substantially improves over the prior-oblivious
8

---

gradient-based attack] which Section 2 already demonstrated is stronger than previous model- based attacks more thorough investigration of how the gradient-basee based attack compares to the prior-aware attack is presented in Appendix D for varying sizes of the prior distribution.
We will use the prior-aware attack exclusively fol-
lowing experiments due to its superiority over the
gradient- attack. Finally, we observe that our best empirical attack and theoretical bound are very close to each other in all settings. We conclude there
Hardue gutto
Phar-emure allech
settings where the upper bound is nearly tight and the prior- prior-based attack is nearly optimal.
1.0-
0.9
Now that we have established that our attacks work well on highly accurate large models, our remaining experiments will be performed on MNIST which are significantly more efficient to run.
0.4-
Figure Comparison of success of reconstruction attacks against reconstruction upper bounds on CIFAR-10 with test accuracy at 1, 10, and 100 equal to 61.88% 89. 89.09%, and 91.27%, respectively. Note, the best model we could train at do with our experimental settings reaches 93.91%.
4.2 Effects of the prior size
We now investigate how the bound and prior-aware attack are affected by the size of the prior in Figure 3 As expected, both the upper and lower bound the probability that we can correctly infer the target point decreases as the prior size increases. We also observe widening gap between the upper bound and attack for larger values
and prior size. However, this bound is still relatively tight for e < 10 and prior size up to 20 Further experiments regarding how the prior affects reconstruction are given in Appendix E
Upper SNOTE stRi
0.8
4.3 Effect of DP-SGD Hyperparameters
0.6
Given that we have developed attack that is close to optimal in a full-batch setting, we are now ready to inspect the effect DP-SGD hyper-parameter con- trolling its privacy guarantees have on reconstruction success. First, we observe how the size of mini-batch affects reconstruction success, before measuring how reconstruction success changes with differing hyper- parameters at a fixed value of e. Further experiments that measure the effect of the clipping norm, C, are deferred to Appendix[I K
Figure 3: How the size of the prior π affects reconstruction success probability for a range of different values c.
Upper bound Prion sware
Improved prior-ware
-X--
guees
Succes sobaaity
Effect of sampling rate q. All of our experiments so far have been in the full-batch (q = 1) setting. We now measure how mini-batching affects both the upper and lower bounds by reducing the data sam- pling probability g from to 0.02 (see Appendix A for additional experimental details).
1.0
0.5
0.0
10
Figure 4: We compare how the attack from Aggorihhmccompar with the improved prior-aware attack when 0.02.
The attack presented
that the gradient of z" is present in every privatized gradient. Since this no longer true in mini-batch DP-SGD, design improved attack by factoring in the knowledge that only fraction of privatized gradi- ents will contain the gradient of the target 2* This is achieved by, for fixed 2, collecting the inner- products (clipc(Vol((),, 24)), g.) across all T iterations,
Algorithm@aassii
'To measure the success probability of the gradient- based attack we take the output of the optimization process, find the closest point in the support of the prior, and declare success if that was the actual target. This process is averaged over 10,000 randomly constructed priors and samples from each prior.

---

10
0.35
Success prob-biiillll
(upper bound)
10
0.30
Succeess probabi abbbil bility
(improxe po
prior-awaid attack)
0.30
0.25
5
5
0.20
0.20
0.15
10-2
10
10a
10-2
10
10a
9
(a) Upper bound.
(b) (Improved) Prior-aware attack.
Figure 5: We plot a against at (4, 10 1011000))) DDD at fixed T = 100 and the corresponding upper bound (Figure Sab and (improved) prior-aware attack (Figure 5b). Reconstruction is less successful at smaller in comparison to large for the same value of
and computing the score using only the top qJ values. Pseudo-code for this improved prior-aware attack variant given in Appendix
Results are shown in Figure where we observe the improved attack fairly tight to the upper bound, and also large difference between the previous and improved attack.
Effect of DP-SGD hyperparameters at a fixed e. In our final experiment, we fix e and investigate if and how the reconstruction upper bound and lower bound (through the improved prior-aware attack) change with different DP-SGD hyperparameters. In Figure 5 we fix E and run DP-SGD [0.01, 0.99]. In each setting
for T 100 iterations with C while varying satisfy (4, 10 D-DD.. For experimental efficiency, we use fewer values of q for the attack than the theoretical bound. Surprisingly,
tune to
find that both the upper bound and lower bound change with different hyperparameter configurations, For example, at q = 0.01 the upper bound on successful reconstruction is z 0.20 (and the attack is z 0.15), while g 0.99 it is 0.35 (and the attack is x 0.32). Generally, an increase in 7 or q increases the upper bound. This suggests that an (c, 5)DP guarantee alone is not able to fully specify the probability that reconstruction attack is successful. We conduct a more extensive evaluation for different and prior sizes in Appendix K.2
5 Conclusion
In this work, we investigated training data reconstruction bounds on DP-SGD. We developed upper bounds on the success that an adversary can reconstruct training point 2" under DP-SGD In contrast to prior work that develop reconstruction upper bounds based on DP or RDP analysis of DP-SGD, our upper bounds are directly based the parameters of the algorithm. We also developed new reconstruction attacks, specifically against DP-SGD, that obtain lower bounds on the probability of successful reconstruction, and observe they are close to upper bounds. Our experiments show that both our upper and lower bounds are superior to previously proposed bounds for reconstruction in DP-SGD. Our investigations further showed that the parameter in DP (or RDP) cannot solely explain robustness to reconstruction attacks. other words, one can have the same value of c for two different algorithms while achieving stronger robustness against reconstruction attacks in the other. This suggest that a more fine-grained analysis of algorithms against specific privacy attacks can lead superior privacy guarantees and also opens up the possibility of better hyperparameter selection for specific privacy concerns.
6 Acknowledgements
The authors would like thank Leonard Berrada and Taylan Cemgil for their thoughtful feedback on an earlier version of this work.
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.
10

---

Altschuler, J. M. and Talwar, K. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. arXiv preprint arXiv:2205.13770, 2022.
Balle, B., Cherubin, G., and Hayes, J. Reconstructing training data with informed adversaries. In 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022, 2022.
Bhowmick, A.. Duchi, J., Freudiger, J., Kapoor, G., and Rogers, R. Protection against reconstruction and its applications in private federated learning. arXiv preprint arXiv: /1X.00///2.009844. 2018.
Carlini, N., Liu, C., Brlingsson, U., Kos, J., and Song, D. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium (USENIX Security 19), pp. 267-284, 2019.
Carlini, N., Tramer, F., Wallace, E., Jagielski, M., Herbert- A., Lee, K., Roberts, A., Brown, T., Song, D., Erlingsson, U., et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pp. 2633-2650, 2021.
Carlini, N., Chien, S., Nasr, M. Song, S., Terzis, A., and Tramer, F. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914. IEEE, 2022.
Carlini, N., Hayes, J., Nasr, M., Jagielski, M., Sehwag, V., Tramèr, F., Balle, B., Ippolito, D., and Wallace, E. Extracting training data from diffusion models. arXiv preprint 1rX1v:2301.13188 2023.
Cattan, Y., Choquette-Chone C. A., Papernot, N., and Thakurta, A. Fine-tuning with differential privacy necessitates an additional hyperparameter search. arXiv preprint arXiv:2210.02/56, 2022.
De, S., Berrada, L.,, Hayes, J., Smith, S. L., and Balle, B. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. arXiv preprint 1rX.v:990.003388 2019.
Dvoretzky, A., Kiefer, J., and Wolfowitz, J. Asymptotic minimax character the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pp- 642-669, 1956.
Dwork, C., McSherry F., Nissim, K., and Smith, A. D. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006.
Feldman, V. and Zmnie, T. Individual privacy accounting via renyi filter. Advances in Neural Information Processing Systems, 34:28080 28091, 2021.
Fredrikson, M., Jha, S., and Ristenpart, T. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC conference computer and communications security, pp. 1122-1333, 2015.
Geiping, J., Bauermeister, H., Dröge, H., and Moeller, M. Inverting gradients how easy is to break privacy in federated learning? In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Google DP Team. Privacy loss distributions. differential /atir///aaaaaaaaa//////aaaa////a 2022.
httpp::/ggithub.com/gooo bos.sasro.....s.iitttiiittooooos pdf
Gopi, S., Lee, Y. and Wutschitz, L. Numerical composition of differential privacy. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Guo, C., Karrer, B., Chaudhuri, K., and van der Maaten, L. Bounding training data reconstruction in private (deep) learning. arXiv preprint arXiv:2201.12388, 2022a.
Guo, C., Sablayrolles, A., and Sanjabi, M. Analyzing privacy leakage in machine learning via multiple hypothesis testing: A lesson from fano. arXiv preprint
2022b.
11

---

Haim, N., Vardi, G., Ychudai, G. Shamir, O., and Irani, M. Reconstructing training data from trained neural networks. arXiv preprint arXiv:2206.0773 2022.
Homer, N., Szelinger, S., Redman, M., Duggan, D., Tembe, W., Muehling. J., Pearson, V., Stephan, D. A., Nelson, S. F., and Craig, D. W. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. PLoS genetics, 4(8): e1000167, 2008
Huang, Y., Gupta, S., Song, Z., Li, K., and Arora, S. Evaluating gradient inversion attacks and defenses in federated learning. Advances in Neural Information Processing Systems, 34:7232-7241, 2021.
Ippolito, D., Tramèr, F., Nasr, M., Zhang, C., Jagielski, M., Lee, K., Choquette-Choor C. A., and Carlini, N. Preventing verbatim memorization in language models gives a false sense of privacy. 2022.
arXiv preprint arXiv:2210.
Jeon, J., Lee, K., Oh, S., J., et al. Gradient inversion with generative image prior. Advances in Neural Information Processing Systems, 34:29898- 299008, 2021.
Jin, X., Chen, P.-Y,, Hsu, C.-Y., Yu, C.-M., and Chen, T. Cafe: Catastrophic data leakage in vertical federated learning. Advances in Neural Information Processing Systems, 34:994-1006, 2021.
Kandpal, N., Wallace, E., and Raffel, C. Deduplicating training data mitigates privacy risks in language models. arXiv preprint 2xii:22002.06539 2022.
Lehmann, I., and Romano,
Testing statistical hypotheses. Springer, 2005.
Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, S. Z. Accuracy first: Selecting differential privacy level for accuracy constrained erm. Advances in Neural Information Processing Systems, 30, 2017.
Mahloujifar, S., Sablayrolles, A., Cormode, G., and Jha, S. Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms. arXiv preprint arXiv:2204.06106, 2022.
Mehta, H., Thakurta, A., Kurakin, A., and Cutkosky, A. Large scale transfer learning for differentially private image classification. arXiv preprint arXiv:2205.02977 2022.
Mireshghallah, F., Goyal, K., Uniyal, A., Berg- Kinkpatra,, T., and Shokri, R. Quantifying pri- vacy risks of masked language models using membership inference attacks. arXiv preprint arXiv:2203.03929 2022.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263-275. IEEE, 2017."
Nasr, M., Song, S., Thakurta, A., Papemoti, N., and Carlini, N. Adversary instantiation: Lower bounds for differentially private machine learning. In Symposium on Security and Privacy (S&P), 2021.
Redberg, R. and Wang, Y.-X. Privately publishable per-instance privacy. Advances in Neural Information Processing Systems, 34: 34:17335 2021.
Sablayrolles, A., Douze, M., Schmid, C., Ollivier, Y., and Jégou, H. White-box vs black-box: Bayes optimal strategies for membership inference. In International Conference on Machine Learning, pp. 5558-5567. PMLR, 2019.
Shokri, R., Stronati, M., Song, C., and Shmatikov, V. Membership inference attacks against machine learning models. 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Somepalli, G., Singla, V., Goldblum, M., Geiping, J., and Goldstein, T. Diffusion art or digital forgery? investigating data replication in diffusion models. arXiv preprint arXiv:2212.0388 2022.
Song, C. and Shmatikov, 1r.1v:1905.11742, 2019.
Overlearning reveals sensitive attributes.
arXiv preprint
12

---

Song, S., Chaudhuri, K., and Sarwate, A. D. Stochastic gradient descent with differentially private updates. 2013 IEEE global conference on signal and information processing, pp. 245-248. IEEE, 2013.
Stock, P., Shilov, I,, Mironov, I., and Sablayrolles, A. Defending against reconstruction attacks with rényi differential privacy. arXiv preprint Xii::2222.007223... 2022.
Tirumala, K., Markosyan, A. H., Zertlemoyer, L.,, and Aghajanyan, A. Memorization without overfit- ting: Analyzing the training dynamics of large language models. arXiv preprint 10X70 2022.
Tramèr, F. and Bonch, D. Differentially private learning needs better features (or much more data). In International Conference on Learning Representations (ICLR), 2021.
Tramèr, F., Terzis, A., Steinke, T., Song, S., Jagielski, M., and Carlini, Debugging differential privacy: A case study for privacy auditing. arXiv preprint arXiv:2202.1223 2022.
Wang, Z.. Song, M., Zhang, Z., Song, Y., Wang, Q., and Qi. H. Beyond inferring class representatives: User-level privacy leakage from federated learning. IEEE INFOCOM 2019-IEEE Conference Computer Communications, pp. 2512-2520. IEEE, 2019.
Ye, and Shokri, R. Differentially private learning needs hidden state (or much faster convergence). arXiv preprint wr.iv:2203.0553000 2022.
Yeom, S., Giacomelli, I., Fredrikson, M., and Jha, S. Privacy risk in machine learning; Analyzing the connection overfitting In 2018 JEEE 31st computer security foundations symposium (CSF), pp. 268 282. IEEE, 2018.
Yin, H., Mallya, A., Vahdat, A., Alvarez, J. M., Kautz, J., and Molchanov, P. Image batch recovery via gradinversion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16337-16346, 2021.
See through gradients:
Yu, D.. Kamath, G., Kulkarni, J., Yin, J., Liu, T.-Y., and Zhang, H. Per-instance privacy accounting for differentially private stochastic gradient descent. arXiv preprint arXiv:2206.02617, 2022.
Zagoruyko, S. and Komodakis, N. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
Zhao, B., Mopuri, K. R., and Bilen, H. idlg: Improved deep leakage from gradients. arXiv preprint arXiv:2001.02610, 2020.
Zhu, L., Liu, Z., and Han, S. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019.
Zhu, Y., Dong. J., and Wang. Y.-.. Optimal accounting of differential privacy via characteristic function. In International Conference Artificial Intelligence and Statistics, pp. 4782 4817. PMLR, 2022.
13

---

Table 1: Hyperparameter settings for each experiment. The set of examples that make up the prior (T), including the target (z"), and the other examples in the training set (D.) are always drawn from the same data distribution, except for the experiment performed in Figure
Dataset
Experiment
Clipping norm C
Sampling pubshility
Update steps T
Model zrchitecture 0
( +
Traiingg datsset size
Pricr size
CIAR 10
Figine
Figrr
IN
Figure
Figure 12h
100)
100)
WRIN-28- 1o
WRRN-28-10 10
500
500
10
Figind
18
Pigurees
Ingure
1,000
Fipui
1,000
Fipuec11
0.02
MNIST
Figing
100)
100
MI.
1000
1,000
1,000
[iging3]
1,000
21
Fiping
129, 1,000
1.0
100
MLP
3,000
Figrrse
0.01 0.99
100
1,000
Figure
100
1,000
A Experimental details
We detail the experimental settings used throughout the paper, and specific hyperparameters used for the various attacks we investigate. The exact configurations for each experiment are given in Table [] We vary many experimental hyperparameters to investigate their effect reconstruction, however, the default setting is described next.
For MNIST experiments we use a two layer MLP with hidden width 10 and eLU activations. The attacks we design in this work perform equally well on all common activation functions, however is well known that the model- attack (Balle et al.] (022) performs poorly on piece-wise linear activations like ReLU. We set [D_ = 999 (and so the training set size is D. U [=*} = 1, 000) and train with full-batch DP-SGD for T = 100 steps. For each we select the learning rate by sweeping over a range of values between 0.001 and 100; we do not use any momentum in optimization. We set C 0.1, 8- 10 and adjust the noise scale for given target The accuracy of this model is over 90% for Ve 2 10, however we emphasize that our experiments on MNIST are meant to primarily investigate the tightness of our reconstruction upper bounds. We set the size of the prior to ten, meaning the baseline probability of successful reconstruction is 10%.
(Zagoruyko & Komodakis, 2016) model with 28 layers and width factor 10 (denoted as WRN-28- group normalization, and eLU activations. We align with the set-up of De et al. (2022), who fine-tune WRN-28-10 model from ImageNet to CIFAR-10. However, because the model- attack is highly expensive, we only fine-tune the final layer. We set [.] 499 (and so the training set size is [D. U (2²)) }1 500) and train with full-batch DP-SGD for T = 100 steps; again we sweep over the choice of learning rate for each value of e, We set C 1, 8 10-5 and adjust the noise scale for given target The accuracy of this model is over 89% for Vc 2 10, which is close to the state-of-the--a results given by De et al. (2022), who achieve 94.2% with the same fine-tuning setting size). Again, we set the size of the prior т to ten, meaning the baseline probability of successful reconstruction is 10%.
For the CIFAR- 10 dataset, we use
(with a substantially larger training set
For the gradient- based and model-based attack we generate 1,000 reconstructions and for prior-aware attack experiments we generate 10,000 reconstructions from which we estimate a lower bound for probability of successful reconstruction. That is, for experiments in Section reppet the attack 1,000 times for targets randomly sampled from base dataset (MNIST or CIFAR-10), and for all other experiments we repeat the attack 10,000 times for targets randomly sampled from the prior, which is itself sampled from the base dataset (MNIST or CIFAR- 10). We now give experimental details specific to the various attacks used throughout the paper. Note that for attack results, we report 95% confidence intervals around our lower bound estimate, however, in many cases these intervals are so tight it renders them invisible to the eye.
Model-based attack details. For the model-based attack given by Balle et al. (2022), we train 40K shadow models, and as stated above, construct a test set by training a further 1,000 models on 1,000 different targets (and D.) from which we evaluate our reconstructions. We use the same architecture for the RecoNN network and optimization hyperparameters as described in the MNIST and CIFAR-10 10 experiments in Balle et al. (2022). and refer the interested reader there for details.
14

---

12
7
7
9
7
12
12
2
7
7
3
3
7
9
7
/
12
12
2
4
7
3
3
7
9
7
/
0
12
18
0
2.
4
7
7
3
3
7
9
7
/ 0
12
Dages
0
2.
6
4
7
3
3
7
9
7
0
Inge
(a) Examples of reconstructions on MNIST.
(b) Examples of reconstructions CIFAR-10.
Figure 6: We give qualitative examples of reconstructions in Figure 6a and Figure 6b for the gradient-based reconstruction attack described in Section 2
Gradient-based attack details. Our optimization hyperparameters are the same for both MNIST and CIFAR-IO. We initialize å from uniform noise and optimize it with respect to the loss given in Equation
1 for IM steps of gradient descent with a learning rate of 0.01. We found that the loss occasionally diverges and it is useful to have random restarts of the optimization process; we set the number of random restarts to five. Note we assume that the label of 2 is known to the adversary. This is standard assumption in training data reconstruction attacks federated learning, as Zhao ctt al. (2020) demonstrated the label of the target can be inferred given access to gradients. If we did not make this assumption, For the datasets we consider, this would increase the cost of the attack by a factor of ten. We evaluate the attack using the same 1,000 targets used to evaluate the model-based attack.
the attack be exhaustively searching over all possible labels.
Prior-aware attack details. The prior-aware attacks given in Algorithm 2 (and in Algorithm have specific hyper- pper-parraettrs that need to be set. As stated, the attack proceeds by summing the inner-product defined in Section SectionB..jover all training steps for each sample in the prior and selecting the sample that maximizes this sum the reconstruction. One practical note is that found it useful to normalize privatized gradients such that the privatized gradient containing the target will be sampled from a Gaussian with unit mean instead of C2, which will be sensitive choice of C and can lead to numerical precision issues.
Estimating y details. As described in Section is instantiated ((000011 T -dimensioonal isotropic Gaussian distribution with zero mean, and ş is given by Ewe (0,10 p(w) WWW, (W,,oI)),) a mixture of T-dimensional isotropic Gaussian distributions with means in {0, 1)"² sampled according to Bgg, T). Throughout all experiments, we use 1M independent Gaussian samples to compute the discrete prior of size |z|, the base probability of reconstruction success, K, i8 given as 1/1n]. Estimating 7 is cheap; setting T= 1 and using a 2.3 GHz 8-Core Intel Core i9 CPU it takes 0.002s to estimate with 10,000 samples. This increases to 0.065s, 0.196s, and 2.084s with 100,000, 1M, and 10M samples. The estimate sensitivity is also small: for the experimental parameters used in Figure at 10, over 1,000 different calls to Algorithm|] | the standard deviation of estimates is < 0.019 using 10,000 samples, and 0.0017 using 1M samples.
estimation of given by the procedure in Algorithm [ and because
B Visualization of reconstruction attacks on MNIST and CIFAR-10
In Figure 6
we give selection of examples for the gradient- gradient-based reconstruction attack presented in Section and plotted in Figure !
C Does the model size make a difference to the prior-aware attack?
Our results on MNIST and CIFAR-10 suggest that the model size does not impact the tightness of our reconstruction attack (lower bound on probability of success); the MLP model used for MNIST has 7,960 trainable parameters, while the WRN-28-11 10 model used for CIFAR-10 has 36.5M. We systematically evaluate the impact of the model size on our prior-aware attack by increasing the size of the MIP hidden layer by factors of ten, creating models with 7,960, 79,600, and 796,000 parameters. Results are given Figure where we observe almost no difference in terms of attack success between the different model sizes.
15

---

520000 prbee
4.8
Succss probestle
6.3
Upper Randen guese
stark Rundon punce
Price Rando gunst
60
(a) Width: 10.
(b) Width: 100.
(c) Width: 1000.
Figure 7: Comparison of model sizes on reconstruction by varying the hidden layer width in two
layer MLP.
12
0.8
2.8
0.
Pro-oweree
Crddeni-oaed stack
bound Srodien boses atook
0.2
Dias socee ateex
20
10*
10
107
10
10
127
(a) Prior size 2.
(b) Prior size is
(c) Prior size 128.
Figure Comparison of prior-aware and gradient-based attack for different prior sizes.
D Comparing the gradient-based attack with the prior-aware attack
Our experiments have mainly been concerned with measuring how DP affects adversary's ability infer which point was included in training, given that they have access to all possible points that could have been included, in the form of discrete prior. This experimental set-up departs from Figure [ where we assumed the adversary does not have access to a prior set, and so cannot run the prior-aware attack described in Algorithm 2 Following on from results Section 4.1 transform these gradient-based attack experimental findings into probability of successful reconstruction by running a post-processing conversion, allowing us to measure how the assumption of adversarial access the discrete prior affects reconstruction success. We run the post-pne post-processing conversion in the following way: Given a target sample 2 and a reconstruction & found through optimizing the gradient based loss in Equation ① we construct prior consisting of z" and the MNIST dataset, where
randomly selected points from 10. We then measure the I.2 distance between and every point in this constructed prior, and assign reconstruction a success if the smallest distance is with respect to z. For each target =², we repeat this procedure 1,000 times, with different random selections of size 1, and overall report the average reconstruction success over 1,000 different targets.
This allows
compare the gradient-based attack (which is prior "unaware") directly our prior-aware attack. Results are shown in Figure 8 where we vary the size of the prior between 2, and 128. In all cases, we see an order of magnitude difference between the gradient- based and prior- prior-aware attack in terms of reconstruction success. This suggests that if we assume the adversary does not have prior knowledge of the possible set of target points, the minimum value of necessary to protect against reconstruction attacks increases.
E Effects of the threat model and prior distribution on reconstruction
The ability to reconstruct a training data point will naturally depend on the threat model in which the security game is instantiated. So far, we have limited our investigation to align with the standard adversary assumptions in the DP threat model. We have also limited ourselves to a setting where the prior is sampled from the same base distribution as D.. These choices will change the performance of our attack, which is what we measure next.
Prior type. We measure how the choice of prior affects reconstruction in Figure 9 We train models when the prior from the same distribution as the rest the training set (MNIST), and when the prior is sampled random noise. Note, because the target point 2" is included in the prior, this means
16

---

1.0
Success probability
0.8
Upper bound
0.6
Prior-aware attack (MNIST prior)
Prior-aware attack (Noise prior)
0.4
Random guess
0.2
0.0
1
5
10
15
20
25
30
35
40
Figure 9: Comparison of how the choice of prior, affects reconstruction success. The prior is selected from a set examples sampled from MNIST or uniform noise (that has the same intra-sample distance statistics the MNIST prior).
we measure how reconstruction success changes when we change the distribution the target was sampled from. One may expect that the choice of prior make difference to reconstruction success the attack relies on distinguishability between D. and 2 with respect to some function operating on points and model parameters (e.g. the difference in loss between points in D. and z²). However, we see that there is little difference between the two; both are close to the upper bound.
On reflection, this is expected so the choice of prior may impact our probability of correct inference if this choice affects the probability that point will be clipped, or if points in the prior have correlated gradients. We explore how different values of clipping, C, can change reconstruction success probability in Appendix K
objective is simply the sum of samples from Gaussian, and
Knowledge of batch gradients. The DP threat model assumes the adversary has knowledge of the gradients of all samples other than the target 2". Here, we measure how important this assumption to our attack. We compare the prior-aware attack (which maximizes Σ (clipc(( ((2)). 9t)) against the attack that selects the 2; maximizing Di= (clipo (Vo, ((z))) gt), where the adversary does not subtract the known gradients from the objective.
In Figure 10 we compare, in full-batch setting, when [D] is small (set to 4), and see the attack does perform worse when we do deduct known gradients. However, the effect more pronounced as [.]| becomes larger, the attack completely fails when setting it to 128. This is somewhat expected, as with larger number of samples a batch highly likely there are gradients correlated with the =" target gradient, masking out its individual contribution and introducing noise into the attack objective.
F Improved prior-aware attack algorithm
As explained in Section 4.3 the awirr-aware attack Algorithm does not account for the variance introduced into the attack objective in mini-batch DP-SGD, and so we design more efficient attack specifically for the mini-batch setting. We give the pseudo-code for this improved prior-aware attack in Algorithm
17

---

1.0
Upper bound
Success probability
0.8
- Prior-aware attack
Prior-aware attack (No subtract gradients, (D-|-4)
0.6
-
0.4
Prior-aware attack subtract gradients, [D-|=128)
*
0.2
Random guess
0.0
5
10
15
20
25
30
35
40
Figure 10: line with the DP threat model, our attack in Algorithm 2 assumes the adversary can subtract known gradients from the privatized gradient. We measure what effect removing this assumption has on reconstruction success probability. When the size of the training set small, removing this assumption has a minor effect, while reconstruction success drops to random with larger training set size.
Algorithm's 3 Improved prior-aware attack
Input:
Discrete prior π = {z1..... 2n Model parameters {01, 0y...., 0r Privatized gradients (with known gradients subtracted) {Ø1..... 9r }. sampling probability q, function that takes the top qf" values from a set of observed gradients top,r
Observations: O ()
Output: Reconstruction guess 2 E
for i E [1,2,... ... do
R - 0
for 1 [1, .., T do
R[1 - (clipo Vo, E(0,, z)),
end for
R t top (R)
Oli] sum(R)
end for
arg max
return 1 π
G Alternative variant of the prior-aware attack
Here, we state alternative attack that uses the log-like ligelikelihood to find out which point in the prior set is used for training. Assume we have 7 steps with clipping threshold C 1, noise a, and the sampling rate is g.
Let -1,--.,9r be the observed gradients minus the gradient of the examples that known to be in the batch and let 4,...,,y lT be the &2 norms of these gradients.
g be the clipped gradient of the example on the For each example in the prior set let gi.... .i...., intermediate model. Also let ,i,...,, 15, be the Eg norms of (ğ1 - gi)..... (ūr - 9
Now we describe the optimal attack based on 1,. For each example z, calculate the following:
-015)2+13
2.2 ). It is easy to observe that this is the log probability of outputting the steps conditioned on 2 being used in the training set. Then since the prior is uniform over the prior set, choose the with maximum 8, and report that the example in the batch.
8= Eiery In(1 - + ge
In fact, this attack could extended to the non-uniform prior by choosing the example that maximizes S2 Pa. where is the original probability of 2.
18

---

H
Comparison with Guo et al. (2022b)
1.0
Guo et (2022b)
0.8
Guo et (2022b)
(Monte-Carlo approx.)
Advantage
0.6
Ours
0.4
0.2
0.5
1.0
1.5
2.0
2.5
3.0
Figure 11: Comparison of our upper bound on advantage (Equation (4) with Guo et al. (2022b) as function of a for a uniform prior of size ten. We use single step of DP-SGD with mini-batch subsampling, and use 100, 000 samples for Monte-Carlo approximation.
Table 2: Comparison of our upper bound on advantage (Equation (4) with Guo al. (2022b) and the Guo et al. (2022b) Monte-Carlo approximation (abbreviated to MC) as function of for uniform prior size ten and one hundred.
Prior size
Method
Advantage upper bound
0.5
1.5
2
2.5
3
Guo ct al.
2022h
0.976
0.593
0.380
0.274
0.213
0.174
Guo el at.
20226
(MC)
0.771
0.397
0,257
0.184
0.144
0.118
Ours
0.737
0.322
0.189
0.128
0.099
0.080
Guo et
2022h
0.861
0.346
0.195
0.131
0.097
0.076
100
el
20720
(MC)
0.549
0.081
0.062
0.049
0.362
0.077
0.035
0.024
0.018
0.012
Recently, Guo et al. (2022b) have analyzed reconstruction of discrete training data. They note that DP bounds the mutual information shared between training data and learned parameters, and use Fano's 's inequality to convert this into bound on reconstruction success. In particular, they define the advantage of the adversary as
Adv Padversary success
PT
[0, 1].
maax
where p!aax is the maximum sampling probability from the prior, and Padversayy success is the probabil- ity that the adversary is successful inferring which point in the prior was included training. They then bound the advantage by lower bounding the adversary's 's error == -1- Padversary success and by appealing to Fano's inequality they show this can be done by finding the smallest E [0, 1] satisfying
f(t) (m) T(=;; w) log + / log((T]]
log(1
(5)
< 0.
where w is output the private mechanism, H(T) ((T) is the entropy of the prior, and I(T; w) is the mutual information between the prior and output of the private mechanism. For an (a. RDD mechanism, (TT; w) < e, and so [(T;; w) can be replaced by in Equation (5). However, Guo et al. (2022b) show that for the Gaussian mechanism, this can improved upon either by using Monte-Carlo approximation of / [ w) - this involves approximating the KL divergence between a Gaussian and
a Gaussian mixture - or by showing that / (T;; w) < |. |T| pz_ log
pr + (1 ph) exp
2
19

---

where A is the sensitivity of the mechanism, and p is the probability of selecting the ith element from the prior. We use a uniform prior in all our experiments and so (T) log and
P'a
[
We convert our bound on success probability to advantage and compare with the Guo al. (202bb) upper bound (and its Monte-Cate approximation) in Figure 11 and Table 2 and note our bound is tighter.
I Experiments with very small priors
Our experiments in Section and Section 4.3 were conducted with an adversary who has side information about the target point. Here, reduce the amount of background knowledge the adversary has about the target, and measure how this affects the reconstruction upper bound and attack success.
We do this in the following set-up: Given a target z, we initialize our reconstruction from uniform noise and optimize with the gradient-based reconstruction attack introduced in Section to produce
2. We mark E as successful reconstruction of = if Ei= T[=[[] =[(] 5] 2 p. where p [0, 1), is the data dimensionality, and we set 255 the reconstruction as successful if || 2||00 < 8, and for < 1, then at least fraction values in 1 must be within an txx. ball of radius 5 from 2. Under the assumption the adversary has no background knowledge of the target point, with reconstruction is given by (2x32/250) dp - if p 1, for MNIST and CIFAR-10, this means the prior probability of a successful reconstruction 9.66 x 10 173 and 2.96 x 10 1850 respectively.
in our experiments. If p this means we mark
32 and a uniform prior, the prior probability of
255
We plot the reconstruction upper bound compared to the attack success for different values of in Figure We also visualize the quality of reconstructions for different values of p. Even for p = 0.6, where 40% of the reconstruction pixels can take any value, and the remaining 60% are within an 255 from the target, one can easily identify that the reconstructions look visually similar to the target.
absolute value of 32
20

---

Upper bound
Upper bound
Attack with fraction pixels in t. ball: 0.8
Attack with fraction pixels t. ball: 0.8
Atlack with fraction pixels in t. ball: 1.0
Allack with fraction pixels in t. ball: 1.0
1.0
2.0
probabilty
0.8
probabilit
0.8
0.6
0.6
0.4
0.4
0.2
0.0
0.0
10a
10a
10a
10a
10
107
10a
10a
10º
10a
102
10
102
Comparison of reconstruction success under very small prior for MNIST, where we judge a reconstruction as successful if at least pixels are within an absolute distance of 32 of the target.
Comparison of reconstruction success under very small prior for CIFAR- 10, where we judge reconstruction as successful at least pixels are within absolute distance of 32 of the target.
253
255
62% plante w thin
60% plants within fwl
1038 pkecss within
bal
0 7
8
2
7
/
6
100% sboels within ball
Original
8
2
7
6
Original
(c) MNIST examples reconstructions where at least
(d) CIFAR-10 examples of reconstructions where at pixels are within absolute distance of 32 of the least pixels within absolute distance of 32 the target.
253 of
253
target.
Figure 12:
Comparison of reconstruction success under very small prior. The prior probability of success for MNIST and CIFAR-IO 9.66 10-475 443 and 2.96 10-1850 respectively.
J Discussion on related work
Here, we give a more detailed discussion of relevant related work over what is surfaced Scction ! and Section 2
DP and reconstruction. By construction, differential privacy bounds the success of membership inference attack, where the aim is to infer if a point was in or out of the training set. While the connection between membership inference and DP well understood, less is known about the relationship between training data reconstruction attacks and DP. A number of recent works have begun to remedy this in the context of models trained with DP-SGD by studying the value of required to thwart training data reconstruction attacks (Bhowmick et al. 2018 Balle et al. 2022 Guo et al., 2022a b Stock et al., 2022). Of course, because differential privacy bounds membership inference, it will also bound ones ability to reconstruct training data; if one cannot determine if 2 was used training, they will not able reconstruct that point. These works are interested both formalizing training data reconstruction attacks, and quantifying the necessary required to bound its success. Most of these works share a common finding the value needed for this bound much larger than the value required to protect against membership inference attacks (< 10 in practice). If all other parameters in "y /Togo())) remain fixed, scale of noise we add to gradients, which turn results models that achieve smaller generalization error than models trained with SP-SGD that protect against membership inference.
see that larger value of reduces the
The claim that protection against membership inference attacks also protects against training data reconstruction attacks glosses over many subtleties. For example, if was not included in training it could still have non-zero probability reconstruction if samples that are close to were included in training. Balle al. (2022) take the approach of formalizing training reconstruction attacks in
21

---

Bayesian framework, where they compute a prior probability of reconstruction, and then find how much more information an adversary gains by observing the output of DP-SGD.
Balle et al. 2022) use an average-case definition of reconstruction over the output of a randomized mechanism. In contrast, [howmick et al. (2018) define worst-case formalization, asking when should an adversary not be able to reconstruct a point of interest regardless of the output of the mechanism. Unfortunately, such worst-case guarantees are not attainable under DP-relaxations like (e, 6)D and RDP, because the privacy loss is not bounded; there is a small probability that the privacy loss will be high.
Stock et al. ) focus on bounding reconstruction for language tasks. They use the probability preservation guarantee from RDP to derive reconstruction bounds, showing that the length of secret within a piece of text itself provides privacy. They translate this to show a smaller amount of DP noise is required to protect longer secrets.
While Balle et al. (2022) propose Bayesian formalization for reconstruction error, Guo et al. (202a) propose frequentist definition. They show that if M is (2, e)-RDP, then the reconstruction MSE is lower bounded by Σ (a)m,/2//ddeee--/ where diam; (Z) is the diameter of the space Z in the ith dimension.
Gradient inversion attacks. The early works of Wang al. (2019) and Zhu al. (2019) showed that one can invert single image representation from gradients of deep neural network. Zhu et al. (2019) actually went beyond this and showed one can jointly reconstruct both the image and label representation. The idea is that given a target point 2, a loss function e, and an observed gradient (wrt to model parameters 0) 9s Vg (0, 2). to construct & such that
arg ming-1lg:- 9ell- The expectation is that images that have similar gradients will be visually similar. By optimizing the above objective with gradient descent, Zhu et al. (2019) showed that one can construct visually accurate reconstruction on standard image benchmark datasets like CIFAR-10.
Jeon al. (021): ): Yin al. (2021): ): Jin al. (2021) : Huang al. (021): Geiping al. (2220)
proposed number of improvements over the reconstruction algorithm used in Zhu et al, (2019; : they showed how to reconstruct multiple training points in batched gradient descent, how optimize
against batch normalization statistics, and incorporate priors into the optimization procedure, amongst other improvements.
The aforementioned attacks assumed an adversary has access to gradients through intermediate model updates. |Balle et al. (2022) instead investigate reconstruction attacks when adversary can only observe a model after it has finished training, and propose attacks against (parametric) ML models under this threat model. However, the attack they construct computationally demanding as it involves retraining thousands of models. This computational bottleneck is also a factor in Haim al. (2022), who also investigate training data reconstruction attacks where the adversary has access only to final model parameters.
K More experiments on the effect of DP-SGD hyperparameters
We extend on investigation into the effect that DP-SGD hyperparameters have reconstruction. We begin by varying the clipping norm parameter, C, and measure the effect on reconstruction. Following this, we replicate our results from Section 4.3 (the effect hyperparameters have on reconstruction at a fixed c) across different values of c and prior sizes, [T].
K.1 Efffet of clipping norm
we see that in essence we are either summing a set of samples only from Gaussian centred at zero or Gaussian centred at C2, If the gradient of the target point is not clipped, then this will reduce the sum of gradients when the target included in batch, the Gaussian will be centred that the objective is not maximized by the target point.
we look again at our attack set-up in Algorithm 2
value smaller than C This will increase the probability
We demonstrate how this changes the reconstruction success probability by training a model for 100 steps with a clipping norm of 0.1 or 1, and measuring the average gradient norm of all samples over all steps. Results are shown in Figure B We see at C' 0.1, attack is tight to the upper bound,
22

---

1,0
-X- C 0.1
0.8
-
C= 1.0
probability
0.8
gradient
*
Upper bound
0.6
Prior-aware attack. C 0.1
Prior-aware 1.0
Random guess
0.0
20
35
5
10
15
20
25
30
35
40
Average gradient norm (over all samples steps) (h) Reconstruction success probability for different for different values of at C' = 0.1 and =
values of
0.1 and C' =.
Figure 13:
Comparison of how reconstruction success is changes with the clipping norm, C. We that if examples have a gradient norm smaller than C, and so are not clipped, reconstruction success probability becomes smaller.
and the average gradient norm is 0.1 for all values of all individual gradients are clipped. When C'= = 1, the average gradient norm decreases from 0.9 at = to 0.5 at e = 40, and we see larger gap between upper and lower bounds. The fact that some gradients may not be clipped is not taken into account by our theory used to compute upper bounds, and so we conjecture that the reduction is reconstruction success is real effect rather than weakness of our attack.
We note that these findings chime with work on individual privacy accounting (Feldman Zrnic 2021 Yu et al.) 2022 Ligett et al.) 2017 Redberg & Wang 2021). An individual sample' privacy loss often much smaller than what is accounted for by DP bounds. These works use the gradient norm of an individual sample to measure the true privacy loss, the claim is that if the gradient norm is smaller than the clipping norm, the amount of noise added is too large, as the DP accountant assumes all samples are clipped. Our experiments support the claim that there is disparity in privacy loss between samples whose gradients are and are not clipped.
K.2 More results on the effect of DP-SGD hyperparameters at a fixed e
In Section 4.3 we demonstrated that the success of reconstruction attack cannot be captured only by the (e, )) guarantee, when e = 4 and the size of the prior, म. is set to ten. We now observe how these results change across different and |r], where we again fix the number of updates T 100, C== 1, vary q E [0.01, 0.99], and adjust a accordingly.
Firstly, in Figure 14 we measure the upper and lower bound ((improved) prior-aware attack) on the probability of successful reconstruction across different q. all settings, we observe smaller reconstruction success at smaller y. where the largest fluctuations in reconstruction success are for larger values of We visualise this in another way by plotting against q and report the upper bound in Figure 15 Note that the color ranges in Figure 15 independent across subfigures.
L Estimating λ from samples
Here, we discuss how to estimate the base probability of reconstruction success, K, if the adversary can only sample from the prior distribution.
Let be the empirical distribution obtained by taking independent samples from the prior and
A ( (n) be the corresponding parameter for this discrete approximation to this can be computed using the methods sketched Section Then we have the following concentration bound.
Proposition 6. With probability
- k/2 we have
&
K
<
The proof is given in Appendix M
23

---

Upe lood
Upe lood
kood pols
poss
pols
(a)
(b) C 4.
2.
(C)
8,
2.
(d)
16, 7
(e) 1, 10.
4, 10.
8, m 10.
(h) 16, 10.
pas
( 1, |||| 100.
c 4,
100.
(k) |
100.
(1)
16, |
100.
Figure 14: How the upper bound and (improved) prior-aware attack change as function of q at fixed value of and prior size, [x]. The amount of privacy leaked through a reconstruction at fixed value of can change with different g.
M Proofs
Throughout the proofs we make some of our notation more succinct for convenience. For probability
distribution w we write (F) = [E], and rewrite B,, (14, v) (T [E] s.t. [F] S x}
Su) p( (E). Given distribution and function taking values in [0, 1] we also write
w( ()) = Ex [x(X).
M.1 Proof of Theorem 2
We say that pair of distributions (H, v) is testable if for all K [0, we have
inf (1 - m())) = inf (1 ((E)) 5(
"(E)
where the infimum on the left over all [0, va-vude measurable functions and the one on the right over measurable events (i.e. {0, va-val functions). The Seymann-Pearson lemma (see e.g. Lehmann Romano (2005)) implies that this condition is satisfied whenever the statistical hypothesis problem of distinguishing between y and admits uniformly most powerful test. For example, this is the case for distributions on Idd where the density ratio p/v is a continuous function.
Theorem 7 (Formal version of Theorem 2). Fix n and p. Suppose that for every fixed dataset D. there exists a distribution μ.D, such that suPoeeupp(s) Bx (xD,, vDD) & Be(pD, VDD) for all x E [0, 1]. If the pair (p, v) is testable, then M is (n. -ReRo with
7 = sup
PD. PD.(E) D. vp. (M)
sup
The following lemma from Dong et al. (2019) will be useful.
Lemma 8. For any and v, the function = inf u())) is convex in [0, 1J.
Lemma 9, For any testable pair (H,,V), the function Su u(E) is concave.
24

---

Proof. By the testability assumption we have
sup
(x))
sup 1a F))
'(E)Sx
v(ESS
sup (1 - ((E))
nBBSs
inf (E)
mB)S
inf (1 - (E)))
v(B)Sk
inf (1 u(o))
Concavity now follows from Lemma
Proof of Theorem Fix D. and let K (1)) throughout, Let also VD., = MDD, D.D
and μ PD.
Expanding the probability of successful reconstruction, get:
P PEw.WW-MDDUz2)102 R(W)) S r) = Ezzz Bxxonww.Mo..uuuyyll... R(W)) S n
Ezan B (DLL (2)) MIDL ([(,)((W)) S n)
EZ Ew [[ R(W)) <|
(z(WW Ilp R(w)) S n|
=EZnn Eww
v(W)
Now fix E supp(z) and let K3 = Pwwelp(2. R(W)) & n7). Using the assumption on j we get:
(=(W) v(W)
M=(W)
Ew
Ilp(2, R(w)) S <nl < sup v(E)SK,
Ew
IiW E)
(By definition of x)
v(W)
sup Ew-n, [u[W e E'l u(F)SNs
sup (E) v(E)SK,
sup μe (E)) (F)SSk
(By definition of and v².)
Finally, using Lemma 9 and Jensen's inequality on the following gives the result:
Ezaa [Kz] = Ezzxl' lP (p(2, R(W) S nl
Ew 1p(Z, R(W) S n]
Ew
K
M.2 Proof of Corollary 4
Here we prove Corollary We will use the following shorthand notation for convenience: μ
(B 4), o2) and v == = (0, If. To prove our result, we use the notion of TV..
Definition 10 (Mahloujifar et al. 2022)). For two probability distributions wi (.) and wz TV, is
defined as
TV. (V))))))))
(w)(x) a (=-(zx)) dx.
Now we state the following lemma borrowed from Mahloujifar al. 2022).
Lemma 11 (Theorem 6 in Mahloujifar al. (2022)) Let VD., MD, be the output distribution of DGD applied to D. and D respectively, with noise multiplier a,, sampling rate q. Then we have
[V. = TVa(M,))
25

---

Now, we state the following lemma that connects TVa to ulow-up function.
Lemma 12 (Lemma 21 in Zhu et al. (2022.)) ). For any pair of distributions WI, we have
sup W2 w2(E) [E) = inf min 0, 0,a.kt TV (Va w2)
+ +
(K a>1
2
2a
Since (VD. (DD)) is bounded by (V, ()) for all a, therefore have
sup (B)S.
PD_ (E) S sup
m(E)
(EESSN
M.3 Proof of Proposition
Recall K 2 P Pz~= [p( 20) I 17 and R sup 2 Z- [p([],ZZZ =0) n/. Let
P [p( Z, 2) E 17 and fig = P2~* Tp (p Z 2) S 17). Note RSg is the sum of i.i.d. Bernoulli random variables and E3 [R=] Kg. Then, using multiplicative Chernoff bound, we see that for fixed
the following holds with probability at least -N222//2
R₂
K₂
Applying this to x" arg sup P Zan (p (0, z0) probability least 1 e NN/2
I nl we get that the following holds with
Rig
S
I
1 1-
1 -
M.4 Proof of Proposition
Let +yy 2 Let E1 be the event that Prr > 2) k Hoefding bound we have IP[Ei] < -2 Now note that since is Gaussian mixture, we can write EiE(2r) asf4, where each is a Gaussian (Vcc,, o)) where |a12 S vT. Now let Ts (WW)//(W) By holder, we have E[r²] S E..EE We also now that E[r"] S eT. therefore, [6 S e", Now let E2 be the event that [E[r [(r > =)] - 7'1 2 т. Since the second moment of r is bounded, the probability of Es goes to zero as N increases. Therefore, almost surely have
By applying Chernoff-
sup ((E) - - I lim Y <
sup
(EE) +
(K
Sk)
Now by pushing 0 and using the fact that μ and v are smooth we have
lim n' lim sup N +-0 v(E)SAtT
((E) + sup ((E). v(E)S
26

---

3359
30-
20
23
4143
-00
0013
-0012
12
26-1
207
20-4
12-3
26-1
(a) c |,|m|
1,
10.
(c)
100.
2ouse
0.2
2.00
11
2.002
13
0.37
00000000
3.58
33-
(d) e 2, ||| =
( = 2, | 10.
(f) e = 2, | = 100.
0.88
2258
109
304
15"
g c = 4, | = 2.
(h) = 4, ||| = 10.
(i) c = 4, |T
100.
mo Stoper bosdd
123
10+
10
114
10
224
(i) c 8, ||| 2.
(k) 8, ||| 10.
(l) = 8, |
100.
2.00
103
10
26-1
164
10
(m) c 16, |
(n) c 16,
10.
(0) c 16, |
100.
traed
02
-14
18
10-
23-4
222
2244
10-4
(p)
32, |m|
(g) c 32,
10.
(7) 32, |
100.
Figure 15: How the upper bound changes as function of & and fixed value of and prior 100. The probability of a successful reconstruction can vary widely with different values of q. For example, at 32 and |<| 100. at 0.01 the upper bound is 0.4 and at = 0.99 it Note that the color ranges are independent across subfigures.
size, |=|. and setting
27


Reviews:
[{"review_id": "8HgS6B5q21", "reviewer": "Reviewer_paNh", "summary": "This paper is about the bounds of differentially private training for protection against data reconstruction attacks. This paper provides an upper bound on the success of any reconstruction attack against DP-SGD. Also it includes experiments that match the expected bounds. The experiments also include different settings that lead to various success rates for reconstruction.", "questions": "Unfortunately, I'm not the expert in this field. I'm curious to learn from the authors about how important these results (theorems and experimental results) are, as it is not easy to be interpreted from the written contributions.", "limitations": "The authors are encouraged to discuss how their findings might be used to help develop more sophisticated reconstruction attacks.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* This paper is well written. It is easy to follow the paper with the background, main theorems (with proofs in supplementary), and experimental settings.\n\n* This paper provides sounded proofs for the theorems.\n\n* This paper provides enough context on the problems and how they approach the problems differently.\n\n* There are sufficient experiments to support the theorems and bounds.", "weaknesses": "The WideResNet in the experiments is pretrained on ImageNet. It would be a stronger paper if the authors also perform experiments on ImageNet. I suppose while the bounds should also apply to ImageNet, the higher resolution images might also affect the reconstruction success rate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review, paNh. We’ve answered your comments and questions below.\n\n> Why pretrain on ImageNet.\n\nExcellent question. There are a number of reasons we chose to pretrain on ImageNet. Reporting results directly on ImageNet is technically possible but computationally challenging.\n\n- In the non fine-tuning regime (DPSGD on ImageNet with no pre-training on public data), the state-of-the-art test accuracy at DP epsilon=8 is around 32%. We do not believe instantiating our bounds and attacks on such a poor model is interesting.\n- Unlike in standard training, CIFAR-10 is still a very challenging dataset to train with DP and is an active benchmark within this research area (De et al. (2022), Bu et al. (2022), we can provide more references if desired), while ImageNet has been slightly less investigated due to the computational challenges of training on ImageNet with DP.\n- Even fine-tuning on ImageNet with DP (after pre-training on public data) is highly expensive (c.f. De et al. (2022)). We could instantiate our attack here, but if we want to report “average success of the attack” – which helps inform us of the average performance of the attack, rather than how well it performs on a specific training run –  we would need to re-run this training procedure hundreds of times (as we do in the paper), making this computationally challenging. We feel for this reason operating on state-of-the-art CIFAR-10 models is reasonable.\n- Other than the computational aspect, there is no specific challenge that makes training from scratch more interesting. Our upper bounds on reconstruction would be calculated in the exact same way (with different parameters), and our attack would also stay the same. For instance we can train a CIFAR-10 classifier from scratch with the exact same hyperparameters that we use for fine tuning (i.e. number of iterations, sampling rate, clipping threshold, and noise multiplier) and expect to see the exact same upper bound as the one for fine tuning, and very similar lower bound as well. Of course, in this setting the accuracy of the model will not be good, but there is nothing specific about training from scratch that makes the attack or the upper bound more interesting.\n\n> I'm curious to learn from the authors about how important these results (theorems and experimental results) are, as it is not easy to be interpreted from the written contributions.\n\nWe believe that this work makes a number of important contributions to analyzing the protection DP offers against privacy attacks.\n\n- At a high level, DP has mainly been analyzed with membership inference attacks (i.e., can we detect if an example was used to train the model?). We know that for epsilon>2, membership attacks should always succeed against models trained with DP (the guarantee of protection becomes vacuous after this), but in practice it seems like models trained with epsilon up to 100 still protect against most privacy attacks. This motivated us to look at why larger epsilons can still protect against privacy attacks. Our work shows that large epsilons can provably protect against reconstruction attacks. The general rule of thumb for practitioners is to use an epsilon < 10, but with our work we have a more formal and granular way of deciding the acceptable epsilon to use. This will help with model utility – if a practitioner wants to train with DPSGD and only cares about protection against reconstruction attacks, our work shows they can use larger epsilons and still provably be robust to this attack. Model utility will benefit because training with larger epsilons means injecting less noise, which in turn, means more accurate models.\n- There have been other works that look into reconstruction attack bounds on DP (Guo et al. (2022)), but ours is the first to provide tight bounds for DPSGD (the algorithm that most people use in private deep learning).\n- More generally, it is rare that in privacy attack research one can show that a privacy attack on DP is efficient enough to reach the bounds predicted by theory on state-of-the-art models. There is usually a compromise to be had, either by reporting loose bounds (Guo et al. (2022)) or running attacks on non state-of-the-art models (Balle et al. (2022) attacks only work on DP CIFAR-10 models with < 50% test accuracy). Either a practitioner can run our bounds to achieve almost tight reconstruction upper bounds, or implement our privacy attack, and use the result as evidence for the desired privacy or a proof for lack of privacy. This is reminiscent of the topic of auditing differential privacy, where there is an attack that tries to “audit” the proven upper bounds on privacy. One can look at our work as the first tight upper bound for reconstruction as well as the first auditing attack for reconstruction upper bounds.\n\nDe et al. \"Unlocking high-accuracy ...\" arXiv:2204.13650 (2022).\n\nBu et al. \"Scalable and efficient training ....\" NeurIPS (2022): 38305-38318.\n\nGuo et al. \"Analyzing privacy leakage in machine learning...\" arXiv:2210.13662, 2022b.\n\nBalle et al. \"Reconstructing training data..\" Security and Privacy, SP 2022"}, {"review_id": "b2IZUiPEDH", "reviewer": "Reviewer_wroj", "summary": "The paper proposes a novel bound on Reconstruction Robustness from DP training using a notion of a blow-up function. In order to use the bound, one needs to estimate the quantities $\\kappa$ (prior probability of reconstruction) and $\\gamma$ (blow-up between neighboring noise distributions) using Monte-Carlo methods. Compared to the prior bounds based on RDP, the proposed bound is tighter. The paper also introduces a new gradient-based that is shown to perform close to the bound, and investigates the impact of different DP-SGD hyperparameters on the bound and on the attack success.", "questions": "- How can one evaluate the accuracy of the upper bound given inherent error in the Monte Carlo estimates? Is there a way to provide an upper confidence bound at a given level of certainty as opposed to an asymptotic guarantee? Is 1M good enough?\n- What is the computational cost of estimating $\\gamma$ with 1M samples?\n- Is the notion of blow-up function new? Are there citations? Most bounds in DP rely on information-theoretic divergences --- is it related to a known divergence?\n- How exactly can the bound be used to reduce the required level of noise in DP-SGD if one were only concerned with reconstruction risks?\n- How can the attack be applied in federated learning scenarios?\n", "limitations": "Approximate nature of the bound in practice --- see weaknesses.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The paper proposes a significant improvement in bounding reconstruction attack risk in DP training. This is of practical importance, as **improved bounds on relevant privacy risks enable practitioners to calibrate their DP-SGD parameters to mitigate those risks** as opposed to relying on the $\\epsilon$ value which is hard to interpret.\n- The paper proposes a new reconstruction attack using gradient information.", "weaknesses": "*Approximate nature of the bound in practice.* The computation of the bound relies on a Monte Carlo procedure that is only shown to converge to the optimal solution asymptotically. The paper does not provide methods to estimate the accuracy of the resulting numeric value of the bound for a given number of MC algorithm samples.\n\nUPDATE (August 10): I update my score to 8 as the weakness above has been clarified in the response.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks wroj for the in-depth review, we’ve tried to answer and clarify your points below.\n\n> How can one evaluate the accuracy of the upper bound given inherent error in the Monte Carlo estimates? Is there a way to provide an upper confidence bound at a given level of certainty as opposed to an asymptotic guarantee? Is 1M good enough?\n\nOf course the review is correct that the bound currently only holds asymptotically. We can provide confidence intervals for the bound as well, using two types of inequalities. Note that our algorithm has two points of error: 1) The first step is the potential gap between the empirical quantile and the population quantile. . To bound this distance we can use the DKW inequality which provides uniform concentration for each quantile. In particular, we can show that the error of quantile estimation is at most $2e^{-2n\\eta^2}$, where $n$ is the number of samples and $\\eta$ is the error in calculation of the quantile. Specifically, with a million samples, we can make sure that with probability 0.999 the error of quantile estimation is less than 0.002 (we can make this smaller by increasing the number of samples). Then, we also need to account for the error of the second step which is the mean estimation. Here, we can use the Bennet’s inequality that leverages the bounded variance of the estimate. In all our bounds, we can show that the error of this part is also less than 0.01 with probability 0.999. We will be happy to add these analyses to the paper. \n\nFor the experimental settings reported in the paper (with T=1), the time to compute $\\gamma$ on our local CPU is as follows:\n- 10,000 samples = 0.002s\n- 100,000 samples = 0.064s\n- 1,000,000 samples = 0.196s\n- 10,000,000 samples = 2.084s\n\nWhen T=100, with 1,000,000 samples it takes ~5s to compute $\\gamma$ on a CPU. On a GPU it takes <<1s.\n\n> Is the notion of blow-up function new? Are there citations? Most bounds in DP rely on information-theoretic divergences --- is it related to a known divergence?\n\nThis notion is tightly related to the notion of trade-off function defined (e.g. see Definition 2,1 in the GDP paper [DRS]). Precisely, blow_up(x)=1-trade_off(x). Note that the trade-off function has more information than a single divergence, because it contains information about TV_a (or hockey_stcik divergence) for all values of a. This is what enables a tight calculation of the upper bound. \n\n[DRS] Dong J, Roth A, Su W. Gaussian Differential Privacy. Journal of the Royal Statistical Society. 2021 Jan.\n\n> How exactly can the bound be used to reduce the required level of noise in DP-SGD if one were only concerned with reconstruction risks?\n\nOur work shows that if one is concerned with reconstruction risk, they can calibrate epsilon / level of noise based on the expected risk as long as they can compute a sensible prior. This is likely going to be context and task specific. For example, do we assume the adversary has a lot of side-knowledge (prior will be larger) or completely uninformed (smaller prior)? These questions are difficult to answer in any detail without getting into specifics of the type of data, the threat model the developer is concerned with and the context in which DP will be implemented. We hope that follow up work can dig into these details for specific use cases of DP.\n\nWith all else being equal, we can quantify the increase in risk to reconstruction attacks from before, to after the model has been trained. If one starts with a *small risk*, then DP training with a larger epsilon will not increase this risk *by much*. What *by a small risk* is, and what an acceptable value of *by much* is, will be specific to the application in which DP is applied.\n\n> How can the attack be applied in federated learning scenarios?\n\nGreat question. The attack requires access to updates/gradients (permitted under the DP threat model), so as long as this information is available the attack is applicable. In most FL settings this information is available and so will be applicable there. \n"}, {"review_id": "JEhZws1PeP", "reviewer": "Reviewer_j4Wo", "summary": "This paper pertains to a line of work exploring reconstruction attacks (RA) as a complement to the standard membership inference attacks (MIAs) for evaluating the privacy leakage of ML models. The idea is that a model can be made resistant to RAs for large values of the privacy budget epsilon for which it would not be resistant to MIAs. In cases where membership leakage is not considered a privacy issue, the model might be both “safe” as per low RA risk and useful, since less noise would have to be added. Resistance to RAs can be studied theoretically (by upper bounding the RA success in the worst case) and empirically by developing ever stronger attacks. This work proposes contributions on both fronts for models trained using DP-SGD. On the attack front, two new reconstruction attacks are proposed. The first one is based on the gradients of the model after every iteration and the second one tries to infer the correct record among n candidates. On the theoretical front, a new upper bound for RA success is proposed, which is much better than the previous bound. Finally, the attack initially developed for models trained with gradient descent (no mini-batches) is extended to the mini-batch case. The attack success is shown to be sensitive to the mini-batch size.", "questions": "1. How sensitive is the empirical upper bound to the parameters of Algorithm 1 used to estimate it, e.g, N? \n2. Is the gradient-based attack the first one to successfully reconstruct records from models trained using DP-SGD? The authors state that Balle et al (2022)’s attack doesn’t succeed, but it isn’t clear in the text whether other attacks from prior works succeed. Clarifying this aspect would better highlight the significance of the contribution.\n3. Fig. 3 suggests that even with a very strong prior (size=2) there is a gap of up to 5% depending on the value of epsilon, and the gap can be much larger for larger prior size. Can the authors give potential reasons why the prior-aware attack is not tight in these scenarios and potential directions for improving the success of attacks? It seems that the threat model cannot be made stronger, what about the method? Or should future work focus on tightening the theoretical upper bound?\n4. Prior-aware attack: Do all of the n candidate records belong to the same class as the target record? The attack could be made artificially easier by selecting candidates with a different label. Similarly, the authors mention that the prior could be motivated by the adversary narrowing down the list of candidates before running the attack. Have the authors explored a list of candidates that are the most similar to the target itself? \n", "limitations": "The paper doesn’t mention limitations or broader societal impacts but studies the privacy of ML models, a topic with positive societal impact.\n", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The gradient-based and prior-aware attack methodologies both seem sound, are well explained and motivated, and the authors explored different alternatives to the proposed formulations. The attacks present sufficient novelty.\n\nThe empirical evaluation is extensive which is highly appreciated.\n\nEmpirically, the new theoretical upper bound on the success of reconstruction significantly improves upon the previous bound of Balle et al. (2022) as shown on Figure 2. Theoretically, the contribution seems significant too, although I did not verify the proof and I found the hypotheses somewhat opaque.", "weaknesses": "1. Prior-aware attack: Conceptually, I am not convinced the 1 out of n classification is the right approach to frame the reconstruction problem. The goal of reconstruction is to extract a target record with limited prior knowledge about the record, i.e., reconstruct the record from scratch. The prior-aware attack changes the task to something quite different, by turning it into a distinguishing game, i.e., finding the right record among 2, 5, 10 etc. possible candidates (specifically, for 2 candidates, the task becomes equivalent to MIA under bounded DP). This means that the adversary already knows the record and the only uncertainty left is which one it is among a limited set of options. \n\n2. One problem with the prior-aware attack is that the prior can be made arbitrarily easy or hard. For instance, if the other records in the prior have a different label than the target record, which the adversary is assumed to already know (Appendix A), it is very easy to guess the right image. In the current experiments, do all of the records in the prior belong to the same class as the target record? Similarly, the authors mention that the prior could be motivated by the adversary narrowing down the list of candidates before running the attack. Have the authors explored a list of candidates that are the most similar to the target itself? \n\n3. The research gap addressed by the paper and the significance of the contributions aren’t clear. The empirical results seem solid, but how the findings translate to the real world is unclear. Perhaps the introduction could explain more the real-world implications of the findings. Eg what does it mean that when training a model with epsilon=10, an extremely strong attack (the prior-aware attack) exists that succeeds 60% of the time, 6x better than the random guess (Figure 2)? In light of the results of this paper, does there exist an epsilon such that the newly proposed, state-of-the-art RAs fail but utility remains very good?\n\n4. Clarity: I found Sec. 3.1 and 3.2 hard to follow. Theorem 2 makes some hypotheses but it’s very difficult for me to understand what these mean and whether they’re validated under real-world scenarios. Hopefully, a reviewer with expertise in DP can check these assumptions as well as the proofs, but regardless of this I think the authors should make these sections clearer and more accessible. \n\n5. Tightness of the upper bound: the authors claim that the upper bound is tight, and indeed Fig.2 shows that for epsilon=1, the upper bound and prior-aware attacks perform similarly. However, the upper bound is also very close to the random guess baseline, such that any better than random attack would appear to be tight. I am not convinced that we can conclude that the upper bound is tight, considering the large gaps shown on Figure 3. At least, some analysis or explanations are needed to better understand when the upper bound is tight and when it isn’t. \n\n6. Minor: Can the authors equalize the color maps on Fig. 5 and 15 so that e.g., yellow on the left becomes comparable with yellow on the right?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\n> Not convinced 1 out of n classification is the right approach to frame the reconstruction problem.\n\nReconstruction for reconstruction's sake is a naive view on the goal of privacy attacks. Successful reconstruction (in the reviewer's sense) implies privacy leakage, but lack thereof does not imply that the data is secure. For example, if the target image contains a car, an attacker might be interested in the digits of the license plate, not the pixels of the image of the car and its background. Thus, the 1 out of n formulation is the right approach to frame reconstruction from the point of view of studying privacy leakage (which is exactly what DP is trying to protect): if the license plate has 4 digits, the attacker is interested in which out of all possible 10000 combinations was present in the training dataset. What this formulation does is move away from the classical membership inference approach where the attacker has so much side information that they only need to infer one bit of information, to a setting where reconstruction requires the attacker to infer log(n) bits to perform reconstruction, where n represents who diffuse the adversary's prior is. Finally, we do have experiments outside of this framing (prior=1/(possible number of pixel configurations) in Appendix I).\n\n> The prior can be made arbitrarily easy or hard.\n\nWe view this as a positive aspect of the prior-aware attack! That we can calibrate our bounds based on the knowledge that the adversary might possess is something that we want in our reconstruction bounds. The adversary might just know that they are reconstructing a photo that is similar to CIFAR distribution (or within a certain class). These are different levels of prior that would lead to potentially different bounds through our framework. Our framework shows that if one can construct a reasonable prior probability of reconstruction, then we can estimate how the posterior probability of reconstruction will increase after training. We believe this flexibility is a core contribution of our work. Deciding if the prior is too easy or too hard is certainly an important question, but will be specific to the application to which one applies DP. \n\n>  Do all records in the prior belong to the same class? Have you explored a list of similar candidates?\n\nYes, and for the experiments on MNIST, the prior set looks almost identical to us. The L2 distance between images in the set is extremely small for e.g. class 1.\n\n> Epsilon where RA's defeated & utility is good?\n\nTo be clear, our main contribution is showing that if we can define a prior probability of reconstruction, then we can calibrate epsilon such that the posterior probability of reconstruction is bounded by some value. What a reasonable prior and posterior probability is will be use case dependent; some applications may be more risk averse than others. In general, unlike analysis DP with membership inference attacks (where any epsilon > 2 gives vacuous guarantees against the attack), we can show that for reconstruction, larger values of epsilon can give meaningful results.\n\n> Not convinced upper bound is tight.\n\nThis is fair. We will edit our wording to “tight in some cases” and “nearly tight in other cases”, unless the reviewer feels “nearly” is an unfair term here. Given the closeness in attack success and bounds in the middle bar of Fig 2 and (for eps < 10) in Fig 3, and in Fig 4 and Fig 5 we believe this is is fair. We would like to note that it is rare for a privacy attack on DP to achieve such close results to an upper bound, and so we feel these attacks do represent a real contribution. \n\n> Equalize the color maps?\n\nWill do.\n\n> Upper bound sensitivity\n\nFor the experimental parameters used in Fig 2 at eps=10, over 1000 different calls to Algorithm 1 we get:\n\n- N : Upper bound (avg +/- std)\n- 10,000 : 0.3358 +/- 0.0195\n- 100,000 : 0.3325 +/- 0.0062\n- 1,000,000 : 0.3304 +/- 0.0017\n\nSo anything above N=10,000 will give a reasonably non-sensitive upper bound. We also refer the reviewer to answer to wroj where we discuss how we can obtain confidence intervals for our bounds.\n\n> Is the gradient attack the first to successfully reconstruct records from models trained with DPSGD?\n\nOther works have looked at this problem but we are the first to (as far as we are aware):\n- Provide bounds specifically on DP-SGD. The main algorithm used in all of private deep learning, and show that our bound is much stronger than prior work (see Appendix H).\n- Design attacks that come to close to the upper bounds on state-of-the-art models. Other works either look at attacks on small convex models (Guo et al. 2022) or constrict their analysis to other domains like text or tabular data (Stock et al. 2022, Guo et al. 2023)\n\n> Reasons why prior-aware attack isn't tight / future directions.\n\nWe think the reason for larger gaps with larger priors is because there is a higher chance that two gradients from two different candidates are very similar. For example, if we have candidate gradient g_0 from a candidate point x_0 and candidate gradient g_1 from a candidate point x_1, if say x_0 and x_1 are both 1’s from MNIST that look similar then g_0 and g_1 will be similar, increasing the probability of a mistake in identifying the right candidate from the prior. As the prior size increases, the probability that this happens will increase. Looking into how to improve the attack to account for this could be a fruitful area for future work.\n\nBalle et al. \"Reconstructing training data with informed adversaries\". SP 2022\n\nCarlini et al. \"Membership inference attacks from first principles.\"  SP 2022\n\nGuo et al. \"Analyzing privacy leakage in machine learning via multiple hypothesis testing: A lesson from fano.\" ICML 23.\n\nGuo et al. \"Bounding training data reconstruction in private (deep) learning.\" ICML 22.\n\nStock et al. \"Defending against Reconstruction Attacks with R\\'enyi Differential Privacy.\" arXiv:2202.07623 (2022).\n"}, {"review_id": "Gzr3evt40k", "reviewer": "Reviewer_AUNf", "summary": "This paper explores reconstruction attacks within the threat model associated with the usage of DP-SGD. The study provides a tighter upper bound on the success rate of the reconstruction attacks than previous works. Additionally, the paper presents an attack that exploits a strong discrete prior and aligns closely with the provided bound.", "questions": "- A more structured presentation of the threat model should be provided for each method, including the baselines and the proposed one. It would be better to place such information in separate section(s), rather than interspersed among small, unstructured paragraphs in Section 2.\n\n- What defines a successful attack in the context of previous works aiming for approximate reconstruction instead of exact retrieval?\n\n- Providing more details in Section 3.2 would be beneficial, such as explicitly presenting the definitions of $\\mu$ and $\\nu$ in Algorithm 1. I would also expect that a relatively large number of samples (e.g., for $N$ and $n$) would be required to make the estimation precise, but such information seems to be missing in the submission.", "limitations": "- Possibly due to the presentation, I may have underestimated the technical and practical value of this submission. A clear claim about its key advantages over existing work should be provided in the revision.\n\n- I quickly scanned through the proofs and did not spot any obvious errors.\n\n- I didn't notice any discussion regarding the computational cost of the proposed method. I would expect such information to be included in the revision.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The investigation into the bounds against reconstruction attacks (under the usage of DP-SGD) is both valid and of practical relevance.\n- The proposal of a tighter bound and a strong attack is intriguing.", "weaknesses": "- The quality of the presentation could be largely improved. Currently, the main assumptions of the proposed attack, the primary algorithm, the evaluation setup, and the key novelty are vague.\n     - From the current submission, the bound appears to be a straightforward adaptation of the general DP bound to the reconstruction attack.\n     - The proposed attack seems to operate only under a strong, possibly unrealistic assumption. For instance, knowing the \"discrete prior\" (specific points from the dataset already) might be quite a strong assumption, potentially transforming the problem from \"reconstruction\" to a simpler \"matching\" task. And the assumption of batch gradient descent (instead of stochastic gradient descent) further introduces additional complications. While this could be useful in certain scenarios (e.g., auditing the privacy cost), explicit argumentation is needed (e.g., why the proposed method is superior to existing techniques for such tasks) to justify its practicality.\n\n- The scope of this submission seems rather narrow, particularly given the attack assumption which restricts the application scenario to be focused only on DP-SGD (may not even be applicable to SGD due to the \"batch\" GD assumption). This makes the attack itself not stand-alone useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review\n\n> The bound appears to be a straightforward adaptation of the general DP bound.\n\nWe respectfully disagree. Our reconstruction bound leverages the notion of blow-up/trade-off function and uses the concavity/convexity of this function in a novel way. The fact that our bounds significantly outperforms all the previous bounds in this domain shows that our upper bound is not a straightforward adaptation of the general DP bound. \n\n> Attack uses unrealistic assumptions. \n\nReconstruction for reconstruction's sake is a naive view on the goal of privacy attacks. Successful reconstruction (in the reviewer's sense) implies privacy leakage, but lack thereof does not imply that the data is secure. For example, if the target image contains a car, an attacker might be interested in the digits of the license plate, not the pixels of the image of the car and its background. Thus, the 1 out of n formulation is the right approach to frame reconstruction from the point of view of studying privacy leakage (which is exactly what DP is trying to protect): if the license plate has 4 digits, the attacker is interested in which out of all possible 10000 combinations was present in the training dataset. What this formulation does is move away from the classical membership inference approach where the attacker has so much side information that they only need to infer one bit of information, to a setting where reconstruction requires the attacker to infer log(n) bits to perform reconstruction, where n represents who diffuse the adversary's prior is. Finally, we do have experiments outside of this framing (prior=1/(possible number of pixel configurations) in Appendix I).\n\n> Assumption of batch gradient descent further introduces additional complications.\n\nWe have results on DPGD (full batch) and DPSGD (mini-batch) in the experimental section: see Figure 4, Figure 5, Figure 15. Considering almost all state-of-the-art implementations of DPSGD (e.g. De et al. (2022)) either operate in full or mini-batch mode we think our work has direct practical implications.\n\n> The scope of this submission seems rather narrow.\n\nThe entire focus of our work is to analyze how DPSGD protects against reconstruction attacks. That our attack is most applicable to DPSGD seems like an unfair and irrelevant criticism.\n\n> Write a threat model\n\nWe will add a threat model section.\n\n> What defines a successful attack in the context of previous works aiming for approximate reconstruction instead of exact retrieval?\n\nThere is not a well defined metric from other works and is somewhat fuzzily defined, hence why we chose to study exact reconstruction here.  Balle et al. do this by reporting a success if the reconstruction is smaller than the average nearest neighbor between any two images in CIFAR-10. Haim et al refrain from determining what a “success” is and just report structural similarity (SSIM). Although designing criteria for how to judge approximate reconstructions is certainly interesting, we believe this is an orthogonal direction.\n\n> Providing more details in Section 3.2 would be beneficial, such as explicitly presenting the definitions of $\\mu$ and $\\nu$ in Algorithm 1. \n\n$\\mu$ and $\\nu$ are arbitrary probability distributions and are defined in line 215. We will explicitly state this in Alg 1. In terms of N, computing $\\gamma$ with 1M samples is efficient (<1 s on a GPU), however, N=10,000 samples is sufficient for consistent results. We refer to our answer to Reviewer j4Wo for precise numbers. In terms of n (the size of the prior), we do have experimental results (Fig 3).\n\n> A clear claim about its key advantages over existing work should be provided in the revision.\n\nPlease see our response to Reviewer paNh for a detailed list of contributions. Generally, we believe that this work makes a number of important contributions to analyzing the protection DP offers against privacy attacks.\n\n- Showing that reconstruction can be provably defeated by large values of epsilon.\n- Providing a framework to translate prior reconstruction risk to posterior reconstruction risk,\n- Our bounds are tighter than prior work.\n- More generally, it is rare that in privacy attack research one can show that a privacy attack on DP is efficient enough to reach the bounds predicted by theory on state-of-the-art models. There is usually a compromise to be had, either by reporting loose bounds (Guo et al. (2022)) or running attacks on non state-of-the-art models (Balle et al. (2022) attacks only work on DP CIFAR-10 models with < 50% test accuracy). Our attack results do not have this compromise.\n\n> I didn't notice any discussion regarding the computational cost of the proposed method.\n\nGood point, we will add a discussion on computational costs. For all experiments presented computing upper bounds is cheap (< 1 s). The prior-aware attack is a bit more expensive as it requires us having to re-run DPSGD for each point in the prior. The model-based attack in Fig 1 is extremely expensive (see Balle et al. (2022) for a detailed explanation of this attack), while the gradient-based attack is cheaper as we just need to run gradient descent, and takes <10 mins on a GPU. We add specific numbers to the revision.\n\nBalle et al. \"Reconstructing training data with informed adversaries\". SP 2022\n\nStock et al. \"Defending against Reconstruction Attacks with R'enyi Differential Privacy.\" arXiv:2202.07623 (2022).\n\nDe et al. \"Unlocking high-accuracy ...\" arXiv:2204.13650 (2022).\n\nHaim et al. \"Reconstructing training data from trained neural networks.\" NeurIPS 2022\n"}, {"review_id": "zTvZ88y18G", "reviewer": "Reviewer_rZtg", "summary": "The paper studies the training data reconstruction robustness of DP-SGD. The paper observes that there is a huge gap between the existing lower bound and upper bound (attacks) on reconstruction error. Motivated by this observation, the paper proposes a tighter lower bound and a stronger attack, which empirically has a smaller gap. The paper further demonstrates how the hyper-parameters in DP-SGD affect the training data reconstruction error, and shows that the error can vary a lot even with the same DP guarantee.", "questions": "\n* Eq 1: The first term is an inner product whereas the second term is l1 error. Intuitively, we want the first term to be large, and the second term to be small. It is unclear why it makes sense to \"sum up\" these two terms as the loss. Do we want to maximize it or minimize it?\n\n\nOther minor questions:\n\n* Line 97: should \"<=\" be \"<\" or \"<<\" instead? Randomly releasing one sample gives (0, 1/|D|)-DP. So delta=1/|D| is too weak.\n\n* Line 311. It says Balle et al. give a trivial bound for epsilon=100. But the bound is indeed tight given that the attack achieves a success probability that is very close to the bound.\n", "limitations": "\nThe authors did not discuss the limitation or the potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "\n* Originality: The paper proposes new theoretical analyses and attacks for training data reconstruction in the context of DP-SGD. The results are new to the best of my knowledge.\n\n* Clarity: The paper is well-written.\n\n* Significance: Given that training data reconstruction is a practical concern, understanding ML models' robustness to it is an important topic. The paper is a solid contribution to this topic.\n\n* Quality: Overall, the paper is of good quality. ", "weaknesses": "* I do not see any major weakness of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks rZtg, answering your questions below.\n\n> Eq 1: The first term is an inner product whereas the second term is l1 error. Intuitively, we want the first term to be large, and the second term to be small. It is unclear why it makes sense to \"sum up\" these two terms as the loss. Do we want to maximize it or minimize it?\n\nThank you very much for catching this. There’s a typo in this equation, there should be a negative sign at the start; it should be -inner_prod + L1 distance. In practice we swept over different coefficients for each of these two terms to find how to weight them. We surveyed the relevant literature on gradient-based attacks, who propose many different losses to optimize: just the inner product, L1, L2, TV loss, summed combinations of them etc. We found through experimentation that the sum of the (negative) inner product with L1 gave the best results.\n\n> Line 97: should \"<=\" be \"<\" or \"<<\" instead? Randomly releasing one sample gives (0, 1/|D|)-DP. So delta=1/|D| is too weak.\n\nTechnically yes, but it is common practice in DP research to set $\\delta$ to 1/|D|. Almost all papers reporting DPSGD results on CIFAR-10 set $\\delta$ to 1/50,000. \n\n> Line 311. It says Balle et al. give a trivial bound for epsilon=100. But the bound is indeed tight given that the attack achieves a success probability that is very close to the bound.\n\nSure the bound is technically tight in this case but we still argue it is trivial. We can always set the upper bound to one. In some cases, the attack will succeed (and so the bound will be tight), and in some cases (smaller epsilons) the attack will fail. In either setting, we haven’t learnt anything useful from the upper bound.\n"}]

Author rebuttal:

Meta-review: While there were dissenting voices among the reviewers, with valid concerns summarized below, overall the reviewers (and I) were very positive about the paper's potential for impact in the discipline of privacy research, as well as potential for impact beyond academia.

Differential privacy (DP) is of significant interest to the NeurIPS community, and is of practical importance beyond. It has a necessarily strong threat model that covers membership inference attacks under minimal assumptions. it is well known that DP covers numerous other (weaker) attacks of interest, however analysis via DP potentially leaves open unmet utiltiy/privacy gains. It is rare, however, for a privacy definition to have the desirable properties of DP, while aligning with a threat model of interest (and not leaving too much unreasonably assumed about the attacker's limitations). This paper considers reconstruction attacks under DP mechanisms. Reconstruction attacks are often of direct concern in practice (compared to membership inference), but it tends to be difficult to say a lot specifically. The paper's direct analysis performs significantly better than a via-DP reduction.

The paper considers DP-SGD specifically (not per se all DP mechanisms) which while critiqued by some reviewers as being overly narrow, I believe to be an appropriate starting point and a sufficient step forward: DP-SGD is the favored way to train modern ML models like DNNs for DP of training data. The paper's bounds offer an avenue for setting the DP-SGD parameters - although this depends on computation of a prior, which is task specific. As clarified by the authors, the use of MC estimation does not invalidate the guarantees: through a standard argument the guarantees hold whp. Computation involved is modest (computing $\gamma$ on a CPU takes only 5s with $T=100$ with $10^6$ MC samples). I found the responses to reviewer concerns compelling, for example in response to reviewer j4Wo, the authors highlight why the prior's flexible is interesting (I concede that this might not always be acceptable but I believe it to be an acceptable option for privacy analysis), and why the definition of success is appropriate. This last point was raised more than once - I agree with the authors here that a graded/nuanced definition of successful reconstruction is helpful (the "1 out of n classification").

The discussion has uncovered a number of improvements to the paper's introduction, discussions, etc. that I believe the authors plan to make including the threat model of reconstruction, trade-off instead of blow-up, clarifications of details of Sec 3.1, compute cost results (added in discussion period), and others as detailed in the discussion. I believe these would all improve the paper's presentation and future impact and hope that the authors can make as many of these improvements as possible.
Decision: Accept (poster)