Unbounded unlearning is a design philosophy for machine unlearning algorithms introduced in Kurmanji et al. (2023). It refers to unlearning methods that are free from the limiting assumptions, poor scalability, and application-specific restrictions that constrain prior approximate unlearning approaches. The term contrasts with “bounded” methods that provide theoretical guarantees at the cost of restrictive conditions.
Prior approximate unlearning methods typically rely on one or more of the following assumptions: (1) the forget set is small relative to the training set, (2) the trained model is close to the optimal solution in weight space (enabling first-order Taylor approximations), (3) SGD iterates are stable across nearby datasets, or (4) a Neural Tangent Kernel linearization accurately approximates the network’s behaviour. Kurmanji et al. show empirically that these assumptions are frequently violated in practice, leading to poor unlearning quality. For example, NTK-based methods (Golatkar et al., 2020b) scale quadratically with dataset size, and Fisher Forgetting (Golatkar et al., 2020a) can exceed the runtime of retraining from scratch.
An unbounded method instead takes a practical, empirically-driven approach: it should (1) work across different applications (bias removal, confusion resolution, privacy protection) without tailoring, (2) scale to arbitrary forget set sizes without degradation, (3) maintain model utility on retained data and generalization, and (4) not require restrictive mathematical assumptions. The SCRUB algorithm is proposed as the prototypical unbounded method, using a teacher-student formulation that naturally handles these desiderata.
Key Details
- The term “unbounded” specifically refers to removing bounds on: forget set size, training set size, model architecture constraints, and application specificity
- Unbounded methods sacrifice formal (epsilon, delta)-certified approximate unlearning guarantees in favour of consistent empirical performance across diverse settings
- The trade-off between theoretical guarantees and practical performance is explicitly acknowledged: methods with guarantees (e.g., those based on differential privacy) either do not scale to deep networks or perform poorly empirically
- Developing theoretical guarantees for unbounded methods like SCRUB is identified as an important open problem
- The concept highlights a fundamental tension in unlearning research between theoretical rigour and practical applicability