🤖 machine learning

Exact Unlearning from Proxies Induces Closeness Guarantees on Approximate Unlearning

This paper proposes a novel machine unlearning framework that shifts focus from parameter updates to precise data distribution inference, theoretically guaranteeing and empirically demonstrating that the resulting model closely approximates the ideal retrained model.

Original authors: Virgile Dine, Teddy Furon

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Virgile Dine, Teddy Furon

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart student (a neural network) who has studied a massive library of books (training data) to become an expert. Suddenly, a law says, "You must forget everything you learned from these specific 10 books."

Usually, to forget, the student has to close the library, throw away those 10 books, and re-study the entire library from scratch. This is slow, expensive, and wasteful.

Current "approximate" methods try to be clever shortcuts. They tell the student: "Just un-learn those specific books!" But they do this by guessing and tweaking the student's brain a little bit at a time. Often, they get confused, forget too much (or too little), and nobody really knows if the student has truly forgotten or is just pretending.

This paper proposes a completely different way to think about forgetting.

The Core Idea: The "Map" vs. The "Brain"

The authors argue that instead of just tweaking the student's brain (the neural network parameters), we should look at the map of the library (the data distribution).

The Problem with Current Methods: Imagine trying to erase a stain from a complex painting by just scrubbing the canvas. You might miss the stain or ruin the whole picture. Current methods are like that scrubbing—they are messy, iterative, and lack a clear "stop" signal.
The New Approach: Instead of scrubbing, the authors say: "Let's build a perfect, mathematical map of what the library looked like before the 10 books were added, and what it looks like after."

How It Works: The "Proxy" Analogy

The paper introduces a concept called Proxies. Think of a proxy as a simplified, mathematical sketch of the data.

Step 1: Draw the Maps. The authors create two mathematical sketches (proxies):
- Map A: A sketch of the entire library (including the books to be forgotten).
- Map B: A sketch of the library without the books to be forgotten.
Step 2: Find the Difference. They calculate the exact difference between Map A and Map B. This difference is the "Unlearning Signal." It's a precise instruction on exactly how the student's knowledge needs to shift to remove the influence of those 10 books.
Step 3: The "Distillation" (The Transfer). Now, they take the original student (the neural network) and use a technique called distillation. Imagine a teacher (the mathematical map) guiding the student to adjust their answers to match the "Map B" version. The student doesn't need to re-learn the whole library; they just need to shift their understanding based on the precise difference the map calculated.

The "Double Label" Trick

One of the paper's cleverest tricks is called **"Doubling the Labels."

Imagine the library has a section for "Animals." Inside, there are dogs and cats. If you want to forget the "dogs," but the student has learned that dogs and cats look very similar, it's hard to just delete "dogs" without messing up "cats."

The authors' method creates a new, expanded map where every book is labeled not just by its category (e.g., "Dog"), but also by its status (e.g., "Dog-Retain" or "Dog-Forget"). By treating "Dog-Retain" and "Dog-Forget" as two completely different categories in their mathematical map, they can precisely calculate how to remove the "Forget" part while keeping the "Retain" part perfectly intact. It's like having a special highlighter that only removes the "Forget" ink without smudging the "Retain" ink.

Why This is Better (The Results)

The paper claims this method is superior for three main reasons:

It's a Shortcut to the "Gold Standard": The "Gold Standard" is retraining the student from scratch. The authors prove mathematically that their method gets much closer to this perfect "retrained" student than other shortcut methods do.
No More Guessing: Because they use mathematical maps, they can calculate a "safe zone" for how much to change the student's brain. They don't have to guess when to stop; the math tells them exactly when the job is done.
It Works on "Subclasses": This is the hardest scenario. If you want to forget "Golden Retrievers" but keep "Labradors" (both are dogs), most methods fail and either forget all dogs or none. This method, using the "Double Label" trick, successfully forgets just the Golden Retrievers while keeping the Labradors safe.

The Bottom Line

Instead of blindly scrubbing a neural network to make it forget, this paper suggests building a precise mathematical blueprint of what the data looks like with and without the unwanted information. By calculating the exact difference between these blueprints, they can guide the neural network to "unlearn" with surgical precision, achieving results that are nearly as good as starting over, but in a fraction of the time.

They call this "Exact Unlearning from Proxies," and their experiments show it consistently outperforms the current state-of-the-art methods, especially in tricky situations where the data to be forgotten is mixed closely with the data to be kept.

Technical Summary: Exact Unlearning from Proxies Induces Closeness Guarantees on Approximate Unlearning

Problem Statement

Machine unlearning aims to remove the influence of specific training data (the "forget set," $D_f$ ) from a trained classifier without retraining the model from scratch on the remaining data (the "retain set," $D_r$ ). While exact unlearning is the gold standard, it is often computationally prohibitive for large deep networks. Current approximate methods, primarily based on first-order gradient updates (e.g., gradient ascent on the forget set), suffer from several limitations:

Lack of Interpretability: They rely on optimization trajectories that do not offer a closed-form characterization of the resulting predictive shift in terms of data distributions.
Instability: Iterative updates often lack clear stopping criteria, leading to over-unlearning or catastrophic forgetting.
Evaluation Gaps: Performance is frequently gauged by membership inference attacks (MIAs) or accuracy metrics, which may not accurately reflect the statistical distance to the ideal retrained model.
Sub-optimality: Existing theoretical bounds often depend on neural network properties (e.g., Hessian approximations) rather than the quality of the underlying data distribution models.

Methodology

The paper proposes a paradigm shift: instead of directly updating network weights via gradients, the authors model the exact unlearning signal as a shift in the logit space derived from explicit mathematical models of the data distributions.

1. The Unlearning Signal as a Logit Shift

The core idea is to define the unlearning target not by an optimization path, but by the difference between the posterior distributions of the retain set and the original dataset.

Let $P$ be the true distribution of the original data and $P_r$ be the true distribution of the retain set.
The authors introduce parametric proxies ( $\bar{P}$ and $\bar{P}_r$ ) to model the class-conditional distributions $P(X|Y)$ and $P_r(X|Y)$ .
These proxies induce posterior distributions and associated logit vectors $M(x)$ and $M_r(x)$ .
The unlearning signal is defined as the shift $\Delta M(x) = M_r(x) - M(x)$ .
The unlearned model logits are constructed as a linear combination: $\tilde{f}_\eta(x) = f_\theta(x) + \eta \Delta M(x)$ , where $\eta$ is a scaling factor.

2. Theoretical Framework and Guarantees

The paper establishes theoretical bounds on the Kullback-Leibler (KL) divergence between the unlearned model and the ideal retrained model ( $P_r$ ).

Admissibility Criterion: A pair of proxies is "admissible" if the initial proxy $\bar{P}$ is a better approximation of the true distribution $P$ than the retain proxy $\bar{P}_r$ is of $P_r$ . This is a verifiable condition.
Safety Regime ( $\eta_{max}$ ): The authors prove the existence of a maximum scaling factor $\eta_{max}$ such that for any $\eta \in [0, \eta_{max}]$ , the unlearning process strictly decreases the KL divergence to the ideal model, provided the admissibility criterion holds.
Bounds: Proposition 1 provides a tight bound on the KL divergence, showing that the error depends on the initial divergence and the "modeling shift" (the difference in how well the proxies model their respective targets). Proposition 2 offers an intuitive bound linking the error to the quality of the class-conditional modeling.

3. Proxy Construction

The paper explores several families of proxies to approximate the data structure:

Naive Models: Standard LDA (Linear Discriminant Analysis) and QDA (Quadratic Discriminant Analysis) treating the whole dataset as a single distribution per class.
Mixture Models (LDA-Mix, QDA-Mix): Modeling the original distribution as a mixture of retain and forget sub-populations within each class.
Label Doubling (LDA-2C, DIR-2C): A novel approach where the label space is doubled to $(y, s)$ $(y, s)$ , where $s \in \{retain, forget\}$ $s \in {r e t ain, f or g e t}$ . This allows the model to intrinsically capture the overlap between retain and forget distributions and estimate the probability of a sample belonging to the forget set.
- DIR-2C: Uses empirical Dirac distributions on the doubled label space. While the direct application is aggressive, it serves as a powerful "teacher" for the distillation step.

4. Implementation via Distillation

The constructed logit shift $\eta_{max} \Delta M(x)$ is implemented in the neural network via Knowledge Distillation. The original network $f_\theta$ acts as a student, trained to minimize the KL divergence between its output and the target logits $\tilde{f}_{\eta_{max}}$ . This step translates the closed-form distributional correction into network parameters.

Key Contributions

Exact Unlearning Signal via Proxies: The paper introduces a closed-form, interpretable unlearning signal derived from explicit mathematical models of data distributions, rather than gradient trajectories.
Theoretical Guarantees: It provides verifiable admissibility criteria and tight theoretical bounds on the KL divergence to the ideal retrained model, linking unlearning performance directly to the quality of the data proxies.
Fine-Grained Proxies: It proposes specific modeling techniques (Mixture models and Label Doubling) that learn membership dependencies from data structure. Notably, LDA-2C and DIR-2C emerge as effective methods for capturing intra-class structure.
Stein Bound for Evaluation: The paper proposes using the KL divergence to derive a "Stein bound" on the number of queries an attacker needs to distinguish the unlearned model from the retrained model, offering a more stable and interpretable alternative to empirical Membership Inference Attacks.

Experimental Results

The method was evaluated on CIFAR-10 and CIFAR-100 across three forgetting scenarios:

Random: Forgetting random samples.
Class: Forgetting an entire class.
Subclass: Forgetting a subset of a class (e.g., "airplanes" within "vehicles"), which is noted as the most challenging and realistic scenario where gradient ascent baselines often fail.

Findings:

Proximity to Ideal: The proposed methods (specifically LDA-2C and DIR-2C) consistently produced unlearned models closest to the ideal retrained model ( $p_{\theta_r}$ ) in terms of KL divergence ( $KL_t$ and $KL_f$ ), outperforming state-of-the-art baselines like SCRUB, SalUn, and GA+FT.
Stability: Unlike iterative baselines which showed unstable trajectories or catastrophic forgetting (e.g., SalUn reducing forget accuracy to near zero), the proposed method converged quickly and stably.
Efficiency: The methods achieved these results with a runtime efficiency (RTE) of approximately 5% of the time required for full retraining.
Proxy Effectiveness: The "Label Doubling" proxies (LDA-2C, DIR-2C) generally outperformed standard mixture models, particularly in the Subclass scenario, by better capturing the distributional overlap between retain and forget sets.

Significance and Claims

The paper claims that its framework offers a paradigm shift by grounding machine unlearning in the structure of data distributions rather than neural network parameter updates.

Soundness: The theoretical bounds demonstrate that if the proxies are sufficiently accurate (verifiable via the admissibility criterion), the unlearning process is guaranteed to move the model closer to the ideal retrained state.
Interpretability: The method provides a closed-form decomposition of the unlearning error, moving away from the "black box" nature of iterative gradient updates.
Practicality: By using distillation, the method can be applied to black-box networks that output logits, making it versatile.
Limitations: The authors modestly acknowledge limitations, including the assumption that the retain set $D_r$ is available to fit the proxy $P_r$ , potential ill-conditioning in high-dimensional feature spaces (mitigated by dimensionality reduction), and the fact that the admissibility criterion is checked empirically on the initial model rather than the true distribution.

In summary, the paper argues that by modeling the data distribution explicitly, one can derive an exact unlearning signal that, when distilled into a network, yields a model statistically indistinguishable from one retrained from scratch, with provable guarantees and superior empirical performance.