Pith. sign in

REVIEW 2 major objections 1 minor 1 cited by

Tight list replicability bounds via a novel sphere covering theorem

T0 review · 2 major / 1 minor · reviewed 2026-06-28 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

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

desk verdict New sphere covering theorem from Borsuk-Ulam yields the first tight list-size bounds for VC classes and margin halfspaces, but the reduction's exactness for those equalities needs verification. read the letter →

arxiv 2606.06148 v1 pith:HUVSDZTM submitted 2026-06-04 cs.LG

Ari Blondal , Hamed Hatami , Pooya Hatami , Chavdar Lalov , Sivan Tretiak This is my paper · ORCID
classification cs.LG
keywords listreplicabilityVCdimensionspherecoveringBorsuk-Ulamtheoremhalf-spacesreproduciblelearningtopologicaltheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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.

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.

Watch

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 1 assumptions · 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.

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

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tight list replicability bounds via a novel sphere covering theorem." pith.science (2026). https://pith.science/paper/HUVSDZTM

@misc{pith2026260606148,
  author       = {Pith},
  title        = {Pith review of: Tight list replicability bounds via a novel sphere covering theorem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HUVSDZTM}},
  note         = {Machine review of arXiv:2606.06148}
}
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$.

Figures

Figures reproduced from arXiv: 2606.06148 by the authors.

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 the follow… view at source ↗
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 spherical mea… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    cs.LG 2026-06 unverdicted novelty 7.0 of 10

    Sign-rank is not bounded by Z2-index: projective-plane incidence matrices have Z2-index at most 5 and sign-rank growing polynomially, via the ordering Index ≤ 2·list-replicability − 1.

Reference graph

Works this paper leans on

33 extracted references · 4 canonical work pages · cited by 1 Pith paper

  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

Show all 33 references
  1. [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

  2. [10]

    A theory of

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

    2021

  3. [11]

    2023 , volume =

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

    2023

  4. [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

  5. [13]

    Patterns , author =

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

    2023

  6. [14]

    , author=

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

    1958

  7. [15]

    and Pitts, Walter , TITLE =

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

    1943

  8. [16]

    2025 , eprint=

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

    2025

  9. [17]

    arXiv preprint arXiv:2503.10240 , year=

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

  10. [18]

    arXiv preprint arXiv:2511.11819 , year=

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

  11. [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

  12. [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

  13. [21]

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

    2022

  14. [22]

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

    1952

  15. [23]

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

  16. [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=

  17. [25]

    arXiv preprint arXiv:2212.05050 , year=

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

  18. [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

  19. [27]

    Advances in Neural Information Processing Systems , volume=

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

  20. [28]

    The Eleventh International Conference on Learning Representations , year=

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

  21. [29]

    Replicable Clustering , url =

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

  22. [30]

    Advances in Neural Information Processing Systems , volume=

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

  23. [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

  24. [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

  25. [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

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.