On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning

Anvith Thudi; Hengrui Jia; Ilia Shumailov; Nicolas Papernot

Source-linked AI summary

On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning

Anvith Thudi, Hengrui Jia, Ilia Shumailov, Nicolas Papernot

arXiv:2110.11891v2Oct 22, 2021cs.LGcs.AIcs.CRstat.ML

TL;DR

Machine unlearning lacks a reliable definition when based on final model parameters or similarity to retraining without deleted data. The paper analyzes dataset forgeability and verification logs, showing that both approximate and exact approaches can be undermined. It concludes that only auditable learning and unlearning algorithms provide a defensible basis for unlearning claims.

Problem
Machine unlearning is important for removing memorized user data, but parameter-based definitions and retraining-based verification may not uniquely establish that a point was forgotten.
Method
The paper analyzes whether different datasets and training trajectories can yield equivalent updates or models, and formalizes forgeability alongside Proof-of-Learning-based verification.
Results
The paper shows that forgeable datasets can produce indistinguishable models, while even a given training trajectory cannot formally prove that certain data points were absent.
Takeaways & Limitations
Unlearning is well-defined only at the algorithmic level, so auditable claims must rely on inspecting procedures designed for external scrutiny.
Takeaways & Limitations
The practical per-step error ε needed for Proof-of-Learning-based definitions is case dependent and remains an active research question.

Abstract

from arXiv · show

Machine unlearning, i.e. having a model forget about some of its training data, has become increasingly more important as privacy legislation promotes variants of the right-to-be-forgotten. In the context of deep learning, approaches for machine unlearning are broadly categorized into two classes: exact unlearning methods, where an entity has formally removed the data point's impact on the model by retraining the model from scratch, and approximate unlearning, where an entity approximates the model parameters one would obtain by exact unlearning to save on compute costs. In this paper, we first show that the definition that underlies approximate unlearning, which seeks to prove the approximately unlearned model is close to an exactly retrained model, is incorrect because one can obtain the same model using different datasets. Thus one could unlearn without modifying the model at all. We then turn to exact unlearning approaches and ask how to verify their claims of unlearning. Our results show that even for a given training trajectory one cannot formally prove the absence of certain data points used during training. We thus conclude that unlearning is only well-defined at the algorithmic level, where an entity's only possible auditable claim to unlearning is that they used a particular algorithm designed to allow for external scrutiny during an audit.

1 Introduction

Machine unlearning addresses the need to remove a user's data impact from a model, but its precise definition remains unresolved. The paper argues that parameter similarity and retraining-based reasoning fail to define approximate unlearning reliably.

Motivation: Machine unlearning seeks to remove a user's data impact after authorization to use that data is withdrawn.The motivation is tied to the right-to-be-forgotten and models' ability to memorize training data.
Existing definitions: Exact unlearning retrains from scratch without the target point, whereas approximate unlearning modifies parameters to approximate that retrained model.Exact retraining is computationally expensive, motivating parameter-update methods.
Approximate unlearning: Two non-overlapping datasets can produce arbitrarily similar, or identically represented, model parameters, so parameter space does not establish which dataset was learned from.The paper instead identifies optimization trajectories as the relevant source of dataset attribution.
Approximate unlearning: Different minibatches can yield arbitrarily similar average gradients, allowing target-containing updates to be replaced while preserving the resulting model update.This creates a route to claims of unlearning without changing the model's effective computation.
Contribution: Forgeability makes learned and supposedly unlearned models indistinguishable when alternative datasets reproduce the same updates, potentially reducing unlearning cost to zero.The paper reports this possibility for standard models and datasets in experiments.
Conclusion: The paper concludes that unlearning must be defined and audited at the algorithmic level rather than inferred from final model parameters.Auditing must inspect whether the learning and unlearning procedures provide the required guarantees.

2 Background

The paper situates unlearning within supervised machine learning, optimization by minibatch updates, and the distinction between exact and approximate methods. It then explains why Proof-of-Learning plausibility does not automatically establish unlearning correctness.

2.1 Machine Learning: Supervised learning uses labeled examples (x_i,y_i) to train a parameterized model that predicts labels for new inputs.The model is optimized through a loss function measuring classification performance.
2.1 Machine Learning: Mean-sampler updates average the individual updates from minibatches, with minibatch stochastic gradient descent as a central example.The paper treats minibatches as the data units used by its update-rule analysis.
2.2 Machine Unlearning: Exact unlearning discards the old model and retrains on a dataset with the requested points removed, while methods such as SISA reduce retraining cost through dataset partitioning.Full retraining can be unaffordable for large datasets and deep neural networks.
2.2 Machine Unlearning: Approximate unlearning directly modifies trained parameters to imitate a model trained without the target points, often by comparing against exactly unlearned parameters.Its validity therefore depends on retraining being a well-defined reference.
2.3 Proof-of-Learning: Proof-of-Learning records training checkpoints and data so a verifier can reproduce alleged computations and assess log plausibility.Verification checks whether intermediate checkpoints can be reproduced within an error threshold.
2.4 Related Work: The paper's forging approach searches for alternative minibatches that produce the same or similar parameter updates, extending prior observations about SGD randomness and data ordering.The construction assumes access to a different dataset from the original training data.

3 Revisiting Machine Unlearning

The paper revisits both parameter-level and algorithm-level definitions of unlearning under a white-box threat model. It shows that forging can defeat parameter comparisons and bypass proposed log-based verification.

3 Revisiting Machine Unlearning: The threat model gives the adversarial trainer all intermediate checkpoints, training data, and hyperparameters, enabling attempts to prove unlearning without changing the original model.This is a white-box setting in which the trainer possesses the information generated during training.
3.1 When is Unlearning Achieved?: Existing parameter-level definitions equate unlearning with reaching parameters obtainable by retraining without the target points.Some definitions additionally require reproducing the distribution associated with such retraining.
3.1 When is Unlearning Achieved?: Forgeability supplies an alternative dataset that can reproduce the same model parameters, making parameter-space unlearning achievable without modifying the model.The paper presents this as a self-contradiction in parameter-based definitions and an invalidation of approximate approaches.
3.2 Proof-of-Unlearning: Exact unlearning motivates Proof-of-Unlearning because retraining-based correctness appears to require evidence that the target points were absent from the new training run.The proposed verification reasoning imports the plausibility logic of Proof-of-Learning.
3.2 Proof-of-Unlearning: Proof-of-Learning logs can be unique for ordinary training because errors accumulate, but an unlearning adversary already has the original log and may need to fake only a few steps.This difference between the PoL and PoUL threat models undermines the verification argument.
3.2 Proof-of-Unlearning: A forging map can swap each occurrence of a target point with another point while preserving updates closely enough for the altered log to pass verification.The paper identifies this map as the formal mechanism behind bypassing algorithm-level verification.

4 Introducing Forging

The paper introduces forging maps to formalize when different datasets can yield the same training trajectories and models. This framework shows why parameter-level unlearning verification fails and motivates algorithm-level verification.

Defining Feasibility and PoL: A feasible model is defined by a proof-of-learning log: a sequence of dataset points and checkpoints that follows a fixed update rule to the final weights.The log is treated as both necessary and sufficient for claiming that a model could come from a dataset.
Defining Valid Logs: A valid log permits per-step reproduction error ε, accounting for numerical imprecision when a verifier reproduces training updates.The authors note that the practically appropriate value of ε is case dependent and remains an active research question.
Defining the Forging Map and Forgeability: A forging map preserves model parameters while replacing data points from dataset D with points from D′ whose updates remain within ε of the original trajectory.When maps exist in both directions, the datasets are called forgeable.
Forgeable and Models: For ε = 0, forgeability is an equivalence relation, and forgeable datasets produce exactly the same set of models under the update rule.Theorem 1 characterizes the equivalence classes by equality of the attainable model sets.
Consequence to Defining Unlearning: If a forging map exists between a dataset and that dataset with the target point removed, approximate unlearning can be achieved without changing the model parameters.The resulting log omits the target point while retaining the same final parameters, making the approximate definition ill-defined.
Consequence to Defining Unlearning: Forging also allows a previously trained model to receive a new log that appears to support exact unlearning, so weights cannot universally verify whether a point influenced training.The paper therefore argues that unlearning must be defined and audited through the learning and unlearning algorithms rather than their output parameters.

5 Methods for Forging

The paper develops several forging constructions showing that distinct datasets can produce indistinguishable or arbitrarily close training updates, including for minibatch SGD. These results undermine parameter- or log-based definitions of unlearning and motivate algorithm-level auditing.

5 Methods for Forging: Forgeability allows one dataset to replace another while preserving model updates up to a predefined error.The paper studies forging maps that exchange data points while keeping computed updates identical or nearly identical.
5 Methods for Forging: Lipschitz update functions make similar data points interchangeable, yielding forgeable datasets for smaller verification errors.Under the stated Lipschitz condition, replacing each point with a nearby point produces a corresponding forgeable dataset.
5 Methods for Forging: For mean-sampler updates over i.i.d. minibatches, increasing minibatch size raises the probability that independently sampled datasets forge one another.The probability approaches one as minibatch size grows, under the theorem’s finite-log and bounded-variance assumptions.
5 Methods for Forging: When the adversary can choose minibatch size and sample indefinitely, a disjoint dataset can forge almost every finite dataset for any ε > 0.The result requires freedom over minibatch size and continued sampling from the underlying distribution.
5.4 Consequences of Theorem 3 for Unlearning of minibatch SGD: Consequently, unlearning is not well-defined for minibatch SGD because the same training log can represent training both with and without a target point.The paper therefore argues that auditing must constrain and verify the training and unlearning algorithms rather than inspect only their outputs.

6 An Instantiation of a Forging Attack

The attack constructs forging maps that replace the point to be unlearned while reproducing training updates closely enough to evade PoL verification. Experiments show low verification error is practical, especially with large minibatches, while smaller datasets and greedy point selection remain viable but less effective.

6.1 Threat Model: The attack targets a PoL by replacing x∗ with another data point while preserving the logged training trajectory closely enough for verification.The threat model assumes white-box access to checkpoints, data points, and hyperparameters.
6.2 Forging Algorithms: The forging algorithm samples n points, forms M candidate minibatches, and selects the minibatch minimizing the distance to the observed update.Ignoring sorting overhead, one forging step costs M gradient steps; forgetting µ points after N epochs costs µNM gradient steps.
6.3 Results: Larger minibatches significantly reduce verification error, reaching ≈10^-5 for large minibatch sizes, whereas increasing n yields only a modest decrease around ≈10^-6.The minibatch-size trend is consistent with an expected 1/b dependence.
6.3 Results: Greedy individual-point selection improves verification error only slightly and converges after fewer than 10 updates.Its effect is much smaller than the effect of increasing minibatch size.
6.3 Results: Fixed smaller sets still achieve error less than 10^-4, despite using 1/60 the size of the larger datasets.The authors present these LeNet5-on-MNIST experiments as initial results and leave broader domains for future work.

7 Discussion

The discussion argues that forging exposes limits of data-level attribution and motivates algorithm-level verification, while identifying extensions and practical constraints for future work.

7 Discussion: Forging creates plausible deniability about whether a particular point was used, and this likelihood increases with batch size.The authors relate this to convergence toward the mean induced by increasing batch size, while distinguishing it from differential privacy because no noise is added.
7 Discussion: Further constraining logs or training appears insufficient to prevent forged logs, while verifiable computing still requires information-flow controls and provenance requirements.The paper presents these as promising directions whose practical adequacy remains for future work.
7 Discussion: Greedy selection of individual points yields only slight improvement, with gains tending to converge after fewer than 10 updates.The experiment updates one point at a time instead of substituting an entire minibatch.
7 Discussion: The forging framework may generalize beyond minibatch SGD, but its dataset-distance interpretation lacks a proved triangle inequality and depends on a fixed model architecture.The authors also note that their forging maps cannot generally be composed because input and output error thresholds differ.
7 Discussion: Forging from fixed smaller sets of 1000 samples still achieves verification error below 10^-4.This result is reported for forging with samples from a smaller dataset across the epoch where forging occurs.
7 Discussion: Auditing exact unlearning may require algorithm-level techniques such as verifiable training, although verification could be too costly for ordinary users and may need a trusted regulator.The discussion frames efficient assurance mechanisms as an open requirement for future work.
7 Discussion: Because minibatches producing updates are not unique, model failures, unfairness, and good performance cannot be exclusively attributed to particular data without ruling out forging examples.The same framework may also support dataset distillation by identifying smaller datasets yielding similar-performance models under suitable restrictions.

8 Conclusions

The conclusion says the findings expose faults in current unlearning definitions rather than ending progress, requiring revised definitions and potentially stronger training-process restrictions.

8 Conclusions: Current unlearning definitions have faults, so future work must reconsider whether training without the data point is well-defined and may add restrictions against forging.The paper explicitly characterizes this as redefining unlearning rather than abandoning progress.

A Table of Notations

The notation table defines symbols for datasets, model parameters, optimization, probability, and forging-log quantities used throughout the paper.

A Table of Notations: The notation includes D, D′, and D̃ for datasets; x_i for an input; y_i for its label; and X for the data space.It also defines c as the number of classes and x*removed as a dataset with removed points.
A Table of Notations: The notation includes w for model parameters, W for parameter space, w_0 for initialization parameters, and w_t for parameters after t updates.M_w denotes the supervised machine-learning model, while N denotes parameter-space dimensionality.
A Table of Notations: The table defines g as the update-rule function, d as a distance metric, ε as an error tolerance, and Ball_ε(w) as a parameter-space distance ball.It also records D as a dataset distribution, μ as the mean of g(w,x), and σ^2 as the covariance trace.
A Table of Notations: For logging and forging, α denotes the number of PoL logs, m the longest PoL-log length, β_D the minibatch size needed to forge dataset D, and P probability.The table also defines n as the number of minibatches in a dataset.