Statistical Inference with Limited Memory

In statistical inference problems, we are typically given a limited number of samples from some underlying distribution, and we wish to estimate some property of that distribution, under a given measure of risk. We are usually interested in characterizing and achieving the best possible risk as a function of the number of available samples. Thus, it is often implicitly assumed that samples are co-located, and that communication bandwidth as well as computational power are not a bottleneck, essentially making the number of samples the sole limiting factor. However, in modern applications such as wireless sensor networks, data may be distributed between multiple remotely-located agents who may be subject to stringent communication constraints, and have limited memory / computational capabilities. In such cases, the bottleneck for inference may become bits rather than samples — either the number of available communication bits, or the number of bits that can be stored in memory. In this talk, we will focus on the latter case, and ask: How does the risk behave as a function of the algorithm’s memory size, when the number of available samples is large? We will formalize this question in a finite-state machine setting, and discuss several techniques for algorithmic construction and lower bound derivation, highlighted through some of our recent work on memory-limited hypothesis testing, bias estimation, uniformity testing, and entropy estimation.

Based on joint work with Tomer Berg and Or Ordentlich.

Bio: 

Ofer Shayevitz received the B.Sc. degree from the Technion Institute of Technology, Haifa, Israel, and the M.Sc. and Ph.D. degrees from the Tel-Aviv University, Tel Aviv, Israel, all in electrical engineering. He is currently an Associate Professor in the Department of EE – Systems at Tel Aviv University. Ofer’s research spans a wide cross-section of problems in information theory, statistical inference, and discrete mathematics. He is the recipient of the European Research Council (ERC) Starting Grant, several Israel Science Foundation (ISF) grants, and the Marie Curie Grant. He is also actively involved in the hi-tech industry, and regularly consults to various companies. Before joining Tel Aviv University, Ofer was a postdoctoral fellow in the Information Theory and Applications (ITA) Center at the University of California, San Diego, and worked as a quantitative analyst with the D.E. Shaw group in New York. Prior to his graduate studies, he has held several R&D positions in the fields of digital communication and statistical signal processing.