CAREER: Low-Degree Polynomial Perspectives on Complexity

Throughout science and industry, massive datasets are ubiquitous in the modern world, and they hold great potential for knowledge. They also pose a challenge: how to best extract the information we desire — be it the structure of a molecule, the mutation responsible for a disease, the community structure in a network, etc. — in the overwhelming presence of random noise. There is a cost to acquiring data, so we desire algorithms for data analysis that are statistically efficient, that is, they have the minimum possible requirements on the quantity and quality of data. We are also constrained to use algorithms that are computationally efficient, that is, the runtime is practical, even for very large problem sizes. However, sometimes it is fundamentally impossible to achieve both these goals simultaneously, and this project aims to understand what tradeoffs are possible and how to achieve them. The results of this project are expected to advance foundational knowledge that can be used to design algorithms and prove they are optimal in a wide variety of settings. This will deepen our fundamental understanding of how to develop the best possible methods for large-scale statistical inference, taking both statistical and computational considerations into account. As part of the education plan for this project, the researcher, who is a member of the mathematics department, will take a leading role in the development of the data science major at his university, which will draw students from many disciplines. This effort will involve development of course materials at the undergraduate level to help students gain a strong foundation in data science. The project will also involve mentorship of graduate students to train the next generation of data scientist researchers. Specifically, this project aims to understand fundamental statistical-computational tradeoffs by studying the power and limitations of low-degree polynomial (LDP) algorithms, a class of algorithms that is tractable to analyze yet still very powerful, capturing the best known algorithms for a wide array of statistical tasks. For a given statistical task, this framework allows us to systematically produce algorithms that both provably succeed and are provably optimal (within the LDP class). This project aims to broaden the LDP framework’s applicability by (1) developing tools to analyze the limitations of LDP algorithms for new types of statistical tasks that previously had no tools to attack; (2) understanding when algebraic structure can be exploited for improved inference by studying orbit recovery problems, which are both mathematically rich and have real-world applications such as cryo-electron microscopy; and (3) applying the LDP framework in settings beyond Bayesian inference in order to shed new light on areas such as robust statistics and approximation algorithms. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.