Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses
2026-06-01 • Machine Learning
Machine LearningCryptography and Security
AI summaryⓘ
The authors study how much it costs statistically to "unlearn" data from a trained machine learning model, which means removing data's influence to respect privacy rights. They provide mathematical bounds showing that the extra error from unlearning depends on how precise the unlearning is relative to the model's size. For simple problems like mean estimation, their upper and lower bounds match exactly. They find that unlearning can be much more accurate than completely retraining the model if the unlearning precision is high compared to the model's dimension. Otherwise, retraining the model from scratch remains the best choice.
machine unlearningexcess population riskapproximate unlearningstrongly convex optimizationmean estimationstatistical errorcondition numberdimensiondifferential privacy
Authors
Matthew Regehr, Gautam Kamath, Andrew Lowy
Abstract
Machine unlearning is motivated by legal and user-facing requirements to remove the influence of individuals' data from trained models, such as the right to be forgotten. Prior work has developed algorithms and error bounds for unlearning in smooth strongly convex stochastic optimization, but the fundamental statistical cost of unlearning has remained unclear. We nearly resolve this problem by proving upper and lower bounds on the excess population risk of approximate $\varepsilon$-unlearning; our bounds are tight up to a condition-number factor. For mean estimation over the unit ball, our upper and lower bounds match. The optimal rate is the usual statistical error plus an unlearning penalty that interpolates between the retraining-from-scratch rate and an exponentially smaller term as $\varepsilon/d$ grows, where $d$ is the dimension of the model. In particular, when $\varepsilon \gg d$, our $\varepsilon$-unlearning algorithm offers an exponential accuracy improvement over retraining the model from scratch and differentially private baselines. On the other hand, when $\varepsilon \le d$, retraining from scratch is optimal.