Abstract: Machine unlearning addresses the problem of updating a machine learning model/system trained on a dataset $S$ so that the influence of a set of deletion requests $U \subseteq S$ on the unlearned model is minimized. The gold standard definition of unlearning demands that the updated model, after deletion, be nearly identical to the model obtained by retraining. This definition is designed for a worst-case attacker (one who can recover not only the unlearned model but also the remaining data samples, i.e., $S \setminus U$). Such a stringent definition has made developing efficient unlearning algorithms challenging. However, such strong attackers are also unrealistic. In this work, we propose a new definition, *system-aware unlearning*, which aims to provide unlearning guarantees against an attacker that can at best only gain access to the data stored in the system for learning/unlearning requests and not all of $S\setminus U$. With this new definition, we use the simple intuition that if a system can store less to make its learning/unlearning updates, it can be more secure and update more efficiently against a system-aware attacker. Towards that end, we present an exact system-aware unlearning algorithm for linear classification using a selective sampling-based approach, and we generalize the method for classification with general function classes. We theoretically analyze the tradeoffs between deletion capacity, accuracy, memory, and computation time.

Lay Summary:

Machine learning models are often trained on private, sensitive data, which could be exposed during deployment. Due to these privacy concerns, some individuals may request for the influence of their data be removed from the model after deployment. Machine unlearning is the selective removal of specific training data after a model has been trained in a more efficient manner than retraining the entire model from scratch. The current definition of machine unlearning provides privacy guarantees against a worst-case attacker (one who can recover not only the unlearned model but also the remaining data samples); however, such strong attackers are unrealistic, and this stringent definition has made the development of efficient unlearning algorithms challenging. In this work, we propose a new definition, system-aware unlearning, which aims to provide unlearning guarantees against an attacker that can at best only gain access to the information stored in the learning system after unlearning. If less information is stored and used by the algorithm, then less information is exposed to the attacker, making it easier to provide privacy against such an attacker. Thus, algorithms that rely on less of their training data can unlearn more efficiently. Using this intuition, we use sample compression algorithms to design more efficient unlearning algorithms for classification.