Leveraging Per-Instance Privacy for Machine Unlearning
Authors: Nazanin Mohammadi Sepahvand
Anvith Thudi
Berivan Isik
Ashmita Bhattacharyya
Nicolas Papernot
Eleni Triantafillou
Daniel M. Roy
Gintare Karolina Dziugaite
Venue: ICML 2025 poster (2025)
Keywords: machine unlearning
differential privacy
Primary area: deep_learning
TL;DR: We show that per-instance privacy levels, computed during training, provide a practical and reliable way to predict unlearning difficulty in fine-tuning-based methods, enabling more efficient and targeted unlearning strategies.

Abstract: We present a principled, per-instance approach to quantifying the difficulty of unlearning via fine-tuning. We begin by sharpening an analysis of noisy gradient descent for unlearning (Chien et al., 2024), obtaining a better utility–unlearning trade-off by replacing worst-case privacy loss bounds with per-instance privacy losses (Thudi et al., 2024), each of which bounds the (R ´enyi) divergence to retraining without an individual datapoint. To demonstrate the practical applicability of our theory, we present empirical results showing that our theoretical predictions are born out both for Stochastic Gradient Langevin Dynamics (SGLD) as well as for standard fine-tuning without explicit noise. We further demonstrate that per-instance privacy losses correlate well with several existing data difficulty metrics, while also
identifying harder groups of data points, and introduce novel evaluation methods based on loss barriers. All together, our findings provide a foundation for more efficient and adaptive unlearning strategies tailored to the unique properties of individual data points.

Leveraging Per-Instance Privacy for Machine Unlearning
Nazanin Mohammadi Sepahvand 12 1 Anvith Thudi 34 Berivan Isik
Ashmita Bhattacharyya 34
Nicolas Papernot 3.4 Eleni Triantafillou
Daniel M. Roy Gintare Karolina Dziugaite 829
Abstract
et al., 2024), mitigating the impact of poisoning attacks (Liu et al., 2024b), or updating out-of-date information.
We present principled, per-instance approach to quantifying the difficulty of unlearning via fine- tuning. We begin by sharpening an analysis of noisy gradient descent for unlearning (Chien al., 2024), obtaining better utility-uneerming trade- off by replacing worst-case privacy loss bounds with per-instance privacy losses (Thudi et al., 2024), each of which bounds the (Rényi) diver- gence to retraining without an individual data point. To demonstrate the practical upplicability of our theory, we present empirical results show- ing that our theoretical predictions are born out both for Stochastic Gradient Langevin Dynamies (SGLD) well as for standard fine-tuning with- out explicit noise. We further demonstrate that per-instance privacy losses correlate well with several existing data difficulty metrics, while also identifying harder groups of data points, and in- troduce novel evaluation methods based on loss barriers. All together, our findings provide foun- dation for more efficient and adaptive unlearning strategies tailored to the unique properties of indi- vidual data points.
In modern large-scale Al training regimes, exact unlearn- ing (i.c., anything equivalent to retraining the model from scratch, without the forget set) prohibitively expensive. To meet this challenge, range of approximate unlearning methods have been developed.
Approaches based on ideas from differential privacy (DP) offer meaningful worst-case guarantees (Guo et al., 2020; Sekhari et al., 2021). These will be our focus. Unfortunately. for non-convex models, like neural networks, DP-based un- learning guarantees have so far come with higher error than their counterparts not designed to support unlearning, limit- ing their practical applicability. One of the key problems is the mismatch between the worst-case, data-agnostic nature of DP and the data-dependent nature of unlearning. Our work attempts to bridge this gap.
Alongside work on theoretical guarantees, research into heuristics has flourished. The aesthetics of such research is to combine strong utility with empirical evaluations on metries inspired by DP-based notions of approximate un- learning. It is not uncommon, however, for state of the art heuristics to be caught out by new attacks, revealing that they do not meet stringent theoretical criteria (Hayes et al., 2024; Pawelczyk et al., 2024). These challenges highlight the need for methods that can balance strong theoretical guarantees with strong practical performance.
1. Introduction
Machine unlearning aims to efficiently remove the influence of specific subsets of training data, called forget sets. The need for unlearning arises in many scenarios, such as han- dling requests for data deletion (Mantelero, 2013; Cooper
Towards understanding failure modes of unlearning, recent empirical work has shown that the behavior of unlearning varies considerably across individual data points (Zhao et al., 2024; Baluta et al., 2024). While prior work has attempted to incorporate these insights into methodology and evaluation, we lack a theoretical basis to 1) explain how individual data influence unlearning and 2) exploit this effect optimally.
"Equal contribution 'Dpartment of Electrical and Computer Engiieering, McGill University, Montreal, Canada Mila, Mon- treal, Canada Depaatment of Computer Seience, University of Toronto, Toronto, Canada *Vector Institute, Toronto, Canada Google. Mountain View, US 'Google DeepMind, London, UK "Department of Statistical Science, University of Toronto, Toronto, Canada 'epartment of Computer Science, McGill University, Montreal, Canada "Google Deep,ind, Toronto, Canada. Corre- spondence to: Gintare Karolina Dziugaite <gkdz @ www.gl.cooo...o.ooooo.
In this work, we introduce principled approach to esti- mating the unlearning difficulty of individual data points. Our approach applies to learning with noisy gradient de- scent. Using recent results in differential privacy with Rényi divergences (Thudi et al., 2024), our proposed measures- per-instance privacy
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
the Rényi divergence between model trained with and without an individual

---

Leveraging Per-Instance Privacy for Machine Unlearning
data point. Critically, per-instance privacy losses can be efficiently estimated during training, based the norms of gradient associated to individual data points.
data points may have far less influence on the learned model, our per-instance analysis uncovers an improved trade-off between unlearning and utility compared to prior worst-case analyses.
Armed with per-instance privacy losses, we revisit Chien et a 's 2024 theoretical analysis of noisy gradient descent as an unlearning scheme (coined "Langevin unlearning" a.k.a "noisy fine-tuning"), based on training without the forget set. Our analysis provides a theoretical foundation for un- derstanding how the number of iterations needed to ap- proximately unlearn scales with per-instance privacy losses. Empirical validation demonstrates that our estimates of per- instance privacy losses serve as reliable predictors of un- learning difficulty under noisy fine-tuning.
Empirical Validation of Unlearning Difficulty. We demonstrate the practical applicability of our theoreti- cal insights, showing that per-instance privacy losses re- liably predict unlearning difficulty in experiments, both for noisy gradient descent and standard fine-tuning.
Efficient Proxies for Privacy Losses We demon- strate that cheap proxy measures of data difficulty are strongly correlated with per-instance privacy losses. This identifies practical and scalable alternatives for assessing unlearning quality and forget set difficulty, particularly in assurce-constrain settings where full privacy loss computation might be prohibitive.
While noisy fine-tuning not widely used, standard (noise- less) fine-tuning is a surprisingly effective and simple ap- building
proximate unlearning approach, and serves block for SOTA methods, such as L.-Sparse fine-tuning (Hayes et al., 2024; Liu et al., 2024a). We demonstrate the applicability of our theoretical insights, showing they extend empirically to standard fine-tuning-bast basen unlearning, even in the absence of explicit noise injection. Empiri- cally, we find that per-instance privacy losses continue to predict unlearning difficulty for fine-tuning across multiple approximate unlearning metrics, datasets, and architectures. Beyond fin-ttuiig, results with the LI-Sparse method (Liu et al., 2024a; Hayes et al., 2024) show privacy losses once again predict the number of steps to unlearn.
Improved Identification of Difficult Data. Unlike existing heuristics for capturing aspects of unlearning difficulty, we show that privacy losses identify harder groups of data points, offering a versatile and theoreti- cally justified measure of unlearning difficulty.
Loss Barrier Analysis of Unlearning. We introduce loss barriers (modulo permutation) as a way to evaluate unlearning. We find that the loss barrier is significantly reduced after unlearning, reaching levels comparable to baseline levels.
Privacy losses may also offer a more refined measure of data difficulty for unlearning. We show that privacy losses are strongly correlated with some (cheaper-to-compute proxy measures of data difficulty studied in prior work. On the other hand, we show that privacy losses identify more "diffi- cult" data, which may be useful for evaluation more broadly.
Broader Implications for Unlearning Methodology. Our empirical findings suggest that per- per-instance pri- vacy losses may be useful in adapting other fine-tuning- based algorithms, such as L1-sparse.
Besides standard empirical unlearning metrics, we evaluate privacy losses on a novel loss- land-aape-baaaaee based metric, based on linear connectivity and loss barriers (Frankle et al., 2020; Fort et al., 2020). While past unlearning metrics look at the output (e.g., loss) of an individual model, loss barriers capture some of the geometry of the loss landscape. Under this stringent test, fine-tuning is able to successfully unlearn. Interestingly, loss barriers also give insight into the differ- ences between difficult and easy data points: points with higher privacy losses start off with larger loss barriers which need to be overcome to unleamn
2. Related Work
Unlearning Unlearning (Cao & Yang, 2015) aims to re- move the influence of training data. In the context of neural networks and non-convex learning problems, even highly optimized exact approaches (Bourtoule et al., 2021) computationally intensive. Going beyond exact unlearn- ing, Ginart et al. (2019) introduced notion of approxi- mate unlcarning, inspired by differential privacy (Dwork et al., 2014). This approach relies on approximate statistical indistinguishability between retraining and unlearning, in exchange for better efficiency or utility compared exact unlearning. Guo et al. (2020); Neel et al. (2021) studied approximate unlearning algorithms for convex models based on gradient descent using all the training data except those data to be forgotten (a.k.a,, finettnnn followed by the ad- dition of noise (often via the Gaussian mechanism, Dwork et al. 2006) to obtain statistical indistinguishability. Neel et al. (2021) proved that, under various assumptions, their
Our contributions can be summarized as follows:
Per-Instance Theoretical Analysis of Unlearning. We revise Chien et al.'s 's analysis of noisy gradient de- scent for unlearning-via. caatmminn-via-feeeee via--finetuuning replacing a worst- case Rényi-DP bound with recent per-instance privacy losses (Thudi et al., 2024). By exploiting that typical
2

---

Leveraging Per-Instance Privacy for Machine Unlearning
approach achieves approximate unlearning in a sequential framework with fixed per-deletion runtime.
signs a different privacy loss for different data points in a dataset, i.e., it is not worst-case, and it is less pessimistic than standard DP for points that do not affect the output distribution as much as the worst-case points. Building on per-instance DP, Ebadi et al. (2015) and Feldman & 7rnic (2021) have introduced algorithms that filter out data points once their per-instance DP loss exceeds a budget in database query problems and neural network training, respectively. For iterative algorithms like SGD, per-instance DP requires new composition theorems as the privacy loss is adaptive to the individual data points and is different at each itera- tion (Wang, 2019). Feldman & Zrmic (2021); Thudi et al. (2024) have filled this gap by providing new privacy compo- sition analyses using the associated divergences computed at an individual level.
For non-convex models, a plethora of approximate unleam- ing methods have been proposed with empirical validation, rather than theoretical guarantees (Graves et al., 2021; Goel et al., 2022; Thudi et al., 2022; Kurmanji et al., 2024; Liu et al., 2024a; Fan et al., 2023). While these approaches are shown to work on some metrics, recent work shows that several unlearning methods fail against more sophisticated attacks for either privacy or poisoning (Hayes et al., 2024; Pawelezyk et al., 2024).
Given the heuristic nature of many unlearning methods, a line of work has attempted to obtain a better understand- ing of their failure modes. Zhao al. (2024); Baluta al. (2024); Fan et al. (2025); Barbulescu & Triantafillou (2024) identified properties of forget sets that influence the be- haviors of approximate unlearning algorithms. Zhao et al. (2024); Barbulescu & Triantafillou (2024) also derived im- proved unlearning methods based on these insights, for vision classifiers and LLMs, respectively. However, we lack a theoretical understanding of the underlying relationship between the identified factors and unlearning difficulty.
Motivated by the empirical observation that per ver-instance pri- vacy loss provides much more promising guarantees than the worst-case DP analysis, we propose to port this per-instance approach to unlearning. We will see that this approach will allow us to provide unlearning guarantees and uncover properties of data that makes forget set easy to unlearn.
3. Preliminaries and Problem Setup
Recently, Chien et al. (2024) studied Langevin dynamics for unlearning and introduced an approximate method with privacy guarantees for non-convex models that we build upon in this work, replacing a worst-case bound by a recent per-instance privacy bound. Their method leverages noisy gradient descent, for both the training algorithm, as well as during (noisy) fine-tuning at unlearning time. While our the- oretical analysis considers that same setup, we empirically also investigate standard training without noise addition.
Given a dataset D = far of n points, we are interested in estimating the difficulty of unlearning as function of the particular set Dr C DD we are aiming to unlearn.
We are interested in settings where retraining the model from scratch on the retain set D' = =D DD is too costly, and so we consider approximate unlearning. In this work, we adopt notion of approximate unlearning based on Rényi divergences. For a > 0 and a # 1, recall that the a- a-Rényi divergence of μ. relative to v >> μ., is defined to be
Differential privacy data analy- sis (Dwork et al., 2006; 2014) and machine learning (Chaud- huri et al., 2011; Abadi et al., 2016). DP methodology provides an upper bound on the divergence between output distributions under neighbouring datasets, i.e., when only one individual data point is altered. Since this upper bound needs to hold for every dataset and all of its neighbors, DP is a worst-case privacy notion with a single privacy param- eter, shared among all individual data points. However, in practice, different individual points have different effects when training a machine learning model (Thudi et al., 2024; Yu et al., 2023). For instance, some data points have a much smaller gradient norm than others, making the worst- case privacy analysis for these points over-conservative, and leads to unnecessary degradations in crivacy-utlliyy trade- offs. To mitigate such degradations, Ghosh & Roth (2011) and Cummings& & Durfee (2020) have analyzed individual sensitivity rather than worst-case sensitivity, which led to an alternative but weaker notion of privacy, called per-instance (or individual, or personalized) DP. Per-instance DP as-
Per-Instance Differential Privacy
(DP) is standard approach to
v(x) [
[xxx
Da(ulli) = log
Enwwy
(I)
(Here, one can interpret m(x) v(z) as a Radon-Nikodym deriva-
tive more generally.)
For a fixed training set and forget set, the following defini- tion captures the goal of unlearning in Rényi divergence:
Definition 3.1. Fix a dataset D and forget set Dr C D. Let v be the distribution of the output of A(DD), i.e., the learning algorithm on the retain set D' D \ DD, and let i be the distribution of the output of ((A(D), DD), i.e., the unlearning algorithm on the learned model A(D) and D', For a > 1, we say 24 E)-éyiiini unlearns Dp from A(D) when (a(ullp) S.. E.
This leads to a uniform notion of Rényi unlearning, which offers the same guarantee for all datasets and all forget sets, which is analogous to standard notions.
3

---

Leveraging Per-Instance Privacy for Machine Unlearning
Definition 3.2 (Rényi Unlearning.. For 1, an unlearn- ing algorithm U is an (a, (e-é) unlearner (for A) when, for all dataset D and forget sets Dr S D, U (a, -)-Rén unlearns Dr from A(D) in the sense of Definition 3.1.
4.1. Convergence Analysis
Fix a dataset D and retain set D' D. We begin with the following corollary of (Thm. 3.2, Chien et al., 2024), which highlights the role of initial bound on Da (VT, (lPTT In the following, we assume the loss is Lipschitz continuous and smooth, and that the step sizes used by A and U have been set according to (Thm. 3.2, Chien et al., 2024).
Note that when this definition holds, one can immediately derive (standard) approximate DP-based unlearning guaran- tees (Ginart et al., 2019; Guo et al., 2020; Neel et al., 2021; Sekhari et al., 2021), using standard reductions (Proposition 10, Mironov, 2017).
Corollary 4.1. Fix D. D'. Let { Ea0221 sat- S Ea and
isfy max ( (Pa(u>-|luT:p') Da(UT,o"\IUD) Da Da(yrpller: S Seaa for all a. Then, there exists con- stant C >> O such that, for all a > 1, Us unlearns D \ from A(D) in k steps, where e" is
3.1. Unlnainng with Noisy Gradient Descent
20x - 1/2
20x - 2 2 exp (- Ck
to +
+ 1-
2a 2
20x 2
2ax
We consider a projected noisy gradient descent during both learning and unlearning, as studied recently by Chien et al. (2024). In this section, we present theoretical results that rely on noise. In Section 6, we present empirical evidence from multi- ple benchmarks that the overall trends extend to standard variants of gradient descent.
setup based on using
The proof is in Appendix A. and follows from (Thm. 3.2, Chien et al., 2024) and the weak triangle inequality for Rényi divergences.
The key observation is that the first term decays exponen- tially fast in the number of steps k. with the initial value determined by the per-instance guarantee and distance to stationarity and the rate determined by the desired value of a and problem parameters (like the Lipschitz and smoothness constants, behind C). The second term, 1, however, does not vanish.
Formally, our learning algorithm A = Ar is T steps of noisy gradient descent on D, starting from a random ini- tialization. Let Vr,D denote the distribution on weights obtained after T steps of training on D, and let VD = V denote the stationary distribution, to which the output distri- bution converges as T D0.
The irreducible term captures the distance to stationarity after T steps of training, measured in higher order (2a 1) -ivieergee This term exists consequence of our unlearning algorithm not attempting to correct for the k- steps of extra training.
Let D' = D Dr denote the retain set of unlearning request. Assuming we trained for T iterations, exact unlearn- ing would produce weights whose (marginal) distribution was Vr,p", i.e. the distribution as if we had trained on D' from scratch for T iterations.
4.2. Unlearning Individual Data Points
Our unlearning algorithm 24 = U2 runs k steps of noisy gradient descent on D'. We denote by (Mr,p) the output distribution of unlearning, i.e., of running k steps of pro- jected noisy gradient descent on D', initialized at sample from VT.D, i.e. first training on DD
The following definition is adapted from differential pri- vacy result by Thudi et al. (2024) to our unleamning setting: Definition 4.2 (Per-Instance Privacy Loss). Recall that VT,D is the distribution of the model weights after T iterations of noisy gradient descent on D. Let g(x", w) V ( x") be the contribution the weight-gradient w, coming from one data point x=" The per-instance privacy loss for x² is:
4. Per-Instance Unlearning Difficulty Analysis
Our goal is to bound the number of steps, k. of unlearning by noisy fine-tuning needed to achieve unlearning in a way that adapts to the influence each data point has on the learned model. We do so by building on two pieces of work: convergence analysis of Langevin dynamics by Chien et al. (2024) and a per-instance Rényi-differentill privacy analysis by Thudi et al. (2024).
P(æ, = DT Cr, In Enwww., Sta (119(0,, w)ll2),
(x-1) and In fe (g) is where Ci, - p
o3(a)
(b(aa)
Au2 M) P.. (1) P.- (1)
pln
202
'A symmetrized variation of this definition was proposed by Chien et al. (2024). Our asymmetric version is more consistent with the unlearning literature, where we care about making events under unlearning distrihution much more likely than under the retraining distribution.
with (a) = --a - ! and of is op composed / times, P-- = 1- (1) is the sampling probability of the data point (batch size over dataset size), and p is a free parameter we set to 3T, following (Fact 3.4, Thudi al., 2024).
4

---

Leveraging Per-Instance Privacy for Machine Unlearning
This quantity, which we show how estimate efficiently in Section 5.1, yields bound on data point's sensitivity.
5. Methodology
Our empirical methodology structured around two key ob- jectives driven by the theoretical role of per-instance privacy losses in unlearning. First, we aim to validate that privacy losses effectively predict the relative difficulty of unlearning data points. Second, we seek to understand the factors con- tributing to this difficulty by investigating the relationship between privacy losses, the loss landscape, and existing met- rics of data difficulty, In the following sections, we present our experimental design to address these questions.
Theorem 4.3. Fix D, let E D, and put DD D fx). Then Da Da I a(),a).
Proof. This follows by applying the per-instance moment- based composition theorem (Thm. 3.3, Thudi et al., 2024) with the per-step divergence bound for single data points (Thm. 3.2, Thudi et al., 2024), using the post-processing inequality to conclude that the divergence after projections is bounded by that before projections.
5.1. Empirically Validating Unlearning Difficulty
As a consequence of Theorem 4.3 applicd to Corollary 4.1, we have unlearning individual data points by noisy gradient descent depends logarithmically on the privacy loss. The following corollary direct substitution of Theorem 4.3 into Corollary 4.1.
Unlearning Algorithms Our investigation primarily fo- cuses on unlearning via fine-tuning on the retain set. We also run unlearning experiments with LI-Sparse (Liu et al., 2024a), regularized version of fine-tuning that is widely recognized as one of the most effective unlearning methods. Hayes et al. (2024) has demonstrated that L1-Sparse out- performs a number of other methods in defending against a basic Membership Inference Attack (MIA), as well as other attacks of varying strengths.
Corollary 4.4. Under the assumptions of Corollary 4.1 and Theorem 4.3, for all 'D and D' = =D { for x E 'D for all >> 1, there exist constants Aa Ba, C. 0 such that, for all 8 > E2a-1, running noisy gradient descent for
(aP + C1E4a-1
Per-instance Privacy loss We compute the terms in the privacy loss P(xr, a)) stated in Definition 4.2 by taking Monte-Carlo estimate from a single training run with check- points Wo, Way: Ways" , Way, i.e.,
2 In In
E2a-1
steps (a, 5)-untearss {x} from A(D).
Ps, (2, = Cara a In ( We, 112))
4.3. Limitations of Existing Group Unlearning Analyses
The above analysis focuses on forgetting one data point. How about bounding the work to unlearn multiple data points simultaneously? The group unlearning bound of (Chien et al., 2024, Cor. 3.4) requires that the order of grows with each data point to unlearn. This is prob- lematic, as the Rényi divergence between, e.g., Gaussians, grows linearly with a (Prop. 7, Mironov, 2017). In con- trast, (Thms. 3.3 and 3.6, Thudi et al., 2024) imply that the Rényi divergence Do (VT,D|//r (!,,,,, ), and hence steps to unleam, does not necessarily grow with Dy; instead, Thudi al. bound the divergence by comparing the distribution of gradients under 'D and under ' \ Dr. Implementing their group privacy accounting (described in Appendix B), how- ever, we found evidence the bounds were likely too loose, as they did not differentiate forget sets that we empirically knew to require different numbers of steps to unlearn (see Figure in appendix). In contrast, we found the rankings provided by privacy losses meaningfully differentiate the number of steps needed to unlearn, as we will describe in Section 6.
where Cs, s 9 are defined in Definition 4.2.
We then approximate the area under the per-step privacy curve (i.e., sum over t = 0, 1. ,.) by using the right hand rule: keeping Ps, constant between the checkpointing intervals 18)-1, This gives our approximate privacy loss:
Pa, (x) - -8-1)--
Throughout the paper we take N 35 and have the check- points 8; evenly spaced throughout training. In the case of SGD, without explicit noise, we approximate these scores by assuming negligible amount of noise is present. In particular we take a S 0.1, which matches the trends we ob- serve with SGLD. We also found the privacy losses rankings for SGD to be stable to the implicit o used for privacy losses computation (see Appendix F). We note that past work has looked into quantifying the noise inherent in training, due to hardware and software nondeterminism (Jia et al., 2021; Zhuang et al., 2022). It is an open problem to exploit soft- ware and hardware nondeterminism to offer a theoretical justification to our approach here.
We conclude that the current state of analysis for group unlearning is not tight enough to capture the behavior we observe in practice. The problem of obtaining a tight analy- sis remains an open problem.
Forget Set Difficulty We rank examples by privacy losses and form 5 forget sets of varying difficulty by taking evenly
5

---

Leveraging Per-Instance Privacy for Machine Unlearning
spaced sequences of 1000 data points. The size of the forget set was chosen to be in a similar range as prior work (e-g-. (Zhao et al., 2024)). Our theory suggests that higher privacy losses should lead to longer, thus more difficult, unlearning. We thus call a forget set more difficult than another forget set if its average privacy loss is higher. In our analysis, each forget set is represented by the average privacy loss of all samples within that set. Further methodological details are provided in Appendix D.
Specifically, we employ the concepts of (linear) loss barri- ers (Frankle al., 2020; Nagarajan & Kolter, 2019). Loss barriers characterize the "flatness" or "curvature" of the loss surface between different model parameter configurations.
The loss barrier err(w, w'; 'D) is the deviation in cross en- tropy L on the data D along the linear path in weight space connecting w to w'. Let = a. Then err(w, w'; S) is
max [Alow + āw';5) af(w; 5) ; (2) a
Unlearning Evaluation We evaluate unlearning efficacy using three metries: (1) accuracy, measured separately the retain set (RA), test set (utility), and on the forget set (FA). We report UA = 1 - FA, indicating how "accurate" unlearning is, as done in (Fan et al., 2023); (2) membership inference attack (MIA): we train a logistic regression clas- sifier to identify training samples and report the fraction of forget set samples incorrectly classified as test samples, thus indicating successful forgetting; and (3) Gaussian Unlearn- ing Score (GUS) (Pawelczyk et al., 2024), which employs Gaussian input poisoning attacks to reveal if the unlearned model still encodes noise patterns associated with the poi- soned forget set data. See Appendix E for more details.
To account for the permutation invariance of neural net- works, we compute these loss barriers modulo permutation, as detailed in (Entezari et al., 2022; Sharma et al., 2024).
Loss barriers provide insight into the geometric properties of high-dimensional loss surfaces. our experiments, we com- pute loss barriers between oracle models (trained without the forget set) and models before and after unlearning forget sets with various average privacy losses. This allows us to examine if forget sets with higher privacy losses (higher pre- dicted unlearning difficulty) exhibit distinct loss landscape characteristics, particularly in terms of loss barriers.
These metries are monitored during unlearning and com- pared with the oraele model to evaluate the effectiveness of the unlearning methods. Recall that the oracle model is obtained by training from scratch using the retain set only. We choose these metrics due to their common use in machine unlearning research (Fan et al., 2025; Zhao et al., 2024; Jia et al., 2023; Deeb & Roger, 2024; Fan et al., 2024; Pawelezyk et al., 2024) and their computational simplicity, enabling us compute them at every step during unlearn- ing. Additional details on their computation and associated parameter choices can be found in Appendix E.
5.3. Comparison to Alternative Data Difficulty Metrics
While the per-instance privacy losses provide valuable in- sights into the unlearning process, their computation re- quires storing gradients throughout training, leading to con- siderable computational overhead. Therefore, we explore al- ternative metrics that could serve as proxies for these scores, offering more efficient way to estimate forget set diffi- culty. Furthermore, we investigate the relationship between these proxies and fine-tuning tuning-based unlearning difficulty, shedding light on their underlying mechanisms.
Datasets and models Our experiments are performed the SVHN (Netzer et al., 2011) 1) and CIFAR- 10 (Alex, 2009) datasets, with a ResNet-18 architecture (He et al., 2016). Ap- pendix F presents results for ViT-small (Dosovitskiy, 2020). Appendix D describes other details for reproducibility.
We evaluate five proxies: (I) the gradient norm of individual data points a single mid- mid-training iteration; (2) the gradient norm at the end of training; (3) the average gradient norm across all training iterations: (4) C-Proxy used by Zhao et al. (2024) to approximate memorization scores from (Feldman et al., 2018); adapted from Jiang et al. (2020). This proxy computes prediction confidence: the entry in the softmax vector corresponding to the ground truth class, averaged throughout the training trajectory; and (5) single-traecctory variant of the EL2N score (Paul et al., 2021). Normally, EL2N score is computed by averaging error signals over multiple training trajectories at fixed time point. However, for computational efficiency and direct comparability with our gradient- gradient-based proxies, we compute a EL2N score at a mid mii-training checkpoint. See Appendix C for a discussion on connections among the scores.
Each experimental configuration (oracle training, or training on all data and unlearning) is run 10 times, and the average performance across these runs is reported.
5.2. Loss Landscape Analysis
While per-instance privacy losses provide a quantitative measure of unlearning difficulty based on training dynam- ics, they do not directly reveal the underlying geometric properties of the loss landscape that contribute to this diffi- culty. To gain a deeper understanding of why certain data points are harder to unlearn, we complement our privacy loss analysis with an investigation of the loss landscape.
6

---

Leveraging Per-Instance Privacy for Machine Unlearning
betore
arter
baseline
20
0m,0005
0m,0025
MIA
GUS
0.5
to en (5% UA Err
20
Loss Barrier
10
15
0.3
0.2
0.1
10-6
10"3
1000
10P
106
102
10
10
10
10
Privacy Loss
Privacy
Privacy
Figure 1. CIFAR-10 dataset results. Left: SGLD unlearning with varying levels of noise (σ)) Forget set difficulty (x-axis), as measured by the privacy loss, against time unlearn (y-axis). Time unlearn is measured in terms of epochs needed to get within 5% of the unlearning metric (c.g., UA or MIA) measured on the oracle model. Middle: SGD unlcarning. Time to unlcarn measured across three evaluation metrics. Right: Error barrier between the oracle and the unlearedd model before and after unlearning for forget sets with different privacy losses. Baseline corresponds to the loss barrier between two oracles.
6. Experimental Results
SGLD Training To evaluate the predictions outlined in Section 4, we examine the relationship between the number of steps needed to unlearn using noisy fine-tuning (SGLD), and the average privacy loss within the forget set. Figure I (left) shows that as forget set privacy losses increase, higher number of fine-tuning steps is needed to reach 5% error margin relative to the oracle, validating prediction.
We empirically validate the predictive capabilities of per- instance privacy losses in forecasting unlearning difficulty. Our primary finding is that privacy losses accurately rank datapoints according to the number of steps needed to un- learn. This is tested for two settings of interest: (1) SGLD, which aligns directly with the assumptions of our theoret- ical upper bounds; and (2) SGD. For SGD, while lacking explicit noise, we adapt privacy losses by assuming small, implicit noise component.
SGD Training While SGLD offers theoretical advantages for privacy analysis and bounding Rényi unlearning. SGD remains the dominant training paradigm in practice. There- fore, we investigate whether our theoretical framework, de- veloped in the context of Langevin dynamics, can also pre- dict unlearning time for models trained with SGD.
To probe the geometric origins of unlearning difficulty as captured by privacy losses, we analyze the loss landscape. Our investigation reveals a consistent trend: data points with higher privacy losses exhibit larger loss barriers on linear path (in the weight space) to the oracle model.
As shown Figure (middle), we observe similar trend as in the SGLD experiments across all evaluation metries: unlearning more difficult forget sets, characterized by higher average privacy losses, requires more fine-tuning steps.
We also assess the practical utility of privacy losses by com- paring them to computationally efficient proxy metrics. Our results demonstrate a strong correlation between privacy losses and existing proxy metrics, including those employed in previous studies to estimate forget set difficulty (C-Proxy in (Zhao al., 2024)). However, key advantage emerges: privacy losses provide superior precision in identifying truly difficult-to-une to-nleerr data points within the context of fine- tuning-basee based unlearning. The forget sets ranked as most difficult by privacy losses consistently take longer to unlearn than those identified by these established proxies.
This suggests that even without explicit noise injection dur- ing training, the concept of per-instance privacy losses de- rived from our theoretical analysis can provide valuable insights into the unlearning process for SGD--rriined mod- els. That is, SGD seems be well-approximated by low noise SGLD. These results replicated across additional datasets, architectures, and forget set sizes, with full details and qualitative examples in Appendix F.
6.1. Time to Unlearn Depends on Per-Instance Privacy
6.2. More Difficult Forget Sets, Larger Loss Barriers
We find that across variety of unlearning metrics, privacy losses accurately separate data points by the number of steps needed to unlearn in both SGLD and SGD. Appendix F.2 shows the same trends for L LI-sparse unlearning.
We characterize difficult to unlearn data points by their loss landscape, in particular, loss barriers (see Section 5).
Figure (right) depicts the loss barrier between oracle mod- cls and unlearned models, while varying the difficulty of the forget set, as measured by the average privacy loss.
7

---

Leveraging Per-Instance Privacy for Machine Unlearning
We observe two key takeaways from this analysis: (1) Com- paring our results to the baseline loss barriers between in- dependently trained oracle models, we find that fine-tuning achieves comparable levels after unlearning. This can be seen as a measure of unlearning efficacy based on loss barri- ers: if the (distribution of the) loss barrier is different from that of the baseline between oracles, unlearning was unsuc- cessful: (2) Higher privacy loss values correspond larger initial barriers, providing geometric interpretation for pri- vacy losses; data points that require more steps to unlearn have to overcome larger loss barriers to the oracle.
1.0
0.8
Prakyy (Nomaazzed
0.6
0.4
Final Gradient Norm
Midpoing Gradient Norm Gradient
0.2
EL2N
C CiPraxy
0.0
0.00
0.02
0.04
0.06
0.08
Privacy Loss
Figure 2. Correlation between privacy losses (x-axis) and various proxy metrics (y-axis). The values of all proxy metrics normal- ized to their maximum value for better visual clarity. For improved readability, the data is binned into bins.
Overall, our findings provide additional evidence for the utility of privacy losses in predicting unlearning difficulty, and point to the effectiveness of loss barriers as both a diagnostic and an evaluation tool for machine unlearning.
C-Praxy
Privacy Loss
Avg Norm
6.3. Existing Metries Correlate with Privacy Losses
To Tniaar (5% uni
13
We now investigate how privacy losses compare to other data difficulty metrics, as described in Section 5. Our results in Figure 2 reveal that all these proxies exhibit high correlation with the actual privacy loss. As expected, the best proxy is the average gradient norm throughout training, but it is also the most expensive proxy as it requires computing gradient norms for each data point at every iteration, versus once. Other proxies (with the exception of C-Proxy) only require gradient/error computation at single checkpoint, yet still provide reasonable approximation for categorizing examples into broad difficulty groups.
20
15-
To Uniuarm
10
15
10-
500
750
1000
1250
1500
1750
2000
500
750
1000
1500 1750 2000 Farget Set Sue
1250
Figure 3. Comparison of the time needed to unlearn (y-axis) the most difficult forget sets as identified by privacy losses (ours). C-Proxy, average gradient norm and EL2N, across different forget set sizes (x-axis).
These findings suggest that, in scenarios where computa- tional resources are limited, utilizing these proxies can offer a practical alternative for estimating forget set difficulty and predicting unlearning time. We refer to recent work by Kwok al. (2024) for an in-depth comparison of different data difficulty metrics that may serve as good proxies.
6.4. Privacy Losses Identify Harder Data
In the previous subsection, we provided evidence that exist- ing data difficulty metrics correlate with per-instance privacy losses. In this section, we provide evidence that, in fact, pri- vacy losses are able to identify harder data. In Figure 3, we compare our per-instance privacy losses to several data diffi- culty metrics, including C-Proxy (described in Section 5), average gradient norm, and EL2N scores.
Recall that C-Proxy has been used in prior work by Zhao et al. (2024) to identify difficult to unlearn forget sets for certain unlearning algorithms. Figure shows that privacy losses are highly correlated with this heuristic. Our work thus offers theoretical grounding to previously proposed heuristics for identifying difficult unlearn forget sets.
For forget sets of size E {600, 1000, 2000). we look at the top 8 data points ranked by C-Proxy, average gradient norm, EL2N scores, and privacy losses. What we see is that, across the board, the data picked out by privacy losses are harder to unlearn, as measured both by the number of itera- tions to reach 5% unlearning accuracy or reach 5% excess membership inference attack error. By identifying more difficult examples, privacy losses open up new empirical approaches evaluating unlearning performance.
Finally, note that among metrics relying averaging over training, our method is more efficient, requiring only 35 evenly spaced checkpoints (approximately 20% of training time), compared to C-Proxy and average gradient norm, which store values at every epoch (150 in total). As shown in Section 6.4, it is also more effective at identifying hard-to- unlearn samples than all other metrics, regardless of whether they rely on averaging.
7. Conclusion
In this work, we have introduced a principled approach to quantifying machine unlearning difficulty at the level of individual data points in terms of per-instance privacy losses,
8

---

Leveraging Per-Instance Privacy for Machine Unlearning
which bound the Rényi divergence between training with and without datapoint. Our theoretical analysis provides foundation for understanding how unlearning scales with the properties of specific data points, particularly in the context of Langevin dynamics.
NSERC Discovery Grant and Canada CIFAR Al Chair the Vector Institute. We also thank Mila Quebec Al Insti- tute and Google DeepMind for providing the computational resources that supported this work.
We have shown that per-instance privacy losses, estimated from training statistics, reliably predict unlearning difficulty in fine-tuning-basee unlearning algorithms, across differ- ent architectures and datasets, even in the absence of ex- plicit noise injection during training. Our empirical results demonstrate that these privacy losses offer a precise and actionable measure of unlearning difficulty. Our work also offers a theoretical grounding for previous work suggesting that certain forget sets are harder to unlearn, with privacy losses capturing similar aspects of difficulty for fine-tuning- based unlearning as previously proposed heuristics (Zhao & Triantafillou, 2024; Baluta et al., 2024; Zhao et al., 2024). Moreover, we show privacy losses identify harder forget sets than previous methods.
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and 7.hang, I.. Deep learning with differential privacy. In ACM SIGSAC Conf. Computer and Communications Security, pp. 308-318, 2016.
Alex, K. Learning multiple layers of features from tiny images, 2009. URL https: //ww...///www/e/ cs. toronto.edu kriz/learning features- 2009-TR.
Baluta, T., Lamblin, P., Tarlow, D., Pedregosa, F., and Dziu- gaite, G. K. Unlearning in-vs. out-of--istribution data in L.MSs under gradient-based method. (rXiv22411.04388 2024.
Our findings have broader implications for unlearning methodology, suggesting that per-instance divergence anal- ysis can guide the development of new, more efficient un- learning algorithms tailored to specific data characteristics. Extending our theoretical framework to other unlearning methods beyond fine-tuning and exploring the use of pri- vacy losses in designing adaptive unlearning strategies is a promising direction for future work.
Barbulescu, G.-O. and Triantafillou, P. To each (textual se- quence) its own: Improving memorized-dar unlearning in large language models. vrXiv:2405.03097 2024.
Bourtoule, L., Chandrasckaran, V., Choquette-Chooo C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In IEEE Symp. Security and Privacy (SP), pp. 141-159. IEEE, 202.1.
Cao, Y. and Yang. J. Towards making systems forget with machine unlearning. In IEEE Symposium on Security and Privacy, pp. 480. IEEE, 2015.
Impact Statement
This paper presents work whose goal is advance the field of machine unlearning, which is specifically oriented to im- prove the trustworthiness of machine learning, by supporting requests to remove the influence of training data. There are many potential positive societal consequences of our work, none which we feel must be specifically highlighted here.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differ- entially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Chien, E., Wang, H. P., Chen, Z., and Li, P. Langevin unlearning: A new perspective noisy gradient de- scent for machine unlearning. In Advances in Neural Information Processing Systems, 2024. URL https: / htwprrrwwwee.eeeooouuii--------.
Acknowledgments
We thank Ioannis Mitliagkas and Ilia Shumailov for feed- back on a draft of this work. Anvith Thudi, Ashmita Bhat- tacharyya, and Nicolas Papernot would like to acknowledge the sponsors of the CleverHans lab, who support our re- search with financial and in-kind contributions: CIFAR through the Canada CIFAR AI Chair, NSERC through the Discovery Grant, the Ontario Early Researcher Award, the Schmidt Sciences foundation through the A12050 Early Ca- reer Fellow program, and the Sloan Foundation. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. An- vith Thudi is also supported by Vanier Fellowship from NSERC. Daniel M. Roy is supported by the funding through
Cooper, A. F,, Choquette-Choo, C. A., Bogen, M., Jagielski, M., Filippova, K., Liu, K. Z., Chouldechova, A., Hayes, J., Huang, Y., Mireshghallah, N., et al. Machine unlearning doesn't 't do what you think: Lessons for generative Al policy, research, and practice. arXiv:2412.06666 2024.
Cummings, R. and Durfee, D. Individual sensitivity prepro- cessing for data privacy. In ACM-SIAM Symposium Discrete Algorithms, pp. 528 547. SIAM, 2020.
Deeb, A. and Roger, F. Do unlearning methods remove infor- mation from language model weights? arXiv:2410.08827, 2024.

---

Leveraging Per-Instance Privacy for Machine Unlearning
Dosovitskiy, A. An image is worth 16x16 words: Trans- formers for image recognition at scale. arXiv preprint arXiv:2010. 11929, 2020.
In International Conference on Machine Learning, vol- ume 119, pp. 3259-3269. PMLR, 2020. URL https: / //proceedings mlr wtwpss//111/Frrrneeee20. html.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, pp. 265 284.. Springer, 2006.
Ghosh, A. and Roth, A. Selling privacy at auction. In ACM Conference on Electronic Commerce, pp. 199-208, 2011.
Ginart, A., Guan, M., Valiant, G., and Zou, J. Y. Making Al forget you: Data deletion in machine learning. Advances in Neural Information Processing Systems, 32, 2019.
Dwork, C., Roth, A., al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoreti- cal Computer Science, 9(3-4):211 1-407, 2014.
Goel, S., Prabhu, A., Sanyal, A., Lim, S.-N., Torr, P., and Kumaraguru, P. Towards adversarial evaluations for inex- act machine unlearning. urXiv:2201.006 1.2200000660 2022.
Ebadi, H., Sands, D., and Schneider, G. Differential privacy: Now it's getting personal. ACM SIGPLAN Notices, 50 (1):69-81, 2015.
Graves, L., Nagisetty, V., and Ganesh, V. Amnesiac machine learning. In AAAI Conference on Artificial Intelligence, 2021.
Entezari, R., Sedghi, H., Saukh, O., and Neyshabur, B. The role of permutation invariance in linear mode con- nectivity of neural networks. In International Confer- ence on Learning Representations, 2022. URL https: //openreviw meet/forummid=dNNe
Guo, C., Goldstein, T.,, Hanmun, A., and Van Der Maaten, L. Certified data removal from machine learning models. In International Conference Machine Learning, pp. PMLR, 2020.
Fan, C., Liu, J., Zhang, Y., Wong. E., Wei, D., and Liu, S. Salun: Empowering machine unlearning via gradient- based weight saliency in both image classification and generation. 2xXi:2330.125000 2023.
Hayes, J., Shumailov, I., Triantafillou, E., Khalifa, A., and Papernot, N. Inexact unlearning needs more careful evalu- ations to avoid a false sense of privacy. arXiv:2403.012118 2024.
Fan, C., Liu, J., Zhang, Y., Wong, E., Wei, D., and Liu, S. SalUn: Empowering machine unlearning via gradient- based weight saliency in both image classification and generation. In International Conference on Learning Rep- resentations, 2024. URL https://openreview/ net/ forum?idd=gommhh@GM.
He, K., Zhang, X., Ren, S., and Sun, Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Jia, H., Yaghini, M., Choquette-Choo C. A., Dullerud, N.,
Fan, C., Liu, J., Hero, A., and Liu, S. Challenging forgets: Unveiling the worst-case forget sets in machine unlearn- ing. In European Conference on Computer Vision, pp. 278 777.297.00 Springer, 2025.
Thudi, A., Chandrasekaran, V., and Papernot, N. Proof-of- learning: Definitions and practice. In IEEE Symposium on Security and Privacy (SP), pp. 1039-1056. IEEE, 2021.
Jia, J., Liu, J., Ram, P., Yao, Y., Liu, G., Liu, Y., Sharma, P., and Liu, S. Model sparsity simplify machine unlearning. In Advances in Neural Information Process- ing Systems, 2023. URL https: http:://ppeereiiew.nee. 208283344
Feldman, V. and Zrnie, Individual privacy accounting via rényi filter. Advances in Neural Information Processing Systems, 14:28080-2800 2021.
Feldman, V., Mironov, I., Talwar, K., and Thakurta, A. Pri- vacy amplification by iteration. In IEEE Symp. Founda- tions of Computer Science, pp. 521-532. IEEE, 2018.
Jiang, Z., Zhang, C., Talwar, K., and Mozer, M. C. Charac- terizing structural regularities of labeled data in overpa- rameterized models. arXiv preprint arXiv:2002.03206, 2020.
Fort, S., Dziugaite, G. K., Paul, M., Kharaghani, S., Roy, D. M., and Ganguli, S. Deep learning versus kernel learning: empirical study of loss landscape geome- try and the time evolution of the neural tangent kernel. Advances in Neural Information Processing Systems, 33: 5850-5861, 2020.
Kurmanji, M., Triantafillou, P., Hayes, J., and Triantafillou, E. Towards unbounded machine unlearning. Advances in Neural Information Processing Systems, 36, 2024.
Kwok, D., Anand, N., Frankle, J., Dziugaite, G. K., and Rolnick, D. Dataset difficulty and the role of inductive bias. arXiv:240J. 008877, 2024.
Frankle, J., Dziugaite, G. K., Roy, D., and Carbin, M. Lin- ear mode connectivity and the lottery ticket hypothesis.
10

---

Leveraging Per-Instance Privacy for Machine Unlearning
Liu, J., Ram, P., Yao, Y., Liu, G., Liu, Y., SHARMA, P., Liu, S., et al. Model sparsity simplify machine unlearning- Advances in Neural Information Processing Systems, 36, 2024a.
machine unlearning. In IEEE European Symposium on Security and Privacy, pp. 303-319. IEHE, 2022.
Thudi, A., Jia, H., Meehan, C., Shumailov, I., and Papernot, Gradients look alike: Sensitivity is often overestimated in DP-SGD. In USENIX Security Symposium, pp. 973- 990, 2024.
Liu, Z., Ye, H., Chen, C., Zheng. Y., and Lam, K.-Y. Threats, attacks, and defenses in machine unlearning: A survey. arXiv:2403.13662 2024b.
Wang. Y.-. Per-instance differential privacy. J. Privacy and Confidentiality, 9(1). 2019.
Mantelero, A. The EU Proposal for a General Data Protec- tion Regulation and the roots of the 'right be forgotten', Computer Law & Security Review, 29(3):22--235, 2013.
Yu, D., Kamath, G., Kulkami, J., Liu, T.-Y., Yin, J., and Zhang, H. Individual privacy accounting for differentially private stochastic gradient descent. Transactions on Ma- chine Leurning Reseurch, 2023. ISSN 2835-8856. URL https://openrew net www.ee/oorunniddllccsssoooo
Mironov, I. Rényi differential privacy. In IEEE Computer Security Foundations Symposium, pp. 263-275. IEEE, 2017.
Nagarajan, V. and Kolter, J. Z. Uniform convergence may be unable to explain generalization deep learning. In Advances in Neural Information Processing Systems, volume 32, pp. 11615-11626, 2019. URL https: //proceedings.o intpriiiiinnns.uuipssss cc/paper/291 9/hash/ 05e97c207235d63e4 db43cc6db7bbb- Abstract html. See Appendix B, Flat minima.
Zhao, K. and Triantafillou, P. Scalability of memorization- based machine unlearning. arXiv:2410.165/6 2024.
Zhao, K., Kurmanji, M., Bärbulescu, G.-O,, Triantafillou, E., and Triantafillou, P. What makes unlearning hard and what to do about it. In Advances in Neural Information Processing Systems, 2024. URL htt.htttt//operreiiiee. ne Dee/Forum?dd-QAbbBBF722
Neel, S., Roth, A., and Sharifi-Malvjerrdi, Descent-to- delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pp- 931-962. PMLR, 2021.
Zhuang, D., Zhang, X., Song, S., and Hooker, S. Ran- domness in neural network training: Characterizing the impact of tooling. Machine Learning and Systems, 4: 316-336, 2022.
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., Ng, A. Y., al. Reading digits natural images with unsupervised feature learning. In 2011 NIPS Workshop Deep Learning and Unsupervised Feature Learning, 2011.
Paul, M., Ganguli, S., and Dziugaite, K. Deep learning on data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34: 20596-20607, 2021.
Pawelczyk, M., Di, Z., Lu, Y., Kamath, G., Sekhari, A., and Neel, S. Machine unlearning fails remove data poisoning attacks. 4rXiv:2406.7700 2024.
Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. Re- member what you want to forget: Algorithms for machine unlearning, 2021. URL httpps://arkt:s orgooogg/aaoo 20000 03279.
Sharma, E., Kwok, D., Denton, T., Roy, D. M., Rolnick, D., and Dziugaite, G. K. Simultaneous linear connectivity of neural networks modulo permutation. Europoean Con- ference Machine Learning, pp. 262-279, 2024. URL 16.
https: org/10. 1007/90807788 --1
Thudi, A., Deza, G., Chandrasckaran, V.. and Papernot, N. Unrolling SGD: Understanding factors influencing

---

Leveraging Per-Instance Privacy for Machine Unlearning
1e8
Group Guarantees over Forget Sets
6.4
Group Privacy Loss
6.2
6.0
1
Datapeint Privacy Loss (Forget Set)
Figure compared our estimates of the group privacy guarantees (y-axis) across forget sets determined by rankings privacy losses (x-axis), and found the group privacy guarantees did change. This was despite these forget sets leading consistent differences in the number of steps to unlearn. We report the mean over 20 estimates the group privacy values, and one standard deviation. We conclude the theory for group unlearning currently sharp enough to capture trends in practice.
A. Proofs
A.1. Corollary 4.1
Proof. By (Theorem 3.2, Chien al., 2024), for all o >> there exists constant C > 0 such that
D2a (eD (ur,D))lud))
2n D2r p
(3)
where (2n |(D)) is the initial 2a-Rényi divergence to stationarity on D', after training on D. By the weak triangle inequality (Proposition 11, Mironov, 2017), this is bounded by
2a - 1/2 Dan (VT.DlluT,))) + D4a D |PD) <
2a - 1/2
2a E/a + E4a-1,
(4)
2a 1
where the second inequality follows from our hypotheses.
Finally, applying the weak triangle inequality once more, Da
is bounded by
a 1/2 D2a (e (VTD))llpD:) + D2o (PD (IT,))))
which yields the claimed bound from our hypotheses, after substituting Equations (3) and (4).
B. Group Privacy Analysis and Methodology
The following theorem comes from the results of Thudi et al. (2024).
Theorem B.1. Suppose we train with noisy gradient descent for T steps. Then for an arbitrary D,D' = D Dr. we have:
T
Da Da(Pr.pllrT <
Cta In
(p-1)++1 where Cr. a-1 p=1 and
12

---

Leveraging Per-Instance Privacy for Machine Unlearning
levels
Freeune/UUA
Rine Tune/Utility
Tune/RA
80
80
75
Accurccy
70
601
65
90
60
55
5
10
15
20
25
5
10
15
20
5
10
20
Epoch
Epoch
Epoch
Tune/MAA
-00
got Samples Laoelled
60
-0
Fpach
Figure Unlearning results accuracy metrics (top) and success rate (boltom). The x-axis represents the number epochs. each plot, lines of different colors represent forget sets of varying difficulty, while the dashed line indicates the oracle's performance.
In Gr, pl In E Dy of()) @ of oon (DB (p( ('()))
where D [D), m.. ; is random sample of a minibatches from D, D' a single random minibatch, 0p(a) p 9 and og op composed times, and p is free parameter and letting (DB, w) Vel(w, DB) be the
3T following (Fact 3.4, Thudi et al., 2024).
gradient:
p/,,) w) A. D
Σ [D w)ll (a - (o)])))((p,,,p) w)ll - Σ U(Da',w) (a 1)U(D' w)12
Proof. A direct consequence of applying (Theorem 3.3, Thudi al., 2024) with the general update per-step divergence bound of (Theorem 3.6, Thudi et al., 2024), and noting the divergence after applying the projections is bounded by the divergence before applying the projections by the post-processing inequality.
B.1. Methodology for privacy losses computation
To estimate the guarantees we take Monte-Carlo sample of checkpoints from single training run at steps 8o, 51, 8 and estimate the In Gt, (D, D', w) term at each step by sampling a single random mini-batch from D' and (f(() mini- batches from D to estimate the expectations. We then compute the sum using the right hand rule, analogous to our estimate of privacy losses described in Section 5.
In Figure 4 we took checkpoints from an SGD training run on CIFARIO with ResNet18, and used 0.1, and took compute the group privacy scores. We report the mean over 20 estimates (given the stochasticity in estimates for the per-step terms In (D, D', w)) and shaded in one standard deviation.
C. Example Difficulty Related Work
Paul et al. (2021) propose EL2N score to capture how much an example contributes to learning a high accuracy predictor, high score meaning high importance during training to achieve high accuracy. At the same time, the authors find that high
13

---

Leveraging Per-Instance Privacy for Machine Unlearning
T to Unlearn (5% UA)
25
20
15
10
10-3
10-2
10
Privacy Loss
Figure 6. Unlearning time for forget sets with different privacy loss values using the L1 L1-sparse method. Time is measured by the number of steps required for the unlearning method to reach 5% margin error, where error is defined as the difference between the unlearned model's UA and the oracle's UA for the given forget set.
scoring examples tend to difficult to learn, are often memorized at the end training and are outliers. This score has been shown to correlate with number of other example difficulty and memorization metrics proposed the literature (Kwok et al., 2024: Paul al., 2021), some of which have been shown also capture unlearning difficulty for number of unlearning algorithms (Zhao al., 2024; Baluta al., 2024; Zhao & Triantafillou, 2024).
D. Additional Experimental Details
Constructing Sefficulty-Baseed Forget Sets To create forget sets with varying difficulty levels, the training dataset is partitioned into five subsets based on privacy scores. First, the samples are sorted in ascending order by their scores. Recursive splits are then performed identify key thresholds: the lower quartile (Q1), the median (Q2), and the upper quartile (Q3). Using these thresholds, five subsets are constructed: (1) the first 1000 samples, (2) intervals centered around QI (Q1 + 500 samples), (3) intervals centered around Q2 (Q2 500 samples), (4) intervals centered around Q3 (Q3 + 500 samples), and (5) the last 1000 samples. This approach provides a systematic stratification of the dataset, enabling the evaluation of unlearning performance across varying levels of difficulty as determined by privacy scores.
Learning rates and training times for SGD The original model, which serves as the starting point for all unlearning techniques (not for SGLD), is trained for 150 epochs using an initial learning rate of 0.01, a weight decay of 0.0005, and learning rate schedule that reduces the learning rate by an order of magnitude at epochs 80 and 120. Each unlearning method is subsequently fine-tuned for 25 epochs.
Additional details for SGLD At every step added N o²) Gaussian noise the minibatch gradient, where vary for ablations. All other hyperparameters were kept the same as SGD. In particular we do not do any additional gradient clipping.
Additional details for L1-sparse L.--sparse is an unlearning method inspired by the observation that pruning aids unlearning (Liu et al., 2024a). Its objective function closely resembles that of fine-tuning but includes an additional L1 regularization term, weighted by a hyperparameter a, which encourages sparsity model parameters to facilitate unlearning.
Hyperparameter tuning We perform hyperparameter tuning (HPT) for the unlearning methods using the Bayesian optimization method random forget set. While fine-tuning involves single hyperparameter the learning rate- L1- Sparse additionally optimizes a. To determine the best hyperparameters for each method, we employ Bayesian optimization to find configurations that achieve an optimal balance between privacy and utility. Additionally, to ensure that the selected hyperparameters are also optimized with respect to the number of steps required for unlearning, we identify hyperparameter sets that fall within a 5% margin error for this trade-off. Among these, we select the configuration that converges the fastest.
14

---

Leveraging Per-Instance Privacy for Machine Unlearning
15.0
T to unleam (5% ACC Err)
30
12.5
to Unlearn (5% UA]
10.0
7.5
5.0
10
2.5
0.0
10-5
10
10a
10
10-3
10-2 Privacy Loss
10
Privacy
Figure SGD unlearning. Unlearning vs, privacy score for ResNet-18 on SVHN (left) and ViT-small on CIFAR-I0 (right). Unlearning time is measured in steps required to reach a 5% UA error margin.
Compute resources
Experiments were conducted using L40 and RTX8000 GPUs, and AMD EPYC 7452 CPUs.
E. Evaluation metrics
Membership Inference Attack Membership inference attacks (MIA) aim to determine whether given sample was part of a model's training data by analyzing differences the model's responses. In our approach, we train a logistic regression classifier using the model's confidence values on training and test samples as inputs. The attacker then attempts classify the forget samples, with success measured by the percentage of forget samples labeled as test, indicating effective unlearning.
Gaussian Unlearning Score We use the Gaussian Unlearning Score (GUS), introduced by Pawelczyk et al. (2024), to quantify the impact of poisoned samples on the model. To compute GUS, each sample in the forget set is perturbed with zero-mean Gaussian noise with a standard deviation a. GUS is then computed by averaging (over the forget set) the per-example inner product between the gradient of loss with respect to the clean (non-poisoned) sample and the stored Gaussian noise used for poisoning, normalized by the L2 norm of the gradient. The effectiveness of unlearning method then assessed by how well it mitigates the influence of these poisoned samples. Specifically, the change in GUS before and after unlearning serves measure of unlearning success.
For the CIFAR-10 10 and ResNet-18 setup, the original work recommends a variance value of 0.32. However, in our experiments, we explored different values and found that smaller variances were better suited for our setup. Based on these empirical findings, we set x² 0.062.
F. Additional Experimental Results
F.1. Unlearning trends during fine-tuning
In this experiment, apply the fine-tuning method unlearn a ResNet-13 18 model trained on the full CIFAR-10 dataset. The forget set varies in difficulty, with five different levels determined by the proxy losses of the samples. The UA, utility and RA values during unlearning is depicted in Figure 5 (top), while the MIA results are depicted in Figure (bottom). For UA and MIA, we see the most difficult forget sets do indeed take longer to unlearn. We see utility and RA are similar across difficulty levels.
F.2. LI sparse fine-tuning
The unlearning results for the L1-sparse method are presented in Figure 6. Similar to our observations for unlearning with SGD or SGLD fine-tume men-unnng, unlearning with LI-sparse takes longer to forget samples with higher privacy scores. In fact, the more challenging the forget sets, the longer the unlearning.
15

---

Leveraging Per-Instance Privacy for Machine Unlearning
tn (5% ACC: Fin)
unlearn (5% ACC Em
-5
20
20
10
10
10
10
10
Privacy Loss
Privacy Loss
Privacy Loss
Figure Unlearning time forget sets (left), 5,000 (middle), and 10,000 (right), evaluated on CIFAR-10. Unlearning time reported as the number of training steps required to achieve UA error within 5%.
F.3. Additional datasets/arcchitccturss
In addition to ResNet-18 on CIFAR-10, we conduct experiments with additional dataset-arcciitecture pairs. Specifically, we evaluate ResNet- on SVHN and ViT-small on CIFAR-1O. ViT-small Vision Transformer model that applies self-attention mechanisms to sequences of image patches, enabling effective global feature extraction. Figure presents the unlearning results for ResNet-18 on SVHN (left) and ViT-small on CIFAR-10 (right). The results suggest that, consistent with our previous findings, unlearning takes longer for forget sets with higher average privacy loss.
Rankings across noise levels We experiments test sensitivity of the ranking for SGD the noise values used in estimating privacy losses. For SVHN with ResNet-18 we found: (1) Spearman correlation between rankings at 0.01 and a = 0.001 was 0. 0.p = 0.0). (2) Between 0.001 and a 0.0005 was 0.99(p = 0.0). (3) Between = 0.0005 and a = 0.0001 was (p = 0.0). These results suggest that rankings are largely noise-invariant, as long as some noise is present. Past work has shown evidence of observable noise during training due to software and hardware non- determinism (Jia et al., 2021).
Figure 9, Qualitative examples of forgetting difficulty CIFAR-10, 10. We show 4 examples each from the casy-to-forget (top row) and hard-to-forget (bottom row) subsets, identified from a forget set of 1,000 samples.
16

---

Leveraging Per-Instance Privacy for Machine Unlearning
F.4. Varying Forget Set Sizes
We conducted additional experiments varying the size of the forget (100, 5,000, and 10,000 samples). The results presented in Figure 8. Our findings indicate that privacy loss consistently distinguishes between easy and hard-to-forge subsets, even when the forget set is small. Interestingly, for very large forget sets (e.g., 10,000 samples), the separation begins to diminish. This observation is intuitive, as the variance in average privacy loss decreases with increasing subset size.
E55. Qualitative Results
Qualitative examples of easy and hard to forget CIFAR-10 samples are provided in Figure 9.
17


Reviews:
[{"review_id": "yc97H0cylN", "reviewer": "Reviewer_T3UX", "summary": "This paper considers the machine unlearning problem, which involves removing the influence of a subset of training data from a trained model. The authors explored a setup in which both learning and unlearning are done via noisy gradient descent and proposed to use the \"per-instance privacy loss\" to estimate the unlearning difficulty.  theoretically demonstrate that the number of unlearning rounds depends at most logarithmically on the \"per-instance privacy loss\" (Corollary 4.4).  Additionally, the authors presented extensive experimental results indicating that \"per-instance privacy loss\" provides a more accurate estimation of unlearning difficulty (i.e., time to unlearn) compared to existing proxy metrics, and it effectively identifies examples that are challenging to unlearn.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. Your review raises two main concerns: (1) the completeness of comparisons with alternative proxy metrics, and (2) the clarity of our empirical claims regarding how accurately privacy losses predict unlearning difficulty. To address the first concern, we have expanded our experiments to include comparisons against additional proxies—EL2N and Average Gradient Norm. These comparisons (available at https://files.catbox.moe/uc54l5.png) support our original finding: privacy loss consistently identifies harder-to-unlearn examples than existing metrics.\n\n\nRegarding the second concern about the clarity of our empirical claims, we believe the ambiguities arise from our dense discussion in our original draft. Below, we describe how we have revised the text to clarify that our claims are already supported by existing figures---e.g., Figure.1 shows privacy losses can rank points by number of unlearning steps, while Figure.3 compares the \"hardness\" of C-proxy and our approach, as measured by training steps to unlearn. We have also clarified definitions where needed. Below we respond to individual points raised in the review.\n\n\n**Claims And Evidence 1. Figure.2 does not directly relate to unlearning difficulty**\n\n\nWe have revised the text for clarity: Figure.2 demonstrates that past metrics correlate well with privacy losses. When discussing \"overestimating difficulty\" we now clearly refer to Figure.3 in our paper, which shows the hardest points identified by C-proxy take fewer steps to unlearn than the hardest points identified by privacy losses. Furthermore, we are updating Figure.3 to also include EL2N and Average Gradient Norm; we found privacy losses still identify the harder datapoints. See updated results at https://files.catbox.moe/uc54l5.png. \n\n\n**Claims And Evidence 2. No predictive rule correlating privacy losses and the number of unlearning steps**\n\n\nWe appreciate this point. Our intended claim is not that privacy losses predict the exact number of steps, but rather that they accurately rank datapoints by how long they take to unlearn. This is shown in Figure.1, where unlearning time increases with privacy loss. We will revise the language to say: “privacy losses accurately rank datapoints according to the number of steps needed to unlearn.”\n\n\n**Claims And Evidence 3. Compared privacy loss only with C-Proxy In Figure.3**\n \n\nAs mentioned above, we have now included EL2N and Average Gradient Norm in our experiments. Privacy loss remains more effective at identifying hard-to-unlearn examples. \n\n\n**Experimental Designs Or Analyses 2.Number of checkpoints (N) used in estimating privacy loss**\n\n\nWe used 35 checkpoints, evenly spaced across the 150 training epochs (47,000 steps). We will add this clarification.\n\n\n**Experimental Designs Or Analyses 3.Do privacy losses also identify easy-to-unlearn data?**\n\n\nYes. As shown in Figure.1, datapoints with the lowest privacy loss scores require virtually no unlearning steps. More broadly, privacy loss correlates with unlearning time across the full range of scores—higher privacy loss values generally correspond to more steps required to forget a sample. This pattern is shown in Figure.1 (middle panel) and is consistent with the trend observed in Figure.5.\n\n\n**Weaknesses 1. privacy loss does not accurately estimate unlearning difficulty for groups**\n\n\nWe appreciate this concern. In Appendix B, we evaluated Thudi et al.’s group-based method and found it failed to distinguish between easy and hard-to-unlearn subsets. In contrast, simply averaging our per-instance privacy losses did capture group-level difficulty (see Figure.1). We believe this result is both practical and empirically sound—and it highlights a useful direction for theory to catch up with practice in deep learning.\n\n\n**Weaknesses 2. Estimating privacy loss may be resource-intensive**\n \n\nWe estimate privacy losses using gradients from just 35 of the 47,000 training steps—only a small fraction of the training cost. By contrast, other metrics like C-Proxy and Average Gradient Norm rely on access to every training checkpoint (150 epochs). EL2N avoids this but performs worse. So our method strikes a good balance between efficiency and predictive power.\n\n\n**Other Comments Or Suggestions. \"5% margin\" in caption of Figure.1 is unclear**\nThanks for pointing this out. We will clarify that the \"5% margin\" refers to the value of the unlearning metric (e.g., UA or MIA) measured on the oracle model: i.e., we're within 5% of the oracle UA (or MIA), depending on the metric being evaluated.", "claims_and_evidence": "1. The authors stated in line 401 that \"Figure 2 reveals that all these proxies overestimate the difficulty.\" However, Figure 2 only presents a comparison of proxies against privacy loss and does not directly relate to unlearning difficulty. To substantiate the claim that a metric overestimates difficulty, the authors should provide evidence showing that data points with relatively high metric values can be unlearned in the same (or even fewer) number of rounds as those with lower values.\n\n2. In Section 6, the authors asserted that \"privacy losses accurately predict the number of unlearning steps.\" While the empirical results indicate that the time to unlearn increases with privacy loss, this alone does not justify the term \"accurately,\" as there is no established predictive rule correlating privacy loss to the exact number of unlearning rounds.\n\n3. In Section 6.4, the authors compared privacy loss only with the C-Proxy. It is unclear why they did not include comparisons with other proxy metrics mentioned in Section 6.3. Are those other metrics demonstrated to be less effective than C-Proxy in previous work?", "methods_and_evaluation_criteria": "The learning and unlearning algorithms, as well as the datasets used, are appropriate for addressing the unlearning problem discussed in the article.", "theoretical_claims": "I did not conduct a thorough review of the proofs, but they appear to be correct.", "experimental_designs_or_analyses": "The authors provided comprehensive experiments to support their proposed \"per-instance privacy loss\". \n\n1. I have raised some questions regarding the claims made based on the experimental results in the \"Claims and Evidence\" section.\n\n2. I would like to inquire about the number of checkpoints ($N$) used in estimating the per-instance privacy loss.\n\n3. While the experiments demonstrate that privacy losses can identify data that are hard to unlearn, do they also indicate which data are easy to unlearn?", "relation_to_broader_scientific_literature": "Unlearning has significant implications for user privacy, as it enables users to delete their data from the trained model, and it can contribute to the development of more robust machine learning models by removing malicious examples. Additionally, the proposed technique may serve as a method for detecting outliers within datasets.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1. The idea of employing the Loss Landscape to demonstrate how geometric properties reflect unlearning difficulty is intriguing.\n\n2. The authors conducted comprehensive experiments that effectively support their proposed method.\n\nWeaknesses:\n\n1. The proposed privacy loss may not accurately estimate unlearning difficulty for groups, as it focuses on per-instance loss and does not account for correlations within the group.\n\n2. Estimating the per-instance privacy loss could be resource-intensive, as it requires gradients from multiple checkpoints.", "other_comments_or_suggestions": "The definition of \"5% margin\" in the caption of Figure 1 is not sufficiently clear. I recommend using the definition provided in Figure 6, which is more precise, as it specifies that \"5% margin\" means the difference between the unlearned model’s UA and the oracle’s UA for the given forget set.", "questions_for_authors": "I would appreciate it if the authors could address my concerns raised in the \"Claims and Evidence\" section.", "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": "iD4hObHkRC", "reviewer": "Reviewer_PpYB", "summary": "This paper provides a theoretical foundation to understand the relationship between per-instance privacy loss and unlearning hardness. It applies a recent per-instance privacy loss to fine-tuning-based unlearning and builds a relationship bewteen unlearning steps with the bound of Renyi divergence between a model trained with and without an individual data point. They then empirically show the relationship of the per-instance privacy loss to approximate unlearning steps.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. Your review primarily raises concerns about the practical utility of our proposed privacy loss metric—specifically, whether its per-instance theoretical guarantees translate to improved empirical unlearning performance. You also highlight the focus on group-level experiments and question whether our comparisons with existing metrics fairly demonstrate superiority. We appreciate these comments and have expanded our response and experiments accordingly.\n\n\nAs outlined below, we clarify that our empirical results already show practical value, particularly by demonstrating that examples with low privacy loss consistently require near 0 unlearning steps. We also include new comparisons against EL2N and Average Gradient Norm, which confirm that privacy loss better identifies harder-to-unlearn datapoints. Taken together, our theoretical and empirical results reinforce the claim that our proposed privacy loss metric is valuable for explaining unlearning performance.\n\n\n**Claims And Evidence. Lack of evidence for practical impact**\n\n\n Figure.1 demonstrates that datapoints identified as easy by privacy loss require near-zero steps to unlearn with fine-tuning. We believe this already shows practical impact: for examples in the easiest quantiles, unlearning can be achieved with just a few fine-tuning steps. This allows privacy loss to serve as a signal for when minimal unlearning is sufficient—something existing metrics do not support as reliably.\n\n\n**Experimental Designs Or Analyses 1. Including experiments demonstrating ​per-instance privacy loss alignment to unlearning steps**\n\n\nThis alignment is already shown in Figure.1, where we demonstrate that privacy loss ranks groups of datapoints by the number of steps needed to unlearn them. Our group-level results are derived by averaging per-instance privacy losses, which provides a straightforward way to extend pre-computed individual guarantees. We also tested Thudi et al.’s group privacy analysis and found it too loose to distinguish between easy and hard groups (Appendix B), further highlighting the value of our empirical approach. Future work on group privacy could study the correctness/discrepancy with averaging per-instance data points to improve the current group privacy theory.\n\n\n**Experimental Designs Or Analyses 2. Claim about overestimation in Figure.2**\n\n\nWe agree that the original claim in Figure.2 was misleading. We now clarify that Figure.2 shows a correlation, but not necessarily overestimation due to scaling mismatches. The overestimation claim is instead supported by Figure.3, which demonstrates that datapoints identified as “hard” by other metrics are in fact easier to unlearn than those identified as hard by privacy loss. To further support this point, we’ve added new experiments comparing privacy loss against EL2N and Average Gradient Norm. Privacy loss continues to identify harder examples more effectively. These results are available at https://files.catbox.moe/uc54l5.png and will be added to our revised draft.\n\n**Other Comments Or Suggestions. Request for overlap analysis or examples**\n\n\nWe have included a qualitative example showing four randomly selected images from both an easy-to-forget set (https://files.catbox.moe/2qdv6h.jpg) and a hard-to-forget set (https://files.catbox.moe/tzm6ac.jpg), each of size 1000 and constructed from the CIFAR-10 dataset. Regarding the distribution overlap, we would be happy to provide it—could the reviewer kindly clarify which specific distribution they are referring to?\n\n\n**Questions For Authors. Could privacy loss help reduce unlearning time?**\n\n\n Yes—this is already possible using our results. For instance, in Figure.1 we show that the easiest 50% of datapoints (as measured by privacy loss) can be unlearned in fewer than five fine-tuning steps. This suggests a simple strategy: apply lightweight fine-tuning for low-privacy-loss points, and use stronger methods (e.g., retraining or more targeted interventions) for datapoints flagged as difficult. This could easily be integrated into frameworks like RUM [1], where privacy loss can guide refinement.\n\n\n[1] Zhao, Kairan, et al. \"What makes unlearning hard and what to do about it.\" Advances in Neural Information Processing Systems 37 (2024): 12293-12333.", "claims_and_evidence": "The paper’s contributions are primarily theoretical. While proposing a novel metric for per-instance unlearning difficulty, it lacks evidence of practical impact (e.g., would unlearning-via-fine-tuning methods with the proposed privacy loss perform better than relying on gradient norms?). Stronger empirical validation (e.g., comparative experiments) is needed to demonstrate real-world utility.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "This paper provides a better convergence analysis of $U_{k}(\\alpha, \\epsilon^*)$-Renyi unlearning. By directly applying the per-instance privacy loss from Thudi et al. ( 2024) into the unlearning setting, this paper builds the bound of Renyi divergence between a model trained with and without an individual data point. Then it builds a connection between the unlearning steps and the Renyi divergence bounds, which is bounded by the per-instance privacy loss. Then it is able to use per-instance privacy loss to predict per-instance unlearning hardness.", "experimental_designs_or_analyses": "- All experiments focus on group unlearning; however, the theoretical analysis provides guarantees only for per-instance scenarios. Including experiments demonstrating ​per-instance privacy loss alignment to unlearning steps would strengthen the practical relevance of the theoretical claims.\n- ​Figure 2: The authors claim that existing proxy privacy losses overestimate unlearning difficulty, but this may stem from scaling differences (e.g., the per-instance hardness  is logarithmic with respect to the proposed loss). A fairer comparison is required. (Figure 3 partially addresses this but only contrasts with C-Proxy, which appears to underperform in Figure 2).", "relation_to_broader_scientific_literature": "This work establishes a theoretical foundation to support prior observations that specific forget sets exhibit inherent challenges during unlearning.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- if you could provide the distribution overlap between the constructed forget set and retain set or show any identified hard-to-forget examples, it would be helpful to understand the metric.", "questions_for_authors": "- I’m curious if we could use the proposed privacy loss to enhance unlearning performance or reduce unlearning time, like what Zhao et al. (2024) did. Could you show me how?", "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": "YYnWUPcJt1", "reviewer": "Reviewer_R2F4", "summary": "The paper proposes a per-instance approach to quantifying the difficulty of unlearning via fine-tuning by replacing the worst-case Rényi-DP bound with per-instance privacy losses. The authors introduce loss barriers as a way for evaluation, which are significantly reduced after unlearning. Alternative cheap proxy measures of data difficulty are explored for better efficiency. Empirical results demonstrate that the privacy losses offer a precise and actionable measure of unlearning difficulty and could identify harder data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Your review focuses on question around the computational efficiency of our method for computing per-instance privacy losses, especially in the context of large-scale models and datasets. You also provide suggestions for improving the clarity of figure and definitions, which we address below.\n\n\nPerhaps the most important statement for us to make about efficiency is that _our approach is significantly more efficient than all alternatives we study__ with the exception of EL2N which is inferior. We require gradients from only 35 checkpoints from the 150 training epochs. At present, alternative methods currently rely on all checkpoints. We also appreciate your suggestions for improving our illustrations and definitions, and we have incorporated them into our planned revisions. Our detailed responses aim to reinforce a key point: our method efficiently and reliably quantifies unlearning difficulty, maintaining practical feasibility even for larger models and datasets.\n\n\n**Weaknesses. Computational efficiency and practical applicability**\n \n\nTo clarify, our method requires storing 35 checkpoints and computing gradients on them for the datapoints being evaluated. Given that our full training run consists of 150 epochs, the  estimation of per-instance guarantees for the whole dataset costs about 20% of training time. Other methods, such as C-Proxy and Average Gradient Norm, are more expensive: C-Proxy averages predicted probabilities across all 150 training checkpoints, and Average Gradient Norm computes gradients at every checkpoint. In contrast, we use only 35 evenly spaced checkpoints. While EL2N is cheaper, it performs worse in identifying hard-to-unlearn examples (see https://files.catbox.moe/uc54l5.png).\nRegarding the idea of using privacy loss for model pruning, we weren’t entirely sure what the reviewer meant—could you clarify this suggestion further?\n\n\n**Other Comments Or Suggestions. Using figure illustrations**\n\n\n Thank you for the helpful suggestion. We will include a similar diagram in the revised draft, following Chien et al. (2024), but highlighting that initial divergence varies across datapoints and that many datapoints begin with near-zero divergence---indicating they require almost no steps to unlearn.\n\n\n**Questions For Authors. Clarification on Figure.1 caption**\n\n\n We appreciate the chance to clarify this. Due to stochasticity in training (e.g., minibatch sampling, GPU nondeterminism), two runs on the same dataset can result in slightly different models. To control for this noise in loss barrier evaluations, we compute the loss barrier between two models trained independently on the same retain dataset. These serve as “oracles” representing ideal retraining, and the baseline corresponds to the loss barrier between them. This gives us a reference point for how small the barrier can be when unlearning is perfect.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The reviewer did not check the correctness of the proofs.", "experimental_designs_or_analyses": "The reviewer has checked all of the experimental designs.", "relation_to_broader_scientific_literature": "This paper presents work whose goal is to advance the field of machine unlearning, which is specifically oriented to improve the trustworthiness of machine learning.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper innovatively introduces per-instance privacy losses for unlearning difficulty measurement and provides theoretical unlearning guarantees.\n2. The paper is well-structured. The narrative is easy to follow.\n\nWeaknesses:\n\n1. Computing per-instance privacy losses requires storing and processing gradients throughout training, which can be computationally expensive, especially for large-scale models and datasets. This limits the practicality of the approach. The reviewer supposes that the proposed method can serve as a strategy for model pruning before unlearning, which can then be used to design experiments on more complex datasets and models.", "other_comments_or_suggestions": "Using figure illustrations aiding analysis in Section 4 and Section 5.2 would be better, as done in Chien et al,. 2024.", "questions_for_authors": "In the caption of Figure 1, what do you mean by \"Baseline corresponds to the loss barrier between two oracles\"? What are the \"two oracles\" here?", "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": "H4A3M99Pfa", "reviewer": "Reviewer_DFL7", "summary": "This paper presents a per-data sample approach to quantifying the difficulty of unlearning the same via fine-tuning. They do this by adapting the definition and analysis of Thudi et al. (https://arxiv.org/abs/2307.00310) on per-instance DP to the unlearning setting to produce a quantity called a “privacy loss”, which measures the difficulty of unlearning a particular sample. This privacy loss can be straightforwardly used to get a tighter estimate on the number of finetuning steps needed to unlearn a sample. They validate the usefulness of privacy losses through experiments, and introduce “loss barriers” as another empirical measure for the difficulty of unlearning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Your review raises two key concerns: the completeness of experimental comparisons between our proposed privacy loss and other proxy metrics, and the practical value of the newly introduced “loss barrier” measure. You also suggest clarifying definitions and improving the accessibility of the theoretical explanations.\n\n\nIn response, we have expanded our experiments to include comparisons against EL2N and Average Gradient Norm, which further confirm that privacy loss is more effective in identifying difficult-to-unlearn examples. We also clarify the purpose and practical relevance of the loss barrier metric, showing that it provides an additional, independent way to evaluate unlearning efficacy. Each of your points is addressed below, underscoring that our proposed metrics provide robust, practical, and comprehensive methods for evaluating unlearning difficulty.\n\n**Theoretical Claims. Unclear definition of privacy loss**\n \n\nCould the reviewer clarify which parts of the definition were unclear? We recognize that the current form includes several moving parts, and we will revise the explanation to improve accessibility in the final draft.\n\n\n**Weaknesses 1. Need for broader comparison in Figure.3**\n\n\n We agree. In addition to C-Proxy, we have now conducted comparisons with EL2N and Average Gradient Norm. Privacy loss continues to identify harder-to-unlearn examples than all alternatives. The new figure is available at https://files.catbox.moe/uc54l5.png and will be included in the revised draft.\n\n\n**Weaknesses 1. No discussion on relative computational cost of different proxies**\n\n\n Thank you for raising this point. We computed privacy losses using 35 evenly spaced training checkpoints (from the 47,000 steps of training). All other methods—except EL2N—require access to all training checkpoints, making them more expensive. C-Proxy averages predictions across all checkpoints, while Average Gradient Norm uses gradients computed at each checkpoint. EL2N is cheaper but less effective, as shown in the new comparison figure linked earlier.\n\n\n**Weaknesses 2. Unclear motivation behind the loss barrier metric**\n\n\nThe loss barrier provides an additional way to assess unlearning, providing a novel membership inference (MI) attack. Specifically, discrepancies from the expected loss barrier between two oracle models can indicate whether unlearning was successful. This provides a novel way to assess whether the model has achieved the correct loss geometry after unlearning—something not captured by existing metrics, which focus only on changes in output or loss at individual points. Its contribution to the paper is to offer another metric to evaluate our main claim: that privacy losses accurately predict unlearning difficulty.\n\n\n**Other Comments Or Suggestions. Clarify UA/MIA/GUS in Figure.1**\n\n\n Thank you—we will revise the caption in Figure.1 to clearly define these terms.", "claims_and_evidence": "The paper proposes a per-sample privacy loss which they claim indicates the difficulty of unlearning the sample. They show theoretically that this privacy loss controls the finetuning steps needed to unlearn. They also show empirically that the privacy loss correlates with the number of steps needed to unlearn a set of items. These claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense to me.", "theoretical_claims": "The theoretical claims appear to make sense. However, it was hard to understand the privacy loss definition so I could not verify it rigorously.", "experimental_designs_or_analyses": "The experimental designs made sense to me. They performed five experiments:\n1) Testing that privacy loss corresponds to number of steps needed to unlearn\n2) Testing that privacy loss corresponds to the difficulty of privacy violating attacks\n3) Testing that loss barrier also corresponds to privacy loss\n4) Testing that privacy loss corresponds to other known measures of the difficulty of unlearning\n5) Testing that privacy loss is a better measure of difficulty of unlearning vs C-Proxy by showing it can select harder forget sets\n\nAll of the setups made sense and showed what they were supposed to show. I think experiment 5 could be expanded upon, as it only compares against C-Proxy.", "relation_to_broader_scientific_literature": "The paper is related to the broader unlearning literature, and takes the differential privacy approach. The paper does a good job of discussing the related work.", "essential_references_not_discussed": "Not that I know of", "other_strengths_and_weaknesses": "Strengths\n- The paper is a very timely publication that combines the analysis of Chien et al. https://openreview.net/forum?id=3LKuC8rbyV which analyzes the number of steps needed to unlearn a set of data points using the DP framework, and the analysis of Thudi et al. (https://arxiv.org/abs/2307.00310) which introduces per-instance privacy. By combining these two, they can produce a tighter analysis of the difficulty of unlearning data samples.\n- The claims are well-supported with theoretical analysis and experiments\n- The paper produces a clear contribution to the literature: a new measure of the difficulty of unlearning data samples which appears to be the best, pending more experimental evidence.\n\nWeaknesses\n- The value of this paper in practice would be in showing that privacy losses are the most accurate way to measure the difficulty of unlearning. The only figure that tries to demonstrate this is Figure 3. However, it only compares against C-Proxy. There are other proxy metrics (as shown in Figure 2), so it is important to compare privacy losses against all of them to be sure of the value of privacy losses in practice. Related to this, it would be good to include a discussion of the relative cost of computing each of these proxies compared to their relative accuracy at predicting the difficulty of unlearning.\n- From what I understand, the loss barrier computes the sharpness of the loss curve between two different models. The authors compute the sharpness of the loss between the oracle model (the perfectly unlearned model) and the model before/after unlearning. The experiments show that the sharper the curvature on a particular set of data is, the sharper the curvature is. This analysis is nice, but I'm wondering what the motivation for this is? Does this loss barrier work help us in any tangible way?", "other_comments_or_suggestions": "- Nit: figure 1 should explicitly write out what UA/MIA/GUS mean", "questions_for_authors": "1. Can you provide a more comprehensive experiment for Figure 3 comparing against the known ways to measure unlearning difficulty? It is critical to make this comparison comprehensive IMO.\n2. What is the value of the loss barrier discussion?", "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": "ZsxolYJaoC", "reviewer": "Reviewer_1kMk", "summary": "This work introduces a theoretically grounded, data-dependent measure of difficulty between data privacy and unlearning. While the current analysis has limitations (scalability, group guarantees), the empirical results are compelling.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Your review raises several important points: concerns about scalability to larger models and datasets, the practical implications of group-level unlearning, assumptions around noise in SGD, and the strength of causal interpretations in our analysis. You also asked about sensitivity to experimental parameters such as forget set size.\n\n\nWe address these concerns below with additional experiments and clarifications. We show that privacy losses remain predictive across varying forget set sizes and are robust to assumptions on implicit SGD noise. Our method remains practical even when theoretical guarantees do not extend cleanly to group unlearning, as we demonstrate empirical effectiveness. Furthermore, we explain clearly why our causal interpretations are theoretically grounded, rather than simply correlational. Finally, we discuss computational cost in the context of scalability.\n\n\n**Experimental Designs Or Analyses.Unclear effect of forget set size**\n\n\n We ran additional experiments varying forget set size and found that privacy losses consistently separate easy and hard sets, even with smaller subsets. As set size increases, differences become smaller: this is intuitive as the variance in average privacy loss gets smaller. Figures for forget set sizes 100, 5,000, and 10,000 are available at:\n https://files.catbox.moe/l8ky5z.png,\n https://files.catbox.moe/odaa0g.png,\n https://files.catbox.moe/dqxk61.png.\n We will include these results and discussion in the revised draft.\n\n\n**Other Strengths And Weaknesses 1. Lack of scalability to larger models and datasets**\n \n\nWhile more large-scale experiments would strengthen our claims, we already include several evaluations across multiple models and datasets (and SGLD noise). We’d appreciate clarification on what specifically the reviewer would want to understand by using larger models.\n\n\n**Other Strengths And Weaknesses 2.Group-level guarantees lack theoretical tightness**\n\n\nOur experiments show that averaging per-instance privacy losses still reliably ranks groups by unlearning difficulty (see Figure.1). Though empirical, this provides a promising direction for future theoretical development on group privacy, especially as the current group analysis is too loose.\n\n\n**Other Strengths And Weaknesses 3. Assumed noise in SGD lacks justification**\n\n\n We ran experiments to test sensitivity to noise values used in estimating privacy losses. For SVHN with ResNet-18: (1) Spearman correlation between rankings at σ = 0.01 and σ = 0.001 was 0.70 (p = 0.0). (2) Between σ = 0.001 and σ = 0.0005 was 0.99 (p = 0.0). (3) Between σ = 0.0005 and σ = 0.0001 was 0.99 (p = 0.0). These results suggest that rankings are largely noise-invariant, as long as some noise is present. Past work has shown evidence of observable noise during training due to software and hardware non-determinism [1]. We will include this discussion in our revised version.\n\n\n[1] Jia, Hengrui, et al. \"Proof-of-learning: Definitions and practice.\" 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021.\n\n\n**Other Comments Or Suggestions. Correlation vs causality**\n\n\n Our theory establishes a link between privacy loss and the number of unlearning steps, stating that small privacy loss means only a few steps are required to unlearn. We would appreciate clarification on what is meant by a “causal effect perspective,” as our goal is to measure difficulty, not to infer intervention outcomes. We welcome suggestions if there's a specific causal framework the reviewer believes is applicable here.\n\n\n**Questions For Authors. Scalability of computation and checkpointing**\n\n\n Our method computes privacy loss using gradients from only 35 (out of total 150 training epochs giving 47,000 steps). In contrast, C-Proxy averages predictions over all 150 epochs of  checkpoints. Average Gradient Norm also averages gradients from all training epochs. EL2N is cheaper, but less predictive (see https://files.catbox.moe/uc54l5.png). Using only 35 checkpoints makes our method more efficient and scalable than most alternatives. We agree that techniques like gradient checkpointing or sampling could further reduce cost and plan to explore these in future work.", "claims_and_evidence": "The identification of \"harder\" forget sets via privacy losses and the loss barrier analysis offer actionable insights for evaluating and improving unlearning algorithms.", "methods_and_evaluation_criteria": "Extensive experiments on SGLD, SGD, and L1-Sparse unlearning demonstrate the practical relevance of privacy losses. The inclusion of loss barrier analysis adds a geometric perspective to unlearning efficacy.", "theoretical_claims": "The paper provides a novel theoretical framework for per-instance unlearning difficulty using Renyi divergence and differential privacy. By replacing worst-case DP bounds with per-instance privacy losses, it offers a more nuanced understanding of unlearning dynamics.", "experimental_designs_or_analyses": "How does varying the forget set size (e.g., 10% vs. 50% of data) affect the predictive power of privacy losses?", "relation_to_broader_scientific_literature": "The correlation between privacy losses and established proxies (e.g., C-Proxy, EL2N) bridges theory and heuristic approaches, grounding the work in prior literature.", "essential_references_not_discussed": "Not any.", "other_strengths_and_weaknesses": "Weakness: 1) Experiments are limited to small-scale datasets (CIFAR-10, SVHN) and architectures (ResNet-18/ViT). The scalability to large models (e.g., LLMs) or massive datasets remains unverified. 2) The paper acknowledges that group unlearning guarantees are not tight but does not propose concrete steps to address this gap. This limits practical applicability for multi-point deletion. 3) For SGD experiments, privacy losses are computed under an assumed implicit noise (σ ≤ 0.1). While pragmatic, this lacks theoretical justification and may not hold in non-stochastic settings.", "other_comments_or_suggestions": "The paper emphasizes correlation with existing proxies but does not rigorously establish causality between privacy losses and unlearning difficulty. The correlation seems trivial and needs more analyzed, for example, from casual effect perspective. The Monte Carlo estimation of privacy losses via checkpoints may introduce bias.", "questions_for_authors": "How do loss barriers correlate with adversarial robustness or membership inference attack success? Do smaller barriers imply better security post-unlearning?  Were other data difficulty metrics (e.g., influence functions) considered? How do they compare to privacy losses in terms of cost and predictive power? How does the computational cost of estimating per-instance privacy losses scale with model size (e.g., transformers) and dataset size? Could gradient checkpointing or sampling mitigate this? Can you provide empirical/theoretical evidence that the implicit noise assumption in SGD holds? How sensitive are the results to the choice of σ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a theoretically grounded and empirically validated framework for quantifying per-instance unlearning difficulty via privacy loss, with connections to Rényi divergence and DP guarantees. The paper is well-organized, with clear claims and extensive experiments demonstrating that privacy loss can effectively rank examples by unlearning difficulty.

Reviewer consensus generally leaned positive. The reviewers appreciated the novelty of per-instance privacy loss as a theoretically justified metric for unlearning hardness, and the extensive empirical evaluation across unlearning setups such as SGD, SGLD, L1-sparse fine-tuning etc. Reviewers also valued the addition of loss barrier analysis as a complementary geometric perspective.

There were also some reasonable concerns raised. The main critique is the limited practical evidence that privacy loss enables faster or more efficient unlearning in real-world systems. Reviewers also asked for a more comprehensive comparison against existing proxy metrics (EL2N, Average Gradient Norm), which the authors addressed convincingly in the rebuttal with new experiments. The cost of estimating privacy loss remains non-trivial (35 checkpoints), although the authors argue it is cheaper than alternatives like C-Proxy.  

Overall, the paper makes a clear, well-supported theoretical and empirical contribution to the growing literature on machine unlearning. While not all practical challenges are resolved, the work is timely, rigorous, and likely to influence future research.
Decision: Accept (poster)