Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization
Authors: Suryanarayana Sankagiri
Jalal Etesami
Matthias Grossglauser
Venue: ICML 2025 poster (2025)
Keywords: matrix factorization
nonconvex optimization
recommender systems
learning from comparisons
matrix concentration inequalities
Primary area: optimization->nonconvex
TL;DR: We prove that gradient descent converges to the global minima for the nonconvex problem of learning a low-rank matrix from comparison data

Abstract: In this paper, we consider a recommender system that elicits user feedback through pairwise comparisons instead of ratings. We study the problem of learning personalised preferences from such comparison data via collaborative filtering. Similar to the classical matrix completion setting, we assume that users and items are endowed with low-dimensional latent features. These features give rise to user-item utilities, and the comparison outcomes are governed by a discrete choice model over these utilities. The task of learning these features is then formulated as a maximum likelihood problem over the comparison dataset. Despite the resulting optimization problem being nonconvex, we show that gradient-based methods converge exponentially to the latent features, given a warm start. Importantly, this result holds in a sparse data regime, where each user compares only a few pairs of items. Our main technical contribution is to extend key concentration results commonly used in matrix completion to our model. Simulations reveal that the empirical performance of the method exceeds theoretical predictions, even when some assumptions are relaxed. Our work demonstrates that learning personalised recommendations from comparison data is both computationally and statistically efficient.

Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization
Suryanarayana Sankagiri
Jalal Etesami?
Matthias Grossglauser'
Abstract
learn users' preferences based on the feedback that they provide, e.g., the ratings on the items they have consumed. A classical method of learning from ratings data is ma- trix completion, which is based on the following modeling assumptions. Each user and item is endowed with a low- dimensional feature vector, and their inner product is taken to be the user-item utility. The ratings are assumed to be noisy reflections of this utility, By fitting this model to the available rating data, the system can learn to predict users' preferences over unseen items as well. This approach has been immensely successful in practice (Koren et al., 2009) and also supported by strong theoretical foundations (Ge et al., 2016).
In this paper, we consider a recommender system that elicits user feedback through pairwise com- parisons instead of ratings. We study the problem of learning personalised preferences from such comparison data via collaborative filtering. Simi- lar to the classical matrix completion setting, we assume that users and items are endowed with low-dimensional latent features. These features give rise user-item utilities, and the comparison outcomes are governed by a discrete choice model over these utilities. The task of learning these fea- tures is then formulated as a maximum likelihood problem over the comparison dataset. Despite the resulting optimization problem being nonconvex, we show that gradient-based methods converge exponentially to the latent features, given a warm start. Importantly, this result holds in sparse data regime, where each user compares only a few pairs of items. Our main technical contribution is to extend key concentration results commonly used in matrix completion to our model. Simu- lations reveal that the empirical performance of the method exceeds theoretical predictions, even when some assumptions are relaxed. Our work demonstrates that learning personalised recom- mendations from comparison data is both compu- tationally and statistically efficient.
This work focuses recommender systems that learn from pairwise preference comparisons instead of ratings. One reason to consider such a setting is that comparison data are widely available as implicit feedback-forr instance, when a user clicks on one of four options, it suggests a preference for the selected item over the others. Additionally, we be- lieve explicitly collecting comparison feedback instead of ratings can be beneficial for several reasons: (i) comparisons naturally cancel out user biases in ratings (Shah et al., 2013); (ii) they avoid the discretization issues of rating-basee meth- ods, where responses are typically binary or lie on a 1-5 star scale (Davenport et al., 2014); and (iii) comparing two items is cognitively easier than rating them on an abstract scale (Stewart et al., 2005). fact, the advantages of ordi- nal (comparison) feedback over cardinal (rating) feedback have been empirically demonstrated in small-scale tasks (Shah al., 2016). We ask whether it is possible to learn personalized preferences from such comparison data in a computationally and statistically efficient manner.
1. Introduction
Recommender systems central to modern streaming platforms and digital marketplaces, where they curate per- sonalized selections for each user from the vast set of items these platforms host. Algorithms powering such systems
To answer this question, is natural to consider the fol- lowing comparison- recommender system model that arises by combining the matrix completion assumptions with discrete choice model. Specifically, assume each user u has utility zu, for every item i, where zu, is defined as the inner product of a low-dimensional user feature vector u and item feature vector v. Thus the utility matrix X can be factorized into feature matrices as follows: X = UVT,, Comparisons follow noisy oracle: when presented with two items and j. the user u picks over with probability
'School of Computer and Communication Sciences, EPFL, Switzerland DDeparmment of Computer Science, TU Munich, Ger- many. Correspondence to: Suryanarayana Sankagiri <surya- marayana.sankaginie ept...etnnnniiiee...........
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Nonconvex Matrix Factorization with Sparse Comparison Data
glFa,t Fu.y) for some known link function g(-). Given dataset that is generated from this model with some ground- truth features (U*, V*), one can learn these features by op- timizing the likelihood of the model over the dataset. These learned features can then he used to predict each user's pref- erences over unseen items. The key theoretical question of interest is whether there exists an efficient algorithm that can provably recover the ground-truth features.
convergence rate-are quite conservative. Our work sug- gests that explicitly asking users to compare pairs of items (instead of rating them) can be viable approach to learn- ing user preferences. To the best of our knowledge, such a dataset is not publicly available. Note that prior works using near-identical methods on real datasets, such as Ren- dle et al. (2009) and Park et al. (2015), infer comparisons from other forms of data. We hope our work will motivate practitioners to collect a large comparison dataset similar to the Netflix dataset, on which our method can be tested. An interesting direction of future research is to empirically test whether comparison-base baase feedback leads to better rec- ommendations than rating- -baing feedback, possibly due to lower noise.
There has been some progress towards this question, no- tably by Park et al. (2015) and Negahban et al. (2018). They prove sample complexity guarantees, showing that it is in- deed possible to estimate the ground-truth features, even when each user makes only a few comparisons. However, their analysis rests on a convex problem posed in terms of the entire utility matrix X, and is therefore inefficient to solve. In contrast, the optimization problem posed in terms of the feature matrices (U, V) is computationally much eas- ier to solve, despite being nonconvex. Indeed, the noncon- vex approach has been applied to large-scale, real-world comparison datasets, where the convex approach would be infeasible (Rendle et al., 2009; Park al., 2015). While this approach is computationally faster, the nonconvexity in the problem makes it harder provide theoretical guarantees. Proving recovery guarantees for this nonconvex approach has been highlighted as an important open problem by Ne- gahban et al. (2018). Our work aims to plug this gap in the literature.
2. RELATED WORK
2.1. On Matrix Completion
The matrix completion problem can be stated as follows: recover a low-rank matrix given a small subset of its entries, possibly corrupted by noise. There are two approaches that provide theoretically optimal solutions for this problem. One approach involves posing nuclear norm minimization program, subject to the constraints that some select entries must match the observation. Candès & Recht (2009) was the first to theoretically establish that a low rank matrix can be recovered exactly, given a small, randomly sampled, subset of its entries (without noise). Later work extended these results to the setting with noisy observations (Candes & Plan, 2010; Negahban & Wainwright, 2012).
In this work, we provide the first theoretical recovery guar- antees for the nonconvex learning- -rom---fooooooo comm-mmmaaisonns prob- lem. Our guarantees stem from careful analysis of the loss landscape. We show that within neighborhood of the true solution, the negative log-likelihood function exhibits a strong convexity-like property. Therefore, with a warm start, (projected) gradient descent converges exponentially fast to the global minimum (see Theorem 4. 1). Our proof of this result involves two broad steps. First, we demonstrate that the expected log likelihood function satisfies this desirable structural property. Second, we show that the empirical log likelihood function is close to its expected value, even when the dataset is sparse. Showing the latter requires strong concentration results. Our work introduces new techniques to establish these results, extending the methods developed for the matrix completion problem. Our guarantees are qualitatively similar to those established for matrix comple- tion, notably the work of Zheng& & Lafferty (2016). Further details of our technical contributions are presented after a review of related literature.
An alternate approach is to pose the problem in its matrix factorization form. This is based on the observation that low-rank matrix X admits factorization into two smaller matrices (U, V): X = UVT, One can pose squared-loss loss minimization problem in terms of the factors (U, V) (Mnih & Salakhutdinov, 2007). While this alternate formulation leads to a nonconvex objective function, it is much faster to solve and yields good results on real data (Koren et al., 2009). This empirical success spurred long line of theo- retical research on analyzing this nonconvex optimization problem. The work of Keshavan et al. (2010a) was the first to provide theoretical guarantees for this nonconvex formu- lation. They propose a two-step method. First, they show that performing the singular value decomposition of the par- tially observed matrix leads to a candidate solution close to the ground-truth. Next, using this matrix as starting point, they show that a gradient-descent like method converges to the true solution.
Our simulation results corroborate our theoretical findings. Importantly, they show that some of the assumptions (such as the warm start) needed for our theoretical result are not necessary in practice. They also show that the constants in our theoretical results- sample complexity and the
Other works have built upon this initial result to show slightly stronger theoretical guarantees with improved proof techniques (Chen & Wainwright, 2015; Sun & Luo, 2016; Zheng & Lafferty, 2016). Following the two-step approach
2

---

Nonconvex Matrix Factorization with Sparse Comparison Data
prescribed by Keshavan al. (2010a), all these works focus on proving that there exists basin of attraction around the true solution. Notably, all these papers use key concentra- tion result developed by Candès & Recht (2009) (Theorem 4. This result, in turn, relies on the following assumptions (i) the ground-truth matrix is incoherent (no row or column of the matrix dominates the rest) and (ii) the observed en- tries are chosen uniformly random from all the entries of the matrix. Furthermore, these methods require that the iterates always remain incoherent throughout; to this end, they use a regularizer (Sun & Luo, 2016) or a projection step (Chen& & Wainwright, 2015; Zheng& & Lafferty, 2016).
efficient nonconvex method which is nearly identical to ours. They applied this method to comparison dataset derived from movie ratings (higher rated movie is preferred over lower rated one), getting recommendations of a quality similar to processing ratings directly, thereby establishing the efficacy of this method.
Negahban et al. (2018) studies this problem in much greater detail, providing matrix recovery guarantees with optimal sample complexity. It also analyzes more complex settings such as sampling item pairs in a nonuniform fashion and learning from one-out-of choices. Ultimately, the paper focuses only on the convex formulation, stating that the analysis of the corresponding nonconvex formulation is an important open problem.
Further work on this problem has led to significant relax- ations in the assumptions needed to prove theoretical guaran- tees. Firstly. Ge al. (2016) and Ge et al. (2017) show that all local minima are global in the nonconvex formulation. This implies gradient-based methods are guaranteed to con- verge to global optimum, even without the initialization procedure. Secondly, Ma et al. (2020) shows that gradient descent has implicit regularization and thus can converge to the optimal solution without an explicit regularizer or a projection operation.
2.3. Our Technical Contributions
In this work, we provide a theoretical analysis of the non- convex formulation for the problem of learning low-rank matrix from comparison data. The modeling assumptions make, such as the incoherence of the ground-truth matrix and the uniform sampling of datapoints, are very similar to prior work on matrix factorization. Our proof strategy is also inspired by prior work on this subject; most notably, that of Zheng & Lafferty (2016). In particular, we follow their approach of using a regularizer to translate an asym- metrie matrix factorization problem (X UVT) into a symmetric one (Y ZZT). We also follow their idea of using projected gradient descent to ensure the iterates stay incoherent.
2.2. On Learning From Comparisons
The central problem in learning from comparison data is to estimate the preference order/rank of all the items given dataset. A popular approach to solve this problem is to assume the comparisons arise from probabilistic choice model, such as the Bradley-Terry-Luce choice model. Theo- retical guarantees for learning the parameters of this model have been established in the literature (Negahban et al., 2012; Maystre & Grossglauser, 2015; Shah et al., 2016). In addition to the offline setting, the corresponding active learn- ing problem has also been well-studied, especially in the framework of dueling bandits (Bengs et al., 2021). In partic- ular, the contextual dueling bandit model is quite similar to our model; however, with the 'collaborative filtering' aspect missing, the basic estimation problem there reduces to that of logistic regression (Saha, 2021; Bengs et al., 2022).
The key difference between our work and prior work is the method used to develop the necessary concentration in- equalities. Most of the papers analyzing matrix completion build upon some fundamental results from Candès & Recht (2009) and Keshavan al. do not apply to our problem, because the structure of the sampling matrix is different. To elaborate, in matrix com- pletion, a data point consists of a single user and a single item, while here, a datapoint consists of a single user and an item-pair. This seemingly minor difference makes us lose the interpretation of the set of samples acting like a projection operator (Candès & Recht, 2009), the samples being edges of a bipartite graph (Keshavan et al., 2010a). In this work, we derive the necessary concentration results by using the matrix Bernstein incquality (Tropp. 2015) as the main tool. Further details are given in Section 5.
these results
The problem of learning low-rank user-item score matrix from comparison data was first formulated by Rendle al. (2009). This work applied a model and algorithm very similar to ours to a comparison dataset derived from implicit user feedback such as views, clicks, and purchases. Rendle et al. (2009) demonstrated that such data is better treated as ordinal information (a preference of the viewed item over the rest) instead of cardinal information (a positive rating of the viewed item).
We make two major simplifying assumptions in this work. First, we assume that our comparisons are noiseless. That is, instead of observing binary preference outcome, we observe the expected value of this outcome. Extending our analysis to the more realistic setting of noisy, binary com-
Park et al. (2015) was the first work to provide theoretical guarantees for this problem, albeit for convex version. This work also noted the similarity of this problem to the matrix completion setting, prompting them to also develop a more
3

---

Nonconvex Matrix Factorization with Sparse Comparison Data
parisons is important direction of future work.' Second, assume we are given an initial point that is suitably close to the ground truth solution. In the matrix completion litera- ture, such an initial solution can be obtained by performing a singular value decomposition on the partially observed matrix, as shown by (Keshavan et al., 2010a). However, this initialization method does not work here. Our simulations in Section 6 suggest that this warm start may not be a necessity. Proving convergence from a random point, as done by (Ge et al., 2016), remains an open problem.
distinct items. The item pair (i.j) is sampled independently from u. The triplets for different datapoints are sampled independently of each other.
In this work, we assume that comparisons are noiseless, Le., instead of a binary outcome, we observe the expected value of the comparison outcome w (that is, g( - =.,,)) )). Although this assumption not a reflection of practice, we make this assumption for the simplicity of exposition. By making this assumption, we can show that with sufficient data, we can estimate the ground-truth matrix to arbitrary precision. The binary outcome setting can be viewed as a noisy setting, as any random variable w can be expressed as the sum of its mean E[w] and some mean- zero noise. We believe it possible to extend our results to the noisy case, except that the recovery guarantees will contain a residual estimation error due to the noise.
3. Model
3.1. The Data Generation Process
Let there be a fixed set of users and items. Let n1 denote the number of users and ri the number of items. We assume that each user u has a certain utility zt.; for every item i. Each user and each item i has r-dimensional feature vector. Further, we assume that the score matrix X E RT X has rank r. Although our analysis holds for any rank r S min R1, 72,, the results are interesting when the matrix is low rank, ie., the r is much smaller than nı and n2.. We call X* the ground-truth utility matrix.
3.2. Notation
We now introduce some additional notation that we will use throughout the rest of this paper. This notation is useful not only to succinctly represent the loss function (see Section 3.3), but also to argue about the desired concentration results (see Section 5).
When user u is asked choose which option they prefer between two items i and j. we assume the user makes choice by comparing their utilities. To be precise, let w = 1 denote the event that the user picks i over j and w = 0 the complementary event. We assume
In Section 3.1, we assumed that the score matrix X* E R xm2 has rank r. This implies that it admits the follow- ing rank-r SVD: X UV Here, U xr and V E R are orthonormal matrices (satisfying UTU = VTTV+ = T,), and Σ* E Rtxr is diagonal matrix with entries of 2 2 o > O.
P(w- = 1) = g( sugg)
(1)
Let = n1 + n2. Define Z E R=xr and Y E Raxx as follows:
where g R + 1) is called the link function. This model captures the intuition that the user certain in their choices among items that differ significantly in their utility, but is more ambiguous when choosing between similar utility ittms. A special case is the classical Plackett-Luce choice model, where the link function is the sigmoid function: g(z) = 1/(1 + exp(-x)). In general, the link function is a smooth, strictly increasing function and is symmetric around zero in the following sense: 9(-x)= 1 - g(x).
U²
2"
1x1/2
(2)
V
UUSUU X-I
X
Y = 1T
(3)
We can interpret U- as the matrix of user feature vectors, with row corresponding to user u. Similarly, V' can be viewed the matrix of item feature vectors Both user and item features are r-dimensional vectors. Note that X* = (U==="/))("">>>>/)") Thus, the user-item utility x"u, i can be viewed as the inner product of the corresponding user and item feature vectors.
We assume we are given dataset D where each data point represents a comparison made by user between two items. The size of the dataset, i.e., the number of data points, is represented by m. We index the dataset by k. Each data point D& is of the form ((4;,,,), w) and is sampled ran- domly as follows. The user index u is chosen uniformly at random from [m.] The pair of item indices (i. is chosen uniformly at random from the set of n22 - 1) pairs of
Given the relation between matrices X", Y". and Z", esti- mating the ground-trutt utility matrix X is equivalent to estimating Z" (barring the symmetries discussed in Section 3.5). The major advantage of this reduction is that it reduces the number of parameters from 72 (in X*) to (ni + n2)r (in Z*). This significant reduction in parameters (when r is small) leads to corresponding gains in computational efficiency. Thus, from here on, the goal of the learning
Indeed, in the matrix completion literature as well, the noise- less case has been addressed first and the noisy case in a follow up work (e.g.. Candès & Recht (2009) followed by Candes & Plan (2010), Keshavan et al. (2010a) followed by Keshavan et al. (2010b)).
4

---

Nonconvex Matrix Factorization with Sparse Comparison Data
problem is to estimate Z' Before we present the precise learning problem in subsequent subsections, we introduce some more notation that will make the presentation concise.
p111 -)--u Therefore, the negative log-likelihood of this observation is -w log(p) (1 w) log(1 p). Next, consider datapoint ((u; i, j),, w) with the corresponding sampling matrix A. The negative log-likelihood of this observation with parameters 7 is
Let e1, e2.... Cn, denote unit vectors in R" and let é1, (,,....,,,, Cn2 denote unit vectors in RT= Let ((C, D)) = Eng J denote the matrix inner product between two matrices of the same size. Therefore:
- log (e( (1,, ))) (1 w) log(1
Then, for the entire dataset, the (normalized) negative log likelihood is given by:
(en(és -
(4)
For any triplet (u; i, j), define the corresponding sampling matrix A E RR to be:
1 m
((2)
we log(o( 27" ())
m
k=
A = 0
ea Cā - 3
(()-))²²
(5)
(1
wk log - g A(x 2 zz"))))
(8)
The gradient of L(Z) is
In the equation above, O denotes matrices with all entries zero of the appropriate size. With this notation, for any data point ((u; i, j), we have:
VL(Z) = - m
Σ
hx(AA + A/) where
(9)
(A,Y*) ((A,, y = z., - -uus
(6)
h1 - g' (g(Ex) wK)
g(zx)(1 o(=x)) 26 - (AN zz n)
P(w (1ci,)))
P(w 1 1| ((A,,))))
Here, VL(Z) is a matrix of the same size as Z while hy and 2 are scalars. Finally, note that with the noiseless assumption, we can substitute wi by a (AA, n* (*)))))
Let Aş denote the sampling matrix corresponding to the dat- apoint DR. By our modeling assumptions above, A1, A2; --- are i..d. random matrices of the same form as (5), with the index being chosen uniformly at random from [mi]. and the indices (i being chosen uniformly at random from
3.4. Important Parameters
[ma] (with the condition + j).
Condition Number Let oi. oi.... denote the singular values of X*. Denote the ratio /a called the condition number of the data, by k. Also note k is also the condi- tion number of Z", because the singular values of 2" are 220 / .oo.....vv ... 22.
Lastly, for any matrix E Raxx, define
m (A + Y
D(Y)
m
Incoherence For any matrix Z, let || denote the maximum of the & norm of its rows and let || || denote the Frobenius norm of Z. Define the incoherence parameter of the ground-truth -ruth matrix as
We overload this notation to highlight the fact that the oper- ator D.-) captures the collective action of all the sampling matrices of the dataset D. We shall encounter such terms repeatedly in our analysis. Observe that D(Y) is the empir- ical mean of i.i.d. random terms. Thus, it is reasonable to expect that D(Y) x [[D( if the number of datapoints m is sufficiently large. Our analysis rests on proving such concentration results; see Section 5 for more details.
# ف n 12. 2,
| 112)
(10)
In principle, j can take values from 1 to n. However, the sample complexity worsens with μl, as the concentration bounds weaken with p.
3.3. The Loss Function
Link Function Bounds Let T denote the interval 24 24u([[2z((()mm)) Let & and E be lower and upper bounds for the following expression:
Recall, from the previous section, that our goal is to estimate the matrix Z We do so by maximizing the likelihood as a function of matrices Z E Raxr over the dataset D. other words, we formulate a loss function in terms of the negative log likelihood, and minimize this function using a gradient descent-like method. This section presents the expressions for the log likelihood and its gradient, using the notation developed in the previous section.
g'(x)g((v)
c 2
min
(11)
NEL.EE g(x) g(x))
g'x))'(yy)
E max wET (( -
(12)
By the assumptions on g(-) stated above, E is strictly positive and is finite. These terms are used to bound the term hy in (9) above.
Given a binary outcome w. the likelihood of the out- come under a Bernoulli distribution with parameter p is
5

---

Nonconvex Matrix Factorization with Sparse Comparison Data
3.5. Symmetries in the Problem
Shift Invariance Under our model, all comparisons in- volve computing the difference between the utilities of two items. Therefore, adding constant vector to each item's s feature vector does not affect the scores. Mathematically, this can be seen as follows. Let V = V + 1 where v E IR' and E _ is the vector of all ones. Let Le, Y and 2 denote the corresponding quantities derived from (U** , V*). Then for any triplet iu; and the correspond- ing sampling matrix A, we have ((en(e: ",)",') (ea(é; - =2," ,x"), which implies ((A, Y = ((A.Y))) Because of this invariance, we assume, without loss of gen- erality, that v 0. In words, we assume that the item features of all matrices in & sum to zero
The generative model, and consequently the log likelihood function, is invariant to certain transformations in the param- eters. We explore these symmetries and their consequences in this section.
Scale Invariance For any score matrix X, the mapping to Z = (U,V) V) is not unique. Indeed, for any invertible r X matrix P. the matrix Z' = (UPI, VP-1) is indistin- guishable from (U, V), as they both lead to the same score matrix X and hence the same likelihood. However, we can distinguish 'imbalanced' matrices from 'balanced' ones by by adding a regularizer term ||U [ to the loss function. Minimizing this regularizer while keeping the log- logllikeldhood constant leads to a pair of feature matrices that are balanced in the norms. In more compact terms, the regularizer can be written as follows:
The shift invariance also manifests itself in our objective function ZZ)). is important to factor out the shift invari- ance in order to establish a strong-convexity like property (i.e., a curvature) for C(Z). Therefore, we restrict our atten- tion to the following subspace:
R(Z) - 7 DZ pi A
n1 0
0 [na]]
(13)
H {2 E RaXt Z (U. = =0.
(19)
For any Z= VU,V), we shall work with the projection of Z onto H. denoted by (+) This projection is given by (U, JV), where J 1 mn 11 111//11)) /(2)). Finally, note that by the assumption stated before, 1b C H.
Note that the ground-truth matrix Z" satisfies R(Z*) = O. Combining the regularizer with the negative log likelihood, the objective function becomes:
f(z) ((Z) (A)4)R(Z),
(14)
4. Algorithm and Result
where A is a positive constant. In this work, we set = ET/4; however, in practice, it should be treated as a hyperparameter. In summary, adding the regularizer R(Z) factors out the scale-invariance of the problem.
A naive approach to minimize the loss function (14) is to simply apply the gradient descent method until one is suffi- ciently close to convergence. Indeed, in Section 6, we show this works well in practice. However, for proving theoreti- cal guarantces, we need to use projected gradient descent. Notably, the projection step involves two successive projec- tions, first onto a of 'incoherent matrices' C and then onto H (defined in (19)). The set C is defined follows:
Rotational Invariance Beyond the scale invariance, the problem at hand also exhibits rotational invariance. Let I be any orthogonal matrix in dimensions, i.e., R E RR such that R." R R = T. The matrix ZR- (UR, VR) give rise to the same scores Z = VU. Thus, one can identify the ground-truth features only up to an orthogonal transformation. Denote this equivalence class of the ground- truth feature matrices by Φb
C fafze Z E Raxr,
12
I
1 31 72
4
1 lpj. (20)
Thus, C contains matrices that are 'nearly as incoherent
as Z (if | F ~ || For any Z E Raxr, the projection of Z onto C. Pc(Z). is a matrix in Raxr obtained
① a 1" 2" Z" R for some orthonormal R}. (15)
by clipping the rows of Z to 3 = (4/3) V (w/n) | F
This equivalence class of solutions naturally gives rise to a new distance metric A that measures how close candidate solution Z is to 4 Define
Z Zg 11,)112)
if 1 1l2 S B otherwise
Vj E [m), Po(Z), =
R 2) A arg
min R.R. R= RRT T,
2z -2-z"Rll R'l,,,,
(16)
The rationale for the projections is the following. One, the (17) objective function displays strong-convexity like property only within the region of incoherent matrices. The projec- (18) tion operation Pe ensures that we stay in this region, which is crucial for proving the theoretical results. The second projection, Pxx factors out the shift invariance in the loss
(Z) A arg min
7 7- F = Z' R(),
A( à Z - (Z).
We measure the quality of solution by ||)
6

---

Nonconvex Matrix Factorization with Sparse Comparison Data
function. This is essential in order establish strong con- vexity; otherwise, there is no curvature in the direction of invariance. Here, there is caveat: this second projection may push the iterates out of the set C. However, we show (in Lemma A.3) that the iterates remain incoherent enough, i.e. they remain in the set C, where
((T/pr)))²) Although the constants in the sample com- plexity result and convergence rate quite large in the statement of Theorem 4.1, our experimental results in Sec- tion 6 show that in practice, these constants are moderate. The following section gives a sketch of the proof of Theorem 4.1. The full proof is provided in the appendix.
C { 7 Rnx 1 S V12p/n ( p] (21)
5. Proof Outline
Theorem 4.1 is nearly identical to the convergence guaran- tees of gradient descent for a strongly convex and smooth function, notwithstanding the projection step and the sym- metries. Lemmas 5.1 and 5.2 establish properties akin to strong-convexity and smoothness respectively. Note that we have dropped the dependence on Z for brevity; e.g., we denote V (z(Z) by V..
Algorithm 1 Projected Gradient Descent
Input: Objective function f. initial solution z |R"r
stepsize 1)
7 < PH (Pe (79))
repeat
Zi+1 t PM (Pe (Z' 1(V((z)))
Lemma 5.1, Suppose the number of samples m is at least 107 (μrx/T)² n log (2n/5), for some E (0, Then, with probability at least 1 8, Z H HLBB(T550) ne,
1 ++t+]
until convergence
Output: z
S IAI 4
EY 8
(Vf.A) 2
Our main theorem states that in the noiseless setting, given a sufficiently large dataset and a warm start, Algorithm I converges exponentially fast to a solution equivalent to the ground-trute matrix. For the sake of conciseness, we introduce the following constants:
Lemma 5.2. Suppose the number of samples m is at least
2n log( (n//)) for some 6 E (0, 1). Then, with probability
at least 1 - 6, 4 Z E B())
7 ف 2/(m1(122 1)), T E/E a a EYo,
| s 10 (oT 1| + (57)² oi "
Let B(s) = (Z: || S {o denote a 'ball' around the true solution. With this notation in place, we state the main result of this paper.
The lemmas are easy to interpret as strong convexity and smoothness conditions if we ignore the terms - D& (which stem from the regularizer).
Theorem 4.1. Suppose the following conditions hold:
At a high level, the method for proving both these lemmas is similar. First, the expressions to be bounded, namely [V A} and [f are written out as the sum and prod- uct of D(Y) terms (recall the definition of D(Y) from (7)). Second, demonstrate that these terms, which capture empirical mean of i.idd. random variables, are close to their statistical mean. Specifically, we show that with high probability, D(Y) RS E[D(Y)), uniformly for all Y in some appropriate set. Finally, we put these results together with the appropriate parameters ensure that the bounds pre- sented in Lemmas 5.1 and 5.2 hold. The following sections flesh out more details.
The dataset D consists of m i.i.d. samples generated according to the model presented in Section 3.1.
The number of samples m is at least 107 (μrx/T)²² n log (8n/5) ( for some d E (0, 1).
The initial point - lies in B(T/50).
The stepsize n in Algorithm I satisfies na < 2.5 10 (r/urz/)
Then, with probability at least 8, the iterates Z:, 22 ..... of Algorithm satisfy;
Showing Strong Convexity The proof of Lemma 5.1 can be split into the following three lemmas.
|| (1--)) |1( VIEN.
Lemma 5.3. For any Z E EC.
We highlight two important points from the above theorem. First, the dependence on the problem size is Onr log which is optima. Second, for a well-chosen step- size, the algorithm convergences exponentially at rate
E (A*2)) - 5E (VL.A) 2 2
D (AA")
8

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Lemma 5.4. Let some e, 6 10 be given. Suppose the number of samples m exceeds 96pr (k/e)² n log (n/6). Then, with probability at least
which we split into the mean (expectation) term and the deviation from the mean. We show that:
H,
D(AAT) 5² BDy = = yy BBly + + (BD
18| (BDb))
D(A07) 2 (11-)) | 2 )
Σ V R" yj = 1اارا kj. BD = m (aij))
ca(2; + &,)-
In the above lemma, we use the notation +- = (Ru, Φy) and A = (AuAAv):
The first term is bounded above with the warm-start assump- tion: || I O11oo, The second term is bounded using the matrix Bernstein inequality (see Lemma D.5).
Lemma 5.5. Let some c, E (0, 1) be given. Suppose the number of samples m exceeds 845 (urk/e)² 2 log (n/6). Then, with probability at least 1 8, v Z C CCnBBe B(e).
Showing Smoothness Our method of proving Lemma 5.2 follows the proof style of Zheng & Lafferty (2016). We start by observing that
D(AA") < 10eyo |
|
(V2, W
sup WER -
Using these three lemmas, Lemma 5.1 can be derived in straightforward manner (proof in Appendix E). Indeed, if we ignore the cross-term (fr; y A in Lemma 5.4, is not hard to see that the three lemmas combined lead to the lower bound (VVL. A 2 y || The gradient of the regularizer helps cancel out this cross-term, but leads to the additional | ADDI ||² term.
Therefore, suffices to find a bound for the term on the right hand side of the above equation. The following lemmas, proven in Appendix D, provide the requisite bound.
Lemma 5.6. For any Z E C and any W E B
(VL, WY S 2=a (D(AT") (D(AA")) D(W
The steps in the proof of Lemma 5.3 are algebraic in nature and largely follow the pattern presented in Zheng & Lafferty 6))16); the proof is given in Appendix B. The main technical contribution of our work lies in the proof of Lemmas 5.4 and 5.5. Although the statements of these lemmas are similar to Lemmas 10 and respectively of Zheng & Lafferty (2016), prove these results in different ways. We outline the broad steps taken to prove these results, filling in the details in Appendices C and D respectively.
Lemma 5.7. Suppose the number of samples m is at least
2n log(An/0) (4n/)). Then, with probability at least 1 - 8, the following inequalities hold uniformly for all E C:
D(AT²) 16y(uraū) ||
D(AA²) < 416>(uroi) ||
D(W S 1927 ||W I A W W Rexr.
key step to prove Lemma 5.4 is to show the identity:
D (A+7) -'TSpp Spu, where A vec(AR"))
Lemma 5.2 follows by combining these lemmas and ac- counting for the gradient of the regularizer (see Appendix E).
Sp A 1 ana a A vec((AA + )"). (22)
6. Simulations
Here, we use the notion of vectorization of matrix, i.e., stacking the columns of a matrix to form vector. Thus, for a matrix Z E _xr,, vec(
We generated random ground truth matrix X E 1g with entries selected independently at random according to normal distribution and calculated its rank-r SVD, U' We have two settings: low- dimensional setting with (N1, n2) = (200, 300) and a high- dimensional setting with (MI, = (2000, 3000). both settings, we had = 3, μ R 1.01, x. 1.1. Using this matrix, we randomly and independently collected m com- parison data points. Specifically, for each setting, the com- parison dataset took the form {(AR, wk) ) k == =,,...,, m)) where A represents the 11th sampling matrix as in (5) and and Wい = g (A, Z Z'Z' )) In this work, we set the reg- ularizer coefficient to be À = 7/40. Subsequently, we applied Algorithm using the stepsize 7) as recommended
Data Generation:
Z) is a vector in R".
Given this quadratic form, it follows that:
[D (D - [D s ||5p B[Sp]lla |ee
The term Sp E[Splll can be bounded with high prob- ability using the matrix Bernstein inequality (see Lemma C.6). To complete the proof of Lemma 5.4, it remains to calculate E {DD (A In Lemma C.2, we show that E [D [A+")] = 4 + AV
The proof of Lemma 5.5, just like the one for Lemma 5.4, involves analyzing quadratic form around a random matrix,
8

---

Nonconvex Matrix Factorization with Sparse Comparison Data
WSC3 Pig Pry.
11222000 007
0x107
2x100
m=100
3x10
2
(a) Different initializations
(b) Varying dataset size
With Sral 1/8 oUt 1905
mm11500
m=-35000
100000
110000
10
Deration
Ewolicn
(c) Different initializations
(d) Varying dataset size
Figure 1. The top row and bottom row show the results for (m1,m2) = (200, 300) and (m1, = (2000, 3000), respectively, (a) and (c) illustrate the effect of different initializations with fixed number of data points, while the remaining plots demonstrate the effect of varying dataset size m. Y-axes are in log scale.
by Theorem 4.1. The quality of the algorithm's 's output at iteration é is measured by [|A(Z")| (nnng. Our code can be found here. Figure presents the resulting plots.
verges rate for computed by connn)) with 8 = 0.05 and co being 1/4 for low-dimensional and 1/2 for high-dimensional setting. In Appendix F, we present an additional plot that highlights the dependence of m on r.
Initialization: We initialize the algorithm with 7 z (Ni, N2J), where Ni R" xr and N2 R with their entries drawn from standard normal distribution. For experiments, we use 0 E {0.5, 2). Figures (a) and (c) show the effect of different initial solutions and also the projection steps in low and high dimensional settings, respectively. In both settings, the number of data points m and also the stepsize were chosen as recommended in Theorem 4.1. This result confirms the linear convergence of Algorithm as predicted by theoretical analysis. It is important to emphasize that while both warm start and the projection step are required for our theoretical guarantees, these simulation results suggest that they are not needed in practice.
7. Conclusion
In this paper, consider mathematical model for comparison-based recommender system: the concatena- tion of the classical matrix factorization framework with Plackett- Plackett-Luce-stlle comparison oracle. We proved that, given a relatively sparse dataset, the parameters of the model can be recovered through an efficient, gradient descent based algorithm, despite the loss function being nonconvex. Our proof rests establishing that the loss function satisfies properties akin to strong convexity and smoothness in neighborhood around the optimal solution. For our analysis, we made two assumptions: we are given a warm start and we observe the exact choice probabilities (rather than binary outcomes). We hope that our work will form the basis of further analysis of this problem that performs global anal- ysis or provides guarantees for data with noisy comparisons. Finally, we believe that this work is an important contri- bution in establishing the viability of comparison-bass recommender systems.
Dataset size: We examine the impact of dataset size m on the algorithm's 's performance. Figures (b) and (d) demon- strate the resulting normalized errors in low and high dimen- sional settings, respectively. As depicted in these plots, large enough m leads to linear convergence of the algorithm while for a small m, the error ||A(')) I| does not go to zero as increases. both plots, the red curves show the con-

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Acknowledgements
Koren, Y., Bell, R., and Volinsky, C. Matrix factorization techniques for recommender systems. Computer, 42(8):
This research has been supported in part by the Swiss National Science Foundation (SNSF) under grant I2BR22.186133.
30-37, 2009,
Ma, C., Wang, K., Chi, Y., and Chen, Y. Implicit regulariza- tion in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations of Computational Mathematics, 20:451-632, 2020.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Maystre, L. and Grossglauser, M. Fast and accurate infer- ence of Plackett-Luce models. In Advances in Neural Information Processing Systems, volume 28, 2015.
References
Mnih, A. and Salakhutdinov, R. Probabilistic matrix factor-
ization. In Advances in Neural Information Processing Systems, volume 20, 2007.
Bengs, V., Busa-Fekete, R., Mesaoudi-Paut A. E., and Hüllermeier, E. Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research (JMLR), 22(7):1-108, 2021.
Negabban, S. and Wainwright, M. J. Restricted strong con- vexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research, 13(():1665-1697, 2012.
Bengs, V., Saha, A., and Hüllermeier, E. Stochastic con- textual dueling bandits under linear stochastic transitivity models. In Proceedings of the 39th International Confer- ence on Machine Learning, 2022.
Negahban, S., Oh, S., and Shah, D. Iterative ranking from pair-wise comparisons. In Advances Neural Informa- tion Processing Systems, volume 25,2012 2012.
Candès, E. and Recht, B. Exact matrix completion via con- vex optimization. Foundations of Computational Mathe- matics, 9:717-772,
Negahban, S., Oh, S., Thekumparampil, K. K., and Xu, J. Learning from comparisons and choices. Journal of Machine Learning Research, 19(40): 95, 2018.
Candes, E. J. and Plan, Y. Matrix completion with noise. Proceedings of the IEEE, 98(6):925-936, 2010.
Park, D., Neeman, J., Zhang, J., Sanghavi, S., and Dhillon, I. Preference completion: Large-scale collaborative ranking from pairwise comparisons. In Proceedings of the 32nd International Conference on Machine Learning. 2015.
Chen, Y. and Wainwright, M. J. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint (rXiv:550900025: 2015.
Rendle, S., Freudenthaler, C., Gantner, Z., and Schmidt- Thieme, L. BPR: Bayesian personalized ranking from implicit feedback. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, 2009.
Davenport, M. A., Plan, Y., Van Den Berg, E., and Wootters, M. 1-bit matrix completion. Information and Inference: Journal of the IMA, 3:189-223, 2014.
Saha, A. Optimal algorithms for stochastic contextual pref- erence bandits. In Advances in Neural Information Pro- cessing Systems, volume 34, 2021.
Ge, R., Lee, J. D., and Ma, T. Matrix completion has no spu- rious local minimum. In Advances in Neural Information Processing Systems, volume 29, 2016.
Shah, N. B., Bradley, K., Parekh, A., Wainwright, M., and Ramchandran, K. A case for ordinal peer-evaluation in mooes. In NIPS workshop on data driven education, 2013.
Ge, R., Jin, C., and Zheng, Y. No spurious local minima in nonconvex low rank problems: A unified geometric anal- ysis. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Shah, N. B., Balakrishnan, S., Bradley, J., Parekh, A., Ram- chandran, K., and Wainwright, M. J. Estimation from pairwise comparisons: Sharp minimax bounds with topol- ogy dependence. Journal of Machine Learning Research, 17(58): 2016.
Keshavan, R. H., Montanari, A., and Oh, S. Matrix comple- tion from few entries. IEEE Transactions Informa- tion Theory, 56(6):2980 2998, 2010a.
Keshavan, R. H., Montanari, A., and Oh, S. Matrix com- pletion from noisy entries. Journal of Machine Learning Research, 11 11:2057-2078, 2010b.
Stewart, N., Brown, G. D., and Chater, N. Absolute identifi- cation by relative judgment. Psychological Review, 112, 2005.
10

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Sun, R. and Luo, Z.-Q. Guaranteed matrix completion via
non-convex factorization. IEEE Transactions on Informa- tion Theory, 62((1))6335-657), 2016.
Tropp,.. An introduction to matrix concentration inequal- ities. Foundations and Trends@ in Machine Learning, 8 (1-2):1-230, 2015.
Zheng, Q. and Lafferty, Convergence analysis for rectangular matrix completion using Burer-Monteiro factorization and gradient descent. arXiv preprint 10Xiv:1605.00051, 2016.

---

Nonconvex Matrix Factorization with Sparse Comparison Data
A. Helper Lemmas
A.1. Matrix Inner Product Identities
We state some basic identities of the matrix inner product operator, which are trivial to verify but are used frequently in the paper. In the following identities, D, E, and F are arbitrary matrices so long as their sizes are compatible with the equations.
(E, = Tr(EF*) = Tr(FEt) (F., = (F, (F", )FT) (DE,F) = - =
(23)
(24)
(D,EF) E. (EE"DFF) D,
(25)
From these identities, we get that for any sampling matrix A (defined in (5)) and any Y.Z Z E Ruxr:
((AA ((A+A")Y, = ([AY, Z + (AAY, Z)
=(A,ZY") (A7 ZYZ)
= (AA, +YZ")
(26)
Let W and Z be two matrices in R= Recall the notation convention introduced in Section 5. Using the above identity and (5), we get that for any sampling matrix A corresponding to the triplet (u:; i,
((A + A") WZT) = (eu(ē; - =, We Zv + Zv (W.: 21 - z3 + (Z W; - W
(27)
(28)
A.2. The Frobenius Norm of the Product of Two Matrices
Let X be any matrix and let maxx and miin (X) denote the largest and smallest singular values of X. Let v be any vector such that the product X u is compatible. By the definition of singular values:
Omin (X) |ell2 S [[Varl2 S m (xmax(X)ai ||ll2
Using this basic fact, we can prove the following result.
Lemma A.1. Let U RRi x and V E R be any two matrices. Let 01 (U) 2 ... 2 (U) denote the singular values
U and (V) 2 ... 2 (V) denote the singular values of V. Then |UVT| satisfies the following bounds:
(U) IV - |UV S (o) |V (v)2 1U S |UV S (V) ||
Proof. We first prove the inequality 2 o, (r x matrix). Let (UVTY' denote the jth column of UVT Finally, note that the squared Frobenius norm of a matrix is the sum of the squared lg norms of its rows or of its columns. Stitching together these simple facts, we get.
|V Let V, denote the jth row of V. written as a column vector
n2
n2 Σ
|UVT
|
2
Σ
LUV1
==1
n2
n2 Σ
>
(U)² |1 = (U)²
V
1=1
1=1
o, (D)² |V
The upper bound | 0n (U) 11Vll2 instead of |UV 2 (U) [V
F < a (U)² | can be derived using the same steps, except we use the inequality |UV 11 <
Finally, the second set of bounds follow by applying the first set of bounds
the matrix VUT, and noting that [UVT F VVT
12

---

Nonconvex Matrix Factorization with Sparse Comparison Data
A.3. The Incoherence of the Iterates
Recall that have assumed that the initial point 2 satisfies the bound || - o i.e., we are given warm start (see Section 4). With this assumption,
prove the following lemmas.
Lemma A.2. Let C be the set defined in (20), i.e.,
= 2 _ 11,
{
4 1 S 3 101|F
Then all the equivalent ground-trate trrnhh matrices lie in C, i.e. & CC
Proof. Start with the identity 2 = + (which follows from (18)). By the triangle inequality, we get
x (0(z))l1> - - || = (z))) + ||A(Z))
Note that all matrices in & have the same Frobenius norm. This implies that || || || Combining this with the bound on |A(Z)) ps we get
1- 1 S 1 FF + 0
(29)
Recall that the singular values of Z are 220 / 20 norm of the vector of its singular values. Therefore:
20,.
We know that the Frobenius norm of matrix is the &
Z r
12 P =
2
o
<
4
1=1
3
||2 2 1 11 v 0
/ 2 7
11 1|
4 v u/n 11
1| vp/n 2 2 3
Thus, we see that Z E C. Because all Z E 4 have the same f norm, it follows that d C C.
Before proceeding further, we introduce some new notation. Recall the convention (established in Section 5) that any matrix Z can be viewed as a concatenation of two matrices: Z = (Zu, Zv). ). To index the rows of Z, we use Zu, u E [mi] for the user features and Z,, Zy.j E [m2]] for the item features. In expressions involving matrix multiplication, we view Zus Z, 2) as row vectors, i.e., as X r matrices. By the definition of || 12. we get:
| = max max
|Zull2 max [E(n:]
(30)
(E(
Equipped with this new notation, state and prove the next result.
Lemma A.3. For any Z e C. let W Px(Z). Then W E C. i.e., W satisfies
12p
|
||
n
Proof. Let z denote the mean of the rows of Zv, i.e.,
Σ 74
12 (E(mz)
follows that
||
1
Σ VE(Na)
Zi
1
1|2,112
S
Σ
1 = 11
(by (30))
122
n2
n2
(E(nz)
sE(ma)
2
13

---

Nonconvex Matrix Factorization with Sparse Comparison Data
The operation of projecting onto the subspace H is such that Wy -Zy and W;- Z3 v for all item rows (see Section 3.5). By the triangle inequality, get:
W. ll2 2| =1|2 - |2 + |||||
max ma
Wi S max |2il12 + || S || + 112112 s 2 2,00
.E(ma]
Because the rows of remain unchanged, we have | 2,,00 S 22112112,00 Next, note that C. Therefore.
4
5
1,10,
Z
1Z"||F
3
3
The last step uses the inequality | F (5/4) 2 F. which follows from (29) in the derivation of Lemma A.2. By combining the above inequalities, we get the desired result:
| 2.30 s
54112
25 p $
7
12p
1 p
9 n
The above result important because it establishes a useful bound that holds for all iterates Z E E4. (Recall that Algorithm takes successive projections, first on C and then onto H.)
A.4. Bounds on the Scores
In this subsection, we derive two related bounds on any Z E Raxr and any sampling matrix
I(A,, 2 S 2| [[ + A F |l
(31)
(32)
Before we prove these bounds, let explore its consequence. By the definition of the incoherence parameter l (10), | (p/n) 1| Therefore,
24 1 5 \1
I(AA, (A,
(33)
6μ [[ + AT) -
12
(34)
Moreover, for all Z C,
24μ |A, 1|
(35)
71
72μ
(144 + AT 2
<
7 ||
(36)
As argued in the previous subsection, all iterates (Z') of Algorithm 1 lie in C and consequently satisfy the above bound.
We now proceed to the derivation of (31). Let Z E Ruxr be some candidate feature matrix and let X = Zu 27 be the corresponding score matrix. Let (u; j) be an arbitrary triplet and let denote the corresponding sampling matrix. Recall the definition of the sampling matrix A corresponding to a triplet (ı; i, from (4) and (5). We have
K( Z2 = |ou.i - Fu,حo = (Zu, (Z, 2,)i < || /
Z, 21112 - 1Z l2 (1 l.2 + 1Z1l22 $ 2
The last inequality follows from the definition of || (see (30)).
14

---

Nonconvex Matrix Factorization with Sparse Comparison Data
The derivation of (32) proceeds as follows.
eu (
--)²
A
0
0
ea (é; Ej)²
A A
(2 2
0
cu(E: - =
Zu
(A A²)Z=
(ē e
0
ZoV]
eu ēÿ) Zv
(è: 2,)e,
Tel -zj]
(e R.)
([ 1 7/ |e.(Z, Z;) + [(2; Zul?
le 2 2, 2 |1 - 12ul12
1 27112 2
(leull 1, ||ē - éøll2 2)
+ +12,112) < 2( 11 - +2 (11 - 2i112 S (112:ll2 + +112)112² = 2012
$ 6 2l.00 (by definition of || 1,,00 (30))
This establishes the second inequality.
A.5. The Matrix Bernstein Inequality
Here, we state special version the matrix Bernstein inequality that we use our proofs. The statement is identical to Corollary 6.2.1 in (Tropp, 2015), barring change in notation.
This concentration result is stated in terms of the operator norm of matrix X, which denote || and is defined as follows:
|
sup wlllv|1==1
|x
(37)
It follows that |2|2- Tmax (X). For square matrices X, an alternate definition of the operator norm is:
|X|2 A
sup ==||=|1,=1
(38)
Lemma A.4 (Matrix Bernstein Inequality). Consider random matrix X of shape n, ne that satisfies:
[[X] X and || S L almost surely.
Let b be an upper bound on the second moment of X:
|E|XX*||| ||2 b and |E|X"X]] X]|| S
Let Xp 1 Em X where each X is an i.d. copy of X. Then, for all t. 2 0,
mt? /2
PO X112 2 t) (n1 + n2) exp
+ 2Lt/3
15

---

Nonconvex Matrix Factorization with Sparse Comparison Data
B. Initial Lemmas
Following the convention the main paper, we drop the explicit dependence on Z wherever is obvious.
B.1. Proof of Lemma 5.3
Lemma 5.3. For any Z E C,
(VL,A)) 2 E D (A*)) 2
5E
D (AA7)
Proof. From the expression of VL (see (9)), we get that:
1 h ((Ax + A ) Z, A) where h2
g((2k) (g(2k) - -wk)
(VL.A)
24: (Ap. Zzz
m71
g(2x)(1 g(2x))
Recall, by definition (see (18)), that Z + + A. Therefore. the term ((AA AT) A)) be expanded as follows:
((Ax + 2, = ((AA + 47) ((AA + A))
(AA A ) + (AA + AAT) (by (25))
Since we have assumed that our observations are noiseless, we have the identity wp = g Ak, 2 2)))). Plugging this equation in the expression of h2, we get:
g'(x)) (g(2x) - g(2)))
= = (A= = -\)
g(=x)(1 - g(=x))
By the mean value theorem,
g(EN) g(*t) = g'(()) = for some ys in the interval between zu and zk
= g'vx) (K.Ag, Zz (AA,, )
= (yx) (KAs, D1T + A + (AA AAT)) (because Z = = A)
1 (AA + A4T))") )
= (yx) (Axx + A AD"")) +
(by (26))
2
Putting the above equations together, we get:
h4 M4AA + A,)
( (vb)
(A, + AT,
1
(A4 + AT,
+
(CAr + AT, (AA +
(1= 9(x)))
2
(zw)) (ub)
(As + A4T 2 +
3
(Ax + A4. + (A.
(1 g(zx))
2
of (=k)9' (M1)
1
((AA + AT, AT,
(A. AA
(1=)(( ((x)))
562 The last step uses the inequality 2a² + 3ab + 12 2 a²
which can be derived from the trivial inequality + +b/222² 2 0.
4
Note also that the coefficient
(x(z )s' (vx)
is positive.
((=x [[]e]]
Finally, observe that we have assumed Z E C. The bounds in (33) and (35) imply
| < 2 1 1|
| S 24 u1 11
which implies lyk| S 24 24 ||
n
n
n
Thus, Ye and zy lie in the interval -24 1| /n, 24 - [p//n] as the definition of the operator (--) (7), the desired expression follows.
By the definition of and E in (1I) and (12), as well
16

---

Nonconvex Matrix Factorization with Sparse Comparison Data
B.2. Proof of Lemma 5.6
Lemma 5.6. For any Ze C and any W R
(VC, wy S 2 (DIA0T) + + D(WZ*).
Proof. The proof of this lemma is similar to the proof of Lemma 5.3. One major difference is that we work with terms of the form ((A + AT, Y') instead of terms (AA, Y)).
Following the steps of the proof of Lemma 5.3, we get:
(VL,H) 1
Σ ha + H)) where he 5((xx) (g(=x) wx) g(zx)(1 - g(zx))
2 (Ax, zz*)
m k=1
g(2x) - ((zī) = g'v)) (KAA, F5 + A + (Ak, AAT)) for some yk in the interval between 24 and =
By (24) and (25). we get:
((AA + + (A+ + H
1 7 + AA AAT) A (A.. DD + + (AA. AAT) = (A, DAT)
Putting together the equations above, we get:
(VC,H) g(x)) (1x) g(x)(1 g(xx)) ( (LAL+AA + +
AATH + 1 2 + AT, AAT>) ) (RAA + AT. HZ²))
(39)
Next, we invoke two straightforward incqualities (ax)<e(m) (bx)ke(m): and (cx)uE[m) with as 2 2 k:
which
apply
to any
sequence of scalars
1
m Σ
abbRCk
abbs
ax
1
1
VA
max as kE[m)
b
The first inequality can be viewed as a form of the Mauchy-Schward inequality and the second, form of Hölder's inequality. Squaring both sides of the equation in (39) and applying these inequalities with
(z )g' (v()) 0g (1 g(2x)) be (Ax + A T4 + 1 + AI AAT), ck c== c(AAAA++ + AT. H7T 1)
and observing that maxxe[m] ak S = (using arguments similar to those in Lemma 5.3), we get
=² 1 Σ
((AAR + TAT 2 (AA + AT AATH))
L ( (A + AT. H
k=1
k=1
< 2=a
1 Σ
(As + 0
1
AA
AT AAT ))
1 S AT. HZT m
m
m k=1
k=
= 2= (D(A0T)+ + ((AA7)) D(H2T),
giving us the bound we want.
17

---

Nonconvex Matrix Factorization with Sparse Comparison Data
C. A Lower Bound for Strong Convexity
In this section, we present the proof of Lemma 5.4, following the approach presented in Section 5. Recall that the goal is to find a lower bound for D (Aæ") that holds with high probability. Our approach will be to first derive an expression for [D (A+*)] and then show that D ( (A is close enough to its expected value. Crucially, we want this result to hold with high probability uniformly for all Z E C.
C.I. Computing Expectations
Recall the definition of the sampling matrix A corresponding to triplet (u; from (4) and (5). In this section, we view the triplet i.) as random variable where u is chosen uniformly at random from [n1] and the pair of item indices (i,j) is chosen uniformly at random from the set of (12 - 1) pairs of distinct items, independent from u. Consequently, eu is a random vector in R é - 2g is a random vector in R and the sampling matrix A is a random matrix in R With this interpretation, we can compute:
1 m.. I
1 11
E Elene 2
Ri( - 2,) -
= n2
J, where =In,
(40)
11
n22
Also recall that y denotes the constant 2/(m (n2 - 1)).
Using these identities, we show the following result.
Lemma C.I. For any matrix X E TR
E (eu(ee (g)" x 7 |
Proof. This proof makes repeated use of the following properties of the trace operator:
the trace is invariant under cyclic shifts, i.e., Tr(ABC) = Tr(CAB) Tr(BCA)
the trace of a scalar is the scalar itself
the trace is a linear operator which commutes with the expectation
We also use the fact that the indices u and (i.j) are independent, so the expectation E[-] can be decomposed into E,,, [E...-]. I-].
(ea(E ēj)", xy- = Tr(ea( - 23) ) x Tr((ē: XTTel ew) = (és - xxT en - -2,)
(,)= = (a-6,) e 2,)
+ El(en( - x E[(ē: E₁)² x" e X(e ē;)] = E, E. E1) x- e X(e: - Ej)]]
= -E,l(ē - 6) le. 2 X(; - -2,] = _ E - ,²)²'x² x x"x(, - 2,)1 (by (40))
nn
1
Eig[TT((E - 21)² x X(e: - -2,))] = E TT X(e: - -2) - 22)²
=
n1
n1
1
2
TM(X XTE (e, - -,)(e 22)²)) = 11 -1)
TT(X'X)) (by (40))
n1
2
2 Tr((JX)
Tr(X" XJJJ' = ni(na -
mi (m² -
2
|| = ||
ni (n2 -
In the last but one step, we make use of the fact that J is projection matrix, which implies J = JJT
We use Lemma C.1 to prove the next result.
18

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Lemma C.2. For any Z E H,
[ = =rAAcr - 1
-
where 2 (R0, and = (Au, Dv) denote the split of and into the first ny and last n2 rows.
Proof.
E D (A
E
1
(Ax A A0
m
[A++ AT, A
[(ea(ā - 2,)² tu A Do "
(by (27))
(by Lemma C.1)
Y A + A +
The last step uses the fact that T. = of and AJ = A These identities can be shown as follows. By our assumption on Z", we know that Z* E H. It follows that the entire equivalence class of solutions & lies in H. particular, (Z)) H. We are given some Z E H. This implies (ZZ) E H. because ((Z) Z (() and H is a vector space. characterization of H is that for any Z (U in H. JV V. equivalently, V J V (J is symmetric). Thus, it follows that T = & and ATJ AV.
We end this section by bounding the expression in Lemma C.2 from below. Lemma C.3. For any Z E H.
E D 27 (0; - 22.004..
Proof. By Lemma C.2,
E D A4
Ar A. AT 1|
7 (140 A I' + +2 )v
27 (1;11A 11 A 11 2( (. (by Lemma A.1)
|| 2 2 2 2
Here, we use the fact that (2x4) o, (vv) Vor This can be shown as follows. Recall 2 = 1U2 1/y and + = Z R for some orthogonal matrix R. Therefore, tu 1/2 R and Φy = 1/2 These expressions are already SVD form. Therefore, the singular values for both b6 and by are the diagonal elements of 10 namely, Vo Vo.....vo
C.2. Vectorization and Quadratic Form
In this section, we shall show that D (A#z) can be expressed as a quadratic form around random matrix. This identity will help us prove the desired concentration result the next section. Let us establish the following notation.
v vec(AR"), ), ak vec((As + 2²)2z), Sa e araf Sp
A m
Sk
(41)
k=
where for any matrix Z E Rxxr vec(Z) is a vector "R obtained by stacking the columns the matrix one after another. This operation is called 'vectorization of a matrix', With this notation in place, we proceed to establish the following identities:
19

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Lemma C.4.
D (Aa") = =0 SDU
||0|2 = ||
Proof. Recall from (17) that + R. Let Å _ AR Then
AΦ" AR Z ÂZ (Ao" + + (ÂZ +²
(42)
Next, invoking the notion of vectorization, we get that for any le m:
{A, Az > ((AA, + أ (by (26))
(ve + A I*), vec(Á))
() (by (7))
(A, AZ + (u, ax) (ax, v)
x Syu
:D (A@" + +0A") = D AZ + 2
(by (42))
m Σ
(Ak, Âz =Z"A")² (by (7))
m
1
Sku
1
Sk v
m
xd SDV
The second statement can be derived easily as shown below:
||ul|2 ( (vec(AA()) ), vec(AiR))
(ART, ART))
(ART R, A))
(by (25))
((A, A))
(because R is an orthonormal matrix, R R = I)
||
C.3. A Concentration Result on Sp
Recall, from (41), that Sp is the empirical mean of i.i.d. random matrices (Sx) Let S denote the prototype random matrix of which (Sk)ke[m) are i.i.d. copies, and let 5 denote E[S]. In this section, we will use the matrix Bernstein inequality (Lemma A.4) to establish an upper bound on ||SSp S $1l. (Recall from (37) that ||x|| denotes the operator norm of X.)
In order to apply the matrix Bernstein inequality. we need to compute two parameters, b and L, that satisfy:
|| S L almost surely,
|||[ST]|| <
Here, is symmetric, so =
20

---

Nonconvex Matrix Factorization with Sparse Comparison Data
For any rank-one symmetric matrix Y yu", [|Y||2 || Here, S aa where a vec((A + 2²) for some sampling matrix A. Using this formula, we get
61 12'1/ almost surely (by (34)) || + A 2 F S n
||S = ||al| = Thus, 6(u/n) || ?/ Moving on to the calculation for b, we get:
B[SST] = BBlaa T aa = 1||aall aa") = ||E[S|T||| = ||||a| ad ad²) 1
s sup([aal |[|aa"]]l, [|[[aa) Ill2 s L ||B[aa")]]2
Where, in the last step, 4a
the fact that ||a12 s L almost surely. The following lemma establishes the bound [Blaa"]], S mi( Thus, we can choose b b= 2y L.
Lemma C.5. Let a E " denote a random vector such that a = vec((A + 2²)2"), with A being the random sampling matrix defined in Section C.I. Then
||aaa)] "11, S 270
Proof. We adapt the definition of the operator norm of a matrix as follows:
[2| (aaa"ll2 =
of Blaa"Ju Ju
sup VER".. 1011=1
vec 2)² E[aa" Ivec()) [laa")vec(2) ()
sup ZeR=xr:[Z] 1
ZEBuxr:|[] 11 Elvec (2 aa vec(2)]
sup
B[(vec((( ( + )"' vec 2
sup
ZERuxr:|12]
r=1
[[[[(A + A² |Z* ,
sup 20
Following the same reasoning as given in the proof of Lemma C.2, we see that:
EI((A +
J|
5 <><1 + Zu p2 (by triangle inequality)
<2>(Zz)27>>11 |zo || (by (a b)2 < 2((a² + b²)
|z= ||]] (because Zi7" -
s 22>(0i 1
+ +oj || |1 (by Lemma A.1; 01 (Zi) = a (Zt) ooi
S 270 ( 2 + 1 (22) (by Lemma o, =1
= 2 ||
Plugging this bound into the expression above, get
Elaa" 1lll111
E[((A AZ
sup zeRnxro|ZZllp-
<
sup
2 ||
2,0
We now have all the ingredients to prove the bound on ||Sp - -5112-
21

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Lemma C.6. Let E (0, and E (0, 1) be given. Suppose the number of samples m at least 96rrn (x/e)2 log (n/0). Then, with probability at least 6,
||Sp 151p- S yeo,
Proof. Let the amount of deviation we wish to tolerate be denoted by i.e., == NE0, We have already established the bounds
||SS S b; L 6μ
| S almost surely,
|| FF = 2 L
n
since Note that b = (2T0k/6), since x = o7 By Lemma A.4,
-mt? /2
P[|Spp - -51 2 t) I 2nr exp
b 2Lt/3
We would like the right hand side to be less than ò. L.e.
mtt /2 b + 2Lt/3
2nr exp
S 8
mt?/?
2nr
2 log
b + 2Lt/3
8
mt²/2
'2r
2 log
(:: 2Ltn/c)
2Lt(N/E+ 1/3)
8
4L
K
2ner
2
log
c
Next, note that = ni + n2, which implies b1 (n22 1) S n Further, the Frobenius norm of matrix the Eg norm of its singular values. We have noted before that the singular values of Z are /20 20 Therefore Using these incqualities, we get
I 1/ S 2ro
4L
4
6f T1
12 1
= 4
6p
1 112)
(
[11 (n22 - 1) 2,
[n1(n2 1)) 11) 12 1
12 o7
< prrn
Also note that x > 1 and < 1, so x/E + 1/3 bounded above by 2k/E. Finally, note that r I n1 and r S 122, so
2r < n1 + n2 n. Therefore, 2nr 5 < 2 /8 < (n/5)². Putting these inequalities together, we get:
96prn (+) log
4L
K log
2nr
+
3)
Thus, the desired concentration result holds with probability least 96urn (n/e)² log (n/8).
5 if the number of samples m exceeds
C.4. Completing the Proof of Lemma 5.4
Lemma 5.4. Let some e, E (0,1) be given. Suppose the number of samples m exceeds 96pr (1/(²) n log (m/8). Then, with probability at least 1 5, v z H.
D (A*T) 2 ((1 ( 1)11 28 AT. So 2001
22

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Proof. In Lemma C.4, established that D (A -u² Spv. Consequently, B[D (At")) x² Sv. Therefore,
[D (A+")
E [D
10 SDU o
(by Lemma C.4)
100(SD -S)ol
< || $11, ||u12
(by (38))
= S0 511, |
(by Lemma C.4)
(A+7)
(D) (A ||50 S112 ||
27 o, | 26 A - -|s - $11, IAII
(by Lemma C.3)
2 (1 - c) | 2 4,
(by Lemma C.6)
D. Upper Bounds for Strong Convexity and Smoothness
D.1. The Dual Sampling Matrix
Associated with each triplet (u, j.), define the dual sampling matrix as follows:
BER :B en + Ez))
(43)
If we endow the triplets with randomness, B is random matrix, whose mean is:
Ble., + =, 2 11
B B[B] = Blen -B)
(44)
111 122
Here, _1 matrix of all ones of shape n 122-
Let Bi...., Bp denote the dual sampling matrices for each of the datapoints, similar the notation for A. Define the empirical mean of the dual sampling matrices, Bp, as follows:
Bd
B
(45)
k=1
In our analysis, we will use the fact that this empirical mean Bp close to the statistical mean B, a manner made precise by Lemma D.5. In preparation for this concentration result, we two parameters, L and (The same notation was used denote related terms for the random matrix Sp in the previous section; however, the correct interpretation should be clear from context.) L is uniform bound on | 2l For each triplet (u; j). the operator norm of the corresponding dual sampling matrix is /2. It follows that L 22. The definition and bound for is given in the lemma below.
Lemma D.1. Let B be the random dual sampling matrix defined above. Let b¹ & B[BB 62 & |E[BB") by and b max(b', b2). Then
min min,
Proof. We know that [leul1 = and || + 2, 1 = almost surely. Further,
B
T
1 - Jayr
B(G + (5)(E + + = (7²)
(11 (nz T)
na
23

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Using these identities, we get
BIB² BJ = Bl(é, + en
= Enyl(e + Ey) Bule
Enyl(e + E,)(é: + E,)²
= (11" + (m2 - 2)
(22
E|BB"| = Blen + 8j) ( + +,j)et]
= Ex (6 + ()) + E,)le
(ea
2 Lm
n1
Computing the operator norms of these matrices straightforward:
b²
|
B1|
111" T +
(m2
2)
112
(1/11"1/2 + (n22 2) (1 l12))
1
(n2 + (n2 - 2)) 12
(2))
(222
(m2)
2
2 <
4
82 ||
1||2
1 l12
71
16
71
b =
max <
min 12)
D.2. Algebraic Upper Bounds on D(W2*)
This subsection contains three lemmas that we shall use in the proof of Lemmas 5.5 and 5.7. The first of these three lemmas, Lemma D.2, gives an upper bound on D(W )") as quadratic form around the random matrix Bp that we defined earlier in the section.
Before we state the result, we introduce some additional notation. Corresponding to any matrix Raxr, define the vector E IR. follows:
2z |2 Vj
[n]
(46)
follows from the definition that
||||| = | ||=1000 = -12122
(47)
Following the convention of splitting the matrix Z into user and item components Z = (Zu, Zv), we split the vector & into vectors zy E "R and zv E Th (z = (zu, )))). The norms of these vectors satisfy the following relations:
|
|| + ||zv Il || || + 11 ||
max( 11
(48)
With these notations and identities in place, we proceed to establish the following result.
Lemma D.2. For any two matrices W and Z in Raxr,
D(WZ") <A(wi BoEv + 25 BDwv)
24

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Proof.
1 m
D(W2*)
Σ (A + A W (7)
771
Σ ((W,: N. Z: - 23) + (Z W; 22 (by (28))
2
Σ
(W.: Z. 2,8²+ (Z,, W; w (by (a + b)2 s 2(a² + b²))
m
(D:i,)
2
Σ
[W 2 11, 2,11++ + 12. 12 I1: - W3ll2 (by Cauchy-Schwarz inequality)
2
Σ
[. (11z + 22 + 1| 12 (1 + 11W3112)2 (by triangle inequality)
m
(Wij))E
2 m
Σ
WW (1 + 12
W 1
(by (a + b)2 S 2(a² + b²))
4
Σ
Wa(4 (2)
Σ
Zu (wi + wz)
m
(u:i,)ED
Σ
We (ealEs + ²²))²)
2V +
4
Σ
zt
+ (eu(E++Eg))) wy
m (wii))DD
m
(wid)eDD
=4wy
Σ
eulés eg)²
2V
420 T
1
Σ
ea(ēi + ēz)² wy
m
m
(arid))D
=4wifBDey + 42 Bowy
The next lemma builds upon the previous result to obtain an upper bound terms of BD B11
Lemma D.3. For any Z E 1R
D(ZZ") 52 22(11212 +2 2 BD 1212,,) 11212
Proof. We start by using the relations in (48) along with the arithmetic mean-geometric mean (AM-GM) inequality to obtain the following bound
||20ع||| + 11æv lla )
||
|| + |12v|1z]
||
|| ||vv|] 11, s
| ll ||
(49)
4
2
2
25

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Using the bound in (49), we show the desired result follows.
D(Zz²)
BDav (by Lemma D.2) 8
Bav (BD B)=v
$ Bav + ||30|2 (Bo - B)zvlls (by the Sehwwy-Schwarz inequality)
s Bay 1B B1| = 112 12vll2
(by definition of the operator norm)
2 =f111"21 2v + |B, - B||2 1| lzvlla llz
(by (44))
11722
$ $12ff11 zv + |BD B B|2 112llla ll (2/(n)n2) - 2/(m1(22 - 1)) =?)
S |2v|l + +l -B11, 11 ll
(1" 1|=112)
1
(7 ||=1l + - [1=15) (by (49))
4
$ 4
(7 [xlll
B|l ||= to |I|11)
(by Hölder's inequality)
1
(1 +
+ (r
- Bl1, 1 00
|
(by (47))
:. D(ZZ)) 2
(7 1Z]6 + + Br B1|2 1
|2||
The third and final result of this section builds Lemma D.2 in a different way compared to the previous one. Here, we obtain a bound in terms of the ε operator norm of Bp. For any matrix X E R2xxx2
||||| & sup e:||u|l;=1
||
(50)
follows that for any v E R
|| - |X ||/]
(51)
can be easily shown that
| = max
|وy
(52)
jE[mal
sE|ml
In addition, we will need Hölder's inequality, which states that for any vectors a, b
(a, b) - |aaloc ||6/] + ||a| z ||a|loc ||a/]
(53)
Using these inequalities, we get the next result.
Lemma D.4. For any matrices W, Z E 1R"xr,
D(WZ") S ([maa( |B|| 11) 2, |
Proof. We start by invoking Lemma D.2, we get:
PW s 4wy BDav 4=4 Bowy
= 4 BTEu
wo + 42 Brwy
Applying (48), (51) and (53), get:
z BTww = (zv, (zv,B/uw) wv) I || BBewy || < | al BB11, ||w ll1 S ||=|| || |/861,, || Il
21. Brwy (2U, Bowv) < || 1BTuy || < | |a [Boll
T
||wv S || [Blll [|
26

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Putting the above inequalities together, get the desired result:
D(W2") < 4 Blwr: we + 42y BDwv
0| | 11, || 11 + 4 || [| |kvlll
S ||2|| (max [max(1/bblll111 1 ([lwll + llw
10 (max|]]Bbll|
|3 ||w], (by(48))
Z 2 (max(]|Boll) ||] [| (by(47))
D.3. Norm Bounds the Dual Sampling Matrix
First, we provide an upper bound on |l Bl This result will be used in conjunction with Lemma D.3 to prove Lemma 5.5.
Lemma D.5. Let E (0, and å E (0, 1) be given. Suppose the number of samples m is at least (5/e))nlog(n(/)) Then, with probability at least 1 - 5,
BB -BI12 min (n 12
Proof. The matrix Bernstein inequality (Lemma A.4) states that
mt² /2 11 + 2T1/3
P([ B|12 2 1) S nxxp
where max[|E[BBB"11, ||[[BBBB]]])))__ B] 111 and L sup g
BBI We have already established that L v2 and v = 4/(mnn ( n2)) (see Lemma D.I). We would like Bm 2 to be bounded above by e/(min(m1,77)) (for some (0, 1)) with probability at least 8. Therefore, the number of samples m must satisfy:
exp (- (- m21/22
8
+ 2Lt/3/
mt² /2
11 2 log
+
211/3
Plugging in the value L = 222 and noting that v = 4t/e, e, we get
ml² /2
2 log )
(41/e) + 22/1133
2 log
(*)
11)
+ 4/6+2/2/3
t
2
min minn(1 n2) log (")
+ m 2
+
3
Finally, note that 4 + 2//2/3 < 5 e < 1) and 2 min(ma 1 n2 S ni + n2 = n. Therefore, m 2 ) log (n/8) is a sufficient condition for the concentration result to hold.
Next, we move on to proving high probability bound on max Bpll BT11 This result will be used in conjunction with Lemma D.4 prove Lemma 5.7.
For this result, need to introduce some new notation and some basic inequalities. Define the random matrix C E [gd x as follows:
C
Cit E/e
(54)
m
27

---

Nonconvex Matrix Factorization with Sparse Comparison Data
where (fx kem) sampled i.i.d. uniformly random from [ng] and (jk kejk sampled i.i.d. uniformly random
from [n2]. independent of (i<)ke[m)- Let C2 IR denote the 1th row of C, but expressed as column vector. Then
m
C2
Ej
(55)
m
follows that
m
||il
1
(56)
m
Note that ||C:|| is the empirical mean of m i..d. Bernoulli random variables of mean 1/nj. Thus, we can bound it from above by the Chernoff bound.
Lemma D.6 (Chernoff bound). Suppose 21, 22,............ Im are i.i.d. Bernoulli random variables with parameter p and let 0 be given. Then:
1 m
me? 2pp11 - p)
P
p+ S exp
(=pp(1
Using Lemma D.6 with == = 1/n1, we get that for any i E [m1].
|1aalh 2 m
m
z exp
2m
Using the union bound, it follows that
2
(- m 2m
max ||Cil ie(m]
2
-
S n, exp
n2
Finally, by (52), we know that
|
= max || ie|m
In conclusion,
P [|c || 2
2 < n exp
m
(57)
2m
Since nı and n2 are arbitrary in the above analysis, one can use the same logic to show that
P P(ICI: 2
2
m
n2 exp
(58)
n2
2n2
Lemma D.7. Suppose the number of samples m is at least 2n log( 4n/5). Then, with probability at least 8.
max([|Bpli
B3b 1111
min
Proof. Define the following two matrices
BB
Σ
e
B3
Σ
Cue
(WiJ)ED
Both B3 and Bb statistically identical to the random matrix C defined in (54). By (58), have that if m > 2n2 (og(4n2/8),
2
8
2
8
P
Bblli
P
BBB
S
(59)
722
4
72
(60)
28

---

Nonconvex Matrix Factorization with Sparse Comparison Data
By construction, Bp -B3 + B.g By the triangle inequality, we get BBll
||
[Bbl]
B 1
Therefore,
4
4
2
2 112
|Bbl1
|Bbl1 + BBll -
|Bll
or
|B 2
(61)
112
7/2
712
Put together, we get that if m
2 2mz
log(412//0) 42226)).
4 2
2
2
P
|Ball
s P
2
or
||
B
||
2
(by (61))
n2
1/2
Y22
S
||BB|||
2
+
BB
||
2
2
8
(by (59))
2
By a similar argument, we can show that if m 2 2n1 log (m1 421/8),
[BBbll
4
P
2
5
71
Finally, note that
4
4
BBll1 S
and ||
S =
|
BBll
||
n22
min n11
m2
4
4
[B8||
|Boll 2
||
2
min 11,, n2
n2
n
Invoking the union bound once again, we get that if m 2 2n (on((444/0))
p ((1Bbl)
2 min min(n1,n m2) ) S
4 2
4
)
|Bobl1
or
||
BB
2
f22
n1
< P
||Bb|] 2
4
+
P
|
||
>
_
4
12
m
< 6
D.4. Proof of Lemma 5.5
Lemma 5.5. Let some c, E 10, be given. Suppose the number of samples m exceeds 845 (urk/e)² n log (n/8). Then, with probability at least 1 5, V. 7 E CC)(
D(AAT) < 10eyo; |A||
Proof. The proof follows from the following facts:
D(AAT) s 2 (1 +2 Bo - B12 11. ||||| by Lemma D.3.
||A| E0; V B(e).
|| S 52prro n v Z T. This can be derived as follows.
A 00 = 1| + 12.00 2² 211212. + || 12.00
12μ
11
52pro
2
where the step follows from the fact that 1 s 2ro
29

---

Nonconvex Matrix Factorization with Sparse Comparison Data
The number of samples is least 5 (13rrk/e)² log (n/6) (845 5 132). By Lemma D.5, with probability least
6,
1
BB B112 v 13rrk min ( (11, n2)
Combining these inequalities, we get that with probability at least 1 - 8, V E BnE.
D(AA)) 2 > 2 + +2 B B|1 1 2, ) || ||
< c9o; + 13pmm min min(n1,ne)
c
52uro²
||
10 ||
The last step is reasoned as follows:
2
2
2
2
2
min n1 n2)
(n1 + n2) min m n2)
max n22 min (11, (n n23
n1 (12 1)
=7
D.5. Proof of Lemma 5.7
The proof of Lemma 5.7 depends on Lemmas D.4 and D.7.
Lemma 5.7. Suppose the number of sumples m is at least log(4n/6). Then, with probability at least - 6, the following inequalities hold uniformly for all Z C:
D(A*") S 16y(uroT)) A|l F D(AAT) < 416 || 1
D I (92o()rro)) ||W||
VW E Rn*
Proof. By Lemma D.4, have that for any matrices W, E R
D(WZ") s ([maxx1| Bpll,
BB 11 |W]]
By Lemma D.7 and the assumption on the number of samples we have made, we get that with probability at least 1 - 8,
4
max BDll
<
min (nin n2
Putting these inequalities together, we get that with probability at least 8, for any matrices W, Z E IRaxr
16
D(W z²)
2 12.0 2,00 [
min n2)
For the first of the bounds we wish to prove, we replace W by A and Z by &. We know that
2proi
| 1|
(:: 11" 1 s 2roī)
16
2proi
=D(ATT) < min ( (n1 n2)
| < (6)()) ||
Here, as in the proof of Lemma 5.5, we use the fact that 2/(n min n2)) S 7. The second and third bounds can be derived in a similar fashion. For the second bound, we use the bound that we established the proof Lemma 5.5.
52proi
| 2,00
Finally, for the third bound, we use the fact that Z E C (see Lemma A.3) to get the bound
S 12
7 11 S
24proi
2,00
30

---

Nonconvex Matrix Factorization with Sparse Comparison Data
E. Proof of Main Result
In this concluding section, we prove the main results our paper, namely Lemma 5.1, Lemma 5.2, and Theorem 4.1.
E.1. Proof Lemma 5.1
As mentioned in Section 5, Lemma 5.1 follows from Lemmas 5.3, 5.4, and 5.5; these are proven in Appendices B, C, and respectively. We restate the results here for convenience.
Lemma 5.3. For any Z C.
(VC,A) D((4"))
S 2
5= D (AA?)
Lemma 5.4. Let some e, E 10 be given. Suppose the number of samples m exceeds 96ur (m/e)² n log (n/6). Then, H.
with probability at least
D (A*T) 2 ((1- 1A| o ()))
Lemma 5.5. Let some e, E (0,1) 1) be given. Suppose the number of samples exceeds 845 (urx/e)² n log (n/6). Then, with probability at least 1 5, v Z E CC)()),
D(AAT) S 10e |A
Lemma 5.1. Suppose the number of samples m is at least 10? (urk/T)² log (2n/6), for some 8 E (0, 1). Then, with probability at least 5, v Z E 7 ((T/0)) nc.
EY
V A
|
AT
Proof. Our proof strategy will be to put together the statements of the three lemmas and work backwards to calculate the value of the parameter needed from Lemmas 5.4 and 5.5 (call them é and 62 for now). Combining the three aforementioned lemmas gives us:
(VL,A)> 2 E (1 - - ||
25 + 2( An
(220, ||
2
4
25(1 - (1) - 25
N0, | + EY A74)
4
Recall from (13) that R(Z) = Zz Dz|12 p. Therefore, VR(Z) = 4DZZ" DZ. Using this identity and (14), we get:
(V (VC, Δ + (V
2E(1 61
25
70, || 4
4
We focus on the last terms. Define X'
21 Then
E
E (2 A XDZZ DZ)
St (
XDZZ DZ
2
Following the steps laid out in Zheng & Lafferty (2016) (Appendix C.1), we get the inequality:
X'
7X || + (x-1) Tr(O DA&T DA)
2(44v AF, A N DZ > 1
DAI
31

---

Nonconvex Matrix Factorization with Sparse Comparison Data
We know that À - (see (14)), which implies X = 1/22. Thus, the last term in the above inequality is cancelled out. Plugging this inequality back into the expression ahove, we get:
25(1 ())
25 70, || + EYRROAE
A
2
44) + ADZZ" DZ
4
25(1
61
25 70, || + 57
(2
A
44 + XDZZ" DZ)
2
29(1 (
25E 70, ||
+ 59
4
1|
1
DA
4 |A
7
2
F
45(1 9 50Ec2 7502
57
yo, |
+
8
Choosing E1 1/8 and E2 = 7/50 = </(0E=) gives us 45(1 - -c1 -50E62 - TEE2 2 2 Therefore,
(VS.A)> > 4
57 of || + E7
|1 DA
The number of samples needed for Lemma 5,4 to hold with probability at least 1 - 8/2 is
2 96pr (N/e1)² n log (2n/8) 6144urm log (2m/5)
The number of samples needed for Lemma 5.5 to hold with probability at least - 8/2
m2 2 845 (prk/c2)² n log (n/0) 2 2112500 (urk/T)² n log (2n/8)
The two lemmas jointly hold with probability at least 1 8. Clearly, the sample complexity requirement from Lemma 5.5 higher. Thus, we can conclude that given 2 10? (μrx(E/E)) n log (2n/6) samples, with probability at least 1 6,
EY 8
(Vf.A)= 2
4 of A
+
0
DA F A e HUB((/550) uC,
E.2. Proof of Lemma 5.2
Lemma 5.2 follows from Lemmas 5.6 and 5.7; these are proven in Appendices B and respectively. We restate the results here for convenience.
Lemma 5.6. For any 7 E C and any W E R
(VC, (VL, 2 (DIA0") D(WZ*).
Lemma 5.7. Suppose the number of samples m is at least 2n loollog/////oo Then, with probability at least - 6, the following inequalities hold uniformly for all Z E C:
D(AT") < (6)(1)))) ||
D(AAT) < 416-((urot) || 1|
D < 1927(uroa} ||W | A WW E Rax
Lemma 5.2. Suppose the number of samples is at least 2n log (4n/)), for some 8 (0, 1). Then, with probability
least 1 - 8, v Z B(1)
(5>)²
f < 10
| +
2 of
x DA r.
32

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Proof. From (14), we get that
V + X VR VDZZ DZ
V |V NDZE DZII, 3 (IV/II= DZ < 2 x² jDZz"Dz A)
(62)
We have assumed that Z E B(1), which implies | J 1 oF S of. Using this bound along with the analysis in Zheng & Lafferty (2016) (Appendix C.2), we get:
D22" DZll
S || + 4o A |0 | + 40i DAI
S 30o || 1212 4oj
|| 0 DAI'
- 180(a))² A J 40
D'
(1 S 6o
(63)
The last bound can be derived as follows:
| | + S ( 811 + 21 s 2(11 + 1| 2( (1l))) S 2(20) + to 6o
Combining the bounds from Lemma 5.6 and Lemma 5.7, we see that if the number of samples m is at least 2n log(4n/0) then with probability at least 1 - 5, AA E C.
(VC, w < 23 D(AAT)) + p(AAA)) D(WZ
$ 2E² (16)(uro | + 1047(uro)) IAI): 192;(uroi)) I[I
46000(E)yrro;) ) | / ||W||/
: 1 WER (VL, wy²
46080(E7))ro7) ||
(64)
Putting together the bounds in (62), (63), and (64), and plugging in the value of = En/4, we see that if the number of samples m is least 2n log(4n) 4n/8). then with probability at least v Z B
(ET)
| 2 (46000()))ro7)* | 12(E701) +
2 oi x DA
=0y(o')) 1
(57)2 of x DA
2 F
E.3. Proof of Theorem 4.1
Lemmas 5.1 and 5.2 are the two key ingredients needed to prove the main theorem of this paper.
Theorem 4.1. Suppose the following conditions hold:
The dataset DD consists of m i.i.d. samples generated according the model presented Section 3.1.
The number of samples m least 10 (urk/T)² nlog (8n/ for some 8 (0, 1).
The initial point dd lies in B(r/50).
The stepsize 1j in Algorithm I satisfies na 5 2.5 10-0000000//ee (T/prK))
33

---

Nonconvex Matrix Factorization with Sparse Comparison Data
Then, with probability at least
8, the iterates 2 .........
...... of Algorithm I satisfy:
||( S -1- 11(2))11 VIEN.
Proof. We begin by following the standard steps in the analysis of gradient descent.
AZ )1 = || ((((+1)
1 1 (12
|P (Z -
-
S 1| - //V/(Z)) ((
= ||A(Z) /))((
= ||A
2 |-- >² |} -
The first inequality comes from the fact that ( is the closest point in O to Z++1, this is by definition of #(Z++1), The second inequality follows from the fact that (22)) E C (by Lemma A.2) and (( E H (by assumption); thus, successive projections of the iterate on to C and can only bring it closer to (ZZ)).
Next, suppose the following bounds hold for some positive constants a, b, c, and d and for all E Z+:
(VI(Z2), A())) 2 ||
(65)
|A( & (|000//|-2|012220223-==222201111
(66)
It follows that:
27KTF(2).
S (1 2nja + R²b A(2 + (1/ 2nc ||12))
$ (1 na) || 2
(67)
provided S min(a/b, 2c/d). The last step can be justified as follows:
S
a
2c (1 - 2na + 17² < - nja n d
+ n2d 2nc 0
Further, 7) S 1/a, then 1 - n 2 0, implying that the right-hand side of (67) remains positive. This allows us to use the
inequality repeatedly to yield:
|( (1 na) || VIEZ. VLEZ,
Finally, observe that we have assumed the number of samples given, m, at least 10" (urk/7)²² n log (8n/5). This ensures that with probability least 1-6 5, both Lemmas 5.1 and 5.2 hold. Lemmas 5.1 and 5.2 imply that the inequalities (65) and (66) hold for all Z E H n B(7/50) C with parameters:
87 of b b= (n))oo))))
Ey d (57)2 oi
4
8
Given these parameters, long the stepsize y satisfies 17 a/b 2.5 10 10-00000000///0 (T/ //rn)//aaa// fa, the other conditions on 1) automatically satisfied.
F. Extra Simulation Results
In this section, we present simulation results that highlight the dependency of the sample complexity of the learning problem on the rank r of the ground-truth matrix X*. In this experiment, the parameters used are as follows. The
34

---

Nonconvex Matrix Factorization with Sparse Comparison Data
10
0.0606
0.0500
0.0285 (0.0103)
0.0208 (0.0071)
0.0105 (0.0029)
0.0097
0.0062 (0.0019)
0.0044
(0.0037)
(0.0077)
(0.0073)
(0.0005)
(0.0015)
(0.0041)
(0.0086)
(0.0092)
(0.0080)
(0.0038)
(0.0035)
(0.0017)
Average Error (Log Scale)
Rank
0.0955
0.0919
0.0837
0.0715
0.0507
0.0384
0.0329
0.0170
(0. (0.0009)
(0. (0.0020)
[0. (0.0024)
(0.0057)
(0.0082)
(0.0117)
(0.0111)
(0.0080)
0.1081
0.1072
0.1025
0.0888
0.0744
0.0547
0.0414
0.0298
(0.0005)
(0.0010)
(0.0025)
(0.0056)
(0.0033)
(0.0091)
(0.0108)
(0.0121)
.2
0.1190
0.1196
0.1160
0.1076
0.0960
0.0787
0.0590
0.0423
(0.0004)
(0. (0.0000)))
(0.0022)
(0.0030)
(0.00
(0.0053)
(0.0110)
30000
40000
50000
60000
70000
80000
90000
100000
Sample Size (m)
Figure 2. Variation of the reconstruction emror as a function of the underlying rank of the matrix r and the sample size m, for ground-truth matrices of size (2000, 3000).
generated matrices have size (n1, (r1,,)) = (2000, 3000). We vary the rank among the values 3.. possible value of r. we generate a dataset the manner described in Section 3.1, whose size m varies among the values (30, 000, 40, 000,..., 100, 000). The comparisons noiseless. The regularizer coefficient (X/4) was set to 0.01.
63.
For every
For faster implementation, gradient descent. As our experiments in Section 6 show, we need neither smart initialization nor the projection step. At the end of 300 epochs, we compute the reconstruction error || - xx*1x / //n/nn 122. For each value of r and m, we run this experiment with ten fresh seeds. The values reported in Figure are the mean and standard deviation of the reconstruction error across these ten runs.
optimize the loss function using the PyTorch implementation of Adam instead of using
We observe that the reconstruction error uniformly increases with the rank and decreases with the sample size m. Interestingly, if we observe the boxes with roughly the same error, that the sample complexity increases roughly linearly with the rank This is not surprising, as ultimately the matrix to be estimated is Z", which has nr parameters. However, our thcoretical analysis gives us a sample complexity that grows as Onnr²). Thus, there is scope for further research in order to develop (nr) sample complexity guarantees.
35


Reviews:
[{"review_id": "ZnJ2VMwMl1", "reviewer": "Reviewer_9TXS", "summary": "In practical settings, users are often picking between their favorite of a few items. As such, we learn about a user’s preferences via the comparisons they made. Given features about the users and the items, the objective is to recover the low-rank matrix of information given data points of the format (user, (item 1, item 2), favorite expected outcome). Specifically in this setting, the authors assume that the outcomes are noiseless, meaning that in fact the expected outcome is revealed. Another assumption made is that we are given an initial matrix which is in an epsilon-ball in the Frobenius norm around the ground-truth matrix. The authors provide theoretical analysis of the non-convex formulation of this problem and provide an algorithm to solve the problem under the assumptions made. The authors also empirically validate their algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for a thorough and positive review of our paper. Here, we address the couple of concerns you have raised. First, you mentioned \"it would be enlightening also to include different values for $r$, the rank of the underlying matrix.\" We agree. Below, we give a table highlighting the estimation error as a function of the rank and the number of samples. We observe that to get the same estimation error, the number of samples grows (approximately linearly) with the rank. In the revised version of the paper, we shall include this experimental result in the form of a heatmap, where this relationship is easy to observe. Second, you mentioned \"some improvements could be made in Sections 2.1 and 2.2 to properly motivate the problem setup.\" Thank you for this feedback, we shall improve these sections in the final version. Indeed, in the current form, some of the definitions may seem a bit arbitrary without further justification.\n\nTo answer your specific questions: \"Why should $Z^*$ be considered the ground truth matrix, rather than $X^*$? What is the motivation behind defining $Y^*$?\" Both these questions are related. The analysis crucially relies on analyzing symmetric matrices $Y$, which can be factored as $Y = ZZ^T$. To elaborate: we work with terms of the form $\\mathcal{D}(Y)$ (defined in (21)), and prove our concentration results for such terms; for these results, $Y$ must be a symmetric matrix. Fundamentally, however, we are trying to estimate the asymmetric matrix $X^* = U^*{V^*}^T$. To overcome this gap, we transform the problem of estimating $X^*$ to one of estimating $Y^*$ (a bigger, but equivalent matrix), which in turn is reduced to the problem of estimating $Z^*$ (because $Y^* = Z^* Z^{*T}$). Thus, ultimately, our loss function is in terms of $Z$ (see (12)). We briefly allude to the relation between these matrices in the first paragraph of Section 1.3, but we will reiterate these connections again in Section 2.1 of our revision. This particular transformation is first proposed in the paper of Zheng and Lafferty, and we borrow this idea from there. Finally, $A_1, A_2, \\ldots, A_m$ are i.i.d. random matrices, all of the same form as $A$ (described in equation (8)).\n\nWe now present a table highlighting the performance of our algorithm as a function of the underlying rank $r$ and the number of samples $m$. We generated a matrix of size 2000x3000 in the same manner as described in Section 5 of the paper. The numbers shown below are the estimation errors, averaged over ten independent runs.\n\n| Rank ↓ / Samples → | 30000         | 40000         | 50000         | 60000         | 70000         | 80000         | 90000         | 100000        |\n|--------------------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|\n| 2  | 0.0606 ± 0.0037 | 0.0500 ± 0.0077 | 0.0285 ± 0.0103 | 0.0208 ± 0.0071 | 0.0105 ± 0.0029 | 0.0097 ± 0.0073 | 0.0062 ± 0.0019 | 0.0044 ± 0.0005 |\n| 3  | 0.0800 ± 0.0015 | 0.0723 ± 0.0041 | 0.0595 ± 0.0086 | 0.0445 ± 0.0092 | 0.0353 ± 0.0080 | 0.0164 ± 0.0038 | 0.0120 ± 0.0035 | 0.0086 ± 0.0017 |\n| 4  | 0.0955 ± 0.0009 | 0.0919 ± 0.0020 | 0.0837 ± 0.0024 | 0.0715 ± 0.0057 | 0.0507 ± 0.0082 | 0.0384 ± 0.0117 | 0.0329 ± 0.0111 | 0.0170 ± 0.0080 |\n| 5  | 0.1081 ± 0.0005 | 0.1072 ± 0.0010 | 0.1025 ± 0.0025 | 0.0888 ± 0.0056 | 0.0744 ± 0.0039 | 0.0547 ± 0.0091 | 0.0414 ± 0.0108 | 0.0298 ± 0.0121 |\n| 6  | 0.1190 ± 0.0004 | 0.1196 ± 0.0008 | 0.1160 ± 0.0020 | 0.1076 ± 0.0030 | 0.0960 ± 0.0041 | 0.0787 ± 0.0053 | 0.0590 ± 0.0110 | 0.0423 ± 0.0111 |", "claims_and_evidence": "Yes, the claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods make sense. Specifically, the algorithm is supported by carefully written theorems.", "theoretical_claims": "I have checked the correctness of the claims made in the paper.", "experimental_designs_or_analyses": "The experimental design for the most part is sound and valid. However, it would be enlightening also to include different values for $r$, the rank of the underlying matrix.", "relation_to_broader_scientific_literature": "This paper addresses an open problem and provides an algorithm to solve it under some assumptions.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths:\n* The paper addresses an open problem, which is the matrix factorization from comparison data in the non-convex setting. Although a few simplifying assumptions are made in order to achieve this result, these are still meaningful steps in solving the more general problem. The algorithm’s dependence on the problem size is $O(nr^2 \\log n)$ where $n$ is the number of samples and $r$ is the rank of the matrix, and converges exponentially fast. The algorithm itself makes two projections in order to stay in the correct region of matrices, and shows that these projections maintain the correct invariance throughout the algorithm.\n* The analysis is overall clear and easy to follow. \n\nWeaknesses:\n* Although the paper is for the most part clear, some improvements could be made in Sections 2.1 and 2.2 to properly motivate the problem setup. In particular, why should $Z^*$ be considered the ground truth matrix, rather than $X^*$? Also, it would be nice to add some motivation for the following definitions such as $Y^*$ as well, and what role these matrices play later on. Furthermore, it would be helpful to the reader to state exactly the definition of $A_k$.", "other_comments_or_suggestions": "See above", "questions_for_authors": "See above", "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": "", "extra_scores": {}}, {"review_id": "6KzmQWxyQF", "reviewer": "Reviewer_aNun", "summary": "This paper focuses on the nonconvex learning problem in recommendation systems based on pairwise user comparison feedback, which has often been formulated as a convex optimization over utility matrices in prior literature. The authors propose a nonconvex matrix factorization approach to model pairwise comparisons as noisy evaluations based on the difference in latent utilities and to solve a maximum likelihood formulation over the latent factors using a nonconvex optimization approach. The main theoretical contribution is a proof that, under a warm start and in a sparse data regime, the negative log-likelihood objective exhibits a locally strong convexity–like behavior. This property guarantees that a projected gradient descent method converges exponentially fast to a solution equivalent to the ground truth. The paper provides detailed proofs employing matrix concentration inequalities (in particular, a matrix Bernstein inequality) and supports the theoretical findings with simulation results on synthetic data.\n\n## update after rebuttal\nI will keep the scores unchanged.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your time and effort in reviewing our paper and recognizing its theoretical contributions. We also acknowledge your suggestion that experiments on real-world datasets would further strengthen our work. While we generally agree, we have chosen not to include such experiments here for the following reasons.\n\nFirst, the primary focus of this paper is on analyzing the nonconvex optimization problem that arises in the context of learning from comparisons. The core challenge is to establish that the loss landscape has favorable structural properties, ensuring gradient descent quickly converges to the global minimum. To focus on this aspect, we assume a low-rank matrix model for utilities and an oracle choice model, both of which are widely accepted in the recommender systems literature. While real-data experiments could complement our results, they would also introduce confounding factors such as how well the assumed model fits reality and the extent of noise in the data. To avoid this confusion, we work exclusively with synthetic data, where these factors do not crop up. Through our experiments, we demonstrate that some of the assumptions needed for the theoretical analysis (warm start, projection step) are not necessary in practice, which improves the practical viability of this method. Our work demonstrates that learning personalized preferences from comparison data is both statistically efficient (low sample complexity) and computationally efficient (exponentially fast gradient descent).\n\nSecond, we are not the first to study the problem of learning personalized rankings from comparison data; both Rendle et al. (2009) and Park et al. (2015) study this very problem. They use the same factorized optimization approach as our work and test it on real-world datasets. In terms of the method, therefore, there is no substantial difference between this prior work and ours. However, before our work, these methods were essentially heuristics. We provide a solid theoretical foundation for why gradient descent on factorized matrices leads to good solutions, a nontrivial result given the nonconvexity of the problem. Despite extensive prior work on nonconvex optimization—especially in matrix completion—existing results do not apply to the learning-from-comparisons setting. Our work addresses this open problem. It is also useful to draw a parallel with the research on classical matrix completion: empirical success of matrix factorization for recommendations (Mnih & Salakhutdinov, 2007; Koren et al., 2009) preceded theoretical justification, which emerged gradually through successive refinements.\n\nFinally, an important limitation in the field is the lack of explicit comparison datasets. To the best of our knowledge, there is no dataset in the regime of recommender systems where users are \\textit{explicitly} asked to compare two items according to their preference. Note that both Rendle et al. (2009) and Park et al. (2015) \\textit{infer} comparisons from other forms of data. In Rendle et al. (2009), items that a user has viewed/purchased are interpreted to be more preferred than those that the user has not viewed. In Park et al. (2015), a user is said to have preferred one item over another if it rates the first item higher than the second. While these inferred comparisons have their merits, our work suggests that explicitly collecting comparison data could also be an effective approach; it could potentially be more effective learning from ratings. Curating such a dataset and testing this hypothesis is an important direction for future work. In the absence of such datasets, however, we would have to resort to inferring comparisons from ratings/views, as done by prior work. Doing so would merely amount to reproducing the results of Rendle et al. (2009) and Park et al. (2015), given the large similarity of the methods. Thus, we have not performed such experiments here.\n\nWe hope this rebuttal helps you better appreciate the contribution of our paper. We shall be happy to answer any other questions you may have.", "claims_and_evidence": "* **Claims:** The key claim of this papaer is that the nonconvex formulation for learning from sparse comparison data exhibits (restricted) strong convexity in a neighborhood of the true solution, which guarantees exponential convergence of projected gradient descent given a warm start. Additional claims include sample complexity bounds and explicit dependence on parameters such as the incoherence and condition number. \n\n* **Evidence:** The authors back these claims with detailed theoretical derivations (Theorem 3.1, supporting Lemmas 4.1–4.7 and their proofs in the appendix) accompanied by simulation experiments that validate the exponential convergence rate. \n\nAll the claims are well motivated and supported by rigorous proofs.", "methods_and_evaluation_criteria": "* **Methods:** The authors propose a projected gradient descent method with two projection steps: one to enforce incoherence of the iterates and one to remove the shift invariance (due to comparing only differences).\n* **Evaluation Criteria:** The theoretical results are evaluated using concentration inequalities and error bounds derived via the matrix Bernstein inequality. The experimental evaluation measures convergence speed via normalized Frobenius norm errors over iterations.", "theoretical_claims": "I did my best to review the derivation of key intermediate results (particularly Lemma 4.3, 4.4, 4.5) under the stated assumptions, and found the arguments to be mathematically sound given the stated assumptions.", "experimental_designs_or_analyses": "The experiments use synthetic data in both low- and high-dimensional settings, simulating pairwise comparisons using a known ground-truth matrix. The simulation results confirm that, when using the recommended step-size and sample complexity, the algorithm exhibits linear (exponential) convergence as predicted by the theory.\n\nWhile the synthetic experiments provide compelling evidence for the theoretical findings, given that recommender systems are highly practical applications and considering that most theoretical works mentioned in this paper have been tested on real-world datasets, the absence of experiments on real-world comparison data is a potential concern.", "relation_to_broader_scientific_literature": "The paper is situated at the intersection of nonconvex matrix factorization and learning from comparison data. It represents an important extension of [1], addressing the scalability issues of previous works [2,3] on large-scale datasets.\n\n[1] Negahban, S., Oh, S., Thekumparampil, K. K., and Xu,J. Learning from comparisons and choices. Journal of Machine Learning Research, 19(40):1–95, 2018.\n\n[2] Park, D., Neeman, J., Zhang, J., Sanghavi, S., and Dhillon, I. Preference completion: Large-scale collaborative ranking from pairwise comparisons. In Proceedings of the 32nd International Conference on Machine Learning, 2015.\n\n[3] Rendle, S., Freudenthaler, C., Gantner, Z., and Schmidt Thieme, L. BPR: Bayesian personalized ranking from implicit feedback. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, 2009.", "essential_references_not_discussed": "Based on my knowledge, the related work discussed in this paper has comprehensive coverage and adequately demonstrates the paper's contributions.", "other_strengths_and_weaknesses": "The theoretical guarantees provided in this paper for the nonconvex formulation—especially in the sparse data regime—are a clear and noteworthy contribution to studies on pairwise comparisons in recommendation systems. However, while the theoretical aspects are strong, the lack of empirical validation on real-world comparison datasets somewhat limits the practical implications of the work, particularly considering the applied nature of recommender systems.", "other_comments_or_suggestions": "It is recommended that the authors demonstrate empirical validation on real-world datasets. If existing datasets do not meet the assumptions of this paper, or if there are other reasons that only synthetic experiments can be conducted, please explicitly explain these limitations.", "questions_for_authors": "N/A", "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": "", "extra_scores": {}}, {"review_id": "RmT7oGwWdz", "reviewer": "Reviewer_Rcd3", "summary": "This paper addresses comparison-based recommendations using non-convex matrix factorization optimization. While this approach is more efficient than convex optimization, it remains challenging. The authors observe that although finding the global minimum may be difficult, the non-convex function behaves convexly near the true solution", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and appreciation of our writing and theoretical analysis. We understand your concerns regarding the warm start and noiseless assumptions and address them below. We also address your questions about with the projection step.\n\nBefore addressing your concerns, we restate our main result: in a neighborhood of the ground-truth solution, the loss function is strongly convex. Thus, when initialized within this neighborhood, projected gradient descent converges linearly to the ground truth. This is the first such result for the learning from comparisons problem. In fact, the main takeaway of our paper is a very practical message: it is possible to learn personalized user preferences from comparison data in a computationally efficient and statistically efficient manner. As you noted, our work serves as a baseline for future theoretical studies to establish guarantees with cold starts and noisy data. We hope this will be the case and are actively working toward such generalizations, though these extensions are nontrivial. The challenges can be seen in the matrix completion literature, where initial assumptions, similar to ours, were later relaxed by follow-up work (see Section 1.1 of our paper). However, broadly speaking, these assumptions are largely for analytical convenience; they are not needed in practice. Our simulations aim to highlight this fact.\n\nRegarding the projection step: we need it to ensure that iterates remain in the set of incoherent matrices; this, in turn, is necessary for our theoretical analysis. If iterates remain incoherent naturally via gradient descent, projection is unnecessary. Our simulations (Figures 1a, 1c) confirm that vanilla gradient descent also converges to the true solution. The strong overlap of error curves for projected and vanilla gradient descent indicates that the projection step hardly perturbs the iterates. In matrix completion, early theoretical works assumed projection steps or regularization to maintain incoherence, but later research showed these were not necessary. Ma et al. (2020) demonstrated that gradient descent has implicit regularization, leading to convergence without explicit projection. Extending this implicit regularization result to learning from comparisons is a promising research direction.\n\nThe warm start assumption ensures initialization in a strongly convex region, allowing us to prove linear convergence of gradient descent. However, our experiments (Figures 1a, 1c) indicate that this assumption is not needed in practice, as even random initialization leads to linear convergence. This phenomenon has also been observed in matrix completion. Early work (2010–2015) on nonconvex matrix factorization assumed a warm start to establish theoretical guarantees, which was later relaxed by Ge et al. (2016–2017), who showed that all local minima are global. Since gradient descent finds local minima, this explains why warm starts are not necessary in practice. However, their analysis relies on quadratic loss functions, making extensions to our setting nontrivial. Furthermore, global analyses of matrix completion do not provide convergence rates, whereas our work guarantees linear convergence within a specific region.\n\nThe noiseless assumption is primarily for analytical convenience; our algorithm can be applied directly to noisy data without modification. This assumption enables us to show exact convergence to the ground truth. Without it, convergence can only be guaranteed up to some statistical estimation error. Analyzing the noisy setting is an important but separate research problem that will likely build on the key ideas introduced in our work. While our original submission lacked simulations on noisy data, we have since conducted extensive experiments showing that performance degrades gracefully with noise (noise in the scores and noisy comparisons). Specifically, when adding a small noise matrix to the ground-truth low-rank matrix, gradient descent converges to a point where the residual error is nearly equal to the norm of the noise matrix. This suggests our method effectively learns the best low-rank approximation of the noisy ground truth. We will include these results in the revised paper. (Unfortunately, we are not able to convey meaningful results through markdown tables here.)\n\nIn summary, we assume a warm start, noiseless observations, and the projection step to simplify the analysis. However, our experiments suggest these assumptions are not necessary in practice. Even without them, simple gradient descent converges efficiently, making learning from comparisons a practical and robust approach. We hope this rebuttal (along with the other rebuttals) addresses the major concerns you have of our paper. We shall be happy to answer any other questions you may have.", "claims_and_evidence": "This work begins optimization with a noiseless warm start, which seems unlikely to be practical in industrial settings or real-world datasets. Can the authors also compare results using naive gradient descent versus the projected method?", "methods_and_evaluation_criteria": "The authors test their approach by simulating a random ground truth matrix drawn from a normal distribution, justified by the presence of popularity bias in user preferences. Figure 1 shows that convergence becomes more linear for large datasets.", "theoretical_claims": "I reviewed the theoretical proofs at the board level. The authors present a clear and logical flow to justify their approach.", "experimental_designs_or_analyses": "Figure 1 summarizes the simulation results, which align well with the theoretical hypothesis and proofs.", "relation_to_broader_scientific_literature": "This work proposes a probabilistic model to address comparison-based recommendation using a non-convex loss. One key assumption is that the rating matrix is noise-free or that optimization begins with a warm start. While this assumption may limit real-world applicability, the work can serve as a solid baseline for future studies to explore probabilistic approaches with cold starts and noisy data, which are more common in both industry and academia. Additionally, given the ground-truth matrix's structure—representing user preferences between two items—future research could extend the model to support k-item comparisons.", "essential_references_not_discussed": "Although the paper references prior work that informs its approach, it lacks a comparison with other baseline methods to evaluate its results.", "other_strengths_and_weaknesses": "1. The paper is well-written and easy to follow.  \n2. It provides solid theoretical proofs.  \n3. The paper's first assumption is that the rating matrix is noiseless. Given that most real-world recommendation datasets are noisy, or at least somewhat, this assumption may not be realistic, particularly in industry settings.  \n4. The results in Figure 1 do not account for other hyperparameters, such as the projection step.", "other_comments_or_suggestions": "no", "questions_for_authors": "Most of the theoretical proofs assume a non-noisy setting. I wonder how introducing a hyperparameter to adjust for noise in the ground truth matrix would affect the results in Figure 1.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper focuses on the nonconvex learning problem in recommendation systems based on pairwise user comparison feedback, which has often been formulated as a convex optimization over utility matrices in prior literature. The authors propose a nonconvex matrix factorization approach to model pairwise comparisons as noisy evaluations based on the difference in latent utilities and to solve a maximum likelihood formulation over the latent factors using a nonconvex optimization approach. The main theoretical contribution is a proof that, under a warm start and in a sparse data regime, the negative log-likelihood objective exhibits a locally strong convexity–like behavior. This property guarantees that a projected gradient descent method converges exponentially fast to a solution equivalent to the ground truth. The paper provides detailed proofs employing matrix concentration inequalities (in particular, a matrix Bernstein inequality) and supports the theoretical findings with simulation results on synthetic data. 


Strengths are: 1) The paper addresses an open problem, which is the matrix factorization from comparison data in the non-convex setting; 2) The theoretical guarantees provided in this paper for the nonconvex formulation—especially in the sparse data regime—are a clear and noteworthy contribution to studies on pairwise comparisons in recommendation systems; 3) The analysis is overall clear and easy to follow; 4) The paper is well-written and easy to follow. One major concern is that the paper's first assumption is that the rating matrix is noiseless. Given that most real-world recommendation datasets are noisy, or at least somewhat, this assumption may not be realistic, particularly in industry settings. Overall, although a few simplifying assumptions are made in order to achieve this result, these are still meaningful steps in solving the more general problem.
Decision: Accept (poster)