📊 statistics

Towards Certified Unlearning for Deep Neural Networks

This paper proposes efficient techniques to extend certified unlearning to deep neural networks by utilizing inverse Hessian approximation and addressing nonconvergence and sequential unlearning scenarios, thereby bridging the gap between theoretical guarantees and nonconvex model applications.

Original authors: Binchi Zhang, Yushun Dong, Tianhao Wang, Jundong Li

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Binchi Zhang, Yushun Dong, Tianhao Wang, Jundong Li

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 giant, super-smart library (a Deep Neural Network) that has read millions of books (user data) to learn how to answer questions. One day, a user says, "I want to be forgotten. Please delete all the books I wrote from your library and retrain your brain so you don't remember me."

In the old days, the library's only option was to burn the whole library down and rebuild it from scratch using only the remaining books. This is called "retraining." It's accurate, but it takes years and costs a fortune.

This paper introduces a new, magical technique called "Certified Unlearning." It's like a high-tech eraser that can surgically remove a specific user's influence from the library's brain without rebuilding the whole thing, while also providing a guarantee (a certificate) that the user is truly gone.

Here is how the authors made this magic work for complex, messy systems like Deep Neural Networks:

1. The Problem: The "Non-Convex" Maze

Most previous "erasers" worked well on simple, smooth hills (convex models). But Deep Neural Networks are like complex, multi-layered mazes with dead ends and hidden valleys (non-convex).

The Challenge: If you try to use a simple eraser on a maze, you might accidentally erase the wrong path or get stuck. Previous methods either didn't work well in these mazes or couldn't prove they actually removed the user's data.

2. The Solution: Two Simple Tricks

The authors proposed two clever tricks to make the eraser work in the maze:

Trick A: The "Local Map" (Local Convex Approximation)
Imagine you are in a dark, twisting maze. You can't see the whole map, but if you look at just the small patch of floor right under your feet, it looks flat and simple.
The authors pretend the complex maze is flat right where the model is currently standing. They add a little "stabilizer" (mathematically, a regularization term) to make that small patch behave like a smooth hill. This allows them to use the simple eraser safely, even though the rest of the maze is chaotic.
Trick B: The "Guess-and-Check" Shortcut (Inverse Hessian Approximation)
To erase a user, you usually need to calculate a massive, complex equation (the Hessian matrix) that involves every single book in the library. Doing this exactly is like trying to count every grain of sand on a beach.
Instead, the authors use a smart sampling trick (LiSSA). Imagine you want to know the average weight of all the books. Instead of weighing every single one, you grab a random handful, weigh them, and use a clever formula to estimate the total weight. This is thousands of times faster and still accurate enough for the job.

3. The "Certificate": Adding a Little Noise

How do we know the user is really gone? The authors use a concept from "Differential Privacy."

The Analogy: Imagine you have a photo of the library after you removed the user's books. To make it 100% impossible to tell if the user's books were ever there, you add a tiny bit of static noise (like snow on an old TV) to the photo.
The math proves that if you add the right amount of noise (based on how much the model changed), no one can tell the difference between the "erased" model and a model that was retrained from scratch. This noise is the "Certificate."

4. Real-World Flexibility

The paper also tackles two tricky real-life scenarios:

The "Early Stop" Problem: Sometimes, the library stops studying before it's perfect (non-convergence). The authors showed their method still works even if the model isn't at its "perfect" state.
The "Chain Reaction" (Sequential Unlearning): What if User A asks to be forgotten, and then User B asks to be forgotten? You can't just go back to the original library; you have to erase User B from the already-erased library. The authors proved their method works in this chain reaction without the errors piling up.

5. The Results: Fast and Safe

The authors tested this on three famous datasets (MNIST, CIFAR-10, SVHN) using different types of neural networks.

Speed: Their method was 10 times faster than rebuilding the model from scratch.
Privacy: They used "Membership Inference Attacks" (hackers trying to guess if a specific person's data was in the model). Their method made the hackers fail almost as often as they would if the model had been rebuilt from scratch.
Quality: The model stayed smart enough to answer questions correctly, even after the "surgery."

Summary

Think of this paper as inventing a surgical laser for AI. Instead of amputating the whole limb (retraining) to remove a splinter (a user's data), they developed a way to precisely zap the splinter out, add a little bandage (noise) to hide the scar, and provide a doctor's note (certificate) proving the patient is safe. This makes the "Right to be Forgotten" actually possible for the massive, complex AI systems we use every day.

1. Problem Statement

Machine Unlearning refers to the process of removing the influence of specific training data (unlearned set $D_u$ ) from a trained model without retraining from scratch. While Certified Unlearning has been successfully applied to convex models (e.g., linear models, SVMs) with strong theoretical guarantees, its application to Deep Neural Networks (DNNs) remains challenging due to:

Non-convexity: DNNs have highly non-convex loss landscapes, making standard Newton-based approximation methods (relying on convexity assumptions) theoretically invalid.
Computational Cost: Exact unlearning via retraining is prohibitively expensive for large-scale DNNs.
Real-world Complexity: Existing methods often fail to account for non-convergent training (e.g., early stopping) or sequential unlearning requests (multiple users requesting deletion over time).

The core problem is to develop a method that provides theoretical certification (guaranteeing the unlearned model is statistically indistinguishable from a retrained model) for DNNs while maintaining computational efficiency.

2. Methodology

The authors propose a framework that extends certified unlearning to non-convex objectives through three main technical pillars:

A. Theoretical Foundation: Bounding Approximation Error

The method relies on Theorem 2.3, which states that if an approximation $\tilde{w}$ of the retrained model $\tilde{w}^*$ has a bounded error $\Delta = \|\tilde{w} - \tilde{w}^*\|_2$ , adding Gaussian noise $Y \sim \mathcal{N}(0, \sigma^2 I)$ with $\sigma \ge \frac{\Delta}{\epsilon}\sqrt{2\ln(1.25/\delta)}$ yields an $\epsilon-\delta$ certified unlearning process.

To achieve this for DNNs, the authors modify the standard single-step Newton update:

Local Convex Approximation: To handle non-convexity, they add an $\ell_2$ regularization term ( $\lambda$ ) to the objective function during Hessian computation. This ensures the Hessian matrix $(H_{w^*} + \lambda I)$ is positive definite, allowing for a bounded inverse.
Parameter Norm Constraints: They impose a constraint $\|w\|_2 \le C$ on the model parameters. This bounds the distance between the original model $w^*$ and the retrained model $\tilde{w}^*$ , preventing the approximation error from exploding.
Error Bound Derivation: Under these constraints, they derive a tractable upper bound for the approximation error (Equation 7 and 11) that does not rely on global convexity assumptions.

B. Computational Efficiency: Inverse Hessian Approximation

Calculating the exact inverse Hessian for DNNs is $O(p^3)$ (where $p$ is the number of parameters), which is infeasible. The authors employ:

LiSSA (Linear-time Stochastic Second-order Algorithm): An iterative estimator to approximate the inverse Hessian-vector product with complexity $O(sp^2)$ , where $s$ is the number of iterations.
Gradient Decomposition: Instead of computing the gradient over the retained set $D_r$ (which is large), they utilize the property that $\nabla L(w^*, D) = 0$ to express $\nabla L(w^*, D_r)$ in terms of the gradient over the small unlearned set $D_u$ . This reduces complexity from $O(np)$ to $O(n_u p)$ .

C. Handling Real-World Scenarios

Non-Convergence: The method is adapted for cases where training stops early (non-optimal $w^*$ ). The error bound is adjusted to include the residual gradient norm ( $G$ ), ensuring certification holds even if the model hasn't fully converged.
Sequential Unlearning: The framework supports multiple sequential deletion requests. The authors prove that the approximation error bound remains stable (and potentially decreases) as the retained set shrinks, provided the model parameters remain bounded.

3. Key Contributions

Extension to Non-Convexity: The first rigorous extension of certified unlearning to DNNs without relying on unrealistic convexity assumptions, using local convex approximation and parameter constraints.
Efficient Algorithm: Development of a computationally efficient algorithm (Algorithm 1) using LiSSA and gradient decomposition, reducing time complexity significantly compared to exact retraining.
Theoretical Guarantees for Complex Settings: Proofs that certification holds under non-convergent training and sequential unlearning scenarios, addressing practical deployment gaps.
Error Bound Analysis: A detailed analysis showing how hyperparameters (regularization $\lambda$ , norm bound $C$ ) affect the approximation error bound and the resulting noise level.

4. Experimental Results

The authors evaluated their method on MNIST, CIFAR-10, and SVHN using MLP, All-CNN, and ResNet-18 architectures.

Unlearning Efficacy (Privacy):
- Membership Inference Attacks (MIA): The certified method achieved the lowest attack success rates (Accuracy and AUC) compared to baselines (Fine-tuning, Negative Gradient, Fisher Forgetting, L-CODEC), indicating superior removal of information regarding unlearned samples.
- Relearn Time: The time required to retrain the unlearned model to a specific loss threshold was low, confirming the model "forgot" the data effectively.
Model Utility:
- The unlearned model maintained high F1-scores on the retained set and test set, comparable to the retrained-from-scratch baseline.
- Performance on the unlearned set dropped significantly (as desired), outperforming baselines that retained too much information.
Efficiency:
- The certified unlearning method was >10x faster than retraining from scratch.
- Using the inverse Hessian approximation (LiSSA) provided a 470x speedup compared to computing the exact inverse Hessian (tested on MLP/MNIST).
Ablation Studies:
- Removing the local convex approximation ( $\lambda=0$ ) or the norm constraint ( $C$ ) significantly increased the approximation error bound, validating the necessity of these techniques.
- Increasing $\lambda$ reduced the error bound but required careful tuning to avoid degrading model utility.

5. Significance

This paper bridges a critical gap between theoretical machine unlearning and practical deep learning applications.

Theoretical Rigor: It moves certified unlearning beyond convex models, providing the first theoretical guarantees for DNNs that account for non-convexity and non-convergence.
Practical Viability: By demonstrating efficiency and robustness in sequential and non-convergent settings, the work makes certified unlearning a viable solution for real-world systems complying with regulations like GDPR and CCPA.
Privacy Assurance: It offers a mathematically provable method to ensure user data is removed from DNNs, addressing the "right to be forgotten" with stronger guarantees than empirical approximations.

In summary, the proposed method achieves a balance between stringency (strong theoretical certification), efficiency (fast computation), and utility (preserving model performance), establishing a new standard for unlearning in deep learning.