Sign-Rank, Index, and List Replicability: Connections and Separations
2026-06-16 โข Machine Learning
Machine LearningInformation Theory
AI summaryโ
The authors study different ways to measure how complex it is to represent binary concepts using points and halfspaces, focusing on a measure called sign rank. They show that one measure, the ๐ซโ-index, can be controlled by another measure called list replicability number, which is usually harder to analyze. This leads them to separate sign rank from ๐ซโ-index and to investigate list replicability deeper. They also connect list replicability to other combinatorial properties and show how it behaves when combining concept classes.
sign rankbinary concept classhalfspace๐ซโ-indexlist replicability numbercombinatorial measuresheightminimum star numberconcept class product
Authors
Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
Abstract
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 $\mathbb{Z}_2$-index and the list replicability number. We order these measures, showing that the $\mathbb{Z}_2$-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 $\mathbb{Z}_2$-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.