1

Finite-sample risk bounds for maximum likelihood
estimation with arbitrary penalties

arXiv:1712.10087v1 [math.ST] 29 Dec 2017

W. D. Brinda and Jason M. Klusowski, Student Member, IEEE

Abstract—The MDL two-part coding index of resolvability
provides a finite-sample upper bound on the statistical risk of
penalized likelihood estimators over countable models. However,
the bound does not apply to unpenalized maximum likelihood
estimation or procedures with exceedingly small penalties. In
this paper, we point out a more general inequality that holds for
arbitrary penalties. In addition, this approach makes it possible to
derive exact risk bounds of order 1/n for iid parametric models,
which improves on the order (log n)/n resolvability bounds. We
conclude by discussing implications for adaptive estimation.
Index Terms—Penalized likelihood estimation, minimum description length, codelength, statistical risk, redundancy

I. I NTRODUCTION
Remarkably general method for bounding the statistical
risk of penalized likelihood estimators comes from work
on two-part coding, one of the minimum description length
(MDL) approaches to statistical inference. Two-part coding
MDL prescribes assigning codelengths to a model (or model
class) then selecting the distribution that provides the most
efficient description of one’s data [1]. The total description
length has two parts: the part that specifies a distribution
within the model (as well as a model within the model class if
necessary) and the part that specifies the data with reference
to the specified distribution. If the codelengths are exactly
Kraft-valid, this approach is equivalent to Bayesian maximum
a posteriori (MAP) estimation, in that the two parts correspond
to log reciprocal of prior and log reciprocal of likelihood
respectively. More generally, one can call the part of the
codelength specifying the distribution a penalty term; it is
called the complexity in MDL literature.
Let (Θ, L) denote a discrete set indexing distributions along
with a complexity function. With X ∼ P , the (pointwise)
redundancy of any θ ∈ Θ is its two-part codelength minus
log(1/p(X)), the codelength one gets by using P as the
coding distribution.1 The expectation of redundancy is the
relative entropy from P to Pθ plus L(θ). Let θ∗ ∈ Θ denote
the minimizer of expected redundancy; it is the average-case
optimal representative from (Θ, L) when the true distribution
is P . Its expected redundancy will be denoted

A

RΘ,L (P ) := inf {D(P kPθ ) + L(θ)},
θ∈Θ

W. D. Brinda and Jason M. Klusowski are with the Department of
Statistics & Data Science, Yale University, New Haven, CT, USA e-mail:
{william.brinda, jason.klusowski}@yale.edu.
1 For now, we mean that P governs the entirety of the data. The notion
of sample size and iid assumptions are not essential to the bounds, as will
be seen in the statement of Theorem II.1. Specialization to iid data will be
discussed thereafter.

or in the context of iid data X n ∼ P n and iid modeling
{Pθn : θ ∈ Θ}, its expected redundancy rate is denoted
(n)



L(θ)
.
D(P kPθ ) +
θ∈Θ
n

RΘ,L (P ) := inf

Interestingly, [2] showed that if the complexity function
is large enough, then the corresponding penalized likelihood
estimator outperforms the best-case average representative.
Specifically, the statistical risk is bounded by RΘ,L (P ); that
result is stated for iid sampling in (2) below.2
There are a number of attractive features of the resolvability
bound; we will highlight four. One of the most powerful
aspects of the resolvability bound is the ease with which it can
be used to devise adaptive estimation procedures for which the
bound applies. For instance, to use a class of nested models
rather than a single model, one only needs to tack on an
additional penalty term corresponding to a codelength used
to specify the selected model within the class.
Another nice feature is its generality: the inequality statement only requires that the data-generating distribution has
finite relative entropy to some probability measure in the
model.3 In practice, the common assumptions of other risk
bound methods, for instance, that the generating distribution
belongs to the model, are unlikely to be exactly true.
A third valuable property of the bound is its exactness
for finite samples. Many risk bound methods only provide
asymptotic bounds. But such results do not imply anything
exact for a data analyst with a specific sample.
Lastly, the resolvability bound uses a meaningful loss function: α-Renyi divergence [4] with α ∈ (0, 1). For convenience,
we specialize our discussion and our present work to Bhattacharyya divergence [5] which is the 12 -Renyi divergence.
DB (P, Q) := 2 log

1
,
A(P, Q)

2 Throughout the paper, we will refer to this inequality as “the resolvability
bound,” but realize that there are a variety of related resolvability bounds
in other contexts. They involve comparing risk to a codelength and lead to
bounds that are suboptimal by a log n factor.
3 Although the forthcoming resolvability bounds (i.e., as in (2) with L that is
at least twice a codelength function) are valid under misspecification, they do
not in general imply consistency in the sense that the corresponding penalized
estimator eventually converges to the element θ ′ of Θ that minimizes KL or
Hellinger to the truth P . Indeed, there are various examples [3] in which
the twice-codelength penalized estimator is inconsistent (i.e., provably never
converges to θ ′ ).

2

where A denotes the Hellinger affinity
Z p
p(x)q(x)dx
A(P, Q) :=
s
q(X)
= EX∼P
.
p(X)

Our bounds can be used for the penalized MLE over a
discretization of an unbounded parameter space under a power
decay condition on the Hellinger affinity, as in Theorems
II.11 and II.12. We show that such a condition is satisfied
by exponential families of distributions with a boundedness
assumption on the largest eigenvalue of the covariance matrix of their sufficient statistics (see Lemma II.9). For these
Like relative entropy, DB decomposes product measures into models and others, we establish order 1/n bounds for the
sums; that is,
Bhattacharyya risk. The primary focus of this paper is to
n
n
n
n
n
A(P , Q ) = A(P, Q)
thus DB (P , Q ) = nDB (P, Q). develop new tools towards this end.
One highly relevant line of work is [13], where he estabBhattacharyya divergence is bounded below by squared lished a more general resolvability risk bound for “posterior”
Hellinger distance (using log 1/x ≥ 1 − x) and above by distributions on the parameter space. Implications for penalrelative entropy (using Jensen’s inequality). Importantly, it ized MLEs come from forcing the “posteriors” to be point(n)
has a strictly increasing relationship with squared Hellinger masses. He derives risk bounds that have the form of RΘ,L
(P )
distance DH , which is an f -divergence:
plus a “corrective” term, which is comparable to the form of
our results. Indeed, as we will point out, one of our corollaries
1
.
DB = 2 log
nearly coincides with [13, Thm 4.2] but works with arbitrary
1 − DH /2
penalties.
As such, it inherits desirable f -divergence properties such
The trick we employ is to introduce an arbitrary function
as the data processing inequality. Also, it is clear from the L, which we call a pseudo-penalty, that adds to the penalty
definition that DB is parametrization-invariant. For many L; strategic choices of pseudo-penalty can help to control the
more properties of DB , including its bound on total variation “penalty summation” over the model. The resulting risk bound
distance, see [6].
has an additional EL(θ̂) term that must be dealt with.
Next, we make note of some of the limitations of the
In Section II, we prove our more general version of the
resolvability bound. One complaint is that it is for discrete resolvability bound inequality using a derivation closely analparameter sets, while people generally want to optimize penal- ogous to the one by [14]. We then explore corollaries that
ized likelihood over a continuous parameter space. In practice, arise from various choices of pseudo-penalty. In Section III,
one typically selects a parameter value that is rounded to a we explain how our approach applies in the context of adaptive
fixed precision, so in effect the selection is from a discretized modeling. Additional work can be found in [15], includspace. However, for mathematical convenience, it is nice to ing some simple concrete examples [15, “Simples concrete
have risk bounds for the theoretical optimizer. A method examples”, Sec 2.1.2], extension to continuous models [15,
to extend the resolvability bound to continuous models was “Continuous parameter spaces”, Sec 2.2], and an application
introduced by [7]; in that paper, the method was specialized to Gaussian mixtures [15, Chap 4].
to estimation of a log density by linear combinations from a
Every result labeled a Theorem or Lemma has a formal
finite dictionary with an l1 penalty on the coefficients. More proof, some of which are in the Appendix. Any result labeled
recently, [8] worked out the continuous extension for Gaussian a Corollary is an immediate consequence of previously stated
graphical models (building on [9]) with l1 penalty assuming results and thus no formal proof is provided. For any random
the model is well-specified and for linear regression with vector X, the notation CX means the covariance matrix, while
l0 penalty assuming the true error distribution is Gaussian. VX represents its trace EkX − EXk2 . The notation λj (·)
These results are explained in more detail by [10], where the means the jth eigenvalue of the matrix argument. Whenever
extension for the l1 penalty for linear regression is also shown, a capital letter has been introduced to represent a probability
again assuming the true error distribution is Gaussian.
distribution, the corresponding lower-case letter will represent
Another limitation is that the resolvability bound needs a density for the measure with respect to either Lebesgue
a large enough penalty; it must have a finite Kraft sum. or counting measure. The penalized MLE is the (random)
This paper provides a more general inequality that escapes parameter that maximizes log-likelihood minus penalty. The
such a requirement and therefore applies even to unpenalized notation D(P kΘ) represents the infimum relative entropy from
maximum likelihood estimation. The resulting bound retains P to distributions indexed by the model Θ. Multiplication and
the four desirable properties we highlighted above, but loses division take precedence over ∧ and ∨; for instance, ab ∧ c
the coding and resolvability interpretations.
means (ab) ∧ c.
Finally, the resolvability bounds for smooth parametric iid
modeling are of order (log n)/n and cannot be improved, acII. M ODELS WITH COUNTABLE CARDINALITY
cording to [11], whereas under regularity conditions (for which
Bhattacharyya divergence is locally equivalent to one-half
Let us begin with countable (e.g. discretized) models, which
relative entropy, according to [7]) the optimal Bhattacharyya were the original context for the MDL penalized likelihood
risk is of order 1/n [12]. Our variant on the resolvability risk bounds. We will show that a generalization of that
method leads to the possibility of deriving exact bounds of technique works for arbitrary penalties. The only assumption
order 1/n.
we need is that for any possible data, there exists a (not

3

necessarily unique) minimizer of penalized likelihood.4 This
existence requirement will be implicit throughout our paper.
Theorem II.1 gives a general result that is agnostic about any
structure within the data; the consequence for iid data with
sample size n is pointed out after the proof.
Theorem II.1. Let X ∼ P , and let θ̂ be the penalized MLE
over Θ indexing a countable model with penalty L. Then for
any L : Θ → R,

EDB (P, Pθ̂ ) ≤ RΘ,L (P )+
X − 1 [L(θ)+L(θ)]
+ EL(θ̂).
2 log
e 2
θ∈Θ

Returning to the overall inequality, we have
X − 1 [L(θ)+L(θ)]
+
EDB (P, Pθ̂ ) ≤ 2 log
e 2

 θ∈Θ

p(X)
E log
+ L(θ̂) + EL(θ̂)
pθ̂ (X)
X − 1 [L(θ)+L(θ)]
+
= 2 log
e 2
θ∈Θ



p(X)
E min log
+ L(θ) + EL(θ̂)
θ∈Θ
pθ (X)
X 1
≤ 2 log
e− 2 [L(θ)+L(θ)]+
θ∈Θ


p(X)
+ L(θ) + EL(θ̂)
inf E log
θ∈Θ
pθ (X)
X − 1 [L(θ)+L(θ)]
= 2 log
e 2
+


θ∈Θ

Proof. We follow the pattern of Jonathan Li’s version of the
resolvability bound proof [14].

1
DB (P, Pθ̂ ) := 2 log
A(P, Pθ̂ )
1
p
pθ̂ (X)/p(X)e− 2 [L(θ̂)+L(θ̂)]
= 2 log
+
A(P, Pθ̂ )
p(X)
+ L(θ̂) + L(θ̂)
log
pθ̂ (X)
p
1
X pθ (X)/p(X)e− 2 [L(θ)+L(θ)]
≤ 2 log
+
A(P, Pθ )
θ∈Θ

log

p(X)
+ L(θ̂) + L(θ̂).
pθ̂ (X)

We were able to bound the random quantity by the sum over
all θ ∈ Θ because each of these terms is non-negative.
We will take the expectation of both sides for X ∼ P . To
deal with the first term, we use Jensen’s inequality and the
definition of Hellinger affinity.

p
1
pθ (X)/p(X)e− 2 [L(θ)+L(θ)]
A(P, Pθ )
θ∈Θ
p
1
X
pθ (X)/p(X)e− 2 [L(θ)+L(θ)]
≤ 2 log
E
A(P, Pθ )
θ∈Θ
X 1
= 2 log
e− 2 [L(θ)+L(θ)].

2E log

X

θ∈Θ

inf {D(P kPθ ) + L(θ)} + EL(θ̂).

θ∈Θ

Suppose now that the data comprise n iid observations and
are modeled as such; in other words, the data has the form
X n ∼ P n , and the model has the form {Pθn : θ ∈ Θ}. Because
DB (P n , Pθ̂n ) = nDB (P, Pθ̂ ) and D(P n kPθn ) = nD(P kPθ ),
we can divide both sides of Theorem II.1 by n to reveal the
role of sample size in this context:
(n)

EDB (P, Pθ̂ ) ≤ RΘ,L (P )+
1
P
2 log θ∈Θ e− 2 [L(θ)+L(θ)] + EL(θ̂)
.
n
We will see three major advantages to Theorem II.1. The
most obvious is that it can handle cases in which the sum of
exponential negative half penalties is infinite; unpenalized estimation, for example, has L identically zero. One consequence
of this is that the resolvability method for minimax risk upper
bounds can be extended to models that are not finitely covered
by relative entropy balls. We will also find that Theorem II.1
enables us to derive exact risk bounds of order 1/n rather than
the usual (log n)/n resolvability bounds.
In many cases, it is convenient to have only the L function
in the summation. Substituting L − L as the pseudo-penalty
in Theorem II.1 gives us a corollary that moves L out of the
summation.
Corollary II.2. Let X ∼ P , and let θ̂ be the penalized MLE
over Θ indexing a countable model with penalty L. Then for
any L : Θ → R,
EDB (P, Pθ̂ ) ≤ RΘ,L (P )+
X − 1 L(θ)
2 log
e 2
+ EL(θ̂) − EL(θ̂).
θ∈Θ

The iid data and model version is
(n)

4 We will say “the” penalized MLE, even though we do not require
uniqueness; any scheme can be used for breaking ties.

EDB (P, Pθ̂ ) ≤ RΘ,L (P )+
1
P
2 log θ∈Θ e− 2 L(θ) + EL(θ̂) − EL(θ̂)
.
n

4

We will use the term pseudo-penalty for the function labeled
L in either Theorem II.1 or Corollary II.2. Note that L is
allowed to depend on P but not on the data.
A probabilistic loss bound can also be derived for the
difference between the loss and the redundancy plus pseudopenalty.
Theorem II.3. Let X ∼ P , and let θ̂ be the penalized MLE
over Θ indexing a countable model with penalty L. Then for
any L : Θ → R,




p(X)
+ L(θ̂) + L(θ̂) ≥ t
P DB (P, Pθ̂ ) − log
pθ̂ (X)
X − 1 [L(θ)+L(θ)]
e 2
≤ e−t/2
.
θ∈Θ

Proof. Following the steps described in [7, Theorem 2.3], we
use Markov’s inequality then bound a non-negative random
variable by the sum of its possible values.




p(X)
P DB (P, Pθ̂ ) − log
+ L(θ̂) + L(θ̂) ≥ t
pθ̂ (X)
(
)
p
1
pθ̂ (X)/p(X)e− 2 [L(θ̂)+L(θ̂)]
= P 2 log
≥t
A(P, Pθ̂ )
)
(p
1
pθ̂ (X)/p(X)e− 2 [L(θ̂)+L(θ̂)]
=P
≥ et/2
A(P, Pθ̂ )
p
1
pθ̂ (X)/p(X)e− 2 [L(θ̂)+L(θ̂)]
−t/2
≤e
E
A(P, Pθ̂ )
X − 1 [L(θ)+L(θ)]
−t/2
≤e
e 2
.
θ∈Θ

iid

For iid data X n ∼ P and an iid model, Theorem II.3
implies
"
#
)
(
p(Xi )
1 X
log
+ L(θ̂) + L(θ̂) ≥ t
P DB (P, Pθ̂ ) −
n i
pθ̂ (Xi )
X − 1 [L(θ)+L(θ)]
.
≤ e−nt/2
e 2
θ∈Θ

Several of our corollaries have L and L designed to make
1
P
− 2 [L(θ)+L(θ)]
≤ 1. In such cases, the difference beθ∈Θ e
tween loss and the point-wise redundancy plus pseudo-penalty
is stochastically less than an exponential random variable.
Often the countable model of interest is a discretization of
a continuous model. Given any ǫ > 0, an ǫ-discretization of
Rd is v + ǫZd , by which we mean {v + mǫ : m ∈ Zd } for
some v ∈ Rd . An ǫ-discretization of Θ ⊆ Rd is a set of the
form Θ ∩ (v + ǫZd ). See Section III-D for a discussion of the
(n)
behavior of RΘ,L (P ) in that context.
To derive useful consequences of the above results, we
will explore some convenient choices of pseudo-penalty: zero,
Bhattacharyya divergence, log reciprocal pmf of θ̂, quadratic
forms, and the penalty. We specialize to the iid data and model
setting for the remainder of this document to highlight the fact
that many of the exact risk bounds we derive are of order 1/n
in that case.

A. Zero as pseudo-penalty
Setting L to zero gives us the traditional resolvability bound,
which we review in this section.
iid

Corollary II.4. Assume X n ∼ P , and let θ̂ be the penalized
MLE over Θ indexing a countable iid model with penalty L.
Then
1
P
2 log θ∈Θ e− 2 L(θ)
(n)
.
EDB (P, Pθ̂ ) ≤ RΘ,L (P ) +
n
The usual statement of the resolvability bound [7] assumes
L is at least twice a codelength function, so that it is large
enough for the sum of exponential terms to be no greater than
1. That is,
X 1
e− 2 L(θ) ≤ 1
(1)
θ∈Θ

implies

(n)

EDB (P, Pθ̂ ) ≤ RΘ,L (P ).

(2)

The quantity on the right-hand side of (2) is called the
index of resolvability of (Θ, L) for P at sample size n. Any
corresponding minimizer θ∗ ∈ Θ is considered to index an
average-case optimal representative for P at sample size n.
1
P
− 2 L(θ)
, the
In fact, for any finite sum z :=
θ∈Θ e
maximizer of the penalized likelihood is also the maximizer
with penalty L̃ := L + 2 log z. Thus one has a resolvability
bound of the form (2) with the equivalent penalty L̃, which
satisfies (1) with equality.
Additionally, the resolvability bounds give an exact upper
bound on the minimax risk for any model Θ that can be
covered by finitely many relative entropy balls of radius ǫ2 ; the
log of the minimal covering number is called the KL-metric
entropy M(ǫ). These balls’ center points are called a KL-net;
iid
we will denote the net by Θǫ . With data X n ∼ Pθ∗ for any
∗
θ ∈ Θ, the MLE restricted to Θǫ has the resolvability risk
bound


2M(ǫ)
EDB (Pθ∗ , Pθ̂ ) ≤ inf D(Pθ∗ kPθ ) +
θ∈Θǫ
n
2M(ǫ)
= inf D(Pθ∗ kPθ ) +
θ∈Θǫ
n
2M(ǫ)
2
.
≤ǫ +
n
If an explicit bound for M(ǫ) is known, then the overall risk
bound can be optimized over the radius ǫ — see for instance
[7, Section 1.5].
Because this approach to upper bounding minimax risk
requires twice-Kraft-valid codelengths, it only applies to models that can be covered by finitely many relative entropy
balls. However, Corollary II.2 reveals new possibilities for
establishing minimax upper bounds even if the cover is infinite.
Given any L, one can use any constant penalty that is at
P 1
least as large as 2 log e− 2 L(θ) + EL(θ̂) where θ̂ is the
unpenalized MLE on the net and the summation is taken
over those points.5 For a minimax result, one still needs this
5 Putting L = 0 into either Theorem II.1 or Corollary II.2 would give us
the same idea.

5

quantity to be uniformly bounded over all data-generating
distribution θ∗ ∈ Θ. See Corollary II.10 below as an example.

iid

B. Bhattacharyya divergence as pseudo-penalty
Important corollaries6 to Theorems II.1 and II.2 come from
setting the pseudo-penalty equal to αDB (P, Pθ ); the expected
pseudo-penalty is proportional to the risk, so that term can
be subtracted from both sides. For the iid scenario, we also
use the product property of Hellinger affinity: A(P n , Pθn ) =
A(P, Pθ )n .
The following corollaries serve as the starting point for the
main bounds in Theorems II.12 and II.11, after which, more
refined techniques are used in controlling the two terms in (3)
and (4).
iid

Corollary II.5. Assume X n ∼ P , and let θ̂ be the penalized
MLE over Θ indexing a countable iid model with penalty L.
Then for any α ∈ [0, 1],
EDB (P, Pθ̂ )


1
P
− 2 L(θ)
αn
e
2
log
A(P,
P
)
1  (n)
θ
θ∈Θ
.
RΘ,L (P ) +
≤
1−α
n

(3)

iid

Corollary II.6. Assume X n ∼ P , and let θ̂ be the penalized
MLE over Θ indexing a countable iid model with penalty L.
Then for any α ∈ [0, 1],
EDB (P, Pθ̂ )
"
#
P
2 log θ∈Θ A(P, Pθ )αn − EL(θ̂)
1
(n)
RΘ,L (P ) +
.
≤
1−α
n
(4)
For simplicity, the corollaries throughout this subsection
will use α = 1/2.
Consider a penalized MLE selected from an ǫ-discretization
of a continuous parameter space; as the sample size increases,
one typically wants to shrink ǫ to make the grid more refined
(see Section III-D). Examining Corollaries II.5 and II.6, we see
two opposing forces at work as n increases: the grid-points
themselves proliferate, while the nth power depresses the
terms in the summation. An easy case occurs when A(P, Pθ ) is
bounded by a Gaussian-shaped curve; we apply Corollary II.6
and invoke Lemma III.10.
iid

Corollary II.7. Assume X n ∼ P , and let θ̂ be the penalized
MLE over an ǫ-discretization Θǫ ⊆ Θ ⊆ Rd indexing an iid
∗ 2
model with penalty L. Assume A(P, Pθ ) ≤ e−ckθ−θ k for
some c > 0 and some θ∗ ∈ Θ. Then
EDB (P, Pθ̂ )

(n)

≤ 2 RΘǫ ,L (P ) +

2d log(1 +

√
2√2π
)
ǫ nc

n

− EL(θ̂)

√
With ǫ proportional to 1/ n, our bound on the summation
of Hellinger affinities is stable. Corollary II.8 sets L = 0 to
demonstrate a more concrete instantiation of this result.



.

6 Our Corollary II.5 was inspired by the very closely related result of [13,
Thm 4.2].

Corollary II.8. Assume X n ∼ P , and let θ̂ be the MLE over
an ǫ-discretization
Θǫ ⊆ Θ ⊆ Rd indexing an iid model using
p
∗ 2
ǫ = 2/n. Assume A(P, Pθ ) ≤ e−ckθ−θ k for some c > 0
∗
and some θ ∈ Θ. Then
√
4d log(1 + 4/ c)
.
EDB (P, Pθ̂ ) ≤ 2D(P kΘǫ) +
n
If P is Pθ∗ in an exponential family with natural parameter
indexed by Θ, then Hellinger affinities do have a Gaussianshaped bound as long as the minimum eigenvalue of the
sufficient statistic’s covariance matrix is uniformly bounded
below by a positive number. We use the notation λj (·) for the
jth largest eigenvalue of the matrix argument.
Lemma II.9. Let {Pθ : θ ∈ Θ ⊆ Rd } be an exponential family
with natural parameter θ and sufficient statistic φ. Then
A(Pθ∗ , Pθ ) ≤ e−ckθ−θ
where c :=

1
8

∗ 2

k

,

inf θ̃∈Θ λd (CX∼Pθ̃ φ(X)).

In Lemma II.9, c does not depend on θ∗ . If in addition the
ǫ-discretization is also a KL-net, then the risk of the estimator
described in Corollary II.8 is uniformly bounded over datagenerating distributions in Θ. The minimax risk is no greater
than the supremum risk of this particular estimator.
Corollary II.10. Let Θ ⊆ Rd index a set of distributions.
Assume that for some c > 0, every θ∗ ∈ Θ has the property
∗ 2
that A(Pθ∗ , Pθ ) ≤ e−ckθ−θ k . Assume further that there
exists β > 0 such that for all ǫ > 0, every ǫ-discretization
Θǫ ⊆ Θ is also a KL-net with balls of radius βǫ2 . Then the
minimax Bhattacharyya risk of Θ has the upper bound
√
4[β + d log(1 + 4/ c)]
∗
.
E
min max
,
P
)
≤
D
(P
iid
B
θ
n
θ̂
∗
n
θ̂ θ ∈Θ X ∼ Pθ∗
In general, however, Hellinger affinity being uniformly
bounded by a Gaussian curve may be too severe of a requirement. A weaker condition is to require only a power decay
for θ far from some θ∗ .
iid

Theorem II.11. Assume X n ∼ P , and let θ̂ be the penalized
MLE over an ǫ-discretization Θǫ ⊆ Θ ⊆ Rd indexing an iid
model with penalty L. Assume that for some θ∗ , θ̃∗ ∈ Θ, radius
R and a, c > 0, the Hellinger affinity A(P, Pθ ) is bounded
by a/kθ − θ∗ kb outside the ball B(θ∗ , R) and bounded by
∗ 2
e−ckθ−θ̃ k inside the ball. If R ≥ 11a1/b ∨ 3ǫ, and n ≥
2(d + 1)/b, then,
EDB (P, Pθ̂ )
"
(n)

≤ 2 RΘǫ ,L (P )+
d[2 log(1 +

√
2√2π
)
ǫ nc

+ 2 log(1 +
n

√
4 √2R
)]
ǫ nb

+ 3 − EL(θ̂)

#

.

6

Proof. The part of the summation where Hellinger affinity
is bounded by a Gaussian curve has the same bound as in
Corollary II.7, which is a direct consequence of Lemma III.10.
X
X
∗ 2
e−cαnkθ−θ̃ k
A(P, Pθ )αn ≤
θ∈Θǫ ∩B(θ ∗ ,R)

θ∈Θǫ ∩B(θ ∗ ,R)

≤
≤

X

e−cαnkθ−θ̃

∗ 2

k

θ∈Θǫ


√ d
2 π
.
1+ √
ǫ nαc

Notice that the “center” point for this Gaussian curve θ̃ can
be different from the center of the ball θ∗ .
The summation of the remaining terms is handled by
Lemma III.14, assuming n ≥ (d + 1)/αb.
X
A(P, Pθ )αn
(6)
≤
≤
≤

X

θ∈Θǫ ∩B(θ ∗ ,R)c



αn
a
kθ − θ∗ kb
!d

4R
p
ǫ nαb log(R/4a1/b )
4R

1+ p
ǫ nαb log(R/4a1/b )

!d

.

(7)

The assumption that R ≥ 11a1/b assures us that
log(R/4a1/b ) ≥ 1, simplifying the bound.
Each of (5) and (6) are at least 1, so by Lemma III.3, the
sum of their logs is bounded by the log of their sum plus
2 log 2. Finally, substitute α = 1/2.
The sample size requirement in Theorem II.11 can be
avoided by using a squared norm penalty. The bound we derive
has superlinear order in the dimension.
iid

Theorem II.12. Assume X n ∼ P , and let θ̂ be the penalized
MLE over an ǫ-discretization Θǫ ⊆ Θ ⊆ Rd indexing an
iid model with penalty L(θ) = kθk2 . Assume that for some
θ∗ , θ̃∗ ∈ Θ, radius R and a, c > 0, the Hellinger affinity
A(P, Pθ ) is bounded by a/kθ −θ∗ kb outside the ball B(θ∗ , R)
∗ 2
and bounded by e−ckθ−θ̃ k inside the ball. If R ≥ 11a1/b ∨3ǫ,
then
(n)

EDB (P, Pθ̂ ) ≤ 2RΘǫ ,k·k2 (P )+
h
√
2π
4d log(1 + 2ǫ√nc
) + log(1 +

As in Corollary II.7, the bounds in Theorems
II.11 and II.12
√
remain stable if ǫ is proportional to 1/ n.
As an example, we will see how these bound apply in a
location family parametrized by the mean in Θ ⊆ Rd . First,
we establish the power decay, assuming P has a finite first
moment. By Lemma III.18,

(5)
∗

θ∈Θǫ ∩B(θ ∗ ,R)c

and III.16. In each case, the bound is no greater than the one
we have claimed.

i
√
d+6R
29 √
)
ǫ nb

+
n
∗ 2
+ 2kθ k + 8
4 log(2 +
.
n
Proof. This time we use Corollary II.5 rather than Corollary II.6. The challenge is to bound the summation

αn
X
a
−kθk2
e
.
kθ − θ∗ kb
∗
c
22
2R
3)

θ∈Θǫ ∩B(θ ,R)

Assuming n ≥ 2(d + 1)/b, we can bound that term as in
Theorem II.11. With smaller n, we invoke Lemmas III.15

A(P, Pθ ) ≤

2(sP + sΘ )
,
kθ − θ∗ k

where θ∗ := EX∼P X, and the other constants are the first central moments sP := EX∼P kX − θ∗ k and sΘ := EX∼Pθ kX −
θk. Therefore, Theorems II.11 and II.12 apply if we can find
a Gaussian-shaped Hellinger affinity bound that holds inside
the ball centered at θ∗ with radius R = 22(sP + sΘ ) ∨ 3ǫ.
In particular, let us assume the model comprises distributions that are continuous with respect to Lebesgue measure.
Then we will also assume that P is continuous; otherwise, the
risk bound is infinite anyway. These assumptions ensure the
existence of exact medians, enabling us to use Lemma III.20.
Let v be the vector of marginal medians of the model
distribution with mean θ = 0. The marginal median vector
of any model distribution Pθ is then θ + v. Let mP be the
marginal median vector of P . By Lemma III.20, for any r ≥ 0,
the inequality
A(P, Pθ ) ≤ e−ckθ+v−mP k

2

1
times
holds for θ within B(mP − v, r), where c is 2d
the minimum squared marginal density of Pθ within r of
its median. It remains to identify an r large enough that
B(mP −v, r) contains B(θ∗ , R). Using the triangle inequality
and then Lemma III.4 to bound the distance between means
and medians,

kθ − (mP − v)k = kθ − θ∗ + v − (mP − θ∗ )k
≤ kθ − θ∗ k + kvk + kmP − θ∗ k
√
√
≤ kθ − θ∗ k + sΘ d + sP d.
For θ in the ball B(θ∗ , R), the first term
√is bounded by R. This
tells us that the ball B(mp − v, R + d(sΘ + sP )) contains
B(θ∗ , R).
Thus
√ if all the marginal densities of Pθ are positive within
R + d(sΘ + sP ) of their medians, then there is a positive c
for which
A(P, Pθ ) ≤ e−ckθ−(mP −v)k

2

in B(θ∗ , R), confirming that Theorems II.11 and II.12 hold.
If the data-generating distribution is itself in the location
family, then P = Pθ∗ and sP = sΘ . Thus the bound holds
uniformly over θ∗ ∈ Θ. If there exists β > 0 such that every
ǫ-discretization of the family is a KL-net with radius βǫ2 , then
a minimax risk bound can be derived in the same manner as
Corollary II.10.

7

C. Log reciprocal pmf of θ̂ as pseudo-penalty
In Section II-B, we chose a pseudo-penalty to have an
expectation that easy to handle; we only had to worry about the
resulting log summation. Now we will select a pseudo-penalty
with the opposite effect. We can eliminate Corollary II.2’s log
summation term by letting L be twice a codelength function.
The smallest resulting EL(θ̂) comes from setting L to be two
times the log reciprocal of the probability mass function of θ̂.
This expectation is the Shannon entropy H of the penalized
MLE’s distribution (i.e. the image measure of P under the
Θ-valued deterministic transformation θ̂).
iid

Corollary II.13. Let X n ∼ P , and let θ̂ be a penalized MLE
over all θ ∈ Θ indexing a countable iid model. Then
EDB (P, Pθ̂ ) ≤

(n)
RΘ,L (P )

2H(θ̂) − EL(θ̂)
+
.
n

It is known that the risk of the MLE is bounded by the logcardinality of the model (e.g. [14]); Corollary II.13 implies a
generalization of this fact for penalized MLEs:
(n)

EDB (P, Pθ̂ ) ≤ RΘ,L (P ) +

2 log |Θ| − EL(θ̂)
.
n

Importantly, Corollary II.13 also applies to models of infinite
cardinality.
Lemma II.14. Let Θǫ ⊆ Rd be an ǫ-discretization, and let θ̂
be a Θǫ -valued random vector. Suppose that for some θ∗ ∈ Rd
and some radius R ≥ 0, every θ ∈ Θǫ outside of B(θ∗ , R)
∗ 2
has probability bounded by e−ckθ−θ k . Then the entropy of
θ̂ has the bound
H(θ̂) ≤

d
2

 √ d
4 π
√
+ d log(1 +
ǫ c

2[c−1/2 ∨R∨3ǫ]
).
ǫ

√
√
If ǫ c ≤ 4 π, then this bound grows exponentially
in d. √
However,
√ if c and R are known, then one can set
ǫ ≥ 4 π/( c ∨ R/3) and find that H(θ̂) is guaranteed to
be bounded by 3d. Of course, one needs to take the behavior
of the index of resolvability into account as well; good overall
behavior will typically require that c has order n.
In certain models satisfying D(Pθ kPθ∗ ) ≥ akθ − θ∗ k2 for
some a > 0, we surmise that it may be possible to establish
the applicability of Lemma II.14 (with c having order n) by
using information theoretic large deviation techniques along
the lines of [16, Thm 19.2].

where Cθ̂ denotes the covariance matrix of the random vector
iid
θ̂(X n ) with X n ∼ P . For the log summation term, we note
that
X
X
′
2
e−(θǫ −Eθ̂) M(θǫ −Eθ̂) ≤
e−λd (M)kθǫ −Eθ̂k
θǫ ∈Θǫ

θǫ ∈Θǫ

≤

!d
√
2 π
,
1+ p
ǫ λd (M )

by Lemma III.10. Using αId as M gives us Corollary II.15.
iid

Corollary II.15. Assume X n ∼ P , and let θ̂ be the penalized
MLE over an ǫ-discretization Θǫ ⊆ Θ ⊆ Rd indexing an iid
model with penalty L. Then for any α ≥ 0,
(n)

EDB (P, Pθ̂ ) ≤ RΘǫ ,L (P )+
2d log(1 +

√
2√ π
)
ǫ α

+ αVθ̂ − EL(θ̂)

n

.

As described in Section III-D, one gets desirable order 1/n
√
(n)
behavior from RΘǫ ,L (P ) by using ǫ proportional to 1/ n.
For either of these two corollaries above to have order 1/n
bounds, the numerator of the second term should be stable in
n. In Corollary II.15, one sets α proportional to 1/ǫ2 and thus
needs Vθ̂ to have order 1/n. In many cases, such as ordinary
MLE with an exponential family, the covariance matrix of the
optimizer over Θ is indeed bounded by a matrix divided by n.
However, one still needs to handle the discrepancy in behavior
between the continuous and discretized estimator.
In a sense, Corollary II.15 shifts the problem to another
risk-related quantity, while the pseudo-penalties used in Sections II-B and II-C provide more direct ways of deriving exact
risk bounds of order 1/n.
E. Penalty as pseudo-penalty
Another simple corollary to Theorem II.1 uses L = αL.
iid

Corollary II.16. Assume X n ∼ P , and let θ̂ be the penalized
MLE over Θ indexing a countable iid model with penalty L.
Then
(n)

D. Quadratic form as pseudo-penalty

EDB (P, Pθ̂ ) ≤ RΘ,L (P )+
α+1
P
2 log θ∈Θ e− 2 L(θ) + αEL(θ̂)
.
n
Bayesian MAP (maximum a posteriori) is a common penalized likelihood procedure that has insufficient penalty for
the index of resolvability bound (2) to be valid. In that
case, Corollary II.4 applies (where L comprises the logs of
the reciprocals of prior masses), but the sum of exponential
terms may be infinite. An alternative approach comes from
Corollary II.16 by setting α = 1.

Other simple corollaries come from using a quadratic
pseudo-penalty L(θ) = (θ − Eθ̂)′ M (θ − Eθ̂) for some positive
definite matrix M . The expected pseudo-penalty is then

Corollary II.17. Assume X n ∼ P , and let θ̂ be the MAP
estimate over Θ indexing a countable iid model with prior
pmf q. Then

iid

EL(θ̂) = tr M Cθ̂,

(n)

EDB (P, Pθ̂ ) ≤ RΘ,log 1/q (P ) +

E log(1/q(θ̂))
.
n

8

For ǫ-discretizations, realize that q has to change as the
refinement increases; thus the second term in Corollary II.17
should be considered to have order strictly larger than 1/n in
that context.

III. A DAPTIVE M ODELING
S
Suppose Θ = k≥1 Θ(k) is a model class and each Θ(k) is
a model of countable cardinality. Let us index the distributions
in Θ by ν = (k, θ) with θ ∈ Θ(k) . Assume the penalty and
pseudo-penalty have the form L(ν) = L0 (k) + Lk (θ) and
L(ν) = L0 (k) + Lk (θ). Then Theorem II.1 can be useful
if the penalty plus pseudo-penalty on k is large enough to
counteract the within-model summations.
X

1
e− 2 [L(ν)+L(ν)]

ν∈Θ

=

X

k≥1



1
e− 2 [L0 (k)+L0 (k)]

X

θ∈Θ(k)



1
e− 2 [Lk (θ)+Lk (θ)]  .

One can use L0 (k) = 0 to avoid P
having to worry about
the behavior of k̂. Then bounds on θ∈Θ(k) e−[Lk (θ)+Lk (θ)]
should be known so that one can devise a penalty on k that
bounds the weighted sum of these summations. In particular,
if such bounds do not depend on any unknown quantities, then
1
√
P
one can set L0 (k) ≥ k 2 + 2 log θ∈Θ(k) e− 2 [Lk (θ)+Lk (θ)]
and have


X
X
1
1
e− 2 L0 (k)
log
e− 2 [Lk (θ)+Lk (θ)]  ≤ 0.
k≥1

θ∈Θ(k)

It remains to deal with ELk (θ̂), either by bounding it or by
absorbing it into the risk as in Corollary II.5.
An important feature of the resolvability bound method is
its generality; bounds can be derived that assume very little
about the data-generating distribution. In non-adaptive models,
however, the bound cannot become small if the data-generating
distribution is far from Gaussian. Our hope is to derive similar
exact risk bounds for penalized MLEs over flexible model
classes as well, such as Gaussian mixtures, so that D(P kΘ)
can be made small (or possibly zero) for large classes of
potential data-generating distributions.

ACKNOWLEDGMENT
We would like to acknowledge our advisor Andrew R.
Barron for teaching us about the MDL method for risk bounds.
We also thank him for his guidance in preparing this document,
especially for driving us toward the most important aspects and
consequences of our ideas.
We are also grateful to the anonymous reviewers whose
detailed feedback led to dramatic improvements to this paper.
Most importantly, they brought [13] to our attention, which
inspired us to write Section II-B.

A PPENDIX
A. Miscellaneous facts
The following handy facts are known, but we provide brief
proofs here nonetheless.
Lemma III.1. For any vectors u, v in a real inner product
space,
ku − vk2 ≤ 2kuk2 + 2kvk2 .
Proof. We apply the Cauchy-Schwarz inequality followed by
the arithmetic-geometric mean inequality.
ka − bk2 = kak2 + kbk2 − 2ha, bi

≤ kak2 + kbk2 + 2kakkbk

≤ kak2 + kbk2 + 2(kak2 /2 + kbk2 /2).
Lemma III.2. Let v ∈ Rd , and let M be a symmetric d × d
matrix. Then
λd (M ) ≤

v′ M v
≤ λ1 (M ).
kvk2

Proof. Any symmetric matrix has an orthonormal eigenvector
decomposition M = QΛQ′ .
v ′ M v = v ′ QΛQ′ v
X
λj (Q′ v)2j
=
j

= kvk2

X
j

2

v
.
λj Q′
kvk j

Realize that squared values in the summation are eigenvectorbasis coordinates of the unit vector in the direction of v.
As such, these squared coordinates must sum to 1. Thus
the summation is a weighted average of the eigenvalues. It
achieves its maximum λ1 when v is in the direction of the
first eigenvector, and it achieves its minimum λd when v is in
the direction of the last eigenvector.
Lemma III.3. Let a1 , . . . , aK ≥ 1/K. Then
X
X
log
ak ≤
log ak + K log K.
k

k

Proof. We apply the log-sum inequality and realize that it
produces coefficients bounded by 1.
#
"
!
P
X
X
Kak
1
k
Kak log P
log
ak = P
k Kak
k1
k
k
#
"
X
1
Kak
≤ P
Kak log
1
k Kak
k
X
≤
log Kak
=

k
X
k

log ak + K log K.

9

Lemma III.4. Let X ∼ P , where P is a probability distribution on Rd with marginal median vector mP . Then
√
kmP − EXk ≤ d EkX − EXk.
Proof. Superscripts indicate coordinates. We use subadditivity
of square root and the fact that the median minimizes expected
absolute deviation.
kEX − mP k ≤ kEX − mP k1
=

d
X
j=1

=

d
X
j=1

≤
≤

d
X
j=1

d
X
j=1

C. Infimum on a grid
In many cases we will need to ensure that the infimum
of a function on a grid of its domain approaches the overall
infimum as the grid becomes increasingly refined. Lemma III.6
will prove to be remarkably useful for such tasks.
Lemma III.6. Let Θǫ ⊆ Θ ⊆ Rd , and assume f : Θ → R is
twice continuously differentiable. If θ is in the convex hull of
Θǫ ∩ B(θ, δ), then

(j)

|EX (j) − mP |
(j)

|E(X (j) − mP )|
(j)

E|X (j) − mP |
E|X (j) − EX (j) |

√
≤ d EkX − EXk.

√
We used the fact that l1 and l2 satisfy kvk ≤ kvk1 ≤ dkvk.

inf f (θǫ ) ≤ f (θ) +

θǫ ∈Θǫ

For any random vector Y and any function f , we will call
Ef (Y ) − f (EY ) a Jensen difference.

λ1 (∇∇′ f (θ̃))+ .

sup
θ̃∈B(θ,δ)

Proof. We first bound the infimum over Θǫ by the infimum
over Θǫ ∩ B(θ, δ). Then that infimum is bounded by the
expectation using any distribution Q on those grid-points. We
have assumed that θ is some weighted average of nearby gridpoints (the ones at most δ distance away), and we can use that
same weighted averaging to define Q. Then the expectation of
the random selection is θ, and we apply Lemma III.5.
inf f (θǫ )

θǫ ∈Θǫ

≤

inf

θǫ ∈Θǫ ∩B(θ,δ)

f (θǫ )

≤ Eθǫ ∼Q f (θǫ )
≤ f (Eθǫ ∼Q θǫ )+
1
2 Eθǫ ∼Q kθǫ

B. Jensen differences

δ2
2

≤ f (θ) + 21 δ 2

− Eθǫ ∼Q θǫ k2
sup

sup

λ1 (∇∇′ f (θ̃))

θ̃∈B(θ,δ)

λ1 (∇∇′ f (θ̃)),

θ̃∈B(θ,δ)

′

Lemma III.5. Let Y be a random vector with convex support
S ⊆ Rd . If f : Rd → R is twice continuously differentiable,
then

assuming λ1 (∇∇ f (θ̃)) is non-negative. If the maximum
eigenvalue is negative, i.e. if f is strictly concave within the
ball, then the second order term is upper bounded by zero.

Ef (Y ) − f (EY )
≤ sup λ1 (∇∇′ f (y)).
VY /2
y∈S

Suppose Θǫ ⊆ Θ ⊆ Rd is an ǫ-discretization, as defined
in Section II. If Θ is convex, then every θ in the convex
√ hull
of Θǫ satisfies the conditions of Lemma III.6 with ǫ d as δ.
In particular, if every dimension of Θ is either R or a closed
half-line, then there is an obvious ǫ-discretization that makes
Lemma III.6 apply for every θ ∈ Θ. For less favorably shaped
Θ, one can consider adding more grid-points “on top of” an
ǫ-discretization.

inf λd (∇∇′ f (y)) ≤

y∈S

Proof. We start with a second-order Taylor expansion with
Lagrange remainder.
f (Y ) = f (EY ) + (Y − EY )′ ∇f (EY )+
1
2 (Y

− EY )′ ∇∇′ f (Ỹ )(Y − EY ),

for some Ỹ on the segment from Y to EY . By Lemma III.2,
the quadratic form has the bounds
kY − EY k2 λd (∇∇′ f (Ỹ )) ≤ (Y − EY )′ ∇∇′ f (Ỹ )(Y − EY )
≤ kY − EY k2 λ1 (∇∇′ f (Ỹ )).

The smallest and largest eigenvalues of the Hessian at Ỹ are
bounded by the infimum of smallest eigenvalue and supremum
of largest eigenvalue taken over the support of Y .
kY − EY k2 inf λd (∇∇′ f (y))
y∈S
′

≤ (Y − EY ) ∇∇′ f (Ỹ )(Y − EY )

≤ kY − EY k2 sup λ1 (∇∇′ f (y)).
y∈S

Substituting this second-order Taylor expansion into Ef (Y ) −
f (EY ) gives the desired result.

(n)

D. Behavior of RΘǫ ,L (P)
(n)

One way to bound RΘǫ ,L (P ) is to use an approach similar
to Section III-C. Suppose pθ (x) is twice continuously differentiable in θ. We define a type of Fisher “cross-information”
matrix


1
,
IP (θ̃) := EX∼P ∇∇′ log
pθ (X) θ=θ̃
where the Hessian is taken with respect to θ. Note that if pθ
represents an exponential family, then P does not play a role.
In that case, IP (θ̃) reduces to the ordinary Fisher information
matrix.
Let B(θ, δ) denote the closed Euclidean ball centered at θ
with radius δ, and let λj (·) denote the jth largest eigenvalue
of its matrix argument.

10

Theorem III.7. Let Θǫ ⊆ Θ ⊆ Rd . Assume that L : Θ → R
is twice continuously differentiable and that pθ (x) is twice
continuously differentiable in θ for every fixed x in its domain.
If θ ∈ Θ is in the convex hull of Θǫ ∩ B(θ, δ), then
(n)
RΘǫ ,L (P )

L(θ)
+
≤ D(P kPθ ) +
n
δ2
sup λ1 (IP (θ̃) + n1 ∇∇′ L(θ̃))+ .
2 θ̃∈B(θ,δ)

+ L(θ)
Proof. Define fX (θ) := log pp(X)
n , and let X ∼ P .
θ (X)
We use a second-order Taylor expansion at θ with Lagrange
remainder and reason similarly to the proofs of Lemmas III.5
and III.6.
(n)
RΘǫ ,L (P )

= inf EfX (θǫ )
θǫ ∈Θǫ

= inf E fX (θ) + (θǫ − θ)′ ∇fX (θ)+
θǫ ∈Θǫ

1
2 (θǫ

= inf

θǫ ∈Θǫ
1
2 (θǫ

′

!

′

− θ) [∇∇ fX (θ̃)](θǫ − θ)

if P is in the model, then we can let Pθ be P to get an exact
(n)
bound of order 1/n for RΘǫ ,L (P ).
E. Bounding summations over grid-points
Lemmas III.9 and III.10 provide bounds for summations of
Gaussian-shaped functions over ǫ-discretizations of Rd .
Lemma III.9. Let Θǫ be an ǫ-discretization of Rd . Then for
any c > 0 and v ∈ Θǫ ,

√ d
X
2
e−ckθ−vk ≤ 1 + ǫ√πc .
θ∈Θǫ

Proof. We can assume without loss of generality that v is the
zero vector and that Θǫ includes zero. First, consider the onedimensional problem. The “center” term equals 1 and the sum
of the other terms is bounded by a Gaussian integral.
X
X
2
2
2
e−cθ =
e−cǫ (θ/ǫ)
θ∈Θǫ

′

′

!

≤1+

(n)

RΘǫ ,L (P ) ≤ D(P kPθ ) +

=

with z := supθ̃∈B(θ,√ad) λ1 (IP (θ̃) + ∇∇′ L(θ̃))+ which does
not depend on n. Notice that this bound uses the n = 1 version
of the supremum term, because they cannot increase with n.
Notice also that, in general, z will increase with d. One could
set a2 = 1/d to cancel out all dimension dependence, but that
has an undesirable overall effect on the risk bound results put
forward in this paper.
One will most likely want to invoke these results with Pθ
being the rI-projection of P onto Θ if it exists. In particular,

X

2 2

z

dz

R

=
≤

X Y

...

(1)

θ1 ∈Θǫ

=

L(θ) + a2 dz/2
,
n

z

e−cǫ

θ∈Θǫ

θ∈Θǫ

L(θ)
+
n

ǫ d
λ1 (IP (θ̃) + n1 ∇∇′ L(θ̃))+ .
sup
2 θ̃∈B(θ,ǫ√d)
√
If one uses discretization ǫ = a/ n,

Z

2 2

The d-dimensional problem can be bounded in terms of d
(1)
(d)
instances of the one-dimensional problem. Let Θǫ , . . . , Θǫ
represent the underlying discretizations of R, so that Θǫ =
Q (j)
j Θǫ .
P 2
X
X
2
e−c j θj
e−ckθk =

Corollary III.8. Let Θ ⊆ Rd be a convex parameter space
having densities twice continuously differentiable in θ. Let
Θǫ ⊆ Θ be an ǫ-discretization. For any θ in the convex hull
of Θǫ ,

2

e−cǫ

√
π
=1+ √ .
ǫ c

− θ) [E∇∇ fX (θ̃)](θǫ − θ) ,

RΘǫ ,L (P ) ≤ D(P kPθ ) +

X
z∈Z

EfX (θ) + (θǫ − θ)′ E∇fX (θ)+

for some θ̃ between θ and θǫ .
The infimum is bounded by the expectation for any random
θǫ on the grid-points. In particular, use the distribution on
neighboring grid-points that makes θǫ have expectation θ. The
first-order term is elminated, while the second-order term is
bounded by half the expected squared length of the vector
θǫ − θ times the largest eigenvalue (if positive).
√
When Θǫ ⊆ Θ is an ǫ-discretization, we use ǫ d as δ.

(n)

θ∈Θǫ

=

Y X

(d)

θd ∈Θǫ

e

2

e−cθj

j

−cθj2

j θ ∈Θ(j)
j
ǫ
√ 
Y
1 + ǫ√πc
j

√ d
1 + ǫ√πc .

Similar reasoning provides a slightly larger bound if the
peak of the Gaussian function is not necessarily in the discretization.
Lemma III.10. Let Θǫ be an ǫ-discretization of Rd . Then for
any c > 0 and v ∈ Rd ,

√ d
X
2
e−ckθ−vk ≤ 1 + 2ǫ√πc .
θ∈Θǫ

Proof. Again, we begin with the one-dimensional problem.
The closest point to v contributes at most 1 to the sum. We
reduce to Lemma III.9 by comparison to Θ∗ǫ/2 , the (ǫ/2)grid that includes v. Each point on the original grid can be
translated “inward” to a neighboring point on the new (more

11

refined) grid. The sum over the new grid’s points will be larger
than the sum over the original grid’s points.
X
X
2
2
e−c(θ−v) ≤
e−c(θ−v)
θ∈Θǫ

θ∈Θ∗
ǫ/2

√

π
√ .
≤1+
(ǫ/2) c
As before, the d-dimensional problem reduces to the onedimensional problem.
Y X
X
2
2
e−ckθ−vk =
e−c(θj −vj )
θ∈Θǫ

j θ ∈Θ(j)
j
ǫ

Y
1+
≤
j


= 1+

√ 
2 √π
ǫ c

√ d
2 √π
ǫ c

.

There are important situations in which a function can
be bounded by one type of behavior near its peak and by
another type of behavior further away. When the tail behavior
has a spherically symmetric bound, Lemma III.11 can help
us convert the summation problem into a one-dimensional
integral.
Lemma III.11. Let f be a real-valued function of the form
f (θ) = g(kθ −θ∗ k) for some non-increasing and non-negative
function g. Let Θǫ be an ǫ-discretization of Θ ⊆ Rd . For any
radius R ≥ 3ǫ,
Z ∞
X
2π d/2
g(r)rd−1 dr,
f (θ) ≤
d Γ(d/2)
(ǫ/4)
R/4
∗
c
θ∈Θǫ ∩B(θ ,R)

if the integral is well-defined.
Proof. First, we bound the summation outside the ball with
diameter 2R by the summation outside the coordinate-axesaligned √hypercube inscribed by the ball, which has sides of
length 2R. Next, we introduce a new more refined grid
Θ∗ǫ/2 , which is the ǫ/2-discretization that includes the point
θ∗ . Consider the hyperplanes of Θǫ grid-points orthogonal to
the first coordinate axis. One can “translate inward” each of
these hyperplanes to a hyperplane in Θ∗ǫ/2 that is closer to θ∗ .
The argument can be repeated for each coordinate axis in turn.
Because√have assumed R ≥ 3ǫ, each translated point outside
of the 2R hypercube remains outside of the R hypercube.
Thus it suffices to sum over the points of Θ∗ǫ/2 outside of the
hypercube of side-length R. For the remainder of this proof,
we will assume without loss of generality that θ∗ is the zero
vector.
We will complete our proof by bounding the function’s
values at each point by its average value over a unique
hypercube closer to zero. Given the standard ǫ-discretization
of Rd , let j index shells radiating outward from the origin.
The jth shell comprises the grid-points on the boundary of
the centered hypercube of side-length 2jǫ, along with the
boundary hypercubes of volume ǫd demarcated by those gridpoints. (We will consider the origin point itself to be the
0th shell.) The total number of points in the first j shells is

(2j + 1)d , so the number of points in the (j + 1)st shell is
[2(j +1)+1]d −[2j +1]d. Similarly, the number of hypercubes
in the (j + 1)st shell is [2(j + 1)]d − [2j]d . Because t 7→ td is
convex and increasing on R+ ,
[2(j + 1) + 1]d − [2j + 1]d ≤ [2(j + 1) + 2]d − [2j + 2]d
= [2(j + 2)]d − [2(j + 1)]d .

In other words, the number of points in the (j + 1)st shell is
no greater than the number of hypercubes in the (j + 2)nd
shell.
Finally, we introduce yet another grid, Θ∗ǫ/4 . We know that
the number of points in the jth shell of Θ∗ǫ/2 is bounded by the
number of hypercubes in the (j + 1)st shell of Θ∗ǫ/4 . If we can
establish that these hypercubes are closer to the origin than are
the points in the jth shell of Θ∗ǫ/2 , then we can bound the sum
of the points’ function values by the sum of the hypercubes’
average function values.
The points comprising the jth shell of Θ∗ǫ/2 are inscribed by
a sphere of radius jǫ/2; that sphere is inscribed by a hypercube
√ . As j increases, the (j + 1)st shell of Θ∗
of radius jǫ/2
ǫ/4 will
2
be about half as far from the origin as the the jth shell of
Θ∗ǫ/2 . Because we have assumed R ≥ 3ǫ, the smallest j we
will need to worry about is j = 3. The third shell of Θ∗ǫ/2 has
distance 3ǫ/2 from the origin, while the 4th shell of Θ∗ǫ/4 has

√ , every hypercube in
distance ǫ from the origin. As ǫ < 3ǫ/2
2
the 4th shell of Θ∗ǫ/4 is entirely closer to the origin than any
point in the 3rd shell of Θ∗ǫ/2 . The comparison continues to
hold for all j ≥ 3.
The average value of f on a hypercube within Θ∗ǫ/4 is equal
to the integral over that region divided by the hypervolume
(ǫ/4)d . The inner-most hypercube that we need to consider is
a distance of R/4 from the origin. We let H0 (z) denote the
coordinate-axes-aligned hypercube centered at the origin with
side-length 2z; we will need to integrate over the complement
of this hypercube. Because g/(ǫ/4)d is non-negative, we can
bound this integral by the integral over a larger region, the
complement of a ball. We then use spherical symmetry to
reduce the problem to a one-dimensional integral.
Z
1
g(kθk)dθ
(ǫ/4)d H0 (R/4)c
Z
1
g(kθk)dθ
≤
(ǫ/4)d B(0,R/4)c
Z ∞
1
g(r)Sr dr
=
(ǫ/4)d R/4
Z ∞
2π d/2
g(r)rd−1 dr,
≤
(ǫ/4)d Γ(d/2) R/4

where Sr is the “surface area” of any ball in Rd with radius
r, which is 2π d/2 rd−1 /Γ(d/2).
A more manageable quantity for the right-hand-side of
Lemma III.11 can be derived.
Lemma III.12. For any ǫ, d > 0,
2π d/2
≤
(ǫ/4)d Γ(d/2)



20
√
ǫ d

d

.

12

Proof. [17, Theorem 1] provides a Stirling lower bound for
the gamma function:
√
2π(d/2)d/2
p
.
Γ(d/2) ≥
ed/2 d/2
√
We also
bound d by (2.9/2)d/2. The overall bound of
√ upper
(20/ǫ d)d comes from rounding numbers up to the nearest
integer.
Next, we apply Lemma III.12 to power decay functions.
Lemma III.13. Let Θǫ be an ǫ-discretization of Rd . For any
R ≥ 3ǫ and q > d,

d
X
1
20
(4/R)q−d
√
≤
.
∗
q
kθ − θ k
q−d
ǫ d
∗
c
θ∈Θǫ ∩B(θ ,R)

Proof. This is a straight-forward application of Lemmas III.11
and III.12.

d Z ∞ d−1
X
1
20
r
√
≤
dr
∗
q
q
kθ − θ k
ǫ d
R/4 r
θ∈Θǫ ∩B(θ ∗ ,R)c

d  d−q ∞
20
r
√
=
d
− q R/4
ǫ d

d
20
(R/4)d−q
√
=
.
q−d
ǫ d
In our applications, the decaying functions will often be
taken to the αn power for some α ∈ [0, 1]. For power decay
in that case, Lemma III.13 can be used to derive a bound that
is exponential
in dimension and is stable if ǫ is proportional
√
to 1/ n.
Lemma III.14. Assume n ≥ (d + 1)/αb, a > 0, and R ≥
4a1/b ∨ 3ǫ. Then

αn
X
a
kθ − θ∗ kb

θ∈Θǫ ∩B(θ ∗ ,R)c

≤

4R

ǫ

p
nαb log(R/4a1/b )

!d

.

Proof. Start with Lemma III.13, then apply the assumption
that bαn − d ≥ 1.

αn
X
a
kθ − θ∗ kb
∗
c
θ∈Θǫ ∩B(θ ,R)

= aαn

X

θ∈Θǫ ∩B(θ ∗ ,R)c



d

1
kθ − θ∗ kbαn
bαn−d

20
(4/R)
√
bαn − d
ǫ d
d  1/b bαn

4a
20R
√
≤
R
4ǫ d
 1/b bαn
d

4a
20R
d/2
√
n
.
=
R
4ǫ nd

≤ aαn

1/b

Assuming 4a1/b < R, the quantity nd/2 ( 4aR )bαn is maxid
mized at n = 2bα log(R/4a
1/b ) . Substituting this critical value
and rounding up gives us the desired bound.
Suppose the sample size is not large enough for
Lemma III.14 to be valid. If the summand is multiplied by
a Gaussian-shaped function, then it is still possible
√ to derive
a bound that is stable if ǫ is proportional to 1/ n, although
the dependence on dimension becomes worse. Lemmas III.15
and III.16 splits the problem into two additional ranges for n.
Lemma III.15. Assume n ≤ (d − 1)/αb, a, κ > 0, and R ≥
4a1/b ∨ 3ǫ. Then

αn
X
2
a
e−κkθk
kθ − θ∗ kb
θ∈Θǫ ∩B(θ ∗ ,R)c
!d
√
√
4 2πe d ∨ a2/b κ
κkθ ∗ k2
√
≤ 2e
.
ǫ nαbκ
Proof. By Lemma III.1, we can upper bound kθk2 in terms
of kθ − θ∗ k2 and kθ∗ k2 .
2

κ

e−κkθk ≤ e− 2 kθ−θ

∗ 2

k +κkθ ∗ k2

Using this, we apply Lemma III.11.

αn
X
a
−κkθk2
e
kθ − θ∗ kb
∗
c
θ∈Θǫ ∩B(θ ,R)

≤e

X

κkθ ∗ k2 αn

a

θ∈Θǫ ∩B(θ ∗ ,R)c

≤ eκkθ

∗ 2

k

aαn

2π d/2
(ǫ/4)d Γ(d/2)

e
Z

∗ 2
−κ
2 kθ−θ k

∞

e−κr

2



.

1
kθ − θ∗ kb

/2 d−bαn−1

r

αn

dr.

R/4

The integral from R/4 to ∞ can be upper bounded by the
integral from 0 to ∞. Then we change the variable to r2 and
compare the integrand to a Gamma distribution’s density.
Z ∞
2
e−κr /2 rd−bαn−1 dr
R/4
Z ∞
2
e−κr /2 rd−bαn−1 dr
≤
R/4
Z
1 ∞ −κr2 /2 2 (d−bαn−2)/2
=
e
(r )
(2rdr)
2 0
)
Γ( d−bαn
2
=
.
2(κ/2)(d−bαn)/2
Applying the Stirling upper and lower bounds for the
gamma function [17, Theorem 1], we arrive at the bound
αn

X
2
a
e−κkθk
kθ − θ∗ kb
∗
c
θ∈Θǫ ∩B(θ ,R)

Γ( d−bαn
)
2π d/2
2
d
(d−bαn)/2
(ǫ/4) Γ(d/2) 2(κ/2)
√ !d
 2/b bαn/2
4 2π
a κe
κkθ ∗ k2
d/2
√
≤e
×
n
d
ǫ nκ
q
d−bαn−1
e1/6(d−bαn) 1 − bαn
.
d
≤ eκkθ

∗ 2

k

aαn

13

We have assumed that d − bαn ≥ 1, so we can upper bound
the final two factors by e1/6 and 1. If d ≤ a2/b κe, then we
2/b
substitute d/bα for n to upper bound nd/2 ( a d κe )bαn/2 by
2/b
( a bακe )d/2 . Otherwise, the optimizer of the product of these
d
two factors is n = bα log(d/a
2/b κe) . Substituting this quantity
into the second factor and d/bα into the first, we bound the
d d/2
) . Using e1/6 ≤ 2 and
product of the two factors by ( bαe
d/e ≤ ed simplifies the bound.
d+1
Lemma III.16. Assume n ∈ ( d−1
αb , αb ), a, κ > 0, and R ≥
1/b
4a ∨ 3ǫ. Then

αn
X
2
a
e−κkθk
kθ − θ∗ kb
θ∈Θǫ ∩B(θ ∗ ,R)c


d 
√
∗ 2
20
22
√
κ
.
≤ eκkθ k
+
2
R3
ǫ nαb

Proof. Begin as in Lemma III.15. Our assumption about n
ensures that the exponent of r is negative in the integral. First
assume R/4 < 1.
Z ∞
2
e−κr /2 rd−bαn−1 dr
R/4

=
≤
≤

Z

1

R/4
Z 1

R/4
Z 1

e−κr

2

/2 d−bαn−1

r

rd−bαn−1 dr +
r−2 dr +

R/4
Z ∞

Z

Z

dr +

Z

∞

e−κr

2

/2 d−bαn−1

r

dr

1

∞

e−κr

2

/2

dr

1

∞

e−κr

2

/2

dr

0

1 √
r−2 dr + ( 2πκ)
2
R/4
√
3
≤ 22/R + 2 κ.
≤

R∞
2
If R/4 ≥ 1, then the integral is bounded by R/4 e−κr /2 dr
which remains less than our bound.
We use Lemma III.12 for the coefficient of the integral.
αn

X
a
−κkθk2
e
kθ − θ∗ kb
θ∈Θǫ ∩B(θ ∗ ,R)c

d 

√
∗ 2
20
22
≤ eκkθ k aαn √
+
2
κ
R3
ǫ d
d 


√
22
20
κkθ ∗ k2 d/2 αn
√
+2 κ .
=e
n a
R3
ǫ nd
If a < 1, the product nd/2 aαn is maximized at n =
−d/2a log α. Substituting that into the second factor gives
e−d/2 ; we bound the first factor using the fact that n ≤
(d+1)/bα ≤ 2d/bα. If a ≥ 1, substitute 2d/bα
factors.
√ in both
d[1∨a2/b ] d
√
) .
In either case, the product is bounded by (
bα
F. Hellinger affinity
Lemma III.17. Let P and Q be probability measures on
(X , A). For any event H ∈ A,
√
p
√
p
A(P, Q) ≤ P H QH + P Hc QHc .

Proof. Let p and q be densities of P and Q with respect to a
common dominating measure µ. We use the Cauchy-Schwarz
inequality.7
Z p
p(x)q(x)dµ(x)
A(P, Q) =
ZX p
Z p
=
p(x)q(x)dx +
p(x)q(x)dµ(x)
c
sZ H
sHZ
≤

p(x)dµ(x)

H

sZ

q(x)dµ(x)+

H

p(x)dµ(x)

Hc

sZ

q(x)dµ(x).

Hc

Lemma III.18. Let P and Q be probability distributions on
Rd . If they both have finite first moments, then
A(P, Q) ≤

2(EkX − EXk + EkY − EY k)
,
kEX − EY k

where X ∼ P and Y ∼ Q.
Proof. Let H denote the halfspace containing EX and demarcated by the perpendicular bisector of the path from EX to
EY .
The P -probability of the complement of H is bounded by
the probability of the complement of a ball within H. We use
Markov’s inequality to bound the probability that the deviation
kX − EXk is larger than kEX − EY k/2.
k c
)
P Hc ≤ P B(EX, kEX−EY
2
EkX − EXk
≤
.
kEX − EY k/2

The same logic also allows us to bound QH. Now invoke
Lemma III.17.
p
p
√
√
A(P, Q) ≤ P H QH + P Hc QHc
p
√
≤ QH + P Hc
EkY − EY k
EkX − EXk
≤
+
.
kEX − EY k/2 kEX − EY k/2

Lemma III.19. Let P and Q be probability distributions
on R. Suppse they have medians mP and mQ , that is,
P (−∞, mP ] = 1/2 and Q(−∞, mQ ] = 1/2. Then
A(P, Q) ≤ e−z

2

/2

,

where z is the Q probability of the interval defined by an open
endpoint at mP and a closed endpoint at mQ .
7 Andrew R. Barron pointed out to the authors that this Lemma is simply
an application of the Data Processing Inequality when the random variable is
processed by the indicator function of H, and it is useful in hypothesis testing
theory.

14

Proof. Assume without loss of generality that mP ≤ mQ .
Apply Lemma III.17 using the interval (−∞, mP ] for H.
√
p
√
p
A(P, Q) ≤ P H QH + P Hc QHc
p
1 p
= √ ( QH + QHc )
2
q
q
1
= √ ( 12 − z + 12 + z)
2
q
p
1
= √
1 + 1 − 4z 2
2
≤ 1 − z 2 /2
≤ e−z

2

/2

.

We recommend using mathematical software to algebraically
verify the second-to-last step.
Regarding Lemma III.19, note that A is symmetric in its
arguments, so letting z be the P probability of the interval
provides a valid bound as well.
Lemma III.20. Let P and Q be probability distributions
on Rd . Assume they have marginal median vectors mP =
(1)
(d)
(1)
(d)
(mP , . . . , mP ) and mQ = (mQ , . . . , mQ ), and assume
that Q has marginal densities q1 , . . . , qd with respect to
Lebesgue measure. Let R ≥ 0. Then for all Q with mQ ∈
B(mP , R),
2

A(P, Q) ≤ e−ckmQ −mP k ,
where
c :=

1
min
min
qj (x)2 .
2d j∈{1,...,d}
(j)
(j)
x∈[mQ −R,mQ +R]

Proof. Let P ∗ and Q∗ be the marginal distributions along the
coordinate with the largest absolute difference between mP
and mQ ; call the coordinates in this direction m∗P and m∗Q .
By Lemma III.19,
A(P ∗ , Q∗ ) ≤ e−z

2

/2

,

where z is the Q∗ probability of the interval from m∗P to
m∗Q . It is at least as large as the absolute difference between
the coordinates times the minimum value of the density q ∗
in the interval between them. The largest squared coordinate
difference is at least as large as the average squared coordinate
difference, that is
|m∗Q − m∗P |2 ≥ d1 kmQ − mP k2 .
The 1/2 factor in c comes from Lemma III.19.
The marginal distributions P ∗ and Q∗ can be produced by
“processing” draws from P and Q. Because Hellinger affinity is a monotonically decreasing transformation of squared
Hellinger divergence, the Data Processing Inequality implies
that A(P, Q) ≤ A(P ∗ , Q∗ ).
Lemma II.9

Proof. Let r denote the family’s carrier function and ψ denote
the log-partition function.
Z q
A(Pθ∗ , Pθ ) :=
p∗θ (x)pθ (x)dx
ZX
∗
′
∗
1
1
=
r(x)e 2 (θ +θ) φ(x)− 2 (ψ(θ )+ψ(θ)) dx
X
Z
∗
′
1
− 21 (ψ(θ ∗ )+ψ(θ))
r(x)e 2 (θ +θ) φ(x) dx
=e
=e

X
− 21 (ψ(θ ∗ )+ψ(θ)) ψ((θ ∗ +θ)/2)

=e

−[(ψ(θ ∗ )+ψ(θ))/2−ψ((θ ∗ +θ)/2)]

e

.

(8)

The exponent is a negative Jensen difference with a distribution that puts 1/2 mass on each of θ and θ∗ . Its expectation
is (θ∗ + θ)/2, and its variance is kθ − θ∗ k2 /4. Applying
Lemma III.5,

 ∗
ψ(θ∗ ) + ψ(θ)
θ +θ
−ψ
2
2
kθ − θ∗ k2
≥
inf λd (∇∇′ ψ(θ̃)).
8
θ̃∈Θ
It is a well-known fact about exponential families that
∇∇′ ψ(θ̃) is equal to the covariance matrix of the sufficient
statistic vector CX∼Pθ̃ φ(X).

G. Entropy of subprobability measures
We extend the notion of entropy to more general measures.
Let Q be a measure on a countable set X . Then we define its
entropy
X
1
H(Q) :=
q(x) log
,
q(x)
x∈X

where q(x) := Q({x}) is the density of Q with respect to
counting measure.8
Lemma III.21. Let Q be a finite measure on a countable set
e := 1 Q be the normalized version of Q. Then
X , and let Q
QX
Proof.

e + (QX ) log 1 .
H(Q) = (QX )H(Q)
QX

H(Q) :=

X

q(x) log

x∈X

1
q(x)

X q(x)
1/QX
log
QX
q(x)/QX
x∈X
X q(x)
1
log
+
= (QX )
QX
q(x)/QX
x∈X
X q(x)
1
(QX )
log
.
QX
QX
= (QX )

x∈X

8 One can likewise extend the notion of differential entropy h for Borel
measures on Rd by using Lebesgue measure rather than counting measure.
Lemmas III.21 and III.22 also hold for differential entropy when Q is a finite
Borel measure on X = Rd .

15

Lemma III.22. Let Q be a subprobability measure on a
e := 1 Q be the normalized version
countable set X , and let Q
QX
of Q. Then
e + 1/e.
H(Q) ≤ H(Q)

Proof. We apply Lemma III.21, noting that QX ≤ 1 and that
the function −z log z has maximum 1/e.
In particular, for any subprobability distribution Q, H(Q) ≤
log |X | + 1/e. A cleaner inequality holds if |X | ≥ 3.
Lemma III.23. Let Q be a subprobability measure on a
countable set X . If |X | ≥ 3, then
H(Q) ≤ log |X |.
Proof. Consider the expression in Lemma III.21, first bounde by log |X |. The function z 7→ z log |X | − z log z
ing H(Q)
(with domain [0, 1]) is maximized at elog |X |−1 ∧ 1. When
elog |X |−1 ≥ 1, then the function is bounded by z log |X | which
is no greater than log |X |. This case applies when |X | ≥ e.
Otherwise, the function’s maximum value is |X |/e. Thus, the
proposed inequality does not hold for sets of size 1 or 2.
Proof of Lemma II.14
Proof. Let q denote the pmf of θ̂.
X
1
q(θ) log
H(θ̂) =
.
q(θ)
θ∈Θǫ

We will bound two parts of the summation separately: outside
a ball centered at θ∗ and then inside that ball.
The function z 7→ z log(1/z)
√ increases as z goes from
0 to 1/e. If kθ − θ∗ k ≥ 1/ c, then the θ term of the
entropy summation can only be increased by substituting the
exponential probability bound
q(θ) log

∗ 2
1
≤ e−ckθ−θ k ckθ − θ∗ k2 .
q(θ)

Thus, outside the ball B := B(θ∗ , R ∨ c−1/2 ∨ 3ǫ), we can
bound the summation by an integral using Lemma III.11 then
compare the integral with a Gamma pdf.
X
1
q(θ) log
q(θ)
θ∈Θǫ ∩B c
X
∗ 2
≤
e−ckθ−θ k ckθ − θ∗ k2
θ∈Θǫ ∩B c
d/2

≤

2π
(ǫ/4)d Γ(d/2)

Z

∞

2

ecr cr2 rd−1 dr

[R∨c−1/2 ∨3ǫ]/4

Z ∞
2
cπ d/2
≤
ecr (r2 )d/2 2rdr
d
(ǫ/4) Γ(d/2) 0
cπ d/2
Γ(d/2 + 1)
=
(ǫ/4)d Γ(d/2) cd/2+1
 √ d
d 4 π
√
.
=
2 ǫ c
Next, we need to bound the terms coming from gridpoints inside B. Q restricted to this subset of grid-points
can be considered a subprobability measure. Because the ball

has radius at least 3ǫ, it contains enough grid-points for
Lemma III.23 to apply; thus the entropy of this subprobability
is bounded by the log-cardinality of the ball’s grid-points. The
number of grid-points in the hypercube circumscribing the ball
−1/2
is no more than (1 + 2[R∨c ǫ ∨3ǫ] )d .
d

X
1
2[R ∨ c−1/2 ∨ 3ǫ]
q(θ) log
.
≤ log 1 +
q(θ)
ǫ
θ∈Θǫ ∩B

R EFERENCES
[1] J. Rissanen, “Modeling by shortest data description,” Automatica,
vol. 14, no. 5, pp. 465–471, 1978.
[2] A. R. Barron and T. M. Cover, “Minimum complexity density estimation,” IEEE transactions on information theory, vol. 37, no. 4, pp. 1034–
1054, 1991.
[3] P. Grünwald and J. Langford, “Suboptimal behavior of bayes and mdl
in classification under misspecification,” Machine Learning, vol. 66, no.
2-3, pp. 119–149, 2007.
[4] A. Rényi, “On measures of entropy and information,” in Fourth Berkeley
Symposium on Mathematical Statistics and Probability, vol. 1, 1961, pp.
547–561.
[5] A. Bhattachayya, “On a measure of divergence between two statistical
population defined by their population distributions,” Bulletin Calcutta
Mathematical Society, vol. 35, pp. 99–109, 1943.
[6] T. Van Erven and P. Harremoës, “Rényi divergence and Kullback-Leibler
divergence,” Information Theory, IEEE Transactions on, vol. 60, no. 7,
pp. 3797–3820, 2014.
[7] A. R. Barron, C. Huang, J. Q. Li, and X. Luo, “The MDL Principle, Penalized Likelihoods, and Statistical Risk,” Feschrift for Jorma Rissanen,
2008.
[8] S. Chatterjee and A. Barron, “Information theoretic validity of penalized
likelihood,” in 2014 IEEE International Symposium on Information
Theory. IEEE, 2014, pp. 3027–3031.
[9] X. Luo, “Penalized likelihoods: fast algorithms and risk bounds,” Ph.D.
dissertation, Yale University, 2009.
[10] S. Chatterjee, “Adaptation in Estimation and Annealing,” Ph.D. dissertation, Yale University, 2014.
[11] J. Rissanen, “Stochastic complexity and modeling,” The Annals of
Statistics, pp. 1080–1100, 1986.
[12] A. R. Barron and N. Hengartner, “Information theory and superefficiency,” The Annals of Statistics, vol. 26, no. 5, pp. 1800–1825, 1998.
[13] T. Zhang, “From ǫ-entropy to KL-entropy: Analysis of minimum information complexity density estimation,” The Annals of Statistics, vol. 34,
no. 5, pp. 2180–2210, 2006.
[14] J. Q. Li, “Estimation of Mixture Models,” Ph.D. dissertation, Yale
University, 1999.
[15] W. D. Brinda, “Adaptive Estimation with Gaussian Radial Basis Mixtures,” Ph.D. dissertation, Yale University, 2018.
[16] P. D. Grünwald, The Minimum Description Length Principle. MIT
press, 2007.
[17] G. Jameson, “A simple proof of Stirling’s formula for the gamma
function,” The Mathematical Gazette, vol. 99, no. 544, p. 68, 2015.

