%~Mouliné par MaN_auto v.0.23.3 2021-05-31 14:23:56
\documentclass[AHL,Unicode,longabstracts,published]{cedram}

\usepackage{mathrsfs}
\usepackage{dsfont}

\DeclareMathOperator{\Var}{Var}

\newcommand{\noopsort}[1]{}

\newcommand{\bE}{\mathbb{E}}
\newcommand{\bL}{\mathbb{L}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\bR}{\mathbb{R}}

\newcommand{\bfE}{\mathbf{E}}


\newcommand{\cC}{\mathcal{C}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cX}{\mathcal{X}}



\newcommand{\caF}{\mathscr{F}}
\newcommand{\caG}{\mathscr{G}}


\newcommand{\intervalleoo}[2]{\mathopen{]} #1\mathclose{}\mathpunct{},#2\mathclose{[}}
\newcommand{\intervalleff}[2]{\mathopen{[} #1\mathclose{}\mathpunct{},#2\mathclose{]}}
\newcommand{\intervalleof}[2]{\mathopen{]} #1\mathclose{}\mathpunct{},#2\mathclose{]}}
\newcommand{\intervallefo}[2]{\mathopen{[} #1\mathclose{}\mathpunct{},#2\mathclose{[}}

\newcommand{\ind}{\mathds{1}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	


\graphicspath{{./figures/}}

\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

%\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}

\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
\let\oldtilde\tilde
\renewcommand*{\tilde}[1]{\mathchoice{\widetilde{#1}}{\widetilde{#1}}{\oldtilde{#1}}{\oldtilde{#1}}}
\let\oldhat\hat
\renewcommand*{\hat}[1]{\mathchoice{\widehat{#1}}{\widehat{#1}}{\oldhat{#1}}{\oldhat{#1}}}
\let\oldexists\exists
\renewcommand*{\exists}{\mathrel{\oldexists}}
\let\oldforall\forall
\renewcommand*{\forall}{\mathrel{\oldforall}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title[Concentration inequalities for suprema of unbounded empirical processes]{Concentration inequalities for suprema of unbounded empirical processes}
\alttitle{Inégalités de concentration pour les suprema de processus empiriques non bornés}


\subjclass{60E15}
\keywords{concentration inequalities, empirical processes, martingale method, generalized moments}



\author[\initial{A.} \lastname{Marchina}]{\firstname{Antoine} \lastname{Marchina}}
\address{Université de Paris,\\
CNRS, MAP5 UMR 8145,\\
F-75006 Paris, (France)}
\email{antoine.marchina@parisdescartes.fr}
\thanks{Many thanks to Emmanuel Rio for enlightening discussions and his careful reading of this work.}

\begin{abstract}
In this paper, we provide new concentration inequalities for suprema of (possibly) non-centered and unbounded empirical processes associated with independent and identically distributed random variables. In particular, we establish Fuk--Nagaev type inequalities with the optimal constant in the moderate deviation bandwidth. The proof builds on martingale methods and comparison inequalities, allowing to bound generalized quantiles as the so-called Conditional Value-at-Risk. Importantly, we also extent the left concentration inequalities of Klein (2002) to classes of unbounded functions.
\end{abstract}

\begin{altabstract}
Dans cet article, nous donnons des inégalités de concentration pour des suprema de processus empiriques non bornés et (éventuellement) non centrés, associés à des variables aléatoires indépendantes et identiquement distribuées. En particulier, nous établissons des inégalités de type Fuk--Nagaev avec constantes optimales dans la bande des moyennes déviations. Notre approche est basée sur des techniques de martingales et des inégalités de comparaison permettant de majorer des quantiles généralisés comme la CVaR. Nous étendons également les inégalités de concentration à gauche de Klein (2002) à des classes de fonctions non bornées.
\end{altabstract}

\datereceived{2019-10-10}
\dateaccepted{2020-07-27}

\editor{A. Philippe}
\womandeditor
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\dateposted{2021-08-26}
\begin{document}
\maketitle

\section{Introduction}
Let $\cT$ be a countable index set. For each $k=1,\,\ldots,\,n$, let $X_k:=(X_{k,\,t})_{t\,\in\,\cT}$ be a collection of centered real-valued random variables such that $X_1,\,\ldots,\,X_n$ are independent and identically distributed according to a law $P$. Define the envelope of the collection of coordinates by
\begin{equation}\label{eqn:def envelope}
M_k:=\sup_{t\,\in\,\cT} \left|X_{k,\,t}\right|\quad\text{ for all }k=1,\,\ldots,\,n\,.
\end{equation}
Throughout the paper, we assume that
\begin{equation}
\bE\left[M_1^2\right]<\infty\,.
\end{equation}
Set now for all $t\in\cT$, $S_{n,\,t}:=X_{1,\,t}+\,\ldots\,+X_{n,\,t}$. For a given (deterministic) vector $c:=(c_t)_{t\,\in\,\cT}$, we define
\begin{equation}\label{eqn:def Z}
Z:=\sup\{S_{n,\,t}+nc_t:t\in\cT\}\,.
\end{equation}
The vector $c$ is introduced to consider possibly non-centered empirical processes.


\begin{rema}
In this paper, as in~\cite{BLM13, vdGL14}, we express the empirical process in terms of random vector. If the indices $t\in\cT$ are associated with measurable functions $f_t:\cX\to\bR$ defined on some measurable space $(\cX,\cF)$, and if $Y_1,\,\ldots,\,Y_n$ is a sequence of centered iid random variables, then defining $X_{k,\,t}=f_t(Y_k)$ leads to the other classical notation (in the centered case),
\[
Z=\sup\left\{\sum_{k=1}^nf(Y_k) : f\in\caF\right\},
\]
where $\caF:=\{f_t:t\in\cT\}$.
\end{rema}

The question asked in this paper is: without the classical boundedness condition on the random variables $X_{k,\,t}$, how to provide an upper bound on the upper tail quantiles of $Z-\bE[Z]$ and $\bE[Z]-Z$?

As a direct consequence of such bounds, we will then able to derive deviation inequalities and moment inequalities which have their own interest in practical applications such as statistical learning. Let us emphasize that in the literature, there are only few studies in the unbounded setting. First, we recall that the bounded case (that is, for all $t\in\cT$, $X_{k,\,t}\leq 1$ a.s. or $|X_{k,\,t}|\leq 1$ a.s) is handled by Talagrand's inequality. Precisely, it is the merit of Talagrand~\cite{Talagrand96a} to obtain the first a functional Bennett inequality for suprema of empirical processes, but with unspecified constants. Ledoux~\cite{Ledoux97} introduces a new method based on entropic inequalities to recover more directly Talagrand’s result. This method is the starting point of a series of paper, mainly to reach optimal constants in Talagrand's inequality: Massart~\cite{Massart00}, Rio~\cite{Rio01,Rio02,Rio12}, Bousquet~\cite{Bousquet03}, Klein~\cite{Klein02} and Klein and Rio~\cite{KR05}. For an overview of the results in the bounded case, we refer the reader to Section~12 in the book of Boucheron, Lugosi, and Massart~\cite{BLM13}.

The different attempts to get tail bounds for suprema of unbounded empirical processes I am aware of, have been investigated by Adamczak~\cite{Adamczak08}, Lederer and van de Geer~\cite{vdGL14,vdGL13}, and Dirksen~\cite{Dirksen15}. Under the moment condition on the envelope $\|M_1\|_{\psi_\alpha}<+\infty$ for some $\alpha\in\intervalleof 01$, where $\|.\|_{\psi_\alpha}$ is the Orlicz norm associated with $\psi_\alpha(x)=\exp(x^{\alpha})-1$ (the case $\alpha=1$ corresponds to having sub-exponential tails), Adamczak~\cite[Theorem~4]{Adamczak08} proves the following deviation inequality: let $\tilde Z=\sup_{t\,\in\,\cT}|\sum_{k=1}^nX_{k,\,t}|$, then for all $0<\varepsilon<1$, $\delta>0$, and $t>0$,
\begin{multline}
\bP\left(\tilde Z\geq (1+\varepsilon)\bE[\tilde Z]+t\right)\\
\leq \exp\left(-\frac{t^2}{2(1+\delta)n\sigma^2}\right)+3\exp\left(-\left(\frac{t}{C_{\alpha,\,\varepsilon,\,\delta}\|\max_k M_k\|_{\psi_\alpha}}\right)^\alpha\right),
\end{multline}
where $\sigma^2=\sup_{t\,\in\,\cT}\Var(X_{1,\,t})$ is the wimpy variance, and $C_{\alpha,\,\varepsilon,\,\delta}$ is an unspecified constant. In~\cite[Corollary~3.1]{vdGL14}, Lederer and van de Geer only require that $\|M_1\|_p<\infty$ for some $p>2$, and obtain that for all $\varepsilon>0$ and $t>0$,
\begin{multline}
\bP\left(\tilde Z\geq (1+\varepsilon)\bE[\tilde Z]+ t\right) \\
\leq \min_{1\,\leq\,r\,\leq\,p} t^{-r}\left(4\sigma\sqrt{rn}+\left(\frac{64}{\varepsilon}+7+\varepsilon\right)r^{1-r/p}n^{r/p}\|M_1\|_p\right)^r.
\end{multline}


These two results are based on truncation arguments and on Talagrand type inequalities for suprema of bounded empirical processes. That explains the additional factor $(1+\varepsilon)$ in front of $\bE[Z]$. The same authors in~\cite[Theorem~8]{vdGL13} provide an exponential tail bound for $\tilde Z$ under a uniform Bernstein condition. To do this, they introduce the Bernstein--Orlicz norm that they combine with a variation of the classical chaining. In~\cite[Corollary~5.2]{Dirksen15}, assuming the same uniform Bernstein condition as in~\cite{vdGL13}, Dirksen uses the generic chaining to upper bound all $p^{\rm th}$ moments of $\tilde Z$ and thus he derives an exponential tail bound by a standard optimization argument.

In the present paper, we relax the previous tail assumptions by only assuming the mild condition that $\|M_1\|_p$ is finite for some $p>2$. We will prove in particular the following deviation inequality around $\bE[Z]$, without extra centering term $\varepsilon\bE[Z]$ and with explicit constants (see Theorem~\ref{thm:FukNagaev from Rio right} below): for any $u\in\intervalleoo 01$,
\[
\bP\left(Z>\bE[Z]+\sqrt{2n\log(1/u)}\,\left(\sigma+\sqrt{v_n}\,\right)+\,n^{1/p}(p+8)\,\|M_1\|_p u^{-1/p}\right)\leq u,
\]
where $v_n$ satisfies $v_n=o(1)$ as $n$ tends to infinity. We emphasize that the constant $1$ in front of $\sigma\sqrt{\text{\small{$2n\log(1/u)$}}}$ is optimal and, in addition, we show that we cannot expect to have a nonasymptotic upper bound with $\sigma$ instead of $\sigma+v_n$ (see Section~\ref{sect1.3} below). Moreover, our term $v_n$ is of a correct order. The proofs of our results rely on martingales methods, comparison inequalities, and recent concentration inequalities for real-valued martingales proved by Rio~\cite{Rio17a}. Another important point is that we do not seek to directly control the upper tail quantile as usual, but instead we control the Conditional Value-At-Risk of $Z-\bE[Z]$. Finally, let us mention that we already use martingale methods in a previous work to obtain concentration inequalities for (general) separately convex functions~\cite{Marchina18a}. However when we apply the results to the case of unbounded empirical processes, the upper bound suffer from the fact that they do not involve the wimpy variance $\sigma^2$ and then are less interesting for the statistical applications we have in mind.

In order to explain our results, let us give some definitions and notation.

\subsection{Upper tail quantile and Conditional Value-At-Risk}
Let $X$ be a real-valued random variable. As usual, we denote by $F_X$ its distribution function and by $F_X^{-1}$ the càdlàg inverse of $F_X$.

\begin{defi}\label{def:CVaR}
The ``upper tail'' quantile function of $X$, which is the càdlàg inverse of the tail function $t\mapsto 1-F_X(t)$, is denoted by $Q_X$. It is defined by
\[
Q_X(u):=\inf\{x\in\bR:1-F_X(x)\leq u\}\,.
\]
\end{defi}

Note that $Q_X(u)$ is the value of the usual quantile function at point $1-u$. The basic property of $Q_X$ is: $x<Q_X(u)$ if and only if $1-F_X(x)>u$. This ensures that $Q_X(U)$ has the same distribution as $X$ for any random variable $U$ uniformly distributed over $\intervalleff 01$.


\begin{defi}
Assume that $X$ is integrable. The Conditional Value-at-Risk (CVaR for short) of $X$ is defined by
\begin{equation}\label{eqn:def CVaR}
\tilde Q_X(u):=\frac{1}{u}\int_0^u Q_X(s)ds\quad\text{ for any }u\in\intervalleof 01\,.
\end{equation}
\end{defi}

It is worth noticing that, for any $u\in\intervalleoo 01$, if the distribution of $X$ has no atom at $Q_X(u)$, then (see, for instance, \cite[Section~5.9]{Pinelis14b} in Pinelis)
\[
\bE\left[X\mid X>Q_X(u)\right]= u^{-1}\sup_{\bP(A)\,\leq\,u}\bE\left[X\ind_A\right]=\tilde Q_X(u)\,.
\]

When $X$ has a finite Laplace transform on a right neighborhood of $0$, we denote by $\ell_X$ the log-Laplace transform of $X$, given by
\begin{equation}\label{eqn:def logLaplace}
\ell_X(t):=\log\bE\left[\exp(tX)\right]\quad \text{for any }t\geq 0\,.
\end{equation}

The Legendre transform $\ell_X^*$ of $X$ is defined by
\begin{equation}\label{eqn:def Legendre transform}
\ell_X^*(\lambda):=\sup\left\{\lambda t - \ell_X(t) : t>0\right\}\quad\text{for any }\lambda\geq0\,.
\end{equation}

We recall that the inverse function of $\ell_X^*$ admits the following variational expression (see, for instance, Rio~\cite[Lemma~A.2]{Rio17b}):
\begin{equation}\label{eqn:inverse Legendre transform}
\ell_X^{*-1}(x)=\inf\left\{t^{-1}(\ell_X(t)+x) : t>0\right\}\quad\text{for any }x\geq 0\,.
\end{equation}
Clearly, one has $Q_X\leq\tilde Q_X$. Moreover,
\begin{equation}\label{eqn:comparaison CVAR Leg}
\tilde Q_X(u)\leq \ell^{*-1}_X(\log(1/u))\quad\text{for any }u\in\intervalleof 01\,.
\end{equation}


This result may be found in Pinelis~\cite[Theorem~3.4]{Pinelis14b}. In this paper, we will focus on upper bounds on the CVaR of $Z-\bE[Z]$ instead of on its upper tail quantile function (also known as the Value-at-Risk). To a certain extent, we can consider that the CVaR is superior than the Value-at-Risk since it has stronger mathematical properties which are very useful in optimization modeling or statistics. We refer the reader to Pinelis~\cite{Pinelis14b} or Rockafellar and Uryasev~\cite{RU00} (see also the references therein) for more on the CVaR. One property that will be of interest to us is the subadditivity of the CVaR (see~\cite[Theorem~3.4]{Pinelis14b}):

\begin{prop}\label{prop:subadd CVaR}
Let $X$ and $Y$ be real-valued and integrable random variables ($X$ and $Y$ may not be independent). Then, for any $u\in\intervalleof 01$,
\begin{equation*}
\tilde{Q}_{X+Y}(u)\leq \tilde{Q}_X(u)+\tilde{Q}_Y(u)\,.
\end{equation*}
\end{prop}



\subsection{Aim and organization of the paper}

In a well known paper~\cite{CIS76}, Cirel'son, Ibragimov and Sudakov proved a comparison inequality between the quantiles of a supremum of a Gaussian process and those of a standard Gaussian random variable (see~\cite[pages~22-23]{CIS76}). Precisely, let $(G_t)_{t\,\in\,\cT}$ be a centered Gaussian process indexed by $\cT$ such that $Z_G:=\sup_{t\,\in\,\cT}G_t<\infty$ almost surely. Define $\sigma_G^2:=\sup_{t\,\in\,\cT}\bE[G_t^2]$, and let $Y$ be a standard Gaussian random variable. They proved that for any $u,v\in\intervalleof 01$,
\begin{equation}\label{eqn:CIS}
\left|Q_{Z_G-\bE[Z_G]}(u)-Q_{Z_G-\bE[Z_G]}(v)\right|\leq\sigma_G \left|Q_{Y}(u)-Q_Y(v)\right|\,.
\end{equation}


Now, combining this inequality with~\eqref{eqn:comparaison CVAR Leg} yields that for any $u\in\intervalleof 01$,
\begin{equation}\label{eqn:CIS2}
\tilde Q_{Z_G-\bE[Z_G]}(u)\leq \sigma_G\,\tilde Q_Y(u)\leq\sigma_G\,\ell_Y^{*-1}(\log(1/u))=\sigma_G\sqrt{2\log(1/u)}\,.
\end{equation}


For the convenience of the reader, we provide a proof of the first inequality in~\eqref{eqn:CIS2} in Appendix~\ref{section:Appendix A}. Note that this inequality could be also deduced from Bobkov~\cite[Corollary~2]{Bobkov03}.

Since the empirical process $S_{n,\,t}$, $t\in\cT$, converges fidi (after suitable normalization) towards a Gaussian process, the aim is then to reach an extension of the Gaussian bound~\eqref{eqn:CIS2} for $Z-\bE[Z]$ in the unbounded case.

Let us mention the considerable work of Boucheron, Bousquet, Lugosi, and Massart~\cite{BBLM05} concerning moment inequalities for general functions of independent random variables. Their methods are based on an extension of the entropy method proposed by Ledoux, which allows to derive a moment inequality on $\|(Z-\bE[Z])_+\|_p$, $p>2$, for centered processes (that is $c\equiv 0$ in~\eqref{eqn:def Z}). However, considering the upper bound that their inequality provides on the quantile, we may notice that it is suboptimal in the moderate deviations bandwidth. Precisely, there is a power $u^{-1/p}$ instead of the term $\sqrt{\text{\small{$\log(1/u)$}}}$ we would like to have by comparing with the right-hand side in~\eqref{eqn:CIS2}. Furthermore, it seems beyond the scope of classical functional analysis tools to handle non-centered empirical processes.

Our method is based on a martingale decomposition of $Z-\bE[Z]$ into a sum of two martingales. The subadditivity of the CVaR allows us to treat each martingale separately. The difficulties lie in the control of their increments, in particular their conditional variance. To this end, we shall establish comparison inequalities with respect to a class of convex functions, similar to Hoeffding's classical inequalities concerning bounded random variables~\cite{Hoeffding63}.

In addition, we want our inequalities on $Z-\bE[Z]$ to generalize those known for the sums of independent random variables, corresponding to a class $\cT$ reduced to one element. When the random variables are unbounded but with finite variances, their deviations are handled by Fuk--Nagaev inequalities. The best known constants are given recently by Rio~\cite{Rio17a} in the context of real-valued martingales. In the setting of real-valued iid centered random variables $X_1,\,\ldots,\,X_n$, he proves that, for any $u\in\intervalleof 01$,
\begin{equation}\label{eqn:Rio FukNagaev iid}
\tilde Q_{S_n}(u)\leq \sigma\sqrt{2n\log(1/u)}+n^{1/p}K_p \left\|X_1\right\|_{p} \,u^{-1/p},
\end{equation}
where $p>2$, $S_n:=X_1+\,\ldots\,+X_n$, the constant $K_p$, depending only on $p$, is explicit and $\sigma^2:=\Var(X_1)$. The reader may notice that the constant $1$ in front of the term $\sigma\sqrt{\text{\small{$2n\log(1/u)$}}}$ is optimal.

The organization of the paper is as follows. In Section~\ref{section:FukNagaev Rosenthal}, we present our main results which are Fuk--Nagaev and Rosenthal type inequalities for $Z-\bE[Z]$ and $\bE[Z]-Z$. A detailed application under the assumption that the $X_{k,t}$'s have power tails is given. In Section~\ref{section:bounds generalized moments}, we derive upper bounds for $\bE[(Z-\bE[Z]-t)_+^\alpha]$, $\alpha\geq 1$. In Section~\ref{section:left deviation inequalities}, we study left deviation inequalities which turn out to be easier to obtain than the right ones. All the proofs are deferred to Section~\ref{section:proofs}. Before starting, let us do some comments on the variance factor in our inequalities.

\subsection{About the variance factor}\label{sect1.3}
Let $(G_t)_{t\,\in\,\cT}$ be a centered Gaussian process such that $Z_G:=\sup_{t\,\in\,\cT}G_t<\infty$ almost surely. As a consequence of~\eqref{eqn:CIS2}, one can derive the following upper bound on the variance:
\begin{equation}\label{eqn:bound variance Gaussian}
\Var(Z_G)\leq \sigma_G^2,
\end{equation}
where $\sigma_G^2:=\sup_{t\,\in\,\cT}\bE[G_t^2]=\sup_{t\,\in\,\cT}\Var(G_t)$. Then, a natural question is whether \eqref{eqn:bound variance Gaussian} is satisfied by $Z$ with
\begin{equation}\label{eqn:def wimpy}
\sigma^2:=\sup\left\{\Var(X_{1,\,t}):t\in\cT\right\}=\sup\left\{\bE\left[X_{1,\,t}^2\right] : t\in\cT\right\}.
\end{equation}
The answer is no, even in the bounded case (see, for instance, \cite[Exercise~11.1]{BLM13} for a simple counterexample). Let us give another example in the unbounded case that will be useful in Section~\ref{section:FukNagaev Rosenthal} to comment on the variance factor appearing in our results.

\begin{exam}\label{example:power type tail}
Let $U,U_1,\,\ldots,\,U_n$ be a sequence of iid random variables uniformly distributed on $\intervalleff 01$. Let $\ell>2$, $\Delta>0$ and $p\in\intervalleoo 01$. Let $\cS$ be the set of all finite unions of disjoint intervals with rational endpoints, which measure is lower than $p$, and included in $\intervalleff{0}{\Delta}$. Define
\[
Z:=\sup_{S\,\in\,\cS}\sum_{k=1}^n \left(U_k^{-1/\ell}\ind_S(U_k)-\int_S u^{-1/\ell}du\right),
\]
and $\sigma^2:=\sup_{S\,\in\,\cS}\Var(U^{-1/\ell}\ind_{S}(U))$. Then, for $p$ and $\Delta$ small enough, one can show that there exists $K>0$ such that
\begin{equation}\label{eqn:example lower bound VarZ}
\frac 1n\Var(Z)-\sigma^2\geq K\left(\frac{\bE[Z]}{n}\right)^{\frac{\ell-2}{\ell-1}}.
\end{equation}
\end{exam}

The details of the proof of~\eqref{eqn:example lower bound VarZ} are deferred to Appendix~\ref{section:Appendix A}. Therefrom, since we want to provide nonasymptotic inequalities, we cannot expect, as in~\eqref{eqn:Rio FukNagaev iid}, the quantity $\sigma\sqrt{\text{\small{$2n\log(1/u)$}}}$ in the moderate deviation part: a corrective term to $\sigma$ is required. Let us now describe this quantity which appears in our inequalities.

First, we set for all $k=1,\,\ldots,\,n$,
\begin{equation}\label{eqn:def E_k}
E_k:=\bE\left[\sup_{t\,\in\,\cT}\frac 1k\sum_{j=1}^k X_{j,\,t}\right].
\end{equation}
Next, we define the following class of distribution functions:

\begin{defi}\label{def:distrib function}
Let $q\in\intervalleff 01$. Let $\psi$ be a nonnegative random variable and set $b_{\psi,\,q}:=F_\psi^{-1}(1-q)$. We denote by $F_{\psi,\,q}$ the distribution function of $\psi\ind_{\psi\,\geq\,b_{\psi,\,q}}$, that is
\begin{equation}\label{eqn:def distrib function}
F_{\psi,\,q}(x):=(1-q)\ind_{0\,\leq x < b_{\psi,\,q}} + F_{\psi}(x)\ind_{x\,\geq\,b_{\psi,\,q}}\quad\text{for all }x\in\bR.
\end{equation}
\end{defi}

Let $\psi$ and $X$ be two nonnegative random variables such that $X$ is first-order stochastically dominated by $\psi$, that is $\bP(X> x)\leq \bP(\psi>x)$ for all $x>0$. Let $\zeta_{\psi,\,q}$ be a random variable with distribution function $F_{\psi,\,q}$, where $q$ is such that $\bE[X]\leq\bE[\zeta_{\psi,\,q}]$. Then~\cite[Lemma~1]{Bentkus08a} of Bentkus (see also~\cite[Lemma~4.3]{Marchina18a} in Marchina) ensures that
\begin{equation}\label{eqn:extension Hoeffding unbounded}
\bE[\varphi(X)]\leq\bE[\varphi(\zeta_{\psi,\,q})]\quad\text{ for any function }\varphi\in\cH_+^1,
\end{equation}
where $\cH_+^1:=\left\{\varphi\, :\,\varphi\text{ is convex, differentiable, and }\lim_{x\to-\infty}\varphi(x)=0\right\}$.

If $\bE[X]=\bE[\zeta_{\psi, q}]$, then the above inequality is true for any convex function. In order to have a better understanding of this result, see that the distributions $F_{\psi,\,q}$, $q\in\intervalleff 01$, are the extremal ones satisfying $0\leq X\leq_{\text{st}} \psi$, where $\leq_{\text{st}}$ denote the first-order stochastic dominance. If $\psi=b$ is a constant, the extremal distributions are the two-valued ones $\mu_q:=(1-q)\delta_0+q\delta_b$, $q\in\intervalleff 01$. And it is well known that for any convex function $\varphi$, $\bE[\varphi(X)]\leq \int \varphi d\mu_{q_0}$, where $q_0$ is such that $\bE[X]=\int xd\mu_{q_0}$ (see Hoeffding~\cite{Hoeffding63}). Then~\eqref{eqn:extension Hoeffding unbounded} is an extension of Hoeffding's comparison inequality to unbounded random variables.

\begin{nota}
Throughout the rest of the paper, $\zeta_k$ denotes a random variable with distribution function $F_{2M_1,\,q_k}$ where $q_k$ is the greatest real in $\intervalleff 01$ such that $\bE[\zeta_k]=E_k$. Define also
\begin{equation}\label{def:V_n}
V_n:=\sum_{k=1}^n \bE\left[\zeta_k^2\right],\text{ and } v_n:=\frac{V_n}{n}.
\end{equation}
\end{nota}

The variance factor in our inequalities is $\sqrt n(\sigma+\sqrt{v_n})$. We can see that $\sqrt{v_n}$ is indeed a ``corrective'' term. If the class $\cT$ satisfies the uniform law of large numbers, that is $\sup_{t\,\in\,\cT}|n^{-1}S_{n,\,t}|$ converges to $0$ in probability, then $E_n$ decreases to 0 (see, for instance, \cite[Section~2.4]{vdVW96} of van der Vaart and Wellner). Now, from the square integrability of $M_1$ and the definition of the random variable $\zeta_n$, the convergence of $E_n$ to $0$ implies the convergence of $\bE[\zeta_n^2]$ to 0, which ensures that $V_n=o(n)$ as $n$ tends to infinity. Thus,
\begin{equation}
\sqrt n(\sigma+\sqrt{v_n})\sim\sigma\sqrt n\quad\text{ as $n$ tends to infinity}\,.
\end{equation}

\section{Fuk--Nagaev and Rosenthal type inequalities}\label{section:FukNagaev Rosenthal}
In this section we provide Fuk--Nagaev and Rosenthal type inequalities for $Z-\bE[Z]$ and $\bE[Z]-Z$. We first introduce some more definitions and notations. For any real-valued integrable random variable $X$ and any $r\geq 1$, define
\begin{equation}\label{eqn:def weak norm}
\Lambda_r^+(X):=\sup_{t\,>\,0} t\,(\bP(X>t))^{1/r}\,.
\end{equation}
We say that $X$ has a weak moment of order $r$ if $\Lambda_r^+(|X|)$ is finite. We denote by $\bL_r^w$ the space of real-valued random variables with a finite weak moment of order $r$. Note that from the definition of $Q_X$, we have (see, for instance, \cite[Chapter~4]{BS88} of Bennett and Sharpley)
\begin{equation}
\Lambda_r^+(X)=\sup_{u\,\in\,]0,\,1]}u^{1/r}Q_X(u)\,.
\end{equation}

\subsection{Fuk--Nagaev type inequalities}

We will now formulate the main results of this part, starting by right-hand side deviations.

\begin{theo}\label{thm:FukNagaev from Rio right}
Let $Z$ be defined by~\eqref{eqn:def Z}. Let $p>2$ and assume that $M_1\in\bL_p^w$. Let $\mu_p:=2+\max(4/3, p/3)$. Then for any $u\in\intervalleoo 01$,
\begin{align}
\tilde Q_{Z-\bE[Z]}(u)\leq\sqrt{2n\log(1/u)}\,\left(\sigma+\sqrt{v_n}\right)+3\,n^{1/p}\mu_p\,\Lambda_p^+(M_1) u^{-1/p}. \tag{$\rm a$}\label{theo2.1.a}
\\
\intertext{Consequently,}
\bP\left(Z>\bE[Z]+\sqrt{2n\log(1/u)}\,\left(\sigma+\sqrt{v_n}\right)+3\,n^{1/p}\mu_p\,\Lambda_p^+(M_1) u^{-1/p}\right)\leq u. \tag{$\rm b$}\label{theo2.1.b}
\end{align}
\end{theo}

\begin{rema}
For any real-valued random variable $X$, by Markov's inequality, $\Lambda_p^+(X)\leq\|X\|_p$. Then, if the envelope $M_1$ has a finite $p^{\rm th}$ moment, one can replace the weak moment $\Lambda_+^p(M_1)$ by the strong moment $\|M_1\|_p$.
\end{rema}

\begin{rema}
Note that an upper bound on the CVaR of $Z$ immediately gives an upper bound on the upper tail quantile of
\begin{equation}
Z^*:=\max_{k\,\leq\,n}\sup_{t\,\in\,\cT}\left\{\sum_{j=1}^k X_{j,\,t}+kc_t\right\}.
\end{equation}
Indeed, for any $u\in\intervalleoo 01$,
\begin{equation}
\begin{aligned}
Q_{Z^*}(u)&\leq \tilde Q_{Z}(u)\\
&\leq \bE[Z]+ \sqrt{2n\log(1/u)}\,\left(\sigma+\sqrt{v_n}\right)+3\,n^{1/p}\mu_p\,\Lambda_p^+(M_1) u^{-1/p}.
\end{aligned}
\end{equation}

The first inequality follows from a byproduct of Doob's maximal inequality which can be found in Gilat and Meilijson~\cite{GM88}.
\end{rema}

The term $v_n$ depends only on $E_k$, $k=1,\,\ldots,\,n$, and on the tail distribution of $M_1$ (see~\eqref{def:V_n}). We provide below a useful and explicit upper bound on $v_n$:
\begin{lemm}\label{lem:upper bound Vn power type tail}
One has
\[
v_n\leq \left(2\Lambda_p^+(M_1)\right)^{\frac{p}{p-1}}\,\frac{p}{p-2}\left(1-\frac 1p\,\right)^{\frac{p-2}{p-1}}\,\frac 1n \sum_{k=1}^n E_k^{\frac{p-2}{p-1}}.
\]
\end{lemm}

If a Donsker theorem holds, one can consider that $E_n\asymp n^{-1/2}$ (see, for instance, van der Vaart and Wellner~\cite{vdVW96}). Then Lemma~\ref{lem:upper bound Vn power type tail} yields that
\begin{equation}\label{eqn:upper bound equiv Vn power type tail}
v_n\leq K_p\,n^{-\frac 12\frac{p-2}{p-1}},
\end{equation}
where $K_p$ is a constant depending only on $p$. This upper bound has to be linked with inequality~\eqref{eqn:example lower bound VarZ}. Indeed, we have shown in Example~\ref{example:power type tail}, which is a particular case of power-type tail, that we have to add to $\sigma^2$ in the variance factor, a term which is at least of order $n^{-\frac 12\frac{p-2}{p-1}}$ when $E_n\asymp n^{-1/2}$. Thus, it supports the idea that our additional term $v_n$ is of a correct order.

For left-hand side deviations, the concentration bounds are similar but the proofs are simpler than for the right-hand side. In fact, it has already been noted by Samson~\cite{Samson07} in the context of transport methods, that martingale like techniques allow to obtain left deviations more easily as regards to the entropy method introduced by Ledoux.

\begin{theo}\label{thm:FukNagaev from Rio left}
Let $Z$ be defined by~\eqref{eqn:def Z}. Let $p>2$. Assume that $M_1\in\bL_p^w$ and that for some $r\geq p$,
\[
m_r^r:=\sup_{t\,\in\,\cT}\bE\left[(-X_{1,\,t})_+^r\right]<\infty\,.
\]
Let $\mu_p:=2+\max(4/3,p/3)$. Then for any $u\in\intervalleoo 01$,
\begin{align}
&\tilde Q_{\bE[Z]-Z}(u)\leq \sqrt{2n\log(1/u)}\,\left(\sigma+\sqrt{v_n}\,\right)+n^{1/r}\mu_\ell\,m_r u^{-1/r}. \tag{$\rm a$}\label{theo2.5.a}
\\
\intertext{Consequently,}
&\bP\left(Z<\bE[Z]-\sqrt{2n\log(1/u)}\,\left(\sigma+\sqrt{v_n}\,\right)-n^{1/r}\mu_r\,m_r u^{-1/r}\right)\leq u. \tag{$\rm b$}\label{theo2.5.b}
\end{align}
\end{theo}

\subsection{Weak and strong Rosenthal type inequalities}

We start with weak Rosenthal inequalities derived from the inequalities of the previous section. We first introduce some more notation. Define
\begin{equation}\label{eqn:def weak norm tilde}
\tilde{\Lambda}_r^+(Y):=\sup_{u\,\in\,]0,\,1]} u^{(1/r)-1}\int_0^u Q_Y(s)ds=\sup_{u\,\in\,]0,\,1]} u^{1/r}\tilde Q_Y(u)\,.
\end{equation}
Hence, we get that
\begin{equation}\label{eqn:bound Lambda by tildeLambda}
\Lambda_r^+(Y)\leq\tilde\Lambda_r^+(Y)\leq\left(\frac{r}{r-1}\right)\Lambda_r^+(Y)\,.
\end{equation}
Furthermore, from the subadditivity of the CVaR (Proposition~\ref{prop:subadd CVaR}), $\tilde\Lambda_r^+(.)$ is subadditive, which implies that $\tilde\Lambda_r^+(.)$ is a norm on the space $\bL_r^w$.

Now, when the envelope $M_1$ has a weak moment of order $p>2$, proceeding as in Rio~\cite{Rio17a}, we derive from Theorems~\ref{thm:FukNagaev from Rio right} and~\ref{thm:FukNagaev from Rio left} the following inequalities:

\begin{coro}\label{cor:weak moment ineq from Rio}
Let $Z$ be defined by~\eqref{eqn:def Z}. Let $p>2$ and assume that $M_1$ have a weak moment of order $p$. Let $\mu_p:=2+\max(4/3, p/3)$. Then
\begin{align*}
\Lambda_p^+(Z-\bE[Z])&\leq\tilde\Lambda_p^+(Z-\bE[Z])\tag{$\rm a$}\label{coro2.6.a}\\
&\leq \sqrt{(p/e)}\sqrt n\,\left(\sigma+\sqrt{v_n}\,\right)+3\,n^{1/p}\mu_p\,\Lambda_p^+ (M_1)\,.\tag{$\rm b$}\label{coro2.6.b}
\\
\intertext{Moreover,}
\Lambda_p^+(\bE[Z]-Z)&\leq \tilde\Lambda_p^+(\bE[Z]-Z)\tag{$\rm c$}\label{coro2.6.c}\\
&\leq \sqrt{(p/e)}\sqrt n\,\left(\sigma+\sqrt{v_n}\,\right)+n^{1/p}\mu_p\,\Lambda_p^+(M_1)\,.\tag{$\rm d$}\label{coro2.6.d}
\end{align*}
\end{coro}


The variational formula~\eqref{eqn:def weak norm tilde} ensures that these inequalities above are the optimal ones that can be achieved from the Fuk--Nagaev type inequalities in Theorems~\ref{thm:FukNagaev from Rio right}-\ref{thm:FukNagaev from Rio left}. Unfortunately, such a formula linking strong moments of order $p>2$ of a real-valued random variable and its CVaR does not exist. For this reason, to obtain an upper bound on $\|Z-\bE[Z]\|_p$ for $p>2$, we directly reinvest the martingale decomposition of $Z-\bE[Z]$ used in the proofs of previous theorems, that we associate with Rosenthal inequalities for real-valued martingales. Those with best known constants are given by Pinelis~\cite[Corollary~1]{Pinelis15}. His result holds for any $p>2$, but for $p\in\intervalleof 24$, the constants are close to optimality (see the discussion~\cite[pages~701-702]{Pinelis15}) and are easy to express. We obtain the following inequality:
\begin{theo}\label{thm:Rosenthal strong}
Let $Z$ be defined by~\eqref{eqn:def Z}. Let $p\in\intervalleof 24$ and assume that $\|M_1\|_p<\infty$. Then
\[
\|Z-\bE[Z]\|_p\leq (p-1)^{1/p}\sqrt{n}(\sigma+\sqrt{v_n}\,)+(2^{1/p}+1)n^{1/p}\|M_1\|_p\,.
\]
\end{theo}

Let us now recall the moment inequality for suprema of empirical processes obtained by Boucheron, Bousquet, Lugosi and Massart~\cite{BBLM05} (see~\cite[Theorems~15.14 and 15.5]{BLM13}): let $p>2$ and define $\tilde Z:=\sup_{t\,\in\,\cT}\left|\sum_{k=1}^nX_{k,\,t}\right|$. Then
\begin{multline}\label{eqn:Rosenthal BBLM}
\left\|(\tilde Z-\bE[\tilde Z])_+\right\|_p\leq \sqrt{\kappa(p-1)}\sqrt{n}\left(\sigma+\Sigma\right)\\
+\kappa(p-1)\left(\left\|\max_{k=1,\,\ldots,\,n}M_k\right\|_p+\sup_{t\,\in\,\cT}\|X_{1,\,t}\|_2\right),
\end{multline}
where $\kappa:=\sqrt{e}/(\sqrt{e}-1)$ and $\Sigma^2:=\bE[\sup_{t\,\in\,\cT}n^{-1}\sum_{k=1}^nX_{k,\,t}^2]$. Let us now comment the differences with our result Theorem~\ref{thm:Rosenthal strong}:
\begin{itemize}
\item In fact, inequality~\eqref{eqn:Rosenthal BBLM} does not require the identical distribution of the sequence $X_1,\,\ldots,\,X_n$. However, contrary to Theorem~\ref{thm:Rosenthal strong}, inequality~\eqref{eqn:Rosenthal BBLM} concerns centered empirical processes, that is $c\equiv 0$ in~\eqref{eqn:def Z}.
\item The moment inequality~\eqref{eqn:Rosenthal BBLM} is only given for the positive part of $\tilde Z-\bE[\tilde Z]$.

\item To compare the constant in front of the variance factor, let us consider the upper bound that the authors provided on $\Sigma^2$ (see~\cite[Theorem~11.17]{BLM13}):
\begin{equation}\label{eqn:upper bound weak variance}
n\Sigma^2\leq n\sigma^2+32\left\|\max_{k=1,\,\ldots,\,n}M_k\right\|_2\,\bE[\tilde Z]+8\left\|\max_{k=1,\,\ldots,\,n}M_k\right\|_2^2.
\end{equation}
\goodbreak
Combining~\eqref{eqn:upper bound weak variance} with~\eqref{eqn:Rosenthal BBLM} leads to the following behavior:
\begin{equation}\label{eqn:Rosenthal BBLM moderate deviation}
\left\|(\tilde Z-\bE[\tilde Z])_+\right\|_p\leq 2\kappa\sqrt{p-1}\,\sigma\sqrt n+o\left(\sqrt n\,\right).
\end{equation}
Note that $B_p:= 2\kappa\sqrt{p-1}$ is increasing in $p$, $B_2\approx 3.1184$ and $B_4\approx 5.5225$. By comparison, our constant $C_p:=(p-1)^{1/p}$ is increasing on $\intervalleff 24$, $C_2= 1$ and $C_4\approx 1.3161$.
\item Let us now compare the variance factor by comparing $v_n$ to $\Sigma^2-\sigma^2$. To this end, we will use a version of Pisier lemma which can be found in Rio~\cite[Appendix D]{Rio17b}. It states that for any $0<r< p$,
\begin{equation}\label{eqn:Pisier lemma}
\left\|\max_{k=1,\,\ldots,\,n}M_k\right\|_r\leq \left(n\int_0^{1/n}Q_{M_1}^r(u)du\right)^{1/r}\leq \textcolor{black}{\Lambda_p^+(M_1)} \left(\frac{p}{p-r}\right)^{1/r}n^{1/p}.
\end{equation}
Putting this upper bound in~\eqref{eqn:upper bound weak variance} yields that
\[
\Sigma^2-\sigma^2\leq K_p\, n^{-\frac 12\left(1-\frac{2}{p}\right)}+o\left(n^{-\frac{1}{2}\left(1-\frac{2}{p}\right)}\right).
\]
Now, see that
\[
n^{-\frac{1}{2}\frac{p-2}{p-1}}=o\left(n^{-\frac{1}{2}\left(1-\frac{2}{p}\right)}\right).
\]
Thus, recalling~\eqref{eqn:upper bound equiv Vn power type tail}, one can say that $\Sigma^2-\sigma^2$ is of a larger order than $v_n$.
\end{itemize}

\subsection{Application to power-type tail}
Let $Y_1,\,\ldots,\,Y_n$ be a finite sequence of nonnegative iid random variables and let $X_1,\,\ldots,\,X_n$ be a finite sequence of iid random variables with values in some measurable space $(\cX,\cF)$ such that the two sequences are independent. Let $P$ denote the common distribution of the $X_k$'s. Let $\caF$ be a countable class of measurable functions from $\cX$ into $\intervalleff{-1}{1}$ such that for all $f\in\caF$,
\begin{equation}\label{eqn:prop caF power type tail}
P(f)=0\quad \text{and}\quad P(f^2)< \delta^2\;\text{ for some }\delta\in \intervalleoo 01\,.
\end{equation}
Let $F$ be a measurable envelope function of $\caF$, that is
\begin{equation}\label{eqn:def envelope power type tail}
|f|\leq F\text{ for any }f\in\caF,\text{ and } F(x)\leq 1\text{ for all }x\in\cX\,.
\end{equation}
We suppose furthermore that for some constant $\ell>2$,
\begin{equation}\label{eqn:hyp envelope power type tail}
\bP(Y_1>t)\leq t^{-\ell}\quad\text{ for any }t>0\,.
\end{equation}
Define now
\begin{equation}\label{eqn:def Z power type tail}
Z:= \sup_{f\,\in\,\caF}\sum_{k=1}^nY_k\,f(X_k)\,.
\end{equation}
We associate to each $f\in\caF$ an unique index $t$, and we define $\cT$ the set of all these indices. Set for all $k=1,\,\ldots,\,n$, $\tilde X_{k,\,t}:=Y_kf(X_k)$. Then, we have $Z=\sup_{t\,\in\,\cT}\linebreak\sum_{k=1}^n X_{k,\,t}$. This allows us to apply results of the previous section. The envelope of the collection of coordinates $M_k$ is defined by $M_k:=Y_kF(X_k)$.

Recalling Lemma~\ref{lem:upper bound Vn power type tail}, the remaining task to provide a useful bound on $v_n$ is to upper bound the quantities $E_k$, $k=1,\,\ldots,\,n$. This will be done by using local maximal inequalities for empirical processes due to van der Vaart and Wellner~\cite[Theorem~2.1]{vdVW11}. The upper bound is expressed in terms of uniform entropy integral. Let us first recall some classical definitions.

\begin{defi}[Covering number and uniform entropy integral]
The covering number $N(\epsilon,\caG, \nu)$ is the minimal number of balls of radius $\epsilon$ in $\bL^2(\nu)$ needed to cover the set $\caG$. The uniform entropy integral is defined by
\[
J(\delta,\caG):=\int_0^\delta\sup_\nu\sqrt{1+\log N\left(\epsilon\|F\|_{\nu,\,2},\caF, \nu\right)}\,d\epsilon\,.
\]
Here, the supremum is taken over all finitely discrete probability distributions $\nu$ on $(\cX,\cF)$ and $\|f\|_{\nu,\,2}$ denotes the norm of a function $f$ in $\bL^2(\nu)$.
\end{defi}

\begin{lemm}\label{lem:upper bound Ek power type tail}
There exists a universal constant $K$ such that for any integer $k\geq 1$,
\[
\frac{1}{k}\,\bE\sup_{g\,\in\,\caG}\left|\sum_{j=1}^k Y_jg(X_j)\right| \leq K\,\frac{\ell}{\ell-2}\left(k^{-1/2}J(\delta,\caG) +\ell\,k^{-(1-1/\ell)}\left(\dfrac{J^2(\delta,\caG)}{\delta^2}\right)^{1-1/\ell}\,\right).
\]
\end{lemm}

\begin{rema}
For a numerical value of the (universal) constant $K$, we refer the reader to~\cite[Section~3.5.1]{GN16} in the book of Giné and Nickl. Moreover, the terms $\ell/(\ell-2)$ and $\ell$ are certainly not optimal and could be improved. They are given for the sake of completeness.
\end{rema}

The result of van der Vaart and Weller deals with bounded empirical processes. The proof of Lemma~\ref{lem:upper bound Ek power type tail} is based on a truncation argument associated with their result. Chernozhukov, Chetverikov and Kato~\cite[Theorem~5.2]{CCK14} have extended the result of van der Vaart and Wellner to unbounded empirical processes. In our setting, it provides the following upper bound:
\begin{multline}\label{eqn:upper bound expected value EP CCK eq1}
\frac{1}{k}\,\bE\sup_{g\,\in\,\caG}\left|\sum_{j=1}^k Y_jg(X_j)\right| \\ \leq K\left(k^{-1/2}\sqrt{\frac{\ell}{\ell-2}} J(\delta,\cG)+k^{-1}\frac{J^2(\delta,\cG)}{\delta^2}\left\|\max_{j=1,\,\ldots,\,k}M_j\right\|_2\right),
\end{multline}
where $K$ is a universal constant. Using now Pisier Lemma~\eqref{eqn:Pisier lemma} to bound above $\|\max_{j=1,\,\ldots,\,k}M_j\|_2$, \eqref{eqn:upper bound expected value EP CCK eq1} becomes
\begin{equation}\label{eqn:upper bound expected value EP CCK eq2}
\frac{1}{k}\,\bE\sup_{g\,\in\,\caG}\left|\sum_{j=1}^k Y_jg(X_j)\right| \leq K\,\sqrt{\frac{\ell}{\ell-2}}\left(k^{-1/2} J(\delta,\cG)+k^{-(1-1/\ell)}\frac{J^2(\delta,\cG)}{\delta^2}\right).
\end{equation}


Compared to Lemma~\ref{lem:upper bound Ek power type tail}, the constants in $\ell$ are better. Namely, in place of the terms $\ell/(\ell-2)$ and $\ell$ in Lemma~\ref{lem:upper bound Ek power type tail}, the right-hand side of~\eqref{eqn:upper bound expected value EP CCK eq2} contains the smaller terms $\sqrt{\text{\small{$\ell/(\ell-2)$}}}$ and $1$ respectively. However, the exponent of the term $J^2(\delta,\cG)/\delta^2$, which is $(1-1/\ell)$ in Lemma~\ref{lem:upper bound Ek power type tail}, leads to a better estimate as $\delta$ is small compared to the exponent $1$ in~\eqref{eqn:upper bound expected value EP CCK eq2}. Indeed, if $\log N(\epsilon\|F\|_{\nu,\,2},\caF, \nu)$ is not larger than $H(1/\varepsilon)$ for some nondecreasing function $H$, independent of $\nu$ and satisfying some minor conditions, then $J^2(\delta,\cG)/\delta^2$ is of an order of $H(1/\delta)$ which then increases as $\delta$ tends to $0$ (see, for instance, \cite[Theorem~3.5.6]{GN16}). We stress out that such an hypothesis on the covering number applies in many situations including VC-classes of functions. Nevertheless, the generality of Chernozhukov, Chetverikov and Kato's result makes it possible to upper bound the $E_k$'s in other cases than the one considered here.

We now apply Theorem~\ref{thm:Rosenthal strong} combined with Lemmas~\ref{lem:upper bound Vn power type tail} and~\ref{lem:upper bound Ek power type tail}.

\begin{theo}\label{thm:result power type tail}
Let $Z$ be defined by~\eqref{eqn:def Z power type tail}.
\begin{enumerate}\romanenumi
\item Assume that $\ell\in\intervalleof 24$ and $\|M_1\|_\ell\leq 1$. Then
\begin{multline}\label{theo2.11.a}
\tag{$\rm a$}
\left\|Z-\bE[Z]\right\|_\ell\\
\leq(\ell-1)^{1/\ell}\sqrt{n}\left(\sigma+K_\ell\,\left(n^{-\frac 14\frac{\ell-2}{\ell-1}}(J(\delta,\caG))^{\frac 12\frac{\ell-2}{\ell-1}}+n^{-\frac 12(1-2/\ell)}\left(\frac{J(\delta,\caG)}{\delta}\right)^{1-2/\ell}\,\right)\right) \\+ \left(2^{1/\ell}+1\right)n^{1/\ell}.
\end{multline}
\item Moreover, for any $\ell>2$,
\begin{multline}\label{theo2.11.b}
\tag{$\rm b$}
\tilde\Lambda_\ell^+(Z-\bE[Z])\\
\leq \sqrt{(p/e)}\sqrt n\,\left(\sigma+K_\ell\,\left(n^{-\frac 14\frac{\ell-2}{\ell-1}}(J(\delta,\caG))^{\frac 12\frac{\ell-2}{\ell-1}}+n^{-\frac 12(1-2/\ell)}\left(\frac{J(\delta,\caG)}{\delta}\right)^{1-2/\ell}\,\right)\right)\\+3\,n^{1/\ell}\mu_\ell,
\end{multline}
and
\begin{multline}\label{theo2.11.c}
\tag{$\rm c$}
\tilde\Lambda_p^+(\bE[Z]-Z)\\
\leq \sqrt{(p/e)}\sqrt n\,\left(\sigma+K_\ell\,\left(n^{-\frac 14\frac{\ell-2}{\ell-1}}(J(\delta,\caG))^{\frac 12\frac{\ell-2}{\ell-1}}+n^{-\frac 12(1-2/\ell)}\left(\frac{J(\delta,\caG)}{\delta}\right)^{1-2/\ell}\,\right)\right)\\+n^{1/\ell}\mu_\ell,
\end{multline}
where $\mu_\ell=2+\max(4/3,\ell/3)$.
\end{enumerate}
\end{theo}

Let us compare with the bounded case: $Y_k\leq 1$ for all $k=1,\,\ldots,\,n$. Integrating Rio's inequality for suprema of bounded empirical processes~\cite[Theorem~1]{Rio02} and using Lemma~\ref{lem:upper bound Ek power type tail}, one obtains for any $\ell>2$,
\begin{align}\label{eqn:bounded Bennett Rio}
\left\|(Z-\bE[Z])_+\right\|_\ell &\leq C_\ell\sqrt n\sqrt{\sigma^2+2\,\bE[Z]/n}\\
&\leq C_\ell\sqrt n\,\left(\sigma + K_\ell\left(n^{-1/4}\sqrt{J(\delta,\caG)}+n^{-1/2}\,\frac{J(\delta,\caG)}{\delta}\right)\right).
\end{align}
Notice that the term
\[
n^{-\frac 14\frac{\ell-2}{\ell-1}}(J(\delta,\caG))^{\frac 12\frac{\ell-2}{\ell-1}}+n^{-\frac 12(1-2/\ell)}\left(\frac{J(\delta,\caG)}{\delta}\right)^{1-2/\ell}
\]
in Theorem~\ref{thm:result power type tail} tends to $n^{-1/4}\sqrt{J(\delta,\caG)}+n^{-1/2}\,J(\delta,\caG)/\delta$ as $\ell$ tends to $\infty$. Thus, we can see our results as extensions of~\eqref{eqn:bounded Bennett Rio} to the unbounded case.

\section{Upper bounds on \texorpdfstring{$\bE[(Z-\bE[Z]-t)^\alpha_+]$}{} and \texorpdfstring{$Q_2(\bE[Z]-Z;u)$}{}}\label{section:bounds generalized moments}
In this section, we provide a general upper bound on $\bE[(Z-\bE[Z]-t)^\alpha_+]$, where $t\in\bR$, $\alpha\geq 1$, in terms of generalized quantiles. In order to explain the result, we start by considering the case $\alpha=1$ which is based on Theorem~\ref{thm:FukNagaev from Rio right}. We emphasize that it is of interest to obtain such bounds in various situations coming from statistical applications, such as study of rates of convergence for estimators (see, for instance, Comte and Lacour~\cite{CL13}).

\subsection{Case \texorpdfstring{$\alpha=1$}{}}
Let $X$ be an integrable real-valued random variable and let $t\in\bR$. Since $Q_X(U)$ and $X$ have the same distribution for any random variable $U$ uniformly distributed on $\intervalleff 01$,
\begin{equation}\label{eqn:case alpha=1 eq1}
\bE\left[(X-t)_+\right]=\int_0^1(Q_X(s)-t)_+ds\,.
\end{equation}
Now, recalling that $x<Q_X(u)$ if and only if $\bP(X>x)>u$, we get
\begin{equation}\label{eqn:case alpha=1 eq2}
\int_0^1(Q_X(s)-t)_+ds=\int_0^{\bP(X>t)}(Q_X(s)-t)ds=\sup_{u\,\in\,]0,\,1]}\int_0^u(Q_X(s)-t)ds\,.
\end{equation}
Note that the right-hand side of~\eqref{eqn:case alpha=1 eq2} is equal to $\sup_{u\,\in\,\intervalleof 01} u(\tilde Q_X(u)-t)$. Combining this fact with~\eqref{eqn:case alpha=1 eq1} leads to the following variational formula
\begin{equation}\label{eqn:case alpha=1 eq3}
\bE[(X-t)_+]=\sup_{u\,\in\,]0,\,1]} u(\tilde Q_X(u)-t)\,.
\end{equation}
Thus, from the upper bound on $\tilde Q_{Z-\bE[Z]}$ given in Theorem~\ref{thm:FukNagaev from Rio right} we derive the following:

\begin{prop}\label{prop:bound stat appli}
Let $Z$ be defined by~\eqref{eqn:def Z}. Let $p>2$ and $\mu_{\ell}=2+\max(4/3,p/3)$. Set also
\[
s_n:=\sqrt{n}\left(\sigma+\sqrt{v_n}\right),\text{ and } b_{n,\,p}:=3\,n^{1/p}\mu_p\,\Lambda_p^+(M_1)\,.
\]
Then, for any $t>0$,
\[
\bE\left[(Z-\bE[Z]-t)_+\right]\leq s_n\,\frac{e^{-\frac12\left(1+t^2/s_n^2\right)}}{\sqrt{1+t^2/s_n^2}}+b_{n,\,p}\,.
\]
\end{prop}

\begin{rema}
A similar upper bound on $\bE[(\bE[Z]-Z-t)_+]$ can be obtain by using Theorem~\ref{thm:FukNagaev from Rio left} instead of Theorem~\ref{thm:FukNagaev from Rio right}.
\end{rema}

The variational formula~\eqref{eqn:case alpha=1 eq3} gives a direct advantage of having an upper bound on the CVaR instead of on the log-Laplace transform of $Z-\bE[Z]$, since the calculation we have to do is more straightforward. Indeed, to obtain an upper bound on $\bE[(Z-\bE[Z]-t)_+]$ from an upper bound on the log-Laplace transform, we first have to derive a deviation inequality by Markov's inequality and then to integrate it from $t$ to $+\infty$.

\subsection{Case \texorpdfstring{$\alpha\geq1$}{}} In this section, we want to generalize the variational formula~\eqref{eqn:case alpha=1 eq3} to $\bE[(X-t)_+^\alpha]$, $\alpha\geq 1$. To this end, we consider the generalized quantiles $Q_\alpha(X;u)$, $\alpha\geq 1$, introduced by Pinelis~\cite[Section~3]{Pinelis14b}. In particular, note that $Q_1(X;u)=\tilde Q_X(u)$. The general definition is somehow complicated, so we do not recall it. However, Pinelis proves the following formula (see~\cite[Theorem~3.3]{Pinelis14b}):
\begin{equation}\label{eqn:def generalized quantiles}
Q_\alpha(X;u)=\inf_{s\,\in\,\bR}\left\{s+u^{-1/\alpha}\|(X-s)_+\|_\alpha\right\}.
\end{equation}


For properties on these quantiles, the reader is referred to~\cite[Theorem~3.4]{Pinelis14b}. We only recall that $Q_\alpha(X;u)$ is nondecreasing in $\alpha$, subadditive in $X$, and $Q_\alpha(X;u)\linebreak\leq \ell^{*-1}_X(\log(1/u))$ for all $\alpha\geq 1$. From Sion's minimax theorem, we derive the following variational formula which generalizes~\eqref{eqn:case alpha=1 eq3}:

\begin{lemm}\label{lem:variational formula generalized moments}
Let $\alpha\geq 1$. Let $X$ be an integrable real-valued random variable. Then
\[
\left\|(X-t)_+\right\|_\alpha= \sup_{u\,\in\,]0,\,1]}u^{1/\alpha}\left(Q_\alpha(X;u)-t\right).
\]
\end{lemm}

The interest of these generalized quantiles $Q_\alpha$ in our setting is similar to that of the CVaR $\tilde Q$. Indeed, our method lies in a decomposition of $Z-\bE[Z]$ into a sum of two martingales. The subadditivity property allows to analyze each martingale separately. Moreover, some comparison inequalities on real-valued martingales directly give upper bounds on their quantiles $Q_\alpha$: see, for instance, Bentkus~\cite{Bentkus04} for cases with $\alpha\in\{1,2,3\}$ or Pinelis~\cite{Pinelis06,Pinelis14a} for cases with $\alpha\in\{3,5\}$. In the next statement, we give an example of such bounds in the case $\alpha=2$ for $\bE[Z]-Z$ and under the additional assumption that the random variables $X_{1,\,t}$, $t\in\cT$, are bounded from below.

\begin{prop}\label{prop:functions bounded below}
Assume that for all $t\in\cT$, $X_{1,\,t}\geq -1$. Let $Z$ be defined by~\eqref{eqn:def Z}. Let $\theta_1,\,\ldots,\,\theta_n$ be a sequence of iid two-valued centered random variables taking the values $1$ and $-\sigma^2$. Set $B_n:=\sum_{k=1}^n \theta_k$. Then for any $u\in\intervalleof 01$,
\begin{align}
Q_2\left(\bE[Z]-Z;u\right)&\leq Q_2(B_n;u)+\sqrt{n}\,\sqrt{2v_n\log(1/u)}\,.\tag{$\rm a$}\label{prop3.4.a}\\
\intertext{Consequently,}
\left\|(\bE[Z]-Z-t)_+\right\|_2&\leq \|(B_n-t)_+\|_2+\sqrt {nv_n}\,\sqrt{(2/e)}\,.\tag{$\rm b$}\label{prop3.4.b}
\end{align}
\end{prop}

\begin{rema}
If $\sigma^2\geq 1$, then (see, for instance, \cite[Lemma~2.36]{BDR15} in Bercu, Delyon and Rio)
\begin{equation}
Q_2(B_n;u)\leq \ell_{B_n}^{*-1}(\log(1/u))\leq \sigma \sqrt{2n\log(1/u)}\,.
\end{equation}
Thus, inequality~\eqref{prop3.4.a} of Proposition~\ref{prop:functions bounded below} provides a sub-Gaussian bound. If $\sigma^2<1$, the inequality above does not hold. However, one has
\begin{equation}
Q_2(B_n;u)\leq \ell_{B_n}^{*-1}(\log(1/u))\leq \sigma \sqrt{2n\log(1/u)}+\frac{1-\sigma^2}{3}\log(1/u)\,.
\end{equation}
We refer the reader to~\cite[Theorem~2.28 and Exercise~6 in Section~2.9]{BDR15} for a proof.
\end{rema}

\section{Left deviation inequalities}\label{section:left deviation inequalities}
As mentioned in Section~\ref{section:FukNagaev Rosenthal}, the left tails are easier to handle than the right tails. Notably, the left-hand side deviations of $Z$ heavily depend on the behavior of the left tails of $X_{1,\,t}$, $t\in\cT$. For example, in Theorem~\ref{thm:FukNagaev from Rio right}, the term $\Lambda_p^+(M_1)$ involves the behavior of right and left tails, while the term $m_r$ in Theorem~\ref{thm:FukNagaev from Rio left} only involves the behavior of the left tails. In this section, we give left deviation inequalities under the additional assumption on the $X_{k,\,t}$'s, of sub-Gamma tails on the left, and of sub-Gaussian tails on the left (our terminology follows~\cite{BLM13}).

\subsection{Under sub-Gamma tails on the left assumption}\label{subsection:sub-Gamma}
Here we assume that $X_{1,t}$ admits a sub-Gamma tail on the left for all $t\in\cT$. To the best of our knowledge, there exists only one exponential inequality for the left-hand side deviations of suprema of empirical processes in the unbounded case (from one side) which is due to Klein~\cite{Klein02}. More precisely, Klein provides an upper bound on the Laplace transform of $\bE[Z]-Z$ which implies the following deviation inequality:
\begin{theo}[{\cite[Theorem~1.1$\MK$(3)]{Klein02}}]
Assume that $X_{1,\,t}\leq 1$ for all $t\in\cT$, and for all integer $p\geq 2$, $|\bE[X_{1,\,t}^p]|\leq \sigma^2 p!/2$. Then
\begin{equation*}
\bP\left(Z< \bE[Z] -\sqrt{2x\tilde V_n}-x-\frac{x\sqrt{2\tilde V_n}}{\sqrt{x}+\sqrt{\tilde V_n/2}}\,\right)\leq \exp(-x),
\end{equation*}
where $\tilde V_n=n\sigma^2+2\,\bE[Z]$.
\end{theo}

The objective here, is to relax the boundedness assumption on the right. Our main result is the following:

\begin{theo}\label{thm:sub-Gamma}
Assume that there exists a positive constant $c$ such that for any $t\in\cT$ and any $\lambda\in\intervalleoo 0c$,
\begin{equation}\label{eqn:hyp thm sub-Gamma}
\log \bE[\exp(-\lambda X_{1,\,t})]\leq \frac{\sigma^2 \lambda^2}{2(1-c\lambda)}\,.
\end{equation}
Let $Z$ be defined by~\eqref{eqn:def Z}. Then for any $u\in\intervalleoo 01$,
\begin{align}
&\tilde Q_{\bE[Z]-Z}(u)\leq \sqrt{2n\log(1/u)}\left(\sigma+\sqrt{v_n}\,\right)+c\log(1/u) \tag{$\rm a$}\label{theo4.2.a}\,.
\\
\intertext{Consequently, for any $x>0$,}
&\bP\left(Z<\bE[Z]-\sqrt{2nx}\left(\sigma+\sqrt{v_n}\,\right)-cx\right)\leq \exp(-x) \tag{$\rm b$}\label{theo4.2.b}\,.
\end{align}
\end{theo}

\begin{rema}
If the random variables $X_{1,\,t}$, $t\in\cT$, satisfy Bernstein's moment conditions on the left, then the hypothesis~\eqref{eqn:hyp thm sub-Gamma} above is satisfied. Precisely, assume that there exists a positive constant $c$ such that, for any integer $p\geq 3$, and all $t\in\cT$,
\begin{equation}
\bE\left[(-X_{1,\,t})_+^p\right]\leq\frac{p! c^{p-2}}{2}\sigma^2.
\end{equation}
Then, since $\bE[X_{1,\,t}]=0$ for all $t\in\cT$, $\log \bE[\exp(-\lambda X_{1,\,t})]\leq \frac{\sigma^2 \lambda^2}{2(1-c\lambda)}$. We refer the reader to Bercu, Delyon and Rio (see~\cite[the proof of their Theorem~2.1]{BDR15}) for a proof.
\end{rema}

\subsection{Under sub-Gaussian tails on the left assumption}\label{subsection:sub-Gaussian}
Here we assume that $X_{1,\,t}$ admits a sub-Gaussian tail on the left for all $t\in\cT$. We show in the following theorem that $Z-\bE[Z]$ is sub-Gaussian on the left.

\begin{theo}\label{thm:sub-Gaussian}
Assume that
\begin{equation}\label{eqn:hyp thm sub-Gaussian}
C(\cT):=\sup_{\lambda\,>\,0}\sup_{t\,\in\,\cT}\frac {2}{\lambda^2}\log \bE\left[\exp(-\lambda X_{1,\,t})\right]<\infty.
\end{equation}
Let $Z$ be defined by~\eqref{eqn:def Z}. Then for any $u\in\intervalleoo 01$,
\begin{align}
\tilde Q_{\bE[Z]-Z}(u)
\leq \sqrt{2n\log(1/u)}\left(\sqrt{C(\cT)}+\sqrt{v_n}\,\right) \tag{$\rm a$}\label{theo4.4.a}.
\\
\intertext{Consequently, for any $x>0$,}
\bP(Z<\bE[Z]-x)\leq \exp\left(-\frac{x^2}{2n\left(\sqrt{C(\cT)}+\sqrt{v_n}\,\right)^2}\right)\tag{$\rm c$}\label{theo4.4.c}.
\end{align}
\end{theo}

If for all $t\in\cT$, $X_{1,\,t}$ is a centered Gaussian random variable with variance equals to $\sigma_t^2$, then we can apply the above result with $C(\cT)=\sup_{t\,\in\,\cT}\sigma^2_t=:\sigma^2$. However we can prove the more precise following result:

\begin{prop}\label{prop:upper bound gaussian marginals}
Assume that for any $t\in\cT$, $X_{1,\,t}$ is a centered Gaussian random variable. Let then $\sigma^2:=\sup_{t\,\in\,\cT} \Var(X_{1,\,t})$. Let $Y$ be a standard Gaussian random variable. Then for any $u\in\intervalleoo 01$,
\[
\tilde Q_{\bE[Z]-Z}(u)\leq \sigma\sqrt n\,\tilde Q_Y(u)+\sqrt{2n\log(1/u)}\,\sqrt{v_n}
\]
\end{prop}

Note that, even if $X_1,\,\ldots,\,X_n$ are iid Gaussian vectors, this result is beyond the scope of Cirel'son, Ibragimov, and Sudakov's paper~\cite{CIS76} since $S_{n,\,t}$, $t\in\cT$, is not a Gaussian process in general.

\begin{exam}
Let $Y_1,\,\ldots,\, Y_n$ be a finite sequence of nonnegative iid random variables and let $X_1,\,\ldots,\, X_n$ be a finite sequence of iid random variables with values in some measurable space $(\cX,\cF)$ such that the two sequences are independent. Let $\cT$ be a countable set, $(A_t)_{t\,\in\,\cT}$ a family of Borel sets in $\cX$ and $(\sigma_t)_{t\,\in\,\cT}$ a family of positive reals such that $\sigma:=\sup_{t\,\in\,\cT}\sigma_t<\infty$. Then Proposition~\ref{prop:upper bound gaussian marginals} applies to
\[
Z:=\sup_{t\,\in\,\cT}\sum_{k=1}^n Y_k\left(2\,\ind_{X_k\,\in \,A_t}-1\right)\,.
\]
\end{exam}


\section{Proofs}\label{section:proofs}
\subsection{Preliminaries}
The starting point of the proofs is based on a martingale decomposition of $Z$ which we now recall. We suppose that $\cT$ is a finite class of functions, that is $\cT=\{t_i : i\in\{1,\,\ldots,\,m\}\}$. The results in the countable case are derived from the finite case using the monotone convergence theorem. Set $\cF_0:=\{\varnothing,\Omega\}$ and for all $k=1,\,\ldots,\,n$, $\cF_k:=\sigma(X_1,\,\ldots, \,X_k)$ and $\cF_n^k:=\sigma(X_1,\,\ldots,\,X_{k-1},X_{k+1},\,\ldots,\,X_n)$. Let $\bE_k$ (respectively $\bE_n^k$) denote the conditional expectation operator associated with $\cF_k$ (resp. $\cF^k_n$). Set also
\begin{align}
Z_k&:=\bE_k[Z],\\
Z^{(k)}&:=\sup\left\{S_{n,\,t}-X_{k,t}+nc_t : t\in\cT\right\}. \label{eqn:def Z^k}
\end{align}
The sequence $(Z_k)$ is an $(\cF_k)$-adapted martingale (the Doob martingale associated with $Z-\bE[Z]$) and
\begin{equation}\label{eqn:decomposition Doob Z}
Z-\bE[Z]=\sum_{k=1}^n \Delta_k,\quad \text{ where }\Delta_k:=Z_k-Z_{k-1}\,.
\end{equation}
Define now the random indices $\tau$ and $\tau_k$, respectively $\cF_n$-measurable and $\cF_n^k$-measurable, by
\begin{align}
\tau &:=\inf\left\{i\in\left\{1,\,\ldots,\,m\right\} : S_{n,t_i}+nc_{t_i}=Z\right\},\\
\tau_k &:=\inf\left\{i\in\{1,\,\ldots,\,m\} : S_{n,t_i}-X_{k,t_i}+nc_{t_i}=Z^{(k)}\right\}.
\end{align}
Notice first that
\[
Z^{(k)}+X_{k,\,t_{\tau_k}}\leq Z\leq Z^{(k)}+X_{k,\,\,t_\tau}.
\]
From this, conditioning by $\cF_k$ gives
\begin{equation}\label{eqn:proof decomposition martingale eq1}
\bE_k\left[X_{k,\,t_{\tau_k}}\right]\leq Z_k-\bE_k\left[Z^{(k)}\right]\leq\bE_k\left[X_{k,\,t_\tau}\right].
\end{equation}
Set now $\xi_k:=\bE_k[X_{k,\,t_{\tau_k}}]$ and let $\varepsilon_k\geq r_k\geq 0$ be random variables such that
\[
\xi_k+r_k=Z_k-\bE_k\left[Z^{(k)}\right]\quad\text{ and }\quad \xi_k+\varepsilon_k=\bE_k\left[X_{k,\,t_\tau}\right].
\]
Thus~\eqref{eqn:proof decomposition martingale eq1} becomes
\begin{equation}\label{eqn:proof decomposition martingale eq2}
\xi_k\leq\xi_k+ r_k\leq \xi_k+\varepsilon_k\,.
\end{equation}
Since the random index $\tau_k$ is $\cF_n^k$-measurable, we have by the centering assumption on the random variables $X_{k,\,t}$, $t\in\cT$,
\begin{equation}\label{eqn:proof decomposition martingale eq3}
\bE_n^k\left[X_{k,\,t_{\tau_k}}\right] =0,
\end{equation}
which ensures that $\bE_{k-1}[\xi_k]=0$. Moreover, $\bE_k[Z^{(k)}]$ is $\cF_{k-1}$-measurable. Hence we get
\[
\Delta_k =Z_k-\bE_k\left[Z^{(k)}\right]-\bE_{k-1}\left[Z_k-\bE_k\left[Z^{(k)}\right]\right]= \xi_k + r_k -\bE_{k-1}[r_k],
\]
which, combined with~\eqref{eqn:decomposition Doob Z}, yields the decomposition of $Z-\bE[Z]$ into a sum of two martingales:
\begin{equation}\label{eqn:decomposition Z-EZ}
Z-\bE[Z]=\Xi_n +R_n,
\end{equation}
where
\begin{equation}\label{eqn:decomposition Z-EZ-def martingales}
\Xi_n:=\sum_{k=1}^n \xi_k \; \text{ and }\;R_n:= \sum_{k=1}^n \left(r_k-\bE_{k-1}[r_k]\right).
\end{equation}


The strategy of the proofs is to treat the two martingales separately. And the main difficulty lies in the control of their quadratic variations, especially that of $R_n$.
\begin{enumerate}\romanenumi
\item Upper bound on $\sum_{k=1}^n \bE_{k-1}[\xi_k^2]$.
\begin{lemm}\label{lem:upper bound quad var Xi}
One has
\[
\langle \Xi \rangle_n:=\sum_{k=1}^n \bE_{k-1}\left[\xi_k^2\right]\leq n\sigma^2.
\]
\end{lemm}
\end{enumerate}

\begin{proof}
First, notice that the same argument as in~\eqref{eqn:proof decomposition martingale eq3} yields
\[
\bE_n^k[X_{k,\,t_{\tau_k}}^2]\leq \sigma^2.
\]
Thus, Lemma~\ref{lem:upper bound quad var Xi} follows from the conditional Jensen inequality.
\end{proof}
\begin{enumerate}\romanenumi
\setcounter{enumi}{1}
\item Upper bound on $ \sum_{k=1}^n\bE_{k-1}[(r_k-\bE_{k-1}[r_k])^2]$.

We recall that $\zeta_k$ denotes a random variable with distribution function $F_{2\,M_1,\,q_k}$ (defined in Definition~\ref{def:distrib function}) where $q_k$ is such that $\bE[\zeta_k]=E_k$.
\end{enumerate}

\begin{lemm}\label{lem:upper bound quad var R}
One has
\[
\langle R \rangle_n:=\sum_{k=1}^n\bE_{k-1}\left[\left(r_k-\bE_{k-1}[r_k]\right)^2\right]\leq\sum_{k=1}^n \bE\left[\zeta_{k}^2\right].
\]
\end{lemm}


\begin{proof}
First, we observe that $\bE_{k-1}[r_k]$ is bounded by a deterministic constant. This will be a consequence of the following lemma of exchangeability of variables.


\begin{lemm}\label{lem:exchangeability}
For any integer $j\geq k$,
\[
\bE_{k-1}\left[X_{k,\,\tau}\right]=\bE_{k-1}\left[X_{j,\,\tau}\right].
\]
\end{lemm}


\begin{proof}[Proof of Lemma~\ref{lem:exchangeability}]
Pointing out that $\tau$ is a function of $X_1,\,\ldots,\,X_n$, one has for every permutation $\pi$ on $n$ elements,
\[
\tau(X_1,\,\ldots,\,X_n)=\tau\circ\pi(X_1,\,\ldots,\,X_n) \text{ almost surely,}
\]
leading to
\[
\bE_n^k[X_{k,\,\tau}]=\bE_n^k[X_{k,\,\tau\circ\pi}].
\]
This implies
\[
\bE_{k-1}[X_{k,\,\tau}]=\bE_{k-1}[X_{k,\,\tau\circ\pi}]\quad \text{for any }k=1,\ldots,n\,.
\]
Taking now $j\geq k$ and applying the previous equality to the transposition $\pi:=(k\,j)$ which exchanges $k$ and $j$, it yields by Fubini's theorem that
\[
\bE_{k-1}\left[X_{k,\,\tau}\right]=\bE_{k-1}\left[X_{j,\,\tau}\right],
\]
which concludes the proof.
\end{proof}

Therefrom,
\begin{equation}
\begin{aligned}
\bE_{k-1}[\varepsilon_k] &= \bE_{k-1}[X_{k,\,\tau}]\\
&=\frac{1}{n-k+1} \bE_{k-1}\left[X_{k,\tau}+\ldots+X_{n,\,\tau}\right]\\
&\leq \frac{1}{n-k+1} \,\bE_{k-1}\sup_{t\,\in\,\cT}\left\{X_{k,\,t}+\ldots + X_{n,\,t}\right\}=E_{n-k+1}\,.
\end{aligned}
\end{equation}
Since $0\leq r_k\leq\varepsilon_k$, we thus get
\[
0\leq \bE_{k-1}[r_k]\leq E_{n-k+1}\,.
\]

Next, \eqref{eqn:proof decomposition martingale eq2} implies that $0\leq r_k\leq 2M_k$. Therefore, the comparison inequality~\eqref{eqn:extension Hoeffding unbounded} ensures that for any function $\varphi\in\cH_+^1$, $\bE_{k-1}[\varphi(r_k)]\leq\bE[\varphi(\zeta_{n-k+1})]$. Since $r_k\geq0$ and $x\mapsto x_+^2$ belongs to $\cH_+^1$, we get
\[
\bE_{k-1}\left[\left(r_k-\bE_{k-1}[r_k]\right)^2\right]\leq\bE_{k-1}\left[r_k^2\right]=\bE_{k-1}\left[r_{k+}^2\right] \leq \bE\left[\zeta_{n-k+1}^2\right]\,.
\]
Finally, summing for $k=1,\,\ldots,\,n$ leads to
\begin{equation}\label{eqn:bound quad var R}
\sum_{k=1}^n\bE_{k-1}\left[\left(r_k-\bE_{k-1}[r_k]\right)^2\right] \leq \sum_{k=1}^n\bE\left[\zeta_k^2\right]=V_n,
\end{equation}
which ends the proof of Lemma~\ref{lem:upper bound quad var R}.
\end{proof}

Before proving the main results, let us explain why left deviation inequalities are easier to handle than the right ones.

\subsection{Upper bound on \texorpdfstring{$\tilde Q_{-R_n}$}{}}

To study the left deviations, we write
\begin{equation}\label{eqn:decomposition martingale}
\bE[Z]-Z=\Xi_n^o +R_n^o,
\end{equation}
where $\Xi_n^o=-\Xi_n$ and $R_n^o=-R_n$. We will control the martingales $\Xi_n$ and $\Xi_n^o$ in the same manner. For $R_n^o$, the above analysis implies that $R_n^o$ is a martingale with bounded from above increments and then it is a sub-Gaussian martingale as shown by the lemma below.

\begin{lemm}\label{lem:bound log-laplace R_n}
For any $t\geq 0$, we have
\begin{align}
\ell_{R_n^o}(t):=\log\bE\left[\exp\left(tR_n^o\right)\right]\leq \frac{t^2V_n}{2}\,.\tag{$\rm a$}\label{lemm5.4.a}
\\
\intertext{Consequently, for any $u\in \intervalleoo 01$,}
\tilde Q_{R_n^o}(u)\leq \ell_{R_n^o}^{*-1}\left(\log(1/u)\right)\leq \sqrt{2n\,v_n\log(1/u)},\tag{$\rm b$}\label{lemm5.4.b}
\end{align}
where $v_n=V_n/n$.
\end{lemm}


\begin{proof}
We recall that
\begin{equation}\label{eqn:proof lemma R_n eqn1}
\bE_{k-1}[r_k]-r_k\leq E_{n-k+1}\,\text{ and }\, \bE_{k-1}\left[\left(\bE_{k-1}[r_k]-r_k\right)^2\right]\leq \bE\left[\zeta_{n-k+1}^2\right].
\end{equation}
Thus, $\max(\bE[\zeta_k^2],E_k^2)=\bE[\zeta_k^2]$. Applying now the inequality for real-valued martingales with differences bounded from above proved by Bentkus~\cite{Bentkus03} (see his inequality (2.16)), we get for any $t\geq 0$,
\begin{equation}\label{eqn:proof lemma R_n eqn3}
\bE\left[\exp\left(tR_n^o\right)\right]\leq \exp\left(t^2V_n/2\right),
\end{equation}
which then gives~\eqref{lemm5.4.a}. Now, it is a classical calculation that
\begin{equation}
\inf_{t\,>\,0}\left\{\frac 1t \left(\frac{t^2V_n}{2}+x\right)\right\}=\sqrt{2\,V_n\,x}=\sqrt{2n\,v_n\,x},
\end{equation}
where the infimum is given by the optimal value $t_x=\sqrt{\text{\small{$2\,x/V_n$}}}$. Finally, \eqref{eqn:comparaison CVAR Leg} ends the proof of~\eqref{lemm5.4.b}.
\end{proof}

\subsection{Proofs of Section~\ref{section:FukNagaev Rosenthal}}

First, we recall some results concerning real-valued martingales. Let $M_n:=\sum_{k=1}^n \linebreak X_k$ be a martingale in $\bL^2$ with respect to a nondecreasing filtration $(\cF_k)$, such that $M_0=0$ and $\bE[X_k^2\mid\cF_{k-1}]\leq b_k^2$ almost surely for all $k=1,\ldots,n$, where $b_k$'s are some positive reals. Define
\[
B_n=\sqrt{\sum_{k=1}^n b_k^2}\,.
\]
We start by a Fuk--Nagaev type inequality obtained by Rio~\cite{Rio17a}:
\begin{theo}[{\cite[Theorem~4.1]{Rio17a}}]\label{thm:Fuk-Nagaev Rio}
Let $r>2$ such that
\[
\left\|\sup_{t\,>\,0}\left(t^r\,\bP(X_{k+}>t\middle|\cF_{k-1})\right)\right\|_\infty<\infty.
\]
Define
\[
C_r^w(M)=\left\|\sup_{t\,>\,0}\left(t^r\sum_{k=1}^n\bP\left(X_{k+}>t\middle|\cF_{k-1}\right)\right)\right\|_\infty^{1/r}\,.
\]
Then for any $u\in \intervalleoo 01$,
\begin{equation*}
\tilde{Q}_{M_n}(u)\leq \sigma\sqrt{2\log(1/u)}+C_r^w(M)\mu_r u^{-1/r},
\end{equation*}
where $\mu_r:=2+\max(4/3,r/3)$.
\end{theo}

Next, we recall the following Rosenthal-type inequality obtain by Pinelis~\cite{Pinelis15}:
\begin{theo}[{\cite[Theorem~1 and inequality (10)]{Pinelis15}}]\label{thm:Rosenthal Pinelis}
Let $r\in\intervalleof 24$. Then
\[
\left\|M_n\right\|_r\leq (r-1)^{1/r} B_n + \left(\sum_{k=1}^n\bE\left[|X_k|^r\right]\right)^{1/r}.
\]
\end{theo}

We are now in a position to prove the main results.

\begin{proof}[Proof of Theorem~\ref{thm:FukNagaev from Rio right}]
First, observe that~\eqref{theo2.1.b} follows immediately from~\eqref{theo2.1.a} since for any real-valued random variable $X$ and any $u\in\intervalleoo 01$, one has $Q_X\leq \tilde Q_X$ and $\bP(X>Q_X(u))\leq u$. Let us now prove~\eqref{theo2.1.a}. Recalling the decomposition~\eqref{eqn:decomposition Z-EZ}, Proposition~\ref{prop:subadd CVaR} implies
\begin{equation}\label{eqn:dem thm FukNagaev from Rio eq1}
\tilde{Q}_{Z-\bE[Z]}(u)\leq \tilde{Q}_{\Xi_n}(u) + \tilde{Q}_{R_n}(u).
\end{equation}
With the notation of Rio's Theorem, since $\xi_k\leq M_k$ and $r_k-\bE_{k-1}[r_k]\leq 2M_k$, one has
\begin{align}
C_\ell^w(\Xi_n)&\leq n^{1/\ell}\Lambda_\ell^+(M_1),\label{eqn:dem FukNagaev from Rio eq3}
\\
C_\ell^w(R_n)&\leq 2\,n^{1/\ell}\Lambda_\ell^+(M_1).\label{eqn:dem FukNagaev from Rio eq4}
\end{align}
Recalling the bounds on the quadratic variations of $\Xi_n$ and $R_n$ given by Lemmas~\ref{lem:upper bound quad var Xi}-\ref{lem:upper bound quad var R}, we then conclude the proof of~\eqref{theo2.1.a} by combining~\eqref{eqn:dem thm FukNagaev from Rio eq1}--\eqref{eqn:dem FukNagaev from Rio eq4} and Theorem~\ref{thm:Fuk-Nagaev Rio}.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:upper bound Vn power type tail}]
By homogeneity, we may assume that $\Lambda_p^+(M_1)=1$. Let $\psi$ be a random variable with tail function defined by $\bP(\psi>t)=t^{-\ell}$ for all $t\geq 1$ and let $\tilde{\zeta}_k$ be a random variable with distribution function $F_{2\psi,\,\tilde{q}_k}$, where $\tilde q_k$ is the real in $[0,1]$ such that $\bE[\tilde{\zeta}_k]=E_k$. Clearly,
\[
F_{2M_1,\,q_k}(x)\geq F_{2\psi,\,\tilde{q}_k}(x)\text{ for any } x\in\bR.
\]
In other words, $\tilde \zeta_k$ dominates $\zeta_k$ for the first-order stochastic dominance. Then~\cite[Lemma~1]{Bentkus08a} of Bentkus ensures that for any convex function $\varphi$,
\begin{equation}
\bE[\varphi(\zeta_k)]\leq \bE[\varphi(\tilde\zeta_k)]\,.
\end{equation}
Thus, applying this inequality to $\varphi(x)= x^2$,
\begin{equation}\label{eqn:comparison xi tildexi}
\bE\left[\zeta_k^2\right]\leq \bE\left[\tilde\zeta_k^2\right].
\end{equation}
Moreover, a straightforward calculation yields that
\begin{equation}\label{eqn:bound tilde xi}
\bE\left[\tilde\zeta_k^2\right]\leq 2^{\frac{p}{p-1}}\,\frac{p}{p-2}\left(1-\frac{1}{p}\,\right)^{(p-2)/(p-1)}E_k^{(p-2)/(p-1)}.
\end{equation}
The claim follows by summing for $k=1,\,\ldots,\,n$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:FukNagaev from Rio left}]
As for the right deviations, we only have to prove~\eqref{theo2.5.a}. We recall that $\bE[Z]-Z=\Xi_n^o+R_n^o$. We shall use Rio's inequality again to control $\Xi_n^o$ and the Gaussian upper bound Lemma~\ref{lem:bound log-laplace R_n} to control $R_n^o$. Contrary to the previous proof, since we do not use Rio's inequality on $R_n^o$, it is interesting to provide a better upper bound on $C_r^w(\Xi_n^o)$. First, by Markov's inequality,
\begin{equation}\label{eqn:proof FukNagaev Rio left eq1}
C_r^w(\Xi_n^o)\leq \left\|\sum_{k=1}^n\bE_{k-1}\left[\left(-\xi_{k}\right)_+^r\right]\right\|_\infty^{1/r}.
\end{equation}
Furthermore, using the same trick as in~\eqref{eqn:proof decomposition martingale eq3}, we obtain
\begin{equation}\label{eqn:proof FukNagaev Rio left eq2}
\bE_{k-1}\left[(-\xi_{k})_+^r\right]\leq m_r^r\,.
\end{equation}
Combining now~\eqref{eqn:proof FukNagaev Rio left eq1}-\eqref{eqn:proof FukNagaev Rio left eq2}, Theorem~\ref{thm:Fuk-Nagaev Rio} and Lemma~\ref{lem:bound log-laplace R_n} ends the proof.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:weak moment ineq from Rio}]
First, observe that~\eqref{coro2.6.a} and~\eqref{coro2.6.c} follow directly from~\eqref{eqn:bound Lambda by tildeLambda}. Let us now prove~\eqref{coro2.6.b}. We proceed exactly as in Rio~\cite[Theorem~5.1]{Rio17a}. Both~\eqref{eqn:def weak norm tilde} and Theorem~\ref{thm:FukNagaev from Rio right}$\MK$\eqref{theo2.1.a} imply
\begin{equation}
\tilde\Lambda_\ell^+(Z-\bE[Z])\leq \left(\sigma\sqrt{n}+\sqrt{V_n}\,\right)\sup_{u\,\in\,]0,\,1]}\left(u^{1/\ell}\sqrt{2\log(1/u)}\,\right)+3\,n^{1/\ell}\mu_\ell\,\Lambda_\ell^+\left(\Phi(X_1)\right).
\end{equation}
Next, observe that $\sup_{u\,\in\,]0,\,1]}u^{1/\ell}\sqrt{2\log(1/u)}= \sqrt{(\ell/e)}$, which concludes the proof of~\eqref{coro2.6.b}. The same is done for the proof of~\eqref{coro2.6.d} by using Theorem~\ref{thm:FukNagaev from Rio left}$\MK$\eqref{theo2.5.a} instead of Theorem~\ref{thm:FukNagaev from Rio right}$\MK$\eqref{theo2.1.a}.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:Rosenthal strong}]
First, we apply Theorem~\ref{thm:Rosenthal Pinelis} to the martingale $\Xi_n$. Then, it follows from Lemma~\ref{lem:upper bound quad var Xi} and the definition of $M_k$ that
\begin{equation}\label{eqn:proof thm Rosenthal strong Xi}
\|\Xi_n\|_p\leq (p-1)^{1/p}\sigma\sqrt n +n^{1/p} \|M_1\|_p\,.
\end{equation}
Next, we do the same for the martingale $R_n$, using Lemma~\ref{lem:upper bound quad var R} instead of Lemma~\ref{lem:upper bound quad var Xi}. We only need to handle $\bE[|r_k-\bE_{k-1}[r_k]|^p]$. It is done by the following:
\begin{lemm}\label{lem:moment nonnegative rv recentered}
$\bE[|r_k-\bE_{k-1}[r_k]|^p]\leq \bE[|r_k|^p]$.
\end{lemm}

This result only uses the fact that $r_k$ is a nonnegative random variable. It is a probably known fact, but for sake of completeness, we give a proof in Appendix~\ref{section:Appendix A}. Now, since $0\leq r_k\leq 2\,M_k$, we deduce that
\begin{equation}\label{eqn:proof thm Rosenthal strong R}
\|R_n\|_p\leq (p-1)^{1/p}\sqrt{nv_n}+2^{1/p}n^{1/p} \|M_1\|_p\,.
\end{equation}
The claim follows by combining~\eqref{eqn:proof thm Rosenthal strong Xi} and~\eqref{eqn:proof thm Rosenthal strong R}.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:upper bound Ek power type tail}]
As in the proof of Lemma~\ref{lem:upper bound Vn power type tail}, $\psi$ denotes a random variable such that $\bP(X>t)=t^{-\ell}$ for all $t\geq1$. Notice that $Q_\psi(u)=u^{-1/\ell}$ for any $u\in \intervalleoo 01$ and that~\eqref{eqn:def envelope power type tail} implies $Q_Y\leq Q_\psi$. Let also $\kappa\in\bR$ be such that
\begin{equation}\label{eqn:def kappa}
2^\kappa = \frac{k\,\delta^2}{J^2(\delta,\caG)}\,.
\end{equation}
Let $U_1,\,\ldots,\,U_k$ be $k$ independent copies of a random variable $U$ distributed uniformly on $\intervalleff 01$. Let us now define for every $j=1,\,\ldots,\,\lceil\kappa\rceil$,
\begin{align*}
I_j &:= \left\{ m\in\{1,\,\ldots,\,k\} : U_m\in\intervalleof {2^{-j}}{ 2^{1-j}} \right\}, \\
J_\kappa &:= \left\{ m\in\{1,\,\ldots,\,k\} : U_m\leq 2^{-\lceil\kappa\rceil}\right\}.
\end{align*}
Here, $\lfloor. \rfloor$ and $\lceil.\rceil$ denote the classical floor and ceiling functions. Recall that $Q_X(U)$ and $X$ have the same distribution. Then,
\begin{equation}\label{eqn:bound mean decomposition}
\bE\sup_{g\,\in\,\caG}\left|\sum_{j=1}^k Y_jg(X_j)\right|\leq \bfE_1 + \bfE_2,
\end{equation}
where
\[
\bfE_1:= \sum_{j=1}^{\lceil\kappa\rceil} \bE\sup_{g\,\in\,\caG}\left|\sum_{i\,\in\,I_j}Q_\psi(U_i)g(X_i)\right|\;\text{ and }\; \bfE_2:=\bE\sup_{g\,\in\,\caG}\left|\sum_{j\in J_\kappa}Q_\psi(U_j)g(X_j)\right|.
\]
Let us bound above $\bfE_2$. Since $G\leq 1$, a straightforward calculation gives
\begin{equation}\label{eqn:Final E_2}
\bfE_2 \leq k\int_0^{2^{-\lceil\kappa\rceil}} Q_\psi(u)\,du \leq k\, \frac{\ell}{\ell-1}\,2^{-\kappa(1-1/\ell)}.
\end{equation}
To bound above $\bfE_1$, we first notice that, since $Q_\psi$ is decreasing, for any $m\in I_j$, $|Y_mg(X_m)|\leq Q_\psi(2^{-j})$. We can then apply~\cite[Theorem~2.1]{vdVW11} of Van der Vaart and Wellner which leads to
\begin{equation}\label{eqn:E_1 eq1}
\bfE_1\leq K\left(J(\delta,\caG)\sum_{j=1}^{\lceil\kappa\rceil} \bE\left[|I_j|^{\frac{1}{2}}\right]\,Q_\psi(2^{-j}) + \frac{J^2(\delta,\caG)}{\delta^2}\sum_{j=1}^{\lceil\kappa\rceil} Q_\psi(2^{-j})\right).
\end{equation}
By the definition of $I_j$, it is easy to see that
\[
\bE\left[|I_j|\right]=\sum_{i=1}^k i \binom{k}{i} (2^{-j})^i (1-2^{-j})^{k-i} = k\,2^{-j}.
\]
Then, Jensen's inequality yields $\bE[|I_j|^{\frac{1}{2}}]\leq \sqrt{k\,2^{-j}}$. Now, since $Q_\psi(u)=u^{-1/\ell}$,
\begin{equation}\label{eqn:Control E_1 eq1}
\sum_{j=1}^{\lceil\kappa\rceil} 2^{-j/2}Q_\psi(2^{-j}) \leq \frac{2^{1/\ell-1/2}}{1-2^{1/\ell-1/2}}\leq \frac{2}{\log(2)}\,\frac{\ell}{\ell-2}\,.
\end{equation}
Likewise,
\begin{equation}\label{eqn:Control E_1 eq2}
\begin{aligned}
\sum_{j=1}^{\lceil\kappa\rceil} Q_\psi(2^{-j}) &= 2^{\lfloor\kappa\rfloor /\ell}\left(2^{1/\ell}+\sum_{j=0}^{\lfloor\kappa\rfloor-1}2^{-j/\ell}\right)\\
&\leq 2^{\lfloor\kappa\rfloor /\ell}\left(2^{1/\ell}+\frac{1}{1-2^{-1/\ell}}\right)
\leq \frac{2^{\kappa/\ell}}{\log(2)}\,\frac{\ell^2}{\ell-2}\,.
\end{aligned}
\end{equation}
Hence, we derive from~\eqref{eqn:E_1 eq1}--\eqref{eqn:Control E_1 eq2},
\begin{equation}\label{eqn:Final E_1}
\bfE_1\leq K\,\frac{\ell}{\ell-2}\left(\sqrt{k}\,J(\delta,\caG) + \ell\,\frac{J^2(\delta,\caG)}{\delta^2}\,2^{\kappa/\ell}\right).
\end{equation}
Finally, \eqref{eqn:bound mean decomposition}, \eqref{eqn:Final E_1}, \eqref{eqn:Final E_2} and the definition of $\kappa$ imply Lemma~\ref{lem:upper bound Ek power type tail}.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:result power type tail}]
Inequality~\eqref{theo2.11.a} follows from Theorem~\ref{thm:Rosenthal strong}, Lemmas~\ref{lem:upper bound Vn power type tail}-\ref{lem:upper bound Ek power type tail} and the subadditivity of the functions $x\mapsto x^a$, for $0<a<1$. Similarly,~\eqref{theo2.11.b} and~\eqref{theo2.11.c} follow by using Corollary~\ref{cor:weak moment ineq from Rio} instead of Theorem~\ref{thm:Rosenthal strong} and the fact that $\Lambda_\ell^+(Y_1G(X_1))\leq\Lambda_\ell^+(\psi)=1$.
\end{proof}

\subsection{Proof of Section~\ref{section:bounds generalized moments}}

\begin{proof}[Proof of Proposition~\ref{prop:bound stat appli}]
Inequality~\eqref{eqn:case alpha=1 eq3} and Theorem~\ref{thm:FukNagaev from Rio right} ($a$) imply
\begin{equation}\label{eqn:bound variational expression eq1}
\begin{aligned}
\bE[(Z-\bE[Z]-t)_+]& \leq \sup_{u\,\in\,]0,\,1]} u\left(s_n\sqrt{2\log(1/u)}+b_{n,\,p}\,u^{-1/p} -t\right)\\\
&\leq \sup_{u\,\in\,]0,\,1]} u\left(s_n\sqrt{2\log(1/u)}-t\right)+b_{n,\,p},
\end{aligned}
\end{equation}
since $u^{1-1/p}\leq 1$. With the change of variables $y=\sqrt{\text{\small{$2\log(1/u)$}}}\in\intervallefo{0}{+\infty}$, the supremum is achieved at
\begin{equation}\label{eqn:bound variational expression eq2}
y_0:=\frac{t}{2\,s_n}+\sqrt{1+\frac{t^2}{4\,s_n^2}}\,.
\end{equation}
Then, the supremum in~\eqref{eqn:bound variational expression eq1} is equal to $s_n\,e^{-y_0^2/2}/y_0$. Observing now that\\ $y_0\geq \sqrt{\text{\small{$1+t^2/s_n^2$}}}$, we finally get the desired inequality which concludes the proof.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:variational formula generalized moments}]
Define $f:\intervalleff 01\times \bR\to\bR$ by
\[
f(u,s):=u^{1/\alpha}(s-t)+\left\|(X-s)_+\right\|_\alpha.
\]
Note that, since $\alpha\geq 1$, for any $s\in\bR$, $u\mapsto f(u,s)$ is concave and for any $u\in\intervalleff 01$, $s\mapsto f(u,s)$ is convex. Thus, we can apply Sion's minimax theorem~\cite{Sion58} which implies that
\begin{equation}\label{eqn:proof variational formula minimax theorem}
\sup_{u\,\in\,]0,\,1]}\inf_{s\,\in\,\bR} f(u,s)=\inf_{s\,\in\,\bR} \sup_{u\,\in\,]0,\,1]}.
\end{equation}
For any $s<t$,
\begin{equation}\label{eqn:proof variational formula eq1}
\|(X-t)_+\|_\alpha\leq\|(X-s)_+\|_\alpha= \sup_{u\,\in\,]0,\,1]} f(u,s).
\end{equation}
Moreover, for any $s>t$,
\begin{equation}\label{eqn:proof variational formula eq2}
\begin{aligned}
\|(X-t)_+\|_\alpha &= \|((X-s)+(s-t))_+\|_\alpha\\
&\leq \|(X-s)_+\|_\alpha +(s-t)\\
&=\sup_{u\,\in\,]0,\,1]} f(u,s).
\end{aligned}
\end{equation}


Thus, \eqref{eqn:proof variational formula eq1} and~\eqref{eqn:proof variational formula eq2} give
\begin{equation}\label{eqn:proof variational formula eq3}
\inf_{s\,\in\,\bR}\sup_{u\,\in\,]0,\,1]} f(u,s)=\|(X-t)_+\|_\alpha\,.
\end{equation}
Finally, we derive from~\eqref{eqn:def generalized quantiles} that
\begin{equation}\label{eqn:proof variational formula eq4}
\sup_{u\,\in\,]0,\,1]}(Q_\alpha(X;u)-t)=\sup_{u\,\in\,]0,\,1]}\inf_{s\,\in\,\bR} f(u,s)=\sup_{u\,\in\,]0,\,1]}\inf_{s\,\in\,\bR} f(u,s).
\end{equation}
The claim follows by combining~\eqref{eqn:proof variational formula eq4}, \eqref{eqn:proof variational formula minimax theorem} and~\eqref{eqn:proof variational formula eq3}
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:functions bounded below}]
Inequality~\eqref{prop3.4.b} directly follows from Lemma~\ref{lem:variational formula generalized moments} and~\eqref{prop3.4.a}. Let us prove~\eqref{prop3.4.a}. Recalling the decomposition~\eqref{eqn:decomposition martingale}, the subadditivity property of the quantile $Q_2$ yields that
\begin{equation}\label{eqn:proof functions bounded below eq1}
Q_2\left(\bE[Z]-Z;u\right)\leq Q_2\left(\Xi_n^o;u\right)+Q_2\left(R_n^o;u\right).
\end{equation}
Moreover, from the properties of $Q_2$ and Lemma~\ref{lem:bound log-laplace R_n},
\begin{equation}\label{eqn:proof functions bounded below eq2}
Q_2\left(R_n^o;u\right)\leq \ell_{R_n^o}^{*-1}(\log(1/u))\leq \sqrt{n}\,\sqrt{2v_n\log(1/u)}.
\end{equation}
Note that $-\xi_k=-\bE_k[X_{k,\,t_{\tau_k}}]\leq 1$ since we assume that $X_{1,\,t}\geq -1$ for all $t\in\cT$. Thus, $\Xi_n^o$ is a martingale with increments $(-\xi_k)$ satisfying
\begin{equation}\label{eqn:proof functions bounded below eq3}
-\xi_k\leq 1\quad\text{and}\quad \Var_{k-1}(-\xi_k)\leq\sigma^2.
\end{equation}
Then, one has the following comparison inequality (see, for instance, Bentkus\cite[Lemma~4.4]{Bentkus04}),
\begin{equation}\label{eqn:proof functions bounded below eq4}
\bE\left[(\Xi_n^o-t)_+^2\right]\leq\bE\left[(B_n-t)_+^2\right]\quad\text{for any }t\in\bR.
\end{equation}
Combined with~\eqref{eqn:def generalized quantiles}, it yields for any $u\in\intervalleof 01$,
\begin{equation}\label{eqn:proof functions bounded below eq5}
Q_2(\Xi_n^o;u)\leq Q_2(B_n;u).
\end{equation}
Finally, inequality~\eqref{prop3.4.a} follows from~\eqref{eqn:proof functions bounded below eq1}, \eqref{eqn:proof functions bounded below eq2} and~\eqref{eqn:proof functions bounded below eq5}.
\end{proof}

\subsection{Proofs of Section~\ref{section:left deviation inequalities}}
\begin{proof}[Proof of Theorem~\ref{thm:sub-Gamma}] As previously, we only have to prove~\eqref{theo4.2.a}.
Recall that
\begin{equation}\label{eqn:proof thm sub-Gamma eq1}
\langle\Xi^o\rangle_n:=\sum_{k=1}^n\bE_{k-1}\left[(-\xi_k)^{2}\right]\leq n\sigma^2.
\end{equation}
Furthermore, as in~\eqref{eqn:proof decomposition martingale eq3}, since $\tau_k$ is $\cF_n^k$-measurable, the conditional Jensen inequality implies that for any $\lambda\geq 0$,
\begin{equation}\label{eqn:proof thm sub-Gamma eq2}
\bE_{k-1}\left[\exp(\lambda\xi_k^o)\right]\leq \bE_{k-1}\bE _n^k\left[\exp\left(-\lambda X_{k,\,t_{\tau_k}}\right)\right]\leq\frac{\sigma^2\lambda^2}{2(1-c\lambda)},
\end{equation}
where we use the assumption~\eqref{eqn:hyp thm sub-Gamma} in the last inequality. An immediate induction on $n$ gives that
\begin{equation}\label{eqn:proof thm sub-Gamma eq4}
\log\bE\left[\exp(\lambda\,\Xi_n^o)\right]\leq n\,\frac{\sigma^2\lambda^2}{2(1-c\lambda)}\,.
\end{equation}


Now, it is a classical calculation that
\begin{equation}\label{eqn:proof thm sub-Gamma eq5}
\inf_{\lambda\,\in\,]0,\,1/c[}\left(\frac{\sigma^2 t}{2(1-\lambda c)}+\frac x\lambda\right)=cx+\sqrt{2x\sigma^2},
\end{equation}
where the infimum is given by the optimal value $\lambda_x=\sqrt{2x}/(\sqrt{\sigma^2}+c\sqrt{2x})$. Recalling~\eqref{eqn:comparaison CVAR Leg}, one concludes that for any $u\in\intervalleoo 01$,
\begin{equation}\label{eqn:proof thm sub-Gamma eq6}
\tilde Q_{\Xi_n}(u)\leq c\log(1/u)+\sigma\sqrt{2n\log(1/u)}.
\end{equation}


Finally, combining Lemma~\ref{lem:bound log-laplace R_n}, \eqref{eqn:proof thm sub-Gamma eq6} and the subadditivity property of $\tilde Q$ implies inequality~\eqref{theo4.2.a} of the theorem and completes the proof of Theorem~\ref{thm:sub-Gamma}.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:sub-Gaussian}]
As previously mentioned, we only have to prove~\eqref{theo4.4.a}. By reasoning in the same way as~\eqref{eqn:proof thm sub-Gamma eq2}, the assumption on the $X_{k,\,t}$'s allows us to derive that
\begin{equation}
\log\bE[\exp(\lambda\,\Xi_n^o)]\leq n\frac{\lambda^2}{2}C(\cT),
\end{equation}
for any $\lambda\geq 0$. Therefore, the same conclusion as in the proof of Theorem~\ref{thm:sub-Gamma} yields that
\begin{equation}
\tilde Q_{\Xi_n^o}(u)\leq \sqrt{2nC(\cT)\log(1/u)},
\end{equation}
for any $u\in\intervalleoo 01$. The claim follows by associating this fact with Lemma~\ref{lem:bound log-laplace R_n}.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:upper bound gaussian marginals}]
Let $\varphi$ be a convex function. Then by Jensen's inequality,
\[
\bE_{k-1}\left[\varphi(-\zeta_k)\right]\leq \bE_{k-1}\left[\varphi\left(-X_{k,\,t_{\tau_k}}\right)\right].
\]
Now, since $\tau_k$ is $\cF_n^k$-measurable, conditionally to $\cF_n^k$, $-X_{k,\,t_{\tau_k}}$ is a centered Gaussian random variable with variance equals to $\sigma^2_{t_{\tau_k}}$. Thus, since $\sigma^2_{t_{\tau_k}}\leq \sigma^2$,
\begin{equation}\label{eqn:comparison gaussian prop supEP}
\bE_{k-1}\bE_n^k\left[\varphi\left(-X_{k,\,t_{\tau_k}}\right)\right]\leq \bE[\varphi(\sigma Y)],
\end{equation}
where $Y$ is standard Gaussian random variable. The proof of~\eqref{eqn:comparison gaussian prop supEP} is deferred to Appendix~\ref{section:Appendix A}. Now, by an induction on $n$, we derive that for any convex function $\varphi$,
\begin{equation}
\bE\left[\varphi\left(\Xi_n^o\right)\right]\leq \bE\left[\varphi\left(\sigma\sum_{k=1}^n Y_k\right)\right],
\end{equation}
where $Y_1,\,\ldots,\,Y_n$ is a sequence of iid standard Gaussian random variables, independent of the other random variables. Then, by the variational formula~\eqref{eqn:def generalized quantiles} for $\alpha=1$, we have for any $u\in\intervalleof 01$,
\begin{equation}\label{eqn:proof comparison gaussian prop supEP eq1}
\tilde Q_{\Xi_n^o}(u)\leq \tilde Q_{\sigma\mathop{\sum_{k=1}\limits^n} Y_k}(u).
\end{equation}
Now, since $\tilde Q_X$ depends only on the distribution of $X$, the right-hand side in~\eqref{eqn:proof comparison gaussian prop supEP eq1} is equal to $\sigma\sqrt n\,\tilde Q_Y(u)$, where $Y$ is a standard Gaussian random variable. The claim follows by combining this fact with Lemma~\ref{lem:bound log-laplace R_n}.
\end{proof}



\appendix
\section{Additional proofs}\label{section:Appendix A}

\begin{proof}[Proof of Inequality~\eqref{eqn:CIS2}]
Let $X=Z_G-\bE[Z_G]$. Recall that $Q_X(U)$ has the same distribution as $X$ for any random variable $U$ with the uniform distribution over $\intervalleff 01$. It implies that $\tilde Q_X(1)=\bE[X]$. Now, since $\bE[X]=0$, one has
\[
\int_0^uQ_X(s)ds=-\int_u^1Q_X(s)ds.
\]
Moreover,
\[
\int_u^1 Q_X(y)dy=\frac{1-u}{u}\int_0^uQ_X\left(u+\frac{1-u}{u}s\right)ds.
\]
Hence, combining this two facts and using the comparison inequality~\eqref{eqn:CIS},
\begin{align*}
\tilde Q_X(u) &=\frac{1-u}{u}\int_0^uQ_X(s)ds+\int_0^uQ_X(s)ds\\
&=\frac{1-u}{u}\int_0^u \left(Q_X(s)-Q_X\left(u+\frac{1-u}{u}s\right)\right)ds\\
&\leq \sigma_G\,\frac{1-u}{u}\int_0^u \left(Q_Y(s)-Q_Y\left(u+\frac{1-u}{u}s\right)\right)ds\\
&= \sigma_G\,\tilde Q_Y(u).
\end{align*}
This concludes the proof of~\eqref{eqn:CIS2}.
\end{proof}

\begin{proof}[Proof of Inequality~\eqref{eqn:example lower bound VarZ}]
First, note that
\[
Z=\sup_{S\,\in\,\cS}\sum_{k=1}^n\left(U_k^{-1/\ell}\ind_S(U_k)-\int_S u^{-1/\ell}du\right)=\sum_{k=1}^n\left(U_k^{-1/\ell}\ind_{U_k\,\leq\,\Delta}-\int_S u^{-1/\ell}du\right).
\]

Next,
\begin{equation}\label{eqn:proof lower bound VarZ eq1}
\frac 1n\Var(Z)=\Var\left(U^{-1/\ell}\ind_{U\,\leq\,\Delta}\right)=\frac{\ell}{\ell-2}\,\Delta^{(\ell-2)/\ell}-\frac{\ell}{\ell-1}\,\Delta^{2(\ell-1)/\ell}.
\end{equation}

Moreover, for all $S\in\cS$,
\begin{equation}\label{eqn:proof lower bound VarZ eq2}
\sigma_S^2 :=\Var\left(U^{-1/\ell}\ind_S(U)\right)\leq\int_0^p u^{2/\ell}du=\frac{\ell}{\ell-2}\,p^{\ell-2/\ell}.
\end{equation}
Combining~\eqref{eqn:proof lower bound VarZ eq1} and~\eqref{eqn:proof lower bound VarZ eq2}, and choosing $p$ and $\Delta$ small enough, we derive
\begin{equation}\label{eqn:proof lower bound VarZ eq3}
\frac 1n \Var(Z)-\sigma^2 \geq K\,\frac{\ell}{\ell-2}\Delta^{(\ell-1)/\ell},
\end{equation}
for a constant $K>0$. See now that
\begin{equation}
\frac 1n\,\bE[Z]=\bE\left[U^{-1/\ell}\ind_{U\,\leq\,\Delta}\right]=\left(1+\frac {1}{\ell-1}\right)\,\Delta^{(\ell-2)/(\ell-1)},
\end{equation}
which implies
\begin{equation}\label{eqn:proof lower bound VarZ eq4}
\Delta=\left(\frac{\ell-1}{\ell} \frac{\bE[Z]}{n}\right)^{\frac{\ell}{\ell-1}}.
\end{equation}

Putting~\eqref{eqn:proof lower bound VarZ eq4} into~\eqref{eqn:proof lower bound VarZ eq3} leads to
\begin{equation}
\frac 1n \Var(Z)-\sigma^2 \geq K_1\Big(\frac{\bE[Z]}{n}\Big)^{\frac{\ell}{\ell-1}},
\end{equation}
where $K_1>0$, which ends the proof.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:moment nonnegative rv recentered}]
The lemma follows from the following general result:
\begin{lemm}
Let $p>2$. Let $X$ be a nonnegative, $\bL^p$-integrable, random variable. Then
\[
\bE[|X-\bE[X]|^p]-\bE[|X|^p]\leq -2(\bE[X])^{p-1}\bE[X\ind_{X\,\leq\,\bE[X]/2}].
\]
\end{lemm}

Assume that $\bE[X]=1$. The general case follows by considering $X/\bE[X]$. Let $M=\bE[X\ind_{X\,\leq\,1/2}]$, and define for any $x\geq 0$,
\[
f_p(x)=|x-1|^p-|x|^p.
\]
Let $g_p:=f_p\ind_{[0,\,1/2]}$ and $h_p:=f_p\ind_{[1/2, +\infty[}$. Since $g_p$ is a decreasing and convex function,
\begin{equation}\label{eqn:appendix moment recentered rv eq1}
\begin{aligned}
\bE[g_p(X)]&\leq\bE\left[g_p\left(X\ind_{X\,\leq\,1/2}\right)\right]\\
&\leq (1-2M) g_p(0)+2Mg_p(1)=1-2M\,. 
\end{aligned}
\end{equation}d
Next, since $h_p$ is concave,
\begin{equation}\label{eqn:appendix moment recentered rv eq2}
\bE\left[h_p(X)\right]\leq h_p(1)=-1.
\end{equation}
Now, since $f_p=g_p+h_p$, the claim follows by combining~\eqref{eqn:appendix moment recentered rv eq1} and~\eqref{eqn:appendix moment recentered rv eq2}.
\end{proof}

\begin{proof}[Proof of Inequality~\eqref{eqn:comparison gaussian prop supEP}]
The claim is an application of the following general comparison result:
\begin{lemm}
Let $X$ be a centered random variable. Let $0\leq a \leq b$. Then, for any convex function $\varphi$
\[
\bE\left[\varphi(aX)\right]\leq \bE\left[\varphi(bX)\right].
\]
\end{lemm}

Let $\varphi$ be a $\cC^2$ convex function. Using the following version of Taylor's formula
\[
\varphi(x)=\varphi(0)+x\varphi'(0)+|x|^2\int_0^1 (1-s)\varphi''(sx)ds,\quad x\in\bR,
\]
we get
\begin{align*}
\bE\left[\varphi(aX)\right] &= \varphi(0)+a^2\,\bE\left[|X|^2\int_0^1\varphi''(saX)ds\right]\\
&=\varphi(0)+ab\,\bE\left[|X|^2\int_0^{a/b}\left(1-\frac ba t\right)\varphi''(tbX)dt\right].
\end{align*}
Now, since $\varphi''\geq 0$ and $0\leq a\leq b$,
\[
ab\,\bE\left[|X|^2\int_0^{a/b}\left(1-\frac ba t\right)\varphi''(tbX)dt\right]\leq b^2\,\bE\left[|X|^2\int_0^{1}\left(1- t\right)\varphi''(tbX)dt\right].
\]
Therefrom,
\[
\bE[\varphi(aX)]\leq\bE[\varphi(bX)].
\]
The general case follows from the monotone convergence theorem since any convex function can be approximated by an increasing sequence of $\cC^2$ convex Lipschitz functions.
\end{proof}
\bibliography{AHL_Marchina}
\end{document}
