Error Accumulation in Second-Order Sequential Machine Unlearning
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.
Related
- Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees
- Risk-Aware Output Control Should be the Focus of Machine Unlearning
- Machine Unlearning for Gibbs Supervised Learning Algorithms
- Minimax Gaussian Mechanisms for Continual Machine Unlearning
- Optimal error estimates of sequential finite element method for nonlinear thermo-poroelasticity problems
BibTeX
@misc{shang2026error,
title = {{Error Accumulation in Second-Order Sequential Machine Unlearning}},
author = {Chen Shang and Haolin Zou and Binghe Zhu and Arian Maleki},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03445},
eprint = {2611.03445},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03445},
}
RIS
TY - UNPB
TI - Error Accumulation in Second-Order Sequential Machine Unlearning
AU - Chen Shang
AU - Haolin Zou
AU - Binghe Zhu
AU - Arian Maleki
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03445
UR - https://arxiv.org/abs/2611.03445
AB - 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.
ER -