Certified Per-Instance Unlearning Using Individual Sensitivity Bounds

Abstract

Certified machine unlearning can be achieved through noise injection, with differential privacy guarantees obtained by calibrating the noise to worst-case sensitivity. Yet, the influence of individual training points is highly heterogeneous, making such uniform calibration unnecessarily conservative for most deletion requests. We consider certified per-instance unlearning, a data-dependent notion of certified deletion in which the unlearning mechanism and its certificate can adapt to the point being removed. Our framework turns point-specific sensitivity information into formal unlearning guarantees, allowing the amount of noise to reflect the difficulty of the deletion request rather than the worst case. When training is deterministic, we derive explicit per-instance unlearning certificates. For noisy gradient descent, in the case of ridge regression, similar certificates are obtained through high-probability sensitivity bounds. Experiments on NYU-Depth with frozen DINOv2 features show substantial variation in deletion difficulty across points, and demonstrate that per-instance calibration can substantially improve utility over uniform worst-case calibration.