Executive Summary
This paper derives mathematically optimal first-order algorithms for solving large-scale least-squares problems using randomized sketching. By uncovering the hidden spectral properties of the Subsampled Randomized Hadamard Transform (SRHT), the authors prove that SRHT-based solvers converge significantly faster than standard Gaussian ones. Furthermore, they introduce a novel algorithm that achieves the best-known computational complexity for this fundamental class of optimization problems.
The Challenge: Large-Scale Least-Squares
Solving the classic least-squares problem—finding a vector $x$ to minimize $\|Ax - b\|^2$—is a cornerstone of data science and machine learning. However, when the data matrix $A$ is massive ($n \times d$ where $n \gg d$) and poorly conditioned (meaning its features are highly correlated), standard iterative methods like Gradient Descent become painfully slow.
To accelerate convergence, researchers frequently use sketching: multiplying $A$ by a random matrix $S$ to create a smaller "sketch" that preserves the original data's core properties. A popular technique is the Hessian Sketch, which uses this compressed representation to pre-condition the optimization process. While sketching is known to be effective, the optimal way to iterate—determining the exact step sizes and momentum parameters—has remained an open question. This is especially true for structured sketches like the SRHT, which are computationally faster to apply than simple Gaussian projections but mathematically harder to analyze.
Methodology: A Random Matrix Theory Approach
The authors analyze the optimization process through the lens of Random Matrix Theory. They focus on a class of pre-conditioned first-order methods where each new guess for $x$ is a linear combination of previous gradients, adjusted by a sketched Hessian ($H_S = A^T S^T S A$).
Key technical steps include:
- Deriving the Spectral Density: The authors derive the exact limiting spectral distribution (LSD) for SRHT embeddings. This is a major mathematical contribution, as the structured nature of SRHT makes it much harder to analyze than independent and identically distributed (i.i.d.) Gaussian matrices.
- Orthogonal Polynomials: Using the newly derived spectral density, they identify the specific family of orthogonal polynomials that minimize the optimization error at each iteration.
- Algorithm Design: These optimal polynomials are then translated into practical iterative update rules.
- For Gaussian sketches, the optimal method simplifies to the well-known Heavy-ball method with constant parameters.
- For SRHT sketches, the optimal method (Algorithm 2) requires non-constant step sizes and momentum parameters that dynamically evolve over time.
Key Insights
- SRHT > Gaussian: The most striking insight is that SRHT isn't just a "fast approximation" of a Gaussian sketch; it is fundamentally superior. Because SRHT rows are subsampled from an orthogonal basis, they "spread" the information of the matrix $A$ more effectively. This leads to a faster convergence rate for the exact same sketch size.
- Fixed is Better than Refreshed: Counter-intuitively, using the same random sketch for every iteration is better than generating a new one each time. A fixed sketch allows the algorithm to "learn" the specific errors of that sketch and compensate for them using optimized momentum.
- Universality: The optimal convergence rate depends only on the dimensions ($n, d, m$) and the type of sketch used, not on the specific singular values of the data matrix $A$. This makes the method highly robust for real-world data where the true spectrum is unknown.
Performance and Results
The theoretical findings were validated using synthetic datasets (matrices with exponential spectral decay to simulate hard, poorly-conditioned problems) as well as standard benchmarks like MNIST and CIFAR-10.
- Faster Convergence: The SRHT convergence rate is proven to be strictly faster than the Gaussian rate.
- Complexity Breakthrough: The proposed SRHT algorithm achieves a total time complexity of $O(nd \log m + md^2 + nd \log(1/\epsilon))$. For a fixed error $\epsilon$, this improves upon state-of-the-art methods (like the pre-conditioned conjugate gradient) by a factor of $\log d$.
- Empirical Match: Numerical simulations show that the empirical error curves match the theoretical predictions almost perfectly. This confirms that the "infinite-dimensional" math of Random Matrix Theory holds true and is highly accurate for practical, finite sample sizes (e.g., $n \approx 1000$).
Limitations and Future Directions
- Dense vs. Sparse: The current analysis focuses on dense matrices where SRHT is most effective. For very sparse matrices, other types of sketches (like Count-Sketch) might be preferable, though their spectral densities are much harder to characterize.
- Beyond Least-Squares: While this paper masters the quadratic case, extending these optimal first-order methods to general convex functions (like Logistic Regression) remains an open challenge, as the Hessian changes at every point in the domain.
- Finite-Sample Bounds: The theoretical results are asymptotic (as $n, d \to \infty$). While they work exceptionally well in practice for moderate sizes, formal high-probability bounds for very small samples were not the primary focus of this work.
Summary updated