Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees
Abstract
Certified machine unlearning ensures the proximity between the unlearned model and a model retrained without the data to be forgotten. Extending this framework to sequential deletion requests, typically arriving as groups of variable size (e.g., all records of one user or of coordinated users), is challenging. For unlearning methods based on fine-tuning on the retain sets, this leads to either degrading performance or increasing computation as the number of unlearning requests grows. For independent successive requests, we instead certify each model release against a counterfactual unlearning trajectory in which the group being deleted never took part. With a fixed fine-tuning budget per deletion, we show that, for smooth strongly convex objectives, this approach keeps the performance loss bounded, uniformly in the number of requests. Experiments with multiclass logistic regression on FEMNIST show that the resulting algorithm needs fewer corrective steps than existing sequential methods and outperforms training-time differential privacy, particularly when group sizes are heterogeneous.
Related
- Error Accumulation in Second-Order Sequential Machine Unlearning
- The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs
- Sequential Certification of Threshold Decisions in Rare-Event Risk Prediction
- Genuine certification of incompatible quantum instruments through sequential communication tasks
- Estimation of the Label-Noise Transition Matrix with Performance Guarantees via Selective Classification
BibTeX
@misc{benarroch2026counterfactual,
title = {{Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees}},
author = {Hanna Benarroch and Jamal Atif and Olivier Cappé},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17993},
eprint = {2610.17993},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05794763v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees
AU - Hanna Benarroch
AU - Jamal Atif
AU - Olivier Cappé
PY - 2026
DA - 2026/10/12
PB - HAL
DO - 10.48550/arxiv.2610.17993
UR - https://hal.science/hal-05794763v1
AB - Certified machine unlearning ensures the proximity between the unlearned model and a model retrained without the data to be forgotten. Extending this framework to sequential deletion requests, typically arriving as groups of variable size (e.g., all records of one user or of coordinated users), is challenging. For unlearning methods based on fine-tuning on the retain sets, this leads to either degrading performance or increasing computation as the number of unlearning requests grows. For independent successive requests, we instead certify each model release against a counterfactual unlearning trajectory in which the group being deleted never took part. With a fixed fine-tuning budget per deletion, we show that, for smooth strongly convex objectives, this approach keeps the performance loss bounded, uniformly in the number of requests. Experiments with multiclass logistic regression on FEMNIST show that the resulting algorithm needs fewer corrective steps than existing sequential methods and outperforms training-time differential privacy, particularly when group sizes are heterogeneous.
ER -