# Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 19 of its 28 references that are in the map.
- First posted on arXiv 1 Jun 2026.

## Placed in

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

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

- [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)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [The Utility and Complexity of in- and out-of-Distribution Machine Unlearning](https://mlsanity.com/paper/2412.09119/) (2024)
- [Tight Bounds for Machine Unlearning via Differential Privacy](https://mlsanity.com/paper/2309.00886/) (2023)
- [Hessian-Free Online Certified Unlearning](https://mlsanity.com/paper/2404.01712/) (2024)
- [Certified Machine Unlearning via Noisy Stochastic Gradient Descent](https://mlsanity.com/paper/2403.17105/) (2024)
- [When to Forget? Complexity Trade-offs in Machine Unlearning](https://mlsanity.com/paper/2502.17323/) (2025)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)

## Abstract (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.