🤖 machine learning

Sequential Subspace Noise Injection Prevents Accuracy Collapse in Certified Unlearning

This paper introduces sequential subspace noise injection, a method that distributes noise across orthogonal parameter subspaces to significantly improve the accuracy of certified unlearning while maintaining rigorous differential privacy guarantees.

Original authors: Polina Dolgova, Sebastian U. Stich

Published 2026-06-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Polina Dolgova, Sebastian U. Stich

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

The Big Problem: The "Eraser" That Rubs Out Everything

Imagine you have a highly skilled artist (a machine learning model) who has painted a masterpiece based on a specific set of photos. Suddenly, a customer says, "I want you to forget that one specific photo I gave you."

In the legal world (like GDPR), you can't just pretend you forgot; you have to prove mathematically that the photo is gone. The current standard way to do this is called Certified Unlearning. It works like a very aggressive eraser. To prove the photo is gone, the algorithm adds a massive amount of "static noise" to the artist's memory and then tries to repaint the picture.

The Catch: The current method is so aggressive that it doesn't just erase the bad photo; it smears the entire canvas. The artist forgets everything, including the good parts of the painting. By the time they try to fix the painting, the colors are so muddy that the picture is ruined (this is called "accuracy collapse").

The Solution: The "One-Block-at-a-Time" Strategy

The authors propose a new method called Block-wise Noisy Fine-Tuning. Instead of smearing the whole canvas at once, they break the painting down into small, separate blocks (like a grid of tiles).

Here is how their method works, using a simple analogy:

The Old Way (The Sledgehammer): Imagine trying to remove a specific stain from a giant tapestry by hitting the entire tapestry with a sledgehammer. You might get the stain out, but you've also torn holes in the whole thing.
The New Way (The Scalpel): The authors suggest treating the tapestry like a puzzle. They cover the whole thing with a grid.
- They pick one single tile (a block of the model's memory).
- They apply the "noise" (the eraser) only to that one tile.
- They leave all the other tiles frozen and untouched.
- Then, they move to the next tile and repeat the process.

Why this helps: Because they are only shaking one small part of the model at a time, the rest of the model stays stable. The "noise" doesn't overwhelm the whole system. It's like cleaning a room by cleaning one drawer at a time, rather than throwing all the furniture out the window and hoping to find your socks later.

The Second Problem: The "Worst-Case" Fear

The paper also points out a second issue with the old method. The old rules were designed to work even if the artist started with a completely blank, random canvas. This forced the algorithm to assume the worst possible scenario, requiring even more noise to be safe.

The authors realized that in reality, the artist isn't starting from scratch; they are starting from a finished painting and just need to tweak it. They introduced a new way to measure the "distance" between the original painting and the one without the bad photo. By using this realistic measurement instead of a "worst-case" guess, they can use less noise, keeping the painting clearer.

The Results: A Clean Slate Without Ruining the Art

The researchers tested this on image recognition tasks (like identifying cats and dogs in photos).

The Old Method: When they tried to remove data, the model's accuracy dropped from 88% to below 20%. It was a disaster.
The New Method: By using the "one-block-at-a-time" approach, the model successfully removed the unwanted data (proving it was gone) but kept its ability to recognize images almost as good as if it had been retrained from scratch.

The Bottom Line

This paper doesn't just say "we made it faster." It solves a fundamental flaw where the safety guarantee (proving data is gone) was destroying the usefulness of the AI.

They found a way to apply the "safety noise" in a smart, sequential pattern (block by block) and with a more realistic starting point. This allows us to legally and mathematically "forget" specific data without destroying the AI's brain in the process. It bridges the gap between strict legal safety and practical, working technology.

Technical Summary: Sequential Subspace Noise Injection for Certified Unlearning

Problem Statement

Machine unlearning aims to remove the influence of specific training data from a trained model to comply with regulations like GDPR or to remove sensitive information. While retraining from scratch is the gold standard, it is often computationally prohibitive. Certified unlearning methods, particularly those based on Differential Privacy (DP), offer formal guarantees of data removal but suffer from a critical practical limitation: accuracy collapse.

Current approaches, such as Noisy Fine-Tuning (NFT) with gradient clipping, inject Gaussian noise to satisfy $(\epsilon, \delta)$ -unlearning guarantees. However, in over-parameterized deep networks, the noise required to certify unlearning is often large enough to dominate the gradient signal across all parameters simultaneously. Empirical results show that standard NFT can cause test accuracy to drop sharply (e.g., from 88% to below 20% on CIFAR-10) and fail to recover even after subsequent fine-tuning. This creates a tension between maintaining rigorous formal guarantees and preserving model utility.

Methodology

The authors propose Block-wise Noisy Fine-Tuning (Block-wise NFT), a modification to the standard NFT framework designed to mitigate accuracy collapse while retaining formal certified guarantees. The method addresses two specific bottlenecks in existing certified unlearning analyses:

1. Sequential Subspace Noise Injection

Standard NFT injects noise into the full parameter space at every step. The authors observe that for high-dimensional models, the $\ell_2$ -norm of the noise vector ( $\sigma\sqrt{d}$ ) overwhelms the clipped gradient updates.

Approach: The parameter space $\mathbb{R}^d$ is partitioned into $k$ mutually orthogonal subspaces (blocks).
Mechanism: Instead of updating all parameters, the algorithm sequentially updates one block at a time. During the update of a specific block, noise is injected only into that subspace, while all other parameters are frozen.
Benefit: This redistributes the same certified noise budget over time and across lower-dimensional subspaces. By restricting perturbations to a fraction ( $1/k$ ) of the coordinates per step, the per-step distortion is significantly reduced, preventing the noise from dominating the training signal.

2. Proximity-Based Calibration ( $\Delta(\rho)$ )

Standard NFT analyses often rely on worst-case model clipping radii ( $C_0$ ) to handle arbitrary initializations, which leads to overly conservative noise requirements.

Approach: The authors replace the worst-case initialization assumption with a high-probability proximity parameter, $\Delta(\rho)$ . This parameter bounds the distance between the fully trained model (on the full dataset) and the retrained model (on the retained dataset) under a fixed coupling of randomness.
Mechanism: By calibrating the noise and clipping based on the actual distance $\Delta(\rho)$ rather than a worst-case diameter, the required noise variance is reduced.
Benefit: This yields a certificate tailored to the specific retraining comparison, avoiding the pessimism of training-agnostic worst-case bounds.

Algorithm Overview

The Block-wise NFT algorithm proceeds as follows:

Partitioning: Decompose model weights into $k$ orthogonal blocks.
Sequential Updates: For each block $i$ $i$ :
- Freeze all parameters except block $i$ .
- Apply noisy fine-tuning to block $i$ using the calibrated noise variance $\sigma^2$ and step count $T$ derived from $\Delta(\rho)$ .
- No initial worst-case clipping ( $C_0$ ) is applied; only the proximity-based bound is used.
Finalization: After all blocks have been updated sequentially, perform standard fine-tuning on the full model to recover utility.

Key Contributions

Method: Introduction of Block-wise NFT, which applies certified noisy updates sequentially across orthogonal parameter blocks. This reduces per-step distortion while ensuring full parameter coverage over the unlearning schedule.
Certification: Extension of the NFT certification analysis to the block-wise schedule. The authors prove that the same $(\epsilon, \delta)$ privacy budget is retained. They also formalize the replacement of worst-case model clipping with the proximity parameter $\Delta(\rho)$ .
Theoretical Insight: Identification of a "Formal Bottleneck" where training-agnostic, worst-case certification creates a utility-efficiency tension. The authors demonstrate that maintaining high utility in fewer steps than retraining is impossible under initialization-agnostic indistinguishability, motivating the shift to proximity-based formulations.
Empirical Validation: Demonstration that Block-wise NFT prevents accuracy collapse on MNIST and CIFAR-10 benchmarks (using ResNet-18 and ViT-Tiny) under both random and class-wise deletions, while remaining robust to membership inference attacks (MIA).

Experimental Results

The paper evaluates Block-wise NFT against standard NFT, retraining from scratch, and various empirical (uncertified) unlearning baselines.

Accuracy Recovery: On CIFAR-10 with ViT-Tiny, standard NFT drops accuracy to below 20% and fails to recover. In contrast, Block-wise NFT maintains significantly higher accuracy during the unlearning phase and recovers to near-retraining levels after fine-tuning.
Privacy Guarantees: The method achieves 100% Unlearned Accuracy (UA) and 100% MIA scores (indicating no leakage), matching the performance of retraining from scratch on these metrics.
Efficiency: Block-wise NFT is computationally efficient, with runtimes comparable to standard NFT and significantly lower than retraining from scratch.
Robustness: The method remains effective across different block sizes ( $k$ ) and block construction strategies (random vs. layer-wise), showing that the gains are not highly sensitive to the specific partitioning.

Significance and Claims

The paper claims that Block-wise NFT bridges the gap between rigorous formal guarantees and practical utility in certified unlearning.

Mitigation of Accuracy Collapse: The primary contribution is demonstrating that the severe accuracy degradation associated with DP-inspired unlearning is not an inherent limitation of certified unlearning but a consequence of specific design choices (full-space noise injection and worst-case clipping).
Practical Viability: By utilizing sequential subspace injection and proximity calibration, the method makes certified unlearning substantially less destructive in the studied regimes.
Limitations and Scope: The authors are modest about the generality of their claims. They note that the calibration of $\Delta(\rho)$ is empirical and specific to the model class and training pipeline. They emphasize that their guarantees are conditional on the stated certification setting and calibration procedure, and that the method does not claim to be a universal solution for all unlearning scenarios without proper calibration.

In summary, the work argues that certified unlearning can be made practical for large models by moving away from worst-case, global noise injection toward structured, sequential updates that respect the actual proximity of the models involved in the unlearning process.