🤖 machine learning

The Forgetting-Retention Dilemma: Certified Unlearning Theory in Continual Learning

This paper establishes the first theoretical foundation bridging continual learning and machine unlearning by formulating a trade-off between preserving historical knowledge and targeted forgetting, deriving risk bounds for non-convex models, and proposing a hybrid strategy that balances storage efficiency with unlearning performance.

Original authors: Yiting Hu, Lingjie Duan, Qian Zhang

Published 2026-06-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yiting Hu, Lingjie Duan, Qian Zhang

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 are a master chef running a restaurant that never closes. Every day, you learn a new recipe (a Continual Learning task). Over time, your kitchen becomes a treasure trove of thousands of dishes.

But here's the catch: sometimes, a customer says, "I want to forget that I ever ordered the spicy tuna roll." They have a legal right to be forgotten. You need to remove the influence of that specific dish from your memory so that if they come back, you don't accidentally serve them a variation of it, or worse, reveal that you know they ordered it.

This is the Machine Unlearning problem.

The paper tackles a very tricky scenario: What happens when you have to forget a dish from last month while you are currently learning today's special? And what if you can't keep a physical copy of every recipe book you've ever written (because of storage limits or privacy laws)?

Here is the breakdown of the paper's solution, using simple analogies:

1. The Core Dilemma: "The Sticky Note vs. The Eraser"

In a normal kitchen, if you want to forget a recipe, you might just burn the page. But in this "Continual Learning" kitchen, the recipes are all mixed together in your brain. If you try to erase the "Spicy Tuna" recipe, you might accidentally erase the "Sushi Rice" recipe too, or ruin your ability to make "Tempura" because the ingredients are so intertwined.

The authors call this the Forgetting-Retention Dilemma:

Retention: You want to keep all your old skills (making Tempura) perfect.
Forgetting: You want to surgically remove one specific skill (Spicy Tuna) without damaging the rest.

The paper proves that these two goals often fight against each other. The more you try to hold onto your old skills, the harder it is to cleanly erase the new "forbidden" data.

2. The Three Approaches Tested

The researchers tested three different ways to handle this "forgetting" request:

A. The "Natural Fade" Method (Gradient-Based)

The Analogy: Imagine you stop practicing the "Spicy Tuna" recipe entirely. Over time, your muscle memory for it naturally fades away because you keep cooking other things.

How it works: The model just keeps learning new tasks. The old data gets pushed out naturally.
The Good: It costs zero extra storage. You don't need to keep any extra notes.
The Bad: It's messy. If the customer asks to forget a recipe from yesterday, it hasn't faded yet, so you can't forget it properly. If they ask to forget something from last year, it's already gone, but you might have accidentally forgotten other things too. It's like trying to erase a drawing by just waiting for the ink to dry; sometimes it works, sometimes it smudges the whole page.

B. The "Precise Eraser" Method (Hessian-Based)

The Analogy: This is like having a high-tech eraser that knows exactly how much pressure to apply to remove only the "Spicy Tuna" ink without touching the "Sushi Rice."

How it works: The model keeps a detailed "map" (called a Hessian matrix) of how every ingredient in every recipe connects to every other ingredient. When a deletion request comes, it uses this map to mathematically reverse the specific changes made by that one recipe.
The Good: It is incredibly accurate. It forgets exactly what it's supposed to, even if the request is for a recipe learned just moments ago.
The Bad: It's heavy. Keeping that detailed map for every single day of cooking takes up a massive amount of storage space (like carrying a library of maps in your apron).

C. The "Hybrid Chef" (The Paper's Innovation)

The Analogy: The authors realized you don't need the heavy map for everything.

The Strategy:
- For old recipes (learned a long time ago), rely on Natural Fade. They are already fading, so you don't need the heavy map.
- For new recipes (learned recently), use the Precise Eraser. These are still fresh in your mind, so you need the map to remove them cleanly.
The Result: You get the best of both worlds. You save a huge amount of storage space (by throwing away the old maps) while still maintaining high accuracy for the recent deletions.

3. The "Certified" Guarantee

The paper doesn't just say, "We think we forgot it." They use a mathematical guarantee called Certified Unlearning.

The Analogy: Imagine a notary public.

Old way: You say, "I burned the recipe." The customer has to trust you.
New way: The notary checks your kitchen and says, "I can mathematically prove that the current state of your kitchen is statistically indistinguishable from a kitchen where that recipe was never written in the first place."
This is crucial for privacy laws. It proves you didn't just "hide" the data; you truly removed its influence.

4. What Did They Find?

The Trade-off: You can't have perfect forgetting and perfect retention without a cost. You have to choose between storing more data (to be precise) or storing less (and accepting a bit more "smudging").
The Order Matters: If you ask to forget things in a logical order (e.g., "Forget Tuesday's menu, then Wednesday's"), it's much easier and more accurate than asking to forget things in a chaotic, random order.
The Winner: The Hybrid approach (using natural fading for old stuff and precise erasing for new stuff) offers the best balance. It keeps the storage costs low while ensuring the "forgetting" is mathematically certified and accurate.

Summary

This paper builds the first theoretical rulebook for how to "unlearn" in a world where AI is constantly learning new things. They showed that you can't just delete data like a computer file; you have to carefully balance keeping your skills sharp while surgically removing specific memories. Their solution is a smart mix of "letting old memories fade" and "using a precise tool for new ones," all backed by a mathematical guarantee that the data is truly gone.

Technical Summary: The Forgetting-Retention Dilemma: Certified Unlearning Theory in Continual Learning

Problem Formulation

The paper addresses the intersection of Machine Unlearning and Continual Learning (CL). While machine unlearning aims to remove the influence of specific data to satisfy privacy regulations (e.g., the "right to be forgotten"), and CL aims to learn sequential tasks without catastrophic forgetting, combining them presents a fundamental theoretical and practical challenge.

Existing certified unlearning algorithms (e.g., Hessian-based or gradient-based methods) are designed for static settings. They fail in CL contexts because:

Complex Model Evolution: CL models evolve dynamically over non-i.i.d. tasks, encoding past information in complex ways that current certified algorithms cannot effectively reverse.
Conflicting Objectives: The goal of CL is to prevent forgetting (preserving historical knowledge), while unlearning requires targeted forgetting.
Storage and Access Constraints: Many certified unlearning methods require full data retention or fail to handle arbitrary, asynchronous unlearning request sequences common in dynamic environments.

The authors formalize the Continual Learning-Unlearning (CLU) problem as a sequential two-stage process:

Learning Stage: The model updates on a new task $D_t$ using an $\ell_2$ -regularized scheme to mitigate forgetting.
Unlearning Stage: Upon receiving a request to delete a set of past tasks $S_t$ , the system must produce a model indistinguishable from one retrained on the remaining data, satisfying $(\epsilon, \delta)$ -certified unlearning guarantees.

The primary performance metric is the Post-Unlearning Excess Risk ( $E_{LU}$ ), which decomposes into two competing terms:

Unlearning Loss ( $E_U$ ): The error introduced by the approximation of the retrained model (the "forgetting" cost).
CL Excess Risk ( $E_L$ ): The error incurred by the CL algorithm on the retained tasks (the "retention" cost).

Methodology

The paper establishes a theoretical foundation for CLU and proposes three algorithmic approaches:

1. Theoretical Foundation

The authors derive an upper bound for the CL excess risk ( $E_L$ ) in non-convex models under $\ell_2$ -regularization. They prove that the optimal regularization parameter $\lambda$ for minimizing CL excess risk may differ significantly from the one required to minimize unlearning loss, highlighting the inherent trade-off.

2. Gradient-Based CLU (Natural Forgetting)

This approach leverages the "natural forgetting" phenomenon inherent in CL, where the influence of distant past tasks decays over time due to sequential updates.

Mechanism: Instead of explicit unlearning steps, the method adds Gaussian noise to the model parameters. The noise scale is calibrated based on a theoretical upper bound ( $\gamma_t$ ) of the approximation error, which quantifies the residual influence of deleted tasks.
Advantage: It requires zero storage overhead beyond the current model state.
Limitation: It is less effective for recent tasks where natural forgetting has not yet occurred, leading to higher unlearning loss.

3. Hessian-Based CLU

This approach adapts second-order certified unlearning methods to the CL setting to achieve accurate, targeted forgetting.

Mechanism: It utilizes stored Hessian information (or approximations like Gauss-Newton or diagonal Hessians) and model updates ( $\Delta_t$ ) to compute a correction term ( $\bar{\Delta}_t$ ). This term approximates the retrained model in a single step, even for arbitrary, asynchronous unlearning sequences.
Challenge: Handling asynchronous requests creates "temporal disorder," where the influence of past deletions propagates into subsequent updates. The authors derive a recursive correction term to account for this.
Cost: It incurs storage overhead proportional to the number of unlearning events and the dimension of the Hessian approximation.

4. Hybrid Strategy (Forgetting-Enhanced Hessian)

To balance storage costs and accuracy, the authors propose a hybrid strategy.

Mechanism: It uses the Hessian-based method for recent unlearning requests (where natural forgetting is weak) and relies on natural forgetting for distant past tasks.
Implementation: The algorithm discards stored Hessian information for tasks older than a specific temporal threshold (determined by the gap between unlearning events).
Benefit: This reduces storage complexity from $O(t \cdot d)$ to $O(\max(t_i - t_{i-1}) \cdot d)$ , where $t_i$ are unlearning times, while maintaining low unlearning error.

Key Results

Experiments were conducted on MNIST, CIFAR-10, and CIFAR-100 using ResNet-18 and CNN backbones with non-i.i.d. task sequences.

Order Sensitivity: Theoretical bounds and experiments confirm that forward-synchronous unlearning sequences (where deleted tasks are strictly newer than the last unlearning event) yield lower approximation errors than asynchronous sequences. Asynchronous requests accumulate additional error terms due to temporal disorder.
Accuracy vs. Storage Trade-off:
- Natural Forgetting (Gradient-based): Achieves the lowest storage (near zero) but suffers from the highest approximation error, particularly for recent tasks.
- Pure Hessian-based: Achieves approximation errors close to full retraining (e.g., ~0.009 on CIFAR-100) but requires significant memory (up to 5x higher than natural forgetting in the Gauss-Newton variant).
- Hybrid (Forgetting-Enhanced): Reduces memory usage significantly (comparable to diagonal Hessian) with only a modest increase in approximation error (~0.045), offering a practical middle ground.
Certified Guarantees: Theoretical upper bounds ( $\gamma_T$ ) were validated against empirical errors. The bounds hold for both gradient and Hessian-based methods, ensuring $(\epsilon, \delta)$ -certified unlearning.
Retention-Forgetting Trade-off: Increasing the regularization strength $\lambda$ reduces unlearning error (by limiting parameter drift) but degrades pure CL test accuracy, empirically validating the theoretical tension between retention and forgetting.

Significance and Claims

The paper claims to provide the first theoretical foundation bridging certified unlearning and continual learning. Its significance lies in:

Formalizing the Trade-off: It rigorously defines the "Forgetting-Retention Dilemma" by decomposing post-unlearning risk into CL excess risk and unlearning loss, proving that minimizing one often exacerbates the other.
Theoretical Bounds: It establishes the first excess-risk bounds for $\ell_2$ -regularized CL in non-convex settings and extends certified unlearning theory to dynamic, sequential request patterns.
Practical Algorithms: It introduces a hybrid strategy that resolves the storage bottleneck of second-order unlearning methods without sacrificing the theoretical guarantees of certified unlearning.
Benchmarking: It provides a rigorous baseline (Natural Forgetting) and demonstrates that while simple, it is insufficient for recent tasks, necessitating the proposed Hessian-based enhancements.

The authors conclude that while their work focuses on the fundamental $\ell_2$ -regularized CL algorithm, it opens the door for extending certified unlearning theory to more sophisticated CL methods, such as memory-based approaches or Elastic Weight Consolidation (EWC).