🤖 machine learning

Sorting from Counterexamples

This paper establishes the optimal query complexity of $\Theta(n\log n + nk)$ for learning an unknown linear order on $n$ items when up to $k$ untruthful counterexamples are allowed, while also providing bounds for cases where the ranking admits a low-dimensional geometric representation.

Original authors: Noga Alon, Shay Moran, Shlomo Moran

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Noga Alon, Shay Moran, Shlomo Moran

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a computer to understand how people prefer things, like ranking restaurants from best to worst. In the real world, getting this right is rarely a matter of asking a single question. Instead, you might ask the computer to guess a full list, and then a human points out just one mistake: "You put the sushi place first, but I actually prefer the falafel spot." The computer learns from this single correction and tries again. This back-and-forth is a fundamental way machines learn to organize information, but it becomes much harder if the person giving the feedback is sometimes wrong, or perhaps just having a bad day. The challenge for scientists is to figure out how many times a machine needs to guess and get corrected before it can be certain of the correct order, especially when some of those corrections are lies.

This question sits at the intersection of computer science and mathematics, specifically in the field of learning theory, which studies how algorithms can improve their performance based on data. The core difficulty here is that the machine must always propose a complete, sensible list, not just a collection of isolated guesses. If it guesses that A is better than B, and B is better than C, it must logically conclude that A is better than C. When the feedback is noisy or contradictory, maintaining this logical consistency becomes a massive hurdle. Researchers have long known that if every piece of feedback is perfect, the number of guesses needed grows in a predictable way as the number of items increases. However, the moment you allow for a few lies, the problem changes dramatically, and until now, the exact cost of those lies was not fully understood.

In a new study, researchers Noga Alon, Shay Moran, and Shlomo Moran have solved this puzzle for the general case. They determined precisely how many guesses a machine needs to learn an unknown ranking when up to a certain number of the corrections it receives might be false. Their work reveals a surprising truth: while the machine can learn the correct order efficiently if everyone is honest, every single lie it encounters forces it to pay a heavy price. Specifically, for each untruthful correction, the machine must make roughly as many additional guesses as there are items in the list. If there are a thousand restaurants and the machine receives ten lies, it must perform thousands of extra rounds of guessing to be sure of the answer. This finding proves that the cost of noise is not just a small bump in difficulty, but a fundamental multiplication of effort that scales directly with the size of the problem.

The team arrived at this conclusion by treating the problem as a geometric shape-finding exercise. They imagined every possible way to rank the items as a distinct region inside a high-dimensional space. When the machine makes a guess and receives a correction, it effectively cuts away a portion of this space, narrowing down where the true answer could be hiding. In a perfect world, a single correction would cut away half of the remaining possibilities, allowing the machine to find the answer quickly. The researchers showed that even when lies are present, they can design a strategy that keeps cutting away a constant fraction of the possibilities, but the presence of a lie slows this process down significantly. They used a powerful mathematical tool, known as a theorem about the center of gravity in convex shapes, to prove that their strategy works. This approach allowed them to construct an algorithm that does not need to know in advance how many lies will be told; it simply adapts to the noise as it goes, ensuring it eventually finds the truth without getting stuck in a loop of contradictions.

The researchers also explored a more specific scenario where the rankings are not arbitrary but follow a simple geometric rule, such as being determined by a few underlying features like price or distance. In this case, the items can be thought of as points in a multi-dimensional space, and the ranking is determined by looking at them from a specific angle. For these structured problems, the researchers found that the number of guesses needed depends on the number of features rather than just the total number of items. They proved that the machine can learn these rankings with far fewer guesses than in the general case, though the cost of each lie remains high. Their work establishes a clear boundary between what is possible and what is not, showing that while geometric structure can make learning easier, the penalty for untruthful feedback remains a stubborn, linear cost that cannot be easily avoided.

This research does more than just provide a formula for counting guesses; it clarifies the fundamental limits of learning from imperfect feedback. The authors demonstrated that the difficulty of handling lies is not a minor technical glitch but a core feature of the problem. Their findings rule out the possibility of designing a system that can ignore lies without paying a significant price in time or effort. Instead, they offer a concrete path forward: by using geometric insights to maintain a consistent and logical order, machines can still learn effectively even in a noisy world, provided we accept that every lie will require a proportional amount of extra work to overcome. The study leaves open the question of whether this cost can be reduced for specific types of structured data, but for the general case, the answer is now clear: truth is expensive, and lies make it even more so.

Technical Summary: Sorting from Counterexamples

Problem Definition

The paper investigates the problem of learning an unknown linear order (ranking) $\pi^*$ over $n$ items through an interactive query process. In each round, a learner proposes a complete linear order $\pi$ . The oracle responds in one of two ways:

Confirmation: Declares $\pi = \pi^*$ , terminating the interaction.
Counterexample: Returns a pair of items $\{i, j\}$ indicating that their relative order in $\pi$ is incorrect.

The core challenge lies in the presence of untruthful counterexamples. A returned pair $\{i, j\}$ is defined as truthful if the proposed order $\pi$ and the target order $\pi^*$ disagree on the relative order of $i$ and $j$ . Conversely, a counterexample is untruthful if $\pi$ and $\pi^*$ actually agree on the relative order of $i$ and $j$ . The model assumes that at most $k$ of the returned counterexamples are untruthful (lies), but the learner does not know the value of $k$ in advance. The goal is to identify the target ranking $\pi^*$ using the minimum number of queries (rounds).

A critical constraint of this model is properness: the learner must output a valid linear order in every round. This distinguishes the problem from standard weighted-majority learning where pairwise predictions might form cycles (Condorcet cycles) and cannot be extended to a single ranking.

Methodology

The authors employ a combination of geometric representations of permutations, convex geometry, and combinatorial lower-bound constructions.

1. Geometric Representation and Grunbaum's Theorem (Unrestricted Rankings)

For the general case where the target can be any of the $n!$ rankings, the authors utilize a geometric representation where each ranking corresponds to a cell in the hypercube $[0, 1]^n$ . A point $x \in [0, 1]^n$ induces a ranking based on the sorted order of its coordinates.

Truthful Case: When all counterexamples are truthful, the set of consistent points forms a convex body. The learner queries the ranking induced by the centroid of this body. Grünbaum's Theorem guarantees that any halfspace containing the centroid of a convex body contains at least a $1/e$ fraction of the body's volume. Thus, a wrong guess eliminates a constant fraction of the remaining volume, leading to an $O(n \log n)$ complexity.
Noisy Case: To handle untruthful counterexamples without permanently discarding the target, the authors replace hard elimination with a smooth weighted update. They maintain a log-concave density over the cube rather than discrete weights. The update rule uses a surrogate loss function designed to preserve log-concavity. This allows the application of the log-concave version of Grünbaum's theorem. The update penalizes rankings inconsistent with the counterexample but ensures that the weight near the true target decreases slowly (only by a factor related to $n$ for untruthful rounds), while the total mass decreases by a constant factor every round.

2. Strong Majority for Geometric Classes

For ranking classes with a low-dimensional geometric structure (where items are vectors $v_i \in \mathbb{R}^d$ and rankings are induced by projecting onto a direction $w$ ), the authors adapt the weighted majority algorithm.

Instead of simple pairwise majority (which can cycle), they define a strong-majority relation: an edge $i \to j$ exists only if a fraction $1 - O(1/d)$ of the current weight supports it.
Using Carathéodory's Theorem, they prove that in $d$ -dimensional geometric classes, this strong-majority relation is acyclic and can be extended to a valid linear order.
This allows the learner to query a valid order while ensuring that any counterexample eliminates a significant fraction ( $\Omega(1/d)$ ) of the total weight.

3. Lower Bound Constructions

The lower bounds are derived from two distinct adversarial strategies:

Sorting Argument ( $\Omega(n \log n)$ ): Adapted from comparison-based sorting (e.g., MergeSort), an adversary forces the learner to traverse a balanced comparison tree, requiring $\Omega(n \log n)$ queries even in the noiseless setting.
Condorcet Cycle ( $\Omega(nk)$ ): The adversary constructs a set of candidate rankings based on a directed cycle of $n$ items. By returning edges of the cycle as counterexamples, the adversary can force the learner to distinguish between $n$ candidates, where each candidate remains viable until its specific "forbidden" edge is returned $k+1$ times. This incurs a cost of $\Omega(nk)$ .
Geometric Lower Bounds: For $d$ -dimensional classes, the authors use polynomial rankings (items on a moment curve) to show that identifying turning points requires $\Omega(d \log n)$ queries, combined with the $\Omega(dk)$ cost from the cycle construction.

Key Results

1. Unrestricted Rankings

For an arbitrary target ranking over $n$ items with at most $k$ untruthful counterexamples:

Optimal Query Complexity: $\Theta(n \log n + nk)$ .
Upper Bound: Achieved by a deterministic learner that does not require $k$ as input. The algorithm uses a log-concave density update and queries the centroid-induced ranking.
Lower Bound: Matches the upper bound up to constant factors. The $\Omega(n \log n)$ term arises from sorting, and the $\Omega(nk)$ term arises from the Condorcet cycle construction.
Implication: While noiseless sorting is $O(n \log n)$ , each untruthful counterexample incurs an additional cost of $O(n)$ , a significant increase compared to standard weighted-majority learning where the cost is $O(k)$ .

2. Geometric Ranking Classes

For a class of rankings induced by vectors in $\mathbb{R}^d$ :

Upper Bound: $O(d^2 \log n + dk)$ .
Lower Bound: $\Omega(d \log n + dk)$ .
Gap: There remains a factor of $d$ gap in the noiseless term ( $d^2 \log n$ vs. $d \log n$ ). The upper bound is achieved by querying linear extensions of the strong-majority graph or via a centerpoint approach.
Properness: The learner can be constrained to output rankings that are themselves geometrically realizable (induced by a direction in $\mathbb{R}^d$ ).

Significance and Claims

The paper claims to provide a tight characterization of the query complexity for learning rankings from counterexamples under bounded noise, highlighting the specific cost of maintaining properness (outputting valid linear orders).

The Cost of Properness: The authors emphasize that requiring the learner to output a linear order (rather than arbitrary pairwise predictions) fundamentally changes the complexity in the presence of noise. In standard weighted-majority, untruthful feedback costs $O(1)$ per lie; here, it costs $O(n)$ because the learner must resolve potential cycles (Condorcet phenomena) to produce a valid order.
Geometric Insights: The work demonstrates how convex geometry (Grünbaum's theorem) and log-concave measures can be leveraged to design proper learning algorithms that are robust to noise, extending techniques previously used for sorting under partial information.
Parameter-Free Learning: The proposed algorithms do not require knowledge of the lie budget $k$ , making them robust to varying noise levels.
Open Questions: The authors note that while the dependence on $k$ is tight, the dependence on $d$ in the geometric noiseless term remains an open problem (specifically, whether $O(d^2 \log n)$ can be improved to $O(d \log n)$ ). They also leave the development of efficient combinatorial implementations (avoiding general-purpose sampling) as a direction for future work.

The paper concludes that even in this basic setting of bounded untruthful counterexamples, the interplay between the structural requirement of linear orders and the noise model presents non-trivial challenges that require sophisticated geometric and combinatorial tools to resolve.