ICML 2017poster48 citations
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
Abstract
The online problem of computing the top eigenvector is fundamental to machine learning. The famous matrix-multiplicative-weight-update (MMWU) framework solves this online problem and gives optimal regret. However, since MMWU runs very slow due to the computation of matrix exponentials, researchers proposed the follow-the-perturbed-leader (FTPL) framework which is faster, but a factor $\sqrt{d}$ worse than the optimal regret for dimension-$d$ matrices. We propose a
BibTeX
@InProceedings{pmlr-v70-allen-zhu17d,
title = {Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster {MMWU}},
author = {Zeyuan Allen-Zhu and Yuanzhi Li},
booktitle = {Proceedings of the 34th International Conference on Machine Learning},
pages = {116--125},
year = {2017},
editor = {Precup, Doina and Teh, Yee Whye},
volume = {70},
series = {Proceedings of Machine Learning Research},
month = {06--11 Aug},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v70/allen-zhu17d/allen-zhu17d.pdf},
url = {https://proceedings.mlr.press/v70/allen-zhu17d.html},
abstract = {The online problem of computing the top eigenvector is fundamental to machine learning. The famous matrix-multiplicative-weight-update (MMWU) framework solves this online problem and gives optimal regret. However, since MMWU runs very slow due to the computation of matrix exponentials, researchers proposed the follow-the-perturbed-leader (FTPL) framework which is faster, but a factor $\sqrt{d}$ worse than the optimal regret for dimension-$d$ matrices. We propose a