Tight Bounds for Machine Unlearning via Differential Privacy
This work provides a theoretical foundation for the 'right to be forgotten' in machine learning, though it is incremental as it builds directly on prior results.
The paper closes the gap between upper and lower bounds on the deletion capacity for machine unlearning algorithms based on differential privacy, establishing tight bounds on how many data points can be unlearnt without affecting model accuracy.
We consider the formulation of "machine unlearning" of Sekhari, Acharya, Kamath, and Suresh (NeurIPS 2021), which formalizes the so-called "right to be forgotten" by requiring that a trained model, upon request, should be able to "unlearn" a number of points from the training data, as if they had never been included in the first place. Sekhari et al. established some positive and negative results about the number of data points that can be successfully unlearnt by a trained model without impacting the model's accuracy (the "deletion capacity"), showing that machine unlearning could be achieved by using differentially private (DP) algorithms. However, their results left open a gap between upper and lower bounds on the deletion capacity of these algorithms: our work fully closes this gap, obtaining tight bounds on the deletion capacity achievable by DP-based machine unlearning algorithms.