The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning
Authors: Youssef Allouah
Joshua Kazdan
Rachid Guerraoui
Sanmi Koyejo
Venue: ICLR 2025 Poster (2025)
Keywords: machine unlearning
differential privacy
optimization
theory
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Machine unlearning, the process of selectively removing data from trained models, is increasingly crucial for addressing privacy concerns and knowledge gaps post-deployment. Despite this importance, existing approaches are often heuristic and lack formal guarantees. In this paper, we analyze the fundamental utility, time, and space complexity trade-offs of approximate unlearning, providing rigorous certification analogous to differential privacy. For in-distribution forget data—data similar to the retain set—we show that a surprisingly simple and general procedure, empirical risk minimization with output perturbation, achieves tight unlearning-utility-complexity trade-offs, addressing a previous theoretical gap on the separation from unlearning ``for free" via differential privacy, which inherently facilitates the removal of such data. However, such techniques fail with out-of-distribution forget data—data significantly different from the retain set—where unlearning time complexity can exceed that of retraining, even for a single sample. To address this, we propose a new robust and noisy gradient descent variant that provably amortizes unlearning time complexity without compromising utility.

Published as a conference paper at ICLR 2025
THE UTILITY AND COMPLEXITY OF IN- AND OUT-OF- DISTRIBUTION MACHINE UNLEARNING
Youssef Allouah Joshua Kazdan', Rachid Guerraoui', Sanmi Koyejo²
'EPFL, Switzerland Stanford University, USA youssef a aoouaahepp.. ch, sanmiccs stanford.edl
ABSTRACT
Machine unlearning, the process of selectively removing data from trained models, is increasingly crucial for addressing privacy concerns and knowledge gaps post- deployment. Despite this importance, existing approaches are often heuristic and lack formal guarantees. In this paper, we analyze the fundamental utility, time, and space complexity trade-offs of approximate unlearning, providing rigorous certification analogous to differential privacy. For in-distribution forget data data similar to the retain set-we show that a surprisingly simple and general procedure, empirical risk minimization with output perturbation, achieves tight unlearning- compiy-cooplexity trade-offs,, addressing a previous theoretical gap on the separation from unlearning "for free" via differential privacy, which inherently facilitates the removal of such data. However, such techniques fail with -uitt--iistriuution forget data-data significantly different from the retain set-where unlearning time complexity can exceed that of retraining, even for a single sample. To address this, we propose new robust and noisy gradient descent variant that provably amortizes unlearning time complexity without compromising utility.
INTRODUCTION
The ability selectively remove "forget" portions of the training data from model is a crucial challenge in modern machine learning. As deep neural networks are widely deployed across diverse domains like computer vision, natural language processing, and healthcare, there growing need to provide individuals with granular control over their data. This need is amplified by stringent regulations like the European Union's General Data Protection Regulation (GDPR) (Voigt and Von dem Bussche 2017). which enshrines the "right to be forgotten," mandating data erasure upon request. Machine unlearning is designed to address this regulatory necessity by systematically removing the influence of specific training examples without compromising model performance.
Recent years have seen growing interest in developing algorithms that can efficiently "unlearn" data (Bourtoule et al., 202 Nguyen al. 2022 Foster et al. 2024).. The proposed approaches range from methods like tine-tuning on the retained data while increasing loss on the forget data (Graves) al. 2024), to more sophisticated techniques that provoke catastrophic
ct al. 2021 Kurmanji forgetting by fine-tuning specific model layers (Goel et al. (022). Unfortunately. many of these methods lack formal guarantees, rendering it unclear when they comply with regulatory standards.
Unlcarning guarantees fall into two main categories: exact and approximate. Exact unlcarning guarantees that the unlearned model has never used the forget data, often relying sharding- baased strategies (Bourtoule et al., 2021), which can be space-inefficient and lack error bounds. In contrast, approximate unlearning ensures only that the unlearned model is statistically close one retrained from scratch without the forget data, akin to the protections offered by differential privacy (Dwork) al. 2014). While approximate unlearning provides a more feasible path in terms of efficiency and practicality, it has yet to fully address certain key challenges.
Although several prior works have explored approximate unlearning (Ginart et al. 2019 Neel et al.
2021 Chourasia and Shah 2023), the theoretical understanding of the complety trade-offs remains incomplete. This particularly true for challenging scenarios, such as when the forget data out-of-distributio or adversarial. Such cases are highly relevant to practice, given the heterogeneity of user data and the observation that deletion requests are often non-random (Marchant et al. (022).
Work done while Stanford University.

---

Published as a conference paper at ICLR 2025
Addressing these challenges is crucial for making machine unleamiing practical and reliable tool for real-world applications, where models must adapt to diverse data and privacy requirements.
Contributions. Our work draws comprchensive landscape of the complextyy trade-offs in approximate unlearning. We tackle two complementary unlearning scenarios: the in-distribution case where the forget data is an arbitrary subset of samples from the test distribution, and we initiate the study of the out-of-distributiio scenario where the forget data may arbitrarily deviate from the test distribution. In particular, our results precisely quantify the number of samples that can be deleted under fixed utility and computation budgets, assuming the empirical loss has a unique global minimum. We analyze the eeetarning-trrining pair consisting of generic optimization procedure and output perturbation, and show that it can unlearn a constant fraction of the dataset. independently of the model dimension, thereby settling a theoretical question by /Skharii al. (202T) and highlighting a tight separation with differential privacy. In the case of out-of-distributton forget data however, we show that this approach can fail to unlearn single sample in the worst case. We propose a new algorithm using robust and efficient variant of gradient descent during training, which ensures good initialization for unlearning independently of the forget data. We show that this algorithm can certifiably unlearn constant fraction of the dataset, with hear-linear time and space complexities.
1.1 RELATED WORK
The concept of machine unlearning, introduced by Cao and Yang (015), has gained significant attention following the introduction of data-privacy laws, such as GDPR, which mandates that companies must delete user data upon request. Cao and Yang (2015) studied exact unlearning, where the unlearned model behaves as if it had never used the forget data, deterministically mimicking retraining from scratch. However, this strict approach is only feasible for highly structured problems. Bourtoule et al. (2021) I tackled this challenge with partitioning strategy. training ensemble models on different data shards. While this approach reduces the need for full retraining when deleting data, it incurs high space complexity and lacks utility guarantees.
To address the impracticalities of exact unlearning, researchers have shifted focus to approximate unlearning, relaxation of exact unlearning. Ginart al. (2019) pioneered this direction, proposing that an unlearned model should be statistically indistinguishable from one retrained without the
forget data, similar to the guarantees offered by differential privacy (Dwork al., 2014). This laid the foundation for spectrum of algorithms that balance computational efficiency and approximate unlearning guarantees (Guo al.] 20200 Izzo et al. 2021 Golatkar al. 2021 Gupta al. 2021
Neel et al. 2021: Chourasia and Shah, 2023).
Certified unlearning. A growing body of work focuses on providing guarantees for approximate
unlearning. particularly for convex learning problems (Guo et al. 20200] Neel et al.] [202]] Sekhari jet al. 2021). Methods such as gradient descent with output perturbation (Neel et al. 20211) have proven effective in the convex case, even with sequential deletion requests. However, little is known about the generalization guarantees of such approaches, even in the convex case. Notably, (Seharii et al. I2021) first proved generalization guarantees for unlearning with Newton step and output perturbation (Guo et al.] 2020), uncovering a separation with differential privacy. Specifically, differential privacy without an unlearning mechanism is inherently limited in the number of deletions it can handle, while maintaining fixed utility on the test loss, a result further tightened by Huang and Canonne (0023). Our work improves upon this by showing that gradient descent with output perturbation offers sharper guarantees. Moreover, we demonstrate that this approach cannot be further improved in general, based on lower bounds from robust mean estimation (Diakonikolas et al. 2019).
Unlcarning -nttof-distribution data. Despite advances in certified unlearning, most approaches assume that the forget data is drawn from the same distribution as the training data, leaving out-of- distribution (OOD) data and adversarially corrupted forget data underexplored. Recent works (Goel al. 2024: Pawelezyk et al. 2024) highlight the complexities that arise when deletion requests target OOD or corrupted samples. These scenarios are especially relevant given that deletion requests are often non-random, originating from diverse and heterogeneous data sources. Moreover, studies like Marchant et al. (2022) have demonstrated that OOD data can be manipulated to slow down certified unlearning algorithms, triggering retraining and causing ofnial-of-service-- like attacks. Our work addresses these issues by introducing
unlearning algorithm that is robust to OOD and corrupted data. The algorithm achieves near-linear time complexity for unlearning, independently of the nature of the forget data, and thus is provably robust against attacks like Marchant et al. (2022).
2

---

Published as a conference paper at ICLR 2025
2 PROBLEM STATEMENT
Consider a training set S made of n examples independently drawn from distribution D over data space 2, and loss function E: IRd x 2 - R. Our goal is to minimize the population risk:
min OER
( = EZ-D [e(0:
(1)
During the training phase, we aim at solving the empirical risk minimization problem:
min
L(0:S)
((0:2).
OER2
S| ZES
Let A denote the training procedure aimed solving (2) on the full dataset S, producing model A(S) E Rd. Next, consider a scenario where a subset S C S of size f := [ referred to as the forger set, needs to be removed. The goal is then update the model based on the retain set S A.y. Ideally, one would retrain using only the retain set with A. However, due to time and space constraints, an approximate unlearning procedure U/ is used, which modifies the original model A(S), knowing the forget data Sy, to be as close as possible to A(S Sy).
Paraphrasing prior definitions (Ginart al. 2019 Neel approximate unlearning as statistical indistinguishabilig between the unlearned model and the model trained without the forget data. We denote by Z = Uk>1 Z² the space of datasets with elements in 2. i.e., S E Z* if and only if it is a tuple of data points from Z.
2021 Sekhari et al., 2021 we formalize
Definition 1 ((g, -aapproximate unlearning). Let q > 1, 2 and S CCS Z'. Let A: 2" Rd be a training procedure, and Z' R + R be a randomized unlearning procedure. The pair (U, A) achieves (g, E) apprrxxmaae unlearning, on training set S with forget set Sy. if D((U(S;,A(S)) [1, A(S), (s))) S,
(3)
where Dg(- II. the Rényi divergence of order q between the probability distributions of its arguments, defined for every P2 as (y(P) P2) = - log (X( Ps(X)
Above, ; A(S)) is the unlearned model and U( A(S Sy)) is the model trained without the forget data and no unlearning request. The guarantee conveys similar semantics to differential privacy (Dwork et al. 2014); an adversary cannot confidently distinguish the unlearned model from the model trained without the forget data, with any auxiliary information.
In this work, plexity, for different types of data distributions, including when the forget data is out-of-distribution corrupt. We define below the utility objectives of the in- and out-of-distribution unlearning scenarios. Throughout, we assume that the loss function is lower bounded, so that all minima are well-defined.
interested in the trade-off of approximate unlearning with time and space or
Definition 2. Let 0 S f < Consider a data distribution D over data space Z, unlearning training pair AU, and recall that Z == Uk21 2h is the set of training sets. Denote the population risk minimum by L. == minBERd L(f), and independent and identical sampling of n and from 'D by S ~ D and S, D=-1, respectively We define the following utility objectives:
samples
1. In In-distribution:
Al)( = EESDD
max L(U(S):A(S)) C..) - S,CS 1Sylsf
2. Out-of-distribution: (o)D(U, = ESS.
max C(U(S),AS..US))) C.]] S,E2* |5ylsf
In other words, our in-distribution objective unlearning quantifies the retained utility when, starting from training set consisting of samples from the test distribution D, an adversary up to f samples arbitrarily. This objective has been previously considered by /Sekhari et al. (021). Besides, our distribbutiiinninnnn objective considers the worst case where the training set is composed of up to if samples that may not be from 2D and are to be removed, while the remainder S, of the training set is sampled from D. This objective has been theoretically studied before in the context of unlearning, and covers practical cases where user data is very heterogeneous, or shifts over time, or is corrupt and needs to be "corrected" (Goel et al. (024)).
remove
In the out-of-distributinn scenario, we denote the retain data by S, for clarity, since it is sampled from the distribution independently of the forget data.
3

---

Published as a conference paper at ICLR 2025
3 DELETION CAPACITY & REDUCTION TO EMPIRICAL RISK MINIMIZATION
We begin by introducing the notion of deletion capacity to compare different unlearning-trainnn pairs. Our approach extends the formalism from Sekhari et al.) (2021), which defined deletion capacity in terms of utility. In this work, we introduce the concept of computational deletion capacity, which accounts for the time complexity incurred during unlearning.
Definition 3. Let n., T > O and consider a pair (U, A) satisfying approximate unlearning.
1. The utility deletion capacity the maximum number f(a) < n of samples that can be removed while ensuring the error remains most a. We refer to it as in-distribution if the error is measured as LID, and out-of- disdiitiibution if it is measured as LOOD-
2. The computational deletion capacity is the maximum number f(T) < n. of samples that can be removed within a given time complexity budget T.
We observe that we aim for unlearning-traiie training pairs which have the largest deletion capacities possible. Besides, introducing a computational aspect deletion capacity natural because, without computational constraints, the utility deletion capacity could be maximized by retraining from scratch. Similarly, the computational deletion capacity could be maximized by outputting a data-independent model. Consequently, we are interested in optimizing both capacities simultaneously- maximizing the number of deletions while keeping both the error and time complexity low. An analogous space complexity analysis could also be considered, but for simplicity, omit it here.
is,
We now show that it is sufficient to analyze the deletion capacity using the empirical loss, via the following generic bounds the population risk with worst-case deletion, under standard assumptions.
Proposition 1. Assume that, for every z E Z, the loss E(- ;(= is p-strongly convex and L-smooth. Consider any peeearninn-training puir (U, with output 0 = ; A(S)), and recall the notation of Definition
By denoting 0" == arg mingers L(0) and o² EE2D |VE(0=; z)ll we have
L E, ~ max L(O; S.) s.,ss.) SYE2* 18, Ss
L o?
LOOD (4, S 1
24 n -
Moreover, if Ve(00 22, D, is sub-Gaussian with variance proxy 0², we have
L (I)( S ESND" max S,CS
8L0² 1 Il(n)
5,) L,s,,,
(5)
112
كSylSf
Finally, assuming that for every Z, the loss ll ;z) is R-Lipschitz, we have
2L A) < ES-D"
max L(, \ S - C.,s,s, + 4LR²
(
2
(6)
f
S,C8 |Sylsf
122
This proposition provides general strategy for analyzing the utility deletion capacity: if the worst- case empirical loss on the retain data is bounded by O'emp. this directly implies a bound on the number of deletions that can be made, with guaranteed bound on the population risk. Importantly, we do not need to directly analyze the generalization error of the unlearned model.
For example, for target population risk bound a 2 Cemp in the Lipschitz nn-distribution case with ((()) we deduce that the utility deletion capacity is least the order (a), i.e., constant fraction of the full dataset when assuming a constant error. Another interesting example is 'lazy' differential privacy, that ignoring removal requests after training with differential privacy, which satisfies approximate unlearning. Standard empirical risk minimization bounds of DP-SGD (Bassily et al. 2014), with the group differential privacy property adapted for Rényi differential privacy (Bun and Steinke, 2016), yield the empirical risk error Ö (((2)) Plugging this bound in Proposition guarantees utility deletion capacity of 2(n 'lazy" differential privacy (Huang and Canonne 2023), after converting from Rényi to approximate differential privacy (Mironov[ (017). We defer the full proofs related to this section to Appendix B
This has recently been shown to be tight for
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 Unlearning via Noisy Minimizer Approximation
Input: Target empirical loss Gemp- smoothness constant L, model dimension d, unlearning budget E. Training: get 0 by approximating the risk minimizer on S up squared distance GempÉ 47dd
Unlearning: get G by approximating the risk minimizer on S \ Sy up to squared distance after initializing at 05
acmpé
4Ld
return 0¹d + (0, Semp
2Ld Ia)
4 IN-DISTRIBUTION UNLEARNING VIA NOISY RISK MINIMIZATION
In this section, we tackle in-distribution unlearning. Specifically, we analyze Algorithm | generic unlearning framework assuming access to an approximate empirical risk minimization oracle. We show that any instance of this framework can minimize the in-distribution empirical utility objective to an arbitrary precision, subject to standard assumptions.
Notation. For any dataset S, we denote by 03s the global minimizer of the empirical loss ((::S), which we assume to be unique. In particular, for any forget set Sy C S, we denote by Sy the unique global minimizer of the empirical loss L(- ; Sy). Consider an arbitrary optimization procedure A (for training or unlearning) which outputs 0g I when given dataset S and initial model 0g E Rd. For every Oprecision: Ainitial > O, we denote by TA (PPreciisoo Aiiitill) the compu- tational complexity required by A to guarantee on any dataset that, given the initialization error 110p 0- < Ainitial, its output 0 satisfies |00 - 0²2l²² S Opprocision-
1. Assume that, for every z E S, the loss (() is L-smooth, and & S d. Assume that for every S C S, S f. the empirical loss over S 2 Sj has a unique minimizer. Recall the notation above and consider the anlearning-trainin pair AU in Algorithm I, with the initialization error of A on set S being at most A.
Theorem 1. Let E, aemp, A > f < n. and
Then, AI) satisfies (g, qe) approxximate unlearning with empirical loss, over worst-case S \ SS, at most Otemp in expectation over the randomness of the algorithm, with time complexity:
Training: TA
ClempE
A
Unlearning: Tu
(eemp
CkempE
+ max S,
0 03 I²) 1S
4Ld
2Ld
4Ld
Theorem T covers most optimization methods that have been studied in certified unlearning, such as gradient descent (Neel et al. 2021 Chourasia and Shah 2023) and the Newton method variants (Guo al. 2020 Sekhari et al. 2021). and also covers unexplored methods with known gradient complexity bounds, e.g., those using stochastic gradients, projection, or acceleration (Bubeck al. 2015). The proof crucially leverages the existence of a unique minimizer as an anchor point to guarantee statistical indistinguishability. In fact, the optimization oracle needs reach the aforementioned minimizer up to precision proportional to the unlearning budget E, to compensate for the output perturbation in Algorithm [ Our approach generalizes previous analyzes (Neel et al., 2021). especially since does not require convexity: it applies to several non-convex problems with unique global minimizer, such as principal component analysis and matrix completion (Zhu et al. 2018).
we get Corollary 2 Jusing gradient descent as approximate Thanks to Theorem and Proposition I risk minimizer, which has worst-case time complexity O Ond log( Cramp }) for strongly convex problems,
{))
for precision Ceemp and initialization error A, with space complexity O(d) (Nestervv et al. 2018).
Corollary 2.
Let E, O, Gemp O, and > L. Assume that, for every z E Z, the loss E( ;2) is pair (U,
u-sttrongly convex and L-smooth, and that S d. Consider the unlearning-trattee in Algorithm 7 where the approximate minimizers are obtained via gradient descen and denote O, E Rd the initial model for training.
fi.c., the sequence pc+1 0; L+p F),0;)), 0, and we replace with \ Sy for unlearning. We explain how compute the number of iterations in Remark 6
5

---

Published as a conference paper at ICLR 2025
Algorithm
In In-Distribution Deletion Capacity
Utility
Computational
Algorithm
with Gradient Descent
l(nva)
? ar explT (2nd) Rd
Newton step
Sekhari et al. 2021
i min a, v(rs
(n 1)11-1001 Q[(dd + d8.58)
di74
Differential Privacy
(Huang and Canonne, 2023
(n (F
(n 1) 1)1T=0()Pd)
Lower bound Laa et al. 2016
(nvaa
Table I: Summary of the in in-distribution deletion capacities (the larger, the better), for error bound a > and computation budget T > O, under approximate unlearning for strongly convex tasks, with smoothness and Lipschitz assumptions. We adapt the unlearning guarantees of prior works to align with our Rényi divergence- definition. The last two reported computational capacities mean that no sample can be unlearned unless T exceeds the proven time complexity of these algorithms.
Then, (U, A) satisfies (eoeeee)pxiimaattt unlearning with empirical loss, over the worst-case 8 S),S at most Cemp in expectation over the randomness of the algorithm with time complexity:
Training: O Ind (ndlog log
1100 - 0% 0311))
Unlearning: O ( (ndlog (I+
0's - 03ys, -33,,11²) )l')):
max
(0s-0''s1
Cempe
Ceemp
SyC$
SSylsf
ignoring dependencies on L, p. Also, the space complexity is (dd) during training and unlearning.
For Cemp S a, assuming that for every Z the loss Cl- iz) is R-Lipschitz, the in-distribution population risk LID (ID(U,, A) is at most a, in (2( and f = ((n)a), with time complexity:
Training: o Onddog
Es 0. 051l²) aE
d
0 Unlearning: O 0( (ndlog
(1 (1+
Rf
2
CE
72
From the result above, we deduce that Algorithm| 1 when using gradient descent, achieves an in- distribution utility deletion capacity of at least (a) This implies that constant fraction of the dataset can be deleted while maintaining a fixed error a. Our analysis establishes light separation from "layy' differential privacy methods, where deletion capacity degrades polynomially with the model dimension d (Huang and Canonne 2023). Furthermore, this result answers previously open theoretical question by /Sekhari et al. (2021), demonstrating that dimension independent utility dele- tion capacity is indeed possible. Notably, the best previously known utility deletion capacity decayed with dimension as ((1//d1/4) (Sekhari et al. 2021). We experimentally validate this separation in Figure La on a simple least-squares regression task. Finally, we observe that the deletion capacity of ((n a). as established in Corollary is right in terms of its dependence on both and n. following lower bounds for robust mean estimation (Lai al. 2016 Diakonikolas et al.) 2019).
dimension-independerr
Meanwhile, the time complexity bound from Corollary 2 increases logarithmically with the fraction of unlearned samples. In fact, for a time budget T, computational deletion capacity given in Corollary 2 is 2(n exp(1I (2ndd) in the Lipschitz case. This capacity scales linearly with n and Rd 0o
exponentially with the time budget T, effectively counterbalancing the linear dependence on the unlearning budget E, the error a. and the inverse of the dimension The exponential dependence on T is highly favorable, though it stems from the logarithmic gradient complexity of gradient descent in strongly convex tasks which degrades to quadratic for non-strongly convex tasks (Nesterov et al. 2018). In contrast, the algorithm by /Sekhari et al. (202)) which achieved the previously best known utility deletion capacity, has a time complexity of O(nd + dd2.38) and space complexity of O(d)). Consequently, its computational deletion capacity is zero unless the time budget 7 is at least Q(nd + d2.38). This comparison shows that gradient descent with output perturbation possesses the largest known in-distribution deletion capacities. A summary comparison of various unlearning training approaches, in terms of in -n-distribution deletion capacity, is provided Table We defer the full proofs related this section to Appendix C

---

Published as a conference paper at ICLR 2025
Als. 2
Out-of oidd-iitibaatin Eiror Crom
Alc. L.
Als. 1.
Ala. 2. 0.405
DP-SGD
Alc. L. 0.45s
In-distibationn
000-
10-
Nomber unleaminng iterationn
Dimension
LOOD unlearning iterations Algorithms [ and using gradient descent, with f E {1, 0.1m, 0.45n forget data out of 1, 000 samples. The per-iteration cost is the same for both algorithms. The unlearning time of Alg. (non-robust) can be 10x slower than Alg. 2
(b) Out-of-distribution
number of
(a) In-distribution error LID versus dimension d for Algorithm and and DP-SGD, with f = 20 forget data out of 10, 000 samples. The error of DP-SGD is near- lincar, showing separation between differential pri- vacy and unlearning.
Numerical validation on a linear regression task with synthetic data for the same unlearning budget, with in- n--distribution (left) and diiistiiitiiinno (right) data. The in-distribution forget set sampled at random, while the out-of-distte of-distribution data is obtained by shifting labels with fixed offset. Additional details and results on real data can found in Appendix
Figure I:
Thanks to analysis. also establish that the certified unleaming algorithms of Neel al. (2021) and Chourasia and Shah (202)), whose generalization bounds were unknown prior to our work, also achieve tight in-distribution utility deletion capacity, and similar computational deletion capacity as Algorithm]] [ with gradient descent. We recall that there are few algorithmic differences with the latter, since Neel et al. (2021) additionally project models and Chourasia and Shah (2023) add noise at each iteration and assume Gaussian model initialization.
5 OUT-OF-DISTRIBUTION UNLEARNING VIA ROBUST TRAINING
While Corollary offers sigmificant improvements over existing results, extending the same analysis to the out-of diitrii-iitiittioonn utility objective poses challenges. In this case (Definition () the forget data can deviate arbitrarily from the test distribution. Unfortunately, the time complexity of the unlearning procedure in Algorithm[] ggrow grows with the distance between the risk minimizers the retain and full data, which becomes unbounded for the out-of-distribution objective, defeating the purpose of approximate unlearning the worst case.
This is formalized in Proposition] 2 below, where single forget sample can make the initialization error the unlearning phase of Algorithm [ arbitrarily large. This naturally implies that the unlearning phase can be slower than retraining from an arbitrary initialization in the worst case, following standard gradient complexity lower bounds (Nesterov et al.) 2018 Theorem 2.1.13).
Proposition 2.
Let f = 1, n > 1, and 2 = dR.d There exists a 1-strongly convex and 1-smooth loss 1, any (unlearning -imme) initialization error A
function, such that for any retain set S, -n-1,
there exists a forget sample 25 E Z achieving |00 (0', 03, A, where 03, and 0 S,u( denote the empirical minimizers the retain and full data respectively.
To address this, we introduce a new strategy where the goal is to train on the full dataset manner that minimizes sensitivity to the forget data. Since the forget data is unknown in advance and could potentially consist outliers, we employ a robust variant gradient descent. Specifically, we use the coordinate- wise trimmed mean of the gradient batch, described in Algorithm 2 The trimmed mean, with trimming parameter r, is a classical robust statistics method that computes the average of all inputs along each coordinate, excluding the smallest and largest values (Lugosi and Mendelson
7

---

Published as a conference paper at ICLR 2025
Algorithm 2 Unlearning via Robust Training and Noisy Minimizer Approximation
Input: Target empirical loss Cemp- smoothness and strong convexity constant μ., model dimension d, initial model 0o. trimming parameter f. unlearning budget e, initialization error A.
Training: get 0 by robust training (shown below) for K do
24 j
log( Ldd iterations:
Cumpé
for t t= o....K
Compute the trimmed mean gradient: r, (M v(((,.z.))
/* average all but f largest and sma smallest inputs coordinate-wist */
Update the model: 0(+1 0 frz
end
Unlearning: get 0 by approximating the risk minimizer S\ \ Sy up to squared distance initializing 0 return 0¹ (0, Seme Lo)
Gompp by
4Ld
2019). This approach allows mitigating the influence of outliers in the forget data, thereby enhancing the efficiency and robustness of the unlearning phase, especially in out-of-distribution settings.
In this section, we denote the retain set as S, for clarity since, in the out-of-distribution scenario, is sampled from the test distribution and independent of the forget data. Recall also that O..s. is the minimizer of the empirical loss over the retain data. In order to analyze Algorithm 2 we introduce the interpolation error constant the retain set S,, and its counterpart the data distribution D given k 2 1 samples, respectively:
E(S,)
==((0) (D) = ES E(S,).
S
ZES.
The smaller the interpolation error, the easier it is fit the retain data, and the underlying data distri- bution, respectively. Theorem below states the unlearning and utility guarantees of Algorithm 2
Theorem 3. Let E, a, Ocmpp H4 > 0,9 0, E Rd, and f S n &niin& {3 5(L- }-
Assume that, for every z E Z, the loss E(. ;2) is j--ttrongy convex and T-smooth. Consider the ceeearning-traiiiin pair (U, A) in Algorithm 2 using gradient descent during unlearning.
Then, (U, satisfies (q, aaprooxmxte unlearning with empirical loss, over S, with worst-case Sy, at most Ceeup in expectation over the randomness of the algorithm with time complexity:
Training: o (Iddlos
110
d
10000 (0.-0)
Unlearning: o (ndlog
[1
d.
LE(S.)
Ceemp
C'empE
ignoring dependencies L, The space complexity is (dd) during training and unlearning. For
Cemp S a, the duttof-distributiin risk LOOD(U, A) 1) is at most a, if n - =0 =D()), with time complexity:
Training: 0 (nd ( d Es. 100 -0--01 03. Ps.11)) Unlearning: O Ondllgg Indlog (1 1+ Le (D))
Theorem 3 addresses the primary limitation of the analysis in Corollary 2 the unlearning time complexity now independent of the out-of-distribution forget data. Instead, the time complexity is driven by the interpolation error on the retain set, rather than the difference between the empirical risk minimizers of the retain and full datasets. The interpolation error often much smaller for well- behaved data or sufficiently large models, making this bound much tighter. In contrast, Corollary P could only achieve such strong bound under the restrictive assumption that the loss is Lipschitz, which either results in an excessively large Lipschitz constant, e.g., scaling with model dimension for bounded domains, or excludes fundamental tasks, such as unconstrained least-squares regression. We numerically validate the robustness of the unlearning time complexity of Algorithm 2 compared to Algorithm|] [] in Figure Tb on least-squares regression task, and defer additional validation on real data to Appendix F Finally, this result is the first theoretical guarantee against the so-called slow-down attacks in machine unlearning (Marchant et al. (022). which not only seek to undermine utility but also unlearning efficiency, denial-of-service attacks.
8

---

Published as a conference paper at ICLR 2025
Algorithm
Out-of-Distribution Deletion Capacity
Utility
Computational
Lipschitz
Non- Non-hipschitz
Algorithm with Gradient Descent
Y
Ω
acexp(T/2nd) Rd (all0
a²=² cxp(T/nd) =(8,))a1100 0
a²c" cxp(T//n)) (SS.)d1100 03,
Algorithm 2 with Gradient Descent
1(n) Ω
Ω
Table 2: Summary of the out-of-distribution utility and computational deletion capacities (the larger, the better) due to Theorem [] for error bound a > 0 and computation budget T' > O, under approximate unlearning for strongly convex tasks, with smoothness and Lipschitz assumptions. The dittr---isttibution deletion capacities of previous certified unlearning methods are not known.
The proof of Theorem demonstrates that the robust training procedure converges to the empirical risk minimizer on the retain data, up to small eπror proportional to the interpolation enror and the fraction of forget data. This provides solid initialization for the unlearning process, with limited sensitivity to the forget data. Additionally, although Algorithm 2 sets the trimming parameter equal to the size f of the forget set for simplicity, the result of Theorem 3 only requires T = O(f), and can be straightforwardly extended to any trimming parameter by replacing f by in the theorem. We
defer the full proof' related to this section to Appendix
The most significant aspect of deletion capacity here is computational. Since we can achieve arbitrarily small empirical risk, Proposition [ implies that the cotto--distribution utility deletion capacity of Algorithm[2is only constrained by the fact that the trimming parameter can be at most half of the full data size, and is thus a constant fraction 2(n)) of the dataset. On the other hand, manipulating the time complexity bound from Theorem 3 gives a computational deletion capacity of Ω a²² end(
This bound is favorable due to its exponential dependence on the time
(d2 (0
budget T, linear dependence on n, and the typically small interpolation error, which effectively mitigates the quadratic dependence on other parameters. In contrast, the unlearning time complexity pair covered by Theorem[[ma maybe unbounded, as explained earlier in the section, and thus the corresponding deletion capacity zero. Still, with the restrictive assumption that the initialization error is bounded on the full dataset and that the loss is R-Lipschitz everywhere, the
of any unlearning-trainie
computational deletion capacity from Corollary is ?
exeexxpT/2mm (2nd) which may be hindered Rd 0. Rd|[00 0000
by large Lipschitz constant R and does not benefit from small interpolation error. A summary comparison of our is provided in Table? 2
approaches, in terms of distri--iittiittioon deletion capacity,
6 CONCLUSION
This paper presents a theoretical analysis of the utility and complexity trade-off's in approximate machine unlearning. By focusing on both in-distribution and out-of-distribution unlearning scenarios, we offer new insights into how much data can be unlearnt under fixed computational budgets while maintaining utility. For the in-distribution case, we showed that a simple optimization procedure with output perturbation can unlearn a constant fraction of the dataset, independent of model dimension, thereby resolvin ving key theoretical question and highlighting the clear distinction from differential privacy-based unlearning approaches. For the more challenging duito--distribution case, we intro- duced robust gradient descent variant, ensuring a good initialization for unlearning and certifiably unlearning a constant fraction of the data with hear-lincar time and space complexity.
An intriguing open research direction is the analysis of unified upper bounds on the deletion capacities, specifically what is the maximum number of samples that can be deleted for a fixed computation, utility, and unlearning budgets? So far, only upper bound on the utility deletion capacity is known. Other open research directions include extending our results to more complex models, and improving utility and time complexity guarantees in real-world applications.

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
YA acknowledges support by SNSF doctoral mobility and 200021 200021 grants. SK acknowledges support by NSF 2046795 and 2205329, IES R305C240046, the MacArthur Foundation, Stanford HAI, OpenAl, and Google. YA thanks Anastasia Koloskova for feedback on the manuscript, and Berivan Isik, Ken Liu, Mehryar Mohri, and members of the Stanford STAIR lab for earlier discussions. The authors are thankful to the anonymous reviewers for their constructive comments.
REFERENCES
Allouah, Y., Farhadkhani, S., Guerraoui, R., Gupta, N., Pinot, R., and Stephan, J. (2023). Fixing by mixing: A recipe for optimal Byzantine MI. under heterogeneity. International Conference on Artificial Intelligence and Statistics, pages 1232-1300. PMLR.
Allouah, Y., Guerraoui, R., Gupta, N., Pinot, R., and Rizk, G. (2024). Robust distributed learning: Tight error bounds and breakdown point under data heterogeneity. Advances in Neural Information Processing Systems, 36.
Bassily, R., Smith, A., and Thakurta, A. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464 473. IEEE.
Blum, M., Floyd, R. W., Pratt, V. R., Rivest, R. L., Tarjan, E., et (1973). Time bounds for selection. J. Comput. Syst. Sei., 7(4):448 461.
Bourtoule. L., Chandrasekaran, V., Choquette- Choo. C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. (2021). Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pages 141-159. IEEE.
Bubeck, S. et al. (2015). Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357.
Bun, M. and Steinke, T. (2016). Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of eryptography conference, pages 635-658. Springer.
Cao, and Yang. J. (2015). Towards making systems forget with machine unlearning. In 2015 IEEE symposium security and privacy, pages 463-480. IEEE.
Chourasia, R. and Shah, N. (2023). Forget unlearning: Towards true data-deletion in machine learning. In International Conference on Machine Learning, pages
PMLR.
Diakonikolas, I., Kamath, G., Kane, D., Li, J., Moitra, A., and Stewart, A. (2019), Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742- 864.
Dwork, C.,, Roth, A., et al. (2014). The algorithmic foundations of differential privacy. Foundations and Trendso9 Theoretical Computer Science, (33-4):211-405
Foster, J., Schoepf, S., and Brintrup, A. (2024). Fast machine unlearning without retraining through selective synaptic dampening. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 12043-12051.
Gil, M., Alajaji, F., and Linder, Т. (2013). Rényi divergence measures for commonly used univariate continuous distributions. Information Sciences, 249:124-1311
Ginart, A., Guan, M., Valiant, G., and Zou, J. (2019). Making ai forget you: Data deletion in machine learning. Advances in neural information processing systems, 32.
Goel, S., Prabhu, A.. Sanyal, A., Lim, S.-N., Tomr P., and Kumaraguru, P. (2022). Towards adversarial evaluations for inexact machine unlearning. arXiv preprint S.1i::2001.066411
Goel, S., Prabhu, A., Torr P., Kumaraguru, P., and Sanyal, A. (2024). Corrective machine unlearning. arXiv preprint 240.14402
10

---

Published as a conference paper at ICLR 2025
Golatkar, A., Achille, A., Ravichandran, A., Polito, M., and Soatto, S. (2021). Mixed-privare forgetting in deep networks. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pages 792-801.
Graves, L., Nagisetty, V., and Ganesh, V. (2021). Amnesiac machine learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11516-11524.
Guo, C., Goldstein, T., Hannun, A., and Van Der Maaten, L. (2020). Certified data removal from machine learning models. In International Conference on Machine Learning, pages 3832-3842.
PMLR.
Gupta, V., Jung, C., Neel, S., Roth, A., Sharifi- Maariii-Malvajerdii, S., and Waites, C. (2021). Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34: 14411699--6330
Huang, Y. and Canonne, C. L. (2023). Tight bounds for machine unlearning via differential privacy. arXiv preprint arXiv:2309.0080 0.080.0
Izzo, Z., Smart, M. A., Chaudhuri, K., and Zou, J. (2021), Approximate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics, pages 2016. PMLR.
Karimi, H., Nutini, J., and Schmidt, M. (2016). Linear convergence of gradient and mooximal-gradion methods under the polyak-tojasicwiez condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pages 795-811. Springer.
Kurmanji, M., Triantafillou, P., Hayes, J., and Triantafillou, E. (2024). Towards unbounded machine unlearning. Advances in Neural Information Processing Systems, 36.
Lai, K. A., Rao, A. B., and Vempala, (2016). Agnostic estimation mean and covariance. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 665-674. IEFE.
Lai, T. W. and Wood, D. (1988). Implicit selection. In Scandinavian Workshop on Algorithm Theory, pages 14-23. Springer.
Lugosi, G. and Mendelson, S. (2019). Mean estimation and regression under heavy- tailed distributions: A survey. Foundations of Computational Mathematics, (553::114--111
Marchant, N. G., Rubinstein, B. I., and Alfeld, (2022). Hard to forget: Poisoning attacks on certified machine unlearning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7691-7700.
Mironov, I. (2017). Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE.
Neel, S., Roth, A., and Sharifi-Malvajerdi, S. (2021). Descent-to-delete: Gradient- methods for machine unlearning. In Algorithmic Learning Theory, pages 931-962. PMLR.
Nesterov, Y. et al. (2018). Lectures convex optimization, volume 137. Springer.
Nguyen, T. T., Huynh, T. T., Nguyen, P. L., Liew, A. W.-C,, Yin, H., and Nguyen, Q. V. H. (2022). A survey of machine unlearning. arXiv preprint arXiv:2209.02299
Pace, R. K. and Barry, R. (1997). Sparse spatial autoregressions. Statistics & Probability Letters, 33(3)2291-297.
Pauwels, E. (2020). Lecture notes: Statistics, optimization and algorithms in high dimension.
Pawelczyk, M., Di, J. 7.,, Lu, Y., Kamath, G., Sekhari, A., and Neel, S. (2024). Machine unlearning fails to remove data poisoning attacks. arXiv preprint arXiv:2406. 17216.
Rigollet, P. and Hütter, J.-C. (2015). High dimensional statistics. Lecture notes for course 18S997, 813(814):46.
11

---

Published as a conference paper at ICLR 2025
Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. T. (2021). Remember what you to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 14.18075-18086.
Vadhan, S. (2017). The complexity of differential privacy. Tutorials on the Foundations of Cryptog- raphy: Dedicated to Oded Goldreich, pages 347-450.
Voigt, P. and Von dem Bussche, A. (2017). The EU general data protection regulation (GDPR). A Practical Guide, 1st Ed., Cham: Springer International Publishing. 10(3152676):0-5555
Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj, A., Zhao, J., Cormode, G., and Mironov, I. (2021). Opacus: User-friendly differential privacy library PyTorch. arXiv preprint arXiv:2 12298.
Zhu, Z., Li, Q., Tang, G., and Wakin, M. B. (2018). Global optimality in low-rank matrix optimization. IEEE Transactions on Signal Processing, 66(13):3614-3222
12

---

Published as a conference paper at ICLR 2025
APPENDIX ORGANIZATION
The appendix is organized as follows. Appendix A recalls standard definitions used in the main paper. Appendix B contains the proof of Proposition [
Appendix contains contaiin the proof' of Theorem and Corollary Appendix DD contains the proof of Proposition 2 Appendix [E contains the proof of
Theorem Finally, Appendix F contains additional details on Tables and 2 and Figure
A STANDARD DEFINITIONS
We recall that assume the loss function to be differentiable everywhere, throughout the paper. Definition 4 (L-smoothness), A function L: IR + R. is L-smooth if. for all 0, O' IR we have
L 0 - 011
((0') [()) (V) 0' - 0)
2
The above is equivalent to, for all 0, 0' E Fd having ||VC(())) (70((")--(())) S L 1 011 (see, e.g., (Nesterov et al. 2018)).
Definition (u-strong convexity). A function C: Rd + R. is u-stonnly convex if. for all 0, 0' Rd we have
[(0') L()) (VL(0), 0' 0)
1
0 011² 2
Moreover, we recall that strong convexity implics the Polyak-Lojasiewinn Lojasiewicz (PL) inequality (Karimi et al. 2016) 2μ (C(0) - L.) < [V Note that a function satisfies L-smoothness and j-stroon convexity inequality simultaneously only if μ S L.
Definition 6 (R-Lipschitz). A function L: IRdd + IR is R-Lipchhitz if. for all 0 0' E Rd,, we have
|C(0') ((0) S R R 0
The above also equivalent to all the gradients being bounded by in norm.
B PROOF OF PROPOSITION
Lemma 4. Let S f < n. Assume that, for every E 2, the loss El: ((:zz) ()) is u-strooglyy convex and L-smooth. Then, have
L EnND Ve(0": 24²
ES-D" [C(03) L.)
(8)
n
Moreover, if z), D, is sub-Gaussian with variance proxy 0², then
8L0"
Iln(n) +1
ESSDD max ((0'sss) C. 5 S,CS 18y155
(9)
112
n
Proof. Assume that, for every z E Z, the loss f(. ;z) is u-strongly convex and L-smooth. Then, successively smoothness and then strong convexity, we have
ES-Da (E(03) - C.] < Es |103 - -01 2/12 Es-D= (VL(0))))
L E 2((00=))1
2n²
n
The last equality is simply due to S consisting of n i.ddd samples from D. This proves the first statement.
Now, assume that vE(A":2), D, sub-Gaussian with variance proxy a² This implies that, a²
for every Sy, f. ( Sy) is aub-Gaussian with variance proxy | < n-7, the
13

---

Published as a conference paper at ICLR 2025
average of Sab-Gaussian of independent caussansi random variables (see (Rigollet and Hütter 2013] Section 1.2)). As a standard property of sub- Gaussian variables (Pauwels) 2020 Theorem 2.1.1), we thus have
|VC(0" (())))))))))))))))))))))))))){ 22
DS exp
80²
Using the above, and Jensen's 's inequality, we have
BS
max ( Cyc8 1sylsf
80² Es in
exp
n-
max |VL(0" 8 S(S)) {SSDIP S,C8
80²
|Sylsf
80² 2
n n-
In
Es exp
802
S,C8
max
SSylss
80
n- n-f
In
Es max exp SyCS 18,15/
71
802
80 ln
Σ S,CS 1Sylss
Es exp
n- n- | 8 {
80²
In
2
Σ
71
n f
802
n
k
We now use the following consequence of the binomial theorem: (n + 1). We obtain
Ek (t) S E/ 1ー s
80 In
SØ
ES-Da max (V S
In (2(n + 1)²)
11 f
k:
S
R=
(In(2) + f In(n + 1)).
n f
Now, we use successively smoothness and strong convexity of the loss function, then the inequality above:
0-1|
Es-D=
max ((03),,)) L+
BSnD"
max S,CS S5
0s
S,C8
|5y|S/
L
< Es-Di max (V S,C8 15
2/12
L 8
(In(2) + f In + 1)).
2p n -
Simplifying the above upper bound concludes the proof.
Lemma (<Neel et al. 2021 Sckhari et al. (021I). Let 0 S f< n and S E Z", Assume that, for every z Z, the loss El is p-strongly convex and R- R-Lipschitz. We have
2RS pm
max S,CS
03s 0z
|S
Proposition 1. Assume that, for every z E Z, the loss El- ;2) is justroogly convex and T.-smooth. Consider any amlearning-trainine pair (U, A), with output == A(S)), and recall the notation
of Definition 2 By denoting 0* := arg millgERs ((0) and o = EELD V 2)] ? have
L ES. max L(); S.) C. 212 n l SYE2"
L o²
(U, < /
|8, Ss
14

---

Published as a conference paper at ICLR 2025
Moreover. if :2)0" D, is Gaussian with variance proxy o?, we have
LID(U, - L
8L0² 1 f In(n)
Es-Dil max
L(U(S,,AAS)):5%% L,,s,, SyC8
(5)
4²
SSylSf
Finally, assuming that for every z 2, the loss (z) is R-Lipschitz, we have
2L
4LK²
2)
LI)(H, S Es-Dn
max [(O; St) L.,s,s,l+ n²²
(6)
S 1 1
n
Proof. Assume that, for every E 2, the loss f(- ;2) is p-sttrongly convex and L-smooth. Let e, 8,8,a a > O. Moreover, denote by 0s and 03 the minimizers of the empirical loss functions S( Sy) and :S), respectively. For the out-of-distribution case, we denote by Os,, the minimizer the empirical loss function L(: ;,). These exist and are well-defined by strong convexity of the loss function.
Lipschitz in-distribution case. Assume in addition that, for every z E 2, the loss E(- :z) is R- Lipschitz. To analyze the population loss, recall that the loss function is R-Lipschitz, L-smooth, and p-strongly convex by assumption, which allows using Lemma 4 as follows:
ESaDr (f(03) - C.] S EN D VE(O"; )
LR
(10)
2n²
n
2n²n
Therefore, we have LID(U, A) = ESnDa
max ((U(S),A(S))) L.] S,C8
18y1sf
ESND" max ((U(S), C(03)] + ES-DD (C(03) C.]
S,CS
1SylS8
4R
ESSD= max L(U((;,A(S)) [(03)) + S,Cs [Sylss
pm
Now, that the loss function is L-smooth by assumption, followed by Jensen's 's inequality, which yields
T. ES-Da max |({S))A(()) 0311 S,CS 15ylst
T.R²
A))
2n2n
03 1|
0 031,,, ||
LR?
< LBSaDr
+ LEsDD
S |S Sf
S,C5
2
We recall from (Sekhari et al. 2021
Lemma 6) that, by the Lipschitzness of the loss, we have
2Rf
max
00 0z,s,
S,
pm
|Syls
Taking squares and expectations and then plugging the above inequality in the previous one yields
U(S; - l
Rf
LR
(I)( < L ESSDD max S,CS Sy1sA
+4
+ 2
um
Because the loss function is j-strongly convex by assumption, we have
max (((S) - 0% s S,CS
A(U(S):A(S)): ST) L.,s |Sy15f
max S,Cs
15y15f
By taking expectations on the bound above and plugging it into the previous bound, we obtain
(u) < ES-D= max A(S);; (Sy) L..srs,) + 4LR² S,CS S
2L
(
/
122
Simplifying and rearranging terms concludes the proof of the Lipschitz in-distribution case.
15

---

Published as a conference paper at ICLR 2025
Assume now that : D, is sub- Gaussaan with variance proxy o². Together with the strong convexity and smoothmess assumptions, we can use the second statement of Lemma 4 as follows:
Sub-Gaussian in-distribution
A)) == EswD" max ((U(S),A(S)) f.]
SyCS
18y1S1
ES-Da max ((U(S), C(O3)1s)) Es- max ((0ss L.]
SyCS
SrCs 1SylSS
|6y15/
8Lo² fln(n)) +1
I ESSDD max L(U(S):A(S)) [(05,s,)] S,CS [SylSI
n n-
Now, we successively that loss is smooth then strongly convex, to show the following for any S:
-
((()) 0s
In 11 ((S)()) L (15))
Plugging the above back in the previous inequality, we obtain
LID A) = ESSD= max A(U(S);A(5)) L.]
S,CS 18ylsf
8L0² fin(n) +
ES-D" max L(U((),A(5)); { s,s,, S,CS S
112 n
This concludes the proof of the sub-Gaussian in-distribution case.
Out-of-distribution case.
Using Lemma the smoothness and strong convexity assumptions
imply
Eg-D [((0";2)1'
E ( L.] <
(11)
24²2 n-
Therefore, we have
(ooD(U,,) =
max A(S, -C.1 S,E2"
18,151
ES -1 max ((U(S),ASS)) C(03,)) ES,-D=-1CC(0p -c.] S,EZ"
18,15f
S ES max L(U(S), - C(03,)) L EX-D [((00=))1' S,E2" |5y15/
2μ²² n-f
Successively using smoothness and strong convexity, and recalling the notation C..s. [(03,; = mingers L,);S,), have
L
C(U(S), (( < |((S)) 03.11² (CUU() L.
After taking maximum over Sy and expectations and plugging this last bound in the one before, get
Io (2, < ES,.DD--1 max A(S)) L..s. + S,E2
L EzAD [((()=))
P
2n² n --f
Syl5f
This concludes the proof.
16

---

Published as a conference paper at ICLR 2025
C PROOFS OF THEOREM I AND COROLLARY 2
Theorem 1. Let E, Cemp: A f n, and q 1. Assume that, for every z S, the loss ((=))) is L-smooth, and & S d. Assume that for every Sy C Sy1S S f, the empirical loss over S', 'ySy has a unique minimizer. Recall the notation above and consider the unlearning trriiinngg pair (U,A) in Algorithm 1, with the initialization error of A on set S being at most A.
Then, A) satisfies (g, apprroxxxee unlearning with empirical loss, over worst-case SS at most Oeemp in expectation over the randomness of the algorithm, with time complexity:
Training: TA
Ceemp
A):
Unlearning: Tu
Ceemp 2Ld
Ceemp 4Ld
+2 max
03 0s,5, 15.ss1").
1²)
4Ld
S,C8
1yyls
Proof. Let q > E, Otemp > 0, < n. and S E 2 given training set. Assume that the loss function is L-smooth at any data point, and that S d. Denote by 0sss,, and 0's the minimizers of the empirical loss functions S { and :(: respectively. These exist and are well-defined by assumption. Also, following Algorithm denote by f5,,,, and 0g the model obtained using A over the training sets S and S, respectively. Moreover, denote by 6 the model obtained after using 4 over the training set S Sy before Gaussian noise addition.
For any precision Cemp > initialization error A O, we denote the worst-case computational com- plexity of the training procedure to approximate the empirical risk minimizer up to squared distance Gemp by Ta(emp:: A), and by (0emp: A) during unlearning. Therefore, the computational
cost of T A) during training and max sycs Tur Gomps
GompE 4Ld
0 0 02is,
during unlearning
since we initialize at 0g.. we have by definition
0
03
Olempe
max
g
S 0/151
1|
Ceemp
05ii, 03 1|=
Ceemp 4Ld
(12)
4Ld
SyCS S
4Ld
Moreover, using Jensen's 's inequality we have
|og 0, || < 2 0 03 + 2 03vs,
1|²
Oeemp 2Ld
+2 +2 0z 03
(13)
Thus, the computational complexity of unlearning is upper bounded by Tue 03 Ozy,s,
Oamps Gamp 4Ld
2Ld
2 max s,cs 1Sylsf
Unlearning analysis. Our goal here is to show that ((a, and ((, Sy)) are near- indistinguishable in the sense of Definition I To do so, we bound the distance between 05iss, and g¹1 and infer the unlearning guarantee via the Rényi divergence bound of the Gaussian mechanism. Now, using inequalities (12) and Jensen's inequality, we obtain
14
05 1|- 2 20/0 0sss,
|| + + - 0zis,
2
Cemp
(14)
Ld
Recall that
= 0² N'O,, 2Ld
Ia) and U(8, A(S) ST)) 0sis, + NO 2Ld La)-
We recall that the formula of Rényi divergences Gil et al. 2013) of order for Gaussians N(,, N(,', E) for arbitrary vectors u, E Rax and symmetric positive definite matrix E Raxd is ((u- W - n'). Therefore, we conclude that (U, satisfies (g. approximate unlearning:
D,(U(S),ASS)) [1, A(S)))
14 0 Si,S,
Se.
(15)
2 Gemp
2Ld
17

---

Published as a conference paper at ICLR 2025
Utility analysis. We now analyze the empirical and population loss of the model A())
Recall that the loss function is L-smooth. Therefore, using inequalities 12
Jensen's inequality and
taking expectations over the randomness of the additive Gaussian noise . (0, 2Ld the empirical loss:
Ia), bound
L E
max (((),,A())) 0' |31 S,C8
E max A(U(S); (S)) -'sss S 2
S,C8
1811s1
|5, Ss
|uu -ksssssss 0'úis + +x
= 2 Xu,
Ocmp 2Ld
Ia)
max S,CS |
< L. max S, كSylsك
0²1 03115
+ LL
|||
X X~~N(0,
(0.
Gemu
2Ld Ia)
L max
8 05,,5
1|²
Ld
Oemp
S
C.emppp
Oemp
< Cempp
(16)
Sycs
2Ld
4Ld
2
S
after using the assumption that E S. d for the last inequality. Therefore, the expected empirical risk error is at most Cemp with the following computational complexities before and during unlearning respectively:
GempE
GempE
Cemp
0 0sis, 13. 1
TA
A),
Tur
+ 2 max
(17)
4Ld
2Ld
2Ld
S,CS
This concludes the proof.
Let E, Or Gemp > 0, and q > 1. Assume that, for every Z E 2, the loss E( ;2) is u-strrongl convex and L-smooth, and that S d. Consider the intaanning-training pair A) in Algorithm | where the approximate minimizers are obtained via gradient descen and denote Oo Rdd the initial model for training.
Corollary 2.
Then, A) satisfies (q, ( -approxiimae unlearning with empirical loss, over the worst-case S',S at most Cemp expectation over the randomness of the algorithm with time complexity:
Training:
log
d.
110u -0%00())))
033l²)
Unlearning: O (ndlog (1+
[1
d
max
003 05 11))s11))
CempE
CempE SyCS
1Sylsf
ignoring dependencies on L, p.. Also, the space complexity is (dd) during training and unlearning.
For Cempp S a. assuming that for every z E Z the loss E( ;z) is R-Lipschitz, the in-distribution population risk LID(U, A) is at most a, if = 2 and f = (onvo)), with time complexity:
Truining: O nd
d
Es 10 03(l²)
, Unlearming: O ndd (1+
Rff
ae
72
Proof. Let a. Gemp > 0, and q > 1. Assume that, for every E Z, the loss E(- ((=zz) z) is j--tronglyy convex and L-smooth, and that ε S d. Consider the training-unte unlearning pair (4, in Algorithm | where the approximate minimizer is obtained via gradient descent, with initialization Og R during training.
For gradient descent, the worst-case computational complexity to reach precision (squared distance to empirical risk minimizer) Gemp > 0 with initialization error (squared distance to empirical risk minimizer) A > 0 is O(nd log A
ignoring dependencies on L, μ (see, e.g., Nesterov et al. (018)).
dema
Therefore, by applying Theorem [ we have that (4, .)) satisfies (g gs) approxxmaaee unlearning. Moreover, in terms of utility, we have
Eu max S,CS
{{))) - C.. S Cemps
(18)
SS
fi.c. the sequence 0c+1 = 0,
L+p VL(O;))) 0, and we replace with \ Sy for unlcarning. We
explain how compute the number of iterations in Remark 6
18

---

Published as a conference paper at ICLR 2025
with the following training and unlearning time respectively:
o (nd log
1100 - 0311)) . nd nd log
(0000031)))
(1
d Ctampé
03s 0siss I²))
Clamp
S SS
In fact, we can obtain the guarantee (18) expectation over S ~ D", at cost of the expectation
of the runtimes above. Indeed, taking expectations over the training set in the standard convergence guarantee of gradient descent for smooth strongly convex problems (c.g., (Nesterov et al., 2018
Theorem 2.1.15) implies that expected enror with expected initialization error Es [ can be achieved in Ond log Es|Al time. That is, we have
ES-D"
A( Cx,5 Sa,
(19)
8,58 |Syls
with the following training and unlearning time respectively:
o nd log
100- - 0311² 13 nnd log (1 Es-
03s - OsSs, l1))
max S,C8 SSrlst
In turn, assuming that the loss is R-Lipschitz any data point, we can plug the bound generalization bound of Proposition T As a result, we have
38 in the
2T. Es-Da
AR²
L
2
A) =
max L(Ō:S) (t) - L,,svs, Sycs |Sy Sf
+
n M
2L
4R
L
+
1
71
Therefore, ignoring dependencies in L, μ,, the in-distribution population risk is at most (the factor 24 in the first term above can removed at the cost of logarithmic overhead the time complexity) when 2 ! and f (nvaa.
Finally, we note that the unlearning time complexity can be further bounded, using the Lipschitz assumption, since we have from (Sekhari al. 2021 Lemma 6) that
2R pm
max S,CS
0's 0 s
|
Thus, ignoring dependencies on L, p. the unlearning time complexity
o (nd nd (1+ as
RJ )))
This concludes the proof.
Remark 6 (Practical implementation of Algorithm with gradient descent). There are two practical scenarios where we can compute an upper bound on the number of optimization iterations needed to reach a predefined precision (in terms of squared distance to the empirical risk minimizer). Consider the optimizer to be gradient descent here for clarity, and denote the empirical loss Lemp and the corresponding empirical risk minimizer Ox.mmp
The first scenario is when the loss function is non-negative (or some global lower bound is known); this is quite common in machine learning, e.g., quadratic loss, cross-entropy loss, hinge loss, etc... In this case, we know that for any initial model Og E Rdd we huve ||0, 0 0m.empl S 2 (femmp (0o) p S.Cemp (60), where the first inequality is due p-strong convexity, and the second
Leup ( (mpp))))) S the loss being non-negative. Therefore, knowing only the loss the initial model, and (a lower
19

---

Published as a conference paper at ICLR 2025
bound on) the strong convexity parameter, e.g.. fz-regularization factor, have a computable upper bound on the initialization error. The upper bound on the number of iterations follows directly from standard first-order convergence analyses, e.g., Theorem 2.1.15 Nestrrov et al. (2018), and is computable knowing the aforementioned bound on the initialization error, and the smoothness and strong convexity constants. The second scenario is when the parameter space is bounded, and in which case we use the projected variant of gradient descent, analyzed in Neel et al. (2021) for empirical risk minimization. There, we know that the initialization error is bounded by the diameter of the parameter space, which is computable. A computable upper bound on the number of iterations needed follows with a similar argument as the first scenario above.
D PROOF OF PROPOSITION 2
Proposition 2. Let f = n, L, and Z = Rd. There exists 1 1-strongly convex and 1-smooth loss function, such that for any retain set S, E 2n-1, any (unlearning-timeg initialization error A > 0,
there exists a forget sample 2 E 2 achieving 0 ()),)(z)) Ss A. where 0's, and 0 {,((Z)) denote the empirical minimizers on the retain and full data respectively.
Proof. Consider the data space 2 = Rd and the quadratic loss (0; 2) = 2 0 z//2 10, 2 E TR... This loss function is 1-strongly convex and 1-smooth any data point. Fix z = o.,s, nnA A for some unit vector E Rd ||u|| = 1. First, observe that
O.,s, arg min ((0:S,) BER
1 S
Σ ZES,
110
z||
Σ z,
S
ZES,
and similarly 0 (.,y) = arg arg mingers L(0;S, (zy}) have
= |s ExES, z. Therefore, we
0 Os,5,U(zy)
Σ
2
1
2f 7 + Σ
|S,| +1
|&,| +1
xx))
ZES,
|S,| +1 (zg + |S (x.s,) = n
(z, + (n 1)0..s.)
Finally, thanks the choice 2 == O,,s, + nnd A u,
||u|| = 1, we conclude
0.,s.ulzy 0.,s, 1|2 n²
1
22 0..s, 1| = =A.
E PROOF OF THEOREM 3
Lemma 7. Let n E N' and f n/2. For any gi,...,, Bn E .R. and any I C [m]] of size [I]
we have
[MM gm) gn) -r < n 25
6f
(+ n - 2
f
1
gg: 1
(20)
sEI
where we denote the average BI
[ EiEz Bi.
1
Proof. Let E N and J < n/2. Fix vectors g1, B1.... gn. E Rd and subset I C [n]] of size = =-f. For any set C [m], we denote Bz == 17 LiET g: E gg: the last notation handy and refers to the expectation over the uniform sampling of i from the set T. First, observe that since each element in I has equal probability of belonging to uniformly random subset T C I = n we have
B =
Σ IET
g:
E
E
g | 1
T~I
(21)
I
17
20

---

Published as a conference paper at ICLR 2025
where recall that the last notation is the expectation over the uniform sampling subsets of I of size n - f. Therefore, using Jensen's inequality, we have
[|MM((8) ... Ba) 3x)-111²-= rM, (B) ........ 8n) - E T~I
8T
E T~I 1 [8I.
gT
Now, recall from (Allouah et al. 2023
Proposition 2) that for every
T
[ [n], IT| = n
f, we have
(g), gm) 811
6f
(1+ n
1
gg - 8T|1" 13---11
(22)
n
2f
2f
[T]
TET
Plugging the above in the previous inequality and taking expectations yields
[TM (gl....,
Bn) Ez 2
E
T~I --
[ gn) 8T
6f
1 11 - 2s
TwI -
gg
BT
n 25
iET
6f
n 2f
1 11 2B
TwI _
int
[g. TT
6f
1+ 11 25
EiII |[
Ez
n1 - 2f
6f
1+
g
gzll"
n 2
n1 2f
The third equality above is due to the same argument of bias-variance decomposition, and Jensen's 's incquality. This concludes the proof.
Lemma 8. Assume that, for every z E 2, the loss ((=;z) is j-strongly convex and L-smooth. Let
Oo E Rd, f S nimn 3 5[T.-p} J. and consider the training Algorithm Then, for any T 2 1 and
12u
any S 1S,l S f, we have
C(OT; S,) - L. <
f5
Σ
Ve(00,, eexp 22
exp (- (C(0);S,)- - L.,s.), (23)
pn |
ZES.
where we denoted 03,- arg mingeRs L(0:S,).
Proof. Let t 2 0, < n min
12" 3 5(T-)t x) J and S,,, Sy E 2" such that |Sy| = n- |S, S f. Recall
that L(::5) St) is L-smooth by assumption. From Algorithm 2 recall that 0.+1 = 0, -r, with Ve(0. Hence, by the smoothness assumption, have
Ft (V((
1 7 1. 1|ral1
L(0++1:8) St)
(V
St), 2
(24)
Moreover, we recall the identity
(VL(0: (()00:((,))),.))) 1 - - - -re11²)
Substituting the above in (4 we obtain that
C(0m1; \ Sy) L(0,; (Sy) S 7 [VL((,; s/)]l + - rell²) + 1
7² 2 ||r.1
2
-- [VV((00 - (1- S ())) -ral
21

---

Published as a conference paper at ICLR 2025
Substituting y I. in the above obtain that
1
1 2L
C(0 (00+118(S))) - [(),;))
|VC(0
+
|r, V S/II (25)
2L
By applying Lemma 7 to the vectors ve(0,; ....... v,(0,;z,) and the indices set I = {
[n] 2, E J, and denoting & = n-
6f
+ 2-
we obtain
||, - V [V(( ve(0r; 2.(0:)))))))
([(Oii)))
I
JEZ
K
vi(0;;2)) 7
vi(Oii)))
(26)
jEZ
VE(0;;2;) - VL(0;; St))
(27)
EE
Besides, by denoting C
2
Σ
ZES, Ve(03, :2) and P = 2L we have thanks to strong
SS
convexity and smoothness (see, e.g., (Allouah al. 2024 Proposition 1)) that
-
S < 2
(28)
Z
iET
V((0.))) VL(008) [S)11 = |VE(O,; -
SEI
1EI
< + (P - 1)
Using the above in (27) yields
rr VC(0;S 2 +
S
Substituting the above in 25 yields
1 ( 2L
((0=)::88 81) <
(111)) (29)
2L
Multiplying both sides in 29 by 2L and rearranging terms, we get
(L= S < x + 2L (C(0;; S(0++1;8)
xÇ² + 2L (C(O)) Lu,sys, + L.,s,s, L((
After rearranging terms, and using strong convexity to lower bound the norm of the gradient with the optimality gap, e.g., see (Karimi et al. 2016). we obtain
2L ( (S)) f.,s)s,) S x²? 24 (1 s(P - 1)) (E(0,; (.,,())))
+ 2L (C(0;; (1 (5) ((,
= =x²² + (2L - 2p (1 s(P - 1))) (C(0;; S1) L,.s)s)).
Dividing both sides by 2T, we get
nC?
[(0 L.,s,s, S
+
1 (1 x(P x(P-1))) 111) (c(0:
f..s)s,)
21
L
(30)
22

---

Published as a conference paper at ICLR 2025
Then, applying 330 recursively for time indices in le E {o,...,,t 1} yields
1(0 SS) - Srss, -
(1 (1--x(P- (1-m(PP--))) - 1)))
Σ (1
2L
k=0
+ (1
1 (1- - x--x(P- 11)) 1+1
(c(06; (C(Ob:)\Ss)) - (,,),s,)
1
xC2
2L 1 - (1 4 (1 x(P - 1))) + (1- 11 (1 -x(((P xx(P 11)) (C(06:8\SS) - s(s,
1
L
+ (1- 1 (1 (1- k(P k(Pp-1))) (E(00: St) - f.,s,)))
2/ (1 k((P - 1))
I
We now take T
2 0. Moreover, using the fact that (1 + x)a I rhe for all x E and
remarking that 1-r(P-1] 1 45 L
n and 1 -x(PP- 1) when & n S min { 1 5(P-11)
12
yields that
5(0r;5\88 St) S(s, S 45 f + + exp (-
P T) (c((): (()) - Lx,s(s,)-
2μ
2L
This concludes the proof.
Theorem 3. Let E, a, Gemp, H. L > 0,92 RR and f S i &mmin {3.
5(L-H) J. Assume that,
12pr
}
for every z E Z, the loss ((: is u-strongly convex and L-smooth. Consider the unlearning-trainie pair (U, in Algorithm 2 using gradient descent during unlearning.
Then, A) satisfies (4, -aappr)-ppoox unlearning with empirical loss, over S, with worst-case Sj, at most Ceepp in expectation over the randomness of the algorithm with time complexity:
Training: O ndllog log
d
1 - 0%.11²) 100-0%.11))
Unlearning: of nnllo
(+ (1+ GempE Th
$ fL(s.)
CempE
ignoring dependencies on L. The space complexity is (d) during training and unlearning. For
Oemp S a, the -fittribtitiiioiinnnn risk LOOD A) is at most a, if n fn-ff = =2(2), with time complexity:
Training: O (nddlog
( d Es, 11uu 0%. ) Unlearning: O (nddlog (1 1+ d S aE
as n (.)n((()))
Proof. Let q > 1,8, at Cemp, a' > 0,05 f < n, and S, E 2=-1,8 s, E za, Assume that the loss function is u-stronglyy convex and L-smooth at any data point, and that E S d. Denote by 03 and 0 the minimizers of the empirical loss functions C(: ;S,) and ((: respectively. These exist and are well-defined by strong convexity of the loss function. Also, following Algorithm 2 denote by 0 and 0z,, the model obtained using As over the training set S and obtained using Ao (i.e., empty forget set f = 0) over the training set S,., respectively. Moreover, denote by g the model obtained after using 24 over the training set S, before Gaussian noise addition.
Recall that the computational cost of reaching the empirical risk minimizer up to squared error Cemp O, starting with an initialization error A > O, with gradient on smooth strongly convex prob-
lems is Ond L log( Cremp ))
(Nesterov et al. 2018). Therefore, letting A = 0 O's 1|2 at the com-
Ld o- 0z. 11
putational cost of Ond 4 log(
LAA Demps
during training and max sy cs O & log( |
Campp
during unlearning since we initialize at 034, we have by definition
max
||00r
0s. 11
Olempe 4L.d
lo..
0%, 1
aemp
(31)
S
4Ld
1sylss
Also, recalling the result of Lemma 8 and using strong convexity, we have
max SyCS |
|05'
O's.
S max (C(05) ;S,) ) - -L.s.) < S,
2
45 1
V
22)
;2)]
+aa
un
SS
ZES.
(32)
23

---

Published as a conference paper at ICLR 2025
Also, from Lemma 8 the computational complexity for the statement above is Onndlog (()) (to be added during training), as the per-iteration cost involves computing d times a trimmed mean over n real numbers, each of which can be done in worst-case linear time and constant space with variations of the complexity of unlearning is upper bounded by
(Blum et al., 1973, Lai and Wood 1988). Thus, the computational
Ld S
un |8,1 Ezes, \ ; :2] 2 )
nd log( O
(33)
1
110eemp
Unlearning analysis. Our goal here is to show that Ay(S)) and u(@ (o(,)) are near- indistinguishable in the sense of Definition I To do so, we bound the distance between 0g. and 0' and infer the unlcarning guarantee via the kenyi divergence bound of the Gaussian mechanism.
Now, using inequalities (31) and the triangle inequality, we obtain
|| - 0 -0.11 s 0² 035''' 1| + 1105 0's 13 OempE Ld Ia) and A(S,) 0g + NOO Ld
(34)
Recall that A(()) = l + NO Gemp
Gamy
2Ld
Thus, using the Rényi divergence expression between multivariate Gaussians (e.g., see (Gil et al. we conclude that AA) satisfies (g. ge -ppproxxxeeee unlearning:
2013
Dj D,(U(S).AA(5)) ((S,A((S))) = 2
9
8 0 qE.
(35)
Chemp
2Ld
Utility analysis. We now analyze the empirical and population loss of the model
Recall that the loss function is L-smooth, and that the retain set S, is fixed. Therefore, using
inequalities BT). Jensen's inequality and taking expectations over the randomness of the additive Gump Ia), we can bound the empirical loss:
Gaussian noise N(0,
2Ld
Eul max A((()), L..., S Eul max [u(S),A)($)) 03, 1| S,E2"
L
2
S,Ez"
15115/
L
E
Gamp X
max 5,EZ" 15
Ou 0's + +X11
2
2Ld
Ie)
< max S,E2* |
||02r
0'.11" + LE
X
X~N(0, 2Ld Ta)
max S,EZ' s
||0d 03.
Ld
Cemp
S
-.- Temmp
Ceepp
Cemps
(36)
2Ld
4Ld
after using the assumption that I for the last inequality. Thus, the expected empirical risk error is at most Cemp with the following computational complexities before and during unlearning respectively:
Ld 1 ExEs, V[(03, nd log( um [5.]
a')
A o ( na (mat max { log ) log
LdA Demp
}).0
.0
/
P.eempp
(37)
Finally, we set a'
=d conclude the first statement of the theorem.
Gemple
In fact, we obtain the guarantee (36) in expectation over S, D=-f, at the cost of the expectation of the runtimes above. Indeed, taking expectations over the training set in the standard convergence
guarantee of gradient descent for smooth strongly convex problems (e.g., (Nesterov et al. 2018 Theorem 2. 1.1 implies that expected error a with expected initialization error Es, A can be achieved in O(nd L log Es, [A)]
time. That is, we have
E D
max CI L.,s, 8,e2" |5115F
Sa
(38)
24

---

Published as a conference paper at ICLR 2025
with the following training and unlearning time respectively:
- 1100 - -0's (s..1*))
nd log
nd log 1
D |
Σ
[iee :2)
ac n
ZES,
In turn, we can plug the bound
38 in the generalization bound of Proposition | As a result, we have
EEDD [VE(0" 2)
LooD(U, z
ES
max (( f.,ss.l++ + S,E2" 8
2p²
L
L BR z
a
2/1²
π - f
Therefore, ignoring dependencies in L, js, the in-distribution population risk is at most a (the factor L in the first term above can be removed at the cost of logarithmic overhead in the time complexity) j
when n2- - f = 22( This concludes the proof.
F ADDITIONAL DETAILS AND RESULTS FOR TABLES AND AND FIGURE
We recall that Table presents a summary of the in-distribution deletion capacities (the larger, the better), for error bound > 0 and computation budget T > under approximate unlearning for strongly convex tasks, with smoothness and Lipschitz assumptions. In particular, we note that the utility deletion capacity of the Newton step algorithm is directly deduced from (Sekhari)
Tables 1 land 2
et al.
2021 Theorem 3), with the following adaption from (EDP, 5) -unlecarnngg (Sekhari et al.
2021
Definition 2) to our (g. unlllarmnn formalism for all > 1: E S
16 16 assuming
6DP
that EDP S (o)) using (Mironov) 2017 Proposition 3). This adaptation is valid given that the
Gaussian mechanism employed (Guo et al. 2020 Sekhari et al. 202I) satisfies Rényi differential privacy (Mironov [017 Corollary 3). The same adaptation is conducted for the differential privacy method (Huang and Canonne 2023). Besides, we note that the last two reported computational capacities mean that sample be unlearned unless T exceeds the proven time complexity of these algorithms (Bassily et al.
2014; Sekhari et al. 202T). Finally, the reported lower bound is a
direct adaptation of (Lai al. 2016 Observation 1.4).
In both tables [ the computational deletion capacities are obtained by computing the maximum deleted samples such that the sum of the training and unlearning time complexities smaller than T. We believe that comparing the sum of both unlearning and training times is important. For the sake of the argument, hypothetical (inefficient) training procedure that computes and stores the empirical risk minimizers every subset of the full dataset would only require constant-time unlearning, which could be misleading if we only compare unlearning times. It is worth noting here that the unlearning time complexity of the work of Sekhari et al. (2021) is independent of n, although at least quadratic in
numerical validation of our theoretical results linear regression task with synthetic data under a fixed approximate unlearning budget, with in-distribution and out-of-distribution data. Specifically, the full data features are generated from d-dimensional Gaussian (0, Ia), = 100, and the labels are generated from the features and a random true underlying model, also from a Gaussian (0, La), with Gaussian response. The in-distribution forget data consists of = 20 data points sampled at random from the 10, 000 full training samples. Moreover, we set the unlearning budget for the in-distribution scenario to E = We use the DP-SGD implementation of Opacus (Yousefpour et al.) [021), and convert to group differential privacy, the group being of size f. with standard conversion bounds (Vadhan 2017 Lemma 2.2), and run the optimizer until convergence or for 100 epochs (usually 10x more than Algorithm[]) with a fine-tuned learning rate. For the out-of coat--f---stibutiion scenario, the forget data is obtained by shifting labels with fixed offset set to 10a, the total number of training samples being 1, 000. Moreover, we set the unlearning budget for the in-distribution scenario to E = 10. The learning rates for Algorithm | and set following standard theoretical convergence rates (Nesterov et al.) 2018) for strongly convex
Figure We recall that Figure
presents Iigurenpresentss
25

---

Published as a conference paper at ICLR 2025
Put-of-distribution Ervor LOOD
104
Alg. 2. f
Alg. 1, f
10
Alg. 2. f 0.1m
Alg. 1, f 0.1m
Alg. ʃ 0.45n
10'-
Alg. 1. f 0.15n
10
10
10
Number unlearning iterations
Figure 2: Out-of-distribttion error LooD versus number of unlearning iterations for Algorithms and 2 using gradient descent as optimizer, with E {1, 0.In, 0.45n) forget data out of 16,512 samples of the California Housing dataset. The per-iteration cost is the same for both algorithms. The unlearning time of Algorithm (non-robust) can be 10x slower than Algorithm 2
The initialization error can be estimated without knowing the distance to the minimizer, since the loss is known to be non-negative in this case, and the strong convexity constant is estimated empirically (see Remark O for details).
tasks, and Theorem 3
Empirical validation on real data. We extend the empirical validation in Figure D in the out-of- distribution scenario the California Housing dataset (Pace and Barry 1997,, standard regression benchmark. The dataset contains 20, 640 samples, each representing district in California, with features describing demographic and geographic information. We conduct the same experiment as in Figure lb described in details in the previous paragraph, and show the results in Figure 2 The conclusions drawn from the synthetic data experiment continue hold here: when unlearning
out-of-distribution data, existing unlearning algorithms encompassed by Algorithm [ (with gradient descent, which is very similar to the algorithms of Neel et al. (202I) and Chourasia and Shah (2023) slower than Algorithm 2 which recall is much less sensitive to out-of-distribution samples by design. is also worth noting that Algorithm iss even slower as the forget data fraction increases, as predicted by the theory, and the same holds for Algorithm althoough a lower rate.
26


Reviews:
[{"review_id": "5vgTW6gD6Q", "reviewer": "Reviewer_RJfS", "summary": "This work analyses the utility and complexity trade-offs in approximate machine unlearning, focusing on both in-distribution and out-of-distribution scenarios. The authors address the challenge of efficiently removing specific data from trained models. For in-distribution data, they demonstrate that ERM with output perturbation can achieve tight trade-offs between unlearning accuracy and computational complexity, connecting a theoretical gap regarding differential privacy limitations in unlearning. However, they identify that these techniques do not work with out-of-distribution data, where the unlearning process can become less efficient than retraining from scratch. To overcome this, the paper introduces a robust and noisy gradient descent algorithm that maintains utility while improving unlearning efficiency in out-of-distribution contexts.", "questions": "* Am I correct in stating that unlearning is not generally possible for non-convex models without a unique minimiser? Can the authors comment on relaxing their assumption to general non-convex models? \n* Could access to a global minimiser be relaxed with a weaker assumption, like the optima within a bounded set of known diameters?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The paper provides an in-depth theoretical exploration of the utility and complexity trade-offs in approximate machine unlearning, which I liked and found beneficial.\n* The authors tackle unlearning in both in-distribution and out-of-distribution (OOD) contexts and make an interesting separation between the scenarios\n* A notable contribution is the introduction of a robust and noisy gradient descent algorithm (Algorithm 2) for OOD unlearning. \n* The paper addresses and resolves a theoretical question Sekhari et al. (2021) posed regarding dimension-independent utility deletion capacity. \n* Overall, it is well-written and straightforward to follow.", "weaknesses": "* Strong Assumptions Limit Applicability: The theoretical results rely on assumptions such as strong convexity, smoothness of the loss function, and the existence of a unique global minimum. While these are standard assumptions for theoretical work, their applicability in practice needs to be clarified.\n* Limited Experimental Evaluation: The experimental validation is conducted on relatively simple tasks, such as linear regression with synthetic data.\n* Assumption of Known Forget Set Size: The algorithms and theoretical guarantees often assume that the size of the forget set is known and relatively small compared to the total dataset size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m4cvP9aeJL", "reviewer": "Reviewer_Nr4d", "summary": "The paper presents a theoretical analysis of the utility and complexity trade-offs in approximate machine unlearning with the deletion capacity under fixed error bound and computational budgets. The authors consider both in-distribution and out-of-distribution unlearning scenarios and propose a new robust and efficient variant of the gradient descent method for the latter situation.", "questions": "What is \"procedure 2\" in Algorithm 2? Please either define \"procedure 2\" explicitly in Algorithm 2, or remove this reference if it's not needed.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The study of the out-of-distribution scenario is very meaningful. \n2. The insight of deletion capacity under fixed computational budgets while maintaining utility is novel.\n3. The theoretical analysis is rigorous.\n4. The paper is well-organized.", "weaknesses": "1. Adding a detailed explanation of out-of-distribution in Abstract would be better.\n2. The reviewer is quite confused about Definition 2. \n   - $\\mathcal Z^*$ is a space (stated on line 127) rather than \"the set of training sets\". Please clarify the definition and usage of $\\mathcal Z^*$\n   - Does $\\mathcal L*$ represent the minimum population risk on the training set or retain set? Simply defining $L*:=\\min\\mathcal L(\\theta)$ (without the dataset) is not clear. Please specify over which dataset $\\mathcal L^*$ is defined\n   - Should $\\mathcal L_{\\mathrm {ID}}$ and $\\mathcal L_{\\mathrm{OOD}}$ be bounded by a certain value?\n3. The authors should add descriptions of gradient descent in Algorithms 1 and 2.\n4. Lack of explanation for the initialization error $\\Delta$.\n5. Although this work focuses more on the theoretical part, it is still better to provide some preliminary results on some datasets under practical scenarios.\n6. Some typos, e.g., missing bold for $\\theta$ in Table 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "062GmYp3y6", "reviewer": "Reviewer_Lmpv", "summary": "This paper studies the problem of machine unlearning, the removal of certain data points from a model after unlearning, for both in and out of distribution data, with a focus on the deletion capacity of unlearning algorithms. First, they present a general theorem for analyzing the utility deletion capacity of an unlearning algorithm, the number of deletions an unlearning algorithm can tolerate while maintaining some error rate. Next, they present an algorithm (Algorithm 1) for unlearning in-distribution data using a noisy ERM approximation and analyze the time and space complexity of their algorithm. They demonstrate that the time complexity of Algorithm 1 can become unbounded for even a single out-of-distribution data removal, and propose a new algorithm for unlearning out-of-distribution data using gradient descent with coordinate-wise trimmed mean gradients.", "questions": "For Table 1, wouldn’t it be more fair to just compare unlearning times, rather than the sum of both learning and unlearning times? Especially since the goal of unlearning is primarily to process deletion requests quickly at the time of unlearning, and one would have to unlearn many more times than one would have to learn. For example, the unlearning time of Sekhari et al [2021] is independent of n, even though the learning time depends on n, but this distinction isn’t clear in Table 1. Perhaps separate columns for learning and unlearning times would make the comparison more clear\n\nSuggestions\n\nIn line 203, I would suggest using a different variable (other than alpha), such as epsilon, because alpha has been used to represent the bound on the generalization error, but in line 203, it is being used to represent a bound on the empirical error.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The theoretical study of out-of-distribution deletions in unlearning is valuable and lacking in the unlearning literature.\n\nProposition 1 gives a generic framework for assessing the very important tradeoff between utility and deletion capacity which I think could be very informative to the community.", "weaknesses": "I think this paper would be improved by a comparison of the utility and computational deletion capacity between the Noisy-GD algorithm from Chourasia and Shah [2023]. The algorithms are very similar and Chourasia and Shah [2023] also have a detailed discussion of the tradeoffs between utility, deletion capacity, and computation time of their algorithm.\n\nFor the unlearning algorithms in this paper, the learning and unlearning time are both $\\tilde{O}(nd)$. Although some time is saved during unlearning, the goal of unlearning is to unlearn using significantly less time than retraining from scratch.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ERAHz2VYfB", "reviewer": "Reviewer_FXKP", "summary": "This paper provides a theoretical analysis of the utility and complexity trade-offs in approximate machine unlearning, with in-distribution and out-of-distribution cases. For the former one, the authors uncover the dimension independency with the help of an optimisation procedure with output perturbation. For the latter one, which is more challenging and under explored, the authors propose a robust gradient descent variant with satisfying time and space complexity, and corresponding statistical guarantee.", "questions": "None.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is very well-written. The problem addressed in the paper is important and interesting, with solid theoretical insights on both in-distribution and out-of-distribution cases. The discussion is comprehensive and the comparisons with the differential privacy and the illustrations are insightful to me.", "weaknesses": "None.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PNfdhRX3C0", "reviewer": "Reviewer_BBwt", "summary": "This paper presents a comprehensive framework for approximating the trade-off between deletion utility and complexity, addressing two complementary deletion scenarios: when the forget set is in distribution and when the forget set is out of distribution. The author's algorithm defines that the optimal values of unlearning algorithms and retraining algorithms can be bounded, allowing for the derivation of the utility and time complexity of gradient descent algorithms based on this bound to achieve a balance between utility and complexity. However, the author does not provide a proof for this bound.", "questions": "1. In Algorithm 1, it is required that the unlearning algorithm approximates the retraining risk minimizer on $\\mathcal{S} \\backslash \\mathcal{S}_f$  to a squared distance of $\\frac{\\pi \\in}{4 L \\mathcal{d}}$. This requirement is unreasonable because we do not know when the unlearning algorithm approaches $\\frac{\\pi \\in}{4 L \\mathcal{d}}$. We have no way of knowing whether the output of the algorithm can even be bounded by this value in relation to the retraining risk minimizer. \n\n2. Considering that there is already a definition of efficiency, it is not wise to extend deletion capacity to computational efficiency. Specifically, deletion capacity was initially intended to understand the relationship between the maximum number of samples that can be deleted and generalization error. The author additionally defines computational (efficiency) deletion capacity, which refers to the maximum number of samples that can be removed within a fixed time overhead. I do not recommend such a generalization, as there are already related metrics, making it a redundant definition. Otherwise, we could generalize deletion capacity to all unlearning metrics, such as efficacy deletion capacity (the maximum number of samples that can be deleted while maintaining good remaining accuracy) and fidelity deletion capacity (the maximum number of samples that can be deleted while maintaining good forget accuracy).\n\n[Ref 1] Descent-to-Delete: Gradient-Based Methods for Machine Unlearning. Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR, 2021.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Exploring unlearning algorithm with theoretical guarantees is very meaningful, as the paper states that existing heuristic algorithms lack formal guarantees, rendering it unclear when they comply with regulatory standards.\n\n2. Analyzing unlearning when the forgotten data can deviate arbitrarily from the test distribution have certain significance in some potential cases.", "weaknesses": "1. **Theoretically**\n   - **Lack of Necessary Proof:** The author directly defines that the outputs (models) of the unlearning and retraining algorithms satisfy (Equation 12), $\\left\\|\\theta^{\\mathcal{U}}-\\boldsymbol{\\theta} _ {\\mathcal{S} \\backslash \\mathcal{S} _ f}^{\\star}\\right\\|^2 \\leq \\frac{\\alpha \\varepsilon}{4 L d},$ but lacks a crucial proof for Equation 12. \n\nSpecifically, The author defines (Equation 12), and proves that the utility objectives $\\mathcal{L}\\left(\\mathcal{U}\\left(\\mathcal{S} _ f, \\mathcal{A}(\\mathcal{S})\\right) ; \\mathcal{S} \\backslash \\mathcal{S} _ f\\right)-\\mathcal{L} _ {\\mathcal{S} \\backslash \\mathcal{S} _ f}^{\\star} \\leq \\alpha$ (Equation 16) based on Equation 12. They then state that within $T=\\mathcal{O}\\left(n d \\log \\left(1+\\frac{d}{\\alpha \\varepsilon}\\left(\\frac{R f}{n}\\right)^2\\right)\\right)$time, it's possible to guarantee that the optimization achieves a difference in Equation 16 that is less than $\\alpha$. However, just because the optimization leads to a result less than $\\alpha$ in Equation 16, it doesn’t mean the unlearning model $\\theta^{\\mathcal{U}}$ and the minimum values of  retraining algorithms satisfy $\\left\\|\\theta^{\\mathcal{U}}-\\boldsymbol{\\theta} _ {\\mathcal{S} \\backslash \\mathcal{S} _ f}^{\\star}\\right\\|^2 \\leq \\frac{\\alpha \\varepsilon}{4 L d}$.  In other words, at time $T$, the model we found satisfies Equation 16, but it does not necessarily satisfy Equation 12.\n\nFor instance, consider the $L$-smoothness function $\\mathcal{L}(\\theta _ 1,\\theta _ 2,\\theta _ 3) = \\theta _ 1^2 + \\theta _ 2^2 + \\frac{1}{{10}^6} \\theta _ 3^2$ which has $L=2$ and dimension $d=3$, with the optimal value occurring at $(\\theta _ 1,\\theta _ 2,\\theta _ 3)=(0,0,0)$. Let $\\epsilon=2400, \\alpha=0.01$. According to the author’s definition in Equation (12), it follows that $\\left\\|\\theta^{\\mathcal{U}}-\\boldsymbol{\\theta} _ {\\mathcal{S} \\backslash \\mathcal{S} _ f}^{\\star}\\right\\|^2 \\leq \\frac{\\alpha \\varepsilon}{4 L d} \\leq 1$  and we can derive that $\\mathcal{L}\\left(\\mathcal{U}\\left(\\mathcal{S} _ f, \\mathcal{A}(\\mathcal{S})\\right) ; \\mathcal{S} \\backslash \\mathcal{S} _ f\\right)-\\mathcal{L} _ {\\mathcal{S} \\backslash \\mathcal{S} _ f}^{\\star} \\leq 0.01$. When unlearning algorithm optimizes to a loss difference of less than 0.01 in $T$ time, we still cannot guarantee $\\left\\|\\theta^{\\mathcal{U}}-\\boldsymbol{\\theta} _ {\\mathcal{S} \\backslash \\mathcal{S} _ f}^{\\star}\\right\\|^2 \\leq 1$ .A counterexample illustrates this: taking $(\\theta _ 1,\\theta _ 2,\\theta _ 3)=(0,0,100)$,  we find $\\mathcal{L}(\\theta _ 1,\\theta _ 2,\\theta _ 3)-\\mathcal{L}(0,0,0) = 0.01$, but $||(\\theta _ 1,\\theta _ 2,\\theta _ 3)-(0,0,0)||^2=(100)^2 \\gg1$.  Hence, the author should firstly prove bound  $\\left\\|\\theta^{\\mathcal{U}}-\\boldsymbol{\\theta} _ {\\mathcal{S} \\backslash \\mathcal{S} _ f}^{\\star}\\right\\|^2$ similarly to [Ref 1] in order to proceed with the subsequent analysis.\n   - For $\\mathcal{U}\\left(\\mathcal{S} _ f, \\mathcal{A}(\\mathcal{S})\\right):=\\boldsymbol{\\theta}^{\\mathcal{U}}+\\mathcal{N}\\left(0, \\frac{\\alpha}{2 L d} \\mathbf{I} _ d\\right)$ and $\\mathcal{U}\\left(\\varnothing, \\mathcal{A}\\left(\\mathcal{S} \\backslash \\mathcal{S} _ f\\right)\\right):=\\theta _ {\\mathcal{S} \\backslash \\mathcal{S} _ f}^{\\mathcal{A}}+\\mathcal{N}\\left(0, \\frac{\\alpha}{L d} \\mathbf{I} _ d\\right)$，please check Equation 15, $\\mathrm{D} _ q\\left(\\mathcal{U}\\left(\\mathcal{S} _ f, \\mathcal{A}(\\mathcal{S})\\right) \\| \\mathcal{U}\\left(\\varnothing, \\mathcal{A}\\left(\\mathcal{S} \\backslash \\mathcal{S} _ f\\right)\\right)\\right)=\\frac{q}{2 \\cdot \\frac{\\alpha}{2 L d}}\\left\\|\\theta^{\\mathcal{u}}-\\boldsymbol{\\theta} _ {\\mathcal{S}}^{\\mathcal{A}} \\backslash \\mathcal{S} _ f\\right\\|^2$, is consistent with the Rényi divergence expression between multivariate Gaussians given by: $D _ q\\left(f _ i \\| f _ j\\right)= \\frac{q}{2}\\left(\\boldsymbol{\\mu} _ i-\\boldsymbol{\\mu} _ j\\right)^{\\prime}\\left[\\left(\\Sigma _ q\\right)^*\\right]^{-1}\\left(\\boldsymbol{\\mu} _ i-\\boldsymbol{\\mu} _ j\\right)  -\\frac{1}{2(q-1)} \\ln \\frac{\\left|\\left(\\Sigma _ q\\right)^*\\right|}{\\left|\\Sigma _ i\\right|^{1-q}\\left|\\Sigma _ j\\right|^q},\\ \\  \\left(\\Sigma _ q\\right)^*=q \\Sigma _ j+(1-q) \\Sigma _ i$. The paper did not provide the derivation process, and the result I obtained based on the expression above is inconsistent with the authors.\n   - For a gradient method, assumptions such as a unique empirical loss minimizer and strong convexity limit its applicability.\n2. **Experiments:** The paper lacks experimental evaluation, only providing a comparison of differential privacy in Figure 1. The author should compare their work with relevant unlearning research. While it's understandable that cutting-edge certified unlearning approaches, as a gradient method, it should at least be conduct experiment for existing gradient methods, such as [Ref 1]. Additionally, the author should report runtime and other metrics, such as privacy budget.\n3. **Clarity：** The author should further explain in what privacy contexts data forgetting may encounter out-of-distribution issues to highlight the significance of this research. Considering that all users may submit deletion requests, this means we cannot guarantee that every piece of data to be removed from the model is out-of-distribution and may be far smaller than the in-distribution data. This uncertainty could complicate the design of forgetting mechanisms.\n4. **Notation:** The author's notation and symbolic system are very confusing and unclear. The definition of $\\alpha$ is confusing: in #203 it refers to worst-case deletion error, in #217 it denotes approximation error, in #234 it is used for the training procedure to approximate the empirical risk minimizer up to squared distance (which seems to conflict with the notation in #220), and in #256 it represents precision.  Please ensure a consistent definition.  Additionally, is $S _ f$ an unlearning request or the forget set as stated in #119? If $S _ f$ represents the forget set, then Equation 3 implies that your unlearning algorithm only needs to utilize the forget set, which conflicts with your algorithm. Furthermore, the paper contains many undefined symbols, such as $\\theta _ S^A,\\theta _ S^{A _ f}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)