11institutetext: 1Amazon Alexa, 300 Pine St., Seattle, Washington, USA 98101
11email<EMAIL_ADDRESS>
# An Algorithm for Learning Smaller Representations of Models With Scarce Data

Adrian de Wynter 11

###### Abstract

111This paper has not been fully peer-reviewed.

We present a greedy algorithm for solving binary classification problems in
situations where the dataset is either too small or not fully representative
of the problem being solved, and obtaining more data is not possible. This
algorithm is of particular interest when training small models that have
trouble generalizing. It relies on a trained model with loose accuracy
constraints, an iterative hyperparameter pruning procedure, and a function
used to generate new data. Analysis on correctness and runtime complexity
under ideal conditions and an extension to deep neural networks is provided.
In the former case we obtain an asymptotic bound of
$O\left(\lvert\Theta\rvert^{2}\left(\log{\lvert\Theta\rvert}+\lvert\theta\rvert^{2}+T_{f}\left(\lvert
D\rvert\right)\right)+\bar{S}\lvert\Theta\rvert\lvert E\rvert\right)$, where
$\lvert\Theta\rvert$ is the cardinality of the set of hyperparameters $\theta$
to be searched; $\lvert E\rvert$ and $\lvert D\rvert$ are the sizes of the
evaluation and training datasets, respectively; $\bar{S}$ and $\bar{f}$ are
the inference times for the trained model and the candidate model; and
$T_{f}({\lvert D\rvert})$ is a polynomial on $\lvert D\rvert$ and $\bar{f}$.
Under these conditions, this algorithm returns a solution that is $1\leq r\leq
2(1-{2^{-\lvert\Theta\rvert}})$ times better than simply enumerating and
training with any $\theta\in\Theta$. As part of our analysis of the generating
function we also prove that, under certain assumptions, if an open cover of
$D$ has the same homology as the manifold where the support of the underlying
probability distribution lies, then $D$ is learnable, and viceversa.

###### Keywords:

data augmentation semi-supervised learning

##  1 Introduction

The goal of most machine learning systems is to, given a sample of an unknown
probability distribution, fit a model that generalizes well to other samples
of the same distribution. It is often assumed that said sample is fully
representative of the unknown, or _underlying_ , probability distribution
being modeled, as well as being independent and identically distributed
Shalev-Shwartz and Ben-David (2014). It occurs in many natural problems that
at least one part of said assumption does not hold. This could be by either
noisy or insufficient sampling of the underlying function, or an ill-posed
problem, where the features of the data do not represent the relevant
characteristics of the phenomenon being described Hampel (1998); Dundar et al.
(2007). Some systems, such as deep neural networks, appear to be remarkably
resilient to this situation. Often, this is due to the fact that
overparametrized models are easier to train Livni et al. (2014). This issue
becomes more self-evident in situations where the presence of outliers may
harm the overall experience, such as commercial voice assistants; as well as
when training small, shallow models, where exposure to large amounts of data
is critical for proper generalizability Livni et al. (2014); Hanneke (2016);
Kawaguchi et al. (2017).

###  1.1 Contributions

We present an algorithm, which we dub Agora,222One of Plato’s Dialogues–
_Timaeus_ –involves a conversation between the eponymous character and
Socrates, about the nature of the world and how it came into being. It fits
well with the nature of our algorithm, and with the goal of machine learning.
for solving binary classification problems in situations when the data does
not fully characterize the underlying probability distribution, chiefly having
in mind the creation of smaller, non-linear models for these tasks whenever we
are unable to further sample the underlying probability distribution.

Our algorithm works by training a model (_Timaeus_), through the output of a
trained, but relatively low-performing, model (_Socrates_), along with a
function to generate new samples (the $\tau$-_function_). The only condition
imposed to Agora, outside of the characterization of the $\tau$-function, is
that the evaluation set must be representative of the underlying distribution
being learned. Similar constraints are not required for the training set.

We provide statements around the correctness and time bounds of this approach
under ideal conditions by leveraging ideas from the field of topological data
analysis. In particular, when the underlying probability distribution
$\mathcal{P}$ is describable as a Riemannian manifold and the size of the data
is large enough to be representative of $\mathcal{P}$; if Timaeus is unable to
“forget” a correctly labeled point, then Agora’s solution is $1\leq r\leq
2\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right)$ times better, when compared
to an enumeration of trained models with hyperparameters from $\Theta$.

Assuming a polynomial-time training algorithm, Agora converges in at most

$O\left(\lvert\Theta\rvert^{2}\left(\log{\lvert\Theta\rvert}+\lvert\theta\rvert^{2}+T_{f}\left(\lvert
D\rvert+\frac{\lvert
E\rvert}{2^{\lvert\Theta\rvert-1}}\right)\right)+\bar{S}\lvert\Theta\rvert\lvert
E\rvert\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right)\right),$ (1)

steps, where $\lvert\Theta\rvert$ is the cardinality of the set of
hyperparameters $\theta$ to be searched; $\lvert E\rvert$ and $\lvert D\rvert$
are the sizes of the evaluation and training datasets, respectively; $\bar{S}$
is the steps required to perform inference on Socrates; and $T_{f}(\lvert
D\rvert)$ is the runtime of the training algorithm–assumed to be a polynomial
on $\lvert D\rvert$ and on the inference time for Timaeus, $\bar{f}$.

We further relax the–admittedly strong–assumption that there exists such a
polynomial-time training algorithm, and consider the case where it is a neural
network with a loss function that is $L$-Lipschitz, bounded from below and
with stochastic gradients bounded by some $G$. We prove that whenever the
learning rate $\eta$, batch size $\lvert B\rvert$, and random state $s$ is
considered as part of the hyperparameter search, then the runtime of Agora is
given by

$O\left(\lvert\Theta\rvert^{2}\left(\log{\lvert\Theta\rvert}+\lvert\theta\rvert^{2}+\bar{f}\left(\lvert
E\rvert+\frac{\lvert
B\rvert}{(LG\zeta)^{2/3}}\right)\right)+\bar{S}\lvert\Theta\rvert\lvert
E\rvert\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right)\right)$ (2)

steps, where $B\subset D$, with $\lvert
B\rvert=\underset{\theta\in\Theta}{\text{max }}\\{\lvert B\rvert\in\theta\\}$
and $\zeta=\underset{\theta\in\Theta}{\text{min }}\\{\eta^{2}\in\theta\\}$ is
the square learning rate.

Additionally, we provide a proof that, under certain assumptions, if an open
cover of $D$ has the same homology as the manifold where the support of
$\mathcal{P}$ lies, then $D$ is learnable, and viceversa. While we only
leverage this result as a mechanism for our correctness proofs, we believe
that this result is of interest to the community at large.

###  1.2 Outline

The remaining of this paper is structured as follows: we begin by providing a
brief survey of related approaches to this and similar problems in Section 2.
After establishing notational conventions, basic definitions, and assumptions
in Section 3, we introduce Agora in Section 4. We provide an analysis of its
correctness and asymptotic bounds in Section 5, before concluding in Section 6
with a discussion of our work, as well as potential applications–and
pitfalls–when using this algorithm.

##  2 Related Work

The Socrates model in the Agora algorithm serves two purposes: it must act as
a guide to the training of a candidate model, and it must judge membership of
an unlabeled point with respect to a given concept class. Both requirements
are studied in multiple fields in the machine learning literature, in theory
and in practice.

Socrates acting as a guide is more commonly known as knowledge distillation,
and has multiple variants. It was originally repurposed by Bucilu et al.
(2006) as a model compression technique, and subsequently applied to deep
learning by Hinton et al. (2015). The judgment of Socrates amounts to ensuring
generated points belong to the domain being considered. For this reason, Agora
and some of these techniques can be considered, from an algorithmic point of
view, a type of active learning. See Balasubramanian et al. (2009) and Sener
and Savarese (2018) in the context of deep learning; and Settles (2012) for a
survey of earlier and foundational work on this area, in addition to the work
by Hanneke (2009). However, this discipline focuses on selecting a subset of
the data to be labeled to guarantee efficient generalizability, and tends to
concentrate on specific tasks and models. Our algorithm overlaps more with the
subfield of membership query synthesis Angluin (2001). That being said, Agora
makes the makes no assumptions about the task or the model being input, and
our setting disallows us from sampling more data. Moreover, Socrates is not
constrained to have a good performance on the dataset, and our proofs impose a
lower-bound accuracy of $2/3$.

The third component of Agora–the $\tau$-function–can be seen as a general-
purpose injector of noisy data. The idea of inducing perturbations in the
data, or data augmentation, is comparatively new when applied to deep learning
Lin et al. (2013). This is a wide field of research, mainly due to the fact
that it is known that perturbations improve a model’s generalizability, up to
a point Graham (2014). When facing a task with a small corpus, another
technique commonly employed is the use of generative models to create
synthetic data Ratner et al. (2017); Zhang et al. (2019); Ho et al. (2019). On
the other hand, generating synthetic data is not always a reliable
stratagem–otherwise, the generating model would have perfect accuracy on the
task and there would be no need to train a second model. Theoretical research
around the effectiveness of this work was done by Dao et al. (2018) by framing
it as a kernel method, and Wu et al. (2020) studied its generalizability with
respect to linear transforms. See Oliver et al. (2018) for an overview of both
data augmentation and knowledge distillation, and how they fit on the wider
field of semi-supervised learning. As mentioned earlier, these techniques
often focus on the training set without consideration as to whether they
properly belong to the support of the underlying probability distribution. In
general, this implies that algorithms for synthetic data generation are task-
dependent, unlike Agora. We circumvent the issue of reliability and potential
overfitting with respect to the underlying probability distribution by
providing tight bounds for which the correctness of Agora holds, with
implications towards generalizability.

Considering scenarions where some parts of the i.i.d. assumption do not hold
has become a more active field of research, as the emerging field of
decentralized learning gains momentum. See, for example the applied works by
Dundar et al. (2007), and Hsieh et al. (2020) from a deep learning point of
view. Yet, there is a trove of work done in learning theory with respect to
under which conditions a hypothesis class is able to learn and generalize to
an input task Valiant (1984); Kearns and Valiant (1994); Balcan et al. (2010);
Hanneke (2016), and more specialized to deep neural networks Kawaguchi et al.
(2017), as well as online learning Littlestone (1988); Shalev-Shwartz (2012).
Furthermore, it is known Kearns (1998) that most learning algorithms allow
some form of error-tolerant statistical query akin to the relationship between
Timaeus and Socrates. We leverage these results for our proofs, in addition to
several elements of the field of topological data analysis, and more
specifically, the techniques used in persistent homology. The interested
reader is highly enouraged to review the survey by Wasserman (2018), and the
brief but thorough note by Weinberger (2011), for introductions to this very
active field. Finally, we must highlight that our proof of the correspondence
between homology and learnability is, to the best of our knowledge, new. A
similar argument using the packing number is given by Mohri et al. (2012),
along with a number of related works Haussler (1995); Alon et al. (1997);
however, it is used to bound various complexity measures, rather than the data
itself. More importantly, they do not leverage the homology of the manifold on
which the support of the probability distribution lies, which, as we will
point out, it is easier to work with than other similarity measures.

##  3 Background

###  3.1 Motivation

Consider the problem of learning a probability distribution $\mathcal{P}$ via
a _dataset_ $D=\\{\langle x_{i},y_{i}\rangle\\}_{i\in[1,n]}$, where $D$ is
sampled from $\mathcal{P}$ with a function $\sigma\colon\mathcal{P}\rightarrow
X\times Y$ for some measurable sets $X$ and $Y$. Here we implicitly assume
$\sigma$ assigns a _label_ $y\in Y$ to every $x\sim\mathcal{P}$, where $x\in
X$. The goal of statistical learning is then, following the model by Valiant
(1984), to output a function (“hypothesis”) $f\colon X\rightarrow Y$ via a
polynomial-time algorithm such that the true error,

$\text{Pr}_{\langle x,y\rangle\sim\mathcal{P}}[f(x)\neq y]\leq\epsilon,$ (3)

is minimized with probability at least $1-\delta$ for some
$0<\epsilon,\delta\leq 1/2$, and for any element of the codomain of $\sigma$
as described by any $\mathcal{P}$.

It is common to approximate Equation 3 by considering the empirical error rate

$\text{err}(f(\cdot),E)=\sum_{\langle x_{i},y_{i}\rangle\in
E}\mathbbm{1}[f(x_{i})\neq y_{i}]$ (4)

on a separate _evaluation_ dataset $E\sim\mathcal{P}$, $E\cap D=\emptyset$, as
the main predictor of generalizability of the model. Solving this problem
directly, however, is known to be hard for multiple problems.333For example,
agnostically learning intersections of half-spaces Klivans and Sherstov
(2006); Daniely (2016).

In this paper we concern ourselves with the setting where $D$ is not
_representative_ of a specific $\mathcal{P}$: that is, that in a given
hypothesis class $W$, there does not exist a guarantee under which a function
$f(\cdot)\in W$ trained with $D$ will be able to properly generalize to other
subsets $E\sim\mathcal{P}$. Formally, we assume $\delta$ in Equation 3 is
fixed and hence

######  Definition 1 ($\epsilon$-representativeness of $\mathcal{P}$)

A dataset $D\sim\mathcal{P}$ is $\epsilon$-_representative_ (or
$\epsilon$-learnable) of $\mathcal{P}$ with $f(\cdot)$ if and only if the
relation

$\text{Pr}_{\langle x,y\rangle\sim\mathcal{P}}[f(x)\neq y]\leq\frac{1}{\lvert
D\rvert}\left(\sum_{\langle x_{i},y_{i}\rangle\in D}\mathbbm{1}[f(x_{i})\neq
y_{i}]\right)+\epsilon$ (5)

holds for a given $\epsilon\in[0,1/2]$ and polynomial-time algorithm.

This definition is not new, and it is merely a notational convenience. Some
equivalent measures are the $\epsilon$-_representativeness_ of $\mathcal{P}$
in the sense of Shalev-Shwartz and Ben-David (2014), which is defined as the
difference between the empirical error and the true error; and, following a
result by Hanneke (2016), the minimum sample size for binary function classes
of finite VC dimension can also be considered equivalent in the
converse.444The result by Hanneke (2016) concerns the minimum size of $D$ such
that Equation 4 holds. It follows that if the sample size doesn’t meet that
bound, the probability distribution is not $\epsilon$-learnable. We will
revisit this result in Section 5.

###  3.2 Assumptions

We will assume a binary classification task, $y_{i}\in\\{0,1\\}$, over
$x_{i}\in X\subset\\{0,1\\}^{m}$ $\forall\langle x_{i},y_{i}\rangle\in D$; and
adopt a narrower view of this problem by considering our hypothesis space to
be a finite set of valid weight assignments $w\in W$ to a fixed _architecture_
or _model_ $f(\cdot;w)$, and our goal to be learning a specific $\mathcal{P}$
defined over $X$.

We will make the assumption that, at all times, we have a validation set $E$
which is $\epsilon$-representative of $\mathcal{P}$, and concern ourselves
with the case when the training set $D$ is not. The scenario where neither $D$
nor $E$ are $\epsilon$-representative of $\mathcal{P}$ is readily seen to be
impossible to solve555There is insufficient data to provide a meaningful
answer in polynomial time. and thus we will not consider it further. It could
be argued that this problem could easily be worked around by switching $E$ and
$D$. We will assume that this can’t be done, due to–for example–an evaluation
dataset that varies over time and whose only invariant is that it remains
$\epsilon$-representative of $\mathcal{P}$. More importantly, we assume we are
unable to sample more data; i.e., we no longer have access to $\sigma$.

###### Remark 1

Balcan et al. (2010) showed that the sample complexity bound for an active
learning algorithm dominates that of a passive algorithm. However, the
conditions required to maintain this remarkable result do not hold in our
setup, as we no longer have access to the sampling function needed in active
learning. Nonetheless, we provide similar bounds for this scenario in Lemma 3.

Likewise, we will only consider, for simplicity, that $\sigma$ is noise-free,
and for some proofs we will assume that both $X$ and the support of
$\mathcal{P}$ lie on some compact Riemannian submanifold of a Euclidean space,
and that all sets involved are measurable.666Real data tends to be high-
dimensional, sparse, and not necessarily lying on a manifold. See Niyogi et
al. (2011) and Section 6 for a discussion on this assumption.  Positive
results around the reconstructability of a manifold under noisy conditions can
be found in Niyogi et al. (2011); Genovese et al. (2014) and Chazal et al.
(2017b). Still, in Section 6 we discuss further improvements to Agora that do
not rely on these constraints. We also provide in Corollary 2 an analysis of
the runtime of Agora under more relaxed assumptions, for the case where the
input is a neural network and, as discussed, the existence of a polynomial-
time algorithm that satisfies Equations 3 and 5 is not guaranteed.

With these constraints we are able to restate the problem as the one of
finding the best weight assignment $w^{*}$ from a set
$W=\\{w_{1},\dots,w_{k}\\}$ such that the accuracy

$\text{acc}(f(\cdot;w^{*}),E)=1-\text{err}(f(\cdot;w^{*}),E)$ (6)

is maximized. This last convention is for practical purposes only, and does
not affect the mathematics governing the problem.

We will use $\bar{f}$ to denote the number of steps required to obtain an
output from a function $f(\cdot;\cdot)$ given a fixed-size input $x$
regardless of other parameters, that is,
$\bar{f}=\operatorname{\Theta}\\!\left(f(x;w)\right)$, $\forall w\in W$.
Likewise, we will refer to the training algorithm used to assign a set of
weights to $f(\cdot;w)$ as train-model$(f,D,\theta)$, and remark that it runs,
by definition, in a number of steps polynomial in $\lvert D\rvert$, $\bar{f}$,
and $\theta$. In this context, $\theta$ is a set of _hyperparameters_ that
control the algorithm’s behavior and are not learned by the architecture
itself. The choice of $\theta$ influences directly the accuracy that can be
attained by $f(\cdot;w)$ on $E$, especially in cases where Equations 4 and 6
are non-convex. We will revisit this assumption in Section 5. Finally, we will
write use $\mathcal{B}_{\rho}(x)$ to refer to a $m$-ball of radius $\rho$ and
centered at some $x\in\mathbb{R}^{m}$.

###  3.3 The $\tau$-function

The $\tau$-function is Agora’s central mechanism to improve the performance of
Timaeus. It exploits the structure of $X$ to generate points, which in turn
are used by the algorithm to obtain a dataset that is
$\epsilon$-representative of $\mathcal{P}$. We will discuss this function in
detail in Section 5.

######  Definition 2 (The $\tau$-function)

Let $D=\\{\langle x_{i},y_{i}\rangle\\}_{i\in[1,n]}$ be a dataset sampled from
a distribution $\mathcal{P}$. Let $\hat{X}=\\{x_{i}\in D\\}$ be the set of all
the points contained in $D$, and let $\mathcal{Q}_{x,\rho}$ be a uniform
probability distribution with support
$\text{supp}(\mathcal{Q}_{x,\rho})=\\{x^{\prime}\colon
x^{\prime}\in\mathcal{B}_{\rho/4}(x)\land x^{\prime}\in Z\land x^{\prime}\neq
x\\}$, for some $\rho>0$ and $X\subset Z\subset\\{0,1\\}^{n}$. The
$\tau$-function, parametrized by $\rho$, is then defined as:

$\displaystyle\tau_{\rho}\colon\hat{X}$ $\displaystyle\rightarrow Z,$ (7)
$\displaystyle\tau_{\rho}(x)\colon\hat{X}$
$\displaystyle\mapsto\tilde{x}\sim\mathcal{Q}_{x,\rho}.$ (8)

##  4 The Agora Algorithm

The Agora algorithm takes as an input a tuple $\langle
f,S,D,E,\Theta,\tau_{\rho}\rangle$, where $f(\cdot;\cdot)$ is an untrained,
fixed architecture (Timaeus) $f\colon X\times W\rightarrow Y$;
$S(\cdot;\cdot)$ is a trained model (Socrates) $S\colon
X\times\\{w^{S}\\}\rightarrow Y$; and $D$ and $E$ are datasets with
$D,E\sim\mathcal{P}$, $D\cap E=\emptyset$, and $E$ is
$\epsilon$-representative of $\mathcal{P}$ for some, perhaps unknown,
$\epsilon$. Agora also has access to a training subroutine train-
model$(\cdot,\cdot,\cdot)$, as described in Section 3.2, with a corresponding
set of possible hyperparameter configurations
$\Theta=\\{\theta_{1},\dots,\theta_{t}\\}$; and a $\tau$-function
$\tau_{\rho}(\cdot)$ parametrized by some $\rho$.

The full procedure is displayed in Algorithm 1. It alternates between
selecting the highest-performing Timaeus over multiple sets of
hyperparameters, and augmenting the training set with elements generated by
$\tilde{x}=\tau_{\rho}(x)$ and scored with Socrates, $S(\tilde{x};w^{S})$.
Specifically, at the $k^{\text{th}}$ iteration, the algorithm will execute the
following steps:

  * •

Train $\lvert\Theta^{(k)}\rvert$ Timaeus models $f(\cdot;w_{i}^{*,(k)})$ on
$D^{(k)}$ corresponding to every $\theta_{i}\in\Theta^{(k)}$, and select the
highest-accuracy model. Tabulate all the scores for the current iteration.

  * •

Create a set $M^{(k)}=\\{\tau_{\rho}(x)\colon\langle x,y\rangle\in E\land
f(x;w^{*,(k)}_{i})\neq y\land\tau_{\rho}(x)\not\in E\\}$, label it with
Socrates, and append it to the training set,
$D^{(k+1)}=D^{(k)}\cup\\{\langle\tilde{x},S(\tilde{x},w^{S})\rangle\colon$
$\tilde{x}\in M\\}$.

  * •

Sort the tabulated performances along with their hyperparameters in non-
decreasing order. Select the hyperparameter $\theta^{(k)}_{0,j}$ belonging to
the longest sequence of contiguous hyperparameters rooted at the first
element, $\theta^{(k)}_{0}\in\Theta^{(k)}$; finally, remove all the
hyperparameter sets from $\Theta^{(k)}$ that contain $\theta^{(k)}_{0,j}$,
$\Theta^{(k+1)}=\\{\theta_{t}\colon\theta_{0,j}^{(k)}\not\in\theta_{t},\;\forall\theta_{t}\in\Theta^{(k)}\\}$.

Algorithm 1 The Agora algorithm

1: Input: Timaeus $f$, Socrates $S$, training dataset $D$, evaluation dataset
$E$, hyperparameter sets $\Theta$, $\tau$-function $\tau_{\rho}(\cdot)$

2: $a^{*}\leftarrow-\infty$

3: $f(\cdot;w^{*})\leftarrow\emptyset$

4: while $|\Theta|\geq 1$ do

5: $Q\leftarrow\\{\\}$

6: for $\theta_{i}\in\Theta$ do

7: $f(\cdot;w^{*}_{i})\leftarrow$ train-model$(f,D,\theta_{i})$

8: $a_{i}\leftarrow$ acc$(f(\cdot;w^{*}_{i}),E)$

9: $Q\leftarrow Q\cup\\{\langle a_{i},\theta_{i}\rangle\\}$

10: if $a_{i}>a^{*}$ then

11: $f(\cdot;w^{*})\leftarrow f(\cdot;w^{*}_{i})$

12: $a^{*}\leftarrow a_{i}$

13: end if

14: end for

15: $M\leftarrow\\{\tau_{\rho}(x):\langle x,y\rangle\in E\land f(x;w^{*})\neq
y\land\tau_{\rho}(x)\not\in E\\}$

16: $D\leftarrow
D\cup\\{\langle\tilde{x},S(\tilde{x};w^{S})\rangle\colon\tilde{x}\in M\\}$

17: Sort $Q$ in non-decreasing order with respect to $a_{i}$.

18: $\theta_{0}\leftarrow$ Select the first hyperparameter set of $Q$.

19: $\theta_{0,j}\leftarrow$ Select from $Q$ the longest sequence of
contiguous hyperparameters with $\theta_{0,j}\in\theta_{0}$ as their first
element, starting in $\theta_{0}$, and breaking ties consistently.

20:
$\Theta\leftarrow\\{\theta_{t}\colon\theta_{0,j}\not\in\theta_{t},\;\forall\theta_{t}\in\Theta\\}$

21: end while

22: return $f(\cdot;w^{*})$

##  5 Analysis

We begin this section by proving properties of the $\tau$-function. This is
done by leveraging some assumptions and techniques from the field of
topological data analysis, and then use these results to provide bounds
regarding Agora’s correctness and runtime.

###  5.1 Properties of the $\tau$-Function

We provide proofs around two basic facts needed for the correctness of Agora:
first, that the $\tau$-function is able to generate a dataset that, when
labeled correctly, is $\epsilon$-representative of $\mathcal{P}$ (shown in
Lemma 3); and second, that in the (ideal) case where the $\tau$-function is
equivalent to $\sigma$ and Socrates has perfect accuracy, using the latter to
label points generated by the former allows an arbitrary classifier to
increase its performance (Lemma 4). As part of this analysis, we additionally
prove in Lemma 1 that if an open cover for the dataset is embedded has the
same homology as the manifold where the support of $\mathcal{P}$ lies, the
dataset will necessarily be $\epsilon$-representative of $\mathcal{P}$, and
viceversa.

To do this, we will rely on the well-known result by Niyogi et al. (2008),
which we reproduce below for convenience with our notation:

######  Theorem 5.1 (Theorem $3.1$ of Niyogi et al. (2008))

Let $\mathcal{M}$ be a compact submanifold of $\mathbb{R}^{N}$ with condition
number $\mu=\text{inf}_{x\in\mathcal{M}}\lvert\lvert
x-m\rvert\rvert_{\mathbb{R}^{N}}$, where $m$ is its medial axis. Let
$X=\\{x_{1},\dots,x_{n}\\}$ be a set of $n$ points drawn i.i.d. according to
the uniform probability measure with support on $\mathcal{M}$. Let
$0<\rho<\mu/2$. Let $U=\cup_{x_{i}\in X}\mathcal{B}_{\rho}(x_{i})$ be a
correspondingly random open subset of $\mathbb{R}^{N}$.

Let
$\beta(\rho)=\frac{\operatorname{vol}{(\mathcal{M})}}{\cos^{m}{(\arcsin{(\frac{\rho}{2\mu})})}\operatorname{vol}{(\mathcal{B}^{m}_{\rho})}}$,
for $m=\text{dim}(\mathcal{M})$, and
$\operatorname{vol}{(\mathcal{B}^{m}_{\rho})}$ the volume of a $m$-ball of
radius $\rho$.

Then, for all

$n>\beta\left(\rho/4\right)\left(\ln{\beta(\rho/8)}+\ln{(1/\delta)}\right),$
(9)

the homology of $U$ equals the homology of $\mathcal{M}$ with probability
greater than $1-\delta$.

Intuitively, the proof for Theorem 5.1 relies on the fact that the homologies
are equal whenever $X$ is dense (in a precise sense) in $\mathcal{M}$, and
hence the number of samples required to ensure such a condition is lower-
bounded by Equation 9.777 The constraint around the condition number (often
known referred to as reach, as introduced by Federer (1959)) being strictly
positive can be weakened to a certain degree Chazal et al. (2006). It is known
Chazal et al. (2017a) that a smooth compact submanifold of $\mathbb{R}^{n}$
always has positive reach. To analyze the correctness of the $\tau$-function,
however, it suffices to enforce the sample size as in Equation 9, and note
that our ambient space and our noisy sampled space are roughly the same;
specifically, they both have the same dimension, and the former is contained
in the latter. We formalize these observations in Lemma 1.

###### Lemma 1

Let $D$ be a dataset sampled from a probability distribution $\mathcal{P}$
with support $X$. Assume $X$ lies on a compact Riemannian submanifold of
$\mathbb{R}^{m}$, $\mathcal{X}$, with condition number $\mu$ in the sense of
Niyogi et al. (2008). Let $\\{f(\cdot;w)\colon w\in W\\}$ be a set of
classifiers with VC dimension $d$.

Let $\rho$ correspond to a choice of $\rho/4$-covering number for
$\mathcal{X}$ such that $0<\rho<\mu/2$, and let

$\Lambda_{\rho}=\left(\frac{\rho\sqrt{\pi}}{4}\right)\left(1-\frac{\rho^{2}}{64\mu^{2}}\right)^{1/2}.$
(10)

Also let $0<\delta\leq 1/2$. Then the homology of an open subset
$\cup_{x_{i}\in D}\mathcal{B}_{\rho}(x_{i})$ equals the homology of
$\mathcal{X}$ with probability at least $\delta$, if and only if $D$ is
$\epsilon$-representative of $\mathcal{P}$ with $f(\cdot;\cdot)$, when

$\displaystyle\epsilon$
$\displaystyle\in\operatorname{\Omega}\\!\left(\left(\frac{\Lambda_{\rho}^{m}}{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}\right)^{1/2}\right)$
(11) $\displaystyle d$
$\displaystyle\in\operatorname{\Omega}\\!\left(\log{\left(2^{m}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{m/2}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\Lambda_{\rho}^{m}}\right)}\right).$
(12)

###### Proof

In Appendix 0.A.

###### Remark 2

The results from Lemma 1 are applicable to a range of models wider than fixed-
architecture classifiers, which are the main focus of this paper.

###### Lemma 2

Let $D\sim\mathcal{P}$ be a dataset that is $\epsilon$-representative of
$\mathcal{P}$ for a set of classifiers $\\{f(\cdot;w)\colon w\in W\\}$ with VC
dimension $d$, and assume the support of $P$ lies on a manifold $\mathcal{X}$
as described in Lemma 1. Then, if for any other dataset $E\sim\mathcal{P}$,
the homology of some open cover of $\mathcal{X}$, $U_{D}=\cup_{x_{i}\in
D}\mathcal{B}_{\rho}(x_{i})$, equals the homology of another open cover
$U_{E}=\cup_{x_{i}\in E}\mathcal{B}_{\rho}(x_{i})$, then $E$ is also
$\epsilon$-representative of $\mathcal{P}$ for the same set of classifiers,
and appropriate choices of $\rho$, $d$, $\lvert E\rvert$, and $\epsilon$.

###### Proof

It follows immediately from Lemma 1.

With both results we are now able to prove a key result: the dataset generated
by the $\tau$-function will also be $\epsilon$-learnable. Our proof follows
closely the techniques from Niyogi et al. (2008), as this problem has a
natural solution in terms of their homology-based framework.

###### Lemma 3

Let $E\sim\mathcal{P}$ be a dataset that is $\epsilon$-representative of a
probability distribution $\mathcal{P}$ with support $X$, for a set of
classifiers $\\{f(\cdot;w)\colon w\in W\\}$ with VC dimension $d$, for
$\epsilon$, $\lvert E\rvert$ and $d$ as stated in Lemma 1. Let
$\tau_{\rho}(\cdot)$ be a $\tau$-function parametrized by $0<\rho<\mu/2$.

Assume that the domain $Z$ of $\tau_{\rho}(\cdot)$ is describable as a compact
Riemannian submanifold of $\mathbb{R}^{m}$ with the same condition number as
$\mathcal{X}$. Consider the set

$\tilde{E}^{(\kappa)}=\bigcup_{j=1}^{\kappa}\\{\tau_{\rho}(x)\colon\forall
x\in E\land\tau_{\rho}(x)\not\in E\\}$ (13)

formed by $\kappa$ calls to $\tau_{\rho}(\cdot)$ on elements of $E$.

Then, for $0<\delta\leq 1/2$ and $\Delta=Z\setminus E$; with $\lvert
E\cup\Delta\rvert\leq c\lvert X\rvert$ for $0<c<1$; if

$\kappa\geq\left(\frac{\lvert X\rvert+\lvert\Delta\rvert}{\lvert
X\rvert(1-c)+2\lvert\Delta\rvert}\right)\ln{\left(\frac{\lvert
E\rvert}{\delta}\right)}$ (14)

then $\tilde{E}^{(\kappa)}$ is $\epsilon$-representative of $\mathcal{P}$ with
probability at least $1-\delta$.

###### Proof

In Appendix 0.B.

It is important to highlight that equivalence up to homology is a weak
relation, in comparison to, say, equivalence up to homeomorphism.
Unfortunately, this is an undecidable problem for dimensions larger than $4$
Markov (1958). One implication of Lemma 3 is that, if $Z=X$, the number of
calls to $\tau_{\rho}(\cdot)$ is minimal for any input problem. We leverage
these ideas to obtain the notion of a _faithful $\tau$-function_:

######  Definition 3 (The Faithful $\tau$-Function)

Let $\tau_{\rho}\colon X\rightarrow Z$ be a $\tau$-function parametrized with
some $\rho$. We say that $\tau_{\rho}(\cdot)$ is _faithful_ whenever $Z=X$ and
$\rho$ corresponds to the minimum $\rho/4$-covering number of $\mathcal{X}$.

We prove in Lemma 4 that it is possible to be able to increase the performance
of the model through a faithful $\tau$-function.

###### Lemma 4

Let $D,E\sim\mathcal{P}$ be datasets such that $D\cap E=\emptyset$, and let
$\mathcal{F}=\\{f(\cdot;w)\colon w\in W\\}$ be a set of classifiers with VC
dimension $d$, trained on $D$, and with $\sup\\{\text{acc}(f,E)\colon
f(\cdot;\cdot)\in F\\}=\alpha$ for some $f(\cdot;\cdot)$. Assume we have an
oracle $\mathcal{O}(\cdot;w^{o})$ for $\mathcal{P}$ such that
acc$(\mathcal{O},F)=1,\;\forall F\sim\mathcal{P}$, and a faithful
$\tau$-function $\tau_{\rho}(\cdot)$. Assume that the conditions from Lemmas 2
and 3 hold.

Then training $f(\cdot;\cdot)$ on a dataset

$D^{\prime}=D\cup\\{\langle\tilde{x},\mathcal{O}(\tilde{x};w^{o})\rangle\colon\tilde{x}=\tau_{\rho}(x)\land
x\in E\land\tilde{x}\not\in E\\}$ (15)

and evaluating it on $E$ will have accuracy acc$(f,E)\geq\alpha$.

###### Proof

From Lemma 3 it can be seen that, if $F$ has the appropriate size,
$D^{\prime}$ will be at least $(1-\alpha)$-learnable by some $f(\cdot;w\in
W)$. Given that $\mathcal{O}(\cdot;w^{o})$ has zero error across $X$, it
follows that we can guarantee that the labeling produced by
$\mathcal{O}(\tau_{\rho}(x);w^{o}))$ will be correct for any $x\in X$. The VC
dimension of $\mathcal{F}$ remains unchanged, but adding a new point to $D$
lowers the Rademacher complexity of this problem,

$\sqrt{\frac{2d\ln{(\lvert D\rvert+\lvert F\rvert)}}{\lvert D\rvert+\lvert
F\rvert}}<\sqrt{\frac{2d\ln{(\lvert D\rvert)}}{\lvert D\rvert}},$ (16)

and hence $E$ remains at least $(1-\alpha)$-learnable.

In practice we might not have access to the conditions from Lemma 4 around a
faithful $\tau$-function and an oracle–indeed, one of the constraints for our
problem is the lack of access to $\sigma$. Nonetheless, these assumptions
allow us to simplify the analysis of Agora. In the case where the
$\tau$-function is not faithful, the bounds still hold as long as the
conditions of Lemma 3 are met, as it is a probabilistic argument. Indeed, we
are still able to work around such limitations to an extent, which is be the
topic of Sections 4 and 5.

###  5.2 Correctness

We state bounds for the accuracy of Socrates, such that it allows us to
maintain the invariants from Lemma 4; and then prove correctness of Algorithm
1. To begin, we introduce the notions of a _random classifier_ and _perfect
memory_ which, like Definition 3, are meant to simplify our analysis. Then we
show that for a random classifier, Agora is able to return a trained model
with arbitrarily low error rate (Lemma 5) and then we extend the results to
obtain correctness conditions for our algorithm (Theorem 5.2).

######  Definition 4 (The Random Classifier)

Let $D\sim\mathcal{P}$ be a dataset with $p$ positive labels and $1-\lvert
D\rvert/p$ negative labels. A _random classifier_ $f$ outputs, when called,
$1$ with probability $1/p$, and $0$ otherwise, regardless of its input.

It is clear that a (specific) model that actually learns the input dataset
will almost always have a better performance than a random classifier. Moving
forward, we will consider the results involving a random classifier a lower
bound on the performance of any other model, so long as the data remains
balanced.888This statement does not hold in all cases. If the data were
imbalanced across all $\mathcal{P}$, “dumber” models could actually perform
better, e.g., guessing all zeros in a problem with $\lvert X\rvert-1$ negative
labels.

######  Definition 5 (Perfect Memory of a Classifier)

Let $\langle f,D,\theta\rangle$ be an input to train-
model$(\cdot,\cdot,\cdot)$, such that acc$(f(\cdot;w^{D}),D)=a$ for some
trained model $f(\cdot;w^{D})$. We say that an architecture $f(\cdot;\cdot)$
has _perfect memory_ with a given training algorithm, if its performance does
not change when augmenting the dataset and retraining it.

That is, for some $\langle x,y\rangle\not\in D$, if for any input $\langle
f,D^{\prime}=D\cup\\{\langle x,y\rangle\\},\theta^{\prime}\rangle$,
$\text{acc}(f(\cdot;w^{D^{\prime}}),D^{\prime})=a^{\prime}$, then the
following relation holds:

$a-\frac{1}{\lvert D\rvert+1}\leq a^{\prime}\leq a+\frac{1}{\lvert
D\rvert+1}.$ (17)

###### Lemma 5

Let $I=\langle f,S,D,E,\Theta,\tau_{\rho}\rangle$ be an input to Agora, such
that $f(\cdot;\cdot)$ is a random classifier with perfect memory, and
$\tau_{\rho}(\cdot)$ is faithful. Assume Socrates has accuracy
acc$(S,D^{\prime})\geq 2/3$, $\forall D^{\prime}\sim\mathcal{P}$, and, for
simplicity, that the problem has equal proportion of negative and positive
labels. Then the accuracy of $f(\cdot;\cdot)$ on $E$ at the end of the
$k^{\text{th}}$ iteration of Agora is given by:

$\text{acc}^{(k)}(f,E)\geq 1-\frac{1}{2^{k}}$ (18)

###### Proof

Assume, for simplicity,
$\Theta=\\{\theta_{1},\dots,\theta_{k}\colon\theta_{i}\cap\theta_{j}=\emptyset\;\forall\theta_{i},\theta_{j}\\}$
and $f(\cdot;w\in\\{w\\})$. The other cases follow immediately from Lines 10
and 20 and the proof for this base case.

Let $D^{(1)}$ be the dataset at the beginning of the first iteration of Agora.
Since $f(\cdot;\cdot)$ is a random classifier, its performance on $E$ is at
least $a^{(1)}_{f}\geq 1/2$, and hence its error rate is $e^{(1)}_{f}\leq
1/2$.

Let the dataset constructed by Lines 15 and 16 be $M^{(1)}$. Clearly, $\lvert
M^{(1)}\rvert\leq\lvert E\rvert/2$, and hence

$\lvert D^{(2)}\rvert\leq\lvert D\rvert+\frac{\lvert E\rvert}{2}.$ (19)

On the next iteration, the labels of every element in $\lvert M^{(2)}\rvert$
have a chance acc$(S,M^{(2)})\geq 2/3$ of being correct, and hence the number
of points that are misclassified is at most $\lvert E\cap M^{(1)}\rvert/2$, or

$\lvert M^{(2)}\rvert\leq\frac{\lvert E\rvert}{4},$ (20)

since $\tau_{\rho}(\cdot)$ is faithful. Hence each $\langle
x_{i},y_{i}\rangle\in E$ is classified correctly with probability
Pr$[f(x_{i})=y_{i}]\geq 1/3$ in the case where Socrates correctly predicted
the label for its corresponding point
$\langle\tilde{x}_{i},S(\tilde{x}_{i})\rangle\in D^{(2)}$. If, for some
$\langle x_{i},y_{i}\rangle\in E$, $f(x_{i})=y_{i}$, but its corresponding
point was incorrectly labeled by Socrates, it will not appear again in any
$M^{(k)}$ due to the perfect memory of $f(\cdot;\cdot)$.

Generalizing the above, it can be seen that at any iteration $k$ the size of
$M^{(k)}$ will be given by

$\lvert M^{(k)}\rvert\leq\frac{\lvert E\rvert}{2^{k}}.$ (21)

Induction on Equation 21 concludes the proof.

Remark that the assumption that the dataset is balanced can be removed and
Lemma 5 would still hold, but now as a function of the proportion of labels.

Regardless, if the _convergent hyperparameter set_ –that is, the final
hyperparameter in the algorithm’s run–is optimal with respect to $\Theta$, the
output of Agora is correct.

###### Theorem 5.2

Let $I=\langle f,S,D,E,\Theta,\tau_{\rho}\rangle$ be an input to Agora, such
that Timaeus is a random classifier with perfect memory, and
$\tau_{\rho}(\cdot)$ is faithful. Let $\theta^{*}$ be the convergent
hyperparameter set for the entire run of Agora, with a corresponding trained
model $f(\cdot;w^{*}\in W)$. Then, for any $\theta_{i}\in\Theta$, if Socrates
has accuracy acc$(S,D^{\prime})\geq 2/3$, $\forall D^{\prime}\sim\mathcal{P}$,
and the problem has equal proportion of positive and negative labels, the
following holds:

$\text{acc}(f(\cdot;w^{*}),E)\geq\text{acc}(f(\cdot;w_{i}),E),$ (22)

where $f(\cdot;w_{i}\in W)$ is the output of train-model$(f,D,\theta_{i})$.

###### Proof

By a straightforward application of Agora and Lemma 5. To begin, assume for
simplicity that we run the algorithm on $I^{\prime}=\langle
f,S,D,E,\\{\theta_{1},\theta_{2}\\},\tau_{\rho}\rangle$, such that
$\lvert\theta_{1}\cap\theta_{2}\rvert\leq\min{(\lvert\theta_{1}\rvert,\lvert\theta_{2}\rvert)}-1$.
Agora only runs for $k=2$ iterations, evaluating three models. On the first
iteration, it obtains two models corresponding to $\theta_{1}$ and
$\theta_{2}$, $f(\cdot;w^{(k=1)}_{1})$ and $f(\cdot;w^{(k=1)}_{2})$, and
prunes out the lowest performing hyperparameter set–say, $\theta_{1}$. Let
$f(\cdot;w^{*,(1)}_{2})$ be the trained model at $k=1$.

On the second iteration, it evaluates only one model, $f(\cdot;w^{(2)}_{2})$.
Call the trained version $f(\cdot;w^{*,(2)}_{2})$. Since $f(\cdot;\cdot)$ has
perfect memory, by Lemma 5 and Lines 10 and 20 we know that

$\text{acc}(f(\cdot;w^{*,(1)}_{1}),E)\leq\text{acc}(f(\cdot;w^{*,(1)}_{2}),E)\leq\text{acc}(f(\cdot;w^{*,(2)}_{2}),E),$
(23)

and hence $\theta^{(2)}=\theta_{2}$ is the convergent hyperparameter set for
Agora for $I^{\prime}$.

Since the performance of $f(\cdot;\cdot)$ does not decrease when calling
Socrates, in general we can see that, across the entire run of the algorithm,
the convergent hyperparameter set will not be removed. In other words, if
$\theta_{j}$ is the aforementioned set, and $k$ the total number of
iterations, for any $i<k$,

$\text{acc}(f(\cdot;w^{*,(k-i)}_{l}),E)\leq\text{acc}(f(\cdot;w^{*,(k)}_{j}),E),$
(24)

for any $\theta_{l}\in\Theta$, $\theta_{l}\neq\theta_{j}$.

It follows that the performance of $f(\cdot;\cdot)$ on the convergent
hyperparameter set, for any instance of Agora, will upper bound the other
members of $\Theta$.

###### Corollary 1

Let $I=\langle f,S,D,E,\Theta,\tau_{\rho}\rangle$ be an input to Agora, where
$\tau_{\rho}(\cdot)$ is a faithful $\tau$-function and Timaeus has perfect
memory, but is not necessarily a random classifier. Let $f(\cdot;w^{*})$ be
the model obtained returned by Agora. Let $f(\cdot;w^{e})$ be the model
obtained from an enumeration over all $\Theta$. Then

$\text{acc}(f(\cdot;w^{*}),E)=r\cdot\text{acc}(f(\cdot;w^{e}),E),$ (25)

for $1\leq r\leq 2\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right)$.

###### Proof

By Lemma 5, if $\tau_{\rho}(\cdot)$ is faithful and $f(\cdot;\cdot)$ has
perfect memory, Agora converges in $1\leq k\leq\lvert\Theta\rvert$ iterations
to a specified accuracy which is lower-bounded by $1-2^{-k}$.

An enumeration over $\Theta$ is equivalent to the first iteration of Agora. It
follows immediately from Lemma 5 that an upper bound is given when
$k=\lvert\Theta\rvert$, or:

$\displaystyle\text{acc}(f(\cdot;w^{e}),E)$ $\displaystyle\geq 1-\frac{1}{2},$
(26) $\displaystyle\text{acc}(f(\cdot;w^{*}),E)$ $\displaystyle\geq
1-\frac{1}{2^{\lvert\Theta\rvert}}.$ (27)

Hence:

$r=\frac{\text{acc}(f(\cdot;w^{*}),E)}{\text{acc}(f(\cdot;w^{e}),E)}\leq
2\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right),$ (28)

as desired. The lower bound follows from the fact that the case where
$\Theta=\\{\theta\\}$ means that Agora is equivalent to an enumeration, and
$k=1$.

Note that the bounds obtained in Corollary 1 are fairly loose, and can be
tightened on a model-by-model basis.

###  5.3 Time Bounds

In this section we provide runtime bounds for Agora. Unlike our earlier
results, we are no longer able to assume that a random classifier will bound
the performance of most models of interest. The runtime of this algorithm is
highly dependent on how long it takes for an arbitrary input to converge. We
show in Theorem 5.3 that the runtime for Agora is polynomial on train-
model$(\cdot,\cdot,\cdot)$, the cardinalities of $\lvert\Theta\rvert$ and
$\lvert E\rvert$, and the inference times for Timaeus and Socrates. We
conclude this section by narrowing down these results in Corollary 2 for a
large class of inputs.

###### Theorem 5.3

Let $I=\langle f,S,D,E,\Theta,\tau_{\rho}\rangle$ be an input to Agora, where
Timaeus has perfect memory and Socrates has accuracy acc$(S,D^{\prime})\geq
2/3$, $\forall D^{\prime}\sim\mathcal{P}$.

Assume $\tau_{\rho}(\cdot)$ is faithful, and the assumptions from Lemma 3
hold. Assume train-model$(f,D,\theta)\in O(\text{poly}(\bar{f},\lvert
D\rvert,\theta))$. If the problem has balanced positive and negative labels,
then Agora terminates in

$\operatorname{O}\\!\left(\lvert\Theta\rvert^{2}\left(\log{\lvert\Theta\rvert}+\lvert\theta\rvert^{2}+T_{f}\left(\lvert
D\rvert+\frac{\lvert
E\rvert}{2^{\lvert\Theta\rvert-1}}\right)\right)+\bar{S}\lvert\Theta\rvert\lvert
E\rvert\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right)\right)$ (29)

steps, where $T_{f}(\lvert D\rvert)\in\Omega(\text{poly}(\bar{f},\lvert
D\rvert,\theta))$, $\forall\theta\in\Theta$ and any $f(\cdot;w\in W)$.

###### Proof

Let $k$ be an iteration of Agora, and let $T_{f}(\lvert D^{(k)}\rvert)$ be the
upper bound number of steps required to train each of the $\Theta^{(k)}$
Timaeus models $f(\cdot;\cdot)$ on $D^{(k)}$. Then the cost, per iteration, of
Line 6 to Line 14 is

$\operatorname{O}\\!\left(\lvert\Theta^{(k)}\rvert\left(T_{f}(\lvert
D^{(k)}\rvert)+\bar{f}\lvert E\rvert\right)\right).$ (30)

Lines 15 and 16 involve $\lvert M^{(k)}\rvert$ calls to $\tau_{\rho}(\cdot)$,
and $\lvert M^{(k)}\rvert$ calls to Socrates. Both operations can be executed
at the same time, and, since Timaeus has perfect memory, we know that the
bound corresponding to this step is tight. Moreover, Line 17 is a simple
sorting statement, which we assume to be comparison-based, while Lines 19 and
20 can be executed with a naïve implementation that compares every element and
employs a counting argument, in time $O(\lvert
Q^{(k)}\rvert\lvert\theta\rvert^{2})$, for $\theta\in\Theta^{(k)}$.

This yields:

$\operatorname{O}\\!\left(\lvert M^{(k)}\rvert\bar{S}+\lvert
Q^{(k)}\rvert\lvert\theta\rvert^{2}+\lvert Q^{(k)}\rvert\log{\lvert
Q^{(k)}\rvert}\right).$ (31)

Adding both equations together, and using the fact that $\lvert
Q^{(k)}\rvert=\lvert\Theta^{(k)}\rvert$, gives a total time per iteration of

$\text{Cost}(k)=\operatorname{O}\\!\left(\lvert\Theta^{(k)}\rvert\left(T_{f}(\lvert
D^{(k)}\rvert)+\bar{f}\lvert
E\rvert+\lvert\theta\rvert^{2}+\log{\lvert\Theta^{(k)}\rvert}\right)+\lvert
M^{(k)}\rvert\bar{S}\right).$ (32)

Since in the worst case Agora will prune exactly one member of $\Theta$ on
every iteration, Equation 32 can be expressed in terms of
$\lvert\Theta\rvert$. By using Lemma 5 we obtain:

$\sum_{k=1}^{\lvert\Theta\rvert}\text{Cost}(k)=\sum_{k=1}^{\lvert\Theta\rvert}\lvert\Theta^{(k)}\rvert\left(\bar{f}\lvert
E\rvert+T_{f}(\lvert D^{(k)}\rvert)\right)+\\\
\operatorname{O}\\!\left(\lvert\Theta\rvert^{2}\left(\log{\lvert\Theta\rvert}+\lvert\theta\rvert^{2}\right)+\bar{S}\lvert\Theta\rvert\lvert
E\rvert\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right)\right).$ (33)

Note that, for $k\geq 2$,

$\sum_{k=1}^{\lvert\Theta\rvert}\lvert\Theta^{(k)}\rvert T_{f}(\lvert
D^{(k)}\rvert)=\lvert\Theta\rvert T_{f}(\lvert
D\rvert)+\sum_{k=2}^{\lvert\Theta\rvert}(\lvert\Theta\rvert-(k-1))T_{f}\left(\lvert
D\rvert+\frac{\lvert E\rvert}{2^{k-1}}\right),$ (34)

and so

$\displaystyle\sum_{k=1}^{\lvert\Theta\rvert}\left(\bar{f}\lvert
E\rvert+T_{f}(\lvert
D^{(k)}\rvert)\right)\in\operatorname{O}\\!\left(\lvert\Theta\rvert^{2}\left(\bar{f}\lvert
E\rvert+T_{f}\left(\lvert D\rvert+\frac{\lvert
E\rvert}{2^{\lvert\Theta\rvert-1}}\right)\right)\right).$ (35)

It then follows that Equation 33 simplifies to

$\sum_{k=1}^{\lvert\Theta\rvert}\text{Cost}(k)\in\operatorname{O}\\!\left(\lvert\Theta\rvert^{2}\left(\log{\lvert\Theta\rvert}+\lvert\theta\rvert^{2}+T_{f}\left(\lvert
D\rvert+\frac{\lvert
E\rvert}{2^{\lvert\Theta\rvert-1}}\right)\right)+\right.\left.\bar{S}\lvert\Theta\rvert\lvert
E\rvert\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right)\right),$ (36)

as desired.

The key assumption behind Theorem 5.3–and Agora, for that matter–is that the
hypothesis class is able to learn, with high probability, $\mathcal{P}$ in a
polynomial number of steps. As mentioned in Section 3.1, this is an
unrealistic assumption for most systems of interest given that there is no
guarantee that an algorithm fulfilling the conditions for $\textsc{train-
model}(\cdot,\cdot,\cdot)$ exists.

We can, however, prove similar results to Theorem 5.3 for a specific subset of
inputs to Agora where the problem is non-convex, but the training algorithm
does run in polynomial time with respect to $\bar{f}$, $D$, $\theta$, and an
extra set of parameters $\pi$. To see this, let us now shift our analysis to
the case where Timaeus and Socrates are piecewise-continuous, real-valued
functions with their output mapped consistently to $\\{0,1\\}$. Due to the
nonconvexity and discontinuities present in Equations 4 and 6, a carefully-
chosen surrogate loss999See, for example Bartlett et al. (2006) and Nguyen et
al. (2009). is commonly employed in tandem with a polynomial-time (or better)
optimization algorithm, such as stochastic gradient descent (SGD).

If we choose the optimizer for train-model$(\cdot,\cdot,\cdot)$ to be SGD, and
the surrogate loss is $L$-Lipschitz smooth, bounded from below and with
bounded stochastic gradients for some $G$, then train-
model$(\cdot,\cdot,\cdot)$ will return an $\epsilon$-accurate solution in
$O(\lvert B\rvert\bar{f}/\epsilon^{c})$ steps, for some constant $c\leq 2$,
$B\subset D$, and an appropriate choice of learning rate $\eta$. Most SGD-
based training procedures present such a runtime, even in the non-convex
setting Reddi et al. (2018); Nguyen et al. (2020), as long as the surrogate
loss function fulfills the conditions mentioned above. Indeed, Nguyen et al.
(2020) showed that, for a specific variant of SGD referred to as _shuffling-
type SGD_ , this algorithm converges to a choice of
$\mathbb{E}\lvert\lvert\nabla F(\cdot;w)\rvert\rvert^{2}\leq\gamma$ with
$c=2/3$ whenever $\eta=\sqrt{\gamma}/(LG)$, for some (not necessarily convex)
function $F$. Note that $\gamma$ may be a stationary point, and that, for an
appropriate choice of loss function, $\gamma\propto\epsilon$.

###### Corollary 2

Assume Timaeus and Socrates are both piecewise-continuous, real-valued
functions with their output mapped consistently to $\\{0,1\\}$, and that the
rest of the assumptions for Theorem 5.3 hold. Also assume that train-
model$(\cdot,\cdot,\cdot)$ uses shuffling-type SGD as its optimizer.

If for every $\theta\in\Theta$ there exists a subset $\pi\subset\theta$ which
encodes the learning rate, batch size, and random seed for train-
model$(\cdot,\cdot,\cdot)$, and if the surrogate loss is is $L$-Lipschitz
smooth, bounded from below and where all gradients are stochastic and bounded
by some $G$, then Agora converges in

$\operatorname{O}\\!\left(\lvert\Theta\rvert^{2}\left(\log{\lvert\Theta\rvert}+\lvert\theta\rvert^{2}+\bar{f}\left(\lvert
E\rvert+\frac{\lvert
B\rvert}{(LG\zeta)^{2/3}}\right)\right)+\bar{S}\lvert\Theta\rvert\lvert
E\rvert\left(1-\frac{1}{2^{\lvert\Theta\rvert}}\right)\right)$ (37)

steps, where $B\subset D$, with $\lvert
B\rvert=\underset{\theta\in\Theta}{\text{max }}\\{\lvert B\rvert\in\theta\\}$
and $\zeta=\underset{\theta\in\Theta}{\text{min }}\\{\eta^{2}\in\theta\\}$.

###### Proof

The extra set of parameters in this case is the choice of learning rate
$\eta$, as well as the characterization of the batch $B\sim D$ with respect to
the state $s$ of some random number generator. Since our setting assumes that
$D$ is not $\epsilon$-representative of $\mathcal{P}$–at least not in the
first iteration–batch-based optimization methods will be sensitive to the
algorithm’s stochasticity. Let $\pi_{i}=\\{\eta_{i},s_{i},\lvert
B\rvert_{i}\\}$, and note that every combination of elements of $\pi_{i}$
guarantees an $\epsilon_{i}$-accurate solution (w.p.1) in polynomial time
under the assumptions given. The unknown $\epsilon_{i}$ is fully characterized
by $\pi_{i}$ and, by definition, the rest of the hyperparameters from
$\theta_{i}$.

It follows that constructiong a hyperparameter set
$\theta_{i}^{\prime}=\theta_{i}\cup\pi_{i}$ will allow Agora to search over
$\pi_{i}$, and select the appropriate values based on $\epsilon_{i}$, hence
maintaining the invariants from Lines 10 and 20, which, by Lemma 5 and Theorem
5.3, ensure correctness.

The bound for Equation 37 is obtained by a simple substitution in Equation 29
of $T_{f}(D)$, coupled with the facts that train-
model$(f,B_{i},\theta_{i}^{\prime})$ with shuffling-type SGD runs in $O(\lvert
B\rvert_{i}\bar{f}/\epsilon_{i}^{2/3})$ steps, and that,
$\forall\pi_{i},\theta_{i},\epsilon_{j}$, train-model$(f,B_{i},\theta_{i})$
defines a surjection $\pi_{i}\cup\theta_{i}\mapsto\epsilon_{j}$,

Note that this result is not necessarily applicable to all machine learning
models, or all neural networks for that matter, as their convergence
conditions differ. Moreover, this makes the ratio from Corollary 1 more
dependent on the choice of $\Theta$, as neural networks, without accounting
for finite-precision computing, belong to hypothesis classes of infinite size.

###### Remark 3

Training Timaeus–especially when it is a neural network–may become
computationally costly, and dominate the other terms in the equation. Still,
the “wall clock” runtime of Agora can be improved by a factor of
$\lvert\Theta\rvert$, by parallelizing Line 7 across multiple nodes.

##  6 Concluding Remarks

We presented an algorithm to obtain models under low-resource and ill-posed
settings. Our analysis of Agora shows that this procedure is able to generate
a dataset that is provably a part of the underlying distribution, and thus
return an optimal solution by making the problem easier to learn–all while
maintaining generalizability.

The runtime of this algorithm can be improved algebraically by employing a
generalized suffix tree in the longest common substring search part of the
procedure. Most practical problems have a near-negligible runtime dependency
with respect to this step, since, as mentioned, the training procedure
signifies the largest drain in terms of computational steps and tends to
dominate the other quantities. On the other hand, although Agora’s intended
use is to simplify the training of smaller models, it can be seen from Lemma 4
that this algorithm can be used to improve the performance of any model.
Indeed, Theorem 5.3 shows a linear dependency of the runtime of Agora with
respect to the steps needed to perform inference on both Timaeus and Socrates,
and hence it performs better when the time needed to train the former is
minimized.

By design, our setup focused on binary classifiers, but the results from this
work can easily be extended to multi-class classification problems by reducing
membership of each class to a binary classification problem, and breaking ties
arbitrarily and consistently. The correctness analysis would vary slightly, as
the VC dimension, which is an integral part of our proofs, is defined only
over binary classification problems.

Another central part of our correctness results is the assumption that the
support lies on or around a manifold. This is a fairly strong
constraint–perhaps even unrealistic. Yet, the work by Genovese et al. (2014)
focused on the existence of density ridges, as opposed to a fully-fledged
manifold, and showed that a well-defined ridge can be topologically similar,
in a certain sense, to such a manifold. Similar to Niyogi et al. (2008), this
result is also resilient to noise from the sampling procedure, and indeed
appears to be a stronger basis from which to analyze the behavior of the
$\tau$-function. Nonetheless, unless the support fulfills the density
requirements from this paper, this algorithm–like all manifold learning
methods–are not guaranteed to yield good results within a practical timeframe.
On the other hand, density can be achieved by a dimensionality reduction step.
This has the benefit of re-establishing the performance bounds under smaller
constants, at the cost of some preprocessing overhead.

Finally, we would like to point out that Agora is not optimal for all possible
hypothesis classes, and its convergence and runtime properties rely on
assumptions that may or may not hold in realistic scenarios. Nevertheless
certain models are remarkably robust to ill-posed problems (e.g., deep neural
networks). A derivative of this algorithm that maintains the invariances from
the $\tau$-function in tandem with better rules for hyperparameter pruning
would, without a doubt, present even better convergence and generalizability
guarantees.

## Acknowledgments

To my grandfather.

## References

  * Alon et al. (1997) Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. 1997.  Scale-sensitive dimensions, uniform convergence, and learnability.  _J. ACM_ , 44(4):615–631.
  * Angluin (2001) Dana Angluin. 2001.  Queries revisited.  In _Proceedings of the 12th International Conference on Algorithmic Learning Theory_ , ALT ’01, page 12–31, Berlin, Heidelberg. Springer-Verlag.
  * Balasubramanian et al. (2009) Vineeth Balasubramanian, Shayok Chakraborty, and Sethuraman Panchanathan. 2009\.  Generalized query by transduction for online active learning.  In _2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops_ , pages 1378–1385.
  * Balcan et al. (2010) Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. 2010.  The true sample complexity of active learning.  _Machine Learning_ , 80(2):111–139.
  * Bartlett et al. (2006) Peter L. Bartlett, Michael I. Jordan, and Jon D. Mcauliffe. 2006.  Convexity, classification, and risk bounds.  _Journal of the American Statistical Association_ , 101(473):138–156.
  * Bucilu et al. (2006) Cristian Bucilu, Rich Caruana, and Alexandru Niculescu-Mizil. 2006.  Model compression.  In _Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 535–541.
  * Chazal et al. (2006) Frédéric Chazal, David Cohen-Steiner, and André Lieutier. 2006.  A sampling theory for compact sets in euclidean space.  In _Proceedings of the Twenty-Second Annual Symposium on Computational Geometry_ , SCG ’06, page 319–326, New York, NY, USA. Association for Computing Machinery.
  * Chazal et al. (2017a) Frédéric Chazal, David Cohen-Steiner, André Lieutier, Quentin Mérigot, and Boris Thibert. 2017a.  Inference of curvature using tubular neighborhoods.  In _Modern Approaches to Discrete Curvature_ , volume 2184 of _Lecture Notes in Mathematics_. Springer, Cham.
  * Chazal et al. (2017b) Frédéric Chazal, Brittany Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, Alessandro Rinaldo, and Larry Wasserman. 2017b.  Robust topological inference: Distance to a measure and kernel distance.  _J. Mach. Learn. Res._ , 18(1):5845–5884.
  * Daniely (2016) Amit Daniely. 2016.  Complexity theoretic limitations on learning halfspaces.  In _Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’16, page 105–117, New York, NY, USA. Association for Computing Machinery.
  * Dao et al. (2018) Tri Dao, Albert Gu, Alexander J. Ratner, Virginia Smith, Christopher De Sa, and Christopher Ré. 2018.  A kernel theory of modern data augmentation.  _CoRR_ , abs/1803.06084.
  * Dundar et al. (2007) Murat Dundar, Balaji Krishnapuram, Jinbo Bi, and R. Bharat Rao. 2007.  Learning classifiers when the training data is not iid.  In _Proceedings of the 20th International Joint Conference on Artifical Intelligence_ , IJCAI’07, page 756–761, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
  * Federer (1959) Herbert Federer. 1959.  Curvature measures.  _Transactions of the American Mathematical Society_ , 93:418–491.
  * Genovese et al. (2014) Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman. 2014.  Nonparametric ridge estimation.  _The Annals of Statistics_ , 42(4):1511–1545.
  * Graham (2014) Benjamin Graham. 2014.  Fractional max-pooling.  _CoRR_ , abs/1412.6071.
  * Hampel (1998) Frank Hampel. 1998.  Is statistics too difficult?  _The Canadian Journal of Statistics / La Revue Canadienne de Statistique_ , 26(3):497–513.
  * Hanneke (2009) Steve Hanneke. 2009.  _Theoretical Foundations of Active Learning_.  Ph.D. thesis, USA.
  * Hanneke (2016) Steve Hanneke. 2016.  The optimal sample complexity of pac learning.  _Journal of Machine Learning Research_ , 17(1):1319–1333.
  * Haussler (1995) David Haussler. 1995.  Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenkis dimension.  _J. Comb. Theory Ser. A_ , 69(2):217–232.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeffrey Dean. 2015.  Distilling the knowledge in a neural network.  In _NIPS Deep Learning and Representation Learning Workshop_.
  * Ho et al. (2019) Daniel Ho, Eric Liang, Ion Stoica, Pieter Abbeel, and Xi Chen. 2019.  Population based augmentation: Efficient learning of augmentation policy schedules.  In _ICML_.
  * Hsieh et al. (2020) Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip B Gibbons. 2020.  The non-iid data quagmire of decentralized machine learning.  In _International Conference on Machine Learning (ICML 2020)_.
  * Kawaguchi et al. (2017) Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. 2017.  Generalization in deep learning.  _arXiv preprint arXiv:1710.05468_.
  * Kearns (1998) Michael Kearns. 1998.  Efficient noise-tolerant learning from statistical queries.  _J. ACM_ , 45(6):983–1006.
  * Kearns and Valiant (1994) Michael Kearns and Leslie Valiant. 1994.  Cryptographic limitations on learning boolean formulae and finite automata.  _J. ACM_ , 41(1):67–95.
  * Klivans and Sherstov (2006) Adam R. Klivans and Alexander A. Sherstov. 2006.  Cryptographic hardness for learning intersections of halfspaces.  In _Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science_ , FOCS ’06, page 553–562, USA. IEEE Computer Society.
  * Lin et al. (2013) Min Lin, Qiang Chen, and Shuicheng Yan. 2013.  Network in network.  _arXiv preprint arXiv:1312.4400_.
  * Littlestone (1988) Nick Littlestone. 1988.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Machine Learning_ , 2(4):285–318.
  * Livni et al. (2014) Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. 2014.  On the computational efficiency of training neural networks.  In _Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1_ , NIPS’14, page 855–863, Cambridge, MA, USA. MIT Press.
  * Markov (1958) Andrei Markov. 1958.  The insolubility of the problem of homeomorphy.  _Dokl. Akad. Nauk SSSR_ , 121:218–220.
  * Mohri et al. (2012) Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. 2012.  _Foundations of Machine Learning_.  The MIT Press.
  * Nguyen et al. (2020) Lam M. Nguyen, Quoc Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, and Marten van Dijk. 2020.  A unified convergence analysis for shuffling-type gradient methods.
  * Nguyen et al. (2009) XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. 2009.  On surrogate loss functions and f-divergences.  _The Annals of Statistics_ , 37(2):876–904.
  * Niyogi et al. (2008) Partha Niyogi, Stephen Smale, and Shmuel Weinberger. 2008.  Finding the homology of submanifolds with high confidence from random samples.  _Discrete Comput. Geom._ , 39(1):419–441.
  * Niyogi et al. (2011) Partha Niyogi, Stephen Smale, and Shmuel Weinberger. 2011.  A topological view of unsupervised learning from noisy data.  _SIAM J. Comput._ , 40(3):646–663.
  * Oliver et al. (2018) Avital Oliver, Augustus Odena, Colin A Raffel, Ekin Dogus Cubuk, and Ian Goodfellow. 2018.  Realistic evaluation of deep semi-supervised learning algorithms.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31_ , pages 3235–3246. Curran Associates, Inc.
  * Ratner et al. (2017) Alexander J. Ratner, Henry R. Ehrenberg, Zeshan Hussain, Jared Dunnmon, and Christopher Ré. 2017.  Learning to compose domain-specific transformations for data augmentation.
  * Reddi et al. (2018) Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. 2018.  On the convergence of adam and beyond.  In _International Conference on Learning Representations_.
  * Sener and Savarese (2018) Ozan Sener and Silvio Savarese. 2018.  Active learning for convolutional neural networks: A core-set approach.  In _International Conference on Learning Representations_.
  * Settles (2012) Burr Settles. 2012.  _Active Learning_.  Morgan & Claypool.
  * Shalev-Shwartz (2012) Shai Shalev-Shwartz. 2012.  _Online Learning and Online Convex Optimization_.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David. 2014.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press.
  * Valiant (1984) Leslie G. Valiant. 1984.  A theory of the learnable.  _Commun. ACM_ , 27(11):1134–1142.
  * Wasserman (2018) Larry Wasserman. 2018.  Topological data analysis.  _Annual Review of Statistics and Its Application_ , 5(1):501–532.
  * Weinberger (2011) Shmuel Weinberger. 2011.  What is … persistent homology?  _Notices of the American Mathematical Society_ , 58:36––39.
  * Wu et al. (2020) Sen Wu, Hongyang R. Zhang, Gregory Valiant, and Christopher Ré. 2020.  On the generalization effects of linear transformations in data augmentation.
  * Zhang et al. (2019) Xinyu Zhang, Qiang Wang, Jian Zhang, and Zhao Zhong. 2019.  Adversarial autoaugment.

## Appendices

##  Appendix 0.A Proof of Lemma 1

####  “If” direction:

We show that an open set $U=\cup_{x_{i}\in D}\mathcal{B}_{\rho}(x_{i})$ that
has the same homology as $\mathcal{X}$ is $\epsilon$-representative of
$\mathcal{P}$, and that Equation 3 holds when the conditions for the lemma are
met.

Fix an arbitrary confidence $0<\delta\leq 1/2$. Then, from Theorem 5.1 the
minimum sample size $\lvert D\rvert$ needed to construct such a set $U$ with
probability greater than $1-\delta$ has to be at least

$\lvert D\rvert>\beta(\rho/4)\left(\ln{\beta(\rho/8)}+\ln{(1/\delta)}\right),$
(38)

for
$\beta(\rho)=\frac{\operatorname{vol}{(\mathcal{\mathcal{X}})}}{\cos^{m}{(\arcsin{(\frac{\rho}{2\mu})})}\operatorname{vol}{(\mathcal{B}^{m}_{\rho})}}$,
and where $\mu$ is the condition number, $\text{dim}(\mathcal{X})=m$, and
$\rho$ the radius $0<\rho<\mu/2$ of the $m$-balls covering $\mathcal{X}$.

On the other hand, Hanneke (2016) showed that the minimum sample size needed
for Equation 3 to hold with probability at least $1-\delta$ is given by

$\lvert D\rvert\geq c\left(\frac{d+\log{(1/\delta)}}{\epsilon^{2}}\right)$
(39)

for some constant $c$ and $0<\epsilon,\delta\leq 1/2$. This bound is tight,
but we are only concerned with the lower bound.

Assume $\lvert D\rvert$ satisfies Equation 38. Then there is an assignment of
$\beta(\rho)$ that allows Equation 39 to hold. Solving Equation 39 for
$\beta(\rho)$ with the ansatz:

$\displaystyle\epsilon$ $\displaystyle=\sqrt{\frac{c}{\beta(\rho/4)}},$ (40)
$\displaystyle d$ $\displaystyle=c^{\prime}\log{\beta(\rho/8)},$ (41)

where $c^{\prime}=\ln{(2)}$, yields:

$\displaystyle\epsilon$
$\displaystyle=\sqrt{c}\left(\frac{\cos^{m}{(\arcsin{(\frac{\rho}{8\mu}))}}\operatorname{vol}{(\mathcal{B}^{m}_{\rho/4})}}{\operatorname{vol}{(\mathcal{\mathcal{X}})}}\right)^{1/2},$
(42) $\displaystyle d$
$\displaystyle=c^{\prime}\log{\left(\frac{\operatorname{vol}{(\mathcal{\mathcal{X}})}}{\cos^{m}{(\arcsin{(\frac{\rho}{16\mu}))}}\operatorname{vol}{(\mathcal{B}^{m}_{\rho/8})}}\right)}.$
(43)

We can refine this result, and obtain the same as Equations 11 and 12 by
noting that the volume $\operatorname{vol}{(\mathcal{B}^{m}_{\rho})}$ is given
in the $m$-dimensional ambient space, which is Euclidean and equipped with the
canonical Euclidean metric, and that $\Gamma(\frac{x}{2}+1)=(x/2)!$:

$\displaystyle\epsilon$
$\displaystyle=\sqrt{c}\left(\frac{\cos^{m}{(\arcsin{(\frac{\rho}{8\mu})})}\pi^{m/2}\left(\frac{\rho}{4}\right)^{m}}{(\frac{m}{2})!\operatorname{vol}{(\mathcal{\mathcal{X}})}}\right)^{1/2},$
(44) $\displaystyle d$
$\displaystyle=c^{\prime}\log{\left(\frac{\operatorname{vol}{(\mathcal{\mathcal{X}})}(\frac{m}{2})!}{\cos^{m}{(\arcsin{(\frac{\rho}{16\mu}))}}\pi^{m/2}\left(\frac{\rho}{8}\right)^{m}}\right)}.$
(45)

Letting
$\Lambda_{\rho}=\left(\frac{\rho\sqrt{\pi}}{4}\right)\left(1-\frac{\rho^{2}}{64\mu^{2}}\right)^{1/2}$,
we obtain

$\displaystyle\epsilon$
$\displaystyle\in\operatorname{\Omega}\\!\left(\left(\frac{\Lambda_{\rho}^{m}}{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}\right)^{1/2}\right)$
(46) $\displaystyle d$
$\displaystyle\in\operatorname{\Omega}\\!\left(\log{\left(2^{m}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{m/2}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\Lambda_{\rho}^{m}}\right)}\right)$
(47)

as desired. It follows that, when the homology of $\cup_{x_{i}\in
D}\mathcal{B}_{\rho}(x_{i})$ equals the homology of $\mathcal{X}$, $D$ is
$\epsilon$-learnable, if $\epsilon$ and $d$ satisfy Equations 11 and 12.

####  “Only if” direction:

We show that a dataset that is $\epsilon$-representative of $\mathcal{P}$ with
its size determined by Equations 11 and 12 and Equation 39 has the same
homology as $\mathcal{X}$.

Fix an arbitrary confidence $0<\delta\leq 1/2$. Assume there exists an
assignment of $\epsilon$ and $d$ that satisfies Equation 39, such that $D$ is
$\epsilon$-representative of $\mathcal{P}$ under these conditions. Then

$\displaystyle\lvert D\rvert$
$\displaystyle>c\left(\frac{c^{\prime}\log{\left(2^{m}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{m/2}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\Lambda_{\rho}^{m}}\right)}+\log{\frac{1}{\delta}}}{c_{\epsilon}\left(\frac{\Lambda_{\rho}^{m}}{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}\right)}\right)$
(48)

for some positive, nonzero constants $c\geq\ln{(2)}$,
$\log{c^{\prime}}=c_{d}\geq 1/8$, and ${c_{\epsilon}}\geq 1$ encoding the
respective constants for Equations 11 and 12.

From the derivation of Equation 38 by Niyogi et al. (2008) we know that the
confidence $\delta$ is lower-bounded by the $\rho/4$-packing number $z$, times
the minimum probability $1-\alpha$ that the intersection of the cover with a
nontrivial subset $F\subset D$, $\lvert F\rvert<\lvert D\rvert$ is empty, that
is:

$z(1-\alpha)^{\lvert F\rvert}\leq ze^{-\lvert F\rvert\alpha}\leq\delta$ (49)

for $\alpha=\underset{x_{i}\in F}{\text{min
}}\operatorname{vol}{(\mathcal{B}_{\rho/4}(x_{i})\cap\mathcal{X})}/\operatorname{vol}{(\mathcal{X})}$.
Crucially, if $\lvert F\rvert$ is larger than a carefully-chosen lower bound,
it follows that the homology of a cover of $F$ equals the homology of
$\mathcal{X}$. From the same work we know that $\alpha$ and $z$ are invariants
of the manifold, and are unrelated to the dataset itself. In particular,

$\displaystyle\frac{1}{\alpha}$
$\displaystyle\leq\frac{\operatorname{vol}{(\mathcal{X})}}{\cos^{m}{(\arcsin{(\frac{\rho}{8\mu})})}\operatorname{vol}{(\mathcal{B}_{\rho/4})}},$
(50) $\displaystyle z$
$\displaystyle\leq\frac{\operatorname{vol}{(\mathcal{X})}}{\cos^{m}{(\arcsin{(\frac{\rho}{16\mu})})}\operatorname{vol}{(\mathcal{B}_{\rho/8})}}.$
(51)

Solving for $\lvert F\rvert$ in Equation 49, we obtain:

$\lvert F\rvert\geq\frac{1}{\alpha}\ln{\frac{z}{\delta}},$ (52)

which is precisely the statement from Equation 38. Plugging in Equation 48 in
Equation 49, along with the fact that $\lvert D\rvert\geq\lvert F\rvert$, it
follows that:

$\frac{1}{\alpha}\ln{\frac{z}{\delta}}\leq
c\left(\frac{\log{\left(c_{d}2^{m}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{m/2}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\Lambda_{\rho}^{m}}\right)}+\log{\frac{1}{\delta}}}{\left(c_{\epsilon}\frac{\Lambda_{\rho}^{m}}{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}\right)}\right)$
(53)
$\leq\left(\frac{c}{\ln{(2)}}\right)\left(c_{\epsilon}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\Lambda_{\rho}^{m}}\right)\ln{\left(c_{d}2^{m}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{m/2}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\delta\Lambda_{\rho}^{m}}\right)}.$
(54)

Our work is limited to show variable-per-variable bounds. Note, however, that
from Equations 50 and 51 we do not obtain any information with respect to the
relationship of these bounds and the ones from Equations 11 and 12. Thus the
best we can do expect that the bounds from Equations 50 and 51 are at least a
lower bound for Equations 11 and 12:

$\displaystyle z$ $\displaystyle\leq
c_{d}2^{m}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{m/2}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\Lambda_{\rho}^{m}}$
(55)
$\displaystyle\frac{\operatorname{vol}{(\mathcal{X})}}{\cos^{m}{(\arcsin{(\frac{\rho}{16\mu})})}\operatorname{vol}{(\mathcal{B}_{\rho/8})}}$
$\displaystyle\leq
c_{d}2^{m}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{m/2}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\Lambda_{\rho}^{m}}$
(56)
$\displaystyle\frac{\operatorname{vol}{(\mathcal{X})}}{\cos^{m}{(\arcsin{(\frac{\rho}{16\mu})})}\operatorname{vol}{(\mathcal{B}_{\rho/8})}}$
$\displaystyle\leq
c_{d}2^{m}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{m/2}\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\left(\frac{\rho\sqrt{\pi}}{4}\right)^{m}\left(1-\frac{\rho^{2}}{64\mu^{2}}\right)^{m/2}}.$
(57)

We can drop the dependence on the volume of the manifold, and recall that
$\operatorname{vol}{(\mathcal{B}_{\rho/8})}$ is defined over the tangent
space, which is Euclidean.101010 This last assumption is not necessary, given
that the definition of the lower bound of $d$ in Equation 12 implies a
constant $c_{d}$ which can be made arbitrarily large with respect to the
volume form of $\mathcal{B}_{\rho/8}$ on a chosen (oriented) manifold. Using
this, along with the fact that $\cos{(\arcsin{(x)})}=\sqrt{1-x^{2}}$, we
obtain:

$\displaystyle\frac{1}{\cos{(\arcsin{(\frac{\rho}{16\mu})})}}$
$\displaystyle\leq
c_{d}\left(\frac{64-\rho^{2}/\mu^{2}}{256-\rho^{2}/\mu^{2}}\right)^{1/2}\left(1-\frac{\rho^{2}}{64\mu^{2}}\right)^{-1/2},$
(58) $\displaystyle 1$ $\displaystyle\leq 8(c_{d}),$ (59)

which is true by the definition of $c_{d}$.

Similarly, for $\alpha$, we obtain another inequality:

$\displaystyle\frac{1}{\alpha}$ $\displaystyle\leq
c_{\epsilon}\left(\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\Lambda_{\rho}^{m}}\right)$
(61)
$\displaystyle\frac{\operatorname{vol}{(\mathcal{X})}}{\cos^{m}{(\arcsin{(\frac{\rho}{8\mu})})}\operatorname{vol}{(\mathcal{B}_{\rho/4})}}$
$\displaystyle\leq
c_{\epsilon}\left(\frac{(\frac{m}{2})!\operatorname{vol}{(\mathcal{X})}}{\left(\frac{\rho\sqrt{\pi}}{4}\right)^{m}\left(1-\frac{\rho^{2}}{64\mu^{2}}\right)^{m/2}}\right)$
(62)
$\displaystyle\frac{1}{\cos^{m}{\left(\arcsin{(\frac{\rho}{8\mu})}\right)}}$
$\displaystyle\leq
c_{\epsilon}\left(1-\frac{\rho^{2}}{64\mu^{2}}\right)^{-m/2}$ (63)
$\displaystyle 1$ $\displaystyle\leq c_{\epsilon},$ (64)

which is true by the definition of $c_{\epsilon}$.

It follows that if $D$ satisfies Equation 39 with Equations 11 and 12 and
$c\geq\ln{(2)}$, the homology of $\cup_{x_{i}\in D}\mathcal{B}_{\rho}(x_{i})$
equals the homology of $\mathcal{X}$.

#### Conclusion:

From both parts it follows that $D$ is $\epsilon$-learnable if and only if the
homology of a cover for $\mathcal{X}$ with elements of $D$, $\cup_{x_{i}\in
D}\mathcal{B}_{\rho}(x_{i})$, equals the homology of $\mathcal{X}$, as long as
$\epsilon$ and $d$ satisfy Equations 11 and 12. This concludes the proof.

###### Remark 4

A consequence of the second part of the proof of Lemma 1 is that the Big Omega
notation can be substituted with an inequality.

##  Appendix 0.B Proof of Lemma 3

By Lemma 2, we know that a dataset is $\epsilon$-representative if (and only
if) an open cover of the dataset has the same homology as the support from
which it was drawn. We can then prove Lemma 3 by showing that an open cover
$\cup_{x_{i}\in\tilde{E}^{(\kappa)}}\mathcal{B}_{\rho}(x_{i})$ of
$\tilde{E}^{(\kappa)}$ has the same homology as a respective cover
$\cup_{x_{i}\in E}\mathcal{B}_{\rho}(x_{i})$ of $E$ via Theorem 5.1, and then
leverage Lemma 2 to state that such a dataset is $\epsilon$-representative of
$\mathcal{P}$. We begin by arguing that building said cover is possible, and
then proceed to establish bounds on $\kappa$.

Fix an arbitrary probability $0<\delta\leq 1/2$.

It is possible to build a $\rho/4$-cover of $\mathcal{X}$ by sampling
$\tau_{\rho}(\cdot)$, even though the codomain of the $\tau$-function excludes
the center of the sphere: since $E$ is $\epsilon$-representative of
$\mathcal{P}$, from Lemma 2 we know that the open cover $\cup_{x_{i}\in
E}\mathcal{B}_{\rho}(x_{i})$ has the same homology as $\mathcal{X}$, and so
$E$ is $\rho/2$-dense on $\mathcal{X}$.

Then there exists at least one $\tilde{x}_{i}\in X$ on every
$\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\}$, such that it is possible to
construct a $\rho/4$-cover $V=\cup_{i=1}^{\lvert
E\rvert}\mathcal{B}_{\rho/4}(\tilde{x}_{i})$ of a manifold on which
$X\setminus E$ lies. Hence such a cover is also a $\rho/4$-cover for
$\mathcal{X}$. The second condition for $\tilde{E}^{(\kappa)}$, that the
elements are not repeated from $E$, holds because of the constraint $\lvert
E\cup\Delta\rvert\leq c\lvert X\rvert$. Given that $E$ was sampled i.i.d. from
$\mathcal{P}$, it is hence possible to sample $\kappa$ times from every
$m$-ball a point that, with probability at most $1/c$, is not in $E$.

We now establish the bounds around $\kappa$ for which this holds by a use of
the union bound on a nonempty $\Delta$, and remark that the case for
$\Delta=\emptyset$ follows from this result.

When $\Delta\neq\emptyset$, a sampled $\tilde{x}_{i}$ might not belong to $X$,
but, by Lemma 2, the cover realized by some subset
$F\subset\tilde{E}^{(\kappa)}$, $\cup_{\tilde{x}_{i}\in
F}\mathcal{B}_{\rho/4}(\tilde{x}_{i})$, will have the same homology as the
homology of $\mathcal{X}$ as long as $\lvert F\rvert\geq\lvert E\rvert$ and
$F\subset X$. To see this, note that if all the points corresponding to
$Z=X\cup\Delta$ lie on some manifold $\mathcal{M}$, then there exists a map
that can construct a submanifold $\mathcal{X}$ of $\mathcal{M}$ containing
only elements of $X$ (resp. $\Delta$); hence a cover for $\mathcal{M}$ will be
a cover for $\mathcal{X}$, but a cover for $\mathcal{X}$ will not necessarily
be a cover for $\Delta$. It follows that, since we only sample elements within
a radius $\rho/4$ of a valid element from $X$, any cover constructed in such a
way will be a cover for $\mathcal{X}$, and thus the homology of a cover
realized by $F\subset\tilde{E}^{(\kappa)}$ equals the homology of
$\mathcal{X}$.

It then suffices to establish the number of tries $\kappa$ needed to obtain
the centers for said cover. For this we rely on the fact that there are two
natural partitions of $\tilde{E}^{(\kappa)}$: one corresponding to the results
of every sampling round, as displayed in Equation 13; and another mapping the
index of every $i^{\text{th}}$ element of $E$ to a set tabulating the result
of the $j^{\text{th}}$ sampling with $\tau_{\rho}(\cdot)$. Partition
$\tilde{E}^{(\kappa)}$ based on the latter strategy, that is,
$\tilde{E}^{(i)}=\\{\tau_{\rho}(x_{i})^{(j)}\colon x_{i}\in E\land
j\in[1,\dots,\kappa]\\}$, for $\tilde{E}^{(i)}\subset\tilde{E}^{(\kappa)}$.
Let $A_{i}$ be the event that the $i^{\text{th}}$ subset of
$\tilde{E}^{(\kappa)}$ under this partition contains solely elements of $E$;
that is, $A_{i}=\text{Pr}[\tilde{E}^{(i)}\cap E\neq\emptyset]$.

Via the union bound, we get:

$\displaystyle\text{Pr}\left[\bigcup_{i=1}^{\lvert E\rvert}[A_{i}=1]\right]$
$\displaystyle\leq\sum_{i}^{\lvert E\rvert}\text{Pr}[A_{i}=1],$ (65)
$\displaystyle\leq\sum_{i}^{\lvert
E\rvert}\prod_{j=1}^{\kappa}\left(1-\frac{\operatorname{vol}({(Z\setminus
E)\cap(\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\})})}{\operatorname{vol}{(Z\cap(\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\}))}}\right)$
(66) $\displaystyle\leq\sum_{i}^{\lvert
E\rvert}\left(1-\frac{\operatorname{vol}({(Z\setminus
E)\cap(\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\})})}{\operatorname{vol}{(Z\cap(\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\}))}}\right)^{\kappa},$
(67)

since all elements in $\mathcal{Q}_{x_{i},\rho}$ are equally probable. Let

$\alpha=\underset{i\in\\{1,\dots,\lvert E\rvert\\}}{\text{min
}}\frac{\operatorname{vol}({(Z\setminus
E)\cap(\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\})})}{\operatorname{vol}{(Z\cap(\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\}))}}.$
(68)

By again relying on the $\rho/2$-density of $E$ on $\mathcal{X}$, we can see
that $\alpha>0$; more importantly, we can observe that the relevant (that is,
inside the cover realized by $E$) subspace of $\mathcal{M}$ has the same
condition number as $\mathcal{X}$, and relax the geometry of this problem. We
then lower bound Equation 68 with a counting argument: since $\tilde{x}_{i}$
is obtained i.i.d. from $Z$ with a uniform probability distribution, we can
assume that every draw for every $\mathcal{B}_{\rho/4}(x_{i})$ is identical,
at least with respect to $Z$. Indeed, remark that all $x_{i}\in E$ were also
sampled in an i.i.d. fashion. Furthermore, we can drop the dependence on the
volume of $\mathcal{B}_{\rho/4}(x_{i})$ by noting that we do not need to
sample elements strictly from $X$. From the constraint $\lvert
E\cup\Delta\rvert\leq c\lvert X\rvert$, then $\lvert Z\rvert=\lvert
X\rvert+\lvert\Delta\rvert$, and $\lvert E\rvert\leq c\lvert
X\rvert-\lvert\Delta\rvert$.

Putting it all together, we obtain:

$\displaystyle\alpha$
$\displaystyle\geq\frac{\lvert\\{\tilde{x_{i}}\colon\tilde{x_{i}}\in(Z\setminus
E)\cap(\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\})\\}\rvert}{\lvert\\{\tilde{x_{i}}\colon\tilde{x_{i}}\in
Z\cap(\mathcal{B}_{\rho/4}(x_{i})\setminus\\{x_{i}\\}\\})\rvert}$ (69)
$\displaystyle\alpha$ $\displaystyle\geq\frac{\lvert Z\setminus
E\rvert}{\lvert Z\rvert}$ (70) $\displaystyle\alpha$
$\displaystyle\geq\frac{\lvert X\rvert(1-c)+2\lvert\Delta\rvert}{\lvert
X\rvert+\lvert\Delta\rvert}$ (71)

Following Niyogi et al. (2008) we can simplify Equation 71 to

$\text{Pr}\left[\bigcup_{i=1}^{\lvert E\rvert}[A_{i}=1]\right]\leq\lvert
E\rvert\left(1-\alpha\right)^{\kappa}\leq\lvert E\rvert
e^{-\kappa\alpha}\leq\delta,$ (72)

where we used the fact that $(1-\beta)\leq e^{\beta}$ for $\beta\geq 0$.
Choose $\kappa$ to be

$\displaystyle\kappa$ $\displaystyle\geq\frac{1}{\alpha}\left(\ln{\lvert
E\rvert}+\ln{(1/\delta)}\right)$ (73) $\displaystyle\kappa$
$\displaystyle\geq\left(\frac{\lvert X\rvert+\lvert\Delta\rvert}{\lvert
X\rvert(1-c)+2\lvert\Delta\rvert}\right)\ln{\left(\frac{\lvert
E\rvert}{\delta}\right)}.$ (74)

From the above, whenever $\kappa$ is as specified in Equation 74,
$\tilde{E}^{(\kappa)}$ has a subset $F\subset\tilde{E}^{(\kappa)}$ that
realizes a cover of $\mathcal{X}$, and such that $\lvert F\rvert\geq\lvert
E\rvert$. It follows from this and from Theorem 5.1 that a cover of $F$ has
the same homology as $E$; by Lemma 2 we conclude that $\tilde{E}^{(\kappa)}$
is $\epsilon$-learnable.

###### Remark 5

It is possible to obtain a tighter bound on Equation 68 (and thus on Equation
74) by employing a geometric argument. We leave this question open for further
research.