Accelerating Machine Learning Algorithms with Adaptive Sampling
Mo Tiwari
The era of huge data necessitates highly efficient machine learning
algorithms. Many common machine learning algorithms, however, rely on
computationally intensive subroutines that are prohibitively expensive on large
datasets. Oftentimes, existing techniques subsample the data or use other
methods to improve computational efficiency, at the expense of incurring some
approximation error. This thesis demonstrates that it is often sufficient,
instead, to substitute computationally intensive subroutines with a special
kind of randomized counterparts that results in almost no degradation in
quality.