Timezone: »

Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
Zeyuan Allen-Zhu · Yuanzhi Li

Mon Aug 07 06:42 PM -- 07:00 PM (PDT) @ C4.4

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 \emph{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.

Author Information

Zeyuan Allen-Zhu (Microsoft Research / Princeton / IAS)
Yuanzhi Li (Princeton University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors