Machine Unlearning under Overparameterization
Authors: Jacob L. Block
Aryan Mokhtari
Sanjay Shakkottai
Venue: NeurIPS 2025 poster ()
Keywords: Machine Unlearning Theory
Overparameterization
Primary area: theory

Abstract: Machine unlearning algorithms aim to remove the influence of specific training samples, ideally recovering the model that would have resulted from training on the remaining data alone. We study unlearning in the overparameterized setting, where many models interpolate the data, and defining the solution as any loss minimizer over the retained set—as in prior work in the underparameterized setting—is inadequate, since the original model may already interpolate the retained data and satisfy this condition. In this regime, loss gradients vanish, rendering prior methods based on gradient perturbations ineffective, motivating both new unlearning definitions and algorithms. For this setting, we define the unlearning solution as the minimum-complexity interpolator over the retained data and propose a new algorithmic framework that only requires access to model gradients on the retained set at the original solution. We minimize a regularized objective over perturbations constrained to be orthogonal to these model gradients, a first-order relaxation of the interpolation condition. For different model classes, we provide exact and approximate unlearning guarantees and demonstrate that an implementation of our framework outperforms existing baselines across various unlearning experiments.

Machine Unlearning under Overparameterization
Jacob L. Block
Aryan Mokhtari
UT Austin
UT Austin Google Research
jblock@utexas.ed
mokhtari @aurtin www.ssttiitttttt.tet.e.
utwxas.e...... edu
Sanjay Shakkottai
UT Austin
sanjay shakkottai@uteea. edu
Abstract
Machine unlearning algorithms aim to remove the influence of specific training samples, ideally recovering the model that would have resulted from training on the remaining data alone. We study unlearning in the overparameterized setting, where many models interpolate the data, and defining the solution as any loss mini- mizer over the retained set-as in prior work in the underparameterizee setting is inadequate, since the original model may already interpolate the retained data and satisfy this condition. In this regime, loss gradients vanish, rendering prior meth- ods based on gradient perturbations ineffective, motivating both new unlearning definitions and algorithms. For this setting, define the unlearning solution the mininum-complexity interpolator over the retained data and propose a new algorithmic framework that only requires access to model gradients the retained set at the original solution. We minimize a regularized objective over perturbations constrained be orthogonal these model gradients, first-order relaxation of the interpolation condition. For different model classes, we provide exact and approximate unlearning guarantees and demonstrate that an implementation of our framework outperforms existing baselines across various unlearning experiments.
Introduction
The ability remove the influence of specific samples from trained model essential comply with privacy regulations such as the GDPR and CCPA [ and to correct mislabeling or bias that may compromise model integrity [3]. Machine unlearning
refers algorithms that address these challenges by modifying model trained on a dataset D to forget a subset of samples, termed the forget set f and produce model that acts if had been trained only on the remaining data, denoted the retain set D, D \ Dy. The ideal, yet costly, "gold standard" unlearning solution is to retrain the model from scratch on D,,, which perfectly achieves the unlearning objective but is often infeasible due to high computational cost and potentially limited access to the original training data, The goal of an unlearning method to efficiently approximate this outcome using the knowledge of the original training procedure, the samples to be forgotten, and potentially restricted side-information related to the retained data, aiming to recover model that could result from training on D, alone.
In the underparameterized regime, where the model class cannot fit all training data, the training loss admits unique minimizer. Thus, the natural definition of exact unlearning is the unique minimizer to the loss on D,. When the loss is further strongly convex, prior work developed efficient unlearning approximations using influence functions, which estimate the effect of removing a sample via single gradient ascent step over the loss on D, preconditioned by the inverse loss Hessian on D [5-7].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In contrast, this paper focuses on the overparamettrized regime, where the model class contains many interpolating solutions. Crucially, the training loss no longer admits unique minimizer, and defining the unlearning solution by loss optimality alone no longer suffices: the original model 0" minimizes the loss over both DD and D,, and 0* clearly encodes information about Dy the data to be removed. Moreover, interpolation causes the loss gradients to vanish, rendering loss- -i--grrddent-aseee methods such as influence functions ineffective (Theorem []. This fundamental shift necessitates both a new definition of unlearning and new algorithmic tools tailored to the overparameterized setting.
We begin by formalizing unlearning in the overparameterized setting. Specifically, we define the exact unlearning solution as the model which minimizes model complexity measure R, subject to minimizing the loss over D,; see (2). For natural choices of R. such as the parameter norm, this definition ensures that the unlearned model reveals no information about the forgotten data and maintains strong generalization using only the retain set. Given this definition of unlearning, we propose a new algorithmic framework to compute the solution. We focus on settings where the loss minimized by any interpolating model, so the constraint reduces to requiring interpolation over D, To solve the resulting problem of minimizing I subject to interpolation. we relax the constraint via a first-order Taylor expansion around 0* and reparameterize as 0 + A, where A is the drift, Since 0" already interpolates D,, the linearized constraint requires A to be orthogonal to model gradients at e on D,.. This simplifies the problem, requiring only gradient access, and avoids the complex interpolation constraint. To mitigate error from this relaxation, we add regularizer R( A) to control the size and direction of the drift. The final objective minimizes Ri + A) + R(( under the relaxed orthogonal gradient constraint, yielding updated parameters 0* A.
Theoretical Contributions. We prove for linear models and linear networks, there exists a regularizer Å such that minimizing R(0"+ + A + R() over our constraint relaxation gives the exact unlearning solution when R is the f--norm of either the effective regressor or the full parameter vector. For two-layer perceptrons with nonlinear activations, where R measures network width, we prove that the right choice of ft yields a solution to our relaxed problem which interpolates D, and matches the best known upper bound on the number of neurons required fit any dataset of given size.
Algorithmic Contributions. We devise an iterative algorithm MinNorm-OG that accesses a subset of Dr. aligning with data access assumptions in prior work X TO]. where OG refers to orthogonal gradient. Min alternates between two steps: solving for the minimizer of R(0 + A) over A satisfying the orthogonal gradient constraint, and descending on the loss over Dr (Algo- rithm 1). We take both It and it as scaled squared E2 norms, which apply broadly to parameterized models and yield closed-form solution to the relaxed problem. We show strong performance of our method across three experimental settings: Data Poisoning. Multi-Claa Label Erasure, and Representation Collapse, using natural and interpretable unlearning metrics to compare our method against existing baselines. Notably, the Multi- Calti-Class Label Erasure and Representation Collapse image-domain experiments introduce novel unlearning settings for effective evaluation.
- + R A
Related work. Unlearning theory traces back to influence functions 11 which estimate the effect of down-weighting sample on a learned function (5). Extensions explored approximate unlearning via differential privacy 6 7 [6] analyzed the deletion capacity an unlearning method can tolerate while maintaining generalization. [12] [3) proposed joint learnin--ullearinng schemes that store information about data subsets during training for later unlearning. Several works proposed iterative unlearning methods for large-scale models, combining loss ascent, descent, and noise injection [4 All these methods rely on loss gradient perturbations, which we show yield vacuous updates under overparameterizztion (Theorem []. In practice, they also struggle to unlearn effectively (9. as loss ascent encourages misfitting DD5 rather than forgetting it. Our framework enforces parameter perturbations to be orthogonal to the gradient over D, to preserve loss optimality, an idea also used in continual learning contexts [19]. Recent unlearning methods use similar projections which mix loss ascent and descent, but their reliance on these objectives inherits prior limitations 220 21).
2 Unlearning in Overparameterizee Settings
We introduce notation (additional standard definitions in Appendix A for our unlearning setting, highlighting the unique challenges of the overparameterized regime. We explain why loss optimality alone no longer suffices to define the ground truth unlearning solution and demonstrate why loss- gradient-basel methods, originally designed for the underparameterizzed case, prove ineffective.
2

---

To formalize the unlearning problem, we now define the problem setting and notation, covering both the underparameterized and overparameterized regimes. We define the full training dataset D = {<z y1) ). with sample inputs æ; E IRm and outputs yi E TIe drawn from the data domain 2 = _ x IR'. Initially, training is performed on the full dataset 'D over the model class (f(0.-) l E R parameterized by 0 E R where f Rd+m + IR' takes parameter vector E Rd and an input æ E RT and maps them to a prediction s(0, x) in the output space R'. We define the training procedure, also denoted the learning algorithm, A 22 - RR which takes in dataset and returns the parameter vector 0 corresponding to the trained model. We make the minimal assumption that A is faithful to known loss function J, meaning A(D) 0 is only guaranteed to be a minimizer of J over D, where J is defined as the average of the sample-wise loss L:
A(D) = 0" E argmin J D argginn
1
Σ (m.
((0;
(I)
0
For our theoretical discussion, we consider sample-wise loss functions L. (0; =0; æ. y) which are mini- mized when f(0, x) y. meaning that sample interpolation implies loss minimization. For example. this is the case for 4p norm regression or classification with 0-1 loss.
With this training setup, we begin the unlearning process given request for the model to forget subset of the training data D, S 'D. We then apply an unlearning algorithm M A(D), Dy) which is given the learning algorithm A, side information I, (e.g.. subset of the samples, the Hessian of the training loss over the retained data), initial solution A(D), and forget set Dy. and which attempts recover the desired unlearning solution, denoted by 0r, where the subscript r indicates that Or is the parameter vector that would result from training only on the retain set D, = D \ Dj To formally define Oz. must distinguish between underparameterizze and overparameterized regimes, as the former's 's definition requires refinement to remain meaningful in the latter.
In the anderparameterized setting, the loss function over both the full data set J (0; D) as well as the retain set J (0: DD) admits a unique minimizer. To ensure that the unlcarning solution remains consistent with the training loss, the only valid choice is to define 0;; as the unique minimizer of [e ; D.). However, in the overparameterize setting this uniqueness property fails to hold, as both J [ and J (0; DD,) may admit multiple minimizers. In order to sidestep the non-uniqueness issue, one may be tempted to define any minimizer of I (0 Dr) as a valid unlearning solution, as presumably any minimizer to J (0: D,) could be found from just training on D, alone. However, following this rationale allows for seemingly valid unlearning solutions to leak information relating to Dy. Specifically. the original solution 0" that interpolates all of D is itself a valid minimizer of the retain set loss J (0; D,). but 0 can reflect training dynamics influenced by Dy, revealing information that cannot be inferred from D, alone (see Appendix C for a conerete illustration).
2.1 Defining Unlearning Beyond Loss Optimality
As discussed above, the overparameterized setting requires more fine-grained definition of the desired unlearning solution-on one that goes beyond loss optimality. We define the unlearning solution in the overparameterized case to be the specific loss minimizer which minimizes an additional objective function R(O), expressed as the output of a training algorithm Ari
An( = 07 E argmin R(O), subject to
E argmin I (O):
This bilevel optimization problem searches for the model which minimizes the complexity measure R among all models which minimize the retain set loss. Indeed, when R admits a unique solution, this formulation overcomes the prior issues of non-uniqueness and the risk of revealing information from the forget set. While different choices of R can address these issues, we ultimately want R to promote desirable model properties. In our theoretical results, we focus on R as a regularization function that penalizes model complexity. This way, the solution 0; to 2 corresponds to the simplest model that interpolates D,- a particularly useful property in the overparameterized regime, where the simplest interpolating model is often associated with optimal generalization performance [22].
Then given the training algorithm Ag, side information about the retain set I,, minimizer to the original training loss A(D). and the forget set Dy, an unlearning algorithm M (A,,I,, A(D), attempts to recover (D,),, the least complex loss minimizer over D, as measured by R.
3

---

2.2 Loss Gradient Methods Deployed Under Overparameterization
For the characterization in (2) of the ground truth unlearning solution under overparameterization, we show that existing unlearning methods based on loss gradient perturbations fail to achieve meaningful unlearning updates. Prior theoretical works proposed sandient-ascent-stlll updates based on influence functions, a principled technique from robust statistics [3H7], while existing empirical unlearning methods perform combinations of loss ascent over y, loss descent over D,, and parameter noising [1 81. ineffective updates when deployed under overparameterization.
We characterize these methods loss- gradient unlearning, and show that they perform
Definition 1. Let 0* = AD).. We say an unlearning algorithm M performs loss mass-gradient unlearning for any positive semi-definite Pr: P3 E TRdddd and zero-mean random variable & E RRd,
M (A)),. D 0 P.VoJ (0*; + P.VoJ ; +
(3)
Although versions of loss loss-gradient unlearning have been theoretically motivated in the underparame- terized setting 77,7 we show they fail to unlearn in the overparameterized setting.
Theorem 1. Let f(0",.) interpolate D, so f(0', x)) = y for all (x, y) E D, and let Mia be any loss-gradient unlearning method. If the sample loss E (0, x. y) is minimized when f(0, x) y, then for all Dj C D, Mui simply noises 0" by some zero-mean random variable &.
MLG (A).....( = +
The recovered parameters 0 already minimize J (0": D,), so the loss gradients vanish and MLo merely adds noise to 0". This shows the core issue with loss gradient updates in overparameterized unlearning: the loss gradient is uninformative, as both 0 and 0, minimize the loss on D,..
3 Our Proposed Framework
We present a new framework to efficiently address the desired unlearning goal overparameterizeed settings without full retraining. A key assumption underlying method is the richness of the function class, allowing for perfect fitting of the retain set. This means there exist several mappings f(0,-) where f(0.x.) xx,) y, for every (x, y:) in the retain set. This lets replace the loss minimization in 2 with the hard constraint f0, x.) = yı leading to the following formulation:
0 E argmin R(O)
s.t. f(0, x;) = y: V( y1) e D,
(4)
This problem can be independently solved, but this would be the equivalent of retraining on the retain set. The main goal of our proposed framework is to solve the above problem efficiently by starting from the model 8" which fits each sample and leveraging the feasibility of this model for the above optimization problem. To do so, we simplify the problem and replace the constraints in 44) with their linear approximation around f* While the constraints f(A, x:)) = y: in (4) can be highly nonconvex and difficult to satisfy in general, demonstrate that using the proposed first-order approximation
f(0", xx)) + ff xx:) (0) =
vf T( 0*) = 0,
(5)
renders it tractable as it leads to a set of linear constraints with respect to 0. Note that in the above simplification used the fact that 0" perfectly fits the retain set, f(0", xx,) yr. Now if we apply this constraint relaxation the resulting optimization problem would be:
min R(O" A
S.L. VS w; T A 0
V(a,, y:) E D
(6)
where for notational convenience, we define the drift variable as A 0 0-. While this relaxation is sensible, it presents a clear limitation: approximating a general function with its linearization is only locally accurate and thus valid when the drift term A remains sufficiently small in some norm. To keep
the surrogate solution close to that of the original problem in { we add a regularization term R² () to the loss to control the drift. The resulting objective function is Ri + A := R(@ + A) R(A) Consequently, the optimization problem we propose solve instead of is given by
Â E argmin Ri + A)
s.t.
vf(0", xz,
((,,y)) E Dr
(7)
A

---

Indeed, by finding A the suggested unlearned model would be 0 A. Although 7 employs relaxed constraints, we will show that for various mapping functions f, there exists function R such that the solution to (7) either (i) solves the original unlearning problem (4) exactly, or (ii) yields model that both interpolates Dr, remaining feasible for ( and satisfies tight upper bound on the complexity measure R. A key advantage of the formulation in ( beyond simplifying the constraints, is its minimal information requirement: it only relies the gradient of f evaluated at the original trained model, i.., the side information Z, = o [oof(0". x) than prior work, which requires access to the inverse Hessian of the loss over D, [3H7], and makes our method substantially simpler than full retraining.
(a) This is significantly less restrictive
Theoretical Guarantees
This section provides theoretical guarantees for using our proposed relaxation 7 solve the exact unlearning problem 4 Going forward, we denote Ruclidean projection onto the set S as Ps (.) and define the penalty function ófa) which is +oo if condition a satisfied and 0 otherwise.
4.1 Linear Model
Given a linear model 0 with 0- w; = Yi for all (0;, ys) E D, we can easily solve the exact unlearning problem 44) for R(0)= ||||2.
Theorem 2. Lel A solve 7 for [ x) = 0 x and i((0) = ||0|| Then the recovered solution
- 0 + Ả solves the exact unlearning problem 44 for R(0) ||01|2
This result holds because, in the linear case, the surrogate and original constraints match exactly, and no approximation error is introduced. Thus, no additional regularizer (i.c., R(()) = 0) is needed.
4.2 L-Layer Linear Network
In this section, extend our analysis to more complex model: L-layer linear network. Let the prediction function be f(,, x) = c AL-1 ... Ajx, where the parameter vector is partitioned = [e; vA)(AI); :..;; vec (Ar.-)], with A, hexhh-- and e E Rh for = 1,.... The input dimension is For clarity, define the effective linear predictor w(0) = A Al-1c, so that f(0, x) = w(0) x. For this model class, study two natural choices of regularizers in 4 (i) R. as the norm of the prediction function as a linear map, and (ii) as the norm all model parameters.
ha. and we assume < to reflect the overparameterized regime.
4.2.1 Minimizing Predictor Norm
We first analyze when the R measures the fg-norm of the effective linear predictor: R(0) || ... ......AJ.... A. T y for all (z. y) E D. we aim to solve 4 for this choice of R. In this case the mapping f is non-linear with respect to 0. As result, the first-order approximation for the con- straints not tight, so solving the surrogate problem (7) does not necessarily give a solution for the problem in (4). However, we show that adding a suitable regularizer Rt to control model drift ensures the relaxed and original problems have the same solution. We first present intermediate result showing the existence of feasible perturbation Á that satisfies the relaxed linearized constraints and, when added to 0', yields an optimal solution to Q
||w(0)]l2- Given 0" [c* vec(Ai)
vec(Aii.1) such that
Lemma 1. Denote the retain set imput subspace by S, span(# (x. y) Dr) and partition the perturbation as À | vec( A.)
vec( Á A...))
the same manner as O. Set
A = || A; c0 A ... A.T,, (w(
(8)
and all other components of â to zero. Then Â orthogonal to the grudient of mapping f(0. evaluated at O 0* for each inpul x in the retain set and hence feasible for the relaxed problem (7)
Moreover, 6 A solves the exact unlearning problem (4) for R(0) [[((0]]
The above result shows that the perturbation direction defined in { leads to an optimal solution for once added to 0*, while satisfying the relaxed linear constraints of the surrogate problem. That
5

---

( which only differs in the constraints from would recover A. In fact, we can show that without adding a proper regularization term R to the loss, Á would not be a solution of the relaxed problem (see Appendix [...T). We next characterize the appropriate regularization R( A) needed to ensure that Á is the optimal solution to the surrogate problem in (
said, it does not imply that solving
Theorem 3. The solution to the relaxed unlearning problem with the following choice of R solves the exact unlearning problem (4) for R(O) = (0)ll22
R(0:0)) |w(0)
(0) ||2 ogetet)
òAA+AA11
4.2.2 Minimizing Parameter Norm
Next, we analyze when the unlearning solution is the loss minimizer with the smallest parameter norm, so R((0) = ||0||- In this case, we can construct an exact unlearning solution from the exact unlearning solution the previously analyzed case when R(0) = [|w(0)]l2-
Theorem 4. Let 0; solve 4 for R(O) = [[((0]l2, so w(θ;) is the min fz-norm linear predictor
over D,.. Define p |/( ll2 and let ve the for l [L 1] each sattisfy ||eell2 1. Set
Å اي U w A. = - for = 2, - 1, ē= e=ptor.-
Then 0- = [ē: vee( (A1): ... vec [1) solves the exact unlearning problem
4 for R(0) |00|2-
Thus, the solution to the minimum norm predictor problem gives the solution to minimum parameter norm problem, so we can apply the previous results to find solution for ( with R(0) w(0)ll2 using the constraint relaxation and then update the parameters as prescribed by Theorem
4.3 2-Layer Perceptron
We lastly consider a 2-layer perceptron with a non-linear activation. Specifically, we define f(0, x) = c T (Axx), where we use the partition 0 = [c: vec(A)] for e E Rd, A E Rhxm Here, h is the total number of neurons and Φ R + R is some activation function. We abuse notation and write o( ((Az) to denote the element-wise application of á to Ax. We analyze the case where R measures the number of active neurons, i.e., the width of the network. Formally, we denote a, as the ith row of A, and we set R(0) = Σ Eim f ||a;|| > 0}. With this choice of R. the unlearning solution promotes recovering a sparse network which fits D,, where D, has n, = [D,| samples. Given that c ((Ax)) y for all (z. y) D, we chase the minimum neuron interpolating solution to D,:
0 argmin R(O) s.t. c. ((A)))) y v( E D,
(10)
0
While we aim to solve 10) for any retain set D,, the exact minimal-width solution remains unknown. Prior work shows that ny + neurons suffice for general activations 23), while for ReLU, some n,-sample datasets need at least nt 2 neurons (24). Here, we apply our framework to recover feasible unlearned networks with width at most n,, improving the best known worst-case bound.
We begin by linearizing the constraints of problem 100 around 0", as directly solving this problem may be intractable due to the non-linear activation é, especially since we assume access to only the model gradients over D,,, not the samples in D, themselves. We define the drift as A a ; vec( A)), yielding the specific instance of the linearized problem (6) for this model class:
min R(O + A) s.t. A (AAa,,) + tr A (6' (A'x,) O cc) x 0 V(æ; v.) E D,, (11)
where c denotes element-wise product. Due to the layered structure and non-linear activation ø. solving (T] may not ensure feasibility for (10), as the relaxed constraints are loose. We first show that a feasible perturbation F, modifying only the last layer c², exists and yields a network satisfying (10) with at most n, active neurons.
Lemma 2. Assume the finite- width network (0 == = T ((Ax)) interpolates D,, where nr = [D,] is the number of retain set samples. Let dim (span "=))) (a. ))., 8 S n,. Then, there exists feasible perturbation À satisfying the linear constraints in (II). such that f( + A.
interpolates D,,, R(@ + Á) < and A = O.

---

Algorithm MinNorm-OG
1: Input: 0", losss I (0), D2 C Dr, step size regularization constant X 2 0, subsample batch size Agent
2: Initialize 9 O'
3: for L. 1,epes. Tepechs do each batch B from D do 5: if Ax < oo then
6:
Compute function gradients Ve.((0, x.) for H; B,i=l. 10:=1,.. -,,... Agent
7:
Solve Á -- argmin l| + 11 + Ae s.t. 1 g: for all i I Agen
Update +- A
Loss descent: t 0 vp. V (0:
10:
return θ
While Lemma provides a feasible point for (II). it is not the solution, as the relaxed problem linearizes the interpolation constraint without limiting drift size, potentially losing interpolation over
D.. The following theorem shows that choosing R to restrict perturbations in A ensures that solving 7 yields a network feasible for (TO) with at most n,, active neurons.
Theorem 5. For R(0) which measures the number of active neurons of the network ((0,-) define
R(O: 0*) = R(O) + ((AAA))
(12)
as the surrogate objective. Then the solution the relaxed unlearning problem 7 with this choice of R results in a network which interpolates D, achieving feasibility for the exact unlearning problem (10). and admits at most = dim (span [ A' (()) (()))))))) (e))) S f2r active neurons, where
[Dr|-
Theorem Jssors shows that for general activation functions, linearizing the constraints to (00) and mini- mizing the sum of the complexity measure R along the appropriate regularizer R for the drift term recovers a network that interpolates D, with at most active neurons, where is the dimension of the span of the learned representations {<(A*x)) (m.)))) Since s can never exceed n,, = [Drl our method guarantees worst-case interpolation width of at most ni, thereby improving the general bound of n, + implied by (3 for minimum width interpolation.
The drift regularizer A only allows perturbations to c², so the solution to 7 reduces width sparsity in the updated last layer + Ac, while leaving the first layer A" unchanged. Although c" + Ac relies on a small set of features, the feature map df [A *) still reflects representations learned from all of DD We show, however, that the sparsity of c* + Å. can be propagated into A", producing network with new, sparser feature map that is less expressive and no longer consistent with having been trained on the full dataset D, yet still satisfics all unlearning guarantees in Theorem []]
Proposition 1. Let 0 vec()) be any parameter vector, and define Á = (Lezo, 1 1 A. Then the updated parameters Ô [c; vec(A)] satisfy: (i) f(0,z) f(O, x) all x E R" (ti)
R(O) R(θ), and (iii) A hus most R(() number of nonzero rows.
Thus, for any parameters 0, we can apply simple update recover new parameters Ô which behave like an R( -nerrnn network in terms of both the function outputs and at the parameter level. We apply this result to the solution the relaxed unlearning problem (7) in the following corollary.
Corollary Let θ = [ē; vec(('A) solve 7 for R defined in 12 and define the updated first layer Á = (1ez0 1 ) A Then network paraneterized by θ è vec( (A)] similarly interpolates D,. has the same number of active neurons R(0) = R(O),, and has at most R(O) non-zero rows.
Thus, solving the relaxed problem 7 and updating A xd via Proposition] Tyillds network that reveals no trace of having been trained on the larger dataset D = D, Li L)D, even at the representation level.
5 From Theory to Practice
We translate our framework into practical algorithm MinNorm-OG (Algorithm TT. At epoch i, we alternaee between solving version of the relaxed unlcarning problem and descending the loss
7

---

Table Data Poisoning experiment results, measured as the median sup-norm distance between the retain set trend (2) and the unlearned model outputs over 10 trials (smaller is better).
Epochs|
Retrain
MinNorm-OG
GD
GA
NGP
NGD
Ridge
f -paare
10
1.50
1.50
3.23
2.56
2.50
2.73
2.27
3.28
100
1.36
1.08
2.76
23.8
2.62
2.85
2.13
1.79
1000
1.17
0.63
2.61
1400
2.75
2.45
1.96
1.37
on D, to maintain feasibility for the exact unlearning problem 4. leveraging access to samples in
D,. Steps 6-8 of Algorithm | denote solving 7 for R(()) - |0 and (((A) - Xe || || where
X 2 O is a scaling parameter, and step 9 shows the loss descent step. To handle batched data and large models, we enforce the orthogonality constraint in 7 over subsample of size Upen within
each batch. For this R and f, the solution to 77) perturbs toward its projection onto the span of model gradients over this subsample (see Appendix EE), which can be interpreted
proximal update under the orthogonal gradient constraint. The main overhead relative to gradient descent comes from solving for Á via a QR decomposition with complexity O(dnpea): ). which is negligible compared to the O (dn B) cost of gradient descent when Npent < BB where ng = [5] is the batch size.
5.1 Experiments
We test our algorithm against the following baseline methods. Retrain erases the initial model and
trains from scratch on D,.. GD [4] runs gradient descent on J (0: D,), while Noisy GD (NGD) [[6] adds gradient noise to the GD steps. GA [15] runs gradient ascent J (0 ;0: D)). NegGrad+ (NGP)
g minimizes a weighted combination of the GD and GA objectives. & Sparee [25] runs GD with an l f--nrmm regularizer. SCRUB (8 optimizes three objectives: minimizing J (0 :D,), minimizing KL divergence of model outputs on D, relative to the original model, and maximizing KL. divergence on
Dy. Negative Preference Optimization (NPO) 18] runs form of gradient ascent over J (0: Dy) inspired by preference optimization. SalUn (26] minimizes J (0: :D,) while fitting random labels over Dy. updating only the parameters that initially have large gradients with respect to J (0; (0:D), :D,)- We apply SCRUB, NPO, and SalUn only in our classification-banl based experiments, as they are not directly designed for general regression tasks. To highlight the performance of our algorithm, we also compare to ridge regression, which approximates our unlearning objective 44) for R(0) = |0l|
by minimizing J (0; D,) A ||@| The minimizer of this regularized objective converges to the minimum-(2-non norm loss minimizer in the ridgeless limit as X, - 0 (22].
While recent work proposed various unlearning benchmarks, especially for LLMs 16 27H29), they often rely on opaque metrics that emphasize suppressing forget-set generation. In contrast, we present the following experiments with interpretable quantitative metrics. In each experiment, we evaluate all methods over a fixed number of unlcarning epochs. In the Data Poisoning experiment, each epoch corresponds to a single unlearning update over the full dataset, D = D, L D,.. In contrast, for the larger-scale Multi-Class Label Erasure and Representation Collapse experiments, each method processes batches from the entire forget set D, and only subset of the retain set, D', C D,, Here, one epoch is defined as a full pass over the forget set batches, where each forget batch is paired with retain batch of equal size sampled from D', Complete details of our experimental setup and full results with uncertainty estimates are provided in Appendix
Data Poisoning. We train a shallow neural network on retain samples (ær, Mr) E D, with yr sin (2,)) and forget samples (æ/, yr) E Dy with yy = 1.5, over input domain X = [-5x, 5π C R. We evaluate the output 0 of each unlearning method by measuring the deviation from the retain set trend, given by supzex [f x) - si)( Results are reported in Table D as the median over 10 trials with visualizations in Figure [ Retrain fails to closely capture the retain set trend y sin(z), while the (regularized) loss descent methods (GD, NGD, Ridge) struggle to simultaneously escape the influence of the forget set and fit to the retain set. GA is unstable and diverges from the retain set. Due to this instability, we found that NGP performed best when the loss-ascent coefficient was near zero, causing it to behave like GD.
Multi- Class Label Erasure. We use the CIFAR-10 30 and Tiny ImageNet 31 datasets, creating red, green, and gray copies of each image. We train modified ResNet- 18 and ResNet-50 models on
8

---

(a) Retrain
(b) MinNorm-OG (ours)
(c) GD
(d) GA
(e) NGP
(1) NGD
(g) Ridge
(hi fg Sp-oree
Original Model
Unleamed Model
sin(x)
Retain Points
Forget Points
Figure 1: Example unlearned model fits when given 100 unlearning epochs for the Data Poisoning experiment, where the forget points distort the retain set trend sin(2).
Batoon
32
510
510
Boca
Figure 2: Pareto frontiers for each method across hyperparameter settings in the Multi- Class Label Erasure experiment on colored versions of CIFAR- 10 (left) and Tiny ImageNet (right). Models predict color and content, the retain set contains only gray images. The ground truth unlearned model (GT) performs well on gray inputs but always predicts gray with probability 1. The x-axis shows accuracy on gray test images (higher is better), and the y-axis shows mean squared error between predicted probability of gray on all inputs and the target of I (lower is better). MinNorm OGG (ours) best approaches the ground-trun -trthh unlearned model's performance relative to the other baselines.
CIFAR-10 and Tiny ImageNet, respectively, to jointly predict image class and color. The retain set D, contains all image content classes only in gray, while the forget set DD contains all colors. The ground truth unlearned model predicts gray content well and always predicts gray color with probability 1, regardless of input. We evaluate retain quality by accuracy on gray-colored test samples, and we measure forget quality eтrоr the mean squared error between the model's predicted probability of an image being gray and the target value of for all colored inputs.
Figure presentss the Pareto frontier of the mean performance across 5 trials for each method under different hyperparameter settings. The optimal point (1, 0) indicates perfect retain quality and zero forget quality eиror. The ground truth unleared model is labeled GT. Our method, MinNorm-OG: performs best across both datasets, as the other methods struggle to unlearn the influence of the colored forget set samples without harming accurate classification of gray test images. Notably, retraining from scratch yields a model with nearly perfect forget quality error, as it is trained only on gray images, but performs better than random guessing gray test images due the limited training epochs and restricted retain set access.
Representation Collapse. We again use the 10 dataset where each of the 10 classes is assigned unique color. The retain set D, contains the CIFAR-10 images colored according to their unique color, while the forget set D, comprises randomly colored images. The ground truth

---

Table Representation Collapse experiment results across constraints on the number of unlearning epochs and percentage of accessible retain set samples. Models are trained on colored images where color perfectly predicts the label in the retain set but not in the full dataset D. Evaluation measured as the mean accuracy (%) on test images labeled by color over 5 trials (higher is better).
Retain %
Epochs
Retrain
MinNorm-OG
GD
GA
NGP
NGD
Ridge
4p-Sparse
Scrub
NPO
SalUn
79.1
49.1
24.0
34.5
45.9
12.6
20.9
12.4
37.3
40.6
29.4
0.1
10
95.5
78.7
55.2
38.3
73.7
33.0
23.0
61.9
43.2
53.4
15
96.3
93.2
78.2
39.8
81.5
46.9
78.2
25.1
74.1
44.6
76.3
92.8
59.5
40.7
34.2
58.3
32.9
33.5
12.5
47.8
42.5
42.5
1
10
98.5
94.7
73.6
38.2
92.4
70.5
63.4
31.4
75.8
43.5
68.7
Table 3: Average time in seconds to perform a single unlearning epoch on the Multi-Class Label Erasure experiment on Tiny ImageNet using ResNet-50, averaged over 5 trials.
Method
Retrain
MinNorm-OG
GD
GA
NGP
NGD
Ridge
fy-Sparse
Scrub
NPO
SalUn
Time (s)
0.90
0.78
0.67
0.68
0.74
0.69
0.68
0.69
0.96
0.94
1.09
unlearned model predicts from color alone, as the color feature completely determines the class label and is easier to learn than the image content features. In contrast, models trained on the full dataset D = D, Li D must predict based on content, since color is no longer fully predictive of the label. For evaluation, we label heldout test images by color and assess unlearning via color-label accuracy, testing if the unlearning methods can collapse the original model into just a color classifier.
Table 2 presents mean results over 5 trials. We observe that Retrain achieves much higher color classification accuracy than any unlearning method, as image color is an easy feature to learn from scratch. However, this result is specific to this setup: since the target function over the retain set is so simple, it is easier to learn from a freshly initialized model than by adapting the original model, which has learned to rely complex image content features. Our prior experiments demonstrate that Retrain not a viable unlearning strategy in general, so we report its results separately in the leftmost column. We bold the MinNorm-O -G results, as they achieve the highest accuracy for each combination of constraints on the percentage of accessible retain set samples and number of unlearning epochs.
5.2 Runtime Comparison
In the above experiments, we compare all unlearning methods under a fixed number of epochs. To assess per-epoch computational efficiency, we measure the runtime required by each method to complete a single unlcarning epoch in the Multi-Class Label Erasure experiment using Tiny ImageNet with ResNet-50, our largest-scale setting. The results reported in Table
We observe that methods which compute loss gradients with simple regularizers on a single data split (GD, GA, NGD, Ridge, l1 fp-Spase are the fastest. NGP is slower, as it requires forward and backward passes over both retain and forget set batches. Our method, MinNorm-OC operates only on the retain set but solves an additional subproblem on top of the loss descent step, while maintaining runtime comparable to NGP. Scrub and NPO are slower, as they require extra forward passes using the original model to evaluate their loss functions, while Retrain is slowed by the need to initialize new model from scratch. Lastly, SalUn is the slowest due to an initial pass over the entire dataset to compute the threshold for deciding which parameters to freeze during unlcarning.
Conclusion
We proposed a new unlearning framework under overparameterization by seeking the simplest solution consistent with the retain set. We proved guarantees on solving the exact unlearning problem through a tractable relaxed formulation. A practical implementation of our framework outperformed baselines, as the simplest solution aligns with unlearning goals and removes artifacts unrelated to the retain set. While our theoretical guarantees open the door for unlearning analysis beyond the underparameterized setting, we focused on model classes like linear networks and two-layer perceptrons. We naturally aim to analyze unlearning more complex settings like deep networks in future work, well as experiment within broader domains at larger scale.
10

---

Acknowledgments
This work was supported part by NSF Grants 2019844, 2107037, and 2112471, ONR Grant N00014-19-1-2566, the Machine Learning Lab (MLL) at UT Austin, the NSF AI Institute for Foundations of Machine Learning (IFML), and the Wireless Networking and Communications Group (WNCG) Industrial Affiliates Program. We are grateful for computing support on the Vista GPU Cluster through the Center for Generative AI (CGAI) and the Texas Advanced Computing Center (TACC) at the University of Texas at Austin.
References
[1] Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016, 2016.
[2] California State Legislature. California Consumer Privacy Act of 2018. Statute, 2018. Cal. Civ. Code $ 1798.100 100 seq.
[3] Isabel Gallegos, Ryan A Rossi, Joe Barrow, Md Mehrab Tanjim, Sungchul Kim, Franck Demoncourt, Tong Yu, ZhaniZ and Nesreen K Ahmed. Bias and fairness in large language models: A survey. Computational Linguistics, 50(3):1097-119, 2024.
[4] Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015. doi: 10. 109/SP:2015.35.
2015 IEEE Symposium on Security and Privacy, pages
[5] Juhan Bae, Nathan Ng. Alston Lo, Marzyeh Ghassemi, and Roger B Grosse. If influence functions are the answer, then what the question? Advances in Neural Information Processing Systems, 35:1 35:1739--1796 2022.
[6] Ayush Sckhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34: 34:110055-8000 2021.
[7] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, pages 2832-3842. PMLR, 2020.
[8] Meghdad Kurmanji, Peter Triantafillou, Jamie Hayes, and Eleni Triantafillou. Towards un- bounded machine unlearning. Advances in Neural Information Processing Systems, 36: 19:79 1987, 2023.
[9] Martin Pawelczyk, Jimmy Z Di, Yiwei Lu, Gautam Kamath, Ayush Sekhari, and Seth Neel. Machine unlearning fails remove data poisoning attacks. The Thirteenth International Conference Learning Representations, 2025.
[10] Pratyush Maini, Zhili Feng, Avi Schwarzschild, Zachary Chase Lipton, and J Zico Kolter. TOFU: A task of fictitious unlcarning for LLMs. In First Conference on Language Modeling, 2024.
[11] Frank R Hampel. The influence curve and its role in robust estimation. Journal of the American Statistical Association, 69(346))333-333 1974.
[12] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, and Chiyuan Zhang. Ticketed Boaminng-unccrmen schemes. In The Thirty Sixth Anmual Conference on Learning Theory, pages 5110-5139. PMLR, 2023.
[13] Lucas Bourtoule, Varun Chandrasekaram, Christopher A Choquette- Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE symposium on security and privacy (SP), pages 141-159. IEEE, 2021.
[14] Seth Neel, Aaron Roth, and Saeed Mhavifi-Mavvjerdi.. Descent-to-delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pages 931-962, PMIR, 2021.

---

[15] Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11516-11524, 2021.
[16] Rishav Chourasia and Neil Shah. Forget unlearning: Towards true data-deletion in machine learning. In International Conference on Machine Learning, pages 6028-6073. PMLR, 2023,
[17] Xiaomeng Jin, Zhiqi Bu, Bhanukiran Vinzamuri, Anil Ramakrishna, Kai-Wei Chang, Volkan Cevher, and Mingyi Hong. Unlearning as multi-task optimization: normalized gradient difference approach with an adaptive learning rate. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume I: Long Papers), pages 11278-11294, 2025.
[18) Ruiqi Zhang, Licong Lin, Yu Bai, and Song Mei. Negative preference optimization: From catastrophic collapse to effective unlearning. In First Conference on Language Modeling, 2024.
[19] Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. In International Conference Artificial Intelligence and Statisties, pages 3762-3773. PMLR, 2020.
[20] Huiqiang Chen, Tianqing Zhu, Xin Yu, and Wanlei Zhou, Machine unlearning via null space calibration. In Proceedings of the Thirty-Thine International Joint Conference on Artificial Intelligence, pages 358-366- 338-366,222 2024.
[21] Tuan Hoang, Santu Rana, Sunil Gupta, and Svetha Venkatesh. Learn to unlearn for deep neural networks: Minimizing unleaming interference with gradient projection. In Proceedings of the JEEE/CVF Winter Conference on Applications of Computer Vision, pages 4819-4828, 2024.
[22] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949 986, April
2022. doi: 10. 10.1214211A0S21444
[23] Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu, Él regularization in infinite dimensional feature spaces. In International Conference on Computational Learning Theory, pages 544-558. Springer, 2007.
[24] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 32, 2019.
[25] Jinghan Jia, Jiancheng Liu, Parikshit Ram, Yuguang Yao, Gaowen Liu, Yang Liu, Pranay Sharma, and Sijia Liu. Model sparsity can simplify machine unlearning. Advances in Neural Information Processing Systems, 36:51 (6:51184-51660 605, 2023.
[26] Chongyu Fan, Jiancheng Liu, Yihua Zhang, Eric Wong, Dennis Wei, and Sijia Liu. Salun: Empowering machine unlearning via gradient-based weight saliency in both image classification and generation. In The Tweifth International Conference on Learning Representations, 2023.
[27] Weijia Shi, Jaechan Lee, Yangsibo Huang, Sadhika Malladi, Jieyu Zhao, Ari Holtzman, Daogao Liu, Luke Zettlemoyer, Noah A Smith, and Chiyuan Zhang. Muse: Machine unlearning six-way evaluation for language models. In The Thirteenth International Conference on Learning Representations, 2025.
[28] Anil Ramakrishna, Yixin Wan, Xiaomeng Jin, Kai Wei Chang, Zhiqi Bu, Bhanukiran Vinzamuri, Volkan Volkan Cevher, Mingyi Hong, and Rahul Gupta. SemEval-2025 task 4: Unlearning sensitive content from large language models. Proceedings the 19th International Workshop on Semantic Evaluation (SemEval-20255 pages 2584 2596. Association for Computational Linguistics, July 2025.
[29] Anil Ramakrishna, Yixin Wan, Xiaomeng Jin, Kai-Wei Chang, Zhiqi Bu, Bhanukiran Vinzamuri, Volkan Cevher, Mingyi Hong, and Rahul Gupta. LUME: LLM unlearning with multitask evaluations. arXiv preprint S.0iv:2502.10997 2025.
[30] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. Technical Report.
12

---

[31] Stanford Cn.3In. Tiny imagenet visual recognition challenge. 2015. Course project from Stanford University's 's CS23In: Convolutional Neural Networks for Visual Recognition.
[32] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference Computer Vision and Pattern Recognition, pages 770-778, 2016.
[33] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2016.
13

---

A General Notation
Vectors and matrices are in bold, with vectors lowercase and matrices uppercase. For sets A, B, AUB denotes disjoint union. 2 is the power set. For a proposition a, 1 {aa is if true and O otherwise; day is +oo if true and 0 otherwise. For æ E I2 and C R PA (x) is the Euclidean projection onto A. For Z E IR*x,, vec( Z) E R is the columnwise vectorization. im 2), ker Z), and row denote the image, kernel, and rowspace. || F is the Frobenius norm, || is the nuclear norm, and 21 is the spectral norm. For Y E m (Z, Y) is the Frobenius inner product and Z @ Y is the element-wise product. (r(-) is the trace. For x E I& and RRd, [x: Bd. stacks x and y. | is the lp norm. [m] = (1,.... .......,... For ar E R, (x)+ = max (ar, 0} is the ReLU.
nj..
Let O and 1 denote the vectors with each entry equal to 0 and I respectively. Further, for x IR and e R. let Layle denote the vector which is 1 in each entry of which is not equal and otherwise.
B Minimum Norm Solutions to Linear Regression
Here prove various properties of minimum norm solutions to linear regression problems which later use for our unlearning results. Following the notation in Section we consider the full n-sample dataset D {x., 4)) with sample inputs æ; Im and outputs Y: R. We consider training linear model f(0, x) = OT parameterized by 0 R We work within the overparameterized setting, so we assume m > n. Define the span of the input vectors S = spanfæ (x, y) E D), and assume dim(S) so the regression problem is realizable. Consider solving the following problem for finding the linear regression solution with minimum & norm:
0- argmin ||0|| s.t. f(0, a)) y V(x.y) ED
Let X E R2xm be the wide matrix whose ith row is equal to a.,, and let y E E" be the vector whose ith element is yı. Then, we can write an equivalent problem in matrix form.
1 11012 s.t. y Xe
0" argmin 2
(13)
We then characterize the solution the above problem relative to the constraint set. Lemma 3. 0* is the unique vector in row(X which is feasible for
Proof. The objective 13) is convex objective with linear constraints which is bounded from below by and has non-empty feasible set. Thus, the KKT conditions are necessary and sufficient for optimality. We now derive the solution X E IR" to the dual problem.
min 1 0
100
s.t. y XO min max AER
|012 + X
X0)
max min
1
|10112
T
(y X0)
2
max 2
1
X
>1| T (g XX A)
s.t. θ= X
| A + XT s.t. 0= T
max
XX
X' and 0 x X
(14)
Thus the primal solution 0* must be of the form
X T X E row X)) To show uniqueness, consider
O 0g row(X that are both feasible for Then,
XO X
X 0 05) 0 0 0 E ker (e).
But, since row (X) is subspace, 07 05 row X) implics 0 ker( X) L Thus,
03 row (X) Further, (X)
0 - 0 E ker((X) n ker X) (0) - 0 = 0
14

---

Using the same analysis, we can characterize the entire feasible set in terms of 0*
Lemma 4, The feasible set to 13 {
- = 0" + ker (X).
Proof. Let O' satisfy y = X0'. Then, X (0' 0*) = 0 so 0' 0 E ker X).
To show the converse, take any 2 E ker ker(X). Then X (0 + =) = X + X2 = X0 =
Using this characterization of 0" and the feasible set, we can cleanly understand how to achieve minimum norm solutions over just subset of the constraints given feasible point. This is central to our unlearning setup in later sections.
Lemma 5. Consider any subset D, S DD and define 0 as the linear regression solution over just D, with minimum norm:
0%- argmin |10112 f(0,x)) (0).))=1 = v(a,y) Dr
(15)
Let S, sp (x, y) E D. Then 0; Ps, (0*).
Proof. 0" already satisfies the feasibility constraint over the whole dataset D, so it must be feasible for 15) Applying Lemmas] 3 and 4 to the minimum norm problem over just D, (15). we must have
that 0r S, and 0* = 0 for some E S. Then,
Ps. (0") Ps. (0, + 2) Pss (0)) 0r
C Loss Minimization Does not Protect Against Data Leakage
The following example concretely demonstrates how certain minimizers of the retain set loss do not align with the intended goals of unlearning.
Recall the unlearning problem for linear regression discussed Section 4.1 In this case, we use the linear model f(0, æ) = O parameterized by O E R". Further suppose the original dataset D ((), has n samples with I; E RT 3/4
Denote the subspace (a. E D), and assume (lim(S) n so the problem is realizable. We work in the overparameterized setting where m and the objective function defined as the mean squared error denoted by
span (æ
[(; n
Σ (y (x
xTx)
Consider when the learning algorithm A runs gradient descent the loss, initialized 0. Due the overparameteriiztion, I has an infinite number of minimizers which each achieve 0 loss. However, is biased towards a specific minimizer which is the unique minimizer the loss the span the input samples, denoted as the subspace S.
Proposition 2. Let (D) be a learning algorithm which runs k steps of gradient descent on J (0: D) initialized at O, and define S span(x (x, v) E D). If lim (DD converges to some 0", then
k-
{0)} S argmin J (
x0 11y--X01 where the éth entry of y R yi and the ith row of X E paxm is क Note that the gradient of the loss for any value of 0 is contained the subspace S, VeJ DD; 2 x (Xo y) and im(X )) S. E Since subspaces are closed under addition, every iterate of
Proof. We write the loss function (0; D) in vector form (0; 11y
Further, the initial iterate of A gradient descent on I (0: D) starting from O must be contained in S. Thus if AtD converges, it must converge to zero of the gradient of the loss, and this point must also be in S. Since the loss convex, this point must be loss minimizer.
15

---

In this case, the original training solution 0 which results from simply performing gradient descent interpolates all of and lies on S. the span of the imput samples in D. Then, given an unlearning request to forget any subset D from D, 0" itself is minimizer to the loss on the resulting retain set D, = Dy. However, since 0* reveals information about all the input samples in D, necessarily leaks information about the samples in y. Thus, even though O is valid minimizer of J (0: Dr)), it not an acceptable unlearning solution.
D Proofs
D.1 Proof of Theorem 1
We assume f(0", interpolates all of D, f(0", .x) y for all (æ, y) E D, and that the sample- wise loss L (0, x, y) is minimized when f(0, x) = y. Thus, 0" must minimize each of the sample- wise losses C (0, æ, y) for all (æz, y) E D. Therefore, VoL (0", y) = 0 for all (æ, y) D.
D. ((.))), C y) and (0"; Dj) pyyl (( (0, x. y), we must have that VeJ (D) = VoJ (0": :D) 0.
Since ;
Then, if Mia any loss loss-gradient unlearning method, the update rule must be of the form
M ((D,,, D,) = P.V (D"; + P. (0"; :)) +
where P. and P/ positive the fact that VeJ (0"; D,) = VoJ ; = 0 to the update MLG gives the desired result:
matrices and is zero-mean random variable. Applying
MLG (A, I, A(D), 0" + +
D.2 Proof of Theorem 2
Recall have feasible vector 0* such that 0 for all (x, y) D, and we want to recover 0r, the minimum & norm solution over just subset D, - D:
r argmin 101
s.t. TJxx x= v(z,y) D,
(16)
Consider solving the relaxed unlearning problem 7 for R(0) |10112:
À 0 A s.t.
argmin
A L æ V(r E Dr
A
Define S, spann# (x, 3) E D,} and write the equivalent problem:
À = argminn
110 + A
AES
By first order optimality, 0" - S, so must have that
Á - Psy (0')
Thus the updated unlearned vector is
0* A 0" Ps (0') = Ps. (0").
Then. Ps, (0*) 0 by Lemma
D.3 Proof of Lemma
Recall that in this case we are interested in minimizing R(0) ||w(0)]lz, where w(0)
AJ AT returns the effective linear predictor parameterized by 0.
16

---

We first show that A is feasible for the relaxed problem 7 Firstly, A is zero in all entries except those corresponding to the perturbation of A1. so we only need to ensure that ÅA, is for each (x, v) D,- Recall we denote the retain set input space as S, span æ (a, y) Dr }. and A is defined as
orthogonal to f 2))
A = - 2 T A c
-2
A2 ... A..AA
A PS (w(f"))
2
Further, the gradients are computed as
AA,S(0,, A
..Aii Ai,11c00
c
Then for any (x,y) D,,
(À Al VA.S(0" x)) tr { | VAI
V A .2) (ÅAi)
A A -2 tr (AAT A
ca Psy (w(O")) oJ TT AL-1- ... ..,))
0,
where the last step follows from the fact that the inner term x. Ps! (w(f")) = since a E Dr implies E S, by definition.
We now show that 0" + Å achieves the optimal unlearning solution 0", By construction of A the only entries of that are perturbed are those which correspond to A,. Thus, we compute effective linear predictor after the perturbation:
w(0" +Ā) = w(0") + Á
A
C
w(0") A
AL-1c 11 2
Ps. (w(O")) CT -
(( ... ".) A² ... ..AA"_ie*
= -w(0") ||45T ...
A c l| -2
Psy (w(0")) (A₂ ... ",, A3 ... .,
-w(0") Pss. (w(0"))
Pss (w(O)))
Since the linear predictor w(0") already interpolated D, Ps. (w(0") must be the minimum norm linear predictor over D, by Lemma 5 Thus, the effective predictor of the perturbed parameters w(O + ) solves the exact unlearning problem when R(0) ||w(0)) so 0 + Á achieves the optimal unlearning solution.
D.4 Proof of Theorem
Recall for this theorem we analyze R(0) = 1|w(0)ll2- Let Å be the perturbation which satisfies the conditions in Lemma Then, Á is feasible for the relaxed problem and further 0" Á solves the exact unlearning problem
Now, let A minimize the relaxed problem for this R defined ( Then because R ensures that all elements of A which do not correspond to A₁ are zero, we must have that for any (x, y) E D,:
w A x T Ai A (Ai + A'A)
- c* A A A',
y "A Vol (0 ..)) y,
where the last equality follows from the feasibility of A to Thus, 0" + A interpolates D,, so 0" + A is feasible for the exact unlearning problem
We now show this point also optimal for
17

---

Since 0- + solves the exact unlearning problem 4 and 0 + A is another feasible point, we must have that
R(O A) R A+)
Further, both A and A are feasible for 7 and A is defined as the solution to 7 so we must have that
R(O +
< R 0 + +))
But, since both Á and A are non-zero only in the entries corresponding to A,, applying and R yields the same value:
RO + A R( + Á) and R(O + --) - + +
Thus, R(O' + A R + A), so 0 + achieves the optimal objective value of (4) Since
we established feasibility and optimality, 0" + must solve
D.4.1 Necessity of Additional Regularizer R for Theorem
In this section, we show that minimizing just R over the relaxed constraints, i.e. solving (6) for R which measures the linear network predictor norm does not solve the exact unlearning solution. Because there is no control the size and direction of the perturbation A, we can construct a simple example where A satisfies just the linearization of the data interpolation constraints but the updated network 0 + A no longer interpolates D,.
Consider dataset of two samples D {(e1, 1), (e2, 1)], where e; R" is the ith standard basis vector for any m 2 3. Consider the original 2-layer interpolating network trained on D defined by R" and A is the m identity matrix
parameters 0 [c* vec (A*)), where cº e1 + e2
A' In., so ʃ(0", x) c² A'x (e: e2) x.
We set D. {(e 1)} and D, f(ez, 1)}, and define the perturbation variable A Ae veo( AA)]. Translating the constraints of (6) to this specific problem instance, we have that
A + tr(A + =
We then select the values A = -3 and A = ege, e2e eze₁ is easy to see that these choices satisfy the above constraint. Further, they achieve exact minimization of We show below that the resulting network's predictor (A* AA) (c* Aa) 0.
R(0* + A)
(A' + AA) T + Ac)ll2
eze
6262 - e3e3 (ei + - e3)1l2
(I+ eiee
e222 ege + ea)ll2
|ee + e2
E3 - ea - el + tall2
|0|| =
Thus, the updated network which solves (6) predicts the constant function at for inputs æ, as f(o + A, = ((A* + AA) (c" + Ac))
0.
This clearly does not interpolate D,. and this example as a whole demonstrates that failing control the size and direction of the drift term A beyond just the linearized constraints does not lead to the exact unlearning solution.
D.5 Proof of Theorem 4
Denote the minimum & norm solution w(θ)) to Xw as just w. for brevity. Using w we construct solution to the exact unlearning problem 4 for R(0) ||0||g- which we restate below:
argmin 101, s.t. w V(x E Dr
18

---

Expanding 0 = le; ; vec( (r))) into the sub-parameters, squaring the objective, and organizing (æ, v) D, into imput data matrix X, [Blp=|xd an equivalent problem:
xd and output vector yr E RR P-l gives
L-1 Σ
argmin ||l|2 AL-1
+ t=1
A s.t. yr = X AL
(17)
Let c², "i.i...... Aii...,,A....... Ai-1 be solution
Then, Ai ... A interpolates D,, so A A = w, + 2 where w. E row(Xx, (X,) and & E ker(X,) by Lemma
Let Pw; [w; w. the projection matrix onto span(wjj (w)). Then replacing Ai with P; maintains feasibility since A A-_,c²* = Pw; (w + z) = w, which feasible by definition. Further, A.Pwo we achieves smaller objective function value since
Aipw: f ur
A = tr(P:: Ai Ai} < Pw; lla || Aill. ||il]
The second equality follows from the cyclic property of trace and the fact that Pw: is both symmetric and idempotent, and the inequality is generalized Hölder's inequality for matrices.
Thus, replacing Aj with the rank-1 matrix Ai Pw: must preserve optimality of any solution that contains AT. Write W: = \ for some A E IR, 01 E R with ||0 =1
We can apply an analogous argument with the matrix Po,, which projects its imput onto span( (1). to show that any solution that contains A must remain optimal with Aí replaced by the rank- matrix A Continuing this argument for each A;, ......4 L as well as for c* shows that can search for solution over a much smaller space. Specifically, for some de and v E Rh, can decompose e" and each A
Ai A TT
A Nevrol1 for -= 2- c² -
reduces to Then. 17
min Pe 112 ||
Σ
1=2
s.t. (A1woe) (22011)))))))))))))))))))))))))) ... (26-101-001 w, and ||we||2
min
w
2 +
A s.t. A .. :
(18)
X
We perform change of variables setting 7 X and enforcing % 0.
min 750
w
w
+
N s.t.
7172 1..
77.=
(19)
2m
Define y (.....,, Yr.), objective function g(>)) I + 2 Ye. and constraint h(y) 7172 " - = 0. By the AM-GM inequality, we have that for any feasible
Et
g(r) 2 L (1wwillnn....0
L l/
where the last equality follows from the constraint h(7) 0. Define feasible point > such that
2" > -(Iwwll
2(1-L)
.|lw | | w11
19

---

Then s(>") 2 achieves the lower bound, so it must solve 19 Thus, the optimal values Ni...., Xi to (T8) result from taking square roots Yē- Then, the following values for the network parameters must be optimal for 17
(1-L) Ai = ||w
A ||w 1e0 for l 2, 2,...,I-- L-1 c' c' "=W 1L-1-
D.6 Proof of Theorem 5
We prove the theorem using the following lemma. See the end of the section for a proof. there exists Ae E G.* such that ||c Acllo S 8, where the Eo- oo-norrm llo counts the number of non-zero elements.
Lemma 6. For E IRth and subspace G C R8th such that dimi())
Because ft does not allow any perturbation of A", any solution to 12 must only perturb 0* in the entries corresponding to c².
Let dim(spanf Φ [A x) "x) (m.))D,) Note that by definition we have that S [D,]. Apply the lemma and span ( A (m.g)) so that there exists Àe E span ([d(A")) such that ||c*
Ácllo < s. Define = [ 0].
Then the network defined by 0 Á has at most active neurons since any zero element of c" + A cannot contribute an active neuron. Further, {Ø(A A (a)))))) = {VaJ(0" , ,.),,, so the perturbation Á is feasible for the relaxed problem (7) But, f is linear in so this perturbation must preserve function value on D,,, since the constraints of the relaxed problem are tight when just perturbing c², Thus, the resulting network defined by 0 Á both interpolates D, and has at most dim (span (dp( A ("*)))))))))))))))(())))))))AA (a.))))))) active neurons.
Note that this construction of Á satisfies the conditions of Lemma so do not include separate proof of the lemma since it is contained within the larger proof of the theorem.
Proof of Lemma
Let the columns of some P E I form a basis for G so that im(P) G Consider the reduced column echelon form of denoted reef (P) P. By definition, im (P) im(P) g so rank( () = h and thus each of the 8 columns of has leading one. Let pb, the ith column of P and let j; denote the index of the leading one in p. for all i [h- -sss.. s].
Let (p:)a denote the kth element of p:. By definition of the reduced column echelon form, we have that (p:)a for all Js. Define
h
PPx
for coefficients 7/2 E defined as
2
c²
Pe
Since each p; is only non-zero in the indices ji h. must have that (c" + Ac)j. for all
i E [h- - s). so ||c + Acllo < 8.
D.7 Proof of Proposition
Consider any parameter vector 0 = vec Then for any input æ, we can write f00, Σ c, æ) where c; is the ith element of c and a, is the ith row of A. Consider the updated parameters [c: A)] for = (lex0, ) o A. Then,
[(0,z) = Σ ca x) = Σ c, 40aa f(0,x),
20

---

where the second equality follows from the fact that we can set to be zero whenever = 0 since that neuron does not contribute to the function output whenever c; O. Further, changing a, for any i where = 0 does not change the number of neurons, since if for the ith neuron we have 0. then this neuron can never be active no matter the value of az:
R
1(ee | > 0}
Σ $:c,
1aa + 0)
Σ
[ + 03 R((),
:: c2
where a. is the ith row of Å. Lastly, since à; is always equal to when C; = 0, we must have that A has at most R(O) number of nonzero rows.
E NinNorm-OG Algorithm
We derive the closed form solution of (7) for the specific choice R(0+ + 4) = 10 + A 12 + +
Define the span of the model gradients over D, the subspace G, span Vof (a.y))) and consider any À 2 0. We then solve the following problem:
argmin 0 + A
X
|| 1 S.L. A E G
(20)
This is strongly convex problem over a linear constraint, so its solution Á the unique point which satisfies the following condition for first order optimality:
(1 + x) + g,.
Note that this is satisfied by the projection
1
po: (0),
1+1 X
which must then be the unique solution to 20
F
Experiments
We first standardize the notation for each algorithm. Throughout our experiments, we sweep over hyperparameters and report the best results for each algorithm, and we sweep related hyperparameters for each algorithm through the same set of values. For example, every algorithm has learning rate which is selected from searching over the same set of values. We first define the hyperparameter names we use along with the algorithms they apply to.
Table 4: Hyperparameter definitions and their associated methods.
Symbol
Methods
Description
T
All
Number of epochs Learning rate
7
All
AGA
NGP. Scrub, SalUn
Loss ascent coefficient Regularization coefficient
Avog
NPO. Scrub, MinNorm-OG, Ridge, & Sparse
NGD
Gradient noise standard deviation
Tap
Scrub, MinNorm-OG
Number of final descent epochs on retain set Regularization coefficient decay rate Projection period
Yoeg
MinNorm-OG Ridge
MinNorm-OK
Ppprt
MinNorm-OG
Subsample size to compute gradient space
F.1 Implementations
We now define the exact implementation of each method. Consider batch of retain samples B, and forget samples By, along with loss function J. For each method, we use the AdamW optimizer with learning rate 77 different effective loss functions. We express the loss functions below.
21

---

F1111
Retrain and GD
Retrain and GD share the same loss function, but Retrain initializes model from scratch before optimizing this loss.
(0; JGD(O;B.) J (B;
E.1.2 GA
-
E1.3 NGD
(0 J (0: +
where & ~N(00,021) is zero-mean Gaussian random vector.
F14 NGP
= J (0: - >GN (B;
F.1.5
Ridge
We store a regularization weighting À which we initialize to À = A We define the Ridge loss as
TRidge (0 ;,, J (
After updating the parameter vector using this loss on each batch, we update as
A
Trg
Note that Trg is always set within the range (0, 1), the update to À approximates the limit À goes to 0 as we iterate through the epochs. This attempts to recover the minimum-now norm training loss minimizer.
F.1.6
f fi-Sparse
For each epoch
1,... T. we define the é -Sparee loss
Jt, St
= J (, + 2(1 (0; (0
Moog |00|
T
This follows the linearly decaying regularization schedule proposed in 25
E.1.7
Scrub
The Scrub loss decomposes into different terms depending on the epoch. Let To(y x)) denote the model's 's predicted distribution over classes for input æ for parameter vector 6, and define KL(- [] as the Kullback-Leibe Leiber divergence. Recall 6* denotes the initial trained model parameters, and denote the current epoch / E (O...., 1). Then the Scrub loss Jsemb Br, By, Areg, \GA, () is defined as:
Jscrub Br,, By, Areg AOA. t) =
J (A (B)
+
[8..1
Aea
Σ
KI (y) xx) Ro xx)) if even or -
(.))B....
Aua By
Σ
(T (y
my) To xz))
otherwise
EB
22

---

F.1.8 NPO
Recall that 0 denotes the initial trained model parameters. Then, the NPO loss is
1
2 AGA
To xt)) 11+
Aai
INPO :0; AGA)
log
B
Te- (y) xfy)
(my.ur)eB,
where To(y1 x denotes the model's predicted probability of class yy for input 2 for parameter vector Note that this is equivalent to setting the parameter / in (88 to Aeg-
F119 SalUn
Before performing any unlearning. SalUn computes the median the absolute values of the elements of the model gradient with respect to the loss over the forget set at the original parameter vector 0" Formally, define
9, abs( J (0" :Dy))
where abs(-) denotes the element weise absolute value. This step requires an initial pass over the forget set which we do not count toward the number of unlearning epochs T.
The "saliency mask" ms is then defined as the binary vector that selects parameters whose corre- sponding gradient magnitudes exceed the median of gy, denoted median(g,))
ms Ligs median(g)) (gy))
After computing ms, SalUn minimizes the loss
Jsaunn : (3)) = (0; + AGXJ (0)
where B' is modified version of the forget batch By in which each true label is replaced with random incorrect label. During unlearning, SALUN treats only the parameters where mg 1 as trainable and freezes the others. Thus, the gradient update is applied only to mg @ O.
F.1.10 MinNorm-OG
For each batch B,, we always perform loss descent step:
JMinNurm-OG (0; J (0 B,)
Following the Adam update for this loss, we then (depending on the epoch) perform the model update corresponding to solving the relaxed unlearning problem ( for R(e + A) = ||0 + A 1
A where is saved parameter of the algorithm. We use the parameters TProj and TeD to determine which epochs to perform the unlearning update. For the TeD last epochs, we only perform the descent step and skip the unlearning update, similar Scrub. In the first T' TeD epochs, perform the unlearning update every Pru epochs.
We initialize \= Avs 1, and each time we perform the unlearning update, we grow the value of
through the update + A+1 using the decay factor Yee E [o, 1]. For our algorithm we only use values of Are such that Aveg < 1. The update for À leads to solutions to the relaxed unlearning problem which result in smaller, more conservative perturbations.
To interpret these values, first recall that we solve the relaxed unlearning problem over a subsam- ple of each batch B, C B, where |3 "pen-- For convenience, define the gradient subspace G. = span SipanVoo[( (f, x)) ) (ae WEB: As we showed in Appendix E for any value of X, the optimal perturbation then Â
T PoL (0). Thus, the initial value À -- leads the perturbation
Ang
Á = -rrog a (0). Further, the coefficient update
X+1 leads to more conservative
1 unlearning perturbation À ~heg 1 Po.. (0), as it is down- weightdd by "egg- Thus, Aveg is the initial strength of the perturbation and Treg represents a multiplicative decay of this strength through each update to X.
23

---

Table 5: Data Poisoning experiment results showing the median sup-norm distance between the retain set trend s2) and the unlearned model outputs across 10 trials (smaller is better). The parentheses indicate the central range of values over the 10 trials.
kpoochs
Retroin
MinNorm-OG
GD
GA
NGP
NGD
Ridge
Spprree
10
1.50 (1.34 1.55)
(155 2.66)
3.23 (2.52, 6.65
2.56 (2.19, 3.45
2.50 26, 3.54)
2.73 (2.26, 7.25)
2.27 (1.90 3,02)
5.28 (2.52 (2.5. 3,62) (1.9 2.48)
100
1.36 (1.27, 1.4)
LOR 163)
2.76 48, (,54)
23.8 (18. 30.0)
2.62. 187)
2,85 (2.47 3.57)
2.13 (1.75, 3,13)
1000
1.17 (1.08 1.26)
0.63 0.96)
2,61 (2.39, 3.38)
1400 (1025, 1899)
2,077 9.80)
(1.66 3.67)
(196 3.84)
(1.1 (1.19,11555 1.55)
We formally write the unlearning update at epoch as follows, where 0g is the current parameter vector, nnw is the updated vector, and mod denotes the modulo operation.
if t mod Treo o or fort2. 2 T -TD
θ new
00
else
A argmin
100 + A12 + +
Aeg
0 new
0 + Å
1
A
Yree
Gradients for Classification. We make a special note of how compute the gradient sub- space 9, for classification tasks. At the parameter value lg. the model prediction is f(0,, x) = argmax ze, (y x) where 2 x:) denotes the model's unnormalized logits over the classes y for input æ for parameter vector 0. This is not a continuous function of 0, so we cannot compute its gradient directly. However, following prior works [19), we the gradient Vo (ze, (y z)),- where j = l0o, æ) the model's predicted class for input æ. other words, we take the gradient of the the unnormalized logits at the index of the maximum value, where we do not treat the index as function of A.
F.2
Data Poisoning
We train 3-layer multilayer perceptron with a hidden dimension of 300 using the sigmoid linear unit (SiLU) activation function. For each seed, we randomly sample 50 retain set points (æy. Mr) D, with = sin(x,,) and 5 forget set points (z), E D, with yy = 1.5, over the input domain X' = 5m, 5m] C TR. We initially train the poisoned model on all the samples using the AdamW optimizer with a learning rate of 10-3 over 100,000 epochs.
Given these poisoned models, we apply each of the unlearning algorithms parameters and evaluate the output 0 of each unlearning method by measuring the deviation from the retain set trend, given by suP ((, a) sin(w)) We fix the number of epochs for each algorithm and allow full data access, so each method has access to all of DD during unlearning. We repeat the entire process over 10 trials. For the number of unlearning epochs T {10, 100, 1000}. we report the best performance of each algorithm in Table 5 along with the central range of each method's performance over the 10 trials, discarding the two best and worst trials. We report the best
sweep of hyper-
hyperparameters for each method in Table 6. and the corresponding search spaces in Table 7 We
also include visualizations of the recovered models from each unlearning method in Figures 3 and
5. All experiments were run on either single NVIDIA A40 GPU or single NVIDIA H200
GPU.
24

---

Table Hyperparameter settings for each entry in Table rameter is not applicable to the corresponding method.
Blank entries indicate that the hyperpa-
Epochs
Method
AGA
Aueg
TeD
Tieg
T Proj
Tlpert
Retrain
le-4
MinNorm-OG
le-3
.1
GD
le-4
GA
le-4
NGP
le-4
1.0
NGD
le-2
Ridge
le-2
3.0
f 2-Sparse
le-2
.1
Retrain
le4
MinNorm-OG
le-3
.1
50
99
2
50
GD
le-3
GA
le-4
100
NGP
5e-4
.01
NGD
le-3
.1
Ridge
le-3
3.0
S-Sparse
le-3
.1
Retrain
le4
MinNorm-OG
le-3
.1
500
10
GD
le-3
GA
lc-4
1000
NGP
le-3
.001
NGD
le-3
1.0
Ridge
le-3
3.0
E fi-Sparse
le-3
.1
Table Hyperparameter values tested in the experiments corresponding to Table
Epochs
Ang
They
Ada
9yen
[le-2, 1e-3, 16-4)
(0.1. 0.5. 1.01
[0.1. 1.0, 3.0)
[0.3,0.6 0.9)
(0.001, 0.01, O.I. 1.0
21.2.5
11,2,5)
(50)
100
[1e-3, Se-4, 1e44)
0..1,0.5 1.0)
[0.1, 1.0, 3.0)
[0.3, 0.6, 0.6,6.6..)) 0.9)
(0.001, 0.01, 0.1. 1.0]
[25, 50]
[1,2)
(50)
1000
[1e33, Se-4, Ie-4)
(0.1, 0.5. 1.0)
[0.1, 3.0)
[0.3,0.6 0.6,
(0.001, 0.01,
(100. 200, 500)
50, 100)
[50]
(a) Retrain
(b) MinNorm-OU (ours)
(c) GD
(d) GA
(c) NGP
(f) NGD
Ridge
(h) L1-Sparse
Original Model
Unleamed
Retain
Forget
Figure 3: Example unlearned model fits when given unlearning epochs for the Data Poisoning experiment, where the forget points distort the retain set trend sin(z).
25

---

(a) Retrain
(b) MinNorm-OG (ours)
(c) GD
(d) GA
(c) NGP
(f) NGD
Ridge
(h) ετ -Sparsc
Original Model
Unleamed Model
sin(x)
Retain Points
Forget Points
Figure 4: Example unlearned model fits when given 100 unlearning epochs for the Data Poisoning experiment, where the forget points distort the retain set trend = sin(x).
(a) Retrain
(b) MinNorm-OO (ours)
(c) GD
(d) GA
(c) NGP
(f) NGD
Ridge
(h) E 21-Sparse
Driginal Madel
Unleamed Model
sin(x)
Retain Points
Forget Points
Figure 5: Example unlearned model fits when given 1000 unlearning epochs for the Data Poisoning experiment, where the forget points distort the retain set trend sin(x).
26

---

F.3 Multi-Class Label Erasure
We use the CIFAR-10 33 and Tiny ImageNet [1 datasets, creating red, green, and gray copies of each image in the training sets. The retain set consists of all gray images, while the forget set is formed by randomly sampling a proportion Peolor E [0. 1] of the red and green copies. We then train modified ResNet- 18 and ResNet-50 models 122 on CIFAR-10 10 and Tiny ImageNet, respectively, to jointly predict image class and color. Each model includes two separate prediction heads, one for image class and one for color.
For CIFAR-IO, we train for 100 epochs using the SGD optimizer with an initial learning rate of 3 x 10-2, weight decay of x 10 momentum of 0.9, and batch size of 256. The learning rate is reduced to 3 10-3 at epoch 50. The ground-truth unlearned model is trained on the gray images alone using the same parameters.
For Tiny ImageNet, initialize the ResNet-50 architecture with TaaggeNet-pretratie weights [33 from the torchvision library. We apply standard data augmentations to reduce overfitting and train for 100 epochs using a batch size of 512, initial learning rate of 0.1, weight decay of 10-1 and momentum of 0.9. The learning rate is decayed by a factor of 0.3 every 25 epochs. During the first 10 epochs, weights to the colored-image domain. For the remaining epochs, we optimize both the class and color prediction losses. The ground-truth unlearned model is trained on the gray images alone using the same parameters.
update the model only using the class prediction loss to adapt the pretrained
We then apply each of the unlearning algorithms over different constraints the number of unlearning epochs and the amount of available retain data. We define Pretain E [0. 1] as the proportion of Dr available during unlearning. For each of the 5 trials, train new initial model and sample Pretinn proportion of 'D, to serve as the available retain data. During each unlearning epoch, the algorithms iterate over batches from the forget set. For every forget set batch, corresponding batch of the same size is sampled from the available retained data. The epoch ends once all forget set batches have been processed, regardless of whether there are unused retain set samples remaining. Any unused retain batches are not discarded-ther will be sampled in subsequent epochs. Once all available retain set batches have been used at least once, the sampling process begins again from the start of the available retain set samples.
The ground truth unlearned model is only trained gray samples, so it achieves strong accuracy on gray-colored inputs and always predicts the input image to be gray, no matter the input image color. We thus measure retain quality accuracy on gray-colored test samples, and forget quality error by the mean squared error between the predicted gray probability and the ideal value of across all colored inputs. For each method, sweep hyperparameters and plot the corresponding Pareto frontier across the two metrics, where the optimal point at (1, 0) which indicates perfect retain quality and zero forget quality error. Each point in the frontier for a given method represents the mean results over 5 trials of a single hyperparameter combination, with error bars representing the standard error for each metric. We label the performance of the ground truth unlearned model GT. All training and parameter searches were performed on cluster of NVIDIA GH200 GPUs.
Table 8: Hyperparameter values tested for the results in Figure 6 running the Multi-Label Class Erasure experiment on CIFAR- 10 with Pester = .01, Pretain = 001 and T
Hyperparameter
Sweep Values
{10-3 10-4 10 10-33
Aga
A
[10-3,10-4.5 10 2)
10.1, {0}
TeD
Tiog
00.2,0.4,0.8)
Thoj
[1]
Upet
{50)
27

---

0.8
Retrain MinNormOG
0.7
GD
GA
NGP
Forget Quality Errer (Lower
SalUn
0.3
0.2
0.1
0.0
0.3
0.2
0.6
Retain Quality (Higher
1)
Figure 6: Pareto frontiers for each method across hyperparameter settings in the Multi-Class Label Erasure task CIFAR-10 with Peator _01, Pretain .01 and 7 2. This is enlarged version of the left subfigure in Figure p with added error bars.
Table 9: Hyperparameter values tested for the results in Figure Erasure experiment Tiny ImageNet with Peotor 01, Pretain
7 running the Multi-Label Class .01 and T 5.
Hyperparameter
Sweep Values
[5 x 10 1074 10-0 10 10
Aga
{10 10 10 10
Areg
100-,,0-2,,5
10 10
10.1,1.0, [2,3)
TeD
Yhey
(0.2,0.4,0.8,00 0.9)
Tho
[1]
Tlpert
{50}
Retrain
0.7
0.6
NGD
Ridge
Forget Quality Erao (Lower
L15parse
0.5
Scrub
NPO
SalUn
0.4
GT
0.3-
0.2
0.0
0.1
0.2
0.3
0.4
0.5
Retain Quallty (Higher
Figure 7: Pareto frontiers for each method across hyperparameter settings in the Multi-Class Label Erasure task on Tiny ImageNet with Peoler = -01, Pretain .01 and = 5. This is an enlarged version of the right subfigure in Figure with added error bars.
28

---

Table 10: Hyperparameter values tested for the results in Figure running the Multi-Label Class Erasure experiment on CIFAR- 10 with Pootor
001, Pretain .01 and T
Hyperparameter
Sweep Values
10 f10"2.1074.10 10 10 110-2,10"2.10 10-
Aga
Ang
[10-3,10-2.5 10 "000,,10-)
10.1,1.010000 [0]
Teo
Tree
00.2,04400.3
Phaj
[1}
Ppes
{50}
Ratrain
MinfermOG
MinHormD
57
57
MCP
2.5
660
660
kldge
Rldge
Forgee Que froe (Lowee
Torge Qualtty Erner cooe
2.5
Sencb
MPO
MPO
saluh
0.2
6.1
611
00
011
0.2
0.3
0.4
0.5
0.5
0.7
0.8
3.1
02
0.3
6.1 Retain Quality (tiiger 1
0.6
0.6
Retain Quality (Hiiger
1)
Figure 8: Pareto frontiers for each method across hyperparameter settings in the Multi-Class Class Label Erasure task on CIFAR-10 10 with Peolor ,01, Pretain = .01 and T = 1. The left panel omits error bars for visual clarity.
Table 11: Hyperparameter values tested for the results in Figure running the Multi-Label Class Erasure experiment on CIFAR-10 with Peotor
.01, Pretain
.001 and 7 =
Hyperparameter
Sweep Values
{10-3 10_4 1000.00-55 10- 10 110-5,10-2,10-1)
Aga
Are
110-3,10-,,5 10 10 10.1,1.0,1000; (0)
Ten
Tice
(0.2,0.4.0.8)
Thoj
(1)
{50)
29

---

6-
6.
Witferedd
MisternOo
8A
Nidg
Forger Quality trrer Blower
L1Sparmn
Farget Qualty freer (Lower
115peran
Scrah
Sallh
Salth
OT
633
Quality
Retain
(Higher
Figure 9: Pareto frontiers for each method across hyperparameter settings in the Multi-Class Label Erasure task CIFAR-10 with Peotor .01, Pretain .001 and T -= 2. The left panel omits error bars for visual clarity.
Table 12:
Hyperparameter values tested for the results in Figure 10 running the Multi- Class Erasure experiment CIFAR- 10 with Pootor 001, Pretain .001 and T 5.
Hyperparameter
Sweep Values
[10-3,5x x 10 10-1, 1,000000" 1,-0,,,000 ,5x 10 10- 10 10-
AGA
110-3.102.11-1 201
Ams
10 10-2,10-1)
10,1,
TeD
[1,2,3}
Yros
0.2200.40..)
TPw
[]
7lpert
[50)
6.5
Mittermb
MistermDC CD
57
GD
57-
2.5
NCD
Fonget Quality Errer Dooee
Nidge
Fonger Qualnt Entor Lowwrr
LiSperse
Rirge
MPO
sall
Salth
0.2
0.1
0.0
0.7
0.7
3.5
5.7
0.2
0.4 0.5
3.7
Retain Quality (ltighe
Rebain Quality (lligher 1.
Figure 10: Pareto frontiers for each method across hyperparameter settings in the Multi-Class Label Erasure task on CIFAR-10 with Poolor -01, Pretain .001 and T 5. The left panel omits error bars for visual clarity.
30

---

Table 13: Hyperparameter values tested for the results in Figure running the Multi-Label Class Erasure experiment on CIFAR- 10 with Pootor
.001, Pretain .001 and T 10.
Hyperparameter
Sweep Values
110-2.10=4, 10 10 10
Aga
{10-9.1022.10-) 10-
Ang
[10-3,10-2.5 x 10 10-2, 2100
10.1.1.0.0000;
Teo
[0,1,2.5)
Treg
10.2,0.400.8) [1}
Thaj
npes
{50}
Aetrain
Ratrain
MinfermDG
MintormoD
57
5.7
MCP
2.5
660
Aldge
Rldge
Forgee Quality froo (Looee
Torge Qualtty Erner Cooe
2.5
Gench
MPO
MPO
saluh
0.2
611
61
00
6.1
0.2
0.5 Relain Quality (tiighe
0.
6.2
0.5
0.4 Retain Quality (tiiger 1.
0.5
Figure 11: Pareto frontiers for each method across hyperparameter settings in the Multi-Class Label Erasure task on CIFAR-10 10 with Peolor .001, Pretain bars for visual clarity.
= .001, and T' = 10. The left panel omits error
Table 14: Hyperparameter values tested for the results in Figure 12 running the Multi-Label Class Erasure experiment on CIFAR-10 with Peotor
.001, Pretain .01 and 7 10.
Hyperparameter
Sweep Values
{10-3 10_4, 1,005 10
Aga
(10-2,10-2,100
Are
(10-3;10-2,5) 10 10
10.00 (0,1,2,5)
Ten
Tice
(0.2,0.4.0.8) (1)
Thoj
{50)
31

---

6-
6.
Mintereodd
BA
Farget Qualhy freer (Lower 1.
Nidge
Forger Quality trrer (lower
115parm
L15peran
Salth
Salth
OT
01
Rebain
(Higher
Retain
Figure 12: Pareto frontiers for each method across hyperparameter settings in the Multi-Class Label Erasure task on CIFAR-10 with Pootor .001, Pretain 001, and 7 10. The left panel omits bars for visual clarity.
Table 15: Hyperparameter values tested for the results in Figure Erasure experiment on Tiny ImageNet with Poolor 00., Pretain
running the Multi-Labol Class .001 and T 10.
Hyperparameter
Sweep Values
{10 3 10 10 1,10 10-9)
Aga
1000000-11
Asg
{10-3, 110-5.102..50 100 20
10.1, (0,1,2)
TOD
Yree
00.2,0.4,0.8.00 0.9)
Throj
[]]
Pper
[50]
6.5
Miatermbc
MitferbD
57
GD
57-
2.8
NCD
Fonget Quality Ereer Dboee
Ridge
Fonger Qualit Entor Cower
Kirge
MPO
salth
Salth
0.2
0.1
0.3
2.0
0.2 Retain Quality (liiger
2.A
0.5
3.0
Rebain Quality Oligher 13
Figure 13: Pareto frontiers for each method across hyperparameter settings in the Multi-Clat Label Erasure task on Tiny ImageNet with Poolor -01, Pretain .001, and T 10. The left panel omits error bars for visual clarity.
32

---

Table 16: Hyperparameter values tested for the results in Figure running the Multi-Label Class
Erasure experiment on Tiny ImageNet with Pcolor = 01,, Pretain
01 and T 10.
Hyperparameter
Sweep Values
110-2,10=4, 1
Aga
{10-3,10"2.10 10-
Ang
[10-3,10-2.5 10-2,10-1)
10.1.1.010000] [0,1,2)
Teo
Theg
(0.2,0.400.8 [1}
Thaj
npet
{50}
Aatrain
Ratrain MinHormDG
MinfermoG
57
57
660
460
kldge
Rldge
Forgee Qualtty froo (Lowee
Targe Qualtty Errer Cooe
2.5
Gencb
MPO
MPO
salun
0.2
611
01
00
0.0
0.1
0.7
0.3
2.5
0.5
2.0
8.1
0.2
3.4
05
Retain Quality (ttigher
Retain Quality (tigher 1
Figure 14: Pareto frontiers for each method across hyperparameter settings in the Multi Class Label Erasure task on Tiny ImageNet with Peolor = .01, Pretain = .01. and T = 10. The left panel omits error bars for visual clarity.
F4 Representation Collapse
We again use the CIFAR-10 10 dataset with modified ResNet- architecture, assigning each of the 10 image classes a unique color. The retain set D, consists of images colored according to their assigned class color, while the forget set DD contains randomly colored images. The ground-truth unlearned model predicts class labels based solely on color, as color perfectly determines the label and is easier to learn than image content. In contrast, models trained on the full dataset D D, LDD must rely content features, since color is no longer fully predictive of the label. Thus, for unlcarning evaluation, we label heldout test images by color and assess unlearning via color-label accuracy, testing if the unlearning methods can collapse the original model into just a color classifier.
To construct D,, we randomly select 1 % of the training images per class and assign each a random color chosen from the remaining nine class colors. For the initial model, we first warm-stan by training for 20 epochs on gray images (a color not used in the class assignments) to encourage learning general image structure. then train for 50 epochs on the combined retain and forget sets, up-wed up-weighting the loss contribution of off-colored samples to promote fast color-invariant learning. We used the SGD optimizer with an initial learning rate of 3 x 10 weight decay of x 10 momentum of 0.9, batch size of 256, and multiplicative learning rate decay of 0.1 every 20 epochs. The ground-trute unlearned model is trained for 50 epochs on the retain set using the same optimizer settings. All training was performed
cluster of NVIDIA H200 GPUs.
We report results mean results over 5 trials in Table 17 which presents the same results Table 2 along with standard errors for each entry. We test each method under different constraints on the number unlearning epochs and percentage of accessible retain set samples. Specifically, for each random trial we randomly sample proportion of Pretain [0. 1 samples from D, which is accessible to each unlearning method. The "Retain %" column Table represents 100 x Pretain- Just as in the Multi-Clan Label Erasure experiment, during each unlearning epoch the algorithms iterate over
33

---

Table 17: Representation Collapse experiment results across constraints on the number of unlearning epochs and percentage of accessible retain set samples. Models are trained on colored images where color perfectly predicts the label in the retain set but not in the full dataset DD Reported values are mean test accuracies (%) on test images labeled by color (higher is better), averaged over 5 trials + standard error.
Retain & Epochs
Retrain
MiaNorm-OG
GD
GA
NGP
NGD
Ridge
1-Sparse
Serub
NPO
Saltin
79.1:4.5
49.1-6.1
2401:322
34,5544
459:34
1266:0.
209437
12,4503
37,343.7
40.6-177
294:55.5
0.1
10
95.511.1
7877-344
5521443
18.3254
13.7238
33012.
60013.7
23,0153
61.133
43.2-6.9
534179
15
96.3-088
03.2-1.3
78243.3
81.5e166
81,3+27
25.144.7
74.1439
44.67766
70345.
02.8-26
89.5-6.1
40.734
14.4447
583366
$29436
335+61
125500
478444
42.-441
42.54277
73613.0
92.412
634150
4355.99
68.114
batches from the forget set and sample a corresponding batch of the same size from the available retained data. The epoch ends once all forget batches have been processed. regardless of whether there are unused retain set samples remaining. Any unused retain batches are not discarded they will be sampled in subsequent epochs. Once all available retain set batches have been used least once, the sampling process begins again from the start of the available retain set samples.
Retrain achieves much higher color classification accuracy than any unlearning method, as image color is an easy feature to learn from scratch. This result is specific to this setup, as our prior experiments demonstrate that Retrain is not viable unlearning strategy in general. For this reason, we report the Retrain results separately in the leftmost column and highlight the MinNorm-OG results in bold, as they represent the best performance among the unlearning methods in each row.
For each constraint setting on the number of epochs and the Retain %, we tested different hyperpa-
rameters before reporting the best performance for each method. Tables 18 19 the set of hyperparameter values we tested for each row of Table 17
20
21
and 22 report
Table 18: Hyperparameter values considered for the Representation Collapse Experiment with T = 5 and Pretain = 0.001.
Hyperparameter
Values
[10 x 10 10
Aga
{10 10-2 10-1)
Aveg
[0.1, 0.2, 0.5, 0.9)
(0.1, 1.0, 10.0)
TeD
[1, 2, 3)
"Yeg
[0.2, 0.4, 0.83
Tho
[1]
Uper
{50}
Table 19: Hyperparameter values considered for the Representation Collapse Experiment with T = 10 and Pretain = 0.001.
Hyperparameter
Values
?
(5x 10 10-3
5
10
10 10-4)
Aaa
(10-3, 10-2. 10-1)
A
(0.01, 0.5, 0.9)
a
(0.1, 1.0, 10.0)
Teo
{3, 5, 7)
(0.2, 0.4, 0.8}
Timj
(1}
Uhpen
(50)
34

---

Table 20: Hyperparameter values considered for the Representation Collapse Experiment with
T = 15 and Pretain = 0.001.
Hyperparameter
Values
?
(5 10 10
5 10" 10
AGA
(10-3, 10 10
Aey
(0.01, 0.1, 0.9]
a
(0.1, 1.0, 10.0)
TGD
(3. 5, 73
{0.2, 0.4, 0.84
T Pro
(1}
(50)
Table 21: Hyperparameter values considered for the Representation Collapse Experiment with T =
and Pretain 0.01.
Hyperparameter
Values
(5 x 10 10-3,
5 10 10
AGA
(10-3, 10 10=1
Ave
{0.01, 0.1, 0.5, 0.9)
a
{0.1, 1.0, 10.0}
Tao
{1, 2, 3)
"fres
(0.2, 0.4, 0.8} (1}
Tro
ppe
(50)
Table 22: Hyperparameter values considered for the Representation Collapse Experiment with
= 10 and Pretain 0.01.
Hyperparameter
Values
"
(5x 10 3 10
10 10
AGA
{10-3, 10-2, 10
Arg
(0.01, 0.1, 0.5, 0.9)
(0.1, 1.0, 10.0)
TGD
(3, 5, 7)
"fie
(0.2, 0.4, 0.8) [1}
Too
Nyen
(50)
F55 Asset Information
We use the CIFAR-10 [3 and Tiny ImageNet [3]] datasets in our experiments. Both datasets are publicly available but do not specify an explicit license. Additionally, we use the ResNet-18 18 and ResNet-50 [32 architectures and pretrained weights from PyTorch's 's torchvision library, which are licensed under the BSD 3-Clause License.
35

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, our main claim centers on the failure prior definitions and algorithms for unlearning when applied in the overparameterized setting, which we show in Section 2 and the theoretical guarantees our new framework and algorithm, which we show in Section We clearly state the model classes we analyze (linear models, linear networks, and 2-layer perceptrons) and we provide specific guarantees for each. We lastly provide strong empirical results in Section []] supporting our claim that our proposed method can outperform prior methods in practice.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We explicitly state the model classes we analyze as well as the exact guarantees for our theoretical results in Section 4 When we describe our theoretical contributions in the Introduction, we mention the specific model classes and the corresponding results we achieve for each of them. Empirically, proposed method in Algorithm D relative to other gradient-descent-baal compare against. In the conclusion, mention future work includes extending our analysis to more complex model classes and performing experiments in broader domains at larger scale.
discuss the computational efficiency of our
methods which we
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
36

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: For each statement of theorems, propositions, and lemmas, explicitly state the assumptions we rely on. The proofs of all statements are the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We explain the experiments in the main body, and we include further discussion in the appendix. Also, all code for generating our empirical results is publicly released.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
37

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is publicly released and the datasets we use (Tiny ImageNet, CIFAR-10) are publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
http:////cc/cccuuuue//////eeeee CCoeee//ddSSSbeeeeee www.bbmmsssooPoooo asssonooiccyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We describe the experimental methodology for each setting in the main paper, while full experimental details are reported in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
38

---

7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For our experiments, either report means along with standard errors or medians with ranges of values across trials. For clarity, the main text presents only the central values (means or medians), while the appendix includes full results with corresponding uncertainty estimates.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report this in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics /tt.e//iiiits/////...........aaa httpr//s.c.ccpccccccsccccctteeea
Answer: [Yes]
Justification: This paper meets all ethical guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
39

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work helps develop theory and algorithms for unlearning in the overpa- rameterized setting, which has no direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not release any new data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
40

---

Answer: [Yes]
Justification: We cite the datasets we use in the main body, and include license information in the appendix.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We release code for reproducing our experiments which contains documenta-
tion.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not use human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
41

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs not used for any important, original, or core components of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non ntn-standard components.
Please refer to our LLM policy (https: /ttp://eeuipssp cc. Cc/Connferencee/22555///// for what should or should not be described.
42


Reviews:
[{"review_id": "4k4mm0kcqZ", "reviewer": "Reviewer_nR8A", "summary": "This paper addresses the machine unlearning problem, with a particular emphasis on overparameterized models. The authors formulate exact unlearning in this setting as a bilevel optimization problem, which not only minimizes loss optimality but also incorporates an additional complexity objective. Building on this novel definition, they propose a solution framework supported by rigorous theoretical analysis. Additionally, they develop an iterative algorithm, MinNorm-OG, and demonstrate its effectiveness through three comprehensive experiments with interpretable quantitative metrics. Overall, this is a solid work that effectively fills a gap in machine unlearning research.", "questions": "Q1: In Line 47, the authors state that their analysis “ … focus on settings where the loss is minimized by any interpolating model”.\n\nHow does the theoretical framework account for cases where the model converges to a local minimum while still satisfying the interpolation constraint?\n\nQ2: Following Q1, what are the theoretical and empirical consequences if the overparameterized model only reaches an approximate optimum but fails to achieve exact interpolation (e.g., due to optimization limitations or early stopping)? Since real-world training may not guarantee convergence to a perfect interpolating solution, how does this affect the proposed unlearning framework’s validity?\n\nQ3: Figure 1 shows an unusual trend: both the original model (red curve) and most baseline unlearning methods (except GA) exhibit a sharp initial peak in their fitting curves. What explains this consistent phenomenon across multiple methods? Why does MinNorm-OG uniquely avoid this issue? Could the authors provide empirical observations or theoretical insights to clarify the mechanism behind this improvement?", "limitations": "A deeper discussion on the assumption regarding the interpolating models would strengthen the work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Clarity\n- S1. The paper is well-organized and clearly written, making it accessible to readers.\n\nSignificance\n- S2. While machine unlearning has been extensively studied, this work tackles a novel and previously unexplored setting, overparameterized models. This unique focus makes it a valuable contribution to the machine unlearning community.\n\nOriginality\n- S3. The paper offers a fresh perspective by distinguishing between underparameterized and overparameterized regimes, thereby justifying the need for a new definition of unlearning tailored to the latter case.\n\nQuality\n- S4. The theoretical foundations are rigorous, and the experimental results in both the main manuscript and the appendices provide sufficient support for the paper’s claims.\n- W1. The major concern is the assumption regarding the interpolating models, whose practical applicability remains unclear. A deeper discussion on this aspect (see Q1-Q2) would strengthen the work.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer nR8A, thank you for highlighting the novelty of our analysis of unlearning within the overparameterized setting along with the rigor of our results. We address your questions and concerns below.\n\n**(Q1): In Line 47, the authors state that their analysis ``focus on settings where the loss is minimized by any interpolating model.” How does the theoretical framework account for cases where the model converges to a local minimum while still satisfying the interpolation constraint?**\n\n(A1): Thank you for raising this question about our theoretical framework and the relationship between data interpolation and loss minimization. For our analysis, we assume that the loss function has the property that any model that interpolates the data must be a global minimizer of the loss. For example, this is the case in $\\ell_p$-norm regression or 0-1 classification (Line 103). In these settings, it is not possible to recover an interpolating model which is not also a global loss minimizer. Because we work in the overparameterized setting, we know such interpolating models exist. Thus, using these assumptions we can rewrite Eqn. (2), which defines the ground truth unlearned model as the least complex loss minimizer, into Eqn. (4), which expresses the ground truth unlearned model as the least complex data interpolator. Our assumption about the loss structure allows this conversion without loss of generality.\n\nHowever, as you mention, there are cases where interpolation and loss minimization are not strictly equivalent. This notably arises in classification tasks, where the true goal is to minimize the expected 0-1 loss over the data, but since this is known to be NP-hard, we instead look to minimize a tractable surrogate like the cross-entropy loss or hinge loss. Even in these settings, our framework of aiming to solve Eqn. (4) through the relaxation in Eqn. (7) remains meaningful, as it **aims to preserve optimality with respect to the true target loss, rather than the training surrogate**. For example, in the classification setting using a surrogate loss like the ones mentioned above, Eqn. (4) searches for the least complex model which correctly predicts the label for each sample in the retain set, therefore minimizing the 0-1 loss over these samples, rather than searching for a model which minimizes the training surrogate. Although 0-1 loss is difficult to directly minimize, we use the fact that the original overparameterized model interpolates the training data and thus a minimizes the 0-1 loss on the retain set. To ensure the unlearned model preserves this property, we only require that the unlearned model's label predictions over the retain set match those of the original model. This condition is tractably approximated using the constraint relaxation in Eqn. (7) which enforces that the model predictions on the retain set remain unchanged up to first order error.\n\nTherefore, in these cases where surrogate losses are used to approximate a more difficult target loss like 0-1, our framework effectively aims to preserve optimality with respect to the true target loss on the retain set, rather than the surrogate, throughout unlearning. We also empirically validate this in our Multi-Class Label Erasure and Representation Collapse experiments, where we use cross-entropy loss as a surrogate for 0-1, and our method continues to perform strongly.\n\nWe appreciate the reviewer’s thoughtful observation and will revise the paper to clarify that even when interpolation does not imply global loss minimization, our framework seeks to preserve optimality with respect to the true target loss, not the training surrogate.\n\n**(Q2): What are the theoretical and empirical consequences if the overparameterized model only reaches an approximate optimum but fails to achieve exact interpolation (e.g., due to optimization limitations or early stopping)? Since real-world training may not guarantee convergence to a perfect interpolating solution, how does this affect the proposed unlearning framework’s validity?**\n\n(A2): This question raises an important point about the validity of our unlearning framework in practical settings. For our analysis, we make the common theoretical assumption that the original model is an exact minimizer of the training loss (Eqn. 1). However, as you point out, in practice we can only hope to achieve approximate minimization of the training objective. In this case, we cannot assume in Eqn. (4) that the original model exactly interpolates the retain set, but instead achieves approximate interpolation up to some error $\\epsilon$. In this practical setting, our framework of aiming to solve Eqn. (4) through the relaxation in Eqn. (7) then aims to find the least complex model which **preserves the same error $\\epsilon$ on the retain set**.\n\nTo illustrate this point, note that a key characteristic of our framework is to exploit the fact that the original model interpolates the retain set and is thus feasible for the problem in Eqn. (4). This allows us to replace the general interpolation constraint with the local linear approximation in Eqn. (7) which enforces that the unlearned model's predictions on the retain set remain unchanged relative to the original model up to first order error. Thus, when the original model only interpolates the retain set up to $\\epsilon$ error, our framework searches for the least complex model which interpolates the retain set up to the same $\\epsilon$ error. Since we assume the original model is overparameterized and trained to completion, this $\\epsilon$ should be small in practice so that our framework leads to a strong (approximate) candidate unlearning solution.\n\nWe note that this is the case in our Data Poisoning experiment. The initial trained model, shown in light red in Figure 1, does not perfectly fit each of the retain set or forget set samples. However, our framework still achieves strong performance.\n\n**(Q3): Figure 1 shows an unusual trend: both the original model (red curve) and most baseline unlearning methods (except GA) exhibit a sharp initial peak in their fitting curves. What explains this consistent phenomenon across multiple methods? Why does MinNorm-OG uniquely avoid this issue? Could the authors provide empirical observations or theoretical insights to clarify the mechanism behind this improvement?**\n\nThank you for mentioning this observation, as it sheds light on key characteristics of overparameterized learning and the failure of the other baseline unlearning methods within this setting. The sharp peak observed in the original model just before the first forget point (ordered left to right) arises because the original model is first trained to fit the entire dataset before unlearning. There is little separation in input space between this forget point and the preceding retain points, but a large difference in their corresponding output values. To interpolate the dataset, the model must sharply transition its predictions in this region, resulting in the observed peak.\n\nThe reason the other unlearning methods (besides GA) fail to remove this peak directly relates to the issue of vanishing loss gradients discussed in Section 2.2 (Theorem 1). Descent-based methods such as GD, NGD, and Ridge attempt to unlearn primarily by continuing to minimize the loss on the retain set. However, at the original model, the loss gradients are nearly zero, making it extremely slow, or even impossible, for these methods to remove unnecessary artifacts embedded in the initial model. In contrast, GA, which only ascends the loss on the forget set, successfully removes the peak, but entirely ignores the retain set, as the resulting model diverges significantly from the retained data. NGP, which optimizes a weighted combination of GA and GD objectives, also fails to remove the artifact in Figure 1. This is because Figure 1 shows results which correspond to the best hyperparameters we found for each method in terms of the unlearning error metric. For NGP, we found that the best performance occurred when the GA term was given a very small weight (Appendix F.2, Table 5), since increasing this weight caused the model to diverge and behave more like GA. Therefore, in this setting, NGP behaves similarly to GD and inherits its failure to produce a meaningful unlearning update.\n\nOur method avoids this issue because MinNorm-OG neither relies on loss gradients nor incorporates any form of loss ascent. Instead, it focuses on minimizing model complexity while approximately preserving optimality on the retain set. As a result, it is not affected by the vanishing gradient problem and is able to effectively remove unnecessary peaks and artifacts in the original model that are irrelevant to retain set interpolation.\n\nWe again thank the reviewer for this insightful observation, as it highlights a central claim of our paper: that loss-gradient-based unlearning methods are fundamentally ill-suited to the overparameterized regime, whereas minimizing model complexity subject to interpolation constraints offers a tractable and effective alternative.\n\n**Concluding Remark:**\n\nWe hope that the clarifications above adequately address your concerns, and we are committed to address any additional questions you may have during the discussion phase."}, {"review_id": "b7w5Vqgx0i", "reviewer": "Reviewer_Tqz5", "summary": "The paper focuses on unlearning in over-parameterized settings, where data is interpolated by the model – a setting where related work in unlearning is still scarce. It provides solid theoretical underpinnings for this setting, focusing on showing why gradient-based unlearning is vacuous once the model interpolates, and proposing a principled alternative (algorithm MinNorm-OG) alongside provable guarantees for linear and shallow-network model classes. The paper also provides empirical evaluations of the proposed method against several (rather simple) baselines.", "questions": "To improve my score(s) the above comments must be taken into account.", "limitations": "I was happy to see that the conclusions section is forthcoming about limitations. Recognizing additional limitations (such as simple/easy baselines, etc.) would help here.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe unlearning problem in overparameterized settings where data is interpolated is indeed an interesting (perhaps corner) case that deserves shedding light into.\n\n2.\tThe theoretical argumentation and development is very nicely done and informative – especially the discussion around single versus multiple existing solutions and the impact on unlearning beyond loss optimizations.\n\n3.\tThe effort to provide empirical results (substantiating the usefulness of the theoretical work) is noteworthy (albeit rather falling short of true practicality in real-world settings).\n\nWeaknesses:\n\nQuality: 3\n\nThe paper’s technical depth and rigour is high but the caveats below reduce the overall mark.\n\n1.\tThe paper’s claim that prior works (in the under-parameterized setting) define the solution as “any loss minimizer over the retained set’ is inaccurate. Loss functions are much more complex in SOTA methods (involving retain sets, forget sets, influence functions and noising ops on forget data, etc.). Hence, the paper’s motivation and problem formulation (looking as the only solution the minimizer on the retain data, D_r) should be re-examined. (By the way, line 113 should have D_r, not D). I urge the authors to explain this in more detail, as this (or I) may (have) be misunderstood.\n\n2.\tThe paper targets very simple network architectures – I realize this is an obvious criticism, but an important one, nonetheless.\n\n3.\tThe paper’s “from theory to practice argumentation” is rather overselling its contents – see the criticism on simplistic models used above. In addition, the datasets used are also rather simplistic.\n\n4.\tThe baselines used are rather rudimentary, perhaps with the exception of SCRUB and NGP. More recently many new unlearning methods have emerged as SOTA. I urge the authors to consider, for instance, algorithms like SalUn [Fan et al, ICLR24] and the framework RUM [Zhao et al, Neurips24]. \n\n5.\tSpeaking of RUM, which focuses on memorization and its affect on unlearning, it would be instructive (and extremely interesting IMHO) to investigate the parallels between interpolation and memorization.  In the RUM paper, for example,  authors found (empirically) a similar result (that unlearning becomes vacuous for low-memorized data). \n\n6.\tSpeaking of the SalUn method, which first identifies the “salient” weights and only updates them (instead of all parameters) during unlearning, a question relevant to this paper is how this affects the existence of multiple solutions in the overparameterized setting – are there fewer differences compared to strong solutions in the under-parameterized setting? \n\nClarity: 3.\n\n1.\tThe paper is nicely written, with formal/crisp language. Perhaps it is overloaded early on with symbols etc which may alienate not very-well-versed readers?\n\n\nSignificance:  2.\n\nOverall, the practical significance is rather limited – as argued in the quality section.\n\n\nOriginality: 4.\n\nOriginality is high – to my knowledge this is the first formal grounding of unlearning within an over-parameterized setting and the first principled solution for this.", "was_revised": true, "final_justification": "After reading all rebuttals and reviews, I fail to see the practicality of the setting studied in the paper. \nI especially find it very hard to believe that all training examples will be interpolated - to the best of my knowledge, this is never the case in real-life scenarios. So, I will keep my score at 3.", "rebuttal": "Dear Reviewer Tqz5, thank you for highlighting the depth and originality of our contributions. Thank you for appreciating the rigor of our arguments, and we are glad you found the writing clear. We address your questions below.\n\n**(Q1): The paper’s claim...misunderstood.**\n\n(A1): Thank you for the question. We believe there was a misunderstanding due to our word choice which we aim to clarify.\n\nWhen we say the unlearning solution has been previously defined as \"any loss minimizer over the retained set,\" we refer to the definition of the ideal, ground truth unlearned model as the best performing model on the retain set, meaning it is a minimizer of the *training loss* over the retain set. We distinguish the training loss from the *unlearning objectives*, which are the objective functions minimized by the different unlearning methods, which as you mention can involve more complicated structure.\n\nWe discuss this definition of the ideal unlearned model used in prior work, which defines it as any minimizer of the training loss over $D_r$, in order to highlight its limitations in the overparameterized setting. In this regime, the original model already interpolates the retain set and achieves zero training loss. As a result, the prior definition would classify the original model as a valid unlearned model, despite the fact that it completely memorizes $D_f$. This motivates our improved definition in Eqn. (2) of the ideal unlearned model as not just any minimizer to the training loss over the retain set, but the one with minimal model complexity.\n\nWe will update the paper’s phrasing to clearly distinguish the training loss from the unlearning objective. Thank you for pointing out the typo in Line 113, we will correct this in the revised paper. \n\n**(Q2): The paper targets...simplistic.**\n\nThe goal of our theory is to establish a principled framework with strong guarantees relating the tractability of solving the exact unlearning problem in Eqn. (4) using the relaxed surrogate proposed in Eqn. (7). To obtain rigorous guarantees, we focused on analyzable yet natural model classes. Extending the theoretical framework to handle deep non-linear networks remains an exciting and challenging direction for future work.\n\nWhile our experiments focus scales up to ResNet-18 on CIFAR-10, our goal is to enable clear, unambiguous unlearning evaluation. Our metrics precisely quantify whether MinNorm-OG, derived from our theoretical framework, consistently improves over baselines. We highlight clear failure cases of prior methods and show that MinNorm-OG performs reliably in practice.\n\nWe agree that scaling to larger models like LLMs is an important next step. However, building robust unlearning benchmarks at this scale with clear, meaningful metrics remains an open challenge [1–2]. Current LLM benchmarks [3–4] often rely on indirect metrics like membership inference or statistical divergence tests. In contrast, our controlled experiments allow for precise evaluation. For example, in the Multi-Class Label Erasure experiment, the retain and forget sets differ only in color distribution, as the retain set contains only gray images while the forget set contains red and green images. This allows us to precisely measure retain quality as classification accuracy on gray test images, and forget quality through the mean squared error between the model's predicted confidence that each input image is gray and the ideal value of 1, since the ground truth unlearned model always predicts input images to be gray with full confidence. These clear metrics enable meaningful comparison across methods and highlight the core contributions of our framework. \n\nIn our section titled “From Theory to Practice,” our goal is to show how our theoretical framework can be translated into an implementable algorithm that can be compared against baselines which perform iterative updates using access to a subset of the retain set. While this does not fully bridge the gap to extremely large-scale settings such as multi-billion-parameter LLMs, we believe it represents a concrete step toward making theoretically grounded unlearning methods applicable in empirical settings. If the reviewer feels that the current title is misleading, we are happy to revise it to something more appropriate, such as “Implementation Details.” \n\n**(Q3): The baselines...RUM.**\n\n(A3): Thank you for bringing up this additional method SalUN as well as the framework RUM. RUM is an interesting framework that proposes a meta-algorithm that applies different existing unlearning algorithms to subsets of the forget set based on a memorization score. We discuss the connection to RUM in our response (A4).\n\nTo address the suggestion to incorporate SalUn, we have added comparisons to SalUN as well as to two additional baselines: (i) retraining from scratch on the retain subset, and (ii) KL-Unif, the method proposed by Reviewer enfq, which minimizes the KL divergence between the model's output distribution on the forget set and the uniform distribution over classes. (See our response to Reviewer enfq for further discussion.) \n\nWe test on the Multi-Class Label Erasure experiment for the same settings shown in Figure 2. In this experiment, we create copies of either MNIST or CIFAR-10 colored gray, red, and green, where the retain set comprises only gray images while the forget set includes red and green samples. We train a model to predict both the image content class and the image color. To evaluate unlearning, we measure retain accuracy as the model’s accuracy on gray test images (higher is better), and forget error as the mean squared error between the model’s predicted probability that each input image is gray and the ideal value of 1 (lower is better). We sweep hyperparameters for each method and record the Pareto frontier of these two metrics. We include a table of Pareto optimal point(s) for each method. \"Original Model\" denotes the performance of the initial model before any unlearning. \n\n**MNIST**\n\n|Method      |Ret. Acc(%)↑|Forget Err.↓|\n|------------|----------|-------|\n|Original    |98.6      |0.67    |\n|SalUn       |98.3      |0.42   |\n|KL-Unif     |98.5      |0.27   |\n|Retrain     |66.1      |0.00   |\n|MinNorm-OG  |97.0      |0.03   |\n\n**CIFAR-10**\n\n|Method     |Ret. Acc(%)↑|Forget Err.↓|\n|-----------|----------|-------|\n|Original   |79.0      |0.67    |\n|SalUn      |63.0      |0.43   |\n|           |49.6      |0.32   |\n|KL-Unif    |58.3      |0.47   |\n|           |18.2      |0.21   |\n|Retrain    |0.10      |0.00   |\n|MinNorm-OG |67.5      |0.48   |\n|           |60.1      |0.20   |\n|           |53.0      |0.11   |\n\nOn MNIST, SalUn slightly reduces forget error with minimal impact on retain accuracy but quickly plateaus, never achieving forget error below 0.42. MinNorm-OG, by contrast, approaches the ideal of 100% retain accuracy and 0.0 forget error. A similar pattern holds on CIFAR-10, where SalUn trades large drops in retain accuracy for modest forget gains, while MinNorm-OG achieves better forget error with far less retain loss. We will add this comparison to the paper.\n\nIn our responses to Reviewers enfq and ditX, we include runtime-constrained experiments across all methods. SalUn consistently showed a poor tradeoff between retain and forget metrics and was relatively costly due to its initial computation of the \"salient weights\". See our response to Reviewer ditX for details.\n\nSalUn may struggle to unlearn for two main reasons. First, with random labels on the forget set, SalUn still trains with non-gray color labels, making it hard to lower forget error. Second, in the overparameterized regime, SalUn freezes parameters based on loss gradients at the original model, which may be near zero and mostly noise, making its salient weight selection unreliable.\n\n**(Q4): RUM...**\n\n(A4): Thank you for bringing up RUM and the relationship between memorization and interpolation. Given a randomized learning algorithm $A(D)$ that returns a distribution over models $f$, the memorization score of a sample $(x_i, y_i)$ is defined as the difference of:\n\n(i) the probability that a model $f \\sim A(D)$ correctly classifies $x_i$ and\n(ii) the probability that a model $f \\sim A(D \\setminus {i})$ correctly classifies $x_i$.\n\nThe memorization score from RUM measures how much a sample's inclusion in training improves the model's prediction. In the overparameterized regime, we assume the model class is rich enough to interpolate the entire dataset, so the first term in the memorization score is essentially 1 for every sample. This allows for large memorization scores under overparameterization. We will include a discussion of this relationship in the revised paper.\n\n**(Q5): Speaking SalUn method...**\n\n(A5): SalUn restricts updates to a subset of model parameters so it can reduce the space of minimizers to its unlearning objective. However, we emphasize that the multiple minimizers of the *training loss* under overparameterization was what motivated our definition of unlearning Section 2.1, not the minimizers of the *unlearning objective*. \n\n**Concluding Remark:**\n\nWe hope that the clarifications and additional results above adequately address your concerns. If so, we kindly request you to consider revising your score. We are committed to address any additional points you may have during the discussion phase.\n\nAs a side note, we also noticed that the originality score mentioned in the text of your review was a 4, while the official score was recorded as a 3. If the higher score was your intended assessment, we would appreciate your consideration in updating it.\n\n[1] Feng, Z., et al. \"Existing Large Language Model Unlearning Evaluations Are Inconclusive.\"\n\n[2] Hu, S., et al. \"BLUR: A Benchmark for LLM Unlearning Robust to Forget-Retain Overlap.\"\n\n[3] Shi, W., et al. ``MUSE: Machine Unlearning Six-Way Evaluation for Language Models.\"\n\n[4] Maini, P., et al. ``TOFU: A Task of Fictitious Unlearning for LLMs.\""}, {"review_id": "qXRSkr1GtG", "reviewer": "Reviewer_enfq", "summary": "The paper addresses the new problem of machine unlearning in overparameterized models, where more than one solutions can fit all training data perfectly. The authors argue that traditional unlearning definitions are insufficient in such settings and proposes a new formulation that accounts for this non-uniqueness. The key contribution is a formal approach to define and achieve unlearning by considering the geometry of the solution space, rather than focusing solely on model outputs or loss values. The paper also introduces an unlearning algorithm aligned with this new definition and demonstrates their effectiveness through theoretical justification and empirical results.", "questions": "See weaknesses", "limitations": "yes", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper presents a novel perspective on machine unlearning in overparameterized models, where multiple solutions can achieve zero training loss. The authors make a compelling case for redefining unlearning under this regime and clearly articulate the motivation and implications. \n- The paper is generally well-written, with clear exposition and sound mathematical formalism, making it accessible and rigorous. \n\n\nWeaknesses: \n1. The overparameterized setup considered in the paper aligns closely with the assumptions of the Neural Tangent Kernel (NTK) regime, where solutions that interpolate training data lie near the initialization. Prior unlearning work leveraging NTK (e.g., [1]) should be acknowledged and discussed to clarify the novelty and positioning of the current approach. \n\n2. The practical benefit of the proposed unlearning approach is unclear without a runtime comparison to retraining from scratch, particularly in the overparameterized regime where training converges quickly. Since the proposed method relies on gradients over the retain set, the computational savings may be marginal unless the retain set is substantially smaller. \n\n3. The authors should clarify whether unlearning Algorithm 1 with a subset of the retain set is reasonable.\nIf so, the authors should compare it with retrain with the subset of the retain set. \n\n4. The motivation for unlearning in overparameterized models would be stronger if grounded in realistic scenarios, especially those involving large models (e.g., LLMs) and massive datasets where retraining is costly. It remains unclear whether the setting proposed in the paper addresses such high-stakes unlearning use cases. \n\n5. The paper focuses primarily on gradient ascent-based methods, but there are other possible approaches to address unlearning in overparameterized models. For instance, minimizing the KL divergence between the model's output logits and a uniform distribution over the label (i.e., minimizing $D_{KL}(f(x) || u)$ for $x\\in D_f$) could serve as a simple and effective alternative. Discussion of such methods would provide a broader context for the proposed solution. \n\n6. Typo: Missing period at the end of line 167. \n\n7. Clarification needed: The use of the delta function in Equations (9) and (12) is unclear. Further justification is necessary. \n\n[1] Golatkar, Aditya, Alessandro Achille, and Stefano Soatto. \"Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations.\" ECCV 2020.", "was_revised": true, "final_justification": "I think the question of \"what unlearning means in the overparameterized regime\" is an excellent one, and the authors provide an interesting and thoughtful answer. However, I remain skeptical about the practical applicability of the proposed method. The core motivation for unlearning lies in its practicality (otherwise, one could simply retrain the model to achieve full removal guarantees). Unlearning becomes relevant when dealing with large-scale models for which retraining is prohibitively expensive. In this context, I am not convinced that such large models can be highly overparameterized in the way assumed by the authors, nor that the proposed method would be applicable or effective in such settings. Therefore, I am maintaining my original score.", "rebuttal": "Dear Reviewer enfq, thank you for highlighting the novelty of our analysis and the rigor of our arguments. We answer your questions below.\n\n**(Q1): ... NTK regime should be acknowledged...**\n\n(A1): Thank you for highlighting Golatkar et al. which studies unlearning for fine-tuning a pretrained network. Since the pretrained network is often overparameterized for the fine-tuning task, they assume fine-tuning causes only a small change in weights. Thus, both the original model and the ideal unlearned model (fine-tuned only on $D_r$) remain close to the pretrained initialization. This enables the use of NTK theory, which approximates the result of fine-tuning by linearizing the network around the pretrained weights. We clarify the distinction to our approach below.\n\nWe consider the general problem of unlearning under overparameterization, not the specific problem of unlearning for fine-tuning. We make no assumption about the magnitude of the weight updates, as unlearning in general may require substantial weight updates which are not well captured by the NTK approximation.\n\nAlthough our framework applies a linearization, it is fundamentally different from the linearization used in the NTK regime. We apply a linearization to handle the complex interpolation constraint in Eqn. (4) which defines the ideal unlearning solution as the minimum-complexity interpolator of the retain set. Since the original model is such an interpolator, we approximate the constraint by its linearization around the original weights. This leads to the tractable objective in Eqn. (7) which approximates the exact unlearning problem in Eqn. (4). \n\nFurther, our practical method MinNorm-OG accounts for unlearning settings which require large weight updates by iteratively solving a version of Eqn. (7) and applying loss descent steps to restore feasibility for Eqn. (4), since in general the linearization of Eqn. (7) is only locally accurate. Unlike the NTK approach, our method handles large weight updates explicitly.\n\nWe will revise the paper to include a discussion of this related work.\n\n**(Q2) Unlearning with retain set...**\n\n(A2) In practice, empirical unlearning methods typically assume some access to retain set samples. All baseline methods we compare against rely on this access, except for GA which performs very poorly. Without access to the retain set, developing a robust and general unlearning algorithm becomes extremely challenging.\n\nSpecific settings, such as unlearning within our framework using the basic model classes considered Section 3 or unlearning for fine-tuning using NTK theory, make unlearning feasible with access only to model gradients. However, these rely on strong assumptions which fail to hold in general.\n\n**(Q3) Compare to retrain... minimizing the KL divergence to uniform...**\n\n(A3) We define your proposed method KL-Unif which minimizes a weighted sum of the retain set loss and the KL divergence between the model’s output and the uniform class distribution on the forget set.\n\n**We include comparisons to retraining from scratch on the accessible subset of the retain set and KL-Unif**. We run these methods on the Multi-Class Label Erasure experiment for the same settings shown in Figure 2. Due to space constraints we present the results in our response (A3) to Reviewer tqz5 above.\n\nRetraining struggles to achieve strong retain accuracy with limited epochs but always attains 0 forget error. MinNorm-OG achieves near-zero forget error with much better retain accuracy. On MNIST KL-Unif maintains decent accuracy at moderate forget error but cannot reduce forget error further, but it performs poorly on CIFAR-10, failing to lower forget error without harming retain accuracy. MinNorm-OG consistently offers better tradeoffs on both datasets.\n\nWe will include these comparisons in the updated paper.\n\n**(Q4) Runtime comparison...**\n\n(A4) We compare mean runtimes over 5 epochs in the Multi-Class Label Erasure experiment. For MinNorm-OG, we report the runtime for the hyperparameters that gave the best performance in Figure 2. For other methods see our response (A2) to Reviewer ditX.\n\n **Mean Runtime (ms)**\n\n|Method      |MNIST |CIFAR-10|\n|------------|------|--------|\n|Retrain     |83.71 |120.33  |\n|MinNorm-OG  |574.49|525.78  |\n|KL-Unif     |114.70|274.02  |\n\nRetraining is one of the cheapest methods, while KL-Unif is somewhat more expensive as the loss function is more involved. Lastly, MinNorm-OG incurs a relatively large per-epoch cost as expected. Due to this variation, we also compare the performance of each method under a fixed wall-clock runtime budget. For the full table see our response (A2) to Reviewer ditX below.\n\n**Multi-Class Label Erasure Results on MNIST, 200 ms** \n\n\n|Method       |Ret. Acc. (%)↑|Forget Err.↓|\n|-------------|----------|--------|\n|Original     |98.6      |.67     |\n|Retrain      |84.0      |.00     |\n|MinNorm-OG   |94.1      |.18     |\n|             |89.1      |.10     |\n|KL-Unif      |95.0      |.37     |\n\n\nOn MNIST, retraining quickly learns a decent classifier with limited data. MinNorm-OG improves retain quality (89.1% vs. 84% accuracy) with a small increase in forget error (0.1 vs. 0, lower is better). KL-Unif fails to achieve low forget error, while MinNorm-OG offers a better tradeoff, reducing forget error while preserving retain accuracy.\n\n**Multi-Class Label Erasure Results on CIFAR-10, 700 ms** \n\n|Method      |Ret. Acc. (%)↑|Forget Err.↓|\n|------------|----------|-------|\n|Original    |79.0      |.67    |\n|Retrain     |14.0      |.00    |\n|MinNorm-OG  |79.4      |.66    |\n|            |74.8      |.55    |\n|            |62.3      |.17    |\n|            |61.1      |.07    |\n|KL-Unif     |73.3      |.54    |\n|            |61.2      |.30    |\n|            |18.8      |.00    |\n\nOn CIFAR-10, retraining fails as the dataset cannot be learned quickly from a small subset. MinNorm-OG achieves 61.1% accuracy with a low forget error of 0.07. Additionally, MinNorm-OG outperforms KL-Unif at intermediate points, reaching 62.3% retain accuracy at 0.17 forget error, while KL-Unif achieves 61.2% accuracy with a worse 0.30 forget error.\n\nKL-Unif may struggle to reduce forget error because its KL term forces the forget set predictions toward a uniform distribution. This may work when the retain and forget sets are completely unrelated, but in realistic settings with shared structure, like our experiments, it struggles to recover the correct unlearned model.\n\n**(Q5): The motivation...use cases.**\n\n(A5): Thank you for raising this point. While our experiments focus on model and dataset sizes up to ResNet-18 on CIFAR-10, our primary goal is to present a set of interpretable experiments supported by unambiguous metrics. These metrics precisely quantify whether our proposed algorithm MinNorm-OG, developed as an extension of our theoretical framework, offers consistent improvements over existing baseline methods. We show clear failure cases for existing methods and demonstrate the stronger performance of MinNorm-OG, supporting the practical relevance of our framework and beyond the settings where we can provide formal guarantees.\n\nWe agree that scaling evaluation to larger models, especially LLMs, is a natural and important next step. However, developing robust large-scale unlearning benchmarks with clear evaluation metrics remains an active research area [1–2]. Existing benchmarks [3–4] often use ambiguous metrics such as membership inference attacks and statistical divergence tests. In contrast, our experiments provide unambiguous evaluations. For example, in the Multi-Class Label Erasure experiment, the retain and forget sets differ only in color distribution, as the retain set contains only gray images while the forget set contains red and green images. This allows us to precisely measure retain quality as classification accuracy on gray test images, and forget quality through the mean squared error between the model's predicted confidence that each input image is gray and the ideal value of 1, since the ground truth unlearned model always predicts input images to be gray with full confidence. These clear metrics enable meaningful comparison across methods and highlight the core contributions of our framework.\n\n**(Q6): The use of the delta function...**\n\n(A6): To derive our surrogate objective in Eqn. (7) for the exact unlearning problem in Eqn. (4), we relax the interpolation constraint in Eqn. (4) via a linearization around the original model. We then introduce a drift regularization term, denoted $\\hat{R}$, to control the error introduced by this linearization for different basic model classes. Thus, we minimize $\\tilde{R}$ defined as $R + \\hat{R}$. In Eqns. (9) and (12), we specify this $\\tilde{R}$ function for (i) linear networks where $R$ measures predictor norm and (ii) 2-layer perceptrons where $R$ measures network width. In both cases, the delta functions appear as the definition of the regularizer $\\hat{R}$ within this full objective $\\tilde{R}$. $\\hat{R}$ ensures that the minimizing Eqn. (7) over the relaxed constraints either recovers the exact solution to Eqn. (4), or returns a feasible interpolating model with tightly controlled complexity. Without $\\hat{R}$, minimizing only $R$ over the linearized constraints would fail to unlearn, as shown in Appendix D.4.1.\n\nWe will correct the typo Line 167.\n\n**Concluding Remark:**\n\nWe hope that our responses and additional results have adequately addressed your concerns. If so, we kindly request you to consider revising your score. We are committed to address any additional points you may have during the discussion phase.\n\n[1] Feng, Z., et al. \"Existing Large Language Model Unlearning Evaluations Are Inconclusive.\"\n\n[2] Hu, S., et al. \"BLUR: A Benchmark for LLM Unlearning Robust to Forget-Retain Overlap.\"\n\n[3] Shi, W., et al. ``MUSE: Machine Unlearning Six-Way Evaluation for Language Models.\"\n\n[4] Maini, P., et al. ``TOFU: A Task of Fictitious Unlearning for LLMs.\""}, {"review_id": "HXXWHweEjr", "reviewer": "Reviewer_ditX", "summary": "The paper considers the problem of unlearning for overparameterized models. In such cases, even the definition of what we mean by an unlearned model is unclear since the original model may interpolate the retain set data and hence trivially minimize the loss. To resolve this, the paper defines the ideal unlearning solution as the one which minimizes some notion of complexity (e.g. parameter norm) while interpolating the retain set. \n\nTo approximately find such a solution, the paper proposes an algorithm that roughly does the following: find an update to the original parameters that minimize the complexity measure, while ensuring that the update is small and is orthogonal to gradients of retain set points. The orthogonality condition is a first order relaxation of the interpolation condition and the update being small ensures that the first order relaxation is accurate. The theory results that follow establish that the approximate solution hence found is reasonable: it is exact in the case of a linear model, and for a 2-layer neural network, it finds an interpolating solution while keeping the number of active neurons small.\n\nThe paper then proposes a more practically applicable version of the algorithm focusing on $\\ell_2$ norm as the complexity measure. The algorithm roughly does the following: (i) Do (mini-batch) gradient descent on the retain set, (ii) Every once in a while, update the parameter to minimize its norm, while ensuring that the update is small and is orthogonal to retain set gradients. For efficiency, this update is done using a small subset of retain set minibatch. \n\nFinally, the paper designs several clever unlearning evals (altered versions of MNIST/CIFAR datasets) and shows that the proposed method performs better than many existing baselines.", "questions": "See the strengths and weaknesses discussion.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is nicely written and was a fun read.\n\n- The proposed method is natural and easy to integrate in existing SGD pipelines (at least in terms of implementation), and seems to beat many existing methods.\n\n- I liked the evals which could be of independent interest. While they may not be sufficient to show that an unlearning method is good, they are certainly necessary and easier to compute compared to some of the existing evals in the unlearning literature.\n\n\n**Weaknesses**\n\n- The most exciting part of the paper for me was that the proposed method is very simple, and beats many existing methods. However, I don't fully understand why. The theory seems a bit disconnected from the actual algorithm used and doesn't provide good justification of why the method works so well. In particular, it was unclear why the method outperforms plain $\\ell_2$ regularization. It seems the proposed method is essentially doing $\\ell_2$ regularization subject to the constraint that the effect of this regularization remains in space orthogonal to retain set minibatch subset. But if this subset is small, then one still ends up shrinking the parameters in the rest of the subspace spanned by the retain set but not captured by this subset. In that sense, it doesn't seem that different from pain $\\ell_2$ regularization. It would be good if the authors can clarify this in detail.\n\n- The evaluation needs some more work to make them convincing:\n(i) The current cost comparison is in terms of number of epochs. But since the per epoch cost differs across methods (e.g. there is expensive orthogonalization in the proposed method), it would be good to compare the wall clock runtime as well.\n(ii) While the proposed evals are nice and seem like a necessary test any proposed unlearning method should pass, the paper would become much stronger if it could compare the method on existing evaluation criterion as well such as KLoM or ULIRA (see [1] for a discussion). Having said that, these evaluations are expensive and it is understandable if a paper omits them.\n\n[1] Georgiev, Kristian, et al. \"Attribute-to-delete: Machine unlearning via datamodel matching.\" arXiv preprint arXiv:2410.23232 (2024).", "was_revised": true, "final_justification": "I thank the authors for their detailed response. I am increasing the score to borderline accept.\n\nThe proposed method is definitely very interesting and well-motivated. However, in the wall-clock time comparison, it seems to do similar to retraining from scratch in one case and running GD in another case (both are standard baselines). It is possible that with optimized implementations, it can outperform these standard baselines. However, without clear evidence, I feel hesitant to recommend a clear acceptance. It would make the paper much stonger if the authors could demonstrate the supriority using optimized implementations.\n\nAlso, I think the comparison with the ridge baseline is worth building on more. It seems somewhat surprising to me that constraining the updates to be orthogonal to retain set minibatch can be significantly more effective than plain ridge baseline, given that the mini-batch sizes are typically very small compared to the retain set size. However, the justification authors gave for this definietly seems plausible. While this is nor strictly necessary for accepatance, I think the paper will become much stronger (maybe in the future version) with some more analysis and intuitions comparing the two methods.", "rebuttal": "Dear Reviewer ditX, we are glad to see you enjoyed reading the paper. We answer your remaining questions below.\n\n**(Q1): The most exciting part...**\n\n(A1): Thank you for this question on plain L2 regularization, which we refer to as Ridge. We note that Ridge is not a previously proposed unlearning method; rather, we include specifically it as a baseline to contrast our proposed algorithm.\n\nAs you mention, the Ridge update modifies the model parameters by descending the loss over a mini-batch while simultaneously shrinking the parameter vector towards the origin. In contrast, MinNorm-OG alternates between two decoupled steps: (i) descending the loss, and (ii) shrinking the parameter norm only in the subspace orthogonal to the gradient of the model's output over the retain samples. This orthogonal projection ensures that the complexity reduction step does not interfere with the model performance on the retain set. Even though MinNorm-OG approximates the true orthogonal subspace using a random subset of each batch, this is often sufficient in practice for preserving the critical directions for retain-set performance.\n\nIn contrast, the Ridge shrinks the parameter vector in directions which can interfere with the loss minimization over the retain set and lead to suboptimal updates. While Ridge can eventually converge to a decent solution, it requires more epochs and greater access to the retain set. In Table 1 (Data Poisoning), Ridge performance improves as the number of epochs increases (the last column reflects Ridge -- the column header ``RegL2” is a typo that will be corrected.) Similarly, in Table 2 (Representation Collapse), Ridge performs better as both retain set access and epochs increase. Thus, Ridge is a reasonable, yet suboptimal, unlearning method as it is not specifically tailored to the bi-level formulation of unlearning in Eqn. (4).\n\nWe will make sure to include this discussion in the revised version of the paper.\n\n**(Q2): The evaluation...if a paper omits them.**\n\n(A2) \n\n(i): Regarding our experimental constraint, we note that it is standard in prior work [1-3] to fix the number of epochs across methods for each experiment. Further, it is increasingly common to evaluate optimization algorithms based on the number of samples processed, especially for LLMs where efficiency is often measured per token. That said, we agree that adding runtime comparisons would strengthen our results.\n\nWe use the Multi-Class Label Erasure experiment for the runtime analysis as it represents our largest scale experiment with the most fine-grained evaluation metrics. We create copies of either MNIST or CIFAR-10 colored gray, red, and green, where the retain set comprises only gray images while the forget set includes red and green samples. We train a model to predict both the image content class and the image color. To evaluate unlearning, we measure retain accuracy as the model’s accuracy on gray test images (higher is better), and forget error as the mean squared error between the model’s predicted probability that each input image is gray and the ideal value of 1 (lower is better).\n\nWe first present the run-times of each method for unlearning with 5 epochs in the same setting as Figure 2. For MinNorm-OG, we present the runtime using the hyperparameters which result in the best performance for the fixed epoch constraint.\n\n**Mean Runtime (ms)**\n|Method      |MNIST |CIFAR-10|\n|------------|------|--------|\n|Retrain     |83.71 |120.33  |\n|GD          |81.94 |112.97  |\n|GA          |87.19 |256.11  |\n|NGD         |84.66 |115.84  |\n|NGP         |116.63|273.85  |\n|Scrub       |98.80 |176.28  |\n|NPO         |100.58|334.79  |\n|Ridge       |82.39 |116.85  |\n|MinNorm-OG  |574.49|525.78  |\n|SalUn       |270.62|784.31  |\n|KL-Unif     |114.70|274.02  |\n\nMinNorm-OG incurs a relatively large per-epoch cost relative to the other methods as expected. Note that SalUn, Retrain, and KL-Unif were added to address the questions of Reviewers Tqz5 and enfq.\n\nWe run additional experiments for unlearning given a fixed runtime budget rather than a fixed epoch budget. We sweep hyperparameters for each unlearning method and record sets of Pareto optimal points for each method. When possible, we select 3-4 points per method. We format the best performing methods in bold. ``Original Model\" denotes the initial model before any unlearning. The range of the retain accuracies is [0,1] as it computes accuracy on gray test images, while the forget error ranges from .67 (the worst possible value when there are 3 color classes) to 0 (perfect forgetting).\n\n**Multi-Class Label Erasure Results on MNIST, 200 ms**\n|Method       |Ret. Acc. (%)↑|Forget Err.↓|\n|-------------|----------|--------|\n|Original     |98.6      |.67     |\n|**Retrain**      |84.0      |.00     |\n|GD           |95.6      |.28     |\n|GA           |40.0      |.48     |\n|GA           |10.3      |.00     |\n|NGD          |98.6      |.67     |\n|**NGP**          |95.1      |.25     |\n|             |84.1      |.01     |\n|Scrub        |95.1      |.39     |\n|             |94.2      |.22     |\n|NPO          |50.2      |.44     |\n|             |18.3      |0.0     |\n|Ridge        |95.6      |.27     |\n|**MinNorm-OG**   |94.1      |.18     |\n|             |89.1      |.10     |\n|SalUn        |96.8      |.58     |\n|KL-Unif      |95.0      |.37     |\n\n**Multi-Class Label Erasure Results on CIFAR-10, 700 ms**\n\n|Method      |Ret. Acc. (%)↑|Forget Err.↓|\n|------------|----------|-------|\n|Original    |79.0      |.67    |\n|Retrain     |14.0      |.00    |\n|**GD**          |72.5      |.55    |\n|            |61.0      |.05    |\n|            |23.6      |.00    |\n|GA          |65.0      |.48    |\n|            |10.1      |.45    |\n|NGD         |73.0      |.65    |\n|            |57.8      |.45    |\n|NGP         |73.4      |.54    |\n|            |61.8      |.21    |\n|            |18.0      |.00    |\n|Scrub       |73.0      |.64    |\n|            |61.0      |.10    |\n|            |23.9      |.04    |\n|NPO         |67.0      |.55    |\n|            |20.2      |.36    |\n|**Ridge**       |72.6      |.55    |\n|            |61.4      |.06    |\n|            |23.6      |.00    |\n|**MinNorm-OG**  |79.4      |.66    |\n|            |74.8      |.55    |\n|            |62.3      |.17    |\n|            |61.1      |.07    |\n|SalUn       |73.0      |.55    |\n|            |65.1      |.37    |\n|            |51.1      |.31    |\n|            |23.6      |.02    |\n|KL-Unif     |73.3      |.54    |\n|            |61.2      |.30    |\n|            |18.8      |.00    |\n\n\nRetrain, NGP, and MinNorm-OG perform best on MNIST. Retraining from scratch on the accessible subset of the retain set can achieve some success since MNIST is not as complex as CIFAR-10. For CIFAR-10, GD, Ridge, and MinNorm-OG perform best. In both experiments, methods with cheaper per-epoch updates perform relatively better under a fixed time budget, as they complete more optimization cycles. Despite this, MinNorm-OG remains a strong performer even though we have not optimized its implementation. Further improvements are likely possible through:\n- Caching gradients between loss descent and projection steps\n- Using lower-level GPU libraries (e.g., cuSOLVER) instead of `torch.linalg.qr`\n\n(ii) Regarding evaluation metrics: while general-purpose metrics like KLoM and ULIRA are valid, we design task-specific metrics tailored to each experiment. This improves clarity and interpretability, allowing for a more precise understanding of unlearning performance. We agree that the paper would benefit from additional discussion connecting our metrics to existing criteria, which we will include in the revised version.\n\nAs noted by Reviewer oxow, our metrics can be seen as direct analogs to prior work [4]. While our metrics are not exact analogs to KLoM for example, they share the same underlying motivation but offer more refined, task-specific insights.\n\nKLoM computes the KL divergence between a model’s predicted class distribution and that of models sampled from a “safe” distribution (e.g., retrained from scratch). In the Multi-Class Label Erasure task, the ground truth unlearned models always classify gray inputs correctly and predict all input images as gray with probability 1. This enables direct evaluation via (i) accuracy on gray test images and (ii) squared error between the predicted gray probability and 1 on colored test inputs. These metrics quantify distributional distance to the true unlearned model in a task-aligned way, rather than relying on general-purpose KL divergence. Similarly, in the Representation Collapse experiment, the ground-truth unlearned models base predictions on color, not content, allowing evaluation via color-based accuracy. These metrics provide a more grounded, data-driven view of distributional change. We will include this discussion of the relationship between our evaluation methods to existing criteria such as KLoM in the updated paper.\n\nWe appreciate the reviewer’s recognition that our metrics are necessary tests unlearning methods should pass. We note that many baseline algorithms struggle even in simple settings like the Data Poisoning experiment. We present these results not to diminish prior work but to motivate the value of our analysis and its practical insights.\n\n**Concluding Remark:**\n\nWe hope that our clarifications and additional results have adequately addressed your concerns. If so, we kindly request you to consider revising your score. We are happy to address any additional questions you may have during the discussion phase.\n\n[1] Maini, P., et al. ``TOFU: A Task of Fictitious Unlearning for LLMs.\"\n\n[2] Shi, W., et al. ``MUSE: Machine Unlearning Six-Way Evaluation for Language Models.\"\n\n[3] Zhang, R., et al. \"Negative Preference Optimization: From Catastrophic Collapse to Effective Unlearning.\"\n\n[4] Goel, Shashwat, et al. \"Corrective Machine Unlearning.\""}, {"review_id": "1guZHuKv7E", "reviewer": "Reviewer_oxow", "summary": "The authors present a forget set free unlearning method for overparameterized settings and provide guarantees for a relaxed problem formulation. The theoretical contributions are backed up with three new benchmarks.", "questions": "- Why did the authors leave out any established benchmarks/metrics? Additional results here would make me increase my score on this otherwise excellent paper", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "- Clarity and Quality: The paper is well written with clear notation and easy to interpret visualizations.\n- Originality: The work is original with theoretical insights and method contributions.\n- Significance: This work provides significant insights for future work to build upon.\n\n*Strengths:*\n- Strong theoretical insights/evaluations\n- MinNorm-OG is intuitive, well explained, and the reasons for the design decisions are well motivated\n- The new benchmarks are easy to interpret and clearly show shortcomings in existing methods\n\n*Weaknesses:*\n- Results on established metrics such as MIA for privacy are missing. The authors rightfully argue that established metrics can be opaque but knowing how this new method stacks up to established methods on this benchmark would be of interest. Overall, the authors did not benchmark on any established benchmarks with all three experimental benchmarks created for this paper. While I trust that the method is strong and will hold up, it would avoid any doubts of cherry picked benchmarks by including standard unlearning benchmarks too. If the authors prefer to stay away from MIA etc., other works such as Goel et al. “Corrective Unlearning” perform poison unlearning too with an objective measure of accuracy.\n- The work only investigates shallow networks (acknowledged by the authors). Seeing how this method performs on larger models and different architectures would be of interest (e.g. transformers)\n\nNitpick: The color red in Figure 1 is hard to see and likely vanishes when printed.", "was_revised": true, "final_justification": "I remain with an accept score based on the points listed in strengths. The authors provided answers to all of my clarifying questions, which did not raise any additional significant concerns and explained why they left out certain aspects, such as MIA scores and explained why. Machine unlearning is still a new field and this work adds new nuggets of knowledge. Especially simple clearly interpretable experiments such as the ones shown in Fig. 1 are helpful in a field that still figures out how to actually measure unlearning performance (the MIA ULIRA etc struggle.)", "rebuttal": "Dear Reviewer oxow, thank you for recognizing the originality, impact, and clarity of our work. We are happy to address your remaining questions below.\n\n**(Q1): Results on established metrics such as MIA for privacy are missing. The authors rightfully argue that established metrics can be opaque but knowing how this new method stacks up to established methods on this benchmark would be of interest. Overall, the authors did not benchmark on any established benchmarks with all three experimental benchmarks created for this paper. While I trust that the method is strong and will hold up, it would avoid any doubts of cherry picked benchmarks by including standard unlearning benchmarks too. If the authors prefer to stay away from MIA etc., other works such as Goel et al. “Corrective Unlearning” perform poison unlearning too with an objective measure of accuracy.**\n\n(A1) Thank you for raising this thoughtful concern about our evaluation choices.\n\nWe did not use membership inference attacks (MIA) to evaluate unlearning performance because they are (i) general-purpose rather than task-specific, (ii) only provide guarantees relative to the sophistication of the attack method, and (iii) offer limited insight into the mechanism of forgetting. MIA results typically reduce to a confidence score indicating whether a model remembers a given sample, without revealing why unlearning failed or how it might be improved. Instead, we design task-specific evaluation metrics that relate to the structure of each unlearning experiment. For instance, in the Multi-Class Label Erasure setting, the forget and retain sets differ only in color: the forget set includes red and green digits while the retain set includes gray digits. This enables precise measurement of retain quality (classification accuracy on gray images) and forget quality (mean squared error between the model’s predicted probability of \"gray\" and the ideal of 1.0).\n\nWe appreciate the reviewer highlighting Goel et al. (``Corrective Unlearning\"), whose evaluation avoids MIA and proposes other meaningful objective metrics. Although their setting differs slightly, as they focus on adversarially manipulated forget sets and partial access to the manipulated samples, their Unlearning and Utility metrics closely align with our own. In their framework, Unlearning measures expected accuracy over the corrected, de-manipulated samples from the forget data domain, and Utility measures accuracy on samples from the retained data domain. In fact, we can reinterpret our metrics as analogs of these:\n\n\n- In the Data Poisoning experiment, the forget set consists of label-manipulated data (from $\\sin(x)$ to the constant $1.5$.) We evaluate the sup-norm error relative to the true sin(x) function, which directly reflects both Unlearning and Utility, as the two metrics coincide since the input domain is shared.\n- In the Multi-Class Erasure setting, we can view the forget set as consisting of adversarially recolored images. Here, both the retain and forget sets are drawn from the same underlying domain of images, so the Unlearning and Utility metrics both correspond to the model's accuracy at predicting both content and color of gray test images. This is exactly our retain accuracy metric. However, this metric only reflects whether the predicted class is correct and does not compare the confidence of the model's predictions. To more closely evaluate whether the model has unlearned the color information associated with the forget set, we also compute our forget metric which measures the mean squared error between the model's predicted probability for the ``gray\" class and the target probability of 1.0, as the ground truth unlearned model always predicts gray with full confidence. This metric can be interpreted as a softmax-level analog of the Unlearning metric, capturing not just whether the model predicts gray, but how confidently it does so, offering a more sensitive measure of unlearning effectiveness on the color prediction task.\n- In the Representation Collapse experiment, forget set labels are based on image content, while retain set labels depend solely on color. This can be seen as an adversarial manipulation where the forget labels are misaligned with the true color-based labels. Our metric measures the model’s accuracy on color-labeled test data, which directly reflects both Unlearning and Utility, since the input domain is shared and the true labels are color-based.\n\nThus, while our benchmarks are novel, they remain deeply connected to established evaluation principles. We appreciate the reviewer’s suggestion and will revise the paper to cite this related work and explicitly draw these connections.\n\n**(Q2): The work only investigates shallow networks (acknowledged by the authors). Seeing how this method performs on larger models and different architectures would be of interest (e.g. transformers)**\n\nWhile our experiments focus on model and dataset sizes up to ResNet-18 on CIFAR-10, our primary goal is to present a set of interpretable experiments supported by unambiguous metrics. These metrics precisely quantify whether our proposed algorithm MinNorm-OG, developed as an extension of our theoretical framework, offers consistent improvements over existing baseline methods. We show clear failure cases for existing methods and demonstrate the stronger performance of MinNorm-OG, supporting the practical relevance of our framework and beyond the settings where we can provide formal guarantees.\n\nWe agree that testing on larger models and more diverse architectures, especially transformer-based LLMs, is a natural extension. However, developing robust unlearning benchmark datasets at large scales, such as those involving LLMs, with clear and meaningful evaluation metrics remains an active area of research [1–2]. Existing benchmarks [3-4] often rely on indirect and sometimes ambiguous metrics such as membership inference attacks, accuracy comparisons between $D_r$ and $D_f$, and statistical divergence tests. In contrast, our controlled experiments offer unambiguous evaluation criteria. For example, in the Multi-Class Label Erasure experiment, the retain and forget sets differ only in color distribution, as the retain set contains only gray images while the forget set contains red and green images. This allows us to precisely measure retain quality and forget quality, since we know the ground truth unlearned model retrained from scratch on $D_r$ demonstrates two key behaviors: (i) it is a strong classifier of gray inputs and (ii) it always predicts the color of an image to be gray with probability 1, no matter its actual color. This allows us to clearly measure retain quality through classification accuracy on gray test images, and forget quality through the mean squared error between the model's predicted confidence that each input image is gray and the ideal value of 1. These clear metrics enable meaningful comparison across methods and highlight the core contributions of our framework. We recognize that scaling to larger models and different architectures is an important direction, which we plan to explore in future work.\n\n**(Q3): Why did the authors leave out any established benchmarks/metrics? Additional results here would make me increase my score on this otherwise excellent paper**\n\n(A3) We hope the above responses help to address your question. In summary, we appreciate the reference to established evaluation metrics such as those from Goel et al., and we note that our evaluation metrics can be viewed as natural analogs to those proposed in that work. Regarding our focus on novel unlearning tasks rather than standard benchmarks, our goal was to design clear and interpretable settings that enable unambiguous and insightful measurements of unlearning performance. Many existing benchmarks come with limitations related to robustness and interpretability. We will add this rationale and discussion to the revised paper, as we agree this design choice is important and merits further explanation.\n\n**Concluding Remark:**\n\nWe hope that the clarifications above adequately address your concerns, and we are committed to address any additional questions you may have during the discussion phase.\n\n[1] Feng, Z., et al. \"Existing Large Language Model Unlearning Evaluations Are Inconclusive.\"\n\n[2] Hu, S., et al. \"BLUR: A Benchmark for LLM Unlearning Robust to Forget-Retain Overlap.\"\n\n[3] Shi, W., et al. ``MUSE: Machine Unlearning Six-Way Evaluation for Language Models.\"\n\n[4] Maini, P., et al. ``TOFU: A Task of Fictitious Unlearning for LLMs.\""}]

Author rebuttal:

Meta-review: The work addresses an important problem, i.e., how to define and perform machine unlearning in overparameterized regimes where models interpolate the training data. The authors propose a new definition of the unlearning solution as the minimum-complexity interpolator on the retain set and introduce a corresponding algorithm, MinNorm-OG, which shows consistent empirical improvements over several baselines across thoughtfully designed benchmarks.

The paper makes a valuable contribution by providing a well-justified theoretical foundation for unlearning in this setting. The connection between theory and practice is clear, and the experiments are interpretable and relevant. Meanwhile, some limitations are also noted, particularly regarding the scalability of the method to very large models and the strong assumption of exact interpolation. The authors are encouraged to consider these aspects in future work, including more extensive empirical validation on larger-scale datasets and architectures. Additionally, further analysis of the relationship between their proposed metrics and existing unlearning evaluation frameworks would strengthen the applicability of their approach.

Overall, the paper introduces a novel and theoretically sound perspective that effectively addresses a clear gap in the literature, making it a good fit for acceptance.
Decision: Accept (poster)