PaperlayerView exact revision on arXiv

Source-linked AI summary

Machine Unlearning: Solutions and Challenges

Jie Xu, Zihan Wu, Cong Wang, Xiaohua Jia

arXiv:2308.07061v3cs.LGcs.AI

TL;DR

Machine unlearning addresses the risks of memorized sensitive, unauthorized, or malicious data by selectively removing its influence from trained models. This paper surveys and categorizes exact and approximate solutions, analyzes their strengths and limitations, and identifies open directions for efficient, verifiable, and broader unlearning.

  • Problem

    Machine learning models may memorize sensitive, unauthorized, or malicious data, creating privacy, security, and performance concerns that motivate selective data removal.

  • Method

    The paper provides a comprehensive taxonomy and critical review of exact and approximate unlearning solutions across methods, models, and data structures.

  • Results

    The review identifies computational complexity, privacy guarantees, and model utility as continuing limitations and organizes promising research directions around efficient, verifiable, and broader unlearning.

  • Takeaways & Limitations

    Machine unlearning offers a roadmap toward adaptive and trustworthy machine-learning systems by clarifying solution tradeoffs and open problems.

Abstract

from arXiv · show

Machine learning models may inadvertently memorize sensitive, unauthorized, or malicious data, posing risks of privacy breaches, security vulnerabilities, and performance degradation. To address these issues, machine unlearning has emerged as a critical technique to selectively remove specific training data points' influence on trained models. This paper provides a comprehensive taxonomy and analysis of the solutions in machine unlearning. We categorize existing solutions into exact unlearning approaches that remove data influence thoroughly and approximate unlearning approaches that efficiently minimize data influence. By comprehensively reviewing solutions, we identify and discuss their strengths and limitations. Furthermore, we propose future directions to advance machine unlearning and establish it as an essential capability for trustworthy and adaptive machine learning models. This paper provides researchers with a roadmap of open problems, encouraging impactful contributions to address real-world needs for selective data removal.

I. INTRODUCTION

Machine unlearning selectively removes the influence of specified training data from already trained models, addressing privacy, security, and adaptation concerns. This paper organizes exact and approximate solutions, critically analyzes their tradeoffs, and identifies future research directions.

  • I. INTRODUCTION: Machine unlearning removes selected training data and its influence from an already trained model, aiming to reproduce behavior as if that data had never been used.It provides a subtractive alternative to full retraining for unauthorized, malicious, or outdated data.
  • I. INTRODUCTION: Machine unlearning supports privacy compliance, defense against poisoned data, and adaptation when data distributions change over time.The paper connects these applications to the right to be forgotten, adversarial robustness, and evolving user preferences.
  • I. INTRODUCTION: Solutions are categorized as exact unlearning, which thoroughly removes data influence, and approximate unlearning, which efficiently minimizes residual influence.Exact methods provide stronger removal guarantees but generally require more computation and storage and suit simpler models more readily.
  • I. INTRODUCTION: The paper provides a comprehensive taxonomy and critical analysis of machine unlearning solutions, including their strengths, limitations, research gaps, and future directions.Its stated goal is to guide development of adaptive and trustworthy machine-learning systems.

3) Ensemble Learning:

Ensemble learning combines multiple models to improve prediction and robustness, and its principles support exact unlearning designs. Machine unlearning nevertheless faces interconnected data dependencies, model complexity, resource costs, privacy leaks, and delays in dynamic settings.

  • 3) Ensemble Learning: Ensemble learning combines multiple weak learners to improve prediction and decision-making by exploiting complementary knowledge and reducing bias and variance.Effectiveness depends on component diversity and competence, training-data quality and size, and the aggregation method.
  • 3) Ensemble Learning: Machine unlearning formally seeks a model with removed-data effects eliminated while preserving performance on the remaining dataset.The target is a selective modification of a trained model rather than unrestricted retraining.
  • 3) Challenges in Machine Unlearning: Removing one data point can disrupt learned dependencies and reduce performance because models extract complex statistical patterns across data points.This dependency makes isolated influence removal difficult.
  • 3) Challenges in Machine Unlearning: Large models complicate influence localization, while iterative optimization, privacy leakage, and changing datasets add computational, privacy, and latency constraints.Removal time, output changes, and accuracy changes can reveal information about removed data or impede prompt updates.

4) Evaluation Metrics for Machine Unlearning Solutions:

The paper evaluates machine unlearning along removal completeness, time efficiency, resource consumption, and privacy preservation. It also situates methods within broader solution families and contrasts unlearning with naive retraining as a baseline.

  • 4) Evaluation Metrics for Machine Unlearning Solutions: Data-erasure completeness measures how thoroughly unlearning removes target-data influence by comparing model predictions or parameters before and after removal.L2 distance and KL divergence are representative comparison measures.
  • 4) Evaluation Metrics for Machine Unlearning Solutions: Unlearning time efficiency compares unlearning duration with naive retraining time, emphasizing responsiveness in real-time applications.The metric captures the practical speed advantage of unlearning over retraining.
  • 4) Evaluation Metrics for Machine Unlearning Solutions: Resource consumption measures memory, power, and storage costs to assess practical viability and scalability.Efficient methods minimize these demands while still meeting unlearning goals.
  • 4) Evaluation Metrics for Machine Unlearning Solutions: Certified removal provides a privacy assurance that the post-removal model is indistinguishable from one never trained on the removed data.The paper identifies epsilon-certified and relaxed (epsilon, delta)-certified removal variants.
  • 4) Evaluation Metrics for Machine Unlearning Solutions: The survey categorizes methods by theoretical foundations such as influence functions, re-optimization, and gradient updates, complementing prior operation-based classifications.Naive retraining removes the target data and retrains from scratch, but is computationally intensive and depends on access to the original data.

A. Overview of Exact Unlearning

SISA enables exact unlearning by isolating data influence across shards, slices, and sub-models, so only affected components require retraining. It improves efficiency and scalability over naive retraining, but storage, partitioning, model-interaction, and generalization tradeoffs remain.

  • A. Overview of Exact Unlearning: SISA divides data into disjoint shards, trains independent sub-models, incrementally stores slice parameters, and aggregates the sub-models into a final model.For removal, retraining can restart from the last saved parameters that exclude the target point.
  • A. Overview of Exact Unlearning: SISA reduces unlearning time and computation by retraining only affected sub-models while aggregation preserves overall prediction performance.The framework is presented as flexible and scalable for evolving unlearning requests.
  • A. Overview of Exact Unlearning: SISA can require extra storage, depend on shard suitability and sub-model characteristics, and degrade generalization through isolated training and aggregation tradeoffs.These limitations constrain performance when data interactions are complex or cannot be partitioned independently.
  • A. Overview of Exact Unlearning: Exact unlearning methods adapt SISA’s isolation and aggregation principles to random forests, graph models, recommendation systems, and k-means.Graph-oriented methods must account for influence spreading across interconnected data.

3) Exact Unlearning for k-means:

Exact unlearning methods use structured retraining or model updates to remove data influence while comparing storage, assumptions, utility, cost, scalability, and practicality. They offer efficient removal but face substantial storage, computational, generality, and evolving-data limitations.

  • Methods: Exact unlearning methods include clustered federated retraining, class-based partitioning, summation updates, and approximate retraining for federated learning.KNOT retrains only clients sharing a cluster; ARCANE confines influence within class-based subsets; summations update models after removing affected data; Liu et al. use Taylor and Hessian approximations.
  • Comparisons and Discussions: Table I compares exact unlearning methods across storage cost, assumptions, model utility, computational cost, scalability, and practicality.
  • Limitations: Exact unlearning requires substantial additional storage for cached parameters, statistics, or intermediate results, limiting scalability for large models or frequent requests.SISA stores parameters for each shard and slice, while HedgeCut stores subtree variants.
  • Limitations: Exact methods can rely on strong algorithmic or data assumptions, and many lack rigorous utility evaluations across diverse models, datasets, and removal volumes.SISA may struggle with dependent data, statistical query methods require summation-form algorithms, and model-specific methods have limited applicability.
  • Limitations: Existing exact unlearning methods add training and scalability costs, while continuously changing data with repeated insertion and removal requests remains an open problem.The suitable method depends on data type, model type, available resources, and the desired efficiency–accuracy balance.

IV. APPROXIMATE UNLEARNING

Approximate unlearning reduces removed-data influence without fully eliminating it, trading completeness for lower computation and storage costs and greater flexibility. Influence-function methods estimate influence and update parameters, but Hessian computation, estimation accuracy, and update choices remain important challenges.

  • Overview: Approximate unlearning minimizes removed-data influence rather than eliminating it completely, providing computational efficiency, lower storage overhead, and greater flexibility.Its efficiency benefits involve a tradeoff between unlearning completeness and speed, computation, and storage savings.
  • Overview: Approximate unlearning typically computes removed-point influence, adjusts model parameters, optionally adds noise, and validates the updated model.Validation may use cross-validation or a hold-out set to assess accuracy and generalization.
  • Influence Functions: Influence-function approaches estimate removed data points’ effects on model parameters and update the model to reverse those effects.The reviewed methods include pioneering Newton-style removal and later work addressing its computational limitations.
  • Limitations: Hessian inversion is computationally expensive and numerically unstable for large models, while later methods reduce data-access, computation, and storage requirements using stored statistics.The Hessian condition number grows with the number of parameters, amplifying inversion errors.
  • Influence Functions: Influence-function unlearning can extend to non-convex models and deep neural networks while incorporating test loss, removal thoroughness, and finer-grained corrections.
  • Limitations: Open challenges include improving influence estimation and parameter updates and selecting optimal update parameters and influence-estimation techniques.Connections to differential privacy and information theory may clarify inherent limits.

C. Approximate Unlearning based on Re-optimization after Removing the Data

Approximate re-optimization unlearning iteratively updates a trained model to preserve performance on remaining data while reducing information from data to be forgotten. The approach offers promising efficiency, but verification, scalability, assumptions, and privacy–accuracy–efficiency tradeoffs remain open challenges.

  • Approximate unlearning based on re-optimization: Re-optimization updates the model from its original parameters by minimizing a loss on remaining data while removing information about forgotten data.The updated model is intended to retain performance on remaining data and statistically behave as if trained without the forgotten data.
  • Approximate unlearning based on re-optimization: Weight scrubbing, noise injection, activation analysis, separated user weights, and mnemonic codes support selective forgetting across deep-network and class-level settings.The reviewed methods target different units of removal, including individual data, user data, activations, and classes.
  • Approximate unlearning based on re-optimization: Approximate re-optimization balances residual information against remaining-data accuracy through a forgetting objective and related hyperparameters.The objective combines expected loss on remaining data with a term penalizing residual information about removed data; λ controls this tradeoff.
  • Approximate unlearning based on re-optimization: Weight-centric analyses may miss information retained in activations, motivating output-focused guarantees for more complete removal assessment.Follow-up work uses final activations because weight changes may not sufficiently alter deep-network outputs.
  • Challenges and discussion: Strong convexity, linear or quadratic approximations, and other simplifying assumptions can limit generalization, while stability and transferability of class-level forgetting remain unresolved.The review also identifies computational expense and the need to quantify closeness between original and re-optimized models as open problems.
  • Challenges and discussion: Approximate re-optimization shows promising early progress toward efficient data removal for deep learning, but requires stronger theory, scalability, and algorithms for complex training dynamics.The paper frames these directions as necessary for advancing the approach beyond its current early progress.

D. Approximate Unlearning based on Gradient Update

Approximate unlearning based on gradient updates starts from a previously trained model and uses a few updates, often with cached training information, to adapt efficiently to small data changes. Its speed is constrained by model assumptions, accumulated approximation errors, and weaker performance for large data changes.

  • Approximate unlearning based on gradient update: Gradient-update unlearning initializes from the previous model and performs a few updates on new data instead of full retraining.This two-step framework targets minor training-data changes.
  • Approximate unlearning based on gradient update: Cached gradients and parameters enable rapid adaptation to small training-set changes, as demonstrated by DeltaGrad and related recovery methods.DeltaGrad uses cached information from original training, while FedRecover targets poisoned federated models with reduced computation and communication costs.
  • Approximate unlearning based on gradient update: Gradient ascent can remove backdoor influence by identifying trigger patterns and increasing prediction loss for those triggers relative to their target labels.BAERASER applies this strategy to discard contaminated memories associated with embedded triggers.
  • Challenges and discussion: Strong-convexity assumptions may fail for complex models, and L-BFGS Hessian approximations may break down for very high-dimensional models.These limitations constrain how reliably gradient-update methods transfer to large or non-convex settings.
  • Challenges and discussion: Approximation errors can accumulate across update rounds, correction strategies add cost, and gradient adjustments may be insufficient for large data changes.The review recommends validating assumptions and guarantees while improving robustness to approximation errors and larger changes.

E. Approximate Graph Unlearning

Approximate graph unlearning must account for dependencies among nodes, edges, and neighborhoods rather than treating training examples as independent. Existing methods address structural influence, dynamic graphs, limited-data settings, and federated knowledge retention, but scalability remains open.

  • Dynamic graphs: GUIDE extends graph unlearning to dynamic graphs through guided partitioning, subgraph repair, and related efficiency mechanisms.
  • Limited training data: GST-based approximate unlearning targets limited-data settings by using analytically constructed, non-trainable wavelet coefficients that are stable under small graph perturbations.
  • Federated knowledge graphs: FedLU addresses federated knowledge-graph heterogeneity and retention with mutual knowledge distillation plus interference and decay-based forgetting.
  • Data interdependence: Graph unlearning requires specialized techniques because removing a node or edge can affect connected neighbors and broader graph representations.Graph Influence Function models affected-neighbor loss, while GNNDELETE constrains edge-deletion effects to local neighborhoods.
  • Open challenges: Current graph-unlearning methods are often evaluated on small networks, leaving scalability to millions of evolving nodes and edges unresolved.
  • Open challenges: Future work should improve efficiency, scalability, flexibility, and evaluation across applications such as recommendation, node classification, and link prediction.

F. Approximate Unlearning based on Novel Techniques

Novel approximate unlearning techniques exploit model architecture, parameter subspaces, class-specific knowledge, decision boundaries, or reward-conditioned generation to remove selected information efficiently.

  • Novel approximate methods tailor unlearning to model structure or data characteristics, including CNN channels, regression subspaces, class knowledge, decision boundaries, and language-model behaviors.
  • PRU projects the exact linear-regression update onto a low-dimensional subspace, with cost scaling linearly in data dimension rather than training-set size.
  • ERM-KTP isolates class-specific knowledge during training, then transfers non-target knowledge while prohibiting target knowledge transfer during unlearning.
  • Boundary Unlearning erases a class by shifting the decision boundary through boundary shrinking or temporary shadow-class expansion and pruning.
  • Quark uses reward-ranked samples, special reward tokens, KL-penalized retraining, and generation-time token selection to steer language models away from undesirable behaviors.

A. Performance and Privacy Issues of Unlearning

Machine unlearning faces tradeoffs among efficiency, model utility, privacy, and legal completeness. The paper therefore emphasizes complementary safeguards, auditable proof, and integration across technical and regulatory layers.

  • Unlearning efficiency can conflict with model utility: isolation-based architectures may reduce performance, while other methods can lower accuracy or cause catastrophic forgetting.
  • Removing one data point may expose information about other data points, motivating the combination of unlearning with encryption and other safeguards.
  • Machine unlearning is neither necessary nor sufficient for the right to be forgotten because retraining can satisfy removal requests and additional legal and technical steps remain required.
  • Right-to-be-forgotten deployments can introduce abuse risks, including repeated requests that reduce model availability or strategic data sharing followed by unlearning.
  • Proof of unlearning must provide auditable evidence despite the model owner controlling the original data and model, making stronger cryptographic proofs important.
  • Succinct zero-knowledge proofs and trusted execution environments are proposed to verify correct unlearning while limiting verification time and cost.

D. Unlearning and Explainable AI

Explainability and machine unlearning can support each other: explanations can identify influential information, while before-and-after explanations can reveal what unlearning changes. The paper also identifies open needs in data coverage, model scope, granularity, privacy, and evaluation.

  • Unlearning and Explainable AI: Influence-function unlearning connects explainable AI with selective removal by estimating how training samples affect model parameters, although estimation is costly and unstable.
  • Unlearning and Explainable AI: Comparing explanations before and after unlearning can reveal how removed information influenced model predictions and clarify memorization changes.
  • Unlearning and Explainable AI: The paper calls for quantitative protocols to evaluate the interaction between explainability and unlearning.
  • Open directions: Future unlearning methods must extend beyond set- and graph-structured data to text, speech, multimedia, and multimodal combinations with distinct structural properties.
  • Open directions: Approximate unlearning remains challenged by non-convex neural networks, including local optima, saddle points, and the need for effective guarantees.
  • Open directions: Finer-grained, interpretable unlearning could remove semantic components such as image regions or words while retaining the rest of an example.
  • Open directions: Reliable evaluation requires metrics for influence removal from forgotten data and influence retention for remaining data, supported by information-theoretic and explainability tools.
Loading 2308.07061v3…