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

CRII：CIF：记忆约束学习：高效算法和信息论下界

基本信息

批准号：
1657471
负责人：
Jayadev Acharya
金额：
$ 17.5万
依托单位：
Cornell University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-02-15 至 2020-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1657471&HistoricalAwards=false
关键词：
CRII CIF Learning Memory Constraints

项目摘要

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.

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