Convergence rates for ordinal embedding
This work addresses a theoretical problem in machine learning for researchers in dimensionality reduction and ordinal data analysis, but it is incremental as it focuses on the 1D case and extends known results.
The authors tackled the problem of determining optimal convergence rates for ordinal embedding in one dimension, proving tight bounds and using examples from additive number theory to demonstrate optimality, while also exploring computational experiments for higher dimensions.
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.