Algorithms that Approximate Data Removal: New Results and Limitations
This addresses data privacy and compliance issues for users and organizations by enabling efficient deletion in streaming settings, though it is incremental with improvements over prior methods.
The paper tackles the problem of efficiently deleting user data from machine learning models trained with empirical risk minimization, particularly for non-smooth regularizers, by developing an online unlearning algorithm that improves runtime while maintaining memory and accuracy. It also reveals a limitation where existing approximate unlearning algorithms fail when hyperparameter tuning methods like cross-validation are used.
We study the problem of deleting user data from machine learning models trained using empirical risk minimization. Our focus is on learning algorithms which return the empirical risk minimizer and approximate unlearning algorithms that comply with deletion requests that come streaming minibatches. Leveraging the infintesimal jacknife, we develop an online unlearning algorithm that is both computationally and memory efficient. Unlike prior memory efficient unlearning algorithms, we target models that minimize objectives with non-smooth regularizers, such as the commonly used $\ell_1$, elastic net, or nuclear norm penalties. We also provide generalization, deletion capacity, and unlearning guarantees that are consistent with state of the art methods. Across a variety of benchmark datasets, our algorithm empirically improves upon the runtime of prior methods while maintaining the same memory requirements and test accuracy. Finally, we open a new direction of inquiry by proving that all approximate unlearning algorithms introduced so far fail to unlearn in problem settings where common hyperparameter tuning methods, such as cross-validation, have been used to select models.