# Some Simple Formulas for Posterior Convergence Rates

Authors: Wenxin Jiang
Journal: International Scholarly Research Notices
 (2014)

---

## Abstract

We derive some simple relations that demonstrate
how the posterior convergence rate is related to two driving factors: a “penalized divergence” of the prior, which measures the ability of the prior distribution to propose a nonnegligible set of working models to approximate the true model and a “norm complexity” of the prior, which measures the complexity of the prior support, weighted by the prior probability masses. These formulas are explicit and involve no essential assumptions and are easy to apply. We apply this approach to the case with model averaging and derive some useful oracle inequalities that can optimize the performance adaptively without knowing the true model.


---

## Body

## 1. Introduction

In Jiang [1], there are some general results on the posterior convergence rate, which were very simple and easy to be applied. The current paper is related and developed from the ideas of Jiang [1]. There is no essential new idea behind the proofs. However, the results have been much simplified from the earlier groundbreaking works in this area, such as Ghosal et al. [2], Walker [3], and Ghosal et al. [4] so that the current work can be applied much more easily and displays the intrinsic driving factors behind the convergence rate more directly.The current paper cannot be used to derive new convergence rates better than what are achievable in the existing literature, except that the current convergence rate is described in adu2-divergence for any u∈(-1,0) (defined later), which is more general than the squared Hellinger distances d-1/22 (corresponding to u=-1/2). A recent work by Norets [5] actually has obtained convergence rates in a stronger Kullback-Leiber divergence d02 (corresponding to the limit u=0); however, the rate in d02 is suddenly much worse than the rate in d-1/22 (e.g., about 1/n in parametric cases, instead of about 1/n). Interestingly, although we allow any du2 for u∈(-1,0), the rate stays at about 1/n, which is essentially as good as in the Hellinger case at u=-0.5 and does not deteriorate to the case of the Kullback-Leibler limit at u=0.Aside from this technical difference in the divergence measures used in this current paper, the difference from the previous works is essentially esthetical. The key difference from the previous works is that the previous results are presented asbounds of the posterior probability (outside a neighborhood of the true density), while the current paper presents almost surebounds of the distance(or divergences) from the true density directly. Applications of previous works sometimes need to make a guess on the convergence rate and then check that it simultaneously satisfies several inequality conditions, while the current paper presents explicit formulas that are essentially assumption free.


## 2. Main Results

LetD denote the observed data generated from a probability distribution P0. Consider a prior distribution π supported on a set of densities PD. Define for a subset A⊂PD the posterior probability as Π(A)=∫f∈A‍f(D)π(df)/∫f∈PD‍f(D)π(df). Denote P0Π(A)=∫‍Π(A)P0(dD). Let ∪j∈NBj be a countable convex cover of A, so that A⊂∪j∈NBj, Bj is convex, and N is a countable set.Define the divergencedt2(p,q)=t-1∫‍p((p/q)t-1) between densities p and q, on a suitable dominating measure, for t>-1. (The Kullback-Leiber divergence corresponds to the limiting case of t=0; the squared Hellinger distance corresponds to the case t=-1/2; the χ2 divergence corresponds to the case t=1.) Then we have the following result.Proposition 1.
For anyu∈(0,1) and any t∈(0,∞), for any K⊂P, one has
(1)(P0Π(A)4)1+u/t≤∑j∈N‍{π(Bj)(1+sup⁡q∈Bj⁡(-ud-u2(p0D,qD)))1/uπ(K)(1+sup⁡q∈K(tdt2(p0D,qD)))-1/t}u.This result requires no assumption essentially. The relation displayed is explicit. In the result,p0D, qD are regarded as probability densities of the entire set of data D.Now consider the case with iid assumption, so thatD=(Y1,…,Yn), Y,Y1,…,Yn being iid (independent and identically distributed), generated from density p0 for a single copy Y. Let π be a prior distribution supported on a set P of densities of Y. Consider any A⊂P with any of its countable convex covers ∪j∈NBj. Using relations such as p0D=Πi=1np0(Yi) and 1+x≤ex for any real x, the previous result becomes as follows.Proposition 2.
For iid data with sample sizen, for any -1<-u<0<t<∞, any K⊂P, one has
(2)(P0Π(A)4)1+u/t≤∑j∈Nexp⁡⁡{-un([inf⁡q∈Bj⁡d-u2(p0,q)mmmmmmmmiimm-n-1ln⁡π(Bj)inf⁡q∈Bj]mmmmmmmmmm-[sup⁡q∈K⁡dt2(p0,q)mmmmmmmnmmmm-n-1ln⁡π(K)sup⁡q∈K])}.The only essential assumption here is iid. The relation displayed is explicit.We will now consider a sequence of densitiesp(n) for iid data, which are generated from the posterior distributions based on iid data with increasing sample sizes n, and study how they converge to the true density p0.Condition 1 (“posterior sequence” of random densities for iid data).
A “posterior sequence”p(n) (labeled by sample size n) of random density functions in P, in a probability space, satisfies, for any subset A⊂P,
(3)Pr⁡[p(n)∈A]=P0Π(A)≡∫‍[∫f∈A‍∏i=1nf(Yi)π(df)∫f∈P‍∏i=1nf(Yi)π(df)]∏i=1n‍p0(Yi)dYi.
Here P is a set of density functions, π() is the prior distribution of f∈P, and Π() is the fraction in the integrand, which can be regarded as the posterior distribution of f based on iid data D=(Y1,…,Yn).At any fixed sample sizen, this probability law is equivalent to assuming that p(n) is sampled from the posterior Π() given data D=(Y1,…,Yn), and D is an iid sample of Y with density p0. We will often omit the superscript and write p(n)=p.SupposeP can be covered by a finite number N- of the Bj's, each being an L1 ball with radius n-1/u. Then the following result can be obtained.Proposition 3.
Consider a “posterior sequence” of densitiesp for iid data satisfying Condition 1. For any u∈{1/2,1/3,1/4,…} and any 0<t<∞, with probability 1, for almost all large sample size n, one has
(4)d-u2(p0,p)≤dt2(p0,π)+n-1ln⁡[N-1/un2(u-1+t-1)],
where dt2(p0,π)≡inf⁡K⊂P[sup⁡q∈Kd2(p0,q)+n-1ln⁡(1/π(K))] and P is the support of the prior π.Here we define a “penalized divergence” dt2(p0,π)≡inf⁡K⊂P[sup⁡q∈Kd2(p0,q)+n-1ln⁡(1/π(K))], for some divergence d of a prior π from the true density p0.Remark 4.
The result can be extended to the continuously valuedu∈(0,1). This is because the dt divergence is monotonically increasing in t. For any d-u so that 1/u is not an integer, we can use a more stringent divergence d-u′ with the -u′ being the next larger value from the integer range {-1/2,-1/3,-1/4,…} to bound the convergence rate in d-u.Remark 5.
In this and other works, we notice that we often encounter in the convergence rate results a quantity similar to the “penalized divergence” of the form dt2(p0,π)≡inf⁡K[sup⁡q∈Kdt2(p0,q)+n-1ln⁡(1/π(K))], related to a prior π. This first part sup⁡q∈Kdt2(p0,q) describes the maximal divergence of a set K (proposed by a prior π) from p0. We can understand this part as the approximation error of the prior π when it is used to propose densities to approximate a true density p0. The second part penalizes an unlikely set K with a small prior π(K). Combining the two parts, we can perhaps try to interpret d2(p0,π) as the approximation error (away from p0) by a not-too-unlikely set proposed by a prior π. This “penalized divergence” is a critically important driving factor for determining the convergence rates in the previous results. It is noted that although this factor corresponds to the approximation ability of π, it already has a complexity penalty built in it implicitly. This is from the penalty against a small prior; the second part is n-1ln⁡(1/π(K)), which is, roughly speaking, about d/n, where d is the number of parameters proposed by the prior π (e.g., for a uniform prior π, for a small d-dimensional cube K with volume δd, we have π(K)∝δd).Remark 6.
The other factor behind the convergence rate is related to the complexity of the model, which is proportional ton-1ln⁡N- where N- is some number that increases with the number of small convex balls needed to cover the prior support of the model. Typically, this “complexity factor'' is roughly about d/n, up to some logarithm factors, where d is the dimension of the parameters involved in the prior. It is noted, however, that with model averaging the higher dimensional model can be downweighted by the model prior, so that effectively one can make d to be of order 1 for this complexity factor, so that the convergence rate will be controlled by the first factor (“the penalized divergence”) alone.The convergence rate result in Proposition3 can be extended to the case of model averaging, when the prior is π(m,df)=πmπ(df∣m), jointly over a model index m∈M in a set of nonoverlapping models M, and density f∈Pm (the support of prior given model m) (we assume nonoverlapping models for simplicity, where Pm∩Pm′=∅ for any two different model indexes m and m′. This is only a technical convention for defining the prior supports, which typically does not affect the real applications see, e.g., Section 3.1) and posterior Π(A)∝∑m∈M∫f∈Pm‍I((m,f)∈A)Πi=1nf(Yi)πmπ(df∣m) for an event A. In this case, let N-m=N((1/n)1/u,L1,Pm), the L1 balls of radius (1/n)1/u needed to cover the prior-support Pm under model m. Then we have the following, under the iid assumption.Proposition 7.
Consider a “posterior sequence” of densitiesp for iid data satisfying Condition 1. For any u∈{1/2,1/3,1/4,…} and any 0<t<∞, with probability 1, for almost all large sample size n, one has
(5)d-u2(p0,p)≤dt2(p0,π)+n-1ln⁡(n2(u-1+t-1)(∑m∈M‍πmuN-m)1/u),
where
(6)dt2(p0,π)≡inf⁡K∈P{sup⁡q∈K⁡dt2(p0,q)-n-1ln⁡π(K)}≤inf⁡m∈M,Km∈Pm⁡{sup⁡q∈Kmdt2(p0,q)mnmmmmmm-n-1ln⁡⁡[πmπ(Km∣m)]sup⁡q∈Km}=inf⁡m∈M⁡[dt2(p0,π(·∣m))-n-1ln⁡πm].P and Pm are supports of the mixing prior π=∑mπmπ(df∣m) and the model-m prior π(df∣m), respectively.This is an oracle inequality that achieves the best performance of all modelsm for the bound on the right hand side. Again, the convergence rate is displayed explicitly, and we will try to explain the driving factors of the convergence rate later. This is unlike the previous works where one has to conjecture a rate ϵ and check that it satisfies many conditions.So far, we have assumed existence of a finite covering number for the prior support, such asN- in Proposition 3 or N-m in Proposition 7. They determine the “complexity factor” as commented in Remark 6. A deeper analysis of the “complexity factor” is to regard it as an upper bound for a better complexity measure related to the prior π, developing an idea pioneered by Walker [3].Remark 8.
The complexity in Remark6 is not satisfactory when the prior support P is unbounded and the covering number N- is infinity. However, the proofs of the propositions can be easily adapted to show that the covering number N- can be replaced by ∑j∈Nπ(Bj)u from Proposition 2, where we have relaxed ∪jBj to be a cover of the entire prior support of P, and we have freedom in choosing the cover ∪jBj. Therefore, we can define a quantity that is related to the prior itself. Let the Nu(π) be the infimum of the lu norm [∑j∈Nπ(Bj)u]1/u over all such covers ∪jBj of P, where each Bj is an L1 ball of radius n-1/u. We may name it as the “lu-norm prior complexity” for covering the prior support. An unbounded prior support may still be coverable by infinitely many Bj's, so that Nu(π) is finite, even with an infinite covering number N-. Then we have a better way of formulating a bound corresponding to Proposition 3:
(7)d-u2(p0,p)≤dt2(p0,π)+n-1ln⁡[Nu(π)n2(u-1+t-1)],
where Nu(π) is the “lu-norm complexity” of this prior π defined in this remark.Remark 9.
We now describe heuristically how to bound the “norm complexity”Nu(π) defined in the previous remark in parametric models, where densities p∈P are parameterized by a d dimensional parameter θ, and a prior on θ induces a prior π on the densities in P. A more rigorous treatment is given in the example of Section 3.2. In typical situations with some smoothness conditions on the densities, we can relate the L1 distance between two densities pθ1 and pθ2 by the maximal norm |·|∞: ∫‍|p1-p2|≤cd|θ1-θ2|∞ for some constant c>1. Then, to cover the parameter space, we can use l∞ ball Aj's in the parameter space with radius h=(cdn1/u)-1, so that the corresponding densities cover the L1-ball Bi with the required radius n-1/u. These sets Aj, with small volumes vol(Aj)=(2h)d, can be used to form a fine partition of the parameter space, so that the norm ∑j∈Nπ(Bj)u=∑j∈Nπ(θ∈Aj)u=[∑j∈Nπ(θj)uvol(Aj)]vol(Aj)u-1≈[∫‍π(θ)udθ]((2h)d)u-1, where π(θj) is the prior density function evaluated at some intermediate point in the set Aj. The sum in the square bracket is a Riemann sum over a fine grid, which we will assume to be approximated by an integral under some regularity conditions, even if the domain may be unbounded. Therefore, we have an upper bound of the norm complexity as
(8)Nu(π)≲(∫‍π(θ)udθ)1/u(cdn1/u2)d(1-u)/u≤|π|u(cdn)d/u2,
for all large enough n. Assume that the prior density is Lu integrable in the parameter space, and the norm |π|u scales as (const)d as in the case of an iid prior π(θ)=∏j=1d‍π1(θj). Then the complexity term in the bound of Remark 8 can be derived as
(9)n-1ln⁡[Nu(π)n2(u-1+t-1)]=O(n-1dln⁡(nd)),
which increases with the dimension d.Remark 10.
Similar to Remark8, we have a better way of formulating a bound corresponding to Proposition 7:
(10)d-u2(p0,p)≤dt2(p0,π)+n-1ln⁡[Nu(π)n2(u-1+t-1)],
where Nu(π) is the “lu-norm complexity” of this prior π, which in this case should be the infimum of the lu norm [∑m∈M∑j∈Nm{πmπ(Bj∣m)}u]1/u over all such covers ∪m,jBmj of P, where each Bmj is an L1 ball of radius n-1/u, and under each model m, ∪j∈NmBmj represents a cover of its prior support Pm using possibly infinitely many balls. The defining expression of Nu(π) can also be related to the norm complexities of all the conditional priors π(·,m) given the model choices: Nu(π)=[∑m∈M{πmNu(π(·∣m))}u]1/u. With model averaging using some suitable weights πm, this term Nu(π) and its effect on the convergence rate no longer diverge with the complexity of the model, in contrast to the conclusion of Remark 9. The convergence rate is then mainly determined by the penalized divergence dt2(p0,π). An example below (in its second part) is used to illustrate this.


## 3. A Simple Example for Illustration

This is a simple binary regression example intended for illustration. We will see that model averaging can be used to derive nearly optimal convergence rates that are adaptive to the assumptions on the true model. In the first part, we will illustrate how to bound the penalized divergence with a uniform prior with a bounded support. In the second part, we will illustrate how to bound the norm complexity when the prior has an unbounded support.


### 3.1. When the Prior Has a Bounded Support

Consider a binary regression modelZ∣X~Bin(1,μ(X)), X∈Unif(0,1), where the true conditional mean function μ(X) is denoted as μ0(X)∈(δ,1-δ) (for some small positive δ), which is bounded away from 0 and 1, for any value of X. We consider an m-piecewise constant working model for the mean function μ. Suppose the prior is π=πmπ(θ1,…,θm∣m) where m indicates the m-piecewise constant model μ(x)=∑j=1mθjI[x∈[(j-1)/m,j/m)]. We consider an independent uniform prior π(θ1,…,θm∣m)=∏j=1mI(θj∈[0,1]). (For technically defining the prior supports to be nonoverlapping for different models, one can further require the θj's to be mutually distinct. The resulting prior would be unchanged almost everywhere and would not affect the discussions later.)We will consider two different setups of the true model.Setup (dense true model).
In the first setup, the trueμ0 has continuous derivative bounded by D. We call this a “dense” setup since we may need a large piecewise constant model (with large m increasing with sample size n) to approximate this quite arbitrary true mean function μ0.
To apply Proposition7, we will use -u=-1/2 and t=1. In the present case, we have d12(p1,p2)=∫01‍dx(μ1-μ2)2/(μ2(1-μ2)), ≤(δ(1-δ))-1∫01‍dx(μ1-μ2)2, if p1(z,x)=μ1z(1-μ1)1-z and p2(z,x)=μ2y(1-μ2)1-z. We will sometimes use the mean function μ's to denote the corresponding distances as d12(μ1,μ2) and so on.
The approximation property of the piecewise constants implies that, for any trueμ0(x), there exists a μ* in the support of π(·∣m) so that |μ0-μ*|<D/m everywhere. In fact, we can take μ*=∑j=1m‍θj*I[x∈[(j-1)/m,j/m)] where θj*=μ0((j-1)/m)∈(δ,1-δ). Now let μ be close to μ*, in the sense that μ=∑j=1mθjI[x∈[(j-1)/m,j/m)] and θj∈θj*±Δ, j=1,...,m, for some small Δ∈(0,δ). Take Km to be the set of all such densities of Bin(1,μ). Then μ∈(δ-Δ,1-δ+Δ) everywhere, since θj∈θj*±Δ and θj*∈(δ,1-δ) for all j.
Letp0 and p be the densities corresponding to μ0 and μ, respectively. Then sup⁡p∈Kmd12(p0,p)=sup⁡p∈Km∫01‍dx(μ0-μ)2/(μ(1-μ))≤sup⁡p∈Km∫01‍dx(|μ0-μ*|+|μ-μ*|)2/{min⁡x(μ(1-μ))}≤(D/m+Δ)2/((δ-Δ)(1-δ+Δ)) due to the triangle inequality. The prior probability over (m,Km) is πm(2Δ)m. Therefore, the “penalized divergence”
(11)d12(p0,π)≤inf⁡m,Δ{((δ-Δ)(1-δ+Δ)-1)(Dm+Δ)2mnmm+(mn)ln⁡(2Δ)-1+n-1ln⁡πm-1(Dm+Δ)2}.
We will take πm∝e-K(m-1)ln⁡n for some large enough constant K>0 and apply Proposition 7. (It can be shown that this will make the “complexity” term n-1ln⁡(n6(∑m=1∞πmN-m)2) negligible compared to d2(p0,π) (by showing N-m≤n2m, we omit the tedious details here).)
We can takem~n1/3 and Δ=1/n for an upper bound of the inf⁡m,Δ. Therefore, the “penalized divergence” d12(p0,π) and the resulting convergence rate d-1/22(p0,p) are both of order O(n-2/3ln⁡n), which is within a ln⁡n factor to the minimax optimal result. It is noted that the model averaging automatically achieves this near optimal rate.Setup (sparse true model).
Consider a second setup, where we assume that the true model is am0-piecewise constant, where we do not know the value m0. We call this a sparse case since we only need an m-piecewise constant model μ* to approximate the true mean function μ0 perfectly, where m=m0 can be much smaller than the choice of m~n1/3 in Setup 1.
Then modifying the above reasoning, we can bound the infimum in the “penalized divergence”d12(p0,π) by taking m=m0 and Δ=1/n and obtain (using |μ*-μ0|=0) the following:
(12)d12(p0,π)≤((δ-1n)(1-δ+1n))-1(0+1n)2+O(m0ln⁡nn)=O(m0ln⁡nn).
This and also the resulting posterior convergence rate d-1/22(p0,p) are, therefore, both close to the parametric rate O(m0/n), as if we knew m0 beforehand.In summary, the priorπ is adaptive in the sense that in either the dense or the sparse case, the resulting posterior distribution works nearly optimally, even if we do not really know whether the true model is dense or sparse.


### 3.2. When the Prior Has an Unbounded Support

In the example above, we have considered a uniform prior forπ(·∣m) with a bounded support. In this subsection, we will consider a parametrization in the log-odds scale, with an unbounded prior support, for illustrating how to calculate the norm complexity described in Remarks 8, 9, and 10. The model is still Z∣X~Bin(1,μ), X∈Unif(0,1), where the true μ, denoted as μ0, is bounded away from 0 and 1. We consider an m-piecewise constant working model for the mean function μ=∑j=1meθj/(1+eθj)I[x∈[(j-1)/m,j/m)]. Suppose the prior is iid for each “log-odds” parameter θj supported on R; then
(13)π=πmπ(θ1,…,θm∣m)=πm∏j=1m‍π(θj∣m).Consider two densities of(Z,X): p1,2=μ1,2z(1-μ1,2)1-z, with parameters θ1j's and θ2j's, respectively. Then one can easily derive a following relationship for the L1 distance: ∫‍|p1-p2|=2∫‍|μ1-μ2|≤(1/2)sup⁡j=1m|θ1j-θ2j|. For covering all the densities in this working model with L1 balls Bmj with radius n-1/u (u∈(0,1)), we can use the densities with parameters in l∞ balls [θs∈[jsh,(js+1)h]:s=1,…,m], with radius h/2=2n-1/u.ThenNu(π(·∣m))≤[∑j1=-∞∞⋯∑jm=-∞∞π(θ1∈[j1h,(j1+1)h],…,θm∈[jmh,(jm+1)h]∣m)u]1/u=[∏s=1m∑js=-∞∞π(θs∈[jsh,(js+1)h]∣m)u]1/u=[∑j=-∞∞π(θ1∈[jh,(j+1)h]∣m)u]m/u, since the priors of θ1,…,θm∣m are iid.Now assume that the prior density for eachθj (given model m) is continuous, symmetric, and decreasing from the origin π(θj∣m)=fm(|θj|) for some decreasing functions fm∈Lu(0,∞) (which can be satisfied by, e.g., independent N(0,1) priors or double-exponential densities).Then∑j=-∞∞π(θ1∈[jh,(j+1)h]∣m)u=2∑j=0∞π(θ1∈[jh,(j+1)h]∣m)u≤2∑j=0∞fm(jh)uhu-1≤[2hfm(0)u+∫-∞∞‍fm(|w|)udw]hu-1, where we used the decreasingness of fm in the last two steps. The integration exists since fm∈Lu(0,∞).Then we haveNu(π(·∣m))≤O(hm(u-1)/u)=O(nm(1-u)/u2), which is finite despite the unbounded priors support. Then according to Remark 10, Nu(π)=[∑m(πmNu(π(·∣m)))u]1/u will be O(n(1-u)/u2) if πm∝e-K(m-1)ln⁡n for some large enough constant K>0. So the norm complexity term in Remark 10 is of order O(ln⁡n/n), which, when compared with the last formula in Remark 9, behaves as if the dimension has become reduced to order O(1) by model averaging. Therefore, the norm complexity term does not affect the convergence rate significantly due to model averaging, and the convergence rate is mainly determined by the penalized divergence d12(p0,π). The bounding of the penalized divergence is similar to the example discussed in the previous subsection and we omit the details. The resulting convergence rates are essentially the same as when the uniform priors (with bounded supports) are used, despite the fact that we now allow priors with unbounded supports (such as normal priors in the parametrization of log-odds).


## 3.1. When the Prior Has a Bounded Support

Consider a binary regression modelZ∣X~Bin(1,μ(X)), X∈Unif(0,1), where the true conditional mean function μ(X) is denoted as μ0(X)∈(δ,1-δ) (for some small positive δ), which is bounded away from 0 and 1, for any value of X. We consider an m-piecewise constant working model for the mean function μ. Suppose the prior is π=πmπ(θ1,…,θm∣m) where m indicates the m-piecewise constant model μ(x)=∑j=1mθjI[x∈[(j-1)/m,j/m)]. We consider an independent uniform prior π(θ1,…,θm∣m)=∏j=1mI(θj∈[0,1]). (For technically defining the prior supports to be nonoverlapping for different models, one can further require the θj's to be mutually distinct. The resulting prior would be unchanged almost everywhere and would not affect the discussions later.)We will consider two different setups of the true model.Setup (dense true model).
In the first setup, the trueμ0 has continuous derivative bounded by D. We call this a “dense” setup since we may need a large piecewise constant model (with large m increasing with sample size n) to approximate this quite arbitrary true mean function μ0.
To apply Proposition7, we will use -u=-1/2 and t=1. In the present case, we have d12(p1,p2)=∫01‍dx(μ1-μ2)2/(μ2(1-μ2)), ≤(δ(1-δ))-1∫01‍dx(μ1-μ2)2, if p1(z,x)=μ1z(1-μ1)1-z and p2(z,x)=μ2y(1-μ2)1-z. We will sometimes use the mean function μ's to denote the corresponding distances as d12(μ1,μ2) and so on.
The approximation property of the piecewise constants implies that, for any trueμ0(x), there exists a μ* in the support of π(·∣m) so that |μ0-μ*|<D/m everywhere. In fact, we can take μ*=∑j=1m‍θj*I[x∈[(j-1)/m,j/m)] where θj*=μ0((j-1)/m)∈(δ,1-δ). Now let μ be close to μ*, in the sense that μ=∑j=1mθjI[x∈[(j-1)/m,j/m)] and θj∈θj*±Δ, j=1,...,m, for some small Δ∈(0,δ). Take Km to be the set of all such densities of Bin(1,μ). Then μ∈(δ-Δ,1-δ+Δ) everywhere, since θj∈θj*±Δ and θj*∈(δ,1-δ) for all j.
Letp0 and p be the densities corresponding to μ0 and μ, respectively. Then sup⁡p∈Kmd12(p0,p)=sup⁡p∈Km∫01‍dx(μ0-μ)2/(μ(1-μ))≤sup⁡p∈Km∫01‍dx(|μ0-μ*|+|μ-μ*|)2/{min⁡x(μ(1-μ))}≤(D/m+Δ)2/((δ-Δ)(1-δ+Δ)) due to the triangle inequality. The prior probability over (m,Km) is πm(2Δ)m. Therefore, the “penalized divergence”
(11)d12(p0,π)≤inf⁡m,Δ{((δ-Δ)(1-δ+Δ)-1)(Dm+Δ)2mnmm+(mn)ln⁡(2Δ)-1+n-1ln⁡πm-1(Dm+Δ)2}.
We will take πm∝e-K(m-1)ln⁡n for some large enough constant K>0 and apply Proposition 7. (It can be shown that this will make the “complexity” term n-1ln⁡(n6(∑m=1∞πmN-m)2) negligible compared to d2(p0,π) (by showing N-m≤n2m, we omit the tedious details here).)
We can takem~n1/3 and Δ=1/n for an upper bound of the inf⁡m,Δ. Therefore, the “penalized divergence” d12(p0,π) and the resulting convergence rate d-1/22(p0,p) are both of order O(n-2/3ln⁡n), which is within a ln⁡n factor to the minimax optimal result. It is noted that the model averaging automatically achieves this near optimal rate.Setup (sparse true model).
Consider a second setup, where we assume that the true model is am0-piecewise constant, where we do not know the value m0. We call this a sparse case since we only need an m-piecewise constant model μ* to approximate the true mean function μ0 perfectly, where m=m0 can be much smaller than the choice of m~n1/3 in Setup 1.
Then modifying the above reasoning, we can bound the infimum in the “penalized divergence”d12(p0,π) by taking m=m0 and Δ=1/n and obtain (using |μ*-μ0|=0) the following:
(12)d12(p0,π)≤((δ-1n)(1-δ+1n))-1(0+1n)2+O(m0ln⁡nn)=O(m0ln⁡nn).
This and also the resulting posterior convergence rate d-1/22(p0,p) are, therefore, both close to the parametric rate O(m0/n), as if we knew m0 beforehand.In summary, the priorπ is adaptive in the sense that in either the dense or the sparse case, the resulting posterior distribution works nearly optimally, even if we do not really know whether the true model is dense or sparse.


## 3.2. When the Prior Has an Unbounded Support

In the example above, we have considered a uniform prior forπ(·∣m) with a bounded support. In this subsection, we will consider a parametrization in the log-odds scale, with an unbounded prior support, for illustrating how to calculate the norm complexity described in Remarks 8, 9, and 10. The model is still Z∣X~Bin(1,μ), X∈Unif(0,1), where the true μ, denoted as μ0, is bounded away from 0 and 1. We consider an m-piecewise constant working model for the mean function μ=∑j=1meθj/(1+eθj)I[x∈[(j-1)/m,j/m)]. Suppose the prior is iid for each “log-odds” parameter θj supported on R; then
(13)π=πmπ(θ1,…,θm∣m)=πm∏j=1m‍π(θj∣m).Consider two densities of(Z,X): p1,2=μ1,2z(1-μ1,2)1-z, with parameters θ1j's and θ2j's, respectively. Then one can easily derive a following relationship for the L1 distance: ∫‍|p1-p2|=2∫‍|μ1-μ2|≤(1/2)sup⁡j=1m|θ1j-θ2j|. For covering all the densities in this working model with L1 balls Bmj with radius n-1/u (u∈(0,1)), we can use the densities with parameters in l∞ balls [θs∈[jsh,(js+1)h]:s=1,…,m], with radius h/2=2n-1/u.ThenNu(π(·∣m))≤[∑j1=-∞∞⋯∑jm=-∞∞π(θ1∈[j1h,(j1+1)h],…,θm∈[jmh,(jm+1)h]∣m)u]1/u=[∏s=1m∑js=-∞∞π(θs∈[jsh,(js+1)h]∣m)u]1/u=[∑j=-∞∞π(θ1∈[jh,(j+1)h]∣m)u]m/u, since the priors of θ1,…,θm∣m are iid.Now assume that the prior density for eachθj (given model m) is continuous, symmetric, and decreasing from the origin π(θj∣m)=fm(|θj|) for some decreasing functions fm∈Lu(0,∞) (which can be satisfied by, e.g., independent N(0,1) priors or double-exponential densities).Then∑j=-∞∞π(θ1∈[jh,(j+1)h]∣m)u=2∑j=0∞π(θ1∈[jh,(j+1)h]∣m)u≤2∑j=0∞fm(jh)uhu-1≤[2hfm(0)u+∫-∞∞‍fm(|w|)udw]hu-1, where we used the decreasingness of fm in the last two steps. The integration exists since fm∈Lu(0,∞).Then we haveNu(π(·∣m))≤O(hm(u-1)/u)=O(nm(1-u)/u2), which is finite despite the unbounded priors support. Then according to Remark 10, Nu(π)=[∑m(πmNu(π(·∣m)))u]1/u will be O(n(1-u)/u2) if πm∝e-K(m-1)ln⁡n for some large enough constant K>0. So the norm complexity term in Remark 10 is of order O(ln⁡n/n), which, when compared with the last formula in Remark 9, behaves as if the dimension has become reduced to order O(1) by model averaging. Therefore, the norm complexity term does not affect the convergence rate significantly due to model averaging, and the convergence rate is mainly determined by the penalized divergence d12(p0,π). The bounding of the penalized divergence is similar to the example discussed in the previous subsection and we omit the details. The resulting convergence rates are essentially the same as when the uniform priors (with bounded supports) are used, despite the fact that we now allow priors with unbounded supports (such as normal priors in the parametrization of log-odds).


## 4. Proofs

Proof of Proposition1.
P
0
Π
(
A
)
≤
P
0
ϕ
+
P
0
Π
(
A
)
(
1
-
ϕ
) for any “test” ϕ as a function of D valued in [0,1]. Consider
(14)P0Π(A)(1-ϕ)=P0[∫f∈A‍(f(D)/p0(D))(1-ϕ)π(df)∫‍(f(D)/p0(D))π(df)]≤P0∫f∈A‍(f(D)/p0(D))(1-ϕ)π(df)a+P0I[∫‍(f(D)p0(D))π(df)≤a]foranya>0,
where P0 represents the expectation under the true density p0.
P
0
∫
f
∈
A
‍
(
f
(
D
)
/
p
0
(
D
)
)
(
1
-
ϕ
)
π
(
d
f
)
=
∫
f
∈
A
‍
P
f
(
D
)
(
1
-
ϕ
)
π
(
d
f
) due to Fubini’s Theorem, where Pf represents the expectation under density f.
Using Markov's theorem, for anyt>0, we have
(15)P0I[∫‍(f(D)p0(D))π(df)≤a]≤atP0(∫‍f(D)π(df)p0(D))-t≤atP0(∫f∈K‍f(D)π(df)p0(D))-t,nmforanyKinthesupportofπ.=atπ(K)-tP0(∫f∈K‍(f(D)/p0(D))π(df)π(K))-t≤atπ(K)-tP0(∫f∈K‍(f(D)/p0(D))-tπ(df)π(K))mmmmmmmmmnmmdue to Jensen's inequality;=atπ(K)-t(∫f∈K‍P0(f(D)/p0(D))-tπ(df)π(K))mmmmmmnmmmmmmduetoFubini’sTheorem;≤atπ(K)-tsup⁡f∈K⁡P0(f(D)p0(D))-t.
All these combine to (*)
(16)P0Π(A)≤P0ϕ+∫f∈A‍Pf(D)(1-ϕ)π(df)a+atπ(K)-tsup⁡f∈KP0(f(D)p0(D))-t.
Now apply a result that is a straightforward extension of Ghosal et al. ([4], Lemma 6.1). For any convex set Bj, there exist ϕj such that for any α, β>0, u∈(0,1), sup⁡f∈Bj(αP0ϕj+βPf(1-ϕj))=sup⁡f∈Bj∫‍min⁡{(αp0),(βf)}≤sup⁡f∈Bj∫‍{(αp0)1-u(βf)u}=α1-uβusup⁡f∈BjP0(p0/f)-u.
Therefore, we can findϕj so that
(17)P0ϕj≤α-uβusup⁡f∈Bj⁡P0(p0f)-u≡λj-usup⁡f∈BjP0(p0f)-u,sup⁡f∈BjPf(1-ϕj)≤α1-uβu-1sup⁡f∈BjP0(p0f)-u=λj1-usup⁡f∈BjP0(p0f)-u.
Given anyλj>0, we can choose (α,β) so that α/β=λj in the above statement.
If we take∪j∈NBj to be a convex cover of A and define a combined test ϕ=max⁡j∈Nϕj and plug it into (*), we have
(18)P0Π(A)≤∑j∈NP0ϕj+∑j∈N‍∫f∈Bj‍Pf(D)(1-ϕj)π(df)a+atπ(K)-tsup⁡f∈K⁡P0(f(D)p0(D))-t≤∑j∈Nλj-usup⁡f∈BjP0(p0f)-u+∑j∈N‍π(Bj)λj1-usup⁡f∈BjP0(p0/f)-ua+atπ(K)-tsup⁡f∈KP0(f(D)p0(D))-t.
Therefore, we have(19)P0Π(A)≤∑j∈N‍(λj-u+π(Bj)λj1-ua)sup⁡f∈BjP0(p0f)-u+atπ(K)-tsup⁡f∈KP0(f(D)p0(D))-t.
Takeλj=(1-u)-1uaπ(Bj)-1 and
(20)a=[∑j∈N‍π(Bj)usup⁡f∈BjP0(p0/f)-u{π(K)-tsup⁡f∈KP0(p0/f)t}]1/(u+t)×{[(1-u)1-uuu]-1ut-1}1/(u+t).
We get(21)P0Π(A)≤c(u,t)(∑j∈N‍{π(Bj)[sup⁡f∈Bj⁡P0(p0/f)-u]1/uπ(K)[sup⁡f∈KP0(p0/f)t]-1/t}u)t/(u+t),
where c(u,t)=(t/(t+u))-t/(t+u)(u/(t+u))-u/(t+u)(uu(1-u)1-u)-t/(u+t)≤4. Then notice that P0(p0/f)t=1+tdt2(p0,f); we obtain the proof of Proposition 1. (For notational convenience, the densities which appeared in the proof here, such as p0 and f, are the densities for the entire data set p0D and fD, resp., and we do not assume iid.)Proof of Proposition2.
Use the fact that, for anyt∈(-1,0)∪(0,∞),
(22)1+tdt2(p0D,fD)=P0(p0DfD)t=∫‍p0D(p0DfD)t=(∫‍p0(p0f)t)n,duetotheiidassumption.=(1+tdt2(p0,f))n≤etndt2(p0,f).
This leads to the proof by applying Proposition1.Proof of Proposition3.
This is a special case of Proposition7, where πm focuses on only one model.Proof of Proposition7.
Repeat the proofs of Propositions1 and 2 for the case with model averaging, with the support of prior being P=∪m∈MPm, where Pm is the support of π(·∣m).
Suppose the convex cover ofA∩P is doubly indexed as ∪m∈M∪j∈NmBmj, where Nm has cardinality at most N-m and ∪j∈NmBmj is a convex cover of the support A∩Pm. Then the result in Proposition 2 holds with
(23)(P0Π(A)4)1+u/t≤∑m∈M,j∈Nmexp⁡{[nsup⁡q∈Kdt2(p0,q)-ln⁡π(K)]-u([ninf⁡q∈Bmj⁡du2(p0,q)mmmmmmmimimmmmm-ln⁡[πmπ(Bmj∣m)]inf⁡q∈Bmj]mmmmmmmiiimmmm-[nsup⁡q∈Kdt2(p0,q)-ln⁡π(K)])}.
In Proposition2, let A=[f:d-u2(p0,f)>ϵ].
Suppose all the convex setsBmj are such that inf⁡j,minf⁡f∈Bmjd-u2(p0,f)>δ. Then we have (†)
(24)(P0Π(A)4)1+u/t≤∑m∈M‍πmuN-m×exp⁡⁡{-un(δ-[sup⁡q∈Kdt2(p0,q)-n-1ln⁡π(K)])},
where N-m is an upper bound for the number of convex sets Bmj needed to cover A∩Pm.
Now we try to define the convex setsBmj in more detail. They are used to cover A, so without generality, each Bmj contains a point in A, say p1, which is not close to p0 since d-u2(p0,p1)>ϵ. If Bmj is small so that any two points are close together, then any point p2 in Bmj (which may fall outside   A) can be made to be also not close to p0, so that d-u2(p0,p2)>δ for some δ>0 related to ϵ. This would be easy to establish by a triangular inequality, were it not for the difficulty that the divergence d-u is not a true distance for u≠1/2. So we would not be able to say, for example, that Bmj should be a small d-u-ball.
To resolve this difficulty, we derive the following inequalities:(25)u|d-u2(p0,p1)-d-u2(p0,p2)|≤∫p01-u|p1u-p2u|≤{∫‍|p1u-p2u|1/u}u
due to Hölder's inequality, and for u=1/k for any k=2,3,4,…, we have |p1u-p2u|1/u=|p11/k-p21/k||p11/k-p21/k|k-1≤|p11/k-p21/k|∑i=0k-1‍|p1i/kp2(k-1-i)/k|2k-1=|(p11/k)k-(p21/k)k|2k-1, so that
(26){∫‍|p1u-p2u|1/u}u≤2(∫‍|p1-p2|)u.
Therefore, ifBmj is an L1 ball with small enough radius λ, then any point p2 in Bmj has a not too small divergence d-u2(p0,p2)≥ϵ-|d-u2(p0,p1)-d-u2(p0,p2)|≥ϵ-u-12(2λ)u≥ϵ-u-14λu=δ. We can take λ=[(u/4)(ϵ-δ)]1/u. The L1 balls are also convex as required. We will take ϵ-δ=4/(nu). Then the radius λ=(1/n)1/u. Therefore, we conclude that we will take Bmj's to be small L1 balls with radius n-1/u.
Now we try to findN-m, an upper bound of the number of such small balls needed to cover A∪Pm. We can use this upper bound N-m≡N((1/n)1/u,L1,Pm), the L1 balls of radius (1/n)1/u needed to cover the entire prior-support Pm under model m.
Then (†) implies, for any ϵ>0, (‡),
(27)(P0Π(d-u2(p0,p)>ϵ)4)1+u/t≤exp⁡⁡{-un(ϵ-ln⁡(e4∑m∈MπmuN-m)(nu)-d(p0,π))},
where dt2(p0π)≡inf⁡K∈P[sup⁡q∈Kdt2(p0,q)-n-1ln⁡π(K)] and P is the support of the prior.
Let the probability in (‡) be bounded by 4/(e-2/(1+u/t)n)2 under a choice of ϵ=ϵn for the right-hand side of (‡). Then the event [d-u2(p0,p)≤ϵn] will happen for all large enough n, almost surely, due to the Borel-Cantelli lemma.
Then(28)(e-2/(1+u/t)n)-2(1+u/t)=exp⁡⁡{-un(ϵn-ln⁡(e4∑m∈MπmuN-m)(nu)mmmmmmmmm-d(p0,π)ln⁡(∑m∈MπmuNmπmuNm)nu)}.
This leads to(29)ϵn=[2(1+u/t)ln⁡n+ln⁡(∑m∈MπmuN-m)](nu)+dt2(p0,π).
The quantitydt2(p0,π)=inf⁡K∈P[sup⁡q∈Kdt2(p0,q)-n-1ln⁡π(K)], under a mixture prior π(K)=∑s∈M‍πsπ(K∣s), can be bounded by taking K=Km⊂Pm, for any m∈M, as inf⁡K[sup⁡q∈Kdt2(p0,q)-n-1ln⁡π(K)≤inf⁡minf⁡Km{sup⁡q∈Kmdt2(p0,q)-n-1ln⁡[πmπ(Km∣m)]}≡inf⁡m[dt2(p0,π(·∣m))-n-1ln⁡πm].



---

*Source: 469340-2014-10-29.xml*