Leveraging Per-Instance Privacy for Machine Unlearning

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.

We 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.

Experimental Designs Or Analyses.Unclear effect of forget set size

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: https://files.catbox.moe/l8ky5z.png, https://files.catbox.moe/odaa0g.png, https://files.catbox.moe/dqxk61.png. We will include these results and discussion in the revised draft.

Other Strengths And Weaknesses 1. Lack of scalability to larger models and datasets

While 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.

Other Strengths And Weaknesses 2.Group-level guarantees lack theoretical tightness

Our 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.

Other Strengths And Weaknesses 3. Assumed noise in SGD lacks justification

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.

[1] Jia, Hengrui, et al. "Proof-of-learning: Definitions and practice." 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021.

Other Comments Or Suggestions. Correlation vs causality

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.

Questions For Authors. Scalability of computation and checkpointing

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.

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.

Perhaps 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.

Weaknesses. Computational efficiency and practical applicability

To 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). Regarding the idea of using privacy loss for model pruning, we weren’t entirely sure what the reviewer meant—could you clarify this suggestion further?

Other Comments Or Suggestions. Using figure illustrations

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.

Questions For Authors. Clarification on Figure.1 caption

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.

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.

In 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.

Theoretical Claims. Unclear definition of privacy loss

Could 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.

Weaknesses 1. Need for broader comparison in Figure.3

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.

Weaknesses 1. No discussion on relative computational cost of different proxies

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.

Weaknesses 2. Unclear motivation behind the loss barrier metric

The 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.

Other Comments Or Suggestions. Clarify UA/MIA/GUS in Figure.1

Thank you—we will revise the caption in Figure.1 to clearly define these terms.

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.

As 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.

Claims And Evidence. Lack of evidence for practical impact

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.

Experimental Designs Or Analyses 1. Including experiments demonstrating ​per-instance privacy loss alignment to unlearning steps

This 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.

Experimental Designs Or Analyses 2. Claim about overestimation in Figure.2

We 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.

Other Comments Or Suggestions. Request for overlap analysis or examples

We 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?

Questions For Authors. Could privacy loss help reduce unlearning time?

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.

[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.

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.

Regarding 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.

Claims And Evidence 1. Figure.2 does not directly relate to unlearning difficulty

We 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.

Claims And Evidence 2. No predictive rule correlating privacy losses and the number of unlearning steps

We 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.”

Claims And Evidence 3. Compared privacy loss only with C-Proxy In Figure.3

As 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.

Experimental Designs Or Analyses 2.Number of checkpoints (N) used in estimating privacy loss

We used 35 checkpoints, evenly spaced across the 150 training epochs (47,000 steps). We will add this clarification.

Experimental Designs Or Analyses 3.Do privacy losses also identify easy-to-unlearn data?

Yes. 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.

Weaknesses 1. privacy loss does not accurately estimate unlearning difficulty for groups

We 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.

Weaknesses 2. Estimating privacy loss may be resource-intensive

We 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.

Other Comments Or Suggestions. "5% margin" in caption of Figure.1 is unclear Thanks 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.