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.