Efficient machine unlearning with minimax optimality

• URL: http://arxiv.org/abs/2604.05669v1
• Date: Tue, 07 Apr 2026 10:09:58 GMT
• Title: Efficient machine unlearning with minimax optimality
• Abstract summary: Machine unlearning aims to eliminate the influence of specific data subsets without the cost of full retraining.<n>We propose a statistical framework for machine unlearning with generic loss functions and theoretical guarantees.<n>Our results reveal that the estimation error decomposes into an oracle term and an unlearning cost determined by the forget proportion and the forget model bias.
• Score: 23.988995429722383
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There is a growing demand for efficient data removal to comply with regulations like the GDPR and to mitigate the influence of biased or corrupted data. This has motivated the field of machine unlearning, which aims to eliminate the influence of specific data subsets without the cost of full retraining. In this work, we propose a statistical framework for machine unlearning with generic loss functions and establish theoretical guarantees. For squared loss, especially, we develop Unlearning Least Squares (ULS) and establish its minimax optimality for estimating the model parameter of remaining data when only the pre-trained estimator, forget samples, and a small subsample of the remaining data are available. Our results reveal that the estimation error decomposes into an oracle term and an unlearning cost determined by the forget proportion and the forget model bias. We further establish asymptotically valid inference procedures without requiring full retraining. Numerical experiments and real-data applications demonstrate that the proposed method achieves performance close to retraining while requiring substantially less data access.

Related papers

• Can Small Training Runs Reliably Guide Data Curation? Rethinking Proxy-Model Practice [109.9635246405237]
  We show that the experiment conclusions about data quality can flip with even minor adjustments to training hyper parameters.<n>We introduce a simple patch to the evaluation protocol: using reduced learning rates for proxy model training.<n> Empirically, we validate this approach across 23 data recipes covering four critical dimensions of data curation.
  arXiv  Detail & Related papers  (2025-12-30T23:02:44Z)
• Density-Aware Farthest Point Sampling [2.9434930072968584]
  We introduce "Density-Aware Farthest Point Sampling" (DA-FPS), a novel sampling method.<n>We prove that DA-FPS provides approximate minimizers for a data-driven estimation of the weighted fill distance.<n>The results demonstrate that DA-FPS significantly reduces the mean absolute prediction error compared to other sampling strategies.
  arXiv  Detail & Related papers  (2025-09-16T16:19:14Z)
• When to Forget? Complexity Trade-offs in Machine Unlearning [23.507879460531264]
  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.
  arXiv  Detail & Related papers  (2025-02-24T16:56:27Z)
• DUPRE: Data Utility Prediction for Efficient Data Valuation [49.60564885180563]
  Cooperative game theory-based data valuation, such as Data Shapley, requires evaluating the data utility and retraining the ML model for multiple data subsets.<n>Our framework, textttDUPRE, takes an alternative yet complementary approach that reduces the cost per subset evaluation by predicting data utilities instead of evaluating them by model retraining.<n>Specifically, given the evaluated data utilities of some data subsets, textttDUPRE fits a emphGaussian process (GP) regression model to predict the utility of every other data subset.
  arXiv  Detail & Related papers  (2025-02-22T08:53:39Z)
• Pseudo-Probability Unlearning: Towards Efficient and Privacy-Preserving Machine Unlearning [59.29849532966454]
  We propose PseudoProbability Unlearning (PPU), a novel method that enables models to forget data to adhere to privacy-preserving manner. Our method achieves over 20% improvements in forgetting error compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-11-04T21:27:06Z)
• Hessian-Free Online Certified Unlearning [8.875278412741695]
  We develop an online unlearning algorithm that achieves near-instantaneous data removal.<n>We prove that our proposed method outperforms the state-of-the-art methods in terms of the unlearning and generalization guarantees.
  arXiv  Detail & Related papers  (2024-04-02T07:54:18Z)
• Self-Supervised Dataset Distillation for Transfer Learning [77.4714995131992]
  We propose a novel problem of distilling an unlabeled dataset into a set of small synthetic samples for efficient self-supervised learning (SSL) We first prove that a gradient of synthetic samples with respect to a SSL objective in naive bilevel optimization is textitbiased due to randomness originating from data augmentations or masking. We empirically validate the effectiveness of our method on various applications involving transfer learning.
  arXiv  Detail & Related papers  (2023-10-10T10:48:52Z)
• On minimizing the training set fill distance in machine learning regression [0.552480439325792]
  We study a data selection approach that aims to minimize the fill distance of the selected set. We show that selecting training sets with the FPS can also increase model stability for the specific case of Gaussian kernel regression approaches.
  arXiv  Detail & Related papers  (2023-07-20T16:18:33Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  Real-world machine learning deployments are characterized by mismatches between the source (training) and target (test) distributions. In this work, we investigate methods for predicting the target domain accuracy using only labeled source data and unlabeled target data. We propose Average Thresholded Confidence (ATC), a practical method that learns a threshold on the model's confidence, predicting accuracy as the fraction of unlabeled examples.
  arXiv  Detail & Related papers  (2022-01-11T23:01:12Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)

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.