Spring 2015

Sketching for M-Estimators: A Unified Approach to Robust Regression

Monday, March 16th, 2015 10:15 am10:40 am

Add to Calendar


Calvin Lab Auditorium

We give algorithms for regression for a wide class of M-Estimator loss functions. These generalize l_p-regression to fitness measures used in practice such as the Huber measure, which enjoys the robustness properties of l_1 as well as the smoothness properties of l_2. For such estimators we give the first input sparsity time algorithms. Our techniques are based on the sketch and solve paradigm. The same sketch works for any M-Estimator, so the loss function can be chosen after compressing the data.

Joint work with Ken Clarkson.