Un-learning a single training example from a trained model

Question

I was going through the paper "The ML Test Score: A Rubric for ML Production Readiness and Technical Debt Reduction" by google on which suggests best practices for models in production. In a section about privacy controls in the data pipeline it says:

Finally, test that any user-requested data deletion propagates to the data in the ML training pipeline, and to any learned models.

I understand about the data deletion from the data pipeline but is it even possible to "un-learn" a single training example without retraining on the new data? They have mentioned in the paper that the practices are being used in google at some point or other, so there might be an efficient way but I'm unable to get any information on this.

I am looking for any literature on this or any ideas about how one would go on solving this problem.

Edit: On further research, I found this paper which focuses on the specific problem. Though making a lot of assumptions they propose a method for k-means too. Looks like this is an upcoming research area and would require time to develop!

Answer 1

is it even possible to "un-learn" a single training example without retraining on the new data?

To the best of my knowledge, the answer is no except in some very special cases.

The most obvious exception that comes to mind is instance-based learning, such as kNN: since the "model" itself consists only of the set of training instances, it's straightforward to remove an instance.

In general, supervised ML relies on generalizing patterns based on the instances from the training set. Any non-trivial model consists of multiple such patterns, with every pattern potentially resulting from a different subset of instances. Even if there was a way to trace which instance participated to which pattern (that would be extremely inefficient), removing any pattern would probably cause the model to fail.