Abstract:

Much of the theory of machine learning is concerned with the optimization of non-convex functions. Convex relaxations and their associated heirarchies (sum-of-squares, lassere) provide a systematic approach for approximately optimizing non-convex functions. Recent breakthroughs in robust statistics have produced the first polynomial time (efficient) algorithms for computing the robust mean of a high dimensional gaussian. Building on these developments, we construct a framework for robust learning via convex relaxations yielding the first polynomial time algorithm for robust regression when the overwhelming majority of the dataset is comprised of outliers.