Search papers, labs, and topics across Lattice.
This paper establishes sharp bounds on list replicability in learning theory by proving a novel sphere covering theorem based on the Borsuk-Ulam theorem. The authors demonstrate that for VC classes, the relationship between list size and accuracy can be precisely quantified, revealing that for large-margin half-spaces, the optimal list size corresponds to the ambient dimension unless the margin is excessively large. In such cases, they present a replicable algorithm that achieves a minimal list size of \(\lceil d/2 \rceil + 1\), enhancing our understanding of reproducibility in machine learning contexts.
List replicability bounds reveal that optimal list sizes can be dramatically reduced under specific margin conditions, reshaping our understanding of reproducibility in learning theory.
In recent years, list replicability has emerged as a framework for formalizing reproducibility in learning theory. A central question is how the required list size relates to the accuracy parameter and natural complexity measures of the hypothesis class. To achieve sharp bounds on list replicability, we prove a novel topological sphere covering theorem, derived from the Borsuk-Ulam theorem. Specifically, if the $d$-sphere is covered by open sets, each of which lies in an open hemisphere, then $d+1$ of these sets must have a common intersection. Using this result, we obtain a sharp bound on the relationship between list size and accuracy for VC classes. We also show that for large-margin half-spaces, provided the margin is not too large, the optimal list size equals the ambient dimension. However, when the margin is taken to be very large, we devise a replicable algorithm achieving the minimal list size of $\lceil d/2 \rceil + 1$.
