text:
\subsection{Proof of Lemma \ref{"train-test-cond"}}\label{"proof-train-test-cond"}
Since the leave-one-out is a special case of $K$-fold  with $K=n$ (or leave-$p$-out with $p=1$)
it suffices to prove the statement concerning  the cases of the leave-$p$-out and the $K$-fold .

\paragraph{$K$-Fold.} For this procedure, the sequence of masks is a
partition of $\llbracket 1, n\rrbracket $:
\begin{equation}\label{"loo-k-fold-prop"}
  \bigcup\limits_{j=1}^K V_j=\llbracket1,n\rrbracket
  \: and \:
  V_j\bigcap V_k=\varnothing\:, \:\forall j\neq k \in \llbracket1,K\rrbracket.
\end{equation}

Under the assumption that $K$ divides $n$, the condition
$card(V_j)= n/K :=n_{V}$ for all the validation sets $V_j$ holds, as
stipulated in~(\ref{"card-condition"}).  Thus we
have
\begin{equation}
  \label{"K-fold-equation"}
  n=\sum_{j=1}^{K}card(V_j)=Kn_{V}.
\end{equation}
Furthermore,\,under \eqref{"loo-k-fold-prop"},\,any  index
$l\in \llbracket 1,n \rrbracket$ belongs to a unique
validation test $V_{j'}$ and to all the train sets $T_j=V_j^c$
with $j\neq j'$. Hence, we both have
\begin{equation*}
  \begin{cases}
    \sum_{j=1}^{K}\un} %[1]{\mathbbm{1}\left\{#1\right\}{l \in T_j} = K-1, & \text{and}  \\
    \sum_{j=1}^{K}\un} %[1]{\mathbbm{1}\left\{#1\right\}{l \in V_j} = 1. &
  \end{cases}
\end{equation*}
Using \eqref{"K-fold-equation"} and the fact that $n_{T}=n-n_{V}=(K-1)n_{V}$ yields
the desired result.

\paragraph{Leave-$p$-out.}
In the leave-$p$-out procedure, the sequence of validation sets is the
family of all subsamples $V_j$ of $\data_n$ of size $card(V_j)=p$, thus
$K=\binom{n}{p}$. On the other hand, any index
$l\in \llbracket 1,n \rrbracket$ belongs to $\binom{n-1}{p-1}$
validation sets. Indeed constructing  a $V_j$ such as $l \in V_j$ is
equivalent to first picking $l$ and then choosing $p-1$ elements from
$\llbracket1,n\rrbracket \setminus \{l\}$.  Hence we have
	\begin{equation*}
	\sum_{j=1}^{K}\un} %[1]{\mathbbm{1}\left\{#1\right\}{l \in V_j} = \binom{n-1}{p-1} \: \, , \: \forall l \in \llbracket1,n\rrbracket.
	\end{equation*}
	Using the identity  $n\binom{n-1}{p-1}=p\binom{n}{p}$ we obtain
	\[\ffrac{1}{Kn_{V}}\sum_{j=1}^{K}\un} %[1]{\mathbbm{1}\left\{#1\right\}{l \in V_j}= \ffrac{1}{p\binom{n}{p}}\sum_{j=1}^{K}\un} %[1]{\mathbbm{1}\left\{#1\right\}{l \in V_j}= 1/n, \]
	A similar argument applies to the sequence $T_{1:K}$, which completes the proof.

\subsection{Proof of Lemma \ref{"RCV-supp"}}\label{"lemma-RCV-supp-proof"}
We introduce for convenience the rescaled variable $Z_\alpha = \alpha Z$ where $Z$ defined in~(\ref{def:Z-CV}) is the average of the supremum  deviations of the (pseudo)-empirical risk $\Tilde R_\alpha$, see~(\ref{def:tilde-rcv}),  over the validation sets $V_j$. Then $Z_\alpha$ may be written as
\[Z_\alpha=\alpha Z=\frac{1}{K}\sum_{j=1}^{K}\left[\ffrac{1}{n_{V}}\sup_{g\in \mathcal{G}}\Big|\sum_{i \in V_j}c(g,O_i)\mathbbm{1}_{\alpha}(X_i)-\EE\left[c(g,O)\mathbbm{1}_{\alpha}(X)\right ] \Big|\right],\]

where we use the shorthand notation  $\mathbbm{1}_{\alpha}(X)=\un} %[1]{\mathbbm{1}\left\{#1\right\}{\lVert X \rVert \geq t_\alpha}$. We derive an upper bound on $ \PP[Z_\alpha - \EE(Z_{\alpha})>t] $ using Proposition~\ref{"Bernstein-extension"}. Namely  we show that the maximum deviations term $D$ and $\sigma^2$ from the latter statement are respectively bounded by
$D \le 1/n$ and $\sigma^2\le 4\alpha/n$. To do so we compute explicitly   the five quantities defined in the satement of Proposition~\ref{"Bernstein-extension"} in our particular context.

\begin{enumerate}
\item  The conditional expectations $f_l$ from Proposition~\ref{"Bernstein-extension"} are
  (recall that $o_i=(x_i,y_i)$),

	\begin{align*}
	&f_{l}(o_1,o_2,\dots,o_l)\\
	&=\mathbb{E}\left (Z_\alpha \mid O_1=o_1,O_2=o_2,\dots,O_l=o_l\right)\\
	&= \frac{1}{K n_{V}}\sum_{j=1}^{K}
	\EE\Bigg[ \sup_{g\in \mathcal{G}}
	\Bigg|\sum_{i \in V_{j,l}}c(g,o_i)\mathbbm{1}_{\alpha}(X_i)+\sum_{i \in V_{j}\setminus V_{j,l} } c(g,O_i)\mathbbm{1}_{\alpha}(X_i) \\
	&\hspace{4cm} -\EE\left[c(g,O)\mathbbm{1}_{\alpha}(X)  \right] \Bigg|\Bigg]\\
	&=\frac{1}{K n_{V}}\sum_{j=1}^{K} \EE\Bigg[ \sup_{g\in \mathcal{G}}
	\left|h_{j,l,g}  \right|\Bigg] \: ,
	\end{align*}
	where $V_{j,l}=V_j\cap \llbracket1,l\rrbracket$ are the mask's indices which belong to the interval $\llbracket1,l\rrbracket$,\,and
	\[h_{j,l,g}=\sum_{i \in V_{j,l}}c(g,o_i)\mathbbm{1}_{\alpha}(x_i)+\sum_{i \in V_{j}\setminus V_{j,l} }c(g,O_i) \mathbbm{1}_{\alpha}(X_i)-\EE\left[c(g,O)\mathbbm{1}_{\alpha}(X)\right] \: . \]

	\item Recall the definition of the  positive deviations $\Delta_l$,
          \[  \Delta_l(o_1,o_2,\dots,o_{l-1},o_l)  =f_{l}(o_1,o_2,\dots,o_{l-1},o_l)-f_{l-1}(o_1,o_2\dots,o_{l-1})\: . \]
In view of the expression for $f_l$ from step 1,   we may thus  write
	\begin{align*}
	\Delta_l(o_{1:l})&=\frac{1}{K n_{V}}\sum_{j=1}^{K} \EE\Bigg[ \sup_{g\in \mathcal{G}}
	\big|h_{j,l,g}   \big|-\sup_{g\in \mathcal{G}}
	\big|h_{j,l-1,g}   \big|\Bigg] \: .
	\end{align*}
	Now, notice  that $V_{j,l}=V_{j,l-1}$ if $l \notin V_{j}$ and $V_{j,l}=V_{j,l-1}\cup\{l\}$ otherwise. Hence
	\[
	h_{j,l,g}-h_{j,l-1,g}= \mathbbm{1}\{l\in V_{j}\}\bigg(c(g,o_l)\mathbbm{1}_{\alpha}(x_l)-c(g,O_l)\mathbbm{1}_{\alpha}(X_l) \bigg) \: .\]
      Using the fact that, for any functions $f,g,$  it holds that
      $ \big\lvert\sup\lvert f \rvert - \sup \lvert g \rvert\big\rvert \leq
      \sup\lvert f-g \rvert$, we obtain
	\begin{equation}
	\label{"delta_bound"}
	\lvert \Delta_l(o_{1:l}) \rvert  \leq \frac{1}{Kn_{V}}\sum_{j=1}^{K}\left[\mathbbm{1}\{l\in V_{j}\}\mathbb{E} \;\underbrace{\sup_{g\in \mathcal{G}}\lvert c(g,o_l)\mathbbm{1}_{\alpha}(x_l)-c(g,O_l)\mathbbm{1}_{\alpha}(X_l) \rvert}_{\leq 1} \right]
	\end{equation}
	and deduce that
	\begin{align*}
	\abs{\Delta_l(o_{1:l})} &\leq \frac{1}{Kn_{V}}\sum_{j=1}^{K}\mathbbm{1}\{l\in V_{j}\}\\
	(\text{by  } \eqref{"key-condition"} ) &\leq \ffrac{1}{n} \: .
	\end{align*}

	\item The maximum positive deviation is defined by
	$D:=\max _{l=1, \ldots, n} \sup _{o_{1}, \ldots, o_{i-1} \in \mathcal{X}} \sup _{o \in \mathcal{X}} \Delta_{l}\left(o_{1}, \ldots, o_{l-1}, o\right) $.
	From the previous step, we immediately obtain \[D\leq 1/n. \]
      \item Let $O'=(X',Y')$ be an independent copy of $O=(X,Y)$ and
        let $o_{1:l}=(o_1,o_2,\dots,o_l)$.  Recall the conditional
        variance term from the statement of
        Proposition~\ref{"Bernstein-extension"},
        $\sigma_l^2(o_{1:l-1}):= \Var[ \Delta_l(O_1,O_2,\dots,O_{l-1},O' ) \mid O_1=o_1, O_2=o_2 , \dots , O_{l-1}=o_{l-1}]$. Then $\sigma_l^2$ may be upper bounded as follows,
	\begin{align*}
	\sigma_l^2(o_{1:l-1})

	&\leq \EE \left[ \Delta_l(O_1,O_2,\dots,O_{l-1},O' ) ^2 \mid O_1=o_1, O_2=o_2 , \dots , O_{l-1}=o_{l-1} \right]\\
	&=\EE \left[ \Delta_l(o_1,o_2,\dots,o_{l-1},O' ) ^2  \right] .
	\end{align*}

	Now using \eqref{"delta_bound"},\,write
	\begin{align*}
          \sigma_l^2 &\leq  \ffrac{1}{(Kn_{V})^2}\mathbb{E}\left[\left(\sum_{j=1}^{K}\mathbbm{1}\{l\in V_{j}\}\mathbb{E}\big[\sup_{g\in \mathcal{G}}\lvert c(g,O')\mathbbm{1}_{\alpha}(X')-c(g,O_l)\mathbbm{1}_{\alpha}(X_l) \rvert \mid X' \big]  \right)^2  \right]\\
          (\lvert c \rvert \leq 1)
                     &\leq (\ffrac{1}{Kn_V})^2\mathbb{E}\left[\left(\sum_{j=1}^{K}\mathbbm{1}\{l\in V_{j}\}\mathbb{E}\big[\sup_{g\in \mathcal{G}}\underbrace{\mathbbm{1}_{\alpha}(X')+\mathbbm{1}_{\alpha}(X_l) }_{\text{independent of $g$}} \mid X'\big]  \right)^2 \right]\\
                     &= (\ffrac{1}{Kn_V})^2\mathbb{E}\left[\left(\sum_{j=1}^{K}\mathbbm{1}\{l\in V_{j}\}\underbrace{(\mathbbm{1}_{\alpha}(X')+\alpha )}_{\text{independent of $j$}}  \right)^2 \right]\\
                     &\leq \EE[(\mathbbm{1}_{\alpha}(X')+\alpha )^2]\left(\frac{1}{Kn_{V}}\sum_{j=1}^{K}\mathbbm{1}\{l\in V_{j}\}\right)^2 \\ & =(\alpha^2+3\alpha)\left(\frac{1}{Kn_{V}}\sum_{j=1}^{K}\mathbbm{1}\{l\in V_{j}\}\right)^2\\
          ( \text{by } \eqref{"key-condition"})
                     &=\ffrac{\alpha^2+3\alpha}{n^2} \\(\alpha \leq 1)
                     &\leq\ffrac{4\alpha}{n^2} \: .
	\end{align*}

	\item Finally get $\sigma^2=\sum_{l=1}^{n}\sup_{o_{1:l-1}}\sigma_l^2(o_{1:l-1})  \leq \ffrac{4\alpha}{n}$.

\end{enumerate}

At this stage, applying proposition \ref{"Bernstein-extension"} gives
\begin{equation*}
\PP(Z_\alpha- \EE[Z_\alpha] > t ) \le  \exp\Big\{\frac{-n t^2}{2(4\alpha + t/3)}\Big\} \: .
\end{equation*}

Therefore for $Z=Z_\alpha/\alpha$ one obtains

\begin{equation*}
\PP(Z- \EE[Z] > t ) \le  \exp\Big\{\frac{-n\alpha t^2}{2(4+ t/3)}\Big\} \: .
\end{equation*}

\subsection{Proof of lemma \ref{"RCV-expectation"}}\label{"proof-RCv-expectation"}
Notice first that, since the observations are \iid,
	\[\mathbb{E}\left[\ffrac{1}{K}\sum_{j=1}^K\sup_{g \in \mathcal{G}}\bigg|\Tilde{\mathcal{R}}_{\alpha}(g,V_j)- \mathcal{R}_{\alpha}(g)\bigg|\right]=
	\mathbb{E}\left[\sup_{g \in \mathcal{G}}\bigg|\Tilde{\mathcal{R}}_{\alpha}(g,V_1)- \mathcal{R}_{\alpha}(g)\bigg|\right].\]
      That is, $\EE(Z) = \EE(Z_{V_1})$, where for a subset of indices  $S = \{1,\ldots, n_S\}$, we denote
      \[
Z_S = \sup_{g \in\mathcal{G}} \big|\Tilde \mathcal{R}_\alpha(g, S) - \mathcal{R}_\alpha(g)\big|.
\]

In order to bound $\EE[Z_S]$ defined above, we follow the same steps as in the proof of Lemma 14 in \cite{goix15}, where most arguments also hold true for a bounded  VC class of cost functions.
We use the symmetrization technique.\,Consider Rademacher random variables $\mathcal{E}=(\epsilon_1,\epsilon_2,\dots,\epsilon_{n_S})$ taking values  in $\{-1,1\}$ and  introduce the randomized process
\[ Z_{\mathcal{E}}=\sup_{g \in \mathcal{G}}\bigg|\frac{1}{\alpha n_S} \sum_{i=1}^{n_S} \epsilon_i c(g,O_i)\un{\lVert X_{i}\rVert> t_\alpha }\bigg| \:.\]
It can be shown using the same classical steps as in the proof of Lemma 13 in \cite{goix15}) that
\begin{equation*}
\label{"Rademacher-inequality"}
\EE(Z_S) \leq 2\EE( Z_{\mathcal{E}}) \: .
\end{equation*}
The key argument to the proceed is to condition the above expectation upon the number of indices $i$ such that $\|X_i\|>t_\alpha$.
Introduce the random variable $O_\alpha$,  which has the same distribution as ($O  \mid \lVert X \rVert  \geq t_\alpha$) and notice that
\[ \sum_{i=1}^{n_S} \epsilon_i c(g,O_i)\un{\lVert X_{i}\rVert> t_\alpha }\sim  \sum_{i=1}^{\mathcal{N}}\epsilon_i c(g,O_{i,\alpha}) \:,\]
where $\mathcal{N}$ has a Binomial distribution $\mathcal{B}(n_S,\alpha)$. Equipped with these notations
\[
\EE( Z_{\mathcal{E}})=
\EE(\phi(\mathcal{N})) \:,
\]

where $\phi(N)=\EE\sup_{g \in \mathcal{G}}\bigg|\ffrac{1}{\alpha n_S} \sum_{i=1}^{N} \epsilon_i c(g,O_{i,\alpha})\bigg|=\ffrac{N}{\alpha n_S}\EE \sup_{g \in \mathcal{G}}  \ffrac{1}{N}\bigg\lvert\sum_{i=1}^{N} \epsilon_i c(g,O_{i,\alpha})\bigg\rvert \: .$

Then by some classical Rademacher complexity arguments for finite VC-classes
  (see \emph{e.g.} \cite{gine2001consistency}, Proposition 2.1),
\begin{align*}
  \EE \sup_{g \in \mathcal{G}}\ffrac{1}{N} \bigg\lvert\sum_{i=1}^{N} \epsilon_i c(g,O_{i,\alpha})\bigg\rvert& \leq \ffrac{M'_1\sqrt{\mathcal{V}_{\mathcal{G}}}}{\sqrt{N}}
                                                                                + \frac{M'_2 \mathcal{V}_{\mathcal{G}}}{N}\; \\
& \le M'\sqrt{ \frac{\mathcal{V}_{\mathcal{G}}}{N}},\end{align*}
for some universal constant $M'>0$,  whence
\begin{align*}
  \phi(N) &\leq \ffrac{N}{\alpha n_S} \ffrac{ M'\sqrt{\mathcal{V}_{\mathcal{G}}}}{\sqrt{N}}\;
            = \ffrac{ M'\sqrt{\mathcal{V}_{\mathcal{G}} N}}{\alpha n_S}

\end{align*}
By concavity we have   $\EE(\sqrt N) \le \sqrt{\EE(N)} = \alpha n_S$, and we obtain
\[\EE( Z_S)\leq 2\EE( Z_{\mathcal{E}}) \leq
  \ffrac{2 M'\sqrt{\mathcal{V}_{\mathcal{G}}}}{\sqrt{n_S \alpha}}
\: .  \]

The result follows with $n_S = n_V$.

\subsection{Detailed proof of Theorem~\ref{theo:main-sanity-rare}}\label{sec:main-theo-proof}
In view of the argument following the statement, we derive probability upper bounds for the three terms $\mathrm{D_{t_\alpha}}$, $\mathrm{D_{cv}}$ and $\mathrm{Bias}}%{C_{train}$ defined in equations~(\ref{"dev_ext"},~\ref{"dev_CV"},~\ref{"bias_CV"}).

\paragraph{Probability bound for $\mathrm{D_{t_\alpha}}$ (see~\eqref{"dev_ext"}).}
 Using the fact that the cost function verifies $0\leq c \leq 1$,  write
\begin{equation*
\hspace{-4mm}\mathrm{D_{t_\alpha}}=\abs{\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\Tilde{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})} \leq U,
\end{equation*}
where $U=\ffrac{1}{Kn_{V}\alpha}\sum_{j=1}^{K}\sum_{i\in V_j}u_{i}$ and (we recall that)
\[u_{i}=\left|\un{\lVert X_{i}\rVert>\lVert X_{(\lfloor \alpha n \rfloor)}\rVert}
-\un{\lVert X_{i} \rVert \geq t_\alpha}\right|.\]
Now notice that
\begin{align*}
U &= \ffrac{1}{Kn_{V}\alpha}\sum_{j=1}^{K}\sum_{i=1}^{n} u_{i}\un} %[1]{\mathbbm{1}\left\{#1\right\}{i \in V_j}\\
&=\ffrac{1}{Kn_{V}\alpha}\sum_{i=1}^{n}u_{i}\sum_{j=1}^{V}\un{i \in V_j}
\\&= \ffrac{1}{n\alpha}\sum_{i=1}^{n}u_{i}. \end{align*}
The last line follows from Assumption \ref{assum:mask-property}.
Hence, using \eqref{bound:z1}, we obtain
\begin{equation}\label{'c_ext'}
\PP( \mathrm{D_{t_\alpha}} -1/n\alpha  \geq t ) \leq  2\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right).
\end{equation}

\paragraph{Probability bound for $\mathrm{D_{cv}}$ (see~\ref{"dev_CV"})).}

First, notice that
\begin{align*}
C_{CV}&=\abs{
	\ffrac{1}{K}\sum_{j=1}^{K}\big[ \Tilde{\mathcal{R}}_{\alpha}\left(\Psi_\alpha(T_j),V_j\right)-\mathcal{R}_{\alpha}\left(\Psi_\alpha(T_j)\right) \big]} \\
&\leq \ffrac{1}{K}\sum_{j=1}^{K}\sup_{g \in \mathcal{G}}\lvert \Tilde{\mathcal{R}}_{\alpha}(g,V_j)-\mathcal{R}_{\alpha} \rvert.
\end{align*}

Using Corollary~\ref{"RCV-sup-control"}
with
\[Z=\ffrac{1}{K}\sum_{j=1}^K\sup_{g \in\mathcal{G}}\lvert\Tilde{\mathcal{R}}_{\alpha}(g,V_j)-\mathcal{R}_{\alpha}(g)\rvert,\]
one obtains  the inequality
\begin{equation}\label{eq:C-CV-bound}
\PP(\mathrm{D_{cv}}-B(n_{V},\alpha)\geq t) \leq \exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right),
\end{equation}
with
\[ B(n_{V},\alpha)= \ffrac{M\sqrt{\mathcal{V}_\mathcal{G}}}{\sqrt{\alpha n_{V}}}, \]
for some universal constant $M>0$.

\paragraph{Probability bounds for $\mathrm{Bias}}%{C_{train}$ (see \eqref{"bias_CV"}).} We write
\begin{align}\label{ineq:Bias-CV-decomp}
\mathrm{Bias}}%{C_{train}&= \ffrac{1}{K}  \left|\sum_{j=1}^K\Bigg(\mathcal{R}_{\alpha}(\Psi_{\alpha}(T_j))-\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\Bigg)\right| \nonumber\\
&\leq C_1+C_2,
\end{align}
with
\begin{align*}
	C_1=\ffrac{1}{K}\left|\sum_{j=1}^K \left( \mathcal{R}_{\alpha}(\Psi_{\alpha}(T_j))-\widehat{\mathcal{R}}_{\alpha}( \Psi_\alpha({T_j}) , T_j) +\widehat{\mathcal{R}}_{\alpha}( \Psi_\alpha({T_j}) , T_j)-\mathcal{R}_\alpha^*\right)\right|,
\end{align*}

\begin{align*}
	C_2=\left|\mathcal{R}_\alpha^* -  \widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),S_n)+\widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),S_n) - \mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\right|
\end{align*}

and \[\mathcal{R}_\alpha^*=\inf_{g \in \mathcal{G}}\mathcal{R}_\alpha(g).\]
Using the fact that  $\widehat{\mathcal{R}}_{\alpha}( \Psi_\alpha({T_j}),T_j)= \inf_{g\in \mathcal{G}}\widehat{\mathcal{R}}_{\alpha}( g, T_j)$ (Assumption~\ref{assum:ERM-settings}) and for any real functions $h$ and $f$, $\lvert \inf{h}-\inf{f}\rvert \leq  \sup\lvert h-f\rvert $ , write
\begin{align*}
\ffrac{1}{K}\left|\sum_{j=1}^K\bigg( \widehat{\mathcal{R}}_{\alpha}( \Psi_\alpha({T_j}) , T_j)-\mathcal{R}_\alpha^*\bigg)\right| &=	\ffrac{1}{K}\left|\sum_{j=1}^K \inf_{g\in \mathcal{G}}\widehat{\mathcal{R}}_{\alpha}(g, T_j)- \inf_{g\in \mathcal{G}}\mathcal{R}_{\alpha}(g)\right|\\&\leq\ffrac{1}{K}\sum_{j=1}^K\left| \inf_{g\in \mathcal{G}}\widehat{\mathcal{R}}_{\alpha}( g , T_j)- \inf_{g\in \mathcal{G}}\mathcal{R}_{\alpha}(g)\right|\\&\leq\frac{1}{K}\sum_{j=1}^K\sup_{g \in \mathcal{G}}\lvert\widehat{\mathcal{R}}_{\alpha}(g,T_j)- \mathcal{R}_{\alpha}(g)\rvert.
\end{align*}

Then,\,by using the triangle inequality, deduce that
\begin{align}\label{ineq:C-1-decomp}
C_1
&\leq  \ffrac{2}{K}\sum_{j=1}^K\sup_{g \in \mathcal{G}}\lvert\widehat{\mathcal{R}}_{\alpha}( g,T_j)- \mathcal{R}_{\alpha}(g)\rvert \nonumber\\
&\leq Z_1+Z_2,
\end{align}

with
\[Z_1=\ffrac{2}{K}\sum_{j=1}^K\sup_{g \in \mathcal{G}}\lvert
\widehat{\mathcal{R}}_{\alpha}( g , T_j)-
 \Tilde{\mathcal{R}}_{\alpha}(g,T_j)\rvert,\]
\[Z_2=\ffrac{2}{K}\sum_{j=1}^K\sup_{g \in \mathcal{G}}\lvert\Tilde{\mathcal{R}}_{\alpha}(g,T_j)- \mathcal{R}_{\alpha}(g)\rvert.\]
In order to bound $Z_2$ we use the fact that the statements of   Lemmas~\ref{"RCV-supp"}, \ref{"RCV-expectation"} and Corollary~\ref{"RCV-sup-control"} still hold true if one substitutes the training sets $T_j$ for the validation sets $V_j$, and the training size $n_T$ for $n_V$, as revealed by an inspection of the proofs,  see Sections~\ref{"lemma-RCV-supp-proof"}
  and~\ref{"proof-RCv-expectation"}. The only difference between the two arguments is in steps 2 and 4 from the proof of Lemma~\ref{"RCV-supp"} where we use the identity $	\frac{1}{K}\sum_{j=1}^{K}\ffrac{\un} %[1]{\mathbbm{1}\left\{#1\right\}{l \in T_j} }{n_{T}}
        =\frac{1}{n}
$ from Lemma~\ref{"train-test-cond"} instead of Identity~(\ref{"key-condition"}).
Thus we obtain, from the twin statement of Corollary~\ref{"RCV-sup-control"},

\begin{equation}\label{ineq:BCV-Z-2}
	\PP(Z_2-2B(n_{T},\alpha) \geq 2t ) \leq 2\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right),
\end{equation}
where $B(n,\alpha)$ is defined in~(\ref{"V-n-def"}).

Similarly the term $Z_1$ can be bounded following the same argument as in the first paragraph (Probability bound for $\mathrm{D_{t_\alpha}}$)) up to  replacing $V_j$ with $T_j$ and $n_V$ with $n_T$, which yields
\begin{equation}\label{ineq:BCV-Z-1}
\PP(Z_1 - \frac{2}{n_{T}\alpha} \geq 2t ) \leq 4\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right).
\end{equation}

Decomposition (\ref{ineq:C-1-decomp}) combined with inequalities (\ref{ineq:BCV-Z-2}), (\ref{ineq:BCV-Z-1}) leads to
\begin{equation}\label{eq:first-term-bound}
\PP\left(C_{1}-2Q(n_{T},\alpha) \geq   4t \right) \leq  6\exp\left(\frac{-n\alpha t^2}{2(4+t/3)}\right),
\end{equation}
with
\begin{align}
	Q(n,\alpha)&=B(n,\alpha)+\ffrac{1}{n\alpha}\nonumber\\ &=\ffrac{M\sqrt{\mathcal{V}_\mathcal{G}}}{\sqrt{\alpha n}}+\ffrac{1}{n\alpha}. \label{eq:Q-def}
\end{align}
Using the same technique,\,one has
\[C_2 \leq 2\sup_{g \in \mathcal{G}}\lvert\widehat{\mathcal{R}}_{\alpha}( g,S_n)- \mathcal{R}_{\alpha}(g)\rvert.\]
Then by Lemma~\ref{lemma:inv-goix}, we obtain
\begin{align}\label{eq:second-term-bound}
\PP\left(C_{2}-2Q(n,\alpha) \geq 4t \right) \leq  6\exp\left(\frac{-n\alpha t^2}{2(4+t/3)}\right).
\end{align}

Moreover,\,notice that we have
\begin{equation*}
\begin{cases}
4B(n_{T},\alpha) \geq 2B(n,\alpha) +2B(n_{T},\alpha), \\
\ffrac{4}{n_{T}\alpha}     \geq \ffrac{2}{n_{T}\alpha} + \ffrac{2}{n\alpha}.
\end{cases}
\end{equation*}
Therefore we get
\begin{equation}\label{eq:monotone-ineq}
	4Q(n_{T},\alpha) \geq 2Q(n,\alpha)+2Q(n_{T},\alpha).
\end{equation}
Combining equations (\ref{eq:first-term-bound}),\,(\ref{eq:second-term-bound}),\,(\ref{eq:monotone-ineq}) and decomposition (\ref{ineq:Bias-CV-decomp}) yields
\begin{equation}\label{"C_train_bound"}
\PP\left(\mathrm{Bias}}%{C_{train}-4Q(n_{T},\alpha)\geq 8t \right) \leq  12\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right).
\end{equation}
\paragraph{Assembling terms.}
Using equations (\ref{'c_ext'}), (\ref{eq:C-CV-bound}), (\ref{"C_train_bound"}) and the decomposition (\ref{ineq:main-decomposition}),\,deduce the inequality
\begin{equation}\label{ineq:CV-Base-UB}
\PP\bigg(\big|\widehat{\mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\big| - E_{CV}(n_{T},n_{V},\alpha)\geq 10t \bigg)  \leq  15\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right),
\end{equation}
with
\begin{align*
&E_{CV}(n_{T},n_{V},\alpha)=B(n_{V},\alpha)+4Q(n_{T},\alpha)+\ffrac{1}{n_{T}\alpha} \nonumber  \\ &=M\sqrt{\mathcal{V}_\mathcal{G}}(\frac{1}{\sqrt{n_{V}\alpha}}+\frac{4}{\sqrt{n_{T}\alpha}})+\ffrac{5}{n_{T}\alpha}.
\end{align*}

The last line follows, using the definitions of $B$ (eq. \ref{"V-n-def"}) and $Q$ (eq. \ref{eq:Q-def}).

By inverting inequality (\ref{ineq:CV-Base-UB}),\,one has,\,with probability $1-15\delta$,
\begin{equation*}
\bigg|\widehat{\mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big) \bigg| \leq   E_{CV}(n_{T},n_{V},\alpha)+ \frac{20}{3 n \alpha}\log(\frac{1}{\delta}) + 20\sqrt{\frac{2}{n\alpha}\log(\frac{1}{\delta})},
\end{equation*}
which is the desired result.

\subsection{Proof of Theorem~\ref{theo:main-sanity-rare-lpo}}\label{"main-theo-lpo-proof"}

In view of the discussion following the statement of the theorem (namely the risk decomposition~(\ref{"basic-inequality"}) and the Markov-type inequality~(\ref{eq:keyTheorem2fromLemma})) and the bound for the term $\mathrm{Bias}}%{C_{train}$ obtained in \eqref{"C_train_bound"}, we only need to obtain bounds for the expectations $\EE(\mathrm{D_{t_\alpha}})$, $\EE(\mathrm{Bias}}%{C_{train})$,
and  $\EE\big(\abs{\hat\mathcal{R}_\alpha(\Psi_\alpha(S_n),S_n)- \mathcal{R}_{\alpha}(\Psi_\alpha(S_n))}\big)$.
The proof will then be completed by combining together the different terms.

	\paragraph{Bounding $\mathbb{E}(\mathrm{D_{t_\alpha}})$.} By equation \ref{'c_ext'}, one has
	\begin{equation*}
	\PP( \mathrm{D_{t_\alpha}} -\frac{1}{n\alpha} \geq t ) \leq  \exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right) \: .
	\end{equation*}
On the one hand, under Assumption~\ref{assum:cost-func} one has $\PP(\mathrm{D_{t_\alpha}} -\frac{1}{n\alpha}  \geq t) =0$ for $t \geq 2$. On the other hand, we have the trivial inequality,
	\[\forall t \leq 2 \: , \: 2(4+t/3) \leq 10 \: .\]
	Hence we can write, for $t\geq0$,
	\begin{equation}\label{ineq:C-ext-larger-bound}
	 \PP( \mathrm{D_{t_\alpha}} -\frac{1}{n\alpha}   \geq t ) \leq  \exp\left(\ffrac{-n\alpha t^2}{10}\right) \: .
	\end{equation}
	Therefore by lemma \ref{"Expectation-UB-subgauss"}, we get
	\begin{align}\label{"exp_c_ext"}
	\EE(\mathrm{D_{t_\alpha}}) &\leq \frac{1}{n\alpha} + \frac{M_1}{\sqrt{n\alpha}} \nonumber\\ & \leq \frac{1}{n_{T}\alpha} + \frac{M_1}{\sqrt{n_{T}\alpha}} \:,
	\end{align}
	for some universal constant $M_1  > 0$.

	\paragraph{Bounding $\mathbb{E}(\mathrm{Bias}}%{C_{train})$.}
	Using equation \eqref{"C_train_bound"} and reasoning as in the previous paragraph  leads to
	\begin{align}\label{"exp_c_train"}
	\EE(\mathrm{Bias}}%{C_{train}) \leq    4Q(n_{T},\alpha)+\frac{M_2}{\sqrt{n_{T}\alpha}},
	\end{align}
	where $Q(n,\alpha)$ is defined by \eqref{eq:Q-def} and $M_2>0$ is a universal constant,\,independent of $\mathcal{G}$,\,$n$ and $\alpha$.
	\paragraph{Bounding $\EE(\abs{\hat\mathcal{R}_\alpha(\Psi_{\alpha}(S_n),S_n)- \mathcal{R}_{\alpha}(\Psi_{\alpha}(S_n))})$.} By lemma \ref{lemma:inv-goix} we obtain
	\begin{align}\label{"risk_alpha_bound"}
	\PP( \big|\hat\mathcal{R}_\alpha(\Psi_{\alpha}(S_n),S_n)- \mathcal{R}_{\alpha}(\Psi_\alpha(S_n))\big|  - Q(n,\alpha)  \geq 2t )  \leq 3\exp\left(\frac{-n\alpha t^2}{2(4+t/3)}\right)\:.
\end{align}
	Then we get
	\begin{align}\label{"exp_c_ER"}
	\EE(\big|\hat\mathcal{R}_\alpha(\Psi_{\alpha}(S_n),&S_n)- \mathcal{R}_{\alpha}(\Psi_{\alpha}(S_n))\big|) \nonumber\\&\leq Q(n,\alpha) +\frac{M_3}{\sqrt{n\alpha}} \nonumber
	\\& \leq  Q(n_{T},\alpha) +\frac{M_3}{\sqrt{n_{T}\alpha}} \:,
	\end{align}
for some universal constant $M_3>0$.

Combining equations \eqref{"exp_c_ext"}, \eqref{"exp_c_train"}, \eqref{"exp_c_ER"} with Lemma \ref{"RCV-markov"} gives
\begin{equation}\label{"Markov-CV-ineq"}
\PP(\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K}) \geq t ) \leq  \frac{5Q(n_{T},\alpha) +\ffrac{M_4}{\sqrt{n_{T}\alpha}}}{t}
+ \ffrac{(1/n_{T}\alpha)}{t}\:,
\end{equation}
where $M_4=M_1+M_2+M_3$. The next step is to derive a probability bound for $\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})$. We have
\begin{align}
\PP(\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})&
-5Q(n_{T},\alpha) \geq 10t )  \nonumber\\
&\leq	\PP(\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\widehat{ \mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),S_n)
-5Q(n_{T},\alpha) \geq 10t )	\nonumber \\
&\leq  \PP(\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{\alpha}(\Psi_{\alpha}(S_n))-4Q(n_{T},\alpha)\geq 8t )\nonumber\\&\hspace{5mm} + \PP(\mathcal{R}_{\alpha}(\Psi_{\alpha}(S_n))-\widehat\mathcal{R}_\alpha(\Psi_{\alpha}(S_n),S_n) \nonumber-Q(n_{T},\alpha)\geq 2t)	\nonumber \\
&\leq \PP(\big|\widehat\mathcal{R}_\alpha(\Psi_{\alpha}(S_n),S_n))- \mathcal{R}_{\alpha}(\Psi_{\alpha}(S_n))\big|-Q(n_{T},\alpha) \geq 2t) \nonumber  \\& \hspace{5mm}+\PP(\mathrm{Bias}}%{C_{train} -4Q(n_{T},\alpha)\geq 8t )\nonumber\\
(\text{By  } \ref{"C_train_bound"} + \ref{"risk_alpha_bound"})&\leq 15\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right) . \label{"neg-Markov-CV-ineq"}
\end{align}
The first inequality follows from the fact that $\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K}) \geq  \widehat{ \mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),S_n)$ (lemma \ref{"RCV-ge-RN"}). The second inequality is obtained by a union bound. The third inequality follows from the definition of $\mathrm{Bias}}%{C_{train}$ (eq. \ref{"bias_CV"}). Combining \eqref{"Markov-CV-ineq"} and \eqref{"neg-Markov-CV-ineq"} and that
\begin{align*}
\PP(\abs{X}\geq 10t) &\leq \PP(X\geq 10t)+ \PP(-X\geq 10t) \leq    \PP(X\geq t)+ \PP(-X\geq 10t),
\end{align*}
leads to
\begin{align}\label{ineq: markov-cv-dev}
\nonumber &\PP\bigg(\big|\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K}) \big| -5Q(n_{T},\alpha) \geq 10t \bigg)  \\
&\leq  \frac{5Q(n_{T},\alpha) }{t} +\frac{M_4/\sqrt{n_{T}\alpha} }{t} + \ffrac{(1/n_{T}\alpha)}{t}  + 15\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right) \: .
\end{align}
Finally, using \eqref{"basic-inequality"}, we get
\begin{align}\label{ineq:UB-MARkov-LPO}
\nonumber &\PP\Big(\big|\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\big| -9Q(n_{T},\alpha) \geq 18t\Big)\\
\nonumber &\leq\PP(\mathrm{Bias}}%{C_{train}-4Q(n_{T},\alpha)\geq 8t) + \PP\Big(\big|\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})\big|-5Q(n_{T},\alpha)\geq 10t\Big) \\
& \leq \frac{Q(n_{T},\alpha) +(M_4/\sqrt{n_{T}\alpha})}{t}
+\ffrac{1/(n_{T}\alpha)}{t}+ 27\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right) .
\end{align}
The last line follows from \eqref{"C_train_bound"} and \eqref{ineq: markov-cv-dev}. Since for any $t\geq 2$,
\begin{equation*}
\PP\Big(\big|\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\big| -9Q(n_{T},\alpha) \geq 18t\Big)=0
\end{equation*}
we can restrict our attention to the case $t\leq 2$, for which  we have
\[ 27\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right) \leq 27\exp\left(\ffrac{-n\alpha t^2}{10}\right) . \]
Using that $\exp(-x)\leq \ffrac{1}{x}$ for $x \geq 0$, we deduce that
\begin{align*}
27\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right)  \leq \frac{270}{n\alpha t^2}.
\end{align*}
Using the latter inequality and inverting \eqref{ineq:UB-MARkov-LPO},\,we get that with probability $1-18\delta$,
\begin{equation*}
\big|\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\big| \leq 9Q(n_{T},\alpha +\frac{5Q(n_{T},\alpha) +  (M_4/\sqrt{n_{T}\alpha})+(1/n_{T}\alpha)}{\delta} +\sqrt{\frac{270}{n_{T}\alpha\delta}},
\end{equation*}
Using the fact that  $ \sqrt{\ffrac{1}{\delta}}\leq\ffrac{1}{\delta}$ (since $\delta \leq 1$), the latter inequality becomes:
\begin{align*}
|\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big) | \leq
9Q(n_{T},\alpha+
\ffrac{1}{\delta\sqrt{n_{T}\alpha}}(5Q(n_{T},\alpha)+M_5)+\ffrac{1}{\delta n_{T}\alpha},
\end{align*}
with $M_5=M_4+\sqrt{270}$. Replacing $Q$ with its expression (Equation~\ref{eq:Q-def}) gives the desired result.

\subsection{Context}\label{"ERM-notations"}
Let $O= (X,Y)$ be a random vector valued in $\mathcal Z =  \mathcal X \times \mathcal Y$, having distribution $P$. Let $0<\alpha \ll 1$, and let $t_\alpha$  be the  $1-\alpha$ quantile of $\lVert X \rVert$. Using $t_\alpha$, one can define a `rare region' (rare since $\alpha \ll 1$)
by $\lVert X \rVert \geq t_\alpha$. For simplicity we assume that $\alpha n = k$ is an integer, where $n$ is the training sample size. Given a class of discrimination rules $\mathcal G$, define  a loss function $c : \mathcal G \times \mathcal Z \to \mathbb{R}$. Following~\cite{jalalzai2018binary} the risk of $g\in \mathcal G$ over the previous rare region is defined as
\begin{equation}
  \label{eq:def-risk-extreme}
  \mathcal{R}_{\alpha}(g)=\EE\left[ c(g,O)\mid \lVert X \rVert \geq t_\alpha \right].
\end{equation}
 \,Let $\data_n=(O_1,\ldots, O_n)$ be a collection of independent and identically distributed random vectors with common distribution $P$.
Given a subsample $S\subset \{1,\ldots , n\}$, the risk estimate based on  $S $ is given by
\[\widehat{\mathcal{R}}_{\alpha}(g, S)=\frac{1}{\alpha n_S} \sum_{i\in S} c(g,O_i)\un} %[1]{\mathbbm{1}\left\{#1\right\}{\lVert X_{i}\rVert>\lVert X_{(\lfloor \alpha n \rfloor)}\rVert },
\]
where $n_S=card(S)$ and $\left\|X_{(1)}\right\| \geq \ldots \geq\left\|X_{(n)}\right\|$ are the (reverse) order statistics of the sample $(\left\|X_i\right\|)_{i= 1,\ldots, n }$.
Our main results hold under assumptions~\ref{assum:ERM-settings} to~\ref{assum:mask-property}  introduced below.

\begin{assumption}[ERM algorithm] \label{assum:ERM-settings}
	The learning rule $\Psi_{\alpha}$ is defined as the  empirical risk minimizer,
	\begin{equation}\label{"g_alpha_j_def"}
	\Psi_\alpha({S})=\argmin_{g \in \mathcal{G}}\widehat{\mathcal{R}}_{\alpha}(g, S).
	\end{equation}
\end{assumption}

Based on the previous definition, the Hold-out estimator of the risk of the learning rule $\Psi_\alpha$ with validation set $V\subset \{1,\ldots, n\}$ and training set $T = \{1,\ldots, n\}\backslash V$ takes the simple form
$	\widehat{\mathcal{R}}_{\alpha}( \Psi_\alpha({T}) , V)$. Given a family of validation sets in  $\{1,\ldots, n\}$,  $V_{1:K} = (V_j)_{j=1,\ldots, K}$,
the \textsc{CV}\xspace  estimator of the risk of $\Psi_\alpha$ is
\begin{equation}\label{"rcvEx-def"}
	\widehat{\mathcal{R}}_{CV,\alpha}(\Psi_\alpha,V_{1 : K})=
	\frac{1}{ K} \sum_{j= 1}^{K}
	\ \widehat{\mathcal{R}}_{\alpha}( \Psi_\alpha({T_j}) , V_j),
\end{equation}
where $T_j = \{1,\ldots, n\} \backslash V_j$. In the sequel we shall often refer to $V_{1:K}$ as the \emph{sequence of masks} because the validation sets are  masked at the training step.
 For clarity reasons, we suppose further that $n$ is divisible by $K$ so that $n/K$ is an integer. This condition guarantees, in the case of $K$-fold cross validation, that all validation sets have the same cardinal $n_{V}=n/K$. We also need the sequence of masks to satisfy a certain balance condition which is expressed below.
\begin{assumption}[Mask property]\label{assum:mask-property}
	The sequence of masks $V_1,V_2,\dots V_K$  satisfies
	\begin{equation}\label{"card-condition"}
	card(V_j)=n_V\quad \forall j \in \llbracket1,K\rrbracket,
	\end{equation}
	for some $n_V \in \llbracket1,n\rrbracket$.\,Moreover it holds that
	\begin{equation}\label{"key-condition"}
	\frac{1}{K}\sum_{j=1}^{K} {\un} %[1]{\mathbbm{1}\left\{#1\right\}{l \in V_j} }=\frac{n_V}{n} \quad \forall l \in \llbracket1,n\rrbracket.
	\end{equation}
\end{assumption}

The next lemma ensures that Assumption~\ref{assum:mask-property} holds true for the standard \textsc{CV}\xspace  procedures (K-fold and \emph{l.p.o.}\xspace) and that condition similar to~\eqref{"key-condition"} is also valid for the training sets $T_j$.

\begin{lemma}
	\label{"train-test-cond"}
	If $K$ divides $n$, for the leave-one-out, leave-$p$-out,\,and $K$-fold procedures,
the sequence of masks $V_{1:K}$ satisfies Assumption~\ref{assum:mask-property}. Also the
        the training sets
	$T_{1:K}$ satisfy
	\begin{equation*}
	\frac{1}{K}\sum_{j=1}^{K}\ffrac{\un} %[1]{\mathbbm{1}\left\{#1\right\}{l \in T_j} }{n_{T}}
        =\frac{1}{n} \quad \forall l \in \llbracket1,n\rrbracket.
	\end{equation*}

\end{lemma}

\begin{myproof}
See Appendix~\ref{"proof-train-test-cond"}
\end{myproof}
\begin{remark}\label{rem:KdividesN}
  The condition that $K$ divides $n$ is required for the  $K$-fold  \textsc{CV}\xspace only, in order to ensure that  $card(V_j)=n_{V}$ for all $j$.
  However straightforward extensions of our results can be obtained in the case where $K$ does not divide $n$ at the price of some notational complexity.

	\end{remark}

We now introduce two assumptions relative to the function class $\mathcal G$ and the cost function $c$. They shall be useful to control the fluctuation of the underlying empirical process. First we require the following standard complexity restriction on the family of functions $(x,y) \mapsto c(g(x), y)$ when $g$ lies in $ \mathcal G$.

\begin{assumption}[finite VC dimension]\label{assum:hypo-class}
  The family $\mathcal{G}$ of classifiers and the cost function $c$ are such that the class of functions $o\mapsto c(g,o) = c(g(x),y)$ on $\mathcal{Z}$
  has a finite VC-dimension $\mathcal{V}_{\mathcal{G}}$, \ie the family of subgraphs
  $\big\{ \{(x,y, t): t < c(g(x), y) \}: t \in \mathbb{R}, (x,y) \in \mathcal{Z}, g \in \mathcal{G} \big\}$ has Vapnik dimension $\mathcal{V}_{\mathcal{G}}$.
      \end{assumption}

Since part of our proofs rely on \cite{gine2001consistency}, we may rather assume directly that the covering number for the $L_2$ norm of this family of functions decrease polynomially (with exponent $\mathcal{V}_{\mathcal{G}}$) (see their condition (2.1)). This would not change the results. This condition is sometimes easier to check in practice.

For simplicity and in view of our focus on binary classification, we limit ourselves to a cost function bounded by $1$. Our result may be extended to any bounded cost function at the price of a multiplicative scaling factor.
\begin{assumption}[Normalized cost function]\label{assum:cost-func}
	The cost function $c$ is non-negative and bounded by $1$,
	\[ 0 \leq c(g,O) \leq 1 \quad\quad \forall (g,O) \in  \mathcal{G}\times \mathcal{Z}. \]
     This hypothesis is clearly satisfied for the  Hamming loss $c(g,O) = \un{ g(X) \neq Y }$.
\end{assumption}

\subsection{Generic tools}
\label{sec:genericTools}

\,First,\,we recall the following McDiarmid's extension of Bernstein inequality (Theorem 3.8 in \cite{McDiarmid98conc}).
\begin{proposition}\label{"Bernstein-extension"}
	For a sequence of observations $(O_1,O_2,\dots,O_n) \in \mathcal{Z}^n$ and some fixed values $o_{1:l}=(o_1,o_2,\dots,o_l)$ and for some measurable function $f\,:\,\mathcal{Z}^n\rightarrow \mathbb{R}$,\,let $Z=f(O_1,O_2,\dots,O_n)$ and define for $l \in \llbracket1,n\rrbracket$:
	\begin{enumerate}
		\item $f_{l}(o_1,o_2,\dots,o_l)=\mathbb{E}\left (Z \mid O_1=o_1,O_2=o_2,\dots,O_l=o_l\right),$
		\item $\Delta_l(o_1,o_2,\dots,o_{l-1},o_l)  =f_{l}(o_1,o_2,\dots,o_{l-1},o_l)-f_{l-1}(o_1,o_2\dots,o_{l-1}),$ (the positive deviations)
		\item $D:=\max _{l=1, \ldots, n} \sup _{o_{1}, \ldots, o_{i-1} \in \mathcal{X}} \sup _{o \in \mathcal{X}} \Delta_{l}\left(o_{1}, \ldots, o_{l-1}, o\right),$ (the maximum positive deviation)
		\item  $\sigma_{l}^2(o_{1:l-1})=\Var\left[ \Delta_l(O_1,O_2,\dots,O_{l-1},O' )
		\mid O_1=o_1, O_2=o_2 , \dots , O_{l-1}=o_{l-1} \right],$ where $O'$ is an independent copy of $O_1,$
            \item
              $\sigma^2=\sum_{l=1}^n \sup_{o_{1:l-1}\in
                \mathcal{X}^{l-1}} \sigma^2_l(o_{1:l-1})$ (the
              maximum sum of variances).
	\end{enumerate}
	Then we have
	\[ \PP(Z - \EE[Z] > t ) \le \exp{\left(\ffrac{-t^2}{2(\sigma^2 + Dt/3)}\right)}. \]
      \end{proposition}

We also recall Proposition 2.5.2 from \cite{vershynin_2018},\,which provides an upper bound for the expectation of sub-Gaussian random variables.
\begin{proposition}\label{"Expectation-UB-subgauss"}
Let $X$ be a real valued random variable and suppose that $\PP(X\geq t)\leq C_1\exp{\left(-t^2/C_2^2\right)}$, for some $C_1 , C_2 > 0$, then there exists a constant $M_2>0$ which depends only on $C_1$,\,such that
\[ \EE(X) \leq M_2 C_2.
\]
\end{proposition}

\subsection{Technical results}\label{sec:technicalResults}

\begin{lemma}\label{"RCV-ge-RN"}
Let $\Psi_{\alpha}$ be the ERM rule on the tail region of level $1-\alpha$ defined in (\ref{"g_alpha_j_def"}). Given a dataset	$\data_n=(O_1,O_2,\dots,O_n)\in \mathcal{X}^n$ and a sequence of mask $V_{1:K}$ it holds that
\[
\widehat{ \mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),S_n) \leq  \widehat{\mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K}).
\]
In other words the \textsc{CV}\xspace risk estimate of the ERM rule cannot be less than the empirical risk evaluated on the full dataset.
\end{lemma}

\begin{proof}
The argument for $\alpha\neq 1$ is the same as the one for
 $\alpha=1$ (standard ERM) which may be found in \cite{kearns1999algorithmic}. We reproduce
  it for the sake of completeness. By definition of
  $\Psi_{\alpha}(S_n)$,\,one has

\begin{equation*}
  \forall j \in \llbracket 1,n \rrbracket \:,\: \widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(T_j),S_n) \geq \widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),S_n).
\end{equation*}

Since $\widehat{\mathcal{R}}_{\alpha}(g,S_n)= \ffrac{1}{n}\left( n_{V}\widehat{\mathcal{R}}_{\alpha}(g,V_j)+n_{T}\widehat{\mathcal{R}}_{\alpha}(g,T_j) \right)$, for $g\in \mathcal{G}$.\,It follows that
\[ \ffrac{1}{n}\left( n_{V}\underbrace{\widehat{\mathcal{R}}_{\alpha}(\Psi_\alpha(T_j),V_j)}_{\text{validation error}}+n_{T}\underbrace{\widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(T_j),T_j)}_{\text{training error}}  \right) \geq \ffrac{1}{n}\left( n_{V}\widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),V_j)+n_{T}\widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),T_j) \right).\]

Since $\Psi_{\alpha}(T_j)$ minimizes the training error on the $j$'th train set $T_j$, in particular we have $\widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),T_j) \geq  \widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(T_j),T_j)$, hence
\begin{equation}\label{ineq:cv-er-base}
	\widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),V_j) \leq  \widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(T_j),V_j)\:,\:\forall j \in \llbracket 1 , K \rrbracket.
\end{equation}

In addition the average empirical risk of $\Psi_\alpha(S_n)$ is equal to its empirical risk on the full dataset, indeed
\begin{align*}
	\ffrac{1}{K}\bigg(\sum_{j=1}^{K}\widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),V_j)\bigg)&=\ffrac{1}{Kn_{V}}\bigg(\sum_{j=1}^{K}\sum_{i\in V_j} c\big(\Psi_{\alpha}(S_n),O_i)\un{\lVert X_{i}\rVert>\lVert X_{(\lfloor \alpha n \rfloor\big)}\rVert }\bigg)\\
	&=\ffrac{1}{Kn_{V}}\bigg(\sum_{j=1}^{K}\sum_{i=1}^{n}c\big(\Psi_{\alpha}(S_n),O_i\big)\un{i \in V_j}\un{\lVert X_{i}\rVert>\lVert X_{(\lfloor \alpha n \rfloor)}\rVert }\bigg)\\
	&=\ffrac{1}{Kn_{V}}\bigg(\sum_{i=1}^{n}c\big(\Psi_{\alpha}(S_n),O_i\big)\un{\lVert X_{i}\rVert>\lVert X_{(\lfloor \alpha n \rfloor)}\rVert }\bigg)\sum_{j=1}^{K}\un{i \in V_j}\\
	(\text{By lemma }\ref{"train-test-cond"})&=\widehat{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n)).
\end{align*}

Thus \,by averaging inequality \ref{ineq:cv-er-base}, we get
\[
\widehat{ \mathcal{R}}_{\alpha}(\Psi_{\alpha}(S_n),S_n) \leq  \widehat{\mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1 : K}).
\]

\end{proof}

The following lemma is used in the proof of our second main result concerning \emph{l.p.o.}\xspace risk estimation, see inequality~(\ref{eq:keyTheorem2fromLemma}). It is a generalization of  Markov inequality that is particularly useful for  cross-validation estimates. Our proof shares similarities with the proof of Theorem 4.1 in~\cite{kearns1999algorithmic} formulated under general algorithmic stability assumptions.
\begin{lemma}\label{"RCV-markov"}
In the setting of Theorem \ref{theo:main-sanity-rare}, we have
\[\PP(\widehat\risk_{\mathrm{CV},\alpha}(\Psi_{\alpha},V_{1 : K}) - \mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1 : K})  \geq t ) \leq
\ffrac{\EE(\mathrm{D_{t_\alpha}}+\mathrm{Bias}}%{C_{train}+\abs{ \hat\mathcal{R}_\alpha(\Psi_{\alpha}(S_n),S_n) - \mathcal{R}_\alpha(\Psi_{\alpha}(S_n)) })}{t}, \]
where  $\mathrm{Bias}}%{C_{train}$ (resp $\mathrm{D_{t_\alpha}}$) is defined by equation \ref{"bias_CV"} (resp \ref{"dev_ext"}).
\end{lemma}

\begin{proof}
Set
$$\widehat\risk_{\mathrm{CV},\alpha}=\widehat\risk_{\mathrm{CV},\alpha}(\Psi_{\alpha},V_{1 : K}),\quad \mathcal{R}_{CV,\alpha}=\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1 : K}) ,\quad  \hat\mathcal{R}_\alpha=\hat\mathcal{R}_\alpha(\Psi_{\alpha}(S_n),S_n), \quad \mathcal{R}_\alpha=\mathcal{R}_\alpha(\Psi_{\alpha}(S_n)).$$
 For any integrable real valued random variable $W$, and any $t>0$ write
  $\EE[W]= \PP[W\ge t]\EE[W \,|\, W\ge t] + \EE[W \un{W<t}]$. Reorganising, we obtain the following generalized Markov inequality,
  \[
    \PP[W>t] = \frac{\EE[W] - \EE[W \un{W<t}]}{\EE[W \,|\, W\ge t]}
    \le \frac{\EE(W) - \EE(W \un{W<t})}{t}.
  \]
  Letting $W = \widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha}$ we obtain
\begin{equation}
\label{"exp-CV-one"}
\PP(\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha}\geq t)= \frac{\EE(\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha})-\EE\left[(\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha}) \un{\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha} \leq t} \right]}{t}.
\end{equation}

Using the fact that $\EE(\tilde{\mathcal{R}}_{CV,\alpha}-\mathcal{R}_{CV,\alpha})=0$ and that $\mathrm{D_{t_\alpha}}=\abs{\widehat\risk_{\mathrm{CV},\alpha}-\tilde{\mathcal{R}}_{CV,\alpha}}$, one gets
\begin{align}
\EE(\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha})&=\EE(\widehat\risk_{\mathrm{CV},\alpha}-\tilde{\mathcal{R}}_{CV,\alpha}) \nonumber \\ &\leq \EE(\mathrm{D_{t_\alpha}}).
\label{"exp-CV-two"}
\end{align}
Now using lemma  \ref{"RCV-ge-RN"} write

\begin{align}
\EE\left[(\mathcal{R}_{CV,\alpha}-\widehat\risk_{\mathrm{CV},\alpha}) \mathbbm{1}_{\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha} \leq t} \right] &\leq \EE\left[(\mathcal{R}_{CV,\alpha}-\widehat\mathcal{R}_\alpha) \mathbbm{1}_{\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha} \leq t} \right] \nonumber \\ & \leq \EE\left[\abs{\mathcal{R}_{CV,\alpha}-\widehat\mathcal{R}_\alpha} \mathbbm{1}_{\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha} \leq t} \right]  \nonumber \\ &
\leq  \EE\left[\abs{\mathcal{R}_{CV,\alpha}-\widehat\mathcal{R}_\alpha} \right] \nonumber \\ &
\leq \EE\left[\abs{\mathcal{R}_{CV,\alpha}-\mathcal{R}_\alpha} \right]+ \EE\left[\abs{\mathcal{R}_\alpha-\widehat\mathcal{R}_\alpha} \right] \nonumber \\
&=\EE\left[\mathrm{Bias}}%{C_{train} \right]+ \EE\left[\abs{\mathcal{R}_\alpha-\widehat\mathcal{R}_\alpha} \right].
\label{"exp-CV-three"}
\end{align}

The last line follows from the definition of $\mathrm{Bias}}%{C_{train}$ in (\ref{"bias_CV"}). Combining inequality \eqref{"exp-CV-one"} with equations \eqref{"exp-CV-two"} and \eqref{"exp-CV-three"} yields
	\[\PP(\widehat\risk_{\mathrm{CV},\alpha}-\mathcal{R}_{CV,\alpha} \geq t ) \leq \ffrac{\EE(\mathrm{D_{t_\alpha}}+\mathrm{Bias}}%{C_{train}+\abs{\hat\mathcal{R}_\alpha- \mathcal{R}_{\alpha}})}{t}, \]
which concludes the proof.
\end{proof}

To conclude this section, we extend Theorem~10 in~\cite{goix15} bounding the supremum deviations of the empirical measure on low probability regions, to handle the case of any cost function $c$ absolutely bounded by one.
\begin{lemma}\label{lemma:inv-goix}
Recall the definitions of the risk $\mathcal{R}_\alpha$ and its empirical version $\ER_\alpha$ given in Section~\ref{sec:framework} and introduce the (random) supremum deviations
		\[Z'=\sup_{g \in \mathcal{G}}\lvert \widehat{\mathcal{R}}_{\alpha}(g,S_n)-\mathcal{R}_\alpha(g) \rvert.\]
If $\mathcal{G}$ is a family of classifiers with finite VC-dimension and $c$ a bounded cost function with $\sup_{g,o}|c(g,o)|\le 1$, then,  the following Bernstein-type  inequality holds,
	\[ \PP(Z'-Q(n,\alpha) \geq t)\leq 3\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right), \]
	where $Q(n,\alpha)=B(n,\alpha)+\ffrac{1}{n\alpha}$ and $B$ is defined by
        %

\begin{equation}\label{"V-n-def"}
  B(n,\alpha) = \ffrac{M\sqrt{\mathcal{V}_{\mathcal{G}}}}{\sqrt{\alpha n}}
\end{equation}
and $M$ is a universal constant.

\end{lemma}

\begin{proof}
	Write $Z' \leq Z_1 +Z_2$ with :
	\[Z_1=\sup_{g \in \mathcal{G}}\lvert \widehat{\mathcal{R}}_{\alpha}(g,S_n)-\Tilde{\mathcal{R}}_{\alpha}(g,S_n) \rvert,\]
	\[ Z_2=\sup_{g \in \mathcal{G}}\lvert\Tilde{\mathcal{R}}_{\alpha}(g,S_n)-\mathcal{R}_{\alpha}(g)\rvert.\]
Concerning $Z_2$, applying Corollary \ref{"RCV-sup-control"} with $K=1$ , $V_1=S_n$ yields
		\begin{equation}\label{ineq:Z-1-UB}
	\PP(Z_2 - B(n,\alpha) \geq t) \leq \exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right).
	\end{equation}
We now focus on $Z_1$. Define
$$u_{i}=\left|\un{\lVert X_{i}\rVert>\lVert X_{(\lfloor \alpha n \rfloor)}\rVert}
-\un{\lVert X_{i} \rVert \geq t_\alpha}\right|$$
and notice that $ Z_1\leq \ffrac{1}{n\alpha}\sum_{i=1}^{n}u_{i}$. It is known (see for instance the bound for the term $A$ in \cite{jalalzai2018binary}, page 12) that
\begin{equation*}
\ffrac{1}{n\alpha}\sum_{i=1}^{n}u_{i}\leq  \frac{1}{\alpha}\left|\frac{1}{n}\sum_{i= 1}^n \un{\lVert X\rVert \geq t_\alpha}-\alpha\right| + \frac{1}{n\alpha}.
\end{equation*}
Now,  by noticing that $\Var(\un} %[1]{\mathbbm{1}\left\{#1\right\}{\lVert X\rVert \geq t_\alpha}) \le \alpha$ and using Bernstein's inequality, we get
\begin{align*}
\PP\left(\bigg|\frac{1}{n}\sum_{i= 1}^n \un} %[1]{\mathbbm{1}\left\{#1\right\}{\lVert X\rVert \geq t_\alpha}-\alpha \bigg|\geq t\right)&\leq 2\exp\left(\ffrac{-n t^2}{2(\alpha+t/3)}\right)\\&\leq 2\exp\left(\ffrac{-n t^2}{2(4\alpha+t/3)}\right).
\end{align*}
Finally,\,dividing by $\alpha$, we get
\begin{align*}
\PP(\frac{1}{\alpha}&\bigg|\sum_{i= 1}^n \frac{1}{n}\un} %[1]{\mathbbm{1}\left\{#1\right\}{\lVert X\rVert \geq t_\alpha}-\alpha\bigg| \geq t)\leq 2\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right).
\end{align*}
Therefore we finally obtain
\begin{equation}\label{bound:z1}
\PP\left(  \ffrac{1}{n\alpha}\sum_{i=1}^{n}u_{i} - 1/n\alpha  \geq t \right) \leq  2\exp\left(\ffrac{-n\alpha t^2}{2(4+t/3)}\right).
\end{equation}
The result follows using $Z' \leq Z_1 + Z_2$ and $ Z_1\leq \ffrac{1}{n\alpha}\sum_{i=1}^{n}u_{i}$.

\end{proof}

\section{Introduction}
\label{sec:intro}
\input{introduction}

\section{Extreme values, extreme risk  and cross-validation: framework}\label{sec:framework}
\input{framework.tex}

\section{Exponential bounds for K-fold \textsc{CV}\xspace  estimates in rare regions}\label{sec:sanity-exponential}
\input{sanity-rare-Kfold}
\section{Polynomial bounds for \emph{l.p.o.}\xspace\textsc{CV}\xspace estimates in rare regions}
\label{sec:sanity-polynomial}
\input{sanity-rare-lpo}

\section{Intermediate results}\label{sec:intermediate-mainPaper}
\input{intermediate-mainpaper}

\subsection{Exponential bounds for cross-validation estimates in rare regions}

Our first main result Theorem~\ref{theo:main-sanity-rare} below holds true for any \textsc{CV}\xspace procedure under assumptions~\ref{assum:ERM-settings} -~\ref{assum:cost-func}. The leading term of the provided upper bound is $\mathcal{O}(\sqrt{\ffrac{\mathcal{V}_{\mathcal{G}}}{n_{V}\alpha}})$.\,In the case of the $K$-fold $\ffrac{1}{n_{V}} = \mathcal{O}(\ffrac{1}{n} )$.\,Thus,\,the bound of Theorem~\ref{theo:main-sanity-rare} becomes  $\mathcal{O}(\sqrt{\ffrac{\mathcal{V}_{\mathcal{G}} \log(1/\delta)}{n\alpha}})$.\,The latter bound is indeed  a sanity check bound as it matches (up to unknown multiplicative constants) the one relative to  the empirical risk conditional to a rare event established in \cite{jalalzai2018binary}, Th. 2, where $k=n\alpha$. Similar rates are obtained in an unsupervised framework \emph{e.g.} in \cite{goix15,drees2021principal,clemenccon2021concentration}. All these results match the asymptotic rate of convergence for tail empirical processes, see \emph{e.g.}~\cite{einmahl1988strong}.

 We shall use the notation $S_n=\{ 1,, \ldots n \}$ to refer to  the full index set. Hence, $\Psi_\alpha(S_n)$ denotes the algorithms trained on $\data_n$.

\begin{theorem}[Exponential \textsc{CV}\xspace bound for rare events]\label{theo:main-sanity-rare}
  Under assumption~\ref{assum:ERM-settings}, \ref{assum:mask-property}, \ref{assum:hypo-class}, \ref{assum:cost-func}, we have, with probability $1-15\delta$,
 \begin{align*}
   \bigg|\widehat{\mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-
   \mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\bigg|  \leq  E_{CV}(n_{T},n_{V},\alpha) + \frac{20}{3 n \alpha} \log(\frac{1}{\delta})   +  20\sqrt{\frac{2}{n\alpha} \log(\frac{1}{\delta})},
\end{align*}
where we put
\begin{align*}
E_{CV}(n_{T},n_{V},\alpha)=M\sqrt{\mathcal{V}_\mathcal{G}}(\frac{1}{\sqrt{n_{V}\alpha}}+\frac{4}{\sqrt{n_{T}\alpha}})+\ffrac{5}{n_{T}\alpha},
\end{align*}
for some universal constant $M >0$.
\end{theorem}

\begin{proof}[Sketch of the proof]
Introduce the pseudo-empirical risk
\begin{equation}\label{def:tilde-rcv}
	\Tilde{\mathcal{R}}_{\alpha}(g , S)=\frac{1}{\alpha n_S} \sum_{i\in S} c(g,O_i)\un} %[1]{\mathbbm{1}\left\{#1\right\}{\lVert X_{i}\rVert>t_\alpha }.
\end{equation}
Notice that when the distribution of $\lVert X \rVert$ is unknown,  $\Tilde{\mathcal{R}}_{\alpha}$ is not observable and only $\widehat{\mathcal{R}}_{\alpha}$ is a genuine statistic.\,However $ \Tilde{\mathcal{R}}_{\alpha}$ will serve as an intermediate quantity in the proofs. \\
Define the average `true' risk of the family $\big(\Psi_\alpha(T_j)\big)_{  0\leq j \leq K}$ by
\begin{equation}\label{eq:true-rcv-def}
	\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})=\frac{1}{K}\sum_{j=1}^{K}\mathcal{R}_{\alpha}( \Psi_{\alpha}(T_j))
\end{equation}
and the average  pseudo-empirical risk by
\begin{equation}\label{eq:pseudo-rcv-def}
	\Tilde{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})=\frac{1}{K}\sum_{j=1}^{K}\Tilde{\mathcal{R}}_{\alpha}(\Psi_{\alpha}(T_j),V_j).
\end{equation}

Using the previous quantities,\,write the following decomposition
\begin{align}\label{ineq:main-decomposition}
	\bigg|\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K}) -\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\bigg| \leq
	\mathrm{D_{t_\alpha}}+\mathrm{D_{cv}}+\mathrm{Bias}}%{C_{train},
\end{align}
with
\begin{align}
	&\mathrm{D_{t_\alpha}}=\abs{\widehat{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})- \Tilde{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})}\label{"dev_ext"},\\
	&\mathrm{D_{cv}}= \abs{\Tilde{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-  \mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})}\label{"dev_CV"}, \\
	&\mathrm{Bias}}%{C_{train}= \abs{\mathcal{R}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})-\mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)}. \label{"bias_CV"}
\end{align}
The remainder of the proof (see Section~\ref{sec:main-theo-proof}) consists in deriving upper bounds for each terms of the error decomposition~(\ref{ineq:main-decomposition}),  from which  the result follows.
The term $\mathrm{D_{t_\alpha}}$
measures the deviation between the cross validation estimator when
using the order statistics and the cross validation estimator when
using the `true' level $t_\alpha$, which can be bounded using Bernstein inequality, taking advantage of the small variance of the random indicator function $\un{\|X\| > t_\alpha}$.
The term $\mathrm{D_{cv}}$ measures the
deviations of
$\Tilde{ \mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K})$ from its
mean. It is controlled by a uniform bound (over the class $\mathcal{G}$) on the deviations of the empirical risk evaluated on the validation sample. To do so we follow standard arguments leading to a bound on such deviations on low probability regions (as \emph{e.g.} in \cite{goix15,jalalzai2018binary}). Finally the term
$\mathrm{Bias}}%{C_{train}$ is the bias of the cross validation
procedure, the control of  which relies on the specific nature (ERM) of the considered learning algorithm. Indeed in this context the bias may be upper bounded in terms of the supremum deviations of the empirical risk evaluated on the training sets $T_j$.
\end{proof}

Theorem \ref{theo:main-sanity-rare} can be used  to obtain exponential bounds for the $K$-fold \textsc{CV}\xspace estimate. From Lemma~\ref{"train-test-cond"},
Assumption~\ref{assum:mask-property} regarding the sequence of masks $V_{1:K}$ holds true for the K-fold \textsc{CV}\xspace procedure. Consequently Theorem~\ref{theo:main-sanity-rare} applies  with $n_{V}=n/K$ and $n_{T}=n-n_{V}=\ffrac{K-1}{K}n$.
In the following corollary, $V_{1:K}^{\textrm{K-fold}}$ denote the sequence of masks associated to $K$-fold

\begin{corollary}\label{coro:K-fold-sanity-check}
	Under the assumptions of Theorem~\ref{theo:main-sanity-rare}, the $K$-fold (with $K\geq 2$) \textsc{CV}\xspace estimate for the conditional risk (\ref{eq:def-risk-extreme}) satisfies with probability $1-15\delta$,
	\begin{align*}
          \bigg|\widehat{\mathcal{R}}_{CV,\alpha}(\Psi_{\alpha},V_{1:K}^\textrm{K-fold})-
          \mathcal{R}_{\alpha}\big(\Psi_{\alpha}(S_n)\big)\bigg|  \leq  E_{\textrm{K-fold}}(n,K,\alpha)
          + \frac{20}{3 n \alpha} \log(\frac{1}{\delta})   +  20\sqrt{\frac{2}{n\alpha} \log(\frac{1}{\delta})},
	\end{align*}
	with, for some universal constant $M >0$,
	\begin{align*}
	E_{\textrm{K-fold}}(n,K,\alpha)=5M\sqrt{\frac{\mathcal{V}_\mathcal{G}K}{n\alpha}}  +\ffrac{5K}{(K-1)n\alpha}.
	\end{align*}
\end{corollary}

	Despite the satisfactory
sanity check bound obtained thus far for the $K$-fold (Corollary~\ref{coro:K-fold-sanity-check}), note that the term
$\mathcal{O}(\sqrt{\ffrac{\mathcal{V}_\mathcal{G}}{n_{V}\alpha}})$ in the upper bound of Theorem~\ref{theo:main-sanity-rare}  does not even
converge to $0$ in the \emph{l.p.o.}\xspace setting because the size $n_V$ of the
validation set remains constant, equal to $p$.\,Thus, Theorem~\ref{theo:main-sanity-rare} is not adapted to the latter type of \textsc{CV}\xspace
schemes. In the next section we obtain
(Theorem~\ref{theo:main-sanity-rare-lpo}) an alternative upper bound
involving only the size $n_T$ of the training set which allows to cover the \emph{l.p.o.}\xspace case.

redpajama_set_name: RedPajamaArXiv


Are you new to Amazon Prime Music and wondering what it has to offer. The FAQs below will answer the questions on your mind and guide you on how to get the best out of Amazon Prime Music.
Is Amazon Prime Music and Amazon MP3 the same?
You might be wondering if Amazon Prime Music has something to do with the company's successful music download service, Amazon MP3. The answer is No. Amazon Prime Music is a separate entity that allows you to stream songs from the cloud rather than download digital music files as you would using Amazon's MP3 store.
No, it isn't. It comes as part of the Amazon Prime membership. Other competing streaming music services like Spotify offer a free ad-supported account, but the only way to get Prime Music is to either subscribe to Amazon Prime, Amazon Mom, or Amazon Student memberships.
However, you can test drive the streaming music service for free if you take out a 30-day trial of Amazon Prime or Amazon Mom. This way you can at least see if it's worth the membership (along with the other benefits you'll get) before paying for a subscription.
What Does Amazon Prime Music Offer?
Prime Music offers a collection of songs and albums which can be streamed to a computer (PC / Mac) and a wide variety of mobile devices. As you might expect, the music is free from advertisements and can be streamed without limits.
The service has a relatively small library of songs and albums compared to other established streaming music services such as Spotify and Beats Music. However, as previously mentioned it comes free with an Amazon Prime subscription — so, if you are already a Prime member, then along with unlimited movies, TV shows, and Kindle books, you've basically got access to a streaming music service at no extra cost.
As well as being able to pick songs and albums there are also professionally curated playlists. These are compilations of songs that fit into familiar themes — genre, artist, etc. You can also add songs that you've discovered while browsing Amazon's library to your own custom playlists.
Currently the Amazon Prime Music service is available in just two countries — the United States and Puerto Rico.
This number is expected to change in the future (as was the case when Amazon MP3 first launched).
What Are The Different Ways I Can Listen to Music on Amazon Prime Music?
Smartphones / Tablets There are apps that you can download for Android (version 4.0+) and iOS (6 or higher).
Yes. Amazon Prime Music has an offline mode that enables you to download songs to your mobile device. This content is stored locally (for use solely within the app) so you can listen without needing an Internet connection. This option may not work on desktop computers.


We are RC Ltd. We offer one off fee collection of rubbish for and Property Management companies in and around Epping Upland and Ugley Green. People use us because you can receive telephone estimates. Services offered include 'quick-clean garden rubbish clearance' and 'Full Tipper domestic rubbish clearance'. Read more on domestic rubbish clearance company.
We know you are are searching for a responsible and accountable Essex based man and van that can dispose of your waste reponsibly? Rubbish Clearance Ltd can help. We are fully insured and licensed.
Looking for a low-priced price for collection of rubbish or green waste removal? Whether you are in a shop or office we can help all local people in Epping Upland. We are a established The rubbish company based in Essex. We do all the loading and clearing up so you don't have to. Whatever amount of rubbish you have, our two man teams can safely collect and dispose of it. Stuff that we dispose of include pass it sofas, sinks, greenhouses and photocopiers.
We collect and remove of all your paper and cardboard boxes, , broken tumble dryers, fridges, loads of bricks, freezers or concrete safely without mess from anywhere in Essex CM16.
Proven commercial waste removal We load and clear your junk.
cheaper waste man and van hire BAR Approved.
Want removal rubbish Recycling Experts.
telephone for alternative to garden skip hire BAR Approved.
low-cost business waste collection We load and clear your junk.
garden waste removal Recycling Experts.


text:
Model train show packs Finch
Sun photograph by LISA YANICK-JONAITIS Miriam Brinks, 4, and her mother Annica Brinks watch a display at the Mid-Michigan Model Train Show and Flea Market at Central Michigan University Sunday.
PUBLISHED: March 30, 2009 at 3:48 a.m. | UPDATED: June 17, 2021 at 8:27 a.m.
Miriam Brinks fell in love with trains at the tender age of 2.
Now, at 4 years old, Miriam was in awe at the Mid Michigan Model Train Show and Flea Market, held Sunday at Central Michigan University's Finch Fieldhouse.
"They are beautiful," Miriam said while watching a model steam engine making a loop around a track. "I want to touch them but my mom and dad say 'no.'"
Mom and dad, Annica and David Brinks of Shepherd, were also enchanted by the displays at the show, which was sponsored by Dog Tales, Inc. and Clare Depot Preservation, which will get proceeds from ticket sales at the show.
"I love it," Miriam said of the display set up by Michigan Small Scale Live Steamers, a club that formed about seven or eight years ago that has been at the show the past three years.
Fred Gandolfi of Houghton Lake said the group wants to get the word out about live steam model trains.
Unlike most model trains, which run on electricity or batteries, MSSLS trains are powered by either alcohol, butane or coal.
Those power sources heat water in the train engines to push the pistons, making the trains move.
"A lot of people walk up and they don't have any idea what's going on until somebody tells them," Gandolfi said. "Then they're just shocked."
People who discover model steam trains at the local show can go to the club's Website, www.mssls.info, to find out where they can purchase the trains and learn more about the hobby, Gandolfi said.
Those who are interested can also get information on how to join the club on the site, he said.
Intended for live steam model train enthusiasts, the club went from having just seven or eight members to 30, Gandolfi said.
"The live steam community was very small," he said, adding that the club has members from as far south as Monticello, Ill. "We promote live steam railroading."
Among the club's display at the show on Sunday was a Baltimore and Ohio engine that uses a battery only for the headlight.
Model steam trains run just like real steam engines, with active, live boilers, Gandolfi said.
Getting into model steam trains can be a bit on the pricy side as well, he said.
To get into the hobby, the base price for an engine is about $350, Gandolfi said.
"From there, the sky's the limit," he said.
An Allegheny engine costs $25,000, Gandolfi said.
When Gandolfi first got into the hobby 16 or 17 years ago, his first steam engine left a bit to be desired.
He still has the Mamod engine, "the cheapest thing on wheels."
"It was terrible," he said.
Still, after the engine stopped running and had sat idle for 10 years, Gandolfi spent three days working on it, and now it runs again.
Having displayed model steam trains at the local show for three years, the group likes participating in charity events; Gandolfi was pleased that Dog Tales and Clare Depot Preservation will benefit from this year's event.
Discovery Museum to host Bowties & Bourbon Gala
Alanis Morissette musical coming to Lansing
Local LARP group encourages participants to play in a fantasy world

redpajama_set_name: RedPajamaCommonCrawl


text:
Where have all the health attachés gone?
Geoff Berridge 14 Jul 2020 Diplo Blog, Diplomacy
An influential article of 2014 noted that health attachés were appointed shortly after the Second World War and were thereafter assigned by 'a growing number of countries [...] to work in embassies in countries of strategic importance'. Is this true? If not, why not? And does it matter anyway?
Because of the sparsity of published diplomatic service lists in recent years, it is not at all easy to make even a rough guess at the number of health attachés extant. Making the task more difficult is the fact that (capital city) diplomatic lists, which are more readily available online, are not always on one page. Old-style, one-page lists, like the Swedish Diplomatic List, require only one search for 'health', but others provide separate pages for each state's mission staff, as in the case of New Zealand, and these demand a search of every individual mission's staff. Nevertheless, a random search of the position of a few states where some evidence is easily available at least enables an impression to be formed of the current position, which is not good.
In the first decade of the new millennium there was a growing fear in medical circles that pandemics were likely to grow in number and intensity; this was due, among other things, to increased global travel. The SARS pandemic of 2003 had sounded a particular alarm. But despite the fact that this was followed by a flu pandemic in 2009, two years later only four countries with missions in the United States of America had diplomatic officers with full-time health responsibilities (two attachés and two counsellors); and in 2014 (the year of the Ebola epidemic), the USA itself had only eight full-time health attachés posted abroad – five by the Department of Health and Human Services (HHS), two by the Pentagon, and one by USAID. Moreover, none had embassy sections of their own, but found themselves part of others, typically economic/commercial, science and technology – or even political sections. On its current website page on health attachés, last updated six months before the 2016 US presidential election, HHS reported that by then it had six: in Brazil, China, India, Mexico, South Africa, and at the US Mission to the UN in Geneva. As for the UK, it probably has no health attachés at all, because while a search of its website brings up 235 hits for 'defence attaché', it brings up only one result for 'health attaché', and not a British one. As for embassies in London, according to its old-style diplomatic list for May 2020, only those of Canada, Iraq, Kuwait, Oman, Qatar, Saudi Arabia, and the United Arab Emirates currently have health or 'medical' attachés. Furthermore, most of these are probably only concerned with ministering to the personal health needs of their citizens resident in, or visiting the UK, than with global health diplomacy. This is certainly the case of Qatar, and it is something of a giveaway that the office of the UAE's medical attaché is in Harley Street, famous for its high class, private specialist clinics. The Swedish diplomatic list reveals no health attachés posted in Stockholm at the moment; likewise the Czech list à propos Prague. By way of a footnote to this paragraph, I can find no reference to Morris B Sanders, the 'Public Health Attaché' said to have been appointed to Brussels, Paris, and The Hague in or around 1948 in any US Foreign Service List between 1945 and 1950.
There are practical reasons for the scarcity of genuine health attachés in the world's embassies. Chief among these, it seems, is the absence of a clear career pathway, which makes the position unattractive to many of those otherwise well qualified – and in high demand elsewhere, especially during a pandemic like the present one. It seems likely, however, that their scarcity is also a result of the complacency of too many governments – especially of the populist variety – towards the threat of pandemics, their preoccupation with nationalist agendas, and their tendency to discount diplomacy in general.
If it is indeed true that health attachés are very thin on the ground, does it matter? Embassies got some bad headlines during the first weeks of the COVID-19 pandemic, chiefly for the mixed response of their consular sections and satellite consulates to the huge numbers of citizens abroad desperate to get home. But health attachés would presumably have been of little use in such circumstances. However, they are surely a valuable conduit for advice to an embassy's economic and/or commercial section urgently seeking a reliable source of medical equipment; and there were lamentable failures in such searches during the first, panicky weeks of the COVID-19 crisis. And in the critical matter of discovering viable anti-virals, and above all, a vaccine for COVID-19, health attachés provide embassies with the ability to promote co-operation on the part of medical scientists and public health experts in relationships where international professional networks are weaker and more fragile. They are also needed to oversee any local health project sponsored by a sending state, support the negotiation and monitoring of bilateral health accords (as in the case of the first Sino-US memorandum), report on local health conditions, and so on. It is significant that in the case of the USA, at any rate, its embassies are repeatedly asking for more health attachés than Washington can provide.
The weak response of many embassies to the demands made on them during the first weeks of the COVID-19 crisis are readily explained by the health precautions required of embassy staff and the impediments to their work caused by local lockdowns and curfews. But a less obvious contributing factor might well have been that health attachés in embassy ranks have almost certainly not grown significantly in numbers since the late 1940s and remain far too few. Some serious research on this subject needs to be done urgently.
This post first appeared on the personal blog of Prof. GR Berridge and is republished here with permission.
Discussion topic
What is the top priority for health attachés?
Join the discussion in the comments below!
Tags:PublicDiplomacy, HealthDiplomacy, COVID-19, Diplomats, Diplomacy, WisdomCircle
You may use [view:name=display=args] tags to display views.
Data Reflections
E-Diplomacy
Bulgarian Diplomatic Institute recognises DiploFoundation's contribution to Institute's work
Prof. Jovan Kurbalija awarded honour by the Republic of Malta
#CyberMediation Conference brings together stakeholders involved in mediation
[WebDebate #47 summary] Current diplomatic responses to COVID-19
'Deplatforming' Donald Trump was a necessary quick fix. What now?
Beyond partnership and participation: Community organising for ownership in humanitarian diplomacy and aid
6K Fans
800+ Videos
15K+ Photos
Follow Like Watch Browse
Subscribe to Diplo's Blog.


text:
The pulse of immigrant Canada
Boots Riley and Robyn Maynard at Knox United Church. Everyone admires white people around the world – but not as much as they admire themselves.
Arts & Culture Top Stories
Sorry to Bother You — With My Accent
Written and directed by Boots Riley, "Sorry to Bother You" is a futuristic, humorous, damningly anti-capitalist film. It was Riley's entrée to film direction. Though…
Ashoke Dasgupta May 18, 2019	No Comments
Written and directed by Boots Riley, "Sorry to Bother You" is a futuristic, humorous, damningly anti-capitalist film. It was Riley's entrée to film direction.
Though it could have been shorter, the film succeeds on many levels such as characters, costumes, scenes, and message. Screened at Winnipeg's "Cinematheque" May 10, it stars Lakeith Stanfield, Tessa Thompson, Jermaine Fowler, Armie Hammer, Omari Hardwick, Terry Crews, Danny Glover, and Steven Yeun. An audience of say 63 packed the auditorium. It's the story of a young black telemarketer, Cassius Green (Stanfield) who adopts a white accent to succeed. Patton Oswalt and David Cross, both white men, provide Green's "white voice."
A black police officer pulls a similar trick to infiltrate the Ku Klux Klan in "The Black Klansman."
Sucked into a corporate conspiracy by his sudden and meteoric success, Green is faced with a choice: personal gain, or the pull of his activist friends organizing against management. "Sorry to Bother You" premiered at the Sundance Film Festival in 2018, and was released in the USA by Annapurna Pictures. Its cast and concept, as well as Riley's screenplay and direction, are excellent.
A poster for the film "Sorry to Bother You."
Watching the film, reminded this reviewer of a call centre he once worked in, where he was trained by a bespectacled, obese Indian woman in her late forties who had developed an incredible, even comical, youthful American accent. The company covertly suggested, by using this trainer, that coloured trainees should follow her leadership by example. It was a practical suggestion since one caller told this reviewer she wanted to speak to "an English person with an English name and accent." When the call centre manager, a white woman, was requested to take action against this blatant racism she ejaculated, "Who's got the time?" Your reviewer was eventually fired, possibly for hanging up on a caller who abused him.
The film may resonate with educated immigrants who often have a "Miracle on 34th Street" experience. Instead of trying to convince people they are Santa Claus, they have to convince the locals they are executives, journalists, teachers, and so on.
Changing technology and times have rendered the film industry over-dependent on photographic gimmicks, but "Sorry to Bother You" is free of cinematographic guile. The only exception may be the cinematic crashing of the hero, Cassius Green, desk and all, into the households he telephones, to underscore the awkwardness of the intrusion caused by gatecrashing them.
The visual effects are well-chosen parts of a seamless experience. The narrative is helped by the smooth flow of the film from scene to scene. The gatecrashing metaphor is used again when mutant labourers crash through the big boss's gates at the end of the film.
The background music, played by Riley's band, works with the scenes.
Cassius Green was a ditzy dolt living in his uncle's garage when he went for an interview with a shady telemarketing firm called RegalView. The lies he tells at the interview are caught out by his interviewer, who hires our hero all the same.
Lakeith Stanfield as Cassius Green.
The film makes a deep racial and sociological impact since statistical disparities show racial inequality remains a problem. Careful analyses of lending practices, hiring patterns and law enforcement reveal systemic biases in North America accompanied by trauma for the coloured.
History reveals that, like the USA, Canada is a country based on the genocide of indigenous peoples. Along with the calculated recruitment of white English and other European peoples to create a specifically white populace with its cultural traditions. The USA was also built on slavery.
One of these nations' great myths is that they have a long history of welcoming refugees and dissidents, and of accepting the world's oppressed and dispossessed.
The white population's complex hangover from its past casts a giant shadow over the present, resulting in the realities presented by the film's call centre.
The truth is that America was England's (and Europe's) sewer to empty its prisons and brothels, remove beggars and vagrants, and rid London of the blighters of its population, who were to die in the process of serving English interests. They were the "fertilizer" or "manure" sent to develop rough lands for their betters to arrive later.
The white population's complex hangover from its past casts a giant shadow over the present, resulting in the realities presented by the film's call centre. The "white" accent is consequently far from neutral or value-free.
In the end, "Sorry to Bother You" is about how vanity, good fortune, and the almighty dollar degrade us under capitalism. About how capitalism can make coloured people sell out, sacrifice their identity, morality and principles.
The film's power lies in its original exposure of the ethical issues triggered by capitalism in general and the adoption of a phoney accent in particular. The artifice of adopting a "white" accent is also demeaning when done to earn a living by concealing who one really is over the phone.
A Night at Knox United
On May 11, the Canadian Centre for Policy Alternatives presented a talk by Boots Riley, emceed by Robyn Maynard at the Knox United Church. It was attended by about 400.
Riley recited a long poem to start with. "The left has run away from class struggle in the USA," he said, calling for workplace organizing to thwart capitalist exploitation. He described some strikes involving armed battles with state militia in the USA. "The left has disconnected from the actual movement against how powers are working. Art and books are important but this disconnect from radical action is deplorable.
"The bases for exploitation and oppression are part of our current culture," Riley asserted. "Culture is merely what comes out of how we survive. Agricultural songs are not sung much in fishing villages," he said. "We have a system that deals with the exploitation of labour, capitalism can never offer full employment. It needs unemployment. A reserve army of the unemployed is necessary to maintain pressure on the employed.
"The unemployed will get involved in illegal business, as they should, because they have to eat. This leads to violence, as does all business.
"Culture is merely what comes out of how we survive."
"The biggest section of the working class are white … it's ingrained in them to look at those lazy 'others.' Racist tropes about the coloured have utility for them. People want a revolution to ring out capitalism but they need a job … The Rockefellers wrote foundations must be created to ensure radical movements don't get revolutionary.
"Millions demonstrated on streets around the world against the Iraq war, but couldn't stop it. That's not the nature of power. Elected leaders are just the puppets of power. Solidarity strikes were outlawed in the US because they worked.
"Some formed unions after seeing my film. Some business models depend on there being no unions," Riley said. This was corroborated by Telespectrum Worldwide, a call centre that folded in Winnipeg about 19 years ago because it ceased to be profitable after unionization.
Ashoke Dasgupta
Website | + posts
Ashoke Dasgupta is a freelance journalist and former editor of Compassionate Friend, Beauty Without Cruelty-India's magazine. He won a UNDP - Goethe Institute Award for Environmental Journalism in Nepal 1995, and the Canadian Ethnic Media Association's Best News/Feature Awards for 2004 and 2006. He got a scholarship to study journalism at Sheridan College Toronto in 2007, graduating with high honours. He has done internships at the Winnipeg Free Press and CBC Radio, and been published in the Winnipeg Free Press, the Calgary Herald and the Toronto Star.
https://newcanadianmedia.ca/author/ashoked/
Trump Dims the Lights in Jerusalem
Cathy Wong's Fear of a Bus Driver
No Apology For Heroism: Linda Sarsour
Raptors' NBA Championship Unites Newcomers with Mainstream Canadians Visible Minorities Keen to Engage Online Despite Untruths FROM LIFE TO CANVAS: Brampton Artist Paints Vivid Journey of Hope & Struggle Long Before Don Cherry, Race in the Rink was part of Canada's Hockey History
Armie HammerBoots RileyCinemathequeDanny GloverfilmmakerJermaine FowlerLakeith StanfieldOmari HardwickSorry to Bother YouSteven YeunSundance Film FestivalTerry CrewsTessa ThompsonWinnipeg
Previous Previous post: Sorry to Bother You – With My Accent
Next Next post: Thoughts on the Current State of America
NCM Journalism Series
Why Won't Canada Help Me Get My Mother's Killers? January 16, 2020
India's Slow March to Becoming a "Hindu Nation" December 23, 2019
books (57) British Columbia (51) Canada (149) Canada 150 (45) CHINA (54) Chinese (53) Citizenship (54) Conservatives (86) diversity (88) EDUCATION (52) ethnic media (48) Federal Election (109) federal elections (77) history (40) human rights (38) immigrant (69) immigrants (105) Immigration (153) iPolitics (65) ISIS (40) Islam (38) Justin Trudeau (58) Liberals (95) media (50) Multiculturalism (60) Muslim (53) Muslims (42) NCM Election Desk (64) NDP (42) Newcomers (78) Ontario (79) Ottawa (106) POLITICS (41) Quebec (55) racism (63) refugee (69) refugees (101) Stephen Harper (50) Syria (98) Syrian refugees (48) terrorism (56) Toronto (130) Trudeau (38) Vancouver (105) women (45)
New Canadian MediaFollow
We're a pioneering nonprofit, independent newsroom that offers an immigrant perspective on Canadian current affairs.
Retweet on TwitterNew Canadian Media Retweeted
Shabana Ansari@shabansa·
How do you deal with being "different" or "not fitting in"? Our differences are our superpowers, says @CeceBellBooks in her heartwarming book El Deafo in which her hearing impaired heroine thinks of herself as having superpowers no one else has! #ReadMoreDiverseBooksChallenge2020
New Canadian Media@NewCdnMedia·
Welcome news. Thank you for always making time for us: as writer, mentor, editor, trainer ...
Amira Elghawaby@AmiraElghawaby
I've been writing opeds since 3rd year j-school. My first national piece 11 years ago was about the need for Canadian Muslims to recount their stories.
Deeply humbled to share that I will now be writing a bimonthly column exploring human rights for the @TorontoStar
#cdnmedia
I have seen swift and decisive RCMP action in many other cases involving Canadians killed in Mexico, the U.S. and Europe.
But when it comes to Indo-Canadians being killed in India, there seems to be a different standard.
This is my mother's story:
https://newcanadianmedia.ca/why-wont-canada-help-me-get-my-mothers-killers/
Archives Select Month January 2020 (3) December 2019 (7) November 2019 (10) October 2019 (18) September 2019 (17) August 2019 (11) July 2019 (8) June 2019 (11) May 2019 (18) April 2019 (9) March 2019 (14) February 2019 (1) January 2019 (2) December 2018 (1) November 2018 (1) October 2018 (2) June 2018 (2) April 2018 (5) March 2018 (11) February 2018 (10) January 2018 (12) December 2017 (5) November 2017 (9) October 2017 (8) September 2017 (20) August 2017 (14) July 2017 (13) June 2017 (10) May 2017 (16) April 2017 (11) March 2017 (19) February 2017 (12) January 2017 (9) December 2016 (9) November 2016 (17) October 2016 (17) September 2016 (16) August 2016 (22) July 2016 (26) June 2016 (27) May 2016 (26) April 2016 (27) March 2016 (44) February 2016 (37) January 2016 (37) December 2015 (47) November 2015 (51) October 2015 (70) September 2015 (65) August 2015 (54) July 2015 (36) June 2015 (45) May 2015 (50) April 2015 (49) March 2015 (40) February 2015 (32) January 2015 (10) December 2014 (12) November 2014 (16) October 2014 (17) September 2014 (17) August 2014 (21) July 2014 (22) June 2014 (16) May 2014 (11) April 2014 (11) March 2014 (13) February 2014 (28) January 2014 (9) November 2013 (12) October 2013 (12) September 2013 (3) August 2013 (2) July 2013 (12) June 2013 (8) May 2013 (9) April 2013 (10) March 2013 (11) February 2013 (11) January 2013 (10) December 2012 (7) November 2012 (4) October 2012 (14)
Syndicate our stories on your site
Subscribe to Site via Email
ETHNIC MEDIA & DIVERSITY STYLE GUIDE
Have a great idea about a story, or a tip? We'd love to hear from you. Email: admin@newcanadianmedia.ca
763 BEAUREGARD CRESCENT, OTTAWA, ON, K4A 3C7, Canada
New Canadian Media provides nonpartisan news and views representing all Canadian immigrant communities. The views expressed on this site are those of the individual writers and commentators, and not necessarily those of New Canadian Media. New Canadian Media is a member of the National NewsMedia Council, a voluntary self-regulatory organization that deals with ethical and journalistic practices in gathering and reporting the news. Visit mediacouncil.ca or call 1-844-877-1163 for more information.


W.O. Bentley introduced the new 6½ liter model in October 1925 at the Olympia Motor Exhibition. The straight six engine powering the vehicle actually displaced 6597cc and the chassis was very similar to the earlier Bentley's, though the braking had been enhanced to cope with the extra power. There was also a more substantial differential and a plate clutch. This new model would be the basis for the company's future campaigns at Le Mans up to 1930 when they retired from racing.
Chassis number BX 2421 has a documented history from new. The original owner was E. Bullivant of Mortimer House, Egerton Gardens. The vehicle carried a guarantee date of March 1927, and was fitted with the later pattern push-on brakes and a 26 gallon tank, features which would only become standard the following year. It had a long steering column and a 3 liter exhaust fishtail. The Sports Tourer coachwork was crafted by Vanden Plas. The body was paneled rather than fabric and it was designed with an armrest for the driver. There were side lockers, a trunk at its rear and a double spare wheel carrier. Full weather protection was required and it had pockets to all the doors. Accessories included Zeiss headlamps. The total cost of the body alone was nearly twice that of a standard Vanden Plas body.
During Bullivant's first year of ownership, the car was upgrade with a new radiator and crankshaft driven dynamo, camshaft damper and 'new type carb.' In 1929, the car was traded at Jack Barclay for a newer model. the next owner was R. Winloe who kept the car maintained by the factory, and continued updates with high speed oil pump gears, a sprung steering wheel, rear hydraulic shock absorbers to the rear and a Spicer shaft, as well as converting it to a C type 'box with the help of Birkin & Coupers of Welwyn.
In 1936, it was purchased by C. Burrage-Moulton. By 1988, it had gone through 10 different owners and was now in the care of C. Pettit. In this period it carburetion was uprated with the fitment of early Speed Six pattern twin SU units. A short time later, the car was offered for sale at auction by Bonhams. Ownership passed to a private British collection, emerging recently for it sale.
In 2011, it returned to a Bonhams auction, this time at the Quail Lodge in California. It would leave the auction unsold after bidding failed to satisfy the vehicle's reserve.


He draws on the most current ideas and theories on the topic of effective leadership, incorporates case examples of large scale transformation, and reveals a remarkable convergence of powerful themes or, as he calls them, the five core competencies.
By integrating the five core competencies:attending to a broader moral purpose, keeping on top of the change process, cultivating relationships, sharing knowledge, and setting a vision and context for creating coherence in organizations, leaders will be empowered to deal with complex change. They will be transformed into exceptional leaders who consistently mobilize their compatriots to do important and difficult work under conditions of constant change.


Every once in a while, we need a solution to either pay money or receive money either commercially or personally for services. Whether its income generated from affiliate sales or receiving money for digital products & services, it is truly important to have a payment service faster than Checks. Since we've abundantly faced this problem & solved it for ourselves, we decided to share our knowledge.
How do Alternative Payment Solutions Work?
We call solutions that step away from wallets as alternative payment solutions. There are many of them out there and some truly amazing and versatile than the likes of PayPal. These payment solutions allow you to send and receive money from individuals and businesses. So for instance, you can get paid directly into your account held by the payment solution provider and you can withdraw funds directly in to your bank account or head to a nearby ATM for cash withdrawal in your currency.
We have put together a handy guide for alternative payment solutions as well as a money transfer service that disrupt the traditional model and allow you to easily get paid for services & physical products.
Below are some of the alternative solutions to PayPal and even Prepaid Cards.
TransferWise has disrupted the traditional bank transfer model and moved £1 billion transparently in 2014. They are here in the list since they give you borderless accounts in multiple currencies. Some of these currencies have their own bank accounts which act like regular bank accounts (with some limitations) This means that you can move funds from one foreign currency account to another without incurring crazy fees. When the time comes to withdraw or pay someone, you can do it directly from your TransferWise account. They save you over 85% of transfer fees when transferring money abroad. Transferring money is simple and fast. You simply register your account and choose the amount you want to transfer and where you want to transfer to. Pay in your local currency which is equal to the mid-market rate of the day. TransferWise then matches your transfer amount to those being transferred from your target location and both funds are settled locally into accounts. Yep for those already familiar with the system, this is the Hawala system used widely in Asia (off books).
Their pricing system is straightforward too and usually amounts to either 0.5% or 1% of fees, unless USD and SWIFT payments are involved. Even then their exchange rate alone makes up for the waiting time involved for SWIFT payments. Oh, you can use our registration link to send up to £200 for FREE (this applies to your first transfer only) to anyone whether it's for commercial or personal purposes. They support a number of currencies including AUD, INR. PHP, PKR etc.
Read our full review of Transferwise here.
This is a rather unique service that allows its customers to make global payments (online) and also receive them. They have solutions for not just Small businesses but also freelancers. Payoneer has mass payout services such as prepaid debit MasterCard card, local bank transfers, branded debit cards (for companies) and a Payment Service for USD, GBP, EUR, AUD, JPY and CNH/CNY currencies.
Once you sign up with Payoneer and get verified, you get your own bank account in each of the currencies held in that country. There are restrictions of course. The account can only be used for payments being sent to you from companies and in the case of EUR account; from SEPA member countries only. The service is truly global and caters to companies and individuals from over 200 countries. There are some limitations to withdrawals for local bank accounts, however, the Payoneer card can be used to withdraw funds globally anywhere MasterCard is accepted. Another very good point in Payoneer's favour is their fees. They are better than many service providers when it comes to FX rates and much cheaper than PayPal; making them a far better payment solution for processing international payments.
Payoneer also supports Escrow services so you can easily bill clients and take money into your escrow account knowing that your money is securely held and will be paid to you when work is complete / services are delivered. You can read the full review of Payoneer services here.
*If you sign up via the links in this post you get $50 credit once you receive the first $1000 into your Payoneer card/account in the first year.
This is used widely in Russia and its surrounding countries. They support a wide variety of services via purses which include, payments, withdrawals, entering into legal agreements, crowdfunding, fundraising and escrow services to name a few. For each transaction, they charge 0.8% of the payment amount though there are maximum fees set for each sort of transaction. They deal in Euro, US Dollars and Russian Rubles. Here's a list of WebMoney's top-up & withdrawal methods. You can see their country coverage here.
Payza is another wallet combined with a payment solution that spans over 190 countries and 21 currencies. Payza provides both personal and business services in most locations. They allow you to upload funds via Bitcoin (free) Bank Wire and Credit Card though, a fee applies in most cases. You can check their fee table and weigh the pros and cons of the service according to your location and requirements.
This is another innovative service that offers withdrawals in WebMoney and Payza accounts in addition to local bank transfers. Paysera is also cheaper than Western Union and MoneyGram where currency conversion is required. Paysera has many pricing tiers which may be a tad confusing at times. Luckily, sign up is free hence one can always signup and see what services are offered through the system and at the time of money transfer decide which one offers the best rate with speed of transfer.
With a global presence in 200 countries spread across all continents and 500,000 agent locations, Western Union provides low cost cash and bank transfers globally. Its a top choice where people want to send personal funds to their family back home. Unlike some of the other services mentioned here, WU is purely a remittance / money transfer service where people in developed countries send money abroad to those in developing countries. Their charges are nominal and their transfers within hours instead of days making it a great choice for low cost transfers.
Use our links to send free transfers to Europe and /or £500 worth of transfer for £2.90 only.
Skrill has come a long way from the days when it was unknown. Though still not as widely used as PayPal, there are many services that accept money & do payouts via Skrill. They are primarily a digital wallet, with the option to load wallet via multiple methods and withdraw funds to local accounts. Their digital wallet solution is available in over 200 countries and those looking for an online payment solution should definitely check out their business site. For personal products, you can take a look at their fee structure, currency and country support at their Skrill Fees page. Having used their service quite extensively, we can attest that uploads & withdrawals to bank accounts globally are fairly quick. All they need is to expand the Skrill prepaid debit card outside of European Union.
So that's a wrap on some very interesting money transfer and global payment solution services. What do you think of the above? Have we missed out on any that are acceptable worldwide? Please let us know in the comments.
If you think you just need a virtual prepaid VISA card, please read our listicle on the link. Another list of VISA gift cards can be seen on our feature covering Gift Cards. If you have trouble with address and phone number, I suggest you get a package forwarding address for that country and inserting it at checkout point.
Payoneer is truly the best solution for sending & receiving Payments online. I have been using Payoneer & love the service they offer.
After overall, I have written an extensive article on Payoneer.
I have faced many problems about money transfer. I have read this article for money transfer, my problem becomes solve.Thanks for sharing this helpful article.About a week ago, i send money through moneygram and i enjoyed 10% off on my first transaction.
Hi Jessica, glad the article helped. It will be updated again very soon with some nifty new services we've tested. Stay tuned.
Havent tested moneygram personally, however i know of someone who sent money via Western Union to UK. This was 5 years ago. Perhaps visit Western Union and find out? Let us know here.


text:
Tag: paranormal
"Well, Wendy said something about a shadow…"
Cast No Shadow by Nick Tapalansky and Anissa Espinosa. First Second, 2017. 9781596438774. 220pp.
Two things I immediately loved about this graphic novel: the ghostly "bees" (there are a few on the dedication page) and the grey tones done by Alex Eckman-Lawn, which reminded me of some of Andi Watson's best black and white art.
Greg doesn't cast a shadow. He's missing his mom and is more than a little angry that his dad's girlfriend, Ruth, is moving in. His best friend Layla is super tough, and tired of his moping. The town's mayor is always trying new attractions to bring in tourists (the latest is The World's Largest Hairball). They mayor's son Jake is not Greg's favorite person. Oh, and there's a haunted house, the scene of several murders, where the ghosts mess with whoever messes with the house.
Greg and Layla go into the house where Greg finds out he can see the very cute ghost of a teenage girl who haunts the place. He more than kinda falls for her which is good because she hasn't had anyone to talk to for a long while. But Layla has also fallen for Jake, which isn't good. Plus Greg is being a jerk to Layla. And then his shadow suddenly shows up.
The book is way more romantic than harrowing, and seems to be part of a wave of middle grade graphic novels about mostly friendly ghosts. All in all it's a bit of innocent fun which touches on bullying, dealing with the romantic lives of friends and parents, and embracing weirdness.
By Gene Ambaumin Book Review February 5, 2018 January 7, 2018 273 WordsLeave a comment
Guy Gardener
Taproot: A Story About A Gardener And A Ghost by Keezy Young. Roar Lion Forge, 2017. 9781941302460.
A sweet, LGBTQ-friendly graphic novel about a ghost named Blue and Hamal, the gardener who can see him (and other ghosts). There's a spooky looking dark place ghosts can suddenly find themselves and a scythe-wielding being called a Reaper (who is after a necromancer in our world, and wants Blue's help), but mostly this is a sweet romance with a lot of nice moments and great colors. It's low-key enough for middle and high schools, though I think older students and adults with good taste will enjoy it the most.
Ponies Galore!
Written in Red (A Novel of the Others) by Anne Bishop. ROC, 2014. 9780451417909. 512pp.
This book takes place on the a continent ruled by The Others — supernatural beings including shapeshifting crows, coyotes, werewolves, plus spirit bears, elementals, weather ponies, vampires, and more. Humans are tolerated and traded with, but they stay in their settlements because mostly they're seen as food. Into one of the Others' villages stumbles Meg, a young woman who escaped her lifelong captivity and is on the run from the men who profited from her powers of prophecy. (Say that five times fast.) The werewolf in charge, Simon, trusts his instincts and hires her to be the Others' human liaison, which mostly means she delivers mail. Meg's innocence and kindness allow her to interact with the Others in a way no other human has, and she's slowly accepted by them. Which is good because the men who want her back are hunting her, and she needs protection.
It's all pretty lighthearted with a decent amount of violence, and lots of scenes in the world's scariest bookstore (which Simon runs). There's a hint of romance throughout, a cop trying to keep humans safe from beings he knows could wipe them out in a heartbeat, and a drug that drives both humans and Others to savage violence. It's the setup for the rest of the series but worth reading on its own.
YOU liked that book? you ask, incredulously. Yes, yes, I did. My first paranormal romance, kinda. I blame YA author Lish McBride, who hand sold it to me at Third Place Books last month along with Sarah Gailey's fabulous novella River of Teeth, a truly diverse western about 1) getting feral hippos out of the swamp that was once the Mississippi River and 2) revenge.
By Gene Ambaumin Book Review October 24, 2017 October 2, 2017 303 WordsLeave a comment
Motorbike Mystery Machine
The Creepy Case Files of Margo Maloo by Drew Weing. First Second, 2016. 9781626723399.
Charles and his parents have moved from a small town to Echo City, where they'll live in the top-floor apartment of the building his dad is renovating. As awful as it is to Charles to have to be in a tiny room, in a busy and (he thinks) dangerous city, it's terrifying when he finds that his building has a resident monster who peeks out of his closet and steals his stuff. Another kid in the building gives him a business card (don't show any grown-ups) from Margo Maloo: Monster Mediator. Margo swoops in through Charles' window and takes him down a hidden access shaft to a blocked-off hotel kitchen. There they find a troll (Margo knows him well, his name is Marcus) and he and Charles end up bonding over their respective collection of Battlebean toys. More adventures follow as Margo lets Charles tag along on her cases around the city.
Kid detectives were my favorite genre in elementary school and this brought back happy memories of free-range kids solving mysteries. This isn't just a throwback, though, these are very modern kids. I especially liked Charles' vague questions to his dad about monsters — he assumes Charles is talking about the problems of gentrification. And maybe he is, really, as many of the stories touch on the monster population (who have their own neighborhoods and grocery stores hidden within the city) being pushed out by humans wandering into their territory.
Don't miss the endpapers that have a map of Echo City. You'll recognize neighborhoods and streets named after your favorite cartoonists and children's authors!
By Sarahin Book Review February 2, 2017 January 25, 2017 277 WordsLeave a comment