We develop new algorithmic principles which enable exact unlearning in very general settings. In particular, we propose a notion of algorithmic stability, called total variation (TV) stability - an algorithmic property, which for any problem, yields an in-principle exact unlearning algorithm.
Such an algorithm might not be efficiently implementable computationally or due to the data access restriction (sequential nature of edits).
To demonstrate the generality of our framework, we discuss, in sec:qsgd how the previous work of [1]} for unlearning in \(k\) -means clustering using randomized quantization can be interpreted as a special case of our framework - a TV stable method, followed by efficient coupling based unlearning.
We also note that the notion of TV-stability has appeared before in [2]}, although in the seemingly unrelated context of adaptive data analysis.
