Statistical and Computational Tradeoffs in High 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.