Descend or Rewind? Stochastic Gradient Descent Unlearning

This paper establishes $(\varepsilon, \delta)$ certified unlearning guarantees for stochastic versions of the Descent-to-Delete (D2D) and Rewind-to-Delete (R2D) algorithms across strongly convex, convex, and nonconvex loss functions by analyzing them as disturbed gradient systems and coupling their trajectories with retraining, ultimately revealing that D2D offers tighter guarantees for strongly convex functions while R2D is better suited for convex and nonconvex scenarios.

The Gist

Imagine you have a giant, super-smart student who has studied a massive library of books to become an expert. One day, a specific person (let's call him "Bob") realizes his book was used to train this student and demands, "I want my book removed from your memory! I have the right to be forgotten."

The student can't just delete one page from a million-page book and hope the rest makes sense. The old way to fix this was to make the student forget everything, throw away the library, and start studying from scratch without Bob's book. This is accurate, but it takes forever and costs a fortune in energy.

This paper introduces two clever shortcuts to "unlearn" Bob's book without restarting the whole school year. The authors compare two methods: "Descent-to-Delete" (D2D) and "Rewind-to-Delete" (R2D).

Here is the breakdown of their findings using simple analogies:

The Two Strategies

1. Descent-to-Delete (D2D): "The Backwards Walk"

• The Idea: Imagine the student is standing at the very top of a mountain (the final trained model). To remove Bob's influence, the student tries to walk backwards down the slope, taking small steps to adjust their position.
• The Problem: On a smooth, simple hill (a "convex" function), this works great. But on a real-world mountain with jagged peaks, hidden valleys, and tricky terrain (a "nonconvex" function, like deep neural networks), walking backwards is dangerous. The student might get stuck in a small hole (a local minimum) or wander off into a completely different valley. They end up in a spot that looks different from where they started, but it's not the right spot for the "Bob-less" version.
• The Paper's Verdict: This method is risky for complex, modern AI models. It often fails to actually "forget" correctly and might just make the model worse at other tasks.

2. Rewind-to-Delete (R2D): "The Time Machine"

• The Idea: Instead of walking backwards from the finish line, imagine the student had a time machine. They go back to a checkpoint from earlier in their studies (say, halfway through the semester). From that earlier point, they re-study the library without Bob's book.
• Why it works: Because they are starting from a point where the student's knowledge was still flexible and not yet "stuck" in a specific pattern, they can smoothly integrate the new reality (no Bob) without getting lost. They are essentially re-doing the last part of the training, but starting from a safer, more stable place.
• The Paper's Verdict: This is the winner for complex, modern AI. It is more reliable, computationally cheaper, and actually achieves the goal of "forgetting" without breaking the model.

The "Stochastic" Twist (The Noise Factor)

In the real world, students don't read books in perfect order; they read random pages (this is called Stochastic Gradient Descent or SGD). This randomness makes the math much harder.

• The Challenge: The authors had to prove that even with this randomness, the "Rewind" method still guarantees that the final model is indistinguishable from one that never saw Bob's book at all.
• The Secret Sauce: They used a mathematical trick called "Coupling." Imagine two students: one studying with Bob's book, and one studying without it. The authors proved that if you make them read the exact same random pages at the same time (except for Bob's book), their paths will stay very close together.
  • For simple hills, the "Backwards Walk" (D2D) is actually slightly more precise.
  • For jagged mountains (real-world AI), the "Time Machine" (R2D) is the only one that doesn't get lost.

The "Privacy Noise"

To make the unlearning mathematically "certified" (proving to a judge that Bob is truly forgotten), the algorithms add a tiny bit of "static" or "noise" to the final answer.

• Think of this like blurring a photo just enough so you can't identify a specific face, but the photo still looks like a face.
• The paper proves that the "Rewind" method needs less of this blurring (noise) to be safe, meaning the final model stays smarter and more accurate.

The Bottom Line

If you want to remove data from a simple, predictable model, you can try walking backwards (D2D). But if you are dealing with modern, complex AI (like the ones powering chatbots or image generators), you should Rewind to an earlier checkpoint and retrain from there (R2D).

Why does this matter?

• Privacy: It helps companies comply with laws like GDPR (the "Right to be Forgotten") without spending millions of dollars retraining models from scratch.
• Efficiency: It saves massive amounts of energy and time.
• Safety: It ensures that when a user asks to be forgotten, they actually are, rather than the model just pretending to forget while secretly keeping the data in a hidden corner.

In short: Don't try to walk backwards off a cliff; use a time machine to go back to solid ground.

Technical Summary

1. Problem Statement

Machine unlearning aims to remove the influence of specific training data points from a trained model without the prohibitive computational cost of retraining from scratch. While $(\varepsilon, \delta)$-certified unlearning provides a rigorous theoretical guarantee (ensuring the unlearned model is indistinguishable from a model retrained on the remaining data), existing methods face significant limitations:

• Second-order methods: Require Hessian computations, which are intractable for large-scale deep learning models.
• First-order full-batch methods: Require full gradient computations, which are inefficient for large datasets.
• Stochastic limitations: Existing stochastic certified unlearning algorithms either apply only to convex functions or provide weaker "post-processing" guarantees rather than full indistinguishability.
• The "Finetuning" Baseline: The stochastic version of "Descent-to-Delete" (D2D) is widely used as a baseline (often called "finetuning"), but it lacks theoretical backing for nonconvex functions and often performs poorly in practice (e.g., getting stuck in stationary points).

The paper addresses the open question: Can stochastic versions of D2D and "Rewind-to-Delete" (R2D) provide provable $(\varepsilon, \delta)$-certified unlearning guarantees for nonconvex loss functions?

2. Methodology

The authors analyze two first-order unlearning frameworks adapted for Stochastic Gradient Descent (SGD):

1. SGD-D2D (Descent-to-Delete): Starts unlearning from the final trained model ($\theta_T$) and performs $K$ steps of SGD on the retained dataset.
2. SGD-R2D (Rewind-to-Delete): Starts unlearning from an earlier checkpoint ($\theta_{T-K}$) saved during training and performs $K$ steps of SGD on the retained dataset.

Core Analytical Framework

The proof strategy relies on coupling arguments and gradient system contraction theory:

• Coupling: The authors couple the randomization (mini-batch sampling) of the training trajectory (on the full dataset $D$) and the retraining trajectory (on the retained dataset $D'$). By maximizing the overlap in sampled batches, they minimize the divergence between the two trajectories.
• Disturbed/Biased Systems: They characterize the training process on $D$ as a "biased" or "disturbed" SGD process relative to the loss function of $D'$.
• Contraction Properties:
  • Strongly Convex: The gradient system is contracting. Disturbances decay exponentially, keeping trajectories close.
  • Convex: The system is semi-contracting. Disturbances grow linearly.
  • Nonconvex: The system is expansive. Disturbances can grow exponentially.
• Sensitivity Bounds: Instead of deterministic sensitivity bounds (required by classic Gaussian mechanisms), the authors derive expected sensitivity bounds ($\mathbb{E}[\|\theta'_{T} - \theta''_{K}\|]$). They combine these with Markov's inequality to establish tail bounds, achieving $(\varepsilon, 2\delta)$ indistinguishability.
• Noise Injection: Gaussian noise is added only at the end of the unlearning process (black-box approach), rather than at every step.

3. Key Contributions

1. Theoretical Guarantees for SGD-R2D: Proved $(\varepsilon, \delta)$-certified unlearning for SGD-R2D on strongly convex, convex, and nonconvex loss functions. This is the first result to provide such guarantees for nonconvex functions using a stochastic unlearning algorithm with minimal assumptions.
2. Theoretical Guarantees for SGD-D2D: Proved $(\varepsilon, \delta)$-certified unlearning for SGD-D2D on strongly convex functions. The proof uses a novel approach that "folds" the unlearning bias into the convergence analysis, circumventing the restrictive Lipschitz continuity assumptions of previous work.
3. Privacy-Utility-Complexity Tradeoffs: Derived explicit bounds on the required noise magnitude ($\sigma$) as a function of the number of unlearning iterations ($K$), training iterations ($T$), and dataset size ($n$).
   • For strongly convex functions, R2D offers a significant computational advantage: as $T \to \infty$, the required $K$ converges to a constant, implying an infinite computational advantage ($T-K$) over retraining.
4. Empirical Validation: Conducted experiments on real-world datasets (eICU and Lacuna-100) comparing SGD-R2D and SGD-D2D.

4. Results and Findings

Theoretical Results

• R2D Superiority in Nonconvex Settings: For nonconvex functions, R2D is theoretically superior because rewinding to an earlier checkpoint allows the algorithm to "undo" the accumulation of disturbances caused by the removed data. D2D, starting from the final model, cannot effectively reverse the divergence in nonconvex landscapes.
• D2D Efficiency in Strongly Convex Settings: For strongly convex functions, D2D can yield tighter probabilistic bounds than R2D because the bias can be folded into the convergence analysis. However, if the initial point is close to the global minimum, D2D may not be more efficient than retraining.
• Noise Requirements: The required noise scales with the sensitivity bound $\Sigma$. For R2D on nonconvex functions, $\Sigma$ grows with $(T-K)$, whereas for strongly convex functions, it decays exponentially with $K$.

Empirical Results

• Performance on Nonconvex Models (ResNet-18):
  • SGD-R2D: Successfully moved the model parameters away from the original model and towards the retrained model. It effectively reduced the model's performance on the unlearned data while maintaining performance on retained data.
  • SGD-D2D: Failed to unlearn effectively. The model often stalled at a stationary point near the initialization or moved in a direction that improved performance on the unlearned data (indicating a failure to "forget").
• Membership Inference Attacks (MIA): R2D demonstrated stronger resistance to membership inference attacks compared to D2D. D2D's tendency to improve performance on unlearned data made it harder to distinguish whether unlearning had occurred, potentially masking privacy leaks.
• Comparison with PABI: Compared against the "Privacy Amplification by Iteration" (PABI) baseline. While PABI achieved better model utility (due to noiseless finetuning), it suffered from the same flaw as D2D: it sometimes improved performance on the unlearned set, suggesting incomplete unlearning. R2D provided more reliable unlearning behavior.

5. Significance

• Bridging Theory and Practice: This work provides the first rigorous theoretical justification for using stochastic gradient-based unlearning in nonconvex deep learning settings, a domain where most existing certified methods fail.
• Redefining the Baseline: The paper challenges the community's reliance on "finetuning" (stochastic D2D) as a baseline for unlearning. It demonstrates that rewinding is a theoretically sound and empirically superior strategy for nonconvex models.
• Black-Box Applicability: The proposed algorithms are "black-box," requiring no changes to the training procedure (no per-step noise or clipping) and only needing noise injection at the end. This makes them highly practical for deployment on pre-trained Large Language Models (LLMs) and other large-scale systems.
• Computational Efficiency: The analysis highlights that for strongly convex problems, unlearning can be exponentially faster than retraining, offering a pathway to scalable, privacy-compliant machine learning.

In conclusion, the paper establishes that Rewind-to-Delete (R2D) is the preferred method for stochastic unlearning in modern, nonconvex deep learning scenarios, offering provable guarantees where previous methods (like D2D) fail both theoretically and empirically.