# Imbalanced classification

## 1) Introduction

When imbalanced classification data is obseverved, standard empirical risk minimization often lead to trivial classification rules for which the majority class is always predicted. Even if this might show good generalization (over imbalanced distribution), this is not satisfactory because the error within the minority class is too large. In many application, e.g., medical diagnosis or anomaly detection for aircraft engines, this is typically what should be avoided simply because one cares too much about being correct when predicting a default.

One way arround this problem consists in changing the underlying risk measure in order to give more importance to the minority class. This is done simply by re-weighting the observations from the majority and minority class so that both have the same magnitude in the new risk measure, that will be called the balanced risk.

The previous approach has been successfully used in many research works (AM risk). *Provide litterature review.*

In this paper, we focus on the case where the minority class is given a very low frequency compared to the majority class. By adopting this imbalanced framework, the first aim is to characterize (comparing the order of magnitude between the two classes) the breaking point for learning: from which frequency of observing the minority class learning can still be achieved?

To answer the previous question, we derive a non-asymptotic concentration inequality that can be applied to bound the excess risk. The bound that is derived becomes small as soon as the number of examples in the minority class goes to infinity. If the proportion of points in the minority class is $p$ and the data size is $n$, then one must only check that $pn$ is large enough. This show (and this is stated as a corollary of the previous bound) that learning is still possible even when $p$ goes to $0$ (only it should not be too small compared to the data size).

A second question which is raised in the paper is whether the asymptotic distribution is affected by the proportion of data in the minority class. This is of prime interest as the limiting distribution will be the basis of any inference procedure.

To answer that second question, and under the light of the first result (the concentration inequality mentioned just before), we consider an asymptotic regime where the frequency $p$ of the minority class goes to $0$ with $n$ but such that $pn \to \infty$. We show that the conditional empirical process has an asymptotic rate of convergence that actually depends on $pn$ (rather than on $n$). This supports the use of a particular approach to make inference in case of imballanced data.

Each of the two above results (concentration inequality and weak convergence) will be key in developping and providing garantees for two different practical procedures. First we introduce the $k$-NN classifier associated to the balanced risk and we show that it is Bayes-consistent. Second we apply the weak convergence result within a logistic regression framework to derive significance tests for the coefficients. Interestingly, the test region are rather different from the standard ones supporting that the framework of imballanced classification is rather different from the standard one and we should develop further tools.

The paper goes as follows. Some mathematical background about imbalanced classification is given in Section 2. In Section 3, we state our $2$ key results (non-asymptotic bound and concentration inequality). Section 4 is dedicated to the nearest-neigbour approach while section 5 is concerned with logistic regresion. All proofs of the mathematical statements are in the Appendix.

## 2) Background on the balanced risk

### 2.1 Classification framework

Consider the standard binary classification problem where some covariates $X$, random variables on $\mathcal X$, are used to decide between the two events $Y\in A$ and $Y \in B$ where $B = A^c$ and $Y$ is another random variable valued in $\mathcal Y$. The underlying probability measure on $\mathcal X\times \mathcal Y$ associated to $(X,Y)$ is denoted by $P$ and the associated expectation is $E$.

The Bayes classifier is denoted $g^*$ and is defined as the minimum-argument of the so-called Bayes-risk given by $R^* (g) = E [ \mathbb I _{Y\neq g(X)}]$. The Bayes classifier $g^*$ predicts $B$ whenever $\eta^*(X) = P (Y \in B|X )\geq 1/2$ and predicts $A$ otherwise.

A standard (practical) approach is to consider - not necessarily minimizing an estimate of the Bayes risk - but rather minimizing another risk estimate associated to a loss function $\ell_g : \mathcal X\times \mathcal Y \to \mathbb R_{\geq 0}$ with respect to some score $g$ over a given class of score functions $\mathcal G$. The associated risk takes the following form
$$ R(g) = E [  \ell_g (X,Y) ] $$
and the question is to know wether the estimated classifier achieves a similar risk as the best function in $\mathcal G$.

Usually the function $\ell _g$ has the following form $\ell_g(X,Y)=\phi(g(X)s(Y))$ where $s(Y)=(\mathbb{I}_B-\mathbb{I}_A)(Y)$ and $\phi$ is convex and differentiable such that $\phi' (0)<0$. This ensures that the loss is classification calibrated and several consistency results (ensuring that the minimizer over all functions of $R$ agrees with the Bayes classifier) can be found in Bartlett (2006). Examples include logistic, exponential, squared and hinge loss (in which case the minimization is taken over score functions rather than classifier).

.
### 2.2 Definition of the balanced risk

As for the previous section, we introduce the balanced Bayes risk given by
$$ R_{\text{bal}}^*(g) = E [ \mathbb I_{Y\neq g(X)} |Y\in A ] + E [   \mathbb I_{Y\neq g(X)} |Y\in B ] .$$
The minimizer of the previous function, $g^*_{bal}$, is called the balanced Bayes classifier. It predicts $B$ whenever $\eta^*(X) \geq P (Y\in B)$ and gives $A$ otherwise (Theorem 2 in Oluwasanmi or Proposition 2 in the present paper).

More generally, the balanced risk associated to any loss function $\ell_g$ is defined as, for all $g\in \mathcal G$,
$$ R_{\text{bal}}(g) = E [ \ell_g(X,Y) |Y\in A ] + E [  \ell_g(X,Y) |Y\in B ] , $$
where for any random variable $Z$ and event $C$ with nonzero probability, $P(C) E [ Z | C ] = E [ Z \mathbb I_ C (Y) ]$.

### 2.3 Estimation
In what follows, we shall use notation from empirical process theory. That is if $\mu$ is a measure on $\mathcal X\times \mathcal Y$ and $f$ is a real function defined on $\mathcal X\times \mathcal Y$, we note $\mu(f) = \int f d\mu$. When $f = \mathbb I _C$ for a measurable set $C$ we write $\mu (f ) = \mu (\mathbb I _C) = \mu(C)$ indiferently.

Suppose that $(X_i,Y_i)_{1\leq i\leq n}$ is a collection of random variables with common distribution $P$. Define, for all measurable and real valued function $f$ defined on $\mathcal X \times \mathcal Y$,
$$ P_n (f) = n^{-1} \sum_{i=1} ^ n f(X_i,Y_i) . $$
The latter measure, $P_n$, is called the empirical measure. While the standard risk estimate simply writes as $P_n(\ell_g)$, for any $g\in \mathcal G$, the balanced risk needs to be modified in order to take into account the presence of conditionning probabilities. Introduce the empirical conditional measure, for any $C\subset \mathcal Y$,
$$ P_n (f | C) = \frac{ P_n (f \mathbb I_C)}{ P_n (\mathbb I_C) },$$
with the convention that $P_n(f|C) = 0$ whenever $P_n (\mathbb I_C) = 0$. Actually, any set $C \subset \mathcal Y$ defines a conditional measure denoted $P(\cdot|C)$ given by
$$P(f|C) = \frac{P ( f \mathbb I_C )}{ P(\mathbb I_C)} ,$$
with the same convention that $P(f|C) = 0$ whenever $P(C) = 0$. Note that the ballanced risk can be expressed, using the notation from above, as
$$R_{\text{bal}}(g) = P( \ell_g | A ) + P (  \ell_g | B )$$
Consequently, we can define the balanced emprirical risk as
$$R_{n,\text{bal}}(g) = P_n( \ell_g | A ) + P_n (  \ell_g | B ).$$

## 3) Concentration bound and weak convergence for the balanced empirical process

Motivated by the application to learning from imbalanced dataset we now provide two results on the balanced emprical process $\{P_n(f|C) \,:\, f\in \mathcal F\}$ where $\mathcal F$ is a class of function $\mathcal F$ defined on $S = \mathcal X\times \mathcal Y$.

### 3.1 Concentration bound

The fisrt result is a concentration inequality valid uniformly over $f$ and for all value of $n$. An important point is that the size of $P(C)$ is taken into account in the analysis and the value of $P(C)$ will take an important place in the obtained bound.

We require the follwoing standard assumption.

**A1** The family of functions $\mathcal F$ is bounded by $U$ and of VC-type with parameter $(v,A)$, i.e., for any $0 < \epsilon < 1$ and any probability measure $Q$ on $(S, \mathcal S)$, we have
\begin{equation}
\mathcal N \left(\mathcal G, L_2(Q) , \epsilon \| G \| _ {L_2(Q) } \right) \le (A/\epsilon)^{v}.
\end{equation}

The concept of VC class previously introduced is standard (*give some reference*). A classic example is the class of cells $\mathbb I_{\{\cdot\leq y \}}$, $y\in \mathbb R$, which is VC with parameter $v = 2$ and $A =1$.

**Theorem 1**
Suppose that A1 is fullfilled. For any $n$ and $\delta$ such that
$$ n P(C) \geq
\max\left[\frac{U^2}{\sigma^2} v \log\left(K' A / \left(2 \delta\sqrt{P(C)} \right) \right), 8log(1/\delta)\right] $$

we have with probability $1-\delta$,
$$ \sup_{f\in \mathcal F} | P_n (f|C) - P(f |C)| \leq 4K' \sigma (C) \sqrt{\frac{ v }{nP(C)} \log(K' A / (2 \delta \sqrt { P (C) } ) ) } $$
with $\sigma^2(C) =\sup_{f\in \mathcal F} var(f|C)\leq 4U^2$.

*Proof.* Starting with
\begin{equation}
P_n(f|C) - P(f|C) = \frac{P_n ( (f - P(f|C)) \mathbb I_C) } {P_n (\mathbb I _C)}
\end{equation}
we focus on each term, denominator and numerator, separetely. For the numerator we show that, with probability $1-\delta$,
$$ P_n ( (f - P(f|C)) \mathbb I_C) \leq K' 2 \sqrt{ \frac{ v \sigma^2(C)P(\mathbb I_C)}{n} \log(K' A / (2 \delta \sqrt { P\mathbb I_C } ) ) } $$
The term $(f - P(f|C)) \mathbb I_C$ has mean $0$ and the class $ f - P(f|C) $ is still bounded by $2U$ and is still VC with VC parameter $(v,A)$ (add a Lemma). As a consequence, we can use Proposition 2 in Plessier, Portier, Segers (Theorem 2 in Appendix). The variance is bounded as follows
$$var((f - P(f|C)) \mathbb I_C )\leq E[(f - P(f|C))^2 \mathbb I_C ] = var(f|C) P(C)\leq \sigma^2(C) P(C),$$
by definition of $\sigma^2(C)$. As a consequence we obtain using the result in the Appendix that
\begin{align*}
&P_n ( (f - P(f|C)) \mathbb I_C) \leq \\
&K' \left( \sigma \sqrt{\frac{ v P(\mathbb I_C)}{n} \log(K' A / (2 \delta \sqrt { P\mathbb I_C } ) ) } + \frac{U v}{n} \log(K' A / (2 \delta \sqrt { P\mathbb I_C } ) ) \right)
\end{align*}
Now it remains to see that the second term (in the right hand side) is smaller than the first term (using the stated condition on $n$ and $\delta$).

For the denominator, using Theorem 1 in the Appendix we have that, with probability $1-\delta$,
$$ P_n(\mathbb I _C ) / P(\mathbb I_C ) \geq (1-\sqrt{\frac{2\log(1/\delta)}{nP(\mathbb I_C)}}) $$

so that with union boud, we get, with probability $1-2\delta$,
\begin{align}
&\frac{P_n ( (f - P(f|C)) \mathbb I_C)}{P_n(\mathbb I_C)} \\
&\leq \frac{K'}{P(\mathbb I_C)-\sqrt{\frac{2\log(1/\delta)P(\mathbb I_C)}{n}}} \left( 2\sigma \sqrt{\frac{ v P(\mathbb I_C)}{n} \log(K' A / (2 \delta \sqrt { P\mathbb I_C } ) ) } \right)
\end{align}
Finally, by the stated condition on $n$ and $\delta$ we have
$$P(\mathbb I_C)-\sqrt{\frac{2\log(1/\delta)P(\mathbb I_C)}{n}} \geq \frac{P(\mathbb I_C)}{2},$$

and the proof is complete.

### 3.1 Weak convergence

For the asymptotic analysis we focus on a particular setup where $ P(C)$ goes to $0$ while $n\to \infty$. This is particularly relevant to deal with imbalanced data set for which one of the classes is less represented than the other.

To this aim we need a particular asymptotic framework in which for each $n\geq 1$, $(X_i,Y_i)_{i=1,\ldots, n}$ is a collection of random variable with common distribution. This distribution is allowed to change with $n$ such that $P( C) \to 0$ but not too fast because $n P(C)\to \infty$.

**Theorem 2**
Suppose that $\mathcal F$ is Donsker, then
$$ \sqrt { n P( C) } (P_n(f|C ) - P(f|C ) ) \leadsto \mathbb G(f),$$
where $G(f)$ is a Gaussian process with covariance function $cov(f_1,f_2| C)$.

Proof.
As a first step, we use the same decomposition as in the proof of Theorem 1 in order to work with a simple emprirical process.

Again, using Lemma 5.1 in Portier 2021 (Theorem 1 in Appendix) yields, with probability $1-\delta$

$$ P_n(\mathbb I _C ) / P(\mathbb I_C ) \leq (1+\sqrt{\frac{3\log(1/\delta)}{nP(\mathbb I_C)}}).$$

Combined with the previous lower bound, this ensures in particular that $P_n(\mathbb I _C ) / P(\mathbb I_C ) \xrightarrow[]{P} 1$ where $\xrightarrow[]{P}$ denotes convergence in probability.

Invoking Slutsky's Lemma it remains to show that
$$ \sqrt { \frac{n}{P(\mathbb I _C)} } (P_n( (f - P(f|C )) \mathbb I _C ) \leadsto \mathbb G(f)$$
This is a typical empirical process with class of function changing with $n$. This kind of process is analysied in Chapter 2.11.3 in Van der Vaart and Wellner (Empirical process).

## 4) Application

### 4.1 Application of the concentration bound

There is two interesting applications of Theorem 1. The first one is about learning from ERM based on VC class of function (is a bit simple). The second one is about the $k$-NN classification and is perhaps more interesting as it uses the full strenght of or bound in that it takes advantage of the variance term $\sigma(C)$.

#### 4.1.1 ERM with balanced losses.

In this section we consider the ERM algorithm $\hat g$ associated to the balanced loss :
$$\hat g =\arg\min_{g \in \mathcal{G}}R_{n,bal}(g).$$

In the next proposition we derive a probability upper bound for the excess risk of $\hat g$.
**Proposition**
Suppose that $\{\ell_g\, :\, g\in \mathcal G\}$ is VC and $L$-bounded. we have, with probability $1-\delta$,
$$R(\hat g ) \leq R_{\mathcal G} +8K' \sigma_{max} \sqrt{\frac{ v \log(K' A / (2 \delta \sqrt { P_{min}} ) ) }{nP_{min}}}. $$

Where $\sigma_{max}=\max\left(\sigma(B),\sigma(A)\right)$, $P_{min}=\min\left(P(A),P(B)\right)$ and $K'>0$ is a universal constant.
*Proof*

First, using the definition of $\hat g$ yields
$$R_{n,bal}(\hat g)-R_{n,bal}(g^*_{bal})\leq 0,$$

So that,

\begin{align}
R_{bal}(\hat g ) - R(g^*_{bal})&\leq R_{bal}(\hat g )-R_{n,bal}(\hat g ) - \left(R_{bal}(g^*_{bal})-R_{n,bal}( g^{*}_{bal} )\right)\\
&\leq \sup_{g\in \mathcal{G}}\lvert R_{bal}(g)-R_{n,bal}( g)\rvert\\
& \leq \sup_{g\in \mathcal G} | P_n (g|B) - P(g |B)|+ \sup_{g\in \mathcal G} | P_n (g|A) - P(g |A)|.
\end{align}
It remains to use Theorem 1 and the proof is complete.

#### 4.1.2 Balanced kNN

In this section aim is to introduce the balanced $k$-NN classifier, which is a modified version of the standard $k$-NN classifier for minimizing the balanced risk (instead of the Bayes risk). The aim is to establish the consistency of the balanced $k$-NN classifier with respect to the balanced risk $R_{bal} ^* (g)$ defined in Section 2.2.

To do so, let $x\in \mathbb R^d$ and $nn(x)$ be the set of index $i$ such that $X_i$ is a $k$-NN of $x$. Define the balanced $k$-NN classifier

$$\hat \nu _ k (x) = \frac{\hat \eta(x)}{P_n(B)},$$

where $\hat \eta(x)= \frac{\sum_{i\in nn(x)} \mathbb I_{ Y_i \in B }}{k}$ denotes the standard k-nn estimate of $\eta(x)$. The $k$-NN balanced classifier is defined as follows. For any $x\in \mathcal X$, it returns $B$ whenever $\hat \nu_k\geq 1$ and $A$ otherwise. Now define the quantity
$$ \nu^* (x) =\frac{ \eta^*(x)}{ P(B) }.$$
In the next proposition we generalize Theorem 17.1 from Biau Devroye (2015) to the balanced $k$-NN classifiers.

**Proposition** For any classifier $g(x)$ that predicts $B$ whenever $\nu(x)\geq 1$ for some real valued measurable function $\nu$, we have
$$R_{bal} ^* (g) - R_{bal} ^* (g^*) =E[\mathbb I_{ g(X) \neq g^*(X)}\frac{\lvert \eta^*(X) -p \rvert}{p(1-p)}],$$
with $p=P(Y\in B)$ and $g^*$ is the balanced Bayes classifier (introduced in 2.2) i.e the classifier that predicts B whenere $\nu^* \geq 1$. Furthermore, whenever $p<1/2$ we have

$$ R_{bal} ^* (g) - R_{bal} ^* (g^*) \leq 2 E [ | \nu(X) - \nu^*(X)|]$$

*Proof*
The balanced risk write as
\begin{align*}
R_{bal} ^* (g)&=P(\nu(X)< 1 \mid Y\in B)+ P(\nu(X)\geq 1 \mid Y\in A)\\
& = E[\frac{\mathbb I_{(\nu(X)< 1)} \mathbb I_{Y\in B}}{p}+ \frac{\mathbb I_{(\nu(X)\geq 1)} \mathbb I_{Y\in A}}{1-p}].
\end{align*}
In addition, using a conditioning argument yields,
$$R_{bal} ^* (g) = E[\frac{\mathbb I_{(\nu(X)< 1)} \eta^*(X)}{p}+ \frac{\mathbb I_{(\nu(X)\geq 1)} (1-\eta^*(X))}{1-p}].$$

Similarly we have
$$R_{bal} ^* (g^*) = E[\frac{\mathbb I_{(\nu^*(X)< 1)} \eta^*(X)}{p}+ \frac{\mathbb I_{(\nu^*(X)\geq 1)} (1-\eta^*(X))}{1-p}].$$
It follows that
\begin{align}
R_{bal} ^* (g) - R_{bal} ^* (g^*) &=E[\mathbb I_{sign( \nu^*(X)-1)\neq sign(\nu(X)-1)}\frac{\lvert \eta^*(X) -p \rvert}{p(1-p)}]\\
(\nu^*=\eta^*/p)&=E[\mathbb I_{g^*(X)\neq g(X)}\frac{\lvert \nu^*(X) -1 \rvert}{(1-p)}].
\end{align}
Which concludes the first part. For the second part, it remains to notice that
$$sign( \nu(X)-1)\neq sign(\nu^*(X)-1) \implies \lvert \nu^*(X) -1 \rvert \leq \lvert \nu(X)- \nu^*(X)\rvert, $$
so that,

\begin{align}
R_{bal} ^* (g) - R_{bal} ^* (g^*) &\leq \frac{E[\lvert\nu^*(X)- \nu(X)\rvert]}{1-p}\\
(p \leq 1/2) & \leq 2E[\lvert\nu(X)- \nu^*(X)\rvert].
\end{align}

Now everything is ready to show the consistency of the balanced $k$-NN with respect to the AM risk.
**Corollary**
Let $\hat \nu_k$ denote the balanced $k$-NN classifier score. Suppose that $k$ is such as $kP(Y\in B)\to \infty$ and $k/n \to 0$, then the classifier $\hat g$ that predicts $B$ whenever $\hat \nu_k\geq 1$ is consistant with respect to the AM risk. Namely,

$$R^*_{bal}(\hat g_k) \xrightarrow[]{a.s} R^*_{bal}(g^*) ,$$

*Proof*

The result follows directly from the previous proposition and Proposition 1 from the Appendix.

### 4.2 Application of the weak convergence

The application we consider is the logistic case, when the loss function is given by
$$\{ \ell_\beta(x,y) = \log(1+ \exp(s(y) \beta^Tx)) : \beta \in \mathbb R^d\} .$$
Since the previous class is parametric, the entropy condition to apply Theorem 2 holds. We also suppose that the conditional distribution of $\mathbb I_A$ given $X$ is bernoulli with parameter $\exp(\beta_0^TX)/(1+\exp(\beta_0^TX))$ for a certain parameter $\beta_0$.

The next result is when $P(B) \to 0$.

**Proposition 1**
Under some smoothness conditions
$$\sqrt{nP(B)} ( \hat \beta - \beta ) \leadsto
\mathcal N( 0, V)$$
with $V = H^{-1} var( \nabla \ell_{\beta_0} |B)$ and
$$H = P (\nabla^2 \ell_{ \beta_0} | A) + P (\nabla^2 \ell_{ \beta_0} | B)$$.

*Proof.*
We further suppose that $\hat \beta \to \beta_0$ in probability (a result that shall be obtained). Under the stipulated assumptions one has
$$ P_n (\nabla \ell_{\hat \beta} | A) + P_n (\nabla \ell_{\hat \beta} | B) = 0$$
and
$$ P (\nabla \ell_{ \beta _0 } -\nabla \ell_{ \beta_0} | A) + P (\nabla \ell_{ \beta _0 } -\nabla \ell_{ \beta_0} | B) = 0$$
We have
$$ P_n (\nabla \ell_{\hat \beta} -\nabla \ell_{ \beta_0} | A) + P_n (\nabla \ell_{\hat \beta}-\nabla \ell_{ \beta_0} | B) = -P_n (\nabla \ell_{ \beta_0} | A) - P_n (\nabla \ell_{\beta_0} | B)$$
And hence
$$ P (\nabla \ell_{\hat \beta} -\nabla \ell_{ \beta_0} | A) + P (\nabla \ell_{\hat \beta}-\nabla \ell_{ \beta_0} | B) = -P_n (\nabla \ell_{ \beta_0} | A) - P_n (\nabla \ell_{\beta_0} | B) + \Delta_n$$
with
$$\Delta_n = (P_n - P) (\nabla \ell_{\hat \beta} -\nabla \ell_{ \beta_0} |A ) + (P_n - P) (\nabla \ell_{\hat \beta} -\nabla \ell_{ \beta_0} |B )$$
Invoking the weak convergence property in Theorem 2 we have that (to be done rigourously) $\Delta_n = o_p( 1/\sqrt{nP(A)} + 1 / \sqrt {nP(B)})$.

It follows using a Taylor development that
$$ (P (\nabla^2 \ell_{\tilde \beta} | A) + P (\nabla^2 \ell_{\tilde \beta} | B)) (\hat \beta - \beta_0) = -P_n (\nabla \ell_{ \beta_0} | A) - P_n (\nabla \ell_{\beta_0} | B) +\Delta_n $$
This implies that
$$ (H + o_P(1)) (\hat \beta - \beta_0) = -P_n (\nabla \ell_{ \beta_0} | A) - P_n (\nabla \ell_{\beta_0} | B) $$
Moreover using $\sqrt{n P(B) } \nabla \ell_{ \beta_0} | A) = O_{p} (\sqrt{P(B) / P(A)}) = o_p(1)$, it follows that
$$ (H + o_P(1)) \sqrt{n P(B) } (\hat \beta - \beta_0) = - \sqrt{n P(B) } P_n (\nabla \ell_{\beta_0} | B) + o_P(1)$$
from which we can deduce the result.

## Appendix

**Theorem 1**
Let $(Z_i)_{i\geq 1}$ be a sequence of i.i.d. random variables valued in $\{0,1\}$. Set $\mu = n \mathbb E [Z_1]$ and $S = \sum_{i=1} ^n Z_i$. For any $\delta \in (0,1)$ and all $n\geq 1$, we have with probability $1-\delta$:
\begin{align*}
S \geq \left(1- \sqrt{ \frac{2 \log(1/\delta) }{ \mu} } \right) \mu .
\end{align*}
In addition, for any $\delta \in (0,1)$ and $n\geq 1$, we have with probability $1-\delta$:
\begin{align*}
S \leq \left(1 + \sqrt{ \frac{3 \log(1/\delta) }{ \mu} } \right) \mu .
\end{align*}

**Theorem 2**

Let $(Z,Z_1,\ldots ,Z_n) $ be an independent and identically distributed ollection of random variables in $ (S,\mathcal S)$. Let $\mathcal G$ be a VC class of functions with parameters $v\geq 1$, $A\geq 1$ and uniform envelope $U\geq \sup_{g\in \mathcal G,\, x\in S} |g(x)|$. Let $\sigma$ be such that $\sigma^2 \geq \sup_{g\in \mathcal G} var(g(Z))$ and $\sigma \leq 2U$. For any $n\geq 1$ and $\delta\in (0,1)$, it holds, with probability $1-\delta$,
\begin{equation}
\sup_{g\in \mathcal G} \left| \sum_{i=1} ^n \{g (Z_i ) - \mathbb E [g(Z) ] \} \right| \\ \leq K' \left(\sigma \sqrt{v n \log( K' \theta/\delta)} + U v \log(K' \theta/\delta ) \right),
\end{equation}
with $\theta = A U / \sigma$ and $K'>0$ a universal constant.

## Result we can have from our bound in Th1

Remind that
$$\hat \nu _ k (x) = \frac{n}{k} \frac{ \sum_{i\in nn(x)} \mathbb I _ { Y_i \in B } }{ \sum_{i = 1}^n \mathbb I _ { Y_i \in B } }$$
and
$$ \nu^* (x) = \frac{ E [ \mathbb I _{Y\in B } | X=x ]}{ E [\mathbb I _ {Y\in B } ] }$$
We have the following result.

**Proposition 1**
Suppose that $x\mapsto P(B|x)$ is $L$-Lipschitz uniformly in $B$. Then we have the almost sure rate

$$\sup _{x\in \mathcal X} | \hat \nu_k (x) - \nu^*(x)| = O \left(\frac{1}{\sqrt{kP(B)}} + (\frac{k}{n})^{1/d} \right) . $$

*Remark.* The proof below unfortunately does not use fully the bound given in Theorem 1 due to the randomness of the class used in the NN algorithm. This is not a big problem because this is still the same kind of bound that we use.

*Proof*
Let us start with a few definition. The $k$-nn radius is denoted by $\hat \tau_k$. That is,
$i\in nn(x)$ is equivalent to $\|X_i - x\| \leq \tau_k$. As a consequence
$$ \sum_{i\in nn(x)} \mathbb I _ { Y_i \in B } =\sum_{i =1}^n \mathbb I _ { Y_i \in B } \mathbb I _ { \|X_i - x\|\leq \tau_k } $$
Moreover we have that $\tau_k \leq \tau_0 = 2 (\frac{k}{n f_X(x) V_d})^{1/d}$ occurs on an event $E$ with large probability. On this event
$$ g\in \mathcal G\{ \mathbb I _ { \|X - x\|\leq \tau } : \tau\leq \tau_0 \}$$
which is VC (ref by Dudley).

Write
$$ \hat \nu_k (x) -\nu^*(x) = \frac{ (1/k) \sum_{i =1}^n (\mathbb I _ { Y_i \in B } - P(B|X_i)) \mathbb I _ { \|X_i - x\|\leq \tau_k } }{ P_n ( \mathbb I _ { B } )} \\+ \frac{ (1/k) \sum_{i =1}^n ( P(B|X_i) - P(B|x)) \mathbb I _ { \|X_i - x\|\leq \tau_k } }{ P_n ( \mathbb I _ { B } )} + P(B|x) (\frac{1}{ P_n ( \mathbb I _ { B } )} - \frac{1}{ P( \mathbb I _ { B } )} ) $$
On the right event, the first term is smaller than
$$ P(\mathbb I_B)^{-1} \sup_{\tau\leq \tau_0} | (1/k) \sum_{i =1}^n (\mathbb I _ { Y_i \in B } - P(B|X_i)) \mathbb I _ { \|X_i - x\|\leq \tau }|$$
whose variance is $P(\mathbb I_B)^{-2} (1/k) P(\mathbb I_B) = 1/(kP(\mathbb I_B))$.

Using the assumption that $P (B |x) / P(B)$ is $L$-Lipschitz we get that (on the right event) the second term is smaller than
$$ L \tau .$$

The third term is smaller than
$$ (P(B|x) / P(B)) (\frac{P(B)}{ P_n ( \mathbb I _ { B } )} - 1 )$$
which is smaller (using again the Lipschitz assumption) than $C / \sqrt {nP(B) }$, negligible.

**Proposition 2**
The optimal classifier $g^*$ with respect to the AM measure is defined as follow,
$$g^*(x)=sign(\eta^*(x)-P(B)).$$
In other words
$$ g^{*} = \arg\min_{g\in \mathbb{R}^{\mathcal{X}}}R_{bal}^*(g).$$

**More details about classification calibrated functions**
We suppose that the loss function write as $\ell_g(X,Y)=\phi(g(X)s(Y))$ where $\phi$ is a convexe positive function and $s(Y)=(\mathbb{I}_A-\mathbb{I}_B)(Y)$. In this case

$$R(g)=E[C_{\eta^*(X)}(\phi(X))]$$

with $\eta^*(X)=P(Y=1\mid X=x)$ and

$$C_\eta(\alpha)=\eta\phi(\alpha)+(1-\eta)\phi(-\alpha),$$

For any $\eta>0$ and $\alpha\in \mathbb{R}$.
Now let's make the following assumption

Assumption (Calibrated loss) The $\phi: \mathbb{R} \rightarrow$ $[0,+\infty]$ is calibrated for the $0-1$ classification in other words:
$$
\left\{\begin{array}{ll}
\forall \nu>\frac{1}{2}, & \inf _{\alpha \leqslant 0} C_\eta(\alpha)>\inf _{\alpha \in \mathbb{\mathbb { R }}} C_\eta(\alpha) \\
\forall \nu<\frac{1}{2}, & \inf _{\alpha>0} C_\eta(\alpha)>\inf _{\alpha \in \mathbb{\mathbb { R }}} C_\eta(\alpha) .
\end{array}\right.
$$

** This is suffisient to ensure that the consistency in the following sense, if

$$ g^{best} \in \arg \min_{g\in \mathbb{R}^{\mathcal{X}}} R(g)$$
Then
$$\mathbb{I}(g^{best}(x)\geq 0) = \mathbb{I}(\eta(x)\geq 1/2). $$

**
** On peut remplacer cette condition par la proprité suivante
$\phi$ convexe et $\phi^{\prime}(0)<0$ cela garanties que $\phi$ est calibré. Cela aussi assure que $\phi$ est décroissante sur $[-\infty,0]$ **
** More details can be found in Bartlett 2006 ( Ou le cours d'Arlot Fondamentaux de l'apprentissage statistique page 67)