# Machine Unlearning via Null Space Calibration

Huiqiang Chen1,3 111word done while at University of Queensland Tianqing Zhu2
222corresponding author Xin Yu3&Wanlei Zhou4 1University of Technology Sydney,
NSW, Australia
2City University of Macau, Macau, China
3University of Queensland, QLD, Australia
<EMAIL_ADDRESS>{tqzhu<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Machine unlearning aims to enable models to forget specific data instances
when receiving deletion requests. Current research centres on efficient
unlearning to erase the influence of data from the model and neglects the
subsequent impacts on the remaining data. Consequently, existing unlearning
algorithms degrade the model’s performance after unlearning, known as over-
unlearning. This paper addresses this critical yet under-explored issue by
introducing machine Unlearning via Null Space Calibration (UNSC), which can
accurately unlearn target samples without over-unlearning. On the contrary, by
calibrating the decision space during unlearning, UNSC can significantly
improve the model’s performance on the remaining samples. In particular, our
approach hinges on confining the unlearning process to a specified null space
tailored to the remaining samples, which is augmented by strategically pseudo-
labeling the unlearning samples. Comparative analyses against several
established baselines affirm the superiority of our approach. Code is released
at this URL.

##  1 Introduction

With the rising concerns regarding the privacy of users’ data in the AI era,
legislative bodies have instituted regulatory measures to safeguard user’s
data. A notable example is the Right to Be Forgotten, which requires service
providers to remove users’ data from AI models upon receiving deletion
requests (Regulation, 2018). However, removing the trace of particular data
from a trained model is challenging. Machine unlearning has emerged as a
promising solution, it endeavors to enable models to forget specific data
samples, effectively erasing their influence as if they were never trained on
these samples. The simplest way is to retrain the model from scratch without
unlearning samples. However, it is time-consuming and even impossible in the
face of frequent unlearning requests. As such, the research community has been
actively developing algorithms to expedite unlearning.

(a) Original model

(b) Baseline

(c) UNSC

Figure 1: A toy example to illustrate the effectiveness of UNSC. (a) presents
decision boundaries of the original model trained on four overlapping Gaussian
distributions, with class-specific accuracy shown. We unlearn the entire
purple class and plot the results in (b) and (c) for baseline and UNSC. Our
method preserves the decision boundaries between remaining samples by
unlearning in the null space and further improves the model’s accuracy by
calibrating the decision space.

However, current unlearning methods find that the unlearning process
significantly affects the remaining data, leading to over-unlearning (Hu et
al., 2023; Fan et al., 2023). The model loses part of its prediction
performance on the remaining data after unlearning. This is because the
unlearning process requires modifications to the weights of the original
model. Though the intent was to eliminate the influence of the unlearning
data, these modifications inadvertently result in partial forgetting of the
remaining samples, ultimately leading to over-unlearning. This raises a
compelling question:

Q1: To maintain the model’s performance, can we prevent over-unlearning, and
if so, how to achieve it?

In this paper, we propose machine Unlearning via Null Space Calibration
(UNSC). To avoid over-unlearning, UNSC constrains the unlearning process
within a null space tailored to the remaining samples. This ensures unlearning
does not negatively impact the model’s performance on the remaining samples.
Figure 1c visualizes this concept, where decision boundaries among remaining
samples closely resemble those depicted in Figure 1a. Going beyond, we further
ask:

Q2: Is it possible to improve the model’s performance after unlearning, and
how?

To answer this question, we find that targeted unlearning can mitigate class
overlap and augment the model’s accuracy. Therefore, calibrating the decision
space might be a possible solution. Take a toy case shown in Figure 1 as an
example. We train a model to classify a mixture of four Gaussian
distributions. Figure 1a depicts the decision boundaries. Due to the overlap
of the purple class with other classes, the model struggles to distinguish the
overlapping samples. Unlearning misclassified samples and calibrating decision
space lead to more accurate decision boundaries shown in Figure 1c.

UNSC assigns pseudo-labels to unlearning samples based on their proximity to
the remaining samples. This process reallocates the space of unlearning
samples to the remaining classes, forming more separable clusters (as shown in
Figure 4(d)). Contributions of this paper are summarized as follows:

  * •

We tackle the challenging problem of over-unlearning. Going beyond, we
investigate the possibility of boosting the model’s performance after
unlearning.

  * •

We propose UNSC, a novel machine unlearning method that confines the
unlearning process to a specific null space and assigns pseudo-labels to the
unlearning samples. Combined, UNSC is not only free from over-unlearning but
can also boost the model’s performance.

  * •

We provide theoretical justifications for the proposed method and empirically
validate it with extensive experiments. The results show UNSC can provide
equivalent and even better performance than retraining.

##  2 Related Works

###  2.1 Machine Unlearning

Current unlearning algorithms have two branches: exact unlearning and
approximate unlearning (Xu et al., 2023). Exact unlearning ensures that
distributions of model weights in an unlearned model are indistinguishable
from those in a model retrained from scratch. Cao and Yang (2015) explore this
concept within the realm of statistical query learning, Ginart et al. (2019)
propose an efficient data elimination algorithm for $k$-means clustering.
However, these methods can not be generalized to deep learning. To address
this limitation, SISA (Bourtoule et al., 2021) divides the training data into
several segments and trains sub-models on each segment. It only needs to
retrain the affected segment when unlearning requests arise. Nevertheless, the
computational overhead of the exact unlearning method remains substantial.

Unlike exact unlearning, approximate unlearning is bounded by an approximate
guarantee. Works in this stream estimate the influence of unlearning samples
and modify the model weights to achieve unlearning. For example, Graves et al.
(2021) made the estimation through the gradient, Guo et al. (2019) developed
their method on the influence function (Koh and Liang, 2017), Golatkar et al.
(2020) use the fisher information matrix in their design. Lin et al. (2023)
associate the unlearning samples with feature maps. While our work belongs to
this category, it does not require the estimation of the influence of
unlearning samples.

Works most closely related to ours are those by (Chen et al., 2023; Li et al.,
2023). Both Chen et al. (2023) and our approach shift decision boundaries. The
distinct advantage of our work lies in the design of a sophisticated null
space, which maintains the decision boundaries of the remaining classes,
leading to better performance. Li et al. (2023) also explore subspace-based
unlearning; however, their approach does not capitalize on unlearning samples
to guide the shifting of decision boundaries, an essential aspect of our
method.

###  2.2 Subspace Learning

DNNs are usually over-parameterized as they have more parameters than input
samples. However, the intrinsic dimension is much smaller (Allen-Zhu et al.,
2019). The weight updates happen in a much smaller subspace than the original
parameter space. Li et al. (2018) find that optimizing in a reduced subspace
reaches 90% performance of regular SGD training. Gur-Ari et al. (2018) observe
that after a short training period, the weight updates converge to a tiny
subspace spanned by several top eigenvectors of the Hessian matrix.

Learning in subspace has many applications. Li et al. (2022) optimize DNNs in
40-dimensional space and achieve comparable performance to regular training
over thousands or even millions of parameters. In the context of meta-
learning, Lee and Choi (2018) employs a learned subspace within each layer’s
activation space where task-specific learners perform gradient descent. This
subspace is tailored to be sensitive to task-specific requirements,
facilitating more effective learning across different tasks. Farajtabar et al.
(2020),Saha et al. (2021), and Wang et al. (2021) applied subspace in
continual learning to reduce the issue of catastrophic forgetting.

##  3 Preliminaries and Notation

We use bold lowercase to denote vectors, e.g., $\mathbf{x}_{i}$, and italics
in uppercase for space or set, e.g., $\mathcal{S}$. The training dataset is
represented as
$\mathcal{D}=\left\\{\mathbf{x}_{i},y_{i}\right\\}_{i=1}^{N}\subseteq\mathcal{X}\times\mathcal{Y}$,
where $\mathcal{X}\subseteq\mathbb{R}^{d}$ is the input space and
$\mathcal{Y}=\left\\{1,...,K\right\\}$ is the label space. We further split
$\mathcal{D}$ into unlearning set $\mathcal{D}_{u}$ and remaining set
$\mathcal{D}_{r}$. We consider unlearning a neural network $f$ with $L$
layers. The input feature of input $\mathbf{x}_{i}$ at layer $l$ is denoted as
$\mathbf{r}_{l}^{i}$. We denote $f(\cdot,\theta_{o})$ the original model
trained on $\mathcal{D}$ with parameters
$\theta_{o}=\left\\{\mathbf{w}_{o}^{1},...,\mathbf{w}_{o}^{L}\right\\}$, and
$f(\cdot,\theta_{r})$ is trained on $\mathcal{D}_{r}$.

A machine unlearning algorithm takes the original model $f(\cdot,\theta_{o})$
and the unlearning samples $\mathcal{D}_{u}$ as input and outputs an unlearned
model $f(\cdot,\theta_{u})$, in which the trace of the unlearning samples is
removed. It can be formally defined as:

######  Definition 1 (Machine unlearning (Cao and Yang, 2015)).

Given a model $f(\cdot,\theta_{o})=\mathcal{A}(\mathcal{D})$ trained on
dataset $\mathcal{D}$ with some training algorithm $\mathcal{A}$, denote
$\mathcal{D}_{u}\subseteq\mathcal{D}$ the set of samples that we want to
remove from the training dataset $\mathcal{D}$ as well as from the trained
model $\mathcal{A}(\mathcal{D})$. An unlearning process $\mathcal{U}$ produces
a new set of weights $\theta_{u}$ that performs as though it had never seen
the unlearning dataset $\mathcal{D}_{u}$.

$\theta_{u}\leftarrow\mathcal{U}(f(\cdot,\theta_{o}),\mathcal{D}_{u}).$ (1)

A key design of UNSC is a specific null space in which we perform unlearning.
It ensures that unlearning will not affect the classification of the remaining
samples. A null space is defined as:

######  Definition 2 (Null space).

Let $\mathbf{A}$ be an $m$ by $n$ matrix, the null space of $A$, denoted by
$null(\mathbf{A})$, is the set of all vectors $\eta\in\mathbb{R}^{n}$ that
satisfy $\mathbf{A}\eta=\mathbf{0}$.

$null(\mathbf{A})=\left\\{\eta\in\mathbb{R}^{n}|\mathbf{A}\eta=\mathbf{0}\right\\}.$
(2)

##  4 Proposed Method

Our proposed method consists of two key parts: 1) unlearning in the null space
to avoid over-unlearning and 2) calibrating decision space to improve the
model’s performance.

###  4.1 Find the Null Space for Unlearning

An ideal unlearning algorithm should erase the trace about the unlearning
samples from the model without degrading the model’s performance on the
remaining samples, i.e., without over-unlearning. To achieve this, UNSC
constrains the unlearning process within a null space tailored to the
remaining samples. The underlying principle is that different models with
weights in the same null space would yield identical predictions on the
samples associated with that null space (theoretical justification is provided
in Section 5.1).

Gradients lie in the subspace spanned by inputs. Considering a single-layer
neural network performing a binary classification task. The loss function is
defined as:

$L_{i}(\mathbf{w})=-y_{i}\log\left(\sigma(\mathbf{w}^{T}\mathbf{x}_{i})\right)-(1-y_{i})\log\left(1-\sigma(\mathbf{w}^{T}\mathbf{x}_{i})\right),$
(3)

in which $\sigma(z)=\frac{1}{1+e^{-z}}$ is the sigmoid function. According to
the chain rule, we have:

$\nabla_{\mathbf{w}}L_{i}=\left(\frac{1-y_{i}}{1-\sigma(\mathbf{w}^{T}\mathbf{x}_{i})}-\frac{y_{i}}{\sigma(\mathbf{w}^{T}\mathbf{x}_{i})}\right)\frac{\partial\sigma(\mathbf{w}^{T}\mathbf{x}_{i})}{\partial\mathbf{w}}.$
(4)

Substitute the last term with the derivative of the sigmoid function, we get:

$\nabla_{\mathbf{w}}L_{i}=\left(\sigma(\mathbf{w}^{T}\mathbf{x}_{i})-y_{i}\right)\mathbf{x}_{i}=e_{i}\mathbf{x}_{i},$
(5)

$e_{i}$ is the prediction error. Eq. 5 shows the gradient lies in the space
$span\left\\{\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{N}\right\\}$. The
same relation can be deduced for the convolutional layer by reformulating the
convolution into matrix multiplication (Liu et al., 2018).

Identify the layer-wise subspace for each class. Based on the relationship
between gradient and inputs, we first identify the subspace of each class.
Then, for each unlearning sample, we find the corresponding null space to
perform unlearning. This incurs negligible computation overhead. For each
class, we only need a small batch of samples ($256$ in our experiment) to find
the null space. In addition, we only need to find the subspace once because we
treat the null space as fixed during unlearning. Our experiment results
justify the hypothesis. One may consider iterative updating the null space
during unlearning. We leave this as future work.

To find the subspace of class $k$, we sample a batch of inputs
$\mathcal{B}_{k}=\left\\{(x_{i},y_{i})|y_{i}=k\right\\}_{i=1}^{B}$ from class
$k$ at random and feed these samples through the original model
$f(\cdot;\theta_{o})$. At the $l$-th layer, we have a collection of input
features as
$\mathbf{R}_{l}^{k}=[\mathbf{r}_{l,1},\mathbf{r}_{l,2},...,\mathbf{r}_{l,B}]$
with each column corresponds to an input. For the convolutional layer, we need
to reformulate the input feature by treating each patch as a column. The
columns of $\mathbf{R}_{l}^{c}$ are usually larger than the rows, and each
column represents a vector sampled from some unknown subspace. We decompose it
using singular value decomposition (SVD) to find the subspace as:

$\mathbf{U}_{l}^{k}\mathbf{\Sigma}_{l}^{k}\mathbf{V}_{l}^{kT}=\text{SVD}(\mathbf{R}_{l}^{k}).$
(6)

Algorithm 1 Find layer-wise subspace of class $k$

Input: Batch input $\left\\{x_{i},y_{i}|y_{i}=k\right\\}_{i=1}^{B}$; network
$f(\cdot;\theta_{o})$; threshold $\left\\{\epsilon_{l}\right\\}_{l=1}^{L}$.
Output: Layer-wise subspace of class $k$.

1:Feed forward $\left\\{x_{i}\right\\}_{i=1}^{B}$ through
$f(\cdot;\theta_{o})$.

2:for $l\in[L]$ do

3: Collect the input feature $\mathbf{R}_{l}^{k}$.

4: Perform SVD:
$\mathbf{R}_{l}=\mathbf{U}_{l}^{k}\mathbf{\Sigma}_{l}^{k}\mathbf{V}_{l}^{kT}$.

5:end for

6:return $\mathcal{S}^{k}=\left\\{\mathbf{U}_{l}^{k}\right\\}_{l=1}^{L}$.

The elements in $\mathbf{U}_{l}^{k}$ are the subspace basis for class $k$ at
layer $l$. The gradient induced by samples from class $k$ lies in this
subspace. $\mathbf{\Sigma}_{l}^{k}$ is a diagonal matrix that stores the
eigenvalues in descending order. We repeat this process of all layers in
$f(\cdot;\theta_{o})$ to identify subspaces of each layer,

$\mathcal{S}^{k}=\left\\{\mathbf{U}_{l}^{k}\right\\}_{l=1}^{L}.$ (7)

Algorithm 1 formalizes this process. Note that the inputs do not need to be
from the same class. However, in our design, we find the layer-wise subspace
$\mathcal{S}^{k}$ of each class for efficient unlearning. The unlearning
samples could come from different classes. For each unlearning sample, we need
to find the corresponding null space to perform unlearning. By identifying
class-wise null space, we can efficiently identify each unlearning sample’s
null space. We articulate this in the following part.

Unlearning in the null space After getting the layer-wise subspaces of each
class, we are ready to find the null space for unlearning. For an unlearning
sample $(x_{i},y_{i}=c)\in\mathcal{D}_{u}$, we perform unlearning in the null
space of the rest classes $\bar{c}=\left\\{i\in[K]|i\neq c\right\\}$. Denote
the concatenation of the rest subspaces as
$\mathcal{S}^{\bar{c}}_{l}=\cup_{i\in\bar{c}}\mathbf{U}^{i}_{l}$ at layer-$l$.
We merge these subspaces as:

$\mathbf{U}_{l}^{\bar{c}}\mathbf{\Sigma}_{l}^{\bar{c}}\mathbf{V}_{l}^{\bar{c}T}=\text{SVD}\left(\mathcal{S}_{l}^{\bar{c}}\right).$
(8)

The basis of the merged subspace comes from the element of
$\mathbf{U}_{l}^{\bar{c}}$. $\mathcal{S}_{l}^{\bar{c}}$ has few dominant
eigenvalues and a large number of very small ones. The eigenvectors
corresponding to those small eigenvalues are usually irrelevant. Thus, we can
approximate the subspace by the span of top-$k$ eigenvectors.

$\left\|\left(\mathcal{S}_{l}^{\bar{c}}\right)_{k}\right\|_{F}^{2}\geq\epsilon_{l}\left\|\mathcal{S}_{l}^{\bar{c}}\right\|_{F}^{2},$
(9)

where $\epsilon_{l}$ is the approximation threshold (we find
$\epsilon_{l}>0.97$ is good enough in our experiment), $\|\mathbf{A}\|_{F}$ is
Frobenius norm of matrix $\mathbf{A}$. The top-$k$ eigenvectors span the
approximate subspace:

$\hat{\mathbf{S}}_{l}^{\bar{c}}=span\left\\{u_{l,1}^{\bar{c}},u_{l,2}^{\bar{c}},...,u_{l,k}^{\bar{c}}\right\\},$
(10)

where $u_{l,i}^{\bar{c}}$ is the $i$-th element of $\mathbf{U}_{l}^{\bar{c}}$.
Gradient lies in $\hat{\mathbf{S}}_{l}^{\bar{c}}$ will alter the model’s
response to samples from $\bar{c}$, which may lead to over-unlearning. As
such, we project the gradient to a space perpendicular to
$\hat{\mathbf{S}}_{l}^{\bar{c}}$, i.e., the null space of the rest samples.
The projection matrix is defined as:

$\mathbf{P}_{l}^{\bar{c}}=\mathbf{I}-\mathbf{\hat{S}}_{l}^{\bar{c}}(\mathbf{\hat{S}}_{l}^{\bar{c})T}.$
(11)

At layer-$l$, the updating rule is modified as:

$\mathbf{w}_{t+1}^{l}=\mathbf{w}_{t}^{l}-\eta\mathbf{P}_{l}^{\bar{c}}\nabla_{\mathbf{w}^{l}}\mathcal{L}^{c},$
(12)

where $\mathcal{L}^{c}$ is the classification loss on unlearning sample
$(x_{i},y_{i}=c)$. Algorithm 2 illustrates the pseudo-code.

###  4.2 Calibrate Decision Space

To calibrate the decision space, we borrow the idea from poisoning attacks,
which aim to decrease the victim model’s performance by feeding it poisoned
samples. There are several poisoning attacks, one of which is the label-
flipping attack (Rosenfeld et al., 2020). In this attack, the input feature
$\mathbf{x}_{i}$ remains unchanged, and the label is carefully set as the most
dissimilar class. But our target is different, i.e., we aim to boost the
model’s utility on the remaining samples. As such, we label an unlearning
sample as the most similar class in the rest of the classes.

However, comparing samples-wise similarity could be rather inefficient and
even impossible when the remaining samples are not accessible. As such, we
base our method on the prediction of the original model. For an unlearning
sample of class $(\mathbf{x}_{i},y_{i}=c)$, we find the pseudo-labels from the
remaining classes set $\bar{c}$ as:

$\displaystyle\tilde{y}=\arg\max_{y\in\bar{c}}f(\mathbf{x}_{i};\theta_{o}).$
(13)

We use the top-$1$ prediction as the pseudo-label for an unlearning sample if
it gives the wrong prediction. Otherwise, we use the second-highest score as
the pseudo-label.

Algorithm 2 Unlearning via null space calibration

Input: Training data $\mathcal{D}$; trained model $f(\cdot;\theta_{o})$.
Output: Unlearned model $f(\cdot;\theta_{u})$

1:# Get the subspace of each class

2:for $k\in[K]$ do

3: Identify the subspace of class $k$ by Algorithm 1 with
$\left\\{x_{i},y_{i}|y_{i}=k\right\\}_{i=1}^{B}$, $f(\cdot;\theta_{o})$, and
$\left\\{\epsilon_{l}\right\\}_{l=1}^{L}$ as input.

4:end for

5:# Calculate the projection matrix

6:for $c\in[K]$ do

7: for $l\in[L]$ do

8: Merge subspaces of rest classes using Eq. 8.

9: Perform $k$-rank approximation by Eq. 9

10: Find the subspace as Eq. 10.

11: Calculate layer-wise projection matrix as Eq. 11.

12: end for

13:end for

14:# Unlearning in the null space

15:for $(x_{i},y_{i})\in\mathcal{D}_{u}$ do

16: $\tilde{y}_{i}$ $\leftarrow$
$\arg\max_{y\in\bar{c}}f(\mathbf{x}_{i};\theta_{o})$ $\triangleright$ Pseudo-
labeling $x_{i}$

17: Calculate gradients on ($x_{i},\tilde{y}_{i}$).

18: Update the original model in the null space as Eq. 12.

19:end for

To elucidate our design, one might consider this in another way: we expect the
unlearned model to behave similarly to the retrained model. The unlearned
model should give the same or similar predictions as the retrained model for
the unlearning samples. The retrained model, trained using the remaining
samples, has never been exposed to the unlearning samples. Consequently, the
retrained model will classify these unlearning samples into categories
represented within the remaining samples. As such, the unlearned model should
predict a given unlearning sample belongs to the same class as the remaining
samples most similar to it.

##  5 Theoretical Analysis

###  5.1 Null Space Prevents Over-unlearning

######  Theorem 1.

For a trained model $f(\cdot;\theta_{o})$, unlearning the target samples from
$\mathcal{D}_{u}$ in the null space tailored to the remaining samples from
$\mathcal{D}_{r}$ ensures the unlearned model $f(\cdot;\theta_{u})$ has
approximately the same performance as $f(\cdot;\theta_{o})$, i.e.,

$\mathcal{L}_{r}(\theta_{u})\approx\mathcal{L}_{r}(\theta_{o}),$ (14)

where
$\mathcal{L}_{r}(\theta):=\frac{1}{|\mathcal{D}_{r}|}\sum_{\mathcal{D}_{r}}\ell(f(\mathbf{x}_{i};\theta),y_{i})$
is the average loss on the remaining samples.

###### Proof.

We expand $\mathcal{L}_{r}(\theta_{u})$ around $\mathcal{L}_{r}(\theta_{o})$
as:

$\displaystyle\mathcal{L}_{r}(\theta_{u})$
$\displaystyle=\mathcal{L}_{r}(\theta_{o})+(\theta_{u}-\theta_{o})^{T}\nabla_{\theta}\mathcal{L}_{r}(\theta_{o})+\mathcal{O}(\left\|\theta_{u}-\theta_{o}\right\|^{2})$
$\displaystyle=\mathcal{L}_{r}(\theta_{o})+\Delta\theta^{T}\nabla_{\theta}\mathcal{L}_{r}(\theta_{o})+\mathcal{O}(\left\|\Delta\theta\right\|^{2}).$

We decompose $\Delta\theta^{T}\nabla_{\theta}\mathcal{L}_{r}(\theta_{o})$
layer-by-layer as:

$\Delta\theta^{T}\nabla_{\theta}\mathcal{L}_{r}(\theta_{o})=\frac{1}{|\mathcal{D}_{r}|}\sum_{l\in[L]}\sum_{\mathcal{D}_{r}}(\Delta\mathbf{w}^{l})^{T}\nabla_{\mathbf{w}^{l}}\ell(f(\mathbf{x}_{i};\theta_{o}),y_{i}).$
(15)

Note $\theta=\left\\{\mathbf{w}^{1},...,\mathbf{w}^{L}\right\\}$ and
$\Delta\mathbf{w}^{l}=\mathbf{w}_{u}^{1}-\mathbf{w}_{o}^{1}$. At the $l$-th
layer, we have
$\mathbf{r}_{i}^{l+1}=\sigma(\mathbf{w}^{l}\mathbf{r}_{i}^{l})$, where
$\sigma(\cdot)$ is activation function, $\mathbf{r}^{l}_{i}$ is the activation
at layer $l$ with respect to input $\mathbf{x}_{i}$. We rewrite the derivative
term by the chain rule:

$\displaystyle\nabla_{\mathbf{w}^{l}}\ell(f(\mathbf{x}_{i};\theta_{0}),y_{i})=$
$\displaystyle\nabla_{f}\ell(f(\mathbf{x}_{i};\theta_{0}),y_{i})\nabla_{w^{l+1}}f(\mathbf{x}_{i};\theta_{0})\text{diag}\left\\{\sigma^{\prime}(\mathbf{w}^{l}\mathbf{r}_{i}^{l})\right\\}\mathbf{r}_{i}^{l}.$

Note that we confine the learning in a null space tailored to the reaming
samples from $\mathcal{D}_{r}$. Thus at the $l$-th layer, we have the
following by definition:

$\left<\Delta\mathbf{w}^{l},\mathbf{r}^{l}_{i}\right>=0,\forall\mathbf{x}_{i}\in\mathcal{D}_{r}.$
(16)

Thus, we immediately have
$\Delta\theta^{T}\nabla_{\theta}\mathcal{L}_{r}(\theta_{o})=0$. During
unlearning, $\Delta\theta$ should be relatively small. As such, we have:

$\mathcal{L}_{r}(\theta_{u})\approx\mathcal{L}_{r}(\theta_{o}).$ (17)

∎

Theorem 1 asserts that confining unlearning in the null space ensures the
unlearned model $f(\cdot,\theta_{u})$ performs comparably to the original
model $f(\cdot,\theta_{o})$. This substantiates that UNSC can effectively
mitigate the risk of over-unlearning.

###  5.2 Pseudo-labeling Benefits Unlearning

Assuming the unlearning sample $\mathbf{x}_{i}$ is generated i.i.d. from the
domain $\left<\mathcal{D}_{u},h_{o}\right>$, with the ground-truth labeling
function $h_{o}$. In our proposed method, we assign pseudo-labels to the
unlearning samples, this equivalent to replacing $h_{o}$ with a new labeling
function $h_{u}$. Consequently, the domain of unlearning samples becomes
$\left<\mathcal{D}_{u},h_{u}\right>$ during learning. The primary objective of
unlearning is to minimize the model’s retention of information about the
unlearning samples. We use the empirical risk on unlearning samples as a proxy
measurement of forgetting in our analysis. The risk of $f(\cdot;\theta_{u})$
over $\left<\mathcal{D}_{u},h_{u}\right>$ is calculated as:

$\epsilon(\theta_{u},h_{u})=\mathbb{E}_{\mathbf{x}_{i}\in\mathcal{D}_{u}}[\mathbf{1}_{f(\mathbf{x}_{i};\theta_{u})\neq
h_{u}(\mathbf{x}_{i})}].$ (18)

We use the parallel notion $\epsilon_{u}(\theta_{u},h_{o})$ to denote the risk
over the original domain $\left<\mathcal{D}_{u},h_{o}\right>$, which can be
expressed as:

$\displaystyle\epsilon(\theta_{u},h_{o})$
$\displaystyle=\epsilon(\theta_{u},h_{o})+\epsilon(\theta_{u},h_{u})-\epsilon(\theta_{u},h_{u})$
$\displaystyle=\epsilon(\theta_{u},h_{u})+\mathbb{E}_{\mathbf{x}_{i}\in\mathcal{D}_{u}}[\mathbf{1}_{f(\mathbf{x}_{i};\theta_{u})\neq
h_{o}(\mathbf{x}_{i})}]$
$\displaystyle-\mathbb{E}_{\mathbf{x}_{i}\in\mathcal{D}_{u}}[\mathbf{1}_{f(\mathbf{x}_{i};\theta_{u})\neq
h_{u}(\mathbf{x}_{i})}]$
$\displaystyle\geq\epsilon(\theta_{u},h_{u})-\mathbb{E}_{\mathbf{x}_{i}\in\mathcal{D}_{u}}[\mathbf{1}_{h_{o}(\mathbf{x}_{i})=h_{u}(\mathbf{x}_{i})}].$
(19)

The forgetting level $\epsilon(\theta_{u},h_{0})$ depends partly on the second
term on the right-hand side. It measures the expectation that the pseudo-
labeling function disagrees with the ground-truth labeling function for the
unlearning samples. To facilitate forgetting, $h_{u}$ should assign each
unlearning sample a label different from $h_{o}(\mathbf{x}_{i})$ to minimize
$\mathbb{E}_{\mathbf{x}_{i}\in\mathcal{D}_{u}}[\mathbf{1}_{h_{o}(\mathbf{x}_{i})=h_{u}(\mathbf{x}_{i})}]$.
The pseudo-label assigned by UNSC differs from the ground-truth label
$h_{o}(\mathbf{x}_{i})$. Thus, it minimizes the second term and increases
$\epsilon(\theta_{u},h_{o})$, leading to better forgetting.

##  6 Experiments

###  6.1 Protocol and Evaluation Metrics

Datasets and models. We compare UNSC with existing methods on the standard
FashionMNIST (Xiao et al., 2017), CIFAR-10, CIFAR-100 (Krizhevsky et al.,
2009), and SVHN (Netzer et al., 2011) benchmarks. We use AlexNet (Krizhevsky
et al., 2012) for FashionMNIST, VGG-11 (Simonyan and Zisserman, 2015) for
SVHN, AllCNN (Springenberg et al., 2015) for CIFAR-10, and ResNet-18 (He et
al., 2015) for CIFAR-100.

Evaluation metrics. We evaluate the unlearning process from two aspects, i.e.,
utility and privacy guarantee. (1) Utility guarantee is evaluated by accuracy
on the remaining testing data $Acc_{\mathcal{D}_{rt}}$ and accuracy on the
unlearning testing data $Acc_{\mathcal{D}_{ut}}$. An ideal unlearning process
should sustain $Acc_{\mathcal{D}_{rt}}$ and reduce $Acc_{\mathcal{D}_{rt}}$
towards zero (Chen et al., 2023). (2) Privacy guarantee is assessed through
the membership inference attack (MIA) (Shokri et al., 2017). Following (Fan et
al., 2023), we apply the confidence-based MIA predictor to the unlearned model
on the unlearning samples. We define the MIA accuracy as the True Negative
Rate $Acc_{MIA}=TN/|\mathcal{D}_{u}|$, i.e., the rate of unlearning samples
that are identified as not being in the training set of the unlearned model. A
higher $Acc_{MIA}$ indicates a more effective unlearning. All results are
averaged over three trials by default.

Implementation details. The original training set is divided into $90\%$ for
training and $10\%$ for validation. We train the original and retrained models
for $200$ epochs and stop the training based on validation accuracy. The
patience is set to $30$. We use SGD optimizer in all experiments, starting
with a learning rate of $0.1$, and reducing it by $0.2$ at epochs $60$, $120$,
and $160$. In the unlearning stage, we determine the best learning rate and
number of epochs for different datasets and networks. Table 4 in Appendix A
details the protocol.

###  6.2 Comparison with the State-of-the-Art

We compare UNSC with various methods, assessing both utility and privacy
guarantees. These include: (1) Retrain, (2) Boundary unlearning (BU) (Chen et
al., 2023), (3) Random labels (RL) (Hayase et al., 2020), (4) Gradient ascent
(GA) (Golatkar et al., 2020), (5) Fisher Forgetting (Fisher) (Golatkar et al.,
2020), and (6) SalUn (Fan et al., 2023). Following (Chen et al., 2023), we
randomly select one class (or ten classes on CIFAR-100) and unlearn all the
samples.

Utility guarantee. Table 1 displays the accuracy results of models obtained by
different unlearning methods. Observing the results reveals that: (1)
Comparison methods struggle with over-unlearning: $Acc_{\mathcal{D}_{ut}}$
decreases at the cost of $Acc_{\mathcal{D}_{rt}}$, leading to over-unlearning.
For instance, SalUn reduces $Acc_{\mathcal{D}_{ut}}$ to $3.56\%$ with a
$16.7\%$ reduction in $Acc_{\mathcal{D}_{rt}}$ on the SVHN dataset. This is
more sever on the CIFAR-100 dataset, as comparison methods degrade
$Acc_{\mathcal{D}_{rt}}$ by more than $30\%$; (2) UNSC excels in avoiding
over-unlearning: UNSC consistently maintains $Acc_{\mathcal{D}_{ut}}$ below 2%
without compromising $Acc_{\mathcal{D}_{rt}}$. This underscores UNSC’s ability
to avoid over-unlearning; (3) UNSC exhibits superior performance compared to
the original model: On all datasets, models derived from UNSC get higher
$Acc_{\mathcal{D}_{rt}}$ than the original models. This improvement can be
attributed to the calibration of decision space, which makes the remaining
samples more separable.

Privacy guarantee. Figure 2 depicts MIA results. By randomly selecting one
class to unlearn, we get various unlearned models through different methods.
We then assess these models using MIA. The retrained model, having no exposure
to unlearning samples, obtains an attack accuracy of $1.0$. On CIFAR-10,
Fisher and GA exhibit an accuracy below $0.8$, pointing to inadequate
unlearning. SalUn achieves a higher accuracy but suffers more severe over-
unlearning than Fisher, as evident by $Acc_{\mathcal{D}_{rt}}$ in Table 1. The
attack accuracy of BU and UNSC is around $0.98$, signifying success
unlearning. However, unlike BU, UNSC is free of over-unlearning. For SVHN, the
attack accuracy of BU and GA falls below $0.8$, suggesting unsuccessful
unlearning. Conversely, UNSC gets an attack accuracy of $1.0$. This validates
the effectiveness and robustness of UNSC.

Table 1: Comparing the utility guarantee among UNSC and SOTA methods: For FashionMNIST, SVHN, and CIFAR-10, we randomly unlearn one class, and for CIFAR-100, we unlearn ten classes. The results of the retrained model are provided as a reference. Approach | FashionMNIST | SVHN | CIFAR-10 | CIFAR-100
---|---|---|---|---
$Acc_{\mathcal{D}_{rt}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$ | $Acc_{\mathcal{D}_{rt}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$ | $Acc_{\mathcal{D}_{rt}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$ | $Acc_{\mathcal{D}_{rt}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$
Original | $93.58_{\pm 0.28}$ | $80.97_{\pm 1.44}$ | $95.52_{\pm 0.12}$ | $91.30_{\pm 0.30}$ | $92.10_{\pm 0.29}$ | $79.93_{\pm 1.72}$ | $75.36_{\pm 0.34}$ | $72.07_{\pm 1.18}$
RL | $91.50_{\pm 0.20}$ | $3.37_{\pm 1.44}$ | $75.87_{\pm 8.67}$ | $1.17_{\pm 0.16}$ | $82.88_{\pm 2.62}$ | $3.30_{\pm 0.83}$ | $24.58_{\pm 2.01}$ | $1.13_{\pm 0.61}$
BU | $72.71_{\pm 0.44}$ | $2.97_{\pm 1.28}$ | $80.99_{\pm 4.01}$ | $4.03_{\pm 1.87}$ | $87.24_{\pm 2.43}$ | $1.47_{\pm 0.17}$ | $36.81_{\pm 3.05}$ | $12.13_{\pm 2.40}$
GA | $80.94_{\pm 3.87}$ | $6.40_{\pm 2.90}$ | $75.11_{\pm 6.76}$ | $3.10_{\pm 3.90}$ | $88.53_{\pm 1.11}$ | $6.80_{\pm 1.93}$ | $36.55_{\pm 12.85}$ | $12.87_{\pm 7.61}$
Fisher | $95.11_{\pm 0.17}$ | $1.50_{\pm 1.27}$ | $95.72_{\pm 0.30}$ | $2.53_{\pm 0.91}$ | $92.54_{\pm 0.79}$ | $0.07_{\pm 0.05}$ | $49.23_{\pm 2.02}$ | $0.00_{\pm 0.00}$
SalUn | $91.11_{\pm 0.32}$ | $1.80_{\pm 1.44}$ | $78.81_{\pm 4.85}$ | $3.56_{\pm 0.56}$ | $88.88_{\pm 0.19}$ | $6.17_{\pm 0.83}$ | $41.85_{\pm 3.56}$ | $5.97_{\pm 1.39}$
UNSC | $\textbf{95.23}_{\pm\textbf{0.27}}$ | $0.67_{\pm 0.17}$ | $\textbf{95.74}_{\pm\textbf{0.17}}$ | $0.00_{\pm 0.00}$ | $92.77_{\pm 0.08}$ | $0.70_{\pm 0.08}$ | $\textbf{76.16}_{\pm\textbf{0.35}}$ | $1.80_{\pm 0.16}$
Retrain | $95.19_{\pm 0.20}$ | $0.00_{\pm 0.00}$ | $95.56_{\pm 0.23}$ | $0.00_{\pm 0.00}$ | $\textbf{93.22}_{\pm\textbf{0.18}}$ | $0.00_{\pm 0.00}$ | $75.77_{\pm 0.22}$ | $0.00_{\pm 0.00}$

(a) On CIFAR-10.

(b) On SVHN.

Figure 2: Comparing the MIA accuracy of different unlearning methods. A higher
$Acc_{MIA}$ indicates more effective unlearning.

###  6.3 Ablation Studies

Pseudo-labeling strategy. To demonstrate the efficacy of the proposed pseudo-
labeling strategy, we conduct a thorough examination of different datasets. We
present results obtained on CIFAR-10 in Figure 3(a) and provide results on
other datasets in Appendix B. We unlearn all samples of class $3$ and assign
pseudo-labels as described in Section. 4.2. Figure 3(a) plots distributions of
pseudo-labels and labels predicted by the retrained model. The distribution of
pseudo-labels aligns well with the predictions of the retrained model on
unlearning samples. The consistency substantiates the effectiveness of the
proposed pseudo-labeling strategy.

(a)

(b)

Figure 3: (a) Distributions of pseudo-labels and predictions of the retrained
model on CIFAR-10. (b) Loss contour on CIFAR-10. We evaluate the model’s loss
on remaining test data.

Impact of null space. Our first contribution is confining the unlearning
process in a null space, which avoids over-unlearning. Here, we provide
experimental validation. We randomly select one class as the unlearning class
and identify the corresponding null space following the steps outlined in
Algorithm 1. We modify the model’s weights by adding vectors composed of two
components: one within the null space and one outside. We evaluate the
modified model on the testing set of remaining samples and plot the loss
contour in Figure 3(b), with the axes displaying the scaled coefficients.

From Figure 3(b), we observe that modifying weights outside the null space
increases the loss, while alterations within the null space leave the loss
unchanged. This pattern validates our analysis: unlearning within the null
space does not impact the model’s performance on the remaining samples.
Results on additional datasets are presented in Appendix B.

(a) Original model (full)

(b) Unlearned model (full)

(c) Original model (part)

(d) Unlearned model (part)

Figure 4: Visualization of latent space after unlearning all samples of class
$3$ (red points) on CIFAR-10: (a) Original and (b) Unlearned model with all
samples, (c) Original and (d) Unlearned models, both excluding the unlearned
samples.

Decision space calibration. Our second contribution is the calibration of the
decision space, which improves the model’s performance on the remaining
samples. To illustrate this, we compare decision spaces of the original and
unlearned model in Figure 4. We unlearn class $3$ and visualize the latent
spaces using UMAP (McInnes et al., 2018). Several observations can be made:
(1) UNSC successfully unlearns class $3$ from the original model. In Figure
4(b), the cluster of class 3 disperses, with its samples overlapping with
adjacent samples. A clear signal that the unlearned model forgets the
unlearned samples; (2) Decision boundaries among the remaining samples remain
unaffected after unlearning. The shape and positions of clusters in Figure
4(d) closely resemble those in Figure 4(c), underscoring the efficacy of UNSC
in overcoming over-unlearning; (3) Better separability after unlearning. UNSC
redistributes the region previously dominated by class $3$ among neighboring
classes, improving their separability as depicted in Figures 4(c) and 4(d).

(a) Unlearn $1$ class

(b) Unlearn $3$ classes

(c) Unlearn $4$ classes

(d) Unlearn $5$ classes

Figure 5: Comparison of class-wise accuracy on CIFAR-10. We compare the
original model, the retrained model, and the model obtained by UNSC under
different settings. In all experiments, the UNSC-obtained model demonstrates
near-zero accuracy on the forgetting classes, achieving superior accuracy
compared to the original model and comparable performance to the retrained
model. Table 2: Performance evaluation of UNSC on CIFAR-10. #Classes denotes
the number of unlearned classes.

#Classes | Original | Retrain | UNSC | Accuracy Gain
---|---|---|---|---
$Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$ | $Acc_{\mathcal{D}_{rt}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$ | $Acc_{\mathcal{D}_{rt}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$ | $\Delta Acc_{\mathcal{D}_{rt}}(\uparrow)$
1 | $92.10_{\pm 0.29}$ | $79.93_{\pm 1.72}$ | $93.22_{\pm 0.18}$ | $0.00_{\pm 0.00}$ | $92.77_{\pm 0.25}$ | $0.70_{\pm 0.08}$ | $0.67_{\pm 0.42}$
2 | $91.66_{\pm 0.36}$ | $87.77_{\pm 0.89}$ | $93.18_{\pm 0.15}$ | $0.00_{\pm 0.00}$ | $92.73_{\pm 0.25}$ | $0.60_{\pm 0.33}$ | $1.07_{\pm 0.35}$
3 | $92.35_{\pm 0.35}$ | $87.44_{\pm 0.64}$ | $94.24_{\pm 0.17}$ | $0.00_{\pm 0.00}$ | $93.84_{\pm 0.33}$ | $0.89_{\pm 0.45}$ | $1.49_{\pm 0.57}$
4 | $92.38_{\pm 0.36}$ | $88.63_{\pm 0.77}$ | $94.28_{\pm 0.36}$ | $0.00_{\pm 0.00}$ | $94.08_{\pm 0.21}$ | $0.31_{\pm 0.23}$ | $1.70_{\pm 0.54}$
5 | $93.23_{\pm 0.34}$ | $88.53_{\pm 0.55}$ | $96.12_{\pm 0.22}$ | $0.00_{\pm 0.00}$ | $96.15_{\pm 0.13}$ | $0.68_{\pm 0.52}$ | $2.92_{\pm 0.42}$

UNSC under different settings. We randomly select $1$ to $5$ classes to
unlearn. Table 2 compares the utility guarantee of the original model, the
retrained model, and the model obtained by UNSC on the CIFAR-10 dataset.
Figure 5 provides a detailed class-wise accuracy breakdown. Additional results
on other datasets can be found in Appendix B.

Across different settings, the model obtained by UNSC gets near-zero accuracy
on the unlearned classes. Meanwhile, the accuracy of the remaining classes is
higher than that of the original model (measured by $\Delta
Acc_{\mathcal{D}_{rt}}$). Furthermore, as the number of unlearned classes
increases, so does the accuracy gain. This observation affirms (1) the
effectiveness of null space in preventing over-unlearning and (2) the benefit
of decision space calibration. As we progressively unlearn additional samples,
we allocate more decision spaces to the remaining samples. This process
results in a more distinguishable decision space, ultimately enhancing the
model’s classification performance on the remaining samples.

UNSC vs. Baselines. To discern the contribution of each component in the
proposed method, we contrast UNSC with three baselines: the original model,
Retrain, and RL. Table 3 presents a detailed breakdown of the results on the
FashionMNIST dataset, with indexed experiments for reference. (for results on
other datasets, please refer to Appendix B).

Contribution of null space. We conduct an ablation study by removing the
constraint of null space and then compare the outcomes of experiments III and
IV. In the absence of null space constraints, RL reduces
$Acc_{\mathcal{D}_{ut}}$ to $0.90\%$, incurring a $7.28\%$ reduction in
$Acc_{\mathcal{D}_{rt}}$. RL successfully completes the unlearning task but at
the cost of excessive impact on the remaining samples. In contrast, when
confining the unlearning process within a null space tailored to the remaining
samples in experiment IV, we decrease $Acc_{\mathcal{D}_{ut}}$ to $1.57\%$
without affecting $Acc_{\mathcal{D}_{rt}}$. This comparison highlights the
effectiveness of the null space in preventing over-unlearning.

Contribution of pseudo-labeling. We further demonstrate the benefits
introduced by pseudo-labeling. Compared to experiment IV, replacing RL with
pseudo-labeling brings a $1.93\%$ improvement in $Acc_{\mathcal{D}_{rt}}$ in
experiment V. Thanks to pseudo-labeling, the decision space of the unlearning
samples can be selectively redistributed to the adjacent classes, forming a
more distinguishable decision space. The combination of null space and pseudo-
labeling contributes to an elevated $Acc_{\mathcal{D}_{rt}}$ of $95.23\%$,
surpassing the original model by $1.61\%$ and even outperforming the retrained
model.

Table 3: Ablation results on FashionMNIST.

Exp. ID | Original | Retrain | RL |  | Null
---
space
| Pesudo-
---
labeling
$Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$
I | $\checkmark$ |  |  |  |  | $93.58_{\pm 0.28}$ | $80.97_{\pm 1.44}$
II |  | $\checkmark$ |  |  |  | $95.19_{\pm 0.20}$ | $0.00_{\pm 0.00}$
III |  |  | $\checkmark$ |  |  | $86.30_{\pm 0.85}$ | $0.90_{\pm 0.21}$
IV |  |  | $\checkmark$ | $\checkmark$ |  | $93.30_{\pm 1.12}$ | $1.57_{\pm 0.53}$
V |  |  |  | $\checkmark$ | $\checkmark$ | $95.23_{\pm 0.27}$ | $0.67_{\pm 0.17}$

##  7 Conclusion

This paper introduces UNSC, an accurate unlearning algorithm that addresses
the challenge of over-unlearning and further enhances the model’s performance
after unlearning. The innovation in UNSC is grounded in two pivotal design
aspects: (1) Constraining the unlearning process within a designated null
space to prevent over-unlearning and (2) Pseudo-labeling the unlearning
samples to calibrate the decision space, thereby improving prediction
accuracy. Our theoretical analysis provides robust support for this approach,
and empirical results convincingly demonstrate the superior performance of
UNSC over existing methods.

## References

  * Allen-Zhu et al. [2019] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International conference on machine learning, pages 242–252. PMLR, 2019.
  * Bourtoule et al. [2021] Lucas Bourtoule, Varun Chandrasekaran, Christopher Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot.  Machine unlearning.  In Proceedings of the 42nd IEEE Symposium on Security and Privacy, 2021.
  * Cao and Yang [2015] Yinzhi Cao and Junfeng Yang.  Towards making systems forget with machine unlearning.  In 2015 IEEE symposium on security and privacy, pages 463–480. IEEE, 2015.
  * Chen et al. [2023] Min Chen, Weizhuo Gao, Gaoyang Liu, Kai Peng, and Chen Wang.  Boundary unlearning: Rapid forgetting of deep networks via shifting the decision boundary.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 7766–7775, June 2023.
  * Fan et al. [2023] Chongyu Fan, Jiancheng Liu, Yihua Zhang, Dennis Wei, Eric Wong, and Sijia Liu.  Salun: Empowering machine unlearning via gradient-based weight saliency in both image classification and generation.  arXiv preprint arXiv:2310.12508, 2023.
  * Farajtabar et al. [2020] Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li.  Orthogonal gradient descent for continual learning.  In International Conference on Artificial Intelligence and Statistics, pages 3762–3773. PMLR, 2020.
  * Ginart et al. [2019] Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou.  Making ai forget you: Data deletion in machine learning.  Advances in neural information processing systems, 32, 2019.
  * Golatkar et al. [2020] Aditya Golatkar, Alessandro Achille, and Stefano Soatto.  Eternal sunshine of the spotless net: Selective forgetting in deep networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9304–9312, 2020.
  * Graves et al. [2021] Laura Graves, Vineel Nagisetty, and Vijay Ganesh.  Amnesiac machine learning.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11516–11524, 2021.
  * Guo et al. [2019] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten.  Certified data removal from machine learning models.  arXiv preprint arXiv:1911.03030, 2019.
  * Gur-Ari et al. [2018] Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer.  Gradient descent happens in a tiny subspace.  arXiv preprint arXiv:1812.04754, 2018.
  * Hayase et al. [2020] Tomohiro Hayase, Suguru Yasutomi, and Takashi Katoh.  Selective forgetting of deep networks at a finer level than samples.  arXiv preprint arXiv:2012.11849, 2020.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition, 2015.
  * Hu et al. [2023] Hongsheng Hu, Shuo Wang, Jiamin Chang, Haonan Zhong, Ruoxi Sun, Shuang Hao, Haojin Zhu, and Minhui Xue.  A duty to forget, a right to be assured? exposing vulnerabilities in machine unlearning services.  arXiv preprint arXiv:2309.08230, 2023.
  * Koh and Liang [2017] Pang Wei Koh and Percy Liang.  Understanding black-box predictions via influence functions.  In International conference on machine learning, pages 1885–1894. PMLR, 2017.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25, 2012.
  * Lee and Choi [2018] Yoonho Lee and Seungjin Choi.  Gradient-based meta-learning with learned layerwise metric and subspace.  In International Conference on Machine Learning, pages 2927–2936. PMLR, 2018.
  * Li et al. [2018] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski.  Measuring the intrinsic dimension of objective landscapes.  arXiv preprint arXiv:1804.08838, 2018.
  * Li et al. [2022] Tao Li, Lei Tan, Zhehao Huang, Qinghua Tao, Yipeng Liu, and Xiaolin Huang.  Low dimensional trajectory hypothesis is true: Dnns can be trained in tiny subspaces.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):3411–3420, 2022.
  * Li et al. [2023] Guanghao Li, Li Shen, Yan Sun, Yue Hu, Han Hu, and Dacheng Tao.  Subspace based federated unlearning, 2023.
  * Lin et al. [2023] Shen Lin, Xiaoyu Zhang, Chenyang Chen, Xiaofeng Chen, and Willy Susilo.  Erm-ktp: Knowledge-level machine unlearning via knowledge transfer.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 20147–20155, 2023.
  * Liu et al. [2018] Zhenhua Liu, Jizheng Xu, Xiulian Peng, and Ruiqin Xiong.  Frequency-domain dynamic pruning for convolutional neural networks.  Advances in neural information processing systems, 31, 2018.
  * McInnes et al. [2018] Leland McInnes, John Healy, and James Melville.  Umap: Uniform manifold approximation and projection for dimension reduction.  arXiv preprint arXiv:1802.03426, 2018.
  * Netzer et al. [2011] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  2011\.
  * Regulation [2018] General Data Protection Regulation.  General data protection regulation (gdpr).  Intersoft Consulting, Accessed in October, 24(1), 2018.
  * Rosenfeld et al. [2020] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter.  Certified robustness to label-flipping attacks via randomized smoothing.  In International Conference on Machine Learning, pages 8230–8241. PMLR, 2020.
  * Saha et al. [2021] Gobinda Saha, Isha Garg, and Kaushik Roy.  Gradient projection memory for continual learning.  arXiv preprint arXiv:2103.09762, 2021.
  * Shokri et al. [2017] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models, 2017.
  * Simonyan and Zisserman [2015] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition, 2015.
  * Springenberg et al. [2015] Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller.  Striving for simplicity: The all convolutional net, 2015.
  * Wang et al. [2021] Shipeng Wang, Xiaorong Li, Jian Sun, and Zongben Xu.  Training networks in null space of feature covariance for continual learning.  In Proceedings of the IEEE/CVF conference on Computer Vision and Pattern Recognition, pages 184–193, 2021.
  * Xiao et al. [2017] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * Xu et al. [2023] Heng Xu, Tianqing Zhu, Lefeng Zhang, Wanlei Zhou, and Philip S Yu.  Machine unlearning: A survey.  ACM Computing Surveys, 56(1):1–36, 2023.

Appendix

##  Appendix A Experiment Setups

We validate UNSC on several datasets using multiple networks. We split the
original training set with 90% as the training set and the remaining 10% as
the validation set. We monitor the model’s accuracy on the validation set
during training and set early stop the training with patience set as $30$. We
train the original model $\theta_{o}$ and retrained model $\theta_{r}$, with
SGD optimizer using an initial learning rate of $0.1$ and decrease it by 0.2
at milestones of epoch $60,120$ and $160$, respectively. In the unlearning
stage, we chose the best learning rate for different datasets&networks. Table
4 lists the training details.

Table 4: Experiment details

Dataset | Network | Batch size | Optimizer | Training $\theta_{o}$ and $\theta_{r}$ | Unlearning
---|---|---|---|---|---
lr | wd | epoch | lr | wd | epoch
FashionMNIST | AlexNet | $512$ | SGD | $0.1$ | $0.0005$ | $200$ | $0.0005$ | $0$ | $15$
SVHN | VGG11 | $512$ | SGD | $0.1$ | $0.0005$ | $200$ | $0.03$ | $0$ | $15$
CIFAR-10 | AllCNN | $512$ | SGD | $0.1$ | $0.0005$ | $200$ | $0.04$ | $0$ | $25$
CIFAR-100 | ResNet18 | $512$ | SGD | $0.1$ | $0.0005$ | $200$ | $0.04$ | $0$ | $25$

##  Appendix B Additional Results

###  B.1 UNSC under different settings

For the FashionMNIST and SVHN datasets, we randomly select $1$ to $5$ classes
to unlearn. Tables 5 and 6 present the results, and Figures 6 and 7 show the
comparisons of class-wise accuracy. On the CIFAR-100 dataset, we randomly
chose $10,20,30,40,50$ classes to unlearn. Table 7 records the results on
CIFAR-100, and Figure 8 plots the class-wise accuracy for $10$ class case. On
all datasets, UNSC can successfully unlearn the target classes (as verified by
the low $Acc_{\mathcal{D}_{ut}}$) and, in the meantime, get a higher
performance than the original model on the remaining classes, i.e., higher
$Acc_{\mathcal{D}_{rt}}$.

(a) Unlearn $1$ class

(b) Unlearn $3$ classes

(c) Unlearn $4$ classes

(d) Unlearn $5$ classes

Figure 6: Class-wise accuracy of the original model, the retrained model, and the model obtained by UNSC on FashionMNIST. We present the results of unlearning different numbers of classes. Table 5: Performance evaluation of UNSC on FashionMNIST. #Classes | Original model | Retrain | UNSC | Accuracy Gain
---|---|---|---|---
$Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$ | $Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$ | $Acc_{\mathcal{D}_{rt}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$ | $\Delta Acc_{\mathcal{D}_{r}}(\uparrow)$
1 | $93.58_{\pm 0.29}$ | $80.97\pm 1.44$ | $95.19_{\pm 0.20}$ | $0.00_{\pm 0.00}$ | $95.23_{\pm 0.27}$ | $0.67_{\pm 0.17}$ | $1.65\pm 0.30$
2 | $94.64_{\pm 0.35}$ | $83.03_{\pm 0.54}$ | $96.16_{\pm 0.04}$ | $0.00_{\pm 0.00}$ | $95.38_{\pm 0.38}$ | $0.80_{\pm 0.29}$ | $0.74\pm 0.26$
3 | $95.88_{\pm 0.22}$ | $84.00_{\pm 0.33}$ | $97.42_{\pm 0.08}$ | $0.00_{\pm 0.00}$ | $96.80_{\pm 0.29}$ | $1.16_{\pm 0.59}$ | $0.91\pm 0.21$
4 | $95.55_{\pm 0.22}$ | $87.47_{\pm 0.31}$ | $96.91_{\pm 0.02}$ | $0.00_{\pm 0.00}$ | $97.19_{\pm 0.21}$ | $0.35_{\pm 0.41}$ | $1.64\pm 0.21$
5 | $95.47_{\pm 0.26}$ | $89.17_{\pm 0.26}$ | $94.91_{\pm 1.93}$ | $0.00_{\pm 0.00}$ | $97.88_{\pm 0.15}$ | $0.04_{\pm 0.02}$ | $2.41\pm 0.24$

(a) Unlearn $1$ class

(b) Unlearn $3$ classes

(c) Unlearn $4$ classes

(d) Unlearn $5$ classes

Figure 7: Class-wise accuracy of the original model, the retrained model, and the model obtained by UNSC on SVHN. We present the results of unlearning different numbers of classes. Table 6: Performance evaluation of UNSC on SVHN.  #Classes | Original model | Retrain | UNSC | Accuracy Gain
---|---|---|---|---
$Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$ | $Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$ | $Acc_{\mathcal{D}_{rt}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$ | $\Delta Acc_{\mathcal{D}_{r}}(\uparrow)$
1 | $95.52_{\pm 0.12}$ | $91.30_{\pm 0.30}$ | $95.56_{\pm 0.23}$ | $0.00_{\pm 0.00}$ | $95.74_{\pm 0.17}$ | $0.00_{\pm 0.00}$ | $0.22\pm 0.09$
2 | $95.34_{\pm 0.14}$ | $94.11_{\pm 0.30}$ | $96.33_{\pm 0.08}$ | $0.00_{\pm 0.00}$ | $96.44_{\pm 0.15}$ | $0.00_{\pm 0.00}$ | $1.10\pm 0.09$
3 | $95.39_{\pm 0.15}$ | $94.41_{\pm 0.13}$ | $95.90_{\pm 1.15}$ | $0.00_{\pm 0.00}$ | $96.74_{\pm 0.16}$ | $0.01_{\pm 0.02}$ | $1.35\pm 0.11$
4 | $95.80_{\pm 0.20}$ | $94.03_{\pm 0.05}$ | $96.99_{\pm 0.13}$ | $0.00_{\pm 0.00}$ | $97.51_{\pm 0.10}$ | $0.01_{\pm 0.01}$ | $1.70\pm 0.12$
5 | $94.85_{\pm 0.08}$ | $95.34_{\pm 0.22}$ | $96.61_{\pm 0.17}$ | $0.00_{\pm 0.00}$ | $97.48_{\pm 0.04}$ | $0.00_{\pm 0.00}$ | $2.62\pm 0.13$

Figure 8: Class-wise accuracy of the original model, the retrained model, and the model obtained by UNSC on CIFAR-100.We randomly unlearn 10 classes. Table 7: Performance evaluation of UNSC on CIFAR-100. #unlearn classes | Original model | Retrain | UNSC | Accuracy Gain
---|---|---|---|---
$Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$ | $Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$ | $Acc_{\mathcal{D}_{r}}(\uparrow)$ | $Acc_{\mathcal{D}_{ut}}(\downarrow)$ | $\Delta Acc_{\mathcal{D}_{r}}(\uparrow)$
10 | $75.36_{\pm 0.34}$ | $72.07_{\pm 1.18}$ | $75.77_{\pm 0.22}$ | $0.00_{\pm 0.00}$ | $76.16_{\pm 0.35}$ | $1.80_{\pm 0.16}$ | $0.80\pm 0.26$
20 | $74.98_{\pm 0.32}$ | $75.20_{\pm 0.66}$ | $76.44_{\pm 0.21}$ | $0.00_{\pm 0.00}$ | $76.85_{\pm 0.23}$ | $0.67_{\pm 0.27}$ | $1.87_{\pm 0.15}$
30 | $74.40_{\pm 0.18}$ | $76.50_{\pm 0.78}$ | $75.81_{\pm 0.26}$ | $0.00_{\pm 0.00}$ | $77.61_{\pm 0.10}$ | $0.43_{\pm 0.08}$ | $3.21_{\pm 0.20}$
40 | $73.94_{\pm 0.27}$ | $76.65_{\pm 0.52}$ | $76.77_{\pm 0.12}$ | $0.00_{\pm 0.00}$ | $78.52_{\pm 0.22}$ | $0.31_{\pm 0.13}$ | $4.58_{\pm 0.32}$
50 | $73.73_{\pm 0.35}$ | $76.32_{\pm 0.47}$ | $76.80_{\pm 0.15}$ | $0.00_{\pm 0.00}$ | $79.64_{\pm 0.27}$ | $0.21_{\pm 0.09}$ | $5.91_{\pm 0.27}$

###  B.2 Loss Contours

We provide loss contours of SVHN, FMNIST, and CIFAR-100 in Figure 9. Similar
to Figure 3(b), on all datasets, loss contour shows the same pattern: loss
remains approximately the same when altering the model’s parameters in the
null space.

(a) FashionMNIST

(b) SVHN

(c) CIFAR-100

Figure 9: Loss contours on FashionMNIST, SVHN, and CIFAR-100

###  B.3 Distributions of Pseudo-lables

We compare the distributions of pseudo-labels on FashionMNIST, SVHN, and
CIFAR-100 datasets. On all datasets, the assigned pseudo-labels closely align
with the predictions given by the retrained model.

(a) FashionMNIST

(b) SVHN

(c) CIFAR-100

Figure 10: Distributions of pseudo labels and labels assigned by the retrained
model: (a) FashionMNIST, (b) SVHN, (c) CIFAR-100.

###  B.4 Ablation Studies on SVHN, CIFAR-10, and CIFAR-100

Following the same setting in Section 6, we randomly select one class on SVHN
and CIFAR-10 (ten classes on CIFAR-100) and unlearn all the samples. Tables 8,
9, and 10 present ablation results.

Table 8: Ablation results on SVHN. Exp. ID |  | Original
---
model
| Retrain
---
model
RL |  | Null
---
space
| Pesudo-
---
labeling
$Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$
I | $\checkmark$ |  |  |  |  | $95.52_{\pm 0.12}$ | $91.30_{\pm 0.30}$
II |  | $\checkmark$ |  |  |  | $95.56_{\pm 0.23}$ | $0.00_{\pm 0.00}$
III |  |  | $\checkmark$ |  |  | $75.87_{\pm 8.67}$ | $1.17_{\pm 0.16}$
IV |  |  | $\checkmark$ | $\checkmark$ |  | $93.64_{\pm 0.71}$ | $2.96_{\pm 2.11}$
V |  |  |  | $\checkmark$ | $\checkmark$ | $95.74_{\pm 0.17}$ | $0.00_{\pm 0.00}$
Table 9: Ablation results on CIFAR-10. Exp. ID |  | Original
---
model
| Retrain
---
model
RL |  | Null
---
space
| Pesudo-
---
labeling
$Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$
I | $\checkmark$ |  |  |  |  | $92.10_{\pm 0.29}$ | $79.93_{\pm 1.72}$
II |  | $\checkmark$ |  |  |  | $93.22_{\pm 0.18}$ | $0.00_{\pm 0.00}$
III |  |  | $\checkmark$ |  |  | $82.88_{\pm 2.62}$ | $3.30_{\pm 0.83}$
IV |  |  | $\checkmark$ | $\checkmark$ |  | $92.71_{\pm 0.31}$ | $2.10_{\pm 0.33}$
V |  |  |  | $\checkmark$ | $\checkmark$ | $93.09_{\pm 0.25}$ | $1.30_{\pm 0.59}$
Table 10: Ablation results on CIFAR-100. Exp. ID |  | Original
---
model
| Retrain
---
model
RL |  | Null
---
space
| Pesudo-
---
labeling
$Acc_{\mathcal{D}_{rt}}$ | $Acc_{\mathcal{D}_{ut}}$
I | $\checkmark$ |  |  |  |  | $75.36_{\pm 0.34}$ | $72.07_{\pm 1.18}$
II |  | $\checkmark$ |  |  |  | $75.77_{\pm 0.22}$ | $0.00_{\pm 0.00}$
III |  |  | $\checkmark$ |  |  | $37.63_{\pm 1.98}$ | $5.27_{\pm 0.48}$
IV |  |  | $\checkmark$ | $\checkmark$ |  | $73.41_{\pm 0.47}$ | $0.30_{\pm 0.22}$
V |  |  |  | $\checkmark$ | $\checkmark$ | $76.16_{\pm 0.35}$ | $1.80_{\pm 0.16}$