NeurIPS 2020oral54 citations
Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method
Michal Derezinski, Rajiv Khanna, Michael W. Mahoney
Abstract
The Column Subset Selection Problem (CSSP) and the Nystrom method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning and scientific computing. A fundamental question in this area is: how well can a data subset of size k compete with the best rank k approximation? We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees which go beyond the standard worst-case analysis. Our approach leads to significantly better bounds for datasets with known rates of singular value decay, e.g., polynomial or exponential decay.
BibTeX
@inproceedings{NEURIPS2020_342c472b,
author = {Derezinski, Michal and Khanna, Rajiv and Mahoney, Michael W},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {4953--4964},
publisher = {Curran Associates, Inc.},
title = {Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/342c472b95d00421be10e9512b532866-Paper.pdf},
volume = {33},
year = {2020}
}