Conformalized matrix completion

Summary

This paper addresses the problem of uncertainty quantification in matrix completion by developing a distribution-free method for predictive inference. The authors propose a novel approach based on the conformal prediction framework, aiming to overcome the limitations imposed by stringent model assumptions such as low-rankness of the underlying matrix and the light-tailed noise. Their method, referred to as Conformalized Matrix Completion (CMC; Algorithm 1), can be combined with any arbitrary matrix completion algorithm to provide confidence intervals for the imputed matrix entries. Here, the “confidence” is measured with respect to the randomness inherent in the measurements of the matrix entries, assuming a randomized probabilistic measurement model. To support their proposed method, the authors also present an intuitive explanation of the method and a theoretical guarantee. They start by giving an intuitive exposition of how the (weighted) exchangeability plays a crucial role in constructing confidence intervals within the conformal prediction framework (Section 3.1). Thereafter, they present Theorem 3.2, which establishes a theoretical guarantee on the average coverage of the confidence intervals, which serves as a key theoretical result of this paper. Additionally, the authors illustrate their analysis by describing two examples of the missingness patterns (i.e., the random observation models) in Section 3.3. Through this illustration, they explicitly evaluate the rate of the expected “weight gap” as expressed in Eq. (6), ultimately demonstrating satisfactory coverage of the constructed confidence intervals. In Section 4, the authors report the results of their numerical simulations. These simulations serve two purposes: (1) comparing the performance of the proposed conformalized method against a model-based baseline (Sections 4.1.1 & 4.2), and (2) investigating the stability of the proposed method when the oracle knowledge of the measurement probability for each entries is not available (Section 4.1.2).

Strengths

One of the primary strengths of this paper lies in its adaptation of the conformal prediction framework to address the challenge of uncertainty quantification in matrix completion. Unlike previous approaches in the literature, this method does not heavily rely on specific model assumptions. This combination of conformal prediction and matrix completion is a significant and original contribution, making the paper stand out in its field. Another notable strength is the careful organization of the paper, which effectively presents the essential components of the study to support the authors' main claims. Section 2 provides a concise overview of the problem setup and evaluation metric. The proposed method is then described in detail, accompanied by an intuitive explanation based on the concept of exchangeability in Section 3.1. The main theoretical result is presented neatly in Section 3.2, and to further enhance the understanding, concrete examples of the missingness patterns are provided in Section 3.3. The paper is further strengthened by the inclusion of numerical study results in Section 4 and a comprehensive discussion in Section 5. As a result, the paper forms a clear and self-contained report of the study, ensuring that the readers can grasp the main ideas and findings with ease. Overall, the adaptation of conformal prediction, the clear organization of the paper, and its ability to convey the study's main contributions effectively are key strengths of this research work.

Weaknesses

While the paper exhibits notable strengths, there are a few areas that could benefit from further improvement and clarification. I have identified three main concerns that warrant attention. Firstly, the authors frequently emphasize that their proposed method is "distribution-free" and does not rely on “any” assumptions about the underlying matrix (e.g., in line 60). However, it is important to explicitly acknowledge that the proposed method and analysis do depend on the probabilistic random observation model, which is necessary for the conformal prediction framework. While this limitation does not appear to be critical, it would be beneficial to provide a careful clarification of the assumptions and limitations to avoid potential confusion. Secondly, although the authors highlight the limitations of existing uncertainty quantification approaches (lines 24 - 30), there is a lack of comparisons between the proposed method and these previous approaches. Consequently, it remains unclear whether and how the proposed method surpasses these existing methods. Including such comparisons would enhance the clarity and strengthen the argument for the superiority of the proposed approach. Additionally, the issue of heavy-tailed noise is briefly mentioned by the authors (lines 32 - 33), who suggest that their method is less sensitive to the noise tail (lines 32-33, lines 257-261). However, this point is not adequately addressed beyond the comparison of the vanilla ALS method to the CMC-ALS method in Figure 1-(c), where the latter seems to be slightly better than the former, but still remains overly conservative; the difference in performance between the ALS and the CMC-ALS does not appear to be substantial (approximately 9x worse vs 6x worse than the oracle). To improve the cohesiveness of the paper, it would be beneficial to either elaborate further on this point or consider removing it if it does not significantly contribute to the main findings. In summary, while the paper possesses strengths, it would benefit from addressing these weaknesses. Clearer clarification of assumptions and limitations, comparative analyses with existing methods, and a more comprehensive discussion of the performance in the presence of heavy-tailed noise would enhance the overall quality and cohesiveness of the paper.

Questions

1. I suggest the authors consider providing a clarification of the assumption on the measurement model, as mentioned in the first point of the "Weakness" section. This clarification would help readers better understand the specific assumptions and limitations of the proposed method. 2. It would be valuable if the authors could compare their method with the approaches mentioned in the second paragraph (lines 24-30) by conducting simulations or other appropriate means. Such comparisons would enable a clearer assessment of how the proposed method outperforms or differs from existing methods. 3. I am curious about the degree to which the proposed CMC method relies on the uncertainty estimate \hat{s}. Many matrix estimation algorithms only provide point estimates for the entries without accompanying uncertainty estimates. In Algorithm 1, when uncertainty estimates are unavailable, the authors set \hat{s}_{ij} = 1 by default (line 3). However, this default choice can be problematic. For instance, consider two scenarios: (1) estimating M and (2) estimating 10M. In scenario 2, the uncertainty should be ten times larger than in scenario 1, but the default choice cannot account for this. It would be beneficial if the authors could address this issue and discuss potential alternatives or adjustments to handle situations where uncertainty estimates are not provided. 4. In Section 3.3, it might be helpful for readers to have either the upper bound for the expected weight gap or the resulting lower bound for average coverage presented as explicit corollaries. 5. The caption of Figure 2 does not provide sufficient information to understand what is being compared. It would be helpful to revise the caption to clearly indicate the elements being compared or provide a brief description of the comparison being made.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

While the authors outline potential future research directions, they do not explicitly address the limitations of their proposed method and approach. It would be beneficial if the authors could include a brief discussion of the technical limitations, such as the assumptions made in their approach. Additionally, providing insights into potential negative impacts when applying the method in real-world applications would further enhance the paper's practical relevance. However, it should be noted that as this paper primarily focuses on theoretical aspects, addressing these limitations in detail may not be deemed critical.

Summary

This paper utilizes conformal inference techniques to address uncertainty quantification in the matrix completion problem. The authors present a novel method for constructing prediction sets for the missing entries estimated by any given matrix completion algorithm, employing a simple data hold-out strategy. The underlying assumption is that the data matrix $M$ is fixed, while randomness arises from the missingness of the matrix entries. Specifically, each index is assumed to have a distinct probability of being observed, independent of the others. The authors demonstrate that when the missingness probabilities are uniform across all entries, the data become exchangeable, allowing for the direct application of standard conformal inference methods. In cases with heterogeneous missing probabilities, the problem becomes more intricate and aligns with the conformal inference under the covariate-shift framework introduced by Tibshirani et al. (2019). To tackle this scenario, the authors propose applying the method developed by Tibshirani et al. (2019) and employ data-driven estimates of the missingness probabilities derived from parametric models. The validity of the proposed method is established through both theoretical arguments leveraging existing results and empirical evaluation using synthetic and real data experiments. These experiments effectively demonstrate the efficacy and practical applicability of the proposed approach.

Strengths

1) This paper is both interesting and original, as it contributes to connection between conformal inference and matrix completion. The authors successfully present a reasonable missingness model and introduce a principled framework to apply weighted split conformal methods. 2) The practical usefulness and potential impact of this paper are noteworthy. Until recently, uncertainty estimation in matrix completion was relatively unexplored, and prior methods were limited due to their heavy reliance on assumptions that often do not hold in practice. Therefore, the assumption-lean approach presented in this paper holds substantial promise and has the potential to significantly impact related fields. 3) The paper is well-written, and the proposed method is clearly and effectively explained.

Weaknesses

1) Technical novelty and originality of theoretical contributions. While this paper seems to rely heavily on the results of Tibshirani et al. (2019) and Barber et al. (2022), the relationship between these works could be explained more clearly. In particular, it would be beneficial to clarify which aspects of the proofs are novel and which can be considered as special instances of prior work. 2) Thoroughness of the numerical experiments. While the proposed method appears promising in theory, the numerical experiments lack convincing evidence. For example, in the four settings depicted in Figure 1, it would be desirable to observe under-coverage in $\texttt{als}$ when the signal-to-noise ratio is low or when the incoherence condition is violated, even with an oracle rank. However, both $\texttt{cmc}$ and $\texttt{als}$ exhibit similar performance when the rank is correctly chosen, with the advantages of $\texttt{cmc}$ primarily stemming from tuning the hypothesized rank. Further investigation and more comprehensive experiments would be useful to establish the illustrate of the proposed method. 3) Realism of real-data experiments. The real data application may not provide significantly more information than a synthetic experiment since the authors begin with the full matrix $M$ and manually sample missing entries using a logistic missingness model. However, it remains unclear whether this logistic model accurately represents practical scenarios. Designing experiments based on more realistic missingness patterns would enhance the informativeness of the results. Additionally, it is expected that the benchmark $\texttt{als}$ would exhibit under-coverage in some heterogeneous settings, but the authors did not compare it to $\texttt{als}$. By neglecting this comparison, the practical relevance of the work is not made as clear as it could be. 4) Limited empirical evaluation. The authors only consider the ``average coverage rate" as defined in Equation (3), which provides a relatively weak coverage guarantee. It would be helpful if the numerical experiments also included appropriate conditional coverage metrics to provide a more comprehensive evaluation.

Questions

1) Usefulness of the one-shot shortcut. The paper introduces a one-shot weighted conformal approach to reduce computational costs. However, it is important to consider potential issues with this relaxation. Firstly, the presence of extremely small probabilities $p_{ij}$ for some test points may lead to excessively large odd ratios $h_{ij}$, resulting in overly conservative predictions that may not be useful for other test points. Secondly, it is not entirely clear why the proposed algorithm without the one-shot relaxation would be prohibitively computationally expensive. Since the weight $w_{ij}$ has a simple form, it should not significantly increase evaluation time in practice. 2) Improvement of technical notation. Some technical details require clarification. For example, in line 157 on page 5, the odd ratio is defined as $(1-p_{ij})/p_{ij}$, which poses a problem when $p_{ij}=0$ for some index $(i,j)$. Additionally, in the Supplement Material, lines 464-467, the variables $\mathbf{Z}$ and $\mathbf{W}$ are not explicitly defined, making it more difficult to verify the proof. 3) Missing citation. In line 233-237, the benchmark prediction sets are mentioned, which are believed to follow from the asymptotic results in Chen et al. (2019). However, the citation for this reference is missing. Including the appropriate citation will provide proper attribution and give readers an opportunity to explore the referenced work. 4) Consideration of alternative methods. There are other matrix completion algorithms available that provide uncertainty quantification, such as matrix completion with Gaussian Copula (Zhao et al, 2020). It would be beneficial for the authors to implement additional benchmarks using these alternative methods to strengthen the validity and robustness of the data experiments.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The main limitations of this paper concern its technical novelty compared to prior work on conformal inference and the depth of its empirical evaluations.

Summary

This paper presents a distribution-free method for constructing prediction intervals in the matrix completion problem, where randomness only arises from the sampling of observed entries. The approach utilizes weighted conformal prediction and establishes a lower bound on the probability of each unobserved entry being included in the prediction interval. The lower bound relies on the estimation error of sampling probabilities, which can be negligible if accurately estimated.

Strengths

* Overall, the paper is clearly written. * The utilization of weighted conformal prediction in the matrix completion problem is quite novel. * The study shows that the resulting prediction interval performs well with well-estimated sampling probabilities.

Weaknesses

* Incorrect estimation of sampling probabilities may significantly degrade the quality of the prediction interval.

Questions

* Are there any experimental results when the sampling probabilities are completely misspecified, e.g., when the heterogeneous missingness is misspecified as uniform sampling? * I'm curious about the impact of the estimated values of $\hat{s_{ij}}$'s. Does misspecification of these values have a substantial negative impact on the results? Are there any empirical findings regarding this? * Is there a rationale for the estimation of theta at Line 237? If there is a reference concerning this, could you provide it? * Since the constructed prediction interval is for M, rather than M*, wouldn't it be appropriate to employ an approach for approximately low-rank matrices in experiments? With an approximately low-rank matrix completion approach, how does the estimation of theta change? * What does Line 277 mean?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Summary

This paper proposes to use conformal prediction for uncertainty quantification of matrix completion. The proposed conformalized matrix completion offers provable predictive coverage regardless of the accuracy of the low-rank model. Empirical results on simulated and real data demonstrate that cmc is robust to model misspecification while matching the performance of existing model-based methods when the model is correct.

Strengths

Strength 1. This paper studies conformal prediction for matric completion with interesting theoretical and algorithmatical findings. 1.1） Through conformal prediction, this paper proposes distribution-free confidence intervals for the completed entries in matrix completion. Benefiting from the use of conformal prediction, the validity is free of any assumption on the underlying matrixs and holds regardless of the choice of estimation algorithms. By proving the (weighted) exchangeabiity of unobserved and observed units when they are (non-uniformly) sampled without replacement from a finite population. 1.2） A provable lower bound for the coverage rate is provided when the sampling mechanism is unknown. 1.3） A one-shot conformalized matrix completion approach is proposed for higher computational efficiency. Strength 2. Experiments on both synthetic and real data suggest the effectivenss of the proposal.

Weaknesses

Weakness 1: One weakness of the proposed uncertainty quantification method for model calibration is that the probability bounds it provides may not be very precise for specific observation models and optimization algorithms. While the method is advantageous in that it is not limited to any particular model or algorithm, there is a possibility that the uncertainty estimates can be too broad for certain scenarios. This potential issue should be acknowledged and addressed in the research. Weakness 2: Another weakness is that the proposed approach does not assume any specific structure on the underlying matrix. As a result, it may not effectively utilize any existing structure in the matrix. To overcome this limitation, the proposed method can be extended to vector completion problems, which could exploit the matrix structure more efficiently. The authors should consider discussing this point and its potential implications. Weakness 3: The paper could benefit from improved clarity in its explanations. It would be more reader-friendly if the authors provided more intuitive explanations for the newly introduced quantities, such as the quantity labeled as (6) in the paper. Enhancing clarity in the presentation of the research would greatly improve its accessibility to readers.

Questions

Please refer to the "Weaknesses".

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The limitations have not been adequately addressed in the main text.

Response to the reply

Thanks for the clarification for my concerns. - My first two questions are inherent to the conformal prediction framework, and are not specific to our specific method or to the specific setting of matrix completion. I think the authors' response is reasonable. - The clarification about $\delta$ makes sense.