CAREER: Computational and Statistical Tradeoffs in Massive Data Analysis

在现代信号处理中，人们经常面临涉及大量数据集的统计推断问题。例如，CERN大型强子对撞机的实验每年产生数百PB的数据，必须有效地存储和处理这些数据，以进一步理解粒子物理。类似的挑战也出现在地震监测中，其中通过手机加速度计在大面积上获取大量数据。分析如此大的数据集通常被视为一个巨大的计算挑战。但是，如果数据是一个信号处理器呢？的主要资源，那么访问更多的数据应被视为一种资产，而不是一种负担，更大的数据集应导致减少运行时的数据分析算法。算法弱化？框架，其中数据分析过程随着数据大小的缩放而退回到更简单的方法，利用数据的不断增长的推理强度来确保以减少的运行时间实现期望的统计准确性水平。 该方法具体说明了在一系列的统计估计任务，凸松弛技术发挥了突出的作用，作为一种算法弱化机制。 在寻求一个精确的表征通过凸松弛获得的计算和统计权衡，调查正式和研究新的措施，表征质量的一个凸集的近似由另一个。 这项研究的一个有趣的特点是，凸松弛，在组合优化问题中提供性能不佳，但可能会产生有用的解决方案时，在推理目标的问题。

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.