Compressed Least Squares Regression revisited

Martin SlawskiAISTATS 2017

Introduction

In high-dimensional regression, where the number of features ($d$) exceeds the number of observations ($n$) or features are highly correlated, standard Ordinary Least Squares (OLS) often fails due to overfitting. Two primary remedies exist: Principal Components Regression (PCR), which utilizes Singular Value Decomposition (SVD) to project data onto a low-rank subspace, and Compressed Least Squares (CLS), which employs random projections via Johnson-Lindenstrauss transforms. While PCR is statistically robust, its computational cost is high. Conversely, CLS is efficient but has historically lacked a strong theoretical foundation, with prior proofs suggesting it required excessively large projected dimensions to be effective.

Refined Bias Analysis

This work rehabilitates CLS by providing a more granular analysis of its error decomposition into bias and variance. The core innovation lies in a refined bias bound. By leveraging tools from randomized numerical linear algebra, the author demonstrates that a random projection effectively captures the same dominant subspace targeted by PCR. This "randomized bias estimation" allows CLS to achieve prediction errors comparable to PCR without the heavy computational cost of a full SVD.

Empirical Validation

The theoretical findings are supported by experiments on both synthetic and real-world datasets.

Synthetic Experiments

The synthetic tests evaluated performance under different "spectral decay" conditions: constant, polynomial, and exponential. As shown in Figure 1, when the spectrum decays (polynomial or exponential), the bias and prediction error of CLS closely track those of PCR, validating the refined theoretical bounds.

Comparison of Bias and Prediction Error for PCR and CLS across different spectral decay types (constant, polynomial, exponential).

Real-World Performance: Twitter Buzz Dataset

To test scalability, the author used the Twitter Social Media Buzz dataset, expanded to 3,080 predictors. Figure 2 illustrates that CLS provides a statistically sound approximation of the optimal low-rank projection. While PCR achieves a slightly lower minimum test error, CLS reaches a comparable level of accuracy significantly faster—approximately 50 times faster than standard SVD implementations in MATLAB for this dataset.

Projection error (top) and test error (bottom) on the Twitter dataset, comparing PCR and CLS performance.

Key Insights

  • Decaying Spectrum is Essential: Both PCR and CLS rely on the data having a decaying spectrum. If the spectrum is flat, dimensionality reduction offers no advantage.
  • CLS as Randomized PCR: CLS is not merely a heuristic; it is a statistically potent alternative that bridges the gap between random projections and optimal low-rank approximations.
  • Computational Advantage: CLS is trivially parallelizable and remains the faster choice for massive datasets where SVD is prohibitive.

Conclusion

While CLS matches PCR's performance in many scenarios, it still shares the same fundamental assumption: the signal must align with high-variance dimensions. In cases where the model is sparse rather than low-rank, methods like Lasso may still be preferable. Future research may explore if specific conditions exist where CLS could statistically outperform PCR.

Summary updated

BibTeX
@inproceedings{slawski2017compressed,
  author = {Martin Slawski},
  title = {{Compressed Least Squares Regression revisited}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
}
Figure