Summary
The paper studies the problem of streaming sparse PCA under iid data. That is, we have $x_1,...,x_n \sim \mathcal D$ iid vectors in $\mathbb R^d$ which are revealed to us in an online fashion. We want to estimate the top eigenvector of $\Sigma = \mathbb E[xx^\intercal]$. We assume that this top eigenvector $v_1$ is $s$-sparse, for $s = O(\frac{n}{\log(n)})$. The error between the real and estimated top eigenvector is computed using the $\sin^2$ error metric $(1-\langle v_1, \tilde v_1\rangle^2)$.
This paper shows that Oja's algorithm can be used to both find the support of $v_1$ and the values in $v_1$ (assuming we are given some value $k \geq s$ and correctly choose a step size parameter).
This algorithm runs in $O(nd)$ time and $O(d)$ space.
The key technical assumptions made are:
- The data is iid subgaussian
- The sparsity of $v_1$ is $s = O(\frac{n}{\log (n)})$
- The effective dimension (ratio of trace to spectral norm) of the covariance matrix is at most $O(\frac{n}{\log(n) \sigma^2})$ where $\sigma^2 = \frac{\lambda_1}{\lambda_1 - \lambda_2} \cdot \frac{\lambda_2}{\lambda_1 - \lambda_2}$ measures the (square) of the singular value gap between the top two eigvals of $\Sigma$.
- The smallest nonzero entries of the (unit vector) top eigevnector $v_1$ is $\tilde\Omega(\frac{d^{1/8}}{n^{1/4}})$.
In contrast to prior works, this work achieves better $\sin^2$ error that prior $O(nd)$ time algorithms and $O(d)$ space algorithms. It also makes no assumption about the quality of the starting vector (i.e. it's not a local convergence result, it's a global convergence result).
The results are essentially all theoretical, with one experiments used to show that Oja works well here, and another used to elucidate which theoretical bounds are loose.
Strengths
The paper is a nice contribution to the literature, and it's well written. Sparse PCA is an important problem, and handling it in low space and time is important as well. The error metrics and assumptions are all reasonable. The paper is written clearly. It's just sorta all around solid.
The result is original in that it has a clear goal: achieve the $\sin^2$ error of large-space or large-time algorithms (those that use $\omega(nd)$ time or $\omega(d)$ space), but only using $O(nd)$ time and $O(d)$ space. It's especially nice that a pretty naive application of Oja's algorithm can achieve this.
There's also some nice novelty in the proof technique, which bounds the 2nd and 4th moments of the entries of the output of Oja's algorithm. In particular, the authors tighten a bound from the prior work by designing and solving a system of linear recurrences. A cool math setup that I do not often see.
I'm not an expert in the sparse pca world, not the streaming pca world, and certainly not streaming sparse pca. That said, assuming the authors are not omitting any relevant prior works, this results on low error in very low space and time seems pretty cool. It seems like a particularly nice step in the sparse PCA literature.
Weaknesses
There's a few notation inconsistency issues, some minor gripes. Nothing I'm really worried about. I'll push it all to the "questions" section below.
I accept this paper for publication.
Questions
None of these are game-breaking, and many of these are minor typos. Feel free to ignore whatever feels unfair to you. But, do at least make the notation for the initial vector consistent and make the figures easy to read.
1. Annoyingly, the authors __very often__ swap the symbols $y_0$, $u_0$, $w_0$, and $z_0$. Please fix this.
1. Figure 1 is too hard to read. The letters are too small. The axes have no labels. The error is negative somehow (if it's plotting $\pm1$ standard deviation, which is making the error bars negative, consider using 25th and 75th quantiles instead?).
1. It's not clear if Lemma 3.1 and Theorem 3.2 allow us to use over/underestimates of $\eta$, or if the theorems are very tied to that exact value of $eta$. Seems worth discussing.
1. It's not clear why Theorem 3.2 requires $k=s$ instead of $k\geq s$. Discussing this would be nice. Returning a vector whose support is $\log(1/\delta)$ times larger than $s$ seems fine to me, if that's the issue here.
1. Prop 3.4 is written a bit unclearly, namely around the "with sparsity parameter, $n=$" part, since $n$ is not a sparsity parameter.
1. Theorems 3.5 and 3.7 uses failure probability $d^{-10}$, which is fine I guess? But why not just use a $\delta$?
1. Remark 3.6 seems like it might make more sense to have back around assumption 2
1. Section 3.4 strikes me as a very standard analysis style. Not sure why you point to [KLL+23] specifically. You can say it's standard, and point to [KLL+23] as an example of this, maybe? If I'm missing something and it's not standard, lemme know.
1. Figure 2 is also too hard to read, especially in print. The letters are too small. The series look too much like each-other. The y-axis should be more specific in the error. It's not really clear what the dotted / population lines are showing -- is it $\log(E[e_i^\intercal B_n u_0])$, or is it $E[\log(e_i^\intercal B_n u_0)]$? Is it something else? What exactly does "error" mean here?
1. Line 221 can use $E[r_i | u_0]$ imo
1. Idk why equation (4) uses absolute values and $\pm$ on the non-top-eigenvalue terms. Isn't $E[B_n]$ PSD, and thus the second term guaranteed to be nonnegative?
1. Line 221 maybe mention that $E[B_n] = (1+\eta \Sigma)^t^?
1. Line 232 this line about [SSM11] taking $\lambda_1 = d^\alpha \rightarrow \infty$ is kinda confusing because it's not a scale-invariant claim. Is it like a condition number that's getting large?
1. Line 238 should mention that Section 4 explains the technique a bit more in detail
1. Line 247 should really point to Section 4 as well, explaining the technique in a bit more detail
1. [Line 256] If you have space, it'd be nice to understand why Theorem 3.5 needs a more general argument that $U = e_i$.