Towards Forgetting and Online Unlearning

Though online learning is a well-established field, the development of mechanisms for ensuring data removal is still in its early stages. While machine unlearning has been studied in batch settings, its application in online learning is both novel and complex due to the difficulty of iteratively maintaining model performance while eliminating data influence. In this paper, we formalize and define online unlearning. We also propose an Online Gradient Descent Forgetting algorithm that ensures the complete removal of requested data influence without retraining. Additionally, we extend an edit-distance 1 algorithm to a framework that allows for multiple deletions by integrating tree-based noise. We also provide rigorous proofs of unlearning, regret analyses, and resource analyses for both algorithms. This work not only advances the theoretical underpinnings of online unlearning but also offers concrete algorithms that can be directly implemented in privacy-sensitive online applications.