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.

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

具有有限数据保留的在线算法

Online Algorithms with Limited Data Retention

Both the human brain and artificial learning agents operating in real-world
or comparably complex environments are faced with the challenge of online model
selection. In principle this challenge can be overcome: hierarchical Bayesian
inference provides a principled method for model selection and it converges on
the same posterior for both off-line (i.e. batch) and online learning. However,
maintaining a parameter posterior for each model in parallel has in general an
even higher memory cost than storing the entire data set and is consequently
clearly unfeasible. Alternatively, maintaining only a limited set of models in
memory could limit memory requirements. However, sufficient statistics for one
model will usually be insufficient for fitting a different kind of model,
meaning that the agent loses information with each model change. We propose
that episodic memory can circumvent the challenge of limited memory-capacity
online model selection by retaining a selected subset of data points. We design
a method to compute the quantities necessary for model selection even when the
data is discarded and only statistics of one (or few) learnt models are
available. We demonstrate on a simple model that a limited-sized episodic
memory buffer, when the content is optimised to retain data with statistics not
matching the current representation, can resolve the fundamental challenge of
online model selection.

本研究探讨在具有有限内存容量的情境下，如何运用基于分层贝叶斯推断的模型选择，以及利用存储在记忆库中的数据解决模型选择中的基本问题。