Research map / Learning theory and algorithms / Prediction and decision losses
System-Aware Unlearning Algorithms: Use Lesser, Forget Faster
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes system-aware unlearning, which only requires indistinguishability from a state-of-system built on a core set, and gives an exact unlearning algorithm for linear classification via monotonic selective sampling (BBQSampler) with sublinear memory.
Problem
Traditional exact unlearning requires an attacker-worst-case indistinguishability from retraining on S\U, which forces storing the entire dataset for linear classifiers and makes unlearning expensive and impractical at scale.
Approach
Relax the unlearning definition to be system-aware: indistinguishability is required only against the stored state, relative to some subset S' (a core set) chosen from S. Core-set algorithms built on monotonic selective sampling (query condition independent of labels) let deletions outside the core set be free and only core-set deletions require updates, yielding exact unlearning with sublinear me
Key results
- On the Purchase dataset, the proposed algorithm matches exact retraining's accuracy while storing 13.1% of data versus 100%, with accumulated deletion time of 58.3s vs 579.3s for retraining and 1174.3s for SISA.
- On the Margin dataset, the algorithm stores 0.6% of data and has accumulated deletion time of 0.5s vs 27.1s for exact retraining and 697.1s for SISA.
- The paper proves the first exact unlearning algorithm for linear classification with memory sublinear in dataset size, with core set size O(d T^kappa log T) and expected deletion time bounded by d^3 T^kappa log T / T under uniform deletions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use selective-sampling core-set unlearning instead of exact retraining | Linear classification · Purchase Dataset | accumulated deletion time: 58.3 vs 579.3 secs | Helped |
| Use selective-sampling core-set unlearning instead of exact retraining | Linear classification · Purchase Dataset | memory usage: 13.1% vs 100% | Helped |
| Use selective-sampling core-set unlearning instead of SISA | Linear classification · Purchase Dataset | accumulated deletion time: 58.3 vs 1174.3 secs | Helped |
| Use selective-sampling core-set unlearning instead of SISA | Linear classification · Purchase Dataset | accuracy over deletions | Helped |
| Use selective-sampling core-set unlearning instead of exact retraining | Linear classification · Margin Dataset | accumulated deletion time: 0.5 vs 27.1 secs | Helped |
| Use selective-sampling core-set unlearning instead of exact retraining | Linear classification · Margin Dataset | memory usage: 0.6% vs 100% | Helped |
| Use selective-sampling core-set unlearning instead of SISA | Linear classification · Margin Dataset | accuracy over deletions | Helped |
| Use selective-sampling core-set unlearning instead of SISA | Linear classification · Margin Dataset | initial training time: 1.3 vs 20.6 secs | Helped |
Surprising findings
- The proposed algorithm maintains better accuracy than SISA under long sequences of label-dependent deletions, even though SISA trains a more expressive model.
- Under the traditional definition, the BBQ-based algorithm is not valid, showing the definitional change is what enables efficiency.
Limitations
- Results are exact (epsilon=delta=0) only; approximate system-aware unlearning is left open.
- Excess risk after deletion is only bounded under realizability and tolerates a small increase versus y-dependent samplers; deletion capacity K shrinks with smaller kappa or larger d.
- Traditional unlearning comparisons and the general-function-class excess risk require a stable regression oracle, which is hard to bound in general.
Experimental setup
Datasets: Purchase dataset Margin dataset (synthetic)
Benchmarks: Purchase dataset Margin dataset
Metrics: test accuracy over label-dependent deletions initial training time accumulated deletion time percentage of data stored in memory
Baselines: SISA Exact Retraining Unlearning Algorithm from prior work (exact retraining for linear regression)
Builds on: BBQSampler SISA certified machine unlearning perfect unlearning
Closest papers by meaning
- What makes unlearning hard and what to do about it (NeurIPS 2024 · similarity 0.89)
- From Dormant to Deleted: Tamper-Resistant Unlearning Through Weight-Space Regularization (NeurIPS 2025 · similarity 0.89)
- Towards Source-Free Machine Unlearning (CVPR 2025 · similarity 0.89)
- When to Forget? Complexity Trade-offs in Machine Unlearning (ICML 2025 · similarity 0.89)
- Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning (ICLR 2025 · similarity 0.88)
- Layer Attack Unlearning: Fast and Accurate Machine Unlearning via Layer Level Attack and Knowledge Distillation (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.