Active seriation aims at recovering an unknown ordering of $n$ items by adaptively querying pairwise similarities. The observations are noisy measurements of entries of an underlying $n$ x $n$ permuted Robinson matrix, whose permutation encodes the latent ordering. The framework allows the algorithm to start with partial information on the latent ordering, including seriation from scratch as a special case. We propose an active seriation algorithm that provably recovers the latent ordering with high probability. Under a uniform separation condition on the similarity matrix, optimal performance guarantees are established, both in terms of the probability of error and the number of observations required for successful recovery.

Furthermore, their guarantees only hold in the realizable setting, requiring thatf is itself a size-s decision tree (i.e.opts = 0). There has been extensive work in the learning theory literature on learning the concept class of decision trees [EH89, Blu92, KM93, OS07, GKK08, HKY18, CM19]. This follows by combining the boundsInf(T) logs (see e.g.