Events

MaD Seminar: Towards a general theory of low degree algorithms in statistics

Speaker: Tim Kunisky

Location: 60 Fifth Avenue, Room 7th floor open space

Date: Thursday, March 20, 2025

Understanding how effectively polynomials solve statistical problems like hypothesis testing and estimation has recently proven fruitful for making accurate predictions about computational hardness, statistical-to-computational gaps, and trade-offs between dataset quality and computational cost. I will present recent work that aims to unite many of these analyses and identify mathematical principles governing what such problems low degree polynomials can solve. I will first present low coordinate degree functions, a generalization of low degree polynomials that turns out to be essential to applying this kind of analysis beyond “integrable” statistical models having well-understood associated orthogonal polynomials. I will then show how the performance of these functions exhibits universality: whether or not they can detect a given continuous signal through a noisy channel depends very little on the structure of the channel, allowing existing analyses of low degree polynomials to be immediately generalized to a wide range of models. Finally, I will describe analogous phenomena and tools for models having discrete signals, such as stochastic block models and their generalizations.