Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides some regret bounds for *online* matrix completion: at each round, a recommendation is made for each of the M users and the reward is observed. The reward distribution is unchanged through time (this is therefore a contextual bandit scenario). 
In the simplest approach (Sections 3, 4, B and C), the authors provide an ETC (explore then commit) approach which roughly consists in making uniformly random (see details in “weaknesses”) predictions until sufficient data has been collected, and then sticking to the optimal strategy (recommending the “best” item according to the current estimate of the matrix) for the rest of the time. The estimation procedure is based on nuclear norm regularization. A regret bound of $\widetilde{O}(T^{2/3})$ is provided for this setting.  

In the next approach, the specific case where the ground truth data is rank one is studied via an ingenious algorithm called OCTAL which leverages the fact that the users and items can be clustered based on the sign of their latent representations. Regret bounds are proved for this setting and experiments demonstrate the efficiency of the method 


strength_and_weaknesses: 



**Strengths**:

This is a fantastically interesting and under-researched topic. 
There is a lot of material in the paper and the results are non trivial and impactful 
There is some progress since the last time I reviewed this paper (ICML): some attempt at fixing the issues I mentioned has been made. In particular, I appreciate that the authors now included the actual optimization problem involved in the estimation of the matrix  (line 12, page 5). I also appreciate that the authors are now conscious of the issue of different sampling regimes (see remark 3), and have attempted to adapt the algorithms to take this into account as per my suggestion. The problems with non square matrices has been much better explained and seems correct now. The case of a large number of observations leading to the same entries being sampled many times is at least attempted. 


**Weaknesses**:

The proofs are still very far from clean. Whilst I now agree that all the issues can be fixed “along the lines” sketched in this paper, it has not been done properly yet. In particular, the supplementary is very vague in how it refers to the algorithms is uses, the proof of corollary 1 (which used to be corollary 2 in the previous draft) is still incorrect and largely forgets about all the issues (which are now mentioned in the main paper).  

I am not sure, but I remain somewhat sceptical that the resampling procedure proposed in algorithm 2 is the correct one. It might work, but as far as I am concerned, the closest correct version of the (still incorrect) proof of Lemma 7 would use a different strategy. 











clarity,_quality,_novelty_and_reproducibility: 
**Novelty:**

This is excellent, impactful work. I admit the novelty is very slightly less than I originally thought due to the existence of the paper [2] which the authors cite in the second paragraph of the related works, but I think the difference is still substantial. Indeed, the algorithm is different, so are the assumptions (low rank instead of low non negative rank), and there is the whole rank 1 case which is very novel and interesting both practically and intuitively from the idea of the proof. 

**Clarity, correctness:**


There was an attempt to fix the serious issues I mentioned in my previous review, and I am grateful about this because this is better than what happens in 90 percent of (even more serious) cases. 
However, there are still substantial problems. I am **completely certain** that the **current draft** is **not clear** and goes back and forth between formulations of the algorithm. My answer is based on an attempt to reach the “closest correct version” of the results. If I chose the right one, the authors should fix things as per my suggestions, if I chose the wrong one, the authors should still fix things as per their own interpretation.  

**TO AUTHORS:** please submit a clean version of the paper and appendix. I will **raise my score to 8** if it is done properly. 


**Proof of Corollary 1**: 

 In the corollary statement, it is said that the result applies to “algorithm A that recommends random items to users in each round (according to equation 1)”, there is no mention of the strategy of Algorithm 1 where we first sample according to the Bernouilli sampling of  [1] and then subsample a suitable training set from this. Thus, the result is incorrect in its current form. 
The authors, again, are not even explaining what they are doing and why. The main part of the proof of the result shows that with high probability, the initial Bernouilli sampling procedure has the property that no single user has been sampled more than m times. That is the end of the proof, no context. 
 In the first version of the paper, the authors incorrectly claimed that since this ensures that there are more samples in each line than for the Bernouilli sampling case, performing the algorithm on this dataset will achieve lower error (this does not follow from [1] and it is unclear to what extent it is true and what extra failure probabilities would need to be added). 
I suspect the algorithm referred to in corollary 1 should be the algorithm 1 from the main text, with the second line of “line 5” corrected to say “if not possible then recommend any item $\rho_u(t)$ in $\mathcal{V}$ *OUTSIDE $\Omega$*. Observe…” This is hinted at in the proof of Corollary 1 on lines 11-12.  Note that **Line 9 of the algorithm is wrong** here in this interpretation, as all the samples outside $\Omega$ should be discarded: the meaningful averaging procedure should occur later in algorithm 2, in a way that we still need to determine properly during the rebuttal and revisions, see below. 
At the end of Corollary 1 (proof), it should be concluded that at the end of the procedure, assuming $\mathcal{F}_1$ doesn’t hold, the sample which is chosen by algorithm A (after discarding samples outside $\Omega$) will in fact be exactly the sample obtained through Bernoulli sampling. 
Note there is also  an extra bracket in the main equation in the proof of Corollary 1. 

**Algorithm 2, Lemma 2, Lemma 7 and associated proofs**

There is some confusion about the sampling procedure again and how it samples several entries many times. The proof of the appearance of the factor of $1/\sqrt{s}$ is not nearly clean enough to determine the statement without ambiguity and is basically just hand waving. See page 20 of the supplementary, the paragraph that starts with “in our problem….”:  **It is clearly stated here that each sample is sampled (exactly) $s$ times, which is inconsistent with the sampling procedure in algorithm 2** (in the algorithm as written, $f$ independent Bernouilli sampling steps are performed). As far as I can see, the only way for it to be the case that each entry is sampled exactly s times is if we use the same Bernouilli sample a single time, and then go through Algo 1 a total of s independent times (in which case the final training set consists in s identical copies of the Bernouilli sample. This does work, despite the apparent loss of entropy due to removing some randomness. If one goes another way there are more technicalities to deal with in terms of the coupling and the randomness involved in the number of times each entry was sampled. 

**Lemma 6:** 

In the proof towards the end of page 18 of the supplementary, the authors appear to introduce a condition on $d_1$ and $d_2$ which is not stated in the Lemma statement. If this is needed, it really needs to be reintroduced as an assumption in all relevant results. 
In addition, in the paragraph that starts with “Hence, with probability….” $d_1^{-10}$ should be $d_2^{-3}$. This is significant since $d_2$ is smaller than $d_1$, resulting in a larger failure probability. Fortunately, it is written correctly in the lemma statement. 







==============================References===================


[1] Yuxin Chen, Yuejie Chi, Jiangqing Fan, Cong Ma, Yuling Yan. “Noisy matrix completion: understanding statistical guarantees for convex relaxation via convex optimization”.  SIAM J. Optimization, 2020. 

[2] Rajat Sen, Karthikeyan Shanmugam, Murat Kocaoglu, Alex Dimakis, Sanjay Shakkottai. “Contextual Bandits with latent confounders: an nmf approach”. Artificial Intelligence and Statistics, PMLR 2017. 

[3] Miao Xu, Rong Jin, Zhi-Hua Zhou. Speedup Matrix Completion with Side Information: Application to Multi-Label Learning. 

[4] Rahul Mazumder, Trevor Hastie, Robert Tibshirani. Spectral Regularization Algorithms for Learning Large Incomplete Matrices. JMLR 2010.


summary_of_the_review: It is a **very interesting and impactful paper**. The *proofs are still quite sloppy*, though they improved since the last time I reviewed this paper two conferences ago. 

Fortunately, ICLR is openreview and there is unlimited space for rebuttals and for updated versions of the manuscript, so we will definitely get to the bottom of this. I will raise my score to 8 if the next revision uploaded contains *clean proofs*. 





[**BEGINNING OF POST REBUTTAL UPDATE AND SUMMARY**]


I have previously reviewed this paper. This is a highly technical and complex paper that I am guessing required a lot of work from the authors. The original version had both minor typos and significant technical issues with a lot of vaguely phrased statements in between, around 60 percent of which eventually turned out to be correct and 40 percent of which could be fixed with modifications to the assumptions or calculations.  After discussions and rebuttals, we managed to fix all issues and improve the readability of the proofs and the versions of the manuscript are converging. Therefore I think the current version of the paper is ready for publication and is a very interesting and worthy piece of work, with **substantially above average quality and impact compared to other ICLR accepted papers.** Therefore, I am raising my score from 5 to 8. **I would put a score of 9 if it was possible.**

I have also increased my correctness score from 2 to 4. However, there are some parts of the paper I didn't have time to look at in much detail during this round of review (mainly Appendix D), so I highly encourage the authors to proofread this before the camera-ready version. 

In general, I wish authors would write more details in calculations in other submissions. Otherwise, if there are errors (which is almost unavoidable in such highly technical papers), reviewers will end up (legitimately) questioning the correct parts of the papers as well. 


[**END OF POST REBUTTAL UPDATE AND SUMMARY**]




==========================Miscellaneous extra comments (**Minor**)============================



You might want to cite [4] when talking of the nuclear norm regularisation strategy as this is the usual reference from a practical point of view.

In the paragraph starting with “In the past decade, …” on page 3, the authors mention “inductive matrix completion”, i.e. the problem of matrix completion in the presence of side information.  It is usual to cite at least [3] there. 


Theorem 1 from [1] is correctly cited in page 17 of the supplementary (as “Lemma 4”) but not as “lemma 1” in the main paper, where there is an arbitrary constant c there. I agree with remark 11 that the result can probably be extended this way but that is not the statement of the main theorem (1.3) in that reference as is (though there is an extension in the same paper which is formulated similarly and the “for a constant c” is still lying around in the theorem statement in that reference without being used). In addition, it doesn’t seem that the authors need this strengthened result here  as the most likely place where this could be needed would be the end of the proof of Lemma 6, but there is an independent failure probability there which means it is not necessary. 





==============================References===================


[1] Yuxin Chen, Yuejie Chi, Jiangqing Fan, Cong Ma, Yuling Yan. “Noisy matrix completion: understanding statistical guarantees for convex relaxation via convex optimization”.  SIAM J. Optimization, 2020. 

[2] Rajat Sen, Karthikeyan Shanmugam, Murat Kocaoglu, Alex Dimakis, Sanjay Shakkottai. “Contextual Bandits with latent confounders: an nmf approach”. Artificial Intelligence and Statistics, PMLR 2017. 

[3] Miao Xu, Rong Jin, Zhi-Hua Zhou. Speedup Matrix Completion with Side Information: Application to Multi-Label Learning. 

[4] Rahul Mazumder, Trevor Hastie, Robert Tibshirani. Spectral Regularization Algorithms for Learning Large Incomplete Matrices. JMLR 2010.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the online low-rank matrix completion problem for recommendation systems. An expected regret formulation, as the core analysis goal of the proposed problem, is defined and then minimized via the proposed ETC algorithm and a further OCTAL algorithm for special case of rank-one reward matrices. It provides rigorous regret guarantees for the proposed algorithms and supplementary experiments are conducted to verify its superiority over the baselines.  
strength_and_weaknesses: Strengths: This work proposed a novel and interesting online low-rank matrix completion problem closely extracted from the application of recommendation systems. The analysis of the proposed method is very inspiring and solid, which utilized the very recent advanced fine-grained theoretical analysis technique in the noisy matrix completion field. 

-Weaknesses: This work lacks sufficient experimental comparison with other methods for the recommendation systems application like one or two more offline algorithms besides the baseline UCB. 

clarity,_quality,_novelty_and_reproducibility: -Clarity: Good;
-Quality: Good;
-Novelty: Good;
-Reproducibility: Good.
summary_of_the_review: This work formulates an interesting online low-rank matrix completion problem for recommendation systems, and designs several specific algorithms with theoretical guarantees. This work provides lots of solid analysis and proofs, and its originality and novelty are clear enough.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers online low-rank matrix completion problem, where in each round the algorithm recommends one item per user, for which it gets a noisy reward sampled from a low-rank user-item preference matrix. The authors proposed two algorithms, ETC and OCTAL. ETC obtains a sub-optimal $T^{2/3}$ rate but the OCTAL only works for rank-1 case. 
strength_and_weaknesses: Strength:

1. In spite of a theoretical paper, it is generally easy to follow.

2. The considered online low-rank matrix completion problem is interesting and has received increasing attentions recently. 


Weaknesses:

1. Technical novelty & related work: My major concern is its technical contribution beyond existing literature. There have been a few recent developments in contextual low-rank matrix/tensor bandit. The considered online low-rank matrix completion can be viewed as a contextual low-rank matrix bandit setting where the user side is the context and the item side is the action/arm. However, none of the following recent works was compared in the experiments. In my personal opinion, the technical novelty beyond these references are limited. 

Sen et al. (2017) considered the same contextual low-rank matrix bandit problem. The authors claim that the proposed work is better as the rate of $T$ is improved from $T^{2/3}$ in Sen et al. (2017) to $T^{1/2}$. However, this improvement is only for rank-1 case. The proposed OCTAL only works for rank-1 and the proposed ETC algorithm has the same $T^{2/3}$ as in Sen et al. (2017). 

Lu et al. (2018) used ensemble sampling for the low-rank matrix bandit problem and their framework can be easily adapted to contextual matrix bandit setting. This paper was not mentioned. 

Jun et al. (2019) and Huang et al. (2021) considered bilinear bandits that can also be viewed as contextual low-rank matrix bandits. However, the authors just briefly mentioned these references and claimed that "they cannot be translated to our problem".

Zhou et al. (2020) even considered more general low-rank tensor bandit and contextual low-rank tensor bandit settings. In their contextual low-rank tensor bandit settings, some mode of the tensor is context and is given, while other modes of the tensor are arms to be decided. It is a higher-order generalization of the considered online low-rank matrix completion in this paper. Importantly, Zhou et al. (2020) also used ETC-type algorithm and proved $T^{2/3}$, and proposed ensemble sampling-type algorithm for contextual low-rank tensor bandit. Their algorithm can be directly used for the considered problem in this paper. 

Lu, X., Wen, Z., and Kveton, B. (2018), “Efficient online recommendation via low-rank ensemble sampling,” Proceedings of the 12th ACM Conference on Recommender Systems, 460–464.

Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. In International Conference on Machine Learning, pp. 3163–3172. PMLR, 2019.

Baihe Huang, Kaixuan Huang, Sham Kakade, Jason D Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Optimal gradient-based algorithms for non-concave bandit optimization. Advances in Neural Information Processing Systems, 34:29101–29115, 2021.

Zhou, J., Hao, B., Wen, Z., Zhang, J. and Sun, W.W., 2020. Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making. arXiv e-prints, pp.arXiv-2007.


2. Although the proposed OCTAL achieves the optimal rate $T^{1/2}$ in time horizon, the algorithm only works for rank-1 case. This is a very limited scenario. In the literature, Katariya et al. (2017) considered rank-1 matrix bandit because their work was the first one to consider such-type problem. Given that there have been many new developments in general-rank matrix bandit setting, it would be important to extend the current OCTAL algorithm and its theory to general-rank case.  


3. In practice, how do you estimate rank in the ETC algorithm? In offline matrix completion, we can use cross-validation to tune the rank. However, it is unclear how to tune the rank in online matrix completion case.


4. Related to Question 3, how do you decide other unknown input parameters, e.g., noise \sigma^2, \|P\|_{\infty}, a, c, C, C', C_{\lambda}, in Algorithm 2 and 3?


5. Compared to OCTAL, the proposed ETC has a worse regret bound and a worse numerical performance. What's the motivation of proposing Algorithm 2?


clarity,_quality,_novelty_and_reproducibility: Clarity: OK. Easy to follow

Quality and Novelty: In spite that there are some new results, the overall technical contribution beyond existing literature is limited. 

Reproducibility: Unknown. Code was not provided. 

summary_of_the_review: This paper considers online low-rank matrix completion problem, which can be viewed as a special contextual low-rank matrix bandit. In spite that there are some new results, the technical contribution beyond existing literature is limited. In addition, there are a few unclear parts in the practical implementations.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies online low-rank matrix completion. In the general (low-rank) case they give a regret bound of O(T^{2/3}) (ignoring polylog factors) and in the special case of rank 1, they give O(T^{1/2}) regret (again ignoring poly log factors). The paper is technical and has required significant back and forth between reviewers and authors, but the reviewers are now confident of correctness (to the extent possible in this kind of review process). 
justification_for_why_not_higher_score: Relatively niche interest. Paper technical but not particularly novel.
justification_for_why_not_lower_score: Well above acceptance threshold.
Decision: Accept: poster