Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper develops theoretical results for IMC in a uniform and distribution free setting. It also develops an algorithm for the adjusted regularisation in (11). 
main_review: I think the paper is solid. Below I have a few questions and would like to hear the authors' responses. 
1. From line 43 to 45, they mentioned the sample complexity in a approximate recovery setting. This guarantees has epsilon ^2 dependence. Is all the results mentioned in the paper (Table 1 and 2) has this epsilon dependence? 

2. The formulation (1) (2) (4) and (11) are all penalized optimization problem. Yet theorems and propositions in Section 3 are all constraint version, e.g., min sth subject to some constraints. Even though there is a general relation between the two via the lagrangian multiplier, the multiplier will depend on the data in general rather than a fixed choice. Can the author comment on how to choose the parameter lambda in (1)(2)(4) and (11) in order to achieve meaningful theoretical results? 

3. Most of the theorem requires the loss to be bounded and Lipschitz. But the loss in (1) (2) and (4) are not lipschitz and bounded if we consider the whole space of the matrices M or Z. With the constraint set in theorems and propositions in Section 3, can the author comment on how large the bounded parameter b of the loss l and the lipschitz constant of the loss l will be if we use the square loss? Will the results in section 3 become very bad if we use square loss?

4. What is the weighted version in Table 2? Is it the setting in Section 3.4 and 3.5? Can I understand it as the case that this is also the distribution free setting but we use a different optimization problem to recover the matrix?

5.In line 54 what is O(r^2)? or you mean rd^2? 

6. In the tables, I think it worth mentioning the following results 
Chen, Yudong. "Incoherence-optimal matrix completion." IEEE Transactions on Information Theory 61, no. 5 (2015): 2909-2923.
This paper discusses the MC and IMC setting with a better incoherence dependence. 

Ding, Lijun, and Yudong Chen. "Leave-one-out approach for matrix completion: Primal and dual analysis." IEEE Transactions on Information Theory 66, no. 11 (2020): 7274-7301.
This one has the best sample complexity O(drlog(d)log(r)) for exact matrix completion, which is better than the results in  Table 1. So this is the state-of-art.  

7. Why r = M/(Sd1d2) is considered as the relaxation of rank in line 165?  I think r = M/S in general is the rank. And in line 168, why |M|_*/S<=sqrt(d1d2*r)? You defined rho in line 167 and it is not used.

8. Perhaps in Line 244, you can mention q and kappa are defined in (9)
limitations_and_societal_impact: Some future work is mentioned in the conclusion.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes inductive matrix completion theoretically and conducts numerical experiments to demonstrate the results. 
main_review: 1. In the first paragraph of Section 3, it says "We have one fixed loss function $l$ used through the paper which is both Lipschitz with constant $\ell$ and bounded by $b$". This choice of loss function $l$ seems quite unusual since the commonly used squared loss function does not satisfy this condition clearly. What's more, in Section 4, it says square loss is adopted in all experiments. But square loss does not fit in the theoretical results proved in this paper. There seems no explanations about this in the paper. 

2. Regarding the choice of loss function $l$, can you give some examples of practical and popular choices?

3. There are some typos. For example, on page 2 below equation (3), since $\boldsymbol{x}$ is defined to be the maximum norm of row of $X$, the definition of $\boldsymbol{x}$ should be $\boldsymbol{x}:=\Vert X\Vert_{2,\infty}$ rather than $\boldsymbol{x}:=\Vert X^{\top}\Vert_{2,\infty}$.

limitations_and_societal_impact: This paper focuses on theoretical analysis. It's expected that the paper does not have direct negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies generalisation bounds of Inductive Matrix Completion (IMC), a variant of the classic matrix completion (MC) problem. The main contribution of the paper is improved bounds in the distribution-free setting. Moreover, the authors introduce the (smoothed) adjusted trace-norm minimization strategy, for which they show non-trivial guarantees under arbitrary sampling. These two results generalize similar results previously proved for standard matrix completion to IMC. 
main_review: Strength:
1. The problem studied is fundamental and well-motivated.
2. Interesting theoretical results are proved, and the proof techniques seems quite non-trivial.
3. Empirical results show that the proposed methods outperform previous IMC on various synthetic datasets and real problems.

Weakness:
The notation and technical proofs are quite dense, and the theoretical results are not as clean as those for standard matrix completion/sensing problems. Thus I think potential audience of this paper might be limited.

I am not familiar with the literature of generalization bounds of IMC, so it’s difficult for me to give a precise evaluation on the technical novelty and depth of the proofs. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper improves convergence rates for Inductive Matrix completion in the distribution-free setting. Authors introduced a new version of the IMC objective and experimentally demonstrate that it may performs better than the standard one.
main_review: The paper is well written and many explanations are displayed to readers that are not familiar with the domain. The paper is outside of my area of expertise and I cannot speak confidently about its correctness.

The empirical section seems to be light.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper studies inductive matrix completion with side information. They provide distribution-free bounds that improve upon previous work. New guarantees are also obtained for weighted nuclear norm minimization under arbitrary sampling. The reviewers agree that this paper makes solid contributions and involves interesting techniques. On the other hand, the reviewers also find that the authors should better explain the Lipschitz/boundedness assumptions as well as the novelties for the weighted trace norm. and the clarity of the presentation can be improved.
Decision: Accept (Poster)