Optimal Iterative Sketching Methods with the Subsampled Randomized Hadamard Transform
Random projections or sketching are widely used in many algorithmic and learning contexts. Here we study the performance of iterative Hessian sketch for least-squares problems. By leveraging and extending recent results from random matrix theory on the limiting spectrum of matrices randomly projected with the subsampled randomized Hadamard transform, and truncated Haar matrices, we can study and compare the resulting algorithms to a level of precision that has not been possible before. Our technical contributions include a novel formula for the second moment of the inverse of projected matrices. We also find simple closed-form expressions for asymptotically optimal step-sizes and convergence rates. These show that the convergence rate for Haar and randomized Hadamard matrices are identical, and asymptotically improve upon Gaussian random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionSimilar Papers 제목 키워드 기반
Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
Random projections or sketching are widely used in many algorithmic and learning contexts. Here we study the performance of iterative Hessian sketch for least-squares problems. By leveraging and extending recent results …
Dimensionality ReductionAn Iterative, Sketching-based Framework for Ridge Regression
Ridge regression is a variant of regularized least squares regression that is particularly suitable in settings where the number of predictor variables greatly exceeds the number of observations. We present a simple…
regressionInference in Randomized Least Squares and PCA via Normality of Quadratic Forms
Randomized algorithms can be used to speed up the analysis of large datasets. In this paper, we develop a unified methodology for statistical inference via randomized sketching or projections in two of the most fundament…
Gradient Coding with Iterative Block Leverage Score Sampling
We generalize the leverage score sampling sketch for $\ell_2$-subspace embeddings, to accommodate sampling subsets of the transformed data, so that the sketching approach is appropriate for distributed settings. This is …
regressionAn Investigation of Newton-Sketch and Subsampled Newton Methods
Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems i…
Dimensionality Reduction