Modeling Deletion Requests in Machine Unlearning

Christian Cianfarani; Aloni Cohen

cs.LGOct 3, 2026

Modeling Deletion Requests in Machine Unlearning

Authors: Christian Cianfarani, Aloni Cohen

Organizations: Data Science Institute Columbia University New York, USA · Department of Computer Science University of Chicago Chicago, USA

Abstract

Machine unlearning is seen as a promising approach to enable users to exercise the "right to erasure" in the context of AI models. We ask how users might influence the behavior of models when exercising this right. We define two types of behaviors that users might adopt when requesting the deletion of their data: adaptivity and collectivity. Drawing connections between the goals of users in this context and results in stochastic optimization, we demonstrate theoretical gaps between the potential effects of groups of users who do and do not display these behaviors. We then show how techniques from data valuation might be used to design deletion requesters that can significantly alter model behavior in realistic settings. In experiments on computer vision tasks, we demonstrate the differential effects of different models of user behavior and attempt to isolate the impacts of adaptivity and collectivity.

Figures & tables

Gap	Lower Bound	Upper Bound
Individual Adaptive vs. Individual Nonadaptive	$\sim$ 1.06	Open
Collective Adaptive vs. Collective Nonadaptive	1	1
Collective Adaptive vs. Individual Adaptive	1.5	Open
Collective Nonadaptive vs. Individual Nonadaptive	1.5	Open

TABLE I: Gaps in our simplified learning setting. We provide lower and upper bounds for the gaps between optimal requesters of different types in our simplified learning setting. The remaining lower bounds are derived in Section VI . To the best of our knowledge, upper bounds on collectivity gaps and the individual adaptivity gap have not been studied in prior work and are not addressed in this paper.

Fig. 1: Nonadaptive Requester Unlearning Performance. We plot the performance of the loss, MIA, and Shapley requesters compared to the random requester. For each requester, we train an initial model on a random subset of 25,000 CIFAR-10 training points and use that model to compute an ordering in which the training sampled will be unlearned. Points are then unlearned in this order over 9 iterations of 1,000 points per iteration. Solid lines represent averages over 4 trials, and one standard deviation is filled above and below the mean.

Fig. 2: Adaptive Requester Unlearning Performance. We plot the performance of the adaptive variants of the loss, MIA, and Shapley requesters compared to the random requester.

Fig. 3: Shapley-Based Requester Unlearning Performance. We plot the performance of variants of the Shapley requester (nonadaptive, adaptive, and individual) compared to the random requester.

Fig. 4: Relabel Unlearning Utility. We plot the performance of nonadaptive and adaptive unlearning requesters compared to the random requester when the unlearning algorithm is Relabel.

Fig. 5: SCRUB Unlearning Utility. We plot the performance of nonadaptive and adaptive unlearning requesters compared to the random requester when the unlearning algorithm is SCRUB.

Fig. 6: Thresholded Adaptivity Gaps. A ternary plot of the thresholded adaptivity gap for three subpopulations plotted over values of $(p_{1},p_{2},p_{3})$ . In this plot, $N$ is fixed to 10 and $k$ is fixed to 8.

Fig. 7: Thresholded Adaptivity Gaps in a Single Parameter Setting. Plotting the thresholded adaptivity gap over values of $\varepsilon$ and expected number of samples $N$ , such that $p_{1}=p_{2}=\varepsilon$ and $p_{3}=1-2\varepsilon$ . In this plot, we fix $k$ to $\lfloor 0.8N\rfloor$ .

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 351 papers

Learning to Unlearn: Machine Unlearning via Learning the Unlearning Behaviors
Aug 17, 2026Hang Zhang, Kaifeng Zhang, Yixiao Ma +3Machine Unlearning Privacy-Preserving ML
State Key Laboratory for Novel Software Technology Nanjing University Nanjing, China · Centre for Cyber Resilience and Trust Deakin University Burwood, VIC, Australia
Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees
Oct 13, 2026Hanna Benarroch, Jamal Atif, Olivier CappéMachine Unlearning
DI-ENS · CMAP
Is your algorithm unlearning or untraining?
Apr 9, 2026Eleni Triantafillou, Ahmed Imtiaz Humayun, Monica Ribero +3Machine Unlearning Machine Unlearning Evaluation
Google · Hasso Plattner Institute

Aug 17, 2026J/K move · Enter open · S save

Learning to Unlearn: Machine Unlearning via Learning the Unlearning Behaviors

Hang Zhang, Kaifeng Zhang, Yixiao Ma, Weijie Xu+2

State Key Laboratory for Novel Software Technology Nanjing University Nanjing, China · Centre for Cyber Resilience and Trust Deakin University Burwood, VIC, Australia

Machine Unlearning Privacy-Preserving ML

Open paper AskPDF arXiv

Various machine unlearning techniques have been developed in response to privacy legislation requirements, enabling individuals to exercise their legal right to have their data

D_f

removed from a machine learning model. This process is typically accomplished via the use of an unlearning function denoted as

U

. Existing methods focus on designing an intricate

U

to unlearn

D_f \subset D

from a previous model

A(D)

, so that the unlearned model performs as closely as possible to the retrained model

A(D \setminus D_f)

. However, these methods often suffer from high computational costs when dealing with massive training data, as the complex structures of

U

become a bottleneck even for models with fewer parameters. Inspired by Learning to Optimize, we introduce the first learning-based model-agnostic approach, Learning-to-UnLearn (L2UL). Our core insight is to shift from manually designing

U

to learning the unlearning behaviors from a distribution perspective, thereby acquiring a simple and efficient

U

via learning. Our experimental results demonstrate that the accuracy achieved by L2UL is comparable to that of retraining while exhibiting impressive efficiency, particularly in data-intensive scenarios. Furthermore, we validate the performance and scalability of our method on larger models ResNet.

Abstract

Machine Unlearning

Explore similar work

Learning to Unlearn: Machine Unlearning via Learning the Unlearning Behaviors

Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees

Is your algorithm unlearning or untraining?