# Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy
Regimes

Amir Hossein Saberi
Electrical Engineering Department,
Sharif University of Technology, Tehran, Iran
<EMAIL_ADDRESS>
&Amir Najafi
School of Mathematics, Institute for
Research in Fundamental Sciences (IPM),
Tehran, Iran
<EMAIL_ADDRESS>
&Seyed Abolfazl Motahari
Computer Engineering Department,
Sharif University of Technology, Tehran, Iran
<EMAIL_ADDRESS>
&Babak H. Khalaj
Electrical Engineering Department,
Sharif University of Technology, Tehran, Iran
<EMAIL_ADDRESS>
###### Abstract

In this paper, we propose a sample complexity bound for learning a simplex
from noisy samples. A dataset of size $n$ is given which includes i.i.d.
samples drawn from a uniform distribution over an unknown arbitrary simplex in
$\mathbb{R}^{K}$, where samples are assumed to be corrupted by an additive
Gaussian noise of an arbitrary magnitude. We propose a strategy which outputs
a simplex having, with high probability, a total variation distance of
$\epsilon+O\left(\mathrm{SNR}^{-1}\right)$ from the true simplex, for any
$\epsilon>0$. We prove that to arrive this close to the true simplex, it is
sufficient to have $n\geq\tilde{O}\left(K^{2}/\epsilon^{2}\right)$ samples.
Here, SNR stands for the signal-to-noise ratio which can be viewed as the
ratio of the diameter of the simplex to the standard deviation of the noise.
Our proofs are based on recent advancements in sample compression techniques,
which have already shown promises in deriving tight bounds for density
estimation in high-dimensional Gaussian mixture models.

##  1 Introduction

Many practical problems in machine learning and data science can be naturally
modeled by learning of high-dimensional geometric shapes from a given set of
data points. In particular, learning of simplices from sample points arises in
many fields ranging from bioinformatics to remote sensing [1, 2, 3]. A simplex
is defined as the set of all convex combinations of $K+1$ points in
$\mathbb{R}^{K}$, for $K\in\mathbb{N}$. Formally speaking, our problem can be
stated as follows: assume $n$ i.i.d. samples are drawn from a uniform measure
over an unknown simplex in $\mathbb{R}^{K}$. Also, each sample is assumed to
be corrupted by an additive zero-mean Gaussian noise with a known variance
$\sigma^{2}$. In this regard, the main question that we try to address in this
paper is: How large $n$ needs to be in terms of parameters such as $K$,
$\sigma$ and etc., such that the true simplex is approximated up to a
reasonable accuracy?

Learning of simplices is a well-studied task. Due to its practical importance,
many efficient algorithms are proposed that solve the problem in different
scenarios such as noisy and sparse cases. From a theoretical point of view,
however, the problem is less studied and fundamental results are not derived
for diverse situations that the problem may face. Several efficient algorithms
for learning of simplices are already proposed (see Section 1.1) which still
suffer from a very large sample complexity. In a concurrent line of work,
researchers have been working on deriving information-theoretic bounds on
sample complexity of the problem without putting any restrictions on the
efficiency of the corresponding algorithms. Recently, optimal sample
complexity bounds are derived for the noiseless case where Maximum Likelihood
Estimator (MLE) is used. The output of MLE for this problem is the minimum
volume simplex which contains all the samples. In [4], Najafi et al. proved
that MLE is a PAC-learning algorithm for finding a $K$-simplex with an
asymptotically decreasing Total Variation (TV) distance. They showed that a
maximum of $\tilde{O}\left(K^{2}/\epsilon\right)$111Logarithmic terms are
ignored. samples are sufficient to estimate the true simplex up to a TV
distance of $\epsilon$ for $\epsilon>0$. However, we do not have access to
noiseless data in real-world situations, and the minimum-volume inclusive
simplex solution no longer is a valid answer for the problem. In fact, in
noisy regimes the corrupted samples are not necessarily contained inside the
true simplex.

In this work, we aim at finding the information-theoretic sample complexity of
learning simplices in noisy regimes. Mathematically speaking, samples are
generated from the following equation:

$\boldsymbol{y}_{i}=\boldsymbol{V}\boldsymbol{\phi}_{i}+\boldsymbol{z}_{i}\quad,\quad
i=1,\ldots,n,$ (1)

where $\boldsymbol{V}$ is a $K\times(K+1)$ matrix that includes the vertices
of the simplex as its columns. Each $\boldsymbol{\phi}_{i}\in\mathbb{R}^{K}$
is drawn from a uniform Dirichlet distribution and
$\boldsymbol{z}_{i}\in\mathbb{R}^{K}$ are sampled from a multivariate Gaussian
distribution $\mathcal{N}\left(0,\sigma^{2}\boldsymbol{I}_{K}\right)$. We
tackle the task of estimating a noisy simplex as a density estimation problem.
In particular, we prove that having at most
$\tilde{O}\left(K^{2}/\epsilon^{2}\right)$ noisy samples from a $K$-simplex is
sufficient to estimate the simplex with a TV-distance of at most
$\epsilon+\frac{\sigma}{\mathrm{Vol}^{\frac{1}{K}}}$, for any $\epsilon>0$.

The algorithm that achieves this bound has three main steps. First, we find a
ball which with high probability contains the main simplex. Then, we quantize
this ball via covering it with many isolated points. Each combination of $K+1$
of such points forms a candidate simplex, and thus a candidate density to
approximate the true simplex. Assuming the covering has been done with a
sufficiently high precision, there exists at least one candidate that has a
small TV-distance from the main simplex. In the final step, we choose a
density from the candidate set such that, with high probability, it has a
small distance from the main simplex. It should be noted that our algorithm
does not run in polynomial-time, since our main goal is to find information-
theoretic bounds for the sample complexity. To the best of our knowledge, our
results are the first sample complexity bounds for this problem in noisy
regimes, regardless of the efficiency of the corresponding algorithms.

###  1.1 Related Works

We categorize the existing works based on their focus, which could be either
the efficiency of the proposed algorithms, or the fundamental sample
complexity of the problem. In the former, the main purpose is mostly to
provide a heuristic solution with promising results in practice. However,
papers in the latter category aim to find fundamental and information-
theoretic limitations for the problem. In the remainder of this part, we
review a number of works from both categories.

In [5], Anderson et al. proved that by having $O\left(K^{22}\right)$ noiseless
samples, they can estimate the true simplex via an efficient (polynomial-time)
algorithm. The core idea behind their work is to use the 3rd moment and local
search techniques from Independent Component Analysis (ICA). In [4], it is
shown that sample complexity of the MLE in noiseless case is
$\tilde{O}\left(K^{2}/\epsilon\right)$, where $\epsilon$ is the permissible
TV-distance of the output of the algorithm from the true simplex. They also
provide an alternative heuristic, yet efficient approach as a practical
surrogate to the MLE.

To the best of our knowledge, theoretical study of this problem in the noisy
setting is limited to the work of Bhattacharyya et al. [6]. Their main idea is
based on a notion named sample compression which is also used in a seminal
work from Ashtiani et al. [7] in learning high-dimensional Gaussian mixture
models. In [6], authors proved that a noisy simplex can be learned using
$O\left(K^{2}\right)$ samples, assuming that there exist a sample near each
vertex of the simplex. In fact, this is a very strong assumption, and a back
of the envelope calculation shows that one needs around
$\tilde{O}\left((1/\epsilon)^{K}\right)$ samples to guarantee the existence of
at least one sample within a distance of $\epsilon$ from any vertex. As
mentioned earlier, several heuristic methods have been introduced so far that
try to deal with real world problems in, for example, bioinformatics and
hyper-spectral imaging [8, 9, 10]. In hyper-spectral imaging, one aims finding
the distribution of the constituent elements in an area through examining its
remote hyper-spectral images. Each pixel in such an image can be thought as a
random convex combination of some fixed prototype vectors that correspond to
the pure elements of that region. The above assumptions turn the problem of
finding constituent minerals and their distribution in the field into
estimating an unknown simplex from presumable uniform samples [11, 12, 13].

Learning of simplices in bioinformatics usually arises in the study of complex
tissues. A complex tissue refers to a tissue composed of multiple cell-types
–a group of cells with similar characteristics– like blood, brain, pancreas
[14], or even tumor cells [15]. Bulk data from complex tissues, such as gene
expression vectors, can again be modeled by several convex combinations of its
constituent cell-types. In this line of work, researchers aim at finding the
structure of tissues through studying the state of cell-types, which naturally
translates into learning a high-dimensional simplex [16, 17].

The rest of the paper is organized as follows: In Section 2, we formally
define the problem and present our notation and definitions. Our main
theoretical results as well as the algorithm that achieves our bounds are
discussed in Section 3. Finally, Section 4 concludes the paper and presents
some suggestions for future works.

##  2 Notation and Definitions

As mentioned before, a $K$-simplex is defined as the set of all convex
combination of $K+1$ affinely independent points in $\mathbb{R}^{K}$. Let
$\boldsymbol{V}=\left[\boldsymbol{v}_{0}|\boldsymbol{v}_{1}|\cdots|\boldsymbol{v}_{k}\right]\in\mathbb{R}^{K\times(K+1)}$
be a matrix whose columns are such points, then $K$-simplex $\mathcal{S}$ can
be defined as follow:

$\mathcal{S}=\left\\{\boldsymbol{V}\boldsymbol{\phi}\bigg{|}~{}\boldsymbol{\phi}\in\mathbb{R}^{K+1},~{}\boldsymbol{\phi}\succ\boldsymbol{0},~{}\boldsymbol{\phi}^{T}\boldsymbol{1}=1\right\\}.$

Here $\boldsymbol{v}_{i}$ denotes the $i$th vertex of the simplex. Also, let
us denote the set of all possible $K$-simplices in $\mathbb{R}^{K}$ by
$\mathbb{S}_{K}$. We show the uniform probability measure over a simplex
$\mathcal{S}$ by $\mathbb{P}_{\mathcal{S}}$, and its probability density
function by $f_{\mathcal{S}}\left(x\right)$. Thus,
$f_{\mathcal{S}}\left(x\right)$ can be written as:

$f_{\mathcal{S}}\left(x\right)=\frac{\boldsymbol{1}\left(\boldsymbol{x}\in\mathcal{S}\right)}{\mathrm{Vol}\left(\mathcal{S}\right)},$

where $\mathrm{Vol}\left(\mathcal{S}\right)$ denotes the Lebesgue measure (or
simple, the volume) of $\mathcal{S}$.

In order to measure the difference between two distributions, we use the total
variation distance. Consider two probability measures $\mathbb{P}_{1}$ and
$\mathbb{P}_{2}$, with respective density functions $f_{1}$ and $f_{2}$, which
are defined over $\mathbb{R}^{K}$. Then, TV distance between $\mathbb{P}_{1}$
and $\mathbb{P}_{2}$ can be defined as

$\operatorname{TV}(\mathbb{P}_{1},\mathbb{P}_{2})\triangleq\sup_{\mathrm{A}\in\mathcal{B}}{|\mathbb{P}_{1}\left(\mathrm{A}\right)-\mathbb{P}_{2}\left(\mathrm{A}\right)|}=\frac{1}{2}\|f_{1}-f_{2}\|_{1}=\frac{1}{2}\int_{\mathbb{R}^{K}}\\!|f_{1}(x)-f_{2}(x)|\,\mathrm{d}x,$

where $\mathcal{B}$ is the set of all Borel sets in $\mathbb{R}^{K}$.

######  Definition 1 (PAC-Learnability of a distribution class in realizable
setting).

We say a class of distributions $\mathcal{F}$ is PAC learnable in realizable
setting, if there exists a learning method which for any distribution
$g\in\mathcal{F}$ and any $\epsilon,\delta>0$, outputs an estimator $\hat{g}$
using $n\geq\mathrm{poly}\left(1/\epsilon,1/\delta\right)$ i.i.d. samples from
$g$, which with probability at least $1-\delta$ satisfies

$\|\hat{g}-g\|_{\mathrm{TV}}<\epsilon.$ (2)

######  Definition 2 (PAC-Learnability of a distribution class in agnostic
setting).

We say a class of distributions $\mathcal{F}$ is PAC learnable in agnostic
setting, if there exists a learning method which for any distribution $g$ (not
necessarily in $\mathcal{F}$) and any $\epsilon,\delta>0$, outputs an
estimator $\hat{g}$ using $n\geq\mathrm{poly}\left(1/\epsilon,1/\delta\right)$
i.i.d. samples from $g$, which with probability at least $1-\delta$ satisfies

$\|\hat{g}-g\|_{\mathrm{TV}}<C\cdot\min_{f\in\mathcal{F}}\|{f}-g\|_{\mathrm{TV}}+\epsilon.$

######  Definition 3 (Agnostic PAC-Learnability of Simplices).

Recall that for any $K$-simplex $\mathcal{S}$ in $\mathbb{R}^{K}$, we define
the uniform measure $\mathbb{P}_{S}$ over $\mathcal{S}$. We say algorithm
$\mathcal{A}$, which takes a sample set as input and outputs a simplex
$\mathcal{S}_{\mathcal{A}}\in\mathbb{S}_{K}$, is an agnostic PAC learning
method for learning of simplices if for all $\mathcal{S}\in\mathbb{S}_{K}$,
any $\epsilon_{1},\epsilon_{2},\delta>0$, any distribution $\mathbb{G}$ with
$\|\mathbb{G}-\mathbb{P}_{\mathcal{S}}\|_{\mathrm{TV}}\leq\epsilon_{1}$, and
assuming to have $n\geq\mathrm{poly}\left(1/\epsilon_{2},1/\delta\right)$
i.i.d. samples from $\mathbb{G}$, the following relation holds with
probability at least $1-\delta$:

$\|\mathbb{P}_{\mathcal{S}_{\mathcal{A}}}-\mathbb{P}_{\mathcal{S}}\|_{\mathrm{TV}}<C_{1}\cdot\epsilon_{1}+C_{2}\cdot\epsilon_{2}.$

We say that the class of $K$-simplices is PAC-Learnable in agnostic setting,
if such an algorithm exists.

We also need to define a series of geometric restrictions for the simplex in
noisy cases. We discuss the necessity of such definitions in later stages.
Similar to [4], let us denote the volume of the largest facet of a $K$-simplex
(here, volume needs be calculated in $\mathbb{R}^{K-1}$) by
$\mathcal{A}_{\max}\left(\mathcal{S}\right)$, and the length of the largest
line segment inside the simplex (diameter) by
$\mathcal{L}_{\max}\left(\mathcal{S}\right)$. In this regard, we define the
isoperimetricity of a $K$-simplex as follow:

######  Definition 4
($\left(\underline{\theta},\bar{\theta}\right)$-isoperimetricity of
simplices).

A $K$-simplex $\mathcal{S}\in\mathbb{S}_{K}$ is defined to be
$\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric if the following
inequalities hold:

$\displaystyle\mathcal{A}_{\max}\left(\mathcal{S}\right)~{}\leq~{}\bar{\theta}\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{K-1}{K}}\quad,\quad\mathcal{L}_{\max}\left(\mathcal{S}\right)~{}\leq~{}\underline{\theta}K\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{1}{K}}.$

The overall concept of isoperimetricity for simplices reflects the fact that
for a simplex to be (even partially) recoverable from noisy data, it should
not be stretched too much in any direction or having highly acute angles. In
other words, sample complexity in noisy regimes is also affected by the
geometric shape of the simplex.

######  Definition 5 ($\epsilon$-representative set).

For any $\epsilon>0$, we say that a finite set of distributions $\mathcal{G}$
is an $\epsilon$-representative set for a distribution class $\mathcal{F}$, if
for any distribution $f\in\mathcal{F}$, there exists some $g\in\mathcal{G}$
that satisfies

$\mathrm{TV}\left(f,g\right)\leq\epsilon.$

Throughout the paper, we use bold lowercase letters to show vectors, bold
uppercase letters to show matrices, light uppercase letters to show random
variables and light lower case letters to show realization of a random
variable. In this paper and for the sake of simplicity in notation, for any
fixed $\bar{\theta},\underline{\theta}>0$, whenever we say the class of
simplices we actually mean the class of
$\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric simplices.

###  2.1 Problem Definition

In this paper, we aim at proving a special form of agnostic PAC-learnability
for simplices. Based on definition 3, and in order to show that the class of
$K$-simplices is agnostic PAC-learnable, we should propose an algorithm that
for all $\mathcal{S}\in\mathbb{S}_{K}$, any positive
$\epsilon_{1},\epsilon_{2},\delta>0$, given a dataset
$\mathrm{S}=\\{\boldsymbol{y}_{1},\boldsymbol{y}_{2},\cdots,\boldsymbol{y}_{n}\\}$
of i.i.d. samples drawn from any probability measure $\mathbb{G}$ with
$\|\mathbb{G}-\mathbb{P}_{\mathcal{S}}\|_{TV}\leq\epsilon_{1}$ and
$n\geq\mathrm{poly}\left(\epsilon_{2},\delta\right)$, outputs a simplex
$\hat{\mathcal{S}}$ such that

$P\left(\|\mathbb{P}_{\widehat{\mathcal{S}}}-\mathbb{P}_{\mathcal{S}}\|_{TV}\geq
C_{1}\cdot\epsilon_{1}+C_{2}\cdot\epsilon_{2}\right)\leq\delta,$ (3)

In our special case, we assume that samples are drawn from
$\mathbb{P}_{\mathcal{S}}$ and then are corrupted by an additive independent
zero mean Gaussian noise with a covariance matrix of
$\sigma^{2}\boldsymbol{I}$. In fact, this procedure describes the distribution
$\mathbb{G}$ in our work. In other words, we assume $\mathbb{G}$ belongs to
the class of noisy simplices, which is the set of all convolution of uniform
measures over simplices in $\mathbb{R}^{K}$ with a zero-mean multivariate
Gaussian distribution
$\mathcal{N}\left(\boldsymbol{0},\sigma^{2}\boldsymbol{I}\right)$.

Our ultimate goals are the followings: First, we tend to show that
$\epsilon_{1}$ in the above configuration, and w.r.t. our particular choice of
$\mathbb{G}$, can be chosen as small as $O\left(\mathrm{SNR}^{-1}\right)$.
Second, we aim at deriving explicit polynomial forms for the lower-bound
$n\geq\mathrm{poly}\left(1/\epsilon_{2},\log\left(1/\delta\right)\right)$,
which (as we will show in Theorem 3) turns out to be

$n\geq\tilde{O}\left[\frac{K^{2}}{\epsilon^{2}_{2}}\log\frac{1}{\delta}\right].$

##  3 Statistical Learning of Simplices in Agnostic Setting

Before going through the details, let us first present an sketch of proof for
agnostic PAC-learnability of noisy simplices. (Bounding the candidate set): In
order to estimate the true simplex from noisy i.i.d. samples, we first split
our data in half and use the first half to restrict the set of all
$K$-simplices in $\mathbb{R}^{K}$ (denoted by $\mathbb{S}_{K}$), to a bounded
set $\mathbb{S}^{\mathcal{D}}_{K}$ which consists of all the simplices that
happen to entirely fall within a finite ball. This way, we can eliminate very
far candidates and thus focus on simplices that are placed near the data
samples. In this regard, we construct a bounded version of $\mathbb{S}_{K}$
denoted by $\mathbb{S}^{\mathcal{D}}_{K}$ in a way that, with high
probability, includes the true simplex. (Quantization): Then, we quantize this
bounded set and create a finite $\epsilon$-representative set of $K$-simplices
denoted by
$\widehat{\mathbb{S}}^{\mathcal{D}}_{K}=\\{\mathcal{S}_{1},\mathcal{S}_{2},\cdots,\mathcal{S}_{M}\\}$
for $M\in\mathbb{N}$, such that for each simplex
$\mathcal{S}\in\mathbb{S}^{\mathcal{D}}_{K}$, there exists some
$i\in\\{1,2,\cdots,M\\}$ where
$\|\mathbb{P}_{\mathcal{S}_{i}}-\mathbb{P}_{\mathcal{S}}\|_{TV}\leq\epsilon$.
(Density selection): In the last part of our proof, we use the second half of
data and try to choose the best simplex in
$\widehat{\mathbb{S}}^{\mathcal{D}}_{K}$. By the best simplex, we mean the one
with minimum TV-distance from the true simplex.

###  3.1 Bounding The Candidate Set

In this part, we show how the first half of the dataset can be utilized in
order to bound the set of all candidate simplices into a ball with a finite
radius in $\mathbb{R}^{K}$. This procedure is crucial for later stages of the
proof. In this regard, suppose that for any $K$-simplex $\mathcal{S}$ we
define $\mathbb{G}_{\mathcal{S}}$ as the noisy version of
$\mathbb{P}_{\mathcal{S}}$ as follows:

$\displaystyle\boldsymbol{y}\sim\mathbb{G}_{\mathcal{S}}\implies$
$\displaystyle\boldsymbol{y}=\boldsymbol{x}+\boldsymbol{z},$
$\displaystyle\boldsymbol{x}=\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi},\quad\boldsymbol{\phi}\sim\mathrm{Dir}\left(1,1,\cdots,1\right),$
$\displaystyle\boldsymbol{z}\sim\mathcal{N}\left(\boldsymbol{0},\sigma\boldsymbol{\mathrm{I}}\right),$
(4)

where $\boldsymbol{V}_{\mathrm{S}}$ denotes the vertex matrix for
$\mathcal{S}$. Also, for a noisy simplex $\mathbb{G}_{\mathcal{S}}$ we define
signal-to-noise ratio or $\mathrm{SNR}$ as

$\mathrm{SNR}=\frac{\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{1}{K}}}{\sigma}.$
(5)

The following lemma shows that having enough samples from a noisy simplex
$\mathbb{G}_{\mathcal{S}}$, one can find a hyper-sphere in $\mathbb{R}^{K}$
which, with high probability, contains $\mathcal{S}$.

######  Lemma 1 (Creating $\mathbb{S}^{\mathcal{D}}_{K}$).

Suppose that we have a set of i.i.d. samples
$\mathrm{S}=\left\\{\boldsymbol{y}_{1},\boldsymbol{y}_{2},\cdots,\boldsymbol{y}_{2m}\right\\}$
from $\mathbb{G}_{\mathcal{S}}$ for $m\in\mathbb{N}$. If $m\geq
72\underline{\theta}^{4}e^{4}\left(\frac{\left(K+1\right)\left(K+2\right)}{K}\right)^{2}\log{\frac{12}{\delta}}$,
then the true simplex $\mathcal{S}$ with probability at least $1-\delta$ will
be confined in a $K$-dimensional sphere with center point $\boldsymbol{p}$ and
radius $R$, where $R$ and $\boldsymbol{p}$ are as follows:

$\displaystyle\mathrm{R}=\sqrt{\frac{4e^{2}(K+1)(K+2)\cdot\underline{\theta}^{2}\cdot\mathrm{D}}{1+\frac{4e^{2}(K-2)}{\mathrm{SNR}^{2}}-\frac{4}{3\underline{\theta}\mathrm{SNR}}}}\left(1+\frac{\bar{\theta}}{\underline{\theta}^{2}e^{2}\mathrm{SNR}\sqrt{K}}\right)\quad,\quad\mathrm{\boldsymbol{p}}=\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{y}_{i}},$
(6)

where $D$ is defined as

$\mathrm{D}=\frac{1}{2m}\sum_{i=1}^{m}{\|\boldsymbol{y}_{2i}-\boldsymbol{y}_{2i-1}\|_{2}^{2}}.$

Proof can be found in appendix section B. This way, the set
$\mathbb{S}^{\mathcal{D}}_{K}$ can be fixed. Next, we discuss how to quantize
this set properly in order to choose an appropriate final candidate for the
true simplex.

###  3.2 Quantization

Let us call the hyper-sphere of Lemma 1 as $\mathrm{C}^{K}(\boldsymbol{p},R)$,
which with high probability contains the main simplex. In this part, we choose
a set of points
$\mathrm{T}^{l}_{\epsilon}(\mathrm{C}^{K}(\boldsymbol{p},R))=\\{\boldsymbol{p}_{1},\boldsymbol{p}_{2},\cdots,\boldsymbol{p}_{l}\\}$
inside this sphere such that for any point
$\boldsymbol{x}\in\mathrm{C}^{K}(\boldsymbol{p},R)$, there exists some
$i\in\\{1,2,\cdots,l\\}$ such that
$\|\boldsymbol{x}-\boldsymbol{p}_{i}\|_{2}\leq\epsilon$. We call
$\mathrm{T}^{l}_{\epsilon}(\mathrm{C}^{K}(\boldsymbol{p},R))$ a covering set
for $\mathrm{C}^{K}(\boldsymbol{p},R)$. One way to construct such covering set
is to uniformly draw points from the sphere. We show that if the number of
drawn random points exceeds
$O\left(\left(1+\frac{2R}{\epsilon}\right)^{2K}\right)$, then with high
probability, they form an $\epsilon$-covering set for
$\mathrm{C}^{K}(\boldsymbol{p},R)$.

Suppose that we construct a random covering set as described above and denote
it with $\mathrm{T}_{\epsilon}(\mathrm{C}^{K}(\boldsymbol{p},R))$. Now, using
each $K+1$ distinct points in
$\mathrm{T}_{\epsilon}(\mathrm{C}^{K}(\boldsymbol{p},R))$ we can build a
$K$-simplex. Assume we collect all such simplices in a set called
$\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))$, i.e.,

$\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))=\left\\{\mathcal{S}(\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{K+1})\bigg{|}~{}\boldsymbol{x}_{i}\in\mathrm{T}_{\epsilon}(\mathrm{C}^{K}(\boldsymbol{p},R)),~{}i=1,\ldots,K+1\right\\}.$

Obviously, there exist at most
$\binom{|\mathrm{T}_{\epsilon}(\mathrm{C}^{K}(\boldsymbol{p},R))|}{K+1}$
simplices in $\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))$. The
following lemma states that this set is a sufficiently good representative for
all $\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric $K$-simplices
inside $\mathrm{C}^{K}(\boldsymbol{p},R)$.

######  Lemma 2.

For any $\epsilon\in\left(0,1\right)$, denote the set of all possible
$K$-simplices with the vertices in
$\mathrm{T}_{\frac{\alpha\epsilon}{K+1}}(\mathrm{C}^{K}(\boldsymbol{p},R))$ as
$\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))$. Then, the resulting
set is an $\epsilon$-representative set for all
$\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric $K$-simplices in
$\mathrm{C}^{K}(\boldsymbol{p},R)$, as long as we have:

$\alpha=\frac{\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{1}{K}}}{5\cdot\bar{\theta}}.$

The proof of this lemma can be find in appendix section B. This way, the
finite candidate set $\mathbb{S}^{\mathcal{D}}_{K}$ can be formed and we can
jump to the final stage of our algorithm for finding a “good" candidate for
the true simplex.

###  3.3 Density Selection

First, let us state a core result in [18] which plays a central role in the
remainder of our derivations. At this stage, we have already created the
finite set of representative simplices
$\widehat{\mathbb{S}}^{\mathcal{D}}_{K}$ and wish to find the best simplex in
this set. This can be done using the following theorem:

######  Theorem 1 (Theorem 6.3 of [18]).

Let $\mathcal{F}$ be a finite class of distributions consisting of $M$
distinct members $\\{f_{1},f_{2},\cdots,f_{M}\\}$. Also, suppose we have
$n\geq\frac{\log{(3M^{2}/\delta)}}{2\epsilon^{2}}$ i.i.d. samples from an
arbitrary distribution $g$ for some $\epsilon>0$. Then, there exist a
deterministic algorithm $\mathcal{A}$, which outputs a number
$j\in\\{1,\ldots,M\\}$ satisfying the following inequality with probability at
least $1-\delta$:

$\|f_{j}-g\|_{TV}\leq
3\cdot\min_{i\in\\{1,2,\cdots,M\\}}\|f_{i}-g\|_{TV}+4\epsilon.$ (7)

Proof can be found inside the reference. Combining the results of Theorem 7
and Lemmas 1 and 2, we can present one of our main results as follows: The set
of all shape-restricted simplices in $\mathbb{R}^{K}$ which entirely fall
inside a sphere with radius $R$ is agnostic PAC-learnable:

######  Theorem 2 (Agnostic PAC-Learnability of Simplices in
$\mathrm{C}^{K}(\boldsymbol{p},R)$).

The class of $\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric
$K$-simplices which are contained within a $K$-dimensional sphere of radius
$R$, denoted by $\mathrm{C}^{K}(\boldsymbol{p},R)$, is PAC-learnable in
agnostic setting. Specifically, for some $\epsilon_{1},\epsilon_{2},\delta>0$,
assume we have at least $n$ i.i.d. samples from a distribution $\mathbb{G}$
which is at most $\epsilon_{1}$-far from at least one simplex in
$\mathrm{C}^{K}(\boldsymbol{p},R)$, with

$n\geq\frac{2K\cdot(K+1)\log\left(1+\frac{10\bar{\theta}(K+1)}{\epsilon_{2}}\cdot\frac{R}{\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{1}{K}}}\right)+\log\frac{3}{\delta}}{\epsilon_{2}^{2}}.$
(8)

Then, there exists an algorithm $\mathcal{A}$ whose output
$\mathcal{S}_{\mathcal{A}}$ satisfies the following inequality with
probability at least $1-\delta$:

$\|\mathbb{P}_{\mathcal{S}_{\mathcal{A}}}-\mathbb{P}_{\mathcal{S}}\|_{\mathrm{TV}}\leq\quad
4\cdot\epsilon_{1}+7\cdot\epsilon_{2}.$ (9)

The proof can be find in the appendix section A. So far, we have proved that
for any $\epsilon,R>0$ and $\boldsymbol{p}\in\mathbb{R}^{K}$, having
$n\geq\tilde{O}\left(K^{2}\log R/\epsilon^{2}\right)$ samples from “any"
distribution $\mathbb{G}$ (not necessarily a uniform measure over a simplex),
there exists an algorithm $\mathcal{A}$ that can output simplex
$\mathcal{S}_{\mathcal{A}}$ such that with high probability

$\left\|\mathbb{P}_{\mathcal{S}_{\mathcal{A}}}-\mathbb{G}\right\|_{\mathrm{TV}}\leq
4\min_{\mathcal{S}\in\mathrm{C}^{K}(\boldsymbol{p},R)}\left\|\mathbb{G}-\mathbb{P}_{\mathcal{S}}\right\|_{\mathrm{TV}}+\epsilon.$

Note that $\bar{\theta}$ which represents the order in the shape of simplices
is also present inside the bounds. In fact, trying to learn a highly stretched
simplex from noisy data can become very tricky since even a small amount of
noise can shoot almost all the samples outside of the simplex. Another
limitation of Theorem 9 is that it requires the simplices to be inside an
sphere of radius $R$. Using Lemma 1, we show that this is not an actual
necessity, if the distribution $\mathbb{G}$ is a noisy version of
$\mathbb{P}_{\mathcal{S}}$ for any $\mathcal{S}\in\mathbb{S}_{K}$. The
following theorem is our main result in this paper:

######  Theorem 3 (Agnostic PAC-Learnability of Simplices in General).

The class of $\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric
$K$-simplices are agnostic PAC-learnable, as long as samples are drawn i.i.d.
from any noisy simplex. In other words, having
$n\geq\tilde{O}\left({K^{2}}/{\epsilon_{2}^{2}}\right)$ i.i.d. samples from a
noisy simplex $\mathbb{G}_{\mathcal{S}}$, there exist an algorithm which
outputs a simplex $\hat{\mathcal{S}}$ that with high probability satisfies

$\|\mathbb{P}_{\hat{\mathcal{S}}}-\mathbb{P}_{\mathcal{S}}\|_{\mathrm{TV}}\leq
C_{1}\cdot\epsilon_{1}+C_{2}\cdot\epsilon_{2},$ (10)

where $\epsilon_{1}$ is the TV-distance between the noisy simplex
$\mathbb{G}_{\mathcal{S}}$ and the uniform measure over the true one
$\mathbb{P}_{\mathcal{S}}$.

Proof of the above theorem can be found in the appendix section A. Obviously,
the $\log R$ dependence inside the sample complexity of Theorem 9 has been
disappeared in that of Theorem 3.

What remains to do is to show that whenever
$\mathbb{G}=\mathbb{G}_{\mathcal{S}}$, i.e., a noisy version of an actual
simplex, the term
$\left\|\mathbb{G}_{\mathcal{S}}-\mathbb{P}_{\mathcal{S}}\right\|_{\mathrm{TV}}$
also decreases as one increases the SNR. The following lemma gives an upper
bound for the TV-distance between a noisy simplex $\mathbb{G}_{\mathcal{S}}$,
and the uniform measure over the noiseless one, i.e.,
$\mathbb{P}_{\mathcal{S}}$:

######  Lemma 3.

For any $\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric simplex
$\mathcal{S}$, the TV-distance between the noisy simplex
$\mathbb{G}_{\mathcal{S}}$ defined via 4 and the noiseless one can be bounded
as

$\mathrm{TV}\left(\mathbb{G}_{\mathcal{S}},\mathbb{P}_{\mathcal{S}}\right)\leq
3\frac{(K+1)\bar{\theta}}{\mathrm{SNR}}\cdot\sqrt{K+\sqrt{8K\log\frac{\mathrm{SNR}}{K+1}}}$
(11)

Proof is given in appendix section B. This way, we showed the distance from a
simplex and its noisy version in total variation sense is at most
$\tilde{O}\left(\mathrm{SNR}^{-1}\right)$ and this proves all of our claims.

##  4 Conclusions

We present sample complexity bounds for learning high-dimensional simplices in
noisy regimes. Formally speaking, we prove that given a sufficient amount of
noisy data, one can estimate a true high-dimensional simplex up to an error
which is reciprocal to the standard deviation of the noise. Also, a presumably
optimal polynomial dependence on a number of parameters, such as dimension has
been achieved for the sample complexity of noisy regime which match those of
the already-solved noiseless case. Our proofs are based on a number of recent
techniques which have been previously used on learning of Gaussian mixture
models. In particular, we use a parameter quantization technique to transform
the problem into a density selection task, and ultimately prove the agnostic
PAC-learnability of simplices which gives us the desired result for sample
complexity. For future directions in this area, one can think of analyzing
this problem under a broader noise and distortion model which might match the
practice even more. Also, improving the bounds, specially trying to eliminate
the term $O\left(\mathrm{SNR}^{-1}\right)$ from the overall error is another
promising research path.

## References

  * [1] G. Satas and B. J. Raphael, “Tumor phylogeny inference using tree-constrained importance sampling,” _Bioinformatics_ , vol. 33, no. 14, pp. i152–i160, 2017.
  * [2] T.-H. Chan, C.-Y. Chi, Y.-M. Huang, and W.-K. Ma, “A convex analysis-based minimum-volume enclosing simplex algorithm for hyperspectral unmixing,” _IEEE Transactions on Signal Processing_ , vol. 57, no. 11, pp. 4418–4432, 2009.
  * [3] R. Schwartz and S. E. Shackney, “Applying unmixing to gene expression data for tumor phylogeny inference,” _BMC bioinformatics_ , vol. 11, no. 1, p. 42, 2010.
  * [4] A. Najafi, S. Ilchi, A. H. Saberi, S. A. Motahari, B. H. Khalaj, and H. R. Rabiee, “On statistical learning of simplices: Unmixing problem revisited,” _The Annals of Statistics_ , vol. 49, no. 3, pp. 1626–1655, 2021.
  * [5] J. Anderson, N. Goyal, and L. Rademacher, “Efficient learning of simplices,” in _Conference on Learning Theory_ , 2013, pp. 1020–1045.
  * [6] C. Bhattacharyya and R. Kannan, “Near-optimal sample complexity bounds for learning latent $k-$ polytopes and applications to ad-mixtures,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 854–863.
  * [7] H. Ashtiani, S. Ben-David, N. Harvey, C. Liaw, A. Mehrabian, and Y. Plan, “Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [8] J. Piper, V. P. Pauca, R. J. Plemmons, and M. Giffin, “Object characterization from spectral data using nonnegative factorization and information theory,” in _Proceedings of AMOS technical conference_ , 2004.
  * [9] J. M. Bioucas-Dias, A. Plaza, N. Dobigeon, M. Parente, Q. Du, P. Gader, and J. Chanussot, “Hyperspectral unmixing overview: Geometrical, statistical, and sparse regression-based approaches,” _IEEE journal of selected topics in applied earth observations and remote sensing_ , vol. 5, no. 2, pp. 354–379, 2012.
  * [10] C.-H. Lin, A. Ambikapathi, W.-C. Li, and C.-Y. Chi, “On the endmember identifiability of craig’s criterion for hyperspectral unmixing: A statistical analysis for three-source case,” in _Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on_. IEEE, 2013, pp. 2139–2143.
  * [11] A. Ambikapathi, T.-H. Chan, W.-K. Ma, and C.-Y. Chi, “Chance-constrained robust minimum-volume enclosing simplex algorithm for hyperspectral unmixing,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 49, no. 11, pp. 4194–4209, 2011.
  * [12] A. Agathos, J. Li, J. M. Bioucas-Dias, and A. Plaza, “Robust minimum volume simplex analysis for hyperspectral unmixing,” in _Signal Processing Conference (EUSIPCO), 2014 Proceedings of the 22nd European_. IEEE, 2014, pp. 1582–1586.
  * [13] S. Zhang, A. Agathos, and J. Li, “Robust minimum volume simplex analysis for hyperspectral unmixing,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 55, no. 11, pp. 6431–6439, 2017.
  * [14] N. S. Zuckerman, Y. Noam, A. J. Goldsmith, and P. P. Lee, “A self-directed method for cell-type identification and separation of gene expression microarrays,” _PLoS computational biology_ , vol. 9, no. 8, p. e1003189, 2013\.
  * [15] D. Tolliver, C. Tsourakakis, A. Subramanian, S. Shackney, and R. Schwartz, “Robust unmixing of tumor states in array comparative genomic hybridization data,” _Bioinformatics_ , vol. 26, no. 12, pp. i106–i114, 2010.
  * [16] O. Shoval, H. Sheftel, G. Shinar, Y. Hart, O. Ramote, A. Mayo, E. Dekel, K. Kavanagh, and U. Alon, “Evolutionary trade-offs, pareto optimality, and the geometry of phenotype space,” _Science_ , vol. 336, no. 6085, pp. 1157–1160, 2012.
  * [17] Y. Korem, P. Szekely, Y. Hart, H. Sheftel, J. Hausser, A. Mayo, M. E. Rothenberg, T. Kalisky, and U. Alon, “Geometry of the gene expression space of individual cells,” _PLoS computational biology_ , vol. 11, no. 7, p. e1004224, 2015.
  * [18] L. Devroye and G. Lugosi, _Combinatorial methods in density estimation_. Springer Science & Business Media, 2012.
  * [19] M. J. Wainwright, _High-dimensional statistics: A non-asymptotic viewpoint_. Cambridge University Press, 2019, vol. 48.

## Appendix

In this section, we present the proofs for the Theorems and Lemmas of the
manuscript.

##  Appendix A Proof of Theorems

###### proof of Theorem $2$.

Suppose that $\mathcal{S}$ is a
$\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric simplex in
$\mathbb{R}^{K}$ which is confined in a $K$-dimensional sphere
$\mathrm{C}^{K}(\boldsymbol{p},R)$. From Lemma $2$, we know how to build an
$\epsilon$-representative set, for any $\epsilon>0$, for all
$\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric $K$-simplices in
$\mathrm{C}^{K}(\boldsymbol{p},R)$. Let us denote this set with
$\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))$. Assume that we have
a set of i.i.d. samples from some distribution $\mathbb{G}$ where
$\|\mathbb{P}_{\mathcal{S}}-\mathbb{G}\|_{\mathrm{TV}}\leq\epsilon_{1}$. From
Theorem $1$, we know that there exists a deterministic algorithm $\mathcal{A}$
such that given

$n\geq\frac{\log{(3|\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))|^{2}/\delta)}}{2\epsilon_{2}^{2}}$

i.i.d. samples from $\mathbb{G}$, the output of the algorithm denoted by
$\mathcal{S}_{\mathcal{A}}$, with probability at least $1-\delta$, satisfies:

$\displaystyle\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}_{\mathcal{A}}},\mathbb{G}\right)\leq$
$\displaystyle~{}3\min_{\mathcal{S}^{\prime}\in\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))}\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}^{\prime}},G\right)+4\epsilon_{2}$
$\displaystyle\leq$
$\displaystyle~{}3\min_{\mathcal{S}^{\prime}\in\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))}\left[\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}^{\prime}},\mathbb{P}_{\mathcal{S}}\right)+\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}},G\right)\right]+4\epsilon_{2}$
$\displaystyle\leq$ $\displaystyle~{}3\epsilon+3\epsilon_{1}+4\epsilon_{2}$
$\displaystyle\leq$ $\displaystyle~{}3\epsilon_{1}+7\epsilon_{2},$ (12)

where in the final inequality above, we assume the $\epsilon$-representative
set $\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))$ is formed for
$\epsilon=\epsilon_{2}$. Then, according to Lemma $2$ the followings hold for
the cardinality of $\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))$:

$\displaystyle\bigg{|}\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))\bigg{|}=$
$\displaystyle\binom{\left|\mathrm{T}_{\frac{\alpha\epsilon_{2}}{K+1}}(\mathrm{C}^{K}(\boldsymbol{p},R))\right|}{K+1}$
$\displaystyle\leq$
$\displaystyle~{}\bigg{|}\mathrm{T}_{\frac{\alpha\epsilon_{2}}{K+1}}(\mathrm{C}^{K}(\boldsymbol{p},R))\bigg{|}^{K+1}$
$\displaystyle\leq$
$\displaystyle~{}\left(\left(1+\frac{2(K+1)R}{\alpha\epsilon_{2}}\right)^{K}\right)^{K+1}$
$\displaystyle=$
$\displaystyle~{}\left(1+\frac{2(K+1)R}{\alpha\epsilon_{2}}\right)^{K(K+1)}.$
(13)

From 13 and 12, we can say that for any $\epsilon_{1},\epsilon_{2},\delta>0$,
there exists an agnostic PAC-learning algorithm $\mathcal{A}$ for the class of
$\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric $K$-simplices
which are contained in a $K$-dimensional sphere
$\mathrm{C}^{K}(\boldsymbol{p},R)$, whose sample complexity is bounded as
follows:

$\displaystyle n\geq$
$\displaystyle~{}\frac{2K(K+1)\log\left(1+\frac{2(K+1)R}{\alpha\epsilon_{2}}\right)+\log\frac{3}{\delta}}{2\epsilon_{2}^{2}}$
$\displaystyle=$
$\displaystyle~{}\frac{K(K+1)\log\left(1+\frac{10\bar{\theta}(K+1)}{\epsilon_{2}}\cdot\frac{R}{\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{1}{K}}}\right)+\log\frac{3}{\delta}}{\epsilon_{2}^{2}}.$
(14)

In other words, given that the number of samples $n$ satisfies the above
lower-bound, then with probability at least $1-\delta$ we have

$\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}_{\mathcal{A}}},\mathbb{P}_{\mathcal{S}}\right)\leq\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}_{\mathcal{A}}},\mathbb{G}\right)+\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}},\mathbb{G}\right)\leq
4\epsilon_{1}+7\epsilon_{2}.$

This completes the proof. Using simple algebra, the bound can be further
simplified into $n\geq
O\left(\frac{K^{2}}{\epsilon_{2}^{2}}\log{\frac{K}{\epsilon_{2}}}\right)$
which completes the proof. ∎

###### proof of Theorem $3$.

From Theorem $2$, we know that the class of
$\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric simplices which
are contained in a $K$-dimensional sphere with radius $R$, is agnostic PAC-
learnable with sample complexity
$O\left(\frac{K^{2}}{\epsilon_{2}^{2}}\log{\frac{K}{\epsilon_{2}}}\right)$,
where $\epsilon_{2}$ is defined accordingly. And from Lemma $1$, we know that
if we have $O\left(K^{2}\right)$ samples from a noisy simplex
$\mathbb{G}_{\mathcal{S}}$, we can find a $K$-dimensional sphere which with
probability at least $1-\delta/2$ contains the true simplex as long as the
radius $R$ of the sphere satisfies

$\mathrm{R}\leq\frac{2e\underline{\theta}^{2}(K+2)\sqrt{(K+1)(K+2)}\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)\left(1+\frac{1}{\underline{\theta}\mathrm{SNR}}\right)}{\sqrt{1+\frac{4e^{2}(K-2)}{\mathrm{SNR}^{2}\left(\mathcal{S}\right)}-\frac{4}{\underline{\theta}\mathrm{SNR}\left(\mathcal{S}\right)}}}.$
(15)

Therefore, it can be shown that there exists an algorithm $\mathcal{A}$ such
that given $n$ i.i.d samples from $\mathbb{G}_{\mathcal{S}}$ with

$\displaystyle n\geq$
$\displaystyle~{}\frac{K(K+1)\log\left(1+\frac{10\bar{\theta}(K+1)}{\epsilon_{2}}\frac{R}{\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{1}{K}}}\right)+\log\frac{6}{\delta}}{\epsilon_{2}^{2}}+144\underline{\theta}^{4}e^{4}\left(\frac{\left(K+1\right)\left(K+2\right)}{K}\right)^{2}\log{\frac{12}{\delta}}$
$\displaystyle=$
$\displaystyle~{}O\left(\frac{K^{2}}{\epsilon^{2}_{2}}\log\frac{K}{\epsilon_{2}}\right),$
(16)

the output of the algorithm $\hat{\mathcal{S}}$ with probability at least
$1-\delta$ satisfies

$\mathrm{TV}\left(\mathbb{P}_{\hat{\mathcal{S}}},\mathbb{P}_{\mathcal{S}}\right)\leq~{}4\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}},\mathbb{G}\right)+7\epsilon_{2}.$

It should be noted that $R$ in (16) is already replaced with the bound in the
r.h.s of (15). This way, the proof is completed. ∎

##  Appendix B Proof of Lemmas

###### proof of Lemma $1$.

To find a $K$-dimensional sphere containing the true simplex, it suffices to
find a point $\boldsymbol{p}$ inside the simplex and an upper-bound $R$ for
its diameter, i.e., the maximum distance between two points in the simplex.
Obviously, this ensures that the $K$-dimensional sphere with center point
$\boldsymbol{p}$ and radius $R$ contains the true simplex. For the maximum
distance between any two points inside $\mathcal{S}\in\mathbb{S}_{K}$, denoted
by $d_{\mathcal{S}}$, we have

$\displaystyle d_{\mathcal{S}}=$
$\displaystyle\max_{\boldsymbol{x},\boldsymbol{y}\in\mathcal{S}}{\|\boldsymbol{x}-\boldsymbol{y}\|_{2}}$
$\displaystyle=$
$\displaystyle\max_{\boldsymbol{\phi}_{\boldsymbol{x}},\boldsymbol{\phi}_{\boldsymbol{y}}\in\mathcal{S}_{\mathrm{S}}^{K}}{\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{\boldsymbol{x}}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{\boldsymbol{y}}\|_{2}}$
$\displaystyle=$
$\displaystyle\max_{\boldsymbol{\phi}_{\boldsymbol{x}},\boldsymbol{\phi}_{\boldsymbol{y}}\in\mathcal{S}_{\mathrm{S}}^{K}}{\|\boldsymbol{V}_{\mathcal{S}}\left(\boldsymbol{\phi}_{\boldsymbol{x}}-\boldsymbol{\phi}_{\boldsymbol{y}}\right)\|_{2}},$
(17)

where $\mathcal{S}_{\mathrm{S}}^{K}$ represents the standard simplex in
$\mathbb{R}^{K}$ and $\boldsymbol{V}_{\mathcal{S}}$ denotes the vertex matrix
of $\mathcal{S}$ (Equation 4 in the main paper). Let
$\sigma_{\max}\left(\mathcal{S}\right)$ denote the maximum singular-value for
the matrix $\boldsymbol{V}_{\mathcal{S}}$, and assume $\boldsymbol{v}_{\max}$
be the unitary eigenvector that corresponds to
$\sigma_{\max}\left(\mathcal{S}\right)$. To be more precise, let
$\boldsymbol{V}_{\mathcal{S}}=\boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^{T}$
be the singular value decomposition of the vertex matrix. Then,
$\sigma_{\max}\left(\mathcal{S}\right)$ refers to the largest singular value
on the main diagonal of $\boldsymbol{\Sigma}$, and $\boldsymbol{v}_{\max}$
represents the corresponding column in $\boldsymbol{V}$. Then, for any point
$\boldsymbol{x}\in\mathbb{R}^{K+1}$, one can write

$\left\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{x}\right\|^{2}_{2}=\sum_{i}\Sigma^{2}_{i,i}\left\|\boldsymbol{U}_{i}\boldsymbol{V}_{i}^{T}\boldsymbol{x}\right\|^{2}_{2}=\sum_{i}\Sigma^{2}_{i,i}\left(\boldsymbol{V}_{i}^{T}\boldsymbol{x}\right)^{2},$

which results in the following useful inequality:

$\left\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{x}\right\|_{2}\geq\sigma_{\max}\left(\mathcal{S}\right)\left|\boldsymbol{v}_{\max}^{T}\boldsymbol{x}\right|.$

For
$\boldsymbol{\phi}_{\boldsymbol{x}}\neq\boldsymbol{\phi}_{\boldsymbol{y}}$,
let
$\boldsymbol{r}\triangleq\left(\boldsymbol{\phi}_{\boldsymbol{x}}-\boldsymbol{\phi}_{\boldsymbol{y}}\right)/\left\|\boldsymbol{\phi}_{\boldsymbol{x}}-\boldsymbol{\phi}_{\boldsymbol{y}}\right\|_{2}$,
and
$\ell\triangleq\left\|\boldsymbol{\phi}_{\boldsymbol{x}}-\boldsymbol{\phi}_{\boldsymbol{y}}\right\|_{2}$.
In other words, let $\boldsymbol{r}$ represent the unitary direction vector
for the difference, and $\ell$ to denote the corresponding length. In this
regard, we have

$\displaystyle\max_{\boldsymbol{\phi}_{\boldsymbol{x}},\boldsymbol{\phi}_{\boldsymbol{y}}\in\mathcal{S}^{K}_{\mathrm{S}}}\left\|\boldsymbol{V}_{\mathcal{S}}\left(\boldsymbol{\phi}_{\boldsymbol{x}}-\boldsymbol{\phi}_{\boldsymbol{y}}\right)\right\|_{2}\geq~{}\sigma_{\max}\left(\mathcal{S}\right)\max_{\boldsymbol{r},\ell}~{}\ell\left|\boldsymbol{v}_{\max}^{T}\boldsymbol{r}\right|\geq~{}\sigma_{\max}\left(\mathcal{S}\right)\max_{\ell|~{}\boldsymbol{r}=\boldsymbol{v}_{\max}}~{}\ell.$
(18)

Now we should find a lower-bound for maximum possible $\ell$ that can be
achieved for some fixed direction $\boldsymbol{r}=\boldsymbol{v}_{\max}$. To
this aim, assume the difference vector
$\boldsymbol{\phi}_{\boldsymbol{x}}-\boldsymbol{\phi}_{\boldsymbol{y}}$ starts
from any arbitrary vertex, i.e., $\boldsymbol{\phi}_{\boldsymbol{x}}$ is a
one-hot vector with $K$ components equal to zero and the remaining one equal
to $1$. In this regard, the minimum possible $\ell$ that can be achieved
(minimum is taken w.r.t. direction of the difference vector) occurs when the
difference vector becomes perpendicular to its front facet. Since all
$\boldsymbol{\phi}$ vectors belong to the standard simplex, such difference
vectors can be easily shown to be of the form $\boldsymbol{\Delta}$ with

$\Delta_{i}=1\quad\mathrm{and}\quad\Delta_{j|j\neq i}=-1/K,$

for any $i\in 0,\ldots,K$. The $\ell_{2}$-norm of all such vectors equals to
$\sqrt{1+1/K}$. Thus, we have

$\displaystyle
d_{\mathcal{S}}\geq~{}\sqrt{\frac{K+1}{K}}\sigma_{\mathrm{max}}\left(S\right)\geq~{}\sigma_{\mathrm{max}}\left(S\right).$
(19)

Assume we have $2m$ i.i.d. samples drawn from a noisy simplex
$\mathbb{G}_{\mathcal{S}}$, denoted by
$\left\\{\boldsymbol{y}\right\\}^{2m}_{i=1}$. This way, we have
$\boldsymbol{y}_{i}=\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{i}+\boldsymbol{z}_{i}$
for $i=1,\ldots,2m$, where $\boldsymbol{\phi}_{i}$ represents the weight
vector for the $i$th sample (drawn from a uniform Dirichlet distribution),
while
$\boldsymbol{z}_{i}\sim\mathcal{N}\left(\boldsymbol{0},\sigma^{2}\boldsymbol{I}\right)$
is an independently drawn noise vector. Let us define $\mathrm{D}$ as

$\mathrm{D}=\frac{1}{2m}\sum_{i=1}^{m}{\|\boldsymbol{y}_{2i}-\boldsymbol{y}_{2i-1}\|_{2}^{2}}.$
(20)

To find an upper-bound for $\sigma_{\mathrm{max}}$, it is enough to find a
high probability lower-bound for $\mathrm{D}$ in terms of
$\sigma_{\mathrm{max}}$. To this aim, we rewrite $\mathrm{D}$ as

$\displaystyle\mathrm{D}=~{}$
$\displaystyle\frac{1}{2m}\sum_{i=1}^{m}{\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}+\boldsymbol{z}_{2i}-\boldsymbol{z}_{2i-1}\|_{2}^{2}}$
$\displaystyle=~{}$
$\displaystyle\frac{1}{2m}\sum_{i=1}^{m}{\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\|_{2}^{2}}+\frac{1}{2m}\sum_{i=1}^{m}{\|\boldsymbol{z}_{2i}-\boldsymbol{z}_{2i-1}\|_{2}^{2}}$
$\displaystyle+\frac{1}{m}\sum_{i=1}^{m}{\left(\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\right)^{T}\left(\boldsymbol{z}_{2i}-\boldsymbol{z}_{2i-1}\right)}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2m}\sum_{i=1}^{m}{\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\|_{2}^{2}}+\frac{2\sigma^{2}}{2m}\sum_{i=1}^{m}{\|\tilde{\boldsymbol{z}}_{2i}-\tilde{\boldsymbol{z}}_{2i-1}\|_{2}^{2}}$
$\displaystyle+\frac{\sigma\sqrt{2}}{m}\sum_{i=1}^{m}{\left(\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\right)^{T}\left(\tilde{\boldsymbol{z}}_{2i}-\tilde{\boldsymbol{z}}_{2i-1}\right)}.$
(21)

Let us denote the three terms in r.h.s. of (21) as $\mathrm{I}$, $\mathrm{II}$
and $\mathrm{III}$, respectively. Also, we have
$\tilde{\boldsymbol{z}}_{i}=\boldsymbol{z}_{i}/\sigma$. To find a lower-bound
for $\mathrm{D}$, we should find respective lower-bounds for $\mathrm{I}$,
$\mathrm{II}$ and $\mathrm{III}$. First, let us discuss about $(\mathrm{I})$:

$\mathrm{I}=\frac{1}{2m}\sum_{i=1}^{m}{\left\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\right\|_{2}^{2}}=f_{\boldsymbol{V}_{\mathcal{S}}}\left(\boldsymbol{\phi}_{1},\boldsymbol{\phi}_{2},\cdots,\boldsymbol{\phi}_{2m}\right).$
(22)

For the term inside of the summation, we have

$\displaystyle\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\|_{2}^{2}~{}\stackrel{{\scriptstyle
a.s.}}{{\leq}}~{}$ $\displaystyle d_{\mathcal{S}}^{2},$ (23)
$\displaystyle\mathrm{Var}\left(\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\|_{2}^{2}\right)\leq$
$\displaystyle~{}\frac{12\sigma^{4}_{\mathrm{max}}\left(\mathcal{S}\right)}{K^{3}}\leq~{}\frac{12d_{\mathcal{S}}^{4}}{K^{3}}$
(24)

From the above inequalities we can see that
$\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\|_{2}^{2}$
satisfies the Bernstein’s condition with $b=2d^{2}_{\mathcal{S}}$ (see eq.
$2.15$ in [19]). Then (from proposition $2.10$ in [19]) the following
inequality holds with probability at least $1-\delta/6$, for any
$\delta\in\left(0,1\right)$:

$f_{\boldsymbol{V}_{\mathcal{S}}}\left(\boldsymbol{\phi}_{1},\cdots,\boldsymbol{\phi}_{2m}\right)\geq\mathbb{E}\left[f_{\boldsymbol{V}_{\mathcal{S}}}\left(\boldsymbol{\phi}_{1},\cdots,\boldsymbol{\phi}_{2m}\right)\right]-2\sqrt{\max\left\\{\frac{4\log{\frac{6}{\delta}}}{m},\frac{3}{K^{3}}\right\\}\cdot\frac{d_{\mathcal{S}}^{4}}{m}\log{\frac{6}{\delta}}},$
(25)

where for the expected value of the function $f$ we have:

$\displaystyle\mathbb{E}\left[f_{\boldsymbol{V}_{\mathcal{S}}}\left(\boldsymbol{\phi}_{1},\cdots,\boldsymbol{\phi}_{2m}\right)\right]~{}=$
$\displaystyle~{}\frac{1}{2m}\sum_{i=1}^{m}{\mathbb{E}\left[\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\|_{2}^{2}\right]}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2}\mathbb{E}\left[\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}^{\prime}\|_{2}^{2}\right]$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2}\mathbb{E}\left[\left(\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}^{\prime}\right)^{T}\left(\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}^{\prime}\right)\right]$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2}\mathbb{E}\left[\left(\boldsymbol{\phi}-\boldsymbol{\phi}^{\prime}\right)^{T}\boldsymbol{V}_{\mathcal{S}}^{T}\boldsymbol{V}_{\mathcal{S}}\left(\boldsymbol{\phi}-\boldsymbol{\phi}^{\prime}\right)\right]$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2}\mathbb{E}\left[\operatorname{Tr}{\left(\boldsymbol{V}_{\mathcal{S}}^{T}\boldsymbol{V}_{\mathcal{S}}\left(\boldsymbol{\phi}-\boldsymbol{\phi}^{\prime}\right)\left(\boldsymbol{\phi}-\boldsymbol{\phi}^{\prime}\right)^{T}\right)}\right]$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2}\operatorname{Tr}{\left(\boldsymbol{V}_{\mathcal{S}}^{T}\boldsymbol{V}_{\mathcal{S}}\mathbb{E}\left[\left(\boldsymbol{\phi}-\boldsymbol{\phi}^{\prime}\right)\left(\boldsymbol{\phi}-\boldsymbol{\phi}^{\prime}\right)^{T}\right]\right)}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2}\operatorname{Tr}{\left(\boldsymbol{V}_{\mathcal{S}}^{T}\boldsymbol{V}_{\mathcal{S}}\frac{1}{(K+1)^{2}(K+2)}\begin{bmatrix}K&-1&\dots&-1\\\
-1&K&\dots&-1\\\ \vdots&\vdots&\ddots&\vdots\\\
-1&-1&\dots&K\end{bmatrix}\right)}$ $\displaystyle=$
$\displaystyle~{}\frac{1}{2(K+1)^{2}(K+2)}\operatorname{Tr}{\left(\boldsymbol{V}_{\mathcal{S}}^{T}\boldsymbol{V}_{\mathcal{S}}\left((K+1)\mathrm{\boldsymbol{I}}-\boldsymbol{1}\boldsymbol{1}^{T}\right)\right)}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2(K+1)^{2}(K+2)}\left((K+1)\operatorname{Tr}{\left(\boldsymbol{V}_{\mathcal{S}}^{T}\boldsymbol{V}_{\mathcal{S}}\right)}-\operatorname{Tr}{\left(\boldsymbol{1}^{T}\boldsymbol{V}_{\mathcal{S}}^{T}\boldsymbol{V}_{\mathcal{S}}\boldsymbol{1}\right)}\right)$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2(K+2)}\left(\sum_{i=1}^{K}{\frac{1}{K+1}\sum_{j=1}^{K+1}{\boldsymbol{V}_{\mathcal{S}}^{2}(i,j)}}-\sum_{i=1}^{K}{\left(\frac{1}{K+1}\sum_{j=1}^{K+1}{\boldsymbol{V}_{\mathcal{S}}(i,j)}\right)^{2}}\right)$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2(K+2)}\sum_{i=1}^{K}{\frac{1}{K+1}\sum_{j=1}^{K+1}{\left(\boldsymbol{V}_{\mathcal{S}}(i,j)-\frac{1}{K+1}\sum_{j=1}^{K+1}{\boldsymbol{V}_{\mathcal{S}}(i,j)}\right)^{2}}}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2(K+2)}\sum_{i=1}^{K}{\frac{1}{K+1}\sum_{j=1}^{K+1}{\left(\widehat{\boldsymbol{V}}_{\mathcal{S}}(i,j)-\frac{1}{K+1}\sum_{j=1}^{K+1}{\widehat{\boldsymbol{V}}_{\mathcal{S}}(i,j)}\right)^{2}}}.$

This quantity can be lower bounded as

$\displaystyle\geq$
$\displaystyle~{}\frac{1}{2(K+2)}\sum_{i=1}^{K}{\frac{1}{K+1}\sum_{j=2}^{K+1}{\left(\widehat{\boldsymbol{V}}_{\mathcal{S}}(i,j)-\frac{1}{K+1}\sum_{j=1}^{K+1}{\widehat{\boldsymbol{V}}_{\mathcal{S}}(i,j)}\right)^{2}}}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2(K+1)(K+2)}\sum_{i=1}^{K}{\sum_{j=2}^{K+1}{\widetilde{{\boldsymbol{V}}}_{\mathcal{S}}(i,j)}^{2}}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2(K+1)(K+2)}\|\widetilde{\boldsymbol{V}}_{\mathcal{S}}\|_{F}~{}=~{}\frac{1}{2(K+1)(K+2)}\sum_{i=1}^{K}{\widetilde{\sigma}_{\mathcal{S}}^{2}}$
$\displaystyle\geq$
$\displaystyle~{}\frac{1}{2(K+2)}\left(\prod_{i=1}^{K}{\widetilde{\sigma}_{\mathcal{S}}^{2}}\right)^{\frac{1}{K}}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{2(K+1)(K+2)}\left(\prod_{i=1}^{K}{\widehat{\sigma}_{\mathcal{S}}^{2}}\right)^{\frac{1}{K}}$
$\displaystyle\geq$
$\displaystyle~{}\frac{1}{2(K+1)(K+2)}\left(\mathrm{Vol}\left(\mathcal{S}\right)\left(\frac{K}{e}\right)^{K}\right)^{\frac{2}{K}}$
$\displaystyle=$
$\displaystyle~{}\frac{K^{2}}{2e^{2}(K+1)(K+2)}\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{2}{K}},$
(26)

where $\widetilde{{\boldsymbol{V}}}_{\mathcal{S}}$ and
$\widehat{{\boldsymbol{V}}}_{\mathcal{S}}$ are defined as

$\displaystyle\boldsymbol{V}_{\mathcal{S}}=$
$\displaystyle\left[\boldsymbol{v}_{0},\boldsymbol{v}_{1},\cdots,\boldsymbol{v}_{K}\right]$
(27) $\displaystyle\widehat{\boldsymbol{V}}_{\mathcal{S}}=$
$\displaystyle\left[\boldsymbol{v}_{1}-\boldsymbol{v}_{0},\boldsymbol{v}_{2}-\boldsymbol{v}_{0},\cdots,\boldsymbol{v}_{K}-\boldsymbol{v}_{0}\right]$
$\displaystyle=$
$\displaystyle\left[\hat{\boldsymbol{v}}_{1},\hat{\boldsymbol{v}_{2}},\cdots,\hat{\boldsymbol{v}}_{K}\right]$
(28) $\displaystyle\widetilde{\boldsymbol{V}}_{\mathcal{S}}=$
$\displaystyle\left[\hat{\boldsymbol{v}}_{1}-\frac{\sum_{1}^{K}{\hat{\boldsymbol{v}}_{i}}}{K+1},\hat{\boldsymbol{v}}_{2}-\frac{\sum_{1}^{K}{\hat{\boldsymbol{v}}_{i}}}{K+1},\cdots,\hat{\boldsymbol{v}}_{K}-\frac{\sum_{1}^{K}{\hat{\boldsymbol{v}}_{i}}}{K+1}\right]$
$\displaystyle=$
$\displaystyle\left[\tilde{\boldsymbol{v}}_{1},\tilde{\boldsymbol{v}_{2}},\cdots,\tilde{\boldsymbol{v}}_{K}\right].$
(29)

From 25 and 26, it is easy to show that if we have $2m\geq
144\underline{\theta}^{4}e^{4}\left(\frac{\left(K+1\right)\left(K+2\right)}{K}\right)^{2}\log{\frac{6}{\delta}}$
i.i.d. samples from $\mathbb{P}_{\mathcal{S}}$, then with probability at least
$1-\frac{\delta}{6}$ (for any $0<\delta\leq 1$), we have

$f\left(\boldsymbol{\phi}_{1},\boldsymbol{\phi}_{2},\cdots,\boldsymbol{\phi}_{2m}\right)\geq\frac{K^{2}}{4e^{2}(K+1)(K+2)}\mathrm{Vol}\left(\mathcal{S}\right)^{\frac{2}{K}}.$
(30)

Next, we should find a lower-bound for the second term in the r.h.s. of 21,
i.e., $\mathrm{II}$.

In 21, $\boldsymbol{z}_{i}$s are drawn from a multivariate Gaussian
distribution with mean vector $\boldsymbol{0}$ and covariance matrix
$\sigma^{2}\boldsymbol{\mathrm{I}}$. Then,
$\boldsymbol{z}^{\prime}_{i}=\tilde{\boldsymbol{z}}_{2i}-\tilde{\boldsymbol{z}}_{2i-1}$
is also a zero-mean Gaussian random vector with covariance matrix
$\boldsymbol{\mathrm{I}}$, and as a result
$\|\boldsymbol{z}^{\prime}_{i}\|_{2}^{2}$ is a Chi-squared random variable
with $K$ degrees of freedom. We know that a Chi-squared random variable with
$K$ degrees of freedom is sub-exponential with parameters
$\left(2\sqrt{K},4\right)$ and therefore
$\frac{1}{2m}\sum_{i=1}^{m}{\|\boldsymbol{z}^{\prime}_{i}\|_{2}^{2}}$ is a
sub-exponential random variable with parameters
$\left(\sqrt{{K}/{m}},{2}/{m}\right)$. Then the following holds with
probability at least $1-\delta/6$:

$\displaystyle\frac{1}{2m}\sum_{i=1}^{m}{\|\tilde{\boldsymbol{z}}_{2i}-\tilde{\boldsymbol{z}}_{2i-1}\|_{2}^{2}}~{}\geq$
$\displaystyle~{}\frac{1}{2m}\sum_{i=1}^{m}{\mathbb{E}\left[\|\tilde{\boldsymbol{z}}_{2i}-\tilde{\boldsymbol{z}}_{2i-1}\|_{2}^{2}\right]}-\sqrt{\frac{2K}{m}\log{\frac{6}{\delta}}}$
$\displaystyle\geq$
$\displaystyle~{}\frac{K}{2}-\sqrt{\frac{2K}{m}\log{\frac{6}{\delta}}}$
$\displaystyle\geq$
$\displaystyle~{}\frac{K}{2}-\sqrt{\frac{K^{3}}{144e^{4}\underline{\theta}^{4}(K+1)^{2}(K+2)^{2}}}$
$\displaystyle\geq$ $\displaystyle~{}\frac{K}{2}-1=\frac{K-2}{2}.$ (31)

Based on the above inequalities, we can give a lower-bound for the second term
in the r.h.s. of 21:

$\mathrm{II}=\frac{2\sigma^{2}}{2m}\sum_{i=1}^{m}{\|\tilde{\boldsymbol{z}}_{2i}-\tilde{\boldsymbol{z}}_{2i-1}\|_{2}^{2}}\geq(K-2)\sigma^{2}.$
(32)

Now to find a lower bound for $\mathrm{D}\left(\mathrm{S}\right)$, we only
need to give a lower bound for $\mathrm{III}$, in the last inequality of 21.
For this part we have:

$\displaystyle\mathrm{III}~{}=$
$\displaystyle~{}\frac{\sigma\sqrt{2}}{m}\sum_{i=1}^{m}{\left(\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\right)^{T}\left(\tilde{\boldsymbol{z}}_{2i}-\tilde{\boldsymbol{z}}_{2i-1}\right)}$
$\displaystyle=$
$\displaystyle~{}\frac{\sigma\sqrt{2}}{m}\sum_{i=1}^{m}{\left(\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\right)^{T}\boldsymbol{z}_{i}^{\prime}}$
$\displaystyle=$
$\displaystyle~{}\frac{\sigma\sqrt{2}}{m}\sum_{i=1}^{m}{g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(z_{i}^{\prime
1},z_{i}^{\prime 2},\cdots,z_{i}^{\prime m}\right)},$ (33)

where in the above equations we have:

$\mathbb{E}\left(g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(z_{i}^{\prime
1},z_{i}^{\prime 2},\cdots,z_{i}^{\prime
m}\right)\right)=\mathbb{E}\left(\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\right)^{T}\mathbb{E}\left(\boldsymbol{z}_{i}^{\prime}\right)=0.$
(34)

To find a lower bound for $\mathrm{III}$ we try to bound
$g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(z_{i}^{\prime
1},z_{i}^{\prime 2},\cdots,z_{i}^{\prime m}\right)$ from below. To do so, we
write the concentration inequality for this function as follow:

$\displaystyle\mathbb{P}\left(g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(z_{i}^{\prime
1},z_{i}^{\prime 2},\cdots,z_{i}^{\prime m}\right)\geq\epsilon\right)\leq$
$\displaystyle~{}\frac{\mathbb{E}_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}},\boldsymbol{z}_{i}^{\prime}}\left[e^{\lambda
g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(z_{i}^{\prime
1},z_{i}^{\prime 2},\cdots,z_{i}^{\prime
m}\right)}\right]}{e^{\lambda\epsilon}}$ $\displaystyle\leq$
$\displaystyle~{}\frac{\mathbb{E}_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}},\boldsymbol{z}_{i}^{\prime}}\left[e^{\lambda
g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(z_{i}^{\prime
1},z_{i}^{\prime 2},\cdots,z_{i}^{\prime
m}\right)}\right]}{e^{\lambda\epsilon}}$ $\displaystyle=$
$\displaystyle~{}\frac{\mathbb{E}_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left[\mathbb{E}_{\boldsymbol{z}_{i}^{\prime}}\left[e^{\lambda
g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(z_{i}^{\prime
1},z_{i}^{\prime 2},\cdots,z_{i}^{\prime
m}\right)}\right]\right]}{e^{\lambda\epsilon}},$ (35)

where
$g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(\boldsymbol{z}\right)$
is a lipschitz function with respect to $\boldsymbol{z}^{\prime}$:

$\displaystyle|g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(\boldsymbol{z}_{1}\right)-g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(\boldsymbol{z}_{2}\right)|\leq$
$\displaystyle\quad\|\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\|_{2}\|\boldsymbol{z}_{1}-\boldsymbol{z}_{2}\|_{2}$
$\displaystyle\leq$ $\displaystyle\quad
2d_{\mathcal{S}}\|\boldsymbol{z}_{1}-\boldsymbol{z}_{2}\|_{2}.$ (36)

From Lemma (2.27) in [19] we know that any $L$-lipschitz function of a
Gaussian R.V. is sub-Gaussian. As a result, we have

$\displaystyle\mathbb{E}_{\boldsymbol{z}_{i}^{\prime}}\left[e^{\lambda
g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(z_{i}^{\prime
1},z_{i}^{\prime 2},\cdots,z_{i}^{\prime m}\right)}\right]\leq$
$\displaystyle\quad e^{\frac{4\pi^{2}d_{\mathcal{S}}^{2}\lambda^{2}}{8}}.$
(37)

From inequalities 37, 35 and equation 33 we have:

$\mathbb{P}\left(\frac{\sigma\sqrt{2}}{2m}\sum_{i=1}^{m}{g_{\boldsymbol{\phi_{2i}},\boldsymbol{\phi_{2i-1}}}\left(\boldsymbol{z}_{i}\right)}\leq-\epsilon\right)\leq\min_{\lambda\geq
0}\frac{\mathbb{E}_{\boldsymbol{\phi_{1}},\cdots\boldsymbol{\phi_{2m}}}\left[e^{\frac{\lambda^{2}\pi^{2}d_{\mathcal{S}}^{2}\sigma^{2}}{2m}\cdot}\right]}{e^{\lambda\epsilon}}\leq
e^{-\frac{m\epsilon^{2}}{2\pi^{2}d_{\mathcal{S}}^{2}\sigma^{2}}}.$ (38)

Then if we have $2m\geq
144\underline{\theta}^{4}e^{4}\left(\frac{\left(K+1\right)\left(K+2\right)}{K}\right)^{2}\log{\frac{6}{\delta}}$,
i.i.d samples, then with probability at least $1-\frac{\delta}{6}$ we have:

$\frac{1}{2m}\sum_{i=1}^{m}{\left(\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i}-\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{2i-1}\right)^{T}\left(\boldsymbol{z}_{2i}-\boldsymbol{z}_{2i-1}\right)}\geq-\frac{\pi\sigma
K^{2}\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)}{6e^{2}\underline{\theta}(K+2)(K+1)}.$
(39)

Now from inequalities 30,32, 39 and equation 21 we have:

$\displaystyle\mathrm{D}\geq$
$\displaystyle\frac{K^{2}\mathrm{Vol}^{\frac{2}{K}}\left(\mathcal{S}\right)}{4e^{2}(K+1)(K+2)}+(K-2)\sigma^{2}-\frac{K^{2}\sigma\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)}{e^{2}\underline{\theta}(K+2)(K+1)}$
$\displaystyle\geq$
$\displaystyle\frac{K^{2}\mathrm{Vol}^{\frac{2}{K}}\left(\mathcal{S}\right)}{4(K+1)(K+2)e^{2}}\left(1+4e^{2}\frac{(K-2)(K+1)(K+2)}{K^{2}}\frac{\sigma^{2}}{\mathrm{Vol}^{\frac{2}{K}}\left(\mathcal{S}\right)}-\frac{4\sigma}{\underline{\theta}\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)}\right)$
$\displaystyle\geq$
$\displaystyle\frac{K^{2}\mathrm{Vol}^{\frac{2}{K}}\left(\mathcal{S}\right)}{4(K+1)(K+2)e^{2}}\left(1+\frac{4e^{2}(K-2)}{\mathrm{SNR}^{2}}-\frac{4}{\underline{\theta}\mathrm{SNR}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{d^{2}_{\mathcal{S}}}{4\underline{\theta}^{2}(K+1)(K+2)e^{2}}\left[\left(1-\frac{2}{\underline{\theta}\mathrm{SNR}}\right)^{2}+\frac{4}{\mathrm{SNR}^{2}}\left(e^{2}(K-2)-\frac{1}{\underline{\theta}^{2}}\right)\right].$
(40)

From the inequality 40 it can be seen that if we have $2m\geq
144\underline{\theta}^{4}e^{4}\left(\frac{\left(K+1\right)\left(K+2\right)}{K}\right)^{2}\log{\frac{6}{\delta}}$
then the following inequality with probability at least $1-\delta/2$ give an
upper bound for the maximum distance between two points in the simplex
$\mathcal{S}$:

$d_{\mathcal{S}}\leq\sqrt{\frac{4e^{2}(K+1)(K+2)\cdot\underline{\theta}^{2}\cdot\mathrm{D}}{1+\frac{4e^{2}(K-2)}{\mathrm{SNR}^{2}}-\frac{4}{\underline{\theta}\mathrm{SNR}}}}=\mathrm{R}.$
(41)

In the same way we could also give an upper bound for
$\mathrm{D}\left(\mathrm{S}\right)$. The following inequalities hold with
probability more than $1-\delta/2$:

$\displaystyle\mathrm{D}\left(\mathrm{S}\right)\leq$
$\displaystyle\frac{d_{\mathrm{S}}^{2}}{2}+\sigma^{2}(K+2)+\frac{K^{2}\sigma\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)}{e^{2}\underline{\theta}(K+2)(K+1)}$
$\displaystyle\leq$
$\displaystyle\frac{K^{2}\underline{\theta}^{2}\mathrm{Vol}^{\frac{2}{K}}\left(\mathcal{S}\right)}{2}+\sigma^{2}(K+2)+\frac{\sigma\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)}{e^{2}\underline{\theta}}$
$\displaystyle\leq$
$\displaystyle(K+2)^{2}\left(\underline{\theta}\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)+\sigma\right)^{2}$
$\displaystyle\leq$
$\displaystyle(K+2)^{2}\underline{\theta}^{2}\mathrm{Vol}^{\frac{2}{K}}\left(\mathcal{S}\right)\left(1+\frac{1}{\underline{\theta}\mathrm{SNR}}\right)^{2}.$
(42)

Based on equation 41 and inequation in 42, we can give an upper bound for the
radius $\mathrm{R}$ in 41. The following inequality holds with probability at
least $1-\delta$:

$\displaystyle\mathrm{R}\leq\frac{2e\underline{\theta}^{2}(K+2)\sqrt{(K+1)(K+2)}\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)\left(1+\frac{1}{\underline{\theta}\mathrm{SNR}}\right)}{\sqrt{1+\frac{4e^{2}(K-2)}{\mathrm{SNR}^{2}\left(\mathcal{S}\right)}-\frac{4}{\underline{\theta}\mathrm{SNR}\left(\mathcal{S}\right)}}}.$
(43)

Now the only thing we should do is to find a point inside of the simplex. To
do this we define a new statistic $\mathrm{\boldsymbol{p}}$ as follows:

$\displaystyle\mathrm{\boldsymbol{p}}$
$\displaystyle=\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{x}_{i}}=\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{i}+\boldsymbol{z}_{i}}=\boldsymbol{V}_{\mathcal{S}}\left(\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{\phi}_{i}}\right)+\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{z}_{i}}=\mathrm{I}+\mathrm{II}$
(44)

It is clear that ‘’I” is placed inside of the true simplex. So the distance
between $\mathrm{\boldsymbol{p}}$ and a point inside the main simplex can be
calculated as follows:

$\displaystyle\min_{\boldsymbol{x}\in\mathcal{S}}{\left\|\mathrm{\boldsymbol{p}}-\boldsymbol{x}\right\|_{2}}$
$\displaystyle\leq\left\|\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{z}_{i}}\right\|_{2}.$
(45)

In the above equation $\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{z}_{i}}$, is a
zero mean Gaussian random vector with covariance matrix
$\frac{\sigma^{2}}{2m}\boldsymbol{I}$, therefore
$\|\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{z}_{i}}\|_{2}^{2}$ is a chi-squared
random variable with $K$ degrees of freedom, and so we can write concentration
inequality for it:

$\displaystyle\mathrm{P}\left[\left|\left\|\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{z}_{i}}\right\|_{2}^{2}-\frac{K\sigma^{2}}{2m}\right|\geq\epsilon\right]\leq
2e^{-\frac{m^{2}\epsilon^{2}}{2K\sigma^{4}}}.$ (46)

Then with probability at least $1-\delta$ we have the following inequality:

$\displaystyle\min_{\boldsymbol{x}\in\mathcal{S}}{\|\mathrm{\boldsymbol{p}}-\boldsymbol{x}\|_{2}^{2}}\leq$
$\displaystyle\quad\frac{K\sigma^{2}}{2m}+\frac{\sigma^{2}}{m}\sqrt{2K\log{\frac{2}{\delta}}}$
$\displaystyle\leq$
$\displaystyle\quad\frac{K\sigma^{2}}{m}\log{\frac{2}{\delta}}$ (47)

Now if we have $2m\geq
144\underline{\theta}^{4}e^{4}\left(\frac{\left(K+1\right)\left(K+2\right)}{K}\right)^{2}\log{\frac{6}{\delta}}$,
then we can rewrite the above inequality as follows:

$\displaystyle\min_{\boldsymbol{x}\in\mathcal{S}}{\|\boldsymbol{p}-\boldsymbol{x}\|_{2}}\leq\quad\frac{\sigma}{\underline{\theta}^{2}e^{2}\sqrt{K}}$
(48)

As we mentioned earlier, the first part in the right hand side of the
inequality 44 ,
$\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{i}}$,
belongs to the interior of the simplex. Then a $K$-dimensional sphere with
radius $R$ and centered at this point, with probability at least $1-\delta$
contains the simplex $\mathcal{S}$. However, in the process of learning we do
not have access to the noiseless data and thus cannot have such a point as the
center of the sphere. Let us show the distance between $\boldsymbol{p}$ and
$\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{V}_{\mathcal{S}}}$ with $d$. Then, it
is clear to see that the $K$-dimensional sphere with radius $R+d$ and center
point $\boldsymbol{p}$, contains the sphere with center point at
$\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{i}}$
and radius $R$. So any simplex which is placed in sphere
$\mathrm{C}^{K}(\frac{1}{2m}\sum_{i=1}^{2m}{\boldsymbol{V}_{\mathcal{S}}\boldsymbol{\phi}_{i}},R)$
is also placed in sphere $\mathrm{C}^{K}(\boldsymbol{p},R+d)$.

So we conclude that if we have $2m\geq
144\underline{\theta}^{4}e^{4}\left(\frac{\left(K+1\right)\left(K+2\right)}{K}\right)^{2}\log{\frac{6}{\delta}}$
i.i.d. samples from $\mathbb{G}_{\mathcal{S}}$ then the main simplex
$\mathcal{S}$ with probability more than or equal to $1-\delta$ will be
confined in a $K$-dimensional sphere with center point at $\boldsymbol{p}$ and
with radius $R$:

$\displaystyle\mathrm{R}=~{}$
$\displaystyle\sqrt{\frac{4e^{2}(K+1)(K+2)\underline{\theta}^{2}\mathrm{D}}{1+\frac{4e^{2}(K-2)}{\mathrm{SNR}^{2}}-\frac{4}{\underline{\theta}\mathrm{SNR}}}}+\frac{\sigma}{\underline{\theta}^{2}e^{2}\sqrt{K}}$
$\displaystyle\leq$
$\displaystyle~{}\sqrt{\frac{4e^{2}(K+1)(K+2)\underline{\theta}^{2}\mathrm{D}}{1+\frac{4e^{2}(K-2)}{\mathrm{SNR}^{2}}-\frac{4}{\underline{\theta}\mathrm{SNR}}}}\left(1+\frac{\bar{\theta}}{\underline{\theta}^{2}e^{2}\sqrt{K}}\right)$
(49)

This completes the proof. ∎

###### proof of Lemma $2$.

Consider a $\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric
$K$-simplex $\mathcal{S}$, which is bounded in a sphere
$\mathrm{C}^{K}(\boldsymbol{p},R)$. It is clear that all vertices of this
simplex $\left\\{\boldsymbol{v}_{1},\ldots,\boldsymbol{v}_{K+1}\right\\}$ are
placed in $\mathrm{C}^{K}(\boldsymbol{p},R)$. From the definition of
$\mathrm{T}_{\frac{\alpha\epsilon}{K+1}}(\mathrm{C}^{K}(\boldsymbol{p},R))$,
we know that for each vertex of the simplex $\boldsymbol{v}_{i}$, there exists
some
$\boldsymbol{v}_{i}^{\prime}\in\mathrm{T}_{\frac{\alpha\epsilon}{K+1}}(\mathrm{C}^{K}(\boldsymbol{p},R))$
such that
$\|\boldsymbol{v}_{i}-\boldsymbol{v}_{i}^{\prime}\|_{2}\leq\frac{\alpha\epsilon}{K+1}$.
Assume for each vertex $\boldsymbol{v}_{i}$ of $\mathcal{S}$, we denote its
closest point in
$\mathrm{T}_{\frac{\alpha\epsilon}{K+1}}(\mathrm{C}^{K}(\boldsymbol{p},R))$ as

$\hat{\boldsymbol{v}}_{i}=\operatorname*{\arg\\!\min}\left\\{\|\boldsymbol{v}_{i}-\hat{\boldsymbol{v}}\|_{2}\bigg{|}~{}\hat{\boldsymbol{v}}\in\mathrm{T}_{\frac{\alpha\epsilon}{K+1}}(\mathrm{C}^{K}(\boldsymbol{p},R))\right\\}.$

Using these points we make a new simplex $\widehat{\mathcal{S}}$. It is clear
that $\widehat{\mathcal{S}}$ belongs to
$\widehat{\mathbb{S}}\left(\mathrm{C}^{K}(\boldsymbol{p},R)\right)$. Assume
$f_{\mathcal{S}}$ and $f_{\hat{\mathcal{S}}}$ denote the probability density
functions that correspond to $\mathcal{S}$ and $\widehat{\mathcal{S}}$,
respectively. Then, the TV-distance between $f_{\mathcal{S}}$ and
$f_{\widehat{\mathcal{S}}}$ can be written and bounded as

$\displaystyle\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}},\mathbb{P}_{\widehat{\mathcal{S}}}\right)=$
$\displaystyle~{}\sup_{A}~{}{\mathbb{P}_{\mathcal{S}}\left(A\right)-\mathbb{P}_{\widehat{\mathcal{S}}}\left(A\right)}$
$\displaystyle=$
$\displaystyle\int_{\boldsymbol{x}\in\\{x^{\prime}:f_{\mathcal{S}}\left(\boldsymbol{x}^{\prime}\right)\geq
f_{\widehat{\mathcal{S}}}\left(\boldsymbol{x}^{\prime}\right)\\}}{f_{\mathcal{S}}\left(\boldsymbol{x}\right)-f_{\widehat{\mathcal{S}}}\left(\boldsymbol{x}\right)}$
$\displaystyle=$
$\displaystyle\int_{\boldsymbol{x}\in\mathcal{S}-\widehat{\mathcal{S}}}{f_{\mathcal{S}}\left(\boldsymbol{x}\right)-f_{\widehat{\mathcal{S}}}\left(\boldsymbol{x}\right)}+\left(\int_{\boldsymbol{x}\in\mathcal{S}\cap\widehat{\mathcal{S}}}{f_{\mathcal{S}}\left(\boldsymbol{x}\right)-f_{\widehat{\mathcal{S}}}\left(\boldsymbol{x}\right)}\right)\boldsymbol{\mathrm{1}}\left(\mathrm{Vol}\left(\mathcal{S}\right)\leq\mathrm{Vol}\left(\widehat{\mathcal{S}}\right)\right)$
$\displaystyle\leq$
$\displaystyle\int_{\boldsymbol{x}\in\mathcal{S}-\widehat{\mathcal{S}}}{f_{\mathcal{S}}\left(\boldsymbol{x}\right)-f_{\widehat{\mathcal{S}}}\left(\boldsymbol{x}\right)}+\int_{\boldsymbol{x}\in\mathcal{S}\cap\widehat{\mathcal{S}}}{\bigg{|}f_{\mathcal{S}}\left(\boldsymbol{x}\right)-f_{\widehat{\mathcal{S}}}\left(\boldsymbol{x}\right)\bigg{|}}$
$\displaystyle=$
$\displaystyle\frac{\mathrm{Vol}\left(\mathcal{S-\widehat{S}}\right)}{\mathrm{Vol}\left(S\right)}+\mathrm{Vol}\left(\mathcal{S}\cap\widehat{\mathcal{S}}\right)\bigg{|}\frac{1}{\mathrm{Vol}(\mathcal{S})}-\frac{1}{\mathrm{Vol}(\widehat{\mathcal{S}})}\bigg{|},$
(50)

where $\mathcal{S}-\widehat{\mathcal{S}}$ shows the set difference between
$\mathcal{S}$ and $\widehat{\mathcal{S}}$. Let us denote the two terms in the
r.h.s. of 50 as $\mathrm{I}$ and $\mathrm{II}$, respectively. To find an
upper-bound for the $\mathrm{TV}$-distance in 50 we find respective upper-
bounds for $\mathrm{I}$ and $\mathrm{II}$. In order to do so, first let us
discuss about $\mathrm{I}$:

$\displaystyle\mathrm{I}=\frac{\mathrm{Vol}\left(\mathcal{S-\widehat{S}}\right)}{\mathrm{Vol}\left(S\right)}.$
(51)

The distance between vertices of $\mathcal{S}$ and $\widehat{\mathcal{S}}$ are
less than $\frac{\alpha\epsilon}{K+1}$, then the maximal difference set (in
terms of volume) between $\mathcal{S}$ and $\widehat{\mathcal{S}}$ can be
bounded as follows: simplex has $K+1$ facets, and the difference set that can
occur from altering each of them is upper-bounded as
$\leq\mathcal{A}_{i}\left(\mathcal{S}\right)\times\alpha\epsilon/(K+1)$, where
$i=1,\ldots,K+1$ denotes the facet index. This way, for $\mathrm{I}$ we have:

$\displaystyle\mathrm{I}\leq$
$\displaystyle~{}\sum_{i=1}^{K+1}{\frac{\alpha\epsilon}{K+1}\frac{\mathcal{A}_{i}\left(\mathcal{S}\right)}{\mathrm{Vol}\left(\mathcal{S}\right)}}$
$\displaystyle\leq$
$\displaystyle~{}\alpha\epsilon\mathcal{A}_{max}\left(\mathcal{S}\right)$
$\displaystyle\leq$
$\displaystyle~{}\alpha\epsilon\bar{\theta}\mathrm{Vol}^{\frac{1}{K}},$ (52)

where $\mathcal{A}_{max}\left(\mathcal{S}\right)$ is the volume of the largest
facet of $\mathcal{S}$. In the final inequality of 52, we take advantage of
the isoperimetricity property of $\mathcal{S}$. Next, we should find an upper-
bound for the second term in the r.h.s. of 50, i.e., $\mathrm{II}$:

$\mathrm{II}=\mathrm{Vol}\left(\mathcal{S}\cap\widehat{\mathcal{S}}\right)\bigg{|}\frac{1}{\mathrm{Vol}(\mathcal{S})}-\frac{1}{\mathrm{Vol}(\widehat{\mathcal{S}})}\bigg{|}.$
(53)

To find an upper-bound for $\mathrm{II}$ we should find an upper-bound for
$\mathrm{Vol}\left(\widehat{\mathcal{S}}\right)$. To do so, we create a
“rounded" simplex $\mathcal{S}^{r}$ which forms by adding a $K$-dimensional
sphere with radius $r=\frac{\alpha\epsilon}{K+1}$ to the original simplex
$\mathcal{S}$. It can be shown that $\widehat{\mathcal{S}}$ is definitely
placed inside $\mathcal{S}^{r}$ and therefore
$\mathrm{Vol}(\hat{\mathcal{S}})\leq\mathrm{Vol}(\mathcal{S}^{r})$. In this
regard, we have

$\displaystyle\mathrm{II}=$
$\displaystyle~{}\mathrm{Vol}\left(\mathcal{S}\cap\widehat{\mathcal{S}}\right)\bigg{|}\frac{1}{\mathrm{Vol}(\mathcal{S})}-\frac{1}{\mathrm{Vol}(\hat{\mathcal{S}})}\bigg{|}$
$\displaystyle\leq$
$\displaystyle~{}\bigg{|}\frac{\mathrm{Vol}(\hat{\mathcal{S}})-\mathrm{Vol}(\mathcal{S})}{\mathrm{Vol}(\mathcal{S})}\bigg{|}$
$\displaystyle\leq$
$\displaystyle~{}\bigg{|}\frac{\mathrm{Vol}(\mathcal{S}^{r})-\mathrm{Vol}(\mathcal{S})}{\mathrm{Vol}(\mathcal{S})}\bigg{|}$
$\displaystyle\leq$
$\displaystyle~{}\left(\sum_{i=1}^{K+1}{\frac{\alpha\epsilon}{K+1}\mathcal{A}_{i}\left(\mathcal{S}\right)}+(K+1)\mathcal{C}_{\alpha}\left(\frac{\alpha\epsilon}{K+1}\right)^{K}\right)\frac{1}{\mathrm{Vol}(\mathcal{S})}$
$\displaystyle\leq$
$\displaystyle~{}\left((K+1)\frac{\alpha\epsilon}{K+1}\mathcal{A}_{\max}\left(\mathcal{S}\right)+(K+1)\mathcal{C}_{\alpha}\left(\frac{\alpha\epsilon}{K+1}\right)^{K}\right)\frac{1}{\mathrm{Vol}(\mathcal{S})}$
$\displaystyle\leq$
$\displaystyle~{}2\alpha\epsilon\bar{\theta}\mathrm{Vol}^{\frac{1}{K}},$ (54)

where $\mathcal{C}_{\alpha}\left(\frac{\alpha\epsilon}{K+1}\right)^{K}$ is the
volume of a $K$-dimensional sphere with radius $r=\frac{\alpha\epsilon}{K+1}$.
Now, using 52 and 54 we have

$\displaystyle\mathrm{TV}\left(\mathbb{P}_{\mathcal{S}},\mathbb{P}_{\widehat{\mathcal{S}}}\right)\leq
3\alpha\epsilon\bar{\theta}\mathrm{Vol}^{\frac{1}{K}}\leq\frac{3}{5}\epsilon\leq\epsilon.$
(55)

From 55, it can be seen that for any
$\left(\underline{\theta},\bar{\theta}\right)$-isoperimetric simplex
$\mathcal{S}$ which is bounded in a $K$-dimensional sphere
$\mathrm{C}^{K}(\boldsymbol{p},R)$, there exists at least one simplex in
$\widehat{\mathbb{S}}(\mathrm{C}^{K}(\boldsymbol{p},R))$ within a TV-distance
of $\epsilon$ from $\mathcal{S}$. Thus the proof is complete.

In the end, it is worth mentioning one possible method to build an
$\epsilon$-covering set for a $K$-dimensional sphere
$\mathrm{C}^{K}(\boldsymbol{p},R)$. Although there exists deterministic ways
to build this set, an alternative approach is by uniformly sampling points
from the sphere. Consider an $\epsilon/2$-packing set with size $L$ for the
sphere. Based on the result of the “coupon collector problem" we know that
having $L\log(L)$ uniform samples from the sphere guarantees with high
probability that there exists at least one sample within a distance of
$\epsilon/2$ from each element of the packing set. Therefore, the resulting
samples are an $\epsilon$-covering set for the sphere. Hence, the cardinality
of an $\epsilon$-covering set built in this way is at most
$\left(1+\frac{4R}{\epsilon}\right)^{2K}$. ∎

###### proof of Lemma $3$.

For the TV-distance between a noisy simplex and its noiseless version, we have

$\displaystyle\mathrm{TV}\left(\mathbb{G}_{\mathcal{S}},\mathbb{P}_{\mathcal{S}}\right)=$
$\displaystyle~{}\sup_{\mathrm{A}}~{}\left({\mathbb{P}_{\mathcal{S}}\left(\mathrm{A}\right)-\mathbb{G}_{\mathcal{S}}\left(\mathrm{A}\right)}\right)$
$\displaystyle=$
$\displaystyle~{}\int_{\boldsymbol{x}\in\mathcal{S}}{\left(\frac{1}{\mathrm{Vol}\left(\mathcal{S}\right)}-\frac{1}{\mathrm{Vol}\left(\mathcal{S}\right)}\int_{\boldsymbol{y}\in\mathcal{S}}{\left(\frac{1}{(2\pi)^{\frac{K}{2}}\sigma^{K}}e^{-\frac{\|x-y\|_{2}^{2}}{2\sigma^{2}}}\right)\mathrm{d}y}\right)\mathrm{d}x}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{\mathrm{Vol}\left(\mathcal{S}\right)}\int_{\boldsymbol{x}\in\mathcal{S}}{\left(1-\int_{\boldsymbol{y}\in\mathcal{S}}{\left(\frac{1}{(2\pi)^{\frac{K}{2}}\sigma^{K}}e^{-\frac{\|x-y\|_{2}^{2}}{2\sigma^{2}}}\right)\mathrm{d}y}\right)\mathrm{d}x}.$
(56)

In the above equations, the inner integral which is on $\boldsymbol{y}$
calculates the probability of a Gaussian random vector with mean
$\boldsymbol{x}$ and covariance matrix $\sigma^{2}\boldsymbol{I}$ takes values
inside the simplex $\mathcal{S}$. To find an upper-bound for the TV-distance
in equation 56, first we need to lower-bound this part. For a Gaussian random
vector $\boldsymbol{y}$ with mean $\boldsymbol{x}$ and covariance matrix
$\sigma^{2}\boldsymbol{I}$, with probability at least $1-\delta/3$ we have
(Proposition $2.9$ and Example $2.8$ in [19]):

$\|y-x\|_{2}\leq\sigma\sqrt{K+\sqrt{8K\log{\frac{3}{\delta}}}}.$ (57)

This way, one can write:

$\int_{\boldsymbol{y}\in\mathcal{S}}{\left(\frac{1}{(2\pi)^{\frac{K}{2}}\sigma^{K}}e^{-\frac{\|x-y\|_{2}^{2}}{2\sigma^{2}}}\right)\mathrm{d}y}\geq\left(1-\frac{\delta}{3}\right)\cdot\mathrm{\boldsymbol{1}}\left(\mathbb{B}\left(\boldsymbol{x},\sigma\sqrt{K+\sqrt{8K\log{\frac{3}{\delta}}}}\right)\in\mathcal{S}\right),$
(58)

where $\mathbb{B}\left(\boldsymbol{p},r\right)$ is a norm ball with radius
$r$, and center point $\boldsymbol{p}$. For each point $\boldsymbol{x}$ inside
of the simplex $\mathcal{S}$, consider a norm ball with center point
$\boldsymbol{x}$ and radius $\sigma\sqrt{K+\sqrt{8K\log{\frac{3}{\delta}}}}$.
If this norm ball does not completely fit inside the simplex, we put
$\boldsymbol{x}$ in a set called $\tilde{\mathcal{S}}$. We put inequality 58
in the equation 56 and give an upper bound for the TV-distance:

$\displaystyle\mathrm{TV}\left(\mathbb{G}_{\mathcal{S}},\mathbb{P}_{\mathcal{S}}\right)=$
$\displaystyle~{}\frac{1}{\mathrm{Vol}\left(\mathcal{S}\right)}\int_{\boldsymbol{x}\in\mathcal{S}}{\left(1-\int_{\boldsymbol{y}\in\mathcal{S}}{\left(\frac{1}{(2\pi)^{\frac{K}{2}}\sigma^{K}}e^{-\frac{\|x-y\|_{2}^{2}}{2\sigma^{2}}}\right)\mathrm{d}y}\right)\mathrm{d}x}$
$\displaystyle\leq$
$\displaystyle~{}\frac{\mathrm{Vol}\left(\mathcal{S}\right)-\mathrm{Vol}\left(\tilde{\mathcal{S}}\right)}{\mathrm{Vol}\left(\mathcal{S}\right)}\frac{\delta}{3}+\frac{\mathrm{Vol}\left(\tilde{\mathcal{S}}\right)}{\mathrm{Vol}\left(\mathcal{S}\right)}$
$\displaystyle\leq$
$\displaystyle~{}\frac{\delta}{3}+\frac{(K+1)\mathcal{A}_{\mathrm{max}}\left(\mathcal{S}\right)}{\mathrm{Vol}\left(\mathcal{S}\right)}\sigma\sqrt{K+\sqrt{8K\log{\frac{3}{\delta}}}}$
$\displaystyle\leq$
$\displaystyle~{}\frac{\delta}{3}+\frac{(K+1)\bar{\theta}}{\mathrm{Vol}^{\frac{1}{K}}\left(\mathcal{S}\right)}\sigma\sqrt{K+\sqrt{8K\log{\frac{3}{\delta}}}}$
$\displaystyle\leq$
$\displaystyle~{}\frac{\delta}{3}+\frac{(K+1)\bar{\theta}}{\mathrm{SNR}}\sqrt{K+\sqrt{8K\log{\frac{3}{\delta}}}},$
(59)

where $\mathcal{A}_{\mathrm{max}}\left(\mathcal{S}\right)$ is the largest
facet of the simplex and $\mathrm{SNR}$ stands for the signal to noise ratio
for the noisy simplex $\mathbb{G}_{\mathcal{S}}$ and calculated as follows:

$\mathrm{SNR}=\frac{\mathrm{Vol}^{1/K}\left(\mathcal{S}\right)}{\sigma}.$ (60)

Inequality 59 holds for any $\delta>0$. Therefore, by replacing $\delta$ with
$\frac{3(K+1)}{\delta}$ we have

$\mathrm{TV}\left(\mathbb{G}_{\mathcal{S}},\mathbb{P}_{\mathcal{S}}\right)\leq
3\frac{(K+1)\bar{\theta}}{\mathrm{SNR}}\sqrt{K+\sqrt{8K\log{\frac{3}{\delta}}}}.$
(61)

Therefore, the proof is complete. ∎