A polylogarithmic bound for list replicability

Ari Blondal; Hamed Hatami; Pooya Hatami; Chavdar Lalov; Sivan Tretiak

stat.MLOct 14, 2026

A polylogarithmic bound for list replicability

Authors: Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak

Organizations: McGill University · Ohio State University

Abstract

Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of $M\ge 2$ binary concepts on $N\ge 2$ domain points is $O(\log^2 M\log 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.

Concept Learning

See all 12 papers

Tight list replicability bounds via a novel sphere covering theorem
Jun 4, 2026Ari Blondal, Hamed Hatami, Pooya Hatami +2ML Reproducibility Statistical Learning Theory
McGill University · Ohio State University
Sign-Rank, Index, and List Replicability: Connections and Separations
Jun 16, 2026Ari Blondal, Hamed Hatami, Pooya Hatami +2Statistical Learning Theory
McGill University · Ohio State University
The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning
Oct 18, 2026Guangjian ZhangAgnostic Learning Sample Complexity

Jun 4, 2026J/K move · Enter open · S save

Tight list replicability bounds via a novel sphere covering theorem

Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov+1

McGill University · Ohio State University

ML Reproducibility Statistical Learning Theory

Open paper AskPDF arXiv

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

Abstract

Concept Learning

Explore similar work

Tight list replicability bounds via a novel sphere covering theorem

Sign-Rank, Index, and List Replicability: Connections and Separations

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning