J.-F Bercher

Source Coding with Escort Distributions and Rényi Entropy Bounds

Keywords: Source coding, Rényi-Tsallis entropies, Escort distributions PACS: 02.50.-r, 05.90.+m, 89.70.+c

We discuss the interest of escort distributions and Rényi entropy in the context of source coding. We first recall a source coding theorem by Campbell relating a generalized measure of length to the Rényi-Tsallis entropy. We show that the associated optimal codes can be obtained using considerations on escort-distributions. We propose a new family of measure of length involving escort-distributions and we show that these generalized lengths are also bounded below by the Rényi entropy. Furthermore, we obtain that the standard Shannon codes lengths are optimum for the new generalized lengths measures, whatever the entropic index. Finally, we show that there exists in this setting an interplay between standard and escort distributions.

Introduction

Rényi and Tsallis entropies extend the standard Shannon-Boltzmann entropy, enabling to build generalized thermostatistics, that include the standard one as a special case. This has received a very high attention and there is a wide variety of applications where experiments, numerical results and analytical derivations fairly agree with these new formalisms [START_REF] Tsallis | Introduction to Nonextensive Statistical Mechanics[END_REF]. These results have also raised interest in the general study of information measures and their applications. The definition of Tsallis entropy was originally inspired by multifractals whereas the Rényi entropy is an essential ingredient [START_REF] Harte | Multifractals: Theory and Applications[END_REF][START_REF] Jizba | [END_REF], e.g. via the definition of the Rényi dimension. For a distribution p of a discrete variable with N possible microstates, the Rényi entropy of order α, with α ≥ 0, is defined by

H α (p) = 1 1 -α log N i=1 p α i . (1)
By L'Hospital rule, for α = 1, we recover the Shannon entropy

H 1 (p) = - N i=1 p i log p i . (2)
Email address: jf.bercher@esiee.fr (J.-F. Bercher) The base of the logarithm is arbitrary. In the following, we will denote log D the base D logarithm. The Tsallis entropy is a simple transformation of the Rényi entropy, but is nonextensive. Often associated to these entropies, and central in the formulation of nonextensive statistical mechanics is the concept of escort distributions: if {p i } is the original distribution, then its escort distribution P is defined by

P i = p q i N i=1 p q i . (3)
The parameter q behaves as a microscope for exploring different regions of the measure p [4]: for q > 1, the more singular regions are amplified, while for q < 1 the less singular regions are accentuated. The escort distributions have been introduced as a tool in the context of multifractals. Interesting connections with the standard thermodynamic are in [4,[START_REF] Beck | Thermodynamics of Chaotic Systems[END_REF]. Discussion of their geometric properties can also be found in [START_REF] Abe | [END_REF]. It is also interesting to note that the escort distributions can be found as the result of a maximum entropy problem with a constraint on the expected value of a logarithmic quantity, see [2, p. 53] in the context of multifractals, or [7] for a different view. We shall also point out that the 'deformed' information measure like the Rényi entropy (1) and the escort distribution (3) are originally two distincts concepts, as indicated here by the different notations α and q. There is a lengthy discussion on this point in [8].

In the information theory of communication, the entropy is the measure of the quantity of information in a message, and a primary aim is to represent the possible messages in an efficient manner, that is to find a compact representation of the information according to a measure of 'compactness'. This is the role of source coding. In this note, we discuss the interest of escort distributions and alternative entropies in this context. This suggests possible connections between coding theory and the measure of complexity in nonextensive statistical mechanics. Related works are the study of generalized channel capacities [9], the notion of nonadditive information content [10], the presentation of a generalized rate distorsion theory [11]. The first section is devoted to a very short presentation of the source coding context, and to the presentation of the fundamental Shannon source coding theorem. In section 3, we describe a source coding theorem relating a new measure of length and the Rényi entropy. In the next section, we show that it is possible to obtain the very same optimum codes, as well as a practical procedure, using a reasoning based on the nonextensive generalized mean as the measure of length. In section 5, we introduce another measure of length, involving escort distribution, and obtain general inequalities for this measure, where the lower bound, once again is a Rényi entropy. We show that the corresponding optimum codes are the standard Shannon codes. Finally, in section 6 we discuss the connections between these different results.

Source coding

In source coding, one considers a set of symbols X = {x 1 , x 2 , . . . x N }, and a source that produces symbols x i from X with probabilities p i where N i=1 p i = 1. The aim of source coding is to encode the source using an alphabet of size D, that is to map each symbol x i to a codeword c i of length l i expressed using the D letters of the alphabet. It is known that if the set of lengths l i satisfies the Kraft-Mac Millan inequality

N i=1 D -l i ≤ 1, (4)
then there exists a uniquely decodable code with these lengths, which means that any sequence c i1 c i2 . . . c in can be decoded unambiguously into a sequence of symbols x i1 x i2 . . . x in . Furthermore, any uniquely de-2 codable code satisfies the Kraft-Mac Millan inequality (4). The Shannon source coding theorem (noiseless coding theorem) indicates that the expected length of the code L is bounded below by the entropy of the source, H 1 (p), and that the best uniquely decodable code satisfies

H 1 (p) ≤ L = i p i l i < H 1 (p) + 1, (5)
where the logarithm in the definition of the Shannon entropy is taken in base D. This result indicates that the Shannon entropy H 1 (p) is the fundamental limit on the minimum average length for any code constructed for the source. The lengths of the individual codewords, also called 'bit-numbers' [5, p. 46], are given by

l i = -log D p i (6)
where log D denotes the logarithm in base D. Obviously these code lengths enable to attain the entropy in the left of the inequality [START_REF] Beck | Thermodynamics of Chaotic Systems[END_REF]. The characteristic of these optimum codes is that they assign the shorter to the most likely symbols and the longer codewords to unlikely symbols. The uniquely decodable code can be chosen to have the prefix property, i.e. the property that no codeword is a prefix of another codeword.

Source coding with Campbell measure of length

It is well-known that Huffman coding yields a prefix code which minimizes the expected length and approaches the optimum limit l i = -log D p i . What is much less well known is that some other forms of lengths have been considered [12], the first and definitely fundamental contribution being the paper of Campbell [13]. Since the codewords lengths obey to the relation ( 6), low probabilities yield very long words. But the cost of using a word is not necessarily a linear function of its length, and it is possible that adding a letter to a long word cost much more than adding a letter to a shorter word. This led Campbell to the proposal of a new average length measure, featuring an exponential account of the elementary lengths of the codewords. This length, which is called a β-exponential mean or Campbell length, is a Kolmogorov-Nagumo generalized mean associated to an exponential function. It is defined by

C β = 1 β log D N i=1 p i D βl i , (7)
where β is a strictly positive parameter. The remarkable result [13] is that just as Shannon entropy is the lower bound on the average codeword length of an uniquely decodable code, the Rényi entropy of order q, with q = 1/(β + 1), is the lower bound on the exponentially weighted codeword length (7):

C β ≥ H q (p). (8)
A simple proof of this result will be given below. It is easy to check that the equality is achieved by choosing the l i such that

D -l i = P i = p q i N j=1 p q j , (9)
that is

l i = -q log D p i + (1 -q)H q (p). (10)
Obviously, the individual lengths obtained this way can be made smaller than the Shannon lengths l i = -log D p i , especially for small p i , by selecting a sufficiently small value of q. Hence, the procedure effectively penalizes the longer codewords and yields a code different from Shannon's code, with possibly shorter codewords associated to the low probabilities. 3

Source coding with nonextensive generalized mean

In the standard measure of average length L = i p i l i , we have a linear combination of the individual lengths, with the probabilities p i as weights. In order to increase the impact of the longer lengths with low probabilities, the Campbell's length uses an exponential of the length. A different approach to the problem can be to modify the weigths in the linear combination, so as to raise the importance of the terms with low probabilities. A simple way to achieve this is to deform, flatten, the original probability distribution and use the new distribution as weights rather than the p i . Of course, a very good candidate is the escort distribution, which leads us to the 'average length measure'

M q = N i=1 p q i j p q j l i = N i=1 P i l i , (11)
which is nothing but the generalized expected value of nonextensive statistical mechanics according to the third mean values' choice of Tsallis, Mendes and Plastino [14]. For the virtual source with distribution P , the standard expected length is M q , and the classical Shannon noiseless source coding theorem immediately applies, leading to

M q ≥ H 1 (P ), (12)
with equality if

l i = -log D P i (13)
which is exactly the lengths in (10) obtained via Campbell's measure. This easy result has also be mentioned in [10]. 1The simple relation l i = -log D P i for the minimization of M q subject to the Kraft-Mac Millan inequality has a direct practical implication. Indeed, it suffices to feed a standard coding algorithm, namely a Huffman coder, with the escort distribution P instead of the natural distribution p, to obtain as a result a code tailored for the Campbell's length measure C β or equivalently for the length measure M q . A simple example, with D = 2, is reported in Table 1: we used a standard Huffman algorithm with the original distribution and the escort distributions with q = 0.7 and q = 0.4. It is worth noting that some specific algorithms have been developed for Campbell's length [15,16,12]. The remark above gives an easy alternative. An important point is that these new codes have direct applications: they are optimum for minimizing the probability of buffer overflows [15], or, with q > 1 for maximizing the chance of the reception of a message in a single snapshot [17]. In the second case, the choice q > 1 increases the main features of the probability distribution, then leading to select more short codewords for the highest probabilities; this maximizes the chance of a complete reception of a message in a single transmission of limited size.

p i q = 1 q = 0.7 q = 0.4 0.

Another measure of length with Rényi bounds

Given these results, it is now interesting to introduce a new measure of average length, similar to Campbell's length but mixing both a an exponential weight of individual lengths l i and an escort distribution. This measure is defined by

L q = 1 q -1 log D N i=1 p q i j p q j D (q-1)l i . ( 14
)
Some specific values are as follows. It is easy to see that L 0 = -log D i D -l i + log D N . When q → +∞, the maximum of the probabilities, say p k = arg max i p i emerges, and L ∞ = l k , where l k is the length associated to p k , the maximum among the probabilities p i . By L'Hospital's rule, we also obtain that L 1 = L = i p i l i . As for Campbell's measure, it is possible to show that L q is bounded below by the Rényi entropy.

As in Campbell's original proof, let us consider the Hölder inequality

N i=1 |x i | p 1/p N i=1 |y i | p ′ 1/p ′ ≤ N i=1 |x i y i | for all sequences (x 1 , . . . , x N ), (y 1 , . . . .y N ) ∈ R N (15)
for p or p ′ in (0, 1) and such that 1/p + 1/p ′ = 1. Note that the reverse inequality is true when p and p ′ are in [1, +∞). Suppose that the l i are the lengths of the codewords in a uniquely decodable code, which means that they satisfy the Kraft inequality (4). If we let now

x i = p α i D -l i and y i = p -α i , it comes N i=1 p αp i D -pl i 1/p N i=1 p -αp ′ i 1/p ′ ≤ N i=1 D -l i ≤ 1, (16)
where the last inequality in the right is the Kraft inequality.

If we let αp = 1, then α = -1/β, and -αp ′ = α/(α -1) = 1/(β + 1). Then, ( 16) reduces to

N i=1 p i D βl i -1/β N i=1 p 1/(β+1) i (β+1)/β ≤ 1. (17)
Taking the base D logarithm, we obtain the Campbell theorem C β ≥ H q (p), with q = 1/(β + 1).

If we now take αp = q and choose -αp ′ = 1, we obtain

N i=1 p q i D -pl i 1/p ≤ 1, (18)
where we used of course the fact that the probabilities sum to one. The condition 1/p + 1/p ′ = 1 easily gives p = 1 -q. Dividing the two sides by ( i p q i ) 1/(1-q) , taking the logarithm and changing the sign of the inequality, we finally obtain

1 q -1 log D N i=1 p q i j p q j D (q-1)l i ≥ 1 1 -q log D N i=1 p q i ( 19
)
which gives the simple inequality

L q ≥ H q . ( 20
)
Hence we obtain that the new length measure of order q is lower bounded by the Rényi entropy of the same order. Note that this result include Shannon result in the special case q = 1. Interestingly, it is easy to check that we have equality in (20) for l i = -log D p i , which is nothing but the optimal lengths in the Shannon coding theorem. Hence, it is remarkable that the whole series of inequalities (20) become equalities for the choice l i = -log D p i which appears as a kind of universal value in this context. This result can draw attention to alternative coding algorithms, based on the minimization of L q , or alternative characterizations of the optimal code. For instance, the inequality (20) shows, as a direct consequence, that the Shannon code with l i = -log D p i minimizes the length of the codeword associated to the maximum probability. Indeed, when q → +∞, L ∞ → l k the length of the codeword of maximum probability, and L ∞ is minimum when l k has its minimum value

H ∞ = -log D p k .
Since the Rényi and Tsallis entropy are related by a simple monotone transformation, inequalities similar to ( 8) and (20) exist with Tsallis entropy bounds.

Connections between the different length measures

It is finally useful to exhibit an interplay between the two length measures, their minimizers, and the standard and escort distributions. The Campbell measure in (7) involves the distribution p, an exponential weight with index β. The optimum lengths that achieve the equality in the inequality (8) are the bitnumbers associated to the escort distribution l i = -log D P i . On the other hand, the measure (14) involves the escort distribution P instead of p, has an index q and the optimum lengths that achieve the equality in the extended source coding inequality (20) are the bit-numbers l i = -log D p i associated to the original distribution. We know that the transformation q ↔ 1/q [14, p. 543] links the original and escort distribution, that is the distribution p is the escort distribution with index 1/q of the distribution P . This remark enables to find an equivalence between thermostatistics formalisms base on linear and generalized averages [START_REF] Raggio | On equivalence of thermostatistical formalisms[END_REF][START_REF] Naudts | [END_REF]. Here, when we substitute q by 1/q in (14), and therefore P by p, we end with Campbell length (7) where q = 1/(β + 1). Concerning the entropy bound in ( 8) and (20), we shall also observe that H 1 q (P ) = H q (p), so that we have finally equivalence between the two inequalities (8) and (20). This is a new illustration of the duality between standard and escort distributions. As a last remark, let us mention that if we apply Jensen inequality to the exponential function in the sum defining L q (14), we then obtain M q ≥ L q , where M q is the generalized mean, taken with respect to the escort distribution, and we have

M q ≥ L q ≥ H q . (21)
The equality in M q ≥ L q means that the transformation in Jensen inequality is a straight line, which means q = 1. In such case, we still obtain M 1 ≥ H 1 (p), which is nothing but the standard Shannon coding theorem.

Conclusions

In this Letter, we have pointed out the relevance of Rényi entropy and escort distributions in the context of source coding. This suggests possible connections between coding theory and the main tools of nonextensive statistical mechanics. We have first outlined an overlooked result by Campbell that gave the first operational characterization of Rényi entropy, as the lower bound in the minimization of a deformed measure of length. We then considered some alternative definitions of measure of length. We showed that Campbell's optimum codes can also be obtained using another natural measure of length based on escort distributions. Interestingly, this provides an easy practical procedure for the computation of these codes. Next, we introduced a third measure of length involving both an exponentiation, as in Campbell's case, and escort distributions. We showed that this length is also bounded below by a Rényi entropy. Finally, we showed that the duality between standard and escort distributions connects some of these results.

Further work should consider the extension of these results, namely the new lengths definitions, in the context of channel coding. With these new lengths, we also intend to investigate the problem of model selection, as in Rissanen MDL (Minimum Description Length) procedures.

Table 1 :

 1 Examples of codes in the binary case, for different values of q.

	48 0	0	00
	0.3	10	10	01
	0.1	110	1100	100
	0.05 1110	1101	101
	0.05 11110	1110	110
	0.01 111110 11110	1110
	0.01 111111 11111	1111

In this interesting paper, another inequality is given for the generalized mean: Mq ≥ Sq(p), where Sq is the normalized version of Tsallis entropy. In fact, this is only true under the condition i exp q (-li) ≤ 1, with the equality occuring for li = -lnq(pi), where exp q and lnq denote the standard nonextensive q-deformed exponential and logarithm. When these lengths li also fullfill the Kraft-Mac Millan inequality we have Mq = Sq(p) > H1(P ).


Jean-Yves Audibert
email: audibert@imagine.enpc.fr

Olivier Catoni
email: olivier.catoni@ens.fr

Linear regression through PAC-Bayesian truncation

Keywords: 62J05, 62J07 Linear regression, Generalization error, Shrinkage, PAC-Bayesian theorems, Risk bounds, Robust statistics, Resistant estimators, Gibbs posterior distributions, Randomized estimators, Statistical learning theory

published or not. The documents may come

Linear regression through PAC-Bayesian truncation

INTRODUCTION

OUR STATISTICAL TASK. Let Z 1 = (X 1 , Y 1 ), . . . , Z n = (X n , Y n ) be n ≥ 2 pairs of input-output and assume that each pair has been independently drawn from the same unknown distribution P . Let X denote the input space and let the output space be the set of real numbers R, so that P is a probability distribution on the product space Z X × R. The target of learning algorithms is to predict the output Y associated with an input X for pairs Z = (X, Y ) drawn from the distribution P . The quality of a (prediction) function f : X → R is measured by the least squares risk:

R(f ) E Z∼P [Y -f (X)] 2 .
Through the paper, we assume that the output and all the prediction functions we consider are square integrable. Let Θ be a closed convex set of R d , and ϕ 1 , . . . , ϕ d be d prediction functions. Consider the regression model

F = f θ = d j=1 θ j ϕ j ; (θ 1 , . . . , θ d ) ∈ Θ .
The best function f * in F is defined by

f * = d j=1 θ * j ϕ j ∈ argmin f ∈F R(f ). (0.1)
Such a function always exists but is not necessarily unique. Besides it is unknown since the probability generating the data is unknown. We will study the problem of predicting (at least) as well as function f * . In other words, we want to deduce from the observations Z 1 , . . . , Z n a function f having with high probability a risk bounded by the minimal risk R(f * ) on F plus a small remainder term, which is typically of order d/n. Except in particular settings (e.g., when Θ is a probability simplex 5 and d ≥ √ n), it is known that the convergence rate d/n cannot be improved in a minimax sense (see [START_REF] Tsybakov | Optimal rates of aggregation[END_REF], and [START_REF] Yang | Aggregating regression procedures for a better performance[END_REF] for related results).

More formally, the target of the paper is to develop estimators f for which the excess risk is controlled in deviations, i.e., such that for an appropriate constant κ > 0, for any ε > 0, with probability at least 1ε,

R( f ) -R(f * ) ≤ κ d + log(ε -1 ) n . (0.2)
Note that by integrating the deviations (using the identity EW = +∞ 0 P(W > t)dt which holds true for any nonnegative random variable W ), Inequality (0.2) implies

ER( f ) -R(f * ) ≤ κ d + 1 n . (0.3)
In this work, we do not assume that the function

f (reg) : x → E[Y |X = x],
which minimizes the risk R among all possible measurable functions, belongs to the model F. So we might have f * = f (reg) and in this case, bounds of the form

ER( f ) -R(f (reg) ) ≤ C[R(f * ) -R(f (reg) )] + κ d n , (0.4)
with a constant C larger than 1 do not even ensure that ER( f ) tends to R(f * ) when n goes to infinity. This kind of bounds with C > 1 have been developed to analyze nonparametric estimators using linear approximation spaces, in which case the dimension d is a function of n chosen so that the bias term R(f * ) -R(f (reg) ) has the order d/n of the estimation term (see [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF] and references within). Here we intend to assess the generalization ability of the estimator even when the model is misspecified (namely when R(f * ) > R(f (reg) )). Moreover we do not assume either that Yf (reg) (X) and X are independent. Notation. When Θ = R d , the function f * and the space F will be written f * lin and F lin to emphasize that F is the whole linear space spanned by ϕ 1 , . . . , ϕ d :

F lin = span{ϕ 1 , . . . , ϕ d } and f * lin ∈ argmin f ∈F lin R(f ).
The Euclidean norm will simply be written as • , and •, • will be its associated inner product. We will consider the vector valued function ϕ : X → R d defined by ϕ(X) = ϕ k (X) d k=1 , so that for any θ ∈ Θ, we have f θ (X) = θ, ϕ(X) .

The Gram matrix is the d × d-matrix Q = E ϕ(X)ϕ(X) T , and its smallest and largest eigenvalues will respectively be written as q min and q max . The empirical risk of a function f is

r(f ) = 1 n n i=1 f (X i ) -Y i 2
and for λ ≥ 0, the ridge regression estimator on F is defined by f (ridge) = f θ(ridge) with θ(ridge) ∈ arg min

θ∈Θ r(f θ ) + λ θ 2 ,
where λ is some nonnegative real parameter. In the case when λ = 0, the ridge regression f (ridge) is nothing but the empirical risk minimizer f (erm) . In the same way, we introduce the optimal ridge function optimizing the expected ridge risk:

f = f θ with θ ∈ arg min θ∈Θ R(f θ ) + λ θ 2 . (0.5)
Finally, let Q λ = Q + λI be the ridge regularization of Q, where I is the identity matrix.

OUTLINE AND CONTRIBUTIONS. The paper is organized as follows. Section 1 is a survey on risk bounds in linear least squares regression. Theorems 1.3 and 1.5 are the results which come closer to our target. Section 2 presents our main result on linear least squares regression. Section 3 gives risk bounds for general loss functions from which the results of Section 2 are derived. Appendix A shows that (0.2) cannot hold under the only assumption that the variance of Y is finite, even in the favorable situation where f (reg) belongs to F.

The main contribution of this paper is to show that an appropriate shrinkage estimator involving truncated differences of losses has an excess risk of order d/n (without a logarithmic factor as it appears in numerous works), concentrating exponentially, which does not degrade when the matrix Q is ill-conditioned or when some ratio of L 2 and L ∞ norms behaves badly or when the output distribution is heavy-tailed. Our results tend to say that shrinkage and truncation lead to more robust algorithms when we consider robustness with respect to the distribution of the noise, and not to a potential contamination of the training data by input-output pairs not generated by P .

VARIANTS OF KNOWN RESULTS

1.1. ORDINARY LEAST SQUARES AND EMPIRICAL RISK MINIMIZATION. The ordinary least squares estimator is the most standard method in linear least squares regression. It minimizes the empirical risk

r(f ) = 1 n n i=1 [Y i -f (X i )] 2 ,
among functions in F lin and produces

f (ols) = d j=1 θ(ols) j ϕ j , with θ(ols) = [ θ(ols) j ] d j=1 a column vector satisfying X T X θ(ols) = X T Y, (1.1)
where Y = [Y j ] n j=1 and X = (ϕ j (X i )) 1≤i≤n,1≤j≤d . It is well-known that • the linear system (1.1) has at least one solution, and in fact, the set of solutions is exactly {X + Y +u; u ∈ ker X}; where X + is the Moore-Penrose pseudoinverse of X and ker X is the kernel of the linear operator X. • X θ(ols) is the (unique) orthogonal projection of the vector Y ∈ R n on the image of the linear map X;

• if sup x∈X Var(Y |X = x) = σ 2 < +∞, we have (see [16, Theorem 11.1]) for any X 1 , . . . , X n in X, E 1 n n i=1 f (ols) (X i ) -f (reg) (X i ) 2 X 1 , . . . , X n -min f ∈F lin 1 n n i=1 f (X i ) -f (reg) (X i ) 2 ≤ σ 2 rank(X) n ≤ σ 2 d n , (1.2)
where we recall that f (reg) :

x → E[Y |X = x] is the optimal regression function, and that when this function belongs to F lin (i.e., f (reg) = f * lin ), the minimum term in (1.2) vanishes;

• from Pythagoras' theorem for the (semi)norm W → √ EW 2 on the space of the square integrable random variables,

R( f (ols) ) -R(f * lin ) = E f (ols) (X) -f (reg) (X) Z 1 , . . . , Z n 2 -E f * lin (X) -f (reg) (X) 2 .
(1.

3)

The analysis of the ordinary least squares often stops at this point in classical statistical textbooks. (Besides, to simplify, the strong assumption f (reg) = f * lin is often made.) This can be misleading since Inequality (1.2) does not imply a d/n upper bound on the risk of f (ols) . Nevertheless the following result holds [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF]Theorem 11.3

]. THEOREM 1.1 If sup x∈X Var(Y |X = x) = σ 2 < +∞ and f (reg) ∞ = sup x∈X |f (reg) (x)| ≤ H
for some H > 0, then the truncated estimator f (ols)

H = ( f (ols) ∧ H) ∨ -H satisfies ER( f (ols) H ) -R(f (reg) ) ≤ 8[R(f * lin ) -R(f (reg) )] + κ (σ 2 ∨ H 2 )d log n n (1.4)
for some numerical constant κ.

Using PAC-Bayesian inequalities, Catoni [10, Proposition 5.9.1] has proved a different type of results on the generalization ability of f (ols) . THEOREM 1.2 Let F ′ ⊂ F lin be such that for some positive constants a, M, M ′ :

• there exists f 0 ∈ F ′ s.t. for any x ∈ X, E exp a Y -f 0 (X) X = x ≤ M; • for any f 1 , f 2 ∈ F ′ , sup x∈X |f 1 (x) -f 2 (x)| ≤ M ′ . Let Q = E ϕ(X)ϕ(X) T and Q = 1 n n i=1 ϕ(X i )ϕ(X i ) T be
respectively the expected and empirical Gram matrices. If det Q = 0, then there exist positive constants C 1 and C 2 (depending only on a, M and M ′ ) such that with probability at least 1ε, as soon as

f ∈ F lin : r(f ) ≤ r( f (ols) ) + C 1 d n ⊂ F ′ , (1.5)
we have

R( f (ols) ) -R(f * lin ) ≤ C 2 d + log(ε -1 ) + log( det Q det Q ) n .
This result can be understood as follows. Let us assume we have some prior knowledge suggesting that f * lin belongs to the interior of a set F ′ ⊂ F lin (e.g., a bound on the coefficients of the expansion of f * lin as a linear combination of ϕ 1 , . . . , ϕ d ). It is likely that (1.5) holds, and it is indeed proved in Catoni [10, section 5.11] that the probability that it does not hold goes to zero exponentially fast with n in the case when F ′ is a Euclidean ball. If it is the case, then we know that the excess risk is of order d/n up to the unpleasant ratio of determinants, which, fortunately, almost surely tends to 1 as n goes to infinity.

By using localized PAC-Bayes inequalities introduced in Catoni [START_REF] Catoni | A PAC-Bayesian approach to adaptive classification[END_REF][START_REF] Catoni | PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF], one can derive from Inequality (6.9) and Lemma 4.1 of Alquier [START_REF] Alquier | PAC-bayesian bounds for randomized empirical risk minimizers[END_REF] the following result. THEOREM 1.3 Let q min be the smallest eigenvalue of the Gram matrix Q = E ϕ(X)ϕ(X) T . Assume that there exist a function f 0 ∈ F lin and positive constants H and C such that

f * lin -f 0 ∞ ≤ H. and |Y | ≤ C almost surely.
Then for an appropriate randomized estimator requiring the knowledge of f 0 , H and C, for any ε > 0 with probability at least 1ε w.r.t. the distribution generating the observations Z 1 , . . . , Z n and the randomized prediction function f , we have

R( f ) -R(f * lin ) ≤ κ(H 2 + C 2 ) d log(3q -1 min ) + log (log n)ε -1 n , (1.6)
for some κ not depending on d and n.

Using the result of [START_REF] Catoni | Statistical Learning Theory and Stochastic Optimization, Lectures on Probability Theory and Statistics, École d'Été[END_REF]Section 5.11], one can prove that Alquier's result still holds for f = f (ols) , but with κ also depending on the determinant of the product matrix Q. The log[log(n)] factor is unimportant and could be removed in the special case quoted here (it comes from a union bound on a grid of possible temperature parameters, whereas the temperature could be set here to a fixed value). The result differs from Theorem 1.2 essentially by the fact that the ratio of the determinants of the empirical and expected product matrices has been replaced by the inverse of the smallest eigenvalue of the quadratic form θ → R( d j=1 θ j ϕ j ) -R(f * lin ). In the case when the expected Gram matrix is known, (e.g., in the case of a fixed design, and also in the slightly different context of transductive inference), this smallest eigenvalue can be set to one by choosing the quadratic form θ → R(f θ ) -R(f * lin ) to define the Euclidean metric on the parameter space.

Localized Rademacher complexities [START_REF] Koltchinskii | Local rademacher complexities and oracle inequalities in risk minimization[END_REF][START_REF] Bartlett | Local rademacher complexities[END_REF] allow to prove the following property of the empirical risk minimizer. THEOREM 1.4 Assume that the input representation ϕ(X), the set of parameters and the output Y are almost surely bounded, i.e., for some positive constants H and C, sup

θ∈Θ θ ≤ 1 ess sup ϕ(X) ≤ H, and |Y | ≤ C a.s.. Let ν 1 ≥ • • • ≥ ν d be the eigenvalues of the Gram matrix Q = E ϕ(X)ϕ(X) T .
The empirical risk minimizer satisfies for any ε > 0, with probability at least 1-ε:

R( f (erm) ) -R(f * ) ≤ κ(H + C) 2 min 0≤h≤d h + n (H+C) 2 i>h ν i + log(ε -1 ) n ≤ κ(H + C) 2 rank(Q) + log(ε -1 ) n ,
where κ is a numerical constant.

PROOF. The result is a modified version of Theorem 6.7 in [START_REF] Bartlett | Local rademacher complexities[END_REF] applied to the linear kernel k(u, v) = u, v /(H + C) 2 . Its proof follows the same lines as in Theorem 6.7 mutatis mutandi: Corollary 5.3 and Lemma 6.5 should be used as intermediate steps instead of Theorem 5.4 and Lemma 6.6, the nonzero eigenvalues of the integral operator induced by the kernel being the nonzero eigenvalues of Q.

When we know that the target function f * lin is inside some L ∞ ball, it is natural to consider the empirical risk minimizer on this ball. This allows to compare Theorem 1.4 to excess risk bounds with respect to f * lin . Finally, from the work of Birgé and Massart [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF], we may derive the following risk bound for the empirical risk minimizer on a L ∞ ball (see Appendix B). THEOREM 1.5 Assume that F has a diameter upper bounded by H for the L ∞norm, i.e., for any f 1 , f 2 in F, sup x∈X |f 1 (x)f 2 (x)| ≤ H and there exists a function f 0 ∈ F satisfying the exponential moment condition:

for any x ∈ X, E exp A -1 Y -f 0 (X) X = x ≤ M, (1.7)
for some positive constants A and M. Let

B = inf φ 1 ,...,φ d sup θ∈R d -{0} d j=1 θ j φ j 2 ∞ θ 2 ∞
where the infimum is taken with respect to all possible orthonormal basis of F for the dot product f 1 , f 2 = Ef 1 (X)f 2 (X) (when the set F admits no basis with exactly d functions, we set B = +∞). Then the empirical risk minimizer satisfies for any ε > 0, with probability at least 1ε:

R( f (erm) ) -R(f * ) ≤ κ(A 2 + H 2 ) d log[2 + ( B/n) ∧ (n/d)] + log(ε -1 ) n ,
where κ is a positive constant depending only on M.

This result comes closer to what we are looking for: it gives exponential deviation inequalities of order at worse d log(n/d)/n. It shows that, even if the Gram matrix Q has a very small eigenvalue, there is an algorithm satisfying a convergence rate of order d log(n/d)/n. With this respect, this result is stronger than Theorem 1.3. However there are cases in which the smallest eigenvalue of Q is of order 1, while B is large (i.e., B ≫ n). In these cases, Theorem 1.3 does not contain the logarithmic factor which appears in Theorem 1.5.

PROJECTION ESTIMATOR.

When the input distribution is known, an alternative to the ordinary least squares estimator is the following projection estimator. One first finds an orthonormal basis of F lin for the dot product f 1 , f 2 = Ef 1 (X)f 2 (X), and then uses the projection estimator on this basis. Specifically, if φ 1 , . . . , φ d form an orthonormal basis of F lin , then the projection estimator on this basis is:

f (proj) = d j=1 θ(proj) j φ j , with θ(proj) = 1 n n i=1 Y i φ j (X i ).
The following excess risk bound of order d/n for this estimator is Theorem 4 in [START_REF] Tsybakov | Optimal rates of aggregation[END_REF] up to minor changes in the assumptions.

f (reg) ∞ = sup x∈X |f (reg) (x)| ≤ H < +∞, then we have ER( f (proj) ) -R(f * lin ) ≤ (σ 2 + H 2 ) d n . (1.8) 1.3. PENALIZED LEAST SQUARES ESTIMATOR.
It is well established that parameters of the ordinary least squares estimator are numerically unstable, and that the phenomenon can be corrected by adding an L 2 penalty ( [START_REF] Levenberg | A method for the solution of certain non-linear problems in least squares[END_REF][START_REF] Riley | Solving systems of linear equations with a positive definite, symmetric but possibly ill-conditioned matrix[END_REF]). This solution has been labeled ridge regression in statistics ( [START_REF] Hoerl | Application of ridge analysis to regression problems[END_REF]), and consists in replacing

f (ols) by f (ridge) = f θ(ridge) with θ(ridge) ∈ argmin θ∈R d r(f θ ) + λ d j=1 θ 2 j ,
where λ is a positive parameter. The typical value of λ should be small to avoid excessive shrinkage of the coefficients, but not too small in order to make the optimization task numerically more stable. Risk bounds for this estimator can be derived from general results concerning penalized least squares on reproducing kernel Hilbert spaces ( [START_REF] Caponnetto | Optimal rates for the regularized leastsquares algorithm[END_REF]), but as it is shown in Appendix C, this ends up with complicated results having the desired d/n rate only under strong assumptions.

Another popular regularizer is the L 1 norm. This procedure is known as Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] and is defined by

θ(lasso) ∈ argmin θ∈R d r(f θ ) + λ d j=1 |θ j | .
As the L 2 penalty, the L 1 penalty shrinks the coefficients. The difference is that for coefficients which tend to be close to zero, the shrinkage makes them equal to zero. This allows to select relevant variables (i.e., find the j's such that θ * j = 0). If we assume that the regression function f (reg) is a linear combination of only d * ≪ d variables/functions ϕ j 's, the typical result is to prove that the risk of the Lasso estimator for λ of order (log d)/n is of order (d * log d)/n. Since this quantity is much smaller than d/n, this makes a huge improvement (provided that the sparsity assumption is true). This kind of results usually requires strong conditions on the eigenvalues of submatrices of Q, essentially assuming that the functions ϕ j are near orthogonal. We do not know to which extent these conditions are required. However, if we do not consider the specific algorithm of Lasso, but the model selection approach developed in [START_REF] Alquier | PAC-bayesian bounds for randomized empirical risk minimizers[END_REF], one can change these conditions into a single condition concerning only the minimal eigenvalue of the submatrix of Q corresponding to relevant variables. In fact, we will see that even this condition can be removed.

CONCLUSION OF THE SURVEY.

Previous results clearly leave room to improvements. The projection estimator requires the unrealistic assumption that the input distribution is known, and the result holds only in expectation. Results using L 1 or L 2 regularizations require strong assumptions, in particular on the eigenvalues of (submatrices of)

Q. Theorem 1.1 provides a (d log n)/n convergence rate only when the R(f * lin ) -R(f (reg)
) is at most of order (d log n)/n. Theorem 1.2 gives a different type of guarantee: the d/n is indeed achieved, but the random ratio of determinants appearing in the bound may raise some eyebrows and forbid an explicit computation of the bound and comparison with other bounds. Theorem 1.3 seems to indicate that the rate of convergence will be degraded when the Gram matrix Q is unknown and ill-conditioned. Theorem 1.4 does not put any assumption on Q to reach the d/n rate, but requires particular boundedness constraints on the output. Finally, Theorem 1.5 comes closer to what we are looking for. Yet there is still an unwanted logarithmic factor, and the result holds only when the output has uniformly bounded conditional exponential moments, which as we will show is not necessary.

Our recent work [START_REF] Audibert | Robust linear least squares regression[END_REF] provides a risk bound for ridge regression showing the benefit on the effective dimension of the shrinkage parameter λ and being of order d/n (without logarithmic factor). The work [START_REF] Audibert | Robust linear least squares regression[END_REF] also proposes a robust estimator for linear least squares, which satisfies a d/n excess risk bound without logarithmic factor, but with constants involving several kurtosis coefficients. As discussed in Section 3.2 of [START_REF] Audibert | Robust linear least squares regression[END_REF], depending on the basis functions and the distribution P , these kurtosis coefficients typically behave either as numerical constants or √ d (but worse non-asymptotic behaviors of these constants can also occur). Finally, several works, and in particular those cited in Section 1.1, have considered the problem of model selection where several linear spaces are simultaneously considered, and the goal is to predict as well as the best function in the union of the linear spaces. Only a few of them considered the case of outputs having only finite conditional moments (and not finite conditional exponential moments). This is the case of [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] in the fixed design setting and [START_REF] Wegkamp | Model selection in nonparametric regression[END_REF] in the random design setting. The excess risk bounds there are typically of order d/n with d the dimension of the "best" linear space, but holds in expectation and essentially when the optimal regression function f (reg) belongs to the union of linear spaces.

A SIMPLE TIGHT RISK BOUND FOR A SOPHISTICATED PAC-BAYES

ALGORITHM

In this section, we provide a sophisticated estimator, having a simple theoretical excess risk bound, with neither a logarithmic factor, nor complex constants involving the conditioning of Q, kurtosis coefficients or some geometric quantity characterizing the relation between L 2 and L ∞ -balls.

We consider that the set Θ is bounded so that we can define the "prior" distribution π as the uniform distribution on F (i.e., the one induced by the Lebesgue distribution on Θ ⊂ R d renormalized to get π(F) = 1). Let λ > 0 and

W i (f, f ′ ) = λ Y i -f (X i ) 2 -Y i -f ′ (X i ) 2 . Introduce Ê(f ) = log π(df ′ ) n i=1 [1 -W i (f, f ′ ) + 1 2 W i (f, f ′ ) 2 ] . (2.1)
We consider the "posterior" distribution π on the set F with density:

dπ dπ (f ) = exp[-Ê(f )] exp[-Ê(f ′ )]π(df ′ ) . (2.2)
To understand intuitively why this distribution concentrates on functions with low risk, one should think that when λ is small enough,

1 -W i (f, f ′ ) + 1 2 W i (f, f ′ ) 2 is close to e -W i (f,f ′ )
, and consequently

Ê(f ) ≈ λ n i=1 [Y i -f (X i )] 2 + log π(df ′ ) exp -λ n i=1 Y i -f ′ (X i ) 2 ,
and

dπ dπ (f ) ≈ exp{-λ n i=1 [Y i -f (X i )] 2 } exp{-λ n i=1 [Y i -f ′ (X i )] 2 }π(df ′ )
.

The following theorem gives a d/n convergence rate for the randomized algorithm which draws the prediction function from F according to the distribution π.

THEOREM 2.1 Assume that F has a diameter upper bounded by H for the L ∞norm: sup

f 1 ,f 2 ∈F,x∈X |f 1 (x) -f 2 (x)| ≤ H (2.3)
and that, for some σ > 0,

sup x∈X E [Y -f * (X)] 2 X = x ≤ σ 2 < +∞. (2.4)
Let f be a prediction function drawn from the distribution π defined in (2.2) and depending on the parameter λ > 0. Then for any 0 < η ′ < 1λ(2σ + H) 2 and ε > 0, with probability (with respect to the distribution P ⊗n π generating the observations Z 1 , . . . , Z n and the randomized prediction function f

) at least 1 -ε, we have R( f ) -R(f * ) ≤ (2σ + H) 2 C 1 d + C 2 log(2ε -1 ) n with C 1 = log( (1+η) 2 η ′ (1-η) ) η(1 -η -η ′ ) and C 2 = 2 η(1 -η -η ′ ) and η = λ(2σ + H) 2 .
In particular for λ = 0.32(2σ + H) -2 and η ′ = 0.18, we get

R( f ) -R(f * ) ≤ (2σ + H) 2 16.6 d + 12.5 log(2ε -1 ) n . Besides if f * ∈ argmin f ∈F lin R(f ), then with probability at least 1 -ε, we have R( f ) -R(f * ) ≤ (2σ + H) 2 8.3 d + 12.5 log(2ε -1 ) n .
PROOF. This is a direct consequence of Theorem 3.5 (page 21), Lemma 3.3 (page 19) and Lemma 3.6 (page 23).

If we know that f * lin belongs to some bounded ball in F lin , then one can define a bounded F as this ball, use the previous theorem and obtain an excess risk bound with respect to f * lin .

REMARK 2.1 Let us discuss this result. On the positive side, we have a d/n convergence rate in expectation and in deviations. It has no extra logarithmic factor. It does not require any particular assumption on the smallest eigenvalue of the covariance matrix. To achieve exponential deviations, a uniformly bounded second moment of the output knowing the input is surprisingly sufficient: we do not require the traditional exponential moment condition on the output. Appendix A (page 34) argues that the uniformly bounded conditional second moment assumption cannot be replaced with just a bounded second moment condition. On the negative side, the estimator is rather complicated. With nowadays computers and numerical methods, it seems impossible to get a good approximation of it even when the dimension d is small. Nevertheless, in presence of a heavytailed noise distribution, it can be a way to move from the empirical risk minimizer (which is the baseline estimator for linear regression) in the right direction (that is in a direction in which one can find an estimator having a smaller risk than the one of the empirical risk minimizer). When the target is to predict as well as the best linear combination f * lin up to a small additive term, the estimator requires the knowledge of a L ∞ -bounded ball in which f * lin lies and an upper bound on

sup x∈X E [Y -f * lin (X)] 2 X = x .
The looser this knowledge is, the bigger the constant in front of d/n is. Note that the possible lack of knowledge of H and σ call for a model selection algorithm, which goes beyond the scope of this work. In practice, a careful application of (cross-)validation ideas would probably be sufficient to select these parameters. REMARK 2.2 The proposed randomized estimator is more complex than the classical Gibbs estimator (that is the one with exponential weights involving the empirical risk). Even if the paper does not prove it, (we believe that) the classical Gibbs estimator cannot be robust to heavy-tailed noise. This belief is motivated by the same arguments as the ones used in [START_REF] Catoni | Challenging the empirical mean and empirical variance: a deviation study[END_REF] to show the absence of robustness of the empirical mean estimator. In absence of heavy-tailed noise, the classical Gibbs estimator satisfies a similar result to Theorem 2.1, given in Theorem 3.2.

Our randomized algorithm consists in drawing the prediction function according to π. As usual, by convexity of the loss function, the risk of the deterministic estimator fdeterm = f π(df ) satisfies R( fdeterm ) ≤ R(f )π(df ), so that, after some computations, one can prove that for any ε > 0, with probability at least

1 -ε: R( fdeterm ) -R(f * lin ) ≤ κ(2σ + H) 2 d + log(ε -1 ) n ,
for some appropriate numerical constant κ > 0.

REMARK 2.3 We consider a "prior" distribution π, which is a uniform distribution on F. In presence of sparsity (when only a small number of the coefficients θ * j in (0.1) are nonzero), alternative prior distributions (of Laplace form) are useful in fixed design regression [START_REF] Dalalyan | Aggregation by exponential weighting, sharp pac-bayesian bounds and sparsity[END_REF][START_REF] Dalalyan | Sparse regression learning by aggregation and Langevin Monte-Carlo[END_REF][START_REF] Alquier | PAC-Bayesian bounds for sparse regression estimation with exponential weights[END_REF] and in the random design scenario [START_REF] Dalalyan | Mirror averaging with sparsity priors[END_REF][START_REF] Alquier | PAC-Bayesian bounds for sparse regression estimation with exponential weights[END_REF]. When the coefficient vector θ * is non-sparse (which is not the focus of these works), the latter papers prove a d log n n risk bound when the noise distribution admits at least sub-exponential tails. REMARK 2.4 Theorem 2.1 expresses boundedness in terms of the L ∞ diameter of the set of functions F. Besides, (2.4) implies that the function

f (reg) : x → E[Y |X = x] satisfies f (reg) (X) -f * (X) ≤ σ
V = 2 sup f ∈F lin :E[f (X) 2 ]=1 E f (X) 2 [Y -f * (X)] 2 + sup f ′ ,f ′′ ∈F E [f ′ (X) -f ′′ (X)] 2 sup f ∈F lin :E[f (X) 2 ]=1 E f (X) 4 2 .
The quantity V is finite when simultaneously, Θ is bounded, and for any j in {1, . . . , d}, the quantities E ϕ 4 j (X) and E ϕ j (X) 2 [Yf * (X)] 2 are finite.

A GENERIC LOCALIZED PAC-BAYES APPROACH

3.1. NOTATION AND SETTING. In this section, we drop the restrictions of the linear least squares setting considered so far in order to focus on the ideas underlying the estimator and the results presented in Section 2. To do this, we consider that the loss incurred by predicting y ′ while the correct output is y is l(y, y ′ ) (and is not necessarily equal to (yy ′ ) 2 ). The quality of a (prediction) function f : X → R is measured by its risk

R(f ) = E l Y, f (X) .
We still consider the problem of predicting (at least) as well as the best function in a given set of functions F (but F is not necessarily a subset of a finite dimensional linear space). Let f * still denote a function minimizing the risk among functions in F: f * ∈ argmin f ∈F R(f ). For simplicity, we assume that it exists. The excess risk is defined as

R(f ) = R(f ) -R(f * ).
Let ℓ : Z×F ×F → R be a function such that ℓ(Z, f, f ′ ) represents 6 how worse f predicts than f ′ on the data Z. Let us introduce the real-valued random processes

L : (f, f ′ ) → ℓ(Z, f, f ′ ) and L i : (f, f ′ ) → ℓ(Z i , f, f ′ )
, where Z, Z 1 , . . . , Z n denote i.i.d. random variables with distribution P .

Let π and π * be two (prior) probability distributions on F. We assume the following integrability condition.

Condition I. For any f ∈ F, we have

E exp[L(f, f ′ )] n π * (df ′ ) < +∞, (3.1)
and π(df

) E exp[L(f, f ′ )] n π * (df ′ ) < +∞. (3.2)
We consider the real-valued processes

L(f, f ′ ) = n i=1 L i (f, f ′ ), (3.3)
Ê(f ) = log exp L(f, f ′ ) π * (df ′ ), (3.4)
L ♭ (f, f ′ ) = -n log E exp -L(f, f ′ ) , (3.5)
L ♯ (f, f ′ ) = n log E exp L(f, f ′ ) , (3.6)
and

E ♯ (f ) = log exp L ♯ (f, f ′ ) π * (df ′ ) . (3.7)
Essentially, the quantities L(f, f ′ ), L ♭ (f, f ′ ) and L ♯ (f, f ′ ) represent how worse is the prediction from f than from f ′ with respect to the training data or in expectation. By Jensen's inequality, we have

L ♭ ≤ nE(L) = E( L) ≤ L ♯ . (3.8)
The quantities Ê(f ) and E ♯ (f ) should be understood as some kind of (empirical or expected) excess risk of the prediction function f with respect to an implicit reference induced by the integral over F.

For a distribution ρ on F absolutely continuous w.r.t. π, let dρ dπ denote the density of ρ w.r.t. π. For any real-valued (measurable) function h defined on F such that exp[h(f )]π(df ) < +∞, we define the distribution π h on F by its density:

dπ h dπ (f ) = exp[h(f )] exp[h(f ′ )]π(df ′ ) . (3.9)
We will use the posterior distribution:

dπ dπ (f ) = dπ - Ê dπ (f ) = exp[-Ê(f )] exp[-Ê(f ′ )]π(df ′ ) . (3.10)
Finally, for any β ≥ 0, we will use the following measures of the size (or complexity) of F around the target function:

I * (β) = -log exp -β R(f ) π * (df )
and

I(β) = -log exp -β R(f ) π(df ) .
L ♭ ( f , f ) + γ * R(f ) π * -γ * R(df ) -γ R f ≤ I * (γ * ) -I(γ) -log exp -E ♯ (f ) π(df ) + log dρ dπ f + 2 log 2ε -1 . (3.11)
PROOF. See Section 4.2 (page 26). Some extra work will be needed to prove that Inequality (3.11) provides an upper bound on the excess risk R( f ) of the estimator f . As we will see in the next sections, despite the -γ R( f ) term and provided that γ is sufficiently small, the left-hand side will be essentially lower bounded by λn R( f ), while, by choosing ρ = π, the estimator does not appear in the right-hand side.

APPLICATION UNDER AN EXPONENTIAL MOMENT CONDITION.

The estimator proposed in Section 2 and Theorem 3.1 seems rather unnatural (or at least complicated) at first sight. The goal of this section is twofold. First it shows that under exponential moment conditions (i.e., stronger assumptions than the ones in Theorem 2.1 when the linear least square setting is considered), one can have a much simpler estimator than the one consisting in drawing a function according to the distribution (2.2) with Ê given by (2.1) and yet still obtain a d/n convergence rate. Secondly it illustrates Theorem 3.1 in a different and simpler way than the one we will use to prove Theorem 2.1.

In this section, we consider the following variance and complexity assumptions. Condition V1. There exist λ > 0 and 0 < η < 1 such that for any function

f ∈ F, we have E exp λ l Y, f (X) < +∞, log E exp λ l Y, f (X) -l Y, f * (X) ≤ λ(1 + η)[R(f ) -R(f * )],
and

log E exp -λ l Y, f (X) -l Y, f * (X) ≤ -λ(1 -η)[R(f ) -R(f * )].
Condition C. There exist a probability distribution π, and constants D > 0 and G > 0 such that for any 0 < α < β,

log exp{-α[R(f ) -R(f * )]}π(df ) exp{-β[R(f ) -R(f * )]}π(df ) ≤ D log Gβ α .
THEOREM 3.2 Assume that V1 and C are satisfied. Let π(Gibbs) be the probability distribution on F defined by its density

dπ (Gibbs) dπ (f ) = exp{-λ n i=1 l[Y i , f (X i )]} exp{-λ n i=1 l[Y i , f ′ (X i )]}π(df ′ )
, where λ > 0 and the distribution π are those appearing respectively in V1 and C. Let f ∈ F be a function drawn according to this Gibbs distribution. Then for any η ′ such that 0 < η ′ < 1η (where η is the constant appearing in V1) and any ε > 0, with probability at least 1ε, we have

R( f ) -R(f * ) ≤ C ′ 1 D + C ′ 2 log(2ε -1 ) n with C ′ 1 = log G(1 + η) η ′ λ(1 -η -η ′ ) and C ′ 2 = 2 λ(1 -η -η ′ ) . PROOF. We consider ℓ (X, Y ), f, f ′ = λ l Y, f (X) -l Y, f ′ (X)
, where λ is the constant appearing in the variance assumption. Let us take γ * = 0 and let π * be the Dirac distribution at f * : π * ({f * }) = 1. Then Condition V1 implies Condition I (page 16) and we can apply Theorem 3.1. We have

L(f, f ′ ) = λ l Y, f (X) -l Y, f ′ (X) , Ê(f ) = λ n i=1 l Y i , f (X i ) -λ n i=1 l Y i , f * (X i ) , π = π(Gibbs) , L ♭ (f ) = -n log E exp -L(f, f * ) , E ♯ (f ) = n log E exp L(f, f * )
and Assumption V1 leads to:

log E exp L(f, f * ) ≤ λ(1 + η)[R(f ) -R(f * )] and log E exp -L(f, f * ) ≤ -λ(1 -η)[R(f ) -R(f * )].
Thus choosing ρ = π, (3.11) gives

[λn(1 -η) -γ] R( f ) ≤ -I(γ) + I λn(1 + η) + 2 log(2ε -1 ).
Accordingly by the complexity assumption, for γ ≤ λn(1 + η), we get

[λn(1 -η) -γ] R( f ) ≤ D log Gλn(1 + η) γ + 2 log(2ε -1 ),
which implies the announced result by reparameterization (taking γ = λnη ′ ). Let us conclude this section by mentioning settings in which assumptions V1 and C are satisfied. LEMMA 3.3 Let Θ be a bounded convex set of R d , and ϕ 1 , . . . , ϕ d be d square integrable prediction functions. Assume that

F = f θ = d j=1 θ j ϕ j ; (θ 1 , . . . , θ d ) ∈ Θ ,
π is the uniform distribution on F (i.e., the one coming from the uniform distribution on Θ), and that there exist 0 < b 1 ≤ b 2 such that for any y ∈ R, the function ly : y ′ → l(y, y ′ ) admits almost everywhere a second derivative such that, (y, y ′ ) → l′′ y (y ′ ) is measurable, for any y, y LEMMA 3.4 Assume that the loss function l satisfies the conditions stated in Lemma 3.3. Assume moreover that there exist A > 0 and M > 0 such that for any x ∈ X,

′ ∈ R, b 1 ≤ l′′ y (y ′ ) ≤ b 2 ,
E exp A -1 l′ Y f * (X) X = x ≤ M.
Assume that F is convex and has a diameter upper bounded by H for the L ∞norm: sup

f 1 ,f 2 ∈F,x∈X |f 1 (x) -f 2 (x)| ≤ H.
In this case Condition V1 holds for any (λ, η) such that

η ≥ λA 2 2b 1 exp M 2 exp Hb 2 /A .
and 0 < λ ≤ (2AH) -1 is small enough to ensure η < 1.

PROOF. See Section 4.4 (page 31).

APPLICATION WITHOUT EXPONENTIAL MOMENT CONDITION.

When we do not have finite exponential moments as assumed by Condition V1 (page 18), e.g., when

E exp λ l[Y, f (X)] -l[Y, f * (X)]
= +∞ for any λ > 0 and some function f in F, we cannot apply Theorem 3.1 with ℓ (X, Y ), f, f ′ = λ l Y, f (X) -l Y, f ′ (X) (because of the E ♯ term). However, we can apply it to the soft truncated excess loss

ℓ (X, Y ), f, f ′ = T λ l Y, f (X) -l Y, f ′ (X) , with T (x) = -log(1-x+x 2 /2)
. This section provides a result similar to Theorem 3.2 in which condition V1 is replaced by the following condition. Condition V2. For any function f , the random variable l Y, f (X) -l Y, f * (X) is square integrable and there exists V > 0 such that for any function f ,

E l Y, f (X) -l Y, f * (X) 2 ≤ V [R(f ) -R(f * )].
THEOREM 3.5 Assume that Conditions V2 above and C (page 18) are satisfied. Let 0 < λ < V -1 and

ℓ (X, Y ), f, f ′ = T λ l Y, f (X) -l Y, f ′ (X) , (3.12
)

with T (x) = -log(1 -x + x 2 /2). (3.13)
Let f ∈ F be a function drawn according to the distribution π defined in (3.10, page 17) with Ê defined in (3.4, page 16) and π * = π the distribution appearing in Condition C. Then for any 0 < η ′ < 1 -λV and ε > 0, with probability at least 1ε, we have

R( f ) -R(f * ) ≤ V C ′ 1 D + C ′ 2 log(2ε -1 ) n with C ′ 1 = log G(1 + η) 2 η ′ (1 -η) η(1 -η -η ′ ) , C ′ 2 = 2 η(1 -η -η ′ )
and η = λV.

In particular, for λ = 0.32V -1 and η ′ = 0.18, we get

R( f ) -R(f * ) ≤ V 16.6D + 12.5 log(2 √ Gε -1 ) n .
PROOF. We apply Theorem 3.1 for ℓ given by (3.12) and π * = π. Let us define, for any f,

f ′ ∈ F, W (f, f ′ ) = λ l Y, f (X) -l Y, f ′ (X) . Since log u ≤ u-1
for any u > 0, we have

L ♭ = -n log E 1 -W + W 2 /2 ≥ n E(W ) -E(W 2 )/2 . Moreover, from Assumption V2, E W (f, f ′ ) 2 2 ≤ E W (f, f * ) 2 + E W (f ′ , f * ) 2 ≤ λ 2 V R(f ) + λ 2 V R(f ′ ), (3.14)
hence, by introducing η = λV ,

L ♭ (f, f ′ ) ≥ λn R(f ) -R(f ′ ) -λV R(f ) -λV R(f ′ ) = λn (1 -η) R(f ) -(1 + η) R(f ′ ) . (3.15) Noting that exp T (u) = 1 1 -u + u 2 /2 = 1 + u + u 2 2 1 + u 2 2 2 -u 2 = 1 + u + u 2 2 1 + u 4 4 ≤ 1 + u + u 2 2 ,
we see that

L ♯ = n log E exp T (W ) ≤ n E W + E W 2 /2 .
Using (3.14) and still η = λV , we get

L ♯ (f, f ′ ) ≤ λn R(f ) -R(f ′ ) + η R(f ) + η R(f ′ ) = λn(1 + η) R(f ) -λn(1 -η) R(f ′ ), and
E ♯ (f ) ≤ λn(1 + η) R(f ) -I λn(1 -η) . ( 3
λn(1 -η) -γ R( f ) + γ * -λn(1 + η) R(f )π -γ * R(df ) ≤ I(γ * ) -I(γ) + I λn(1 + η) -I λn(1 -η) + 2 log 2ε -1 .
By the complexity assumption, choosing γ * = λn(1 + η) and γ < λn(1η), we get

λn(1 -η) -γ R( f ) ≤ D log G λn(1 + η) 2 γ(1 -η) + 2 log 2ε -1 ,
hence the desired result by considering γ = λnη ′ with η ′ < 1η.

REMARK 3.2 The estimator seems abnormally complicated at first sight. This remark aims at explaining why we were not able to consider a simpler estimator. In Section 3.3, in which we consider the exponential moment condition V1, we took ℓ (X, Y ), f, f ′ = λ l Y, f (X) -l Y, f ′ (X) and π * as the Dirac distribution at f * . For these choices, one can easily check that π does not depend on f * .

In the absence of an exponential moment condition, we cannot consider the function ℓ (X, Y ), f, f ′ = λ l Y, f (X) -l Y, f ′ (X) but have instead to use a truncated version. The truncation function T of Theorem 3.5 can be replaced by the simpler function u → (u ∨ -M) ∧ M for some appropriate constant M > 0 but this leads to a bound with worse constants, without really simplifying the algorithm. The precise choice T (x) =log(1x + x 2 /2) comes from the remarkable property: there exist second order polynomials P ♭ and P ♯ such that 1 P ♭ (u) ≤ exp T (u) ≤ P ♯ (u) and P ♭ (u)P ♯ (u) ≤ 1 + O(u 4 ) for u → 0, which are reasonable properties to ask in order to ensure that (3.8), and consequently (3.11), are tight.

Besides, if we take ℓ as in (3.12) with T a truncation function and π * as the Dirac distribution at f * , then π would depend on f * , and is consequently not observable. This is the reason why we do not consider π * as the Dirac distribution at f * , but π * = π. This leads to the estimator considered in Theorems 3.5 and 2.1. REMARK 3.3 Theorem 3.5 still holds for the same randomized estimator in which (3.13, page 21) is replaced with

T (x) = log(1 + x + x 2 /2).
Condition V2 holds under weak assumptions as illustrated by the following lemma. LEMMA 3.6 Consider the least squares setting: l(y, y ′ ) = (yy ′ ) 2 . Assume that F is convex and has a diameter upper bounded by H for the L ∞ -norm:

sup f 1 ,f 2 ∈F,x∈X |f 1 (x) -f 2 (x)| ≤ H
and that for some σ > 0, we have

sup x∈X E [Y -f * (X)] 2 X = x ≤ σ 2 < +∞.
(3.17)

Then Condition V2 holds for V = (2σ + H) 2 .
PROOF. See Section 4.5 (page 33).

LEMMA 3.7 Consider the least squares setting: l(y, y ′ ) = (yy ′ ) 2 . Assume that F (i.e., Θ) is bounded, and that for any j ∈ {1, . . . , d}, E ϕ j (X)

4 < + ∞ and E ϕ j (X) 2 [Y -f * (X)] 2 < +∞. Then Condition V2 holds for V = 2 sup f ∈F lin :E[f (X) 2 ]=1 E f (X) 2 [Y -f * (X)] 2 + sup f ′ ,f ′′ ∈F E [f ′ (X) -f ′′ (X)] 2 sup f ∈F lin :E[f (X) 2 ]=1 E f (X) 4 2 .
PROOF. See Section 4.6 (page 33).

4. PROOFS 4.1. MAIN IDEAS OF THE PROOFS. The goal of this section is to explain the key ingredients appearing in the proofs which both allow to obtain sub-exponential tails for the excess risk under a non-exponential moment assumption and get rid of the logarithmic factor in the excess risk bound.

Sub-exponential tails under a non-exponential moment assumption via truncation.

Let us start with the idea allowing us to prove exponential inequalities under just a moment assumption (instead of the traditional exponential moment assumption). To understand it, we can consider the (apparently) simplistic 1-dimensional situation in which we have Θ = R and the marginal distribution of ϕ 1 (X) is the Dirac distribution at 1. In this case, the risk of the prediction function

f θ is R(f θ ) = E (Y -θ) 2 = E (Y -EY ) 2 +(EY -θ) 2
, so that the least squares regression problem boils down to the estimation of the mean of the output variable. If we only assume that Y admits a finite second moment, say E(Y 2 ) ≤ 1, it is not clear whether for any ε > 0, it is possible to find θ such that with probability at least 1 -2ε,

R(f θ) -R(f * ) = E(Y ) -θ 2 ≤ c log(ε -1 ) n , (4.1)
for some numerical constant c. Indeed, from Chebyshev's inequality, the trivial choice θ = 1 n n i=1 Y i just satisfies: with probability at least 1 -2ε,

R(f θ) -R(f * ) ≤ 1 nε ,
which is far from the objective (4.1) for small confidence levels (consider ε = exp(-√ n) for instance). The key idea is thus to average (soft) truncated values of the outputs. This is performed by taking

θ = 1 nλ n i=1 log 1 + λY i + λ 2 Y 2 i 2 , with λ = 2 log(ε -1
) n (this mean estimator thus depends on the confidence level parameter ε). Since we have

log E exp(nλ θ) = n log 1 + λE(Y ) + λ 2 2 E(Y 2 ) ≤ nλE(Y ) + n λ 2 2 ,
the exponential Chebyshev's inequality (see Lemma 4.1) guarantees that with probability at least 1ε, we have nλ(

θ -E(Y )) ≤ n λ 2 2 + log(ε -1 ), hence θ -E(Y ) ≤ 2 log(ε -1 ) n .
Replacing Y by -Y in the previous argument, we obtain that with probability at least 1ε, we have

nλ E(Y ) + 1 nλ n i=1 log 1 -λY i + λ 2 Y 2 i 2 ≤ n λ 2 2 + log(ε -1 ). Since -log(1 + x + x 2 /2) ≤ log(1 -x + x 2 /2), this implies E(Y ) -θ ≤ 2 log(ε -1 ) n .
The two previous inequalities imply Inequality (4.1) (for c = 2), showing that sub-exponential tails are achievable even when we only assume that the random variable admits a finite second moment (see [START_REF] Catoni | Challenging the empirical mean and empirical variance: a deviation study[END_REF] for more details on the robust estimation of the mean of a random variable).

Localized PAC-Bayesian inequalities to eliminate a logarithm factor.

The analysis of statistical inference generally relies on upper bounding the supremum of an empirical process χ indexed by the functions in a model F. One central tool to obtain these bounds are the concentration inequalities. An alternative approach, called the PAC-Bayesian one, consists in using the entropic equality

E exp sup ρ∈M ρ(df )χ(f ) -K(ρ, π ′ ) = π ′ (df )E exp χ(f ) . (4.2)
where M is the set of probability distributions on F and K(ρ, π ′ ) is the Kullback-Leibler divergence (whose definition is recalled in (4.4, page 29)) between ρ and some fixed distribution π ′ . Let ř : F → R be an observable process such that for any f ∈ F, we have

E exp χ(f ) ≤ 1 for χ(f ) = λ[R(f ) -ř(f )
] and some λ > 0. Then, as a consequence of (4.2), for any ε > 0, with probability at least 1ε, for any distribution ρ on F,

ρ(df )R(f ) ≤ ρ(df )ř(f ) + K(ρ, π ′ ) + log(ε -1 ) λ . (4.3)
The left-hand side quantity represents the expected risk with respect to the distribution ρ. The question is now how to use (4.3) to design a posterior distribution ρ for which ρ(df )R(f ) is guaranteed to be small. The constraint on the choice of (ρ, π ′ ) is that ρ should be computable from the data (e.g., it cannot depend on R) and π ′ should not depend on the data: it may depend on R (in contrast with Bayesian prior distributions!) but not on ř. Simple choices like (ρ,

π ′ ) = (δ f * , δ f * ) or (ρ, π ′ ) = (δ f , δ f ) for f ∈ argmin f ∈F ř(f )
, where δ a denotes the Dirac distribution at the function f , are thus forbidden (while they would have led to small right-hand side of (4.3)).

For fixed π ′ , the posterior distribution minimizing the right-hand side of (4.3) is ρ = π ′ -λř . It is computable from the data if π ′ is. Without prior knowledge, this would lead to take a "flat" distribution for π ′ (e.g., the one induced by the Lebesgue measure in the case of a model F defined by a bounded parameter set in some Euclidean space). The resulting Kullback-Leibler divergence might be very large as it compares a distribution with a sharp peak (concentrated on functions f ∈ F for which ř(f )) with a flat one.

To get a smaller Kullback-Leibler divergence, we can take posterior and prior distributions which are peaked around almost the same function. This can be done by taking π and ρ respectively concentrated around f * and f . More precisely, one can take posterior distributions of the form ρ = π -λř for some λ > 0 and a "flat" distribution π computable without knowing neither the distribution P generating the data nor the training data (in particular, π must not depend on R or ř), and a "localized" prior distribution π ′ = π -βR for some β > 0. The parameters λ and β controlling the sharpness of the peaks at argmin f ∈F R(f ) * and argmin f ∈F ř(f ) should be taken such that the peaks overlap (to ensure that the Kullback-Leibler divergence is small) and are in the same time sharp enough (to ensure that ρ(df )ř(f ) is small). The use of the "localized" prior distribution π ′ = π -βR implies an additional technical difficulty as one needs to control the divergence K(ρ, π -βR ). This is achieved by writing

K(ρ, π -βR ) = K(ρ, π) + log exp[-βR(f )] π(df ) + β R(f ) ρ(df ),
and controlling the new logarithmic term through PAC-Bayesian inequalities.

4.2. PROOF OF THEOREM 3.1. We use the standard way of obtaining PAC bounds through upper bounds on Laplace transforms of appropriate random variables. This argument is synthesized in the following result.

LEMMA 4.1 For any ε > 0 and any real-valued random variable V such that E exp(V ) ≤ 1, with probability at least 1ε, we have

V ≤ log(ε -1 ). Let V 1 ( f ) = L ♭ ( f , f ) + γ * R(f ) π * -γ * R(df ) -γ R( f ) -I * (γ * ) + I(γ) + log exp -Ê(f ) π(df ) -log dρ dπ f ,
and

V 2 = -log exp -Ê(f ) π(df ) + log exp -E ♯ (f ) π(df )
To prove the theorem, according to Lemma 4.1, it suffices to prove that

E exp V 1 ( f ) ρ(d f ) ≤ 1 and E exp(V 2 )ρ(d f ) ≤ 1.
These two inequalities are proved in the following two sections.

4.2.1. Proof of E exp V 1 ( f ) ρ(d f ) ≤ 1.
From Jensen's inequality, we have

L ♭ ( f , f ) + γ * R(f ) π * -γ * R(df ) = L( f , f ) + γ * R(f ) π * -γ * R(df ) + L ♭ ( f , f ) -L( f , f ) π * -γ * R(df ) ≤ L( f , f ) + γ * R(f ) π * -γ * R(df ) + log exp L ♭ ( f , f ) -L( f , f ) π * -γ * R(df ).
From Jensen's inequality again,

-Ê( f ) = -log exp L( f , f ) π * (df ) = -log exp L( f , f ) + γ * R(f ) π * -γ * R(df ) -log exp -γ * R(f ) π * (df ) ≤ -[ L( f , f ) + γ * R(f )]π * -γ * R(df ) + I * (γ * ).
From the two previous inequalities, we get

V 1 ( f ) ≤ L( f , f ) + γ * R(f ) π * -γ * R(df ) + log exp L ♭ ( f , f ) -L( f , f ) π * (df ) -γ R( f ) -I * (γ * ) + I(γ) + log exp -Ê(f ) π(df ) -log dρ dπ ( f ) , = L( f , f ) + γ * R(f ) π * -γ * R(df ) + log exp L ♭ ( f , f ) -L( f , f ) π * (df ) -γ R( f ) -I * (γ * ) + I(γ) -Ê( f ) -log dρ dπ ( f ) , ≤ log exp L ♭ ( f , f ) -L( f , f ) π * -γ * R(df ) -γ R( f ) + I(γ) -log dρ dπ ( f ) = log exp L ♭ ( f , f ) -L( f , f ) π * -γ * R(df ) + log dπ -γ R dρ ( f ) ,
hence, by using Fubini's inequality and the equality

E exp -L( f , f ) = exp -L ♭ ( f , f ) , we obtain E exp V 1 ( f ) ρ(d f ) ≤ E exp L ♭ ( f , f ) -L( f , f ) π * -γ * R(df ) π -γ R(d f ) = E exp L ♭ ( f , f ) -L( f , f ) π * -γ * R(df ) π -γ R(d f ) = 1. 4.2.2. Proof of E exp(V 2 )ρ(d f ) ≤ 1.
It relies on the following result.

LEMMA 4.2 Let W be a real-valued measurable function defined on a product space A 1 × A 2 and let µ 1 and µ 2 be probability distributions on respectively A 1 and A 2 .

• if

E a 1 ∼µ 1 log E a 2 ∼µ 2 exp -W(a 1 , a 2 ) < +∞, then we have -E a 1 ∼µ 1 log E a 2 ∼µ 2 exp -W(a 1 , a 2 ) ≤ -log E a 2 ∼µ 2 exp -E a 1 ∼µ 1 W(a 1 , a 2 ) . • if W > 0 on A 1 × A 2 and E a 2 ∼µ 2 E a 1 ∼µ 1 W(a 1 , a 2 ) -1 -1 < +∞, then E a 1 ∼µ 1 E a 2 ∼µ 2 W(a 1 , a 2 ) -1 -1 ≤ E a 2 ∼µ 2 E a 1 ∼µ 1 W(a 1 , a 2 ) -1 -1
.

PROOF.

• Let A be a measurable space and M denote the set of probability distributions on A. The Kullback-Leibler divergence between a distribution ρ and a distribution µ is

K(ρ, µ)    E a∼ρ log dρ dµ (a) if ρ ≪ µ, +∞ otherwise, (4.4
inf ρ∈M E a∼ρ h(a) + K(ρ, µ) = -log E a∼µ exp -h(a) . (4.5)
By using twice (4.5) and Fubini's theorem, we have

-E a 1 ∼µ 1 log E a 2 ∼µ 2 exp -W(a 1 , a 2 ) = E a 1 ∼µ 1 inf ρ E a 2 ∼ρ W(a 1 , a 2 ) + K(ρ, µ 2 ) ≤ inf ρ E a 1 ∼µ 1 E a 2 ∼ρ W(a 1 , a 2 ) + K(ρ, µ 2 ) = -log E a 2 ∼µ 2 exp -E a 1 ∼µ 1 W(a 1 , a 2
) .

• By using twice (4.5) and the first assertion of Lemma 4.2, we have

E a 1 ∼µ 1 E a 2 ∼µ 2 W(a 1 , a 2 ) -1 -1 = E a 1 ∼µ 1 exp -log E a 2 ∼µ 2 exp -log W(a 1 , a 2 ) = E a 1 ∼µ 1 exp inf ρ E a 2 ∼ρ log W(a 1 , a 2 ) + K(ρ, µ 2 ) ≤ inf ρ exp K(ρ, µ 2 ) E a 1 ∼µ 1 exp E a 2 ∼ρ log W(a 1 , a 2 ) ≤ inf ρ exp K(ρ, µ 2 ) exp E a 2 ∼ρ log E a 1 ∼µ 1 W(a 1 , a 2 ) = exp inf ρ E a 2 ∼ρ log E a 1 ∼µ 1 W(a 1 , a 2 ) + K(ρ, µ 2 ) = exp -log E a 2 ∼µ 2 exp -log E a 1 ∼µ 1 W(a 1 , a 2 ) = E a 2 ∼µ 2 E a 1 ∼µ 1 W(a 1 , a 2 ) -1 -1
.

From Lemma 4.2 and Fubini's theorem, since V 2 does not depend on f , we have

E exp(V 2 )ρ(d f ) = E exp(V 2 ) = exp -E ♯ (f ) π(df ) E exp -Ê(f ) π(df ) -1 ≤ exp -E ♯ (f ) π(df ) E exp Ê(f ) -1 π(df ) -1 = exp -E ♯ (f ) π(df ) E exp L(f, f ′ ) π * (df ′ ) -1 π(df ) -1 = exp -E ♯ (f ) π(df ) exp L ♯ (f, f ′ ) π * (df ′ ) -1 π(df ) -1 = 1.
This concludes the proof that for any γ ≥ 0, γ * ≥ 0 and ε > 0, with probability (with respect to the distribution P ⊗n ρ generating the observations Z 1 , . . . , Z n and the randomized prediction function f ) at least 1 -2ε: Introduce Ω = φ ∈ S; ∃u > 0 s.t. f * + uφ ∈ F .

V 1 ( f ) + V 2 ≤ 2 log(ε -1 ).
For any φ ∈ Ω, let u φ = sup{u > 0 : f * + uφ ∈ F}. Since π is the uniform distribution on the convex set F (i.e., the one coming from the uniform distribution on Θ), we have

exp -α[R(f ) -R(f * )] π(df ) = φ∈Ω u φ 0 exp -α[R(f * + uφ) -R(f * )] u d-1 dudφ. Let c φ = E[φ(X) l′ Y (f * (X))
] and a φ = E φ 2 (X) . Since

f * ∈ argmin f ∈F E lY f (X) ,
we have c φ ≥ 0 (and c φ = 0 if both -φ and φ belong to Ω). Moreover from Taylor's expansion,

b 1 a φ u 2 2 ≤ R(f * + uφ) -R(f * ) -uc φ ≤ b 2 a φ u 2 2 .
Introduce

ψ φ = u φ 0 exp -α[uc φ + 1 2 b 1 a φ u 2 ] u d-1 du u φ 0 exp -β[uc φ + 1 2 b 2 a φ u 2 ] u d-1 du .
For any 0 < α < β, we have

exp -α[R(f ) -R(f * )] π(df ) exp -β[R(f ) -R(f * )] π(df ) ≤ inf φ∈S ψ φ .
For any ζ > 1, by a change of variable,

ψ φ < ζ d u φ 0 exp -α[ζuc φ + 1 2 b 1 a φ ζ 2 u 2 ] u d-1 du u φ 0 exp -β[uc φ + 1 2 b 2 a φ u 2 ] u d-1 du ≤ ζ d sup u>0 exp β[uc φ + 1 2 b 2 a φ u 2 ] -α[ζuc φ + 1 2 b 1 a φ ζ 2 u 2 ] . Taking ζ = (b 2 β)/(b 1 α) when c φ = 0 and ζ = (b 2 β)/(b 1 α) ∨ (β/α) other- wise, we obtain ψ φ < ζ d , hence log exp -α[R(f ) -R(f * )] π(df ) exp -β[R(f ) -R(f * )] π(df ) ≤        d 2 log b 2 β b 1 α when sup φ∈Ω c φ = 0, d log b 2 β b 1 α ∨ β α otherwise,
which proves the announced result.

4.4. PROOF OF LEMMA 3.4. For -(2AH) -1 ≤ λ ≤ (2AH) -1 , introduce the random variables

F = f (X) F * = f * (X), Ω = l′ Y (F * ) + (F -F * ) 1 0 (1 -t) l′′ Y (F * + t(F -F * ))dt, L = λ[ l(Y, F ) -l(Y, F * )],
and the quantities

a(λ) = M 2 A 2 exp(Hb 2 /A) 2 √ π(1 -|λ|AH) and à = Hb 2 /2 + A log(M) = A 2 log M 2 exp Hb 2 /(2A) .
From Taylor-Lagrange formula, we have

L = λ(F -F * )Ω. Since E exp |Ω|/A | X ≤ M exp Hb 2 /(2A) , Lemma D.2 gives log E exp α[Ω -E(Ω|X)]/A | X ≤ M 2 α 2 exp Hb 2 /A 2 √ π(1 -|α|)
for any -1 < α < 1, and

E(Ω|X) ≤ Ã. (4.6) By considering α = Aλ[f (x) -f * (x)] ∈ [-1/2; 1/2] for fixed x ∈ X, we get log E exp L -E(L|X) | X ≤ λ 2 (F -F * ) 2 a(λ). (4.7)
Let us put moreover

L = E(L|X) + a(λ)λ 2 (F -F * ) 2 .
Since

log E exp L -E(L) ≤ log E exp L -E( L) + λ 2 a(λ)E (F -F * ) 2 ≤ E L2 g(b ′ ) + λ 2 a(λ)E (F -F * ) 2 ≤ λ 2 E (F -F * ) 2 Ã2 g(b ′ ) + a(λ) , with g(u) = exp(u) -1 -u /u 2 . Computations show that for any -(2AH) -1 ≤ λ ≤ (2AH) -1 , Ã2 g(b ′ ) + a(λ) ≤ A 2 4 exp M 2 exp Hb 2 /A .
Consequently, for any

-(2AH) -1 ≤ λ ≤ (2AH) -1 , we have log E exp λ[ l(Y, F ) -l(Y, F * )] ≤ λ[R(f ) -R(f * )] + λ 2 E (F -F * ) 2 A 2 4 exp M 2 exp Hb 2 /A . Now it remains to notice that E (F -F * ) 2 ≤ 2[R(f ) -R(f * )]/b 1 . Indeed con- sider the function φ(t) = R(f * + t(f -f * )) -R(f * ), where f ∈ F and t ∈ [0; 1].
From the definition of f * and the convexity of F, we have φ ≥ 0 on [0; 1], implying that φ ′ (0) ≥ 0. Besides φ(1) = φ(0) + φ ′ (0) + 1 0 (1t)φ ′′ (t)dt, where φ ′′ (t) is defined as

φ ′′ (t) = E f (X) -f * (X) 2 l′′ Y [(1 -t)f * + f ](X) ≥ b 1 E f (X) -f * (X) 2 , implying that b 1 2 E(F -F * ) 2 ≤ R(f ) -R(f * ). (4.8)
4.5. PROOF OF LEMMA 3.6. We have

E [Y -f (X)] 2 -[Y -f * (X)] 2 2 = E [f * (X) -f (X)] 2 2[Y -f * (X)] + [f * (X) -f (X)] 2 = E [f * (X) -f (X)] 2 4E [Y -f * (X)] 2 X + 4E(Y -f * (X)|X)[f * (X) -f (X)] + [f * (X) -f (X)] 2 ≤ E [f * (X) -f (X)] 2 4σ 2 + 4σ|f * (X) -f (X)| + [f * (X) -f (X)] 2 ≤ E [f * (X) -f (X)] 2 (2σ + H) 2 ≤ (2σ + H) 2 [R(f ) -R(f * )],
where the last inequality is the usual relation between excess risk and L 2 distance using the convexity of F (see above (4.8) for a proof).

E [Y -f (X)] 2 -[Y -f * (X)] 2 2 = E 2[f * (X) -f (X)][Y -f * (X)] + [f * (X) -f (X)] 2 2 ≤ 2 E [f * (X) -f (X)] 2 [Y -f * (X)] 2 + E [f * (X) -f (X)] 4 2 ≤ 2 E [f * (X) -f (X)] 2 sup s∈S E s(X) 2 [Y -f * (X)] 2 + E [f * (X) -f (X)] 2 sup s∈S E s(X) 4 2 ≤ V [R(f ) -R(f * )], with V = 2 sup s∈S E s(X) 2 [Y -f * (X)] 2 + sup f ′ ,f ′′ ∈F E [f ′ (X) -f ′′ (X)] 2 sup s∈S E s(X) 4 2 ,
where the last inequality is the usual relation between excess risk and L 2 distance using the convexity of F (see above (4.8) for a proof).

A. UNIFORMLY BOUNDED CONDITIONAL VARIANCE IS NECESSARY TO REACH d/n RATE

In this section, we show that the target (0.3) cannot be reached if we just assume that Y has a finite variance and that the functions in F are bounded. For this purpose, the following result gives a 1/ √ n lower bound when d = 2. (Note that it is not implied by the log(1 + d/ √ n)/n lower bound for convex aggregation, proved in [START_REF] Tsybakov | Optimal rates of aggregation[END_REF], and in slightly weaker forms in [START_REF] Juditsky | Functional aggregation for nonparametric estimation[END_REF][START_REF] Yang | Aggregating regression procedures for a better performance[END_REF], since the latter bound is shown for d ≥ √ n.)

For this, consider an input space X partitioned into two sets X 1 and X

2 : X = X 1 ∪ X 2 and X 1 ∩ X 2 = ∅. Let ϕ 1 (x) = 1 x∈X 1 and ϕ 2 (x) = 1 x∈X 2 . Let F = θ 1 ϕ 1 + θ 2 ϕ 2 ; (θ 1 , θ 2 ) ∈ [-1, 1] 2 .
THEOREM A.1 For any estimator f and any training set size n ≥ 1, we have

sup P E R( f ) -R(f * ) ≥ 1 4 √ n , (A.1)
where the supremum is taken with respect to all probability distributions such that f (reg) ∈ F and Var(Y ) ≤ 1.

PROOF. Let β satisfying 0 < β ≤ 1 be some parameter to be chosen later. Let P σ , σ ∈ {-, +}, be two probability distributions on X × R such that for any σ ∈ {-, +},

P σ (X 1 ) = 1 -β, P σ (Y = 0|X = x) = 1 for any x ∈ X 1 , and
P σ Y = 1 √ β | X = x = 1 + σ √ β 2 = 1 -P σ Y = - 1 √ β | X = x for any x ∈ X 2 .
One can easily check that for any σ ∈ {-, +}, Var Pσ (Y ) = 1β ≤ 1 and f (reg) (x) = σϕ 2 ∈ F. To prove Theorem A.1, it suffices to prove (A.1) when the supremum is taken among P ∈ {P -, P + }. This is done by applying Theorem 8.2 of [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF]. Indeed, the pair (P -, P + ) forms a (1, β, β)-hypercube in the sense of Definition 8.2 with edge discrepancy of type I (see (8.5), (8.11) and (10.20) for q = 2): d I = 1. We obtain

sup P ∈{P -,P + } E R( f ) -R(f * ) ≥ β(1 -β √ n),
which gives the desired result by taking β = 1/(2 √ n).

B. EMPIRICAL RISK MINIMIZATION ON

∈ F # such that f -g ∞ ≤ δ.
We apply a slightly improved version of Theorem 5 in Birgé and Massart [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF]. First for homogeneity purpose, we modify Assumption M2 by replacing the condition "σ 2 ≥ D/n" by "σ 2 ≥ B 2 D/n" where the constant B is the one appearing in (5.3) of [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF]. This modifies Theorem 5 of [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF] to the extent that "∨1" should be replaced with "∨B 2 ". Our second modification is to remove the assumption that W i and X i are independent. A careful look at the proof shows that the result still holds when (5.2) is replaced by: for any x ∈ X, and m ≥ 2

E s [M m (W i )|X i = x] ≤ a m A m ,
for all i = 1, . . . , n.

We consider

W = Y -f * (X), γ(z, f ) = (y -f (x)) 2 , ∆(x, u, v) = |u(x) -v(x)|, and
M(w) = 2(|w| + H). From (1.7), for all m ≥ 2, we have E [(2(|W | + H)] m |X = x] ≤ m! 2 [4M(A + H)] m
. Now consider B ′ and r such that Assumption M2 of [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF] holds for D = d. Inequality (5.8) for τ = 1/2 of [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF] implies that for any

v ≥ κ d n (A 2 + H 2 ) log(2B ′ + B ′ r d/n), with probability at least 1 - κ exp -nv κ(A 2 + H 2 ) , R( f (erm) ) -R(f * ) + r(f * ) -r( f (erm) ) ≤ E f (erm) (X) -f * (X) 2 ∨ v /2
for some large enough constant κ depending on M. Now from Proposition 1 of [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF] and Lemma B.1, one can take either B ′ = 6 and r

√ d = B or B ′ = 3 n/d and r = 1. By using E f (erm) (X) -f * (X) 2 ≤ R( f (erm) ) -R(f * ) (since F is
convex and f * is the orthogonal projection of Y on F), and r(f * )r( f (erm) ) ≥ 0 (by definition of f (erm) ), the desired result can be derived. Theorem 1.5 provides a d/n rate provided that the geometrical quantity B is at most of order n. Inequality (3.2) of [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF] allows to bracket B in terms of B = sup f ∈span{ϕ 1 ,...,ϕ d } f 2

∞ /E[f (X)] 2 , namely B ≤ B ≤ Bd. To understand better how this quantity behaves and to illustrate some of the presented results, let us give the following simple example.

Example 1. Let A 1 , . . . , A d be a partition of X, i.e., X = ⊔ d j=1 A j . Now consider the indicator functions ϕ j = 1 A j , j = 1, . . . , d: ϕ j is equal to 1 on A j and zero elsewhere. Consider that X and Y are independent and that Y is a Gaussian random variable with mean θ and variance σ 2 . In this situation: f for some numerical constant κ. When d is large, the term (d 2 L 2 ε )/(np min ) is felt, and leads to suboptimal rates. Specifically, since p min ≤ 1/d, the r.h.s. of (B.1) is greater than d 4 /n 2 , which is much larger than d/n when d is much larger than n 1/3 . If Y is not Gaussian but almost surely uniformly bounded by C < +∞, then the randomized estimator proposed in Theorem 1.3 satisfies the nicer property: with probability at least 1ε,

R( f ) -R(f * lin ) ≤ κ(H 2 + C 2 )
d log(3p -1 min ) + log((log n)ε -1 ) n ,

for some numerical constant κ. In this example, one can check that B = B′ = 1/p min where p min = min j P(X ∈ A j ). As long as p min ≥ 1/n, the target (0.2) is reached from Corollary 1.5. Otherwise, without this assumption, the rate is in (d log(n/d))/n.

C. RIDGE REGRESSION ANALYSIS FROM THE WORK OF CAPONNETTO AND DE VITO

From [START_REF] Caponnetto | Optimal rates for the regularized leastsquares algorithm[END_REF], one can derive the following risk bound for the ridge estimator.

THEOREM C.1 Let q min be the smallest eigenvalue of the d × d-product matrix Q = Eϕ j (X)ϕ k (X) j,k . Let K = sup x∈X d j=1 ϕ j (x) 2 . Let θ * be the Euclidean norm of the vector of parameters of f * lin = d j=1 θ * j ϕ j . Let 0 < ε < 1/2 and L ε = log 2 (ε -1 ). Assume that for any x ∈ X,

E exp |Y -f * lin (X)|/A | X = x ≤ M.
For λ = (KdL ε )/n, if λ ≤ q min , the ridge regression estimator satisfies with probability at least 1ε:

R( f (ridge) ) -R(f * lin ) ≤ κL ε d n A 2 + λ q min KL ε θ * 2 (C.1)
for some positive constant κ depending only on M.

PROOF. One can check that f (ridge) ∈ argmin f ∈H r(f )+λ d j=1 f 2 H , where H is the reproducing kernel Hilbert space associated with the kernel K : (x, x ′ ) → d j=1 ϕ j (x)ϕ k (x ′ ). Introduce f (λ) ∈ argmin f ∈H R(f ) + λ d j=1 f 2 H . Let us use Theorem 4 in [START_REF] Caponnetto | Optimal rates for the regularized leastsquares algorithm[END_REF] and the notation defined in their Section 5.2. Let ϕ be the column vector of functions [ϕ j ] d j=1 , Diag(a j ) denote the diagonal d × d-matrix whose jth element on the diagonal is a j , and I d be the d × d-identity matrix. Let U and q 1 , . . . , q d be such that UU T = I and Q = UDiag(q j )U T . We have f * lin = ϕ T θ * and f (λ) = ϕ T (Q + λI) -1 Qθ * , hence f * linf (λ) = ϕ T UDiag(λ/(q j + λ))U T θ * .

After some computations, we obtain that the residual, reconstruction error and effective dimension respectively satisfy A(λ) ≤ λ 2 q min θ * 2 , B(λ) ≤ λ 2 q 2 min θ * 2 , and N(λ) ≤ d. The result is obtained by noticing that the leading terms in (34) of [START_REF] Caponnetto | Optimal rates for the regularized leastsquares algorithm[END_REF] are A(λ) and the term with the effective dimension N(λ).

The dependence in the sample size n is correct since 1/n is known to be minimax optimal. The dependence on the dimension d is not optimal, as it is observed in the example given page 36. Besides the high probability bound (C.1) holds only for a regularization parameter λ depending on the confidence level ε. So we do not have a single estimator satisfying a PAC bound for every confidence level. PROOF. Since g is an increasing function, we have g(V ) ≤ g(b). By using the inequality log(1 + u) ≤ u, we obtain

log E exp V -E(V ) = -E(V ) + log E 1 + V + V 2 g(V ) ≤ E V 2 g(V ) ≤ E V 2 g(b).
LEMMA D.2 Let V be a real-valued random variable such that E exp |V | ≤ M for some M > 0. Then we have |E(V )| ≤ log M, and for any -1 < α < 1,

log E exp α V -E(V ) ≤ α 2 M 2 2 √ π(1 -|α|) .
PROOF. First note that by Jensen's inequality, we have |E(V )| ≤ log(M). By using log(u) ≤ u -1 and Stirling's formula, for any -1 < α < 1, we have

log E exp α V -E(V ) ≤ E exp α V -E(V ) -1 = E exp α V -E(V ) -1 -α V -E(V ) ≤ E exp |α||V -E(V )| -1 -|α||V -E(V )| ≤ E exp |V -E(V )| sup
≤ α 2 M 2 m≥2 |α| m-2 √ 2πm ≤ α 2 M 2 2 √ π(1 -|α|)
.

THEOREM 1 . 6

 16 If sup x∈X Var(Y |X = x) = σ 2 < +∞ and

3. 2 .THEOREM 3 . 1

 231 THE LOCALIZED PAC-BAYES BOUND. With the notation introduced in the previous section, we have the following risk bound for any randomized estimator. Assume that π, π * , F and ℓ satisfy the integrability conditions (3.1) and (3.2, page 16). Let ρ be a (posterior) probability distribution on F admitting a density with respect to π depending on Z 1 , . . . , Z n . Let f be a prediction function drawn from the distribution ρ. Then for any γ ≥ 0, γ * ≥ 0 and ε > 0, with probability (with respect to the distribution P ⊗n ρ generating the observations Z 1 , . . . , Z n and the randomized prediction function f ) at least 1ε:

  and l(y, y ′ ) = l(y, y) + (y ′y) l′ y (y) + y ′ y (y ′y ′′ ) l′′ y (y ′′ )dy ′′ . Then Condition C holds for the above uniform π, G = b 2 /b 1 and D = d. Besides when f * = f * lin (i.e., min F R = min θ∈R d R(f θ )), Condition C holds for the above uniform π, G = b 2 /b 1 and D = d/2. PROOF. See Section 4.3 (page 30). REMARK 3.1 In particular, for the least squares loss l(y, y ′ ) = (yy ′ ) 2 , we have b 1 = b 2 = 2 so that condition C holds with π the uniform distribution on F, D = d and G = 1, and with D = d/2 and G = 1 when f * = f * lin .

. 16 )

 16 Plugging (3.15) and (3.16) in (3.11) for ρ = π, we obtain

4. 3 .

 3 PROOF OF LEMMA 3.3. Let us look at F from the point of view of f * . Precisely let S R d (O, 1) be the sphere of R d centered at the origin and with radius 1 and S = d j=1 θ j ϕ j ; (θ 1 , . . . , θ d ) ∈ S R d (O, 1) .

  -(2AH) -1 ≤ λ ≤ (2AH) -1 , we have L ≤ |λ|H Ã + a(λ)λ 2 H 2 ≤ b ′ with b ′ = Ã/(2A) + M 2 exp Hb 2 /A /(4 √ π). Since L -E(L) = L -E(L|X) + E(L|X) -E(L),by using Lemma D.1, (4.7) and (4.6), we obtain

4. 6 .

 6 PROOF OF LEMMA 3.7. Let S = {s ∈ F lin : E[s(X) 2 ] = 1}. Using the triangular inequality in L 2 , we get

  * lin = f (reg) = d j=1 θϕ j . According to Theorem 1.1, if we know an upper bound H on f (reg) ∞ = θ, we have that the truncated estimator ( f (ols) ∧ H) ∨ -H satisfiesER( f (ols) H ) -R(f * lin ) ≤ κ (σ 2 ∨ H 2 )d log n nfor some numerical constant κ. Let us now apply Theorem C.1. Introduce p j = P(X ∈ A j ) and p min = min j p j . We have Q = Eϕ j (X)ϕ k (X) j,k = Diag(p j ), K = 1 and θ * = θ √ d. We can take A = σ and M = 2. From Theorem C.1, for λ = dL ε /n, as soon as λ ≤ p min , the ridge regression estimator satisfies with probability at least 1ε: R( f (ridge) ) -R(f * lin ) ≤ κL ε

  Finally the dependence on the confidence level is larger than expected. It contains an unusual square. The example given page 36 illustrates Theorem C.1. D. SOME STANDARD UPPER BOUNDS ON LOG-LAPLACE TRANSFORMS LEMMA D.1 Let V be a random variable almost surely bounded by b∈ R. Let g : u → exp(u) -1u /u 2 . log E exp V -E(V ) ≤ E V 2 g(b).

  u≥0 exp(|α|u) -1 -|α|u exp(-u) ≤ E exp |V | + |E(V )| sup

  almost surely. By using Lemma 3.7 (page 23) instead of Lemma 3.6 (page 23), Theorem 2.1 still holds without assuming (2.3) and (2.4), when replacing (2σ + H) 2 with

This corresponds to the convex aggregation problem, which has been widely studied by several authors since the work of Nemirovski and Judisky[START_REF] Nemirovski | Topics in nonparametric statistics. Ecole d'Eté de Probabilités de Saint-Flour XXVIII-1998[END_REF][START_REF] Juditsky | Functional aggregation for nonparametric estimation[END_REF]. This particular setting is not the topic of this paper, but our results apply to it, and correspond to the minimax optimal rate for d ≤ √ n.For d > √ n, the minimax optimal rate of convex aggregation is log(1 + d/ √ n)/n, which is not achieved by our procedure.

While the natural choice in the least squares setting is ℓ((X, Y ), f, f ′ ) = [Yf (X)] 2 -[Yf ′ (X)][START_REF] Alquier | PAC-Bayesian bounds for sparse regression estimation with exponential weights[END_REF] , we will see that for heavy-tailed outputs, it is preferable to consider the following soft-truncated version of it, up to a scaling factor λ > 0: ℓ((X, Y ), f, f ′ ) = T λ (Yf (X)) 2 -(Yf ′ (X)) 2 , with T (x) =log(1x + x 2 /2). Equality (3.4, page 16) corresponds to (2.1, page 12) with this choice of function ℓ and for the choice π * = π.