Remember What You Want to Forget — Reading Notes

Easy Learn, Easy Go.

There’s been a lot of focus on models that can do everything. Early ML researchers (and some holdouts) used to throw every type of data at a model in the hopes that the model would find something useful.

This is fine for massive weather models or economic forecasts, but it doesn’t work for production machine learning. Most notably because production models work with sensitive people data.

Courts have been catching on to this. The EU passed the largest and most comprehensive data protection law (aptly names the General Data Protection Regulations, GDPR) over a large portion of digital subscribers. California isn’t far behind. Models not only need to be careful with sensitive data, but unlearn it on command.

This was the state of things when Sekhari et al. published their paper. Antonio Ginart theorized about data deletion as a purely algorithmic problem, but Sekhari brings the theoretical backing to his claims. Sample complexities, closed-form deletion capacities, and experimental results make for a very convincing argument for privacy-preserving ML.

Let’s get into it.

Why We Can’t Just Hit Delete.

Ginart et al. and Sekhari et al. both propose a naive unlearning solution, which is to just delete the model entirely. A new model can be retrained on the sanitized dataset and legal obligations are fulfilled.

But this poses some pretty unexpected problems. Most notably, deleting someone’s data actually leaks their information. Chen et al. show that adversaries can easily derive the influence of an unlearned datapoint by comparing the model before and after deletion.

There’s also the less compelling implementation barriers. Pulling a model for every data deletion request is deeply infeasible, and consumes large amounts of energy. The field was facing a bind: we needed algorithms that could unlearn without pulling the model from production.

There’s been a few solutions proposed:

First Option: Never Learn the Data in the First Place.

This sounds counterintuitive, but that’s just a show of Dwork’s innovation when she theorized differential privacy.

It’s a preventative measure applied to any training set for a model. The data queried is injected with just enough noise that the training data is just indistinguishable enough from the original to avoid a lawsuit. And so a company could store a person’s data, use it for simulating new (marginally unrecognizable) data, and still protect their users.

The only issue is that this noise adds up. Anonymizing a single user’s data means spreading their noise to every other observation in the sample. But when this is done for every data point, then the model performance dips. This is especially the case when we need exact unlearning. The training resembles less and less the true population until all meaningful signal is masked. Sekhari actually proves a fundamental limit on how well a model can learn without actually seeing real data.

It also happens that approximate differential privacy is a bit of a gamble. There is a nonzero probability that the randomized dataset is identical to the original dataset. In this case, the entire dataset is exposed.

So the field needed alternatives.

Second Option: Restrict the Influence of Every Observation

Bourtole et al. had a different approach for exact unlearning. Their SISA model almost unlearns data perfectly by partitioning the training set into nonoverlapping sets and training different model segments on different training sets.

The intuition is strong. If User A’s data is only used to train one branch of a decision tree, then that data is easily unlearned by removing that segment of the model. No other part of the model was trained on the data, and so the only cost is that required to retrain the branch.

But this exact unlearning comes at a cost. First, we have to keep track of every single observation used for training. User A’s data deletion request can only be fulfilled if I know which branch of the model had seen the data. For online learning, this is something like keeping a potentially unbounded training set in-memory.

There’s also a more fundamental problem: the data is only seen by one part of the model. Its performance is bounded by default because the model undergoes less training, and so such methods are limited in use.

Third Option: Unlearning to a Strong Degree

Sekhari et al. formalize $(\epsilon, \delta)$-certified unlearning as an alternative. The method allows practitioners to train their models and only add noise to the model when a deletion is actually performed. Sekhari proves regret bounds 6x tighter than DP-style unlearning by using a standard trick from online convex optimization theory: a Newton Update.

The Newton update addresses the shortcomings of prior methods. It allows the engineer to set a threshold for unlearning, with a lower threshold experiencing a smaller amount of deletion noise. And because the operation works purely on gradient information, the model only keeps a set of gradients in-memory.

It also raises the bar on model quality. His unlearning definition requires strong model inference not only for training data that the model has seen, but the population data it has yet to learn. In other words: models need to unlearn without any loss of future predictive accuracy.

It also opens the door for more efficient unlearning methods. A memory constraint that grows linearly with the sample size is unideal, as is the $\mathcal{O}(d^2)$ Hessian inversion, but methods like Nocedal’s L-BFGS optimization allows for efficient sketching with bounded error terms. Indeed, Qiao et al. implement a Hessian sketch unlearning method that unlearns an observation in constant time.

And so Sekhari’s definition opens up doors. We have a new toolbox to approach unlearning and build lean, secure models. We also have a formal definition of unlearning that raises the bar on privacy and performance.

The next feasible step is to scale it to production: build a model that learns and unlearns on the fly with minimal performance loss.

We won’t spoil the surprise, but we’re doing just that. Stay tuned.

Read Along with Us.

Chen, Min, et al. “When Machine Unlearning Jeopardizes Privacy.” arXiv:2005.02205, arXiv, 14 Sept. 2021. arXiv.org, https://doi.org/10.48550/arXiv.2005.02205. Qiao, Xinbao, et al. “Hessian-Free Online Certified Unlearning.” arXiv:2404.01712, arXiv, 6 Feb. 2025. arXiv.org, https://doi.org/10.48550/arXiv.2404.01712. Sekhari, Ayush, et al. “Remember What You Want to Forget: Algorithms for Machine Unlearning.” arXiv:2103.03279, arXiv, 22 July 2021. arXiv.org, https://doi.org/10.48550/arXiv.2103.03279. Prudente, L. F., and D. R. Souza. “Global Convergence of a BFGS-Type Algorithm for Nonconvex Multiobjective Optimization Problems.” arXiv:2307.08429, arXiv, 11 Apr. 2024. arXiv.org, https://doi.org/10.48550/arXiv.2307.08429.