PaperlayerView exact revision on arXiv

Source-linked AI summary

Why Forget-Only Unlearning Needs Memorization

Luka Radić, Vikrant Singhal, Amartya Sanyal

arXiv:2610.10519v1cs.LGcs.ITmath.ITstat.ML

TL;DR

Forget-only unlearning asks whether a model and the deleted examples alone can produce an output close to retraining, despite retraining’s cost. The paper derives impossibility and memorization lower bounds, including a threshold-learner gap between ordinary storage and deletion needs.

  • Problem

    Machine unlearning seeks outputs close to retraining after selected examples are removed, but retraining can be too expensive and forget-only unlearning gives the deletion algorithm no retained data or other training information.

    Source: §1 · pp. 1–2

  • Method

    The paper uses indistinguishable trained models with divergent retraining targets to derive unlearning lower bounds, then lower-bounds memorization from the information in possible deletion targets.

    Source: §1 · pp. 2–3

  • Results

    Threshold learners need Ω(m log(N/n)) bits for requests of size at most m when n ≥ 2m, despite ordinary learning retaining one boundary point; hard-margin linear SVMs in d ≥ 2 admit no fixed finite ε with non-trivial utility uniformly.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Information discarded during ordinary learning may be needed for deletion, creating a tradeoff between preserving it in the model and relying on retained data or other training information.

    Source: §1 · pp. 1, 3

    The lower bounds quantify required recoverable information but do not specify which features to memorize or how to store them, and their instantiation for contemporary architectures remains open.

    Source: §5 · p. 11

Abstract

from arXiv · show

Machine unlearning asks for a deletion algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, we study forget-only unlearning, where the deletion algorithm receives only the trained model and the examples to forget, with no retained data or extra training information. We ask whether forget-only unlearning is always possible. We first show that this depends on the learning method: different datasets can produce the same trained model but require very different outputs after the same examples are removed. Using this observation, we derive lower bounds on how accurately unlearning can match retraining and instantiate them for several standard learning algorithms. We then ask what must be true when forget-only unlearning succeeds. To this end, we derive lower bounds on what an algorithm must memorize about the training data to handle arbitrary deletion requests. For simple threshold learners, the required information can be as large as the entire dataset, even though ordinary training keeps only one boundary point. Overall, our results show that information discarded during ordinary learning may be needed later for deletion, so models designed for forget-only unlearning may need to retain more information than standard training does.

1 Introduction

The introduction asks whether unlearning can match retraining when the unlearner sees only the trained model and the examples to forget. It presents impossibility results and memorization lower bounds, including a threshold-learner gap between what ordinary training retains and what deletion can require.

1 Introduction

  • Forget-only unlearning gives the deletion algorithm only the trained model and forget set, while certified unlearning seeks an output distribution close to retraining on retained data.Retraining is described as the gold standard but is often too expensive or practically impossible.Source: §1 · p. 1
  • Different datasets can yield the same trained model but far-apart retraining targets after the same deletion, leaving a forget-only unlearner unable to match both.For a threshold learner, deleting a shared leftmost positive point makes the differing second-leftmost positive points the retraining targets.Source: §1 · p. 2
  • For hard-margin linear SVMs in dimension d ≥ 2, no forget-only unlearner with non-trivial utility achieves a fixed finite ε uniformly over datasets and deletion requests.The result illustrates that some learning methods cannot support the requested guarantee without additional information.Source: §1 · p. 2
  • The paper lower-bounds I(M; S) from retraining targets induced by deletion requests, accounting for unlearning and utility requirements and avoiding double-counting overlapping information.The bound applies across request orderings, allowing the strongest lower bound to be selected.Source: §1 · pp. 2–3
  • Ordinary threshold learning keeps one boundary point and carries log(N/n) bits, while supporting requests of size at most m with n ≥ 2m requires Ω(m log(N/n)) bits.The lower bound quantifies the additional information required for forget-only unlearning.Source: §1 · p. 3
  • The paper distinguishes its algorithm- and deletion-target-dependent bounds from prior space-complexity bounds and frames a tradeoff between preserving information and using other training information.It characterizes its account as among the first formal explanations of why forget-only unlearning requires memorization.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the learning and deletion setting, the forget-only information restriction, and the guarantees used to compare unlearning with retraining. They also require empty-request unlearning to preserve utility so that a constant-output unlearner cannot satisfy the comparison vacuously.

2 Preliminaries

  • For a dataset S, the learner outputs M = A(S), while the retraining target after deleting U is A(S \ U); a forget-only unlearner receives only M and U.It has no retained data, logs, checkpoints, gradients, or auxiliary statistics beyond information stored in M.Source: §2 · p. 3
  • Rényi unlearning compares the unlearned output on (A(S), U) with the empty-request output on the retrained model A(S \ U), using symmetric α-Rényi divergence.The guarantee applies to every dataset and deletion request up to the specified budget.Source: §2 · pp. 3–4
  • Empty-request utility requires the unlearner’s output on an empty request to remain close to its input, preventing an input-independent output from satisfying unlearning alone.The text gives zero-one and norm-based metric choices and notes that a Gaussian empty-request map satisfies the utility condition.Source: §2 · p. 4

3 Impossibility of Forget-Only Unlearning

Forget-only impossibility depends on the learner: shared-deletion examples make pretrained models indistinguishable while separating retraining outputs. The paper instantiates this obstruction for standard learners and finite-teaching-dimension ERMs.

Scope

  • The impossibility result is learner-dependent: a model that encodes the full dataset can recover the retained data after deletion.Thus the lower bound cannot apply unconditionally to every learner.Source: §3 · p. 4

Shared-deletion lower bound

  • Shared-deletion examples yield lower bounds because datasets with close pretrained-model distributions can have well-separated retraining outputs after the same deletion.Theorem 3.1 gives bounds for exact and approximate collisions; the lower bound depends on the learner and the separation between retraining outputs.Source: §3 · pp. 4–5

Canonical thresholds

  • Canonical threshold learners admit shared-deletion examples, separating ordinary learning behavior from what deletion may require.The canonical learner returns the midpoint between the largest negative and smallest positive examples.Source: §3 · p. 6

Empirical median

  • For empirical medians, the largest shared-deletion separation depends on sample parity and deletion budget, reaching 2c for larger budgets.For even n, Δ=2c when m≥3; for odd n, Δ=2c when m≥2.Source: §3 · p. 6

Hard-margin linear classification

  • Hard-margin SVM admits shared-deletion examples at every positive separation, yielding unbounded lower bounds under the stated Gaussian post-processing condition.With fixed-variance Gaussian empty-unlearning post-processing, no finite ε gives a uniform guarantee, even for single-example deletions.Source: §3 · p. 6

Finite teaching dimension

  • Finite teaching dimension guarantees shared-deletion examples for sufficiently large zero-one empirical-risk-minimization problems.The construction has |U|=O(τ^2) and |S_i|=o(τ^3), and gives separation Δ=min_{i≠j}ϕ(h_i−h_j).Source: §3 · p. 6

4 Memorization for Forget-Only Unlearning

Section 4 asks how much information the trained model must retain for forget-only unlearning, after showing that deletion requests may require targets not recoverable from the model alone. Its lower bounds quantify this requirement and show that standard learner outputs can be insufficient across several learning settings.

4 Memorization for Forget-Only Unlearning

  • The section asks how much information A(S) must store so the retraining target can be recovered from the trained model and a deletion request.The analysis measures this requirement through mutual information between A(S) and the training data S.Source: §4 · p. 7

4.1 Memorization Lower Bound

  • The lower bound counts new information in retraining targets across requests, subtracting a penalty for approximate unlearning.The requests can reveal overlapping information, so the analysis accounts only for what each target adds beyond those already considered; the request ordering is an accounting device.Source: §4.1 · p. 8

4.2 Instantiations of Theorem 4.3

  • For canonical threshold ERM, the ordinary output carries log(N/n) bits, while the paper says forget-only unlearning can require significantly more information.The construction uses realizable samples and deletion requests of size m; the extra information may not fit in the learner’s single threshold output.Source: §4.2 · pp. 9–10
  • For coordinate PCA, the output is one coordinate index requiring O(log d) bits, while forget-only unlearning can require substantially more information.The proposition constructs a dataset distribution and deletion requests for which any unlearner satisfying the stated assumptions must meet a lower bound.Source: §4.2 · p. 9
  • For ridge regression, the bare fitted output is identically zero, yet when β3 < 2/3 those coefficients cannot support the required guarantee, even for single-example deletions.The construction uses one-hot inputs and singleton deletion requests.Source: §4.2 · p. 10
  • For row-wise factorized affine matrix completion, the full-sample fitted matrix is deterministic, but the construction can require storing a hidden permutation.The proposition states a lower bound for datasets of size n > 3m with deletion requests of size m.Source: §4.2 · p. 10
  • The paper concludes that unlearning may require a different output space because a threshold learner’s single-number output cannot encode the additional information.The ordinary threshold output is the threshold itself, selected from a finite set of possible values.Source: §4.2 · p. 10

5 Related Work and Discussion

The discussion places the results in the strict forget-only setting, where deletion receives only the trained model and forget set. It distinguishes this setting from work that substitutes proxies or studies different memory bounds, and identifies open questions about what information models should store.

5 Related Work and Discussion

  • Strict forget-only unlearning gives the deletion algorithm only the trained model and forget set, unlike approaches using retained data, logs, checkpoints, gradients, or auxiliary statistics.Empirical successes may rely on benign requests, local stability, proxy information, or weaker-than-retraining indistinguishability criteria.Source: §5 · p. 11
  • Retain-free methods may substitute proxy data, surrogate distributions, curvature information, or deliberately preserved training state for access to retained examples.The paper connects these approaches to its lower bound’s intuition that the trained model must retain recoverable information about the retraining target.Source: §5 · p. 11
  • Cherapanamjeri et al. [2025] study memory complexity through eluder dimension, whereas these bounds depend on the learner and deletion requests and cover strict forget-only unlearning.Their results do not directly cover regression, PCA, or factorization.Source: §5 · p. 11
  • The bounds quantify how much recoverable information is needed but do not identify which features or statistics to store or how to store them.Applying the bounds to contemporary architectures and large-scale learning pipelines remains an open direction.Source: §5 · p. 11

A Additional Related Works

The additional related-work discussion surveys empirical unlearning methods and evaluations, noting that methods can succeed under some settings while failing under others. It contrasts empirical forgetting criteria with retraining-style indistinguishability and relates evaluation difficulty to target sensitivity and comparison criteria.

A Additional Related Works

  • Language-model unlearning methods use gradient ascent, unlikelihood, negative preference optimization, or forget-data-only objectives, but optimize empirical criteria rather than the stronger indistinguishability requirement studied here.The cited examples include approaches targeting Harry Potter content and FLAT, which uses neither retain data nor a reference model.Source: A Additional Related Works · p. 15
  • Unlearning difficulty varies with deletion distribution and evaluation criterion; empirical observations are consistent with greater difficulty when retraining targets are more sensitive to retained data and comparisons are more stringent.The discussion cites benchmarks and representation-based evaluations alongside certified-unlearning work on deletion-specific and distribution-free sensitivity.Source: A Additional Related Works · p. 15

B Supporting Lemmas

The supporting lemmas establish an event-probability consequence of a Rényi-divergence bound and outline the measure-theoretic ingredients used in its proof.

B Supporting Lemmas

  • The event-transfer lemma bounds P(E) by e^(γε)Q(E)^γ when α > 1, γ = (α−1)/α, and Dα(P∥Q) ≤ ε.The claim applies to every measurable event E.Source: B Supporting Lemmas · p. 15
  • The proof introduces a common dominating measure for P and Q and defines the Radon–Nikodym derivative used to express the divergence.The passage gives 1/2(P + Q) as an example of a common dominating measure.Source: B Supporting Lemmas · p. 15
  • The proof applies Hölder’s inequality to an event probability before concluding the argument.The cited proof passages introduce the event and the Hölder exponents.Source: B Supporting Lemmas · p. 16

C Deferred Proofs from Section 3

The deferred proof turns shared-deletion examples into separated regions around retraining targets, then uses those regions to bound how many targets an unlearner can serve. It handles exact and approximate collisions separately.

C Deferred Proofs from Section 3

  • Separated target sets yield disjoint regions B_i, and empty-request utility places most retrained-output probability in each corresponding region.The proof obtains pairwise disjointness and Q_i(B_i)≥1−u(r), with u(r)=κ+Γ(r).Source: C Deferred Proofs from Section 3 · pp. 16–17
  • The proof defines the original models, retrained targets, and unlearning output laws, then builds regions around retraining targets to compare their distributions.For each example, it sets M_i=A(S_i), W_i=A(S_i\U), and defines B_i as the points within radius r of E_i.Source: C Deferred Proofs from Section 3 · p. 17
  • For approximate collisions, the proof applies the same distributional bounds in both directions, sums over disjoint regions, and optimizes over r.It uses that x↦x^γ is increasing before taking logarithms and rearranging.Source: C Deferred Proofs from Section 3 · p. 17
  • In the exact-collision case, identical unlearning output laws and disjoint regions constrain the number of distinguishable retraining targets.The zero-collision condition forces T_i=T_1; the proof sums bounds over the disjoint B_i.Source: C Deferred Proofs from Section 3 · p. 17

C.1 Teaching Dimension

Finite teaching dimension lets the proof construct many datasets that produce the same ERM model but different retraining targets after a shared deletion request.

C.1 Teaching Dimension

  • A teaching set uniquely identifies a hypothesis among the class, and teaching dimension is the minimum teaching-set size maximized over hypotheses.The proof uses teaching sets of size at most τ.Source: §C.1 · p. 18
  • Given teaching sets T0 and Ri for h0 and hi, each of size at most τ, the common request U uses τ+1 copies of T0, and Si=Ri∪U has size at most τ(τ+2).Source: §C.1 · p. 18
  • Each dataset has ERM output h_0, while removing the shared request leaves a teaching set for a distinct h_i, so the retraining targets differ.h_0 makes at most τ errors on R_i, whereas h_i makes at least τ+1 errors on the repeated T_0.Source: §C.1 · p. 18

C.2 Proofs of the Examples

The examples quantify how much retraining targets can diverge after shared deletions for threshold, median, and hard-margin SVM learners. The separation depends on the learner and, for medians, on the deletion-set size.

C.2 Proofs of the Examples

  • For threshold learners, the examples establish shared-deletion separations of c−1/2 in the stated setting.The construction pads the datasets so their full-sample threshold outputs coincide, while deletion yields different outputs.Source: §C.2 · p. 18
  • For even-sized median datasets, one deleted point permits separation c, while two deleted points can also attain separation c.The two-point construction has post-deletion medians −c/2 and c/2.Source: §C.2 · p. 19
  • For even-sized median datasets, any deletion size from three through n−1 permits the maximum separation 2c.The construction deletes three shared zeros and is admissible for every m≥3 in the stated range.Source: §C.2 · pp. 19–20
  • For odd-sized median datasets, one deleted point permits separation c, while deletion sizes from two through n−1 permit separation 2c.The latter construction deletes two shared zeros; 2c is the trivial upper bound.Source: §C.2 · p. 20
  • For hard-margin SVMs, the full datasets share output ρ^-1e_1, but deleting one point creates arbitrarily large target separation as ρ approaches zero.Choosing ρ sufficiently small yields any desired Δ>0, and the construction applies for every 1≤m≤n−1.Source: §C.2 · pp. 20–21

D Deferred Proofs from Section 4

The deferred proofs connect unlearning guarantees to bounds on output mismatch and memorization. They use data processing and utility conditions, then apply information-theoretic inequalities to bound the information needed about training data.

D Deferred Proofs from Section 4

  • The proof of the unlearning bound uses conditional independence and data processing, with separate terms for empty-request movement, learner randomness, and approximate unlearning.For deterministic learners, the randomness term vanishes, giving β_un≤e^γεηγ.Source: D Deferred Proofs from Section 4 · pp. 21–22
  • The retraining target and its empty-request reference are compared under the unlearning guarantee, while empty-request utility prevents an input-independent output from satisfying the intended condition.The argument bounds the probability that independent runs of the retraining algorithm disagree, using the empty-request utility condition for the matched term.Source: D Deferred Proofs from Section 4 · pp. 21–22
  • For finite discrete model spaces, the memorization proof applies Fano’s inequality and sums information bounds across the request permutation.The derivation uses the chain rule, non-negativity of mutual information, and data processing.Source: D Deferred Proofs from Section 4 · pp. 21–23

D.1 Deferred Proofs from Section 4.2

The deferred proofs instantiate the conditional-support argument across threshold, PCA, ridge, and factorization constructions. They show how retraining targets can depend on information concealed by the original fitted output.

Threshold construction

  • A size-m deletion moves the leftmost remaining positive example to xm+i; given prior history, its location is uniform within Bm+i, and distinct locations define distinct hypotheses.The construction uses n ≥ 2m so that xm+i exists after deletion.Source: §D.1 · p. 23

Theorem 4.4

  • For threshold ERM, conditional retraining-target uncertainty is log q, while the bare output’s boundary point is uniform over Bm.The proof applies the conditional-support argument after substituting q for each request.Source: §D.1 · p. 23

Theorem 4.5

  • After deleting Ui, the largest remaining empirical second moment is λi+1 at ai+1; ai+1 is uniform over a q-coordinate block, giving H(Wi | Hi) = log q.The conditional-support Fano argument uses the q possible targets per request.Source: §D.1 · p. 24

Theorem 4.6

  • Balanced-label ridge datasets all fit zero, but deleting one positive copy makes the retrained coefficient depend on hidden count Ci, requiring accurate unlearning to retain count information.The construction keeps total dataset size fixed despite the random counts.Source: §D.1 · pp. 24–25

Theorem 4.7

  • Deleting a row’s m sum measurements makes the retrained matrix reveal σ(i); the conditional target entropies are log qi, summing to log(r!).The original fitted matrix is deterministic on the construction, so its mutual information with the dataset is zero.Source: §D.1 · p. 26

Related papers

Loading 2610.10519v1…