Oja's Algorithm for Streaming Sparse PCA

Thank you for your kind words regarding the motivation of our problem and the simplicity of the presentation. We address your primary concerns below:

[Re: Novelty of fundamental ideas]: While our algorithm builds on top of Oja’s algorithm, hard thresholding of Oja’s vector for Sparse PCA has not been proposed or analyzed before. We introduce several novel ideas in this analysis and respectfully disagree with the claim of the lack of fundamental new ideas in our work. In what follows, we describe the motivation for the problem considered in our work, how it compares with relevant works under the computational and statistical regime of interest, and bring out the new ideas involved in our analysis.

Importance of the Problem Setting

Motivation: Sparse PCA has been a long-standing problem, with many algorithms being proposed in the literature, motivated both by theoretical ideas and practical applications. It has seen a lot of interest from the Computer Science and Statistics communities. Table 1 in our paper provides a detailed summary of various important contributions over the last two decades, along with their statistical performance as a function of various computational and model parameters.

Problem Statement: In this paper, we consider a variant of the problem that has been relatively unexplored in the literature - Can Sparse PCA be performed at the statistically optimal rate in linear time and space, without placing strong structural assumptions on the population covariance matrix?. The only papers which operate under this tight statistical and computational budget, to the best of our knowledge, are Johnstone and Lu [JL09], Yang and Xu [YX15], and Wang and Lu [WL16]. However, all of them require a spiked population covariance model for their analysis. Figure 1(a) compares the performance of these algorithms on a population covariance model which slightly deviates from the spiked model and shows how critical this assumption is for their performance.

Our Contribution: This question on the efficiency of PCA, without sparsity, has been asked before (see e.g. Jain et. al [2016]) and Oja's algorithm has emerged as one of the clear winners, achieving the statistically optimal rate under tight computational and space constraints. However, its extension under the sparsity assumption is challenging and has not been analyzed before. In fact, this algorithm, despite its simplicity, has not been proposed in its current form in the literature before. We therefore believe that this algorithm and its analysis provide a valuable step in the direction of computationally and space-efficient Sparse PCA algorithms which work without strong assumptions on the data distribution.

Novel Ideas in Our Analysis

1. We would like to point out that the analysis of thresholding, as pointed out by all other reviewers, is very different and novel, diverging significantly from analyzing regular Oja’s algorithm. In particular, it introduces a tight analysis of a system of linear recurrences, which is novel, as pointed out by Reviewer zu7o.

2. Our analysis further offers theoretical insights into the behavior of the entries of the Oja vector, which, to the best of our knowledge, has not been attempted before. In particular, Lemma 3.13 and 3.14 provide the first results of their kind and show that although the entries of the Oja vector do not concentrate, it is indeed possible to show a tail-bound on their deviation.

3. The closest algorithm to our work that we are aware of analyzes soft-thresholding of the Oja vector under a stronger assumption on the covariance model and an initialization close to the population eigenvector (see Wang and Lu, 2016). Furthermore, they provide a PDE-based asymptotic analysis of the problem, whereas our work provides a sharp and non-asymptotic rate of convergence.

[Re: Definition of $r_\mathsf{eff}$]: We define $r_\mathsf{eff}$ in Lines 4-5.

Dear Reviewer qSPb,

Thank you for your response. As per your suggestion, we will define $r_\mathsf{eff}$ in an equation after the abstract to make it easy to spot. We would also like to take this opportunity to reiterate that the proof techniques in our paper are completely different from those in the previous papers on streaming PCA and matrix products which were done under bounded $r_\mathsf{eff}$. We hope that our response has conveyed the novelty of our work. If you have any further questions that we can answer, please let us know.

Thank you for your kind words regarding our presentation, the novelty of our algorithm, the motivation of our problem, and the contribution to literature. We address your primary concerns below:

[Re: Top-k principal components] Recent results provide a black-box way to obtain k-PCA given an algorithm to extract the top eigenvector (see [a]) which could be employed treating our algorithm as a 1-PCA oracle. This deflation-styled approach has also been proposed in [b] in the context of Sparse PCA.

We also believe that an analysis such as [c] can be extended to the sparse setting to obtain top-k principal components simultaneously via QR decomposition and thresholding. This could be an interesting direction for future work.

References:

[a] Jambulapati, A., Kumar, S., Li, J., Pandey, S., Pensia, A. & Tian, K.. (2024). Black-Box k-to-1-PCA Reductions: Theory and Applications. Proceedings of Thirty-Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:2564-2607.

[b] Mackey, Lester. "Deflation methods for sparse PCA." Advances in neural information processing systems 21 (2008).

[c] Allen-Zhu, Zeyuan, and Yuanzhi Li. "First efficient convergence for streaming k-pca: a global, gap-free, and near-optimal rate." In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 487-492. IEEE, 2017.

Thank you for your kind and detailed feedback and comments about the clarity and presentation of our work, the novelty of our analysis, and the significance of our contribution to the Sparse PCA literature. We will correct all the typographical issues pointed out and will not address them here individually. We answer your primary concerns and suggestions below:

[Re: $y_0, u_0, w_0$, and $z_0$]: Thank you for pointing it out. We will take care to fix them in the final manuscript.

[Re: Over/under estimates of $\eta$]:: For step-sizes, we follow the convention in (Balsubramani et al. (2015), De Sa et al. (2015), Jain et al. (2016), Li et al (2017), Allen-Zhu et al. (2016)), Huang et al. (2021), where Oja’s algorithm is analyzed without sparsity and the optimal learning rate requires knowledge of the gap, $\lambda_{1} - \lambda_{2}$, and other model parameters to get the statistically optimal rate. Our sin-squared error roughly is of the form $O\left(\eta\lambda_1+\exp(-n\eta(\lambda_1-\lambda_2)\right)$. The optimal eta ensures that the first term dominates yielding our optimal error rates. However, a small $\eta$ resulting from plugging in an upper bound on the eigengap $\lambda_1-\lambda_2$ may make the second term dominate leading to a suboptimal sin-squared error. We will clarify this further.

[Re: Figure 1(a) and 2(a), (b)]: We have provided revised figures in the global author rebuttal document along with detailed explanations of each axis and the legend followed. Figure 1(a) plots the sine-squared error with iterations of the algorithm. The error bars currently represent standard deviations across 100 runs, leading to a negative error. We have now fixed that to plot the 25th and 75th percentile bars in the revised figure and added labels to the axes. Figures 2 (a), and (b) have also been revised with a larger font size and clear axis labels. The y-axis in Figure 2(a) has been corrected to read the “value” of the referenced quantity instead of “error” and dotted lines have been removed to avoid confusion. The line width has been increased to enhance clarity. The lines labelled “sample” plot $\log(|e_{i}^{\top}B_{n}u_{0}|)$, whereas the “population” curves plot $\log(|\mathbb{E}[e_{i}^{\top}B_{n}u_{0}]|)$.

[Re: $k \geq s$ in Theorem 3.2]: Our probability boosting argument for Algorithm 3 requires a distance metric, such that when the true support $S\in \hat{S}$, $d(S,\hat{S})\leq \epsilon$ for some small $\epsilon>0$. And not only that, we also crucially need that $d(S,\hat{S})\leq \epsilon$ implies that $\hat{S}$ contains $S$. This is easily done for $k=s$ since the metric is just the indicator function, which returns 0 if two sets are equal and 1 otherwise. With $k \geq s$, we were as of yet unable to create such a metric that would be amenable to boosting to high probability.

[Re: Prop 3.4]: Thank you for pointing that out. It should read “with sparsity parameter s, such that n = …”

[Re: Failure probability and $d^{-10}$]: This is primarily to show that the failure probability can be $\frac{1}{\mathsf{poly}(d)}$ without affecting the sample complexity or the error by more than a constant multiplicative factor.

[Re: Section 3.4 and [KLL+23]]: Although Section 3.4 is reminiscent of a standard median-of-means type analysis, we were unaware of other existing algorithms that extended this framework to vectors, apart from techniques such as the geometric median(also suggested by Jain et al. (2016) for probability boosting), which may or may not return a sparse vector. One advantage of [KLL+23] is that they choose a vector from the given set.

[Re: Eq(4) and absolute value terms]: As described on Line 221, the $\pm$ notation is used here to describe the bound on the deviation. That’s why the second term has an absolute value, which is an upper bound on the deviation.

[Re: Line 232 involving [SSM11]]: Thank you for pointing this out. Yes, you are indeed correct, this is indeed a condition number since the second eigenvalue is 1 here. We will clarify this in the revised manuscript.

[Re: General argument for $U=e_i$]: We use other matrices in place of U, such as U=I_S, in the proof to handle truncation assuming knowledge of the true support. Lemma A.5.1 provides a sketch of which terms come into play and the corresponding values of U which are important. We included that in the appendix in the interest of space and can provide a brief sketch in the extended manuscript after revision.

Thank you for your kind words regarding the problem statement considered, the simplicity and performance of our algorithm, and the novelty of our analysis. We will correct the matrix multiplication constant to ~2.372 based on recent developments (see [a]).

References:

[a] Williams, Virginia Vassilevska, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. "New bounds for matrix multiplication: from alpha to omega." In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3792-3835. Society for Industrial and Applied Mathematics, 2024.