When to Forget? Complexity Trade-offs in Machine Unlearning

Machine Unlearning (MU) aims at removing the influence of specific data points from a trained model, striving to achieve this at a fraction of the cost of full model retraining. In this paper, we analyze the efficiency of unlearning methods and establish the first upper and lower bounds on minimax computation times for this problem, characterizing the performance of the most efficient algorithm against the most difficult objective function. Specifically, for strongly convex objective functions and under the assumption that the forget data is inaccessible to the unlearning method, we provide a phase diagram for the unlearning complexity ratio---a novel metric that compares the computational cost of the best unlearning method to full model retraining. The phase diagram reveals three distinct regimes: one where unlearning at a reduced cost is infeasible, another where unlearning is trivial because adding noise suffices, and a third where unlearning achieves significant computational advantages over retraining. These findings highlight the critical role of factors such as data dimensionality, the number of samples to forget, and privacy constraints in determining the practical feasibility of unlearning.

Machine Unlearning (MU) is about removing the impact of certain pieces of data from a machine learning model—like making the model “forget” something it previously learned—without having to retrain it entirely from scratch. In this paper, we explore how efficient these unlearning methods can be and provide the first clear boundaries on how fast or slow this process can possibly be, even in the best or worst cases. We focus on a specific setting where the data to be forgotten isn’t available during the unlearning process and where the learning problem follows some well-behaved mathematical rules. We introduce a new way to measure how much faster unlearning can be compared to full retraining and show that depending on the situation, three different outcomes are possible: unlearning might be impossible without full retraining, very easy using simple techniques like adding noise, or genuinely much faster than starting over. Our results show that whether unlearning is practical depends heavily on the complexity of the data, how much data needs to be forgotten, and how strict the privacy requirements are.