Variance-Reduced $(\varepsilon,δ)-$Unlearning using Forget Set Gradients
This work provides a novel, provably guaranteed method for machine unlearning, which is crucial for practitioners needing to remove specific data from trained models while maintaining formal privacy assurances.
This paper introduces Variance-Reduced Unlearning (VRU), a first-order algorithm for machine unlearning that directly incorporates forget set gradients into its update rule. It achieves provable $(\varepsilon,\delta)$-unlearning and demonstrates strictly improved convergence rates compared to existing methods, especially in a low-error regime.
In machine unlearning, $(\varepsilon,δ)-$unlearning is a popular framework that provides formal guarantees on the effectiveness of the removal of a subset of training data, the forget set, from a trained model. For strongly convex objectives, existing first-order methods achieve $(\varepsilon,δ)-$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,δ)-$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,δ)-$unlearning methods. Moreover, we prove that, in a low-error regime, VRU asymptotically outperforms any first-order method 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.