The Space Complexity of Learning-Unlearning Algorithms

• URL: http://arxiv.org/abs/2506.13048v1
• Date: Mon, 16 Jun 2025 02:31:41 GMT
• Title: The Space Complexity of Learning-Unlearning Algorithms
• Authors: Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman, Ayush Sekhari, Abhishek Shetty,
• Abstract summary: We study the memory complexity of machine unlearning algorithms that provide strong data deletion guarantees to the users.<n>We ask how many bits of storage are needed to be able to delete certain training samples at a later time.
• Score: 18.44297364051363
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the memory complexity of machine unlearning algorithms that provide strong data deletion guarantees to the users. Formally, consider an algorithm for a particular learning task that initially receives a training dataset. Then, after learning, it receives data deletion requests from a subset of users (of arbitrary size), and the goal of unlearning is to perform the task as if the learner never received the data of deleted users. In this paper, we ask how many bits of storage are needed to be able to delete certain training samples at a later time. We focus on the task of realizability testing, where the goal is to check whether the remaining training samples are realizable within a given hypothesis class \(\mathcal{H}\). Toward that end, we first provide a negative result showing that the VC dimension is not a characterization of the space complexity of unlearning. In particular, we provide a hypothesis class with constant VC dimension (and Littlestone dimension), but for which any unlearning algorithm for realizability testing needs to store \(\Omega(n)\)-bits, where \(n\) denotes the size of the initial training dataset. In fact, we provide a stronger separation by showing that for any hypothesis class \(\mathcal{H}\), the amount of information that the learner needs to store, so as to perform unlearning later, is lower bounded by the \textit{eluder dimension} of \(\mathcal{H}\), a combinatorial notion always larger than the VC dimension. We complement the lower bound with an upper bound in terms of the star number of the underlying hypothesis class, albeit in a stronger ticketed-memory model proposed by Ghazi et al. (2023). Since the star number for a hypothesis class is never larger than its Eluder dimension, our work highlights a fundamental separation between central and ticketed memory models for machine unlearning.

Related papers

• Provable unlearning in topic modeling and downstream tasks [36.571324268874264]
  Provable guarantees for unlearning are often limited to supervised learning settings.<n>We provide the first theoretical guarantees for unlearning in the pre-training and fine-tuning paradigm.<n>We show that it is easier to unlearn pre-training data from models that have been fine-tuned to a particular task, and one can unlearn this data without modifying the base model.
  arXiv  Detail & Related papers  (2024-11-19T16:04:31Z)
• MUSE: Machine Unlearning Six-Way Evaluation for Language Models [109.76505405962783]
  Language models (LMs) are trained on vast amounts of text data, which may include private and copyrighted content. We propose MUSE, a comprehensive machine unlearning evaluation benchmark. We benchmark how effectively eight popular unlearning algorithms can unlearn Harry Potter books and news articles.
  arXiv  Detail & Related papers  (2024-07-08T23:47:29Z)
• Active Learning with Simple Questions [20.239213248652376]
  We consider an active learning setting where a learner is presented with a pool S of n unlabeled examples belonging to a domain X. We study more general region queries that allow the learner to pick a subset of the domain T subset X and a target label y. We show that given any hypothesis class H with VC dimension d, one can design a region query family Q with VC dimension O(d) such that for every set of n examples S subset X and every h* in H, a learner can submit O(d log n) queries from Q to a
  arXiv  Detail & Related papers  (2024-05-13T17:13:32Z)
• Deep Unlearning: Fast and Efficient Gradient-free Approach to Class Forgetting [9.91998873101083]
  We introduce a novel class unlearning algorithm designed to strategically eliminate specific classes from the learned model. Our algorithm exhibits competitive unlearning performance and resilience against Membership Inference Attacks (MIA)
  arXiv  Detail & Related papers  (2023-12-01T18:29:08Z)
• Tight Bounds for Machine Unlearning via Differential Privacy [0.7252027234425334]
  We consider the so-called "right to be forgotten" by requiring that a trained model should be able to "unlearn" a number of points from the training data. We obtain tight bounds on the deletion capacity achievable by DP-based machine unlearning algorithms.
  arXiv  Detail & Related papers  (2023-09-02T09:55:29Z)
• Ticketed Learning-Unlearning Schemes [57.89421552780526]
  We propose a new ticketed model for learning--unlearning. We provide space-efficient ticketed learning--unlearning schemes for a broad family of concept classes.
  arXiv  Detail & Related papers  (2023-06-27T18:54:40Z)
• A Survey of Learning on Small Data: Generalization, Optimization, and Challenge [101.27154181792567]
  Learning on small data that approximates the generalization ability of big data is one of the ultimate purposes of AI. This survey follows the active sampling theory under a PAC framework to analyze the generalization error and label complexity of learning on small data. Multiple data applications that may benefit from efficient small data representation are surveyed.
  arXiv  Detail & Related papers  (2022-07-29T02:34:19Z)
• Vertical Machine Unlearning: Selectively Removing Sensitive Information From Latent Feature Space [21.8933559159369]
  We investigate a vertical unlearning mode, aiming at removing only sensitive information from latent feature space. We introduce intuitive and formal definitions for this unlearning and show its relationship with existing horizontal unlearning. We propose an approximation with an upper bound to estimate it, with rigorous theoretical analysis.
  arXiv  Detail & Related papers  (2022-02-27T05:25:15Z)
• Meta Clustering Learning for Large-scale Unsupervised Person Re-identification [124.54749810371986]
  We propose a "small data for big task" paradigm dubbed Meta Clustering Learning (MCL) MCL only pseudo-labels a subset of the entire unlabeled data via clustering to save computing for the first-phase training. Our method significantly saves computational cost while achieving a comparable or even better performance compared to prior works.
  arXiv  Detail & Related papers  (2021-11-19T04:10:18Z)
• Learning the hypotheses space from data through a U-curve algorithm: a statistically consistent complexity regularizer for Model Selection [0.0]
  This paper proposes a data-driven systematic, consistent and non-exhaustive approach to Model Selection. Our main contributions are a data-driven general learning algorithm to perform regularized Model Selection on $mathbbL(mathcalH)$. A remarkable consequence of this approach are conditions under which a non-exhaustive search of $mathbbL(mathcalH)$ can return an optimal solution.
  arXiv  Detail & Related papers  (2021-09-08T18:28:56Z)
• High-dimensional separability for one- and few-shot learning [58.8599521537]
  This work is driven by a practical question, corrections of Artificial Intelligence (AI) errors. Special external devices, correctors, are developed. They should provide quick and non-iterative system fix without modification of a legacy AI system. New multi-correctors of AI systems are presented and illustrated with examples of predicting errors and learning new classes of objects by a deep convolutional neural network.
  arXiv  Detail & Related papers  (2021-06-28T14:58:14Z)
• Learnable Subspace Clustering [76.23527400396151]
  We develop a learnable subspace clustering paradigm to efficiently solve the large-scale subspace clustering problem. The key idea is to learn a parametric function to partition the high-dimensional subspaces into their underlying low-dimensional subspaces. To the best of our knowledge, this paper is the first work to efficiently cluster millions of data points among the subspace clustering methods.
  arXiv  Detail & Related papers  (2020-04-09T12:53:28Z)

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.