Active Seriation: Efficient Ordering Recovery with Statistical Guarantees
James Cheshire, Yann Issartel · 2026
Read Active Seriation: Efficient Ordering Recovery with Statistical Guarantees by James Cheshire, Yann Issartel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15336.txt.
Introduction
Cheshire and Issartel tackle active seriation, the task of restoring a hidden order to a set of items. The method queries pairwise similarities one by one and adapts as answers arrive. Observations are noisy reads of a permuted Robinson matrix that encodes the true order. Their algorithm may start from partial order knowledge or from scratch. Under a uniform gap condition on the similarity matrix, it recovers the order with high probability. The guarantees cover both error rates and the number of queries needed.
Catalog record
| CREATOR | James Cheshire, Yann Issartel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132019 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.15336
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Active Seriation: Efficient Ordering Recovery with Statistical Guarantees James Cheshire, Yann Issartel Abstract Active seriation aims at recovering an unknown ordering of n n items by adaptively querying pairwise similarities. The observations are noisy measurements of entries of an underlying n × n n\times 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. 1 Introduction The seriation problem involves ordering n items based on noisy measurements of pairwise similarities. This reordering problem originates in archaeology, where it was used for the chronological dating of graves [ 39 ] . More recently, it has found applications in data science across various domains, including envelope reduction for sparse matrices [ 2 ] , read alignment in de novo sequencing [ 21 , 36 ] , time synchronization in distributed networks [ 14 , 24 ] , and interval graph identification [ 19 ] . In many of these settings, pairwise measurements can be made in an adaptive fashion, leveraging information from previously chosen pairs. Motivated by these applications, we study the problem of recovering an accurate item ordering from a sequence of actively selected pairwise measurements. The classical seriation problem has attracted substantial attention in the theoretical literature [ 1 , 18 , 31 , 23 , 8 , 29 ] . In this line of work, the learner receives a single batch of observations, whereas in the active setting considered in this paper, the algorithm can adaptively select which pairs to observe; to the best of our knowledge, this active seriation setting has not been previously analyzed. Related problems include adaptive ranking and sorting under noisy observations [ 30 , 6 , 28 ] . However, these problems typically rely on pairwise comparisons (e.g., is item i preferred to item j ?) to infer a total order. In contrast, seriation builds on pairwise similarity scores that encode proximity in the underlying ordering. This distinction leads to different statistical and algorithmic challenges. Problem setup. In the seriation paradigm, we assume the existence of an unknown symmetric matrix M representing pairwise similarities between a collection of n items. The matrix M is structured so that the similarities M_{ij} are correlated with an unknown underlying ordering of the items, which is encoded by a permutation \pi=(\pi_{1},\ldots,\pi_{n}) of [n] . The similarity M_{ij} between items i and j tends to be large when their positions \pi_{i} and \pi_{j} are close, and small when they are far apart. To model this structure formally, the literature assumes that M is a Robinson matrix whose rows and columns have been permuted by the latent permutation \pi [ 18 , 37 , 31 , 23 ] ; see Section 2.1 for a formal presentation. We consider a general framework in which the algorithm may be initialized with partial information on the latent ordering \pi . Specifically, it can be provided with a correct ordering of a subset of the items that is consistent with \pi . This setting includes seriation from scratch as the special case where no such information is given initially. The algorithm adaptively selects pairs of items and observes noisy measurements of their similarities. A total of T such observations are collected, and the noise is controlled by an unknown parameter \sigma . The goal is to recover the latent ordering \pi of the n items from these T observations. We evaluate the performance of an estimator \hat{\pi} by its probability of failing to identify \pi . See Section 2 for details. Contribution. We introduce Active Seriation by Iterative Insertion (ASII), an active procedure for estimating the ordering \pi . Unlike most existing seriation methods, which are non-active, ASII is remarkably simple, runs in polynomial time, and yet achieves optimality guarantees both in terms of error probability and sample complexity. In the general framework considered in this paper, we analyze the performance of ASII and establish exponential upper bounds on its probability of error. In the special case of seriation from scratch, where no prior ordering information is available, we provide a sharp characterization of the statistical difficulty of ordering recovery over the class of similarity matrices with minimal gap \Delta between adjacent coefficients. This difficulty is governed by the signal-to-noise ratio (SNR) of order \Delta^{2}T/(\sigma^{2}n) , which can be interpreted as the number of observations per item, T/n , multiplied by the SNR per observation, (\Delta/\sigma)^{2} . Our results identify a phase transition at the critical level \textup{SNR}\asymp\ln n : below this threshold, ordering recovery is information-theoretically impossible, while above it, ASII achieves recovery with a probability of error that decays exponentially fast with the SNR. Moreover, we show that no algorithm can achieve a faster decay rate, establishing optimality in this regime. Finally, we illustrate the performance of ASII through numerical experiments and a real-data application. 1.1 Related work Classical seriation. The non-active seriation problem was first addressed by [ 1 ] in the noiseless setting, using a spectral algorithm. Subsequent works analyzed this approach under noise [ 18 , 23 , 34 ] , typically relying on strong spectral assumptions to establish statistical guarantees. More recent contributions proposed alternative polynomial-time algorithms with guarantees under different and sometimes weaker assumptions [ 31 , 23 , 8 , 29 ] . Our analysis falls within the line of work on Lipschitz-type assumptions [ 23 , 29 ] , as our \Delta -separation condition can be viewed as a lower Lipschitz requirement. Statistical-computational gaps. Prior studies have suggested statistical–computational gaps in the non-active seriation problem [ 23 , 8 , 5 ] , where known polynomial-time algorithms fall short of achieving statistically optimal rates under certain noise regimes or structural assumptions. While some of these gaps have recently been closed [ 29 ] , the resulting algorithms tend to be complex and may not scale well in practice. In contrast, in the active setting, we show that a simple and computationally efficient algorithm achieves statistically optimal performance. Bandit models. In classical multi-armed bandits (MAB) [ 7 ] , each arm yields independent rewards, and the goal is to maximize cumulative reward or identify the best arm. In contrast, in active seriation, each query (i,j) measures the similarity between two interdependent items, and all measurements must be consistent with a single latent ordering. This interdependence prevents a direct application of standard MAB algorithms such as UCB or Thompson Sampling, which treat arms as independent and do not exploit structural relationships between them. Algorithmically, our approach is related to noisy binary search and thresholding bandits [ 17 , 32 , 3 , 35 , 15 , 11 , 12 ] , which rely on adaptive querying under uncertainty. However, these methods operate on low-dimensional parametric models, whereas seriation involves a combinatorial ordering that must remain globally consistent across item pairs. Active ranking. A related but distinct problem is active