We consider statistical and algorithmic aspects of solving large-scale least-squares (LS) problems using randomized sketching algorithms. Prior results show that, from an , when using sketching matrices constructed from random projections and leverage-score sampling, if the number of samples @math much smaller than the original sample size @math , then the worst-case (WC) error is the same as solving the original problem, up to a very small relative error. From a , one typically considers the mean-squared error performance of randomized sketching algorithms, when data are generated according to a statistical linear model. In this paper, we provide a rigorous comparison of both perspectives leading to insights on how they differ. To do this, we first develop a framework for assessing, in a unified manner, algorithmic and statistical aspects of randomized sketching methods. We then consider the statistical prediction efficiency (PE) and the statistical residual efficiency (RE) of the sketched LS estimator; and we use our framework to provide upper bounds for several types of random projection and random sampling algorithms. Among other results, we show that the RE can be upper bounded when @math is much smaller than @math , while the PE typically requires the number of samples @math to be substantially larger. Lower bounds developed in subsequent work show that our upper bounds on PE can not be improved.
@cite_4: We study randomized sketching methods for approximately solving least-squares problem with a general convex constraint. The quality of a least-squares approximation can be assessed in different ways: either in terms of the value of the quadratic objective function (cost approximation), or in terms of some distance measure between the approximate minimizer and the true minimizer (solution approximation). Focusing on the latter criterion, our first main result provides a general lower bound on any randomized method that sketches both the data matrix and vector in a least-squares problem; as a surprising consequence, the most widely used least-squares sketch is sub-optimal for solution approximation. We then present a new method known as the iterative Hessian sketch, and show that it can be used to obtain approximations to the original least-squares problem using a projection dimension proportional to the statistical complexity of the least-squares minimizer, and a logarithmic number of iterations. We illustrate our general theory with simulations for both unconstrained and constrained versions of least-squares, including @math -regularization and nuclear norm constraints. We also numerically demonstrate the practicality of our approach in a real face expression classification experiment.
Subsequent work by Pilanci and Wainwright @cite_4 also considers a statistical perspective of sketching. Amongst other results, they develop a lower bound which confirms that using a single randomized sketching matrix @math can not achieve a better PE than @math . This lower bound complements the upper bounds developed in this paper. Their main focus is to use this insight to develop an iterative sketching scheme which yields bounds on the SPE when an @math sketch is applied repeatedly.