A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares

Garvesh Raskutti, Michael W. Mahoney

TL;DR

This paper bridges the gap between algorithmic and statistical analyses of randomized sketching for large-scale least-squares problems. It introduces a unified framework to evaluate sketching methods based on both worst-case error (algorithmic) and mean-squared error (statistical), revealing that while residual error can be controlled with fewer samples, prediction error requires significantly more.

What Problem Does This Paper Address?

Solving large-scale Ordinary Least-Squares (OLS) problems, where the number of data points ($n$) and features ($p$) are massive, is computationally challenging. Randomized sketching offers a solution by using a smaller "sketch" of the data to approximate the full solution. However, prior work has largely focused on an algorithmic perspective, guaranteeing performance against worst-case data without statistical assumptions. This paper addresses the question of how these sketching methods perform from a statistical perspective, where data is assumed to follow a linear model with noise, and whether the insights from algorithmic guarantees translate to statistical efficiency.

Methods

The authors develop a unified framework to analyze sketching algorithms from both algorithmic (worst-case error, Cwc) and statistical (prediction efficiency, CPE, and residual efficiency, CRE) viewpoints. They define these criteria and then derive structural conditions on the sketching matrix $S$ that influence these performance measures. Specifically, they analyze how $S$ interacts with the left singular subspace of the data matrix $X$. The paper then provides theoretical upper bounds for CPE and CRE for several types of sketching matrices, including:

  • Leverage-score sampling with re-scaling (SR): Samples are chosen proportionally to their leverage scores and then re-scaled.
  • Leverage-score sampling without re-scaling (SNR): Samples are chosen proportionally to leverage scores but not re-scaled.
  • Uniform sampling (SUnif): Samples are chosen uniformly at random.
  • Random projections (SSGP, SHad): Matrices with i.i.d. Gaussian or subsampled Hadamard entries.

They also leverage existing lower bounds to show that their upper bounds for prediction efficiency are tight.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic data generation for empirical evaluation.

Key Insights and Ideas

  • Algorithmic vs. Statistical Trade-offs: The paper highlights that what guarantees good performance in a worst-case algorithmic setting doesn't always translate to optimal statistical performance.
  • Prediction Error is Harder to Control: Controlling prediction error (how well the model predicts new data) is significantly more challenging than controlling residual error (how well the model fits the observed data). This is because prediction error is scaled by $p$, while residual error is scaled by $n-p$.
  • Sketch Size Matters Differently: For residual efficiency, a sketch size $r$ only slightly larger than $p$ ($p \lesssim r \ll n$) is sufficient. However, for prediction efficiency, $r$ needs to be much closer to $n$ to achieve comparable performance.
  • Leverage Scores are Key (but with caveats): Leverage-score based sampling methods (especially without re-scaling) can offer sharper statistical bounds, but they require stronger assumptions about the data's leverage score distribution (e.g., a "k-heavy hitter" distribution).
  • Random Projections Offer Uniformity: Random projection methods (like SSGP and SHad) tend to "uniformize" the leverage scores of the data matrix, making their statistical performance less sensitive to the original data's structure.

Key Results

  • RE Bounds: For several sketching methods (SR, SSGP, SHad), residual efficiency (CRE) can be bounded with $r$ on the order of $p$ (e.g., $r \approx p \log p$).
  • PE Bounds: Prediction efficiency (CPE) bounds typically scale with $r$ being much closer to $n$ (e.g., $r \approx n$).
  • Lower Bounds Confirm PE Difficulty: Subsequent work by Pilanci and Wainwright (2014) provides lower bounds that confirm the $r \approx n$ requirement for good prediction efficiency is fundamental for single sketches.
  • Empirical Validation: Simulations show that leverage-score sampling without re-scaling (SNR) often performs best statistically, especially for non-uniform leverage scores. Projection-based methods (SSGP, SHad) are more stable when $r$ is close to $p$.

Limitations and Future Work

  • Model Assumptions: The statistical analysis relies on a standard linear model with homoscedastic noise. The behavior of sketching methods under model mis-specification is an open question.
  • Sketching Matrix Diversity: The paper analyzes a specific set of sketching matrices. There's a vast literature on other sketching techniques that could be evaluated using the proposed framework.
  • Iterative Sketching: While the paper focuses on single sketches, iterative sketching approaches (mentioned as future work) can achieve better prediction efficiency.
  • Robustness: The paper does not explicitly analyze the robustness of sketching methods to outliers or other data anomalies.
  • Computational Complexity: While sketching reduces computational cost, the paper's focus is on statistical and algorithmic guarantees, not a direct comparison of wall-clock times for all methods.

Summary updated

Abstract

We consider statistical as well as algorithmic aspects of solving large-scale least-squares (LS) problems using randomized sketching algorithms. For a LS problem with input data $(X, Y) \in \mathbb{R}^{n \times p} \times \mathbb{R}^n$, sketching algorithms use a sketching matrix, $S\in\mathbb{R}^{r \times n}$, where $r \ll n$. Then, rather than solving the LS problem using the full data $(X,Y)$, sketching algorithms solve the LS problem using only the sketched data $(SX, SY)$. Prior work has typically adopted an algorithmic perspective, in that it has made no statistical assumptions on the input $X$ and $Y$, and instead it has been assumed that the data $(X,Y)$ are fixed and worst-case (WC). Prior results show that, when using sketching matrices such as random projections and leverage-score sampling algorithms, with $p \lesssim r \ll n$, the WC error is the same as solving the original problem, up to a small constant. From a statistical perspective, we typically consider the mean-squared error performance of randomized sketching algorithms, when data $(X, Y)$ are generated according to a statistical linear model $Y = X \beta + \epsilon$, where $\epsilon$ is a noise process. 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 sketching algorithms. Among other results, we show that the RE can be upper bounded when $p \lesssim r \ll n$ while the PE typically requires the sample size $r$ to be substantially larger. Lower bounds developed in subsequent results show that our upper bounds on PE can not be improved. (A preliminary version of this paper appeared as Raskutti and Mahoney (2014, 2015).)
BibTeX
@article{raskutti2016statistical,
  author = {Garvesh Raskutti and Michael W. Mahoney},
  title = {{A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares}},
  journal = {J. Mach. Learn. Res.},
  year = {2016},
  url = {https://openreview.net/forum?id=4o0V2anGQZ},
}

Loading related content...

Figure