Machine Unlearning via Simulated Oracle Matching
Authors: Kristian Georgiev
Roy Rinberg
Sung Min Park
Shivam Garg
Andrew Ilyas
Aleksander Madry
Seth Neel
Venue: ICLR 2025 Poster (2025)
Keywords: machine unlearning
data attribution
training data attribution
privacy
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: principled and practical algorithm for unlearning training data by leveraging recent advances in predictive data attribution

Abstract: Machine unlearning---efficiently removing the effect of a small "forget set" of training data on a pre-trained machine learning model---has recently attracted significant research interest. Despite this interest, however, recent work shows that existing machine unlearning techniques do not hold up to thorough evaluation in non-convex settings. In this work, we introduce a new machine unlearning technique that exhibits strong empirical performance even in such challenging settings. Our starting point is the perspective that the goal of unlearning is to produce a model whose outputs are *statistically indistinguishable* from those of a model re-trained on all but the forget set.  This perspective naturally suggests a reduction from the unlearning problem to that of *data attribution, where the goal is to predict the effect of changing the training set on a model's outputs. Thus motivated, we propose the following meta-algorithm, which we call Datamodel Matching (DMM): given a trained model, we (a) use data attribution to *predict* the output of the model if it were re-trained on all but the forget set points; then (b) *fine-tune* the pre-trained model to match these predicted outputs. In a simple convex setting, we show how this approach provably outperforms a variety of iterative unlearning algorithms. Empirically, we use a combination of existing evaluations and a new metric based on the KL-divergence to show that even in non-convex settings, DMM achieves strong unlearning performance relative to existing algorithms. An added benefit of DMM is that it is a meta-algorithm, in the sense that future advances in data attribution translate directly into better unlearning algorithms, pointing to a clear direction for future progress in unlearning.

Published conference paper at ICLR 2025
ArTRIBUTE-TO-DELETT. MACHINE UNLEARNING VIA DATAMODEL MATCHING
Kristian Georgiev', ; Roy Rinberg? Sung Min Park*;
Shivam Garg**
Andrew Nlyas, Aleksander Madry', Seth Neel?
1 MIT EECS Harvard Business School Harvard SEAS
Sttanford CS
Microsoft Research "Stanford Statistics
ABSTRACT
Machine efffiiiing-fffciinntly removing the effect of a small "forget set" of training data on a pre-trained machine learning model-has recently attracted significant research interest. Despite this interest, however, recent work shows that existing machine unlearning techniques do not hold up to thorough evaluation in non-convex settings. In this work, we introduce new machine unlearning technique that exhibits strong empirical performance even in such challenging settings. Our starting point is the perspective that the goal of unlearning is produce a model whose outputs are statistically indistinguishable from those model re- re-trrined on all but the forget set. This perspective naturally suggests a reduction from the unlearning problem to that of data altribution, where the goal is predict the effect of changing the training set on a model's outputs. Thus motivated, we propose the following meta- mheaa-algorthm, which we call Datamodel Matching (DMM): given a trained model, we (a) use data attribution to predict the output of the model if it were re-trained on all but the forget set points; then (b) fine-tune the pre- trainer model to match these predicted outputs. simple convex setting, we show how this approach provably outperforms variety of iterative unlearning algorithms. Empirically, we use combination of existing evaluations and new metric based on the KL-divergence to show that in convex settings, DMM achieves strong unlearning performance relative to existing algorithms. An added benefit of DMM is that is a meta-algorithm,, in the sense that future advances in data attribution translate directly into better unlearning algorithms, pointing to a clear direction for future progress in unlearning.
INTRODUCTION
The goal of machine unlearning is to remove (or "unlearn") the impact of a specific collection of training examples from trained machine learning model. Initially spurred by regulations such the EU's Right to be Forgotten (Ginart et al., 2019), machine unlearning has found a variety of recent applications including: removing the effect of toxic, outdated, or poisoned data (Pawelezyk et al., 2024b; Goel et al., 2024); rectifying copyright infringement in generative models (Liu, 2024; Dou al., 2024); and even LLM safety training (Li al., 2024; Yao al., 2024).
This plethora of potential applications has prompted a growing line of research into better unlearning algorithms. An unlearning algorithm takes as input a model 9 (trained on dataset S) and a "forget set" SF C S. and outputs model fuz that "looks like" it was trained on the so-called "retain set" Sn = S \ Sr. Of course, one valid unlearning algorithm simply ignores the trained model 0 and trains new model fur from scratch on the retain set Sn- This algorithm clearly succeeds at the task of unlearning, since the generated Our really trained only on the retain set. But as model and dataset sizes continue to increase, or unlearning requests become more frequent, this approach becomes infeasible. The goal of unlearning is thus to approximate this naive retraining algorithm while imposing much lower computational burden.
"qqull contribution

---

Published a conference paper at ICLR 2025
For convex models (i.e., models obtained by empirical risk minimization over loss convex in parameter 0), there are fast unlearning algorithms that also enjoy provable guarantees (Neel et al., 2021; Graves et al., 2021; Izzo et al., 2021b; Mu & Klabjan, 2025; Qiao et al., 2025)
For large neural networks, however- where efficient unlearning is arguably most relevant, given the cost of training from scratch-the situation is considerably murkier. The only methods that obtain provable guarantees tend to significantly degrade accuracy and/or require significant changes to the training pipeline (Bourtoule et al., 2020a; Li et al., 2022). As a result, unlearning algorithms for neural networks typically rely on heuristic approaches that fine-tune an initial model 0 into an "empirically unlearned" model z.z. These approaches, however, have not yet led to consistently reliable unlearning algorithms, evidenced by variety of empirical evaluations and benchmarks (Hayes et al., 2024; Kurmanji et al., 2023; Pawelczyk et al., 2023). In particular, recent evaluations such U- URLiRA (Hayes et al., 2024) demonstrate that the predictions of the empirically unlearned model are often easily distinguishable from the "oracle" predictions by an adversary.
A pervasive challenge for fine-tuning-bssee approaches is what we refer to as the missing targets problem. In order to "unlearn" forget set point x E Sp, fine-tuning- based methods typically employ some version of gradient ascent on z, starting from 8, and gradient descent on the retain set SR in order to maintain performance. If left unrestricted, gradient ascent will continue to make the loss on arbitrarily high-wil we want, however, is increase the loss only until it reaches its counterfactual value, i.e., the loss on x of a model trained on the retain set SR. Ideally, we could terminate the algorithm when the model's loss on x reaches this "target" value, but the problem is that (a) we do not have access to the target; and (b) the optimal "stopping time" might be different for different points x E Sp. The result is the well-documented phenomenon of unlearning algorithms "undershooting" and "overshooting" the loss on different examples (Hayes et al., 2024).
This work. In this paper, we present new unlearning algorithm that sidesteps the issue discussed above, and (empirically) achieves state-of-the-ar unlearning performance. Our algorithm resembles prior techniques in that we rely on fine-tuning the trained model B. We deviate from prior work, however, through two main ideas:
1.
Oracle Matching (OM). Consider the following thought experiment: what if we could access the ouputs (but not the parameters) of a model trained on the retain set Sy² We show that such "oracle" access directly enables an efficient, algorithm. Rather than aanniiizingmmxximinee directly minimizes the difference between model outputs and oracle outputs subsample of the train set, thus sidestepping the aforementioned "missing targets" problem. Empirically, we find that the fine-tuned model also generalizes beyond the fine-tuning points, and in some way "distills" the target model into parameters 0'.
teo-tuuing-bused unlearning loss on the retain/forget sets, this algorithm
2. Oracle simulation. OM on its own not an unlearning algorithm relies on the very "oracle model" that it aims to replicate. Observe, however, that implementing OM does not require access to the weights of an oracle model, but only to its outputs on a fixed number of inputs. Thus, OM can be implemented efficiently given access an efficient routine for computing such outputs. Such a routine is precisely the target of predictive data attribution methods (Ilyas et al., 2024), where the goal is exactly to predict how model's outputs would change if its training dataset were modified. This leads to our second idea: instead of fine-tuning on "oracle" outputs, fine-tune on simulated outputs from predictive data attribution method. We show that despite these methods being imperfect, applying our OM algorithm simulated oracle outputs works nearly as well using the true oracle outputs.
The resulting algorithm, datamodel matching (DMM), not only achieves current state-of state-of-the-ar -he- performance (Figure 1), but also introduces reduction from unlearning to data attribution, allowing us to translate future improvements in the latter field to better algorithms for the former.
The rest of our paper proceeds follows. In Section 2, we formally introduce the unlearning problem, as well as the field of (predictive) data attribution. In Section 3, we strengthen existing unlearning evaluation by introducing a new metric called KL Divergence of Margins (KLoM). KLOM directly adapts a formal definition of unlearning (Neel et al., 2021) to be computationally and statistically tractable to estimate, and addresses some challenges faced by existing unlearning metrics. Then, in Section 4, we combine the two insights above (Oracle Matching and Oracle Simulation) into a simple algorithm called datamodel matching (DMM). Finally, in Section 5, we provide some theoretical
2

---

Published conference paper at ICLR 2025
justification for our algorithm using a case study of underdetermined ridge (linear) regression. In particular, we show that in this simple setting, the oracle matching (OM) primitive can provably lead faster convergence. We conclude with a discussion of limitations and directions for future work.
Average
Porget
Retain
Validation
10
CIFAR-11
BB
KLoM
GA
X
SCRUB
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Do Nothing
Rotrain
LJVING-17
10
D30 Dtrect
KLoM
MM Matciattinngg
X
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Time (fraction of full re-training: +)
Figure 1: Leveraging predictive data attribution enables effective unlearning. We apply differ- ent approximate unlearning methods to trained DNNs to unlearn forget sets from CIFAR-10 and ImageNet-LLving-17 17. We measure unlearning quality using KLoM scores (y-axis), which quantifies the distributional distance between unlearned predictions and oracle predictions (0 being perfect), To contextualize each method's efficiency, we also show the amount of compute relative to full re-training (x-axis). We evaluate KL.M values over points the forget, retain, and validation sets to ensure that unlearning is effective across all datapoints, and report the 95th percentile in each group; we also report their weighted average (Ist column). Our new methods based on data attribution (DM-DIRECY) and DMM) dominate the pareto frontier of existing unlearning methods, and approach the unlearning quality of oracle models (full re- re-training) at much smaller fraction of the cost.
2 PRELIMINARIES
In this section, we introduce some preliminary notation, definitions, and results. Throughout the section, we will let S xn be fixed dataset drawn from an example space X, and we define a learning algorithm A x - θ as (potentially random) function mapping from datasets to machine learning models 0. Finally, for an example E X. we use fz : + H to denote a model evaluation the example x (for example, this may be the k-dimensional per-class probabilities).
2.1 MACHINE UNLEARNING
Consider a machine learning model 0 ~ A(S)) trained on a dataset S. Given a "forget set" SF C S, and a corresponding "retain set" SR S \ Sp. the goal of an exact unlearning algorithm to compute a sample from A(SR) starting from the trained model 0:
Definition 1 (Exact unlearning (Ginart et al., 2019)). An unlearning algorithm U θ x 21 9 said to be an exact unlearning algorithu if. for all SE C &S, S,U() SF) A(SR), where represents equality in distribution over models.
Though compelling in theory, exact unlearnin tends to be too stringent criterion when applied to deep learning, often leading to computational infeasibility or degradations in accuracy (Liu, 2024).
This motivates look at approximate unlearning, which asks only for the distribution over unlearned models to be (c, -)--indistinguishable from re-training:
Definition ((s, -unllarrng (Neel al., 2021)). U is an (appo--pto unlearning algorithm if. for all O C Sp C. S we have that
SF) Pr Sr)
O S e (A(RR) E + Pr (A(R)) O] < e Pr (T((S) Sp) e 0 +
This definition (intentionally) resembles differential privacy (Dwork & Roth, 2014), and asks for the distribution of unleareed models to be statistically close to the distribution of re-trained "oracle"
3

---

Published conference paper at ICLR 2025
models. In particular, this condition guarantees than an adversary who observes the model returned by the unlearning algorithm & cannot draw any inferences with accuracy that is much higher than if the model was fully re-trained.
While unlearning algorithms achieving Definition 2 exist for convex models (Neel et al., 2021; Izzo et al., 2021b; Guo et al., 2019), and for non-convex models when the training process is altered or under stylized optimization conditions (Bourtoule et al., 2021; Chien et al., 2024; Gupta et al., 2021), the bulk of ongoing work in unlearning evaluates Definition 2 empirically, rather than as a provable property. We return to the problem of evaluating unlearning algorithms more carefully in Section 3.
2.2 PREDICTIVE DATA ATTRIBUTION (DATAMODELING)
Our work also draws on a separate line of work in machine learning called data attribution (Koh & Liang, 2017; Hammoudeh & Lowd, 2024; Ilyas et al., 2024). Broadly, data attribution is area concerned with connecting training data samples to the predictions of the corresponding ML models. Of particular relevance our work is a particular type of data attribution called predictive data attribution (also known as datamodeling (llyas et al., 2022; Park et al., 2023)).
In predictive data attribution, the goal to produce an estimator (or datamodel) that takes as input a training set, and output accurately predicts the behavior of machine learning model trained on that training set. Using our existing notation: for an example æ E X, a datamodel for æ a function f: 2 - I such that, for any S" C.
f (<((S"))
In other words, (S') directly predicts the result of applying the training algorithm A to the dataset S', and evaluating the function f on the resulting model. Despite the complexity of modern training algorithms A (e.g.. training deep neural networks with stochastic gradient descent), Ilyas al. (2022) empirically show that linear datamodels often suffice to accurately predict model behavior. In other words, for an example x, one can compute a vector 3 E R such that, for subsets S' C S,
fa()))== = Σ 3 fa(('))).
2:ES"
To compute these coefficients, llyas et al. (2022) sample a variety of subsets S from 8, and then solve the (regularized) regression problem
Ss at random
m
B = min WER"
4 w 1s. - (=(As)))) + A||we||1-
171
They show that despite the datamodel being constructed using random subsets S; C S, the function if remains remarkably accurate non-random datasets (see Ilyas al. (2022) for a full evaluation). Linear datamodels are particularly appealing for two reasons. First, the coefficients & have an intuitive interpretation
the influence of the i-th training example a model's prediction (Koh & Liang, 2017; Feldman, 2021). Second, they establish a connection to a class of statistical techniques relating to influence functions, which has unlocked a suite of tools for estimating the coefficients more effectively (Park et al., 2023; Grosse et al., 2023).
3 EMPIRICALLY EVALUATING UNLEARNING
In Section 2, we introduced the unlearning problem, culminating in formal definition of the problem (Definition 2). As stated, evaluating whether Definition 2 holds for given unlearning algorithm is difficult problem for several reasons. First, given the overparameterized nature of large-scale models, fully satisfying Definition 2 is likely impossible, and verifying it involves comparing distributions in a space with millions or billions of dimensions. Secondly, the definition generally needs to hold over arbitrary forget sets Sr, at least across a range of forget sets SF likely occur practice.
The current evaluation paradigm. To deal with these problems, one typically evaluates unlearning by focusing on model outputs fz rather than model parameters, and testing for the implications of
'A common choice of model output used in prior work, which we will also use, is the margin of the classifier.
4

---

RA, study Published conference paper at ICLR 2025
Definition rather than for the definition directly. In particular, the strongest existing unlearning evaluation for supervised learning, called U-LİRA (Hayes et al., 2024), takes inspiration from membership inference attacks (MIAs) (Carlini et al., 2022) and evaluates the ability of an adversary to distinguish between the distribution of outputs of unlearned model on (a) validation examples and (b) unlearned examples.
A more direct evaluation. Recall from Section 2 that traditionally the target of unlearning algorithms has been (e, -approxiittee unlearning (Definition 2). Note that in essence, Definition 2 simply asks for the distribution induced by the unlearning algorithm be "close" to distribution of models that have never been trained on Sp. In particular, we can view it as special case the condition
As(U(A(S)) Sr); safe(Sr)) S,
where As is statistical divergence measure parameterized by 8 >> O, and safe(Sr) is distribution of "safe" models (i.e., models that have not been trained on SF). We can recover Definition 2 exactly by letting safe(Sp) be exactly A(S \ SF), i.e. the distribution of models trained on all but the forget set and setting As appropriately.
We make two observations about (4). First, the choice of safe(Sp) is somewhat arbitrary, and in particular any distribution that does not depend on Sp. and produces a useful model would suffice. This includes, for example, distributions A' \. Sp) for algorithms A'' of A. or distributions of ensembles of models A(S') \ Sp). Second, while the As used Definition 2 has an appealing privacy interpretation, it is sensible (especially given focus on empirical evaluation)
consider other divergences that are easier to estimate. These two observations inspire a metric that we call KL for empirical unlearning evaluation. KLoM corresponds to Definition 2 where we (a) use A KL divergence, (b) allow for an arbitrary "reference distribution" sF)e(Sp), and (c) as in distributions of model outputs fz rather than parameters.
Definition 3 (KL divergence of margins (KLoM)). For unlearning algorithm U, reference distribu- tion safe Sp), ), and imput x, the KL divergence of margins (KLoM) is given by
KLOMUU, (a) x)) == DKI=DDee((afffpp (e(U(A()),
Despite the arbitrariness of Sp), unless otherwise noted we will mirror Definition 2 and take safe(Sr) == A(S \ Sp). Throughout the rest of this work, we primarily evaluate unlearning algo- rithms via computing KTOM for different inputs x from the forget set, retain set, and validation set. We also evaluate our algorithms with J-LiRA, and defer these results to the Appendix.
Compared to U- LiRA,, KLOM is simpler to implement, has natural correspondence with our original Definition 2, and importantly, does not suffer from catastrophic unlearning: observe that an unlearning algorithm 2/ that transforms its input into random classifier will pass U-LiRA RA evaluation, as the random classifier will treat unlearned points and validation points identically. In contrast, by forcing us explicitly specify safe(Sr), KLOM explicitly compares unlearned models to a baseline whose performance we know a priori. Crucially, both KLoM and U-Li RA evaluate unlearning algorithms using point-specific distributional estimates, which as observed in Hayes et al. (2024) makes these evaluations far more stringent than prior approaches.
4 DMM: UNLEARNING BY SIMULATED ORACLE MATCHING
Having defined an evaluation apparatus, we now introduce our algorithm for machine unlearning. We first motivate the algorithm by observing common challenge in existing methods. We then, in Section 4.2, propose an effective hypothetical algorithm for unlearning, under the unrealistic assumption that we have access to outputs of the "oracle" model. In Section 4.3, we show how to accurately simulate such oracle outputs using data attribution methods. Finally, in Section 4.4, we combine these insights and present our final algorithm, datamodel matching (DMM), and demonstrate its effectiveness and efficiency.
4.1 MOTIVATION: THE MISSING TARGETS PROBLEM
Recall that the goal of unlearning is to approximate an oracle model, i.c., a model that was never trained given "forget set" of data. In strongly convex settings, this oracle model is unique, since
5

---

Published conference paper at ICLR 2025
it corresponds the minimizer of strongly convex loss function over the complement of the forget set (called the relain set). Thus, running gradient descent (GD) on the retain set loss yields a provable (and in some cases, efficient (Neel et al., 2021)) unlearning algorithm.
In the context of deep neural networks, however, GD alone is insufficient. In these settings, the loss function and training data alone do not fully specify the final model. In particular, once we have already minimized loss on the forget set, applying GD on the retain set does not significantly alter forget set predictions, preventing us from recovering the oracle model. Many unlearning methods for deep neural networks (Triantafillou et al., 2023; Kurmanji et al., 2023) thus actively increase loss the forget set (c.g., via gradient ascent) while maintaining performance on the retain set.
This general approach comes with significant set of drawbacks, which we collectively refer as the missing targets problem. First, the assumption that forget set points will increase in loss after unlearning and retain set points will not is not necessarily correct. For example, if there duplicated points across the forget and retain sets, then loss on points in the retain set might increase, while loss on points in the forget set might not change. Second, even for forget set point whose loss does increase under the oracle model, our goal is not to increase loss arbitrarily, but instead only until it reaches its "target value" under the model. Since we lack access these values, it is challenging to know when a given forget set point has been "unlearned." Prior work tries to address this by devising heuristic regularization schemes, e.g., via early stopping, but nevertheless often overshoot or undershoot the target loss for given data point. Figure 2 illustrates this phenomenon for a popular unlearning algorithm called SCRUB: over iterations the algorithm, different points are unlearned (and then subsequently "overshot") at different points in time (Hayes et al., 2024).
Porpst set
Betsin est
Valddtion ont
1pach
Byock
The missing targets problem. We apply the SCRUB (Kurmanji et al., 2023) algorithm to unlearn a forget set of CIFAR-10, 10, and measure how well different (random) points are unlearned over time. To quantify how well given point x is unlearned, we fit Gaussian distribution the outputs of oracle models on x, and compute the likelihood of the average outputs from unlearned models under this distribution. For many examples in the forget set (shown in red), unlearning quality hurt by training for too long as we lack access to oracle targets.
Figure 2:
4.2 THE ORACLE MATCHING ALGORITHM
In essence, the underlying challenge is that we do not know the oracle model's behavior priori. But what if we did have access to its predictions? In particular,
Given access sample outputs from the oracle model (re-trained without the forget set), efficiently fine-tune an existing model (trained on the full dataset) to match the outputs out of sample?
While assuming access to oracle outputs is unreasonable--inee our goal is to produce an oracle model in the first place-later in Section 4.4, we will replace oracle access with an efficient proxy using data attribution. For now, we simply assume we have direct access to oracle predictions, and focus on understanding whether gradient- based optimization can match predictions of the oracle. Even in this idealized setting, it is not clear how fast (if at all) gradient descent can converge to an oracle model. For example, whether we can do this efficiently with a small sample unclear; possible that fine-tuning the trained model can match the oracle predictions on the sampled points, but fail to generalize when evaluated on held-out points.
Formally, we assume access to predictions of an oracle model (xr) = f=((A(R)), where again SR is the retain set and fa is the evaluation of the model on input x (e.g., in classification settings one can take f to be the logits of the neural network). The Oracle Matching (OM) algorithm runs gradient descentto minimize the MSE between the output logits from the model (0) and oracle predictions poracle (x:) on samples from the forget and retain sets; the pseudocode in Algorithm C.I.

---

Published conference paper at ICLR 2025
Evaluating oracle matching. We evaluate OM on various forget sets on two image classification tasks: ResNet-9 models trained on (IFAR-10 and ResNet-18 models trained on ImageNet subset Living-17 17 (Santurkar al., 2020). We compare OM to the following unlearning baselines: gradient ascent (GA) on forget set, gradient descent (GD) on retain set, SCRUB (Kurmanji et al., 2023), no-op "Do Nothing" baseline, and partial or full re-training, We evaluate all methods using KI (Section 3) over distribution of 100 unlearned -peecfi--pecific) and 100 re-trained models (see Appendix F for more details).
Average
Forget
Retain
Validation
CIFAR-1D
KLoM (-)
10
GD
SCRUB
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Nothing
Retrain
LIVING-17
KLoM (-)
1.0
Oracle
Ocucle Mutcling
X
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Time (fraction of full re-training:
+)
Figure 3: Oracle matching can efficiently approximate re-training. The KLoM metric (y-axis) measures the distributional difference between unlearned predictions and oracle predictions (0 being perfect). We also show the amount of compute relative to full re-training (x-axis). We evaluate KLoM values over points in the forget, retain, and validation sets and report the 95th percentile in each group: we also report the average across groups (1st column).
The results (Figure 3) demonstrate that OM is able to efficiently match the predictions of the oracle. Models unlearned with OM closely match the oracle distribution- as measured by KLoM scores- across all splits of the dataset (forget, retain, and validation sets), significantly outperforming all of the prior gradient-based approaches. Importantly OM achieves effective unlearning while using less than 5% of the compute of full-retraining. In contrast, matching the performance of OM on the forget set by retraining requires spending more than 60% of full retraining time. The success of OM implies that for any given trained model 0 and the forget sets we studied: i) there exists another model O' close in parameter space that yields similar predictions as an oracle retrained without the forget set; and ii) I can be fine-tuned to quickly converge to 0' with sufficient sample of oracle outputs. We find that using a sufficiently high ratio of forget points in the fine-tuning tine-tuning set and a sufficient fraction of retain points (but still much smaller than the full train set) is able provide enough guidance (see Appendix G for exact details).
4.3 AN EFFICIENT PROXY FOR ORACLES: DATAMODELS
We saw that OM is highly effective at approximating oracle outputs, but OM is not practical algorithm as it assumes access to oracle outputs. To now turn this into a practical algorithm, we leverage methods for predictive data attribution (introduced in Section 2) to simulate oracle outputs.
Recall that datamodel fz predicts the counterfactual output of the model on input when trained on an arbitrary subset S \. SF: (s \ SF) x (A(()) ). In the case of linear datamodels, we can parameterize the datamodel with a vector 3(x) so that fz(S') (F) = Eies,s (x)).. Leveraging linearity, we can weiie this Eies (z(x) Eiesp (((x), and also replace the first term with the starting model output (0g). Our general algorithm, DM-DIRECT (Appendix C.2), simulates the oracle outputs as h(x) = (f6) - Eies, (z(z).
Estimating datamodels. To estimate datamodels, we follow the approach in (Ilyas et al., 2022): we train models random subsamples of the full training set and use sparse linear regression to fit datamodel vectors 3(x) (later in Appendix G.2 we explore alternative estimators).
See Appendix D.4 for detailed descriptions of each.
7

---

Published conference paper at ICLR 2025
Evaluating DM-DIRECT. In Figure 4, we compare model outputs on random forget and retain examples; the histograms show that the unlearned outputs from DM-DIRECT closely approximate the true oracle outputs. KLOM evaluations (Figure 1) show that DM-DIRECT (green line) in produces outputs close in distribution to that from oracle re- training for almost all points in the data distribution.
Forget example
Forget example 2
Forget example 3
Retain example 1
0.4
0.3
cnnele
unleammed mell
Density
0.2
0.1
0.1
0.0
10 -10 -5 0
10
-5
100 5.0
7.5
10.0
12.5
15.0
Margin
Figure 4: Datamodels predict oracle outputs. For random samples from the forget and retain sets, we compare the distribution (across multiple runs) of margins when evaluted on that example across three settings: i) null (model on full dataset); ii) oracle (model re- trarrined without forget set); and iii) unlearned (using DM-DIR DIRECT). In every case, the predicted outputs (orange) closely match the ground-truth (oracle), demonstrating the effectiveness of datamodels as proxy for oracle outputs.
4.4 ORACLE MATCHING WITH DATAMODELS
Now that we have an efficienty proxy for oracle outputs via datamodels, we revisit the OM algorithm from earlier. Our final algorithm, datamodel matching (DMM), first uses datamodels to generate approximations of oracle predictions on a subset of retain points and the forget points, and then runs OM on the datamodel predictions (see Appendix C.3 for pseudocode).
In Figure I, we contextualize the performance of DMM against baselines and DM-DIRECT from earlier. DMM achieves levels of unlearning similar to that of fully retraining the model (as measured by KLOM scores), while using significantly less compute." 3 Using datamodels allow us recover the performance of OM, and outperforms all prior gradient-basee approaches. Importantly, DMM also matches the test accuracy of the oracle model and maintains accuracy the points in the retain set (Appendix H,4), a common failure mode in prior methods. In particular, DMM is significantly more effective than partially re-training given the same computational budget. We do not include the cost of computing datamodels as this is a one-time cost and hence amortized over many unlearning requests. This is possible because once a predictive datamodel has been constructed (either via re-sampling as done here or influence function- approximations, which we explore in Appendix G.2), the datamodel generalizes well new forget sets in practice.
To better understand DMM, in Appendix G. we ablate different components of oracle matching and datamodel estimation. We show that OM addresses the motivating problem of missing targets, leading to stability in optimization. We also show that leveraging more efficient estimators for datamodels such as TRAK (Park et al., 2023) still yields effective unlearning via DMM.
ORACLE MATCHING FOR LINEAR MODELS
We have seen that empirically OM outperforms standard gradient-based unlearning methods, and have highlighted the missing targets problem as one possible explanation. Are there other factors that contribute the success of OM relative to prior methods gradient-based methods, and understand what settings we expect OM to perform well? This motivates studying a setting where the missing targets problem is neutralized: when the objective is strongly convex. In this setting, the unlearned model is the unique empirical risk minimizer on X and GD initialized at the current model is a provably effective unlearning algorithm (Neel al., 2020). Even in the setting when GD on its own can converge, does providing "guidance" from an oracle help?
better
We answer this affirmitively: First, in Subsection 5.1, empirically identify two factors that influence whether OM outperforms GD: the degree of regularian regularization and stochasticity in optimization. Next, in
Wee only count the finetuning cost; the cost of computing datamodels is amortized across unlearning updates. "The practice of not including pre-computation costs is standard in literature, e.g., Izzo al. (2021a).
8

---

Published conference paper at ICLR 2025
Subsection 5.2, we theoretically characterize the exact convergence rates of full batch OM and GD to the unlearned model in terms of the degree of regularization and the relative eigenmass on the forget and retain sets. Unlike in the full-batch setting where both algorithms converge at linear rate, the stochastic setting show that OM converges exponentially faster than SGD, which sheds light on the superior performance of stochastic OM in our empirical results.
Setting. We consider the following ridge regression algorithm, given by
A(5) == arg min
Σ (EL.9))ES
(0 x4 - y.) 2|10
where 2; Fd are the training imputs, 34 R are the corresponding labels, and the setting is overparameterized, so d > |S]. Given a model fru = A(S)) trained on full dataset S, our goal is to unlearn the forget set SF C S by obtaining a model that minimizes the objective on the retain set SR = S Sp. For convenience, we use X, XR. and X to denote the covariate matrices for the full dataset S, the retain set 5R. and the forget set SF respectively. We choose the under-determined ridge regression for three reasons: (a) The objective (5) is strongly convex, and so GD on X R is guaranteed to compute the (unique) unlearned model if ran for sufficiently many iterations; (b) the least-squares objective is amenable to theoretical analysis; and (c) the parammetttte setting is most relevant to modern deep learning models where d > n.
Unlearning algorithms. Let 0, A(SR) be the minimizer of the ridge regression objective on the retain set (i.c., the unlcarning target). Starting from 0 = A(S), we evaluate several iterative first-order unlearning algorithms in terms of their ability to recover 0,: (i) GD minimizes the ridge regression objective on the retain set Sn using gradient descent with constant step size, starting from Oun (ii) GDA incorporates forget set points in the gradient descent updates, combining gradient descent on the retain set with gradient ascent on the forget set; (iii) OM assumes query access to an unlearned model 0*, and uses gradient descent (with constant step size) to minimize squared error with respect to "oracle" predictions x l on the full dataset, aiming to minimize ||.X0 x0.11 OMRS performs gradient descent on the squared error from oracle predictions but only on the retain set, thereby minimizing the objective , x | We analyze both the full-batch and stochastic versions of these methods. See Appendix E.3 for details on the setup of the algorithms we evaluate.
OM
OM retain set
GD
GD+GA
120
180
staps
(a) small X, full-batch
(b) large X, full-batch
(c) small X, stochastic
(d) large X, stochastic
Figure 5: Comparing unlearning methods for a linear model with d = 400, n 100, |Sp| = 5. The
y-axis shows the relative squared distance to the optimal unlearned model R(0,) -
11u.- where 0, is the iterate time f, Oun is the model trained on all data, and 0, is the optimal unlearned model.
5.1 LINEAR MODEL EXPERIMENTS
Figure 5a depicts the performance of the four unlearning algorithms we consider with low regular- ization (A = 4) in the full-batch setting. We observe that OM converges to the unlearned solution much faster GD, while GDA and OMRS both fail to converge even as - oc. Given that OMRS makes negligible progress, we can conclude that the success of OM is due to inclusion of the forget points. Investigating further, we observe that during unlearning, the model parameters change the most in directions orthogonal to the retain set: despite the fact that 24% of the mass of the forget set points lies the span of the retain set, this span actually captures less than 0.01% of the mass the ground-truth update 0, Oun GD is only able to make progress orthogonally to the retain set due to the the & regularization term, and when À is low, this rate of progress is slow. On the other hand, OM makes rapid progress in these directions due the inclusion of forget set points. In Figure 5b, consider the same setting as above but set À to a much larger value of 400. Here, GD converges slightly faster than OM due to the stronger le regularization, which aids GD in converging along directions

---

Published conference paper at ICLR 2025
orthogonal to the retain set. Thus. OM converges faster than GD when À is moderate but can be slower with large A. In both settings OMRS and GDA do not successfully converge, but GDA- GDA-guided makes significant progress towards 0. before
by the heuristic use of the forget set points- eventually diverging. In Figures 5c and 5d, we replicate the experiments above with stochastic variants of the unlearning algorithms. As in the non-stochastic case, we see the OM on the retain set fails to make any progress, and that GDA makes quick progress but then diverges. However, unlike in the full- batch setting, SOM outperforms SGD in both the large and small À settings (see Appendix E.3 for a discussion). This surprising finding is characterized in Theorem 2 below, where we show that SOM converges exponentially faster than SGD.
5.2 CONVERGENCE THEORY
We now turn studying the algorithms theoretically, starting with the full-batch case, corresponding to Figures Sa and 5b above; then the kochastic/miniiatthii case (Figures 5c and 5d). In all cases, we will focus the two convergent algorithms above: oracle matching and ridge gradient descent.
Full-batch case. In Theorem I, we provide a theoretical analysis the convergence rates of GD and OM. The key takeaway here is that the convergence rate for both algorithms depends on both (a) the relative eigenmass of the forget and retain sets; and (b) the strength of the ridge regularization.
Theorem 1 (Proof in Appendix F. Let S and Sn be the full training set and the retain set respectively, with imput matrices X and X and corresponding labels y and yn. Additionally, let 0ju and O- denote the optima of the ridge objective (5) for the full data S and retain set SR respectively. After t iterations of unlearming starting from Ofuii, the iterate O2 satisfies
(I 212)) (I- 1-2 11-121XXA XRR
(0nun - -..) for ridge gradient descent (GD). for oracle matching (OM).
0: - Og =
2nx X)' (0jull 0.)
Theorem I shows that both (full-batch) OM and GD exhibit linear convergence, albeit at different rates. Indeed, in directions orthogonal to the retain set, the middle term in the GD convergence rate disappears, and so the rate depends only on 1/λ. Thus, as long as the learning rate 1) is set high enough (i.e., not to cancel out the X) higher regularization will cause GD to converge faster.
Stochastic case. In our experimental analysis, we saw that unlike the full-batch case, the stochastic version of oracle matching was consistently more effective than that of gradient descent. In Theorem we show that, at least in the setting of under-determined ridge regression we consider here, this observation is strongly supported by theory. In particular, we show that while OM converges at a linear rate (i.e., exponentially fast in t), we can show a l 1) SGD, giving strong separation between the two methods.
(2) lower bound on the convergence of
Theorem 2 (Proof in Appendix E.2), Consider the setting of Theorem 1, where Og is the iterate after t steps of unlearning initialized at fuutt Further let Timnn Tmaz denote the minimum and maximum eigenvalues of X X, and let A and B be lower and upper bounds on the norm of the covariates (i.e., |+
B 2
2 A for all i). Then, as long as the learning rate E (0, 507maa +xj) and rank( > 1,
2
EE 110 0-1 1|2
[0((1- "m) for oracle matching (OM).
full
11
E
(2)))
for ridge gradient descent (GD).
(6)
The intuition is as follows. In each update step, stochastic OM updates the model parameters only in the span of the random subset of points used for that update. In contrast, stochastic GD decays the model parameters in other directions due to the regularization term. (Recall that this is what led to GD's s improved convergence the in the subspace orthogonal to the retain set, stochastic GD also decays the parameters along the directions spanned by retain set points that are not in the current batch. So, while increasing improves full-batch GD's 's convergence speed, this advantage does not hold for stochastic GD.
setting.) While this shrinkage beneficial
6 CONCLUSION
In this work, we have shown that reducing unlearning to predictive data attribution yields a general and effective framework for unlearning.
10

---

Published conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We thank Jamie Hayes and Ilia Shumailov for discussions machine unlearning and ULIRA. We thank Salil Vadhan for some useful discussions throughout the paper. RR was supported in part by NSF grant BCS-221880S Additionally, we acknowledge Harvard SEAS and MIT CSAIL for providing computational resources.
REFERENCES
Juhan Bac, Wu Lin, Jonathan Lorraine, and Roger Grosse. Training data attribution via approximate unrolled differentation. arXiv preprint 1rXiv:2405.12186 2024.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning, 2020a. URL
https::// /ttpvvaxiivvvv////////e////aaava org/ abs/ 1912..91.1111 03817.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning, 2020b. URL
https:://// httpss///xxxvv..rg/../.
03817.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. 42nd IEEE Symposium Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021, pp. 141-159, IEEE, 2021. doi:
200.://4440002222.0000000 URL https: /tt.d/oo.ogoo//oo/oo
1109/SP40001 2021 00019.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning, In 2015
IEEE symposium on security and privacy, pp. 463-480. IEEE, 2015.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914, IEEE, 2022.
Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li. Stochastic gradient langevin unlearning, 2024.
Sang Keun Choe, Hwijeen Ahn, Juhan Bae, Kewen Zhao, Minsoo Kang, Youngseog Chung, Adithya Pratapa, Willie Neiswanger, Emma Strubell, Teruko Mitamura, al. What is your data worth to gpt? llm-scale data valuation with influence functions. arXiv preprint arXiv:2405. 13954, 2024.
Guangyao Dou, Zheyuan Liu, Qing Lyu, Kaize Ding, and Erie Wong. Avoiding copyright infringe- ment via machine unlearning. 2024. URL https: //tp://aavvvv//aa///a//eeee.aava org/ob//////o allgg//bb//// 2 10952. 209520992.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy, aug 2014. ISSN 1551-305X. URL https: /ttp://....//11...........000000
Ronen Eldan and Mark Russinovich. Who's harry potter? approximate unlcarning in 1lms. arXiv preprint arXiv:2310.02255 2023.
Logan Engstrom, Axel Feldmann, and Aleksander Madry. Dsdm: Model-aware dataset selection with datamodels, 2024.
Vitaly Feldman. Does learning require memorization? a short tale about long tail, 2021. URL https://arwa org/ abs/aaassaa/ /1tbs//99/ 05271.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235. 2023.
Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. Making ai forget you: Data deletion in machine learning. Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), 2019.
11

---

Published conference paper at ICLR 2025
Shashwat Goel, Ameya Prabhu, Amartya Sanyal, Ser-Nam Lim, Philip Torr, and Ponnurangam Kumaraguru. Towards adversarial evaluations for inexact machine unlearning. arXiv preprint wwXiv:2201.06644 2022.
Shashwat Goel, Ameya Prabhu, Philip Torr, Ponnurangam Kumaraguru, and Amartya Sanyal. Cor- rective machine unlearning, 2024. URL htt.:ppp////axii..rrrraaa/////// 14015.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. 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.
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Roger Grosse, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, et al. Studying large language model generalization with influence functions. arXiv preprint arXiv:2308.0322 2023.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learing (ICML), 2019.
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharif-Maalvaeedi, and Chris Waites. Adaptive machine unlearning. ArXiv, abs/2106.04378, 2021. URL https://apt. semanti cacholar. www.:laar..r/ooouuootttaa 235367846.
Zayd Hammoudeh and Daniel Lowd. Training data influence analysis and estimation: survey. Machine Learning, 113(5)2351-2200; 2024.
Frank R Hampel. The influence curve and its role in robust estimation. Journal of the american statistical association, 69(346):383-393 1974.
Jamie Hayes, Ilia Shumailov, Eleni Triantafillou, Amr Khalifa, and Nicolas Papernot. Inexact unlearning needs more careful evaluations to avoid a false sense of privacy, 2024.
Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclere, and Aleksander Madry. Datamodels: Predicting predictions from training data. CoRR, hbss/202..00622, 2022. URL
https: /tte:///aaxxiee aaa/aaiiiiii.//.i org/ abs
Andrew Ilyas, Kristian Georgiev, Logan Engstrom, and Sung Min (Sam) Park. Data attribution at scale: leml 2024 tutorial, 2024. URL https: / /mmm/mmmaaaaaaa aanl--daa-tuutrrii -tutoriall org/. Accessed: 2024-09-24.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS), 2021a.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models, 2021b.
Louis Jaeckel. The infinitesimal jacklnife. Bell Telephone Laboratories, 1972.
Jinghan Jia, Jiancheng Liu, Parikshit Ram, Yuguang Yao, Gaowen Liu, Yang Liu, Pranay Sharma, and Sijia Liu. Model sparsity can simplify machine unlearning, 2024. URL /tttps://arxiv. org/ aataab//2330 04934.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885 1894. PMLR, 2017.
Nupur Kumari, Bingliang Zhang, Sheng- Yu Wang, Eli Shechtman, Richard Zhang, and Jun- Yan Zhu. Ablating concepts in text-to-image diffusion models. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 22691-22700 2023.
12

---

Published conference paper at ICLR 2025
Meghdad Kurmanji, Peter Triantafillou, and Eleni Triantafillou. Towards unbounded machine unlearning, arXiv preprint arXiv:2302.09880, 2023.
Nathaniel Li, Alexander Pan, Anjali Gopal, Summer Yue, Daniel Berrios, Alice Gatti, Justin D. Li, Ann-Kathrin Dombrowski, Shashwat Goel, Long Phan, Gabriel Mukobi, Nathan Helm- Berger, Rassin Lababidi, Lennart Justen, Andrew B. Liu, Michael Chen, Isabelle Barrass, Oliver Zhang, Xiaoyuan Zhu, Rishub Tamirisa, Bhrugu Bharathi, Adam Khoja, Zhenqi Zhao, Ariel Herbert- Voss, Cort B. Breuer. Samuel Marks, Oam Patel, Andy Zou, Mantas Mazeika, Zifan Wang, Palash Oswal, Weiran Lin, Adam A. Hunt, Justin Tienken-Harder Kevin Y. Shih, Kemper Talley, John Guan, Russell Kaplan, Ian Steneker, David Campbell, Brad Jokubaitis, Alex Levinson, Jean Wang, William Qian, Kallol Krishna Karmakar, Steven Basart, Stephen Fitz. Mindy Levine, Ponnurangam Kumaraguru, Uday Tupakula, Vijay Varadharajan, Ruoyu Wang, Yan Shoshitaishvili, Jimmy Ba, Kevin M. Esvelt, Alexandr Wang, and Dan Hendrycks. The wmdp benchmark: Measuring and reducing malicious use with unlearning, 2024. URL https: /ttp///aavvvv//va owg/abs/ 22403. 03218.
Xuechen Li, Florian Tramèr, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners, 2022. URL
Ken Ziyu Liu. Machine unlearning 2024, Apr 2024. URL https::ts///
kz wwwiu/bllg heagg//nlleaannnn
Siqiao Mu and Diego Klabjan. Rewind-to-delete: Certified machine unlearning for nonconvex
functions, 2025. URL https: ntttps://arxiv... http::/aaxvvvvooo org. abs wwwp/409. 2409.09778.
Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi Descent-to-delete: Gradient-based methods for machine unlearning. 2020.
Seth Neel, Aaron Roth, and Saeed Maiaiei-Mallajeerdi. Descent-to-dellte: Gradient-based methods for machine unlearning. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), 2021.
Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclerc, and Aleksander Madry. Trak: Attributing model behavior at scale, 2023.
Martin Pawelczyk, Seth Neel, and Himabindu Lakkaraju. In-context unlearning: Language models few shot unlearners, 2023.
Martin Pawelczyk, Jimmy Z Di, Yiwei Lu, Gautam Kamath, Ayush Sekhari, and Seth Neel. Machine unlearning fails to remove data poisoning attacks. arXiv preprint urXiv:2406. 17216, 2024a.
Martin Pawelczyk, Jimmy Z Di, Yiwei Lu, Gautam Kamath, Ayush Sekhari, and Seth Neel. Machine unlearning fails to remove data poisoning attacks, 2024b.
Daryl Pregibon. Logistic regression diagnostics. The annals of statistics. 94):705-7724 1981.
Xinbao Qiao, Meng Zhang, Ming Tang, and Ermin Wei. Hessian-free online certified unlearning, 2025. URL https://azxiv http://aawwxaxaaaaa../////
Shauli Ravfogel, Michael Twiton, Yoav Goldberg, and Ryan D Cotterell. Linear adversarial concept erasure. International Conference on Machine Learning, pp. 18400-18421. PMLR, 2022.
Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopulation shift. In ArXiv preprint arXiv:2008. 04455, 2020.
Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot. On the necessity of auditable algorithmic definitions for machine unlearning. In 31st USENIX Security Symposium (USENIX Security 22), pp. 4007-4022. 2022.
Eleni Triantafillou, Fabian Pedregosa, Isabelle Guyon, Sergio Escalera, Julio C. S. Jacques Ju- nior, Gintare Karolina Dziugaite, Peter Triantafillou, Vincent Dumoulin, loannis Mitliagkas, Lisheng Sun Hosoya, Meghdad Kurmanji, Kairan Zhao, Jun Wan, and Peter Kairouz. Neurips 2023 machine unlearning challenge. https: http////nnnaannnneeeeeeeeaa cha Lenge. git hituuu.... io, 2023. Accessed: 2024-05-29.
13

---

Published conference paper at ICLR 2025
Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learning models. In International Conference on Machine Learning, pp. 10355-10366. PMLR, 2020.
Yuanshun Yao, Xiaojun Xu, and Yang Liu. Large language model unlearning, 2024. URL https: 10633.
Zexuan Zhong, Zhengxuan Wu, Christopher Manning, Christopher Potts, and Danqi Chen. Mquake: Assessing knowledge editing in language models via multi-hop questions. arXiv preprint arXiv:2305. 14795, 2023.
14

---

Published conference paper at ICLR 2025
Appendices
Limitations
B Related work
C Pseudocode
18
C.I Oracle Matching
18
C.2 Datamodel Direct
18
C,3 Datamodel Matching
18
Experimental setup
D.1 Training setup
D.2
Constructing forget
19
D.3 Datamodel estimation
19
D.4 Unlearning Baselines
19
E
Linear model analysis
21
E.1
Proof Theorem
21
Proof Theorem
................................
21
E.3
Experiment details
24
E,4
Additional experiments
25
F
Unlearning evaluation
27
F.1
KL Divergence of Margins (KLoM)
27
F2
U-LiRA
28
Comparing U-LiRA to KLoM
................................
30
F4
Sensitivity of unlearning models and forget sets ................................
31
G Understanding effectiveness of datamodel matching
32
G.1 Unlearning stability of OM
32
G.2 Datamodel ablations
33
Additional results
36
Hyperparameter sensitivity unlearning algorithms
H.2 Per-sample unlearning time
37
H.3 Full KLOM evaluation
38
H.4 Model accuracy after unlearning
39
15

---

Published conference paper at ICLR 2025
A LIMITATIONS
In this work, we presented general framework for reducing unlearning to the related problem of predictive data attribution. Our fine-grained evaluations using KLoM-which directly measures the quality of unlearning in terms of the difference in the distributions of the unlearned model's outputs from oracle unlearning methods and approaches the performance of oracle re-training, To conclude, we discuss some limitations and promising directions for future work:
that DMM significantly outperforms prior gradient-based
Extending techniques and evaluations beyond classification. While our methods perform well in classification settings with few classes, extending them to work in settings with more classes (e.g.- full ImageNet or language-modelle modeeinod) would make them more practical. Extending our techniques directly (i.e., attributing and estimating all class logits) would incur heavy computational cost, so additional techniques will be necessary to make the algorithms more scalable.
Improving and understanding oracle matching. As we saw in ??, OM and DMM sometimes cause a mismatch on the retain set due to "reversing the overfitting." [Roy: todo- provide a reference to where this is defined. Better understanding the dynamics of the OM algorithm and leveraging other insights (e.g.. from the model distillation literature) would be valuable for making the matching part of our framework more stable. One potential direction is understand when and how better sampling strategies (instead of random subsampling of the retain set) can improve general matching algorithms. [Sam: more clever sampling strategies]
Reducing computational costs. Even the most efficient data attribution methods require a non-trive uni-trivial computational cost (at least on the same order as training the original model). Can we design other cheaper alternatives for data attribution that we can still leverage for-and are possibly tailored to -racticall unlearning scenarios without the full computational cost?
Applying to more practical scenarios. In our analysis, we only considered single unlearning requests (i.e., removing one forget set). A natural way of extending them to multiple unlearning requests is to apply DMM sequentially. However, it is plausible that after too many unlearning updates with DMM, the model diverges far enough so that we need to "recalibrate" the pre-computed datamodels. Analyzing how well existing unlearning algorithms and DMM compose under multiple unlearning requests and other practical scenarios can be valuable for understanding the practicality and failure modes of these methods.
B RELATED WORK
We provide a high level overview of prior works most relevant to our setting. For a more extensive survey of unlearning, see Liu (2024).
goals and evaluations. While other lines of work also study unlearning "concepts" "knowledge" (Ravfogel et al., 2022; Eldan & Russinovich, 2023; Kumari et al., 2023; Zhong et al., 2023), we focus on the data-driven notion of unlearning (Cao & Yang. 2015; Ginart al., 2019; Wu al., 2020; Neel al., 2021; Bourtoule al., 2020b). Our focus on approximate unlearning methods. However, other works (e.g., Bourtoule et al. (2020b)) aim for exact unlearning (e.g., by careful data partitioning and ensembling approaches come with provable guarantees, they often come at the cost of accuracy (Bourtoule et al., 2020b), so most unlearning algorithms for deep learning are approximate. This approximate nature necessitates empirical evaluations in lieu of a provable guarantee. One line of work adapts membership inference attacks (MIAs) evaluate machine unlearning (Golatkar et al., 2020; Goel et al., 2022; Hayes et al., 2024). Complementary to that, Pawelczyk et al. (2024a) evaluate machine unlearning methods' ability to remove backdoor attacks from the training set. More broadly, evaluation in these setting can be nuanced: Thudi et al. (2022) argue that due to the stochastic nature of deep learning optimization, approximate evaluation of machine unlearning is only well-defined on an algorithmic level, and not on an individual model instance level.
Machine unlearning:
leveraging differential privacy). While these
Prior unlearning approaches in deep learning. Due to challenges of developing rigorous un- learning methods in non-convex settings, typical approaches involve some form of pradient-based
16

---

Published conference paper at ICLR 2025
optimization. Strategies include: partial fine-tuning (Goel et al., 2022), combinations gradient descent and ascent (Kurmanji et al., 2023), and sparsity-regularizzed fine-tuning (Jia et al., 2024) among others. Our approach also employs fine-tuning, but differs primarily in that we address the common problem of "missing targets." Other approaches employ parameter updates based local quadratic approximation (Golatkar et al., 2020; ?) or influence function approximations (?); these be interpreted as also leveraging different forms of data attribution. However, approach is unique in its use of predictive data attribution only as guidance and still employing fine-tuning, which more flexible and robust strategy than direct parameter updates.
The primary method we compare against is SCRUB (and SCRUB+R) as it achieves the current state- of-the-art strong unlearning evaluations Hayes et al. (2024). At high level, SCRUB finetunes the original model to: i) maximize the KI. divergence between the probabilities of the original model and the new model on forget points; ii) minimize the KL divergence on retain points; and iii) also minimize test loss. Despite their alternative design choices from other fine-tuning approaches (e.g.. use of KL divergence), our analyses suggest that suffers from similar underlying challenges.
Data attribution. Key to our framework is a reduction to the problem of predictive data attribu- tion (Ilyas al., 2022; Park al., 2023). More broadly, the problem of attributing model predictions back to training data has been extensively studied in recent machine learning literature (Koh & Liang, 2017; Park et al., 2023; Engstrom al., 2024; Grosse et al., 2023; Choe et al., 2024: Bae et al., 2024), with some of the ideas originating from statistics (Hampel, 1974; Jaeckel, 1972; Pregibon, 1981). For an extensive survey on the topic, refer to Hammoudeh & Lowd (2024); Ilyas et al. (2024).
Model distillation. Our approach of fine-tuning on (simulated) oracle predictions has some similarity different line of work on knowledge distillation (?), e.g., distilling an existing "teacher" model (possibly an ensemble) to a "student" model (often smaller). We can cast oracle matching as distilling an oracle model into the current model. The main difference, however, is that in our setting, the model we fine-tune is already trained on the full dataset, and our goal is only to apply small update to this model.
17

---

Published conference paper at ICLR 2025
C PSEUDOCODE
C.I ORACLE MATCHING
Algorithm C.1 Oracle Matching (OM)
1: Input: Trained model oy; oracle predictions (or) fine-tuning set size r
2: Output: Unlearned model 0
3: for {1, T do
epochs Sub-sample points from retain set
4: Sn ( SF
5: Snic-tune = SF US
6: for Sine tume do
mini-batch D Compute loss
7:
I(O,) = (fc) foracle (x)]1²
8:
0.+1 0r Tt VoL(O.)
Perform update with gradient
9:
end for
10:
end for
11:
Return Model Or
C.2 DATAMODEL DIRECT
Algorithm C.2 DM-DIRECT
1: Input: Trained model 0g; datamodels (1x) for each S; forget SF
2: Output: A predictor h(()) S + R*
h(x) (0o) Σ (z)
iESF
4: End
C.3 DATAMODEL MATCHING
Algorithm C.3 Datamodel Matching (DMM)
1: Input: Trained model 0g; datamodels 3(-); fine-tuning set size
2: Output: Unlearned model
3: Sn S. SF
Sub-sample points from retain
4: Suoe-tune = Sp U
n
5: h DM-DIRECT(0 B,
Simulate oracles with datamodels T epochs mini-bater
6: for trtt = (f,,..., T,,, do
7:
for Sime tume do L(0,) = (ft) h(x) 12
8:
b Compute loss
9:
0.+1 = 0.
V VoL(0,)
b Perform update with gradient
10: end for
11:
end for
12: Return Model fr
18

---

Published conference paper at ICLR 2025
D EXPERIMENTAL SETUP
D.1 TRAINING SETUP
For 10. train ResNet-9 models' for 24 epochs with SGD with batch size of 512, momentum 0.9, and weight decay 5e 4. We set learning rate initially at 0.4, and a single-peak cosine schedule peaking the 5th epoch. We use momentum of 0.9 and weight decay of 5e 4.
For ImageNet Living 17 (Santurkar et al., 2020), we train ResNet-18 models for 25 epochs using SGD with batch size of 1024, momentum 0.9, and weight decay 5e 4. Label smoothing is set to 0.1.
D.2 CONSTRUCTING FORGET SETS
We evaluate methods across various types and sizes of forget sets to test the robustness unlearning. Our selection of unlearning scenarios span both random and non-random forgets of different sizes; that said, we view the non-random sets as practically more interesting. Compared to prior work, our target sets are harder to unlearn class.
remove small coherent subpopulation opposed to an entire
On CIFAR-10, 10, use 9 different forget sets 1,2,3 are random forget sets of sizes 10,100,1000 respectively; sets 4-9 correspond to semantically coherent subpopulations of examples (e.g., all dogs facing a similar direction) identified using clustering methods.
On ImageNet diving-17, we use three different forget sets: set 1 is random of size 500; sets and 3 correspond to 200 examples from certain subpopulation (corresponding single original ImageNet class) within the Living- 17 superclass.
D.3 DATAMODEL ESTIMATION
Regression-based. We re-train models on random 50% subsets of the full train dataset, and use between 1,000 and 20,000 models. We use the sparse linear regression based solvers from llyas et al. (2022) to estimate each datamodel vector. Though our main results are computed with 20,000 models, we find that using just 1,000 models suffice effective unlearning with DMM.
TRAK. We compute TRAK scores using 300 model checkpoints and 16328 projection dimensions using the code provided in Park et al. (2023).
D.4 UNLEARNING BASELINES
Most unlearning algorithms are highly sensitive to the choice of forget set; thus, so for each of the unlearning algorithms we compare to, we evaluate over grid of hyperparameters and report the best KLOM scores for each forget set. Below we describe each algorithm and indicate the respective hyperparameter grid.
Full/partial Re-training
Full retraining discards the original model and trains model from scratch using only the retain set SR- By definition, this achieves perfect unlearning. As additional baselines to tradeoff time and unlearning accuracy, we re-train for different number of epochs (on the same learning rate schedule), but keep all the other hyerpaarameters the same as in Appendix D.I.
II. Gradient Ascent (GA)
Gradient ascent iteratively updates model parameters to increase loss on the forget set. Starting from a trained model the algorithm computes the gradient of the loss L with respect to the model parameters over examples Diorges. These gradients are then used to iteratively adjust 0 in the direction that increases L.
Hy Hyperparameters: For each forget set, sweep over the following hyperparameters:
:/ap:s://iiii http://hwwaaaaaaaaaa/o//tt//a/aa cifar10.py
19

---

Published conference paper at ICLR 2025
1. Learning rate (1)): [10-5 10 1.10% 30-0,,0000 10 1).
2. Total unlearning epochs: 7,, 10).
III. Gradient Descent (GD)
Gradient descent achieves unlearning by fine-tuning the original model on the retain set SR. We note that in the convex setting this algorithm provides provable unlearning guarantees Neel et al. (2021).
Hyperparameters: For each forget set, we swept over the following hyperparameters:
1. Learning rate (1)): [10-3 10-1 10-3, 10-2].
2. Total unlearning epochs: [,, 10].
IV. SCRUB
SCRUB (Kurmanji al., 2023), the current state-of-the-art unlearning method, combines variants of GA and GD-based heuristics. During the first phase, it runs GA-like algorithm on the forget set while simultaneously running GD-like on retain set; in the second phase, it runs additional iterations of GD on the retain set. For the first phase, SCRUB specifically maximizes/minimize the KI. divergence between the logits the original model's predictions and the new unlearned model's predictions. See the original paper for more details.
plyerpaaraettrs:
For each forget set, we sweep over the following hyperparameters:
1. Momentum parameter 33 was set to 0.999
2. Retain batch size: 64
3. Forget batch size: 32, 64
4. Number of epochs for GA-based unlearning (maximization epochs) 1,3,5,7,9
5. Learning rates: [3 10-1 10-1,3 3 10-2
10.0,,3.. 10-2,10-2 10 1,33,3 10-4, 4,10. 1,004.3
10-5, 10-5,3 3 x 10-6, 10-6].
6. Number of total epochs: [5, 7, 10]
V. Do-nothing
This is "no-op" that simply returns the original (fully-trained) model. We include this as baseline as: typically this what is currently done in practice and ii) many existing methods (as our evaluations show) perform worse than this trivial baseline.
Implementations for all methods are available bit 1y www.annnnnnnnnemmmmmmmaa via-s wwa-simllateeeoeeeeooo.o
20

---

Published conference paper at ICLR 2025
E LINEAR MODEL ANALYSIS
E. PROOF OF THEOREM
We restate Theorem below.
Theorem 1 (Proof in Appendix E.1). Let S and Sn be the full training and the retain respectively, with input matrices and X and corresponding labels y and yn. Additionally, let faa and O, denote the optima of the ridge objective (5) for the full data S and retain set SR respectively. After t iterations of unlearming starting from Ofui the iterate O2 satisfies
(1-2n))² (I 1
27 2y Xn)R) (0pmt 0.) for ridge gradient descent (GD). 1122q
(1 (1-2 (0full) -0,) 0.) 02 - 04
for oracle matching (OM).
Proof. Note that by using the Taylor expansion of the ridge gradient descent objective around 0., we can rewrite follows:
|x00 ynll2 + 2ll@lk
(7)
1Xx0. yn 2 + >l 11 (0 0.)² (X +1) (0 0x)
(8)
= c (0 0.) Rx XT) (0-0,).
(9)
where e |X - yRll + 0100 |1011 112 is a constant independent of 6. Similarly, we can write oracle matching objective as
Xx - x0.1 = (0 - 00) x) (0 0.).
(10)
Note that both the ridge gradient descent and the oracle matching objectives can be written as
(0 0.)² 2) (0 0.) +
(11)
for some PSD matrix Z and some constant c. Gradient descent update on objective 11 can be written as:
= 0,-1 2n 2T 2(0,-1 10:1--00. 0.).
(12)
Subtracting 0, from both sides,
02 - 0, = -1- 2n 2)(0,-1 0-).
(13)
Unrolling the recursion, squaring both sides, and simplifying then yields the desired result.
E.2 PROOF OF THEOREM? 2
Theorem 2 (Proof in Appendix E.2), Consider the setting of Theorem 1, where Og is the iterate after t steps of unlearning initialized at ffull. Further let Tmaz denote the minimum and maximum eigenvalues of X X. and let and B be lower and upper bounds on the norm of the covariates (i.e., B 2 || 2 A for all i). Then, as long as the learning rate E (0, blymaz and rank( > 1,
Ymaz
2
E [10 0+ [12]
SO((1- - ))) for oracle matching (OM). (+
E
(6)
0 putl - 0.112
for ridge gradient descent (GD).
Proof. We will begin with a more general setting than the theorem. In particular, consider an arbitrary convex optimization problem of the form
min f(0),
where f(0) Σ f((0),
where the function f a-stronggy convex, and each fa is 3-smooth. In other words, we have that for any 0 and 0',
( Vf(0'),0 0¹) 2 all0 0'll
(f is a-strongly convex)
(0) - (())))) < 0 0 8'll for all e [n].
(each f. is B-smooth)
21

---

Published conference paper at ICLR 2025
Note that without loss of generality, we can restrict our attention the subspace spanned by X, in which case both oracle matching and ridge gradient descent are instances of this setting- for GD, Tmmin and "mar + X, and for OM a "mmn and "maz
We further define quantity of called gradient disagreement, measured as
of = E. [V.. [[.)1( =E, [IV
where 8, is the optimum of
Upper bound for OM. With these quantities defined, us begin with the OM upper bound. In fact, this follows directly from a standard SGD convergence proof, e.g., Theorem 5.8 of (Garrigos & Gower, 2023), restated below:
Theorem 3 (Theorem 5.8 of (Garrigos & Gower, 2023)). Suppose f is a-strongly convex sum of 8-smooth convex functions. Consider the sequence of iterates {0t)ee generated by stochastic gradient descent with fixed step size yj (0, 23 For 0,
2n a
[10 0.1 S (1 (1-na)'11g na) 0.11
o7.
few observations conclude the proof. First, any step size 1) S 5(7mma + also satisfies 1/ S 27man and we can thus apply the Theorem to our case. Second, for oracle matching, we have that
V (i( = (ar 0 ar 0.) wi.
which means that V)i( = and thus of 0, concluding the proof.
Lower bound for GD. We now show that for the same set of learning rates, the stochastic version of ridge gradient descent on the retain set cannot converge faster than 1/t². Key analysis will be that, for GD, the gradient disagreement o3 non-zero, so long as the dataset is non-degenerate. In particular,
07 = E, [IV
2 n
max | f...)))
max (x) - y,)ar + A0_11".
n
To see that this is strictly positive, we can proceed by contradiction. Suppose that of = 0. Observe that if a 0. yı for any [n]. then the corresponding f/ 4x21 11 and of 0. Thus, x. 0. * y; for all i. In this case, however, we must have that
(x) 0_ y: = Xo..
meaning that 0, is parallel oy. If raak(X) > 1, this is contradiction and so of > 0.
We can now continue with the rest of the proof. We start with some algebraic manipulation of the gradient update. particular, for a random E [m]]
0, 0. 0.-1 0, 1/V (0.
||0, 0.11 10,-1 1. 2 (m, 0. V)
Taking an expectation conditioned on 0,-1,
E ||0 2| 0 11 2n (6.-1 9., (((+=-1))+ + [
Now, we treat the second and third terms separately. In particular, for the second term,
201(0-1 - 0., f((,,1)) < 2n - 0.11 (((--)))
(Cauchy-Schwarz - V vf((.))l (Gradient at optimum is zero)
2n18100-11 0.1
(Smoothness)
22

---

Published conference paper at ICLR 2025
For the third term, we use the identity ||u v/12 < 2||u||2 + 2//2|1 which we can rearrange to be Letting V[i(0(-1) and v (S((0--1) (..(.))
||u[| 2 2 u -
|| =
e [IV
2 [V
"
- = [I [IV V=((0.)
2
2 B
7/
2
[VV[:
12 10:-1 - 0.12
2
n803
3/
110--1 -011
2
Combining everything far,
- + n209
E 01 - 0011 2 (1 2n2 32 - 02l1
Taking expectation with respect to previous iterates yields
[110g 1111 2 (1 2n13 - ./2 110 - -0.12+ n807 t-1
Σ
(1 (1-2n1 17 82
r=0
np03
(1 2n - 32) 110 - -0,12
12
m
|10 0.112
since 17 S 5,3
5
2
5 3. Note that log(1 -x) 2 22-22 for x < 1, and
For ease of notation, let C
--x
E [11 - 0.13 2 exp t. (t((-(n) 2 2-Cm)
On I- |10, 0,112 n'0 2
(14)
We now derive the learning rate 77 that minimizes (14), and show that at this optimal learning rate (14) (11(12). Note we can see this by inspection even without the formal derivation, because for (14)
to be O( we need ( so that the right hand term is O(1/t²), which forces the first term exp (t. (tC = (1). Now, to minimize the right hand side above with respect to we take the derivative and set zero (note that at the extreme points 1 0 and 17 53 are left with constant amount of error). The result of this calculation is the fixed learning rate that optimizes the error at time t. Again for ease of notation, let (()) 2-Cy, so that
d 0 dn
0003
exp (t (-Cr) 110. - 0.11
(g())()) + ng' (n)) exp (t-- |10 0, 2 no?
no Ct (g(n) + (xp ((00000) 0.11
log(no)) ) = log(t) (gggl((((((()++=((()))))))))
0. Ctn 9(n)
Ctn g(n) log(t) log(C(g(() + (n)) 01]l log(no7))
Cby g(r) > log(C(g(m) + ng' (1)) 10 - 0.ll) - log(no})
C(g(n) + ng (n)) 10u 0-1
> log
+ looo(111))
of
log
((g(n)++no(m)))000--
+ log(1/n)
07
Cn-g(n)
23

---

Published conference paper at ICLR 2025
Now, by definition of g(n), we have that for 77 E (0, 55)) g(n) S 26 and g(n) + n g'(n) 2 2. Thus:
log
2C (0-00111111 8-11
+ log(1/n)
of
t
26C
+ )
log
log(1/n))
26Ct 2
7
Using the fact that (1/g1/)) 2 1 x for x E (0, 1) yields:
log
2C 10
0-1l
+1
7
26Ct
-1
1)
log
20 10 -0-1 +1
07
7
26C't +
Plugging this result into (14) yields the desired 12(1/t²) lower bound.
E.3 EXPERIMENT DETAILS
Details of unlearning algorithms
We consider the various iterative algorithms for unlearning starting from Oal For all of them, we consider their full-batch as well as the stochastic version. For the stochastic versions, we use mini-batch size of 5. We search for the learning rate from {10, algorithms below:
10 10
200 }. We describe the
2: 2
1. Ridge Gradient Descent (GD): This involves minimizing the ridge regression objective with the retain set points (Xretain Mretain) using gradient descent.
2. Ridge Gradient Descent Ascent (GD+GA): This method aims to incorporate forget set points in the ridge gradient descent updates. Each step involves moving direction that is a linear combination of the gradient descent step on the retain set and the gradient ascent step the forget set. That is, we
0, = =0:11 7/grad (0--1) * grad forget (0.-1))
Here, grad (0) 2XT retuin (X Vretmin) 220 and grad (0) 2XT
forget (X Kforget
Mosga). We do hyperparameter search for a in {0.01, In the stochastic setting, each update step, we draw minibatch points uniformly at random from the full dataset, and calculate the ascent step term only if the drawn points include points from the forget set.
3. Oracle Matching (OM): Here, we assume oracle access to predictions made using the optimal model 0.. This method involves using gradient descent to minimize the the squared error from the oracle predictions on the full dataset: || N I|2. We include full algorithm of this in Algorithm C.I.
4. Oracle Matching on retain set (OM retain set): This involves using gradient descent minimize the squared error from the oracle predictions only on the retain set points:
X 0 0x
Slow convergence with stochastic gradient descent.
In Section 5, we saw that in the stochastic setting, OM converges much faster than GD, even when is large. Here, we dig deeper into the large experiment considered in Section 5 to understand this. We observe that stochastic GD remains stable only at small learning rates with large X, which results in slower progress. Specifically, while the optimal learning rate for full-batch GD similar in both large and small À regimes, for stochastic GD, it is about 100 times smaller in the large X regime. Using higher learning rate for stochastic GD in the large À regime leads to instability and non-convergence, issue not seen with stochastic OM.
24

---

Published conference paper at ICLR 2025
In each update step, stochastic OM adjusts the model parameters only within the span of the random subset of points used for that update. On the other hand, stochastic GD decays the model parameters in other directions due to the regularization term. Although we want the parameters to decay in the subspace orthogonal to the span of the retain set, stochastic GD also decays the parameters in directions spanned by the retain set points that are not part of the current update set. As a result, using a high learning rate for stochastic GD in the large À regime disrupts parameters in the span of the retain set. Therefore, while increasing À improves full- ball-batch GD's convergence speed and could potentially make faster than OM, this advantage does not apply to stochastie GD, which has to a much smaller learning rate.
In Figure E. la, illustrate how stochastic GD high learning rates disrupts the model parameters within the span of the retain set. We plot the progression of relative squared distance to the optimal
Here 0₂ is the iterate at time t, Qun is the model trained on the full dataset, 8, is the optimal unlearned model, and Pretain is the projection matrix onto the retain set span. We show this for iterates with the optimal learning rate, as well as for learning rates 4 times faster and times slower. As the learning rate increases, the iterates tend to diverge the span of the retain set.
unlearned parameter within the span of retain set points, [|P (0.000;-))))) -0111
10ma 0. 18
In Figure E. lb, we plot the progression of relative squared distance to the optimal unlearned parameter
orthogonal the subspace orthogonal to the retain set points, |a (9, 1I where Potth-retain is
66 10mn-8-153
the projection matrix for the orthogonal subspace. Here, we observe that increasing the learning rate beyond the optimal rate leads to faster convergence. Thus, while increasing the learning rate beyond the optimal value accelerates convergence in the subspace orthogonal to the retain points, it harms progress in the span of the retain set points. Therefore, in the large À regime, stochastic GD must operate at small learning rates to avoid disrupting the model parameters in the span of the retain set.
dist orthogonal to retain
CD opt
dist within retain
GD opt Ir
my m
M
GD 0.25x opt
1.0
0.5
0.5
0.0
0.0
50
100
150
200
250
300
50
100
150
200
250
300
number of steps
number of steps
(a)
(b)
Figure E.1: Stochastic Gradient Descent performance in the large À regime with varying learning rates. (a) The y-axis shows the relative squared distance to the optimal unlearned parameter within the span of retain set points, Pau -.11
(0,--00 00]13 where is the iterate time t, Oruil is the model trained
on the full dataset, 0. is the optimal unlearned model, and Pretain is the projection matrix onto the retain set span. Larger learning rates lead divergence within this span. (b) The y-axis shows the
relative squared distance to the optimal unlearned parameter in the subspace orthogonal to the retain
set points, P0 )1I. where Puthh retain the projection matrix for the orthogonal subspace. 10.1-
Larger learning rates result in faster convergence in this subspace.
E.4 ADDITIONAL EXPERIMENTS
In section 5, we discussed an example with linear models that highlighted the qualitative differences between oracle matching and other unlearning methods. Here, we show the comparison for another example with different covariance structure. We draw 100 training points (I,, y1) where x; are drawn i..d. from (0,, )) in 400 dimensions where covariance matrix Σ diag(1, 1/2, 1/3, 1/400) ( (.ag(.) represents a diagonal matrix with the specified entries on the diagonal). Y: = HT 6s where 0 is drawn from (0, I) and e; is drawn from N (00 1/4). These 100 points form (Xrutt- yrun)- We fit these points to minimize the ridge regression objective with À = 1/4 (for the small case) or (for the large À case), to obtain the model O Here À 1/4 /4 is the À value that minimizes the
25

---

Published conference paper at ICLR 2025
expected squared prediction enror. We want to unlearn 5 training points chosen uniformly random. We show the performance of various methods (in both the stochastic and full-batch setting with small and large A) in Figure E.2, Even here, we obtain the same qualitative patterns as Figure E.2.
GD+GA
1.0
1.0
0.8
0.8
R(0)
0.6
R
0.6
0.4
0.2
0.2
0.0
0.0
50
150
200
250
300
20
10
60
100
number of steps
number of steps
(a) small X, full batch
(b) large X, full batch
0.8
0.8
R
R
0.6
0.4
0.4
0.2
0.2
0.0
0.0
200
400
600
800
200
400
600
800
number of steps
number of steps
small A. stochastic
(d) large X, stochastic
Figure E.2: Another example comparing the performance of various unlearning methods with linear models.
26

---

Published conference paper at ICLR 2025
F UNLEARNING EVALUATION
F.1 KL DIVERGENCE OF MARGINS (KLoM)
Below we formally define the KLoM evaluation, which computes the distance between the distribution of outputs for unlearned models and re-trained models. For output, we use the classification margin. We also include visual representation of our algorithm in Figure F.I.
Algorithm F.1 KLoM
1: Input Number of models N, dataset D, forget set F C D, retain set R C D (such that
FU R), and a validation dataset V. training algorithm A, unlearning algorithm U, margin
function 6, and histogram function H (S).
2: Train N models (Oracles) on the entire dataset, excluding the forget set. @ = {A(D) F)).
G00 = N.
3: Train N models (Unlearned-model))) on the entire dataset, then for each model unlearn forget set
F. O (U), F)), |0/]
4: Initialize a vector of results with all zeros 7.
5: for each point x in Forget, Retain, Validation set do
Compute the margins for each oracle M, = (x)( 0%). Compute the margins for each unleared-mmoel My (6(0 e 8: Assign F[x] = (Mo)) Hi))(M,))
6:
7:
9: end for
10:
return F
Note that in order to approximate the KL divergence, we compute histogram HSS) that takes set of real numbers and returns an empirical probability distribution by truncating and binning samples from S.
For each poin deline out menoure Sy
miaisii(am (M})
Divegence
.M" - lin(((maniin((O)lal (M])
Generato histogram offiv) values.
Figure F.I: Visual diagram of KLoM
In practice, we compute KLOM using = 100 oracles compared to 100 unlearned models. For each point we evaluate we clip the N margins to range of [-100, 100) to exclude outliers (some methods, like SCRUB, result extremely large margins) into 20 bins. Then the KL-divergence is computed between the binned histogram of the oracles and the binned histogram of the unlearned models. For any region of the support where one histogram has no support, and the other does, the bin with support is set non-zero probability of 10-5, 5 We note, that for this reason, KLoM scores are artificially rescaled and capped at value around xz 12. This cap can changed by changing the number of bins the minimum value
27

---

Published conference paper at ICLR 2025
F.2 U-LIRA
At a high-level U-LiRA measures the distinguishabiliy of predictions of an unlearned model from that of retrained models based adapting membership inference attacks. Implementing the Algorithm F.2, as written, would be computationally infeasible in most cases, as it involves unlearning and retraining T times for each point (z, In practice, Hayes al. (2024) computes U-LiRA using the method Algorithm F.4.
Omitting few details, the main idea is as follows: consider unlearning algorithm  and training algorithm A. Start from model Og trained on a random subset 5 ~ PP, and unlearn one specific (random) forget set, produce 0p. Next, construct collection of shadow models by that producing many unlearned models from random training sets and random forget sets. Lastly for a collection of points in the retain set and in the forget set ([r|æ Sp SS} compare how Or compares the subset of shadow models that never-saw-2 distribution of margins for models that unlearned-r. Now u perfectly unlearns Sp, then Gu no longer depends on Sy, and so even conditioned on 0g the marginal distribution of x E SF 10g is still P; the same distribution any I E Sv. Operationalizing this intuition, U-Li RA with probability 2 draws either
S or x E Sv, and measures the output y (0o). An (optimal) adversary observes y. and tries to guess whether the corresponding was an unlearned point or a validation point, c.g. whether I E Sp or Sv. More generally, if U is an (c,d)-unlearning algorithm, the two distributions y/ E Sp, 6g and y/a: Sv, 0g would be (c, 6) --indistinguishable by post-proce post-processing, and so even the optimal adversary couldn't have accuracy greater than fee 5. The optimal adversary be implemented by training models with/without x, unlearning SF, and then measuring the output y. For a more detailed description of M-LiRA and overview of similar MIA-based approaches, we refer the reader (Hayes al., 2024) (Section 4.2), and we include the pseudocode for the computationally efficient version of this evaluation MaacienntULIRAA
Efficient- ULIRA in Appendix F.2.
Algorithm F22 U-LiRA (LiRA adapted for machine unlearning) (Hayes et al., 2024)
Args: model parameters to evaluate 8", learning algorithm A, unlearning algorithm U, number of shadow models T', example (I, y). logit function é, function that returns probabilities f(, given model parameters 0.
Observations: O + U Ó -
while & < T do
D + sample dataset that includes (x,, v)
80 + A(D) train model
0' < (00, (x., y)) unlearn (I. y)
8" < A(D \. (I, v)) retrain without (z, y)
O(t) < (xf(x;;))
Ôlt] + o(f(2; ("))
end while
,1, fit Gaussian O)
P. Ō. fit Gaussian Ô)
(1 0*)) o
Pueember + o(
Pmemmee then
return Predict (æ, y) is member of training
else
return Predict (z, y) is not member of training
In the original U-LiRA paper (Hayes et al., 2024), they report results for Efficient U-LiRA for N= 256, forgettable points F all points of class 5, ny 40 random forget sets per base model, and each forget set m = 20. The N base models that they are train are trained on ResNet- 18 for 100 epochs, and highly overparameterized.
28

---

Published conference paper at ICLR 2025
Algorithm F.3 Sub algorithm: Membership Prediction
1: Input: Sets A, B of real-valued numbers, and point E R.
2: (ji, a <- fit Gaussian( A)
3: (f, fit Gaussian B)
N(zpp 4: Pinember + Ma.u.a")+
5: if Pmember > then
6: return Predict (z, y) is member of set A
7:
else
8:
return Predict (I., y) is not member of set A
9:
end if'
Algorithm F,4 Efficient-ULLRA
1: Input Number of base models N, set of forgettable points F (default: all points of class 5), Number of random forget sets per base model n, size of each forget set m (default 200)
2: Train N base models random 50% subsets of the dataset
3: for each base model 0; do
4: construct n random forget sets of size m, denoted Ft.j.
5: for each random forget set Fij do
6: Unlearn forget set Fij
7: end for
8: end for
9: Split the ny N unlearned models into two sets, Shadow models S and Target models T
10: initialize accuracy vector ä R(T), with all O's.
11: for each target model o E T do
12: Construct D, from from the m points that 0g unlearned
13: Construct D, from m from the m points that O, was not trained on.
let D D D.,,
15: Let c
for each point
D do
17:
Let SA be the set of shadow models that were trained on Let SB be the set of shadow models that unlearned x E SB)
19:
Construct sets A = (0'(x)) E SA). B =
20:
Run sub-algorithm Membership Prediction F.3 with inputs (A, 2), returning / {1,0)
21:
if then/ and Dy) OR (1 0 and E D,)
22:
c+
23:
end if
24:
25:
end for
26:
Average the model accuracy across all predictions in D, or = c/(2m)
end for
28:
Average the accuracy-per-mode over all the target models Return mean (α)
29

---

Published conference paper at ICLR 2025
For our evaluation, U-LiRA paper (Hayes al., 2024), we run Efficient U-LiRA for N 50, n, 40 random forget sets per base model, and then we vary the training setting, the forget size nt, and total set of forgettable points F. Specifically, we try settings
1. ResNet-18 trained for 100 epochs, evaluated on forget sets of size 200, with the forgettable points F being 1000 points in class 5.
2. ResNet-9 trained for 25 epochs, evaluated on forget sets of size 200, with the forgettable points /' being 1000 points in class
3. ResNet-9 trained for 25 epochs, evaluated on forget sets of size 50, with the forgettable points F being 500 random points in the dataset.
F.3 COMPARING D-LIRA TO KLOM
In this paper we propose a new method for evaluating unlearning, KLOM, Here, we argue that this is a superior measure existing measures, in particular compared U- LiRA. The advantages of KLOM are:
1. KLoM requires fewer unlearning trials (on the order of 100) than D-LiRA (which is generally on the order of 2000).
2. KLoM returns distribution of differences, rather than binary assignment if one particular model was more like an unlearned model or retrained model. This is valuable because it tells you how a method unlearns individual points (c.g. is bad on average, or just bag on specific points)
3. XLcM does not assume the margins can be fit well by Gaussian. Anecdotally, for U- U-LiRA, we find this is a decent but not great assumption, and it's currently unclear how much error this really introduces.
4. KLcM has the capacity to look at unlearning algorithm's is ability to handle coherent sets of points, not just random subsets of some set forgettable points.
5. U LiRA does not capture closeness to unlearned model, and thus one can force U-LiRa score to go down (implying better unlearning) by having the unlearning method destroy the original model, thus U-LiRA scores must be traded-off against an accuracy drop. KLOM measures distance directly, and thus unlearning can be evaluated with single measure. We expand on this point below. And is illustrated by figure F.2.
A Toy Example Where U-LiRA Fails:
Consider your unlearning method returns a constant function f (e.g. such that that the margin always some constant, e.g. 7). In such situation, the distribution of unlearned models will look radically different from the distribution of models that were fully retrained; in theory, good unlearning measure should return that this is a bad unlearning method. However, U-L. RA will actually return nearly perfect unlearning score (+= 50%). In U-LiRA, one does 2 sets of likelihood ratio tests, first on points the unlearned model unlearned, then on points the unlearned model never saw. The first set of likelihood ratio tests, D-LiRA will get 100% (or nearly). because margin is constant (7), and so it will be at the unlearned -models peak; thus we get 100% accuracy on these points. Now, on set 2, U-LiRA will get 0% (or nearly), because U-Li LiRA compute the likelihood ratio at the margin of the unlearned model's prediction, which in this case a constant (7), thus it will still be at the unlearned-modes peak. Thus, U-LiRA will not predict that anything is "mot-in-the-training-ee, achieving 0% on this set.
However, the problem is that 100 +0 /2 50%, which appears to perfect unlearning score, but in reality is just a classifier that thinks everything is from an unlearned model.
Advantages of U-LiRA:
1. It is worth noting that our measure requires binning, and some assumptions there. U-LiRA does not (because it makes the Gaussian approximation assumption)
30

---

Published conference paper at ICLR 2025
ULIRA score vs Validation accuracy for Gradient-Ascent
Validation accuracy
LR = 0.001
LR 0.0005
65
LR 0.000125
LR 2.5e-05
LR 5e-06
2.5e-06
LR 5e-07
LR 2.5e-08
0.50
0.52
0.54
0.56
0.58
0.60
ULIRA score
Figure F.2: U-LiRA accuracy vs Validation accuracy of the unlearned model, for Gradient Ascent method, for model trained CIFAR-IO. Unlearning occurs on random forget sets of size 200 in class 5. Observe that it is possible to achieve nearly perfect U-LiRA accuracy (50%) by simply dropping the validation accuracy of the model by 20%. With Gradient Ascent specifically, this is achieved by increasing the learning rate beyond the optimal learning rate, causing the gradient ascent updates to be too significant.
ULIRA scores by method and forget set
DataModel Direct SUBUU
DataMode) Matchina
15
Geadbent Accent
Seaduent
ULJRA ancuracy (60
89
55
oabees desss
100
valnet olang
200
enbons clats
slo
Fanged
Pooget Bot
Penget Sod
uatons
Forget Set group
Figure F.3: Results for Efficient-ULIRA run with parameters specified in F2. The validation
accuracies are presented above the bar for the each method-forget set pairing. Observe that Gradient Ascent method is able achieve an excellent U-LiRA score, but does so the cost of the validation accuracy of the unlearned model.
2. U-LiRA reports an accuracy for particular model, and then averages that across multiple unlearning models. this correctly captures individual model performance, rather than aggregate unlearning algorithm performance.
F.4
SENSITIVITY OF UNLEARNING TO MODELS AND FORGET SETS
See Figure F.3.
31

---

Published conference paper at ICLR 2025
G UNDERSTANDING EFFECTIVENESS OF DATAMODEL MATCHING
We saw that datamodel matching is effective and efficient algorithm for unlearning. Here, we aim to better understand the effectiveness of datamodel matching (DMM), Since DMM consists of i) oracle matching (the finetuning algorithm) and ii) datamodels (approximation to oracle outputs), we study each component separately. First, in Appendix G.I, we analyze the stability of OM across time and to different choices of hyperparameters and show:
We show that once OM unlearns an example, the example generally stays unlearned after further iterations. addressing the original "missing targets problem." As a result, OM is also much more stable than prior methods with respect to the choice of optimization hyperparameters.
OM is stable across time:
OM generalizes from small sample: Though OM introduces additional design parameters (sampling ratios for forget and retain sets), we find that OM is effective as long as we include sufficiently large sample of both. In particular, we only need sample a small fraction of the retain set, making OM efficient.
Next, in Appendix G.2, we ablate different components the datamodel estimators to better understand necessary ingredients for DMM and show:
Necessity of modeling interactions between datapoints: Datamodels (linearly) model the effect of different training examples on other inputs. We show that using only the "diagonal" entries (i.e., modeling only the self-influence) is much less effective.
We show that replacing regression-estimated datamodels with much faster alternatives like TRAK still yield effective unlearning algorithms, albeit with worse performance than well-estimated datamodels.
Effectivvness of fast approximate data attribution methods:
G.1 UNLEARNING STABILITY OF OM
To motivate our approach, we demonstrated earlier that existing fine-tuning approaches suffer from the problem of different unlearning rates due to lacking meaningful targets to converge to. In Figure G.I, we find that OM no longer suffers from the same problem, since unlearning quality generally only improves over time (there is risk of overshooting), even if points still unlearned at different rates. Because of this, we find that OM is much more robust to the choice optimization parameters such learning rate and number of epochs compared to prior gradient ascent based methods (see Appendix H.1).
SCRUB
Orccle Matching
50
writin omci auterbotte
grobablity ooaaggin
60
40
30
30
10
10
Epoch
Figure G.I: Oracle matching circumvents the stopping time problem. We revisit the earlier plot and apply the same analysis to oracle matching. The red lines highlight examples in the forget set whose unlearning quality is hurt by training longer. This happens frequently when running SCRUB, but goes away nearly entirely when using oracle matching.
Generalization of OM. OM fine-tunes on samples from both the forget and retain sets. The efficiency of OM hinges whether it can generalize from small sample. Ablations (Appendix G.1) show i) OM succeeds as long as the ratio of forget set points in the fine-tuning set is sufficiently high, and ii) small fraction (2 0.04) of retain set suffices guide OM converge towards oracle most
32

---

Published conference paper at ICLR 2025
retain set samples. That is, OM is able effectively generalize from a small sample of oracle outputs. This implies that we only need to approximate oracle predictions on small fraction of the training data, increasing the efficiency of the OM algorithm.
meeai
forget set
retain set
Val Set
5.0
petain radio
5:01
4.5
5.04
3.0
WI. 044 (0002) pa wotE of R100
2.0
2.5
3.5
3.0
2.0
1.5
30
0.5
9.05 OUTS 17 198
1.0
0.10
0.07
3:10
5,03 re-tralaing)
0.05
Figure G.3: Varying the Figure G.2: Varying the fraction of retain set sampled for oracle match- tio of forget set samples in ing. A sufficiently large sample (2 0.04) appears to be sufficient in the fine-tuning set for oracle enabling OM to generalize to out-of-sample.
matching.
Challenge of overfitting.
We hypothesize that OM struggles the retain set of Living-17 17 due models being more overfit. further investigation showed the lack of use of data augmentation as the main cause of overfit- ting. Under hyperparameter settings that are identical except the of standard image data augmentation (random cropping and flips), the trained models overfit much less. In this new setting, re-trained oracle models and applied oracle matching with the same exact hyperparameters as before (so they are not optimized for the new setup). The resulting KLoM scores on the retain set are significantly lower (95th percentile decreasing from 2.88 to 0.62; see Appendix G.1), supporting our hypothesis that significant overfitting caused OM to perform worse on the retain set on Living-17.
2.00
original (ao DAJ (trained DA
1.75
density
1.25
1.00
0.50
0.25
3
set)
Figure G.4: Oracle matching struggles more on overfit predictions. We contrast the performance of oracle matching on the train set in two different hyperparameters settings, differing only in their use of data augmentation (DA). OM struggles much more on models that are overfit when data augmentation is turned off.
G.2 DATAMOdEL ABLATIONS
Given the stability of OM, the success of DMM essentially only depends on the fidelity of datamodel approximation to oracle outputs. We now study which components of the datamodel are in fact necessary.
'We had tumndd off data augmentation for all of our experiments as this was done all major prior works on (empirical) unlcamiing for DNNs.
33

---

Published conference paper at ICLR 2025
Necessity of modeling interactions between datapoints. Datamodels model the effect of different training examples given model output. By leveraging them, we were able to accurately simulate the oracle model outputs. Inspecting the weights of linear datamodels show that the dominant entry for the datamodel of training input corresponding the example itself (i.c., excluding that training example has the largest negative effect on the model prediction on itself). The corresponding weight is what is also known the memorization score in prior work Feldman (2021). Could memorization scores suffice to linearly model oracle outputs? In Figure G.6, we evaluate the quality of oracle predictions when using the full datamodel vector only the memorization scores, and find the following:
Using only the diagonal entries hurts unlearning quality for non-random forget sets (5), particularly for examples in the tail (dotted line). Intuitively, this is because the other weights in datamodels (the "non-diagonal" entries) capture important cross-example correlations (e.g., similar examples should have reinforcing effect on one another). Moreover, globally scaling the memorization scores (orange lines) cannot account for the missing non-diagonal entries. On the other hand, this is less important for random forget sets (3), as two random examples are in general unrelated to one another. Hence, to effectively unlearn forget sets that arise in practice via our approach, it seems necessary to model interactions between different datapoints.
Insufficiency of memorization scores for unlearning non-random forget sets:
Consistency of best scaling: As an artifact, we also find that scaling down the datamodel weights globally by a factor (=00.9 here) improves unlearning quality marginally. Fortunately, the scale seems consistent across different types of forget sets; one could calibrate this scale using "held-out" forget part of pre-computation stage, and subsequently apply to all forget sets.
forget set 3
forget set 5
Diagonal only
3.5
False
3.0
True
2.0
2.5
KLoM
1.5
2.0
1.5
1.0
1.0
0.5
0.5
0.6
0.8
1.0
1.2
1.4
0.8
1.2
multiplier
multiplier
Figure G.5: The effect of non-diagonal entries and re-scaling on the unlearning effectiveness of DM-DIRECT for two different types of forget set CIFAR-10 (left is random; right is non-random). Solid and dotted lines correspond to the mean and 95%-perceetile KLOM scores. Diagonal-only indicates that we only the memorization scores (the "diagonal" of the datamodel matrix).
Scaling with estimation cost. Though we excluded the cost of estimating datamodels in our analysis in Section 4.4 (as it is one-time cost), practically we need to account for them as estimating predictive datamodels is computationally expensive. But estimating them is not all or nothing: we can tradeoff the computational cost and the datamodel predictiveness by varying the number of re-trained models. Here, we investigate how varying the computational resources affects both datamodel predictiveness (LDS) and unlearning performance (as measured by KLoM), In Figure G.6, we show the result of varying the computational cost by orders of magnitude: we can observe that while the datamodel predictiveness (as measured by the linear datamodeling score (Park et al., 2023)) continues increase at the same rate, KLOM KLoM-averaged averaged across various forget sets begins to saturate.
We hypothesize that this is due to the following difference in the distribution of counterfactual subsets being evaluated: while achieving high LDS requires predicting model outputs on the same distribution of random subsets of the training data that the datamodels trained on, achieving high KL.MM
34

---

Published conference paper at ICLR 2025
0.5
KLoM
0.8
0.4
LDS
0.3
0.7
0.2
10a
10* datamodel estimation cost
10a
10*
datamodel estimation cost (# re-trained models)
re-trained models)
Figure G.6: The effect of estimation cost on unlearning performance and datamodel predictive- ness. On CIFAR-10, we show how unlearning performance DM- -DTRRCCT (measured by KLOM; lower is better) and datamodel predictiveness (measured by the linear datamodeling score; higher is better) scales with datamodel estimation cost (number of re-trained models, in {10s, 10 2 x 10 x 10*)). KLoM is averaged over different forget sets.
SCRUD
Ratroo
Grada
Din (TRAK)
Perpet
Wetaat
Validatioo
CEPARLO
3.2
CLPARO
Time Itraction of full zo co-training; ++)
Figure G.7: Datamodel-Matching with more efficient estimators. In the same up as in Figure 1, we evaluate the effectivness of DM-DIRECT and DMM when a different, more efficient estimator (TRAK) for datamodels. Though the equality of unlearning degrades, our algorithms still outperform prior methods. Note that the computational savings from using TRAK is not reflected on the x-axis, as computation of datamodels considered separately from the fine-tuning cost of DMM.
scores requires predicting over small non-random forget sets. practice, this suggests that for the purposes of unlearning, cheaper alternatives (either by using the same cerression-based estimator with reduced computational resources or by using a different estimator) may perform nearly as well as computationally expensive methods.
Efficient unlearning with TRAK. While datamodels estimated using the regression approach of Ilyas et al. (2022) are predictive, and can be pre-computed prior to unlearning, they nonetheless are expensive to compute. Since the work of Ilyas et al. (2022), follow-up works (Park et al., 2023; Grosse et al., 2023) have shown that efficient alternative methods can be quite effective with substantially lower computational costs.
Here we investigate whether DMM is still effective when datamodels estimated with TRAK, which is based on a particular approximation to the influence function. In Figure G.7 we run OM with predictions generated by TRAK estimators with x1000 less compute than the regression-based datamodels. As expected DMM with TRAK performs worse in terms of KLoM than when datamodels are used, but we find that this drastically cheaper alternative to DMM still outperforms all prior methods significantly. These results highlight that improving the accuracy of TRAK in order to close the gap in KLoM scores with datamodels represents an important direction for developing even more efficient and effective unlearning algorithms.
35

---

Published conference paper at ICLR 2025
H ADDITIONAL RESULTS
H.1 HYPERPARAMETER SENSITIVITY OF UNLEARNING ALGORITHMS
Methods that involve something akin to gradient ascent, like SCRUB, where unlearning for longer or with larger learning rate can reduce the utility of the model; as opposed to gradient descent based methods, like Oracle Matching, where if the learning rate is sufficiently small, unlearning for longer does not hurt the model. We illustrate this by showing how much the same unlearning algorithm affected by changing the learning rate, in Figure H.1, where we plot the 85th percentile of KL.MM score as function of learning rate".
SCRUB 85.0 Percentile of KL.O scores for CIFAR10
Forget Set
Retain Set
Valldation Set
B5th Perrantii of k1 KINM srsive
Kostarzation Epocts
10
Epocto
mitte Epochs
8
Musim sution Epodls -7
Mesimaattive tpncls
10
10-2
Learning Rabe
Learning Rate
Leasuing Rale
Oracle Matching 85.0
KLOM scores CIAARIO
Forget Set
Relain Set
Validation Sct
83th Percartile tiln of XT.CM enores
Eppci
Epocis
Epocas
Epoxis
Tporit
13-1 Learning Ralo
Learning
Rabe
Loarning Rate
Figure H.1: KLOM sensitivity to learning rate. SCRUB is trained for 10 epochs, with the first "Maximization Epochs" used for Gradient Ascent; Oracle Matching trained for 'Epochs', both demarcated in the legend. Both algorithms are evaluated on Forget 5, which non-random forget set of size 100. The red lines denotes the learning rate at which the KLOM score drops below 6 (an arbitrarily chosen threshold which we deemed as the largest value approaching a "reasonable" unlearning). Left red line indicates the largest forget that achieves reasonable unlearning for Forget points, and the right red line indicates the smallest learning rate that achieves reasonable unlearning for Validation and Retain points. The line is darker that subset is limiting factor for the thresholding.
The key takeaway is that the range of learning rates for SCRUB is much smaller (less than an order of magnitude), while Oracle Matching only performs significantly better, the range of learning rates that attain good KLOM scores is much larger dynamic range. We do note that because this a log- scale, the range for the SCRUB learning rates larger magnitude: however, the critical observation is how flat the KLOM scores are as a function of learning rate and the relative ranges of learning rates. Flatter and wider ranges (even on log-scale) make hyperparameter tuning dramatically simpler and significantly more likely to choose learning rate in a good range.
"We choose the 85th percentile for KLOM scores, because SCRUB generally performs significantly worse than Oracle Matching, and we found that for higher percentiles, the effect was weaker because SCRUB never achieved particularly good KL.OM scores.
36

---

Published conference paper at ICLR 2025
Oracle Matching
Retain
Validation
Brubaktiiy saagln
00-
30
10
Epoch
Epoch
Spoch
Datamodels Matching
Retalin
Validation
Prodabilty of
50
16
Epach
Sporh
Figure H.2: Plotting unlearning quality over time for Oracle Matching and Datamodels matching. We observe that different points unlearn at different rates. However, unlike for gradient ascent based methods like SCRUB, for gradient descent based methods like Datamodels matching and oracle matching, one data point is unlearned, it tends to remain unlearned. The red lines highlight examples whose final quality of unlearning is more than 10% worse than their maximum unlearning quality.
H.2 PER-SAMPLE UNLEARNING OVER TIME
We present the rate of unlearning individual data points function of epochs in the unlearning algorithm for both Oracle Matching and Data Models matching, which we contrast with SCRUB unlearning, presented in Figure 2.
See Figure H.2.
37

---

Published conference paper at ICLR 2025
H.3 FULL KLcM EVALUATION
Building on this point that the effectiveness of different methods is forget set specific, we now share all the KLoM scores for the different methods, below in Figures H.3 and H.4.
Average
Forget
Retain
Validation
Forget Set (c) Forget Set 8 (+) Forget Set (+) Forget Set (+) Forget Set 5 (+)) Forget Set 4 (+) Forget Set 3 (+)) Forget Set (+)) Forget Set (+)
10
1.0
0.0
1.0
10
BB
10
X
X
0.5
1.0
1.0
0.5
1.0
CA
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.5
1.0
Do Nothing
10
KlaM
Oracle
1
DM- Jtrect
2MMMatching
DM Matching (TRAK)
0.5
1.0
0.0
0.5
1.0
0.0
1.0
0.0
0.5
1.0
10
10
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
5*
0.5
1.0
0.0
0.5
1.0
0.0
1.0
0.5
1.0
Time (fraction of re-training: +-)
Figure H.3: KLOM results for all forget sets 1-9 on CIFAR-10. The pareto frontier for each method in line plot, but each KLoM data point for each method is plotted.
38

---

Published conference paper at ICLR 2025
Average
Forget
Retain
Validation
Forget Set 4 (c) Forget Set: 1 (-)
10
X
GD
0.0
0.5
1,0
0.5
1.0
0.0
0.5
1,0
0.5
1.0
SCRUB
Do Nothing
10
Oracle
KLoM
DM-Direct
DM-Matchhing
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Forget Set (())
460
1.0
Time (fraction of full re-training: +)
Figure H.4: KLoM results for all forget sets 1-3 on Living-17. 17. The pareto frontier for each method is line plot, but each KLoM data point for each method is plotted.
Observe that Gradient Descent tends to perform very well for the retain and validation sets, but leaves the forget set relatively unchanged. This is parametrizable through hyperparameters like weight-decay, but not explored in this plot.
H.4 MODEL ACCURACY AFTER UNLEARNING
For measures of unlearning it is possible to do well the machine unlearning measure-of- success, while at the same time doing completely terribly on the target task, resulting in terrible generalization and large validation error. We that our measure of success, KLoM, does suffer from this problem, as a machine unlearning algorithm is measured on its ability to match the margins of retrained model, which is assumed to do well general. However, for completeness, a table of the model accuracies for each unlearning methods, evaluated for the method that achieves the lowest KLOM 99th perh-percentile score on the forget set.
include
Index
GA
GD
Scrub
Retrain an Oracle
DM-Direct
DM-Matching
88.34
88.44 14.44
88.29
88.48
89.97
89,90
2
88.48
88.49
88.36
88.51
89.98
89.70
88.25
88.48
87.55
88,25
89.96
89.61
4
87.85
88.44
88.26
88.53
89.95
89.46
88.07
88.48
81.99
88.51
89.93
89.86
6
84.20
88.47
85.65
88.42
89.86
89.47
87.98
88.44
88.26
88,49
89.98
89.88
8
88.30
88.49
81.62
88.43
90.03
89.93
9
10.92
88.48
85.36
88.46
89.99
89.89
Table H.l: Model Accuracy Results
We note that the pareto optimality curve is computed separately for each forget This is because because we observe that unlearning is quite model-specific and forget-specific; as such, it's reasonable of hyperparameters for each unlearning depending
that a practitioner should have different on the forget set. Thus, having the pareto- frontier be specified per-forget-se set gives each unlearning method the best opportunity perform in that setting.
pareto-frontier
39


Reviews:
[{"review_id": "r4NWsgxXiP", "reviewer": "Reviewer_Y44J", "summary": "The paper addresses the problem of _machine unlearning_ (removing the effect of a few training data points \"forget set\" on the model's outputs) with by reducing it to the problem of _data attribution_ (predicting the effect the training set on the model's outputs). With this, the paper proposes a meta-algorithm Datamodel Matching (DMM) that gets predictions from data attribution on all-but-forget set and finetunes the model to match the predictions. A new unlearning metric KL Divergence on Metrics (KLoM) is also introduced. Finally, the paper presents experiments on unlearning in image classification tasks, showing that DMM is better at unlearning and faster than naive-retraining on the all-but-forget-set.", "questions": "# High-level questions\n1. Definition 3. Why is KLoM called KL-divergence of Margins? I couldn't find the reasoning.\n2. Line 321 and Alg A.1. Assuming that dataset $S$ has distinct datapoints, isn't $S_{finetune}$ the same as $S$, implying that Alg A.1 is simply matching the model's outputs to the oracle? Then I don't understand the novelty of Oracle Matching.\n3. Line 364. Why replace the first term with $\\beta$? Linear $\\beta$ is exactly the definition of the estimator $\\hat{f}$, which is only an approximation to $f_x$. It'd make sense to explicitly state that DM-DIRECT approximately simulates the oracle outputs. You could then argue that even this approximate simulator works well empirically.\n\n# Low-level questions\n1. Line 173. Is this estimator/datamodel only for a single $x$? Does this mean that distinct inputs might require distinct datamodels?\n2. Equation 2. What is the approximation in? Is it in some measure of distributions?\n3. Figures. Why are there multiple points on the plot for each legend entry?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is written extremely well, and has a natural flow to it. When reading I thought of many questions and added annotations, only to find them answered in the next paragraph or section. E.g. the authors introduce Oracle Matching with the strong assumption of oracle access to data attributor $f^{oracle}$ (Section 4.2), and immediately discuss how to simulate such an oracle without such an access (Section 4.3). In Section 5 as well, the paper attends to a natural question readers could have: is oracle matching useful when the problem is easy to solve with gradient descent. This is good writing, and I appreciate the authors' efforts in putting themselves in the readers' shoes.\n\nIn sum, the Oracle Matching and Simulation methods are intuitive yet thoroughly tested on image classification tasks. These methods are original as well, and it is surprising to me that linear datamodels work so well empirically. I'd like to see this paper accepted, and the research directions it inspires.", "weaknesses": "It is unclear that linear datamodels extend to other kinds of tasks, e.g. language modeling or regression problems. I believe this to be a major weakness of the paper. While linear datamodels lead to simple algorithms in this paper, the previous work [1] does not have a good argument for why linear datamodels work [1; Section 7.2]---in fact Figure 6 of [1] display imperfect matching using linear datamodels. It'd be useful to mention this limitation in this manuscript as well, and discuss the limitation's impact to machine learning.\n\n# Suggestions:\n1. Line 156. It'd be useful to the reader to add a citation on differential privacy, e.g. one of the standard works like [2].\n2. Line 176. $\\hat{f}$ should have output range in $\\mathbb{R}^k$ since the range of $f_x$ is in $\\mathbb{R}^k$. \n3. Line 182. \"show\" -> \"empirically show\".\n4. Definition 3. Write safe, $S_F$, and input $x$ explicitly in KLoM, otherwise KLoM$(\\mathcal{U})$ looks like KLoM of the unlearning function across _all_ safe functions and inputs. I'm curious why the authors wrote KLoM$(\\mathcal{U})$.\n5. Add a Limitations section.\n\n[1] Ilyas, A., Park, S. M., Engstrom, L., Leclerc, G., & Madry, A. (2022). Datamodels: Predicting predictions from training data. arXiv preprint arXiv:2202.00622.\n[2] Dwork, C., & Roth, A. (2014). The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4), 211-407.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "CqRQxwfLh5", "reviewer": "Reviewer_Bnzy", "summary": "This paper introduces a new Unlearning algorithm called Datamodel Matching (DMM) to unlearn a forget set by fine-tuning a model that has been pre-trained on a larger dataset including the forget and retain set. They use predictive data attribution to approximate the oracle model---the one that is retrained from scratch on the retain set and hence has not seen the forget set at all. Predictive data attribution learns datamodels for each input x to simulate how a model trained on the retain set would behave on x. With this approximation, DMM then applies Oracle Matching to align the model's output distribution with that of the oracle. They introduce KLoM for measuring the unlearning quality and show empirically that their algorithm outperforms previous gradient-based algorithms, achieving a lower KLoM and quickly approaching oracle-level accuracy with only a fraction of the retraining time.", "questions": "1. This question is regarding the GD baseline. Given a model $\\theta_{full}=A(S)$ trained on a full dataset S (including the retain set $S_R$), GD minimizes the loss on the retain set using gradient descent, starting from $\\theta_{full}$. Since $S_R$ was already in the dataset S that the model was trained on, this essentially involves further training on $S_R$, which could lead to overfitting without effectively forgetting $S_F$. This may explain why, in Figure 3, GD performs similarly to 'Do Nothing' and, on average, even worse. My interpretation is that further training on $S_R$ may not significantly alter a model that was sufficiently trained on S if the loss is strongly convex and could lead to overfitting (and hence degrading performance on the validation) in more complex landscapes. Could the authors clarify if there’s any specific benefit of GD for unlearning that I might be overlooking?\n\n2. The authors mention the possibility of having duplicates across the forget and retain sets on page 6 when discussing the drawbacks of Gradient Ascent. Given that $S_F$ and $S_R$ are sets and $S_R$ is defined as $S \\backslash S_F$, I don't see how this duplication is possible. Could the authors clarify this?\n\n3. Could the authors provide more interpretation of the results in Figure 2? How do you interpret the changes and fluctuations in the red and gray lines?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow.\n\n2. It provides a solid introduction to Unlearning, offering a detailed overview of related work, recent advancements, and existing challenges. The motivation is well-described, and the flow effectively positions this paper within the broader field, helping readers understand its scope and contributions better. The use of data attribution to approximate the Oracle model is particularly compelling.", "weaknesses": "1. The experimental results, while supportive of the algorithm’s effectiveness, are somewhat limited in scope. The analysis focuses primarily on CIFAR-10 and an ImageNet subset (Living-17), with figures 1 and 3 illustrating outcomes only on these datasets. Expanding the experiments to include additional datasets would enhance the generalizability of the findings. On the Retain set, Oracle Matching gets close to the Oracle in CIFAR-10 but this is not the case with Living-17 which means that while the algorithm can reduce KLoM on the forget set, it does not work as well on the retain set. More discussion on this observation can improve the understanding of the algorithm’s limitations, and I'm interested to know how this observation extends to other tasks.\n\n2. The paper could benefit from clearer explanations and interpretations of the figures and baselines. The discussion around interpreting each figure is limited. Additionally, some of the baseline methods are not well-defined; for instance, SCRUB is introduced without a description, and GD (Gradient Descent) is not explained well until page 9 (also see my question on GD in the Questions).\n\n3. Minor typo: The RHS of equation (2) should be dependent on x.\n\n4. Calculating one $\\beta$ vector for each x in the dataset appears computationally intensive. Although the authors mention that this is a one-time process that amortizes over unlearning requests, further discussion on its computational cost relative to the unlearning phase would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "bl9RFQdA5C", "reviewer": "Reviewer_JhM3", "summary": "This paper introduces the concept of Oracle Matching to significantly reduce the time complexity of unlearning processes, achieving this in a fraction of the time required for traditional retraining or fine-tuning while maintaining model performance as close as possible to that of full retraining. The authors utilize the concept of \"DataModels\" to efficiently approximate a proxy for the oracle, leveraging this proxy within the Oracle Matching framework.", "questions": "line 246 - specify $\\text{safe}(S_F)$ - how do you know this safe(S_F)? How did you calculate this? \n\npage 6 - line 317 - this description is clear but what exactly distinguishes your approach from distillation. The comparison between your method and a distillation unlearning approach such as [Efficient Two-stage Model Retraining for Machine Unlearning](https://openaccess.thecvf.com/content/CVPR2022W/HCIS/papers/Kim_Efficient_Two-Stage_Model_Retraining_for_Machine_Unlearning_CVPRW_2022_paper.pdf)\n\nFigure 3 - For this evaluation, did you retrain the model and then computed the unlearned model using oracle matching?\n\nline 365: in this formulation, to create the datamodels for remaining data, you used the datamodel of whole dataset minus the datamodel of forget set. if my understanding is correct, doesn't it add the additional computation because you need to estimate two datamodels first. \nalso can you prove this formulation result in an exact or good estimation of datamodel for remaining data? \n\nline 374: the true oracle output - I am just worried about the closeness of the proxy to actual retain datamodel to the.\n\nline 404 - , the datamodel generalizes well to new forget sets in practice. very interesting how do you demonstrate this ?\n\nORACLE MATCHING FOR LINEAR MODELS: my understanding  is that the quality of unlearning for the oracle matching heavily is influenced by the unlearning quality of approximated oracle model . it would be interesting to investigate the influence of that model.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed approach is both innovative and highly impactful, offering substantial reductions in unlearning time. The authors demonstrate a profound understanding of unlearning methods based on gradient descent and fine-tuning. They delve into the challenges of these methods, particularly examining their impact on the model's performance after unlearning. Although gradient-based approaches are among the most effective unlearning methods, they often degrade the predictive performance of the model considerably—a drawback that the authors have thoroughly investigated and discussed.\n\nThe concept of Oracle Matching, combined with the use of DataModels, greatly reduces time complexity. This approach shows considerable promise for improving the efficiency of unlearning processes without compromising model performance.", "weaknesses": "Grammatical errors:\n- Abstract - line 2\n- The abstract and introduction was written in rush. please \n\n\nEarly introduction of specific notions:\n- such as $S$, $S_R$ in the beginning of the paper without providing the backgrounds and clearly stating them, confuses the reader. (Intro - second paragraph)\n- line 74 - trained model $\\theta$\n\nAmbiguity:\n- line 49 - Simple models // what is considered to be a simple model?\n- line 59 - variety of empirical evaluations and benchmarks // what are these benchmarks? either needs to mention at least one of evaluation criteria, or rephrase the sentence.\n\nIncorrect Statement:\n- line 63 - , fine-tuning-based methods typically employ.... - incorrect, the simple fine tuning only focus on the remaining datapoints and fine tune the model on $S_R$. If there is a paper that conducts the fine tuning in the way you mentioned in this line, you need to point it out, but otherwise, check this paper [\"Model Sparsity Can Simplify Machine Unlearning\"](https://openreview.net/pdf?id=0jZH883i34)\n\nIncorrect notation:\n- line 152 - the notation for approximate unlearning is the same as exact unlearning.\n\nline 83 - Empirically, we find that .... - I was expecting to see a comparison between your method and unlearning distillation approach, but you didn't made that comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)