GIBBS ESTIMATORS

OLIVIER CATONI

CNRS – Université Paris 6

Abstract. We present a new type of estimator, based on ideas coming from statistical mechanics and information theory. This is a general method of adaptive statistical inference, which can be used to perform various tasks, such as density estimation, least square regression estimation and classification. It allows the simultaneous use of several models of different dimensions (or more accurately complexities), and addresses in this way the question of adaptive model selection.

1. Introducing the Gibbs estimator for density estimation and its main oracle inequality

We will outline in this paper a general purpose approach to adaptive statistical inference in which the question of density estimation plays a central role. The performance of the method will be assessed by oracle inequalities : this name has been coined by D. Donoho and I. Johnstone to denote non-asymptotic upper-bounds for the risk of an adaptive estimator, when only mild assumptions are made on the true distribution of the observed statistical sample, and when the risk is proved to be almost as small as for the best parametric estimator in a given family of parametric models.

From the technical point of view, the whole paper is built on some “abstract inference theorem” stated for “non-normalized likelihood functions”, which is stated and proved in appendix A.

Anyhow, to make things more appealing, we will describe in the first section the less general but more intuitive framework of density estimation. We will present a new adaptive method, that we named the Gibbs aggregation rule, or more shortly the Gibbs estimator, along with the main oracle inequality which provides a non asymptotic upper-bound for its risk.

In this first and central application to density estimation, the risk will be measured by the Kullback Leibler divergence between the true unknown distribution of the sample and its estimated distribution.

Date: June 25, 2001(preliminary revision, please do not circulate).

1991 Mathematics Subject Classification. Primary: 62F35, secondary: 62A10, 62B10, 94A17, 94A45.

Key words and phrases. Model selection, adaptive pattern classification, adaptive least square regression.

I would like to thank Lucien Birgé and Pascal Massart for the joint organization of a seminar on adaptive statistics which has fostered my interest for this subject. I am also grateful to Erwin Bolthausen: I completed this paper while visiting him at the University of Zürich-Irchel.

The classification and least square regression problems of the following sections could be related to the case of density estimation with respect to the Kullback divergence by considering some proper models of conditionnal distributions. Anyhow the three applications can also be derived from the “abstract” setting of appendix A, where “generalized” likelihood functions, with no probabilistic normalization, are delt with.

Since the first draft of this paper, the Gibbs estimator has been further investigated in a few other articles :

• I wrote a paper [11] dedicated to adaptive histogram estimation, and some computer code to implement the Gibbs estimator in this case, which can be downloaded from my web page at

     http://www.proba.jussieu.fr/users/catoni/homepage/homepage-en.html

• I wrote a paper [10] about “almost Gaussian” deviation inequalities, where I use the same kind of log-Laplace estimates to prove deviation inequalities. This may be of some interest to understand the proofs of the oracle inequality for the Gibbs estimator : unlike other authors dealing with other model selection methods, we do not use deviation inequalities to bound the mean risk, but, as [10] shows, we use a tool which can generate deviation inequalities, therefore it is not surprising that it can replace them.

• My student Gilles Blanchard (whose PhD was jointly supervised by Alain Trouvé) explored in [5] the use of some form of Gibbs estimator for adaptive decision trees and its relations with boosting.

• My student Jean-Philippe Vert studied the double mixture variant of the Gibbs estimator for context trees in [15]. He also proposed some improvements of the estimator for context trees in the case of a large vocabulary in [16], where experimental data about text categorization are produced. More experiments about text categorization can be found in [17].

I hope this references will convince the reader that the Gibbs estimator is not only a mathematical curiosity, but is also a practical adaptive inference method, which can be efficiently implemented in various contexts.

1.1. Mathematical framework. We set here the mathematical framework for density estimation. We use the term density estimation, because it is well established, but in fact, we do not require the true sample distribution to have a density with respect to the reference measure we consider. It is only required that the estimator has a density with respect to a given reference measure on the sample space, and weak convergence may occur to a true distribution which does not satisfy this property.

Let us start with a convenient and classical

Definition 1.1. A regular conditional probability distribution ν(dX | Y) on the product 𝒳 × 𝒴 of two measurable spaces (𝒳, ℬ) and (𝒴, ℱ) will be a map ν : ℬ × Y → ℝ such that

1. for any y ∈ Y, the map A ↦ ν(A, y) is a probability measure on (𝒳, ℬ),

2. for any A ∈ ℬ, the map y ↦ ν(A, y) is measurable with respect to ℱ.

Let (𝒳, ℬ) be a measurable sample space, and let (X_{1}, …, X_{N}) be an i.i.d. sample of observations drawn with respect to some distribution P_{N}. In practice P_{N} = P^{⊗N} ∈ ℳ_{+}^{1}(𝒳^{N}, ℬ^{⊗N}) will be a product measure, but from the technical point of view, we will only use the fact that P_{N} is the marginal of rank N of some exchangeable distribution defined on some larger power of 𝒳, 𝒳^{M}, with M > N. The question under investigation is to estimate P (or P_{M}(dX_{N+1} | X_{1}^{N}), depending on the setting). This means we want to build a regular conditional probability distribution P̂(dX | X_{1}, …, X_{N}) on (𝒳^{N+1}, ℬ^{⊗(N+1)}) which is on the average close to P (in some sense to be made more precise in the sequel).

It is well known that there is in general no answer to this question, unless we give it a more restricted meaning, because the space of all probability measures on 𝒳 is usually too big (except when 𝒳 is a small finite set). One classical way of making the question well posed would be to impose some restrictive hypotheses on the unknown distribution P. The alternative way is to impose some restrictions on the set of distributions among which the estimator is to be chosen. This is somehow more realistic, because this set is left to our choice, whereas the properties of P are in most practical cases unknown. Dealing with an unknown sample distribution within a restricted class of estimators is an active research topic in more than one scientific community, among which we can cite researches in nonparametric adaptive statistics (too many prominent contributors to cite them all), in statistical learning theory (Vapnik’s school), in information theory (Rissanen’s MDL school) and in PAC learning (Valliant, Schapire, Mansour, McAllester, ...).

Accordingly to what we just explained, we will focus on some restricted family of distributions {Q_{θ} ∈ ℳ_{+}^{1}(𝒳, ℬ) ; θ ∈ Θ}. This notation is somewhat redundent, we could, as one of the referees of this paper pointed out, have chosen to consider a subset 𝒬 ⊂ ℳ_{+}^{1}(𝒳, ℬ). Anyhow, as we will have to define a prior probability measure on the set 𝒬, and therefore a sigma-algebra on this set, we prefer to use the setting of conditional probability measures on a product space Θ × 𝒳. More precisely, we will assume that (Θ, ℬ′) is a measurable space, and that the family {Q_{θ} : θ ∈ Θ} is a regular conditional probability measure on (𝒳 × Θ, ℬ ⊗ ℬ′). We will also assume that we can find a reference measure μ ∈ ℳ_{+}^{1}(𝒳, ℬ) such that for any θ ∈ Θ, the measure Q_{θ} is absolutely continuous with respect to μ and such that there exists for each θ a version of the Radon-Nikodym derivative \frac{Q_{θ}}{μ} such that the map (θ, x) ↦ \frac{Q_{θ}}{μ} (x) is measurable with respect to the product sigma algebra ℬ′ ⊗ ℬ on Θ × 𝒳.

Another important specificity of the estimation scheme we will introduce is that the estimator P̂(dX | X_{1}, …, X_{N}) will not be chosen from the family {Q_{θ} : θ ∈ Θ} itself, but from the mixtures {∫_{θ∈Θ} Q_{θ}ρ(dθ | X_{1}, …, X_{N})}, where ρ(dθ | X_{1}, …, X_{N}) ranges among all the possible regular conditional probability distributions on Θ × 𝒳^{N}. This framework is familiar in the setting of Bayesian estimation. However, we will not use a Bayesian estimator, as the reader will see, but some pseudo-Bayesian posterior ρ which is more suited to obtain a non asymptotic oracle inequality under weak hypotheses. Understanding why it is often more efficient to estimate a posterior ρ on the parameter space rather than a given value of the parameter θ̂(X_{1}, …, X_{N}) is a deep question, on which we are still working at the time this paper is written. We produce here some toy counter example showing that there is no parameter estimator θ̂(X_{1}, …, X_{N}) achieving in all circumstances the same performance as the posterior ρ(dθ | X_{1}, …, X_{N}) we will use, but we do think that this question would deserve a more thorough exploration than what is done in this paper.

Our approach is “pseudo-Bayesian” in the sense that we use of some prior probability measure π ∈ ℳ_{+}^{1}(Θ, ℬ′) on the parameter space. However, it is to be understood that this measure has nothing to do with what our expectations might be about the true sample distribution P we are confronted with: we will obtain worst case bounds for the average risk, meaning bounds which hold for any specific value of P. The choice of π will on the other hand influence the value of the bound we will get for any particular P: changing the prior π will make the bound tighter for some values of P, while it will make it looser for other values of P.

All these preliminary explanations being given, we are ready for the definition of the Gibbs estimator:

Definition 1.2. Let π ∈ ℳ_{+}(Θ) be a positive sigma-finite measure on the parameter space Θ. Let β ∈]0, 1], α ∈]β, 1] and N ∈ ℕ be given. Let us assume that the map

(θ, x) ↦ q(θ, x) =^{def} \frac{Q_{θ}}{μ} (x)

satisfies the set of hypotheses ℋ(N + 1, β, α) given in appendix A. (Let us remind the purists that we chose once for all to work with a given realisation of the derivatives \frac{Q_{θ}}{μ}. The hypotheses of appendix A are for instance fulfilled when this

realisation is such that the function (θ, x) ↦ log (\frac{Q_{θ}}{μ} (x)) is bounded and π is a finite measure.) We define the Gibbs estimator at inverse temperature β ∈ ℝ_{+} to be the regular conditional probability distribution

G_{β}^{N}(dX | X_{1}, …, X_{N}) = \frac{𝔼_{π(dθ)} ((∏_{n=1}^{N} \frac{Q_{θ}}{μ} (X_{n}))^{β} Q_{θ}(dX))}{𝔼_{π(dθ)} ((∏_{n=1}^{N} \frac{Q_{θ}}{μ} (X_{n}))^{β})}.

The fact that it is for any (X_{1}, …, X_{N}) a probability measure is a consequence of the monotone convergence theorem. The fact that it is regular is part of Fubini’s theorem (applied separately to the numerator and denominator).

In the study of the Gibbs estimator, an important role will be played by the log-Laplace transform introduced in appendix A:

ℰ^{X_{1}^{N+1}}(α) = log 𝔼_{π(dθ)} ((∏_{n=1}^{N} \frac{Q_{θ}}{μ} (X_{n}))^{β} (\frac{Q_{θ}}{μ} (X_{N+1}))^{α}) ,

where a dummy (i.e. non observed) variable X_{N+1} has been introduced for convenience. Note also that X_{1}^{N+1} is a shorthand for (X_{1}, …, X_{N+1}). Depending on his background, the reader may also like to see the function ℰ^{X_{1}^{N}} as a free-energy function, or as the logarithm of the moment generating function of an exponential family of distributions. As it can be seen from the computations made in appendix A, computing derivatives of ℰ^{X_{1}^{N}} involves the family of posterior regular conditional distributions

ρ_{β,α}^{X_{1}^{N+1}}(dθ) = \frac{(∏_{n=1}^{N} \frac{Q_{θ}}{μ} (X_{n}))^{β} (\frac{Q_{θ}}{μ} (X_{N+1}))^{α} π(dθ)}{𝔼_{π(dθ′)} ((∏_{n=1}^{N} \frac{Q_{θ′}}{μ} (X_{n}))^{β} (\frac{Q_{θ′}}{μ} (X_{N+1}))^{α})}

on the parameter space Θ. The notation ρ_{β,α}^{X_{1}^{N+1}}(dθ) is a short hand for

ρ_{β,α}(dθ | X_{1}, …, X_{N+1}),

which will be useful to make equations fit in the page width.

Note that ρ_{β,0}^{X_{1}^{N+1}} does not depend on X_{N+1}: we will also write it as ρ_{β}^{X_{1}^{N}}. The Gibbs estimator can then be written as

G_{β}^{N}(dX_{N+1} | X_{1}, …, X_{N}) = 𝔼_{ρ_{β}^{X^{N}_{1}} (dθ)}(Q_{θ}(dX_{N+1})).

This justifies the name “Gibbs estimator”: indeed the measure ρ_{β}^{X_{1}^{N}} can be seen as a Gibbs measure, related to the hamiltonian:

h(θ; X_{1}^{N}) = −\frac{1}{N} ∑_{n=1}^{N} log (\frac{Q_{θ}}{μ} (X_{n})) ,

since it can be written as

ρ_{β}^{X_{1}^{N}} (dθ) = \frac{exp(−βNh(θ; X_{1}^{N}))π(dθ)}{𝔼_{π(dθ′)}(exp(−βNh(θ′; X_{1}^{N})))}.

(A Gibbs measure is simply a measure obtained by an exponential change of measure involving an energy function — here h(θ; X_{1}, …, X_{N}) — and an exponent called the inverse temperature — here Nβ, — from a reference measure — here π.) The normalisation given to h in this attempt to justify our terminology is quite natural since when the sample distribution is i.i.d., h will converge P^{⊗ℕ} a.s. to a finite limit from the strong law of large numbers (at least when log \frac{Q_{θ}}{μ} (X) has a first moment).

The theorems in this paper are concerned with the high temperature region β ∈]0, 1/2]. They provide oracle inequalities for the mean divergence of the true sample distribution with respect to the estimator. Namely, assuming that there exists a regular version of P (dX_{N+1} | X_{1}, …, X_{N}), they provide a bound for

𝔼_{P_{N+1}}(𝒦(P_{N+1}(dX_{N+1} | X_{1}, …, X_{N}), G_{β}^{N}(dX_{N+1} | X_{1}, …, X_{N}))),

where 𝒦 is the Kullback Leibler divergence: let us recall that the divergence 𝒦(m_{1}, m_{2}) of two probability measures m_{1} and m_{2} is defined as

𝒦(m_{1}, m_{2}) =^{def} \begin{cases}𝔼_{m_{1}} (\frac{m_{1}}{m_{2}} ) & if m_{1} ≪ m_{2} \\ +∞ & otherwise. \end{cases}

To put things into perspective, let us remark that when β = 1 the Gibbs estimator G_{1}^{N} is a Bayesian estimator: it minimizes the Bayesian risk

𝔼_{π(dθ)}𝔼_{Q_{θ}^{⊗N} (dX_{1}^{N})}(𝒦(Q_{θ}(dX_{N+1}), Q̂(dX_{N+1} | X_{1}, …, X_{N})))

over all possible choices of regular conditional probabilities Q̂(dX_{N+1} | X_{1}, …, X_{N}). Moreover, when the maximum likelihood is achieved for a single value of the parameter θ, the Gibbs estimator converges to the maximum likelihood estimator when β tends to +∞. Therefore we can see the Gibbs estimator as a “thermalized” version of both the Bayesian and the maximum likelihood estimators. Working in the high temperature region β < 1 can also be interpreted as a deliberate underestimation of the sample size: To compute the Gibbs estimator, we plug the empirical distribution of N observations into the Bayesian estimator for a sample of size βN.

The main reason for introducing the Gibbs estimator is that it satisfies a rather sharp non asymptotic oracle inequality which is the statistical pendent of the universal compression properties of universal codes in information theory.

1.2. Main oracle inequality.

Theorem 1.1. In the setting and under the hypotheses described in definition 1.2,

(1) 𝔼_{P_{N+1}} (log \frac{μ}{G_{β}^{N}} (X_{N+1} | X_{1}^{N}))

≤ inf_{θ∈Θ_{1}} \{𝔼_{P_{N+1}} (log \frac{μ}{Q_{θ}} (X_{N+1})) + \frac{γ_{β}(θ)}{β(N + 1)}\} ,

where Θ_{1} and γ_{β}(θ) are defined by equations (16) and (17) in appendix A. Moreover, according to what is assumed in defintion 1.2, the “inverse temperature” parameter β is assumed to satisfy condition (19), which itself depends on condition (18).

As a consequence, in the case when there exists a regular version of P_{N+1}(dX_{N+1} | X_{1}^{N}),

(2) 𝔼_{P_{N+1}(dX_{1}^{N})}𝒦(P_{N+1}(dX_{N+1} | X_{1}^{N}), G_{β}^{N}(dX_{N+1} | X_{1}^{N}))

≤ inf_{θ∈Θ_{1}} \{𝔼_{P_{N+1}(dX_{1}^{N})}𝒦(P_{N+1}(dX_{N+1} | X_{1}^{N}), Q_{θ}(dX_{N+1})) + \frac{γ_{β}(θ)}{β(N + 1)}\} ,

where 𝒦(., .) is the Kullback Leibler divergence.

Proof. The first part (1) is just a rewriting of theorem A.1. To prove the second part, let us remark that (2) is trivial when

inf_{θ∈Θ_{1}} 𝔼_{P_{N+1}(dX_{1}^{N})}𝒦(P_{N+1}(dX_{N+1} | X_{1}^{N}), Q_{θ}(dX_{N+1})) = +∞.

Otherwise, there is θ_{1} ∈ Θ_{1} such that

𝔼_{P_{N+1}(dX_{1}^{N})}𝒦(P_{N+1}(dX_{N+1} | X_{1}^{N}), Q_{θ_{1}}(dX_{N+1})) < +∞.

This means that

X_{1}^{N+1} ↦ log (\frac{P (dX_{N+1} | X_{1}^{N})}{Q_{θ_{1}}(dX_{N+1})}) ∈ 𝕃^{1}(𝒳^{N+1}, P_{N+1}).

Moreover by definition of Θ_{1},

X_{1}^{N+1} ↦ log (\frac{Q_{θ_{1}}(dX_{N+1})}{μ(dX_{N+1})}) ∈ 𝕃^{1}(𝒳^{N+1}, P_{N+1}).

Thus the sum of the two previous functions is also integrable :

X_{1}^{N+1} ↦ log (\frac{P_{N+1}(dX_{N+1} | X_{1}^{N})}{μ(dX_{N+1})}) ∈ 𝕃^{1}(𝒳^{N+1}, P_{N+1}),

and consequently we go from (1) to (2) by substracting on both side the finite constant

𝔼_{P_{N+1}(dX_{1}^{N+1})} [log (\frac{P_{N+1}(dX_{N+1} | X_{1}^{N})}{μ(dX_{N+1})} ∈ 𝕃^{1}(𝒳^{N+1}, P_{N+1}))] .

Remark 1.1. Note that the definition of G_{β}^{N} depends on the choice of the reference measure μ only through the assumption that for each θ, Q_{θ} is absolutely continuous with respect to μ. Replacing μ by an equivalent probability measure μ′ does not change the definition of G_{β}^{N} (by equivalent, we mean that μ ≪ μ′ and μ′ ≪ μ). However it may change the definition of Θ_{1} as well as the integrability assumption (14).

Remark 1.2. The hypotheses of the theorem are for instance fulfilled for any sample distribution P_{N+1} when π is a finite measure and the function (θ, x) ↦ log \frac{Q_{θ}}{μ} (x) is bounded. In this case Θ_{1} = Θ and the value of β can be set independently from P_{N+1} using remark A.3.

Remark 1.3. In the case of an exponential model, we can give for χ_{β,α} (see (18)), β (see (19)) and γ_{β}(θ) (see (17)) worst case upper bounds with respect to P_{N+1} which depend only on the entropy structure of the model. Let us restrict for simplicity to the case when 𝒳 is finite, and assume that {Q_{θ}; θ ∈ Θ ⊂ ℝ^{d}} is defined by

Q_{θ}(dx) = \frac{exp⟨θ, f(x)⟩}{Z(θ)}μ(dx),

where f : 𝒳 → ℝ^{d}, μ is everywhere positive, and where Θ is the support of the prior distribution π. For any values of (x_{1}, …, x_{N+1}) ∈ 𝒳^{N+1}, (β, ξ) ∈ [0, 1]^{2}, we

can define Q̂_{β,ξ}^{x_{1}^{N+1}} in the closure \overline{\{Q_{θ}; θ ∈ ℝ^{d}\}} of \{Q_{θ}; θ ∈ ℝ^{d}\} such that

𝔼_{Q̂_{β,ξ}^{x{N+1 \atop 1}} (dX)}(f(X)) = \frac{1}{βN + ξ} (∑_{i=1}^{N} βf(x_{i}) + ξf(x_{N+1})) .

It is not necessarily unique and can be obtained by minimization of the non-negative convex function

θ ⟼ 𝒦(P̂_{β,ξ}^{x_{1}^{N+1}}, Q_{θ}),

where

P̂_{β,ξ}^{x_{1}^{N}} = \frac{1}{βN + ξ} (∑_{i=1}^{N} βδ_{x_{i}} + ξδ_{x_{N+1}}) .

Then we can write ρ_{β,ξ}^{x_{1}^{N+1}}(dθ) as

ρ_{β,ξ}^{x_{1}^{N+1}}(dθ) ∝ exp (−(βN + ξ)𝒦(Q̂_{β,ξ}^{x_{1}^{N+1}}, Q_{θ})) π(dθ),

where the symbol ∝ means that we have omitted to write the normalizing constant that turns ρ_{β,ξ}^{x_{1}^{N+1}} into a probability distribution. Accordingly, we can bound γ_{β}(θ) by

sup_{θ∈Θ} γ_{β}(θ) ≤ sup_{Q̄∈\overline{\{Q_{θ} ; θ∈ℝ^{d}\}}} \frac{𝔼_{π(dθ)}[β(N + 1)𝒦(Q̄, Q_{θ}) exp(−β(N + 1)𝒦(Q̄, Q_{θ}))]}{𝔼_{π(dθ)}[β(N + 1)𝒦(Q̄, Q_{θ})]}.

In the same way, putting

ρQ̄ ; β,ξ(dθ) ∝ exp(−(βN + ξ)K(Q̄, Q_{θ}))π(dθ),

and

M_{ρ(dθ)}^{3}(g(θ)) = E_{ρ(dθ)} (g(θ) − E_{ρ(dθ′)}g(θ′))^{3} ,

we can bound χ_{β,α} by

χ_{β,α} ≤ 0 ∨ sup_{ξ∈[0,α]} sup_{Q̄∈\overline{\{Q_{θ} ; θ∈ℝ^{d}\}}} sup_{x∈𝒳} \frac{−M_{ρQ̄ ; β,ξ(dθ)}^{3} (log \frac{Q_{θ}}{μ} (x))}{Var_{ρQ̄ ; β,ξ(dθ)} (log \frac{Q_{θ}}{μ} (x))}.

In conclusion, when theorem 1.1 is applied to an exponential model {Q_{θ} : θ ∈ Θ}, the coefficients sup_{θ∈Θ} γ_{β}(θ) and χ_{β,α} corresponding to an arbitrary exchangeable sample distribution P_{N+1} can be bounded by expressions where the empirical distribution has been replaced by the worst case distribution Q̄ in the closure \overline{\{Q_{θ}; θ ∈ ℝ^{d}\}} of the larger model obtained by letting the parameter θ range in the whole ℝ^{d}.

Theorem 1.1 is concerned with values of β in the region ]0, 1/2[. Another interesting value of the temperature is β = 1/2. To cover this case, we can adopt the set of hypotheses ℋ′(N + 1, β) described in appendix B and define the third centered moment of the function h(θ) with respect to the distribution ρ ∈ ℳ_{+}^{1}(Θ) to be

M_{ρ(dθ)}^{3}h(θ) = E_{ρ(dθ)}(h(θ) − E_{ρ(dθ′)}h(θ′))^{3}.

Theorem B.1 of appendix B reads in this framework as

Theorem 1.2. In the setting described in definition 1.2, when hypothesis ℋ(N + 1, β, α) is replaced by ℋ′(N + 1, 1/2) described in appendix B,

(3) 𝔼_{P_{N+1}} [log \frac{μ}{G_{1/2}^{N}} (X_{N+1} | X_{1}^{N})]

≤ inf_{θ∈Θ_{1}} \{𝔼_{P_{N+1}} (log \frac{μ}{Q_{θ}} (X_{N+1})) + \frac{2γ(θ)}{(N + 1)}\}

+ \frac{1}{24} sup_{η∈[0,1]} −𝔼_{P_{N+1}}M_{ρ_{1/2,η}^{X{N+1 \atop 1}} (dθ)}^{3} [log (\frac{Q_{θ}}{μ} (X_{N+1}))] .

As a consequence, in the case when there exists a regular version of P (dX_{N+1} | X_{1}^{N}),

(4) 𝔼_{P_{N+1}(X_{1}^{N})}𝒦(P_{N+1}(dX_{N+1} | X_{1}^{N}), G_{1/2}^{N}(dX_{N+1} | X_{1}^{N}))

≤ inf_{θ∈Θ_{1}} \{𝔼_{P_{N+1}(dX_{1}^{N})}𝒦(P_{N+1}(dX_{N+1} | X_{1}^{N}), Q_{θ}(dX_{N+1})) + \frac{2γ_{1/2}(θ)}{N + 1}\}

+ \frac{1}{24} sup_{η∈[0,1]} −𝔼_{P_{N+1}}M_{ρ_{1/2,η}^{X{N+1 \atop 1}} (dθ)}^{3} [log (\frac{Q_{θ}}{μ} (X_{N+1}))] .

2. Checking the accuracy of the bounds on the Gaussian shift model

It is instructive to illustrate theorems 1.1 and 1.2 with the Gaussian shift model, where we can compute everything explicitly. In this exponential model 𝒳 = ℝ^{d},

μ(dx) = (2π)^{−d/2}(det H)^{−1/2} exp (−\frac{1}{2}⟨x, H^{−1}x⟩) dx

where “dx” is the Lebesgue measure on ℝ^{d} and H is a symmetric positive definite matrix, f(x) = x, so that

Q_{θ}(dx) = (2π)^{−d/2}(det H)^{−1/2} exp(−\frac{1}{2}∥H^{−1/2}(x − Hθ)∥^{2})dx,

and π(dθ) = dθ (the Lebesgue measure).

Here the relative entropy takes the form

𝒦(Q_{θ}, Q_{θ′}) = \frac{1}{2}∥H^{1/2}(θ − θ′)∥^{2}.

Moreover

γ_{β}(θ) ≤ sup_{θ̂} \frac{E_{dθ′} \frac{β(N+1)}{2}∥H^{1/2}(θ′ − θ)∥^{2} exp(−\frac{β(N+1)}{2}∥H^{1/2}(θ′ − θ̂)∥^{2})}{E_{dθ′} exp(−\frac{β(N+1)}{2}∥H^{1/2}(θ′ − θ̂)∥^{2})}

− \frac{β(N + 1)}{2}∥H^{1/2}(θ̂ − θ)∥^{2} = \frac{d}{2}.

We have also

ρ_{β,ξ}^{x_{1}^{(}N+1)}(dθ) = (\frac{βN + ξ}{2π} )^{d/2} (det H)^{1/2} exp (−\frac{βN + ξ}{2} ∥H^{1/2}(θ − θ̄_{β,ξ})∥^{2}) dθ,

where

θ̄_{β,ξ} = H^{−1} (\frac{1}{βN + ξ} (∑_{i=1}^{N} βx_{i} + ξx_{N+1})) .

Making the computation in a orthonormal basis of eigenvectors of H, we obtain easily that

Var_{ρ_{β,ξ}^{x{N+1 \atop 1}} (dθ)} [log (\frac{Q_{θ}}{μ} (x_{N+1}))] = Var_{ρ_{β,ξ}^{x{N+1 \atop 1}} (dθ)} [−\frac{1}{2}∥H^{−1/2}(x_{N+1} − Hθ)∥^{2}]

= (βN + ξ)^{−2} (\frac{d}{2} + (βN + ξ)∥H^{−1/2}(x_{N+1} − Hθ̄_{β,ξ})∥^{2}) ,

M_{ρ_{β,ξ}^{x{N+1 \atop 1}} (dθ)}^{3} [log (\frac{Q_{θ}}{μ} (x_{N+1}))] = M_{ρ_{β,ξ}^{x{N+1 \atop 1}} (dθ)}^{3} [−\frac{1}{2}∥H^{−1/2}(x_{N+1} − Hθ)∥^{2}]

= −(βN + ξ)^{−3} (d + 3(βN + ξ)∥H^{−1/2}(x_{N+1} − Hθ̄_{β,ξ})∥^{2}) .

Thus χ_{β,1} ≤ \frac{3}{βN} and for N > 9 we can take in theorem 1.1

β = \frac{1}{2} − \frac{1}{N + 1}.

We obtain that

E_{P_{N+1}}𝒦(P_{N+1}(dX_{N+1} | X_{1}^{N}), G_{1/2−1/(N+1)}(dX_{N+1} | X_{1}^{N}))

≤ inf_{θ∈Θ} E_{P_{N+1}}𝒦(P (dX_{N+1} | X_{1}^{N}), Q_{θ}(dX_{N+1})) + \frac{d}{N + 1} (1 − \frac{2}{N + 1})^{−1} .

In the case when P_{N+1} = P^{⊗(N+1)} is a product measure having a second moment E_{P} (∥X∥^{2}) < +∞,

E_{P^{⊗(N+1)}}∥H^{−1/2}(X_{N+1} − Hθ̄_{β,ξ})∥^{2}

= E_{P} ∥H^{−1/2}(X − E_{P} (X))∥^{2} ((1 − \frac{ξ}{βN + ξ} )^{2} + \frac{β^{2}N}{(βN + ξ)^{2}} )

≤ \frac{N + 1}{N}E_{P} ∥H^{−1/2}(X − E_{P} (X))∥^{2}.

Therefore applying theorem 1.2 we obtain that

E_{P^{⊗N} (dX_{1}^{N})}𝒦(P, G_{1/2}^{N}(dX_{N+1} | X_{1}^{N}))

≤ inf_{θ∈Θ} 𝒦(P, Q_{θ}) + \frac{d}{N + 1}

+ \frac{N + 1}{2N^{3}}E_{P} ∥H^{−1/2}(X − E_{P} (X))∥^{2} + \frac{d}{3N^{3}}

As in this case G_{β}^{N}(dX_{N+1} | X_{1}^{N}) can be explicitly computed, we can check to which extent theorems 1.1 and 1.2 are sharp for the Gaussian shift model: putting

θ̄ = H^{−1} (\frac{1}{N} ∑_{i=1}^{N} x_{i})

we have

G_{β}^{N}(dx_{N+1} | x_{1}^{N}) = E_{ρ_{β,0}^{x{N+1 \atop 1}} (dθ)}Q_{θ}(dx_{N+1})

= ∫_{θ∈ℝ^{d}} (\frac{βN}{2π} )^{d/2} (det H)^{1/2} exp (−\frac{βN}{2} ∥H^{1/2}(θ − θ̄)∥^{2})

× (2π)^{−d/2}(det H)^{−1/2} exp (−\frac{1}{2}∥H^{−1/2}(x_{N+1} − Hθ)∥^{2}) dθdx_{N+1}

= ∫_{θ} (\frac{βN}{(2π)^{2}} )^{d/2} exp (−\frac{βN + 1}{2}∥H^{1/2}(θ − θ̄)∥^{2}

+⟨(x_{N+1} − Hθ̄), (θ − θ̄)⟩ − \frac{1}{2}∥H^{−1/2}(x_{N+1} − Hθ̄)∥^{2}) dθdx_{N+1}

= (2π)^{−d/2}(det H)^{−1/2} (\frac{βN}{βN + 1})^{d/2}

× exp (−\frac{1}{2} \frac{βN}{βN + 1}∥H^{−1/2} (x_{N+1} − \frac{1}{N} ∑_{i=1}^{N} x_{i}) ∥^{2}) dx_{N+1}.

We can then explicitly compute

sup_{θ} E_{P^{⊗(N+1)}(dX_{1}^{N+1})} [log (\frac{Q_{θ}(dX_{N+1})}{G_{β}^{N}(dX_{N+1} | X_{1}^{N})})]

= \frac{d}{2} log \frac{βN + 1}{βN}

+ \frac{1}{2} \frac{βN}{βN + 1}E_{P^{⊗(N+1)}(dX_{1}^{N+1})}∥H^{−1/2} (X_{N+1} − \frac{1}{N} ∑_{i=1}^{N} X_{i}) ∥^{2}

− inf_{θ} \frac{1}{2}E_{P (dX_{N+1})}∥H^{−1/2}(X_{N+1} − Hθ)∥^{2}

= \frac{d}{2} log (1 + \frac{1}{βN} )

− \frac{1 − β}{2(βN + 1)}E_{P (dX_{N+1})}∥H^{−1/2}(X_{N+1} − E_{P} (X))∥^{2}.

This shows that in case β = 1/2 − 1/(N + 1) the evaluation given by theorem 1.1 is sharp for the worst P (the case when its variance is going to zero). In theorem 1.2 the leading term is also sharp in the worst case. It is also interesting to notice that the average risk of the Bayesian estimator Q_{1}^{N+1} is independent of P and that G_{β}^{N+1} is asymptotically minimax when the sample distribution P is supposed to be drawn from the model {Q_{θ}; θ ∈ Θ} for any β ∈]0, 1]. Indeed, the choice of β does not influence the prediction made for the mean of P. This is a good thing, because in some situations it is necessary to make a “pessimistic” choice of β to meet the hypotheses of theorem 1.1, and it is hopeful that such a pessimistic choice would not systematically prevent the estimator from having an optimal behaviour. In the case when P ∉ {Q_{θ}; θ ∈ Θ}, smaller values of β do a better job when the variance of P is larger than in the model and larger values of β do a better job when the variance of P is smaller than in the model.

These easy computations made on the Gaussian shift model can be expected to be typical of more general exponential models in which, under broad conditions, θ will be asymptotically normal under ρ_{β,γ}^{X_{1}^{N+1}}(dθ), given X_{1}, …, X_{N+1}.

We would like now to illustrate the use of theorem 1.1 in a totally different completely discrete setting.

3. Application to adaptive classification

In this application to classification, we consider a product space (𝒳×𝒴, ℬ_{1} ⊗ℬ_{2}), where 𝒴 is a finite set with C elements and ℬ_{2} is the discrete sigma algebra. We let {f_{θ} : 𝒳 → 𝒴; θ ∈ Θ} be a family of classification rules. Our goal is to find a classification rule f : 𝒳 → 𝒴 which minimizes the error of classification P (f(X) ≠ Y), for some probability measure P ∈ ℳ_{+}^{1}(𝒳 × 𝒴), which we know through the observation of an i.i.d. sample of classified patterns (X_{i}, Y_{i})_{i=1}^{N} distributed according to P^{⊗N}.

We introduce the family of conditional “non-normalised” likelihood functions

q_{θ}(y | x) = exp(−λ1(f_{θ}(x) ≠ y)),

where λ ∈]0, 1[ is a fixed constant (to be optimized later on). We have

−E_{P} log q_{θ}(Y | X) = λP (f_{θ}(X) ≠ Y).

Applying theorem A.1 of appendix A to q_{θ}(y | x), noticing that in this situation χ_{β,α} ≤ λ (for any values of β and α), we obtain that

(5) − E_{P^{⊗N}} log g_{β}^{N}(Y_{N+1} | X_{N+1})

≤ inf_{θ∈Θ} (−E_{P^{⊗(N+1)}} log q_{θ}(Y_{N+1} | X_{N+1}) − \frac{1 + exp λ/2}{N} log π(\{θ\})) ,

where

g_{β}^{N}(Y_{N+1} | X_{N+1}) = \frac{𝔼_{π(dθ)} [(∏_{i=1}^{N} q_{θ}(Y_{i} | X_{i}))^{β} q_{θ}(Y_{N+1} | X_{N+1})]}{𝔼_{π(dθ)} [(∏_{i=1}^{N} q_{θ}(Y_{i} | X_{i}))^{β}]},

with β = \frac{1}{1 + exp(λ/2)}.

From this main inequality, we are going to derive four different results. One is concerned with a randomised classification rule in the general case, the second one is concerned with the performance of the same classification rule in the case when it is known that the conditional distribution of the classes is sufficiently far from the uniform distribution, the last two results are concerned with the derivation of a non randomised classification rule.

3.1. Randomised classification rule, general case. Let us define a notation for the posterior probability distribution associated with the Gibbs estimator :

ρ_{β}(dθ) ∝^{def} (∏_{i=1}^{N} q_{θ}(Y_{i} | X_{i}))^{β} π(dθ).

We can see that

− log g_{β}^{N}(Y_{N+1} | X_{N+1}) = − log 𝔼_{ρ_{β}(dθ)}q_{θ}(Y_{N+1} | X_{N+1})
= − log[𝔼_{ρ_{β}(dθ)} exp(−λ𝟙(f_{θ}(X_{N+1}) ≠ Y_{N+1}))]
= − log[1 − (1 − e^{−λ})𝔼_{ρ_{β}(dθ)}[𝟙(f_{θ}(X_{N+1}) ≠ Y_{N+1})]]
≥ (1 − e^{−λ})𝔼_{ρ_{β}(dθ)}[𝟙(f_{θ}(X_{N+1}) ≠ Y_{N+1})].

This proves

Theorem 3.1.

𝔼_{P^{⊗N} (dZ_{1}^{N})}𝔼_{ρ_{β}(dθ)}P (f_{θ}(X_{N+1}) ≠ Y_{N+1})

≤ inf_{θ∈Θ} (\frac{λ}{1 − e^{−λ}} P (f_{θ}(X_{N+1}) ≠ Y_{N+1}) − \frac{1 + e^{λ/2}}{1 − e^{−λ}} \frac{log π(\{θ\})}{N + 1}) .

3.2. Randomised classification rule for “non-ambiguous” classification problems. We will see further below that the order of the bound obtained in theorem 3.1 is optimal in the general case. However, another type of result can be obtained when the classification problem is not too ambiguous in the following

GIBBS ESTIMATORS 13

sense : Assuming that we have chosen some regular version of P (dY | X), let us consider an “ideal” classification rule f̃: 𝒳 → 𝒴, such that

P (Y = f̃(x) | X = x) = max_{y∈𝒴}P (Y = y | X = x), x ∈ 𝒳.

Let us introduce for any x ∈ 𝒳 the notation

μ_{x} = min_{y∈𝒴\{f̃(x)}}[P (Y = f̃(x) | X = x) − P (Y = y | X = x)].

Assume for the moment that the value of the observation (X_{1}, Y_{1}), …, (X_{N}, Y_{N}) is fixed, so that ρ(dθ) is fixed, and remark that for any x ∈ 𝒳

(6) − 𝔼_{P (dY | X=x)}{log[𝔼_{ρ(dθ)}{exp[−λ(𝟙(Y ≠ f_{θ}(X)) − 𝟙(Y ≠ f̃(X)))]}]}

≥ 𝔼_{P (dY | X=x)}𝔼_{ρ(dθ)}[−(e^{λ} − 1)𝟙(Y = f_{θ}(X) and Y ≠ f̃(X))

+ (1 − e^{−λ})𝟙(Y ≠ f_{θ}(X) and Y = f̃(X))]

≥ 𝔼_{ρ(dθ)}[(1 − e^{−λ})(P (Y ≠ f_{θ}(X) | X = x) − P ((Y ≠ f̃(X) | X = x))

− (e^{λ} − 1)(1 − e^{−λ})P (Y = f_{θ}(X) and Y ≠ f̃(X) | X = x)]

As moreover

P (Y = f_{θ}(X) and Y ≠ f̃(X) | X = x)] ≤ \frac{1 − μ_{x}}{2} 𝟙(f_{θ}(X) ≠ f̃(X))

and

P (Y ≠ f_{θ}(X) | X = x) − P (Y ≠ f̃(X) | X = x) ≥ μ_{x}𝟙(f_{θ}(X) ≠ f̃(X)),

it is necessarily true that

P (Y = f_{θ}(X) and Y ≠ f̃(X) | X = x)]

≤ \frac{(1 − μ_{x})}{2μ_{x}}[P (Y ≠ f_{θ}(X) | X = x) − P (Y ≠ f̃(X) | X = x)].

Comming back to (6) we obtain

(7) − 𝔼_{P (dY | X=x)}{log[𝔼_{ρ(dθ)}{exp[−λ(𝟙(Y ≠ f_{θ}(X)) − 𝟙(Y ≠ f̃(X)))]}]}

≥ 𝔼_{ρ(dθ)}[(1 − e^{−λ}) (1 − \frac{1 − μ_{x}}{2μ_{x}} (e^{λ} − 1)) (P (Y ≠ f_{θ}(X) | X = x)

− P ((Y ≠ f̃(X) | X = x))].

14 O. CATONI

This will be useful when μ_{x} is not too small. For small values of μ_{x}, we would better use the bound established in the “general” case, which can be written as (8) − 𝔼_{P (dY | X=x)}{log[𝔼_{ρ(dθ)}{exp[−λ(𝟙(Y ≠ f_{θ}(X)) − 𝟙(Y ≠ f̃(X)))]}]}

≥ (1 − e^{−λ})𝔼_{ρ(dθ)}[P (Y ≠ f_{θ}(X) | X = x) − P (Y ≠ f̃(X) | X = x)]

− (λ − 1 + e^{−λ})P (Y ≠ f̃(X) | X = x)

≥ (1 − e^{−λ})𝔼_{ρ(dθ)}[P (Y ≠ f_{θ}(X) | X = x) − P (Y ≠ f̃(X) | X = x)]

− \frac{1}{2}(λ − 1 + e^{−λ}).

Let us define for any real positive constant μ the set

Ω_{μ} =^{def} {x ∈ 𝒳 : P (Y = f̃(x) | X = x) < max_{z∈𝒴\{f̃(x)}} P (Y = z | X = x) + μ}.

Combining equations (7) and (8), we get

(9) − 𝔼_{P (dX,dY)}{log[𝔼_{ρ(dθ)}{exp[−λ(𝟙(Y ≠ f_{θ}(X)) − 𝟙(Y ≠ f̃(X)))]}]}

≥ 𝔼_{ρ(dθ)}[(1 − e^{−λ}) (1 − \frac{1 − μ}{2μ}(e^{λ} − 1)) (P (Y ≠ f_{θ}(X))

− P ((Y ≠ f̃(X)))] − (λ − 1 + e^{−λ})\frac{P (Ω_{μ})}{2}.

This proves the following theorem : Theorem 3.2. In the setting described above,

𝔼_{P^{⊗N} (dZ_{1}^{N})}{𝔼_{ρ_{β}(dθ)}[P (f_{θ}(X_{N+1}) ≠ Y_{N+1})]} ≤ P (f̃(X_{N+1}) ≠ Y_{N+1})

+ inf_{θ∈Θ}\{C_{1}(λ, μ)(P (f_{θ}(X_{N+1}) ≠ Y_{N+1})−P (f̃(X_{N+1}) ≠ Y_{N+1}))−C_{2}(λ, μ)\frac{log(π(θ))}{(N + 1)}\}

+ C_{3}(λ, μ)

where

C_{1}(λ) = \frac{λ}{1 − e^{−λ}} (1 − \frac{1 − μ}{2μ}(e^{λ} − 1))^{−1} ,
C_{2}(λ) = \frac{(1 + e^{λ/2})}{(1 − e^{−λ})} (1 − \frac{1 − μ}{2μ}(e^{λ} − 1))^{−1} ,
C_{3}(λ) = \frac{λ − 1 + e^{−λ}}{1 − e^{−λ}} (1 − \frac{1 − μ}{2μ}(e^{λ} − 1))^{−1} \frac{P (Ω_{μ})}{2}.

Remark 3.1. Note that for any fixed value of μ ∈]0, 1[,

C_{1}(λ, μ) ∼_{λ↓0} 1,
C_{2}(λ, μ) ∼_{λ↓0} \frac{2}{λ},
C_{3}(λ, μ) ∼_{λ↓0} \frac{λP (Ω_{μ})}{4}.

Remark 3.2. In the case when • the best classification rule is achieved : f̃ = f_{θ_{0}} for some value θ_{0} ∈ Θ,

• the classification problem is not ambiguous in the sense that P (Ω_{μ}) = 0 for

some positive value of μ, then the Gibbs estimator achieves the best possible classification rate up to an additive loss factor of order 1/N.

3.3. Deterministic classification rule. If we want a non random classification rule, we can take

f̂_{β}(x) = arg max_{y} 𝔼_{ρ_{β}(dθ)}[1(f_{θ}(x) = y)].

As 𝔼_{ρ_{β}(dθ)}δ_{f_{θ}(X_{N+1})}(dY_{N+1}) ≤ 1/2 when f̂_{β}(X_{N+1}) ≠ Y_{N+1}, we get

𝔼_{ρ_{β}(dθ)}[1(f_{θ}(X_{N+1}) ≠ Y_{N+1})] = \frac{1}{2}E_{ρ_{β}(dθ)}∥δ_{f_{θ}(X_{N+1})} − δ_{Y_{N+1}}∥_{Var}

≥ \frac{1}{2}∥E_{ρ_{β}(dθ)}δ_{f_{θ}(X_{N+1})} − δ_{Y_{N+1}}∥_{Var}

≥ \frac{1}{2}1(f̂_{β}(X_{N+1}) ≠ Y_{N+1}),

and therefore

− log(g_{β}^{N}(Y_{N+1} | X_{N+1})) ≥ − log (1 − \frac{1}{2}(1 − e^{−λ})1(f̂_{β}(X_{N+1}) ≠ Y_{N+1}))

= −1(f̂_{β}(X_{N+1}) ≠ Y_{N+1}) log (1 − \frac{1}{2}(1 − e^{−λ})) .

Thus

Proposition 3.1. The deterministic classification rule f̂_{β} defined above satisfies

P^{⊗(N+1)}(f̂_{β}(X_{N+1}) ≠ Y_{N+1})

≤ inf_{θ} (log \frac{2}{1 + e^{−λ}} )^{−1} (λP (f_{θ}(X_{N+1}) ≠ Y_{N+1}) − \frac{(1 + e^{λ/2}) log π(\{θ\})}{N + 1}) .

In the case of a “non-ambiguous” classification problem, it is also possible to establish an oracle inequality for the deterministic classification rule f̂. we can remark that for any x ∈ 𝒳,

𝔼_{ρ(dθ)}[P (f̃(x) = Y | X = x) − P (f_{θ}(x) = Y | X = x)]

≥ μ_{x}𝔼_{ρ(dθ)}[𝟙(f̃(x) ≠ f_{θ}(x))]

≥ \frac{μ_{x}}{2} 𝟙(f̂(x) ≠ f̃(x))

≥ \frac{μ_{x}}{1 + μ_{x}} [P (f̃(x) = Y | X = x)

− P (f̂(x) = Y | X = x)].

The last inequality is due to the fact that

2P (f̃(x) = Y | X = x) − μ_{x} ≤ 1.

16 O. CATONI

Thus

P (Y ≠ f̂(X) | X = x) − P (Y ≠ f̃(X) | X = x)

≤ \frac{1 + μ_{x}}{μ_{x}} 𝔼_{ρ(dθ)}[P (Y ≠ f_{θ}(X) | X = x) − P (Y ≠ f̃(X) | X = x)]

≤ −\frac{1 + μ_{x}}{μ_{x}} (1 − e^{−λ})^{−1} (1 − \frac{1 − μ_{x}}{2μ_{x}} (e^{λ} − 1))^{−1}

× 𝔼_{P (dY | X=x)} log 𝔼_{ρ(dθ)}{exp(−λ[𝟙(Y ≠ f_{θ}(X)) − 𝟙(Y ≠ f̃(X))])}.

We will use this chain of inequalities when x ∉ Ω_{μ}. When x ∈ Ω_{μ}, we will use the general case inequality

P (Y ≠ f̂(X) | X = x) − P (Y ≠ f̃(X) | X = x)

≤ 2𝔼_{ρ(dθ)}[P (Y ≠ f_{θ} | X = x)] − P (Y ≠ f̃(X) | X = x)

≤ −\frac{2}{1 − e^{−λ}} log\{𝔼_{ρ(dθ)} exp[−λ𝟙(Y ≠ f_{θ}(X)]\} − P (Y ≠ f̃(X) | X = x)

≤ −\frac{2}{1 − e^{−λ}} log\{𝔼_{ρ(dθ)} exp[−λ𝟙(Y ≠ f_{θ}(X) − 𝟙(Y ≠ f̃(X))]\}

+ (\frac{2λ}{1 − e^{−λ}} − 1) P (Y ≠ f̃(X) | X = x).

Combining the two last equations proves a new theorem about the deterministic aggregation rule f̂. Theorem 3.3. In the setting described above,

P (f̂X_{N+1}) ≠ Y_{N+1}) ≤ P (f̃(X_{N+1}) ≠ Y_{N+1})

+ inf_{θ∈Θ}{C_{1}(λ, μ)[P (f_{θ}(X_{N+1}) ≠ Y_{N+1}) − P (f̃(X_{N+1}) ≠ Y_{N+1})]

− C_{2}(λ, μ)\frac{log(π(θ))}{(N + 1)}\} + C_{3}(λ, μ)

where

C_{1}(λ) = \frac{1 + μ}{μ} \frac{λ}{1 − e^{−λ}} (1 − \frac{1 − μ}{2μ}(e^{λ} − 1))^{−1} ,
C_{2}(λ) = \frac{1 + μ}{μ} \frac{(1 + e^{λ/2})}{(1 − e^{−λ})} (1 − \frac{1 − μ}{2μ}(e^{λ} − 1))^{−1} ,
C_{3}(λ) = (\frac{2λ}{1 − e^{−λ}} − 1) P (Ω_{μ}).

Remark 3.3. Note that for any fixed value of μ ∈]0, 1[,

C_{1}(λ, μ) ∼_{λ↓0} \frac{1 + μ}{μ},
C_{2}(λ, μ) ∼_{λ↓0} \frac{2(1 + μ)}{μ λ},
C_{3}(λ, μ) ∼_{λ↓0} P (Ω_{μ}).

Remark 3.4. Here again, when P (Ω_{μ}) = 0 for some value of μ and f̃ = f_{θ_{0}} for some θ_{0} ∈ Θ, then the optimal probability of error P (Y ≠ f̃(X)) can be reached at spead 1/N.

3.4. Counter example. It is easy to build a counter example in which, for some positive constant A and for any (randomized or not) estimator f̂,

sup_{P} \{P^{⊗(N+1)}(f̂(X_{N+1}) ≠ Y_{N+1}) − inf_{θ∈Θ} P (f_{θ}(X_{N+1}) ≠ Y_{N+1})\} ≥ \frac{A}{\sqrt{N}} .

Take for example 𝒳 = {x} to be a one point set, 𝒴 = {0, 1} and consider the two sample distributions \{P_{i}^{⊗N} ; i ∈ \{−1, +1\}\}, where P_{i}(x, 0) = \frac{1}{2} + \frac{iα}{\sqrt{N}} = 1−P_{i}(x, 1), Θ = {0, 1} and f_{θ}(x) = θ. Then

max_{i∈{−1,+1}}{P_{i}^{⊗(N+1)}(f̂ ≠ Y_{N+1}) − min_{θ∈Θ} P_{i}(f_{θ} ≠ Y_{N+1})}

= max_{i∈\{−1,+1\}} \frac{2α}{\sqrt{N}} P_{i}^{⊗N}(f̂ ≠ i)

≥ \frac{α}{\sqrt{N}} ∑_{i∈\{−1,+1\}} P_{i}^{⊗N}(f̂ ≠ i)

≥ \frac{α}{\sqrt{N}} ∑_{y_{1}^{N} ∈\{+1,−1\}^{N}} min_{i∈\{−1,+1\}} P_{i}^{⊗N}(y_{1}^{N})

= \frac{α}{\sqrt{N}} (1 − \frac{1}{2} ∥P_{+1}^{⊗N} − P_{−1}^{⊗N} ∥)

Moreover, according to Pinsker’s inequality

\frac{1}{2}∥P_{+1}^{⊗N} − P_{−1}^{⊗N}∥^{2} ≤ 𝒦(P_{+1}^{⊗N}, P_{−1}^{⊗N})

= N𝒦(P_{+1}, P_{−1})

= 2α\sqrt{N} log (1 + \frac{2α}{\sqrt{N} (1 − \frac{α}{\sqrt{N}} )})

≤ \frac{4α^{2}}{1 − \frac{α}{\sqrt{N}}} .

Therefore for any α < 1/2, there is a constant A, independent of N, such that

inf_{f̂} sup_{i} (P_{i}^{⊗(N+1)}(f̂ ≠ Y_{N+1}) − inf_{θ∈Θ} P_{i}(f_{θ} ≠ Y_{N+1})) ≥ \frac{A}{\sqrt{N}} .

On the other hand if we take λ = 1/\sqrt{N} in theorem 3.1, we get that

𝔼_{P^{⊗N}} [𝔼_{ρ_{β}(dθ)}1(f_{θ} ≠ Y_{N+1})]

≤ inf_{θ∈Θ} (1 + \frac{1}{2\sqrt{N}} ) P_{N}(f_{θ} ≠ Y_{N+1}) − \frac{2 log π(\{θ\})}{\sqrt{N}} + 𝒪 (\frac{1}{N} ) .

This shows that, when inf_{θ} P (f_{θ}(X_{N+1}) ≠ Y_{N+1}) is of order one a randomized classification with λ of order 1/\sqrt{N} is almost as good as the best f_{θ} in the sense that the supplementary error rate is of the optimal order 1/\sqrt{N}.

When inf_{θ} P (f_{θ}(X_{N+1}) ≠ Y_{N+1}) is of order 1/N, we should take λ of order 1, and we can build a deterministic adaptive classification rule with a probability of error of order 1/N.

4. Two stage adaptive least square regression

Let us consider a product space (𝒳 × 𝒴, ℬ_{1} ⊗ ℬ_{2}) where 𝒴 = ℝ^{D} and ℬ_{2} is the Borel sigma algebra. Let { f_{m}^{K} : 𝒳 × (𝒳 × 𝒴)^{K} → 𝒴; m ∈ M , K ∈ ℕ } be a countable family of regression estimators. We would like to select the “best” regression estimator according to the quadratic criterion

𝔼_{P_{N}} ∥Y_{K+1} − f_{m}^{K}(X_{K+1} ; Z_{1}^{K})∥^{2}

where P_{N} ∈ ℳ_{+}^{1}((𝒳 × 𝒴)^{N}, (ℬ_{1} ⊗ ℬ_{2})^{⊗N}) is some exchangeable distribution and where Z_{1}^{K} = {(X_{i}, Y_{i}) ; 1 ≤ i ≤ K} is the observation.

We will assume that Y_{K+1} − f_{m}^{K}(X_{K+1} ; Z_{1}^{K}) is P_{N} almost surely bounded by some constant B:

sup_{m∈M} ∥Y_{K+1} − f_{m}^{K}(X_{K+1} ; Z_{1}^{K})∥ ≤ B, P_{N} a.s.

We will use a two stage scheme based on theorem 1.1. We consider an observation vector (Z_{1}^{N}) which we split into (Z_{1}^{K}) and (Z_{K+1}^{N}). We use the Gaussian shift model

Q_{m}^{K}(dY_{K+1} | X_{K+1} ; Z_{1}^{K}) = (\frac{λ}{2π} )^{D/2} exp (−\frac{λ}{2}∥Y_{K+1} − f_{m}^{K}(X_{K+1} ; Z_{1}^{K})∥^{2}) dY_{K+1},

where dY_{K+1} is the Lebesgue measure on ℝ^{D}. We extract from this model the non-normalized likelihood function :

q_{m}(Y_{i} | X_{i}; Z_{1}^{K}) = exp (−\frac{λ}{2}∥Y_{i} − f_{m}^{K}(X_{i})∥^{2}) .

(We could have kept the normalization, but it will be simpler to drop it, since we will not need it in the following application of theorem A.1.) We form the Gibbs estimator

g_{β}^{N}(Y_{N+1} | X_{N+1} ; Z_{1}^{N})

=^{def} \frac{𝔼_{π(dm)} [( ∏_{i=K+1}^{N} q_{m}^{K}(Y_{i} | X_{i}; Z_{1}^{K}))^{β} q_{m}^{K}(Y_{N+1} | X_{N+1} ; Z_{1}^{K})]}{𝔼_{π(dm)} [( ∏_{i=K+1}^{N} q_{m}^{K}(Y_{i} | X_{i}; Z_{1}^{K}))^{β}]},

where π ∈ ℳ_{+}^{1}(M) is some prior probability distribution. Applying theorem 1.1 we get

𝔼_{P_{N+1}} log g_{β}^{N}(Y_{N+1} | X_{N+1} ; Z_{1}^{N})

≥ sup_{m∈M} (𝔼_{P_{N+1}(dZ_{1}^{N+1})}[log q_{m}^{N}(Y_{N+1} | X_{N+1} ; Z_{1}^{K})] − \frac{log π(\{m\})}{β(N − K + 1)}) ,

GIBBS ESTIMATORS 19

when β = (1 + exp(\frac{λB^{2}}{4} ))^{−1}. On the other hand

log g_{β}^{N}(Y_{N+1} | X_{N+1} ; Z_{1}^{N})

= \frac{D}{2} log (\frac{λ}{2π} ) + log \{𝔼_{ρ(dm)} [exp (−\frac{λ}{2}∥Y_{N+1} − f_{m}(X_{N+1} ; Z_{1}^{K})∥^{2})]\} ,

where

ρ(dm) ∝ ( ∏_{i=K+1}^{N} q_{m}^{K}(Y_{i} | X_{i}; Z_{1}^{K}))^{β} π(dm).

Choosing λ = B^{−2}, and using the fact that the Gaussian function

y ⟼ exp (−\frac{1}{2}∥y∥^{2})

is concave in the unit ball of ℝ^{D}, we get that

− log \{𝔼_{ρ(dm)} [exp (−\frac{λ}{2}∥Y_{N+1} − f_{m}^{K}(X_{N+1} ; Z_{1}^{K})∥^{2})]\}

≥ \frac{λ}{2}∥Y_{N+1} − 𝔼_{ρ(dm)}f_{m}^{K}(X_{N+1} ; Z_{1}^{N})∥^{2}.

This proves the following Theorem 4.1. With the previous notations and the choice of parameters

λ = B^{−2},
β = (1 + e^{1/4})^{−1},

we get

𝔼_{P_{N+1}}∥Y_{N+1} − 𝔼_{ρ(dm)}f_{m}^{K}(X_{N+1} ; Z_{1}^{K})∥^{2}

≤ inf_{m∈M} (𝔼_{P_{N+1}}∥Y_{N+1} − f_{m}^{K}(X_{N+1} ; Z_{1}^{K})∥^{2} − \frac{2B^{2}(1 + e^{1/4})}{(N − K + 1)} log π(\{m\})) .

Remark 4.1. If we know only that

∥Y_{N+1}∥ ≤ B, P_{N+1} a.s.

then we should force f_{m}^{K}(X_{N+1} ; Z_{1}^{K}) to be bounded, using

f̃_{m}^{K}(X_{N+1} ; Z_{1}^{K}) = T_{B}(f_{m}^{K}(X_{N+1} ; Z_{1}^{K})),

where

T_{B}(y) = \begin{cases}y & if ∥y∥ ≤ B, \\ \frac{B}{∥y∥}y & otherwise. \end{cases}

As we have in this situation

𝔼_{P_{N+1}}∥Y_{N+1} − f̃_{m}^{K}(X_{N+1} ; Z_{1}^{K})∥^{2} ≤ 𝔼_{P_{N+1}}∥Y_{N+1} − f_{m}^{K}(X_{N+1} ; Z_{1}^{K})∥^{2} this truncation operation will always improve the estimator.

Remark 4.2. Using the progressive mixture estimator posterior distribution (see [8])

ρ̃(dm) = \frac{1}{N − K + 1} ∑_{M=K+1}^{N+1} \frac{∏_{i=M}^{N} q_{m}^{K}(Y_{i} | X_{i}; Z_{1}^{K})π(dm)}{𝔼_{π(dm′)} ∏_{i=M}^{N} q_{m′}^{K}(Y_{i} | X_{i}; Z_{1}^{K})}, (10)

we would have obtained the sharper result

𝔼_{P_{N+1}}∥Y_{N+1} − 𝔼_{ρ̃(dm)}f_{m}^{K}(X_{N+1} ; Z_{1}^{K})∥^{2}

≤ inf_{m∈M} (𝔼_{P_{N+1}}∥Y_{N+1} − f_{m}^{K}(X_{N+1} ; Z_{1}^{K})∥^{2} − \frac{2B^{2}}{N − K + 1} log π(\{m\})) .

With the Gibbs estimator we loose a factor 1 + e^{1/4}. Nevertheless, we think that the Gibbs estimator can be preferred to the progressive mixture estimator in many circumstances for at least three reasons:

• It can be computed faster than the progressive mixture estimator. Indeed, as shown in equation (10), the progressive mixture estimator is a Cesaro mean of N −K +1 terms, the last one having the same form as the Gibbs estimator, except for the introduction of the β exponent.

• As we explained in the first section, the Gibbs posterior distribution ρ(dm) is a Gibbs distribution at temperature βN. Therefore we can expect that it will be as a rule sharply peaked around only a few values of m ∈ M. Therefore, although the Gibbs estimator appears at first sight as a combination of all the regression models, it will in practice perform a selection, because the majority of the weights ρ(dm) will be small with respect to 1/N, which is the required precision to preserve the quality of approximation stated in the theorem. This is not the case for the progressive mixture estimator : indeed the first term in equation (10) is the “flat” distribution π(dm)/(N − K + 1), which gives comparable weights of orfer 1/N to all the regression models.

• The Gibbs estimator is “almost” the Bayesian estimator corresponding to the prior distribution π(dm), therefore in the case when we expect the conditional mean 𝔼_{P_{N+1}}(Y_{N+1} | X_{N+1} ; Z_{1}^{N}) to be close to f_{m}^{K}(X_{N+1} ; Z_{1}^{K}) with probability π(m), but we are not completely sure of this guess and want a robust estimator, this is a good incitation to use the Gibbs estimator, which appears as a “cautious” variant of the Bayes estimator.

Remark 4.3. It would be impossible to obtain the same kind of result with a true selection rule (a rule which would select only one m as opposed to a convex combination of several f_{m}^{K}). The counter example given in the previous section about classification applies to quadratic regression. We can also modify this example to make it look more like a regression problem.

Indeed, let 𝒳 be a trivial one point set. Let 𝒴 = ℝ^{2}. Consider the parameter set Θ = Θ_{1} ∪Θ_{2}, where Θ_{1} = ℝ×{0} and Θ_{2} = {0}×ℝ. Let us consider the (constant !) regression functions {f_{θ} = θ; θ ∈ Θ} and let us drop in the notations the trivial dependence on X. Splitting the sample in two halves and using

f_{+1}^{K}(Y_{1}^{K}) = (\frac{1}{K} ∑_{i=1}^{K} Y_{i}(1), 0) ,

f_{−1}^{K}(Y_{1}^{K}) = (0, \frac{1}{K} ∑_{i=1}^{K} Y_{i}(2)) ,

where Y_{i} = (Y_{i}(1), Y_{i}(2)) ∈ ℝ^{2}, we get that for some constant A > 0 and any exchangeable probability distribution P_{N+1} such that P_{N+1} almost surely ∥Y_{i}∥ ≤ B

𝔼_{P_{N+1}(dY_{1}^{N+1})}∥Y_{N+1} − 𝔼_{ρ(dm)}f_{m}^{K}(Y_{1}^{K})∥^{2} − inf_{θ∈Θ} 𝔼_{P_{N+1}(dY_{1}^{N+1})}∥Y_{N+1} − f_{θ}∥^{2} ≤ \frac{AB^{2}}{N} .

To see that no estimator θ̂ : 𝒴^{N} → Θ could have the same rate of convergence in the worst case, let us consider in 𝒴 the two points

p_{m} = (1 + \frac{m}{2}, 1 − \frac{m}{2}), m ∈ \{−1, +1\},

and the two distributions

P_{m}(dY) = (\frac{1}{2} + \frac{αm}{\sqrt{N}} ) δ_{p_{+1}}(Y) + (\frac{1}{2} − \frac{αm}{\sqrt{N}} ) δ_{p_{−1}}(Y), m ∈ \{−1, +1\}.

We are going to prove that for some small enough positive constant α and some positive constant C

inf_{θ̂} sup_{m∈{−1,+1}}(𝔼_{P_{m}^{⊗(N+1)}(dY_{1}^{N+1})}∥Y_{N+1} − fθ̂∥^{2}

− inf_{θ∈Θ} 𝔼_{P_{m}(dY_{N+1})}∥Y_{N+1} − f_{θ}∥^{2}) ≥ \frac{C}{\sqrt{N}} .

Let

Ȳ_{m} = 𝔼_{P_{m}(dY)}(Y) = (1 + \frac{α m}{\sqrt{N}} , 1 − \frac{α m}{\sqrt{N}} ) ,

m̂(Y_{1}^{N}) = \begin{cases}+1 & if θ̂(Y_{1}^{N}) ∈ Θ_{1} \\ −1 & otherwise. \end{cases}

Remarking that

∥θ̂ − Ȳ_{m}∥^{2} ≥ (1 − \frac{α m m̂}{\sqrt{N}})^{2} ,

we get that

inf_{θ̂} sup_{m} (𝔼_{P_{m}^{⊗N+1}}∥Y_{N+1} − fθ̂∥^{2} − inf_{θ} 𝔼_{P_{m}(dY_{N+1})}∥Y_{N+1} − f_{θ}∥^{2})

= inf_{θ̂} sup_{m} 𝔼_{P_{m}^{⊗N}} ∥Ȳ_{m} − θ̂∥^{2} − (1 − \frac{1}{α \sqrt{N}} )^{2}

≥ inf_{m̂} sup_{m} \frac{4 α}{\sqrt{N}} P_{m}^{⊗N}(m ≠ m̂)

≥ \frac{C}{\sqrt{N}} ,

the justification of the last inequality being the same as in the counter example given about adaptive pattern classification in section 3.4.

5. One stage piecewise constant regression

In this section, we consider a measurable product space (𝒳 × 𝒴, ℬ_{1} ⊗ ℬ_{2}), where 𝒴 = ℝ^{D} and ℬ_{2} is the Borel sigma algebra. We consider an exchangeable probability distribution P_{N} ∈ ℳ_{+}^{1}((𝒳 × 𝒴)^{N}, (ℬ_{1} ⊗ ℬ_{2})^{⊗N}). We let {(X_{i}, Y_{i}) = Z_{i}; i = 1, …, N} be the canonical process. The observation is Z_{1}^{N−1} and we want to estimate P_{N}(Y_{N} | X_{N} ; Z_{1}^{N−1}).

We assume that Y is a.s. bounded: there exists a positive constant B such that

∥Y_{i}∥ ≤ B, P_{N} a.s. i = 1, …, N.

To define a model, we consider a countable family 𝒮 of measurable partitions S ⊂ ℬ_{1} of 𝒳. In connection with each partition S ∈ 𝒮, we consider the parameter space Θ_{S} = 𝒴^{S} of the maps θ_{S} : S → 𝒴. We consider also the canonical projection I_{S} : 𝒳 → S defined by X ∈ I_{S}(X), and we call f_{θ} : 𝒳 → 𝒴 the regression function f_{θ}(X) = f_{θ_{S}}^{S}(X) = θ_{S}(I_{S}(X)), where θ = (S, θ_{S}). On the global “structured” parameter set Θ = {(S, θ_{S}) ; S ∈ 𝒮, θ_{S} ∈ Θ_{S}}, we consider a prior probability distribution π(S, dθ_{S}) depending in a permutation invariant way on X_{1}^{N}. We take

π(dθ_{S} | S) = ∏_{I∈S} (\frac{ϵ(I)}{2π})^{D/2} exp (−\frac{ϵ(I)}{2}∥θ_{S}(I)∥^{2}) dθ_{S}(I),

where the choice of the regularization parameter ϵ(I) will depend on ∑_{i=1}^{N} 1(X_{i} ∈ I). The marginal distribution π(dS) can be arbitrary at this stage.

We then consider the model {Q_{θ}; θ ∈ Θ} defined by

Q_{θ}(dY | X) = (\frac{λ(I_{S}(X))}{2π})^{D/2} exp (−\frac{λ(I_{S}(X))}{2}∥Y − f_{θ}(X)∥^{2}) dY,

where the choice of λ(I) will depend on ∑_{i=1}^{N} 1(X_{i} ∈ I). We will study the Gibbs estimator at inverse temperature β

G_{β}(dY_{N} | X_{N} ; Z_{1}^{N−1}) = g_{β}(Y_{N} | X_{N} ; Z_{1}^{N−1})dY_{N}
= 𝔼_{ρ_{β,0}(dθ)}Q_{θ}(dY_{N} | X_{N}),

where

ρ_{β,ξ}(dθ) ∼ ( ∏_{i=1}^{N−1} q_{θ}(Y_{i} | X_{i}))^{β} q_{θ}(Y_{N} | X_{N})^{ξ} π(dθ).

Theorem 1.1 extends verbatim to the case when π(dθ) and Q_{θ}(dY | X) depend on the design X_{1}^{N} in a permutation invariant way. Indeed we can apply the theorem to

\frac{1}{|𝔖_{N}|} ∑_{σ∈𝔖_{N}} 1(X_{i} = X̄_{σ(i)} ; 1 ≤ i ≤ N)P_{N}(Y_{1}^{N} | X_{1}^{N})

and write P_{N} as a combination of these more elementary distributions which have a fixed deterministic design.

We have to compute the posterior distributions ρ_{β,ξ}(dθ) and the constants γ_{β}(θ) and χ_{β,α}. Let

a(I) = ∑_{i=1}^{N−1} 1(X_{i} ∈ I),
b(I) = 1(X_{N} ∈ I),
η(I) = λ(I) (βa(I) + ξb(I)) + ϵ(I),
θ̄(I) = (a(I) + \frac{ξ}{β} b(I) + \frac{ϵ(I)}{λ(I)β} )^{−1} ( ∑_{i=1}^{N−1} Y_{i} 1(X_{i} ∈ I) + \frac{ξ}{β} Y_{N} 1(X_{N} ∈ I)) .

Let us choose ϵ(I) = ϵ̄λ(I) where ϵ̄ is a constant. With these notations

ρ_{β,ξ}^{Z_{1}^{N}} (dθ_{S} | S) = ∏_{I∈S} (\frac{η(I)}{2π})^{D/2} exp (−\frac{η(I)}{2}∥θ_{S}(I) − θ̄_{S}(I)∥^{2}) dθ_{S}(I),

ρ_{β,ξ}^{Z_{1}^{N}} (S) ∼ π(S) ∏_{I∈S} (\frac{η(I)}{2π})^{−D/2} (\frac{λ(I)}{2π})^{(βa(I)+ξb(I))D/2}

× exp (−\frac{β}{2} ∑_{i=1}^{N−1} λ(I_{S}(X_{i}))∥Y_{i} − f S ; θ̄_{S}(X_{i})∥^{2} − \frac{ξ}{2}λ(I_{S}(X_{N}))∥Y_{N} − f S ; θ̄_{S}(X_{N})∥^{2}

− ∑_{I∈S} \frac{ϵ(I)}{2}∥θ̄_{I}∥^{2}) .

Let us put for short

h(θ) = \frac{λ(I_{S}(X_{N}))}{2}∥Y_{N} − f_{θ}(X_{N})∥^{2} − \frac{D}{2} log λ(I_{S}(X_{N})).

We have

χ_{β,1} ≤ 0 ∨ sup_{ξ∈[0,1]} \frac{𝔼_{P_{N}} M_{ρ_{β,ξ}(dθ)}^{3}h(θ)}{𝔼_{P_{N}} Var_{ρ_{β,ξ}(dθ)} h(θ)}.

In the following computations, we put ρ(dθ) = ρ_{β,ξ}^{Z_{1}^{N}} (dθ) for short. We can decompose the variance into

Var_{ρ} h(θ) = 𝔼_{ρ}(h − 𝔼_{ρ}(h | S))^{2} + 𝔼_{ρ}(𝔼_{ρ}(h | S) − 𝔼_{ρ}(h))^{2}.

In the same way, we can decompose the third moment into

M_{ρ}^{3}(h) = 𝔼(h − 𝔼(h | S) + 𝔼(h | S) − 𝔼(h))^{3}
= 𝔼(h − 𝔼(h | S))^{3} + 3𝔼((h − 𝔼(h | S))^{2}(𝔼(h | S) − 𝔼(h)))
+ 𝔼(𝔼(h | S) − 𝔼(h))^{3}

The conditional expectation of h is equal to

𝔼_{ρ}(h | S) = \frac{λ(I_{N})}{2} (∥Y_{N} − f S ; θ̄_{S}(X_{N})∥^{2} + \frac{D}{η(I_{N})}) − \frac{D}{2} log λ(I_{N}),

where we have put I_{N} = I_{S}(X_{N}).

Let us choose

λ(I) = λ̄ (1 + \frac{1}{β(a(I) + b(I) − 1) + ϵ̄}) ,

where λ̄ is a constant. We obtain that

∥𝔼(h | S) − 𝔼(h)∥ ≤ 2B^{2}λ̄ (1 + \frac{1}{ϵ̄}) + \frac{D}{2} (\frac{1}{ϵ̄} + log (1 + \frac{1}{ϵ̄})) .

The terms 𝔼((h−𝔼(h | S))^{2} | S) and 𝔼((h−𝔼(h | S))^{3} | S) can be computed explicitly from the lemma:

Lemma 5.1. Let θ ∼ 𝒩(0, α^{−1}I) be a centered Gaussian random variable in ℝ^{D} and let Y ∈ ℝ^{D} be a fixed vector, then

𝔼 (∥Y − θ∥^{2} − 𝔼(∥Y − θ∥^{2}))^{2} = \frac{1}{α^{2}} (4α∥Y ∥^{2} + 2D) ,
𝔼 (∥Y − θ∥^{2} − 𝔼(∥Y − θ∥^{2}))^{3} = \frac{1}{α^{3}} (24α∥Y ∥^{2} + 8D)

≤ \frac{6}{α}𝔼 (∥y − θ∥^{2} − 𝔼(∥Y − θ∥^{2}))^{2} .

Taking α = η(I_{N}), we get that

𝔼((h − 𝔼(h | S))^{3} | S) = (\frac{λ(I_{N})}{2η(I_{N})})^{3} (24η(I_{N})∥Y_{N} − θ̄_{S}(I_{N})∥^{2} + 8D)

≤ \frac{3λ(I_{N})}{η(I_{N})}𝔼((h − 𝔼(h | S))^{2} | S)

≤ \frac{3}{ϵ̄}𝔼((h − 𝔼(h | S))^{2} | S).

Therefore we have

M_{ρ}^{3}(h) ≤ \frac{3}{ϵ̄}𝔼((h − 𝔼(h | S))^{2})

+ (2B^{2}λ̄ (1 + \frac{1}{ϵ̄}) + \frac{D}{2} (\frac{1}{ϵ̄} + log (1 + \frac{1}{ϵ̄})))

× (3𝔼((h − 𝔼(h | S))^{2}) + 𝔼((𝔼(h | S) − 𝔼(h))^{2}))

≤ (3 (2B^{2}λ̄ (1 + \frac{1}{ϵ̄}) + \frac{D}{2} (\frac{1}{ϵ̄} + log (1 + \frac{1}{ϵ̄}))) + \frac{3}{ϵ̄}) Var_{ρ} h.

In conclusion, we have proved that

Lemma 5.2.

χ_{β,1} ≤ 6B^{2}λ̄ (1 + \frac{1}{ϵ̄}) + \frac{3D}{2} (\frac{1}{ϵ̄} + log (1 + \frac{1}{ϵ̄})) + \frac{3}{ϵ̄}.

Let us compute now γ_{β}(θ′). We have

𝔼_{ρ_{β,β}(dθ)} log (∏_{i=1}^{N} q_{θ}(Y_{i} | X_{i}))^{−β}

= 𝔼_{ρ_{β,β}(dθ)} ∑_{i=1}^{N} β (\frac{λ(I_{S}(X_{i}))}{2}∥Y_{i} − f_{θ}(X_{i})∥^{2} − \frac{D}{2} log \frac{λ(I_{S}(X_{i}))}{2π}) .

GIBBS ESTIMATORS 25

Moreover, putting c(I) = ∑_{i=1}^{N} 1(X_{i} ∈ I), we get that

𝔼_{ρ_{β,β}} (∑_{i=1}^{N} \frac{βλ(I_{S}(X_{i}))}{2}∥Y_{i} − f_{θ}(X_{i})∥^{2} | S)

= ∑_{i=1}^{N} \frac{βλ(I_{S}(X_{i}))}{2}∥Y_{i} − f S ; θ̄_{S}(X_{i})∥^{2} + ∑_{I∈S} \frac{Dc(I)}{2 (c(I) + \frac{ϵ̄}{β})}

≤ ∑_{i=1}^{N} \frac{βλ(I_{S}(X_{i}))}{2}∥Y_{i} − f S ; θ̄_{S}(X_{i})∥^{2} + \frac{D|S|}{2}.

We can now use the fact (proved in proposition A.1) that

\frac{∑_{S∈𝒮} π̃(S)h̃(S)e^{−h̃(S)}}{∑_{S∈𝒮} π̃(S)e^{−h̃(S)}} ≤ h̃(S′) − log π̃(S′) + log ∑_{S∈𝒮} π̃(S).

Putting

π̃(S) = π(S) ∏_{I∈S} (\frac{η(I)}{2π})^{−D/2}

× exp (\frac{D|S|}{2} − ∑_{I∈S} \frac{ϵ̄λ(I)}{2}∥θ̄_{S}(I)∥^{2}) ,

h̃(S) = ∑_{i=1}^{N} β (\frac{λ(I_{S}(X_{i}))}{2}∥Y_{i} − f S ; θ̄_{S}(X_{i})∥^{2}

−\frac{D}{2} log \frac{λ(I_{S}(X_{i}))}{2π}) + \frac{D|S|}{2},

we get that Lemma 5.3.

𝔼_{ρ_{β,β}(dθ)} log (∏_{i=1}^{N} q_{θ}(Y_{i} | X_{i}))^{−β}

≤ ∑_{i=1}^{N} \frac{βλ(I_{S′}(X_{i}))}{2}∥Y_{i} − f S′ ; θ̄_{S′} (X_{i})∥^{2} − ∑_{I∈S′} \frac{βDc(I)}{2} log \frac{λ(I)}{2π}

+ \frac{D|S′|}{2} + |S′|\frac{λ̄ϵ̄}{2} (1 + \frac{1}{ϵ̄}) B^{2} − log π̄(S′) + log ∑_{S∈𝒮} π̄(S),

where

π̄(S) = π(S) ∏_{I∈S} (\frac{η(I)}{2π})^{−D/2} exp \frac{D|S|}{2}.

Now remembering that

θ̄_{S}(I) = (c(I) + \frac{ϵ̄}{β})^{−1} ∑_{j=1}^{N} 1(X_{j} ∈ I) Y_{j}

26 O. CATONI

it is easy to see that

∑_{i=1}^{N} \frac{βλ(I_{S′}(X_{i}))}{2} ∥Y_{i} − f S′ ; θ̄_{S′} (X_{i})∥^{2}

≤ inf_{θ_{S′}} ∑_{i=1}^{N} \frac{βλ(I_{S′}(X_{i}))}{2}∥Y_{i} − f_{θ_{S′}}^{S′} (X_{i})∥^{2}

+ ∑_{I∈S′} \frac{βλ(I)}{2} (\frac{ϵ̄}{βc(I) + ϵ̄})^{2} c(I) ∥\frac{1}{c(I)} ∑_{j=1}^{N} Y_{j} 1(X_{j} ∈ I)∥^{2}

≤ inf_{θ_{S′}} ∑_{i=1}^{N} \frac{βλ(I_{S′}(X_{i}))}{2} ∥Y_{i} − f_{θ_{S′}}^{S′} (X_{i})∥^{2}

+ \frac{1}{2}|S′|λ̄(1 + ϵ̄)B^{2}.

This proves that Lemma 5.4.

sup_{θ_{S′} ∈Θ_{S′}} γ_{β}(S′, θ_{S′}) ≤ \frac{D|S′|}{2} + |S′|B^{2}λ̄(1 + ϵ̄) − log π̄(S′) + log ∑_{S∈𝒮} π̄(S).

We can now compute g_{β} more explicitly.

g_{β}(Y_{N} | X_{N} ; Z_{1}^{N−1}) = 𝔼_{ρ_{β,0}(dS)} (\frac{λ(I_{N})}{2π})^{D/2} (\frac{η(I_{N})}{2π})^{D/2}

× exp (−\frac{λ(I_{N})}{2}∥Y_{N} − θ_{S}(I_{N})∥^{2}

−\frac{η(I_{N})}{2}∥θ_{S}(I_{N}) − θ̄_{S}(I_{N})∥^{2}) dθ_{S}(I_{N})

= 𝔼_{ρ_{β,0}(dS)} (2π (\frac{1}{λ(I_{N})} + \frac{1}{η(I_{N})}))^{−D/2}

× exp (−\frac{1}{2} (\frac{1}{λ(I_{N})} + \frac{1}{η(I_{N})})^{−1} ∥Y_{N} − θ̄_{S}(I_{N})∥^{2}) ,

where

λ(I_{N}) = λ̄ (1 + \frac{1}{βa(I_{N}) + ϵ̄}) ,
η(I_{N}) = λ(I_{N})(βa(I_{N}) + ϵ̄),
θ̄_{S}(I) = \frac{1}{a(I) + ϵ̄/β} ∑_{i=1}^{N−1} Y_{i} 1(X_{i} ∈ I).

However

\frac{1}{λ(I_{N})} + \frac{1}{η(I_{N})} = \frac{1}{λ̄},

(the value of λ(I_{N}) was chosen for that!) and therefore:

g_{β}(Y_{N} | X_{N}; Z_{1}^{N−1}) = 𝔼_{ρ_{β,0}(dS)} (\frac{λ̄}{2π} )^{D/2} exp (−\frac{λ̄}{2}∥Y_{N} − f S ; θ̄_{S}(X_{N})∥^{2}) .

Let us assume from now that λ̄ ≤ \frac{1}{4B^{2}} and that ϵ̄ ≥ β. Let Z̄_{1}^{N} be fixed for a while and let P̄ be the exchangeable distribution obtained by integrating over the permutations of the indices:

P̄Z̄_{1}^{N} (dZ_{1}^{N}) = \frac{1}{|𝔖_{N}|} ∑_{σ∈𝔖_{N}} δ_{(Z̄_{σ(i)})}(dZ_{1}^{N}).

We can apply theorem 1.1 to P̄Z̄_{1}^{N} first and integrate over Z̄_{1}^{N} afterwards. Using moreover the fact that the Gaussian function is concave in the unit ball as in the previous section, we get that

𝔼P̄ \frac{λ̄}{2}∥Y_{N}−𝔼_{ρ_{β,0}(dS)}f S ; θ̄_{S}(X_{N})∥^{2} − \frac{D}{2} log \frac{λ̄}{2π}

≤ 𝔼P̄ log g_{β}(Y_{N} | X_{N} ; Z_{1}^{N−1})^{−1}

≤ inf_{S∈𝒮} ( inf_{θ_{S}∈Θ_{S}} 𝔼P̄ (\frac{λ(I_{S}(X_{N}))}{2}∥Y_{N} − f_{θ}(X_{N})∥^{2} − \frac{D}{2} log \frac{λ(I_{S}(X_{N}))}{2})

+\frac{γ_{β}(S)}{βN}) ,

as soon as β ≤ (1 + exp χ_{β,1}/2)^{−1}. But

λ(I_{S}(X_{N})) = λ̄ (1 + \frac{1}{βa(I_{S}(X_{N})) + ϵ̄}) ,

and therefore

𝔼P̄ (\frac{λ(I_{S}(X_{N}))}{λ̄} − 1)∥Y_{N} − f_{θ}(X_{N})∥^{2}

≤ 4B^{2}𝔼P̄ \frac{1}{β(c(I_{N}) − 1) + ϵ̄}

= 4B^{2} \frac{1}{N} ∑_{I∈S} \frac{c(I)}{β(c(I) − 1) + ϵ̄}

≤ \frac{4B^{2}|S|}{βN}.

Thus

𝔼_{P_{N}} ∥Y_{N} − 𝔼_{ρ_{β,0}(dS)}f S ; θ̄_{S}(X_{N})∥^{2}

≤ inf_{S∈𝒮} ( inf_{θ_{S}∈Θ_{S}} 𝔼_{P_{N}} ∥Y_{N} − f_{θ_{S}}^{S}(X_{N})∥^{2}

+\frac{4B^{2}|S|}{βN} + \frac{2γ_{β}(S)}{λ̄βN}) .

We can summarize what we have obtained by a theorem:

Theorem 5.1. For any exchangeable probability distribution P_{N} such that

∥Y_{i}∥ ≤ B P_{N} almost surely,

for any choice of parameters λ̄, ϵ̄ and β such that

λ̄ ≤ \frac{1}{4B^{2}} ,
β ≤ ϵ̄,
inf_{α>β} \frac{β^{2}}{(α − β)(2 − α − β)} exp αχ ≤ 1,

where

χ = 6B^{2}λ̄ (1 + \frac{1}{ϵ̄}) + \frac{3D}{2} (\frac{1}{ϵ̄} + log (1 + \frac{1}{ϵ̄})) + \frac{3}{ϵ̄},

for any choice of prior probability distribution π̄ on 𝒮, the posterior Gibbs distribution

ρ(S) ∼ π̄(S) ∏_{I∈S} (1 + \frac{1}{β(c(I) − 1) + ϵ̄})^{βa(I)D/2} (\frac{βc(I) + ϵ̄}{βa(I) + ϵ̄})^{D/2} exp (−\frac{D|S|}{2})

× exp (−\frac{λ̄}{2} ( ∑_{i=1}^{N−1} β (1 + \frac{1}{β(c(I_{S}(X_{i})) − 1) + ϵ̄}) ∥Y_{i} − f S ; θ̄_{S}(X_{i})∥^{2}

+ϵ̄∑_{I∈S} (1 + \frac{1}{β(c(I) − 1) + ϵ̄}) ∥θ̄_{S}(I)∥^{2}))

satisfies

𝔼_{P_{N}} ∥Y_{N} − 𝔼_{ρ(dS)}f S ; θ̄_{S}(X_{N})∥^{2} ≤ inf_{S∈𝒮} ( inf_{θ_{S}∈Θ_{S}} 𝔼_{P_{N}} ∥Y_{N} − f_{θ_{S}}^{S}(X_{N})∥^{2} + \frac{γ̄(S)}{N}) ,

with

γ̄(S) = \frac{D|S|}{λ̄β} + \frac{B^{2}|S|}{β}(6 + 2ϵ̄) − \frac{2 log π̄(S)}{λ̄β}.

Remark 5.1. We can take for example

ϵ̄ = 3(D + 1),
λ̄ = \frac{1}{7B^{2}} ,
β = \frac{1}{1 + e},

which gives

γ̄(S) = (1 + e)B^{2} ((13D + 12)|S| − 14 log π̄(S)) .

Remark 5.2. It is clear from the proof that the constants in this theorem are pessimistic, at least when N is large with respect to |S|, since we have in many places used 0 as a lower bound for a(I).

Remark 5.3. The expression of ρ(S) is interesting, since it shows what an approximate “least favourable” prior distribution may look like. Of particular significance is the factor exp(−D|S|/2) which appears as a penalty term for the dimension of Θ_{S}. We can find here an analogy with the penalized maximum likelihood estimator (see [3]). Note also that the use of a “double mixture” over a countable union of continuous parameter spaces finds its origin in information theory (see for example [14], [12], [18]).

6. Conclusion

With the Gibbs estimator, we advocate an approach to statistical inference in which the model is used as a tool to extract information from the sample. An important conclusion is that it is not always necessary to represent accurately the sample distribution, and we gave examples where the model is coined to reflect the loss function to be minimized rather that the statistical properties of the observation. This gives for example a theoretical justification to the use of a Gaussian shift model in non Gaussian situations, or to the use of an exponential model for adaptive pattern classification. We hope that this paper will also contribute to create new links between information theory, statistical mechanics and statistical inference.

We are planning to give more applications and to discuss the design of algorithms to compute Gibbs estimators in forthcoming studies.

References

[1] A. Barron (1987) Are Bayes Rules Consistent in Information ? Open Problems in Communication and Computation, T. M. Cover and B. Gopinath Ed., Springer Verlag 1987.

[2] A. Barron and Y. Yang (1995) Information Theoretic Determination of Minimax Rates of Convergence, preprint of the Department of Statistics at Yale University, http://www.stat.yale.edu/Preprints, submitted to the Annals of Statistics

[3] A. Barron, L. Birgé and P. Massart, (1995) Risk bounds for model selection via penalization, preprint, available on the web at http://www.math.u-psud.fr/html/ppo.html , Equipe de Modélisation Stochastique et Statistique, Université Paris-Sud Orsay.

[4] G. Blanchard, The “progressive mixture” estimator for regression trees, Annales de l’I.H.P., 35(6):793-820, 1999.

[5] G. Blanchard, A new algorithm for Bayesian MCMC CART sampling, preprint, 2000.

[6] L. Birgé and P. Massart (1997) From model selection to adaptive estimation, Festschrift for Lucien Le Cam, 55–87, Springer, New York.

[7] L. Birgé and P. Massart (1995) Minimum contrast estimators on sieves, preprint, available on the web at http://www.math.u-psud.fr/html/ppo.html, Equipe de Modélisation Stochastique et Statistique, Université Paris-Sud Orsay.

[8] O. Catoni (1997) A mixture approach to universal model selection, preprint LMENS - 97 - 30, http://www.dmi.ens.fr/preprints.

[9] O. Catoni, Universal aggregation rules with sharp oracle inequalities, to appear in the Annals of Statistics, 2000, N.B.: this is a revised and extended version of “A mixture approach to universal model selection”.

[10] O. Catoni, Free energy estimates and deviation inequalities, preprint, to appear in revised form, under the title Laplace transform estimates and deviation inequalities, in the Annales de l’I.H.P., 1999.

[11] O. Catoni, Data compression and adaptive histograms, to appear in the proceedings of the International Conference on Foundations of Computational Mathematics in honor of Professor Steve Smale’s 70th Birthday, July 2000.

[12] M. Feder and N. Merhav, Hierarchical Universal Coding, IEEE Trans. Inform. Theory, vol 42, no 5, Sept, 1996.

[13] W. Rudin, Real and Complex Analysis, McGraw-Hill, 1966.

[14] B. Y. Ryabko, Twice-universal coding, Probl. Inform. Transm., vol 20, no 3, pp. 24-28, July-Sept 1984.

[15] J.-P. Vert, Double mixture and universal inference, preprint, 2000.

[16] J.-P. Vert, Adaptive context trees and text clustering, IEEE Trans. Inform.Theory to appear.

[17] J.-P. Vert, Text categorization using adaptive context trees, preprint, 2000.

[18] F. M. J. Willems, Y. M. Shtarkov and T. J. Tjalkens, The Context-Tree Weighting Method: Basic Properties, IEEE Trans. Inform. Theory, vol 41, no 3, May, 1995.

[19] F. M. J. Willems, Y. M. Shtarkov and T. J. Tjalkens, Context Weighting for General Finite-Context Sources, IEEE Trans. Inform. Theory, vol 42, no 5, Sept, 1996.

Appendix A. Some abstract inference problem

In this appendix, we give a non-normalized form of the density estimation theorem, which covers all the cases studied in the paper.

Let us consider a measurable state space (𝒳, ℬ) and an exchangeable probability measure P_{N} on (𝒳^{N}, ℬ^{⊗N}). Let us consider also a measurable parameter space (Θ, ℬ′), and a positive σ-finite measure π ∈ ℳ_{+}(Θ, ℬ′) (more explicitely we assume that Θ is the union of a countable family of ℬ′ measurable sets of finite π-measure, in order to be able to apply Fubini’s theorem to the product of π with some other measures). Let q : Θ × 𝒳 → ℝ_{+} be a non negative measurable function (the reader may like to view it as a “non normalized” likelihood function). Let λ be the Lebesgue measure on the real line. As the positive measure π will be in many applications a probability measure, we will use for any function h ∈ 𝕃^{1}(Θ, π) the notation

𝔼_{π(dθ)}(h) =^{def} ∫_{θ∈Θ} h(θ)π(dθ).

In the same way, for any f ∈ 𝕃^{1}(𝒳^{N}, P_{N}), 𝔼_{P_{N}} (f(X_{1}, …, X_{N})) – or more explicitely 𝔼_{P_{N} (dX_{1}^{N})}(f(X_{1}, …, X_{N})) – will denote the expectation with respect to P_{N} .

In order to impose some integrability conditions on the functions q(θ, x) related to our purpose, we will make use of the following simple lemma concerning the composition of absolutely continuous functions :

Lemma A.1. Let I be an interval of the real line and let F : I^{2} → ℝ ∈ 𝒞^{1}(I^{2}) be a function with a continuous and bounded differential dF ∈ 𝕃^{∞}. Let g : J → I and h : J → I be two absolutely continuous functions defined on some other real interval J. Under this set of hypotheses, x ↦ F (g(x), h(x)) is also absolutely continuous and its Radon-Nikodym derivative is

F (g, h)′ = \frac{∂F}{∂x} (g, h)g′ + \frac{∂F}{∂y} (g, h)h′,

where g′ and h′ are the Radon-Nikodym derivatives of g and h.

Proof. Let μ_{g} and μ_{h} be the signed measures defined by g and h. Then as F is Lipschitz of order 1, F (g, h) is of bounded variations, and μ_{F (g,h)} is dominated by |μ_{g}| + |μ_{h}|, the sum of the total variation measures of μ_{g} and μ_{h}. Therefore μ_{F (g,h)} is dominated by the Lebesgue measure, which means by definition that F (g, h) is absolutely continuous. The composition formula comes from the fact that the Radon-Nikodym derivatives g′ and h′ are also almost everywhere the usual derivatives of g and h. For more background on absolutely continuous functions, we refer the reader to [13, Chap 8].

Assume that the following integrability conditions are fulfilled for some positive real parameter β ∈]0, 1/2] :

(11) θ ↦ ( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{k}

∈ 𝕃^{1}(Θ, π), k ∈ {0, 1}, (X_{1}, …, X_{N}) ∈ 𝒳^{N},

GIBBS ESTIMATORS 31

(12) (θ, η) ↦ ( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}(log q(θ, X_{N}))^{3}

∈ 𝕃^{1}(Θ × [ϵ, 1], π ⊗ λ), (X_{1}, …, X_{N}) ∈ 𝒳^{N}, ϵ > 0.

Note that from the interpolation of norms (which is nothing but Hölder’s inequality) ∥fg^{η}∥ ≤ ∥fg^{β}∥^{η/β}∥f∥^{(1−η/β)}, η ∈ [0, β], hypothesis (11) (along with Fubini’s theorem) implies

(θ, η) ↦ ( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η} ∈ 𝕃^{1}(Θ×[0, 1], π⊗λ), (X_{1}, …, X_{N}) ∈ 𝒳^{N}.

In view of this, hypothesis (12) implies that

(θ, η) ↦ ( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}(log q(θ, X_{N}))^{k}

∈ 𝕃^{1}(Θ × [ϵ, 1], π ⊗ λ), (X_{1}, …, X_{N}) ∈ 𝒳^{N}, 0 ≤ k ≤ 3, ϵ > 0.

Hypotheses (11), (12) and Fubini’s theorem imply that

𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}(log(q(θ, X_{N})))^{k}]

= 𝔼_{π(dθ)} [(∏_{n=1}^{N} q(θ, X_{n}))^{β} (log(q(θ, X_{N})))^{k}]

+ ∫_{τ=β}^{η} 𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{τ} (log(q(θ, X_{N})))^{k+1}] dτ

(X_{1}, …, X_{N}) ∈ 𝒳^{N}, k ∈ {0, 1, 2}, η ∈]0, 1].

Therefore, using Fubini’s theorem again, we see that

η ↦ 𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}] ∈ 𝒞^{2}(]0, 1]), (X_{1}, …, X_{N}) ∈ 𝒳^{N}.

In order to consider its logarithm, we will introduce the following positivity condition :

π (∏_{n=1}^{N} q(θ, X_{n}) > 0) > 0, (X_{1}, …, X_{N}) ∈ 𝒳^{N}. (13)

Note that this condition implies that

𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}] > 0, (X_{1}, …, X_{N}) ∈ 𝒳^{N}, η ∈ [0, 1].

Note also that condition (13) is satisfied if some measurable set of parameters T ∈ ℬ′ is such that π(T) > 0 and

inf_{x∈𝒳} q_{θ}(x) > 0, θ ∈ T.

Under these conditions, introducing the abriged notation X_{1}^{N} =^{def} (X_{1}, …, X_{N}), we see that

η ↦ ℰ^{X_{1}^{N}} (η) =^{def} log 𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}] ∈ 𝒞^{2}(]0, 1]),

X_{1}^{N} ∈ 𝒳^{N}.

Note that ℰ^{X_{1}^{N}} (η) is also defined (according to (11)) and right continuous at point 0 (apply the monotone convergence theorem on the sets {θ : q(θ, X_{N}) ≥ 1} and {θ : q(θ, X_{N}) < 1}), and that it is a convex function on [0, 1] (see the expression of its second derivative below). Moreover

\frac{∂}{∂η} ℰ^{X_{1}^{N}} (η) = \frac{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η} log q(θ, X_{N})]}{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}]},

\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η) = \frac{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}(log(q(θ, X_{N})) − \frac{∂}{∂η} ℰ^{X_{1}^{N}} (η))^{2}]}{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}]}

Putting

\frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η) =^{def} \frac{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}(log(q(θ, X_{N})) − \frac{∂}{∂η} ℰ^{X_{1}^{N}} (η))^{3}]}{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}]},

and using Fubini’s theorem and lemma A.1, we see that \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η) is absolutely continuous and that

\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η) = \frac{∂^{2}}{∂η^{2}}_{|η=β}ℰ^{X_{1}^{N}} (η) + ∫_{β}^{η} \frac{∂^{3}}{∂ξ^{3}} ℰ^{X_{1}^{N}} (ξ)dξ, η ∈]0, 1].

(This implies that \frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η) is almost everywhere the derivative of \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η).)

Now we will need to take expectations with respect to (X_{1}, …, X_{N}), and to exchange these expectations with integrations with respect to η. This leads to consider the following set of assumptions:

X_{1}^{N} ↦ \frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η) ∈ 𝕃^{1}(𝒳^{N}, P_{N}), (14)

(15) (X_{1}^{N}, η) ↦ \frac{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}|log(q(θ, X_{N})) − \frac{∂}{∂η} ℰ^{X_{1}^{N}} (η)|^{3}]}{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}]}

∈ 𝕃^{1}(𝒳^{N} × [ϵ, 1], P_{N} ⊗ λ), ϵ > 0.

Note that hypothesis (15) implies that

(X_{1}^{N}, η) ↦ \frac{∂^{k}}{∂η^{k}} ℰ^{X_{1}^{N}} (η) ∈ 𝕃^{1}(𝒳^{N} × [ϵ, 1], P_{N} ⊗ λ), k ∈ \{2, 3\}, ϵ > 0.

Let Θ_{1} ⊂ Θ be the set of parameters for which q(θ, X_{N}) is integrable :

Θ_{1} =^{def} {θ ∈ Θ : X_{1}^{N} ↦ q(θ, X_{N}) ∈ 𝕃^{1}(𝒳^{N}, P_{N})}. (16)

For any θ ∈ Θ_{1}, let us consider the constant

(17) γ_{β}(θ) =^{def} 𝔼_{P_{N}} ( \begin{matrix}β log ∏_{n=1}^{N} & q(θ, X_{n}) \\ − \frac{𝔼_{π(dθ′)} ((∏_{n=1}^{N} q(θ′, X_{n}))^{β} β log (∏_{n=1}^{N} q(θ′, X_{n})))}{𝔼_{π(dθ′)} ((∏_{n=1}^{N} q(θ′, X_{n}))^{β})} \end{matrix}) .

Note that γ_{β}(θ) is a well defined real number for any θ ∈ Θ_{1}, because it is from the definition of Θ_{1}, assumption (14) and the fact that P_{N} is exchangeable, the expectation with respect to P_{N} of the difference of two integrable functions. Indeed

\frac{𝔼_{π(dθ′)} ((∏_{n=1}^{N} q(θ′, X_{n}))^{β} β log (∏_{n=1}^{N} q(θ′, X_{n})))}{𝔼_{π(dθ′)} ((∏_{n=1}^{N} q(θ′, X_{n}))^{β})}

= ∑_{n=1}^{N} \frac{𝔼_{π(dθ′)} ((∏_{n=1}^{N} q(θ′, X_{n}))^{β} β log (q(θ′, X_{n})))}{𝔼_{π(dθ′)} ((∏_{n=1}^{N} q(θ′, X_{n}))^{β})},

and each term in the righthand side has the same distribution as β \frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η).

Assume that the previous integrability and positivity hypotheses hold for some given value of β. Assume moreover that for some value of α ∈]β, 1]

χ_{β,α} = 0 ∨ ess sup_{ξ∈]0,α]} [\frac{−𝔼_{P_{N}} \frac{∂^{3}}{∂ξ^{3}} ℰ^{X_{1}^{N}} (ξ)}{𝔼_{P_{N}} \frac{∂^{2}}{∂ξ^{2}} ℰ^{X_{1}^{N}} (ξ)}𝟙 (𝔼_{P_{N}} \frac{∂^{2}}{∂ξ^{2}} ℰ^{X_{1}^{N}} (ξ) > 0)] < +∞, (18)

and that

\frac{β^{2}}{(α − β)(2 − α − β)} exp(αχ_{β,α}) ≤ 1. (19)

To summarize what has been assumed, we will let ℋ(N, β, α) denote the set of hypotheses (11) through (19), which depends on three parameters: N, β, and α.

Theorem A.1. Let us assume that ℋ(N, β, α) holds. In this case

(ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0)) ∈ 𝕃^{1}(𝒳^{N}, P_{N}),

and the expectation 𝔼_{P_{N}} (ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0)) is such that

(20)  𝔼_{P_{N}} (ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0)) ≥ 𝔼_{P_{N}} \frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η)

≥ sup_{θ∈Θ_{1}} (𝔼_{P_{N}} log q(θ, X_{N}) − \frac{γ_{β}(θ)}{βN}) . (21)

Remark A.1. The hypotheses mentioned in the theorem are all fullfilled when the function (θ, x) ↦ log(q(θ, x)) is bounded.

Remark A.2. The condition (19) on β can also be written as

β ≤ \frac{1}{e^{αχ} − 1} (\sqrt{1 + α(e^{αχ} − 1)(2 − α)} − 1) ,

where we have put χ_{β,α} = χ for short.

When χ_{β,1} is small, we can take α = 1 and obtain the sufficient condition

β ≤ (1 + exp(χ_{β,1}/2))^{−1}.

When χ_{β,1} is large, we can take α = χ_{β,1}^{−1} log(χ_{β,1}) and, (reminding that α ↦ χ_{β,α} is increasing), obtain the sufficient condition

β ≤ \frac{1}{χ_{β,1} − 1} (\sqrt{1 + (χ_{β,1} − 1) (2 − \frac{log(χ_{β,1})}{χ_{β,1}}) \frac{log(χ_{β,1})}{χ_{β,1}}} − 1)

∼_{χ_{β,1}→+∞} \frac{\sqrt{2 log(χ_{β,1})}}{χ_{β,1}}.

Remark A.3. Obviously,

sup_{β,α} χ_{β,α} ≤ sup_{θ,θ′,x} log [\frac{q(θ, x)}{q(θ′, x)}] .

This provides a bound when the lefthand side of this inequality is finite, that is when the model {x ↦ q(θ, x) ; θ ∈ Θ} is so to speak “log bounded”.

Remark A.4. Putting

h(θ, θ′, x_{1}^{N}) = \frac{β}{N} log (∏_{n=1}^{N} \frac{q(θ, x_{n})}{q(θ′, x_{n})}) ,

we can write γ_{β}(θ) in the form

γ_{β}(θ) = 𝔼_{P_{N}} \frac{𝔼_{π(dθ′)}[Nh(θ, θ′, X_{1}^{N}) exp(−Nh(θ, θ′, X_{1}^{N}))]}{𝔼_{π(dθ′)}[exp(−Nh(θ, θ′, X_{1}^{N}))]},

and bound it by

γ_{β}(θ) ≤ sup_{x_{1}^{N} ∈𝒳^{N}} \frac{𝔼_{π(dθ′)}[Nh(θ, θ′, x_{1}^{N}) exp(−Nh(θ, θ′, x_{1}^{N}))]}{𝔼_{π(dθ′)}[exp(−Nh(θ, θ′, x_{1}^{N}))]}.

to stress the fact that γ_{β}(θ) can be bounded using some evaluation of Laplace integrals over the parameter space.

When Θ is countable, and π is a finite measure, the following explicit bound is useful:

Proposition A.1.

γ_{β}(θ) ≤ log \frac{π(Θ)}{π(\{θ\})}. (22)

It is a consequence of the more general lemma C.1 proved in appendix C.

Proof of theorem A.1. For any ϵ ∈]0, β[, any X_{1}^{N} ∈ 𝒳^{N}, we can write

\begin{aligned}ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (ϵ) & = ∫_{η=ϵ}^{1} \frac{∂}{∂η} ℰ^{X_{1}^{N}} (η)dη \\ & = (1 − ϵ)\frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η) + ∫_{η=β}^{1}(1 − η)\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη \\ & − ∫_{η=0}^{β} 𝟙(η ≥ ϵ)(η − ϵ)\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη. \end{aligned} (23)

From the monotone convergence theorem

lim_{ϵ↓0} ∫_{η=0}^{β} 𝟙(η ≥ ϵ)(η − ϵ)\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη = ∫_{η=0}^{β} η \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη.

Thus

\begin{aligned}ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0) & = \frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η) + ∫_{η=β}^{1}(1 − η)\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη \\ & − ∫_{η=0}^{β} η \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη. \end{aligned} (24)

The two first terms of the righthand side are in 𝕃^{1}(𝒳^{N}, P_{N}), according to hypotheses (14), (15) and Fubini’s theorem. To see that the third one is also in 𝕃^{1}(𝒳^{N}, P_{N}), we will need to use hypothesis (18)

Coming back to the expression of \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η), we see that 𝔼_{P_{N}} (\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)) = 0 if and only if θ ↦ q(θ, X_{N}) is π a.s. constant P_{N} almost surely, and therefore that either 𝔼_{P_{N}} \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η) > 0 for all η ∈]0, 1], or \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η) = 0, P_{N} a.s. for all η ∈]0, 1]. In the latter case

(ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0)) = \frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η), P_{N} a.s.,

and therefore equation (20) of theorem A.1 holds. In the former case, using Fubini’s theorem and lemma A.1, we wee that for any ξ ∈ [β, α] and any ζ ∈]0, β],

log 𝔼_{P_{N}} \frac{∂^{2}}{∂η^{2}}_{|η=ξ}ℰ^{X_{1}^{N}} (η) = log 𝔼_{P_{N}} \frac{∂^{2}}{∂η^{2}}_{|η=ζ}ℰ^{X_{1}^{N}} (η) + ∫_{η=ζ}^{ξ} \frac{𝔼_{P_{N}} \frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η)}{𝔼_{P_{N}} \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)}dη

≥ log 𝔼_{P_{N}} \frac{∂^{2}}{∂η^{2}}_{|η=ζ}ℰ^{X_{1}^{N}} (η) − αχ_{β,α}. (25)

A first consequence of (25) is that η ↦ 𝔼_{P_{N}} \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η) is bounded on ]0, β] and therefore that (due to Fubini’s theorem and (15))

(X_{1}^{N}, η) ↦ \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η) ∈ 𝕃^{1}(𝒳^{N} × [0, 1], P_{N} ⊗ λ). (26)

This establishes the integrability of the third term of the righthand side of (24), and thus achieves to prove that ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0) ∈ 𝕃^{1}(𝒳^{N}, P_{N}).

Integrating with respect to P_{N}, we see from Fubini’s theorem and (26) that

(27) 𝔼_{P_{N}} [∫_{η=β}^{1}(1 − η)\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη − ∫_{η=0}^{β} η \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη]

= ∫_{η=β}^{1}(1 − η)𝔼_{P_{N}} [\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)] dη − ∫_{η=0}^{β} η𝔼_{P_{N}} [\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)] dη.

We can assume that 𝔼_{P_{N}} [\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)] > 0 for all η ∈]0, 1], since in the alter-

native situation we already proved (20). Remembering that \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η) ≥ 0 and coming back to equation (27), we see that we can troncate the first integral of the righthand side to obtain

(28) 𝔼_{P_{N}} [∫_{η=β}^{1}(1 − η)\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη − ∫_{η=0}^{β} η \frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)dη]

≥ ∫_{η=β}^{α}(1 − η)𝔼_{P_{N}} [\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)] dη − ∫_{η=0}^{β} η𝔼_{P_{N}} [\frac{∂^{2}}{∂η^{2}} ℰ^{X_{1}^{N}} (η)] dη.

Using (25), we see that

(29) inf_{ξ∈[β,α]} 𝔼_{P_{N}} [\frac{∂^{2}}{∂η^{2}}_{|η=ξ}ℰ^{X_{1}^{N}} (η)] ≥ exp(−αχ_{β,α})𝔼_{P_{N}} [ sup_{ζ∈]0,β]} \frac{∂^{2}}{∂η^{2}}_{|η=ζ}ℰ^{X_{1}^{N}} (η)] .

Combining equations (23), (27), (28), (29) and (19) we obtain

𝔼_{P_{N}} (ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0))

≥ 𝔼_{P_{N}} (\frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η))

+ [\frac{(α − β)(2 − α − β)}{2} exp(−αχ_{β,α}) − \frac{β^{2}}{2} ] sup_{ζ∈]0,β]} 𝔼_{P_{N}} [\frac{∂^{2}}{∂η^{2}}_{|η=ζ}ℰ^{X_{1}^{N}} ] (η)

≥ 𝔼_{P_{N}} [\frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η)] .

This ends the proof of (20). Note that we have not used yet the fact that P_{N} was supposed to be exchangeable. To prove (21) from (20), it is enough to notice that, due to the fact that P_{N} is exchangeable, for any θ ∈ Θ_{1}

γ_{β}(θ) = 𝔼_{P_{N}} (log q(θ, X_{N})) − βN𝔼_{P_{N}} [\frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η)] .

Appendix B. Another type of bound

Theorem A.1 is concerned with values of β in the region ]0, 1/2[. Another interesting value of the temperature is β = 1/2. In this section we will consider a set of assumptions ℋ′(N, β) which is the same as the set of hypotheses ℋ(N, β, α) of appendix A, except that we do not require conditions (18) and (19), and that condition (15) is strengthened to

(30) (X_{1}^{N}, η) ↦ η^{2} \frac{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}|log(q(θ, X_{N})) − \frac{∂}{∂η} ℰ^{X_{1}^{N}} (η)|^{3}]}{𝔼_{π(dθ)} [( ∏_{n=1}^{N−1} q(θ, X_{n}))^{β} (q(θ, X_{N}))^{η}]}

∈ 𝕃^{1}(𝒳^{N} × [0, 1], P_{N} ⊗ λ).

Under this slightly different set of hypotheses, we can write

ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (ϵ) = (1 − ϵ)\frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η) + \frac{(1 − β)^{2} − (β − ϵ)^{2}}{2} \frac{∂^{2}}{∂η^{2}}_{|η=β}ℰ^{X_{1}^{N}} (η)

+ ∫_{η=β}^{1} \frac{(1 − η)^{2}}{2} \frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η)dη + ∫_{η=ϵ}^{β} \frac{(η − ϵ)^{2}}{2} \frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η)dη.

Applying Lebesgue’s dominated convergence theorem to the righthand side under hypothesis (30), we see that the poinwise limit of the lefthand side when ϵ tends to zero, which is equal to ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0), is in 𝕃^{1}(𝒳^{N}, P_{N}). We can then come back to the second order expansion (23), and integrate up to α only (instead of one), to get the inequality

ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0) ≥ \frac{∂}{∂η}_{|η=β}ℰ^{X_{1}^{N}} (η) + \frac{(1 − β)^{2} − (1 − α)^{2} − β^{2}}{2} \frac{∂^{2}}{∂η^{2}}_{|η=β}ℰ^{X_{1}^{N}} (η)

+ ∫_{η=β}^{1} \frac{(1 − η)^{2} − (1 − α)^{2}}{2} \frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η)dη + ∫_{η=0}^{β} \frac{η^{2}}{2} \frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η)dη, P_{N} a.s.

Choosing α = 1 − \sqrt{1 − 2β}, to cancel the second order term, and integrating with respect to P_{N}, we obtain the following theorem :

Theorem B.1. Under the set of hypotheses ℋ′(N, β) described above,

ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0) ∈ 𝕃^{1}(𝒳^{N}, P_{N})

and

𝔼_{P_{N}} (ℰ^{X_{1}^{N}} (1) − ℰ^{X_{1}^{N}} (0)) ≥ sup_{θ∈Θ_{1}} (𝔼_{P_{N}} (log q(θ, X_{N})) − \frac{γ_{β}(θ)}{βN})

+ \frac{1}{24}(1 − \sqrt{1 − 2β})^{3}(1 + 3\sqrt{1 − 2β}) inf_{η∈[0,1−\sqrt{1−2β}]} 𝔼_{P_{N}} [\frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η)] .

Remark B.1. This theorem is interesting in cases when − inf_{η} 𝔼_{P_{N}} [\frac{∂^{3}}{∂η^{3}} ℰ^{X_{1}^{N}} (η)]

turns out to be small when compared to \frac{γ_{β}(θ)}{βN}.

Remark B.2. When (θ, x) ↦ q(θ, x) is bounded on Θ×𝒳, then ℋ′(N, β) is satisfied for any β ∈ [0, 1/2] and Θ_{1} = Θ.

Appendix C. Some technical lemma for countable parameter sets

Lemma C.1. For any lower bounded real measurable function g : Θ → ℝ, any probability distribution π ∈ ℳ_{+}^{1}(Θ),

\frac{𝔼_{π(dθ)}(g(θ) exp(−g(θ)))}{𝔼_{π(dθ)}(exp(−g(θ)))} ≤ inf_{θ∈Θ}(g(θ) + log \frac{1}{π(\{θ\})}).

Proof. Introducing a threshold value ϵ = log (\frac{1}{π(\{θ\})}) − 1, we can upper bound

g(θ′) by g(θ) + ϵ + (g(θ′) − g(θ) − ϵ)_{+} and write

\frac{𝔼_{π(dθ′)}(g(θ′) exp(−g(θ′)))}{𝔼_{π(dθ′)}(exp(−g(θ′)))} ≤ g(θ) + ϵ + \frac{𝔼_{π(dθ′)}((g(θ′) − g(θ) − ϵ)_{+} exp(−g(θ′)))}{𝔼_{π(dθ′)}(exp(−g(θ′)))}

≤ g(θ) + ϵ + \frac{exp(−ϵ)}{π(\{θ\})} sup_{λ∈ℝ}(λ exp(−λ))

≤ g(θ) + ϵ + \frac{exp(−ϵ − 1)}{π(\{θ\})}

≤ g(θ) + log \frac{1}{π(\{θ\})}.

Laboratoire de Probabilités et Modèles Aléatoires,, U.M.R. 7599 du C.N.R.S. Case 188, Université Paris 6,, bureau 4 E 19 bât Chevaleret, 16 rue Clisson,, F-75 013 Paris, tel: (33) (1) 44 27 85 15,, fax: (33) (1) 44 27 72 23

E-mail address: catoni@ccr.jussieu.fr