In the unlearning setup, there is no adversary per se, or in the idealized application, the curator is the adversary and the dataset owners wants it to have as little control as possible.
It is therefore natural to
demand that the probability distribution of the entire state maintained by the algorithm, and not just the output be exactly identical after performing the unlearning operation.
This, with slight differences, is referred to as perfect unlearning in [1]}, and what our algorithms satisfy.
We have argued that designing TV stable algorithms is a good start, and for a moment suppose that the TV stability is same as DP.
Then should we measure TV stability between the joint distributions over the entire state?
This would limit the application of DP techniques in which keeping additional state hidden has stronger privacy property.
In that case, TV stability parameter, and hence the computational cost of unlearning would be large.
Interestingly, even though the previous work in differentially private convex ERM, for example [2]}, argues that the released iterate (average/final iterate) is differentially private, the analysis is typically carried out by first arguing, via a composition step, that all iterates together are differentially private. This means that all iterates can be released without any additional cost of privacy.
This innocuous property arguably provides no benefit for privacy, but turns out to be extremely beneficial to us in unlearning. However, even though the all the iterates can be released, the mini-batches still need to kept secret.
We handle this in the unlearning algorithm using an estimation step - see paragraph titled “Estimation of marginals" in sec:main-idea-unlearning.
