CAREER: Algorithms for understanding data
CAREER: Algorithms for understanding data
批准号:
1351108
负责人:
Gregory Valiant
金额:
$50.0万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2014
资助国家:
美国
项目状态:
已结题
起止时间:
2014-07-01 至 2019-06-30
中文摘要
给定来自某个未知分布的样本,人们可以对潜在分布推断出什么,这些推断的效率如何?在许多最基本的设置中,我们对计算和信息理论的可能性和障碍的理解仍然非常贫乏。该项目涉及两个广泛的研究目标:开发探测数据的有效算法,以及了解如何有效地估计分布的属性。研究的第一行试图理解关于数据集的哪些问题可以极其有效地回答,这需要在数据集大小或分布上是次线性的计算资源(时间或内存)。第二个研究目标是了解以高概率确定分布或数据集是否具有给定属性所需的最小信息量。在统计属性估计的上下文中,这个问题询问需要多少样本才能以高概率将所讨论的属性估计到所需的精度。本研究追求新的估计算法、新的信息理论工具和下界。从遗传、生物和医学数据库到记录我们的经济和社会行为的数据库,随着许多学科中大量重要的数据集的出现,如何理解这些数据的挑战具有特别直接的相关性,并迅速成为科学理解的瓶颈。本项目研究的具体问题产生于对这些数据集的分析;这些问题的算法进步有可能很快被采用,并改变正在进行的数据分析工作。除了对数据科学的直接影响之外,这些问题都是非常基本和基础的。因此,从他们的研究中收集到的新技术、观点和见解可能会对计算机科学、统计学、信息论和数据科学中的其他问题产生广泛的影响。
英文摘要
Given samples from some unknown distribution, what can one infer about the underlying distribution, and how efficiently can these inferences be made? In many of the most fundamental settings, our understanding of the computational and information theoretic possibilities and barriers is still startlingly poor. This project tackles two broad research objectives: developing efficient algorithms for probing data, and understanding how to efficiently estimate properties of distributions. The first line of research seeks to understand which questions about a dataset can be answered extremely efficiently, requiring computational resources (time, or memory) that are sublinear in the size of the dataset or distribution. The second research objective is to understand the minimal amount of information necessary to ascertain, with high probability, whether or not a distribution or dataset possesses a given property. In the context of statistical property estimation, this problem asks how few samples are needed to estimate the property in question to a desired accuracy, with high probability. This research pursues both new estimation algorithms, and new information theoretic tools and lower bounds.With vast and important datasets emerging across many disciplines, from genetic, biological, and medical databases, to databases documenting our economic and social behaviors, the challenge of how to make sense of them has particular immediate relevance and has rapidly become the bottleneck in scientific understanding. The specific problems investigated in this project arise in the analysis of these datasets; algorithmic advances on these problems have the potential to very quickly be adopted and transform ongoing data analysis efforts. Beyond the immediate implications for the data sciences, these questions are extremely basic and foundational. As such, new techniques, perspectives, and insights gleaned from their study are likely to have broad implications for other problems throughout computer science, statistics, information theory, and the data sciences.
期刊论文(1)
专著(0)
科研奖励(0)
会议论文
Spectrum estimation from samples
样本的频谱估计
DOI:
10.1214/16-aos1525
发表时间:
2017
期刊:
The Annals of Statistics
影响因子:
--
作者:
[Kong, Weihao, Valiant, Gregory]
通讯作者:
Valiant, Gregory
AF: Small: Memory Bounded Optimization and Learning
-
批准号:2341890
-
项目类别:Standard Grant
-
资助金额:$60.0万
-
财政年份:2024
-
负责人:Gregory Valiant
-
依托单位:
AF: Small: Robust and Secure Learning
-
批准号:1813049
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2018
-
负责人:Gregory Valiant
-
依托单位:
AF:Medium:Collaborative Research:Estimation, Learning, and Memory: The Quest for Statistically Optimal Algorithms
-
批准号:1704417
-
项目类别:Continuing Grant
-
资助金额:$55.0万
-
财政年份:2017
-
负责人:Gregory Valiant
-
依托单位:
海外基金