# Active Seriation: Efficient Ordering Recovery with Statistical Guarantees

arXiv: https://arxiv.org/abs/2603.15336 · HTML: https://mlsanity.com/paper/2603.15336/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 16 Mar 2026.

## Builds on (most cited first, 15 of 15)

- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [Maximum Selection and Ranking under Noisy Comparisons](https://mlsanity.com/paper/1705.05366/) (2017)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [The Influence of Shape Constraints on the Thresholding Bandit Problem](https://mlsanity.com/paper/2006.10006/) (2020)
- [On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons](https://mlsanity.com/paper/1909.03194/) (2019)
- [Optimal Bounds for Noisy Sorting](https://mlsanity.com/paper/2302.12440/) (2023)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Deterministic and Probabilistic Binary Search in Graphs](https://mlsanity.com/paper/1503.00805/) (2015)
- [Active Ranking of Experts Based on their Performances in Many Tasks](https://mlsanity.com/paper/2306.02628/) (2023)
- [Reconstruction of Line-Embeddings of Graphons](https://mlsanity.com/paper/2007.06444/) (2020)
- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [Reconstructing Latent Orderings by Spectral Clustering](https://mlsanity.com/paper/1807.07122/) (2018)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Active Bipartite Ranking with Smooth Posterior Distributions](https://mlsanity.com/paper/2602.24263/) (2026)

## Built on by (most cited first, 1 of 1)

- [From Cone Geometry to Monge Structure: Local Defects and Global Regret in High-Dimensional Optimal Transport](https://mlsanity.com/paper/2606.04695/) (2026)

## Abstract (arXiv)

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.