On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning

• Exact unlearning retrains from scratch without the target point, while approximate unlearning modifies parameters in a few updates to approach a model that never learned that point.Exact retraining is generally computationally expensive, though it can be made more efficient to some extent [2]; approximate methods define success in parameter space [10] [11] [12] [13].Source: §1 · p. 1
• Similar or identical model parameters can arise from non-overlapping datasets, so parameter proximity cannot establish whether a model learned from or unlearned a particular dataset.The paper argues that what matters is the optimization trajectory by which parameters were obtained, not the parameter point alone.Source: §1 · p. 1
• Different minibatches can yield arbitrarily similar average gradients, allowing training steps involving a target point to be replaced while preserving the gradient computation’s outcome.The paper attributes this observation about similar gradient-descent steps to Shumailov et al. [22].Source: §1 · pp. 1–2
• Experiments show forgeability for standard models and datasets: points can be replaced while keeping updates identical up to a predefined error, enabling indistinguishable learned and unlearned models at no cost.Forgeability is defined as replacing points from one dataset with points from another while keeping model updates identical up to a minimal error.Source: §1 · p. 2
• Unlearning can only be defined through learning and unlearning algorithms, whose properties must remove the point’s effect and whose correct implementation must be supported by auditable evidence.The paper calls for external scrutiny, such as audits, and proposes verifiable computation as a promising direction; its algorithm-level framing is analogous to Dwork et al.’s differential privacy work.Source: §1 · p. 2

2.1 Machine Learning

• In supervised learning, a model predicts labels from labeled examples by iteratively updating parameters to reduce a loss, often using minibatch SGD.The paper calls updates that average per-example updates over minibatches mean-samplers.Source: §2.1 · p. 2

2.2 Machine Unlearning

• Exact unlearning retrains on data with requested points removed, while approximate unlearning modifies parameters to mimic that result more cheaply.Exact retraining can be costly; SISA [2] reduces retraining by partitioning data into shards, while Amnesiac Machine Learning [12] subtracts logged updates. Approximate-unlearning evaluations compare membership-inference behavior or parameter similarity to exactly unlearned models, but their claims depend on retraining being well-defined.Source: §2.2 · p. 3

2.3 Proof of Learning

• Proof-of-Learning logs model checkpoints, training data points, and update information so a verifier can reproduce and check training steps.Verification accepts a step when its parameter-distance error is below a threshold accounting for hardware floating-point noise; this establishes plausibility, not exact computation.Source: §2.3 · pp. 3–4

2.4 Data Ordering Attack

• Building on Shumailov et al. [22], the paper’s forging approach searches a different dataset for minibatches that produce the same or a similar parameter update.Shumailov et al. [22] showed that data ordering can alter SGD training dynamics, including by making a step approximately compute a desired gradient.Source: §2.4 · p. 4

3.1 When is Unlearning Achieved?

• The threat model gives the adversarial trainer access to all training checkpoints, data points, and hyperparameters.The trainer seeks to convince a verifier they retrained without specified points, without changing the original model.Source: §3.1 · p. 4
• Parameter-space unlearning fails under forging: the same parameters can be obtained with a dataset omitting the target, so no model change may be needed.This undermines definitions that equate unlearning with parameters reachable by retraining without the data point and invalidates approximate unlearning approaches.Source: §3.1 · pp. 4–5

3.2 A Strawman for an Auditable Approach to Unlearning: Proof-of-Unlearning

• Because forging can bypass PoUL, meaningful unlearning claims require algorithm-level definitions that support external scrutiny.The paper characterizes the presented PoUL approach as insufficient for auditable claims.Source: §3.2 · p. 5
• Proof-of-Unlearning would verify a retraining log whose minibatches omit the target, but the model owner already has the original log and may need to fake only a few plausible steps.The proposed approach adapts proof-of-learning, which relies on a training log to attest that updates did not use the data point.Source: §3.2 · p. 5
• A forging map can replace each target occurrence with another point yielding the same update, leaving checkpoints unchanged and producing a valid PoUL without retraining.If such a map exists for every possible original-data training log, no checkpoint sequence alone can determine whether the owner retrained or merely applied the mapping.Source: §3.2 · p. 5

4 Introducing Forging

• A forging map preserves parameter checkpoints while replacing logged data points, enabling the framework to characterize datasets that yield equivalent training trajectories.The section introduces forging to formalize unlearning and notes that the framework may also inform other machine-learning contexts.Source: §4 · p. 6

4.1 Defining Forgeability and Forging Map B

• Feasibility is defined by a PoL log, and a forging map replaces its data points while preserving checkpoints and allowing per-step error ε.The paper treats a PoL log as necessary and sufficient for a model to be feasible from a dataset; ε accommodates numerical imprecision, but its practical size is case-dependent. The defined map takes zero-error logs to ε-error logs and is not composable unless ε = 0.Source: §4.1 · p. 6

4.2 Forgeable and Models

• With zero-error forgeability, D and D′ yield the same set of models, and are forgeable if and only if they produce the same parameter sequences.The paper identifies zero-error forgeability as an equivalence relation on datasets.Source: §4.2 · p. 7

4.3 Consequence to Defining Unlearning.

• If D can forge D without x*, the unchanged model meets the paper’s approximate-unlearning definition, making that definition ill-defined.Forging replaces the logged data points with points from D without x* while preserving the parameter checkpoints and a valid log.Source: §4.3 · p. 7
• Forging also invalidates proof-of-unlearning and shows that unlearning cannot be universally verified from model weights, so verification must focus on the process or algorithm.The paper says certified unlearning’s model-level guarantees need algorithm-level verification, while proposed exact-unlearning audits should enable external scrutiny.Source: §4.3 · p. 8

5.1 Forgeability for Similar Datasets

• If the update function is Lipschitz in its data point across valid logs, datasets with sufficiently similar points are forgeable with a smaller error threshold.Lemma 3 formalizes this condition for valid zero-error logs and parameter-space balls of radius ε.Source: §5.1 · pp. 8–9

5.2 Forgeability of Densely Packed Updates

• If every update for any parameter and data point is within ε of an update from D′, then D′ forges datasets whose valid logs stay within the specified parameter set.A sufficiently large, diverse D′ could forge an entire class of datasets, but constructing such a universal forger may be difficult and may require specifying the update function.Source: §5.2 · p. 9

5.3 Forgeability for Mean Sampling

• For i.i.d. minibatch datasets under mean-sampler updates, Theorem 2 bounds the probability that D′ forges D in ℓ2 within 2ε using minibatch size, variance, dataset size, and log-length limits.The theorem assumes D′ has n minibatches, there are α valid logs, and each log has length at most m; the probability of mutual forging approaches one as batch size grows.Source: §5.3 · p. 10
• With freedom to choose minibatch size and sample indefinitely from D, an adversary can forge almost every finite dataset with a finite disjoint dataset for every ε > 0.The result assumes points in D have zero probability of being drawn; the authors also note that increasing minibatch size raises the probability of finding a forgery.Source: §5.3 · p. 10

5.4 Consequences of Theorem 3 for Unlearning of minibatch SGD

• Minibatch SGD unlearning is not well-defined over logs or models because the same training log can reflect either omitting a data point or using it and forging the log.The authors argue that meaningful audits therefore require constraints on the training process and external verification that the prescribed process was used; unlearning should be defined algorithmically.Source: §5.4 · pp. 10–11

6.3 Results

• Verification error fell below 10^-4, reaching approximately 10^-6 before hardware noise for suitable large minibatches, demonstrating practical forging at very low thresholds.The authors note that improved forging and PoL verification could create an arms race without other constraints to rule out forging.Source: §6 · p. 11, §6.3 · p. 12

6.1 Threat Model

• The threat model assumes access to a PoL’s model and training dataset, and replaces steps using x∗ with other steps to forge a map to D′ = D\x∗.Experiments use LeNet5 trained on MNIST, with SGD and fixed learning rate η = 0.01; results are initial findings.Source: §6.1 · p. 11

6.2 Attack Description

• The attack samples candidate minibatches from D excluding x∗, then chooses the batch whose update most closely matches the original; its cost is µNM gradient steps for µ forgotten points over N epochs.The method follows the data-ordering attack of Shumailov et al. [22]. Forging with a smaller subset of size n would mean using only n points to forge |D|−n points.Source: §6.2 · p. 11, §6 · p. 11

6.3 Results

• With minibatch size fixed at 1000, verification error stayed around 10^-6 across sample counts, while larger minibatches reduced error by several magnitudes to approximately 10^-5.The sample-count trend was modest; increasing minibatch size had a much larger effect. Figure 1 shows error across 100 trials with randomized checkpoints and x∗.Source: §6.3 · p. 12, Figure 1 · p. 12
• Greedy replacement of individual points slightly improved verification error, but the improvement tended to converge after fewer than 10 updates and was small relative to the minibatch-size effect.The reported improvement is relative to the error before greedy updates.Source: §6.3 · p. 12
• On fixed sets of 1000 samples, forging still achieved verification error below 10^-4, despite using one-sixtieth the size of the larger datasets.This was higher than the approximately 10^-6 achieved with larger datasets; the authors suggest smaller datasets may be equivalent in the limit of large minibatches, leaving this for future work.Source: §6.3 · p. 12

7.1 Relation to Information Leakage

• Plausible deniability about training on a point increases with batch size, reflecting convergence toward an average run; this differs from differential privacy.The authors suggest that forging may indicate stability to the underlying distribution and less leakage about specific points, while leaving privacy implications for future work.Source: §7.1 · p. 12

7.2 On the Need for Verifiable Training and Unlearning Algorithms

• Immutable logs or one-time-training constraints may not prevent forged logs; verifiable computing needs controls on information flow and data provenance.The authors describe the forging framework as potentially useful for proving that forging does not exist under further conditions.Source: §7.2 · p. 13

7.3 Extending the Forging Framework

• The forging framework extends beyond minibatch SGD to broader machine-learning study, and greedy point-level updates offer only marginal benefit while smaller-dataset forging keeps error below 10^-4.The figure captions report only a marginal benefit from increasing greedy updates and verification error below 10^-4 when forging with samples from a smaller dataset.Source: §7.3 · p. 13, Figure 3 · p. 13, Figure 4 · p. 14
• An ε-based distance between datasets is a possible extension, but its triangle inequality remains unproved; how forgeable classes vary with model architecture is also open.The proposed distance is defined via forgeability modulo the ε = 0 equivalence class; the paper gives neither a proof nor a counterexample for the triangle inequality.Source: §7.3 · p. 13

7.4 Importance to ML Governance

• When forging is possible, proof-of-learning logs cannot audit exact unlearning; regulators may instead need algorithm-level auditing, such as verifiable training.A forging map can connect a dataset to itself with the data to be unlearned removed, so the log alone cannot establish the claim.Source: §7.4 · p. 14
• Forging makes data attribution ill-defined for model failures, fairness, and performance unless training rules it out; ε = 0 classes may inform dataset distillation.The paper argues that unfairness cannot be attributed to data alone without ruling out forging, and that similar-performance datasets in an ε = 0 class could aid dataset distillation.Source: §7.4 · p. 14
• Even verifiable-training certificates may be too costly for ordinary users to check, so assurance needs efficient verification or a trusted regulator acting for them.The passage frames assurance as evidence that unlearning meets security or privacy standards.Source: §7.4 · p. 14

8 Conclusions

• Unlearning definitions may need stricter training-process restrictions to make forging examples harder, and training without the data point should be tested as a potentially well-defined alternative.The paper leaves open whether that alternative avoids susceptibility to forging examples.Source: §8 · p. 15
• The findings highlight data attribution as a broader challenge in analyzing both correct and incorrect machine-learning predictions, and identify forgeability as a direction for future study.Source: §8 · p. 15

• Dataset notation includes D, D′, and ˜D; xi and yi denote an input and its label, X the data space, and c the number of classes.Source: A Table of Notations · p. 16
• Training notation defines w and W as model parameters and parameter space, w0 and wt as initialization and post-update parameters, and Mw as the supervised model.Source: A Table of Notations · p. 16
• The table names L as the loss, g as the update rule, ˆx and b as minibatch inputs and size, and η as the learning rate.Source: A Table of Notations · p. 16
• PoL and PoUL denote proof-of-learning and proof-of-unlearning; d and ε define distance and validity threshold, while HDg,d,ε and HD collect valid logs.HD denotes valid logs stemming from w0 using dataset D, and HD(w) denotes logs with ε = 0.Source: A Table of Notations · p. 16
• B and Bε are forging maps, x∗ denotes data points to unlearn, and D/x∗ is the dataset with x∗ removed.L is the Lipschitz constant, and Ballε(w) is the parameter-space distance ball centered at w with radius ε.Source: A Table of Notations · p. 16
• D also denotes the distribution of datasets; µ and σ2 are the mean and covariance trace of g(w,x), respectively.Source: A Table of Notations · p. 16