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

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

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.