Machine Unlearning Reframed as Private Retroactive Algorithms, at No Asymptotic Cost Over Privacy Alone

arXiv 2609.05329·low signalXBlueskyLinkedInCopy link

arXiv 2609.05329 argues the standard 'emulate retraining from scratch' goal for machine unlearning carries no meaningful privacy semantics against an adversary observing a sequence of releases, making unlearning a data-maintenance question rather than a privacy one. The paper defines private retroactive algorithms by combining the retroactivity requirement — all subsequent answers reflect the revised history as if it had always been in force — with differential privacy under continual observation. Constructions achieve both properties at no asymptotic cost over privacy alone for linear statistics, clustering, and histograms, alongside impossibility results.