# Local Borsuk-Ulam, Stability, and Replicability

arXiv: https://arxiv.org/abs/2311.01599 · HTML: https://mlsanity.com/paper/2311.01599/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 2 Nov 2023.

## Builds on (most cited first, 7 of 7)

- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [Boosting Simple Learners](https://mlsanity.com/paper/2001.11704/) (2020)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)
- [Replicability and stability in learning](https://mlsanity.com/paper/2304.03757/) (2023)

## Built on by (most cited first, 14 of 14)

- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Stability and List-Replicability for Agnostic Learners](https://mlsanity.com/paper/2501.05333/) (2025)
- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Simplicial covering dimension of extremal concept classes](https://mlsanity.com/paper/2511.11819/) (2025)
- [On Reductions and Representations of Learning Problems in Euclidean Spaces](https://mlsanity.com/paper/2411.10784/) (2024)
- [Tight list replicability bounds via a novel sphere covering theorem](https://mlsanity.com/paper/2606.06148/) (2026)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)
- [Replicable Conformal Prediction](https://mlsanity.com/paper/2608.23638/) (2026)

## Abstract (arXiv)

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/2rfloor 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=lceilfracd+32rceil sets.