When to Forget? Complexity Trade-offs in Machine Unlearning
Authors: Martin Van Waerebeke
Marco Lorenzi
Giovanni Neglia
Kevin Scaman
Venue: ICML 2025 poster (2025)
Keywords: Machine Unlearning
Optimization
Differential Privacy
Theory
Primary area: theory->optimization
TL;DR: We investigate when unlearning algorithm can go much faster than full retraining, and when they cannot.

Abstract: Machine Unlearning (MU) aims at removing the influence of specific data points from a trained model, striving to achieve this at a fraction of the cost of full model retraining. In this paper, we analyze the efficiency of unlearning methods and establish the first upper and lower bounds on minimax computation times for this problem, characterizing the performance of the most efficient algorithm against the most difficult objective function. Specifically, for strongly convex objective functions and under the assumption that the forget data is inaccessible to the unlearning method, we provide a phase diagram for the *unlearning complexity ratio*---a novel metric that compares the computational cost of the best unlearning method to full model retraining. The phase diagram reveals three distinct regimes: one where unlearning at a reduced cost is infeasible, another where unlearning is trivial because adding noise suffices, and a third where unlearning achieves significant computational advantages over retraining. These findings highlight the critical role of factors such as data dimensionality, the number of samples to forget, and privacy constraints in determining the practical feasibility of unlearning.

When to Forget? Complexity Trade-offs in Machine Unlearning
Martin Van Waerebeke' Marco Lorenzi
Giovanni Neglia"
Kevin Scaman
Abstract
Kg,
Machine Unlearning (MU) aims at removing the influence specific data points from a trained model, striving to achieve this a fraction of the cost of full model retraining. In this paper, we analyze the efficiency of unlearning methods and establish the first upper and lower bounds on min- imax computation times for this problem, char- acterizing the performance of the most efficient algorithm against the most difficult objective func- tion. Specifically, for strongly convex objective functions and under the assumption that the forget data is inaccessible the unlearning method, provide phase diagram for the unlearning com- plexity ratio-a a novel metric that compares the computational cost of the best unlearning method to full model retraining. The phase diagram re- veals three distinct regimes: one where unlearning at reduced cost infeasible, another where un- learning is trivial because adding noise suffices, and a third where unlearning achieves significant computational advantages over retraining. These findings highlight the critical role of factors such as data dimensionality, the number of samples to forget, and privacy constraints determining the practical feasibility of unlearning.
ryd
Inefficient
(IR)
Unlearning
Efficient (ER)
higher privacy
Unlearning
Trivial (TR)
Unlearning
r
lower utility
e/eo
Figure 1: Schematic representation of the phase diagram for unlearning, where e (resp. en) the target (resp. initial) excess risk, and R.,5 the strength of the privacy constraint (see Section 4). We describe the existence of three regimes of unlearning (IR, ER, TR).
(Mantelero, 2013) and CCPA (Goldman, 2020) attempt to limit these risks and give individuals the right to ask for erasure their data, but modern machine learning models rely on vast corpora, making impractical and costly to honor such request by retraining the model completely (Cottier et al., 2024).
1. Introduction
With the widespread collection of personal data, privacy concerns have become more important than ever (Jha et al., 2024; Kiryati and Landau, 2021). ) As vast amounts of data are gathered, the risk of errors or damaging information being recorded grows, potentially leading to severe conse- quences in the training of machine learning models. This, in turn, can result in inaccurate predictions, such as incorrect medical treatment plans and prognosis (Navarro al., 2021; Lawrence al., 2024). Regulations such the GDPR
Machine Unlearning (MU) aims to solve this issue by ef- ficiently removing the influence of specific training data (the 'orget set') without the need for full model retraining. MU focuses on developing algorithms that can replicate the effects of retraining from scratch at a "fraction of its cost" (Kong and Chaudhuri, 2023; Georgiev et al., 2024).
'INRIA Paris PINRIA Sophia Antipolis. Correspondence to: Martin Van Wacrebeke <mrrtin van van Maneerrbcce@inria..
While we want to retrain the model "al fraction of the cost", the exact "fraction" is currently not quantified in the literature. Specifically, a general machine learning setting and for any accepted excess risk e, let us define ry as the fraction of data in the forget set. We denote by
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
To (resp. T the number of stochastic gradient steps required to unlearn the forget set (resp. to retrain from scratch without the forget set) until the excess risk falls below e. The efficacy of MU can thus be quantified through the ratio of time required by unlearning over retraining, T /T². which we call the unlearning complexity ratio. We currently lack general bounds on this ratio, making it difficult to rigorously assess the efficiency of MU methods relative to simple retraining.
on efficient methods without certified guarantees (Kurmanji et al., 2024; Eldan and Russinovich, 2023) whose unlearning performance are verified empirically by assessing various metrics such as the accuracy of Membership Inference At- tacks (MIAs). In the case of unlearning, the assumption is that the worse the performance of MIAs over the forget set, the better the quality of unlearning. Recently, the effi- cacy of these methods has been questioned (Aubinais et al., 2023; Hayes et al., 2024). At the same time, the theoretical analysis of MU has known important advances, with new certified unlearning methods (Chourasia and Shah, 2023; Ullah and Arora, 2023; Georgiev et al., 2024), which allow for provable robustness against any MIA.
Our first goal consists in characterizing the regime in which the unlearning complexity ratio is provably lower than one, Le., when unlearning is possible at a smaller cost than full retraining. The second goal of our work consists in studying the relationship between the unlearning complexity ratio and the amount of data forget quantified by ry, in order to establish a link between the size of the forget data and the unlearning cost.
Certified Unlearning Studies offering certified unlearn- ing guarantees are based on either exact or approximate schemes. While the former offers stronger guarantees by generating models corresponding to exact retraining, they need to modify the training process, usually through some form of sharding (Bourtoule et al., 2021; Yan et al., 2022; Wang et al., 2023), or tree-based approaches (Ullah et al., 2021; Ullah and Arora, 2023). For this reason, in this work we choose focus on certified approximate unlearning methods, less explored approach to MU that is steadily gaining attention in the field. Some approximate methods rely on KL-based metrics (Golatkar et al., 2020; Jin et al., 2023; Georgiev et al., 2024), or to linear modeling methods (Izzo et al., 2021) to ensure unlearning. We note that the majority of these approaches provide unlearning certifica- tion relying on the theory of Differential Privacy (Guo et al., 2020; Neel al., 2021; Gupta al., 2021; Chourasia and Shah, 2023; Allouah et al., 2024).
Contributions. In this paper, we provide a detailed analysis of when unlearning algorithms can lead to efficient data removal. To do so, we provide the first upper and lower bounds on the unlearning complexity ratio, and thus charac- terize the relative performance of unlearning with respect to retraining. In particular:
We introduce the umlearning complexity ratio (unlearn- ing time over retraining time), leveraging minimax optimization complexity in MU for the first time. This allows us to identify regimes where unlearning is inef- ficient (IR), efficient (ER), or trivial (TR).
We provide the first lower bound for unlearning com- plexity, answering an open problem in the literature (Allouah et al., 2024) and showing that there is a reggime in which gradient- based unlearning cannot asymptoti- cally beat simple retraining (IR).
Machine Unlearning and Differential Privacy. Differ- ential Privacy (DP (Dwork and Roth, 2014) ensures that the protected data (the forget set in our case) has a small statistical impact on the final model. One notable advantage of DP- basedd unlearning certification is its provable robust- ness against any MIA. Protecting every sample through DP would ensures the privacy of the entire dataset, and thus eliminate the need for unlearning, but would come at the cost of significant decrease in model utility (Chaudhuri et al., 201 I; Abadi et al., 2016). In contrast, in the most com- mon definition of unlearning (Ginart et al., 2019), MU only needs to guarantee the privacy of small subset of samples, making it far less restrictive approach. This is emphasized by the fact that several papers in both centralized and de- centralized MU offer significant gains in performance and running time as compared to the systematic application of DP (Fraboni et al., 2024; Allouah et al., 2024). The liter- ature of DP-based MU relies on starting from the original optimum, retraining on the retain set (the full dataset minus the forget and adding noise to the parameters in order to achieve unlearning. The forget set is thus ignored in order to remove its impact on the weights of the model.
We derive the first upper bound for this ratio, exhibiting a regime in which unlearning is provably faster than retraining (ER). The bound scales with r7. the square of the portion of data to forget, demonstrating that a small fraction of data can be unlearned at small cost.
We identify a last regime where unlearning is "trivial," " as simply adding noise to the parameters suffices, and is thus much more efficient than retraining (TR).
2. Related Work
Machine Unlearning is frot-growing but still relatively new field. Several research directions have emerged in the last years, providing the literature with innovative unlearning methods (Jin et al., 2023; Eldan and Russinovich, 2023) and clever ways of evaluating them (Lynch et al., 2024; Hong et al., 2024). One part of the literature has focused
2

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
Comparisons to the Scratch Baseline. Since the impact of the forget set be perfectly removed by retraining from scratch, any relevant unlearning method must be faster than simple retraining. This naturally raises the question of how unlearning methods compare with retraining: what compu- tational savings can be achieved, and at what utility cost. While essential, this question is generally challenging to answer due to the complexity of deep-learning models, and the lack of both unified set of hypotheses and unlearning definition. As a result, while it is common to provide empirical comparison between unlearning and retraining from scratch, this comparison is rarely backed by theoreti- cal arguments. Izzo et al. (2021) provided a comparison of the computational costs of hessian-bar based MU methods for linear models. Other relevant literature use first-order meth- ods perform MU. Huang and Canonne (2023) proved that when the retain set is not accessible during unlearn- ing, one cannot outperform DP on the entire dataset. Two recent papers (Chourasia and Shah, 2023; Allouah et al., 2024) have identified boupds on the number of gradi- ent steps needed by their specific MU algorithm to achieve unlearning, and compare these bounds with the ones on full retraining and other methods. Specifically, Chourasia and Shah (2023) consider a stronger definition of unlearning based on adversarial requests and has to rely on the applica- tion of DP on the entire training set. (Allouah et al., 2024) is a recent work that considers a setting closer to ours, but focusing however on non-stochastic gradient descent. The authors provide bounds on the number of samples that their two algorithms can delete at a certain utility or computing cost, in contrast to our study of the performance of the best possible algorithms over wide class.
where & IR x R + R is a loss function, 0 E Rd the vector of model parameters, and & 'D a random data point in E' drawn according to data distribution D. In machine unlearning, our goal is to remove the impact of a subset of the distribution 'D from an already learnt model. More precisely, for a fraction ry E 1], we decompose our distribution in two parts,
r- Dr + (1-r)) Dr,
(2)
where Dj is the distribution one wishes to remove (i.e., the forget distribution), while D, is the distribution that is unaffected by the removal (ie., , the retain distribution). For example, in order to recover more common setting over discrete data set (see e.g., (Ginart et al., 2019)), we may take D as the uniform distribution over the training dataset EN = (EI...., }. Dy as the uniform distribution over the forget set (Ei,...,&. } C Ex, and ry = k/N. Finally, from a model trained on D (i.e., achieving a small loss C())), our goal is now recover good model for D, in as little computation time as possible, i.e., a model O' whose loss over D,,, L. (0') == Eg-D, [(O',))) is small. In order to derive upper and lower bounds for the time complexity of unlearning, we will focus on strongly-convex and Lipschitz optimization problems.
A Assumption 1 (loss regularity). Let p., L. > 0, and R L/22u. For any & E RR, the loss function ((:EE) of Eq. (1) is L L-Lipschitz and p-strongly convex on (0,, R).
Although not directly applicable to most neural networks, these assumptions have already been used in the literature (Sekhari et al., 2021; Huang and Canonne, 2023) and are less restrictive than other recent studies that also rely on smoothness (Chourasia and Shah, 2023; Allouah et al., 2024). We denote as Fse(1, L) the class of such loss func- tions, abbreviated to Fac when there is no ambiguity. More- over, for any function é E Fsc. we denote as 0* (resp. 0,)) the unique minimizer of L(A) Eς-D [E(0, <)] (resp. (0) Eę-D, [e(0, ()), and it corresponding loss value L (resp. L;). Note that the choice of radius R = T./2μ is relatively standard for theoretical analyses (see e.g., Bubeck et al. 2015), as it allows to focus on the regime in which strongly-conver functions offer significantly faster conver- gence times than their convex counterparts. Finally, fol- lowing standard terminology in the stochastic optimization literature, we will denote computing time the number of stochastic gradient accesses, or equivalently the number of data samples used throughout the (un)learning procedure.
3. Problem Setup
In this section, we describe our learning setup, including the class of iterative learning and unlearning algorithms we consider, and the definition of differential privacy-based unlearning used throughout the paper.
Notations. Let I,, 2 0, and f: IRd - TR a differentiable function. We say that is L-Lipschitz if, v0, 0' E Rd,
((0)) {(0)) < L 0 8'Il. and j-strongly convex if ((0')= 2 ((0) + (VE(0), 0' - 0) + - 1 01l2.
Moreover, we denote as ||||| = V. 0z the nornorm and as (0, R)) = (0 E Rd ||@|| S R} the ball of radius R in Rd, Finally, we will use the notation (D)) for the support of a probability distribution D.
3.2. Iterative First-Order Algorithms
3.1. Learning and Unlearning Setups
In this, section, we provide precise definitions for learning and unlcarning algorithms. More precisely, we will con- sider that both types of algorithms are non-deterministic, iterative and first-order, i.e., that model parameters are up- dated through a stochastic iterative procedure that accesses
Consider a supervised learning setting in which our objec- tive is to minimize the objective function
min L())= = EE [e(( E) 0
3

---

When to Forget? ? Complexity Tradc-offs in Machine Unlearning
Algorithm 1 Iterative (Un)Learning Algorithm
Algorithm 2 "Noise and Fine-Tune" Unlearning Algorithm
Require: Update rule A A, number of iterations T,
Require: number of iterations T, initial model 0", loss function E, dataset D,..
initial model Po, loss function É, dataset D.
1: Initialize memory: Ma (
1: Sample noise 9 ~N 0, (N /t²² la
2: for ( to T -1 1 do
3: Sample data point: & ~~ D
2: Initialize model: 0u = 0" + g
4: Compute gradient: (e)
3: Initialize memory: mgg On
5: Update: (0.+1, mc+1) = A(O,, ())
4: for t = to I do
6: end for
5: Sample data point: & ~ Dr
7: return Final model 0r
6: Compute gradient: Ve Ex)
7: Update: oc+1 = 0: x((+1) Ve Ve(0,, St)
8: Update: m = m. + (t + 1)0
stochastic gradient of the loss function at each iteration (see Algorithm
9: end for
1). This class of algorithms, defined by their update rule A E A, is very general and contains most standard optimization algorithms used in machine learning. More precisely, an update rule is a measurable function
10: return Final model Ó (T+1)(++2)
2mp
Again, we will denote as U the class of such unlearning algorithms, and simply write (D,,, Dy) when there is no ambiguity on the values of T and L. Note that these un- learning algorithms can only sample from the retain set to perform unlearning. This is relatively common in the litera- ture of DP-based MU (Neel et al., 2021; Fraboni et al., 2024; Huang and Canonne, 2023; Allouah et al., 2024), although more efficient unlearning methods might exist in scenar- ios in which the forget dataset is also available during un- learning. Finally, while we allow stateful algorithms in our framework, the algorithm used to achieve our upper bound in Section 4 only uses the state to remember the weighted average of previous iterations rather than all iterations, alle- viating some privacy issues for adaptive unlearning requests (Izzo al., 2021).
A (0,, Ve, w) = (0z+1, m)+1);
(3)
where 0, E d is the current model, V, E E stochastic gradient, m, E M memory state, and w E Ω a seed used for adding randomness into the algorithm. The memory serves as a storage mechanism for essential information about past iterates, enabling the computation of quantities such as momentum, moving averages, or adaptive step-sizes.
For given update rule A E A, we denote 0/7 E, D,)) the output of Algorithm I, which applies the update rule A successively T times, starting at Og E T
Learning Algorithms. For any update rule A E A, we define the associated learning algorithm as the function A mapping the number of iterations, loss function, and dataset to the output of A initialized at Oo- 0, i.e.,
3.3. Unlearning Guarantees
Unlearning aims at removing the impact of the forget set on the trained model. The way it achieved in DP-based un- learning is by making sure that the output of the unlearning algorithm is statistically indistinguishable from the output of another algorithm independent from the retain set.
A(T, Dr) = (0,
(4)
In what follows, we will denote by A the class of such learning algorithms, and write A(D,) when there is no ambiguity on the values of T and L.
In the literature of ba-bd MU, most papers rely on the following definition, first introduced by Ginart et al. (2019).
Unlearning Algorithms. While learning algorithms try to estimate the optimum of the objective function E, from scratch, unlearning algorithms have the advantage of starting from a pre-trained model with low excess risk (i.e, error of the model minus error of the optimal model) on the whole dataset. More precisely, we will assume that such model was trained for a sufficiently large amount of time, and reached the unique minimizer 6* of the objective function L. Therefore, for any update rule A E A, we define the associated unlearning algorithm as the function 2/ mapping the number of iterations, loss function, retain dataset and forget dataset to the output of A initialized at 0,- 0", ,ie.
Definition 1 ((c, 8) Reffereee Unlearning). An unlearning algorithm U E U satisfies (c, Reefeernn Unlearning if there is a reference algorithm A E à such that, for any couple of distributions (Dr, D5) and subset S C Rdd
P(U(D,,))) E $ e P[A(D,) E S] + P[A(D,) e é PP(D,, Dj) E E +
We refer to it as "reference unlearning" in the sense that an algorithm 4 is said to achieve unlearning if another algo- rithm A achieves a similar output while being independent from the forget set. However, as mentioned in recent re-
UT, e, Dr, Dy) = (0', ,0, e, Dr).
(5)
4

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
search (Georgiev et al., 2024), this is not satisfying in the sense that it makes the unlearning definition rely on the al- gorithm A which is generally simple retraining on the retain set. We propose another -slightly stronger (see Lemma 3.1)- definition that does not rely on a reference algorithm but rather only on the unlearning algorithm itself.
of any algorithm A and find the algorithm minimizing this worst case. Therefore, one can define the minimax re- training time of algorithms in A over the function class Fsc
as
T == inf sup T A). AE tEFic
(8)
Definition 2 ((c, 8)- --Uneeaminng) An unlearning algorithm U U satisfies (e, O)-nneurnn, if. for any triplet of distributions (Dr, D,,D) J,D)), loss function l, and for any subset of outputs S C R4, the following holds,
In the same way, we define the minimax forget time of unlearning algorithms in Ue, d over the function class Fsc as
T = inf sup (e,u). UEU.s REFic
PR,(Dr, E S) < e- IPU D')) E +
4. Regimes of Unlearning Complexity
The values (c are called the unlearning budget. The lower the budget, the harder unlearning is to achieve.
In this section, we provide lower and upper bounds for the unlearning complexity ratio T /T: (see Section 3.4) over wide class of unleaming algorithms U. By doing so, we identify regimes in which unlearning methods are significantly faster than retraining, and regimes in which they are not. In particular, we identify values of the target excess risk e and strength of the privacy constraint Ke,5 = E V In (125/55 (see the Gaussian mechanism in Dwork and Roth 2014) in which the unlearning complexity ratio is small when forget ratio ry is small. An illustration of this phase diagram is available in Figure 1, highlighting the three regimes observed in the analysis. All the proofs are deferred to the Appendix.
This definition is very close to the notion of Differential Privacy. The only difference is that this one only ensures privacy of the forget set rather than the entire training set. This definition very convenient because it does not depend on any other learning algorithm. We will refer to this defini- tion going forward, but note the two are closely related, as proven next.
Lemma 3.1 (Equivalence of definitions). Any algorithm achieving (e, ö)-nneernnng also achieves (e, RReferenne Unlearning. Furthermore, any algorithm achieving (e, Reefereee Unlearning also achieves (1+ Unlearning.
4.1. Speed of Retraining from Scratch
Note that the way U is defined allows non- non-private algorithms to belong in it. For any unlearning budget (e, o), we thus de- fine Ug, as the algorithms in U achieving (e, 0)-nneerrnn
First, we recall the optimal convergence rate for strongly convex and Lipschitz functions, and adapt its proof to our setting. In addition, we show that learning is trivial (i.e. T 0) if e 2 eg target excess risk.
12 as Oo 0 already satisfies the 8p
3.4. Minimax Computation Times
In order to quantify whether or not it is worth it to perform unlearning, let us start by introducing some key elements. First, we define the time required to re-learn from scratch and unlearn. For a given excess risk threshold e, loss l and learning algorithm A E A, one can define the time needed to retrain from scratch until we get excess risk smaller than e as
Lemma 4.1. Ife 2 ca, then
T =0
In order for our lower bounds to hold, we need a technical assumption that allows flexibility on the choice of forget dis- tribution and objective function, as well as a clear separation between forget and retain distributions.
(e, (T; ((C, se), (6)
TEN
Assumption 2. (Flexible distributions) For any p E [0, 1), AE C R2 s.I. P(C, E A) = p. where & Dr. Moreover, there exists a distribution D', such that supp( (Dp and supp(D',) are two-by-two disjoint.
where (0) = EęWD, [))
In the same way, we can define the minimal number of optimization steps required by an algorithm U to 5)- Unlearn the forget set and achieve an expected excess risk under the threshold e starting from the optimum 0* i.e.
This assumption is relatively weak, and usually verified for continuous distributions, as long supp DD,) and supp(D)) do not cover the whole space TR...
TV (e,24) = min(T (T; EI D,)) C1 $ e}. Tek
(7)
Lemma 4.2. Under Assumption 2, and e eg. we have
When studying the performance of an algorithm over a func- tion class, one wants to study the worst-case performance
T = θ Cg
(10)
5

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
To claim that an unlearning method is efficient will thus require for its computation time to be significantly smaller than O(eo/e). We will show that such unlearning algo- rithms do exist in Section 4.4.
Wu 2025), but requires combining this classical method with the (c, J--nneamnnngg constraint in order derive proximity between the two algorithm's 's outputs.
Theorem 2 provides a regime in which first-order unlearn- ing methods cannot asymptotically outperform retraining. This regime is delimited by a curve of type Ke, 2 ave, with a a constant, explaining our choice of representation in Fig. 1. For low forget ratios ry < 1, the unlearning complexity ratio is lower bounded by a constant when is below quantity proportional to (1 + k²2,) In this regime, removing even minimal parts of a dataset requires a non-negligible retraining time. This may be an issue when numerous small removals must be made to a model, as each of these removals will incur cost proportional to that of its full retraining. Fortunately, reeo is often extremely small in practical scenarios when the forget ratio is proportional to /n where is the size of the training dataset (see Section 4.5), and this regime only appears for very high privacy constraints Ki., of the order of 1 V Finally, when the target excess risk e tends to 0, a direct corollary of Theorem 2 is that unlearning cannot asymptotically outperform re- training, regardless of the strength of the privacy constraint Ke,8- However, most existing exact MU algorithms rely on modifications of the training set and are thus not included in our framework.
4.2. Trivial Unlearning Regime
We now start with the simplest case: for high target ex- cess risk and low privacy constraint Ke,5, simply adding Gaussian noise to the parameters of the model is sufficient.
Theorem 1 (Trivial regime). If the target excess risk verifies + vdnces) en, e0) then
EE
I-ry
T TS
0. 0.
(11)
This first regime corresponds to the dark blue area in Fig- ure 1. In this regime, unlearning can be performed with zero gradient access, provided that the combination of e and Ke,5 is sufficiently permissive. The boundary of this region, as described in the previous theorem, is an affine function of e, as represented in Fig. 1. For low forget ratios ry < 1, the regime begins at e Rs rÿeo and Ke.8 = 0, and ends at e = 60 and Ke,5 1/(ryvd). As direct consequence, for fixed target excess risks and privacy constraints Kr,8, unlearning eventually becomes trivial as the forget ratio Ty tends to 0. This result is expected, as the distance bound between the two optima ||0- I is proportional to Ty. and thus unlearning al algorithms start directly from the optimum in this regime (see Lemma C.I).
Corollary Within the hypothesis of Theorem 2, and for ry E (0, 1) and K5,5 2 0 fixed we have
T
lim inf
>0 T
(13)
In other words, the advantage of starting from a pre-trained model 0* instead of retraining from scratch reduces as the target excess risk decreases, and, below a certain threshold, no asymptotic complexity improvement can be achieved by unlearning methods over retraining. Additionally, Theorem 2 offers an impossibility result for exact unlearning methods within our assumption set. Indeed, exact unlearning implies setting K., = +oo, applying Theorem 2 thus informs us that no asymptotic performance gain is possible.
4.3. Inefficient Unlearning Regime
Conversely, we now show the existence of a regime which unlearning cannot asymptotically outperform retraining.
Theorem 2 (Inefficient regime). Let ô E [10- e.... Under Assumption 2, there exists a universal constant e >> such that, ife min 1, (,=), (1
(225)) }
eg. then
T T5 = 2(1)
(12)
4.4. Efficient Unlearning Regime
We have now identified that, on one end of the spectrum, unlearning is trivial while on another end, unlearning is inefficient. We now characterize what happens between those two extremes by showing that a simple unlearning mechanism achieves a good unlearning complexity ratio in this intermediate regime. To do so, derive upper bound on unlearning time using the unlearning algorithm "noise and fine-tune" (see Algorithm 2), which is an adapted version of Neel et al. (2021)'s 's perturbed gradient descent. Using this upper bound along with Lemma 4.2, we imme- diately get an upper bound on the unlearning complexity
The proof of Theorem 2 relies on three steps: 1) defining a class of objective functions L for g R' + {-1,1) 1} such that their optimum over D does not provide any information on the dataset D,,, 2) showing that two such functions L and L have optimums over D, distant from one another, and 3) showing that any algorithm's 's output will behave nearly identically on both L and L-9, thus leading to the impossibility of having both functions efficiently optimized by the same algorithm. Overall, the approach is similar to Le Cam's 's two point method (see for instance Polyanskiy and
6

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
ratio. Although the choice of this simple algorithm may not be optimal, it only impacts the results in this subsection, whereas Theorems I and 2 are agnostic to the choice of the algorithm.
4.5. Discussion
Overall, our analysis shows that there are three main Segimes-Trividae Inefficient, and Efficient-that describe how unlearning time compares to retraining wwws--roo--tttte time, based on the target excess risk the strength of the privacy constraint Ke,, and the forget ratio ry. Figure I illustrates these regimes and their boundaries.
Theorem 3 (Noise and Fine- Tune Efficiency). For any e co. we have
T T5
= O ( (1-17) ) (1+ dm2,))
cn
(14)
Since we rely on noising the model parameters to ensure unlearning, our bound scales with vd. is common in differentially-private optimization (Bassily al., 2014). While natural, this dependence is not matched by our lower bound in Theorem 2. We leave the exploration of this dis- crepancy to future work.
The proof of Theorem 3 relies on controlling the distance be- tween the two optima || | - 0; by a factor proportional to ry, and using the classical convergence rate in O(LR/VT) for convex stochastic optimization when the optimum is within distance R from the initialization. Quite surpris- ingly, this convergence rate proportional to ry is obtained with the use of convergence rates from the convex literature, despite being in a strongly convex regime where faster rates in (L2 /TT) are usually favored.
In a realistic machine learning setting, one is usually inter- ested in achieving an excess risk on the training set of the same order as the generalization error, which value if often around 1/n, where n is the size of the dataset (Bousquet and Elisseeff, 2002). In this context, forgetting one sample with an average unlearning budget (i.e., Ke,5 22 1) can be done fairly cheaply, since applying the bound from Theo- rem 2 yields T /TS of the order of r2 as rīdn, and one can thus remove number of data points at most of the order / Moreover, if y x 1/nn, then the unlearning complexity ratio is of the order d/ n and unlearning can be very efficient in under- mnder-parameterized settings.
Theorem shows that efficient unlearning, with an unlearn- ing complexity ratio proportional r², is possible. For low forget ratios ry < 1, the "noise and fine-tune" method out- performs retraining (i.e., TH < T when the target excess risk is above a quantity proportional to r (1+ [1+dR2,, eo. and we recover, up to a constant and for a fixed dimension d, the regime in which unlearning becomes possible in Theo- rem 2 (see Section 4.3). The combination of both Theorem 2 and Theorem 3 thus shows that r (1 + dr²,, eo acts as threshold for the target excess risk before which efficient un- learning impossible, and above which unlearning becomes efficient (and even trivial beyond rr + Veo).
5. Experiments
We investigate the global landscape of the unlearning com- plexity ratio as a function of key factors, including the ac- cepted excess risk threshold e and the unlearning budget (c, which are jointly quantified by the constant Ke,5-
Moreover, while a large value of Ke.5 negatively impacts the unlearning time, the converse is only true to certain extent since a low value will not necessarily allow for immediate unlearning. This is due to the fact that, even with very a weak privacy constraint, the unlearning algorithm still has to cover the distance between the full optimum and the retain optimum.
5.1. Experimental Setting
The goal of the experiment section is to validate the the- oretical analysis presented in Section 4 by comparing the performance of unlearning and retraining on both real and synthetic functions and datasets.
In order to give an estimate of the unlearning complexity ratio, we need to choose specific algorithms to represent the learning algorithm class as well as the unlearning algorithm class U. For the learning algorithm, we choose stochastic gradient descent, Gower, 2023), since it is known to achieve the optimal asymptotic speed of O Se ) (see proof of Lemma 4.2).
To complete the characterization of the unlearning regimes initiated in this section and illustrated in Figure 1, we con- clude with the following direct corollary of Theorem 3, which characterizes the efficient regime.
defined in (Garrigos and
Corollary 2. (Efficient regime). There exists a universal constant e > 0 such that, for any 7 E (0,1), if
c rf ) 2 e
For the unlearning algorithm, we choose the "noise and fine-tune" algorithm (see Alg. 2) since it is the one used to derive the bound in Theorem 3.
γ 1 1- rr)
(1+ dri.)) co.
then
We aim to learn linear regression models in Rd (with even d). We perform experiments both on synthetic "worst-case"
T
T'5 7.
7

---

When to Forget ? Complexity Trade-offs in Machine Unlearning
1.0
IR
IR
0.8
0.8
10
10
0.50
0.50
Kg.6
1-
ER
ER
0.10
TR
TR
0.10
0.1
0.01
0.01
0.1
10
T2
1e-05
0.0001
0.001
0.01
0.1
Tt
e
e
T5
(a) Synthetic dataset.
(b) Real dataset.
Figure 2: Experimental phase diagram of the unlearning complexity ratio. We give estimates for T and T using the "noise and fine-tune" (Algorithm 2) and SGD algorithms, respectively. We display the value of their ratio as function of Ke,5 and in log-log scale. We notice the three regimes described in our theoretical analysis: inefficient (IR), efficient (ER), and trivial (TR)..
functions, as analysed in our theory, and on the Digit dataset of handwritten digits, which is subset of the larger dataset proposed in Alpaydin and Alimoglu (1996).
The unlearning and retraining algorithms are performed for fixed time T. To produce the phase diagram of Fig. 2b, we choose values of T logarithmically spread between 1 and 106. We also choose values of and K,,5 logarithmically spread between 10-2 and 10?. For each value of T, we generate a corresponding function g and loss function C. We run our learning algorithms for stochastic gradient steps, recording the corresponding time every error threshold e is passed. For each value Ke,5, we run our unlearning algorithm for T stochastic gradient steps, recording the corresponding time when every threshold is passed. We repeat this process 50 times to better estimations of the expected unlearning and retraining times. Then, for each value of e, we average all the obtained learning times. For each pair of value (e, Ke,5), we average all of the obtained unlearning times. The ratio of the average unlearning time and of the average learning time is what refer to the empirical unlearning complexity ratio. By definition, this set to 0 if the average unlearning time is 0.
In every experiment, the retain and forget are obtained through the random splitting of the dataset into two parts of respective sizes [ry vı and [ry n... We consider ry = 10-2
5.2. Experiments on Synthetic Data
For the synthetic dataset, the expected loss function is:
d/2
(()) = |101 4 Re Re-D(g(E)
Σ
[0.1
1=1
i=1+4/2
where g R- + 1-, and 0; represents the i-th co- ordinate of The dataset distribution D influences the loss solely through the resulting distribution of g()), where g(E) is Rademacher random variable with expected value of [[g] T where T denotes the number of time steps for which the experiment will be conducted. For this experiment, we set L 25 and 1.
5.3. Experiments Real Data
For the real data, the experimental process is simpler optimize standard cross-entropy loss with L2 regulariza- tion. For various values of Ke. and we measure T and TSS in a more realistic machine learning setting, with decay-
This loss function stems from the refinement of the "worst- case" loss analyzed during the proof Theorem 2, with the goal of deriving a hard function fitting our hypothesis. Its origin is given in more details in Appendix B.
8

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
ing learning rate, batch size of 64, and averaging the results over 50 runs. We defer the full experimental details Ap- pendix D. The sensitivity used for the unlearning algorithm is the real distance| | 11
Empirical validation confirms these insights, showing the utility of analysing unlearning through the minimax com- plexity framework. Beyond unveiling fundamental limits and opportunities, our results address an open question on whether unlearning can outperform retraining- what circumstances. We introduce the first bounds on the unlearning complexity ratio, as well as the first lower bound on unlearning time.
under
5.4. Experimental Results
Figure 2 illustrates the empirical unlearning complexity ratio. The figure empirically demonstrates the existence of the different regimes theorized in Sec. 4. More specifically, Theorem 1 predicts an affine linear dependency between e and Ke,5 at the frontier of the efficient regime and the trivial regime. In the log-log plot, this would appear as a line with slope 1, which can recognize in the level-curve corresponding to an empirical complexity ratio equal to 0.1 in Fig 2a'. We can however see that that this is not the case when experimenting on the smooth loss function of Figure 2b, as the smoothness allows for faster convergence rates, and the delimitation thus becomes a square-root function.
We hope that the framework and findings presented here will stimulate further studies on machine unlearning in broader contexts, and allow further analysis of wider class of algo- rithms and objective functions, as well as data distributions. Specifically, bownd-bonn the unlearning complexity ra- tio for methods beyond the first order, not verifying Assump- tion 2, or methods relying on the forget set, remains an open challenge.
Impact Statement
The existence of the efficient regime ER can also be noticed in Fig. 2. A large portion of the figure shows values of the experimental unlearning complexity ratio well below 1. We observe that, while our experiments considered an optimal learning algorithm, the "fine and tune" unlearning algorithm may be sub-optimal. One can expect that better unlearning algorithms can achieve even smaller complexity ratios.
This paper presents work whose goal is to advance the field of Machine Learning and Unlearning. There are many po- tential societal consequences of our work, none which we feel must be specifically highlighted here.
A Acknowledgements
Finally, we also observe the IR regime at the top of the figure. Infact, the low slope of the level line at 0.5 indicates behaviour similar to what is theoretically predicted by Theorem 3 as a square root function has slope of 0.5 in log-log scale.
This work was supported by the French government man- aged by the Agence Nationale de la Recherche (ANR) through France 2030 program with the references ANR- 23-PEIA-005 (REDEEM), ANR-22-FAI1-000S (TRAIN), ANR-2441AS2-0001 (Fed-Ops), ANR-19-P3IA
(3IA),
This research was also supported in part by the European Network of Excellence dAIEDGE under Grant Agreement Nr. 101 120726, by the EU HORIZON MSCA 2023 DN project FINALITY (G.A. 101 101168816), by the Groupe La Poste, sponsor of the Inria Foundation, the framework of the FedMalin Inria Challenge.
6. Conclusion
In this paper, we study the efficiency of machine unlearning through the lens of novel metric -the unlearning com- plexity ratio- which compares the worst-case convergence speeds of the best unlearning and retraining algorithms. Our analysis reveals three distinct regimes. In one (TR), we show that unlearning can be done "for free" because pertur- bation the parameters enough to achieve unlearning while keeping the excess risk low enough (Theorem 1). In another (IR), described by our lower bound on the unlearning com- plexity ratio (Theorem 2), unlearning cannot asymptotically beat retraining through gradient- baadde methods. In the last regime (ER), in between the other two, our upper bound on the unlearning complexity ratio shows that unlearning possible at a small fraction of the cost of retraining, a cost that scales with the square of the fraction of forgotten samples (Theorem 3).
References
REFERENCES
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016). Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and commu- nications security, pages 308-318.
Allouah, Y., Kazdan, J., Guerraoui, R., and Koyejo, S. (2024). The utility and complexity of in-and out- of-distribution machine unlearning. arXiv preprint arXiv:2412.09119.
'The fact that the level line stops around e 1 an artifact due to the discretization of the experimental setting.
Alpaydin, E. and Alimoglu, (1996). Pen-Based Recog-
9

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
nition of Handwritten Digits. UCI Machine Learning Repository. DOI: http:///oo..rrr110222/33///////
Ginart, A., Guan, M., Valiant, G., and Zou, J. Y. (2019). Making ai forget you: Data deletion in machine learning. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché- Buc, F., Fox, E., and Garnett, R., editors. Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc.
Aubinais, E., Gassiat, E., and Piantanida, P. (2023). Fun- damental limits of membership inference attacks on ma- chine learning models. arXiv preprint arXiv:2310. 1377666
Bassily, R., Smith, A., and Thakurta, A. (2014). Private em- pirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th anmual symposium on foundations of computer science, pages 464-473. IEEE.
Golatkar, A., Achille, A., and Soatto, S. (2020). Eternal sunshine the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
Bourtoule, L.,, Chandrasekaran, V., Proqueette-Choo C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. (2021). Machine unlearning. In 2021 IEEE Symposium Security and Privacy (SP), pages 141-159. IEEE.
Goldman, E. (2020), An introduction to the california con- sumer privacy act (cepa). Santa Clara Univ. Legal Studies Research Paper.
Bousquet, O. and Elisseeff, A. (2002). Stability and gener- alization. J. Mach. Learn. Res., 2:499-526.
Guo, C.,, Goldstein, T., Hannun, A., and Van Der Maaten, L. (2020). Certified data removal from machine learning models. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learn- ing, volume 119 of Proceedings of Machine Learning Research, pages 3832-3842. PMLR.
Bubeck, S. al. (2015). Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357)
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. (2011). Differentially private empirical risk minimization. Jour- nal of Machine Learning Research, 12(3).
Gupta, V., Jung, C., Neel, S., Roth, A., Sharifi-Malvajerdl S., and Waites, C. (2021). Adaptive machine unlearn- ing. Advances in Neural Information Processing Systems, 1816319-163300
Chourasia, R. and Shah, N. (2023). Forget unlearning: Towards true data-deletion in machine learning. In Inter- national Conference on Machine Learning, pages 6028- 6073, PMLR.
Hayes, J., Shumailov, I., Triantafillou, E., Khalifa, A., and Papernot, N. (2024). Inexact unlearning needs more care- ful evaluations to avoid a false sense of privacy. arXiv preprint 243302240..012
Cottier, B., Rahman, R., Fattorini, L., Maslej. N., and Owen, D. (2024). The rising costs of training frontier ai models. arXiv preprint arXiv:2405.21015
Hong, Y., Yu, L., Yang, H., Ravfogel, S., and Geva, M. (2024). Intrinsic evaluation of unlearning using paramet- ric knowledge traces. arXiv preprint arXiv:2406. 1614.
Dwork, C. and Roth, A. (2014). The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):21 1-407
Huang, Y. and Canonne, L. (2023). Tight bounds for ma- chine unlearning via differential privacy. arXiv preprint arXiv:2309.000 00866.
Eldan, R. and Russinovich, M. (2023). Who's harry pot- ter? approximate unlearning in 1lms. arXiv preprint arXiv:2310.0223:
Izzo, Z., Anne Smart, M., Chaudhuri, K., and Zou, J. (2021). Approximate data deletion from machine learning models. In Banerjee, A. and Fukumizu, K., editors, Proceedings of The 24th International Conference telligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2008-2016 PMLR.
Fraboni, Y., Van Waerebeke, M., Scaman, K., Vidal, R., Kameni, L., and Lorenzi, M. (2024). Sifu: Sequential informed federated unlearning for efficient and provable client unlearning in federated optimization. In Interna- tional Conference Artificial Intelligence and Statistics, pages 3457-3465. PMLR.
Artificial In-
Garrigos, G. and Gower, R. M. (2023). Handbook of conver- gence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301. 11235 1235.
Jha, N., Trevisan, M., Mellia, M., Fernandez, D., and Irar- razaval, R. (2024). Privacy policies and consent manage- ment platforms: Growth and users' interactions over time. arXiv preprint 1823:
Georgiev, K., Rinberg, R., Park, S. M., Garg, S., Ilyss, A., Madry, A., and Neel, S. (2024). Attribute-to-dlltte: Ma- chine unlearning via datamodel matching. arXiv preprint 10.22224...23232.
Jin, R., Chen, M., Zhang, Q., and Li, X. (2023). Forget- table federated linear learning with certified data removal. arXiv preprint 20xx:2306.02216.
10

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
Kiryati, N. and Landau, Y. (2021). Dataset growth in medi- cal image analysis research, Journal of imaging, 7(8):155.
Wang, Z., Alghazzawi, D. M., Cheng, L.,, Liu, G., Wang, C., Cheng, Z., and Yang. Y. (2023). Fedesa: Boost- ing the convergence speed of federated unlearning un- der data heterogeneity. In 2023 IEEE Indl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing Communications, Social Computing Networking ASSAABCCoondSoriaCmSSStttaiiaac pages 388-393. IEEE.
Kong, Z. and Chaudhuri, K. (2023). Data redaction from pre-trained gans. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 638-60080 677.
IEEE.
Kurmanji, M., Triantafillou, P., Hayes, J., and Triantafil- lou, E. (2024). Towards unbounded machine unlearning. Advances in neural information processing systems, 36.
Yan, H., Li, X., Guo, Z., Li, H., Li, F., and Lin, X. (2022). Arcane: An efficient architecture for exact machine un- learning. In IJCAI, volume 6, page 19.
Lawrence, H. R., Schneider, R. A., Rubin, S. B., Matarić, M. J., McDuff, D. J., and Bell, M. J. (2024). The opportu- nities and risks of large language models in mental health. JMIR Mental Health, 1(1):e59479.
Lynch, A., Guo, P., Ewart, A., Casper, S., and Hadfield- Menell, D. (2024). Eight methods to evaluate robust unlearning in llms. arXiv preprint arXiv:2402. 16835.
Mantelero, A. (2013). The eu proposal for general data protection regulation and the roots of the 'right to be forgotten'. Computer Law & Security Review, 29(3):229- 235.
Navarro, C. L. A., Damen, J. A., Takada, T., Nijman, S. W., Dhiman, P., Ma, J., Collins, G. S., Bajpai, R., Riley. R. D., Moons, K. G., et al. (2021). Risk of bias studies on prediction models developed using supervised machine learning techniques: systematic review. bmj, 375.
Neel, S., Roth, A., and Sharifi Maniiiiiia,ajjriii,, S. (2021). Descent-to-delete: Cradient-based methods for machine unlearning. In Feldman, V., Ligett, K., and Sabato, S., ed- itors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Pro- ceedings of Machine Learning Research, pages 931-962. PMLR.
Polyanskiy, Y. and Wu, Y. (2025). Information Theory: From Coding to Learning. Cambridge University Press.
Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. T. (2021). Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34:1840 18085-
Ullah, E. and Arora, R. (2023). From adaptive query release to machine unlearning. International Conference on Machine Learning, pages 34642-34667. PMLR.
Ullah, E., Mai, T., Rao, A., Rossi, R. A., and Arora, R. (2021). Machine unlearning via algorithmic stability. In Conference on Learning Theory, pages 4126-4142. PMLR.
Villani, C. et al. (2009). Optimal transport: old and new, volume 338. Springer.

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
A. Upper Bounds
The rt_ Proof of Theorem I. Let 2 1-ry --ry
+ vddi.s) co-
Let the unlearning algorithm consist in simply adding Gaussian noise to the previous optimum 0* By application of the Gaussian mechanism (Dwork and Roth, 2014), adding i.i.d. Gaussian noise with standard deviation lic,ó |0 0'1l ensure (e, JUnleennngg of the forget set. Using the bound from Lemma C.I, we sample:
Tf Tf_ L 1 1a)) g NO, (Ke, 1- 1
(15)
where la is the identity matrix in Rdd.
Let = 0 + g. We can then bound the expected loss of Ó:
B (0)
c E (c(()) (1) (0")
+ (f") f
(16)
(
1
1
Vances
(I-
H
+
1 rf 1
(17)
rs (rs + Vdvios)
(18)
se
(19)
Proof of Theorem 3. According to Lemma C.1, we have
rf 1- ry
100 0 <
Rı.
(20)
To perform the unlearning,
the noise fine-tune method as introduced in Algorithm 2. For the noising part, the
standard deviation of the noise that needs to be added to ensure (e, -)Unleamingg of Dj is Ke,8 1 0,11. Thus, we set & R1 and define 0 = l* + g. where o2)
Now, can notice that
E
0
0:1""
[||||]] 1 0;11 s (1 du? dr?
(21)
While we do not know the exact distance |@
0::| our SGD will need to cover, have its expectation. Thus, set the learning rate y be optimal for the expectation of the distance, i.e., :
(1+dx2 x
TV12
Let A, be the SSD algorithm with learning rate 7, defined in Section 3 of Garrigos and Gower (2023). Using Theorem 9.7 from Garrigos and Gower (2023), we get
0 0:
2
E (.,,
C; E
(22)
2TT
(1 + dis2 (.62 R
L
(23)
2T
2
LR
dr?
(24)
For given excess risk threshold e, the unlearning time can then be upper-bounded as
12

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
R2 T - 2²
dr2,6)
(1-r, -1--/,; ) (1+ dn2,6)
Ts
(0 )
(25)
B. Lower bounds
The lower bounds of Section 4 rely on three steps: 1) defining a class of objective functions 2 for g RR" + (-1,1) such that their optimum over 'D does not provide any information on the dataset D,, 2) showing that two such functions L and C-9 have optimums over D, distant from one another, and 3) showing that any algorithm's 's output will behave nearly identically on both _ and L-9, thus leading the impossibility of having both functions efficiently optimized by the same algorithm.
{E(ea [0)( where 8 is loss function such that In what follows, for any function g + [-,,1], we denote as (0) =E
-
e (0. = 16 1101
2 9())11
(26)
2
where 0₃ is the first coordinate of in the canonical basis of Id..
This loss was used as base for the experiment on synthetic data. More specifically, we added an L1 penalization term in order to make the function non-smooth, and expanded the loss on 0, the first half of parameters. This is motivated by the need to avoid numerical instability every other parameter but the first would otherwise quickly converge to 0, and the first one would oscillate around the optimal value, in a process that could converge prematurely.
By definition, Vo (0, {) = 11 - Lg(g)))) where e is the first vector of the canonical basis of IRd, and (9 is L-Lipschitz and jesttonngy convex. Moreover, the objective function on D, is (() thus the minimizer of C is 0*
= 5 0 Y/2 E [o((')) 01, where ç ~ Dr, and L E [e(e)] S Rt.. We now show that, provided we find two functions 9, g' such that the output of any algorithm is (statistically) almost indistinguishable, then minimizing both L and L beyond certain quantity is impossible. To properly define this indistinguishabbiity, we will use the total variation distance div (P. Q) SuPACR IP(A) Q(A) for two probability distributions P and Q.
L E [o({')] e1 (note that |00 g.r 2z
2/
Lemma B.1. Let 9.9' R [_ two functions. 0o 0 Rdd two initial parameters, and A A algorithm. Then
sup g"El
E ce" (04(00, es",, ,D)) - -cq""
(1 drv(Pas Pa)),
(27)
32
where& 5 Dr, 04,, es', Dr)).
(0) and Pg (resp. P is the probability distribution of 04 69, Dr) (resp. c²" mingers (0)
Proof. First, note that 0r. 2p
[g((')] e and thus C²( - LØ- -1 g.r 0112. Using the optimal transport definition
of total variation (see egg., Villani et al. 2009), div d Q) = inf P(X + P(X couplings of and Q As consequence, there exists two random variables 02 Pg and O2 ~ Pg. and such that P0 + 02)) = drv (Pg. ). leading to
Y) where the infimum is taken over all
sup [((a')) E /oyr. - 04 60"" "o,,,))
= max E [10; 1 - 02 -0]1]]
|10: - -02113}
(1 drv(Pg (Pg. Ps))) max
g.r o|l
|00- "1}}}
(28)
(1- drvd P.))) 00...1.
where 0 - =E [0, 0, = 02] [ E 0, 0z). Finally, using the formula for 0
L E Elg(g') e1 and () - C.¹
24
2 10 - - gives the desired result.
g.r
13

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
We now show that partieular choice of functions 9: leads almost indistinguishable outputs.
Lemma B.2. Assume that Vy [0, 1]. there exists A supp(Dr) such that PD, (1 + 7)/2. (e) 21
Ar 10-10 1 i E supp(D,), and gE) = min(1, (1-7h>) otherwise. Then, we have
div (u(T, 10 D,, u(T, e0 Dy. - 7VVT (0-rs)- (6-
- (
(29)
2r
Proof. First, note that the minimizer of 2 is 0 (1 ry)4e1, and we thus have u(T, 15", ,Dr, Dj)
0/((0 e0", ;D,) and U(T,e l-9", Dr, Df) o 0
To ease the notations, we denote by 0g,1
0 (-T1)) e1, (9"21 D,) the output of algorithm A on the function 29 starting at 0o (1-rr) 61, where 2p
21 kry
The = (1 1-r,) ) Let K
(1-rz)> then we have, by triangular inequality, 2rg
div (0000 0K,K)
Σ
d0 0k,k+)), h=0
Σ k=0
drv fov(0xx 1,,,,-1,00+11,--11 0k+1N+1)-
(30)
By construction, we have 00.0 U(, (9" D,, and - bounded: the first using the fact that the T gradients (Ex) for t E [O,T 1] are close in total variation distance (i.e.. Lemma C.5), and the second using the (c, (0)-)))nneaning constraint on U.
= UT, 88" D,, D,),,). We now show that both sums can be
By Lemma C.4, there is a measurable function р사 such that o., = PA (1-ry)( Z/
where Z 7
2/
(1 + g²* (22 are ii.d. Bernoulli random variables of parameter 1+722 algorithm initialized at the same starting position, we have
As Oz.k and 0s outputs of the same
ΣK-1 drv (0 0c,4+1)
Ek=o dnv ((Zg...,
2z_1), (Zp
Zk+1))
drv Bin (T, 1ggak)
Bin T, T4
Lk=
/
72443
tan
v V1-22
v 1/1-724
(31)
T
tan
72k
Itan-
%
1-1
V1-78
=
2
lan
V1-yox²
728
TTyT
using the fact that f F:x: x + tan ( アーーzz
is increasing and convex x E [0. 1], and f(0) 0 and f(1) -T/2.
Finally, let D'y be a probability distribution on R such that supp(D',) n (D,) U supp supp(Dy)) 0, for any E [0, 1]. let g²(( (E) g² (5) if & supp(D,, U supp(D,), and (5) otherwise. Then, have (T, (3 ,D,, D,) 0z and
u(T, 00 t2 D.., D',) 1 Thus, have
ΣK-1 drv ( (O 0211,441)
= Ek'-t drv (U(T, Be.,i,,,,,,0 ,D, Dy), UT, 2012 ,D. D/))
< - 11
(32)
K' 11
((1-rp)-r1))
where K'
Combining the two inequalities concludes the proof.
2rr
We are now in position to prove Theorem 2.
Proof of Theorem 2. Combining Lemma B.1 (with = = and g' = -g²) and Lemma B.2, we have, for any 7 E [0, 1],
L²7² (1 (Pgr,,
min max E (I,, D,)) 27] 2 8
(33)
Meu CEFie
14

---

When to Forget ? Complexity Trade-offs in Machine Unlearning
where drv (rv(Pgr, P-gr) ) dnv
(Pgr, gr, Pgo) + (Poo P IYVT (1 (1-m/)--r (e - 11 8). Let c1, C2 E [0,1] and
7 c/vT. If (1-rgle rTTT -1) 1), (ee (ee-11 5) c2, then
L
min max -,,, ueD LEFec
(1
02),
(34)
8 ppT
2
(1-rt)/8pe - 1)
and thus, if
(e (e- c2.
1yl1 201
T, (1 C2) T z qee
(35)
r7
Finally, take 0 1/2, c1 such that - 02 1/3, and rewrite the condition
(1
8(1-ry)ap
62) (1
2
c- -1+8)
simple functional analysis gives that, for 10 S S e, we have
1
2 In 25 10a)
03 1 V 2 In (1(25///0)
1+ 2(e 1 8)
c3 1+
(36)
2(e 1 +1)
where C3 11/3321n(1222 105) and the desired result.
Using the same approach, a lower bound on the time complexity scratch can also derived.
Proof of Lemma 4.2. First, by strong convexity, we have
(, - C S (VC(0))
100012
(37)
Moreover, the convexity of 0 (0) ||0|] implies that (VL(-0), (0,) +,0, VL(0), O0,) and thus
3/ 0 2 LR
3p R²
I
(.( - - < V 0 |,;
(38)
8p
As consequence, i 2 ep. then T: = (and _ = 0). Let us now assume that e < Ep. First, note that this convergence
rate is achieved by stochastic gradient descent. For example, direct extension of Theorem 6.2 from Bubeck et al. (2015)
gives, after I' iterations of (stochastic) gradient descent fc+1 0 1h V Vol(Oe.C {e) with decreasing step-size T} p(++2)
2L
E
L
(0r)
min [(0) BERd
(39)
H(T + 2)
where 0r = IT-1
(1+1)(++2) 6,, and thus
2(++)
2L2
T S
(40)
μie
The lower bound is consequence of Theorem with Ke,5 0, algorithm retraining from scratch would not depend on the forget dataset, and thus have absolute privacy. particular, if < 122 (1 - xe1 ), we have 8
L2 (1 TC1 ) T > 8 qe 2
(41)
and as soon as e/co < for > 0, there exists a constant 02 > O such that 7.5 2 c2co/e.
15

---

When to Forget? ? Complexity Trade-offs in Machine Unlearning
C. Useful lemmas
In this section, we provide five lemmas that will be necessary to prove our upper and lower bounds (see sections above), as well as the proof for unleaming definition equivalence.
Lemma C.1.
Let 0 arg ming L, (0). Then, we have:
100 -0,1 S rf L --ry μ
(42)
Proof. By strong convexity of L, we have 10"-0;1 0711 S [V
Moreover, [O'| = (
B &.)] - where & D, and E, Dj, VL(0") = 0. Combining the two inequalities gives the desired result.
Lemma C.2.
rf 1
6. L S
(43)
1- rg)
μ
Proof. Let 0r;- = aarg ming (0). Then,
Ep, (e(0") {(0,)) = Ep (1(00) - {(O))) rf ED, (e(0") ((0)))
(44)
1-r9
rf ED, (e(0") - ((07))
$ 1 rj
(45)
$ rf L 00 0:1
(46)
ry
2 T
rf
(47)
1-rf
where the last inequality is given by Lemma C.I.
Lemma C.3. If the unlearning algorithm U verifies (e, -.nlearnnn,,,, then, for any triplet of distributions (D,, D,, D'y) we have
dry
- - -1
(48)
Proof. By (e, -Unnlarmnn,, we have, for any $ c R PD, S e PRU D') E S] + 6, and thus
EJ
E S] < 11) PP, D') 5 1
(49)
The converse relation with D, and D' exchanged leads to a bound on the absolute value, and thus the desired result.
Proof of Lemma 1.1. Let Do be an arbitrary distribution, e.g., the uniform distribution on the R/l-ball. Let 2/ E U be an (e, -0nlernnng algorithm. Let U e U be an (c, (encc-unngg algorithm. Then, the algorithm Ao (T, (T,,, uT,11, L,,,, Do) such that for any couple of distributions (D,, Dy) over (0,, R) and subset 5 C Rd..
()) e S] S.P Da) E S]+ + = E[ S] Do) E s] < ef PP, Dy) S +
thus an (e, ( Reffrrnce Unlearning algorithm. This proves the first implication.
Let U U be an (e, Refeerece Unlearning algorithm and A E its reference algorithm. Let D,, Dy, D', be three distributions over BO0, R). Then,
P(((D,, Dj) E Se PLA(D,) E S)+ 5 el (e P(U(D,,)))) E E +)) +
(50)
thus an (2e, (1 + exp(e))6) (op(<))o)-Referennce) Reference Unlearning algorithm. This concludes the proof.
16

---

When to Forget ? Complexity Trade-offs in Machine Unlearning
Lemma CA. Let A E A be an iterative algorithm as defined in Algorithm 1. Then, there exists T i.i.d random variables "Dr and measurable fianction A such that, for ant T > 0, 0o IR. and R + {-1,1} have
( (,,,,) = (0 ((6), ...., (........()))))))
(51)
Proof. Let (ma, 0t) be the memory state and current parameter of algorithm iteration (see algorithm 1). First, for T = my 0 and Og are both (trivially) measurable functions of 0u. Then, by recursion, if both my-1 and 0r-1 measurable functions of Oo (((. (()-))) then
(mr, 0r) A(m,, V (r))) A(mr-1, p0r-1 2 w)
(52)
which is measurable function of 0o (Eo) ... ((rr-1), This concludes the proof.
Lemma C.5. Let T 2 and 7,7 E [-1, Then, we have
Bin T, - ,Bin TT:22 2
1177
1
VT tan
V1 g22 (}
2 Lan
?
drv
(53)
V1 VI-22
Proof. Assume that > 2 7, and let 4077 >)) = dıv Bin (T, - Bin (T, (r))
The proof relies on bounding the
derivative of & with respect to its second variable. Let y + where then
707,7 + E)
E
(X)
Prxxx
1 E
1
(1 (1+2++))
(1+7)*
E
1
(1 + X I+7
(T - (-)
(54)
x (T x) 1 ((?)
2(14)
(147) V [1- + (
Var(X)
1- + (
where P., is the density of the binomial distribution Bin (T, 1 and X Bin (T, ) verifies the triangular inequality, we have
As the total variation distance
drv
1+7 Bin (7, T, 2
Bin T, 1 1 < /' p(u, u+du) 5
VT
lan -1
/1 V1-1"2
7'
-tan -1
7
2
2
/
(55)
D. Experimental Details
In order to produce Fig. 2, we optimized a standard cross-cntrops loss with L2 regularization (of weight 1). We used a batch-size 64 and trained until the threshold e was reached, for every chosen value of Kg,5. The values of e (resp. ka,6) are chosen regularly spaced on the linear scale between 5 10 6 and 10 (resp. 10 and 102). The optimized used the standard SGD optimizer without acceleration. The learning rate is initialised at 10-2 and multiplied by 0.6 every 1000 epoch. Each experiment is repeated 50 times and the results are then averaged.
17


Reviews:
[{"review_id": "gsSR9vUdHC", "reviewer": "Reviewer_ak4V", "summary": "In this paper, the authors studied the complexity trade-offs of machine unlearning, in particular, at which conditions, unlearning can outperform retraining from scratch regarding the efficiency or unlearning cannot bring any benefits. To accomplish this, the authors proposed to leverage a phase diagram to reveal these regions, which is supported by the authors' rigorous theoretical analysis throughout the paper.\n\n\n\n## update after rebuttal\nI went over the authors' responses and other reviewers' comments. I think the authors have adequately addressed all of our comments, in particular, our concerns about the real datasets. Since all of us lean to accept this paper, I would love to increase the score to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank *Reviewer ak4V* for their detailed feedback on our work, and we especially appreciate their focus on the theoretical elements of the paper. Here is a point-by-point response to their questions: $$ $$\n\n- **Link to non DP-based unlearning papers:** There are indeed several ways of achieved certified unlearning besides DP-based MU methods. While we have mentioned some of them in the literature review, including *Bourtoule et al*’s \"Machine Unlearning\" paper, it is true that our work would benefit from discussing these elements in more details later in the analysis. Indeed, there is no direct equivalence between DP-based guarantees and the type of guarantees offered by order two methods like \"Deltagrad\" or exact unlearning methods like SISA (from *Bourtoule*’s work).  \nHowever, our impossibility result in Theorem 3 has interesting consequences as to the feasibility of exact unlearning in our setup. Since the \"unlearn\" and \"retrain\" distributions ought to be the exact same in exact unlearning, it implies (0,0)-Unlearning as defined in Definition 1. Thus, $\\kappa_{\\epsilon,\\delta}=\\infty$ and Theorem 2 implies that $T^U_e$ cannot asymptotically improve over $T^S_e$, regardless of $e$. Note that this result does not contradict the potential efficiency of exact unlearning methods since they usually rely on a modification of the training process, which is outside of the theoretical framework laid-out in this paper.  \nAs for the link between second-order and first-order unlearning, since the unlearning guarantees used are very different by nature, they are hardly comparable theoretically. However, auditing first and second-order MU methods and their relative resilience to various attacks would be a valuable research direction and is left to future works. $$ $$\n\n\n- **Role played by Algorithm 2**: The exact role that Algorithm 2 holds in our paper is indeed a subtle question, that we are happy to expand upon. Please be assured that the following elements will be included in our final version.\nIn our analysis, we rely on Alg. 2 solely in order to show the existence of efficient first-order unlearning algorithms, but our analysis characterises the behaviour of every first-order algorithm as long as it relies only on the retain set. Indeed, Alg. 2 is only used in the proof of Theorem 3 to characterize the regime in which we know that unlearning algorithms can outperform retraining asymptotically. Therefore, the boundaries of the IR and TR are independent from Alg. 2, which is only used in Theorem 3 to describe the ER. $$ $$\n\n\n- **Theorem 3 and the Efficient Regime:** We thank the reviewer for pointing out a potential source of confusion for readers, as Theorem 3 is in essence not a result that delimits the efficient regime, but rather shows that efficient methods do exist in this regime. In particular, Theorem 3 only provides the unlearning time for Alg. 2, which happens to improve upon retraining from scratch precisely in the efficient regime. To improve readability, we have decided to rename Theorem 3 as *\"noise and fine tune efficiency\"*, and add the following corollary to this theorem:  \n**Corollary (Efficient regime).** There exists a universal constant $c > 0$ such\nthat, for any $\\gamma\\in(0,1)$, if $e \\geq \\frac{c}{\\gamma} \\left(\\frac{r_f}{1-r_f}\\right)^2 \\left(1+d\\kappa_{\\varepsilon,\\delta}^2\\right) e_0$, then\n$$\n\\frac{T^U_e}{T^S_e} < \\gamma.\n$$\n\n\n- **Experiments on Real Datasets:**\nFollowing the reviewer’s suggestion, we conducted additional experiments using the standard [real-world dataset \"Digits\" of handwritten numbers](https://scikit-learn.org/1.5/auto_examples/datasets/plot_digits_last_image.html) to further validate our theoretical findings. We are pleased to report that the three regimes predicted by our theory can be observed in these experiments, as illustrated [here (anonymized link)](https://anonymous.4open.science/r/Submission6456/figure.pdf). Additional experimental details are provided in the second part of our response to *Reviewer KpLi*.", "claims_and_evidence": "Most claims of the paper look fine to me.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation make sense to me.", "theoretical_claims": "The theoretical claims and analysis look fine to me.", "experimental_designs_or_analyses": "Yes, I checked the experimental designs and analyses. I feel that the authors may need additional experiments on real datasets to justify the theoretical results in this paper.", "relation_to_broader_scientific_literature": "The contributions of this paper are closely related to the area of machine unlearning.", "essential_references_not_discussed": "I think the authors primarily focus on one type of machine unlearning approach. It would be better if the authors could incorporate some discussion in the paper to discuss the connections of the proposed approach to other machine unlearning approaches, in particular, those not dependent on adding gaussian noises, say Bourtoule, Lucas, Varun Chandrasekaran, 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), pp. 141-159. IEEE, 2021.  and Wu, Yinjun, Edgar Dobriban, and Susan Davidson. \"Deltagrad: Rapid retraining of machine learning models.\" In International Conference on Machine Learning, pp. 10355-10366. PMLR, 2020.", "other_strengths_and_weaknesses": "Strengths:\n+ The authors have done a series of theoretical analyses to reveal the complexity trade-offs in machine unlearning, which is perfect.\n+ The authors' overall presentation is clear and easy to follow\n+ The authors also performed some empirical studies, which can justify the phase diagram proposed by them.\n\nWeakness:\n- One of my biggest concerns is that the analysis conducted in this paper is closely tied to Algorithm 2. I am not sure whether the analysis could apply to general scenarios. Maybe I missed something but it would be great if the authors could have some discussion on this. \n- I think it would be better if the authors could perform experiments on real datasets rather than synthetic ones to verify their findings. If the results on real datasets match their analysis, that would be more convincing\n- I also feel a little confused about Theorem 3. Based on my understanding, this theorem should correspond to the ER area in Figure 1, right? According to Figure 1, the ER area only appears between $a * \\frac{e}{e_0}$ and $b * \\frac{e}{e_0}$ where $0 < a < b < 1$ for any fixed $k_{\\epsilon, \\delta}$. But it seems to me that Theorem 3 applied to any $e$ smaller than $e_0$. Although the authors attempt to have this discussion in paragraphs after Theorem 3, I still feel that more clarification would be essential (perhaps by combining Figure 1).", "other_comments_or_suggestions": "See above comments", "questions_for_authors": "See above comments", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9kJ8ZtZkaM", "reviewer": "Reviewer_KpLi", "summary": "This paper proposes a novel efficiency-oriented metric for machine unlearning. Based on the training resources required for a retrained model, it measures the efficiency of machine unlearning with respect to the size of the forget set and introduces three different regimes. The first regime addresses cases where unlearning can be achieved with minimal cost, while the second and third regimes deal with the lower and upper bounds of the complexity ratio, respectively. The paper empirically demonstrates the validity of these regimes through experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank *Reviewer KpLi* for their insights and appreciate their practice-oriented review of our paper. We think adding the following discussion to the final version of the paper will benefit it greatly. $$  $$\n\n- **Choice of experiments:** Our work studies the ratio of \"worst case\" unlearning and retraining time, meaning that the we bound the convergence time for every algorithm when optimising over the hardest possible functions. Our theoretical analysis is based on \"worst-case\" functions that have forms such as the one described in Eq. 26, used to prove lower bounds on convergence speeds: $\\ell^g(\\boldsymbol{\\theta}, \\xi) = \\frac{\\mu}{2} \\|\\boldsymbol{\\theta}\\|^2 - \\frac{L}{2} g(\\xi) \\theta_1$.\nTherefore, in order to assess the relevance and significance of our theoretical analysis, it makes sense to empirically evaluate how fast unlearning and retraining algorithms go when optimising functions of this form.  \nWe started by optimizing over this loss function directly, but faced two issues.\nThe first and most significant was that we did not observe the linear delimitation between TR and ER theorized in Theorem 1, the second was numerical instability. The first problem occurred because of the smoothness of the function: since Theorem 1 does not assume smoothness of the loss and Eq 26. provides a smooth loss, TR expanded beyond what was expected, forming a square root boundary rather than a linear one.  \nFor this reason, we introduced non-smoothness in the form of an $L1$ penalty, making the loss: $\\ell^g(\\boldsymbol{\\theta}, \\xi) = \\frac{\\mu}{2} \\|\\boldsymbol{\\theta}\\|^2 - \\frac{L}{2} g(\\xi) \\theta_1 + \\lambda \\|\\boldsymbol{\\theta}_{2:d}\\|_1$, which fixed the issue and provided a loss function better-aligned with the theory. The second issue was numerical instability: since every parameter but the first one was quickly decreasing to $0$, the remaining task was optimising over the first parameter. The first parameter naturally oscillated between values over and under the optimal one, resulting in a noisy process that could converge prematurely by chance. Therefore, we chose to expand the loss on the first parameter to half of the model's parameters, solving the second issue, and making the loss  \n\n$$\\ell^g(\\boldsymbol{\\theta}, \\xi) = \\frac{\\mu}{2} \\left\\|\\boldsymbol{\\theta}\\right\\|^2 - \\frac{L}{4} g(\\xi) \\sum_{i=1}^{d/2} \\theta_i + \\frac{L}{4} \\sum_{i=d/2 + 1}^{d} \\left|\\theta_i\\right|.$$ While uncommon, it represents a hard loss function that verifies every assumption made in the paper, which is why we chose it to perform our experiments.\n$$ $$\n\n- **Practical applicability of the experiments:** In order to asses the practical applicability of our theory, we corroborated our experimental results with additional experiments on [the real-world dataset \"Digits\" from sklearn](https://scikit-learn.org/1.5/auto_examples/datasets/plot_digits_last_image.html). We performed a logistic regression on this well-known dataset of handwritten digits. We used a standard cross-entropy loss with $L2$ weight regularisation (thus ensuring strong convexity and Lipschitzness of the loss) to train a linear classifier on the data, and compare unlearning and retraining times, as done in Figure 2. [The result for the experiment is available at this anonymised link](https://anonymous.4open.science/r/Submission6456/figure.pdf), in compliance with the [ICML 2025 Peer Review FAQ](https://icml.cc/Conferences/2025/PeerReviewFAQ). Additionally, since adding this new experiment broadens the scope of the experimental section and further verifies our theoretical findings, we will include them in the updated version of the paper. The specific hyperparameters used to generate this figure are: batch size of $64$, use of SGD with a starting learning rate of $0.01$, decaying by a factor of $0.6$ every $1000$ batch, with a penalty weight of $1$ and results averaged over $50$ seeds. \n$$ $$\n\n- **Mention of non DP-based unlearning methods:** While we do mention several unlearning methods  with both no unlearning guarantees and with non DP-based guarantees in the first and second paragraphs of our literature review, we will include an additional discussion on the link between these papers and our, as explained in more details in our response to *Reviewer ak4V*.", "claims_and_evidence": "It is positive that the authors clearly present their claims through Assumptions, Theorems, and Corollaries. However, the empirical evidence supporting the existence of such regimes does not appear to be sufficient. The paper only provides experiments on a limited set of settings, and it does not demonstrate how generally these regimes hold.", "methods_and_evaluation_criteria": "As I mentioned earlier, I do not think the paper has conducted an adequate evaluation on this point. However, I am not fully confident in this judgment. To me, this paper appears to be more theory-focused rather than practical, and since I am more of a practitioner than a theorist, it is possible that my evaluation is biased due to my limited perspective. Therefore, I plan to further assess this aspect through discussions with other reviewers during the discussion period.", "theoretical_claims": "The paper presents theoretical theorems for the three regimes. Although I have read through the logical arguments, I have not verified them rigorously.", "experimental_designs_or_analyses": "The argument on this point does not seem very convincing to me. I hope the authors will provide a thorough explanation in the rebuttal as to why the experiments presented in the paper are sufficient.", "relation_to_broader_scientific_literature": "The paper appears to focus primarily on reviewing DP-based unlearning methods, and I am not sure if this is sufficient. It would have been better if the authors had also mentioned machine unlearning literature from a more practical perspective. However, since the main contribution of this paper lies in providing a theoretical foundation, I consider this a minor concern.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The strength of the paper is that it is well-written and easy to understand, while the weakness is that the experiments are not sufficiently thorough. Please refer to the above comments for more details.", "other_comments_or_suggestions": "The strength of the paper is that it is well-written and easy to follow, while the weakness is that the experiments are not sufficiently comprehensive. Please refer to the above sections for more detailed comments.", "questions_for_authors": "It seems necessary for the authors to provide an explanation of why the current evaluation in the paper is sufficient. As it stands, I am not fully convinced, and therefore, I find it difficult to recommend acceptance at this point.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VEeSESwSmw", "reviewer": "Reviewer_qtfk", "summary": "In this paper, the author revisits the machine unlearning topic and analyzes the efficiency of unlearning methods. The author defines a complexity ratio metric that compares the computation costs of the unlearning method and full model retraining. A phase diagram is drawn based on the complexity ratio and reveals three distinct regimes, which are impossible unlearning, efficient unlearning, and trivial unlearning, respectively. Based on the phase diagram, it answers the question about which would be the most efficient way to achieve the unlearning purpose under certain conditions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank *Reviewer qtfk* for their positive review of our work and their attention to rigour. Here are our answers to their main comments. $$ $$\n\n- Missing introduction of quantities: We thank the reviewer for pointing out two omissions that affect the clarity of the paper. We appreciate their careful reading and the opportunity to address these issues. $T^U_e$ and $T^S_e$ will be properly introduced, as well as $e$, by this modification of lines 50 to 55: \n> \"Specifically, in a general machine learning setting, let us define $r_f$ as the fraction of data in the forget set, and $e$ as the excess risk—that is, the gap in loss between a learned model and the optimal one. We denote by $T^U_e$ (resp. $T^S_e$) the time required for an algorithm to unlearn the forget set (resp. to retrain from scratch without the forget set) until the excess risk falls below $e$. Note that *time* is here measured by the number of accesses to gradients of individual data points, and thus assumes that gradient computation is the main computation bottleneck.\" \n\n$$ $$\n\n- **Limitations of the proposed theory:** Our theoretical analysis is limited in its scope, as discussed in the conclusion, by the assumptions we make: strong-convexity of the objective, first-order of the algorithms, dependence only on the retain set of the unlearning algorithms, and verification of Assumption 2. Additional limitations include the tightness of our analysis since our bound from Theorem 3 scales with $\\sqrt{d}$, which is not matched by our lower bound in Theorem 2, as discussed in subsection 4.5, and the potential non-optimality of Alg. 2, as discussed in subsection 5.2. The reviewer is right in pointing-out that these points are dispersed throughout the paper and we will make sure to group them in our final manuscript.\n$$ $$\n\n- **Experiments on Real Datasets:**\nFollowing the reviewer’s suggestion, we conducted additional experiments using the standard [real-world dataset \"Digits\" of handwritten numbers](https://scikit-learn.org/1.5/auto_examples/datasets/plot_digits_last_image.html) to further validate our theoretical findings. We are pleased to report that the three regimes predicted by our theory can be observed in these experiments, as illustrated [here (anonymized link)](https://anonymous.4open.science/r/Submission6456/figure.pdf). Additional experimental details are provided in the second part of our response to *Reviewer KpLi*.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The author summarizes many interesting and meaningful insights, which are helpful and can be considered as guidelines for future research in the field of machine unlearning.", "essential_references_not_discussed": "Yes", "other_strengths_and_weaknesses": "Strength:\n* This paper is well-organized.\n* The author summarizes many interesting and meaningful insights, which are helpful and can be considered as guidelines for future research in the field of machine unlearning.\n* The authors provide extensive theoretical evidence to support their claims.\n\nWeakness:\n* In the introduction section, the author defined TS as the stochastic gradient steps required to unlearn by retraining from scratch. But the definition of TU is missing. And here the author defines the T as the steps, where the next sentence says the ratio of time required. Note that the ratio of the number of steps and the ratio of time required is different.\n* The author does not explain what the excess risk e is.\n* It would be better if the author could have a more comprehensive discussion on the limitations of the proposed theory.\n* The evaluation part lacks some practical cases to prove the feasibility of the proposed theory.", "other_comments_or_suggestions": "In the introduction section, the author mentioned “we provide the first lower bound for the unlearning complexity ratio, answering an open problem in the literature (Allouah et al., 2024)…”. It would be better to explicitly describe what the open problem is.", "questions_for_authors": "Please refer to the weakness part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bAN1lwHHyR", "reviewer": "Reviewer_tKga", "summary": "The paper considers machine unlearning for strongly convex objective functions and under the assumption that the forget set is inaccessible to the unlearning method. The paper provides and proves some theoretical lower and upper bounds on the ratio of the number of training iterations needed by unlearning from the fully trained model and retraining from the initial model to achieve a given excess risk threshold. The bound depends on the weight of the forget set and data dimensionality. The paper identifies three regimes where 1) trivial unlearning is possible by adding noise to the parameters, 2) unlearning is inefficient (impossible) and does not asymptotically improve the number of iterations and 3) efficient unlearning is possible by adding noise before fine tuning with stochastic gradient descent.\n\n## update after rebuttal\nThe authors have satisfactorily addressed my concerns and my review was already positive.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank *Reviewer tKga* for their in-depth review and detailed analysis of our theoretical work. We address their comments below and will make sure to include the corrected elements into the final version. $$ $$\n\n- **Impossible VS Inefficient Unlearning:** You are correct in saying that unlearning in this regime is inefficient rather than impossible. Therefore, we will rename IR to \"Inefficient Unlearning\" in the final manuscript. $$ $$\n\n- **Form of the loss function:** The loss function we rely on is inspired from Eq. 26 in order to represent a loss of the \"worst-case\" type we study in our theoretical analysis. However, it is adapted in order to be both harder (non-smooth) and yield more stable results, as explained in details in our response to *Reviewer KpLi*. $$ $$\n\n- **Experiments on Real Datasets:**\nFollowing the reviewer’s suggestion, we conducted additional experiments using the standard [real-world dataset \"Digits\" of handwritten numbers](https://scikit-learn.org/1.5/auto_examples/datasets/plot_digits_last_image.html) to further validate our theoretical findings. We are pleased to report that the three regimes predicted by our theory can be observed in these experiments, as illustrated [here (anonymized link)](https://anonymous.4open.science/r/Submission6456/figure.pdf). Additional experimental details are provided in the second part of our response to Reviewer KpLi. $$ $$\n\n- **Non Standard Definitions:** Our first unlearning definition (Definition 1) is indeed worded differently from other works, but remains close to what other papers in the literature have used, see e.g. [Georgiev et al](https://arxiv.org/pdf/2410.23232)'s Definition 2, [Chourasia et al](https://arxiv.org/pdf/2210.08911)'s Definition 2.4 where the forget set is taken as any subset of the overall dataset. While our Definition 2 is indeed unusual, it relies on the same principles and implicitly uses the concept of neighboring dataset: If $\\mathcal{D}_f$ and $\\mathcal{D}_f'$ are of size $k$, then the total datasets $\\mathcal{D}_r \\cup \\mathcal{D}_f$ and $\\mathcal{D}_r \\cup \\mathcal{D}_f'$ are $k$-neighbors. It is common for the overall datasets to be neighbors in unlearning definitions, but this is usually not the case for forget sets. $$ $$\n\n- **Out-of-distribution data handling:** In our analysis, there indeed is no direct analysis of the in- vs out-of-distribution character of the data. We do not make specific assumptions on the data as to the distribution they follow. $$ $$\n\n- **Verification and explanation of Ass. 2:** Assumption 2 is a technical assumption needed for the proofs. We believe it could be lifted with little change in term of results but the analysis would be made significantly heavier.\nThere are two principal elements to Assumption 2: the existence of $A$ such that $\\mathbb{P}(\\xi_r \\in A) = p$ where $\\xi_r \\sim \\mathcal{D}_r$, and the existence of another data distribution $\\mathcal{D}_f'$. The second point is relatively trivial if, as stated in the article,  \"$supp(\\mathcal{D}_r)$ and $supp(\\mathcal{D}_f)$ do not cover the whole space. The first point is a consequence of the Intermediate Value Theorem: Define $f(r) = \\mathbb{P}(X \\in B(0,r))$. By the continuity of the density, $f$ is continuous, with $f(0)=0$ and $lim f(r)=1$. By the Intermediate Value Theorem, for every $p\\in [0,1]$ there exists an $r_p \\ge 0$ such that $f(r_p)=p$.\n\n- **Lemma C.1:** We are grateful for the reviewer’s attention to detail and will add the missing expectations, that indeed hold on the retain set, then forget set, respectively.", "claims_and_evidence": "The claims made are supported by clear and convincing evidence. However, there are some minor issues\n1) The paper makes the strong assumption of strongly convex and Lipschitz smooth loss functions. While this seems standard in previous work, their applicability in practice needs to be clarified. \n2) Definitions 1 and 2 are slightly non-standard and strong as they are for _any_ forget sets. In the usual DP definitions, there is some constraints regarding neighbouring forget sets. \n3) In Section 4.3, inefficient unlearning seems to be a more appropriate description than impossible unlearning. Unlearning is possible and may even more efficient but the speedup is not an asymptotic order.", "methods_and_evaluation_criteria": "Not applicable, this is a theory work.", "theoretical_claims": "I have checked the correctness of proofs in Appendix A and C.\nIn the proof of Lemma C.1, the distribution which the expectation is taken w.r.t. should be stated. It is first on the retain set, then on the forget set. if r_f > .5, the bound can just be L.\nIn the proof of Theorem 2, the connection between Eq (36) and the claim in Theorem 2 is not immediately clear. The readability and clarity of the proofs can be enhanced.", "experimental_designs_or_analyses": "There is only one experiment on linear regression model on synthetic function and dataset instead of real world datasets such as the Californian Housing dataset.\nI am not sure why the expected loss function in line 389 is used over other loss functions.", "relation_to_broader_scientific_literature": "(Chourasia and Shah, 2023; Allouah et al., 2024) have identified upper-bounds on the number of gradient steps needed by their specific MU algorithm and retraining to achieve unlearning.\nThe paper identified lower and upper bounds of the ratio of the number of training iterations needed by unlearning from the fully trained model and retraining from the initial model to achieve a given excess risk threshold. The bounds would hold for any stochastic, iterative, first-order learning algorithm.", "essential_references_not_discussed": "Essential references (Chourasia and Shah, 2023; Allouah et al., 2024) are discussed.", "other_strengths_and_weaknesses": "**Strengths**\n1. The paper and mathematical definitions (especially Section 1-3) are well-written and clear.\n2. The paper provides novel and important theoretical insights that would work for any stochastic, iterative and first-order algorithm.\n\n**Weaknesses**\n1. The experiments are limited. It is on a synthetic dataset and loss function.", "other_comments_or_suggestions": "Typos\n*  In Sec 4, there should a brief summary about how each theorem is proven. For example, Theorem 1 uses the MU algorithm that adds Gaussian noise to the previous optimum\n* \"Let the unlearning algorithm consist in simply\" in line 554\n* Distribution expectation is taken w.r.t. in Lemma C.1 proof is missing", "questions_for_authors": "1. Allouah et al., 2024 have separate results from out of distribution data. How do out of distribution data affect your theoretical guarantees? The DP-based MU algorithms and definition seem to work for any dataset as long as the weight on the forget set is fixed. The response would make the difference between both papers clearer.\n3. Explain assumption 2 and why it is \"verified for continuous distribution\"\n4. Why is it appropriate to use the expected loss function in line 389 over other loss functions? The response would affect the evaluation of the experiments", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Overall, I think this is a solid contribution with the following strengths:
- The paper considers a specific form of machine unlearning algorithm that does not require access to the forget set, and establishes asymptotic conditions under which unlearning can be trivial, efficient or inefficient relative to the re-training (from scratch) unlearning scheme.
- The paper validates this theoretical finding on a couple of real datasets with a loss function that satisfies the necessary assumptions.

Overall, this is an interesting paper that tries to provide deeper insights into the area of machine unlearning. The reviewers raised some valid concerns which the authors appeared to satisfactorily address in the author responses. One limitation is that this form of analysis is specific to a specific class of unlearning algorithms, and it does not say much about other forms of unlearning algorithms. However, the authors do clearly acknowledge this limitations.
Decision: Accept (poster)