# Minimum Excess Risk in Bayesian Learning

Aolin Xu  Maxim Raginsky

###### Abstract

We analyze the best achievable performance of Bayesian learning under
generative models by defining and upper-bounding the minimum excess risk
(MER): the gap between the minimum expected loss attainable by learning from
data and the minimum expected loss that could be achieved if the model
realization were known. The definition of MER provides a principled way to
define different notions of uncertainties in Bayesian learning, including the
aleatoric uncertainty and the minimum epistemic uncertainty. Two methods for
deriving upper bounds for the MER are presented. The first method, generally
suitable for Bayesian learning with a parametric generative model, upper-
bounds the MER by the conditional mutual information between the model
parameters and the quantity being predicted given the observed data. It allows
us to quantify the rate at which the MER decays to zero as more data becomes
available. Under realizable models, this method also relates the MER to the
richness of the generative function class, notably the VC dimension in binary
classification. The second method, particularly suitable for Bayesian learning
with a parametric predictive model, relates the MER to the minimum estimation
error of the model parameters from data. It explicitly shows how the
uncertainty in model parameter estimation translates to the MER and to the
final prediction uncertainty. We also extend the definition and analysis of
MER to the setting with multiple model families and the setting with
nonparametric models. Along the discussions we draw some comparisons between
the MER in Bayesian learning and the excess risk in frequentist learning.

<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
    1. 1.1 Overview of the presentation
    2. 1.2 Relation to existing works
      1. 1.2.1 Accumulated excess risk for log loss
      2. 1.2.2 Convergence of posterior distribution
      3. 1.2.3 PAC-Bayes
    3. 1.3 A note on notation
  2. 2 Model and definitions
    1. 2.1 Bayesian learning under parametric generative model
    2. 2.2 A data processing inequality for Bayes risk
    3. 2.3 Definition of minimum excess risk
  3. 3 Upper bounds via conditional mutual information
    1. 3.1 Logarithmic loss
    2. 3.2 Quadratic loss
    3. 3.3 Zero-one loss
    4. 3.4 General loss functions
    5. 3.5 Realizable models and connection to VC dimension
  4. 4 Upper bounds via functional and distributional continuities
    1. 4.1 Via continuity of optimal omniscient decision rule
      1. 4.1.1 General upper bound
        1. Example: constant $\Psi^{*}$
        2. Example: logistic regression
      2. 4.1.2 Realizable models with additive noise
        1. Example: linear regression
    2. 4.2 Deviation of posterior predictive distribution from true predictive model
    3. 4.3 From deviation of posterior predictive distribution to MER bound
      1. 4.3.1 Via conditional mutual information upper bound
      2. 4.3.2 Via continuity of generalized entropy
        1. Classification
        2. Regression
      3. 4.3.3 Examples
        1. Logistic regression (continued)
        2. Nonlinear and linear regression (continued)
  5. 5 Extensions
    1. 5.1 Multiple model families
    2. 5.2 MER in nonparametric models
  6. 6 Discussion
    1. 6.1 Tightness and utility of the results
    2. 6.2 MER in Bayesian learning vs. excess risk in frequentist learning
  7. A Miscellaneous lemmas
    1. A.1 Regularity conditions for (30)
    2. A.2 A transportation inequality
    3. A.3 Series with growth rate $\log n$
    4. A.4 Convexity of $\mathcal{W}_{p}^{p}(P,Q)$
    5. A.5 Lipschitz continuity of multivariate function
    6. A.6 Proof of Lemma 3
    7. A.7 Proof of Lemma 5
  8. B MER upper bound for linear regression based on Theorem 6
  9. C Proof of Theorem 15

##  1 Introduction

Bayesian learning under generative models has been gaining considerable
attention in recent years as an alternative to the frequentist learning. In
the Bayesian setting, the observed data
$Z^{n}=((X_{1},Y_{1}),\ldots,(X_{n},Y_{n}))$ is modeled as conditionally
i.i.d. samples generated from a probabilistic model given the model
realization $P_{Z|W}$, while the model is treated either as a random element
of some parametric model family drawn according to a prior distribution of the
model parameters $W$, or as a nonparametric random process [1]. The task of
Bayesian learning is to predict a quantity of interest $Y$ based on the
observed data $(X,Z^{n})$ and the structure of the model, while the quality of
prediction can be assessed by the expected loss with respect to some loss
function $\mathbf{E}[\ell(Y,\psi(X,Z^{n}))]$. Although Bayesian learning often
relies on posterior sampling or approximation techniques [2, 3] and hence has
much higher computational complexity than its frequentist counterpart, the
Bayesian viewpoint has many attractive features, e.g., reducing overfitting
[4], quantifying uncertainty in making predictions [5, 6, 7], enabling model
compression [8], etc. In contrast with the growing attention to the
algorithmic side of Bayesian learning, its performance analysis is relatively
scarce compared to the volume of literature on the theoretical analysis of
frequentist learning. In this paper, we set aside the computational issues in
Bayesian learning and focus on analyzing its best achievable performance under
the generative model with respect to general loss functions.

###  1.1 Overview of the presentation

In Section 2, we define the minimum excess risk (MER) in Bayesian learning as
the gap between the Bayes risk $R_{\ell}(Y|X,Z^{n})$, defined as the minimum
expected loss attainable by learning from the data, and its fundamental limit
$R_{\ell}(Y|X,W)$, defined as the minimum expected loss that would be achieved
if the model parameters were known. The MER is an algorithm-independent
quantity that captures the uncertainty arising from the lack of knowledge of
the underlying model parameters, commonly known as epistemic uncertainty. Its
value and rate of convergence to zero reflect the difficulty of the learning
problem. The decomposition of the Bayes risk into its fundamental limit and
MER also provides rigorous definitions of the aleatoric uncertainty and the
minimum epistemic uncertainty in Bayesian learning, the quantification of
which has become an important research topic in recent years [9, 10, 11]. To
the authors’ knowledge, the general definition of MER is new, and has not been
systematically studied before.

We then present two methodologies for deriving upper bounds on the MER. We
first show in Section 3 that, under a generic parametric generative model and
for a wide range of loss functions, the MER can be upper-bounded in terms of
the conditional mutual information between the model parameters and the
quantity being predicted given the observed data, $I(W;Y|X,Z^{n})$. This leads
to asymptotic upper bounds on the MER that scale as $O({d}/{n})$ or
$O({\sqrt{{d}/{n}}})$ depending on the loss function, where $d$ is the
dimension of the parameter space and $n$ is the data size. It also reveals an
MER-information relationship in Bayesian learning, echoing the generalization-
information relationship in frequentist learning [12]. Under realizable
models, it is shown that for any bounded loss function, the MER for binary
classification scales as $O(d/n)$, where $d$ is the VC dimension of the
generative function class. Next, in Section 4, we explore two alternative
methods for bounding the MER. One relies on the smoothness of the decision
rule in the model parameters, while the other relies on the smoothness of the
minimum expected loss as a functional of the predictive model. The resulting
upper bounds single out the dependence of the MER on the minimum achievable
estimation error of the model parameters from the data, e.g., on the minimum
mean square error (MMSE) of the estimated model parameters $R_{2}(W|X,Z^{n})$.
It explicitly shows how the difficulty of model parameter estimation
translates into the difficulty of prediction due to the model uncertainty.

The analysis of the MER in the single model family setting can be extended to
the setting with multiple model families. The definition of MER can also be
extended to the setting with nonparametric generative models, such as Gaussian
processes, and the analysis of MER based on conditional mutual information
carries over to this setting. These extensions are briefly discussed in
Section 5. We close by summarizing the results and making some comparisons
between the MER in Bayesian learning and the excess risk in frequentist
learning in Section 6.

###  1.2 Relation to existing works

####  1.2.1 Accumulated excess risk for log loss

The closest connection between this work and prior literature is the MER for
the logarithmic (log) loss defined in this paper and the accumulated excess
risks for the log loss defined in Bayesian universal source coding [13],
Bayesian sequential prediction [14], Bayesian density estimation [15], and
Bayesian supervised learning [16], all of which turn out to be the mutual
information between the model parameters and the observed data, and are
achieved by the posterior predictive distribution as a soft predictor. The
only work where more general loss functions is considered is the study of
sequential prediction in [14], where an upper bound on the accumulated excess
risk for bounded loss functions is derived. Our definition of MER goes beyond
the log loss to general loss functions, which can be unbounded, and the MER in
general is achieved not necessarily by the posterior predictive distribution,
but by some hard predictor according to the loss function. In Section 3 we
show that the MER for the log loss is nevertheless an important quantity, as
it can be used to upper-bound the MER for many other loss functions. Most of
the above works, with the exception of [16], considered only unsupervised
learning, while our results hold for both supervised and unsupervised
learning. In addition, the MER defined in this work is the instantaneous
excess risk, instead of the accumulated risk studied in above works, thus is
amenable to more refined analyses. Another closely related work that
considered both supervised learning and instantaneous risk is [17], where the
Bayes risk of binary classification with the zero-one loss is derived by
relating it to the accumulated log loss, and is further related to the VC
dimension of the generative function class. As only realizable models are
considered in [17], the Bayes risk there is equal to the MER. In Section 3.5,
we also study the MER under realizable models, but our results go beyond
binary classification and the zero-one loss.

####  1.2.2 Convergence of posterior distribution

A classical frequentist analysis of Bayesian inference is the convergence of
the _posterior parameter distribution_ to the true model parameters, assuming
the data is sampled from some _fixed_ model with the true parameters [18, 19,
20]. This analysis has recently been extended to deep neural network models
[21]. The convergence of the _posterior predictive distribution_ has also been
studied under the same assumption [22]. The main difference between these
works and ours is the assumption on the data distribution. In our work, the
underlying data distribution considered in the performance analysis stays the
same as the generative model based on which the optimal predictor, or the
learning algorithm, is derived. In other words, the model parameters are
assumed to be randomly drawn from the prior, and the data samples are drawn
from the model given the model parameters. In addition, rather than the
convergence of the posterior of the model parameters, we are interested in the
accuracy of the predicted quantity of interest. In Section 4 we reveal how
this accuracy explicitly depends on the accuracy of the model parameter
estimation, by studying the expected deviation of the posterior predictive
distribution from the random true model.

####  1.2.3 PAC-Bayes

Another loosely related line of work in statistical learning is the PAC-Bayes
framework in the frequentist setting [23, 24, 25] and its extension as the
Bayes mixture model [26]. The main difference between the Bayesian setting
considered here and the PAC-Bayes framework is again the underlying data
distribution. For the former, the data distribution is restricted to a
parametric or nonparametric family of generative models with the data samples
being _conditionally_ i.i.d. given the model realization, and there is
virtually no restriction on candidate predictors. For the latter, the data
samples are drawn unconditionally i.i.d. according to a completely unknown
distribution, and the hypothesized Bayes-like update takes place in a
hypothesis space consisting of admissible predictors only. The excess risk
studied in this paper is thus not directly related to the generalization error
or excess risk in the PAC-Bayes method. Nevertheless, the MER-information
relationship in Theorem 6 is an interesting analogue of the generalization-
information relationship in the frequentist setting [12, Theorem 1] that leads
to an information-theoretic derivation of the PAC-Bayes algorithm.

###  1.3 A note on notation

Throughout the paper, random variables are denoted by uppercase letters and
their realizations are in the corresponding lowercase letters. To keep the
notation uncluttered, we may use $K_{U|v}$, $P_{U|v}$ and $\mathbf{E}[U|v]$
respectively to denote the probability transition kernel $K_{U|V=v}$, the
conditional distribution $P_{U|V=v}$ and the conditional expectation
$\mathbf{E}[U|V=v]$. When the conditioning variables are written in uppercase
letters, these quantities are random, and expectations can be taken with
respect to the conditioning variables. Throughout the paper, $D(\cdot,\cdot)$
denotes a generic statistical distance, while the KL divergence is denoted by
$D_{\rm KL}(\cdot\|\cdot)$. All probability spaces considered in this paper
are Borel spaces, and all functions are measurable functions. We use natural
logarithms throughout the paper.

##  2 Model and definitions

###  2.1 Bayesian learning under parametric generative model

The basic task in supervised learning is to construct an accurate predictor of
$Y$, a quantify of interest, given an observation $X$, where the knowledge of
the joint distribution of $X$ and $Y$ is vague but can be inferred from a
historical dataset $((X_{1},Y_{1}),\ldots,(X_{n},Y_{n}))$. In the _model-based
learning_ framework, a.k.a. learning under a _generative model_ , the joint
distribution of $X$ and $Y$ is assumed to be an element of a known model
family. The model family can be either parametric or nonparametric. We focus
on the parametric case in this work, and defer a brief discussion on the
nonparametric case to Section 5.2. In the case of parametric modeling, the
model family is a collection of parametrized distributions
${\mathcal{M}}=\\{P_{X,Y|w},w\in{\mathsf{W}}\\}$, where $w$ represents the
vector of unknown model parameters belonging to some space ${\mathsf{W}}$.
Under the _Bayesian formulation_ , the vector of model parameters $W$ is
itself treated as a random quantity with a prior distribution $P_{W}$, while
the data samples are conditionally i.i.d. given $W$. Formally, the model
parameters $W$, the data samples $Z^{n}\mathrel{\mathop{\mathchar
58\relax}}=(Z_{1},\ldots,Z_{n})$ with $Z_{i}\mathrel{\mathop{\mathchar
58\relax}}=(X_{i},Y_{i})$, $i=1,\ldots,n$, and the pair $Z=(X,Y)$ consisting
of the fresh observation $X$ and the quantity $Y$ to be predicted are assumed
to be generated according to the joint distribution

$\displaystyle
P_{W,Z^{n},Z}=P_{W}\Big{(}\prod\limits_{i=1}^{n}P_{Z_{i}|W}\Big{)}P_{Z|W},$
(1)

where $P_{Z_{i}|W}=P_{Z|W}$ for each $i$. As an example of the above model,
the _predictive modeling_ framework, a.k.a. probabilistic discriminative model
[1], further assumes that $P_{Z|W}$ factors as $P_{Z|W}=P_{X|W}K_{Y|X,W}$,
with some probability transition kernel $K_{Y|X,W}$ directly describing the
true predictive distribution of the quantity of interest given the observation
and model parameters. It is often further assumed that $X$ is independent of
$W$ under the predictive modeling framework. Note that the above models and
the following definitions encompass the unsupervised learning problem as well,
where one just ignores the observations $(X^{n},X)$ so that $Z_{i}=Y_{i}$ and
$Z=Y$.

Under the generative model (1), the Bayesian learning problem can be phrased
as a Bayes decision problem of predicting $Y$ based on $X$ and the labeled
observations $Z^{n}$. Given an action space ${\mathsf{A}}$ and a loss function
$\ell\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{Y}}\times{\mathsf{A}}\rightarrow\mathbb{R}$, a decision
rule $\psi\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{Z}}^{n}\rightarrow{\mathsf{A}}$ that maps
observations to an action is sought to make the expected loss
$\mathbf{E}[\ell(Y,\psi(X,Z^{n}))]$ small. A decision rule that minimizes the
expected loss among all decision rules is called a _Bayes decision rule_. The
corresponding minimum expected loss is defined as the _Bayes risk_ in Bayesian
learning:

######  Definition 1.

In Bayesian learning, the Bayes risk with respect to a loss function $\ell$ is
defined as

$\displaystyle R_{\ell}(Y|X,Z^{n})\mathrel{\mathop{\mathchar
58\relax}}=\inf_{\psi\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{Z}}^{n}\rightarrow{\mathsf{A}}}\mathbf{E}[\ell(Y,\psi(X,Z^{n}))],$
(2)

where the infimum is taken over all decision rules such that the above
expectation is defined.

###  2.2 A data processing inequality for Bayes risk

To better understand the definition of $R_{\ell}(Y|X,Z^{n})$, we give a brief
review of the general definition of the Bayes risk and prove a useful property
of it. Given a random element $Y$ of ${\mathsf{Y}}$, the quantity

$\displaystyle R_{\ell}(Y)\mathrel{\mathop{\mathchar
58\relax}}=\inf_{a\in{\mathsf{A}}}\mathbf{E}[\ell(Y,a)]$ (3)

is known as the Bayes envelope [14] or the generalized entropy [27] of $Y$.
Given a random element $V$ of some space ${\mathsf{V}}$ jointly distributed
with $Y$, the general definition of the _Bayes risk_

$\displaystyle R_{\ell}(Y|V)\mathrel{\mathop{\mathchar
58\relax}}=\inf_{\psi\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{V}}\rightarrow{\mathsf{A}}}\mathbf{E}[\ell(Y,\psi(V))]$ (4)

is the minimum expected loss of predicting $Y$ given $V$. It can be expressed
as the expectation of the conditional Bayes envelope
$R_{\ell}(Y|V=v)\mathrel{\mathop{\mathchar
58\relax}}=\inf_{a\in{\mathsf{A}}}\mathbf{E}[\ell(Y,a)|V=v]$ with respect to
$V$, as
$R_{\ell}(Y|V)=\int_{\mathsf{V}}P_{V}(\operatorname{d\\!}v)R_{\ell}(Y|V=v).$
The Bayes risk $R_{\ell}(Y|V)$ can thus be viewed as a generalized conditional
entropy of $Y$ given $V$ [28, 29]. The following lemma states that the Bayes
risk satisfies a _data processing inequality_.

######  Lemma 1.

Suppose the random variables $U$, $V$ and $Y$ form a Markov chain $U-V-Y$; in
other words, $Y$ and $U$ are conditionally independent given $V$. Then, for
any loss function $\ell$, the Bayes risk of predicting $Y$ from $U$ is at
least as large as the Bayes risk of predicting $Y$ from $V$, i.e.,

$\displaystyle R_{\ell}(Y|U)\geq R_{\ell}(Y|V).$ (5)

###### Proof.

Let $\psi$ be a Bayes decision rule for predicting $Y$ from $U$. Upon
observing $V$, a random variable $U^{\prime}$ can be sampled from $P_{U|V}$,
conditionally independent of $(U,Y)$ given $V$. Then $\psi(U^{\prime})$ serves
as a randomized prediction of $Y$ from $V$. As all probability spaces under
consideration are Borel spaces, the sampling of $U^{\prime}$ conditional on
$V$ can be realized by a function $f\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{V}}\times[0,1]\rightarrow{\mathsf{U}}$ of $V$ and an
independent random variable $T$ uniformly distributed on $[0,1]$, such that
$P_{f(V,T)|V}=P_{U|V}$ [30, Lemma 3.22]. We have

$\displaystyle R_{\ell}(Y|V)$
$\displaystyle\leq\inf_{t\in[0,1]}\mathbf{E}[\ell(Y,\psi(f(V,t)))]$ (6)
$\displaystyle\leq\mathbf{E}[\ell(Y,\psi(f(V,T)))]$ (7)
$\displaystyle=\mathbf{E}[\ell(Y,\psi(U^{\prime}))]$ (8)
$\displaystyle=\mathbf{E}[\ell(Y,\psi(U))]$ (9) $\displaystyle=R_{\ell}(Y|U)$
(10)

where (6) is due to the definition of $R_{\ell}(Y|V)$ and the fact that
$\psi(f(\cdot,t))$ is a map from ${\mathsf{V}}$ to ${\mathsf{Y}}$ for each
$t\in[0,1]$; (7) follows from the independence between $T$ and $(V,Y)$; (9)
follows from the fact that $P_{U^{\prime}|V}=P_{U|V,Y}$ due to the Markov
chain $U-V-Y$, hence $P_{U^{\prime},V,Y}=P_{U,V,Y}$; and (10) follows from the
definition of $\psi$. ∎

In view of the definition of $\mu$-entropy in (14) and (15) in Section 3.1,
the classic data processing inequality for mutual information stating that
$I(U;Y)\leq I(V;Y)$ in a Markov chain $U-V-Y$ [31] can be derived from Lemma 1
applied to the log loss. More importantly, Lemma 1 extends the _value of
information principle_ in Bayes decision making [28], which states that
$R_{\ell}(Y)\geq R_{\ell}(Y|V)$, as it can be viewed as a special case of
Lemma 1 when $U$ is independent of $(V,Y)$. Lemma 1 also extends the
_principle of total evidence_ [32], a.k.a. the _value of knowledge theorem_
[33], which states that $R_{\ell}(Y|V_{1})\geq R_{\ell}(Y|V_{1},V_{2})$ for
arbitrary random variables $V_{1}$ and $V_{2}$ jointly distributed with $Y$.
While the original argument in [32] overlooked the randomness of $V_{1}$, this
principle can be rigorously justified by Lemma 1 as $V_{1}-(V_{1},V_{2})-Y$
always form a Markov chain. It is also apparent from Lemma 1 or its proof that
randomizing the decision rule does not help to decrease the expected loss in
Bayes decision making, as $(T,V)-V-Y$ form a Markov chain for any independent
random variable $T$ to be used in the randomized decision rule.

###  2.3 Definition of minimum excess risk

An immediate consequence of Lemma 1 in Bayesian learning is that the Bayes
risk $R_{\ell}(Y|X,Z^{n})$ decreases as the data size $n$ increases, as
$(X,Z^{n})-(X,Z^{n+1})-Y$ form a Markov chain. A special case of this result
for linear regression with quadratic loss appears in [34]. While
$R_{\ell}(Y|X,Z^{n})$ decreases in $n$, it will not necessarily vanish as
$n\rightarrow\infty$. We define the _fundamental limit of the Bayes risk_ as
the minimum expected loss when the model parameters $W$ are known, which is
attained by some “omniscient” decision rule $\Psi\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{A}}$ that can
directly access the model parameters.

######  Definition 2.

In Bayesian learning, the fundamental limit of the Bayes risk with respect to
a loss function $\ell$ is defined as

$\displaystyle R_{\ell}(Y|X,W)=\inf_{\Psi\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{A}}}\mathbf{E}[\ell(Y,\Psi(X,W))].$
(11)

For any feasible decision rule $\psi\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{Z}}^{n}\rightarrow{\mathsf{A}}$, we can
define its _excess risk_ as the gap between its expected loss
$\mathbf{E}[\ell(Y,\psi(X,Z^{n}))]$ and $R_{\ell}(Y|X,W)$. In this work, our
interest is in the gap between the Bayes risk $R_{\ell}(Y|X,Z^{n})$ and its
fundamental limit $R_{\ell}(Y|X,W)$, which is the minimum achievable excess
risk among all feasible decision rules:

######  Definition 3.

The minimum excess risk (MER) with respect to a loss function $\ell$ is
defined as

$\displaystyle{\rm MER}_{\ell}\mathrel{\mathop{\mathchar
58\relax}}=R_{\ell}(Y|X,Z^{n})-R_{\ell}(Y|X,W).$ (12)

The MER defined above is an algorithm-independent quantity. It quantifies the
regret of the best decision rule that has access to data, but not to model
parameters, relative to the best “omniscient” decision rule. It thus reflects
the difficulty of the learning problem, which comes from the lack of knownedge
of $W$. This is better illustrated by decomposing the Bayes risk as

$\displaystyle R_{\ell}(Y|X,Z^{n})=R_{\ell}(Y|X,W)+{\rm MER}_{\ell}.$ (13)

If we view the Bayes risk as a measure of the minimum prediction uncertainty,
this decomposition allows us to give formal definitions of the “aleatoric”
uncertainty and the minimum “epistemic” uncertainty [9]. The first term, the
fundamental limit of the Bayes risk, can be viewed as the aleatoric part of
the minimum prediction uncertainty, which exists even when the model
parameters are known. The second term, the MER, can be viewed as the epistemic
part of the minimum prediction uncertainty, which is due to the lack of
knowledge of $W$. In [10], a decomposition of uncertainty is proposed for the
log loss and the quadratic loss, where the epistemic uncertainty is defined as
$R_{\ell}(Y|X)-R_{\ell}(Y|X,W)$ when expressed by our notation; however, this
definition does not take the observed data into consideration, thus does not
reflect the intuitive expectation that the epistemic uncertainty should
decrease as the data size increases [11]. On the contrary, defining the
minimum epistemic uncertainty as the MER has the advantage that it becomes
smaller as more data is observed, as asserted by the following result.

######  Theorem 1.

For any loss function, ${\rm MER}_{\ell}$ decreases in the data size $n$, and
${\rm MER}_{\ell}\geq 0$ for all $n$.

###### Proof.

The claim that ${\rm MER}_{\ell}$ decreases in $n$ is due to the previously
justified fact that $R_{\ell}(Y|X,Z^{n})$ decreases in $n$ as a consequence of
Lemma 1. The claim that ${\rm MER}_{\ell}\geq 0$ is due to the Markov chain
$(X,Z^{n})-(X,W)-Y$ and Lemma 1. ∎

Intuitively, we expect that ${\rm MER}_{\ell}\downarrow 0$ as
$n\rightarrow\infty$. However, except for the log loss, there are few results
in the literature regarding this convergence in the general case, or regarding
how the MER depends on the estimation error of the model parameters. In the
following two sections, we use different methods to derive upper bounds on MER
for general loss functions. We show that, in many cases, the MER can be upper-
bounded either in terms of the conditional mutual information
$I(W;Y|X,Z^{n})$, or in terms of the minimum achievable estimation error of
$W$ from $(X,Z^{n})$. These results reflect how the MER depends on the joint
distribution in (1), in particular on $P_{Z|W}$ and $P_{W}$, as well as on the
loss function and the data size.

##  3 Upper bounds via conditional mutual information

The first method for upper-bounding the MER is to relate it to the conditional
mutual information $I(W;Y|X,Z^{n})$, which can be further bounded by
$\frac{1}{n}I(W;Y^{n}|X^{n})$ or $\frac{1}{n}I(W;Z^{n})$. In many cases, it
can be shown that the mutual information $I(W;Z^{n})$ is sublinear in $n$ [35,
36, 37], which implies that the MER converges to zero as $n\to\infty$.

###  3.1 Logarithmic loss

We first consider the setting where one makes “soft” predictions, such that
the action space is the collection of all probability densities $q$ with
respect to a common $\sigma$-finite positive measure $\mu$ on ${\mathsf{Y}}$.
The log loss $\ell(y,q)\mathrel{\mathop{\mathchar 58\relax}}=-\log q(y)$
penalizes those densities that assign small probabilities to the outcome $y$.
Based on the definitions in (3) and (4), it can be shown that

$\displaystyle R_{\log}(Y)=H_{\mu}(Y)\mathrel{\mathop{\mathchar
58\relax}}=-\int_{\mathsf{Y}}p_{Y}(y)\log p_{Y}(y)\mu(\operatorname{d\\!}y)$
(14)

and

$\displaystyle R_{\log}(Y|V)=H_{\mu}(Y|V)\mathrel{\mathop{\mathchar
58\relax}}=-\int_{\mathsf{V}}P_{V}(\operatorname{d\\!}v)\int_{\mathsf{Y}}p_{Y|v}(y)\log
p_{Y|v}(y)\mu(\operatorname{d\\!}y),$ (15)

which can be viewed as the _$\mu$ -entropy_ of $Y$ and the _conditional
$\mu$-entropy_ of $Y$ given $V$, and the optimal actions are the unconditional
density $p_{Y}$ and the conditional density $p_{Y|v}$ with respect to $\mu$,
respectively. For instance, if ${\mathsf{Y}}$ is discrete and $\mu$ is the
counting measure, then $R_{\log}(Y)=H(Y)$ and $R_{\log}(Y|V)=H(Y|V)$ are the
Shannon and the conditional Shannon entropy; while if
${\mathsf{Y}}=\mathbb{R}^{p}$ and $\mu$ is the Lebesgue measure, then
$R_{\log}(Y)=h(Y)$ and $R_{\log}(Y|V)=h(Y|V)$ are the differential and the
conditional differential entropy. (See [31] for further background on
information theory.) With these definitions, the MER for the log loss is the
difference between two $\mu$-entropy terms:

$\displaystyle{\rm MER}_{\log}$
$\displaystyle=H_{\mu}(Y|X,Z^{n})-H_{\mu}(Y|X,W).$ (16)

A key observation is that ${\rm MER}_{\log}$ can be expressed in terms of the
conditional mutual information:

######  Lemma 1.

For the log loss,

$\displaystyle{\rm MER}_{\log}=I(W;Y|X,Z^{n}).$ (17)

###### Proof.

The claim follows from the fact that
$I(W;Y|X,Z^{n})=H_{\mu}(Y|X,Z^{n})-H_{\mu}(Y|X,W,Z^{n})$ and that
$H_{\mu}(Y|X,W,Z^{n})=H_{\mu}(Y|X,W)$. The second fact is due to the Markov
chain $(X,W,Z^{n})-(X,W)-Y$ encoded in (1) and the definition of the
conditional $\mu$-entropy. ∎

Equation (17) states that ${\rm MER}_{\log}$ is the average reduction of the
uncertainty about $Y$ that comes from the knowledge of $W$, given that
$(X,Z^{n})$ is already known. With this representation, using the conditional
independence structure in (1) and the data processing inequality in Lemma 1
applied to the $\mu$-entropy, we have:

######  Theorem 2.

The MER with respect to the log loss can be upper-bounded as

$\displaystyle I(W;Y|X,Z^{n})\leq\frac{1}{n}I(W;Y^{n}|X^{n}).$ (18)

###### Proof.

For $i=1,\ldots,n-1$, we have

$\displaystyle I(W;Y_{i}|X^{n},Y^{i-1})$
$\displaystyle=H_{\mu}(Y_{i}|X^{n},Y^{i-1})-H_{\mu}(Y_{i}|W,X^{n},Y^{i-1})$
(19)
$\displaystyle=H_{\mu}(Y_{i+1}|X^{n},Y^{i-1})-H_{\mu}(Y_{i+1}|W,X^{n},Y^{i-1})$
(20) $\displaystyle\geq
H_{\mu}(Y_{i+1}|X^{n},Y^{i})-H_{\mu}(Y_{i+1}|W,X^{n},Y^{i})$ (21)
$\displaystyle=I(W;Y_{i+1}|X^{n},Y^{i})$ (22)

where (19) is due to the definitions of the conditional mutual information and
the conditional $\mu$-entropy in (15); (20) follows from the fact that
$(W,X^{n},Y^{i-1},Y_{i})\stackrel{{\scriptstyle\rm
d.}}{{=}}(W,X^{n},Y^{i-1},Y_{i+1})$111For random variables $U$ and $V$,
$U\stackrel{{\scriptstyle\rm d.}}{{=}}V$ means that $U$ and $V$ have the same
distribution.; and (21) follows from the fact that
$H_{\mu}(Y_{i+1}|X^{n},Y^{i-1})\geq H_{\mu}(Y_{i+1}|X^{n},Y^{i})$ due to Lemma
1, and the fact that
$H_{\mu}(Y_{i+1}|W,X^{n},Y^{i-1})=H_{\mu}(Y_{i+1}|W,X^{n},Y^{i})=H_{\mu}(Y_{i+1}|W,X_{i+1})$
as $Y_{i+1}$ is conditionally independent of everything else given
$(W,X_{i+1})$.

Then, from the chain rule of mutual information,

$\displaystyle I(W;Y^{n}|X^{n})$
$\displaystyle=\sum_{i=1}^{n}I(W;Y_{i}|X^{n},Y^{i-1})$ (23) $\displaystyle\geq
nI(W;Y_{n}|X^{n},Y^{n-1})$ (24) $\displaystyle=nI(W;Y|X,Z^{n-1})$ (25)
$\displaystyle=n\big{(}H_{\mu}(Y|X,Z^{n-1})-H_{\mu}(Y|W,X,Z^{n-1})\big{)}$
(26) $\displaystyle\geq
n\big{(}H_{\mu}(Y|X,Z^{n})-H_{\mu}(Y|W,X,Z^{n})\big{)}$ (27)
$\displaystyle=nI(W;Y|X,Z^{n})$ (28)

where (24) is obtained by repeated application of (22); (25) is due to the
fact that $(W,Z^{n-1},Z_{n})\stackrel{{\scriptstyle\rm
d.}}{{=}}(W,Z^{n-1},Z)$; and (27) follows from Lemma 1 and the fact that $Y$
is conditionally independent of everything else given $(W,X)$. The claim
follows from (28). ∎

Theorem 2 can be weakened to the following corollary using the fact that
$I(W;Y^{n}|X^{n})=I(W;Z^{n})-I(W;X^{n})$. There is no slack when $X$ is
independent of $W$.

######  Corollary 1.

The MER with respect to the log loss can be upper-bounded as

$\displaystyle I(W;Y|X,Z^{n})$ $\displaystyle\leq\frac{1}{n}I(W;Z^{n}).$ (29)

Upon maximizing over $P_{W}$ on both side of (29), Corollary 1 is reminiscent
of the _redundancy-capacity theorem_ in universal source coding in the
Bayesian setting [13, 14], where the quantity of interest is the minimum
_overall_ redundancy
$\min_{Q}\mathbf{E}_{P_{W,Z^{n}}}[-\log{Q(Z^{n})}+\log{P_{Z^{n}|W}(Z^{n}|W)}]$,
which can be shown to be $I(W;Z^{n})$. Therefore, from the source coding point
of view, ${\rm MER}_{\log}$ in (17) may be interpreted as the minimum
_instantaneous_ redundancy of encoding a fresh sample when $n$ data samples
are observed, which is shown to be smaller than the normalized minimum overall
redundancy by Corollary 1. More generally, the mutual information $I(W;Z^{n})$
is also known to be the minimum _accumulated_ excess risk for the log loss in
Bayesian sequential prediction [14], Bayesian density estimation [15], and
Bayesian supervised learning [16]. The non-asymptotic relationships between
the instantaneous ${\rm MER}_{\log}$ and the accumulated excess risks shown in
Theorem 2 and Corollary 1 hold for general model $P_{Z|W}$ and prior $P_{W}$,
and allow us to quantify the rate of convergence of ${\rm MER}_{\log}$ by
upper-bounding $I(W;Y^{n}|X^{n})$ or $I(W;Z^{n})$.

From the results of [35, 36, 37], if ${\mathsf{W}}$ is a $d$-dimensional
compact subset of $\mathbb{R}^{d}$ and the model $P_{Z|w}$ is sufficiently
smooth in $w$ (see Section A.1 for rigorous statements of these conditions),
then

$\displaystyle I(W;Z^{n})=\frac{d}{2}\log\frac{n}{2\pi
e}+h(W)+\frac{1}{2}\mathbf{E}\big{[}\log\det J_{Z|W}\big{]}+o(1)\quad\text{ as
$n\rightarrow\infty$,}$ (30)

where $h(W)$ is the differential entropy of $W$, and, as a functional of
$P_{Z|w}$, $J_{Z|w}$ is the Fisher information matrix about $w$ contained in
$Z$ with respect to $P_{Z|w}$, and the expectation is taken with respect to
$P_{W}$. Due to the logarithmic dependence on $n$ in (30) and the chain rule
of mutual information, it can be shown that the instantaneous mutual
information under the same conditions satisfies $I(W;Z|Z^{n})=O(d/n)$ as
$n\rightarrow\infty$. This gives us a refined asymptotic upper bound on ${\rm
MER}_{\log}$ whenever (30) holds than directly applying (30) to Corollary 1:

######  Theorem 3.

Under the regularity conditions listed in Section A.1 under which (30) holds,
we have

$\displaystyle{\rm MER}_{\log}$
$\displaystyle=O\Big{(}\frac{d}{2n}\Big{)}\quad\text{as
$n\rightarrow\infty$.}$ (31)

###### Proof.

The proof relies on [38, Lemma 6] which is stated as Lemma 2 in Appendix A.3.
Suppose $(a_{1},a_{2},\ldots)$ and $(b_{1},b_{2},\ldots)$ are two sequences of
real numbers such that $a_{n}=\sum_{i=1}^{n}b_{i}$ for all $n$. Lemma 2 states
that, if $\lim_{n\rightarrow\infty}{a_{n}}/{\log n}$ and
$\lim_{n\rightarrow\infty}nb_{n}$ exist, then they are equal. With this result
and the chain rule of mutual information, we know that whenever (30) holds,

$\displaystyle\lim_{n\rightarrow\infty}(n+1)I(W;Z|Z^{n})=\lim_{n\rightarrow\infty}\frac{I(W;Z^{n})}{\log
n}=\frac{d}{2}.$ (32)

The claim follows from the fact that $I(W;Y|X,Z^{n})\leq I(W;Z|Z^{n})$. ∎

As we show next, the representation of ${\rm MER}_{\log}$ via the conditional
mutual information in (17) and the resulting upper bounds derived in this
subsection can be used to obtain upper bounds on the MER for other loss
functions as well.

###  3.2 Quadratic loss

While the log loss is naturally used for assessing “soft” predictions, it is
also a common practice to make “hard” predictions, e.g., the actions can be
elements in ${\mathsf{Y}}$. When ${\mathsf{Y}}={\mathsf{A}}=\mathbb{R}$, a
commonly used loss function is the quadratic loss $\ell(y,a)=(y-a)^{2}$. For
any $V$ that statistically depends on $Y$, the conditional Bayes envelope with
respect to the quadratic loss is $R_{2}(Y|V=v)={\mathsf{var}}[Y|v]$, the
optimal action is the conditional mean $\mathbf{E}[Y|v]$, and the
corresponding Bayes risk

$\displaystyle R_{2}(Y|V)=\mathbf{E}[{\mathsf{var}}[Y|V]]$ (33)

is the minimum mean square error (MMSE) of estimating $Y$ from $V$. In this
case, the MER in Bayesian learning turns out to be

$\displaystyle{\rm MER}_{2}$
$\displaystyle=\mathbf{E}\big{[}{\mathsf{var}}[Y|X,Z^{n}]\big{]}-\mathbf{E}\big{[}{\mathsf{var}}[Y|X,W]\big{]}.$
(34)

More generally, when ${\mathsf{Y}}={\mathsf{A}}=\mathbb{R}^{p}$ and
$\ell(y,a)=\|y-a\|^{2}$ with $\|\cdot\|$ denoting the $l_{2}$ norm, the MER in
this case is

$\displaystyle{\rm MER}_{2}$
$\displaystyle=\mathbf{E}\big{[}\|Y-\mathbf{E}[Y|X,Z^{n}]\|^{2}\big{]}-\mathbf{E}\big{[}\|Y-\mathbf{E}[Y|X,W]\|^{2}\big{]}$
(35)
$\displaystyle=\mathbf{E}\big{[}\|\mathbf{E}[Y|X,Z^{n}]-\mathbf{E}[Y|X,W]\|^{2}\big{]},$
(36)

where the second equality follows from the fact that
$\mathbf{E}[Y|X,W]=\mathbf{E}[Y|X,W,Z^{n}]$ and the orthogonality principle in
MMSE estimation [39].

Under the assumption that $\|Y\|\leq b$, using a result that connects MMSE
difference to conditional mutual information [40, Theorem 10], we can upper-
bound ${\rm MER}_{2}$ in terms of $I(W;Y|X,Z^{n})$:

######  Theorem 4.

If ${\mathsf{Y}}=\\{y\in\mathbb{R}^{p}\mathrel{\mathop{\mathchar
58\relax}}\|y\|\leq b\\}$ for some $b>0$, then for the quadratic loss,

$\displaystyle{\rm MER}_{2}\leq{2b^{2}}I(W;Y|X,Z^{n}).$ (37)

###### Proof.

[40, Theorem 10] states that if $\|Y\|\leq b$, then for any $(U,V)$ jointly
distributed with $Y$,

$\displaystyle R_{2}(Y|U)-R_{2}(Y|U,V)$ $\displaystyle\leq 2b^{2}I(V;Y|U).$
(38)

Using this result and the fact that $R_{2}(Y|X,W)=R_{2}(Y|X,W,Z^{n})$, we
obtain (37). ∎

With Theorem 4, all the upper bounds on ${\rm MER}_{\log}$ derived in Section
3.1 can be used to further upper-bound ${\rm MER}_{2}$. In particular,
whenever (30) holds, we have ${\rm MER}_{2}=O(b^{2}d/2n)$ as
$n\rightarrow\infty$.

###  3.3 Zero-one loss

Another loss function we consider for hard predictions is the zero-one loss
$\ell(y,a)={\bf 1}\\{y\neq a\\}$ with ${\mathsf{Y}}={\mathsf{A}}$. For any $V$
that statistically depends on $Y$, the conditional Bayes envelope with respect
to the zero-one loss is $R_{01}(Y|V=v)=1-\max_{y\in{\mathsf{Y}}}P_{Y|v}(y)$,
the optimal action is the conditional mode
$\operatorname*{arg\,max}_{y\in{\mathsf{Y}}}P_{Y|v}(y)$, and the corresponding
Bayes risk is

$\displaystyle
R_{01}(Y|V)=1-\mathbf{E}[\max\nolimits_{y\in{\mathsf{Y}}}P_{Y|V}(y)],$ (39)

with expectation taken with respect to $V$. The MER for the zero-one loss is

$\displaystyle{\rm
MER}_{01}=\mathbf{E}[\max\nolimits_{y\in{\mathsf{Y}}}P_{Y|X,W}(y)]-\mathbf{E}[\max\nolimits_{y\in{\mathsf{Y}}}P_{Y|X,Z^{n}}(y)],$
(40)

where the expectations are taken with respect to the conditioning variables.
In this case, as the loss function takes values in $[0,1]$, Theorem 6 stated
in the next subsection gives an upper bound for ${\rm MER}_{01}$ in terms of
$I(W;Y|X,Z^{n})$:

######  Corollary 2.

For the zero-one loss,

$\displaystyle{\rm MER}_{01}$
$\displaystyle\leq\sqrt{\frac{1}{2}I(W;Y|X,Z^{n})}.$ (41)

From the results in Section 3.1, we know that whenever (30) holds, ${\rm
MER}_{01}=O(\sqrt{d/n})$ as $n\rightarrow\infty$.

For the special case of binary classification, where ${\mathsf{Y}}=\\{0,1\\}$,
the Bayes risk $R_{01}(Y|X,Z^{n})$ is studied in [17] and is upper-bounded in
terms of $H(Y^{n}|X^{n})$. When the model is realizable, that is, when
$Y=g(X,W)$ with some generative function $g\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow\\{0,1\\}$, it is also
observed in [17] that $H(Y^{n}|X^{n})$ can be further upper-bounded in terms
of the VC dimension of the generative function class
$\mathcal{G}=\\{g(\cdot,w)\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\rightarrow\\{0,1\\},w\in{\mathsf{W}}\\}$, defined as

$\displaystyle V(\mathcal{G})\mathrel{\mathop{\mathchar
58\relax}}=\sup\Big{\\{}n\in\mathbb{N}\mathrel{\mathop{\mathchar
58\relax}}\sup_{x^{n}\in{\mathsf{X}}^{n}}\big{|}\big{\\{}(g(x_{1},w),\ldots,g(x_{n},w)),w\in{\mathsf{W}}\big{\\}}\big{|}=2^{n}\Big{\\}}.$
(42)

The Sauer-Shelah lemma [41, 42] states that, if $V(\mathcal{G})=d$, then for
all $x^{n}\in{\mathsf{X}}^{n}$,

$\displaystyle\big{|}\big{\\{}(g(x_{1},w),\ldots,g(x_{n},w)),w\in{\mathsf{W}}\big{\\}}\big{|}\leq\sum_{k=1}^{d}{{n}\choose{k}}\leq
en^{d}.$ (43)

As ${\rm MER}_{01}\leq R_{01}(Y|X,Z^{n})$, the results in [17] lead to the
following MER upper bounds.

######  Theorem 5.

If ${\mathsf{Y}}=\\{0,1\\}$, then

$\displaystyle{\rm
MER}_{01}\leq\frac{1}{2}H(Y|X,Z^{n})\leq\frac{1}{2n}H(Y^{n}|X^{n}).$ (44)

Moreover, if $Y=g(X,W)$ with some function $g\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{Y}}$, and the
function class $\mathcal{G}=\\{g(\cdot,w)\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\rightarrow{\mathsf{Y}},w\in{\mathsf{W}}\\}$ has VC
dimension $d$, then

$\displaystyle{\rm MER}_{01}\leq O\Big{(}\frac{d}{2n}\Big{)}\quad\text{as
$n\rightarrow\infty$.}$ (45)

These upper bounds also hold for $\frac{1}{2}{\rm MER}_{\log}$ in the same
settings.

###### Proof.

The proof of (44) is essentially drawn from [17]. Using our notation,

$\displaystyle{\rm MER}_{01}$ $\displaystyle\leq R_{01}(Y|X,Z^{n})$ (46)
$\displaystyle=\mathbf{E}\Big{[}\min_{y\in\\{0,1\\}}P[Y=y|X,Z^{n}]\Big{]}$
(47)
$\displaystyle\leq\mathbf{E}\Big{[}\frac{1}{2}h_{2}\big{(}P[Y=1|X,Z^{n}]\big{)}\Big{]}$
(48) $\displaystyle=\frac{1}{2}H(Y|X,Z^{n})$ (49)
$\displaystyle\leq\frac{1}{2n}H(Y^{n}|X^{n}),$ (50)

where (46) follows from the fact that ${R}_{01}(Y|X,W)\geq 0$; (47) follows
from (39) and the assumption that ${\mathsf{Y}}=\\{0,1\\}$; (48) follows from
the fact that $\min\\{p,1-p\\}\leq\frac{1}{2}h_{2}(p)$ for $p\in[0,1]$, where
$h_{2}(\cdot)$ is the binary entropy function; and (50) can be proved by the
chain rule of Shannon entropy and the fact that $H(Y_{i}|X^{n},Y^{i-1})$
decreases as $i$ increases, similar to the proof of Theorem 2.

The proof of (45) relies on the observation made in [17] that
$H(Y^{n}|X^{n})\leq d\log n+1$ under a realizable model whenever the VC
dimension of $\mathcal{G}$ is $d$, which is due to the Sauer-Shelah lemma
(43). Additionally, from $H(Y^{n}|X^{n})=\sum_{i=1}^{n}H(Y_{i}|X^{n},Y^{i-1})$
and Lemma 2, we have

$\displaystyle\lim_{n\rightarrow\infty}(n+1)H(Y|X,Z^{n})=\lim_{n\rightarrow\infty}\frac{H(Y^{n}|X^{n})}{\log
n}\leq d$ (51)

whenever these limits exist, which proves (45).

The upper bounds also hold for $\frac{1}{2}{\rm MER}_{\log}$ because ${\rm
MER}_{\log}\leq H(Y|X,Z^{n})$, as $H(Y|X,W)\geq 0$ when ${\mathsf{Y}}$ is
discrete. ∎

In Section 3.5, we discuss the MER under realizable models in more general
settings, where the results go beyond binary classification and zero-one loss.

###  3.4 General loss functions

Now we derive a general upper bound for the MER with respect to a wide range
of loss functions. For an arbitrary loss function
$\ell\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{Y}}\times{\mathsf{A}}\rightarrow\mathbb{R}$, let
$\Psi^{*}\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{Y}}$ be the
optimal omniscient decision rule such that
$\mathbf{E}[\ell(Y,\Psi^{*}(X,W))]=R_{\ell}(Y|X,W)$. Given $(X,Z^{n})$, let
$W^{\prime}$ be a sample from the posterior distribution $P_{W|X,Z^{n}}$
conditionally independent of everything else given $(X,Z^{n})$. Then the MER
can be upper-bounded by

$\displaystyle{\rm MER}_{\ell}$
$\displaystyle\leq\mathbf{E}[\ell(Y,\Psi^{*}(X,W^{\prime}))]-\mathbf{E}[\ell(Y,\Psi^{*}(X,W))].$
(52)

Here, $\Psi^{*}(X,W^{\prime})$ is a plug-in decision rule, where we first
estimate $W$ by $W^{\prime}$ from $(X,Z^{n})$, and then plug $W^{\prime}$ in
$\Psi^{*}$ to predict $Y$ given $X$. The right side of (52) is the excess risk
of this plug-in decision rule. Under regularity conditions on the moment
generating function of $\ell(Y,\Psi^{*}(X,W^{\prime}))$ under the conditional
distribution $P_{Y,W^{\prime}|X,Z^{n}}$, we have the following upper bound on
${\rm MER}_{\ell}$ in terms of $I(\Psi^{*}(X,W);Y|X,Z^{n})$.

######  Theorem 6.

Assume there is a function $\varphi(\lambda)$ defined on $[0,b)$ for some
$b\in(0,\infty]$, such that

$\displaystyle\log\mathbf{E}_{x,z^{n}}\Big{[}\exp\Big{\\{}-\lambda\Big{(}\ell(Y,\Psi^{*}(x,W^{\prime}))-\mathbf{E}_{x,z^{n}}\big{[}\ell(Y,\Psi^{*}(x,W^{\prime}))\big{]}\Big{)}\Big{\\}}\Big{]}\leq\varphi(\lambda)$
(53)

for all $0\leq\lambda<b$ and all $(x,z^{n})$, where
$\mathbf{E}_{x,z^{n}}[\cdot]$ denotes the conditional expectation with respect
to $(Y,W^{\prime})$ given $(X,Z^{n})=(x,z^{n})$. Then

$\displaystyle{\rm MER}_{\ell}$
$\displaystyle\leq\varphi^{*-1}\left(I(\Psi^{*}(X,W);Y|X,Z^{n})\right),$ (54)

where $\varphi^{*}(\gamma)\mathrel{\mathop{\mathchar
58\relax}}=\sup_{0\leq\lambda<b}\\{\lambda\gamma-\varphi(\lambda)\\}$,
$\gamma\in\mathbb{R}$, is the Legendre dual of $\varphi$, and
$\varphi^{*-1}(u)\mathrel{\mathop{\mathchar
58\relax}}=\sup\\{\gamma\in\mathbb{R}\mathrel{\mathop{\mathchar
58\relax}}\varphi^{*}(\gamma)\leq u\\}$, $u\in\mathbb{R}$, is the generalized
inverse of $\varphi^{*}$. In addition, if $\varphi(\lambda)$ is strictly
convex over $(0,b)$ and $\varphi(0)=\varphi^{\prime}(0)=0$, then
$\lim_{x\downarrow 0}\varphi^{*-1}(x)=0.$

###### Proof.

We have the following chain of inequalities:

$\displaystyle{\rm MER}_{\ell}$
$\displaystyle\leq\mathbf{E}[\ell(Y,\Psi^{*}(X,W^{\prime}))]-\mathbf{E}[\ell(Y,\Psi^{*}(X,W))]$
(55)
$\displaystyle=\mathbf{E}\big{[}\mathbf{E}[\ell(Y,\Psi^{*}(X,W^{\prime}))-\ell(Y,\Psi^{*}(X,W))|X,Z^{n}]\big{]}$
(56) $\displaystyle\leq\mathbf{E}\big{[}\varphi^{*-1}\big{(}D_{\rm
KL}(P_{Y,\Psi^{*}(X,W)|X,Z^{n}}\|P_{Y,\Psi^{*}(X,W^{\prime})|X,Z^{n}})\big{)}\big{]}$
(57) $\displaystyle=\varphi^{*-1}\big{(}\mathbf{E}\big{[}D_{\rm
KL}(P_{Y,\Psi^{*}(X,W)|X,Z^{n}}\|P_{Y,\Psi^{*}(X,W^{\prime})|X,Z^{n}})\big{]}\big{)}$
(58) $\displaystyle=\varphi^{*-1}\big{(}I(\Psi^{*}(X,W);Y|X,Z^{n})\big{)}$
(59)

where (57) follows from the assumption (53) in the statement of the theorem
and Lemma 1 stated in Appendix A.2 applied to $P=P_{Y,\Psi^{*}(x,W)|x,z^{n}}$
and $Q=P_{Y,\Psi^{*}(x,W^{\prime})|x,z^{n}}$, and the expectation is taken
with respect to $(X,Z^{n})$; (58) follows from the concavity of
$\varphi^{*-1}$, which is due to the convexity of $\varphi^{*}$, and Jensen’s
inequality; (59) follows from the fact that $W^{\prime}$ is conditionally
i.i.d. of $W$ and conditionally independent of $Y$ given $(X,Z^{n})$. The last
claim of the theorem comes from the fact that under the assumptions on
$\varphi$, its Legendre dual $\varphi^{*}$ is increasing on $[0,\infty)$ and
continuous at $0$ and so is the inverse $\varphi^{*-1}$. ∎

An example for the condition in (53) to hold is when the random variable
$\ell(Y,\Psi^{*}(x,W^{\prime}))$ is $\sigma^{2}$-subgaussian222A random
variable $U$ is $\sigma^{2}$-subgaussian if
$\mathbf{E}[e^{\lambda(U-\mathbf{E}U)}]\leq e^{\lambda^{2}\sigma^{2}/2}$ for
all $\lambda\in\mathbb{R}$. conditionally on $(X,Z^{n})=(x,z^{n})$. In this
case, (53) holds with $b=\infty$ and
$\varphi(\lambda)={\sigma^{2}\lambda^{2}}/{2}$, and we have the following
corollary.

######  Corollary 3.

If $\ell(Y,\Psi^{*}(x,W^{\prime}))$ is $\sigma^{2}$-subgaussian conditionally
on $(X,Z^{n})=(x,z^{n})$ for all $(x,z^{n})$, then

$\displaystyle{\rm MER}_{\ell}$
$\displaystyle\leq\sqrt{{2\sigma^{2}}I(\Psi^{*}(X,W);Y|X,Z^{n})}.$ (60)

Using the fact that if $\ell(\cdot,\cdot)\in[a,b]$ then $\ell$ is
$(b-a)^{2}/4$-subgaussian under any distribution of the arguments, Corollary 3
can provide upper bound for the MER under any bounded loss functions. More
generally, Theorem 6 can be applied in the situation where the loss function
is unbounded and non-subgaussian. In Appendix B, we present such a case where
an MER upper bound for the quadratic loss in linear regression is derived
based on Theorem 6.

From the data processing inequality of mutual information,

$\displaystyle I(\Psi^{*}(X,W);Y|X,Z^{n})\leq I(W;Y|X,Z^{n}).$ (61)

Since $\varphi^{*-1}$ defined in Theorem 6 is an increasing function on
$[0,\infty)$, the upper bounds in (54) and (60) can be weakened by replacing
$I(\Psi^{*}(X,W);Y|X,Z^{n})$ with $I(W;Y|X,Z^{n})$ or any of its upper bounds
derived in Section 3.1. In particular, when (30) holds in addition with the
assumption in Theorem 6, we have ${\rm MER}_{\ell}=O(\varphi^{*-1}(d/n))$ as
$n\rightarrow\infty$.

Theorem 6 also provides a connection between the MER and the mutual
information between the _observed data_ and the _learned model parameters_. If
$X$ is independent of $W$, then $P_{W|X,Z^{n}}=P_{W|Z^{n}}$, and
$(W^{\prime},Z^{n})$ have the same joint distribution as $(W,Z^{n})$. In this
case, when the condition in Corollary 3 is satisfied, upper-bounding
$I(W;Y|X,Z^{n})$ in (60) by $\frac{1}{n}I(W;Z^{n})$ according to Corollary 1
leads to the following result.

######  Corollary 4.

If $X$ is independent of $W$ in addition to the condition in Corollary 3, then

$\displaystyle{\rm MER}_{\ell}$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}}{n}I(Z^{n};W^{\prime})},$ (62)

where $I(Z^{n};W^{\prime})$ is the mutual information between the data and the
learned model parameters sampled from the posterior distribution
$P_{W|Z^{n}}$.

Corollary 4 is an analogue of the generalization-information relationship in
the frequentist learning [43, 12], where it is shown that the generalization
error in frequentist learning can be upper-bounded in terms of the mutual
information between the _observed data_ and the _learned hypothesis_. From
(54), we also know that when the more general condition in Theorem 6 is
satisfied, we have ${\rm
MER}_{\ell}\leq\varphi^{*-1}(\frac{1}{n}I(Z^{n};W^{\prime}))$, which is
analogous to upper bounds on the generalization error in [44].

###  3.5 Realizable models and connection to VC dimension

In Section 3.3 we have presented the MER for the zero-one loss under the
realizable model of binary classification. Here, we present a few results on
the MER for general loss functions under general realizable models. These
results provide tighter asymptotic MER bounds under realizable models than
directly using the general results obtained in the previous subsection.
Following the observations made in [17], these results also show how the key
quantities in classical frequentist learning theory, notably the
Vapnik–Chervonenkis (VC) dimension, can be naturally brought into the MER
analysis in Bayesian learning through the information-theoretic framework
proposed in this work.

A realizable model is a model where the quantity of interest $Y$ is determined
by the observation $X$ and the model parameters $W$ through a _generative
function_ $g\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{Y}}$. Under a
realizable model, $g(X,W^{\prime})$ can serve as a plug-in decision rule,
where $W^{\prime}$ is a sample from the posterior distribution
$P_{W|X,Z^{n}}$, conditionally independent of everything else given
$(X,Z^{n})$. It is observed in a follow-up work [45] (which has appeared after
the initial version of this paper was posted) that the generalization error
bounds developed in [46] for the realizable setting of frequentist learning
can be adapted to MER bounds for realizable models in Bayesian learning. In
particular, [45, Lemma 3] shows that for a loss function $\ell\in[0,b]$, if
$R_{\ell}(Y|X,W)=0$, then ${\rm MER}_{\ell}\leq 3bI(W;Y|X,Z^{n})$. Following
this approach, the next result provides an upper bound for the MER under
realizable models, with a better prefactor and a tighter conditional mutual
information term.

######  Theorem 7.

For a loss function $\ell\in[0,b]$, if there exists a function
$g\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{Y}}$ such that
$\ell(Y,g(X,W))=0$ almost surely with respect to the joint distribution
$P_{W,X,Y}$, then

$\displaystyle{\rm MER}_{\ell}\leq\frac{b}{\log 2}I(g(W,X);Y|X,Z^{n}).$ (63)

###### Proof.

We have the following chain of inequalities:

$\displaystyle{\rm MER}_{\ell}$
$\displaystyle\leq\mathbf{E}[\ell(Y,g(X,W^{\prime}))]$ (64)
$\displaystyle=\mathbf{E}\big{[}\mathbf{E}[\ell(Y,g(X,W^{\prime}))|X,Z^{n}]\big{]}$
(65) $\displaystyle\leq\int\frac{b}{\log
2}I(g(x,W);Y|X=x,Z^{n}=z^{n})P_{X,Z^{n}}({\rm d}x,{\rm d}z^{n})$ (66)
$\displaystyle=\frac{b}{\log 2}I(g(X,W);Y|X,Z^{n}),$ (67)

where (64) follows from the assumption that $\ell(Y,g(X,W))=0$, the minimum
loss, which implies that $R_{\ell}(Y|X,W)=0$; (66) follows by applying Lemma 2
stated below to the joint distribution $P_{g(x,W),Y|x,z^{n}}$ for all
$(x,z^{n})$ under $P_{X,Z^{n}}$. ∎

The following lemma used in the proof of Theorem 7 is adapted from [46,
Theorem 5.7], where it is developed for bounding the generalization error in
the realizable setting of frequentist learning.

######  Lemma 2.

Let $V$ and $Y$ be jointly distributed random variables on
${\mathsf{V}}\times{\mathsf{Y}}$. Let $V^{\prime}$ be an independent copy of
$V$, that is, $P_{V^{\prime}}=P_{V}$ and $V^{\prime}$ is independent of
$(V,Y)$. For a function $\ell\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{Y}}\times{\mathsf{V}}\rightarrow[0,b]$, if $\ell(Y,V)=0$
almost surely with respect to $P_{V,Y}$, then

$\displaystyle\mathbf{E}[\ell(Y,V^{\prime})]\leq\frac{b}{\log 2}I(V;Y).$ (68)

###### Proof.

We follow the symmetrization idea used in the proof of [46, Theorem 5.7]. Let
$\tilde{V}=(V_{0},V_{1})$ with $V_{0}$ and $V_{1}$ being i.i.d. samples from
$P_{V}$. Let $S$ and $S^{\prime}$ be i.i.d. uniform Bernoulli random variables
independent of $\tilde{V}$, with $\overline{S}=1-S$, and
$\overline{S^{\prime}}=1-S^{\prime}$. With these random variables at hand, we
can construct $V=\tilde{V}_{S}$, $V^{\prime}=\tilde{V}_{\overline{S}}$, and
$Y$ to be jointly distributed with $V$ and conditionally independent of
everything else given $V$. Then, following the technique used in the proof of
[46, Theorem 5.7], for any $u>0$ and $t>0$,

$\displaystyle\mathbf{E}[\ell(Y,V^{\prime})]$ $\displaystyle=$
$\displaystyle\mathbf{E}[\ell(Y,V^{\prime})]-\mathbf{E}[u\ell(Y,V)]$ (69)
$\displaystyle=$
$\displaystyle\mathbf{E}[\ell(Y,\tilde{V}_{\overline{S}})]-\mathbf{E}[u\ell(Y,\tilde{V}_{S})]$
(70) $\displaystyle=$
$\displaystyle\mathbf{E}\big{[}\mathbf{E}[\ell(Y,\tilde{V}_{\overline{S}})-u\ell(Y,\tilde{V}_{S})|\tilde{V}]\big{]}$
(71) $\displaystyle\leq$
$\displaystyle\frac{1}{t}\Big{(}I(S;Y|\tilde{V})+\mathbf{E}\Big{[}\log\mathbf{E}\big{[}\exp\big{\\{}t\big{(}\ell(Y,\tilde{V}_{\overline{S^{\prime}}})-u\ell(Y,\tilde{V}_{S^{\prime}})\big{)}\big{\\}}\big{|}\tilde{V}\big{]}\Big{]}\Big{)}$
(72) $\displaystyle=$
$\displaystyle\frac{1}{t}\Big{(}I(S;Y|\tilde{V})+\mathbf{E}\Big{[}\log\mathbf{E}\big{[}\mathbf{E}\big{[}\exp\big{\\{}t\big{(}\ell(Y,\tilde{V}_{\overline{S^{\prime}}})-u\ell(Y,\tilde{V}_{S^{\prime}})\big{)}\big{\\}}|Y,S,\tilde{V}\big{]}\big{|}\tilde{V}\big{]}\Big{]}\Big{)}$
(73) $\displaystyle=$
$\displaystyle\frac{1}{t}\Big{(}I(S;Y|\tilde{V})+\mathbf{E}\Big{[}\log\mathbf{E}\big{[}\tfrac{1}{2}e^{t\ell(Y,\tilde{V}_{\overline{S}})}+\tfrac{1}{2}e^{-ut\ell(Y,\tilde{V}_{\overline{S}})}\big{|}\tilde{V}\big{]}\Big{]}\Big{)}$
(74)

where (69) is due to the assumption that $\ell(Y,V)=0$ almost surely; (72) is
due to the Donsker-Varadhan theorem, which implies that

$\displaystyle D_{\rm
KL}(P_{S,Y|\tilde{V}}\|P_{S^{\prime},Y|\tilde{V}})\geq\mathbf{E}\big{[}t\big{(}\ell(Y,\tilde{V}_{\overline{S}})-u\ell(Y,\tilde{V}_{S})\big{)}\big{|}\tilde{V}\big{]}-\log\mathbf{E}\big{[}\exp\big{\\{}t\big{(}\ell(Y,\tilde{V}_{\overline{S^{\prime}}})-u\ell(Y,\tilde{V}_{S^{\prime}})\big{)}\big{\\}}\big{|}\tilde{V}\big{]};$

and (74) follows from the fact that $S^{\prime}$ is equally likely to be $S$
or $\overline{S}$ conditional on $S$, writing out the inner-most expectation
in this way, and by setting $\ell(Y,\tilde{V}_{S})$ to $0$.

Setting $t=\frac{\log 2}{b}$ and sending $u\rightarrow\infty$, we see that the
inner expectation in (74) is upper-bounded by $1$, which leads to

$\displaystyle\mathbf{E}[\ell(Y,V^{\prime})]\leq\frac{b}{\log
2}I(S;Y|\tilde{V}).$ (75)

The claim follows from the observation made in [47] that $I(S;Y|\tilde{V})\leq
I(\tilde{V},S;Y)=I(V;Y)$, where the equality holds because $Y$ is
conditionally independent of $(\tilde{V},S)$ given $V=\tilde{V}_{S}$. ∎

Theorem 7 can be weakened by the data processing inequality of mutual
information,

$\displaystyle I(g(X,W);Y|X,Z^{n})\leq I(W;Y|X,Z^{n}),$ (76)

which can be further bounded by $\frac{1}{n}I(W;Y^{n}|X^{n})$ or
$\frac{1}{n}I(W;Z^{n})$ due to Theorem 2 or Corollary 1. When ${\mathsf{Y}}$
is discrete, $I(W;Y^{n}|X^{n})$ can be further bounded by $H(Y^{n}|X^{n})$. It
implies that under a realizable model with discrete ${\mathsf{Y}}$, not
necessarily binary, the MER with respect to a bounded loss function can be
upper-bounded nonasymptotically on the order of $H(Y^{n}|X^{n})/n$.

With a realizable model, a natural question to ask is how the MER depends on
the richness of the _generative function class_
$\mathcal{G}=\\{g(\cdot,w)\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\rightarrow{\mathsf{Y}},w\in{\mathsf{W}}\\}$. When
${\mathsf{Y}}=\\{0,1\\}$, one featuring combinatorial quantity that measures
the richness of $\mathcal{G}$ is its VC dimension, defined in (42). The
connection between $H(Y^{n}|X^{n})$ and $V(\mathcal{G})$ is observed in [17],
in the setting of binary classification with the zero-one loss. We make use of
it here to obtain a corollary of Theorem 7, which extends the results in
Theorem 5 as it applies to more general loss functions.

######  Corollary 5.

Under a realizable model with ${\mathsf{Y}}=\\{0,1\\}$, if the function class
$\mathcal{G}=\\{g(\cdot,w)\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\rightarrow{\mathsf{Y}},w\in{\mathsf{W}}\\}$ has VC
dimension $d$, then for any loss function $\ell\in[0,b]$,

$\displaystyle{\rm MER}_{\ell}\leq O\Big{(}\frac{b}{\log
2}\cdot\frac{d}{n}\Big{)}\quad\text{as $n\rightarrow\infty$}.$ (77)

###### Proof.

By (76) and Theorem 2, and the assumptions that the model is realizable and
${\mathsf{Y}}$ is discrete, the upper bound in Theorem 7 can be weakened to

$\displaystyle{\rm MER}_{\ell}$ $\displaystyle\leq\frac{b}{\log
2}H(Y|X,Z^{n})\leq\frac{b}{n\log 2}H(Y^{n}|X^{n}).$ (78)

The Sauer-Shelah lemma (43) implies that $H(Y^{n}|X^{n})\leq d\log n+1$. In
addition, from the chain rule of Shannon entropy and Lemma 2, we have

$\displaystyle\lim_{n\rightarrow\infty}(n+1)H(Y|X,Z^{n})=\lim_{n\rightarrow\infty}\frac{H(Y^{n}|X^{n})}{\log
n}\leq d,$ (79)

similar to the proof of (45) in Theorem 5. This proves the claim in view of
(78). ∎

The VC dimension plays a key role in the frequentist learning theory, in
bounding the excess risk in terms of the richness of the _hypothesis class_ ,
which amounts to the set of decision rules. In Bayesian learning, while there
is no restriction on the decision rules, Corollary 5 shows that the VC
dimension of the generative function class plays a similar role in upper-
bounding the MER.

##  4 Upper bounds via functional and distributional continuities

In the previous section, the upper bounds are derived by relating the MER to
$I(W;Y|X,Z^{n})$. In this section, we explore alternative methods for bounding
the MER, either in terms of the smoothness of the optimal omniscient decision
rule in model parameters, or in terms of the smoothness of the minimum
expected loss in the predictive model. These smoothness, or continuity
properties enable us to bound the MER via the accuracy of estimated parameters
from the data. The following lemma is instrumental for this approach.

######  Lemma 1 ([48], [49]).

Let $({\mathsf{U}},\rho)$ be a metric space. If $U$ and $U^{\prime}$ are two
random elements of ${\mathsf{U}}$ that are conditionally i.i.d. given another
random element $V$ of some space ${\mathsf{V}}$, i.e.,
$P_{U,U^{\prime}|V=v}=P_{U|V=v}P_{U^{\prime}|V=v}$ and
$P_{U|V=v}=P_{U^{\prime}|V=v}$ for all $v\in{\mathsf{V}}$, then
$\mathbf{E}[\rho(U^{\prime},U)]\leq 2R_{\rho}(U|V).$ Moreover, if
${\mathsf{U}}=\mathbb{R}^{d}$, then
$\mathbf{E}[\|U^{\prime}-U\|^{2}]=2R_{2}(U|V).$

As an aside, Lemma 1 provides us with a means for evaluating the performance
of making randomized prediction by sampling from the posterior predictive
distribution $P_{Y|X,Z^{n}}$, via upper-bounding the corresponding MER. Let
$Y^{\prime}$ be sampled from $P_{Y|X,Z^{n}}$, which can be realized by first
sampling $W^{\prime}$ from $P_{W|X,Z^{n}}$ then $Y^{\prime}$ from
$P_{Y|X,W^{\prime}}$. Then, for any metric $\ell$ on ${\mathsf{Y}}$, we have

$\displaystyle\mathbf{E}[\ell(Y,Y^{\prime})]\leq 2R_{\ell}(Y|X,W)+2{\rm
MER}_{\ell}.$ (80)

###  4.1 Via continuity of optimal omniscient decision rule

####  4.1.1 General upper bound

We start from (52) which states that ${\rm
MER}_{\ell}\leq\mathbf{E}[\ell(Y,\Psi^{*}(X,W^{\prime}))]-\mathbf{E}[\ell(Y,\Psi^{*}(X,W))]$,
where $\Psi^{*}$ is the optimal omniscient decision that achieves
$R_{\ell}(Y|X,W)$ when $W$ is known, and $W^{\prime}$ is a sample from the
posterior distribution $P_{W|X,Z^{n}}$ conditionally independent of everything
else given $(X,Z^{n})$. The MER can be upper-bounded in terms of the
smoothness of the function $\ell(y,\Psi^{*}(x,w))$ in $w$ and the accuracy of
approximating $W$ by $W^{\prime}$.

######  Theorem 8.

If ${\mathsf{W}}=\mathbb{R}^{d}$ and $W$ is independent of $X$, then

$\displaystyle{\rm
MER}_{\ell}\leq\mathbf{E}\Big{[}\sup_{y\in{\mathsf{Y}}}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}\ell(y,\Psi^{*}(X,w))\|\Big{]}\sqrt{2R_{2}(W|Z^{n})},$
(81)

where $\Psi^{*}$ is the optimal omniscient decision rule for the loss function
$\ell$.

###### Proof.

We have

$\displaystyle{\rm MER}_{\ell}$
$\displaystyle\leq\mathbf{E}[\ell(Y,\Psi^{*}(X,W^{\prime}))-\ell(Y,\Psi^{*}(X,W))]$
(82)
$\displaystyle\leq\mathbf{E}\Big{[}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}\ell(Y,\Psi^{*}(X,w))\|\cdot\|W^{\prime}-W\|\Big{]}$
(83)
$\displaystyle\leq\mathbf{E}\Big{[}\sup_{y\in{\mathsf{Y}}}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}\ell(y,\Psi^{*}(X,w))\|\Big{]}\mathbf{E}[\|W^{\prime}-W\|]$
(84)
$\displaystyle\leq\mathbf{E}\Big{[}\sup_{y\in{\mathsf{Y}}}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}\ell(y,\Psi^{*}(X,w))\|\Big{]}\sqrt{2R_{2}(W|Z^{n})},$
(85)

where we used (52), Lemma 4, the assumption that $X$ and $W$ are independent,
and the fact that
$\mathbf{E}[\|W^{\prime}-W\|]\leq\sqrt{E[\|W^{\prime}-W\|^{2}]}=\sqrt{2R_{2}(W|Z^{n})}$
due to Lemma 1. ∎

##### Example: constant $\Psi^{*}$

An extreme case where Theorem 8 can be useful is when
$\Psi^{*}\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{Y}}$ does not
dependent on $W$ under certain loss functions, in which case Theorem 8
guarantees that the MER is zero. For example, if $Y_{i}=g(X_{i},W)V_{i}$ and
$Y=g(X,W)V$, with some $g\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow\mathbb{R}$ and $(V^{n},V)$
being i.i.d. zero-mean random variables independent of $(W,X^{n},X)$, then for
the quadratic loss,

$\displaystyle\Psi^{*}(X,W)=\mathbf{E}[g(X,W)V|X,W]=g(X,W)\mathbf{E}[V]\equiv
0,$ (86)

hence ${\rm MER}_{2}=0$ by Theorem 8. It implies that for this example

$\displaystyle
R_{2}(Y|X,Z^{n})=R_{2}(Y|X,W)=\mathbf{E}\big{[}g(X,W)^{2}V^{2}\big{]}=\mathbf{E}\big{[}g(X,W)^{2}\big{]}{\mathsf{var}}[V],$
(87)

which shows that a small MER does not necessarily mean a small Bayes risk
$R_{\ell}(Y|X,Z^{n})$.

##### Example: logistic regression

Another example where Theorem 8 can be applied to is bounding the MER for
logistic regression with the log loss. Bayesian logistic regression is an
instance under the predictive modeling framework, where
${\mathsf{Y}}=\\{0,1\\}$, $W\in\mathbb{R}^{d}$ is assumed to be independent of
$X$, and the predictive model is specified by
$K_{Y|x,w}(1)=\sigma(w^{\top}\phi(x))$, with
$\sigma(a)\mathrel{\mathop{\mathchar 58\relax}}=1/(1+e^{-a})$,
$a\in\mathbb{R}$, being the logistic sigmoid function, and
$\phi(x)\in\mathbb{R}^{d}$ being the feature vector of the observation. For
the log loss, the optimal omniscient decision rule $\Psi^{*}(x,w)$ is the
Bernoulli distribution with bias $\sigma(w^{\top}\phi(x))$. Since $|\frac{\rm
d}{{\rm d}a}\log\sigma(a)|=|1-\sigma(a)|\leq 1$, from Theorem 8 we have

$\displaystyle{\rm
MER}_{\log}\leq\mathbf{E}[\|\phi(X)\|]\sqrt{2R_{2}(W|Z^{n})}.$ (88)

This result explicitly shows that the MER in logistic regression depends on
how well we can estimate the model parameters from data, as it is dominated by
$R_{2}(W|Z^{n})$, the MMSE of estimating $W$ from $Z^{n}$. For logistic
regression, a closed-form expression for this MMSE may not exist.
Nevertheless, any upper bound on it that is nonasymptotic in $d$ and $n$ will
translate to a nonasymptotic upper bound on the MER. In Section 4.3.3 we
continue the discussion of this example with different upper-bounding methods,
where the dependence on $R_{2}(W|Z^{n})$ can be improved when it is small.

####  4.1.2 Realizable models with additive noise

The smoothness of $\Psi^{*}(x,w)$ in $w$ can lead to potentially tighter MER
bounds under realizable models, possibly with additive noise. Consider the
generative model of the form $Y_{i}=g(X_{i},W)+V_{i}$ and $Y=g(X,W)+V$, where
the generative function $g\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow\mathbb{R}$ is some
parametric nonlinearity in general, which could be approximated by a
feedforward neural network, the parameter vector $W\in\mathbb{R}^{d}$ is
independent of $(X^{n},X)$, and the additive noise $(V^{n},V)$ are i.i.d.
real-valued random variables independent of $(W,X^{n},X)$. This model
encompasses both linear and nonlinear Bayesian regression problems. We have
the following MER bounds for the quadratic loss under this model.

######  Theorem 9.

Under the model considered above, for the quadratic loss,

$\displaystyle{\rm MER}_{2}$ $\displaystyle\leq 2R_{2}(g(X,W)|X,Z^{n})\leq
2\mathbf{E}\Big{[}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}g(X,w)\|^{2}\Big{]}R_{2}(W|Z^{n}).$
(89)

###### Proof.

Under the model considered above, for the quadratic loss,

$\displaystyle\Psi^{*}(X,W)=\mathbf{E}[g(X,W)+V|X,W]=g(X,W)+\mathbf{E}[V].$
(90)

We have

$\displaystyle{\rm MER}_{2}$
$\displaystyle\leq\mathbf{E}\big{[}(Y-g(X,W^{\prime})-\mathbf{E}[V])^{2}\big{]}-\mathbf{E}\big{[}(Y-g(X,W)-\mathbf{E}[V])^{2}\big{]}$
(91)
$\displaystyle=\mathbf{E}\big{[}(g(X,W^{\prime})-g(X,W))^{2}\big{]}+{\mathsf{var}}[V]-{\mathsf{var}}[V]$
(92) $\displaystyle=2R_{2}(g(X,W)|X,Z^{n})$ (93)
$\displaystyle\leq\mathbf{E}\Big{[}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}g(X,w)\|^{2}\cdot\|W^{\prime}-W\|^{2}\Big{]}$
(94)
$\displaystyle=2\mathbf{E}\Big{[}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}g(X,w)\|^{2}\Big{]}R_{2}(W|Z^{n}),$
(95)

where (91) follows from (52); (92) follows from the independence between
$(X,W)$ and $V$; (93) follows from the fact that $g(X,W^{\prime})$ and
$g(X,W)$ are conditionally independent given $(X,Z^{n})$, and Lemma 1; (94)
follows from (92) and Lemma 4; and (95) follows from the independence between
$X$ and $W$, and Lemma 1. ∎

##### Example: linear regression

Theorem 9 can be applied to bounding the MER of the linear regression problem
with the quadratic loss. Bayesian linear regression is an instance of the
noisy realizable model considered above, where $g(x,w)=w^{\top}\phi(x)$,
$\phi(x)\in\mathbb{R}^{d}$ is the feature vector of the observation $x$, and
$(V^{n},V)$ are i.i.d. samples from $\mathcal{N}(0,\sigma^{2})$. With the
Gaussian prior of model parameters
$P_{W}=\mathcal{N}(0,\sigma_{W}^{2}\mathbf{I}_{d})$, the MMSE for estimating
$W$ from $Z^{n}$ has a closed-form expression

$\displaystyle R_{2}(W|Z^{n})=\mathbf{E}[{\rm tr}(C_{W|Z^{n}})],$ (96)

where

$\displaystyle
C_{W|Z^{n}}=\Big{(}\frac{1}{\sigma_{W}^{2}}\mathbf{I}_{d}+\frac{1}{\sigma^{2}}\mathbf{\Phi}\mathbf{\Phi}^{\top}\Big{)}^{-1}$
(97)

is the conditional covariance matrix of $W$ given $Z^{n}$, which only depends
on $X^{n}$ through the $d\times n$ feature matrix
$\mathbf{\Phi}=[\phi(X_{1}),\ldots,\phi(X_{n})]$. Under this model, we also
have $\nabla_{w}g(x,w)=\phi(x)$, hence Theorem 9 implies that

$\displaystyle{\rm MER}_{2}\leq 2\mathbf{E}[\|\phi(X)\|^{2}]\mathbf{E}[{\rm
tr}(C_{W|Z^{n}})].$ (98)

Under the above model with Gaussian prior, it can be shown that the posterior
predictive distribution $P_{Y|x,z^{n}}$ is Gaussian with variance
$\sigma^{2}+\phi(x)^{\top}C_{W|z^{n}}\phi(x)$. From this we can obtain exact
expressions for the MER and alternative upper bounds:

$\displaystyle{\rm
MER}_{\log}=\frac{1}{2}\mathbf{E}\Big{[}\log\Big{(}1+\frac{1}{\sigma^{2}}\phi(X)^{\top}C_{W|Z^{n}}\phi(X)\Big{)}\Big{]}\leq\frac{\mathbf{E}[\|\phi(X)\|^{2}]}{2\sigma^{2}}\mathbf{E}[{\rm
tr}(C_{W|Z^{n}})],$ (99)

and

$\displaystyle{\rm
MER}_{2}=\mathbf{E}\big{[}\phi(X)^{\top}C_{W|Z^{n}}\phi(X)\big{]}\leq\mathbf{E}[\|\phi(X)\|^{2}]\mathbf{E}[{\rm
tr}(C_{W|Z^{n}})].$ (100)

The upper bounds in (99) and (100) are justified by noting that

$\displaystyle\phi(X)^{\top}C_{W|Z^{n}}\phi(X)=\|C_{W|Z^{n}}^{1/2}\phi(X)\|^{2}\leq\sigma_{1}^{2}\big{(}C_{W|Z^{n}}^{1/2}\big{)}\|\phi(X)\|^{2}\leq{\rm
tr}(C_{W|Z^{n}})\|\phi(X)\|^{2},$ (101)

where $\sigma_{1}(\cdot)$ is the largest singular value of the underlying
matrix. A special choice of the $d$ feature functions composing the feature
vector is such that they are orthonormal with respect to $P_{X}$, namely
$\int_{\mathsf{X}}\phi_{i}(x)\phi_{j}(x)P_{X}({\rm d}x)=\mathbf{1}\\{i=j\\}$
for $i,j\in\\{1,\ldots,d\\}$. In this case, $\Phi\Phi^{\top}\approx
n\mathbf{E}[\phi(X)\phi(X)^{\top}]=n\mathbf{I}_{d}$, hence $\mathbf{E}[{\rm
tr}(C_{W|Z^{n}})]\sim O(d/n)$, implying that ${\rm MER}_{2}$ scale with $d$
and $n$ as $O(d/n)$ according to (100). It further implies that the upper
bound (98) given by Theorem 9 is order-optimal for vanishing MER. We continue
the discussion of this example in Section 4.3.3.

###  4.2 Deviation of posterior predictive distribution from true predictive
model

Under the predictive modeling framework, the generative model is specified as
$P_{Z|W}=P_{X|W}K_{Y|X,W}$, with a parametrized probability transition kernel
$K_{Y|X,W}$ describing the true predictive model of $Y$ given $X$. An
alternative method for upper-bounding the MER under this framework is by
examining the deviation of the posterior predictive distribution
$P_{Y|X,Z^{n}}$ from the true predictive model $K_{Y|X,W}$ in terms of a
suitable convex statistical distance between them. Here, by a convex
statistical distance we mean any statistical distance $(P,Q)\mapsto D(P,Q)$
that is convex in the first argument when the second one is held fixed, or
convex in the second argument while the first one is held fixed. For example,
any $f$-divergence, including the commonly used total variation distance, KL
divergence and $\chi^{2}$-divergence, is jointly convex in both arguments
[50]. As another example, consider the $p$th power of $p$-Wasserstein distance
between two Borel probability measures $P$ and $Q$ on $\mathbb{R}^{m}$ with
finite second moments [51]:

$\displaystyle\mathcal{W}_{p}^{p}(P,Q)\mathrel{\mathop{\mathchar
58\relax}}=\inf_{\pi\in\Pi(P,Q)}\mathbf{E}_{(X,Y)\sim\pi}[\|X-Y\|^{p}],$ (102)

where $\Pi(P,Q)$ denotes the collection of all couplings of $P$ and $Q$, i.e.,
Borel probability measures on $\mathbb{R}^{m}\times\mathbb{R}^{m}$ with
marginals $P$ and $Q$. As shown in Lemma 3 in Appendix A.4,
$(P,Q)\mapsto\mathcal{W}_{p}^{p}(P,Q)$ is also jointly convex. The following
lemma is key for relating the deviation of $P_{Y|X,Z^{n}}$ from $K_{Y|X,W}$ to
the estimation error of model parameters.

######  Lemma 2.

Let $W^{\prime}$ be a sample from the posterior distribution $P_{W|X,Z^{n}}$,
such that $W$ and $W^{\prime}$ are conditionally i.i.d. given $(X,Z^{n})$.
Then for any $(w,x,z^{n})$ and any statistical distance $D$ that is convex in
the first argument,

$\displaystyle
D(P_{Y|x,z^{n}},K_{Y|x,w})\leq\mathbf{E}[D(K_{Y|x,W^{\prime}},K_{Y|x,w})|x,z^{n}],$
(103)

and consequently,

$\displaystyle\mathbf{E}[D(P_{Y|X,Z^{n}},K_{Y|X,W})]\leq\mathbf{E}[D(K_{Y|X,W^{\prime}},K_{Y|X,W})]$
(104)

where the expectations are taken with respect to the joint distribution of
$(W,X,Z^{n},W^{\prime})$. Similarly, for any $(w,x,z^{n})$ and any statistical
distance $D$ that is convex in the second argument,

$\displaystyle
D(K_{Y|x,w},P_{Y|x,z^{n}})\leq\mathbf{E}[D(K_{Y|x,w},K_{Y|x,W^{\prime}})|x,z^{n}],$
(105)

and consequently,

$\displaystyle\mathbf{E}[D(K_{Y|X,W},P_{Y|X,Z^{n}})]\leq\mathbf{E}[D(K_{Y|X,W},K_{Y|X,W^{\prime}})].$
(106)

###### Proof.

From the joint distribution in (1), it follows that for any $(w,z^{n},z)$,

$\displaystyle P_{Y|x,z^{n}}(y)$
$\displaystyle=\int_{{\mathsf{W}}}K_{Y|x,w^{\prime}}(y)P_{W|x,z^{n}}({\rm
d}w^{\prime})$ (107)

If the statistical distance considered here is convex in the first argument,
we have

$\displaystyle
D(P_{Y|x,z^{n}},K_{Y|x,w})\leq\int_{{\mathsf{W}}}D(K_{Y|x,w^{\prime}},K_{Y|x,w})P_{W|x,z^{n}}({\rm
d}w^{\prime}),$ (108)

which proves (103). Taking expectations over the conditioning terms, we obtain
(104). The proof of (105) and (106) follows the same argument when $D$ is
convex in the second argument. ∎

Whenever the convex statistical distance $D(K_{Y|x,w^{\prime}},K_{Y|x,w})$ can
be upper-bounded via $\|w^{\prime}-w\|$ or $\|w^{\prime}-w\|^{2}$, Lemma 1 can
be used to further upper-bound $\mathbf{E}[D(K_{Y|X,W^{\prime}},K_{Y|X,W})]$
in terms of the minimum achievable estimation error of $W$. In the following
two subsections, we use two different methods together with Lemma 2 and Lemma
1 to convert upper bounds on the deviation of $P_{Y|X,Z^{n}}$ from $K_{Y|X,W}$
into upper bounds on the MER for various loss functions.

###  4.3 From deviation of posterior predictive distribution to MER bound

####  4.3.1 Via conditional mutual information upper bound

For the log loss, we can directly upper-bound $I(W;Y|X,Z^{n})$ in terms of the
KL divergence between $K_{Y|X,W}$ and $P_{Y|X,Z^{n}}$, and arrive at the
following result with Lemma 2.

######  Theorem 10.

When $P_{Z|W}=P_{X|W}K_{Y|X,W}$, let $W^{\prime}$ be a sample from the
posterior distribution $P_{W|X,Z^{n}}$, conditionally independent of
everything else given $(X,Z^{n})$. Then,

$\displaystyle{\rm MER}_{\log}$ $\displaystyle\leq\mathbf{E}[D_{\rm
KL}(K_{Y|X,W}\|K_{Y|X,W^{\prime}})]$ (109)

where the expectation is taken with respect to the joint distribution of
$(W,W^{\prime},X)$.

###### Proof.

From (17), we have

$\displaystyle{\rm MER}_{\log}$ $\displaystyle=I(W;Y|X,Z^{n})$ (110)
$\displaystyle=\mathbf{E}[D_{\rm KL}(P_{Y|X,Z^{n},W}\|P_{Y|X,Z^{n}})]$ (111)
$\displaystyle=\mathbf{E}[D_{\rm KL}(P_{Y|X,W}\|P_{Y|X,Z^{n}})]$ (112)
$\displaystyle\leq\mathbf{E}[D_{\rm KL}(K_{Y|X,W}\|K_{Y|X,W^{\prime}})],$
(113)

where (112) follows from the fact that $Y$ is conditionally independent of
$Z^{n}$ given $(X,W)$; and (113) is from Lemma 2 and the fact that $D_{\rm
KL}(P\|Q)$ is convex in $Q$ for a fixed $P$. ∎

In Section 4.3.3 we continue with the example of logistic regression, where
Theorem 10 can be used with Lemma 1 to bound the MER in terms of the MMSE of
estimating $W$ from data.

####  4.3.2 Via continuity of generalized entropy

The second method for relating the MER to the deviation of posterior
predictive distribution is directly comparing $R_{\ell}(Y|X,Z^{n})$ against
$R_{\ell}(Y|X,W)$, via the distributional continuity of the generalized
entropy. We examine classification and regression problems separately.

##### Classification

For classification problems where ${\mathsf{Y}}$ is finite, we consider both
the soft classification with the log loss and the hard classification with the
zero-one loss. The MER upper bounds rely on the continuity properties of the
Shannon entropy and the maximal probability, respectively, as stated in the
following lemma, with proofs provided in Appendix A.6. For more general
discussions on the continuity of generalized entropy, the reader may refer to
[52, 53].

######  Lemma 3.

Let $P$ and $Q$ be distributions on a finite set ${\mathsf{Y}}$ such that
$\min_{y\in{\mathsf{Y}}}Q(y)>0$. Then

$\displaystyle
H(P)-H(Q)\leq\big{(}-\log{\min_{y\in{\mathsf{Y}}}Q(y)}\big{)}d_{\rm TV}(P,Q),$
(114)
$\displaystyle\max_{y\in{\mathsf{Y}}}Q(y)-\max_{y\in{\mathsf{Y}}}P(y)\leq
d_{\rm TV}(P,Q),$ (115)

where $d_{\rm TV}(P,Q)\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{2}\sum_{y\in{\mathsf{Y}}}|P(y)-Q(y)|$ is the total
variation distance between $P$ and $Q$.

Compared with the well-known Shannon entropy difference bound in terms of the
total variation distance $|H(P)-H(Q)|\leq 2d_{\rm
TV}(P,Q)\log({|{\mathsf{Y}}|}/2d_{\rm TV}(P,Q))$ when $d_{\rm
TV}(P,Q)\leq{1}/{4}$ [31, Theorem 17.3.3], the bound given in (114) is not as
tight in $|{\mathsf{Y}}|$, but is tighter in $d_{\rm TV}(P,Q)$, which leads to
sharper MER bounds when the data size is large. Armed with Lemma 3 and Lemma
2, we have the following MER bounds for classification problems.

######  Theorem 11.

If ${\mathsf{Y}}$ is finite, then for the log loss,

$\displaystyle{\rm
MER}_{\log}\leq\sup_{x\in{\mathsf{X}},\,w\in{\mathsf{W}}}(-\log\kappa(x,w))\mathbf{E}[d_{\rm
TV}(K_{Y|X,W^{\prime}},K_{Y|X,W})],$ (116)

where $\kappa(x,w)\mathrel{\mathop{\mathchar
58\relax}}=\min_{y\in{\mathsf{Y}}}K_{Y|x,w}(y)$, $W^{\prime}$ is a sample from
$P_{W|X,Z^{n}}$, conditionally independent of everything else given
$(X,Z^{n})$, and the expectation is with respect to $P_{W,W^{\prime},X}$. In
addition, for the zero-one loss,

$\displaystyle{\rm MER}_{01}$ $\displaystyle\leq\mathbf{E}[d_{\rm
TV}(K_{Y|X,W^{\prime}},K_{Y|X,W})].$ (117)

###### Proof.

When ${\mathsf{Y}}$ is finite, for the log loss,

$\displaystyle{\rm MER}_{\log}$ $\displaystyle=H(Y|X,Z^{n})-H(Y|X,W)$ (118)
$\displaystyle=\int\big{(}H(Y|x,z^{n})-H(Y|x,w)\big{)}P({\rm d}w,{\rm d}x,{\rm
d}z^{n})$ (119)
$\displaystyle\leq\int\Big{(}-\log{\min_{y\in{\mathsf{Y}}}K_{Y|x,w}(y)}\Big{)}d_{\rm
TV}(P_{Y|x,z^{n}},P_{Y|x,w})P({\rm d}w,{\rm d}x,{\rm d}z^{n})$ (120)
$\displaystyle\leq\sup_{w\in{\mathsf{W}},x\in{\mathsf{X}}}\big{(}-\log{\min\nolimits_{y\in{\mathsf{Y}}}K_{Y|x,w}(y)}\big{)}\mathbf{E}\big{[}d_{\rm
TV}(P_{Y|X,Z^{n}},P_{Y|X,W})\big{]}$ (121)
$\displaystyle\leq\sup_{w\in{\mathsf{W}},x\in{\mathsf{X}}}\big{(}-\log{\min\nolimits_{y\in{\mathsf{Y}}}K_{Y|x,w}(y)}\big{)}\mathbf{E}\big{[}d_{\rm
TV}(P_{Y|X,W^{\prime}},P_{Y|X,W})\big{]}$ (122)

where (120) follows from Lemma 3; and (122) follows from Lemma 2.

For the zero-one loss,

$\displaystyle{\rm MER}_{01}$
$\displaystyle=\mathbf{E}[\max\nolimits_{y\in{\mathsf{Y}}}K_{Y|X,W}(y)]-\mathbf{E}[\max\nolimits_{y\in{\mathsf{Y}}}P_{Y|X,Z^{n}}(y)]$
(123)
$\displaystyle=\int\big{(}\max\nolimits_{y\in{\mathsf{Y}}}K_{Y|x,w}(y)-\max\nolimits_{y\in{\mathsf{Y}}}P_{Y|x,z^{n}}(y)\big{)}P({\rm
d}w,{\rm d}x,{\rm d}z^{n})$ (124) $\displaystyle\leq\int d_{\rm
TV}(K_{Y|x,w},P_{Y|x,z^{n}})P({\rm d}w,{\rm d}x,{\rm d}z^{n})$ (125)
$\displaystyle\leq\mathbf{E}[d_{\rm TV}(K_{Y|X,W},K_{Y|X,W^{\prime}})]$ (126)

where (125) follows from Lemma 3, and (126) follows from Lemma 2. ∎

##### Regression

Next, we consider regression problems with ${\mathsf{Y}}\subset\mathbb{R}^{p}$
under the assumption that both the marginal and various conditional
distributions of $Y$ are absolutely continuous with respect to the Lebesgue
measure. We consider both the soft prediction with the log loss, and the hard
prediction with the quadratic loss. For the soft setting, ${\rm MER}_{\log}$
can be upper-bounded using the continuity of differential entropy with respect
to the Wasserstein distance, as stated in the following lemma.

######  Lemma 4 ([54]).

Let $U$ be a random vector in $\mathbb{R}^{p}$ with finite
$\mathbf{E}[\|U\|^{2}]$, and $V$ be a Gaussian random vector in
$\mathbb{R}^{p}$ with covariance matrix $\sigma^{2}\mathbf{I}_{p}$. Then

$\displaystyle h(U)-h(V)$
$\displaystyle\leq\frac{1}{2\sigma^{2}}\big{(}3\sqrt{\mathbf{E}[\|U\|^{2}]}+11\sqrt{\mathbf{E}[\|V\|^{2}]}\big{)}\mathcal{W}_{2}(P_{U},P_{V})$
(127)

where $\mathcal{W}_{2}(P_{U},P_{V})$ is the $2$-Wasserstein distance between
$P_{U}$ and $P_{V}$.

With Lemma 4 and Lemma 2, we have the following bound for regression with the
log loss.

######  Theorem 12.

If ${\mathsf{Y}}=\mathbb{R}^{p}$, and $K_{Y|x,w}$ is Gaussian with covariance
matrix $\sigma^{2}\mathbf{I}_{p}$ for all $(x,w)$, then for the log loss,

$\displaystyle{\rm MER}_{\log}$
$\displaystyle\leq\frac{7}{\sigma^{2}}\sqrt{\mathbf{E}\big{[}\|Y\|^{2}\big{]}\mathbf{E}[\mathcal{W}_{2}^{2}(K_{Y|X,W^{\prime}},K_{Y|X,W})]},$
(128)

where $W$ and $W^{\prime}$ are conditionally i.i.d. given $(X,Z^{n})$, and the
expectation is with respect to $P_{X,W,W^{\prime}}$.

###### Proof.

For the log loss,

$\displaystyle{\rm MER}_{\log}$ $\displaystyle=h(Y|X,Z^{n})-h(Y|X,W)$ (129)
$\displaystyle=\int\big{(}h(Y|x,z^{n})-h(Y|x,w)\big{)}P({\rm d}w,{\rm d}x,{\rm
d}z^{n})$ (130)
$\displaystyle\leq\int\Big{(}\frac{3}{2\sigma^{2}}\sqrt{\mathbf{E}\big{[}\|Y\|^{2}|x,z^{n}\big{]}}+\frac{11}{2\sigma^{2}}\sqrt{\mathbf{E}\big{[}\|Y\|^{2}|x,w\big{]}}\Big{)}$
$\displaystyle\qquad\quad\mathcal{W}_{2}(P_{Y|x,z^{n}},K_{Y|x,w})P({\rm
d}w,{\rm d}x,{\rm d}z^{n})$ (131)
$\displaystyle\leq\left(\int\Big{(}\frac{3}{2\sigma^{2}}\sqrt{\mathbf{E}\big{[}\|Y\|^{2}|x,z^{n}\big{]}}+\frac{11}{2\sigma^{2}}\sqrt{\mathbf{E}\big{[}\|Y\|^{2}|x,w\big{]}}\Big{)}^{2}P({\rm
d}w,{\rm d}x,{\rm d}z^{n})\right)^{1/2}$
$\displaystyle\quad\,\left(\int\mathcal{W}_{2}^{2}(P_{Y|x,z^{n}},K_{Y|x,w})P({\rm
d}w,{\rm d}x,{\rm d}z^{n})\right)^{1/2}$ (132)
$\displaystyle\leq\frac{7}{\sigma^{2}}\big{(}\mathbf{E}\big{[}\|Y\|^{2}\big{]}\big{)}^{1/2}\left(\int\mathcal{W}_{2}^{2}(P_{Y|x,z^{n}},K_{Y|x,w})P({\rm
d}w,{\rm d}x,{\rm d}z^{n})\right)^{1/2}$ (133)
$\displaystyle\leq\frac{7}{\sigma^{2}}\sqrt{\mathbf{E}\big{[}\|Y\|^{2}\big{]}\mathbf{E}[\mathcal{W}_{2}^{2}(K_{Y|X,W^{\prime}},K_{Y|X,W})]\big{)}}.$
(134)

where (131) follows from Lemma 4; (132) follows from Cauchy-Schwarz
inequality; (133) follows from the triangle inequality of the $L_{2}$ norm,
which states that
$\sqrt{\mathbf{E}[(U+V)^{2}]}\leq\sqrt{\mathbf{E}[U^{2}]}+\sqrt{\mathbf{E}[V^{2}]}$;
and (134) follows from Lemma 2 and Lemma 3. ∎

For the hard setting, in scalar regression problems with
${\mathsf{Y}}={\mathsf{A}}=\mathbb{R}$ and the quadratic loss, the MER as
given by (34) is the expected difference between two variances. The following
results relate the variance difference between two probability distributions
to their $2$-Wasserstein distance and KL divergence respectively.

######  Lemma 5 ([55], proof given in Appendix A.7).

Let $U$ and $V$ be random variables over a set ${\mathsf{U}}\subset\mathbb{R}$
with finite $\mathbf{E}[U^{2}]$ and $\mathbf{E}[V^{2}]$. Then,

$\displaystyle|{\mathsf{var}}[U]-{\mathsf{var}}[V]|\leq
2\big{(}\sqrt{\mathbf{E}[U^{2}]}+\sqrt{\mathbf{E}[V^{2}]}\big{)}\mathcal{W}_{2}(P_{U},P_{V}).$
(135)

When $V$ is Gaussian with variance $\sigma^{2}$, Lemma 5 with Talagrand’s
inequality [56] states that

$\displaystyle|{\mathsf{var}}[U]-{\mathsf{var}}[V]|\leq
2\big{(}\sqrt{\mathbf{E}[U^{2}]}+\sqrt{\mathbf{E}[V^{2}]}\big{)}\sqrt{2\sigma^{2}D_{\rm
KL}(P_{U}\|P_{V})};$ (136)

under the same condition, we also have a potentially tighter bound [53]:

$\displaystyle|{\mathsf{var}}[U]-{\mathsf{var}}[V]|\leq
2\sigma^{2}\big{(}\sqrt{D_{\rm KL}(P_{U}\|P_{V})}+D_{\rm
KL}(P_{U}\|P_{V})\big{)}.$ (137)

With Lemma 5, we can derive the following upper bounds for ${\rm MER}_{2}$.

######  Theorem 13.

For regression problems with ${\mathsf{Y}}=\mathbb{R}$, if
$\mathbf{E}[Y^{2}|x,w]$ is finite for all $(x,w)$, then for the quadratic
loss,

$\displaystyle{\rm MER}_{2}$ $\displaystyle\leq
4\sqrt{\mathbf{E}[Y^{2}]\mathbf{E}[\mathcal{W}_{2}^{2}(K_{Y|X,W^{\prime}},K_{Y|X,W})]},$
(138)

where $W^{\prime}$ is a sample from $P_{W|X,Z^{n}}$, conditionally independent
of everything given $(X,Z^{n})$.

###### Proof.

Similar to the proof of Theorem 12, for the quadratic loss, we have

$\displaystyle{\rm MER}_{2}$
$\displaystyle=\int\big{(}{\mathsf{var}}[Y|x,z^{n}]-{\mathsf{var}}[Y|x,w]\big{)}P({\rm
d}w,{\rm d}x,{\rm d}z^{n})$ (139) $\displaystyle\leq
2\int\big{(}\sqrt{\mathbf{E}[Y^{2}|x,z^{n}]}+\sqrt{\mathbf{E}[Y^{2}|x,w]}\big{)}\mathcal{W}_{2}(P_{Y|x,z^{n}},K_{Y|x,w})P({\rm
d}w,{\rm d}x,{\rm d}z^{n})$ (140) $\displaystyle\leq
2\left(\int\big{(}\sqrt{\mathbf{E}[Y^{2}|x,z^{n}]}+\sqrt{\mathbf{E}[Y^{2}|x,w]}\big{)}^{2}P({\rm
d}w,{\rm d}x,{\rm d}z^{n})\right)^{1/2}\cdot$
$\displaystyle\qquad\\!\left(\int\mathcal{W}_{2}^{2}(P_{Y|x,z^{n}},K_{Y|x,w})P({\rm
d}w,{\rm d}x,{\rm d}z^{n})\right)^{1/2}$ (141) $\displaystyle\leq
4\sqrt{\mathbf{E}[Y^{2}]\mathbf{E}[\mathcal{W}_{2}^{2}(P_{Y|X,Z^{n}},K_{Y|X,W})]}$
(142) $\displaystyle\leq
4\sqrt{\mathbf{E}[Y^{2}]\mathbf{E}[\mathcal{W}_{2}^{2}(P_{Y|X,W^{\prime}},K_{Y|X,W})]}.$
(143)

where (140) follows from Lemma 5; (141) follows from Cauchy-Schwarz
inequality; (142) follows from the triangle inequality of the $L_{2}$ norm;
and (143) follows from Lemma 2 and Lemma 3. ∎

In Section 4.3.3 we make use of Theorem 11, 12 and 13 with Lemma 1 to bound
the MER in concrete learning problems in terms of the MMSE of estimating $W$
from data.

####  4.3.3 Examples

##### Logistic regression (continued)

We continue with the example of logistic regression discussed in Section
4.1.1, where ${\mathsf{Y}}=\\{0,1\\}$, ${\mathsf{W}}\subset\mathbb{R}^{d}$,
$K_{Y|x,w}(1)=\sigma(w^{\top}\phi(x))$ with
$\sigma(a)\mathrel{\mathop{\mathchar 58\relax}}=1/(1+e^{-a})$, and $X$ is
assumed to be independent of $W$. As
$\|\nabla_{w}\sigma(w^{\top}\phi(x))\|\leq\|\phi(x)\|/4$, from Lemma 4 we know
that $\sigma(w^{\top}\phi(x))$ is $\|\phi(x)\|/4$-Lipschitz in $w$, hence

$\displaystyle d_{\rm
TV}(K_{Y|x,w^{\prime}},K_{Y|x,w})=\big{|}\sigma(w^{\prime\top}\phi(x))-\sigma(w^{\top}\phi(x))\big{|}\leq\frac{1}{4}\|\phi(x)\|\|w^{\prime}-w\|.$
(144)

Then, from Theorem 10, Theorem 11 and Lemma 1, the following bounds hold for
the log loss and the zero-one loss.

######  Corollary 6.

In binary logistic regression, for the log loss,

$\displaystyle{\rm MER}_{\log}$
$\displaystyle\leq\log\Big{(}1+\frac{1}{2}s_{\phi}^{2}e^{s_{\phi}s_{\mathsf{W}}}R_{2}(W|Z^{n})\Big{)}$
(145)

where $s_{\phi}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{x\in{\mathsf{X}}}\|\phi(x)\|$ and
$s_{\mathsf{W}}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{w\in{\mathsf{W}}}\|w\|$; while for the zero-one loss,

$\displaystyle{\rm MER}_{01}$
$\displaystyle\leq\frac{1}{4}\mathbf{E}[\|\phi(X)\|]\sqrt{2R_{2}(W|Z^{n})}.$
(146)

###### Proof.

For the log loss, from Theorem 10,

$\displaystyle{\rm MER}_{\log}$ $\displaystyle\leq\mathbf{E}\big{[}D_{\rm
KL}(K_{Y|X,W}\|K_{Y|X,W^{\prime}})\big{]}$ (147)
$\displaystyle\leq\mathbf{E}\Big{[}\log\Big{(}1+\frac{2d_{\rm
TV}^{2}(K_{Y|X,W},K_{Y|X,W^{\prime}})}{\min\\{\sigma(W^{\prime\top}\phi(X)),1-\sigma(W^{\prime\top}\phi(X))\\}}\Big{)}\Big{]}$
(148)
$\displaystyle\leq\mathbf{E}\Big{[}\log\Big{(}1+4e^{|W^{\prime\top}\phi(X)|}{d_{\rm
TV}^{2}(K_{Y|X,W},K_{Y|X,W^{\prime}})}\Big{)}\Big{]}$ (149)
$\displaystyle\leq\mathbf{E}\Big{[}\log\Big{(}1+\frac{1}{4}e^{s_{\phi}s_{\mathsf{W}}}s_{\phi}^{2}\|W-W^{\prime}\|^{2}\Big{)}\Big{]}$
(150)
$\displaystyle\leq\log\Big{(}1+\frac{1}{2}e^{s_{\phi}s_{\mathsf{W}}}s_{\phi}^{2}R_{2}(W|Z^{n}))\Big{)}$
(151)
$\displaystyle\leq\frac{1}{2}s_{\phi}^{2}e^{s_{\phi}s_{\mathsf{W}}}R_{2}(W|Z^{n})$
(152)

where we used a reverse Pinsker’s inequality [57, Theorem 28], the fact that
$\max\\{1/\sigma(w^{\top}\phi(x)),1/(1-\sigma(w^{\top}\phi(x)))\\}\leq
2\exp\\{|w^{\top}\phi(x)|\\}$, $d_{\rm
TV}(K_{Y|x,w^{\prime}},K_{Y|x,w})\leq\|\phi(x)\|\|w^{\prime}-w\|/4$ from
(144), Jensen’s inequality, and Lemma 1.

For the zero-one loss, from Theorem 11,

$\displaystyle{\rm MER}_{01}$ $\displaystyle\leq\mathbf{E}[d_{\rm
TV}(K_{Y|X,W^{\prime}},K_{Y|X,W})]$ (153)
$\displaystyle\leq\frac{1}{4}\mathbf{E}\big{[}\|\phi(X)\|\|W^{\prime}-W\|\big{]}$
(154)
$\displaystyle\leq\frac{1}{4}\mathbf{E}[\|\phi(X)\|]\sqrt{\mathbf{E}\big{[}\|W^{\prime}-W\|^{2}\big{]}}$
(155) $\displaystyle=\frac{1}{4}\mathbf{E}[\|\phi(X)\|]\sqrt{2R_{2}(W|Z^{n})}$
(156)

where we used (144) and Lemma 1. ∎

The upper bound in (145) shows that the rate of convergence of $\rm
MER_{\log}$ in $n$ for logistic regression is the same as that for
$R_{2}(W|Z^{n})$, as $\log(1+u)\leq u$ for $u>0$. This improves the upper
bound given in (88) when $R_{2}(W|Z^{n})$ is small, e.g., when $n$ is large.

##### Nonlinear and linear regression (continued)

We also continue with the discussion on the nonlinear and linear regression
problems in Section 4.1.2, where $Y=g(X,W)+V$, ${\mathsf{W}}=\mathbb{R}^{d}$,
$X$ and $W$ are independent, and $V\sim\mathcal{N}(0,\sigma^{2})$ is
independent of $(X,W)$. Under this model,

$\displaystyle\mathcal{W}_{2}^{2}(K_{Y|x,w^{\prime}},K_{Y|x,w})=2\sigma^{2}D_{\rm
KL}(K_{Y|x,w^{\prime}}\|K_{Y|x,w})=(g(x,w)-g(x,w^{\prime}))^{2}.$ (157)

From Theorem 10, Theorem 13 and Lemma 1, we obtain the following upper bounds
for nonlinear regression.

######  Corollary 7.

For the above nonlinear regression problem, let
$s_{g}\mathrel{\mathop{\mathchar
58\relax}}=\mathbf{E}\big{[}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}g(X,w)\|^{2}\big{]}$.
Then for the log loss,

$\displaystyle{\rm MER}_{\log}$
$\displaystyle\leq\frac{1}{\sigma^{2}}R_{2}(g(X,W)|X,Z^{n})\leq\frac{s_{g}}{\sigma^{2}}R_{2}(W|Z^{n}),$
(158)

while for the quadratic loss,

$\displaystyle{\rm MER}_{2}$ $\displaystyle\leq
4\sqrt{2(\mathbf{E}[g(X,W)^{2}]+\sigma^{2})R_{2}(g(X,W)|X,Z^{n})}$ (159)
$\displaystyle\leq
4\sqrt{2(\mathbf{E}[g(X,W)^{2}]+\sigma^{2})s_{g}R_{2}(W|Z^{n})}.$ (160)

###### Proof.

For the log loss,

$\displaystyle{\rm MER}_{\log}$ $\displaystyle\leq\mathbf{E}[D_{\rm
KL}(K_{Y|X,W}\|K_{Y|X,W^{\prime}})]$ (161)
$\displaystyle=\frac{1}{2\sigma^{2}}\mathbf{E}\big{[}\big{(}g(X,W)-g(X,W^{\prime})\big{)}^{2}\big{]}$
(162) $\displaystyle=\frac{1}{\sigma^{2}}R_{2}(g(X,W)|X,Z^{n})$ (163)
$\displaystyle\leq\frac{1}{2\sigma^{2}}\mathbf{E}\big{[}(\sup\nolimits_{w\in{\mathsf{W}}}\|\nabla_{w}g(X,w)\|)^{2}\|W-W^{\prime}\|^{2}\big{]}$
(164)
$\displaystyle=\frac{1}{\sigma^{2}}\mathbf{E}\big{[}\sup\nolimits_{w\in{\mathsf{W}}}\|\nabla_{w}g(X,w)\|^{2}\big{]}R_{2}(W|Z^{n}).$
(165)

where (161) follows from Theorem 10; (162) is from (157); (163) is due to
Lemma 1 for the quadratic loss; (164) is due to (162) and Lemma 4; and (165)
follows from Lemma 1.

For the quadratic loss, from Theorem 13, (157) and Lemma 1, and a similar
reasoning as above,

$\displaystyle{\rm MER}_{2}$ $\displaystyle\leq
4\sqrt{\mathbf{E}[Y^{2}]\mathbf{E}[\big{(}g(X,W)-g(X,W^{\prime})\big{)}^{2}]}$
(166) $\displaystyle=4\sqrt{2\mathbf{E}[Y^{2}]R_{2}(g(X,W)|X,Z^{n})}$ (167)
$\displaystyle\leq
4\sqrt{2\mathbf{E}[Y^{2}]\mathbf{E}\big{[}\sup\nolimits_{w\in{\mathsf{W}}}\|\nabla_{w}g(X,w)\|^{2}\big{]}R_{2}(W|Z^{n})}$
(168)
$\displaystyle=4\sqrt{2\big{(}\mathbf{E}[g(W,X)^{2}]+\sigma^{2}\big{)}s_{g}R_{2}(W|Z^{n})},$
(169)

which proves the second upper bound. ∎

For the special case of linear regression with Gaussian prior
$P_{W}=\mathcal{N}(0,\sigma_{W}^{2}\mathbf{I}_{d})$, we have
$g(x,w)=w^{\top}\phi(x)$, $s_{g}=\mathbf{E}[\|\phi(X)\|^{2}]$, and
$R_{2}(W|Z^{n})=\mathbf{E}[{\rm tr}(C_{W|Z^{n}})]$ with $C_{W|Z^{n}}$ given in
(97); Corollary 7 in this case gives

$\displaystyle{\rm MER}_{\log}$
$\displaystyle\leq\frac{1}{\sigma^{2}}\mathbf{E}[\|\phi(X)\|^{2}]\mathbf{E}[{\rm
tr}(C_{W|Z^{n}})],$ (170)

and

$\displaystyle{\rm MER}_{2}$ $\displaystyle\leq
4\sqrt{2\big{(}\sigma_{W}^{2}\mathbf{E}[\|\phi(X)\|^{2}]+\sigma^{2}\big{)}\mathbf{E}[\|\phi(X)\|^{2}]\mathbf{E}[{\rm
tr}(C_{W|X^{n},Y^{n}})]}.$ (171)

From the exact expressions of MER given in (99) and (100), we see that the
upper bound for ${\rm MER}_{\log}$ in (170) is order-optimal for vanishing
MER; while the upper bound for ${\rm MER}_{2}$ in (171) is not, unlike the
upper bound (98) for ${\rm MER}_{2}$ given by Theorem 9. In Appendix B, we
derive an alternative upper bound for $\rm MER_{2}$ based on Theorem 6 in
Section 3.4, however it is not order-optimal either. Nevertheless, the upper
bound in (171) can be tighter than the order-optimal upper bound in (98) when
$R_{2}(W|Z^{n})$ is large, e.g., when $n$ is small.

We also see from Theorem 9 and Corollary 7 that the MER upper bounds for the
general nonlinear regression problem depend on $n$ only through
$R_{2}(g(X,W)|X,Z^{n})$ or $R_{2}(W|Z^{n})$. Although closed-form expressions
of these quantities are generally intractable, the upper bounds explicitly
show how the epistemic part of the overall prediction uncertainty depends on
the model uncertainty, which can be quantified by the corresponding MMSE.
Moreover, the upper bounds obtained in terms of $R_{2}(g(X,W)|X,Z^{n})$ can be
much tighter than those in terms of $R_{2}(W|Z^{n})$, especially when multiple
values of $W$ map to the same function $g(\cdot,W)$, e.g., when
$g\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{Y}}$ can be
represented by over-parametrized neural networks [58].

##  5 Extensions

###  5.1 Multiple model families

Instead of being described by a single model family, in many cases the joint
distribution of $X$ and $Y$ can be better represented by a finite class of
model families ${\mathbb{M}}=\\{{\mathcal{M}}_{m},m\in{\mathsf{M}}\\}$ all
together, where each family
${\mathcal{M}}_{m}=\\{P_{X,Y|w,m},w\in{\mathsf{W}}_{m}\\}$ is a collection of
parametrized joint distributions of $(X,Y)$. The class of model families
$\mathbb{M}$ is also known as the _model class_ , and the index $m$ of each
family is also known as the _model index_ [59]. In the Bayesian formulation,
the model index $M$ is treated as a random element of ${\mathsf{M}}$ with
prior $P_{M}$; given a model index $m$, the model parameters are represented
as a random vector in ${\mathsf{W}}_{m}$ with prior $P_{W|m}$. As before,
denoting $Z_{i}\mathrel{\mathop{\mathchar 58\relax}}=(X_{i},Y_{i})$,
$i=1,\ldots,n$, as the observed data and $Z\mathrel{\mathop{\mathchar
58\relax}}=(X,Y)$ as a fresh pair, the quantities under consideration are
assumed to be generated from the joint distribution

$\displaystyle
P_{M,W,Z^{n},Z}=P_{M}P_{W|M}\Big{(}\prod\limits_{i=1}^{n}P_{Z_{i}|W,M}\Big{)}P_{Z|W,M}$
(172)

where $P_{Z_{i}|W,M}=P_{Z|W,M}$ for $i=1,\ldots,n$. In the same spirit in the
single model family setting, we can define the MER in the above multi-model
family setting as follows.

######  Definition 4.

In the multi-model family setting, the fundamental limit of the Bayes risk
with respect to the loss function $\ell$ is defined as

$\displaystyle R_{\ell}(Y|X,W,M)=\inf_{\Psi\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{W}}\times{\mathsf{M}}\rightarrow{\mathsf{A}}}\mathbf{E}[\ell(Y,\Psi(X,W,M))].$
(173)

######  Definition 5.

In the multi-model family setting, the minimum excess risk with respect to the
loss function $\ell$ is defined as

$\displaystyle{\rm MER}_{\ell}=R_{\ell}(Y|X,Z^{n})-R_{\ell}(Y|X,W,M).$ (174)

Similar to Lemma 1 and Theorem 10 in the single model family setting, for the
log loss, the MER in the multi-model family setting can be related to the
conditional mutual information $I(M,W;Y|X,Z^{n})$ and its upper bounds.

######  Theorem 14.

In the multi-model family setting, with the log loss,

$\displaystyle{\rm MER}_{\log}=I(M,W;Y|X,Z^{n}),$ (175)

which can be upper-bounded by $\frac{1}{n}I(M,W;Y^{n}|X^{n}).$ Further, if
$P_{X,Y|w,m}=P_{X|w,m}K_{Y|X,w,m}$ for all
$(m,w)\in{\mathsf{M}}\times{\mathsf{W}}_{m}$, then

$\displaystyle{\rm MER}_{\log}\leq\mathbf{E}[D_{\rm
KL}(K_{Y|X,W,M}\|K_{Y|X,W^{\prime},M^{\prime}})],$ (176)

where $(M^{\prime},W^{\prime})$ is a sample from the posterior distribution
$P_{M,W|X,Z^{n}}$ such that $(M,W)$ and $(M^{\prime},W^{\prime})$ are
conditionally i.i.d. given $(X,Z^{n})$.

In addition, we can still bound the MER in terms of the deviation of the
posterior predictive distribution from the true predictive model, similar to
the results in Section 4.3. As in the predictive modeling framework, suppose
that for each model family $\mathcal{M}_{m}\in\mathbb{M}$,
$P_{X,Y|w,m}=P_{X|w,m}K_{Y|X,w,m}$ for all $w\in{\mathsf{W}}_{m}$. Then for
any statistical distance $D$, a diameter-like quantity of the model class
$\mathbb{M}$ with respect to $\\!D$ can be defined as

$\displaystyle{\rm diam}(\mathbb{M},D)=\max_{m\neq
m^{\prime}\in{\mathsf{M}}}\sup_{w\in{\mathsf{W}}_{m},w^{\prime}\in{\mathsf{W}}_{m^{\prime}}}\sup_{x\in{\mathsf{X}}}D(K_{Y|x,w^{\prime},m^{\prime}},K_{Y|x,w,m}).$
(177)

With the above definition we have the following general upper bound on the
deviation of the posterior predictive distribution from the true predictive
model. The proof is given in Appendix C.

######  Theorem 15.

In the multi-model setting, for any statistical distance $D$ that is convex in
the first argument,

$\displaystyle\mathbf{E}[D(P_{Y|X,Z^{n}},K_{Y|X,W,M})]\leq\mathbf{E}[D(K_{Y|X,W^{\prime},M^{\prime}},K_{Y|X,W,M})],$
(178)

where $(M^{\prime},W^{\prime})$ is a sample from the posterior distribution
$P_{M,W|X,Z^{n}}$ such that $(M,W)$ and $(M^{\prime},W^{\prime})$ are
conditionally i.i.d. given $(X,Z^{n})$. The right side of (178) can be further
upper-bounded by

$\displaystyle\mathbf{E}[D(K_{Y|X,W^{\prime},M},K_{Y|X,W,M})]+2{\rm
diam}(\mathbb{M},D)R_{01}(M|X,Z^{n}),$ (179)

where $W^{\prime}$ is a sample from the posterior distribution
$P_{W|X,Z^{n},M}$ such that $W^{\prime}$ and $W$ are conditionally i.i.d.
given $(X,Z^{n},M)$. If $D$ is convex in the second argument, we obtain
another set of upper bounds by exchanging the order of the arguments of $D$ in
the results above.

Theorem 15 shows that under the multi-model family setting, the expected
deviation consists of two parts: the first part can be related to the
estimation error of the model parameters when the model index is correctly
identified, which depends on the complexity of each model family; the second
part is related to the penalty when the model index is wrongly identified,
which depends on the overall complexity of the model class and the error
probability of model index estimation.

As an example, for linear regression with multiple model families, the
predictive model in the $m$th family can be described as
$K_{Y|x,w,m}=\mathcal{N}(w^{\top}\phi(x,m),\sigma^{2})$, where
$w\in{\mathsf{W}}_{m}\subset\mathbb{R}^{d_{m}}$ is the model parameter vector
and $\phi(x,m)\in\mathbb{R}^{d_{m}}$ is the feature vector of the observation
$x$. We also assume that $X$ is independent of $(M,W)$. In this case,

$\displaystyle D_{\rm KL}(K_{Y|x,w^{\prime},m^{\prime}}\|K_{Y|x,w,m})$
$\displaystyle=\frac{1}{2\sigma^{2}}\big{(}w^{\prime\top}\phi(x,m^{\prime})-w^{\top}\phi(x,m)\big{)}^{2},$
(180)

and

$\displaystyle{\rm diam}(\mathbb{M},D_{\rm
KL})=\frac{1}{2\sigma^{2}}\max_{m\neq
m^{\prime}\in{\mathsf{M}}}\sup_{w\in{\mathsf{W}}_{m},w^{\prime}\in{\mathsf{W}}_{m^{\prime}}}\sup_{x\in{\mathsf{X}}}\big{(}w^{\prime\top}\phi(x,m^{\prime})-w^{\top}\phi(x,m)\big{)}^{2}.$
(181)

From Theorem 14, the chain rule of mutual information, Theorem 15, and the
previous results on linear regression in the single model family, we have the
following upper bounds for ${\rm MER}_{\log}$ for linear regression with
multiple models:

$\displaystyle{\rm MER}_{\log}$
$\displaystyle\leq\frac{1}{2\sigma^{2}}\mathbf{E}[\|\phi_{M}(X)\|^{2}]R_{2}(W|Z^{n},M)+H(M|Z^{n})$
(182)

and

$\displaystyle{\rm
MER}_{\log}\leq\frac{1}{\sigma^{2}}\mathbf{E}[\|\phi_{M}(X)\|^{2}]R_{2}(W|Z^{n},M)+2{\rm
diam}(\mathbb{M},D_{\rm KL})R_{01}(M|Z^{n})$ (183)

where

$\displaystyle R_{2}(W|Z^{n},M)=\sum_{m\in{\mathsf{M}}}P_{M}(m)\mathbf{E}[{\rm
tr}(C_{W|Z^{n},m})]$ (184)

with
$C_{W|Z^{n},m}=({\sigma_{W,m}^{-2}}\mathbf{I}_{d_{m}}+{\sigma^{-2}}\mathbf{\Phi}_{m}\mathbf{\Phi}_{m}^{\top})^{-1}$
and $\mathbf{\Phi}_{m}=[\phi(X_{1},m),\ldots,\phi(X_{n},m)]$ being the
$d_{m}\times n$ feature matrix for the $m$th model family. We see that the MER
consists of a part that depends on the minimum achievable model parameter
estimation error given each model index, and a part that depends on the
uncertainty of model index estimation and the “diameter” of the model class.

###  5.2 MER in nonparametric models

The definition of MER can also be extended to Bayesian learning under a
nonparametric predictive model that can be specified in terms of a random
process. Formally, consider the case where $F$ is a real-valued random process
indexed by $x\in{\mathsf{X}}$, and the predictive model is a probability
transition kernel $K_{Y|F(X)}$. It is further assumed that $F$ is a priori
independent of $X$. The observed data and the fresh pair are assumed to be
generated from the joint distribution

$\displaystyle
P_{F,Z^{n},Z}=P_{F}\Big{(}\prod\limits_{i=1}^{n}P_{Z_{i}|F}\Big{)}P_{Z|F}$
(185)

where $P_{Z_{i}|F}=P_{Z|F}=P_{X}K_{Y|F(X)}$ for $i=1,\ldots,n$. Two simple
examples of the above model are 1) noiseless Gaussian process regression
model, where $F$ is a Gaussian process with a mean function
$m\mathrel{\mathop{\mathchar 58\relax}}{\mathsf{X}}\rightarrow\mathbb{R}$ and
a covariance function $k\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{X}}\times{\mathsf{X}}\rightarrow\mathbb{R}$, and $Y=F(X)$;
and 2) binary classification model with Gaussian process as a latent function
[7], where $F$ can be the same Gaussian process, and
$K_{Y|F(X)}(1|f(x))=\sigma(f(x))$ with $\sigma(\cdot)$ being the logistic
sigmoid function.

In the same spirit in the parametric case, the MER under the above
nonparametric model can be defined as

$\displaystyle{\rm MER}_{\ell}=R_{\ell}(Y|X,Z^{n})-R_{\ell}(Y|F(X)),$ (186)

where $R_{\ell}(Y|X,Z^{n})$ and $R_{\ell}(Y|F(X))$ are defined according to
the general definition of the Bayes risk in (3), and correspond to (2) and
(11) respectively. For the log loss, using the fact that
$H_{\mu}(Y|F(X),Z^{n})=H_{\mu}(Y|F(X))$ and following the same argument as in
Corollary 1, we have

$\displaystyle{\rm MER}_{\rm log}$
$\displaystyle=I(F(X);Y|X,Z^{n})\leq\frac{1}{n}I(F(X);Y^{n}|X^{n}).$ (187)

For the quadratic loss,

$\displaystyle{\rm MER}_{2}$ $\displaystyle=R_{2}(Y|X,Z^{n})-R_{2}(Y|F(X)).$
(188)

In the special case of noiseless Gaussian process regression model,
$R_{2}(Y|F(X))=0$, which implies

$\displaystyle{\rm MER}_{2}$
$\displaystyle=R_{2}(F(X)|F(X_{1}),\ldots,F(X_{n}))$ (189)
$\displaystyle=\mathbf{E}\big{[}k(X,X)-k(X,X^{n})^{\top}\Sigma^{-1}(X^{n})k(X,X^{n})\big{]}$
(190)

where $k(X,X^{n})$ is the covariance vector between $F(X)$ and
$(F(X_{1}),\ldots,F(X_{n}))$, and $\Sigma(X^{n})$ is the covariance matrix of
$(F(X_{1}),\ldots,F(X_{n}))$. The above expression may be further analyzed
using the eigenfunction expansion of the covariance function $k$ [7]. For the
binary classification model with Gaussian process as the latent function, or
more general models specified with non-Gaussian processes, the MER may not
have a simple close-form expression.

##  6 Discussion

We have defined the minimum excess risk in Bayesian learning with respect to
general loss functions, and presented general methods for obtaining upper
bounds for this quantity. How to lower-bound this quantity is left as an open
problem. We would like to close the paper by discussing the following two
aspects.

###  6.1 Tightness and utility of the results

Two methods for deriving upper bounds on the MER have been presented: one
method relates the MER to $I(W;Y|X,Z^{n})$; the other one relates it to
$R_{2}(W|X,Z^{n})$.

With the precise asymptotic expansion of $I(W;Z^{n})$, the first method is
suitable for asymptotic analysis for a wide range of loss functions. Using
this method, we have shown that for any bounded loss function, the MER scales
with the data size $n$ as $O(\sqrt{1/n})$ in general, while for the log loss,
the squared loss with bounded $Y$, and bounded loss under realizable models,
this convergence rate can be improved to $O(1/n)$. When the model parameter
lies in a compact subset of $\mathbb{R}^{d}$, or when the VC dimension of the
generative function class is $d$, the MER bounds can also capture the
dependence on $d$, as $O(\sqrt{d/n})$ or $O(d/n)$ in different settings. An
MER lower bound of $\Omega(d/n)$ is derived in a follow-up work [45, Theorem
10] for the cases where the excess risk of using $\Psi^{*}(X,W^{\prime})$ as
the plug-in decision rule is lower bounded by $\|W-W^{\prime}\|^{2}$, which
matches upper bounds in certain settings derived in this work.

The second method has the potential to provide us with nonasymptotic upper
bounds. The only explicit expression for $R_{2}(W|X,Z^{n})$ we have so far is
for linear regression, for which we have derived order-optimal upper bound for
both ${\rm MER}_{\log}$ and ${\rm MER}_{2}$. In order to obtain explicit upper
bounds for problems beyond linear regression, e.g. logistic regression or
nonlinear regression, we would need upper bounds on $R_{2}(W|X,Z^{n})$, or
other forms of minimum model parameter estimation error in these settings.
Nevertheless, from the examples on logistic regression, linear regression, and
nonlinear regression, we see that the MER upper bounds obtained from the
second method depend on $n$ only through $R_{2}(W|X,Z^{n})$. This explicitly
shows how the model uncertainty translates to the epistemic uncertainty and
contributes to the overall prediction uncertainty. The definition of MER
provides such a principled way to define different notions of uncertainties in
Bayesian learning, and its study guides the analysis and estimation of these
uncertainties, which is an increasingly important direction of research with
wide applications.

###  6.2 MER in Bayesian learning vs. excess risk in frequentist learning

The distinguishing feature of Bayesian learning is that the generative model
of data is assumed to be drawn from a known model family according to some
prior distribution. As a result, the MER in Bayesian learning is determined by
how accurate the model can be estimated, and there is no notion of
_approximation error_ unless the model family or the prior distribution is
misspecified. This stands in contrast to the frequentist formulation of
statistical learning where the data-generating model is assumed to be
completely unknown, and the excess risk consists of an estimation error part
and an approximation error part.

In the discussion on the setting with multiple model families in Section 5.1,
it is shown that the MER there not only depends on the accuracy of the model
parameter estimation within a fixed model, but also on the product of the
error probability of model index estimation and a diameter-like term measuring
the largest statistical distance among the predictive models. The latter
quantity may be viewed as an analogue of the approximation error in the
frequentist setting, as it upper-bounds the penalty incurred by a wrong
estimate of the model index. Its impact on the MER vanishes as the data size
increases though, as the error probability of model index estimation would
eventually go to zero.

Another connection to the frequentist learning would be the identical
expressions shared by the MER-information relationship in Corollary 4 and the
generalization-information relationship in the frequentist setting of [12,
Theorem 1]. It shows the important roles played by information-theoretic
quantities in the theory of statistical learning.

## Appendix

##  Appendix A Miscellaneous lemmas

###  A.1 Regularity conditions for (30)

The regularity conditions for (30) to hold are listed here for completeness.
These conditions are drawn from in [37, Section 2]. Let
${\mathsf{W}}\subset\mathbb{R}^{d}$ and assume that the densities of $P_{Z|w}$
exist with respect to the Lebesgue measure for all $w\in{\mathsf{W}}$. Also
assume the parameter space ${\mathsf{W}}$ has a non-void interior and its
boundary has a $d$-dimensional Lebesgue measure zero.

  1. 1.

The density $p_{Z|W}(z|w)$ is twice continuously differentiable in $w$ for
almost every $z$. There exists $\delta(w)$ such that for every
$j,k\in\\{1,\dots,d\\}$:

$\displaystyle\mathbf{E}\Big{[}\sup_{w^{\prime}\mathrel{\mathop{\mathchar
58\relax}}\|w^{\prime}-w\|\leq\delta(w)}\Big{|}\frac{\partial^{2}}{\partial
w_{j}^{\prime}\partial w_{k}^{\prime}}\log
p_{Z|W}(Z|w^{\prime})\Big{|}\Big{]}$ (191)

is finite and continuous in $w$. In addition, for each $j\in\\{1,\dots,d\\}$:

$\displaystyle\mathbf{E}\Big{[}\Big{|}\frac{\partial}{\partial w_{j}}\log
p_{Z|W}(Z|w)\Big{|}^{2+\zeta}\Big{]}$ (192)

is finite and continuous, as a function of $w$, for some $\zeta>0$.

  2. 2.

Conditions on Fisher information matrix: define the matrix

$\displaystyle[I(w)]_{j,k}=\mathbf{E}\Big{[}\frac{\partial}{\partial
w_{j}}\log p_{Z|W}(Z|w)\frac{\partial}{\partial w_{k}}\log
p_{Z|W}(Z|w)\Big{]},$ (193)

and

$\displaystyle[J(w)]_{j,k}=\Big{[}\frac{\partial^{2}}{\partial
w^{\prime}_{j}\partial
w^{\prime}_{k}}D_{\rm{KL}}\Big{(}P_{Z|w}\|P_{Z|w^{\prime}}\Big{)}\Big{|}_{w^{\prime}=w}\Big{]};$
(194)

we have $I(w)=J(w)$. The matrix $I(w)$ is also positive definite.

  3. 3.

For $w\neq w^{\prime}$, we have $P_{Z|w}\neq P_{Z|w^{\prime}}$.

  4. 4.

The prior on $W$ is continuous and is supported on a compact subset of the
interior of ${\mathsf{W}}$.

###  A.2 A transportation inequality

The following lemma is adapted from [60, Lemma 4.18] and [44, Theorem 2].

######  Lemma 1.

For distributions $P$ and $Q$ on a set ${\mathsf{U}}$ and a function
$f\mathrel{\mathop{\mathchar 58\relax}}{\mathsf{U}}\rightarrow\mathbb{R}$,
suppose there exists a function $\varphi$ over $(0,b)$ with some
$b\in(0,\infty]$ such that

$\displaystyle\log\mathbf{E}_{Q}\big{[}e^{-\lambda(f(U)-\mathbf{E}_{Q}f(U))}\big{]}\leq\varphi(\lambda),\quad\forall\,0<\lambda<b.$
(195)

Then

$\displaystyle\mathbf{E}_{Q}[f(U)]-\mathbf{E}_{P}[f(U)]\leq\varphi^{*-1}(D_{\rm
KL}(P\|Q)),$ (196)

where

$\displaystyle\varphi^{*}(\gamma)$
$\displaystyle=\sup_{0<\lambda<b}\lambda\gamma-\varphi(\lambda),\quad\gamma\in\mathbb{R}$
(197)

is the Legendre dual of $\varphi$ and $\varphi^{*-1}$ is the inverse of
$\varphi^{*}$, defined as

$\displaystyle\varphi^{*-1}(x)$
$\displaystyle=\sup\\{\gamma\in\mathbb{R}\mathrel{\mathop{\mathchar
58\relax}}\varphi^{*}(\gamma)\leq x\\},\quad x\in\mathbb{R}.$ (198)

###### Proof of Lemma 1.

The Donsker-Varadhan theorem states that

$\displaystyle D_{\rm KL}(P\|Q)=\sup_{g\mathrel{\mathop{\mathchar
58\relax}}{\mathsf{U}}\rightarrow\mathbb{R}}\mathbf{E}_{P}[g(U)]-\log\mathbf{E}_{Q}[e^{g(U)}],$
(199)

which implies that

$\displaystyle D_{\rm KL}(P\|Q)$
$\displaystyle\geq\sup_{0<\lambda<b}\lambda(\mathbf{E}_{Q}[f(U)]-\mathbf{E}_{P}[f(U)])-\log\mathbf{E}_{Q}[e^{-\lambda(f(U)-\mathbf{E}_{Q}f(U))}]$
(200)
$\displaystyle\geq\sup_{0<\lambda<b}\lambda(\mathbf{E}_{Q}[f(U)]-\mathbf{E}_{P}[f(U)])-\varphi(\lambda)$
(201) $\displaystyle=\varphi^{*}(\mathbf{E}_{Q}[f(U)]-\mathbf{E}_{P}[f(U)]).$
(202)

Consequently, from the definition in (198),

$\displaystyle\mathbf{E}_{Q}[f(U)]-\mathbf{E}_{P}[f(U)]\leq\varphi^{*-1}(D_{\rm
KL}(P\|Q)),$ (203)

which proves (196). ∎

###  A.3 Series with growth rate $\log n$

The following lemma is a restatement of [38, Lemma 6].

######  Lemma 2.

Suppose $(a_{1},a_{2},\ldots)$ and $(b_{1},b_{2},\ldots)$ are two sequences of
real numbers such that $a_{n}=\sum_{i=1}^{n}b_{i}$ for all $n$. Then

$\displaystyle\lim_{n\rightarrow\infty}\frac{a_{n}}{\log
n}=\lim_{n\rightarrow\infty}nb_{n},$ (204)

whenever both limits exist.

###  A.4 Convexity of $\mathcal{W}_{p}^{p}(P,Q)$

######  Lemma 3.

The $p$th power of the $p$-Wasserstein distance is jointly convex in its two
arguments, i.e. $\mathcal{W}_{p}^{p}(P,Q)$ is convex in $(P,Q)$.

###### Proof.

By definition,

$\displaystyle\mathcal{W}_{p}^{p}(P,Q)=\inf_{\Pi(P,Q)}\mathbf{E}_{(X,Y)\sim\Pi}[\|X-Y\|^{p}].$
(205)

For arbitrary $(P_{1},Q_{1})$, $(P_{2},Q_{2})$, and $\gamma\in[0,1]$, let
$\Pi_{1}$ and $\Pi_{2}$ be the optimal couplings for
$\mathcal{W}_{p}^{p}(P_{1},Q_{1})$ and $\mathcal{W}_{p}^{p}(P_{2},Q_{2})$
respectively. Then

$\displaystyle\mathcal{W}_{p}^{p}(\gamma P_{1}+(1-\gamma)P_{2},\gamma
Q_{1}+(1-\gamma)Q_{2})$ (206) $\displaystyle\leq$
$\displaystyle\mathbf{E}_{(X,Y)\sim\gamma\Pi_{1}+(1-\gamma)\Pi_{2}}[\|X-Y\|^{p}]$
(207) $\displaystyle=$
$\displaystyle\gamma\mathbf{E}_{(X,Y)\sim\Pi_{1}}[\|X-Y\|^{p}]+(1-\gamma)\mathbf{E}_{(X,Y)\sim\Pi_{2}}[\|X-Y\|^{p}]$
(208) $\displaystyle=$
$\displaystyle\gamma\mathcal{W}_{p}^{p}(P_{1},Q_{1})+(1-\gamma)\mathcal{W}_{p}^{p}(P_{2},Q_{2}),$
(209)

where the first inequality is because $\gamma\Pi_{1}+(1-\gamma)\Pi_{2}$ is a
coupling of $\gamma P_{1}+(1-\gamma)P_{2}$ and $\gamma Q_{1}+(1-\gamma)Q_{2}$.
This shows the convexity of $\mathcal{W}_{p}^{p}(P,Q)$ in $(P,Q)$. ∎

###  A.5 Lipschitz continuity of multivariate function

The following lemma states a sufficient condition for a multivariate function
to be Lipschitz continuous [61].

######  Lemma 4.

Suppose a function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\rightarrow\mathbb{R}$ is continuously differentiable
everywhere in a convex set ${\mathsf{X}}\subset\mathbb{R}^{n}$. If $c>0$ is
such that $\|\nabla f(x)\|\leq c$ for all $x\in{\mathsf{X}}$, then
$|f(y)-f(x)|\leq c\|y-x\|$ for all $x,y\in{\mathsf{X}}$.

###  A.6 Proof of Lemma 3

With the log loss, the generalized entropy of discrete $Y$ is the Shannon
entropy. We have

$\displaystyle H(P)-H(Q)$
$\displaystyle=\mathbf{E}_{P}[-\log{P(U)}]-\mathbf{E}_{Q}[-\log{Q(U)}]$ (210)
$\displaystyle\leq\mathbf{E}_{P}[-\log{Q(U)}]-\mathbf{E}_{Q}[-\log{Q(U)}]$
(211) $\displaystyle=\sum_{u\in{\mathsf{U}}}(P(u)-Q(u))(-\log{Q(u)})$ (212)
$\displaystyle\leq(-\log\min_{u\in{\mathsf{U}}}Q(u))d_{\rm TV}(P,Q),$ (213)

where the first inequality follows from the fact that
$H(P)=\inf_{Q}\mathbf{E}_{P}[-\log Q(U)]$, and the last inequality follows
from the fact that $-\log Q(u)\in[0,-\log\min_{u\in{\mathsf{U}}}Q(u)]$ and the
dual representation of the total variation distance.

For the zero-one loss, the generalized entropy of discrete $Y$ is one minus
the maximum probability. We have

$\displaystyle(1-\max\nolimits_{u\in{\mathsf{Y}}}P(u))-(1-\max\nolimits_{u\in{\mathsf{U}}}Q(u))$
$\displaystyle=$
$\displaystyle\max\nolimits_{u\in{\mathsf{Y}}}Q(u)-\max\nolimits_{u\in{\mathsf{Y}}}P(u)$
(214) $\displaystyle\leq$ $\displaystyle Q(u_{\max})-P(u_{\max})$ (215)
$\displaystyle\leq$ $\displaystyle d_{\rm TV}(Q,P)$ (216)

where in (215), $u_{\max}\mathrel{\mathop{\mathchar
58\relax}}=\operatorname*{arg\,max}_{u\in{\mathsf{Y}}}Q(u)$; (216) follows
from the fact that $d_{\rm
TV}(Q,P)=\sup\nolimits_{E\subset{\mathsf{U}}}Q[E]-P[E]$ for any pair of
distributions on ${\mathsf{U}}$. The claim follows from the fact that the
total variation distance is symmetric.

###  A.7 Proof of Lemma 5

First note that according to the definition of the $\mathcal{W}_{2}$ distance,
$\mathbf{E}[U^{2}]=\mathcal{W}_{2}^{2}(P_{U},\delta_{0})$ and
$\mathbf{E}[V^{2}]=\mathcal{W}_{2}^{2}(P_{V},\delta_{0})$, where $\delta_{0}$
denotes the point mass at $0$. Then

$\displaystyle{\mathsf{var}}[U]-{\mathsf{var}}[V]$
$\displaystyle=\mathbf{E}[U^{2}]-\mathbf{E}[V^{2}]+(\mathbf{E}[U]+\mathbf{E}[V])(\mathbf{E}[V]-\mathbf{E}[U])$
(217)
$\displaystyle\leq(\mathcal{W}_{2}^{2}(P_{U},\delta_{0})-\mathcal{W}_{2}^{2}(P_{V},\delta_{0}))+|\mathbf{E}[U]+\mathbf{E}[V]|\mathcal{W}_{1}(P_{U},P_{V})$
(218)
$\displaystyle\leq(\mathcal{W}_{2}(P_{U},\delta_{0})+\mathcal{W}_{2}(P_{V},\delta_{0}))|\mathcal{W}_{2}(P_{U},\delta_{0})-\mathcal{W}_{2}(P_{V},\delta_{0})|+$
$\displaystyle\quad\,\,\,|\mathbf{E}[U]+\mathbf{E}[V]|\mathcal{W}_{2}(P_{U},P_{V})$
(219)
$\displaystyle\leq(\sqrt{\mathbf{E}[U^{2}]}+\sqrt{\mathbf{E}[V^{2}]})\mathcal{W}_{2}(P_{U},P_{V})+|\mathbf{E}[U]+\mathbf{E}[V]|\mathcal{W}_{2}(P_{U},P_{V})$
(220) $\displaystyle\leq
2(\sqrt{\mathbf{E}[U^{2}]}+\sqrt{\mathbf{E}[V^{2}]})\mathcal{W}_{2}(P_{U},P_{V})$
(221)

where we have used the triangle inequality for the $\mathcal{W}_{2}$ distance
and the fact that

$\displaystyle|\mathbf{E}[U]-\mathbf{E}[V]|\leq\mathcal{W}_{1}(P_{U},P_{V})\leq\mathcal{W}_{2}(P_{U},P_{V}).$
(222)

##  Appendix B MER upper bound for linear regression based on Theorem 6

To make use of Theorem 6 for linear regression with the quadratic loss, let
$Y=W^{\top}\phi(X)+V$ where $V\sim\mathcal{N}(0,\sigma^{2})$, and assume $X$
is independent of $W$. In addition, let $W^{\prime}$ be sampled from
$P_{W|Z^{n}}$ independently of everything else. Since
$\psi^{*}(X,W^{\prime})=W^{\prime\top}\phi(X)$, we have

$\displaystyle(Y-\psi^{*}(X,W^{\prime}))^{2}$
$\displaystyle=(Y-W^{\prime\top}\phi(X))^{2}=((W-W^{\prime})^{\top}\phi(X)+V)^{2}.$
(223)

Since $W^{\prime}$ is a conditionally i.i.d. copy of $W$ given $(X,Z^{n})$, it
can be seen that the conditional distribution of
$(W-W^{\prime})^{\top}\phi(X)$ given $(X,Z^{n})=(x,z^{n})$ is Gaussian with
zero mean and variance $2\phi(x)^{\top}C_{W|z^{n}}\phi(x)$. It follows that
conditional on $(X,Z^{n})=(x,z^{n})$, $(Y-\psi^{*}(x,W^{\prime}))^{2}$ has the
same distribution as
$\big{(}2\phi(x)^{\top}C_{W|z^{n}}\phi(x)+\sigma^{2}\big{)}U^{2}$, where
$U\sim\mathcal{N}(0,1)$. As a consequence of the fact that

$\displaystyle\log\mathbf{E}[e^{-\lambda(\sigma_{\chi}^{2}U^{2}-\mathbf{E}[\sigma_{\chi}^{2}U^{2}])}]=\lambda\sigma_{\chi}^{2}-\frac{1}{2}\log(1+2\sigma_{\chi}^{2}\lambda)\leq\sigma_{\chi}^{4}\lambda^{2}\mathrel{\mathop{\mathchar
58\relax}}=\varphi(\lambda)\quad\text{for $\lambda>0$},$ (224)

the fact that $\varphi^{*-1}(\gamma)=2\sigma_{\chi}^{2}\sqrt{\gamma}$, the
assumption that $\sup_{x,x^{n}}\phi(x)^{\top}C_{W|z^{n}}\phi(x)\leq b$, the
fact that
$I(W;Y|X,Z^{n})=\mathbf{E}[\frac{1}{2}\log(1+{\phi(X)^{\top}C_{W|Z^{n}}\phi(X)}/{\sigma^{2}})]$,
and Theorem 6, we have

$\displaystyle{\rm MER}_{2}$ $\displaystyle\leq
2(2b+\sigma^{2})\sqrt{\frac{1}{2}\log\Big{(}1+\frac{1}{\sigma^{2}}\mathbf{E}\big{[}\phi(X)C_{W|Z^{n}}\phi(X)\big{]}\Big{)}}$
(225) $\displaystyle\leq
2(2b+\sigma^{2})\sqrt{\frac{1}{2}\log\Big{(}1+\frac{1}{\sigma^{2}}\mathbf{E}[\|\phi(X)\|^{2}]\mathbf{E}[{\rm
tr}(C_{W|X^{n},Y^{n}})]\Big{)}}.$ (226)

##  Appendix C Proof of Theorem 15

From the fact that
$P_{Y|x,z^{n}}=\sum_{m^{\prime}\in{\mathsf{M}}}P_{M|X,Z^{n}}(m^{\prime}|x,z^{n})\int_{{\mathsf{W}}_{m^{\prime}}}\\!\\!P_{W|M,X,Z^{n}}({\rm
d}w^{\prime}|m^{\prime},x,z^{n})K_{Y|x,w^{\prime},m^{\prime}}$ and the
convexity assumption of the statistical distance under consideration, the
proof of the first inequality essentially follows the same steps of the proof
of Lemma 2.

The second inequality is based on the first one, and can be shown as

$\displaystyle\quad\,\,\mathbf{E}\big{[}D(P_{Y|X,Z^{n}},K_{Y|X,W,M})\big{]}$
(227)
$\displaystyle\leq\mathbf{E}\big{[}D(K_{Y|X,W^{\prime},M^{\prime}},K_{Y|X,W,M})\big{]}$
(228)
$\displaystyle=\sum_{m\in{\mathsf{M}}}P_{M}(m)\int_{{\mathsf{W}}_{m}}\\!\\!P_{W|M}({\rm
d}w|m)\int_{{\mathsf{X}}\times{\mathsf{Z}}^{n}}P_{X,Z^{n}|W,M}({\rm d}x,{\rm
d}z^{n}|w,m)\,\cdot$
$\displaystyle\quad\,\sum_{m^{\prime}\in{\mathsf{M}}}P_{M|X,Z^{n}}(m^{\prime}|x,z^{n})\int_{{\mathsf{W}}_{m^{\prime}}}\\!\\!P_{W|X,Z^{n},M}({\rm
d}w^{\prime}|x,z^{n},m^{\prime})D(K_{Y|x,w^{\prime},m^{\prime}},K_{Y|x,w,m})$
(229) $\displaystyle=S_{1}+S_{2}$ (230)

where the last step is to split the summation over $m^{\prime}$ such that

$\displaystyle S_{1}$
$\displaystyle=\sum_{m\in{\mathsf{M}}}P_{M}(m)\int_{{\mathsf{W}}_{m}}P_{W|M}({\rm
d}w|m)\int_{{\mathsf{X}}\times{\mathsf{Z}}^{n}}P_{X,Z^{n}|W,M}({\rm d}x,{\rm
d}z^{n}|w,m)$
$\displaystyle\qquad\quad\,\,P_{M|X,Z^{n}}(m|x,z^{n})\int_{{\mathsf{W}}_{m}}\\!\\!P_{W|X,Z^{n},M}({\rm
d}w^{\prime}|x,z^{n},m)D(K_{Y|x,w^{\prime},m},K_{Y|x,w,m})$ (231)
$\displaystyle\leq\sum_{m\in{\mathsf{M}}}P_{M}(m)\int_{{\mathsf{W}}_{m}}\\!P_{W|M}({\rm
d}w|m)\int_{{\mathsf{X}}\times{\mathsf{Z}}^{n}}P_{X,Z^{n}|W,M}({\rm d}x,{\rm
d}z^{n}|w,m)$
$\displaystyle\qquad\qquad\qquad\,\,\int_{{\mathsf{W}}_{m}}\\!P_{W|X,Z^{n},M}({\rm
d}w^{\prime}|x,z^{n},m)D(K_{Y|x,w^{\prime},m},K_{Y|x,w,m})$ (232)
$\displaystyle=\mathbf{E}[D(K_{Y|X,W^{\prime},M},K_{Y|X,W,M})]$ (233)

and

$\displaystyle S_{2}$
$\displaystyle=\sum_{m\in{\mathsf{M}}}P_{M}(m)\int_{{\mathsf{W}}_{m}}P_{W|M}({\rm
d}w|m)\int_{{\mathsf{X}}\times{\mathsf{Z}}^{n}}P_{X,Z^{n}|W,M}({\rm d}x,{\rm
d}z^{n}|w,m)\,\cdot$ $\displaystyle\quad\sum_{m^{\prime}\neq
m}P_{M|X,Z^{n}}(m^{\prime}|x,z^{n})\int_{{\mathsf{W}}_{m^{\prime}}}\\!\\!\\!P_{W|X,Z^{n},M}({\rm
d}w^{\prime}|x,z^{n},m^{\prime})D(K_{Y|x,w^{\prime},m^{\prime}},K_{Y|x,w,m})$
(234) $\displaystyle\leq\Big{(}\max_{m,m^{\prime}\in{\mathsf{M}},m\neq
m^{\prime}}\sup_{w\in{\mathsf{W}}_{m},w^{\prime}\in{\mathsf{W}}_{m^{\prime}}}\sup_{x\in{\mathsf{X}}}D(K_{Y|x,w^{\prime},m^{\prime}},K_{Y|x,w,m})\Big{)}$
$\displaystyle\quad\,\sum_{m\in{\mathsf{M}}}P_{M}(m)\int_{{\mathsf{W}}_{m}}P_{W|M}({\rm
d}w|m)\int_{{\mathsf{X}},{\mathsf{Z}}^{n}}P_{X,Z^{n}|W,M}({\rm d}x,{\rm
d}z^{n}|w,m)\sum_{m^{\prime}\neq m}P_{M|X,Z^{n}}(m^{\prime}|x,z^{n})$ (235)
$\displaystyle={\rm diam}(\mathbb{M},D){\mathbb{P}}[M^{\prime}\neq M]$ (236)
$\displaystyle\leq 2{\rm diam}(\mathbb{M},D)R_{\text{01}}(M|X,Z^{n})$ (237)

where the last step follows from Lemma 1 applied to the zero-one loss.

## Acknowledgment

The authors would like to thank Yihong Wu for insightful comments on an early
draft of this work; Lemma 5 is given by him. The authors are also thankful to
Max Welling and Auke Wiggers for discussions on different notions of
uncertainties in Bayesian learning. M. Raginsky was supported in part by the
NSF CAREER award CCF-1254041, in part by the Illinois Institute for Data
Science and Dynamical Systems (iDS2), an NSF HDR TRIPODS institute, under
award CCF-1934986, in part by DARPA under the LwLL (Learning with Less Labels)
program, and in part by ARO MURI grant W911NF-15-1-0479 (Adaptive Exploitation
of Non-Commutative Multimodal Information Structure).

## References

  * [1] C. M. Bishop, _Pattern Recognition and Machine Learning (Information Science and Statistics)_. Berlin, Heidelberg: Springer-Verlag, 2006.
  * [2] S. Brooks, A. Gelman, G. Jones, and X.-L. Meng, _Handbook of Markov Chain Monte Carlo_. Chapman Hall/CRC, 2011.
  * [3] D. M. Blei, A. Kucukelbir, and J. D. McAuliffe, “Variational inference: A review for statisticians,” _Journal of the American Statistical Association_ , vol. 112, no. 518, pp. 859–877, 2017.
  * [4] R. M. Neal, _Bayesian Learning for Neural Networks_. Berlin, Heidelberg: Springer-Verlag, 1996.
  * [5] C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra, “Weight uncertainty in neural networks,” in _International Conference on Machine Learning_ , 2015.
  * [6] Y. Gal and Z. Ghahramani, “Dropout as a Bayesian approximation: Representing model uncertainty in deep learning,” in _International Conference on Machine Learning_ , 2016.
  * [7] C. E. Rasmussen and C. K. I. Williams, _Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning)_. The MIT Press, 2006.
  * [8] C. Louizos, K. Ullrich, and M. Welling, “Bayesian compression for deep learning,” in _Conference on Neural Information Processing Systems_ , 2017\.
  * [9] A. Kendall and Y. Gal, “What uncertainties do we need in Bayesian deep learning for computer vision?” in _Conference on Neural Information Processing Systems_ , 2017.
  * [10] S. Depeweg, J. M. Hernández-Lobato, F. Doshi-Velez, and S. Udluft, “Decomposition of uncertainty in Bayesian deep learning for efficient and risk-sensitive learning,” in _ICML_ , 2018.
  * [11] E. Hüllermeier and W. Waegeman, “Aleatoric and epistemic uncertainty in machine learning: A tutorial introduction,” _ArXiv 1910.09457_ , 2019.
  * [12] A. Xu and M. Raginsky, “Information-theoretic analysis of generalization capability of learning algorithms,” in _Conference on Neural Information Processing Systems_ , 2017.
  * [13] L. D. Davisson, “Universal noiseless coding,” _IEEE Transactions on Information Theory_ , vol. 19, pp. 783–795, 1973.
  * [14] N. Merhav and M. Feder, “Universal prediction,” _IEEE Transactions on Information Theory_ , vol. 44, no. 6, pp. 2124–2147, 1998.
  * [15] D. Haussler and M. Opper, “Mutual information, metric entropy and cumulative relative entropy risk,” _Ann. Statist._ , vol. 25, no. 6, pp. 2451–2492, 12 1997.
  * [16] J. Baxter, “A Bayesian/information theoretic model of learning to learn via multiple task sampling,” _Machine Learning_ , vol. 28, pp. 7–39, 1997.
  * [17] D. Haussler, M. Kearns, and R. E. Schapire, “Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension,” _Machine Learning_ , vol. 14, no. 1, 1994.
  * [18] L. Le Cam and G. L. Yang, _Asymptotics in Statistics Some Basic Concepts_ , 2nd ed. Springer New York, 2000.
  * [19] S. Ghosal, J. K. Ghosh, and A. W. van der Vaart, “Convergence rates of posterior distributions,” _Ann. Statist._ , vol. 28, no. 2, pp. 500–531, 04 2000.
  * [20] S. Ghosal and A. van der Vaart, “Convergence rates of posterior distributions for noniid observations,” _Ann. Statist._ , vol. 35, no. 1, pp. 192–223, 02 2007.
  * [21] N. G. Polson and V. Ročková, “Posterior concentration for sparse deep learning,” in _Conference on Neural Information Processing Systems_ , 2018\.
  * [22] A. R. Barron, “Information-theoretic characterization of Bayes performance and the choice of priors in parametric and nonparametric problems,” in _Bayesian Statistics 6_. Oxford University Press, 1998.
  * [23] D. McAllester, “PAC-Bayesian stochastic model selection,” _Machine Learning_ , vol. 51, no. 1, 2003.
  * [24] J. Shawe-Taylor and R. C. Williamson, “A PAC analysis of a Bayesian estimator,” in _Conference on Computational Learning Theory_ , 1997.
  * [25] T. Zhang, “Information-theoretic upper and lower bounds for statistical estimation,” _IEEE Trans. Inform. Theory_ , vol. 52, no. 4, pp. 1307 – 1321, 2006.
  * [26] R. Meir and T. Zhang, “Generalization error bounds for Bayesian mixture algorithms,” _Journal of Machine Learning Research_ , 2003.
  * [27] P. D. Grünwald and A. P. Dawid, “Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory,” _Ann. Statist._ , vol. 32, no. 4, pp. 1367–1433, 2004.
  * [28] M. H. DeGroot, “Uncertainty, Information, and Sequential Experiments,” _The Annals of Mathematical Statistics_ , vol. 33, no. 2, pp. 404 – 419, 1962\.
  * [29] F. Farnia and D. Tse, “A minimax approach to supervised learning,” in _Conference on Neural Information Processing Systems_ , 2016.
  * [30] O. Kallenberg, _Foundations of Modern Probability_ , 2nd ed. Springer, 2002.
  * [31] T. Cover and J. Thomas, _Elements of Information Theory_ , 2nd ed. New York: Wiley, 2006.
  * [32] I. J. Good, “On the Principle of Total Evidence,” _The British Journal for the Philosophy of Science_ , vol. 17, no. 4, pp. 319–321, 1967.
  * [33] S. Huttegger and M. Nielsen, “Generalized learning and conditional expectation,” _Philosophy of Science (forthcoming)_ , 2020.
  * [34] C. S. Qazaz, C. K. I. Williams, and C. M. Bishop, “An upper bound on the bayesian error bars for generalized linear regression,” in _Mathematics of Neural Networks: Models, Algorithms and Applications_. Boston, MA: Springer US, 1997, pp. 295–299.
  * [35] J. Rissanen, “Universal coding, information, prediction, and estimation,” _IEEE Transactions on Information Theory_ , vol. 30, no. 4, pp. 629–636, 1984\.
  * [36] B. S. Clarke and A. R. Barron, “Information-theoretic asymptotics of Bayes methods,” _IEEE Trans. Inform. Theory_ , vol. 36, no. 3, pp. 453–471, 1990\.
  * [37] ——, “Jeffreys’ prior is asymptotically least favorable under entropy risk,” _Journal of Statistical Planning and Inference_ , vol. 41, no. 1, pp. 37–60, 1994.
  * [38] D. Haussler and M. Opper, “General bounds on the mutual information between a parameter and $n$ conditionally independent observations,” in _Proceedings of the Eighth Annual Conference on Computational Learning Theory_ , 1995, p. 402–411.
  * [39] B. Hajek, _Random processes for engineers_. Cambridge University Press, 2015.
  * [40] Y. Wu and S. Verdú, “Functional properties of minimum mean-square error and mutual information,” _IEEE Transactions on Information Theory_ , vol. 58, no. 3, pp. 1289–1301, 2012.
  * [41] N. Sauer, “On the density of families of sets,” _Journal of Combinatorial Theory_ , vol. 13.1, 1972.