Exact Unlearning After Data Curation
Organizations: Birla Institute of Technology and Science, Pilani Pilani, Rajasthan, India
Abstract
Training pipelines often remove similar examples before fitting a model. Deleting a raw record can change that selection and admit an example that was excluded before. What must a service retain to reproduce training after such requests? We answer this question for a fixed rule in which earlier similar records block later ones. A limit on the total number of future deletions identifies exactly which records can still enter training. We use this boundary to build a summary of training statistics that can be repaired exactly after repeated deletions. The repaired summary is the same as rebuilding it on the surviving data with the remaining budget. We also construct finite-precision features for ridge regression, a linear learner with a penalty on coefficient size. With exact rational outputs, allowing one more deletion changes the required private information. It rises from zero to every private feature sign in the excluded candidates. An encoding attains this conditional private-information minimum on the constructed family throughout a sequence of requests. On 1,001 AskUbuntu development records, deleting an initially excluded record admits another record at 13 of 51 fixed similarity cutoffs. Exact membership repair passes 13,056 deletion-step checks. Two model-based semantic calibrations fail their fixed criteria, so the downstream task study is not run. The central result is a retention contract: the future deletions a service promises to support determine which excluded data can still be needed.
Figures & tables
| Cutoff | Edges | Selected | Excluded | Excluded deletions with admission |
|---|---|---|---|---|
| .50 | 500,500 | 1 | 1,000 | 0 |
| .84 | 245,841 | 7 | 994 | 1 |
| .90 | 15,678 | 504 | 497 | 50 |
| .96 | 197 | 952 | 49 | 7 |
| .995 | 0 | 1,001 | 0 | 0 |
| Check | Matches / checks |
|---|---|
| Selected membership after each singleton request | 13,056 / 13,056 |
| Sequential versus batched retained state | 408 / 408 |
| Sequential versus reverse-order retained state | 408 / 408 |
| Retained state versus fresh reconstruction | 408 / 408 |
| Cutoff | Pairs | Weighted joint positive (%) |
|---|---|---|
| .90 | 330 | 0.01 |
| .95 | 180 | 0.31 |
| .98 | 90 | 9.66 |
| .99 | 60 | 40.00 |
| .995 | 30 | 40.00 |
Machine Unlearning
Machine unlearning removes the influence of selected data or concepts from trained models while preserving useful behavior and avoiding full retraining.
See all 356 papers