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

Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses
Jun 1, 2026Matthew Regehr, Gautam Kamath, Andrew LowyStatistical Learning Theory Machine Unlearning
University of Waterloo · University of Waterloo and Vector Institute · CISPA Helmholtz Center for Information Security
Efficient Unlearning with Privacy Guarantees
Jul 7, 2025Josep Domingo-Ferrer, Najeeb Jebreel, David SánchezPrivacy-Preserving ML Machine Unlearning
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
Learning to Unlearn: Machine Unlearning via Learning the Unlearning Behaviors
Aug 17, 2026Hang Zhang, Kaifeng Zhang, Yixiao Ma +3Machine Unlearning Privacy-Preserving ML
State Key Laboratory for Novel Software Technology Nanjing University Nanjing, China · Centre for Cyber Resilience and Trust Deakin University Burwood, VIC, Australia

Jun 1, 2026J/K move · Enter open · S save

Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses

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

Open paper AskPDF arXiv

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.

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