REVIEW 4 major objections 6 minor 23 references
Leveraging Per-Instance Privacy for Machine Unlearning
T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper claims that the cost of unlearning a training point is governed by that point's per-instance privacy loss, and that the required number of fine-tuning steps grows only logarithmically in that loss.
desk verdict A real per-instance unlearning bound and an honest paper, but the headline empirical claim outstrips what the experiments actually test. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the per-instance privacy loss $P(x,\alpha)$ (Definition 4.2), a sum over training steps of R\'enyi divergence bounds for a single point $x$, computed from the norm of $x$'s gradient at checkpoints. It carries the argument by replacing the worst-case R\'enyi-DP bound in the Langevin-unlearning convergence analysis: Theorem 4.3 shows $D_\alpha(\nu_{T,D}\|\nu_{T,D\setminus\{x\}}) \le P(x,\alpha)$, and substituting that into the convergence corollary gives the logarithmic step bound of Corollary 4.4. The other load-bearing piece is the convergence analysis inherited from Chien et al., which controls the divergence after $k$ noisy fine-tuning steps by exponential decay plus an irreducible stationarity term.
What would settle it
Compute the actual per-point R\'enyi divergence to retraining, $D_\alpha(\nu_{T,D}\|\nu_{T,D\setminus\{x\}})$, for a small model, exactly for a linear model or by many retraining samples, and compare it with the paper's $P(x,\alpha)$; if $P(x,\alpha)$ is not an upper bound for some $x$, Corollary 4.4 fails. Separately, estimate the implicit per-step noise of SGD from hardware and software nondeterminism: if it is regularly above $\sigma \approx 0.1$, the bridge from the theory to noise-free fine-tuning is broken.
Extended reading notes
Core claim
The paper's central claim is Corollary 4.4: for any $\alpha > 1$, running noisy gradient descent for $k \ge A_\alpha \ln\big((B_\alpha P(x,4\alpha) + C_\alpha \varepsilon_{4\alpha-1})/(\delta - \varepsilon_{2\alpha-1})\big)$ steps $(\alpha,\delta)$-unlearns a single point $x$, where $P(x,\alpha)$ is the per-instance privacy loss of $x$ and the constants depend on $\alpha$ and problem smoothness parameters. In words, the unlearning work is logarithmic in the point's own influence, not in a worst-case dataset-wide constant. The paper backs this with Definition 4.2, a computable per-instance privacy loss derived from per-instance R\'enyi differential privacy composition, and with experiments showing that privacy-loss rankings predict the ordering of unlearning difficulty under SGLD, SGD, and L1-sparse fine-tuning. It further claims that privacy losses correlate with existing difficulty proxies yet identify more difficult forget sets, and that loss barriers between the unlearned and oracle models drop to baseline levels after unlearning while their initial height tracks privacy loss.
Load-bearing premise
The load-bearing premise is that SGD without explicit noise behaves, for privacy-loss accounting, like SGLD with a small fixed noise level ($\sigma \le 0.1$); if the implicit noise of real training is not small in the required sense, the paper's theory does not reach its headline setting of standard fine-tuning.
Editorial extensions
If this is right
- If the central claim is right, the per-point unlearning budget is logarithmic in the point's privacy loss: points with small loss can be forgotten in a handful of noisy fine-tuning steps.
- Forget sets can be ranked before unlearning by average per-instance privacy loss, and that ranking predicts which sets take longer to unlearn across SGLD, SGD, and L1-sparse fine-tuning.
- Per-instance privacy losses can be estimated from a single training run with only 35 checkpoints, roughly 20 percent of training time, making the ranking practical.
- Loss barriers provide a geometric check on unlearning: after fine-tuning, the barrier between unlearned and oracle models matches the oracle-oracle baseline, while harder points start with larger barriers.
- Existing difficulty proxies such as gradient norms, C-Proxy, and EL2N correlate with privacy losses, but privacy losses single out harder-to-unlearn points, offering a stricter evaluation target.
Reading between the lines
- A natural next step the paper does not take is an adaptive unlearning scheduler: use each point's privacy loss to set its individual fine-tuning budget, allocating more steps only where the logarithmic bound says they are needed.
- Because the ranking appears stable to the assumed noise level, the mechanism driving difficulty is probably gradient sensitivity rather than the Gaussian noise itself; a direct test would vary batch size, data augmentation, or optimizer hyperparameters and check whether privacy-loss rankings track the resulting changes in steps to unlearn.
- The paper's admitted gap on group unlearning suggests a concrete open problem: find a tight group-level bound that reproduces privacy-loss rankings of group difficulty; until then, group guarantees remain out of reach.
- If privacy losses are accepted as a principled data-difficulty score, they could double as a training-time diagnostic for memorization and for which points would be cheapest to delete under future right-to-be-forgotten requests.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes per-instance privacy losses, adapted from Thudi et al. (2024), to quantify the difficulty of unlearning individual training points via noisy gradient descent. It refines the analysis of Chien et al. (2024) to obtain a bound (Corollary 4.4) on the number of fine-tuning steps needed to unlearn a single point, with a logarithmic dependence on that point's per-instance privacy loss. Empirically, on CIFAR-10 and SVHN with ResNet-18 and ViT-small, the authors rank examples by estimated privacy loss, form forget sets of 1,000 examples with varying average privacy loss, and measure the number of fine-tuning steps needed to match an oracle under SGLD, SGD, and L1-sparse unlearning. They also compare privacy losses to existing data-difficulty proxies and introduce loss-barrier-based evaluation. The main claims are that per-instance privacy losses predict unlearning difficulty and that this holds even for standard noiseless fine-tuning.
Significance. If the central claim were fully supported, the paper would make a useful contribution: replacing worst-case privacy bounds with per-instance bounds is a principled, data-dependent refinement, and the logarithmic dependence in Corollary 4.4 is a concrete improvement over worst-case analyses. The empirical correlation between privacy losses and unlearning time, if validated at the individual-point level, could inform adaptive unlearning strategies. The paper is also transparent about several limitations, including the admitted looseness of group unlearning bounds and the open problem of justifying implicit noise in SGD. However, the current evidence is mostly at the group level, not the individual-point level, and the SGD results rest on an unverified equivalence to low-noise SGLD. These gaps are substantial because they sit exactly at the interface between the theoretical result and the headline empirical claims.
major comments (4)
- [Section 6 and Section 5.1] The experiments never unlearn individual data points: Section 5.1 forms five forget sets of 1,000 examples ranked by privacy loss, and Section 6.1 measures the time until the whole forget set's UA/MIA/GUS matches the oracle. Since Corollary 4.4 is per-instance and Section 4.3 explicitly concedes that the group unlearning analysis is not tight, the abstract's claim that 'privacy losses accurately rank datapoints' is not directly supported by the reported experiments. The authors should either add individual-point unlearning experiments or clearly reframe the empirical claims as group-level ranking results.
- [Section 5.1 and Corollary 4.4] The SGD experiments rely on the assumption that training without explicit noise behaves like SGLD with a fixed small noise scale sigma <= 0.1, and the text itself states that providing a theoretical justification for this assumption is an open problem. Because Corollary 4.4 applies only to noisy gradient descent with a known noise scale, the central claim that the theory extends to standard fine-tuning is unsupported for the SGD experiments. The authors should either (a) provide direct evidence of an effective implicit noise scale, for example by measuring the actual stochasticity due to nondeterminism, or (b) present the SGD results as heuristic and outside the scope of the theoretical guarantee, without claiming that they validate the theory.
- [Section 6.1 and Corollary 4.4] The bound in Corollary 4.4 contains dataset-dependent stationarity terms epsilon_{4*alpha-1} and epsilon_{2*alpha-1} that are not estimated or controlled in any of the experiments. Consequently, the observed monotone relationship between average privacy loss and unlearning time could in principle be driven by variation in these stationarity terms rather than by P(x, alpha). The paper should either provide estimates showing that the stationarity terms are comparable across forget sets, or state explicitly that the experiments test only the privacy-loss term under an unverified assumption about those terms.
- [Section 4.3 and Section 6] There is a logical mismatch between the theory and the experiments: the theoretical result is per-instance, but all reported unlearning evaluations are for groups of 1,000 examples, and the average of per-instance Renyi divergence bounds is not a bound on the divergence for the group. The paper itself notes in Section 4.3 that the group accounting is too loose to differentiate forget sets. This gap affects even the SGLD experiments, not just the SGD ones. The authors need to either tighten the group analysis or validate the per-instance prediction directly on individual points before claiming that the experiments confirm the theoretical relationship.
minor comments (6)
- [Definition 4.2] The displayed formula for ln f_{t,alpha}(g) appears to contain typesetting errors, including ambiguous placements of 'ln', 'p', and the exponents (e.g., 'e^{g^2 (k^2 - k)/(2 sigma^2)}'), which make the definition hard to parse; the authors should restate it carefully and define every symbol, including P_{x*}(1) and o_i^p(alpha).
- [Corollary 4.1] The notation in Corollary 4.1 uses both epsilon_alpha and epsilon'_alpha, but the bound's first term involves epsilon'_{4alpha} while the proof in Appendix A.1 uses epsilon'_{4alpha} and epsilon_{4alpha-1}; the authors should verify that all indices are consistent and clarify whether the asymmetry of the Renyi divergence requires the max in the definition of epsilon_alpha.
- [Section 6.1 and Figure 1] The phrase '5% error margin relative to the oracle' is used across UA, MIA, and GUS without specifying the metric in each panel; the authors should define a single normalized margin or state per-metric thresholds to make the unlearning-time comparisons reproducible.
- [Figure 1 (right) and Section 6.2] The loss-barrier results report no error bars or variance across the 10 runs mentioned in Section 5.1; adding confidence intervals would help assess whether the observed barrier differences are stable.
- [Appendix D versus Section 5.1] The main text says forget sets are formed by taking 'evenly spaced sequences of 1000 data points,' while Appendix D describes quartile-based intervals around Q1, Q2, and Q3; these two descriptions should be reconciled.
- [Section 5.3] The single-trajectory variant of EL2N differs from the original multi-trajectory definition in Paul et al. (2021); the authors should explicitly note this change when comparing correlations, so that readers do not infer that the original EL2N score was evaluated.
Circularity Check
No significant circularity: the unlearning bound derives from external DP composition and Langevin convergence theorems, and the empirical ranking is measured independently of privacy-loss computation.
full rationale
The derivation chain is self-contained with respect to external results. Corollary 4.4 is obtained by substituting Theorem 4.3 (per-instance privacy loss bound from Thudi et al., a peer-reviewed external result) into Corollary 4.1 (Langevin unlearning convergence from Chien et al., also external), using the weak triangle inequality from Mironov. None of these inputs contains the target conclusion; in particular, Theorem 4.3 is a DP composition theorem whose assumptions do not include the unlearning step bound. The empirical claim that per-instance privacy losses rank unlearning difficulty is not circular: privacy losses are computed from training-time gradients before unlearning, while 'time to unlearn' is independently measured as the number of fine-tuning steps needed to reach a 5% margin of the oracle's UA/MIA/GUS metrics. There is no equation in the paper forcing this empirical monotonicity; it is a genuine correlation. The SGD experiments rely on an assumed implicit noise level (sigma <= 0.1), which is a stated limitation and an open theoretical problem, but the reported stability of privacy-loss rankings across sigma values indicates the qualitative ordering is not merely an artifact of a post hoc fit. The group-level validation versus per-instance theory, and the admitted looseness of group bounds in Section 4.3, are correctness and scope concerns rather than circularity. Self-citations to Thudi et al. are load-bearing only as external published theorems, which counts as independent support under the stated criteria. No step reduces, by construction, to its own inputs.
Assumptions & free parameters
free parameters (3)
- Renyi order alpha for ranking =
not stated (alpha=8 used for group analysis in Appendix B)
- composition parameter p =
p = 3T
- implicit noise scale sigma for SGD =
sigma <= 0.1 (stability checked for 0.0001 to 0.01)
assumptions (5)
- domain assumption Loss is Lipschitz continuous and smooth; step sizes set according to Chien et al. (2024, Thm 3.2)
- domain assumption Markov chain converges exponentially to a stationary distribution with rate C (mixing assumption)
- standard math Weak triangle inequality for Renyi divergences (Mironov 2017)
- standard math Thudi et al. (2024) Theorems 3.2 and 3.3: per-step divergence bound and per-instance moment composition
- ad hoc to paper SGD is equivalent to SGLD with small implicit noise sigma <= 0.1
invented entities (1)
-
Implicit Gaussian noise in SGD training
Cite this review
Pith. "Pith review of Leveraging Per-Instance Privacy for Machine Unlearning." pith.science (2026). https://pith.science/paper/AILU76OX
@misc{pith2026250518786,
author = {Pith},
title = {Pith review of: Leveraging Per-Instance Privacy for Machine Unlearning},
year = {2026},
howpublished = {\url{https://pith.science/paper/AILU76OX}},
note = {Machine review of arXiv:2505.18786}
}
read the original 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 tradeoff by replacing worst-case privacy loss bounds with per-instance privacy losses (Thudi et al., 2024), each of which bounds the (Renyi) divergence to retraining without an individual data point. 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.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[3]
URL https: //openreview.net/forum?id=3LKuC8rbyV. 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 do what you think: Lessons for generative AI policy, research, and practice. arXiv:2412.06966,
-
[4]
We compared our estimates of the group privacy guarantees (y-axis) across forget sets determined by rankings of privacy losses (x-axis), and found the group privacy guarantees did not change. This was despite these forget sets leading to consistent differences in the number of steps to unlearn. We report the mean over 20 estimates of the group privacy val...
work page 2024
-
[5]
An image is worth 16x16 words: Trans- formers for image recognition at scale
9 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,
arXiv 2010
-
[6]
Unlearning time for forget sets with different privacy loss values using the L1-sparse method. Time is measured by the number of steps required for the unlearning method to reach a 5% margin of 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 be difficul...
work page 2024
-
[7]
SGD unlearning. Unlearning time vs. privacy score for ResNet-18 on SVHN (left) and ViT-small on CIFAR-10 (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 inferenc...
work page 2024
-
[8]
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.01218,
-
[10]
Kwok, D., Anand, N., Frankle, J., Dziugaite, G. K., and Rolnick, D. Dataset difficulty and the role of inductive bias. arXiv:2401.01867,
-
[11]
Threats, Attacks, and Defenses in Machine Unlearning: A Survey
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 can simplify machine unlearning. Advances in Neural Information Processing Systems, 36, 2024a. Liu, Z., Ye, H., Chen, C., Zheng, Y ., and Lam, K.-Y . Threats, attacks, and defenses in machine unlearning: A sur...
Show all 23 references
-
[12]
URL https: //proceedings.neurips.cc/paper/2019/hash/ 05e97c207235d63ceb1db43c60db7bbb-Abstract. html. See Appendix B, Flat minima. Neel, S., Roth, A., and Sharifi-Malvajerdi, S. Descent-to- delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, ...
2019
-
[14]
Z., Lu, Y ., Kamath, G., Sekhari, A., and Neel, S
Pawelczyk, M., Di, J. Z., Lu, Y ., Kamath, G., Sekhari, A., and Neel, S. Machine unlearning fails to remove data poisoning attacks. arXiv:2406.17216,
-
[15]
URL https://doi.org/10.1007/978-3-031-70368-3
-
[16]
URL https://openreview.net/forum?id=l4Jcxs0fpC
ISSN 2835-8856. URL https://openreview.net/forum?id=l4Jcxs0fpC. Zhao, K. and Triantafillou, P. Scalability of memorization- based machine unlearning. arXiv:2410.16516,
-
[18]
The x-axis represents the number of epochs
Unlearning results for accuracy metrics (top) and MIA success rate (bottom). The x-axis represents the number of epochs. In each plot, lines of different colors represent forget sets of varying difficulty, while the dashed line indicates the oracle’s performance. ln Gt,α(D, D′...
2024
-
[19]
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 ...
2024
-
[20]
We report the mean over 20 estimates (given the stochasticity in our estimates for the per-step terms ln Gt,α(D, D′, w)) and shaded in one standard deviation
In Figure 4 we took checkpoints from an SGD training run on CIFAR10 with ResNet18, and used σ = 0.1, and took α = 8 to compute the group privacy scores. We report the mean over 20 estimates (given the stochasticity in our estimates for the per-step terms ln Gt,α(D, D′, w)) and...
2021
-
[23]
Unlearning time is reported as the number of training steps required to achieve a UA error within 5%
Unlearning time for forget sets of size 100 (left), 5,000 (middle), and 10,000 (right), evaluated on CIFAR-10. Unlearning time is reported as the number of training steps required to achieve a UA error within 5%. F.3. Additional datasets/architectures In addition to ResNet-18 ...
-
[2009]
Baluta, T., Lamblin, P., Tarlow, D., Pedregosa, F., and Dziu- gaite, G
URL https://www.cs.toronto.edu/ kriz/learning-features-2009-TR.pdf . Baluta, T., Lamblin, P., Tarlow, D., Pedregosa, F., and Dziu- gaite, G. K. Unlearning in-vs. out-of-distribution data in LLMs under gradient-based method. arXiv:2411.04388,
2009 arXiv
-
[2019]
Towards adversarial evaluations for inex- act machine unlearning
Goel, S., Prabhu, A., Sanyal, A., Lim, S.-N., Torr, P., and Kumaraguru, P. Towards adversarial evaluations for inex- act machine unlearning. arXiv:2201.06640,
-
[2020]
and Roger, F
Deeb, A. and Roger, F. Do unlearning methods remove infor- mation from language model weights? arXiv:2410.08827,
-
[2021]
Y ., et al
Netzer, Y ., Wang, T., Coates, A., Bissacco, A., Wu, B., Ng, A. Y ., et al. Reading digits in natural images with unsupervised feature learning. In 2011 NIPS Workshop on Deep Learning and Unsupervised Feature Learning,
2011
-
[2022]
Fan, C., Liu, J., Zhang, Y ., Wong, E., Wei, D., and Liu, S
URL https: //openreview.net/forum?id=dNigytemkL. 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. arXiv:2310.12508,
-
[2023]
Jiang, Z., Zhang, C., Talwar, K., and Mozer, M
URL https://openreview.net/ forum?id=0jZH883i34. 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,
2002 arXiv
-
[2024]
and Triantafillou, P
Barbulescu, G.-O. and Triantafillou, P. To each (textual se- quence) its own: Improving memorized-data unlearning in large language models. arXiv:2405.03097,
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.