Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work analysis streaming PCA algorithms in the time varying covariance model and shows that the noisy power method that relies on a batch of samples at each update is Reta-optimal, as opposed to Oja's method that relies on a single sample per update. The proposed theory deviates from the mainstream setting where the fixed covariance model is employed. The proposed theory sheds light onto the performance of streaming PCA algorithms in a setting where the covariance matrix changes over time. The proposed theory is demonstrated practically on synthetic data.
strengths_and_weaknesses: Strengths:
1. The paper is well-written and has a good flow.
2. The proposed theory is motivated with practical examples.
3. This work provided convergence analysis two important algorithms, namely the noisy power method and Oja's method under time varying covariance model.
4. The proposed theory in corroborated by synthetic studies.

Weaknesses:
1. Multiple redundant words and typos. 
2. Some of the text is hard to follow.
3. Some analysis of the synthetic studies is missing.



questions: 1. Multiple redundant words and typos (e.g., 2 in line 38 instead of (2), "of" in line 133, "the" in line 136, "zt" instead of "wt" in line 224, period in line 318). Please go through the paper again and fix all inconsistencies. 

2. Please rephrase lines 97-98. They are hard to follow. 

3. Lines 135-139 present how quickly the At can vary. This is not mentioned earlier in the abstract or the introduction. Please mention this briefly in the abstract and/or introduction so that the reader is aware of this setting and is not misled into assuming no conditions on the rate of change of At.

4. Is the assumption 1 in definition 1 relevant in practice? Please provide examples.

5. Does Algorithm 1 need input batch size, B, with xt? If so, please add it to the pseudocode. 

6. Does algorithm 2 require input learning rate, \zeta? If so, please add it to the pseudocode. 

7. Line 301 refers to line 6 in Algorithm 2 but there are only 5 lines. Please edit this typo.

8. In the experimental studies, can we please see what happens for larger perturbation \Tau? Does the trend in Figure 1(a) hold for larger \Tau?

9. Please comment on the behavior of Oja's algorithm in Figure 1(a). It appears that larger learning rates are better for larger perturbations. Why? Please elaborate.

limitations: A limitation is method in the text and posed a future work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a novel streaming principal component analysis (PCA) method. A major novelty in the model is that the it investigates a robust perspective, where the covariance matrix belongs to a temporal uncertainty set.

The contributions are two-fold. On one hand, the paper provides a fundamental lower bound for estimating the principal components within the considered framework, namely when the covariance matrix belongs to a temporal uncertainty set. On the other hand, the authors provide an analysis for two algorithms to recover the principal components extensively used in the standard streaming PCA setting.
strengths_and_weaknesses: 
The paper is relatively well written, and the contributions are clearly identified.

A major issue of this paper is its position within the state of the art. While the authors do cite some relevant related methods, it seems that the authors either consider robust PCA literature, or streaming PCA literature, but never both frameworks.

Another issue with respect to the state of the art is that the authors provide some critics wrt related works [46, 11, 50, 25], as they consider “Oja’s algorithm … and do not provide a benchmark comparison”. However, this is exactly what the present paper does: it presents an Oja’s algorithm, and does not provide a benchmark comparison.

Experiments are not comprehensive. It is missing any analysis with a comparative study, neither in the main paper nor in the appendix. It is also missing some benchmark on real datasets that allows to clearly motivate the proposed work.

There are many spelling and grammatical errors, such as “it satisfies mild condition”, “the columns form basis”, “the ith largest eigenvalue “, “and and”, “we assume … and then draws”, “it is hard to compute of the“, “Note that if the we…”, “These feature models the behavior”, “these hypothesis”, “We consider following algorithms…”, “We used following parameters”,… and many others. A proofreading of the paper is required.
questions: See Weaknesses, mainly related to positioning with respect to the state of the art and weak experimentations.
limitations: See Weaknesses
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the properties of streaming PCA in a dynamic environment.  In particular, the authors consider the problem of recovering the top k eigenvectors of the last observation in the stream even when the associated covariance matrices are drifting.  The authors establish a minimax lower bound for the problem and show that the iterated power method achieves the minimax rate.  They also derive convergence rates for Oja’s algorithm in this setting, another commonly used method for streaming PCA. 

strengths_and_weaknesses: Strengths:
- The authors address an interesting problem that, to the best of my knowledge, has not been studied very much: streaming PCA with time-varying covariance matrices.  
- The authors consider the problem of recovering the top k eigenvectors opposed to the the top eigenvector, which has only recently started to be addressed in some generality in the streaming PCA literature. 
- The minimax rate is a nice result that characterizes the difficulty of the problem and also quantifies the effect of drift well.  
- The authors show that a commonly used streaming method (noisy power method) attains the minimax rate and also provide analysis for another widely used algorithm (Oja’s algorithm).  
- On the technical side, the time-varying nature of the problem leads to additional complications and more involved/novel analysis.  

Weaknesses:
- To me, it appears that this time-varying covariance matrix setting is novel but somewhat unnatural. I believe that the authors should provide better motivation for their problem.  Arguably, the top k eigenvectors of the expectation of the sample covariance is a more natural target than the eigenspace for the last element in the data stream.  Under mild perturbations, one would expect that the mean of this expectation would still converge to some limit and is a meaningful target.  One would also expect that that recovering this eigenspace is much easier.  
- While the spiked covariance matrix is a common setup, minimax rates for this class have rather poor dependence on dimension.  If one solely considers regimes suggested by these bounds, then one of the main benefits of streaming methods, namely low space requirements, is lost.  See Q1 below.

questions: - Some recent work has emerged on PCA where the problem complexity is captured by the effective rank, defined as $r(\Sigma) = tr(\Sigma)/ \lambda_1(\Sigma)$ instead of the dimension.  Do you believe that some of your analysis will be useful for deriving minimax rates in this setup?  Either way, I believe that this line of work should be cited and mentioned briefly.    
- The Gaussian spiked covariance model is a bit more restrictive than other setups considered in the literature (although these papers consider an IID stream).  Could you discuss how much the minimax results depend on the Gaussianity assumption?  It seems that the assumption is not needed in for deriving upper bounds for the streaming algorithms. 

limitations: Yes, the authors are honest about the suboptimality of the rate for Oja's algorithm.  It may also be worthwhile to state that minimax results may be pessimistic regarding the difficulty of the problem when more structure is present.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors analyze the convergence of the noisy power method and Oja’s algorithm in the field of robust streaming PCA.
strengths_and_weaknesses: Strengths
1) The paper is well  organized.
2) This study about the fundamental limit of the minimax error and convergence of the noisy power method and Oja’s algorithm is welcome and well conducted.

Weaknesses: 
1) There are missing references about key works in the field of streaming PCA. Please see:
L Balzano, “On the equivalence of Oja's algorithm and GROUSE”, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, Valencia, Spain, March 2022.
Oja's improvements:
K. Abed-Meraim, S. Attallah, A. Chkeif, Y. Hua, “Orthogonal Oja algorithm", IEEE Signal Processing Letters, Volume 7, no. 5, pages 116-119, 2000.
S. Wu, H. Wai, A. Scaglione, N. Jacklin, “The Power-Oja method for decentralized subspace estimation/tracking”, IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2017, pages 3524-3528, 2017.
PAST/OPAST
B. Yang, “Projection approximation subspace tracking", IEEE Transactions on Signal Processing, Volume 43, pages 95–107, January 1995.
K. Abed-Meraim, A. Chkeif, Y. Hua, “Fast orthonormal PAST algorithm,” IEEE Signal Processing Letters, Volume 7, No. 3, pages60–62, 2000.
PETRELS and its improvements
Y. Chi, R. Calderbank, Y. Eldar, “PETRELS: Parallel subspace estimation and tracking by recursive least squares from partial observations", IEEE Transactions on Signal Processing, Volume 61, No. 23, pages 5947–5959, 2013.
N. Linh-Trung, V. Nguyen, M. Thameri, T. Minh-Chinh, K. Abed-Meraim, "Low-complexity adaptive algorithms for robust subspace tracking", IEEE Journal of Selected Topics in Signal Processing, Volume 12, No. 6, pages 1197-1212, 2018.
L. Thanh, N. Dung, N. Linhtrung, K. Abed Meraim, "Robust Subspace Tracking with Missing Data and Outliers: Novel Algorithm with Convergence Guarantee", IEEE Transactions on Signal Processing, 2021.

2) The authors missed to indicate in one or two sentence that streaming algorithms attempt to deal either or both the presence of outliers or partly observed data.
questions: Can the authors  precise if they tested the algorithms in the presence of outliers or partly observed data?
limitations: The authors have well addressed the limitations of their work.
review_title: null

Meta-review: metareview: The authors consider the streaming principal component analysis problem where the data generation process may be subject to perturbations. The paper provides fundamental limits and analyze the convergence of the noisy power method and Oja's method in this setting. This shows that the former is rate-optimal. The reviewers found the paper to be a solid contribution. Further, the paper has undergone some substantial improvements during the discussion process, which I commend the authors on. I recommend acceptance while strongly encouraging the authors to take any remaining reviewer comments into account while crafting the next version of the manuscript. 
confidence: Certain
Decision: Accept