Convergence rates for ordinal embedding
We prove optimal bounds for the convergence rate of ordinal embedding (also known as non-metric multidimensional scaling) in the 1-dimensional case. The examples witnessing optimality of our bounds arise from a result in additive number theory on sets of integers with no three-term arithmetic progressions. We also carry out some computational experiments aimed at developing a sense of what the convergence rate for ordinal embedding might look like in higher dimensions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
LORE: Jointly Learning the Intrinsic Dimensionality and Relative Similarity Structure From Ordinal Data
Learning the intrinsic dimensionality of subjective perceptual spaces such as taste, smell, or aesthetics from ordinal data is a challenging problem. We introduce LORE (Low Rank Ordinal Embedding), a scalable framework t…
Estimation of perceptual scales using ordinal embedding
In this paper, we address the problem of measuring and analysing sensation, the subjective magnitude of one's experience. We do this in the context of the method of triads: the sensation of the stimulus is evaluated via …
CORE: Learning Consistent Ordinal REpresentations for Image Ordinal Estimation
The goal of image ordinal estimation is to estimate the ordinal label of a given image with a convolutional neural network. Existing methods are mainly based on ordinal regression and particularly focus on modeling the o…
regressionFast Stochastic Ordinal Embedding with Variance Reduction and Adaptive Step Size
Learning representation from relative similarity comparisons, often called ordinal embedding, gains rising attention in recent years. Most of the existing methods are based on semi-definite programming (\textit{SDP}), wh…
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 in the form of distance comparisons like "item $i$ is closer to item $j$ than item $k$". Ordin…
Prediction