CS Paper Radar

Exact Unlearning After Data Curation

Priyank Jayraj, Devanshu sahoo, Uday Mittal

cs.LG cs.AI ·submitted 2026-10-24 03:51 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Why Forget-Only Unlearning Needs Memorization

cs.LG cs.ITstat.ML ·2026-10-07 ·Luka Radić, Vikrant Singhal, Amartya Sanyal
similarity 0.72
Abstract

Machine unlearning asks for a deletion algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, we study forget-only unlearning, where the deletion algorithm receives only the trained model and the examples to forget, with no retained data or extra training information. We ask whether forget-only unlearning is always possible. We first show that this depends on the learning method: different datasets can produce the same trained model but require very different outputs after the same examples are removed. Using this observation, we derive lower bounds on how accurately unlearning can match retraining and instantiate them for several standard learning algorithms. We then ask what must be true when forget-only unlearning succeeds. To this end, we derive lower bounds on what an algorithm must memorize about the training data to handle arbitrary deletion requests. For simple threshold learners, the required information can be as large as the entire dataset, even though ordinary training keeps only one boundary point. Overall, our results show that information discarded during ordinary learning may be needed later for deletion, so models designed for forget-only unlearning may need to retain more information than standard training does.

0.18

Client-Side Probing of Deleted Ridge Statistics in Federated Unlearning

cs.CR cs.LG ·2026-09-03 ·Yijun Quan, Giovanni Montana
similarity 0.68
Abstract

Federated unlearning aims to remove a client's data from a shared model without retraining from scratch. Some efficient systems make deletion exact by storing compact, additive summaries of the training features and broadcasting an updated linear classifier after every accepted change. We show that these broadcasts can also reveal the hidden summaries. A malicious client can submit known changes, use the returned classifiers to identify the server state, and compare states immediately before and after an isolated deletion. This exposes the deleted sample, class, or client summary and can enable its reinsertion. We characterize exactly when the observations contain enough independent information, give a matching optimal construction for unrestricted probes, and derive a more realistic estimator based on additions formed from the attacker's own data. On MNIST and CIFAR-10, high-precision broadcasts permit exact label recovery for every tested sample deletion with both probe types. Lower-precision broadcasts sharply reduce fine-grained recovery, and insufficiently diverse responses prevent identification altogether. Unrestricted probes are readily detected by their size; most individual attacker-data additions resemble honest batches, although we do not claim that the complete sequence is inconspicuous. The results identify a concrete privacy and integrity risk, its algebraic cause, and practical limits involving broadcast precision, update verification, response rate, and concurrent activity.

0.32

Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees

cs.LG stat.ML ·2026-10-13 ·Hanna Benarroch, Jamal Atif, Olivier Cappé
similarity 0.68
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.

0.17

Bounding Retraining Equivalence and the Deletion Floor in Materials Machine Unlearning

cs.LG cond-mat.mtrl-sciquant-ph ·2026-09-28 ·Can Polat, Mustafa Kurban, Erchin Serpedin, Hasan Kurban
similarity 0.68
Abstract

In materials machine learning, closely related retained structures can sustain accurate property predictions even after removing a specific record, rendering post-deletion prediction error an ambiguous metric for machine unlearning. To resolve this ambiguity, we define the deletion floor as the expected target loss under a specified retraining procedure at the deleted request. Standard indistinguishability constraints yield a sharp interval bounding an update's target loss around this baseline reference. Theoretically, a conditional neighbor bound links a low deletion floor directly to retained fit, prediction regularity, and local label agreement, while an exact ridge identity isolates residual fit from the prediction change induced by record deletion. Empirically, controlled redundancy sweeps show an $\approx 8\times$ drop in median normalized retraining loss when one retained relative remains after deletion. Across two distinct fitting regimes in a paired Materials Project study, the lower-floor regime also exhibits a larger prediction change on more than 50% of the shared requests. Systematic comparisons against approximate updates and the original model decouple deliberate target suppression from preserved overall model utility. Consequently, request-level unlearning evaluations should report reference loss, prediction change, and retained utility together, interpreting post-deletion accuracy against what retraining itself leaves behind.

0.28

Do unlearning algorithms learn the right features?

cs.LG ·2026-11-04 ·Polina Dolgova, Amartya Sanyal, Sebastian U. Stich
theory similarity 0.67
Abstract

Machine unlearning is commonly evaluated with standard post-deletion metrics that compare an unlearned model to one retrained on the remaining data. Such snapshot evaluations can conceal consequential differences in the features the two models encode. We prove that if an unlearned and a retrained model agree on their outputs but encode different features, a single gradient step on their prediction heads can break this agreement. We further show that deleting an arbitrarily small fraction of the data can cause retraining to select qualitatively different features, so matching retraining can require learning features that the full model never had. We then introduce a measure of feature recovery that separates missing from extraneous features. Across eight unlearning methods, models that perform well on standard metrics often fail to recover the retrained features. This mismatch predicts deviations from retraining under subsequent relearning and downstream adaptation, and directly correcting it systematically reduces these deviations.

0.16

Exact Unlearning via Quantized Sufficient Statistics

cs.LG ·2026-10-05 ·Ami Tavory, Shripad Gade, Tal Sarig, Noam Touitou, Ido Guy
top venue similarity 0.65
Abstract · 33 pages, 20 figures, 15 tables. Accepted at NeurIPS 2026

Exact unlearning requires a deployed predictor to match one rebuilt without the information named by a deletion request. Existing general-purpose exact methods localize retraining through disjoint shards, but every request still invalidates a model, and smaller shards reduce the data available to each constituent predictor. We introduce Quantized Sufficient Statistics (QSS), which separates a small frozen schema from mutable, sum-decomposable content. The schema learns global structure; the content stores local prediction corrections as additive statistics indexed by quantized regions. Deleting content is therefore exact subtraction rather than optimization. We distinguish two guarantees: QSS-L exactly removes a label while retaining the unlabelled input, whereas QSS-E exactly removes both input and label by learning the schema without deletable examples. A deletion takes the arithmetic fast path with probability $1-ρ$ and triggers a full rebuild with probability $ρ$; all reported expected latencies include both events. Across 15 vision, text, and tabular datasets at $ρ=0.5\%$, QSS-L is within 2 percentage points of SISA on 11 tasks and provides 4--483$\times$ lower expected deletion latency on the low-class-count tasks where a compact schema is effective. QSS-E quantifies the additional accuracy cost of removing every trace of an input.

0.45

IDSISA: Influence-Distilled Sharded Training for Efficient Machine Unlearning

cs.LG cs.AI ·2026-11-04 ·Deeraj SK, Sadhana Devarajan, Tanmoy Hazra, Anupam Shukla
theory similarity 0.63
Abstract · This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may…

Machine unlearning removes the influence of specific training examples to comply with privacy regulations. Full retraining gives strong guarantees but is computationally prohibitive at scale; approximate methods are efficient but lack formal guarantees. SISA (Sharded, Isolated, Sliced, and Aggregated training) achieves certified deletion through data sharding and independent retraining, but random partitioning scatters forget requests across most shards, and isolated retraining degrades utility. We introduce IDSISA (Influence-Distilled SISA), which uses influence functions to concentrate forget-prone samples into few shards and distillation from unaffected shards to recover utility lost to isolation. The deletion guarantee inherited from SISA's retraining step remains exact and requires no probabilistic qualification; the distillation-based utility recovery is a separately quantified, empirically bounded approximation ($ε_{\text{cert}} \leq 0.015$ in expectation). We further formalize certification under sequences of repeated deletion requests, where cross-shard distillation can create dependencies between shards; we prove that a closure-based cascading retraining procedure restores the deletion guarantee to the full aggregated model under any deletion sequence. Experiments on ResNet-18/CIFAR-10, ResNet-18/CIFAR-100, BiLSTM/IMDB, TCN/IMDB, and a fully connected network on Fashion-MNIST show $14-91\%$ better selective forgetting, up to $50\%$ better utility retention in relative terms (with consistent percentage-point gains on the other architectures, where a relative baseline is undefined), and unlearning-time changes ranging from $-6.7\%$ to $+6.4\%$ depending on architecture, relative to SISA.

0.22

OSR: Output Space Redistribution for Adaptive Label Removal in Classification Models

cs.LG ·2026-09-03 ·Minyi Peng, Darian Gunamardi, Ivan Tjuawinata, Yongsen Zheng, Kwok-Yan Lam
published similarity 0.62
Abstract · Accepted by ICA3PP 2026

Label removal occurs frequently in classification systems with evolving taxonomies, where categories must be dynamically updated or eliminated. To accommodate such changes, classification models must adapt accordingly. Existing solutions, broadly categorized as retraining-based and feature-space-adjustment-based, share common limitations despite their variations, including reliance on access to original data, substantial computational and storage costs, inconsistent results, poor scalability, and degradation of model utility. To address this, we propose a novel approach that leverages statistical redistribution in the output space to approximate the post-removal confidence vectors of a retrained model. Applicable as a modular output filter, our method bypasses the burden of feature-space adjustments or loss-function convergence, alleviating scalability limitations. Furthermore, by requiring only existing labels and prior output confidences, the method potentially mitigates privacy concerns inherent to data-dependent solutions. Extensive experiments demonstrate competitive performance against full retraining, with improvements in computational efficiency and privacy preservation across several classification tasks.

0.37