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 losing a $\sqrt{d}$ factor in total regret where $d$ is the matrix dimension. We propose a 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.
Introduction
In the online eigenvector problem, an algorithm must choose a unit vector $w_k$ at each time step $k$. Subsequently, an adversary reveals a matrix $A_k$, and the algorithm receives a gain $w_k^\top A_k w_k$. The objective is to minimize regret, defined as the difference between the gain of the best fixed vector in hindsight and the cumulative gain of the algorithm.
Historically, practitioners have faced a stark choice:
- Matrix Multiplicative Weight Update (MMWU): Provides optimal $O(\sqrt{T})$ regret but requires a full eigendecomposition at every step, leading to a high computational cost of $O(d^\omega)$.
- Follow the Perturbed Leader (FTPL): Offers significantly faster iterations but suffers from a sub-optimal regret bound that is $\sqrt{d}$ times larger than MMWU.
The FTCL framework presented by Allen-Zhu and Li (2017) resolves this tension, providing a method that is both theoretically optimal and computationally efficient.
The Follow-the-Compressed-Leader (FTCL) Framework
The core innovation of FTCL is the "compression" of the matrix strategy. Instead of maintaining a full $d \times d$ weight matrix, FTCL projects the strategy onto a much lower-dimensional subspace.
- Adversarial Setting: The authors demonstrate that compressing the matrix strategy to just dimension 3 using random Gaussian vectors is sufficient to maintain the optimal $O(\sqrt{T})$ regret.
- Stochastic Setting: When matrices are sampled from a fixed distribution, the strategy can be compressed to dimension 1. This insight reveals that Oja’s algorithm—a classic heuristic for streaming PCA—is essentially a 1D compressed version of MMWU, finally proving its optimality in stochastic environments.
Computationally, FTCL replaces expensive eigendecompositions with the solution of a small number of linear systems. This allows the algorithm to leverage fast iterative solvers, drastically reducing the time per iteration.
Theoretical Comparison
The following table compares FTCL with existing state-of-the-art methods. FTCL is the first framework to achieve optimal regret while maintaining competitive time complexity.
Empirical Evaluation
The authors tested FTCL against MMWU and FTPL using three synthetic matrix sequences ($d=100, T=10000$):
- Random: Matrices from a Wishart distribution.
- Diagonal: The leading eigenvector rotates through the standard basis.
- Diagonal + Rotation: A challenging scenario where the eigenbasis changes gradually over time.
As shown in Figure 1, FTCL consistently matches the performance of the computationally expensive MMWU. Notably, in the "diagonal+rotation" case, the faster FTPL method fails to maintain low regret, while FTCL remains optimal.
Conclusion
The Follow-the-Compressed-Leader framework bridges the long-standing gap between theoretical optimality and practical efficiency in online eigenvector learning. By demonstrating that low-dimensional projections can capture sufficient information for optimal regret, the authors resolve key open questions and provide a powerful new tool for high-dimensional online matrix problems.
Summary updated