# Concentration bounds for the empirical angular measure with statistical
learning applications

Stéphan<EMAIL_ADDRESS>[ Hamid
<EMAIL_ADDRESS>[ Anne
<EMAIL_ADDRESS>[ Johan
<EMAIL_ADDRESS>[ Institut polytechnique de Paris and
UCLouvain  LTCI, Télécom Paris, Institut polytechnique de Paris
LIDAM/ISBA, UCLouvain,

###### Abstract

The angular measure on the unit sphere characterizes the first-order
dependence structure of the components of a random vector in extreme regions
and is defined in terms of standardized margins. Its statistical recovery is
an important step in learning problems involving observations far away from
the center. In the common situation when the components of the vector have
different distributions, the rank transformation offers a convenient and
robust way of standardizing data in order to build an empirical version of the
angular measure based on the most extreme observations. However, the study of
the sampling distribution of the resulting empirical angular measure is
challenging. It is the purpose of the paper to establish finite-sample bounds
for the maximal deviations between the empirical and true angular measures,
uniformly over classes of Borel sets of controlled combinatorial complexity.
The bounds are valid with high probability and scale essentially as the square
root of the effective sample size, up to a logarithmic factor. Discarding the
most extreme observations yields a truncated version of the empirical angular
measure for which the logarithmic factor in the concentration bound is
replaced by a factor depending on the truncation level. The bounds are applied
to provide performance guarantees for two statistical learning procedures
tailored to extreme regions of the input space and built upon the empirical
angular measure: binary classification in extreme regions through empirical
risk minimization and unsupervised anomaly detection through minimum-volume
sets of the sphere.

62G05,

62G30,

62G32,

62H30,

angular measure,

classification,

concentration inequality,

extreme value statistics,

minimum-volume sets,

ranks,

###### keywords:

[class=MSC]

###### keywords:

, , and

##  1 Learning from multivariate extremes

Estimation and prediction problems regarding the extremal behavior of a random
vector $X=(X_{1},\ldots,X_{d})$ are of key importance for risk assessment in
finance, insurance, engineering and environmental sciences and, recently, for
the analysis of weak signals in machine learning. A standard assumption to
model the joint upper tail of $X$ is that its distribution lies in the maximal
domain of attraction of a multivariate extreme value distribution. This
assumption comprises two parts:

  1. (i)

the marginal distributions of $X$ belong to the maximal domains of attraction
of some univariate extreme value distributions;

  2. (ii)

after marginal transformation of $X$ through the probability integral
transform or a variation thereof, the joint distribution of the transformed
vector belongs to the maximal domain of attraction of a multivariate extreme
value distribution with pre-specified margins.

Under the side assumption that the marginal distributions of $X$ are
continuous, point (ii) above only involves the copula of $X$. Point (ii) can
be imposed on its own, that is, independently of the assumptions on the
margins in point (i), and this is what we will do in this paper.

#### The angular measure for multivariate extremes

The multivariate extreme value distribution in point (ii) is determined by a
finite Borel measure, $\Phi$, with support contained in the intersection of
$[0,\infty)^{d}$ with the unit sphere on $\mathbb{R}^{d}$ with respect to some
norm. This so-called angular measure, originally called spectral measure in
[17], describes the first-order dependence structure of joint extremes of $X$
and is rooted in the theory of multivariate regular variation [42]. Since
then, it has been recognized that the modelling of extremal dependence may
require finer assumptions than the traditional maximal domain of attraction
condition, leading for instance to conditional extreme value models and the
theory of hidden regular variation; see for instance [12, 50] and the
references therein. Here, we focus on inference on the angular measure $\Phi$.

Inference on the angular measure is an important problem in extreme value
analysis. It plays a part in the construction of confidence intervals for rare
event probabilities [15, 18]. It lies at the basis for a test of the
hypothesis that a bivariate distribution is in the maximum domain of
attraction of an extreme value distribution [22]. It serves to model the
action of a covariate on the extremal dependence of a baseline distribution
through a density ratio model [13, 7]. The angular density is also at the
basis of an estimator of bivariate tail quantile regions [21]. Bounds for
probabilities of joint excesses over high thresholds that are robust against
misspecification of the angular measure are derived in [26]. The angular
measure underlies techniques to find groups of variables exhibiting extremal
dependence, with dimension reduction and sparse representations as objectives
[8, 39, 37]; see [27] for a review. In [35], the spherical $k$-means algorithm
applied to a sample from the angular measure yields prototypes of extremal
dependence.

Furthermore, the angular measure is helpful for solving supervised and
unsupervised learning tasks for sample points far away from the center of the
distribution. In the spirit of principal component analysis, the
eigendecomposition of the Gram matrix of the angular measure yields low-
dimensional summaries of extremal dependence [11, 19]. Anomalous data can be
detected from unusual combinations of variables being large simultaneously
[31] or from their lack of membership of minimum-volume sets of the unit
sphere containing a large fraction of the total mass of the angular measure
[47]. Binary classification in extreme regions can be performed on the basis
of the differences between the intra-class angular measures of the explanatory
variables [34].

#### The empirical angular measure

For a given dimension $d$, the collection of all angular measures is subject
only to some moment constraints stemming from the marginal standardization of
$X$ but does not form a parametric family. The usual considerations in favor
of and against the use of parametric versus non-parametric methods therefore
apply. Many parametric models have been proposed [9, 10] and new ones continue
to be invented, with a growing emphasis on the use of flexible models almost
of a semi-parametric nature [3, 45, 44].

Our focus is on non-parametric estimation and inference via the empirical
angular measure, $\widehat{\Phi}$, introduced in [23] although already alluded
to some years earlier in [15] and [18]. Given a random sample from an unknown
distribution, the marginal standardization mentioned in point (ii) above is
done by means of the empirical cumulative distribution functions. As a result,
the estimator depends on the data only through the ranks. On the one hand, the
use of ranks makes the method robust. On the other hand, the additional
dependence stemming from the ranks greatly complicates the study of the
sampling distribution of the estimator. In fact, its asymptotic distribution
is known only in the bivariate case [23, 25]. In higher dimensions, all that
seems to be known is its consistency [35, Proof of Proposition 3.3].

Variations on the empirical angular measure enforce the aforementioned moment
constraints through empirical or Euclidean likelihoods [25, 14] as well as a
folding technique [32]. Other variations exploit more specific assumptions on
the marginal distributions to estimate them differently than by the empirical
distribution functions, for instance by fitting generalized Pareto
distributions to the univariate tails [24]. Sometimes, asymptotic results are
established as if the marginal distributions are known. In our paper, we focus
on the original, rank-based empirical angular measure and we make no
assumptions on the unknown marginal cumulative distribution functions except
for their continuity.

#### Concentration inequalities

It is the main goal of this paper to carry out a non-asymptotic analysis of
the empirical angular measure $\widehat{\Phi}$, which, to the best knowledge,
is the first of its kind. The concentration inequality established in our main
result, Theorem 3.1, states that with a certain large probability $1-\delta$
the estimation error is not larger than a certain small quantity depending,
among other things, on $\delta$ and on the number, $k$, of sample points used
in the definition of the estimator. The bound concerns the largest estimation
error

$\sup_{A\in\mathcal{A}}\lvert\widehat{\Phi}(A)-\Phi(A)\rvert$ (1)

over classes $\mathcal{A}$ of Borel subsets $A$ of the unit sphere satisfying
certain properties. In particular, the complexity of $\mathcal{A}$ comes into
play via the Vapnik–Chervonenkis dimension of a collection of sets constructed
from $\mathcal{A}$. The proof of the concentration inequality combines two
tools: first, the use of framing sets to capture certain random sets, as in
[23] and [25], although the framing sets are defined in a different manner
here; and second, a concentration inequality for rare events borrowed from
[30].

The main term in the concentration bound is of the order $\log(k)/\sqrt{k}$
and stems from the most extreme observations. Asymptotic theory for the
empirical angular measure in the bivariate case [23, 25] suggest a learning
rate of the order $1/\sqrt{k}$. Whether our logarithmic term is an artefact of
our analysis or rather a genuine property of the estimator we do not know.
However, this motivates our second contribution, which is a truncated version
of the empirical angular measure, whereby the most extreme observations are in
some sense discarded, the rule depending on a tuning parameter $M>1$. The
concentration bound of the resulting truncated empirical angular measure
$\widehat{\Phi}_{M}$ in Theorem 3.2 has a main term proportional to
$(1-1/M)^{-1}\log(M)/\sqrt{k}$.

Although the angular measure $\Phi$ can be studied with respect to any norm on
$\mathbb{R}^{d}$, this study is limited to the supremum norm
$\lVert{x}\rVert=\max(|x_{1}|,\ldots,|x_{d}|)$ for $x\in\mathbb{R}^{d}$. The
supremum norm has the advantage that its value is not affected by the precise
values of the smaller coordinates of $x$. The faces of the unit sphere induced
by the supremum norm are parallel to the coordinate axes, a property that
links up well with the use of component-wise ranks. Extensions to more general
norms are expected to involve substantial additional complications, the study
of which is left for further research.

In numerical experiments, we compare the actual performance of the empirical
angular measure and the truncated counterpart. We find that neither estimator
dominates the other. The non-negligible impact of the rank transformation is
illustrated by comparing the estimators with oracle versions based upon known
marginal distributions.

#### Applications to statistical learning

The concentration bounds for the empirical angular measure are leveraged to
study two statistical learning problems: minimum-volume set estimation and
binary classification in extreme regions. These two problems and the methods
proposed to solve them were introduced in the conference papers [47] and [34],
respectively. In both cases, the method was based upon the empirical angular
measure. However, the technical difficulties inherent to the rank
transformation were ignored and the theoretical analysis was performed as if
the marginal distributions are known. Here, we apply concentration
inequalities for the empirical angular measure to obtain finite-sample
performance guarantees for the rank-based methods.

We briefly describe the two learning problems and the role of the angular
measure. For unsupervised anomaly detection, the learning task can be
formulated as minimum-volume set estimation on the sphere, that is, the
statistical recovery of a Borel set of the sphere with minimum volume but
containing a given, large fraction of the total mass of the angular measure
[47]. Any large observation whose angle lies outside the minimum-volume set is
considered as a potential anomaly. Concentration inequalities for the uniform
estimation error over a class of candidate sets enable us in Section 4.1 to
get statistical guarantees on the minimum-volume set selected within the class
on the basis of an estimator of the angular measure.

The second problem concerns binary classification in extreme regions.
Empirical risk minimization, which is the main paradigm of statistical
learning theory, tends to ignore the predictive performance of candidate
classifiers in low-density regions of the input space. Instead, we focus on
the probability of classification error in such extreme regions. By
controlling the fluctuations of the empirical angular measure, we establish
generalization bounds for classifiers obtained by minimizing the empirical
classification error based on the most extreme input observations only. In
Theorem 4.2, we state a bound on the supremum of the empirical risk over a
class of candidate classifiers.

Numerical experiments on both methods were reported already in the two cited
conference papers, but then for the empirical angular measure with respect to
the sum norm, $\|x\|_{1}=|x_{1}|+\cdots+|x_{d}|$. In Section 5 we investigate
the finite-sample performance in case of the max norm, both with and without
truncation of the largest observations.

#### Outline

The paper is organized as follows. In Section 2, the relevant notions
pertaining to multivariate extreme value analysis are briefly recalled. The
main results related to the non-asymptotic analysis of the empirical angular
measure and its truncated version are formulated in Section 3. Section 4
illustrates the application of the concentration inequalities to two
statistical learning problems, minimum-volume set estimation and binary
classification in extreme regions. Numerical experiments are presented in
Section 5. A discussion in Section 6 concludes the paper. Proofs and some
auxiliary results are deferred to the Supplement.

##  2 Upper tail dependence

We set out some basics of multivariate extreme value theory (Sections 2.1 and
2.2) and recall a rank-based standardization procedure (Section 2.3). Equipped
with these notions, we describe the empirical angular measure and introduce a
truncated variant (Section 2.4). For background, we refer to monographs such
as [42, 2, 16]

###  2.1 Regular variation and exponent measure

Let $X=(X_{1},\ldots,X_{d})$ be a random vector with law $P$ and continuous
marginal cumulative distribution functions
$F_{j}(u)=\operatorname{\mathbb{P}}[{X_{j}\leqslant u}]$ for $u\in\mathbb{R}$.
We standardize each component of $X$ to unit-Pareto margins by a combination
of the probability integral transform and the quantile transform through
$V_{j}=1/(1-F_{j}(X_{j}))$ for $j=1,\ldots,d$.

The working hypothesis in this paper is that the resulting random vector
$V=(V_{1},\ldots,V_{d})$ is multivariate regularly varying; this formalizes
the assumption in point (ii) in the introduction. Specifically, we assume that
there exists a non-zero Borel measure $\mu$ on the punctured orthant
$E=[0,\infty)^{d}\setminus\\{(0,\ldots,0)\\}$ which is finite on Borel sets
bounded away from the origin and such that

$\lim_{t\to\infty}t\operatorname{\mathbb{P}}[{t^{-1}V\in B}]=\mu(B)$ (2)

for all Borel sets $B$ of $E$ bounded away from the origin and such that
$\mu(\partial B)=0$, with $\partial B$ the topological boundary of $B$.
Convergence in (2) for all such $B$ is equivalent to measure convergence
$t\operatorname{\mathbb{P}}[{t^{-1}V\in\,\cdot\,}]\to\mu(\,\cdot\,)$ as
$t\to\infty$ in the space $\mathcal{M}_{0}$ of Borel measures on $E$ that are
finite on Borel sets bounded away from the origin [33]. Specifically, we have
$\lim_{t\to\infty}t\operatorname{\mathbb{E}}[f(t^{-1}V)]=\int_{E}f\mathrm{d}\mu$
for every bounded and continuous real function $f$ on $E$ vanishing in a
neighbourhood of the origin. Alternatively, multivariate regular variation can
be described in the language of vague convergence of Radon measures on the
compactified, punctured orthant $[0,\infty]^{d}\setminus\\{(0,\ldots,0)\\}$
[42, 43].

The measure $\mu$ is referred to as the exponent measure because of its
appearance in the exponent of the expression of the multivariate extreme value
distribution to which the law of $V$ is attracted. The exponent measure is
homogeneous: writing $\lambda A=\\{\lambda x:x\in A\\}$ for $\lambda>0$ and
$A\subseteq\mathbb{R}^{d}$, we have

$\forall\lambda>0,\qquad\mu(\lambda\,\cdot\,)=\lambda^{-1}\mu(\,\cdot\,).$ (3)

Its margins are standardized: by (2) and since the distribution of each
component $V_{j}$ is unit-Pareto, we have

$\forall y\in(0,\infty),\;\forall j\in\\{1,\ldots,d\\},\qquad\mu(\\{x\in
E:x_{j}\geqslant y\\})=y^{-1}.$ (4)

###  2.2 Angular measure with respect to the max norm

Here and throughout, let

$\mathbb{S}=\\{x\in[0,\infty)^{d}:\lVert{x}\rVert=1\\}\quad\text{where}\quad\lVert{x}\rVert=\max(|x_{1}|,\ldots,|x_{d}|).$
(5)

Although the angular measure to be introduced next can be defined with respect
to any norm on $\mathbb{R}^{d}$, the extension of the concentration inequality
in Theorem 3.1 to norms other than the max norm requires significant
additional work, as shall be discussed later, and is left for future research.
Consider the mapping $\theta:E\rightarrow\mathbb{S}$ that assigns to any
vector $x\in E$ its ‘angle’ $\theta(x)=x/\lVert{x}\rVert$.

The angular measure $\Phi$ is defined as the push-forward measure by $\theta$
of the restriction of $\mu$ to $\\{x\in E:\lVert{x}\rVert\geqslant 1\\}$: for
any Borel set $A\subseteq\mathbb{S}$, we have

$\Phi(A)=\mu(\mathcal{C}_{A})\quad\text{where}\quad\mathcal{C}_{A}=\\{x\in
E:\lVert{x}\rVert\geqslant 1,\;\theta(x)\in A\\}.$ (6)

In view of the marginal standardization (4), the total mass of the angular
measure is finite and we have $1\leqslant\Phi(\mathbb{S})\leqslant d$.

The exponent measure $\mu$ is determined by the angular measure: by
homogeneity (3),

$\mu(\\{x\in E:\lVert{x}\rVert\geqslant u,\theta(x)\in A\\})=u^{-1}\Phi(A)$

for every $u>0$ and every Borel set $A\subseteq\mathbb{S}$. More generally,
for any non-negative Borel measurable function $f$ on $E$, we have

$\int_{E}f\,\mathrm{d}\mu=\int_{0}^{\infty}\int_{\mathbb{S}}f(r\theta)\,\mathrm{d}\Phi(\theta)\,\frac{\mathrm{d}r}{r^{2}}.$
(7)

The combination of the marginal standardization (4) with the change-of-
variable formula in (7) implies the identities

$\forall
j=1,\ldots,d,\qquad\int_{\mathbb{S}}\theta_{j}\,\mathrm{d}\Phi(\theta)=1.$ (8)

In fact, any non-negative Borel measure $\Phi$ on $\mathbb{S}$ satisfying the
moment constraints (8) is the angular measure of some random vector $X$.
Indeed, from such a measure $\Phi$ on $\mathbb{S}$, we can define a measure
$\mu$ on $E$ through (7) and then consider the max-stable distribution with
$\mu$ as exponent measure as in [17].

###  2.3 Data standardization and ranks

The component-wise transformation of $X$ to a vector $V$ with unit-Pareto
margins is formalized by the map
$v:\mathbb{R}^{d}\rightarrow[1,\;\infty]^{d}$, with

$\forall x\in\mathbb{R}^{d},\qquad
v(x)=\left(\frac{1}{1-F_{1}(x_{1})},\ldots,\frac{1}{1-F_{d}(x_{d})}\right),$
(9)

with the convention $1/0=\infty$. In this notation, we have $V=v(X)$.

Let $X_{1},\ldots,X_{n}$ be an independent random sample from the law $P$ of
$X$, with $X_{i}=(X_{i1},\ldots,X_{id})$. Since $P$ is unknown in practice, it
is replaced by its empirical version
$P_{n}(\,\cdot\,)=n^{-1}\sum_{i=1}^{n}\mathbbm{1}\\{X_{i}\in\,\cdot\,\\}$,
where $\mathbbm{1}\\{\mathcal{E}\\}$ denotes the indicator variable of the
event $\mathcal{E}$. In particular, the marginal cumulative distribution
functions $F_{j}$ are substituted with their empirical counterparts

$\widehat{F}_{j}(t)=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{X_{ij}\leqslant
t\\},\text{ for }t\in\mathbb{R}\text{ and }1\leqslant j\leqslant d,$

in order to mimic the aforementioned standardization. The empirically
standardized sample points are

$\widehat{V}_{i}=\hat{v}(X_{i})=\bigl{(}\hat{v}_{1}(X_{i1}),\ldots,\hat{v}_{d}(X_{id})\bigr{)},\qquad
i=1,\ldots,n$ (10)

where $\hat{v}(x)=(\hat{v}_{1}(x_{1}),\ldots,\hat{v}_{d}(x_{d}))$ for all
$x\in\mathbb{R}^{d}$ and

$\hat{v}_{j}(x_{j})=\frac{1}{1-\frac{n}{n+1}\widehat{F}_{j}(x_{j})},$ (11)

for $j=1,\ldots,d$ and $i=1,\ldots,n$. The factor $\frac{n}{n+1}$ in (11)
serves to avoid division by zero in case
$x_{j}\geqslant\max(X_{1j},\ldots,X_{nj})$.

We have $\hat{v}_{j}(X_{ij})=1/(1-R_{ij}/(n+1))$, where
$R_{ij}=n\widehat{F}_{j}(X_{ij})$ is the rank of $X_{ij}$ among
$X_{1j},\ldots,X_{nj}$. Any statistic that is a function
$\widehat{V}_{1},\ldots,\widehat{V}_{n}$ depends on the data
$X_{1},\ldots,X_{n}$ only through the component-wise ranks. This will be the
case for the empirical angular measure.

###  2.4 The (truncated) empirical angular measure

Let $\delta_{x}$ denote a point mass at $x$ and put

$\widehat{P}_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{\widehat{V}_{i}},$ (12)

the empirical distribution of the pseudo-observations
$\widehat{V}_{1},\ldots,\widehat{V}_{n}$ in (10). The random measure
$\widehat{P}_{n}$ can be legitimately considered as an estimator of the
distribution of $V$.

The definition (2) of the exponent measure $\mu$ involves a limit as
$t\to\infty$. Setting $t=n/k$ for $k\in\\{1,\ldots,n\\}$ such that both $k$
and $n/k$ are large yields the empirical exponent measure

$\widehat{\mu}(B)=\tfrac{n}{k}\widehat{P}_{n}(\tfrac{n}{k}B)=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{\widehat{V}_{i}\in(n/k)B\\}$
(13)

for Borel sets $B\subseteq E$. Consider a Borel set $A\subseteq\mathbb{S}$ and
recall the angular measure $\Phi$ and the cone $\mathcal{C}_{A}$ in (6). In
view of (13), _the empirical angular measure_ [23] is defined as

$\widehat{\Phi}(A)=\widehat{\mu}(\mathcal{C}_{A})=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{\widehat{V}_{i}\in(n/k)\mathcal{C}_{A}\\}=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{\lVert{\widehat{V}_{i}}\rVert\geqslant
n/k,\,\theta(\widehat{V}_{i})\in A\\}.$ (14)

It is the empirical version of the pre-asymptotic angular measure

$\Phi_{t}(A)=t\operatorname{\mathbb{P}}[{t^{-1}V\in\mathcal{C}_{A}}]$

at level $t=n/k$. In the bivariate case, the asymptotic distribution of the
empirical angular measure has been investigated in case the sequence $k=k(n)$
satisfies $k\to\infty$ and $k/n\to 0$ as $n\to\infty$. The max-norm was
considered in [23], while the $L_{p}$-norm for $p\in[1,\infty]$ was studied in
[25] together with empirical likelihood methods to exploit the moment
constraints (8).

In Section 3.3, a non-asymptotic study of the accuracy of an alternative
estimator is proposed, referred to as the _truncated empirical angular
measure_ , which is closely related to the exponent measure of doubly
truncated cones. For $M>1$ and any Borel set $A\subseteq\mathbb{S}$, define

$\mathcal{C}_{A}^{M}=\\{x\in E:\ 1\leqslant\lVert{x}\rVert<M,\,\theta(x)\in
A\\}.$

Note that $\mathcal{C}_{A}^{M}=\mathcal{C}_{A}\setminus(M\mathcal{C}_{A})$, so
that, by homogeneity of $\mu$,

$\mu(\mathcal{C}_{A}^{M})=\mu(\mathcal{C}_{A})-\mu(M\mathcal{C}_{A})=(1-\tfrac{1}{M})\mu(\mathcal{C}_{A})=\tfrac{M-1}{M}\Phi(A).$

On the basis of this equation, we define a truncated version of
$\widehat{\Phi}$ by

$\widehat{\Phi}_{M}(A)=\frac{M}{M-1}\widehat{\mu}\left(\mathcal{C}_{A}^{M}\right)=\frac{M}{M-1}\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{\widehat{V}_{i}\in(n/k)\mathcal{C}_{A}^{M}\\},$
(15)

for all $M>1$. In effect, the $k/M$ most extreme observations among the $k$
largest ones are discarded. As we shall see in Section 3, the rationale is
that for those observations, the difference between the empirically
standardized points $\widehat{V}_{i}=\hat{v}(X_{i})$ and their unobservable
counterparts $V_{i}=v(X_{i})$ is difficult to control.

##  3 Concentration inequalities

Recall the (truncated) empirical angular measure $\widehat{\Phi}$ and
$\widehat{\Phi}_{M}$ in (14) and (15), respectively. Our main results provide
concentration inequalities for the uniform deviations

$\sup_{A\in\mathcal{A}}|\widehat{\Phi}(A)-\Phi(A)|\quad\text{ and
}\quad\sup_{A\in\mathcal{A}}|\widehat{\Phi}_{M}(A)-\Phi(A)|.$ (16)

The suprema are taken over classes $\mathcal{A}$ of Borel sets $A$ of
$\mathbb{S}$ in (5) satisfying appropriate assumptions. To bound the two
suprema, both empirical measures are rewritten in terms of random sets which
are subsequently framed in between deterministic sets. We first explain the
idea behind the framing approach (Section 3.1) before stating our main
theorems on concentration bounds for the empirical angular measure and its
truncated variant (Sections 3.2 and 3.3). We conclude in Section 3.4 with
examples of collections $\mathcal{A}$.

###  3.1 Framing random sets

Since the estimators depend on the data only through the ranks, they are
invariant under increasing component-wise transformations. So although the
marginal distributions $F_{1},\ldots,F_{d}$ are unknown, we can and will
nevertheless assume that they are unit-Pareto already. In that case, we have
$v(x)=x$ for $x\in[1,\infty]^{d}$ in (9), so that $V=v(X)=X$ and
$V_{i}=v(X_{i})=X_{i}$ for $i=1,\ldots,n$. In particular, the law of $V=X$ is
$P$.

Recall $\widehat{P}_{n}$ in (12) and let
$P_{n}=n^{-1}\sum_{i=1}^{n}\delta_{V_{i}}$ denote the empirical distribution
of $V_{1},\ldots,V_{n}$. Since
$\widehat{V}_{i}=\hat{v}(X_{i})=\hat{v}(V_{i})$, we have
$\widehat{P}_{n}=P_{n}\circ\hat{v}^{-1}$, that is, $\widehat{P}_{n}$ is the
push-forward measure of $P_{n}$ by $\hat{v}$. Up to a scaling factor, the
value of the empirical angular measure $\widehat{\Phi}$ in a Borel set $A$ of
$\mathbb{S}$ can thus be expressed as $P_{n}$ evaluated in the random set

$\widehat{\Gamma}_{A}=\hat{v}^{-1}(\tfrac{n}{k}\mathcal{C}_{A})=\left\\{x\in
E:\ \lVert{\hat{v}(x)}\rVert\geqslant\tfrac{n}{k},\;\theta(\hat{v}(x))\in
A\right\\},$ (17)

where, as before, $\theta(y)=y/\lVert{y}\rVert$ for $y\in E$. Indeed, we have

$\widehat{\Phi}(A)=\tfrac{n}{k}\widehat{P}_{n}(\tfrac{n}{k}\mathcal{C}_{A})=\tfrac{n}{k}P_{n}(\hat{v}^{-1}(\tfrac{n}{k}\mathcal{C}_{A}))=\tfrac{n}{k}P_{n}(\widehat{\Gamma}_{A}).$

Let $\mathcal{A}$ be a class of Borel sets of $\mathbb{S}$. Following in the
footsteps of [23] and [25], we construct for any $A\in\mathcal{A}$ two nested
deterministic sets $\Gamma^{-}_{A}\subseteq\Gamma^{+}_{A}$ framing the cone
$\mathcal{C}_{A}$, i.e., such that
$\Gamma^{-}_{A}\subseteq\mathcal{C}_{A}\subseteq\Gamma^{+}_{A}$, and such that
on an event that occurs with high probability, we have

$\forall
A\in\mathcal{A},\qquad\tfrac{n}{k}\Gamma^{-}_{A}\subseteq\widehat{\Gamma}_{A}\subseteq\tfrac{n}{k}\Gamma^{+}_{A}.$
(18)

On that event, the signed error can then be bounded from above by

$\displaystyle\widehat{\Phi}(A)-\Phi(A)$
$\displaystyle=\tfrac{n}{k}P_{n}(\widehat{\Gamma}_{A})-\mu(\mathcal{C}_{A})\leqslant\tfrac{n}{k}P_{n}(\tfrac{n}{k}\Gamma_{A}^{+})-\mu(\Gamma_{A}^{-})$
$\displaystyle\leqslant\tfrac{n}{k}\lvert
P_{n}(\tfrac{n}{k}\Gamma_{A}^{+})-P(\tfrac{n}{k}\Gamma_{A}^{+})\rvert+\lvert\tfrac{n}{k}P(\tfrac{n}{k}\Gamma_{A}^{+})-\mu(\Gamma_{A}^{+})\rvert+\mu(\Gamma_{A}^{+}\setminus\Gamma_{A}^{-}).$

A lower bound can be derived in a similar way, yielding, on the same event,

$\displaystyle\lvert\widehat{\Phi}(A)-\Phi(A)\rvert$
$\displaystyle\leqslant\max_{B\in\\{\Gamma_{A}^{+},\Gamma_{A}^{-}\\}}\tfrac{n}{k}\lvert
P(\tfrac{n}{k}B)-\mu(B)\rvert$ (bias term) (19)
$\displaystyle\quad{}+\max_{B\in\\{\Gamma_{A}^{+},\Gamma_{A}^{-}\\}}\tfrac{n}{k}\lvert
P_{n}(\tfrac{n}{k}B)-P(\tfrac{n}{k}B)\rvert$ (stochastic error)
$\displaystyle\quad{}+\mu(\Gamma_{A}^{+}\setminus\Gamma_{A}^{-})$ (framing
gap).

Next we will introduce assumptions to enable the construction of the framing
sets $\Gamma_{A}^{-}$ and $\Gamma_{A}^{+}$ together with a high-probability
event on which (18) holds. The task is then to control the three terms on the
right-hand side of (19) uniformly over $A\in\mathcal{A}$. The bias term will
be left as such; controlling it is an entirely different subject requiring
higher-order multivariate regular variation [1, 28]. Under appropriate
complexity assumptions on the class $\mathcal{A}$ and the collection of
framing sets, the stochastic error term can be uniformly bounded by means of
the concentration inequality for tail empirical processes established in [30]
and recalled in Theorem A.1 in the Supplement. Finally, the framing gap can be
controlled by ensuring that the set $\Gamma_{A}^{+}\setminus\Gamma_{A}^{-}$ is
small.

###  3.2 Concentration bounds for the empirical angular measure

The main result of this paper, Theorem 3.1, is stated in this subsection. Let
$\mathbb{B}=[-1,+1]^{d}$ denote the closed unit ball in $\mathbb{R}^{d}$ with
respect to the sup-norm $\lVert{\,\cdot\,}\rVert$. For sets
$A,B\subseteq\mathbb{R}^{d}$ write $A+B=\\{a+b:a\in A,b\in B\\}$. For
$\varepsilon>0$ and $A\subseteq\mathbb{R}^{d}$, we thus have
$A+\varepsilon\mathbb{B}=\\{x\in\mathbb{R}^{d}:\exists a\in
A,\lVert{x-a}\rVert\leqslant\varepsilon\\}$.

######  Assumption 1 (Subsets of the sphere).

The class $\mathcal{A}$ is a collection of non-empty Borel sets of
$\mathbb{S}$ with the following properties:

  1. (i)

There exists a countable collection $\mathcal{A}_{0}\subseteq\mathcal{A}$ such
that for every $A\in\mathcal{A}$ there is a sequence $A_{n}\in\mathcal{A}_{0}$
such that $\lim_{n\to\infty}\mathbbm{1}\\{x\in A_{n}\\}=\mathbbm{1}\\{x\in
A\\}$ for every $x\in A$.

  2. (ii)

There exists $\tau\in(0,1)$ such that

$\forall A\in\mathcal{A},\qquad A\subseteq\\{x\in\mathbb{S}:\
x_{1}\wedge\cdots\wedge x_{d}>\tau\\}=:\mathbb{S}_{\tau}.$ (20)

  3. (iii)

There is a constant $c>0$ such that for any $A\in\mathcal{A}$ and
$\varepsilon>0$, there exist Borel subsets $A_{+}(\varepsilon)$ and
$A_{-}(\varepsilon)$ of $\mathbb{S}$ satisfying

$\Phi\bigl{(}A_{+}(\varepsilon)\setminus A_{-}(\varepsilon)\bigr{)}\leqslant
c\,\varepsilon\,$ (21)

together with the inclusions

$\bigl{(}A_{-}(\varepsilon)+\varepsilon\mathbb{B}\bigr{)}\cap\mathbb{S}\subseteq
A\qquad\text{and}\qquad(A+\varepsilon\mathbb{B})\cap\mathbb{S}\subseteq
A_{+}(\varepsilon).$ (22)

Condition (i) amounts to the pointwise measurability of the indicators
$\\{\mathbbm{1}\\{\cdot\in A\\}:A\in\mathcal{A}\\}$ [49, Example 2.3.4] and
ensures that for any $A\in\mathcal{A}$ we can find $A_{n}\in\mathcal{A}_{0}$
such that for any finite Borel measure $\nu$ on $\mathbb{S}$ we have
$\nu(A)=\lim_{n\to\infty}\nu(A_{n})$. The suprema over $\mathcal{A}$ in Eq.
(16) are therefore equal to those over $\mathcal{A}_{0}$ and are thus
measurable. Condition (ii) stipulates that the elements of the class
$\mathcal{A}$ are bounded away from the $2^{d}-1$ faces of the sphere. Though
it may be considered as restrictive at first glance, we point out that maximal
deviations of the empirical angular measure over classes of Borel subsets of a
given face of the sphere correspond to maximal deviations of the empirical
angular measure for the corresponding components of $X$. The crucial point in
Condition (iii) is inequality (21), bounding the measure of the difference
between the inner and outer $\varepsilon$-hulls of $A\in\mathcal{A}$. The
inequality is satisfied if it holds with $\Phi$ replaced by the
$(d-1)$-dimensional Lebesgue measure on $\mathbb{S}$ and $\Phi$ has a bounded
density on $\mathbb{S}_{\tau}$ with respect to this measure.

In order to deal with the estimation error stemming from the use of the
marginal empirical distribution functions in (11), we frame the cones
$\mathcal{C}_{A}$ in Eq. (6) between slightly smaller and larger sets built
from the inner and outer hulls. For $A\in\mathcal{A}$, $\sigma\in\\{-,+\\}$
and $r,h>0$, define

$\Gamma_{A}^{\sigma}(r,h)=\left\\{x\in[0,\infty)^{d}:\
\lVert{x}\rVert\geqslant\tfrac{1}{r},\;\theta(x)\in
A_{\sigma}(h\lVert{x}\rVert)\right\\}.$

For all $A\in\mathcal{A}$ and $h>0$, we have
$\Gamma_{A}^{-}(r,h)\subseteq\mathcal{C}_{A}$ for $0<r\leqslant 1$ and
$\mathcal{C}_{A}\subseteq\Gamma_{A}^{+}(r,h)$ for $r\geqslant 1$. The upper
confidence bound at level $1-\delta$ for the maximal deviation (1) stated in
Theorem 3.1 below is derived from the decomposition (19) with framing sets
$\Gamma_{A}^{+}(r_{+},h)$ and $\Gamma_{A}^{-}(r_{-},h)$ for specific choices
of $r_{+}$, $r_{-}$ and $h$.

To control the stochastic error, we need a handle on the complexity of the
collection of framing sets. The Vapnik–Chervonenkis (VC) dimension of a
collection $\mathcal{F}$ of subsets of some set $\mathcal{X}$ is the supremum
(possibly infinite) of the set of positive integers $n$ with the property that
there exists a subset $\\{x_{1},\ldots,x_{n}\\}$ of $\mathcal{X}$ with
cardinality $n$ such that all $2^{n}$ subsets of $\\{x_{1},\ldots,x_{n}\\}$
can be written in the form $\\{x_{1},\ldots,x_{n}\\}\cap F$ for some
$F\in\mathcal{F}$. The VC-dimension is a central quantity in statistical
learning and empirical process theory as it lies at the basis of many
concentration inequalities for empirical distributions, see for instance [49,
5].

######  Assumption 2.

For any $r,h>0$, the collections $\\{\Gamma_{A}^{-}(r,h):A\in\mathcal{A}\\}$
and $\\{\Gamma_{A}^{+}(r,h):A\in\mathcal{A}\\}$ of subsets of $E$ have finite
VC-dimension.

In the framing sets $\Gamma_{A}^{\sigma}(r,h)$, the tolerance $\varepsilon$
for the angle $\theta(x)$ in the inner and outer hulls of a set $A$ depends on
the norm $\lVert{x}\rVert$. Therefore, in Assumption 2 it is not sufficient to
assume that the collection $\mathcal{A}$ or even the collection of inner and
outer hulls has finite VC-dimension. In Section 3.4 we provide a realistic
example of an angular class $\mathcal{A}$—namely a class defined by linear
inequality constraints—where Assumptions 1 and 2 are satisfied.

######  Theorem 3.1.

Let $X_{1},\ldots,X_{n}$ be an independent random sample with common
distribution $P$ on $\mathbb{R}^{d}$ with continuous margins and with angular
measure $\Phi$. Let $\mathcal{A}$ be a collection of Borel sets of
$\mathbb{S}$ such that Assumptions 1 and 2 are fulfilled. Let $n,k,\rho$ be
such that $n>(3\vee 6c)/\tau$, $3\vee 6c<k<\tau n$ and $k/n<\rho<\tau$. Put
$\Delta=C\sqrt{\log((d+1)/\delta)/(\rho k)}+C\log((d+1)/\delta)/k$ where $C$
is a universal constant described below. For $\sigma\in\\{-,+\\}$ and
$A\in\mathcal{A}$, abbreviate
$\Gamma_{A}^{\sigma}=\Gamma_{A}^{\sigma}(r_{\sigma},3\Delta)$ where
$r_{\pm}=1+\frac{1}{n}-\frac{1}{k}\pm\Delta$. Then, for any $\delta\in(0,1)$,
with probability at least $1-\delta$, the empirical angular measure satisfies

$\sup_{A\in\mathcal{A}}\lvert\widehat{\Phi}(A)-\Phi(A)\rvert\leqslant\sup_{A\in\mathcal{A},\;\sigma\in\\{+,-\\}}\left|\tfrac{n}{k}P(\tfrac{n}{k}\Gamma_{A}^{\sigma})-\mu(\Gamma_{A}^{\sigma})\right|\\\
+C\left(\sqrt{\frac{d(1+\Delta)V_{\mathcal{F}}\log((d+1)/\delta)}{k}}+\frac{\log\left((d+1)/\delta\right)}{k}\right)\\\
+\bigl{(}2d+3c\left(\log(d/(3c))-\log(\Delta)+1\right)\bigr{)}\Delta,$ (23)

provided $k$ is sufficiently large so that
$(2/k)\leqslant\Delta<(1-1/k)\wedge(1/(3c))$ and
$\rho/(1-\Delta\rho)\leqslant\tau$ and where $V_{\mathcal{F}}$ is the VC-
dimension of the collection

$\left\\{\Gamma_{A}^{-}:A\in\mathcal{A}\right\\}\cup\left\\{\Gamma_{A}^{+}:A\in\mathcal{A}\right\\}.$
(24)

The proof is given in Appendix B in the Supplement. Note that $r_{-}\leqslant
1\leqslant r_{+}$, so that
$\Gamma_{A}^{-}(r_{-},h)\subseteq\mathcal{C}_{A}\subseteq\Gamma_{A}^{+}(r_{+},h)$
for all $h>0$. In the decomposition (19), the framing gap is bounded by
$\left(2d+3c(\log(d/(3c))-\log(\Delta)+1)\right)\Delta$ while the estimation
error is bounded by

$C\left(\sqrt{\frac{d(1+\Delta)V_{\mathcal{F}}\log((d+1)/\delta)}{k}}+\frac{\log\left((d+1)/\delta\right)}{k}\right),$

with probability larger than $1-\delta$. The constant $C$ is the one appearing
in the concentration inequality for empirical processes over collections of
sets of extreme values proved in [30] (see Theorem A.1 in the Supplement),
applied to the collection
$\\{(n/k)\Gamma_{A}^{\sigma}(r_{\sigma},3\Delta):\;\sigma\in\\{+,-\\},\;A\in\mathcal{A}\\}$.
By Assumption 2, the collection in (24) has a finite VC-dimension: For two
collections $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ of subsets of a set
$\mathcal{X}$ with finite VC-dimensions $d_{1}$ and $d_{2}$, respectively, the
VC dimension of $\mathcal{F}_{1}\cup\mathcal{F}_{2}$ is bounded by
$d_{1}+d_{2}+1$ [40, Exercise 3.24].

For fixed $\rho$ and $\delta$, when ignoring the bias term, the bound on the
right-hand side of (23) is of the order

$3c\Delta\log(1/\Delta)+\operatorname{o}\left(\frac{\log(k)}{\sqrt{k}}\right)=\frac{3}{2}cC\sqrt{\frac{\log((d+1)/\delta)}{\rho}}\frac{\log(k)}{\sqrt{k}}+\operatorname{o}\left(\frac{\log(k)}{\sqrt{k}}\right),$
(25)

as $k\to\infty$. Interestingly, the angular part of the $\operatorname{gap}$
term dominates the $\operatorname{error}$ term.

###  3.3 Concentration bounds for the truncated empirical angular measure

We now extend the concentration result established in the previous subsection
to the truncated version (15) of the empirical angular measure, which discards
the most extreme observations (a fraction of the largest
$\lVert{\widehat{V}_{i}}\rVert$’s) because of the variability they induce.
This time, we build framing sets for the doubly truncated cones
$\mathcal{C}_{A}^{M}$ for $M>1$. For $A\in\mathcal{A}$, $\sigma\in\\{-,+\\}$,
$h>0$ and $0\leqslant s<r$, consider the sets

$\displaystyle\Gamma_{A}^{\sigma}(r,s;h)$
$\displaystyle=\Gamma_{A}^{\sigma}(r,h)\setminus\Gamma_{A}^{\sigma}(s,h)$ (26)
$\displaystyle=\left\\{x\in[0,\infty)^{d}:\
\tfrac{1}{r}\leqslant\lVert{x}\rVert<\tfrac{1}{s},\;\theta(x)\in
A_{\sigma}(h\lVert{x}\rVert)\right\\},$

where $1/s$ is to be read as $\infty$ if $s=0$. In order to derive an upper
confidence bound for the maximal deviations of the estimator (15) at level
$1-\delta$ from a bias/variance/gap decomposition similar to (19), we use the
inclusions
$\Gamma_{A}^{M,-}\subseteq\mathcal{C}_{A}^{M}\subseteq\Gamma_{A}^{M,+}$ with
framing sets

$\displaystyle\Gamma_{A}^{M,-}$
$\displaystyle=\Gamma_{A}^{-}\bigl{(}1+\tfrac{1}{n}-\tfrac{1}{k}-\Delta,(1+\tfrac{1}{n})\tfrac{1}{M}-\tfrac{1}{k}+\Delta;3\Delta\bigr{)},$
(27) $\displaystyle\Gamma_{A}^{M,+}$
$\displaystyle=\Gamma_{A}^{+}\bigl{(}1+\tfrac{1}{n}-\tfrac{1}{k}+\Delta,((1+\tfrac{1}{n})\tfrac{1}{M}-\tfrac{1}{k}-\Delta)_{+};3\Delta\bigr{)},$

choosing $k$ and $\Delta$ as in the previous subsection. A variation of the
proof of Theorem 3.1 then permits to establish the following result.

######  Theorem 3.2.

Let $M>1$ and suppose that Assumptions 1 and 2 are fulfilled. Then, for all
$\delta\in(0,1)$, we have with probability larger than $1-\delta$:

$\sup_{A\in\mathcal{A}}\lvert\widehat{\Phi}_{M}(A)-\Phi(A)\rvert\leqslant\tfrac{M}{M-1}\sup_{A\in\mathcal{A},\;\sigma\in\\{-,+\\}}\lvert\tfrac{n}{k}P(\tfrac{n}{k}\Gamma_{A}^{M,\sigma})-\mu(\Gamma_{A}^{M,\sigma})\rvert\\\
+\tfrac{M}{M-1}C\left(\sqrt{\frac{d(1+\Delta)V_{M}\log((d+1)/\delta)}{k}}+\frac{\log((d+1)/\delta)}{k}\right)\\\
+\tfrac{M}{M-1}\left(4d\Delta+3c\Delta\log\bigl{(}M\wedge
d/(3c\Delta)\bigr{)}+\bigl{(}3c\Delta-d/M\bigr{)}_{+}\right),$ (28)

where $\Delta$, $k$, $n$ and $\rho$ are chosen as in Theorem 3.1 and with
$V_{M}$ the VC-dimension of the collection

$\bigl{\\{}\Gamma_{A}^{M,-}:A\in\mathcal{A}\bigr{\\}}\cup\bigl{\\{}\Gamma_{A}^{M,+}:A\in\mathcal{A}\bigr{\\}}.$
(29)

See Appendix B in the Supplement for the proof. The collection (29) has finite
VC-dimension because of the representation (26) in terms of set differences in
combination with the stability of the VC property under a finite number of set
operations; see for instance [48] and the references therein. For fixed $M>1$,
$\rho$ and $\delta$, ignoring the bias, the bound on the right-hand side of
(28) is of the order

$\frac{M}{M-1}\left(C\sqrt{\frac{dV_{M}\log((d+1)/\delta)}{k}}+(4d+3c\log(M))\Delta\right)+\operatorname{o}\left(\frac{1}{\sqrt{k}}\right)\\\
=\frac{M}{M-1}C\sqrt{\frac{\log((d+1)/\delta)}{k}}\left(\sqrt{dV_{M}}+(4d+3c\log(M))\sqrt{\rho^{-1}}\right)+\operatorname{o}\left(\frac{1}{\sqrt{k}}\right),$

as $k\to\infty$. This bound is to be compared with (25): the factor $\log(k)$
has disappeared, in return for a factor $\frac{M}{M-1}\log(M)$. Setting
$M=\sqrt{k}$ yields (25) again.

###  3.4 Examples of collections of subsets of the sphere

This section aims at verifying that our Assumptions 1 and 2 are met when
working with a class of sets which is defined by a finite number of linear
inequality contraints. This setting relates to a wide range of statistical
machine learning algorithms such as logistic regression, classification and
regression trees or linear discriminant analysis. Recall $\mathbb{S}_{\tau}$
in (20). The scalar product and the Euclidean norm on $\mathbb{R}^{d}$ are
denoted by $\langle{x,y}\rangle$ and
$\lVert{x}\rVert_{2}=\sqrt{\langle{x,x}\rangle}$, respectively.

######  Example 3.1 (Linear restrictions).

Fix $\tau\in(0,1)$ and consider the collection

$\mathcal{A}=\left\\{A_{a,\beta,\tau}:\
(a,\beta)\in\mathbb{R}^{d}\times\mathbb{R},\;\lVert{a}\rVert_{2}=1\right\\}$

of Borel subsets of $\mathbb{S}_{\tau}$ defined via

$\displaystyle A_{a,\beta}$ $\displaystyle=\\{x\in\mathbb{S}:\
\langle{a,x}\rangle\leqslant\beta\\},$ $\displaystyle A_{a,\beta,\tau}$
$\displaystyle=A_{a,\beta}\cap\mathbb{S}_{\tau}.$

We first consider Assumption 1. Restricting $a$ and $\beta$ to have rational
coordinates yields a countable collection $\mathcal{A}_{0}\subset\mathcal{A}$
satisfying item (i) in Assumption 1. Item (ii) is satisfied by definition. For
$A_{a,\beta,\tau}\in\mathcal{A}$ and $\varepsilon>0$, define the inner and
outer hulls

$\displaystyle A_{a,\beta,\tau;-}(\varepsilon)$
$\displaystyle=A_{a,\beta-\sqrt{d}\varepsilon,\tau+\varepsilon},$
$\displaystyle A_{a,\beta,\tau;+}(\varepsilon)$
$\displaystyle=A_{a,\beta+\sqrt{d}\varepsilon,\tau-\varepsilon},$

with the convention that $\mathbb{S}_{\upsilon}=\mathbb{S}$ if $\upsilon<0$ (a
case which arises if $\varepsilon>\tau$). We show that item (iii) in
Assumption 1 is satisfied, provided the angular measure $\Phi$ has a bounded
density on $\mathbb{S}_{\tau}$ with respect to $(d-1)$-dimensional Lebesgue
measure. First, we show the inclusions (22).

  * •

For $x\in A_{a,\beta,\tau;-}(\varepsilon)$ and for $y\in\mathbb{S}$ such that
$\lVert{y-x}\rVert\leqslant\varepsilon$, we have $y\in A_{a,\beta,\tau}$:
indeed,

$y_{1}\wedge\cdots\wedge y_{d}\geqslant x_{1}\wedge\cdots\wedge
x_{d}-\varepsilon>\tau+\varepsilon-\varepsilon=\tau$

as well as

$\langle{a,y}\rangle=\langle{a,x}\rangle+\langle{a,y-x}\rangle\leqslant\beta-\sqrt{d}\varepsilon+\lVert{a}\rVert_{2}\lVert{y-x}\rVert_{2}\leqslant\beta-\sqrt{d}\varepsilon+\sqrt{d}\lVert{y-x}\rVert\leqslant\beta.$

This is the first inclusion in (22).

  * •

For $x\in A_{a,\beta,\tau}$ and for $y\in\mathbb{S}$ such that
$\lVert{y-x}\rVert\leqslant\varepsilon$, we have

$y_{1}\wedge\cdots\wedge y_{d}\geqslant x_{1}\wedge\cdots\wedge
x_{d}-\varepsilon>\tau-\varepsilon$

so that $y\in\mathbb{S}_{\tau-\varepsilon}$ (if $\varepsilon>\tau$ this
trivial since $\mathbb{S}_{\upsilon}=\mathbb{S}$ for $\upsilon<0$) together
with

$\langle{a,y}\rangle=\langle{a,x}\rangle+\langle{a,y-x}\rangle\leqslant\beta+\lVert{a}\rVert_{2}\lVert{y-x}\rVert_{2}\leqslant\beta+\sqrt{d}\lVert{y-x}\rVert\leqslant\beta+\sqrt{d}\varepsilon.$

This implies the second inclusion in (22).

The difference between the inner and outer hulls is

$A_{a,\beta,\tau;+}(\varepsilon)\setminus
A_{a,\beta,\tau;-}(\varepsilon)\subseteq\left\\{x\in\mathbb{S}:\
\beta-\sqrt{d}\varepsilon<\langle{a,x}\rangle\leqslant\beta+\sqrt{d}\varepsilon\right\\}\cup(\mathbb{S}_{\tau-\varepsilon}\setminus\mathbb{S}_{\tau+\varepsilon}).$

Since $\lVert{a}\rVert_{2}=1$, the $(d-1)$-dimensional Lebesgue measure of the
set on the right-hand side is bounded by a constant multiple (depending only
on $d$) of $\varepsilon$.

Next we show that Assumption 2 is satisfied. The VC-dimension is preserved
under bijections. We identify $E=[0,\infty)^{d}\setminus\\{(0,\ldots,0)\\}$
with the product set $(0,\infty)\times\mathbb{S}$ via
$x\mapsto(\lVert{x}\rVert,x/\lVert{x}\rVert)$. In the latter space, we need to
establish the finiteness of the VC-dimensions of the collections
$\\{\Upsilon_{A}^{-}(r,h):A\in\mathcal{A}\\}$ and
$\\{\Upsilon_{A}^{+}(r,h):A\in\mathcal{A}\\}$ for fixed $r,h>0$, where

$\Upsilon_{A}^{\sigma}(r,h)=\left\\{(u,\theta)\in(\tfrac{1}{r},\infty)\times\mathbb{S}:\
\theta\in A_{\sigma}(hu)\right\\}$

for $\sigma\in\\{-,+\\}$ and $A\in\mathcal{A}$. For $A=A_{a,\beta,\tau}$ we
have

$\theta\in
A_{-}(hu)\iff\left[\theta_{1}\wedge\cdots\wedge\theta_{d}\geqslant\tau+hu\text{
and }\langle{a,\theta}\rangle\leqslant\beta-\sqrt{d}hu\right].$

This corresponds to $d+1$ linear inequality constraints on $(u,\theta)$ as
$(a,\beta)$ ranges over $\mathbb{R}^{d}\times\mathbb{R}$. The VC dimension of
$\\{\Upsilon_{A}^{-}(r,h):A\in\mathcal{A}\\}$ as a collection of subsets of
$(0,\infty)\times\mathbb{S}$ is therefore finite [49, Lemma 2.6.17 and
Exercise 14 on page 152], and the same is then true for
$\\{\Gamma_{A}^{-}(r,h):A\in\mathcal{A}\\}$ as a collection of subsets of $E$.
The argument for the outer hulls is similar.

######  Example 3.2 (Stability under intersections).

Let $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ be two collections of Borel
subsets of $\mathbb{S}$ satisfying Assumptions 1 and 2. We show that the same
is true for the collection of intersections

$\mathcal{A}_{1}\sqcap\mathcal{A}_{2}=\left\\{A_{1}\cap A_{2}:\
A_{1}\in\mathcal{A}_{1},\,A_{2}\in\mathcal{A}_{2}\right\\}.$

In Assumption 1, item (i) follows by considering the countable collection of
intersections $\mathcal{A}_{1,0}\sqcap\mathcal{A}_{2,0}$, where
$\mathcal{A}_{j,0}$ is the countable subset of $\mathcal{A}_{j}$ for
$j\in\\{1,2\\}$. Item (ii) is trivially satisfied. Regarding (iii): given
$A_{j}\in\mathcal{A}_{j}$ with inner and outer hulls
$A_{j,\sigma}(\varepsilon)$, the inner and outer hulls of $A_{1}\cap A_{2}$
can chosen to be $A_{1,-}(\varepsilon)\cap A_{2,-}(\varepsilon)$ and
$A_{1,+}(\varepsilon)\cap A_{2,+}(\varepsilon)$. The two inclusions (22) are
straightforward to verify. The measure of the set difference between the inner
and outer hulls can be controlled via

$\bigl{(}A_{1,+}(\varepsilon)\cap
A_{2,+}(\varepsilon)\bigr{)}\setminus\bigl{(}A_{1,-}(\varepsilon)\cap
A_{2,-}(\varepsilon)\bigr{)}\subseteq\bigl{(}A_{1,+}(\varepsilon)\setminus
A_{1,-}(\varepsilon)\bigr{)}\cup\bigl{(}A_{2,+}(\varepsilon)\setminus
A_{2,-}(\varepsilon)\bigr{)}.$

If $c_{1}$ and $c_{2}$ denote the constants on the right-hand of (21) for
$\mathcal{A}_{1}$ and $\mathcal{A}_{2}$, respectively, then $c_{1}+c_{2}$ is a
valid constant for $\mathcal{A}_{1}\sqcap\mathcal{A}_{2}$.

To show that the collections of framing sets derived from the inner and outer
hulls thus constructed have a finite VC-dimension (Assumption 2), it suffices
to observe that, by definition,

$\Gamma_{A_{1}\cap
A_{2}}^{\sigma}(r,h)=\Gamma_{A_{1}}^{\sigma}(r,h)\cap\Gamma_{A_{2}}^{\sigma}(r,h)$

and thus

$\\{\Gamma_{A}^{\sigma}(r,h):A\in\mathcal{A}_{1}\sqcap\mathcal{A}_{2}\\}=\\{\Gamma_{A_{1}}^{\sigma}(r,h):A_{1}\in\mathcal{A}_{1}\\}\sqcap\\{\Gamma_{A_{2}}^{\sigma}(r,h):A_{2}\in\mathcal{A}_{2}\\}.$

The collection on the left-hand side has a finite VC-dimension since, by
assumption, each of the two collections on the right-hand side has a finite
VC-dimension; see for instance [49, Lemma 2.6.17].

######  Example 3.3 (Stability under unions).

The stability property in Example 3.2 continues to hold for the collection of
unions

$\mathcal{A}_{1}\sqcup\mathcal{A}_{2}=\left\\{A_{1}\cup A_{2}:\
A_{1}\in\mathcal{A}_{1},\,A_{2}\in\mathcal{A}_{2}\right\\}.$

The inner and outer hulls of a union $A_{1}\cup A_{2}$ are now defined as the
unions of the inner and outer hulls of $A_{1}$ and $A_{2}$. The verification
of Assumptions 1 and 2 is completely similar. In combination with Example 3.1,
this property covers classifiers built from decision trees with a given depth.
The leaves of such a tree correspond to unions of rectangles, the maximum
number of rectangles in the union being determined by the tree depth. Decision
trees appear in our numerical experiments in Section 5.2.

##  4 Applications to statistical learning

We illustrate how concentration results such as those in Theorems 3.1 and 3.2
are useful to establish sound non-asymptotic guarantees for the validity of
certain statistical learning procedures relying on the empirical angular
measure and recently introduced in the literature. Two algorithmic approaches
are analyzed in Sections 4.1 and 4.2. The first one covers the minimum-volume
set estimation methodology of [47] in order to perform (unsupervised) anomaly
detection among extreme observations while the second one consists of a
learning procedure proposed in [34] to perform (supervised) binary
classification in extreme regions.

###  4.1 Minimum-volume set estimation

To illustrate the usefulness of bounds on the supremum in (1), consider the
problem of estimating a _minimum-volume set_ [20, 41], such sets extending the
notion of univariate quantiles. In the context of the angular measure for
multivariate upper extremes, the question is to find a Borel set $\Omega$ of
the unit sphere $\mathbb{S}$ in $[0,\infty)^{d}$ with minimal volume
$\lambda(\Omega)$—with $\lambda$ some reference measure such as the
$(d-1)$-dimensional Hausdorff measure—but still having content $\Phi(\Omega)$
not smaller than some pre-specified lower limit
$\alpha\in(0,\Phi(\mathbb{S}))$. In [47], such a set $\hat{\Phi}$ is used for
the purpose of (unsupervised) anomaly detection in extreme regions. As
$\Omega$ is supposed to contain a large fraction
$\Phi(\Omega)/\Phi(\mathbb{S})$ of the possible directions of extreme points,
a new such point is deemed to be a potential anomaly if it lies in a direction
outside $\Omega$. The fact that $\Omega$ has minimal volume $\lambda(\Omega)$
means that the critical region $\mathbb{S}\setminus\Omega$ to detect
suspicious points is as large as possible.

As $\Phi$ is unknown, $\Omega$ needs to be learned from a training sample.
Although $\Omega$ may be characterized as a certain super-level set of the
density of $\Phi$ with respect to the reference measure $\lambda$, a more
practical approach than estimating this density, especially in high
dimensions, is to limit the search to an algorithmically manageable collection
$\mathcal{A}$ of Borel subsets of $\mathbb{S}$. Let $\hat{\Phi}$ be any
estimator of $\Phi$, not necessarily the empirical angular measure. Following
the logic in [46], let $\hat{A}$ solve the empirical angular minimum-volume
set problem

$\min\bigl{\\{}\lambda(A):\
A\in\mathcal{A},\hat{\Phi}(A)\geqslant\alpha-\psi\bigr{\\}}$

where $\psi\in(0,\alpha)$ is a tolerance parameter. The price to pay for
having to estimate the angular measure is that the minimal required content
$\alpha$ has been relaxed to $\alpha-\psi$.

Bounds on the largest estimation error of $\hat{\Phi}$ over $\mathcal{A}$ are
helpful to provide probabilistic guarantees for $\hat{A}$. Suppose that, on
some event $\mathcal{E}$, we have

$\sup_{A\in\mathcal{A}}|\hat{\Phi}(A)-\Phi(A)|\leqslant\psi.$ (30)

Then, on the same event $\mathcal{E}$, we obviously have

$\Phi(\hat{A})\geqslant\hat{\Phi}(\hat{A})-\psi\geqslant\alpha-2\psi$ (31)

as well as

$\lambda(\hat{A})\leqslant\inf\\{\lambda(A):\
A\in\mathcal{A},\Phi(A)\geqslant\alpha\\}.$ (32)

Indeed, on $\mathcal{E}$, the collection
$\\{A\in\mathcal{A}:\Phi(A)\geqslant\alpha\\}$ is contained in
$\\{A\in\mathcal{A}:\hat{\Phi}(A)\geqslant\alpha-\psi\\}$ so that the infimum
of $\lambda(A)$ for $A$ in the latter collection must be the smaller one. By
(31), the empirical solution $\hat{A}$ is guaranteed to have at least content
$\alpha-2\psi$ under $\Phi$, while according to (32), the volume of $\hat{A}$
is smaller than the one of the actual minimum-volume set under $\Phi$.

Concentration inequalities for the supremum of $|\hat{\Phi}(A)-\Phi(A)|$ over
$A\in\mathcal{A}$ provide the existence, for a given $\delta>0$, of a scalar
$\psi\equiv\psi(\delta)$ such that (30) holds on an event with probability at
least $1-\delta$. It follows that, with high probability, the empirical
minimum-volume set $\hat{A}$ satisfies (31) and (32). Provided $\psi$ and
$\delta$ are both small, the combination of both properties justifies the use
of $\hat{A}$ as an approximation to the true but unknown minimum-volume set
under $\Phi$. For the empirical angular measure and its truncated version,
valid choices for the tolerance parameter $\psi(\delta)$ are given by the
upper bounds in Theorems 3.1 and 3.2 respectively.

###  4.2 Classification in extreme regions

We apply our Theorems 3.1 and 3.2 to binary classification in extreme regions.
In [34] this problem was investigated in case the marginal distributions of
the predictor variables are known so that a standardized vector with exact
unit-Pareto margins is observable. Here we assume the margins are unknown and
employ a rank-based standardization instead.

First we recall the set-up of [34]. Consider a random pair $(V,Y)$ where $Y$
in $\\{-1,1\\}$ is the label to be predicted and $V$ in $[0,\infty)^{d}$ is
the vector of predictors (features). The goal is to learn a classifier
$g:[0,\infty)^{d}\to\\{-1,1\\}$ such that the classification risk for feature
vectors $V$ far away from the origin be small. Let
$p=\operatorname{\mathbb{P}}[{Y=1}]$ and assume $0<p<1$.

The starting point in [34] is to assume a conditional version of the regular
variation condition (2): there exist non-zero Borel measures $\mu_{+}$ and
$\mu_{-}$ on $E=[0,\infty)^{d}\setminus\\{0\\}$ that are finite on Borel sets
bounded away from the origin and such that

$\lim_{t\to\infty}t\operatorname{\mathbb{P}}[{t^{-1}V\in B\mid
Y=\sigma\,1}]=\mu_{\sigma}(B)$ (33)

for $\sigma\in\\{-,+\\}$ and Borel sets $B\subseteq E$ bounded away from the
origin satisfying $\mu_{\sigma}(\partial B)=0$. The angular measure of
$\mu_{\sigma}$ is

$\Phi_{\sigma}(A)=\mu_{\sigma}(\mathcal{C}_{A}),\qquad\text{for
$\sigma\in\\{-,+\\}$ and Borel sets $A\subseteq\mathbb{S}$},$

with $\mathcal{C}_{A}$ as in (6). By (33), the unconditional distribution of
$V$ is regularly varying as in (2) with limit measure
$\mu=p\mu_{+}+(1-p)\mu_{-}$ and angular measure
$\Phi=p\Phi_{+}+(1-p)\Phi_{-}$.

In [34] it was assumed that an independent random sample
$\\{(V_{i},Y_{i})\\}_{i=1}^{n}$ from the law of $(V,Y)$ is given. Here,
instead, the set-up is that we observe an independent random sample
$\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ from the distribution of $(X,Y)$ and that (33)
holds with $V=v(X)$, where $v$ is defined via the probability integral
transform in (9). This means that the classifier will have to be learned from
the pairs $(\widehat{V}_{i},Y_{i})$ where $\widehat{V}_{i}=\hat{v}(X_{i})$ in
(10) is based on the rank transform.

We emphasize that the marginal distribution functions $F_{j}$ in the
definition of $v$ are not conditioned upon $Y$. Indeed, for a new observation,
marginal standardization will have to be carried out without the knowledge of
the label to be predicted.

In [34] the focus is on the conditional classification risk above level $t>0$
of a classifier $g:[0,\infty)^{d}\setminus\\{0\\}\to\\{-1,1\\}$ defined on the
standardized input $V$:

$L_{t}^{\text{cond}}(g)=\operatorname{\mathbb{P}}[{Y\neq
g(V)\mid\lVert{V}\rVert>t}],$

Let $\mathcal{G}$ be a pre-defined family of classifiers $g$ and let
$L_{t}^{\text{cond}^{*}}=\inf_{g\in\mathcal{G}}L_{t}^{\text{cond}}(g)$ be the
smallest conditional classification risk for classifiers in $\mathcal{G}$. The
purpose is to learn from the training sample a classifier
$\hat{g}\in\mathcal{G}$ such that for large $t$ the excess risk
$L_{t}^{\text{cond}}(\hat{g})-L_{t}^{\text{cond}*}$ be small.

In [34], it is argued that, asymptotically, attention can be restricted to
_angular classifiers_ $g$, that is, for which $g(x)=g(\theta(x))$ with
$\theta(x)=x/\lVert{x}\rVert$ for $x\in E$. Their analysis involves a random
pair $(V_{\infty},Y_{\infty})$ whose distribution is the weak limit as
$t\to\infty$ of $(t^{-1}V,Y)$ conditionally on $\lVert{V}\rVert>t$, a limit
which exists thanks to (33). Let $\eta(x)=\operatorname{\mathbb{P}}[{Y=1\mid
V=x}]$ denote the regression function of $(V,Y)$ and let
$\eta_{\infty}(x)=\operatorname{\mathbb{P}}[{Y_{\infty}=1\mid V_{\infty}=x}]$
be the one of $(V_{\infty},Y_{\infty})$. The respective Bayes classifiers are

$\displaystyle g^{*}(x)$ $\displaystyle=\mathbbm{1}\\{\eta(x)\geqslant
1/2\\},$ (34) $\displaystyle g_{\infty}^{*}(x)$
$\displaystyle=\mathbbm{1}\\{\eta_{\infty}(x)\geqslant 1/2\\}.$

Note that $g^{*}$ minimizes the conditional risk $L_{t}^{\text{cond}}$ for any
$t>0$. Assume that when $\lVert{x}\rVert$ is large, $\eta(x)$ and
$\eta_{\infty}(x)$ are uniformly close:

$\sup_{x\in[0,\infty)^{d}:\lVert{x}\rVert\geqslant
t}\left|\eta(x)-\eta_{\infty}(x)\right|\to 0\quad\text{ as }t\to\infty.$ (35)

Then by Theorem 1 in [34], (i) the asymptotic Bayes classifier
$g_{\infty}^{*}$ is angular, and (ii) the latter’s excess conditional risk
over the actual Bayes classifier $g^{*}$ vanishes in the limit, that is,
$L_{t}^{\text{cond}}(g_{\infty}^{*})-L_{t}^{\text{cond}}(g^{*})\to 0$ as
$t\to\infty$.

These properties motivate restricting the search to a class $\mathcal{G}$ of
candidate classifiers $g$ depending on the angle only. Theorem 2 in [34]
provides a concentration inequality for the excess risk of the empirical risk
minimizer $\hat{g}_{k}\in\mathcal{G}$ learned from a sample
$\\{(V_{i},Y_{i})\\}_{i=1}^{n}$, using only those points for which
$\lVert{V_{i}}\rVert$ belongs to a top fraction among those observed. Here, we
intend to do the same but for the rank-based transformed feature vectors
$\widehat{V}_{i}=\hat{v}(X_{i})$ in (10).

#### Classification risk and angular measure

For $g$ in a class of angular classifiers $\mathcal{G}$, define

$L_{t}(g)=t\operatorname{\mathbb{P}}[{\lVert{V}\rVert\geqslant
t}]\,L_{t}^{\text{cond}}(g)=t\operatorname{\mathbb{P}}[{g(V)\neq
Y,\,\lVert{V}\rVert\geqslant t}].$ (36)

The multiplicative factor
$t\operatorname{\mathbb{P}}[{\lVert{V}\rVert\geqslant t}]$ converges to
$\Phi(\mathbb{S})$ and does not change the minimizer in the class
$\mathcal{G}$. Working with the unconditional version $L_{t}(g)$ rather than
with $L_{t}^{\text{cond}}(g)$ simplifies the analysis that follows.

In view of Assumption 1 required in Section 3, we exclude from our empirical
risk minimization (ERM) strategy those feature vectors whose angle (after
standardization) is too close to the boundary of the unit sphere. Let
$\tau\in(0,1)$ and recall $\mathbb{S}_{\tau}$ in (20). We have

$L_{t}(g)=L_{t}^{>\tau}(g)+L_{t}^{\leqslant\tau}(g)$ (37)

with

$\displaystyle L_{t}^{>\tau}(g)$
$\displaystyle=t\operatorname{\mathbb{P}}[{g(V)\neq
Y,\,\theta(V)\in\mathbb{S}_{\tau},\,\lVert{V}\rVert\geqslant t}],$
$\displaystyle L_{t}^{\leqslant\tau}(g)$
$\displaystyle=t\operatorname{\mathbb{P}}[{g(V)\neq
Y,\,\theta(V)\notin\mathbb{S}_{\tau},\,\lVert{V}\rVert\geqslant t}].$

The regions of the sphere $\mathbb{S}$ labeled $+1$ and $-1$ by
$g\in\mathcal{G}$ are denoted by

$\mathbb{S}_{g}^{\sigma}=\\{x\in\mathbb{S}:g(x)=\sigma 1\\},\qquad\text{for
$\sigma\in\\{-,+\\}$.}$

We work hereafter under the following smoothness assumption.

######  Assumption 3 (Smoothness).

The scalar $\tau\in(0,1)$ is such that $\Phi(\partial\mathbb{S}_{\tau})=0$ and
the class $\mathcal{G}$ is such that
$\Phi(\partial\mathbb{S}_{g}^{+})=\Phi(\partial\mathbb{S}_{g}^{-})=0$ for all
$g\in\mathcal{G}$.

######  Lemma 4.1.

If the conditional regular variation property (33) and Assumption 3 hold, then
for any angular classifier $g\in\mathcal{G}$,

$\displaystyle\lim_{t\to\infty}L_{t}^{>\tau}(g)$
$\displaystyle=L_{\infty}^{>\tau}(g):=p\Phi^{+}(\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau})+(1-p)\Phi^{-}(\mathbb{S}_{g}^{+}\cap\mathbb{S}_{\tau}),$
$\displaystyle\lim_{t\to\infty}L_{t}^{\leqslant\tau}(g)$
$\displaystyle=L_{\infty}^{\leqslant\tau}(g):=p\Phi^{+}(\mathbb{S}_{g}^{-}\setminus\mathbb{S}_{\tau})+(1-p)\Phi^{-}(\mathbb{S}_{g}^{+}\setminus\mathbb{S}_{\tau}),$

and thus

$\lim_{t\to\infty}L_{t}(g)=L_{\infty}(g):=p\Phi^{+}(\mathbb{S}_{g})+(1-p)\Phi^{-}(\mathbb{S}_{g}^{+}).$

The proof is deferred to Appendix C. The idea of the decomposition (37) is to
discard points with angle outside $\mathbb{S}_{\tau}$. If $\Phi$ is
concentrated on the interior of $\mathbb{S}$, the corresponding loss term
$L_{t}^{\leqslant\tau}(g)$ can be expected to be small for $\tau$ close zero,
since

$\sup_{g\in\mathcal{G}}L_{t}^{\leqslant\tau}(g)\leqslant
t\operatorname{\mathbb{P}}[{\theta(V)\not\in\mathbb{S}_{\tau},\,\lVert{V}\rVert>t}]\to\Phi(\mathbb{S}\setminus\mathbb{S}_{\tau}),\qquad\text{as
$t\to\infty$}.$

#### ERM classifier and decomposition of the excess risk

Given $0<\tau<1$ and integers $1<k\leqslant n$, define the empirical risk of a
classifier $g\in\mathcal{G}$ by

$\widehat{L}^{\tau}(g)=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{g(\widehat{V}_{i})\neq
Y_{i},\,\theta(\widehat{V}_{i})\in\mathbb{S}_{\tau},\,\lVert{\widehat{V}_{i}}\rVert\geqslant
n/k\\}.$ (38)

Assuming a minimizer exists, the ERM classifier is defined as

$\hat{g}_{k}^{\tau}\in\mathop{\rm
arg\,min}_{g\in\mathcal{G}}\widehat{L}^{\tau}(g).$

Otherwise, introduce a tolerance parameter and consider an approximate
minimizer instead.

Recall $L_{\infty}$ in Lemma 4.1. A consequence of Theorem 1 in [34] is that
if (35) holds, the Bayes classifier $g_{\infty}^{*}$ in (34) minimizes
$L_{\infty}$ over all measurable classifiers. One way to measure the
performance of the ERM classifier $\hat{g}_{k}^{\tau}$ is via the asymptotic
excess risk

$L_{\infty}(\hat{g}_{k}^{\tau})-\inf_{g\in\mathcal{G}}L_{\infty}(g).$

The latter can be bounded in terms of the supremum deviation of the empirical
and asymptotic risks over $\mathcal{G}$: since
$\widehat{L}(\hat{g}_{k}^{\tau})$ is equal to the infimum of $\widehat{L}(g)$
over $g\in\mathcal{G}$, we have

$L_{\infty}(\hat{g}_{k}^{\tau})-\inf_{g\in\mathcal{G}}L_{\infty}(g)\leqslant
2\sup_{g\in\mathcal{G}}|\widehat{L}^{\tau}(g)-L_{\infty}(g)|.$ (39)

Our main purpose is therefore to obtain a concentration inequality for the
supremum on the right-hand side of these inequalities. In our context, the
supremum deviation itself decomposes further, since for all $g\in\mathcal{G}$,
we have
$L_{\infty}^{\leqslant\tau}(g)\leqslant\Phi(\mathbb{S}\setminus\mathbb{S}_{\tau})$
and thus

$\sup_{g\in\mathcal{G}}|\widehat{L}^{\tau}(g)-L_{\infty}(g)|\leqslant\sup_{g\in\mathcal{G}}|\widehat{L}^{\tau}(g)-L_{\infty}^{>\tau}(g)|+\Phi(\mathbb{S}\setminus\mathbb{S}_{\tau}).$
(40)

The term $\Phi(\mathbb{S}\setminus\mathbb{S}_{\tau})$ may be viewed as an
additional bias term which vanishes as $\tau\to 0$ provided $\Phi$ is
concentrated on the interior of $\mathbb{S}$. On the other hand, the upper
bounds in Theorem 3.1 and Theorem 4.2 grow roughly as $1/\sqrt{\tau}$ as
$\tau\to 0$. The choice of $\tau$ thus constitutes an additional bias-variance
compromise.

Lemma C.1 in Appendix C parallels Lemma 4.1 by relating the empirical risk
$\widehat{L}^{\tau}(g)$ to the empirical angular measures of the positive and
negative instances,

$\widehat{\Phi}_{\sigma}(A)=\frac{1}{k_{\sigma}}\sum_{i=1}^{n}\mathbbm{1}\\{Y_{i}=\sigma
1\\}\mathbbm{1}\\{\theta(\widehat{V}_{i})\in
A,\;\lVert{\widehat{V}_{i}}\rVert\geqslant n/k\\}\,,\qquad
A\subseteq\mathbb{S}\,,\quad\sigma\in\\{-,+\\},$ (41)

where $k_{\sigma}=kn_{\sigma}/n$ and
$n_{\sigma}=\sum_{i=1}^{n}\mathbbm{1}\\{Y_{i}=\sigma 1\\}$ is the number of
points such that $Y_{i}=\sigma 1$. In view of the error decomposition
(39)–(40), we state our main result in terms of the maximum deviations
$\sup_{g\in\mathcal{G}}|\widehat{L}^{\tau}(g)-L_{\infty}^{>\tau}(g)|$,
following the techniques from Section 3.

######  Theorem 4.2 (Deviations of the empirical tail risk).

Let $\mathcal{G}$ be a class of angular classifiers. Consider the collection
$\mathcal{A}=\\{\mathbb{S}_{g}^{+}\cap\mathbb{S}_{\tau}:g\in\mathcal{G}\\}\cup\\{\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau}:g\in\mathcal{G}\\}$.
If Assumptions 1 and 2 relative to the class $\mathcal{A}$ and the
unconditional angular measure $\Phi$ are satisfied and if the conditional
regular variation assumption (33) and Assumption 3 hold, then, with
probability at least $1-\delta(d+2)/(d+1)$,

$\sup_{g\in\mathcal{G}}|\widehat{L}^{\tau}(g)-L_{\infty}^{>\tau}(g)|\leqslant
2(\operatorname{error}+\operatorname{bias\,II}+\operatorname{gap})$

where $\operatorname{error}$ and $\operatorname{gap}$ are the same as in
Theorem 3.1, that is,

$\displaystyle\operatorname{error}$
$\displaystyle=C\left(\sqrt{d(1+\Delta)V_{\mathcal{F}}k^{-1}\log((d+1)/\delta)}+k^{-1}\log((d+1)/\delta)\right),$
$\displaystyle\operatorname{gap}$
$\displaystyle=\bigl{(}2d+3c\left(\log(d/(3c))-\log(\Delta)+1\right)\bigr{)}\Delta,$

with $C$ the constant appearing in Theorem A.1, $\Delta$ and $V_{\mathcal{F}}$
as defined in Theorem 3.1, and

$\operatorname{bias\,II}=\sup\Bigl{\\{}\left|\tfrac{n}{k}\operatorname{\mathbb{P}}[{V\in\tfrac{n}{k}B,Y=\sigma
1}]-\operatorname{\mathbb{P}}[{Y=\sigma 1}]\mu_{\sigma}(B)\right|:\\\
\text{$B=\Gamma_{A}^{+}$ or $B=\Gamma_{A}^{-}$ for some $A\in\mathcal{A}$ and
$\sigma\in\\{-,+\\}$}\Bigr{\\}}.$

The proof relies on the relationships between the (empirical) classification
risks and the (empirical) angular measure pointed out in Lemmata 4.1 and C.1,
which imply that

$\displaystyle|\widehat{L}^{\tau}(g)-L_{\infty}^{>\tau}(g)|$
$\displaystyle\leqslant\Bigl{|}\frac{n_{+}}{n}\widehat{\Phi}_{+}(\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau})-p\Phi_{+}(\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau})\Bigr{|}$
$\displaystyle\quad\mbox{}+\Bigl{|}\frac{n_{-}}{n}\widehat{\Phi}_{-}(\mathbb{S}_{g}^{+}\cap\mathbb{S}_{\tau})-(1-p)\Phi_{-}(\mathbb{S}_{g}^{+}\cap\mathbb{S}_{\tau})\Bigr{|}$

for $g\in\mathcal{G}$. The right-hand side of the latter display is then
bounded uniformly in $g\in\mathcal{G}$ by adapting the proof of Theorem 3.1;
see Appendix C in the Supplement for details.

#### Truncated empirical risk and associated estimator

Consider a truncated version of the risk $\widehat{L}^{\tau}(g)$ where the
observations $X_{i}$ such that $\lVert{\widehat{V}_{i}}\rVert$ exceeds $Mn/k$
are not taken into account, where $M>1$ is a truncation level as in Section
3.3:

$\widehat{L}^{\tau,M}(g)=\frac{M}{k(M-1)}\sum_{i=1}^{n}\mathbbm{1}\\{g(\widehat{V}_{i})\neq
Y_{i},\,\theta(\widehat{V}_{i})\in\mathbb{S}_{\tau},\,n/k\leqslant\lVert{\widehat{V}_{i}}\rVert\leqslant
Mn/k\\}.$ (42)

Let $\hat{g}_{k}^{\tau,M}$ denote the minimizer of $\widehat{L}^{\tau,M}(g)$
among a family of angular classifiers $\mathcal{G}$. As in Theorem 4.2 it can
be proven that on an event with large probability,

$\sup_{g\in\mathcal{G}}|\widehat{L}^{\tau,M}(g)-L_{\infty}^{>\tau}(g)|\leqslant
2\left(\operatorname{error_{M}\,II}+\operatorname{bias_{M}\,II}+\operatorname{gap_{M}\,II}\right),$

where $\operatorname{error_{M}\,II}$, $\operatorname{bias_{M}\,II}$ and
$\operatorname{gap_{M}\,II}$ have expressions similar (if not identical) to
$\operatorname{error}_{M}$, $\operatorname{bias}_{M}$ and
$\operatorname{gap}_{M}$ respectively in Theorem 3.2. For the sake of brevity
we leave the details to the interested reader. As in (39) this concentration
bound allows to control the asymptotic excess risk
$L_{\infty}(\hat{g}^{\tau,M}_{k})-\inf_{g\in\mathcal{G}}L_{\infty}(g)$. In
Section 5.2 we verify experimentally that the performances of
$\hat{g}_{k}^{\tau}$ and $\hat{g}_{k}^{\tau,M}$ are comparable.

##  5 Simulation experiments

Our experiments aim at (i) investigating the influence of the rank
transformation on the empirical angular measure $\widehat{\Phi}$ in (14), and
(ii) comparing the latter with its truncated version $\widehat{\Phi}_{M}$ in
(15), and this in the context of binary classification in extreme regions. We
compare the performance of the two versions of the empirical angular measure
with an oracle estimator $\widetilde{\Phi}$ obtained from probability integral
transformed data $V_{i}=v(X_{i})$ with $v$ as in (9): for integer $1\leqslant
k\leqslant n$ and for $\theta(x)=x/\lVert{x}\rVert$ with
$\lVert{\,\cdot\,}\rVert$ the max-norm,

$\widetilde{\Phi}(A)=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{\theta(V_{i})\in
A,\,\lVert{V_{i}}\rVert\geqslant n/k\\},\qquad A\subseteq\mathbb{S}.$ (43)

The latter is observable only when the marginal distributions $F_{j}$ are
known.

We report the results of two Monte Carlo experiments on simulated data. In
Section 5.1 we consider as a performance measure the worst-case error
$\sup_{A\in\mathcal{A}}|\Phi^{\prime}(A)-\Phi(A)|$ with $\Phi^{\prime}$ equal
to $\widehat{\Phi}$, $\widehat{\Phi}_{M}$ or $\widetilde{\Phi}$ and where
$\mathcal{A}$ is a collection of hyper-rectangles on $\mathbb{S}$. In our
second experiment (Section 5.2), we compare the classification scores of three
binary classifiers trained on pairs $(\theta(\widehat{V}_{i}),Y_{i})$ such
that $\lVert{\widehat{V}_{i}}\rVert$ exceeds a large threshold, and this
including or excluding the points with the largest norms.

The experiments were implemented in Python 3 using the packages numpy, scipy,
matplotlib, and scikit-learn. The computer code to reproduce the experiments
is available upon request.

###  5.1 Supremum error of the empirical angular measures

The goal of this experiment is to assess the influence of the rank
transformation and the truncation on the uniform error
$\sup_{A\in\mathcal{A}}|\Phi^{\prime}(A)-\Phi(A)|$ for $\Phi^{\prime}$ equal
to $\widehat{\Phi}$, $\widehat{\Phi}^{M}$ or $\widetilde{\Phi}$. The setting
is such that $\Phi(A)$ can be approximated with arbitrary precision by Monte
Carlo sampling, the standardization $v$ to unit-Pareto margins can be computed
analytically, and the bias term in the upper bounds of Theorems 3.1 and 3.2 is
zero. The estimation error then only stems from the stochastic error and
framing gap in (19) leading to the terms on the second and third lines in (23)
and (28).

#### Experimental setting

We consider an independent random sample $X_{1},\ldots,X_{n}$ drawn from the
distribution of a random vector $X=R\Theta$ where $R$ and $\Theta$ are
independent, the random variable $R$ follows a unit-Pareto distribution on
$[1,\infty)$ and $\Theta$ follows a symmetric Dirichlet distribution on the
unit simplex $\\{x\in[0,1]^{d}:x_{1}+\cdots+x_{d}=1\\}$ with parameter
$(\nu,\ldots,\nu)$ for some concentration parameter $\nu>0$. The larger $\nu$,
the stronger $\Theta$ is concentrated around the barycenter
$(1/d,\ldots,1/d)$.

In this setting, all statistics involved in our analysis are easily
computable. The following facts are an immediate consequence of Lemma D.1 in
the supplement. Let $A\subseteq\mathbb{S}$ be a Borel set, let $\tau\in(0,1)$
and recall $\mathbb{S}_{\tau}$ in (20).

  * •

If $n/k>d/\tau$, the pseudo-empirical estimator $\widetilde{\Phi}$ in (43) is

$\tilde{\Phi}(A)=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{\Theta_{i}/\lVert{\Theta_{i}}\rVert\in
A,\,dR_{i}\lVert{\Theta_{i}}\rVert\geqslant n/k\\}.$

  * •

The true $\Phi(A)$ may be approached with arbitrary precision by the Monte
Carlo estimator

$\Phi_{\text{MC}}(A)=\frac{d}{N}\sum_{i=1}^{N}\mathbbm{1}\\{X_{i}^{\prime}\in\mathcal{C}_{A}\\}=\frac{d}{N}\sum_{i=1}^{N}\mathbbm{1}\\{\Theta_{i}^{\prime}/\lVert{\Theta_{i}^{\prime}}\rVert\in
A,\,R_{i}^{\prime}\lVert{\Theta_{i}^{\prime}}\rVert\geqslant 1\\},$ (44)

where $X_{i}^{\prime}=(R_{i}^{\prime},\Theta_{i}^{\prime})$ for
$i\in\\{1,\ldots,n\\}$ is another independent random sample from the law of
$(R,\Theta)$. The Monte Carlo estimator is unbiased and has variance bounded
by $d^{2}/(4N)$.

  * •

We have
$\Phi(A)=\frac{n}{k}\operatorname{\mathbb{P}}[{V\in\frac{n}{k}\mathcal{C}_{A}}],$
so that the bias term in Theorems 3.1 and 3.2 is null.

We consider dimensions $d=2$ and $d=5$. The concentration parameter of the
Dirichlet distribution for $\Theta$ is set to $\nu=10$. The sample sizes
considered are $n\in\\{5\cdot 10^{3},10^{4},5\cdot 10^{4},10^{5},5\cdot
10^{5},10^{6}\\}$. For each $n$, the integer $k$ is set to $\sqrt{n}$ rounded
down. We choose $\mathcal{A}$ as the finite collection of hyper-rectangles
forming a regular grid on $\mathbb{S}_{\tau}$ for $\tau=0.1$ with side length
$h=(1-\tau)/S$ with $S=5$. Each set $A\in\mathcal{A}$ is of the form
$A=A_{1}\times\cdots\times A_{d}$, where, for some $j_{0}\in\\{1,\ldots,d\\}$
and some integer vector $(i_{j})_{j\neq j_{0}}\in\\{0,1,\ldots,S-1\\}^{d-1}$,
we have

$A_{j}=\begin{cases}\\{1\\}&\text{if $j=j_{0}$},\\\
(\tau+i_{j}h,\tau+(i_{j}+1)h)&\text{if $j\neq j_{0}$}.\end{cases}$

The Monte Carlo sample size in (44) is set to $N=5\cdot 10^{8}$ so that
$\Phi_{\mathrm{MC}}(A)$ has standard deviation at most $d/\sqrt{4N}\leqslant
d\cdot 2.24\cdot 10^{-5}$. As seen below, the latter is negligible compared to
the deviations of $\widetilde{\Phi}$, $\widehat{\Phi}$ and
$\widehat{\Phi}_{M}$ from $\Phi_{\text{MC}}$. For ease of writing, we identify
$\Phi$ and $\Phi_{\mathrm{MC}}$.

#### Results

Figures 1 and 2 show the supremum errors
$\sup_{A\in\mathcal{A}}|\Phi^{\prime}(A)-\Phi(A)|$ averaged over 50
independent experiments as a function of $k$ (axes on log-scales) for
$\Phi^{\prime}$ equal to $\widehat{\Phi}$, $\widehat{\Phi}^{M}$ or
$\widetilde{\Phi}$ in dimensions $d=2$ and $d=5$ respectively. In each figure,
the three panels correspond to three values of $M$ in (15), chosen such that
(from left to right) $10\%$, $5\%$ and $2\%$ of the set
$\\{i=1,\ldots,n:\lVert{\widehat{V}_{i}}\rVert\geqslant n/k\\}$ is discarded.

(a)

(b)

(c)

Figure 1: Average errors $\sup_{A\in\mathcal{A}}|\Phi^{\prime}(A)-\Phi(A)|$,
$\Phi^{\prime}\in\\{\widehat{\Phi},\widehat{\Phi}_{M},\widetilde{\Phi}\\}$ in
dimension $d=2$, as a function of $k$ with $k=\sqrt{n}$, with axes on log
scales, over 50 independent replications. Only the error curve for
$\widehat{\Phi}_{M}$ varies between Figures 2(a), 2(b) and 2(c) where $M$ is
respectively set so that $10\%$, $5\%$ and $2\%$ of extremes are discarded.
Colored intervals represent standard deviations of the errors. The dotted line
has equation $y=1/(4\sqrt{k})$.

(a)

(b)

(c)

Figure 2: Average errors $\sup_{A\in\mathcal{A}}|\Phi^{\prime}(A)-\Phi(A)|$,
$\Phi^{\prime}\in\\{\widehat{\Phi},\widehat{\Phi}_{M},\widetilde{\Phi}\\}$ in
dimension $d=5$, as a function of $k$ with $k=\sqrt{n}$, with axes on log
scales, over 50 independent replications. Only the error curve for
$\widehat{\Phi}_{M}$ varies between Figures 2(a), 2(b) and 2(c) where $M$ is
respectively set so that $10\%$, $5\%$ and $2\%$ of extremes are discarded.
Colored intervals represent standard deviations of the errors. The dotted line
has equation $y=1/(4\sqrt{k})$.

  * •

The errors of all three estimators decrease at rate $1/\sqrt{k}$, in line with
our theoretical findings.

  * •

Perhaps surprisingly, the oracle estimator $\widetilde{\Phi}$, using knowledge
of margins, is—to a small extent—outperformed by the rank-based
$\widehat{\Phi}$. This finding is consistent with [29] and [6], who show that,
for positively associated pairs, as is the case here, the asymptotic variance
of the rank-based empirical (tail) copula is less than the one of the oracle
estimator.

  * •

The only situation where the truncated estimator $\widehat{\Phi}_{M}$ has
significantly worse performance than the other two is when the dimension is
low and the sample size is large (Figure 2(a)). In all other cases, the three
estimators have comparable performance.

###  5.2 Binary classification in extreme regions

We place ourselves in the classification framework described in Section 4.2,
where two angular classifiers $\widehat{g}^{\tau}$ and $\widehat{g}^{\tau,M}$
are proposed, the first one based on all training data with
$\lVert{\widehat{V}_{i}}\rVert\geqslant n/k$ and the second one using only
those training data with $n/k\leqslant\lVert{\widehat{V}_{i}}\rVert\leqslant
Mn/k$ for a truncation level $M>1$. The aim of this experiment is to assess
the impact of the truncation on the classification error as measured on a test
set.

#### Experimental setting for classification

Our set-up generalizes the one in Section 5.1 to binary classification. The
training set is an independent random sample $\\{(X_{i},Y_{i})\\}_{i=1}^{n}$
from the distribution of a random vector $(X,Y)$ with $X=R\Theta$ where $R$
and $(\Theta,Y)$ are independent, $R$ is unit-Pareto, $Y$ takes values in
$\\{-1,+1\\}$, and the conditional distribution of $\Theta$ given $Y=\sigma 1$
is symmetric Dirichlet on the unit simplex
$\\{x\in[0,1]^{d}:x_{1}+\cdots+x_{d}=1\\}$ with concentration parameter
$(\nu_{\sigma},\ldots,\nu_{\sigma})$ where $\nu_{\sigma}>0$ for
$\sigma\in\\{-,+\\}$. The conclusions of Lemma D.1 then hold for the
conditional distributions of $X$ given $Y=\sigma 1$ for $\sigma\in\\{-,+\\}$.

The classifiers are trained on the points $(\theta(\widehat{V}_{i}),Y_{i})$
with $\widehat{V}_{i}$ in (10) for indices $i$ in the sets

$\displaystyle\left\\{i=1,\ldots,n:\
\theta(\widehat{V}_{i})\in\mathbb{S}_{\tau},\,\lVert{\widehat{V}_{i}}\rVert\geqslant
n/k\right\\}$ and $\displaystyle\left\\{i=1,\ldots,n:\
\theta(\widehat{V}_{i})\in\mathbb{S}_{\tau},\,n/k\leqslant\lVert{\widehat{V}_{i}}\rVert\leqslant
Mn/k\right\\}.$

These choices are in line with the empirical angular measures without and with
truncation, respectively. The parameter $\tau\in(0,1)$ takes care of the need
to stay away from the boundary of $\mathbb{S}$; see Assumption 1. The feature
vectors $\theta(\widehat{V}_{i})$ take values in $\mathbb{S}$, so that the
classifiers are angular by construction.

We consider three families $\mathcal{G}$ of binary classifiers: logistic
regression, classification trees and random forests. Following current
practice, the actual calibration of the parameters is based on empirical risk
minimization as in (38) and (42) but with some modifications. For logistic
regression, the deviance is used instead of the classification risk. For
classification trees, the training proceeds stepwise considering one feature
at a time according to a greedy and randomized approach, while random forests
combine several such trees through majority voting. The collections
$\mathcal{A}=\bigcup_{\sigma\in\\{-,+\\}}\\{\mathbb{S}_{g}^{\sigma}\cap\mathbb{S}_{\tau}:g\in\mathcal{G}\\}$
generated by the three families $\mathcal{G}$ are intersections of a bounded
number of half-spaces and unions thereof. The number of intersections and
unions are determined by the dimension $d$, the maximal depth of the
classification trees and the number of such trees in the random forest. In
view of Section 3.4, the collections $\mathcal{A}$ satisfy Assumptions 1 and
2, as required.

To measure the generalization performance of the resulting classifiers
$\widehat{g}^{\tau}$ and $\widehat{g}^{\tau,M}$ we generate a test set
$\\{(X^{\prime}_{i},Y^{\prime}_{i})\\}_{i=1}^{n}$ in the same way as the
training set and independent from the latter. Let
$\widehat{V}^{\prime}_{i}=\hat{{v}}(X^{\prime}_{i})$ denote the transformed
points using the rank transform $\hat{{v}}$ in (11) issued from the training
step. As in Section 4.2 we restrict our attention to test data such that
$\widehat{V}_{i}^{\prime}$ has a large norm and has an angle in
$\mathbb{S}_{\tau}$. More precisely, we consider the index set:

$\displaystyle\mathcal{I}_{\text{test}}^{\tau}=\left\\{i=1,\ldots,n^{\prime}:\theta(\widehat{V}_{i}^{\prime})\in\mathbb{S}_{\tau},\lVert{\widehat{V}_{i}^{\prime}}\rVert\geqslant
n/k\right\\}.$

The classification test error of a candidate angular classifier $g$ is thus

$L_{\text{test}}^{\tau}(g)=\frac{1}{|\mathcal{I}_{\text{test}}^{\tau}|}\sum_{i\in\mathcal{I}_{\text{test}}^{\tau}}\mathbbm{1}\\{g(\theta(\widehat{V}_{i}^{\prime}))\neq
Y^{\prime}_{i}\\}.$ (45)

Training and test samples of size $n=10^{5}$ were generated in dimension
$d=10$. As in Section 5.1, we set $\tau=0.1$ and $k=\lfloor{\sqrt{n}}\rfloor$,
ensuring sufficiently large training sets as well as $n/k>d/\tau$. We fix the
number of positive and negative instances to $n/2$ in both the training and
test sets so as to mimic a balanced mixture model with
$p=\operatorname{\mathbb{P}}[{Y=+1}]=1/2$. The truncation level $M>1$ is
selected so that the top-$5\%$ of the observations with
$\lVert{\widehat{V}_{i}}\rVert\geqslant n/k$ are discarded. The class-specific
Dirichlet concentration parameters are $\nu_{+}=1$ and $\nu_{-}=2$.

#### Results

Figure 3 displays boxplots of the quantities
$L_{\text{test}}^{\tau}(\widehat{g}^{\tau})$ and
$L_{\text{test}}^{\tau}(\widehat{g}^{\tau,M})$ in (45) after 100 independent
replications. The three panels correspond to logistic regression,
classification trees and random forests, respectively. Two-sample
Kolmogorov–Smirnov tests between the empirical distributions over the 100
replications of the test errors with and without truncation did not allow to
reject the null hypothesis of equality between distributions, as the minimum
p-value over the three pair-wise comparisons was 0.91. This supports the
viability of the truncation-based method as an alternative to the untruncated
one.

(a)

(b)

(c)

Figure 3: Boxplots over 100 independent replications of the classification
test error (45) of the angular classifiers $\widehat{g}^{\tau}$ and
$\widehat{g}^{\tau,M}$ without and with truncation of the most extreme values
issued from logistic regression (a), classification trees (b) and random
forests (b).

##  6 Conclusion

We derived non-asymptotic guarantees in the form of concentration inequalities
for the rank-based empirical angular measure with respect to the max-norm. The
bounds are valid in any dimension and concern the supremum error over certain
collections of subsets of the sphere. Apart from a logarithmic term, the
bounds match the convergence rate known in the bivariate case [23, 25]. The
logarithmic term can be removed by discarding the largest observations. Two
applications to statistical learning based on observations in extreme regions
are worked out: minimum-volume set estimation and binary classification.

It would be interesting to be able to complement our upper bounds with lower
bounds on the estimation error. Sharp bounds would provide guidance on the
choice of the threshold parameter $k$ and the truncation level $M$, ideally in
an adaptive manner as in [4].

The truncated empirical angular measure was based on a hard threshold,
discarding a certain fraction of the largest observations altogether.
Alternatively, one could use weights to regulate the influence of large
observations on the estimator.

The results are limited to the max-norm because for other choices, the norm of
a vector also depends on components which are not necessarily large—the latter
are masked in case of the max-norm. Avoiding non-extreme components is also
why we focused on subsets of the relative interior of the unit sphere, staying
away from the relative boundary. Allowing for sets touching the latter and
extending the theory to the popular sum and Euclidean norms constitute
important but challenging avenues for further research.

The application to classification was limited to two balanced classes.
Extensions to multiple classes and to unbalanced situations can be worked out
in the same way. Of an altogether different nature, however, is the prediction
of a continuous response from observations in extreme regions. The latter
would require concentration inequalities for the empirical angular measure
evaluated on collections of functions more general than set indicators. This
topic has not yet even been broached in the bivariate case.

## References

  * [1] [author] Beirlant, JanJ., Escobar-Bach, MikaelM., Goegebeur, YuriY. and Guillou, ArmelleA. (2016). Bias-corrected estimation of stable tail dependence function. Journal of Multivariate Analysis 143 453–466.
  * [2] [author] Beirlant, J.J., Goegebeur, Y.Y., Segers, J.J. and Teugels, J.J. (2005). Statistics of Extremes: Theory and Applications. Wiley Series in Probability and Statistics.
  * [3] [author] Boldi, M. O.M. O. and Davison, A. C.A. C. (2007). A mixture model for multivariate extremes. 69 217–229.
  * [4] [author] Boucheron, StéphaneS. and Thomas, MaudM. (2015). Tail index estimation, concentration and adaptivity. Electronic Journal of Statistics 9 2751–2792.
  * [5] [author] Bousquet, OlivierO., Boucheron, StéphaneS. and Lugosi, GáborG. (2004). Introduction to Statistical Learning Theory. In Advanced Lectures on Machine Learning, (OlivierO. Bousquet, UlrikeU. von Luxburg and GunnarG. Rätsch, eds.). Lecture Notes in Artificial Intelligence 3176 169–207. Springer, Berlin.
  * [6] [author] Bücher, AxelA. (2014). A note on nonparametric estimation of bivariate tail dependence. Statistics & Risk Modeling 31 151–162.
  * [7] [author] Castro Camilo, DanielaD. and de Carvalho, MiguelM. (2017). Spectral density regression for bivariate extremes. Stochastic Environmental Research and Risk Assessment volume 31 1603–1613.
  * [8] [author] Chautru, EmilieE. (2015). Dimension reduction in multivariate extreme value analysis. Electronic Journal of Statistics 9 383–418.
  * [9] [author] Coles, Stuart G.S. G. and Tawn, Jonathan A.J. A. (1991). Modelling extreme multivariate events. Journal of the Royal Statistical Society. Series B (Statistical Methodology) 53 377–392.
  * [10] [author] Cooley, DanielD., Davis, Richard A.R. A. and Naveau, PhilippeP. (2010). The pairwise beta distribution: A flexible parametric multivariate model for extremes. Journal of Multivariate Analysis 101 2103–2117.
  * [11] [author] Cooley, DanielD. and Thibaud, EmericE. (2019). Decompositions of dependence for high-dimensional extremes. Biometrika 106 587–604.
  * [12] [author] Das, BikramjitB., Mitra, AbhimanyuA. and Resnick, SidneyS. (2013). Living on the multidimensional edge: seeking hidden risks using regular variation. Advances in Applied Probability 45 139–163.
  * [13] [author] de Carvalho, MiguelM. and Davison, Anthony C.A. C. (2014). Spectral density ratio models for multivariate extremes. Journal of the American Statistical Association 109 764–776.
  * [14] [author] de Carvalho, MiguelM., Oumow, BorisB., Segers, JohanJ. and Warchoł, MichałM. (2013). A Euclidean likelihood estimator for bivariate tail dependence. Communications in Statistics – Theory and Methods 42 1176–1192.
  * [15] [author] de Haan, LaurensL. and de Ronde, JohnJ. (1998). Sea and wind: multivariate extremes at work. Extremes 1 7–45.
  * [16] [author] de Haan, LaurensL. and Ferreira, AnaA. (2007). Extreme Value Theory: An Introduction. Springer Science & Business Media.
  * [17] [author] de Haan, LaurensL. and Resnick, Sidney IS. I. (1977). Limit theory for multivariate sample extremes. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 40 317–337.
  * [18] [author] de Haan, LaurensL. and Sinha, Ashoke KumarA. K. (1999). Estimating the probability of a rare event. The Annals of Statistics 27 732–759.
  * [19] [author] Drees, HolgerH. and Sabourin, AnneA. (2019). Principal component analysis for multivariate extremes. (to appear) https://arxiv.org/abs/1906.11043.
  * [20] [author] Einmahl, J. H. J.J. H. J. and Mason, D. M.D. M. (1992). Generalized quantile process. The Annals of Statistics 20 1062–1078.
  * [21] [author] Einmahl, John H. J.J. H. J., de Haan, LaurensL. and Krajina, AndreaA. (2013). Estimating extreme bivariate quantile regions. Extremes 16 121–145.
  * [22] [author] Einmahl, John H. J.J. H. J., de Haan, LaurensL. and Li, DeyuanD. (2006). Weighted approximations of tail copula processes with application to testing the bivariate extreme value condition. The Annals of Statistics 34 1987–2014.
  * [23] [author] Einmahl, John H. J.J. H. J., de Haan, LaurensL. and Piterbarg, Vladimir I.V. I. (2001). Nonparametric estimation of the spectral measure of an extreme value distribution. The Annals of Statistics 29 1401–1423.
  * [24] [author] Einmahl, John H. J.J. H. J., de Haan, LaurensL. and Sinha, Ashoke KumarA. K. (1997). Estimating the spectral measure of an extreme value distribution. Stochastic Processes and their Applications 70 143–171.
  * [25] [author] Einmahl, John H. J.J. H. J. and Segers, JohanJ. (2009). Maximum empirical likelihood estimation of the spectral measure of an extreme-value distribution. The Annals of Statistics 37 2953–2989.
  * [26] [author] Engelke, SebastianS. and Ivanovs, JevgenijsJ. (2017). Robust bounds in multivariate extremes. Annals of Applied Probability 27 3706–3734.
  * [27] [author] Engelke, SebastianS. and Ivanovs, JevgenijsJ. (2021). Sparse structures for multivariate extremes. Annual Review of Statistics and Its Application 8 241–270.
  * [28] [author] Fougères, Anne-LaureA.-L., de Haan, LaurensL. and Mercadier, CécileC. (2015). Bias correction in multivariate extremes. The Annals of Statistics 43 903–934.
  * [29] [author] Genest, ChristianC. and Segers, JohanJ. (2010). On the covariance of the asymptotic empirical copula process. Journal of Multivariate Analysis 101 1837–1845.
  * [30] [author] Goix, N.N., Sabourin, A.A. and Clémençon, S.S. (2015). Learning the Dependence Structure of Rare Events: a Nonasymptotic Study. In Proceedings of the International Conference on Learning Theory, COLT’15.
  * [31] [author] Goix, NicolasN., Sabourin, AnneA. and Clémençon, StephanS. (2017). Sparse representation of multivariate extremes with applications to anomaly detection. Journal of Multivariate Analysis 161 12–31.
  * [32] [author] Guillou, ArmelleA., Naveau, PhilippeP. and You, AlexandreA. (2015). A folding methodology for multivariate extremes: estimation of the spectral probability measure and actuarial applications. Scandinavian Actuarial Journal 2015 549–572.
  * [33] [author] Hult, HenrikH. and Lindskog, FilipF. (2006). Regular variation for measures on metric spaces. Publications de l’Institut Mathematique 94 121–140.
  * [34] [author] Jalalzai, HamidH., Clémençon, StephanS. and Sabourin, AnneA. (2018). On Binary Classification in Extreme Regions. In Advances in Neural Information Processing Systems 3092–3100.
  * [35] [author] Janßen, AnjaA. and Wan, PhyllisP. (2020). $k$-means clustering of extremes. Electronic Journal of Statistics 14 1211–1233.
  * [36] [author] Koltchinskii, V.V. (2006). Local Rademacher complexities and oracle inequalities in risk minimization (with discussion). The Annals of Statistics 34 2593–2706.
  * [37] [author] Lehtomaa, JaakkoJ. and Resnick, Sidney I.S. I. (2020). Asymptotic independence and support detection techniques for heavy-tailed multivariate data. Insurance: Mathematics and Economics 93 262–277.
  * [38] [author] Lugosi, G.G. (2002). Pattern classification and learning theory. In Principles of nonparametric learning (Udine, 2001). CISM Courses and Lect. 434 1–56. Springer, Vienna. 1987656
  * [39] [author] Meyer, NicolasN. and Wintenberger, OlivierO. (2019). Sparse regular variation. https://arxiv.org/abs/1907.00686.
  * [40] [author] Mohri, MehryarM., Rostamizadeh, AfshinA. and Talwalkar, AmeetA. (2018). Foundations of Machine Learning. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA.
  * [41] [author] Polonik, W.W. (1997). Minimum volume sets and generalized quantile processes. Stochastic Processes and their Applications 69 1–24.
  * [42] [author] Resnick, Sidney I.S. I. (1987). Extreme Values, Regular Variation, and Point Processes 4\. Springer-Verlag, New York.
  * [43] [author] Resnick, Sidney I.S. I. (2007). Heavy-Tail Phenomena: Probabilistic and Statistical Modeling. Springer Science & Business Media.
  * [44] [author] Sabourin, AnneA. (2015). Semi-parametric modeling of excesses above high multivariate thresholds with censored data. Journal of Multivariate Analysis 136 126–146.
  * [45] [author] Sabourin, AnneA. and Naveau, PhilippeP. (2014). Bayesian Dirichlet mixture model for multivariate extremes: A re-parametrization. Computational Statistics & Data Analysis 71 542–567.
  * [46] [author] Scott, C.C. and Nowak, R.R. (2006). Learning minimum volume sets. Journal of Machine Learning Research 7 665–704.
  * [47] [author] Thomas, AlbertA., Clemencon, StéphanS., Gramfort, AlexandreA. and Sabourin, AnneA. (2017). Anomaly Detection in Extreme Regions via Empirical MV-sets on the Sphere. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AartiA. Singh and JerryJ. Zhu, eds.). Proceedings of Machine Learning Research 54 1011–1019. PMLR, Fort Lauderdale, FL, USA.
  * [48] [author] van der Vaart, AadA. and Wellner, Jon A.J. A. (2009). A note on bounds for VC dimensions. In High dimensional probability V: the Luminy volume. Inst. Math. Stat. (IMS) Collect. 5 103–107. Inst. Math. Statist., Beachwood, OH.
  * [49] [author] van der Vaart, Aad W.A. W. and Wellner, Jon A.J. A. (1996). Weak Convergence and Empirical Process. With Applications to Statistics. Springer-Verlag, New York.
  * [50] [author] Wadsworth, J. L.J. L., Tawn, J. A.J. A., Davison, A. C.A. C. and Elton, D. M.D. M. (2017). Modelling across extremal dependence classes. Journal of the Royal Statistical Society. Series B (Statistical Methodology) 79 149–175.

Supplement

This supplement contains proofs and additional auxiliary results to the main
paper.

##  Appendix A Auxiliary results

We start with stating auxiliary results that are used in the proof of the main
theorems.

######  Theorem A.1 (Theorem 1 in [30]).

Let $P_{n}$ denote the empirical distribution of an independent random sample
$\xi_{1},\ldots,\xi_{n}$ from a distribution $P$ on some measurable space. Let
$\mathcal{A}$ be a VC-class of measurable subsets of the state space with VC-
dimension $V_{\mathcal{A}}$. Let $B$ be a measurable subset containing
$\bigcup_{A\in\mathcal{A}}A$ and write $p=P(B)$. There is an absolute constant
$C>0$ such that, for all $\delta\in(0,1)$, on an event with probability at
least $1-\delta$, we have

$\sup_{A\in\mathcal{A}}\lvert{P_{n}(A)-P(A)}\rvert\leqslant
C\left(\sqrt{pV_{\mathcal{A}}n^{-1}\log(1/\delta)}+n^{-1}\log(1/\delta)\right).$

In [30], the constant $C$ is not made explicit. Just before their Lemma 14,
there is a reference to [36] providing bounds on the expectation of a
symmetrized supremum, but from that source, the constant looks near impossible
to trace. An alternative route to obtain a value for the constant is via
Theorems 1.16–17 in [38], giving an explicit bound for the expectation of a
symmetrized supremum in terms of an integral over covering numbers of the
class of sets. In turn, the covering numbers of such a class can be bounded
explicitly in terms of its VC dimension. In this way, the constant $C$ can be
made explicit but its value is most likely going to be far from optimal, as
the cited bounds are not sharp, in particularly not the one in Theorem 1.16 in
[38]. We prefer the current write-up in terms of a generic $C$. Should a sharp
value for $C$ be found in the future, it can be substituted as is in our
results.

######  Lemma A.2.

Let $\lVert{\,\cdot\,}\rVert$ be a norm on a real vector space and write
$\theta(z)=z/\lVert{z}\rVert$ for non-zero $z$. For non-zero vectors $x$ and
$y$, we have

$\lVert{\theta(x)-\theta(y)}\rVert\leqslant
2\frac{\lVert{x-y}\rVert}{\lVert{x}\rVert\vee\lVert{y}\rVert}.$

###### Proof.

Since $\theta(\,\cdot\,)$ is scale-invariant, we can divide both $x$ and $y$
by $\lVert{x}\rVert\vee\lVert{y}\rVert$ without changing the two sides of the
inequality. For the sake of the proof we can thus assume that
$\lVert{x}\rVert=1\geqslant\lVert{y}\rVert>0$, in which case we need to show
that

$\lVert{x-\theta(y)}\rVert\leqslant 2\lVert{x-y}\rVert.$

By the triangle inequality, we have

$\lVert{x-\theta(y)}\rVert\leqslant\lVert{x-y}\rVert+\lVert{y-\theta(y)}\rVert$

and

$\lVert{y-\theta(y)}\rVert=\left|1-\tfrac{1}{\lVert{y}\rVert}\right|\lVert{y}\rVert=|\lVert{y}\rVert-1|=|\lVert{y}\rVert-\lVert{x}\rVert|\leqslant\lVert{y-x}\rVert.\qed$

##  Appendix B Empirical angular measures
Proofs of Theorems 3.1 and 3.2

###### Proof of Theorem 3.1.

The empirical exponent and angular measures $\widehat{\mu}$ and
$\widehat{\Phi}$ only depend on the sample $X_{1},\ldots,X_{n}$ through the
transformed data

$\widehat{F}_{j}(X_{ij})=\frac{1}{n}\sum_{t=1}^{n}\mathds{1}\\{X_{tj}\leqslant
X_{ij}\\}$

for $i=1,\ldots,n$ and $j=1,\ldots,d$. The sum of indicators is equal to the
rank of $X_{ij}$ within $X_{1j},\ldots,X_{nj}$. As the marginal cumulative
distribution function $F_{j}$ is continuous, the ranks of
$X_{1j},\ldots,X_{nj}$ are with probability one equal to those of
$V_{1j},\ldots,V_{nj}$, where $V_{ij}=1/(1-F_{j}(X_{ij}))$. Hence, even though
the margins $F_{1},\ldots,F_{d}$ are unknown, the fact that $\widehat{\mu}$
and $\widehat{\Phi}$ are rank statistics implies that for the sake of the
proof, we may and will henceforth assume that the margins $F_{1},\ldots,F_{d}$
are unit-Pareto.

Abbreviate $\Gamma_{A}^{\pm}=\Gamma_{A}^{\pm}(r_{\pm},3\Delta)$ with
$r_{\pm}=1+\tfrac{1}{n}-\tfrac{1}{k}\pm\Delta$ and with $\Delta$ as in the
statement of the theorem. Since $r_{-}\leqslant 1\leqslant r_{+}$, we have

$\forall
A\in\mathcal{A},\qquad\Gamma_{A}^{-}\subseteq\mathcal{C}_{A}\subseteq\Gamma_{A}^{+}.$

We shall construct an event $\mathcal{E}_{1}$ with probability at least
$1-d\delta/(d+1)$, on which we have

$\forall
A\in\mathcal{A},\qquad\tfrac{n}{k}\Gamma_{A}^{-}\subseteq\widehat{\Gamma}_{A}\subseteq\tfrac{n}{k}\Gamma_{A}^{+}.$
(46)

Then, on the event $\mathcal{E}_{1}$, the decomposition (19) of the estimation
error holds true. We treat the three terms involved in the decomposition in
turn. At the end, we construct the event $\mathcal{E}_{1}$ with the required
properties.

#### Bias term

Taking the supremum over $A\in\mathcal{A}$ immediately yields the first term
on the right-hand side of the bound (23).

#### Stochastic error

We apply Theorem A.1 to the collection

$\mathcal{F}=\left\\{\tfrac{n}{k}\Gamma_{A}^{\sigma}:\;\sigma\in\\{-,+\\},\;A\in\mathcal{A}\right\\},$
(47)

which has finite VC dimension $V$ in view of Assumption 2 and the paragraph
following Theorem 3.1; the rescaling by the factor $n/k$ obviously does not
change the VC dimension. For every $A\in\mathcal{A}$, we have

$\tfrac{n}{k}\Gamma_{A}^{-}\subseteq\tfrac{n}{k}\Gamma_{A}^{+}\subseteq\left\\{x\in[0,\infty)^{d}:\
\lVert{x}\rVert\geqslant\tfrac{n}{k}\tfrac{1}{1+\Delta}\right\\}.$

Since the margins of $P$ are unit-Pareto, it follows that the probability $p$
appearing in Theorem A.1 applied to $\mathcal{F}$ is bounded by

$P\left[\textstyle{\bigcup_{j=1}^{d}}\left\\{x\in[0,\infty)^{d}:x_{j}\geqslant\tfrac{n}{k}\tfrac{1}{1+\Delta}\right\\}\right]\leqslant
d(1+\Delta)\tfrac{k}{n}.$

As a consequence, on an event $\mathcal{E}_{2}$ with probability at least
$1-\delta/(d+1)$, we have,

$\displaystyle\sup_{A\in\mathcal{A},\;\sigma\in\\{-,+\\}}\tfrac{n}{k}\lvert
P_{n}(\tfrac{n}{k}\Gamma_{A}^{\sigma})-P(\tfrac{n}{k}\Gamma_{A}^{\sigma}))\rvert$
$\displaystyle\leqslant\tfrac{n}{k}C\left(\sqrt{d(1+\Delta)\tfrac{k}{n}V(\mathcal{F})n^{-1}\log((d+1)/\delta)}+n^{-1}\log((d+1)/\delta)\right)$
$\displaystyle=C\left(\sqrt{d(1+\Delta)V(\mathcal{F})k^{-1}\log((d+1)/\delta)}+k^{-1}\log((d+1)/\delta)\right).$

This is the second term on the right-hand side of the bound (23). Since
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ have probabilities at least
$1-d\delta/(d+1)$ and $1-\delta/(d+1)$, respectively, the event
$\mathcal{E}_{1}\cap\mathcal{E}_{2}$ has probability at least $1-\delta$.

#### Framing gap

For $A\in\mathcal{A}$, any point $x\in\Gamma_{A}^{+}\setminus\Gamma_{A}^{-}$
has either a norm $\lVert{x}\rVert$ between $r_{-}$ and $r_{+}$ or an angle
$\theta(x)$ contained in a set of the form $A_{+}(\varepsilon)\setminus
A_{-}(\varepsilon)$ for some $\varepsilon>0$. Specifically,

$\mu(\Gamma_{A}^{+}\setminus\Gamma_{A}^{-})\\\
\leqslant\mu\left(\left\\{x\in[0,\infty)^{d}:\
(1+\tfrac{1}{n}-\tfrac{1}{k}+\Delta)^{-1}\leqslant\lVert{x}\rVert<(1+\tfrac{1}{n}-\tfrac{1}{k}-\Delta)^{-1}\right\\}\right)\\\
+\mu\left(\left\\{x\in[0,\infty)^{d}:\ \lVert{x}\rVert\geqslant
1,\;\theta(x)\in A_{+}(3\Delta\lVert{x}\rVert)\setminus
A_{-}(3\Delta\lVert{x}\rVert)\right\\}\right).$ (48)

The first term on the right-hand side in (48) is equal to

$\left((1+\tfrac{1}{n}-\tfrac{1}{k}+\Delta)-(1+\tfrac{1}{n}-\tfrac{1}{k}-\Delta)\right)\mu(\\{x\in[0,\infty)^{d}:\lVert{x}\rVert\geqslant
1\\})=2\Delta\Phi(\mathbb{S}).$

The second term on the right-hand side in (48) can be computed via the product
representation (7) of $\mu$ in polar coordinates: in view of (21) in
Assumption 1, the result is

$\displaystyle\int_{1}^{\infty}\Phi\bigl{(}A_{+}(3\Delta r)\setminus
A_{-}(3\Delta r)\bigr{)}\frac{\mathrm{d}r}{r^{2}}$
$\displaystyle\leqslant\int_{1}^{\infty}\min\\{\Phi(\mathbb{S}),3c\Delta
r\\}\frac{\mathrm{d}r}{r^{2}}$
$\displaystyle=3c\Delta(1+\log\Phi(\mathbb{S})-\log(3c\Delta)),$

since $\int_{1}^{\infty}\min(b,ar)\frac{\mathrm{d}r}{r^{2}}=a(\log(b/a)+1)$
for $a\in(0,b]$ and $3c\Delta\leqslant 1\leqslant\Phi(\mathbb{S})$ by
assumption.

The resulting upper bound in (48) does not depend on $A\in\mathcal{A}$.
Bounding $\Phi(\mathbb{S})$ by $d$, we obtain the third term on the right-hand
side of the bound (23).

#### Construction of the event $\mathcal{E}_{1}$

We still need to construct an event $\mathcal{E}_{1}$ with probability at
least $1-d\delta/(d+1)$ on which the inclusions (46) hold. To do this, we
apply Theorem A.1 to each of the collections

$\mathcal{F}_{j}=\left\\{\\{x\in[0,\infty)^{d}:x_{j}>\tfrac{n}{k}y\\}:\
y\in[\rho,\infty)\right\\},\qquad j=1,\ldots,d.$

Fix $j=1,\ldots,d$ and let $P_{n,j}=n^{-1}\sum_{i=1}^{n}\delta_{X_{ij}}$. Each
set in the collection $\mathcal{F}_{j}$ is a subset of
$\\{x\in[0,\infty)^{d}:x_{j}>\tfrac{n}{k}\rho\\}$, whose $P$-probability is
$p=\tfrac{k}{n}\rho^{-1}$. The class $\mathcal{F}_{j}$ has VC dimension $1$.
By Theorem A.1, there exists an event $\mathcal{E}_{1,j}$ with probability at
least $1-\delta/(d+1)$ on which

$\displaystyle\sup_{x_{j}\geqslant\frac{n}{k}\rho}\left|P_{n,j}((x_{j},\infty))-x_{j}^{-1}\right|$
$\displaystyle\leqslant
C\left(\sqrt{\tfrac{k}{n}\rho^{-1}n^{-1}\log((d+1)/\delta)}-n^{-1}\log((d+1)/\delta)\right)$
$\displaystyle=n^{-1}C\left(\sqrt{k\rho^{-1}\log((d+1)/\delta)}+\log((d+1)/\delta)\right)=\tfrac{k}{n}\Delta.$
(49)

Since

$\hat{v}_{j}(x_{j})=\frac{1}{1-\frac{n}{n+1}P_{n,j}((-\infty,x_{j}])}=\frac{n+1}{nP_{n,j}((x_{j},\infty))+1},$

we have on the event $\mathcal{E}_{1,j}$ the bounds

$\forall
x_{j}\geqslant\tfrac{n}{k}\rho,\qquad\frac{n+1}{nx_{j}^{-1}+k\Delta+1}\leqslant\hat{v}_{j}(x_{j})\leqslant\frac{n+1}{(nx_{j}^{-1}-k\Delta)_{+}+1}.$
(50)

Moreover, since $\hat{v}_{j}$ is monotone, we have on $\mathcal{E}_{1,j}$ the
inequalities

$\forall
x_{j}\leqslant\tfrac{n}{k}\rho,\qquad\hat{v}_{j}(x_{j})\leqslant\hat{v}_{j}(\tfrac{n}{k}\rho)\leqslant\frac{n+1}{k(\rho^{-1}-\Delta)+1}\leqslant\frac{n}{k}\frac{\rho}{1-\rho\Delta}\leqslant\frac{n}{k}\tau.$
(51)

Let $\mathcal{E}_{1}=\bigcap_{j=1}^{d}\mathcal{E}_{1,j}$, the probability of
which is at least $1-d\delta/(d+1)$, as required. We need to show that on
$\mathcal{E}_{1}$, the inclusions (46) hold. To do so, we proceed in steps.
Throughout, we work on $\mathcal{E}_{1}$.

_Step 1: Restriction to $(\tfrac{n}{k}\rho,\infty)^{d}$._ — If
$x\in[0,\infty)^{d}$ is such that
$\lVert{\hat{v}(x)}\rVert\geqslant\tfrac{n}{k}$ but there exists
$j=1,\ldots,d$ with $x_{j}\leqslant\tfrac{n}{k}\rho$, then, by (51), we have
on $\mathcal{E}_{1}$ the bound

$\theta_{j}(\hat{v}(x))=\frac{\hat{v}_{j}(x_{j})}{\lVert{\hat{v}(x)}\rVert}\leqslant\tau$

and thus, by Assumption 1, necessarily $\theta(\hat{v}(x))\not\in A$ for all
$A\in\mathcal{A}$. Hence, on $\mathcal{E}_{1}$, we have

$\widehat{\Gamma}_{A}=\left\\{x\in(\tfrac{n}{k}\rho,\infty)^{d}:\
\lVert{\hat{v}(x)}\rVert\geqslant\tfrac{n}{k},\;\theta(\hat{v}(x))\in
A\right\\}.$ (52)

_Step 2: Radial framing._ — On $\mathcal{E}_{1}$, we have

$\forall
x\in[0,\infty)^{d},\qquad\lVert{x}\rVert\geqslant\frac{n}{k}\frac{1}{1+\frac{1}{n}-\frac{1}{k}-\Delta}\implies\lVert{\hat{v}(x)}\rVert\geqslant\frac{n}{k}.$
(53)

Indeed, for such $x$, there exists $j=1,\ldots,d$ such that
$x_{j}\geqslant\tfrac{n}{k}\tfrac{1}{1+1/n-1/k-\Delta}$ and thus, on
$\mathcal{E}_{1}$,

$\displaystyle\hat{v}_{j}(x_{j})$
$\displaystyle\geqslant\hat{v}_{j}(\tfrac{n}{k}\tfrac{1}{1+1/n-1/k-\Delta})$
$\displaystyle\geqslant\frac{n+1}{n\frac{k}{n}(1+\frac{1}{n}-\frac{1}{k}-\Delta)+k\Delta+1}=\frac{n+1}{k(1+\frac{1}{n})}=\frac{n}{k}.$

Furthermore, on $\mathcal{E}_{1}$, we have

$\forall
x\in[\tfrac{n}{k}\rho,\infty)^{d},\qquad\lVert{\hat{v}(x)}\rVert\geqslant\frac{n}{k}\implies\lVert{x}\rVert\geqslant\frac{n}{k}\frac{1}{1+\frac{1}{n}-\frac{1}{k}+\Delta}.$
(54)

Indeed, for such $x$, there exists $j=1,\ldots,d$ such that
$\hat{v}_{j}(x_{j})\geqslant\tfrac{n}{k}$ and thus, by (50), also

$\frac{n+1}{(nx_{j}^{-1}-k\Delta)_{+}+1}\geqslant\frac{n}{k},$

which implies

$x_{j}\geqslant\frac{n}{k}\frac{1}{1+\tfrac{1}{n}-\tfrac{1}{k}+\Delta}.$

Recall $\widehat{\Gamma}_{A}$ in (17). In view of (52), it follows that, on
$\mathcal{E}_{1}$, for all $A\in\mathcal{A}$, we have

$\displaystyle\widehat{\Gamma}_{A}$
$\displaystyle\supset\left\\{x\in(\tfrac{n}{k}\rho,\infty)^{d}:\
\lVert{x}\rVert\geqslant\frac{n}{k}\frac{1}{1+\frac{1}{n}-\frac{1}{k}-\Delta},\;\theta(\hat{v}(x))\in
A\right\\},$ (55) $\displaystyle\widehat{\Gamma}_{A}$
$\displaystyle\subseteq\left\\{x\in(\tfrac{n}{k}\rho,\infty)^{d}:\
\lVert{x}\rVert\geqslant\frac{n}{k}\frac{1}{1+\frac{1}{n}-\frac{1}{k}+\Delta},\;\theta(\hat{v}(x))\in
A\right\\}.$

_Step 3: Angular framing._ — We will show that, on $\mathcal{E}_{1}$, for any
$x\in[\tfrac{n}{k}\rho,\infty)^{d}$ and $A\in\mathcal{A}$,

$\theta(x)\in
A_{-}(3\tfrac{k}{n}\Delta\lVert{x}\rVert)\implies\theta(\hat{v}(x))\in
A\implies\theta(x)\in A_{+}(3\tfrac{k}{n}\Delta\lVert{x}\rVert).$ (56)

In combination with (55), this will show the inclusions (46) and thus finish
the proof.

Fix such $x$ and $A$. Put $\varepsilon=3\tfrac{k}{n}\Delta\lVert{x}\rVert$. We
consider two cases: $\varepsilon<1$ and $\varepsilon\geqslant 1$.

If $\varepsilon\geqslant 1$, the two implications in (56) are trivially
fulfilled: Since the $\lVert{\,\cdot\,}\rVert$-diameter of $\mathbb{S}$ is
equal to $1$, we have $A_{-}(\varepsilon)=\varnothing$ (as
$\mathbb{S}\setminus A$ is not-empty) while $A_{+}(\varepsilon)=\mathbb{S}$.

The interesting case is thus $\varepsilon<1$. By Lemma A.2, we have

$\lVert{\theta(\hat{v}(x))-\theta(x)}\rVert\leqslant
2\frac{\lVert{\hat{v}(x)-x}\rVert}{\lVert{x}\rVert}.$

Further, by (50), for all $j=1,\ldots,d$, since $nx_{j}^{-1}-k\Delta\geqslant
n\cdot 3\frac{k}{n}\Delta-k\Delta>0$,

$\displaystyle|\hat{v}_{j}(x_{j})-x_{j}|$
$\displaystyle=\max_{\sigma\in\\{-1,+1\\}}\left|\frac{n+1}{nx_{j}^{-1}+\sigma
k\Delta+1}-x_{j}\right|$
$\displaystyle=x_{j}\max_{\sigma\in\\{-1,+1\\}}\left|\frac{n+1}{n+(\sigma
k\Delta+1)x_{j}}-1\right|$
$\displaystyle=x_{j}\max_{\sigma\in\\{-1,+1\\}}\frac{|1-(\sigma
k\Delta+1)x_{j}|}{n+(\sigma k\Delta+1)x_{j}}.$

Recall that $x_{j}\geqslant\tfrac{n}{k}\rho\geqslant 1$ and $k\Delta\geqslant
2$. For he case $\sigma=+1$, we have

$\frac{|1-(+k\Delta+1)x_{j}|}{n+(+k\Delta+1)x_{j}}\leqslant\frac{(k\Delta+1)x_{j}}{n+(k\Delta+1)x_{j}}\leqslant\frac{3}{2}\frac{k}{n}\Delta
x_{j}.$

For the case $\sigma=-1$, we also have

$\frac{|1-(-k\Delta+1)x_{j}|}{n+(-k\Delta+1)x_{j}}=\frac{(k\Delta-1)x_{j}-1}{n+(-k\Delta+1)x_{j}}\leqslant\frac{k\Delta
x_{j}}{n-k\Delta x_{j}}\leqslant\frac{3}{2}\frac{k}{n}\Delta x_{j},$

since $\varepsilon<1$ implies $n-k\Delta x_{j}\geqslant
n-k\Delta\lVert{x}\rVert\geqslant n-n/3=2n/3$. We conclude that

$\lVert{\hat{v}(x)-x}\rVert\leqslant\frac{3}{2}\frac{k}{n}\Delta\lVert{x}\rVert^{2}$

and thus

$\lVert{\theta(\hat{v}(x))-\theta(x)}\rVert\leqslant
3\tfrac{k}{n}\Delta\lVert{x}\rVert=\varepsilon.$

The implications (56) now follow by definition of $A_{-}(\varepsilon)$ and
$A_{+}(\varepsilon)$.

We conclude that, on $\mathcal{E}_{1}$, the inclusions (46) hold, as required.
The proof Theorem 3.1 is complete. ∎

###### Proof of Theorem 3.2.

The structure of the proof is identical to the one of the proof of Theorem
3.1. Again, we can assume without loss of generality that the margins of $P$
are unit-Pareto.

#### Decomposition of the estimation error

Rather than the set $\widehat{\Gamma}_{A}$ in (17), we now write

$\widehat{\Gamma}_{A}^{M}=\hat{v}^{-1}(\tfrac{n}{k}\mathcal{C}_{A}^{M})=\left\\{x\in[0,\infty)^{d}:\
\tfrac{n}{k}\leqslant\lVert{\hat{v}(x)}\rVert<\tfrac{n}{k}M,\;\theta(\hat{v}(x))\in
A\right\\},$

so that

$\displaystyle\widehat{\Phi}_{M}(A)$
$\displaystyle=\tfrac{M}{M-1}\tfrac{n}{k}\widehat{P}_{n}(\tfrac{n}{k}\mathcal{C}_{A}^{M})=\tfrac{M}{M-1}\tfrac{n}{k}P_{n}\bigl{(}\hat{v}^{-1}(\tfrac{n}{k}\mathcal{C}_{A}^{M})\bigr{)}=\tfrac{M}{M-1}\tfrac{n}{k}P_{n}(\widehat{\Gamma}_{A}^{M}),$
$\displaystyle\Phi(A)$
$\displaystyle=\tfrac{M}{M-1}\mu(\mathcal{C}_{A}^{M})=\tfrac{M}{M-1}\tfrac{n}{k}\mu(\tfrac{n}{k}\mathcal{C}_{A}^{M}).$

Recall the sets $\Gamma_{A}^{M,-}$ and $\Gamma_{A}^{M,+}$ defined in (27). We
have

$\displaystyle 1+\tfrac{1}{n}-\tfrac{1}{k}-\Delta$
$\displaystyle<1<1+\tfrac{1}{n}-\tfrac{1}{k}+\Delta,$
$\displaystyle((1+\tfrac{1}{n})\tfrac{1}{M}-\tfrac{1}{k}-\Delta)_{+}$
$\displaystyle<\tfrac{1}{M}<(1+\tfrac{1}{n})\tfrac{1}{M}-\tfrac{1}{k}+\Delta.$

Since moreover $A_{-}(\varepsilon)\subseteq A\subseteq A_{+}(\varepsilon)$ for
any $A\in\mathcal{A}$ and $\varepsilon>0$, we have

$\forall
A\in\mathcal{A},\qquad\Gamma_{A}^{M,-}\subseteq\mathcal{C}_{A}^{M}\subseteq\Gamma_{A}^{M,+}.$

We will show that on the event $\mathcal{E}_{1}$ constructed in the proof of
Theorem 3.1 also

$\forall
A\in\mathcal{A},\qquad\tfrac{n}{k}\Gamma_{A}^{M,-}\subseteq\widehat{\Gamma}_{A}^{M}\subseteq\tfrac{n}{k}\Gamma_{A}^{M,+}.$
(57)

Then, on the event $\mathcal{E}_{1}$, we have

$\displaystyle\tfrac{M-1}{M}\bigl{(}\widehat{\Phi}_{M}(A)-\Phi(A)\bigr{)}$
$\displaystyle=\tfrac{n}{k}P_{n}(\widehat{\Gamma}_{A}^{M})-\mu(\mathcal{C}_{A}^{M})$
$\displaystyle\leqslant\tfrac{n}{k}P_{n}(\tfrac{n}{k}\Gamma_{A}^{M,+})-\mu(\Gamma_{A}^{M,-})$
$\displaystyle\leqslant\tfrac{n}{k}\lvert
P_{n}(\tfrac{n}{k}\Gamma_{A}^{M,+})-P(\tfrac{n}{k}\Gamma_{A}^{M,+})\rvert$
$\displaystyle\quad{}+\lvert\tfrac{n}{k}P(\tfrac{n}{k}\Gamma_{A}^{M,+})-\mu(\Gamma_{A}^{M,+})\rvert+\mu(\Gamma_{A}^{M,+}\setminus\Gamma_{A}^{M,-}).$

A lower bound for the estimation error can be derived in a similar way,
yielding, on $\mathcal{E}_{1}$,

$\displaystyle\lvert\widehat{\Phi}_{M}(A)-\Phi(A)\rvert$
$\displaystyle\leqslant\tfrac{M}{M-1}\max_{B\in\\{\Gamma_{A}^{M,+},\Gamma_{A}^{M,-}\\}}\tfrac{n}{k}\lvert
P_{n}(\tfrac{n}{k}B)-P(\tfrac{n}{k}B)\rvert$ (stochastic error)
$\displaystyle\quad{}+\tfrac{M}{M-1}\max_{B\in\\{\Gamma_{A}^{M,+},\Gamma_{A}^{M,-}\\}}\tfrac{n}{k}\lvert
P(\tfrac{n}{k}B)-\mu(B)\rvert$ (bias term)
$\displaystyle\quad{}+\tfrac{M}{M-1}\,\mu(\Gamma_{A}^{M,+}\setminus\Gamma_{A}^{M,-})$
(framing gap).

The bias term is the one stated in Theorem 3.2. Below, we treat the stochastic
error and the framing gap, and we show that the inclusions (57) hold on
$\mathcal{E}_{1}$.

#### Stochastic error

We apply Theorem A.1 to the collection

$\mathcal{F}^{M}=\left\\{\tfrac{n}{k}\Gamma_{A}^{M,\sigma}:\;\sigma\in\\{-,+\\},\;A\in\mathcal{A}\right\\}$

For every $A\in\mathcal{A}$, we have

$\tfrac{n}{k}\Gamma_{A}^{M,-}\subseteq\tfrac{n}{k}\Gamma_{A}^{M,+}\subseteq\left\\{x\in[0,\infty)^{d}:\lVert{x}\rVert\geqslant\tfrac{n}{k}\tfrac{1}{1+\Delta}\right\\}.$

Since the margins of $P$ are unit-Pareto, it follows that the probability $p$
appearing in Theorem A.1 applied to $\mathcal{F}^{M}$ is bounded by

$P\left[\textstyle{\bigcup_{j=1}^{d}}\left\\{x\in[0,\infty)^{d}:x_{j}\geqslant\tfrac{n}{k}\tfrac{1}{1+\Delta}\right\\}\right]\leqslant
d(1+\Delta)\tfrac{k}{n}.$

As a consequence, on an event $\mathcal{E}_{2}^{M}$ with probability at least
$1-d\delta/(d+1)$, we have

$\sup_{A\in\mathcal{A}}\max_{B\in\\{\Gamma_{A}^{M,+},\Gamma_{A}^{M,-}\\}}\tfrac{n}{k}\lvert
P_{n}(\tfrac{n}{k}B)-P(\tfrac{n}{k}B)\rvert\\\ \leqslant
C\left(\sqrt{d(1+\Delta)V_{M}k^{-1}\log((d+1)/\delta)}+k^{-1}\log((d+1)/\delta)\right)$

where $V_{M}$ is the VC-dimension of $\mathcal{F}^{M}$, which is the same as
the one of the collection in (29). Apart from the factor $\tfrac{M}{M-1}$, the
upper bound is equal to the second term on the right-hand side of (28). Since
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}^{M}$ have probabilities at least
$1-d\delta/(d+1)$ and $1-\delta/(d+1)$, respectively, the event
$\mathcal{E}_{1}\cap\mathcal{E}_{2}^{M}$ has probability at least $1-\delta$.

#### Framing gap

For $A\in\mathcal{A}$, any point $x\in\Gamma_{A}^{M,+}\setminus\Gamma_{A}^{M}$
has either a norm $\|{x}\|_{\infty}$ in between two certain bounds or an angle
$\theta(x)$ contained in a set of the form $A_{+}(\varepsilon)\setminus
A_{-}(\varepsilon)$ for some $\varepsilon>0$. Specifically,

$\displaystyle\mu\bigl{(}\Gamma_{A}^{M,+}\setminus\Gamma_{A}^{M,-}\bigr{)}$
$\displaystyle\leqslant\mu\left(\left\\{x:\left(1+\tfrac{1}{n}-\tfrac{1}{k}+\Delta\right)^{-1}\leqslant\lVert{x}\rVert\leqslant\left(1+\tfrac{1}{n}-\tfrac{1}{k}-\Delta\right)^{-1}\right\\}\right)$
$\displaystyle\quad{}+\mu\left(\left\\{x:\left((1+\tfrac{1}{n})\tfrac{1}{M}-\tfrac{1}{k}+\Delta\right)^{-1}\leqslant\lVert{x}\rVert\leqslant\left((1+\tfrac{1}{n})\tfrac{1}{M}-\tfrac{1}{k}-\Delta\right)_{+}^{-1}\right\\}\right)$
$\displaystyle\quad{}+\mu\left(\left\\{x:1\leqslant\lVert{x}\rVert\leqslant
M,\;\theta(x)\in A_{+}(3\Delta\lVert{x}\rVert)\setminus
A_{-}(3\Delta\lVert{x}\rVert)\right\\}\right).$

By homogeneity of $\mu$, both the first and second terms are bounded by
$2\Delta\Phi(\mathbb{S})\leqslant 2d\Delta$. For the third term, the product
representation (7) of $\mu$ in polar coordinates and the inequality (21) in
Assumption 1 yield the bound

$\displaystyle\int_{1}^{M}\Phi\bigl{(}A_{+}(3\Delta r)\setminus A_{-}(3\Delta
r)\bigr{)}\frac{\mathrm{d}r}{r^{2}}$
$\displaystyle\leqslant\int_{1}^{M}\Phi(\mathbb{S})\wedge(3c\Delta
r)\frac{\mathrm{d}r}{r^{2}}$
$\displaystyle\leqslant\int_{1}^{M}d\wedge(3c\Delta
r)\frac{\mathrm{d}r}{r^{2}}$
$\displaystyle=3c\Delta\log\bigl{(}M\wedge\tfrac{d}{3c\Delta}\bigr{)}+\bigl{(}3c\Delta-\tfrac{d}{M}\bigr{)}_{+},$

since for $a\in(0,b]$ we have

$\int_{1}^{M}b\wedge(ar)\frac{\mathrm{d}r}{r^{2}}=a\log\bigl{(}M\wedge\tfrac{b}{a}\bigr{)}+\bigl{(}a-\tfrac{b}{M}\bigr{)}_{+}$

and since $3c\Delta\leqslant 1\leqslant\Phi(\mathbb{S})$ by assumption.

Summing the contributions, we get an upper bound on
$\mu\bigl{(}\Gamma_{A}^{M,+}\setminus\Gamma_{A}^{M,-}\bigr{)}$ that does not
depend on $A\in\mathcal{A}$. Up to a factor $M/(M-1)$, we obtain the last term
on the right-hand side of (28).

#### The inclusions (57) hold on event $\mathcal{E}_{1}$

The event $\mathcal{E}_{1}$ was constructed in the course of the proof of
Theorem 3.1. On that event, the inequalities (50) and (51) hold.

_Step 1: Restriction to $(\tfrac{n}{k}\rho,\infty)^{d}$._ — By exactly the
same reasoning as in the proof of Theorem 3.1, we conclude that, on
$\mathcal{E}_{1}$, the set $\widehat{\Gamma}_{A}^{M}$ in (B) satisfies

$\widehat{\Gamma}_{A}^{M}=\left\\{x\in(\tfrac{n}{k}\rho,\infty)^{d}:\
\tfrac{n}{k}\leqslant\lVert{\hat{v}(x)}\rVert<\tfrac{n}{k}M,\;\theta(\hat{v}(x))\in
A\right\\}.$ (58)

_Step 2: Radial framing._ — On $\mathcal{E}_{1}$, apart from (53) and (54), we
also have

$\forall
x\in[0,\infty)^{d},\qquad\lVert{x}\rVert\geqslant\frac{n}{k}\frac{1}{((1+\frac{1}{n})\frac{1}{M}-\frac{1}{k}-\Delta)_{+}}\implies\lVert{\hat{v}(x)}\rVert\geqslant\frac{n}{k}M$
(59)

[if $(1+\frac{1}{n})\frac{1}{M}-\frac{1}{k}-\Delta\leqslant 0$, then the
condition is void] as well as

$\forall
x\in[\tfrac{n}{k}\rho,\infty)^{d},\qquad\lVert{\hat{v}(x)}\rVert\geqslant\frac{n}{k}M\implies\lVert{x}\rVert\geqslant\frac{n}{k}\frac{1}{(1+\frac{1}{n})\tfrac{1}{M}-\frac{1}{k}+\Delta}.$
(60)

Indeed, for such $x$ as in (59), if
$(1+\frac{1}{n})\frac{1}{M}-\frac{1}{k}-\Delta>0$, then there exists
$j=1,\ldots,d$ such that
$x_{j}\geqslant\tfrac{n}{k}\tfrac{1}{(1+1/n)/M-1/k-\Delta}$ and thus, on
$\mathcal{E}_{1}$, by (50)

$\displaystyle\hat{v}_{j}(x_{j})$
$\displaystyle\geqslant\hat{v}_{j}\bigl{(}\tfrac{n}{k}\tfrac{1}{(1+1/n)/M-1/k-\Delta}\bigr{)}$
$\displaystyle\geqslant\frac{n+1}{n\frac{k}{n}((1+\frac{1}{n})\frac{1}{M}-\frac{1}{k}-\Delta)+k\Delta+1}=\frac{n}{k}M.$

Similarly, for $x$ as in (60), we have by (50) also

$\frac{n+1}{(nx_{j}^{-1}-k\Delta)_{+}+1}\geqslant\frac{n}{k}M,$

which, after some algebra, can be shown to imply

$x_{j}\geqslant\frac{n}{k}\frac{1}{(1+\tfrac{1}{n})\frac{1}{M}-\tfrac{1}{k}+\Delta}.$

In view of (58) together with the inequalities in this step, we get that, for
$\widehat{\Gamma}_{A}^{M}$ in (58),

$\displaystyle\left\\{x\in(\tfrac{n}{k}\rho,\infty)^{d}:\
\frac{n}{k}\frac{1}{1+\frac{1}{n}-\frac{1}{k}-\Delta}\leqslant\lVert{x}\rVert<\frac{n}{k}\frac{1}{(1+\frac{1}{n})\tfrac{1}{M}-\frac{1}{k}+\Delta},\;\theta(\hat{v}(x))\in
A\right\\},$ (61) $\displaystyle\subseteq\widehat{\Gamma}_{A}^{M}$
$\displaystyle\subseteq\left\\{x\in(\tfrac{n}{k}\rho,\infty)^{d}:\
\frac{n}{k}\frac{1}{1+\frac{1}{n}-\frac{1}{k}+\Delta}\leqslant\lVert{x}\rVert<\frac{n}{k}\frac{1}{((1+\frac{1}{n})\tfrac{1}{M}-\frac{1}{k}-\Delta)_{+}},\;\theta(\hat{v}(x))\in
A\right\\}.$

_Step 3: Angular framing._ — Again, this step does not involve $M$. The
implications (56) hold. In combination with (61), we conclude that on
$\mathcal{E}_{1}$, the inclusions (57) hold. The proof of Theorem 3.2 is
complete. ∎

##  Appendix C Classification in extreme regions: Proofs

In the proofs, we find it sometimes convenient to take explicit note of the
map $T:\mathbb{R}^{d}\to[0,\infty)^{d}$ (typically, $T=v$ or $T=\hat{v}$) used
to transform the marginal distributions of the predictor variable. In line
with the theoretical and empirical classification risks $L_{t}(g)$ and
$\widehat{L}_{t}(g)$ in (36) and (38) in the paper, define

$\displaystyle L_{t}(g,T)$
$\displaystyle=t\,\operatorname{\mathbb{P}}[{g(T(X))\neq
Y,\,\lVert{T(X)}\rVert\geqslant t}],$ $\displaystyle\widehat{L}^{\tau}(g,T)$
$\displaystyle=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{g(T(X_{i}))\neq
Y_{i},\,\theta(T(X_{i}))\in\mathbb{S}_{\tau},\,\lVert{T(X_{i})}\rVert\geqslant
n/k\\}.$

Then $L_{t}(g)$ in (36) corresponds to $L_{t}(g,v)$ here and
$\widehat{L}^{\tau}(g)$ in (38) to $\widehat{L}^{\tau}(g,\hat{v})$.

###### Proof of Lemma 4.1.

We prove only the first statement. The proof of the second one follows the
same lines and is left to the reader. The third statement is obtained by
adding up the left and right hand sides of the first two identities. Decompose
$L_{t}^{>\tau}$ into a type-I and a type-II risk:
$L_{t}^{>\tau}(g,T)=L_{t,+}^{>\tau}(g,T)+L_{t,-}^{>\tau}(g,T)$ with

$L_{t,\sigma}^{>\tau}(g,T)=t\operatorname{\mathbb{P}}[{g(T(X))\neq
Y,\,Y=\sigma
1,\,\theta(T(X))\in\mathbb{S}_{\tau},\,\lVert{T(X)}\rVert\geqslant
t}],\qquad\sigma\in\\{-,+\\}.$

Consider the cones generated by regions
$\mathbb{S}^{\pm}_{g}=\\{x\in\mathbb{S}:g(x)=\sigma 1\\}$, that is,
$R_{g}^{\sigma}=\\{tx:\ x\in\mathbb{S}_{g}^{\sigma},\,t\geqslant 1\\}$ for
$\sigma\in\\{-,+\\}$. Equipped with this notation we may write

$\displaystyle L_{t,+}^{>\tau}(g,T)$
$\displaystyle=t\operatorname{\mathbb{P}}[{T(X)\in
R_{g}^{-},\,Y=+1,\,\theta(T(X))\in\mathbb{S}_{\tau},\,\lVert{T(X)}\rVert\geqslant
t}],$ $\displaystyle L_{t,-}^{>\tau}(g,T)$
$\displaystyle=t\operatorname{\mathbb{P}}[{T(X)\in
R_{g}^{+},\,Y=-1,\,\theta(T(X))\in\mathbb{S}_{\tau},\,\lVert{T(X)}\rVert\geqslant
t}].$

Setting the standardization function $T$ to $v$ yields $T(X)=V$ and thus

$\displaystyle L_{t,+}^{>\tau}(g,v)$
$\displaystyle=t\operatorname{\mathbb{P}}[{V\in
R_{g}^{-},\,\theta(T(X))\in\mathbb{S}_{\tau},\,\lVert{V}\rVert\geqslant
t,\,Y=+1}]$
$\displaystyle=pt\operatorname{\mathbb{P}}[{\theta(V)\in\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau},\,\lVert{V}\rVert\geqslant
t\mid Y=+1}]$ $\displaystyle\to
p\Phi^{+}(\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau}),\qquad t\to\infty,$

where the last convergence occurs because of Assumption 3 and the fact that
$\Phi^{+}$ is dominated by $\Phi$, so that
$\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau}$ is a $\Phi^{+}$-continuity set.
Proceeding similarly with $L_{t,-}^{>\tau}(g,v)$, the result follows. ∎

The next result parallels Lemma 4.1 by relating the empirical risk with the
empirical angular measure of the positive and negative classes. Consider the
type-I and type-II empirical errors,

$\widehat{L}_{\sigma}^{\tau}(g,T)=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{g(T(X_{i}))\neq
Y_{i},\,Y_{i}=\sigma
1,\,\theta(T(X_{i}))\in\mathbb{S}_{\tau},\,\lVert{T(X_{i})}\rVert\geqslant
n/k\\}.$

for $\sigma\in\\{-,+\\}$. Setting $T=\hat{v}$ as in (11) yields
$T(X_{i})=\widehat{V}_{i}$ and thus

$\widehat{L}_{+}^{\tau}(g,\hat{{v}})=\frac{1}{k}\sum_{i=1}^{n}\mathbbm{1}\\{\theta(\widehat{V}_{i})\in\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau},\,Y_{i}=+1,\,\lVert{\widehat{V}_{i}}\rVert\geqslant
n/k\\}.$

Recall from (41) the empirical angular measures $\widehat{\Phi}_{\sigma}$ of
the positive and negative instances. A similar treatment of
$\widehat{L}_{-}^{\tau}(g,\hat{{v}})$ yields immediately:

######  Lemma C.1.

In the case where $T$ is the rank transformation $\hat{{v}}$,

$\displaystyle\widehat{L}_{+}^{\tau}(g,\hat{{v}})=\frac{k_{+}}{k}\hat{\Phi}_{+}(\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau})\,,\qquad\widehat{L}_{-}^{\tau}(g,\hat{{v}})=\frac{k_{-}}{k}\widehat{\Phi}_{-}(\mathbb{S}_{g}^{+}\cap\mathbb{S}_{\tau}).$

###### Proof of Theorem 4.2.

Recall from the proof of Lemma 4.1 the decomposition of $L_{\infty}^{>\tau}$
into type-I and type-II errors,
$L_{\infty}^{>\tau}=L_{\infty,+}^{>\tau}+L_{\infty,-}^{>\tau}$ with
$L_{\infty,+}^{>\tau}(g)=p\Phi^{+}(\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau})$
and
$L_{\infty,-}^{>\tau}(g)=(1-p)\Phi^{-}(\mathbb{S}_{g}^{+}\cap\mathbb{S}_{\tau})$.
Recall also the definitions for their empirical counterparts
$\widehat{L}_{\pm}^{\tau}$ in Lemma C.1. For $g\in\mathcal{G}$, the deviations
of the empirical risk may be bounded by the sum of the deviations of the two
error types,

$\displaystyle\left|\widehat{L}^{\tau}(g,\hat{v})-L_{\infty}^{>\tau}(g)\right|$
$\displaystyle=\left|\widehat{L}_{+}^{\tau}(g,\hat{v})-L_{\infty,+}^{>\tau}(g)+\widehat{L}_{-}^{\tau}(g,\hat{v})-L_{\infty,-}^{>\tau}(g)\right|$
$\displaystyle\leqslant\left|\widehat{L}_{+}^{\tau}(g,\hat{v})-{\cal
L}_{\infty,+}^{>\tau}(g)\right|+\left|\widehat{L}_{-}^{\tau}(g,\hat{v})-L_{\infty,-}^{>\tau}(g)\right|.$
(62)

Let us focus on the first term of the sum. From Lemmata 4.1 and C.1, recalling
that $k^{+}=kn^{+}/n$, we have

$|\widehat{L}_{+}^{\tau}(g,\hat{v})-L_{\infty,+}^{>\tau}(g)|\leqslant\bigg{|}\frac{k^{+}}{k}\hat{\Phi}^{+}(\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau})-p\Phi^{+}(\mathbb{S}_{g}^{-}\cap\mathbb{S}_{\tau})\bigg{|},$

which suggests extending the concentration results concerning the empirical
measure $\widehat{\Phi}$ to its conditional version
$\widehat{\Phi}^{+},\widehat{\Phi}^{-}$. To do so we shall work on the product
space $\mathbb{R}^{d}\times\\{-1,1\\}$. We first introduce some notation. Let
$Q$ be the joint distribution of the pair $(X,Y)$ on
$\mathbb{R}^{d}\times\\{-1,1\\}$ and let $Q_{n}$ denote its empirical version,
$Q_{n}~{}=~{}\frac{1}{n}\sum_{i\leqslant n}\delta_{(X_{i},Y_{i})}.$ As in
Section 3 we can and will assume that each margin $X_{j}$ is unit Pareto so
that $X=V$. The empirical measure of the rank-transformed data is

$\widehat{Q}_{n}=\frac{1}{n}\sum_{i\leqslant
n}\delta_{(\hat{V}_{i},Y_{i})}=Q_{n}\circ(\hat{{v}},\mathrm{id})^{-1}$

where $\mathrm{id}$ is the identity function mapping (on $\\{-1,1\\}$).

Define the limit measure on $E\times\\{-1,1\\}$: for $\sigma\in\\{-,+\\}$ and
Borel sets $B\subseteq E$, put

$\nu(B\times\\{\sigma 1\\})=\lim_{t\to\infty}t\operatorname{\mathbb{P}}[{V\in
tB,Y=\sigma 1}]=\operatorname{\mathbb{P}}[{Y=\sigma 1}]\mu^{\sigma}(B),$

which exists from the conditional regular variation assumption (33). Notice
that $\nu$ is homogeneous of order $-1$ w.r.t. the first component. With this
notation and the one borrowed from the proof of Theorem 3.1 (see (52) for the
definition of $\widehat{\Gamma}_{A}$), we have, for $A\subseteq\mathbb{S}$,

$\displaystyle\frac{k_{+}}{k}\widehat{\Phi}^{+}(A)$
$\displaystyle=\tfrac{n}{k}\widehat{Q}_{n}\left(\tfrac{n}{k}\mathcal{C}_{A}\times\\{+1\\}\right)$
$\displaystyle=\tfrac{n}{k}Q_{n}\left(\hat{{v}}^{-1}(\tfrac{n}{k}\mathcal{C}_{A})\times\\{+1\\}\right)$
$\displaystyle=\tfrac{n}{k}Q_{n}(\widehat{\Gamma}_{A}\times\\{+1\\})$

and

$p\Phi_{+}(A)=\nu(\mathcal{C}_{A}\times\\{+1\\}).$

It is shown in the proof of Theorem 3.1 that under the assumptions of the
statement, there exists an event $\mathcal{E}_{1}$ of probability at least
$(1-d\delta/(d+1))$ on which
$\frac{n}{k}\Gamma_{A}^{-}\subseteq\widehat{\Gamma}_{A}\subseteq\frac{n}{k}\Gamma_{A}^{+}$,
see 46. In addition recall that

$\forall
A\in\mathcal{A},\qquad\Gamma_{A}^{-}\subseteq\mathcal{C}_{A}\subseteq\Gamma_{A}^{+}.$

Thus on the event $\mathcal{E}_{1}$, as in the proof of Theorem 3.1 we can
decompose the error as

$\displaystyle\frac{k^{+}}{k}\widehat{\Phi}_{+}(A)-p\Phi_{+}(A)$
$\displaystyle=\tfrac{n}{k}Q_{n}(\widehat{\Gamma}_{A}\times\\{+1\\})-\nu(\mathcal{C}_{A}\times\\{+1\\})$
$\displaystyle\leqslant\tfrac{n}{k}Q_{n}(\tfrac{n}{k}\Gamma_{A}^{+}\times\\{+1\\})-\nu(\Gamma_{A}^{-}\times\\{+1\\})$
$\displaystyle\leqslant\tfrac{n}{k}\left|Q_{n}(\tfrac{n}{k}\Gamma_{A}^{+}\times\\{+1\\})-Q(\tfrac{n}{k}\Gamma_{A}^{+}\times\\{+1\\})\right|$
$\displaystyle\qquad+\left|\tfrac{n}{k}Q(\tfrac{n}{k}\Gamma_{A}^{+}\times\\{+1\\})-\nu(\Gamma_{A}^{+}\times\\{+1\\})\right|$
$\displaystyle\qquad+\nu\left((\Gamma_{A}^{+}\setminus\Gamma_{A}^{-})\times\\{+1\\}\right).$

A lower bound for the estimation error can be derived in a similar way,
yielding, on $\mathcal{E}_{1}$,

$\displaystyle\left\lvert\frac{k_{+}}{k}\widehat{\Phi}_{+}(A)-p\Phi_{+}(A)\right\rvert$
$\displaystyle\leqslant\max_{B\in\\{\Gamma_{A}^{+},\Gamma_{A}^{-}\\}}\tfrac{n}{k}\left|Q_{n}(\tfrac{n}{k}B\times\\{+1\\})-Q(\tfrac{n}{k}B\times\\{+1\\})\right|$
(stochastic error II)
$\displaystyle\quad{}+\max_{B\in\\{\Gamma_{A}^{+},\Gamma_{A}^{-}\\}}\tfrac{n}{k}\left|Q(\tfrac{n}{k}B\times\\{+1\\})-\nu(B\times\\{+1\\})\right|$
(bias term -II)
$\displaystyle\quad{}+\nu\left((\Gamma_{A}^{+}\setminus\Gamma_{A}^{-})\times\\{+1\\}\right)$
(framing gap II).

We treat the three terms separately, following closely the proof of Theorem
3.1.

#### Stochastic error II

Since by construction $Q(B\times\\{+1\\})\leqslant P(B)$ the $Q$\- probability
of the class $\mathcal{F}^{\prime}=\mathcal{F}\times\\{+1\\}$ (with
$\mathcal{F}$ defined in (47)) is less than $d(1+\Delta)\tfrac{k}{n}$. The
class $\mathcal{F}^{\prime}$ has same VC-dimension $V_{\mathcal{F}}$ as
$\mathcal{F}$. Thus on an event $\mathcal{E}_{2}^{+}$ of probability
$1-\delta/(d+1)$ we again have

$\sup_{A\in\mathcal{A}}\max_{B\in\\{\Gamma_{A}^{+},\Gamma_{A}^{-}\\}}\tfrac{n}{k}\left|Q_{n}(\tfrac{n}{k}B\times\\{+1\\})-Q(\tfrac{n}{k}B\times\\{+1\\})\right|\\\
\leqslant
C\left(\sqrt{d(1+\Delta)V_{\mathcal{F}}k^{-1}\log((d+1)/\delta)}+k^{-1}\log((d+1)/\delta)\right),$

which is the term labelled ‘$\operatorname{error}$’ in the statement.

#### Bias term-II

Taking the supremum over $A\in\mathcal{A}$ immediately yields the bias term in
the statement of Theorem 4.2.

#### Framing gap-II