Sharp Logarithmic-Product Bounds for List Replicability of Sign Matrices
Source: arxiv.org/abs/2611.10408
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.10408
curl -X POST /api/v1/records/arxiv/2611.10408/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.10408/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'