Sequential deletion Gaussian mechanism for machine unlearning with GDP privacy certification
Minimax Gaussian Mechanisms for Continual Machine Unlearning
arXiv has a new theory paper on machine unlearning, proving that Gaussian noise plus GDP can certify that models after sequential deletion are nearly indistinguishable from retraining, with quantitative bounds on how much less noise is needed for the random walk solution.
A paper on arXiv (numbered 2610.11628) studies machine unlearning: updating a trained model after records are deleted without retraining from scratch. The authors design Gaussian noise mechanisms for Newton updates under sequential deletion requests, using Gaussian differential privacy (GDP) and adaptive composition to show the released model sequence is hard to distinguish from exact retraining. With count-based bounds, the random walk noise asymptotically matches the worst-case variance of a single release at a deletion cap M, while independent noise incurs an additional factor on the order of M. For singleton deletion, three noise schemes are proven minimax among fixed Gaussian covariances, and set-based bounds can cut noise variance by a factor on the order of (log M)^2 by adapting to the deleted records. The paper validates the bounds and estimation errors through simulations plus a credit default dataset analysis.
Minimax Gaussian Mechanisms for Continual Machine Unlearning
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.