Sketching Structured Matrices for Faster Nonlinear Regression

Haim Avron, Vikas Sindhwani, David P. WoodruffNeurIPS 2013 · OpenReview

Introduction

This paper introduces a novel approach to performing nonlinear regression—such as polynomial fitting—on massive datasets by "sketching" structured matrices. By exploiting the mathematical properties of Vandermonde matrices, the authors develop algorithms that are faster than the time it takes to even read the expanded nonlinear data. This effectively achieves "sub-input sparsity" runtimes for complex regression tasks, offering a powerful tool for scalable machine learning.

The Challenge of Nonlinear Regression

In modern machine learning, capturing nonlinear relationships is crucial. A standard method is to expand features into polynomials (e.g., transforming a feature $x$ into $[1, x, x^2, \dots]$). However, this approach scales poorly: expanding a dataset with $n$ samples and $d$ features to degree $q$ creates a massive matrix of size $n \times (d \cdot q)$.

While "sketching"—randomly compressing a large matrix into a smaller one while preserving its essential properties—has revolutionized linear regression, applying it to these expanded nonlinear matrices is traditionally expensive. Standard practice requires either materializing the giant expanded matrix in memory or spending significant computational time processing it. The authors tackle a fundamental question: Can we solve nonlinear regression in time proportional to the original sparse data, rather than the massive expanded version?

Methodology: Exploiting Block-Vandermonde Matrices

The authors focus on Block-Vandermonde matrices, where each block represents a feature expanded into its powers. Their solution relies on several key technical innovations:

  1. Fast Structured Sketching: Instead of building the full expanded matrix $Z = T_q(A)$, the authors utilize a "Sparse Embedding Matrix" (a type of random projection). This can be applied to $Z$ implicitly, without ever fully calculating or storing $Z$.
  2. Fast Vandermonde Multiplication: They leverage the mathematical property that multiplying a vector by a Vandermonde matrix can be executed in $O(n \log^2 q)$ time using FFT-like operations.
  3. Tailored Algorithms:
  4. StructRegression-2: A solver for $l_2$ (least squares) regression that combines sparse embeddings with a second round of sketching (Subsampled Randomized Hadamard Transform) to reduce the problem to a highly manageable size.
  5. StructRegression-1: A more complex solver for $l_1$ (robust) regression. This uses a well-conditioned basis and a specialized sampling procedure to handle the "absolute deviation" loss function, which is notoriously harder to sketch than least squares.

Datasets & Performance

The authors evaluated their approach on several standard machine learning benchmarks, including MNIST (digit classification), CPU (hardware performance), ADULT (income prediction), CENSUS, and FOREST COVER.

Table comparing regression methods across various datasets.

In classification tasks, the proposed "Additive Polynomial Regression" consistently outperformed standard linear regression and often beat the popular Random Fourier Features method in terms of testing error. For instance, on the MNIST dataset, their method reduced the classification error from 14% (ordinary linear regression) down to 6.9%.

Key Results: Speedup and Accuracy

The empirical results confirm both the practical value of the modeling framework and the speedup benefits of randomized regression.

Performance metrics vs. Sketch Size: (a) Speedup, (b) Suboptimality of residual, and (c) Classification Error.
  • Speedup: On large-scale experiments, the sketching method achieved up to a 5x speedup over the exact solution while using a sketch size of only 15% of the original data.
  • Accuracy: The "suboptimality of residual" (a measure of how much worse the sketch is compared to the exact answer) remained remarkably low (around $10^{-1}$), even under significant compression.

Key Insights

  • Beating "Input Sparsity": Typically, the fastest an algorithm can run is $O(nnz(Z))$, where $nnz$ is the number of non-zero entries. Because $Z$ is an expansion of $A$, it has $q$ times more entries. The authors' algorithm runs in time closer to $nnz(A)$, meaning it processes the "implicit" matrix faster than it could read the "explicit" one.
  • Maclaurin vs. Fourier: While Random Fourier Features (RFF) are standard for approximating kernels, the authors demonstrate that a Maclaurin series expansion (which creates a Vandermonde structure) can be more flexible and sometimes more accurate for the same number of features.
  • Memory Efficiency: Because the expanded matrix is never fully stored, this method allows for high-degree polynomial regression on machines that would otherwise run out of RAM.

Limitations and Future Work

While highly effective, the approach has limitations. The current work relies heavily on the Vandermonde structure of monomial bases ($x, x^2, x^3$). Other basis functions, like splines or wavelets, might not fit this specific mathematical structure as neatly. Additionally, Vandermonde matrices are notoriously ill-conditioned as the degree $q$ increases; while sketching helps mitigate this, very high-degree expansions might still face numerical precision issues. Finally, while the $l_2$ bounds are tight, the $l_1$ algorithm has a higher polynomial dependence on dimensions in its theoretical runtime, suggesting room for further optimization in robust nonlinear regression.

Summary updated

Abstract

Motivated by the desire to extend fast randomized techniques to nonlinear $l_p$ regression, we consider a class of structured regression problems. These problems involve Vandermonde matrices which arise naturally in various statistical modeling settings, including classical polynomial fitting problems and recently developed randomized techniques for scalable kernel methods. We show that this structure can be exploited to further accelerate the solution of the regression problem, achieving running times that are faster than input sparsity''. We present empirical results confirming both the practical value of our modeling framework, as well as speedup benefits of randomized regression."
BibTeX
@inproceedings{avron2013sketching,
  author = {Haim Avron and Vikas Sindhwani and David P. Woodruff},
  title = {{Sketching Structured Matrices for Faster Nonlinear Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=Bk-Qa8-OWr},
}
Figure