Machine Unlearning via Algorithmic Stability
This addresses the need for data removal in machine learning systems, offering a novel approach with potential applications in privacy-sensitive domains, though it appears incremental in building on existing stability and differential privacy concepts.
The paper tackles the problem of machine unlearning by introducing Total Variation (TV) stability as a framework for exact unlearning, and designs efficient unlearning algorithms based on noisy SGD with theoretical bounds on risk trade-offs.
We study the problem of machine unlearning and identify a notion of algorithmic stability, Total Variation (TV) stability, which we argue, is suitable for the goal of exact unlearning. For convex risk minimization problems, we design TV-stable algorithms based on noisy Stochastic Gradient Descent (SGD). Our key contribution is the design of corresponding efficient unlearning algorithms, which are based on constructing a (maximal) coupling of Markov chains for the noisy SGD procedure. To understand the trade-offs between accuracy and unlearning efficiency, we give upper and lower bounds on excess empirical and populations risk of TV stable algorithms for convex risk minimization. Our techniques generalize to arbitrary non-convex functions, and our algorithms are differentially private as well.