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. 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 $\text{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.

Cited by in corpus (9)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• A Rank-1 Sketch for Matrix Multiplicative Weights
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
• An $\tilde{\mathcal{O}}(m/{\epsilon }^{3.5})$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints
• Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation