Certified Unlearning as a Stability Tool: Rates, Limits, and Implications

The relationship between differential privacy and the generalization of a learning algorithm has long been an open problem. We prove that the existence of a stable “privacy wrapper” implies generalization, a sufficient condition for generalization weaker than differential privacy. Specifically, we view certified unlearning (CU), which guarantees indistinguishability between unlearned and retrained models, as a privacy wrapper for its learning counterpart. We show that an $(\epsilon ,\delta )$-unlearning certificate, combined with unlearning stability, controls the learner's algorithmic stability and generalization without requiring differential privacy during learning. Our conversion theorem transfers $(\epsilon ,\delta )$-unlearning certification to algorithmic stability by replacing full-trajectory stability with that accumulated over the shorter unlearning process. The resulting stability bound depends on the certified unlearning dynamic. For a contractive unlearner with an anchored checkpoint, the learner has $O(n^{-1})$ stability, uniformly in the training horizon $T$. For a non-expansive (but non-contractive) unlearner, the stability bound is $O(n^{-1/3})$. In the expansive regime, the bound admits no vanishing rate in $n$. Another surprising result is “ununlearnablility”. Reversing the conversion theorem yields a contrapositive impossibility result: for nonsmooth convex, expansive smooth nonconvex, and ill-conditioned strongly convex losses, no stable, shallow, and cheaply certifiable unlearner can satisfy the required guarantees. Experiments with linear heads on frozen CIFAR-10 and SST-2 features confirm the predicted scaling laws and phase transitions (Appendix B).