# Evaluating Inexact Unlearning Requires Revisiting Forgetting

Shashwat Goel Ameya Prabhu* Ponnurangam Kumaraguru
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Code: https://github.com/shash42/Evaluating-Inexact-Unlearning Equal
Contribution

###### Abstract

Existing methods in inexact unlearning are evaluated by measuring
indistinguishability from models retrained after removing the deletion set. We
argue that achieving indistinguishability is unnecessary and its practical
relaxations are insufficient. We formulate the goal of unlearning as
forgetting all information specific to the deletion set while maintaining high
utility and resource efficiency.

We introduce a novel test for forgetting called Interclass Confusion (IC).
Despite being a black-box test, IC can investigate whether information from
the deletion set was erased until the early layers of the network. We analyze
two aspects of forgetting: (i) memorization and (ii) property generalization.
We empirically show that two simple unlearning methods, exact-unlearning and
catastrophic-forgetting the final $k$ layers of a network, outperforms prior
unlearning methods when scaled to large deletion sets. Overall, we believe our
formulation and the IC test will guide the design of better unlearning
algorithms.

##  1 Introduction

There have been growing concerns about the ethics of data use for designing
machine learning systems, with primary considerations being privacy [46] and
harmful data [22]. Privacy protections come forth with legislation like GDPR
[20], CCPA [2], and PIPEDA [4]. These policies require organizations to allow
users to delete their data from all systems, including learnt models [23, 3,
28] which can leak information about user data [60, 16]. Similarly, there is a
need to tackle problems in datasets ranging from random noisy labels [25, 53,
52] to systematic biases111to the extent that bias is a dataset problem [39].
[55], besides adversarial subsets such as poisoned data [10, 19, 72].

Removing the influence of the sensitive data points from trained models is a
reliable approach to tackle a wide range of harms due to data, from user
privacy requests to systematic biases. The domain of _machine unlearning_ [15,
28, 12] targets this data deletion problem. Formally, we are given a model $M$
trained on a dataset $D$ by a (potentially stochastic) training procedure $T$,
and any deletion set $D_{f}\subset D$222$D_{f}$ may not be i.i.d sampled from
$D$.. An unlearning procedure generates a model $M_{u}$ aiming to delete any
information present in $D_{f}$ but not in the retain set $D\setminus D_{f}$.
Our work is focused on _inexact_ unlearning, where information removal may be
imperfect or unproven.

Figure 1: Difference between the goals of indistinguishability and our
definition of forgetting highlighted, with each coloured square representing
information contributed by different sets of data. Prior work only defines
$M_{u^{\prime}}$ to have unlearnt. In contrast, we define unlearning as
removing all information gained from $D_{f}$ (in black) which is achieved by
both models $M_{u}$ and $M_{u^{\prime}}$.

As illustrated in Figure 1, most prior evaluations of inexact-unlearning
operationalize their goal as _model indistinguishability_ , i.e. producing a
model with a parameter [33, 27, 71, 43, 68] or output [11, 30, 31, 29, 51, 54]
distribution indistinguishable from one produced by retraining from scratch
using $T$ on $D\setminus D_{f}$ ($M_{u^{\prime}}$ and $M_{r}$ in Figure 1
respectively). We highlight important shortcomings of evaluations which rely
on model indistinguishability. We reformulate unlearning from achieving model
indistinguishability to having three orthogonal goals: _forgetting_ ,
_utility_ and _resource efficiency_ , with a focus on forgetting. Inexact-
unlearning methods should be on the pareto frontier of the trade-off among the
above three desiderata, while scaling to large deletion sets. Figure 1
illustrates the forgetting criteria, which considers any unlearning procedure
that has deleted information present in $D_{f}$ but not in $D\setminus D_{f}$
as having _forgotten_ perfectly.

Black-box evaluations can be enhanced using three strategies: (i) Manipulating
input data or labels, (ii) Strategic selection of the deletion set and (iii)
Computing measurement functions on the model’s output labels/probabilities. We
refer to the first two aspects together as designing a _test_ and the third
aspect as defining a _metric_. Inspired by the practical application of
removing mislabelled and biased data from models, we leverage label
manipulations to propose the Inter-class Confusion (IC) test for supervised
classification settings. The IC test induces confusion between two classes,
requiring the unlearning procedure to erase this confusion. By doing this, the
IC test enhances the gap between models which have unlearnt to varying
extents, serving as a richer attack to identify imperfect unlearning. The IC
reliably demonstrates whether the information was removed from even the early
layers of the network. In deep networks, we find simply performing unlearning
on the final linear layer [71, 41, 11] fails to remove most information.

Our forgetting-oriented framework allows us to analyze diverse phenomena.
First, we decompose forgetting into _memorization_ [7], when the metric is
computed for the models outputs on $D_{f}$, and _property generalization_
[49], when on unseen samples similar to $D_{f}$. Second, we empirically find
that catastrophically forgetting [26] from the final $k$ layers almost
entirely removes the information while having a significantly better trade-off
on time than retraining those layers. Third, we find that using some
regularization methods can make the original model $M$ more amenable to
unlearning. Thus, any comparison of unlearning efficacy must be attentive to
the optimization procedure used to obtain $M$.

Overall, we alleviate the shortcomings in the goal of model
indistinguishability, weak evaluation methods and small deletion sets in prior
work. Our contributions are:

  1. 1.

We propose a new formulation of inexact-unlearning, which focuses on
forgetting additional information contributed by the deletion set $D_{f}$.

  2. 2.

We study the setting of large deletion set sizes. We show the resource
efficiency of data-influence isolation, the prevalent strategy for exact-
unlearning, scales poorly as deletion sets grow.

  3. 3.

We propose the IC test which amplifies the difference in the information
present in the original dataset $D$ and retain set $D\setminus D_{f}$.

  4. 4.

We investigate how early in a deep network is sample-specific information
retained, the phenomenon of catastrophic-forgetting and possibilities for
optimizing the original model for amenability to unlearning.

##  2 Problem Formulation

We define unlearning as having three critical goals: _Forgetting_ , _Utility_
and _Resource Efficiency_. All notations are compiled in Appendix Table 7 for
reference.

Forgetting: Given _any_ subset of the data $D_{f}\subset D$, forgetting is
defined as removing the information $D_{f}$ contributes to the model which
cannot be obtained from $D\setminus D_{f}$.

Utility: A naive unlearning procedure is initializing a new random model,
which removes all information about $D_{f}$ thus satisfying the forgetting
criteria. However, all other information is lost alongside. Once unlearning
procedures delete $D_{f}$ satisfactorily, utility determines the value of the
model produced. Utility could include desirable properties like robustness
[63] and out-of-distribution generalization [38], but in this work we focus on
test accuracy.

Resource Efficiency: Consider another naive unlearning procedure which trains
a new _retrained_ model $M_{r}$ from scratch on $D\setminus D_{f}$ with the
same training procedure $T$. This procedure satisfies forgetting by never
using $D_{f}$ and typically has high utility.333Not necessarily the maximum
utility possible. However, retraining from scratch is computationally
inefficient. Any proposed unlearning procedure must be significantly more
resource-efficient than retraining to be valuable, primarily in terms of the
time required to unlearn.

A unifying definition that formalizes forgetting and captures utility and
resource efficiency is an open problem. Our paper further focuses on inexact-
unlearning and scalability to large deletion sets, which we describe below.

Inexact-unlearning: Provably perfect forgetting with good utility and resource
efficiency can often be hard to achieve, especially in deep networks. Hence,
inexact-unlearning literature has relaxed the forgetting goal in two ways:
imperfect [33, 71, 68] and not not provable [37, 41, 11, 59, 70, 34, 47].
Imperfectness relaxes the forgetting requirement for unlearning methods in
order to achieve better utility or compute-efficiency, implying that models
should try to remove _most_ information specific to the deletion set. The
degree of forgetting can either be measured using empirical tests or
approximate guarantees. Relaxing provability implies unlearning methods do not
provide any guarantees of information removal. Our work focuses on empirically
measuring the amount of forgetting produced by imperfect unlearning methods.

Scalability to large deletion sets: Popular unlearning methods, both exact and
inexact, either explicitly assume tiny deletion sets [64, 12, 71] or scale
poorly beyond them in practice [56, 32, 30, 31]. However, many real-world
scenarios require the removal of a large number of samples. Examples include
removing noisy labels [53, 52], deleting poisoned samples [69, 42, 45],
deleting data that induces harmful biases [55, 22], and organizations
requiring deletion of user data older than some retention period. Even in the
context of privacy, a single user might _own_ multiple samples in the dataset.
In biometrics like face recognition [67], one user may form an entire class
[11]. Moreover, user deletion requests may occur in bursts after certain
_events of interest_ , such as revelations of privacy leakages by an
organization [5]. Lastly, batching online deletion requests requires less
invocations of the unlearning procedure, boosting resource efficiency.

###  2.1 Against Model Indistinguishability

Prior works in inexact-unlearning like [71, 54, 68, 28, 58] combine forgetting
and utility, evaluating unlearning as: A procedure has unlearnt a given
deletion set $D_{f}$ if the distribution $\phi_{u}$ of models it produces is
indistinguishable from the distribution $\phi_{r}$ produced by retraining-
from-scratch using training procedure $T$ on $D\setminus D_{f}$.

However, there are important shortcomings with this goal of model
indistinguishability. Indistinguishability of the model distributions
$\phi_{u}$ and $\phi_{r}$ is not necessary for unlearning. To demonstrate
this, one can simply exploit the fact that tweaking the training procedure
gives significantly different model distributions [73]. Let us generate
another model distribution $\phi^{\prime}_{r}$ by using training procedure
$T^{\prime}$ on dataset $D\setminus D_{f}$. $T^{\prime}$ can be created by
varying multiple critical hyperparameters in $T$, like the number of epochs,
regularization method, and the learning rate to ensure that
$\phi^{\prime}_{r}$ is significantly different from $\phi_{r}$. Now, both
$\phi_{r}$ and $\phi^{\prime}_{r}$ achieve forgetting because they both are
unaware of the deletion set. However, $\phi_{r}$ and $\phi^{\prime}_{r}$ are
significantly different, which illustrates the existence of multiple model
distributions that satisfy the goal of unlearning. Thus, the
indistinguishability definition excludes most correct solutions by
unnecessarily penalizing them for not matching one particular distribution. To
handle this, some definitions [30, 31, 29, 11] only require the existence of
some retrain distribution $\phi^{*}_{r}$ obtained from a potentially different
training procedure than $T$ which is indistinguishable from $\phi_{u}$.
However, it is practically infeasible to both find such a distribution
$\phi^{*}_{r}$ and even measure the equivalence of model distributions. This
is due to the prohibitive cost of collecting a representative sample of deep
networks.

Most prior work approximates the equivalence of model distributions by
measuring similarity of weights [71, 64, 41] or outputs [30, 31, 29, 54]
between a single model sampled from $\phi_{u}$ and $\phi_{r}$. However,
measuring similarity between two model instances is not representative of the
similarity between the underlying distributions. Further, parallel work [65]
illustrates how it is possible to obtain a model identical to the original
model $M$ even when not using $D_{f}$ for training. Thus, even $M$ can be
drawn from $\phi_{r}$, in which case performing no unlearning might pass
similarity-to-retrained-model based criteria.

To summarize: _model indistinguishability is neither necessary nor sufficient
for defining unlearning in practice._

###  2.2 Against Data-Influence Isolation

Figure 2: Hyperbolic deterioration of efficiency in isolation-based unlearning
when scaling to a large number of removed samples. In this work, we analyze
$|D_{f}|$ from 100-4000 where $\mathbb{E}[Y]\sim 1$.

Among recent work that does not rely on the indistinguishability criterion,
data-influence isolation approaches form the majority. They achieve the
forgetting objective by simply ensuring no access to the deletion set. A
detailed discussion of prior work in isolation-based strategies is provided in
Appendix Section B.1.

Figure 3: Interclass Confusion Test Pipeline: First, we mislabel a subset of
samples (here, shape and colour represent image content and label
respectively) from two classes of the original dataset, forming $D_{f}$. Then,
$M$ and $M_{r}$ are obtained by training from scratch on $D$ and $D\setminus
D_{f}$ respectively. The unlearning procedure can leverage (some of) $M$,
$D_{f}$ and $D\setminus D_{f}$ to produce the unlearnt model $M_{u}$. Finally,
we evaluate using three metrics described in Section 3.1. Notice the specific
cells used in computing the Forgetting Score and Error.

Figure 2 demonstrates that the computation costs of isolation-based strategies
scale poorly as the deletion set size increases. Let $P$ be the number of
parts obtained with the isolation strategy. We assume the best-case scenario
where each sample only influences one part. We make the simplifying assumption
that the samples are uniformly distributed across parts, and the probability
of a removed sample belonging to any particular portion remains constant
($\frac{1}{P}$). Let $Y$ be the number of affected parts. The probability part
$i$ is affected by atleast one sample in $D_{f}$ is
$1-(1-\frac{1}{P})^{|D_{f}|}$. Thus by the linearity of expectation:

$\mathop{\mathbb{E}}[Y]=P\left(1-\left(1-\frac{1}{P}\right)^{|D_{f}|}\right)$
(1)

##  3 Approach

Appendix Table 8 lists all abbreviations for reference.

###  3.1 Evaluation Strategies

Evaluation strategies aim to detect imperfectness in unlearning for any given
deletion set size $n$. Evaluations in existing literature have used two tests:

Random Samples (RS): The deletion set is formed by selecting $n$ random
samples from $D$.

Class Removal (CR): It does targeted sample selection compared to RS, removing
$n$ samples from a particular class. We call it full class removal (FCR) when
all samples of a class are removed and partial class removal (pCR) otherwise.

Both RS and CR overlook the potential to use data manipulations which can
introduce a strong differentiating influence specific to $D_{f}$, enhancing
evaluations.

Interclass Confusion (IC): As illustrated in Figure 3:

  1. 1.

Take $\frac{n}{2}$ samples each from two chosen classes in the training data
$S\subset D$ (Strategic sampling).

  2. 2.

Swap labels between the two classes for all samples in $S$ (Label
manipulation) to get the confused set $S^{\prime}$. $S^{\prime}$ and
$D\setminus S$ together form the new training data $D^{\prime}$.

  3. 3.

Mark the entirety of $S^{\prime}$ as data to be deleted ($D_{f}$) from the
trained model.

Random Confusion (RC): It ablates targeted data selection as in IC test.
Specifically, only the first step of IC is changed with $S$ now consisting of
$n$ samples drawn randomly from $D$ and mislabelled randomly to a different
class.

Test | Targeted | Mislabels
---|---|---
RS | $\times$ | $\times$
CR | $\checkmark$ | $\times$
RC | $\times$ | $\checkmark$
IC | $\checkmark$ | $\checkmark$

Table 1:  Targeted tests provide insights with smaller deletion sets. Removal
of mislabelled data aligns forgetting with utility.

We summarize the data manipulation and subset selection strategies of the four
tests in Table 1.

Metric | Test | DPBU | Comp | CPG
---|---|---|---|---
Relearn time | RS [29], pCR [30, 31], FCR [29] | $\times$ | $\times$ | $\times$
L2 weights | RS [71, 41, 64] | $\times$ | $\times$ | $\checkmark$
L1-ConfusionMat | RS [54] | $\times$ | $\checkmark$ | $\checkmark$
L1-Softmax | RS [29], pCR [31], FCR [29] | $\times$ | $\checkmark$ | $\checkmark$
MIA |  RS [29, 47], pCR [31], FCR [29, 11], IC (Ours) | $\checkmark$ | $\checkmark$ | $\times$
Error |  pCR [30, 31], FCR [29], RS [37, 29, 59] | $\times$ | $\checkmark$ | $\checkmark$
Error | RC (Ours), IC (Ours) | $\checkmark$ | $\checkmark$ | $\checkmark$
Forgetting Score | FCR, IC (Ours) | $\checkmark$ | $\checkmark$ | $\checkmark$

Table 2:  Unlike ours, existing evaluation methods do not satisfy atleast one
of the three desiderata.

Now discussing metrics, let the confusion matrix generated by model $M$ on any
given dataset $S$ be denoted by $C^{M,S}$. Let the confused classes in the IC
test be $A$, $B$ and their samples in $S$ be $S_{A}$ and $S_{B}$.

Error (Err): Computing error is a standard label-only metric used in prior
work which measures the percentage of mistakes made on samples from the
affected classes. For the IC test, it only considers samples from the confused
classes:

$Err(M,S,A,B)=\frac{\sum_{k}C^{M,S}_{A,k}+\sum_{k^{\prime}}C^{M,S}_{B,k^{\prime}}}{|S_{A}|+|S_{B}|},k\neq
A,~{}k^{\prime}\neq B$

Forgetting Score (Fgt): We propose Fgt which measures the number of samples
classified in a way that wouldn’t occur if the information had been fully
removed. For the IC-test, it is the number of samples still confused between
the two classes: $Fgt(M,S,A,B)=C^{M,S}_{A,B}+C^{M,S}_{B,A}$.

For confusion between $N>2$ classes, Fgt is the sum of the confusion matrix
terms for all pair-wise misclassifications among the $N$ classes. Thus, Fgt
converges to error when $N$ is the same as the total number of classes, as in
RC and RS. For CR test, Fgt calculates the number of samples labelled as the
removed class, further details in Appendix Section C.2.2. Note that even
though the influence of utility is significantly lesser than Err as
illustrated in Figure 3, increasing model accuracy can lower Fgt without
removing more information. Even on complete removal of information specific to
$D_{f}$, Fgt can be non-zero if some samples are mislabelled between the
confused classes. While lower Fgt can reliably rank better unlearnt models in
the same setting, it is unclear what values of Fgt guarantee that a model has
unlearnt perfectly. Designing metrics which disentangle forgetting and utility
completely remains an open problem.

Confidence-based MIA (CoMI): Membership Inference Attacks (MIA) [60] aim to
infer the presence of particular samples in the training data. Recently, a
simple confidence-based MIA (CoMI) [62] has been shown to match the
performance of even expensively trained white-box MIA classifiers (see [40]
for a survey). We tailor traditional MIA formulations for unlearning and adapt
CoMI for the IC test by using the confidence of the confused class labels
instead of true classes. A detailed description is included in Appendix
Section B.2. As in existing MIA literature, the attack accuracy ranges from
50% (unlearnt) to 100%, with a higher value signifying more confidence in
detecting whether a sample was in the training data.

###  3.2 Comparison of Evaluation Methods

As shown in Table 2, the IC test achieves three important qualities not found
_together_ in existing evaluation methods.

Does not penalize better utility (DPBU): We need evaluation methods to not
penalize better utility. Consider using a combination of RS test and the error
metric on deletion set samples [37, 59, 29], better unlearning would be
required to have a higher error. Such an evaluation can not differentiate
between an unlearnt model that generalizes well to the (now unseen) deletion
set and one that does not unlearn at all. Similarly, metrics measuring
indistinguishability criteria exclude a large set of correct solutions,
unnecessarily penalizing even the ones with better utility.

Comparability (Comp): Metrics should enable choosing between unlearning
procedures in the presence of differing training procedures and architectures
as such changes are often used to enable better unlearning [12, 37, 30, 31,
29, 32]. As mentioned in Table 2, L2-weights cannot be compared if there is
any architectural modification. Similarly, re-learn time [30, 31, 29] is too
sensitive to the training procedure $T$.

Checks Property Generalization (CPG): Zhang et. al. [76] demonstrated that
deep networks can overfit on randomly labelled training data, a phenomenon
known as memorization. In contrast, certain properties only present in $D_{f}$
might have introduced effects on the classification of unseen samples [49],
which we term as _property generalization_. Removal of such generalized
properties is especially important for debiasing, denoising and depoisoning.
However, prior tests such as membership inference attacks [60, 18] only try to
determine memorization, with no explicit consideration for property
generalization. Fgt and Err when computed on the deletion set $D_{f}$ measure
memorization. On the subset $D_{t}$ of unseen (test set) samples from the
affected classes, they measure property generalization. In the untargeted RS
and RC, as all classes are affected $D_{t}$ is the same as the full test set.
We empirically show how some unlearning methods may remove memorization but
not property generalization in Section 4.2.3.

Note that all evaluations discussed here, both past and proposed, give a
specific setting which unlearning procedures may overfit to without actually
being capable of forgetting all information. Like in _attacks_ , passing any
single evaluation alone cannot guarantee perfect unlearning. Thus, an
unlearning procedure should be benchmarked on the hardest evaluations possible
to have greater confidence in its efficacy. We empirically show that the IC
test consistently detects retained information better than existing tests
across multiple unlearning metrics making it a strong benchmark.

###  3.3 Methods: Information Retention in DNNs

We propose a way to determine how early information specific to $D_{f}$ is
encoded in a deep network. For any model $M$, we can obtain an unlearnt model
$M_{u}$ by erasing all information gained from $D_{f}$ in the final $k$
layers. If the IC test shows $M_{u}$ still didn’t forget all information, we
know some information has to be present in the earlier layers.

Exact-unlearning the last $k$ layers (EU-$k$): We freeze the initial layers of
the model $M$, and retrain the last $k$ layers from scratch using the same
training procedure $T$ on retain set $D\setminus D_{f}$. Varying $k$ allows us
to check how early in the network the test can detect the presence of
information.

Catastrophically forgetting the last $k$ layers (CF-$k$): Neural Networks
suffer from catastrophic-forgetting [26], when a model is continually updated
without some previously learnt samples, the model loses knowledge about them.
We freeze the initial layers of the model $M$ and finetune the last $k$ layers
on the retain set $D\setminus D_{f}$. We use the same training procedure $T$
but for fewer epochs as the information learnt by the original model is
leveraged, making it significantly more efficient than EU-$k$. We measure how
close catastrophic-forgetting gets to the complete removal of information
about $D_{f}$ for varying $k$.

Both EU-$k$ and CF-$k$ exploit the fact that a large fraction of computation
occurs during convolutions in the early layers [13]. The features produced by
the earlier layers can be precomputed once, requiring increasingly less time
for unlearning as $k$ decreases. In Appendix Section D.2, we show that a small
$k$ suffices for removing most information as the earlier layers encode
generic low-level features [74]. We empirically show varying $k$ trades-off
forgetting with resource-efficiency at similar utility as $M_{r}$, thus making
EU-$k$ and CF-$k$ valuable baselines for inexact-unlearning. EU-$k$ and CF-$k$
do not require access to $D_{f}$, which is a useful quality when handling
deletion requests in the privacy setting.

##  4 Experiments

We now empirically compare our IC test and CF/EU baselines, using them to
obtain broader insights. We discuss implementation details in Appendix Section
C.1.

###  4.1 Experimental Setup

Evaluation: We compute the Err, Fgt and CoMI for the tests, except in RS and
RC where Fgt is the same as Err and thus is redundant. We use the same
deletion set size $n$ for a fair comparison across tests. Experiments in this
section use $n$ corresponding to the number of training samples in one class:
4000 for CIFAR10 and 400 for CIFAR100 [44]. In this setting, the CR test
completely removes all information about the class (FCR). The IC test
completely confuses the two classes involved, and robustness to label noise
[50] cannot help unlike in RC. More details about choices made for the tests
are in Appendix Section C.3. Appendix Sections D.4 and D.3 show the effect of
varying deletion set size, we find that observations about IC test detailed
later in this section are consistent even for smaller deletion sets.

Table Structure: Each number represents the ’information remaining’ in the
model (row) as estimated by the evaluation strategy (column). A better test
gives a clearer forgetting trend: i) It should ideally detect retained
information in inexact unlearning procedures as having worse numbers than the
retrain model ii) It should reliably distinguish more effective unlearning
procedures and rank them in the correct order as represented by the arrow in
the column header.

The values of original model $M$ can be used as a reference for how much
information was present initially. This gives an idea of how much improvement
the unlearning procedure produced. Similarly, the values of the retrain model
$M_{r}$ (obtained using the same training procedure $T$) can be used as a
reference for perfect forgetting. A better unlearning procedure gives values
which are closer to the retrained model than the original model. However,
unlike the indistinguishability criteria, the unlearnt model can obtain better
numbers than the retrain model which can occur due to the influence of utility
on metrics. Similarly, having the same value as the retrain model does not
guarantee perfect forgetting, it only indicates that the evaluation cannot
differentiate further.

###  4.2 Results

We compare various evaluation strategies, unlearning methods and the effect of
the training procedure on unlearning. All results are averaged over three runs
with different seeds.

####  4.2.1 Evaluation Method Comparisons

Method |  | RS-Err ($\uparrow$ $\downarrow$) | CR-Err ($\uparrow$) | RC-Err ($\downarrow$) | IC-Err ($\downarrow$) | CR-Fgt ($\downarrow$) | IC-Fgt ($\downarrow$)
---|---|---|---|---|---|---|---
CIFAR-10 ($|D_{f}|=4000$)
Original |  | 8.4 $\pm$ 0.2 | 7.4 $\pm$ 1.4 | 14.3 $\pm$ 0.7 | 53.2 $\pm$ 1.0 | 1006.0 $\pm$ 19.2 | 901.3 $\pm$ 27.1
1-layer | CF | 8.4 $\pm$ 0.1 | 68.1 $\pm$ 7.4 | 13.0 $\pm$ 0.9 | 40.9 $\pm$ 0.4 | 319.0 $\pm$ 73.7 | 621.0 $\pm$ 21.0
EU | 8.5 $\pm$ 0.1 | 100.0 $\pm$ 0.0 | 12.8 $\pm$ 0.9 | 40.4 $\pm$ 0.4 | 0.0 $\pm$ 0.0 | 624.3 $\pm$ 31.1
10-layers | CF | 8.4 $\pm$ 0.2 | 97.4 $\pm$ 1.1 | 12.0 $\pm$ 0.6 | 27.3 $\pm$ 0.6 | 26.3 $\pm$ 10.8 | 349.7 $\pm$ 13.1
EU | 8.7 $\pm$ 0.1 | 100.0 $\pm$ 0.0 | 12.0 $\pm$ 0.7 | 28.1 $\pm$ 1.8 | 0.0 $\pm$ 0.0 | 354.0 $\pm$ 13.1
50-layers | CF | 8.5 $\pm$ 0.1 | 100.0 $\pm$ 0.0 | 10.0 $\pm$ 0.4 | 24.0 $\pm$ 0.8 | 0.0 $\pm$ 0.0 | 229.0 $\pm$ 14.0
EU | 9.3 $\pm$ 0.3 | 100.0 $\pm$ 0.0 | 10.4 $\pm$ 0.4 | 23.3 $\pm$ 0.3 | 0.0 $\pm$ 0.0 | 209.7 $\pm$ 15.0
Retrain |  | 9.3 $\pm$ 0.1 | 100.0 $\pm$ 0.0 | 8.8 $\pm$ 0.3 | 22.3 $\pm$ 0.9 | 0.0 $\pm$ 0.0 | 179.7 $\pm$ 4.5
CIFAR-100 ($|D_{f}|=400$)
Original |  | 32.1 $\pm$ 1.1 | 16.0 $\pm$ 1.7 | 32.4 $\pm$ 1.4 | 60.7 $\pm$ 5.5 | 96.7 $\pm$ 2.3 | 77.0 $\pm$ 9.3
1-layer | CF | 32.1 $\pm$ 1.0 | 100.0 $\pm$ 0.0 | 32.4 $\pm$ 1.3 | 57.7 $\pm$ 4.4 | 0.0 $\pm$ 0.0 | 67.3 $\pm$ 3.8
EU | 32.1 $\pm$ 1.0 | 100.0 $\pm$ 0.0 | 32.4 $\pm$ 1.2 | 56.3 $\pm$ 5.5 | 0.0 $\pm$ 0.0 | 65.3 $\pm$ 4.5
10-layers | CF | 32.4 $\pm$ 0.9 | 100.0 $\pm$ 0.0 | 32.6 $\pm$ 1.3 | 49.7 $\pm$ 2.8 | 0.0 $\pm$ 0.0 | 52.7 $\pm$ 4.5
EU | 33.3 $\pm$ 1.2 | 100.0 $\pm$ 0.0 | 33.3 $\pm$ 1.2 | 49.8 $\pm$ 4.3 | 0.0 $\pm$ 0.0 | 50.3 $\pm$ 8.5
50-layers | CF | 31.7 $\pm$ 0.9 | 100.0 $\pm$ 0.0 | 31.8 $\pm$ 0.8 | 43.7 $\pm$ 1.9 | 0.0 $\pm$ 0.0 | 34.3 $\pm$ 4.7
EU | 32.1 $\pm$ 0.3 | 100.0 $\pm$ 0.0 | 31.8 $\pm$ 1.0 | 47.0 $\pm$ 2.8 | 0.0 $\pm$ 0.0 | 33.3 $\pm$ 4.5
Retrain |  | 32.2 $\pm$ 0.4 | 100.0 $\pm$ 0.0 | 31.7 $\pm$ 1.3 | 45.5 $\pm$ 5.2 | 0.0 $\pm$ 0.0 | 30.3 $\pm$ 2.1

Table 3: Comparison of evaluation methods for property generalization. Scores
are reported as: mean $\pm$ stdev. For RS-Err, forgetting ($\uparrow$ is
better) and utility ($\downarrow$ is better) are misaligned. Only the IC-test
demonstrates that exactly unlearning the final layer does not remove
properties generalized from $D_{f}$.

Property generalization (Measured on $D_{t}$): In Table 3 we compare different
evaluation methods444Recall that MIA cannot measure property generalization.
and state consistent observations. Primarily, the IC test is the only test
which reliably determines that exactly unlearning the final layer (comparing
the rows 1 layer-EU and Retrain) does not remove generalized properties.
Comparing the columns, we see that neither the addition of confusion (RS
$\rightarrow$ RC) nor targeted sample selection (RS $\rightarrow$ CR) detects
imperfect forgetting of generalized properties alone, _both_ components
(forming the IC-test) are necessary. Given EU-50 has higher IC-Fgt than the
Retrain model, our IC-test can detect retained generalized properties upto
almost half the depth of the network. Comparing CF and EU procedures for each
value of $k$, we observe that catastrophic-forgetting is able to unlearn
nearly as well as exact-unlearning.

Method |  | RS-Err ($\uparrow$$\downarrow$) | CR-Err ($\uparrow$) | RC-Err ($\downarrow$) | IC-Err ($\downarrow$) | CR-Fgt ($\downarrow$) | IC-Fgt ($\downarrow$) | RS-CoMI ($\downarrow$) | CR-CoMI ($\downarrow$) | RC-CoMI ($\downarrow$) | IC-CoMI ($\downarrow$)
---|---|---|---|---|---|---|---|---|---|---|---
CIFAR-10 ($|D_{f}|=4000$)
Original |  | 0.2 $\pm$ 0.1 | 0.1 $\pm$ 0.1 | 52.9 $\pm$ 4.4 | 77.3 $\pm$ 0.6 | 3996.0 $\pm$ 2.0 | 3054.3 $\pm$ 44.4 | 55.9 $\pm$ 0.2 | 55.2 $\pm$ 0.4 |  $<$ 50 | 67.1 $\pm$ 1.0
1-layer | CF | 0.2 $\pm$ 0.0 | 62.0 $\pm$ 9.0 | 44.9 $\pm$ 4.6 | 58.7 $\pm$ 1.1 | 1518.3 $\pm$ 365.2 | 2295.3 $\pm$ 43.9 | 55.8 $\pm$ 0.1 | 59.0 $\pm$ 1.7 |  $<$ 50 | 64.6 $\pm$ 1.5
EU | 0.2 $\pm$ 0.1 | 100.0 $\pm$ 0.0 | 44.1 $\pm$ 4.9 | 58.7 $\pm$ 1.0 | 0.0 $\pm$ 0.0 | 2299.3 $\pm$ 50.8 | 55.8 $\pm$ 0.1 | 64.5 $\pm$ 1.0 |  $<$ 50 | 64.5 $\pm$ 1.7
10-layers | CF | 0.4 $\pm$ 0.0 | 96.3 $\pm$ 1.3 | 33.2 $\pm$ 2.2 | 32.0 $\pm$ 0.9 | 146.3 $\pm$ 58.1 | 1241.3 $\pm$ 23.2 | 55.2 $\pm$ 0.2 | 60.6 $\pm$ 1.9 |  $<$ 50 | 58.6 $\pm$ 0.2
EU | 0.6 $\pm$ 0.1 | 100.0 $\pm$ 0.0 | 31.1 $\pm$ 1.6 | 30.0 $\pm$ 1.0 | 0.0 $\pm$ 0.0 | 1156.3 $\pm$ 10.3 | 55.0 $\pm$ 0.4 | 64.1 $\pm$ 1.3 |  $<$ 50 | 58.5 $\pm$ 0.9
50-layers | CF | 3.6 $\pm$ 0.8 | 100.0 $\pm$ 0.0 | 12.7 $\pm$ 1.1 | 20.4 $\pm$ 0.3 | 0.0 $\pm$ 0.0 | 571.0 $\pm$ 16.1 | 52.0 $\pm$ 0.6 | 61.6 $\pm$ 3.6 |  $<$ 50 | 54.1 $\pm$ 0.3
EU | 7.3 $\pm$ 1.0 | 100.0 $\pm$ 0.0 | 11.4 $\pm$ 1.4 | 22.0 $\pm$ 0.9 | 0.0 $\pm$ 0.0 | 457.7 $\pm$ 21.4 | 50.5 $\pm$ 0.8 | 67.3 $\pm$ 4.6 |  $<$ 50 | 52.7 $\pm$ 0.8
Retrain |  | 9.2 $\pm$ 0.5 | 100.0 $\pm$ 0.0 | 9.0 $\pm$ 0.1 | 22.2 $\pm$ 1.0 | 0.0 $\pm$ 0.0 | 377.3 $\pm$ 15.5 |  $<$ 50 $\pm$ 0.4 | 62.8 $\pm$ 1.4 |  $<$ 50 | 51.8 $\pm$ 0.6
CIFAR-100 ($|D_{f}|=400$)
Original |  | 0.1 $\pm$ 0.1 | 0.0 $\pm$ 0.0 | 99.6 $\pm$ 0.3 | 99.1 $\pm$ 1.2 | 399.3 $\pm$ 0.6 | 397.0 $\pm$ 1.7 | 57.9 $\pm$ 1.4 | 63.2 $\pm$ 1.6 |  $<$ 50 | 83.3 $\pm$ 3.1
1-layer | CF | 0.2 $\pm$ 0.1 | 100.0 $\pm$ 0.0 | 99.0 $\pm$ 0.4 | 96.3 $\pm$ 1.4 | 0.0 $\pm$ 0.0 | 382.7 $\pm$ 2.3 | 57.7 $\pm$ 2.2 | 66.1 $\pm$ 1.4 |  $<$ 50 | 81.1 $\pm$ 2.0
EU | 0.1 $\pm$ 0.1 | 100.0 $\pm$ 0.0 | 98.7 $\pm$ 0.6 | 95.6 $\pm$ 0.3 | 0.0 $\pm$ 0.0 | 382.7 $\pm$ 4.5 | 57.4 $\pm$ 1.2 | 59.4 $\pm$ 1.6 |  $<$ 50 | 81.1 $\pm$ 2.5
10-layers | CF | 0.8 $\pm$ 0.7 | 100.0 $\pm$ 0.0 | 81.8 $\pm$ 2.0 | 77.6 $\pm$ 8.8 | 0.0 $\pm$ 0.0 | 303.0 $\pm$ 35.5 | 56.4 $\pm$ 1.6 | 63.6 $\pm$ 1.1 |  $<$ 50 | 76.1 $\pm$ 3.0
EU | 2.8 $\pm$ 1.9 | 100.0 $\pm$ 0.0 | 73.1 $\pm$ 3.8 | 71.2 $\pm$ 6.1 | 0.0 $\pm$ 0.0 | 264.3 $\pm$ 33.8 | 55.4 $\pm$ 0.5 | 58.1 $\pm$ 3.2 |  $<$ 50 | 71.2 $\pm$ 2.8
50-layers | CF | 18.6 $\pm$ 4.0 | 100.0 $\pm$ 0.0 | 36.7 $\pm$ 2.0 | 40.1 $\pm$ 2.3 | 0.0 $\pm$ 0.0 | 81.0 $\pm$ 5.0 | 50.7 $\pm$ 3.0 | 59.5 $\pm$ 1.9 |  $<$ 50 | 57.8 $\pm$ 1.0
EU | 31.5 $\pm$ 4.1 | 100.0 $\pm$ 0.0 | 32.7 $\pm$ 3.5 | 40.7 $\pm$ 2.8 | 0.0 $\pm$ 0.0 | 51.7 $\pm$ 3.8 |  $<$ 50 | 59.4 $\pm$ 1.5 |  $<$ 50 | 52.2 $\pm$ 0.3
Retrain |  | 33.4 $\pm$ 4.3 | 100.0 $\pm$ 0.0 | 32.8 $\pm$ 1.4 | 41.0 $\pm$ 2.3 | 0.0 $\pm$ 0.0 | 59.0 $\pm$ 5.6 |  $<$ 50 | 60.2 $\pm$ 3.4 |  $<$ 50 | 53.9 $\pm$ 1.4

Table 4: Comparison of evaluation methods for memorization. Scores are
reported as: mean $\pm$ stdev. While other tests run into limitations across
metrics, IC consistently amplifies memorization removal trends demonstrating
it is significantly more useful than other tests.

Memorization (Measured on $D_{f}$): In Table 4 we compare different evaluation
methods and state consistent observations. The CR test columns indicate CR is
not able to detect memorized information even in exact-unlearning of the final
layer. Comparing tests using the CoMI metric, we observe that IC is the only
test that clearly demonstrates the forgetting trends across unlearning more
layers. In contrast, RS-CoMI gives a weak signal while CR-CoMI and RC-CoMI do
not give any insights. Comparing tests using the Err metric, the RS test also
seems to give clear trends, but its interpretation is unclear since RS-Err
penalizes better utility. Specifically, a perfectly unlearnt model can give a
low RS-Err if it simply generalizes to the now unseen deletion set. In
contrast, the IC and RC tests are free from such issues. Comparing CF and EU
procedures for each value of $k$, we observe that catastrophic-forgetting is
slightly worse than exact-unlearning.

Overall, the IC-test is the most effective in distinguishing between varying
forgetting efficacy across metrics. For a given $k$, catastrophic-forgetting
removes most of the information in those layers despite being twice as
resource efficient as exact-unlearning. We conclude that EU-$1$ leaks a lot of
information gained from $D_{f}$, severely limiting the usefulness of prior
unlearning methods that only modify the final layer of deep networks [11, 71,
41].

Method |  | None | Early Stop | Cutmix | Cutmix+Early
---|---|---|---|---|---
CIFAR-10 ($|D_{f}|=4000$)
Original |  | 3054$|$901 | 2187$|$883 | 2178$|$850 | 2156$|$955
10-layers | CF | 1241$|$349 | 685$|$280 | 641$|$249 | 648$|$272
EU | 1156$|$354 | 719$|$281 | 663$|$270 | 667$|$279
50-layers | CF | 571$|$229 | 526$|$230 | 477$|$209 | 494$|$225
EU | 457$|$209 | 484$|$213 | 444$|$210 | 507$|$223
Retrain |  | 377$|$179 | 518$|$227 | 418$|$201 | 518$|$214
CIFAR-100 ($|D_{f}|=400$)
Original |  | 397$|$77 | 318$|$84 | 295$|$83 | 213$|$70
10-layers | CF | 303$|$52 | 179$|$43 | 110$|$43 | 86$|$24
EU | 264$|$50 | 136$|$42 | 106$|$35 | 77$|$23
50-layers | CF | 81$|$34 | 75$|$26 | 57$|$31 | 57$|$19
EU | 51$|$32 | 59$|$30 | 51$|$36 | 50$|$31
Retrain |  | 59$|$30 | 60$|$37 | 55$|$28 | 54$|$26

Table 5: Forgetting scores quantifying unlearning efficacy when using
different regularizers for training the original model. Scores are reported as
Memorization $|$ Property Generalization computed using IC-Fgt ($\downarrow$)
on $D_{f}$ and $D_{t}$ respectively.

Model |  | IC-Fgt ($\downarrow$) | Err ($\uparrow$) | Test Err ($\downarrow$) | Time(s) ($\downarrow$)
---|---|---|---|---|---
$T$ from [30, 31]
Original |  | 92.3$|$121.6 | 8.3$|$7.0 | 26.7 | 0.00
Fisher |  | 94.6$|$157.0 | 6.0$|$5.6 | 33.2 | 141.95
NTK-F |  | 77.0$|$119.6 | 23.0$|$20.3 | 31.0 | 141.90
Retrain |  | 0.0$|$0.0 | 100.0$|$100.0 | 41.4 | 9.81
$T$ (Ours)
Original |  | 98.0$|$97.3 | 0.0$|$15.6 | 16.3 | 0.00
1-layer | CF | 18.3$|$12.3 | 79.5$|$88.9 | 30.9 | 4.43
EU | 9.6$|$4.3 | 87.6$|$96.4 | 31.9 | 9.38
10-layers | CF | 15.6$|$9.3 | 82.0$|$91.0 | 29.4 | 5.22
EU | 2.0$|$0.0 | 97.8$|$100.0 | 32.6 | 10.78
Retrain |  | 0.0$|$0.0 | 100.0$|$100.0 | 32.5 | 12.33

Model |  | IC-Fgt ($\downarrow$) | Err ($\downarrow$) | Test Err ($\downarrow$) | Time(s) ($\downarrow$)
---|---|---|---|---|---
$T$ from [30, 31]
Original |  | 54.3$|$85.0 | 65.5$|$58.6 | 42.8 | 0.00
Fisher |  | 57.6$|$96.6 | 64.3$|$56.0 | 43.7 | 142.73
NTK-F |  | 9.6$|$31.0 | 18.6$|$25.1 | 31.1 | 142.76
Retrain |  | 9.0$|$13.3 | 25.0$|$18.3 | 30.5 | 9.15
$T$ (Ours)
Original |  | 79.6$|$91.6 | 84.5$|$51.3 | 33.3 | 0.00
1-layer | CF | 16.3$|$23.6 | 25.6$|$20.0 | 20.8 | 4.58
EU | 13.3$|$19.3 | 24.3$|$19.5 | 20.6 | 9.57
10-layers | CF | 13.6$|$19.2 | 28.2$|$21.0 | 21.2 | 5.31
EU | 8.0$|$11.3 | 21.0$|$18.3 | 19.4 | 10.93
Retrain |  | 6.3$|$8.6 | 19.0$|$14.5 | 17.7 | 12.79

Table 6: _Comparison between methods on FCR-Test (left) and IC-Test (right) on
Small-CIFAR-5. Fgt and Err are reported as: Memorization $|$ Property
Generalization computed on $D_{f}$ and $D_{t}$ respectively. We also report
the error on full test set and unlearning time._

####  4.2.2 Amenability to Unlearning

Intuitively, different original models can show varying propensities to
memorize $D_{f}$, and the same unlearning procedures may be able to remove
more information from some original models. We investigate the effects of
changing the training procedure $T$ when training the original model $M$ on
the efficacy of unlearning. We find regularization methods, like cutmix [75]
and early stopping, have a significant effect on forgetting while providing
better utility and resource-efficiency respectively.

From Table 5, our primary observation from the first row is that both early
stopping and cutmix greatly reduce memorization of confused labels in the
original model. Comparing across rows, we observe that unlearning 10-layers
from a regularized model achieves a much greater decrease in both memorization
and property generalization. This indicates better regularization of the
original model makes it easier to remove information; however, as better
unlearning deletes more information, the benefits of regularization decrease
as can be seen by comparing lower rows (more layers) with higher rows.

Overall, the training procedure for the original model can have a significant
impact on the efficacy of unlearning. Thus, when no training assumptions are
involved, a fair comparison of unlearning methods requires starting from
similarly trained original models.

####  4.2.3 Unlearning Method Comparisons

Setup: We compare EU-$k$ and CF-$k$ with approaches which are not explicitly
limited to tiny deletion sets and have made their code available: Fisher[30]
and NTK+Fisher (NTK-F) [31]. We use Small-CIFAR-5, a subset of CIFAR10, as in
Golatkar et. al. [30, 31] for comparing Fisher and NTK-F as they cannot scale
to larger datasets like CIFAR10 due to extensive memory requirements. Both
Fisher and NTK-F require a variety of training assumptions not found in
standard training procedures. We use the training procedure of Golatkar et.
al. to benchmark Fisher and NTK-F while following our standard training
procedure for EU-$k$ and CF-$k$. We present results on both the CR and IC test
in Table 6.

Utility: We observe that the original and retrained models have a
significantly lower test set error and hence better utility. However, they
overfit more to the train set resulting in more memorization compared to
Golatkar et. al.. On the CR test, the retrained test error is higher than the
original as 20% of test set samples are from the removed class. There is no
compromise in utility compared to an exactly unlearnt model for both EU-$k$
and CF-$k$, which we show holds consistently for other datasets in Appendix
Section 10.

Forgetting: Surprisingly, Fisher does worse than no unlearning in both
evaluation settings, across all metrics (Fgt, Err, Test Error, Time). EU-$1$
outperforms CF-$10$ in both tests, indicating catastrophic-forgetting is less
effective on tiny datasets. On the CR test, NTK-F seems to achieve only
marginal forgetting, performing dramatically worse than even our final layer
unlearning methods. On the IC-Test, NTK-F is able to achieve a reduction in
memorization comparable to a retrained model. However, NTK-F does poorly in
removing property generalization, worse than even CF-$1$ and EU-$1$,
highlighting the need for a separate analysis of property generalization not
found in existing literature.

Fisher and NTK-F require compute costs for obtaining the Fisher Information
Matrix, to the extent that they take far more unlearning time than even
retraining from scratch. They show poor forgetting for large deletion sizes.
Overall, even for small $k$, CF-$k$ and EU-$k$ achieve better forgetting,
utility, and resource efficiency than previously proposed unlearning methods
beyond tiny deletion sets.

##  5 Conclusion

In this work, we motivated the need to unlearn large deletion sets, to which
data-influence isolation approaches scale poorly. To overcome the limitations
of indistinguishability-based definitions, we redefined the goal of unlearning
by splitting it into forgetting and utility, and highlighted resource-
efficiency. We discussed how forgetting involves removing two types of
information gained specifically from the data to be deleted: memorization and
property generalization. Our black-box Interclass Confusion test is domain-
agnostic as it only affects labels. It reliably distinguishes unlearning
procedures with varying forgetting efficacy, showing distinctive gaps across
metrics. We devised unlearning baselines which show that most information
specific to the deletion set is present in the final layers of the network, an
observation supported by recent parallel work [77, 8].

Overall, we hope that our definition of unlearning and IC test will guide the
design and evaluation of future approaches for inexact-unlearning. Our work
raises various future directions to be investigated: (1) How do we formalize
the notion of additional _information_ contributed by $D_{f}$? (2) Contrary to
aggregate scores over a dataset which might be influenced by model utility, is
it possible to devise an evaluation that reliably determines whether any
individual sample was forgotten? (3) Can we better investigate where
information about any subset of samples is stored in a deep network to allow
targeted deletion similar to Dai et. al. [21]?

Acknowledgements: We thank Shyamgopal Karthik, Saujas Vaduguru, Arjun T.H.,
Naren Akash R.J., Shradha Sehgal, Nikhil Chandak, Shashwat Chandra among
others for helpful feedback.

## References

  * [1] Alternative k-nearest neighbour rules in supervised pattern recognition: Part 1\. k-nearest neighbour classification by using alternative voting rules.  Analytica Chimica Acta, 1982.
  * [2] California consumer privacy act, 2018.
https://leginfo.legislature.ca.gov/faces/billTextClient.xhtml?bill˙id=201720180AB375.

  * [3] Humans forget, machines remember: Artificial intelligence and the right to be forgotten.  Computer Law & Security Review, 2018.
  * [4] Personal information protection and electronic documents act, 2018.
https://www.priv.gc.ca/en/opc-news/news-and-announcements/2018/an˙181010/.

  * [5] Alessandro Acquisti, Allan Friedman, and Rahul Telang.  Is there a cost to privacy breaches? an event study.  2006\.
  * [6] Nasser Aldaghri, Hessam Mahdavifar, and Ahmad Beirami.  Coded machine unlearning.  In IEEE Access, 2021.
  * [7] Devansh Arpit, Stanisław Jastrzundefinedbski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien.  A closer look at memorization in deep networks.  In ICML, 2017.
  * [8] Robert Baldock, Hartmut Maennel, and Behnam Neyshabur.  Deep learning through the lens of example difficulty.  NeurIPS, 2021.
  * [9] Michele Banko and Eric Brill.  Scaling to very very large corpora for natural language disambiguation.  ACL, 2001.
  * [10] Marco Barreno, Blaine Nelson, Russell Sears, Anthony D Joseph, and J Doug Tygar.  Can machine learning be secure?  In ASIA CCS, 2006.
  * [11] Thomas Baumhauer, Pascal Schöttle, and Matthias Zeppelzauer.  Machine unlearning: Linear filtration for logit-based classifiers.  arXiv preprint arXiv:2002.02730, 2020.
  * [12] Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot.  Machine unlearning.  In IEEE S&P, 2021.
  * [13] Andrew Brock, Theodore Lim, J. M. Ritchie, and Nick Weston.  Freezeout: Accelerate training by progressively freezing layers, 2017\.
  * [14] Jonathan Brophy and Daniel Lowd.  Machine unlearning for random forests.  In ICML, 2021.
  * [15] Yinzhi Cao and Junfeng Yang.  Towards making systems forget with machine unlearning.  In IEEE S&P, 2015.
  * [16] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In USENIX Security, 2019.
  * [17] Gert Cauwenberghs and Tomaso Poggio.  Incremental and decremental support vector machine learning.  In NeurIPS, 2000.
  * [18] Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang.  When machine unlearning jeopardizes privacy.  In CCS, 2021.
  * [19] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song.  Targeted backdoor attacks on deep learning systems using data poisoning.  arXiv preprint arXiv:1712.05526, 2017.
  * [20] Council of European Union.  Council regulation (EU) no 269/2014, 2014.
http://eur-lex.europa.eu/legal-
content/EN/TXT/?qid=1416170084502&uri=CELEX:32014R0269.

  * [21] Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, and Furu Wei.  Knowledge neurons in pretrained transformers.  arXiv preprint arXiv:2104.08696, 2021.
  * [22] Simone Fabbrizzi, Symeon Papadopoulos, Eirini Ntoutsi, and Ioannis Kompatsiaris.  A survey on bias in visual datasets.  arXiv preprint arXiv:2107.07919, 2021.
  * [23] Federal Trade Commission.  California company settles ftc allegations it deceived consumers about use of facial recognition in photo storage app, January 2021.
  * [24] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In CCS, 2015.
  * [25] Benoit Frenay and Michel Verleysen.  Classification in the presence of label noise: A survey.  In IEEE NNLS, 2014.
  * [26] Robert M. French.  Catastrophic forgetting in connectionist networks.  In Trends in Cognitive Sciences, 1999.
  * [27] Shaopeng Fu, Fengxiang He, Yue Xu, and Dacheng Tao.  Bayesian inference forgetting, 2021.
  * [28] Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou.  Making AI forget you: Data deletion in machine learning.  In NeurIPS, 2019.
  * [29] Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto.  Mixed-privacy forgetting in deep networks.  In CVPR, 2021.
  * [30] Aditya Golatkar, Alessandro Achille, and Stefano Soatto.  Eternal sunshine of the spotless net: Selective forgetting in deep networks.  In CVPR, 2020.
  * [31] Aditya Golatkar, Alessandro Achille, and Stefano Soatto.  Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations.  In ECCV, 2020.
  * [32] Laura Graves, Vineel Nagisetty, and Vijay Ganesh.  Amnesiac machine learning.  In AAAI, 2021.
  * [33] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens van der Maaten.  Certified data removal from machine learning models.  In ICML, 2020.
  * [34] Tomohiro Hayase, Suguru Yasutomi, and Takashi Katoh.  Selective forgetting of deep networks at a finer level than samples.  In AAAI-W, 2021.
  * [35] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In CVPR, 2015.
  * [36] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [37] Yingzhe He, Guozhu Meng, Kai Chen, Jinwen He, and Xingbo Hu.  Deepobliviate: A powerful charm for erasing data residual memory in deep neural networks.  arXiv preprint arXiv:2105.06209, 2021.
  * [38] Dan Hendrycks and Kevin Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  ICLR, 2017.
  * [39] Sara Hooker.  Moving beyond “algorithmic bias is a data problem”.  Patterns, 2021.
  * [40] Hongsheng Hu, Zoran Salcic, Gillian Dobbie, and Xuyun Zhang.  Membership inference attacks on machine learning: A survey.  arXiv preprint arXiv:2103.07853, 2021.
  * [41] Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou.  Approximate data deletion from machine learning models.  In AISTATS, 2021.
  * [42] Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li.  Manipulating machine learning: Poisoning attacks and countermeasures for regression learning.  In IEEE S&P, 2018.
  * [43] Sharu Theresa Jose and Osvaldo Simeone.  A unified pac-bayesian framework for machine unlearning via information risk minimization.  In ICML, 2021.
  * [44] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [45] Yiming Li, Baoyuan Wu, Yong Jiang, Zhifeng Li, and Shu-Tao Xia.  Backdoor learning: A survey.  arXiv preprint arXiv:2007.08745, 2020.
  * [46] Bo Liu, Ming Ding, Sina Shaham, Wenny Rahayu, Farhad Farokhi, and Zihuai Lin.  When machine learning meets privacy: A survey and outlook.  In ACM Computing Surveys, 2021.
  * [47] Yang Liu, Zhuo Ma, Ximeng Liu, Jian Liu, Zhongyuan Jiang, Jianfeng Ma, Philip Yu, and Kui Ren.  Learn to forget: Machine unlearning via neuron masking.  arXiv preprint arXiv:2003.10933, 2020.
  * [48] Ilya Loshchilov and Frank Hutter.  Sgdr: Stochastic gradient descent with warm restarts.  In ICLR, 2017.
  * [49] Preetum Nakkiran and Yamini Bansal.  Distributional generalization: A new kind of generalization, 2020.
  * [50] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari.  Learning with noisy labels.  NeurIPS, 2013.
  * [51] Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi.  Descent-to-delete: Gradient-based methods for machine unlearning.  In COLT, 2021.
  * [52] Curtis G. Northcutt, Anish Athalye, and Jonas Mueller.  Pervasive label errors in test sets destabilize machine learning benchmarks, 2021.
  * [53] Curtis G. Northcutt, Lu Jiang, and Isaac L. Chuang.  Confident learning: Estimating uncertainty in dataset labels.  In JAIR, 2021.
  * [54] Alexandra Peste, Dan Alistarh, and Christoph H Lampert.  Ssse: Efficiently erasing samples from trained machine learning models.  arXiv preprint arXiv:2107.03860, 2021.
  * [55] Vinay Uday Prabhu and Abeba Birhane.  Large image datasets: A pyrrhic win for computer vision?  In WACV, 2021.
  * [56] Sebastian Schelter.  ”amnesia” - machine learning models that can forget user data very fast.  In CIDR, 2020.
  * [57] Sebastian Schelter, Stefan Grafberger, and Ted Dunning.  Hedgecut: Maintaining randomised trees for low-latency machine unlearning.  In SIGMOD/PODS, 2021.
  * [58] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh.  Remember what you want to forget: Algorithms for machine unlearning.  In NeurIPS, 2021.
  * [59] Takashi Shibata, Go Irie, Daiki Ikami, and Yu Mitsuzumi.  Learning with selective forgetting.  In IJCAI, 2021.
  * [60] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In IEEE S&P, 2017.
  * [61] Connor Shorten and Taghi M Khoshgoftaar.  A survey on image data augmentation for deep learning.  Journal of Big Data, 2019.
  * [62] Liwei Song and Prateek Mittal.  Systematic evaluation of privacy risks of machine learning models.  In USENIX, 2021.
  * [63] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [64] Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, and Nicolas Papernot.  Unrolling sgd: Understanding factors influencing machine unlearning.  arXiv preprint arXiv:2109.13398, 2021.
  * [65] Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot.  On the necessity of auditable algorithmic definitions for machine unlearning.  arXiv preprint arXiv:2110.11891, 2021.
  * [66] Cheng-Hao Tsai, Chieh-Yen Lin, and Chih-Jen Lin.  Incremental and decremental training for linear classification.  In KDD, 2014.
  * [67] Matthew Turk and Alex Pentland.  Eigenfaces for recognition.  Journal of cognitive neuroscience, 1991.
  * [68] Enayat Ullah, Tung Mai, Anup Rao, Ryan Rossi, and Raman Arora.  Machine unlearning via algorithmic stability.  In COLT, 2021.
  * [69] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y. Zhao.  Neural cleanse: Identifying and mitigating backdoor attacks in neural networks.  In IEEE S&P, 2019.
  * [70] Alexander Warnecke, Lukas Pirch, Christian Wressnegger, and Konrad Rieck.  Machine unlearning of features and labels.  arXiv preprint arXiv:2108.11577, 2021.
  * [71] Yinjun Wu, Edgar Dobriban, and Susan B. Davidson.  Deltagrad: Rapid retraining of machine learning models.  In ICML, 2020.
  * [72] Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen.  Generative poisoning attack method against neural networks.  In Information & Security, 2020.
  * [73] Li Yang and Abdallah Shami.  On hyperparameter optimization of machine learning algorithms: Theory and practice.  Neurocomputing, 2020.
  * [74] Jason Yosinski, Jeff Clune, Thomas Fuchs, and Hod Lipson.  Understanding neural networks through deep visualization.  In ICML-W, 2015.
  * [75] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In CVPR, 2019.
  * [76] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In ICLR, 2017.
  * [77] Hattie Zhou, Ankit Vani, Hugo Larochelle, and Aaron Courville.  Fortuitous forgetting in connectionist networks.  arXiv preprint arXiv:2202.00155, 2022.

Abbr. | Definition
---|---
$T$ | The standard training procedure. Detailed in Appendix Section C.1.
$D$ | The entire training dataset.
$D_{f}$ | The samples to be removed, called the deletion set.
$D_{t}$ | Unseen (test set) samples from the same distribution (here, affected classes) as the deletion set.
$M$ | The original model, obtained from the training procedure $T$ using the entire train set $D$.
$M_{u}$ | The unlearnt model, obtained from applying some unlearning procedure on $M$.
$M_{r}$ | The retrained model, obtained from the same training procedure $T$ using the retained data $D\setminus D_{f}$.
$M_{u}^{\prime}$ | An unlearnt model aimed at achieving indistinguishability from the retrained model as in prior work.
$\phi_{u}$ | The distribution of models obtained from applying an unlearning procedure on the original model $M$.
$\phi_{r}$ | The distribution of models obtained by retraining from scratch, that is applying the same training procedure $T$ using the retain set $D\setminus D_{f}$.
$T^{\prime}$ | A modified version of the standard training procedure $T$.
$\phi^{\prime}_{r}$ | The distribution of models obtained by retraining but with a different training procedure $T^{\prime}$ using the retain set $D\setminus D_{f}$.
$P$ | Number of parts a data & influence isolation strategy divides the training data into. For more details see Section 2.2.1.
$Y$ | Number of parts of the training pipeline containing any influence of the dataset. For more details see Section 2.2.1.
$S$ | The subset of the original dataset $D$ selected for manipulations in unlearning testing.
$S^{\prime}$ | The manipulated version of the subset $S$.
$D^{\prime}$ | The modified training data after manipulating the subset $S$, formally $D\setminus S\cup S^{\prime}$. See Section 3.1 for more details.
$C^{M,S}_{i,j}$ | The cell in the $i^{th}$ row and $j^{th}$ column of the confusion matrix obtained by applying model $M$ to labeled data $S$.
$S_{C}$ | Samples of class $C$ in a dataset $S$.
$A,B$ | The confused classes in the IC test.
$N$ | The number of classes confused. See Section 3.1.1 for more details.
$n$ | The size of the deletion set to be chosen.

Table 7: Reference for notations used in this work

Abbr. | Definition | Ref. in Section
---|---|---
IC | Interclass Confusion test | 3.1, 4.1.
RC | Random Confusion test | 3.1.2, 4.1.
RS | Random Samples test | 4.1.
CR | Class Removal test | 4.1.
pCR | Partial Class Removal test | 4.1.
FCR | Full Class Removal test | 4.1.
Fgt | Forgetting Score metric | 3.1.1.
Err | Error metric | 3.1.1
MIA | Membership Inference Attack(s) | 3.1.1, App. Sec. 2.
CoMI | Confidence-based Membership Inference attack | 3.1.1, App. Sec. 2.
CF-$k$ | Catastrophic-Forgetting $k$ layers | 3.2.
EU-$k$ | Exact-Unlearning $k$ layers | 3.2.
DNN | Deep Neural Network |
i.i.d | Independent and identically distributed |
NTK-F | Neural Tangent Kernel + Fisher method |
stdev | Standard Deviation |

Table 8: Reference for abbreviations used in this work

In the appendix, we provide additional information and experiments to
supplement the observations in the main paper. The appendix is organized
sectionwise as follows:

  1. (A)

We detail all notations and abbreviations used in the main paper.

  2. (B)

We provide additional background and analysis on data isolation strategies,
membership inference attacks and how unlearning methods might require the
capability to learn.

  3. (C)

We provide details of implementation, test and metric choices, unlearning
method comparisons and utility calculations.

  4. (D)

We show empirical results on varying the number of unlearning epochs, layers
in the architecture and samples to be deleted. We also vary the choice of
confused classes and ablate the effect of warm restarts in our training
procedure. These results demonstrate the robustness of our observations.

##  Appendix A References: Notations and Abbreviations

In Tables 7 and 8 we list the notations and terms used in this work
respectively for reference when reading the paper.

##  Appendix B Additional Analysis

###  B.1 Against Isolation Strategies

Isolation-based strategies change the training process by creating an ensemble
[56, 12, 32, 37], each of whose models is trained on different subsets of the
dataset. This ensures architecturally [12, 6, 56] or temporally [37, 12]
isolating the influence of any sample to a limited part of training, requiring
retraining for only the affected parts. Isolation has been used across
techniques like Linear Classification [6], Random Forest [57, 14], KNN [1],
SVM [17, 66] and DNN [32, 12, 37] by utilizing or creating a sparse influence
graph [56]. Data-influence isolation often comes at the cost of utility as
each portion becomes a weaker learner [9], especially in deep networks [61].
To overcome the dropping utility, the training and unlearning time may need to
be increased, reducing resource efficiency.

We also show that the probability of full-retrain in data-influence isolation
unlearning methods scales poorly with increasing deletion set size. Let $p(n)$
be the probability that all $P$ portions are affected on the removal of $n$
samples. Extending the analysis of Warnecke et. al. [70] from the specific
case of SISA to data-influence isolation in general, we get:

$p(n)=1-\frac{\sum_{j=1}^{k}(-1)^{j+1}\binom{|P|}{j}(|P|-j)^{n}}{|P|^{n}}$

Figure 4 shows $p(|D_{f}|)$ grows logistically, implying there is a fast
increase in the chance of needing a full-retrain as deletion sets get larger.
This demonstrates how data-influence isolation provides little improvement in
efficiency compared to the retrain-from-scratch baseline for practical
scenarios.

Figure 4: Logistic growth of the probability of needing to retrain all
portions with increasing deletion set size. We represent isolation strategies
with different portion sizes $P$.

###  B.2 Membership Inference Attacks

####  B.2.1 Background

Membership Inference Attacks (MIA) [60] can be used to determine whether a
particular sample was part of the training data of a model. Many different
black-box formulations of MIA have been used to measure the efficacy of
unlearning. Most [31, 29, 47, 32] learn a binary attack classifier: based on
the model’s output for the sample, was the sample in the seen training set
(class 0) or the unseen test set (class 1)? The attack classifier is then
applied on deletion set samples, with ideal unlearning entailing all samples
are classified as unseen. However, such a test is extremely sensitive to the
efficacy of the attack classifier which may be unreliable. Another approach
has been to train the attack classifier to distinguish the outputs of a large
number of original ($M$) and retrained ($M_{r}$) models and then classify the
unlearnt model $M_{u}$ [11]. This formulation involves prohibitive
computational expense and applies only when using the problematic
indistinguishability definition.

Song et. al. [62] recently show that _metric-MIA_ , measuring simple metrics
and deciding membership based on a threshold, can match the classification
accuracy of trained attack models. In particular, their confidence-based MIA
measures the model’s output probability for the target class and selecting
separate class-wise membership thresholds. It is shown to match the
performance of even white-box MIA attack classifiers.

####  B.2.2 Our Formulation

We adapt the confidence-based MIA [62] to propose an efficient black-box MIA
formulation specifically tailored for measuring forgetting. We assume direct
access to the actual model outputs instead of shadow models [32, 47], as
shadow models only weaken the attack, making the unlearning test artificially
easier to pass. We distinguish the model outputs on samples from the deletion
set $D_{f}$ and unseen samples $D_{t}$ from the same underlying distribution
rather than training an attack classifier using the entire train and test set.
We believe this formulation gives a more targeted measurement of forgetting as
it directly discriminates between outputs on $D_{f}$ and $D_{t}$ in contrast
to train and test set used in past literature [31, 29, 32, 47].

Our MIA takes in model $M$, forget set $D_{f}$ and unseen samples $D_{u}$ from
the same classes found in $D_{f}$. The following procedure is repeated for
each ’target class’ $t$:

  * •

Dataset $D_{MIA}$ is created with the probability outputs for class $t$:
$M(D_{f})_{t}$ and $M(D_{u})_{t}$ stored as class 0 and class 1 respectively.

  * •

We then create a 50-50555Given that only 1 parameter (threshold) needs to be
learnt, the shadow size is sufficient shadow ($D_{MIA-S}$) - test
($D_{MIA-T}$) split of $D_{MIA}$.

  * •

A threshold $p_{t}$ needs to be chosen such that probabilities $>p_{t}$ are
classified as class 0, and probabilities $<p_{t}$ as class 1. The $p_{t}$ that
maximizes the accuracy on $D_{MIA-S}$ is chosen.

  * •

The accuracy obtained on $D_{MIA-T}$ using threshold $p_{t}$ is the MIA
accuracy for target class $t$. A weighted average of this test accuracy across
all target classes is taken as the final MIA accuracy.

Usually, the target class $t$ is the actual label of the sample. However, in
the case of IC test, we use the mislabelled class as the target for both,
$D_{f}$ and $D_{u}$ samples. Intuitively, the memorization of mislabels in the
deletion set would make the wrong class probability output unnaturally higher
than other unseen samples of the same class, making the MIA stronger. Such an
enhancement is not possible in the case of $RC$ as the mislabels are
untargeted.

In line with existing MIA literature, we want our attack classifier accuracy
to be 50% incase of no classifier advantage. Thus as the forget set and unseen
set may have differing sizes in some experiments, we take a random subset of
the larger one to make the attack dataset balanced. The numbers reported are
averaged over 20 runs with randomness induced by the subset sampling step.
Note that since the classifier learns to distinguish between the test and
forget set distribution directly, it might be able to distinguish them
spuriously, leading to slightly more than 50% attack classifier accuracy even
on perfect unlearning. Thus, the reference gold standard MIA performance can
instead be that of any exactly unlearnt model upon undergoing the same
evaluation.

###  B.3 Unlearning Can Require Learning

Most unlearning definitions allow the choice of any deletion set $D_{f}$, and
indeed an ideal unlearning procedure should be able to remove any data. The IC
test creates a scenario that fits this definition while being difficult to
handle. Note that the IC test is applicable irrespective of the number of
classes in the dataset. The only difference is that when a larger number of
classes is used, the original model will have more clean classes to learn from
leading to more meaningful representations. If metrics are computed only on
the affected classes, the IC tests will continue to provide clear trends for
forgetting.

We find it insightful to consider the extreme case of binary classification.
If we apply the IC test with half the samples of each class mislabelled as the
other, the training set of the original model $M$ becomes completely randomly
labelled. Thus, the original model has no information to learn.

Now, if we delete all the mislabelled samples, we are left with 50% of the
clean training set. Perfect unlearning would solely remove the confusing
influence of the mislabelled data while learning a useful classifier from the
informative clean data. Indeed, the retrain model $M_{r}$ trained on
$D\setminus D_{f}$ would learn meaningful representations with decent
accuracy. Thus, in some scenarios the unlearnt model can have more meaningful
information than the original model. This entails that the unlearning
procedures we design need to have a capacity to learn as in the case of EU-$k$
and CF-$k$. This is a significant difficulty for methods that attempt to
unlearn without any underlying learning of the retain set. If unlearning
scenarios like these which might require learning are beyond the scope of an
unlearning procedure, there is a need to explicitly state restrictions on the
definitions adopted. We hope our work spurs the important discussion of how
unlearning might need learning. Conversely, recent parallel work [77] claims
that forgetting helps improve subsequent learning. We believe the relationship
between forgetting and learning forms an intriguing direction for future work.

##  Appendix C Additional Details

We now provide some additional details for results shown in the main paper.

###  C.1 Implementation Details

We use CIFAR10 and CIFAR100 datasets with a 40,000-10,000-10,000 train-valid-
test split.

We use the ResNet architecture [36] with 110 layers. Our standard training
procedure $T$ is the following: We train our models initialized as Kaiming
Normal [35] for 62 epochs (CIFAR10) or 126 epochs (CIFAR100), using a SGD
optimizer with momentum 0.9 and weight decay 5e-5, an SGDR [48] scheduler with
$t_{mult}$ = 2, $t_{0}$ = 1, minlr = 5e-3, maxlr = 0.01 and a batch size of
64. For EU-$k$ and CF-$k$ we use the same choices described above, but on the
final $k$ layers. In CF-$k$, we finetune for only half the epochs to obtain a
two-fold speedup over EU-$k$. The choices made specific to the different
evaluation methods are highlighted in Sections B.2.2, C.3.

The setup used for all experiments is a PC with a Intel(R) Xeon(R) E5-2640
2.40 GHz CPU, 128GB RAM and 1 GeForce RTX 2080 GPU.

We make the following deviations in our experiments:

  * •

In Table 6 we make changes described in Section C.4.

  * •

In Tables 5 and 10 we change the training procedure. When using cutmix
regularization, we use $p=0.5$ and $\alpha=1.0$. For early stopping, we halve
the number of epochs both while training the original/retrain models and also
in the unlearning procedures.

  * •

In Table 11 we vary the number of finetuning epochs in CF-$k$.

  * •

In Table 16 we vary the confused classes in the IC test from easy-hard on the
axis of distinguishability.

  * •

In Figure 5 we further benchmark on ResNet-20, ResNet-56 and ResNet-110 to
show our results are robust to the choice of network depths.

  * •

In Table 17 we ablate the effect of warm restarts in training the
original/retrain model.

###  C.2 Metrics

####  C.2.1 On the Metric Comparisons Table

Note that the list of metrics in Table 1 of the main paper does not include
metrics like upper bound on information remaining in weights and activations
[30, 31, 29] since its unclear whether such metrics can be computed on methods
other than their own proposed unlearning procedure. We also exclude purely-
qualitative tests such as model inversion attacks [24] which have been used in
prior unlearning works [32, 11].

####  C.2.2 Details of Metric Computation

For clarity, we further describe the computation of some metrics. CoMI has
already been described in Appendix Section B.2. Note that for measuring
memorization, the deletion set is used, while for measuring generalization (a
subset of) the test set is used.

IC-Fgt: For the IC test between class $A$ and $B$, the forgetting score
represents the number of samples of class $A$ mislabelled as class $B$ and
vice-versa. Intuitively, as the mislabelled samples are forgotten by the
unlearning procedure, the model should confuse lesser samples between these
two classes.

CR-Fgt: For the CR test removing samples from class $C$, the forgetting score
represents the number of samples the model classifies as class $C$.
Intuitively, as more samples from $C$ are removed, the model should classify
lesser samples into $C$. Note that if the entire class is not removed, a model
that generalizes better from the partial samples still available may get
penalized unnecessarily.

IC-Err: Error on unseen samples from the confused classes of the IC test, $A$
and $B$.

CR-Err: Error on unseen samples of the removed class $C$.

RC, RS-Err: Error on all samples from the test set. Here, a specific set of
classes cannot be used for a targeted measurement.

Method |  | RS ($\downarrow$) | CR ($\downarrow$) | RC ($\downarrow$) | IC ($\downarrow$)
---|---|---|---|---|---
CIFAR-10 ($|D_{f}|=4000$)
Original |  | 8.4 $\pm$ 0.2 | 8.8 $\pm$ 0.4 | 14.3 $\pm$ 0.7 | 6.9 $\pm$ 0.5
1-layer | CF | 8.4 $\pm$ 0.1 | 8.3 $\pm$ 0.2 | 13.0 $\pm$ 0.9 | 6.5 $\pm$ 0.5
EU | 8.5 $\pm$ 0.1 | 8.4 $\pm$ 0.3 | 12.8 $\pm$ 0.9 | 6.6 $\pm$ 0.3
10-layers | CF | 8.4 $\pm$ 0.2 | 8.4 $\pm$ 0.2 | 12.0 $\pm$ 0.6 | 6.5 $\pm$ 0.4
EU | 8.7 $\pm$ 0.1 | 8.6 $\pm$ 0.2 | 12.0 $\pm$ 0.7 | 6.7 $\pm$ 0.2
50-layers | CF | 8.5 $\pm$ 0.1 | 8.1 $\pm$ 0.4 | 10.0 $\pm$ 0.4 | 6.1 $\pm$ 0.3
EU | 9.3 $\pm$ 0.3 | 8.8 $\pm$ 0.4 | 10.4 $\pm$ 0.4 | 6.9 $\pm$ 0.5
Retrain |  | 9.3 $\pm$ 0.1 | 8.2 $\pm$ 0.3 | 8.8 $\pm$ 0.3 | 6.4 $\pm$ 0.2
CIFAR-100 ($|D_{f}|=400$)
Original |  | 32.1 $\pm$ 1.1 | 31.6 $\pm$ 1.1 | 32.4 $\pm$ 1.4 | 31.8 $\pm$ 0.8
1-layer | CF | 32.1 $\pm$ 1.0 | 31.7 $\pm$ 1.2 | 32.4 $\pm$ 1.3 | 31.7 $\pm$ 0.7
EU | 32.1 $\pm$ 1.0 | 31.7 $\pm$ 1.1 | 32.4 $\pm$ 1.2 | 31.8 $\pm$ 0.7
10-layers | CF | 32.4 $\pm$ 0.9 | 32.2 $\pm$ 1.1 | 32.6 $\pm$ 1.3 | 32.0 $\pm$ 0.6
EU | 33.3 $\pm$ 1.2 | 32.5 $\pm$ 1.1 | 33.3 $\pm$ 1.2 | 32.8 $\pm$ 0.9
50-layers | CF | 31.7 $\pm$ 0.9 | 31.5 $\pm$ 1.0 | 31.8 $\pm$ 0.8 | 31.2 $\pm$ 0.6
EU | 32.1 $\pm$ 0.3 | 31.6 $\pm$ 0.2 | 31.8 $\pm$ 1.0 | 31.7 $\pm$ 1.0
Retrain |  | 32.2 $\pm$ 0.4 | 31.6 $\pm$ 0.6 | 31.7 $\pm$ 1.3 | 31.8 $\pm$ 1.0

Table 9: Error on the retain set distribution of test samples across
unlearning tests. Scores are reported as: mean $\pm$ stdev. The EU-$k$ and
CF-$k$ unlearning procedures lead to a minimal change in utility compared to
retraining from scratch, unless utility is correlated with unlearning in the
applied test.

Method |  | None | Early Stop | Cutmix | Cutmix+Early
---|---|---|---|---|---
CIFAR-10 ($|D_{f}|=4000$)
Original |  | 6.53 | 7.91 | 5.81 | 8.02
10-layers | CF | 6.11 | 7.93 | 5.45 | 7.27
EU | 6.55 | 7.88 | 5.68 | 7.08
50-layers | CF | 5.75 | 7.31 | 5.32 | 6.75
EU | 6.57 | 7.87 | 6.16 | 8.20
Retrain |  | 6.31 | 8.50 | 5.70 | 8.97
CIFAR-100 ($|D_{f}|=400$)
Original |  | 32.53 | 33.10 | 27.26 | 30.03
10-layers | CF | 32.22 | 33.04 | 27.98 | 30.61
EU | 33.25 | 33.23 | 28.59 | 31.23
50-layers | CF | 30.93 | 32.37 | 27.92 | 29.37
EU | 31.98 | 33.66 | 30.41 | 30.93
Retrain |  | 30.64 | 32.62 | 26.67 | 30.67

Table 10: Error on the retain set distribution of test samples on varying the
training procedure of the original model. Regularized models have better
utility even after unlearning.

In Table 9 we show the utilities of the EU-$k$ and CF-$k$ unlearning
procedures across all four tests. We observe a negligible impact on utility
compared to retraining from scratch, unlike most unlearning procedures
suggested in existing literature. The only significant difference in error is
observed in the RC test, where better unlearning leads to improved utility as
the model gets less confused by the mislabelled samples. Note that this is not
observed in the IC test as the error is reported on only the unaffected
classes, where error is independent of unlearning. Thus, EU-$k$ and CF-$k$ can
be used to control the unlearning-efficiency tradeoff at a fixed utility.

###  C.3 Choices for Tests

In the IC test we confuse samples between classes 3 (Cat) and 5 (Dog) on
CIFAR10 and classes 47 (Maple Tree) and 52 (Oak Tree) on CIFAR100 unless
otherwise specified. The deletion set size is the same as the number of
samples from one class in the training set. Note that while the size of
$D_{f}$ is the same when comparing different tests, the size of $D_{t}$ is
dependent on the test itself. In targeted tests (CR, IC), $D_{t}$ only has
test set samples from the affected classes, whereas in untargeted tests (RS,
RC) $D_{t}$ consists of the entire test set. In CR test we remove class 0 for
both CIFAR10 and CIFAR100, whereas in RS and RC we draw an equal number of
samples randomly from each class.

###  C.4 Details of Comparison with Golatkar et. al.

For comparisons with Golatkar et. al., we use their code, dataset and training
procedure. The only change we make is using the ResNet-20 architecture as is
standard for CIFAR10 to obtain results of both their and our procedures.
Golatkar et. al. benchmark on a subset of 500 images (100 each from 5 classes)
of CIFAR10, which they call Small-CIFAR5. We tried benchmarking their
unlearning procedure on models obtained using our training procedure, but
possibly due to the violation of some of their training assumptions, we
obtained models with near-random performance.

Method | Epochs | Mem | Prop. Gen. | Test-Err
---|---|---|---|---
|  | (Fgt) | (Fgt) |
CIFAR10
Original | - | 3016.0 | 927.0 | 16.00
CF-10 | 6 | 1453 | 408 | 11.07
14 | 1305 | 366 | 10.63
30 | 1226 | 335 | 10.24
CF-50 | 6 | 758 | 251 | 9.42
14 | 643 | 241 | 9.17
30 | 569 | 229 | 9.25
Retrain | 62 | 390 | 184 | 9.33
CIFAR100
Original | - | 395 | 70 | 32.53
CF-10 | 6 | 357 | 56 | 32.71
14 | 348 | 55 | 32.60
30 | 337 | 54 | 32.98
62 | 325 | 57 | 32.60
CF-50 | 6 | 128 | 47 | 32.88
14 | 141 | 45 | 32.12
30 | 108 | 47 | 32.11
62 | 86 | 36 | 31.92
Retrain | 126 | 64 | 31 | 30.82

Table 11: Varying catastrophic forgetting epochs on the IC test. The number of
epochs used for fine-tuning can further control the forgetting-efficiency
tradeoff without hurting utility.

###  C.5 Utilities

To measure utility, we compute error on unseen samples from the same
distribution as $D\setminus D_{f}$, called the retain distribution. For the RS
and RC tests, as the removal is untargeted, the evaluated samples are the same
as the full test set. For the CR and RC tests the evaluated samples consist of
test set samples from the unaffected classes. This is done as error on samples
from the deletion set distribution correlates with the unlearning efficacy,
and thus removing them leads to a measurement of utility independent of
unlearning.

In Table 10 we show the impact of regularization on utility. We observe that
early stopping slightly increases the errors, while cutmix alone reduces them
especially in CIFAR100. Given the significant improvement in utility and
greater downstream amenability to unlearning, using regularizers like Cutmix
seems highly rewarding. Our unlearning procedures do not decrease the utility
barring a slight deterioration when the training procedure uses cutmix while
the unlearning procedure does not.

(a) Model: ResNet-20 Dataset: CIFAR10

(b) Model: ResNet-20 Dataset: CIFAR100

(c) Model: ResNet-56 Dataset: CIFAR10

(d) Model: ResNet-56 Dataset: CIFAR100

(e) Model: ResNet-110 Dataset: CIFAR10

(f) Model: ResNet-110 Dataset: CIFAR100

Figure 5: Variation in forgetting efficacy across number of layers unlearnt
using CF-$k$ and EU-$k$. The annotations represent
(Memorization$|$Generalization) based on the IC test forgetting score. Most
information is present in the final layers of the network, and applying
unlearning to the earlier half of the network provides negligible benefits.
CF-$k$ consistently performs close to EU-$k$.

Method |  | Err ($\uparrow\downarrow$) | CoMI ($\downarrow$)
---|---|---|---
|  | 400 | 2K | 8K | 20K | 400 | 2K | 8K | 20K
CIFAR10
Original |  | 0.5$|$8.3 | 0.1$|$8.5 | 0.1$|$8.3 | 0.2$|$8.7 | 56.8 | 55.9 | 55.7 | 56.2
10-layers | CF | 0.2$|$8.4 | 0.3$|$8.7 | 0.3$|$8.1 | 0.4$|$8.9 | 57.1 | 55.3 | 55.1 | 55.6
EU | 0.2$|$8.3 | 0.8$|$8.6 | 0.4$|$8.2 | 0.7$|$8.9 | 56.4 | 54.2 | 54.9 | 55.4
50-layers | CF | 4.0$|$8.5 | 4.0$|$8.8 | 3.1$|$8.2 | 4.8$|$9.7 | 51.3 | 52.0 | 52.3 | 52.6
EU | 7.0$|$8.2 | 6.5$|$8.7 | 6.0$|$8.7 | 10.1$|$11.1 | 50.3 | 50.4 | 50.8 | 50.3
Retrain |  | 8.8$|$8.4 | 9.6$|$9.1 | 10.2$|$9.4 | 14.6$|$14.1 |  $<$50 |  $<$50 |  $<$50 |  $<$50
CIFAR100
Original |  | 0.0$|$32.8 | 0.2$|$32.3 | 0.1$|$31.4 | 0.1$|$32.6 | 57.9 | 68.6 | 70.3 | 70.6
10-layers | CF | 1.5$|$33.3 | 1.4$|$32.9 | 1.1$|$31.6 | 2.1$|$33.8 | 53.2 | 63.5 | 66.3 | 66.3
EU | 7.5$|$34.3 | 5.1$|$33.2 | 3.5$|$32.2 | 9.2$|$34.8 | 54.9 | 61.3 | 64.3 | 62.2
50-layers | CF | 25.2$|$32.7 | 21.9$|$32.3 | 20.5$|$31.6 | 23.2$|$34.6 | 48.9 | 51.9 | 53.8 | 54.9
EU | 34.8$|$32.1 | 35.9$|$32.6 | 32.8$|$33.3 | 40.9$|$40.4 | 45.6 | 47.8 | 49.7 | 50.3
Retrain |  | 32.5$|$30.7 | 35.9$|$33.0 | 37.4$|$35.3 | 43.6$|$42.3 | 44.5 | 48.5 | 49.0 | 49.9

Table 12: Varying $|D_{f}|$ for RS test. Results are reported as
Memorization$|$Property Generalization. Error seems to distinguish varying
levels of unlearning, but needs huge deletion sets in the case of property
generalization. Moreover, here error has the limitation of misaligning
forgetting ($\uparrow$) and utility ($\downarrow$).

Method |  | Err ($\downarrow$) | CoMI ($\downarrow$)
---|---|---|---
|  | 400 | 2K | 8K | 20K | 400 | 2K | 8K | 20K
CIFAR10
Original |  | 92.5$|$9.5 | 73.5$|$12.1 | 48.5$|$19.8 | 36.2$|$27.8 |  $<$50 | 50.0 |  $<$50 |  $<$50
10-layers | CF | 54.2$|$9.3 | 37.4$|$10.7 | 30.5$|$14.6 | 28.9$|$23.9 |  $<$50 |  $<$50 |  $<$50 |  $<$50
EU | 40.0$|$9.4 | 33.5$|$10.5 | 29.0$|$14.9 | 28.5$|$23.4 |  $<$50 |  $<$50 |  $<$50 |  $<$50
50-layers | CF | 13.6$|$8.8 | 11.5$|$9.2 | 12.5$|$11.0 | 17.0$|$16.4 |  $<$50 |  $<$50 | 50.0 |  $<$50
EU | 6.9$|$9.3 | 10.7$|$9.7 | 11.6$|$11.6 | 16.4$|$15.9 |  $<$50 |  $<$50 |  $<$50 | 50.0
Retrain |  | 5.8$|$8.2 | 8.5$|$8.6 | 9.5$|$9.5 | 12.9$|$12.8 |  $<$50 |  $<$50 | 50.0 | 50.0
CIFAR100
Original |  | 99.8$|$31.8 | 99.4$|$36.9 | 97.7$|$52.1 | 94.3$|$72.9 |  $<$50 |  $<$50 |  $<$50 |  $<$50
10-layers | CF | 82.8$|$32.1 | 71.7$|$35.7 | 67.7$|$44.7 | 71.6$|$60.5 |  $<$50 |  $<$50 |  $<$50 |  $<$50
EU | 69.2$|$33.1 | 61.0$|$36.2 | 60.7$|$44.3 | 66.1$|$58.1 |  $<$50 |  $<$50 |  $<$50 |  $<$50
50-layers | CF | 35.5$|$31.5 | 36.5$|$33.0 | 40.8$|$38.3 | 51.7$|$49.7 |  $<$50 |  $<$50 |  $<$50 | 50.5
EU | 30.5$|$32.0 | 33.0$|$32.0 | 38.0$|$37.0 | 47.4$|$46.2 |  $<$50 |  $<$50 |  $<$50 | 50.1
Retrain |  | 31.2$|$30.8 | 34.0$|$32.7 | 36.2$|$35.4 | 43.1$|$41.5 |  $<$50 |  $<$50 |  $<$50 |  $<$50

Table 13: Varying $|D_{f}|$ for RC test. Results are reported as
Memorization$|$Property Generalization. Error reliably measures memorization
even in small deletion sets, though larger ones are needed to produce
detectable effects on property generalization.

Method |  | Fgt ($\downarrow$) | Err ($\downarrow$) | CoMI ($\downarrow$)
---|---|---|---|---
CIFAR-10 |
$|D_{f}|\rightarrow$ |  | 400 | 1K | 2K | 4K | 400 | 1K | 2K | 4K | 400 | 1K | 2K | 4K
Original |  | 348$|$211 | 854$|$300 | 1721$|$513 | 3016$|$927 | 88.8$|$19.8 | 88.3$|$24.7 | 85.0$|$34.2 | 76.6$|$53.9 | 91.4 | 86.2 | 80.6 | 66.1
10-layers | CF | 247$|$181 | 543$|$235 | 1003$|$306 | 1226$|$335 | 63.2$|$18.4 | 54.8$|$22.6 | 50.6$|$25.1 | 30.9$|$26.8 | 83.9 | 76.9 | 71.8 | 58.7
EU | 209$|$181 | 487$|$233 | 920$|$296 | 1165$|$352 | 55.8$|$18.3 | 49.9$|$22.4 | 48.9$|$25.2 | 28.9$|$27.0 | 78.8 | 75.6 | 70.5 | 59.1
50-layers | CF | 69$|$158 | 187$|$186 | 302$|$181 | 569$|$229 | 24.5$|$16.6 | 22.4$|$18.2 | 21.4$|$19.1 | 20.1$|$23.2 | 64.8 | 59.9 | 58.5 | 54.2
EU | 55$|$179 | 124$|$175 | 216$|$182 | 453$|$195 | 17.5$|$17.0 | 18.8$|$17.4 | 18.5$|$19.4 | 23.0$|$23.0 | 53.3 | 55.0 | 53.2 | 53.2
Retrain |  | 41$|$164 | 92$|$183 | 176$|$185 | 390$|$184 | 17.0$|$16.4 | 17.3$|$19.1 | 19.1$|$20.4 | 22.2$|$21.4 | 50.2 | 52.3 | 52.2 | 52.0
CIFAR-100 |
$|D_{f}|\rightarrow$ |  | 40 | 100 | 200 | 400 | 40 | 100 | 200 | 400 | 40 | 100 | 200 | 400
Original |  | 40$|$37 | 99$|$39 | 196$|$46 | 395$|$70 | 100.0$|$37.0 | 99.0$|$40.0 | 97.0$|$43.0 | 100.0$|$57.0 | 88.2 | 88.5 | 85.6 | 86.4
10-layers | CF | 35$|$32 | 81$|$41 | 152$|$35 | 325$|$57 | 90.0$|$35.5 | 81.0$|$41.5 | 78.0$|$38.5 | 85.8$|$51.0 | 86.5 | 83.8 | 78.9 | 79.0
EU | 28$|$33 | 61$|$33 | 124$|$40 | 290$|$60 | 80.0$|$39.0 | 72.0$|$38.0 | 68.0$|$41.5 | 76.8$|$53.0 | 86.4 | 78.9 | 76.0 | 72.1
50-layers | CF | 5$|$36 | 19$|$37 | 37$|$28 | 86$|$36 | 20.0$|$40.0 | 37.0$|$36.5 | 37.0$|$38.5 | 41.8$|$44.5 | 55.1 | 64.4 | 56.3 | 59.0
EU | 3$|$32 | 11$|$34 | 31$|$32 | 49$|$37 | 32.5$|$36.5 | 34.0$|$41.0 | 38.5$|$37.0 | 40.5$|$44.5 |  $<$50 | 52.4 | 55.4 | 52.0
Retrain |  | 3$|$30 | 10$|$30 | 29$|$24 | 64$|$31 | 35.0$|$35.5 | 39.0$|$36.0 | 31.5$|$32.5 | 39.0$|$39.5 |  $<$50 | 52.7 |  $<$50 | 53.0

Table 14: Varying $|D_{f}|$ for IC test. Results are reported as
Memorization$|$Property Generalization. In CIFAR10, at 10% of the class size,
the IC test reliably detects imperfect forgetting across metrics. In CIFAR100,
imperfect removal of memorization is detected at 10% of the class size, a
noticeable effect on generalization requires a larger deletion set.

##  Appendix D Additional Experiments

Finally, we vary some of the choices we make in our experiments to demonstrate
the robustness of our observations.

###  D.1 Varying the number of unlearning epochs

The original experiments train CF-$k$ models for half the epochs compared to
EU-$k$ models. In Table 11 we compare the variation of performance among
CF-$k$ models at the end of each warm restart while finetuning. While less
information is unlearnt on reducing epochs, even six epochs are sufficient for
drastic improvements in forgetting, with no significant change in utility
(error on full test set). The number of catastrophic forgetting epochs can
thus be reduced, and control the forgetting-efficiency tradeoff.

###  D.2 Varying the number of layers

In Figure 5 we show results of varying $k$ for 3 different ResNet depths: 20,
56 and 110. The IC test is able to detect retained information despite exact
unlearning of 3̃0% of the final layers. However, on unlearning the final half
of the network, its unclear whether most information is removed or the IC test
is unable to identify the presence of retained information. CF-$k$ is
consistently within a small margin of EU-$k$ demonstrating the catastrophic
forgetting is able to lose enough information to match EU while being two
times faster.

Method |  | Fgt ($\downarrow$) | Err ($\uparrow\downarrow$) | CoMI ($\downarrow$)
---|---|---|---|---
CIFAR-10 |
$|D_{f}|\rightarrow$ |  | 400 | 1K | 2K | 4K | 400 | 1K | 2K | 4K | 400 | 1K | 2K | 4K
Original |  | 400$|$1054 | 999$|$1022 | 1997$|$1017 | 3994$|$997 | 0.0$|$4.9 | 0.2$|$6.7 | 0.1$|$7.2 | 0.1$|$7.8 | 57.8 | 55.6 | 54.9 | 54.7
10-layers | CF | 398$|$997 | 997$|$1004 | 1990$|$965 | 195$|$34 | 0.2$|$7.4 | 0.4$|$7.0 | 0.7$|$10.2 | 95.5$|$96.6 | 58.3 | 54.8 | 54.5 | 58.5
EU | 400$|$1039 | 993$|$989 | 1987$|$978 | 0$|$0 | 0.2$|$5.3 | 1.3$|$8.4 | 0.9$|$10.0 | 100.0$|$100.0 | 54.6 | 54.7 | 54.8 | 62.8
50-layers | CF | 391$|$995 | 944$|$966 | 1869$|$969 | 0$|$0 | 2.5$|$7.6 | 5.7$|$9.8 | 6.0$|$10.3 | 100.0$|$100.0 | 53.1 | 51.4 | 50.5 | 57.5
EU | 383$|$999 | 944$|$999 | 1784$|$947 | 0$|$0 | 6.2$|$8.5 | 6.2$|$8.2 | 11.2$|$12.2 | 100.0$|$100.0 | 51.3 | 50.2 |  $<$50 | 62.1
Retrain |  | 373$|$1004 | 899$|$995 | 1745$|$943 | 0$|$0 | 6.2$|$7.8 | 9.6$|$7.8 | 13.2$|$12.2 | 100.0$|$100.0 | 50.4 |  $<$50 |  $<$50 | 61.8
CIFAR-100 |
$|D_{f}|\rightarrow$ |  | 40 | 100 | 200 | 400 | 40 | 100 | 200 | 400 | 40 | 100 | 200 | 400
Original |  | 40$|$103 | 100$|$100 | 200$|$106 | 399$|$98 | 0.0$|$11.0 | 0.0$|$13.0 | 0.0$|$12.0 | 0.0$|$14.0 |  $<$50 | 60.0 | 60.1 | 65.0
10-layers | CF | 40$|$90 | 99$|$97 | 197$|$96 | 0$|$0 | 0.0$|$16.0 | 1.0$|$15.0 | 4.0$|$15.0 | 100.0$|$100.0 | 55.5 | 57.6 | 56.7 | 62.4
EU | 39$|$92 | 97$|$93 | 193$|$97 | 0$|$0 | 5.0$|$17.0 | 4.0$|$19.0 | 4.0$|$15.0 | 100.0$|$100.0 | 50.3 | 59.6 | 56.5 | 55.1
50-layers | CF | 37$|$101 | 90$|$103 | 172$|$92 | 0$|$0 | 5.0$|$11.0 | 13.0$|$12.0 | 17.0$|$18.0 | 100.0$|$100.0 |  $<$50 |  $<$50 | 52.3 | 57.7
EU | 35$|$95 | 81$|$86 | 166$|$85 | 0$|$0 | 15.0$|$15.0 | 22.0$|$19.0 | 17.0$|$19.0 | 100.0$|$100.0 |  $<$50 |  $<$50 | 50.1 | 58.5
Retrain |  | 34$|$97 | 82$|$93 | 159$|$89 | 0$|$0 | 15.0$|$15.0 | 20.0$|$17.0 | 22.0$|$18.0 | 100.0$|$100.0 |  $<$50 |  $<$50 |  $<$50 | 63.5

Table 15: Varying $|D_{f}|$ for CR test. Results are reported as
Memorization$|$Property Generalization. The CR test is not able to reliably
distinguish varying levels of property generalization and provides a weak
signal for memorization, particularly for small $|D_{f}$

###  D.3 Varying Amount of Untargeted Removal

In Tables 12 and 13, we show the forgetting performance when we vary deletion
set sizes in tests with untargeted removal, RS and RC. Here, we use larger
sizes than those reported in the main paper as smaller deletion sets show
negligible trends in untargeted removal. For detecting effects on property
generalization, Err on RC test needs far fewer samples than Err on RS. For
memorization, we see that Err is able to distinguish and rank models fairly
well whereas CoMI works well in the case of RS test but fails completely on
the RC test. CF models continue to be close to EU models here and the gap
between them decreases as we add more confusion. Overall, untargeted removal
requires much larger deletion sets to show clear forgetting trends as compared
to targeted removal, demonstrating the usefulness of strategic sampling.

###  D.4 Varying Amount of Targeted Removal

Now, we study the forgetting performance for partial Class Removal (pCR) and
partial Interclass Confusion. We show results for varying $|D_{f}|$ from 10%
samples of a class to the size of an entire class (as used in the original
paper).

First, we present the results of the IC test in Table 14. We see that for
memorization (left of $|$) all metrics are reflective even when a very small
subset of samples is confused. Err and CoMI having increasingly better
contrast for smaller deletion sets. In contrast, Fgt works consistently well
across all deletion set sizes with roughly similar amplitudes of differences.
For property generalization (right of $|$), we have somewhat but not
substantially weaker trend in error as compared to Fgt as sample sizes
decrease. Both are able to reflect trends in unlearning property
generalization.

Then, we present the results of the CR test in Table 15. The CR test has
significantly different behavior when all samples of the class are removed
(FCR) compared to partial removal (pCR). In the case of FCR, all information
about the class is removed, and hence an unlearnt model is expected to not
classify any sample as the removed class. However, in pCR a well generalized
model may correctly classify more samples as the affected class, thus leading
to the misalignment of utility and forgetting. We observe that CoMI seems to
have unclear trends in pCR, sometimes giving a weak signal for unlearning
efficacy. Fgt and Err in pCR tests with sample sizes ranging from a tenth to
half of the class give a substantial signal, but much weaker than IC test.
Thus, targeted removal contributes to better measurements of forgetting for
relatively smaller deletion sets, but has limited usefulness without adding
confusion.

Class Pair |  | {6, 7} | {2, 8} | {0, 4} | {1, 9} | {3, 5}
---|---|---|---|---|---|---
CIFAR10 ($|D_{f}|=400$)
Original |  | 238$|$38 | 304$|$40 | 320$|$43 | 317$|$100 | 348$|$211
10-layers | CF | 15$|$4 | 38$|$6 | 85$|$11 | 127$|$64 | 247$|$181
EU | 14$|$4 | 21$|$4 | 63$|$12 | 111$|$66 | 209$|$181
50-layers | CF | 3$|$2 | 9$|$6 | 8$|$10 | 33$|$57 | 69$|$158
EU | 0$|$5 | 2$|$7 | 5$|$11 | 18$|$65 | 55$|$179
Retrain |  | 1$|$1 | 1$|$9 | 1$|$7 | 9$|$54 | 41$|$164
CIFAR10 ($|D_{f}|=4000$)
Original |  | 2980$|$1005 | 2855$|$868 | 2952$|$983 | 2915$|$1000 | 3016$|$927
10-layers | CF | 57$|$7 | 76$|$14 | 83$|$18 | 305$|$93 | 1226$|$335
EU | 50$|$10 | 49$|$13 | 76$|$21 | 257$|$99 | 1165$|$352
50-layers | CF | 24$|$6 | 30$|$7 | 31$|$11 | 160$|$70 | 569$|$229
EU | 12$|$4 | 21$|$6 | 27$|$12 | 130$|$66 | 453$|$195
Retrain |  | 3$|$1 | 19$|$6 | 20$|$17 | 117$|$65 | 390$|$184

Table 16: Varying confused class pairs on CIFAR10, with the similarity of the
classes increasing from left to right. Scores reported as
Memorization$|$Property Generalization. While the IC test reliably detects
imperfect forgetting across class pairs, the trends are clearer for more
similar classes.

###  D.5 Varying Confused Classes

Throughout our experiments, we only confused the hardest pair of classes in
the dataset (Cat and Dog for CIFAR10, Maple Tree and Oak Tree for CIFAR100).
Here we ablate the chosen class pair, grouping the ten classes in CIFAR10 into
five pairs to maximize diversity. The five pairs are arranged in increasing
order of similarity below:

  * •

Frog (6) - Horse (7)

  * •

Bird (2) - Ship (8)

  * •

Airplane (0) - Deer (4)

  * •

Automobile (1) - Truck (9)

  * •

Cat (3) - Dog (5)

In table 16 we can see that the number of confused samples by any model is
much higher as we go from left to right, indicating that confusing a similar
pair of classes makes unlearning more difficult. Both memorization (left of
$|$) and property generalization (right of $|$) trends across varying levels
of unlearning, from Original to Retrain, are consistently preserved. This
shows that irrespective of the chosen class pair, the IC test is able to
clearly distinguish varying degrees of forgetting.

Sched | CF-$10$ | CF-$50$
---|---|---
| CoMI | Fgt | CoMI | Fgt
CIFAR10 ($|D_{f}|=4000$)
WR | 58.66 | 335 | 54.24 | 229
No | 58.10 | 340 | 53.62 | 234
CIFAR100 ($|D_{f}|=400$)
WR | 77.99 | 58 | 58.24 | 41
No | 78.87 | 55 | 58.57 | 43

Table 17: We compare Warm Restarts and keeping a single learning rate cycle
between the same maxLR and minLR. CoMI represents memorization while Fgt
measures property generalization.

###  D.6 Learning Without Restarts

One concern which may arise is whether catastrophic forgetting performs well
due to warm restarts in our learning rate schedule. We ablate this effect in
Table 17 and see that in all cases removing warm restarts has no effect on the
degree of catastrophic forgetting.