Abstract: 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…

Abstract: We consider estimation of parameters defined as linear functionals of solutions to linear inverse problems. Any such parameter admits a doubly robust representation that depends on the solution to a dual linear inverse problem, where the dual solution can be thought as a generalization of the inverse propensity function. We provide the first source condition double robust inference method that ensures asymptotic normality around the parameter of interest as long as either the primal or the dual inverse problem…

Abstract: We consider the Error-in-Operator (EiO) problem of recovering the source x signal from the noise observation Y given by the equation Y = A x + ε in the situation when the operator A is not precisely known. Instead, a pilot estimate \hat{A} is available. The study is motivated by Hoffmann & Reiss (2008), Trabs (2018) and by recent results on high dimensional regression with random design; see e.g., Tsigler, Bartlett (2020) (Benign overfitting in ridge regression; arXiv:2009.14286) Cheng, and Montanari (2022) (Dimension free ridge regression; arXiv:2210.08571), among many others. Examples of EiO include regression with error-in-variables and instrumental regression, stochastic diffusion, Markov time series, interacting particle…