# Online Learning and Unlearning

arXiv: https://arxiv.org/abs/2505.08557 · HTML: https://mlsanity.com/paper/2505.08557/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 18 of its 28 references that are in the map.
- First posted on arXiv 13 May 2025.

## Placed in

- LLM safety and security / [Machine unlearning](https://mlsanity.com/safety/machine-unlearning/)

## Builds on (most cited first, 18 of 18)

- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [Algorithms that Approximate Data Removal: New Results and Limitations](https://mlsanity.com/paper/2209.12269/) (2022)
- [Corrective Machine Unlearning](https://mlsanity.com/paper/2402.14015/) (2024)
- [Reconstructing Training Data from Model Gradient, Provably](https://mlsanity.com/paper/2212.03714/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions](https://mlsanity.com/paper/2409.09778/) (2024)
- [Ticketed Learning-Unlearning Schemes](https://mlsanity.com/paper/2306.15744/) (2023)
- [Control, Confidentiality, and the Right to be Forgotten](https://mlsanity.com/paper/2210.07876/) (2022)
- [Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation](https://mlsanity.com/paper/2306.06723/) (2023)

## Built on by (most cited first, 1 of 1)

- [Less Noise, Same Certificate: Retain Sensitivity for Unlearning](https://mlsanity.com/paper/2603.03172/) (2026)

## Abstract (arXiv)

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.