Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization

Jonathan Lacotte, Mert Pilanci

In the era of massive datasets, solving regularized least-squares (often known as ridge regression) is a fundamental but computationally heavy task. A NeurIPS 2020 paper by Jonathan Lacotte and Mert Pilanci from Stanford University introduces a highly efficient way to handle this challenge. By adaptively "sketching" data based on its underlying complexity rather than its raw size, their method achieves significant speedups and memory savings over traditional solvers.

The Challenge of Scale in Ridge Regression

Given a data matrix $A$ of size $n \times d$ and a target vector $b$, ridge regression seeks to find a vector $x$ that minimizes the objective: $\|Ax - b\|_2^2 + \nu\|x\|_2^2$.

When $n$ and $d$ scale into the millions, standard direct solvers become prohibitively slow, requiring $O(nd^2)$ operations. Iterative solvers like Conjugate Gradient (CG) offer a more scalable $O(nd)$ per-iteration cost, but their convergence speed is heavily bottlenecked by the matrix's "condition number." If the data is poorly scaled, CG can take an impractical amount of time to converge.

"Sketching" has emerged as a popular workaround. By multiplying the data by a random matrix $S$, the dimension is reduced from $n$ to a much smaller $m$, making the problem easier to solve. However, traditional theory dictates that the sketch size $m$ must be at least as large as the original data dimension $d$. This paper challenges that assumption, demonstrating that if the data exhibits spectral decay, the "effective dimension" ($d_e$) is actually much smaller than $d$. The primary hurdle? The effective dimension is rarely known in advance.

The Solution: Adaptive Polyak-IHS

To bridge this gap, the authors propose the Adaptive Polyak-IHS (Iterative Hessian Sketch) method. This algorithm dynamically scales with a problem's effective dimension rather than the full data dimension.

Key components of the method include:

  • Adaptive Sketching: Instead of guessing an optimal sketch size $m$ upfront, the algorithm initializes at $m=1$. At each iteration, it monitors a "sketched Newton decrement"—a computationally inexpensive proxy that measures how rapidly the error is decreasing.
  • Dynamic Improvement Criterion: If the error reduction falls below a specific threshold, the algorithm rejects the current step, doubles the sketch size ($m \leftarrow 2m$), and re-sketches the data. This self-correcting feedback loop ensures the sketch size grows only as large as strictly necessary.
  • Sharp Concentration Bounds: The authors provide novel, tighter mathematical proofs for the behavior of Gaussian and Subsampled Randomized Hadamard Transform (SRHT) embeddings over ellipsoids. They prove that a sketch size proportional to $d_e$ (plus a logarithmic factor for SRHT) guarantees high-probability convergence.
  • Momentum Acceleration: The framework incorporates a "Heavy-ball" (Polyak) momentum technique to further accelerate convergence.

Key Insights and Performance

The algorithm was rigorously evaluated on standard machine learning benchmarks, including MNIST and CIFAR-10, focusing on both fixed regularization parameters and regularization paths.

1. The Power of Effective Dimension In regularized problems, the geometry of the search space forms an ellipsoid. The algorithm only needs high accuracy in directions where the data exhibits significant variance. By proving that $m \approx d_e$ is sufficient, the authors drastically reduce the computational burden.

2. SRHT Superiority The research highlights that SRHT (an orthogonal projection) is generally superior to Gaussian embeddings for practical applications. It is faster to compute—requiring $O(nd \log m)$ time compared to the $O(nmd)$ time needed for Gaussian embeddings.

3. Empirical Speedups and Memory Savings The total time complexity of the adaptive method is roughly $O(nd \log(1/\epsilon))$, but the most intensive operation (matrix factorization) scales with $d_e$ instead of $d$. On MNIST and CIFAR-10, the adaptive method reached high precision (e.g., $10^{-10}$ relative error) significantly faster than standard CG and state-of-the-art pre-conditioned CG (pCG). Furthermore, because the sketch size $m$ remains small, the algorithm requires vastly less memory to store the sketched Hessian matrix. It proved particularly robust when the regularization parameter $\nu$ was small—a scenario where standard iterative methods typically falter.

Limitations and Future Directions

While highly effective for dense matrices, the current SRHT-based approach leaves room for expansion:

  • Sparse Data: The authors suggest that integrating specialized "sparse embeddings" could further reduce the $O(nd)$ cost for sparse datasets.
  • Beyond Least-Squares: Extending this adaptive sketching logic to other loss functions (like Logistic Regression) or different regularizers (like $L_1$/Lasso) remains an open challenge.
  • Underdetermined Systems: The primary focus and empirical validation center on overdetermined systems ($n \gg d$). While the appendix touches on $d > n$ scenarios, further research is needed to fully optimize the method for underdetermined systems.

Ultimately, this paper provides a highly practical, self-tuning algorithm that removes the guesswork from randomized linear algebra, offering a faster, leaner approach to large-scale ridge regression.

Summary updated

Abstract

We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT). While current randomized solvers for least-squares optimization prescribe an embedding dimension at least greater than the data dimension, we show that the embedding dimension can be reduced to the effective dimension of the optimization problem, and still preserve high-probability convergence guarantees. In this regard, we derive sharp matrix deviation inequalities over ellipsoids for both Gaussian and SRHT embeddings. Specifically, we improve on the constant of a classical Gaussian concentration bound whereas, for SRHT embeddings, our deviation inequality involves a novel technical approach. Leveraging these bounds, we are able to design a practical and adaptive algorithm which does not require to know the effective dimension beforehand. Our method starts with an initial embedding dimension equal to 1 and, over iterations, increases the embedding dimension up to the effective one at most. Hence, our algorithm improves the state-of-the-art computational complexity for solving regularized least-squares problems. Further, we show numerically that it outperforms standard iterative solvers such as the conjugate gradient method and its pre-conditioned version on several standard machine learning datasets.
BibTeX
@inproceedings{lacotte2020effective,
  author = {Jonathan Lacotte and Mert Pilanci},
  title = {{Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=4EuGpUvISfM},
}
Figure