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 = \textsc{Poly}(d, \log(1/\epsilon))$
retention suffices to achieve mean squared error $\epsilon$ after observing
$O(1/\epsilon)$ $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
$\epsilon$. 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.

引入带有数据保留约束条件的在线算法模型，在多维均值估计和线性回归问题中展示了多维随机子集和对抗噪声模型在模拟随机梯度下降的进展方面的最新进展。