Machine Unlearning as Private Retroactive Algorithms
A cs.CR paper defines private retroactive algorithms, showing machine unlearning is a data-maintenance problem and giving DP constructions for linear statistics, clustering, histograms.
The paper argues that machine unlearning's requirement to emulate retraining from scratch carries no meaningful privacy semantics against adversaries observing sequences of releases, recasting it as a data-maintenance question addressed by retroactive algorithms. It defines private retroactive algorithms, combining retroactivity with differential privacy under continual observation. Constructions achieve privacy and retroactivity at no asymptotic cost over privacy alone for linear statistics, clustering, and histograms, alongside impossibility results.
- Recasts machine unlearning as retroactive data maintenance, not privacy per se
- New definition couples retroactivity with differential privacy under continual observation
- Constructions for linear statistics, clustering, histograms at no asymptotic cost
- Includes impossibility results bounding private retroactive computation
Full article146 words · extracted from arxiv.org · click to collapse
Machine unlearning typically aims to emulate retraining from scratch: upon a deletion request, the unlearning algorithm should produce an outcome that would have been obtained had the deleted point never been included. Recent work has shown that this emulation requirement carries no meaningful privacy semantics against an adversary who observes a sequence of releases. Machine unlearning is thus not a privacy question per se, but rather a data maintenance question, which is precisely the subject of retroactive algorithms. These are algorithms supporting modifications of past operations, guaranteeing that all subsequent answers reflect the revised history as if it had always been in force. We put forward a definition of private retroactive algorithms, combining the retroactivity requirement with differential privacy under continual observation. We present constructions achieving both privacy and retroactivity at no asymptotic cost over privacy alone for linear statistics, clustering, and histograms, alongside impossibility results.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.05329