{"ID":3083736,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T09:00:11.459356253Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.06148","arxiv_id":"2606.06148","title":"Tight list replicability bounds via a novel sphere covering theorem","abstract":"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$.","short_abstract":"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 t...","url_abs":"https://arxiv.org/abs/2606.06148","url_pdf":"https://arxiv.org/pdf/2606.06148v1","authors":"[\"Ari Blondal\",\"Hamed Hatami\",\"Pooya Hatami\",\"Chavdar Lalov\",\"Sivan Tretiak\"]","published":"2026-06-04T13:24:05Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}