David P. Woodruff is a prominent researcher at IBM Almaden. He graduated his Ph.D. at MIT in 2007 under the supervision of Piotr Indyk. He is the recipient of numerous awards, including the “Presburger Award from EATCS”, the “IBM Pat Goldberg Award”, and the “IBM Master Inventor Award” (with more than 20 U.S. Patents). Also, he is recognized for “Outstanding IBM Research Division Accomplishments” and he is a member of the “IBM Academy of Technology”. He has a strong record of publications in prestigious conferences such as STOC, FOCS, SODA, ICALP, PODS and NIPS. Most recently, he wrote an excellent book “Sketching as a Tool for Numerical Linear Algebra” summarizing a rapidly emerging subfield of TCS which has many applications in machine learning.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

MPI Audience

English

45 Minutes

Saarbrücken

We give near optimal algorithms for regression, low rank approximation, and robust variants of these problems. Our results are based on the sketch and solve paradigm, which is a tool for quickly compressing a problem to a smaller version of itself, for which one can then run a slow algorithm on the smaller problem. These lead to the fastest known algorithms for fundamental machine learning and numerical linear algebra problems, which run in time proportional to the number of non-zero entries of the input. We first give algorithms for least squares regression, and robust variants such as l_p regression and M-Estimator loss functions. Then we give algorithms for approximate singular value decomposition, and robust variants such as minimizing sum of distances to a subspace, rather than sum of squared distances.

Pavel Kolev

+49 681 9325 1026

--email hidden

passcode not visible

logged in users only