Venue: NeurIPS 2022 Conference

Reviews:

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 paper looks at online matrix-completion -- the goal is to obtain a matrix $X \in \mathbb{R}^{d \times r}$ that minimizes $\|XX^\top - M\| _F^2$ when the elements of the $d \times d$ matrix $M$ are revealed in an online fashion. The paper looks at improving the convergence guarantees of SGD for this task, in terms of the dependence in the condition number $\kappa$ of the ground-truth $M$. 

A previous result of [1] showed a convergence guarantee of $O(\kappa^4 dr\log(d/\epsilon))$ for the regular SGD update. This result shows that multiplying the stochastic gradient with a pre-conditioner -- $P = (XX^\top)^{-1}$ -- gives the aforementioned convergence guarantee without any dependence on $\kappa$. 

The paper shows that this preconditioner can be maintained by making 4 calls to the Sherman-Morris formula and incurs an additional cost of $O(r^2)$ as compared to $O(r)$ in regular SGD. 

The main contribution in the analysis is a descent lemma -- arguing that the coherence of the iterates remains $O(1)$ throughout. 

[1] Chi Jin, Sham M Kakade, and Praneeth Netrapalli. Provable efficient online matrix completion via non-convex stochastic gradient descent. Advances in Neural Information Processing Systems, 29, 2016.

strengths_and_weaknesses: SGD for Online matrix-completion seems to be well-motivated [1] and applying a pre-conditioner in the descent step is a natural idea that also seems to be well-studied for full GD [2,3]. Hence, this idea is natural but the main contribution seems to be in the analysis -- specifically in Lemma 4 -- that argues that the coherence of the iterates decreases at a linear rate, independent of $\kappa$. This analysis seems to be an important contribution to understanding the preconditioned stochastic optimization for RMSE matrix-completion.

WEAKNESS 

As you have mentioned. It seems like, the quality of approximation required for the initial iterate $X_0$ contains a factor of $1/d$ that [1] doesn't. Please see questions section.


[2] Jialun Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for over329
parameterized nonconvex matrix factorization. Advances in Neural Information Processing
330 Systems, 34:5985–5996, 2021.

[3] Tian Tong, Cong Ma, and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation
341 via scaled gradient descent. Journal of Machine Learning Research, 22(150):1–63, 2021.



questions: Since you require $\|X_0X_0^\top - ZZ^\top\|_F^2 < 1/(\kappa \cdot d)$, which is a $1/d$ factor smaller than required for [1], couldn't you make the critique that, for a fair comparison to [1], your result in fact needs an $O(d)$ **factor** more iterations? If that's the case then the complexity of ScaledSGD is $~O(d^2)$, which as pointed out is vacuous. Am I missing something here? 
limitations: Yes.
review_title: null

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: The matrix completion is a classic type of method that tries to recover the ground truth from the observation elements. The stochastic gradient descent (SGD) is one of the solutions to the huge-scale matrix completion in the real world. However, it is suffering from the ill-conditioned ground truth. This work is proposing an SGD-based method that is not affected by the ill-conditioned ground truth. Meanwhile, achieves the per iteration complexity improvement.
strengths_and_weaknesses: Strengths：
The SGD version in this problem is missing, and this work is trying to fill the missing piece.

This work is a nice extension of previous work, including the full-gradient method ScaledGD and PrecGD, the matrix completion SGD results (symmetric PSD case) from Jin [40]. The main contribution of this work could be eliminating the k-dependency in the complexity.

The experiment in the paper is synthetic data, but they offer real data in supplementary. 

It’s a solid improvement on per iteration complexity.

Weaknesses：
It’s not actually a weakness. The main contribution is about eliminating the condition number k in complexity. It reads like the previous work did not consider that at all. However, the previous work ScaledGD did discuss the case that k is independent. It’s fine but probably fairer to mention that to make it clearer.



questions: 
For soundness, it could be better to emphasize whether or not the algorithm is trying to invert the ill-conditioned matrix and the XX^T for complexity discussion.
limitations: No potential negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper propose new online algorithm for matrix completion. When the underlying low-rank matrix is ill-conditioned (has a large condition numer), the authors delivered improved theoretical guarantees for the local convergence of the algorithm.
strengths_and_weaknesses: Strengths: This paper makes solid contribution to online matrix completion when the ground truth is ill-conditioned. The authors present a new algorithm that provably handles ill-conditioned low-rank matrix with theoretical guarantees. Extensive numerical experiments are conducted to illustrate the theory. 

Weakness: my concerns for this paper is mainly about its novelty, as discussed in the first point below.
1. Given that prior literature [1] already showed the fast convergence of SGD for online matrix completion with well-conditioned ground truth, and a series of recent work [2,3,4] showing that scaling provably improves the performance of gradient descent in the presence of ill-conditioned ground truth, it is not surprising to see that by incorporating the scaling scheme with SGD will improve the performance for online matrix completion with ill-conditioned ground truth. What is the technical novelty of this paper? I recommend the authors to highlight their technical contributions of this paper.
2. The theory in this paper only guarantees local convergence. If I am not missing anything, this paper does not discuss how to obtain an initialization that satisfies the conditions in Theorem 2. The most popular initialization scheme is spectral method. Under what conditions does spectral method or other method satisfy the conditions in Theorem 2? How does these conditions depend on the condition number? If we don't have a good initialization scheme when the ground truth is ill-conditioned, then the local convergence result in this paper alone will not be so useful.
3. The claim that 
4. The writing quality of this paper need to be improved, and the paper need to be proof-read. For example, only on page 4 I see the following problems:
(a) the equation (SGD) contains multiple typos; 
(b) the sentence "many iterations of SGD should concentrate about the behavior of full-batch gradient descent" is ungrammatical;
(c) on line 140, "a cubic factor of $\kappa^3$" is actually $\kappa^9$;
(d) on line 144 "initial" -> "initialization" or "initial point";
(e)  on line 145 "with at least XXX probability" -> "with probability at least XXX"

[1] Jin, C., Kakade, S. M., & Netrapalli, P. (2016). Provable efficient online matrix completion via non-convex stochastic gradient descent. Advances in Neural Information Processing Systems, 29.

[2] Tong, T., Ma, C., & Chi, Y. (2021). Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent. J. Mach. Learn. Res., 22, 150-1.

[3] Tong, T., Ma, C., & Chi, Y. (2021). Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number. IEEE Transactions on Signal Processing, 69, 2396-2409.

[4] Tong, T., Ma, C., Prater-Bennette, A., Tripp, E., & Chi, Y. (2022, May). Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Completion. In International Conference on Artificial Intelligence and Statistics (pp. 2607-2617). PMLR.

---------------After rebuttal----------------------

I would like to thank the authors for addressing my comments. I have updated the score accordingly.
questions: The claim on line 156-158 is not correct. Full-batch gradient descent also does not require regularizer or projection to maintain incoherence, which was shown in [5].

[5] Ma, C., Wang, K., Chi, Y., & Chen, Y. (2020). Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution. Foundations of Computational Mathematics, 20(3), 451-632.
limitations: This is a theory paper and I believe there is no potential negative societal impact.
review_title: null

Meta-review: metareview: The SGD version for this matrix completion problem is missing, and this work is trying to fill the missing piece.
The concerns of the reviewers seem to be resolved.
Please try to add the real-data experiments to the final version, maybe instead of the synthetic data.
confidence: Certain
Decision: Accept