Adaptive Sketches for Robust Regression with Importance Sampling
This work addresses the computational bottleneck of implementing importance sampling in large-scale machine learning, offering a practical solution for faster convergence in robust regression tasks.
The paper tackles the problem of slow convergence in stochastic gradient descent (SGD) due to high variance from uniform sampling by introducing data structures for robust regression that enable importance sampling with sublinear space and a single data pass, achieving efficient SGD with nearly optimal sampling distributions.
We introduce data structures for solving robust regression through stochastic gradient descent (SGD) by sampling gradients with probability proportional to their norm, i.e., importance sampling. Although SGD is widely used for large scale machine learning, it is well-known for possibly experiencing slow convergence rates due to the high variance from uniform sampling. On the other hand, importance sampling can significantly decrease the variance but is usually difficult to implement because computing the sampling probabilities requires additional passes over the data, in which case standard gradient descent (GD) could be used instead. In this paper, we introduce an algorithm that approximately samples $T$ gradients of dimension $d$ from nearly the optimal importance sampling distribution for a robust regression problem over $n$ rows. Thus our algorithm effectively runs $T$ steps of SGD with importance sampling while using sublinear space and just making a single pass over the data. Our techniques also extend to performing importance sampling for second-order optimization.