Precise expressions for random projections: Low-rank approximation and randomized Newton

Abstract

It is often desirable to reduce the dimensionality of a large dataset by projecting it onto a low-dimensional subspace. Matrix sketching has emerged as a powerful technique for performing such dimensionality reduction very efficiently. Even though there is an extensive literature on the worst-case performance of sketching, existing guarantees are typically very different from what is observed in practice. We exploit recent developments in the spectral analysis of random matrices to develop novel techniques that provide provably accurate expressions for the expected value of random projection matrices obtained via sketching. These expressions can be used to characterize the performance of dimensionality reduction in a variety of common machine learning tasks, ranging from low-rank approximation to iterative stochastic optimization. Our results apply to several popular sketching methods, including Gaussian and Rademacher sketches, and they enable precise analysis of these methods in terms of spectral properties of the data. Empirical results show that the expressions we derive reflect the practical performance of these sketching methods, down to lower-order effects and even constant factors.

This version of the paper includes a correction to the assumptions in a technical result, Theorem 2. None of the other claims are affected by this change. The conference version of this paper does not include the correction, so we recommend to cite this arXiv version when referencing Theorem 2

References in corpus (14)

• Benign Overfitting in Linear Regression
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Exact expressions for double descent and implicit regularization via surrogate random design
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Inexact Non-Convex Newton-Type Methods
• Asymptotics for Sketching in Least Squares Regression
• Faster Least Squares Optimization
• Bounds on tail probabilities for quadratic forms in dependent sub-gaussian random variables
• Distributed estimation of the inverse Hessian by determinantal averaging
• How to reduce dimension with PCA and random projections?
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nyström method
• Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling