Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
Abstract
We study k-GenEV, the problem of finding the top k generalized eigenvectors, and k-CCA, the problem of finding the top k vectors in canonical-correlation analysis. We propose algorithms LazyEV and LazyCCA to solve the two problems with running times linearly dependent on the input size and on k. Furthermore, our algorithms are doubly-accelerated: our running times depend only on the square root of the matrix condition number, and on the square root of the eigengap. This is the first such result for both k-GenEV or k-CCA. We also provide the first gap-free results, which provide running times that depend on $1/\sqrt{\varepsilon}$ rather than the eigengap.
Cite
Text
Allen-Zhu and Li. "Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition." International Conference on Machine Learning, 2017.Markdown
[Allen-Zhu and Li. "Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition." International Conference on Machine Learning, 2017.](https://mlanthology.org/icml/2017/allenzhu2017icml-doubly/)BibTeX
@inproceedings{allenzhu2017icml-doubly,
title = {{Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition}},
author = {Allen-Zhu, Zeyuan and Li, Yuanzhi},
booktitle = {International Conference on Machine Learning},
year = {2017},
pages = {98-106},
volume = {70},
url = {https://mlanthology.org/icml/2017/allenzhu2017icml-doubly/}
}