Minimax Gaussian Mechanisms for Continual Machine Unlearning

Qi Kuang; Yin Xia

stat.MLOct 8, 2026

Minimax Gaussian Mechanisms for Continual Machine Unlearning

Authors: Qi Kuang, Yin Xia

Organizations: Department of Statistics and Data Science, Fudan University

Abstract

Machine unlearning updates a trained model after records are deleted, aiming to match exact retraining without repeating the full training procedure. We develop Gaussian mechanisms for Newton updates under sequential deletion requests. Using Gaussian differential privacy (GDP) and its adaptive composition rule, we show that the full sequence of released models is statistically difficult to distinguish from matched exact retraining. To calibrate these mechanisms for empirical risk minimization, we derive upper bounds on the error of the Newton approximation relative to exact retraining and on how this error changes after each deletion batch. Independent Gaussian noise is calibrated using bounds on the full residual at each release, whereas Gaussian random walk noise uses smaller bounds on residual increments. These bounds yield allocations minimizing the worst-case maximum noise variance across releases under the resulting GDP certification constraints. With count-based bounds, the random walk asymptotically matches the worst-case variance of a single release at deletion cap $M$ , while independent noise incurs an additional factor of order $M$ . Set-based bounds can reduce the noise variances by using gradients and Hessians of the deleted records. For singleton deletion, we further show that count-based independent noise, count-based random walk noise, and set-based independent noise are minimax among fixed Gaussian covariances under their respective residual or increment bounds. With set-based bounds, allowing variances to adapt to deleted records can improve on every fixed covariance by a factor of order $(\log M)^2$ on some data sequences. The residual and noise bounds also yield parameter and predictive consistency relative to exact retraining, uniformly over deletion policies. Simulations and a credit default data analysis evaluate bounds, noise variances, and estimation errors.

Figures & tables

Figure 1: Residuals, residual increments, and their bounds along the same deletion paths. Panel (a) compares

\|e_{S_{t}}\|_{2}

r^{\mathrm{set}}(S_{t})

, and

r^{\mathrm{cnt}}(m_{t})

. Panel (b) compares

\|e_{S_{t}}-e_{S_{t-1}}\|_{2}

d^{\mathrm{set}}(S_{t-1},S_{t})

, and

d^{\mathrm{cnt}}(m_{t-1},m_{t})

. Orange curves show observed norms, blue curves show set-based bounds, and dashed gray curves show count-based bounds. Curves are means over

100

independent repetitions. Bands show one standard error of the mean. Both vertical axes use a logarithmic scale. Here

n=10{,}000

and

M=32

Figure 2: Worst-case variance of count-based RW relative to count-based IND. The curve plots

D^{\mathrm{cnt}}/R^{\mathrm{cnt}}

, averaged over

100

independent training samples with a common

\beta^{\star}

and

n=10{,}000

. Error bars show one standard error of the mean but are largely hidden by the circular markers. The horizontal axis is logarithmic with base

2

, and the vertical axis is linear.

Figure 3: Maximum parameter error, prediction error, and GED under random deletion, with

M_{n}=\lfloor\sqrt{n}/2\rfloor

and

\mu=1

. Colors distinguish IND and RW, and line styles distinguish the bounds used. Curves show means over

100

repetitions at each sample size. Bands show one standard error of the mean. Both axes are logarithmic.

Figure 4: Maximum parameter error, prediction error, and GED under adaptive deletion, with

M_{n}=\lfloor\sqrt{n}/2\rfloor

and

\mu=1

. Each method chooses deletions using its own preceding releases. Curves show means over

100

repetitions at each sample size. Bands show one standard error of the mean. Both axes are logarithmic.

Figure 5: Count-based IND and RW with

M_{n}=\lfloor 0.05n^{9/10}\rfloor

and fixed deletion order. Panels show means of the three maximum errors over

100

repetitions. Bands show one standard error of the mean. Both axes are logarithmic.

Figure 6: Parameter error, prediction error, and GED for IND and RW on credit default data, with

n=24{,}000

p=6

M=16

, and

\lambda=\mu=1

. All errors are relative to exact retraining on the retained data. Prediction error and GED average over the test sample and fresh release noise, conditional on the current deletion set and preceding releases.

Figure 7: Maximum noise variance for count-based IND and RW in the separation experiment, with

\mu=1

. Curves show means over

100

repetitions, and bands show one standard error.

Setting	$n$	$M$	Count IND	Count RW	Computable RW	Retraining
Residual	10000	32	2.412	2.417	4.065	20.489
Random	1000	15	0.523	0.507	1.371	2.536
Random	2000	22	0.797	0.784	2.014	4.473
Random	4000	31	1.299	1.289	3.017	9.983
Random	8000	44	2.382	2.371	4.851	25.056
Random	16000	63	4.235	4.228	7.826	69.137

Table 1: Median cumulative running times (ms) for the settings of Figures 1 , 3 , and 6 .

Explore similar work

Jul 7, 2025cs.CR

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 \emph{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

Jun 1, 2026cs.LG

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

May 1, 2026cs.LG

Unlearning Offline Stochastic Multi-Armed Bandits

Machine unlearning aims to unlearn data points from a learned model, offering a principled way to process data-deletion requests and mitigate privacy risks without full retraining. Prior work has mainly studied unsupervised / supervised machine unlearning, leaving unlearning for sequential decision-making systems far less understood. We initiate the first study of a foundational sequential decision-making problem: offline stochastic multi-armed bandits (MAB). We formalize the privacy constraint for offline MAB and measure utility by the post-unlearning decision quality. We conduct a systematic study of both single- and multi-source unlearning scenarios under two data-generation models, the fixed-sample model and the distribution model. For these settings, our algorithmic design is built on two canonical base algorithms: Gaussian mechanism and rollback, and we propose adaptive algorithms that switch between them according to the data regime and privacy constraint. We further introduce a mixing procedure that elucidates the rationale behind these baselines. We provide performance guarantees across the above settings and establish lower bounds under both dataset models. Experiments validate the predicted tradeoffs and demonstrate the effectiveness of the proposed methods.

Zichun Ye, Runqi Wang, Xuchuang Wang +3

Shanghai Jiao Tong University, Shanghai, China · University of Massachusetts Amherst, Massachusetts, United States · University of Washington, Tacoma, United States

Multi-Armed Bandits Robust Multi-Armed Bandits Privacy-Preserving ML Machine Unlearning

Ask PDF