Antoine Marchina
email: antoine.marchina@u-pem.fr

Left deviation inequalities for suprema of empirical processes

Left deviation inequalities for suprema of empirical processes

Antoine Marchina

Introduction and notations

In the recent paper [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF], we prove new upper bounds on the deviation above the mean for suprema of empirical processes indexed by classes of unbounded functions. More specifically, let X 1 , . . . , X n be a finite sequence of independent random variables and identically distributed according to a law P , valued in some measurable space (X , F) and let F be a countable class of measurable functions from X to R. We assume that for all f ∈ F , P (f ) = 0 and that F has a square integrable envelope function Φ, that is |f | ≤ Φ for any f ∈ F , and Φ ∈ L 2 .

(1.1)

We set

Z := sup f ∈F n k=1 f (X k ). (1.2)
If Φ(X 1 ) admits a finite weak moment of order > 2 (denoted by Λ + (Φ(X 1 ))), we establish the following Fuk-Nagaev type upper bound on the Conditionnal Value at Risk (CVaR for short, see Definition 1.1 below) of Z -E[Z]:

QZ-E[Z] (u) ≤ 2 log(1/u) σ √ n + V n + 3 n 1/ µ Λ + (Φ(X 1 ))u -1/ , (1.3)
for any u ∈ ]0 , 1[. Here σ 2 := sup f ∈F P (f 2 ), µ := 2+max(4/3, /3) and V n is an explicit corrective term. We recall that an upper bound on the CVaR leads to a deviation inequality (see Proposition 1.4 further). We stress out that there are few results in the literature concerning concentration inequalities for suprema of unbounded empirical processes whose main ones can be found in Boucheron, Bousquet, Lugosi and Massart [START_REF] Boucheron | Moment inequalities for functions of independent random variables[END_REF], Adamczak [START_REF] Adamczak | A tail inequality for suprema of unbounded empirical processes with applications to Markov chains[END_REF] and Lederer and van de Geer [START_REF] Van De Geer | The Bernstein-Orlicz norm and deviation inequalities[END_REF][START_REF] Lederer | New concentration inequalities for suprema of empirical processes[END_REF]. Their results provide a less accurate estimate compared to (1.3). In these papers, the deviation is around (1 + η)E [Z] with η > 0 and/or the constants are nonexplicit or nonoptimal.

The purpose of this paper is to complete the analysis started in [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF], by providing upper bounds for the left-hand side deviations, also in unbounded settings. We consider four different cases:

• sup f ∈F (-f ) + (X 1 ) admits a weak moment of order > 2.

• For all f ∈ F , f (X 1 ) admits a sub-Gamma tail on the left • For all f ∈ F , f (X 1 ) admits a sub-Gaussian tail on the left.

• Suprema of randomized empirical processes.

It is worth noticing that the left-hand side deviations around the mean for Z heavily depend on the behavior of the left tails (under the distribution P ) of the functions in the class F . The behavior of right tails only takes part in a corrective term in the subgaussian coefficient in our inequalities. The main results, under the assumptions mentionned above, are stated respectively in Sections 2, 3, 4 and 5. All the proofs are postponed to Section 6.

In the rest of this section, we give notations and definitions which we will use all along the paper. Let us start with the classical notations x + := max(0, x) and x α + := (x + ) α for all real x and α. Next, we define the quantile function and the Conditional Value-at-Risk. Definition 1.1. Let X be a real-valued integrable random variable. Let the function Q X be the càdlàg inverse of x → P(X > x). The Conditional Value-at-Risk is defined by

QX (u) := u -1 u 0 Q X (s)ds for any u ∈ ]0 , 1].
(1.4)

Let us now recall the definition of the Legendre transform of a convex function.

Definition 1.2. Let

φ : [0 , ∞[ → [0 , ∞]
be a convex, nondecreasing and càdlàg function such that φ(0) = 0. The Legendre transform φ * of the function φ is defined by φ * (λ) := sup{λt -φ(t) : t > 0} for any λ ≥ 0.

(1.5)

The inverse function of φ * admits the following variational expression (see, for instance, Rio [START_REF] Rio | Asymptotic theory of weakly dependent random processes[END_REF]Lemma A.2]).

φ * -1 (x) = inf{t -1 (φ(t) + x) : t > 0} for any x ≥ 0.
(1.6)

A particular function φ satisfying conditions of Definition 1.2 is the log-Laplace transform of a random variable:

Notation 1.3.
Let X be a real-valued integrable random variable with a finite Laplace transform on right neighborhood of 0. The log-Laplace transform of X, denoted by X , is defined by

X (t) := log E[exp(tX)] for any t ≥ 0. (1.7)
The function Q X and the CVaR satisfy the following elementary properties, which are given and proved in Pinelis [START_REF] Pinelis | An optimal three-way stable and monotonic spectrum of bounds on quantiles: a spectrum of coherent measures of financial risk and economic inequality[END_REF]Theorem 3.4]. Proposition 1.4. Let X and Y be real-valued and integrable random variables. Then, for any u ∈ ]0 , 1],

(i) P(X > Q X (u)) ≤ u, (ii) Q X (u) ≤ QX (u), (iii) QX+Y (u) ≤ QX (u) + QY (u).
(iv) Assume that X has a finite Laplace transform on a right neighborhood of 0. Then QX (u) ≤ * -1 X (log(1/u)).

Remark 1.5. Since we use different notations from those of Pinelis, let us mention that his notations

Q 0 (X; u), Q 1 (X; u) and Q ∞ (X; u) correspond respectively to Q X (u), QX (u) and * -1 X (log(1/u)).
Let us now define the following class of distribution functions.

Notation 1.6. Let q ∈ [0 , 1]. Let ψ be a nonnegative random variable. We denote by F ψ the distribution function of ψ and by F -1 ψ the càdlàg inverse of F ψ . Set b ψ,q := F -1 ψ (1 -q). We denote by F ψ,q the distribution function defined by F ψ,q (x) := (1 -q)1 0≤x<b ψ,q + F ψ (x)1 x≥b ψ,q .

(1.8)

Set for any k = 1, . . . , n,

E k := E sup f ∈F P k (f ) , (1.9)
and let ζ k denote a random variable with distribution function F 2φ(X 1 ),q k , where q k is the real in

[0 , 1] such that E[ζ k ] = E k .
Let us now define the quantity which appears in all of our inequalities in the corrective term in the subgaussian coefficient:

V n := n k=1 E[ζ 2 k ]. (1.10)
The justification of the term "corrective" is given by this remark:

Fuk-Nagaev type inequalities

In this Section we provide Fuk-Nagaev type inequalities which allow us to derive strong and weak moment inequalities. These left deviation inequalities are the exact counterparts of the right deviation inequalities stated in [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF].

We recall that Φ := sup f ∈F |f | and we define also Φ -:= sup f ∈F (-f ) + .

General inequalities

Theorem 2.1. Let x > 0. For any s > 0, we have

P(Z ≤ E[Z] -x) ≤ 1 + x 2 4snσ 2 -s/2 + exp - x 2 8V n + nP Φ -(X 1 ) ≥ x 2s ,
where V n is defined by (1.10).

Consequently, if Φ -(X 1 ) admits an -th moment, we derive then by integrating the above inequality the following moment inequality:

Corollary 2.2. Let ≥ 2. Assume that Φ -(X 1 ) is L -integrable. Then (E[Z] -Z) + ≤ 2β 1/ √ + 1 σ √ n + δ V n + 2 n 1/ ( + 1) Φ -(X 1 )
,

where β := ( √ π/2) Γ( /2)/Γ(( + 1)/2)

Under weak moments assumptions

We first introduce some more definitions and notations. For any real-valued integrable random variable X and any r ≥ 1, let

Λ + r (X) := sup t>0 t (P(X > t)) 1/r . (2.1)
We say that X have a weak moment of order

r if Λ + r (|X|) is finite. Define also Λ+ r (X) := sup u∈]0,1] u (1/r)-1 u 0 Q X (s)ds. (2.2)
From the definition of Q X , we have

Λ + r (X) = sup u∈]0,1] u 1/r Q X (u). (2.3)
Hence, we get that

Λ + r (X) ≤ Λ+ r (X) ≤ r r-1 Λ + r (X). (2.4)
Furthermore, from Proposition 1.4 (iii), Λ+ r (.) is subadditive. The main result of this section is the following Fuk-Nagaev type inequality for E[Z]-Z.

Theorem 2.4. Let > 2. Assume that Φ -(X 1 ) have a weak moment of order . Then for any u ∈ ]0 , 1[,

Q E[Z]-Z (u) ≤ QE[Z]-Z (u) (a) ≤ 2 log(1/u) σ √ n + V n + n 1/ µ Λ + (Φ -(X 1 ))u -1/ , (b)
where µ := 2 + max(4/3, /3) and V n is defined by (1.10). Consequently,

P Z < E[Z] -2 log(1/u) σ √ n + V n -n 1/ µ Λ + (Φ -(X 1 ))u -1/ ≤ u. (c) Corollary 2.5. Let > 2. Assume that Φ -(X 1
) have a weak moment of order . Then

Λ + (E[Z] -Z) ≤ Λ+ (E[Z] -Z) (a) ≤ ( /e) σ √ n + V n + n 1/ µ Λ + (Φ -(X 1 )), (b)
where µ := 2 + max(4/3, /3).

Application to power-type tail

Let Y 1 , . . . , Y n be a finite sequence of nonnegative, independent and identically distributed random variables and let X 1 , . . . , X n be a finite sequence of independent and identically distributed random variables with values in some measurable space (X , F) such that the two sequences are independent. Let P denote the common distribution of the X k . Let G be a countable class of measurable functions from X into [-1, 1] such that for all g ∈ G ,

P (g) = 0 and P (g 2 ) < δ 2 for some δ ∈]0, 1[. (2.5)
Let G be a measurable envelope function of G , that is

|g| ≤ G for any g ∈ G , and G(x) ≤ 1 for all x ∈ X . (2.6)
Let G -be a measurable function such that

(-g) + ≤ G -for any g ∈ G , and G -(x) ≤ 1 for all x ∈ X . ( 2.7)
We suppose furthermore that for some constant p > 2,

P(Y 1 > t) ≤ t -p for any t > 0. (2.8)
Define now

Z := sup g∈G n k=1 Y k g(X k ).
(2.9) Deviations of Z above the mean are studied in [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF] and more precise bounds for V n in terms of the uniform entropy integral (using a result of van der Vaart and Wellner [START_REF] Van Der Vaart | A local maximal inequality under uniform entropy[END_REF]) are given. Here, we prodive upper bounds for the left-hand side deviations. Since the proofs are rather equivalent, we refer the reader to [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF] for the details.

Let us first recall the definitions of covering numbers and uniform entropy integral. G ,Q) is the minimal number of balls of radius in L 2 (Q) needed to cover the set G . The uniform entropy integral is defined by

Definition 2.6 (Covering number and uniform entropy integral). The covering number N ( ,

J(δ, G ) := sup Q δ 0 1 + log N G Q,2 , G , Q d .
Here, the supremum is taken over all finitely discrete probability distributions Q on (X , F) and f Q,2 denotes the norm of a function f in L 2 (Q).

In the following theorem, K denotes an universal constant which may change from line to line. Theorem 2.7. Let p > 2. Let Z be defined by (2.9). Under conditions (2.5) -(2.8), the following results hold:

(i) If Y 1 is L p -integrable, then (E[Z] -Z) + p ≤ 2 β p p 1/p √ p + 1 σ √ n+K p p -2 n q/4 J(δ, G )+ √ p n 1/p J(δ, G ) δ 1/q + 2 n 1/p (p + 1) Y 1 p G -(X 1 ) p , (a)
where

β p = ( √ π/2) Γ(p/2) /Γ((p + 1)/2) 1/p . (ii) Moreover, Λ+ p (E[Z] -Z) ≤ (p/e) σ √ n + K p p -2 n q/4 J(δ, G ) + √ p n 1/p J(δ, G ) δ 1/q + n 1/p µ p , (b)
where q = p/(p -1) and µ p = 2 + max(4/3, p/3).

Under sub-Gamma tails on the left assumptions

Here we assume that f (X 1 ) admits a sub-Gamma tail on the left for all f ∈ F .

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 [START_REF] Klein | Une inégalité de concentration à gauche pour les processus empiriques[END_REF]. More precisely, Klein provides an upper bound on the Laplace transform of E[Z] -Z which implies the following deviation inequality:

Theorem 3.1 (Theorem 1.1 (3) in [8]). Assume that for all f ∈ F , f ≤ 1, and for all integer p ≥ 2, |P (f p )| ≤ σ 2 p!/2. Then P Z < E[Z] - √ 2xv n -x - x √ 2v n √ x + v n /2 ≤ exp(-x),
where

v n = nσ 2 + 2E[Z].
The objective here is to relax the boundedness assumption on the right. Our main result is the following: Theorem 3.2. Assume that there exists a positive constant c such that for any f ∈ F and any t ∈ ]0 , c[,

log P (e -tf ) ≤ σ 2 t 2 2(1 -ct) . (3.1)
Then for any u ∈ ]0 , 1[,

Q E[Z]-Z (u) ≤ QE[Z]-Z (u) (a) ≤ 2 log(1/u) σ √ n + V n + c log(1/u). (b)
Consequently, for any x > 0,

P Z < E[Z] - √ 2x σ √ n + V n -cx ≤ exp(-x). (c) Remark 3.3.
If the elements of F satisfy Bernstein's moment conditions on the left, then the hypothesis (3.1) above is satisfied. Precisely, assume that there exists a positive constant c such that, for any integer p ≥ 3, and all f ∈ F ,

P ((-f ) p + ) ≤ p!c p-2 2 σ 2 . (3.2)
Then, since P (f ) = 0 for all f ∈ F , log P (e -tf ) ≤ σ 2 t 2 2(1-ct) . We refer the reader to Bercu, Delyon and Rio [START_REF] Bercu | Concentration Inequalities for Sums and Martingales[END_REF] (see the proof of their Theorem 2.1) for a proof.

Under sub-Gaussian tails on the left assumptions

Here we assume that f (X 1 ) admits a sub-Gaussian tail on the left for all f ∈ F . We show in the following theorem that Z -E[Z] is sub-Gaussian on the left tail. Then for any u ∈ ]0 , 1[,

Q E[Z]-Z (u) ≤ QE[Z]-Z (u) (a) ≤ 2 log(1/u) nC(F ) + V n . (b)
Consequently, for any x > 0,

P(Z < E[Z] -x) ≤ exp   - x 2 2 nC(F ) + √ V n 2    . (c)

Application to classes of nonnegative functions

Let X 1 , . . . , X n be a finite sequence of independent random variables and identically distributed according to a law P . Let F be a countable class of functions from X to [0, +∞[ and define

F 0 := {f -P (f ) : f ∈ F }. (4.2)
Define now

Z := sup g∈F 0 n k=1 g(X k ). (4.3)
Remark 4.2. Equivalently, one can consider the case of classes of bounded from below functions which are centered under P .

Let us define

σ 2 := sup f ∈F Var P (f ) := sup f ∈F (P (f 2 ) -P (f ) 2 ). ( 4
C(F 0 ) ≤ σ 2 + 1 6 sup f ∈F P (f ) 2 . (a)
Consequently, for any x < 0,

P(Z < E[Z] -x) ≤ exp   - x 2 2 n(σ 2 + 1 6 sup f ∈F P (f ) 2 ) + √ V n 2   , (b)
where V n is defined by (1.10) with Φ := sup g∈F 0 |g| = sup f ∈F |f -P (f )|.

Suprema of randomized empirical processes

Let X 1 , . . . , X n be a finite sequence of independent random variables and identically distributed according to a law P , valued in some measurable space (X , F) with common distribution P . Let Y 1 , . . . , Y n be a finite sequence of independent, identically distributed and centered real-valued random variables with finite Laplace transform on a neighborhood of 0. And we assume that the two sequences are independent. Let G be a countable class of measurable functions from X to [0 , 1] and define

Z := sup g∈G n k=1 Y k g(X k ). ( 5
v (x) := x √ 2/ log(1 + v -1 (e x -1)). (5.2)
Note that γ v (x) = √ 2vx(1 + O(x)) as x goes to 0 and γ v (x) ∼ √ 2x as x goes to infinity. We have for any x > 0,

P Z -E[Z] > nγ v x n ≤ exp(-x). (5.3)
This result is based on a slighlty different use of martingale methods and comparison inequalities which in fact allow to examine general separately convex functions of independent random variables. However, we provide in [START_REF] Marchina | Concentration inequalities for separately convex functions[END_REF] only right deviation inequalities and it seems not that easy to generalize to obtain left deviation inequalities. Therefore, the objective here is to fill this gap. In what follows, we establish a result in a more general setting that Gaussian case. When we specify to the Gaussian case, we obtain a result similar to (5.3) with a better variance term v but with an additionnal corrective term. We denote by G an envelope function of G , that is g(x) ≤ G(x) ≤ 1 for any x ∈ X and any g ∈ G . Then, for any x ≥ 0,

P Z < E[Z] -n * -1 σ 2 ,R x n -2xV n ≤ exp(-x), (a)
where V n is defined by (1.10) with Φ(x, y) = |y|G(x). Consequently, for any x ≥ 0,

P Z < E[Z] -n γ σ 2 ,R x n -2xV n ≤ exp(-x), (b)
where γ v,R , v ≥ 0, is the function defined for any x ≥ 0 by

γ v,R (x) = 2x R -1 (1 + v -1 (e x -1)) . ( 5
P Z < E[Z] -n γ σ 2 x n -2xV n ≤ exp(-x).
(5.9)

Note that the variance term σ 2 in the inequality above is better than the variance term v = E[sup g∈G g 2 (X 1 )] in Inequality (5.3). However, methods developed in [START_REF] Marchina | Concentration inequalities for separately convex functions[END_REF] allow us to consider the non-identically distributed case, that is

Z = sup g∈G n k=1 a k Y k g(X k
) where a 1 , . . . , a n are a sequence of positive reals.

Example 5.5 (Sub-Gamma case).

Here we assume that

R(t) := exp t 2 2(1 -t) ,
which satisfies the hypotheses of Theorem 5.1. Then

P Z < E[Z] -n γ σ 2 ,L x n -2xV n ≤ exp(-x), (5.10)
where

γ σ 2 ,R := 2x -z x + z 2 x + 2z x
with z x := log(1 + σ -2 (e x -1)).

(5.11)

Here, note that γ σ 2 ,R = ( √ 2σ 2 x + x)(1 + O(x)
) as x goes to 0, and γ σ 2 ,R ∼ 2x as x tends to infinity.

Example 5.6 (Symmetric exponential case).

Here we assume that R(t) := 1/(1 -t 2 ), which is equivalent to suppose that Y 1 law = εW , where ε is a Rademacher random variable, W is an exponential random variable with parameter 1 and the two random variables are independent. We can easily verify that R satisfies the hypotheses of Theorem 5.1. Then

P Z < E[Z] -n γ σ 2 ,R x n -2xV n ≤ exp(-x), (5.12)
where

γ σ 2 ,R := 2x 1 + σ -2 (e x -1)
σ -2 (e x -1) .

(5.13)

Here, note that γ σ 2 ,R = 2 √ σ 2 x + O(x) as x goes to 0 and γ σ 2 ,R ∼ 2x as x tends to infinity.

Proofs

The starting point of the proofs is a martingale decomposition of E[Z] -Z which we briefly recall (we refer the reader to [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF] for more details). First by virtue of the monotone convergence theorem, we can suppose that F is a finite class of functions. Set F 0 := {∅, Ω} and for all k = 1, . . . , n,

F k := σ(X 1 , . . . , X k ) and F k n := σ(X 1 , . . . , X k-1 , X k+1 , . . . , X n ). Let E k (re- spectively E k n ) denote the conditional expectation operator associated with F k (resp. F k n ). Set also Z (k) := sup{nP n (f ) -f (X k ) : f ∈ F } and Z k := E k [Z].
Let us number the functions of the class F and consider the random variables

τ := inf{i > 0 : nP n (f i ) = Z} and τ k := inf{i > 0 : nP n (f i )-f i (X k ) = Z (k) }.
We notice that

f τ k (X k ) ≤ Z -Z (k) ≤ f τ (X k ). ( 6.1)
Set now

ξ k := E k [f τ k (X k )], r k := Z -Z (k) -ξ k and ε k := E k [f τ (X k )] -ξ k .
Projecting then (6.1) on F k leads to

ξ k ≤ ξ k + r k ≤ ξ k + ε k . (6.2) Since E k n [f τ k (X k )] = P (f τ k ), the centering assumption on the elements of F ensures that Z k -Z k-1 = ξ k + r k -E k-1 [r k ]. (6.3)
Thus we get the following decomposition:

E[Z] -Z = Ξ o n + R o n , (6.4)
where

Ξ o n := n k=1 ξ o k , ξ o k := -ξ k and R o n := n k=1 (E k-1 [r k ] -r k ).
Now the martingale R o n is sub-Gaussian, as shown by the lemma below. Lemma 6.1. For any t ≥ 0, we have

R o n (t) := log E[exp(tR o n )] ≤ t 2 V n 2 , ( a
)
where V n is defined by (1.10). Consequently, for any u ∈ ]0 , 1[,

QR o n (u) ≤ * -1 R o n (log(1/u)) ≤ 2 V n log(1/u). (b)
Proof of Lemma 6.1. We start by showing that

E k-1 [r k ] -r k ≤ E n-k+1 and E k-1 [(E k-1 [r k ] -r k ) 2 ] ≤ E[ζ 2 n-k+1 ]. (6.5)
These bounds are stated and proved in Marchina [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF]. We briefly recall below main arguments. First, note that r k ≥ 0 by (6.2). Next, a property of exchangeability of variables (see Lemma 3.10 in [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF])

shows that E k-1 [r k ] ≤ E n-k+1 .
Then we get the first bound of (6.5). The second bound follows from a comparison inequality of generalized moments due to Bentkus [3, Lemma 1] (see also Lemma 2.1 in Marchina [START_REF] Marchina | Concentration inequalities for separately convex functions[END_REF]). Indeed, since (6.2) implies 0

≤ r k ≤ 2Φ(X k ), we have E k-1 [ϕ(r k )] ≤ E[ϕ(ζ n-k+1
)] for any real-valued, convex and differentiable function ϕ such that lim x→-∞ ϕ(x) = 0. Then, since x → x 2 + is such a function and r k+ = r k , we get

E k-1 [(E k-1 [r k ] -r k ) 2 ] ≤ E k-1 [r 2 k+ ] ≤ E[ζ 2 n-k+1 ]. (6.6)
We recall that ζ k denotes a random variable with distribution function

F 2Φ(X 1 ),q k such that E[ζ k ] = E k . Thus we have max(E[ζ 2 k ], E 2 k ) = E[ζ 2 k ].
Applying now the bound for martingales with differences bounded from above proved by Bentkus [START_REF] Bentkus | An inequality for tail probabilities of martingales with differences bounded from one side[END_REF] (see his Inequality (2.16)), we get for any t ≥ 0,

E[exp(tR o n )] ≤ exp(t 2 V n /2), (6.7)
which then gives (a). Now, it is a classical calculation that inf

t>0 1 t t 2 V n 2 + x = 2 V n x, (6.8)
where the infimum is given by the optimal value t = 2 x/V n . Finally, Proposition 1.4 (iv) ends the proof of (b). Now, in view of (6.4), it remains us to bound up the CVaR (or the log-Laplace) of Ξ o n according to the assumptions made in different sections.

Proofs of Section 2

Proofs in this section are almost identical to that of the article [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF]. Thus we only give main arguments.

Proof of Theorem 2.1. The proof is similar to the proof of Theorem 3.2 in [START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF]. First, note that one derive from Lemma 6.1 (a) and the usual Cramér-Chernoff calculation that for any x ≥ 0,

P(R o n ≥ x) ≤ exp - x 2 2V n . ( 6.9)
We bound up the log-Laplace of Ξ o n thanks to a Fuk-Nagaev type inequality for martingales obtained by Courbot [START_REF] Courbot | Rates of convergence in the functional CLT for martingales[END_REF]. Hence, we first need to control the quadratic variation. Since τ k is F k n -measurable, the centering assumption on the elements of F yields that

E k-1 [ξ o2 k ] = E k-1 [ξ 2 k ] ≤ E k-1 E k n [f 2 τ k (X k )] = E k-1 P (f 2 τ k ) ≤ σ 2 , ( 6.10)
where the first inequality follows from the conditionnal Jensen inequality. Then, since ξ o k ≤ Φ(X k ) and (1 + x) log(1 + x) -x ≥ x log(1 + x)/2, Theorem 1 in Courbot [START_REF] Courbot | Rates of convergence in the functional CLT for martingales[END_REF] leads to the following inequality:

P(Ξ o n+ ≥ x) ≤ 1 + x 2 snσ 2 -s/2 + nP Φ(X 1 ) > x s , ( 6.11)
for any x > 0 and any s > 0. Furthermore,

E[Z] -Z = Ξ o n + R o n ≤ Ξ o n+ + R o n
, which yields that for any x ≥ 0,

P(Z < E[Z] -x) ≤ inf t∈[0,1] {P(Ξ o n+ ≥ tx) + P(R o n ≥ (1 -t)x)}. (6.12)
Since the optimization in t in the right-hand side is difficult to calculate, we take t = 1/2 in the sequel. Finally, combining (6.12), (6.11) and (6.9) ends the proof of Theorem 2.1.

Proof of Corollary 2.2. The proof relies on the following equality: for any ≥ 1,

E[(E[Z] -Z) + ] = ∞ 0 P(E[Z] -Z ≥ x)x -1 dx. ( 6
C w (Ξ o n ) ≤ n 1/ Λ + (Φ(X 1 )), (6.14)
where

C w (Ξ o n ) := sup t>0 t n k=1 P(ξ o k+ > t | F k-1 ) 1/ ∞ .
Now, recalling (6.10), the Fuk-Nagaev type inequality for martingale obtained by Rio [START_REF] Rio | New deviation inequalities for martingales with bounded increments[END_REF] (see his Theorem 4.1) yields

QΞ o n (u) ≤ σ 2 log(1/u) + n 1/ µ Λ + (Φ(X 1 ))u -1/ . ( 6

Proof of Section 3

Proof of Theorem 3.2. As in Theorem 2.4, we only have to prove (b). Moreover we already saw in the proof of Theorem 2.1 that

Ξ o n := n k=1 E k-1 [ξ o2 k ] ≤ nσ 2 . (6.16)
Furthermore, as in (6.10), since τ k is F k n -measurable, the conditionnal Jensen inequality implies that for any t ≥ 0,

E k-1 [exp(tξ o k )] ≤ E k-1 E k n [exp(-tf τ k (X k ))] = E k-1 [P (exp(-tf τ k ))]. ( 6
)] ≤ n σ 2 t 2 2(1 -ct) . (6.18) Now, it is a classical calculation that inf t∈]0,1/c[ σ 2 t 2(1 -tc) + x t = cx + √ 2xσ 2 , ( 6.19)
where the infimum is given by the optimal value t = √ 2x/( √ σ 2 + c √ 2x). Recalling (1.6), one conclude that for any u ∈ ]0 , 1[, QΞn (u) ≤ c log(1/u) + σ 2n log(1/u).

(6.20)

Finally, combining Lemma 6.1, (6.20) and the point (iii) of Proposition 1.4 implies inequality (b) of the theorem and completes the proof.

Proofs of Section 4

Proof of Theorem 4.1. As previously mentioned, we only have to prove (b). By reasoning in the same way as (6.17), the assumptions on the elements of . Hence we only have to prove the upper bound on C(F 0 ). Let g = f -P (f ) ∈ F 0 . Note that -g = P (f ) -f ≤ P (f ) and Var P (g) = Var P (f ) ≤ σ 2 , where σ 2 is defined by (4.4). Then Lemma 2.36 in Bercu, Delyon and Rio [START_REF] Bercu | Concentration Inequalities for Sums and Martingales[END_REF] implies that

F allow us to derive that log E[exp(tΞ o n )] ≤ n t 2 2 C(F ), ( 6
C(F 0 ) ≤ 1 2 sup f ∈F P (f ) 2 ϕ σ 2 P (f ) 2 , (6.23)
where ϕ is the function defined by

ϕ(x) =        1 -x 2 | log(x)| if x < 1 2x if x ≥ 1.
(6.24)

The following lemma provides an upper bound for the function ϕ. We refer the reader to Lemma 2.37 and the proof of Theorem 2.33 in [START_REF] Bercu | Concentration Inequalities for Sums and Martingales[END_REF] for a proof.

E k-1 [exp(t ξ o k )] = E k-1 [exp(-(tη k )Y k )] ≤ E k-1 [R(tη k )] = E k-1 [ R(t 2 η 2 k )]. ( 6

.26)

Observe now that 0 ≤ η 2 k ≤ 1 and E k-1 [η 2 k ] ≤ σ 2 by a similar reasoning to (6.10) by means of the conditionnal Jensen's inequality. Therefore, applying (conditionally to F k-1 ) a classical convex comparison due to Hoeffding [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] (see his inequalities where θ σ 2 is a Bernoulli random variable with parameter σ 2 , independent of all other random variables. Now, since we have assumed that the function R is convex, (6.26) becomes Then, putting t x := R -1 (1 + σ -2 (e x -1)) in (6.30) concludes the proof. Note that t x is optimal in the standard Gaussian case, that is R(t) = exp(t 2 /2) and σ 2 = 1.

E k-1 [exp(t ξ o k )] ≤ E k-1 [ R(t 2 η 2 k )] ≤ E[ R(t 2 θ σ 2 )] = E[R(t θ σ 2 )] = 1 + σ 2 (

2

 2 log P (e -tf ) < ∞. (4.1)

. 4 ) 4 . 3 .

 443 Proposition One has

. 13 )

 13 After calulation of this integral, we put s = +1 and we use the sub-additivity of x → x to conclude the proof. Proof of Theorem 2.4. The proof is similar to the proof of Theorem 3.3 in [10]. Inequality (a) is the point (ii) of Propostion 1.4 and Inequality (c) follows immediately from (b) by the point (i) of the same Proposition 1.4. Let us prove (b). Since ξ o k ≤ Φ(X k ), we have

. 15 )

 15 Combining Lemma 6.1, (6.14) and the point (iii) of Proposition 1.4 implies Inequality (b) of the theorem and thus concludes the proof.Proof of Corollary 2.5. Inequality (a) follows from (2.4). To prove (b) we proceed exactly as in Rio[START_REF] Rio | About the constants in the Fuk-Nagaev inequalities[END_REF] Theorem 5.1] (see also the proof of (b) of Corollary 3.7 in[START_REF] Marchina | Concentration inequalities for suprema of unbounded empirical processes[END_REF]).

  .21) for any t ≥ 0. Therefore, the same conclusion as in the proof of Theorem 3.2 yields that QΞ o n (u) ≤ 2nC(F ) log(1/u), (6.22) for any u ∈ ]0 , 1[, which associated to Lemma 6.1 and Proposition 1.4 give (b) and end the proof. Proof of Proposition 4.3. Both inequality (c) of Theorem 4.1 and the upper bound on C(F 0 ) (a) imply (b)

Lemma 6 . 2 . 3 ( 1 - 5 Proof of Theorem 5 . 1 .

 6231551 For any x ≥ 0, ϕ(x) ≤ 2x + 1 x) + .Therefore combining this bound with (6.23) one hasC(F 0 ) ≤ σ 2 (f ) 2 -σ 2 ) + } ≤ σ 2 Aspreviously, by an induction on n, to bound up log E[exp(t Ξ o n )] we only have to bound up the conditionnal Laplace of the increments ξ o k . Let us denote by η k the random variable E k[g τ k (X k )]. Then, we write ξ o k = -η k Y k . Now, since η k is F k-1 σ(X k )-measurable,Y k and η k are independent and one has for any t ≥ 0,

  (4.1)-(4.2)) leads toE k-1 [ϕ(η 2 k )] ≤ E[ϕ(θ σ 2 )] for any convex function ϕ : R → R, (6.27)

1 σ 2

 12 4 (iv) and (iii), concludes the proof of Inequality (a) of Theorem. Next, to prove (b), we show that * -1 σ 2 ,R ≤ γ σ 2 ,R . First, using the variational formula (1.5), one has * -,R (x) = inf t>0 {t -1 ( σ 2 ,R + x)}.(6.30)

  R(t) -1). (6.28) Thus, as mentionned at the beginning of the proof, we derive by an induction on n that for anyt ≥ 0 log E[exp(t Ξ o n )] ≤ n log(1 + σ 2 (R(t) -1)) = n σ 2 ,R (t). (6.29)Combining now (6.29), Lemma 6.1 and Proposition 1.