A polylogarithmic bound for list replicability
stat.ML, cs.LG, math.CO
Submitted: 2026-10-14
Updated: 2026-10-14
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of M 2 binary concepts on N 2 domain points is O(squared M N), which would be the first
Abstract
Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of M 2 binary concepts on N 2 domain points is O(squared M N), which would be the first polylogarithmic upper bound on this quantity. In this note, we present a short, self-contained proof of this bound, following the high-level approach of the manuscript but with considerably simpler arguments.
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Efficient quadratic entropy with distance sketches
- Embedding-Bias in Conditional Independence Testing
- From Log-Odds to Shapley Values: An Explanatory Geometry for the Weighted Naive Bayes Classifier