Distributional Machine Unlearning via Selective Data Removal
Authors: Youssef Allouah
Rachid Guerraoui
Sanmi Koyejo
Venue: ICLR 2026 Poster (2026)
Keywords: unlearning
theory
privacy
sample complexity
machine learning
statistical learning
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Machine learning systems increasingly face requirements to remove entire domains of information—such as toxic language or biases—rather than individual user data. This task presents a dilemma: full removal of the unwanted domain data is computationally expensive, while random partial removal is statistically inefficient. We find that a domain's statistical influence is often concentrated in a small subset of its data samples, suggesting a path between ineffective partial removal and unnecessary complete removal. We formalize this as distributional unlearning: a framework to select a small subset that balances forgetting an unwanted distribution while preserving a desired one. Using Kullback-Leibler divergence constraints, we derive the exact removal-preservation Pareto frontier for Gaussian distributions and prove that models trained on the edited data achieve corresponding log-loss bounds. We propose a distance-based selection algorithm and show it is quadratically more sample-efficient than random removal in the challenging low-divergence regime. Experiments across synthetic, text, and image datasets (Jigsaw, CIFAR-10, SMS spam) show our method requires 15–82% less deletion than full removal for  strong unlearning effects, e.g., halving initial forget set accuracy. Ultimately, by showing a small forget set often suffices, our framework lays the foundations for more scalable and rigorous subpopulation unlearning.

Published as a conference paper at ICLR 2026
DISTRIBUTIONAL MACHINE UNLEARNING VIA SELECTIVE DATA REMOVAL
Youssef Allouah Rachid G Koyejo* Stanford University, USA EPFIL, Switzerland (yallouah, sanmi] stanford. edu
ABSTRACT
Machine learning systems increasingly face requirements to remove entire do- mains of information-suct as toxic language or biases-rathe than individual user data. This task presents dilemma: full removal of the unwanted domain data is computationally expensive, while random partial removal statistically ineffi- cient. We find that domain's 's statistical influence is often concentrated in small subset of its data samples, suggesting a path between ineffective partial removal and unnecessary complete removal. We formalize this as distributional unlearn- ing: a framework to select a small subset that balances forgetting an unwanted distribution while preserving desired one. Using Kullback-Leibler divergence constraints, we derive the exact removal removal-preservaitee preservation Pareto frontier for Gaussian distributions and prove that models trained on the edited data achieve correspond- ing log-loss bounds. We propose a distance-based selection algorithm and show it is quadratically more sample-efficient than random removal in the challenging cow-divergence regime. Experiments across synthetic, text, and image datasets (Jigsaw, CIFAR-IO, SMS spam) show our method requires 1 15-82% less deletion than full removal for strong unlearning effects, e.g., halving initial forget set accu- racy. Ultimately, by showing a small forget set often suffices, our framework lays the foundations for more scalable and rigorous subpopulation unlearning.
INTRODUCTION
As machine learning models persist in production, the data on which they were trained often be- comes legally or ethically objectionable, requiring deletion. The nature of these requests is now scaling beyond individual user data towards erasing entire subpopulations, which can represent unwanted domains, concepts, or any data-defined construct, e.g., harmful biases toxic lan- guage (Kurmanji et al., 2024). This new scale of unlearning presents a dilemma. On one hand, removing the full set of domain data involves a prohibitive cost, since the computational cost of efficient removal methods typically scales with the size of the forget set (Guo et al. 2020). This challenge highlighted in efforts unlearn creative works like the Harry Potter book series (Eldan & Russinovich] ) where the sheer size of the identified text and the trained model make the sub- sequent unlearning action computationally expensive. On the other hand, removing a random small subset can be statistically inefficient because the statistical footprint of the domain persists. For instance, large language models can still verbatim reproduce training sequences even if the specific source text is removed (Liu et al. 2025), due to overlapping context with the remaining data. This dilemma, between the expensive cost of full removal and the ineffectiveness of naive partial removal, leaves a methodological gap for a more targeted and efficient approach domain unlearning.
To address this methodological gap, we start with a key observation: domain's statistical influ- ence is often concentrated in small, high-impact subset of its samples. This suggests an optimal strategy exists between the two extremes: a targeted removal of only this impactful subset, which can be both computationally efficient and statistically effective. To formalize this, we model do- mains as unknown probability distributions, well- precedented abstraction in both statistical learn- ing (Shalev-Shwarte & Ben-David 2014) and natural language processing (Blei et al. 2003 Sri- vastava & Sutton 2017). This statistical framing allows us to pose precise research question: what is the minimal set of data points to remove make the data distribution far from an un- wanted domain, yet simultaneously close to retained one? We introduce distributional unlearning, an information- -hheorrttittttticcccooooo framework that quantitatively addresses this question. This data-centric,
Work done while EPFL.. Code available http://gghha...ommysshhaaainnnnn

---

Published as a conference paper at ICLR 2026
statistical framing is complementary to the rich literature what term sample-level unlearn- ing: methods that efficiently approximate retraining without a pre-defined set of individual records. While prior work sample-level methods, based influence functions (Guo et al. 2020 or data sharding (Bourtoule et al. 2021), have made important progress on the computational problem, they do not address the statistical question of which samples should constitute that set for maximal im-
pact. Similarly, while class-level unlearning (Tarun et al., [023] Kodge et al.) (024) and concept erasure (Ravfogel al. 2020 Belrose al., 2023) methods also operate on certain domains, they either act on model's internal representations making the changes potentially reversible- or lack a formal method for finding a small subset to remove. This leaves our foundational question unan- swered: which samples to remove in the first place?
Contributions. We summarize our contributions tackling the above question as follows:
Framework: We formalize distributional unlearning, a data-centric framework that uses Kullback-Leibler divergence constraints balance removal and preservation guarantees.
Pareto frontier & downstream guarantees: We derive the closed-form Pareto frontier of achievable removal- preseevarrssrotiioon levels for exponential families. We further prove our framework provides log-loss shift guarantees for downstream models.
Algorithu & sample efficiency: We study the sample complexity of distributional unlearn- ing with both random and selective removal mechanisms. We propose cestance-basee selection algorithm and prove that it achieves a quadratic improvement in sample efficiency over random removal in low-divergence Gaussian regimes.
Empirical validation: We validate our framework on synthetic, text, and image data (Jig- saw, CIFAR-I0, SMS spam). While our synthetic analysis suggests high potential data efficiency gains up to 82%, real-world data complexity reduces these to still-sinnifccant 15-50% in deletion budget savings. We show these data savings hold in combination with various downstream sample-level unlearning methods.
1.1 RELATED WORK
Sample-level unlearning. Sample-level unlearning has made impressive strides in fast model up- dates and formal deletion guarantees (Neel et al. I: Zhang et al. 2024a Chien et al., 2024 Allouah et al.) 2025 Koloskova et al. 2025). Izzo et al. (202)) use influence-
updates to approximate the effect of deleting single point without full retraining; Guo et al. (2020) provide certified bounds on how close the post-deletion model is to a seratch-retrained one: Bourtoule et al.
(202I) employ data sharding efficiently erase small batches. However, this class of methods does not address which or how many samples must be removed to eliminate domain's 's overall statistical footprint. Our work complements these techniques by asking not just how to update a model once samples are flagged, but which samples to flag in the first place, and in what quantity.
Concept erasure. Concept erasure methods tackle unwanted attributes in learned features. INLP (Ravfogel et al. 2020) repeatedly projects out directions predictive of a protected attribute; counterfactual augmentation (Kaushik et al., 2020) synthesizes targeted data to sever causal links; adversarial training (Flazar & Goldberg 2018) trains encoders to remove specific signals. These operate post-hoc on fixed model's s representations-iidn getder-but they rely white-box access and tailor to one model at a time. Where concept erasure edits model representations, we edit the data, guaranteeing forgetting for downstream models.
for fairness use-cases such as removing
Coresets & domain adaptation. Domain adaptation theory (Ben-David al. 2010) seeks to mini- mize the impact of divergence between domains; we flip this paradigm by intentionally increasing di- vergence from unwanted source while controlling proximity to desired one. Similarly, our work inverts the goal of coresets, which approximate a single distribution for efficient training (Mirza- soleiman al.] 2020 Gentile et al.. 2024). Coreset methods are designed for a one-distribution problem, whereas we select samples from an unwanted distribution based on their relationship to separate, retained distribution. This two-distribution approach is critical; our experiments show that a coreset- based baseline is inefficient for unlearning because it ignores the retain data.
2 DISTRIBUTIONAL UNLEARNING: DEFINITION AND IMPLICATIONS
The predominant paradigm in machine unlcarning, which we call sample-level unlcarning, addresses the computational challenge of fully removing a known finite set of data points. This work addresses
2

---

Published as a conference paper at ICLR 2026
complementary scenario, which we call distributional unlearning, where the goal is to erase the sta- tistical influence of a subpopulation. In this section, we formalize this task, establish its fundamental trade-offs, and prove its consequences for downstream predictors.
Problem Statement. To make the abstract abstract of the unwanted domain tractable, we first model it as an underlying probability distribution P1- This abstraction, common in statistical machine learning, allows us to set a mathematical objective: to construct a new data distribution p that is statistically distant from pl yet remains close retained distribution p2- In practice, these true Ji=l distributions are unknown. We instead work with finite sets of samples: S = {xx, p drawn i..dd from unwanted distribution Pl, and S2 = [-1 {_) from retained distribution p2. Crucially, we assume these sets are obtained via some upstream process, such as keyword filtering (as in our Jigsaw experiments), the output of pre- pre-trained classifier. or human annotation. Our contribution is to solve the subsequent statistical problem: given these identified samples, which subset should be removed to most efficiently achieve our objective defined at the distribution level?
To formalize our objective, we choose Kullback-Leibh (KL) divergence because it enables con- trol over the expected log-loss of downstream models, hence connecting data-level edits to pre- dictive outcomes. We recall for two absolutely-contimuuus distributions q: p on data space X' that (11l)))=== Jx g(xr) log q(a) dr.
p(x)
Definition 1 ((a, e) -iDistrrbbttional Unlearning). For tolerances a, > 0, a distribution p E
P
satisfies (a, ( distribbtiin unlearning with respect to (PI.P2) if:
KL(P: p) 2 (removal),
KL(p2 |l p) S (preservation).
(1)
The first inequality forces the edited data to be information-thhorttical distant from the popula- tion we wish to forget. The second inequality upper bounds collateral damage to the population we preserve. While we focus KL divergence for its analytical tractability and its direct control of expected log-loss, we note that different tasks may favor different divergences, and our frame- work in principle accommodate alternative or task-weighted notions of discrepancy. In the remainder of this section, we analyze the properties of this definition at the population level, captur- ing the fundamental trade-offs and downstream learning-theorets guarantees. In Section 3 turn to the practical finite-sample setting and provide high-probability guarantees for specific removal algorithms. Throughout, we defer all proofs to Appendix A
Removal- Presevattr Trade-off. The pair (a,e) captures a trade-off: how far we can move from pi while remaining close to p2- To understand which (a,E) pairs are jointly achievable, we characterize the feasible region and its boundary. Formally, the Pareto frontier PF PF(P1, P2; P)) con- sists of those pairs (a, =) for which no strictly better trade-off exists: there no p' E P satisfying KT(p; Ilv') 2 a' and (T. (fp2llll) < e' with a' > a and e' < E. That is, every point on the frontier optimal the sense that one objective cannot be improved without worsening the other. To build intuition, we first derive this frontier for the analytically tractable case of Gaussian distributions.
Proposition 1 (Pareto Frontier). Let pi, P2 be two distributions in P, the class of Gaussian distri- butions with shared positive covariance. The Pareto frontier of (ax,e) values achievable in P is:
P2) ( (:( ((Va-VKT.ppille 2) : (T(pIlle>)
This frontier quantifies a natural, fundamental cost of distributional unlearning: a minimal preser- vation loss is incurred for any given removal level, a trade-off governed by the initial divergence KL Ip2).. The result also highlights the suboptimality of a common default: keeping only the retained data p2. While this strategy achieves perfect preservation, the frontier shows it is possible to attain a significantly higher level of removal by accepting a potentially small preservation loss. While shown here for Gaussians for simplicity, this trade-off holds more generally for regular expo- nential families (Appendix [A] Theorem 4 and is validated by our synthetic experiments (Fig. I
Downstream Performance. We now connect our data-level objective to predictive performance in supervised learning. Consider a predictor h X + A())), where X' is the input space and A the probability simplex over label space V, trained on a distribution p over X' y that satisfies (a, E) distribbutio unlearning with respect to (p1. P2). We study how performs under the true data- nata-generating distributions P1 and p2-
Let Ely. q) = log q(v), for E V.q E A()), denote the log-loss. Define the expected loss under p as ((h:p) (((.)))p ((,,,)())) h()))). Then, for any class of distributions P. we have:
3

---

Published as a conference paper at ICLR 2026
Removal Method
Sample Complexity
Removal
Preservation
Random (Prop.
3 (1 - -1 (1 (1-VE)
Selective (Thm.
n1 (1 (1)
n1 (1-1
Table 1: Summaayy of simplified sample complexity bounds, showing the number of p1 samples (out of nı 2 1) to remove to achieve (a, -distribbtiinnll unlearning with high probability. We assume ng is large, (L(p1 llpz) is small, and #22 is constant; Corollary I0 for details. The key insight is the quadratic improvement is sample efficiency of selective removal over random in this regime.
Proposition Let h minimize C(h: p). and let h2, h2 be optimal predictors under Pr. P. respectively. If p satisfies (a, dd.i)rriiiibbtiionna unlearning with respect to (p1,P2) then:
[(h; p1) - [(h1;p1) 2 81,
p(h: [(h2; S 82,
(2)
where 61 == (L(xIxllxx) = KL(p2.x (px) denote the marginal KL divergence over inputs.
These bounds show that distributional unlearning guarantees increased loss under the forgotten dis- tribution and bounded degradation under the preserved one. In this sense, our framework provides meaningful control over downstream predictive behavior. Regarding the extra marginal KI. term in the first inequality, which quantifies divergence on input distributions, the cata-ppocsssing inequal- ity gives KL(,I, x((xx) < (L (lp). hence this extra term is always bounded by the same already control. similar term appears in the second inequality, but can only improve the preser- vation bound. Finally, these bounds provide practical rule for calibrating the (a, E) parameters. For instance, if a practitioner decides they can tolerate at most a 0.1 nat increase in log-loss on the retained test set, they can set their preservation budget g 0.1. Then, the Pareto frontier (Prop. [p indicates the maximum achievable removal for this budget, in the Gaussian case. In a scenario where the initial distributions have divergence (L1 (p2) 2. this choice of corresponds the removal target of a = 3. These values match our findings in controlled experiments (Fig, 2 2nd column).
ALGORITTMS AND SAMPLE COMPLEXITY
The previous section defined our framework the population level. We now turn to the practical finite-sample setting, where we must achieve (ax, E) --diitributional unlearning using only the drawn data samples introduced in Section 2 To build analytical understanding of the finite-sample be- havior, we analyze the problem in an idealized but foundational setting: univariate Gaussian distribu- tions with known variance. This tractable setting allows us derive closed-form sample complexity bounds, providing crucial intuition about the relative efficiency of different removal strategies. We then validate that these insights generalize empirically to more complex settings Section 4
In the following, we introduce and analyze two deletion strategies: a random baseline and a selective, distance-based method. We focus on the class of distributions P {N, o²): μ R.. with known a > 0. Given no1 i.i.d. samples from the unwanted distribution P1 E P and from the retained distribution P2 E P, and deletion budget S f S n.. we derive high-probability bounds on the resulting (a,, ddistributio unlearning guarantees. We defer all proofs to Appendix A
3.1 RANDOM REMOVAL
We begin with baseline deletion strategy that treats every sample equally, deleting f points chosen uniformly at random from the n samples of p1. The formal procedure is follows:
Algorithm (Random Removal).
1. Randomly select out of the n1 samples of pı without replacement.
2. Remove those f samples.
3. Re-fit (f, o²) by MLE (maximum likelihood estimation) on the remaining data.
The following theorem provides a finite-sample guarantee for achieving (a, e) -iistrributti un- learning using random removal with deletion budget f.
Proposition 3 (Random Removal). Let P1.P2 E P and 8 E (0, 1). We observe n, samples pt and 122 samples from p2, and randomly remove f samples from pn before fitting. With probability
4

---

Published as a conference paper at ICLR 2026
1 - 6, the resulting MLE distribution satisfies ( disttribbuti unlearning with:
111
-
3ln(4/8)
111
2
3
KI,(p) 12)
1
2
1/2
2m2
11 {
2
kTp(1 || p2) + 3ln(4/6) (1+
n1
8 S
f2
72
n2
This result shows that the effectiveness of random removal is driven by the ratio of remaining un- wanted samples to retained samples m=ي An interesting aspect of these bounds is the quadratic dependence on this ratio, which indicates diminishing returns: each subsequent random deletion provides progressively less of an unlearning effect. This quadratic relationship stems from the con- centration of the empirical mean, whose variance scales inversely with the sample size. While conceptually simple, this method's 's inefficiency arises because treats all samples equally, failing to prioritize those that contribute most to the unwanted statistical patterns.
3.2 SELECTIVE REMOVAL
We hypothesize that a more effective strategy than random removal should prioritize which samples to delete, using pa as reference. Since our goal is to shift the dataset's empirical mean away from the unwanted center μ41 and towards the retained center 122 the most impactful samples to remove are those from P1 that are furthest from μlg. This intuition leads to our proposed selective removal strategy, which uses the empirical mean of the retained data üi reference point for selection.
Algorithm (Selective Removal).
1. Compute the mean وa of the n/2 samples from p2-
2. For each the n samples v; from Pt, compute the score 8; = |r -
3. Delete the f samples with the largest scores s;.
4. (V o²) by MLE on the remaining data.
The following theorem provides a finite-sample guarantee for achieving diittiiiitiiiii un- learning using selective removal with a deletion budget f.
Theorem 1 (Selective Removal). Let Pi,Pa E P and 8 (0, 1). Let f samples from pi be re- moved according to Selective Removal. With probability 1 5, the resulting estimate satisfies (a, ...d)ddiibbbbttonnal unlearning with:
a 2 KL l1
1/11 Th -
2
10-(1-1 9
1
In(4//),
KL(p) pa)) In(4/0)
2
2
2n1
122
R1-$
11
2
g-1(1
f
In(4/6)
KL(pi || ) + ln(4/6)
112
2n1
where ((u:k) == Φuu 22k) + ( uu + v 22x) 1, for u,
0, and t is the stundard normal CDF
While the above expression is more complex than that of Prop. 3 reveals a significant improvement in efficiency, materialized the term involving the inverse CDF g (- :)). Intuitively, this term represents a quantile of folded normal distribution, shifted by we are truncating the distribution of scores by removing those the tail. Specifically, this term strictly amplifies the quadratic decrease in f. which was the best could previously obtain with random removal. This amplification is greatest when the distributions are close (the low-divergence regime), the "outler" samples are more distinct and their removal provides greater and more targeted shift in the empirical mean. As we summarize in Table derive formally in Corollary IO (Appendix (A). this improved leverage translates directly into quadratic improvement in sample efficiency over the random baseline in low-divergence regimes. This theoretical advantage is core finding of our work and is empirically validated in our experiments (Fig. 2
(TT(Pll)22)) and arises because
EMPIRICAL VALIDATION
We now empirically evaluate our distributional unlearning framework across several case studies, moving from synthetic more complex real-world data. These experiments are designed to validate
5

---

Published as a conference paper at ICLR 2026
Domain
Separability
Target on P1
Random
Selective
Savings
Gaussians
Low
KL(pi [p)
65
18
82 %
Gaussians
High
(p(pi lp)
65
50
50 %
Jigsaw toxic comments
Low
Recall
100
85
15 %
SMS Spam
Medium
Recall
90
75
25 %
CIFAR-10
High
Accuracy
80
50
50 %
Table 2: Deletion budget (%) needed reach half of the initial value of the removal metric (no selective removal score;
deletion) on each dataset. "Selective"=bbes-perfrri size reduction versus full removal, i.e. retrain on p2 samples only. Gaussians (low) and (high) are the papparabliit"summmarrr
scenarios of the top leftmost and rightmost plots of Fig. 2 respectively. how distinguishable the domains are; the observed savings follow this difficully.
the qualitative trends predicted by our thebry-notably, the superior sample efficiency of selective removal- aathval-rather than to directly apply Theorem I and Proposition 3 which assume Gaussianity. To this end, we operationalize abstract domains using well-defined proxies, e.g., keyword-based subsets, image classes. This allows for a reproducible evaluation of our selection algorithms, while acknowledging that the upstream task of identifying such domains in the wild is a separate challenge.
Our validation begins with synthetic Gaussians to directly verify our theoretical predictions in controlled environment. We then move to high-dimensional real-world data, starting with the case of well-separated distributions (CIFAR-10), showing our framework generalizes standard class un- learning. We then test our framework in the more challenging scenario of intertwined distribu- tions (Jigsaw toxic comments), where the unwanted domain semantically linked to the main task. Finally, we demonstrate the broad applicability of our data-centric approach by using it as an efficieney-boosting front-end for existing sample-level unlearning algorithms. We defer results on an additional text dataset (SMS Spam) and full experimental details to Appendix B
Results overview. We summarize our main empirical findings in Table 2 Our synthetic experi- ments directly validate our theory, showing data savings of up to 82% in the low-divergence Gaus- sian regime, where our analysis predicts the greatest advantage. Crucially, this insight generalizes to high- high-dimensional non- non-Gaussian text and image data, where selective methods still provide signif- icant 15-50% data savings. As expected, the magnitude of these gains is more modest than in the idealized theoretical setting, reflecting the increased complexity of real-world distributions. Across all experiments, these removal gains are achieved with negligible impact on performance on the re- tained domains, confirming the downstream performance guarantees predicted by Proposition 2 In particular, the intertwined distribution case study on Jigsaw confirms that simply deleting all is suboptimal, as discussed after Proposition]] [ Finally, we show in T our selection methods combine effectively with various sample-level unlearning methods, not just retraining from scratch.
4.1 SYNTHETIC GAUSSIANS: PARETO FRONTIER AND SAMPLE EFFICIENCY
We first validate our theoretical framework in controlled setting, designed to directly verify the analytical predictions made in Sections and 3 the Pareto frontier shape and the superior sample ef- ficiency of selective removal. We set p1 (0, 1) and P2 -N(,, 1) for varying μ {0.5, 2.5, 5), which allows controlling the initial divergence KL(p) (l i.e., intertwinement level. For each con- figuration, draw n11 n22 1000 samples from p1 and p2, respectively. We implement the two mechanisms from Section 3 random and selective removal. After deleting f samples, we re-fit Gaussian p = ((, 1) on the retained pi and p2 samples. We then compute forward KL divergences = (L lIp) and æ = (L(p2)lp) to quantify forgetting and preservation, respectively.
Pareto frontier. Figure D confirms that the empirical (a,e) trade-off closely matches the theoretical Pareto frontier de- rived in Proposition [] To plot feasible empirical trade-offs, we set p N(H, 1) and vary μ E IR, while pı (O( 1) and P2 = (2, 1) so that <T.(pIl(p2) 2. The latter quantity is the threshold predicted by the theory, and validated by Fig- ure I Indeed, feasible trade-offs whose removal divergence a They are domi-
25
Two soud Mizi
2.0
255
2.0-
500
is below this threshold are pareto-suboptingg nated by the trade-off (a = KL (lp2), = 0), which can be achieved with the choice of distribution p p= P2-
Figure 1: Synthetic Gaussians. The empirical frontier aligns with the theoretical prediction.
Sample efficiency. We next compare the sample efficiency of
the two removal strategies analyzed in Section 3 In Figure 2
we plot removal a function of
6

---

Published as a conference paper at ICLR 2026
(s), p.m2.5
2.2
2.23
22-
14-
1.4
Semvies (1
Seriless rerweed))
Sanile rerseesd
Fresenvation (2), 1o
Preservation DrL, 2.
pe050
6.05-
25-
2.0
344
3.0
2-2
C55
Semoiica 1omovod (T)
Sumipia 12
Sumplo romooved 11
Figure 2: Synthetic Gaussians. Selective removal consistently requires fewer deletions, especially when (pIl)))p) is small (left), for the same removal and preservation target as random removal. In high-divergence regimes (right), the gap between methods shrinks, as predicted by the theory.
the number of pl samples removed. Selective removal reaches higher forgetting levels with fewer deletions than random removal, especially in the low-divergence regime (122 = 0.5, top left plot). For example, to reach 0.06 nats removal divergence, i.c., half of that obtained by removing all samples, selective removal requires 5x less samples than random removal, i.e., 10x reduction in size from full removal. Analogous trends hold for preservation (bottom left plot): selective removal more effectively preserves the reference distribution P2 throughout. The remaining plots show similar trends when increasing the divergence (L(P) llpa) by increasing /22. As in theory, selective removal offers the greatest savings when p and p2 are close and diminishes as the distributions diverge.
4.2 CASE STUDIES IN REAL- WORLD DATA
Having validated our theoretical predictions in controlled setting, we now test our framework's applicability on high-dimensional non-Gaussian data. We present two case studies representing distinct unlearning scenarios. We first analyze the CIFAR-10 dataset (Krizhevsky et al. 2014) to test our framework on well-separated distributions, showing it generalizes standard class unlearning. We then turn to the Jigsaw toxic comments datase for the more challenging scenario of intertwined distributions, where the unwanted domain is semantically linked to the main task.
Removal methods. Across both case studies, we evaluate several scoring heuristics designed to rank samples in the unwanted distribution p1 for selective removal. These heuristics are high-dimensional analogues inspired by the principles developed in our theoretical analysis. The choice of distance metric is adapted to the data modality: for the sparse, high-dimensional TF-IDF text embeddings, we use Cosine distance; for the dense CNN image features, where feature covariance is meaningful, use Mahalanobis distance" Our main selective removal strategies are: (1) distance to retained (COS-MU2 / MAHA-MU2): this heuristic is a direct analogue of the distance-based method formally analyzed in Section 3 It scores samples based only their distance to the mean of the retained distribution p2, in cosine and Mahalanobis distance respectively; (2) likelihood-ratio (LR-COS LR- MAHA): this an extension that scores samples based on a margin between their distance the p2 mean versus their distance to the p1 mean, aiming to remove samples that are both distinguishable from Pa and representative P1. in cosine and Mahalanobis distance respectively; (3) Local Density Ratio RATTOO: This heuristic estimates the local density ratio around sample using its k- nearest neighbors (A= = 10). It aims to remove samples that are much more "typical" of the unwanted distribution p1 than the retained distribution P2 in their immediate feature neighborhood; (4) Feature Norm (THIDF-NORM): This simpler baseline scores samples based on the -nrnorm of their feature vector. It serves as proxy for a sample's "informativeness" We further discuss their computational complexity in Remark 12 While our selection rules follow directly from the Gaussian analysis, note that real-world distributions can be multimodal, in which case more expressive criteria, e.g., incorporating local density or cluster structure, may further improve performance.
extremity in the feature space.
"The Mahalanobis distance of vector x to probability distribution p. of mean j and covariance Σ, is: 5--(I- n1). We estimate y and Σ, empirically on the retained distribution p2-
d(z, p) == V -
7

---

Published as a conference paper at ICLR 2026
Cal accurary vs. deletion
Kept accurary vs. deletion
0.840
06-
0.425
0.430
94-
0.825
0.820
0.415
0.1
0.410
00
20
60
102
20
60
103
cet images de aeed
7% cal images deleted
(a) Accuracy on cat images (pi, forgotten).
(b) Accuracy on non-cat images (p2, retained).
Figure 3: CIFAR-10 images. Removing cat images suppresses accuracy that class (left) while leaving accuracy on the retained nine classes essentially unchanged (right, <0.03 variation). No substantial removal is observed until 50% deletion, before selective removal strategies LR-MAIIA and MAHA-MU2 outperform random removal. Error bars: +1 standard error over thirty seeds.
Our scoring ffunctions compute similarity between forget and retain samples using finite-sample es- timates, e.g., empirical means or embeddings. When only small or proxy retain subset is available, as may occur in large-scale settings, these estimates become noisier but still supply a meaningful signal, and the distributional unlearning framework applies without modification. Extending these ideas to settings such as large language models, where the retain distribution may be approximated by a genaral-capabilities corpus, is a natural direction for future work.
Remark (Selection Budget Choice). In practical deployments, the deletion budget can be chosen in two complementary ways. First, budget may be constrained by the computational cost of a down- stream sample-level unlearning method, which case one simply targets the largest forget-set size that satisfies this constraint. Second, one may inspect the cumulative distribution of selection scores and choose the smallest subset of samples that accounts for a desired fraction of the total influence (e.g., 80%), analogous coverage thresholds used in data pruning.
4.2.1 CIFAR- 10: VALIDATION ON SEPARAAED DISTRIBUTIONS
We first validate our framework on well-separated distributions using the CIFAR- 10 dataset, treating the 'cat' class as the unwanted domain to simulate common class-level unlearning tasks. This allows us to test key hypothesis: that even within a single, well-defined class, the statistical influence distinguishing it from other classes is not uniformly distributed among its members. To test this, rank all 'cat' images based on distance scores computed in the feature space of a CNN model, aiming to find the subset whose removal most efficiently crases the class's ' statistical footprint. We delete the top ccore-ranked samples for each deletion budget, re-train convolutional neural network for ten epochs, and report accuracy on the cat test set and accuracy on the other nine classes test set.
Findings. The results in Figure our hypothesis. The superior sample efficiency of selective methods shows that even within a single class, statistical influence is concentrated. For instance, the LR-MAHA strategy halves the initial accuracy on the "cat' class by deleting only 50% of the images, making it 1.6x more data-efficient than random removal. By removing the most statistically distinct cats first, our data-centric approach accelerates the unlearning process while leaving performance on the other nine classes stable (Fig. [3b). This demonstrates our framework's 's value in class unlearning scenarios, offering a more targeted and efficient alternative to naive or complete removals.
4.2.2 JIGSAW TOXIC COMMENTS: INTERTWINED DISTRIBUTION CHALLENGE
We now test our framework on intertwined distributions using the Jigsaw toxic comments dataset. Here, the unwanted domain comments containing specific profanities (8.6% of the corpus, cho- sen keywords in Appendix B contains strong predictive signals for the main task of identifying toxicity the retained, non-profane comments. This creates a high-stakes trade-off where simply removing the entire unwanted Pi samples harms utility, fact demonstrated by the sharp drop in performance at full deletion in our experiments (F). The objective is therefore to remove the influence of explicit profanity while preserving the shared predictive features.
Findings. Our results validate the need for a targeted strategy in this setting. Figure 4a shows that recall on profane comments remains high until large deletion budgets reached, confirming the hardness of the task and suggesting that naively removing random profane comments which may be statistically similar non-profane text-is ineffective. A significant unlearning effect is
8

---

Published as a conference paper at ICLR 2026
0.-
0.6-
4.6
0.20
0.4
F2
0.5
1,50
0.00
ninder
mindon
014 of p1 removed
5/9
0.5
1.0
-14 of pa nemovadd
(a) Recall on profane comments (pL. forgotten).
(b) F/ non-profane comments (p2, retained).
Figure 4: Jigsaw Toxic Comments. Impact of removing profane comments on Jigsaw Toxic. Left: recall on the to-be-forgotten set pı; right: F on the retained set p2. Utility is almost unchanged up to 60% deletion; marked forgetting appears only around 80% deletion, with LR-COS showing the steepest drop. Error bars: 11 standard error over five randomness seeds.
only achieved by selective strategies like LR-COS, which prioritize removing outlier, distinguishable comments. For example, to reduce recall on the profane set 0.70, the LR-COS strategy achieves this same effect by deleting 80%, a 15% reduction in the required deletion budget compared to ran- dom removal, while relatively maintaining performance on the retained set unlike complete removal.
4.3 SYNERGY WITH SAMPLE-LEVEI UNLEARNING
key application of our data-centric framework to serve as an feficiency-boostiin front-end for various sample-level unlearning algorithms, as their computational cost typically scales with the size of the flagged forget set (e.g., fewer gradients on forget data, see Remark []]. First, on Gaus- sian data, pair selection method with full retraining and standard influence function-based approximation using the log-liket log-likeldhood Hessian. Second, on our more complex CIFAR- 10 class unlearning task, pair with recent methods, including finetuning and advanced, gradient-based techniques like NegGrad+ (Kurmanji et al.) 2024) and SalUn (Fan et al. 2024) (App. B.2.2) The results, summarized in Table[5] show consistent and significant improvement in sample efficiency. This advantage is most pronounced in the synthetic, low-divergence setting where our method is up to 5x more sample-efficient, and it qualitatively generalizes to the CIFAR-10 task, where our method uses a deletion budget up to 2x smaller than full removal, while achieving strong unlearn- ing effect, i.e. 20% test accuracy on forget data, with original =866 test accuracy on the retained data. Savings vary following the quality of sample-level unlearning, which is poor for naive fine- tuning, and much more interesting for SalUn, which approximates retraining standard well.
We compare against a centroid-based coreset baseline that removes the samples most representa- tive of pl (those closest to its mean); we also evaluated k-center greedy (recalled App. B.2.1] which performs near-identically. This strategy performs poorly because, in low-divergence settings, removes exactly the samples that are least distinguishable from P2-the opposite of our selec- tive method. While more sophisticated coreset methods exist, they are designed to preserve the properties of a single distribution. Our dual-distribution objective- maximize divergence from Pı while minimizing divergence with respect p2-is fundamentally different. We hypothesize that any method optimizing for within-distribution representativeness will underperform our cross- distributional approach, and leave a deeper adaptation of coreset methods to future work. Indeed, our experiments in Section B.4 with two strong gradient-based coresets (CRAIG (Mirzasoleiman et al. 2020), GradMatch (Killamsetty et al. 202T) illustrate this limitation empirically, as both out- perform random deletion yet fall substantially short of our distributional selection under matched budgets. Similarly. recent pruning methods such as TDDS (Zhang et al.) (022b)) CCS (Zheng al., 2023), and UNSEEN (Xu et al. 2025) further advance data-efficiency for training, but they remain single-distribution methods: their scoring functions are defined entirely on the training distribution. As such, they cannot exploit the contrast between the forget and retain distributions that drives dis- tributional unlcarning.
Remark 3 (Retain data assumption). When retain distribution is available, our objective col- lapses to selecting influential points within the forget distribution, which is more aligned with clas- sical coreset construction. Our experiments indicate that such finge-distributte ited in low-dit diverregee regimes: they emphasize representativeness within the forget distribution but cannot leverage the crucial contrast with the retain distribution that drives effective data removal.
methods are lim-

---

Published as a conference paper at ICLR 2026
Unlearning
Selection Method
Savings
Selection
Unlearning Method
Method
Random
Coreset
Selective
Method
Retraining
Influence Func.
Retraining
80
75
60
40 %
Selective
15
18
Finetuning
98
98
88
12 %
Random
61
91
NegGrad+
88
85
70
30 %
Coreset
63
93
SalUn
68
75
55
45 %
Table 5: Synergy with Sample-Level Unlearning. Deletion budget (in %) required to reach: (left) 20% test accuracy the CIFAR-10 10 forget class; (right) half the initial KL divergence in low- divergence Gaussians (Fig. 2 top left scenario). Our Selective removal benchmarked against Random selection and Coreset baseline across various sample-level unlearning methods. "Sav- ings" indicates the relative reduction in size of selective removal from the full forget set.
For this reason, we view acquiring or defining even a coarse proxy retain dataset (e.g., a general capabilities corpus) as an important practical consideration for applying distributional unlearning.
CONCLUSION AND FUTURE WORK
Machine unlearning increasingly requires moving beyond individual record deletion to crase the influence of entire subpopulations. We tackled the central dilemma of this task: that full removal is computationally expensive, while naive partial removal is statistically inefficient. We find that domain's statistical influence is often concentrated a small high-impact subset of its samples. We formalized this insight distributional unlearning, a framework for selecting small subset of data that optimally balances forgetting an unwanted distribution while preserving a desired one. Our the- oretical analysis provided provable guarantees connecting this data-centric approach to downstream model performance, and our experiments validated that a selective, distance- based removal strategy is often more data-efficient than random full removals across range of tasks. While our work provides a foundation for selective data removal, we acknowledge its limitations, which point to important directions for future research below.
Distributional assumptions. Our finite-sample analysis provides strong guarantees but assumes Gaussian distributions; while our experiments show the core insights generalize qualitatively, bridg- ing the gap between these theoretical bounds and the behavior on complex real-world data remains an open question. This distributional mismatch also helps explain the gap between the 82% data savings in our low-divergence synthetic setting and the still-sinnificant 15-50% savings on real data. More fundamentally, our framework operates on samples that have already been identified as be- longing to an unwanted subpopulation. This leads to an exiciting extension of our work: because we show that only a small subset is needed for effective unlearning, this creates the potential for active identification systems that could help practitioners find these few, high-impact samples at fraction of the cost of exhaustive annotation.
Data- to model-level guarantees. Moreover, evaluation of unlearning is based model perfor- mance degradation, which directly validates our theoretical log-loss guarantees. A privacy-centre evaluation could employ methods like Memhership Inference attacks (Shokri et al. 2017) to for- mally verify that the unlearned model is indistinguishable from one retrained from scratch, repre- senting another crucial avenue for future work. Conceptually, one could make formal link between the (sample-level) certified (Guo et al. 2020) and distributional unlearning frameworks.
LLM fine-tuning applications. Beyond the foundational discriminative settings studied here, there is now a rapidly expanding line of work on data selection for large language model (LLM) in- struction tuning. Classical instruction tuning (Wei et 2022). demonstrates that finetuning on curated instruction datasets can significantly improve generalization. More recent approaches focus on selecting high-quality subsets from a single instruction distribution to improve supervised fine- tuning (SFT) efficiency (Li et al.) 2024a b) Wang et al. 2025); see also the survey of /Zhang et al.) 2025). These methods aim to upweight instructive or representative examples for SFT, whereas our framework addresses fundamentally different objective: distributional unlearning requires se- lecting a deletion subset that shifts a model's behavior between two distributions. In this sense, our theory is model-agnostic and can serve the selection layer for future (multimodal) LLM unleam- ing pipelines by operating directly on data representations (c.g., LLM embeddings) and respecting forget/retain distributional structure.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
YA acknowledges support by SNSF grant 200021. 200477 and the G-Research PhD prize. SK ac- knowledges support by NSF 2046795 and 2205329, IES R305C240046, ARPA-H, the MacArthur Foundation, Schmidt Sciences, HAI, OpenAl, Microsoft, and Google. SK and YA acknowledge support by the Center for Safety.
REFERENCES
Youssef Allouah, Joshua Kazdan, Rachid Guerraoui, and Sanmi Koyejo. The utility and complexity of in- and out-of-distribution machine unlearning. In The Thirteenth International Conference on Learning Representations, 2025.
Tiago A. Almeida, José M. Gómez Hidalgo, and Akebo Yamakami. Contributions to the study of sms spam filtering: New collection and results. In Proceedings of the 11th ACM Symposium on Document Engineering, pp. 3-10. ACM, 2011.
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, and Joydeep Ghosh. Clustering with breg- divergences. Journal of machine learning research, 6(0ct):1705-1749) 2005.
Nora Belrose, David Schneider-ooseph, Shauli Ravfogel, Ryan Cotterell, Edward Raff, and Stella Biderman. Leace: Perfect linear concept erasure in closed form. Advances Neural Information Processing Systems, 36:66044 2023.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- Vaughan. A theory of learning from different domains. Machine learning, 79:151-175, 2010.
Dimitri Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 38-39, 1997.
David M Blei, Andrew Y Ng. and Michael Jordan. Latent dirichlet allocation. Journal of machine Learning research, 30an):993-1022, 2003.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Chou Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. 2021 IEEE Symposium Security and Privacy (SP), pp. 141-159, IEEE, 2021.
Eli Chien, Haoyu Peter Wang, Ziang Chen, and Pan Li. Langevin unlearning: A new perspective of noisy gradient descent for machine unlearning. In The Thirty-eighih Annual Conference on Neural Information Processing Systems, 2024. UtLhttps: /ttttpsss//peeneeieeeek net / forum? id= 3LXuC8rbyV
Rishav Chourasia and Neil Shah. Forget unlearning: Towards true data-deletion in machine learning. In International Conference on Machine Learning, pp. 6028-6073. PMLR, 2023.
Yanai Elazar and Yoav Goldberg. Adversarial removal of demographic attributes from text data. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 11-21, 2018.
Ronen Eldan and Mark Russinovich. Who's 's harry potter? approximate unlearning in 1lms. arXiv preprint arXiv:2310.02238, 2023.
Chongyu Fan, Jiancheng Liu, Yihua Zhang, Eric Wong, Dennis Wei, and Sijia Liu. Salun: Em- powering machine unlearning via gradient- based weight saliency in both image classification and generation. In The Twelfth International Conference on Learning Representations, 2024. URL
lew net /tt.e//nneeeeeeeee.eoooooooooooo
Claudio Gentile, Zhilei Wang, and Tong Zhang. Fast rates in pool-based batch active learning. Journal of Machine Learning Research, 25(262): 2024.

---

Published as a conference paper at ICLR 2026
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, pp. 3832- 3842. PMLR. 2020.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou, Approximate data dele- tion from machine learning models. In International Conference on Artificial Intelligence and Statistics, pp. 2008-2016. PMLR, 2021.
Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. Learning the difference that makes a differ- ence with sanntterfcccualllyaggeeeee data. In International Conference Learning Represen- tations, 2020. URL
net mett:/oruuml..dssllggss.
Krishnateja Killamsetty, Sivasubramanian Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning, pp. 5464-5474, PMLR, 2021.
Sangamesh Kodge, Gobinda Saha, and Kaushik Roy. Deep unlearning: Fast and efficient gradient- free class forgetting. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL
https::/openreviii
net / forum d== 5p6wwB110
Anastasia Koloskova, Youssef Allouah, Animesh Jha, Rachid Guerraoui, and Sanmi Koyejo. Certi- fied unlearning for neural networks. In Forty-second International Conference on Machine Learn- ing, 2025. URL
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 10 dataset. online: http://www. cs. toronto. edw/rriz/cfaa: hmm,, 55(5), 2014.
Meghdad Kurmanji, Peter Triantafillou, Jamie Hayes, and Eleni Triantafillou. Towards unbounded machine unlearning. Advances in Neural Information Processing Systems, 36, 2024.
Ming Li, Yong Zhang, Zhitao Li, Jiuhai Chen, Lichang Chen, Ning Cheng, Jianzong Wang, Tianyi Zhou, and Jing Xiao. From quantity to quality: Boosting IIm performance with self-guided data selection for instruction tuning. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Vol- ume 1: Long Papers), pp. 7602-7635, 2024a.
Yunshui Li, Binyuan Hui, Xiaobo Xia, Jiaxi Yang, Min Yang, Lei Zhang, Shuzheng Si, Ling-Hao Chen, Junhao Liu, Tongliang Liu, et al. One-shot learning instruction data prospector for large language models. Proceedings of the 62nd Annual Meeting of the Association for Computa- fional Linguistics (Volume 1: Long Papers), pp. 4586 4601, 2024b.
Ken Liu, Christopher A. Choquette-Choo, Matthew Jagiclski, Peter Kairouz, Sanmi Koyejo, Percy Liang, and Nicolas Papernot. Language models may verbatim complete text they were not ex- plicitly trained on. In Forty-second International Conference on Machine Learning, 2025. URL
net net. / forum wwt.ee/eeeeeoooooooooooo........ 1d-=bl1kIbbbbbc.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp. 6950-6960. PMLR, 2020.
Seth Neel, Aaron Roth, and Saeed Sharifi- Maleriiiiaaajjridi. descent-to-delete: Gradient- based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Shauli Ravfogel, Yair Elazar, and Yoav Goldberg. Null it out: Guarding protected attributes by iterative nullspace projection. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7231-7245, 2020.
Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
12

---

Published as a conference paper at ICLR 2026
Akash Srivastava and Charles Sutton. Autoencoding variational inference for topic models. In International Conference on Learning Representations, 2017. URL httttp:://peeeeeiiee:
Dett/Eorun?2Ld=3yEEVV..
Ayush K Tarun, Vikram S Chundawat, Murari Mandal, and Mohan Kankanhalli. Fast yet effective machine unlearning. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Martin Van Waerebeke, Marco Lorenzi, Giovanni Neglia, and Kevin Scaman. When to forget? com- plexity trade-offs in machine unlearning. Forty-second International Conference on Machine Learning, 2025, URL /tLLltttt///ppeeeeiiiieee htwp://wwwee//ooummm//mm forum dir.rruIirnid
net
Martin Wainwright, Michael I Jordan, el. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1-2):1-305, 2008.
Shaobo Wang, Xiangqi Jin, Ziming Wang, Jize Wang, Jiajun Zhang, Kaixin Li, Zichen Wen, Zhong Li, Conghui He, Xuming Hu, and Linfeng Zhang. Data whisperer: Efficient data selection for task-specific LLM fine-tuning via few-shot in-context learning. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meet- ing of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 23287-221 2-305,,, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-89176- org/2025.
251-0. doi: 10. 1135/
1135. htanttss:/aclaatitttee
Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, An- drew M Dai, and Quoc V Le. Finetuned language models zero-shot learners. In International Conference on Learning Representations, 2022.
Furui Xu, Shaobo Wang, Luo Zhongwei, and Linfeng Zhang. Rethinking dataset pruning from generalization perspective. In The Future of Machine Learning Data Practices and Repositories at ICLR 2025, 2025.
Binchi Zhang, Yushun Dong, Tianhao Wang, and Jundong Li. Towards certified unlearning for deep neural networks. In Proceedings of the 41st International Conference on Machine Learning, pp- 58800-58815 2024a.
Bolin Zhang, Jiahao Wang, Qianlong Du, Jiajun Zhang, Zhiying Tu, and Dianhui Chu. A survey on data selection for I1m instruction tuning. Journal of Artificial Intelligence Research, 83, 2025.
Xin Zhang, Jiawei Du, Yunsong Li, Weiying Xie, and Joey Tianyi Zhou. Spanning training progress: Temporal dual-depth scoring (tdds) for enhanced dataset pruning. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 26223-26232, 2024b.
Haizhong Zheng, Rui Liu, Fan Lai, and Atul Prakash. Coverage- centric coreset selection for high pruning rates. In The Eleventh International Conference on Learning Representations, 2023.
13

---

Published as a conference paper at ICLR 2026
A PROOFS
A.1 PARETO FRONTIER
Proposition 1 (Pareto Frontier). Let P1-P2 be distributions in P, the class of Gaussian distri- butions with shared positive covariance. The Pareto frontier of (a, values achievable in P is:
PF(PI.P2:P) ( -v- (VV-VKIIniill)) )) :0 KT.pillea)
Proof. For simplicity, we consider univariate Gaussians with shared variance. For d-dimensional Gaussians with covariance E Rdddd the same result holds after replacing squared error by the (see Proposition 4).
Mahalanobis distance || p =
Let o2) P. Since all distributions in P share the same variance, the KI. divergence from to p pi:
KL(p:1lp) (1² 1,
20
Fix a 2 KT.(p)lp22) We want to compute the minimal possible & achievable under the constraint KT(p: (p) 2 Define this minimum as:
(N2 - 14)
min E. (a) PER, (
2220
20
This is one-dimensional quadratic minimization problem subject to quadratic inequality con- straint, The feasible set is:
(-00, 2v2a| u [m + +av2a, oo).
We minimize (#2 - 2)²² over this set. This yields two cases:
If #2 [Pn Vv 1n + a -a 22)) then the closest feasible points are the endpoints. The minimizing value of μ is:
p p= mn + sign( - m11) oV22,
and the resulting divergence
E. (a) (1/2 14 sign( m2) 2a)
20
If #l already lies in the feasible set, i.e., 1 - M1l ov 2a, then we can choose μ = P2 yielding (- = 0.
Thus, for all a 2
(1u2 - M1 M1l -01-00/2x)) 1²
(a(
202
where (x)+ = maxxfx,00 03. Let A = 122 - H1l, and recall that KL
A²
Then:
202
A = av 2KL(pillp2)
Substituting into (a:):
(a) (Va- / KKL(p) p2)
for a 2 KL(PIllp2).
Finally, note that any pair (a, with a < KL(p1 (p2) satisfies (a) = 0, hence is dominated by (KI.(p) (12). 0). Therefore, the Pareto optimal points are exactly:
claimed. {(o, aa, (Va- (KL(pilpe)) ") a 2 KL(pillps) )
14

---

Published as a conference paper at ICLR 2026
Next, show that qualitatively similar result holds more generally for any exponential-fame -amily member.
Theorem (Pareto Frontier Exponential Families). Ler (X, pi) be measurable space and let
P = { (z)) = exp((
- (())) : A E θ c CR)
be a regular minimal exponential family (carrier h > 0, sufficient statistic T: X' + Rdd po, (2),
log-partition A).
Fix pi(x)
1,2, and a 2 0. Define v(a)
inface (KL(pellpe) KL(Pillpe) 2 2). where KL(glpp) = lloolg//)) dp. Then:
(i) The Pareto frontier for points in P is
PF(pI p2; P) (a, v(a)) KL(pille2)
where v(a) = (L(p2llP)) + a x 01) (Bpa Ep (T]), and X" is the unique scalar in (0, such thut the distribution p' E P of mean Ep- Bp-(T]] X" Ez -p Epp!7 [T]
satisfies (T I|p") =
(ii) (Gaussian case) IfP (N(,, E): uu IRd) with fixed E > O, then for KL(pi 1|p)): v(a) (Va- - (KL(pillee) 2
Proof. In this proof, for fixed 2 0, we study the optimal value
v(a) inf (KL(p2)lpo) KL(Pillpa) 2 a).
d
This enables characterzing the Pareto frontier of feasible (a, a) trade-off's Below, we focus on the non-trivial case a > (L (lp2). Indeed, in the case S KL(Pi] (lp2), the problem above's unconstrained minimizer P2 is a feasible solution, so that v(a) 0 for all a S (L(pll)p))
Reparametrization and KKT. First, we recall the expression of the KL divergence in exponential families as Bregman divergence. For any 0', 0 E θ one has
(p (Ipo) A(0) A(0') (0 - (0--))TVA(0))
We let
f = (L(pll)p)), g (L(Ppllpe)
Both continuously differentiable the open set θ. The feasible set (g(0) () > a} is nonconvex,
so we check linear independence constraint qualification (LICQ, Bertsekas (1977) at any minimizer
g" To do so, recall (see Wainwright et al. (2008) that for exponential families v.((0) Ep, [T]
for any 0 E O, so that
Vg(0) = = -A(0)) + VA(O) = Ep, [T] + Ep, [T].
Minimality of the exponential family ensures Epe [T] is injective Wainwright al. 2008 This together with the fact that * pe for any feasible 0, since a > 0, implies that Vg(0*) # 0 and
LICQ holds.
Next, we form the Lagrangian
=( f(0) (()(0)) a), A2 0.
Since LICQ holds, KKT conditions are necessary Bertsekas stationarity (V&L = 0) gives
1997) for any minimizer 0*, Hence,
vf(0") À (OT)
Given that we had derived V VoKL (|pp) = = - Ep, [T] + Ep, [T], we obtain
Ep,,1 [7] + E,, [T] A (- E,, [T] EEp-
hence (1 A) E [T] [y, A E,, [7] Observe that we must have À *f 1, as otherwise E,p [T] F,, [7]. but this contradicts fact that P1 * P1 given that Ep [T] is injective for minimal exponential families Wainwright et al. (2008) Therefore, have the following:
E
T
TV (T)
E [7]
A
15

---

Published as a conference paper at ICLR 2026
Now, we observe that the inequality constraint must be active. Otherwise, the minimizer lies in the interior of the feasible set and is thus a local minimum of the unconstrained problem. The latter admits P2 unique minimizer,
the minimizer at hand must be P2 but this is not feasible since we assume (T.(p: l1P2) < a. Therefore, the minimizer must lie at the boundary of the feasible set, and the inequality constraint is active. That is, have g(0") a.
Optimal value. We are now ready to derive the expression the optimal value:
v(a)= f(#*) KL(p2llp))
We use the following classical Pythagorean-type identity for Bregman divergences (see, e.g., Baner- jee et al. [anerjee al. (2005): ):
KL(P=llp") (Palll))) + KL(p: llp') + (02 01) (VA((1)) VA((0)).
Now, consider the aforementioned KKT multiplier > 0, # such that VA((*) = Ey [T]
A [T) AV - as well as (L I|p") ( a. We thus get
A-1
v(a) = KL(p>llp") (L(Pelle)) + (L [|p") + (02 - 0,) - vA(O"))
1
<L(pellp1) + KL(p=llp*
X (02 - (0) (VA((2)) vA(O:))
1
(IT(p=)p))) + A-1 (02 01) (V ((2)) A():)))
We now again use that VA(0) Ep [2'] for all 0 θ. We then obtain:
1
u(a) = (T2lll))) ta+ - (02 01) (E (T) - Ep, (T))
(3)
Uniqueness of A. We now show that there a unique KKT multiplier À for the optimal solution.
We recall that X > is such that À + 1 and:
A E. [T] Epp [7]
Epp
g(0)) KL a.
Above, the first equation uniquely defines the distribution p", by minimality of the family, and we now show that there is only unique À of interest such that the second equations above holds.
Let 8* (A) be the unique (by minimality) parameter such that Ep. [T] AE -1-E,,
We define
A-1
H(A) = KL(Pill")) A(0*) A(02) (0) - -61) (.0TTTACI VA((1)
Taking the derivative above, we get
dH
dA (A) = (VA(0") - vA(A:)) d0"
dA (A).
We again use that First, replacing in the previous derivative equation, we obtain:
AVA(0,) - VA(O2)
A((')) = Ep. [7]
E
X-1
X A-1
dH (A) = (V^(0*) - VA(O:))
dd
dA (A) ( - (VA(0)) - vA((2)) d0
1
(A).
dA
dA
Second, taking the derivative with respect to À in the expression of VA((0) yields: d0"
V 7²A(0))
(A) dx
( 1)2 (VA(0)) AA()))).
We observe that the Fisher information matrix 2 ((("))) is positive definite since the family is reg- ular. Multiplying by the inverse of the latter then yields:
do
dx (A)
VA(00)) 1 (VA(()) VA(02)).
(x-1)3
16

---

Published as a conference paper at ICLR 2026
Plugging the above in the latest expression of the derivative of H yields:
dH
do
dx (A)
A --1 (VA(O)) AA(22))
AA (A)
1A- VA((.)) VA( A(A)))
VA(02)).
Since the matrix V²A(6") is positive definite by regularity of the family, the corresponding quadratic form above is positive (recall 01 A 02), and the sign of the derivative that of X 1. Therefore, H is decreasing on (0, 1) and increasing on (1, +.0). It is straighforward to check that H ((+) (L l122). H(1-) = H(++) = +oc, and H++00) = O. Since KL(pillp>) < a by assumption, there exists unique X E (0, 1) such that H(*)
and unique Aj > 1 such that H (At)
We now discard Aj thanks to the expression of the optimal value expression 33. Indeed. the second term in 3 is positive for Aj since Ai > and (0) (E (Lpp [T] - Ep, [T])
(12-01) (02)) (A(0)) )) > by strict convexity of and the fact that p1 7 P2. On the other hand, this same second term is negative for X since X_ < 1. Therefore, the optimal value is smaller for the choice of X so
that:
1
(a) KL(P2lPp)) + +
1- (02 01) T
[T] Ep, (21).
(4)
where X is the unique scalar in (0, 1) such that:
X E [
Epa [T]
p [T]
g(0)) = KT. (1p²)) = a.
x
Finally, we note that v(a)) is non-decreasing by definition; increasing shrinks the feasible set. Also, we recall that v(a)) 0 for all a < KL (P2), i.e., all trade-offs (a, E) with < (L [2),, >> 0 are dominated by (KL llp2), 0). Therefore, we conclude that the pareto frontier given by:
PF(pi.Pa:P) {a, v(a)) a KL(Pillp2)
Gaussian case. For P₁. N(u, E) one has T(x) x, Epg [T] = μ. and
KL Ip,.) { - 1)) T p).
By the conditions on we have
X 122
KL(pi ) a.
Using the KL divergence expression for Gaussians N E) (recall KL(N(M, E),N E))
(Jn p2) T E-1(pp (2))), get
KL(pillp)
#1 1¹¹ X 1
(A* 1)2
Solving for X E 1) yields X' = 1- / KL(P: 122)/a and
1¹ =1= + V KL(pillp2)
(122 - (11)
Thus, direct computations yield
2 (aa) [1 - ( (VKL(pillp)) va)²
with v(a) 0 a < KL P2). This concludes the proof.
Discussion. In Proposition we show that, in any regular exponential family, the trade-off between betweenn removal (a) and preservation (e) can be quantified. This yields perevvalpreservatioon trade-off curve that faithfully reproduces the soared-cov Gaussian Pareto frontier -aanely the familiar (Va- Vi-VDr 2D² parabola-wa while in other families gives an explicit but generally non-algebraic trade- off curve.
17

---

Published as a conference paper at ICLR 2026
A.2 PREDICTIVE PERFORMANCE
Proposition 2. Let h minimize L(h; p), and let h1, l/2 be optimal predictors under pt.P2 E P.
respectively. If salisfies (ax, -iistrribution unlearning with respect to (pı,p2), then:
p(); P() 2 10-00 81,
p2) [(122 S 82,
(2)
where 01 = x llxx). 62 == KL(p2.X (pX) denote the marginal KL divergence over inputs.
Proof. Let h(y x) == (v) denote the conditional distribution defined by the hypothesis h, and suppose h minimizes the expected log-loss under p. Since E(y, q) log g(y) is strictly proper scoring rule, the unique minimizer of p) is the true conditional distribution h((x) = p(: x),
where p(z. y) px (x)p(y z))
We begin by analyzing the expected log-loss of this hypothesis under an arbitrary distribution over X x V:
[(h: q) E(z,)~al- | log h(y x)] = Byynt log pvy =)].
where 9º denotes the marginal distribution of x under g. and q(- .)) the corresponding conditional.
Now recall the standard identity for any two conditional distributions q(- x)) and p(: æ):
By log ply =)) KL,( a)) p(y x)) + H z));
where Hlg(y I x)) By log q x)] is the Shannon entropy of the label distribution under for fixed æ.
Taking the expectation over xxx get:
[(h; = Bx [KL 2) ply z)) + (9(3)) x])]
= Exnux KL(g(y xx) p(y x)) + Ex H Hgggy x))-
The second term is the expected entropy, which corresponds to the Bayes-optimal risk under q:: [(h; g) inf C(h': :) Ex-qx H H(q(y) x)).
(5)
Next, we relate the expected conditional KL term to the total KL divergence between the joint distributions. Using the chain rule for KL divergence, we have:
KL(g ll p) KT( 1x) + Exngx KL(g(V x)) || ply x)).
This decomposition holds generally for joint distributions with conditional factorizations. Solving for the conditional KL. term, we obtain:
E Ex KL(g(y) x) ply x)) KL p) KL || 1x).
Substituting the above into the expression for L(h; and using (5) get:
C(h: q) KL p) (L I| p q))
(8)
We now apply this to g = Pi and q = P2, noting that p satisfies (a, e) -distributional unlearning, i.e. KL(p1 |l p) 2 and KL(y2 p)
For P1. we define 6, = (L || p and compute:
((h:p)) L(hip1)) = KL(p1 || p) KL(PN 110*==Ka KK(p1 11 -6 81-
For P2, define 82 KL x) and similarly compute:
C(h: L(h2: KL |l p) KK ll xxxx KL(P2 1p) 53 S 82.
This completes the proof.
18

---

Published as a conference paper at ICLR 2026
A.3 RANDOM REMOVAL
Lemma 5 (Finite-sample concentration). Let p be the empirical mean of n samples drawn from N(,, For any 8 E (0, 1), with probability at least 1 8, we have
ln(2/0)
l/ - 14) S V
n1
Proof. This follows directly from Hoeffding's 's inequality for sub-Gaussian variables.
Proposition 3 (Random Removal). Let p1.P2 P and ô (0, We observe n samples from pi and n2 samples from p2, and randomly remove I ssamples from before fitting. With probability 1 6, the resulting MLE distribution satisfies (a, di-dtttibbutionall unlearning with:
n1 -1-1)
3l((4/))
121
2
- 3
KL(Pi 11)
1
1
2
112
2nz
111
2
KL |l p2) + 3ln(4/8)
1+
n1
-J
$S3
712
72
12
Proof. We recall that p1 = (V((,,o)), = Nu od) E P and p p== NW, o²) E P are univariate Gaussian distributions. We are given nn i.i.d. samples xi (1) (n1) from pt and my i...d samples (mz) from p2.
222
22
Upon removing f S. n, randomly chosen samples #1 ,..., we set the center μ of the unlearned distribution p to be:
(1)
(m1-f) from the target distribution Pl.
(n1 - f) + n2
f +
where رb == n Den's bound (Lemma 5
(i) and fu = 1 Ei x2
(
We also observe that a standard Hoeffding
ny
yields that:
2l1(4/))
2 2ln(4/5)
AA - M1l S V
|A2 uel S V
(10)
72
each with probability also recall that
5. so that both hold with probability 8 thanks union bound. We
KL(pI 11 (w) =1)²
KL(p2 () (#2 n1)
(11)
20
2g
Preservation bound. First, we upper bound the KI. divergence of p2 from p. To do so, we first use the triangle inequality to get
(n1 f)An + n2fi2
n1 5
n2
|1 - 12l
112
(f1 - ()2) +
(fl2 - p2)
111 f + n2
ff + 122
111 - n22
11 f
n1 f
f
112
(11 H22 +
(f1 - -41) +
(f22 42)
f +
n1 f + 722
111 - f +
71
|M1 Mel
111 f
Ip= M1
+
112
102 μ2
71 f + 12
111
+ n22
n1 f
+ 122
Therefore, using (TOp we have with probability
6:
71
2mm(4/8)
72
2ln(4/8)
J U2l < m1 - f + n2
[11
12
M1 f + n2
711
112
112
Taking squares, using Jensen's inequality, and simplifying further since f 2 0. yields:
11- 1221 <
111
n2 /)
102 u22 +3
m1 /)
o²
2 21 (4/0)
02 6ln(44))
(12)
n2
n1 f
122
19

---

Published as a conference paper at ICLR 2026
Dividing both sides by 2x² and then using (28
yields with probability 1 - 5:
f n2
31m(4/6) (1+
KL(p2 || p)
KL p2)
(13)
n2
T12
Removal bound. Second, lower bound the KI. divergence of pı from p. To do so, Jensen's inequality and (12 to obtain that, with probability 6, we have
H1 -22l = =1p1 - μl + -22l S 2| -u12 21 u2l2
2| 11? +
11 -1--
2
|
u
u2|²=
60 2 In(4/5)
71 - 1
112
7/2
Rearranging terms and dividing by 2 along with (28 yields that with probability 1 1 - we have
(T p)
11
U212
111
I
uzl
3 (4(04)
(1
-
20²
40
n2
20
2nz
71
111 - -
3ln(4/0)
3
KL P2)
1
2
122
2nz
72
Conclusion. With probability
we have (a, () distribbutii unlearning with
n11
-
KL || P2) 3l1(4/8)
1h
3
1
2
112
2n2
T12
711
f
2
KL(pi || p2) + 3lm(4/))
(1+ 1
11
8
S
11/2
112
112
A.4 SELECTIVE REMOVAL
Lemma 6 Kieeeky--KKeeerwolfowwo Inequality). Let F1, I2...., En be independent and iden- tically distributed random variables with cumulative distribution function F. Define the empirical distribution function by
F(1) Σ
Ha. S $t..
Then, for any E (0,1), with probability at least 1 we have
ln(2/6)
F(t)) -F(())()) S
sup EER
2n
Lemma 7. Let Pl, U2 E o Consider nı i..dd samples xx ...
( from N( o²) and
(a1)
(nz) ....,,((m)) from N NH22 (²)) We define juz the average of the samples from n2 iidd samples 222
(1)
N o²), ii the average of the n, - nı closest samples from (2)2) ,...,,
(n1) to pzz We define ④ -11p-1121 where ob is the standard normal CDF.
Fit E IR + Φ(" ((lllu)
For any 8 (0, 1), we have with probability 1- 6.
f
(2(2/))
/22 5
F-1
+
(14)
71
2n1
(5) that fij is the average of the n, - samples, out of n, i.i.d. from Pt, with the closest distance A2, the empirical mean of na samples from P2-
Proof. Recall from Equation
20

---

Published as a conference paper at ICLR 2026
Denote by 7y | m j22 the (m immediate from the triangle inequality that
f)tth largest distance of j02 pi samples. It then
B1
m1 f
(ini)
((m))
li1
P2l
H2l
n1 a
P2l
S fy.
(15)
R1
f
Besides. denoting by F1 the empirical
CDF of the empirical distribution
over
{14 (8) P2l e [. have for all t R:
1 M1
(t)
ni Σ 1
(16)
Yet, recall that with probability 1 - 2, we have
2 2ln(4/6)
A22 p2l S Vo
(17)
n12
Therefore, the triangle inequality gives for i [m1]. |0)1 (6) ( and we deduce
|m)
(i)
pel S |z]
P2l +
102
pl 1
Do +
o
12
1 T1
1 a1
(t)
71
malse)
n2
1
|x
(9)
s n22
2lm(4/8)
(18)
In particular, by definition of ły. we have
2lm(4/))
1
711 f
( + +oV
(19)
|x palstt)
112
71
81
T01
Now, observe that |z
(2)
p2l
follows folded normal distribution of location μ4 #2 and
scale o², since (f) follows N(m.oo²) Denote by Fj its CDF. Thanks to the Dvoret- -eeeeiffr-Wolfoiiii inequality (Lemma we have with probability 1 that for all e R
In(4/8)
(20)
2n1
Plugging the above in the previous inequality, and using a union bound, we get with probability 1- 8,
2 2l((4/)) S Fitt + V
2m((4/8)
In(4/))
f
In(4/0)
Filty + V
(21)
n22
2n
2n
By taking the inverse FT1 of the CDF F1 and rearranging terms, we obtain with probability 1 - that
f
In(4/5)
2l((4/)
ビ S
F
1
(22)
ni
2n1
n2
Finally, going back to 15 we obtain with probability 1 1 8 that
S
In(4/8)
2 2ln(4/8)
j pal < fy FT-1
1
+
(23)
2n
72
21

---

Published as a conference paper at ICLR 2026
Lemma 8. Let Ml, U2 E R and suppose that ~ (122,03) Define the random variable 2
x Pal, with cumulattve distribution funciionn
1111 N2l
$ 1
p2l
P
t t 0,
0
where & denotes the standard normal CDF. Then, for any p E (0, 1) the inverse CDF satisfies
| -
F =0 pp 20
where the function g(u; k) is defined by g(u; k) = +buu 22x + D(u + 22K) - 1, and g - k) denotes the inverse function in u satisfying g(u; x) = p. In particular, when μl P2 (so that 0) have g(u: 0) (2) 1 and thus Fo.1 (p) + p+1
Proof. Since x N(11; 2 we have that |x 12 has CDF
(1) = P1 U2
+ 11
M2l )
1 2 0.
Introduce the change of variable == 1 that t Then,
Fo(ou) 2 =0(u | U2l (-u
M1 p2l
0
Using the symmetry o ((-x)= = (x), this becomes
+ 20uu( uu M1 H2l Fo = 20u |1| u2l
1.
Defining
Iii p and setting 20
g(u; K) = 4(u - V2x) + + + V2x) - 1,
we have Fo = g(u; Thus, if u² is the unique solution of ;("";)) = p. then
Fo(au))= =
so that
(p) ou" = -p;x)
In the special case 141 = (12 (so that ń = 0), we obtain g(u; 0) = 20( 1, whose inverse is given by u = t 1 ((p + 1)/2). Hence, Fi-1 = tb ((p ( 1)2).. as required.
Theorem 1 (Selective Removal). Let p1, P2 E P and 8 E (0, 1). Let f samples from P1 be re- moved according Selective Removal. With probability 1 6. the resulting estimate satisfies (a, eiddistributional unlearning with:
1 KL(pi |2)
1/mi -
g-'(1
f
In(4/6),
KL(PI p²))² In(4/6)
a 2
9
+
112
n1
2n1
722
ES
11
2
9
0-1
f
in(4/0).
KK[(pI p2))
+
2ln(4/8)
122
n1
2n1
n2
where g(u; x) T(u /2k) + ( + v 22x) 1, for u, 0, and t is the standard normal CDF.
Proof. We recall that p1 NNH P2 N o²) E and p p= N o2) E P are univariate Gaussian distributions. We are given ny i.i.d. samples x I (n1) from P1 and n2 i.i.d. samples 22 22 ((12) The distance-based selection removes f < n, selected samples from the target distribution Pı with the largest distances to ji2 n2
(92) from p2-
1 > ク 22
(8) the empirical estimator of the mean of p2- That is,
22

---

Published as a conference paper at ICLR 2026
(1mm) (mim)) denoting by si 11.1,
the original m samples from Pi reordered by increasing distance
to jiz:
|1] (1mm1) Azl - S [a]
|
(nam))) Pal:
(24)
with ties broken arbitrarily, then distance-based selection retains only #1 obtain
(1mi) (nu f.ll)
21
to
(im1)
A1
11
(25)
Subsequently, we the center of the unlearned distribution be:
(m1 f) + nz
(26)
111 f +
where ii 7 Di (im1) and ju2 D 12 ing bound (Lemma 5)
We also observe that a standard Hoeffd-
yields that:
2ln(4/8)
102 12l S Vo
(27)
n12
with probability 1 2. We also recall that
KL(pi I] (#1 12)
(#/
11)²
KL(p2 || p)
(28)
20²
20
Preservation bound. First, we upper bound the KL divergence of p2 from p. To do so, we first use the triangle inequality to get
110
122
(m1 f) + n2j22
122
111
ʃ
(fi - u22) +
712
(fr2 p2)
71 - f + n2
n11
+ 122
n1 - f + +
Th f
lia
p2l
112
1102 122
n1 f + n2
n1
+
n2
Therefore, using 27 we have with probability 1
| μ2|
li
P2
+
122
2 2m444)
11 + n2
711
f
+ 422
112
Moreover, know from Lemma that with probabilty 1 1 5
(1- f
In(4/6)
l
u2l S F-1
+
n1
2n1
Using the above in the previous inequality with a union bound, yields that with probability
| pal S n1 F-1
1
+
In(4/5)
n1 f n2 VV
112
2ln(4/8)
112
2n1
122
We further simplify the above using Lemma
8
which implies that for all p
F-)(p) aa--- p; |
-122
202
where the function g defined by g(u, x) = Φ(u v 2x + + 22x) this in the previous bound yields
1or u, Plugging
n1 f
1 (1
f +
In (n(4/))
|11 -121
H2
Y22
2 ll((4/)
|p 42l <
+
+ 112
711
2n
20
711
f + 722
722
(29)
23

---

Published as a conference paper at ICLR 2026
Dividing both sides by 0 and then using (28
yields with probability 1 1-6 5:
(TL 1I S
m1 - (1
+
In(4/6)
KI.(p: || p22) +
V n2 log( 4/0)
(m1 I + 1222 12)
n1
2n1
n1 f + n2
(30)
The above directly implies, by taking squares and using Jensen's inequality and that f 2 0, that with probability 1- 5:
KL(p2 I)) S
111
2
9
In(4/6) 2n1
KL(p1 p2)
2 + 12/
2 2n((/))
(31)
12
71
Removal bound. Second, we lower bound the KL divergence of p1 from p. To do so, we use Jensen's 's inequality and (29 obtain that, with probability 1 - 6, we have
|1 p2) 2 = 1141 1 pel
S 2|p1
112 + 2/p 2211
S 21
11/2 +2
11 -J
2
0² g
(1
+
In(4/0),
|
142 2 2
n1
f + 112
71
2m1
20
122
2
4 (1(04))
+
f + n22
71
Rearranging terms, using that ʃ 2 0, and dividing by 4o2 along with (88
yields that with probability
1 - 5 we have
111 1u12
111
122
1
In(4/8)
111 1
112ll
)²
In(4/5)
(L 11
g
202
402
2
11.
n2
2n1
20
n2
1
(T
||
P2)
1
111
2
9
(1
S
+
In(4/0).
[/1 12
In(4/8)
2
2
112
71
201
20
11/
Now, using (28) we get
KL(Pi 11) > KL(pi || P2)
1
n1
9-1(1
g-
f
+
In(4/))
KL(P) || p²))²
In(4/0)
2
2
112
2n1
Conclusion.
With probability
- 6, have (a, -distributional unlearning with
/
m1 ) g
f
In(4/5)
KL[(p pa)) 2 In(4/5)
a
2 (L
|| P22
+
2
2
2n1
n2
111
2
(1
s In(4/6)
KL || p2))
2 +
2 2l((4/))
9
112
2n1
A.5 SIMPLIFIED SAMPLE COMPLEXITY FOR SELECTIVE REMOVAL
In this section, we can simplify the result of Theorem I on selective removal by simplifying cum- bersome terms. This leads to Corollary I0 which then yields to the sample complexity results in T
We first prove upper bound on the inverse CDF of a folded Normal for small quantiles.
Lemma 9. Let pr, P2 E RR, a > O, and x ~ Nin, o²). Define the random variable = |x mrab which follows a folded normal distribution whose cumulative distribution function (CDF) given by
1
122
||1
112
F(t) = Piz < {t = ①b
t
2 0,
(32)
24

---

Published as a conference paper at ICLR 2026
where & denotes the standard normal CDF. Then, for any p 0 such that F Fp) $ 1 u2) holds that:
F (p) S
P
Ps P2
where (px)) = _ exp 2/=
R, is the standard normal density.
Proof. Since F, defined in 32 is continuously differentiable and strictly increasing on [0, |an - w2l
(with F(O) = 0) and by the assumption F (p) < Im pal. the Mcan Value Theorem guarantees that there exists some & (0,F-1()) (p)] such that
F (1) (p)
F(O) + P()
(F (D)
Since F(0) and F is strictly increasing, one may directly write, via the Mean Value Theorem, that there exists & E [0, F (p)] with
F F(F = (F)
By definition of the inverse CDF, F (p)
=p; hence,
p= F" F (p).
remains lower-bound (5) for & E [0, || p2|]. We recall that for / O.
111 |22
1 μ42
F(t) +
Taking the derivative with respect to yields
U1
U2l
1
t - |1
12l
Ft(t)
+
40
1
u2l
1
1 + |1
1121
where we used that the standard normal density á is symmetric.
For [0, |u p2l], observe that |M1 - p2l S 0. Because the standard normal density is symmetric and nonincreasing on [0, co), we have
|1 u2l
M1
U2
2 40 |1 (
Also, the second term yo [+|m1-02] is nonnegative. Hence, for all E [0, /2l we have
1 10
111 p2l
F'(1)
0
In partieular, at / { obtain
1 FE) - 0
|1] 141-119 u22
Substituting this lower bound into the equation p (F) F (p) yields
|m| 1 u2l
p
Rearranging the inequality gives the desired upper bound:
F Fr)(p)
0
4p
This completes the proof.
25

---

Published as a conference paper at ICLR 2026
We now ready prove the corollary below. Note that retaining dependences a, only in this corollary leads to the result of Table
Corollary 10.
Let P2 E P and ó E (0,1). Let I samples from pı removed according to our distance-based scoring rule random before MLE. Then in each case, with probability at least 1- 6, the resulting estimate satisfies (a, disttribbutio unlearning if:
1. Random removal: n2
12lm(4/8) and KL(pi p2) So, and mim (2,03
2KL(PI p2) -a 12KL( P2)
122 min { 6KT. P2)
8
2 mh - m2
12
2. Selective removal:
2 2m(4//) max
1 1 1
VEL a: VKL(PI p2) 4a). KL(P1
P2) 2 4a, and f 2 n
+
In(4/0)
2 2KL(p1 P22)
and
2n1
1/4 exp(-KL((g p2)),
22 n1 vnin
16T
[L[(1 p2) 4a )
1/4
12 11
112222
exp(- P2))
8x
Proof. We treat random and selective removal separately below.
Random Removal. Consider removing f samples using the random removal mechanism, before
maximum likelihood estimation. From Theorem 3 unlearning with:
with probability - 8, we achieve (a, ())
111 1
1
2
3ln(4/0)
1+
mh
(L p2)
(removal),
112
2nz
722
f11
f
KL(p1 P2) + 3lm(4/0)
(1+
8<3
(preservation).
122
n2
n2
Therefore, assuming that n2 2 min (5.a)
lm//)) and KL || p2) 8a, direct calculations show that it is
sufficient set:
2KL(p1 P2)
f2 n1 /2
(removal),
12KL P2)
f 2 n22 min ( 6KI(pp p2)
(preservation).
Selective Removal. For selective removal, Theorem shows that, with probability - 8. we achieve (ar, eo.-e)l-aanniing with:
1 KL(Pi P22
1
n21
9 9-1
f.
In(4/5)
KL(p) || p2))
In(4/8)
(removal),
2
2
112
n1
2n,
n2
f
2
f
In(4/8)
KL(Pi p2) )²
2lm(4/6)
8 5
(preservation).
712
711
2n1
n22
We can simplify these bounds using Lemma 9 Indeed, thanks to the latter and using the same notation and a simple change of variable, we have for all p, K. > 0 such that p < F(um pal)
g 1- (p: S oi d(v2k)
P
PV exp(x))
(33)
26

---

Published as a conference paper at ICLR 2026
SMS Spam Recall on (forgotten) deletion
SMS Spai F1 ham (kept) deletion
1,000
Pecall on spam (forgatten)
CSL COL
wede
(lest)
0.896
0.004
F3
0.000
2,988
40
60
50
100
20
60
80
100
% spam messages romaved
spom messages removed
(a) Recall on spam (pI, forgotten).
(h) Macro-F/ on ham (p2, kept).
Figure 5: SMS Spam. The likelihood-ratio score (LR-COS) pushes spam recall below 0.6 after deleting 70% of spam, whereas random deletion needs nearly 90% removal to reach the same point. Ham performance remains almost flat (<0.004 absolute change) until the final 100 % budget, af- firming the tight preservation guarantee. Error bars: #1 standard error over ten seeds.
Now,
we
plug
in
P
f
In(4/5)
2m1
Assuming f 2
11
D (2 2KL(P1 P2)) + +
In(4/8) 2n1
which directly implies that S F(uu - H2l) as
required, we then obtain
In(4/8) 2n1
In(4/0)) 2m1
+1
KL(p1 p2)) $ 5(1
n2 +
v 2T exp (KL(p1 || p2))
Plugging the above back in the first bounds due Theorem I
obtain:
1
n1 -
5 (1
f
In(4/0))
2n exp (2KL(p) P2)) In(4/6)
a 2 KL || [22)
+
2
2
112
n2
2n1
8 < 111 - f (1
f
In(4/6)
2 1m(44/)
+
2T exp (2KT(p1 P2)) +
n2
2m1
n22
Therefore, assuming that n2 2 2ln(4/5) max
a KL(Pp P2) 4o and KL(p1
p2) 2 4a, and recalling we had assumed f 2 22022/2K((2) p2)) + + V
In(4/6)
di-
2m
rect calculations show that is sufficient to set:
E
1/4
f2 n4 /2
|| P2))
(removal),
16T
KL(P)
P2)
4a
1/4
2 ni V2i11
exp(-KL(p) P2))
(preservation).
8T
B EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
B. SMS SPAM: A CONTENT-MODERATTUE UNLEARNING TASK
We revisit the UCI SMS Spam Collection Almeida et al. 2011), treating the spam class (p1) as information forget and the ham class (p2) information to preserve. Messages vectorised with TF-IDF features. Deletion budgets again span 5% to 100% of the spam slice in 5 5-point increments. We compare the five scoring rules as before (COS-MU2, I.-COS, KNN-RATIO, FFIDE-NORM,
27

---

Published as a conference paper at ICLR 2026
Removal Divergence (a)
Preservation Divergence
0.225
Ukelhocd-rsto
Ukeihood-rato
Dedwnce
Ditwnce
0.200
retio
0.030
L2-narm
L2-narm
0.175
Random
0.025
Rancom
0.150
0.020
0.125
0.015
0.100
0.010
0.075
0.005
0.050
0.000
0.025
0.0
0.2
0.6 Fraction removed
0.4
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Fraction of Pr removed
Figure 6: Synthetic Gaussians. Comparison of all strategies considered in the real-world datasets, using the low-divergence scenario of synthetic Gaussians (left plot, Fig. 2 Likelihood-ratio sur- passes the distance- based strategy for lower deletion budgets. However, for larger budgets, it sacri- fices utility for excessive removal. This is likely because it deletes samples representative of pl but close to p2 since pl and p2 are similar here.
rANdoM) and average results over ten random seeds. Metrics reported are recall on pr and macro- F/ on P2-
Findings. We report our main findings on our SMS Spam task in Figure We observe that spam re- call decays gradually until 75-80% deletion, after which all methods converge to zero as P1 vanishes. LR-COS consistently dominates: reaches recall of 0.60 at the 70% deletion budget, whereas ran- dom deletion does not cross that threshold until 90% deletion. Throughout, ham macro-Fi increases slightly (see Fig. Fig. an artefact of plass-imbllance ceeiaancccrrmmvinngggeeg spam reduces false positives in the ham siie-yyt the difference across methods never exceeds 0.002. These results strengthen the ev- idence that selective deletion offers a 1.5x sample-efficiency gain over random removal while preserving downstream utility almost perfectly.
Remark 11 (Sample vs. Computational Efficiency in Unlearning). The computational cost of sample-level unlearning typically scales with the size of the forget set. For instance, influence- function- based approaches. such as the one proposed by Guo et al.) (2020), require computing gra- dients and Hessian-vector products for forget samples to approximate a second-ore -ordrr update. Other methods, like SalUn (Fan et al.) 2024), identify and modify salient model parameters by backprop- agating through the network for each forget sample. Reducing the size of the forget set implies less g gradient computations and hence time savings. This forget size scaling observation also holds for the large class certified unlearning methods based on noise addition (Chourasia & Shah 2023 Allouah et al. 2025
Waerebeke et al. 2025
B.2 EXPERIMENTAL DETAILS
B.2.1 HEURISTIC DELETION STRATEGIES
Across all datasets, we evaluate five scoring strategies for ranking samples in the forget distribution P1 for removal. These scores approximate statistical dissimilarity from the retained distribution P2 and correspond to different operational interpretations of divergence:
LR-COS / LR-MAHA fikelihooddratio inspired): A proxy for the log- likeliholdoo ratio of under Pa versus P1:
s s(x) d(x,, d(xr, (41)
where dl denotes cosine distance in TF-IDF space (text) Mahalanobis distance in CNN feature space (images). Points are scored high when they are far from Pa and close to P1-
28

---

Published as a conference paper at ICLR 2026
COS-MU2 / MAHA-MU2 (dissimilarity p2): Measures the distance from each x E P1 to the empirical mean of p2:
(x) d2)
This approximates the contribution of each point the KL divergence KL(p2ll)) when p is modeled as a Gaussian.
KNN-RATIO (local density ratio): Estimates the ratio k-NN densities:
pi (x)
s(x)
where (()))) = exp(-IIx-NNe (1) (a/2) is local Gaussian kernel density using k = 10
nearest neighbors. This captures how typical z is under p1 versus p2-
TFIDE-NORM/ / 1.2-NORM: Uses the & norm of the raw input (TF-IDF or real-valued) as a proxy for informativeness or deviation from the origin:
s |||||
CORESET (eentroid-basede Selects samples closest to the centroid of the forget set P1:
(x) = | 11ll2,
where μu is the empirical mean of pt. This strategy prioritizes representative samples that are central the forget distribution, potentially capturing the most characteristic patterns.
K- CENTER (k-center greedy): Greedy selection to maximize minimum distance coverage the forget set: set:
s(x)
max || 22|12. YES
where S is the set of already selected points. This strategy iteratively selects points that maximize the minimum distance to previously selected points, ensuring diverse coverage of the forget distribution.
RANDOM: Samples points uniformly at random from P1 as a bascline.
The first two sets of heuristics are direct extensions of our Gaussian selective removal method. When reporting results under "Selective removal" in tables, report the best-performing heuristic among these.
Remark 12 (Computational complexity of selection). The selection methods evaluated present a spectrum of computational complexities, which is key practical consideration for their use. At the most efficient end, methods like Random Removal, L2-Norm scoring, and the centroid-based Coreset are computationally inexpensive. Their complexity scales roughly linearly with the number of forget samples (n1) and feature dimensions (d), making their cost approximately O(nyd) plus sorting time. Our primary selective algorithms, based on distance to the retained set's mean, are moderately more complex. The Cosine distance variant remains efficient at O([n1 + n2)d), but the Mahalanohis distance version more demanding. need compute an inverse covariance matrix introduces a term that scales with the cube of the dimensions (O(d)), making it potentially prohibitive for high-dimensional data.
On the other hand, some heuristics are computationally intensive. The KNN-RATIO method is par- ticularly costly because it requires performing a k-nearest neighbor search for every sample in the forget set, which scales poorly with large datusets. Similarly, the iterafive nature of the K-CENTER greedy algorithm makes much slower than single-pass scoring approaches. This highlights a fundamental trade-off: while more complex methods like KNN-RATIO aim to capture muanced dis- tributional information, their computational overhead might be impractical. Simpler, faster methods like calculating the distance the retained mean often provide strong, practical balance between the effectiveness of the selection and its computational feasibility.
B.2.2 TABLE SAMPLE-LEVEL. UNLFARNING METHODS
We evaluate five sample-level unlearning strategies that represent different approaches to machine unlearning:
29

---

Published as a conference paper at ICLR 2026
RETRAINING (oracle baseline):
-Description:
Complete retraining from scratch on the retained data only. It trains new model from random initialization using only samples from p2- It provides the theoretical upper bound for sample-level unlearning performance, representing the gold standard but with highest computational cost.
Hyperparameters: Adam optimizer, learning rate 1 10-3, 10 epochs, batch size 128.
FINE-TUNING (naive baseline):
Descrripiion Continues training the pre-trained model retained data only. We initialize with pre-trained weights, then train for additional epochs on non-removed samples.
Hyperparameters: Adam optimizer, learning rate x 10 10-4, 4, epochs, batch size 128.
SALUN (saliency-based unlearning (Fan et al. 2024
Description:
This method resets parameters with highest saliency for forget samples, then finetunes on retained data: (I) Compute saliency scores for forget samples, (2) Reset top-k% most salient parameters initial values, (3) Finetune retained data. It leverages parameter importance to selectively reset the most forget-relevant param- eters while preserving general knowledge.
Hyperparameters: Adam optimizer, learning rate 5 x 10-4, 4, epochs, batch size 128, 1opk_percent=0.22
NEGGRAD+ (stochastic gradient descent ascent (Kurmanji al. 2024
Description:
This method simultaneously maximizes loss forget samples while minimizing loss on retained samples with loss 3 retain (1 - 3) x forget.loss.
This is essentially SGDA to balance retention of p2 knowledge against forgetting of Pi samples through opposing gradient directions.
Hyperparameters:: SGD optimizer, learning rate 1 x 10-3, momentum 0.99, weight decay 0.1, 3 epochs, 3 0.9, batch size 128.
INFLUENCE FUNC. (influence function-based approximation):
Description:
Approximates the effect of removing forget samples using influence functions, then applies parameter updates without retraining: (1) Compute influence scores for forget samples using Hessian-vector products, (2) Apply parameter updates based on influence estimates. This is computationally expensive for larger models, so we only use for the Gaussian experiment.
Hyperparameters: Adam optimizer, learning rate 1 x 10 10-4, epochs, batch size 128, damping factor 0.01.
B.2.3 SYNTHETIC GAUSSIANS
We draw mı = 122 1,000 samples from Pı = -N(0,) and p2 = - 1) for E (0.5, 2.5, 5.0), with seeds. After computing scores using each strategy, we remove the top-/ fraction of p1 points, fit Gaussian [V 1) to the retained data, and compute:
a == KT. 1p)),
= KT
These metrics match the forward-KI. objectives of removal and preservation. No predictive model is trained; results reflect pure distributional divergence. For completeness, in Figure O we plot comparison all strategies considered in the real-world datasets, using the low-divergence scenario of synthetic Gaussians (left plot, Fig. 2). Likelihood-ratio surpasses the distance-based strategy for lower deletion budgets. However, for larger budgets, it sacrifices utility for excessive removal. This is likely because it deletes samples representative of p1 but close P2 since Pı and p2 similar here. This indicates that no removal strategy strictly dominates all others across all divergence (between pı and P2) scenarios.
30

---

Published as a conference paper at ICLR 2026
B.2.4 JIGSAW TOXIC COMMENTS
use the Jigsaw Toxic Comment Classification dataset, with 140K examples filtered to length 5-200 tokens. We define Pi as all training comments containing any of the keywords: "f*ck", "s"it" "d"mn", "b"tch", "a"s", and P2 as the remaining comments. For each of 5 random seeds, we:
1. Stratified-split Pt, P2 into 70/30 train/val.
2. Compute TF-IDF embeddings (40K max features, 1-2 grams, sublinear TE, min df=5).
3. Score and remove f of p1 training points using each heuristic.
4. Downsample P2 to 5x the remaining P1 size.
5. Train an fz-regularized logistic regression on the edited data.
6. Evaluate Recall@p; and F/ @ on the validation sets.
B.2.5 SMS SPAM COLLECTION
We use the UCI SMS Spam dataset (5574 examples, 13.4% spam). We apply:
TF-IDF vectorization (20K features, 1-2 grams, stopword removal).
2. Scoring of spam (p1) messages using each heuristic.
3. Removal of top-f fraction of spam for each strategy.
4. Retrain a logistic regression classifier.
5. Evaluate Recall @ spam and F1 @aam on a held-out 20% test split.
We run 10 seeds and report mean + standard error.
B.2.6 CIFAR-10 CLASS REMOVAL
We treat the "cat" class as Pı and the other classes as P2- We use the standard CIFAR-10 split (50K train, 10K test), and proceed as follows:
1. Train a 3-block CNN CCony-BN-ReLU x2 MaxPool, widths 32-64-128, global avg pool
+ linear head) for 10 epochs on the full training set.
2. Extract features for all training images using the penultimate layer.
3. Compute Mahalanobis distance scores for each cat image (p1) using:
maaha (x) = V( (x- T - 14)
where and Σ are estimated from P2-
4. Delete the fop-f fraction of cat images under each scoring method.
5. Retrain the same CNN architecture on the edited training set.
6. Evaluate:
Accuracy Accuracy
on the test set. Results are averaged over 30 random seeds.
B.2.7 COMPUTING ENVIRONMENT
All experiments were run on a HPE DL380 Gen equipped with two Intel(R) Xeon(R) Platinum 8358P CPUs running at 2.60GHz, 128 GB of RAM, 740 GB SSD, and two NVIDIA A10 GPUs. Training for vision experiments was implemented in PyTorch, while text-based experiments used Scikit-learn, All experiments were conducted using single GPU.
31

---

Published as a conference paper at ICLR 2026
B.3 ABLATION: SENSITIVITY TO FEATURE REPRESENTATIONS
To assess how sensitive our selective deletion procedure is to the choice of feature representation. conducted ablation study on CIFAR-10 where we varied only the feature extractor and kept the selection algorithm and training setup fixed. We compare five representations: the default CNN features used in the main paper. ResNet-18 features (both pretrained and trained from scratch), and raw pixel features. For each setting, we measure forget-sct accuracy at a deletion budget of 60% (lower better forgetting). The results are shown in T
Two main observations emerge. First, across standard learned representations (CNN, ResNet- 18 scratch, R8 pretrained), the forgetting performance is very similar, suggesting that the method is robust once the feature extractor provides reasonably expressive embedding space. Sec- ond, using raw pixels significantly weakens forgetting, confirming that feature quality matters, but not in way that makes the method brittle to the specific backbone.
Feature Extractor
Forget Set Accuracy (%)
Random (baseline)
40.5 + 2.5
CNN (default)
21.6 + 1.9
ResNet-18 (trained from scratch)
20.4 = 2.1
ResNet-18 (pretrained)
27.3 = 1.8
Raw pixels
31.8 + 2.0
Table 6: Forget set accuracy (mean + s.e.m.) at 60% deletion for different feature extractors on CIFAR-10. Lower better forgetting.
B.4 ADDITIONAL CORESET BASELINES ON CIFAR-11 10
To further investigate the behavior of retain-agnostic coreset methods in our unlearning setting, compared our selective removal strategy against two strong data subset selection baselines, CRAIG, GradMatch, and CCS, on CIFAR-10. All methods operate at fixed deletion budget of 60% from the forget class, and report the resulting forget-set accuracy (lower is better forgetting). While CRAIG and GradMatch slightly, though not significantly, improve over random deletion, they still operate purely the forget distribution and cannot exploit contrast with the retain distribution. As shown in Table our distributional selection substantially outperforms these baselines.
Selection Method
Forget Set Accuracy (%)
Random
39.2 = 1.9
CRAIG (Mirzasoleiman et al. 2020
36.3 2.7
GradMatch (Killamsetty et al. 2021
35.5 = 4.2
CCS (Zheng al. 2023)
40.9 4.1
Selective (ours)
24.5 = 1.4
Table Forget accuracy (mean + s.e.m.) on CIFAR-I0 60% deletion budget from the forget class. Lower values indicate stronger unlearning. Our selective removal method, which leverages the retain distribution, outperforms all strong coreset baselines (CRAIG, GradMatch, CCS) and random deletion.
32


Reviews:
[{"review_id": "0eKwncw34h", "reviewer": "Reviewer_UHoi", "summary": "This paper tackles the problem of machine unlearning, whcih traditionally focuses on removing entire domains or subpopulations of data as opposed to individual data points. The core of this paper is that a domain's statistical influence is often concentrated in small subsets of its samples. Thus, the authors propose distributional unlearning: a framework to select a small data subset by maximizing the statistical distance from the forget distribution while minimizing the distance to the retain distribution by using KL divergence. Experiments are conducted on synthetic, text, and image datasets.", "questions": "I would appreciate if the authors addressed the few concerns raised in weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper does a good job of defining and motivating the proposed \"distribution unlearning\" framework. \n- The framework is built with a strong theoretical foundation:\n  - Using KL divergence to define forget and retain objectives is simple yet effective.\n  - The proposed selective removal algorithm is quite intuitive and is derived directly from the theoretical analysis. The authors also analyze theoretically how the selective removal algorithm is a strategy to maximizing the KL divergnce of the forget set while minimizing the KL divergence of the retain set. \n- Experimental evaluations, while not conducted on large-scale data, is well-structured and quite comprehensive.", "weaknesses": "- The framework is built on the assumption that the unwanted and retained data sets are already known. While the authors assert that this could be done via some upstream process (e.g., keyword filtering), there could be other scenarios where such techniques do not work. \n- I'm not entirely sure if the core motivation, that a domain's influence is concentrated in a small subset holds in the experimental results. For example, in CIFAR10 the removal is only observed after 50% deletion and in Jigsaw it is only observed after 80% deletion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3QUVxRM9ml", "reviewer": "Reviewer_CfVa", "summary": "The paper introduces the concept of distributional unlearning, a framework for studying the statistical properties of data removal in training datasets. The authors claim that may be convenitent to reduce not all the data of the forget set but a subset of them, the question they are trying to answer is what is the minimal subset of data points to remove (the forget set) in order to make the resulting data distribution far from the distribution of the forget set, while remaining close to the distribution of the retain set. \nTo formalize this idea, the authors define the notion of $(\\alpha, \\varepsilon)$- distributional unlearning for a distribution $p$ with respect to two other distributions $p_1$ and $p_2$. A distribution $p$ satisfies $(\\alpha, \\varepsilon)$-distributional unlearning if it is at least $\\alpha$-far from $p_1$ and at most $\\varepsilon$-close to $p_2$, where \"far\" and \"close\" are measured in terms of the KL divergence between $p_1 or $p_2 and $p$. \nMost of the theoretical analysis in the paper focuses on Gaussian distributions, where the authors characterize the Pareto frontier of achievable $(\\alpha, \\varepsilon)$ values. They also prove a finite-sample guarantee for achieving $(\\alpha, \\varepsilon)$ distributional unlearning using two data deletion mechanisms: random removal, where a fixed number of samples are deleted uniformly at random; and relective removal, where data points are assigned scores proportional to their distance from the mean of the retain distribution, and high-scoring points are removed.\nThe authors compare the performance of these two algorithms on several datasets and also discuss the synergy of their approach with other unlearning methods.", "questions": "- In practical machine learning settings, can the Kullback–Leibler (KL) divergence between two data distributions $p_1$ and $p_2$  remain small even when the samples removed from $p_1$  are rare but highly influential, such that the resulting model still retains significant information about those removed samples?\n I'm thinking for instance of removing a few minority-class examples can shift the decision boundary a lot or in linear regression about a few points can dominate parameter estimates, but contribute little to the overall KL.\n- How is the synergy with other unlearning methods implemented in practice? For example, are the “selective samples” identified according to the procedure described in Section B.2.6 (so with the score only depending on their class and their embedding) and then used as the input (forget set) for the subsequent unlearning algorithm? (instead of performing retraining) \n- See also weaknesses", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written, with clear exposition and excellent presentation. The theoretical claims are sound. \n- The introduction of distributional machine unlearning represents a novel and interesting contribution, offering a perspective on how data deletion can be studied from a statistical standpoint.\n- The inclusion of coreset-based methods as an additional baseline is appropriate and well-motivated.", "weaknesses": "- The theoretical results are derived for data following two gaussian distributions (strong assumption) for two simple removal strategies. While these allow for closed-form analysis, they are not particularly practical for real-world unlearning. \n- The use of Kullback–Leibler (KL) divergence between data distributions as the central measure does not directly capture the notion of “forgetting” at the model level. KL divergence quantifies average differences between data distributions, not how much information a trained model retains about specific samples.\nTherefore, KL-based analysis provides a bound on distributional robustness or generalization under deletion, rather than a guarantee of behavioral or algorithmic unlearning. In other words, a model may still encode information about deleted data even if the KL divergence between underlying distributions is small.\n- It would be interesting to see \n- The paper is interesting from the thoeretical point of view and for the introduction of this problem. But is not clear how useful can be in practice since typically retraining from scratch is something one may want to avoid. \n- For the removal for instance of the class \"cat\" it is not shown how effective is this removal on samples that are \n\nMinor: \n- The setting considered in this paper is conceptually quite different from standard machine unlearning. The authors themselves acknowledge this distinction. Rather than proposing an algorithmic method to efficiently remove the influence of specific samples from a trained model, the work studies what happens statistically when data are deleted and the model is retrained from scratch.\nConsequently, it is unclear whether the term unlearning is fully appropriate for this setting. The framework primarily measures how retraining after deletion affects model parameters and distributions, rather than addressing unlearning as a computational or algorithmic problem.\n- The abstract highlights the derivation of the exact removal–preservation Pareto frontier for exponential families as a key contribution. However, this result appears only in the appendix and is not discussed or emphasized in the main text. Given its limited exposition and lack of integration into the core narrative, featuring it prominently in the abstract may be misleading or disproportionate relative to its role in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9OTDGRXoR2", "reviewer": "Reviewer_KqBQ", "summary": "This paper introduces \"distributional unlearning,\" a novel information-theoretic framework to address the problem of removing entire domains or subpopulations of data from a training set. The authors argue that full domain removal is computationally prohibitive, while random partial removal is statistically ineffective. Their key insight is that a domain's statistical influence is often concentrated in a small subset of its data. The proposed framework formalizes this by modeling the \"forget\" and \"retain\" data as two distinct probability distributions, p1 and p2. The goal is to find a data subset that maximally increases the KL divergence from p1 (removal) while minimally increasing the KL divergence from p2 (preservation). The paper provides strong theoretical results, deriving the removal-preservation Pareto frontier for exponential families and proving downstream log-loss guarantees for models trained on the resulting data. It proposes a simple and efficient distance-based algorithm—removing p1 samples that are furthest from the mean of p2—and proves it is quadratically more sample-efficient than random removal in low-divergence regimes. Experiments on synthetic, text, and image data validate the theory, showing that this selective approach can achieve strong unlearning effects with 15-82% fewer data deletions than full removal.", "questions": "How sensitive are the results to the choice of the feature space? For the CIFAR-10 experiment, if you were to use features from a different model (e.g., a ViT instead of a CNN) or a model trained on a different dataset, would you expect the set of \"most influential\" cat images to remain largely the same?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper's primary strength is its elegant formalization of domain unlearning as a distributional problem. By defining the objectives using KL divergence and characterizing the optimal trade-off via a Pareto frontier, the authors provide a rigorous, data-centric foundation for a problem that is often treated with ad-hoc heuristics. The connection established in Proposition 2 between the data-level KL objectives and the downstream model's expected log-loss is particularly powerful, as it provides a clear theoretical justification for why this data selection approach should work.", "weaknesses": "1. Novelty:\nThe core algorithm—removing points from one set based on their distance to the mean of another—is mechanically very simple. The novelty does not lie in a complex algorithmic contribution but rather in the application of this simple heuristic to the unlearning problem and, most importantly, the new theoretical framework that justifies it. While the framework is novel, the method itself could be seen as an application of standard outlier-detection or data-cleaning principles.\n2. Experiments:\n- Dependence on Feature Space: The effectiveness of the distance-based removal heuristics (e.g., MAHA-MU2, LR-COS) is entirely contingent on the quality of the embedding space. The paper uses standard features (e.g., from a pre-trained CNN), but provides no analysis of how the performance would change with a different, perhaps less-optimal, feature representation. If the feature space does not effectively separate the \"statistically influential\" samples, the distance metric may fail to identify them.\n- Limited Baselines: The paper effectively demonstrates superiority over random removal and a simple coreset baseline. However, the coreset baseline (removing points closest to the p1 centroid) is shown to be ill-suited for this dual-distribution problem. A comparison with more sophisticated data selection methods, even if from different domains (e.g., active learning), could have provided a broader context for the performance gains.\n- Theory-Practice Gap: The strong, closed-form sample complexity results are derived under the assumption of Gaussian distributions. While the authors acknowledge this and show that the qualitative insights generalize, the quantitative gap between the predicted 82% savings on synthetic data and the 15-50% savings on real-world data is substantial. This highlights that the complexity of real data distributions significantly tempers the theoretical gains.\n- Practical Usage: the authors could consider more general/modern settings like LLM SFT.\n3. Additional Things:\n- The Oracle of p1 and p2: The entire framework operates on the strong assumption that the forget (p1) and retain (p2) sets are already known and perfectly separated. In practice, identifying every sample belonging to an unwanted domain (e.g., \"toxic language\") is an extremely challenging and often ambiguous task in itself. The paper solves the important second step of this process (which subset to remove) but does not address the first, which is a major practical caveat.\n- Simplicity of \"Statistical Influence\": The method operationalizes \"statistical influence\" as distance from the retained data's mean. This is effective for unimodal, Gaussian-like distributions but may be less effective for multi-modal or complex distributions, where influence might be related to local density or boundary effects rather than just distance to a single central point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fiqXOENGSE", "reviewer": "Reviewer_w9hG", "summary": "This paper presents an intuitive method to select a subset of the forget data to remove/unlearn to balance model utility and unlearning performance.", "questions": "Q1 See question in weaknesses.\n\nQ2 How should your method be used to pick the correct forget set (size of f samples) in practice when pairing it with an unlearning method (as in Table 5.)?\n\nQ3 (Out of interest, feel free to ignore) Do you envision a version of your method that works in a setting where only the forget set is available?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method is intuitive, novel, and well presented. The claims are theoretically and empirically backed up.\n\nWhat I find especially relevant as a contribution is that this method can be used together with existing unlearning methods, improving them via a better composition of retain and forget sets.", "weaknesses": "The computational overhead for large datasets (e.g. web-scale data) is problematic. As this will require approximations to have a feasible retain set size, the performance of the method when the retain set is only available in an approximate manner (e.g. representative samples of an LLM training set) would be of interest as the results in table 2 already show a significant performance difference from Gaussian -> more realistic datasets (SMS, etc.).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)