pith. sign in

arxiv: 2606.06148 · v1 · pith:HUVSDZTMnew · submitted 2026-06-04 · 💻 cs.LG

Tight list replicability bounds via a novel sphere covering theorem

Ari Blondal , Hamed Hatami , Pooya Hatami , Chavdar Lalov , Sivan Tretiak This is my paper

Pith reviewed 2026-06-28 02:04 UTC · model grok-4.3

classification 💻 cs.LG
keywords list replicabilityVC dimensionsphere coveringBorsuk-Ulam theoremhalf-spacesreproducible learningtopological learning theory
0
0 comments X

The pith

A new sphere covering theorem from Borsuk-Ulam yields tight bounds on list size versus accuracy for replicable learning of VC classes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that any cover of the d-sphere by open sets each contained in an open hemisphere requires d+1 sets to share a common point. It applies this topological fact to show sharp relationships between the list size needed for replicable learning and the accuracy parameter when the hypothesis class has finite VC dimension. The same approach gives exact optimal list sizes for large-margin half-spaces that depend on whether the margin is moderate or very large. A reader would care because list replicability formalizes reproducibility requirements, and knowing the minimal list size tells how many candidate outputs an algorithm must return to guarantee both accuracy and reproducibility.

Core claim

The central claim is a sphere covering theorem: if the d-sphere is covered by open sets each lying inside some open hemisphere, then some d+1 of the sets have nonempty intersection. This theorem is derived from the Borsuk-Ulam theorem. Using it, the paper establishes that for any VC class the minimal list size required to achieve replicable learning at accuracy epsilon is tightly characterized in terms of the VC dimension. For half-spaces with margin not too large the optimal list size equals the ambient dimension d; when the margin is taken very large an explicit replicable algorithm achieves the smaller list size of ceil(d/2)+1.

What carries the argument

The novel sphere covering theorem stating that any cover of the d-sphere by open sets each contained in an open hemisphere must contain d+1 sets with a common intersection point.

If this is right

  • For any hypothesis class with finite VC dimension the minimal list size for replicable learning is a sharp function of accuracy and VC dimension.
  • For half-spaces whose margin is bounded away from the maximum possible value the smallest achievable list size equals the ambient dimension.
  • When the margin is taken sufficiently large a simple replicable algorithm exists whose list size is only ceil(d/2)+1.
  • The topological reduction supplies matching upper and lower bounds on list size for these families.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same covering argument could be adapted to other learning problems that involve symmetric choice among hypotheses.
  • Practical replicable algorithms for linear classifiers might exploit the dimension-dependent list sizes shown for half-spaces.
  • The result suggests that topological methods can replace combinatorial arguments when deriving tight sample-complexity bounds for reproducibility constraints.

Load-bearing premise

The replicability requirement for learning can be modeled exactly as a covering of the d-sphere by open sets each contained in an open hemisphere.

What would settle it

An explicit cover of the d-sphere by open sets each inside some open hemisphere in which no d+1 sets intersect, or a concrete VC class and accuracy level where the minimal list size needed for replicable learning exceeds the bound derived from the theorem.

Figures

Figures reproduced from arXiv: 2606.06148 by Ari Blondal, Chavdar Lalov, Hamed Hatami, Pooya Hatami, Sivan Tretiak.

Figure 1
Figure 1. Figure 1: Regimes for lr(Hd γ , ϵ) when d > 1. When γ < √ 1 d , it is well known that vc(Hd γ ) = d, so we know from Theorem A that lr = d. 3 Proof of Theorem 2.1 In this section, we prove our main topological result. Theorem 2.1. Let A1, . . . , Am be a finite open cover of the d-sphere S d , where each Ai is contained in an open hemisphere. Then d + 1 of these sets have a common nonempty intersection. We will use … view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of the disagreement set Eu,w between cu and cw, projected onto the plane common to u, w, and 0. Now let θ := arccos(⟨u, w⟩) be the angle between u and w. We have ν(Eu,w) = ν({x ∈ supp cu ∩ supp cw : cu(x) ̸= cw(x)}) = = 2ν({x ∈ S d−1 : ⟨u, x⟩ ≥ γ,⟨w, x⟩ ≤ −γ}) = = 2ν({x ∈ S d−1 : x1 ≥ γ, cos(θ)x1 + sin(θ)x2 ≤ −γ}) (2) where the last equality follows from the rotational invariance of the sph… view at source ↗
read the original 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper proves a novel sphere covering theorem derived from Borsuk-Ulam: if the d-sphere is covered by open sets each contained in some open hemisphere, then d+1 of the sets must have nonempty common intersection. It applies the theorem to obtain sharp bounds relating list size to accuracy for replicable learning of VC classes, and shows that for large-margin halfspaces (margin not too large) the optimal list size equals the ambient dimension d, while providing a replicable algorithm achieving list size ceil(d/2)+1 when the margin is very large.

Significance. If the central theorem and the modeling reduction both hold with no slack, the work would deliver the first tight (matching upper and lower) characterizations of list replicability for VC classes and halfspaces, a notable advance over prior non-sharp bounds in the area. The explicit derivation from Borsuk-Ulam and the algorithmic construction for the large-margin regime are clear strengths.

major comments (2)
  1. [Reduction from replicability to sphere covering (implicit in the passage from the learning problem to the topological st] The modeling step that reduces replicability to a covering of the d-sphere by open sets each contained in an open hemisphere (the step underlying both the VC-class bound and the halfspace optimality claim) must be shown to be tight in both directions. If the hemisphere condition is strictly weaker than the replicability constraint that must hold for every distribution, then the derived upper bound on list size may be loose and the matching lower bound establishing optimality (list size = d) would not apply.
  2. [Application to large-margin halfspaces] For the halfspace result claiming optimal list size exactly equals d when the margin is not too large, the manuscript must verify that the lower-bound construction (showing list size < d is impossible) survives the same geometric encoding; any gap between the covering condition and actual replicability over all distributions would falsify the equality.
minor comments (1)
  1. [Abstract] The abstract states the VC-class bound only qualitatively; an explicit functional form (e.g., list size as a function of accuracy and VC-dimension) would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments regarding the tightness of the modeling reduction. We address each major comment below and will revise the manuscript accordingly to make the equivalence explicit.

read point-by-point responses

  1. Referee: [Reduction from replicability to sphere covering (implicit in the passage from the learning problem to the topological st] The modeling step that reduces replicability to a covering of the d-sphere by open sets each contained in an open hemisphere (the step underlying both the VC-class bound and the halfspace optimality claim) must be shown to be tight in both directions. If the hemisphere condition is strictly weaker than the replicability constraint that must hold for every distribution, then the derived upper bound on list size may be loose and the matching lower bound establishing optimality (list size = d) would not apply.

    Authors: We agree that an explicit demonstration of tightness in both directions is necessary to support the sharpness claims. The reduction is designed so that replicability over every distribution corresponds exactly to the open sets lying in open hemispheres (via the definition of list replicability and the geometry of the hypothesis space), with the converse also holding by construction of the covering. In the revision we will add a dedicated lemma and proof establishing the if-and-only-if equivalence between the replicability constraint and the hemisphere-containment condition. revision: yes

  2. Referee: [Application to large-margin halfspaces] For the halfspace result claiming optimal list size exactly equals d when the margin is not too large, the manuscript must verify that the lower-bound construction (showing list size < d is impossible) survives the same geometric encoding; any gap between the covering condition and actual replicability over all distributions would falsify the equality.

    Authors: We will revise the halfspace section to include an explicit check that the lower-bound construction (establishing that list size strictly less than d is impossible) is preserved under the same geometric encoding used for the sphere-covering argument. This verification will confirm that no modeling gap exists and that the claimed optimality (list size exactly equal to d) holds for margins that are not too large. revision: yes

Circularity Check

0 steps flagged

No circularity: novel theorem derived from external Borsuk-Ulam; bounds follow from independent reduction

full rationale

The paper states its sphere covering theorem is derived from the Borsuk-Ulam theorem (external). Learning bounds for VC classes and half-spaces are obtained by applying the new covering result after reducing replicability to a sphere-covering condition. No load-bearing self-citations, no fitted parameters renamed as predictions, and no self-definitional steps appear in the derivation chain. The reduction encodes replicability via open sets in hemispheres but does not make the claimed bounds tautological with the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the Borsuk-Ulam theorem (standard topology) and the geometric encoding of replicability as a sphere covering; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Borsuk-Ulam theorem
    Invoked to derive the sphere covering statement.

pith-pipeline@v0.9.1-grok · 5711 in / 1288 out tokens · 35397 ms · 2026-06-28T02:04:59.751558+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 4 canonical work pages

  1. [1]

    2002 , publisher=

    Algebraic Topology , author=. 2002 , publisher=

    2002

  2. [2]

    2003 , publisher=

    Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry , author=. 2003 , publisher=

    2003

  3. [3]

    2000 , publisher=

    Topology , author=. 2000 , publisher=

    2000

  4. [4]

    1987 , publisher=

    Real and complex analysis , author=. 1987 , publisher=

    1987

  5. [5]

    2014 , publisher=

    Understanding machine learning: From theory to algorithms , author=. 2014 , publisher=

    2014

  6. [6]

    Forty-second International Conference on Machine Learning , year=

    The Role of Randomness in Stability , author=. Forty-second International Conference on Machine Learning , year=

  7. [7]

    Peter Dixon and Aduri Pavan and Jason Vander Woude and N. V. Vinodchandran , title=. 2023 , cdate=

    2023

  8. [8]

    and Radcliffe, Jamie and Vinodchandran, N

    Vander Woude, Jason and Dixon, Peter and Pavan, A. and Radcliffe, Jamie and Vinodchandran, N. V. , booktitle =. Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma , volume =. doi:10.52202/079017-2508 , editor =

    work page doi:10.52202/079017-2508

  9. [9]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =

    Chase, Zachary and Chornomaz, Bogdan and Moran, Shay and Yehudayoff, Amir , title =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =. 2024 , isbn =

    2024

  10. [10]

    A theory of

    Alon, Noga and Hanneke, Steve and Holzman, Ron and Moran, Shay , booktitle=. A theory of. 2021 , organization=

    2021

  11. [11]

    2023 , volume =

    Chase, Zachary and Moran, Shay and Yehudayoff, Amir , booktitle =. 2023 , volume =

    2023

  12. [12]

    and Vander Woude, Jason and Vinodchandran, N

    Dixon, Peter and Pavan, A. and Vander Woude, Jason and Vinodchandran, N. V. , title =. Proceedings of the 37th International Conference on Neural Information Processing Systems , articleno =. 2024 , publisher =

    2024

  13. [13]

    Patterns , author =

    Leakage and the reproducibility crisis in machine-learning-based science , issn =. Patterns , author =. 2023 , note =

    2023

  14. [14]

    , author=

    The perceptron: a probabilistic model for information storage and organization in the brain. , author=. Psychological Review , volume=. 1958 , publisher=

    1958

  15. [15]

    and Pitts, Walter , TITLE =

    McCulloch, Warren S. and Pitts, Walter , TITLE =. Bull. Math. Biophys. , FJOURNAL =. 1943 , PAGES =

    1943

  16. [16]

    2025 , eprint=

    Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces , author=. 2025 , eprint=

    2025

  17. [17]

    arXiv preprint arXiv:2503.10240 , year=

    Spherical dimension , author=. arXiv preprint arXiv:2503.10240 , year=

    work page arXiv

  18. [18]

    arXiv preprint arXiv:2511.11819 , year=

    Simplicial covering dimension of extremal concept classes , author=. arXiv preprint arXiv:2511.11819 , year=

    work page arXiv

  19. [19]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Impagliazzo, Russell and Lei, Rex and Pitassi, Toniann and Sorrell, Jessica , title =. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2022 , isbn =

    2022

  20. [20]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Ghazi, Badih and Golowich, Noah and Kumar, Ravi and Manurangsi, Pasin , title =. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2021 , publisher =

    2021

  21. [21]

    Alon, Noga and Bun, Mark and Livni, Roi and Malliaris, Maryanthe and Moran, Shay , TITLE =. J. ACM , FJOURNAL =. 2022 , NUMBER =

    2022

  22. [22]

    Fan, Ky , TITLE =. Ann. of Math. (2) , FJOURNAL =. 1952 , PAGES =

    1952

  23. [23]

    Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin , year =. User-. Advances in

  24. [24]

    An Equivalence Between Private Classification and Online Prediction , year=

    Bun, Mark and Livni, Roi and Moran, Shay , booktitle=. An Equivalence Between Private Classification and Online Prediction , year=

  25. [25]

    arXiv preprint arXiv:2212.05050 , year=

    The unstable formula theorem revisited via algorithms , author=. arXiv preprint arXiv:2212.05050 , year=

    work page arXiv

  26. [26]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , series =

    Stability is stable: Connections between replicability, privacy, and adaptive generalization , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , series =. 2023 , pages=

    2023

  27. [27]

    Advances in Neural Information Processing Systems , volume=

    Replicability in reinforcement learning , author=. Advances in Neural Information Processing Systems , volume=

  28. [28]

    The Eleventh International Conference on Learning Representations , year=

    Replicable Bandits , author=. The Eleventh International Conference on Learning Representations , year=

  29. [29]

    Replicable Clustering , url =

    Esfandiari, Hossein and Karbasi, Amin and Mirrokni, Vahab and Velegkas, Grigoris and Zhou, Felix , booktitle =. Replicable Clustering , url =

  30. [30]

    Advances in Neural Information Processing Systems , volume=

    The bayesian stability zoo , author=. Advances in Neural Information Processing Systems , volume=

  31. [31]

    Proceedings of the 37th International Conference on Neural Information Processing Systems , articleno =

    Eaton, Eric and Hussing, Marcel and Kearns, Michael and Sorrell, Jessica , title =. Proceedings of the 37th International Conference on Neural Information Processing Systems , articleno =. 2023 , publisher =

    2023

  32. [32]

    Proceedings of the 41st International Conference on Machine Learning , articleno =

    Kalavasis, Alkis and Karbasi, Amin and Larsen, Kasper Green and Velegkas, Grigoris and Zhou, Felix , title =. Proceedings of the 41st International Conference on Machine Learning , articleno =. 2024 , publisher =

    2024

  33. [33]

    Proceedings of the 40th International Conference on Machine Learning , articleno =

    Kalavasis, Alkis and Karbasi, Amin and Moran, Shay and Velegkas, Grigoris , title =. Proceedings of the 40th International Conference on Machine Learning , articleno =. 2023 , publisher =

    2023