|Robust Sketching, and Smoothing for Time-Data Trade-Offs|
University of Colorado
Monday, January 26, 2015
The first part of the talk discusses sketching. A sketch is a Johnson-Lindenstrauss style transformation in the context of dimension reduction for the purpose of accelerating an algorithm. We argue that due to the uncertainty introduced, it makes sense to consider robust algorithms. In the context of least-squares, we show how to incorporate robustness, which leads to a method that is faster than traditional least-squares and more accurate than standard sketching approaches.
The second part of the talk is about computing with large data sets under a computational budget. From a statistical error perspective, more data samples are always better, but this introduces computational difficulties. By blindly applying algorithms designed for small data, one may end up doing worse than applying a simpler algorithm that is designed for large data. Similar ideas have been discussed before, but here we introduce a concrete plan ("smoothing") that makes these concepts precise, and both theoretically and experimentally show how our plan can improve prediction accuracy under a fixed time-constraint.