The Unseen Threat: Residual Knowledge in Machine Unlearning under Perturbed Samples

AI summary

Overview

Research area: Machine learning privacy — specifically machine unlearning and its interaction with adversarial perturbations of inputs.

Technical level: Advanced. The paper combines empirical benchmarking on vision datasets with measure-theoretic and geometric probability arguments (isoperimetric inequalities on the unit sphere, $(\epsilon,\delta)$-indistinguishability, Rényi divergences).

Scope: The paper identifies and formalizes a previously unreported privacy risk — "residual knowledge" — in which an unlearned model retains predictive traces of forget samples in their local perturbation neighborhoods, proves this disagreement is inevitable in high dimensions, and proposes a fine-tuning mitigation called RURK.

What This Paper Is About

Machine unlearning lets a model provider approximately remove the influence of specific user data without retraining from scratch, and existing guarantees certify that the unlearned model is statistically indistinguishable from a freshly retrained one. This paper shows that those guarantees only cover the original samples: when a forget sample is slightly and imperceptibly perturbed, the unlearned model can still classify it correctly while the retrained model fails — meaning information about the "forgotten" sample survives in its neighborhood. The authors formalize this as residual knowledge, prove it is unavoidable in high-dimensional input spaces even under certified unlearning, and introduce RURK, a fine-tuning objective that penalizes the model for re-recognizing perturbed forget samples.

Key Contributions

1. Formalizing residual knowledge. The authors define residual knowledge as the ratio $r_\tau((\mathbf{x},y)) \triangleq \Pr[m(\mathbf{x}')=y] / \Pr[a(\mathbf{x}')=y]$ for independently sampled unlearned ($m$) and retrained ($a$) models with $\mathbf{x}'$ drawn i.i.d. from the ball $\mathcal{B}_p(\mathbf{x},\tau)$, extended to the whole forget set by averaging. Values above 1 indicate the unlearned model recognizes perturbed forget samples more often than the retrained model does.

2. Proving that adversarial distinguishability and disagreement are inevitable. Proposition 1 shows adversarial examples drawn against unlearned or retrained models become less indistinguishable than the models themselves, with probability $2\delta/(1-e^{-\epsilon})$ (distinguishability increases by a factor of two). Proposition 2 uses the isoperimetric inequality to show that disagreement on perturbed inputs is inevitable on the unit sphere for any $(\epsilon,\delta)$-unlearning, for both $p=2$ and $p=\infty$.

3. The RURK fine-tuning strategy. RURK adds a regularization term that penalizes the loss on "vulnerable perturbations" — perturbed samples inside $\mathcal{B}_p(\mathbf{x},\tau)$ that the unlearned model still labels correctly — while preserving accuracy on the retain set.

4. Empirical validation across unlearning algorithms and benchmarks. Experiments on small CIFAR-5, full CIFAR-10, and ImageNet-100 with deep networks show residual knowledge is prevalent across existing unlearning methods and that RURK effectively prevents it.

Main Findings

• Residual knowledge is prevalent in existing methods. On CIFAR-10, with a perturbation norm of approximately 0.03, over 7% of forget samples still exhibit residual knowledge (reported from Appendix C.4).

• Certified unlearning does not protect perturbed inputs. Even when unlearned and retrained models satisfy $(\epsilon,\delta)$-indistinguishability — and even when they agree on the original forget sample — adversarial examples can separate them. The paper notes this is related to adversarial example transferability, an area largely unexplored in the unlearning literature.

• Disagreement probability depends on perturbation size. In Proposition 2, the disagreement probability is at least $\left(\frac{2\delta}{1-e^{-\epsilon}}\right)\left{1-\mathcal{O}\left[\left(\frac{\pi}{8}\right)^{1/2}\exp\left(-2\epsilon-\frac{d-1}{2}\tau^{2}\right)\right]\right}$; for any fixed $(\epsilon,\delta)$ it depends only on the perturbation norm $\tau$, and increases as $\tau$ grows.

• Edge cases of the bound behave as expected. When $\epsilon=\delta=0$ (exact unlearning), the probability in Eq. (3) is zero, since identical models cannot disagree. As $\epsilon\to\infty$ for fixed $\delta$, the probability approaches its upper bound of $2\delta$. The condition underlying Proposition 2 — that the agreement region occupies at most half the surface area — is easily satisfied in multi-class settings where $|\mathcal{Y}|>2$.

• Residual knowledge bounds adversarial disagreement. Lemma A.4 gives both an upper and lower bound linking $r_\tau$ to the expected adversarial disagreement $\mathbb{E}[k_\tau(\mathbf{x}')]$; as $r_\tau((\mathbf{x},y)) \to 1$, that expected disagreement approaches zero, making residual knowledge a tractable proxy.

• Noise-tolerant model weights are not the answer. The background notes that a simple approach adds Gaussian noise $\mathbf{w}+\sigma\mathbf{n}$ to weights, but as $\sigma$ increases the model becomes increasingly independent of training data and performance can degrade.

• A trade-off exists between indistinguishability and robustness. When the RURK objective is optimized with (Projected) Noisy Gradient Descent (NGD), the result satisfies $(\alpha,\epsilon)$-Rényi unlearning, where $\epsilon$ depends on smoothness and Lipschitz continuity of the loss. Increasing $\tau$ in RURK's regularization term enlarges the adversarial perturbation space, making the adversarial loss less smooth with a larger Lipschitz constant, which ultimately increases $\epsilon$.

• RURK reduces to prior objectives in the limit. As $\tau \to 0$, the RURK objective reduces to objectives used in prior work such as Neel et al. (2021) and Chien et al. (2024).

• Evaluation scope. Three random sample-unlearning scenarios are used: small CIFAR-5 (200 training and 200 test images per class from the first five classes of CIFAR-10, ResNet-18), full CIFAR-10 (ResNet-18), and ImageNet-100 (a 100-class subset of ImageNet-1k with 1,300 images per class, ResNet-50). In all cases only 50% of class 0 is unlearned. Baseline algorithms are {CR, Fisher, NTK} for small CIFAR-5 and {GD, NGD, GA, NegGrad+, EU-k, CF-k, SCRUB, SSD} for full CIFAR-10. Specific numerical results for ImageNet-100 and the full baseline comparison table are not included in the provided content.

Methodology in Plain English

The authors start from a simple observation: two models can be statistically similar in aggregate and still disagree on individual inputs. They define "disagreement" as a yes/no indicator that the unlearned and retrained models predict differently at a point.

They then ask what happens in a small neighborhood around a data point. Using an isoperimetric inequality — a classical geometric result stating that in high dimensions, a small set must have a relatively large boundary — they argue that if two models disagree on even a small region, small perturbations will spread that disagreement over a much larger region. They work on the unit sphere (with data normalized to unit norm) and show the disagreement probability is bounded below by an expression that grows with the perturbation radius. They note this assumption is admittedly strong but that the same principle generalizes to the unit cube (Ledoux, 2001, Proposition 2.8), which better matches normalized image pixels.

To make this measurable, they single out the most concerning case: a perturbed forget sample that the unlearned model still labels correctly but the retrained model does not. They call the ratio of these two success probabilities "residual knowledge" and estimate it by Monte Carlo sampling — drawing $c$ samples inside the perturbation ball and comparing how many each model classifies correctly.

For mitigation, they fine-tune with two terms: a standard loss on the retain set to preserve utility, minus a weighted term that actively penalizes the model's confidence on vulnerable perturbations found near forget samples (found via FGSM, PGD, or similar methods). In practice, they can simplify by treating the whole perturbation ball as the vulnerable set.

Empirically, they compare an "Original" model trained on everything, a "Re-train" model trained from scratch without the forget set (used only as a reference since it is not viable in practice), and several unlearning algorithms, then check whether RURK closes the gap.

Why This Matters

Impact on research. The paper challenges the completeness of certified unlearning: satisfying $(\epsilon,\delta)$-unlearning or $(\alpha,\epsilon)$-Rényi unlearning does not imply that forget samples are unrecoverable from their local neighborhoods. It introduces a new evaluation axis — robustness of unlearning under perturbed inputs — and shows the two goals can be in tension. To the authors' knowledge, this is the first work to uncover this privacy risk and provide a scalable solution.

Real-world applications:

• Regulatory compliance. The EU's GDPR "Right to be Forgotten" requires removing user data from models, not just databases. Residual knowledge means a deletion request could be nominally honored while traces remain extractable through perturbation, creating legal exposure.
• Deployed recommendation and personalization models. Where user data must be removed on request, local residuals could allow inferences about removed users.
• Model providers offering unlearning as a service. Certification claims based on indistinguishability would need to be extended to neighborhood behavior.
• Auditing and red-teaming. Residual knowledge provides a concrete, computable metric that auditors can use to test whether an unlearning claim holds up.

Industry relevance. All six authors are affiliated with JPMorganChase (Global Technology Applied Research and AI Research). Financial services firms face deletion requests, model governance requirements, and regulatory scrutiny, and the computational cost of full retraining — noted by the paper as impractical in real-time or large-scale settings — makes approximate unlearning attractive. At the same time, the paper's results cut against relying on approximate guarantees alone.

Future Directions

• Reconciling the robustness–indistinguishability trade-off. The paper itself identifies that enlarging $\tau$ in RURK's regularization term increases the effective $\epsilon$ of the resulting $(\alpha,\epsilon)$-Rényi unlearning guarantee. Finding ways to gain robustness without weakening the certification remains open.
• Relaxing the geometric assumptions. Proposition 2 assumes data on the unit sphere; the authors point to Ledoux (2001, Proposition 2.8) as generalizing the isoperimetric property to the unit cube and suggest that establishing the result under looser conditions is a natural extension.
• Reducing the cost of finding vulnerable perturbations. Explicitly searching for the set $\mathcal{V}((\mathbf{x},y),\tau)$ at each gradient step is computationally expensive; the paper proposes the approximation $\mathcal{V}((\mathbf{x},y),\tau)=\mathcal{B}_p(\mathbf{x},\tau)$ as a cheaper alternative, leaving room for more efficient strategies.
• Extending beyond image classifiers. The empirical study covers vision benchmarks with ResNet and VGG architectures. Whether residual knowledge and RURK transfer to language models, image generators, and other model classes discussed in the related work is not addressed in the provided content. The paper concludes with a discussion of limitations and future research directions in Section 6, whose details are not included in the truncated text.

Target Audience

This paper is best suited for machine learning privacy researchers, particularly those working on machine unlearning, certified removal, and membership inference; adversarial robustness researchers interested in the intersection with privacy; and practitioners in regulated industries — financial services, healthcare, and any sector handling deletion requests — who need to understand the limits of approximate unlearning guarantees. It will also interest auditors and compliance teams evaluating whether an unlearning claim is genuinely sufficient. Readers should be comfortable with probability theory, $\ell_p$ norms, differential privacy-style definitions, and empirical benchmarking of deep networks.

Authors’ abstract

Machine unlearning offers a practical alternative to avoid full model re-training by approximately removing the influence of specific user data. While existing methods certify unlearning via statistical indistinguishability from re-trained models, these guarantees do not naturally extend to model outputs when inputs are adversarially perturbed. In particular, slight perturbations of forget samples may still be correctly recognized by the unlearned model - even when a re-trained model fails to do so - revealing a novel privacy risk: information about the forget samples may persist in their local neighborhood. In this work, we formalize this vulnerability as residual knowledge and show that it is inevitable in high-dimensional settings. To mitigate this risk, we propose a fine-tuning strategy, named RURK, that penalizes the model's ability to re-recognize perturbed forget samples. Experiments on vision benchmarks with deep neural networks demonstrate that residual knowledge is prevalent across existing unlearning methods and that our approach effectively prevents residual knowledge.