Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Sketching as a Tool for Linear Algebra
Speaker:David P. Woodruff
coming from:IBM Almaden Research Center
Speakers Bio: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.
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Language:English
Date, Time and Location
Date:Friday, 27 January 2017
Time:11:00
Duration:45 Minutes
Location:Saarbrücken
Building:E1 4 - MPI-INF
Please note: New Room!
Room:019
Abstract
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.
Contact
Name(s):Pavel Kolev
Phone:+49 681 9325 1026
EMail:pkolev@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
Created by:Pavel Kolev, 01/13/2017 01:06 PMLast modified by:Uwe Brahm/MPII/DE, 01/27/2017 07:00 AM
  • Pavel Kolev, 01/26/2017 05:50 PM
  • Pavel Kolev, 01/13/2017 01:06 PM -- Created document.