Speaker: Pravesh Kothari

Abstract: Finding planted "signals" in random "noise" is a theme that captures problems arising in several different areas such as machine learning (compressed sensing, matrix completion, sparse principal component analysis, regression, recovering planted clusters), average-case complexity (stochastic block model, planted clique, random constraint satisfaction), and cryptography (attacking security of pseudorandom generators). For some of these problems (e.g. variants of compressed sensing and matrix completion), influential works in the past two decades identified the right convex relaxation and techniques for analyzing it that guarantee nearly optimal (w.r.t. to the information theoretic threshold) recovery guarantees. However these methods are problem specific and do not immediately generalize to other problems/variants. This talk is about a principled approach via the sum-of-squares method, to design and analyze a "right" convex relaxation that offers optimal recovery guarantees for a broad class of average case problems including all those listed above. I will illustrate this approach by focusing on the example of a recent work on outlier-robust linear regression. I will explain how the process of coming up with the convex relaxation and its analysis in this paradigm can be black-boxed into showing a "simple" proof of unique identifiability (i.e., a statement that the signal (such as mixture components/added clique/regression-hypothesis) is information-theoretically uniquely identified by the observed data.