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.
Speaker Biography
David Woodruff received his Ph.D. from MIT in 2007 and has been a research scientist at IBM Almaden since then. His research interests are in big data, including communication complexity, compressed sensing, data streams, machine learning, and numerical linear algebra. He is the author of the book “Sketching as a Tool for Numerical Linear Algebra”. He received best paper awards in STOC and PODS, and the Presburger award.