# Certified Data Removal Under High-dimensional Settings

arXiv: https://arxiv.org/abs/2505.07640 · HTML: https://mlsanity.com/paper/2505.07640/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 30 of its 65 references that are in the map.
- First posted on arXiv 12 May 2025.

## Placed in

- LLM safety and security / [Machine unlearning](https://mlsanity.com/safety/machine-unlearning/)

## Builds on (most cited first, 30 of 30)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Amnesiac Machine Learning](https://mlsanity.com/paper/2010.10981/) (2020)
- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Towards Unbounded Machine Unlearning](https://mlsanity.com/paper/2302.09880/) (2023)
- [Fast Yet Effective Machine Unlearning](https://mlsanity.com/paper/2111.08947/) (2021)
- [When Machine Unlearning Jeopardizes Privacy](https://mlsanity.com/paper/2005.02205/) (2020)
- [Fast Machine Unlearning Without Retraining Through Selective Synaptic Dampening](https://mlsanity.com/paper/2308.07707/) (2023)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Zero-Shot Machine Unlearning](https://mlsanity.com/paper/2201.05629/) (2022)
- [Towards Adversarial Evaluations for Inexact Machine Unlearning](https://mlsanity.com/paper/2201.06640/) (2022)
- [A Swiss Army Infinitesimal Jackknife](https://mlsanity.com/paper/1806.00550/) (2018)
- [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020)
- [Algorithms that Approximate Data Removal: New Results and Limitations](https://mlsanity.com/paper/2209.12269/) (2022)
- [Machine Unlearning Fails to Remove Data Poisoning Attacks](https://mlsanity.com/paper/2406.17216/) (2024)
- [Approximate Message Passing algorithms for rotationally invariant matrices](https://mlsanity.com/paper/2008.11892/) (2020)
- [Machine Unlearning: Taxonomy, Metrics, Applications, Challenges, and Prospects](https://mlsanity.com/paper/2403.08254/) (2024)
- [The Squared-Error of Generalized LASSO: A Precise Analysis](https://mlsanity.com/paper/1311.0830/) (2013)
- [Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions](https://mlsanity.com/paper/1807.02694/) (2018)
- [A Higher-Order Swiss Army Infinitesimal Jackknife](https://mlsanity.com/paper/1907.12116/) (2019)
- [On Optimal Generalizability in Parametric Learning](https://mlsanity.com/paper/1711.05323/) (2017)
- [Error bounds in estimating the out-of-sample prediction error using leave-one-out cross validation in high-dimensions](https://mlsanity.com/paper/2003.01770/) (2020)
- [Does SLOPE outperform bridge regression?](https://mlsanity.com/paper/1909.09345/) (2019)
- [Consistent Parameter Estimation for LASSO and Approximate Message Passing](https://mlsanity.com/paper/1511.01017/) (2015)
- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [Can we trust the bootstrap in high-dimension?](https://mlsanity.com/paper/1608.00696/) (2016)

## Built on by (most cited first, 6 of 6)

- [Gaussian Certified Unlearning in High Dimensions: A Hypothesis Testing Approach](https://mlsanity.com/paper/2510.13094/) (2025)
- [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026)
- [Newfluence: Boosting Model interpretability and Understanding in High Dimensions](https://mlsanity.com/paper/2507.11895/) (2025)
- [Forgetting-MarI: LLM Unlearning via Marginal Information Regularization](https://mlsanity.com/paper/2511.11914/) (2025)
- [A Robust Certified Machine Unlearning Method Under Distribution Shift](https://mlsanity.com/paper/2601.06967/) (2026)
- [Variance-Reduced (varepsilon,δ)-Unlearning using Forget Set Gradients](https://mlsanity.com/paper/2602.14938/) (2026)

## Abstract (arXiv)

Machine unlearning focuses on the computationally efficient removal of specific training data from trained models, ensuring that the influence of forgotten data is effectively eliminated without the need for full retraining. Despite advances in low-dimensional settings, where the number of parameters ( p ) is much smaller than the sample size ( n ), extending similar theoretical guarantees to high-dimensional regimes remains challenging. We propose an unlearning algorithm that starts from the original model parameters and performs a theory-guided sequence of Newton steps ( T ∈  1,2). After this update, carefully scaled isotropic Laplacian noise is added to the estimate to ensure that any (potential) residual influence of forget data is completely removed. We show that when both ( n, p → ∞ ) with a fixed ratio ( n/p ), significant theoretical and computational obstacles arise due to the interplay between the complexity of the model and the finite signal-to-noise ratio. Finally, we show that, unlike in low-dimensional settings, a single Newton step is insufficient for effective unlearning in high-dimensional problems -- however, two steps are enough to achieve the desired certifiebility. We provide numerical experiments to support the certifiability and accuracy claims of this approach.