Tight list replicability bounds via a novel sphere covering theorem
June 04, 2026
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\).
1 Introduction↩︎
Randomized learning algorithms can produce different hypotheses across multiple executions, even when trained on data drawn from the same distribution. In many contexts, it is desirable for the algorithm to produce consistent outputs across such runs. This idea is also connected to broader discussions of scientific reproducibility, in which repeated experiments are expected to yield consistent conclusions. Motivated by this perspective, a growing body of work in learning theory has introduced formal notions describing when and how randomized algorithms can be made replicable [1]–[12].
One such notion is list replicability, introduced in [3], [4]. Informally, the list replicability number of a concept class is the smallest integer \(L\) for which there exists a learning algorithm whose set of likely output hypotheses has size at most \(L\) under every data distribution. This quantity also characterizes the amount of shared randomness required for replicable learning [13], [14], and has found applications in differentially private learning [15], [16].
Although the definition of list replicability is purely algorithmic, there has been widespread success in reformulating it as a topological property of the space of distributions that are realizable in the given learning task [3], [4], [17]–[20]. This perspective has enabled the use of tools from algebraic topology to derive general bounds on list size. In particular, [17] utilized a local version of the Borsuk-Ulam theorem as a powerful tool to lower-bound list replicability. They showed that for any finite cover of the \(d\)-sphere by antipodal-free open sets, there are at least \(\lceil d / 2 \rceil + 1\) sets with a common nonempty intersection. This sphere covering result was used to show that the list size of any list-replicable learner for a concept class of VC dimension \(d\) is at least \(\lceil d/2\rceil+1\), independent of the accuracy parameter \(\epsilon\in (0,1/2)\). Furthermore, [19] applied the sphere covering result to the class of large-margin half-spaces, showing that its list-replicability number lies between \(\lceil d / 2 \rceil + 1\) and \(d\).
In the local Borsuk–Ulam theorem of [17], the factor of \(1/2\) is inherent and cannot be improved. In contrast, in its application to list-replicability, this factor is an artifact of the proof technique. In particular, the lower bound of \(\lceil d / 2 \rceil + 1\) on the list size is not tight: when the accuracy parameter satisfies \(\epsilon < 1/d\), the list size must be at least \(d\) [3]. Together with the persistent gap between known lower and upper bounds for the list replicability of large-margin halfspaces, this indicates that the appearance of the \(1/2\) factor is due to limitations of the topological tools used so far, rather than an inherent barrier.
We confirm this hypothesis by introducing a novel sphere covering theorem. Instead of merely assuming antipodal-freeness, we impose the stronger condition that each open set in the cover of the \(d\)-sphere is contained in an open hemisphere. Under this assumption, we show that at least \(d+1\) sets must have a common nonempty intersection. This result yields both sharper and more general bounds for list replicability across several settings.
Using our new sphere covering theorem, we prove that the list size of any list-replicable learner for a concept class of VC dimension \(d\) is at least \(d\) for any \(\epsilon < 1/2\). Previously, this bound was only known for \(\epsilon < 1/d\). As a consequence, the optimal list size for the concept class \(\{\pm 1\}^d\) is exactly \(d\), independent of the accuracy parameter \(\epsilon\).
In the setting of large-margin half-spaces, we apply our sphere covering result to show that for margins \(\gamma < 1 / \sqrt{2}\), the list replicability number is exactly \(d\). In contrast, when \(\gamma\) is very close to \(1\), we construct an explicit learner showing that the list replicability number is \(\lceil d / 2 \rceil + 1\). Together, these results show that the lower and upper bounds from [19] are tight in the appropriate parameter regimes.
Finally, we study list replicability for large-margin half-spaces where the learner is restricted to outputting linear classifiers. For such algorithms, we show that the optimal list replicability is \(d\), again matching the upper bound in [19].
1.0.0.1 Paper organization
In 1.1 we collect the fundamental definitions broadly necessary for our main results. Definitions and theorems useful beyond this context are provided in their respective sections.
Our main results are contained in 2. We begin by situating our sphere covering result, [thm:main95topological95result], within the broader framework of topological methods for list replicability. With this result in hand, we turn to our improved lower bound on \(\epsilon\)-list replicability of VC classes in [thm:VC95bound]. Afterwards, we present our new lower and upper bounds on the list replicability number of large-margin half-spaces in [thm:margin95LR95lower95bound] and [thm:very95large95margin]. Finally, an application of our topological result yields a tight lower bound on the list replicability number of linear classifiers in [thm:linear95classifiers].
As the proofs for [thm:VC95bound] [thm:margin95LR95lower95bound] [thm:linear95classifiers] share many similarities, we have extracted those similarities into a framework theorem in 4, and deferred the full proofs to [sec:VC_bound] [sec:margin_LR_lower_bound] [sec:linear_classifiers] respectively.
1.1 Preliminaries↩︎
1.1.0.1 Partial concept classes.
The framework of partial concept classes, introduced by Alon, Hanneke, Holzman, and Moran [21], extends classical learning theory to settings in which the data is guaranteed to satisfy additional structural assumptions that enable efficient learning. In particular, partial concept classes provide a natural framework for our study of large-margin half-spaces.
A partial concept class over an arbitrary domain \(\mathcal{X}\) is a set \(\mathcal{C}\subseteq \{\pm 1, \star\}^{\mathcal{X}}\), where each function \(c \in \mathcal{C}\) is called a partial concept. We say that a partial concept \(c\) is undefined at \(x\) whenever \(c(x)\) takes the star value \(\star\). The support of a partial concept \(c\) is defined to be \(\mathop{\mathrm{supp}}(c)\coloneq\{x\in \mathcal{X}: c(x)\neq \star\}\). Note that a total concept class \(\mathcal{C}\subseteq\{\pm 1\}^{\mathcal{X}}\) is a special case of a partial concept class.
1.1.0.2 PAC learning.
In the probably approximately correct (PAC) learning framework, the learner observes \(n\) independent labeled examples \(S = ((x_1, y_1), \dots, (x_n, y_n))\) sampled from an unknown but fixed distribution \(\mu\) over \(\mathcal{X} \times \{\pm 1\}\). The objective is to produce a hypothesis \(h \colon \mathcal{X} \to \{\pm 1\}\) that, with high probability, performs well on the overall distribution, as measured by the population loss \[\mathop{\mathrm{loss}}_\mu(h) \mathrel{\vcenter{:}}= \mathbb{P}_{(x, y) \sim \mu}[h(x) \neq y].\]
Note that \(\mu\) is a distribution on \(\mathcal{X}\times \{\pm 1\}\), and therefore the learner never observes labels equal to \(\star\). Moreover, the hypothesis produced by the learner should not contain \(\star\) labels, since any such label would automatically be counted as an error.
We define a learning rule to be a (possibly randomized) function \(\mathcal{A}\) that maps any sample \(S \in \bigcup_{n=0}^\infty (\mathcal{X}\times \left\{\pm 1\right\})^n\) to a hypothesis \(\mathcal{A}(S) \in \left\{\pm 1\right\}^{\mathcal{X}}\). Since our primary focus is learnability rather than computational efficiency, we impose no computability constraints on \(\mathcal{A}\).
A distribution \(\mu\) over \(\mathcal{X}\times\{\pm 1\}\) is realizable by a partial concept class \(\mathcal{C}\) if for every \(n\in\mathbb{N}\), a random sample \(S = ((x_i, y_i))_{i=1}^n \sim \mu^n\) is almost surely realizable by some \(c \in \mathcal{C}\), that is, \(c(x_i) = y_i\) for all \(i=1,\ldots,n\).
A partial concept \(\mathcal{C}\) is PAC learnable by a learning rule \(\mathcal{A}\) if for any \(\epsilon,\delta>0\), there exists a sample complexity \(n\coloneq n(\epsilon,\delta)\) such that for any realizable distribution \(\mu\), we have \[\mathbb{P}_{S\sim\mu^n} [\mathop{\mathrm{loss}}_{\mu}(\mathcal{A}(S)) \leq \epsilon] \geq 1-\delta.\]
1.1.0.3 VC dimension.
Let \(A\subseteq \mathcal{X}\) be a subset and \(\mathcal{C}\) be a partial concept class over \(\mathcal{X}\). We say \(\mathcal{C}\) shatters \(A\) if \(\{\pm 1\}^A\subseteq \{c|_A :~ c\in \mathcal{C}\}\). The VC dimension of \(\mathcal{C}\) is defined by \[\mathop{\mathrm{\mathrm{\small vc}}}(\mathcal{C})\coloneq \sup \{ |A| :~A \subseteq \mathcal{X}\text{ is shattered by \mathcal{C}}\}.\] As in the total setting, it is shown in [21] that the finiteness of the VC dimension exactly characterizes PAC learnability for a partial concept class \(\mathcal{C}\). In fact, there exists a learning rule with sample complexity \(O_{\epsilon,\delta}(\mathop{\mathrm{\mathrm{\small vc}}}(\mathcal{C}))\).
1.1.0.4 Large-margin half-spaces.
One of the most prominent examples of a partial concept class is that of large-margin half-spaces. In this setting, we use undefined labels to formalize the large-margin assumption: data points are guaranteed to be well separated.
In the large-margin half-spaces learning problem, the domain is the unit sphere \(\mathbb{S}^{d-1} \subset \mathbb{R}^d\). For each \(w\in\mathbb{S}^{d-1}\), we define a partial concept \[\begin{align} c_w(x) \coloneq \begin{cases} \mathop{\mathrm{sign}}(\langle w, x \rangle) &\text{if } |\langle w, x \rangle| \geq \gamma\\ \star &\text{otherwise} \end{cases}, \end{align}\] where \(\gamma>0\) is the margin parameter. Note that \(c_w\) deems every \(x\) within distance \(\gamma\) from the hyperplane defined by \(w\) as undefined. Otherwise, it assigns \(\pm 1\) depending on which side of the hyperplane \(x\) is on. We denote by \(\mathcal{H}^d_{\gamma}\) the set \(\{c_w : w \in \mathbb{S}^{d-1}\}\) of all \(\gamma\)-margin partial concepts. It is well known from the analysis of the Perceptron algorithm [22], [23] (see also [24] and [21]), that the Littlestone dimension of \(\mathcal{H}^d_{\gamma}\) is bounded by \(1/\gamma^2\). Since the Littlestone dimension is a relaxation of the VC dimension, we also have \[\mathop{\mathrm{\mathrm{\small vc}}}(\mathcal{H}_{\gamma}^d)\leq \frac{1}{\gamma^2}\] which is independent of the dimension \(d\). This implies that under the large-margin assumption \(\gamma>0\), linear classification is efficiently PAC learnable even in high dimensions.
1.1.0.5 List replicability.
List replicability was introduced in [3], [4] as a framework for studying the replicability of a learning problem while preserving the guarantees of PAC learning.
Definition 1 (List replicability). A learning rule \(\mathcal{A}\) is an \((\epsilon,L)\)-list replicable learner* for a partial concept class \(\mathcal{C}\) if for every \(\delta>0\) there exists a sample complexity \(n \coloneq n(\delta)\) such that the following holds. For every distribution \(\mu\) realizable by \(\mathcal{C}\), there exists a list of hypothesis \(h_1,\ldots,h_L \in \left\{\pm 1\right\}^\mathcal{X}\) such that \[\mathop{\mathrm{loss}}_\mu(h_i) \le \epsilon ~\forall i ~\text{ and } ~ \mathbb{P}_{S \sim \mu^n} [\mathcal{A}(S) \in \left\{h_1,\ldots,h_L\right\}] \geq 1-\delta.\] The \(\epsilon\)-list replicability number of \(\mathcal{C}\) is \[\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C},\epsilon) \mathrel{\vcenter{:}}= \min\{L : \exists (\epsilon,L)\text{-list replicable learner for }\mathcal{C}\},\] with \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C},\epsilon)=\infty\) if none exists. The list replicability number of \(\mathcal{C}\) is \[\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C}) \mathrel{\vcenter{:}}= \sup_{\epsilon>0} \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C},\epsilon).\] We say \(\mathcal{C}\) is list replicable if \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C})<\infty\).*
The goal in list replicability is to produce a PAC learner with the smallest possible list size.
1.1.0.6 Space of realizable distributions.
Given a partial concept class \(\mathcal{C}\), we define the set \[\Delta_{\mathcal{C}}\coloneq \{\mu : \mu\;\text{realizable by}\; \mathcal{C}\}\] of all realizable distributions. When equipped with the total variation () distance, \(\Delta_{\mathcal{C}}\) forms a metric space, which we refer to as the space of realizable distributions associated with \(\mathcal{C}\).
1.1.0.7 Topological terminology.
Let \(\mathbb{S}^d\subset \mathbb{R}^{d+1}\) denote the \(d\)-dimensional unit sphere. We say that a set \(U\subseteq \mathbb{S}^d\) is antipodal-free if it does not contain both a point \(x\) and its antipode \(-x\). We say a cover \(\mathcal{U}=\{U_i\}_{i\in I}\) of \(\mathbb{S}^d\) is antipodal-free if \(U_i\) is antipodal-free for all \(i\in I\).
The overlap degree of a cover \(\mathcal{U}=\{U_i\}_{i\in I}\) is the largest integer \(k\) for which there exists \(k\) sets \(U_1, \dots, U_k\in \mathcal{U}\) such that \(\bigcap_{i=1}^k U_i\neq \varnothing\).
If \(\mathcal{U}=\{U_i\}_{i \in I}\) is an open cover, then a partition of unity subordinate to \(\mathcal{U}\) is a collection of continuous maps \(f_i \colon \mathbb{S}^d \to [0, 1]\) such that the support of \(f_i\) is contained in \(U_i\) for each \(i \in I\), and \(f_1 + \dots + f_m = 1\).
Any point \(p \in \mathbb{S}^d\) defines a unique orthogonal homogeneous hyperplane in \(\mathbb{R}^{d+1}\) given by \[P = \{x \in \mathbb{R}^{d+1} : {\left\langle p,x \right\rangle} = 0\}.\] For each point \(w \neq p\) in \(\mathbb{S}^d\), there is a unique line through \(p\) and \(w\), which intersects the plane \(P\) in a unique point \(w'\). The stereographic projection through \(p\) is the injective map \(\pi \colon \mathbb{S}^d \setminus \{p\} \to P \cong \mathbb{R}^d\) given by taking \(w \in \mathbb{S}^d\) to \(w' \in P\).
2 Main Results↩︎
2.1 Lower-bounding list replicability via topology↩︎
The most well-established strategy to lower-bound the \(\epsilon\)-list replicability number \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C},\epsilon)\) of a class \(\mathcal{C}\) hinges on exploiting the topological structure of its space of realizable distributions \(\Delta_{\mathcal{C}}\).
This method was independently introduced by Chase, Moran, and Yehudayoff [3] and by Dixon, Pavan, Woude, and Vinodchandarn [4], and was subsequently refined and extended in [17]–[20], [25] to address a broader range of problems. These works employ a variety of topological results, such as the Poincaré-Miranda theorem [3], KKM/Sperner’s Lemma [4], [25], a Local Borsuk-Ulam theorem [17]–[19], and Lebesgue’s covering theorem [20], to obtain lower bounds on the list replicability number of a variety of concept classes.
In this vein, our first contribution is a sphere-covering result on the overlap degree of open covers with small diameters.
theorembutheorem Let \(A_1, \dots, A_m\) be a finite open cover of the \(d\)-sphere \(\mathbb{S}^d\), where each \(A_i\) is contained in an open hemisphere. Then \(d+1\) of these sets have a common nonempty intersection.
We refer the reader to 1 for a precise framework detailing the use of [thm:main95topological95result] in proving lower bounds for list replicability.
2.2 List replicability of finite VC classes↩︎
In [17], Chase, Chornomaz, Moran, and Yehudayoff asked whether concept classes with finite VC dimension can be learned in a list-replicable way with a small list size when the accuracy parameter \(\epsilon\) is large. The following bounds are known:
Theorem 1 ([3], [17]). Let \(\mathcal{C}\) be a concept class with \(\mathop{\mathrm{\mathrm{\small vc}}}\) dimension \(d\). Then \[\begin{align} \text{for \epsilon < \frac{1}{2},}~ \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C}, \epsilon) &\geq \frac{d}{2} + 1\\ \text{whereas for \epsilon < \frac{1}{d},}~ \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C}, \epsilon) &\geq d. \end{align}\]
Our first application of [thm:main95topological95result] is to show that \(d\) is the correct lower bound for the full range \(\epsilon \in [0,1/2)\).
atheoremtheoremA Let \(\mathcal{C}\) be a (partial) concept class with \(\mathop{\mathrm{\mathrm{\small vc}}}\) dimension \(d\). \[\text{For any \epsilon < \frac{1}{2},}~ \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C}, \epsilon) \geq d.\]
Note that for the binary cube \(\mathcal{C}= \{\pm 1\}^d\), we have \(\mathop{\mathrm{\mathrm{\small vc}}}(\mathcal{C}) = d\) and \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C}, \epsilon) \le d\) for all \(\epsilon < 1/2\) [3]. Consequently, [thm:VC95bound] implies that the \(\epsilon\)-list replicability number of the binary cube equals \(d\) for all \(\epsilon < 1/2\). In other words, increasing the accuracy parameter \(\epsilon\) does not yield any improvement in list replicability for some finite VC classes.
2.3 List replicability of large-margin half-spaces↩︎
The list replicability number of a concept class provides bounds on various learning theory and communication complexity parameters such as VC dimension [3], [17], Littlestone dimension [15], [26]3, and sign-rank [19], [20]. In particular, several previously open questions in these areas were resolved by studying the list replicability number of large-margin half-spaces [19]. The explicit bounds on the list replicability number of the class depended only on the underlying dimension \(d\) of the problem:
Theorem 2 ([19]). For any fixed dimension \(d>1\), margin \(\gamma \in (0,1)\), and accuracy parameter \(\epsilon \in (0,1/2)\), \[\left \lceil\frac{d}{2}\right \rceil+1 \leq \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d,\epsilon) \leq d.\] Hence, \(\left \lceil\frac{d}{2}\right \rceil+1 \leq \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d) \leq d\).
These general bounds left open the question of precisely how the margin \(\gamma\) and accuracy parameter \(\epsilon\) affect the \(\epsilon\)-list replicability number, if at all. We give a partial answer to this question. Our second application of [thm:main95topological95result] improves the lower bounds for \(\epsilon\)-list replicability of large-margin half-spaces for a wide range of margins \(\gamma\). This determines the exact value of the list replicability number in this range.
atheoremmarginlowerbound For any dimension \(d > 1\) and margin \(\gamma \in (0, \frac{1}{\sqrt{2}})\), there exists an accuracy parameter \(\epsilon \mathrel{\vcenter{:}}= \epsilon(\gamma, d)\) such that \[\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}^d_\gamma, \epsilon) \geq d.\] Hence, \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d)=d\) for all \(\gamma\in (0,1/\sqrt{2})\).
As a complement to this result, we examine the setting in which the margin \(\gamma\) is relatively large. In this setting, we prove a tight upper bound on the \(\epsilon\)-list replicability number.
atheoremmarginupperbound For any dimension \(d > 1\) and accuracy parameter \(\epsilon\in [0,1/2)\), there exists some \(\gamma_0\coloneq \gamma_0(d) \in(0,1)\) such that for any margin \(\gamma\in (\gamma_0,1)\) we have \[\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}^d_\gamma, \epsilon) \leq \left \lceil\frac{d}{2}\right \rceil+1.\] Hence, \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d)=\lceil \frac{d}{2}\rceil+1\) for all \(\gamma\in (\gamma_0(d),1)\).
This proof uses an explicit learning rule which exploits a particular cover originally given by Chase, Chornomaz, Moran, and Yehudayoff ([17], see 4 for a description), in conjunction with the Lebesgue Number Lemma (5).
Linear classifiers↩︎
Our third and final application of [thm:main95topological95result] addresses the question of list-replicably learning the large-margin half-space problem with linear classifiers. A hypothesis on the domain \(\mathbb{S}^{d-1}\) is a linear classifier if it is of the form \[\begin{align} h_w(x) \coloneq \begin{cases} 1 &\text{if } \langle w, x \rangle \geq 0,\\ -1 &\text{if } \langle w, x \rangle < 0 \end{cases} \end{align}\] for some \(w \in \mathbb{S}^{d-1}\).
The upper bound \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}^d_\gamma, \epsilon) \leq d\) from 2 uses a learning rule which always outputs a linear classifier. We show that, under that restriction, a list of size \(d\) is best possible.
atheoremlinearclassifiers Fix a dimension \(d > 1\) and a margin \(\gamma \in (0,1)\). For any error parameter \(\epsilon \in (0,1/2)\) and list length \(L > 1\), if \(\mathcal{A}\) is an \((\epsilon,L)\)-list replicable learner for \(\mathcal{H}^d_\gamma\) which outputs linear classifiers, then \(L \geq d\).
2.4 Open Questions↩︎
In [thm:VC95bound], we remove the optimal lower bound’s dependency on \(\epsilon\), while we get a new dependency on \(\epsilon\) in the lower bound of \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d, \epsilon)\). We wonder if list replicability varies with \(\epsilon\).
Question 1. Is there a total or partial concept class \(\mathcal{C}\) and two error parameters \(\epsilon_1, \epsilon_2 \in (0, \frac{1}{2})\) with \(\epsilon_1 < \epsilon_2\) such that \[\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C}, \epsilon_1) > \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C}, \epsilon_2)?\]
While we have solved \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d)\) for many of the most applicable regimes, the behaviour of the list replicability number is merely bounded in other regimes. Looking at 1, we ask what the transition between the top and bottom regimes looks like.
Question 2. For which parameters can the bound \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d, \epsilon) = d\) be established?
Question 3. Are there values of \(\gamma \in (0, 1), \epsilon \in (0, \frac{1}{2})\) such that \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d, \epsilon)\) takes on every integer value in the range \([\lceil \frac{d}{2} \rceil + 1, d]\)?
![Figure 1: Regimes for \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d, \epsilon) when d>1. When \gamma < \frac{1}{\sqrt{d}}, it is well known that \mathop{\mathrm{\mathrm{\small vc}}}(\mathcal{H}_\gamma^d) = d, so we know from [thm:VC95bound] that \mathop{\mathrm{\mathrm{\small lr}}}= d.](/article/2606.06148/_pdflatex/fbjluvie.png "fig:")
3 Proof of [thm:main95topological95result]↩︎
In this section, we prove our main topological result.
We will use the following classical form of the Borsuk-Ulam theorem.
Theorem 3 ([27]). For every continuous mapping \(f \colon \mathbb{S}^d\rightarrow\mathbb{R}^d\), there exists a point \(x\in\mathbb{S}^d\) with \(f(x)=f(-x)\).
Proof of [thm:main95topological95result]:. Let \(\mathcal{A}= \{A_1, \dots, A_m\}\) be a finite open cover of \(\mathbb{S}^d\) such that there exist \(u_1, \dots, u_m \in \mathbb{S}^d\) with \[A_i \subseteq \{x \in \mathbb{S}^d: \langle x, u_i \rangle > 0\}.\]
Since \(\mathbb{S}^d\) is a compact Hausdorff space, there is a partition of unity subordinate to \(\mathcal{A}\) [28]. That is, there exist continuous maps \(f_i \colon \mathbb{S}^d \to [0, 1]\) such that the support of \(f_i\) is contained in \(A_i\) for each \(i\), and \(f_1 + \dots + f_m = 1\).
Consider the continuous map \(g \colon \mathbb{S}^d \to \mathbb{R}^{d+1}\) given by \[g(x) \coloneq \sum_{i=1}^m f_i(x) u_i.\] Note that \(\langle x, g(x)\rangle > 0\) for all \(x\), and in particular \(g\) is never zero. It follows that \(h(x) \coloneq g(x)/\left|\!\left|g(x)\right|\!\right|\) is a well-defined, continuous map from \(\mathbb{S}^d\) to \(\mathbb{S}^d \subset \mathbb{R}^{d+1}\). Moreover, \(h\) inherits the property that \(\langle x, h(x) \rangle > 0\) for all \(x\).
We claim that \(h\) must be surjective. Indeed, assuming otherwise, let \(p \in \mathbb{S}^d\) be a point outside the image of \(h\), and let \(\pi \colon \mathbb{S}^d \to \mathbb{R}^d\) be the stereographic projection through \(p\). By 3, the continuous map \(\pi \circ h \colon \mathbb{S}^d \to \mathbb{R}^d\) must identify some antipodal pair \(w\) and \(-w\). Since stereographic projection is bijective, it follows that \(h(w) = h(-w)\). This contradicts the fact that \(\langle x, h(x) \rangle > 0\) for all \(x\).
To complete the proof, we will show that the surjectivity of \(h\) guarantees the overlap of at least \(d+1\) sets of \(\mathcal{A}\). The image of \(g\) is a subset of the space \(T\), composed of the union of a finite number of convex sets. \[\begin{align} T &\mathrel{\vcenter{:}}= \bigcup ~\{\sigma_S : \text{for all}~S \subset [m] ~\text{where}~ \bigcap_{i \in S} A_i \neq 0\}\\ \text{where}~ \sigma_S &\mathrel{\vcenter{:}}= \mathop{\mathrm{conv}}\{u_i: i \in S\} \end{align}\] Since we only consider \(S\) where the corresponding open sets overlap, for each \(S\) there is some \(x_S\) with \(\langle x_S, u_i \rangle > 0\) for all \(i\) in \(S\). This means that \(\sigma_S\) doesn’t intersect \(0\), and its radial projection onto the sphere lies in a vector space of dimension at most \(|S|\): \[\begin{align} \left\{\frac{x}{|x|}: x \in \sigma_S\right\} \subseteq \mathbb{S}^d \cap \mathop{\mathrm{span}}\{u_i : i \in S\}. \end{align}\] Finally, if this vector space has dimension less than \(d+1\), its intersection with \(\mathbb{S}^d\) has measure \(0\) in \(\mathbb{S}^d\). Therefore, if no \(d+1\) sets intersect, then the image of \(h\) is contained in a finite union of sets with \(0\) measure, which itself has \(0\) measure, contradicting its surjectivity. ◻
4 The topological method in list replicability↩︎
In this section, we describe a framework for applying [thm:main95topological95result] to obtain lower bounds on list replicability. This framework is applied to prove [thm:VC95bound] [thm:margin95LR95lower95bound] [thm:linear95classifiers], so we explain it in detail, with its applications deferred to [sec:VC_bound] [sec:margin_LR_lower_bound] [sec:linear_classifiers] respectively.
The overarching strategy begins by identifying a subset of realizable distributions, \(\Delta\), that, when endowed with the total variation metric, is homeomorphic to a high-dimensional sphere or ball. The existence of an \((\epsilon,L)\)-list replicable algorithm \(\mathcal{A}\) then induces an open cover \(\mathcal{U}\) of this subset whose overlap degree lower bounds the list size \(L\). If \(\mathcal{U}\) satisfies additional structural constraints, such as bounds on the size of the open sets or antipodal freeness, then we invoke a suitable sphere covering theorem to show that any open cover satisfying these properties must exhibit a large overlap, thereby yielding the desired lower bound.
For our purposes, [thm:main95topological95result] is the appropriate sphere covering theorem. Our specific realization of the strategy above is described in the following lemma.
Lemma 1. Let \(\mathcal{A}\) be an \((\epsilon,L)\)-list replicable learning algorithm for a concept class \(\mathcal{C}\subseteq \{\pm 1,\star\}^\mathcal{X}\) with sample complexity \(n \mathrel{\vcenter{:}}= n(\delta)\). Fix a dimension \(d \geq 1\) and a confidence parameter \(\delta \leq \frac{1}{2d}\), and suppose that, for some subset of realizable distributions \(\Delta \subseteq \Delta_\mathcal{C}\), there is a continuous map \(\varphi \colon \mathbb{S}^{d-1} \to \Delta\).
If there is an \(\epsilon_0 > \epsilon\) such that, for every output \(h\) of \(\mathcal{A}\), the set \[U_h \mathrel{\vcenter{:}}= \left\{ w \in \mathbb{S}^{d-1} ~:~ \mathbb{P}_{S \sim \varphi(w)^n}[\mathcal{A}(S) = h] > \frac{1-2\delta}{L} ~\text{and}~ \mathop{\mathrm{loss}}_{\varphi(w)}(h) < \epsilon_0 \right\}\] is contained in an open hemisphere of \(\mathbb{S}^{d-1}\), then \(L \geq d\). If this holds for any \(\mathcal{A}\) then \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C},\epsilon) \geq d\).
Each set \(U_h\) collects all points in \(\mathbb{S}^{d-1}\) which, under \(\varphi\), encode distributions for which \(h\) is a “likely” and “accurate” output of \(\mathcal{A}\). In application the size of these sets will be controlled with \(\varepsilon\), whereas the other parameters \(\delta\), \(n\), and \(\mathcal{A}\) are less impactful.
Proof. First, we will show that the family \(\mathcal{U}\) is open. Let \(X\) be the set of realizable distributions \(x\) for which \(\mathop{\mathrm{loss}}_x(h) < \epsilon_0\). Since \(\mathop{\mathrm{loss}}\) is a continuous function, \(X\) is open with respect to TV distance. Similarly, \(\varphi^{-1}(X)\) is in turn open because of the continuity of \(\varphi\). Note that \(\varphi^{-1}(X)\) is exactly those \(w \in \mathbb{S}^{d-1}\) satisfying \(\mathop{\mathrm{loss}}_{\varphi(w)}(h) < \epsilon_0\). An analogous argument shows that the set of \(w \in \mathbb{S}^{d-1}\) satisfying \(\mathbb{P}_{S \sim \varphi(w)^n} [\mathcal{A}(S) = h] > \frac{1-2\delta}{L}\) is also open. Therefore, each \(U_h\) is open because it is the intersection of two open sets.
Second, we will show how the \((\epsilon,L)\)-list replicability of \(\mathcal{A}\) guarantees that \(\mathcal{U}\) is a cover. For any element \(w \in \mathbb{S}^{d-1}\), the distribution \(\varphi(w)\) is realizable by the definition of \(\varphi\). The list replicability assumption guarantees some set of hypotheses \(\{h_1, \dots, h_L\}\) for which \(\mathbb{P}_{S \sim\varphi(w)^n} [\mathcal{A}(S) \in \{h_1, \dots, h_L\}] \geq 1-\delta\) and \(\mathop{\mathrm{loss}}_{\varphi(w)}(h_i) \leq \epsilon\). It follows by the pigeonhole principle that there is some \(h\) in \(\{h_1, \dots, h_L\}\) such that \(U_h\) contains \(w\).
Finally, we will show the desired lower bound on \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C},\epsilon)\). By assumption, each \(U_h\) is contained in an open hemisphere. Therefore, [thm:main95topological95result] guarantees some \(w \in \mathbb{S}^{d-1}\) is contained in \(d\) sets of \(\mathcal{U}\). By construction, there are \(d\) distinct hypotheses \(h_1, \dots, h_d\) and a distribution \(\varphi(w)\) such that \[\mathbb{P}_{S \sim\varphi(w)^n} [\mathcal{A}(S) = h_i] > \frac{1-2\delta}{L} \;\,\text{for all}\;\,i \in [d].\] Since the events \([\mathcal{A}(S) = h_i]\) are disjoint, we have that \[1>\frac{d(1-2\delta)}{L}\geq \frac{d(1-1/d)}{L}=\frac{d-1}{L},\] since \(\delta \leq 1/2d\). It follows that \(L \geq d\). If this is true for arbitrary \(\mathcal{A}\), we conclude that \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C},\epsilon) \geq d\) by the definition of the \(\epsilon\)-list replicability number. ◻
5 Proof of [thm:VC95bound]↩︎
Proof. By definition of \(\mathop{\mathrm{\mathrm{\small vc}}}\) dimension, the concept class \(\mathcal{C}\) contains the class \(\mathcal{P}\mathrel{\vcenter{:}}= \{\pm 1\}^{[d]}\) as a subclass. It is quick to check that, for every \(\epsilon\), \[\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{C}, \epsilon) \geq \mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{P}, \epsilon),\] so we restrict ourselves to the analysis of \(\mathcal{P}\).
Arguing by way of 1, first note that the set of realizable distributions \(\Delta_{\mathcal{P}}\) with the metric of total variation distance is homeomorphic to \(\mathbb{S}^{d-1}\) (Here \(\{e_i\}_i\) is the unit vector for the \(i\)th dimension in \(\mathbb{R}^d\)): \[\begin{align} p : \Delta_\mathcal{P}&\to \mathbb{S}^{d-1}\\ \mu &\mapsto \frac{\sum_i e_i[\mu(i, +) - \mu(i, -)]}{\sqrt{\sum_i [\mu(i, +) - \mu(i, -)]^2}} \end{align}\] Note that this map is a homeomorphism precisely because only one of \(\mu(i, +), \mu(i, -)\) can be non-zero at a time.
What is left is to check that, for any \(\epsilon < \frac{1}{2}\), each set \(U_h\) is contained in a hemisphere \[\begin{align} \{x \in \mathbb{S}^{d-1} : \langle x, u_h \rangle > 0\}\\ \text{where}~ u_h = (h(1), h(2), \dots, h(d)) \end{align}\] For a realizable distribution \(\mu\) and a hypothesis \(h\), the loss of \(h\) on \(\mu\) can be calculated as \[\begin{align} \mathop{\mathrm{loss}}_\mu(h) = \frac{1}{2} \left( 1 + \sum_i h(i) \left[ \mu(i, -) - \mu(i, +) \right] \right). \end{align}\] If \(p(\mu) \in U_h\), then \(\mathop{\mathrm{loss}}_\mu(h)\) is less than \(\frac{1}{2}\), so \[\begin{align} \sum_i h(i) \left[ \mu(i, +) - \mu(i, -) \right] > 0. \end{align}\] Finally, we get that \[\begin{align} \langle u_h, p(\mu) \rangle &= \frac{\sum_i h(i) \cdot [\mu(i, +) - \mu(i, -)]}{\sqrt{\sum_i [\mu(i, +) - \mu(i, -)]^2}} > 0. \qedhere \end{align}\] ◻
6 Proof of [thm:margin95LR95lower95bound]↩︎
Fix \(d\). Pick any \(\gamma\in(0,1/\sqrt{2})\). The lower bound follows from trying to learn the collection of realizable distributions \(\Delta \mathrel{\vcenter{:}}= \{\mu_w : w \in \mathbb{S}^{d-1}\}\), where \(\mu_w\) is the uniform distribution on \[\left\{(x, c_w(x)) : x\in \mathop{\mathrm{supp}}(c_w)\right\}.\] The map \(\varphi\colon \mathbb{S}^{d-1} \rightarrow \Delta\) defined by \(w \mapsto \mu_w\) is a homeomorphism.
Denote by \(\nu\) the spherical measure, that is, the uniformly distributed measure on \(\mathbb{S}^{d-1}\), normalized so that \(\nu(\mathbb{S}^{d-1})=1\). For each \(x\in \mathbb{S}^{d-1}\), let \((x_1,\dots,x_d)\) be its coordinates in \(\mathbb{R}^{d}\). Define \[\epsilon \coloneq \nu(\{ x\in\mathbb{S}^{d-1} ~:~ x_1 \geq \gamma, ~x_2 \leq -\gamma \}) ~\text{and}~ \epsilon_0 \coloneq \frac{ \nu(\{ x \in \mathbb{S}^{d-1} ~\colon~ x_1 \geq \gamma, ~x_2\leq -\gamma \}) }{ \nu(\{x\in\mathbb{S}^{d-1}\,\colon\,|x_1|\geq\gamma\}) }.\]
It is not hard to see that both \(\epsilon_0\) and \(\epsilon\) are strictly positive and \(\epsilon_0>\epsilon\) when \(\gamma \in (0,1/\sqrt{2})\).
Now suppose \(\mathcal{A}\) is an \((\epsilon,L)\)-list replicable learner for \(\mathcal{H}_\gamma^d\). Let \(T \subseteq \{\pm 1\}^{\mathbb{S}^{d-1}}\) be the collection of all possible hypotheses output by \(\mathcal{A}\). For each hypothesis \(h \in T\), define the set \(U_h\) \[\begin{align} U_h &= \left\{ w \in \mathbb{S}^{d-1} ~:~ \mathbb{P}_{S \sim \mu_w^{n}} [ \mathcal{A}(S) = h ] > \frac{1-2\delta}{L},\,\mathop{\mathrm{loss}}_{\mu_w}(h)<\epsilon_0 \right\} \end{align}\] of distributions on which \(\mathcal{A}\) is likely to output \(h\).
Claim 4. For each \(h\in T\), if \(u,w \in U_h\), then \(\langle u, w \rangle > 0\). In particular, \(U_h\) is contained in an open hemisphere.
Proof of Claim.. Let \(u, w \in U_h\). Define the set on which \(c_u\) and \(c_{w}\) disagree: \[\mathcal{E}_{u, w} \mathrel{\vcenter{:}}= \{x \in \mathop{\mathrm{supp}}c_u \cap \mathop{\mathrm{supp}}c_{w} : c_u(x) \neq c_{w}(x)\}.\] We have \[\label{eq:error95support} \begin{align} \nu(\mathcal{E}_{u, w}) &=\nu(\mathop{\mathrm{supp}}(c_w))\frac{\nu(\mathcal{E}_{u,w})}{\nu(\mathop{\mathrm{supp}}(c_w))}\\ & \leq \nu(\mathop{\mathrm{supp}}(c_w))(\mathop{\mathrm{loss}}_{\mu_u}(h) + \mathop{\mathrm{loss}}_{\mu_{w}}(h)) \\ &< \nu(\mathop{\mathrm{supp}}(c_w)) 2\epsilon_0 \\ &= 2\epsilon. \end{align}\tag{1}\] The first inequality is implied by the fact that \(h\) is not consistent with either \(\mu_u\) or \(\mu_{w}\) on each point in \(\mathcal{E}_{u,w}\). The second inequality follows directly from our definition of \(U_h\). The last equality is a consequence of \(\nu(\mathop{\mathrm{supp}}(c_w))=\nu(\{x\in \mathbb{S}^{d-1}:|x_1|\geq \gamma\})\) for any \(w\) and our definitions of \(\epsilon\) and \(\epsilon_0\).
Now let \(\theta \mathrel{\vcenter{:}}= \arccos(\langle u, w \rangle)\) be the angle between \(u\) and \(w\). We have \[\label{eq:error95support95equality} \begin{align} \nu(\mathcal{E}_{u, w}) &=\nu(\{x \in \mathop{\mathrm{supp}}c_u \cap \mathop{\mathrm{supp}}c_{w} : c_u(x) \neq c_{w}(x)\}) = \\ & = 2\nu(\{x\in \mathbb{S}^{d-1}\,\colon \langle u,x\rangle\geq\gamma,\langle w,x\rangle\leq-\gamma\})= \\ & = 2\nu(\{x\in \mathbb{S}^{d-1}\,\colon x_1\geq\gamma,\cos(\theta)x_1+\sin(\theta)x_2\leq-\gamma\}) \end{align}\tag{2}\] where the last equality follows from the rotational invariance of the spherical measure.
For the sake of contradiction, assume that \(\theta \in [\pi/2,\pi]\). Next we show \[\label{eq:inclusion95angle} \nu(\{x\in\mathbb{S}^{d-1}\,\colon x_1\geq\gamma,\,x_2\leq-\gamma\}) \subseteq \nu(\{x\in\mathbb{S}^{d-1}\;\colon x_1\geq\gamma,\cos(\theta)x_1+\sin(\theta)x_2\leq-\gamma\}).\tag{3}\] Indeed, it is enough to check \(\cos(\theta)x_1+\sin(\theta)x_2\leq-\gamma\) assuming \(x_1\geq\gamma\) and \(x_2\leq-\gamma\). Since \(\theta\in[\pi/2,\pi]\), cosine is non-positive and sine is non-negative. Thus, we only need to verify \(\sin(\theta)-\cos(\theta)\geq1\). Since, the left hand-side is non-negative, we square both sides to get \[\sin^2(\theta)-2\sin(\theta)\cos(\theta)+\cos^2(\theta)\geq 1\] which holds as \(\theta\in[\pi/2,\pi]\). We conclude that the inclusion in 3 holds.
Now by 2 and 3 , we have \[\label{eq:lower95measure} \nu(\mathcal{E}_{u,w})\geq 2\nu(\{x\in\mathbb{S}^{d-1}\,\colon x_1\geq\gamma,\,x_2\leq-\gamma\}) =2\epsilon.\tag{4}\] Finally, by 1 and 4 , we have \(2\epsilon\leq\nu(\mathcal{E}_{u,w})<2\epsilon\) which is a contradiction. Thus, if \(u, w \in U_h\), then \(\theta < \frac{\pi}{2}\), and so \(\langle u, w \rangle > 0\). ◻
Having proved 4, we have that 1 implies [thm:margin95LR95lower95bound].
Remark 5. Examining the relationship between \(\epsilon\) and \(\gamma\) in the above proof, we can see that, for any dimension \(d>1\), there exists a continuous decreasing function \(\epsilon\colon(0,1/\sqrt{2}) \rightarrow (0,1/4)\) such that: \(\epsilon(\gamma)\rightarrow1/4\) as \(\gamma \rightarrow 0^+\), \(\epsilon(\gamma)\rightarrow0\) as \(\gamma \rightarrow {(1/\sqrt{2})}^-\), and \(\mathop{\mathrm{\mathrm{\small lr}}}(\mathcal{H}_\gamma^d, \epsilon(\gamma)) \geq d\) for any \(\gamma \in (0,1/\sqrt{2})\). This justifies the depiction of the boundary between the lower green and middle yellow regions in 1.
7 Proof of [thm:very95large95margin]↩︎
Before we begin, we introduce some basic notation. We endow \(\mathbb{S}^{d-1}\) with the \(\ell_2\) metric and for each \(x\in\mathbb{S}^{d-1}\) and all \(\eta>0\) we denote by \(B(\eta,x)\) all points in \(\mathbb{S}^{d-1}\) which are less than \(\eta\) away from \(x\).
For each realizable distribution \(\mu\), let \(\mathop{\mathrm{supp}}(\mu)\) denote its support. We define \[\mathop{\mathrm{supp}}^{+}(\mu)\mathrel{\vcenter{:}}= \{x \in \mathbb{S}^{d-1}\colon(x,1)\in\mathop{\mathrm{supp}}(\mu)\}\] to be the positive label support of \(\mu\), and likewise for \(\mathop{\mathrm{supp}}^{-}(\mu)\).
Next, we present some topological results that will be used in the proof.
Theorem 4 ([17]). There exists a finite antipodal-free open cover \(\mathcal{U}\mathrel{\vcenter{:}}= \{U_i\}_{i=1}^{n}\) of \(\mathbb{S}^{d-1}\) such that each point \(x\in\mathbb{S}^{d-1}\) is contained in at most \(\left \lceil \frac{d}{2}\right \rceil+1\) of the sets \(U_i\).
We also utilize the following standard result in the theory of compact metric spaces.
Theorem 5 (Lebesgue Number Lemma). Let \((X,d)\) be a compact metric space, and let \(\mathcal{U}\) be an open cover of \(X\). Then there exists a number \(\eta > 0\) such that for every \(x \in X\), the open ball \(B(x,\eta)\) is contained in some \(U \in \mathcal{U}\).
Proof. Since \(X\) is compact, we can assume without loss of generality that the cover \(\mathcal{U}\) is finite. Define the function \(f(x)\coloneq \max_{i\in I}d(x,U_i^c)\). By the continuity of \(f\) and compactness of \(X\), it follows that \(f\) must achieve its minimum. The minimum cannot be zero as \(\mathcal{U}\) is a cover. Taking \(\eta\) to be the minimum of \(f\) completes the proof. ◻
Finally, we present the proof [thm:very95large95margin].
Proof of [thm:very95large95margin]. Pick any \(\epsilon\in[0,1/2)\).
Let \(\mathcal{U}\) be the antipodal-free open cover \(\mathcal{U}\) of \(\mathbb{S}^{d-1}\) from 4. By 5, there exists a \(\eta>0\) such that each ball \(B(\eta,x)\) is contained in some \(U_i\).
Pick \(\gamma(d)>0\) to be sufficiently close to \(1\) so that for any realizable distribution \(\mu\) there exist a point \(w_{\mu}\in\mathbb{S}^{d-1}\) for which the following containments hold: \[\mathop{\mathrm{supp}}^+(\mu)\subseteq B(\eta/2,w_{\mu})~~\text{and}~~ \mathop{\mathrm{supp}}^-(\mu)\subseteq B(\eta/2,-w_{\mu}).\]
Next we construct a \((0,\left \lceil \frac{d}{2}\right \rceil+1)\)-list replicable algorithm with sample complexity \(1\).
Sample one point \((x,y)\) from \(\mu\). Let \[u(x,y)\coloneq \begin{cases} x & \text{for}~ y=1\\ -x & \text{for} ~y=-1\end{cases}\]
Find the smallest index \(i\) for which \(B(\eta,u)\subseteq U_i\) for some \(U_i \in \mathcal{U}\). Such an \(i\) is guaranteed to exist by the Lebesgue Number Lemma (5).
Output the signed indicator hypothesis \[h_{U_i}(x)\coloneq \begin{cases} 1 & \text{for} ~x\in U_i\\ -1 & \text{for} ~ x\in U_i^c\end{cases}\]
Firstly, we show accuracy. With probability \(1\) we have the chains of containments \[\label{eq:32containments951} \mathop{\mathrm{supp}}^+(\mu)\subseteq B(\eta/2,w_{\mu})\subseteq B(\eta,u)\subseteq U_i\tag{5}\] \[\mathop{\mathrm{supp}}^-(\mu)\subseteq B(\eta/2,-w_{\mu})\subseteq B(\eta,-u)\subseteq U_i^c\] where the second containment in both chains follows from the fact that \(u\in B(\eta/2,w_{\mu})\), and the third containment in the second chain follows from the property that \(\mathcal{U}\) is antipodal free. We conclude \(h_{U_i}(x)\) achieves zero error with probability 1.
Finally, we check the list replicability. With probability 1 we have \(B(\eta/2,w_{\mu})\subseteq U_i\) and, in particular, \(w_{\mu}\in U_i\). By 4, there could be at most \(\left \lceil \frac{d}{2}\right \rceil+1\) sets \(U_j\in \mathcal{U}\) containing \(w_{\mu}\). Hence, with probability \(1\), we output from a list of \(\left \lceil \frac{d}{2}\right \rceil+1\) different hypotheses. ◻
8 Proof of [thm:linear95classifiers]↩︎
Proof. Consider the set of realizable distributions \(\Delta \mathrel{\vcenter{:}}= \{\mu_w : w \in \mathbb{S}^{d-1}\}\), where \(\mu_w\) is the uniform distribution on \[\left\{(x, c_w(x)) : x\in \mathop{\mathrm{supp}}(c_w)\right\}.\] The map \(\varphi\colon \mathbb{S}^{d-1} \rightarrow \Delta\) defined by \(w \mapsto \mu_w\) is a homeomorphism.
By assumption \(\mathcal{A}\) outputs linear classifiers of the form \[\begin{align} h_w(x) \coloneq \begin{cases} 1 &\text{if } {\left\langle w,x \right\rangle} \geq 0,\\ -1 &\text{if } {\left\langle w,x \right\rangle} < 0 \end{cases} \end{align}\] for some \(w \in \mathbb{S}^{d-1}\). Fix \(\epsilon < \epsilon_0 < 1/2\). For any such output \(h_w\), we will show that the set \[U_{h_w} \mathrel{\vcenter{:}}= \left\{ y \in \mathbb{S}^{d-1} ~:~ \mathbb{P}_{S \sim \varphi(y)^n}[\mathcal{A}(S) = h_w] > \frac{1-2\delta}{d-1} ~\text{and}~ \mathop{\mathrm{loss}}_{\varphi(y)}(h_w) < \epsilon_0 \right\}\] is contained in the open hemisphere \[H_w \mathrel{\vcenter{:}}= \left\{y \in \mathbb{S}^{d-1} : {\left\langle w,y \right\rangle} > 0\right\} .\] Indeed, if \({\left\langle w,y \right\rangle} \leq 0\), then \(h_w\) correctly labels no more than half of the support of \(\varphi(y)\). Since \(\varphi(y)\) is a uniform distribution, it follows that \(\mathop{\mathrm{loss}}_{\varphi(y)}(h_w) \geq 1/2 > \epsilon_0\). We deduce that \(U_{h_w} \subseteq H_w\), so applying 1 completes the proof. ◻