Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization

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.

Before 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.

Regarding 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.

The 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.

The 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.)

In 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.

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.

First, 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).

Second, 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.

Finally, 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 explicitly asked to compare two items according to their preference. Note that both Rendle et al. (2009) and Park et al. (2015) 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.

We hope this rebuttal helps you better appreciate the contribution of our paper. We shall be happy to answer any other questions you may have.

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.

To 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)).

We 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.