Source-linked AI summary
Remember What You Want to Forget: Algorithms for Machine Unlearning
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, Ananda Theertha Suresh
TL;DR
Machine unlearning asks how to delete requested training datapoints from a learned model while preserving generalization, under computation and storage constraints. The paper develops unlearning algorithms using stored statistics and shows improved deletion capacity for convex losses compared with differential privacy. It also identifies unresolved tightness and broader-scope questions.
Problem
The paper asks how to unlearn training datapoints while retaining accuracy on unseen data, rather than focusing only on empirical training loss, and while controlling computation and storage.
Method
The paper designs unlearning algorithms that use the learned model, deletion requests, and stored data statistics without requiring the training dataset during deletion.
Results
For convex losses, the algorithms can delete up to eO(n/d1/4) samples, a quadratic improvement in dimension dependence over the differential-privacy comparison.
Takeaways & Limitations
The results demonstrate a strict separation between differential privacy and machine unlearning for deletion capacity.
Takeaways & Limitations
The tight dependence of deletion capacity on d or n remains unresolved, and efficient methods for non-convex losses and online deletion remain future directions.
Abstract
from arXiv · showhide
We study the problem of unlearning datapoints from a learnt model. The learner first receives a dataset $S$ drawn i.i.d. from an unknown distribution, and outputs a model $\widehat{w}$ that performs well on unseen samples from the same distribution. However, at some point in the future, any training datapoint $z \in S$ can request to be unlearned, thus prompting the learner to modify its output model while still ensuring the same accuracy guarantees. We initiate a rigorous study of generalization in machine unlearning, where the goal is to perform well on previously unseen datapoints. Our focus is on both computational and storage complexity. For the setting of convex losses, we provide an unlearning algorithm that can unlearn up to $O(n/d^{1/4})$ samples, where $d$ is the problem dimension. In comparison, in general, differentially private learning (which implies unlearning) only guarantees deletion of $O(n/d^{1/2})$ samples. This demonstrates a novel separation between differential privacy and machine unlearning.
1 Introduction
Machine unlearning seeks resource-efficient deletion of training datapoints while preserving performance on unseen data. This paper studies generalization alongside computation and storage, and separates unlearning guarantees from differential privacy.
- Motivation: User-data deletion laws and model-extraction risks motivate removing requested datapoints from trained machine-learning systems.The paper notes that some regulations mandate deletion and that models may reveal training data.
- Motivation: Retraining from scratch is computationally expensive, while retaining complete datasets or many checkpoints can require prohibitive storage.Training may take weeks and use millions in resources; checkpoint storage scales with dataset size.
- Research question: The central question is how to design resource-efficient unlearning algorithms that generalize to previously unseen test data.Prior work focused on empirical training loss rather than test performance.
- Contributions: The paper studies unlearning under both computation and storage constraints, without requiring the training data during deletion.The algorithms instead support deletion without direct access to the training dataset.
- Contributions: Differential privacy provides a clean unlearning approach, but the paper establishes a strict separation between differential privacy and machine unlearning.The comparison treats DP-based methods as algorithms that ignore which particular samples are deleted.
- Results: For convex losses, the proposed algorithms delete up to eO(n/d1/4) samples, improving the dependence on d quadratically over the DP comparison.The result applies to both strongly convex and convex loss functions.
2 Preliminaries
The preliminaries define learning quality through population-risk excess and formalize unlearning using a model, deletion requests, and compact data statistics. They also define deletion capacity while highlighting the computational and storage costs of retraining.
- Learning: Learning minimizes population test loss using samples drawn independently from an unknown distribution, while empirical loss is optimized because the distribution is unavailable.The dataset contains n i.i.d. samples from D.
- Learning: The quality of a learning algorithm is measured by excess population risk relative to the best hypothesis in the class.This excess-risk notion also induces a sample-complexity measure.
- Learning: The paper fixes an excess-risk target of 0.01 for comparing algorithms, with standard convex-loss bounds whose hidden constants are dimension-independent.The hidden constant depends on properties such as the loss function’s Lipschitzness.
- Unlearning: An unlearning algorithm receives the learned model, deletion requests, and optional statistics T(S), but not necessarily the full training dataset.The statistics represent additional storage and may include empirical means, variances, or average gradients.
- Unlearning: The unlearning map outputs a new model from deleted samples, the original model, and stored statistics, with its definition comparing deletion against training on the remaining dataset.The observer should be unable to distinguish the two cases with high probability under the formal guarantee.
- Deletion capacity: Deletion capacity is the maximum number of samples that can be unlearned while maintaining excess population risk of 0.01.The expectation is over the sampled dataset and algorithm outputs.
- Complexity: The framework seeks high deletion capacity with storage independent of n, excluding full-dataset storage and aggressive checkpointing.Retraining from scratch requires storing the dataset and reading Ω(n − m) remaining samples, making it computationally expensive.
3 Our results
The paper shows that minimizing empirical loss can fail to preserve test performance after adversarial deletions, motivating resource-efficient unlearning algorithms with population-risk guarantees. For convex losses, its sample-aware algorithm improves deletion capacity over differential-privacy-based unlearning while using stored dataset statistics.
- Population risk vs empirical risk: Adversarial deletions can worsen test loss even when the updated model exactly minimizes empirical loss on the remaining data.In the mean-estimation example, deleting m points with value 1 shifts the empirical minimizer downward by m/n, away from the test-optimal parameter.
- Population risk vs empirical risk: Empirical-loss methods can delete up to n − 1 samples, but retaining test-loss guarantees imposes a non-trivial deletion-capacity limit.This limitation persists even when the unlearning algorithm has access to all undeleted samples.
- Strict separation between unlearning and differential privacy: Differential privacy provides a baseline unlearning strategy that ignores which samples are requested for deletion.The resulting DP-based guarantee motivates asking whether the dimension dependence can be improved using sample-aware techniques.
- Unlearning for convex loss functions: Sample-aware unlearning can bypass the DP dimension dependence for convex losses, deleting up to O(n/d1/4) samples while retaining test-loss performance.The algorithm is described for convex, Lipschitz, and Hessian-Lipschitz losses; its running time is O(d^ω) and its space complexity is O(d^2).
- Unlearning for convex loss functions: The convex-loss result separates unlearning from DP by a multiplicative Θ(d1/4) deletion-capacity gap.The paper compares O(n/d1/4) deletions for its unlearning algorithm with Θ(n/d1/2) guaranteed by DP, and reports at least quadratic improvements in dependence on ε and log(1/δ).
- Unlearning for convex loss functions: The algorithm stores additional dataset statistics independent of n and uses the requested samples during unlearning.This storage-and-use mechanism motivates the paper’s title, “Remember what you want to forget.”
4 Unlearning algorithms
The paper develops unlearning algorithms for strongly convex and convex losses that support generalization while reducing storage and deletion costs. The method updates the learned model using stored Hessian information, estimates the post-deletion minimizer, and adds calibrated noise.
- Learning algorithm: Asc minimizes empirical loss and stores the Hessian at the output point as data statistics T(S).The stored statistic uses O(d^2) memory, independent of n and m.
- Unlearning algorithm: The unlearning algorithm estimates the Hessian after deletion, removes deleted-point contributions, and perturbs the updated model with Gaussian noise.It receives the delete requests, the learned point, and T(S), without requiring the full training dataset.
- Technical insight: O(m^2/n^2) precision approximates the empirical minimizer after deleting m samples, enabling noise of scale σ ∝ O(m^2/n^2).This smaller noise scale underlies the improvement over differential privacy.
- Guarantees: The algorithms Asc and ¯Asc satisfy (ε, δ)-unlearning and provide excess-risk guarantees for learning and deletion outputs.The deletion guarantee yields a lower bound on the number of samples that can be removed while preserving a target excess risk.
- Complexity: O(d^ω) is the unlearning running time, independent of dataset size n; for diagonal-Hessian linear SVMs, learning takes O(nd) and unlearning O(d).Here ω ∈ [2, 2.38].
- Convex losses: For convex losses, the method reduces to the strongly convex setting by adding regularization.The resulting analysis is deferred to the appendix.
5 Conclusion
The conclusion frames the work as a study of population-risk generalization in machine unlearning rather than only empirical-risk minimization. It reports improved deletion capacity over differential privacy and identifies several open directions.
- Contribution: The paper studies machine unlearning with a focus on population risk minimization, contrasting prior work focused on empirical risk minimization.
- Result: For convex losses, the proposed algorithm improves deletion capacity by at least a quadratic factor in d over an out-of-the-box differentially private algorithm.
- Future work: The paper identifies information-theoretic lower bounds, efficient unlearning for finite or discrete hypothesis classes, non-convex losses, and online deletion as future directions.The present work considers batch deletion, with all requests arriving at the same time.
B.1 Proof of Theorem 1
The proof establishes a lower bound by reducing learning under squared loss to mean estimation and constructing nearby distributions whose means differ. An adversary deletes samples to make the remaining datasets difficult to distinguish.
- Hard distributions: Two distributions can have ℓ1 distance at most α while their means differ by at least α/2.The proof realizes this using shifted uniform distributions.
- Adversarial deletion: An adversary deletes at most 2nα samples so the retained dataset has a distribution based on the overlap of the two original distributions.The adversary is truncated after m deletions when needed.
- Proof setup: The proof uses W = [0, 1], Z = R, and squared loss f(w, z) = (w − z)^2 to construct an information-theoretic lower bound.
- Reduction to mean estimation: Under squared loss, bounding learning error reduces to estimating the mean of the underlying distribution.The population minimizer equals the distribution mean in this construction.
- Lower-bound argument: The unlearner must perform well on either distribution despite receiving datasets made similar through deletion.The proof allows the unlearner access to the entire sample set, strengthening the lower-bound setting.
- Consequence: For δ ≤ 0.005, ε ≤ 1, and m ≥ 100, achieving excess risk below 0.01 requires m ≤ c_ε n, where c_ε < 1.
B.2 Proof of Lemma 1
The proof derives a differentially private learning-and-unlearning pair by returning the private model unchanged after deletion. Group privacy then supplies the unlearning guarantee and deletion-capacity bound.
- Construction: The construction uses a DP algorithm private for datasets with edit distance m and an unlearning algorithm that returns the input model unchanged.Because no data statistics are needed, T(S) = ∅.
- Guarantee: The learning guarantee combined with differential privacy’s group-privacy property establishes the required privacy relation for m deletions.
- Unlearning guarantee: The resulting pair (A, ¯A) is (ε, δ)-unlearning for deletion sets of size m.
- Deletion capacity: The bound on the private learner’s excess risk yields a lower bound on deletion capacity while keeping excess risk at γ = 0.01.
B.3 Proof of Theorem 2
The proof treats strongly convex and convex losses separately, using their respective learning and unlearning guarantees to establish deletion-capacity lower bounds while preserving excess risk γ = 0.01.
- Strongly convex loss setting: Strongly convex losses use Asc and ¯Asc, whose guarantees establish (ε, δ)-unlearning.The algorithms are specified in Algorithms 2 and 1, respectively.
- Strongly convex loss setting: The strongly convex excess-risk bound implies deletion of at least a stated number of samples while maintaining γ = 0.01.The constant c depends on M, L, and λ.
- Convex loss setting: Convex losses use Ac and ¯Ac, with λ selected as in (25), and these algorithms satisfy (ε, δ)-unlearning.The algorithms are specified in Algorithms 3 and 4, respectively.
- Convex loss setting: The convex excess-risk bound likewise implies deletion of at least a stated number of samples while maintaining γ = 0.01.The constant c depends on M, L, and B.
C.1 Proof of Lemma 3
The lemma compares regularized objectives before and after deletions, then uses strong convexity, smoothness, and Lipschitzness to bound the distance between their minimizers.
- Conclusion: The resulting minimizer-distance bound is ∥bw − bw′∥ ≤ 2mL.This is obtained by applying Lemma 6 after the preceding inequalities.
- Objective comparison: The proof defines bF1 and bF2 over the original dataset and ¯S := S \ U, with bw and bw′ as their respective minimizers.This establishes the two optimization problems being compared.
- Objective comparison: The comparison uses the minimizer property of bw′, L-Lipschitzness of f, and λ-strong convexity of bF1.These properties produce the intermediate inequality relating the two minimizers.
- Taylor expansion: A Taylor expansion of ∇bF2 around bw uses the Hessian-Lipschitz constant M and the stationarity of bw′.Because bw′ minimizes bF2, ∇bF2(bw′) = 0.
- Taylor expansion: Strong convexity gives ∥∇2 bF2(bw)v∥ ≥ λ∥v∥, which is combined with the preceding relations.The vector v is introduced to connect the gradient comparison to the minimizer distance.
C.2 Proof of Theorem 3
The theorem combines learning and unlearning performance bounds with a Gaussian-noise mechanism to provide excess-risk and (ε, δ)-unlearning guarantees for strongly convex losses.
- Setup: The strongly convex setting uses Asc for learning and ¯Asc for unlearning, with data sampled independently from D and w* minimizing population loss F.The proof proceeds through separate learning and unlearning lemmas.
- Learning guarantee: Lemma 8 supplies the learning guarantee for the empirical-risk-minimizer output bw.The guarantee is stated for S ∼ D^n.
- Unlearning performance: Lemma 9 bounds the performance of the unlearning output ew for any deletion set U of m requests.The expectation is over the dataset S and Gaussian noise ν.
- Unlearning performance: The excess-risk analysis decomposes the population-loss difference and uses Lipschitzness, strong convexity, Jensen’s inequality, and Gaussian-noise properties.The final guarantee follows after substituting the noise scale and using n = Ω(m).
- Unlearning guarantee: The algorithms satisfy two-sided probability inequalities establishing (ε, δ)-unlearning for every measurable output set W.The proof follows the Gaussian-mechanism differential-privacy argument.
D Unlearning algorithms for convex loss function
For convex losses, the paper reduces the problem to the strongly convex case through regularization, then proves learning, unlearning, and generalization guarantees under convexity and smoothness assumptions.
- Algorithm construction: Convex-loss algorithms invoke the strongly convex algorithms on a regularized loss ef with an appropriate λ.Algorithms 3 and 4 provide the corresponding learning and unlearning procedures.
- Assumptions: The analysis assumes convex, L-Lipschitz, M-Hessian-Lipschitz losses and an optimal w* satisfying ∥w*∥ ≤ B.These are stated as Assumptions 2 and 3.
- Algorithm construction: The regularized loss is λ-strongly convex, (L + λ∥w∥)-Lipschitz, (H + λ)-smooth, and M-Hessian Lipschitz.These properties hold at w, and Assumption 1 applies when ∥w∥ ≤ L/λ.
- Theorem 4: Theorem 4 guarantees learning performance for bw, unlearning performance for ew after m deletions, and (ε, δ)-unlearning.The guarantees apply to S ∼ D^n under the stated assumptions.
- Corollaries: Without unlearning requests, λ = L/B√n yields a learning rate that is tight for Lipschitz convex losses.The tightness statement is attributed to Bubeck (2014, Theorem 6.1).
- Corollaries: With m deletion requests, Corollary 2 selects λ to control the performance of both the learning output bh and the unlearning output ew.Substitution into Theorem 4 gives the corresponding joint guarantee.
D.1 Proof of Theorem 4
Theorem 4 follows from separate performance and forgetting guarantees for the algorithms Ac and ¯Ac. The proof bounds the relevant parameter domain, derives performance guarantees, and establishes two-sided (ε, δ)-forgetting inequalities.
- Performance guarantees: Lemma 11 provides a performance guarantee for the point bw returned by Ac on datasets S ∼ D^n.The proof relates empirical and population objectives using the minimizers of the regularized and population losses.
- Performance guarantees: ∥bw∥≤L/λ bounds the empirical minimizer’s domain, enabling a 2L-Lipschitz bound for ef.The proof restricts attention to W := {w | ∥w∥≤L/λ} before applying a generalization lemma.
- Performance guarantees: Lemma 12 provides a performance guarantee for the point ew returned by ¯Ac after processing m delete requests.The proof uses the L-Lipschitzness of the loss and population loss, together with the procedure ¯Ac’s computation via ¯Asc.
- Forgetting guarantee: Algorithms Ac and ¯Ac satisfy two reciprocal (ε, δ)-forgetting inequalities comparing deletion processing with retraining on S \ U.For every measurable set W, each direction bounds one output probability by e^ε times the other plus δ.
- Proof structure: Theorem 4 is proved by applying Lemmas 11, 12, and 13 to its separate claims.Each lemma supplies the corresponding performance or forgetting statement.