arXiv:2012.15721v1 [cs.LG] 31 Dec 2020

Coded Machine Unlearning
Nasser Aldaghri

Hessam Mahdavifar

Ahmad Beirami

University of Michigan

University of Michigan

Facebook AI

aldaghri@umich.edu

hessam@umich.edu

beirami@fb.com

Abstract
Models trained in machine learning processes may store information about individual samples usedin the training process. There are many cases where the impact of an individual sample may need
to be deleted and unlearned (i.e., removed) from the model. Retraining the model from scratch after
removing a sample from its training set guarantees perfect unlearning, however, it becomes increasingly
expensive as the size of training dataset increases. One solution to this issue is utilizing an ensemble
learning method that splits the dataset into disjoint shards and assigns them to non-communicating weaklearners and then aggregates their models using a pre-defined rule. This framework introduces a trade-off
between performance and unlearning cost which may result in an unreasonable performance degradation,
especially as the number of shards increases. In this paper, we present a coded learning protocol where
the dataset is linearly coded before the learning phase. We also present the corresponding unlearning
protocol for the aforementioned coded learning model along with a discussion on the proposed protocol’s
success in ensuring perfect unlearning. Finally, experimental results show the effectiveness of the codedmachine unlearning protocol in terms of performance versus unlearning cost trade-off.

1

Introduction

Machine learning (ML) models are being used for different purposes, e.g., regression, classification, andclustering. They have been the subject of extensive research interest in the past decade. Influential works
in the literature such as [1–4] have enabled machine learning models to perform well on complex tasks.
Given the abundance of data, machine learning has become ubiquitous. Once an ML model is trained, somesamples in the training dataset might be required to be removed due to various reasons, e.g., to satisfy
users’ requests of data removal, or due to discovery of corrupt low-quality samples or adversarially modified
samples that are specifically created to negatively affect the performance of the ML model. Straightforward
removal of these samples from storage units may not achieve complete removal since ML models trainedon such samples still retain information about them. This problem has risen in the literature and several
methods have been proposed to handle these requests. As ML models are trained on large datasets, removalof samples becomes more expensive; hence, efficient removal protocols are desired to enable fast removal ofsamples from these models.

1.1

Our contribution

In this paper, we look into perfect machine unlearning for regression problems. We consider an ensemble
learning setup similar to the one presented in [5] where the dataset is sharded at the master node and assigned to non-communicating weak learners to be trained independently from each other and their models
1Average test MSE

Undesirable region

Uncoded machine unlearning

Desirable region

Original learning algorithm

Unachievable region

Average unlearning cost

Figure 1: Performance vs unlearning cost trade-off of the uncoded machine unlearning proposed in [5].

are then aggregated at the master node. In this setup, the cost of unlearning is the time required to retrain
the affected weak learners trained on the desired samples, which is directly related to the size of the shards
as smaller shards incur less unlearning cost; however, this may be at the cost of degraded performance. Figure 1 shows the performance versus unlearning cost trade-off for the uncoded machine unlearning protocolpresented in [5]. We aim to design a protocol that operates within the desirable region shown in the figure.
In this figure the original learning algorithm, where a single learner is trained on the entire uncoded training
dataset, sets the lower bound of the achievable mean squared error (MSE), which may be at an unreasonable unlearning cost for various applications. We present a new framework for encoding the dataset prior
to training that can potentially outperform uncoded machine unlearning in terms of performance versus unlearning cost trade-off as shown in Figure 1. We show that the proposed protocol can provide significant
improvements in performance when compared to uncoded machine unlearning and discuss certain intuitions
behind the proposed protocol’s success.
More specifically, we consider a regression problem and present a coded learning protocol that utilizes arandom linear coding scheme to combine the training samples randomly into a smaller number of samples
which are then used to train weak learners with the goal of enabling efficient unlearning. Then, we present anefficient unlearning protocol that utilizes the aforementioned coding scheme to remove the unlearned samples
from the training dataset as well as to update the model to completely remove such samples from the model.
This is done while maintaining a better performance compared to the uncoded machine unlearning. One of
the inspirations of utilizing random codes in this work is the success they have shown in different information
processing scenarios such as random codes to achieve channel capacity [6], random projections in learningkernels [7, 8], and random projection in compressed sensing [9, 10]. Random projections [7] enable efficientlearning of large-scale kernels that are capable of modeling nonlinear relationships. We take advantage ofrandom projections to model nonlinear relationships and propose the use of random linear codes to enableefficient unlearning. Finally, we show the success of the proposed protocol by showing experimental resultsof the performance against the unlearning cost on a few realistic datasets as well as synthetic datasets.

1.2

Related work

The problem of how to efficiently remove information about a training sample from a trained ML model,
referred to as machine unlearning [11], has been recently introduced in the literature. In this scenario, a2trustworthy party aims to train an ML model on a training dataset of raw data with the guarantee that
unlearning requests are satisfied by removing sample from the training dataset as well as removing any traceof them in the trained ML model. One straightforward approach to perfectly satisfy this requirement isto retrain the model from scratch after removing the samples that need to be unlearned from the training
dataset. However, as large training datasets are increasingly available and used in these models, retraining
becomes prohibitively expensive.
Several works have been proposed in the literature to provide efficient unlearning solutions. Perfect unlearning ensures guaranteed removal of data from learning models. For example, [11] uses statistical query
learning to speed up the unlearning process. A more general framework for perfect unlearning considers an
ensemble learning setup where a master node shards the training dataset and assigns the shards to noncommunicating weak learners that are trained independently from each other, and then aggregates theirmodels using a certain aggregation function [5].
A different approach to the unlearning problem is known as statistical unlearning, where the data removal
protocols offer statistical guarantees of removal, similar to statistical methods for estimating leave-one-out
cross validation [12–15]. For example, the work in [16] presents a statistical formulation of data deletionfrom machine learning similar to differential privacy and describes a method to achieve deletion in linear
and logistic regression scenarios. A formulation of data deletion problems using cryptographic notations ispresented in [17] with a brief discussion on deletion in ML models. Other works on statistical unlearning
are also presented in [18–21]. Statistical unlearning is typically suitable for convex models which are wellbehaving; however, they often provide no guarantees for non-convex models.
Another closely related line of work is concerned with individual samples’ privacy; this is relevant in cases
where the samples contain highly sensitive information and they need to be kept secret even from the MLmodel. Examples of privacy-preserving ML include works based on differential privacy such as [22–24] andprivacy-preserving learning such as [25–30]. A major distinction between this line of work and machine unlearning is that samples do not need to be kept private in machine unlearning, but the requests of unlearning
need to be honored.
Different methods proposed in the ML literature can be useful in reducing the retraining cost of ML models. One method used to reduce the number of the randomly projected features of samples is known asdata-dependent random projections where feature projections are sampled from some data-dependent distributions [8, 31, 32]. Another method is known as data distillation where the dataset is compressed using a
distillation algorithm [33, 34]. However, since these methods are date-dependent, they inherently leak information about samples and their algorithms, i.e., random projections algorithms or distillation algorithms,
need to be updated accordingly to mitigate any leakage of information about such samples to ensure perfect unlearning after retraining the model. Consequently, this process incurs an additional overhead in theunlearning cost that cannot be neglected.

1.3

Organization

The rest of paper is organized as follows. In Section 2 the problem setup and the proposed protocol are presented including the proposed protocols for coded learning and unlearning. In Section 3 several experiments
are conducted to evaluate the proposed protocol using certain datasets along with a discussion on the intuition behind the protocol’s success. Finally, the paper is concluded along with discussion on possible future
work directions in Section 4.
3

2

Problem Setup and Proposed Protocol

In this section the setup for the problem of machine learning and unlearning is described along with theproposed protocol for regression models. First, a description of a regression learning model along with its
metrics is discussed. Then, the proposed protocol for coded machine learning using data encoding of the
training dataset prior to launching the learning model is presented along and a specific encoder for regression
models is introduced. Moreover, the corresponding protocol for perfect coded unlearning is introduced, andits success is shown.

2.1

Problem setup

Consider a setup where the training dataset is a matrix denoted as [X, y] whose rows are the independentand identically distributed (i.i.d.) samples xi along with their response yi for i = 1, 2, ..., n, where xi ∈ X
and yi ∈ Y. We denote n as the number of samples, d as the number of features. Columns of X are referred
to as the features while y is referred to as the response variable, whose elements are of the form
yi = f (xi ) + .

(1)

The training dataset is used to train a learning model to produce a model, i.e., a function f : X → R, thatminimizes a loss function. For regression problems, the loss ` is a function that measures the goodness of fitof the model f ∈ F on the training dataset, typically expressed asn`(X, y; f ) =1X(yi − f (xi ))2 + Ω(kf kF ),
n i=1

(2)

where Ω is a regularization term. The learning model finds a function f ∗ that minimizes the loss function
as follows
f ∗ = argmin `(X, y; f ).

(3)

f ∈F

The Representer theorem is a powerful theorem for general regression problems. It states that for the regularized loss in (2), when using a a strictly increasing function Ω, and a kernel k : X × X → R with F as its
associated Reproducing Kernel Hilbert Space (RKHS), then the minimizer f ∗ of the loss function above isexpressed in the form [35]
f∗ =

n
X

wi k(., xi ),

(4)

i=1

where wi ∈ R. This powerful theorem translates any regression problem, even nonlinear problems, as a linear
problem in the RKHS. Hence, the problem can be transformed and re-expressed to be as follows
y = Kw + ,

(5)where K is an n × n kernel matrix whose elements kij = k(xi , xj ), w is a n × 1 coefficient vector, and  is an × 1 noise vector. The L2 -regularized learning model for this kernel problem, also known as ridge regression,aims to estimate w that minimizes the loss functionn`(K, y; w) =1X
(yi − kTi w)2 + λwT w,
n i=1
4

(6)

where ki is the i-th row of K, and λ is the regularization parameter. We denote the resulting model trainedon [X, y] when initialized with parameters h as f ∗ = Mh (X, y).
These kernel methods suffer greatly in regimes where the size of training datasets is large. Specifically, fora dataset with a fixed number of features, computations of the elements in the kernel matrix result in an
additional complexity of O(n2 ) on top of the optimization method used to solve the problem. One method ofresolving this issue is proposed in [7], which suggests using random projections of the features to a relatively
low-dimensional space compared to n. This gives a good approximation of the function f ∗ using random
projections to a D-dimensional space where d < D  n, which enables efficient linear regression methods to
be used to solve the regression problem. These random projections enable an approximation of the targetfunction f ∗ , denoted as fˆ, expressed as follows
fˆ(x) =DX

φ(xT θ i + bi )wi + ,

(7)

i=1

where φ is an activation function, θ i and bi are chosen randomly from some distributions, wi ’s are thecoefficients to be estimated, and D is the desired dimension of the projected features [7]. This enables us
to apply this transformation of the original feature matrix X into another feature matrix Xp of size n × D,then we have the following
y = Xp w + ,

(8)where w are the coefficients to be estimated of size D × 1.
After the model has been trained, it is used for prediction until a request of unlearning samples arrives. Once
unlearning requests arrive, the model stops processing any prediction requests and launches the unlearning
protocol. Machine unlearning is formulated as follows: when an unlearning request of sample [xTu , yu ] fromthe training dataset is received, the model must be immediately updated to remove any effect of this sample,
i.e., unlearn it, from Mh (X, y). The unlearning protocol is denoted as U and its output is an updated model
denoted as U(Mh (X, y), [xu , yu ]). In this paper, we require U to be a perfect unlearning protocol defined asfollows [5].
Definition 1 (perfect machine unlearning) An unlearning protocol U on model Mh (X, y) is said to be
perfect if the output of the unlearning protocol removing the sample [xTu , yu ], denoted as U(Mh (X, y), [xTu , yu ]),is a statistical draw from the distribution of the models trained on [X \xu , y\yu ], denoted as Mh (X \xu , y\yu ),where [X \xu , y\yu ] denotes the training dataset [X, y] after removing the sample [xTu , yu ] from it.
Perfect unlearning protocols ensure the complete removal of samples form the model but may suffer in termsof their efficiency. Removing the samples from the training dataset and retraining a model from scratch
achieves perfect unlearning. However, the major hurdle of this approach is the extended delay time required
to unlearn a sample as retraining is the process that mainly causes this delay; hence, it is desirable to design
efficient unlearning protocols that can be used for large scale datasets.

2.2

Proposed protocol

The proposed protocol is described in two parts, learning and unlearning. In the learning phase we present
a method for encoding the training dataset prior to training and describe a specific coding scheme for aregression learning model. After the model has been trained, we transition into the unlearning phase, we
describe an efficient method to process unlearning requests using the coded training dataset and update themodel to perfectly unlearn the desired samples.
5

Enc de....

Agg ega

Figure 2: Proposed coded learning setup.

2.2.1

Learning

The proposed protocol introduces the idea of data encoding prior to training the ensemble model as shownin Figure 2. The learning model M, also referred to as the master node, is launched to learn a regression
model whose training dataset is assumed to have been preprocessed. The model starts by passing the training
dataset through an encoder to produce a sharded coded training dataset that contains r coded shards. Then,each coded shard j is used to train a weak learner Lj to produce a model denoted as fj∗ . Once these weaklearners are trained, the model M is ready for prediction. When sample x is passed to the model M, it isdirectly passed to each of the weak learners to produce weak predictions fj∗ (x) for j = 1, 2, ..., r, then themodel M computes the final prediction f ∗ (x) by applying an aggregation function a : Rr → R, such as
averaging, a majority vote, etc, as followsf ∗ (x) = a(f1∗ (x), f2∗ (x), ..., fr∗ (x)).

(9)

For linear regression models, or nonlinear regression models coupled with random projections, we know thatthe generated model fj∗ is the corresponding weights w∗j . Once all weak learners Lj ’s have been trained, M
produces a matrix W ∗ whose columns are the estimated coefficients from the weak learners as follows
W ∗ = [w∗1 , w∗2 , ..., w∗r ].

(10)

Once W ∗ is available, the model M computes the aggregate prediction weights by computing the mean of
the weight vectors of the weak learners to produce w∗agg , which is directly used at the time of prediction,
bypassing the weak predictions computations. When the sample x is passed as input, the predicted output
isf ∗ (x) = xT w∗agg .

(11)

The encoding of the training dataset is a method to produce a new training dataset with the goal of reducing
learning and unlearning costs. Coding can be viewed as a method to incorporate multiple samples from theuncoded training dataset into a single sample of the coded training dataset to enable efficient learning andunlearning. In other words, although we have less number of coded samples for weak learners, each of thesecoded samples is created from multiple uncoded samples, enabling the model to learn these uncoded samples
indirectly. First, let us define an encoder as follows.
6

Algorithm 1 Learning (Learn)
1: Input: [X, y], s, r, ρ.
2: Output: W ∗ , {X, y}, G.
3: At master node M, do
4: if s 6= 1 then5:{X, y}, G ← LinearEnc([X, y], s, r, ρ).
6: else7:{X, y} = {[X, y]}8:
G = [1]9: end if
10: Send [X i , yi ] to weak learner Li
11: At weak learner Li , do
12: w∗i ← argminw `([X i , yi ], w)
13: Send w∗
i to M
14: At master node M, do
15: W ∗ = [w∗, w∗2 , ..., w∗r ]
1P
r
1
∗
∗
16: wagg = r
i=1 wiAlgorithm 2 Linear encoder (LinearEnc)
1: Input: [X, y], s, r, ρ.
2: Initialization: G = 0s×r , {X, y} = empty.
3: Output: {X, y}, G.
4: while G is not full column rank do
5:
Set G = 0s×r
6:
while G has any all-zero rows do
7:
G ← RandMatrix(s, r, ρ)
8:
end while
9: end while
10: Split [X, y] into s submatrices [Xi , yi ] of equal size
11: for j in range(r) do
Ps
Ps
12:
{X, y}.append([( i=1 gij Xi ), ( i=1 gij yi )])13: end for
14: return {X, y}, G

Definition 2 (encoder) An encoder with rate τ is defined as a function that transforms the original training dataset with n samples into another dataset with m samples while maintaining the same number offeatures. The rate of this encoder is
τ=

n
.
m

(12)

When using shards of equal size, as considered in this work, the rate can also be viewed as the ratio of thenumber of uncoded shards to the number of coded shards. The rate and design of the encoder are now
additional parameters of the model that require tuning when building a model. It is worth noting that thedesign of the encoder itself for a fixed rate directly affects the unlearning cost of the overall model as well as
the performance, as will be clarified later. Hence, it should be carefully considered when designing a model.
The proposed coded learning model for linear regression is described in Algorithm 1. The learning algorithm
takes the training dataset [X, y] and code parameters s, r, ρ as inputs and outputs the coded training dataset
along with the coding matrix and the trained model. The model M utilizes a linear encoder described in7

Algorithm 2 to encode the training dataset using the provided code parameters. The linear encoder takes
the desired code parameters s, r, ρ along with the training dataset [X, y] as inputs and processes it as follows:[X, y] is divided into s disjoint submatrices of equal size, i.e., each has n = ns samples, denoted as [Xi , yi ]for i = 1, 2, ..., s. These are encoded using a matrix G, described next, to produce [X j , yj ], for j = 1, 2, ..., r.
The output of this encoder is {X, y} whose elements are the shards used to train the corresponding weaklearners, i.e., shard j is used to train the j-th weak learner to produce the corresponding optimum w∗j . Notethat the code parameters should keep the coded shards in the original regime of the original dataset; forexample, if n > d, then n > d.
Following the success of random codes in information theory [6] and random projections in signal processing [9, 10] and machine learning [7], we propose to use a random binary matrix generator (RandMatrix) togenerate G. In this protocol, the matrix G is of size s × r and density 0 < ρ 6 1. We desire the matrix G to
be a tall matrix, i.e., r 6 s, since our goal is to reduce the number of coded samples used for training. Sincer 6 s, G needs to satisfy two conditions: each row of G should have at least one nonzero element, and it
should have full rank. The first condition ensures that all the shards are used in training the model, while
the second condition ensures that every weak learner has a training dataset that is unique from all otherweak learners. Another consequence of using a code with r 6 s is that it lowers the initial learning cost bya factor of τ compared to uncoded machine unlearning. For example, for some s and r then we only needto train r learners using n/s coded samples each, compared to s learners each with n/s uncoded samples in
uncoded machine unlearning.

2.2.2

Unlearning

Now that the model has been trained on the coded training dataset, we proceed to describe a protocol
to unlearn samples from this model. Our goal is to remove such samples from the coded shards as wellas to remove any trace of such samples from the affected weak learners where such samples appear. The
unlearning protocol for the aforementioned learning protocol is described in Algorithm 3. The algorithm’s
inputs are the coded dataset {X, y}, the samples to be unlearned [Xu , yu ], their indices u in the uncoded
training dataset [X, y], the matrix G, and the original model estimated coefficients W ∗ . The algorithm’sf∗ .
e ye}, and the updated estimated coefficients of the model W
outputs are the updated coded dataset {X,Essentially, the algorithm needs to identify the uncoded shards that include the samples with indices u as
well as their corresponding coded shards using the matrix G. The samples first need to be removed fromthe coded shard by subtracting them from the corresponding coded samples in all coded shards where they
appear to eliminate their effect from the coded shards. Once all the coded shards are updated, they are thenused to update their corresponding weak learners to unlearn these samples from the weak learner models
followed by updating the final aggregate model using the updated weak learners estimates. The following
lemma proves that the algorithm guarantees perfect unlearning.

Lemma 1 The unlearning protocol described in Algorithm 3 perfectly unlearns the desired samples from themodel in the sense of Definition 1.
Proof: Without loss of generality, we consider a single sample [xTu , yu ] that is requested to be unlearned
from the model, which appears in [X j , yj ] that is used to train the j-th weak learner whose model is denoted
ej , yej ] by subtracting the sample
by Mhj (X j , yj ). First, the protocol updates this training dataset to be [XT[xu , yu ] from the corresponding coded sample in order to remove it from the dataset [X j , yj ]. Then, theej , yej ], is trained from scratch and the resulting model
j-th weak learner, whose new training dataset is [X0hTej , yej ), where h0 is chosen
is denoted as U(Mj (X j , yj ), [xu , yu ]). This model is equivalent to a model Mhj (X8Algorithm 3 Unlearning (Unlearn)
1: Input: {X, y}, [Xu , yu ], u, G, W ∗ .
2: Initialization: j = empty.

f∗ .
e y
e}, W
3: Output: {X,
4: At master node M, doe ye} = {X, y}
5: Set {X,f∗ = W ∗6: Set W
7: for i in range(length(u)) do8:s0 ← index of the uncoded shard containing [xTi , yi ]i0 ← index of [xTi , yi ] within shard s0
j0 ← indices of nonzero elements in row s0 of G
for j 0 in j0 doe
xj 0 i0 = e
xj 0 i0 − gs0 j 0 xi
yej 0 i0 = yej 0 i0 − gs0 j 0 yi
end for15:
j.append(j0 )16: end for
17: ju ← unique(j)ej , yej ] to weak learner Lj for all j ∈ ju
18: Send [X
19: At weak learner Lj , doe ej ; w)
20: w̃∗j ← argminw `(Xj , y
21: Discard the previous model w∗
j
22: Send w̃∗j to M
23: At master node M, dof ∗ with the updated w̃∗ for all j ∈ ju
24: Replace column j of W
j
P
r
1
∗
25: Set w̃∗
agg = ri=1 w̃i
9:
10:
11:
12:
13:
14:

randomly. Using the uniqueness property of the linear and ridge regression solutions, we have the following:
00

U(Mhj (X j , yj ), [xTu , yu ]) = Mhj (X j \ xu , yj \ yu ),(13)

for some random h00 . Hence, the desired sample is perfectly unlearned from the j-th weak learner. The
same argument applies to all other affected weak learners after removing the desired samples from theircorresponding training datasets. Therefore, as the resulting models from the affected weak learners are
updated along with re-calculating the aggregation function, the overall updated model perfectly unlearns
the desired samples from the model.
For large-scale problems, we can speed up the unlearning protocol even more. Using iterative optimization
methods one can start the optimization problem for the weak learners on the new training dataset using
the solution from their previous model. Specifically, for linear and ridge regression problems the resulting
model will always be the same as the one trained from scratch since these iterative methods will converge toa unique global minimizer regardless of the initialization. However, this cannot be used for other complex
models such as the over-parameterized multi-layer perceptron (MLP) since the training loss can be zero forthese models. Hence, when a sample is removed and the model is initialized from the previous model, it will
immediately converge since the training loss is already zero, but this solution was reached in part due to theremoved sample. Therefore, this approach in this over-parameterized scenario does not perfectly unlearn thesample.
The last design parameter of the coded learning is the generator matrix G. One of the properties of thematrix G used in the encoder is its density ρ, and it can be seen in Algorithm 3 that the density of G directly9affects the unlearning cost. For example, a sample whose corresponding row in G is dense requires updating
more weak learners than a sample whose corresponding row is sparse. Therefore, the design of such a matrix
is directly related to the efficiency of unlearning. If we aim to have the lowest unlearning cost for an encoderwith specific rate, we use the minimum matrix density that satisfies both of the aforementioned conditions
for the matrix G, which is ρ = 1r . This corresponds to the case where there is only one nonzero element ineach row of the matrix G, i.e., each sample only shows up exactly in one coded shard.
Remark: Since the choice of the encoder in Algorithm 1 is independent of the data, it does not leak any
information about the data itself and does not affect the perfect unlearning condition. However, other typesof data-dependent encoders may require additional steps to ensure the removal of the unlearned samples
from the encoder itself, which may introduce an additional overhead. An example of such encoders is one
that assigns samples to weak learners based on some properties of the training dataset itself. This leakage
of information, even if small, needs to be taken into account when designing perfect unlearning protocols.

3

Experiments

In this section, we present the simulation results of some experiments to compare the performance versus theunlearning cost on realistic datasets for two protocols: the uncoded machine unlearning protocol describedin [5] and the proposed coded machine unlearning protocol. The experiments simulate unlearning of a sample
from the training dataset, where the performance is measured in terms of the mean squared error and theunlearning cost is measured in terms of the time required to retrain the affected weak learner.
We utilize the sklearn.linear_model package [36], specifically, LinearRegression and/or Ridge
modules, to produce the simulation results for all the experiments. Since the cost of unlearning is related tothe size of the shards, we sweep the variable s while fixing the rate for the coded scenario and observe theperformance. Each point in the plots shows the average of a number of runs, where each run simulates theexperiment on a randomly shuffled dataset that is then split into training and testing datasets according to
the specified sizes. During each run, after splitting the dataset into training and testing, Algorithm 1 is run
first using s and r for a specific code with rate τ = rs and density ρ = 1r . Once the model is trained, a random
sample from the training dataset is chosen to be unlearned using Algorithm 3. After all the runs are done,
the performance is measured as the average mean squared error of the testing dataset, while the unlearning
cost is measured as the average time required to retrain the affected weak learners, since removing a sample
from the dataset has negligible cost.
For the simulations, datasets are preprocessed as follows, each column of the original feature matrix and the
response vector is normalized to be in the range [0, 1]. If the random projections approximation [7] is used as
described in (7), then the projections are done on the normalized features using a cosine activation function
and the following parameters
1
Id ),
2d
bi ∼ unif(−π, π).

θ i ∼ N (0,

3.1

(14)
(15)

Results

We conduct three experiments to evaluate the proposed protocol on realistic datasets. The first dataset is
known as the Physicochemical Properties of Protein Tertiary Structure dataset [37]. The goal is to use the10

0.0620.005=10 -4

Coded,-4

Uncoded,
Coded,

Average test MSE=10

Uncoded,0.058

Coded,

Uncoded
Coded, =2
Coded, =50.0045=10 -5=10 -5

Average test MSE

0.06

Uncoded,=10 -6=10 -6

0.056

0.054

0.004

0.0035

0.003

0.052

0.0025
0.05

0

0.01

0.02

0.03

0.04

0.05

0.06

0.07

0.6

0.08

0.8

1

1.2

1.4

Average unlearning cost (sec)

Average unlearning cost (sec)

1.6
10-3

Figure 4: Performance vs unlearning cost fordifferent rates τ using the Computer Activity
dataset [38], random projections of features toa 25-dimensional space, and λ = 10−3 .

Figure 3: Performance vs unlearning cost fordifferent values of λ using the Physicochemical
Properties of Protein Tertiary Structure dataset[37], random projections of features to a 300dimensional space, and a code of rate τ = 5.

9 original features to estimate the root mean square deviation. This dataset includes 45,730 samples, where
42,000 samples are for training and the rest are for testing. We consider random projections with D = 300.
The results shown in Figure 3 show the simulation results for multiple values of λ = 10−4 , 10−5 , 10−6 usinga code of rate τ = 5. It can be seen that coding provides a better performance compared to the uncodedmachine unlearning at lower unlearning cost, even when using regularization with different values.
The second dataset is known as the Computer Activity dataset [38]. It is concerned with estimating the
portion of time that the CPU operates in user mode using different observed performance measures. We
consider random projections of the original features to a space with D = 25. The dataset has 8,192 samples,with 12 original features, of which 7,500 samples are for training while the rest are for testing. The experiments use a regularization parameter λ = 10−3 and different code rates τ = 2, 5. The results are shownin Figure 4. In this figure, we observe that coding provides a better performance compared to the uncodedmachine unlearning at lower unlearning cost. Additionally, different rates allow for different achievable performance measures as evident in the figure. More on the effect of code rates will be discussed later in theexperiments on a large-scale synthetic dataset.
Finally, we experiment on the Combined Cycle Power Plant dataset [37]. The goal is to estimate the net
hourly electrical energy output using different ambient variables around the plant. The dataset has 9,568
samples, with 4 original features, of which 9,000 samples are for training while the rest are for testing. We
consider random projections with D = 20. The experiments use linear regression with no regularization anddifferent code rates τ = 2, 5 and their results are shown in Figure 5. For this case, there is no region ofcoding to operate in, and intuitively, we do not expect it to beat the performance of the original learningalgorithm with a single uncoded shard. However, although coding does not provide better trade-off in thiscase, it does not exhibit a worse trade-off either.
The above experiments show results for datasets with relatively small to moderate size and number of features. It remains to be seen if similar behavior can be observed if the dataset size as well as the number offeatures become much larger. The following experiment shows simulation results of a synthetic dataset generated as follows: a total of 600,000 samples are generated, each with i.i.d. features of size d = 100 drawn
from lognormal distribution with parameters µ = 1, σ 2 = 4, then passed through a random 3-layer MLP, followed by an output layer with standard normal noise term to generate the desired response variable. The
layers contain 50, 25, 50 nodes, respectively, with a sigmoid activation function and their weights and biases
11

0.0120.00550.005

0.0115

Average test MSE

Average test MSE

Uncoded
Coded, =2
Coded, =5
Coded, =10
Coded, =20
Coded, =40
Coded, =50
Coded, =100

Uncoded
Coded, =2
Coded, =50.0045

0.004

0.011

0.01050.0035

0.003
0.5

1

1.5

2

2.5

Average unlearning cost (sec)

3

0.01
10-1

3.5
10

-3

100

101

Average unlearning cost (sec)Figure 5: Performance vs unlearning cost for different rates τ using the Combined Cycle Power
Plant dataset [37] and random projections of features to a 20-dimensional space.

Figure 6: Performance vs unlearning cost forsynthetic data generated from an MLP withlognormal(1, 4) features using random projections to a 2,000-dimensional space, λ = 10−2 ,and codes of different rates τ .

are i.i.d. drawn from the standard normal distribution. We use λ = 10−2 and apply random projections
on the original features using the parameters described above and D = 2,000. The dataset is split into
500,000 samples for training and 100,000 for testing. The simulation results are shown in Figure 6. Notethat log-scale is used on the x-axis for a better demonstration of the curves for the coded scenarios. It canbe observed that as we increase the rate of the code, the unlearning cost decreases while minimum achievable performance increases. Hence, one can choose the maximum code rate that satisfies a performance close
to the original learning algorithm.

3.2

Discussion

The success of the proposed protocol is prominently seen in cases where uncoded machine unlearning exhibits
significant degradation in performance as unlearning cost decreases. One possible intuition into why thisphenomenon occurs is related to the samples used for training each of the weak learners. Influential samples
have been explored in the literature extensively [39]. As we previously discussed, coding is a method of
combining samples into the coded dataset, including these influential samples.
Let us examine the influence of individual samples on the performance of the trained model. We take twoof the previously considered datasets, the Computer Activity dataset [38] and the Combined Cycle Power
Plant dataset [37]. We conduct the following experiment: we randomly shuffle the data and split it intotraining and testing datasets with the same sizes as we used before, then we remove samples from the training
dataset according to some criteria, then train a single learner on the remaining samples and observe its test
MSE. We use two criteria of removal, the first is as follows: remove a sample if any of its original featureslie outside a certain percentiles. This criteria removes what we denote as outliers. The other criteria is asfollows: remove samples whose original features lie inside certain percentiles, this removes what we denoteas inliers. In other words, outliers are samples at the tails of the probability distribution function (PDF),
and inliers are the ones close to the median. We vary these percentiles symmetrically on both ends andobserve the performance on the testing data for multiple runs then compute the observed average test MSE.
Figure 7 shows the experiment results for the dataset with Computer Activity dataset and Figure 8 showsthe experiment results for the Combined Cycle Power Plant dataset. In Figure 7, we see a degradation in
performance as more outlier samples are removed that is much more significant than the case where inlier
12

0.04

0.04
Inliers removed
Outliers removed

0.035

0.03

Average test MSE

Average test MSE

0.03
0.025
0.02
0.015

0.025
0.02
0.015

0.01

0.01

0.005

0.005

0
0%

Inliers removed
Outliers removed

0.035

20%

40%

60%

80%

0
0%

100%

Percentage of remaining training samples

20%

40%

60%

80%

100%

Percentage of remaining training samples

Figure 7: Original learning algorithm’s performance vs percentage of remaining samples after
removal of outliers and inliers from the Computer
Activity dataset [38].

Figure 8: Original learning algorithm’s performance vs percentage of remaining samples after
removal of outliers and inliers from the Combined
Cycle Power Plant dataset [37].

samples are removed. On the other hand, in Figure 8, the performance of the model after removing outliers
and inliers is quite similar until we remove more than 50% of the samples, then a small gap appears between
the two curves that gets larger as the number of removed samples increases.
We believe that one explanation behind the behavior of the uncoded machine unlearning is related to theexistence of these influential samples, i.e., outlier samples. In particular, if influential samples exist in thedataset, then the uncoded machine unlearning suffers significant degradation as we increase the numberof shards and the proposed protocol can provide a better trade-off. On the other hand, if such influential
samples do not exist, then the uncoded machine unlearning does not exhibit any degradation in performanceas the number of shards increases, and as shown in the experiment in Figure 5, the proposed protocol does
not improve on the uncoded machine unlearning and it does not negatively affect it either. It is worth
noting that these influential samples exist in heavy-tailed distributions which are quite common in a rangeof real-world examples such as technology, social sciences and demographics, medicine, etc, where machinelearning is increasingly employed for these scenarios. In the aforementioned experiments, we observed that
if the probability distribution functions of some of the features have heavy tails, then we have a trade-off
for the uncoded machine unlearning and coding provides a better trade-off. However, if there are no heavy
tails in the probability distribution functions then we do not see this trade-off and, hence, coding does notprovide a better trade-off.
To verify this observation, we create three synthetic datasets with known feature distribution and known
relationship to the response variable. Each one of the datasets has d = 100 i.i.d. feature vectors whose
elements are drawn from lognormal(µ, σ 2 ) distribution to create the feature matrix X. Then, we map thesefeatures X to a degree 3 polynomial with no interaction terms, resulting in the following
Xp = [X, X ◦2 , X ◦3 ],(16)

where X ◦c is the element-wise c-th power of matrix X. The response variable is generated using (8) with
i.i.d. elements of w and  drawn from the standard normal distribution. The lognormal distribution has two
parameters, µ and σ 2 . We fix µ = 1 and vary σ 2 . As σ 2 increases, the tail becomes heavier; hence, we expect
the trade-off to be more evident. The number of samples in each dataset is 25,000 samples, of which 23,000
are used for training and the rest are used for testing. The simulated experiments for σ 2 = 0.1, 0.5, 0.7 areshown in Figure 9. The code used for all datasets has rate τ = 5. As can be seen from the figure, as we
increase the value of σ 2 , the tail becomes heavier and the trade-off becomes more significant for the uncodedmachine unlearning. Additionally, as the tail becomes heavier, the gain provided by the proposed protocol
13

0.25

0.02
2

Uncoded,
=0.1

2

=0.5

2

=0.7

Average test MSE

0.015

Coded,

Uncoded,
Coded,

02

2

Uncoded,0

5

10

Coded,

2

2

Inliers removed,

=0.1

2

=0.5

Inliers removed,

0.2

=0.5
2

2

=0.1

2

=0.5

2

=0.7

2

Outliers removed,

=0.1

2

Outliers removed,

Average test MSE

0.5

=0.7

=0.7

0.01

Inliers removed,
Outliers removed,

0.15

2

=0.1
=0.5
=0.7

0.1

0.005

0.05

0

0

0.05

0.1

0.15

0.2

0
0%

0.25

Average unlearning cost (sec)

20%

40%

60%

80%

100%

Percentage of remaining training samples

Figure 9: Performance vs unlearning cost for synthetic data with lognormal features with fixedµ = 1 and different values of σ 2 used in a polynomial of degree 3. The rate of the code is τ = 5.
The inset figure shows the PDFs of the original lognormal features of the considered datasetswith µ = 1 and different values of σ 2 .

Figure 10: Original learning algorithm’s performance vs percentage of remaining samples after
removal of outliers and inliers from the lognormal polynomial datasets.

in terms of the trade-off is more significant compared to the uncoded machine unlearning.
We also run experiments, same as the ones in Section 3.1 showing the effect of removing inliers versus removing outliers, for these datasets. We run the inlier and outlier removal process based on the original featuresand observe the performance on the trained model’s performance on the testing dataset. Figure 10 shows results of these experiments. Similar to what we observed in the realistic dataset experiments, for distributions
with heavier tails, removing outlier samples has more influence than inlier samples.
Additional experiments on synthetic datasets are shown in Appendix A. They include experiments withknown relationship between the features and response variable as well as a dataset generated using features
passed through a random 3-layer MLP to produce the response variable where we utilize random projections
to model this relationship.

4

Conclusion

In this work, we considered the problem of perfect machine unlearning for ensemble learning scenarios where
the model consists of a master node and multiple non-communicating weak learners trained on disjoint
shards of the training dataset. We focused on the trade-off between the performance and unlearning cost for
regression models. We presented a new method of learning called coded learning which can potentially enable
more efficient unlearning while exhibiting a better trade-off, in terms the performance versus the unlearning
cost, compared to the uncoded machine unlearning. We presented a protocol for coded learning along with alinear encoder for regression datasets as well as its corresponding unlearning protocol and showed its successin ensuring perfect unlearning.
We presented a handful of experiments to show the proposed protocol can succeed in providing a better
trade-off for various realistic datasets with different values of the underlying parameters. On the other hand,
we considered datasets for which the uncoded machine unlearning does not exhibit any trade-off between
14performance and unlearning cost and showed that coding in these scenarios maintains performance on parwith the uncoded machine unlearning. In the experiments, we showed that when using appropriate codes
one can potentially reduce the unlearning cost to a fraction of the unlearning cost for a single learner trainedon the entire dataset while observing a comparable performance to the one of a single learner. Finally,
discussions are provided on whether we should expect the proposed protocol to outperform the uncoded machine unlearning based on the existence of influential samples in the dataset and properties of the probability
distribution function of the dataset features.
We consider this work as a first step towards understanding the role of coding in machine unlearning. A few
possible directions of future work include extending the proposed protocol to concept classes with higher
capacity, such as deep neural networks. Studying different classes of codes beyond linear random codes forsupervised learning problems is also another possible avenue for research. Designing protocols for almost
perfect machine unlearning in convex/non-convex models where only statistical guarantees are required isanother area for future investigation. Finally, theoretical exploration of the interplay between influential
samples in conjunction with random coding and their impact on the final learned model is another interesting
direction for future work.

References[1] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings ofthe IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
[2] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in Advances in neural information processing systems, 2014, pp.
2672–2680.
[3] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin,“Attention is all you need,” in Advances in neural information processing systems, 2017, pp. 5998–6008.
[4] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, “Language models are unsupervised
multitask learners,” OpenAI blog, vol. 1, no. 8, p. 9, 2019.
[5] L. Bourtoule, V. Chandrasekaran, C. Choquette-Choo, H. Jia, A. Travers, B. Zhang, D. Lie, and N. Papernot, “Machine unlearning,” arXiv preprint arXiv:1912.03817, 2019.
[6] C. E. Shannon, “A mathematical theory of communication,” The Bell system technical journal, vol. 27,
no. 3, pp. 379–423, 1948.
[7] A. Rahimi and B. Recht, “Random features for large-scale kernel machines,” in Advances in neural
information processing systems, 2007, pp. 1177–1184.
[8] A. Sinha and J. C. Duchi, “Learning kernels with random features,” in Advances in Neural Information
Processing Systems, 2016, pp. 1298–1306.
[9] D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp.
1289–1306, 2006.
[10] E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction fromhighly incomplete frequency information,” IEEE Transactions on Information Theory, vol. 52, no. 2,
pp. 489–509, 2006.
[11] Y. Cao and J. Yang, “Towards making systems forget with machine unlearning,” in 2015 IEEE Symposium on Security and Privacy. IEEE, 2015, pp. 463–480.
15[12] A. Beirami, M. Razaviyayn, S. Shahrampour, and V. Tarokh, “On optimal generalizability in parametriclearning,” in Advances in Neural Information Processing Systems, 2017, pp. 3455–3465.
[13] P. W. Koh and P. Liang, “Understanding black-box predictions via influence functions,” arXiv preprint
arXiv:1703.04730, 2017.
[14] R. Giordano, W. Stephenson, R. Liu, M. Jordan, and T. Broderick, “A swiss army infinitesimal jackknife,” in The 22nd International Conference on Artificial Intelligence and Statistics, 2019, pp. 1139–
1147.
[15] K. R. Rad and A. Maleki, “A scalable estimate of the out-of-sample prediction error via approximate
leave-one-out cross-validation,” Journal of the Royal Statistical Society Series B, vol. 82, no. 4, pp.
965–996, 2020.
[16] C. Guo, T. Goldstein, A. Hannun, and L. van der Maaten, “Certified data removal from machine learningmodels,” ICML, 2020.
[17] S. Garg, S. Goldwasser, and P. N. Vasudevan, “Formalizing data deletion in the context of the rightto be forgotten,” in Annual International Conference on the Theory and Applications of Cryptographic
Techniques. Springer, 2020, pp. 373–402.
[18] A. Ginart, M. Guan, G. Valiant, and J. Y. Zou, “Making AI forget you: Data deletion in machinelearning,” in Advances in Neural Information Processing Systems, 2019, pp. 3513–3526.
[19] S. Neel, A. Roth, and S. Sharifi-Malvajerdi, “Descent-to-delete: Gradient-based methods for machine
unlearning,” arXiv preprint arXiv:2007.02923, 2020.
[20] A. Golatkar, A. Achille, and S. 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,
2020, pp. 9304–9312.
[21] Q. P. Nguyen, B. K. H. Low, and P. Jaillet, “Variational bayesian unlearning,” Advances in Neural
Information Processing Systems, vol. 33, 2020.
[22] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer andCommunications Security, 2016, pp. 308–318.
[23] C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and differential privacy,” in 2010 IEEE 51st
Annual Symposium on Foundations of Computer Science. IEEE, 2010, pp. 51–60.
[24] K. Chaudhuri and C. Monteleoni, “Privacy-preserving logistic regression,” in Advances in neural information processing systems, 2009, pp. 289–296.
[25] R. Shokri and V. Shmatikov, “Privacy-preserving deep learning,” in Proceedings of the 22nd ACM
SIGSAC conference on computer and communications security, 2015, pp. 1310–1321.
[26] P. Mohassel and Y. Zhang, “SecureML: A system for scalable privacy-preserving machine learning,” in2017 IEEE Symposium on Security and Privacy (SP). IEEE, 2017, pp. 19–38.
[27] J. So, B. Guler, A. S. Avestimehr, and P. Mohassel, “CodedPrivateML: A fast and privacy-preserving
framework for distributed machine learning,” arXiv preprint arXiv:1902.00641, 2019.
[28] M. Soleymani, H. Mahdavifar, and A. S. Avestimehr, “Privacy-preserving distributed learning in theanalog domain,” arXiv preprint arXiv:2007.08803, 2020.
[29] S. S. Azam, T. Kim, S. Hosseinalipour, C. Brinton, C. Joe-Wong, and S. Bagchi, “Towards generalized
and distributed privacy-preserving representation learning,” arXiv preprint arXiv:2010.01792, 2020.
16

[30] T. Li, J. Li, X. Chen, Z. Liu, W. Lou, and T. Hou, “NPMML: A framework for non-interactive privacypreserving multi-party machine learning,” IEEE Transactions on Dependable and Secure Computing,2020.
[31] S. Shahrampour, A. Beirami, and V. Tarokh, “On data-dependent random features for improved generalization in supervised learning,” AAAI, 2018.
[32] R. Agrawal, T. Campbell, J. Huggins, and T. Broderick, “Data-dependent compression of random
features for large-scale kernel approximation,” in The 22nd International Conference on Artificial Intelligence and Statistics, 2019, pp. 1822–1831.
[33] I. Radosavovic, P. Dollár, R. Girshick, G. Gkioxari, and K. He, “Data distillation: Towards omnisupervised learning,” in Proceedings of the IEEE conference on computer vision and pattern recognition,
2018, pp. 4119–4128.
[34] T. Wang, J.-Y. Zhu, A. Torralba, and A. A. Efros, “Dataset distillation,” arXiv preprint
arXiv:1811.10959, 2018.
[35] B. Scholkopf and A. J. Smola, Learning with kernels: support vector machines, regularization, optimization, and beyond. Adaptive Computation and Machine Learning series, 2018.
[36] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg et al., “Scikit-learn: Machine learning in python,” the Journal of machine
Learning research, vol. 12, pp. 2825–2830, 2011.
[37] D. Dua and C. Graff, “UCI machine learning repository,” 2017. [Online]. Available://archive.ics.uci.edu/ml

http:[38] C. Rasmussen, R. Neal, G. Hinton, D. Camp, M. Revow, Z. Ghahramani, R. Kustra, and R. Tibshirani,“Data for evaluating learning in valid experiments (delve),” 2003.
[39] D. A. Belsley, E. Kuh, and R. E. Welsch, Regression diagnostics: Identifying influential data and sourcesof collinearity. John Wiley & Sons, 2005, vol. 571.

17

A

Synthetic data

In this appendix we further experiment with three synthetic datasets to show the trade-off using the uncodedmachine unlearning and the proposed coded machine unlearning. In the first experiment, we randomly
generate d = 100 i.i.d. feature vectors where each element is drawn from χ2 (1), i.e., a chi-square distribution
with 1 degree of freedom. Then, we map these features X to a degree 4 polynomial with no interaction
terms, resulting in the following
Xp = [X, X ◦2 , X ◦3 , X ◦4 ].

(17)Then, the response variable is generated as described in (8), where elements of w and  are i.i.d. andgenerated randomly from the standard normal distribution. The size of the dataset is 47,000 samples, ofwhich 42,000 samples are for training the rest are for testing. The simulation is run with no regularization
term and using codes of rates τ = 2, 5, 10. The result of this experiment is shown in Figure 11. It can be seenthat coding provides a better performance compared to the uncoded machine unlearning at lower unlearning
cost. Additionally, it can be observed that different rates allow for different achievable performance measures.
As the rate increases, the lowest achievable MSE increases. Hence, similar to what is observed in Figure6, although higher rates reduce the unlearning cost, they might be incapable of achieving some desired
performance measures. For example, see the rightmost points of the curves for rate τ = 2 and τ = 10 in
Figure 11.
In the second experiment, we use a random MLP to create a nonlinear mapping and utilize random projections to simulate the experiment. Specifically, we randomly generate d = 50 i.i.d. feature vectors whose
elements are drawn from a lognormal(1, 4) distribution, then pass these features through a 3-layer MLP with50, 25, 50 nodes for each layer, respectively, each with a sigmoid activation function, followed by a linear output layer with a single node. All the weights and biases of these layers are i.i.d. and are generated froma standard normal distribution. A standard normally-distributed error term is added to the output of the
MLP to generate the final response variable. In this experiment, we use random projections as described in(7) on the normalized original features using D = 1,000 and the aforementioned parameters. The size of thedataset is 90,000 samples, of which 82,000 are for training and the rest are for testing. The results of thisexperiment for a code with rate τ = 5 and regularization parameters λ = 10−2 , 10−3 are shown in Figure
12. To illustrate the benefit of random projections, compare the curves in the figure with the performanceof using the original features and ridge regression on a single learner which is trained on the entire uncoded
training dataset where we observe an average MSE in the range 0.147 − 0.15 for the aforementioned valuesof λ, as well as λ = 0. This experiment shows that coding can provide gain in the trade-off, compared tothe uncoded machine unlearning, even for models that employ regularization using different parameters.
In the third experiment, we generate d = 100 i.i.d. feature vectors where each element of these vectors isdrawn from a standard normal distribution. Then, the response variable is generated as a linear combinationof these features plus noise, where elements of w and  are i.i.d. and generated randomly from the standard
normal distribution. The size of the dataset is 15,000 samples, of which 10,000 are for training the rest are fortesting. We simulate the linear regression problem using codes of rates τ = 2, 5. The result of this experimentis shown in Figure 13. This experiment shows a case where the uncoded machine unlearning maintains thesame performance as the unlearning cost decreases. For this case, there is no meaningful region for thecoding to operate in and, intuitively, we do not expect it to beat the performance of the original learningalgorithm with a single uncoded shard. Therefore, although coding does not provide a better trade-off inthis case, it does not exhibit a worse trade-off either.
Finally, we conduct two experiments that are concerned with the outlier vs inlier removal for two datasets;
the aforementioned chi-square features in a polynomial and the standard normal features in a linear model.
The results of the two experiments are shown in Figure 14 and Figure 15, respectively. Similar to the observations discussed in Section 3, the degradation in performance is more evident in datasets whose features18

0.0175

0.0035
Uncoded
Coded, =2
Coded, =5
Coded, =10

0.003

Uncoded,
Coded,

Uncoded,

0.017

Average test MSE

Average test MSE

Coded,

0.00250.002

0.0015=10 -3=10 -30.01650.016

0.01550.001

0.0005=10 -2=10 -2

0

0.1

0.2

0.3

0.4

0.5

0.6

0.015

0.7

Average unlearning cost (sec)

0

0.2

0.4

0.6

0.8

Average unlearning cost (sec)Figure 11: Performance vs unlearning cost forsynthetic data with χ2 (1) features used in a polynomial of degree 4.

Figure 12: Performance vs unlearning cost forsynthetic data generated from an MLP withlognormal(1, 4) features using random projections to a 1,000-dimensional, code rate τ = 5,
and different values of λ.

have heavier tails. Furthermore, as we observed in the experiments in this appendix, coding provides a better trade-off compared to the uncoded machine unlearning for datasets with heavy-tailed features; however,if the dataset does not have heavy-tailed features, coding does not negatively affect the trade-off.

B

Training Performance

In this appendix, the performance of a model on the training dataset is measured as the MSE of the uncoded
training dataset, regardless of whether coding is utilized or not, using the aggregate model. Note that thelearning cost is computed as the average time that is taken to train the weak learners on their respective
datasets. The resulting trade-off for the realistic datasets considered in Section 3 is shown in Figures 16-18,
and for the experiments considered in Appendix A is shown in Figures 19-21. It can be observed from thesefigures that the train MSE is always less than the test MSE when comparing each point in these figures with
its corresponding point in the test MSE figures. The correspondence here is not an x-axis correspondence,but rather an order correspondence. For instance, the rightmost point in any curve should be compared withthe rightmost point in the corresponding curve.

19

0.0012
Uncoded
Coded, =2
Coded, =5

Average test MSE

0.001

0.00080.00060.00040.0002

0

0.005

0.01

0.015

0.02

0.025

0.03

Average unlearning cost (sec)Figure 13: Performance vs unlearning cost for synthetic data with standard normally distributed features
used in a linear model.

0.2

0.2
Inliers removed
Outliers removed

Inliers removed
Outliers removed

0.15

Average test MSE

Average test MSE

0.15

0.1

0.05

0
0%

0.1

0.05

20%

40%

60%

80%

0
0%

100%

Percentage of remaining training samples

20%

40%

60%

80%

100%

Percentage of remaining training samples

Figure 14: Original learning algorithm’s performance vs percentage of remaining samples after removal of outliers and inliers from the χ2 (1)polynomial dataset.

Figure 15: Original learning algorithm’s performance vs percentage of remaining samples after
removal of outliers and inliers from the linear
dataset with standard normal features.

20

0.0050.062=10 -4

Coded,-4=10

Average train MSE

Uncoded,
Coded,

0.058

Uncoded,
Coded,

0.056=10 -6=10 -6

0.054
0.052
0.05
0.048

Uncoded
Coded, =2
Coded, =50.0045=10 -5=10 -5

Average train MSE

0.06

Uncoded,

0.004

0.00350.003

0.0025
0

0.02

0.04

0.06

0.08

0.1

0.12

0

1

Average learning cost (sec)Figure 16: Training performance vs learning
cost for different values of λ using the Physicochemical Properties of Protein Tertiary Structure dataset [37], random projections of features
to a 300-dimensional space, and a code of rate
τ = 5.

4

5

6
10-3

0.0035
Uncoded
Coded, =2
Coded, =5

Uncoded
Coded, =2
Coded, =5
Coded, =10

0.003

Average train MSE

0.005

Average train MSE

3

Figure 17: Training performance vs learning costfor different rates using the Computer Activity
dataset [38], random projections of features to a
25-dimensional space, and λ = 10−3 .

0.00550.00450.004

0.00350.003

2

Average learning cost (sec)0.00250.002

0.0015

0.001

0

0.002

0.004

0.006

0.008

0.01

0.0005

0.012

Average learning cost (sec)

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

Average learning cost (sec)Figure 18: Training performance vs learning costfor different rates using the Combined Cycle
Power Plant dataset [37] and random projectionsof features to a 20-dimensional space.

Figure 19: Training performance vs learning costfor synthetic data with χ2 (1) features used in apolynomial of degree 4.

210.0175
Uncoded,0.001=10 -3

Coded,

0.016
0.01550.015

0.00080.00060.00040.01450.014

Uncoded
Coded, =2
Coded, =5=10 -3

Average train MSE

Average train MSE

Uncoded,0.01650.0012=10 -2=10 -2

Coded,

0.017

0

0.2

0.4

0.6

0.8

1

0.0002

1.2

Average learning cost (sec)

0

0.01

0.02

0.03

0.04

Average learning cost (sec)Figure 20: Training performance vs learning costfor synthetic data generated from an MLP withlognormal(1, 4) features using a code of rate τ =5 and different values of λ.

Figure 21: Training performance vs learning costfor synthetic data with standard normally distributed features used in a linear model.

22