Optimal Randomized First-Order Methods for Least-Squares Problems

Jonathan Lacotte, Mert Pilanci

Abstract

We provide an exact analysis of a class of randomized algorithms for solving overdetermined least-squares problems. We consider first-order methods, where the gradients are pre-conditioned by an approximation of the Hessian, based on a subspace embedding of the data matrix. This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled randomized Hadamard transforms (SRHT). Our key technical innovation is the derivation of the limiting spectral density of SRHT embeddings. Leveraging this novel result, we derive the family of normalized orthogonal polynomials of the SRHT density and we find the optimal pre-conditioned first-order method along with its rate of convergence. Our analysis of Gaussian embeddings proceeds similarly, and leverages classical random matrix theory results. In particular, we show that for a given sketch size, SRHT embeddings exhibits a faster rate of convergence than Gaussian embeddings. Then, we propose a new algorithm by optimizing the computational complexity over the choice of the sketching dimension. To our knowledge, our resulting algorithm yields the best known complexity for solving least-squares problems with no condition number dependence.

Introduction

Solving overdetermined least-squares problems ($Ax=b$, where $n \gg d$) is a fundamental task in data science and engineering. While standard solvers require $O(nd^2)$ time, iterative methods like Gradient Descent offer a faster alternative. However, their efficiency is often hampered by the condition number ($\kappa$) of the data matrix $A$. Sketching techniques—multiplying $A$ by a random matrix $S$ to create a smaller "subspace embedding"—have emerged as a powerful tool to pre-condition these problems, making convergence independent of the original data's condition number. Despite their popularity, an exact theoretical understanding of the optimal convergence rates for different sketching matrices, particularly structured ones like the Subsampled Randomized Hadamard Transform (SRHT), has been lacking.

Methodology

This work provides a rigorous analysis of randomized first-order methods using Hessian Sketching. The authors analyze two primary embedding types: standard Gaussian projections and the computationally efficient SRHT ($O(nd \log m)$). The core technical contribution is the derivation of the limiting spectral density for SRHT matrices. By understanding the distribution of eigenvalues as dimensions grow, the authors leverage the theory of orthogonal polynomials to design a "Heavy-ball" style optimization method (Algorithm 2) with parameters specifically tuned to the geometry of the SRHT sketch.

Limiting spectral density of SRHT (solid blue) vs. Gaussian (dotted red) embeddings across different parameters.

Key Results

The analysis reveals that SRHT embeddings provide a strictly faster convergence rate than Gaussian embeddings for a fixed sketch size. This superiority stems from the "more orthogonal" nature of SRHT matrices, which results in a tighter eigenvalue distribution. Empirically, Algorithm 2 demonstrates significant efficiency gains, achieving a complexity of $O(nd \log d + d^3 + nd \log(1/\epsilon))$. This represents a $\log d$ factor improvement over previous state-of-the-art methods like Pre-conditioned Conjugate Gradient for dense problems.

Empirical convergence of Algorithm 2 (SRHT) compared to Gaussian and other baseline methods, showing faster error reduction.

Numerical simulations validate these theoretical findings. Even at relatively small matrix sizes ($n \approx 1000$), the empirical convergence matches the asymptotic predictions with high precision. The resulting algorithm is robust to ill-conditioned data, as its performance is decoupled from the original matrix's condition number.

Discussion and Limitations

While the asymptotic analysis provides powerful insights and matches experimental data well, formal finite-sample bounds remain a subject for future work. Additionally, the current framework is specialized for least-squares problems; extending this optimal polynomial approach to broader convex optimization tasks or sparse sketching matrices is an open challenge. In practice, minor "conservative perturbations" to theoretical parameters were used to ensure stability in finite-sample settings, suggesting room for further refinement of the theory.

Summary updated

Abstract

We provide an exact analysis of a class of randomized algorithms for solving overdetermined least-squares problems. We consider first-order methods, where the gradients are pre-conditioned by an approximation of the Hessian, based on a subspace embedding of the data matrix. This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled randomized Hadamard transforms (SRHT). Our key technical innovation is the derivation of the limiting spectral density of SRHT embeddings. Leveraging this novel result, we derive the family of normalized orthogonal polynomials of the SRHT density and we find the optimal pre-conditioned first-order method along with its rate of convergence. Our analysis of Gaussian embeddings proceeds similarly, and leverages classical random matrix theory results. In particular, we show that for a given sketch size, SRHT embeddings exhibits a faster rate of convergence than Gaussian embeddings. Then, we propose a new algorithm by optimizing the computational complexity over the choice of the sketching dimension. To our knowledge, our resulting algorithm yields the best known complexity for solving least-squares problems with no condition number dependence.
BibTeX
@inproceedings{lacotte2020optimal,
  author = {Jonathan Lacotte and Mert Pilanci},
  title = {{Optimal Randomized First-Order Methods for Least-Squares Problems}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=pziEG-TWYBS},
}
Figure