Search papers, labs, and topics across Lattice.
The paper introduces the concept of "retain sensitivity" for certified machine unlearning, which measures the worst-case output change over deletions while keeping the retained data fixed. It argues that existing DP-based certified unlearning methods are overly conservative because they protect the privacy of the retained data, which is unnecessary for unlearning. By calibrating noise to retain sensitivity instead of global sensitivity, the authors achieve the same unlearning guarantees with significantly less noise, leading to improved utility.
Certified unlearning can achieve the same guarantees with less noise by calibrating to "retain sensitivity" rather than global sensitivity, exploiting the fact that unlearning doesn't require protecting the privacy of retained data.
Certified machine unlearning aims to provably remove the influence of a deletion set $U$ from a model trained on a dataset $S$, by producing an unlearned output that is statistically indistinguishable from retraining on the retain set $R:=S\setminus U$. Many existing certified unlearning methods adapt techniques from Differential Privacy (DP) and add noise calibrated to global sensitivity, i.e., the worst-case output change over all adjacent datasets. We show that this DP-style calibration is often overly conservative for unlearning, based on a key observation: certified unlearning, by definition, does not require protecting the privacy of the retained data $R$. Motivated by this distinction, we define retain sensitivity as the worst-case output change over deletions $U$ while keeping $R$ fixed. While insufficient for DP, retain sensitivity is exactly sufficient for unlearning, allowing for the same certificates with less noise. We validate these reductions in noise theoretically and empirically across several problems, including the weight of minimum spanning trees, PCA, and ERM. Finally, we refine the analysis of two widely used certified unlearning algorithms through the lens of retain sensitivity, leveraging the regularity induced by $R$ to further reduce noise and improve utility.
