# Hessian-Free Online Certified Unlearning

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- First posted on arXiv 2 Apr 2024.

## Placed in

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

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

- [Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions](https://mlsanity.com/paper/2409.09778/) (2024)
- [Missing-by-Design: Certifiable Modality Deletion for Revocable Multimodal Sentiment Analysis](https://mlsanity.com/paper/2602.16144/) (2026)
- [Certified Unlearning in Decentralized Federated Learning](https://mlsanity.com/paper/2601.06436/) (2026)
- [Efficient Unlearning with Privacy Guarantees](https://mlsanity.com/paper/2507.04771/) (2025)
- [WARP: Weight Teleportation for Attack-Resilient Unlearning Protocols](https://mlsanity.com/paper/2512.00272/) (2025)
- [Governing AI Forgetting: Auditing for Machine Unlearning Compliance](https://mlsanity.com/paper/2602.14553/) (2026)
- [When Sample Selection Bias Precipitates Model Collapse](https://mlsanity.com/paper/2606.13732/) (2026)
- [Auditing of Unlearning Algorithms](https://mlsanity.com/paper/2607.05898/) (2026)
- [Mo' Memory, Mo' Problems: Stream-Native Machine Unlearning](https://mlsanity.com/paper/2508.10193/) (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)
- [WIN-U: Woodbury-Informed Newton-Unlearning as a retain-free Machine Unlearning Framework](https://mlsanity.com/paper/2604.13438/) (2026)
- [Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses](https://mlsanity.com/paper/2606.01527/) (2026)
- [The Forgetting-Retention Dilemma: Certified Unlearning Theory in Continual Learning](https://mlsanity.com/paper/2606.29832/) (2026)
- [Correlation-Guided Fast Machine Unlearning via Hessian Analysis](https://mlsanity.com/paper/2609.12620/) (2026)
- [One-Step Curvature Probes Miss the Fitting Operator: Retained Capacity and Terminal Null-Space Correction for Continual Learning](https://mlsanity.com/paper/2610.03952/) (2026)
- [Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees](https://mlsanity.com/paper/2610.17993/) (2026)

## Abstract (arXiv)

Machine unlearning strives to uphold the data owners' right to be forgotten by enabling models to selectively forget specific data. Recent advances suggest pre-computing and storing statistics extracted from second-order information and implementing unlearning through Newton-style updates. However, the Hessian matrix operations are extremely costly and previous works conduct unlearning for empirical risk minimizer with the convexity assumption, precluding their applicability to high-dimensional over-parameterized models and the nonconvergence condition. In this paper, we propose an efficient Hessian-free unlearning approach. The key idea is to maintain a statistical vector for each training data, computed through affine stochastic recursion of the difference between the retrained and learned models. We prove that our proposed method outperforms the state-of-the-art methods in terms of the unlearning and generalization guarantees, the deletion capacity, and the time/storage complexity, under the same regularity conditions. Through the strategy of recollecting statistics for removing data, we develop an online unlearning algorithm that achieves near-instantaneous data removal, as it requires only vector addition. Experiments demonstrate that our proposed scheme surpasses existing results by orders of magnitude in terms of time/storage costs with millisecond-level unlearning execution, while also enhancing test accuracy.