Statistical and Computational Tradeoffs in High Dimensional Learning

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

• 批准号: 1541100
• 负责人: Philippe Rigollet
• 金额: $ 45万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-02-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1541100&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.

对于各种统计程序，主要涉及在高维参数空间中搜索稀疏结构，已经观察到通过计算高效程序获得的性能与最佳过程之间的差距。示例包括稀疏回归，稀疏主成分分析，社区检测，聚类，网络分析和矩阵完成。这种观察暗示了存在固有的统计价格，用于使用计算有效方法。研究人员通过在理论计算机科学和统计学习理论之间绘制新的桥梁来研究这个价格的规模。实际上，该议程要求将当前的统计最佳选择概念转移到有限的计算能力下具有更大的相关性，并开发了实现该最佳性的新算法。最近建立了大数据，因为新规范正在导致统计范围的范式转移：计算能力是新的bottereck，而不是缺乏观察力。研究人员奠定了理论基础，以研究统计和计算性能之间的这种新权衡。这项研究的直接好处是帮助统计学家和从业者在可用的启发式方面导航海洋，并避免与使用它们相关的常见陷阱。