Machine Unlearning as Private Retroactive Algorithms

Haim Kaplan; Refael Kohen; Yishay Mansour; Kobbi Nissim; Uri Stemmer

Source-linked AI summary

Machine Unlearning as Private Retroactive Algorithms

Haim Kaplan, Refael Kohen, Yishay Mansour, Kobbi Nissim, Uri Stemmer

arXiv:2609.05329v1Sep 4, 2026cs.CRcs.DS

TL;DR

Machine unlearning’s retraining-emulation requirement does not provide meaningful privacy against sequence-observing adversaries, motivating private retroactive algorithms that combine history-consistent updates with continual-observation differential privacy. The paper formalizes this framework and shows exact retroactivity can be achieved without asymptotic privacy-only overhead for linear queries and histograms, while CountDistinct reveals a cost of retroactivity.

Problem
Recent work shows that unlearning’s simulation requirement has unclear privacy semantics, while privacy for retroactive systems must account for cumulative leakage across evolving releases.
Method
The paper formalizes private retroactive algorithms for insertion-and-deletion sequences, combining retroactivity with differential privacy under continual observation.
Results
Exactly retroactive continual-DP algorithms incur no asymptotic error overhead for oblivious-noise linear queries, and sparse histogram error scales polylogarithmically with T independently of |X|.
Takeaways & Limitations
Privacy and retroactivity can coexist at no asymptotic cost for linear queries and histograms, but retroactivity can rule out instance-adaptive error guarantees for CountDistinct.
Takeaways & Limitations
For CountDistinct, retroactivity strictly forbids instance-adaptive error guarantees and forces worst-case error even on the easiest instances.

Abstract

from arXiv · show

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.

1 Introduction

The paper reframes machine unlearning as retroactive data maintenance and combines retroactivity with continual differential privacy. It shows that this combination is achievable at no asymptotic privacy cost for several tasks, while proving a Count Distinct impossibility.

Motivation: Perfect retraining constrains output distributions but does not by itself constrain what a sequence of releases reveals about individuals.Deletion can enable differencing attacks and can degrade privacy for remaining data.
Motivation: Retroactivity treats deletions as modifications of past operations, requiring subsequent answers to reflect the revised history.This reframes unlearning’s consistency requirement as a maintenance problem studied by retroactive data structures.
Definition: Private retroactive algorithms combine coherent tracking of surviving data with cumulative leakage protection under continual observation.The privacy requirement concerns the joint output sequence, while retroactivity concerns answer suffixes after histories are revised.
Positive results: For linear queries with data-independent noise, exact retroactivity adds no asymptotic error overhead beyond the standard continual-DP transformation.The construction applies to oblivious-noise mechanisms and includes existing continually private clustering algorithms as an application.
Positive results: Sparse histograms achieve exact retroactivity with ℓ∞ error independent of the universe size, despite using data-dependent thresholding.The method maintains an obliviously noisy histogram and delays thresholding until release.
Positive results: Generic compilers provide marginal approximate retroactivity with additive error proportional to baseline accuracy and exact sliding-window retroactivity with privacy costs tied to window and sample sizes.The exact sliding-window compiler specializes to window functionalities and uses random sampling of the active window.
Impossibility: Retroactivity is not universally free: for Count Distinct, private retroactive algorithms incur polynomial worst-case error even on easiest insertion-only sequences.Thus retroactivity rules out the instance-adaptive polylogarithmic error guarantees available under privacy alone.

2 The model and the definitions

The paper models arbitrary additions and deletions as input sequences whose surviving stamped points define the current data. It then formalizes privacy and retroactivity separately before combining them into private retroactive algorithms.

Input sequences: Each time step contains a possibly empty multiset of additions or deletions, with deletions naming stamped additions and arbitrary no-op behavior permitted.Surviving data is processed sequentially, and repeated additions contribute multiplicity.
Dynamic algorithms: A dynamic algorithm receives each update multiset and outputs one answer per round, producing a distribution over the full answer sequence.
Privacy: Privacy protects against inserting one addition or deletion by requiring indistinguishability of the joint output distributions for neighboring sequences.The definition quantifies over fixed neighboring input streams, while an adaptive strengthening is treated separately.
Retroactivity: Retroactivity requires answer suffixes to be identically distributed whenever two histories have the same surviving data from some time onward, even if their prefixes differ substantially.The requirement is stronger than marginal approximate retroactivity because it constrains joint suffix distributions.
Private retroactivity: A private retroactive algorithm satisfies both privacy and retroactivity, while accuracy is imposed separately because the always-⊥ algorithm satisfies the combined definition trivially.

3 Linear functionalities with oblivious noise

For linear statistics with data-independent noise, the classical tree mechanism remains exactly retroactive under continual observation without asymptotic error overhead. The section also identifies extensions to clustering under the same retroactive framework.

Linear statistics: Any one-shot differentially private oblivious-noise mechanism becomes exactly retroactive and continually private with no asymptotic error overhead over the standard continual-DP transformation.
Linear statistics: Oblivious-noise mechanisms add input-independent noise to linear query answers, making persistent noise compatible with retroactivity.The transformation uses a complete binary tree over time and persistent independent noise vectors on dyadic intervals.
Linear statistics: At each round, the error is the sum of at most m independent noise samples, where m = log2 T + 1.
Linear statistics: For counting, the construction achieves error ˜Θ(log3/2 T), matching the non-retroactive lower bound for private counting.
Clustering: The clustering case study observes that an existing continual-observation construction for k-means and k-median is already exactly retroactive, with privacy and accuracy inherited from that algorithm.For k-median, running the construction with privacy parameter ε/2 yields (ε, 0)-privacy and retroactivity.
Clustering: The clustering model uses at most one update per round over a bounded ball and releases k centers at every round.The k-means guarantee holds simultaneously for all rounds with probability at least 0.99.

4 Stability-based histograms

The histogram construction combines dyadic persistent noise with release-time thresholding to produce sparse, private, exactly retroactive histograms over a huge universe. Its error is independent of the universe size, while privacy uses ε = 2mε0.

Accuracy: The released histogram is sparse and has ℓ∞ error independent of |X|, because nonempty bins receive noisy treatment while empty bins are output exactly as zero.
Construction: Thresholding delays the nonlinear sparsification step until release time, preserving oblivious dynamic noise while outputting exact zeros for bins outside the released support.This avoids the retroactivity problem caused by making the noise-bearing bins data dependent during the dynamic computation.
Construction: The algorithm maintains independent Lap(1/ε0) noise variables indexed by dyadic intervals and bins, instantiating each variable on first use and reusing it thereafter.At each round it computes noisy values for bins with surviving items before releasing a sparse histogram.
Guarantees: Theorem 4.1 gives an exactly retroactive, (ε, δ)-private algorithm with ε = 2mε0 and threshold τ = 1 + m
Retroactivity proof: Retroactivity follows because answer suffixes depend only on surviving counts and noise variables for bins active from the uniting time onward.Noise associated with erased bins does not affect outputs because those bins are released as exact zeros.
Privacy proof: Privacy couples neighboring executions by shifting at most 2m noise variables over the differing activity window, then bounds the remaining threshold-release discrepancy across rounds.The resulting event bound is Pr[A(S) ∈E] ≤ e^ε Pr[A(S′) ∈E] + δ.

5 Generic compilers

The paper develops generic compilers that add marginal approximate or exact retroactivity to private dynamic algorithms. These constructions cover Gaussian-noise mechanisms, sliding-window sampling, and gated algorithms for window tasks.

From continual privacy to marginal approximate retroactivity: A continual-DP algorithm can be transformed into one that is marginally approximately retroactive, with approximation error for blocks of B consecutive answers.The transformation applies to any accurate algorithm satisfying continual DP.
From continual privacy to marginal approximate retroactivity: The compiler runs the private algorithm and adds fresh Gaussian noise to each answer, using accuracy to mask differences between histories that later coincide.For answers within distance 2E, Gaussian noise with the prescribed scale provides the needed indistinguishability.
From continual privacy to marginal approximate retroactivity: The compiled algorithm preserves (ε, δ)-privacy by post-processing and obtains marginal approximate retroactivity through blockwise composition of the added noise.The proof combines accuracy, Gaussian mechanism properties, and composition across the block.
Exact retroactivity for window functionalities: sampling with expiry: For sliding-window tasks, uniform sampling from surviving points yields an exactly retroactive private algorithm, with privacy depending on window size and sample size.Sampling only surviving points guarantees retroactivity, while sample secrecy can amplify privacy.
Exact retroactivity for window functionalities: sampling with expiry: A gated window algorithm is exactly retroactive and private when n ≥C log2(T) log(T/δt)/εt, while releasing M(Qℓ) at sufficiently populated rounds except with probability δt.The count error is bounded by n−1 except with probability δt.
Exact retroactivity for window functionalities: sampling with expiry: The sampling compiler supports an exactly retroactive interior-point algorithm that releases a valid live-point value with probability 1 −β −δt when the occupancy threshold is met.At other rounds, the release is either a valid value or ⊥.

6 On the price of retroactivity

This section shows that retroactivity can conflict with instance-adaptive accuracy for CountDistinct. Retroactivity forces each round’s output distribution to depend only on the current surviving data, preventing algorithms from retaining history-dependent privacy budgets.

Negative result: Retroactivity forbids instance-adaptive error bounds for CountDistinct, although the result gives an instance-adaptive rather than worst-case separation.The paper leaves a worst-case separation as an open question.
Comparison with instance-adaptive mechanisms: Instance-adaptive mechanisms track flippancy and obtain polylogarithmic error when maximum flippancy is O(1), but their history-dependent noise is not retroactive.Their noise accounts for changes involving copies that have since been deleted.
Amnesia: A retroactive algorithm’s output distribution at round ℓ depends only on the stamped multiset Dataℓ(S), so accuracy on insertion-only sequences transfers to all sequences.This is the amnesia lemma’s consequence for per-round accuracy.
Impossibility theorem: The impossibility follows by combining amnesia with a marginal worst-case lower bound for private CountDistinct.The transferred per-round accuracy would contradict the lower bound if f(1) were smaller.
Impossibility theorem: For private retroactive CountDistinct, the error bound satisfies f(1) ≥c T 1/4 even on insertion-only sequences with maximum flippancy 1.Thus the easiest instances already require a worst-case-level bound.
Forced budget amnesia: The paper interprets this limitation as forced budget amnesia: retroactivity forbids retaining records of past flips that no longer survive.This prevents the data-dependent accounting used by instance-adaptive continual mechanisms.

A A model with retroactive insertions

The appendix extends the update model so additions may also be inserted into the past. It defines the resulting state and neighboring relation while distinguishing partial from full retroactivity.

Update model: An update may be a retroactive addition (add, t, x) or a deletion (del, t, x), with the earlier model recovered when additions use the current round’s timestamp.Additions naming future times are ignored until applicable.
Update model: The current data state is formed by processing updates in arrival order, adding stamped points whose timestamps are no later than the current round and then applying deletions.A deletion removes one matching copy when present and otherwise does nothing.
Neighboring sequences: The neighboring relation remains defined by inserting one operation into an update sequence, now allowing either a retroactive addition or a deletion.The relation continues to operate at single-operation granularity.
Partial and full retroactivity: Partial retroactivity queries only the current state, whereas full retroactivity may query any revised past state after retroactive insertions and deletions are applied.A retroactive insertion changes revised past states at or after its timestamp once it arrives.

B Adaptive privacy

The appendix defines privacy against adaptively chosen streams and combines that guarantee with retroactivity. The adversary selects future updates from past answers and may issue one challenge addition or deletion.

Adaptive privacy game: The adaptive model allows an adversary to choose each round’s updates as a function of previous released answers and its internal randomness.The adversary may also make challenge declarations during the game.
Adaptive privacy game: The adversary may issue at most one challenge addition or one challenge deletion naming an earlier timestamp and point.The challenge is included only in one of the two game worlds.
Adaptive privacy game: After receiving each update set, the algorithm returns an answer that is revealed to the adversary, completing the adaptive interaction.The adversary uses the resulting transcript to choose subsequent updates.
Definition: An adaptively private retroactive algorithm is both adaptively private under this game and retroactive.The definition combines the adaptive privacy requirement with the paper’s retroactivity definition.

C The persistent ranks variant

The persistent-ranks variant assigns each addition a secret rank that remains fixed throughout its lifespan, creating temporal correlation in sampling. Its privacy proof couples neighboring executions through one persistent rank and tracks the resulting inclusion patterns over the bounded window.

Persistent-rank mechanism: Each addition receives an independent secret uniform rank that determines its sample inclusion throughout its lifespan.At each round, the mechanism releases a differentially private function of the min{k, n_ℓ} live copies with smallest rank.
Persistent-rank mechanism: Persistent ranks create temporal correlation because an item’s inclusion is no longer an independent coin flip at each round.
Retroactivity: The construction is retroactive because sample blocks after time i depend only on the surviving data from time i onward, making answer suffixes identically distributed when those data agree.
Privacy coupling: The privacy coupling maintains one fixed distinguished rank r* as the sole rank difference throughout the critical window W*.For differing additions, LIFO deletions preserve the unmatched rank; for differing deletions, cyclic rank assignment ensures the same property.
Inclusion patterns: The extra copy affects the transcript only through its binary inclusion pattern over its lifespan, determined by comparisons with round-specific rank thresholds.The lifespan contains the critical window and has size at most W because items expire after W rounds.
Privacy amplification: Any two inclusion patterns differing at h rounds induce conditional distributions that are (2hε0, 2he^ε0δ0)-indistinguishable, yielding an (εW, δW) bound over a lifespan of at most W rounds.The argument composes per-round privacy losses because the base mechanism uses fresh coins each round.

D Marginal worst case negative result for CountDistinct

This section proves a marginal worst-case lower bound for private dynamic CountDistinct: even per-round accuracy, rather than simultaneous sequence accuracy, is incompatible with sufficiently small error. The proof encodes robustly decodable bits into neighboring update sequences, contradicting differential privacy.

Setup: The lower bound already applies to marginal accuracy, requiring accuracy separately at each time step rather than simultaneously over the output sequence.
Reconstruction tool: Robust linear-query reconstruction supplies queries that recover all but n/100 bits from sufficiently accurate noisy answers.The robust decoder guarantee holds for a fixed family of k = c1·n sign queries when the corruption fraction stays below the threshold.
Contradiction: 0.792 is a reconstruction accuracy achieved with probability at least 4/5, while differential privacy permits at most 0.732 + δ*/2 expected coordinate accuracy.The proof sets δ* = 0.1, so the privacy upper bound is strictly below the decoder’s achieved accuracy.
Conclusion: For sufficiently large T, no (1, δ*)-private dynamic CountDistinct algorithm achieves (c·T^1/4, β*) accuracy per round on all input sequences.
Reduction: The constructed sequence S(y) encodes each bit y_i through an addition at round i, then uses query-specific add-and-delete blocks to generate CountDistinct answers.At the midpoint of block j, the present values are exactly Y ∪ Q_j, enabling a linear-query estimate from the transcript.
Privacy preservation: Changing one coordinate of y changes exactly one update, so the derived answer vector B(y) remains (1, δ*)-differentially private by post-processing.