Submitted to the Annals of Statistics
arXiv: arXiv:0000.0000

arXiv:1508.07929v4 [] 19 Nov 2016

ON THE CONTRACTION PROPERTIES OF SOME
HIGH-DIMENSIONAL QUASI-POSTERIOR
DISTRIBUTIONS
By Yves F. Atchadé∗
University of Michigan
We study the contraction properties of a quasi-posterior distribution Π̌n,d obtained by combining a quasi-likelihood function and
a sparsity inducing prior distribution on Rd , as both n (the sample
size), and d (the dimension of the parameter) increase. We derive
some general results that highlight a set of sufficient conditions under which Π̌n,d puts increasingly high probability on sparse subsets of
Rd , and contracts towards the true value of the parameter. We apply
these results to the analysis of logistic regression models, and binary
graphical models, in high-dimensional settings. For the logistic regression model, we shows that for well-behavedpdesign matrices, the
posterior distribution contracts at the rate O( s⋆ log(d)/n), where
s⋆ is the number of non-zero components of the parameter. For the
binary graphical model, under some regularity conditions, we show
that a quasi-posterior analog of the neighborhood
p selection of [29]
contracts in the Frobenius norm at the rate O( (p + S) log(p)/n),
where p is the number of nodes, and S the number of edges of the
true graph.

1. Introduction. Let Z (n) denote a sample space equipped with a reference sigma-finite measure denoted dz. The upper script n represents the
sample size. Let Z be a Z (n) -valued random variable that we model as hav(n)
(n)
ing distribution Pθ given a parameter θ ∈ Rd . We assume that Pθ has a
(n)
density fn,θ : Pθ (dz) = fn,θ (z)dz. Let Π be a prior distribution on Rd . The
resulting posterior distribution for learning the parameter θ is the random
probability measure
R
fn,θ (Z)Π(dθ)
, A meas. ⊆ Rd .
A 7→ R A
f
(Z)Π(dθ)
d
n,θ
R

In practice, many inference problems are best tackled using quasi-likelihood
(or pseudo-likelihood) functions. In the Bayesian framework, this leads to a
∗

Supported in part by NSF grant DMS 1228164 and DMS 1513040
MSC 2010 subject classifications: Primary 62F15, 62Jxx
Keywords and phrases: Quasi-Bayesian inference, High-dimensional inference, Bayesian
Asymptotics, Logistic regression models, Discrete graphical models

1

2

YVES F. ATCHADÉ

quasi-Bayesian inference.
R Let (θ, z) 7→ qn,θ (z) denote a jointly measurable
function such that 0 < Rd qn,θ (z)Π(dθ) < ∞, almost surely [dz]. Substituting qn,θ in place of fn,θ yields the quasi-posterior (QP) distribution
R
def A qn,θ (Z)Π(dθ)
, A ⊆ Rd .
(1.1)
Π̌n,d (A|Z) = R
q
(Z)Π(dθ)
Rd n,θ
Although Π̌n,d is not a posterior distribution in the usual sense, it possesses
the property that it is a probability distribution obtained by tilting a prior
distribution using a likelihood-like function. Hence, to the extent that the
quasi-likelihood function θ 7→ qn,θ (Z) contains information about the true
value of the parameter θ, one can expect the same from the quasi-posterior
distribution (1.1), in which case valid inferential procedures can be derived
using Π̌n,d . This idea is perhaps best seen by noting that (1.1) is a solution
of the minimization

 Z
log qn,θ (Z)µ(dθ) + KL(µ|Π) ,
min −
µ≪Π

Rd

def R
where KL(µ|Π) = Rd log(dµ/dΠ)dµ is the KL-divergence between µ and
Π, and where the minimization is over all probability measures that are
absolutely continuous with respect to the prior Π. We refer to [36] for more
details (and in particular to Proposition 5.1 of that paper for a proof of the
above statement). The implication of this result is that, under appropriate
regularity conditions, one can expect the QP distribution to concentrate
around the maximizer of the function θ 7→ log qn,θ (Z), provided that the
prior distribution does not prevent it. The goal of this paper is to formalize
this idea for a class of statistical models.
As pointed out to us by a referee, QP distributions are commonly used
in the PAC-Bayesian framework to aggregate estimators ([28, 15, 17, 1, 2]).
However in this literature the emphasis is typically on the estimators, not
on the QP distributions themselves. An influential work on quasi-Bayesian
procedures is [16], which subsequently led to the development of quasiBayesian inference in semi-parametric modeling, particularly models arising from moment and conditional moment restrictions ([26, 35, 22, 24]).
Approximate Bayesian computation (ABC) methods (see e.g. [27] and the
references therein) are also popular quasi-Bayesian procedures.
The present paper is motivated by the idea that quasi-Bayesian inference
holds a great potential for dealing with high-dimensional statistical models. For some of these models, a likelihood-based inference is intractable,
and this has impeded somewhat the applicability of the Bayesian frame-

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

3

work in this area. However, M-estimation procedures that maximizes various quasi/pseudo-likelihood functions are often readily available. Using the
quasi-Bayesian framework, these quasi-likelihood functions can be easily employed to derive tractable quasi-Bayesian procedures.
We study the behavior of the QP distribution (1.1) when the prior distribution Π is given by
X
πδ Π(dθ|δ),
(1.2)
Π(dθ) =
δ∈∆d

def

for a discrete distribution {πδ , δ ∈ ∆d } on ∆d = {0, 1}d , and a sparsity
inducing prior Π(dθ|δ) on Rd , that we build as follows. Given δ, the components of θ are independent, and for 1 ≤ j ≤ d,

Dirac(0)
if δj = 0
(1.3)
θj |δ ∼
,
Laplace(ρ) if δj = 1
where Dirac(0) is the Dirac measure on R with full mass at 0, and Laplace(ρ)
denotes the Laplace distribution with parameter ρ > 0. The marginal prior
distribution of θj implied by (1.3) belongs to the class of spike-and-slab
priors ([30]).
(n)
We work under the assumption that Z ∼ Pθ⋆ for some θ⋆ ∈ Rd . When d
is assumed fixed and n → ∞, it is known from the initial work of [16] that
Π̌n,d concentrates around θ⋆ , and is asymptotically Gaussian (when properly
scaled). Infinite-dimensional extensions of such results have recently been
studied ([26, 18, 22]). The present paper focus on the case where Π̌n,d arises
from a high-dimensional parametric model with the sparsity inducing prior
(1.2-1.3), and the results that we derive substantially extend previous works
by [13, 24]. More precisely, we derive a general result (Theorem 3) that highlights the key determinants that control the convergence and convergence
rate of Π̌n,d towards θ⋆ . The theorem is obtained by combining ideas from
[13] together with a general methodology for studying high-dimensional Mestimators synthesized in [31], as well as an important technical result by
[23] on the existence of test functions.
We apply these results to the Bayesian analysis of high-dimensional logistic regression models. We derive a non-asymptotic result (Theorem 4) that
shows that for large d, and appropriately large sample size n, the resulting
posterior distribution Π̌n,d puts a high probability on sparse subsets of Rd ,
and contracts towards the true value of the parameter θ⋆ as n, d → ∞, at
the rate
!
r
s⋆ log(d)
,
O
n

4

YVES F. ATCHADÉ

where s⋆ = kθ⋆ k0 . The constant in the big-O notation depends crucially on
some smallest restricted eigenvalues of the Fisher information matrix of the
model.
We also apply the results to a quasi-Bayesian inference of high-dimensional
binary graphical models. Discrete graphical models are known to pose significant difficulties due to the intractable nature of the likelihood function.
A very successful frequentist approach to deal with large graphical models
is the neighborhood selection method of [29] initially proposed for Gaussian
graphical models, and extended to the Ising model by [32]. We analyze a
quasi-Bayesian version of neighborhood selection applied to binary graphical
models. We show that as n, p → ∞ (where p is the number of nodes in the
graph), provided that n is sufficiently large, the QP distribution obtained
from neighborhood selection contracts towards the true model parameter θ⋆
in the Frobenius norm at the rate
!
r
(p + S) log(p)
,
O
n
where S is the number of edges in the graph defined by θ⋆ . This convergence
rate is the same as in the Gaussian case with a full likelihood inference ([9]),
and compares very well with the best existing frequentist results. For inneighborhood
selection
stance [34] shows that the scaled g-Lasso version
 of

p
in the Gaussian case converges at the rate O s⋆ log(d)/n in the spectral norm, where s⋆ is the maximum degree of the graph defined by θ⋆ . In
general, faster convergence rate can be achieved if one is only interested in
components of the matrix. To illustrate this we analyze the contraction of
def
Π̌n,d in the norm |||θ||| = maxj kθ·j k2 , where θ·j is the j-th column of θ. We
show that in this norm, the QP distribution obtained from neighborhood
selection contracts towards θ⋆ at the rate
!
r
s⋆ log(p)
,
O
n
where here s⋆ is the maximum degree of the graph defined by the true
parameter θ⋆ . Furthermore, the sample size n required for this result to
hold is milder, and comparable to the sample size requirement in simple
high-dimensional logistic regressions.
An important issue not addressed in this work is how to obtain Monte
Carlo samples from the QP distribution (1.1). It is well known that posterior and quasi-posterior distributions built from discrete-continuous mixture
priors as in (1.2)-(1.3) are computational difficult to handle with standard

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

5

Markov Chain Monte Carlo algorithms. However there has been some recent progress, including the STMaLa of [33], or the Moreau approximation
approach of the author developed in [5]. We point the reader to these works
for more details and some additional references. Further discussion of computational methods can be in [13].
The remainder of the paper is organized as follows. First we close the
introduction with some notation that will be used throughout the paper.
Section 2 develops a general analysis of the QP distribution Π̌n,d . The applications to logistic regression models and binary graphical models is discussed
in Section 3. The proof of Theorem 3 is presented in Section 5, while the
remaining proofs are gathered in the supplementary material [3].
1.1. Notation. For an integer d ≥ 1, we equip the Euclidean space Rd
with its usual Euclidean inner product h·, ·i, associated norm k · k2 , and
def

its Borel sigma-algebra. We set ∆d = {0, 1}d . We will also use the followdef Pd
def Pd
def
ing norms on Rd : kθk1 =
j=1 |θj |, kθk0 =
j=1 1{|θj |>0} , and kθk∞ =
max1≤j≤d |θj |.
For δ ∈ ∆d , µd,δ denotes the product measure on Rd defined as
def

µd,δ (dθ) =

d
Y

νδj (dθj ),

j=1

where ν0 (dz) is the Dirac mass at 0, and ν1 (dz) is the Lebesgue measure on
R. For θ, θ ′ ∈ Rd , θ · θ ′ ∈ Rd denotes the component-wise product of θ and
def
θ ′ : (θ · θ ′ )j = θj θj′ , 1 ≤ j ≤ d. And for δ ∈ ∆d , we set δc = 1 − δ, that is
def

δjc = 1 − δj , 1 ≤ j ≤ d. For θ ∈ Rd , the sparsity structure of θ is the element
δ ∈ ∆d defined as δj = 1{|θj |>0} , 1 ≤ j ≤ d.

Throughout the paper e denotes the Euler number, and m
q is the combinatorial number m!/(q!(m − q)!). For x ∈ R, the notation ⌈x⌉ represents the
smallest integer larger of equal to x, and sign(x) is the sign of x (sign(x) = 1
if x > 0, sign(x) = −1 if x < 0, and sign(x) = 0 if x = 0). Finally, for θ ∈ Rd ,
def

and A ⊂ Rd , θ + A = {θ + u, u ∈ A}.

2. Contraction properties of the quasi-posterior distribution Π̌n,d .
We consider the QP distribution (1.1) on Rd , with the prior distribution
(1.2-1.3). Using the notation of Section 1.1, Π̌n,d can be written as
(2.1)

Π̌n,d (dθ|Z) ∝ qn,θ (Z)

X

δ∈∆d

πδ

 ρ kδk0
2

e−ρkθk1 µd,δ (dθ).

6

YVES F. ATCHADÉ

We are interesting in the contraction behavior of Π̌n,d for large n, d. We
take the usual frequentist view of Bayesian procedures by assuming the
following.
H 1.

(n)

There exists θ⋆ ∈ Rd such that Z ∼ Pθ⋆ (dz) = fn,θ⋆ (z)dz.
(n)

We write E(n) for the expectation operator with respect to Pθ⋆ (dz).
We also make the basic assumption that the quasi-likelihood function is
log-concave and smooth, and we use the notation ∇ log qn,u (z) to denote
the derivative of the map θ 7→ log qn,θ (z) at u. The j-th component of
∇ log qn,u (z) is written as (∇ log qn,u (z))j .
H 2.
tiable.

For all z ∈ Z (n) , the map θ 7→ log qn,θ (z) is concave and differen-

Remark 1. The assumption that the function θ 7→ log qn,θ (z) is concave
is imposed mostly for simplicity, and is not crucial to derive the main result
(Theorem 3). In fact, this assumption is not used in Theorem 3-(2). However,
in the application of Theorem 3, concavity is typically crucial to control the
events En that appear in the theorem.
Following [13], we specify the prior {πδ , δ ∈ ∆d } as follows.
d −1
H 3. For all δ ∈ ∆d , πδ = gkδk0 kδk
, for a discrete distribution
0
{gs , 0 ≤ s ≤ d}, for which there exist positive universal constants c1 , c2 ,
c3 ≥ c4 such that

(2.2)

c1
c2
gs−1 ≤ gs ≤ c gs−1 , s = 1, . . . , d.
dc3
d4

Remark 2. This assumption guarantees that the prior distribution concentrates on sparse subsets of Rd . Note that {gs } is the distribution of
the number of non-zero components produced by the prior. The assumption in (2.2) guarantees that for d large enough so that dcc24 < 1, we have
gs ≤ ( dcc24 )s g0 , and the rate dcc24 gets smaller with d.
[14] has several examples of prior distributions that satisfy H3. For instance if, for some hyper-parameter u > 1, q ∼ Beta(1, du ), and given q, we
draw independently δj ∼ Ber(q), then the marginal distribution of δ in this
case satisfies H3, with c1 = 1/2, c2 = 1, c3 = u and c4 = u − 1.

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

7

We study the contraction properties of Π̌n,d towards θ⋆ . We borrow a
strategy developed mostly for the analysis of high-dimensional M-estimators,
that consists in identifying a “good” subset En of the sample space Z (n) on
which the map θ 7→ qn,θ (Z) has good curvature properties (see e.g. [31] for
an excellent presentation of these ideas). Using this idea, the task at hand
then boils down to controlling the probability of the set En and showing
that Π̌n,d has good contraction properties when Z ∈ En . To that end, and
to shorten notation, we introduce the (Bregman divergence) function
def

Ln,θ (z) = log qn,θ (z)−log qn,θ⋆ (z)−h∇ log qn,θ⋆ (z), θ − θ⋆ i , θ ∈ Rd , z ∈ Z (n) .
This function plays a key role in informing on the curvature of the objective
function θ 7→ log qn,θ (Z) around θ⋆ . However, in high-dimensional settings,
it is typically not realistic to assume that θ 7→ log qn,θ (Z) has good curvature
on the entire parameter space Rd . As well explained in [31], one should look
at restrictions of Ln,θ (z) to interesting subsets of Rd .
We will use a rate function to express the curvature of θ 7→ log qn,θ (Z).
Throughout the paper, a continuous function r : [0, ∞) → [0, ∞) is a rate
function if r is strictly increasing, r(0) = 0, and limx↓0 r(x)/x = 0. Given a
rate function r, and a ≥ 0, we define
(2.3)

def

φr (a) = inf{x > 0 : r(z) ≥ az, for all z ≥ x},

with the convention that inf ∅ = +∞. The main example of a rate function
is r(x) = τ x2 , for some τ > 0 (for linear regression problems). However,
the examples below are related to logistic regression and the rate function
r(x) = τ x2 /(1 + bx) is used.
A non-empty subset Θ of Rd is a cone if for all λ ≥ 0, and all x ∈ Θ,
λx ∈ Θ. We will say that a cone Θ is a split cone if u·x ∈ Θ for all x ∈ Θ, and
all u ∈ {−1, 1}d (we recall that the notation u · x denotes the component-bycomponent product). Split cones serve as generalizations of sparse subsets
of Rd . The archetype example of a split cone is the set of s-sparse elements:
{θ ∈ Rd : kθk0 ≤ s}. However in some problems, one might have to work
with sparse elements with some additional structure, and this motivates the
introduction of the split cones. A particularly important example of a split
cone is the set of elements of Rd with the same sparsity structure as θ⋆ :
n
o
def
(2.4)
Θ⋆ = θ ∈ Rd : θj = 0 for all j s.t. θ⋆j = 0 .
Another important example of split cone that we will use is the set




X
def
N = θ ∈ Rd : θ 6= 0, and
|θj | ≤ 7kθ · δ⋆ k1 ,


j: δ⋆j =0

8

YVES F. ATCHADÉ

where δ⋆ denote the sparsity structure of θ⋆ : δ⋆j = 1{|θ⋆j |6=0} , 1 ≤ j ≤ d.
Given a rate function r, and a split cone Θ ⊆ Rd , we set
(2.5)


1
def
(n)
Ěn,1 (Θ, r) = z ∈ Z : for all θ ∈ θ⋆ + Θ, Ln,θ (z) ≤ − r(kθ − θ⋆ k2 ) .
2
Here as in classical Bayesian asymptotics, in order to control the normalizing constant of the quasi-posterior distribution, we need a lower bound on
the function θ 7→ Ln,θ (z). Again, a restricted version will suffice. For L ≥ 0,
we set
(2.6)


L
def
(n)
2
ˆ
En,1 (Θ, L) = z ∈ Z : for all θ ∈ θ⋆ + Θ, Ln,θ (z) ≥ − kθ − θ⋆ k2 .
2
Finally, for λ > 0 we set
(
(2.7)

def

En,0 (Θ, λ) =

z∈Z

(n)

λ
:
sup
|h∇ log qn,θ⋆ (z), ui| ≤
2
u∈Θ, kuk2 =1

)

.

The main idea behind these definitions is that on the event {Z ∈ Eˆn,1 (Θ, L)∩
Eˇn,1 (Θ, r)} the quasi-log-likelihod function θ 7→ log qn,θ (Z) has very nice
curvature properties when restricted to the set θ⋆ + Θ. The definition of
En,0 (Θ, λ) implies that on the event {Z ∈ En,0 (Θ, λ)}, θ⋆ is close to the
maximizer of the map θ 7→ log qn,θ (Z). Hence the set En,0 (Θ, λ)∩ Eˆn,1 (Θ, L)∩
Eˇn,1 (Θ, r) is our example of a “good set”, and on that set, we expect Π̌n,d (·|Z)
to have good concentration properties around θ⋆ . This is the substance of
the next result. Before stating the main theorem, we introduce few more
def
notation. For M > 0, let Bd (Θ, M ) = {θ ∈ θ⋆ + Θ, s.t. kθ − θ⋆ k2 ≤
M }. For ǫ > 0, let D(ǫ, Bd (Θ, M )) denote the ǫ-packing number of the ball
Bd (Θ, M ), defined as the maximal number of points in Bd (Θ, M ) such that
the k·k2 -distance between any pair of such points is at least ǫ.
def

Theorem 3. Assume H1-H3, and set s⋆ = kθ⋆ k0 . Suppose that d is
such that dc4 ≥ 8c2 . Let Θ̄ ⊇ Θ⋆ be a split cone, L̄ ≥ 0, λ̄ ≥ 0, and a rate

def
function r be such that ǭ = φr 2λ̄ is finite.
def

1. Set En = En,0 (Rd , ρ) ∩ Ên,1 (Θ⋆ , L̄) ∩ Ěn,1 (N , r). Then for any integer

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

9

k ≥ 0,
h
n
o i
(2.8) E(n) Π̌n,d θ ∈ Rd : kθk0 ≥ s⋆ + k |Z ≤ P(n) [Z ∈
/ En ]

s   

4c2 k
4L̄ ⋆ d
,
+ 2ea 4 + 2
ρ
dc4
s⋆

√ 
where a = − 21 inf x>0 r(x) − 4ρ s⋆ x , if N 6= ∅, and a = 0 if N = ∅.
def

2. Set En = En,0 (Θ̄, λ̄) ∩ Ên,1 (Θ⋆ , L̄) ∩ Ěn,1 (Θ̄, r). For any M0 > 2,

(2.9)



/ En ]
E(n) Π̌n,d θ ∈ θ⋆ + Θ̄ : kθ − θ⋆ k2 > M0 ǭ |Z ≤ P(n) [Z ∈
s ⋆ X
   c 3 s ⋆ 
2
X
1 jM0 ǭ
1 jM0 ǭ
ρ
d
d
+
Dj e− 8 r( 2 ) +2
e− 8 r( 2 ) e3ρc0 jM0ǭ ,
1+
c1
s⋆
L̄
j≥1

j≥1

def

where Dj = D
def



jM0 ǭ
2 , Bd (Θ̄, (j


+ 1)M0 ǭ) , and where

c0 = supu∈Θ̄ supv∈Θ̄, kvk2 =1 | hsign(u), vi |.
Proof. See Section 5.1.

Theorem 3-Part(1) shows that for ρ, L̄ and r such that the event {Z ∈
En,0 (Rd , ρ) ∩ Eˆn,1 (Θ⋆ , L̄) ∩ Ěn,1 (N , r)} has high probability, one can use the
second term on the right-hand side of (2.8) to establish that the concentration of the prior on sparse subsets (as assumed in H3) is inherited by
the quasi-posterior distribution.
In the logistic regression example below,

s⋆
4L̄
a
is O(ecs⋆ log(d) ), for some constant c.
we show that the term e 4 + ρ2

And since sd⋆ ≤ es⋆ log(de) , it follows that for such models the right-side of
(2.8) becomes small for k of the order of (c/c4 )s⋆ . The same is true for linear
regression models ([13]).
Part (2) of the theorem shows that if λ̄, L̄, the split cone Θ̄ and the rate
function r are well chosen such that the event {Z ∈ En,0 (Θ̄, λ̄) ∩ Ên,1 (Θ⋆ , L̄) ∩
Eˇn,1 (Θ̄, r)} has high probability, then the convergence rate of the quasiP
1 jM0 ǭ
posterior distribution is controlled mainly by the series j e− 8 r( 2 ) , and
its dependence on n, d. In the examples below, we show how the terms on
the right-hand of (2.9) can be handled.
We note that Part (2) of the theorem controls only the probability of
the event θ ∈ θ⋆ + Θ̄ : kθ − θ⋆ k2 >
 M0 ǭ whereas in most applications we
typically want the probability of θ ∈ Rd : kθ − θ⋆ k2 > M0 ǭ . As we will

10

YVES F. ATCHADÉ

show in the examples below, one can use Part(1) of the theorem to upper
bound separately the probability of the event θ ∈
/ θ⋆ + Θ̄ .
Finally, we point out that the upper bounds in (2.8) and (2.9) depends
in general on θ⋆ , typically through L̄ and the rate function r. These terms
essentially model the curvature of θ 7→ log qn,θ (Z) around θ⋆ . Our setting
thus differs from the linear regression setting where the curvature of θ 7→
log qn,θ (Z) is constant, and the resulting posterior concentration bounds are
uniform in θ⋆ ([13] Theorem 1 and 2).
3. Sparse Bayesian logistic regression. As a first application we
study the contraction behavior of a posterior distribution obtained from a
high-dimensional logistic regression model, for large values of the sample
size n and the dimension d. Suppose that Z1 , . . . , Zn are independent 0-1
binary random variables and we consider the model
P(Zi = 1) =

ehxi ,θi
,
1 + ehxi ,θi

for a parameter θ ∈ Rd , where xi ∈ Rd is a known vector of covariates.
Writing z = (z1 , . . . , zn ), the likelihood function is then
!
n
X
zi hxi , θi − g (hxi , θi) ,
qn,θ (z) = exp
i=1

where

def

g(x) = log(1 + ex ), x ∈ R.
Using the prior distribution given in (1.2)-(1.3), we consider the posterior
distribution
(3.1)
!
n
X  ρ kδk1
X
Zi hxi , θi − g (hxi , θi)
Π̌n,d (dθ|Z) ∝ exp
πδ
e−ρkθk1 µd,δ (dθ).
2
i=1

δ∈∆

We make the following assumption that implies H1.
B1. Z1 , . . . , Zn are independent 0-1 binary random variables, and there
exist θ⋆ ∈ Rd , x1 , . . . , xn ∈ Rd , such that
P(Zi = 1) =

ehxi ,θ⋆ i
, i = 1, . . . , n.
1 + ehxi ,θ⋆ i

11

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

Let X ∈ Rn×d denote the design matrix, where the i-th row of X is given
by the transpose of xi . We shall write g ′ , and g (2) to denote the first and
second derivatives of g. Let W ∈ Rn×n be the diagonal matrix with i-th
diagonal entry given by
Wi = g (2) (hxi , θ⋆ i) , i = 1, . . . , n.
We define
def

κ1 = inf




θ ′ (X ′ W X)θ
d
c
: θ ∈ R \ {0}, kθ · δ⋆ k1 ≤ 7kθ · δ⋆ k1 .
nkθk22

For s ∈ {1, . . . , d}, we define
def

κ̄1 (s) = sup




θ ′ (X ′ X)θ
: 1 ≤ kθk0 ≤ s ,
nkθk22

 ′ ′
θ (X W X)θ
def
: 1 ≤ kθk0 ≤ s .
and κ1 (s) = inf
nkθk22

We choose the regularization parameter ρ in the prior distribution (1.3)
as
def

(3.2)

ρ = 4kXk∞
def

p

n log(d),

where kXk∞ = maxi,j |Xij |. We note that κ̄1 (1) ≤ kXk2∞ , and κ1 (s) ≤
κ̄1 (1)/4, for all s ≥ 1.
def

Assume B1 and H3. Choose ρ as in (3.2). Set s⋆ = kθ⋆ k0 ,


2
2
log(4e)
64kXk2∞
κ̄(s⋆ )
def
(3.3) ζ = s⋆ +
+
+
1+
s⋆ ,
+
c4 c4
κ1
64kXk2∞ (log(d))2
log(d)
Theorem 4.

def

def

and s̄ = ⌈s⋆ + ζ⌉. If κ = min(κ1 , κ1 (s̄)) > 0, then there exists a universal
constant A < ∞ such that for all d large enough, and
(3.4)

n ≥ AkXk4∞



s⋆
κ

2

log(d),

the following statements hold.
1.

h
n
o i 4
E(n) Π̌n,d θ ∈ Rd : kθk0 ≥ ζ |Z ≤ .
d

12

YVES F. ATCHADÉ

2. There exists a finite constant M0 > 2 (that depends only on the constants in H3), such that
(
"
) !#
r
M0 kXk∞ s̄ log(d)
12
d
(n)
Π̌n,d
θ ∈ R : kθ − θ⋆ k2 >
E
|Z
≤ .
κ1 (s̄)
n
d
Proof. See Section 5.2.
If the dimension d is large, then
2
2
ζ ≈ s⋆ +
+
c4 c4



64kXk2∞
1+
κ1



s⋆ .

Therefore, for design matrices X for which the restricted eigenvalues κ1 and
κ1 (s̄) of the matrix n−1 X ′ W X are not too small, Theorem 4 implies that
most of the probability mass of the posterior distribution is on sparse subsets
of Rd , and
 the rate of convergence of the posterior distribution (3.1) is
q
s⋆ log(d)
. The frequentist ℓ1 -penalized M-estimator for logistic regresO
n

sion has been analyzed by [31] (assuming a random design matrix X), and
[25] (assuming a deterministic design matrix X), and is known to converge
at the same rate, and under assumptions that are similar to those imposed
above. Technically, our approach is closer to [25]. The approach of [31] leads
to slightly better conditions on the sample size n (they require n to increase
linearly in s⋆ , not quadratically, as in (3.4)), at the expense of more structure
on the design matrix (X is assumed to have i.i.d. rows from a sub-Gaussian
distribution and positive definite covariance).
Remark 5. As pointed out by a referee, one can use the convergence
rate in Theorem 4-Part(2) with an argument used in [14] Theorem 2.2 to
derive a bound on the convergence rate in the ℓq -norm for q ∈ (0, 2]:
"
(
) !#
1 r
q
log(d)
M
kXk
(s̄)
16
0
∞
E(n) Π̌n,d
θ ∈ Rd : kθ − θ⋆ kq >
|Z
≤ .
κ1 (s̄)
n
d

This follows from the fact that for any r > 0,
n

o
θ ∈ Rd : kθ − θ⋆ kq > r ⊆
n
o[n
o
θ ∈ Rd : kθ − θ⋆ kq > r, kθk0 ≤ ζ
θ ∈ Rd : kθk0 > ζ ,

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

13

and by Holder’s inequality, for θ ∈ Rd such that kθk0 ≤ ζ, kθ − θ⋆ k0 ≤ s̄,
and
1
−1
kθ − θ⋆ kq ≤ kθ − θ⋆ k2 (s̄) q 2 .
Obviously, the same argument can be used with respect to the general bound
in Theorem 3, but the resulting bound would be more complicated.
Remark 6. It is interesting to observe that the contraction result given
in Theorem 4 Part(2) holds, not in spite of the large dimension d, but because d is large. In other words, the result should be viewed as a form of
concentration of measure phenomenon for Π̌n,d as d → ∞. In particular,
Theorem 4 should not be applied to a fixed-dimension case in an attempt
to recover standard Bayesian contraction results (fixed d, n → ∞). Indeed,
note that for d fixed, the prior distribution Π in (1.2-1.3) with ρ as in (3.2)
converges weakly to a point-mass at 0 as n → ∞, which is not a good behavior of a prior in fixed-dimensional settings. However with more appropriate
prior assumptions, the argument in the proof of Theorem 3 can be easily
modified to derive convergence rate results that would be applicable to the
fixed-dimensional setting. We refer to [20] (and the references therein) for a
good presentation of finite-dimensional Bayesian asymptotics.
4. Quasi-Bayesian inference of large binary graphical models.
As another example, we consider the Bayesian analysis of high-dimensional
binary graphical models (sometimes called Ising models). Let Mp be the
space of real-valued p × p symmetric matrices. For θ ∈ Mp , let fθ be the
probability mass function defined on {0, 1}p by
(4.1)


p
X
X
1
exp 
θjj xj +
θij xi xj  , xj ∈ {0, 1}, 1 ≤ j ≤ p,
fθ (x1 , . . . , xp ) =
Zθ
j=1

i<j

where Zθ is the normalizing constant. We consider the problem of estimating
θ under a sparsity assumption, from a matrix Z ∈ Rn×p where each row of
Z is an independent realization from fθ⋆ for some sparse θ⋆ ∈ Mp . This
problem has generated some literature in recent years ([8, 21, 32, 4, 10] and
the references therein), all in the frequentist framework.
The Bayesian estimation of θ is significantly more challenging because the
normalizing constant Zθ are typically intractable, and this leads to posterior distributions that are doubly intractable. In the frequentist literature
cited above, the preferred approach for estimating θ is via penalized pseudolikelihood maximization, which nicely side-steps the intractable normalizing
constants issue. The quasi-Bayesian framework developed in this work can

14

YVES F. ATCHADÉ

be used to combine these pseudo-likelihood functions with a prior distribution to produce quasi-Bayesian posterior distributions.
The most commonly used pseudo-likelihood function is obtained by taking
the product of all the conditional densities in (4.1). This is an idea that
goes back at least to [12]. Combined with a prior distribution Π on Mp , this
approach readily yields a quasi-posterior distribution on Mp that falls in the
framework presented above. Note however that when p is large, say p ≥ 500,
the space Mp has dimension bigger than 105 , and MCMC sampling from
this quasi-posterior distribution becomes a daunting and time consuming
task. One interesting idea is to break the symmetry and to consider the
quasi-likelihood



P
p Y
n exp Zij θjj +
θ
Z
Y
k6=j kj ik

 , θ ∈ Rp×p.
(4.2)
qn,θ (Z) =
P
j=1 i=1 1 + exp θjj +
k6=j θkj Zik

Notice that the only difference between q̄n,θ and qn,θ is that the symmetry
constraint in θ is relaxed, that is the parameter space of the map θ 7→
qn,θ (Z) is Rp×p , not Mp . However this difference has a huge impact since
now qn,θ (Z) factorizes along the columns of θ. As a result, maximizing a
penalized version of (4.2) is equivalent to solving p independent logistic
regression (assuming a separable penalty), and this can be done efficiently
in a parallel computing environment. This pseudo-likelihood approach was
popularized by the influential paper [29] in the Gaussian case, and extended
to the Ising model by [32]. In a recent work ([6]), the author extended
this idea to the Bayesian analysis of large Gaussian graphical models, and
analyzed the contraction of the resulting quasi-posterior distribution using
Theorem 3. Here we extend the method to the Ising model.
Throughout this section, if θ ∈ Rp×p , θ·j ∈ Rp denotes the j-th column of
θ. In view of the discussion above, and for a discrete probability distribution
{πδ , δ ∈ ∆p } on ∆p , and ρ > 0, we consider the quasi-posterior Π̌n,d on
Rp×p given by
(4.3)

Π̌n,d (dθ|Z) ∝ qn,θ (Z)
=

p
Y

j=1

p X
Y

j=1 δ∈∆p

πδ

 ρ kδk0

Π̌n,d,j (dθ·j |Z) .

2

e−ρkθ·j k1 µp,δ (dθ·j )

15

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

where Π̌n,d,j (·|Z) is the probability measure on Rp given by



P
exp Zij uj + k6=j uk Zik


Π̌n,d,j (du|Z) ∝
P
u
Z
k
ik
i=1 1 + exp uj +
k6=j
 ρ kδk0
X
×
πδ
e−ρkuk1 µp,δ (du).
2
n
Y

δ∈∆p

Remark 7. One of the limitation of the approach is that the distribution
Π̌n,d does not necessarily produce symmetric matrices. However, because of
the contraction properties discussed below, typical realizations of Π̌n,d will
be close to be symmetric. Furthermore, from a practical viewpoint, one can
easily remedy a broken symmetry using various symmetrization rules as
suggested for instance in [29].
We make the following assumptions.
C1. The rows of Z ∈ Rn×p are independent {0, 1}p -valued random variables with common probability mass function fθ⋆ , for some θ⋆ ∈ Mp .
We define

def

s⋆j = kθ⋆·j k0 ,

def

and s⋆ = max s⋆j .
1≤j≤p

Hence s⋆ is the maximum degree of the undirected graph encoded by θ⋆ .
The sparsity structure of θ⋆ is the matrix δ⋆ ∈ {0, 1}p×p defined as δ⋆,jk =
1{|θ⋆jk |>0} . For X ∼ fθ⋆ , and 1 ≤ j ≤ p, we define
def

X(j) = (X1 , . . . , Xj−1 , 1, Xj+1 , . . . , Xp ) ∈ Rp ,
(viewed as a column vector), and
h
i

def
′
H(j) = E g(2) θ⋆·j , X(j) X(j) X(j)
.

We set

def

(4.4) κ2 (s) = inf inf
1≤j≤p

def

κ2 = inf inf
1≤j≤p

(


 u′ H(j) u
 kuk22

)
u′ H(j) u
, u ∈ Rp \ {0}, kuk0 ≤ s ,
kuk22

, u ∈ Rp \ {0},

X

k: δ⋆kj 6=0

|uk | ≤ 7

X

and

k: δ⋆kj =0



|uk | .


16

YVES F. ATCHADÉ

Remark 8. It is easy to verify that

 


P
n
n
u
+
u
Z
exp
Z
X
Y
j
ij
k6=j k ik
=−


g(2)
∇(2) log 
P
i=1
i=1 1 + exp uj +
k6=j uk Zik

u, Zi(j)



′
Zi(j) Zi(j)
,

where Zi(j) = (Zi1 , . . . , Zi,j−1 , 1, Zi,j+1 , . . . , Zip ). Hence −nH(j) is the Fisher
information matrix in the conditional model that regress the j-th column
of Z on the remaining. The quantities κ2 (s) and κ2 are (the minimum over
j of) restricted smallest eigenvalues of these information matrices. We will
work under the assumption that κ2 (s) > 0 and κ2 > 0, for some well-chosen
s. Similar assumptions are made in most work on high-dimensional discrete
graphical models ([32, 4, 10]). Although these assumptions are very natural
in this context, to the best of our knowledge there does not seem to exist
any easy way of checking them for a given parameter value θ⋆ .
We will take the prior parameter ρ as
p
(4.5)
ρ = 24 n log(p).

In order to apply Theorem 3 we view Rp×p as Rd , with d = p2 , equipped
def p
def
with the Frobenius norm kθkF =
Tr(θ ′ θ), and inner product hθ, ϑiF =
Tr(θ ′ ϑ), where Tr(θ) denotes the trace of the matrix θ. Throughout this
section, the norm k · k2 always denotes the Euclidean norm on Rp . We will
work with split cones of the form {θ ∈ Rp×p : kθ·j k0 ≤ sj , 1 ≤ j ≤ p}.
Theorem 9. Consider the quasi-posterior distribution (4.3). Suppose
that C1 holds, the prior {πδ , δ ∈ ∆p } satisfies H3 (with d replaced by p),
and ρ is given by (4.5). For 1 ≤ j ≤ p set


s⋆j
4
2
log(4e)
128
def
+
(4.6)
ζj = s⋆j +
+
+
1+
s⋆j ,
c4 c4
κ2
64(log(p))2
log(p)
def

def

def

s̄j = ⌈s⋆j + ζj ⌉, and s̄ = max1≤j≤p s̄j . If κ = min(κ2 , κ2 (s̄)) > 0, then
there exist universal finite positive constants A1 , A2 such that for all p large
enough and
2

p
X
1
s̄j  log(p),
(4.7)
n ≥ A1 
κ
j=1

the following statements hold.

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

17

1.



4
E(n) Π̌n,d θ ∈ Rp×p : kθ·j k0 > ζj , for some j |Z ≤ e−A2 n + .
p

2. There exists a finite constant M0 > 2 (that depends on the constants
in H3), such that
v
 


u


p
u X


log(p)
M0 u


(n) 
d×d
t
s̄j 
E Π̌n,d  θ ∈ R
: kθ − θ⋆ kF >
|Z 


κ
n
(s̄)
2


j=1


≤ 2e−A2 n +

12
.
p

Proof. See Section 5.3.
If p and n are large while κ remains bounded away from zero, Theorem
9-Part(1) implies that the quasi-posterior distribution Π̌n,d puts high probability on matrices of Rd×d with the same sparsity pattern as θ⋆ , and Theorem
9-Part(2) implies that in this case, the rate of convergence in the Frobenius
norm is of order
!
r
(p + S) log(p)
,
O
n
def P
where S = pj=1 s⋆j is twice the number of non-zero components of θ⋆ . As
we show next, faster convergence rate is possible if one is only interested in
components of θ. We consider the norm
def

|||θ||| = max kθ·j k2 , θ ∈ Rp×p .
1≤j≤p

Theorem 10. Under the assumptions of Theorem 9, if κ > 0, then there
exist finite universal constants A1 , A2 , and a finite constant M0 > 2 (that
depends only on the constants in H3) such that for all p large enough, and
for
2

s̄
log(p),
n ≥ A1
κ(s̄)
"
(
) !#
r
s̄ log(p)
M0
12
(n)
d×d
E
Π̌n,d
θ∈R
: |||θ − θ⋆ ||| >
|Z
≤ 2e−A2 n + .
κ2 (s̄)
n
p
Proof. See Section 5.3.

18

YVES F. ATCHADÉ

5. Proofs.
5.1. Proof of Theorem 3. To improve readability we split the proof in
three parts. The first part deals with the normalizing constant of the quasiposterior distribution, the second part deals with the existence of test functions, and the proof of the theorem itself is given in the third part.
5.1.1. On the normalizing constant of the quasi-posterior distribution.
The next lemma provides a lower bound on the normalizing constant of the
quasi-posterior distribution (2.1), following an approach initially developed
by [13].
Lemma 11. Assume H1-H2. Fix L ≥ 0, and a split cone Θ ⊇ Θ⋆ . For
all z ∈ Ên,1 (Θ, L),
(5.1)

Z

Rd

qn,θ (z)
Π(dθ) ≥ πδ⋆
qn,θ⋆ (z)



ρ2
L + ρ2

s ⋆

e−ρkθ⋆ k1 .

Proof. Using the definition of the prior Π, we have
Z
 ρ  s⋆ Z
qn,θ (z) −ρkθk1
qn,θ (z)
Π(dθ) ≥ πδ⋆
e
µd,δ⋆ (dθ).
(5.2)
2
θ⋆ +Θ⋆ qn,θ⋆ (z)
Rd qn,θ⋆ (z)
For z ∈ Ên,1 (Θ, L), and θ ∈ θ⋆ + Θ⋆ ⊆ θ⋆ + Θ,
log qn,θ (z) − log qn,θ⋆ (z) ≥ h∇ log qn,θ⋆ (z), θ − θ⋆ i −

L
kθ − θ⋆ k22 .
2

Setting ϑ = ∇ log qn,θ⋆ (z), (5.2) then gives
Z
 ρ s⋆
qn,θ (z)
(5.3)
e−ρkθ⋆ k1
Π(dθ) ≥ πδ⋆
(z)
q
2
d
n,θ⋆
R
Z
L
2
ehϑ,θ−θ⋆ i− 2 kθ−θ⋆ k2 e−ρkθ−θ⋆ k1 µd,δ⋆ (dθ).
×
θ⋆ +Θ⋆

We note that the support of the measure µd,θ⋆ is Θ⋆ = θ⋆ + Θ⋆ . Using
this and the change of variable θ = θ⋆ + z, we see that the integral on the
right-hand size of (5.3) is
Z
L
2
ehϑ,zi− 2 kzk2 −ρkzk1 µd,δ⋆ (dz).
Rd

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

19

By Jensen’s inequality,
Z

L

hϑ,zi

e
Rd

2

e− 2 kzk2 −ρkzk1

R

µd,δ⋆ (dz)
L
2
e− 2 kuk2 −ρkuk1 µd,δ⋆ (du)
!
L
Z
2
e− 2 kzk2 −ρkzk1
hϑ, zi R
≥ exp
µd,δ⋆ (dz) = 1.
kuk22 −ρkuk1
−L
2
R
(du)
µ
e
d
d,δ
⋆
R

Rd

Using this, and going back to (5.2) we conclude that
Z
Z
 ρ s⋆
L
qn,θ (z)
2
e− 2 kuk2 −ρkuk1 µd,δ⋆ (du).
e−ρkθ⋆ k1
Π(dθ) ≥ πδ⋆
2
Rd qn,θ⋆ (z)
Rd
Now, note that
Z

Rd

L

2

e− 2 kuk2 −ρkuk1 µd,δ⋆ (du) =

Z

L 2

e−ρ|z|− 2 z dz

R

s ⋆

.

It is easy to calculate that for a ≥ 0, b > 0
(5.4)

Z

− a2 u2 −b|u|

e
R

 
√b
1
−
Φ
2
a
  ,
du = √
a φ √b
a

where φ is the density of the standard normal distribution, and Φ its cdf. The
formula continues to hold by continuity at a = 0. The ratio (1 − Φ(z))/φ(z)
(known as Mills’ ratio), satisfies
(5.5)

z
2
4
1 − Φ(z)
√
√
≤
≤
≤
, z ≥ 0,
2
1+z
φ(z)
z + z2 + 4
3z + z 2 + 8

see for instance [11] Theorem 2.3 for a proof. We use this inequality and
(5.4) to conclude that
Z
L 2
2ρ
,
e−ρ|z|− 2 z dz ≥
L
+
ρ2
R
and the lemma follows easily.
5.1.2. On the existence of test functions. In this paragraph we establish
the existence of test functions to test the density fn,θ⋆ against some misspecified alternatives Qn,θ defined below. The result is based on Lemma 6.1

20

YVES F. ATCHADÉ

of [23], that we shall recall first for completeness. For any two integrable nonnegative functions q1 , q2 on Z (n) , and for α ∈ (0, 1), the Hellinger transform
Hα (q1 , q2 ) is defined as
Z
def
q1α (z)q21−α (z)dz.
Hα (q1 , q2 ) =
Z (n)

def

Here we work with the case α = 1/2, and set H(q1 , q2 ) = H1/2 (q1 , q2 ).
Lemma 12 ([23] Lemma 6.1). Let p be a probability density function on
and Q a class of non-negative integrable functions on Z (n) . Then
(5.6)

Z
Z
Z (n)

inf sup

φ q∈Q

φ(z)p(z)dz +

Z (n)

Z (n)

(1 − φ(z))q(z)dz ≤

sup

q∈conv(Q)

H(p, q),

where conv(Q) is the convex hull of Q, and the infimum in (5.6) is taken
over all test functions, that is all measurable functions φ : Z (n) → [0, 1].
Furthermore, there exists a test function φ that attains the infimum.
To derive the test function for our quasi-likelihood setting, we will also
need the following easy result.
Lemma 13. Fix λ ≥ 0, a split cone Θ, and a rate function r such that
φr (2λ) is finite. For any θ ∈ θ⋆ + Θ such that kθ − θ⋆ k2 ≥ φr (2λ), we have
1
qn,θ (z)
≤ e− 4 r(kθ−θ⋆ k2 ) , z ∈ En,0 (Θ, λ) ∩ Eˇn,1 (Θ, r).
qn,θ⋆ (z)

Proof. For all z ∈ Z (n) , and θ ∈ Rd , we have

qn,θ (z)
= exp [h∇ log qn,θ⋆ (z), θ − θ⋆ i + Ln,θ (z)] .
qn,θ⋆ (z)

By the definition of Ěn,1 (Θ, r), for θ ∈ θ⋆ + Θ and z ∈ Ěn,1 (Θ, r), we
have Ln,θ (z) ≤ − 12 r(kθ − θ⋆ k2 ). And by the definition of En,0 (Θ, λ), for
z ∈ En,0 (Θ, λ), and θ ∈ θ⋆ + Θ, we have
|h∇ log qn,θ⋆ (z), θ − θ⋆ i| ≤

λ
kθ − θ⋆ k2 .
2

Hence, for z ∈ En,0 (Θ, λ) ∩ Ěn,1 (Θ, r), and θ ∈ θ⋆ + Θ,


qn,θ (z)
λ
1
≤ exp
kθ − θ⋆ k2 − r(kθ − θ⋆ k2 ) .
(5.7)
qn,θ⋆ (z)
2
2
If in addition kθ − θ⋆ k2 ≥ φr (2λ), then from the properties of the rate function r, we have 2λ kθ − θ⋆ k2 − r(kθ − θ⋆ k2 ) ≤ 0, and the result follows.

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

21

Our main result on the existence of test functions follows. We recall that
def
for M > 0, and a split cone Θ, Bd (Θ, M ) = {θ ∈ θ⋆ + Θ : s.t. kθ − θ⋆ k2 ≤
M }, and for ǫ > 0, D(ǫ, Bd (Θ, M )) denotes the ǫ-packing number of Bd (Θ, M )
in the norm k·k2 .
Lemma 14. Fix λ ≥ 0, a split cone Θ, and a rate function r such that
def
ǫ̃ = φr (2λ) is finite. Set E¯n = En,0 (Θ, λ) ∩ Ěn,1 (Θ, r). For θ ∈ Rd , define the
function
def

def

(5.8)

Qn,θ (z) = 1Ēn (z)

qn,θ (z)
fn,θ⋆ (z),
qn,θ⋆ (z)

z ∈ Z (n) .

For any M > 2, there exists a measurable function φ : Z (n) → [0, 1] such
that,
X
1 jM ǫ̃
Dj e− 8 r( 2 ) ,
E(n) (φ(Z)) ≤
j≥1


+ 1)M ǫ̃) . Furthermore, for all j ≥ 1, all
where Dj = D
θ ∈ θ⋆ + Θ such that kθ − θ⋆ k2 > jM ǫ̃,
Z
1 jM ǫ̃
(1 − φ(z))Qn,θ (z)dz ≤ e− 8 r( 2 ) .


def

jM ǫ̃
2 , Bd (Θ, (j

Z (n)

Proof. First, notice that the function z 7→ Qn,θ (z) is integrable for all
qn,θ (z)
θ ∈ θ⋆ + Θ. Indeed, using (5.7) for any such θ, and for z ∈ Ēn : qn,θ
≤
⋆ (z)

λ
exp 2 kθ − θ⋆ k2 . Hence,
Z

Z (n)

Qn,θ (z)dz =

Z

Ēn

λ
qn,θ (z)
fn,θ⋆ (z)dz ≤ e 2 kθ−θ⋆ k2 .
qn,θ⋆ (z)

Now, fix ǫ > 2ǫ̃ (where ǫ̃ = φr (2λ)), and fix θ ∈ θ⋆ + Θ such that
def

kθ − θ⋆ k2 > ǫ. Set Pθ = {Qn,u : u ∈ θ⋆ + Θ and ku − θk2 ≤ ǫ/2}, and let
conv(Pθ ) denote the convex hull of the set Pθ . By Lemma 12 applied with
p = fn,θ⋆ , and Q = Pθ , there exists a measurable function φθ : Z (n) → [0, 1]
such that
(5.9) E(n) [φθ (Z)] ≤
and

sup
Q∈conv(Pθ )

sup
Q∈Pθ

Z

Z (n)

H(fn,θ⋆ , Q)

(1 − φθ (z))Q(z)dz ≤

sup
Q∈conv(Pθ )

H(fn,θ⋆ , Q).

22

YVES F. ATCHADÉ

Any
written as a finite convex combination Q =
P Q ∈ conv(Pθ ) can beP
α
Q
where
α
≥
0,
j
j j n,uj
j αj = 1, u ∈ θ⋆ + Θ, and kuj − θk2 ≤ ǫ/2.
However, since kθ − θ⋆ k2 > ǫ, and kuj − θk2 ≤ ǫ/2, we see that kuj − θ⋆ k2 >
ǫ/2 > ǫ̃. Hence, using Lemma 13 and the definition of the Hellinger transform, we have
v
Z
sX
uX
qn,uj (z)
u
1
t
H(fn,θ⋆ , Q) =
fn,θ⋆ (z)dz ≤
αj 1Ēn (z)
αj e− 4 r(kuj −θ⋆ k2 ) .
qn,θ⋆ (z)
Z (n)
j

j

Hence (5.9) becomes
(5.10)
E

(n)

− 81 r( 2ǫ )

[φθ (Z)] ≤ e

and

sup
Q∈Pθ

Z

Z (n)

1

ǫ

(1 − φθ (z))Q(z)dz ≤ e− 8 r( 2 ) .

Now, given M > 2, we write {θ ∈ θ⋆ + Θ : kθ − θ⋆ k2 > M ǫ̃} = ∪j≥1 B(j),
where
B(j) = {θ ∈ θ⋆ + Θ, s.t. jM ǫ̃ < kθ − θ⋆ k2 ≤ (j + 1)M ǫ̃}.
For each j ≥ 1, let Sj be a maximal (jM ǫ̃/2)-separated points in B(j). For
each j for which B(j) 6= ∅, and each point θk ∈ Sj we can construct a test
function φθk as above, with ǫ = jM ǫ̃. Then we set
φ = sup max φθk ,
j≥1 θk ∈Sj

where the supremum in j is over the indexes for which B(j) 6= ∅. Now, any
θ ∈ θ⋆ + Θ such that kθ − θ⋆ k2 > jM ǫ̃ will be within iM ǫ̃/2 of a point θk in
Si for some i ≥ j. Hence by (5.10), for any such θ,
Z
Z
1 jM ǫ̃
(1 − φθk (z))Qn,θ (z)dz ≤ e− 8 r( 2 ) .
(1 − φ(z))Qn,θ (z)dz ≤
Z (n)

Z (n)

Notice that the size of Sj is upper bounded by Dj . Using this and (5.10), we
get
X
1 jM ǫ̃
E(n) [φ(Z)] ≤
Dj e− 8 r( 2 ) ,
j≥1

which proves the lemma.

23

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS
def

5.1.3. Proof of Theorem 3-Part(1). For integer k ≥ 0, let Ak = {θ ∈
d
R : kθk0 ≥ s⋆ + k}. We have

E(n) Π̌n,d (Ak |Z) ≤ P(n) (Z ∈
/ En ) + T,
"
#
R
qn,θ (Z)
Π(dθ)

Ak qn,θ (Z)
⋆
qn,θ (Z)
Π(dθ)
Rd qn,θ (Z)
⋆

where T = E(n) 1En (Z) R

. We use Lemma 11, and Fubini’s

theorem to write


s

Z
qn,θ (Z)
1
L̄ ⋆ ρkθ⋆ k1 (n)
e
T ≤
E
Π(dθ)
1+ 2
1En (Z)
πδ⋆
ρ
Ak qn,θ⋆ (Z)

s
L̄ ⋆
1
1+ 2
=
πδ⋆
ρ
"
#
Z

X
qn,θ (Z) e−ρkθk1
ρ kδk0
(n)
×
πδ
1En (Z)
(5.11)
µd,δ (dθ).
E
2
qn,θ⋆ (Z) e−ρkθ⋆ k1
Ak
δ∈∆d

We need to control the expectation on the right-side of (5.11). First note
that En,0 (Rd , ρ) = {z ∈ Z (n) : k∇ log qn,θ⋆ (z)k∞ ≤ ρ2 }. With this in mind,
we see that z ∈ En ⊆ En,0 (Rd , ρ), and θ ∈ Rd , we have
qn,θ (z)
qn,θ⋆ (z)

def ρ
2 kθ

= exp [h∇ log qn,θ⋆ (z), θ − θ⋆ i + Ln,θ (z)] ,
i
hρ
≤ exp kθ − θ⋆ k1 + Ln,θ (z) .
2

− θ⋆ k1 + ρ(kθ⋆ k1 − kθk1 ), it follows that for all θ ∈ Rd ,
#
qn,θ (Z) e−ρkθk1
1En (Z)
≤ eB(θ) E(n) [1En (Z) exp (Ln,θ (Z))] .
qn,θ⋆ (Z) e−ρkθ⋆ k1

Setting B(θ) =
"

(5.12) E(n)

We then write
1
1
1
kθ⋆ k1 + kθ − θ⋆ k1 = kθ⋆ k1 + kθ · δ⋆c k1 + k(θ − θ⋆ ) · δ⋆ k1
2
2
2
1
3
≤ kθk1 − kθ · δ⋆c k1 + k(θ − θ⋆ ) · δ⋆ k1 .
(5.13)
2
2
Using this bound in the expression of B(θ) shows that if θ ∈
/ θ⋆ + N , then
we have
(5.14)

3ρ
ρ
B(θ) ≤ − kθ · δ⋆c k1 + k(θ − θ⋆ ) · δ⋆ k1
2
2
ρ
≤ − kθ − θ⋆ k1 .
4

24

YVES F. ATCHADÉ

This bound together with the fact that the expectation on the right-side of
(5.12) is always smaller or equal to 1 (which follows from the concaveness
assumption) show that when θ ∈
/ θ⋆ + N ,
"
#
−ρkθk1
ρ
q
(Z)
e
n,θ
≤ e− 4 kθ−θ⋆ k1 .
E(n) 1En (Z)
−ρkθ
k
⋆
1
qn,θ⋆ (Z) e
Now, consider the case where N =
6 ∅, and θ − θ⋆ ∈ N . In that case, the
ˇ
definition of the set En,1 (N , r) and (5.12) yield
"
#
qn,θ (Z) e−ρkθk1
(n)
B(θ)− 12 r(kθ−θ⋆ k2 )
.
1En (Z)
E
≤
e
qn,θ⋆ (Z) e−ρkθ⋆ k1
From (5.14),
ρ
1
1
B(θ) − r(kθ − θ⋆ k2 ) ≤ − kθ − θ⋆ k1 + 2ρk(θ − θ⋆ ) · δ⋆ k1 − r(kθ − θ⋆ k2 ),
2
2
2
and
√
1
1
2ρk(θ − θ⋆ ) · δ⋆ k1 − r(kθ − θ⋆ k2 ) ≤ 2ρ s⋆ kθ − θ⋆ k2 − r(kθ − θ⋆ k2 ),
2
2
√
1
≤ − [r(kθ − θ⋆ k2 ) − 4ρ s⋆ kθ − θ⋆ k2 ]
2
i
h
1
1/2
≤ − inf r(x) − 4ρs⋆ x .
2 x>0

Therefore, when θ =
6 θ⋆ , and θ ∈ θ⋆ + N , we have
"
#
ρ
qn,θ (Z) e−ρkθk1
(n)
1En (Z)
E
≤ ea e− 2 kθ−θ⋆ k1 ,
−ρkθ
k
⋆
1
(Z)
qn,θ⋆
e

i
h
1/2
where a = − 12 inf x>0 r(x) − 4ρs⋆ x . Note that a > 0, since limx↓0 r(x)/x =
0. In view of these calculations and (5.11), we conclude that
s

 ρ kδk0 Z
ρ
L̄ ⋆ 1 X
a
e− 4 kθ−θ⋆ k1 µd,δ (dθ).
πδ
T ≤e 1+ 2
ρ
πδ⋆
2
Ak
δ∈∆d

Note that µd,δ (Ak ) = 0 if kδk0 < s⋆ + k, and
 ρ kδk0 Z
2

− ρ4 kθ−θ⋆ k1

e
Rd

µd,δ (dθ) ≤

 ρ kδk0 Z
2

R

− ρ4 |z|

e

dz

kδk0

= 4kδk0 .

25

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

Therefore,
a

T ≤e



L̄
1+ 2
ρ

s ⋆

1
πδ⋆

X

πδ 4kδk0 .

δ: kδk0 ≥s⋆ +k

Using H3,
1
πδ⋆

X

δ: kδk0 ≥s⋆ +k

kδk0

πδ 4

=

d
s⋆

gs⋆

d
X

j=s⋆ +k

j

4 gj ≤

d
s⋆

gs⋆

d
X

4j

j=s⋆ +k

 c j−s⋆
2
gs⋆
dc4


 

d
4c2 j−s⋆
d s⋆ X
=
4
.
s⋆
dc4
j=s⋆ +k

For d large enough so that d4cc42 < 1, we have
which proves the stated bound.

Pd

j=s⋆ +k


4c2 j−s⋆
dc4

≤2


4c2 k
,
dc4


def

5.1.4. Proof of Theorem 3-Part(2). Define U (ǭ) = {θ ∈ θ⋆ +Θ̄ : kθ − θ⋆ k2 >
M0 ǭ}. We apply Lemma 14 with λ = λ̄, Θ = Θ̄, the rate function r and with
M = M0 > 2. Notice ǭ = φr (2λ̄) is called ǫ̃ in Lemma 14. By Lemma 14
there exists a measurable functions φ : Z (n) → [0, 1] such that
X
1 jM0 ǭ
(5.15)
E(n) [φ(Z)] ≤
Dj e− 8 r( 2 ) ,
j≥1



def
where Dj = D jM20 ǭ , Bd (Θ̄, (j + 1)M0 ǭ) . Using the test function φ, we
have
Π̌n,d (U (ǭ)|Z) ≤ φ(Z) + (1 − φ(Z))Π̌n,d (U (ǭ)|Z) .
In view of (5.15), it remains only to control the expectation of (1−φ(Z))Π̌n,d (U (ǭ)|Z).
def
To do so, we set Ēn = En,0 (Θ̄, λ̄) ∩ Eˇn,1 (Θ̄, r), so that En ⊆ E¯n ∩ Eˆn,1 (Θ̄, L̄),
and use Lemma 11 and Fubini’s theorem to write
(5.16)




E(n) (1 − φ(Z))Π̌n,d (U (ǭ)|Z) = E(n) (1 − φ(Z))

R

qn,θ (Z)
U (ǭ) qn,θ⋆ (Z) Π(dθ)

R qn,θ (Z)
qn,θ⋆ (Z) Π(dθ)



s

1
ρ2 ⋆ ρkθ⋆ k1
e
≤ P(n) (Z ∈
/ En ) +
1+
πδ⋆
L̄


Z
qn,θ (Z)
(n)
E
×
1Ēn (Z)(1 − φ(Z))
Π(dθ).
qn,θ⋆ (Z)
U (ǭ)

26

YVES F. ATCHADÉ

We split U (ǭ) as U (ǭ) = ∪j≥1 B(j), where
B(j) = {θ ∈ θ⋆ + Θ̄ s.t. jM0 ǭ < kθ − θ⋆ k2 ≤ (1 + j)M0 ǭ}.
Therefore, and using the notation of Lemma 14, the integral in (5.16) is


Z
qn,θ (Z)
(n)
Π(dθ)
E
1Ēn (Z)(1 − φ(Z))
qn,θ⋆ (Z)
U1 (ǭ)

Z
X 1 jM0 ǭ
XZ
(1 − φ(z))Qn,θ (z)dz Π(dθ) ≤
e− 8 r( 2 ) Π(B(j)).
=
j≥1

B(j)

Z (n)

j≥1

From the prior Π, we have
 ρ kδk0 Z
X
ρkθ⋆ k1
eρ(kθ⋆ k1 −kθk1 ) µd,δ (dθ).
πδ
e
Π(B(j)) =
2
B(j)
δ∈∆d

and for θ ∈ B(j),
ρ
3
ρ(kθ⋆ k1 − kθk1 ) ≤ ρkθ − θ⋆ k1 ≤ − kθ − θ⋆ k1 + ρkθ − θ⋆ k1
2
2
3
ρ
ρ
≤ − kθ − θ⋆ k1 + ρc0 kθ − θ⋆ k2 ≤ − kθ − θ⋆ k1 + 3ρc0 jM0 ǭ
2
2
2
where c0 = supu∈Θ̄ supv∈Θ̄, kvk2 =1 | hsign(u), vi |. Hence
 ρ kδk0 Z
X
ρ
ρkθ⋆ k1
3ρc0 jM0 ǭ
πδ
e
Π(B(j)) ≤ e
e− 2 kθ−θ⋆ k1 µd,δ (dθ),
2
B(j)
δ∈∆d

kδk0
 ρ kδk0 Z
X
− ρ2 |z|
3ρc0 jM0 ǭ
e
≤ e
πδ
,
dz
2
R
δ∈∆d
X
3ρc0 jM0 ǭ
πδ 2kδk0 .
= e
δ∈∆d

Therefore, the second term on the right-hand side of (5.16) is upper bounded
by


s

X
1 
ρ2 ⋆ X − 1 r( kM0 ǭ ) 3ρc0 kM0 ǭ
kδk0 
e 8 2 e
πδ 2
.
1+
πδ⋆
L̄
k≥1

δ∈∆d

dc4

≥ 4c2 ,
As in Part(1), using H3 and for
 d


d X
d
d 
X
X
2c2 j
s⋆
s⋆
−1
kδk0
j
πδ 2
=
πδ⋆
2 gj ≤
g0
gs⋆
gs⋆
dc4
j=0
j=0
δ∈∆d
 
   c 3 s ⋆
d g0
d
d
≤2
≤2
.
s⋆ gs⋆
s⋆
c1

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

27

This ends the proof.

5.2. Proof of Theorem 4. Clearly, B1 implies H1, and H2 trivially holds
true. Furthermore in this case the function Ln,θ is given by
Ln,θ (z) = −

n
X
i=1

g(hxi , θi) − g(hxi , θ⋆ i) − g ′ (hxi , θ⋆ i) hxi , θ − θ⋆ i ,

which does not depend on z. To control this term, we will rely on a nice selfconcordant properties of the logistic function g(x) = log(1 + ex ) developed
by [7] Lemma 1, which states that for all x0 , u ∈ R,


(5.17) g(2) (x0 ) e−|u| + |u| − 1 ≤ g(x0 + u) − g(x0 ) − g′ (x0 )u


≤ g(2) (x0 ) e|u| − |u| − 1 .

Proof of Part(1). We shall apply Theorem 3-(Part 1). Clearly, θ 7→
def

log qn,θ (z) is concave for all z ∈ {0, 1}n . We define H(x) = e−x + x − 1. It
can be checked that H satisfies
H(x) ≥

(5.18)

x2
, x ≥ 0.
2+x

This holds because (2 + x)H(x) − x2 = (2 + x)e−x + x − 2, the derivative of
which is 1 − x+1
ex ≥ 0, for all x ≥ 0. Using (5.17), we get
Ln,θ (z) ≤ −

n
X
i=1

g(2) (hxi , θ⋆ i) H (| hxi , θ − θ⋆ i |) .

Furthermore, for θ − θ⋆ ∈ N , we have
1/2

|hxi , θ − θ⋆ i| ≤ kXk∞ kθ − θ⋆ k1 ≤ 8kXk∞ s⋆ kθ − θ⋆ k2 .
Using this, (5.18), and the definition of κ1 , we get for all z ∈ {0, 1}n ,
n
X ′W X
(θ − θ⋆ )′
(θ − θ⋆ )
2 + maxi | hxi , θ − θ⋆ i |
n
nκ kθ − θ⋆ k22
≤ −
,
√ 1
2 + 8 s⋆ kXk∞ kθ − θ⋆ k2
1
= − r(kθ − θ⋆ k2 ),
2

Ln,θ (z) ≤ −

(5.19)

28

YVES F. ATCHADÉ

√
where r(x) = nκ1 x2 /(1 + 4 s⋆ kXk∞ x). Hence, with this particular choice
of rate function P(n) (Z ∈
/ Eˇn,1 (N , r)) = 0. Since g(2) (x) ≤ 1/4, it follows that
X ′X
n
(θ − θ⋆ ).
Ln,θ (z) ≥ − (θ − θ⋆ )′
8
n
As a result, if θ − θ⋆ ∈ Θ⋆ , Ln,θ (z) ≥ −(n/8)κ̄1 (s⋆ )kθ − θ⋆ k22 . Hence P(n) (Z ∈
/
ˆn,1 (Θ⋆ , L̄)) = 0, for L̄ = nκ̄1 (s⋆ )/4. Finally, we have ∇ log qn,θ (Z) =
E
⋆
Pn
′
i=1 (Zi − g (hxi , θ⋆ i)) xi , and by Hoeffding’s inequality, and a standard
union bound argument,
!
n


X

ρ
Zi − g′ (hxi , θ⋆ i) Xij >
P(n) Z ∈
/ En,0 (Rd , ρ)
= P(n) max
1≤j≤d
2
i=1


2
ρ2
= ,
≤ 2 exp log(d) −
2
8kXk∞ n
d
given the choice of ρ in (3.2) of the main paper. Hence we can apply Theorem
3-Part(1). This says that for any k ≥ 0,
h

i 2
E(n) Π̌n,d {θ ∈ Rd : kθk0 ≥ s⋆ + k}|Z ≤
d


s ⋆   
κ̄1 (s⋆ )
d
4c2 k
−a
+ 2e
4+
,
16kXk2∞ log(d)
dc4
s⋆
i
h
1/2
where a = (1/2) inf x>0 r(x) − 4ρs⋆ x . It is not hard to verify that for
i
h 2
c2
c2
τx
− cx ≥ − 4√τ √
, if τ ≥ (4/3)bc. In the
≥ − 2τ
τ, b, c > 0, inf x>0 1+bx
τ −cb
p
√
case of a, the condition τ ≥ (4/3)bc is satisfies if n ≥ 64×(4/3)kXk2∞ s⋆ log(d)/κ1 ,
and we have
64kXk2∞ s⋆ log(d)
.
a≥−
κ1

Using this and the combinatorial inequality ds ≤ es log(de) , it follows that
h

i 2
E(n) Π̌n,d {θ ∈ Rd : kθk0 ≥ s⋆ + k}|Z ≤
d





64kXk2∞
κ̄1 (s⋆ )
log(4e)
4c2
+2 exp s⋆ log(d) 1 +
+
.
+
+ k log
κ1
64kXk2∞ log(d)2
log(d)
dc4

Then for α > 0, choose


2
log(4e)
64kXk2∞
2α
κ̄1 (s⋆ )
+
+
1+
s⋆ ,
(5.20) k =
+
c4
c4
κ1
64kXk2∞ (log(d))2
log(d)

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

29

to conclude that the second term on the right-hand side of the above inequality is upper-bounded by d2α , provided that dc4 /2 ≥ 4c2 . Setting α = 1
proves the theorem.
√
Proof of Part(2). We apply Theorem 3-Part(2) with λ̄ = ρ s̄ with ρ
as in (3.2) of the main paper, and s̄ = ζ + s⋆ , with ζ as in Part (1). We also
choose L̄ = nκ̄1 (s⋆ )/4,√Θ̄ = {θ ∈ Rd : kθ − θ⋆ k0 ≤ s̄}, the rate function
r(x) = nκ1 (s̄)x2 /(1 + s̄kXk∞ x/2), and En = En,0 (Θ̄, λ̄) ∩ Ên,1 (Θ⋆ , L̄) ∩
Eˇn,1 (Θ̄, r). With similar calculations as in Part (1), it is easy to establish
that
2
P(n) (Z ∈
/ En ) ≤ .
d
If θ ∈
/ Θ̄, then kθk0 > s̄ − s⋆ = ζ, and by Part (1), we conclude that
h
i 4
E(n) Π̌n,d (Rd \ Θ̄|Z) ≤ .
d
Recall that φr (a) = √
inf{x > 0 : r(z) − az ≥ 0, for all z ≥ x}. Since
r(x) = nκ1 (s̄)x2 /(1 + s̄kXk∞ x/2), if nκ1 (s̄) − s̄1/2 λ̄kXk∞ > 0, then
ǭ = φr (2λ̄) =

λ̄
.
nκ1 (s̄) − s̄1/2 λ̄kXk∞

Then we take n large enough so that (3/4)nκ1 (s̄) ≥ s̄1/2 λ̄kXk∞ , to conclude
that
r
16kXk∞ s̄ log(d)
4λ̄
λ̄
=
< ∞.
≤
ǭ =
nκ1 (s̄)
κ1 (s̄)
n
nκ1 (s̄) − s̄1/2 λ̄kXk∞
The condition (3/4)nκ1 (s̄) ≥ s̄1/2 λ̄kXk
p ∞ translates into the sample size
√
condition n ≥ (16/3)kXk2∞ (s̄/κ1 (s̄)) log(d), which holds by assumption.
We fix M0 ≥ max(500, 1 + (c3 + c4 /2)/8), and apply Theorem 3 to get:
(5.21)
h
n
o i 6 X
1 jM0 ǭ
Dj e− 8 r( 2 )
E(n) Π̌n,d θ ∈ Rd : kθ − θ⋆ k > M0 ǭ |Z ≤ +
d
j≥1
   c 3 s ⋆ 
s ⋆ X
1 jM0 ǭ
d
d
L̄
1/2
+2
e3ρs̄ jM0 ǭ e− 8 r( 2 ) .
1+ 2
s⋆
c1
ρ
j≥1

Since φr (a) is defined as inf{x > 0 : r(z) ≥ az, for all
√ z ≥ x}, and
jM0 ǭ/2 ≥ ǭ = φr (2λ̄), we have r(jM0 ǭ/2) ≥ 2λ̄(jM0 ǭ/2) = ρ s̄jM0 ǭ. Hence
(5.22)

X
j≥1



jM0 ǭ
− 18 r
2

e

≤

X
j≥1

√
− 18 jM0 s̄ρǭ

e

1

=

e− 8 M0

√

s̄ρǭ
√
− 81 M0 s̄ρǭ

1−e

≤ 2e−8M0 s̄ log(d) ,

30

YVES F. ATCHADÉ

where the last inequality follows from the bounds


√
√
s̄kXk2∞
λ̄
1
1
log(d) ≥ 8M0 s̄ log(d) ≥ 1
= 2M0
M0 s̄ρǭ ≥ M0 s̄ρ
8
8
nκ1 (s̄)
κ1 (s̄)
since 8M0 s̄ ≥ 16M0 /c4 ≥ 1, and log(d) ≥ 1, by assumption. Using the
arguments in Example 7.1 of [19] shows that the packing numbers Dj satisfies

supj≥1 Dj ≤ ds̄ (24)s̄ ≤ (24)s̄ es̄ log(de) . It follows that



X
jM ǭ
log(24e)
− 18 r( 20 )
Dj e
− 8M0
≤ 2 exp s̄ log(d) 1 +
log(d)
j≥1

≤

2
,
d

provided that log(d) ≥ 1, and using the condition 8M0 ≥ c4 /2+1+log(24e).
Setting x = jM0 ǭ/2, we have
!
√
√
1 jM0 ǭ
nκ1 (s̄)x
x
√
− 48ρ s̄ ,
3ρ s̄jM0 ǭ − r(
) ≤ −
8
2
8 1 + 12 s̄kXk∞ x
!
√
nκ1 (s̄) M20 ǭ
x
≤ −
− 48ρ s̄
√
8 1 + 12 s̄kXk∞ M20 ǭ
√
2ρ s̄x
(5.23)
,
≤ −
8
provided that

√
√
nκ1 (s̄) M20 ǭ
− 48ρ s̄ ≥ 2ρ s̄.
√
M0 ǭ
1
1 + 2 s̄kXk∞ 2
p
√
This latter condition holds for all M0 ≥ 500, if n > 125s̄kXk2∞ log(d)/κ1 (s̄).
In which case, from (5.23) we have
X
j≥1

e3ρs̄

1/2 jM

0 ǭ

1

e− 8 r(

jM0 ǭ
)
2

≤

X
j≥1

1

e− 8 jM0

√

s̄ρǭ

(a)

≤ 2e−8M0 s̄ log(d) ,

where the inequality (a) uses (5.22). In conclusion, the last term on the
right-hand side of (5.21) is upper-bounded by
(5.24)


   c 3 s ⋆ 
s
d
d
log(e/c1 )
L̄ ⋆ −8M0 s̄ log(d)
e
≤ 4 exp s⋆ log(d) 1 + c3 +
4
1+ 2
s⋆
c1
ρ
log(d)


κ̄1 (s⋆ )
+
− 8M0 s̄ log(d) .
64kXk2∞ log(d)2

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

31

Given that s̄ = s⋆ + ζ with ζ as in Part (1), since log(d) ≥ log(e/c1 ), and
8M0 ≥ 2 + c3 , we see that the right-side of (5.24) is upper-bounded by
4(1/d)16M0 /c4 ≤ (4/d). The theorem follows.
5.3. Proof of Theorem 9 and 10. It is obvious that H1 and H2 hold for
this example. For convenience in the notation, for z ∈ Rn×p , 1 ≤ j ≤ p, we
let z (j) ∈ Rn×p be the matrix obtained by replacing all the components of
the j-th column of z by 1. We introduce

 
P
u
+
u
z
exp
z
j
ij
k6=j k ik
def
(j)

 ,
qn,u
(z) =
P
1
+
exp
u
+
u
z
i=1
j
k6=j k ik
E
D
def
(j)
(j)
(j)
, u ∈ Rp .
(z),
u
−
θ
(z)−
∇
log
q
and L(j)
(z)
=
log
q
(z)−log
q
⋆·j
n,u
n,u
n,θ⋆·j
n,θ⋆·j
n
Y

(j)

The function u 7→ qn,u (z) is the likelihood function of the logistic regresdef

(j)

sion model of the j-column of z on z (j) . Let Hn (z) = −∇(2) log qn,θ⋆·j (z).
Specifically, we have


n
X
X
def
(j) (j)
g(2) θ⋆jj +
(Hn(j) (z))st =
zik θ⋆kj  zis zit , 1 ≤ s, t ≤ p.
i=1

k6=j

(j)

We will need the following restricted smallest eigenvalues of Hn (z).


 u′ (H(j) (z))u

X
X
def
n
(j)
p
,
u
∈
R
\
{0},
|u
|
≤
7
|u
|.
.
κ2 (z) = inf
k
k
 nkuk2

k: δ⋆,kj =0

def
(j)
κ2 (s, z) =

inf

(

)
(j)
u′ (Hn (z))u
, u ∈ Rp \ {0}, kuk0 ≤ s. .
nkuk2

(j)

κ2 (z) = inf κ2 (z),
1≤j≤p

k: δ⋆,kj =1

(j)

and κ2 (s, z) = inf κ2 (s, z).
1≤j≤p

The next result shows that if κ2 (s) > 0 and κ2 > 0 (with κ2 (s) and κ2
as defined in (4.4) of the main paper, then with high probability κ2 (Z) > 0
and κ2 (s, Z) > 0. The proof is an easy modification of the argument of
[4] Lemma 2.5. We omit the details.
Lemma 15. Assume C1. There exist finite universal constants a1 , a2
such that the following two statements holds true.

32

YVES F. ATCHADÉ

2

1. For 1 ≤ s ≤ p, if κ2 (s) > 0, and n ≥ a1 κ s(s) log(p), then
2


κ (s)
P(n) κ2 (s, Z) ≤ 2
≤ e−a2 n .
2
 2
2. If κ2 > 0, and n ≥ a1 sκ⋆ log(p), then

κ 
P(n) κ2 (Z) ≤ 2 ≤ e−a2 n .
2

Proof of Theorem 9-Part(1). We will reduce the result to Theorem
4 Part(1). We set
def

(j)

G (j) = {z ∈ Rn×p : κ2 (z) > κ2 /2},
def

def

and G = {z ∈ Rn×p : κ2 (z) > κ2 /2}.
def

We also define A(j) = {u ∈ Rp : kuk0 ≤ ζj }. Define Θ = {θ ∈ Rp×p :
kθ·j k0 ≤ s̄j , 1 ≤ j ≤ p}. Hence if θ ∈
/ Θ, then θ·j ∈
/ A(j) , for some j.
Therefore,
p
h

i
h

i
X
(n)
d×d
(n)
E(n) 1G (Z)Π̌n,d,j Rd \ A(j) |Z .
E
Π̌n,d R
\ Θ|Z ≤ P (Z ∈
/ G)+
j=1

Note that G ⊆ G (j) , and {Z ∈ G (j) } is Z (j) −measurable. Hence by conditioning on Z (j) , we get
h

i
E(n) Π̌n,d Rd×d \ Θ|Z ≤ P(n) (Z ∈
/ G)
+

p
X
j=1

h
ii


h
E(n) 1G (j) (Z)E(n) Π̌n,d,j Rd \ A(j) |Z |Z (j)

By conditioning on Z (j) , and for Z ∈ G (j) , we are taken back to the setting
of the standard logistic regression with a well-behaved design matrix. With
the
p choice of ζj , and since ρ in (4.5) of the main paper is taken larger than
4 n log(p), by Theorem 4 (1), there exists an absolute constant A1 such
that for pc4 ≥ 8c2 max(1, 2c2 ), and n ≥ A1 (s⋆ /κ2 )2 log(p), we have
h
i


4
E(n) Π̌n,d,j Rd \ A(j) |Z |Z (j) ≤ 2 .
p

The term p2 in 4/p2 comes from using α = 2 in (5.20). Without any loss
of generality we can take A1 as large as the constant a1 in Lemma 15 to
conclude that P(n) (Z ∈
/ G) ≤ e−a2 n . Hence
h

i
4
E(n) Π̌n,d Rd×d \ Θ|Z ≤ e−a2 n + ,
p
as claimed.

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

33

Proof of Theorem 9-Part(2). We shall apply Theorem 3-Part(2). We
will apply the theorem with the split cone
def

Θ̄ = {θ ∈ Rd×d : kθ·j k0 ≤ s̄j , 1 ≤ j ≤ p}.
Here the norm k · k2 in Theorem 3 is the Frobenius norm k·kF , whereas the
notation k · k2 in what follows will denote the Euclidean norm on Rp . Notice
that if θ ∈
/ θ⋆ + Θ̄, then θ ∈
/ Θ (where Θ is as defined in Theorem 9). Hence

we will use Theorem 9 to control the term E(n) Π̌n,p (Rd×d \ (θ⋆ + Θ̄)|Z) .
More precisely, there exist universal positive constants A1 , A2 such that for
pc4 ≥ 8c2 max(1, 2c2 ), and n ≥ A1 (s⋆ /κ2 )2 log(p),
(5.25)



4
E(n) Π̌n,p (Rd×d \ (θ⋆ + Θ̄)|Z) ≤ e−A2 n + .
p

√
def P
Set S̄ = pj=1 s̄j , λ̄ = ρ S̄, L̄ = ns⋆ /4, r(x) = nκ(s̄)x2 /(2 + S̄ 1/2 x), and
consider En = En,0 (Θ̄, λ̄) ∩ Eˆn,1 (Θ⋆ , L̄) ∩ Eˇn,1 (Θ̄, r). We have
v
uX
u p
s̄j k∇ log qn,θ⋆ (Z)k∞ .
sup
h∇ log qn,θ⋆ (Z), uiF ≤ t
u∈Θ̄, kukF =1

j=1

Using this and a standard Hoeffding inequality, we obtain that
(5.26)

2 


λ̄
1
 q
  ≤ 2,
P(n) Z ∈
/ En,0 (Θ̄, λ̄) ≤ 2 exp 2 log(p) −
P
p
2n 2
p
j=1 s̄j

given the choice of λ̄, and ρ in (4.5).
(j)
We use a second order Taylor expansion of u 7→ qn,u (z) around θ⋆·j and
(2)
the fact that g (x) ≤ 1/4 to deduce that for all θ ∈ θ⋆ + Θ⋆
!
p
(j) ]′ [Z (j) ]
ns⋆
[Z
nX
(θ·j − θ⋆·j ) ≥ −
(θ·j − θ⋆·j )′
kθ − θ⋆ k2F .
Ln,θ (z) = −
8
n
8
j=1

Hence with L̄ = ns⋆ /4,
(5.27)

P(n) (Z ∈
/ Ên,1 (Θ⋆ , L̄)) = 0.

Consider the set
def

G (j) = {z ∈ Rn×p : κ(j) (s̄, z) > κ(s̄)/2},

def

and G = {z ∈ Rn×p : κ(s̄, z) > κ(s̄)/2}.

34

YVES F. ATCHADÉ

Take Z ∈ G. Then for all j, κ(s̄, Z (j) ) > κ(s̄)/2 and we can use the same
argument in (5.19) to conclude that for θ − θ⋆ ∈ Θ̄,
(j)

Ln,θ·j (Z) ≤ −

nκ(s̄)kθ·j − θ⋆·j k22 /2
.
√
2 + s̄j kθ·j − θ⋆·j k2

It follows that for θ − θ⋆ ∈ Θ̄,
Ln,θ (Z) ≤ −

p
X
nκ(s̄)kθ·j − θ⋆·j k22 /2
1 nκ(s̄) kθ − θ⋆ k2F
1
≤
−
= − r(kθ − θ⋆ kF ).
√
2 + s̄j kθ·j − θ⋆·j k2
2 2 + S̄ 1/2 kθ − θ⋆ kF
2
j=1

Hence, with the rate function r(x) = nκ(s̄)x2 /(2 + S̄ 1/2 x), we have

(5.28)
P(n) Z ∈
/ Eˇn,1 (Θ̄, r) ≤ P(n) (Z ∈
/ G) ≤ e−a2 n ,

2

s̄
log(p) (without any loss
as seen in Lemma 15, provided that n ≥ A1 κ(s̄)
of generality, we take A1 greater than the constant a1 in Lemma 15). Hence,
with En = En,0 (Θ̄, λ̄) ∩ Ên,1 (Θ⋆ , L̄) ∩ Eˇn,1 (Θ̄, r), it follows from (5.26)-(5.28)
2

s̄
log(p)
that for n ≥ A1 κ(s̄)
2
P(n) (Z ∈
/ En ) ≤ e−a2 n + .
p

(5.29)

Finally, we note that with the same calculations as in the proof of Theorem
2

S̄
log(p),
4 Part(2), we can choose the constant a1 such that for n ≥ A1 κ(s̄)
2λ̄
4λ̄
96
≤ ǭ = φr (2λ̄) ≤
≤
nκ(s̄)
nκ(s̄)
κ(s̄)

r

S̄ log(p)
< ∞.
n

We are then ready to apply Theorem 3-Part(2). Fix M0 ≥ max(500, 1 +
def

(c3 + c4 /2)/8), set V = {θ ∈ Rd×d : kθ − θ⋆ kF > M0 ǭ}, then for n ≥

2
S̄
A1 κ(s̄)
log(p), (2.9), (5.25), and (5.29) give

(5.30)
E

(n)



 X
1 jM0 ǭ
2
+ e
+
+
Dj e− 8 r( 2 )
e
p
j≥1


s
   c3 s⋆j 
p
Y
L̄ ⋆j  X − 1 r( kM0 ǭ ) 3ρc0 kM0 ǭ
p
p
e 8 2 e
+
1+ 2
2
.


c1
ρ
s⋆j


Π̌n,d (V |Z) ≤
j=1



−A2 n

4
+
p





−a2 n

k≥1

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

35

Similar calculations as in the proof of Theorem 4 Part(2) shows that
X

1

Dj e− 8 r(

j≥1

jM0 ǭ
)
2

≤

2
, and
p

X

1

e− 8 r(

j≥1

jM0 ǭ
)
2

e3ρc0 jM0 ǭ ≤ 2e−16M0 S̄ log(p) ,

and
   c3 s⋆j 
s
p
Y
p
p
L̄ ⋆j
2
1+ 2
s⋆j
c1
ρ
j=1





p
X
s⋆
log(e/c1 )
.
+
s⋆j  log(p) 1 + c3 +
≤ 2p exp 
2
log(p)
4(24 ) log(p)2
j=1

Hence, and by the same argument as in the proof of Theorem 4 Part(2), the
last term on the right-side of (5.30) is bounded by 4/p.
Proof of Theorem 10. We will reduce this result to Theorem 4 Part(2).
We set
def
V = {θ ∈ Rp×p : kθ·j k2 > ǫj , for some j},
def

and V̄ = Θ̄ ∩ V, where Θ̄ = {θ ∈ Rd×d : kθ·j k0 ≤ s̄j , 1 ≤ j ≤ p}. Using
Theorem 9 as we did in (5.25), there exist universal positive constants A1 , A2
such that for pc−4 ≥ 8c2 max(1, 2c2 ), and n ≥ A1 (s⋆ /κ2 )2 log(p),
h
i




E(n) Π̌n,d (V|Z) ≤ E(n) Π̌n,d (Rd×d \ Θ̄|Z) + E(n) Π̌n,d (V̄|Z) ,
≤ e−A2 n +

We define
def

(j)



4
+ E(n) Π̌n,d (V̄|Z) .
p

G (j) = {z ∈ Rn×p : κ2 (z) > κ2 /2},

def

and G = {z ∈ Rn×p : κ2 (z) > κ2 /2}.

def

We also define A(j) = {u ∈ Rp : kuk0 ≤ s̄j , and kuk2 > ǫj }. Hence, if
θ ∈ V̄, then θ·j ∈ A(j) , for some j. Therefore,
p
h
ii
h


X


E(n) 1G (j) (Z)E(n) Π̌n,d,j A(j) |Z |Z (j)
E(n) Π̌n,d (V̄|Z) ≤ P(n) (Z ∈
/ G)+
j=1



Fix M0 ≥ max(125, c4 (1 + c3 )/64). E(n) Π̌n,d,j A(j) |Z is the same as the
posterior distribution of the logistic regression of the j-th column of Z on

36

YVES F. ATCHADÉ

Z (j) , and for Z (j) ∈ G (j) , we can apply Theorem 4 Part(2). Hence, we can
take A1 large enough so that for p ≥ e(1 + c1 )/c1 , and n ≥ A1 (s̄/κ2 )2 log(p),
h
i


8
1G (j) (Z)E(n) Π̌n,d,j A(j) |Z |Z (j) ≤ 2 .
p
Hence



12
E(n) Π̌n,d (V|Z) ≤ 2e−A2 n + .
p

Acknowledgements. The author would like to thank Shuheng Zhou
for very helpful conversations on restricted convexity.

References.
[1] Alquier, P. and Lounici, K. (2011). PAC-Bayesian bounds for sparse regression
estimation with exponential weights. Electron. J. Stat. 5 127–145.
[2] Arias-Castro, E. and Lounici, K. (2014). Estimation and variable selection with
exponential weights. Electron. J. Stat. 8 328–354.
[3] Atchadé, Y. F. (2016). Supplement to “On the contraction properties of some
high-dimensional quasi-posterior distributions”. DOI:xxx.
[4] Atchadé, Y. F. (2014). Estimation of high-dimensional partially-observed discrete
Markov random fields. Electronic Journal of Statistics 8 2242–2263.
[5] Atchadé, Y. F. (2015).
A Moreau-Yosida approximation scheme for highdimensional posterior and quasi-posterior distributions. ArXiv e-prints .
[6] Atchadé, Y. F. (2015). A scalable quasi-Bayesian framework for Gaussian graphical
models. ArXiv e-prints .
[7] Bach, F. (2010). Self-concordant analysis for logistic regression. Electron. J. Statist.
4 384–414.
[8] Banerjee, O., El Ghaoui, L. and d’Aspremont, A. (2008). Model selection
through sparse maximum likelihood estimation for multivariate Gaussian or binary
data. J. Mach. Learn. Res. 9 485–516.
[9] Banerjee, S. and Ghosal, S. (2015). Bayesian structure learning in graphical
models. Journal of Multivariate Analysis 136 147 – 162.
[10] Barber, R. F. and Drton, M. (2015). High-dimensional ising model selection with
bayesian information criteria. Electron. J. Statist. 9 567–607.

HIGH-DIMENSIONAL QUASI-POSTERIOR DISTRIBUTIONS

37

[11] Baricz, A. (2008). Mills’ ratio: Monotonicity patterns and functional inequalities.
Journal of Mathematical Analysis and Applications 340 1362 – 1370.
[12] Besag, J. (1974). Spatial interaction and the statistical analysis of lattice systems.
J. Roy. Statist. Soc. Ser. B 36 192–236.
[13] Castillo, I., Schmidt-Hieber, J. and van der Vaart, A. (2015). Bayesian linear
regression with sparse priors. Ann. Statist. 43 1986–2018.
[14] Castillo, I. and van der Vaart, A. (2012). Needles and straw in a haystack:
Posterior concentration for possibly sparse sequences. Ann. Statist. 40 2069–2101.
[15] Catoni, O. (2004). Statistical learning theory and stochastic optimization, vol. 1851
of Lecture Notes in Mathematics. Springer-Verlag, Berlin. Lecture notes from the
31st Summer School on Probability Theory held in Saint-Flour, July 8–25, 2001.
[16] Chernozhukov, V. and Hong, H. (2003). An MCMC approach to classical estimation. J. Econometrics 115 293–346.
[17] Dalalyan, A. S. and Tsybakov, A. B. (2007). Aggregation by exponential weighting and sharp oracle inequalities. In Learning theory, vol. 4539 of Lecture Notes in
Comput. Sci. Springer, Berlin, 97–111.
[18] Florens, J.-P. and Simoni, A. (2012). Nonparametric estimation of an instrumental
regression: A quasi-bayesian approach based on regularized posterior. Journal of
Econometrics 170 458 – 475.
[19] Ghosal, S., Ghosh, J. K. and van der Vaart, A. W. (2000). Convergence rates
of posterior distributions. Ann. Statist. 28 500–531.
[20] Ghosh, J. K. and Ramamoorthi, R. V. (2003). Bayesian nonparametrics. Springer
Series in Statistics, Springer-Verlag, New York.
[21] Höfling, H. and Tibshirani, R. (2009). Estimation of sparse binary pairwise
Markov networks using pseudo-likelihoods. J. Mach. Learn. Res. 10 883–906.
[22] Kato, K. (2013). Quasi-Bayesian analysis of nonparametric instrumental variables
models. Ann. Statist. 41 2359–2390.
[23] Kleijn, B. J. K. and van der Vaart, A. W. (2006). Misspecification in infinitedimensional Bayesian statistics. Ann. Statist. 34 837–877.
[24] Li, C. and Jiang, W. (2014). Model Selection for Likelihood-free Bayesian Methods
Based on Moment Conditions: Theory and Numerical Examples. ArXiv e-prints .
[25] Li, Y.-H., Scarlett, J., Ravikumar, P. and Cevher, V. (2014). Sparsistency of
ℓ1 -regularized M-estimators. arXiv preprint arXiv:1410.7605 .
[26] Liao, Y. and Jiang, W. (2011). Posterior consistency of nonparametric conditional
moment restricted models. Ann. Statist. 39 3003–3031.
[27] Marin, J.-M., Pudlo, P., Robert, C. and Ryder, R. (2012). Approximate
bayesian computational methods. Statistics and Computing 22 1167–1180.
[28] McAllester, D. A. (1999). Some pac-bayesian theorems. Machine Learning 37
355–363.
[29] Meinshausen, N. and Buhlmann, P. (2006). High-dimensional graphs with the
lasso. Annals of Stat. 34 1436–1462.
[30] Mitchell, T. J. and Beauchamp, J. J. (1988). Bayesian variable selection in linear
regression. JASA 83 1023–1032.
[31] Negahban, S. N., Ravikumar, P., Wainwright, M. J. and Yu, B. (2012). A
unified framework for high-dimensional analysis of m-estimators with decomposable
regularizers. Statistical Science 27 538–557.
[32] Ravikumar, P., Wainwright, M. J. and Lafferty, J. D. (2010). Highdimensional Ising model selection using ℓ1 -regularized logistic regression. Ann.
Statist. 38 1287–1319.
[33] Schreck, A., Fort, G., Le Corff, S. and Moulines, E. (2013). A shrinkage-

38

YVES F. ATCHADÉ

thresholding Metropolis adjusted Langevin algorithm for Bayesian variable selection.
ArXiv e-prints .
[34] Sun, T. and Zhang, C.-H. (2013). Sparse Matrix Inversion with Scaled Lasso.
Journal of Machine Learning Research 14 3385–3418.
[35] Yang, W. and He, X. (2012). Bayesian empirical likelihood for quantile regression.
Ann. Statist. 40 1102–1131.
[36] Zhang, T. (2006). From ǫ-entropy to KL-entropy: Analysis of minimum information
complexity density estimation. The Annals of Statistics 34 pp. 2180–2210.
Yves F. ATCHADÉ
University of Michigan
Department of Statistics
1085 South University
Ann Arbor, 48109, MI, United States
E-mail: yvesa@umich.edu

arXiv:1508.07929v4 [] 19 Nov 2016

???
??? ???
e-mail: ???

1
imsart-generic ver. 2014/10/16 file: ims-template.tex date: November 22, 2016

