Statistical and Computational Tradeoffs in High Dimensional Learning

高维学习中的统计和计算权衡

• 批准号: 1317308
• 负责人: Philippe Rigollet
• 金额: $ 45万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1317308&HistoricalAwards=false
• 关键词: Statistical; Computational; Tradeoffs; Dimensional; Learning

For various statistical procedures, mostly involving searching for a sparse structure in a high-dimensional parameter space, a gap between the performance attained by computationally efficient procedures and optimal ones has been observed. Examples include sparse regression, sparse principal component analysis, community detection, clustering, network analysis and matrix completion. This observation hints at the existence of an inherent statistical price to pay for using computationally efficient methods. The investigators study how large this price can be by drawing new bridges between theoretical computer science and statistical learning theory. Practically, this agenda requires shifting the current notion of statistical optimality to have more relevance under limited computational power and developing new algorithms that achieve said optimality.The recent establishment of big-data as the new norm is causing a paradigm shift in statistics: computational power is the new bottleneck, not the lack of observations. The investigators lay theoretical foundations to study this new tradeoff between statistical and computational performance. A direct benefit of this research is to help statisticians and practitioners navigate the ocean of available heuristics and avoid the common pitfalls associated with using them.

对于各种统计程序，主要涉及在高维参数空间中搜索稀疏结构，计算效率高的程序与最优的程序之间的性能存在差距。例子包括稀疏回归、稀疏主成分分析、社区检测、聚类、网络分析和矩阵补全。这一观察结果暗示，使用计算效率高的方法存在固有的统计代价。研究人员通过在理论计算机科学和统计学习理论之间建立新的桥梁来研究这个代价有多大。实际上，这一议程需要改变当前统计最优性的概念，使其在有限的计算能力下具有更大的相关性，并开发实现所述最优性的新算法。最近大数据作为新规范的确立正在引起统计学范式的转变：计算能力是新的瓶颈，而不是缺乏观察。研究人员为研究统计性能和计算性能之间的这种新的权衡奠定了理论基础。这项研究的一个直接好处是帮助统计学家和实践者在可用的启发式的海洋中航行，并避免与使用它们相关的常见陷阱。