NeurIPS 2019spotlight13 citations
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
Abstract
Given a n-by-d data matrix A, principal component projection (PCP) and principal component regression (PCR), i.e. projection and regression restricted to the top-eigenspace of A, are fundamental problems in machine learning, optimization, and numerical analysis. In this paper we provide the first algorithms that solve these problems in nearly linear time for fixed eigenvalue distribution and large n. This improves upon previous methods which had superlinear running times when either the number of top eigenvalues or gap between the eigenspaces were large.
BibTeX
@inproceedings{NEURIPS2019_3b92d18a,
author = {Jin, Yujia and Sidford, Aaron},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/3b92d18aa7a6176dd37d372bc2f1eb71-Paper.pdf},
volume = {32},
year = {2019}
}