Space-Efficient Estimation of Robust Statistics and Distribution Testing
Space-Efficient Estimation of Robust Statistics and Distribution Testing
复制标题
稳健统计和分布测试的空间高效估计
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Mcgregor
中科院分区：
文献类型：
--
作者：
Steve Chien;Katrina Ligett;A. Mcgregor
在给定I.I.D.序列的情况下，估计和推断的一般问题。样本在统计、属性测试和学习社区中得到了广泛的研究。感兴趣的自然量是所考虑的特定学习或估计问题的样本复杂性。虽然样本复杂性是任务计算效率的重要组成部分，但考虑空间复杂性也是很自然的：我们是否需要在绘制所有样本时存储它们，或者使用样本复杂性显著次线性的内存是否足够？令人惊讶的是，估计复杂性的这一方面在除少数特定情况外的所有情况下都得到了明显较少的关注。虽然空间受限的顺序计算是数据流计算领域的研究范围，但几乎所有关于数据流算法理论的文献都只考虑“经验问题”，其中的目标是计算流中存在的数据的函数，而不是关于流的来源的推断。我们的贡献是双重的。首先，我们提供了将空间效率与来自I.I.D.序列的稳健统计估计联系起来的结果。样本。稳健统计在我们的设置中是一类特别有趣的统计，因为根据定义，它们对采样数据中的噪声或错误具有弹性。我们证明了这一性质足以确保存在非常节省空间的流算法来进行它们的估计。相反，“非稳健”统计量的数值可能会随着样本的增加而发生显著变化，这限制了任何有限长度样本序列的实用性。其次，我们给出了一个一般性的结果，它在分布特性测试的背景下捕获了样本和空间复杂性之间的权衡。
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 space-bounded, sequential computation is the purview of the field of data-stream computation, almost all of the literature on the algorithmic theory of data-streams 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 two-fold. 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 space-efficient stream algorithms exist for their estimation. In contrast, the numerical value of a "non-robust" 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 trade-off between sample and space complexity in the context of distributional property testing.