Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices
Abstract
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 805ln(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, and 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.
Related
- Sharp two-sided bounds for the product of modified Bessel functions and for its logarithmic derivative
- Sharp Logarithmic Bounds for Vilenkin-Fejér Kernels
- On non-monotonicity of logarithmic energy for random matrices
- Sharp inequalities for the Newtonian and logarithmic capacities
- Sharp logarithmic Sobolev inequalities on free groups by variational comparison
BibTeX
@misc{zhang2026sharp,
title = {{Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices}},
author = {Guangjian Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.10408},
eprint = {2611.10408},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.10408},
}
RIS
TY - UNPB
TI - Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices
AU - Guangjian Zhang
PY - 2026
DA - 2026/11/07
PB - arXiv
DO - 10.48550/arxiv.2611.10408
UR - https://arxiv.org/abs/2611.10408
AB - 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 805ln(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, and 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.
ER -