Local Borsuk-Ulam, Stability, and Replicability
Zachary Chase Bogdan Chornomaz Shay Moran Amir Yehudayoff
We use and adapt the Borsuk-Ulam Theorem from topology to derive limitations
on list-replicable and globally stable learning algorithms. We further
demonstrate the applicability of our methods in combinatorics and topology.
  We show that, besides trivial cases, both list-replicable and globally stable
learning are impossible in the agnostic PAC setting. This is in contrast with
the realizable case where it is known that any class with a finite Littlestone
dimension can be learned by such algorithms. In the realizable PAC setting, we
sharpen previous impossibility results and broaden their scope. Specifically,
we establish optimal bounds for list replicability and global stability numbers
in finite classes. This provides an exponential improvement over previous works
and implies an exponential separation from the Littlestone dimension. We
further introduce lower bounds for weak learners, i.e., learners that are only
marginally better than random guessing. Lower bounds from previous works apply
only to stronger learners.
  To offer a broader and more comprehensive view of our topological approach,
we prove a local variant of the Borsuk-Ulam theorem in topology and a result in
combinatorics concerning Kneser colorings. In combinatorics, we prove that if
$c$ is a coloring of all non-empty subsets of $[n]$ such that disjoint sets
have different colors, then there is a chain of subsets that receives at least
$1+ \lfloor n/2\rfloor$ colors (this bound is sharp). In topology, we prove
e.g. that for any open antipodal-free cover of the $d$-dimensional sphere,
there is a point $x$ that belongs to at least $t=\lceil\frac{d+3}{2}\rceil$
sets.