# Online Algorithms with Limited Data Retention

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 17 Apr 2024.

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

- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient](https://mlsanity.com/paper/2006.07990/) (2020)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Formalizing Data Deletion in the Context of the Right to be Forgotten](https://mlsanity.com/paper/2002.10635/) (2020)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2206.04270/) (2022)
- [Control, Confidentiality, and the Right to be Forgotten](https://mlsanity.com/paper/2210.07876/) (2022)
- [Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares](https://mlsanity.com/paper/1803.00841/) (2018)
- [On the Multidimensional Random Subset Sum Problem](https://mlsanity.com/paper/2207.13944/) (2022)

## Abstract (arXiv)

We introduce a model of online algorithms subject to strict constraints on data retention. An online learning algorithm encounters a stream of data points, one per round, generated by some stationary process. Crucially, each data point can request that it be removed from memory m rounds after it arrives. To model the impact of removal, we do not allow the algorithm to store any information or calculations between rounds other than a subset of the data points (subject to the retention constraints). At the conclusion of the stream, the algorithm answers a statistical query about the full dataset. We ask: what level of performance can be guaranteed as a function of m? We illustrate this framework for multidimensional mean estimation and linear regression problems. We show it is possible to obtain an exponential improvement over a baseline algorithm that retains all data as long as possible. Specifically, we show that m = textscPoly(d, log(1/ε)) retention suffices to achieve mean squared error ε after observing O(1/ε) d-dimensional data points. This matches the error bound of the optimal, yet infeasible, algorithm that retains all data forever. We also show a nearly matching lower bound on the retention required to guarantee error ε. One implication of our results is that data retention laws are insufficient to guarantee the right to be forgotten even in a non-adversarial world in which firms merely strive to (approximately) optimize the performance of their algorithms. Our approach makes use of recent developments in the multidimensional random subset sum problem to simulate the progression of stochastic gradient descent under a model of adversarial noise, which may be of independent interest.