Active Seriation
James Cheshire, Yann Issartel
We consider the problem of active seriation, in which the learner must order $n$ items from $T$ sequentially observed pairwise similarities. Items are ordered according to their pairwise similarities: two items sharing a high similarity are expected to be close in the ordering, and vise-versa. At each round, the learner selects a pair $i,j$ and receives a noisy observation of the similarity between $i$ and $j$. After $T$ rounds, the learner returns an ordering of the $n$ items, whose accuracy is measured by the probability of error of not recovering the true ordering. We characterize the minimax rates of this problem when a minimal gap $\Delta$ separates pairwise similarities, and we provide a polynomial time algorithm achieving this rate, adaptively to the unknown parameter $\Delta$.