Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
By Zeyuan Allen-Zhu, Yuanzhi Li. 2017
47 citations recorded by the source corpus.
The online problem of computing the top eigenvector is fundamental to machine learning. In both adversarial and stochastic settings, previous results (such as matrix multiplicative weight update, follow the regularized leader, follow the compressed leader, block power method) either achieve optimal regret but run slow, or run fast at the expense of loosing a $\sqrt{d}$ factor in total regret where $d$ is the matrix dimension. We propose a $\textit{follow-the-compressed-leader (FTCL)}$ framework which achieves optimal regret without sacrificing the running time. Our idea is to "compress" the matrix strategy to dimension 3 in the adversarial setting, or dimension 1 in the stochastic setting. These respectively resolve two open questions regarding the design of optimal and efficient algorithms for the online eigenvector problem.
Subfields: Optimization & Training
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Optimization & Training
- Zeyuan Allen-Zhu
- Peter Richtárik
- Yuanzhi Li
- Mikhail Belkin
- Jakub Konecný
- Francis R. Bach
- Filip Hanzely
- Quanquan Gu
Citations in the corpus
- Natasha 2: Faster Non-Convex Optimization Than SGD (2017, background): “Our prior work [8] showed (see its last section) that 6 Theorem 3.”