R440, Astronomy-Mathematics Building, NTU
(台灣大學天文數學館 440室)
Convex Relaxation for Robust Statistics
Morris Yau (University of California, Berkeley)
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.