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 purpose of this paper is to investigate simultaneous preference and metric learning from a crowd of respondents. For learning the metric and ideal points, the authors ask each user a series of questions in the form “do you prefer item i or item j?” These comparisons can be used to provide a signal from which user's optimal preference latent point uk a common metric M can be estimated. The main contributions of this work are threefold: 1) This paper can provide the sufficient number of items and paired comparisons needed for an exact preference and metric learning over generic items. This is possible when noiseless difference of item distances are known exactly. 2) Instead of exact distance comparisons, if the provided paired comparisons are noisy, this paper provides prediction guarantees when learning from such comparisons. Based on the authors' work, two convex algorithms that learn full-rank and low-rank metrics are presented with prediction error bounds. 3) Authors also provide guaranteed recovery of the ideal point and the metric when learning from noisy binary labels under assumptions about the response distribution.
In the experiment section, this approach is evaluated on synthetic datasets as well as real psychometric data examining individual and collective color preferences.
strengths_and_weaknesses: Strength:

The paper is well-written and easy to read. The paper looks theoretically sound with clearly described assumptions and has provided proofs when needed. In the experiments section, the method has been evaluated on synthetic and real-world data. Authors have provided significant amount of detail about their approach, proofs, additional experiments, broader impact and discussions about the limitations of their approach in the supplementary materials. This makes their paper more clear and easy to understand. 

Weaknesses/Concerns:

In the experiment section, it seems like you don't compare your method to [1] as you mentioned this work is closest to your work. In general, it is kind of hard for me to abstract how significant is the contribution of this paper. I can't what has been improved over other state-of-the-art techniques in the experiment section.  

Experiments: Color Dataset: "We also compare against a baseline that solves the same optimization as eq. (2) separately for each individual respondent" --> please add the baseline name you used in Fig. 1d in the text as well. It is not clear which baseline you describe in the text.

line 26: add citation for Mahalanobis distance

line 218-222: sometimes you use $M_*$ and sometimes $M^*$ which I think both are the same term. 


[1] A. Xu and M. Davenport, “Simultaneous preference and metric learning from paired comparisons,” in Advances in Neural Information Processing Systems, 2020, pp. 454–465.
questions: line 103: "Note that eq. (1) includes a nonlinear interaction between M and uk; however, by defining vk := −2Muk (which we refer to as user k’s “pseudo-ideal point”) eq. (1) becomes linear in M and vk" --> I don't understand this part. Is it possible to rename something and make it convex? or you are solving another problem which is a relaxation of the main problem? If so, please state that.

When you describe your method, you discuss noisy/noiseless settings. In the experiment section (in the main paper) how do you measure noise? or do you account for noisy setting in the experiments?


limitations: I appreciate that the paper has discussed its limitations in the supplementary materials throughly. It would be nice to see some of these discussions in the main paper as well, perhaps in a conclusion section.
review_title: null

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 investigates a joint method that can perform preference learning and metric learning.

strengths_and_weaknesses: Strengths:
- The main contribution of this paper is modeling a shared metric between all users rather than learning separate metrics for each user
- This simple idea makes the sample complexity reduced from O(d2) paired comparisons per user to only O(d),

Weakness:
 - The lack of empirical results and justification.

questions: - Although I wasn't able to fully grasp the detailed derivations and proofs, they seem sufficient to support the model's identifiability, prediction, and recovery claims. However, I hope other reviewers will check their soundness by looking at the full Appendix.
- The synthetic dataset experiment results are not consistently better than the baseline settings. More justifications and interpretations of the synthetic experiments would be helpful.
-  The real dataset experiments were conducted with only one dataset, with constrained setups. Why haven't the authors explored other preference datasets like OpenAI's summarization dataset?
- The lack of empirical support suggests that the title of this work should be framed focusing on the "theoretical analysis" of the identifiability and recovery guarantees of simultaneous preference and metric learning.


limitations: Yes. I really appreciate seeing that the authors have listed out the appropriateness of the assumption and their potential impracticality in real-world settings.
review_title: null

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 studies a preference learning problem, in which each item and user is associated with a latent position, and when a user is close to an item (under the Mahalanobis-norm), the user likes the item more. The problem assumes that the item’s latent positions are known, the users’ latent positions are unknown and the Mahalanobis-norm (the $M$ matrix in the paper) is unknown. The goal is to estimate the unknowns. 

The theoretical result looks quite strong (if they are correct) and the experiments seem to be too weak to be forgivable. 

strengths_and_weaknesses: My concerns: 

(*) Why this particular model? 

Specifically, there are three lines of closely related modeling: 

1. If the preference function is in inner product form, e.g., whether a user likes an item is a function of <x, u>, where x is known and u is unknown, then this is a standard linear/logistic regression. 
2. If both x and u are known, $M$ is unknown (but assumed to be low rank), then it is also extensively studied (an EC result a few years back; I cannot quite find the paper; sorry; nevertheless, the results probably are implied by recent works by Negahban and Wainwright). 
3. If both x and u are unknown, the preference function is distance between latent positions, it is also studied by Katz-Samuels and Scott 2018 and Liu, Wu, Liu, Xia 19.  
 
So the proposed model seems to be a very special case that is not considered in the literature. I dont see strong argument why this specific formulation is needed. I can think of two ways to rebuttal: (i) there are many practical settings, in which this model is more relevant; this probably cannot fly because of the weak experiments, (ii) the new problem is mathematically interesting because it exhibits new structure that 1, 2, and 3 does not have — this may fly. 

(**) some technical details 
I cannot quite parse line 195 to line 221 (around Theorem 3.1). The authors formulated an optimization problem, which is not convex. Then the author proceeds to introduce a new set of variables $v_k = -2 M u_k$ and translates the problem to Eq. 2. (i) It is not completely clear to me this is a relaxation. It is not obvious that a feasible solution to Eq. 2 implies a feasible solution for the original problem (especially enforcing |u_k| < \lambda_u via |v_k| < \lambda_v and |M|_F < lambda_F seems difficult). This kind of M u_k interaction looks very painful so if it would be quite impressive if it is handled correctly. (ii) this change of variable almost resembles the inner product model mentioned above; so what's the difference in terms of techniques and why not directly inner product model? 

The low-rank result appears to be interesting: the standard route would just hope that $M$ is low rank so the regularizer is nuclear norm of $M$. But the authors seem to be saying that for this specific case, doing the nuclear norm for $[M, v_1, …, v_k]$ is more suitable. If Thm 3.1 is correct/meaningful, then Thm 3.3 is believable and probably involves some non-trivial analysis. 

(***) Experiments: 
Using color dataset seems to be quite strange. There are many benchmark dataset available and I feel unsure why the authors do not use them — maybe minimally try the original netflix for a theory result? 

questions: Please see above. 
limitations: Please see the strength & weakness.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Authors propose a preference learning method which ideal points of multiple users and the underlying Mahalanobis metric are jointly learned. In the noiseless setting which the exact differences between distances from ideal points to items are learned, authors provide sufficient and necessary conditions for identifiability. When only noisy binary labels are available, authors provide sample complexity analysis for both full-rank and low-rank metrics. Recovery guarantees of parameters are also provided. There are two empirical results. In the simulation experiments, authors study the statistical efficiency of the proposed method and its variants. In the real data example, authors experiment on pairwise color preference data, which finding matches prior findings from the area of the application.
strengths_and_weaknesses: First of all, the theoretical analysis is of high quality and quite comprehensive. Authors go well beyond the prior analysis of Xu and Davenport (NeurIPS 2010), which only provided identifiability analysis in a much simpler single-user setting. Sufficient conditions of identifiability provides a good intuition on how the sample complexity for estimating the metric $M$ is amortized. Actual sample complexity analysis for noisy settings also match this intuition on the amortization of the cost for estimating $M$. This analysis is also built upon the analysis of preference matrix, which could be of separate interest in future studies.

Second, the paper is very clearly written. Almost authors provide intuitive explanation on every mathematical object they introduce. The analysis naturally progresses from simpler setting to more complex settings, building intuition first and leveraging that intuition for the discussion of higher technical complexity. 

While it's good to know an externally validated finding could be recovered in the real data experiment, the demonstrated practical value of the method still seems limited.
questions: When there is only a single user, the estimation method proposed in this paper is quite different from that of Xu and Davenport (NeurIPS 2020). Would it be of interest to compare the proposed estimation method with Xu and Davenport in the special case of single user? This will allow us to understand the impact of differences between these two estimation strategies.
limitations: In-depth discussion on limitations and societal impact are provided in Appendix A.1 and A.2.

I also appreciate that in the real data experiments, authors validate their findings with published work from the area the data are gathered from. However, I still wonder what prevents authors from running larger-scale experiments from learning-to-rank datasets or recommender system datasets. The proposed method may not achieve the best NDCG, but such an experiment will give practitioners better idea about how applicable the proposed method is to larger-scale problems? While it's good to know an externally validated finding could be recovered in the real data experiment, the demonstrated practical value of the method still seems limited.
review_title: null

Meta-review: metareview: All reviewers felt this paper deserved to be accepted given its strong theoretical contributions and clear presentation. The authors may wish to consider additional experiments given that a number of reviewers found the empirical evaluation to be relatively weak, and are encouraged to follow through on incorporating conclusions and limitations into the main paper body.
confidence: Certain
Decision: Accept