Variance-Reduced $(\varepsilon, \delta)-$Unlearning using Forget Set Gradients

In machine unlearning, $(\varepsilon,\delta)-$unlearning is a popular framework that provides formal guarantees on the effectiveness of the removal of a subset of training data, the \emph{forget set}, from a trained model. For strongly convex objectives, existing first-order methods achieve $(\varepsilon,\delta)-$unlearning, but they only use the forget set to calibrate injected noise, never as a direct optimization signal. In contrast, efficient empirical heuristics often exploit the forget samples (e.g., via gradient ascent) but come with no formal unlearning guarantees. We bridge this gap by presenting the Variance-Reduced Unlearning (*VRU*) algorithm. To the best of our knowledge, *VRU* is the first first-order algorithm that directly includes forget set gradients in its update rule, while provably satisfying $(\varepsilon,\delta)-$unlearning. We establish the convergence of *VRU* and show that incorporating the forget set yields strictly improved rates, *i.e.*, a better dependence on the achieved error compared to existing first-order $(\varepsilon,\delta)-$unlearning methods. Moreover, we prove that, in a low-error regime *VRU* asymptotically outperforms any first-order methods that ignores the forget set. Experiments corroborate our theory, showing consistent gains over both state-of-the-art certified unlearning methods and over empirical baselines that explicitly leverage the forget set.

When a machine learning model is trained, it absorbs everything it's shown. Sometimes you later need it to forget part of that data — say, a user requests their information be deleted. Retraining the model from scratch on the remaining data works but is slow and costly, so researchers look for faster shortcuts. Existing shortcuts come in two flavors. Some carry a mathematical guarantee that forgetting truly happened, but they barely use the data being deleted. Others aggressively use that data to work well in practice, but offer no guarantee. Our method, VRU, is the first of its kind to do both: it actively uses the to-be-forgotten data to steer the model while still proving the forgetting is genuine. We show it reaches a target accuracy faster than existing guaranteed methods — and when only a small slice of data needs deleting, it beats both any guaranteed method that ignores that data and retraining from scratch. Experiments confirm it forgets more cleanly while keeping the model accurate.