theoremTheorem corCorollary lemmaLemma propositionProposition
definitionDefinition assumptionAssumption exampleExample

# Asymptotically Minimax Regret by Bayes Mixtures

Jun’ichi Takeuchi, and Andrew R. Barron, J. Takeuchi is with Faculty of
Information Science and Electrical Engineering, Kyushu University, Fukuoka
819-0395, Japan. E-mail: (see
http://www.me.inf.kyushu-u.ac.jp/~tak/homepage.en.html).A. R. Barron is with
Department of Statistics and Data Science, Yale University, CT 06511, USA.This
research was supported in part by JSPS KAKENHI, Grant Numbers JP19300051,
JP24500018, JP18H03291, and JP23H05492.

###### Abstract

We study the problems of data compression, gambling and prediction of a
sequence $x^{n}=x_{1}x_{2}...x_{n}$ from an alphabet ${\cal X}$, in terms of
regret and expected regret (redundancy) with respect to various smooth
families of probability distributions. We evaluate the regret of Bayes mixture
distributions compared to maximum likelihood, under the condition that the
maximum likelihood estimate is in the interior of the parameter space. For
general exponential families (including the non-i.i.d. case) the
asymptotically mimimax value is achieved when variants of the prior of
Jeffreys are used. Interestingly, we also obtain a modification of Jeffreys
prior which has measure outside the given family of densities, to achieve
minimax regret with respect to non-exponential type families. This
modification enlarges the family using local exponential tilting (a fiber
bundle). Our conditions are confirmed for certain non-exponential families,
including curved families and mixture families (where either the mixture
components or their weights of combination are parameterized) as well as
contamination models. Furthermore for mixture families we show how to deal
with the full simplex of parameters. These results also provide
characterization of Rissanen’s stochastic complexity.

###### Index Terms:

universal coding, universal prediction, regret, redundancy, exponential
family, Bayes mixture, Jeffreys prior

##  I Introduction

We study the problem of data compression, gambling and prediction of a string
$x^{n}=x_{1},x_{2},...,x_{n}$ from a given alphabet ${\cal X}$, in terms of
regret and expected regret (redundancy) with respect to various families of
probability distributions. We evaluate the regret and expected regret of Bayes
mixture distributions and show that it asymptotically achieves the minimax
value when variants of Jeffreys prior are used. Our results contain
generalization of the results in [50, 51, 14]. Our results provide evaluation
of stochastic complexity defined by Rissanen [37].

This paper’s main concern is the regret of a coding or prediction strategy.
This regret is defined as the difference of the loss incurred and the loss of
an ideal coding or prediction strategy for each sequence. A coding scheme for
strings of length $n$ is equivalent to a probability mass function $q(x^{n})$
on ${\cal X}^{n}$. We can also use $q$ for prediction and gambling, that is,
its conditionals $q(x_{i+1}|x^{i})$ provide a distribution for the coding or
prediction of the next symbol given the past. The minimax regret with respect
to a target family of probability mass functions
$S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ and a given set of parameters
$K\subset\Theta$ is defined as

$\min_{q}\max_{x^{n}\in{\cal
K}}\max_{\theta\in\Theta}\Bigl{(}\log\frac{1}{q(x^{n})}-\log\frac{1}{p(x^{n}|\theta)}\Bigr{)},$

where ${\cal K}$ denotes the set $\\{x^{n}:\hat{\theta}(x^{n})\in K\\}$, which
is the set of strings for which the maximum likelihood estimate $\hat{\theta}$
is in $K$. Typically $K$ is either all of $\Theta$ or a subset that excludes
points near the boundary. The maximum is taken for all strings $x^{n}$ in
$\cal K$. The regret $\log(1/q(x^{n}))-\log(1/p(x^{n}|\hat{\theta}))$ in the
data compression context is also called the (pointwise) redundancy: the
difference between the code length based on $q$ and the minimum of the
codelengths $\log(1/p(x^{n}|\theta))$ achieved by distributions in the family.
Also, $\log(1/q(x^{n}))-\log(1/p(x^{n}|\theta))$ is the sum of the incremental
regrets of prediction
$\log(1/q(x_{i+1}|x^{i}))-\log(1/p(x_{i+1}|x^{i},\theta))$, with what is
sometimes called the log-loss. This regret is also called the pointwise
regret, to emphasize the distinction from the expected regret also discussed
below.

The heart of our analysis is the consideration of Bayes mixtures and the use
of the Laplace method to approximate them. A Bayes mixture takes the form
$q(x^{n})=\int p(x^{n}|\theta)w(\theta)d\theta$, also called the Bayes factor
or the marginal density of $x^{n}$ obtained by integrating out $\theta$ from
the joint distribution.

Though certain coding and prediction settings have a discrete alphabet ${\cal
X}$, we are interested in minimax regret problems also for continuous spaces
${\cal X}$. Then the $p(x^{n}|\theta)$ as well as $q(x^{n})$ are understood to
be probability density functions with respect to a given reference measure.

For the case that $S$ is the class of all discrete memoryless sources, it was
proved [51] that the minimax regret asymptotically equals
$(d/2)\log(n/2\pi)+\log C_{J}(K)+o(1)$, where $d$ equals the size of alphabet
minus $1$ and $C_{J}(K)$ is the integral of the square root of the determinant
of the Fisher information matrix over $K$. An important point in the above is
that $K$ is taken there to be $\Theta$ itself, i.e. we do not have to have any
restriction for the sequence $x^{n}$. To obtain this asymptotically minimax
regret, they use sequences of Bayes mixtures with certain prior distributions
that weakly converge to the Jeffreys prior. The reason why one needs such
variants of the Jeffreys prior is as follows: If we use the Jeffreys prior,
the regret is asymptotically higher than the minimax value, for $x^{n}$ such
that $\hat{\theta}$ is near the boundary of $\Theta$. Priors which have higher
density near the boundaries than the Jeffreys prior give more prior attention
to these boundary regions and thereby pull the regret down to not more than
the asymptotically minimax level.

In this paper, we provide such regret results for more general parametric
families of densities. For exponential families of arbitrary dimension, the
Jeffreys mixture is shown to be asymptotically minimax, if $K$ is a compact
subset included in the interior of $\Theta$. A boundary modification is shown
to produce a variant of Jeffreys mixture asymptotically minimax for $K=\Theta$
in the one-dimensional exponential family case. For general smooth families
that are not of exponential type, we find that any Bayes mixture that uses a
prior restricted to the family is not asymptotically minimax, but a slight
modification (enlargement) of the family allows for priors for which the
regret of Bayes mixtures does achieve the asymptotically minimax value.

The related problem of minimax expected regret (redundancy), which is defined
as

$\min_{q}\max_{\theta\in
K}E_{\theta}\Bigl{(}\log\frac{1}{q(x^{n})}-\log\frac{1}{p(x^{n}|\theta)}\Bigr{)}$

was studied by Clarke and Barron [14]. They considered fairly general classes
of i.i.d. processes and showed that the minimax expected regret asymptotically
equals $(d/2)\log(n/2\pi e)+\log C_{J}(K)+o(1)$, when $K$ is a compact subset
of the interior of $\Theta$. Moreover the expected regret is related to the
value of

$\min_{q}\max_{\theta\in
K}E_{\theta}\Bigl{(}\log\frac{1}{q(x^{n})}-\log\frac{1}{p(x^{n}|\hat{\theta})}\Bigr{)}$

using the target code length with $1/p(x^{n}|\hat{\theta})$ instead of
$1/p(x^{n}|\theta)$. It has a corresponding minimax value
$(d/2)\log(n/2\pi)+\log C_{J}(K)+o(1)$. Preceding work [51], [50] evaluated
the minimax expected regret for the class of discrete memoryless sources and
showed that sequences of slightly modified Jeffreys mixtures achieve the
minimax value asymptotically for the whole probability simplex $\Theta$. As we
shall see, the answer for the minimax regret and the minimax expected regret
are similar.

To obtain the minimax regret results, we employ the Laplace integration
method, which was used by [13, 14] to evaluate the expected regret of the
Bayes procedures. Especially in [14], they succeeded to uniformly evaluate the
expected regret by the Laplace integration for compact subsets $K$ of
$\Theta^{\circ}$, the interior of $\Theta$. To handle all of $\Theta$, careful
modification of the Laplace method is required to handle behaviour near the
boundary.

Since the Jeffreys mixture achieves asymptotically the minimax expected
regret, one might expect that it also achieves asymptotically the minimax
pointwise regret. However, it does not in general. Namely, we can see that for
processes which are not exponential type, the worst case regret of the
Jeffreys mixture is asymptotically higher than the minimax value, even if
strings are restricted such that the maximum likelihood estimate (MLE) is in
the interior of the parameter space.

The reason follows from examination of the Laplace approximation to the Bayes
mixture density. This leads to an approximation to the regret of the Jeffreys
mixture which converges to the minimax value, if and only if the difference
between the determinant of the empirical Fisher information matrix and that of
the Fisher information matrix at the MLE converges to $0$. For exponential
families, the empirical and expected Fisher informations are the same, hence
the Jeffreys mixture is asymptotically minimax. The situation is different for
families which are not exponential type, for then there exist sequence $x^{n}$
for which the determinants of these matrices are asymptotically different.

Even though the Jeffreys mixture is not asymptotically minimax, we can obtain
an asymptotic minimax regret, by a modified Jeffreys mixture obtained by
adding a small contribution from a mixture of an enlarged set of densities,
whose dimension is higher than the original set. The added components deal
with the strings for which the empirical Fisher information differs from the
Fisher information. When the original set is a curved exponential family
embedded in an exponential family, we have the option to use that family as
the enlarged model. Furthermore, this method can be applied to non-i.i.d.
families under certain assumptions.

Our result about minimax regret provides an alternative way to evaluate, more
generally, the stochastic complexity in Rissanen [37], where he used the
normalized maximum likelihood. Our results show that the codelength of the
minimax strategy retains asymptotically the mixture codelength interpretation
of earlier incarnations of his criterion. The work [6] shows that in some
cases the exact minimax strategy has a signed mixture interpretation without
resorting to asymptotics.

The codelength of a code based on a mixture
$q(x^{n})=\int_{K}p(x^{n}|\theta)w(\theta)d\theta$ has Laplace approximation
(for $\hat{\theta}$ away from the boundary of $K$) given by

$\log\frac{1}{q(x^{n})}\sim\log\frac{1}{p(x^{n}|\hat{\theta})}+\frac{d}{2}\log\frac{n}{2\pi}+\log\frac{|\hat{J}(\hat{\theta},x^{n})|^{1/2}}{w(\hat{\theta})\,\;},$

where $\hat{J}(\hat{\theta},x^{n})$ is the empirical Fisher information,
defined as $(1/n)$ times the second derivative matrix of the minus log-
likelihood, evaluated at the MLE $\hat{\theta}$. With Jeffreys prior in which
$w(\theta)$ is proportional to $|J(\theta)|^{1/2}$, the Laplace approximation
for $\log(1/q(x^{n}))$ is

$\log\frac{1}{p(x^{n}|\hat{\theta})}+\frac{d}{2}\log\frac{n}{2\pi}+\log
C_{J}(K)+\frac{1}{2}\log\frac{{|\hat{J}(\hat{\theta})|}}{{|J(\hat{\theta})|}},$

where

$C_{J}(K)=\int_{K}{|J(\theta)|^{1/2}}d\theta.$

Accordingly, the regret of the code based on Jeffreys prior takes the
approximation form

$\frac{d}{2}\log\frac{n}{2\pi}+\log
C_{J}(K)+\frac{1}{2}\log\frac{{|\hat{J}(\hat{\theta})|}}{{|J(\hat{\theta})|}}.$

Our modification of $q(x^{n})$ by enlargement of the family with an associated
modification to the prior shows that

$\displaystyle\frac{d}{2}\log\frac{n}{2\pi}+\log C_{J}(K)$ (1)

remains the asymptotically minimax regret even though in the non-exponential
family cases there are sequences $x^{n}$ for which
$\log\bigl{(}{{|\hat{J}(\hat{\theta},x^{n})|}}/{{|J(\hat{\theta})|}}\bigr{)}$
does not converge to $0$.

This presents a challenge for the formulation and analysis of our asymptotic
minimax procedures with the maximum of the regret taken over all $x^{n}$. In
contrast the minimax expected regret is easier to achieve because the
expectation washes out the effect of $\hat{J}$ different from $J$. In either
formulation, with $\log(1/p(x^{n}|\hat{\theta}))$ as the target, the minimax
value takes the asymptotic form (1).

In Section II, we formally introduce the notion of minimax and maximin regret.
Section III gives keys to the bounds. In Section IV, we give the lower bound
on the maximin regret for general smooth families in the i.i.d. setting
(Theorems 1 and 2) and for families of non-i.i.d. densities (Theorems 3 and
4). These hold for any subset $K$ of $\Theta$ with finite Jeffreys integral.
Likewise, in Section V, we give corresponding upper bound on the minimax
regret for general smooth families with a compact subset $K$ in the interior
of $\Theta$ (Theorem 5), which incorporate the discussed innovations. In
Section VI, we provide various types of families as concrete examples,
including certain curved exponential families and certain mixture families
that are not representable as exponential families.

##  II Preliminaries

Let $({\cal X},{\cal B},\nu)$ be a measurable space with a reference measure
$\nu$, assumed to be sigma finite (such as counting measure or Lebesgue
measure). Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ denote a parametric
family of probability densities over ${\cal X}$ with respect to $\nu$. Assume
that $\Theta\subseteq\Re^{d}$. We let $p(x^{n}|\theta)$ denote
$\prod_{i=1}^{n}p(x_{i}|\theta)$. Also, we let $\nu(dx^{n})$ denote
$\prod_{i=1}^{n}\nu(dx_{i})$. Here, we are treating models for independently
identically distributed (i.i.d.) random variables. (Section IV treats certain
non i.i.d. cases.) We let $P_{\theta}$ denote the distribution function with
density $p(\cdot|\theta)$ and $E_{\theta}$ denote expectation with respect to
$P_{\theta}$.

Define the Fisher information matrix by

$J_{ij}(\theta)=E_{\theta}\Bigl{(}-\frac{\partial^{2}\log
p(x|\theta)}{\partial\theta^{i}\partial\theta^{j}}\Bigr{)}.$

(We let $\log$ denote the natural logarithm.) We assume that $J(\theta)$
exists and is strictly positive definite in the interior of $\Theta$. Let $K$
denote a subset of $\Theta$. We let
$C_{J}(K)\stackrel{{\scriptstyle\mbox{\scriptsize\rm
def}}}{{=}}\int_{K}|J(\theta)|^{1/2}d\theta$, which we call the Jeffreys
integral on $K$. Our interest is in cases in which $C_{J}(K)$ is finite. The
Jeffreys prior over $K$ is a prior distribution with density function

$w_{K}(\theta)=\frac{{|J(\theta)|^{1/2}}}{C_{J}(K)}1_{K}(\theta).$

Define the Jeffreys mixture for $K$ as

$m_{K}(x^{n})=\int_{K}p(x^{n}|\theta)w_{K}(\theta)d\theta.$

We also introduce the empirical Fisher information as a function of $x^{n}$:

$\hat{J}_{ij}(\theta)=\hat{J}_{ij,n}(\theta)=\hat{J}_{ij}(\theta,x^{n})=\frac{-1\>\>\;}{n}\frac{\partial^{2}\log
p(x^{n}|\theta)}{\partial\theta^{i}\partial\theta^{j}}.$

Note that $J_{ij}(\theta)=E_{\theta}[\hat{J}_{i,j}(\theta)]$. Moreover, in the
present i.i.d. setting, $\hat{J}_{ij,n}(\theta)$ is near $J_{ij}(\theta)$ with
high probability for large $n$, by the law of large numbers, when
$J_{ij}(\theta)$ is finite, if we were to have the $X_{i}$ distributed
according to $P_{\theta}$. We work with the arbitrary sequence perspective, so
the empirical $\hat{J}_{ij,n}(\theta)$ need not be close to $J_{ij}(\theta)$.
Nevertheless we will find a role for the expected value formulation of Fisher
information in characterization of the minimax regret among arbitrary
sequences.

Let $\hat{\theta}(x^{n})$ be the maximum likelihood estimate (MLE), which is

$\arg\max_{\theta\in\Theta}p(x^{n}|\theta).$

More strictly, we define $\hat{\theta}$ to be an element of the set
$\\{\theta:p(x^{n}|\theta)=\max_{\theta}p(x^{n}|\theta)\\}$. For the case
where this set has more than one element, we presume there is an arbitrarily
specified rule to choose one element.

For example, in the case of Bernoulli sources, we have
$\hat{\theta}=\sum_{i=1}^{n}x_{i}/n$, where $\theta$ is the parameter denoting
the probability that ‘$1$’ occurs. The function $\hat{\theta}$ mapping each
$x^{n}$ in ${\cal X}^{n}$ to the value $\hat{\theta}(x^{n})$ is the maximum
likelihood estimator. In the above case of Bernoulli sources,
$\hat{\theta}(x^{n})$ is defined on the whole ${\cal X}^{n}$. However, in
certain cases, there may exist strings for which $\max p(x^{n}|\theta)$ does
not exists. In such cases, we restrict the domain of $\hat{\theta}$ to the set
of $x^{n}$’s such that the MLE does exist.

We introduce the notion of minimax regret and maximin regret. Let ${\cal
K}_{n}$ denote a fixed subset of ${\cal X}^{n}$. Let ${\cal P}_{n}$ denote the
set which consists of all probability densities over ${\cal X}^{n}$ with
respect to the fixed sigma-finite reference measure.

For sample size $n$ and set ${\cal K}_{n}$, define the maximum regret of a $q$
in ${\cal P}_{n}$ (denoted by $\bar{r}_{n}(q,{\cal K}_{n})$) as

$\bar{r}_{n}(q,{\cal K}_{n})=\sup_{x^{n}\in{\cal
K}_{n}}\sup_{\theta\in\Theta}\log\frac{p(x^{n}|\theta)}{q(x^{n})}=\sup_{x^{n}\in{\cal
K}_{n}}\log\frac{p(x^{n}|\hat{\theta})}{q(x^{n})}$

and the _minimax_ regret as

$\bar{r}_{n}({\cal K}_{n})=\inf_{q\in{\cal P}_{n}}\bar{r}_{n}(q,{\cal
K}_{n}).$

For each $q\in{\cal P}_{n}$, the minimum average regret for sample size $n$
denoted

$\mbox{\@text@baccent{$\; r$}}_{n}(q)=\inf_{\tilde{q}\in{\cal P}_{n}}\int
q(x^{n})\Bigl{(}\log\frac{p(x^{n}|\hat{\theta})}{\tilde{q}(x^{n})}\Bigr{)}\nu(dx^{n})$

is achieved by $\tilde{q}=q$. We define the _maximin_ regret for the set
${\cal K}_{n}$ as

$\mbox{\@text@baccent{$\; r$}}_{n}({\cal K}_{n})=\sup_{q\in{\cal P}_{{\cal
K}_{n}}}\mbox{\@text@baccent{$\; r$}}_{n}(q),$

where ${\cal P}_{{\cal K}_{n}}$ is the set of all probability densities
supported on ${\cal K}_{n}$.

By the above definitions, $\bar{r}_{n}({\cal
K}_{n})\geq\mbox{\@text@baccent{$\; r$}}_{n}({\cal K}_{n})$ holds. (In fact,
$\bar{r}_{n}({\cal K}_{n})=\mbox{\@text@baccent{$\; r$}}_{n}({\cal K}_{n})$
holds [39, 51].) In this paper, we usually consider the minimax regret problem
for the following form of the set ${\cal K}_{n}$: given $K\subseteq\Theta$,

${\cal K}_{n}={\cal X}^{n}(K)=\\{x^{n}:\hat{\theta}\in K\\}.$

Next, we remind the reader of the notions of the minimax and maximin value of
expected regret (redundancy). Let a sample size $n$ and a parameter set $K$ be
given. For each $q\in{\cal P}_{n}$, we define the maximum expected regret
(denoted by $\bar{R}_{n}(q,K)$) as

$\bar{R}_{n}(q,K)=\sup_{\theta\in
K}E_{\theta}\Bigl{(}\log\frac{p(x^{n}|\theta)}{q(x^{n})}\Bigr{)}$

and the minimax expected regret as

$\bar{R}_{n}(K)=\inf_{q\in{\cal P}_{n}}\bar{R}_{n}(q,K),$

where $E_{\theta}$ denotes the expectation with respect to $p(x^{n}|\theta)$.
Let $\Omega(K)$ denote the set which consists of all prior probability
measures over $K$. For each prior $w\in\Omega(\Theta)$, the minimum Bayes
expected regret for sample size $n$ denoted

$\mbox{\@text@baccent{$R$}}_{n}(w)=\inf_{q\in{\cal P}_{n}}\int
E_{\theta}\Bigl{(}\log\frac{p(x^{n}|\theta)}{q(x^{n})}\Bigr{)}w(d\theta)$

is achieved by $q(x^{n})=m(x^{n})=\int p(x^{n}|\theta)w(d\theta)$. We define
the maximin expected regret for the parameter set $K$ as

$\mbox{\@text@baccent{$R$}}_{n}(K)=\sup_{w\in\Omega(K)}\mbox{\@text@baccent{$R$}}_{n}(w).$

We also have $\bar{R}_{n}(K)\geq\mbox{\@text@baccent{$R$}}_{n}(K)$. (In fact,
$\bar{R}_{n}(K)=\mbox{\@text@baccent{$R$}}_{n}(K)$ holds [17, 25].)

Finally, we note some terminology. We let $1_{A}$ denote the characteristic
function of a set $A$. We write $o(1)$ for an expression upper bounded by a
positive quantity tending to zero. In the proofs, we denote certain positive
constants by $C_{i}$ ($i=1,2,...$), where $i$ is ‘local’ in each proof.

##  III The Key to Handling Worst Case Regret

The notion that the worst case regret is the same asymptotically as an average
case regret should come as a surprise. Indeed, if one inspects the worst case
regret of an average case optimal procedure, e.g. with the Jeffreys mixture,
there will be strings for which the worst case performance of the procedure is
quantitatively different in its asymptotics than the average case performance.

To succeed in bringing the worst case regret value down to the average case
optimum requires a sequence of somewhat new specialized procedures. These
specializations are modifications of Jeffreys mixtures that address two
difficulties. One is that Laplace approximation is no longer valid for strings
for which the MLE $\hat{\theta}$ is at or very close to the boundary of the
parameter space. That is a familiar issue, addressed by modification of the
prior to give small additional prior weights to parameter values near the
boundary. Such boundary modification was needed in the special case of [50,
51]. Here we provide an improved near-boundary fix by using a multiplicative
correction factor for the prior. This improved correction factor comes from
the probability of $K$ assigned by a normal distributions that arises in the
Laplace approximation. This just-right probability correction factor from
Laplace approximation is near $1$ away from the boundary (by an amount of
larger order than $1/\sqrt{n})$, and typically approaches $1/2$ as the
parameter approaches the boundary (at a rate faster than order $1/\sqrt{n}$).

The more fundamental difficulty is the discrepancy between the worst case and
average values of the regret of mixture procedures that can exist even when
$\hat{\theta}$ is in the interior, which, as exhibited above, is due to
individual strings having
$(1/2)\log\bigl{(}|\hat{J}(\hat{\theta})|/|J(\hat{\theta})|\bigr{)}$ not near
zero when not in an exponential family. We present and analyze ideas to
overcome that difficulty which were initiated by the authors as discussed in
[40, 7, 5].

For general smooth families we form a direct enlargement by a exponential
tilting using linear combinations of the entries of the differences
$\hat{J}(\theta)-J(\theta)$. It is formed as

$\displaystyle
p(x^{n}|\theta,\beta)=p(x^{n}|\theta)e^{n\beta\cdot(\hat{J}(\theta)-J(\theta))-\psi_{n}(\theta,\beta)}$
(2)

Where $\beta\cdot M$ for matrices $\beta$ and $M$ denotes the Frobenius inner
product (the sum of products across all $d^{2}$ entries).

The idea for this enlargement in addressing minimax regret originate in
preliminary form in [40, 7] as informally discussed in [5, 43]. Here
$\psi_{n}(\theta,\beta)$ is the log of the required normalization factor, so
that $p(x^{n}|\theta,\beta)$ sums (integrates with respect to $\nu^{n}$) to
the value $1$ for every $\theta\in K$ and every $\beta$ in a neighborhood
around $0$. The prior assigns most of its weight to a Jeffreys prior on
$\theta$ (with $\beta$ set to $0$) and small weight on a smooth prior on
$(\theta,\beta)$ with $\beta$ in a neighborhood of $0$. Now demonstration of
the success of this modification is based on demonstration of increased
likelihood beyond that which is available at $\beta=0$ when
$\hat{J}(\hat{\theta})-J(\hat{\theta})$ is not equal to $0$. Indeed, as we
show in Section V, the contribution to the mixture from $\beta$ with
$\beta\cdot(\hat{J}(\hat{\theta})-J(\hat{\theta}))$ positive is sufficient to
increase the value of $m(x^{n})$ to again overcome the discrepancy in
$(1/2)\log(|\hat{J}(\hat{\theta})|/|J(\hat{\theta})|)$ from Laplace
approximation.

We have a somewhat different modification that can be used in the case of
curved exponential families embedded in a full exponential family as developed
in examples in Section VI. For both of the modifications we study, there is,
in the analysis, the consideration of values of $\beta$ in a neighborhood of a
small multiple of $\hat{J}(\hat{\theta})-J(\hat{\theta})$ which are sufficient
to accomplish our objectives. We see the similarity of effect. In both cases
there is opportunity to create a likelihood increase from a suitable linear
combination of these statistics.

These ideas emanate from an underlying principle. Of importance in smooth
statistical families is the parametric enlargement

$\displaystyle p(x^{n}|\theta,\beta)=p(x^{n}|\theta)e^{\beta\cdot\nabla\log
p(x^{n}|\theta)-\psi_{n}(\theta,\beta)},$ (3)

where $\nabla\log p(x^{n}|\theta)$ is the score function at $\theta$ and
$\psi_{n}(\theta,\beta)$ is the log normalizing constant near
$(1/2)\beta^{t}J(\theta)\beta$ for small $\beta$. Traditionally such a family
arises in local asymptotic expansion of likelihood ratios, evaluated at a
perturbation $\theta+\beta$ of a given $\theta$, as used in demonstration of
local asymptotic normality [30, 33, 36]. In Amari’s information geometry it is
a local exponential tangent to the family at $\theta$. Again, in this setting,
a prior can be put jointly on $\theta$ and $\beta$, where most of the prior
weight is concentrated at $\beta=0$ with Jeffreys prior on $\theta$.

The use of the first derivative of $\log p(x^{n}|\theta)$ in the exponent
would seem to produce a different sort of enlargement than occurs with
equation (2) which uses the second derivative. Nevertheless, improvement in
$m(x^{n})$ still arises by suitable characterization of the increased
likelihood available with the enlarged family. For each small $\beta$ the
maximum likelihood value $\hat{\theta}_{\beta}$ achieving
$\max_{\theta}p(x^{n}|\theta,\beta)$ in (3) satisfies the approximate
relationship

$\displaystyle
p(x^{n}|\hat{\theta}_{\beta},\beta)=p(x^{n}|\hat{\theta}_{0})e^{(n/2)\beta^{T}(\hat{J}(\hat{\theta}_{0})-J(\hat{\theta}_{0}))\beta}$
(4)

to within term of order $n|\beta|^{3}$ in the exponent. This is the desired
effect, where $\hat{\theta}_{0}=\hat{\theta}$ here is the MLE in the original
family and $\hat{\theta}_{\beta}$ is the MLE in the tilted family (3). The
likelihood is larger at some non-zero $\beta$ than at $\beta=0$ provided
$\beta^{T}(\hat{J}(\hat{\theta})-J(\hat{\theta}))\beta$ can be strongly
positive, or equivalently provided
$\hat{J}(\hat{\theta})(J(\hat{\theta}))^{-1}$ has some eigenvalue greater than
$1$. Consequently, when $(1/2)\log(|\hat{J}(\hat{\theta})|/|J(\hat{\theta})|)$
is positive (which is the only case of concern) optimization in this tangent
family is sufficient to realize similar likelihood gain to optimization in the
family tilted by second derivatives of log-likelihood.

This provides an enlargement of parametric families by exponential tilting
using score functions suitable to endow the family with the property we need,
comparable to the curved exponential family case. Analogous conditions are in
Amari and Nagaoka [3], who use tilting by first and second derivatives. A
distinction thought is that he is considering local families with a fixed true
$\theta$ whereas we are considering the joint family parametrized by $\theta$
and $\beta$.

For general families in the present paper we use the enlargement of the form
(2) in our analysis, now further motivated by the connections to locally
asymptotically normal familiers we have discussed here.

##  IV Lower Bounds

Our targets are fairly general smooth parametric families under some
conditions and some classes of non-i.i.d. stochastic processes. First we
describe our results about lower bounds.

###  IV-A Lower Bounds for General i.i.d. Families

Let $S\stackrel{{\scriptstyle\mbox{\scriptsize\rm
def}}}{{=}}\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a family of probability
densities with respect to the reference measure $\nu$, with a $d$-dimensional
parameter $\theta$. Assume that $\Theta\subseteq\Re^{d}$ and let
$\Theta^{\circ}$ denote its interior. We use $K$ to denote subsets of
$\Theta$, with particular interest in sets for which $C_{J}(K)$ is finite and
for which the boundary measure of $K$ is zero. We handle both the case of
bounded sets $K$ (Lemma 1) and more general cases of possibly unbounded sets
$K$ (Theorem 1).

For each $\delta>0$, define Mahalanobis neighborhoods of $\theta\in\Theta$ as

$B_{\delta}(\theta)=\\{\theta^{\prime}\in\Theta:(\theta^{\prime}-\theta)^{t}J_{\theta}(\theta^{\prime}-\theta)\leq\delta^{2}\\}.$

We employ the assumptions described below. The density $p(x|\theta)$ is twice
continuously differentiable for $\theta\in\Theta^{\circ}$ for every $x$.
Moreover, for every $\theta\in\Theta^{\circ}$ there is a $r=r(\theta)$ such
that, for every $i$, $j$,

$\displaystyle E_{\theta}\Biggl{[}\sup_{\theta^{\prime}\in
B_{r}(\theta)}|\hat{J}_{ij,1}(\theta^{\prime})|\Biggr{]}$ (5)

is finite. The Fisher information $J(\theta)$ is continuous and positive
definite in $\Theta^{\circ}$.

Consequences of continuity and positive definiteness are that the following
two quantities tends to $0$ as $\delta\rightarrow 0$ for any $\theta$ in
$\Theta^{\circ}$

$\displaystyle\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\frac{|J(\theta^{\prime})|^{1/2}}{|J(\theta)|^{1/2}}-1$ (6)

and

$\displaystyle\sup_{\theta^{\prime}\in B_{\delta}(\theta)}\max_{z\neq
0}\frac{z^{t}J(\theta)z}{z^{t}J(\theta^{\prime})z}-1.$ (7)

Since $J(\theta)$ is symmetric and positive definite it has a real
eigendecomposition with positive eigenvalues. Taking the positive square roots
of the eigenvalues provides representation of the principle square root matrix
$J(\theta)^{1/2}$ and taking their reciprocal provides representation of
$J(\theta)^{-1}$. With $J(\theta)$ continuous these inverses and square roots
remain symmetric and continuous in $\theta$ ([28],p.411). Armed with these we
can standardize the empirical Fisher information as
$J(\theta)^{-1/2}\hat{J}(\theta^{\prime})J(\theta)^{-1/2}$, which has
expectation equal to the identity matrix $I$ at $\theta^{\prime}=\theta$.

From the continuity from Assumption 2 and the domination (finiteness of
expected supremum) from Assumption 1, it follows by the monotone convergence
theorem that for every $i,j$ the following quantity also tends to $0$ as
$\delta\rightarrow 0$, for each $\theta$ in $\Theta^{\circ}$,

$\displaystyle E_{\theta}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\pm((J(\theta)^{-1/2}\hat{J}_{1}(\theta^{\prime},x)J(\theta)^{-1/2})_{ij}-I_{ij}),$
(8)

where the $\pm$ indicates that the statement is true with each choice of sign.

The maximum likelihood estimator $\hat{\theta}$ is a consistent estimator of
$\theta$, for each $\theta$ in $\Theta^{\circ}$, so that

$P_{\theta}\\{||\hat{\theta}(x^{n})-\theta||_{J(\theta)}>\delta\\}=o(1),$

for each $\delta>0$.

Remark: We give a demonstration of consistency under suitable conditions in
Lemma F in the Appendix. Assumptions 1, 2, and 3 are related to the conditions
pioneered by Cramér (see p. 501 of [15]) for local asymptotic properties of
maximum likelihood estimators building on earlier assumptions by Wald [47] for
consistency of the maximum likelihood estimator.

The set $K\subseteq\Theta$ has positive and finite

$C_{J}(K)=\int_{K}|J(\theta)|^{1/2}d\theta$

and the measure of $K\setminus K^{\circ}$ is zero.

We remark that the zero measure condition is to make
$C_{J}(K^{\circ})=C_{J}(K)$. It is clearly satisfied if $K$ is open or if $K$
is a closed set with boundary measure zero.

From the theory of finite measures, convergent functions are uniformly
convergent except in sets of arbitrarily small measure. Consequently, as
elaborated in the appendix, if Assumptions 1,2,IV-A hold, then, for any
$\epsilon>0$, there is a $\delta>0$ and a good set $G$ of parameters, such
that for all $\theta$ in $G$ the quantities in (6) and (7) are less than
$\epsilon$, the expected suprema in (8) are less than $\epsilon/(2d)$ and the
Jeffreys measure of the complement of $G$, which is $\int_{K\smallsetminus
G}|J(\theta)|^{1/2}d\theta$, is less than $\epsilon\,C_{J}(K)$.

Moreover, using a law of large numbers, it is shown in the appendix, as a
consequence of the expected suprema being less than $\epsilon/(2d)$, that for
$\theta$ in $G$,

$\displaystyle P_{\theta}\Bigl{(}\inf_{z\neq 0}\inf_{\theta^{\prime}\in
B_{\delta}(\theta)}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J(\theta)z}<1-\epsilon\Bigr{)}=o(1)$
(9)

as $n$ goes to infinity.

To see the connection with the standardized empirical information, note that
the infimum here among $z$ is the same as

$\inf_{\zeta:||\zeta||=1}\inf_{\theta^{\prime}\in
B_{\delta}(\theta)}{\zeta^{t}J(\theta)^{-1/2}\hat{J}(\theta^{\prime})J(\theta)^{-1/2}\zeta}$

as can be seen by setting $\zeta$ to correspond to $J(\theta)^{1/2}z$ divided
by its norm.

Two lower bounds related to maximin regret will be given. The first, using
Assumption 1, is a general lower bound showing the asymptotically validity of
the $(d/2)\log(n/2\pi)+\log C_{J}(K)$ expression, but it somewhat less
constructive. It uses the fact mentioned above that convergent functions are
nearly uniformly convergent, so there exists a good set $G$ with the indicated
properties, while having a small Jeffreys measure for its complement. Also, as
we said, it uses a law of large numbers for a sample average of such suprema,
but, assuming only the finite expectation, there is, in general, no assurance
of rates of approach in such a law of large numbers, and this translates to a
lack of explicit rate of approach in the general lower bound. Moreover, for
the purpose of obtaining the general lower bound on the minimax value it
suffices to appeal to an approximation argument with Jeffreys mixtures that
live on $G$.

The other lower bound we give is specific to the use of the Jeffreys prior on
$K$ without modification. In that case a stronger condition, refining
Assumption 1, will be used with finite expected square (to permit application
of Chebyshev’s inequality for control of rate of convergence in the law of
large numbers), as well as a continuity assumption of the expected suprema, to
get uniform convergence (uniform closeness to zero of the expected suprema)
within any compact subset of $K$. Armed with this more refined Assumption
$1^{\prime}$ (to be specified later below) we have more explicit control of
rates of approach to the maximin value.

Now let $A\subseteq K$ be a parameter set to which Lemma 1 will appeal. This
set $A$ can be the good set $G$ as discussed above, whose existence is a
consequence of Assumptions 1, 2, and IV-A. Or if $K$ is compact and additional
assumptions are satisfied we may have $A=K$.

Define

$\displaystyle\eta_{1,\delta}(A)=$ $\displaystyle\sup_{\theta\in
A}\sup_{\theta^{\prime}\in B_{\delta}(\theta)}\max_{z\neq
0}\frac{z^{t}J(\theta)z}{z^{t}J(\theta^{\prime})z}-1,$ (10)
$\displaystyle\eta_{2,\delta}(A)=$ $\displaystyle\sup_{\theta\in
A}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\frac{|J(\theta^{\prime})|^{1/2}}{|J(\theta)|^{1/2}}-1,$
(11)

and, similarly, let $\eta_{0,\delta}(A)$ be $2d$ times the following supremum

$\displaystyle\sup_{\theta\in A}E_{\theta}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\pm(J(\theta)^{-1/2}\hat{J}_{1}(\theta^{\prime},x)J(\theta)^{-1/2})_{ij}-I_{ij}).$
(12)

As previously mentioned the $2d$ factor is so that when this
$\eta_{0,\delta}(A)\leq\epsilon$ the conclusion of (9) holds.

We extract nice sets within $\Theta\times{\cal X}^{n}$, which we will use in
obtaining lower bounds on the maximin value. Define

$\displaystyle\mathscr{B}$
$\displaystyle=\\{(\theta,x^{n}):\theta,\hat{\theta}(x^{n})\in
K,||\theta-\hat{\theta}(x^{n})||_{J(\theta)}\leq\delta/4\\}$
$\displaystyle\mathscr{N}$ $\displaystyle=\Bigl{\\{}(\theta,x^{n}):\theta\in
A,\inf_{\theta^{\prime}\in B_{\delta}(\theta)}\inf_{z\neq
0}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J(\theta)z}\geq
1-\epsilon\Bigr{\\}}.$ (13)

Here, for any subset $\cal G$ of $\Theta\times{\cal X}^{n}$, we let ${\cal
G}_{x^{n}}$ and ${\cal G}_{\theta}$ denote the section of $\cal G$ given
$x^{n}$ and $\theta$, respectively, that is,

$\displaystyle{\cal G}_{x^{n}}$ $\displaystyle=\\{\theta:(\theta,x^{n})\in\cal
G\\},$ $\displaystyle{\cal G}_{\theta}$
$\displaystyle=\\{x^{n}:(\theta,x^{n})\in\cal G\\}.$

Now fix a pair $(\theta,x^{n})\in\mathscr{N}$. We show that the section
$\mathscr{B}_{x^{n}}$ is included in $B_{\delta}(\theta)$. Assume
$\theta^{\prime}\in\mathscr{B}_{x^{n}}$. Then,

$||\theta^{\prime}-\hat{\theta}||_{J(\theta^{\prime})}\leq\delta/4$

holds. Likewise, since $(\theta,x^{n})\in\mathscr{B}$,

$||\theta-\hat{\theta}||_{J(\theta)}\leq\delta/4.$

Since $\theta,\theta^{\prime}\in\mathscr{B}_{x^{n}}$, and $\theta\in A$ we
have, by the definition of $\eta_{1,\delta}=\eta_{1,\delta}(A)$,

$||\theta^{\prime}-\hat{\theta}||_{J(\theta)}\leq(1+\eta_{1,\delta})^{1/2}||\theta^{\prime}-\hat{\theta}||_{J(\theta^{\prime})}\leq\delta/2,$

assuming $\eta_{1,\delta}\leq 3$. Whence

$||\theta^{\prime}-\theta||_{J(\theta)}<\delta,$

which means $\theta^{\prime}\in B_{\delta}(\theta)$ and
$\mathscr{B}_{x^{n}}\subset B_{\delta}(\theta)$. By this, if
$x^{n}\in\mathscr{N}_{\theta}$ and $(\theta,x^{n})\in\mathscr{B}$, the
following holds,

$\displaystyle\min_{\theta^{\prime}\in\mathscr{B}_{x^{n}}}\min_{z\neq
0}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J(\theta)z}\geq
1-\epsilon.$ (14)

We can prove the following Lemma, which is the heart of our main results for
the lower bounds. Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a
$d$-dimensional family of probability densities. We suppose that Assumptions
IV-A-IV-A hold for $S$. Let $0<\epsilon<1$ be given and assume for a specified
$A\subset K$ that there is a $\delta>0$ such that
$\eta_{0,\delta}(A)\leq\epsilon$. Assume also that $\eta_{1,\delta}(A)\leq 3$
and let $\eta_{2,\delta}=\eta_{2,\delta}(A)$. Define a probability density
$m_{\delta}$ supported on the set

$\mathcal{A}_{\delta}=\\{x^{n}:(\mathscr{N}\cap\mathscr{B})_{x^{n}}\neq\emptyset\\}\subset\mathcal{K},$

by

$\displaystyle\bar{m}_{\delta}(x^{n})$
$\displaystyle=\int_{(\mathscr{N}\cap\mathscr{B})_{x^{n}}}p(x^{n}|\theta)w_{A}(\theta)d\theta,$
(15) $\displaystyle m_{\delta}(x^{n})$
$\displaystyle=\frac{\bar{m}_{\delta}(x^{n})}{\bar{C}_{n}},$ (16)

where

$\displaystyle\bar{C}_{n}=\int_{\mathcal{K}}\bar{m}_{\delta}(x^{n})\nu(dx^{n})$
(17)

Then

$E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{m_{\delta}(x^{n})}\geq\log\frac{(1-\epsilon)^{d/2}C_{J}(A)n^{d/2}}{(1+\eta_{2,\delta})(2\pi)^{d/2}}-o(1)$

holds as $n$ goes to infinity.

Remark: The support of the density $m_{\delta}$ is the set of $x^{n}$ such
that the section $(\mathscr{N}\cap\mathscr{B})_{x^{n}}$ is not empty.

Proof: We have

$\displaystyle
E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{m_{\delta}(x^{n})}=E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{\delta}(x^{n})}+\log\bar{C}_{n}.$
(18)

Note that the log likelihood ratio in the first term of the right hand side is
positive, while $\log(p(x^{n}|\hat{\theta})/m_{\delta}(x^{n}))$ can be
negative.

For the first term. we have

$\displaystyle
E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{\delta}(x^{n})}$
$\displaystyle=$
$\displaystyle\int_{{\mathcal{K}}}\frac{\bar{m}_{\delta}(x^{n})}{\bar{C}_{n}}\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{\delta}(x^{n})}\nu(dx^{n})$
$\displaystyle=$
$\displaystyle\frac{1}{\bar{C}_{n}}\int_{{\mathcal{K}}}\int_{(\mathscr{N}\cap\mathscr{B})_{x^{n}}}\\!\\!\\!p(x^{n}|\theta)w_{{A}}(\theta)d\theta\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{\delta}(x^{n})}\nu(dx^{n})$
$\displaystyle=$
$\displaystyle\frac{1}{\bar{C}_{n}}\int_{{K}}\\!\\!w_{{A}}(\theta)\Bigl{[}\int_{(\mathscr{N}\cap\mathscr{B})_{\theta}}\\!\\!p(x^{n}|\theta)\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{\delta}(x^{n})}\nu(dx^{n})\Bigr{]}d\theta.$

Here, using the sections, reversed order integration is possible by the
Fubini-Tonelli theorem because of positivity of the integrand.

Let $i(\theta)$ denote the quantity in the brackets $[$ $]$. We will show a
lower bound on $i(\theta)$.

Note that $x^{n}\in(\mathscr{N}\cap\mathscr{B})_{\theta}$ is equivalent to
$(\theta,x^{n})\in\mathscr{N}\cap\mathscr{B}$ and to
$\theta\in(\mathscr{N}\cap\mathscr{B})_{x^{n}}$. By Taylor expansion of the
log likelihood ratio around $\hat{\theta}$ under the condition that
$x^{n}\in(\mathscr{N}\cap\mathscr{B})_{\theta}$, we have

$\displaystyle\frac{\bar{m}_{\delta}(x^{n})}{p(x^{n}|\hat{\theta})}$
$\displaystyle=$
$\displaystyle\int_{(\mathscr{N}\cap\mathscr{B})_{x^{n}}}\frac{p(x^{n}|\theta^{\prime})w_{A}(\theta^{\prime})}{p(x^{n}|\hat{\theta})}d\theta^{\prime}$
$\displaystyle=$
$\displaystyle\int_{(\mathscr{N}\cap\mathscr{B})_{x^{n}}}e^{-n(\theta^{\prime}-\hat{\theta})^{t}\hat{J}(\theta^{\prime\prime},x^{n})(\theta^{\prime}-\hat{\theta})/2}w_{A}(\theta^{\prime})d\theta^{\prime},$

where $\theta^{\prime\prime}$ is a point between $\hat{\theta}$ and
$\theta^{\prime}$. Since $x^{n}\in(\mathscr{N}\cap\mathscr{B})_{\theta}$, we
have $\theta\in(\mathscr{N}\cap\mathscr{B})_{x^{n}}$. Now

$\displaystyle\max_{\theta^{\prime}\in
B_{\delta}(\theta)}\frac{w_{A}(\theta^{\prime})}{w_{A}(\theta)}$
$\displaystyle\leq(1+\eta_{2,\delta})$

and

$\displaystyle\min_{\theta^{\prime}\in B_{\delta}(\theta)}\min_{z\neq
0}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J(\theta)z}$
$\displaystyle\geq 1-\epsilon$

hold for $\theta\in A$, where $\eta_{2,\delta}=\eta_{2,\delta}(A)$. Hence we
have for all $x^{n}\in(\mathscr{N}\cap\mathscr{B})_{\theta}$,

$\displaystyle\frac{\bar{m}_{\delta}(x^{n})}{p(x^{n}|\hat{\theta})}$
$\displaystyle\leq$
$\displaystyle(1+\eta_{J,\delta})w_{A}(\theta)\int_{\mathscr{N}_{x^{n}}}e^{-n(1-\epsilon)(\theta^{\prime}-\hat{\theta})^{t}J(\theta)(\theta^{\prime}-\hat{\theta})/2}d\theta^{\prime}$
$\displaystyle\leq$ $\displaystyle(1+\eta_{2,\delta})w_{A}(\theta)\int
e^{-n(1-\epsilon)(\theta^{\prime}-\hat{\theta})^{t}J(\theta)(\theta^{\prime}-\hat{\theta})/2}d\theta^{\prime}$
$\displaystyle=$
$\displaystyle\frac{(1+\eta_{2,\delta})w_{A}(\theta)}{(1-\epsilon)^{d/2}}\frac{(2\pi)^{d/2}}{n^{d/2}|J(\theta)|^{1/2}}$
$\displaystyle=$
$\displaystyle\frac{(1+\eta_{2,\delta})}{(1-\epsilon)^{d/2}}\frac{(2\pi)^{d/2}}{n^{d/2}C_{J}(A)}.$

Hence, for all $\theta\in A$, we have

$\displaystyle
i(\theta)\\!\geq\\!\log\\!\frac{(1-\epsilon)^{d/2}C_{J}(A)n^{d/2}}{(1+\eta_{2,\delta})(2\pi)^{d/2}}\\!\\!\int_{(\mathscr{N}\cap\mathscr{B})_{\theta}}\\!\\!\\!\\!p(x^{n}|\theta)\nu(dx^{n}),$

which implies

$\displaystyle\int_{{K}}w_{A}(\theta)i(\theta)d\theta$ $\displaystyle\geq$
$\displaystyle\Bigl{(}\log\frac{(1-\epsilon)^{d/2}C_{J}(A)n^{d/2}}{(1+\eta_{2,\delta})(2\pi)^{d/2}}\Bigr{)}\int_{{\mathcal{K}}}\bar{m}(x^{n})\nu(dx^{n})$
$\displaystyle=$
$\displaystyle\Bigl{(}\log\frac{(1-\epsilon)^{d/2}C_{J}(A)n^{d/2}}{(1+\eta_{2,\delta})(2\pi)^{d/2}}\Bigr{)}\bar{C}_{n}.$

Dividing both sides by $\bar{C}_{n}$, we have

$\displaystyle
E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{\delta}(x^{n})}\geq\log\frac{(1-\epsilon)^{d/2}C_{J}(A)n^{d/2}}{(1+\eta_{2,\delta})(2\pi)^{d/2}}.$
(19)

Now we will proceed to a lower bound on $\bar{C}_{n}$. We have

$\displaystyle\bar{C}_{n}$
$\displaystyle=\int_{\mathcal{K}}\int_{(\mathscr{N}\cap\mathscr{B})_{x^{n}}}p(x^{n}|\theta)w_{A}(\theta)d\theta\nu(dx^{n})$
$\displaystyle=\int_{{K}}\int_{(\mathscr{N}\cap\mathscr{B})_{\theta}}p(x^{n}|\theta)\nu(dx^{n})w_{A}(\theta)d\theta$
$\displaystyle=\int_{{K}}P_{\theta}((\mathscr{N}\cap\mathscr{B})_{\theta})w_{A}(\theta)d\theta$
$\displaystyle\geq\int_{{K}}(P_{\theta}(\mathscr{N}_{\theta})+P_{\theta}(\mathscr{B}_{\theta})-1)w_{A}(\theta)d\theta$
(20)
$\displaystyle=\int_{{K^{\circ}}}(P_{\theta}(\mathscr{N}_{\theta})+P_{\theta}(\mathscr{B}_{\theta})-1)w_{A}(\theta)d\theta,$
(21)

where the last equality holds because the boundary of $K$ is assumed to have
zero measure. Here, because of (9),

$P_{\theta}(\mathscr{N}_{\theta})=1-o(1)$

holds as $n$ goes to infinity, for each $\theta\in{A}$. Now

$\mathscr{B}_{\theta}=\\{x^{n}:\hat{\theta}\in B_{\delta/4}(\theta)\cap K\\}.$

For $\theta$ on the boundary, the probability of this event generally
converges to number less than one. But for $\theta$ in the interior, the
consistency implies that $\hat{\theta}$ is in $K$ with probability tending to
$1$. Hence for each $\theta\in{K^{\circ}}$, we have

$P_{\theta}(\mathscr{B}_{\theta})=1-o(1)$

as $n$ goes to infinity, because of Assumption IV-A. Obviously,
$\bar{C}_{n}\leq 1$. Together with (20) and the pointwise convergence of
$P_{\theta}(\mathscr{N}_{\theta})$ and $P_{\theta}(\mathscr{B}_{\theta})$ to
$1$, by Fatou’s Lemma (or the dominated convergence theorem) we have that
$\liminf_{n}\bar{C}_{n}\geq 1$. Thus

$\displaystyle\bar{C}_{n}=1-o(1)$ (22)

as $n$ goes to infinity. Hence, with (18) and (19), we have

$E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{m_{\delta}(x^{n})}\geq\log\frac{(1-\epsilon)^{d/2}C_{J}(A)n^{d/2}}{(1+\eta_{2,\delta})(2\pi)^{d/2}}-o(1),$

as $n$ goes to infinity. The proof is completed.

Now we state the theorem about the lower bound on the maximin regret for
general i.i.d. families. Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a
$d$-dimensional family of probability densities. Suppose that Assumptions IV-
A-IV-A hold for $S$. Let $K$ be a subset of $\Theta$ (possibly $K=\Theta$)
which satisfies Assumption IV-A. Then the following holds

$\displaystyle\liminf_{n\rightarrow\infty}\Bigl{(}\mbox{\@text@baccent{$r$}}_{n}(\mathcal{K})-\frac{d}{2}\log\frac{n}{2\pi}\Bigr{)}\geq\log
C_{J}(K).$ (23)

Remark: This theorem allows for $\Theta$ and $K$ to be unbounded as long as
$C_{J}(K)$ is finite.

Proof of Theorem 1: We are given $K\subset\Theta$ satisfying the finite
$C_{J}(K)$ assumption. Let $\epsilon>0$ be arbitrarily small. We have the
existence of the set $A=G$ for which
$\int_{K-G}w_{K}(\theta)d\theta\leq\epsilon$ and within which the properties
of convergence to zero of expressions (6), (7) and (8) hold uniformly within
$G$. This is an appeal to Egorov’s theorem for finite measures that pointwise
convergence implies uniform convergence except in a set of negligible measure.
Accordingly, we can arrange positive $\delta$ sufficiently small that
$\eta_{1,\delta}(A)\leq\epsilon\leq 3$, $\eta_{2,\delta}(A)\leq\epsilon$, and
$\eta_{0,\delta}\leq\epsilon$. As detailed in the appendix, the last
inequality implies the in-probability behavior (9). By Lemma 1 we have a
procedure providing a lower bound on the maximin regret

$\underline{r}_{n}(K)\geq\log\frac{(1-\epsilon)^{d/2}C_{J}(A)n^{d/2}}{(1+\eta_{2,\delta})(2\pi)^{d/2}}-o(1)$

Accordingly,

$\liminf\left[\underline{r}_{n}(K)-(d/2)\log\frac{n}{2\pi}\right]$

is at least

$\log C_{J}(K)+(1+d/2)\log(1-\epsilon)-\log(1+\epsilon).$

Now since $\epsilon$ is arbitrarily small it implies that

$\liminf\left[\underline{r}_{n}(K)-(d/2)\log\frac{n}{2\pi}\right]\geq\log
C_{J}(K).$

This completes the proof of Theorem 1.

Under the following stronger assumptions than those for Theorem IV-A, we can
obtain a lower bound on the average regret for mixtures using Jeffreys prior
on all of $K$, when $K$ is compact. The density $p(x|\theta)$ is twice
continuously differentiable in $\theta$ for all $x$, and there is a
$\bar{r}=\bar{r}(K)>0$ so that for each $i$, $j$ and every $\theta\in K$,

$\displaystyle
E_{\theta}\biggl{[}\sup_{\theta^{\prime}:|\theta^{\prime}-\theta|\leq{r}}|\hat{J}_{ij,1}(\theta^{\prime})|^{2}\biggr{]}$
(24)

is finite and continuous as a function of $\theta$ for $r\leq\bar{r}$.

$J(\theta)$ is continuous and positive definite in $\Theta$. Furthermore, the
gradient $\nabla\log p(x|\theta)$ has expectation $E[\nabla\log
p(X|\theta)]=\int\nabla p(x|\theta)dx$ equal to zero with covariance matrix

$I(\theta)=E_{\theta}[\nabla\log p(X|\theta)\nabla^{t}\log p(X|\theta)]$

also finite and continuous in $\Theta$.

Here $I(\theta)$ and $J(\theta)$ are the two forms of Fisher Information.
Usually $I(\theta)$ equals $J(\theta)$, though we do not need that here.

The maximum likelihood estimator $\hat{\theta}$ is a consistent estimator of
$\theta$, indeed consistent uniformly in $K$, with tail probability tending to
zero faster than $1/\log n$, that is,

$\sup_{\theta\in
K}P_{\theta}\\{|\hat{\theta}(x^{n})-\theta|>\delta\\}=o(1/\log n),$

for each $\delta>0$.

Demonstration of consistency, indeed with tail probability tending to zero at
rate $O(1/n)$ is given in the Appendix under sensible conditions.

Assumption IV-A differs from Assumption 1 because of the presence of the
square of the empirical Fisher information in (24). With Assumption 1′ using
Chebyshev’s inequality we can obtain the following property which strengthens
(9)

$\displaystyle\max_{\theta\in K}P_{\theta}\Bigl{(}\inf_{z\neq
0}\inf_{\theta^{\prime}:|\theta^{\prime}-\theta|\leq\delta}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J(\theta)z}\leq
1-\epsilon\Bigr{)}$ (25) $\displaystyle=\>O(1/n).$

Under Assumptions IV-A, IV-A, IV-A,
$\sqrt{n}J(\theta)^{1/2}(\hat{\theta}-\theta)$ converges in distribution to a
mean zero normal random vector and there is a constant $c$ such that the
following inequality holds for any positive $b$,

$\displaystyle\max_{\theta\in
K}P_{\theta}\bigl{(}\sqrt{n}||J(\theta)^{1/2}(\hat{\theta}-\theta)||>b\sqrt{\log
n}\bigr{)}$ $\displaystyle\quad\leq\frac{c}{b^{2}\log
n}+o\Bigl{(}\frac{1}{\log n}\Bigr{)}.$

The constant $c$ equals $\max_{\theta\in K}{\rm
trace}(J(\theta)^{-1}I(\theta))$ which is the dimension $d$, the trace of an
identity matrix, when $I(\theta)=J(\theta)$.

This Lemma IV-A is proved in the Appendix.

Let $K_{\delta}=\\{\theta\in\Theta:B(\theta,\delta)\subset K\\}$ be the
$\delta$ interior of $K$, where we are using the ordinary Euclidean ball
$B(\theta,r)=\\{\theta^{\prime}\in R^{d}:||\theta^{\prime}-\theta||\leq r\\}$
and let $K\setminus K_{\delta}$ be the corresponding $\delta$ shell of $K$.
(Here we could have used the ellipses based on $J(\theta)$ in place of
Euclidean balls in defining an analogous shell.)

The set $K\subseteq\Theta$ has positive and finite

$C_{J}(K)=\int_{K}|J(\theta)|^{1/2}d\theta$

and, with $\delta_{n}$ of order $\sqrt{\log n}/\sqrt{n}$, the contribution of
the shell $\int_{K\setminus K_{\delta_{n}}}|J(\theta)|^{1/2}d\theta$ is of
order $o(1/\log n)$.

Note that, if the boundary of $K$ has finite surface measure, then the measure
of the $\delta$ shell is of order $\delta$, which is of order $\sqrt{\log
n}/\sqrt{n}$ with the chosen $\delta_{n}$, so the shell measure vanishes at
rate much faster than the required $o(1/\log n)$.

The asymptotic lower bound of Theorem 1 was established by using a code
distribution (16) analogous to the Jeffreys mixture code, but with
modification by restriction for each $x^{n}$ to $\theta$ in
$(\mathscr{B}\cap\mathscr{N})_{x^{n}}$. It is of interest to know whether a
Bayes mixture using Jeffreys prior on all of $K$ has the same asymptotic lower
bound. The next result (Theorem 2) shows this to be true for compact $K$ with
slightly more stringent assumptions. Indeed with these assumptions the
Jeffreys mixture provides a lower bound which is as good as the asymptotically
maximin value. Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a
$d$-dimensional family of probability densities. Suppose that $K$ is a compact
subset of $\Theta$ for which Assumptions 1′, 2′, 3′, and 4′ hold. Define a
density $m_{{K}}$ over $\mathcal{K}={\cal X}^{n}(K)$ as

$\displaystyle m_{{K}}(x^{n})$
$\displaystyle=\frac{\bar{m}_{{K}}(x^{n})}{C_{n}}$
$\displaystyle\bar{m}_{{K}}(x^{n})$
$\displaystyle=1_{\mathcal{K}}(x^{n})\int_{{K}}p(x^{n}|\theta)w_{{K}}(\theta)d\theta,$

where $C_{n}$ is the normalization constant and $w_{{K}}(\theta)$ is the
Jeffreys prior on ${K}$. Then the following holds

$\displaystyle\liminf_{n\rightarrow\infty}\Bigl{(}\mbox{\@text@baccent{$r$}}_{n}(m_{{K}})-\frac{d}{2}\log\frac{n}{2\pi}\Bigr{)}\geq\log
C_{J}({K}).$

Remark: The code distribution $m_{K}(x^{n})$ here differs from code
distribution $m_{\delta}$ used in Theorem 1 because here we do not make the
restriction to $\mathscr{B}\cap\mathscr{N}$.

Proof: We examine the value $\mbox{\@text@baccent{$r$}}_{n}(m_{{K}})$. We have

$\displaystyle E_{m_{K}}\log\frac{p(x^{n}|\hat{\theta})}{m_{K}(x^{n})}$
$\displaystyle=$
$\displaystyle\int_{\mathcal{K}}m_{K}(x^{n})\log\frac{p(x^{n}|\hat{\theta})}{m_{K}(x^{n})}\nu(dx^{n})$
$\displaystyle=$
$\displaystyle\int_{\mathcal{K}}m_{K}(x^{n})\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{K}(x^{n})}\nu(dx^{n})+\log
C_{n}$ $\displaystyle=$
$\displaystyle\frac{1}{C_{n}}\int_{\mathcal{K}}\int_{K}p(x^{n}|\theta)w_{K}(\theta)d\theta\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{K}(x^{n})}\nu(dx^{n})$
$\displaystyle+\log C_{n}.$

We proceed to lower bound it as follows, where $m_{\delta}$ is the same as in
Lemma 1 and
$1_{\mathscr{G}\cap\mathscr{N}}=1_{\mathscr{G}\cap\mathscr{N}}(\theta,x^{n})$,

$\displaystyle\geq$
$\displaystyle\frac{1}{C_{n}}\int_{\mathcal{K}}\int_{K}1_{\mathscr{G}\cap\mathscr{N}}p(x^{n}|\theta)w_{K}(\theta)d\theta\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{K}(x^{n})}\nu(dx^{n})$
$\displaystyle+\log C_{n}$ $\displaystyle=$
$\displaystyle\frac{\bar{C}_{n}}{C_{n}}\int_{\mathcal{K}}m_{\delta}(x^{n})\log\frac{p(x^{n}|\hat{\theta})}{\bar{m}_{K}(x^{n})}\nu(dx^{n})+\log
C_{n}$ $\displaystyle=$
$\displaystyle\frac{\bar{C}_{n}}{C_{n}}\int_{\mathcal{K}}m_{\delta}(x^{n})\log\frac{p(x^{n}|\hat{\theta})}{m_{K}(x^{n})}\nu(dx^{n})+(1-\frac{\bar{C}_{n}}{C_{n}})\log
C_{n}$ $\displaystyle\geq$
$\displaystyle\frac{\bar{C}_{n}}{C_{n}}E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{m_{\delta}(x^{n})}+(1-\frac{\bar{C}_{n}}{{C}_{n}})\log
C_{n}$ $\displaystyle\geq$
$\displaystyle\bar{C}_{n}E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{m_{\delta}(x^{n})}+\log
C_{n},$

where the first inequality in the above manipulation follows from
${p(x^{n}|\hat{\theta})/\bar{m}_{K}(x^{n})}\geq 1$, the second inequality
follows from the positivity of Kullback divergence of $m_{\delta}$ from
$m_{K}$, and the last inequality follows from $C_{n}\leq 1$, which implies
$\log C_{n}\leq 0$.

We appeal to Lemma 1 using $A=K$. By Assumption 1′, the expected supremum in
(8) is continuous in $\theta$ and by the monotone convergence theorem it
converges monotonically to $0$ as $\delta\rightarrow 0$, so by Dini’s Theorem
(see e.g. ([38]), p.150) the convergence is uniform on the compact $K$.
Accordingly, $\eta_{0,\delta}(K)$ tends to zero as $\delta\rightarrow 0$.
Likewise, by compactness, $\eta_{1,\delta}(K)$ and
$\eta_{2,\delta}=\eta_{2,\delta}(K)$ tend to zero as $\delta\rightarrow 0$.
Given $\epsilon>0$, pick $\delta$ such that $\eta_{0,\delta}(K)\leq\epsilon$
and $\eta_{1,\delta}(K)\leq 3.$

By Lemma 1, the expectation in the last line above is lower bounded as

$E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{m_{\delta}(x^{n})}\geq\log\frac{(1-\epsilon)^{d/2}C_{J}({K})n^{d/2}}{(1+\eta_{2,\delta})(2\pi)^{d/2}}-o(1).$

Picking $\delta>0$ and $\epsilon>0$ sufficiently small, the above lower bound
is sufficient for our purpose, provided $\bar{C}_{n}$ and $C_{n}$ converges to
$1$ at a rate sufficiently fast. In fact, noting that the lower bound contains
the term $(d/2)\log n$, we need to prove $\bar{C}_{n}=1-o(1/\log n)$ and
$C_{n}=1-o(1)$, which imply the claim of Theorem 2.

First examine $\bar{C}_{n}$. Here, we already have $\bar{C}_{n}=1-o(1)$ in the
proof of Lemma 1, but it is not sufficient for our purpose. However, using
Assumptions 1′-3′, we can show $\bar{C}_{n}=1-o(1/\log n)$. Indeed, by (20),
we have

$\displaystyle\bar{C}_{n}\geq\int_{{K^{\circ}}}(P_{\theta}(\mathscr{N}_{\theta})+P_{\theta}(\mathscr{B}_{\theta})-1)w_{{K}}(\theta)d\theta.$
(26)

Here, by (25), we have

$\min_{\theta\in K}P_{\theta}(\mathscr{N}_{\theta})\geq 1-o(1/\log n).$

Hence

$\displaystyle\int_{K}P_{\theta}(\mathscr{N}_{\theta})w_{K}(\theta)d\theta\geq
1-o(1/\log n).$ (27)

For evaluation of $P_{\theta}(\mathscr{B}_{\theta})$, we employ Lemma 2. Let
$\delta_{n}=\sqrt{b\log n}/\sqrt{n}$. Then by Lemma 2,

$\min_{\theta\in K}P_{\theta}(\hat{\theta}\in B(\theta,\delta_{n}/2))\geq
1-\frac{4c}{b^{2}\log n}-o\Bigl{(}\frac{1}{\log n}\Bigr{)}.$

Provided $\theta\in K_{\delta_{n}}$, $\hat{\theta}\in B(\theta,\delta_{n}/2)$
implies $\hat{\theta}\in K$ and $\hat{\theta}\in B_{\delta}(\theta)$ for
sufficiently large $n$, that is, $x^{n}\in\mathscr{B}_{\theta}$. Then, we have

$\min_{\theta\in K_{\delta_{n}}}P_{\theta}(\mathscr{B}_{\theta})\geq
1-\frac{4c}{b^{2}\log n}-o\Bigl{(}\frac{1}{\log n}\Bigr{)}.$

Hence we have

$\displaystyle\int_{K}P_{\theta}(\mathscr{B}_{\theta})w_{K}(\theta)d\theta$
$\displaystyle\quad\geq\int_{K_{\delta_{n}}}P_{\theta}(\mathscr{B}_{\theta})w_{K}(\theta)d\theta$
$\displaystyle\quad\geq\frac{C_{J}(K_{\delta_{n}})}{C_{J}(K)}\Bigl{(}1-\frac{4c}{b^{2}\log
n}-o\Bigl{(}\frac{1}{\log n}\Bigr{)}\Bigr{)}.$

Here, by Assumption 4′, ${C_{J}(K_{\delta_{n}})/C_{J}(K)}=1-o(1/\log n)$
holds. Hence, we have

$\displaystyle\int_{K}P_{\theta}(\mathscr{B}_{\theta})w_{K}(\theta)d\theta\geq
1-\frac{4c}{b^{2}\log n}-o\Bigl{(}\frac{1}{\log n}\Bigr{)}.$

Together with (26) and (27), we have

$\bar{C}_{n}\geq 1-\frac{4c}{b^{2}\log n}-o\Bigl{(}\frac{1}{\log n}\Bigr{)}.$

Noting that $b$ can be arbitrarily large, we have $\bar{C}_{n}\geq 1-o(1/\log
n)$.

Next, we will examine $C_{n}$, for which we have

$\displaystyle C_{n}=$
$\displaystyle\int_{\mathcal{K}}\int_{K}1_{\mathcal{K}}(x^{n})p(x^{n}|\theta)w_{K}(\theta)d\theta$
(28) $\displaystyle=$ $\displaystyle\int_{K}P_{\theta}(\hat{\theta}\in
K)w_{K}(\theta)d\theta.$ (29)

By the same way as for $\bar{C}_{n}$, we can prove this is $1-o(1/\log n)$.
The proof is completed.

###  IV-B Lower Bounds for Stochastic Processes

Here, we consider the case in which the model consists of non i.i.d.
stochastic processes.

Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a parameterized family of
joint densities of a stochastic process, i.e. $p(x^{n}|\theta)$ satisfies

$p(x^{n}|\theta)=\int_{\cal X}p(x^{n+1}|\theta)\nu(dx_{n+1})$

and

$\int_{\cal X}p(x_{1}|\theta)\nu(dx_{1})=1.$

We introduce the following notation

$J_{n,\theta}=J_{n}(\theta)\stackrel{{\scriptstyle\mbox{\scriptsize\rm
def}}}{{=}}E_{\theta}\hat{J}(\theta,x^{n}).$

In this subsection, define the Jeffreys prior for each $n$ over $K$ as

$\displaystyle w^{(n)}_{K}(\theta)$
$\displaystyle=\frac{|J_{n,\theta}|^{1/2}}{C_{J,n}(K)}$

where $C_{J,n}(K)$ is the Jeffreys integral

$\displaystyle C_{J,n}(K)$ $\displaystyle=\int_{K}|J_{n,\theta}|^{1/2}d\theta$

based on the Fisher information indexed by $n$.

With the use of $J_{n,\theta}$ we modify the definition of
$B_{\delta}(\theta)$ as

$B_{\delta}(\theta)=B_{n,\delta}(\theta)=\\{\theta^{\prime}\in\Theta:(\theta^{\prime}-\theta)^{t}J_{n,\theta}(\theta^{\prime}-\theta)\leq\delta^{2}\\}.$

We use the following assumptions.

For each $i$, $j$, for each $\theta\in K$, and for each $\tilde{\epsilon}>0$,
there is a $\delta=\delta(\theta,\tilde{\epsilon})>0$, such that

$\displaystyle\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\bigl{(}\pm(J_{n,ij}(\theta)-\hat{J}_{ij}(\theta^{\prime},x^{n}))\bigr{)}\leq\tilde{\epsilon}\>\>\>$
(30)

holds, with $P_{\theta}$ probability converging to $1$ as
$n\rightarrow\infty$.

To define $B_{\delta}(\theta)$ properly, the smallest eigenvalue of
$J_{n}(\theta)$ must be lower bounded by a positive constant. Hence we use the
following assumption, which is used in the upper bound results, too.

The matrix $J_{n}(\theta)$ is positive definite, and the collection of
functions $J_{n}(\theta)$, $n\in\mathbb{N}$ is equicontinuous for
$\theta\in\Theta$, with a continuous $\lambda(\theta)>0$ serving as a lower
bound on its smallest eigenvalue, uniformly for $n\in\mathbb{N}$.

It follows from these two assumption that the assertion of Assumption
$1^{\prime\prime}$ can be refined. Indeed, it follows that for for each
$\theta$ in $K$ and for any $\epsilon>0$, there is an
$\tilde{\epsilon}=\tilde{\epsilon}(\epsilon,\theta)>0$ such that at
$\delta=\delta(\tilde{\epsilon},\theta)$,

$\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\Bigl{(}\pm\bigl{(}J_{n}(\theta)^{-1/2}\bigl{(}J_{n}(\theta)-\hat{J}(\theta^{\prime},x^{n})\bigr{)}J_{n}(\theta)^{-1/2}\bigr{)}_{ij}\Bigr{)}\leq\frac{\epsilon}{d}\>\>\>$

with $P_{\theta}$ probability converging to $1$ as $n\rightarrow\infty$, and
consequently,

$\displaystyle P_{\theta}\Bigl{(}\inf_{z\neq 0}\inf_{\theta^{\prime}\in
B_{\delta}(\theta)}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J_{n}(\theta)z}<1-\epsilon\Bigr{)}=o(1)$
(31)

as $n$ goes to infinity. This corresponds to (9) for the i.i.d. case.

From Assumption $2^{\prime\prime}$, we also have

$\displaystyle\min_{n\in\mathbb{N}}\min_{\theta\in
K}\min_{z:|z|=1}z^{t}J_{n}(\theta)z>0.$ (32)

for compact subsets $K$ of $\Theta$. This is because $\lambda(\theta)$, being
positive and continuous, is therefore strictly positive on any compact set.

Sufficient condition for Assumptions $1^{\prime\prime}$ and $2^{\prime\prime}$
are given in the appendix for Markov processes.

Define two nice sets as

$\displaystyle\mathscr{B}$
$\displaystyle=\\{(\theta,x^{n}):\theta,\hat{\theta}(x^{n})\in{K},||\theta-\hat{\theta}(x^{n})||_{J_{n,\theta}}\leq\delta/4\\}$
(33) $\displaystyle\mathscr{N}$
$\displaystyle=\Bigl{\\{}(\theta,x^{n}):\inf_{\theta^{\prime}\in
B_{\delta}(\theta)}\inf_{z\neq
0}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J_{n}(\theta)z}\geq
1-\epsilon\Bigr{\\}}.$ (34)

Further define

$\displaystyle\eta_{1,J,\delta}=\sup_{\theta\in K}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\max_{z\neq
0}\frac{z^{t}J_{n}(\theta)z}{z^{t}J_{n}(\theta^{\prime})z}-1,$ (35)
$\displaystyle\eta_{2,J,\delta}=\sup_{\theta\in K}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\max_{z\neq
0}\frac{z^{t}J_{n}(\theta^{\prime})z}{z^{t}J_{n}(\theta)z}-1,$ (36)

and $\eta_{J,\delta}=\max\\{\eta_{1,J,\delta},\eta_{2,J,\delta}\\}$. By
equicontinuity of $J_{n}(\theta)$ and compactness of ${K}_{\delta}$, this
$\eta_{J,\delta}$ converges to $0$ as $\delta$ tends to zero, uniformly for
$n\in\cal{N}$.

For $\epsilon>0$, let $\delta=\delta_{\epsilon}>0$, with
$(1+\eta_{J,\delta})^{1/2}<2$, be sufficiently small that (31) holds for each
$\theta\in{K}$, and $\delta_{\epsilon}\rightarrow 0$ as $\epsilon\rightarrow
0$.

As before, when (30) holds we have

$\displaystyle\min_{\theta^{\prime}\in\mathscr{B}_{x^{n}}}\min_{z\neq
0}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J_{n}(\theta)z}\geq
1-\epsilon.$ (37)

For each $\theta$ in $\Theta^{\circ}$, the maximum likelihood estimator
$\hat{\theta}(x^{n})$ is consistent. Namely,
$\lim_{n}|\hat{\theta}(x^{n})-\theta|=0$ in $P_{\theta}$ probability, where
$P_{\theta}$ is the distribution determined by the $x^{n}$ with densities
$p(x^{n})$ for $n\geq 1$.

The Jeffreys integral $C_{J,n}(K)$ is finite.

We can prove the following. Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a
$d$-dimensional family of stochastic processes. We suppose that Assumptions
$1^{\prime\prime}$, $2^{\prime\prime}$, $3^{\prime\prime}$, and
$4^{\prime\prime}$ hold for $S$. Define a density $m_{\delta}$ supported on
the set

$\\{x^{n}:(\mathscr{N}\cap\mathscr{B})_{x^{n}}\neq\emptyset\\}\subset{\mathcal{K}},$

by

$\displaystyle\bar{m}_{\delta}(x^{n})$
$\displaystyle=\int_{(\mathscr{N}\cap\mathscr{B})_{x^{n}}}p(x^{n}|\theta)w^{(n)}_{{K}}(\theta)d\theta,$
$\displaystyle m_{\delta}(x^{n})$
$\displaystyle=\frac{\bar{m}_{\delta}(x^{n})}{\bar{C}_{n}},$

where

$\displaystyle\bar{C}_{n}=\int_{{\mathcal{K}}}\bar{m}_{\delta}(x^{n})\nu(dx^{n}).$
(38)

Then

$E_{m_{\delta}}\log\frac{p(x^{n}|\hat{\theta})}{m_{\delta}(x^{n})}\geq\log\frac{(1-\epsilon)^{d/2}C_{J,n}({K})n^{d/2}}{(1+\eta_{J,\delta})(2\pi)^{d/2}}-o(1)$

holds as $n$ goes to infinity.

Proof: Similar to the proof of Lemma IV-A.

The following result, under the stated assumptions in the non i.i.d. setting,
states that $\log C_{J,n}(K)$ provides control on the minimax regret from
below. It corresponds to Theorem 1 in the i.i.d. setting.

Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a $d$-dimensional family of
stochastic processes. Suppose that Assumptions $1^{\prime\prime}$,
$2^{\prime\prime}$, $3^{\prime\prime}$, and $4^{\prime\prime}$ hold for $S$.
Let $K$ be an arbitrary measurable subset of $\Theta$. Then the following
holds

$\displaystyle\liminf_{n\rightarrow\infty}\Bigl{(}\mbox{\@text@baccent{$r$}}_{n}(\mathcal{K})-\frac{d}{2}\log\frac{n}{2\pi}-\log
C_{J,n}(K)\Bigr{)}\geq 0.$

Proof: The conclusion is a consequence of Lemma IV-B and is shown in the same
fashion as Theorem 1.

##  V Upper Bounds

For the upper bound we handle both i.i.d. and stochastic process cases at
once. We need strength Assumption 2′′, which is a certain equi-continuity of
Fisher information. Similarly as for the lower bound results, we use a compact
subset $K$ of $\Theta^{\circ}$. In this section, $K$ denotes a convex set
which is the closure of an open set.

We employ the following stronger assumption than Assumption 2′′. The matrix
$J_{n}(\theta)$ is positive definite, and the collection of functions
$J_{n,ij}(\theta)$ is Lipschitz continuous in $K$, uniformly for all
$n\in\mathbb{N}$ and for all $i,j$,

$|J_{n,ij}(\theta^{\prime})-J_{n,ij}(\theta)|\leq M|\theta^{\prime}-\theta|$

with a continuous $\lambda(\theta)>0$ serving as a lower bound on its smallest
eigenvalue, uniformly for $n\in\mathbb{N}$.

The main theorem gives the upper bound which matches the lower bound we have
obtained.

To obtain the upper bound, we will construct an enlarged model of probability
densities from the model $S$.

Define a matrix-valued random variable $V\in\mathbb{R}^{d\times d}$ as

$V_{n}(\theta)=V(x^{n}|\theta)=J_{n,\theta}^{-1/2}\hat{J}(\theta,x^{n})J_{n,\theta}^{-1/2}-I.$

We also use the notation $V_{ij,n}(\theta)$ to denote the $(i,j)$-entry of
$V_{n}(\theta)$. Let $\mathcal{B}=(-b/2,b/2)^{d\times d}$ for some small
$b>0$. We consider the case where the following assumption holds. For every
compact set $K$ included in $\Theta^{\circ}$, there exists a $b>0$ and a
$C_{1}=C_{1,K}>0$, such that the following holds.

$\displaystyle\forall n\in\mathbb{N},\>\>\forall\theta\in
K,\>\>\forall\beta\in\mathcal{B},$ $\displaystyle\Bigl{(}\int
p(x^{n}|\theta)\exp(nV_{n}(\theta)\cdot\beta)\nu_{n}(dx^{n})\Bigr{)}^{1/n}<C_{1},$
(39)

where $V(x^{n}|\theta)\cdot\beta$ denotes the matrix inner product of
Frobenius

$\mathrm{trace}(V_{n}(\theta)\beta^{t})=\sum_{ij}V_{ij,n}(\theta)\beta_{ij}.$

Define a function $\psi_{n}(\theta,\beta)$ as

$\psi_{n}(\theta,\beta)=\frac{1}{n}\log\\!\int
p(x^{n}|\theta)\exp(nV_{n}(\theta)\cdot\beta)\nu_{n}(dx^{n}).$

Note that Assumption V is the boundedness of $\psi_{n}(\theta,\beta)$.

We define the enlarged family $\bar{S}$ by

$\displaystyle\bar{S}$
$\displaystyle=\\{p_{e}(x^{n}|\theta,\beta):\theta\in\Theta,\beta\in\mathcal{B}\\},$
$\displaystyle p_{e}(x^{n}|\theta,\beta)$
$\displaystyle=p(x^{n}|\theta)\exp\Bigl{(}n(V_{n}(\theta)\cdot\beta-\psi_{n}(\theta,\beta))\Bigr{)}.$

Let $u=(\theta,\beta)$ and ${\cal
U}=\\{u=(\theta,\beta):\theta\in\Theta,\beta\in\mathcal{B}\\}$. We have

$\displaystyle\frac{\partial\psi_{n}(\theta,\beta)}{\partial\beta_{ij}}=E_{\theta,\beta}V_{ij,n}(\theta)$

and

$\displaystyle\frac{\partial^{2}\psi_{n}(\theta,\beta)}{\partial\beta_{kl}\partial\beta_{ij}}$
$\displaystyle=$ $\displaystyle
n\Bigl{(}E_{\theta,\beta}V_{kl,n}(\theta)V_{ij,n}(\theta)-E_{\theta,\beta}V_{kl,n}(\theta)E_{\theta,\beta}V_{ij,n}(\theta)\Bigr{)},$

where $E_{\theta,\beta}$ denotes expectation with respect to
$p_{e}(x^{n}|\theta,\beta)$. The latter is the covariance of
$\sqrt{n}V_{ij,n}(\theta)$ and $\sqrt{n}V_{kl,n}(\theta)$ at
$p_{e}(x^{n}|\theta,\beta)$. Correspondingly, let ${\rm
Cov}_{n}(\theta,\beta)$ denote the matrix whose $(ij,kl)$-entry is

$[{\rm
Cov}_{n}(\theta,\beta)]_{ij,kl}=\frac{\partial^{2}\psi_{n}(\theta,\beta)}{\partial\beta_{ij}\beta_{kl}}.$

We let $\lambda_{n}^{*}$ denote the maximum of the largest eigenvalue of ${\rm
Cov}_{n}(\theta,\beta)$ among $(\theta,\beta)\in\Theta\times\mathcal{B}$.

When the model is i.i.d., the enlarged family can be single-letterized as

$\displaystyle\bar{S}$
$\displaystyle=\\{p_{e}(x|\theta,\beta):\theta\in\Theta,\beta\in\mathcal{B}\\},$
$\displaystyle p_{e}(x|\theta,\beta)$
$\displaystyle=p(x|\theta)\exp\Bigl{(}V_{1}(\theta)\cdot\beta-\psi(\theta,\beta)\Bigr{)},$

where (39) is reduced to

$\displaystyle\int p(x|\theta)\exp(V_{1}(\theta)\cdot\beta)\nu(dx)<C_{1},$

and

$\psi(\theta,\beta)=\log\\!\int
p(x|\theta)\exp(V_{1}(\theta)\cdot\beta)\nu(dx).$

Note that the enlarged family $p_{e}(x^{n}|\theta,\beta)$ is still i.i.d.,
that is, $p_{e}(x^{n}|\theta,\beta)=\prod_{t=1}^{n}p_{e}(x_{t}|\theta,\beta)$.
Further we have

$\displaystyle
p_{e}(x^{n}|\theta,\beta)=p(x^{n}|\theta)\exp\Bigl{(}n(V_{n}(\theta)\cdot\beta-\psi(\theta,\beta))\Bigr{)}.$

where the following holds.

$V(x^{n}|\theta)=\frac{1}{n}\sum_{t=1}^{n}V(x_{t}|\theta).$

Then, $\partial^{2}\psi(\theta,\beta)/\partial\beta_{kl}\partial\beta_{ij}$ is
the covariance of $V_{ij}(x|\theta)$ and $V_{kl}(x|\theta)$ at
$p_{e}(x|\theta,\beta)$, and we have

$[{\rm
Cov}_{n}(\theta,\beta)]_{ij,kl}=\frac{\partial^{2}\psi(\theta,\beta)}{\partial\beta_{kl}\partial\beta_{ij}}.$

In the i.i.d. case, $[{\rm
Cov}_{n}(\theta,\beta)]_{ij,kl}=\partial^{2}\psi(\theta,\beta)/\partial\beta_{kl}\partial\beta_{ij}$
dose not depend on $n$, $\lambda^{*}_{n}$ also does not depend on $n$. Hence,
we use the symbols ${\rm Cov}(\theta,\beta)$ and $\lambda^{*}$ for i.i.d.
cases.

For a given compact $K$ included in $\Theta^{\circ}$, define subsets
$G_{n,\delta}$ and $G_{n,\delta}^{c}$ of $\mathcal{K}$ as follows.

$\displaystyle G_{n,\delta}$ $\displaystyle=\Bigl{\\{}x^{n}:\hat{\theta}\in
K,\>||V(x^{n}|\hat{\theta})||_{s}\leq\delta\Bigr{\\}},$ $\displaystyle
G_{n,\delta}^{c}$ $\displaystyle=\Bigl{\\{}x^{n}:\hat{\theta}\in
K,\>||V(x^{n}|\hat{\theta})||_{s}>\delta\Bigr{\\}},$

where $||A||_{s}$ for a symmetric matrix $A\in\Re^{d\times d}$ denotes the
spectral norm of $A$ defined as

$||A||_{s}=\max_{z:|z|=1}||Az||=\max_{z:|z|=1}|z^{t}Az|.$

Note the following relation between the spectral norm $||A||_{s}$ and the
Frobenius norm $||A||$ (which is the Euclidean norm of the associated vector
with $d^{2}$ elements).

$\frac{||A||}{\sqrt{d}}\leq||A||_{s}\leq||A||.$

We call elements of $G_{n,\delta}$ and $G_{n,\delta}^{c}$ good strings and not
good strings, respectively.

We also define the two kinds of neighborhood of $\theta$ as

$\displaystyle B_{\epsilon}(\theta)$
$\displaystyle=\\{\theta^{\prime}:(\theta^{\prime}-\theta)^{t}J_{n,\theta}(\theta^{\prime}-\theta)\leq\epsilon^{2}\\},$
(40) $\displaystyle\hat{B}_{\epsilon}(\theta)$
$\displaystyle=\\{\theta^{\prime}:(\theta^{\prime}-\theta)^{t}\hat{J}(\hat{\theta})(\theta^{\prime}-\theta)\leq\epsilon^{2}\\},$
(41)

where the latter depends on $x^{n}$.

We further put the following assumptions. Let $w_{n}(\theta)$ be the prior
density function we use for $p(x^{n}|\theta)$. Assume the following equi-
semicontinuity, that is,

$w_{n}(\theta^{\prime})\geq(1-\eta_{r})w_{n}(\theta)$

holds for all large $n$, for all small $r>0$, for all $\theta\in K$, and for
all $\theta^{\prime}$ in $B_{r}(\theta)$, where $\eta_{r}=\eta(r)$ is a
positive valued function defined on $(0,\infty)$ with $\lim_{r\rightarrow
0}\eta_{r}=0$.

There exist a positive number $\bar{h}_{K}\geq 1$ and a small positive number
$\epsilon=\epsilon_{K}$ such that the following inequality holds for all large
$n$, for all $x^{n}\in{\mathcal{K}}$, for all $\tilde{\theta}\in
B_{\epsilon}(\hat{\theta})\cap K$, and for all $z$.

$\displaystyle
z^{t}\hat{J}(\tilde{\theta},x^{n})z\leq\bar{h}_{K}z^{t}\hat{J}(\hat{\theta},x^{n})z.$
(42)

This assumption does hold for the mixture family with compact $K$
$\subset\Theta^{\circ}$. However, there are other families for which we cannot
show it holds. To treat those cases too, we use the following weakened
assumption. In fact, we prove Theorem V under this assumption.

There exist a positive number $\bar{h}_{K}\geq 1$ and a small positive number
$\epsilon=\epsilon_{K}$ such that the following inequality holds for all large
$n$, for all $x^{n}\in{\mathcal{K}}$, for all $\tilde{\theta}\in
B_{\epsilon}(\hat{\theta})\cap K$, and for all $z$.

$\displaystyle
z^{t}\hat{J}(\tilde{\theta},x^{n})z\leq\bar{h}_{K}\max\\{z^{t}\hat{J}(\hat{\theta},x^{n})z,z^{t}J_{n,\hat{\theta}}z\\}.$
(43)

There exist a number $\kappa_{J}$ $=\kappa_{J}(K)>0$ and a small number
$\delta_{0}=\delta_{0}(K)>0$ such that the following inequality holds for all
large $n$, for all $x^{n}\in G_{n,\delta_{0}}$, for all small $\epsilon>0$,
for all $\tilde{\theta}\in B_{\epsilon}(\hat{\theta})\cap K$, and for all $z$.

$\displaystyle
z^{t}\hat{J}(\tilde{\theta},x^{n})z\leq(1+\kappa_{J}\epsilon)z^{t}\hat{J}(\hat{\theta},x^{n})z.$
(44)

There exists an $\epsilon>0$ and a $\zeta\in(0,1)$, such that,

${\forall n\in\mathbb{N}},\;{\forall
x^{n}\in\mathcal{K}},\;\inf_{\tilde{\theta}\in\hat{B}_{\epsilon}(\hat{\theta})\cap
K}||V(x^{n}|\tilde{\theta})||_{s}\geq\zeta||V(x^{n}|\hat{\theta})||_{s}.$

If the collection of empirical Fisher information matrices
$\hat{J}(\theta)=\hat{J}(\theta,x^{n})$ for all $x^{n}$ and all $n$, is
equicontinuous as functions of $\theta$ in $K$, then Assumptions 9’, 10, 11
hold. For Assumption 9, if also the minimum of the smallest eigenvalue of
$\hat{J}_{n}(\hat{\theta})$ for all $n$ and for all $x^{n}\in\mathcal{K}$ is
lower bounded by a positive constant, then it holds.

The following is used to control the behavior of the ideal prior for
stochastic processes. Note that it holds automatically for i.i.d. cases. For
each $\theta\in K$, $\sup_{n\in\mathbb{N}}||J_{n}(\theta)||_{s}$ is finite.

Under this assumption and Assumption V, we can show that
$\sup_{n\in\mathbb{N}}\sup_{\theta\in K}||J_{n}(\theta)||_{s}$ is finite,
similarly as (32).

Hereafter we use the symbol $\Phi$ to denote the probability measure of the
$d$-dimensional standard normal distribution.

Let $m_{w_{n}}$ be the mixture of $S$ with respect to a prior density
$w_{n}(\theta)$ over a convex and compact set $K$ included in
$\Theta^{\circ}$. Suppose that Assumptions V, 6, and 8 hold. Then, for an
arbitrary $\epsilon>0$, and for all $x^{n}\in G_{n,\delta}$ with
$\delta\leq\delta_{0}$, the following holds

$\displaystyle\log\frac{p(x^{n}|\hat{\theta})}{m_{w_{n}}(x^{n})}$
$\displaystyle\leq\frac{d}{2}\log\frac{n}{2\pi}+\log\frac{|J_{n}(\hat{\theta})|^{1/2}}{w_{n}(\hat{\theta})\Phi(U_{K,\epsilon,n}(\hat{\theta}))}$
$\displaystyle+\log\frac{(1+\kappa_{J}\epsilon)^{d/2}(1+\delta)^{d/2}}{1-\eta_{\epsilon}},$

where

$U_{K,\epsilon,n}(\theta)=N_{\sqrt{n}\epsilon}(0)\cap(nJ_{n}(\theta))^{1/2}(K-\theta),$

and

$N_{r}(0)=\\{z:|z|\leq r\\}.$

Ignoring the restriction to $N_{\sqrt{n}\epsilon}(0)$ the
$\Phi(U_{K,\epsilon,n}(\hat{\theta}))$ may be interpreted as the probability
that a Gaussian variable of mean $\hat{\theta}$ and covariance
$(nJ_{n}(\hat{\theta}))^{-1}$ belongs to the parameter set $K$. When
$\hat{\theta}$ is sufficiently in the interior this
$\Phi(U_{K,\epsilon,n}(\hat{\theta}))$ is near $1$ for large $n$. Whereas, for
$\hat{\theta}$ at the boundary or within order $n^{-1/2}$ of the boundary, it
provides the modification for the classical Laplace approximation to account
for the fact that the near boundary case makes the normal integral
approximation be an incomplete normal integral.

Proof of Lemma V: By a Laplace integration for the mixture $m_{w}$ restricted
in $B_{\epsilon}(\hat{\theta})$, we have

$\displaystyle\frac{m_{w_{n}}(x^{n})}{p(x^{n}|\hat{\theta})}$
$\displaystyle\geq\int_{B_{\epsilon}(\hat{\theta})\cap
K}e^{-n(\theta-\hat{\theta})^{t}\hat{J}(\tilde{\theta})(\theta-\hat{\theta})/2}w_{n}(\theta)d\theta$
$\displaystyle\geq(1-\eta_{\epsilon})w_{n}(\hat{\theta})$
$\displaystyle\cdot\int_{B_{\epsilon}(\hat{\theta})\cap
K}e^{-n(1+\kappa_{J}\epsilon)(\theta-\hat{\theta})^{t}\hat{J}(\hat{\theta})(\theta-\hat{\theta}))/2}d\theta,$

by Assumption 6. . Since $x^{n}\in G_{n,\delta}$, by Assumption V,

$\displaystyle\frac{m_{w_{n}}(x^{n})}{p(x^{n}|\hat{\theta})}$
$\displaystyle\geq(1-\eta_{\epsilon})w_{n}(\hat{\theta})$
$\displaystyle\cdot\int_{B_{\epsilon}(\hat{\theta})\cap
K}e^{-n(1+\kappa_{J}\epsilon)(1+\delta)(\theta-\hat{\theta})^{t}J_{n}(\hat{\theta})(\theta-\hat{\theta}))/2}d\theta.$

Noting

$(nJ_{n}(\hat{\theta}))^{1/2}(B_{\epsilon}(\hat{\theta})-\hat{\theta})=N_{\sqrt{n}\epsilon}(0),$

by change of variables

$z=\bigl{(}(1+\kappa_{J}\epsilon)(1+\delta)nJ_{n}(\hat{\theta})\bigr{)}^{1/2}(\theta-\hat{\theta}),$

the integration in the last line is transformed as

$\displaystyle\int_{B_{\epsilon}(\hat{\theta})\cap
K}e^{-n(1+\kappa_{J}\epsilon)(1+\delta)(\theta-\hat{\theta})^{t}J_{n}(\hat{\theta})(\theta-\hat{\theta}))/2}d\theta$
$\displaystyle=$
$\displaystyle\frac{\int_{(1+\kappa_{J}\epsilon)^{1/2}(1+\delta)^{1/2}U_{K,\epsilon,n}(\theta)}e^{-|z|^{2}/2}dz}{(1+\kappa_{J}\epsilon)^{d/2}(1+\delta)^{d/2}n^{d/2}|J_{n}(\hat{\theta})|^{1/2}},$

which is larger than

$\displaystyle\frac{(2\pi)^{d/2}\Phi(U_{K,\epsilon,n}(\theta))}{(1+\kappa_{J}\epsilon)^{d/2}(1+\delta)^{d/2}n^{d/2}|J_{n}(\hat{\theta})|^{1/2}},$

since $U_{K,\epsilon,n}(\theta)$ is included in

$\displaystyle(1+\kappa_{J}\epsilon)^{1/2}(1+\delta)^{1/2}\bigl{(}N_{\sqrt{n}\epsilon}(0)\cap(nJ_{n}(\theta))^{1/2}(K-\theta)\bigr{)}$

because $K$ is a convex set. Hence we have

$\frac{m_{w_{n}}(x^{n})}{p(x^{n}|\hat{\theta})}\geq\frac{(1-\eta_{\epsilon})w_{n}(\hat{\theta})(2\pi)^{d/2}\Phi(U_{K,\epsilon,n}(\theta))}{(1+\kappa_{J}\epsilon)^{d/2}(1+\delta)^{d/2}n^{d/2}|J_{n}(\hat{\theta})|^{1/2}},$

which yields the claim of the lemma. This completes the proof of Lemma V.

Lemma V suggests the following choice of a prior density:

$w_{K,\epsilon,n}(\theta)=\frac{|J_{n}(\theta)|^{1/2}}{C_{K,\epsilon,n}\Phi(U_{K,\epsilon,n}(\theta))},$

where $C_{K,\epsilon,n}$ is the normalization constant. This idea is that the
prior proportional to $|J_{n}(\theta)|^{1/2}/\Phi(U_{K,\epsilon,n}(\theta))$
provides the approximate modification to Jeffreys prior to equalize the regret
in accordance with Laplace approximation, not only in the interior, but also
for $\hat{\theta}$ near the boundary of $K$.

However, unfortunately this prior $w_{K,\epsilon,n}$ does not satisfy
Assumption V, as seen below. Recall that the assumption requires that the
prior density $w_{n}(\theta^{\prime})$ keeps its value over the range
$B_{\epsilon}(\theta)$. We can make a counter example as follows. Assume that
$\theta$ is at the boundary of $K$ and that $\Phi(N_{\sqrt{n}\epsilon}(0))$
almost equals $1$. Then, $\Phi(U_{K,\epsilon,n}(\theta))$ is smaller than a
half, which means that $w_{K,\epsilon,n}(\theta)$ is larger than twice the
value of Jeffreys prior. Note that there exists $\theta^{\prime}$ in
$B_{\epsilon}(\theta)$ such that $B_{\epsilon}(\theta^{\prime})\subset K$,
provided $\epsilon$ is sufficiently small. For that $\theta^{\prime}$,
$\Phi(U_{K,\epsilon,n}(\theta^{\prime}))$ almost equals $1$. Hence,
$w_{K,\epsilon,n}(\theta^{\prime})\lessapprox w_{K,\epsilon,n}(\theta)/2$
holds.

To overcome this problem, we employ the slightly modified prior than
$w_{K,\epsilon,n}$, which we call the ideal priors for the good strings. To
this end, we define a modified region of $U_{K,\epsilon,n}(\theta)$ as below.

$\displaystyle
U^{(\alpha)}_{K,\epsilon,n}(\theta)=N_{\sqrt{n}\epsilon}(0)\cap((n/\alpha^{2})J_{n}(\theta))^{1/2}(K-\theta)$

where $\alpha$ is a positive real value.

Remark: If $J_{n}(\theta)$ does not depend on $n$, i.e.
$J_{n}(\theta)=J(\theta)$, then

$U^{(\alpha)}_{K,\epsilon,n}(\theta)=U_{K,\alpha\epsilon,n/\alpha^{2}}(\theta)$

holds.

Note that

$U^{(\alpha)}_{K,\epsilon,n}(\theta)\subset U_{K,\epsilon,n}(\theta)$

holds for $\alpha\geq 1$, since $K$ is a convex set, which means

$\displaystyle\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))\leq\Phi(U_{K,\epsilon,n}(\theta)).$
(45)

[The ideal prior for the good strings] Define the prior density
$w^{(\alpha)}_{K,\epsilon,n}$ over $K$ as

$w^{(\alpha)}_{K,\epsilon,n}(\theta)=\frac{|J_{n}(\theta)|^{1/2}}{C_{K,\epsilon,n}^{(\alpha)}\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))},$

where

$C^{(\alpha)}_{K,\epsilon,n}=\int_{K}\frac{|J_{n}(\theta)|^{1/2}}{\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))}d\theta,$

where we assume $n\epsilon^{2}\rightarrow\infty$,
$\alpha/\sqrt{n}\epsilon\rightarrow\infty$ and $\epsilon\alpha\rightarrow 0$
as $n$ goes to infinity.

Remark: As for setting of $\epsilon$ and $\alpha$, we may let
$\epsilon=\sqrt{\log n/n}$ and $\alpha=\log n$ for example.

For this prior we can show that Assumption V holds under Assumption V and that
$C_{J,n}(K)/C_{K,\epsilon,n}^{(\alpha)}\rightarrow 1$ as $n$ goes to infinity.
First, we will show the latter.

Note that the following holds. For all $n>0$ and $\epsilon>0$,

$\Phi(N_{\sqrt{n}\epsilon}(0))\geq
1-\exp\Bigl{(}-\frac{n\epsilon^{2}}{2}\bigl{(}1-\frac{d}{n\epsilon^{2}}\log\frac{n\epsilon^{2}}{d}\bigr{)}+\frac{d}{2}\Bigr{)},$

which is larger than

$1-\exp\Bigl{(}-\frac{n\epsilon^{2}}{4}+\frac{d}{2}\Bigr{)},$

when $n\epsilon^{2}/d\geq 2$.

See Appendix H for the proof.

Using this proposition, we have the following lemma, where

$\displaystyle\rho^{(\alpha)}_{n}(\epsilon,\theta)$
$\displaystyle=\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))$

and

$\displaystyle\rho^{(\alpha)}_{n}(\epsilon)=\inf_{\theta\in
K}\rho^{(\alpha)}_{n}(\epsilon,\theta).$

Let $K$ be an arbitrary compact set in $\Theta^{\circ}$. Suppose Assumption V
holds and let $̱\lambda$ denote a lower bound on the smallest eigenvalue of
$J_{n,\theta}$ among $n\in\mathbb{N}$ and $\theta\in K$. Let

$K_{\epsilon}=\\{\theta:B_{\epsilon}(\theta)\subset K\\},$

Then for $\epsilon$ such that $n\epsilon^{2}/d\geq 2$ and
$\epsilon^{2}\alpha^{2}\leq\mbox{\@text@baccent{$\lambda$}}$, we have

$C_{J,n}(K)\leq
C_{K,\epsilon,n}^{(\alpha)}\leq\frac{C_{J,n}(K)}{1-e^{-n\epsilon^{2}/4+d/2}}+\frac{C_{J,n}(K\setminus
K_{\epsilon\alpha})}{\rho_{n}^{(\alpha)}(\epsilon)},$

where

$C_{J,n}(A)=\int_{A}|J_{n,\theta}|^{1/2}d\theta.$

The proof is in Appendix I.

We have a lower bound for $\rho^{(\alpha)}_{n}(\epsilon)$ as follows, where
${\rm vol}(A)$ denotes the volume of $A\in\mathbb{R}^{d}$, ${\rm diam}(A)$ the
diameter of $A\in\mathbb{R}^{d}$, and $V_{k}$ the volume of the
$k$-dimensional sphere of radius $1$, that is,

$V_{k}=\frac{\pi^{k/2}}{\Gamma(k/2+1)}.$

Assume that $K$ is compact, convex, and the closure of an open set in
$\Re^{d}$. Then, for all $\epsilon$ such that ${\rm
vol}(N_{\epsilon}(0))\leq{\rm vol}(J^{1/2}_{n,\theta}K)/2$, the following
holds.

$\rho^{(\alpha)}_{n}(\epsilon,\theta)\geq\frac{{\rm
vol}(J^{1/2}_{n,\theta}K)}{2({\rm
diam}(J^{1/2}_{n,\theta}K))^{d}V_{d}}\Phi(N_{\sqrt{n}\epsilon}(0)).$

Since Assumptions V and V, the minimum eigenvalue of $J_{n,\theta}$ has a
positive lower bound and the maximum eigenvalue has an upper bound, which are
uniform for $\theta\in K$. Hence, by Lemma V, $\rho^{(\alpha)}_{n}(\epsilon)$
is lower bounded by a positive constant when $\sqrt{n}\epsilon/\alpha$ is not
small.

Noting this fact, we can show the following lemma. Suppose that Assumptions V
and V hold. If $\epsilon/\alpha\rightarrow 0$ and
$n\epsilon^{2}/\alpha^{2}\rightarrow\infty$ as $n$ goes to infinity, then

$\lim_{n\rightarrow\infty}\Bigl{(}\log{C_{K,\epsilon,n}^{(\alpha)}}-\log{C_{J,n}(K)}\Bigr{)}=0.$

Proof: Since $\sup_{\theta\in K}\sup_{n}|J_{n}(\theta)|^{1/2}$ is finite under
Assumption V, $C_{J,n}(K\setminus K_{\epsilon\alpha})$ converges to zero
uniformly for all $n$, as $\epsilon$ tends to zero. Noting that
$\rho_{n}^{(\alpha)}$ is lower bounded by a certain positive constant, since
Lemma V. Hence by Lemma V, which is shown under Assumption V, we have the
claim of the lemma. This completes the proof.

To show that Assumption V holds for the ideal priors, we will show the
following lemma. Let $\lambda_{n}$ denote the maximum of the largest
eigenvalue of $J_{n}(\theta)$ among $\theta\in K$. For a certain $\epsilon>0$,
for all $r\leq\epsilon$, for all $\theta^{\prime}\in B_{r}(\theta)\cap K$, and
for all $\theta\in K$,

$\displaystyle\frac{\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta^{\prime}))}{\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))}$
$\displaystyle\leq$ $\displaystyle
1+\frac{\sqrt{n\lambda_{n}}r}{\rho_{n}(\epsilon,\theta)\alpha}+\frac{C_{d}\,{\rm
diam}(K)\sqrt{n\lambda_{n}}\max\\{g_{\theta,r},0\\}}{\rho_{n}(\epsilon,\theta)\alpha}$

holds, where $C_{d}=2^{1-d/2}\Gamma(d/2)$ and

$g_{\theta,r}=\max_{\theta^{\prime}\in B_{r}(\theta)\cap
K}||J_{n}(\theta)^{-1/2}J_{n}(\theta^{\prime})^{1/2}||_{s}-1.$

The proof is in Appendix K.

Note that $\rho_{n}^{(\alpha)}(\epsilon,\theta)$ is lower bounded by a
positive constant, since $\sqrt{n}\epsilon\rightarrow\infty$ when $n$ goes to
infinity because of Lemma V. Since $g_{\theta,r}$ is of order $r$ uniformly
over $K$ by Assumption V, we have

$\displaystyle\sup_{\theta^{\prime}\in K\cap B_{r}(\theta)}\sup_{\theta\in
K}\frac{\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta)}{\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta^{\prime}))}\geq
1-O\Bigl{(}\frac{\sqrt{n}\epsilon}{\alpha}\Bigr{)},$ (46)

when $\sqrt{n}\epsilon/\alpha$ tends to $0$. From this, we have

$\inf_{\theta\in K}\inf_{\theta^{\prime}\in
B_{r}(\theta)}\frac{w_{K,\epsilon,n}^{(\alpha)}(\theta^{\prime})}{w_{K,\epsilon,n}^{(\alpha)}(\theta)}\geq
1-O\Bigl{(}\frac{\sqrt{n}\epsilon}{\alpha}\Bigr{)},$

Since we assume $\sqrt{n}\epsilon/\alpha$ tends to $0$ as $n$ goes to
infinity, this means that $w_{K,\epsilon,n}^{(\alpha)}$ satisfies Assumption
V. Hence, we can immediately show the following lemma from Lemma V and (45).
In fact, for the ideal priors, Assumption V holds under Assumption V on Fisher
information. Let $m_{K,\epsilon,n}^{(\alpha)}$ denote the mixture of $S$ with
respect to the prior density $w_{K,\epsilon,n}^{(\alpha)}$. Suppose that
Assumptions V, 7, 8, and 10 hold. Then, for all $x^{n}\in G_{n,\delta}$ and
for all $\epsilon>0$, we have

$\displaystyle\log\frac{p(x^{n}|\hat{\theta})}{m_{K,\epsilon,n}^{(\alpha)}(x^{n})}$
$\displaystyle\leq$ $\displaystyle\frac{d}{2}\log\frac{n}{2\pi}+\log
C_{K,\epsilon,n}^{(\alpha)}$ $\displaystyle+$
$\displaystyle\log\frac{(1+\kappa_{J}\epsilon)^{d/2}(1+\delta)^{d/2}}{1-\eta_{\epsilon}}.$

Here, we treat the strings $x^{n}\in G_{n,\delta}^{c}$. We use the mixture of
the extended model $\bar{S}$. Define a prior density $\bar{w}(\theta,\beta)$
over $\bar{S}$ as

$\displaystyle\bar{w}(\theta,\beta)=w_{K}^{(n)}(\theta)b^{-d^{2}}.$

Note that this is the direct product of the Jeffreys prior
$w_{K}^{(n)}(\theta)$ and the uniform probability density over $\mathcal{B}$.

Recall that $\lambda_{n}^{*}$ denotes the maximum of the largest eigenvalue of
${\rm Cov}_{n}(\theta,\beta)$ among
$(\theta,\beta)\in\Theta\times\mathcal{B}$. We have the following Lemma. Let
$\bar{m}$ denote the mixture of $\bar{S}$ with respect to the prior $\bar{w}$.
Suppose Assumptions V, V, V, and V. Set
$\tilde{a}=\min\\{1/2\lambda_{n}^{*},1\\}$ and
$\tilde{\delta}=\zeta\delta/\sqrt{d}$. Then for all $x^{n}\in
G_{n,\delta}^{c}$, we have

$\displaystyle\frac{\bar{m}(x^{n})}{p(x^{n}|\hat{\theta})}$
$\displaystyle\geq\frac{(1-\eta_{\epsilon})\pi^{d/2}\Phi(U_{K,\epsilon,n})}{\bigl{(}\bar{h}_{K}(1+||V(x^{n}|\hat{\theta})||_{s})n\bigr{)}^{d/2}C_{J,n}(K)}$
$\displaystyle\cdot\frac{V_{d^{2}}(\tilde{a}\tilde{\delta})^{d^{2}}}{2^{d^{2}}}\exp\Bigl{(}\frac{\zeta
n||V(x^{n}|\hat{\theta})||_{s}\tilde{a}\tilde{\delta}}{16}\Bigr{)}.$ (47)

Remark: The key factor in this expression is the exponential in
$n||V(x^{n}|\hat{\theta})||\tilde{\delta}$, which makes the coding
distribution $\bar{m}(x^{n})$ large when the empirical Fisher information
deviation $V(x^{n}|\hat{\theta})$ is not small.

Proof: Note that

$\displaystyle\frac{\bar{m}(x^{n})}{p(x^{n}|\hat{\theta})}$ $\displaystyle=$
$\displaystyle\int\frac{p_{e}(x^{n}|\theta,\beta)\bar{w}(\theta,\beta)}{p(x^{n}|\hat{\theta})}d\theta
d\beta$ $\displaystyle=$ $\displaystyle b^{-d^{2}}\\!\\!\\!\int\int
e^{n(V_{n}(\theta)\cdot\beta-\psi_{n}(\theta,\beta))}d\beta\frac{p(x^{n}|\theta)}{p(x^{n}|\hat{\theta})}w_{K}^{(n)}(\theta)d\theta.$

First, we will evaluate the integral with respect to $\beta$ assuming
$\theta\in B_{\epsilon}(\hat{\theta})$, which implies
$||V_{n}(\theta)||_{s}\geq\zeta||V_{n}(\hat{\theta})||_{s}>\zeta\delta$, by
Assumption V and $x^{n}\in G_{n,\delta}^{c}$. Hence,
$||V_{n}(\theta)||\geq\zeta\delta/\sqrt{d}=\tilde{\delta}$ holds. Below, We
will find a certain region where the integrand
$e^{n(V_{n}(\theta)\cdot\beta-\psi_{n}(\theta,\beta))}$ is exponentially large
in the polynomial of $n$.

By Taylor expansion of $\psi_{n}(\theta,\beta)$ with respect to $\beta$ at
$(\theta,0)$, we have

$\displaystyle V_{n}(\theta)\cdot\beta-\psi_{n}(\theta,\beta)$
$\displaystyle=$ $\displaystyle V_{n}(\theta)\cdot\beta-\beta^{t}n{\rm
Cov}_{n}(\theta,\beta^{\prime})\beta/2$ $\displaystyle\geq$ $\displaystyle
V_{n}(\theta)\cdot\beta-\lambda^{*}_{n}||\beta||^{2}/2,$ (48)

where $\beta^{\prime}=t\beta$ with a certain $t\in[0,1]$, and

$\beta^{t}n{\rm
Cov}_{n}(\theta,\beta^{\prime})\beta=\sum_{ij,kl}\beta_{ij}[n{\rm
Cov}_{n}(\theta,\beta^{\prime})]_{ij,kl}\beta_{kl}.$

Let $f(\beta)$ denote the last side of (48). Introduce new parameters
$(v,\beta_{\perp})\in\Re\times\mathcal{B}$ by

$\beta=v\frac{V_{n}(\theta)}{||V_{n}(\theta)||}+\beta_{\perp},$

where $\beta_{\perp}\cdot V_{n}(\theta)=0$ is assumed. Then, we have

$f(\beta)=||V_{n}(\theta)||v-\frac{\lambda_{n}^{*}}{2}(v^{2}+||\beta_{\perp}||^{2}).$

Now consider the region $N_{\tilde{a}\tilde{\delta}/2}(\tilde{\beta})$ with
$\tilde{\beta}$ $=(\tilde{v},\tilde{\beta}_{\perp})$
$=(\tilde{a}\tilde{\delta},0)$. Note that $\tilde{a}\lambda_{n}^{*}\leq 1/2$
holds since $\tilde{a}=\min\\{1/2\lambda_{n}^{*},1\\}$. For all $\beta$ in
$N_{\tilde{a}\tilde{\delta}/2}(\tilde{\beta})$, we have

$\displaystyle f(\beta)$ $\displaystyle=$
$\displaystyle||V_{n}(\theta)||v-\frac{\lambda_{n}^{*}}{2}\bigl{(}(\tilde{a}\tilde{\delta}+v-\tilde{a}\tilde{\delta})^{2}+||\beta_{\perp}||^{2}\bigr{)}$
$\displaystyle=$ $\displaystyle||V_{n}(\theta)||v$ $\displaystyle-$
$\displaystyle\frac{\lambda_{n}^{*}}{2}\bigl{(}\tilde{a}^{2}2\tilde{\delta}^{2}+2\tilde{a}\tilde{\delta}(v-\tilde{a}\tilde{\delta})+(v-\tilde{a}\tilde{\delta})^{2}+||\beta_{\perp}||^{2}\bigr{)}$
$\displaystyle\geq$
$\displaystyle||V_{n}(\theta)||v-\frac{\lambda_{n}^{*}}{2}\Bigl{(}\tilde{a}^{2}2\tilde{\delta}^{2}+2\tilde{a}\tilde{\delta}(v-\tilde{a}\tilde{\delta})+\frac{\tilde{a}^{2}2\tilde{\delta}^{2}}{4}\Bigr{)}$
$\displaystyle=$
$\displaystyle\bigl{(}||V_{n}(\theta)||-\lambda_{n}^{*}a\tilde{\delta}\bigr{)}v-\frac{3\lambda_{n}^{*}\tilde{a}^{2}2\tilde{\delta}^{2}}{8}$
$\displaystyle\geq$
$\displaystyle\frac{||V_{n}(\theta)||}{2}v-\frac{3\lambda_{n}^{*}\tilde{a}^{2}2\tilde{\delta}^{2}}{8}$
$\displaystyle\geq$
$\displaystyle\frac{||V_{n}(\theta)||\tilde{a}\tilde{\delta}}{4}-\frac{3\lambda_{n}^{*}\tilde{a}^{2}2\tilde{\delta}^{2}}{8}$
$\displaystyle=$
$\displaystyle\frac{\tilde{a}\tilde{\delta}}{4}\Bigl{(}||V_{n}(\theta)||-\frac{3\lambda_{n}^{*}\tilde{a}\tilde{\delta}}{2}\Bigr{)}$
$\displaystyle\geq$
$\displaystyle\frac{\tilde{a}\tilde{\delta}}{4}\Bigl{(}||V_{n}(\theta)||-\frac{3\tilde{\delta}}{4}\Bigr{)}$
$\displaystyle\geq$
$\displaystyle\frac{\tilde{a}\tilde{\delta}||V_{n}(\theta)||}{16}.$

To derive the first inequality above, we have used
$(v-\tilde{a}\tilde{\delta})^{2}+||\beta_{\perp}||^{2}\leq(\tilde{a}\tilde{\delta}/2)^{2}$
for $\beta\in N_{\tilde{a}\tilde{\delta/2}}(\tilde{\beta})$. The second
follows from $\lambda_{n}^{*}\tilde{a}\leq 1/2$ and
$\tilde{\delta}\leq||V_{n}(\theta)||$. The others also follow from them and
$v\geq\tilde{a}\tilde{\delta}/2$. In this evaluation, we used the condition
$a\lambda_{n}^{*}\leq 1/2$, but we actually defined
$\tilde{a}=\min\\{1/2\lambda_{n}^{*},1\\},$ since too large $\tilde{a}$ may
cause the problem that $N_{\tilde{a}\tilde{\delta}/2}(\tilde{\beta})$ is
beyond $\mathcal{B}$.

From this, the following lower bound provided $\theta\in
B_{\epsilon}(\hat{\theta})$ is obtained.

$\displaystyle\int
e^{n(V(x^{n}|\theta)\cdot\beta-\psi_{n}(\theta,\beta))}d\beta$
$\displaystyle\geq\int_{N_{\tilde{a}\tilde{\delta}/2}(\tilde{\beta})}e^{n(V(x^{n}|\theta)\cdot\beta-\psi_{n}(\theta,\beta))}d\beta$
$\displaystyle\geq\frac{V_{d^{2}}(\tilde{a}\tilde{\delta})^{d^{2}}}{2^{d^{2}}}\exp\Bigl{(}\frac{n||V_{n}(\theta)||\tilde{a}\tilde{\delta}}{16}\Bigr{)}$
$\displaystyle\geq\frac{V_{d^{2}}(\tilde{a}\tilde{\delta})^{d^{2}}}{2^{d^{2}}}\exp\Bigl{(}\frac{n\zeta||V_{n}(\hat{\theta})||_{s}\tilde{a}\tilde{\delta}}{16}\Bigr{)},$
(49)

where we have used Assumption 11 and the inequality $||A||_{s}\leq||A||$.

Next we will evaluate the integral with respect to $\theta$. Since the bound
for the integral with $\beta$ is uniform for $\theta\in
B_{\epsilon}(\hat{\theta})$, it suffices to evaluate

$\int_{B_{\epsilon}(\hat{\theta})}\frac{p(x^{n}|\theta)w_{K}^{(n)}(\theta)}{p(x^{n}|\hat{\theta})}d\theta.$

For that purpose, we make use of (42) in Assumption V. We need a case argument
depending on which one is the maximum in the right side of (42). For
$\theta\in B_{\epsilon}(\hat{\theta})$, first assume
$(\theta-\hat{\theta})^{t}J_{n,\hat{\theta}}(\theta-\hat{\theta})\leq(\theta-\hat{\theta})^{t}\hat{J}(\hat{\theta})(\theta-\hat{\theta})$,
then we have

$\displaystyle\frac{p(x^{n}|\theta)}{p(x^{n}|\hat{\theta})}$
$\displaystyle\geq\exp\Bigl{(}\frac{-n(\theta-\hat{\theta})^{t}\hat{J}(\theta^{\prime})(\theta-\hat{\theta})}{2}\Bigr{)}$
$\displaystyle\geq\exp\Bigl{(}\frac{-n\bar{h}_{K}(\theta-\hat{\theta})^{t}\hat{J}(\hat{\theta})(\theta-\hat{\theta})}{2}\Bigr{)},$

where $\theta^{\prime}=t\theta+(1-t)\hat{\theta}$ with a certain $t\in[0,1]$.
The last inequality follows from Assumption V. Since

$||(J_{n,\hat{\theta}})^{-1/2}\hat{J}(\hat{\theta})(J_{n,\hat{\theta}})^{-1/2}||_{s}\leq||V(x^{n}|\hat{\theta})||_{s}+1$

holds, we have

$\frac{(\theta-\hat{\theta})^{t}\hat{J}(\hat{\theta})(\theta-\hat{\theta})}{(\theta-\hat{\theta})^{t}J_{n,\hat{\theta}}(\theta-\hat{\theta})}\leq||\hat{V}||_{s}+1,$

where $\hat{V}$ denotes $V(x^{n}|\hat{\theta})$. Hence for any $\theta\in
B_{\epsilon}(\hat{\theta})$ with
$(\theta-\hat{\theta})^{t}J_{n,\hat{\theta}}(\theta-\hat{\theta})\leq(\theta-\hat{\theta})^{t}\hat{J}(\hat{\theta})(\theta-\hat{\theta})$,

$\displaystyle\frac{p(x^{n}|\theta)}{p(x^{n}|\hat{\theta})}\geq
e^{-n\bar{h}_{K}(1+||\hat{V}||_{s})(\theta-\hat{\theta})^{t}J_{n,\hat{\theta}}(\theta-\hat{\theta})/2}.$
(50)

Next assume
$(\theta-\hat{\theta})^{t}J_{n,\hat{\theta}}(\theta-\hat{\theta})>(\theta-\hat{\theta})^{t}\hat{J}(\hat{\theta})(\theta-\hat{\theta})$
for $\theta\in B_{\epsilon}(\hat{\theta})$. Then, directly from Assumption V,
we have

$\frac{p(x^{n}|\theta)}{p(x^{n}|\hat{\theta})}\geq
e^{-n\bar{h}_{K}(\theta-\hat{\theta})^{t}J_{n,\hat{\theta}}(\theta-\hat{\theta})/2}.$

Hence, (50) holds for any $\theta\in B_{\epsilon}(\hat{\theta})$.

Then, in a manner similar to the proof of Lemma V, by Laplace approximation
over $B_{\epsilon}(\hat{\theta})$, we have

$\displaystyle\int_{B_{\epsilon}(\hat{\theta})}\frac{p(x^{n}|\theta)w_{K,n}(\theta)}{p(x^{n}|\hat{\theta})}d\theta$
$\displaystyle\geq\frac{(1-\eta_{\epsilon})(2\pi)^{d/2}\Phi(U_{K,\epsilon,n})w_{K}^{(n)}(\hat{\theta})}{\bar{h}_{K}^{d/2}n^{d/2}(1+||\hat{V}||_{s})^{d/2}|J_{n,\hat{\theta}}|^{1/2}}$
$\displaystyle=\frac{(1-\eta_{\epsilon})(2\pi)^{d/2}\Phi(U_{K,\epsilon,n})}{\bar{h}_{K}^{d/2}n^{d/2}(1+||\hat{V}||_{s})^{d/2}C_{J,n}(K)}$

Together with (49), we have (47). This completes the proof of Lemma V.

Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a $d$-dimensional family of
stochastic processes. Suppose that Assumptions 7, 8, 9’, 10, and 11 hold.
Further, we assume that $J_{n}(\theta)$ is equicontinuous for all $n$ and that

$\lambda^{*}=\varlimsup_{n\rightarrow\infty}\lambda_{n}^{*}$

is finite. Fix a sequence $\epsilon_{n}$ which converges to $0$ slower than
$1/\sqrt{n}$. Define a mixture $m_{n}$ over $\bar{S}$ as

$m_{n}(x^{n})=(1-n^{-r})m_{K,\epsilon_{n},n}(x^{n})+n^{-r}\bar{m}(x^{n}).$

Then, the following holds.

$\displaystyle\varlimsup_{n\rightarrow\infty}\Bigl{(}\sup_{x^{n}\in\mathcal{K}}$
$\displaystyle\log\frac{p(x^{n}|\hat{\theta})}{m_{n}(x^{n})}-\frac{d}{2}\log\frac{n}{2\pi}-\log
C_{J,n}(K)\Bigr{)}$ $\displaystyle\leq 0.$ (51)

Proof: In this proof, we use Lemmas 5 and 8, plugging in
$\delta_{n}=n^{-1/2+\gamma}$ in place of $\delta$, which means that
$\tilde{\delta}$ is replaced by

$\tilde{\delta}_{n}=\frac{\zeta\delta_{n}}{\sqrt{d}}.$

When $x^{n}\in G_{n,\delta_{n}}$, by Lemma V, we have

$\displaystyle\log\frac{p(x^{n}|\hat{\theta})}{m_{n}(x^{n})}$
$\displaystyle\leq\frac{d}{2}\log\frac{n}{2\pi}+\log C_{K,\epsilon_{n},n}$
$\displaystyle+\log$
$\displaystyle\frac{(1+\kappa_{J}\epsilon_{n})^{d/2}(1+\delta_{n})^{d/2}}{1-\eta(\epsilon_{n})}-\log(1-n^{-r}).$

Here, $\delta_{n}$, $n^{-r}$ and $|\log C_{K,\epsilon_{n},n}-\log C_{J,n}(K)|$
converge to $0$ as $n$ goes to infinity (the last one follows from Lemma 7),
hence we have

$\displaystyle\varlimsup_{n\rightarrow\infty}$ $\displaystyle\sup_{x^{n}\in
G_{n,\delta_{n}}}\Bigl{(}\log\frac{p(x^{n}|\hat{\theta})}{m_{n}(x^{n})}-\frac{d}{2}\log\frac{n}{2\pi}-\log
C_{J,n}(K)\Bigr{)}$ $\displaystyle\leq 0.$

Next, we move to the case that $x^{n}\in G_{n,\delta_{n}}^{c}$. Since

$\frac{m_{n}(x^{n})}{p(x^{n}|\hat{\theta})}\geq\frac{n^{-r}\bar{m}(x^{n})}{p(x^{n}|\hat{\theta})},$

we evaluate the lower bound of $\bar{m}(x^{n})/p(x^{n}|\hat{\theta})$ using
Lemma V. When $n$ is large and $\epsilon$ is small, the right side of (47)
times $C_{J,n}(K)$ is not less than $g(||\hat{V}||_{s})$ with

$g(\xi)=\frac{A(\tilde{a}\tilde{\delta}_{n})^{d^{2}}}{(1+\xi)^{d/2}n^{d/2}}\exp\Bigl{(}\frac{\zeta
n\xi\tilde{a}\tilde{\delta}_{n}}{16}\Bigr{)},$

where $A$ is a constant which does not depend on $||\hat{V}||_{s}$, $n$, and
$\tilde{\delta}_{n}$. The first derivative of $\log g(\xi)$ is

$-\frac{d}{2(1+\xi)}+\frac{\zeta
n\tilde{a}\tilde{\delta}_{n}}{16}\geq-\frac{d}{2}+\frac{\zeta
n\tilde{a}\tilde{\delta}_{n}}{16},$

which is positive when $n$ is large, since $n\tilde{\delta}_{n}$ diverges to
infinity as $n$ goes to infinity. Hence, $g(||\hat{V}||_{s})$ is not less than

$\displaystyle g(\tilde{\delta}_{n})$
$\displaystyle=\frac{A(\tilde{a}\tilde{\delta}_{n})^{d^{2}}}{(1+\delta_{n})^{d/2}n^{d/2}}\exp\Bigl{(}\frac{\zeta
n\delta_{n}\tilde{a}\tilde{\delta}_{n}}{16}\Bigr{)}$
$\displaystyle=\frac{A(\tilde{a}\delta_{n})^{d^{2}}}{(1+\delta_{n})^{d/2}n^{d/2}d^{d^{2}/2}}\exp\Bigl{(}\frac{\zeta^{2}n\tilde{a}\delta_{n}^{2}}{16\sqrt{d}}\Bigr{)}$

for large $n$. Therefore, we have

$\displaystyle\frac{C_{J,n}(K)m_{n}(x^{n})}{p(x^{n}|\hat{\theta})}$ (52)
$\displaystyle\geq\frac{n^{-r}A\tilde{a}^{d^{2}}n^{d^{2}(-1/2+\gamma)}}{(1+\delta_{n})^{d/2}n^{d/2}d^{d^{2}/2}}\exp\Bigl{(}\frac{\zeta^{2}\tilde{a}n^{2\gamma}}{16\sqrt{d}}\Bigr{)},$

which diverges to infinity as $n$ goes to infinity. It means that the regret
for not bad sequences is negative and can be ignored. This completes the
proof.

##  VI Regret Bounds for Special Cases

In this section, employing the main theorems for general cases, we will show
asymptotic minimax bounds on regret of some special models: exponential
families, curved exponential families, models with hidden variables including
mixture families (with fixed components), and contaminated Gaussian location
families. Concerning the mixture families, we show a stronger upper bound than
that obtained by Theorem 5, that is, we show that the same form of the
asymptotic upper bound is valid without restricting the strings to
$\mathcal{K}$.

In the first subsection below, we describe the formal definition of
exponential families and review their basic properties. In the remaining
subsections, we discuss regret bounds for each example.

###  VI-A Definition of Exponential Families

Define the exponential family, following [12, 2]. [Exponential Family] Given
Borel measurable functions $T:{\cal X}\rightarrow\Re^{d}$ and $U:{\cal
X}\rightarrow\Re$, define the natural parameter space

$\Theta=\Bigl{\\{}\theta\in\Re^{d}:\int_{{\cal X}}\exp\bigl{(}\theta\cdot
T(x)+U(x))\nu(dx)<\infty\Bigr{\\}}$

a subset of $\Re^{d}$, assumed to have a non-empty interior $\Theta^{\circ}$.
Define $\psi(\theta)=\log\int_{\cal X}\exp(\theta\cdot T(x)+U(x))\nu(dx)$ and
a probability density on ${\cal X}$ with respect to $\nu$ by

$p(x|\theta)=\exp\bigl{(}\theta\cdot T(x)-\psi(\theta)+U(x)\bigr{)}.$

Let $K$ denote a subset of $\Theta$ such that $\bar{K}=\bar{K^{\circ}}$. We
refer to the set $S(K)=\\{p(x|\theta):\theta\in K\\}$ as an exponential family
of densities on ${\cal X}$.

The class of exponential families includes many common statistical models such
as Gaussian, Poisson, Bernoulli sources and so on. The following familiar case
expresses how the Gaussian family is an exponential family. [Gaussian
distributions] Let ${\cal X}=\Re$ and $\nu(dx)$ be the Lebesgue measure $dx$.
The density of $N(\mu,\sigma^{2})$ is

$\displaystyle\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp\Bigl{(}-\frac{(x-\mu)^{2}}{2\sigma^{2}}\Bigr{)}$
$\displaystyle=\exp\bigl{(}\frac{\mu
x}{\sigma^{2}}-\frac{x^{2}}{2\sigma^{2}}-\frac{\mu^{2}}{2\sigma^{2}}-\frac{\log(2\pi\sigma^{2})}{2}\Bigr{)}.$

Let $\theta=(\mu/\sigma^{2},-1/(2\sigma^{2}))$, $T(x)=(x,x^{2})$, $U(x)=0$ and
$\psi(\theta)=\mu^{2}/(2\sigma^{2})+(1/2)\log(2\pi\sigma^{2})$. Then, we see
that the Gaussian is an exponential family, where
$\Theta=\Re\times(-\infty,0)$.

Hereafter, we absorb the factor $\exp(U(x))$ into the reference measure
$\nu(dx)$ (that is, we change $\exp(U(x))\nu(dx)$ to $\nu(dx)$).

It is known that $\Theta$ is a convex set. Let $\cal T$ denote the range of
$T(x)$ for $x$ in the support of $\nu$ and let $\overline{\mbox{conv}}({\cal
T}$) be the closure of its convex hull. We can assume that the model is
arranged to be full rank such that $\dim(\overline{\mbox{hull}}({\cal
T}))=\dim\Theta=d$ holds without loss of generality [12]. An exponential
family which satisfies this condition is said to be minimal. We assume
$S(\Theta)$ is minimal in this paper.

It is known that $\psi(\theta)$ is of class $C^{\infty}$ and strictly convex
on $\Theta^{\circ}$. We refer to $\theta$ as the natural parameter (or
$\theta$-coordinates). We define the expectation parameter (or
$\eta$-coordinates) as $\eta_{i}=E_{\theta}(T_{i}).$ It is known that the
function on $\Theta^{\circ}$ mapping $\theta\mapsto\eta$ is an injection and
of class $C^{\infty}$. Let ${\cal
H}=\\{\eta(\theta):\theta\in\Theta^{\circ}\\}$ be the range of this map. We
also assume that $S(\Theta)$ is steep: that is $E_{\theta}(|T(x)|)=\infty$
holds for any $\theta\in\Theta-\Theta^{\circ}$. It is known that ${\cal H}$ is
the interior of $\mbox{conv}({\cal T})$ for steep exponential families.
Further, if $\Theta$ is open, then $S(\Theta)$ is said to be regular. Note
that any regular family is steep automatically (vacuously) since
$\Theta-\Theta^{\circ}$ is empty.

Note that $\partial\psi/\partial\theta^{i}=E_{\theta}(T_{i}(x))=\eta_{i}$ and
$\partial^{2}\psi/\partial\theta^{j}\partial\theta^{i}=E_{\theta}((T_{i}(x)-\eta_{i})(T_{j}(x)-\eta_{j}))$
hold on $\Theta^{\circ}$. Here, this
$E_{\theta}((T_{i}(x)-\eta_{i})(T_{j}(x)-\eta_{j}))$ is the Fisher information
matrix with respect to $\theta$ denoted $J(\theta)$. We let $I(\eta)$ denote
the Fisher information matrix of $\eta$. This $I(\eta)$ is known to be the
inverse matrix of $J(\theta)$. It is known that $J(\theta)$ is strictly
positive definite in $\Theta^{\circ}$.

Given the string $x^{n}$, we have
$p(x^{n}|\theta)=\prod_{\tau=1}^{n}p(x_{\tau}|\theta)=\prod_{\tau=1}^{n}\exp(\theta\cdot
T(x_{\tau})-\psi(\theta))=\exp(n(\theta\cdot\bar{T}-\psi(\theta)))$, where

$\bar{T}=\bar{T}(x^{n})=\frac{\sum_{\tau=1}^{n}T(x_{\tau})}{n}.$

These yield

$\displaystyle\frac{\partial\log p(x^{n}|\theta)}{\partial\theta_{i}}$
$\displaystyle=n(\bar{T}_{i}-\eta_{i}),$ $\displaystyle\frac{\partial^{2}\log
p(x^{n}|\theta)}{\partial\theta_{i}\partial\theta_{j}}$
$\displaystyle=-nJ_{ij}(\theta).$ (53)

The latter implies that $\log p(x^{n}|\theta)$ is strictly concave in
$\Theta^{\circ}$, hence, the former implies that $\log p(x^{n}|\theta)$ takes
the unique maximum at $\eta=\bar{T}$ under the condition that $\bar{T}\in{\cal
H}$. Let $\hat{\eta}$ $=\hat{\eta}(x^{n})$ denote the maximum likelihood
estimate of $\eta$ given $x^{n}$. Then, we have
$\hat{\eta}(x^{n})=\bar{T}(x^{n})$ for $x^{n}$ with $\bar{T}(x^{n})\in{\cal
H}^{\circ}$. The identity (53) also implies

$\hat{J}(\theta,x^{n})=J(\theta)$

for all $\theta\in\Theta$ and for all $x^{n}$. Therefore, Assumptions 1,
$1^{\prime}$, 2, and $2^{\prime}$ hold for the natural parameter $\theta$ of
exponential familes.

For the expectation parameters $(\tilde{\eta},\eta)\in{\cal H}^{2}$,
corresponding to $p(\cdot|\theta)$ and $p(\cdot|\tilde{\theta})$, let
$D(\tilde{\eta}||\eta)$ denote the Kullback divergence from
$p(\cdot|\tilde{\theta})$ to $p(\cdot|\theta)$. Then, we have

$D(\tilde{\eta}||\eta)=E_{\tilde{\theta}}\Bigl{(}\log\frac{p(x|\tilde{\theta})}{p(x|\theta)}\Bigr{)}=\tilde{\theta}\cdot\tilde{\eta}-\psi(\tilde{\theta})-\theta\cdot\tilde{\eta}+\psi(\theta),$

We extend the domain ${\cal H}^{2}$ to $\Re^{d}\times{\cal H}$, following
[12]:

$\displaystyle D(\tilde{\eta}||\eta)$
$\displaystyle=\left\\{\begin{array}[]{ll}\displaystyle\lim_{\epsilon\rightarrow+0}\inf\\{D(\eta^{\prime}||\eta):\eta^{\prime}\in{\cal
H},|\tilde{\eta}-\eta^{\prime}|<\epsilon\\},\\\ \mbox{\hskip 85.35826ptfor
$(\tilde{\eta},\eta)\in\partial{\cal H}\times{\cal H}$,}\\\
\infty,\>\>\>\>\>\>\>\>\mbox{\hskip 54.06023ptfor
$(\tilde{\eta},\eta)\in\bar{\cal H}^{c}\times{\cal H}$},\end{array}\right.$

where $\partial{\cal H}$ is the boundary of $\cal H$ and $\bar{{\cal H}}^{c}$
is the complement of the closure.

We have the following relation between differentiation with respect to $\eta$
and differentiation with respect to $\theta$:

$\frac{\partial}{\partial\eta_{i}}=\sum_{j}\frac{\partial\theta_{j}}{\partial\eta_{i}}\frac{\partial}{\partial\theta_{j}}=\sum_{j}I_{ij}(\eta)\frac{\partial}{\partial\theta_{j}}.$

This holds for $\theta\in\Theta^{\circ}$ (equivalently for $\eta\in{\cal H}$).
Thus $\theta$ and $\psi(\theta)$ are infinitely differentiable with respect to
$\eta$ as well as with respect to $\theta$. Hence, $D(\tilde{\eta}||\eta)$ is
of class $C^{\infty}$ on ${\cal H}^{2}$.

The following is a large deviation inequality. Suppose that $\eta\in{\cal H}$.
Let $\Lambda$ be a closed half space of $\Re^{d}$ (i.e.
$\Lambda=\\{x\in\Re^{d}:x\cdot\xi\geq\gamma\\}$ for any specified
$\xi\in\Re^{d}$ and $\gamma\in\Re$). Then, the following inequality holds

$P_{\theta}(\bar{T}(x^{n})\in\Lambda)\leq\exp(-n\inf_{\tilde{\eta}\in\Lambda}D(\tilde{\eta}||\eta)).$

See [16, 12] for the proof.

###  VI-B Lower and Upper Bounds for Exponential Families

From Lemma VI-A, Assumptions 3 and 3’ hold. We continue to assume finiteness
of $C_{J}(K)$ (Assumption 4’). For the regular exponential families, all the
remaining assumptions for Lemmas 1 and 2 automatically hold. Hence, Lemmas 1
and 2 and Theorems 1 and 3 can be applied to show the desired lower bound
indeed holds for the maximin regret for regular exponential families.

Next, we consider the upper bound. For the natural parameter $\theta$ of
exponential families, $\hat{J}(\theta,x^{n})=J(\theta)$ holds for any
$\theta\in\Theta^{\circ}$ and for any $x^{n}$. Hence, if we use the natural
parameter, we do not need the fiber bundle of local exponential families to
obtain the asymptotic minimax regret. In fact, we can prove the following
theorem, where we suppose only Assumptions about $K$. ($K$ is compact, convex,
and included in $\Theta^{\circ}$.) Let
$S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a $d$-dimensional exponential
family. Let $K$ be a compact and convex subset of $\Theta^{\circ}$. Let
$m_{K,\epsilon_{n},n}$ be the same one as in Theorem 5. Then, the following
holds.

$\displaystyle\varlimsup_{n\rightarrow\infty}\Bigl{(}\sup_{x^{n}\in{\cal
K}}\log\frac{p(x^{n}|\hat{\theta})}{m_{K,\epsilon_{n},n}(x^{n})}$
$\displaystyle-\frac{d}{2}\log\frac{n}{2\pi}\Bigr{)}$ (55)
$\displaystyle\leq\log C_{J}(K).$

This theorem immediately follows from Lemmas 5 and 7, which hold in much
simpler forms then the original ones, since any string $x^{n}$ is in the good
set $G_{n,\delta}$ by the fact $\hat{J}(\theta,x^{n})=J(\theta)$,

###  VI-C Lower and Upper Bounds for Curved Exponential Families

As a more general case than exponential families, we consider curved
exponential families. It is defined as a surface in the natural parameter
space of an exponential family. If the surface is a hyperplane, the surface
forms an exponential family again. Hence, we are interested in cases that the
surface is curved. Below, we give a formal definition of curved exponential
families. [Curved Exponential Families] Let $S=\\{\bar{p}(\cdot|u):u\in{\cal
U}\\}$ be a $\bar{d}$-dimensional steep exponential family, where
$\bar{p}(x|u)=\exp(u\cdot T(x)-\psi(u))$ denotes the density with respect to a
measure $\nu(dx)$ and $u$ its natural parameter. Let $\Theta$ be an open
subset of $\Re^{d}$ ($d<\bar{d}$) and $\phi=(\phi_{1},\ldots,\phi_{\bar{d}})$
be a function from $\Theta$ to ${\cal U}$. Assume that $\phi$ is twice
continuously differentiable in $\Theta$ and that the Jacobian of $\phi$ is of
rank $d$ for every $\theta$ in $\Theta$. Further, we assume that $\phi$ is an
injection. Let $p(\cdot|\theta)=\bar{p}(\cdot|\phi(\theta))$. Then, the family
$M=\\{p(\cdot|\theta):\theta\in K\\}$ with densities

$p(x|\theta)=\exp(\phi(\theta)\cdot T(x)-\psi(\phi(\theta)))$

is referred to as a $d$-dimensional curved exponential family of densities
embedded in the exponential family $S$.

In the above definition, let $\eta$ denote the function which maps $u$ to the
corresponding expectation parameter of $S$, that is, $\eta(u)=\int
T(x)\bar{p}(x|u)\nu(dx)$.

For the curved exponential family $M$, the score function is

$\displaystyle\frac{\partial\log p(x|\theta)}{\partial\theta_{i}}$
$\displaystyle=\frac{\partial\phi(\theta)\cdot
T(x)}{\partial\theta_{i}}-\sum_{k}\frac{\partial\psi(\phi(\theta))}{\partial
u_{k}}\frac{\partial\phi_{k}(\theta)}{\partial\theta_{i}}$
$\displaystyle=\frac{\partial\phi(\theta)\cdot
T(x)}{\partial\theta_{i}}-\eta\cdot\frac{\partial\phi(\theta)}{\partial\theta_{i}}$
$\displaystyle=\frac{\partial\phi(\theta)\cdot(T(x)-\eta)}{\partial\theta_{i}}.$
(56)

Then, by the chain rule of differentiation, we have

$\displaystyle\frac{\partial^{2}\log
p(x|\theta)}{\partial\theta_{j}\partial\theta_{i}}$
$\displaystyle=\frac{\partial^{2}\phi(\theta)\cdot(T(x)-\eta)}{\partial\theta_{j}\partial\theta_{i}}-\sum_{k,l}\frac{\partial\phi_{l}(\theta)}{\partial\theta_{i}}\frac{\partial\eta_{l}}{\partial
u_{k}}\frac{\partial\phi_{k}(\theta)}{\partial\theta_{j}}$
$\displaystyle=\frac{\partial^{2}\phi(\theta)\cdot(T(x)-\eta)}{\partial\theta_{j}\partial\theta_{i}}-\sum_{k,l}\frac{\partial\phi_{l}(\theta)}{\partial\theta_{i}}\bar{J}_{kl}(u)\frac{\partial\phi_{k}(\theta)}{\partial\theta_{j}},$
(57)

where $\bar{J}_{kl}(u)$ is the Fisher information matrix of the exponential
family $S$. Taking the expected value, we have

$-J_{ij}(\theta)=-\sum_{k,l}\frac{\partial\phi_{l}(\theta)}{\partial\theta_{i}}\bar{J}_{kl}(u)\frac{\partial\phi_{k}(\theta)}{\partial\theta_{j}}.$

By this we have confirmed that the Fisher information exists and is finite.
Further, since $\phi$ is twice continuously differentiable and its Jacobian is
of rank $d$ for every $\theta\in\Theta$, the Fisher information is continuous
and is positive definite for all $\theta\in\Theta$. (That is, Assumption 2
holds.) Further (57) yields

$\displaystyle\hat{J}_{ij}(\theta,x)=J_{ij}(\theta)-\frac{\partial^{2}\phi(\theta)}{\partial\theta_{i}\partial\theta_{j}}\cdot(T(x)-\eta(\phi(\theta))).$
(58)

This shows how the empirical Fisher information differs from the Fisher
information in curved exponential families. Since $T(x)$ and its covariance
matrix with respect to $\bar{p}(\cdot|u)$ for all $u\in\mathcal{U}$ is finite,
Assumptions 1 and 1’ hold. Assumption 2’ also holds because of (56). Further,
note that the maximum likelihood estimator for curved exponential families is
consistent uniformly for $\theta\in K$, when $K$ is compact and interior to
$\Theta$. This can be easily confirmed by Lemma 9 (the large deviation
theorem). Hence, Lemmas 1 and 2 and Theorems 1 and 3 work for curved
exponential families and we have the validity of the desired lower bound.

Next, we consider the upper bound. By (58), we have

$\displaystyle\hat{J}_{ij}(\theta,x^{n})=J_{ij}(\theta)-\frac{\partial^{2}\phi(\theta)}{\partial\theta_{i}\partial\theta_{j}}\cdot(\bar{T}-\eta(\phi(\theta))).$
(59)

Let $H^{k}$ denote the Hessian of $\phi_{k}(\theta)$ (the Hessian of the $k$th
component of $\phi(\theta)$). Then we can write

$\displaystyle\hat{J}(\theta,x^{n})=J(\theta)-\sum_{k}(\bar{T}_{k}-\eta_{k}(\phi(\theta)))H^{k}(\theta).$
(60)

By this, we have

$\displaystyle
V(x^{n}|\theta)=-\sum_{k}(\bar{T}_{k}-\eta_{k}(\phi(\theta)))J_{\theta}^{-1/2}H^{k}(\theta)J_{\theta}^{-1/2}.$
(61)

Since the exponential moments of $T(x)$ exist for $u\in\mathcal{U}^{\circ}$ by
definition of the natural parameter space of exponential families, Assumption
7 holds for a certain $b>0$. Further, note that, if $T(x)$ is bounded, then
$\bar{T}(x^{n})$ is uniformly bounded for all $n$. Hence, if $T(x)$ is
bounded, the collection of functions $V(x^{n}|\theta)$,
$x^{n}\in\mathcal{X}^{n}$, $n=1,2,\ldots$ is equicontinuous uniformly for
$\theta\in K$. Then, Assumptions 8 to 11 hold. As for the ideal prior,
Assumption 9 does hold. That is, we can use Theorem 5, and the general minimax
strategy works. On the contrary, if $T(x)$ is not bounded, it is not clear
whether the assumptions hold or not.

However, to deal with such curved exponential families with unbounded $T(x)$,
we can establish another minimax strategy. In this alternative strategy, to
deal with the string $x^{n}$ whose empirical Fisher information differs from
the Fisher information, we mix in small measure component living in the full
$\bar{d}$-dimensional exponential family $S$ instead of the fiber bundle of
local exponential families.

Let $K$ be a compact set included in $\Theta^{\circ}$ such that
$\bar{K}=\bar{K^{\circ}}$. Let ${\cal U}_{c}$ be a compact set included in
${\cal U}^{\circ}$ such that ${\cal
U}_{c}^{\circ}\supset\\{\phi(\theta):\theta\in\bar{K}\\}$. Our asymptotic
minimax strategy is established in the following theorem. Note that we do not
assume the boundness of $T(x)$ here.

Let $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$ be a $d$-dimensional curved
exponential family of densities defined in Definition VI-C and let

$\displaystyle
m_{n}(x^{n})=(1-n^{-r})m_{K,\epsilon,n}(x^{n})+n^{-r}\int\bar{p}(x^{n}|u)w(u)du,$

where $w(u)$ is the uniform prior over $\mathcal{U}_{c}$. Then, the following
holds.

$\displaystyle\limsup_{n\rightarrow\infty}(\sup_{x^{n}\in\mathcal{K}}\log\frac{p(x^{n}|\hat{\theta})}{m_{n}(x^{n})}-\frac{d}{2}\log\frac{n}{2\pi})$
$\displaystyle\hskip 85.35826pt\leq\log C_{J}(K).$

Proof: Define a set of good strings:

$G_{n}=\\{x^{n}:\hat{\theta}\in
K\>\mbox{and}\>|\hat{\eta}-\eta(\phi(\hat{\theta}))|\leq\delta_{n}\\}$

(recall that $\eta$ denotes the expectation parameter and that
$\hat{\eta}=\bar{T}$), where we let $\delta_{n}=n^{-1/2+\gamma}$
($0<\gamma<1/2$). Define also

$G_{n}^{c}=\\{x^{n}:\hat{\theta}\in
K\>\mbox{and}\>|\hat{\eta}-\eta((\phi(\hat{\theta}))|>\delta_{n}\\}$

We can prove the usual asymptotic bound for regret when $x^{n}\in G_{n}$,
while for $x^{n}\in G_{n}^{c}$, it turns out that the regret of our strategy
becomes negative, that is, the code length becomes shorter than $-\log
p(x^{n}|\hat{\theta})$.

For $x^{n}\in G_{n}$, from (60) and the Cauchy-Schwartz inequality, we have
for each $(i,j)$,

$\displaystyle(\hat{J}_{ij}(\theta,x^{n})-J_{ij}(\theta))^{2}$
$\displaystyle\leq|\bar{T}-\eta(\phi(\theta))|^{2}\sum_{k}(H_{ij}^{k}(\theta))^{2}$
$\displaystyle\leq\delta_{n}^{2}\sum_{k}(H_{ij}^{k}(\theta))^{2}.$

Since $H^{k}(\theta)$ is continuous and $K$ is compact,
$\sum_{k}(H_{ij}^{k}(\theta))^{2}$ is bounded by a constant $C_{H,K}^{2}$.
Accordingly, for $x^{n}\in G_{n}$,

$\max_{ij}\max_{\theta\in K}|\hat{J}_{ij}(\theta,x^{n})-J_{ij}(\theta)|\leq
C_{H,K}\,\delta_{n}$

holds, which implies

$\max_{\theta\in K}||\hat{J}(\theta,x^{n})-J(\theta)||\leq
d\,C_{H,K}\delta_{n}.$

Therefore, uniformly over $x^{n}\in G_{n}$,

$\max_{\theta\in K}||\hat{J}(\theta,x^{n})-J(\theta)||_{s}\leq
d\,C_{H,K}\delta_{n}$

which means, for all unit vector $z$, we have

$\max_{\theta\in K}|z^{t}(\hat{J}(\theta,x^{n})-J(\theta))z|\leq
d\,C_{H,K}\delta_{n}.$

Since $J(\theta)$ is continuously differentiable, for $\epsilon>0$,

$\max_{\theta^{\prime}\in B_{\epsilon}(\theta)\cap K}\max_{\theta\in
K}|z^{t}(\hat{J}_{n}(\theta^{\prime})z-z^{t}J(\theta))z|\leq
d\,C_{H,K}\delta_{n}+O(\epsilon).$

Now since $\delta_{n}=n^{-1/2+\gamma}$, the right side is $O(\epsilon)$ for
$n\geq(1/\epsilon)^{2/(1-2\gamma)}$. Therefore, for such $n$, we have the
following two inequalities holding uniformly for $x^{n}\in G_{n}$ and
uniformly for all unit vectors $z$,

$\displaystyle\max_{\tilde{\theta}\in B_{\epsilon}(\hat{\theta})\cap
K}|z^{t}\hat{J}(\tilde{\theta},x^{n})z-z^{t}J(\hat{\theta})z|$
$\displaystyle\leq O(\epsilon)$

and

$\displaystyle|z^{t}\hat{J}(\hat{\theta},x^{n})z-z^{t}J(\hat{\theta})z|$
$\displaystyle\leq O(\epsilon).$

Since $z^{t}J(\hat{\theta}))z$ is lower bounded by a positive constant (even
when we take a minimum over all unit vectors $z$), for sufficiently small
$\epsilon$, the $z^{t}(\hat{J}(\hat{\theta},x^{n})z$ is also lower bounded by
a positive constant, uniformly over unit vectors $z$ and $x^{n}\in G_{n}$.
Consequently, for all $n\geq(1/\epsilon)^{2/(1-2\gamma)}$ and all $x^{n}\in
G_{n}$, we have

$\max_{\tilde{\theta}\in B_{\epsilon}(\hat{\theta})\cap
K}\frac{z^{t}\hat{J}(\tilde{\theta},x^{n})z}{z^{t}\hat{J}(\hat{\theta},x^{n})z}\leq
1+O(\epsilon).$

This is the last inequality in Assumption 9 and is sufficient to obtain the
same bound for good strings as in Theorem 5. To show that, we have the
condition that $\epsilon$ must converge to $0$ slower than $1/\sqrt{n}$. Now,
we face the new condition $\epsilon\geq\delta_{n}=n^{-1/2+\gamma}$, which does
not contradict the previous condition.

Next we consider $x^{n}\in G^{c}_{n}$. Let $N_{\delta}(u)$ denote the $\delta$
neighborhood of $u$ and let ${\cal U}_{c}^{\prime}$ a compact set included in
${\cal U}_{c}^{\circ}$. Now we will prove that the following holds for a
certain $\kappa>0$.

$\displaystyle\forall n\in\mathbb{N},\>\forall x^{n}\in
G_{n}^{c},\>\exists\tilde{u}\in{\cal U}_{c}^{\prime},\>$
$\displaystyle\inf_{u\in
N_{\kappa\delta_{n}}(\tilde{u})}\frac{1}{n}\log\frac{\bar{p}(x^{n}|u)}{p(x^{n}|\hat{\theta})}\geq
C_{2}\delta_{n}^{2}.$ (63)

Indeed, by Taylor expansion with respect to $u$ at $\phi(\hat{\theta})$, we
have

$\displaystyle\frac{1}{n}$
$\displaystyle\log\frac{\bar{p}(x^{n}|u)}{p(x^{n}|\hat{\theta})}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\log\frac{\bar{p}(x^{n}|u)}{\bar{p}(x^{n}|\phi(\hat{\theta}))}$
$\displaystyle=$
$\displaystyle(u-\phi(\hat{\theta}))\cdot\bar{T}-\psi(u)+\psi(\phi(\hat{\theta}))$
$\displaystyle=$
$\displaystyle(\bar{T}-\eta(\phi(\hat{\theta})))\cdot(u-\phi(\hat{\theta}))$
$\displaystyle-(1/2)(u-\phi(\hat{\theta}))^{t}\bar{J}(u^{\prime})(u-\phi(\hat{\theta})),$

where $u^{\prime}=\xi u+(1-\xi)\phi(\hat{\theta})$ for some $\xi\in[0,1]$. Let

$\tilde{u}=\phi(\hat{\theta})+2\kappa\delta_{n}\frac{\bar{T}-\phi(\hat{\theta}))}{|\bar{T}-\phi(\hat{\theta})|}.$

Then, for all $u\in N_{\kappa\delta_{n}}(\tilde{u})$, we have
$\kappa\delta_{n}\leq|u-\phi(\hat{\theta})|\leq 3\kappa\delta_{n}$. Hence, we
have

$\displaystyle\inf_{u\in
N_{\kappa\delta_{n}}(\tilde{u})}\frac{1}{n}\log\frac{\bar{p}(x^{n}|u)}{p(x^{n}|\hat{\theta})}$
$\displaystyle\geq$
$\displaystyle\kappa\delta_{n}^{2}-9\kappa^{2}\lambda^{*}\delta_{n}^{2}/2$
$\displaystyle=$
$\displaystyle\kappa(\delta_{n}^{2}-9\kappa\lambda^{*}\delta_{n}^{2}/2),$

where $\lambda^{*}$ denotes the maximum value among the maximum eigenvalues of
$\bar{J}(u)$ for $u\in\mathcal{U}_{c}$. Let $\kappa=1/9\lambda^{*}$, then the
above implies (63). Hence we have for all $n\in\mathbb{N}$ and for all
$x^{n}\in G_{n}^{c}$,

$\displaystyle\frac{n^{-r}\int\bar{p}(x^{n}|u)w(u)du}{p(x^{n}|\hat{\theta})}$
$\displaystyle\geq\int_{N_{\kappa\delta_{n}}(\tilde{u})}\frac{n^{-r}\bar{p}(x^{n}|u)w(u)}{p(x^{n}|\hat{\theta})}du$
$\displaystyle\geq
C_{3}n^{-r}\int_{N_{\kappa\delta_{n}}(\tilde{u})}\exp(C_{2}n\delta_{n}^{2})du$
$\displaystyle\geq
C_{3}n^{-r}{(\kappa\delta_{n})^{\bar{d}}}\exp(C_{2}n\delta_{n}^{2})$
$\displaystyle\geq C_{4}{n^{-r}n^{-\bar{d}/4}}\exp(C_{2}n^{2\gamma}).$

This means that the regret of $m_{n}$ is negative for all large $n$ and can be
ignored. This completes the proof.

Lastly we give a comment about the case of stochastic processes. Though
Theorem VI-C above is for the i.i.d. case only, it can be extended to the case
of Markov sources. It is known that some parametric model of Markov sources
approaches an exponential family as $n$ goes to infinity, in the sense that
the difference between Fisher and empirical Fisher information matrices
converges to zero as $n$ goes to infinity. We call the model of stochastic
processes with that condition as an asymptotic exponential family. In
particular, the Markov model defined by a context tree [48] (a tree model) is
interesting. When the context tree satisfies a certain condition, the model is
called a finite state machine X (FSMX) model [49]. It is shown that the tree
model is an asymptotic exponential family if and only if the model is an FSMX
model [45].

As a special case, consider the model of $k$th order Markov chains, which is
an example of an FSMX model. For this case, it has been shown that the
Jeffreys mixture asymptotically achieves the minimax regret [44]. Note that
any tree model can be regarded as a sub family (a surface) of the model of a
certain order Markov chains. It means that a tree model can be regarded as a
curved exponential family embedded in an asymptotic exponential family. It
suggests that we can establish a similar theorem as Theorem VI-C concerning
tree models. In fact, such a theorem is in [42].

###  VI-D Lower and Upper Bounds for Models with Hidden Variables

The contents of this section was presented in part in 2014 IEEE International
Symposium on Information Theory [41].

First we introduce the notion of models with hidden variables below, where
$(\mathcal{Y},\mathcal{B}_{y},\nu_{y})$ is a measurable space. [Model with
Hidden Variables] Let $q(y|\theta)$ be a density of a $d$-dimensional
exponential family over $\mathcal{Y}$ with natural parameter $\theta$. Define
a class $S$ of probability density functions over $\mathcal{X}$ by

$\displaystyle
S=\Bigl{\\{}p(x|\theta)=\int\\!\\!\kappa(x|y)q(y|\theta)\nu_{y}(dy)\;\colon\;\theta\in\Theta\Bigr{\\}},$
(64)

where $\kappa(x|y)$ is a fixed conditional probability density function of $x$
given $y$. Then, $S$ is called a model with a hidden variable $y$.

For the above definition, we will assume that the Fisher information is
positive definite over $\Theta^{\circ}$. (Assumption 2.) Whether this holds or
not depends on the property of $\kappa(x|y)$. Later we will see that if $x$
and $y$ are not independent random variables with respect to the joint density
$\kappa(y|x)q(y|\theta)$, then $J(\theta)$ is positive definite. This is
reasonable because we can draw information about $\theta$ from $x$, if $x$ and
$y$ are not independent.

If $q(y|\theta)$ is the multinomial model over the finite set
$\mathcal{Y}=\\{0,1,\ldots,d\\}$, then $p(x|\theta)$ is in the following form:

$\displaystyle
p(x|\theta)=\sum_{y=1}^{d}\theta_{y}\kappa(x|y)+\Bigl{(}1-\sum_{y=1}^{d}\theta_{y}\Bigr{)}\kappa(x|0).$
(65)

Here, $\theta$ denotes a $d$-dimensional vector
$(\theta_{1},\ldots,\theta_{d})\in\Re^{d}$ satisfying
$0\leq\sum_{i=1}^{d}\theta_{i}\leq 1$ and $\theta_{i}\geq 0$ for all $i$. This
model is called a mixture family in information geometry [2, 3]. The mixture
family is the dual object of the exponential family in information geometry
[2, 3]. Note that this mixture family is a simpler object than the more
general class of mixture models such as Gaussian mixtures, binomial mixtures,
etc., which are used in many settings.

Typically, models with a hidden variable are examples of non exponential
families. But note that if it is the mixture family and if ${\cal X}$ is a
finite subset of an Euclidean space and each $\kappa(\cdot|y)$ is a point mass
at an $x=x_{y}$ in ${\cal X}$, then it is also an exponential family. That is
the case of the multinomial Bernoulli model.

In this section we first argue the general case of models with hidden
variables, assuming $T(y)$ is bounded, for which Theorem 5 gives the minimax
solution for the set of strings $\mathcal{K}=\mathcal{X}^{n}(K)$ for a compact
$K$ interior to $\Theta$.

After that, for the mixture family case, we show a minimax strategy for the
problem without restriction to the set of strings $\mathcal{X}^{n}$. The shown
strategy is different from the one used in Theorem 1.

####  VI-D1 Lower Bound for Models with Hidden Variables

Here, we consider the lower bound. We examine Assumptions for Theorems 1 and
2. Here, we assume $\theta$ in $q(y|\theta)$ is the natural parameter of
exponential family $q(y|\theta)$:

$q(y|\theta)=\exp(\theta\cdot T(y)-\psi(\theta)).$

Below, let $\eta$ denote the expectation parameter: $\eta=\int
T(y)q(y|\theta)\nu_{y}(dy)$ and let $G(\theta)$ denote the Fisher information
matrix for $q(y|\theta)$ with respect to $\theta$.

We will show some nice properties of the score function, the Fisher
information, and the empirical Fisher information. Let ${\rm
Cov}_{\theta}[\bar{T}(Y^{n})|x^{n}]$ denote the covariance matrix of
$\sqrt{n}\bar{T}(y^{n})$ with respect to the conditional probability
distribution $p(y^{n}|x^{n},\theta)$ with a fixed $x^{n}$, where
$\bar{T}=\sum_{t=1}^{n}T(y_{t})/n$. Further, define

${\rm Cov}_{\theta}[T(Y)|X]=\int{\rm
Cov}_{\theta}[\bar{T}(Y)|x]p(x|\theta)\nu(dx).$

Then, we have the following lemma. For the model with hidden variable (64),
the following equalities hold.

$\displaystyle\frac{1}{n}\frac{\partial\log
p(x^{n}|\theta)}{\partial\theta_{i}}$ $\displaystyle=\tilde{t}_{i}-\eta_{i},$
(66) $\displaystyle\hat{J}(\theta,x^{n})$ $\displaystyle=G(\theta)-\,{\rm
Cov}_{\theta}[\bar{T}(Y^{n})|x^{n}],$ (67) $\displaystyle J(\theta)$
$\displaystyle=G(\theta)-{\rm Cov}_{\theta}[T(Y)|X]$ (68)

and

$\frac{\partial\hat{J}_{ij}(\theta,x^{n})}{\partial\theta_{k}}=\frac{\partial
G_{ij}(\theta)}{\partial\theta_{k}}-\sqrt{n}\tilde{w}_{ijk}(\theta,x^{n}),$

where

$\displaystyle\tilde{t}_{i}$
$\displaystyle=\tilde{t}_{i}(\theta,x^{n})=\int\bar{T}(y^{n})p(y^{n}|x^{n},\theta)\nu_{y}(dy^{n})$

and

$\displaystyle\tilde{w}_{ijk}$ $\displaystyle=\tilde{w}_{ijk}(\theta,x^{n})$
$\displaystyle=n^{3/2}\int(\bar{T}_{i}-\tilde{t}_{i})(\bar{T}_{j}-\tilde{t}_{j})(\bar{T}_{k}-\tilde{t}_{k})p(y^{n}|x^{n},\theta)\nu_{y}(dy^{n}).$

Proof: Note that

$\displaystyle\frac{\partial
p(x^{n}|\theta)}{\partial\theta_{i}}=\int\kappa(x^{n}|y^{n})n(\bar{T}_{i}-\eta_{i})q(y^{n}|\theta)\nu(dy^{n}).$
(69)

Hence, we have

$\displaystyle\frac{\partial\log p(x^{n}|\theta)}{\partial\theta_{i}}$
$\displaystyle=\frac{\int\kappa(x^{n}|y^{n})n(\bar{T}_{i}-\eta_{i})q(y^{n}|\theta)\nu(dy^{n})}{p(x^{n}|\theta)}$
(70) $\displaystyle=\int
n(\bar{T}_{i}-\eta_{i})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle=n(\tilde{t}_{i}-\eta_{i}),$

where
$p(y^{n}|x^{n},\theta)=\kappa(x^{n}|y^{n})q(y^{n}|\theta)/p(x^{n}|\theta)$.
This yields (66). To further differentiate, we need
$(\partial/\partial\theta_{i})p(y^{n}|x^{n},\theta)$. By the product rule of
differentiation

$\displaystyle\frac{\partial p(y^{n}|x^{n},\theta)}{\partial\theta_{i}}$
$\displaystyle=$