PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Unlearn: Machine Unlearning via Learning the Unlearning Behaviors

Hang Zhang, Kaifeng Zhang, Yixiao Ma, Weijie Xu, Ye Zhu, Kai Ming Ting

arXiv:2608.16700v1cs.LGcs.AI

TL;DR

Machine unlearning methods can become computationally inefficient because manually designed unlearning functions bottleneck processing massive datasets. L2UL learns unlearning behavior from distributions, achieving comparable accuracy to retraining with improved efficiency, including on larger ResNet models.

  • Problem

    Existing machine unlearning methods can be bottlenecked by complex unlearning functions when processing massive datasets, despite privacy-driven needs to erase data from models.

  • Method

    L2UL is a model-agnostic framework that learns a simple unlearning function from distribution-oriented unlearning behavior using retrained models as ground truth.

  • Results

    L2UL handles massive datasets with exceptional speed and no loss in accuracy, while empirical and theoretical results show greater efficiency than existing methods.

  • Takeaways & Limitations

    Learning unlearning behavior offers a streamlined capability for efficient machine unlearning in large-data settings and scales to larger ResNet models.

  • Takeaways & Limitations

    L2UL requires retraining to obtain its training target, so it cannot currently generate training data when the model cannot be retrained, such as with streaming data.

Abstract

from arXiv · show

Various machine unlearning techniques have been developed in response to privacy legislation requirements, enabling individuals to exercise their legal right to have their data $D_f$ removed from a machine learning model. This process is typically accomplished via the use of an unlearning function denoted as $U$. Existing methods focus on designing an intricate $U$ to unlearn $D_f \subset D$ from a previous model $A(D)$, so that the unlearned model performs as closely as possible to the retrained model $A(D \setminus D_f)$. However, these methods often suffer from high computational costs when dealing with massive training data, as the complex structures of $U$ become a bottleneck even for models with fewer parameters. Inspired by Learning to Optimize, we introduce the first learning-based model-agnostic approach, Learning-to-UnLearn (L2UL). Our core insight is to shift from manually designing $U$ to learning the unlearning behaviors from a distribution perspective, thereby acquiring a simple and efficient $U$ via learning. Our experimental results demonstrate that the accuracy achieved by L2UL is comparable to that of retraining while exhibiting impressive efficiency, particularly in data-intensive scenarios. Furthermore, we validate the performance and scalability of our method on larger models ResNet.

1 Introduction

Machine unlearning is motivated by privacy risks and the high cost of retraining or executing complex unlearning functions on massive datasets. L2UL addresses this bottleneck by learning a simple, model-agnostic unlearning function from retrained models, with theoretical and empirical validation.

  • Motivation: Privacy risks from expanding online data motivate legal measures and the development of machine unlearning methods.The introduction cites CCPA, PIPEDA, and GDPR as legislative responses to user-privacy risks.
  • Motivation: Retraining on remaining data is expensive, while complex unlearning functions can require repeated retraining or Hessian computation.These costs become especially problematic for relatively simple models navigating massive datasets.
  • Method: L2UL learns an unlearning function from retrained models as ground truth instead of manually designing a complex function.The approach is inspired by Learning to Optimize, which learns update rules from optimization states.
  • Contributions: L2UL is presented as a pioneering model-agnostic framework for machine unlearning via learning.The paper also provides a generalization bound for Logistic Regression and Multi-Layer Perceptron models.
  • Advantages: Learning replaces manual design in L2UL, and its simple unlearning function enables very short execution time.The introduction identifies these as two advantages over current methods and reports empirical validation of effectiveness and efficiency.

2 Problem Formulation

This section formalizes machine learning and machine unlearning, defining unlearning as producing a model from D, D_f, and A(D) that closely matches retraining on D \ D_f. Exact unlearning requires matching the distribution of models produced by retraining, while naive retraining is expensive for large remaining datasets.

  • Learning setup: A hypothesis function h: X → Y is learned by algorithm A on training set D ⊂ Z, where Z = X × Y.X is the sample space and Y is the label space.
  • Machine unlearning: Machine unlearning removes a requested subset D_f ⊂ D from a model A(D).The request obliges the learned model to unlearn the users’ data.
  • Machine unlearning: An unlearning algorithm U takes D, D_f, and A(D) as input and outputs a model expected to be as close as possible to A(D \ D_f).U is defined as a map from 2^Z × 2^Z × H to H.
  • Exact unlearning: Exact unlearning holds if P(U(D, D_f, A(D))) = P(A(D \ D_f)), matching the distributions of models trained after forgetting D_f.P(A(D)) denotes the distribution of all models trained on dataset D by randomized algorithm A.
  • Naive unlearning: Naive unlearning retrains a new model on D \ D_f, but this is expensive when |D \ D_f| is large.Retraining achieves exact unlearning under the stated definition.

3 Related Work

Related work categorizes machine unlearning into D-oriented, D_f-oriented, and A(D)-oriented approaches. Unlike prior methods that manually design the unlearning function U, L2UL learns U and belongs to the A(D)-oriented category.

  • Overview: Existing machine unlearning methods remove user data from a previously trained model without full retraining.The related work is organized around three unlearning categories.
  • D-oriented unlearning: D-oriented unlearning partitions D into subsets so that only affected constituent models require retraining when D_f must be forgotten.SISA shards and slices D, trains constituent models incrementally, and limits retraining to the affected model.
  • D_f-oriented unlearning: D_f-oriented unlearning models the impact of forgotten data through influence functions or Markov Chain Monte Carlo sampling, then erases that impact.These approaches directly consider how D_f affects the model.
  • A(D)-oriented unlearning: A(D)-oriented unlearning updates learned-model parameters after forgetting D_f, including noise-based tuning on D\D_f and few-shot learning when D is unavailable.Few-shot learning applies when only A(D), rather than the training data, is known.
  • L2UL: L2UL is an A(D)-oriented algorithm that learns the unlearning function U instead of manually designing it.Prior works can produce an unlearned model close to the retrained model, but do not use learning to obtain U.

4 Proposed Method

L2UL reframes machine unlearning as learning a distribution-based function that maps the full data, forget data, and original model parameters to an unlearned model. It uses kernel mean embeddings with Isolation Kernel features and trains a neural network to match retrained-model parameters efficiently.

  • Distribution-based unlearning: L2UL defines unlearning as a permutation-invariant function U: P × P × H → H over distributions of retained and forgotten data.Representing D and D_f as distributions ensures the output is unchanged when dataset rows are exchanged.
  • Distribution representation: Kernel Mean Embedding converts the data distributions into vectors, while Isolation Kernel supplies an exact finite-dimensional feature map of dimension ψ × t.Each feature-map element is binary, indicating the cell containing x across t partitions.
  • Neural unlearning function: A two-hidden-layer neural network concatenates μ_D, μ_f, and the original model parameters θ to produce unlearned parameters θ′.The experiments use a two-layer fully connected network with widths (256, 64).
  • Learning procedure: L2UL trains on instances pairing the embedded full and forget datasets with parameters of a model trained on a sampled subset, using retrained parameters θ_r as targets.The training set is generated by repeatedly sampling data, selecting forget samples, and retraining on the remaining subset.
  • Inference and efficiency: Once N_U is learned, new forget requests are processed directly without repeating preprocessing or neural-network training, supporting efficient unlearning for few-parameter models with very large datasets.The method’s efficiency follows from learning a small unlearning function while representing large datasets through kernel mean embeddings.

12 end

Theoretical results upper-bound the expected loss of L2UL-unlearned classifiers, including MLPs, and show it is close to that of retrained classifiers.

  • Theoretical analysis: The generalization error bound of the L2UL unlearning model is expressed as an MSE bound involving the dataset radius R.R bounds the norm of every dataset point, with ||x|| ≤ R for all x ∈ X.
  • Theoretical analysis: The expected loss of an MLP unlearned by L2UL is also upper-bounded.The bound uses cross entropy loss, an MLP-structure-dependent finite scalar C, and the unlearning model’s generalization bound ε.
  • Theoretical analysis: Theorems 4.5 and 4.6 indicate that L2UL-unlearned classifiers have expected loss close to that of retrained classifiers.This conclusion applies to the classifier results covered by both theorems.

5 Experiments

Across seven public datasets, L2UL delivers retraining-comparable unlearning accuracy with substantially lower unlearning time for both linear and nonlinear classifiers. It also demonstrates forgetting, contaminated-model cleaning, and robustness to several hyperparameters, while requiring sufficient unlearning information in its input data.

  • Experimental setup: Experiments use seven public datasets and compare L2UL with Retrain, SISA, DeltaGrad, and FYEMU using unlearning time and test accuracy averaged over 10 runs.Each run unlearns one randomly selected instance.
  • Linear classifiers: For Logistic Regression, L2UL achieves accuracy comparable to Retrain and SISA and outperforms DeltaGrad across all seven datasets.On Magic, L2UL is 630, 149, and 282 times faster than Retrain, SISA, and DeltaGrad; on HIGGS, the respective speedups are 422500, 49715, and 51500 times.
  • Nonlinear classifiers: For MLP, L2UL generally matches Retrain and SISA, outperforms DeltaGrad on five datasets, and matches or exceeds FYEMU across the evaluated datasets.L2UL is 15087, 1203, 730, and 43 times faster than Retrain, SISA, DeltaGrad, and FYEMU on Magic, respectively, and 398000, 105250, 294750, and 32750 times faster on HIGGS.
  • Forgetting and model cleaning: L2UL forgets D_f from A(D), as shown by Membership Inference Attack and accuracy on unlearned data, and cleans contaminated models while retaining 1.00 accuracy as dirty points increase.For LR, contamination reduces accuracy to approximately 0.5, whereas L2UL maintains 1.00; similar cleaning results are observed with MLP.
  • Hyperparameter sensitivity and limitation: L2UL is robust to ψ when ψ≥4 and to m, while MLP accuracy on HIGGS rises from 0.60 to 0.65 as s increases; learning U requires sufficient unlearning information in D.For LR on SUSY and HIGGS and MLP on SUSY, accuracy is robust to s and close to retraining.

6 Complexity Analysis

Unlearning time complexity is governed by the model, forgotten data, or parameter dimensions, depending on the algorithm. L2UL has explicit preprocessing, training, unlearning, and space complexity bounds, with faster unlearning possible through stored feature maps at increased storage cost.

  • Existing unlearning algorithms: SISA has time complexity T(A(|D|/k)), limited by the model A and dataset size |D| because it retrains on some shards.Here, k is the number of shards.
  • Existing unlearning algorithms: Df-oriented unlearning has time complexity O(|Df|d3), making its cost depend on the forgotten data Df.This approach considers the influence of Df.
  • Existing unlearning algorithms: A(D)-oriented unlearning has time complexity O(|Df|d2 + d|θ|), limited by the forgotten data Df and parameter count |θ|.This approach updates model parameters.
  • L2UL complexity: L2UL preprocessing costs O(ψt|D|d + mT(A(s))), training U costs T(U(m)), and unlearning Df costs O(ψt|Df|d).Its space complexity is O(ψtd).
  • L2UL complexity: Precomputing feature maps for every point in D reduces unlearning to selecting corresponding maps and taking their mean, while space complexity increases to O(ψt|D|).The mean operation is described as very fast, although time complexity still depends on Df.

7 Unlearn large-scale parameters: ResNet

The section evaluates L2UL on the larger ResNet-18 model using CIFAR-10, finding that it preserves model performance while achieving strong unlearning effectiveness and superior efficiency. L2UL attains the highest ToW scores for all tested forgetting sizes, maintains a comparably low MIA gap, and completes unlearning quickly.

  • Experimental setup: L2UL is evaluated on ResNet-18 trained for 50 epochs on CIFAR-10 with a learning rate of 0.0001.The evaluation uses ToW and MIA gap, the metrics used in RUM.
  • Results: L2UL and the comparison algorithms have a comparably low MIA gap.The MIA metric is defined as Membership Inference Attack gap.
  • Results: L2UL takes a very short time to complete the unlearning.The section identifies unlearning speed as a key advantage over the comparison algorithms.
  • Scalability: L2UL scales across both large-scale data and larger model parameter sizes, maintaining model performance after forgetting data while providing superior unlearning efficiency.The summary describes its efficiency as far superior to existing algorithms.

8 Disscussion

The discussion identifies retraining dependence and privacy leakage as limitations of L2UL, while reporting that retraining its unlearning model is rarely necessary on HIGGS. It also proposes matching unlearning methods to four combinations of model and dataset size, positioning L2UL for simple models on large datasets.

  • Limitations: L2UL requires the retrained model A(D \ D_f) to construct training data and use Equation 2, so it cannot currently handle settings such as streaming data where retraining is unavailable.Finding a new loss function for training N_U without retraining remains an open challenge.
  • Limitations: The unlearning function U contains the user’s information D_f, so U must itself be unlearned after it is used to unlearn A.This creates an additional privacy requirement for deploying the method.
  • Empirical discussion: P(k ≥ 2) < 0.004 on HIGGS, indicating that data {x,y} ∈ D is rarely used to train U and that retraining U is generally unnecessary.When retraining is needed, it takes 5.2 seconds on HIGGS.
  • Task taxonomy: The proposed taxonomy distinguishes four unlearning scenarios according to model size and dataset size, ranging from simple models on small datasets to complex models on large datasets.The scenarios also include complex models on small datasets and simple models on large datasets.
  • Task taxonomy: The work focuses on simple models with large datasets, where a lightweight method is presented as sufficient and sophisticated techniques for complex architectures as unnecessarily resource-intensive.The taxonomy’s broader goal is to match method complexity to task complexity and avoid prohibitive computational costs.

9 Conclusion

The paper proposes Learning-to-UnLearn (L2UL), a framework that learns unlearning behaviors from a distribution-oriented perspective instead of manually designing complex unlearning functions. It targets machine-unlearning settings with simple models and large training datasets.

  • 9 Conclusion: L2UL addresses machine unlearning by learning unlearning behaviors rather than manually designing complex functions.The paper presents L2UL as, to the authors’ knowledge, the first framework following this approach.
  • 9 Conclusion: L2UL adopts a distribution-oriented perspective to provide a streamlined unlearning capability.The conclusion characterizes this capability as both streamlined and potent.
  • 9 Conclusion: The approach focuses on scenarios involving simple models and large training datasets.The paper states that Logistic Regression and Multilayer Perceptrons were used in these settings.

A.1 Proof of Theorem 4.5 … A.4 Proof of Theorem 7.1

The appendix proves bounds for unlearning-model error and MLP parameter gradients, then derives L2UL’s computational and space complexity and a sampling-probability result. These proofs rely on dataset-radius, model-architecture, and parameter-norm assumptions together with standard inequalities and propagation recurrences.

  • A.1 Proof of Theorem 4.5: Theorem 4.5 bounds the unlearning error e between U(A(D), D, D_f) and A(D\D_f) by ||e|| ≤ √𝜖.Here 𝜖 is the unlearning model’s generalization bound measured by MSE, and the dataset satisfies ||x|| ≤ R.
  • A.1 Proof of Theorem 4.5: Theorem 4.5’s proof uses Taylor expansion, the Cauchy–Schwarz inequality, and convexity of the norm function to establish the required bound.The unlearned and retrained models are represented by U(A(D), D, D_f) and A(D\D_f), respectively.
  • A.2 Proof of Theorem 4.6: Theorem 4.6 analyzes an (N + 1)-layer MLP using softmax at the output and sigmoid activations in the remaining layers.The proof defines layer weights and biases by their neuron dimensions and formulates forward propagation over a finite test set X with |X| = m.
  • A.2 Proof of Theorem 4.6: For cross-entropy loss, Theorem 4.6 derives back-propagation expressions and bounds the parameter-gradient norm using flattened layer weights and biases.The proof reduces the bound on dΘ to bounds on dW and dB, with ||dΘ||2 = ||dW||2 + ||dB||2, under ||W||∞ ≤ R.
  • A.3 Proof of Complexity: Algorithm 1 has time complexity O(𝜓𝑡|D|𝑑 + mT(A(s))), combining feature-map preprocessing with the cost of processing each loop.The appendix separately identifies training U on m data points as T(U(m)).
  • A.3 Proof of Complexity: Unlearning D_f from U requires O(𝜓𝑡|D_f|𝑑) time, while U requires O(𝜓𝑡𝑑) space.The time bound includes feature-map construction and computation of μ_f; the space bound stores μ_D and isolation-kernel partition seeds.
  • A.4 Proof of Theorem 7.1: Theorem 7.1 derives the probability that a point x appears at least k0 times when m subsets are sampled from D.The proof first gives the probability that x is sampled from |D| points, then extends it across m independent sampling repetitions to obtain the at-least-k0 event.
Loading 2608.16700v1…