🤖 machine learning

Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses

This paper establishes near-optimal upper and lower bounds on the statistical cost of machine unlearning for smooth strongly convex losses, demonstrating that the optimal error rate interpolates between retraining-from-scratch and exponentially smaller terms depending on the relationship between the unlearning parameter $\varepsilon$ and the model dimension $d$ .

Original authors: Matthew Regehr, Gautam Kamath, Andrew Lowy

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthew Regehr, Gautam Kamath, Andrew Lowy

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 chef who has cooked a massive stew using thousands of ingredients from a giant market. This stew represents a machine learning model trained on a huge dataset.

Now, imagine a customer comes in and says, "I want to take back the 50 carrots I contributed to this stew. Please make a new version of the stew that tastes exactly the same as if I had never given you those carrots in the first place." This is the concept of Machine Unlearning.

The paper you provided tackles a very specific question: How much does the taste of the stew suffer when we try to remove those carrots, compared to just throwing away the whole pot and cooking a fresh one from scratch?

Here is the breakdown of their findings using simple analogies:

The Two Obvious (But Flawed) Ways to Do It

The "Forget Everything" Approach (Differential Privacy):
Imagine the chef decides to add a tiny bit of "noise" or "fog" to the recipe before anyone even knows which carrots to remove. This way, no one can tell if specific carrots were used or not.
- The Problem: This is overly cautious. The chef adds so much fog that the stew tastes worse than it needs to, even if only one carrot needs to go.
The "Start Over" Approach (Retraining from Scratch):
The chef throws away the whole pot, takes out the 50 carrots, and starts cooking the entire stew again from the beginning with the remaining ingredients.
- The Problem: This is perfect for removing the carrots (the new stew is exactly what it should be), but it's incredibly wasteful and slow. You lose all the work done on the original pot.

The Paper's Big Discovery: A "Magic Swap"

The authors, Matthew Regehr, Gautam Kamath, and Andrew Lowy, found a "Goldilocks" solution that sits between these two extremes. They developed a new algorithm that acts like a magic swap.

Here is how their "Core-swap" algorithm works in plain English:

The Setup: The chef keeps a "backup plan" ready. When the stew is finished, the chef doesn't just serve the main pot. They also prepare a "safety net" version that looks like the stew without the specific carrots, but they hide it inside a slightly larger, fuzzy cloud of possibilities.
The Request: When the customer says, "Remove my carrots," the chef doesn't throw everything away. Instead, they perform a clever trick:
- They take the main, delicious stew (which includes the carrots).
- They swap the "fuzzy cloud" part of the recipe to match the version without the carrots.
- Crucially, they do this in a way that makes it statistically impossible for an outsider to tell if the chef actually removed the carrots or just swapped the recipe around.

The "Privacy Budget" (The $\epsilon$ Factor)

The paper introduces a variable called $\epsilon$ (epsilon). Think of this as your "Privacy Budget" or "Confidence Level."

Low Budget ( $\epsilon$ is small): If you demand to be absolutely sure the carrots are gone (very strict privacy), the "magic swap" doesn't help much. In this case, the best you can do is just retrain from scratch. The paper proves that if your privacy demands are this high, you can't cheat the system; you have to pay the full cost of starting over.
High Budget ( $\epsilon$ is large): If you are willing to accept a tiny, almost imperceptible chance that the carrots might still be "technically" there (but statistically hidden), the magic swap shines.
- The Result: The paper shows that when you have a high privacy budget, their new algorithm is exponentially better than starting over. It's like getting a fresh-tasting stew with 99% of the effort saved. The error (the difference in taste) drops so low it's almost negligible compared to the "start over" method.

The "Dimension" Factor

The paper also mentions $d$ (the dimension). In our analogy, imagine the stew has many different flavor profiles (salt, sweet, sour, spicy, etc.).

If the number of flavors ( $d$ ) is small compared to your privacy budget ( $\epsilon$ ), the magic swap works wonders.
If the number of flavors is huge compared to your budget, the magic swap struggles, and you are better off just starting over.

The Bottom Line

The authors proved that they have found the theoretical limit of how well you can unlearn data.

If you want perfect privacy: You must retrain from scratch. There is no shortcut.
If you have a flexible privacy budget: You can use their new "Core-swap" method to get a result that is exponentially more accurate than retraining from scratch, while still satisfying the legal requirement to "forget" the data.

They didn't just invent a new trick; they proved mathematically that you cannot do better than their method (up to a small factor related to how "curved" the math problem is). They solved the puzzle of exactly how much "statistical pain" you have to pay to remove a piece of data from a machine learning model.

Technical Summary: Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses

Problem Statement

The paper investigates the fundamental statistical cost of machine unlearning within the framework of smooth strongly convex stochastic convex optimization (SCO). The goal is to design an algorithm that, given a dataset $Z$ and a request to delete a subset of samples $U$ (where $|U| \le m$ ), outputs an updated model that is statistically indistinguishable from a model trained from scratch on the retained data $Z \setminus U$ .

The quality of the solution is measured by the excess population risk, defined as $\Delta_{F_P}(w) = F_P(w) - F^*_P$ , where $F_P$ is the population loss. The central question addressed is: What is the minimax optimal excess population risk for $\epsilon$ -unlearning up to $m$ samples in smooth strongly convex SCO?

The paper considers approximate $\epsilon$ -unlearning, where the output distribution of the unlearning algorithm on $(Z, U)$ must be $\epsilon$ -indistinguishable (in the max-divergence sense) from the output of the learning algorithm run on $Z \setminus U$ with an empty deletion request.

Methodology

1. Upper Bound: Core-Swap $\epsilon$ -Unlearning Algorithm

The authors propose a novel algorithm (Algorithm 1) that interpolates between two extreme strategies:

Retraining from Scratch (RFS): Returns the Empirical Risk Minimizer (ERM) on $Z \setminus U$ . This satisfies exact 0-unlearning but incurs high statistical error due to discarding data.
Ignore Request: Returns the ERM on the full dataset $Z$ . This is accurate but fails unlearning guarantees.

Mechanism:
The algorithm exploits the geometry of the solution space. It constructs a mixture distribution for the output:

High Probability: Sample uniformly from a small ball centered at the full-data ERM solution $\hat{w}_Z$ . This ensures high accuracy.
Low Probability: Sample uniformly from a larger ball centered at the reduced-data ERM solution $\hat{w}_{Z \setminus U}$ . This ball is sized large enough to cover any possible full-data ERM solutions that could result in the same retained dataset $Z \setminus U$ after a valid deletion.

By carefully calibrating the radii of these balls and the mixing probability $\eta$ , the algorithm ensures that the likelihood ratio between the "dry run" (no deletion) and the "true run" (deletion) remains bounded by $e^\epsilon$ . The algorithm requires two calls to an ERM oracle and one convex projection, running in $O(d)$ time.

2. Lower Bound: Packing Argument

To establish optimality, the authors derive a lower bound using a packing technique distinct from standard differential privacy arguments.

Construction: They construct a set of "hard" mean estimation instances where the means point in many separated directions within the unit ball.
Deletion Strategy: For each instance, a specific deletion request is defined that removes the "signal" samples (the non-zero entries) with high probability.
Collapse: After deletion, the retained datasets for all these distinct instances collapse to a common reference dataset (all zeros).
Indistinguishability: The $\epsilon$ -unlearning constraint forces the output distributions for all these distinct initial instances to be close to the distribution produced by the common reference dataset.
Packing Limit: The size of the packing (number of separated directions) limits the accuracy with which the algorithm can recover the true mean, leading to a lower bound on the error.

Key Contributions and Results

1. Minimax Optimal Rates

The paper establishes nearly tight upper and lower bounds on the excess population risk for smooth strongly convex SCO. The optimal rate is characterized as:
$\text{Risk} \approx \frac{1}{n} + \left(\frac{m}{n}\right)^2 e^{-2\epsilon/(d+2)}$
where:

$\frac{1}{n}$ is the standard statistical error term.
$\left(\frac{m}{n}\right)^2$ is the penalty for retraining from scratch.
$e^{-2\epsilon/(d+2)}$ is the exponential improvement factor achievable by the proposed unlearning algorithm.

The bounds are tight up to a condition-number factor $\kappa = \beta/\mu$ (where $\beta$ is smoothness and $\mu$ is strong convexity).

2. Sharp Characterization for Mean Estimation

For the specific case of mean estimation over the unit ball in $\mathbb{R}^d$ , the authors provide upper and lower bounds that match up to constants. This gives an essentially sharp characterization of the statistical price of unlearning in this canonical setting.

3. Analysis of Baselines and Prior Work

Retraining from Scratch: The paper provides a sharp analysis showing that RFS achieves an excess risk of $O(1/n + (m/n)^2)$ . It is proven to be optimal when $\epsilon \lesssim d$ .
Differential Privacy (DP): The paper notes that standard DP baselines (group DP) yield a risk of $O(1/n + d^2 m^2 / (\epsilon^2 n^2))$ , which is suboptimal compared to the proposed method when $\epsilon \gg d$ .
Prior Algorithms: The authors sharpen the analysis of the Newton-step algorithm from [SAKS21], showing a quadratic improvement in the unlearning error term, and identify a bug in the utility analysis of [AKGK25], providing a corrected guarantee.

4. Regime Analysis

The results delineate two distinct regimes based on the ratio of the privacy budget $\epsilon$ to the dimension $d$ :

Low Budget ( $\epsilon \lesssim d$ ): Retraining from scratch is statistically optimal. The unlearning penalty cannot be improved beyond the $(m/n)^2$ term.
High Budget ( $\epsilon \gg d$ ): The proposed algorithm offers an exponential improvement in accuracy over retraining from scratch and DP-based baselines. The unlearning penalty is reduced by a factor of $\exp(-2\epsilon/(d+2))$ .

Significance and Claims

The paper claims to nearly resolve the open question regarding the minimax optimal excess risk for $\epsilon$ -unlearning in smooth strongly convex SCO.

Fundamental Limit: It establishes that the statistical cost of unlearning is not a fixed penalty but depends exponentially on the ratio of the unlearning budget to the model dimension.
Efficiency: The proposed algorithm demonstrates that it is possible to achieve high accuracy (close to the full-data ERM) while satisfying strict unlearning constraints, provided the privacy budget is sufficiently large relative to the dimension.
Utility vs. Privacy Trade-off: The work clarifies the trade-off between the "right to be forgotten" and model utility, showing that for high-dimensional models with sufficient privacy budget, unlearning need not come at the cost of discarding significant statistical information (as in retraining from scratch).

The authors note that their bounds for general SCO differ by a condition-number factor, leaving a gap for a fully sharp characterization beyond mean estimation. They also identify extending these results to nonconvex optimization and handling explicit storage/computational constraints as open directions for future work.