CRII: CIF: Learning with Memory Constraints: Efficient Algorithms and Information Theoretic Lower Bounds

数据量、存储量、统计估计任务的计算时间等资源之间的权衡是现代数据科学的核心。根据设置，某些资源可能比其他资源更有价值。例如，在信用分析和人口遗传学中，数据量至关重要。对于涉及移动的设备、传感器网络或生物医学植入物的应用，可用的存储是有限的并且是宝贵的资源。该项目旨在通过（i）设计需要小空间的高效算法和（ii）建立这些任务所需存储的基本限制来促进我们对存储量和统计任务所需数据量之间权衡的理解。这项研究是在流算法的交叉点，主要关注算法问题的存储要求，统计学习，研究统计任务的数据要求。研究人员在存储限制条件下制定基本的统计问题。具体问题包括离散分布的熵估计，这是统计学、信息论和计算机科学等各个领域的研究人员研究过的典型问题。感兴趣的范例如下：虽然已知的样本有效的熵估计算法需要大量的存储，但通过采取比最佳数量多一点的样本，可以大幅降低存储需求。这个问题的互补面是纯粹的信息论。在其中，研究人员希望开发出通用的下限，可用于证明存储样本权衡的基本限制。

The trade-offs between resources such as the amount of data, the amount of storage, computation time for statistical estimation tasks are at the core of modern data science. Depending on the setting, some of the resources might be more valuable than others. For example, in credit analysis and population genetics, the amount of data is vital. For applications involving mobile devices, sensor networks, or biomedical implants, the storage available is limited and is a precious resource. This project aims to advance our understanding of the trade-offs between the amount of storage and the amount of data required for statistical tasks by (i) designing efficient algorithms that require small space and (ii) establishing fundamental limits on the storage required for these tasks. The research is at the intersection of streaming algorithms, which is primarily concerned with storage requirements of algorithmic problems, and statistical learning, which studies data requirements for statistical tasks. The investigators formulate basic statistical problems under storage constraints. The specific questions include entropy estimation of discrete distributions, a canonical problem that researchers from various fields including statistics, information theory, and computer science have studied. The paradigm of interest is the following: while the known sample-efficient entropy estimation algorithms require a lot of storage, it might be possible to reduce the storage requirements drastically by taking a little more than the optimal number of samples. The complementary side of the problem is purely information theoretic. In it, the researchers expect to develop general lower bounds that can be used to prove fundamental limits on the storage-sample trade-offs.