Statistical Inference with Limited Memory: A Survey
Tomer Berg Or Ordentlich Ofer Shayevitz
The problem of statistical inference in its various forms has been the
subject of decades-long extensive research. Most of the effort has been focused
on characterizing the behavior as a function of the number of available
samples, with far less attention given to the effect of memory limitations on
performance. Recently, this latter topic has drawn much interest in the
engineering and computer science literature. In this survey paper, we attempt
to review the state-of-the-art of statistical inference under memory
constraints in several canonical problems, including hypothesis testing,
parameter estimation, and distribution property testing/estimation. We discuss
the main results in this developing field, and by identifying recurrent themes,
we extract some fundamental building blocks for algorithmic construction, as
well as useful techniques for lower bound derivations.