Organizations: Princeton University, Princeton, NJ 08544, USA, and Tel Aviv University, Tel Aviv 69978, Israel. · Technion – Israel Institute of Technology and Google Research. · Technion – Israel Institute of Technology.
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:
Θ(nlogn+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 Rd, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of O(d2logn+dk) and a lower bound of Ω(dlogn+dk), leaving a factor of d gap in the noiseless term.
Figures & tables
Figure 1: The pairwise majority relation may contain a Condorcet cycle, even though each individual ranking is a linear order.
Figure 2: A geometric ranking in two dimensions. The items are represented by vectors v1,…,vn∈R2 . A direction w induces a ranking by ordering the items according to their projections onto w . Dashed lines indicate orthogonal projections.
Figure 3: The geometric representation of rankings for n=2 . A point x∈[0,1]2 induces a ranking according to the order of its coordinates. The line x1=x2 splits the square into the two cells corresponding to the two possible linear orders.
Figure 4: Schematic view of the polynomial construction. The items are consecutive points on the real line, and the polynomial has one turning point in each of Θ(d) disjoint intervals. A comparison of two consecutive items near the midpoint of the current uncertainty interval determines on which side the corresponding turning point may lie, yielding a binary-search-type lower bound.
Active seriation aims at recovering an unknown ordering of n items by adaptively querying pairwise similarities. The observations are noisy measurements of entries of an underlying n x 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.
James Cheshire, Yann Issartel
LTCI, Télécom Paris, Institut Polytechnique de Paris
In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the Z2-index and the list replicability number. We order these measures, showing that the Z2-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and Z2-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.
In a controlled experiment on modular arithmetic (p=9973), varying only example ordering while holding all else constant, two fixed-ordering strategies achieve 99.5% test accuracy by epochs 487 and 659 respectively from a training set comprising 0.3% of the input space, well below established sample complexity lower bounds for this task under IID ordering. The IID baseline achieves 0.30% after 5{,}000 epochs from identical data. An adversarially structured ordering suppresses learning entirely. The generalizing model reliably constructs a Fourier representation whose fundamental frequency is the Fourier dual of the ordering structure, encoding information present in no individual training example, with the same fundamental emerging across all seeds tested regardless of initialization or training set composition. We discuss implications for training efficiency, the reinterpretation of grokking, and the safety risks of a channel that evades all content-level auditing.