Efficient machine unlearning with minimax optimality

Jingyi Xie; Linjun Zhang; Sai Li

stat.MLApr 7, 2026

Efficient machine unlearning with minimax optimality

Authors: Jingyi Xie, Linjun Zhang, Sai Li

Organizations: Institute of Statistics and Big Data, Renmin University of China, Beijing 100872, China · Department of Statistics, Rutgers University, Piscataway, NJ 08854, USA · Department of Statistics and Data Science, Tsinghua University, Beijing 100084, China

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.

Figures & tables

\displaystyle\hat{\bm{\theta}}^{(\textup{unl})}_{r,t}=\hat{\bm{\theta}}^{(\textup{unl})}_{r,t-1}-\alpha\left\{\frac{N_{r}}{\tilde{n}_{r}}\dot{\ell}(\hat{\bm{\theta}}^{(\textup{unl})}_{r,t-1};\widetilde{\mathcal{D}}_{r})-\frac{N_{r}}{\tilde{n}_{r}}\dot{\ell}(\hat{\bm{\theta}}_{p};\widetilde{\mathcal{D}}_{r})-\dot{\ell}(\hat{\bm{\theta}}_{p};\mathcal{D}_{f})\right\},

(7)

Algorithm 1 Gradient descent algorithm for the unlearning estimate

\displaystyle\hat{\bm{\theta}}_{r}^{(\textup{uls})}=\argmin_{\bm{\theta}\in\mathbb{R}^{p}}\left\{-\frac{\omega_{f}}{N_{f}}\ell(\bm{\theta};\mathcal{D}_{f})+(\hat{\bm{\theta}}_{p}-\bm{\theta})^{\top}\widetilde{\Sigma}_{p}(\hat{\bm{\theta}}_{p}-\bm{\theta})\right\},

(9)

Algorithm 2 Proposed ULS estimator

Figure 1: Boxplots of the estimation errors for five unlearning estimators: $\mathring{\bm{\theta}}_{r}^{(\textup{rtr})}$ (gray without hatch), $\hat{\bm{\theta}}_{p}$ (gray with backward-slash hatch), $\hat{\bm{\theta}}_{r}^{(\textup{diff})}$ (blue with vertical-line hatch), $\tilde{\bm{\theta}}_{r}^{(\textup{ols})}$ (yellow with horizontal-line hatch), and $\hat{\bm{\theta}}_{r}^{(\textup{uls})}$ (red with forward-slash hatch). The three panels correspond to experimental settings (a), (b), and (c), with $N_{r}=20000$ and $N_{f}=1000$ . Each setting is replicated with 1000 Monte Carlo trials.

Figure 2: Boxplots of the estimation errors for five unlearning estimators: $\mathring{\bm{\theta}}_{r}^{(\textup{rtr})}$ (gray without hatch), $\hat{\bm{\theta}}_{p}$ (gray with backward-slash hatch), $\hat{\bm{\theta}}_{r}^{(\textup{diff})}$ (blue with vertical-line hatch), $\tilde{\bm{\theta}}_{r}^{(\textup{ols})}$ (yellow with horizontal-line hatch), and $\hat{\bm{\theta}}_{r}^{(\textup{uls})}$ (red with forward-slash hatch). The three panels correspond to experimental settings (a), (b), and (c), with $N_{r}=20000$ and $N_{f}=2000$ . Each setting is replicated with 1000 Monte Carlo trials.

	$\tilde{n}_{r}/N_{r}$			$p$			$\delta$
	0.1	0.2	0.3	10	50	100	1	2	3
Average Coverage
ULS	0.935	0.957	0.960	0.957	0.957	0.952	0.947	0.957	0.949
OLS	0.945	0.952	0.942	0.951	0.952	0.942	0.954	0.952	0.960
Average SD $(\times 10^{-2})$
ULS	$0.81$	$0.75$	$0.73$	$0.74$	$0.75$	$0.76$	$0.72$	$0.75$	$0.80$

Table 1: Inference results for settings (a), (b), and (c) with

N_{r}=20000

and

N_{f}=1000

. Each setting is replicated with 1000 Monte Carlo trials.

Estimator	$\mathring{\bm{\theta}}_{r}^{(\textup{rtr})}$	$\hat{\bm{\theta}}_{r}^{(\textup{pru})}$	$\hat{\bm{\theta}}_{r}^{(\textup{diff})}$	$\tilde{\bm{\theta}}_{r}^{(\textup{ols})}$	$\hat{\bm{\theta}}_{r}^{(\textup{uls})}$	$\hat{\bm{\theta}}_{r}^{(\textup{uls}+)}$
Running Time (s)	0.44	90.08	25.60	0.12	0.25	25.20

Table 2: Average running time per estimator over 20 folds on the Yelp dataset. For

\hat{\bm{\theta}}_{r}^{(\textup{diff})}

and

\hat{\bm{\theta}}_{r}^{(\textup{uls}+)}

, running time includes 5-fold cross-validation over 20 candidates for tuning parameter selection. All experiments were conducted on an Intel Xeon Gold 5418Y CPU with 48 physical cores.

Figure 3: Boxplots of mean prediction errors for the Yelp review rating unlearning task under the setting $\tilde{n}_{r}/N_{r}=0.1$ . Each boxplot is based on 20 random splits of training and test samples.

Figure 4: Distribution of the response variable $y$ within the full dataset $\mathcal{D}$ . The left panel shows the distribution of raw response, which is severely right-skewed. The right panel displays the transformed response $\log_{10}(y)$ , illustrating a significantly reduced scale.

Figure 5: Boxplots of mean prediction errors for the UK Biobank hospital episode unlearning task under the setting $\tilde{n}_{r}/N_{r}=0.1$ . Each boxplot is based on 20 random splits of training and test samples.

$\tilde{n}_{r}/N_{r}$	0.1	0.2	0.3
ULS	$0.158\pm 0.029$	$0.163\pm 0.026$	$0.159\pm 0.025$
OLS	$0.181\pm 0.078$	$0.172\pm 0.053$	$0.147\pm 0.044$

Table 3: Inference results for the coefficient of the “one or more operative procedures performed” covariate. The table reports the 95% confidence intervals produced by ULS and OLS method across

\tilde{n}_{r}/N_{r}\in\{0.1,0.2,0.3\}

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Boxplots of the estimation errors for three unlearning estimators: $\hat{\bm{\theta}}_{r}^{(\textup{uls})}$ (yellow with horizontal-line hatch), $\hat{\bm{\theta}}_{r,T}^{(\textup{uls})}$ (orange with vertical-line hatch) and $\hat{\bm{\theta}}_{r}^{(\textup{uls}+)}$ (dark orange with plus-sign hatch). The three panels correspond to experimental settings (a), (b), and (c), with fixed $N_{r}=20000$ and $N_{f}=1000$ . Each setting is replicated with 1000 Monte Carlo trials.

Figure 7: Boxplots of the estimation errors for three unlearning estimators: $\hat{\bm{\theta}}_{r}^{(\textup{uls})}$ (red with forward-slash hatch), $\hat{\bm{\theta}}_{r,T}^{(\textup{uls})}$ (dark orange solid) and $\hat{\bm{\theta}}_{r}^{(\textup{uls}+)}$ (orange with cross-hatch). The three panels correspond to experimental settings (a), (b), and (c), with fixed $N_{r}=20000$ and $N_{f}=2000$ . Each setting is replicated with 1000 Monte Carlo trials.

	$\tilde{n}_{r}/N_{r}$			$p$			$\delta$
	0.1	0.2	0.3	10	50	100	1	2	3
Average Coverage
ULS	0.954	0.950	0.951	0.948	0.950	0.942	0.957	0.950	0.943
OLS	0.963	0.947	0.956	0.951	0.947	0.946	0.939	0.947	0.944
Average SD $(\times 10^{-2})$
ULS	$0.99$	$0.84$	$0.78$	$0.83$	$0.84$	$0.85$	$0.75$	$0.84$	$0.97$

Appendix

Table 4: Inference results for setting (a), (b) and (c) with

N_{r}=20000

and

N_{f}=2000

. Each setting is replicated with 1000 Monte Carlo trials.

Figure 8: Boxplots of mean prediction errors for the Yelp review rating prediction unlearning task. $\hat{\bm{\theta}}_{r}^{(\textup{diff})}$ , $\tilde{\bm{\theta}}_{r}^{(\textup{ols})}$ , and $\hat{\bm{\theta}}_{r}^{(\textup{uls})}$ are evaluated under the retained subsample proportion $\tilde{n}_{r}/N_{r}=0.2$ . Each boxplot is based on 20 random splits of training and test samples.

Figure 9: Boxplots of mean prediction errors for the Yelp review rating prediction unlearning task. $\hat{\bm{\theta}}_{r}^{(\textup{diff})}$ , $\tilde{\bm{\theta}}_{r}^{(\textup{ols})}$ , and $\hat{\bm{\theta}}_{r}^{(\textup{uls})}$ are evaluated under the retained subsample proportion $\tilde{n}_{r}/N_{r}=0.3$ . Each boxplot is based on 20 random splits of training and test samples.

Figure 10: Boxplots of mean prediction errors for the UK Biobank hospital episode unlearning task. $\hat{\bm{\theta}}_{r}^{(\textup{diff})}$ , $\tilde{\bm{\theta}}_{r}^{(\textup{ols})}$ , and $\hat{\bm{\theta}}_{r}^{(\textup{uls})}$ are evaluated under the retained subsample proportion $\tilde{n}_{r}/N_{r}=0.2$ . Each boxplot is based on 20 random splits of training and test samples.

Figure 11: Boxplots of mean prediction errors for the UK Biobank hospital episode unlearning task. $\hat{\bm{\theta}}_{r}^{(\textup{diff})}$ , $\tilde{\bm{\theta}}_{r}^{(\textup{ols})}$ , and $\hat{\bm{\theta}}_{r}^{(\textup{uls})}$ are evaluated under the retained subsample proportion $\tilde{n}_{r}/N_{r}=0.3$ . Each boxplot is based on 20 random splits of training and test samples.

Machine Unlearning

Machine unlearning removes the influence of selected data or concepts from trained models while preserving useful behavior and avoiding full retraining.

See all 354 papers

Jun 1, 2026

Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses

Machine unlearning is motivated by legal and user-facing requirements to remove the influence of individuals' data from trained models, such as the right to be forgotten. Prior work has developed algorithms and error bounds for unlearning in smooth strongly convex stochastic optimization but the fundamental statistical cost of unlearning has remained unclear. We nearly resolve this problem by proving upper and lower bounds on the excess population risk of approximate

(\varepsilon, δ)

-unlearning; our bounds are tight up to a condition-number factor. For mean estimation over the unit ball, our upper and lower bounds match. In fact, our algorithm achieves

\varepsilon

-unlearning, which implies a notable separation between differential privacy and unlearning:

(\varepsilon, δ)

-unlearning has no statistical advantage over pure

\varepsilon

-unlearning. The optimal rate is the usual sampling error plus an unlearning penalty that interpolates between the retraining from scratch rate and an exponentially smaller term as

\varepsilon/d

grows, where

d

is the dimension of the model. The retraining penalty dominates the sampling error for large unlearning requests. In particular, retraining from scratch is information theoretically optimal up to

\varepsilon \lesssim d

. On the other hand, for

\varepsilon \gg d

and large unlearning requests, our

\varepsilon

-unlearning algorithm offers an exponential accuracy improvement over retraining the model from scratch and differentially private baselines.

Matthew Regehr, Gautam Kamath, Andrew Lowy

University of Waterloo · University of Waterloo and Vector Institute · CISPA Helmholtz Center for Information Security

Statistical Learning Theory Machine Unlearning

Ask PDF

Jul 7, 2025

Efficient Unlearning with Privacy Guarantees

Privacy protection laws, such as the GDPR, grant individuals the right to request the forgetting of their personal data not only from databases but also from machine learning (ML) models trained on them. Machine unlearning has emerged as a practical means to facilitate model forgetting of data instances seen during training. Although some existing machine unlearning methods guarantee exact forgetting, they are typically costly in computational terms. On the other hand, more affordable methods do not offer forgetting guarantees and are applicable only to specific ML models. In this paper, we present efficient unlearning with privacy guarantees (EUPG), a novel machine unlearning framework that offers formal privacy guarantees to individuals whose data are being unlearned. EUPG involves pre-training ML models on data protected using privacy models, and it enables {\em efficient unlearning with the privacy guarantees offered by the privacy models in use}. Through empirical evaluation on four heterogeneous data sets protected with

k

-anonymity and

ε

-differential privacy as privacy models, our approach demonstrates utility and forgetting effectiveness comparable to those of exact unlearning methods, while significantly reducing computational and storage costs. Our code is available at https://github.com/najeebjebreel/EUPG.

Josep Domingo-Ferrer, Najeeb Jebreel, David Sánchez

1CYBERCAT (Center for Cybersecurity Research of2026 Catalonia), ComSCIAM-Center for Computational Science and Applied Mathematics, Department of Computer EngineeringJun and Mathematics, Universitat Rovira i Virgili, Av. Pa¨ısos26 Catalans 26, E-43007 Tarragona, Catalonia

Privacy-Preserving ML Machine Unlearning

Ask PDF

Aug 17, 2026

Learning to Unlearn: Machine Unlearning via Learning the Unlearning Behaviors

Various machine unlearning techniques have been developed in response to privacy legislation requirements, enabling individuals to exercise their legal right to have their data

D_f

removed from a machine learning model. This process is typically accomplished via the use of an unlearning function denoted as

U

. Existing methods focus on designing an intricate

U

to unlearn

D_f \subset D

from a previous model

A(D)

, so that the unlearned model performs as closely as possible to the retrained model

A(D \setminus D_f)

. However, these methods often suffer from high computational costs when dealing with massive training data, as the complex structures of

U

become a bottleneck even for models with fewer parameters. Inspired by Learning to Optimize, we introduce the first learning-based model-agnostic approach, Learning-to-UnLearn (L2UL). Our core insight is to shift from manually designing

U

to learning the unlearning behaviors from a distribution perspective, thereby acquiring a simple and efficient

U

via learning. Our experimental results demonstrate that the accuracy achieved by L2UL is comparable to that of retraining while exhibiting impressive efficiency, particularly in data-intensive scenarios. Furthermore, we validate the performance and scalability of our method on larger models ResNet.

Hang Zhang, Kaifeng Zhang, Yixiao Ma +3

State Key Laboratory for Novel Software Technology Nanjing University Nanjing, China · Centre for Cyber Resilience and Trust Deakin University Burwood, VIC, Australia

Machine Unlearning Privacy-Preserving ML

Ask PDF

Abstract

Machine Unlearning

Explore similar work

Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses

Efficient Unlearning with Privacy Guarantees

Learning to Unlearn: Machine Unlearning via Learning the Unlearning Behaviors