Machine Unlearning via Algorithmic Stability
arXiv:2102.13179
Abstract
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.
References in corpus (7)
- Deep Learning with Differential Privacy
- Rényi Divergence and Kullback-Leibler Divergence
- Renyi Differential Privacy
- Descent-to-Delete: Gradient-Based Methods for Machine Unlearning
- How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
- Certified Data Removal from Machine Learning Models
- On maximal agreement couplings