Fast Regression with an _ Guarantee

Abstract

Sketching has emerged as a powerful technique for speeding up problems in numerical linear algebra, such as regression. In the overconstrained regression problem, one is given an n d matrix A, with n d, as well as an n 1 vector b, and one wants to find a vector x so as to minimize the residual error \|Ax-b\|_2. Using the sketch and solve paradigm, one first computes S A and S b for a randomly chosen matrix S, then outputs x' = (SA)^ Sb so as to minimize \|SAx' - Sb\|_2. The sketch-and-solve paradigm gives a bound on \|x'-x^*\|_2 when A is well-conditioned. Our main result is that, when S is the subsampled randomized Fourier/Hadamard transform, the error x' - x^* behaves as if it lies in a "random" direction within this bound: for any fixed direction a R^d, we have with 1 - d^-c probability that \[ a, x'-x^* \|a\|_2\|x'-x^*\|_2d^12- , (1) \] where c, > 0 are arbitrary constants. This implies \|x'-x^*\|_ is a factor d^12- smaller than \|x'-x^*\|_2. It also gives a better bound on the generalization of x' to new examples: if rows of A correspond to examples and columns to features, then our result gives a better bound for the error introduced by sketch-and-solve when classifying fresh examples. We show that not all oblivious subspace embeddings S satisfy these properties. In particular, we give counterexamples showing that matrices based on Count-Sketch or leverage score sampling do not satisfy these properties. We also provide lower bounds, both on how small \|x'-x^*\|_2 can be, and for our new guarantee (1), showing that the subsampled randomized Fourier/Hadamard transform is nearly optimal.

Tasks

Reproductions