Reconstruction Attacks on Machine Unlearning: Simple Models are Vulnerable
Authors: Martin Andres Bertran
Shuai Tang
Michael Kearns
Jamie Heather Morgenstern
Aaron Roth
Steven Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: machine unlearning
reconstruction attack
Primary area: privacy

Abstract: Machine unlearning is motivated by principles of data autonomy. The premise is that a person can request to have their data's influence removed from deployed models, and those models should be updated as if they were retrained without the person's data. We show that these updates expose individuals to high-accuracy reconstruction attacks which allow the attacker to recover their data in its entirety, even when the original models are so simple that privacy risk might not otherwise have been a concern. We show how to mount a near-perfect attack on the deleted data point from linear regression models. We then generalize our attack to other loss functions and architectures,  and empirically demonstrate the effectiveness of our attacks across a wide range of datasets (capturing both tabular and image data). Our work highlights that privacy risk is significant even for extremely simple model classes when individuals can request deletion of their data from the model.

Reconstruction Attacks on Machine Unlearning: Simple Models are Vulnerable
Martin Bertran Amazon AWS AI/M
Shuai Tang Jump Trading
Michael Kearns University of Pennsylvania
Amazon AWS AI/ML
Jamie Morgenstern University of Washington Amazon AWS AI/ML
Aaron Roth University of Pennsylvania Amazon AWS AI/ML
Zhiwei Steven Wu
Carnegie Mellon University Amazon AWS AI/M
Abstract
Machine unlearning motivated by desire for data autonomy: a person can request have their data's influence removed from deployed models, and those models should be updated as if they were retrained without the person's 's data. We show that, counter- counter-ituittively these updates expose individuals high-accuracy reconstruction attacks which allow the attacker to recover their data in its entirety, even when the original models are so simple that privacy risk might have been concern. We show how to mount a near-perfect attack on the deleted data point from linear regression models. We then generalize our attack to other loss functions and architectures, and empirically demonstrate the effectiveness our attacks across wide range of datasets (capturing both tabular and image data). Our work highlights that privacy risk is significant even for extremely simple model classes when individuals can request deletion of their data from the model.
otherwise
Introduction
As model training on personal data becomes commonplace, there has been growing literature on data protection in machine learning (ML), which includes at least two aspects:
Data Privacy The primary concern regarding data privacy in machine learning (ML) applications is that models might inadvertently reveal details about the individual data points used in their training. This type privacy risk can manifest in various ways, ranging from membership inference attacks (Shokri et al. the training to more severe reconstruction attacks (Dick al. 2023) that attempt to recover entire data records of numerous individuals. To address these risks, algorithms that adhere to differential privacy standards (Dwork al.) (006) provide proven safeguards, specifically limiting the ability to infer information about individual training data.
which only seek to confirm whether a specific individual's 's data was used
Machine Unlearning Proponents of data autonomy have advocated for individuals have the right to decide how their data used, including the right to retroactively ask that their data and its influences be removed from any model trained on it. Data deletion, or machine unlearning, refer technical approaches which allow such removal of influence (Ginart et al. 2019 Cao & Yang 2015). The idea that, after an individual's 's data is deleted, the resulting model should be in the state it would have been had the model originally been trained without the individual in question's 's data. The primary
Martin and Shuai are the lead authors, and other authors are ordered alphabetically. Work done while Shuai was employed by Amazon. (mazen.(maberrop AT amazon.com|
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Target
Turget
Hiacc (ours))
Nitac
Figure 2: CIFARIO samples reconstructed from logistic regression model over random Fourier feature embedding (4096) of the raw input. We randomly chose one deleted sample per label (Row 1) and compared them against the reconstructed sample using our method (HRec, Row 2) and a perturbation baseline (MaxDiff, Row 3) which searches for the public sample with the largest prediction difference before and after sample deletion. HRec produces reconstructions similar to the deleted images both visually and quantitatively measured by cosine similarity.
focus of this literature has been on achieving or approximating this condition for complex models in ways that are more computationally efficient than full retraining (see e.g. Golatkar et al. (2020): Izzo
al. (021): Gao et al. (2022) Neel al. (2021: Bourtoule al. (2021): Gupta al. (2021).)
Practical work on both privacy attacks (like membership inference and reconstruction attacks) and machine unlearning has generally focused on large, complex models like deep neural networks. This because (1) these models are the ones that are (perceived as) most susceptible to privacy attacks, since they have the greatest capacity memorize data, and (2) they provide the most technically challenging case for machine unlearning (since for simple models, the baseline of just retraining the model is feasible). For simple (e.g.. linear) models, the common wisdom has been that the risk of privacy attacks is low, and indeed, we verify in Appendix A that state-of-the-art membership inference attacks fail to achieve non-trivial performance when attacking linear models trained tabular data, and an example is shown in Figure]
The main message of paper is that the situation changes starkly when we consider privacy risks in the presence of machine unlearning. As show, absent additional protections like differential privacy, request- ing that your data be removed even from linear regression model-can expose you to a complete re- construction attack. Informally, this is because it gives the adversary two models that differ in whether your data was used in training, which allows them to attempt a differencing attack. We show that the parameter dif- ference between the models can be approximately (or exactly, for linear models) expressed as a function of the gradient of the deleted sample and the expected Hessian of the model w.r.t. public data. This allows us to equate model unlearning to releasing the gradient of the unlearned samples, and leverage existing literature on reconstruction from sample gradients to achieve our results.
Model ACS Income Regression Ridge
10
NY
CA
True Positive Rate
10
TX
10%
10
10
10 -3
10
10"
10'
False Posltive Rate
Figure 1: We conduct membership infer- ence attacks on a ridge regression on ACS Income task; the attack performance is poor (close to random guessing).
Our Contributions We consider the following threat model: An attacker has access to the parameters of some model both before and after deletion request is made. The attacker also has sampling access to the un- derlying data distribution, but no access the training set of the models. In this setting, we first study exact reconstruction attacks on linear regression. We give an attack that accurately recovers the deleted sample given the pair linear models before and after sample deletion. This is made possible by leveraging the closed-form single-sample training algorithm for linear regression as well as the ability to accurately estimate the covariance matrix of the training data from modestly sized disjoint sample of public data drawn from the same distribution.

---

We then extend our attack to the setting where the model consists of a (fixed and known) embedding function, followed by a trained linear layer. Our goal remains recover the original data point (not only its embedding). This is natural class of simple models, and also captures last-layer fine-tuning on top of a pre-trained model- common setting in which machine unlearning guarantees are offered.
Finally, we give a second-order unlearning approximation via Newton's method which extends our attack generic loss functions and model architectures. This provides way to approximate the gradient of a deleted sample with respect to the model parameters, and later the sample itself. We remark that Newton's 's update approximation has itself been proposed as a way to approximate unlearning (Izzo et al. 2021 Gao et al. 2022), and is naturally related to the literature on influence functions (Hampel] 1974; Koh & Liang 2017]Zhang & Zhang 2022). which examines the effect any (set of) samples has on the final trained model.
We experimentally demonstrate the effectiveness of our attack variety of simple tabular and image classification and regression tasks. The success of our attack highlights the privacy risks of retraining models remove the influence of individual's data. without additional protections like differential privacy (as advocated by e.g. [Chourasia et al. (2022) in another context). Figure [ shows several deleted samples from a model trained on CIFAR TO (Krizhevsky et al. 2009) alongside the recovered reconstructions for our method and a baseline based on public data.
1.1 Additional Related Work
We elaborate on our threat model and related work to position our approach within the existing literature. Our model involves a scenario where model maintainer trains model on a private dataset, Xpriv E Rnxd and Ypriv E RR to minimize a loss function É, yielding parameters St. Upon a user's s request for data deletion, the maintainer re-trains the model excluding the user's data, resulting in new parameters 3 Our adversary, equipped with both model parameters before and after the deletion , and access to public samples (Xpab- Ypub) from the same distribution, aims to reconstruct the deleted sample (zr, y) using the algorithm A(3 X Upah) - (α, 9).
Extensive literature exists on membership inference and reconstruction attacks against static models, with notable references including [Shokri et al. (2017); Carlini al. (2021] 2022): Bertran al.) (2023); Carlini et al. (2023). These studies primarily address attacks on large-scale models, whereas our work focuses on simpler models and explores the changes induced by deletion operations.
Pioneering work in model inversion attacks on linear models by Fredrikson et al. (2014); Wu et al. (2015) demonstrates that partial information about a data sample be inferred from model outputs. However, these attacks do not directly utilize model parameters.
The concept of privacy risks in machine unlearning was first outlined by Chen et al. [022 1), who introduced membership inference attack based on shadow models applicable to updates machine learning models. This attack's ' efficacy increases with model complexity. In contrast, our approach targets the reconstruction of the exact data point, extending beyond mere membership inference.
Further research by Salem et al. (2020) explored reconstruction attacks using single-gradient updates on complex models. Unlike their approach, which relies solely on API access to the model, our method utilizes direct access to model parameters, allowing for efficient reconstruction of data points even in fully retrained simple models.
Recent works have also examined gradient- based reconstruction attacks, typically focusing on untrained models (Zhu et al., 2019 Zhao al. 2020 Wang et al. 2023). Our contribution extends these techniques to the context of machine unlearning, highlighting the utility of analyzing updates for data reconstruction.
Balle et al. 2022) present a scenario where the adversary possesses almost complete knowledge of the training dataset, aiming to reconstruct the missing sample. This represents distinct model from ours, where the adversary's 's knowledge is limited to model parameters and public samples.
Overall, our work contributes to the understanding of privacy vulnerabilities in machine learning, particularly in scenarios involving model updates and unlearning, where adversaries exploit the slight yet informative differences between model parameters. Most work on machine unlearning asks that they "unlearned" models be indistinguishable from what would have been obtained had the model been retrained without the deleted points the bascline that attack in this paper. However
3

---

there are several exceptions Cohen et al. (2023); Garg et al. (2020) that ask for stronger conditions
(satisfied, e.g. by requiring that the entire sequence of models released satisfy differential privacy like conditions) that can preclude such attacks. The concurrent work in Hu et al. (2024) shares thematic similarities by attacking specific (linearized) approximations model unlearning.
2
Method
We develop an attack aimed reconstructing the features of a deleted user from a (regularized) linear regression model. Specifically, our focus is reconstructing sample (æ, y), previously part of the private training dataset Xpiv Upiv. using models trained before and after the deletion this sample.
The parameters of these models, 3+ and BT, solutions regularized linear regression problem. The model including the deleted sample yields:
8+ = arg min | 1xp 5 Ypriv 112 +11B3122
(1)
8
with closed-form solution 3+ C-1X prey/pvv Here, C regularized covariance matrix. For the model post-deletion,
X priv Xpev Al represents the
& can described similarly, but adjusted for the absence of (2r y):
g = (C ZX
) (X Priv x xTy) y).
(2)
Using the Sherian-Morrison formula, we can relate g and 3 via:
y - x C-'x. 1 1+x
B+ =
(3)
This equation leads to an expression for the change in parameters due to the deletion of (I, y):
C(8 B y).
(4)
where axx, y) is scalar function dependent the sample. This representation shows that the difference between 8 and B scaled by C, is proportional to æ, which suggests a potential avenue for reconstructing
However, when we not have access to priv or X, we must rely on publicly available data Xpuh- Mpab- Xpab. considering that C' and Ć' are both empirical estimates of the underlying statistical covariance [[ xz) For rigorous analysis bounding the errors in this approximation, see Tropp et al. (2015).
We approximate C' using public data as = XT pub.
Linear models are often learned with bias terms, which can be interpreted as a feature with value 1. To simply the notation, we assume that the d-th dimension of sample x 1, noted as za Given our assumption, the scaling factor (xx y) is adjusted by normalizing the reconstructed feature vector ensure the scale of is maintained. We then estimate the reconstructed sample (ø. y) as follows:
2/2a.
where
2 = ò B
where Σ is the d-th element of é, ensuring S. 1. This method offers systematic approach to estimate deleted user features from differential changes in model parameters, employing public data approximate necessary statistics and regularization impacts.
Beyond Linear Regression
Our attack is derived for the simple models used linear regression. However, the same ideas can be generalised beyond linear regression. The attack generalises immediately to any model which performs linear regression on top fixed embedding: our attack recovers the embedding of deleted point, and reduces the problem to inverting the embedding. We can also generalise to other loss functions- primary challenge is that we no longer have closed-form expressions for an "update", but approximate this, describe in Section 3.2

---

3.1 Fixed Embedding Functions
Our attack is built upon the analytical update of adding or deleting a sample to a linear regression model, therefore, it also generalises linear models trained top of embeddings of the original features. Suppose that both parameter vectors 5 and 3 along with the embedding function é _d + R are publicly known (and the embedding function has bias term). Our attack first reconstructs the embeddings as in Eq. (5). and then reconstructs features by finding data point whose embedding best matches the reconstructed transformed features as follows:
T = arg min l - o(x)1
where
I = p( ((X (st - 8-) -
(6)
Here, we assume that the embedding ø is fixed that is, it doesn't change after deleting a sample. This is the case when e.g. performing last-layer fine- tinettuning on top of pre-trained model, and for data-independent embeddings like random Fourier features.
3.2 Arbitrary Loss Functions and Architectures
Our foundational equation, Eq. specifically addresses linear models minimized under the mean squared error. When broadening this scope to include alternative loss functions and model architectures, the luxury of closed-form solutions vanishes. However, we can utilize Newton's 's method for approximating the "update function" necessary after data deletion. Consider model maintainer optimizing an empirical risk function represented as:
E(B; Xpiv Upáv)
(x.)) (xp 2;, v).
n
where 8+ and B are the optimal parameters before and after excluding a specific data point, (s, v). respectively. By adopting a second-order Taylor approximation via Newton's 's method, we estimate:
8 g+ H H-ive,
where H = V V [(3; Xpro (x, Upriv \,),
Ve = V 8=0- C(B: Xpriv (x, Ppriv \r).
Using the first-order optimality conditions, deduce that the aggregate gradient over the remaining samples inversely equals that of the removed sample:
-= E(B; Xpriv: Upriv) = O,
(9)
n n
V V ((3
(10)
Integrating Eq.
10 into Eq.
8 we derive:
H n
3 Rd 3
V -= ((3 x),),
(11)
nH -
~ 8= E(3;,,
(12)
In linear regression, this method precisely recovers the known Eq (4) In the general case, the Hessian matrix, analogous to the covariance matrix in linear regression, is estimated using public data sharing the same distribution the private data:
1 Ex S'ee.eEE(Xae Mpo ((: m
(13)
For linear models under attack, the gradients at the removed loss sample, particularly for certain model layers, correlate directly with the data of the removed sample. Efficiently approximated through influence matrices such as the Fisher information matrix, these gradients serve as crucial elements in reconstructive attacks model privacy.
For non-linear models and more intricate architectures, the materialization of the Hessian may become impractical due to its size, prompting the use of efficient Hessian product computations.
5

---

Algorithm Generalized Attack
Require: Public data pub IRmxxd Ypub IRm
Require: Parameter vectors , Rd
Require: Loss function {(3)
Require: Embedding function
Ensure: Reconstructed sample 2\
Estimate the Hessian H using Eq.
13
Reconstruct the embedding using Eq. if <(x) = x then
12
Directly recover =
else
Reconstruct the input 7 using Eq.
end if Return I
3.3 Multiclass Classification and Label Inference
In a multiclass classification setting, our approach described in Eq. 12 facilitates an estimation of parameter gradients with respect to the deleted sample. Employing Eq. (6. initially defined in Section 3.1 allows for reconstructing the deleted data point. In models using linear layers directly post-embedding, recovery becomes straightforward. However, for models with multiple class-specific parameters, label inference requires additional steps.
Employing softmax nonlinearity for outputting probability vectors, we observe that the derivative of the loss with respect to the bias for the correct label is distinctively negative, setting it apart from the other biases which demonstrate positive derivatives under typical loss functions:
Vo, - In (a; B+)] fx;;; 1 v).
(14)
The deleted label y can then be inferred as:
arg min V,, 2(3 3=$1
(15)
This approach significantly extends the capabilities of privacy attacks to encompass a wider array of multiclass classification models.
4
Experiments
We assess our attack across diverse datasets, including tabular and image data, and for both classifi- cation and regression tasks. Initially, we train a model on the complete dataset X Upriv to derive parameters 8+, and then retrain it et-excluding single sample (z, y)- obtain / We note that 3 is achieved through full retraining, not upproximate unlearning methods- our attack does not depend on imperfect unlearning be effective.
Our attack leverages public data samples from the same distribution as the training data but does not require knowledge of the deleted sample's features or label. We evaluate approach against two baselines that utilize public data:
"Avg": Predicts the deleted sample a Exex, an average of the public samples.
"MaxDiff': Identifies the public sample that maximizes the prediction discrepancy between 3+ and 8 as & = arg ma. x ( 8-) Ill-
These baselines exploit similarities between public and private data, with "MaxDiff" additionally considering the change in model parameters. Our threat model differs significantly from that of Salem et al. (2020), who assume black-box access and a simpler model update scenario; details and comparisons are found in Appendix
For practical simulations, each dataset is split into two: one for private training and the other for public samples. We simulate the deletion of each sample the private set, retrain the model, and attempt its reconstruction using our method and the baselines.

---

Cross
POY
PDF Cross
liRec
2.0
0.8
Nax
0.8
0.5
0.4
0.4
0.4
0.2
0.2
0.6
0.0
0.0
0.25
0:75
675
3.5
0.25
0.25
0.5
Contre simlerity
Creame similerity
Coxine similerly
(a) MNIST results
Cross Eitropy
RBF Nidgo
RBF Cross Entropy
1.4
Mflecc tourss
2.0
1.0
Arg
NexD
0.3
0.5
1.4
0.5
0.8
0.3
0.7
0.7
0.6
0.0
0,2
0.25
0.5
0.75
0.25
0.75
0.25
0.75
Costne 5 mmilantty
Cosine similartty
Costne simitaity
(b) Fashion MNIST results
Entropy
Bidgo
Entrapy
1.0
2.0
3.2
Propurdan target
0.8
0.8
0.8
03.6
0.8
0..4
0.4
0.1
HRle (ours)
0.2
0.2
Ang
0-6
NT
0.0
0.2
siilliity
similarity
Ozsina siiilalyy
(c) CIFARIO results
Figure 3: Cumulative distribution function of cosine similarity between deleted and reconstructed sample via the average, MaxDiff, and HRec (our) attack on MNIST, Fashion MNIST and CIFAR10 for three model architectures (linear cross- ridge regression over 4096 random Fourier features, and cross-entropy over 4096 random Fourier features). Lower curves correspond more effective attacks than higher curves. Our attack achieves better cosine similarity with the deleted sample across all settings; the effect is especially apparent the denser CIFARIO dataset.
Hyperparameters, specifically the & regularization strength X, are optimized on the private set and remain constant when recalculating 8 We explore attacks on unregularized models in Appendix C
We quatify the efficacy of our attacks and baselines with the cosine similarity between deleted and reconstructed samples, aggregated into Cumulative Distribution Function (CDF) of these similarity scores: sharp peak near indicates precise reconstruction. CDFs which are "below"" others correspond to more effective attacks, which have a higher fraction of reconstructed points with very high similarity to the original data. The performance of target models is evaluated in Appendix [D]
4.1 Image Data
We evaluate our generalized attack methodology, outlined in Algorithm I across three distinct model configurations on Fashion MNIST (FMNIST), MNIST, and CIFAR 10 datasets. Fashion MNIST and MNIST consist of 28 x 28 grayscale images, whereas CIFARIO 10 includes 32 x 32 x 3 RGB images, with all datasets aimed at 10-way classification (Xiao et al.) 2017 LeCun et al. 1998 Krizhevsky al. 2009). Each dataset undergoes normalization process where input features are scaled to the range
7

---

/
3
4
WOLL CONTTE
WRA comm
/
8
4
2
S
4
S
7
8
9
WORK QUAEO
S
6
7
8
9
6
6
9
9
9
Fashion MNIST
(b) MNIST
Figure 4: Sample reconstructions on Fashion MNIST/ MNIST for 40K parameter model (cross- entropy over random Fourier features of the raw input). We randomly chose one deleted sample per label (Rows 1, 4) and compared them against the reconstructed sample using our method (HRec, Rows 2, 5) and perturbation baseline (MaxDiff, Rows 6) which searches for the public sample with the largest prediction difference before and after sample deletion. HRec produces reconstructions that are highly similar to the deleted images.
Cross-entropy Loss for Multiclass Classification: We first consider a linear model with softmax output, trained to minimize the cross-entropy loss fce(f (3, y) log o (3) + X | This model facilitates direct gradient estimation with respect to the parameters 3 proportional to the raw input æ, negating the need for Eq.
Ridge Regression with Random Fourier Features: The second model incorporates an embedding function 6, generating random Fourier features (Rahimi & Rechi (007). The associated loss function, Ridgee (3. (x)), y) [Ø(z)] 21l2 + A|| admits an analytical solution for the Hessian matrix
H (X) (XX) concerning (zx,, , but requires embedding inversion via Eq. (6).
This model merges the complexities of the first two: it lacks closed-form update solution and necessitates embedding inversion, addressing scenarios with both softmax nonlinearity and random Fourier embeddings.
Cross-entropy Loss with Random Fourier Features:
Figure 3 Billustrates the efficacy of our attack across all three model types on MNIST, FMNIST and CIFARTO, demonstrating the capability to consistently recover samples highly similar to the original, deleted samples. Figures 4a and 4bjdecict randomly sampled deletions and their nearest recovered samples using HRec and Maffiff techniques, particularly under the challenging conditions of cross- entropy loss random Fourier features. Further results for additional model configurations be found in Scction[E] expanding upon the robustness and versatility of our attack methodology across varied settings and data modalities.
4.2 Tabular Data
Ridge Regression for Income Prediction We perform an attack on ridge regression models using American Community Survey (ACS) income data from 2018 (Ding et al. [002)) Our approach involves direct application of Eq. (4) along with an intercept normalization technique. Figure 5 (first row) illustrates the attack performance. If the covariance matrix of the private data and the regularization parameter were known, our approach could perfectly recover the deleted sample. However, approximation assumes À 0 and estimates the covariance matrix from public samples, which introduces some estimation error. Despite these approximations, we achieve near pear-perfect reconstruction of the deleted sample.
Ridge Regression with Random Features variation of the previous attack, we target a ridge regression model trained with random Fourier features (Rahimi & Recht 2007). Assuming access to both the random Fourier features and the model weights, we reconstruct the embedding of the deleted sample and then solve an inverse problem to recover the original features. The results,

---

Mothod = Ridge State = NY
Method = Ridge State GA
Method = Rige (Stato = TX
1.0
HRed (ours)
Proporion under tanget
MaxDiff
0.8
Aug
0.6
0.4
0.2
Method
RBF R Ridge (State NY
Method
RBF Ridge State CA
Method RBF Ridge State
TX
1.0
Proportion under target
0.0
0.6
0.4
0.2
0.0
0.25
0.75
1.00
0.00
0.25
0.75
1.00
0.00
0.25
0.75
1.00
Cosine similarity
Cosine similarity
Cosine similarity
Figure ACS Income Regression. Target models are ridge regression with tuned hyperparameters on original features (first row), and over random Fourier features (second row). ACS Income data from three states are used to demonstrate the effectiveness our attack. Given the analytical single-sample update rules of linear regression, attack (HRec) reconstructs the deleted sample almost perfectly on all datasets and different embedding functions.
depicted in the second row of Figure demonstrate significant improvement the baselines, achieving almost perfect reconstruction accuracy.
Binary Classification for Income Level Prediction We extend our analysis to binary classification tasks using logistic regression and support vector machines (SVMs) with squared hinge loss. Both models allow analytical computation of their Hessian matrices:
A = puh
DX pub:
where D M is diagonal matrix. For logistic regression, the diagonal terms are defined as D. = (x (1 a (2. (+)), with a being the sigmoid function. For SVMs, the terms are DH 1(1 y, 3+ 2 0). The reconstruction of the deleted sample's features is obtained via fst - ). enhanced by the intercept normalization trick. The performance these attacks is showcased in Figure 6a where our method, HRec, consistently outperforms the baselines across all datasets and model classes.
Binary Classification with Random Features Lastly, we attack binary classification models trained on an enriched set random Fourier features. Figure presents preseets the performance curves for our attack compared to various baselines. Our method outperforms all baselines in attacks on logistic regression models and performs competitively with MaxDiff baseline attacks on SVM models, highlighting the efficacy of our approach.
Our comprehensive attack strategies on regression and binary classification models demonstrate the potential vulnerabilities in these machine learning setups, especially when certain model parameters or features are accessible to an adversary. These findings underscore the need for robust privacy- preserving mechanisms in machine learning applications.
Conclusion
present a strong reconstruction attack that targets data points that are deleted from simple models. Our reconstructions are nearly perfect for linear regression models, and still achieve high-quality reconstructions for linear models constructed on top embeddings, and for models which optimize various objective functions. This shines light on the privacy risk inherent in even very simple

---

Method LogRagg State NY
Method LogRig Sttte GA
Method LogRagg
State
TX
1,0
HRed (ours)
Proporion under target
MaxDif
0.8
Avg
0.6
0.4
0.2
Mothod SVM Stato NY
Method SVM State GA
Method SVM
State
1.0
Proportinn under Sangel
0.8
0.6
0.4
0.2
0.0
1.00
0.25
1.00
Cosine similrtty
Cosine similanty
Cosine similartty
(a) Original features.
LogReg
RDF LogReg
Method RDF LogRegi
Proporton under targht
MaxDif
0.4
0.2
0.0
Method REF SVM State NY
Method RBF SVM State CA
Method RBF SVM State TX
1.0
Propomion under harget
0.8
0.00
0.25
0.50
0.75
1.00
00
0.25
3.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Costne
Costne
(b) Random Fourier Features.
Figure 6: ACS Income Level Prediction. Target models are logistic regression (first row) and SVM (second row) for binary classification tasks. These methods do not have analytical forms of the single-sample update: however, our approximation using Newton's update facilitates the outstanding performance of HRec among all attacks. While this reconstruction is imperfect due to approximation errors, large number of deleted samples can still be reconstructed with high similarity scores.
models in the context of data deletion or "machine unlearning". and motivates using technologies like differential privacy to mitigate reconstruction risk.
10

---

References
Balle, B., Cherubin, G., and Hayes, Reconstructing training data with informed adversaries. In 2022 IEEE Symposium Security and Privacy (SP), pp. 1138-1156. IEEE, 2022.
Bertran, M., Tang, S., Kearns, M., Morgenstem, J., Roth, A., and Wu, Z. Scalable membership inference attacks via quantile regression. arXiv preprint arXiv:2307.03664 2023.
Bourtoule, I.., Chandrasekaran, V., Choquette- Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp- 141- IEEE, 2021.
Cao, Y. and Yang. J. Towards making systems forget with machine unlearning, In 2015 IEEE symposium on security and privacy, pp. 463-480. IEEE, 2015.
Carlini, N., Tramer, F., Wallace, E.,, Jagielski, M., Herbert- Voss, A., Lee, K., Roberts, A., Brown, T., Song, D., Erlingsson, U., 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., Tramer, F., Balle, B., Ippolito, D., and Wallace, E. Extracting training data from diffusion models. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 5253-5270, 2023.
Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., and Zhang, Y. When machine unlearning jeopardizes privacy. Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp- 896-911, 2021.
Chourasia. R., Shah, N., and Shokri, R. Forget unlearning: Towards true data-deletion in machine learning. arXiv preprint arX arXiv:2210.08911, 2022.
Cohen, A., Smith, A., Swanberg, M., and Vasudevan, N.N. Control, confidentiality, and the right be forgotten. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pp. 3358-3372. 2023.
Dick, T., Dwork, C., Kearns, M., Liu, T., Roth, A., Vietri, G., and Wu, Z. S. Confidence-ranked reconstruction of census microdata from published statistics. Proceedings of the National Academy of Sciences, 120(8) 8605120, 2023. doi: 10. 1077000ass.22 86058660120 120. URL httpss/s::///e ://tts pnas. catas.org//oi/// abs/ 1073/ pnas. 2218605120
Ding, F., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. pp. 265-284. Springer, 2006.
Fredrikson, M., Lantz, E., Jha, S., Lin, S., Page, D., and Ristenpart, T. Privacy in pharmacogenetics: An (End-to-End] case study of personalized warfarin dosing. In 23rd USENIX security symposium (USENIX Security 14), pp. 17-32, 2014.
Gao, J., Garg, S., Mahmoody, M., and Vasudevan, P. N. Deletion inference, reconstruction, and compliance machine (un) learning. arXiv preprint arXiv:2202.03346) 2022.
Garg. S., Goldwasser, S., and Vasudevan, P. N. Formalizing data deletion in the context of the right to be forgotten. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 402. Springer, 2020.
Ginart, A., Guan, M., Valiant, G., and Zou, J. Making forget you: Data deletion in machine learning, Advances in neural information processing systems, 32, 2019.

---

Golatkar, A., Achille, A., and Soatto, S. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9304-9312, 2020.
Gupta, V., Jung, C., Neel, S., Roth, A., Sharifi-Malvjerdi.. S., and Waites, C. Adaptive machine
unlearning. Advances in Neural Information Processing Systems, 34:16319-16330, 2021.
Hampel, F. R. The influence curve and its role in robust estimation. Journal of the american statistical association, 69(346):383-33) 393, 1974.
Hu, H., Wang, S., Dong, and Xue, M. Learn what you want unleam: Unlearning inversion attacks against machine unlearning, arXiv preprint arXiv:2404.03253, 2024.
Izzo, Z., Smart, M. A., Chaudhuri, K., and Zou, J. Approximate data deletion from machine learning models. International Conference on Artificial Intelligence and Statistics, pp. 2008-2016. PMLR, 2021.
Koh, P. W. and Liang, P. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885-1894. PMLR, 2017.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
LeCun, Y.. Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-2324, 1998.
Neel, Roth, A., and Malvajrd,,,, Descent-to-delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Rahimi, A. and Recht, B. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Salem, A., Bhattacharya, A., Backes, M., Fritz, M., and Zhang, Y. (Updates-Leak): Data set inference and reconstruction attacks in online learning. In 29th USENIX security symposium (USENIX Security 20), pp. 1291-1308, 2020.
Shokri, R., Stronati, M., Song, C., and Shmatikov, V. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Tropp, A. al. An introduction to matrix concentration inequalities. Foundations and Trends@) in Machine Learning, 8(1-2):1-230 2015.
Wang. Z., Lee, J., and Lei, Q. Reconstructing training data from model gradient, provably. In International Conference on Artificial Intelligence and Statistics, pp. 6595-6612. PMLR, 2023.
WU, X., Fredrikson, M., Wu, W., Jha, S., and Naughton, J. F. Revisiting differentially private regression: Lessons from learning theory and their consequences. arXiv preprini arXiv:1512.06380 2015.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:/708.00747 2017.
Zhang, and Zhang, S. Rethinking influence functions of neural networks in the over-parameterized regime. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9082- 9090, 2022.
Zhao, B., Mopuri, K. R., and Bilen, H. idlg: Improved deep leakage from gradients. arXiv preprint vxXiv:2001.02610 2020.
Zhu, L., Liu, 7.,, and Han, S. Deep leakage from gradients. Advances neural information processing systems, 32, 2019.
12

---

A Membership Inference Attacks on Linear Models
Linear models usually have lower privacy risks compared neural networks because the parameters of linear model are significantly fewer. To demonstrate the low privacy risks, we conduct a state-of- the-art membership inference attack (MIA) proposed by Carlini al. (2022) Likelihood Ratio Attack (LiRA) on the same tabular tasks. The goal of MIA is to determine whether sample is in the training set of the target model.
On each task, we split the dataset into three splits, including 40% for training the target model, another 40% as the public samples for learning shadow models, and the rest 20% the holdout for evaluation. After training the target model on the private training set, we train 64 shadow models using the same optimization algorithm on the public samples with Bootstrap. Then, we use the joint set of the private samples and the holdout samples as samples under attack, and evaluate the attack performance.
As shown in Figure / the attack performance is close to random guessing, which implies that is already challenging to determine which sample has been used in training when the target model is linear.
Model
Regression- Ridge
Model
Prediction
LogiReg
Prediction
10"
GA
10"
Poslive
10
10"
10"
10
10
10"
10
10
10
10
2
10"
10"
10"
10"
10
Posilive
Figure Membership inference attacks on ACS tasks.
B Additional Comparisons
Here we provide limited comparison Updates-leak (Salem al. (2020) against our method and baselines for the same simple model architecture (cross ceross-entropy loss over a linear model on top of 4096 random Fourier features). We stress that threat model for Updates-Leea differs from our own in two important ways. First, they assume query access to the model, while we assume access to the parameters. Second, we carry out our attack on two models, fully trained to convergence on two different datasets, ((Xpriv Bpriv) and (Xpriv Spriv v)). ). In contrast, Spdates-leak, instead attacks the difference between a model trained on (Xpriv \ Z. Mpriv \ y) and an updated model where in the update, only single gradient descent step is taken on the 'update' sample (x, y) (single sample attack version). The Updates-Leak approach also incurs a significantly higher computational cost due to its shadow model and encoder learning approach. For these reasons, limit the comparison to a single model architecture on CIFAR 10 while stressing this comparison is not 'apples to apples'. In particular, even though plot the reconstrution cosine similarity curves the same axis (and see that ours improves), our technique and UpdateslLeat are attacking different pairs of models (we attack the model that results from full retraining, whereas they attack the model that results from single gradient update).
Figure 8 shows the cosine similarity comparison, and Figure 9 show some example reconstructions for Updates-Leak in this scenario. We leveraged their publicly available code to produce these comparisons, using their default configuration (10, 000 shadow models are used for training, and their DC-GAN generator trained for 10, 000 epochs on the shadow model dataset).
13

---

1.0
HRec (ours)
Avg
Proportion below target
0.8
MaxDiff
UpdatesLeak
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
cosine similarity
Figure 8: Cumulative distribution function of cosine similarity between the target (deleted) sample and the reconstructed sample via the average, MaxDiff, Updates-Leate and HRec (our) attack on CIFARIO on simple model (cross-entropy loss over linear model on top of 4096 random Fourier features). All attacks save for Updates-Leak operate against the full retraining baseline, that the comparison between two models trained from scratch until convergence in dataset with and without the 'deleted' sample ((X ((Xpriv ((Xpriv>pere Mprii)) and (X \ I, Spriv y)), Updates- Leak instead attacks two models, one trained until convergence on the dataset without the sample ((xpr) priv' \ Upriv \ v)), and one that took a single gradient descent step on the loss of the updated sample æ. y. Here lower curves dominate higher curves. Our attack achieves better cosine similarity with the deleted sample.
14

---

Figure 9: Sample reconstructions for Updates-LLeal on CIFAR10. Original images and their corre- sponding reconstruction are shown side by side in an alternating fashion. The model architecture is cross-entropy loss over a linear model on top of 4096 random Fourier features. The models before and after the update differ in single gradient descent step being taken the update sample (x, y).
15

---

C Attacking Unregularized Models
In our main experiments, emulate the more realistic situation where the model maintainer tunes the hyperparameter of the target model on the entire dataset, and keeps it fixed during unlearning. Since the impact of regularization on the attack performance rather challenging to analyze and immediately obvious, we here present results on attacking models without regularization.
C.1
ACS Income Regression
On this task, the model maintainer directly optimizes the following objective without the regularization term:
8 = arg min X yll
(16)
This problem admits an analytical expression for 3+ and B which can written as:
g = C-11 X priv Speiv
(17)
8 (C xx
(X (Xprix priv
y),
(18)
where C = X peiv- Xprv is the covariance matrix. In the scenario where the inverse of the covariance matrix doesn't exist, we use the Moore-Penross inverse instead. Our attack still stays the same.
The results are presented in Figure 10 and we can see that without regularization
Method OLS
State NY
Method OLS State = CA
Method = OLS State TX
1.0
HRec (ours)
Proportin under target
0.8
0.8
0.2
0.0
Method
RBB OLS State NY
Method KBF OLS State CA
Method RHP OLS State
IX
1.0
Proportion under target
0.8
0.6
0.2
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Cosine similarity
Cosine similarity
Cosine similarity
Figure 10: ACS Income Regression. Target models are ordinary linear regression on original features (first row), and over random Fourier features (second row). Our attack HRec reconstructs the deleted sample almost perfectly.
C.2 Image Classification Tasks
Here we additionally show results across CIFARIO, MNIST, and Fashion MNIST on the more challenging target model scenario (RBF Cross Entropy). For these results, the model maintainer does not use any form regularization. Results are shown Figure
16

---

Entropy
HRec (ours)
Popartion below Larget
MixDEft
0.6
0.4
0.2
0.0
0.25
0.5
0.75
Cosine similrity
Fashion MNIST results
RSF Cross Entrapy
1.0
HRec (ours) Bug
Propation beebow targee
0.8
Mixdafff
0.9
0.4
0.2
0.25
0.5
0.75
Cos sinilerity
(b) MNIST results
RSF Cross Entropy
1.0
HBac (nurs) Avg
Prosoet belner target
0.8
0.6
0.4
Cosine similarity
(c) CIFARIO results
Figure 11: Cumulative distribution function of cosine similarity between the target (deleted) sample and the reconstructed sample via the average. MaxDiff, and HRee (our) attack Fashion MNIST, MNIST, and CIFARIO 10 for target model using cross-entropy over 4096 random Fourier features. In this scenario, the model maintainer does not use any form of regularization when training the original or updated model. Here lower curves dominate higher curves. Our attack achieves better cosine similarity with the deleted sample across all settings; the effect is especially apparent in the denser CIFAR dataset.
17

---

D Performance of Target Models
D.1 ACS Income Tasks
Table 1: Performance of target models ACS Income tasks. Regression tasks evaluated using
r², which indicates the portion of explained variance, and classification tasks are evaluated using score since class labels not balanced.
STATE
NY
CA
TX
TASK
TARGET MODEL
+RBF
+RBF
+RBF
REGRESSION (R2)
RIDGE REGRESSION
0.2755
0.32712
0.30139
0.3510
0.3089
0.3510
LOGISTIC REGRESSION
0.7154
0.7230
0.7313
0.7413
0.6889
0.7009
CLASSIFICATION (FI)
LINEAR SVM
0.7099
0.7149
0.7345
0.7325
0.6868
0.6968
D.2
Image tasks
Table 2: Out of sample accuracy of target models Image tasks
DATASET
LINEAR CROSS-ENTROPY
RBF RIDGE
RBF CROSS ENTROPY
CIFARTO MNIST
39.5%
48.7%
50.4%
91.6%
96.2%
96.4%
FASHION MNIST
84.5%
87.3%
88.4%
18

---

E
Additional Results on Image Datasets
Target
Target
HRAC (ourss)
Hiac (ours)
MoxDiff
McxDfff
Targge
Hiktee (ours)
Figure 12: Sample reconstructions on CIFARIO. Rows 1-3 rows show results of attacking linear cross-entropy model, and rows 4-6 show similar results for ridge regression over 4096 random Fourier features. We randomly chose one deleted sample per label (shown in rows and 4) and compared them against the reconstructed sample using method (HRec, rows and 5) and perturbation baseline (Max rows 3 and 6) which searches for the public sample with the largest prediction difference before and after sample deletion. HRec produces reconstructions that are highly similar to the deleted images.
19

---

Target
Thoget
Nite: (ours)
Hitc (ours)
Naxcltt
MOXCHI
Target
barget
Nitec
Figure 13: Sample reconstructions on Fashion MNIST. Rows 1-3 rows show results of attacking linear cross-entropy model, and rows 4-6 show similar results for ridge regression over 4096 random Fourier features. We randomly chose one deleted sample per label (shown in rows and 4) and compared them against the reconstructed sample using our method (HRec, rows and 5) and perturbation baseline (MaxDiff, rows 3 and 6) which searches for the public sample with the largest prediction difference before and after sample deletion. HRec produces reconstructions that are highly similar to the deleted images.
Target
D
4
Satget
$
6
7
8
9
Hitcc (ours)
HRaac (ours)
D
3
9
$
6
7
8
9
MaxOlE
3
3
5
MOXOMT
5
7
8
5
3
4
5
6
7
8
9
HRMC (ours)
2
3
4
5
6
2
8
9
MEXDET
2
3
MaxDer
5
6
7
8
9
Figure 14: Sample reconstructions on MNIST. Rows 1-3 rows show results of attacking linear
cross-entropy model, and rows 4-6 show similar results for ridge regression over 4096 random Fourier features. We randomly chose one deleted sample per label (shown in rows I and 4) and compared them against the reconstructed sample using our method (HRec, rows and 5) and a perturbation baseline (MaxDiff, rows 3 and 6) which searches for the public sample with the largest prediction difference before and after sample deletion. HRec produces reconstructions that are highly similar to the deleted images.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract describes the context the contribution and describes the main theoretical and practical results presented
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide clear context on the settings where our contribution applies and substantiate each claim with theory and/or empirical results.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: assumptions and results are clearly stated.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide detailed algorithm and description of the exact setup of our experiments
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Open source code will be provided at a later date
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: setup and hyperparameters are well described
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: While we don't 't report error bars, we report the full distribution of the recon- struction error for our experiments the form of cosine similarity CDF curves.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Answer: [No]
21

---

Justification: The computational costs of the experiments were small enough that they could be run serially on a single GPU machine without great eftort.
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We comply fully with the code of ethics
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the potential impacts of our work in the introduction and conclusion. Chief among them that more care needs to taken to ensure model unlearning preserves user privacy (e.g., using DP at the model learning/disgorging phase).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper highlights an existing vulnerability in the field of machine unlearn-
ing.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: (public) datasets and architectures are properly cited.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets are provided
Guidelines:
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: NA
22


Reviews:
[{"review_id": "8nul1B9qt2", "reviewer": "Reviewer_b41V", "summary": "This work focuses on investigating privacy issues in machine unlearning. Specifically, assuming the availability of model parameters before and after unlearning, as well as the ability to sample data from the original data distribution, the proposed reconstruction attack aims to recover deleted samples. By analyzing the training objective of linear regression, the study found that the difference between the parameters before and after unlearning is proportional to the deleted sample. Based on this observation, this study proposes an algorithm to extract deleted samples accurately. The method extends to more complex models and arbitrary loss functions using Newton's method to approximate the parameter update process.", "questions": "1. In what scenarios is the threat model proposed in the paper realistic?\n2. Is the proposed method effective when unlearning is performed using existing unlearning methods?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The topic of the study, concerning privacy risks in unlearning, is crucial. Since the data deleted in unlearning usually has high privacy sensitivity, recovering such data poses a significant threat.\n\n2. The proposed algorithm is elegant and achieves near-perfect results in linear regression. It also has the potential to extend to more complex models.", "weaknesses": "1. The assumptions are too strong. The authors assume access to model parameters before and after unlearning and the ability to sample from the original data distribution. The authors need to clarify under what circumstances an attacker could have the assumptions mentioned in the paper, especially the sampling ability, since the deleted data is typically highly sensitive or inappropriate, making sampling difficult.\n\n2. The goal of this paper is to explore the privacy risks in machine unlearning. In real-world scenarios, machine unlearning is achieved through existing unlearning methods. However, in this paper, unlearning is implemented by retraining after removing the samples to be unlearned. This creates a gap between the resulting model and the model obtained through actual unlearning methods. Therefore, it is questionable that the experimental results obtained from such a model can directly demonstrate the privacy risks associated with machine unlearning in real-world situations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*[Response to Weaknesses 1]*\n\nWe take the position that security assurances should be based on minimal assumptions. Here, we view the assumption that an attacker who has API access to the model does -not- have access to model parameters to be dangerously strong. Consider for example a d dimensional linear model, as we study initially in our work. Just from query access, an attacker can recover the model parameters by querying the model on d linearly independent points and solving a system of linear equations. This requires no knowledge of the data distribution. So, there is no meaningful difference between white box and black box access in such scenarios.\n\nWhat about for more complex models? Even there the boundary between white-box and black-box access has been blurring. For example recent work [1] has shown that it is possible to reconstruct the embedding matrix from a production LLM model with only black-box access. And of course, open source models explicitly release parameters with each version of the model. \n\nWith regards to access to the data distribution, we only assume access to samples from the same distribution as training data, not to private samples atually used in training. This is a standard assumption underlying even simpler attacks suck as membership inference. We agree with the reviewer that it may sometimes be difficult for an attacker to ascertain what this distribution is, but again, we take the view that when analysing attacks as a means to audit security vulnerabilities, we should be generous (within reason) about the assumed abilities of the attacker.\n\n[1] Carlini, Nicholas, et al. \"Stealing part of a production language model.\" arXiv preprint arXiv:2403.06634 (2024).\n\n*[Response to Weaknesses 2]*\n\nAn important aspect of existing machine unlearning approaches is that almost all of them aim to approximate full retraining with reduced computational cost. These approximations are proposed due to the intense compute required for full retraining, especially for large neural networks and LLMs. \n\nOur study is explicitly focused on exposing the risk present in even very simple models, such as linear regression, logistic regression, SVMs, and feature augmentation using random Fourier features. For such models, full retraining is feasible, and would be the expected solution to the data deletion problem, as computational approximations to retraining are not needed.\n\nFull retraining for a single data deletion in linear regression is equivalent to updating the model parameters using Newton's update as we discussed in Sec. 3.2. By leveraging this concept, our attack achieves almost perfect reconstruction, and the only error source is the estimation of the Hessian matrix using public data. For more complex models, a number of popular unlearning methods approximate full retraining by taking a Newton update. When we apply our attack to more complex models, we act as if full retraining results in the model that is derived from taking a newton step --- and the reason our reconstruction performance degrades is simply that this approximation becomes imperfect. However, if rather than full retraining, the machine unlearning method employed was one that simply took a newton step, our reconstruction would again be near perfect. We will elaborate on this point in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5o4z74s89D", "reviewer": "Reviewer_VcL6", "summary": "The authors propose an attack that can accurately recover unlearned samples through reconstruction attacks on linear regression models. They extend this work to include linear models with fixed embeddings and generalize it to more generic loss functions and model architectures by employing Newton’s method for the reconstruction attack. This work significantly contributes to understanding the privacy vulnerabilities in machine unlearning.", "questions": "1. Is “Avg” a valid or commonly used baseline? It seems too straightforward to predict the deleted example as an average of the public samples, as described in Section 4. Can the authors elaborate on the principle or intuition behind this choice?\n2. How robust is this attack across different configurations? For example, how does the attack's performance vary when using different model architectures on the same dataset?\n3. Can the authors elaborate on the computational complexity and scalability of the proposed attack method when applied to various datasets and model architectures?\n4. What practical countermeasures can be implemented to mitigate the identified privacy vulnerabilities (e.g. the proposed reconstruction attack in this paper) in machine unlearning?", "limitations": "See Weaknesses Section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The authors provide rigorous theoretical proof of the reconstruction attack.\n2. They conducted thorough experiments across different tasks, datasets, and architectures, demonstrating the effectiveness of their attack.\n3. The extension of the work to linear models with fixed embeddings and the generalization to other loss functions and model architectures showcase the adaptability and robustness of their method.", "weaknesses": "1. This work is limited to the exact unlearning scenario, i.e. retraining from scratch without the unlearned data, and focuses solely on unlearning a single data point. In contrast, the scenarios that have received more attention in unlearning research involve approximate unlearning and unlearning multiple data points at the same time.\n2. The experimental evaluation lacks diversity in metrics, which could provide a more comprehensive understanding of the attack's effectiveness.\n3. There is limited discussion on the potential defenses against the proposed attack.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*[Response to Weaknesses]* \n\nOur study is explicitly focused on exposing the risk present in even very simple models, such as linear regression, logistic regression, SVMs, and feature augmentation using random Fourier features. For such models, full retraining is feasible, and would be the expected solution to the data deletion problem, as computational approximations to retraining are not needed.\n\nFull retraining for a single data deletion in linear regression is equivalent to updating the model parameters using Newton's update as we discussed in Sec. 3.2. By leveraging this concept, our attack achieves almost perfect reconstruction, and the only error source is the estimation of the Hessian matrix using public data. For more complex models, a number of popular unlearning methods approximate full retraining by taking a Newton update. When we apply our attack to more complex models, we act as if full retraining results in the model that is derived from taking a newton step --- and the reason our reconstruction performance degrades is simply that this approximation becomes imperfect. However, if rather than full retraining, the machine unlearning method employed was one that simply took a newton step, our reconstruction would again be near perfect. We will elaborate on this point in the revision. \n\nRe: multi-sample deletion, our approach recover an approximation of the gradient sum for all the deleted samples. A determined adversary can poison an unlearning round by requesting deletion of n-1 samples known to the adversary, and so can recover the gradient of the single unknown point from this sum. Nevertheless we agree that multi-sample recovery is an important question that our work does not address, and think this is one of the most interesting questions for future work arising from our paper.\n\nOn the displayed metrics: We show both the full distribution of cosine similarity as well as randomly selected reconstructions for visual inspection. While other metrics such as similarity on a well-chosen embedding function could be of interest, we chose to simplify the presentation and show the more challenging (pixel-wise, for images) cosine similarity comparison. We are open to suggestions and are happy to engage if you have particular additional metrics that you think would be informative.\n\nOn defenses: Our work highlights the privacy risk of unlearning in standard models. As we discuss in our work,  training models using differential privacy (at small epsilon values) provably prevents reconstruction, even in unlearning scenarios because of differential privacy's composition property. There is an exciting opportunity for research suggested by our work: is there a way to give unlearning methods which have meaningful privacy guarantees even when the additional model training procedure did not? \n\n----\n*[Response to Questions]* \n\nOn the use of “Avg” as a baseline: This is a straightforward way of leveraging information about the data distribution in a manner that does not incorporate any information about the model parameters. The “MaxDiff” baseline is also included, and this is motivated by the assumption that the overall performance of the update on held-out data would be, in relative terms, much smaller than the peformance difference of the sample being deleted (since this sample transitions from being in the training distribution, to being outside it)\n\nOn the robustness to model architectures: Our existing experiments already show results for a variety of simple models and loss functions on the same datasets (linear and logistic regression, ridge regression, ridge regression over random Fourier features, cross-entropy minimization over random Fourier features, as well as support vector machines over both raw features and random Fourier features).\n\nOn the computational complexity of the attack: Our attack in its most general form relies on a Hessian-vector product per public sample as shown in Eq. 13. This can be efficiently implemented in all common deep learning frameworks with a computational complextiy of $O(nd^2)$ with $n$ being the number of public samples and $d$ the number of parameters in the model. It is also possible to replace the Hessian computation altogether by using the Fisher information matrix, bringing the computational complexity down to $O(nd)$.\n\nOn countermeasures: The most straightforward countermeasure would be to train the original and updated models using differential privacy. This would provably prevent any reconstruction attack (as privacy composes across pairs of models if they are both trained privately). An exciting research direction suggested by our work is the study of unlearning methods in which the parameter update is itself differentially private with respect to the deleted samples --- and a fuller understanding of how this trades off with other unlearning desiderata.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xh4zB9ltn8", "reviewer": "Reviewer_YZsT", "summary": "This paper presents reconstruction attacks against Machine Unlearning in the following sense: the attacker is assumed to have access to a model's parameters before and after the removal of a single data point; they then produce a guess for this point, which is evaluated in terms of its cosine similarity to the original data point.", "questions": "Can you please explain your threat model choices (see Weaknesses above)?\n\nTypo: \"To simply the notation\"\n\nBaseline: an interesting baseline to consider would be the point from the public set that is closest to the target point in the private set; this would intuitively be a better baseline than MaxDiff. Could your methods beat this baseline?", "limitations": "These were appropriately discussed, although the authors should better emphasize that the threat model is not realistic.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "This paper is nice and easy to read. The description of the attacks is easy to follow, and the theoretical derivations are interesting.\nThe specific application of reconstruction attacks against machine unlearning is, to my knowledge, novel; it stems from a large body studying the privacy of machine unlearning.\nThe presented problem is also well-scoped, and this research opens the space for new studies in the area.", "weaknesses": "1. The threat model is unrealistic: it is far fetched to assume that the attacker has access to the model parameters (before and after unlearning), and yet at the same time to assume that they cannot see the target point x in this process. Now, strong assumptions such as this one have been used in prior literature; but usually their purpose is to set upper bounds on the adversary when proving the security of defenses. That is not the case here.\nA second assumption that is quite strange is that the attacker somehow knows the model's parameters, yet they don't know the training set Xpriv, and they need to rely on a public one.\n\n2. The authors focus on the very limited and quite simplistic scenario specified above. Yet they had various options for exploration:\n- what if the attacker only has black-box access to the model? Based on similar prior work that evaluated both white- and black-box access (e.g., Balle et al.), I would expect your attacks to transfer well.\n- You mentioned DP in several places, yet provided no evaluation of said defense: what parameter set can prevent these attacks?\n- What if more than 1 points were unlearned at once? Would your attack apply?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*[Response to Weaknesses]*\n\nWe take the position that security assurances should be based on minimal assumptions. Here, we view the assumption that an attacker who has API access to the model does -not- have access to model parameters to be dangerously strong. Consider for example a d dimensional linear model, as we study initially in our work. Just from query access, an attacker can recover the model parameters by querying the model on d linearly independent points and solving a system of linear equations. This requires no knowledge of the data distribution. So, there is no meaningful difference between white box and black box access in such scenarios.\n\nWhat about for more complex models? Even there the boundary between white-box and black-box access has been blurring. For example recent work [1] has shown that it is possible to reconstruct the embedding matrix from a production LLM model with only black-box access. And of course, open source models explicitly release parameters with each version of the model. \n\nAs for the fact that the attacker does not know the training set: first we note that the goal of a reconstruction attack is to recover data from the training set. Even for linear models, in which recovering the parameters given only black box access to the model is trivial, it is in general not possible to recover the training set from the parameters of a single linear model. To see this note that many datasets produce the same set of parameters --- linear regression parameters are e.g. invariant to rotations of the dataset For linear models, and the model can be expressed with only O(d) bits of information (after discretizing weights), whereas a dataset with n datapoints and d features requires Omega(n * d) bits to represent.  For larger models, existing state of the art methods such as [2,3] rely on creating a set of samples such that the realized model parameters satisfy the KKT conditions of the loss function (the parameters minimize the loss at recovered samples). The success of these approaches requires that datasets are trained on a small number of samples (e.g. 500).\n\n[1] Carlini, Nicholas, et al. \"Stealing part of a production language model.\" arXiv preprint arXiv:2403.06634 (2024).\n\n[2] Haim, Niv, et al. \"Reconstructing training data from trained neural networks.\" Advances in Neural Information Processing Systems 35 (2022): 22911-22924.\n\n[3] Buzaglo, Gon, et al. \"Deconstructing data reconstruction: Multiclass, weight decay and general losses.\" Advances in Neural Information Processing Systems 36 (2024).\n\n----\n\nRe: multi-sample deletion, our approach recover an approximation of the gradient sum for all the deleted samples. A determined adversary can poison an unlearning round by requesting deletion of n-1 samples known to the adversary, and so can recover the gradient of the single unknown point from this sum. Nevertheless we agree that multi-sample recovery is an important question that our work does not address, and think this is one of the most interesting questions for future work arising from our paper.\n\nOn defenses: differential privacy guarantees compose, so given two models (from before and after a deletion) each trained with $\\epsilon$-differential privacy, we have the guarantees of $2\\epsilon$-differential privacy. When examples are drawn from a distribution uniform on some data domain $\\mathcal{X}$, then $\\epsilon \\leq \\Omega(\\log|\\mathcal{X}|) is enough to provably prevent reconstruction. More generally differential privacy bounds the advantage that an adversary has attempting to reconstruct a sample given the model parameters (compared to their success rate ``just guessing''), and so precise guarantees depend on the entropy of the data distribution (as low entropy distributions allow high rates of \"reconstruction\" without the adversary even needing to see the model. These are standard/generic properties of differential privacy which is why we did not devote space to it, but we are happy to elaborate in the revision. \n\n----\n\n*[Response to Questions]*\n\nUnless we misunderstand, the ''baseline'' you propose could not be implemented without already knowing the private dataset: otherwise the attacker would have no way of knowing what the ``closest point to the target point'' in the private set is. Of course with knowledge of the private training set, there is nothing left to do. If we misunderstand your proposal please let us know, and we'll be happy to discuss further!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9ZphqT9rZ0", "reviewer": "Reviewer_zg9a", "summary": "This paper studies reconstruction attacks on machine unlearning. The authors propose a reconstruction attack that can accurately recovers the deleted sample given the pair of linear models before and after sample deletion. This is made possible by leveraging the closed-form single-sample training algorithm for linear regression as well as the ability to accurately estimate the covariance matrix of the training data from a public dataset. They also extend the attack to the setting where the model consists of a (fixed and known) embedding function, followed by a trained linear layer.", "questions": "See above weaknesses.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The problem studied in this paper is interesting.\n\n- The proposed attack achieves good performance for linear regression models.", "weaknesses": "- The proposed attack is based on strong assumptions. This paper assumes that the attacker has knowledge of the training data distribution, the model’s loss function, and the embedding function. However, this information is usually not published by the model maintainer. It is unclear how the attacker can obtain this information in practice. The authors should provide more details to justify these assumptions.\n\n- The proposed attack has limited applications. This paper mainly focuses on linear models, and it is unclear whether the proposed attack can maintain good performance with more complex models.\n\n- It is unclear which unlearning method is adopted in the experiments. Will the attack performance vary when different unlearning methods are applied?\n\n- The proposed attack relies on a public dataset with the same distribution as the training data. The authors do not provide information about the size of this dataset in their experiments. It would be more convincing if they could evaluate the effect of dataset size on the attack performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*[Response to Weaknesses 1]*\n\nThe assumption of having access to the training data distribution is standard throughout the membership inference literature. Because we are trying to compare the risks of data deletion to the known risks absent data deletion, we adopt the same model. In general we view this as an appropriately cautious assumption about what an attacker might know, especially when attacks are being used to assess model risk. You are right that it might sometimes be difficult for an attacker to find an appropriate sampling distribution, and understanding how much it can be relaxed is an important question in general for the entire literature on privacy attacks; but one that we view as outside the scope of this paper.\n\nIn our experiments, we assume the most commonly-used loss functions, including MSE, logistic loss, and hinge loss, and show positive results for each. Random fourier features are also widely used in areas where latency is a concern. \n\n----\n\n*[Response to Weaknesses 2&3]*\n\nAn important aspect of existing machine unlearning approaches is that almost all of them aim to approximate full retraining with reduced computational cost. These approximations are proposed due to the intense compute required for full retraining, especially for large neural networks and LLMs. \n\nOur study is explicitly focused on exposing the risk present in even very simple models, such as linear regression, logistic regression, SVMs, and feature augmentation using random Fourier features. For such models, full retraining is feasible, and would be the expected solution to the data deletion problem, as computational approximations to retraining are not needed.\n\nFull retraining for a single data deletion in linear regression is equivalent to updating the model parameters using Newton's update as we discussed in Sec. 3.2. By leveraging this concept, our attack achieves almost perfect reconstruction, and the only error source is the estimation of the Hessian matrix using public data. For more complex models, a number of popular unlearning methods approximate full retraining by taking a Newton update. When we apply our attack to more complex models, we act as if full retraining results in the model that is derived from taking a newton step --- and the reason our reconstruction performance degrades is simply that this approximation becomes imperfect. However, if rather than full retraining, the machine unlearning method employed was one that simply took a newton step, our reconstruction would again be near perfect. We will elaborate on this point in the revision. \n\n----\n\n*[Response to Weaknesses 4]*\n\nAs we mention in Sec. 4, in all our experiments, the dataset is split into two halves; the first half is used for training the private model, and the second half is used for attacking the trained model.\n\nThe public dataset is used to estimate the Hessian matrix, which is the covariance matrix for linear regression. The quality of the estimation increases asymptotically with respect to the number of samples in the public dataset, and it is the only source of error in attacking linear regression, thus, the attack performance behaves similarly to the quality of the estimation. This grows with the dimension of the model; we can elaborate on this point in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the leakage introduced by machine unlearning in simple settings, and shows that entire data points can be reconstructed.
While I agree with reviewers that the setting is not entirely realistic, I think this type of "bottom-up" work is valuable to gain a better understanding of the leakage of machine unlearning.
Decision: Accept (poster)