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.
Related
- Certified exact bounds for adaptive quantitative group testing with two defectives
- Certified bounds on optimization problems in quantum theory
- Region bounds, error margins and certified positivity in the numerical conformal bootstrap; Or the first mathematically rigorous bounds on the 3d Ising CFT critical exponents
- Pay Only for Disagreement: Certified No-Regression Verdicts for Model Updates with Matching Label-Complexity Bounds
- Bipartite Carrier Compression and Machine-Certified Bounds in Schönhage Trilinear Multiplication Tensors
BibTeX
@misc{benarroch2026certified,
title = {{Certified Per-Instance Unlearning Using Individual Sensitivity Bounds}},
author = {Hanna Benarroch and Jamal Atif and Olivier Cappé},
howpublished = {HAL},
year = {2026},
month = oct,
eprint = {2602.15602},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05514920v3},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Certified Per-Instance Unlearning Using Individual Sensitivity Bounds
AU - Hanna Benarroch
AU - Jamal Atif
AU - Olivier Cappé
PY - 2026
DA - 2026/10/12
PB - HAL
UR - https://hal.science/hal-05514920v3
AB - 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.
ER -