Online Learning and Unlearning
This addresses the need for efficient and privacy-compliant machine learning models in dynamic environments, though it is incremental as it builds on existing online gradient descent methods.
The paper tackles the problem of online learning with unlearning requests, where a model must be updated sequentially while ensuring that after a data point is unlearned, outputs are statistically indistinguishable from a model trained without that point. It presents two algorithms based on online gradient descent that achieve regret bounds comparable to standard OGD, providing unlearning guarantees without significant computational overhead.
We formalize the problem of online learning-unlearning, where a model is updated sequentially in an online setting while accommodating unlearning requests between updates. After a data point is unlearned, all subsequent outputs must be statistically indistinguishable from those of a model trained without that point. We present two online learner-unlearner (OLU) algorithms, both built upon online gradient descent (OGD). The first, passive OLU, leverages OGD's contractive property and injects noise when unlearning occurs, incurring no additional computation. The second, active OLU, uses an offline unlearning algorithm that shifts the model toward a solution excluding the deleted data. Under standard convexity and smoothness assumptions, both methods achieve regret bounds comparable to those of standard OGD, demonstrating that one can maintain competitive regret bounds while providing unlearning guarantees.