Source-linked AI summary
Sorting from Counterexamples
Noga Alon, Shay Moran, Shlomo Moran
TL;DR
The paper studies learning linear rankings from counterexamples when up to k may be untruthful and k is unknown. It uses geometric representations for upper bounds and sorting-based arguments for lower bounds, obtaining Θ(n log n + nk) for arbitrary rankings and O(d^2 log n + dk) for d-dimensional geometric classes.
Problem
The paper studies how to learn an unknown ranking from pairwise counterexamples when up to k feedback responses may be untruthful, without knowing k in advance.
Method
The upper-bound approach represents rankings as cells in a geometric cube, while the lower-bound approach uses a MergeSort comparison tree.
Results
Θ(n log n + nk) queries suffice and are necessary for arbitrary rankings; d-dimensional geometric classes admit an O(d^2 log n + dk) upper bound.
Takeaways & Limitations
The optimal complexity for arbitrary rankings matches sorting when feedback is truthful and includes an nk term when up to k counterexamples are untruthful.
Takeaways & Limitations
The work focuses on query complexity and does not develop fully efficient implementations of its algorithms.
Abstract
from arXiv · showhide
Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ Θ(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.
1 Introduction
The paper studies learning an unknown ranking from complete-order queries that receive pairwise counterexamples, including up to k untruthful responses. It characterizes unrestricted rankings tightly and gives upper and lower bounds for low-dimensional geometric ranking classes.
- Problem: The learner proposes a linear order and receives either confirmation or a pair whose proposed relative order is wrong.At most k returned counterexamples may be untruthful, k is unknown to the learner, and correctness declarations are always truthful.
- Problem: Pairwise majority predictions can form a Condorcet cycle, so the learner must output a genuine linear order rather than independent pairwise decisions.The rankings a ≻ b ≻ c, b ≻ c ≻ a, and c ≻ a ≻ b produce such a cycle.
- Unrestricted rankings: Θ(n log n + nk) queries are necessary and sufficient for arbitrary rankings with at most k untruthful counterexamples.The noiseless term matches sorting, while the noisy term reflects the additional cost of untruthful feedback.
- Algorithms and limitations: The algorithms achieve the unrestricted upper bound without knowing k, and the computational treatment leaves fully efficient implementations for future work.The proposed implementation route uses approximate sampling of efficiently evaluable log-concave distributions, but the required guarantees are not developed.
- Unrestricted rankings: The upper bound uses a geometric representation of rankings in [0,1]^n, where counterexamples impose halfspace constraints and Grünbaum’s theorem ensures constant-fraction progress.The learner queries the ranking induced by the center of gravity of the remaining feasible body.
- Geometric rankings: For d-dimensional geometric ranking classes, the paper gives an O(d^2 log n + dk) upper bound and a matching-in-k Ω(d log n + dk) lower bound.The upper bound rounds a sufficiently strong majority relation to a proper linear order, while a factor of d remains in the noiseless term.
2 Proof Overview
The proof overview develops geometric and combinatorial arguments for proper ranking queries, handling truthful and untruthful counterexamples across unrestricted and geometric ranking classes.
- Upper bounds: The unrestricted upper bound replaces pairwise majority with geometric averaging so every query remains a valid linear order.The approach uses the cube representation of rankings and centroid-based queries.
- Upper bounds: In the truthful case, centroid queries eliminate a constant fraction of the remaining volume, yielding O(log(n!)) = O(n log n) rounds.Grünbaum’s theorem supplies the constant-fraction volume guarantee.
- Upper bounds: For untruthful feedback, a log-concave density replaces discontinuous weighted updates, preserving geometric progress while tolerating bounded errors.The update uses a convex surrogate and applies the log-concave form of Grünbaum’s inequality.
- Lower bounds: The lower bounds combine sorting-style arguments with Condorcet-cycle constructions, then use polynomial orders on the moment curve for geometric classes.The polynomial construction places Θ(d) independently adjustable turning points across disjoint item intervals.
3 Related Work
The paper situates its counterexample model among comparison-based ranking, sorting, equivalence-query, and proper-learning research, while emphasizing its distinct interaction and properness requirements.
- Comparison-based ranking: Prior work studies pairwise comparisons for preference elicitation, theoretical learning, and ranking from comparison data.The cited literature includes statistical preference models and active comparison schemes.
- Comparison-based ranking: This model differs from standard comparison queries because the learner proposes a complete ranking and the oracle returns a misordered pair.Every query must itself be a linear order, making properness central.
- Equivalence queries: The interaction is related to equivalence-query learning, but adds boundedly many untruthful counterexamples and a central linear-order query requirement.In the geometric setting, the queried order need not belong to the target geometric class.
- Proper learning: Related proper-learning work replaces majority predictions with hypotheses from a prescribed class; this paper applies a related principle under boundedly many untruthful counterexamples.Its geometric upper bound first forms strong pairwise predictions and then extends them to a valid linear order.
4 Arbitrary Rankings
For arbitrary rankings, the paper gives a k-independent upper bound of O(n log n + nk) and a matching lower bound of Ω(n log n + nk). The upper bound uses log-concave weighted updates and Grünbaum’s theorem, while the lower bound combines sorting and Condorcet-cycle arguments.
- Upper bound: The learner represents rankings as equal-volume cells in [0,1]^n, with counterexamples imposing halfspace constraints.Each ranking is induced by sorting coordinates, and the n! ranking cells partition the cube up to measure-zero boundaries.
- Upper bound: Log-concave weighted updates replace hard elimination, preserving the geometric structure needed for Grünbaum’s theorem despite untruthful counterexamples.The maintained density remains log-concave, and the centroid-induced query retains constant progress in total weight.
- Upper bound: O(n log n + nk) queries suffice for arbitrary target rankings, using a deterministic proper learner that does not know k.The learner cannot receive counterexamples for more than O(n log n + nk) rounds before it proposes the target ranking.
- Lower bound: Ω(n log n) queries are necessary even with truthful counterexamples, via a MergeSort comparison-tree construction.The lower bound follows because each of Θ(log n) recursion levels requires Ω(n) comparisons.
- Lower bound: Ω(nk) additional queries are necessary when up to k counterexamples are untruthful, using a Condorcet-cycle construction.Together with the sorting term, this yields worst-case expected complexity Ω(n log n + nk) for randomized proper learners.
5 Geometric Rankings
For d-dimensional geometric ranking classes, strong weighted-majority relations remain acyclic, enabling proper linear-order queries despite untruthful counterexamples. The resulting deterministic learner uses O(d^2 log n + dk) queries, while matching lower bounds leave only a factor-d gap in the noiseless term.
- Geometric ranking classes: A d-dimensional geometric class ranks items by projecting vectors v_i onto a direction w, with only strict linear orders allowed.The relation is i ≺_π j exactly when ⟨v_i,w⟩ < ⟨v_j,w⟩.
- Proper prediction: Strong weighted-majority comparisons are acyclic in a d-dimensional geometric class, despite arbitrary pairwise majorities potentially forming cycles.Acyclicity follows from the geometric representation and a convexity argument.
- Proper prediction: Every query is a genuine linear order obtained by taking a linear extension of the acyclic strong-majority graph, although it need not belong to H.The threshold ensures each queried comparison has at least a 1/(d+1) fraction of current weighted support.
- Upper bound: O(d^2 log n + dk) queries suffice with at most k untruthful counterexamples, and the deterministic learner need not know k.The total weight decreases on every counterexample, while the target ranking loses weight only on untruthful rounds.
- Lower bound: Ω(d log n + dk) queries are necessary for some d-dimensional geometric classes, so the dependence on k is tight while the noiseless term retains a factor-d gap.A low-degree polynomial ranking class supplies the lower bound construction.
6 Open Questions and Future Directions
The paper identifies open questions about geometric classes, partial prior information, computational efficiency, and richer noise models. In particular, geometric rankings have a tight k-dependent term but an unresolved factor-d gap in the noiseless term.
- Geometric ranking classes: For geometric ranking classes, the upper bound is O(d^2 log n + dk) and the lower bound is Ω(d log n + dk).The unresolved issue is whether the upper bound can improve or whether some classes require Ω(d^2 log n) queries.
- Geometric ranking classes: The dependence on untruthful counterexamples is tight, but the noiseless term has an unresolved factor-d gap.The paper asks whether O(d log n + dk) is achievable or Ω(d^2 log n) is necessary for some classes.
- Starting from partial information: With known comparisons forming a poset P and L possible linear extensions, the truthful deterministic complexity is Θ(log L), while the noisy case remains less clear.The width x of P yields a Condorcet-based lower bound, but the full noisy complexity may require more structural parameters than L and x.
- Computational efficiency: The paper does not develop fully efficient implementations and leaves the precise computational complexity of its algorithms open.It suggests making randomized polynomial-time approximations explicit and seeking efficient combinatorial algorithms.
- Richer noise models: The bounded-total-lies model leaves open richer stochastic noise models, including per-round adversarial errors with probability at most p < 1/2.The paper also suggests preference-generated feedback such as Bradley–Terry models.