Finite Sample Prediction and Recovery Bounds for Ordinal Embedding
The goal of ordinal embedding is to represent items as points in a low-dimensional Euclidean space given a set of constraints like "item i is closer to item j than item k". Ordinal constraints like this often come from human judgments. The classic approach to solving this problem is known as non-metric multidimensional scaling. To account for errors and variation in judgments, we consider the noisy situation in which the given constraints are independently corrupted by reversing the correct constraint with some probability. The ordinal embedding problem has been studied for decades, but most past work pays little attention to the question of whether accurate embedding is possible, apart from empirical studies. This paper shows that under a generative data model it is possible to learn the correct embedding from noisy distance comparisons. In establishing this fundamental result, the paper makes several new contributions. First, we derive prediction error bounds for embedding from noisy distance comparisons by exploiting the fact that the rank of a distance matrix of points in R d is at most d + 2. These bounds characterize how well a learned embedding predicts new comparative judgments. Second, we show that the underlying embedding can be recovered by solving a simple convex optimization. This result is highly non-trivial since we show that the linear map corresponding to distance comparisons is non-invertible, but there exists a nonlinear map that is invertible. Third, two new algorithms for ordinal embedding are proposed and evaluated in experiments.
This paper addresses the problem of finding potentially low dimensional embedding from distance comparisons known as ordinal embedding. The authors provide novel generalization bounds based on finite quantitiesfor ordinal embedding, as far as I understand the fiel, this is novel. They also study a particular model based on maximum likelihood estimation where they justify that a correct embedding can be recevered. An experimental evaluation is provided on synthetic data that includes 2 new algorithms. 
Pros: -Interesting and a priori novel theoretical analysis for Ordinal Embedding Cons: -Paper sometimes hard to follow where some parts deserve more attention -The noise model the authors propose to study is not clear -Experimental evaluation limited to synthetic data with comparison to only one existing method  Overall: Good and interesting theoretical results that are novel for this topic. But the paper lacks of discussion/precision on some parts and the practical aspects are relatively limited.  Comments:  -The bounds proposed in this paper appear to be novel and are interesting. I wonder wether there exists a link with U-statistics that can be used to justify that a true risk can be efficiently estimated  by considering a random subset from all the possible triplets. Check the following reference for example: *S. Clemencon, I. Colin and A. Bellet. Scaling-up Empirical Risk Minimization: Optimization of Incomplete U-statistics. Journal of Machine Learning Research 17(76):1-36, 2016.  The results in Section 4 are interesting, but the authors do not discuss their implication from a practical standpoint. We do not know if they are purely theoretical to justify the consistency of the method with no ambition to deduce some practical algorithms or if there are some perspectives to develop new well-founded approach to recover the embedding.  -The authors mention the presence of a noise model but I was unable to find a description or discussion about this noise model in the paper. If the authors have in mind a classic Gaussian noise, this must be clearly mentioned and discussed accordingly in the paper. In the supplementary caption of Figure 3 page 14, I was not able to understand what means \alphaM for describing the noise since \alpha and M have not been introduced before.  ==After rebuttal == Ok for the answer. You may anyway specify more clearly your point here. Since $f$ takes as argument the distance between elements in the triplet (which is reasonable for defining the true labeling), one could think that the noise may depend on this distance which is not what you meant here.   -The experimental setup is limited to synthetic data but i would have been interesting to study the behavior of the approach on real data.  The notion of prediction error is not explicitly mention in the setup, I guess that this corresponds to the evaluation over the test set of the difference between the risk R  in Section 2 of the learned model and the true R defined. If so, I think that an additional experiment showing the accuracy obtained on the test set by counting the number of times the distances between in each triplet are correctly ordered could be interesting to assess if the embedding is relevant in addition to a good estimation of the true matrix G^*.  I am not completely convinced by the approach "Nuclear Norm PGD Debiased" since it exhibits a performance similar or worse than "Nuclear PGD". Anyway the two proposed algorithms are presented quickly is Section 5. However, they deserve more discussion. In particular, the remark on performance gap between convex and non convex solutions at the end of Section 5.  The algorithms are not sufficiently presented and their properties are not sufficiently discussed. I think that the authors could move a part of the proofs of justifications of Section 4 into the supplementary material to have more place to discuss other aspects of the paper.  Finally, the experimental section seems disconnected from the results presented in Section 4.  Trying to assess in practice the quantities presented in this section from the model obtained in the experiments could strengthen the global coherence of the paper.  -The paper lacks of a general conclusion that could present the perspective and replace the work with respect to existing work in the state of the art.  At the end, it is difficult for me to really assess the quality of the contribution in comparison to existing work in the literature and I think the paper misses a deeper discussion on existing work.  -Other remarks: *l51: has a a non-empty -> has a non-empty *l77: in the definition of all the triplets, T, you may need to add the constraint: i < j  *l89: If you assume that the set of triplets T is infinite, the notation \frac{1}{T} is not accurate in the definition of the expectation *l98: later we will link define $\ell$ -> choose between link and define