Error bounds for efficient machine unlearning in high dimensions
Error Accumulation in Second-Order Sequential Machine Unlearning
Machine Learning
Summary
Machine unlearning aims to remove data effects from trained AI models without fully retraining them. This paper studies how errors build up when repeatedly deleting data in models with many parameters. The authors analyze ways to certify that the unlearning works properly under different privacy rules, using mathematical methods to keep errors small. They show only a few update steps are needed for reliable unlearning, and Newton-based methods combined with conjugate gradient computations work well, especially for difficult problems.
What this means in practice
- •For machine learning engineers: Implement efficient and certified data removal in large AI models under different privacy guarantees, reducing the need for full retraining.
- •For financial model developers: Maintain updated risk models by securely and efficiently removing outdated or incorrect training data, ensuring stable model performance.
Authors
Chen Shang, Haolin Zou, Binghe Zhu, Arian Maleki
Abstract
Machine unlearning seeks to remove the influence of deleted training data without full retraining. In the sequential setting, deletion requests arrive over time, and repeated updates can accumulate approximation errors. In this paper, we study error accumulation in high dimensions, where parameter count $p$ is proportional to sample size $n$, for second-order unlearning methods under two privacy settings: (i) \emph{partial unlearning}, which allows unpublished internal states to be retained while certified versions of the model are released; and (ii) \emph{perfect unlearning}, which retains only published models and no hidden states. We also distinguish pointwise and pathwise certification, depending on whether the certification guarantee applies to each released model or the whole released sequence. We analyze conjugate gradient (CG) as an efficient solver for the inverse Hessian-vector product (IHVP) in Newton iterations. Our theory shows that a maximum of 1/2/2/3 Newton--CG updates suffice for successful certification and vanishing population-risk degradation of the published model, for pointwise partial, pathwise partial, pointwise perfect and pathwise perfect certification, respectively. Numerical experiments demonstrate accurate sequential tracking and substantial computational gains of Newton-based methods combined with conjugate gradient, over gradient-based updates, especially for ill-conditioned problems.