Loading Events
  • This event has passed.
Stochastics and Statistics Seminar

Fine-Grained Extensions of the Low-Degree Testing Framework

September 8, 2023 @ 11:00 am - 12:00 pm

Alex Wein (University of California, Davis)


The low-degree polynomial framework has emerged as a versatile tool for probing the computational complexity of statistical problems by studying the power and limitations of a restricted class of algorithms: low-degree polynomials. Focusing on the setting of hypothesis testing, I will discuss some extensions of this method that allow us to tackle finer-grained questions than the standard approach.

First, for the task of detecting a planted clique in a random graph, we ask not merely when this can be done in polynomial time O(n^c), but seek the optimal exponent c as a function of the clique size. To this end, we consider algorithms that make non-adaptive edge queries and then apply a low-degree test, and we determine the number of queries required. This is joint work with Jay Mardia and Kabir Verchand.

Second, in the spiked Wigner model with any iid spike prior, we seek the precise optimal tradeoff curve between type I and type II error rates. Conditional on an appropriate strengthening of the “low-degree conjecture,” we show that tests based on the spectrum achieve the best possible tradeoff curve among poly-time algorithms, while exponential-time non-spectral tests can do better. This is joint work with Ankur Moitra.

Alex Wein received his PhD from MIT Mathematics in 2018 supervised by Ankur Moitra. He is now an Assistant Professor of Mathematics at UC Davis. His research spans theoretical computer science, statistics, probability, and data science, with an emphasis on understanding the computational complexity of high-dimensional statistical inference. He is a recipient of the 2018 Charles W and Jennifer C Johnson Prize from MIT, and the 2023 Sloan Research Fellowship.

MIT Statistics + Data Science Center
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307