Descent-to-Delete: Gradient-Based Methods for Machine Unlearning

• URL: http://arxiv.org/abs/2007.02923v1
• Date: Mon, 6 Jul 2020 17:54:35 GMT
• Title: Descent-to-Delete: Gradient-Based Methods for Machine Unlearning
• Authors: Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi
• Abstract summary: We give the first data deletion algorithms that are able to handle an arbitrarily long sequence of adversarial updates. We introduce several new conceptual distinctions: for example, we can ask that after a deletion, the entire state maintained by the optimization algorithm is statistically indistinguishable from the state that would have resulted had we retrained.
• Score: 15.647473776016042
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the data deletion problem for convex models. By leveraging techniques from convex optimization and reservoir sampling, we give the first data deletion algorithms that are able to handle an arbitrarily long sequence of adversarial updates while promising both per-deletion run-time and steady-state error that do not grow with the length of the update sequence. We also introduce several new conceptual distinctions: for example, we can ask that after a deletion, the entire state maintained by the optimization algorithm is statistically indistinguishable from the state that would have resulted had we retrained, or we can ask for the weaker condition that only the observable output is statistically indistinguishable from the observable output that would have resulted from retraining. We are able to give more efficient deletion algorithms under this weaker deletion criterion.

Related papers

• The Right to be Forgotten in Pruning: Unveil Machine Unlearning on Sparse Models [18.728123679646398]
  Machine unlearning aims to efficiently eliminate the memory about deleted data from trained models and address the right to be forgotten.<n>In this paper, we empirically find that the deleted data has an impact on the pruned topology in a sparse model.<n>Motivated by the observation and the right to be forgotten, we define a new terminology un-pruning" to eliminate the impact of deleted data on model pruning.
  arXiv  Detail & Related papers  (2025-07-24T18:13:26Z)
• Instance-dependent Early Stopping [57.912273923450726]
  We propose an Instance-dependent Early Stopping (IES) method that adapts the early stopping mechanism from the entire training set to the instance level. IES considers an instance as mastered if the second-order differences of its loss value remain within a small range around zero. IES can reduce backpropagation instances by 10%-50% while maintaining or even slightly improving the test accuracy and transfer learning performance of a model.
  arXiv  Detail & Related papers  (2025-02-11T13:34:09Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Fast constrained sampling in pre-trained diffusion models [77.21486516041391]
  We propose an algorithm that enables fast and high-quality generation under arbitrary constraints. During inference, we can interchange between gradient updates computed on the noisy image and updates computed on the final, clean image. Our approach produces results that rival or surpass the state-of-the-art training-free inference approaches.
  arXiv  Detail & Related papers  (2024-10-24T14:52:38Z)
• Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions [11.955062839855334]
  Machine unlearning algorithms aim to efficiently data from a model without it from scratch.<n> certified machine unlearning is a strong theoretical guarantee based on differential generalization.
  arXiv  Detail & Related papers  (2024-09-15T15:58:08Z)
• CItruS: Chunked Instruction-aware State Eviction for Long Sequence Modeling [52.404072802235234]
  We introduce Chunked Instruction-aware State Eviction (CItruS), a novel modeling technique that integrates the attention preferences useful for a downstream task into the eviction process of hidden states. Our training-free method exhibits superior performance on long sequence comprehension and retrieval tasks over several strong baselines under the same memory budget.
  arXiv  Detail & Related papers  (2024-06-17T18:34:58Z)
• Efficient and Generalizable Certified Unlearning: A Hessian-free Recollection Approach [8.875278412741695]
  Machine unlearning strives to uphold the data owners' right to be forgotten by enabling models to selectively forget specific data. We develop an algorithm that achieves near-instantaneous unlearning as it only requires a vector addition operation.
  arXiv  Detail & Related papers  (2024-04-02T07:54:18Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  We propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.
  arXiv  Detail & Related papers  (2024-02-24T09:47:46Z)
• A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints [87.08677547257733]
  Neuro-symbolic AI bridges the gap between purely symbolic and neural approaches to learning. We show how to maximize the likelihood of a symbolic constraint w.r.t the neural network's output distribution. We also evaluate our approach on Sudoku and shortest-path prediction cast as autoregressive generation.
  arXiv  Detail & Related papers  (2023-12-06T20:58:07Z)
• Late Stopping: Avoiding Confidently Learning from Mislabeled Examples [61.00103151680946]
  We propose a new framework, Late Stopping, which leverages the intrinsic robust learning ability of DNNs through a prolonged training process. We empirically observe that mislabeled and clean examples exhibit differences in the number of epochs required for them to be consistently and correctly classified. Experimental results on benchmark-simulated and real-world noisy datasets demonstrate that the proposed method outperforms state-of-the-art counterparts.
  arXiv  Detail & Related papers  (2023-08-26T12:43:25Z)
• Algorithms that Approximate Data Removal: New Results and Limitations [2.6905021039717987]
  We study the problem of deleting user data from machine learning models trained using empirical risk minimization. We develop an online unlearning algorithm that is both computationally and memory efficient.
  arXiv  Detail & Related papers  (2022-09-25T17:20:33Z)
• Adaptive Machine Unlearning [21.294828533009838]
  SIS flexible retraining aim to remove deleted data points from models at a cheaper computational retraining than fully trained models. We show how prior work gives guarantees for non-adaptive deletion sequences, giving strong provable deletion guarantees for extremely strong algorithms.
  arXiv  Detail & Related papers  (2021-06-08T14:11:53Z)
• Online Forgetting Process for Linear Regression Models [18.336825781223034]
  Motivated by the EU's "Right To Be Forgotten" regulation, we initiate a study of statistical data deletion problems. We propose a deletion-aware algorithm textttFIFD-OLS for the low dimensional case, and witness a catastrophic rank swinging phenomenon. As a remedy, we propose the textttFIFD-Adaptive Ridge algorithm with a novel online regularization scheme.
  arXiv  Detail & Related papers  (2020-12-03T02:57:53Z)
• Compressive Summarization with Plausibility and Salience Modeling [54.37665950633147]
  We propose to relax the rigid syntactic constraints on candidate spans and instead leave compression decisions to two data-driven criteria: plausibility and salience. Our method achieves strong in-domain results on benchmark summarization datasets, and human evaluation shows that the plausibility model generally selects for grammatical and factual deletions.
  arXiv  Detail & Related papers  (2020-10-15T17:07:10Z)
• Tomographic Auto-Encoder: Unsupervised Bayesian Recovery of Corrupted Data [4.725669222165439]
  We propose a new probabilistic method for unsupervised recovery of corrupted data. Given a large ensemble of degraded samples, our method recovers accurate posteriors of clean values. We test our model in a data recovery task under the common setting of missing values and noise.
  arXiv  Detail & Related papers  (2020-06-30T16:18:16Z)

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.