We study the problem of URLetting datapoints from a learnt model. In this case, the learner first receives a dataset S drawn i.i.d. from an unknown distribution, and outputs a predictor w that performs well on unseen samples from that distribution. However, at some point in the future, any training data point z \in S can request to be unlearned, thus prompting the learner to modify its output predictor while still ensuring the same accuracy guarantees. In our work, we initiate a rigorous study of machine unlearning in the population setting , where the goal is to maintain performance on the unseen test loss. We then provide unlearning algorithms for convex loss functions . For the setting of convex losses, we provide an unlearning algorithm that can delete up to O(n/d^{1/4}) samples, where d is the problem dimension. In comparison, in general, differentially private learningv (which implies unlearning) only guarantees deletion of O(n/d^{1/2}) samples. This shows that unlearningis at least polynomially more efficient than learning privately in terms of dependence on d in the deletion capacity .
We study the problem of unlearning datapoints from a learnt model. The learner first receives a dataset S drawn i.i.d. from an unknown distribution, and outputs a model that performs well on unseen samples from the same distribution. However, at some point in the future, any training datapoint z \in S can request to be unlearned, thus prompting the learner to modify its output model while still ensuring the same accuracy guarantees. We initiate a rigorous study of generalization in machine unlearning , where the goal is to perform well on previously unseen datapoints. Our focus is on both computational and storage complexity . For the setting of convex losses, we provide an unlearning algorithm that can unlearn up to O(n/d^{1/4}) samples, where d is the problem dimension. In comparison, in general, differentially private learning (which implies unlearning) only guarantees deletion of O(n/d^{1/2}) samples. This demonstrates a novel separation between differential privacy and machine unlearning .
R
URLetting
unlearning
R
In this case, the
The
R
predictor w
model
R
that
the same
R
data point
datapoint
R
predictor
model
R
In our work, we
We
R
machine unlearning in the population setting
generalization in machine unlearning
R
maintain performance on the unseen test loss. We then provide unlearning algorithms for convex loss functions
perform well on previously unseen datapoints. Our focus is on both computational and storage complexity
R
delete
unlearn
R
learningv
learning
R
shows that unlearningis at least polynomially more efficient than learning privately in terms of dependence on d in the deletion capacity
demonstrates a novel separation between differential privacy and machine unlearning