Research map / Learning theory and algorithms / Prediction and decision losses
Active Seriation: Efficient Ordering Recovery with Statistical Guarantees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ASII, a simple polynomial-time active insertion algorithm with backtracking for seriation from noisy pairwise similarity queries, with exponential error bounds and matching minimax lower bounds in the SNR Δ²T/(σ²n) ≍ ln n phase transition.
Problem
Recovering an unknown ordering of n items from adaptively chosen noisy pairwise similarity observations, where similarities follow a pre-Robinson (permuted Robinson) matrix structure.
Approach
Insert items one by one into a growing ordered list using a noisy three-way local test and a binary search with backtracking, using only O(T/(n log k)) samples per test so that occasional wrong tests are corrected later; the procedure needs no knowledge of sigma or the minimal gap.
Key results
- Upper bound: error probability at most exp(-Δ²T/(2400σ²n)) whenever Δ²T/(σ²n) ≥ c0 ln n, without knowing σ or Δ.
- Lower bound: no algorithm succeeds with vanishing error when Δ²T/(σ²n) ≲ ln n (error ≥ 1/2), and any algorithm has error at least exp(-8Δ²T/(σ²n)) in the recovery regime, giving minimax-optimal sample complexity T* ≍ σ²n ln n/Δ².
- In simulations ASII beats naive insertion across four scenarios and is stable on non-Toeplitz matrices where batch Adaptive Sampling and Spectral Seriation sometimes fail, though it trails batch methods on the Toeplitz scenario.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use backtracking during noisy insertion search instead of naive insertion without backtracking (ablation) | ASII · Synthetic seriation scenarios 1–4 | probability of error | Helped |
| Use ASII rather than batch seriation methods | Seriation methods on Toeplitz scenario 1 · Synthetic seriation scenario 1 (Toeplitz) | probability of error | Hurt |
| Use ASII rather than batch seriation methods | Seriation methods on non-Toeplitz scenarios · Synthetic seriation scenarios 2–4 (non-Toeplitz) | probability of error | Helped |
| Concentrate queries adaptively rather than observe the full similarity matrix in a batch | ASII versus batch approaches · Active seriation from scratch | number of observations for recovery: O(n^2) -> T \gtrsim (\sigma/\Delta)^2 n \ln n | Helped |
| Require the signal-to-noise ratio to exceed the logarithmic threshold | ASII · Active seriation from scratch | probability of error: \frac{\Delta^2 T}{\sigma^2 n} \le c_1 \ln n: p_{M,T} \ge 1/2; \quad \frac{\Delta^2 T}{\sigma^2 n} \ge c_0 \ln n: p_{M,T} | Helped |
| Use an insertion-and-validation extension with resolution parameter \tilde\Delta | ASII · Arbitrary pre-R matrices | probability of correct ordering of a \tilde\Delta-maximal subset: 1 - \exp\!\left(-\, c' \tfrac{\tilde\Delta^2 T}{\sigma^2 \tilde n}\right) | Helped |
Surprising findings
- ASII matches minimax-optimal rates even though the lower bounds hold only for Toeplitz matrices, so heterogeneous non-Toeplitz structure incurs no statistical cost.
- On the Toeplitz scenario, ASII underperforms the batch methods Adaptive Sampling and Spectral Seriation.
Limitations
- Individual tests are deliberately unreliable (constant success probability), so guarantees rely on constants that may be large for the iterative active procedure.
- Analysis is for uniform minimal-gap separation; the extension to general pre-R matrices returns only a subset of items.
- Lower bound for the regime Δ²T/(σ²n) ≳ ln n is only exponential-rate matched; open whether it extends to the full complementary regime.
Experimental setup
Datasets: synthetic Robinson matrices single-cell RNA-seq human primordial germ cells
Benchmarks: synthetic seriation scenarios (n=10, T=10000) single-cell RNA-seq similarity matrix reordering
Metrics: probability of error exact recovery probability
Baselines: Adaptive Sampling Spectral Seriation naive ASII without backtracking
Builds on: Adaptive Sampling seriation noisy binary search thresholding bandits
Closest papers by meaning
- Active preference learning for ordering items in- and out-of-sample (NeurIPS 2024 · similarity 0.84)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.83)
- Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity (ICML 2025 · similarity 0.82)
- Are Greedy Task Orderings Better Than Random in Continual Linear Regression? (NeurIPS 2025 · similarity 0.82)
- Active Set Ordering (NeurIPS 2024 · similarity 0.82)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.