Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Consider the task of hypothesis testing between two distributions Q and P, with the goal of minimizing the type I and type II error rates. The Neyman-Pearson lemma characterizes the Pareto frontier of all tests; in particular the ensemble of tests obtained by thresholding the likelihood ratio function is Pareto-optimal. Unfortunately in many high-dimensional settings, likelihood ratio tests are not efficiently computable, and we expect that the Pareto frontier of all computationally efficient tests is strictly weaker than that provided by the likelihood ratio. In these cases, the relevant question becomes to characterize the "efficient Pareto frontier".

• We propose a "fix" to the Neyman-Pearson lemma, conjecturing that in many settings, the efficient Pareto frontier is characterized by tests based on a low-degree truncation of the likelihood ratio (which is computable in polynomial time).

• We provide a recipe for proving such a statement when Q is a high-dimensional product distribution (contingent on a significantly weaker computational hardness assumption).

• We show how to instantiate our recipe for specific concrete distributions Q and P of interest, like the spiked Wigner model below the BBP threshold.

This talk is based on joint works with Prasad Raghavendra and Alex Wein.