New Bounds on Compressive Linear Least Squares Regression

Ata KabánAISTATS 2014 · OpenReview

Abstract

In this paper, we provide a new analysis of compressive least squares regression that removes a spurious $\log N$ factor from previous bounds, where $N$ is the number of training points. Our new bound demonstrates that the bias introduced by data compression is independent of the size of the training set, offering a more robust theoretical foundation for random projections in large-scale machine learning.

Introduction

In the era of massive data, high-dimensional feature spaces ($d$) often make standard Ordinary Least Squares (OLS) regression computationally prohibitive. To address this, practitioners frequently employ random projections to squash data into a lower-dimensional space ($k \ll d$) before performing regression. This technique, known as Compressive OLS, significantly reduces the computational footprint.

Historically, the theoretical guarantees for Compressive OLS relied on the Johnson-Lindenstrauss Lemma (JLL) or the Restricted Isometry Property (RIP). These frameworks ensure that the entire geometry of the dataset—all pairwise distances or dot products—is preserved after compression. However, this global preservation comes at a cost: to satisfy JLL, the required dimension $k$ must scale with $\log N$. This implies a "logarithmic tax" where adding more data points necessitates a larger compressed dimension to maintain error bounds. This paper challenges that requirement, asking whether we truly need to preserve the entire geometry to solve a specific regression problem.

Methodology

This work utilizes a "first principles" approach to analyze the expected excess risk—the difference between the error of a model trained on compressed data and the optimal model in the original high-dimensional space. The analysis is conducted within the "fixed design" framework, where input features are treated as constants and labels are treated as random variables.

Direct Expectation Analysis

Unlike previous analyses that relied on "union bounds" (which consider the worst-case error across all $N$ points and introduce the $\log N$ factor), this paper calculates the exact expectation over the random projection matrix $R$.

Generalizing Random Matrix Theory

A core contribution of this work is the development of a new lemma to compute the expectation of the form $E[R^T R \Sigma R^T R]$. While previous results were often restricted to specific Haar (orthonormal) matrices, this generalization allows the theory to apply to any i.i.d. projection matrix with finite fourth moments. This theoretical expansion enables a broader understanding of how different types of random matrices affect regression performance.

Key Insights

Independence from $N$

The most significant finding is that the bias term in the error bound is independent of the training set size $N$. This suggests that Compressive OLS is far more robust for large-scale data than previously thought; the quality of the regression depends on the dimensionality of the compressed space and the structure of the optimal weight vector, not the number of observations.

The Role of Kurtosis

The analysis reveals that the statistical properties of the projection matrix entries—specifically the excess kurtosis ($\kappa$)—directly impact the compression quality.

  • Platykurtic distributions: Matrices with negative excess kurtosis (such as binary $\{-1, 1\}$ weights) provide tighter bounds than standard Gaussian projections.
  • Sparse projections: The theory shows that sparse projections can match the performance of Gaussian ones provided their kurtosis is zero.

Local vs. Global Preservation

The paper identifies that regression does not require global distance preservation. Instead, the error depends on how well the optimal weight vector ($w$) can be represented within the random subspace. If the problem is "compressible" (defined by a small Mahalanobis norm of $w$), a small $k$ suffices regardless of $N$.

Main Results

Theorem 1: Expected Risk

The paper establishes that the expected excess risk is bounded by: $$\text{Error} \leq \gamma \frac{k}{N} + \frac{1}{k} \|w\|^2_{\Sigma + (1+\kappa)Tr(\Sigma)I_d}$$ In this expression, the first term represents variance (which diminishes as $N$ grows), while the second term represents bias (which diminishes as $k$ grows). Crucially, $N$ does not appear in the bias term, proving the independence of compression error from the number of data points.

Theorem 2: High Probability Bounds

For subgaussian projection matrices, the author provides upper and lower bounds that hold with high probability. these results confirm that the $N$-independence observed in the expected risk holds true even in non-average cases.

Discussion and Limitations

While this work provides a tighter bound for Compressive OLS, it focuses on the fixed design setting. While these results often translate to random designs where inputs are stochastic, a formal proof for that setting remains for future work. Additionally, the high-probability bounds currently require the projection matrix to be subgaussian; whether this requirement can be relaxed to more general distributions is an open question. Finally, because the bounds depend on the norm of the unknown optimal weight vector $w$, they serve primarily as a theoretical framework for understanding compressibility rather than a prescriptive tool for selecting $k$ in practice.

Summary updated

Abstract

In this paper we provide a new analysis of compressive least squares regression that removes a spurious log N factor from previous bounds, where N is the number of training points. Our new bound ha...
BibTeX
@inproceedings{kaban2014new,
  author = {Ata Kabán},
  title = {{New Bounds on Compressive Linear Least Squares Regression}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=MzUmuXd4VuX},
}
Figure