Sign-Rank, Index, and List Replicability: Connections and Separations
New tools for measuring how hard it is to learn complex patterns
Researchers discovered how three different measures of pattern complexity relate to each other, proving that two newer measures called the Z₂-index and list replicability can help estimate sign rank—a notoriously hard-to-calculate measure in machine learning. By connecting these measures and studying list replicability more deeply, the team resolved an open question about when sign rank and the Z₂-index diverge.
Sign rank is a fundamental concept in learning theory, but computing it directly is so difficult that researchers often can't determine whether certain problems are inherently hard to learn. These new connections give machine learning theorists practical tools to prove lower bounds on sign rank without calculating it directly, potentially accelerating progress on long-standing open problems in computational learning.