Sign-Rank, Index, and List Replicability: Connections and Separations

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.

34 pages, 1 figure