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.

研究在线问题的顶部特征向量的计算方法。提出了一种 follow-the-compressed-leader（FTCL）算法，能够在不牺牲运行时间的情况下实现最优遗憾率。该算法在敌对和随机环境中均能提供最优解决方案，解决了在线特征向量问题的两个未解之谜。

跟随压缩的领袖：更快的特征向量在线学习和更快的 MMWU

Follow the Compressed Leader: Faster Online Learning of Eigenvectors and  Faster MMWU

We give faster algorithms and improved sample complexities for estimating the
top eigenvector of a matrix $\Sigma$ -- i.e. computing a unit vector $x$ such
that $x^T \Sigma x \ge (1-\epsilon)\lambda_1(\Sigma)$:
Offline Eigenvector Estimation: Given an explicit $A \in \mathbb{R}^{n \times
d}$ with $\Sigma = A^TA$, we show how to compute an $\epsilon$ approximate top
eigenvector in time $\tilde O([nnz(A) + \frac{d*sr(A)}{gap^2} ]* \log
1/\epsilon )$ and $\tilde O([\frac{nnz(A)^{3/4} (d*sr(A))^{1/4}}{\sqrt{gap}} ]
* \log 1/\epsilon )$. Here $nnz(A)$ is the number of nonzeros in $A$, $sr(A)$
is the stable rank, $gap$ is the relative eigengap. By separating the $gap$
dependence from the $nnz(A)$ term, our first runtime improves upon the
classical power and Lanczos methods. It also improves prior work using fast
subspace embeddings [AC09, CW13] and stochastic optimization [Sha15c], giving
significantly better dependencies on $sr(A)$ and $\epsilon$. Our second running
time improves these further when $nnz(A) \le \frac{d*sr(A)}{gap^2}$.
Online Eigenvector Estimation: Given a distribution $D$ with covariance
matrix $\Sigma$ and a vector $x_0$ which is an $O(gap)$ approximate top
eigenvector for $\Sigma$, we show how to refine to an $\epsilon$ approximation
using $ O(\frac{var(D)}{gap*\epsilon})$ samples from $D$. Here $var(D)$ is a
natural notion of variance. Combining our algorithm with previous work to
initialize $x_0$, we obtain improved sample complexity and runtime results
under a variety of assumptions on $D$.
We achieve our results using a general framework that we believe is of
independent interest. We give a robust analysis of the classic method of
shift-and-invert preconditioning to reduce eigenvector computation to
approximately solving a sequence of linear systems. We then apply fast
stochastic variance reduced gradient (SVRG) based system solvers to achieve our
claims.

该研究论文提出了一种基于随机优化和矩阵估计的算法，能够通过线性系统求解来计算矩阵（具有稳定秩）的顶部特征向量，并提供了更快的算法和改进的样本复杂度。