CAREER: Computational and Statistical Tradeoffs in Massive Data Analysis

职业：海量数据分析中的计算和统计权衡

• 批准号: 1350590
• 负责人: Venkat Chandrasekaran
• 金额: $ 47.5万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-02-01 至 2020-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1350590&HistoricalAwards=false
• 关键词: CAREER; Computational; Statistical; Tradeoffs; Massive; CAREER; Computational; Statistical; Tradeoffs; Massive

In modern signal processing, one is frequently faced with statistical inference problems involving massive datasets. For example, the experiments at the Large Hadron Collider at CERN generate hundreds of petabytes of data each year, which must be stored and processed efficiently in order to further our understanding of particle physics. Similar challenges also arise in seismic monitoring where massive amounts of data are acquired over large areas via cellphone accelerometers. Analyzing such large datasets is usually viewed as a substantial computational challenge. However, if data are a signal processor?s main resource then access to more data should be viewed as an asset rather than as a burden, and larger datasets should lead to a reduction in the runtime of data analysis algorithms.This project blends concepts from computer science and from statistical signal processing to address the challenge with massive datasets by developing ?algorithm weakening? frameworks in which a data analysis procedure backs off to simpler methods as the data scale in size, leveraging the growing inferential strength of the data to ensure that a desired level of statistical accuracy is achieved with reduced runtime. The approach is concretely illustrated across a range of statistical estimation tasks, with convex relaxation techniques playing a prominent role as an algorithm weakening mechanism. In seeking a precise characterization of the computational and statistical tradeoffs obtained via convex relaxation, the investigator formalizes and studies new measures for characterizing the quality of approximation of one convex set by another. An interesting feature of this research is that convex relaxations which provide poor performance in combinatorial optimization problems may nonetheless yield useful solutions when employed in problems with inferential objectives.

在现代信号处理中，人们经常面临涉及大量数据集的统计推断问题。例如，在CERN的大型强子对撞机上进行的实验每年会产生数百个数据，必须进行有效的存储和处理，以进一步了解我们对粒子物理的理解。在地震监测中也出现了类似的挑战，在地震监测中，通过手机加速度计在大区域中获取了大量数据。分析如此大的数据集通常被视为重大的计算挑战。但是，如果数据是信号处理器的主要资源，则应将更多数据视为资产，而不是负担，而较大的数据集应导致数据分析算法的运行时降低。该项目将计算机科学的概念从计算机科学和统计信号处理中融合来解决与大规模数据集来通过开发质疑的挑战？随着数据量表的规模，数据分析过程逐渐回到更简单的方法的框架，利用数据的推论强度不断增长，以确保通过降低的运行时达到所需的统计准确性水平。 该方法在一系列统计估计任务中有具体说明，凸松弛技术在算法弱化机制中起着重要的作用。 在寻求通过凸松弛获得的计算和统计折衷的精确表征，研究者对表征另一个凸的近似质量进行了形式化并研究了新的措施。 这项研究的一个有趣特征是，在推理目标问题中使用时，凸出的放松在组合优化问题中提供较差的性能可能会产生有用的解决方案。