Why Forget-Only Unlearning Needs Memorization

TL;DR

Forget-only unlearning, where a model must delete specific data without access to training data, is not always feasible with standard models. The paper shows that models must retain more information than typical training requires to support arbitrary deletions, with memory requirements potentially matching the full dataset size. This reveals a fundamental trade-off between efficient training and effective unlearning.

Why It Matters

As data privacy regulations grow, the ability to reliably delete data from models is critical. This work demonstrates that standard machine learning models are inherently unsuitable for unlearning without additional memory, forcing a reevaluation of model design for compliance and trustworthiness.

Key Findings

• Forget-only unlearning cannot always succeed because identical models trained on different datasets may require different outputs after deletion.
• Lower bounds on unlearning accuracy depend on the learning algorithm and show that perfect unlearning is impossible without retaining more data than standard training preserves.
• Even simple models like threshold learners may need to memorize the entire training dataset to support arbitrary deletions, despite learning only a single boundary point.