Regehr, Kamath, Lowy tighten machine unlearning bounds

The central claim of the new arXiv paper is compact: "(ε, δ)-unlearning has no statistical advantage over pure ε-unlearning."

For a subfield that has spent years importing the ε/δ machinery of differential privacy into unlearning, that is a real result. The authors, Matthew Regehr, Gautam Kamath, and Andrew Lowy, prove matching upper and lower bounds on the excess population risk of approximate unlearning for smooth strongly convex losses, "tight up to a condition-number factor." For mean estimation over the unit ball, they write, "our upper and lower bounds match."

The optimal rate splits in two: the usual sampling error plus an unlearning penalty. That penalty "interpolates between the retraining from scratch rate and an exponentially smaller term as ε/d grows," where d is the model dimension.

The corollaries cut both ways. For ε ≲ d, "retraining from scratch is information theoretically optimal"; you cannot do better. For ε ≫ d and large unlearning requests, the authors' algorithm offers "an exponential accuracy improvement over retraining the model from scratch and differentially private baselines." Two researchers we track posted the preprint the same week.