# Metric-valued regression

Dan Tsir Cohen and Aryeh Kontorovich
dantsir<EMAIL_ADDRESS>
###### Abstract

We propose an efficient algorithm for learning mappings between two metric
spaces, ${\cal X}$ and ${\cal Y}$. Our procedure is strongly Bayes-consistent
whenever ${\cal X}$ and ${\cal Y}$ are topologically separable and ${\cal Y}$
is “bounded in expectation” (our term; the separability assumption can be
somewhat weakened). At this level of generality, ours is the first such
learnability result for unbounded loss in the agnostic setting. Our technique
is based on metric medoids (a variant of Fréchet means) and presents a
significant departure from existing methods, which, as we demonstrate, fail to
achieve Bayes-consistency on general instance- and label-space metrics. Our
proofs introduce the technique of semi-stable compression, which may be of
independent interest.

##  1 Introduction

Regression and multiclass classification fall under the rubric of supervised
prediction from labeled examples. The chief difference between the two is that
classification typically assumes the discrete metric on the label space
(captured by the 0-1 loss), while regression (at least with absolute loss111
Quadratic loss can be captured by the inframetrics (Fraigniaud et al., 2008)
or near-metrics (Hanneke, 2021b).) implicitly assumes the standard metric over
the real-valued labels. In this paper, we study the considerably more general
setting of metric-valued regression, where the labels reside in an arbitrary
metric space. This setting subsumes both multiclass classification and real-
valued regression, and strictly generalizes these.

We consider the following fundamental learning problem: the instance space
${\cal X}$ is endowed with a metric $\rho$ and the label space ${\cal Y}$ with
a metric $\ell$. The learner receives a training sample $(X_{i},Y_{i})$,
$i\in[n]$, drawn iid from an unknown distribution ${\bar{\mu}}$ on ${\cal
X}\times{\cal Y}$. The learner’s goal is to (efficiently) produce a hypothesis
$f_{n}:{\cal X}\to{\cal Y}$, based on the labeled sample, so as to minimize
the risk
$R(f_{n}):=\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(f_{n}(X),Y)$. In
particular, we say that the learning procedure is strongly universally Bayes-
consistent if, for every ${\bar{\mu}}$, we have that $R(f_{n})\to R(f^{*})$
almost surely as $n\to\infty$, where $f^{*}$ is the minimizer of $R(\cdot)$
over all measurable $f:{\cal X}\to{\cal Y}$.

##### Our contribution.

We propose a novel algorithm, ${\mathsf{MedNet}}$, for learning in the metric-
valued regression setting. To our knowledge, this is the first strong Bayes-
consistency result for unbounded loss with agnostic noise. While inspired by
the OptiNet algorithm of Hanneke et al. (2021), the extension from 0-1 loss to
arbitrary metrics required non-trivial modifications to the learning procedure
and the risk analysis; a detailed account of the similarities and innovations
is provided in Section 2. We show that under quite general, natural conditions
on the metric spaces $({\cal X},\rho)$ and $({\cal Y},\ell)$, our algorithm is
strongly universally Bayes-consistent. The structural assumptions on ${\cal
X}$ and ${\cal Y}$ are truly minimalistic: we require them to be separable
metric spaces, and for ${\cal Y}$ to be bounded in expectation:
$\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty$ for some
$y_{0}\in Y$. A byproduct of our analysis is the introduction of the semi-
stable compression technique, which may be of independent interest.

##### Related work.

The regression setting with labels residing in a metric space other than
$\mathbb{R}$ is relatively uncommon; such works include Ferraty et al. (2011)
and Biess et al. (2019), who study the Banach- and Hilbert-space valued cases,
respectively, as well as the more recent results discussed below. Our work
builds on Hanneke et al. (2021), who gave a complete characterization of the
metric spaces $({\cal X},\rho)$ for which there exists a strong Universal
Bayes-Consistent (UBC) learner, where ${\cal Y}=\mathbb{N}$ is endowed with
the discrete metric. They also provided an algorithm, OptiNet, which achieves
strong UBC whenever the latter is achievable by any learner (also provided
therein is a comprehensive literature review of the strengths and limitations
of previous metric-space methods, including $k$-NN). Györfi and Weiss (2021)
followed up with a simplified algorithm, Proto-NN, which, in addition to
enjoying all of the properties of OptiNet, is also strongly UBC in $L_{1}$ for
unbounded real labels ${\cal Y}=\mathbb{R}$, as long as
$\mathop{\mathbb{E}}|Y|<\infty$; our boundedness in expectation generalizes
this condition.

Hanneke (2021b) introduced the very general paradigm of “learning whenever
learning is possible,” which extends the iid setting to essentially the
broadest possible class of random processes. That work dealt mostly with the
realizable (noiseless) case and bounded losses, though certain kinds of noise
were considered in Section 9 therein. A series of recent preprints followed:
Blanchard and Cosson (2021); Blanchard (2021); Hanneke (2021a); Blanchard et
al. (2021). These also study sampling processes far more general than iid, but
consider label-loss structures that are bounded, or noiseless, or both.
Blanchard and Cosson (2021), for example, provide a reduction from the metric-
valued regression problem to the binary classification problem for the
realizable setting with bounded loss. Another aspect in which the above works
are incomparable to ours is their use of non-algorithmic learning procedures:
more in the spirit of an existence proof, these involve non-constructive
operations such as enumerating elements of a $\sigma$-algebra.222 So as not to
get bogged down with computability issues over continuous inputs, we only
claim full algorithmic constructivity for countable ${\cal Y}$. When ${\cal
Y}$ is merely separable, we assume access to an oracle for computing
$\varepsilon$-nets over ${\cal Y}$. Such an oracle is easily constructed for,
e.g., ${\cal Y}=\mathbb{R}^{d}$.

In the special case of the singleton ${\cal X}=\left\\{x\right\\}$ and a
general metric space $({\cal Y},\ell)$, the consistency of various Fréchet
means (which are naturally related to medoids) has been recently examined by
Evans and Jaffe (2020); Schötz (2021). More tangentially related works include
Morvant et al. (2012), who, in a PAC-Bayesian setting, gave multiclass risk
bounds with a confusion matrix error structure, which is close in spirit to
assuming a metric on the label set. The assumptions there are fairly
restrictive (every label must appear at least a constant number of times in
the sample), and no learning procedure or Bayes-consistency result was
provided. On the algorithmic front, our procedure partitions the instance
space ${\cal X}$ into Voronoi cells and chooses the label $y\in{\cal Y}$ for
each cell based on a variant of the medoid principle. A number of loosely
medoid-based learning algorithms have been proposed (der Laan et al., 2003;
Gottlieb et al., 2016; Newling and Fleuret, 2017; Baharav and Tse, 2019), but
our approach is distinct from all of these, in that we compute medoids in the
label (rather than instance) space.

Finally, stable compression was a technique introduced by Bousquet et al.
(2020) for the realizable case and extended to the agnostic case by Hanneke
and Kontorovich (2021). We introduce a semi-stable variant for both cases by
allowing additional side information; only the compression set (and not the
side information) is required to satisfy the stability condition of Bousquet
et al.

##  2 Main results and overview of techniques

Our main result is the existence of a strong Universal Bayes-Consistent (UBC)
learner for metric-valued regression.

######  Theorem 1.

There exists a learning algorithm, ${\mathsf{MedNet}}$, with the following
property. Let $({\cal X},\rho)$ and $({\cal Y},\ell)$ be separable metric
spaces endowed with a distribution ${\bar{\mu}}$ supported on the product
Borel $\sigma$-algebra of ${\cal X}\times{\cal Y}$, such that ${\cal Y}$ is
bounded in expectation:
$\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty$ for some
$y_{0}\in{\cal Y}$. Given a training sample
$(X_{i},Y_{i})_{i\in[n]}\sim{\bar{\mu}}^{n}$ as input, ${\mathsf{MedNet}}$
outputs a predictor $f_{n}:{\cal X}\to{\cal Y}$ that is strongly universally
Bayes-consistent: $R(f_{n})\to R^{*}$ almost surely (under ${\bar{\mu}}$) as
$n\to\infty$, where
$R(f)=\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(f(X),Y)$ is the risk and
$R^{*}$ the Bayes-optimal risk (minimum risk achieved by any measurable $f$).

The proof proceeds via a sequence of incremental results, culminating in
Theorem 12, which is a restatement of Theorem 1. A few remarks regarding our
assumptions on $({\cal X},\rho)$ and $({\cal Y},\ell)$ are in order. As per
Hanneke et al. (2021), the assumption of separability may be weakened to
essential separability (ES): this is the condition that the support of
${\bar{\mu}}$ is contained in a separable subspace. It was shown therein that
the ES condition (on ${\cal X}$) is also necessary for any learner to succeed,
and observed that any actual metric space encountered in practice will be ES;
in fact, the existence of non-ES metric spaces is widely believed to be
independent of ZFC. For countable ${\cal Y}$, a variant of Theorem 1 — namely,
Theorem 10 — holds for any bounded loss function $\ell:{\cal Y}\times{\cal
Y}\to[0,L]$; no metric structure is necessary. Finally, a word about the
computational efficiency of ${\mathsf{MedNet}}$. The latter, conceptually,
consists of two stages: (I) computing a $\gamma$-net on the finite training
sample (residing in ${\cal X}$) and (II) for each Voronoi cell $C$ induced on
the sample by the $\gamma$-net, finding a medoid $y\in{\cal Y}$ that minimizes
$\sum_{c\in C}\ell(c,y)$. The $\gamma$-net in stage (I) can indeed be
efficiently constructed (Gottlieb et al., 2014; Kpotufe and Verma, 2017). At
stage (II), ${\mathsf{MedNet}}$ truncates ${\cal Y}$ adaptively to some finite
${\cal Y}^{\prime}$ over which the medoid can always be computed in a runtime
linear in $|{\cal Y}^{\prime}|$. When additional structural information
regarding ${\cal Y}$ is available, it may be leveraged to obtain more
efficient medoid oracles.

To illustrate our significant departure from previous techniques, let us
provide some simple examples where those fail to be Bayes-consistent for
various simple label metrics. Let ${\cal X}=\left\\{0\right\\}$ be the trivial
singleton metric space and ${\cal Y}=\left\\{a,b,c,o\right\\}$ be the label
space endowed with the metric $\ell(a,b)=\ell(b,c)=\ell(c,a)=1$;
$\ell(o,a)=\ell(o,b)=\ell(o,c)=1/2$, and let the distribution ${\bar{\mu}}$ be
such that
$\operatorname{\mathbb{P}}_{(X,Y)\sim{\bar{\mu}}}(Y=a)=\operatorname{\mathbb{P}}_{(X,Y)\sim{\bar{\mu}}}(Y=b)=\operatorname{\mathbb{P}}_{(X,Y)\sim{\bar{\mu}}}(Y=c)=1/3$.
We observe that any majority-vote based method, such as $k$-NN, which takes a
vote among the $k$ nearest neighbors (Györfi et al., 2002), or OptiNet, which
takes a vote within each Voronoi cell (Hanneke et al., 2021), or the memory-
based techniques of Blanchard and Cosson (2021); Blanchard (2021); Blanchard
et al. (2021), or the hybrid approach of Györfi and Weiss (2021) cannot
achieve Bayes-consistency in this case — for the simple reason that they can
only output the observed labels $a,b,c$ (and hence, at best, achieve an
asymptotic risk of $2/3$), while the Bayes-optimal predictor $f^{*}\equiv o$
achieves $R(f^{*})=1/2$.

The necessity of predicting labels that never occurred in the sample required
overcoming a subtle challenge not present in Hanneke et al. (2021). As in that
work, we obtain finite-sample generalization bounds via a sample compression
scheme. The latter selects a sub-sample $S_{I}=(X_{i},Y_{i})_{i\in
I\subset[n]}$, based on which the predictor will be constructed. To mitigate
the noise, we occasionally wish to relabel a point $X_{i}\in S_{I}$ with a
label other than $Y_{i}$. One could do this using $b$ bits of side
information, but Hanneke et al. sidestepped this issue by doubling the
compression set size: the first $k$ pairs $(X_{i},Y_{i})$ indicate which $X$’s
to use (their $Y$’s are discarded) and the second $k$ pairs indicate how to
label those first $k$ points $X_{i}$. This stratagem is not applicable when we
wish to relabel an $X$ with a $Y\in{\cal Y}$ not occurring in the sample.
Instead, ${\mathsf{MedNet}}$ adaptively truncates ${\cal Y}$ to a finite
${\cal Y}_{n}$, whose elements can be described in $b(n)=\log_{2}|{\cal
Y}_{n}|$ bits of side information. This solves two problems simultaneously:
the concentration inequalities we invoke require a bounded range, and our
compression schemes require bounded side information. We introduce a semi-
stable variant of the stable compression scheme (Bousquet et al., 2020;
Hanneke and Kontorovich, 2021) to analyze the behavior of our truncated
medoid.

Finally, we recall the family of regression techniques based on Lipchitz-
extension and observe that it is not suitable for learning general metric-to-
metric mappings. A binary classifier based on the McShane-Whitney extension
theorem was shown to be Bayes-consistent (Kontorovich and Weiss, 2014); this
technique was also applied by Gottlieb et al. (2017); Ashlagi et al. (2021) to
real-valued regression. When ${\cal X}$ and ${\cal Y}$ are both Hilbert
spaces, the Kirszbraun extension theorem likewise provides a basis for a
regression algorithm (Biess et al., 2019). (While the latter three works do
not prove Bayes-consistency, the finite-sample generalization bounds provided
therein are likely straightforwardly adaptable to such a result via an
appropriate regularization schedule.) Unfortunately, Lipschitz extension is
limited to a small number of metric spaces with a special structure; besides
the aforementioned cases, Naor and Sheffield (2012) established one for ${\cal
X}$ a locally compact length space and ${\cal Y}$ a metric tree, remarking
that “It is rare for a pair of metric spaces […] to have the isometric
extension property.” As a concrete example, the spaces $({\cal
X},\rho)=(\mathbb{R}^{3},\left\|\cdot\right\|_{1})$ and $({\cal
Y},\ell)=(\mathbb{R}^{2},\left\|\cdot\right\|_{2})$ fail to have this property
(Naor, 2015, Counterexample 2.4).

##### Open problem.

The bounded in expectation (BIE) condition on ${\cal Y}$ is a natural
generalization of the real-valued variant that $\mathop{\mathbb{E}}|Y|<\infty$
(or, more generally, $\mathop{\mathbb{E}}|Y|^{p}<\infty$ if $L_{p}$ risk is
being considered). These conditions, while sufficient for Bayes consistency,
are clearly not always necessary. Consider, for example, ${\cal X}={\cal
Y}=\mathbb{R}$, endowed with the standard metric, where the distribution
${\bar{\mu}}$ is such that the ${\cal X}$-marginal is Cauchy (i.e., has
density $f(x)=[\pi(1+x^{2})]^{-1}$) and $X=Y$ almost surely. In this case,
$\mathop{\mathbb{E}}|Y|=\infty$ and the more general BIE condition also fails.
Yet the identity predictor $h(x)=x$ achieves the Bayes-optimal risk of $0$,
and various simple learning algorithms, including linear regression, achieve
Bayes consistency (we conjecture that ${\mathsf{MedNet}}$ does as well).
Problem: formulate a necessary and sufficient condition on the metric spaces
$({\cal X},\rho)$ and $({\cal Y},\ell)$, and the joint distribution
${\bar{\mu}}$ such that ${\mathsf{MedNet}}$ (or some other learning algorithm)
is strongly Bayes-consistent. A natural and optimistic candidate is the
condition $R^{*}<\infty$.

##  3 Definitions and notation

For $n\in\mathbb{N}:=\left\\{1,2,\ldots\right\\}$, define
$[n]:=\\{1,\ldots,n\\}$; for any set $\mathcal{Z}$, we write
$\mathcal{Z}^{+}:=\bigcup_{n=1}^{\infty}\mathcal{Z}^{n}$ and
$\mathcal{Z}^{\leq k}:=\bigcup_{n=1}^{k}\mathcal{Z}^{n}$, where $|z|$ denotes
the sequence length. For $A\in\mathcal{Z}^{+}$, we write $B\subset A$ to
denote the subsequence relation. Our instance and label spaces are the metric
spaces $({\cal X},\rho)$ and $({\cal Y},\ell)$, respectively, whose product
Borel $\sigma$-algebra is equipped with the probability measure ${\bar{\mu}}$,
whose ${\cal X}$-marginal will be denoted by $\mu$ and ${\cal Y}$-marginal by
$\mu_{\cal Y}$. We say that ${\cal Y}$ is bounded in expectation (BIE) if
$\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty$ for some
$y_{0}\in Y$. Some of our results will also hold for countable ${\cal Y}$
equipped with an arbitrary (possibly non-metric) loss function $\ell:{\cal
Y}\times{\cal Y}\to[0,\infty)$. We denote set cardinalities by $|{\cal Y}|$
and the diameter by

$\displaystyle\left\|{\cal Y}\right\|\equiv\operatorname{diam}({\cal
Y}):=\sup_{y,y^{\prime}\in{\cal Y}}\ell(y,y^{\prime});$ (3.1)

the latter is also meaningful when $\ell$ is not a metric. For $x\in{\cal X}$
and $r>0$, $B_{r}(x)$ denotes the open ball of radius $r$ about $x$; an
analogous definition holds when $({\cal Y},\ell)$ is a metric. Unless
specified otherwise, $S_{n}=(X_{i},Y_{i})_{i\in[n]}$ is always sampled iid
from ${\bar{\mu}}$. To any measurable mapping $f:{\cal X}\to{\cal Y}$ we
associate the (true) risk
$R(f):=\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(f(X),Y)$ and the
empirical risk $\widehat{R}:{\cal Y}^{\cal X}\times({\cal X}\times{\cal
Y})^{+}\to\mathbb{R}$ by

$\displaystyle\widehat{R}(f;S):=|S|^{-1}\sum_{(x,y)\in S}\ell(f(x),y).$ (3.2)

The Bayes-optimal risk is $R^{*}:=\inf_{f}R(f)$, where the infimum is over all
measurable $f:{\cal X}\to{\cal Y}$.

We implicitly assume the existence of fixed measurable total orders on ${\cal
X}$ and on ${\cal Y}$, whose existence is guaranteed by Hanneke et al. (2021,
Proposition D.1), and refer to these orderings as lexicographic. For
$A\subseteq{\cal X}$, denote its $\gamma$-envelope by
$\textrm{UB}_{\gamma}(A)$ $:=\cup_{x\in A}B_{\gamma}(x)$ and consider the
$\gamma$-missing mass of $S_{n}$, defined as the following random variable:

$\displaystyle\mathsf{mm}_{\gamma}(S_{n}):=\mu({\cal
X}\setminus\textup{{UB}}_{\gamma}(S_{n})).$ (3.3)

As in Hanneke et al. (2021), we denote, for any labeled sequence
$S=(x_{i},y_{i})_{i=1}^{n}\in({\cal X}\times{\cal Y})^{n}$, and any $x\in{\cal
X}$, the nearest neighbor of $x$ with respect to $S$ and its label by
$X_{\mathsf{nn}}(x,S)$ and $Y_{\mathsf{nn}}(x,S)$, respectively:

$\displaystyle(X_{\mathsf{nn}}(x,S),Y_{\mathsf{nn}}(x,S)):=\mathop{\mathrm{argmin}}_{(x_{i},y_{i})\in
S}\rho(x,x_{i}),$

where ties are broken lexicographically. The $1$-NN predictor induced by $S$
is defined as $h_{S}(x):=Y_{\mathsf{nn}}(x,S)$. For any $m\in\mathbb{N}$, any
sequence $\bm{X}=\\{x_{1},\ldots,x_{m}\\}\in{\cal X}^{m}$ induces a Voronoi
partition of ${\cal X}$,
$\mathcal{V}(\bm{X}):=\\{V_{1}(\bm{X}),\dots,V_{m}(\bm{X})\\}$, where each
Voronoi cell is

$\displaystyle V_{i}(\bm{X}):=\left\\{x\in{\cal
X}:i=\mathop{\mathrm{argmin}}_{1\leq j\leq m}\rho(x,x_{j})\right\\},$

again breaking ties lexicographically. In particular, for
$\bm{X}=\\{X_{i}:(X_{i},Y_{i})\in S\\}$, we have $h_{S}(x)=Y_{i}$ for all
$x\in V_{i}(\bm{X})$. A $1$-NN algorithm is a mapping from an i.i.d. labeled
sample $S_{n}\sim{\bar{\mu}}^{n}$ to a labeled set
$S^{\prime}_{n}\subseteq{\cal X}\times{\cal Y}$, yielding the $1$-NN predictor
$h_{S^{\prime}_{n}}$. For $A\subseteq{\cal X}$ and $\gamma>0$, a $\gamma$-net
of $A$ is any maximal set $B\subseteq A$ in which all interpoint distances are
at least $\gamma$. For a partition $\cal{A}$ of $B\subseteq{\cal X}$, we write
$\left\|\cal{A}\right\|:=\sup_{A\in\cal{A}}\left\|A\right\|$ (again, as in
(3.1), $\left\|A\right\|:=\operatorname{diam}A$). Given a labeled set
$S_{n}=(x_{i},y_{i})_{i\in[n]}$, $d\in[n]$, and any
$\bm{i}=\\{i_{1},\ldots,i_{d}\\}\in[n]^{d}$, denote the sub-sample of $S_{n}$
indexed by $\bm{i}$ by
$S_{n}(\bm{i}):=\\{(x_{i_{1}},y_{i_{1}}),\dots,(x_{i_{d}},y_{i_{d}})\\}$.
Similarly, for a vector
${\bm{y}}^{\prime}=\\{y^{\prime}_{1},\ldots,y^{\prime}_{d}\\}\in{\cal Y}^{d}$,
define
$S_{n}{(\bm{i},{\bm{y}}^{\prime})}:=\\{(x_{i_{1}},y^{\prime}_{1}),\dots,(x_{i_{d}},y^{\prime}_{d})\\}$,
namely the sub-sample of $S_{n}$ as determined by $\bm{i}$ where the labels
are replaced with ${\bm{y}}^{\prime}$. Lastly, for $\bm{i},\bm{j}\in[n]^{d}$,
we denote
$S_{n}(\bm{i};\bm{j}):=\\{(x_{i_{1}},y_{j_{1}}),\dots,(x_{i_{d}},y_{j_{d}})\\}.$

We use standard order-of-magnitude notation throughout the paper; thus, for
$f,g:\mathbb{N}\to[0,\infty)$ we write $f(n)\in O(g(n))$ to mean
$\limsup_{n\to\infty}f(n)/g(n)$ $<\infty$ and $f(n)\in o(g(n))$ to mean
$\limsup_{n\to\infty}f(n)/g(n)=0$. Likewise, $f(n)\in\Omega(g(n))$ means that
$g(n)\in O(f(n))$. In accordance with common convention, we often use the less
precise notation $f(n)=O(g(n))$, etc.

We say that a metric space $({\cal X},\rho)$ is separable if it contains a
dense countable set. A metric probability space $({\cal X},\rho,\mu)$ is
separable if there is a measurable ${\cal X}^{\prime}\subseteq{\cal X}$ with
$\mu({\cal X}^{\prime})=1$ such that $({\cal X}^{\prime},\rho)$ is separable.

A sample compression scheme $(\kappa,\psi)$ of size at most $k$ using $b$ bits
of side-information consists of a _compression function_ and a _reconstruction
function_. The _compression function_ $\kappa$ maps every finite sample set to
$b$ bits plus a _compression set_ , which is a subset of at most $k$ labeled
examples.

$\displaystyle\kappa:\left({\cal X}\times{\cal Y}\right)^{+}\to\left({\cal
X}\times{\cal Y}\right)^{\leq k}\times\left\\{0,1\right\\}^{b}.$

The _reconstruction function_ $\psi$ maps every possible compression set and
$b$ bits to a hypothesis:

$\displaystyle\psi:\left({\cal X}\times{\cal Y}\right)^{\leq
k}\times\left\\{0,1\right\\}^{b}\to{\cal Y}^{\cal X}.$

##  4 Semi-stable compression

In this section, we expand the definition of stable compression and present
our results for this notion. First, we split the compression function $\kappa$
into its two components. For $S\in({\cal X}\times{\cal Y})^{+}$, we write
$\kappa(S)=(\kappa_{\mathsf{cs}}(S),\kappa_{\mathsf{si}}(S))\in({\cal
X}\times{\cal Y})^{\leq k}\times\left\\{0,1\right\\}^{b}$; these are the
compression set and the side information. We say that $(\kappa,\psi)$ is semi-
stable if the $\kappa_{\mathsf{cs}}$ component is stable in the sense of
Bousquet et al. (2020): whenever $\kappa_{\mathsf{cs}}(S)\subseteq
S^{\prime}\subseteq S$, we have that

$\displaystyle\psi(\kappa_{\mathsf{cs}}(S^{\prime}),\kappa_{\mathsf{si}}(S))=\psi(\kappa_{\mathsf{cs}}(S),\kappa_{\mathsf{si}}(S))=\psi(\kappa(S)).$

We denote by $|\kappa_{\mathsf{cs}}(\cdot)|$ and
$|\kappa_{\mathsf{si}}(\cdot)|$ the sizes of the compression set and side
information (in bits), respectively.

######  Theorem 2 (proof deferred to Section C.3.4).

Suppose that ${\cal X}$ is an instance space and ${\cal Y}$ a label space with
a loss function $\ell:{\cal Y}\times{\cal Y}\to[0,L]$, and $(\kappa,\psi)$ is
semi-stable compression scheme. For any distribution ${\bar{\mu}}$ over ${\cal
X}\times{\cal Y}$, any $n\in\mathbb{N}$, and any $\delta\in(0,1)$, for
$S_{n}\sim{\bar{\mu}}^{n}$ we have that

$\displaystyle R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle\leq\left(20\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+20\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+15\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}\right)\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle+(6L+18)\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+8L\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+(2L+12)\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}$
$\displaystyle+7L\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+(3L+10)\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6L\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}$

holds with probability at least $1-\delta$.

###  $(\alpha,k,b)$-semi-stable-compression

Let ${\cal X}$, ${\cal Y}$, $\ell$, and $S_{n}$ be as in the statement of
Theorem 2. For $k\leq n$, $b\in\mathbb{N}$, and $\alpha\geq 0$, we say that
$(S^{\prime}_{n},h_{S^{\prime}_{n}})$ is an _$(\alpha,k,b)$ -semi-stable-
compression_ of $S_{n}$ if there exist $\bm{i}\in[n]^{k}$ and ${\bf Y}\in{\cal
Y}^{k}$ such that:

  1. 1.

$h_{S^{\prime}_{n}}$ and $S^{\prime}_{n}=S_{n}(\bm{i},{\bf Y})$ are a result
of a semi-stable compression scheme of size $k$ with at most $b$ bits of side
information. Thus, $S^{\prime}_{n}=\kappa_{\mathsf{si}}(S_{n})$ and
$h_{S^{\prime}_{n}}=\psi(\kappa_{\mathsf{cs}}(S),\kappa_{\mathsf{si}}(S))$.

  2. 2.

$\widehat{R}(h_{S^{\prime}_{n}};S_{n})\leq\alpha$.

######  Lemma 3 (proof in Section B.2).

Let ${\cal X}$, ${\cal Y}$, $\ell$, $L$, and $S_{n}$ be as in Theorem 2. For
$k\leq n$, define

$\displaystyle{}Q(n,\alpha,k,b,\delta,L):=Q_{n}(\alpha,k,b,\delta,L)$
$\displaystyle:=\left(20\sqrt{\frac{k}{n}}+20\sqrt{\frac{b}{n}}+15\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}+1\right)\alpha$
(4.1)
$\displaystyle\quad+(6L+18)\frac{k}{n}+8L\sqrt{\frac{k}{n}}+(2L+12)\frac{b}{n}+7L\sqrt{\frac{b}{n}}$
$\displaystyle\quad+(3L+10)\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6L\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}.$

Then the function $Q$ satisfies the following properties:

  1. Q1.

For any $n\in\mathbb{N}$ and $\delta\in(0,1)$, with probability at least
$1-\delta$ over $S_{n}\sim{\bar{\mu}}^{n}$, for all $\alpha\in[0,L]$,
$k\in[n]$, $b\in\mathbb{N}$: If $(S^{\prime}_{n},h_{S^{\prime}_{n}})$ is an
$(\alpha,k,b)$-semi-stable-compression of $S_{n}$, then

$R(h_{S^{\prime}_{n}})\leq Q_{n}(\alpha,k,b,\delta,L).$

  2. Q2.

For any fixed $n\in\mathbb{N}$ and $\delta\in(0,1)$, $Q$ is monotonically
increasing in $\alpha$ and in $k$.

  3. Q3′′.

There is a sequence $\\{\delta_{n}\\}_{n=1}^{\infty}$, $\delta_{n}\in(0,1)$
such that $\sum_{n=1}^{\infty}\delta_{n}<\infty$, and for any $k_{n}\in o(n)$
we have that

$\displaystyle\lim_{n\rightarrow\infty}\sup_{\alpha\in[0,L]}(Q_{n}(\alpha,k_{n},b,\delta_{n},L)-\alpha)=0.$

##  5 Metric approximations

Our proof technique involves performing several distinct truncations,
approximating a potentially unbounded quantity by a finite one. In this
section, we adapt a variant of this method from Hanneke et al. (2021) for the
0-1 loss to arbitrary bounded losses. Here, $({\cal X},\rho)$ is assumed to be
a separable metric space, and ${\cal Y}$ a _countable_ label space with a loss
function $\ell:{\cal Y}^{2}\to[0,L]$. Let ${\cal V}=\\{V_{1},\dots\\}$ be a
countable partition of ${\cal X}$, and define the function $I_{\cal V}:{\cal
X}\to{\cal V}$ such that $I_{\cal V}(x)$ is the unique $V\in{\cal V}$ for
which $x\in V$. For any measurable set $\emptyset\neq E\subseteq{\cal X}$
define the true medoid label $y^{*}(E)$ by

$\displaystyle y^{*}(E)=\mathop{\mathrm{argmin}}_{y\in{\cal Y}}\int_{X\in
E}\ell(y,Y)\mathrm{d}{\bar{\mu}},$ (5.1)

where ties are broken lexicographically according to fixed total order on
${\cal Y}$. Given ${\cal V}$ and a measurable set $W\subseteq{\cal X}$, define
the true medoid predictor $h_{{\cal V},W}^{*}:{\cal X}\to{\cal Y}$ given by

$\displaystyle h_{{\cal V},W}^{*}(x)=y^{*}(I_{\cal V}(x)\cap W).$ (5.2)

######  Lemma 4 (proof in Section B.3).

Let ${\bar{\mu}}$ be a probability measure on ${\cal X}\times{\cal Y}$ with
${\cal X}$-marginal $\mu$, where ${\cal X}$ is a metric probability space, and
${\cal Y}$ a _countable_ label space with a loss function $\ell$ such that
$L:=\left\|{\cal Y}\right\|<\infty$. For any $\nu>0$, there exists a diameter
$\beta=\beta(\nu)>0$ such that for any countable measurable partition ${\cal
V}=\\{V_{1},\dots\\}$ of ${\cal X}$ and any measurable set $W\subseteq{\cal
X}$ satisfying

  * $\mathrm{(}\textup{i})$

$\mu({\cal X}\setminus W)\leq\nu$

  * $\mathrm{(}\textup{ii})$

$\sup_{V\in{\cal V}}\left\|V\cap W\right\|\leq\beta$,

the true medoid predictor $h_{{\cal V},W}^{*}$ defined in (5.2) satisfies

$\displaystyle R(h_{{\cal V},W}^{*})\leq R^{*}+9L\nu.$

The proof of Lemma 4 is similar to that of Hanneke et al. (2021, Lemma 3.6),
with novel arguments to handle the general loss function setting. Next, we
state two results from Hanneke et al. (2021):

######  Lemma 5 (variant of Lemma 3.7, Hanneke et al. (2021)).

Let $({\cal X},\rho,\mu)$ be a separable metric probability space. For
$S_{n}\sim\mu^{n}$, let ${\bm{X}}(\gamma)$ be any $\gamma$-net of $S_{n}$.
Then, for any $\gamma>0$, there exists a function
$t_{\gamma}:\mathbb{N}\to\mathbb{R}_{+}$ in $o(n)$ such that
$\displaystyle\operatorname{\mathbb{P}}\left[\sup_{\gamma\text{-}\mathrm{nets}\,\,{\bm{X}}(\gamma)}|{\bm{X}}(\gamma)|\geq
t_{\gamma}(n)\right]\leq 1/n^{2}.$

######  Lemma 6 (Lemma 3.8, Hanneke et al. (2021)).

Let $({\cal X},\rho,\mu)$ be a separable metric probability space, $\gamma>0$
be fixed, and the $\gamma$-missing mass $\mathsf{mm}_{\gamma}$ defined as in
(3.3). Then there exists a function $u_{\gamma}:\mathbb{N}\to\mathbb{R}_{+}$
in $o(1)$, such that
$\operatorname{\mathbb{P}}\left[\mathsf{mm}_{\gamma}(S_{n})\geq
u_{\gamma}(n)+t\right]\leq\exp\left(-nt^{2}\right)$ for $S_{n}\sim\mu^{n}$ and
$t>0$.

##  6  Algorithms and analysis: finite ${\cal Y}$

In this section, we give the most basic version of our algorithm, denoted
${\mathsf{MedNet}}_{|{\cal Y}|<\infty}$, for the case where $({\cal X},\rho)$
is a separable metric and ${\cal Y}$ is a finite set equipped with an
arbitrary (not necessarily metric) loss function $\ell:{\cal Y}\times{\cal
Y}\to\mathbb{R}_{+}$. This rudimentary setting provides the basis for
extension to more general settings, in the sequel.

The input is the sample $S_{n}$; the set of instances in the sample is denoted
by $\bm{X}_{n}=\\{X_{1},\ldots,X_{n}\\}$. The algorithm defines a set $\Gamma$
of all $n\choose 2$ scales $\gamma>0$ which are interpoint distances in
$\bm{X}_{n}$, and the additional scale $\gamma=\infty$. For each scale in
$\Gamma$, the algorithm constructs a $\gamma$-net of $\bm{X}_{n}$. Denote the
constructed $\gamma$-net by

$\displaystyle\bm{X}(\gamma):=\\{X_{i_{1}},\ldots,X_{i_{M}}\\},$ (6.1)

where

$\displaystyle M\equiv M_{n}(\gamma):=|{\bm{X}}(\gamma)|$ (6.2)

denotes its size and
$\bm{i}\equiv\bm{i}(\gamma):=\\{i_{1},\ldots,i_{M}\\}\in[n]^{M}$ denotes the
indices selected from $S_{n}$ for this $\gamma$-net.

For each $\gamma$-net, Algorithm 1 finds the _empirical medoid labels_ in the
Voronoi cells defined by the partition
$\mathcal{V}(\bm{X}(\gamma))=\\{V_{1}(\bm{X}(\gamma)),\ldots,V_{M}(\bm{X}(\gamma))\\}$.
These labels are denoted by ${\bm{Y}}^{\prime}(\gamma)\in{\cal Y}^{M}$.
Formally, for $i\in[M]$,

$\displaystyle Y^{\prime}_{i}(\gamma):=\mathop{\mathrm{argmin}}_{y\in{\cal
Y}}{\sum_{j\in[n]:X_{j}\in V_{i}}\ell(y,Y_{j})}.$ (6.3)

As always, ties are broken lexicographically. The output of
${\mathsf{MedNet}}_{|{\cal Y}|<\infty}$ is a labeled set
$S^{\prime}_{n}(\gamma):=S_{n}(\bm{i}(\gamma),{\bm{Y}}^{\prime}(\gamma))$ for
every candidate scale $\gamma\in\Gamma$. The algorithm then selects a single
scale $\gamma^{*}\equiv\gamma_{n}^{*}$ from $\Gamma$, and outputs the
hypothesis that it induces, $h_{S^{\prime}_{n}(\gamma^{*})}$. The choice of
$\gamma^{*}$ is executed by minimizing a generalization error bound, denoted
$Q$, which upper-bounds $R(h_{S^{\prime}_{n}(\gamma)})$ with high probability.

Assumptions : $({\cal X},\rho)$ is a separable metric space, ${\cal Y}$ a
_finite_ label space with a loss function $\ell$. Define $L:=\left\|{\cal
Y}\right\|=\max_{y,y^{\prime}\in{\cal Y}}\ell(y,y^{\prime})$ and
$b:=\log_{2}|{\cal Y}|$.

Input : Sample $S_{n}=(X_{i},Y_{i})_{i\in[n]}$, confidence
$\delta_{n}\in(0,1)$

Output : predictor $h:{\cal X}\to{\cal Y}$

Let
$\Gamma:=(\left\\{\rho(X_{i},X_{j}):i,j\in[n]\right\\}\cup\\{\infty\\})\setminus\\{0\\}$;

for  _$\gamma\in\Gamma$_ do

Let $\bm{X}(\gamma)$ be a $\gamma$-net of $\\{X_{1},\ldots,X_{n}\\}$;

Let $M_{n}(\gamma):=|\bm{X}(\gamma)|$;

For each $i\in[M_{n}(\gamma)]$, let $Y^{\prime}_{i}(\gamma)$ be the _empirical
medoid label_ of $V_{i}(\bm{X}(\gamma))$ as in (6.3);

Set $S^{\prime}_{n}(\gamma):=(\bm{X}(\gamma),{\bm{Y}}^{\prime}(\gamma))$;

Set $h_{S^{\prime}_{n}(\gamma)}:=x\mapsto
Y_{\mathsf{nn}}(x,S^{\prime}_{n}(\gamma))$.

Set $\alpha_{n}(\gamma):=\widehat{R}(h_{S^{\prime}_{n}(\gamma)};S_{n})$;

end for

Find
$\gamma^{*}_{n}\in\mathop{\mathrm{argmin}}_{\gamma\in\Gamma}Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma),b,\delta,L)$,
where $Q_{n}$ is defined in (4.1);

Set $S^{\prime}_{n}:=S^{\prime}_{n}({\gamma^{*}_{n}})$;

return $h=h_{S^{\prime}_{n}}$;

Algorithm 1 ${\mathsf{MedNet}}_{|{\cal Y}|<\infty}$

### Bayes Consistency of ${\mathsf{MedNet}}_{|{\cal Y}|<\infty}$

The Bayes consistency result of Hanneke et al. (2021) was for the $0$-$1$
loss. Their approach was also compression-based, but did not leverage the
stability property, had no need for side information, and did not have to
truncate potentially unbounded losses. Our main technical innovation was
constructing ${\mathsf{MedNet}}$ (formally defined in Section A.1) as a semi-
stable compression scheme with side-information, and then invoking it with an
appropriate truncation schedule for infinite and unbounded ${\cal Y}$.

The first order of business is to verify that ${\mathsf{MedNet}}_{|{\cal
Y}|<\infty}$ indeed furnishes a semi-stable compression scheme for any fixed
$\gamma$:

######  Lemma 7 (proof in Section B.1).

Let $({\cal X},\rho)$ be a separable metric space, and ${\cal Y}$ a _finite_
label space with a loss function $\ell$. For any fixed scale
$\gamma\in\Gamma$, the procedure in Algorithm 1 generating
$h_{S^{\prime}_{n}(\gamma)}$ is a semi-stable compression scheme.

The following key technical lemma is a generalization of Hanneke et al. (2021,
Lemma 3.5) from 0-1 loss to the general loss setting.

######  Lemma 8 (proof in Section B.4).

Let ${\bar{\mu}}$ be a probability measure on ${\cal X}\times{\cal Y}$, where
${\cal X}$ is a metric probability space, and ${\cal Y}$ a _countable_ label
space endowed with a loss function $\ell\leq L<\infty$. Let $t_{\gamma}$ as in
Lemma 5. Then there exist functions $\varepsilon\mapsto\gamma(\varepsilon)$
and
$\varepsilon\mapsto\gamma:=\nu(\varepsilon)\in(0,\frac{\varepsilon}{176L})$
such that for each $\varepsilon,b>0$ there is an
$N_{0}(\nu(\varepsilon),b,\delta_{n},t_{\gamma})$ such that for all $n\geq
N_{0}$, and all $d\in[t_{\gamma}(n)]$,

$\displaystyle p_{d}$
$\displaystyle:=\operatorname{\mathbb{P}}\Big{[}Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma),b,\delta_{n},L)>R^{*}\\!+\varepsilon\;\wedge\;\mathsf{mm}_{\gamma}(S_{n})\\!\leq\\!\frac{\varepsilon}{18L}\;\wedge\;M_{n}(\gamma)\\!=\\!d\Big{]}\leq
e^{-\frac{n\varepsilon^{2}}{32}}+e^{-\frac{1}{2}n\nu^{2}}\\!,$

where $M_{n}(\gamma)$ is defined in (6.2).

The main result of this section is

######  Theorem 9.

Let $({\cal X},\rho)$ be a separable metric space, and ${\cal Y}$ a _finite_
label space with a loss function $\ell$. Then there exists a choice of
$\delta_{n\in\mathbb{N}}$ such that the sequence of hypotheses $h_{n}$
computed by ${\mathsf{MedNet}}_{|{\cal Y}|<\infty}(S_{n},\delta_{n})$ is
strongly Bayes consistent:
$\operatorname{\mathbb{P}}[\lim_{n\rightarrow\infty}R(h_{n})=R^{*}]=1.$

###### Proof.

Recall that $L:=\left\|{\cal Y}\right\|=\max_{y,y^{\prime}\in{\cal
Y}}\ell(y,y^{\prime})$ and let $b:=\log_{2}|{\cal Y}|$. Let $Q$ be the
generalization bound in (4.1) and set the input confidence $\delta$ for input
size $n$ to $\delta_{n}$ as stipulated by Q3′′.

Given a sample $S_{n}\sim{\bar{\mu}}^{n}$, we abbreviate the optimal empirical
error $\alpha_{n}^{*}=\alpha(\gamma^{*}_{n})$ and the optimal compression size
$M_{n}^{*}=M(\gamma^{*}_{n})$ as computed by Algorithm 1. By Lemma 7, the
labeled set $S^{\prime}_{n}(\gamma_{n}^{*})$ computed by Algorithm 1 is an
$(\alpha_{n}^{*},M_{n}^{*},b)$-semi-stable compression of the sample $S_{n}$.
For brevity we denote $Q_{n}(\alpha,k):=Q_{n}(\alpha,k,b,\delta_{n},L).$ To
prove the Theorem, we first follow the standard technique, used also in
Hanneke et al. (2021), of decomposing the excess risk into two terms:

$\displaystyle R(h_{S^{\prime}_{n}(\gamma^{*}_{n})})-R^{*}$ $\displaystyle=$
$\displaystyle\big{(}R(h_{S^{\prime}_{n}(\gamma^{*}_{n})})-Q_{n}(\alpha_{n}^{*},M_{n}^{*})\big{)}+\big{(}Q_{n}(\alpha_{n}^{*},M_{n}^{*})-R^{*}\big{)}=:T_{\mathrm{I}}(n)+T_{\mathrm{II}}(n)$

and arguing that each term decays to zero almost surely. For
$T_{\mathrm{I}}(n)$ we have, similarly to Hanneke et al., that Property Q1
from Lemma 3 implies that for any $n>0$,

$\displaystyle\operatorname{\mathbb{P}}\\!\left[R(h_{S^{\prime}_{n}(\gamma^{*}_{n})})-Q_{n}(\alpha_{n}^{*},M_{n}^{*})>0\right]\leq\delta_{n}.$
(6.4)

Applying Borel-Cantelli to the fact that $\sum\delta_{n}<\infty$ yields
$\limsup_{n\to\infty}T_{\mathrm{I}}(n)\leq 0$ almost surely. The main
departure from the proof in Hanneke et al. is in establishing
$\limsup_{n\to\infty}T_{\mathrm{II}}(n)\leq 0$ almost surely. We will argue
that there exist $N=N(\varepsilon)>0$, $\gamma=\gamma(\varepsilon)>0$,
$\nu=\nu(\varepsilon)>0$, and universal constants $c,C>0$ such that $\forall
n\geq N$,

$\displaystyle\operatorname{\mathbb{P}}[Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))>R^{*}+\varepsilon]\leq
Cne^{-cn\varepsilon^{2}}+ne^{-\nu^{2}n/2}+1/n^{2}.$ (6.5)

For any $\gamma>0$ (even if $\gamma\notin\Gamma$), Algorithm 1 finds a
$\gamma_{n}^{*}$ such that

$\displaystyle Q_{n}(\alpha_{n}^{*},M_{n}^{*})$ $\displaystyle=$
$\displaystyle\min_{\gamma^{\prime}\in\Gamma}Q_{n}(\alpha_{n}(\gamma^{\prime}),M_{n}(\gamma^{\prime}))\,\leq\,Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma)).$

The bound in (6.5) thus implies that $\forall n\geq N$,

$\displaystyle\operatorname{\mathbb{P}}[Q_{n}(\alpha_{n}^{*},M_{n}^{*})>R^{*}+\varepsilon]\leq
Cne^{-cn\varepsilon^{2}}+ne^{-\nu^{2}n/2}+1/n^{2}.$ (6.6)

By the Borel-Cantelli lemma, this implies that almost surely,
$\limsup_{n\rightarrow\infty}T_{\mathrm{II}}(n)=\limsup_{n\rightarrow\infty}(Q_{n}(\alpha_{n}^{*},M_{n}^{*})-R^{*})\leq
0.$ Since $\forall n,T_{\mathrm{I}}(n)+T_{\mathrm{II}}(n)\geq 0$, this implies
$\lim_{n\to\infty}T_{\mathrm{II}}(n)=0$ almost surely, thus completing the
proof.

It remains to prove (6.5), the 0-1 loss analog of which was proved in Hanneke
et al., Eq. (3.4). That argument does not hold for general losses, and we
present the novel argument below. We bound the left-hand side of (6.5) using a
function $n\mapsto t_{\gamma}(n)\in o(n)$, used to upper bound the compression
size; the latter is furnished by Lemma 5.

$\displaystyle\operatorname{\mathbb{P}}[Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))>R^{*}+\varepsilon]$
$\displaystyle\leq$
$\displaystyle\operatorname{\mathbb{P}}\left[Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))>R^{*}+\varepsilon\;\wedge\;\mathsf{mm}_{\gamma}(S_{n})\leq\frac{\varepsilon}{18L}\;\wedge\;M_{n}(\gamma)\leq
t_{\gamma}(n)\right]$
$\displaystyle\,+\,\operatorname{\mathbb{P}}[\mathsf{mm}_{\gamma}(S_{n})>\frac{\varepsilon}{18L}]+\operatorname{\mathbb{P}}[M_{n}(\gamma)>t_{\gamma}(n)]=:P_{\mathrm{I}}+P_{\mathrm{II}}+P_{\mathrm{III}}.$

We estimate $P_{\mathrm{I}}$ via a union bound:

$\displaystyle\operatorname{\mathbb{P}}\left[Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))>R^{*}+\varepsilon\;\wedge\;\mathsf{mm}_{\gamma}(S_{n})\leq\frac{\varepsilon}{18L}\;\wedge\;M_{n}(\gamma)\leq
t_{\gamma}(n)\right]$
$\displaystyle\leq\sum_{d=1}^{t_{\gamma}(n)}\operatorname{\mathbb{P}}\Big{[}Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))>R^{*}+\varepsilon\;\wedge\;\mathsf{mm}_{\gamma}(S_{n})\leq\frac{\varepsilon}{18L}\;\wedge\;M_{n}(\gamma)=d\Big{]}.$

Thus, it suffices to bound each term in the summation separately. Applying
Lemma 8 and summing, we have, for $n$ sufficiently large that
$t_{\gamma}(n)\leq n$,

$\displaystyle
P_{\mathrm{I}}\leq\sum_{d=1}^{t_{\gamma}(n)}p_{d}\;\leq\;t_{\gamma}(n)(e^{-\frac{n\varepsilon^{2}}{32}}+e^{-\frac{1}{2}n\nu^{2}})\leq
n(e^{-\frac{n\varepsilon^{2}}{32}}+e^{-\frac{1}{2}n\nu^{2}}).$ (6.8)

Now, using the function $t_{\gamma}$, we note that $P_{\mathrm{III}}\leq
1/n^{2}$ thanks to Lemma 5. A bound on $P_{\mathrm{II}}$, which bounds the
$\gamma$-missing-mass $\mathsf{mm}_{\gamma}(S_{n})$, is furnished by Lemma 6.
Taking $n$ sufficiently large so that $u_{\gamma}(n)$, as furnished by Lemma
6, satisfies $u_{\gamma}(n)\leq\varepsilon/36L$, and invoking Lemma 6 with
$t=\varepsilon/36L$, we have
$P_{\mathrm{II}}=\operatorname{\mathbb{P}}[\mathsf{mm}_{\gamma}(S_{n})>\varepsilon/18L]\leq
e^{-\frac{n\varepsilon^{2}}{1296L^{2}}}.$ Plugging this, (6.8), and
$P_{\mathrm{III}}\leq 1/n^{2}$ into (6) yields (6.5), which completes the
proof. ∎

##  7 Extensions

###  7.1 Countable ${\cal Y}$ with finite diameter:
${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal Y}\right\|<\infty}$

In this section we describe an extension of ${\mathsf{MedNet}}_{|{\cal
Y}|<\infty}$, denoted ${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal
Y}\right\|<\infty}$, which is strongly Bayes-consistent for countably infinite
${\cal Y}$, but still with a finite diameter. A modification of
${\mathsf{MedNet}}_{|{\cal Y}|<\infty}$ is required because the latter uses a
compression scheme with $b=\log_{2}|{\cal Y}|$ bits of side information.

Our variant is formally presented in Algorithm 3 and operates as follows. We
fix in advance a specific sequence $b_{n}\in\mathbb{N}$, to be specified in
the sequel. The family of $\gamma$-nets over the input sample is generated
exactly as in ${\mathsf{MedNet}}_{|{\cal Y}|<\infty}$. For each $\gamma$-net,
${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal Y}\right\|<\infty}$ (presented
in Section A.2) computes the _truncated empirical medoid labels_ in the
Voronoi cells defined by the partition
$\mathcal{V}(\bm{X}(\gamma))=\\{V_{1}(\bm{X}(\gamma)),\ldots,V_{M}(\bm{X}(\gamma))\\}$.
These labels are denoted by ${\bm{Y}}^{\prime}(\gamma)\in\mathsf{pref}({\cal
Y},b_{n})^{M}$. Formally, for $i\in[M]$,

$\displaystyle
Y^{\prime}_{i}:=\mathop{\mathrm{argmin}}_{y\in\mathsf{pref}({\cal
Y},b_{n})}{\sum_{j\in[n]:X_{j}\in V_{i}}\ell(y,Y_{j})},$ (7.1)

where $\mathsf{pref}({\cal Y},b):=\left\\{y\in{\cal Y}^{\prime}:\omega(y)\leq
2^{b}\right\\}$ for $b\in\mathbb{N}$, for some fixed canonical injection
$\omega:{\cal Y}\to\mathbb{N}$. In words, $\mathsf{pref}({\cal Y},b_{n})$ is a
sample-dependent, cardinality-based truncation of the label space. Other than
the truncation, ${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal
Y}\right\|<\infty}$ behaves exactly as ${\mathsf{MedNet}}_{|{\cal
Y}|<\infty}$.

######  Theorem 10 (proof in Section B.6).

Let $({\cal X},\rho)$ be a separable metric space, and ${\cal Y}$ a
_countable_ label space with a loss function $\ell\leq L<\infty$. Then there
is a choice of $\delta_{n\in\mathbb{N}}$ and truncation schedule
$b_{n\in\mathbb{N}}$ such that the sequence of hypotheses $h_{n}$ computed by
${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal
Y}\right\|<\infty}(S_{n},\delta_{n},b_{n})$ is strongly Bayes consistent:
$\operatorname{\mathbb{P}}[\lim_{n\rightarrow\infty}R(h_{n})=R^{*}]=1.$

###  7.2 Countable metric space $({\cal Y},\ell)$ with unbounded diameter:
${\mathsf{MedNet}}^{\aleph_{0}}$

In this section, we extend ${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal
Y}\right\|<\infty}$ to the case where $({\cal Y},\ell)$ is a countable metric
space. That is, the loss $\ell$ is now assumed to be a metric, but the
boundedness condition $\left\|{\cal Y}\right\|<\infty$ is relaxed to
boundlessness-in-expectation (BIE):
$\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty$ for some
$y_{0}\in{\cal Y}$. Boundedness was used in the analysis of
${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal Y}\right\|<\infty}$ in order to
invoke a distribution-free concentration inequality (Hoeffding’s). The present
extension, denoted ${\mathsf{MedNet}}^{\aleph_{0}}$, invokes
${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal Y}\right\|<\infty}$ as a
subroutine with an appropriately diameter-truncated label space. The latter is
defined as follows. Fix a $y_{0}\in{\cal Y}$ that is a witness of the BIE
property333 Lemma 18 shows that if BIE holds then every $y^{\prime}\in{\cal
Y}$ is such a witness, and in particular, we may always choose $y_{0}$ as the
“first” element under the canonical ordering. . For $y\in{\cal Y}$ and $L>0$,
define $\llbracket{\cal Y}\rrbracket_{L}:=B(y_{0},L)$ and the diameter-
truncation operation

$\displaystyle y\wedge L:=\mathop{\mathrm{argmin}}_{\hat{y}\in\llbracket{\cal
Y}\rrbracket_{L}}\ell(y,\hat{y}).$ (7.2)

In words, $y\wedge L$ is the closest $\hat{y}$ to $y$ in the $L$-ball about
$y_{0}$.

${\mathsf{MedNet}}^{\aleph_{0}}$ is formally presented in Algorithm 2 and
operates as follows. The cardinality- and diameter-truncation schedules
$b_{n\in\mathbb{N}}$ and $L_{n\in\mathbb{N}}$ are fixed in advance; the former
as any $b_{n}\in o(n)$ and the latter specified in the sequel. Next, the
labels $Y_{i}$ of the input sample are truncated to $\llbracket
Y_{i}\rrbracket:=Y_{i}\wedge L_{n};$ this is a substantive difference from the
cardinality-based truncation in ${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal
Y}\right\|<\infty}$, which does not modify the sample labels.

Assumptions : $({\cal X},\rho)$ is a separable metric space, $({\cal Y},\ell)$
a BIE countable metric space

Input : Sample $S_{n}=(X_{i},Y_{i})_{i\in[n]}$, $\delta_{n}\in(0,1)$,
$b_{n}\in\mathbb{N}$, $L_{n}>0$

Output : predictor $h:{\cal X}\to{\cal Y}$

Set $\llbracket S_{n}\rrbracket:=\\{(X_{i},\llbracket
Y_{i}\rrbracket):i\in[n]\\}$, where $\llbracket Y_{i}\rrbracket:=Y_{i}\wedge
L_{n}$ ;

Set $h_{n}:={\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal
Y}\right\|<\infty}(\llbracket S_{n}\rrbracket,\delta_{n},b_{n})$ in
_truncated_ label space $\llbracket{\cal Y}\rrbracket_{L_{n}}$

Set $h_{n}:={\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal
Y}\right\|<\infty}~{}~{}~{}~{}~{}~{}~{}$ (i.e., ${\cal Y}$ in (6.3) is
replaced with $\llbracket{\cal Y}\rrbracket_{L_{n}}$) ;

return $h=h_{n}$

Algorithm 2 ${\mathsf{MedNet}}^{\aleph_{0}}$

######  Theorem 11 (proof in Section B.7).

Let $({\cal X},\rho)$ and $({\cal Y},\ell)$ be metric spaces, separable and
countable, respectively, equipped with a product distribution ${\bar{\mu}}$
such that BIE holds for ${\cal Y}$. Then there is a choice of
$\delta_{n\in\mathbb{N}}$ and truncation schedules $b_{n\in\mathbb{N}}$,
$L_{n\in\mathbb{N}}$ such that the sequence of hypotheses $h_{n}$ computed by
${\mathsf{MedNet}}^{\aleph_{0}}(S_{n},\delta_{n},b_{n},L_{n})$ is strongly
Bayes consistent:
$\displaystyle\operatorname{\mathbb{P}}[\lim_{n\rightarrow\infty}R(h_{n})=R^{*}]=1.$

The only remaining extension to render the proof of Theorem 1 complete is from
countable to separable $({\cal Y},\ell)$; this straightforward step is carried
out in Section A.1.

## References

  * Ashlagi et al. (2021) Y. Ashlagi, L. Gottlieb, and A. Kontorovich.  Functions with average smoothness: structure, algorithms, and learning.  In M. Belkin and S. Kpotufe, editors, _Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA_ , volume 134 of _Proceedings of Machine Learning Research_ , pages 186–236. PMLR, 2021\.  URL http://proceedings.mlr.press/v134/ashlagi21a.html.
  * Baharav and Tse (2019) T. Z. Baharav and D. Tse.  Ultra fast medoid identification via correlated sequential halving.  In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. B. Fox, and R. Garnett, editors, _NeurIPS_ , 2019\.  URL https://proceedings.neurips.cc/paper/2019/hash/c4de8ced6214345614d33fb0b16a8acd-Abstract.html.
  * Bardenet and Maillard (2015) R. Bardenet and O.-A. Maillard.  Concentration inequalities for sampling without replacement.  _Bernoulli_ , 21(3):1361 – 1385, 2015.  doi: 10.3150/14-BEJ605.  URL https://doi.org/10.3150/14-BEJ605.
  * Biess et al. (2019) A. Biess, A. Kontorovich, Y. Makarychev, and H. Zaichyk.  Regression via kirszbraun extension with applications to imitation learning.  _CoRR_ , abs/1905.11930, 2019.  URL http://arxiv.org/abs/1905.11930.
  * Blanchard (2021) M. Blanchard.  Universal strong and weak online learning with bounded loss, preprint.  2021\.
  * Blanchard and Cosson (2021) M. Blanchard and R. Cosson.  Universal online learning with bounded loss: Reduction to binary classification.  2021\.
  * Blanchard et al. (2021) M. Blanchard, R. Cosson, and S. Hanneke.  Universal online learning with unbounded losses: Memory is all you need.  2021\.
  * Bousquet et al. (2020) O. Bousquet, S. Hanneke, S. Moran, and N. Zhivotovskiy.  Proper learning, helly number, and an optimal SVM bound.  In J. D. Abernethy and S. Agarwal, editors, _Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]_ , volume 125 of _Proceedings of Machine Learning Research_ , pages 582–609. PMLR, 2020.  URL http://proceedings.mlr.press/v125/bousquet20a.html.
  * der Laan et al. (2003) M. V. der Laan, K. Pollard, and J. Bryan.  A new partitioning around medoids algorithm.  _Journal of Statistical Computation and Simulation_ , 73(8):575–584, 2003.  doi: 10.1080/0094965031000136012.  URL https://doi.org/10.1080/0094965031000136012.
  * Evans and Jaffe (2020) S. N. Evans and A. Q. Jaffe.  Strong laws of large numbers for Fréchet means, 2020.
  * Ferraty et al. (2011) F. Ferraty, A. Laksaci, A. Tadj, and P. Vieu.  Kernel regression with functional response.  _Electronic Journal of Statistics_ , 5(none):159 – 171, 2011.  doi: 10.1214/11-EJS600.  URL https://doi.org/10.1214/11-EJS600.
  * Fraigniaud et al. (2008) P. Fraigniaud, E. Lebhar, and L. Viennot.  The inframetric model for the internet.  In _IEEE INFOCOM 2008 - The 27th Conference on Computer Communications_ , pages 1085–1093, 2008.  doi: 10.1109/INFOCOM.2008.163.
  * Gottlieb et al. (2014) L. Gottlieb, A. Kontorovich, and R. Krauthgamer.  Efficient classification for metric data (extended abstract COLT 2010).  _IEEE Transactions on Information Theory_ , 60(9):5750–5759, 2014.  doi: 10.1109/TIT.2014.2339840.  URL http://dx.doi.org/10.1109/TIT.2014.2339840.
  * Gottlieb et al. (2016) L.-A. Gottlieb, A. Kontorovich, and R. Krauthgamer.  Adaptive metric dimensionality reduction (extended abstract: ALT 2013).  _Theoretical Computer Science_ , pages 105–118, 2016.
  * Gottlieb et al. (2017) L.-A. Gottlieb, A. Kontorovich, and R. Krauthgamer.  Efficient regression in metric spaces via approximate Lipschitz extension.  _IEEE Transactions on Information Theory_ , 63(8):4838–4849, 2017.
  * Györfi and Weiss (2021) L. Györfi and R. Weiss.  Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces.  _Journal of Machine Learning Research_ , 22(151):1–25, 2021.  URL http://jmlr.org/papers/v22/20-1081.html.
  * Györfi et al. (2002) L. Györfi, M. Kohler, A. Krzyżak, and H. Walk.  _A Distribution-Free Theory of Nonparametric Regression_.  Springer-Verlag New York, Inc., 2002.
  * Hanneke (2021a) S. Hanneke.  Universally consistent online learning with arbitrarily dependent responses, preprint.  2021a.
  * Hanneke (2021b) S. Hanneke.  Learning whenever learning is possible: Universal learning under general stochastic processes.  _Journal of Machine Learning Research_ , 22(130):1–116, 2021b.  URL http://jmlr.org/papers/v22/17-298.html.
  * Hanneke and Kontorovich (2021) S. Hanneke and A. Kontorovich.  Stable sample compression schemes: New applications and an optimal SVM margin bound.  In V. Feldman, K. Ligett, and S. Sabato, editors, _Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide_ , volume 132 of _Proceedings of Machine Learning Research_ , pages 697–721. PMLR, 2021\.  URL http://proceedings.mlr.press/v132/hanneke21a.html.
  * Hanneke et al. (2021) S. Hanneke, A. Kontorovich, S. Sabato, and R. Weiss.  Universal Bayes consistency in metric spaces.  _The Annals of Statistics_ , 49(4):2129 – 2150, 2021.  doi: 10.1214/20-AOS2029.  URL https://doi.org/10.1214/20-AOS2029.
  * Kontorovich and Weiss (2014) A. Kontorovich and R. Weiss.  A Bayes consistent 1-NN classifier.  In _Artificial Intelligence and Statistics (AISTATS 2015)_ , 2014\.
  * Kpotufe and Verma (2017) S. Kpotufe and N. Verma.  Time-accuracy tradeoffs in kernel prediction: Controlling prediction quality.  _J. Mach. Learn. Res._ , 18:44:1–44:29, 2017.  URL http://jmlr.org/papers/v18/16-538.html.
  * Maurer and Pontil (2009) A. Maurer and M. Pontil.  Empirical bernstein bounds and sample variance penalization, 2009.
  * Morvant et al. (2012) E. Morvant, S. Koço, and L. Ralaivola.  PAC-bayesian generalization bound on confusion matrix for multi-class classification.  In _Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012_. icml.cc / Omnipress, 2012.  URL http://icml.cc/2012/papers/434.pdf.
  * Naor (2015) A. Naor.  Metric embeddings and lipschitz extensions, 2015.
  * Naor and Sheffield (2012) A. Naor and S. Sheffield.  Absolutely minimal lipschitz extension of tree-valued mappings.  _Mathematische Annalen_ , 354(3):1049–1078, Nov. 2012.  ISSN 0025-5831.  doi: 10.1007/s00208-011-0753-1.
  * Newling and Fleuret (2017) J. Newling and F. Fleuret.  A sub-quadratic exact medoid algorithm.  In A. Singh and X. J. Zhu, editors, _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA_ , volume 54 of _Proceedings of Machine Learning Research_ , pages 185–193. PMLR, 2017\.  URL http://proceedings.mlr.press/v54/newling17a.html.
  * Pollard (2002) D. Pollard.  _A user’s guide to measure theoretic probability_.  Cambridge University Press, 2002.
  * Schervish (1995) M. J. Schervish.  _Theory of statistics_.  Springer Series in Statistics. Springer-Verlag, New York, 1995.  ISBN 0-387-94546-6.  doi: 10.1007/978-1-4612-4250-5.  URL https://doi.org/10.1007/978-1-4612-4250-5.
  * Schötz (2021) C. Schötz.  Strong laws of large numbers for generalizations of Fréchet mean sets, 2021.

##  Appendix A Deferred results

###  A.1 Separable metric space $({\cal Y},\ell)$ with unbounded diameter

The extension from countable to separable $({\cal Y},\ell)$ — implemented by
the final, subscript-free version of ${\mathsf{MedNet}}$— is quite
straightforward. The approximation arguments we invoke are standard, and hence
we only give a sketch of the proof. In Section E, we give a countable
discretization ${\cal Y}_{\varepsilon}\subseteq{\cal Y}$, with a corresponding
discretized version ${\bar{\mu}}_{\varepsilon}$ of ${\bar{\mu}}$ and the
induced Bayes-optimal risk $R^{*}_{\varepsilon}$ on the discretized space.
Theorem 20 guarantees that $R^{*}_{\varepsilon}\to R^{*}$ as $\varepsilon\to
0$.

As discussed in the Introduction, we assume access to an oracle that takes
$\varepsilon>0$ as input and returns a (necessarily at most countable, due to
separability) $\varepsilon$-net ${\cal Y}_{\varepsilon}$ of ${\cal Y}$. Given
this oracle, ${\mathsf{MedNet}}$ operates as follows. First, a sequence
$\varepsilon_{n}\downarrow 0$ is fixed. For each $n\in\mathbb{N}$, the sample
$S_{n}$ is drawn and the $\varepsilon$-net ${\cal Y}_{n}:={\cal
Y}_{\varepsilon_{n}}$ is constructed. Next, each label $Y_{i}$ in $S_{n}$ is
projected onto ${\cal Y}_{n}$ — i.e., replaced by $Y_{i}^{\prime}\in{\cal
Y}_{n}$ that is closest to $Y_{i}$. The resulting modified sample
$S_{n}^{\prime}$ is then fed into ${\mathsf{MedNet}}^{\aleph_{0}}$ with the
additional arguments $\delta_{n},b_{n},L_{n}$ as in Theorem 11. The latter
shows that almost surely, the the constructed predictor’s risk minus
$R^{*}_{\varepsilon_{n}}$ decays to zero.444 Formally, Theorem 11 proves
convergence on a fixed label space ${\cal Y}$, but a standard diagonal
argument lets us apply it to the sequence ${\cal Y}_{n}$ and conclude the
aforementioned claim.  This, coupled with Theorem 20, implies Theorem 1:

######  Theorem 12.

Let $({\cal X},\rho)$ and be $({\cal Y},\ell)$ separable metric spaces
equipped with a product distribution ${\bar{\mu}}$ such that BIE holds for
${\cal Y}$. For any $\varepsilon_{n}\downarrow 0$, let ${\cal Y}_{n}$ be a
sequence of $\varepsilon_{n}$-nets as above. Discretize each sample
$S_{n}\sim{\bar{\mu}}^{n}$ to $S_{n}^{\prime}$ with labels in ${\cal Y}_{n}$,
as above. Then there is a choice of $\delta_{n\in\mathbb{N}}$ and truncation
schedules $b_{n\in\mathbb{N}}$, $L_{n\in\mathbb{N}}$ such that the sequence of
hypotheses $h_{n}$ computed by
${\mathsf{MedNet}}^{\aleph_{0}}(S_{n}^{\prime},\delta_{n},b_{n},L_{n})$ is
strongly Bayes consistent:
$\operatorname{\mathbb{P}}[\lim_{n\rightarrow\infty}R(h_{n})=R^{*}]=1.$

###  A.2 The ${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal Y}\right\|<\infty}$
algorithm

Assumptions : Let $({\cal X},\rho)$ be a separable metric space, and ${\cal
Y}$ a _countable_ label space with a loss function $\ell$ such that
$L:=\left\|{\cal Y}\right\|<\infty$.

Input : Sample $S_{n}=(X_{i},Y_{i})_{i\in[n]}$, confidence
$\delta_{n}\in(0,1)$, side-information size $b_{n}\in\mathbb{N}$

Output : predictor $h:{\cal X}\to{\cal Y}$

Let
$\Gamma:=(\left\\{\rho(X_{i},X_{j}):i,j\in[n]\right\\}\cup\\{\infty\\})\setminus\\{0\\}$;

for  _$\gamma\in\Gamma$_ do

Let $\bm{X}(\gamma)$ be a $\gamma$-net of $\\{X_{1},\ldots,X_{n}\\}$;

Let $M_{n}(\gamma):=|\bm{X}(\gamma)|$;

For each $i\in[M_{n}(\gamma)]$, let $Y^{\prime}_{i}(\gamma)$ be the _truncated
empirical medoid label_ of $V_{i}(\bm{X}(\gamma))$ as in (7.1) ;

Set $S^{\prime}_{n}(\gamma):=(\bm{X}(\gamma),{\bm{Y}}^{\prime}(\gamma))$;

Set $h_{S^{\prime}_{n}(\gamma)}:=x\mapsto
Y_{\mathsf{nn}}(x,S^{\prime}_{n}(\gamma))$.

Set $\alpha_{n}(\gamma):=\widehat{R}(h_{S^{\prime}_{n}(\gamma)};S_{n})$;

end for

Find
$\gamma^{*}_{n}\in\mathop{\mathrm{argmin}}_{\gamma\in\Gamma}Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma),b_{n},\delta,L)$,
where $Q_{n}$ is defined in (4.1);

Set $S^{\prime}_{n}:=S^{\prime}_{n}({\gamma^{*}_{n}})$;

return $h=h_{S^{\prime}_{n}}$;

Algorithm 3 ${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal Y}\right\|<\infty}$

##  Appendix B Auxiliary Proofs

###  B.1 Proof of Lemma 7

######  Lemma.

Let $({\cal X},\rho)$ be a separable metric space, and ${\cal Y}$ a _finite_
label space with a loss function $\ell$. For any fixed scale
$\gamma\in\Gamma$, the procedure in Algorithm 1 generating
$h_{S^{\prime}_{n}(\gamma)}$ is a semi-stable compression scheme.

###### Proof.

Fix a $\gamma\in\Gamma$. Define $b:=\log_{2}|{\cal Y}|$ and the map
$\mathsf{bits}:{\cal Y}\to\left\\{0,1\right\\}^{b}$ as one that converts the
lexicographic index of $y\in{\cal Y}$ to its unique $b$-bit binary
representation. Our compression function:

$\displaystyle\left({\cal X}\times{\cal Y}\right)^{+}\to\left({\cal
X}\times{\cal Y}\right)^{+}\times\\{0,1\\}^{b}.$

Recall our notation $\bm{i}_{\gamma}$ as the $\gamma$-net indices calculated
and selected for a sample $S_{n}\sim({\cal X}\times{\cal Y})^{n}$, and ${\bf
Y}^{\prime}(\bm{i}_{\gamma})$ the empirical medoid labels of a $\gamma$-net
$\bm{X}(\bm{i}_{\gamma})$, as defined in (6.3). Let $\kappa$ be such that
$\kappa(S_{n})=(\kappa_{\mathsf{cs}}(S_{n}),\kappa_{\mathsf{si}}(S_{n}))$,
where

$\displaystyle\kappa_{\mathsf{cs}}(S_{n})$
$\displaystyle=S_{n}(\bm{i}_{\gamma})\in\left({\cal X}\times{\cal
Y}\right)^{|\bm{i}_{\gamma^{*}}|}$ $\displaystyle\kappa_{\mathsf{si}}(S_{n})$
$\displaystyle=\left\\{\mathsf{bits}(Y^{\prime}):Y^{\prime}\in{\bf
Y}^{\prime}(\bm{i}_{\gamma})\right\\}\in\left(\\{0,1\\}^{b}\right)^{|\bm{i}_{\gamma^{*}}|}.$

In words, $\kappa_{\mathsf{cs}}$ compresses the sample $S_{n}$ to a specific
$\gamma$-net keeping original labels, while $\kappa_{\mathsf{si}}$ calculates
the respective empirical limited medoid labels of the resulting sub-sample. As
for the reconstruction function

$\displaystyle\psi:\left({\cal X}\times{\cal
Y}\right)^{+}\times\\{0,1\\}^{b}\to{\cal Y}^{\cal X},$

it is defined as

$\displaystyle\psi\left(S_{n}(\bm{i}_{\gamma}),{\bf
Y}^{\prime}(\bm{i}_{\gamma})\right)=h_{S_{n}\left(\bm{i}_{\gamma},{\bf
Y}^{\prime}(\bm{i}_{\gamma})\right)};$

in words, we take the $1$-nearest-neighbor rule predictor of the sub-sample
$S_{n}(\bm{i}_{\gamma})$ labeled by ${\bf Y}^{\prime}(\bm{i}_{\gamma})$.

It remains to argue that our compression scheme is semi-stable. Indeed, since
the scale $\gamma$ is fixed and the net is constructed in a deterministic
fashion, for any $S^{\prime}$ satisfying $\kappa_{\mathsf{cs}}(S_{n})\subseteq
S^{\prime}\subseteq S_{n}$, the $\gamma$-net computed by the algorithm will be
the same. Therefore
$\kappa_{\mathsf{cs}}(S^{\prime})=\kappa_{\mathsf{cs}}(S_{n})$ and the
definition follows. ∎

###  B.2 Proof of Lemma 3

######  Lemma.

Let ${\cal X}$, ${\cal Y}$, $\ell$, $L$, and $S_{n}$ be as in Theorem 2. For
$k\leq n$, define

$\displaystyle Q(n,\alpha,k,b,\delta,L):=Q_{n}(\alpha,k,b,\delta,L)$
$\displaystyle:=\left(20\sqrt{\frac{k}{n}}+20\sqrt{\frac{b}{n}}+15\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}+1\right)\alpha$
$\displaystyle\quad+(6L+18)\frac{k}{n}+8L\sqrt{\frac{k}{n}}+(2L+12)\frac{b}{n}+7L\sqrt{\frac{b}{n}}$
$\displaystyle\quad+(3L+10)\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6L\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}.$

Then the function $Q$ satisfies the following properties:

  1. Q1.

For any $n\in\mathbb{N}$ and $\delta\in(0,1)$, with probability at least
$1-\delta$ over $S_{n}\sim{\bar{\mu}}^{n}$, for all $\alpha\in[0,L]$,
$k\in[n]$, $b\in\mathbb{N}$: If $(S^{\prime}_{n},h_{S^{\prime}_{n}})$ is an
$(\alpha,k,b)$-semi-stable-compression of $S_{n}$, then

$R(h_{S^{\prime}_{n}})\leq Q_{n}(\alpha,k,b,\delta,L).$

  2. Q2.

For any fixed $n\in\mathbb{N}$ and $\delta\in(0,1)$, $Q$ is monotonically
increasing in $\alpha$ and in $k$.

  3. Q3′′.

There is a sequence $\\{\delta_{n}\\}_{n=1}^{\infty}$, $\delta_{n}\in(0,1)$
such that $\sum_{n=1}^{\infty}\delta_{n}<\infty$, and for any $k_{n}\in o(n)$
we have that

$\displaystyle\lim_{n\rightarrow\infty}\sup_{\alpha\in[0,L]}(Q_{n}(\alpha,k_{n},b,\delta_{n},L)-\alpha)=0.$

###### Proof.

Let ${\cal X}$ be an instance space, and ${\cal Y}$ a label space with a loss
function $\ell$ such that $L:=\left\|{\cal Y}\right\|<\infty$. Starting from
Q1, let $(S^{\prime}_{n},h_{S^{\prime}_{n}})$ be an $(\alpha,k,b)$-semi-
stable-compression of $S_{n}$. Thus, $Q$ satisfies property Q1 by Theorem 2.

Furthermore, property Q2 (monotonicity in $\alpha$ and in $k$) can also be
easily verified from the definition in (4.1).

To establish Q3′′, an inspection of
$Q_{n}(\alpha,k_{n},b,\delta_{n},L)-\alpha$ shows that since $k_{n}\in o(n)$,
only the terms containing $\frac{\ln(\frac{4e^{2}}{\delta_{n}})}{n}$ are not
obviously decaying to zero. To ensure the latter, any choice of $\delta_{n}$
with $-\log\delta_{n}\in o(n)$ suffices. The additional constraint
$\delta_{n}$ must satisfy is $\sum_{n=1}^{\infty}\delta_{n}<\infty$; one such
choice $\delta_{n}=e^{-\sqrt{n}}$. ∎

###  B.3 Proof of Lemma 4

######  Lemma.

Let ${\bar{\mu}}$ be a probability measure on ${\cal X}\times{\cal Y}$ with
${\cal X}$-marginal $\mu$, where ${\cal X}$ is a metric probability space, and
${\cal Y}$ a _countable_ label space with a loss function $\ell$ such that
$L:=\left\|{\cal Y}\right\|<\infty$. For any $\nu>0$, there exists a diameter
$\beta=\beta(\nu)>0$ such that for any countable measurable partition ${\cal
V}=\\{V_{1},\dots\\}$ of ${\cal X}$ and any measurable set $W\subseteq{\cal
X}$ satisfying

  * $\mathrm{(}\textup{i})$

$\mu({\cal X}\setminus W)\leq\nu$

  * $\mathrm{(}\textup{ii})$

$\sup_{V\in{\cal V}}\left\|V\cap W\right\|\leq\beta$,

the true medoid predictor $h_{{\cal V},W}^{*}$ defined in (5.2) satisfies

$\displaystyle R(h_{{\cal V},W}^{*})\leq R^{*}+9L\nu.$

###### Proof.

We begin similarly to the proof of Hanneke et al. (2021, Lemma 3.6). Let
$\eta_{y}:{\cal X}\to[0,1]$ be the conditional probability function for label
$y\in{\cal Y}$,

$\displaystyle\eta_{y}(x)=\operatorname{\mathbb{P}}(Y=y\,|\,X=x),$

and let $\zeta_{y}:{\cal X}\to[0,L]$ be the expected loss function for the
label $y\in{\cal Y}$:

$\displaystyle\zeta_{y}(x)=\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(y,Y)\,|\,X=x\right]=\int_{y^{\prime}\in\mathcal{Y}}\ell(y,y^{\prime})\eta_{y^{\prime}}(x)\mathrm{d}\mu$

which is measurable by Schervish (1995, Corollary B.22).

Define $\tilde{\eta}_{y}:{\cal X}\to[0,1]$ as $\eta_{y}$’s conditional
expectation function with respect to $({\cal V},W)$: For $x$ such that
$I_{\cal V}(x)\cap W\neq\emptyset$,

$\displaystyle\tilde{\eta}_{y}(x)=\operatorname{\mathbb{P}}(Y=y\,|\,X\in
I_{\cal V}(x)\cap W)=\frac{\int_{I_{\cal V}(x)\cap
W}\eta_{y}(z)\mathop{}\\!\mathrm{d}\mu(z)}{\mu(I_{\cal V}(x)\cap W)}.$

Otherwise, if $I_{\cal V}(x)\cap W=\emptyset$, define
$\tilde{\eta}_{y}(x)=\bm{{1}}[y\text{ is lexicographically first}]$. Note that
$(\tilde{\eta}_{y})_{y\in{\cal Y}}$ are piecewise constant on the cells of the
restricted partition ${\cal V}\cap W$. Accordingly, define
$\tilde{\zeta}_{y}\to[0,L]$:

$\displaystyle\tilde{\zeta}_{y}(x)=\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(y,Y)\,|\,X\in
I_{\cal V}(x)\cap
W\right]=\sum_{y^{\prime}\in\mathcal{Y}}\ell(y,y^{\prime})\tilde{\eta}_{y^{\prime}}(x).$

In the proof of Hanneke et al., there is no appearance of $\zeta_{y}$ or
$\tilde{\zeta}_{y}$; there, the much simpler conditional error probabilities
suffice. Note likewise that their local majority vote classifier has been
replaced here by the local medoid. By definition, the Bayes-optimal predictor
$h^{*}$ and the true medoid predictor $h^{*}_{{\cal V},W}$ satisfy

$\displaystyle h^{*}(x)$ $\displaystyle=$
$\displaystyle\mathop{\mathrm{argmin}}_{y\in{\cal Y}}\zeta_{y}(x),$
$\displaystyle h^{*}_{{\cal V},W}(x)$ $\displaystyle=$
$\displaystyle\mathop{\mathrm{argmin}}_{y\in{\cal Y}}\tilde{\zeta}_{y}(x).$

It follows that

$\displaystyle\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(h^{*}_{{\cal
V},W}(X),Y)\,|\,X=x\right]$
$\displaystyle-\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(h^{*}(X),Y)\,|\,X=x\right]$
$\displaystyle=\zeta_{h^{*}_{{\cal V},W}(x)}(x)-\zeta_{h^{*}(x)}(x)$
$\displaystyle=\zeta_{h^{*}_{{\cal V},W}(x)}(x)-\tilde{\zeta}_{h^{*}_{{\cal
V},W}(x)}(x)+\tilde{\zeta}_{h^{*}_{{\cal
V},W}(x)}(x)-\tilde{\zeta}_{h^{*}(x)}(x)$
$\displaystyle+\tilde{\zeta}_{h^{*}(x)}(x)-\zeta_{h^{*}(x)}(x)$
$\displaystyle\leq\zeta_{h^{*}_{{\cal V},W}(x)}(x)-\tilde{\zeta}_{h^{*}_{{\cal
V},W}(x)}(x)+\tilde{\zeta}_{h^{*}(x)}(x)-\zeta_{h^{*}(x)}(x)$
$\displaystyle\leq 2\max_{y^{\prime}\in\left\\{h^{*}_{{\cal
V},W}(x),h^{*}(x)\right\\}}\left|\zeta_{y^{\prime}}(x)-\tilde{\zeta}_{y^{\prime}}(x)\right|$
$\displaystyle=2\max_{y^{\prime}\in\left\\{h^{*}_{{\cal
V},W}(x),h^{*}(x)\right\\}}\left|\sum_{y\in\mathcal{Y}}\ell(y^{\prime},y)\left(\eta_{y}(x)-\tilde{\eta}_{y}(x)\right)\right|$
$\displaystyle\leq
2L\left|\sum_{y\in\mathcal{Y}}\left(\eta_{y}(x)-\tilde{\eta}_{y}(x)\right)\right|$
$\displaystyle\leq
2L\sum_{y\in\mathcal{Y}}\left|\eta_{y}(x)-\tilde{\eta}_{y}(x)\right|.$

By condition $\mathrm{(}\textup{i})$ in the lemma statement, $\mu({\cal
X}\setminus W)\leq\nu$. Thus,

$\displaystyle R(h^{*}_{{\cal V},W})-R^{*}$ $\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(h^{*}_{{\cal
V},W}(X),Y)\right]-\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(h^{*}(X),Y)\right]$
$\displaystyle=$ $\displaystyle\int_{{\cal X}\setminus
W}\left(\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(h^{*}_{{\cal
V},W}(X),Y)\,|\,X=x\right]-\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(h^{*}(X),Y)\,|\,X=x\right]\right)\mathrm{d}\mu(x)$
$\displaystyle\quad+\int_{W}\left(\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(h^{*}_{{\cal
V},W}(X),Y)\,|\,X=x\right]-\mathop{\mathbb{E}}_{\bar{\mu}}\left[\ell(h^{*}(X),Y)\,|\,X=x\right]\right)\mathrm{d}\mu(x)$
$\displaystyle\leq$ $\displaystyle L\cdot\mu({\cal X}\setminus
W)+2L\int_{W}\sum_{y\in\mathcal{Y}}\left|\eta_{y}(x)-\tilde{\eta}_{y}(x)\right|\mathrm{d}\mu(x)$
$\displaystyle\leq$ $\displaystyle
L\nu+2L\sum_{y\in\mathcal{Y}}\int_{W}\left|\eta_{y}(x)-\tilde{\eta}_{y}(x)\right|\mathrm{d}\mu(x).$

Let ${\cal Y}_{\nu}\subseteq{\cal Y}$ be a finite set of labels such that
$\operatorname{\mathbb{P}}[Y\in{\cal Y}_{\nu}]\geq 1-\nu$. Then

$\displaystyle\sum_{y\notin{\cal
Y}_{\nu}}\int_{W}\left|\eta_{y}(x)-\tilde{\eta}_{y}(x)\right|\mathrm{d}\mu(x)$
$\displaystyle\leq$ $\displaystyle\sum_{y\notin{\cal
Y}_{\nu}}\int_{W}\eta_{y}(x)\mathrm{d}\mu(x)$ $\displaystyle=$
$\displaystyle\sum_{y\notin{\cal
Y}_{\nu}}\int_{W}\operatorname{\mathbb{P}}_{\bar{\mu}}(Y=y\,|\,X=x)\mathrm{d}\mu(x)$
$\displaystyle=$ $\displaystyle\sum_{y\notin{\cal
Y}_{\nu}}\operatorname{\mathbb{P}}_{\bar{\mu}}(Y=y,X\in W)$
$\displaystyle\leq$ $\displaystyle\sum_{y\notin{\cal
Y}_{\nu}}\operatorname{\mathbb{P}}(Y=y)$ $\displaystyle=$
$\displaystyle\operatorname{\mathbb{P}}(y\notin{\cal Y}_{\nu})\leq\nu.$

We conclude:

$\displaystyle R(h^{*}_{{\cal V},W})-R^{*}\leq 3L\nu+2L\sum_{y\in{\cal
Y}_{\nu}}\int_{W}|\eta_{y}(x)-\tilde{\eta}_{y}(x)|\mathrm{d}\mu(x).$ (B.1)

To bound the integrals in (B.1), we invoke a result from the proof of Lemma
3.6 in Hanneke et al. (2021), which showed that

$\displaystyle\sum_{y\in{\cal
Y}_{\nu}}\int_{W}|\eta_{y}(x)-\tilde{\eta}_{y}(x)|\mathop{}\\!\mathrm{d}\mu(x)\leq\sum_{y\in{\cal
Y}_{\nu}}\frac{3\nu}{|{\cal Y}_{\nu}|}=3\nu.$

Applying this bound to (B.1), we conclude $R(h^{*}_{{\cal V},W})-R^{*}\leq
9L\nu.$ ∎

###  B.4 Proof of Lemma 8

######  Lemma.

Let ${\bar{\mu}}$ be a probability measure on ${\cal X}\times{\cal Y}$, where
${\cal X}$ is a metric probability space, and ${\cal Y}$ a _countable_ label
space endowed with a loss function $\ell\leq L<\infty$. Let $t_{\gamma}$ as in
Lemma 5. Then there exist functions $\varepsilon\mapsto\gamma(\varepsilon)$
and
$\varepsilon\mapsto\gamma:=\nu(\varepsilon)\in(0,\frac{\varepsilon}{176L})$
such that for each $\varepsilon,b>0$ there is an
$N_{0}(\nu(\varepsilon),b,\delta_{n},t_{\gamma})$ such that for all $n\geq
N_{0}$, and all $d\in[t_{\gamma}(n)]$,

$\displaystyle p_{d}$
$\displaystyle:=\operatorname{\mathbb{P}}\Big{[}Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma),b,\delta_{n},L)>R^{*}\\!+\varepsilon\;\wedge\;\mathsf{mm}_{\gamma}(S_{n})\\!\leq\\!\frac{\varepsilon}{18L}\;\wedge\;M_{n}(\gamma)\\!=\\!d\Big{]}\leq
e^{-\frac{n\varepsilon^{2}}{32}}+e^{-\frac{1}{2}n\nu^{2}}\\!,$

where $M_{n}(\gamma)$ is defined in (6.2).

###### Proof.

We begin the proof similarly to Hanneke et al. (2021, Lemma 3.5) and then
diverge in order to extend their 0-1 loss to the general loss setting. Let
$\bm{i}=\bm{i}(\gamma)\in[n]^{d}$ be the set of indices in the net
$\bm{X}=\bm{X}(\gamma)$ selected by the algorithm. Let ${\bm{Y}}^{*}\in{\cal
Y}^{d}$ be the true medoid labels with respect to the restricted partition
$\mathcal{V}(\bm{X})\cap\textrm{UB}_{2\gamma}(\bm{X})$,

$\displaystyle({\bm{Y}}^{*})_{j}=y^{*}(V_{j}\cap\textrm{UB}_{2\gamma}(\bm{X})),\qquad
j\in[d].$ (B.2)

We pair $\bm{X}$ with the labels $\bm{Y}^{*}$ to obtain the labeled set

$\displaystyle
S_{n}(\bm{i},*):=S_{n}(\bm{i},{\bm{Y}}^{*})=(\bm{X},\bm{Y}^{*})\in({\cal
X}\times{\cal Y})^{d}.$ (B.3)

Note that conditioned on $\bm{X}$, $S_{n}(\bm{i},*)$ does not depend on the
rest of $S_{n}$.

The induced $1$-NN predictor $h_{S_{n}(\bm{i},*)}(x)$ can be expressed as
$h_{{\cal V},W}^{*}(x)=y^{*}(I_{\cal V}(x)\cap W)$ with ${\cal
V}=\mathcal{V}(\bm{X})$ and $W=\textrm{UB}_{2\gamma}(\bm{X})$ (see (5.2) for
the definition of $h_{{\cal V},W}^{*}$). We now show that

$\displaystyle\mathsf{mm}_{\gamma}(\bm{X}_{n})\leq\frac{\varepsilon}{18L}\quad\implies\quad
R(h_{S_{n}(\bm{i},*)})\leq R^{*}+\varepsilon/2,$ (B.4)

by showing that under the assumption
$\mathsf{mm}_{\gamma}(\bm{X}_{n})\leq\frac{\varepsilon}{18L}$, the conditions
of Lemma 4 hold for $\mathcal{V},W$ as defined above. To this end, we bound
the diameter of the partition $\mathcal{V}\cap
W=\mathcal{V}\cap\textrm{UB}_{2\gamma}(\bm{X})$, and the measure of the
missing mass $\mu({\cal X}\setminus W)=\mathsf{mm}_{2\gamma}(\bm{X})$ under
the assumption.

To bound the diameter of the partition
$\mathcal{V}\cap\textrm{UB}_{2\gamma}(\bm{X})$, let $x\in
V_{j}\cap\textrm{UB}_{2\gamma}(\bm{X})$. Note that $V_{j}$ is the Voronoi cell
centered at $x_{i_{j}}\in\bm{X}$. Then
$\rho(x,x_{i_{j}})=\min_{i\in\bm{i}}\rho(x,x_{i})$ and, since
$x\in\textrm{UB}_{2\gamma}(\bm{X})$, $\min_{i\in\bm{i}}\rho(x,x_{i})\leq
2\gamma$. Thus,

$\displaystyle\left\|{\cal V}\cap
W\right\|=\max_{j}\left\|V_{j}\cap\textrm{UB}_{2\gamma}(\bm{X})\right\|\leq
4\gamma.$

To bound $\mathsf{mm}_{2\gamma}(\bm{X})$ under the assumption
$\mathsf{mm}_{\gamma}(\bm{X}_{n})\leq\frac{\varepsilon}{18L}$, observe that
for all $z\in\textrm{UB}_{\gamma}(\bm{X}_{n})$, there is some $i\in[n]$ such
that $z\in B_{\gamma}(x_{i})$. For this $i$, there is some $j\in\bm{i}$ such
that $x_{i}\in B_{\gamma}(x_{j})$, since $\bm{X}$ is a $\gamma$-net of
$\bm{X}_{n}$. Therefore $z\in B_{2\gamma}(x_{j})$. Thus,
$z\in\textrm{UB}_{2\gamma}(\bm{X})$. It follows that
$\textrm{UB}_{\gamma}(\bm{X}_{n})\subseteq\textrm{UB}_{2\gamma}(\bm{X})$, thus
$\mathsf{mm}_{2\gamma}(\bm{X})\leq\mathsf{mm}_{\gamma}(\bm{X}_{n})$. Under the
assumption, we thus have
$\mathsf{mm}_{2\gamma}(\bm{X})\leq\frac{\varepsilon}{18L}$. Hence, by the
choice of $\gamma=\gamma(\varepsilon)$ in the statement of the lemma, Lemma 4
implies (B.4).

To bound $Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))$, we consider the
relationship between the hypothetical true medoid predictor
$h_{S_{n}(\bm{i},*)}$ and the actual predictor returned by the algorithm,
$h_{S_{n}(\bm{i},\bm{{\bm{Y}}^{\prime}})}$. Firstly, for any $\nu\in(0,1)$,
there exists a finite ${\cal Y}^{\prime}_{\nu}\subseteq{\cal Y}$ such that
$\operatorname{\mathbb{P}}\left[Y\in{\cal Y}^{\prime}_{\nu}\right]\geq 1-\nu$.
Therefore, since $b$ is non-decreasing in $n$, there exists an $N_{1}(\nu)$
large enough such that for any $n\geq N_{1}(\nu)$ ${\cal
Y}^{\prime}_{\nu}\subseteq\mathsf{pref}({\cal Y},b)$. Fix such a $\nu$
specifically such that $\nu<\frac{\varepsilon}{176L}$. Thus we have that
$\operatorname{\mathbb{P}}\left[Y\in\mathsf{pref}({\cal Y},b)\right]\geq
1-\nu$.

For brevity we denote

$\displaystyle Q_{n}(\alpha,k):=Q_{n}(\alpha,k,b,\delta_{n},L).$

Let us split our cases:

$\displaystyle p_{d}$ $\displaystyle=$
$\displaystyle\operatorname{\mathbb{P}}\big{[}Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))>R^{*}+\varepsilon\;\;\wedge\;\;\mathsf{mm}_{\gamma}(\bm{X}_{n})\leq\frac{\varepsilon}{18L}\;\;\wedge\;\;M_{n}(\gamma)=d$
(B.5)
$\displaystyle\;\;\;\;\;\wedge\;\;\widehat{R}(h_{S_{n}(\bm{i},\bm{{\bm{Y}}^{\prime}})};S_{n})\leq\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})+2\nu
L\big{]}+$
$\displaystyle+\quad\operatorname{\mathbb{P}}\big{[}Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))>R^{*}+\varepsilon\;\;\wedge\;\;\mathsf{mm}_{\gamma}(\bm{X}_{n})\leq\frac{\varepsilon}{18L}\;\;\wedge\;\;M_{n}(\gamma)=d$
$\displaystyle\;\;\;\;\;\wedge\;\;\widehat{R}(h_{S_{n}(\bm{i},\bm{{\bm{Y}}^{\prime}})};S_{n})>\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})+2\nu
L\big{]}$ $\displaystyle:=$ $\displaystyle(p_{d})_{1}+(p_{d})_{2}.$

Now, let ${\bf Y}^{*}$ be the best medoids possible for the sample, from the
entire label space ${\cal Y}$:

$\displaystyle\widehat{R}(h_{S_{n}(\bm{i},{\bf Y}^{*})};S_{n})=\min_{{\bf
Y}\in{\cal Y}^{d}}\widehat{R}(h_{S_{n}(\bm{i},{\bf Y})};S_{n}).$

This means:

$\displaystyle\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{*})};S_{n})\leq\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})};S_{n})\qquad\text{ and }\qquad\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{*})};S_{n})\leq\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}).$

Specifically, we note that since

$\displaystyle\widehat{R}(h_{S_{n}(\bm{i},{\bf Y}^{\prime})};S_{n})=\min_{{\bf
Y}\in\mathsf{pref}({\cal Y},b_{n})^{d}}\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y})};S_{n}),$

we have that

$\displaystyle\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})};S_{n})-\widehat{R}(h_{S_{n}(\bm{i},{\bf Y}^{*})};S_{n})$
$\displaystyle=\frac{1}{n}\sum_{(X,Y)\in S_{n},Y\notin\mathsf{pref}({\cal
Y},b_{n})}\ell(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})}(X),Y)-\ell(h_{S_{n}(\bm{i},{\bf Y}^{*})}(X),Y)$
$\displaystyle\leq\frac{1}{n}L\left|\left\\{(X,Y)\in
S_{n},Y\notin\mathsf{pref}({\cal Y},b_{n})\right\\}\right|$
$\displaystyle\Rightarrow\mathop{\mathbb{E}}\left[\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})};S_{n})-\widehat{R}(h_{S_{n}(\bm{i},{\bf Y}^{*})};S_{n})\right]$
$\displaystyle\leq\frac{1}{n}L\cdot\nu n=\nu L.$

Hence, we observe:

$\displaystyle\mathop{\mathbb{E}}\left[\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})};S_{n})-\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{*})};S_{n})\right]\leq\nu L\qquad\text{ and
}\qquad\mathop{\mathbb{E}}\left[\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{*})};S_{n})-\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})\right]\leq 0,$

whence

$\displaystyle\mathop{\mathbb{E}}\left[\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})};S_{n})-\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})\right]\leq\nu L.$

Next, Hoeffding’s inequality implies that for any $t>0$:

$\displaystyle\operatorname{\mathbb{P}}\left(\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})};S_{n})-\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})>\nu
L+t\right)<\exp\left(-\frac{nt^{2}}{2L^{2}}\right).$

Taking $t=\nu L$ we get:

$\displaystyle(p_{d})_{2}\leq\operatorname{\mathbb{P}}\left(\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})};S_{n})-\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})>2\nu
L\right)<\exp\left(-\frac{1}{2}n\nu^{2}\right).$

Next, we examine the case $\widehat{R}(h_{S_{n}(\bm{i},{\bf
Y}^{\prime})};S_{n})-\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})\leq 2\nu L$, and
use the monotonicity Property Q2 of $Q$:

$\displaystyle Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))$ $\displaystyle\leq
Q_{n}\left(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})+2\nu L,M_{n}(\gamma)\right)$
$\displaystyle\leq
Q_{n}\left(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),M_{n}(\gamma)\right)+2\nu
L\left(20\sqrt{\frac{M_{n}(\gamma)}{n}}+20\sqrt{\frac{b}{n}}+15\sqrt{\frac{\ln(\frac{4e^{2}}{\delta_{n}})}{n}}+1\right)$
$\displaystyle\leq
Q_{n}\left(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),M_{n}(\gamma)\right)+2\nu
L\left(21+20\sqrt{\frac{b}{n}}+15\sqrt{\frac{\ln(\frac{4e^{2}}{\delta_{n}})}{n}}\right)$
$\displaystyle:=Q_{n}\left(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),M_{n}(\gamma)\right)+2\nu
L\cdot F_{n}(b,\delta_{n}).$

Examining, $F_{n}(b,\delta_{n})$ we note (as shown in the proof of Lemma 3)
that for $n$ sufficiently large (larger than some $N_{2}(b,\delta_{n})$), we
have $F_{n}(b,\delta_{n})\leq 22$. Thus,

$\displaystyle Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))\leq
Q_{n}\left(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),M_{n}(\gamma)\right)+44\nu
L.$ (B.6)

Combining (B.4) and (B.6),

$\displaystyle\Big{\\{}Q_{n}(\alpha_{n}(\gamma),M_{n}(\gamma))>R^{*}+\varepsilon\;\;\wedge\;\;\mathsf{mm}_{\gamma}(\bm{X}_{n})\leq\frac{\varepsilon}{18L}\;\;\wedge\;\;M_{n}(\gamma)=d$
$\displaystyle\;\;\;\;\;\wedge\;\;\widehat{R}(h_{S_{n}(\bm{i},\bm{{\bm{Y}}^{\prime}})};S_{n})\leq\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})\Big{\\}}$
$\displaystyle\qquad\;\implies\;\left\\{Q_{n}(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),d)+44\nu
L>R(h_{S_{n}(\bm{i},*)})+\frac{\varepsilon}{2}\;\;\wedge\;\;|\bm{i}|=d\right\\}.$

Thus, for all $d\leq t_{\gamma}$,

$\displaystyle(p_{d})_{1}$
$\displaystyle\leq\operatorname{\mathbb{P}}\left[Q_{n}(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),d)>R(h_{S_{n}(\bm{i},*)})+\frac{\varepsilon}{2}-44\nu
L\;\wedge\;|\bm{i}|=d\right]$
$\displaystyle\leq\operatorname{\mathbb{P}}\Big{[}\exists\bm{i}\in[n]^{d}:Q_{n}(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),d)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad>R(h_{S_{n}(\bm{i},*)})+\frac{\varepsilon}{2}-44\nu
L\Big{]}.$ (B.7)

To bound the last expression, let $\bm{i}\in[n]^{d}$ and denote

$\displaystyle r_{d,n}=\sup_{\alpha\in(0,L)}(Q_{n}(\alpha,d)-\alpha).$

We therefore have

$\displaystyle
Q_{n}(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),d)\leq\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})+r_{d,n}.$

Let $\bm{i}^{\prime}=\\{1,\dots,n\\}\setminus\bm{i}$ and note that

$\displaystyle\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n})\leq\frac{n-d}{n}\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}(\bm{i}^{\prime}))+\frac{d}{n}.$

Combining the two inequalities above, we get

$\displaystyle
Q_{n}(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),d)\leq\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}(\bm{i}^{\prime}))+\frac{d}{n}+r_{d,n}.$

Recalling $t_{\gamma}\in o(n)$, by Property Q3′′,

$\displaystyle\lim_{n\to\infty}\frac{t_{\gamma}}{n}+r_{t_{\gamma},n}=0.$

In addition, by Q2, we have $r_{d,n}\leq r_{t_{\gamma},n}$ for all $d\leq
t_{\gamma}$. Hence, using our $\nu<\frac{\varepsilon}{176L}$, we take $n$
sufficiently large (larger than some $N_{3}(t_{\gamma})$), so that for all
$d\leq t_{\gamma}$,

$\displaystyle\frac{d}{n}+r_{d,n}\leq\frac{t_{\gamma}}{n}+r_{t_{\gamma},n}\leq\frac{\varepsilon}{4}-44\nu
L,$

and thus

$\displaystyle
Q_{n}(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),d)\leq\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}(\bm{i}^{\prime}))+\frac{\varepsilon}{4}-44\nu
L.$

Therefore, for any $n\geq
N_{0}(\nu,b,\delta_{n},t_{\gamma}):=\max\\{N_{1},N_{2},N_{3}\\}$,

$\displaystyle
Q_{n}(\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}),d)>R(h_{S_{n}(\bm{i},*)})+\frac{\varepsilon}{2}-44\nu
L$
$\displaystyle\qquad\qquad\implies\quad\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}(\bm{i}^{\prime}))>R(h_{S_{n}(\bm{i},*)})+\frac{\varepsilon}{4}.$

Now,

$\displaystyle\operatorname{\mathbb{P}}\left[\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}(\bm{i}^{\prime}))>R(h_{S_{n}(\bm{i},*)})+\frac{\varepsilon}{4}\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{S_{n}(\bm{i})}\left[\operatorname{\mathbb{P}}_{S_{n}(\bm{i}^{\prime})\,|\,S_{n}(\bm{i})}\left[\widehat{R}(h_{S_{n}(\bm{i},*)};S_{n}(\bm{i}^{\prime}))>R(h_{S_{n}(\bm{i},*)})+\frac{\varepsilon}{4}\right]\right].$

Since $\operatorname{\mathbb{P}}_{S_{n}(\bm{i}^{\prime})\,|\,S_{n}(\bm{i})}$
is a product distribution, by Hoeffding’s inequality we have that (B.4) is
bounded above by $e^{-2(n-d)(\frac{\varepsilon}{4})^{2}}$. Since
$h_{S_{n}(\bm{i},*)}$ is invariant to permutations of $\bm{i}$’s entries,
bounding (B.7) by a union bound over $\bm{i}$ yields

$\displaystyle(p_{d})_{1}\leq\binom{n}{d}e^{-2(n-d)(\frac{\varepsilon}{4})^{2}}\leq
e^{d\log\left(\frac{en}{d}\right)-2(n-d)(\frac{\varepsilon}{4})^{2}},$

where we used $\binom{n}{d}\leq\left(\frac{en}{d}\right)^{d}$. Selecting $n$
large enough so that for all $d\leq t_{\gamma}$ we have
$d\log(en/d)\leq(n-d)(\frac{\varepsilon}{4})^{2}$ and $d\leq n/4$. Combining
this with (B.7) proves the lemma. ∎

###  B.5 Proof of Lemma 5

######  Lemma.

Let $({\cal X},\rho,\mu)$ be a separable metric probability space. For
$S_{n}\sim\mu^{n}$, let ${\bm{X}}(\gamma)$ be any $\gamma$-net of $S_{n}$.
Then, for any $\gamma>0$, there exists a function
$t_{\gamma}:\mathbb{N}\to\mathbb{R}_{+}$ in $o(n)$ such that
$\displaystyle\operatorname{\mathbb{P}}\left[\sup_{\gamma\text{-}\mathrm{nets}\,\,{\bm{X}}(\gamma)}|{\bm{X}}(\gamma)|\geq
t_{\gamma}(n)\right]\leq 1/n^{2}.$

###### Proof.

Almost identical to Hanneke et al. (2021, Lemma 3.7) — the former has a factor
of $2$ multiplying $|{\bm{X}}(\gamma)|$ — and hence omitted. ∎

###  B.6 Proof of Theorem 10

######  Theorem.

Let $({\cal X},\rho)$ be a separable metric space, and ${\cal Y}$ a
_countable_ label space with a loss function $\ell\leq L<\infty$. Then there
is a choice of $\delta_{n\in\mathbb{N}}$ and truncation schedule
$b_{n\in\mathbb{N}}$ such that the sequence of hypotheses $h_{n}$ computed by
${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal
Y}\right\|<\infty}(S_{n},\delta_{n},b_{n})$ is strongly Bayes consistent:
$\operatorname{\mathbb{P}}[\lim_{n\rightarrow\infty}R(h_{n})=R^{*}]=1.$

###### Proof.

The claim will follow if we succeed in showing how the lemmas and theorems
invoked in proving Bayes consistency of ${\mathsf{MedNet}}_{|{\cal
Y}|<\infty}$ (Theorem 9) are applicable in the present setting.

In Lemma 7, which established that the procedure is a semi-stable compression
scheme a globally constant $b=\log_{2}|{\cal Y}|$ was used. The claim remains
perfectly true if the size of the label space happens to depend on the sample
size, which is precisely how the result is being invoked in the present
setting.

Next, we argue that the $Q_{n}$ bound in Lemma 3 remains valid for
sufficiently slowly growing $b_{n}$, and our chosen rate of $o(n)$ suffices.
The remaining lemmas 4 and 8 can be used freely since they allow for countable
label spaces. Lemmas 5 and 6 likewise do not require any modifications. Thus,
we have shown how a straightforward modification of the proof of Theorem 9
also proves the theorem in question. ∎

###  B.7 Proof of Theorem 11

######  Theorem.

Let $({\cal X},\rho)$ and $({\cal Y},\ell)$ be metric spaces, separable and
countable, respectively, equipped with a product distribution ${\bar{\mu}}$
such that BIE holds for ${\cal Y}$. Then there is a choice of
$\delta_{n\in\mathbb{N}}$ and truncation schedules $b_{n\in\mathbb{N}}$,
$L_{n\in\mathbb{N}}$ such that the sequence of hypotheses $h_{n}$ computed by
${\mathsf{MedNet}}^{\aleph_{0}}(S_{n},\delta_{n},b_{n},L_{n})$ is strongly
Bayes consistent:
$\displaystyle\operatorname{\mathbb{P}}[\lim_{n\rightarrow\infty}R(h_{n})=R^{*}]=1.$

###### Proof.

Let $Q$ be the generalization bound as defined in Lemma 3, and set the input
confidence $\delta$ for input size $n$ to $\delta_{n}$ as stipulated by Q3′′.
Choose any $b_{n}\in o(n)$, and $L_{n}$ such that
$L_{n}^{2}k_{n},L_{n}^{2}b_{n},L_{n}^{2}\ln(\frac{4e^{2}}{\delta_{n}})\in
o(n)$. Similarly, we choose $k_{n}\in o(n)$ arbitrarily (cf. Lemma 3). Given a
sample $S_{n}\sim{\bar{\mu}}^{n}$, we abbreviate the optimal empirical error
$\llbracket\alpha_{n}^{*}\rrbracket=\alpha(\gamma^{*}_{n})$ and the optimal
compression size $\llbracket M_{n}^{*}\rrbracket=M(\gamma^{*}_{n})$ as
computed by Algorithm 1 on our truncated sample. Let $\llbracket
h_{n}\rrbracket$ be the output of ${\mathsf{MedNet}}^{\aleph_{0}}$,

$\displaystyle\llbracket
f_{n}^{*}\rrbracket:=\mathop{\mathrm{argmin}}_{f:{\cal X}\to{\cal Y}\wedge
L_{n}}R(f),$

be the Bayes-optimal predictor for the truncated label space and

$\displaystyle\llbracket R_{n}^{*}\rrbracket:=R(\llbracket
f_{n}^{*}\rrbracket).$

be the optimal risk in the _truncated setting_ on our modified sample. For
brevity we denote

$\displaystyle Q_{n}(\alpha,k):=Q_{n}(\alpha,k,b,\delta_{n},L_{n}).$

To prove Theorem 11, we first follow the standard technique, used also in
Theorem 9, of decomposing the excess error over the Bayes error into two
terms:

$\displaystyle R(\llbracket h_{n}\rrbracket)-\llbracket
R(f_{n}^{*})\rrbracket$ $\displaystyle=$ $\displaystyle\big{(}R(\llbracket
h_{n}\rrbracket)-Q_{n}(\alpha_{n}^{*},M_{n}^{*})\big{)}+\big{(}Q_{n}(\alpha_{n}^{*},M_{n}^{*})-\llbracket
R(f_{n}^{*})\rrbracket\big{)}$ $\displaystyle=:$ $\displaystyle
T_{\mathrm{I}}(n)+T_{\mathrm{II}}(n).$

We now show that each term decays to zero almost surely. Regarding,
$T_{\mathrm{I}}(n)$ we wish to invoke Lemmas 7 and 3 as in the proof of
Theorem 9. The argument of Lemma 7, which shows that
${\mathsf{MedNet}}^{\aleph_{0}}_{\left\|{\cal Y}\right\|<\infty}$ is a semi-
stable compression scheme, applies verbatim to
${\mathsf{MedNet}}^{\aleph_{0}}$.

As for Lemma 3, properties Q1 and Q2 trivially continue to hold, while to
ensure Q3′′, we constrain the choice of the diameter truncation schedule
$L_{n}$ to satisfy
$L_{n}^{2}k_{n},L_{n}^{2}b_{n},L_{n}^{2}\ln(\frac{4e^{2}}{\delta_{n}})\in
o(n)$, where $k_{n}\in o(n)$ is as in Lemma 3. Having verified the
applicability of Lemmas 7 and 3, we invoke property Q1 from Lemma 3:

$\displaystyle\operatorname{\mathbb{P}}\\!\left[R(\llbracket
h_{n}\rrbracket)-Q_{n}(\alpha_{n}^{*},M_{n}^{*})>0\right]\leq\delta_{n},\qquad
n\geq 1.$

Since $\delta_{n}$ was chosen as furnished by Lemma 3(Q3′′), the Borel-
Cantelli lemma implies that
$\limsup_{n\to\infty}T_{\mathrm{I}}(n)\leq 0$ with probability $1$.

We now proceed to argue that the generalization bound
$Q_{n}(\alpha_{n}^{*},M_{n}^{*})$ approaches the truncated optimal Bayes error
$\llbracket R_{n}^{*}\rrbracket$, which will establish
$\limsup_{n\to\infty}T_{\mathrm{II}}(n)\leq 0$ almost surely. Since Lemmas 4,
8, 5 and 6 do not rely on $L_{n}$ being fixed, the are applicable to our
setting. Thus, the argument from the proof of Theorem 9 applies here as well,
and thus $\limsup_{n\to\infty}T_{\mathrm{II}}(n)\leq 0$ almost surely. It
follows that $\lim_{n\to\infty}R(\llbracket h_{n}\rrbracket)-\llbracket
R_{n}^{*}\rrbracket=0$. It remains to exploit the BIE property of ${\cal Y}$
and invoke Theorem 19 to conclude that $\lim_{n\to\infty}\llbracket
R(f_{n}^{*})\rrbracket-R^{*}=0$, whence

$\displaystyle\lim_{n\to\infty}R(\llbracket h_{n}\rrbracket)-R^{*}=0.$

∎

##  Appendix C Compression Scheme Theorems

In this section we introduce a series of new theorems regarding semi-stable
compression schemes, each leading to the next, culminating in Theorem 2 which
is used to bound the generalization of ${\mathsf{MedNet}}$.

###  C.1 Definitions

###  C.2 Setting

Let ${\cal X}$ be an instance space, and ${\cal Y}$ of finite diameter, and
${\bar{\mu}}$ a distribution supported on the product Borel $\sigma$-algebra
of ${\cal X}\times{\cal Y}$, such that ${\cal Y}$ is bounded by some $L>0$:
$\forall y_{1},y_{2}\in{\cal Y}:\ell(y_{1},y_{2})\leq L$.

###  C.3 Theorems & Lemmas

####  C.3.1 Semi-stable Agnostic sample compression scheme of given size

######  Theorem 13.

For any $k,b\in\mathbb{N}\cup\\{0\\}$, let $(\kappa,\psi)$ be any semi-stable
compression scheme of size at most $k$ using at most $b$ bits of side-
information. For any distribution ${\bar{\mu}}$ over ${\cal X}\times{\cal Y}$,
any $n\in\mathbb{N}$ with $n>2k$, and any $\delta\in(0,1)$, for
$S_{n}\sim{\bar{\mu}}^{n}$, with probability at least $1-\delta$

$\displaystyle\left|R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})\right|$
$\displaystyle\leq\sqrt{\frac{4L^{2}}{n-2k}\left(k\ln(4)+\ln(4/\delta)\right)}+\sqrt{\frac{L^{2}}{n-2k}b\ln(2)}.$

###### Proof.

If $k=0$, the result trivially follows from Hoeffding’s inequality, so let us
suppose $k\geq 1$. As in the proof of Theorem 5 in Bousquet et al. (2020), fix
any $T_{n}\in[n-1]$ and let $\mathcal{I}_{n}$ be any family of subsets of
$[n]$ with the properties that each $I\in\mathcal{I}_{n}$ has $|I|\leq
n-T_{n}$, and for every $i_{1},\dots,i_{k}\in[n]$ there exists
$I\in\mathcal{I}_{n}$ such that $\\{i_{1},\dots,i_{k}\\}\subseteq I$. In
particular, Bousquet et al. construct a family $\mathcal{I}_{n}$ satisfying
the properties above with $T_{n}=k\lfloor\frac{n}{2k}\rfloor$, and with
$|\mathcal{I}_{n}|=\binom{2k}{k}<4^{k}$: namely, let $D_{1},\dots,D_{2k}$ be
any partition of $[n]$ with each
$|D_{i}|\in\\{\lfloor\frac{n}{2k}\rfloor,\lceil\frac{n}{2k}\rceil)\\}$, and
define
$\mathcal{I}_{n}=\left\\{\bigcup\\{D_{j}:j\in\mathcal{J}\\}:\mathcal{J}\subseteq[2k],|\mathcal{J}|=k\right\\}$;
that is, $\mathcal{I}_{n}$ contains all unions of exactly $k$ of the $2k$ sets
$D_{j}$.

Let there be a sample $S_{n}\sim{\bar{\mu}}^{n}$. Recall our notation that for
any $I\in\mathcal{I}_{n}$ we have $S(I)\subseteq S_{n}$. For any
$I\in\mathcal{I}_{n}$, define $\bar{I}:=[n]\setminus I$. Let
$\sigma:[n]\to[n]$ be a uniformly random permutation of $[n]$, and for any
$I=(i_{1},\dots,i_{\ell})\subseteq[n]$ define
$\bm{\sigma}(I):=(\sigma(i_{1}),\dots,\sigma(i_{\ell}))$.

Next, for any $I\subseteq[n]$ and any $\bm{b}\in\\{0,1\\}^{b}$, let
$\hat{h}_{I,\bm{b}}:=\psi\left(\kappa_{\mathsf{cs}}\left(S\left(I\right)\right),\bm{b}\right)$.
Now, since $S(\bar{I})$ is independent of $S(I)$, Hoeffding’s Inequality
(applied under the conditional distribution given $S(I)$) and the law of total
probability imply that with probability
$1-\frac{\delta}{2|\mathcal{I}_{n}|\cdot 2^{b}}$:

$\displaystyle\left|R\left(\hat{h}_{I,\bm{b}}\right)-\widehat{R}\left(\hat{h}_{I,\bm{b}};S\left(\bar{I}\right)\right)\right|$
$\displaystyle\leq\sqrt{\frac{L^{2}\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{2(n-|I|)}}$
$\displaystyle=\sqrt{\frac{L^{2}\left(\ln(|\mathcal{I}_{n}|)+b\ln(2)+\ln(4/\delta)\right)}{2(n-|I|)}}.$

Applying this under the conditional distribution given $\sigma$, together with
the union bound and the law of total probability, we have that with
probability at least $1-\frac{\delta}{2}$, every $I\in\mathcal{I}_{n}$ and
every $\bm{b}\in\\{0,1\\}^{b}$ has

$\displaystyle\left|R\left(\hat{h}_{\bm{\sigma}^{-1}\left(I\right),\bm{b}}\right)-\widehat{R}\left(\hat{h}_{\bm{\sigma}^{-1}\left(I\right),\bm{b}};S\left(\overline{\bm{\sigma}^{-1}\left(I\right)}\right)\right)\right|$
$\displaystyle\leq\sqrt{\frac{L^{2}\left(\ln(|\mathcal{I}_{n}|)+b\ln(2)+\ln(4/\delta)\right)}{2(n-|I|)}}.$

In particular, let $\bm{i}^{*}$ be the indices such that

$\displaystyle\kappa_{\mathsf{cs}}(S_{n})=\left\\{(X_{i},Y_{i})\in
S_{n}:i\in\bm{i}^{*}\right\\}=S_{n}(\bm{i}^{*}).$

Now, by property (ii) of $\mathcal{I}_{n}$ there must exist
$I^{*}\in\mathcal{I}_{n}$ such that

$\displaystyle\bm{\sigma}(\bm{i}^{*})\subseteq I^{*},$

which means:

$\displaystyle\Rightarrow\quad$
$\displaystyle\bm{i}^{*}\subseteq\bm{\sigma}^{-1}(I^{*})$
$\displaystyle\Rightarrow\quad$
$\displaystyle\kappa_{\mathsf{cs}}(S_{n})=S_{n}(\bm{i}^{*})\subseteq
S_{n}(\bm{\sigma}^{-1}(I^{*})).$

Due to the semi-stability property of $(\kappa,\psi)$ and since
$S_{n}(\bm{\sigma}^{-1}(I^{*}))\subseteq S_{n}$, this implies

$\displaystyle\Rightarrow\psi(\kappa_{\mathsf{cs}}(S_{n}(\bm{\sigma}^{-1}(I^{*}))),\kappa_{\mathsf{si}}(S_{n}))=\psi(\kappa_{\mathsf{cs}}(S_{n}),\kappa_{\mathsf{si}}(S_{n}))=\psi(\kappa\left(S_{n}\right)).$

Thus, on the above event of probability at least $1-\frac{\delta}{2}$ we get,
for $I=I^{*}$ and $\bm{b}=\kappa_{\mathsf{si}}(S_{n})$,

$\displaystyle\left|R(\psi(\kappa\left(S_{n}\right)))-\widehat{R}(\psi(\kappa\left(S_{n}\right));S(\overline{\bm{\sigma}^{-1}(I^{*})}))\right|\leq\sqrt{\frac{L^{2}\left(\ln(|\mathcal{I}_{n}|)+b\ln(2)+\ln(4/\delta)\right)}{2(n-|I^{*}|)}}.$

Furthermore, by property (i) of $I_{n}$ we have that $n-|I^{*}|\geq T_{n}$,
and so

$\displaystyle\left|R(\psi(\kappa\left(S_{n}\right)))-\widehat{R}(\psi(\kappa\left(S_{n}\right));S(\overline{\bm{\sigma}^{-1}(I^{*})}))\right|\leq\sqrt{\frac{L^{2}\left(\ln(|\mathcal{I}_{n}|)+b\ln(2)+\ln(4/\delta)\right)}{2T_{n}}}.$
(C.1)

Next, we want to relate
$\widehat{R}(\psi(\kappa\left(S_{n}\right));S(\overline{\bm{\sigma}^{-1}(I^{*})}))$
to $\widehat{R}(\psi(\kappa\left(S_{n}\right));S_{n})$. Let
$\hat{h}:=\psi(\kappa\left(S_{n}\right))$. For each $i\in[n]$, let
$\ell_{i}:=\ell(\hat{h}(X_{i}),Y_{i})$. For any $I\in\mathcal{I}_{n}$, by
Hoeffding’s inequality without replacement (Bardenet and Maillard, 2015)
applied under the conditional distribution given $S_{n}$, together with the
law of total probability, with probability at least
$1-\frac{\delta}{2|\mathcal{I}_{n}|}$ it holds that

$\displaystyle\left|\frac{1}{n-|I|}\sum_{i\in\overline{\bm{\sigma}^{-1}(I)}}\ell_{i}-\widehat{R}(\psi(\kappa\left(S_{n}\right));S_{n})\right|\leq\sqrt{\frac{L^{2}\ln(4|\mathcal{I}_{n}|/\delta)}{2(n-|I|)}}.$

By the union bound, this holds simultaneously for all $I\in\mathcal{I}_{n}$
with probability at least $1-\frac{\delta}{2}$. In particular, taking
$I=I^{*}$, and recalling that $n-|I^{*}|\geq T_{n}$, on this event we have
that

$\displaystyle\left|\widehat{R}(\psi(\kappa\left(S_{n}\right));S(\overline{\bm{\sigma}^{-1}(I^{*})}))-\widehat{R}(\psi(\kappa\left(S_{n}\right));S_{n})\right|\leq\sqrt{\frac{L^{2}\ln(4|\mathcal{I}_{n}|/\delta)}{2T_{n}}}$
(C.2)

By the union bound, the above two events (each of probability at least
$1-\frac{\delta}{2}$) hold simultaneously with probability at least
$1-\delta$, in which case (C.1) and (C.2) together imply

$\displaystyle\left|R(\psi(\kappa\left(S_{n}\right)))-\widehat{R}(\psi(\kappa\left(S_{n}\right));S_{n})\right|$
$\displaystyle\leq\left|R(\psi(\kappa\left(S_{n}\right)))-\widehat{R}(\psi(\kappa\left(S_{n}\right));S(\overline{\bm{\sigma}^{-1}(I^{*})}))\right|+$
$\displaystyle\quad+\left|\widehat{R}(\psi(\kappa\left(S_{n}\right));S(\overline{\bm{\sigma}^{-1}(I^{*})}))-\widehat{R}(\psi(\kappa\left(S_{n}\right));S_{n})\right|$
$\displaystyle\leq\sqrt{\frac{L^{2}\left(\ln(|\mathcal{I}_{n}|)+b\ln(2)+\ln(4/\delta)\right)}{2T_{n}}}+\sqrt{\frac{L^{2}\ln(4|\mathcal{I}_{n}|/\delta)}{2T_{n}}}$
$\displaystyle\leq\sqrt{\frac{4L^{2}\left(\ln(|\mathcal{I}_{n}|)+\ln(4/\delta)\right)}{2T_{n}}}+\sqrt{\frac{L^{2}b\ln(2)}{2T_{n}}}$

The theorem now immediately follows from plugging the aforementioned family
$\mathcal{I}_{n}$ from Bousquet et al. (2020), having
$|\mathcal{I}_{n}|=\binom{2k}{k}<4^{k}$ and
$T_{n}=k\left\lfloor\frac{n}{2k}\right\rfloor>\frac{n-2k}{2}$. ∎

####  C.3.2 Accounting for realizable case

######  Lemma 14.

Let $Z_{1},\dots,Z_{n}$ be i.i.d random variables with values in $[0,L]$ for
some $L>0$, and let $\delta>0$. Define
${\bar{Z}}:=\frac{1}{n}\sum_{i=1}^{n}Z_{i}$. Then with probability at least
$1-\delta$ we have:

$\displaystyle\mathop{\mathbb{E}}[{\bar{Z}}]-{\bar{Z}}\leq{\bar{Z}}\cdot\sqrt{\frac{2\ln(4/\delta)}{n-1}}+L\sqrt{\frac{2\ln(4/\delta)}{n-1}}+\frac{7L\ln(4/\delta)}{3(n-1)}.$

###### Proof.

Let ${Z^{\prime}}_{i}:=\frac{Z_{i}}{L}\in[0,1]$ for all $i\in\\{1,\dots,n\\}$.
Using the empirical Bernstein inequality stated in Maurer and Pontil (2009,
Theorem 4), we get

$\displaystyle\mathop{\mathbb{E}}[{\bar{Z^{\prime}}}]-{\bar{Z^{\prime}}}$
$\displaystyle\leq\sqrt{\frac{2\widehat{\operatorname{Var}}(\bm{{Z^{\prime}}})\ln(4/\delta)}{n}}+\frac{7\ln(4/\delta)}{3(n-1)}$
$\displaystyle\Rightarrow\mathop{\mathbb{E}}[{\bar{Z}}]-{\bar{Z}}$
$\displaystyle\leq
L\sqrt{\frac{2\widehat{\operatorname{Var}}(\bm{Z})\ln(4/\delta)}{L^{2}n}}+\frac{7L\ln(4/\delta)}{3(n-1)}$
(C.3)
$\displaystyle=\sqrt{\frac{2\widehat{\operatorname{Var}}(\bm{Z})\ln(4/\delta)}{n}}+\frac{7L\ln(4/\delta)}{3(n-1)},$

where $\widehat{\operatorname{Var}}(\bm{Z})$ is defined to be:

$\displaystyle\widehat{\operatorname{Var}}(\bm{Z}):=\frac{1}{n(n-1)}\sum_{1\leq
i<j\leq n}(Z_{i}-Z_{j})^{2}.$

Observe that

$\displaystyle\widehat{\operatorname{Var}}(\bm{Z})$
$\displaystyle=\frac{1}{n(n-1)}\sum_{1\leq i<j\leq n}(Z_{i}-Z_{j})^{2}$
$\displaystyle=\frac{1}{n(n-1)}\cdot n\sum_{i=1}^{n}(Z_{i}-{\bar{Z}})^{2}$
$\displaystyle=\frac{1}{n-1}\sum_{i=1}^{n}(Z_{i}-{\bar{Z}})^{2}$
$\displaystyle=\frac{1}{n-1}\left(\sum_{i=1}^{n}Z_{i}^{2}-2{\bar{Z}}\sum_{i=1}^{n}Z_{i}+n{\bar{Z}}^{2}\right)$
$\displaystyle=\frac{1}{n-1}\left(\sum_{i=1}^{n}Z_{i}^{2}-2n{\bar{Z}}^{2}+n{\bar{Z}}^{2}\right)$
$\displaystyle=\frac{1}{n-1}\left(\sum_{i=1}^{n}Z_{i}^{2}-n{\bar{Z}}^{2}\right)$
$\displaystyle\leq\frac{1}{n-1}\left(nL^{2}-n{\bar{Z}}^{2}\right)$
$\displaystyle=\frac{n}{n-1}\left(L^{2}-{\bar{Z}}^{2}\right).$

Now plugging this back into (C.3):

$\displaystyle\mathop{\mathbb{E}}[{\bar{Z}}]-{\bar{Z}}$
$\displaystyle\leq\sqrt{\frac{2(L^{2}-{\bar{Z}}^{2})\ln(4/\delta)}{n-1}}+\frac{7L\ln(4/\delta)}{3(n-1)}$
$\displaystyle\leq\sqrt{\frac{2(L^{2}+{\bar{Z}}^{2})\ln(4/\delta)}{n-1}}+\frac{7L\ln(4/\delta)}{3(n-1)}$
$\displaystyle\leq{\bar{Z}}\sqrt{\frac{2\ln(4/\delta)}{n-1}}+L\sqrt{\frac{2\ln(4/\delta)}{n-1}}+\frac{7L\ln(4/\delta)}{3(n-1)},$

where the last inequality used $\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$ for any
$x,y>0$. ∎

######  Lemma 15.

Let $S_{n}=\\{(X_{i},Y_{i})\\}_{i=1}^{n}\sim({\cal X}\times{\cal Y})^{n}$ be a
_given_ sample. Let $\hat{h}:{\cal X}\to{\cal Y}$ be a predictor, and
$\ell:{\cal Y}\times{\cal Y}\to\mathbb{R}^{+}$ be a bounded loss function by
some $L>0$. Let $I\subseteq[n]$ be a random variable _sampled without
replacement_ from $[n]$. Then for any $\delta\in(0,1)$, with confidence at
least $1-\delta$:

$\displaystyle\left|\frac{1}{|I|}\sum_{i\in
I}\ell\left(\hat{h}(X_{i}),Y_{i}\right)-\widehat{R}(\hat{h};S_{n})\right|\leq\widehat{R}(\hat{h};S_{n})\sqrt{\frac{2\ln(2/\delta)}{|I|}}+L\sqrt{\frac{2\ln(2/\delta)}{|I|}}+\frac{2L\ln(2/\delta)}{3|I|}.$

###### Proof.

Let $\ell_{i}:=\ell(\hat{h}(X_{i}),Y_{i})$ for $i\in[n]$. Treating
$\ell_{1},\dots,\ell_{n}$ as a given finite population, and
$\\{\ell_{i}\\}_{i\in I}$ as a random sample drawn without replacement from
it, we can use a version of Bernstein’s inequality (Bardenet and Maillard,
2015),

$\displaystyle\operatorname{\mathbb{P}}\left(\left|\frac{1}{|I|}\sum_{i\in
I}\ell_{i}-\mu\right|\geq\varepsilon\right)\leq
2\exp\left(-\frac{|I|\varepsilon^{2}}{2\sigma^{2}+\frac{2L}{3}\varepsilon}\right)\qquad\varepsilon>0,$

where we have defined:

$\displaystyle\mu$
$\displaystyle:=\frac{1}{n}\sum_{i=1}^{n}\ell_{i}=\widehat{R}(\hat{h};S_{n})$
(population mean) $\displaystyle\sigma^{2}$
$\displaystyle:=\frac{1}{n}\sum_{i=1}^{n}(\ell_{i}-\mu)^{2}$
$\displaystyle\text{(population variance)}.$

For any $\delta\in(0,1)$, we get that with confidence at least $1-\delta$:

$\displaystyle\left|\frac{1}{|I|}\sum_{i\in
I}\ell_{i}-\mu\right|\leq\frac{2L}{3|I|}\ln(2/\delta)+\sqrt{\frac{2\sigma^{2}\ln(2/\delta)}{|I|}}.$

Now similarly to the analysis in the proof of Lemma 14, we see that

$\displaystyle\sigma^{2}\leq L^{2}+\widehat{R}^{2}(\hat{h};S_{n})$

using that and that $\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$ for any $x,y>0$ we get
the statement of the lemma. ∎

######  Theorem 16.

For any $k\in\mathbb{N}$, $b\in\mathbb{N}\cup\\{0\\}$, let $(\kappa,\psi)$ be
any semi-stable compression scheme of size at most $k$ using at most $b$ bits
of side-information. For any distribution ${\bar{\mu}}$ over ${\cal
X}\times{\cal Y}$, any $n\in\mathbb{N}$ with $n>4k+4$, and any
$\delta\in(0,1)$, for $S_{n}\sim{\bar{\mu}}^{n}$, with probability at least
$1-\delta$

$\displaystyle R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle\leq\widehat{R}(\psi(\kappa(S_{n}));S_{n})\left(5\sqrt{\frac{8\left(\ln(\frac{4}{\delta})+k\ln
4\right)}{n}}+4\sqrt{\frac{8b\ln 2}{n}}\right)$
$\displaystyle\quad+2L\sqrt{\frac{8\left(\ln(\frac{4}{\delta})+k\ln
4\right)}{n}}+\frac{(28+8L)\left(\ln(\frac{4}{\delta})+k\ln 4\right)}{3n}$
$\displaystyle\quad+L\sqrt{\frac{8b\ln 2}{n}}+\frac{28b\ln 2}{3n}.$

###### Proof.

Similarly to Hanneke and Kontorovich (2021), this proof follows similar
arguments as Theorem 13, except using Lemma 14 in place of Hoeffding’s
inequality in both places in the proof where such inequalities are used.

Let $\mathcal{I}_{n}$ and $T_{n}$ be as in the proof of Theorem 13, and let
$[n]=\\{1,\dots,n\\}$ for and $n\in\mathbb{N}$.

Let there be a sample
$S_{n}=\\{(X_{i},Y_{i})\\}_{i=1}^{n}\sim{\bar{\mu}}^{n}$. As in Theorem 13,
for any $I\in\mathcal{I}_{n}$ we have $S(I)=\\{(X_{i},Y_{i}):i\in
I\\}\subseteq S_{n}$, for any $I\in\mathcal{I}_{n}$, define
$\bar{I}:=[n]\setminus I$. Let $\sigma:[n]\to[n]$ be a uniform random
permutation of $[n]$, and for any $I=(i_{1},\dots,i_{\ell})\subseteq[n]$
define $\bm{\sigma}(I):=(\sigma(i_{1}),\dots,\sigma(i_{\ell}))$.

For any $I\subseteq[n]$ and any $\bm{b}\in\\{0,1\\}^{b}$, let
$\hat{h}_{I,\bm{b}}:=\psi\left(\kappa_{\mathsf{cs}}\left(S\left(I\right)\right),\bm{b}\right)$.
Now, since $S(\bar{I})$ is independent of $S(I)$, Lemma 14 (applied under the
conditional distribution given $S(I)$) and the law of total probability imply
that with probability $1-\frac{\delta}{2|\mathcal{I}_{n}|\cdot 2^{b}}$:

$\displaystyle
R\left(\hat{h}_{I,\bm{b}}\right)-\widehat{R}\left(\hat{h}_{I,\bm{b}};S\left(\bar{I}\right)\right)$
$\displaystyle\leq\widehat{R}\left(\hat{h}_{I,\bm{b}};S\left(\bar{I}\right)\right)\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{n-|I|-1}}$
$\displaystyle\quad+L\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{n-|I|-1}}+\frac{7\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{3(n-|I|-1)}.$

Applying this under the conditional distribution given $\sigma$, together with
the union bound and the law of total probability, we have that with
probability at least $1-\frac{\delta}{2}$, every $I\in\mathcal{I}_{n}$ and
every $\bm{b}\in\\{0,1\\}^{b}$ has

$\displaystyle
R\left(\hat{h}_{\bm{\sigma}^{-1}\left(I\right),\bm{b}}\right)-\widehat{R}\left(\hat{h}_{\bm{\sigma}^{-1}\left(I\right),\bm{b}};S\left(\overline{\bm{\sigma}^{-1}\left(I\right)}\right)\right)$
$\displaystyle\leq\widehat{R}\left(\hat{h}_{\bm{\sigma}^{-1}\left(I\right),\bm{b}};S\left(\overline{\bm{\sigma}^{-1}\left(I\right)}\right)\right)\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{n-|I|-1}}$
$\displaystyle\quad+L\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{n-|I|-1}}+\frac{7\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{3(n-|I|-1)}.$

In particular, let $\bm{i}^{*}$ be the indices such that

$\displaystyle\kappa_{\mathsf{cs}}(S_{n})=\left\\{(X_{i},Y_{i})\in
S_{n}:i\in\bm{i}^{*}\right\\}=S_{n}(\bm{i}^{*})$

Now, by property (ii) of $\mathcal{I}_{n}$ there must exist
$I^{*}\in\mathcal{I}_{n}$ such that

$\displaystyle\bm{\sigma}(\bm{i}^{*})\subseteq I^{*},$

which means:

$\displaystyle\Rightarrow\quad$
$\displaystyle\bm{i}^{*}\subseteq\bm{\sigma}^{-1}(I^{*})$
$\displaystyle\Rightarrow\quad$
$\displaystyle\kappa_{\mathsf{cs}}(S_{n})=S_{n}(\bm{i}^{*})\subseteq
S_{n}(\bm{\sigma}^{-1}(I^{*})).$

Due to the semi-stability property of $(\kappa,\psi)$ and since
$S_{n}(\bm{\sigma}^{-1}(I^{*}))\subseteq S_{n}$, this implies

$\displaystyle\Rightarrow\psi(\kappa_{\mathsf{cs}}(S_{n}(\bm{\sigma}^{-1}(I^{*}))),\kappa_{\mathsf{si}}(S_{n}))=\psi(\kappa_{\mathsf{cs}}(S_{n}),\kappa_{\mathsf{si}}(S_{n}))=\psi(\kappa\left(S_{n}\right)).$

Thus, on the above event of probability at least $1-\frac{\delta}{2}$ we can
get for $I=I^{*}$ and $\bm{b}=\kappa_{\mathsf{si}}(S_{n})$,

$\displaystyle
R\left(\psi(\kappa\left(S_{n}\right))\right)-\widehat{R}\left(\psi(\kappa\left(S_{n}\right));S\left(\overline{\bm{\sigma}^{-1}\left(I^{*}\right)}\right)\right)$
$\displaystyle\leq\widehat{R}\left(\psi(\kappa\left(S_{n}\right));S\left(\overline{\bm{\sigma}^{-1}\left(I^{*}\right)}\right)\right)\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{n-|I^{*}|-1}}$
$\displaystyle\quad+L\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{n-|I^{*}|-1}}+\frac{7\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{3(n-|I^{*}|-1)}.$

Furthermore, by property (i) of $I_{n}$ we have that $n-|I^{*}|\geq T_{n}$,
and that
$\widehat{R}\left(\psi(\kappa\left(S_{n}\right));S\left(\overline{\bm{\sigma}^{-1}\left(I^{*}\right)}\right)\right)\leq\frac{n}{T_{n}}\widehat{R}\left(\psi(\kappa\left(S_{n}\right));S_{n}\right)$,
so

$\displaystyle
R\left(\psi(\kappa\left(S_{n}\right))\right)-\widehat{R}\left(\psi(\kappa\left(S_{n}\right));S\left(\overline{\bm{\sigma}^{-1}\left(I^{*}\right)}\right)\right)$
$\displaystyle\leq\frac{n}{T_{n}}\widehat{R}\left(\psi(\kappa\left(S_{n}\right));S_{n}\right)\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{T_{n}-1}}$ (C.4)
$\displaystyle\quad+L\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{T_{n}-1}}+\frac{7\ln(\frac{4|\mathcal{I}_{n}|\cdot
2^{b}}{\delta})}{3(T_{n}-1)}.$

Now, given $S_{n}$, we define
$\ell_{i}:=\ell(\psi(\kappa(S_{n}))(X_{i}),Y_{i})$ for $i\in[n]$. Now for any
$I\in\mathcal{I}_{n}$, under the conditional distribution given $S_{n}$ we
apply Lemma 15 and see that with probability at least
$1-\frac{\delta}{2|\mathcal{I}_{n}|}$:

$\displaystyle\left|\frac{1}{n-|I|}\sum_{i\in\overline{\bm{\sigma}^{-1}\left(I\right)}}\ell_{i}-\widehat{R}(\psi(\kappa(S_{n}));S_{n})\right|$
$\displaystyle\leq\widehat{R}(\psi(\kappa(S_{n}));S_{n})\sqrt{\frac{2\ln(4|\mathcal{I}_{n}|/\delta)}{n-|I|}}$
$\displaystyle\quad+L\sqrt{\frac{2\ln(4|\mathcal{I}_{n}|/\delta)}{n-|I|}}+\frac{2L\ln(4|\mathcal{I}_{n}|/\delta)}{3(n-|I|)}.$

By the union bound, this holds simultaneously for all $I\in\mathcal{I}_{n}$
with probability at least $1-\frac{\delta}{2}$. In particular, taking
$I=I^{*}$, and recalling that $n-|I^{*}|\geq T_{n}$, on this event we have
that

$\displaystyle\left|\widehat{R}(\psi(\kappa(S_{n}));S(\overline{\bm{\sigma}^{-1}\left(I^{*}\right)}))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})\right|$
$\displaystyle\leq\widehat{R}(\psi(\kappa(S_{n}));S_{n})\sqrt{\frac{2\ln(4|\mathcal{I}_{n}|/\delta)}{T_{n}}}$
(C.5)
$\displaystyle\quad+L\sqrt{\frac{2\ln(4|\mathcal{I}_{n}|/\delta)}{T_{n}}}+\frac{2L\ln(4|\mathcal{I}_{n}|/\delta)}{3T_{n}}.$

By the union bound, the two events represented by (C.4) and (C.5) hold
simultaneously with probability at least $1-\delta$, in which case together we
get:

$\displaystyle R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle\leq
R\left(\psi(\kappa\left(S_{n}\right))\right)-\widehat{R}\left(\psi(\kappa\left(S_{n}\right));S\left(\overline{\bm{\sigma}^{-1}\left(I^{*}\right)}\right)\right)$
$\displaystyle\quad+\left|\widehat{R}(\psi(\kappa(S_{n}));S(\overline{\bm{\sigma}^{-1}\left(I^{*}\right)}))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})\right|$
$\displaystyle\leq\widehat{R}(\psi(\kappa(S_{n}));S_{n})\left(\left(1+\frac{n}{T_{n}}\right)\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|}{\delta})}{T_{n}-1}}+\frac{n}{T_{n}}\sqrt{\frac{2b\ln
2}{T_{n}-1}}\right)$
$\displaystyle\quad+2L\sqrt{\frac{2\ln(\frac{4|\mathcal{I}_{n}|}{\delta})}{T_{n}-1}}+\frac{(7+2L)\ln(\frac{4|\mathcal{I}_{n}|}{\delta})}{3(T_{n}-1)}+L\sqrt{\frac{2b\ln
2}{T_{n}-1}}+\frac{7b\ln 2}{3(T_{n}-1)}.$

The theorem now follows from plugging the aforementioned family
$\mathcal{I}_{n}$ from Bousquet et al. (2020), with
$|\mathcal{I}_{n}|=\binom{2k}{k}<4^{k}$ and
$T_{n}=k\left\lfloor\frac{n}{2k}\right\rfloor>\frac{n-2k}{2}$ — with the
modification thatsince $n>4k+4$ we have $\frac{n-2k}{2}-1>\frac{n}{4}$,
meaning $T_{n}>T_{n}-1>\frac{n}{4}$:

$\displaystyle R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle\leq\widehat{R}(\psi(\kappa(S_{n}));S_{n})\left(5\sqrt{\frac{8\left(\ln(\frac{4}{\delta})+k\ln
4\right)}{n}}+4\sqrt{\frac{8b\ln 2}{n}}\right)$
$\displaystyle\quad+2L\sqrt{\frac{8\left(\ln(\frac{4}{\delta})+k\ln
4\right)}{n}}+\frac{(28+8L)\left(\ln(\frac{4}{\delta})+k\ln 4\right)}{3n}$
$\displaystyle\quad+L\sqrt{\frac{8b\ln 2}{n}}+\frac{28b\ln 2}{3n}.$

∎

####  C.3.3 Semi-stable compression scheme of bounded sample-dependent size

######  Theorem 17.

Let $(\kappa,\psi)$ be any semi-stable compression scheme with side-
information. For any distribution ${\bar{\mu}}$ over ${\cal X}\times{\cal Y}$,
any $n\in\mathbb{N}$, and any $\delta\in(0,1)$, for
$S_{n}\sim{\bar{\mu}}^{n}$, with probability at least $1-\delta$, if
$|\kappa_{\mathsf{cs}}(S_{n})|<\frac{n}{4}-1$ then

$\displaystyle R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle\leq\widehat{R}(\psi(\kappa(S_{n}));S_{n})\left(5\sqrt{\frac{8T_{\kappa,S_{n}}}{n}}+4\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}\right)$
$\displaystyle\quad+2L\sqrt{\frac{8T_{\kappa,S_{n}}}{n}}+\frac{(28+8L)T_{\kappa,S_{n}}}{3n}$
$\displaystyle\quad+L\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}+\frac{28|\kappa_{\mathsf{si}}(S_{n})|\ln 2}{3n},$

where

$\displaystyle
T_{\kappa,S_{n}}:=\ln\left(\frac{4(|\kappa_{\mathsf{cs}}(S_{n})|+1)(|\kappa_{\mathsf{cs}}(S_{n})|+2)(|\kappa_{\mathsf{si}}(S_{n})|+1)(|\kappa_{\mathsf{si}}(S_{n})|+2)}{\delta}\right)+|\kappa_{\mathsf{cs}}(S_{n})|\ln
4.$

###### Proof.

Let $(\kappa,\psi)$ be any semi-stable compression scheme with side-
information. Now for each $k\in\mathbb{N}\cup\\{0\\}$ and
$b\in\mathbb{N}\cup\\{0\\}$, let $(\kappa_{k,b},\psi)$ be a compression scheme
such that, for any $S_{n}\sim\mu^{n}$, if $|\kappa_{\mathsf{cs}}(S)|\leq k$
and $|\kappa_{\mathsf{si}}(S)|\leq b$, then $\kappa_{k,b}(S)=\kappa(S)$, and
otherwise $(\kappa_{\mathsf{cs}})_{k,b}(S_{n})=\emptyset$ and
$(\kappa_{\mathsf{si}})_{k,b}(S_{n})=\emptyset$. In particular, note that
$|(\kappa_{\mathsf{cs}})_{k,b}(S)|\leq k$ and
$|(\kappa_{\mathsf{si}})_{k,b}(S)|\leq b$ always. Thus, for each $k$ and $b$,
Theorem 16 implies that for any $n>4k+4$

$\displaystyle\left|R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})\right|$
$\displaystyle\leq\widehat{R}(\psi(\kappa(S_{n}));S_{n})\left(5\sqrt{\frac{8t_{k,b}}{n}}+4\sqrt{\frac{8b\ln
2}{n}}\right)$
$\displaystyle\quad+2L\sqrt{\frac{8t_{k,b}}{n}}+\frac{(28+8L)t_{k,b}}{3n}$
$\displaystyle\quad+L\sqrt{\frac{8b\ln 2}{n}}+\frac{28b\ln 2}{3n}$

holds with probability at least $1-\frac{\delta}{(k+1)(k+2)(b+1)(b+2)}$, where

$\displaystyle
t_{k,b}:=\ln\left(\frac{4(k+1)(k+2)(b+1)(b+2)}{\delta}\right)+k\ln 4.$

By the union bound, the above claim holds simultaneously for all
$k\in\mathbb{N}\cup\\{0\\}$ and $b\in\mathbb{N}\cup\\{0\\}$ with probability
at least $1-\sum_{k,b}\frac{\delta}{(k+1)(k+2)(b+1)(b+2)}=1-\delta$. Finally,
note that there necessarily exists some $k\in\mathbb{N}\cup\\{0\\}$ and
$b\in\mathbb{N}\cup\\{0\\}$ for which $|\kappa_{\mathsf{cs}}(S)|=k$ and
$|\kappa_{\mathsf{si}}(S)|=b$, in which case
$\psi(\kappa(S))=\psi(\kappa_{k,b}(S))$ for these $k$ and $b$. This completes
the proof. ∎

####  C.3.4 Semi-stable compression scheme of any sample-dependent size

######  Theorem.

2. Suppose that ${\cal X}$ is an instance space and ${\cal Y}$ a label space with a loss function $\ell:{\cal Y}\times{\cal Y}\to[0,L]$, and $(\kappa,\psi)$ is semi-stable compression scheme. For any distribution ${\bar{\mu}}$ over ${\cal X}\times{\cal Y}$, any $n\in\mathbb{N}$, and any $\delta\in(0,1)$, for $S_{n}\sim{\bar{\mu}}^{n}$ we have that

$\displaystyle R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle\leq\left(20\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+20\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+15\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}\right)\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle+(6L+18)\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+8L\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+(2L+12)\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}$
$\displaystyle+7L\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+(3L+10)\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6L\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}$

holds with probability at least $1-\delta$.

###### Proof.

Let $(\kappa,\psi)$ be any semi-stable compression scheme with side-
information. We will observe the RHS of Theorem 17. Since for any
$x\geq\sqrt{3}$ $\ln(x^{2})<\frac{x}{2}$, firstly we have:

$\displaystyle T_{\kappa,S_{n}}$
$\displaystyle:=\ln\left(\frac{4(|\kappa_{\mathsf{cs}}(S_{n})|+1)(|\kappa_{\mathsf{cs}}(S_{n})|+2)(|\kappa_{\mathsf{si}}(S_{n})|+1)(|\kappa_{\mathsf{si}}(S_{n})|+2)}{\delta}\right)+|\kappa_{\mathsf{cs}}(S_{n})|\ln
4$ $\displaystyle\leq\ln(\frac{4}{\delta})+|\kappa_{\mathsf{cs}}(S_{n})|\ln
4+\frac{|\kappa_{\mathsf{cs}}(S_{n})|+2}{2}+\frac{|\kappa_{\mathsf{si}}(S_{n})|+2}{2}$
$\displaystyle=|\kappa_{\mathsf{cs}}(S_{n})|\ln(4\sqrt{e})+\frac{1}{2}|\kappa_{\mathsf{si}}(S_{n})|+\ln(\frac{4e^{2}}{\delta})$

Next, let us abbreviate the right-hand side of the bound in Theorem 17:

$\displaystyle\widehat{R}(\psi(\kappa(S_{n}));S_{n})\left(5\sqrt{\frac{8T_{\kappa,S_{n}}}{n}}+4\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}\right)+2L\sqrt{\frac{8T_{\kappa,S_{n}}}{n}}+\frac{(28+8L)T_{\kappa,S_{n}}}{3n}$
$\displaystyle+L\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}+\frac{28|\kappa_{\mathsf{si}}(S_{n})|\ln 2}{3n}$
$\displaystyle\quad:=A_{\mathrm{I}}\widehat{R}(\psi(\kappa(S_{n}));S_{n})+A_{\mathrm{II}},$
$\displaystyle A_{\mathrm{I}}$
$\displaystyle:=5\sqrt{\frac{8T_{\kappa,S_{n}}}{n}}+4\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}$ $\displaystyle\leq
5\sqrt{\frac{8(|\kappa_{\mathsf{cs}}(S_{n})|\ln(4\sqrt{e})+\frac{1}{2}|\kappa_{\mathsf{si}}(S_{n})|+\ln(\frac{4e^{2}}{\delta}))}{n}}+4\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}$ $\displaystyle\leq
5\sqrt{\frac{8|\kappa_{\mathsf{cs}}(S_{n})|\ln(4\sqrt{e})}{n}}+5\sqrt{\frac{4|\kappa_{\mathsf{si}}(S_{n})|}{n}}+5\sqrt{\frac{8\ln(\frac{4e^{2}}{\delta})}{n}}+4\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}$
$\displaystyle=5\sqrt{8\ln(4\sqrt{e})}\cdot\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+(10+4\sqrt{8\ln
2})\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+5\sqrt{8}\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}$
$\displaystyle\leq
20\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+20\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+15\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}$
$\displaystyle:=B_{\mathrm{I}},$ $\displaystyle A_{\mathrm{II}}$
$\displaystyle:=2L\sqrt{\frac{8T_{\kappa,S_{n}}}{n}}+\frac{(28+8L)T_{\kappa,S_{n}}}{3n}+L\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}+\frac{28|\kappa_{\mathsf{si}}(S_{n})|\ln 2}{3n}$ $\displaystyle\leq
2L\sqrt{\frac{8\left(|\kappa_{\mathsf{cs}}(S_{n})|\ln(4\sqrt{e})+\frac{1}{2}|\kappa_{\mathsf{si}}(S_{n})|+\ln(\frac{4e^{2}}{\delta})\right)}{n}}$
$\displaystyle\quad+\frac{(28+8L)\left(|\kappa_{\mathsf{cs}}(S_{n})|\ln(4\sqrt{e})+\frac{1}{2}|\kappa_{\mathsf{si}}(S_{n})|+\ln(\frac{4e^{2}}{\delta})\right)}{3n}$
$\displaystyle\quad+L\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}+\frac{28|\kappa_{\mathsf{si}}(S_{n})|\ln 2}{3n}$
$\displaystyle\quad\leq
2L\sqrt{\frac{8|\kappa_{\mathsf{cs}}(S_{n})|\ln(4\sqrt{e})}{n}}+2L\sqrt{\frac{4|\kappa_{\mathsf{si}}(S_{n})|}{n}}+2L\sqrt{\frac{8\ln(\frac{4e^{2}}{\delta})}{n}}$
$\displaystyle\quad+\frac{(28+8L)\left(|\kappa_{\mathsf{cs}}(S_{n})|\ln(4\sqrt{e})+\frac{1}{2}|\kappa_{\mathsf{si}}(S_{n})|+\ln(\frac{4e^{2}}{\delta})\right)}{3n}$
$\displaystyle\quad+L\sqrt{\frac{8|\kappa_{\mathsf{si}}(S_{n})|\ln
2}{n}}+\frac{28|\kappa_{\mathsf{si}}(S_{n})|\ln 2}{3n}$
$\displaystyle=\frac{(28+8L)\ln(4\sqrt{e})}{3}\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+2L\sqrt{8\ln(4\sqrt{e})}\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+$
$\displaystyle\quad+\frac{14+4L+28\ln
2}{3}\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+(4+\sqrt{8\ln
2})L\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}$
$\displaystyle\quad+\frac{28+8L}{3}\frac{\ln(\frac{4e^{2}}{\delta})}{n}+2\sqrt{8}L\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}$
$\displaystyle\leq(6L+18)\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+8L\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+$
$\displaystyle\quad+(2L+12)\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+7L\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}$
$\displaystyle\quad+(3L+10)\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6L\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}$
$\displaystyle=\left(6\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+8\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+2\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+7\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+3\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}\right)L$
$\displaystyle\quad+18\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+12\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+10\frac{\ln(\frac{4e^{2}}{\delta})}{n}$
$\displaystyle:=B_{\mathrm{II}}.$

Let ${\bar{\mu}}$ be any distribution over ${\cal X}\times{\cal Y}$, and let
$n\in\mathbb{N}$, and $\delta\in(0,1)$. From Theorem 17 we know that for
$S_{n}\sim{\bar{\mu}}^{n}$, with probability at least $1-\delta$, if
$|\kappa_{\mathsf{cs}}(S_{n})|<\frac{n}{4}-1$ then

$\displaystyle R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n})$
$\displaystyle\leq
A_{\mathrm{I}}\widehat{R}(\psi(\kappa(S_{n}));S_{n})+A_{\mathrm{II}}$ (C.6)
$\displaystyle\leq
B_{\mathrm{I}}\widehat{R}(\psi(\kappa(S_{n}));S_{n})+B_{\mathrm{II}}.$

Now, for $B_{\mathrm{I}}$ we note that even if
$|\kappa_{\mathsf{cs}}(S_{n})|\geq\frac{n}{4}-1$ we have:

$\displaystyle B_{\mathrm{I}}$
$\displaystyle:=20\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+20\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+15\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}$
$\displaystyle\geq 0\geq-1$

and for $B_{\mathrm{II}}$, we observe firstly that if $n\leq 4$:

$\displaystyle B_{\mathrm{II}}$
$\displaystyle:=\left(6\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+8\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+2\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+7\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+3\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}\right)L$
$\displaystyle\quad+18\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+12\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+10\frac{\ln(\frac{4e^{2}}{\delta})}{n}$
$\displaystyle\geq\left(\frac{3}{2}+8\sqrt{\frac{1}{4}}+2\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+7\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+3\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}\right)L$
$\displaystyle\quad+\frac{9}{2}+12\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+10\frac{\ln(\frac{4e^{2}}{\delta})}{n}$
$\displaystyle\geq L$

and now even if $n\geq 5$ and
$|\kappa_{\mathsf{cs}}(S_{n})|\geq\frac{n}{4}-1$:

$\displaystyle B_{\mathrm{II}}$
$\displaystyle:=\left(6\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+8\sqrt{\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}}+2\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+7\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+3\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}\right)L$
$\displaystyle\quad+18\frac{|\kappa_{\mathsf{cs}}(S_{n})|}{n}+12\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+10\frac{\ln(\frac{4e^{2}}{\delta})}{n}$
$\displaystyle\geq\left(6\left(\frac{1}{4}-\frac{1}{n}\right)+8\sqrt{\frac{1}{4}-\frac{1}{n}}+2\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+7\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+3\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}\right)L$
$\displaystyle\quad+18\left(\frac{1}{4}-\frac{1}{n}\right)+12\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+10\frac{\ln(\frac{4e^{2}}{\delta})}{n}$
$\displaystyle\geq\left(\frac{6}{20}+8\sqrt{\frac{1}{20}}+2\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+7\sqrt{\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}}+3\frac{\ln(\frac{4e^{2}}{\delta})}{n}+6\sqrt{\frac{\ln(\frac{4e^{2}}{\delta})}{n}}\right)L$
$\displaystyle\quad+\frac{18}{20}+12\frac{|\kappa_{\mathsf{si}}(S_{n})|}{n}+10\frac{\ln(\frac{4e^{2}}{\delta})}{n}$
$\displaystyle\geq L.$

Thus, even if $|\kappa_{\mathsf{cs}}(S_{n})|\geq\frac{n}{4}-1$, we have

$\displaystyle
B_{\mathrm{I}}\widehat{R}(\psi(\kappa(S_{n}));S_{n})+B_{\mathrm{II}}$
$\displaystyle\geq L-\widehat{R}(\psi(\kappa(S_{n}));S_{n})$ (C.7)
$\displaystyle\geq
R(\psi(\kappa(S_{n})))-\widehat{R}(\psi(\kappa(S_{n}));S_{n}).$

Finally, the theorem follows from (C.6) and (C.7). ∎

##  Appendix D Diameter-truncating BIE ${\cal Y}$

Recall the bounded-in-expectation (BIE) condition:
$\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty$ for some
$y_{0}\in{\cal Y}$. Under BIE, the trivial $f_{0}(x)\equiv y_{0}$ achieves
$R(f_{0})<\infty$, and a fortiori, $R^{*}=\inf_{f}R(f)<\infty$.

######  Lemma 18.

If there exists some $y_{0}\in{\cal Y}$ for which
$\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty$, then this
holds for all $y\in{\cal Y}$.

###### Proof.

Suppose that $\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty$
for some $y_{0}\in{\cal Y}$. Then, by the triangle inequality, for any other
$y^{\prime}\in{\cal Y}$, we have

$\displaystyle\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y^{\prime},Y)\leq\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}[\ell(y^{\prime},y_{0})+\ell(y_{0},Y)]=\ell(y^{\prime},y_{0})+\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty.$

∎

Thus, the choice of $y_{0}\in{\cal Y}$ is immaterial; let us fix one such
element once and for all. For any sequence $L_{n}\uparrow\infty$, let
$\llbracket{\cal Y}\rrbracket_{n}:=B(y_{0},L_{n})$ denote the
“$L_{n}$-truncated” space.

We observe that

$\displaystyle f^{*}(x):=\mathop{\mathrm{argmin}}_{y^{\prime}\in{\cal
Y}}\mathop{\mathbb{E}}[\ell(y^{\prime},Y)\,|\,X=x]$

(where ties in ${\cal Y}$ are broken lexicographically) achieves
$R(f^{*})=R^{*}$, since it is a pointwise minimizer of the non-negative risk
integrand. Let us also define a truncated version:

$\displaystyle
f_{n}^{*}(x):=\mathop{\mathrm{argmin}}_{\hat{y}\in\llbracket{\cal
Y}\rrbracket_{n}}\mathop{\mathbb{E}}[\ell(\hat{y},Y)\,|\,X=x].$

Since $y_{0}\in\llbracket{\cal Y}\rrbracket_{n}$, we have that

$\displaystyle
g_{n}(x):=\mathop{\mathbb{E}}[\ell(f_{n}^{*}(x),Y|X=x)]\leq\mathop{\mathbb{E}}[\ell(y_{0},Y|X=x)]=:h(x).$

While one or both of $g_{n},h$ may be infinite for some $x$, BIE implies that
$h$ is integrable. Next, we claim that

$\displaystyle\lim_{n\to\infty}g_{n}(x)=g(x):=\mathop{\mathbb{E}}[\ell(f^{*}(x),Y|X=x)],\qquad
x\in{\cal X}.$

Indeed, this follows from a stronger property: there is a function $N:{\cal
X}\to\mathbb{N}$ such that $f_{n}^{*}(x)=f^{*}(x)$ for all $x$ and all $n\geq
N(x)$; this is immediate by construction and because $L_{n}\uparrow\infty$.
Applying Lebesgue’s Dominated Convergence Theorem to the sequence $g_{n}\leq
h$ yields

######  Theorem 19.

If ${\cal Y}$ is BIE, $f^{*}$ is a Bayes-optimal predictor and $f^{*}_{n}$ is
its truncation as defined above, then

$\displaystyle\lim_{n\to\infty}R(f_{n}^{*})=R(f^{*})=R^{*}.$

##  Appendix E Discretizing separable $({\cal Y},\ell)$

For any separable $({\cal Y},\ell)$ and $\varepsilon>0$, any $\varepsilon$-net
${\cal Y}_{\varepsilon}\subseteq{\cal Y}$ is always countable. Define
$\pi_{\varepsilon}(y)$ as the closest element to $y$ in ${\cal
Y}_{\varepsilon}$, breaking ties lexicographically. Then the Voronoi cell
$V(y)$ about each $y\in{\cal Y}_{\varepsilon}$ is given by
$V(y)=\left\\{y^{\prime}\in{\cal Y}:\pi_{\varepsilon}(y^{\prime})=y\right\\}$.
Any probability measure ${\bar{\mu}}$ on the product Borel $\sigma$-algebra on
${\cal X}\times{\cal Y}$ induces the product measure
${\bar{\mu}}_{\varepsilon}$ on ${\cal X}\times{\cal Y}_{\varepsilon}$ as
follows. By Pollard (2002, Appendix F, Theorem 1), the measure ${\bar{\mu}}$
admits the disintegration intro $\mu^{\cal Y}\otimes\Lambda$, where $\mu^{\cal
Y}$ is the ${\cal Y}$-marginal of ${\bar{\mu}}$ and
$\Lambda(y,E)=\operatorname{\mathbb{P}}_{(X,Y)\sim{\bar{\mu}}}(X\in
E\,|\,Y=y)$ is the conditional kernel. Define the measure $\mu^{\cal
Y}_{\varepsilon}$ on ${\cal Y}_{\varepsilon}$ by $\mu^{\cal
Y}_{\varepsilon}(y)=\mu^{\cal Y}(V(y))$ and the product measure
${\bar{\mu}}_{\varepsilon}=\mu^{\cal Y}_{\varepsilon}\otimes\Lambda$ on ${\cal
X}\times{\cal Y}_{\varepsilon}$. Let $R^{*}$, $R^{*}_{\varepsilon}$ be the
Bayes-optimal risk under ${\bar{\mu}}$ and ${\bar{\mu}}_{\varepsilon}$,
respectively.

######  Theorem 20.

$\displaystyle\lim_{\varepsilon\to 0}R^{*}_{\varepsilon}=R^{*}.$

###### Proof.

Appealing to a standard truncation argument, we assume without loss of
generality that $R^{*}<\infty$. The product metric $\rho\oplus\ell$ on ${\cal
Z}={\cal X}\times{\cal Y}$, given by
$\rho\oplus\ell((x,y),(x^{\prime},y^{\prime}))=\rho(x,x^{\prime})+\ell(y,y^{\prime})$
renders $({\cal Z},\rho\oplus\ell,{\bar{\mu}})$ and $({\cal
Z}_{\varepsilon},\rho\oplus\ell,{\bar{\mu}}_{\varepsilon})$ metric probability
spaces. Let $h^{*}:{\cal X}\to{\cal Y}$ be the Bayes-optimal predictor for
$({\cal Z},\rho\oplus\ell,{\bar{\mu}})$, and define $f^{*}:{\cal X}\times{\cal
Y}\to\mathbb{R}$ by $f^{*}(x,y)=\ell(h^{*}(x),y)$. Then

$\displaystyle R^{*}=\int_{{\cal X}\times{\cal
Y}}f^{*}(x,y)\mathrm{d}{\bar{\mu}}(x,y).$

Since we assumed $R^{*}<\infty$, we have that $f^{*}\in L_{1}({\bar{\mu}})$
and hence, by Hanneke et al. (2021, Lemma A.1) $f^{*}$ may be approximated in
$L_{1}$ by Lipschitz functions: for all $\eta>0$, there is a $\Delta<\infty$
and a $\Delta$-Lipschitz $\tilde{f}:{\cal X}\times{\cal Y}\to\mathbb{R}$ such
that $\int_{{\cal X}\times{\cal
Y}}|f^{*}(x,y)-\tilde{f}(x,y)|\mathrm{d}{\bar{\mu}}(x,y)<\eta$. Thus, there is
no loss of generality in assuming $f^{*}$ to be $\Delta$-Lipschitz:

$\displaystyle|f^{*}(x,y)-f^{*}(x^{\prime},y^{\prime})|\leq\Delta(\rho(x,x^{\prime})+\ell(y,y^{\prime})).$

Define the natural projection of $h\in{\cal Y}^{\cal X}$ onto
$h_{\varepsilon}\in{\cal Y}_{\varepsilon}$, via
$h_{\varepsilon}(x):=\pi_{\varepsilon}(h(x))$. Then by the Lipschitz property,
$|R(h_{\varepsilon})-R(h)|\leq\Delta\varepsilon$. ∎