Pierre Alquier
email: alquier@ensae.fr

PAC-BAYESIAN BOUNDS FOR RANDOMIZED EMPIRICAL RISK MINIMIZERS

Keywords: January 9, 2009. 2000 Mathematics Subject Classification. Primary 62G08; Secondary 62H30, 68T05, 68T10 Regression estimation, classification, adaptative inference, statistical learning, randomized estimator, empirical risk minimization, empirical bound

 in the classification setting to more general problems of statistical inference. We show how to control the deviations of the risk of randomized estimators. A particular attention is paid to randomized estimators drawn in a small neighborhood of classical estimators, whose study leads to control the risk of the latter. These results allow to bound the risk of very general estimation procedures, as well as to perform model selection.

Introduction

The aim of this paper is to perform statistical inference with observations in a possibly large dimensional space. Let us first introduce the notations.

1.1. General notations. Let N ∈ N * be the number of observations. Let (Z, B) be a measurable space and P 1 , ..., P N be N probability measures on this space, unknown to the statistician. We assume that (Z 1 , ..., Z N ) is the canonical process on Z N , B ⊗N , P 1 ⊗ ... ⊗ P N . We want to perform statistical inference on a general parameter space Θ, with respect to some loss function

ℓ θ : Z → R, θ ∈ Θ.
Definition 1.2 (Risk functions). We introduce, for any θ ∈ Θ,

r(θ) = P (ℓ θ ) = 1 N N i=1 ℓ θ (Z i ) ,
the empirical risk function, and

R(θ) = P(ℓ θ ) = 1 N N i=1 P i (ℓ θ ) ,
the risk function.

We now describe three classical problems in statistics that fit the general context described above.

Example 1.1 (Classification). We assume that Z = X × Y where X is a set of objects and Y a finite set of possible labels for these objects. Consider a set of classification functions {f θ : X → Y, θ ∈ Θ} which assign to each object a label. Let us put, for any z = (x, y) ∈ Z, ℓ θ (z) = ψ (f θ (x), y) where ψ is some symmetric discrepancy measure. The most usual case is to use the 0-1 loss function ψ(y, y ′ ) = δ y (y ′ ) . If moreover |Y| = 2 we can decide that Y = {-1, +1} and set ψ(y, y ′ ) = 1 R * + (yy ′ ) . However, in many practical situations, algorithmic considerations lead to use a convex upper bound of this loss function, like ψ(y, y ′ ) = (1 -yy ′ ) + = max(1 -yy ′ , 0), the "hinge loss", ψ(y, y ′ ) = exp(-yy ′ ), the exponential loss, ψ(y, y ′ ) = (1 -yy ′ ) 2 , the least square loss.

For example, Cortes and Vapnik [START_REF] Cortes | Support vector networks[END_REF] generalized the SVM technique to non-separable data using the hinge loss, while Schapire, Freund, Bartlett and Lee [START_REF] Schapire | Boosting the margin: A new explanation for the effectiveness of voting methods[END_REF] gave a statistical interpretation of boosting algorithm thanks to the exponential loss. See Zhang [START_REF] Zhang | Statistical behavior and consistency of classification methods based on convex risk minimization[END_REF] for a complete study of the performance of classification methods using these loss functions. Remark that in this case, f θ is allowed to take any real value, and not only -1 or +1, although the labels Y i in the training set are either -1 or +1.

Example 1.2 (Regression estimation). The context is the same except that the label set Y is infinite, in most case it is R or an interval of R. Here, the most usual case is the regression with quadratic loss, with ψ(y, y ′ ) = (y -y ′ ) 2 , however, more general cases can be studied like the l p loss ψ(y, y ′ ) = (y -y ′ ) p for some p ≥ 1.

Example 1.3 (Density estimation). Here, we assume that P 1 = ... = P N = P and consequently that P = P ⊗N , and we want to estimate the density f = dP/dµ of P with respect to a known measure µ. We assume that we are given a set of probability measures {Q θ , θ ∈ Θ} with densities q θ = dQ θ /dµ and we use the loss function ℓ θ (z) =log [q θ (z)]. Indeed in this case, we can write under suitable hypotheses

R(θ) = P (-log • q θ ) = P -log • dQ θ dµ = P log • dP dQ θ + P log • dµ dP = K (P, Q θ ) -P (log •f ) ,
showing that the risk is the Kullback-Leibler divergence between P and Q θ up to a constant (the definition of K is reminded in this paper, see Definition 1.8 page 5).

In each case the objective is to estimate arg min R on the basis of the observations Z 1 , ..., Z N -presumably using in some way or another the value of the empirical risk. We have to notice that when the space Θ is large or complex (for example a vector space with large dimension), arg min R and arg min r can be very different. This does not happen if Θ is simple (for example a vector space with small dimension), but such a case is less interesting as we have to eliminate a lot of dimensions in Θ before proceeding to statistical inference with no guarantees that these directions are not relevant.

1.2. Statistical learning theory and PAC-Bayesian point of view. The learning theory point of view introduced by Vapnik and Cervonenkis ( [START_REF] Cervonenkis | On the uniform convergence of relative frequencies of events to their probabilities[END_REF], see Vapnik [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] for a presentation of the main results in English) gives a setting that proved to be adapted to deal with estimation problems in large dimension. This point of view received an important interest over the past few years, see for example the well-known books of Devroye, Gyrfi and Lugosi [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF], Friedman, Hastie and Tibshirani [START_REF] Friedman | The Elements of Statistical Learning[END_REF] or more recently the paper by Boucheron, Bousquet and Lugosi [START_REF] Boucheron | Theory of classification: some recent advances[END_REF] and the references therein, for a state of the art.

The idea of Vapnik and Cervonenkis is to introduce a structure, namely a family of submodels Θ 1 , Θ 2 , ... The problem of model selection then arises: we must choose the submodel Θ k in which the minimization of the empirical risk r will lead to the smallest possible value for the real risk R. This choice requires to estimate the complexity of submodels Θ k . An example of complexity measure is the so-called Vapnik Cervonenkis dimension or VC-dimension, see [START_REF] Cervonenkis | On the uniform convergence of relative frequencies of events to their probabilities[END_REF][START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF].

The PAC-Bayesian point of view, introduced in the context of classification by McAllester [START_REF] Mcallester | Some pac-bayesian theorems[END_REF][START_REF] Mcallester | Pac-bayesian model averaging[END_REF] is based on the following remark: while classical measures of complexity (like VC-dimension) require theoretical results on the submodels, the introduction of a probability measure π on the model Θ allows to measure empirically the complexity of every submodel. In a more technical point of view, we will see later that π allows a generalization of the so-called union bound (see [START_REF] Mcallester | Pac-bayesian model averaging[END_REF] for example). This point of view might be compared with Rissanen's work on MDL (Minimum Description Length, see [START_REF] Rissanen | Modeling by shortest data description[END_REF]) making a link between statistical inference and information theory, andlog π(θ) can be seen as the length of a code for the parameter θ (at least when Θ is finite).

The PAC-Bayesian point of view was developed in more contexts (classification, least square regression and density estimation) by Catoni [START_REF] Catoni | Statistical Learning Theory and Stochastic Optimization[END_REF], and then improved in the context of classification by Catoni [START_REF] Catoni | A pac-bayesian approach to adaptative classification[END_REF], Audibert [START_REF] Audibert | PAC-Bayesian Statistical Learning Theory[END_REF] and in the context of least square regression by Audibert [START_REF] Audibert | Aggregated estimators and empirical complexity for least square regression[END_REF] and of regression with a general loss in our PhD thesis [START_REF] Alquier | Transductive and Inductive Adaptative Inference for Regression and Density Estimation[END_REF]. The most recent work in the context of classification by Catoni [START_REF] Catoni | PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical Learning)[END_REF] improves the upper-bound given on the risk of the PAC-Bayesian estimators, leading to purely empirical bounds that allow to perform model selection with no assumption on the probability measure P. The aim of this work is to extend these results to the very general context of statistical inference introduced in subsection 1.1, that includes classification, regression with a general loss function and density estimation.

Let us introduce our estimators.

Definition 1.3. Let us assume that we have a family of functions the empirical risk minimizer. In the case where the dimension of Θ is large, we can choose several submodels indexed by a finite or countable family I: (Θ i , i ∈ I). In order to obtain θi = arg min θ∈Θi r(θ)

ψ i θ : Z → R ∪ {+∞} indexed by i in
we can put

ψ i θ (.) =    l θ (.) if θ ∈ Θ i +∞ otherwise.
The problem of the selection of the θi with the smallest possible risk (so-called model selection problem) can be solved with the help of PAC-Bayesian bounds.

Note that PAC-Bayesian bounds given by Catoni [START_REF] Catoni | A pac-bayesian approach to adaptative classification[END_REF][START_REF] Catoni | Statistical Learning Theory and Stochastic Optimization[END_REF][START_REF] Catoni | PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical Learning)[END_REF] usually apply to "randomized estimators". More formally, let us introduce a σ-algebra T on Θ and a probability measure π on the measurable space (Θ, T ). We will need the following definitions.

Definition 1.4. For any measurable set (E, E), we let M 1 + (E) denote the set of all probability measures on the measurable space (E, E). Definition 1.5. In order to generalize the notion of estimator (a measurable function Z N → Θ), we call a randomized estimator any function ρ : Z N → M 1 + (Θ) that is a regular conditional probability measure. For the sake of simplicity, the sample being given, we will write ρ instead of ρ (Z 1 , ..., Z N ). PAC-Bayesian bounds for randomized estimators are usually given for their mean risk θ∈Θ R(θ)dρ(θ), whereas here we will rather focus on R( θ), where θ is drawn from ρ and ρ is highly concentrated around a "classical" (deterministic) estimator θi . 1.3. Truncation of the risk. In this subsection, we introduce a truncated version of the relative risk of two parameters θ and θ ′ . Definition 1.6. We put, for any λ ∈ R * + and (θ,

θ ′ ) ∈ Θ 2 R λ (θ, θ ′ ) = P (ℓ θ -ℓ θ ′ ) ∧ N λ .
Note of course that if P-almost surely, we have

ℓ θ -ℓ θ ′ ≤ N/λ then R λ (θ, θ ′ ) = R(θ) -R(θ ′ ).
In what follows, we will give empirical bounds on R λ (θ, θ ′ ) for some θ and θ ′ chosen by some statistical procedure. One can wonder why we prefer to bound this truncated version of the risk instead of R(θ)-R(θ ′ ). The reason is the following. In this paper, we want to give bounds that hold with no particular assumption on the unknown data distribution P. However, it is clear that we cannot obtain a purely empirical bound on R(θ) -R(θ ′ ) with no assumption on the data distribution, as it is shown by the following example.

Example 1.5. Let us choose c > 0 and λ > 0. We assume that P 1 = ... = P N and that Θ = {θ, θ ′ } with l θ ′ (z) = 0. We put l θ (Z) = cN with probability 1/N and 0 otherwise. Then we have R(θ ′ ) = 0 and

R(θ) = 1 N cN + 1 - 1 N 0 = c
while r(θ ′ ) = 0 and with probability at least (1 -1/N ) N ≃ exp(-1) we also have r(θ) = 0, this means that we cannot upper bound precisely R(θ)-R(θ ′ ) by empirical quantities with no assumption.

So, we introduce the truncation of the risk. However, two remarks shall be made. First, in the case of a bounded loss function ℓ, with a large enough ratio N/λ we have R λ (θ, θ ′ ) = R(θ) -R(θ ′ ).

In the general case, if we want to upper bound R(θ) -R(θ ′ ) we can make additional hypotheses on the data distribution, ensuring that we can dispose of a (known) upper-bound :

∆ λ (θ, θ ′ ) ≥ R(θ) -R(θ ′ ) -R λ (θ, θ ′ )
as it is done in our PhD Thesis [START_REF] Alquier | Transductive and Inductive Adaptative Inference for Regression and Density Estimation[END_REF]. For the sake of completeness, such an upper bound is given in the Appendix, page 28. 1.4. Main tools. In this subsection, we give two lemmas that will be useful in order to build PAC-Bayesian theorems. First, let us recall the following definition. In this whole subsection, we assume that (E, E) is an arbitrary measurable space.

m(h) -K(m, n) ,
where by convention ∞ -∞ = -∞. Moreover, as soon as h is upper-bounded on the support of n, the supremum with respect to m in the right-hand side is reached for the Gibbs distribution, n exp(h) given by:

∀e ∈ E, dn exp(h) dn (e) = exp[h(e)] π(exp •h) .
The proof of this lemma is given at the end of the paper, in a section devoted to proofs (subsection 5.1 page 15). We now state another lemma that will be useful in the sequel. First, we need the following definition. Definition 1.9. We put, for any

α ∈ R * + , Φ α : ]-∞, 1/α[ → R t → - log (1 -αt) α .
Note that Φ α is invertible, that for any u ∈ R,

Φ -1 α (u) = 1 -exp (-αu) α ≤ u,
and that 2(Φα(x)-x)

αx 2 ---→ x→0
1. Also note that for α > 0, Φ α is convex and that Φ α (x) ≥ x. An elementary study of this function also proves that for any C > 0, for any α ∈ ]0, 1/(2C)[ and any p ∈ [0, C] we have:

Φ α (p) ≤ p + αp 2 2 .
We can now give the lemma.

Lemma 1.2. We have, for any λ ∈ R * + , for any a ∈]0, 1], for any (θ, θ ′ ) ∈ Θ 2 ,

P exp λΦ λ N R λ a (θ, θ ′ ) - λ N N i=1 Φ λ N (ℓ θ -ℓ θ ′ ) (Z i ) ∧ aN λ = 1.
The proof is almost trivial, we give it now in order to emphasize the role of the truncation and of the change of variable.

Proof. For any

λ ∈ R * + , for any (θ, θ ′ ) ∈ Θ 2 , P exp λΦ λ N R λ a (θ, θ ′ ) - λ N N i=1 Φ λ N (ℓ θ -ℓ θ ′ ) (Z i ) ∧ aN λ = P exp N i=1 log 1 - λ N (l θ -l θ ′ )(Z i ) ∧ aN λ -log 1 - λ N P i (l θ -l θ ′ )(Z i ) ∧ aN λ = P N i=1 1 -λ N (l θ -l θ ′ )(Z i ) ∧ aN λ 1 -λ N P i (l θ -l θ ′ )(Z i ) ∧ aN λ = N i=1 P i 1 -λ N (l θ -l θ ′ )(Z i ) ∧ aN λ 1 -λ N P i (l θ -l θ ′ )(Z i ) ∧ aN λ = 1.
Note that this lemma will be used as an alternative to Hoeffding's or Bernstein's (see [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF][START_REF] Bernstein | Theory of Probability[END_REF]) inequalities in order to prove PAC inequalities. 1.5. A basic PAC-Bayesian Theorem. Let us integrate Lemma 1.2 with respect to (θ, θ ′ ) with a given probability measure

n = π ⊗ π ′ with (π, π ′ ) ∈ [M 1 + (Θ)] 2 .
Applying Fubini-Tonelli Theorem we obtain:

(1.2) P (θ,θ ′ )∈Θ 2 d(π ⊗ π ′ )(θ, θ ′ ) exp λΦ λ N R λ a (θ, θ ′ ) - λ N N i=1 Φ λ N (ℓ θ -ℓ θ ′ ) (Z i ) ∧ aN λ = 1.
This implies that for any (ρ,

ρ ′ ) ∈ [M 1 + (Θ)] 2 , P (θ,θ ′ )∈Θ 2 d(ρ ⊗ ρ ′ )(θ, θ ′ ) exp λΦ λ N R λ a (θ, θ ′ ) - λ N N i=1 Φ λ N (ℓ θ -ℓ θ ′ ) (Z i ) ∧ aN λ -log d(ρ ⊗ ρ ′ ) d(π ⊗ π ′ ) (θ, θ ′ ) ≤ 1.
(This inequality becomes an equality when π ≪ ρ and π ′ ≪ ρ ′ .)

Theorem 1.3. Let us assume that we have (π, π ′ ) ∈ M 1 + (Θ) 2 , and two randomized estimators ρ and ρ ′ . For any ε > 0, for any (a, λ) ∈]0, 1] × R * + , with P(ρ ⊗ ρ ′ )probability at least 1 -ε over the sample (Z i ) i=1,...,N and the parameters ( θ, θ′ ), we have:

R λ a θ, θ′ ≤ Φ -1 λ N 1 N N i=1 Φ λ N ℓ θ -ℓ θ′ (Z i ) ∧ aN λ + log dρ dπ θ + log dρ ′ dπ ′ θ′ + log 1 ε λ .
In order to provide an interpretation of Theorem 1.3, let us give the following corollary in the bounded case, which is obtained using basic properties of the function Φ given just after Definition 1.9 page 6. In this case, the parameter a is just set to 1.

Corollary 1.4. Let us assume that for any

(θ, z) ∈ Θ × Z, 0 < l θ (z) < C. Let us assume that we have (π, π ′ ) ∈ M 1 + (Θ) 2
, and two randomized estimators ρ and ρ ′ . For any ε > 0, for any λ ∈]0, N/(2C)], with P(ρ ⊗ ρ ′ )-probability at least 1 -ε we have:

R θ -R θ′ ≤ Φ -1 λ N r θ -r θ′ + λ 2N P l θ -l θ′ 2 + log dρ dπ θ + log dρ ′ dπ ′ θ′ + log 1 ε λ .
We can see that the difference of the "true" risk of the randomized estimators θ and θ′ , drawn independently from ρ and ρ ′ , is upper bounded by the difference of the empirical risk, plus a variance term and a complexity term expressed in terms of the log of the density of the randomized estimator with respect to a given prior. So Theorem 1.3 provides an empirical way to compare the theoretical performance of two randomized estimators, leading to applications in model selection. This paper is devoted to improvements of Theorem 1.3 (we will see in the sequel that this theorem does not necessarily lead to optimal estimators) and to the effective construction of estimators using variants of Theorem 1.3. Now, note that the choice of the randomized estimators ρ and ρ ′ is not straightforward. The following theorem, which gives an integrated variant of Theorem 1.3, can be usefull for that purpose.

Theorem 1.5. Let us assume that we have

(π, π ′ ) ∈ M 1 + (Θ) 2 . For any ε > 0, for any (a, λ) ∈]0, 1] × R * + , with P-probability at least 1 -ε, for any (ρ, ρ ′ ) ∈ M 1 + (Θ) 2 , Θ 2 R λ a (θ, θ ′ )d(ρ ⊗ ρ ′ )(θ, θ ′ ) ≤ Φ -1 λ N Θ 2 1 N N i=1 Φ λ N (ℓ θ -ℓ θ ′ ) (Z i ) ∧ aN λ d (ρ ⊗ ρ ′ )(θ, θ ′ ) + K(ρ, π) + K(ρ ′ , π ′ ) + log 1 ε λ .
The proof is given in subsection 5.2 page 15.

1.6. Main results of the paper. In our PhD dissertation [START_REF] Alquier | Transductive and Inductive Adaptative Inference for Regression and Density Estimation[END_REF], a particular case of Theorem 1.5 is given and applied to regression estimation with quadratic loss in a bounded model of finite dimension d. In this particular case, it is shown that the estimators based on the minimization of the right-hand side of Theorem 1.5 do not achieve the optimal rate of convergence: d/N , but only (d log N )/N . A solution is given by Catoni in [START_REF] Catoni | Statistical Learning Theory and Stochastic Optimization[END_REF] and consists in replacing the prior π by the so-called "localized prior" π exp(-βR) for a given β > 0. The main problem is that this choice leads to the presence of non-empirical terms in the right-hand side, K(ρ, π exp(-βR) ).

In Section 2, we give an empirical bound for this term K(ρ, π exp(-βR) ). We also give a heuristic that leads to this technique of localization.

In Section 3, we show how this result, combined with Theorem 1.5, leads to the effective construction of an estimator that can reach optimal rates of convergence.

The proofs of the theorems stated in this paper are gathered in Section 5.

Empirical bound for the localized complexity and localized PAC-Bayesian theorems

2.1. Mutual information between the sample and the parameter. Let us consider Theorem 1.5 with ρ ′ = π ′ = δ θ ′ for a given parameter θ ′ . For the sake of simplicity, let us assume in this subsection that we are in the bounded case (l θ bounded by C). Theorem 1.5 ensures that, for any λ ∈]0, N/(2C)[, with P-

probability at least 1 -ε, for any ρ ∈ M 1 + (Θ), ρ (R) -R(θ ′ ) ≤ ρ (r) -r(θ ′ ) + λ 2N P Θ (l θ -l θ ′ ) 2 dρ(θ) + K(ρ, π) + log 1 ε λ .
This is an incitation to choose ρ = arg min

µ∈M 1 + (Θ) µ (r) + λ 2N P Θ (l θ -l θ ′ ) 2 dρ(θ) + K(µ, π) λ .
However, if we choose to neglect the variance term, we may consider the following randomized estimator:

ρ = arg min µ∈M 1 + (Θ) µ (r) + K(µ, π) λ .
Actually, in this case, Lemma 1.1 leads to:

ρ = π exp(-λr) .
Let us remark that, for any (ρ, π) ∈ M 1 + (Θ) we have:

(2.1)

P K(ρ, π) = P K(ρ, P (ρ)) + K(P (ρ), π).
This implies that, for a given data-dependent ρ, the optimal deterministic measure π is P (ρ) in the sense that it minimizes the expectation of K(ρ, π) (left-hand side of Equation 2.1), making it equal to the expectation of K(ρ, P (ρ)). This last quantity is the mutual information between the estimator and the sample. So, for ρ = π exp(-λr) , this is an incitation to replace the prior π with P π exp(-λr) . It is then natural to approximate this distribution by π exp (-λR) .

In what follows, we replace π by π exp(-βR) for a given β > 0, keeping one more degree of freedom. Now, note that Theorem 1.5 gives:

ρ (R) -R(θ ′ ) ≤ ρ (r) -r(θ ′ ) + λ 2N P Θ (l θ -l θ ′ ) 2 dρ(θ) + K ρ, π exp(-βR) + log 1 ε λ
and note that the upper bound is no longer empirical (observable to the statistician). The aim of the next subsection is to upper bound K ρ, π exp(-βR) by an empirical bound in a general setting.

∈]0, 1] × R * + and (θ, θ ′ ) ∈ Θ 2 , v a, λ N (θ, θ ′ ) = 2N λ λ N N i=1 Φ λ N (ℓ θ -ℓ θ ′ ) (Z i ) ∧ aN λ -r(θ) -r(θ ′ ) . Theorem 2.1. Let us choose a distribution π ∈ M 1 + (Θ). For any ε > 0, for any (a, γ, β) ∈]0, 1] × R * + × R * + such that β < γ, with P-probability at least 1 -ε, for any ρ ∈ M 1 + (Θ), K ρ, π exp(-βR) ≤ BK a,β,γ (ρ, π) + β γ -β log 1 ε
where

BK a,β,γ (ρ, π) = 1 - β γ -1 K ρ, π exp(-βr) + log Θ π exp(-βr) (dθ ′ ) exp Θ ρ(dθ) βγ 2N v a, γ N (θ, θ ′ ) + β∆ γ a (θ, θ ′ ) .
The proof is given in the section dedicated to proofs, more precisely in subsection 5.3 page 16. Note that the localized entropy term is controlled by its empirical counterpart together with a variance term.

Before combining this result with Theorem 1.5, we give the analogous result for the non-integrated case, which proof is also given in subsection 5.3. Theorem 2.2. Let us choose a distribution π ∈ M 1 + (Θ) and a randomized estimator ρ. For any ε > 0 and η > 0, for any (a, γ, β

) ∈]0, 1] × R * + × R * + such that β < γ, with Pρ-probability at least 1 -ε, log dρ dπ exp[-βR] ( θ) ≤ D a,β,γ (ρ, π)( θ) + β γ -β log 1 ε
where

D a,β,γ (ρ, π)( θ) = 1 - β γ -1 log dρ dπ exp[-βr] ( θ) + log Θ π exp(-βr) (dθ ′ ) exp βγ 2N v a, γ N ( θ, θ ′ ) + β∆ γ a ( θ, θ ′ ) .

2.3.

Localized PAC-Bayesian theorems.

Definition 2.2. From now on, we will deal with model selection. We assume that we have a family of submodels of Θ: (Θ i , i ∈ I) where I is finite or countable. We also choose a probability measure µ ∈ M 1 + (I), and assume that we have a prior distribution

π i ∈ M 1 + (Θ i ) for every i. We choose π = i∈I µ(i)π i exp(-βiR)
and apply Theorem 1.3 that we combine with Theorem 2.2 by a union bound argument, to obtain the following result.

Theorem 2.3. Let us assume that we have randomized estimators (ρ i ) i∈I such that ρ i (Θ i ) = 1, for any ε > 0, for any (a, β, β ′ , γ, γ ′ , λ) ∈]0, 1] × (R * + ) 5 such that β < γ and β ′ < γ ′ , with P i∈I ρ i -probability at least 1 -ε over the sample (Z n ) n=1,...,N and the parameters ( θi ) i∈I , for any (i, i ′ ) ∈ I 2 we have:

R λ a θi , θi ′ ≤ Φ -1 λ N r θi -r θi ′ + λ 2N v a, λ N θi , θi ′ + 1 λ D a,β,γ (ρ, π i ) θi + D a,β ′ ,γ ′ (ρ, π i ′ ) θi ′ + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ ) .
In the same way, we can give an integrated variant, using Theorem 1.5 and Theorem 2.1.

Theorem 2.4. For any ε > 0, for any (a, β, β ′ , γ, γ ′ , λ) ∈]0, 1] × (R * + ) 5 such that β < γ and β ′ < γ ′ , with P-probability at least 1 -ε, for any (i, i ′ ) ∈ I 2 and (ρ, ρ ′ ) ∈ M 1 + (Θ i ) × M 1 + (Θ i ′ ), Θ 2 d(ρ ⊗ ρ ′ )(θ, θ ′ )R λ a (θ, θ ′ ) ≤ Φ -1 λ N ρ(r) -ρ ′ (r) + λ 2N Θ 2 d(ρ ⊗ ρ ′ )(θ, θ ′ ) v a, λ N (θ, θ ′ ) + BK a,β,γ (ρ, π i ) + BK a,β ′ ,γ ′ (ρ ′ , π i ′ ) + 1 + β γ-β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ ) λ .
2.4. Choice of the parameters. In this subsection, we explain how to choose the parameters λ, β, β ′ , γ and γ ′ in Theorems 2.3 and 2.4. In some really simple situations (parametric model with strong assumptions on P), this choice can be made on the basis of theoretical considerations, however, in many realistic situations, such hypothesis cannot be made and we would like to optimize the upper bound in the Theorems with respect to the parameters. This would lead to data-dependant values for the parameters, and this is not allowed by Theorems 2.4 and 2.3. Catoni [START_REF] Catoni | PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical Learning)[END_REF] proposes to make a union bound on a grid of values of the parameters, thus allowing optimization with respect to these parameters. We apply this idea to Theorem 2.4, and obtain the following result.

Theorem 2.5. Let us choose a measure ν ∈ M 1 + (Θ) that is supported by a finite or countable set of points, supp(ν). Let us assume that we have randomized estimators (ρ i,β ) i∈I,β∈supp(ν) such that ρ i,β (Θ i ) = 1. For any ε > 0 and a ∈]0, 1], with P i∈I,β∈supp(ν) ρ i,β -probability at least 1 -ε over the sample (Z n ) n=1,...,N and the parameters ( θi,β ) i∈I,β∈supp(ν) , for any (i, i ′ ) ∈ I 2 and (β, β ′ ) ∈ supp(ν) 2 we have: Definition 2.3. Let us choose some real constants ζ > 1, a ∈]0, 1] and ε > 0. We assume that some randomized estimators (ρ i,β ) i∈I,β∈supp(ν) have been chosen and that we have drawn θi,β for every i ∈ I and β ∈ supp(ν). We define, for any i ∈ I,

R λ a θi,β , θi ′ ,β ′ ≤ B (i, β), (i ′ , β ′ ) = inf λ ∈]0, +∞[ γ ∈]β, +∞[ γ ′ ∈]β ′ , +∞[ Φ -1 λ N r θi,β -r θi ′ ,β ′ + λ 2N v a, λ N θi,β , θi ′ ,β ′ + 1 λ D a,β,γ (ρ i,β , π i ) θi,β + D a,β ′ ,γ ′ (ρ i,β ′ , π i ′ ) θi ′ ,β ′ + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εν(λ)ν(γ)ν(β)ν(γ ′ )ν(β ′ )µ(i)µ(i ′ ) .
C i, β = inf γ∈[ζβ,+∞[ D a,β,γ (ρ i,β , π i ) θi,β + β γ -β + 1 ζ -1 + 1 log 3 εµ(i)ν(β)ν(γ)
.

We have the following result.

Theorem 2.6. For any

(i, i ′ , β, β ′ ) ∈ I 2 × supp(ν) 2 , B (i, β), (i ′ , β ′ ) ≤ inf λ>0 Φ -1 λ N r θi,β -r θi ′ ,β ′ + λ 2N v a, λ N θi,β , θi ′ ,β ′ + C θi,β + C θi ′ ,β ′ + ζ+1 ζ-1 log 3 εν(λ) λ .
Note, as a consequence of the concavity of Φ -1 λ N

, that this implies Corollary 2.7.

B (i, β), (i ′ , β ′ ) + B (i ′ , β ′ ), (i, β) ≤ 2 inf λ>0 Φ -1 λ N λ 2N v a, λ N θi,β , θi ′ ,β ′ + v a, λ N θi ′ ,β ′ , θi,β 2 + C (i, β) + C (i ′ , β ′ ) + ζ+1 ζ-1 log 3 εν(λ)
λ .

Corollary 2.7 shows that the symmetric part of B has an upper bound which contains only variance and complexity terms.

Application: model selection

In this section, we propose a general algorithm to select among a family of posteriors -and so to perform model selection as a particular case. This algorithm was introduced by Catoni [START_REF] Catoni | PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical Learning)[END_REF] in the case of classification. We first give the general form of the estimator. We then give an empirical bound on its risk. The last subsection is devoted to a theoretical bound under suitable hypothesis.

3.1. Selection algorithm. We introduce the following definition for the sake of simplicity.

Definition 3.1. Let us put:

P = t 1 , ..., t M = {(i, β) ∈ I × supp(ν)} ,
where M = |I| × |supp(ν)| and the indexation of the t i 's is such that

C(t 1 ) ≤ ... ≤ C(t M ).
Now, remark that there is no reason for the bound B defined in Theorem 2.5 to be sub-additive. So let us define a sub-additive version of B. Definition 3.2. We put, for any (t, t ′ ) ∈ P 2 :

B(t, t ′ ) = inf h ≥ 1 (t 0 , ..., t h ) ∈ P h+1 t 0 = t, t h = t ′ h k=1 B(t k-1 , t k ).
Definition 3.3. For any k ∈ {1, ..., M } we put:

s(k) = inf j ∈ {1, ..., M }, B(t k , t j ) > 0 .
We are now ready to give the definition of our estimator.

Definition 3.4. We take as an estimator θt where t = t k and k = min (arg max s) .

3.2.

Empirical bound on the risk of the selected estimator.

Theorem 3.1. Let us put ŝ = s( k). For any ε > 0, with P t∈P ρ t -probability at least 1 -ε,

R θt ≤ R θt j +          0, 1 ≤ j < ŝ, B(t s(j) , t j ) ŝ ≤ j < k, B( t, t ŝ) + B(t ŝ, t j ), j ∈ (arg max s) B( t, t j ),
otherwise.

Thus, adding only non negative terms to the bound,

R θt ≤ R θt j +                0, 1 ≤ j < ŝ, B(t s(j) , t j ) + B(t j , t s(j) ) ŝ ≤ j < k, B(t j , t ŝ) + B(t ŝ, t j ) +B( t, t ŝ) + B(t ŝ, t ) j ∈ (arg max s), B(t j , t ) + B( t, t j ),
otherwise.

For a proof, we refer the reader to Catoni [START_REF] Catoni | PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical Learning)[END_REF] where this Theorem is proved in the case of classification, the proof can be reproduced here without any modification.

Theorem 3.1 shows that, according to Corollary 2.7 (page 12), R( θt ) -R( θt j ) can be bounded by variance and complexity terms relative to posterior distributions with a complexity not greater than C(t j ), and an empirical loss in any case not much larger than the one of θt j .

Theoretical bound.

In this subsection, we choose ρ i,β as π i exp(-βr) restricted to a (random) neighborhood of θi . More formally, for any p ≥ 0, let us put

Θ i,p = θ ∈ Θ i , r(θ) -inf Θi r ≤ p
and for any q ∈]0, 1] let us put

p i,β (q) = inf p > 0, π i exp(-βr) (Θ i,p ) ≥ q .
Then let us choose q once and for all and let us choose ρ i,β so that

dρ i,β dπ i exp(-βr) (θ) = 1 Θ i,p i,β (q) (θ) π i exp(-βr) Θ i,p i,β (q)
. Moreover, we assume that 0 ≤ l θ (z) ≤ C for any θ ∈ Θ and z ∈ Z, and we fix a = 1. In this case, note that for any λ ≤ N/(2C) we have:

v 1, λ N (θ, θ ′ ) ≤ P (l θ -l θ ′ ) 2 .
For the sake of simplicity we introduce the following definition.

Definition 3.5. Let us put, for any (θ, θ ′ ) ∈ Θ 2 :

v(θ, θ ′ ) = P (l θ -l θ ′ ) 2 and V (θ, θ ′ ) = P [v(θ, θ ′ )] .
To obtain the following result we take ν as the uniform measure on the grid Let us assume that Mammen and Tsybakov's margin assumption is satisfied, in other words let there exist

supp(ν) = 2 0 , 2 1 , ..., 2 ⌊ log N log 2 ⌋ .
(κ, c) ∈ [1, +∞[×R * + such that ∀θ ∈ Θ, V (θ, θ) κ ≤ c R(θ) -R(θ) .
Let moreover every sub-model Θ i , i ∈ I satisfy the following dimension assumption:

sup ξ∈R ξ π i exp(-ξR) (R) -R θ i ≤ d i for a given sequence (d i ) i∈I ∈ (R + ) I .
Then there is a constant C = C(κ, c, C) such that, with P i∈I,β∈supp(ν) ρ i,β -probability at least 1 -4ε,

R θt ≤ inf i∈I R θ i +C max R θ i -R θ 1 κ d i + log 1 q + log 1+log 2 N εµ(i) N 1 2 , d i + log 1 q + log 1+log 2 N εµ(i) N κ 2κ-1 .
For a proof, see subsection 5.4 page 16. Let us now make some remarks. Remark 3.1 (Choice of the parameter q). The better choice for q is obviously q = 1. In this case, our estimator is drawn randomly from the distribution, ρ i,β = π i exp(-βr) , and the term log(1/q) vanishes.

However, practitioners worried about the idea to choose randomly in the whole space an estimator can use a smaller value of q ensuring that, in any model i and for any β, r θi,β ≤ inf Θi r + p i,β (q), so θi,β is drawn in a neighborhood of the minimizer of the empirical risk.

Remark 3.2 (Margin assumption). The so-called margin assumption

V (θ, θ) κ ≤ c R(θ) -R(θ)
was first introduced by Mammen and Tsybakov in the context of classification [START_REF] Mammen | Smooth discrimination analysis in statistical learning[END_REF][START_REF] Tsybakov | Optimal aggregation of classifiers in statistical learning[END_REF]. It has however been studied in the context of general regression by Lecue in his PhD Thesis [START_REF] Lecue | Aggregation Procedures: Optimality and Fast Rates[END_REF]. The terminology comes from classification, where a similar assumption can be described in terms of margin. In the general case however, there is no margin involved, but rather a distance V (θ, θ ′ ) 1/2 on the parameter space, which serves to describe the shape of the function R in the neighborhood of its minimum value R(θ).

Remark 3.3 (Dimension assumption). In many cases, the assumption

sup ξ∈R ξ π i exp(-ξR) (R) -R θ i ≤ d i
is just equivalent to the fact that every Θ i has a finite dimension proportionnal to d i .

Conclusion

In this paper we studied a quite general regression problem. We proposed randomized estimators, that can we drawn in small neighborhoods of empirical minimizers. We proved that these estimators reach the minimax rate of convergence under Mammen and Tsybakov's margin assumption.

We would like also to point out that the techniques used here can be applied in a more general context. In particular, Catoni [START_REF] Catoni | PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical Learning)[END_REF] studied the transductive classification setting, where for a given k ∈ N, we observe the objects X 1 , • • • , X (k+1)N and the labels Y 1 ,• • • ,Y N , and we want to predict the kN missing labels Y N +1 ,• • • ,Y (k+1)N . In this context, a deviation result equivalent to Lemma 1.2 (page 6) can be proved, and from this result we can obtain a theorem similar to Theorem 3.1 (page 12). We refer the reader to our PhD thesis [START_REF] Alquier | Transductive and Inductive Adaptative Inference for Regression and Density Estimation[END_REF] for more details (the transductive setting is introduced page 54 and the deviation result is Lemma 3.1 page 56).

Proofs

5.1. Proof of Lemma 1.1. For the sake of completeness, we reproduce here the proof of Lemma 1.1 given in Catoni [START_REF] Catoni | A pac-bayesian approach to adaptative classification[END_REF].

Proof of Lemma 1.1. Let us assume that h is upper-bounded on the support of n. Let us remark that m is absolutely continuous with respect to n if and only if it is absolutely continuous with respect to n exp(h) . If it is the case, then

K m, n exp(h) = m log dm dn -h + log n(exp •h) = K(m, n) -m(h) + log n(exp •h).
The left-hand side of this equation is nonnegative and cancels only for m = n exp(h) . Note that it remains valid when m is not absolutely continuous with respect to n and just says in this case that +∞ = +∞. We therefore obtain 0 = inf

m∈M 1 + (E) [K(m, n) -m(h)] + log n(exp •h).
This proves the second part of lemma 1.1. For the first part, we do not assume any longer that h is upper bounded on the support of n. We can write log n(exp

•h) = sup B∈R log n[exp •(h ∧ B)] = sup B∈R sup m∈M 1 + (E) [m (h ∧ B) -K(m, n)] = sup m∈M 1 + (E) sup B∈R [m (h ∧ B) -K(m, n)] = sup m∈M 1 + (E) sup B∈R [m (h ∧ B)] -K(m, n) = sup m∈M 1 + (E) [m(h) -K(m, n)] .

Proof of Theorem 1.5.

Proof of Theorem 1.5. The beginning of this proof follows exactly the proof of Theorem 1.3 (page 7) until Equation 1.2. Now, let us apply (to Equation 1.2) Lemma 1.1 with (E, E) = (Θ 2 , T ⊗2 ) to obtain:

P exp sup m∈M 1 + (Θ 2 ) Θ 2 λΦ λ N R λ a (θ, θ ′ ) - λ N N i=1 Φ λ N (ℓ θ -ℓ θ ′ ) (Z i ) ∧ aN λ dm(θ, θ ′ ) -K(m, π ⊗ π ′ ) = 1. Consequently P exp sup (ρ,ρ ′ )∈[M 1 + (Θ)] 2 Θ 2 λΦ λ N R λ a (θ, θ ′ ) - λ N N i=1 Φ λ N (ℓ θ -ℓ θ ′ ) (Z i ) ∧ aN λ d(ρ ⊗ ρ ′ )(θ, θ ′ ) -K(ρ, π) -K(ρ ′ , π ′ ) = 1.
This ends the proof.

Proof of Theorems 2.1 and 2.2.

Proof of Theorem 2.1. First, notice that:

K ρ, π exp(-βR) = β ρ(R) -π exp(-βR) (R) + K (ρ, π) -K π exp(-βR) , π .
Let us apply Theorem 1.5 with π = π ′ = ρ ′ = π exp(-βR) to obtain with probability at least 1 -ε, for any ρ ∈ M 1 + (Θ),

K ρ, π exp(-βR) ≤ β ρ(r) -π exp(-βR) (r) + γ 2N Θ 2 v a, γ N (θ, θ ′ )d ρ ⊗ π exp(-βR) (θ, θ ′ ) + log 1 ε + K ρ, π exp(-βR) γ + Θ 2 ∆ λ a (θ, θ ′ )d ρ ⊗ π exp(-βR) (θ, θ ′ ) + K (ρ, π) -K π exp(-βR) , π .
Replacing in the right-hand side of this inequality π exp(-βR) with a supremum over all possible distributions leads to the announced result.

Proof of Theorem 2.2. We have, for any θ:

log dρ dπ exp(-βR) (θ) = β R(θ) -π exp(-βR) (R) + log dρ dπ (θ) -K π exp(-βR) , π .
Let us apply Theorem 1.3 with π = π ′ = ρ ′ = π exp(-βR) and a general ρ to obtain with Pρ-probability at least 1 -ε over θ,

log dρ dπ exp(-βR) (θ) ≤ β r(θ) -π exp(-βR) (r) + γ 2N Θ v a, γ N (θ, θ ′ )dπ exp(-βR) (θ ′ ) + log 1 ε + K ρ, π exp(-βR) γ + Θ ∆ λ a (θ, θ ′ )dπ exp(-βR) (θ ′ ) + log dρ dπ (θ) -K π exp(-βR) , π .
The end of the proof is the same as in the case of Theorem 2.1.

5.4.

Proof of Theorem 3.2. We begin by a set of preliminary lemmas and definitions.

Definition 5.1. For the sake of simplicity, we will write:

r ′ (θ, θ ′ ) = r(θ) -r(θ ′ ) and R ′ (θ, θ ′ ) = R(θ) -R(θ ′ ) for any (θ, θ ′ ) ∈ Θ 2 .
Definition 5.2. We introduce the margin function:

ϕ : R * + → R x → sup θ∈Θ V (θ, θ) -xR ′ (θ, θ) .
Lemma 5.1 (Mammen and Tsybakov [START_REF] Mammen | Smooth discrimination analysis in statistical learning[END_REF][START_REF] Tsybakov | Optimal aggregation of classifiers in statistical learning[END_REF]). Mammen's and Tsybakov margin assumtion:

∃(κ, c) ∈ [1, +∞[×R * + , ∀θ ∈ Θ, V (θ, θ) κ ≤ cR ′ (θ, θ) implies: ∀x > 0, ϕ(x) ≤ 1 - 1 κ (κcx) -1 κ-1
for κ > 1 and ϕ(c) ≤ 0 for κ = 1.

Definition 5.3. We define the modified Bernstein function:

g : R → R x →    2[exp(x)-1-x] x 2 if x = 0, 1 if x = 0.
The function g is a variant of Bernstein's function, used in Bernstein's inequality (see Bernstein [START_REF] Bernstein | Theory of Probability[END_REF]). Here, we prove a variant of this inequality. Lemma 5.2 (Variant of Bernstein's inequality). We have, for any λ > 0 and any (θ, θ ′ ) ∈ Θ 2 :

(5.1)

P exp λR ′ (θ, θ ′ ) -λr ′ (θ, θ ′ ) - λ 2 2N g 2λC N V (θ, θ ′ ) ≤ 1,
and the reverse inequality

(5.2) P exp λr ′ (θ, θ ′ ) -λR ′ (θ, θ ′ ) - λ 2 2N g 2λC N V (θ, θ ′ ) ≤ 1.
We also have a similar inequality for variances:

(5.3) P exp N 4C 2 v(θ, θ ′ ) - N 2C 2 V (θ, θ ′ ) ≤ 1.
Proof. We have:

P exp [λR ′ (θ, θ ′ ) -λr ′ (θ, θ ′ )] = exp N i=1 log P exp - λ N (l θ -l θ ′ ) (Z i ) + λR ′ (θ, θ ′ ) .
Now, note that for any b > 0, for any x ∈ [-b, b] we have:

exp(-x) = 1 -x + x 2 2 g(-x) ≤ 1 -x + x 2 2 g(b), so that log P exp - λ N (l θ -l θ ′ ) (Z i ) ≤ -λR ′ (θ, θ ′ ) + λ 2 2N g 2Cλ N V (θ, θ ′ ).
It shows that

P exp [λR ′ (θ, θ ′ ) -λr ′ (θ, θ ′ )] ≤ exp λ 2 2N g 2Cλ N V (θ, θ ′ ) .
The proof of the reverse inequality follows the same scheme. For Inequality (5.3) note that, using the same scheme, we obtain:

P exp λv(θ, θ ′ ) -λV (θ, θ ′ ) - λ 2 2N g 4λC 2 N P (l θ -l θ ′ ) 4 (Z) ≤ 1.
This implies that

P exp λv(θ, θ ′ ) -λV (θ, θ ′ ) - λ 2 2C 2 N g 4λC 2 N V (θ, θ ′ ) ≤ 1.
The choice λ = N/4C 2 and the remark that g(1) ≤ 2 (actually g(1) ≃ 1.4) leads to Inequality (5.3).

P. ALQUIER

Definition 5.4. For the sake of shortness, we put:

δ N (i, q, ε, κ) = max R θ i -R θ 1 κ d i + log 1 q + log 1+log 2 N εµ(i) N 1 2
,

d i + log 1 q + log 1+log 2 N εµ(i) N κ 2κ-1
. Now let us give a brief overview of what follows. Lemma 5.3 proves that for some β, θi,β achieves the expected rate of convergence in model Θ i : δ N (i, q, ε, κ). As we then want to use Theorem 3.1 to compare our estimator θt to every possible θi,β , we will have to control the various parts of the empirical bound B(., .) by theoretical terms. So we give two more lemmas: Lemma 5.4 controls the empirical variance term v(., .) by the theoretical variance term V (., .) while Lemma 5.5 provides a control for the empirical complexity term C(i, β). Given these three results we will be able to prove Theorem 3.2. Let us start with Lemma 5.3. Under the assumptions of Theorem 3.2, there is a constant

C ′ = C ′ (κ, c, C) such that, with P i∈I,β∈supp(ν) ρ i,β -probability at least 1 -ε, for any i ∈ I, there is a β = β * (i) ∈ supp(ν) such that R ′ θi,β , θ i ≤ C ′ δ N (i, q, ε, κ).
Proof. We have, by Inequality (5.1) in Lemma 5.2:

1 ≥ π i exp(-βR) P exp λR ′ (., θ i ) -λr ′ (., θ i ) - λ 2 2N g 2λC N V (., θ i ) ≥ Pρ i,β exp λR ′ (., θ i ) -λr ′ (., θ i ) - λ 2 2N g 2λC N V (., θ i ) -log dρ i,β dπ i exp(-βR) (.) . Thus µ(i)ν(β) ≥ Pρ i,β exp λR ′ (., θ i ) -λr ′ (., θ i ) - λ 2 2N g 2λC N V (., θ i ) -log dρ i,β dπ i exp(-βR) (.) + log(µ(i)ν(β)) .
So, with P i∈I,β∈supp(ν) ρ i,β -probability at least 1 -ε/2, for any i ∈ I and β ∈ supp(ν),

(5.4) λR ′ ( θi,β , θ i ) ≤ λr ′ ( θi,β , θ i ) + λ 2 2N g 2λC N V ( θi,β , θ i ) + log dρ i,β dπ i exp(-βR) ( θi,β ) + log 2 εµ(i)ν(β) .
Note that, using Definition 5.2, for any x > 0,

V ( θi,β , θ i ) ≤ 2 V ( θi,β , θ) + V (θ, θ i ) ≤ 2 xR ′ ( θi,β , θ) + xR ′ (θ i , θ) + 2ϕ(x) .
Therefore Inequality (5.4) becomes:

λ - xλ 2 N g 2Cλ N R ′ ( θi,β , θ) ≤ λ + xλ 2 N g 2Cλ N R ′ (θ i , θ) + λr ′ ( θi,β , θ i ) + 2ϕ(x)λ 2 N g 2λC N + β R θi,β -π i exp(-βR) R + log dρ i,β dπ i ( θi,β ) -K π i exp(-βR) , π i + log 2 εµ(i)ν(β) , leading to λ - xλ 2 N g 2Cλ N -β R ′ ( θi,β , θ) ≤ λ + xλ 2 N g 2Cλ N -β R ′ (θ i , θ) + 2ϕ(x)λ 2 N g 2λC N -βπ i exp(-βR) R ′ (., θ i ) + log dρ i,β dπ i exp(-βr) ( θi,β ) -log π i exp -λr ′ (., θ i ) -K π i exp(-βR) , π i + log 2 εµ(i)ν(β) and (5.5) λ - xλ 2 N g 2Cλ N -β R ′ ( θi,β , θ i ) ≤ 2xλ 2 N g 2Cλ N R ′ (θ i , θ) + 2ϕ(x)λ 2 N g 2λC N -βπ i exp(-βR) R ′ (., θ i ) + log dρ i,β dπ i exp(-βr) ( θi,β ) -log π i exp -λr ′ (., θ i ) -K π i exp(-βR) , π i + log 2 εµ(i)ν(β)
.

We can then use Inequality (5.2) (in Lemma 5.2, page 17) to obtain, with probability at least 1 -ε/2, for any i ∈ I and β ∈ supp(ν),

(5.6) -log π i exp -λr ′ (., θ i ) ≤ λπ i exp(-βR) r ′ (., θ i ) + K π i exp(-βR) , π i ≤ λπ i exp(-βR) R ′ (., θ i ) + λ 2 2N g 2Cλ N π i exp(-βR) V (., θ i ) + K π i exp(-βR) , π i -log εµ(i)ν(β) 2 ≤ λ + xλ 2 N g 2Cλ N π i exp(-βR) R ′ (., θ i ) + xλ 2 N g 2Cλ N R ′ (θ i , θ) + 2ϕ(x)λ 2 N g 2Cλ N + K π i exp(-βR) , π i + log 2 εµ(i)ν(β)
.

Combining Inequalities (5.5) and (5.6) we have, with probability at least 1 -ε, for any i and β:

(5.7) λ - xλ 2 N g 2Cλ N -β R ′ ( θi,β , θ i ) ≤ 4xλ 2 N g 2Cλ N R ′ (θ i , θ) + 4ϕ(x)λ 2 N g 2λC N + λ + xλ 2 N g 2Cλ N -β π i exp(-βR) R ′ (., θ i ) + log dρ i,β dπ i exp(-βr) ( θi,β ) + 2 log 2 εµ(i)ν(β)
.

In order to make explicit the terms in Inequality 5.7, let us remind the definition of ρ i,β in Theorem 3.2 (page 13) and remark that

log dρ i,β dπ i exp(-βr) ( θi,β ) ≤ log 1 q .
Let us also recall the dimension hypothesis in Theorem 3.2, implying that

π i exp(-βR) R ′ (., θ i ) ≤ d i β .
Let us finally choose λ = 2β, Inequality 5.7 becomes:

(5.8)

β - 16xβ 2 N g 4Cβ N R ′ ( θi,β , θ i ) ≤ 16xβ 2 N g 4Cβ N R ′ (θ i , θ) + 16ϕ(x)β 2 N g 4βC N + β + 4xβ 2 N g 4Cβ N d i + log 1 q + 2 log 2 εµ(i)ν(β)
.

Finally, Lemma 5.1 together with the margin assumption in Theorem 3.2 ensures that

ϕ(x) ≤ 1 - 1 κ (κcx) -1 κ-1 if κ > 1 and ϕ(c) ≤ 0 if κ = 1.
Let us first deal with the case κ = 1. Inequality (5.8) becomes, taking x = c,

(5.9) R ′ ( θi,β , θ i ) ≤ 1 2 - 4cβ N g 4Cβ N -1 16cβ N g 4Cβ N R ′ (θ i , θ) + 1 + 4cβ N g 4Cβ N d i β + 1 β log 1 q + 2 β log 2 εµ(i)ν(β) .
In the right-hand side of Inequality 5.9, the numerator is optimal for β of the order of

N d i + log 1 q + log 2 εµ(i)ν(β)
R ′ (θ i , θ) but in order to keep the denominator away from zero, the maximal order of magnitude for β is N , so let us take β of the order of min

     N d i + log 1 q + log 2 εµ(i)ν(β) R ′ (θ i , θ) , N      .
This choice leads to:

(5.10) R ′ ( θi,β , θ i ) ≤ C ′′ max R θ i , θ d i + log 1 q + log 1+log 2 N εµ(i) N 1 2 , d i + log 1 q + log 1+log 2 N εµ(i) N = C ′′ δ N (i, q, ε, 1)
for some C ′′ = C ′′ (c, C). In the case where κ > 1, Inequality (5.8) becomes:

(5.11) R ′ ( θi,β , θ i ) ≤ 1 2 - 4xβ N g 4Cβ N -1 16xβ N g 4Cβ N R ′ (θ i , θ) + 1 - 1 κ 16β(κcx) -1 κ-1 N g 4βC N + 1 + 4xβ N g 4Cβ N d i β + 1 β log 1 q + 2 β log 2 εµ(i)ν(β)
. Now, we choose x or the order of min R ′ θ i , θ

-κ-1 κ , N β
in Inequality (5.11) (the case x = R ′ θ i , θ

κ-1 κ minimizes the numerator while the fact that x = O(N/β) ensures that the denominator does not get too close to zero). Now, let us consider both cases for x, and first x = R ′ θ i , θ -κ-1 κ . In this case, let us choose β of the order of min

       N d i + log 1 q + log 2 εµ(i)ν(β) R ′ (θ i , θ) 1 κ , N        .
This leads to a bound of the order of max R θ i , θ

1 κ d i + log 1 q + log 1+log 2 N εµ(i) N 1 2 , d i + log 1 q + log 1+log 2 N εµ(i) N ≤ δ N (i, q, ε, κ).
In the other case, x is of the order of N/β and

R ′ θ i , θ -κ-1 κ ≥ N β , implying that R ′ θ i , θ ≤ β N κ κ-1 .
We have to choose β in order to optimize the numerator, in this case the optimal order of magnitude is

d i + log 1 q + log 1 + log 2 N εµ(i) κ-1 N 1 2κ-1
and leads to a bound of the order of

d i + log 1 q + log 1+log 2 N εµ(i) N κ 2κ-1 ≤ δ N (i, q, ε, κ).
So we have proved that, in the case κ > 1, for some

C ′′′ = C ′′′ (κ, c, C), (5.12) R ′ ( θi,β , θ i ) ≤ C ′′′ δ N (i, q, ε, κ).
We put:

C ′ (κ, c, C) =    C ′′ (c, C) if κ = 1 C ′′′ (κ, c, C) if κ > 1
and remark that Inequalities (5.10) and (5.12) end the proof.

Lemma 5.4. Under the assumptions of Theorem 3.2, with P i∈I,β∈supp(ν) ρ i,βprobability at least 1 -ε, for any (i, i ′ ) ∈ I 2 , for any (β, γ, β ′ , γ ′ ) ∈ supp(ν) 4 :

v θi,β , θi ′ ,β ′ ≤ 2V θi,β , θi ′ ,β ′ + 4C 2 N D 1,β,γ ρ i,β , π i θi,β + D 1,β ′ ,γ ′ ρ i ′ ,β ′ , π i ′ θi ′ ,β ′ + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ )
.

Proof. According to Inequality (5.3) (Lemma 5.2 page 17),

P exp N 4C 2 v(θ, θ ′ ) - N 4C 2 V ′ (θ, θ ′ ) ≤ 1.
Let us integrate in (θ, θ ′ ) with respect to the distribution

π i exp(-βR) ⊗ π i ′ exp(-β ′ R)
and sum over all i, i ′ , β and β ′ to obtain, with P i∈I,β∈supp(ν) ρ i,β -probability at least 1 -ε/3, for any (i, i ′ ) ∈ I 2 , for any (β,

β ′ ) ∈ supp(ν) 2 : v θi,β , θi ′ ,β ′ ≤ 2V ′ θi,β , θi ′ ,β ′ + 4C 2 N log dρ i,β dπ i exp(-βR) θi,β + log dρ i ′ ,β ′ dπ i ′ exp(-β ′ R) θi ′ ,β ′ + log 3 ε .
To conclude the proof, there remains to combine this result with Theorem 2.2 page 10, using a union bound argument.

Lemma 5.5. Under the assumptions of Theorem 3.2, there is a constant K = K(κ, c, C) such that, with P i∈I,β∈supp(ν) ρ i,β -probability at least 1 -ε, for any i ∈ I, there is γ ∈ supp(ν) such that, for β = β * (i),

D 1,β,γ (ρ i,β , π i ) θi,β ≤ C(i, β) ≤ Kδ N (i, q, ε, κ)β.
Proof. We have

D 1,β,γ (ρ i,β , π i ) θi,β = 1 - β γ -1 log dρ i,β dπ i exp(-βr) θi,β + log π i exp(-βr) exp βγ 2N v ., θi,β ≤ 1 - β γ -1 log 1 q + log π i exp βγ 2N v .
, θi,β -βr ′ (., θ)

log π i exp -βr ′ (., θ) .

Let us now apply Lemma 5.2 and the now usual integration technique to obtain the following inequalities, with probability at least 1 -4ε/5:

log π i exp -βr ′ (., θ) =sup

ρ∈M 1 + (Θi) -βρr ′ (., θ) -K(ρ, π i ) ≤ -sup ρ∈M 1 + (Θi) -βρR ′ (., θ) + β 2 2N g 2βC N V (., θ) + log 5 ε -K(ρ, π i ) ≤ -log π i exp -βR ′ (., θ) + β 2 2N g 2βC N V (., θ) + log 5 ε . Moreover log π i exp βγ 2N v ., θi,β -βr ′ (., θ) ≤ log π i exp βγ N V (., θi,β )βR ′ (., θ) + β 2 2N g 2βC N V (., θ) + βγ4C 2 N 2 D 1,β,γ (ρ i,β , π i ) θi,β + 1 + 4βγC 2 N 2 + 4γC 2 β 2 N (γ -β) log 5 ε , so that 1 - β γ - βγ4C 2 N 2 D 1,β,γ (ρ i,β , π i ) θi,β ≤ log 1 q + log π i exp(-βR) exp βγ N + β 2 N g 2βC N V (., θ) + 2 + 4βγC 2 N 2 + 4γC 2 β 2 N (γ -β) log 5 ε ≤ log 1 q + log π i exp(-βR) exp x βγ N + β 2 N g 2βC N R ′ (., θ i ) + 2βγ N + β 2 N g 2βC N xR ′ (θ i , θ) + ϕ(x) + x βγ N R ′ ( θi,β , θ i ) + 2 + 4βγC 2 N 2 + 4γC 2 β 2 N (γ -β) log 5 ε .
We then apply Lemma 5.3 to obtain with probability at least 1 -ε/5

R ′ ( θi,β , θ i ) ≤ C ′ δ N (i, q, ε/5, κ).
Moreover we can choose γ = 2β, and remember that the choice β = β * (i) leads to β < N , so

(5.13) 1 2 - β 2 8C 2 N 2 D 1,β,2β (ρ i,β , π i ) θi,β ≤ log 1 q + log π i exp(-βR) exp xβ 2 N [2 + g (2C)] R ′ (., θ i ) + β 2 N [2 + g (2C)] xR ′ (θ i , θ) + ϕ(x) + 2xβ 2 N C ′ δ N (i, q, ε/5, κ) + 2 + 12β 2 C 2 N 2 log 5 ε .
Now, let us compute:

log π i exp(-βR) exp xβ 2 N [2 + g (2C)] R ′ (., θ i ) ≤ β 2 N [2 + g(2C)] x 0 π i exp{-β[1-δβ N (2+g(2C))]} R ′ (., θ i )dδ ≤ β 2 N [2 + g(2C)] β 1 -xβ N [2 + g(2C)] xπ i exp{-β[1-xβ N (2+g(2C))]} R ′ (., θ i ) ≤ xd i β N 2 + g(2C) 1 -xβ N [2 + g(2C)
] by the dimension assumption, and so for any x smaller than N/β, Inequality 5.13 becomes

(5.14) 1 2 - β 2 8C 2 N 2 D 1,β,2β (ρ i,β , π i ) θi,β ≤ 2βC ′ δ N (i, q, ε/5, κ) + β 1 β log 1 q + d i β 2 + g(2C) 1 -xβ N [2 + g(2C)] + β N [2 + g (2C)] xR ′ (θ i , θ) + ϕ(x) + 2 + 12g(2C) β log 5 ε .
The optimization of the right-hand side of Inequality (5.14) with respect to x and β leads to the same discussion as for the optimization of the right-hand side of Inequality (5.8) (page 20) in the proof of Lemma 5.3 (and a choice of x satisfying x < N/β).

We are now able to proceed to the proof of Theorem 3.2. With P i∈I,β∈supp(ν) ρ i,β -probability at least 1 -4ε the inequalities stated in Theorem 3.1 and in Lemmas 5.3, 5.4 and 5.5 are simultaneously satisfied. In this case, let us choose i ∈ I, β = β * (i) and j such that t j = (i, β).

We have:

R ′ θt , θ(i,β) ≤                0, 1 ≤ j < ŝ (case 1
), B(t s(j) , t j ) + B(t j , t s(j) ) ŝ ≤ j < k (case 2), B(t j , t ŝ) + B(t ŝ, t j ) +B( t, t ŝ) + B(t ŝ, t) j ∈ (arg max s) (case 3), B(t j , t) + B( t, t j ), otherwise (case 4).

Let us examine successively the four cases (1, 2, 4 and 3, this last case being the most difficult).

Case 1: if 1 ≤ j < ŝ, then R ′ θt , θ(i,β) ≤ 0,
and so, by the result of Lemma 5.3 (page 18),

R ′ θt , θ i ≤ C ′ δ N (i, q, ε, κ).
Case 2: the idea in all the remaining cases (2, 4 and 3) is that we have to give a control of R ′ θt , θ(i,β) , controlled by the empirical bound B(., .), in terms of theoretical quantities only. In case 2, ŝ ≤ j < k, then for any λ ∈ supp(ν), R ′ θt s(j) , θ(i,β) ≤ B(t s(j) , t j ) + B(t j , t s(j) )

≤ λ 2N v(t s(j) , t j ) + C(t s(j) ) + C(t j ) + ζ+1 ζ-1 log 3 εν(λ) λ ≤ λ N V (t s(j) , t j ) + C(t j ) + C(t s(j) ) + ζ+1 ζ-1 log 3 εν(λ) λ + 4C 2 λ N 2 C(t j ) + C(t s(j) ) + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ )
.

As we have, by definition of the function s(.), the inequality C(t s(j) ) ≤ C(t j ),

R ′ θt s(j) , θ(i,β) ≤ λ N V (t s(j) , t j ) + 2C(t j ) + ζ+1 ζ-1 log 3 εν(λ) λ + 4C 2 λ N 2 2C(t j ) + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ ) ,
and so

(5.15) R ′ θt s(j) , θt j ≤ 2λ N xR ′ θt s(j) , θ + xR ′ θt j , θ + ϕ(x) + 2C(t j ) + ζ+1 ζ-1 log 3 εν(λ) λ + 4C 2 λ N 2 2C(t j ) + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ ) . Thus 1 - 2λx N R ′ θt s(j) , θt j ≤ 2λ N 2xR ′ ( θt j , θ i ) + 2xR ′ (θ i , θ) + ϕ(x) + 2C(t j ) + ζ+1 ζ-1 log 3 εν(λ) λ + 4C 2 λ N 2 2C(t j ) + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ )
.

Let us apply Lemma 5.5 page 22 to upper bound C(t j ), Lemma 5.3 page 18 to upper bound R ′ ( θt j , θ i ) and Lemma 5.1 page 16 to upper bound ϕ(x). Let us put moreover λ = γ = γ ′ = 2β = 2β ′ and remember that β < N . We obtain, for any x such that x < N/β,

1 - 4βx N R ′ θt s(j) , θt j ≤ 4β N 2xR ′ θ i , θ + 1 - 1 κ (κcx) -1 κ-1 + [K(1 + 32C 2 ) + 8C ′ ]δ N (i, q, ε, κ) + 1 2β + ζ + 1 ζ -1 log 3 εν(λ) 2β + 48C 2 N log 3 εµ(i)µ(i ′ ) .
Let us replace x and β by the values given in the discussion for the optimization of the right-hand side of Inequality (5.8) (page 20) in the proof of Lemma 5.3 (and a choice of x satisfying x < N/β) to obtain the existence of a constant D ′ = D ′ (κ, c, C) such that R ′ θt s(j) , θt j ≤ D ′ δ N (i, q, ε, κ).

We then deduce from this result and from Lemma 5.3 that R ′ θt , θ i ≤ R ′ θt , θt j + R ′ θt j , θ i ≤ (D ′ + C ′ ) δ N (i, q, ε, κ).

Case 4: the proof follows roughly the same scheme than for case 2; if j > max(arg max s), note that C(t j ) ≥ C( t ), therefore R ′ θt , θ(i,β) ≤ B( t, t j ) + B(t j , t)

≤ λ 2N v(
β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ )
.

Let us apply Lemma 5.5 page 22 to upper bound C(t j ), Lemma 5.3 page 18 to upper bound R ′ ( θt j , θ i ) and Lemma 5.1 page 16 to upper bound ϕ(x). Let us put moreover λ = γ = γ ′ = 2β = 2β ′ and remember that β < N . We obtain, for any x such that x < N/β,

1 - 4βx N R ′ θt s(j) , θ(i,β) ≤ 4β N 2xR ′ θ i , θ + 1 - 1 κ (κcx) -1 κ-1 + [K(1 + 32C 2 ) + 8C ′ ]δ N (i, q, ε, κ) + 1 2β + ζ + 1 ζ -1 log 3 εν(λ) 2β + 48C 2 N log 3 εµ(i)µ(i ′ )
.

Choosing x exactly in the same way as in the previous cases and replacing β = β * (i) with its value, we obtain the existence of D ′′ = D ′′ (κ, c, C) such that R ′ θt , θ(i,β) ≤ D ′′ δ N (i, q, ε, κ)

and so R θt , θ i ≤ (C ′ + D ′′ ) δ N (i, q, ε, κ).

Case 3: if j ∈ (arg max s), remember that ŝ = s( t) = s(j), so that (5.16) R ′ θt , θt j ≤ B(t j , t s(j) ) + B(t s(j) , t j ) + B( t, t ŝ) + B(t ŝ, t) .

We are going to upper bound separately B(t j , t s(j) ) + B(t s(j) , t j ) and B( t, t ŝ) + B(t ŝ, t). Let us first deal with the term B(t j , t s(j) ) + B(t s(j) , t j ):

(5.17) B(t j , t s(j) ) + B(t s(j) , t j ) ≤ λ 2N v(t s(j) , t j ) + 2C(t j ) + ζ+1 ζ-1 log 3 εν(λ) λ ≤ λ N V (t s(j) , t j ) + 2C(t j ) + ζ+1 ζ-1 log 3

εν(λ) λ + 4C 2 λ N 2 2C(t j ) + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ ) ≤ 2λ N
xR ′ ( θt s(j) , θt j ) + 2xR ′ ( θt j , θ i ) + 2xR ′ (θ i , θ) + ϕ(x)

+ 2C(t j ) + ζ+1 ζ-1 log 3 εν(λ) λ + 4C 2 λ N 2 2C(t j ) + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ )
.

Let us notice that R ′ ( θt s(j) , θt j ) ≤ B(t s(j) , t j ) and remember that, by definition, B(t j , t s(j) ) ≥ 0. This shows that R ′ ( θt s(j) , θt j ) ≤ B(t j , t s(j) ) + B(t s(j) , t j ) .

Once again, let us apply Lemma 5.5 to upper bound C(t j ), Lemma 5.3 to upper bound R ′ ( θt j , θ i ) and Lemma 5.1 to upper bound ϕ(x). Let us put moreover λ = γ = γ ′ = 2β = 2β ′ . Inequality 5.17 becomes:

1 -4βx N B(t j , t s(j) ) + B(t s(j) , t j ) ≤ 4β N 2xR ′ (θ i , θ) + 1 -1 κ (κcx)

-1 κ-1 + [K(1 + 32C 2 ) + 8C ′ ]δ N (i, q, ε, κ) + 1 2β + ζ + 1 ζ -1 log 3 εν(λ) 2β + 48C 2 N log 3 εµ(i)µ(i ′ )
and therefore B(t j , t s(j) ) + B(t s(j) , t j ) ≤ Eδ N (i, q, ε, κ).

There remains to upper bound B( t, t ŝ) + B(t ŝ, t) . We will use to that purpose the fact that C( t) ≤ C(t j ):

B( t, t ŝ) + B(t ŝ, t) ≤ 2λ N xR ′ ( θt , θt j ) + xR ′ ( θt s(j) , θt j ) + 2xR ′ ( θt j , θ i ) + 2xR ′ (θ i , θ) + ϕ(x)

+ 2C(t j ) + ζ+1 ζ-1 log 3 εν(λ) λ + 4C 2 λ N 2 2C(t j ) + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ )
.

Note that we have already proved that R ′ ( θt s(j) , θt j ) ≤ B(t j , t s(j) ) + B(t s(j) , t j ) ≤ Eδ N (i, q, ε, κ).

Plugging all these results into Inequality (5.16), we obtain, 1 -2λx N R ′ θt , θt j ≤ Eδ N (i, q, ε, κ) + 2λ N xEδ N (i, q, ε, κ) + 2xR ′ ( θt j , θ i ) + 2xR ′ (θ i , θ) + ϕ(x)

+ 2C(t j ) + ζ+1 ζ-1 log 3 εν(λ) λ + 4C 2 λ N 2 2C(t j ) + 1 + β γ -β + β ′ γ ′ -β ′ log 3 εµ(i)µ(i ′ ) .
As usual, let us apply Lemma 5.5 to upper bound C(t j ), Lemma 5.3 to upper bound R ′ ( θt j , θ i ) and Lemma 5.1 to upper bound ϕ(x). Let us put λ = γ = γ ′ = 2β = 2β ′ , to obtain

1 - 4βx N R ′ θt , θt j ≤ 4β N 2xR ′ (θ i , θ) + 1 - 1 κ (κcx) -1 κ-1 + [K(1 + 32C 2 ) + 8C ′ + 3E]δ N (i, q, ε, κ) + 1 2β + ζ + 1 ζ -1 log 3 εν(λ) 2β + 48C 2 N log 3 εµ(i)µ(i ′ ) ,
and therefore R ′ θt , θt j ≤ E ′ δ N (i, q, ε, κ).

This ends the proof.

Definition 1 . 1 .

 11 Let us putP = P 1 ⊗ ... ⊗ P N ,

  a finite or countable set I and by θ ∈ Θ. For every i ∈ I we choose: θi ∈ arg min θ∈Θ P ψ i θ . Example 1.4 (Empirical risk minimization and model selection). If we take I = {0} we can choose ψ 0 θ (z) = l θ (z) and we obtain P ψ 0 θ = r(θ) and so θ0 = arg min θ∈Θ r(θ)

2. 2 .

 2 Empirical bound of the localized complexity. Definition 2.1. Let us put, for any (a, λ)

2. 5 .

 5 Introduction of the complexity function. It is convenient to remark that we can dissociate the optimization with respect to the different parameters in Theorem 2.5 thanks to the introduction of an appropriate complexity function. The model selection algorithm we propose in the next subsection takes advantage of this decomposition.

Theorem 3 . 2 .

 32 Let us put, for any i ∈ I,

Appendix : bounding the effect of truncation

We will show here how to upper bound R(θ)-R(θ ′ )-R λ (θ, θ ′ ) by some quantity ∆ λ (θ, θ ′ ) depending on an additional hypothesis on the data distribution.

Lemma 5.6. Let us assume that we are in the i.i.d. case, where P 1 = ... = P N and that for some constants (b,

Proof. From definitions,

where (x) + = x ∧ 0. So we can write

leading to the result stated in the lemma.