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.

Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2602.15602 [cs.LG]

(or arXiv:2602.15602v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2602.15602 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.