One for All: Simultaneous Metric and Preference Learning over Multiple Users
Authors: Gregory Canal
Blake Mason
Ramya Korlakai Vinayak
Robert D Nowak
Venue: NeurIPS 2022 Accept (2022)
Keywords: metric learning
preference learning
paired comparisons
recommender system
multiple users

Abstract: This paper investigates simultaneous preference and metric learning from a crowd of respondents. A set of items represented by $d$-dimensional feature vectors and paired comparisons of the form ``item $i$ is preferable to item $j$'' made by each user is given. Our model jointly learns a distance metric that characterizes the crowd's general measure of item similarities along with a latent ideal point for each user reflecting their individual preferences. This model has the flexibility to capture individual preferences, while enjoying a metric learning sample cost that is amortized over the crowd. We first study this problem in a noiseless, continuous response setting (i.e., responses equal to differences of item distances) to understand the fundamental limits of learning. Next, we establish prediction error guarantees for noisy, binary measurements such as may be collected from human respondents, and show how the sample complexity improves when the underlying metric is low-rank. Finally, we establish recovery guarantees under assumptions on the response distribution. We demonstrate the performance of our model on both simulated data and on a dataset of color preference judgements across a large number of users.

One for All: Simultaneous Metric and Preference Learning over Multiple Users
Gregory Canal
Blake Mason Rice University Houston, mmn3@rice.edo
University of Wisconsin-Madison Madison, WI gcanal@wies wwwswwwws......... edu
Ramya Korlakai Vinayak University of Mesconsin-Madiseee
Robert Nowak
University Bicconsin-Madison Madison, WI
Madison, WI ramyaßece. wisc.edu
rdnovak@visc.edi
Abstract
This paper investigates simultaneous preference and metric learning from crowd of respondents. A set of items represented by d-dimensional feature vectors and paired comparisons of the form "item is preferable to item j" made by each user is given. Our model jointly learns a distance metric that characterizes the crowd's general measure of item similarities along with a latent ideal point for each user reflecting their individual preferences. This model has the flexibility to capture individual preferences, while enjoying a metric learning sample cost that is amortized over the crowd. We first study this problem in noiseless, continuous response setting (i.e., responses equal differences item distances) to understand the fundamental limits of learning. Next, we establish prediction error guarantees for noisy, binary measurements such may collected from human respondents, and show how the sample complexity improves when the underlying metric is low- rank. Finally, we establish recovery guarantees under assumptions on the response distribution. We demonstrate the performance of model on both simulated data and on a dataset of color preference judgments across large number of users.
Introduction
In many data-driven recommender systems (e.g., streaming services, online retail), multiple users interact with a set of items (e.g., movies, products) that are common to all users. While each user has their individual preferences items when making preference judgments. This is a reasonable assumption, since collections of users typically have shared perceptions of similarity between items regardless of their individual item preferences [1-3]. In this work we develop and analyze models and algorithms for simultancously learning individual preferences and the common metric by which users make preference judgments.
these items, there may exist shared structure in how users perceive
Specifically, suppose there exists a known, fixed set X' of n items, where each item E 1,..., n is parameterized by feature vector æ; Rdd We model the crowd's preference judgments between items as corresponding to a common Mahalanobis distance metric d (ar, y) = || y where ||||| M = v Mr x and M is a d positive semidefinite matrix to be learned. Measuring distances with dm has the effect of reweighting individual features as well as capturing pairwise interactions between features. To capture individual preferences amongst the items, we associate with each of K users an ideal point us E Rd for E 1,..., such that user k prefers items that are closer to us than those items that are farther away, measured by the common metric d The ideal point
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

model is attractive since it can capture nonlinear notions of preference, and preference rankings are determined simply by sorting item distances to each user point and can therefore be easily generalized to items outside of X' with known embedding features [4-7]. Furthermore, once user's point uy is estimated, in some generative modeling applications can then be used to synthesize an "ideal" item for the user located exactly at Ug. which by definition would be their most preferred item if it existed.
In order to learn the metric and ideal points, we issue series of paired comparison queries to each user in the form "do you prefer item i or item j?" Since such preferences directly correspond to distance rankings in Rdd, these comparisons provide signal from which the user points {ux] 1 k=1 and common metric M can be estimated. The main contribution of this work is series of identifiability prediction. and recovery guarantees to establish the first theoretical analysis of simultaneous preference and metric learning from paired comparisons over multiple users. Our key observation is that by modeling a shared metric between all users rather than learning separate metrics for each user, the sample complexity is reduced from Odd²) paired comparisons per user only ((d), which is the sample cost otherwise required to learn each ideal point; in essence, when amortizing metric and preference learning over multiple users, the metric comes for free. Our specific contributions include:
Nccessary and sufficient conditions on the number of items and paired comparisons required for exact preference and metric estimation over generic items, when noiseless differences of item distances are known exactly. These results characterize the fundamental limits of our problem in an idealized setting, and demonstrate the benefit of amortized learning over multiple users. Furthermore, when specialized to K = our results significantly advance the existing theory of identifiability for single-user simultaneous metric and preference learning [7].
Prediction guarantees when learning from noisy, one-bit paired comparisons (rather than exact distance comparisons). We present prediction error bounds for two convex algorithms that learn full- rank and low-rank metrics respectively, and again illustrate the sample cost benefits of amortization.
Recovery guarantees on the metric and ideal points when learning from noisy, binary labels under assumptions on the response distribution. Furthermore, we empirically validate the recovery performance of our multi-user learning algorithms on both synthetic datasets as well as on real psychometrics data studying individual and collective color preferences and perception.
Summary of related work: Metric and preference learning are both extensively studied problems (see [8] and [9] for surveys of each). A common paradigm in metric learning is that by observing distance comparisons, one can learn a linear [10-12], kernelized [13, 14], or deep metric [15, 16] and use it for downstream tasks such as classification. Similarly, it is common in preference learning to use comparisons to learn a ranking or to identify a most preferred item [5, 6, 17-19]. An important family of these algorithms reduces preference learning to identifying an ideal point for fixed metric 20]. The closest work to ours is [7]. who perform metric and preference learning simultaneously from paired comparisons in the single-user case and propose alternating minimization algorithm that achieves empirical success. However, that work leaves open the question of thcoretical guarantees for the simultancous learning problem, which we address here. A core challenge when establishing such guarantees is that the data are a function of multiple latent parameters (i.e., unknown metric and ideal point(s)) that interact with each other in nonlinear manner, which complicates standard generalization and identifiability arguments. To this end, we introduce new theoretical tools and advance the techniques of [12] who showed theoretical guarantees for learning Mahalanobis metric from triplet queries. We survey additional related work more extensively in Appendix B.
Let [K] := 1.....K K. Unless specified otherwise, ||-|| denotes the E norm when acting vector, and the operator norm induced by the &2 norm when acting on a matrix. Let e, denote the ith standard basis vector, 1 the vector of all ones, 0,, the b matrix of all zeros (or 0 if the dimensions are clear), and I the identity matrix, where the dimensionality is inferred from context. For a symmetric d x d matrix A, let vec* (A) denote the vectorized upper triangular portion of A, which is a D-length vector where D = d(d + 1).2. Let u &, v vec* (uo") denote the unique entries of the Kronecker product between vectors u, V E Rdd and let + denote the Hadamard (or element- product between two matrices.
Notation:
AA,1;,1,22. ... Ai,d
A2., Az.d.... Ad.al"
2 Identifiability from unquantized measurements
In this section, we characterize the fundamental limits on the number of items and paired comparisons per user required to identify M and {u+)k exactly. In order to understand the fundamental
2

---

hardness of this problem, we begin by presenting identifiability guarantees under the idealized case where we receive exact, noiseless difference of distance measurements', before deriving similar results in the case of noisy realizations of the sign of these differences in the following sections.
We formally define our model as follows: if user k responds that they prefer item to item j, then M < || , u M Equivalently by defining
||0;
= a ux I - ||æe uA M - xx Mæ. 2; Mæj 2uk M (a; - xz), (1)
user k prefers item over item j [0) < 0 (otherwise j preferred). In this section, we assume that
(k) is measured exactly, and refer to this mcasurement type as unquantized paired comparison.
I Let my denote the number of unquantized paired comparisons answered by user k and let mr =
Lk=1 my denote the total number of comparisons made across all users.
It is not immediately clear if recovery of both M and {u=) is possible from such measurements, which depend quadratically on the item vectors. particular, one can conceive of pathological examples where these parameters are not identifiable (i.e., there exists no unique solution). For instance, suppose = n, M = al for scalar a > 0, Dz e; for E [n], and for each user
3x 1 for scalar 3x. Then one can show that [ 0 for all i, J, k, and therefore , are unidentifiable from any set of paired comparisons over X.. In what follows, we derive necessary and sufficient conditions on the number and geometry of items, number of mcasurements per user, and interactions between measurements and users in order for the latent parameters to be identifiable.
Note that eq. (1) includes nonlinear interaction between M and uxi however, by defining Us 2M us (which we refer to as user k's "pseudo-ideal point," reflecting the component of uz in the column space of M) eq. (1) becomes linear in M and uy:
(()) %.
2 Mx; 22. Max + (z: (=:-x; "m,=")))mm
M full-rank and the system of equations admits unique solutions for M and {u then ug can be recovered exactly from vg.2 In other words, the non-convex eq. (1) can be solved two stages by first solving linear relaxation (2) in terms of M and Uk. and then solving for uy Note that since M symmetric, we may write x Mæ; = (vec* (2M I @ M), x, &g x,). Defining vec* (2M @ M). from which M can be determined, we have
v vMM)
(k) 3
[1 Øg ac Dy Os 22²)² (æ: x;,"7
(MM
4k
By concatenating all user measurements in single linear system, we can directly show conditions for identifiability of M and (vx )K by characterizing when the system admits unique solution. To do so, we define class of matrices that will encode the item indices in each pair queried to each user: Definition 2.1. A a matrix S is a selection matrix if for every i [a]. there exist distinct indices Ps.0 E [b] such that Sli, p:] = 1, Sli, 9:] -1, and S 0 for j E [b] \ {P:, 9:}.
In Appendix C, characterize several theoretical properties of selection matrices, which will be useful in proving the results that follow.
For each user k, we represent their queried pairs by a my x selection matrix denoted Sy. where each
row selects a pair of items corresponding to its nonzero entries. Letting X == [....... 2n,] Rd X [at] & #1...., In 0s æn. DxR, and ò; E m denote the vector of unquantized measurement values for user k. we can write the entire linear system over all users as a set mrr
equations with D + dK variables to be recovered:
S S 80
S
O Oned d S,XT
Om . Omlid
81
Vi
0 Om
r
where r =
(3)
5K
UK
Sk X T 8
Omg.d
0mx.d
Sk XT
1 We use the term "measurement" interchangeably with "paired comparison." "If M were rank deficient, only the component of u, in the row space of M affects ( this case, there is an equivalence class of user points that accurately model their responses. We then take uy to be the minimum norm solution, ie.. uy 3
'.M. vt. This generalizes Proposition I of [7] for the multiple user case.
3

---

From this linear system, it is clear that v (M) (and hence M) and {ux) k== (and hence ) if M is full-rank) can be recovered exactly if and only if T has full column rank. In the following sections, we present necessary and sufficient conditions for this to occur.
2.1 Necessary conditions for identifiability
To build intuition, note that the metric M has D degrees of freedom and each of the K pseudo-ideal points ty has d degrees of freedom. Hence, there must be at least mer D Kd mcasurements in total (i.e., rows of [' to have any hope of identifying M and {ux )== When amortized over the K users, this corresponds to each user providing at least d D/K measurements average. In general, of these measurements are responsible for identifying each user's own pseudo-ideal point (since es is purely function of user k's responses), while the remaining D/K contribute towards collective set of D measurements needed to identify the common metric. While these D measurements must be linearly independent from each other and from those used to learn the ideal points, a degree of overlap is acceptable in the additional d measurements each user provides, as the Uy 's are independent of one another. We formalize this intuition in the following proposition, where we let ST == [S ........ 5k1' denote the concatenation of all user selection matrices.
Proposition 2.1. If has full column rank, then Σx= m. 2 D + dK and the following must hold:
(a) for all & E [K], rank(S, = d, and therefore rank(Sx) 2 d and my 2 d
(b) E rank(S
x 2 D + dK, and therefore Σ (S,)(S 2 D + dK
(c) (S X
xT) = D+ d, and therefore rank( 2 D D+d, d, rank X x²))= D d, and D + d
E m. + dK exactly, then (a) and (b) are equivalent to m. Z d V k and each user's selection matrix having full row rank. (c) implies that the number of required items n scales as (dd)) in higher dimensional feature spaces, this scaling could present a challenge since it might be difficult in practice to collect such a large number of items for querying. Finally, note that the conditions in Proposition 2.1 are not sufficient for identifiability: in Appendix C.6, we present counterexample where these necessary properties are fulfilled, yet the system is not invertible.
2.2 Sufficient condition for identifiability
Next, present class of pair selection schemes that are sufficient for parameter identifiability and match the item and measurement count lower bounds in Proposition 2.1. This result leverages the idea that as long the the d measurements each user provides to learn their ideal point do not "overlap" with the D measurements collectively provided to learn the metric, then the set of my total measurements is sufficiently rich ensure unique solution. First, define property of certain selection matrices where each pair introduces at least one new item that has not yet been selected:
Definition 2.2. An m x selection matrix S is incremental if for all i E [m)] at least one of the following is true, where pt and q are as defined in Definition 2.1: (a) for all j < i, S P4] 0; (b) for all j < i, STj. qi] 0.
We now present class of invertible measurement schemes that builds on the definition of incremental- ity. For simplicity assume that my = D + dK exactly, which is the lower bound from Proposition 2. 1. Additionally, assume without loss of generality that each m, > d; if instead there existed user k* such that my- = d exactly, one can show under the necessary conditions in Proposition 2.1 that the system would separate into two subproblems where first the metric would need to be learned from the other K- users, and then Vk- is solved for directly from user h* 's measurements.
Proposition 2.2. Let K 2 1, and suppose m. > d E [K], mt D dK, and n 2 D + ++
Suppose that for each k E [K], there exists a d x n selection matrix (()) and my n selection matrix s(²) such that St = [( (z) JT, and that the following are true:
(a) For all ke E [K], (aak(s())) d

---

(b) Defining the D x n selection matrix S(2) as S = (( rr..... y))r) D x D permutation P such that each k E [K].
there exists
(
is incremental
Additionally, suppose each item x, sampled i.i.d. from a distribution px that is absolutely continu- ous with respect to the Lebesgue measure. Then with probability 1, I has full column rank.
Remark 2.3. In Appendix C.6 we construct a pait selection scheme that satisfies conditions in Proposition 2.2 while only using the minimum number of measurements and items, with my = + D/ K (and therefore mr = D + dK) and n = D + + 1. Importantly, this construction confirms that the lower bounds the number of measurements and items in Proposition 2.1 are in fact tight. Since D (df), if = Rd(d) then only my = ((d) measurements are required per user. This scaling demonstrates the benefit of amortzing metric learning across multiple users, since in the single user case D + d = (dd)) measurements would be required.
2.3 Single user case
In the case of a single user (K = 1). it is straightforward to show that the necessary and sufficient
selection conditions in Proposition 2.1 and Proposition 2.2 respectively are equivalent and simplify to the condition that rSnk(S) 2 D + d (where we drop the subscript on S1). In a typical use case, a practitioner unlikely explicitly select pair indices that result in S being full-rank, and instead would select pairs uniformly at random from the set of (2) unique item pairs. By proving a tail bound on the number of random comparisons required for S to be full-rank, we have with high probability that randomly selected pairs are sufficient for metric and preference identifiability in the single user case. We summarize these results the following corollary:
Corollary 2.3.1. When K = 1, if is full column rank then rank(S) > D d. Conversely, for a fixed S satisfying rank(S) 2 D if each æ; is sampled i.i.d. according to distribution px that is absolutely continuous with respect to the Lebesgue measure then I is full column rank with probability 1. If each pair is selected independently and uniformly at random with n Q(D + d) and me (D + d), then if a, is drawn i...d. from px. I has full column rank with high probability.
Importantly, the required item and sample complexity for randomly selected pairs matches the lower bounds in Proposition 2.1 up constant. As we describe in Appendix C.7, we conjecture that similar result holds for the multiuser case (K > 1), which is left to future work.
Prediction and generalization from binary labels
In practice, do not have access exact difference of distance measurements. Instead, paired comparisons are one-bit measurements (given by the user preferring one item over the other) that are sometimes noisy due to inconsistent user behavior from model deviations. In this case, rather than simply solving linear system, we must optimize a loss function that penalizes incorrect response predictions while enforcing the structure of our model. In this section, we apply different set of tools from statistical learning theory to characterize the sample complexity of randomly selected paired comparisons under general noise model, optimized under a general class of loss functions.
We assume that each pair is sampled uniformly with replacement from the set of (?) pairs, and the user l queried each iteration is independently and uniformly sampled from the set of K users.
For a pair = (i.j) given to user k. we observe a (possibly noisy) binary response v/
(k) where
yp (A)) -1 indicates that user k prefers item i to j. and yı (k) indicates that j is preferred. Let = {p, k, (kb) ))=((()))) be an i..d. joint dataset over pairs p. selected users k. and responses yp where (S] denotes the number of such data points. We wish to learn M and vectors {ux k=1 that
K
3 We note these conditions are not exhaustive: in Appendix we construct an example where full column rank, yet the conditions in Proposition 2.2 are not met. A general set of matching necessary and sufficient identifiability conditions on { has remained elusive; towards this end, in Appendix C.7 we describe more comprehensive set of conditions that conjecture sufficient for identifiability.
5

---

predict the responses in S: given convex, L-Lipschitz loss é: R R2n, we wish to solve
1
Σ (k) (11 x; 2:113r 1 - -3,13²))
min M, Mu
S
M
M P S Xp, uull2 S Ao AA E [K], 1813 S Vi,ji
where Xp, Au. ? are hyperparameters and ap defined in eq. (I). The constraint M ensures that M defines metric, the Frobenius and l2 norm constraints prevent overfitting, and the
constraint 8/4) is technical point to avoid pathological cases stemming from coherent æ vectors.
The above optimization is non-convex due to the interaction between the M and u terms. Instead, as in Section 2 we define Uk 2M un and solve the relaxation
min R(M, vv )= s.t. M = 0, ||| Ar, 1l la S Ao AK [K] 16 SyVi,j
M. KK
(S)
Σ 1/ (o. (o. 2. - o% (a: - m;)) where i(M, [vx] = |ا|
The quantity R(M, (2) {==)/=) estimate of the true risk given by
k= is the empirical risk, given dataset S. The empirical risk is an unbiased
R(M, 4Th (m =E (1, (a. Ma, a. Maj + oz (a; (aaa)a;)))) =;)))]
(k) conditioned on the where the expectation is with respect to random draw of p (i. k, and Vp choice of p and k. Let M and kk denote the minimizers of the empirical risk optimization constraints. The
in eq. (5), and let M and {vt minimize the true risk, subject to the
following theorem bounds the excess risk of the empirical optimum R(M, (6g (k))) relative to the optimal true risk R(M", {=))k=))
Theorem 3.1. Suppose [2 for all E [n]]. With probability least 1 8.
256 ()7 + KX2)
R(M {ui] S
log(d? (d2 + d 1))
[S]
(6)
/128L2 + K\E)
81 log(?
log + rl 1)
3|S]
[
Remark 3.2. To put this result in context, suppose || F d that the average squared magnitude of each entry is a constant, in which case we can set XF = d. Similarly, if each entry of v is dimensionless, then l|u 2 x vd and so we can set A, = Vd. We then have that the excess risk where Ô suppresses logarithmic factors, implying sample complexity S
in eq. (6) is Ô (v d2 Kd
of d² + Kd measurements across all users, and therefore an average of d + df K measurements per user. If K M(d), this is equivalent to ((d) measurements per user, which corresponds to the parametric rate required per user in order to estimate their pscudo-ideal point Uk- Similar to the case of unquantized measurements, the (dd2) sample cost of estimating the metric from noisy one-bi bit comparisons has been amortized across all users, demonstrating the benefit of learning multiple user preferences simultaneously when the users share common metric.
3.1 Low-rank modeling
In many settings, the metric M may be low-rank with rank < d [8, 12]. In this case, M only has dr degrees of freedom rather than d degrees as in the full-rank case. Therefore if K = a(d), we intuitively expect the sample cost of learning the metric to be amortized to a cost of O(r)
"We restrict ourselves the where the loss is function of (k) (lu æıllăs l|u. x, 11143)
'Specifically we may choose X, = 2Ar Au, resulting in constraint set containing the solution to (4). To see this, let M" {u be the solution to (4) and define vi = - 2M 2 Then || = 2|| ( uill2 S 2 & 2 M [ | 5 2Ap A...

---

measurements per user. Furthermore, as each Uk. is contained in the r-dimensional column space of M, we also expect a sample complexity (r) to learn each user's pseudo-ideal point. Hence, we expect the amortized sample cost per user to be Q(r) in the low-rank setting, which can be significant improvement over ((d) in the full-rank setting when r <
Algorithnically, ideally one would constrain the M and {6x h== that minimize the empirical risk such that ran and tk E colsp(M)); unfortunately, such constraints not convex. Towards a convex algorithm, note that since 8% E colsp(M), rank([ M, m1 "", "x 1) rank (M) = Thus, it sufficient constrain the rank of M, mn, "., "x We relax this constraint to a convex constraint on the nuclear norm
M on ... ux Ill-, and solve a similar optimization problem to eq. (5):
min R(M, (ux) s.t. M 2 O, IIM M. M.
wK|ll~ Au, 10 Sy Vi,j,, (7)
We again let M and { minimize the true risk R(M, {vr } ) subject to the same con- straints. The following theorem bounds the excess risk over this constraint set:
Theorem 3.3. Suppose | S for all E [n]. With probability least 1 -8
2A3 log(2d+ K)
[(
4 4minnd, n)
|
16
R(M, (6 R(M" ( 52n
S
K
n
VK
SLS. 3|S
8L2yy log (2/5)
log + K) +
[S]
To put this result in context, suppose that the items x; and ideal points us are sampled i.i.d. from (O,, Lt) With this item distribution it is straightforward to show that with high probability, || ( (see [21]). For given
let M Jf LL", where L is d matrix with orthonormal columns sampled uniformly from the Grassmanian. With this choice of scaling we have || = d, so that each element of M is dimensionless on average. Furthermore, recalling that 8; 2M uss with this choice of scaling E|[ 1|3] x and so each entry of 0& on average is dimensionless. To choose setting for X recall that [M, V1, v1,-..... .Uk] has rank r and therefore
|| V1
ux]ll- S [il[[M
U1
UK]lFF S VrluP K max | 122)
kE [K]
which one can show is Ol + dk log K)) with high probability and so we set X O (Vr(d + +d dK (o)gKK)). K)) With these term scalings, we have the following corollary:
Corollary 3.3.1. Let n 2 d, æi, Us ~ NO, 1) and M = / LL', where a x matrix with orthonormal columns. If K ((d2), then in the same setting as Theorem 3.3 with high probability
(v dr + Kr
R(M, (6,) - R(M (
[S]
Remark 3.4. The scaling [S] = Odr Kr) matches our intuition that (dr) collective measurements should be made across all users to account for the dr degrees of freedom in M, in addition to O(r) measurements per user to resolve their own pseudo-ideal point's degrees of freedom. If K = -(d), then each user answering O(r) queries sufficient amortize the cost of Icarning the metric with the same order of measurements per user as is required for their ideal point. Although Corollary 3.3. requires the even stronger condition that K ((d2), we believe this is an artifact of our analysis sis and that K = (dd) should suffice. Even so, a (2(d2) user count scaling might be reasonable in practice since recommender systems typically operate over large populations of users.
'The required user scaling of K Rddd)) implies that Corollary 3.3.1 only recovers amortized scaling of ((r) measurements per user if the user count very large. Nevertheless, the original statement of Theorem 3.3 does apply for any user count, and this case the only drawback to not invoking K = a(d2) that the amortized scaling is larger than Orr + dr/ dr/K) measurements per user. We believe this scaling can in fact be tightened to Orr + dr/ K) measurements per user for all user counts K (not just K - {2dd)), which we leave to future work. See the proof of Corollary 3.3.1 for additional discussion.
7

---

4
Recovery guarantees
The results in the previous section give guarantees on the generalization error of a learned metric and idcal points when predicting pair responses over X, but do not bound the recovery error of the learned parameters M, {+x k with respect to M' and { - Yet, in some settings such as data generated from human responses (22,23) it may be reasonable to assume that true M and {ot ) do exist that generate the observed data (rather than serving only as a model) and that practitioners may wish to estimate and interpret these latent variables, in which case accurate recovery is critical. Unfortunately, for an arbitrary noise model and loss function, recovering M and {v)) k exactly is generally impossible if the model is not identifiable. However, now show that with small amount of additional structure, one can ensure that M and {6x} accurately approximate M and {ot 1/ if a sufficient number of one-bit comparisons are collected.
We assume a model akin to that of [12] for the case of triplet metric learning. Let f: R - [0 be strictly monotonically increasing link function satisfying f(z) 1 f( r); for example, (x) = (1 + + is the logistic link and (xx ((x) is the probit link where (.)) denotes the CDF of standard normal distribution. Defining 6, (M, v) x!! Mæ; =² Mæ, x" (x: mz)
for p (i, we assume that P(r -1) = f (-5p (M', e()) for some M 0 and oi colsp(M') (M)) This naturally reflects the idea that some queries are easier to answer (and thus less noisy) than others. For instance, if 1
(()) < 0 such may occur when æ; very nearly equals user 5(h)) 1
k's ideal point, we may assume that user & almost always prefers item to j and so f(-o (since f is monotonic). Furthermore, we assume that eq. (5) is optimized with the negative log- likelihood loss f induced by f: ( P; M, v) = - lo (Up5 Ux))). In Appendix E, we show that we may lower bound the excess risk of M, {o+) by the squared error between the unquantized mcasurements corresponding to M, {ū&] and M {vūj We then utilize tools from Scction 2 combined with the results in Section 3 to arrive at the following recovery guarantee.
-loogf
Theorem 4.1. Fix a strictly monotonic link function f satisfying f(x) = f( x). Suppose for a given item set X with n D + d + 1 and ||> S 1 V [mi] that the pairs and users in dataset S are sampled independently and uniformly at random, and that user responses are sampled according (M',
to P(y (k) -1) = f (-6'(M .x)) where M {ug satisfy the constraints in (5). Let M,
{ox) 1- be the solution to (5) solved using loss l.. Then with probability at least 1 -6, 6,
K 0111?)
(JIX2, x²1)²
| M |
mmin
K
k=
(A3 + K\2) [
(X + K\a)
2 log(3)
log(d' + d 1)
log(d +d+1) C7
07
3C3|s]
2|S
where Cj min fz) and J := In 1 1,, is the centering matrix. Furthermore, if X is constructed by sampling each item i.i.d. from a distribution px with support on the unit ball that is absolutely continuous with respect to the Lebesgue measure, then with probability 1, miin (J(X) 80 x²I) > O.
Remark 4.2. The key conclusion from this result is that since minn (JX x²) > 0 almost surely,
the recovery error of M. HK with respect to M {wi)K= is upper bounded by a decreasing function of the number of data points, (S]. In other words, the metric and pseudo-ideal points identifiable from one-bit paired comparisons under an assumed response distribution. As discussed in Section 2, the ideal points (ut) k= are then also identifiable as long as M is full-rank. We present an analogous result for the case of a low-rank metric in Appendix E, and leave to future work a study of the scaling of amin (J[x² x²)) with respect and n.
5 Experimental results
Below we analyze the performance of the empirical risk minimizers given in eqs. (5) and (7) on both simulated and real-world data,' with further details deferred to Appendix F.
"ode available https: //tp::///tttttt www.//rrggaaal/mutttsteeeeetette
8

---

Simulated experiments: We first simulate data in a similar setting to Cor. 3.3.1 where 2;, Ug ~ (0 ( and M = Jr LL" where L E Rd is a random orthogonal matrix. To construct the training dataset, quety fixed number of randomly selected pairs per user and evaluate prediction accuracy on a held-out test set, where all responses are generated according to a logistic link function (injecting response noise). We evaluate the prediction accuracy of the Frobenius norm regularized optimization in eq. (5) (referred to as Frobenius metric), designed for full-rank matrix recovery, as well as the nuclear norm regularized optimization in eq. (7) (referred to as Nuclear full), designed for low-rank metrics. We also compare against several ablation methods that modify the constraint sets in (5) and (7): Nuclear metric, where | and || ||2 are constrained; Nuclear split, where || ||. and [| , uk|ll- are constrained; and PSD only, where only M > O is enforced. We also compare against Nuclear full, single, which is equívalent to Nuclear full when applied separately to each user (learning a unique metric and ideal point), where test accuracy is averaged over all users. To compare performance under best-case hyperparameter setting, we lune each method's 's respective constraints using oracle knowledge of M' and {um] Finally, we also evaluate prediction accuracy when the ground-trite parameters are known exactly (i.e., M- M Uk -2M -2. uf). which we call Oracle. This accuracy gives the "best case" performance, and reflects the inherent response noise in the generated data.
To test a low-rank setting, we set d = 10, r = 1, n = 100, and K = 10. We observe that Nuclear full outperforms the baseline methods in terms of test accuracy, and is closely followed by Nuclear split (Fig. la). Interestingly Nuclcar metric, which also enforces a nuclear norm constraint on M, does not perform as well, possibly because it does not encourage the pseudo-ideal points to lie in the same low-rank subspace. While Nuclear metric does demonstrate slightly improved metric recovery (Fig. 1b), Nuclear full and Nuclear split recover higher quality metries for lower query counts (which is the typical operating regime for tuman-in-the--oop systems) and exhibit significantly better ideal point recovery (Fig. 1c), illustrating the importance of proper subspace alignment between the ceuudo-ieaal points. To this end, unlike Nuclear split, Nuclear full explicitly encourages the pseudo-ideal points to align with the column space of M, which may explain its slight advantage. Finally, we note that Nuclear full, single results in the worst prediction accuracy, demonstrating the benefit of a common metric model when the underlying metric is in fact shared. While the single user case is not the focus of this work, in Appendix F.4 we compare the performance of Nuclear full, single against the methods proposed in (7), which only considers the single user case.
Color dataset: We also study the performance of our model on a dataset of pairwise color preferences across multiple respondents (K = 48) [24]. In this setting, each color (n 37) represented as a 3- 3-dimensional vector in CIELAB color space (lightness, red vs. green, blue vs. yellow), which was designed as uniform space for how humans perceive color [25]. Each respondent was asked to order pairs of color by preference, as described in [26, Sec. 3.1]. Since all 2(5)) possible pairs (including each pair reversal) were queried for each respondent, we may simulate random pair sampling exactly.
As there are only d = 3 features, we constrain the Frobenius norm of the metric and optimize eq. (5) using the hinge loss. Varying the number of pairs queried per user, we plot prediction accuracy on held-out test set (Learned M, crowd in Fig. 1d). As CIELAB is designed to be perceptually uniform, we compare against a solution to eq. (5) that fixes M = I and only learns the points (ux) (Identity M in Fig. 1d). This method leads to markedly lower prediction accuracy than simultaneously learning the metric and ideal points; this result suggests that although people's perception of color is uniform in this space, their preferences are not. We also compare against a baseline that solves the same optimization as eq. (5) separately for each individual respondent (learning a unique metric and ideal point per user), with prediction accuracy averaged over all respondents (Learned M, single in Fig. 1d). Although learning individual metrics appears to result in better prediction after many queries, in the low-query regime (< 20 pairs per user) learning a common metric across all users results in slightly improved performance (see Appendix F for zoomed plot). As is small relative to the number of queries given to each user, the success of individual metric learning is not unexpected; however, collecting O(d2) samples per user is generally infeasible for larger d unlike collective metric learning which benefits from crowd amortization. Finally, learning single metric common to all users allows for insights into the crowd's ' general measure of color similarity. As can be seen in Fig. le, the learned metric is dominated by the "lightness" feature indicating that people's 's preferences correspond most strongly to color's 's lightness. As external validation, this is consistent with the findings of Fig. of [24].
9

---

Nedeor fdll
3.0
Naciner fol
0.75
Nuchoar spit
Necloa splt
Naciear
matti
0.70
webr: (M) relattv
2.0
maric
Frbbetus mert:
PS0 orly
arge
0.55
100
250
2000 Numbur of parts 1ost
Nambbr of parts per ioer
Number parts por uset
(a) Test accuracy
(b) Relative metric error
(c) Relative ideal point error
0.66
0.62
Lightness
1.00
0.50
0.58
Red va. Green
00255
0.56
0.00
0.54
Identity
Blue vs. Yollo
-022
Learned M, crowd single
0.52
Lightess
Red us. Green
Blue vo. Yallow
50
100
300
Color preference prediction accuracy
(e) Average M over all color trials
Figure (a-c) Normally distributed items with = 10. r = 1, n = 100 and K = 10. Error bars indicate =1 standard eπrо about the sample mean. For visual clarity, PSD only and Nuclear full, single baselines are omitted from (b-c) due to poor performance. (d) Average color preference prediction accuracy, where error bars indicate 2.5% and 97.5% percentiles. (e) Estimated color preference metric. For (a-e), random train/test splitting was repeated over 30 trials.
6
Discussion
The main contribution of this work is model for multi-user simultancous metric and preference learning consisting of shared metric that captures the crowd's common perceptions between items, as well as user-specific idcal points that characterize individual preferences. Our core result is that when querying paired comparisons over large number of users, the sample cost of metric learning is distributed over the crowd, with the total number of queries per user scaling with the rank of the underlying metric.
One interesting avenue for future work is to study more flexible metric models, since as with any Mahalanobis metrie model may not be the case that linear weightings of quadratic feature combinations provide enough flexibility to adequately model certain preference judgements. While it may be possible generalize the linear metric results studied here more general Hilbert space, another avenue to increase model flexibility is to acquire richer set of features in the item set, which would typically involve increasing the ambient dimension. In this setting, an important consideration would be to ameliorate the requirement that the number of items scales as ldd2²). While this condition necessary for identifiability if the metric is full-rank, we believe that the item count should only need to scale as (ddr) if the metric has rank r < d (see Appendix C.3 for additional discussion). Furthermore, in the case of metric learning from triplet queries is known that only Q(r) items required for metric recovery in the low-rank case [12]. This suggests potential strategy of supplementing paired comparisons with triplet queries to reduce the number of required items.
Acknowledgements and Disclosure of Funding
We thank the reviewers for their feedback, well as Karen Schloss for providing the color preference data used in our experiments and for useful discussions and references about color preference learning. This work was partially supported by AFOSR/AFRL grant FA9550-18-1-011 and ARMY MURI grant W91 W911NF-1151-0079
10

---

References
[1] R. N. Shepard, "The analysis of proximities: Multidimennsioall scaling with an unknown distance function. i." Psychometrika, vol. 27, no. 2. pp. 125-140, 1962.
[2] C. H. Coombs, "A theory of data." 1964.
[3] O. Tamuz. C. Liu, S. Belongie, O. Shamir, and A. T. Kalai, "Adaptively learning the crowd kernel," arXiv preprint arXiv: 1033, 2011.
[4] G. S. Carpenter and K. Nakamoto, "Consumer preference formation and pioneering advantage." Journal of Marketing research, vol. 26, no. 3, pp. 285-298, 1989.
[5] K. G. Jamicson and R. Nowak, "Active ranking using pairwise comparisons," Advances in Neural Information Processing Systems, J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, Eds., vol. 24. Curran Associates, Inc., 2011. [Online]. Available: https: peaeeeeddngssneurissscccpppp
[6] G. Canal, A. Massimino, M. Davenport, and C. Rozell, "Active embedding search via noisy paired comparisons," in Proceedings of the 36th International Conference on Machine Learning, ser. Proceedings of Machine Learnnng Research, K. Chaudhuri and R. Salakbutdinov, Eds., vol. 97. PMLR, 09-15 Jun 2019, pp. 902-911. [Online]. Available: https:/pproceedngs.mi...p mlr. prees/// 19.html
[7] A. Xu and M. Davenport, "Simultaneous preference and metric learning from paired comparisons," in Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., 2020, pp. 454-465, [Online]. Available: https://procedingg.eemm hewp:eeeeeddnnnnnnussss...m coaripssccppaaer/222//iie 056 0S51bC77cca0888337794494933 111119999991111222--22---111 ba23-Paper.pdl
[8] A. Bellet, A. Habrard, and M. Sebban, "Metric learning," Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 9, no. pp. 1-151, 2015.
[9] Fürnkranz and E. Hüllermeier, "Preference learning and ranking by pairwise comparison." in Preference learning. Springer, 2010, pp. 65-82.
[10] K. Q. Weinberger, J. Blitzer, and L. K. Saul, "Distance metric learning for large margin nearest neighbor classification," in Advances in neural information processing systems, 2006, pp- 1473-1480.
[11] J. V. Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon, "Informationn-theorttic metric learning," in Proceedings of the 24th international conference on Machine learning, 2007, pp. 209-216.
[12] B. Mason, L. Jain, and R. Nowak, "Learning low-dimensional metrics," in Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017. [Online]. Available: https:/prooceedings http://poceedings.uui...s...o. www.nnee.uccpaaaanee paarippscc/paper/201//iie Pab.::/0222000000010aa9aaapppppp Paperr.pd
[13] R. Chatpatanasiri, T. Korsrilabutr, P. Tangchanachaianan, and B. Kijsirikul. "A new kemelization framework for mahalanobis distance learning algorithms," Neurocomputing, vol. 73, no. 10-12,
pp. 1570-1579, 2010.
[14] M. Kleindessner and U. von Luxburg, "Kernel functions based on triplet comparisons," arXiv preprint 10Xi::661.084444 2016.
[15] M. Kaya and H. $. Bilge, "Deep metric learning: A survey," Symmetry, vol. 11, no. 9, 1066, 2019.
[16] E. Hoffer and N. Ailon, "Deep metric learning using triplet network," in International workshop on similarity-
pattern recognition. Springer, 2015, pp. 84-92.
[17] K. G. Jamieson and R. D. Nowak, "Low-dimensional embedding using adaptively selected ordinal data," in 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2011, pp. 1077-1084.
[18] K.-S. Jun, L. Jain, B. Mason, and H. Nassif, "Improved confidence bounds for the linear logistic model and applications to bandits," in International Conference on Machine Learning. PMLR, 2021, pp. 5 5148-5157
11

---

[19] G. H. Canal, M. R. O'Shaughnessy, C. J. Rozell, and M. A. Davenport, "Joint estimation of trajectory and dynamics from paired comparisons," 2019 IEEE 8th International Workshop on Computational Advances in Multi- Adaptive Processing (CAMSAP), 2019, pp. 121-125.
[20] A. K. Massimino and M. A. Davenport, "As you like it: Localization via paired comparisons." Journal of Machine Learning Research, vol. 22, no. 186, pp. 1-39, 2021.
[21] K. R. Davidson and S. J. Szarek, "Local operator theory, random matrices and banach spaces," Handbook of the geometry of Banach spaces, vol. 1, no. 317-366, p. 2001.
[22] B. Mason, M. A. Rau, and R. Nowak, "Cognitive task analysis for implicit knowledge about visual representations with similarity learning methods," Cognitive Science, vol. 43, no. 9, p. e12744, 2019. [Online]. Available:
12744
[23] M. A. Rau, B. Mason, and R. Nowak, "How model implicit knowledge? similarity learning methods to assess perceptions of visual representations." International Educational Data Mining Society, 2016.
[24] S. E. Palmer and K. B. Schloss, "An ecological valence theory of human color preference," Proceedings of the National Academy of Sciences, vol. 107, no. 19, pp. 8877-8882, 2010.
[25] K. B. Schloss, L. Lessard, C. Racey, and A. C. Hurlbert, "Modeling color preference using color space metrics," Vision Research, vol. 151, pp. 99-116, 2018.
[26] S. E. Palmer, K. B. Schloss, and J. Sammartino, "Visual aesthetics and human preference," " Annual review of psychology, vol. 64, pp. 77-107, 2013.
[27] B. Kulis el al., "Metric learning: A survey," Foundations and Trends@ in Machine Learning, vol. 5, no. 4, pp. 287-364, 2013.
[28] H.-J Ye, D.-C. Zhan, and Y. Jiang, "Fast generalization rates for distance metrie learning," Machine Learning, vol. 108, no. 2, pp. 267-295, 2019.
[29] F. Liu, X. Huang, Y. Chen, and J. Suykens. "Fast learning in reproducing kernel krein spaces via signed measures," in International Conference Artificial Intelligence and Statistics. PMLR, 2021, pp. 388-396.
[30] M. Huai, H. Xue, C. Miao, L. Yao, L. Su, C. Chen, and A. Zhang, "Deep metric learning: The generalization analysis and an adaptive algorithm." in IJCAI, 2019, pp. 2535-2541
[31] G. Canal, S. Fenu, and C. Rozell, "Active ordinal querying for tuplewise similarity learning," " Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, pp. 3340- Apr. 2020. [Online]. Available: hups://ojs.a http://ojssaai.oor.. www.aiirrr/nideppp//////. wtwp:pp/AAAAaaaiicee/ieews//////
[32] B. Mason, A. Tripathy, and R. Nowak, "Learning nearest neighbor graphs from noisy distance samples," Advances in Neural Information Processing Systems, vol. 32, 2019.
[33] L. Jain, K. G. Jamieson. and R. Nowak, "Finite sample prediction and recovery bounds for ordinal embedding," " in Advances in Neural Information Processing Systems, D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, Eds., vol. 29. Curran Associates, Inc., 2016. [Online]. Available: https://pocccddiss..errri...oo. wwt..nip...cpppppe/0006666 4ela677c54aa66666657444511
12 Paper.pdf
[34] R. A. Bradley and M. E. Terry, "Rank analysis of incomplete block designs: I. the method of paired comparisons," Biometrika, vol. 39, no. 3/4, pp. 324-345, 1952.
[35] P. Rao and L. L. Kupper, "Ties in coiped-comparioon experiments: A generalization of the bradley-terry model," Journal of the American Statistical Association, vol. 62, no. 317, pp. 194-204, 1967.
[36] R. D. Luce, Individual choice behavior: A theoretical analysis. Courier Corporation, 2012.
[37] R. L. Plackett, "The analysis of permutations," " Journal of the Royal Statistical Society: Series C (Applied Statisticss), vol. 24, no. 2, pp. 193-202 202, 1975.
[38] L. L. Thurstone, "A law of comparative judgment." Psychological review, vol. 34, no. 4, p. 273,
1927.
[39] I. Melekhov, J. Kannala, and E. Rahtu, "Siamese network features for image matching," " in 2016 23rd international conference on pattern recognition (ICPR). IEEE, 2016, pp. 378-383,
[40] Y. Freund, R. Iyer, R. E. Schapire, and Y. Singer, "An efficient boosting algorithm for combining preferences," Journal of machine learning research, vol. 4, no. Nov, pp. 933-969, 2003.
12

---

[41] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender, "Learning to rank using gradient descent," in Proceedings of the 22nd international conference on Machine learning, 2005, pp. 89-96.
[42] Z. Zheng, K. Chen, G. Sun, and H. Zha, "A regression framework for learning ranking functions using relative relevance judgments." " in Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval. 2007, pp. 287-294.
[43] D. Chumbalov, L. Maystre, and M. Grossglauser, "Scalable and efficient comparison- based search without features," in Proceedings of the 37th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119. PMLR, 13-18 Jul 2020, pp. 1995-2005. [Online]. Available: https:/prooceeding..lli http://ccnnnnn./pppooo/////////a 19/chumbalov20a.hhl
[44] N. Houlsby, F. Huszar, Z. Ghahramani, and J. Hernández-lobato, "Collaborative gaussian processes for preference learning," Advances in neural information processing systems, vol. 25, 2012.
[45] B. Dubois, "Ideal point versus attribute models of brand preference: A comparison of predictive validity," ACR North American Advances, 1975.
[46] S. Janson, "Tail bounds for sums of geometric and exponential variables." " Statistics & Probability Letters, vol. 135, pp. 1-6, 2018. [Online]. Available: https://www.sccineeeddrctt comp:ssicncaattteepppil111111111
[47] M. Davenport and Romberg, "An overview of low-rank matrix recovery from incomplete observations." IEEE Journal of Selected Topics in Signal Processing, vol. 10, no. 4, pp. 608 622, 2016.
[48] S. Shalev-Shwartz and S. Ben-David, Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
[49] A. Tropp. "An introduction to matrix concentration inequalities," arXiv preprint urXiv:1501.0155 2015.
[50] B. Laurent and P. Massart, "Adaptive estimation of a quadratic functional by model selection," The Annals of Statistics, vol. 28, no. 5, pp. 1302-1338, 2000. [Online]. Available: http://www.jjsoorrrgttbbol2224
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes], in Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes], in Appendix A
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all thcoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (cither in the supplemental material or as a URL)? [Yes], plcase see linked code repository well as Sections 5 and F.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]. please see Section F
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] in Section F
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [Yes] please see linked code repository.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xUDQ2Ul6MB", "reviewer": "Reviewer_u2T5", "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. \n\nThe theoretical result looks quite strong (if they are correct) and the experiments seem to be too weak to be forgivable. \n", "questions": "Please see above. ", "limitations": "Please see the strength & weakness. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My concerns: \n\n(*) Why this particular model? \n\nSpecifically, there are three lines of closely related modeling: \n\n1. 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. \n2. 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). \n3. 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.  \n \nSo 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. \n\n(**) some technical details \nI 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? \n\nThe 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. \n\n(***) Experiments: \nUsing 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? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "wvAujb51lUd", "reviewer": "Reviewer_eLgv", "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.", "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.\n\nI 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.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nSecond, 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. \n\nWhile 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "uyQEZDJRj2J", "reviewer": "Reviewer_BgB1", "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.\nIn the experiment section, this approach is evaluated on synthetic datasets as well as real psychometric data examining individual and collective color preferences.", "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.\n\nWhen 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?\n\n", "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.  ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe 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. \n\nWeaknesses/Concerns:\n\nIn 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.  \n\nExperiments: 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.\n\nline 26: add citation for Mahalanobis distance\n\nline 218-222: sometimes you use $M_*$ and sometimes $M^*$ which I think both are the same term. \n\n\n[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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G6h5NQWXm1g", "reviewer": "Reviewer_KXvU", "summary": "This paper investigates a joint method that can perform preference learning and metric learning.\n", "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.\n- The synthetic dataset experiment results are not consistently better than the baseline settings. More justifications and interpretations of the synthetic experiments would be helpful.\n-  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?\n- 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.\n\n", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The main contribution of this paper is modeling a shared metric between all users rather than learning separate metrics for each user\n- This simple idea makes the sample complexity reduced from O(d2) paired comparisons per user to only O(d),\n\nWeakness:\n - The lack of empirical results and justification.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept