Error Accumulation in Second-Order Sequential Machine Unlearning
Organizations: Department of Statistics, Columbia University · Department of Electronic Engineering, Columbia University
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 is proportional to sample size , for second-order unlearning methods under two privacy settings: (i) partial unlearning, which allows unpublished internal states to be retained while certified versions of the model are released; and (ii) 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.
Figures & tables
| Hidden state | Certification | Center Tolerance | Max Newton-CG steps | Noise std per coordinate | Max risk along deletion path |
|---|---|---|---|---|---|
| Allowed (partial unlearning) | Pointwise | ||||
| Pathwise | |||||
| Forbidden (perfect unlearning) | Pointwise | ||||
| Pathwise |
Machine Unlearning
Machine unlearning removes the influence of selected data or concepts from trained models while preserving useful behavior and avoiding full retraining.
See all 372 papers