Search papers, labs, and topics across Lattice.
This paper introduces Variance-Reduced Unlearning (VRU), a novel first-order algorithm for $(\varepsilon, \delta)$-unlearning that directly incorporates gradients from the forget set into the model update rule. VRU leverages variance reduction techniques to ensure convergence and formal unlearning guarantees, unlike existing heuristics that use forget set gradients without such guarantees. The authors prove that VRU achieves improved convergence rates compared to methods that only use the forget set for noise calibration, and demonstrate its superior performance empirically.
Forget-set gradients, previously only used in uncertified heuristics, can now be harnessed for provably faster and more accurate machine unlearning.
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.
