We survey the works on machine unlearning -
[1]} were one of the first papers to study the topic of machine unlearning. Their approach implements statistical query (SQ) algorithms by estimating the statistical queries using training data. Since the estimates are usually the mean of query evaluations computed on training data, unlearning is cheap, as we only need to subtract the evaluation on the deleted point.
[2]} studies this problem, with the goal to design systems to efficiently handle deletion requests.
Their approach, called SISA, is essentially a divide-and-conquer strategy, wherein the data is divided into disjoint sets, called shards, and a model on each shard is trained separately and aggregated. Furthermore, they do several check-pointing of states for each shard. In the average case, this provides a speedup of \(\frac{(R+1)S}{2}\)  for \(S\)  shards and \(R\)  checkpoints per shard, over retraining. They however give no guarantees on accuracy with this divide-and-conquer training method.
[3]} is another work which uses \((\epsilon , \delta )\) -differential privacy like guarantee. They study unlearning in generalized linear models, and propose a Newtons-step based method, leveraging connections with influence functions. Their computational cost is \(O(d^3)\)  computations for one unlearning. They, however give no guarantees on excess empirical risk achieved by the training method.
Finally, the work of [4]} studies batch unlearning in linear regression, with the goal to improve the computational cost of batch \(k\)  unlearning requests. Their method achieves a runtime of \(O(k^2d)\)  as opposed to \(O(kd^2)\)  for a naive approach. However, their notion of unlearning is again approximate, in the sense that model returned after unlearning is closest to the exact unlearning model among models in the \(d\)  dimensional subspace spanned by the to-be-deleted \(k\)  points. So it is easy to see that with larger \(k\) , the notion of approximation improves, which explains the \(k^2\)  term in the runtime as opposed to \(k\) .
