Faster Least Squares Optimization

Abstract

We investigate iterative methods with randomized preconditioners for solving overdetermined least-squares problems, where the preconditioners are based on a random embedding of the data matrix. We consider two distinct approaches: the sketch is either computed once (fixed preconditioner), or, the random projection is refreshed at each iteration, i.e., sampled independently of previous ones (varying preconditioners). Although fixed sketching-based preconditioners have received considerable attention in the recent literature, little is known about the performance of refreshed sketches. For a fixed sketch, we characterize the optimal iterative method, that is, the preconditioned conjugate gradient as well as its rate of convergence in terms of the subspace embedding properties of the random embedding. For refreshed sketches, we provide a closed-form formula for the expected error of the iterative Hessian sketch (IHS), a.k.a. preconditioned steepest descent. In contrast to the guarantees and analysis for fixed preconditioners based on subspace embedding properties, our formula is exact and it involves the expected inverse moments of the random projection. Our main technical contribution is to show that this convergence rate is, surprisingly, unimprovable with heavy-ball momentum. Additionally, we construct the locally optimal first-order method whose convergence rate is bounded by that of the IHS. Based on these theoretical and numerical investigations, we do not observe that the additional randomness of refreshed sketches provides a clear advantage over a fixed preconditioner. Therefore, we prescribe PCG as the method of choice along with an optimized sketch size according to our analysis. Our prescribed sketch size yields state-of-the-art computational complexity for solving highly overdetermined linear systems. Lastly, we illustrate the numerical benefits of our algorithms.

References in corpus (8)

• Randomized algorithms for matrices and data
• Steepest descent and conjugate gradient methods with variable preconditioning
• On accuracy of approximation of the spectral radius by the Gelfand formula
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Asymptotics for Sketching in Least Squares Regression
• Preconditioning in Expectation
• High-Dimensional Optimization in Adaptive Random Subspaces
• Sparse sketches with small inversion bias

Cited by in corpus (12)

• Distributed Sketching Methods for Privacy Preserving Regression
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
• Distributed Averaging Methods for Randomized Second Order Optimization
• Hashing embeddings of optimal dimension, with applications to linear least squares
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
• Optimal Randomized First-Order Methods for Least-Squares Problems
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
• Ridge Regression with Frequent Directions: Statistical and Optimization Perspectives
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners
• Precise expressions for random projections: Low-rank approximation and randomized Newton