Borsuk-Ulam and replicable learning of large-margin halfspaces

Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak · 2025

Read Borsuk-Ulam and replicable learning of large-margin halfspaces by Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-15294.txt.

Introduction

Ari Blondal and four colleagues settle how many backup answers a learning algorithm needs to be replicable on halfspace problems, in a 2025 paper. Replicability asks that rerunning training on fresh data returns the same hypothesis, and list versions allow a short menu of acceptable answers.

For wide-margin halfspaces in d dimensions, the needed list size sits between d over two plus one, and d. The proof's lower bound leans on a topological theorem about spheres. The result cascades into five other problems, each a named open question in learning and communication complexity, now answered as corollaries. The upper bound builds a replicable learner from the stability of support vector machines.

Catalog record

CREATORAri Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-15294

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Borsuk-Ulam and replicable learning of large-margin halfspaces Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak Abstract We prove that the list replicability number of d d -dimensional γ \gamma -margin half-spaces satisfies d 2 + 1 ≤ LR ⁡ ( ℋ γ d ) ≤ d , \frac{d}{2}+1\leq\LR(\mathcal{H}^{d}_{\gamma})\leq d, which grows with dimension. This resolves several open problems: • Every disambiguation of infinite-dimensional large-margin half-spaces to a total concept class has unbounded Littlestone dimension, answering an open question of Alon, Hanneke, Holzman, and Moran (FOCS ’21). • Every disambiguation of the Gap Hamming Distance problem in the large gap regime has unbounded public-coin randomized communication complexity. This answers an open question of Fang, Göös, Harms, and Hatami (STOC ’25). • There is a separation of O ⁡ ( 1 ) O(1) vs ω ⁡ ( 1 ) \omega(1) between randomized and pseudo-deterministic communication complexity. • The maximum list-replicability number of any finite set of points and homogeneous half-spaces in d d -dimensional Euclidean space is d d , resolving a problem of Chase, Moran, and Yehudayoff (FOCS ’23). • There exists a partial concept class with Littlestone dimension 1 1 such that all its disambiguations have infinite Littlestone dimension. This resolves a problem of Cheung, H. Hatami, P. Hatami, and Hosseini (ICALP ’23). Our lower bound follows from a topological argument based on a local Borsuk-Ulam theorem. For the upper bound, we construct a list-replicable learning rule using the generalization properties of SVMs. 1 Introduction Large-margin half-space classification is a fundamental problem in learning theory. In this setting, data is normalized to lie on the unit sphere \mathbb{S}^{d-1}\subset\mathbb{R}^{d} , and we are guaranteed a promise that each point lies at least a fixed margin \gamma\in(0,1) from some unknown homogeneous hyperplane. The learner is then tasked with classifying points based on the side of the defining hyperplane to which they belong. This problem has been extensively studied for both its theoretical and practical significance: it provides a clean geometric model for analyzing more complex learning tasks, and underlies the success of Support Vector Machines (SVMs), which leverage the large-margin assumption to produce accurate classifications in high-dimensional spaces, with applications across domains such as text and image recognition, bioinformatics, and fraud detection. We study this problem through the lens of replicability, the requirement that an algorithm produce consistent outcomes when repeated under similar conditions and with similar data. In recent years, replicability has become a vibrant research area, and various rigorous formulations of replicability for learning algorithms have been introduced and studied [ BLM20 , MM22 , CMY23 , BGH+23 , KVYZ23 , EKK+23 , EKM+23 , MSS23 , EHKS23 , KKL+24 , KKMV23 ] . Among them, one of the most intriguing is the notion of global stability , which was first discovered in connection with differentially private learning and online learning [ BLM20 , ABL+22 , CMY23 ] . Subsequent work, however, has shown that its significance extends well beyond these applications. In its equivalent formulation as list replicability [ CMY23 ] , the notion is intrinsically linked to the geometry and topology of the space of realizable distributions of a concept class [ CMY23 , CCMY24 , BGHH25 , CMW25 , BHH+25 ] . For example, for finite classes, it characterizes the topological dimension of this space under its natural simplicial structure [ BHH+25 ] . Through these connections, fundamental results in classical topological dimension theory, such as the Lebesgue covering theorem, translate directly into statements about learnability and replicability. Our main result states that the list replicability number of the large-margin classification problem in \mathbb{R}^{d} lies between \tfrac{d}{2}+1 and d . In particular, it diverges as the ambient dimension d grows. This stands in contrast to many common complexity measures for the same task, such as the VC dimension, Littlestone dimension, and randomized communication complexity, which are bounded by a function of the margin \gamma\in(0,1) independent of the ambient dimension d . This divergence has several consequences and resolves a number of open problems from previous works, as discussed in detail in Section 2.1 . Beyond its implications within learning theory, it also connects naturally to questions in communication complexity. In particular, our most notable consequence shows that any disambiguation of the large-margin classification problem into a total concept class must have a large Littlestone dimension and a large randomized communication complexity. Thus, while the original partial problem is “easy” under these classical measures, every possible completion of it to a total problem is inherently “hard”. Establishing such lower bounds for disambiguations is typically very challenging, as the initial partial problem is “easy” and one has no control over how it is extended to a total one. A notable consequence of our disambiguation theorem is an O(1) versus \Omega(\log\log n) gap between randomized and pseudo-deterministic communication complexities. Separating these two measures is a well-known open problem in the study of pseudodeterminism [ GIPS21 ] , and our result provides the first O(1) versus \omega(1) separation. 1.1 Preliminaries We study the large-margin half-space problem through the formal lens of partial classes, which offers a general framework for analyzing such constrained learning tasks. A partial concept class over an arbitrary domain \mathcal{X} is a set \mathcal{C}\subseteq\left\{\pm 1,\star\right\}^{\mathcal{X}} , where each c\in\mathcal{C} is called a partial concept . The value c(x)=\star indicates that c is undefined at x , and therefore, both \pm 1 are acceptable predictions for the label of x . PAC learning. The standard mathematical framework for analyzing the complexity of a learning task is probably approximately correct (PAC) learning . In PAC learning, the learner is given parameters \delta,\epsilon>0 and receives training data consisting of n=n(\mathcal{C},\delta,\epsilon) independent labeled examples drawn from an unknown but fixed distribution \mu over \mathcal{X}\times\{\pm 1\} . We work in the realizable setting: for every n , a random sample \bm{S}=((\bm{x}_{i},\bm{y}_{i}))_{i=1}^{n}\sim\mu^{n} is almost surely realizable by some c\in\mathcal{C} , meaning that c(\bm{x}_{i})=\bm{y}_{i} for all i=1,\ldots,n . 1 1 1 Here, and throughout the paper, we use boldface letters to denote random variables and use the notation (\bm{x},\bm{y})\sim\mu to express that (\bm{x},\bm{y}) is a random variable distributed according to \mu . Note that \mu is a distribution over \mathcal{X}\times\left\{\pm 1\right\} , so none of the labels \bm{y}_{i} take the value \star . The learner’s task is to use the training data to output, with probability at least 1-\delta , a hypothesis h:\mathcal{X}\to\{\pm 1\} whose population loss \loss_{\mu}(h)\coloneqq\Pr_{(\bm{x},\bm{y})\sim\mu}[h(\bm{x})\neq\bm{y}] is at most \epsilon . The following simple lemma from [ AHHM21 ] establishes the connection between realizability and having zero population loss. Lemma 1.1 ( [ AHHM21 ] ) . Let \mathcal{C}\subseteq\left\{\pm 1,\star\right\}^{\mathcal{X}} be a partial concept class, and let \mu be a distribution on \mathcal{X}\times\left\{\pm 1\right\} . If \loss_{\mu}(\mathcal{C})\coloneqq\inf_{c\in\mathcal{C}}\loss_{\mu}(c) is zero, then \mu is realizable by \mathcal{C} . Conversely, if \mu is realizable and has finite or countable support, then \loss_{\mu}(\mathcal{C})=0 . The fundamental theorem of PAC learning states that the size of the training set required for PAC learning a total concept class depends on a combinatorial parameter known as the VC dimension, which we now define in the more general partial setting. A (partial) concept class \mathcal{C}\subseteq\{\pm 1,\star\}^{\mathcal{X}} shatters a set S\subseteq\mathcal{X} if \{c|_{S}:c\in\mathcal{C}\}=\{\pm 1\}^{S} , where c|_{S} denotes the restriction

Read the complete text