首页 > AI前沿 > Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices

Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices

arXiv机器学习 2026-11-07 10:43 15 阅读 查看原文

List replicability measures how many accurate hypotheses suffice to contain the output of a learning rule with arbitrarily high confidence. We prove that every nonempty class of $m$ binary concepts on $n$ domain points has list replicability at most $805\ln(2m)\ln(2n)$. This resolves the logarithmic-product conjecture of Blondal, Hatami, Hatami, Lalov, and Tretiak. Hanner matrices give lower bounds of the same order, for square matrices and for explicit families with unequal logarithmic aspect ratios.

  • The upper bound is obtained by constructing nested acyclic sets in the faces of a cube.
    • A critical-point estimate supplies highly connected regions.
    • Weighted cell attachments keep the sets compatible across faces.
    • A cubical carrier theorem converts them into accurate finite covers and learning rules.
  • Appending one constant coordinate turns list replicability into an exact geometric quantity, the face width, and graph-orientation classes satisfy exact product formulas.
  • In particular, there are explicit classes with list replicability $4k+1$ and equivariant index $3k$, so the additive gap between the two is unbounded.
  • We also develop entropy-tilting and two-sided Gibbs constructions, give combinatorial upper bounds adapted to structured matrices, compute exact values on classical families, and study the index of Paley matrices.