Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses

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 $(\epsilon ,\delta )$-unlearning; our bounds are tight up to a condition-number factor. For mean estimation over the unit ball, our upper and lower bounds match up to constants. In fact, our algorithm achieves $\epsilon$-unlearning, which implies a notable separation between differential privacy (DP) and unlearning: $(\epsilon ,\delta )$-unlearning has no statistical advantage over pure $\epsilon$-unlearning in stochastic convex optimization. The optimal rate is the usual sampling error plus an unlearning penalty that interpolates between the retraining-from-scratch rate and an exponentially smaller term as $\epsilon /d$ grows, where $d$ is the dimension of the model. In particular, retraining-from-scratch is statistically optimal when $\epsilon \lesssim d$. On the other hand, for $\epsilon \gg d$ and large unlearning requests, our $\epsilon$-unlearning algorithm offers an exponential accuracy improvement over retraining the model from scratch and over DP baselines.