Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper develops an online bootstrap method to quantify the error of estimating the leading eigenvector of a matrix via Oja's algorithm. The authors a) find a closed from expression of the leading eigenvector from Oja's algorithm, b) approximate this closed from expression via Hoeffding decomposition for U-statistics, and c) devise a Gaussian multiplier bootstrap (algorithm) to approximate the distribution of the Hoeffding decomposition. The authors establish Gaussian approximation and bootstrap consistency results and include a small scale simulation study.
main_review: This is an interesting and well-written paper which balances rigorous theory and intuition in just the right way. I particularly enjoyed how the authors draw from classical statistical theory (U-statistics, Hoeffding decomposiiton) and modern theory (Gaussian approximation, hiogh-dim. bootstrap) to solve a relevant problem in machine learning.

I have the following comments:
1) Unfortunately, I do not understand Algorithm 1: Where are the $W_i$'s used? What are $Y_t$ and $Z_i$? I would appreciate if the authors could explain and clarify the notation.
2) Reg Theorem 1: To choose $\eta_n$ one has to gauge $\lambda_1 - \lambda_2$ and $M_d$. How do the authors do this in practice? How sensitive is their algorithm to values of $\eta_n$?
3) Line 187: Technically, convergence of the Kolmogorov distance in eq. (11) does not imply that the authors "establish the [limiting] distribution of $n/\eta_n(1- (v_1^T\hat{v}_1)^2)$" because the limiting distribution of $Z_n^TZ_n$ need not to exist. It would be more accurate to state that in the limit the difference of the distributions of $n/\eta_n(1- (v_1^T\hat{v}_1)^2)$ and $Z_n^TZ_n$ in Kolmogorov distance vanishes. And that's good enough for most (all?) statistical purposes.
limitations_and_societal_impact: I wished the authors had discussed how to choose the tuning parameters of their algorithm and included a more comprehensive simulation study. (The current simulation is based on a covariance matrix with very light correlation/ almost sparse. How does their method work on dense and/ or equicorrelated covariances)?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper study the problem of uncertainty quantification for the estimation error of the leading eigenvector from Oja's algorithm. The authors establish the distribution of $\sin^2$ error of the leading eigenvetor of Oja's algorithm. Also, the authors propose an online bootstrap algorithm for Oja's algorithm and provide the conditions under which the bootstrap is consistent. 

main_review: 
Strength:
1. Bootstrapping the error of Oja's algorithm is an interesting and important problem. The paper provides solid contributions to this problem.
2. The distribution of $\sin^2$ error of the leading eigenvetor of Oja's algorithm is novel.


Weakness:
1. The writing is not good. Some notations are confusing. For example, the variables $Y_t$ and $Z_i$ in Algorithm 1 are not defined. Also, some expectation notations lack brackets. For instance, in line 259, $\mathbb{E}ZZ^T$ should be $\mathbb{E}[ZZ^T]$.
2. The second comment is still about the writing. In Figure 1, what does the x-axis represent? Why the range of the x-axis of figures (C) and (D) are [0,1]? I suggest the authors can provide more descriptions on the figures.
3. I'm confused about the data generation of the experiment. The paper chooses $X=Z(\Sigma^{1/2})^T$, which indicates that $\mathbb{E}[X^T X]=\Sigma^{1/2}\mathbb{E}[Z^T Z]\Sigma^{1/2}$. Since $\mathbb{E}[Z^T Z]=nI$, the expectation of$X^T X$ should be $n\Sigma$ rather than $\Sigma$. Would you please tell me if I have missed something?

Overall, I think the paper provides some solid contributions to an important problem, but the writing of the paper should be polished.
limitations_and_societal_impact: See main review
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper the bootstrapped Oja scheme is considered. For the squared sin distance between the Oja’s scheme output and the first eigenvector of the covariance matrix of observations, the authors provide a Gaussian approximation and demonstrate bootstrap consistency. 
main_review: The authors consider a problem of quantification of uncertainty for Oja scheme in the framework for the streaming PCA. With this aim, the multiplier bootstrap is introduced in the update step of the Oja scheme. The proof of asymptotical Gaussian approximation for the squared sin distance and the asymptotical first term expansion of the squared sin error is based on the Hoeffding decomposition of the update matrices and high-dimensional CLT for the quadratic forms of random vectors and concentration and anti-concentration bounds. For the bootstrapped Oja the standard techniques lead to the bootstrap consistency result. In the end, the authors demonstrate the convergence of the bootstrapped CDF to the sampling CDF for the case of well-posed problems and further discuss the limitations.

The paper is overall quite well written. The following points could be corrected and clarified:  
1) S and S_k in the Eq. 5 are not defined 
2) In Algorithm 1 in the update step a vector estimate is missing in the brackets
3) In Algorithm 1 Z_i -> W_i 
4) In Remark 2, which is the referenced result? In [28] the error has log (d) in the nominator, and in the Remark 2 it is log(n)  
5) I am not sure I understand the condition (10) in view of (11), does the left-hand side of (10) contain anything depending on n?  
6) In supplementary material in Proposition A2 a number of the equation is missing

limitations_and_societal_impact: The learning rate in the considered version of Oja scheme assumes the knowledge of the number of upcoming observations (e.g. see [28]). 
Would not it be a limitation for the streaming PCA problem?
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Oja’s principal subspace algorithm is a well-known and powerful technique for learning and tracking principal information in a time series setting. In this paper, the authors use U-statistics and a concentration of matrix products to obtain an error estimate between the leading eigenvector and the output of Oja’s algorithm. The other eigenvectors are probably beyond the theoretical understanding of random matrix theory at the moment. There are two main contributions: (1) Establishes the distribution of the sin^2 error estimate for the leading eigenvector computed via Oja’s algorithm and (2) A stream-friendly bootstrap algorithm to compute quantiles of the error estimate. The paper contains an interesting theoretical analysis involving modern matrix random theory, and since they have the distribution, a potential application to bootstrapping. The main novelties in this paper are theoretical, and the author could better demonstrate the advantages of their online multiplier bootstrapping technique. 
main_review: The paper's main contribution is theoretical, and so to truly appreciate this paper, one must get into the technical details. The authors take the standard point-of-view and analyze Oja's algorithm as a limit of products of random variables. I am very impressed that they were able to establish the distribution of the sin^2 error between the leading eigenvector of X and the computed vector via Oja’s algorithm (see Theorem 1). It is implicit as the probability distribution is connected to the eigenvalues and eigenvectors of Sigma, limiting its practical application. To have some practice application of Theorem 1, the authors propose a streaming bootstrap procedure (see Theorem 2). 

The paper explains an overview of their analysis. After n iterations, Oja's algorithm can be expressed as a normalized matrix-vector product with a matrix B_n. Using Hoeffding decomposition, the authors write B_n as a sum of matrices that are uncorrelated (see (5)). This allows them to compute second-moment information of norms of B_n and consequential the distribution of the sin^2 error. For the bootstrapping idea, the authors use a comparison lemma. 

While I don't fully appreciate all the 36 pages of technical details in the supplementary materials, I hope that the authors can better describe their final practical algorithm. In fact, I have several confusions involving Algorithm 1:  

The input is u_0, but at the same time u_0 is assigned g/||g||. I think the authors want u_0 to be uniform on the sphere, so it shouldn't be an input. Also, what is Z_i in the algorithm (how to estimate their distribution)? I encourage the author's to write "Compute Y_t = X_tX_t^T - \Sigma" in the algorithm? How does one compute Sigma in Algorithm 1? What is the integer p in Algorithm 1? Theorem 1 needs the stepsize to go to infinite, but in Algorithm 1, it is constant. While Algorithm 1 presents the stepsize as constant, Section 4 uses log(n) (but what happens at n = 1?). Also, Theorem 1 presents an asymptotic result, but do the authors understand the optimal step size for the fastest convergence in probability? 

Here are a few grammar errors that I spotted while reading. I am sure the authors will want to correct them. 
 
l30: Define X. 

l65: "convergence rates which deteriorate" should read "convergence rates that deteriorate"

l105: "where the the random" should read "where the random" 

l161: "approximation to the distribution" should read "approximation of the distribution"

l163: "wew update" should read "we update"

l189: "growly wih n" should be "grow with n"

l191: "multivariate Gaussian distribution", do the authors mean "multivariate standard Gaussian distribution"? Otherwise, is the statement true?  

l249: "parameters of this distributions" should read "parameters of this distribution"

l260: "we use the later" should read "we use the latter"

l263: "that that of the" should read "that of the"

l276: "For step 2-3" should read "For steps 2-3"

References: put captials for: oja, bernstein, pca, fpca, robbins-monro, etc.
limitations_and_societal_impact: The expected limitations were discussed such as the analysis is only for the first principal vector of Oja's algorithm.
review_title: null

Meta-review: The reviewers were unanimous in their support for this paper, with a clear theoretical contribution to our understanding of an important algorithm. Most reviewers also felt the paper was well-written, and we thus feel it will be broadly interesting to the NeurIPS community.   
Decision: Accept (Spotlight)