Algorithms for Ordinal Learning of Line Metric Spaces

Algorithms relying on Ordinal Informations to retrieve embedding have seen rise in usage in recent times due to the increase of popularity of automated analyses involving human generated opinions. In addition to this applications have been proven to also be successful in the field of ranking where the use of pairwise comparisons improves both efficiency and accuracy in noisy settings. In this document, we will first explore an algorithm for solving the LLOC problem in one dimension by proving its time complexity and, more importantly, the accuracy guarantees under the assumption that all the constraints between points are present in the constraint set. We will then proceed to conjecture a variation of such algorithm capable to learn multidimensional embeddings under the assumption that the base algorithm can handle instances where the the number of constraints is not cubic. Lastly we will assess the capabilities of such algorithm in both Ordinal Embedding and Metric Learning scenarios.