Talk: Understanding Statistical-vs-Computational Tradeoffs via Low-Degree Polynomials

Abstract: A central goal in modern data science is to design algorithms for statistical inference tasks such as community detection, high-dimensional clustering, sparse PCA, and many others. Ideally these algorithms would be both statistically optimal and computationally efficient. However, it often seems impossible to achieve both these goals simultaneously: for many problems, the optimal statistical procedure involves a brute force search while all known polynomial-time algorithms are statistically sub-optimal (requiring more data or higher signal strength than is information-theoretically necessary). In the quest for optimal algorithms, it is therefore important to understand the fundamental statistical limitations of computationally efficient algorithms.

I will discuss an emerging theoretical framework for understanding these questions, based on studying the class of "low-degree polynomial algorithms." This is a powerful class of algorithms that captures the best known poly-time algorithms for a wide variety of statistical tasks. This perspective has led to the discovery of many new and improved algorithms, and also many matching lower bounds: we now have tools to prove failure of all low-degree algorithms, which provides concrete evidence for inherent computational hardness of statistical problems. This line of work illustrates that low-degree polynomials provide a unifying framework for understanding the computational complexity of a wide variety of statistical tasks, encompassing hypothesis testing, estimation, and optimization.

Bio: Alex Wein is currently a Postdoctoral Fellow at Georgia Tech, hosted by Santosh Vempala. Previously he was a Simons-Berkeley Research Fellow at UC Berkeley, and before that, a Courant Instructor at NYU. He obtained his PhD from the MIT Department of Mathematics in 2018, supervised by Ankur Moitra. His work is centered on mathematical foundations of data science, aiming to understand optimal algorithms and fundamental limitations for solving high-dimensional inference and optimization problems in a computationally efficient manner.