Why Forget-Only Unlearning Needs Memorization: Lower Bounds on Machine Unlearning

Forum topic · 小凯 · 2026-10-09

Summary

A new arXiv paper (2610.10519) by Luka Radić, Vikrant Singhal, and Amartya Sanyal examines forget-only machine unlearning, where a deletion algorithm must approximate retraining from scratch using only the trained model and the examples to forget—no retained data or extra training information. The authors first show feasibility depends on the learning method: different datasets can yield identical trained models yet demand very different outputs after removing the same samples. From this observation they derive lower bounds on how accurately unlearning can match retraining, instantiated for several standard learning algorithms. They then establish necessary conditions for successful forget-only unlearning, proving lower bounds on how much information about the training data an algorithm must memorize to handle arbitrary deletion requests. For simple threshold learners, the required information can equal the entire dataset—even though ordinary training retains only a single boundary point. The overall conclusion: information discarded during standard training may later be needed for deletion, so models intended for forget-only unlearning may need to retain substantially more information than standard training requires.

Paper Overview

Research area: Machine Learning Authors: Luka Radić, Vikrant Singhal, Amartya Sanyal Published: 2026-10-07 arXiv: 2610.10519

Abstract

Machine unlearning asks for a deletion algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, the authors study forget-only unlearning, where the deletion algorithm receives only the trained model and the examples to forget, with no retained data or extra training information. The central question: is forget-only unlearning always possible?

Key Findings

Feasibility depends on the learning method. Different datasets can produce the exact same trained model, yet after the same forget examples are removed, they require very different outputs—meaning the trained model alone cannot always determine the right unlearning result.
Lower bounds on unlearning accuracy. Building on this observation, the paper derives lower bounds on how accurately forget-only unlearning can match full retraining, and instantiates these bounds for several standard learning algorithms.
Memorization is necessary. The authors also characterize what must hold when forget-only unlearning *does* succeed, deriving lower bounds on how much information about the training data the algorithm must retain to handle arbitrary deletion requests.
Striking example: threshold learners. For simple threshold learners, the required retained information can be as large as the entire dataset—even though ordinary training only preserves a single boundary point.

Implications

The results show that information discarded during ordinary training may later be required for deletion. Consequently, models designed for forget-only unlearning may need to retain more information than standard training would otherwise keep—an important consideration for privacy-compliant ML systems and right-to-be-forgotten implementations.