Source-linked AI summary
Noisy Sorting Without Resampling
Mark Braverman, Elchanan Mossel
TL;DR
The paper studies noisy sorting without resampling, where a single noisy comparison is available for each pair and the objective is to find an optimal ranking. It develops a randomized insertion and dynamic-programming approach that solves the problem with high probability while keeping optimal rankings close to the true order. The guarantees include polynomial running time and O_γ(n log n) sampling complexity, with a stated generalization beyond independent comparisons.
Problem
Noisy Sorting Without Resampling asks for an optimal ranking from noisy pairwise comparisons without repeated queries, a setting motivated by sports and expert rankings.
Method
The paper proves that optimal rankings are close to the true order, then uses insertion and dynamic programming to find an optimal solution efficiently.
Results
The randomized algorithm finds an optimal NSWR solution in time n^O((β+1)γ^-4) except with probability n^-β, with sampling complexity C n log n.
Takeaways & Limitations
Every optimal ranking is close to the true order with high probability, supporting efficient recovery of a near-true ranking despite noisy comparisons.
Takeaways & Limitations
The stated model assumes independent comparison errors, although the proofs can be modified when conditional correctness probabilities remain at least p.
Abstract
from arXiv · showhide
In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order $a_{π(1)} < ... < a_{π(n)}$ where $π$ is a permutation on $n$ elements. The input is the status of $n \choose 2$ queries of the form $q(a_i,x_j)$, where $q(a_i,a_j) = +$ with probability at least $1/2+\ga$ if $π(i) > π(j)$ for all pairs $i \neq j$, where $\ga > 0$ is a constant and $q(a_i,a_j) = -q(a_j,a_i)$ for all $i$ and $j$. It is assumed that the errors are independent. Given the status of the queries the goal is to find the maximum likelihood order. In other words, the goal is find a permutation $σ$ that minimizes the number of pairs $σ(i) > σ(j)$ where $q(σ(i),σ(j)) = -$. The problem so defined is the feedback arc set problem on distributions of inputs, each of which is a tournament obtained as a noisy perturbations of a linear order. Note that when $\ga < 1/2$ and $n$ is large, it is impossible to recover the original order $π$. It is known that the weighted feedback are set problem on tournaments is NP-hard in general. Here we present an algorithm of running time $n^{O(γ^{-4})}$ and sampling complexity $O_γ(n \log n)$ that with high probability solves the noisy sorting without re-sampling problem. We also show that if $a_{σ(1)},a_{σ(2)},...,a_{σ(n)}$ is an optimal solution of the problem then it is ``close'' to the original order. More formally, with high probability it holds that $\sum_i |σ(i) - π(i)| = Θ(n)$ and $\max_i |σ(i) - π(i)| = Θ(\log n)$. Our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts.
1 Introduction
The paper studies noisy sorting without resampling, where pairwise comparisons provide a noisy view of an unknown order and the goal is to find an optimal ranking. It develops a high-probability polynomial-time algorithm, low sampling complexity, and proximity guarantees for optimal rankings.
- 1.2 Related Sorting Models and Results: The problem is difficult for unrestricted tournament inputs because feedback arc set is NP-hard, while repeated-query variants can recover the true order efficiently.The paper distinguishes the no-resampling setting from models permitting repetitions, which admit O(n log n) query procedures with high probability.
- 1.1 The Sorting Model: The optimization objective is equivalent to maximum likelihood when every query is answered correctly with fixed probability p.The score maximizes the likelihood of observing the comparisons under a uniform prior over rankings.
- 1.3 Main Results: Theorem 3 gives a randomized algorithm that finds an optimal NSWR solution in time n^O((β+1)γ^-4) except with probability n^-β.The guarantee holds for any γ > 0 and β > 0.
- 1.3 Main Results: Theorem 4 shows that every optimal ranking is close to the true order with high probability.The paper quantifies closeness using total and maximum positional displacement.
- 1.3 Main Results: The same guarantees can be achieved with sampling complexity C n log n, where C depends on β and γ.The low-sampling implementation uses techniques related to prior sorting methods.
- 1.3 Main Results: The model can be generalized to dependent comparisons when each conditional correctness probability remains at least p.Independence is assumed in the stated model but is not essential to the modified proofs.
- 1.4 Techniques: The analysis proves proximity first and then uses insertion plus dynamic programming to construct the efficient algorithm.The insertion procedure exploits that re-sorting after adding one element moves no element by more than O(log n).
2 Sorting a presorted list
For a list already close to an optimal ordering, the paper uses dynamic programming to find an optimal sort efficiently. The algorithm exploits the bounded displacement to limit candidate interval contents and recursively combine subproblems.
- 2 Sorting a presorted list: O(n^2 · 2^6k) time suffices to find an optimal ordering when every element is at most k positions from its optimal location.This replaces brute-force enumeration over all possible permutations.
- 2 Sorting a presorted list: The dynamic program stores optimal orderings for intervals and possible element subsets consistent with the k-position displacement bound.For each interval, the selected set must contain a required core and remain within an expanded interval.
- 2 Sorting a presorted list: At most 2^4k candidate subsets arise for each interval because only 4k boundary elements can vary.The remaining elements are forced by the displacement constraints.
- 2 Sorting a presorted list: The interval hierarchy contains n − 1 intervals with lengths 2, 4, 8, and so on.This hierarchical structure supports the recursive dynamic-programming computation.
- 2 Sorting a presorted list: The recursion divides intervals into two nearly equal halves and combines optimal solutions by enumerating feasible left-half choices.The chosen left subset uniquely determines the right subset, after which the joined score is recomputed.
3 The Discrepancy between the true order and Optima
With high probability, every optimal ordering stays close to the true order: its total displacement is linear, while each element moves only O(log n) positions. The proof first controls large deviations for individual permutations, then shows that a large displacement would force many large displacements.
- 3.1 Average proximity: A permutation that beats the true order must overcome at least half of the pairwise relations on which the two orders differ.The resulting binomial-tail probability is bounded using a Chernoff bound.
- 3.1 Average proximity: With high probability, any optimal ordering has total displacement at most linear in n.A union bound combines bounds on individual permutations with a count of permutations having bounded displacement.
- 3.2 Pointwise proximity: One big dislocation is likely to entail many big dislocations, preventing a bad interval of length at least c3 log n.The proof uses good and bad positions, interval covering, and the linear-deviation bound for induced suborders.
- 3.2 Pointwise proximity: A displacement of one element by at least m1 is unlikely for any pair of indices, where m1 = O((−log ε + log n)/γ^2).The bound follows from a union bound over the events Aij.
- 3.2 Pointwise proximity: For every optimal ordering and every element, |i − σ(i)| < c3 log n with probability greater than 1 − 2ε.This conclusion follows assuming the events from Corollaries 12 and 13 hold.
4 The algorithm
The algorithm incrementally constructs optimal orderings on a random chain of subsets, using bounded dislocation to insert each new element near its original location. With high probability, it reaches an optimal ordering in polynomial time.
- Dislocation bound: With probability at least 1 − n^-β/2, every optimal ordering along the random subset chain displaces each element by less than c3 log n.Here c3 = O(γ^-4(β + 1)).
- Iterative construction: The algorithm chooses a random chain S1 ⊂ . . . ⊂ Sn and computes each optimal ordering iteratively by inserting the newly added element.Each subset Sk has size k, and σn is an optimal ordering for the full instance.
- Insertion: Majority comparisons identify the new element’s block within an error of ±2, placing it within 3c3 log n of its original location.Blocks have length c3 log n, and the incorrect-placement probability is bounded using a union bound.
- Dynamic programming: After insertion, each element is at most 4c3 log n positions from its optimal location, allowing dynamic programming to recover σk in time O(n^2 4c3+2).The process repeats until the full set is reached.
- Guarantee: The algorithm runs in time O(n^24c3+3) and fails with probability at most n^-β.The failure bound combines the chain event and the failure probabilities of the insertion stages.
5 Query Complexity
The query-efficient implementation separates dynamic-programming and insertion comparisons, using binary-search-style majority tests for insertion. It achieves O(n log n) sampling complexity while retaining high-probability guarantees.
- Query types: The algorithm uses two query types: comparisons during dynamic programming and comparisons made while inserting new elements.The query-complexity analysis treats these stages separately.
- Overall complexity: The total number of dynamic-programming comparisons is O(n log n), except with probability O(n^-β).The analysis sums the query counts across geometrically sized insertion ranges.
- Dynamic programming: The dynamic-programming stage compares each element only with elements at distance at most c0 log n from it.This bounded comparison neighborhood is used to control the total number of dynamic-programming queries.
- Insertion cost: Each inserted element can be placed using at most C log n comparisons and O(log n) time, except with probability O(n^-β).C = O(γ^-2(β + 1)), while the placement distance is at most c log n from the optimal location.
- Insertion search: Binary-search-tree insertion performs c2 log n majority-test steps, moving toward a leaf containing the correct interval with probability at least 0.99 at each step.The tree recursively partitions consecutive intervals, and tests may move to a child or backtrack to a parent.
- Insertion search: The insertion search uses at most 3kc2 log n queries, with C = 3kc2 = O(γ^-2(β + 1)).After c2 log n steps, the current node identifies one of two neighboring intervals containing the inserted element.