ICS 2010

Welcome to ICS2010
Innovations in Computer Science  ICS 2010, Tsinghua University, Beijing, China, January 57, 2010. Proceedings, 251265,
9787302217527
Tsinghua University Press
The generic problem of estimation and inference given a sequence of i.i.d. samples has been extensively studied in the statistics, property testing, and learning communities. A natural quantity of interest is the sample complexity of the particular learning or estimation problem being considered. While sample complexity is an important component of the computational efficiency of the task, it is also natural to consider the space complexity: do we need to store all the samples as they are drawn, or is it sufficient to use memory that is significantly sublinear in the sample complexity? Surprisingly, this aspect of the complexity of estimation has received significantly less attention in all but a few specific cases. While spacebounded, sequential computation is the purview of the field of datastream computation, almost all of the literature on the algorithmic theory of datastreams considers only “empirical problems”, where the goal is to compute a function of the data present in the stream rather than to infer something about the source of the stream. Our contributions are twofold. First, we provide results connecting space efficiency to the estimation of robust statistics from a sequence of i.i.d. samples. Robust statistics are a particularly interesting class of statistics in our setting because, by definition, they are resilient to noise or errors in the sampled data. We show that this property is enough to ensure that very spaceefficient stream algorithms exist for their estimation. In contrast, the numerical value of a “nonrobust” statistic can change dramatically with additional samples, and this limits the utility of any finite length sequence of samples. Second, we present a general result that captures a tradeoff between sample and space complexity in the context of distributional property testing. Preview:

Copyright 20092010, Institute for Computer Science, Tsinghua University, All Rights Reserved.