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: This paper presents a private and secure matrix completion scheme, where the data gets sent to a server for the task. The communication security is based on homomorphic encryption, and the privacy notion here is $(\varepsilon,\delta)$-differential privacy (DP). The authors work with a relaxed notion of joint DP.

Both theoretical and experimental results are provided for completeness. The focus is on exact recovery in this paper.

Edit: Score updated.
strengths_and_weaknesses: Strengths:
The paper does provide a scheme that seems to satisfy both the communication security and DP requirements. This paper actually focuses on exact recovery, as opposed to sacrificing accuracy in the prior work. The experimental results indicate compatibility with two matrix completion algorithms, NN and AM.

Weaknesses:
1. I wish the writing could be a bit more clear in terms of the cryptographic tools and the preliminaries related to matrix completion problem.
2. The DP side of the scheme doesn't seem very interesting as it just involves adding some Gaussian noise. I don't see any assumptions about the data range (except that the $\ell_2$ norm is bounded by $L$), or how they're being removed. I would have liked to see more of that. This problem might have just required something that simplistic, but I certainly wouldn't highlight its DP property as a huge selling-point for this reason.
questions: I don't necessarily have many questions. Could I know what the assumptions behind the data are? I would like to see what the sensitivity for the added noise is. How big is the norm bound $L$ in practice, and how is it affecting the accuracy of your scheme?

What is the running time of the scheme compared to prior work?
limitations: I couldn't find where the authors discuss the limitations of their work. Could I be pointed to that, please?

I feel that the writing quality could be improved by adding more detailed preliminaries for the main problem and the cryptographic primitives (even in the supplement).

In Equation 13, what is $\mu(U)$?

There seems to be some typo at the end of Line 130.

Lines 114-115: What does $\mathcal{A}-j(D)$ mean? How is this different from running $\mathcal{A}$ on $D_{-j}$?

Lines 102-106: there are both bullets and numbering.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper studies the problem of privacy-preserving data completion in a distributed manner with the homomorphic matrix completion problem and propose a homomorphic encryption-decryption scheme. 
strengths_and_weaknesses: Strengths: The targeted problem is interesting and important. This paper is well organized and easy to follow. Some theoretical results are provided to guarantee recovery and differential privacy.

Weakness:
(1) The centralized server framework in Figure 1(a) does not seem to be a well-known distributed framework in distributed matrix completion. There are too many nodes increasing with the dimension n2. In distributed matrix completion works, say, Mackey, Talwalkar, and Jordan (2015, JMLR), people distribute the matrix into blocks and complete them in parallel. It is worth discussing whether the holomorphic matrix completion can work in that distributed setting.

(2) One key assumption in matrix completion is low-rankness. However, the transformation M+KR in the server is determined by the public key K to guarantee low rankness. In practice, how do we choose the dimension k since we have no idea the true rank r of M?

(3) The transformation g(M)=M+KR is too standard in DP. Is that possible to apply the non-linear transformation to improve privacy?

(4) Could the authors numerically provide the privacy and recovery trade-off in different privacy levels?

(5) Overall, this work follows a simple idea of differential privacy by replacing random noise as the product of public key and random noise. The guarantee of differential privacy and completion is relatively standard in existing works.
questions: (1) It is worth discussing whether the holomorphic matrix completion can work in that distributed setting.

(2) One key assumption in matrix completion is low-rankness. However, the transformation M+KR in the server is determined by the public key K to guarantee low rankness. In practice, how do we choose the dimension k since we have no idea the true rank r of M?

(3) The transformation g(M)=M+KR is too standard in DP. Is that possible to apply the non-linear transformation to improve privacy?

(4) Could the authors numerically provide the privacy and recovery trade-off in different privacy levels?

(5) Overall, this work follows a simple idea of differential privacy by replacing random noise as the product of public key and random noise. The guarantee of differential privacy and completion is relatively standard in existing works.
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 authors derive a novel homomorphic matrix completion algorithm with a proof that the homomorphism property holds provided certain technical conditions are satisfied, including a probabilistic bound on the number of observed entries required.
They also prove that the novel algorithm satisfies differential privacy constraints.
The authors' scheme solves the matrix completion problem on the server with homomorphically encrypted matrix entries while employing a higher rank constraint using any standard matrix completion method. The proof for the homomorphism property relies upon a homomorphic version of the Rudelson selection estimation theorem from [3].

Experimental results on the Netflix and MovieLens datasets indicate that the homomorphic counterparts of nuclear norm (NN) minimization, dubbed HNN and alternating minimization (AM), dubbed HAM, are only slightly worse than the original ones and that the new schemes outperforms the differentially private Frank Wolf (FW) scheme.

strengths_and_weaknesses: Strengths

1. The theoretical guarantees in the papers as summarized above appear to be quite strong.

2. The experimental results as summarized above appear to be quite solid. The observation regarding the significant drop in error for HNN in Sec. 6.3 is also quite interesting.

3. The authors provide geometric intuition for Lemma 1 regarding why $M$ is the exact solution to Eq (3) when a certain condition holds. It appears that Lemma 1 and this geometric interpretation is original and not already present in reference [3] or [6].

4.
Homomorphic encryption is generally supposed to be slow, but the proposed encryption / decryption method using public / private random matrices seems to be quite fast. 

Weaknesses

1. This reviewer found the math in the paper hard to follow and hard to constantly refer to [3] or other references because the paper didn't seem to be self-contained.
The tangent cone mentioned after eq (12) is not defined in the paper and neither is the incoherence parameter used in (13).

2. Both constants $C$ and $c$ are present in Lemma 3 and Corollary 1. It seems to this reviewer that $c = C$. 

3. The parameter $\zeta$ in Theorem 4 doesn't seem to be defined anywhere.

4. Typo: "Rank-decent" should be "Rank-descent" after eq (12).

questions: The parameter $k$ is a design parameter of the algorithm but the authors simply set it to $10$ in all experiments.
Shouldn't it vary with rank $r$ or $p$ ?

limitations: The limitations of the proposed method seems to be the trade-off between accuracy and privacy / number of samples, as discussed in the Conclusion.
review_title: null

Meta-review: metareview: 
This paper concerns privacy-preserving matrix completion in a distributed manner. The communication security is based on homomorphic encryption, while the notion of privacy is defined as the subspace-aware join differential privacy.

The paper received a mixed evaluation from the reviewers, ranging from accept (7) to reject (3), and the reviewers that gave these scores decided to keep them after the rebuttal and the following discussion.

The strengths of the paper mentioned by the reviewers were: 
- Focusing on an interesting and important problem
- Providing an algorithm that guarantees the exact recovery, as opposed to sacrificing accuracy in the prior work
- Solid experimental results

On the other hand, the identified weaknesses were:
- The DP side does not seem very interesting, just involving Gaussian mechanism
- Necessity to know at least an estimate of the rank of M before the homomorphic encryption (a 2-phase solution to that is sketched in the rebuttal)
- The paper not being self-contained
- Some technical issues, which (I believe) were clarified in the feedback

Despite the weaknesses mentioned above, I lean toward the acceptance with my recommendation, although with a limited confidence.
confidence: Less certain
Decision: Accept