Approximate unlearning (also called certified or bounded unlearning) relaxes the strict distributional equality of exact unlearning to allow bounded divergence between the unlearned model and the retrained model. It is formalised in Nguyen et al. (2025) with several levels of relaxation.
epsilon-Approximate Unlearning (Definition 1): Given epsilon > 0, an unlearning mechanism U performs epsilon-certified removal for a learning algorithm A if for all hypothesis sets T, datasets D, and samples z:
e^{-epsilon} ⇐ Pr(U(D, z, A(D)) in T) / Pr(A(D \ z) in T) ⇐ e^{epsilon}
(epsilon, delta)-Approximate Unlearning (Definition 3): A relaxed version adding an additive delta term:
Pr(U(D, z, A(D)) in T) ⇐ e^{epsilon} * Pr(A(D \ z) in T) + delta
This is analogous to (epsilon, delta)-differential privacy but applied in the “reverse” direction: differential privacy bounds what the model learns, while approximate unlearning bounds what the model forgets.
Key Details
- The bounds can be measured in either weight space (parameter distributions) or output space (prediction distributions)
- Output-space indistinguishability (weak unlearning) is sufficient for privacy but more permissive than weight-space indistinguishability
- Relationship to differential privacy: If a learning algorithm A is epsilon-differentially private, then it never memorises data in the first place, making unlearning trivial. However, differentially private models suffer significant accuracy loss for large epsilon
- Indistinguishability metrics include: L2 distance (verification error), KL divergence, JS-Divergence, and activation distance
- Key algorithms providing approximate unlearning guarantees include: certified removal mechanisms (Guo et al.), regularised/distributed perturbed gradient descent (Neel et al.), Fisher-based unlearning (Golatkar et al.), and gradient/model clipping (Koloskova et al.)
- certified pixel-level unlearning adapts (epsilon, delta)-approximate unlearning to the conditional pixel-wise prediction space for segmentation tasks
- The unlearning isomorphism enables applying standard approximate unlearning guarantees to the segmentation mask refinement problem