We thank the reviewers for their comments. We will improve the presentation in the final version based on these comments. We provide our responses below.$
Assigned_Reviewer_7:
* The only difference between solve() procedures in Theorems 5 and 8 is in the amount of accuracy demanded of the linear system solvers. When we use iterative algorithms (such as SVRG) for linear system solving, this difference translates into running the algorithm for different number of iterations. We will clarify this point in the final version.
* The result in Section 6 does combine our analysis from Sections 3 and 4 with the results of Musco and Musco. We will try to give more details in the final version subject to space limitations.
Assigned_Reviewer_8:
* Numerical analysis paper vs machine learning and experimental results and practical significance: Given that our main contribution is to give a provably faster algorithm for PCA computation, and considering the length of our theoretical analysis, we thought it best to focus on its exposition rather than incorporate experimental results which might require us to cut down on other parts of the paper. Rather, by being published at a machine learning venue, we hope our results will be directly and easily accessible to practitioners who might be able to leverage our run time improvements on relevant problems.
Assigned_Reviewer_9:
* Yes, we must solve the liner system in Theorem 5 to decreasing additive error to obtain eps error in the end. Indeed Corollary 6 specifies the value of c_1 we wish to use, which decreases with every iteration and gets geometric decrease in G(x) in expectation in every iteration. Indeed as noted in the conclusion of Corollary 6, we have E[G(\tilde{x})] \leq 4/25 G(x) which gives us the desired linear convergence to arbitrary accuracy.