When to Forget? Complexity Trade-offs in Machine Unlearning

• URL: http://arxiv.org/abs/2502.17323v1
• Date: Mon, 24 Feb 2025 16:56:27 GMT
• Title: When to Forget? Complexity Trade-offs in Machine Unlearning
• Authors: Martin Van Waerebeke, Marco Lorenzi, Giovanni Neglia, Kevin Scaman,
• Abstract summary: Machine Unlearning (MU) aims at removing the influence of specific data points from a trained model.<n>We analyze the efficiency of unlearning methods and establish the first upper and lower bounds on minimax times for this problem.<n>We provide a phase diagram for the unlearning complexity ratio -- a novel metric that compares the computational cost of the best unlearning method to full model retraining.
• Score: 23.507879460531264
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Machine Unlearning (MU) aims at removing the influence of specific data points from a trained model, striving to achieve this at a fraction of the cost of full model retraining. In this paper, we analyze the efficiency of unlearning methods and establish the first upper and lower bounds on minimax computation times for this problem, characterizing the performance of the most efficient algorithm against the most difficult objective function. Specifically, for strongly convex objective functions and under the assumption that the forget data is inaccessible to the unlearning method, we provide a phase diagram for the unlearning complexity ratio -- a novel metric that compares the computational cost of the best unlearning method to full model retraining. The phase diagram reveals three distinct regimes: one where unlearning at a reduced cost is infeasible, another where unlearning is trivial because adding noise suffices, and a third where unlearning achieves significant computational advantages over retraining. These findings highlight the critical role of factors such as data dimensionality, the number of samples to forget, and privacy constraints in determining the practical feasibility of unlearning.

Related papers

• Capturing the Temporal Dependence of Training Data Influence [100.91355498124527]
  We formalize the concept of trajectory-specific leave-one-out influence, which quantifies the impact of removing a data point during training. We propose data value embedding, a novel technique enabling efficient approximation of trajectory-specific LOO. As data value embedding captures training data ordering, it offers valuable insights into model training dynamics.
  arXiv  Detail & Related papers  (2024-12-12T18:28:55Z)
• RESTOR: Knowledge Recovery through Machine Unlearning [71.75834077528305]
  Large language models trained on web-scale corpora can memorize undesirable datapoints.<n>Many machine unlearning algorithms have been proposed that aim to erase' these datapoints.<n>We propose the RESTOR framework for machine unlearning, which evaluates the ability of unlearning algorithms to perform targeted data erasure.
  arXiv  Detail & Related papers  (2024-10-31T20:54:35Z)
• Attribute-to-Delete: Machine Unlearning via Datamodel Matching [65.13151619119782]
  Machine unlearning -- efficiently removing a small "forget set" training data on a pre-divertrained machine learning model -- has recently attracted interest. Recent research shows that machine unlearning techniques do not hold up in such a challenging setting.
  arXiv  Detail & Related papers  (2024-10-30T17:20:10Z)
• Distribution-Level Feature Distancing for Machine Unlearning: Towards a Better Trade-off Between Model Utility and Forgetting [4.220336689294245]
  We propose Distribution-Level Feature Distancing (DLFD), a novel method that efficiently forgets instances while preserving task-relevant feature correlations.<n>Our method synthesizes data samples by optimizing the feature distribution to be distinctly different from that of forget samples, achieving effective results within a single training epoch.
  arXiv  Detail & Related papers  (2024-09-23T06:51:10Z)
• Learn while Unlearn: An Iterative Unlearning Framework for Generative Language Models [52.03511469562013]
  We introduce the Iterative Contrastive Unlearning (ICU) framework, which consists of three core components. A Knowledge Unlearning Induction module targets specific knowledge for removal using an unlearning loss. A Contrastive Learning Enhancement module preserves the model's expressive capabilities against the pure unlearning goal. An Iterative Unlearning Refinement module dynamically adjusts the unlearning process through ongoing evaluation and updates.
  arXiv  Detail & Related papers  (2024-07-25T07:09:35Z)
• Partially Blinded Unlearning: Class Unlearning for Deep Networks a Bayesian Perspective [4.31734012105466]
  Machine Unlearning is the process of selectively discarding information designated to specific sets or classes of data from a pre-trained model. We propose a methodology tailored for the purposeful elimination of information linked to a specific class of data from a pre-trained classification network. Our novel approach, termed textbfPartially-Blinded Unlearning (PBU), surpasses existing state-of-the-art class unlearning methods, demonstrating superior effectiveness.
  arXiv  Detail & Related papers  (2024-03-24T17:33:22Z)
• An Information Theoretic Approach to Machine Unlearning [43.423418819707784]
  To comply with AI and data regulations, the need to forget private or copyrighted information from trained machine learning models is increasingly important.<n>In this work, we address the zero-shot unlearning scenario, whereby an unlearning algorithm must be able to remove data given only a trained model and the data to be forgotten.<n>We derive a simple but principled zero-shot unlearning method based on the geometry of the model.
  arXiv  Detail & Related papers  (2024-02-02T13:33:30Z)
• Unlearnable Algorithms for In-context Learning [36.895152458323764]
  In this paper, we focus on efficient unlearning methods for the task adaptation phase of a pretrained large language model. We observe that an LLM's ability to do in-context learning for task adaptation allows for efficient exact unlearning of task adaptation training data. We propose a new holistic measure of unlearning cost which accounts for varying inference costs.
  arXiv  Detail & Related papers  (2024-02-01T16:43:04Z)
• Compute-Efficient Active Learning [0.0]
  Active learning aims at reducing labeling costs by selecting the most informative samples from an unlabeled dataset. Traditional active learning process often demands extensive computational resources, hindering scalability and efficiency. We present a novel method designed to alleviate the computational burden associated with active learning on massive datasets.
  arXiv  Detail & Related papers  (2024-01-15T12:32:07Z)
• Unlearn What You Want to Forget: Efficient Unlearning for LLMs [92.51670143929056]
  Large language models (LLMs) have achieved significant progress from pre-training on and memorizing a wide range of textual data. This process might suffer from privacy issues and violations of data protection regulations. We propose an efficient unlearning framework that could efficiently update LLMs without having to retrain the whole model after data removals.
  arXiv  Detail & Related papers  (2023-10-31T03:35:59Z)
• Machine Unlearning of Features and Labels [72.81914952849334]
  We propose first scenarios for unlearning and labels in machine learning models. Our approach builds on the concept of influence functions and realizes unlearning through closed-form updates of model parameters.
  arXiv  Detail & Related papers  (2021-08-26T04:42:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.