# Continuity of Generalized Entropy and Statistical Learning

Aolin Xu

###### Abstract

We study the continuity property of the generalized entropy as a functional of
the underlying probability distribution, defined with an action space and a
loss function, and use this property to answer the basic questions in
statistical learning theory, the excess risk analyses for various learning
methods. We first derive upper and lower bounds for the entropy difference of
two distributions in terms of several commonly used $f$-divergences, the
Wasserstein distance, and a distance that depends on the action space and the
loss function. Examples are given along with the discussion of each general
result, comparisons are made with the existing entropy difference bounds, and
new mutual information upper bounds are derived based on the new results. We
then apply the entropy difference bounds to the theory of statistical
learning. It is shown that the excess risks in the two popular learning
paradigms, the frequentist learning and the Bayesian learning, both can be
studied with the continuity property of different forms of the generalized
entropy. The analysis is then extended to the continuity of generalized
conditional entropy. The extension provides performance bounds for Bayes
decision making with mismatched distributions. It also leads to excess risk
bounds for a third paradigm of learning, where the decision rule is optimally
designed under the projection of the empirical distribution to a predefined
family of distributions. We thus establish a unified method of excess risk
analysis for the three major paradigms of statistical learning, through the
continuity of generalized entropy.

<EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
    1. 1.1 Generalized entropy
    2. 1.2 Continuity in distribution
    3. 1.3 Applications to statistical learning theory
    4. 1.4 Novelty
  2. 2 Bounds on entropy difference
    1. 2.1 Bounds via total variation distance
      1. 2.1.1 General results
      2. 2.1.2 Examples
    2. 2.2 Bounds via KL divergence
      1. 2.2.1 General results
      2. 2.2.2 Example: variance comparison against Gaussian
      3. 2.2.3 Example: bounded loss functions
      4. 2.2.4 Example: subgaussian log loss and connection to Rényi entropy order
    3. 2.3 Bounds via $\chi^{2}$ divergence
      1. 2.3.1 General results
      2. 2.3.2 Examples
    4. 2.4 Bounds via $D(P_{\ell},Q_{\ell})$
    5. 2.5 Bounds via Wasserstein distance
    6. 2.6 Bounds via $({\mathsf{A}},\ell)$-dependent distance
    7. 2.7 Comparison with existing bounds
    8. 2.8 An information-theoretic application: mutual information upper bound
  3. 3 Application to frequentist learning
    1. 3.1 Excess risk of ERM algorithm
    2. 3.2 Finite sample space
    3. 3.3 Lipschitz-continuous loss function
    4. 3.4 Learnability, typicality, and entropy continuity
  4. 4 Application to Bayesian learning
    1. 4.1 Minimum excess risk in Bayesian learning
    2. 4.2 Method of analysis based on entropy continuity
    3. 4.3 Example: regression with quadratic loss
  5. 5 Application to inference and learning with distributional drift
    1. 5.1 Bounds on conditional entropy difference
    2. 5.2 Excess risk bounds via entropy difference
    3. 5.3 Excess risk in learning by projecting to exponential family
  6. A Proof of Lemma 2

##  1 Introduction

###  1.1 Generalized entropy

The definition of Shannon entropy can be generalized via the following
statistical decision making problem [1]. Let ${\mathsf{Z}}$ be a space of
outcomes, ${\mathsf{A}}$ be a space of actions, and
$\ell:{\mathsf{Z}}\times{\mathsf{A}}\rightarrow\mathbb{R}$ be a loss function.
An outcome $Z$ is drawn from a distribution $P$ on ${\mathsf{Z}}$. The
decision making problem is to pick an action from ${\mathsf{A}}$ that
minimizes the expected loss. The minimum expected loss can be used as a
definition of the _generalized entropy_ of distribution $P$ w.r.t. the action
space ${\mathsf{A}}$ and the loss function $\ell$,

$\displaystyle
H_{\ell}(P)\triangleq\inf_{a\in{\mathsf{A}}}\mathbb{E}_{P}[\ell(Z,a)],$ (1)

which may also be written as $H_{\ell}(Z)$ when the distribution of $Z$ is
clear. When there is a need to emphasize the role of the action space, we may
use the notation $H_{{\mathsf{A}},\ell}(P)$ or $H_{{\mathsf{A}},\ell}(Z)$ as
well. Examples of the generalized entropy include:

  * •

When ${\mathsf{A}}$ is the family of distributions $Q$ on ${\mathsf{Z}}$ (e.g.
$Q$ is a PMF if ${\mathsf{Z}}=\mathbb{N}$, or a PDF if
${\mathsf{Z}}=\mathbb{R}^{p}$), the optimal action for the logarithmic loss
$\ell(z,Q)=-\log Q(z)$ is $P$, and $H_{\log}(Z)$ is the Shannon entropy $H(Z)$
when ${\mathsf{Z}}$ is discrete, or the differential entropy $h(Z)$ when
${\mathsf{Z}}$ is continuous.

  * •

When ${\mathsf{Z}}={\mathsf{A}}=\mathbb{R}^{p}$, the optimal action for the
quadratic loss $\ell(z,a)=\sum_{j=1}^{p}(z_{j}-a_{j})^{2}$ is $\mathbb{E}[Z]$,
and $H_{2}(Z)=\sum_{j=1}^{p}{\rm Var}[Z_{j}]$. In particular, when $p=1$,
$H_{2}(Z)={\rm Var}[Z]$.

  * •

When ${\mathsf{Z}}={\mathsf{A}}$ are discrete, the optimal action for the
zero-one loss $\ell(z,a)=\mathbf{1}\\{z\neq a\\}$ is
$\operatorname*{arg\,max}_{z}P(z)$, and
$H_{01}(Z)=1-\max_{z\in{\mathsf{Z}}}P(z)$.

The above decision making problem can also be used to formulate the
frequentist statistical learning problem, by letting ${\mathsf{Z}}$ be a
sample space, ${\mathsf{A}}$ be a hypothesis space, and $P$ be an unknown
distribution on ${\mathsf{Z}}$. For any hypothesis $a\in{\mathsf{A}}$,
$\mathbb{E}_{P}[\ell(Z,a)]$ is its population risk, and
$H_{{\mathsf{A}},\ell}(P)$ is the minimum population risk among all hypotheses
in ${\mathsf{A}}$, which would be achieved if $P$ were known. In practice,
what is available is a training dataset consisting of $n$ samples drawn i.i.d.
from $P$, with empirical distribution ${\widehat{P}}_{n}$. The empirical risk
minimization (ERM) algorithm outputs a hypothesis $a_{{\widehat{P}}_{n}}$ that
minimizes the empirical risk $\mathbb{E}_{{\widehat{P}}_{n}}[\ell(Z,a)]$ among
$a\in{\mathsf{A}}$, and $H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})$ is the
minimum empirical risk. It is one of the main goals of statistical learning
theory to bound the gap between
$\mathbb{E}_{P}[\ell(Z,a_{{\widehat{P}}_{n}})]$ and
$H_{{\mathsf{A}},\ell}(P)$, known as the excess risk of the ERM algorithm.

The generalized entropy defined in (1) can be extended to the _generalized
conditional entropy_ , defined via a Bayes decision making problem based on an
observation $X\in{\mathsf{X}}$ that statistically depends on $Z$ [2], as

$\displaystyle
H_{\ell}(P_{Z|X}|P_{X})\triangleq\inf_{\psi:{\mathsf{X}}\rightarrow{\mathsf{A}}}\mathbb{E}_{P}[\ell(Y,\psi(X))],$
(2)

where the expectation is taken w.r.t. the joint distribution $P_{X}\otimes
P_{Z|X}$ of $(X,Y)$, and the decision rule $\psi$ ranges over all mappings
from ${\mathsf{X}}$ to ${\mathsf{A}}$ such that the expected loss is well-
defined. The generalized conditional entropy in (2) may also be written as
$H_{\ell}(Z|X)$ when the joint distribution is clear. It is also expressible
in terms of the unconditional entropy,

$\displaystyle
H_{\ell}(P_{Z|X}|P_{X})=\int_{\mathsf{X}}H_{\ell}(P_{Z|X=x})P_{X}({\rm d}x).$
(3)

In Bayesian inference, the generalized conditional entropy is essentially the
_Bayes risk_ , which quantifies the minimum achievable expected loss of the
inference problem, and the optimal decision rule $\psi_{\rm B}$ is known as
the _Bayes decision rule_. Examples, in parallel to the above instantiations
of the generalized unconditional entropy, include:

  * •

For the log loss, $H_{\log}(Z|X)$ is the conditional Shannon/differential
entropy, and $\psi_{\rm B}(x)$ is the posterior distribution $P_{Z|X=x}$;

  * •

For the quadratic loss with ${\mathsf{Z}}={\mathsf{A}}=\mathbb{R}^{p}$,
$H_{2}(Z|X)=\sum_{j=1}^{p}\mathbb{E}[{\rm Var}[Z_{j}|X]]$ is the minimum mean
square error (MMSE) of estimating $Z$ from $X$, and $\psi_{\rm
B}(x)=\mathbb{E}[Z|X=x]$;

  * •

For the zero-one loss,
$H_{01}(Z|X)=1-\int_{{\mathsf{X}}}\max_{z\in{\mathsf{Z}}}P_{X,Z}({\rm d}x,z)$,
and $\psi_{\rm B}(x)=\operatorname*{arg\,max}_{z}P_{Z|X=x}(z)$ is the maximum
a-posteriori (MAP) rule.

From the above definitions and examples, we see that the performance limits of
a variety of statistical inference, learning, and decision making problems are
different instantiations of the generalized entropy or the generalized
conditional entropy. A good understanding of the properties of the generalized
entropy and its conditional version can thus help us better-understand the
performance limits of such problems.

###  1.2 Continuity in distribution

In the first part of this paper, we study the continuity property of the
generalized entropy defined in (1) in the distribution $P$. Given
${\mathsf{A}}$ and $\ell$, the generalized entropy $H_{{\mathsf{A}},\ell}(P)$
as a functional of $P$ is _continuous at a distribution_ $Q$ w.r.t. a
statistical distance $D(\cdot,\cdot)$111Throughout the paper, $D(\cdot,\cdot)$
denotes a generic statistical distance; the KL divergence will be denoted by
$D(\cdot\|\cdot)$., if

$\displaystyle\lim_{n\rightarrow\infty}|H_{{\mathsf{A}},\ell}(Q_{n})-H_{{\mathsf{A}},\ell}(Q)|=0$
(4)

for any sequence of distributions $(Q_{n})_{n\in{\mathbb{N}}}$ such that
$\lim_{n\rightarrow\infty}D(Q_{n},Q)=0$. In plain words,
$H_{{\mathsf{A}},\ell}(\cdot)$ is continuous at $Q$ if
$|H_{{\mathsf{A}},\ell}(P)-H_{{\mathsf{A}},\ell}(Q)|$ is small whenever
$D(P,Q)$ is small. A weaker notion of continuity is semicontinuity:
$H_{{\mathsf{A}},\ell}(\cdot)$ is _upper_ (or _lower_) _semicontinuous at a
distribution_ $Q$ w.r.t. $D(\cdot,\cdot)$, if
$\limsup_{n\rightarrow\infty}H_{{\mathsf{A}},\ell}(Q_{n})\leq
H_{{\mathsf{A}},\ell}(Q)$ (or
$\liminf_{n\rightarrow\infty}H_{{\mathsf{A}},\ell}(Q_{n})\geq
H_{{\mathsf{A}},\ell}(Q)$) whenever $\lim_{n\rightarrow\infty}D(Q_{n},Q)=0$.
We investigate the sufficient conditions on the action space ${\mathsf{A}}$,
loss function $\ell$ and the distribution $Q$ to make
$H_{{\mathsf{A}},\ell}(\cdot)$ continuous or semicontinuous at $Q$.
Specifically, given distributions $P$ and $Q$ on ${\mathsf{Z}}$, we derive
upper and lower bounds for
$H_{{\mathsf{A}},\ell}(P)-H_{{\mathsf{A}},\ell}(Q)$, in terms of various
statistical distances between $P$ and $Q$. This is the main objective of
Section 2.

In Sections 2.1, 2.2 and 2.3, we derive bounds for the entropy difference in
terms of the total variation distance, KL divergence and $\chi^{2}$ divergence
between $P$ and $Q$ on ${\mathsf{Z}}$. Among the results in terms of the KL
divergence, we show a connection between the Lipschitz continuity of the Rényi
entropy in the entropy order and the continuity of the Shannon/differential
entropy in the underlying distribution. These bounds are sharpened in Section
2.4 by considering the distance between distributions of the loss under $P$
and $Q$ when an optimal action is taken. In Section 2.5, we propose a general
method to bound the entropy difference in terms of the Wasserstein distance,
which depends on the property of the loss function. In Section 2.6, we examine
a bound in terms of a distance that depends on both the action space and the
loss function. In Section 2.7, comparisons are made between the results
derived in this work and the existing bounds on the entropy difference in the
literature. Finally, an information-theoretic application of the results is
presented in Section 2.8, where new upper bounds on the mutual information are
derived using the new entropy difference bounds in terms of KL divergence and
total variation distance. The results in Section 2 have been presented in part
in [3].

###  1.3 Applications to statistical learning theory

While the continuity properties of the generalize entropy may find
applications in a variety of subjects, in this paper we focus on studying
their applications to the theory of statistical learning. We show that the
three major paradigms of statistical learning, namely the frequentist
learning, the Bayesian learning, and learning by fitting the empirical
distribution with a predefined family of distributions, all can be studied
under the framework of the continuity of generalized entropy.

In Section 3, we show that the excess risk of the ERM algorithm in the
frequentist learning can be analyzed with the upper bounds on the entropy
difference obtained in Section 2, in terms of the statistical distance between
the data-generating distribution and the empirical distribution. In
particular, we give two examples where the success of the ERM algorithm does
not directly depend on the hypothesis class, but on the underlying
distribution and the loss function. We also reveal an intimate connection
between a generalized notion of typicality in information theory and the
learnability of a hypothesis class, through an entropy-continuity argument.

In Section 4, we give an overview of using the continuity property of the
generalized entropy to analyze the minimum excess risk in Bayesian learning,
which is studied in detail in [4]. The main idea is to bound the entropy
difference in terms of the statistical distance between the posterior
predictive distribution and the true predictive model, which leads to upper
bounds for the minimum excess risk in terms of the minimum estimation error of
the model parameters.

The study of the continuity of generalized entropy is extended to the
generalized conditional entropy in Section 5. Based on conditional entropy
difference bounds, we derive upper bounds for the excess risk in Bayes
decision making problems with distributional mismatch. An application of the
results is the excess risk analysis of a third paradigm of learning, where the
learned decision rule is optimally designed under a surrogate of the data-
generating distribution, which is found by projecting the empirical
distribution to an exponential family of distributions. This method of
analysis may also shed some light on the in-distribution excess risk analysis
of the recently proposed maximum conditional entropy and minimax frameworks of
statistical learning [2, 5].

###  1.4 Novelty

The continuity of Shannon entropy has been known for decades. A result
regarding this property can be found in [6, Lemma 2.7] and [7, Theorem 17.3.3]
in terms of the total variation distance. In [8], a tighter such bound is
derived via an optimal coupling argument, further improvement of which are
given in [9] and [10]. The continuity of differential entropy has been studied
much more recently in [11] in terms of the Wasserstein distance. The results
on Shannon/differential entropy obtained in this work have their own merits
compared to the existing results, which will be discussed in Section 2.7. For
the generalized entropy defined in (1) with general loss functions, there has
been no dedicated study on its continuity properties so far.

It is also new to view the excess risk analysis for the learning problems
through the continuity of generalized entropy. Most existing works on the
frequentist learning focus on the complexity analysis of the hypothesis space,
instead of directly comparing the distance between the data-generating
distribution and the empirical distribution. The latter method leads to a new
result in Theorem 13 that does not depend on the hypothesis space. The
performance of Bayesian learning under a generative model w.r.t. general loss
functions is much less studied than the frequentist learning. The analysis
based on entropy continuity provides a unique way to relate the minimum
achievable excess risk to the model uncertainty, as illustrated by Theorem 14.
The method of supervised learning by designing the decision rule under a
surrogate of the data-generating distribution is also less studied in the
literature. Corollary 13 addresses a special case of this problem and
explicitly shows that the excess risk consists of a fixed term of
approximation error and a vanishing term of estimation error.

This work would make a first effort to develop general methods of analysis for
the continuity property of the generalized entropy, establish connections to
statistical learning theory, and draw attention of researchers in related
fields on its potentially broader applications.

##  2 Bounds on entropy difference

In this section, we derive upper and lower bounds on the entropy difference
between two distributions $P$ and $Q$ in terms of their total variation
distance, KL divergence, $\chi^{2}$ divergence, Wasserstein distance, and a
semidistance that depends on ${\mathsf{A}}$ and $\ell$. We also compare the
new results with existing ones, and apply some of the new results to derive
new upper bounds for the mutual information.

In what follows, we assume the infimum in (1) can be achieved for all
distributions, and let $a_{P}$ and $a_{Q}$ be the optimal actions achieving
the infimum under distributions $P$ and $Q$ respectively. Then we have
$H_{\ell}(P)=\mathbb{E}_{P}[\ell(Z,a_{P})]$ and
$H_{\ell}(Q)=\mathbb{E}_{Q}[\ell(Z,a_{Q})]$. All of the results in this
section build on the following lemma, a consequence of the definitions of
$a_{P}$ and $a_{Q}$, and the variational representation of the generalized
entropy in (1).

######  Lemma 1.

Suppose there exist actions $a_{P}$ and $a_{Q}$ in ${\mathsf{A}}$ such that
$H_{\ell}(P)=\mathbb{E}_{P}[\ell(Z,a_{P})]$ and
$H_{\ell}(Q)=\mathbb{E}_{Q}[\ell(Z,a_{Q})]$, then

$\displaystyle\mathbb{E}_{P}[\ell(Z,a_{P})]-\mathbb{E}_{Q}[\ell(Z,a_{P})]\leq
H_{\ell}(P)-H_{\ell}(Q)\leq\mathbb{E}_{P}[\ell(Z,a_{Q})]-\mathbb{E}_{Q}[\ell(Z,a_{Q})].$
(5)

###  2.1 Bounds via total variation distance

####  2.1.1 General results

We first show that when the loss function is uniformly bounded, the entropy
difference can be controlled in terms of the total variation distance between
the two distributions, defined as $d_{\rm
TV}(P,Q)\triangleq\frac{1}{2}\int_{{\mathsf{Z}}}|P-Q|({\rm d}z)$.

######  Theorem 1.

If $\ell(\cdot,a_{Q})\in[\alpha_{Q},\beta_{Q}]$ for all $z\in{\mathsf{Z}}$,
then

$\displaystyle H_{\ell}(P)-H_{\ell}(Q)\leq(\beta_{Q}-\alpha_{Q})d_{\rm
TV}(P,Q).$ (6)

Consequently, if $\ell(\cdot,a_{P})\in[\alpha_{P},\beta_{P}]$ for all
$z\in{\mathsf{Z}}$, then

$\displaystyle H_{\ell}(Q)-H_{\ell}(P)\leq(\beta_{P}-\alpha_{P})d_{\rm
TV}(P,Q).$ (7)

###### Proof.

The upper bound in (6) can be shown by

$\displaystyle H_{\ell}(P)-H_{\ell}(Q)$
$\displaystyle\leq\mathbb{E}_{P}[\ell(Z,a_{Q})]-\mathbb{E}_{Q}[\ell(Z,a_{Q})]$
(8) $\displaystyle=\int_{{\mathsf{Z}}}\ell(z,a_{Q})(P-Q)({\rm d}z)$ (9)
$\displaystyle=\int_{{\mathsf{Z}}}\big{(}\ell(z,a_{Q})-(\alpha_{Q}+\beta_{Q})/2\big{)}(P-Q)({\rm
d}z)$ (10)
$\displaystyle\leq\int_{{\mathsf{Z}}}\frac{\beta_{Q}-\alpha_{Q}}{2}|P-Q|({\rm
d}z)$ (11) $\displaystyle=(\beta_{Q}-\alpha_{Q})d_{\rm TV}(P,Q),$ (12)

where the first step follows from Lemma 1, and the last step follows the
definition of $d_{\rm TV}(P,Q)$. The upper bound in (7) follows by exchanging
the roles of $P$ and $Q$, and the fact that $d_{\rm TV}(P,Q)=d_{\rm TV}(Q,P)$.
∎

####  2.1.2 Examples

Applying Theorem 1 to the log loss, we obtain new bounds for the
Shannon/differential entropy.

######  Corollary 1.

For both discrete and continuous ${\mathsf{Z}}$, let
$\bar{P}=\sup_{z\in{\mathsf{Z}}}P(z)/\inf_{z\in{\mathsf{Z}}}P(z)$ and
$\bar{Q}=\sup_{z\in{\mathsf{Z}}}Q(z)/\inf_{z\in{\mathsf{Z}}}Q(z)$. Then

$\displaystyle H_{\log}(P)-H_{\log}(Q)\leq\big{(}\log\bar{Q}\big{)}d_{\rm
TV}(P,Q),$ (13)

and

$\displaystyle|H_{\log}(P)-H_{\log}(Q)|\leq\big{(}\log(\bar{P}\vee\bar{Q})\big{)}d_{\rm
TV}(P,Q).$ (14)

Next, applying Theorem 1 to the quadratic loss, we obtain a bound for the
variance difference between two distributions on a bounded interval in terms
of their total variation distance.

######  Corollary 2.

If ${\mathsf{Z}}\subset[\alpha,\beta]\subset\mathbb{R}$, then

$\displaystyle\big{|}{\rm Var}_{P}[Z]-{\rm
Var}_{Q}[Z]\big{|}\leq(\beta-\alpha)^{2}d_{\rm TV}(P,Q).$ (15)

###### Proof.

From the assumption that ${\mathsf{Z}}\subset[\alpha,\beta]$, we have that for
any $z\in{\mathsf{Z}}$,
$0\leq\ell(z,a_{P})=(z-\mathbb{E}_{P}Z)^{2}\leq(\beta-\alpha)^{2}$ and
$0\leq\ell(z,a_{Q})=(z-\mathbb{E}_{Q}Z)^{2}\leq(\beta-\alpha)^{2}$. The result
then follows from Theorem 1. ∎

Additionally, applying Theorem 1 to the zero-one loss, we immediately have the
following result.

######  Corollary 3.

If ${\mathsf{Z}}$ is discrete, then

$\displaystyle\big{|}\max_{z\in{\mathsf{Z}}}P(z)-\max_{z\in{\mathsf{Z}}}Q(z)\big{|}\leq
d_{\rm TV}(P,Q).$ (16)

###  2.2 Bounds via KL divergence

####  2.2.1 General results

The next set of results present sufficient conditions for the entropy
difference to be controlled by the KL divergence between the two
distributions. These results may apply to the generalized entropy with an
unbounded loss function. Recall that a random variable $U$ is
$\sigma^{2}$-subgaussian if $\mathbb{E}[e^{\lambda(U-\mathbb{E}U)}]\leq
e^{\lambda^{2}\sigma^{2}/2}$ for all $\lambda\in\mathbb{R}$.

######  Theorem 2.

If $\ell(Z,a_{Q})$ is $\sigma_{Q}^{2}$-subgaussian under $Q$, then

$\displaystyle H_{\ell}(P)-H_{\ell}(Q)\leq\sqrt{2\sigma_{Q}^{2}D(P\|Q)};$ (17)

for the other direction, if $\ell(Z,a_{P})$ is $\sigma_{P}^{2}$-subgaussian
under $Q$, then

$\displaystyle H_{\ell}(Q)-H_{\ell}(P)\leq\sqrt{2\sigma_{P}^{2}D(P\|Q)}.$ (18)

More generally, if there exists a function $\varphi_{Q}$ over $[0,b_{Q})$ with
some $b_{Q}\in(0,\infty]$ such that

$\displaystyle\log\mathbb{E}_{Q}\left[e^{\lambda\left(\ell(Z,a_{Q})-\mathbb{E}_{Q}[\ell(Z,a_{Q})]\right)}\right]\leq\varphi_{Q}(\lambda)$
(19)

for all $0\leq\lambda<b_{Q}$, then

$\displaystyle H_{\ell}(P)-H_{\ell}(Q)\leq\varphi_{Q}^{*-1}(D(P\|Q));$ (20)

for the other direction, if there exists a function $\varphi_{P}$ over
$[0,b_{P})$ with some $b_{P}\in(0,\infty]$ such that

$\displaystyle\log\mathbb{E}_{Q}\left[e^{-\lambda\left(\ell(Z,a_{P})-\mathbb{E}_{Q}[\ell(Z,a_{P})]\right)}\right]\leq\varphi_{P}(\lambda)\quad$
(21)

for all $0\leq\lambda<b_{P}$, then

$\displaystyle H_{\ell}(Q)-H_{\ell}(P)\leq\varphi_{P}^{*-1}(D(P\|Q));$ (22)

where
$\varphi_{Q}^{*}(\gamma)\triangleq\sup_{0\leq\lambda<b_{Q}}\lambda\gamma-\varphi_{Q}(\lambda)$
and
$\varphi_{P}^{*}(\gamma)\triangleq\sup_{0\leq\lambda<b_{P}}\lambda\gamma-\varphi_{P}(\lambda),$
$\gamma\in\mathbb{R}$, are Legendre duals of $\varphi_{Q}$ and $\varphi_{P}$;
and $\varphi_{Q}^{*-1}$ and $\varphi_{P}^{*-1}$ are the generalized inverses
of $\varphi_{Q}^{*}$ and $\varphi_{P}^{*}$, defined as
$\varphi_{Q}^{*-1}(x)\triangleq\sup\\{\gamma\in\mathbb{R}:\varphi_{Q}^{*}(\gamma)\leq
x\\}$ and
$\varphi_{P}^{*-1}(x)\triangleq\sup\\{\gamma\in\mathbb{R}:\varphi_{P}^{*}(\gamma)\leq
x\\},$ $x\in\mathbb{R}$. In addition, if $\varphi_{Q}(\lambda)$ is strictly
convex over $(0,b_{Q})$ and $\varphi_{Q}(0)=\varphi_{Q}^{\prime}(0)=0$, then
$\lim_{x\downarrow 0}\varphi_{Q}^{*-1}(x)=0;$ similarly, if
$\varphi_{P}(\lambda)$ is strictly convex over $(0,b_{P})$ and
$\varphi_{P}(0)=\varphi_{P}^{\prime}(0)=0$, then $\lim_{x\downarrow
0}\varphi_{P}^{*-1}(x)=0.$

Remark. By exchanging the roles of $P$ and $Q$ in Theorem 2, we can obtain
another set of bounds for the entropy difference in terms of $D(Q\|P)$ under
appropriate conditions.

###### Proof of Theorem 2.

The results in (17) and (18) are special cases of the general results in (20)
and (22) respectively, with
$\varphi_{Q}(\lambda)={\sigma_{Q}^{2}\lambda^{2}}/{2}$,
$\varphi_{P}(\lambda)=\sigma_{P}^{2}\lambda^{2}/2$, and $b_{Q}=b_{P}=\infty$,
such that $\varphi_{Q}^{*}(\gamma)={\gamma^{2}}/{2\sigma_{Q}^{2}}$ and
$\varphi_{P}^{*}(\gamma)={\gamma^{2}}/{2\sigma_{P}^{2}}$. The general results
are consequences of Lemma 1 and Lemma 2 stated below, instantiated with
$f(z)=\ell(z,a_{Q})$, $\varphi_{+}(\lambda)=\varphi_{Q}(\lambda)$ and
$b_{+}=b_{Q}$ for (20), and with $f(z)=\ell(z,a_{P})$,
$\varphi_{-}(\lambda)=\varphi_{P}(\lambda)$ and $b_{-}=b_{P}$ for (22). ∎

######  Lemma 2.

For distributions $P$ and $Q$ on an arbitrary set ${\mathsf{Z}}$ and a
function $f:{\mathsf{Z}}\rightarrow\mathbb{R}$, if there exists a function
$\varphi_{+}$ over $[0,b_{+})$ with some $b_{+}\in(0,\infty]$ such that

$\displaystyle\log\mathbb{E}_{Q}\left[e^{\lambda\left(f(Z)-\mathbb{E}_{Q}f(Z)\right)}\right]\leq\varphi_{+}(\lambda),\quad\forall\,0\leq\lambda<b_{+},$
(23)

then

$\displaystyle\mathbb{E}_{P}[f(Z)]-\mathbb{E}_{Q}[f(Z)]\leq\varphi_{+}^{*-1}(D(P\|Q));$
(24)

for the other direction, if there exists a function $\varphi_{-}$ over
$[0,b_{-})$ with some $b_{-}\in(0,\infty]$ such that

$\displaystyle\log\mathbb{E}_{Q}\Big{[}e^{-\lambda\left(f(Z)-\mathbb{E}_{Q}f(Z)\right)}\Big{]}\leq\varphi_{-}(\lambda),\quad\forall\,0\leq\lambda<b_{-},$
(25)

then

$\displaystyle\mathbb{E}_{Q}[f(Z)]-\mathbb{E}_{P}[f(Z)]\leq\varphi_{-}^{*-1}(D(P\|Q));$
(26)

where

$\displaystyle\varphi_{+}^{*}(\gamma)$
$\displaystyle\triangleq\sup_{0\leq\lambda\leq
b_{+}}\lambda\gamma-\varphi_{+}(\lambda),\quad\gamma\in\mathbb{R}$ (27)
$\displaystyle\varphi_{-}^{*}(\gamma)$
$\displaystyle\triangleq\sup_{0\leq\lambda\leq
b_{-}}\lambda\gamma-\varphi_{-}(\lambda),\quad\gamma\in\mathbb{R}$ (28)

are Legendre duals of $\varphi_{+}$ and $\varphi_{-}$, and $\varphi_{+}^{*-1}$
and $\varphi_{-}^{*-1}$ are the generalized inverses of $\varphi_{+}^{*}$ and
$\varphi_{-}^{*}$,

$\displaystyle\varphi_{+}^{*-1}(x)$
$\displaystyle\triangleq\sup\\{\gamma\in\mathbb{R}:\varphi_{+}^{*}(\gamma)<x\\},\quad
x\in\mathbb{R}$ (29) $\displaystyle\varphi_{-}^{*-1}(x)$
$\displaystyle\triangleq\sup\\{\gamma\in\mathbb{R}:\varphi_{-}^{*}(\gamma)<x\\},\quad
x\in\mathbb{R}.$ (30)

In addition, if $\varphi_{+}(\lambda)$ is strictly convex over $(0,b_{+})$ and
$\varphi_{+}(0)=\varphi_{+}^{\prime}(0)=0$, then

$\displaystyle\lim_{x\downarrow 0}\varphi_{+}^{*-1}(x)=0;$ (31)

similarly, if $\varphi_{-}(\lambda)$ is strictly convex over $(0,b_{-})$ and
$\varphi_{-}(0)=\varphi_{-}^{\prime}(0)=0$, then

$\displaystyle\lim_{x\downarrow 0}\varphi_{-}^{*-1}(x)=0.$ (32)

As a concrete example of Lemma 2, if $f(Z)$ is $\sigma^{2}$-subgaussian under
$Q$, then choosing
$\varphi_{+}(\lambda)=\varphi_{-}(\lambda)=\sigma^{2}\lambda^{2}/2$ and
$b_{+}=b_{-}=\infty$ leads to the well-known bound

$\displaystyle|\mathbb{E}_{P}f(Z)-\mathbb{E}_{Q}f(Z)|\leq\sqrt{2\sigma^{2}D(P\|Q)},$
(33)

which is used in proving (17) and (18).

Lemma 2 is proved in Appendix A. The proof is adapted from [12, Lemma 4.18],
[13, Theorem 2] and [14, Theorem 1]. It is worthwhile to point out that by
properly defining the inverse functions $\varphi_{+}^{*-1}$ and
$\varphi_{-}^{*-1}$, the restrictions on the functions $\varphi_{+}$ and
$\varphi_{-}$ in terms of convexity and boundary conditions
$\varphi_{\pm}(0)=\varphi_{\pm}^{\prime}(0)=0$ imposed in the references are
not needed to prove (24) and (26). However, with these conditions we can show
that $\lim_{x\downarrow 0}\varphi_{+}^{*-1}(x)=0$ and $\lim_{x\downarrow
0}\varphi_{-}^{*-1}(x)=0$, which is needed by Theorem 2 for proving the
continuity of the generalized entropy.

####  2.2.2 Example: variance comparison against Gaussian

As the first application of the general results in Theorem 2, we consider
bounding the variance difference between an arbitrary real-valued random
variable, potentially unbounded, and a Gaussian random variable.

######  Corollary 4.

For the quadratic loss, if $Z$ is Gaussian with variance $\sigma^{2}$ and an
arbitrary mean under $Q$, then for any $P$ on $\mathbb{R}$,

$\displaystyle\big{|}{\rm Var}_{P}[Z]-{\rm Var}_{Q}[Z]\big{|}$
$\displaystyle\leq 2\sigma^{2}\Big{(}\sqrt{D(P\|Q)}+D(P\|Q)\Big{)}.$ (34)

###### Proof.

We first prove that

$\displaystyle{\rm Var}_{P}[Z]-{\rm Var}_{Q}[Z]$ $\displaystyle\leq
2\sigma^{2}\Big{(}\sqrt{D(P\|Q)}+D(P\|Q)\Big{)}.$ (35)

Under $Q$, $(Z-\mathbb{E}_{Q}Z)^{2}$ has the same distribution as
$\sigma^{2}U^{2}$, where $U$ is standard Gaussian. From the moment generating
function of the $\chi^{2}$ random variable, we have

$\displaystyle\log\mathbb{E}_{Q}\left[e^{\lambda\left((Z-\mathbb{E}_{Q}Z)^{2}-\sigma^{2}\right)}\right]=-\frac{1}{2}\log(1-2\sigma^{2}\lambda)-\sigma^{2}\lambda,\quad-\infty<\lambda<\frac{1}{2\sigma^{2}}.$
(36)

It can be verified that (19) in Theorem 2 is satisfied with
$\varphi_{Q}(\lambda)=\sigma^{4}\lambda^{2}/(1-2\sigma^{2}\lambda)$ and
$b_{Q}={1}/{2\sigma^{2}}$ [12, Section 2.4], i.e.,

$\displaystyle\log\mathbb{E}_{Q}\left[e^{\lambda\left((Z-\mathbb{E}_{Q}Z)^{2}-\sigma^{2}\right)}\right]<\frac{(\sigma^{2}\lambda)^{2}}{(1-2\sigma^{2}\lambda)},\quad\forall\,\,0<\lambda<\frac{1}{2\sigma^{2}}.$
(37)

Further, we have
$\varphi_{Q}^{*}(\gamma)=(\sqrt{2\gamma+\sigma^{2}}-\sigma)^{2}/4\sigma^{2}$
and $\varphi_{Q}^{*-1}(x)=2\sigma^{2}(\sqrt{x}+x)$, which leads to (35) by
(20) in Theorem 2.

Next, we prove the other direction

$\displaystyle{\rm Var}_{Q}[Z]-{\rm Var}_{P}[Z]$ $\displaystyle\leq
2\sigma^{2}\Big{(}\sqrt{D(P\|Q)}+D(P\|Q)\Big{)}.$ (38)

Under $Q$, $(Z-\mathbb{E}_{P}Z)^{2}$ has the same distribution as
$\sigma^{2}U^{2}$, where $U$ is Gaussian with mean
$(\mathbb{E}_{Q}[Z]-\mathbb{E}_{P}[Z])/\sigma$ and variance $1$. From the
moment generating function of the non-central $\chi^{2}$ random variable, we
have

$\displaystyle\log\mathbb{E}_{Q}\left[e^{-\lambda\left((Z-\mathbb{E}_{P}[Z])^{2}-\mathbb{E}_{Q}[(Z-\mathbb{E}_{P}Z)^{2}]\right)}\right]=$
$\displaystyle-\frac{1}{2}\log(1+2\sigma^{2}\lambda)+\lambda\mathbb{E}_{Q}[(Z-\mathbb{E}_{P}[Z])^{2}]$
$\displaystyle-\frac{(\mathbb{E}_{Q}[Z]-\mathbb{E}_{P}[Z])^{2}\lambda}{1+2\sigma^{2}\lambda},\quad-\frac{1}{2\sigma^{2}}<\lambda<\infty.$
(39)

Dropping the last term when $\lambda>0$, we have

$\displaystyle\log\mathbb{E}_{Q}\left[e^{-\lambda\left((Z-\mathbb{E}_{P}[Z])^{2}-\mathbb{E}_{Q}[(Z-\mathbb{E}_{P}Z)^{2}]\right)}\right]\leq-\frac{1}{2}\log(1+2\sigma^{2}\lambda)+\lambda\mathbb{E}_{Q}[(Z-\mathbb{E}_{P}[Z])^{2}],\quad\forall\lambda>0.$
(40)

It can be verified via Taylor expansion of the right side of (40) that (21) in
Theorem 2 is satisfied with
$\varphi_{P}(\lambda)=\sigma^{4}\lambda^{2}-\big{(}\sigma^{2}-\mathbb{E}_{Q}[(Z-\mathbb{E}_{P}Z)^{2}]\big{)}\lambda$
and $b_{P}=\infty$, i.e.,

$\displaystyle\log\mathbb{E}_{Q}\left[e^{-\lambda\left((Z-\mathbb{E}_{P}[Z])^{2}-\mathbb{E}_{Q}[(Z-\mathbb{E}_{P}Z)^{2}]\right)}\right]\leq\sigma^{4}\lambda^{2}-\big{(}\sigma^{2}-\mathbb{E}_{Q}[(Z-\mathbb{E}_{P}Z)^{2}]\big{)}\lambda,\quad\forall\lambda>0.$
(41)

Further, we have
$\varphi_{P}^{*}(\gamma)=(\gamma+\sigma^{2}-\mathbb{E}_{Q}[(Z-\mathbb{E}_{P}Z)^{2}])^{2}/4\sigma^{4}$
and
$\varphi_{P}^{*-1}(x)=2\sigma^{2}\sqrt{x}+(\mathbb{E}_{P}[Z]-\mathbb{E}_{Q}[Z])^{2}$,
which leads to

$\displaystyle{\rm Var}_{Q}[Z]-{\rm Var}_{P}[Z]$ $\displaystyle\leq
2\sigma^{2}\sqrt{D(P\|Q)}+\big{(}\mathbb{E}_{P}[Z]-\mathbb{E}_{Q}[Z]\big{)}^{2}$
(42)

by (22) in Theorem 2. The upper bound in (38) then follows from the fact that
$(\mathbb{E}_{P}[Z]-\mathbb{E}_{Q}[Z])^{2}\leq 2\sigma^{2}D(P\|Q)$, which is
in turn due to the fact that $Z$ is Gaussian with variance $\sigma^{2}$ under
$Q$ and (33) as a consequence of Lemma 2. ∎

####  2.2.3 Example: bounded loss functions

Next, we apply Theorem 2 to the cases where the loss function is bounded.
Using the fact that a bounded random variable taking values in
$[\alpha,\beta]$ is $(\beta-\alpha)^{2}/4$-subgaussian under any distribution,
Theorem 2 leads to the following corollary.

######  Corollary 5.

If $\ell(\cdot,a_{Q})\in[\alpha_{Q},\beta_{Q}]$ for all $z\in{\mathsf{Z}}$,
then

$\displaystyle
H_{\ell}(P)-H_{\ell}(Q)\leq(\beta_{Q}-\alpha_{Q})\sqrt{\frac{1}{2}D(P\|Q)};$
(43)

if $\ell(\cdot,a_{P})\in[\alpha_{P},\beta_{P}]$ for all $z\in{\mathsf{Z}}$,
then

$\displaystyle
H_{\ell}(Q)-H_{\ell}(P)\leq(\beta_{P}-\alpha_{P})\sqrt{\frac{1}{2}D(P\|Q)}.$
(44)

In particular, for the log loss, using the notation in Corollary 1,

$\displaystyle|H_{\log}(P)-H_{\log}(Q)|\leq\big{(}\log(\bar{P}\vee\bar{Q})\big{)}\sqrt{\frac{1}{2}D(P\|Q)};$
(45)

for the quadratic loss, if
${\mathsf{Z}}\subset[\alpha,\beta]\subset\mathbb{R}$, then

$\displaystyle\big{|}{\rm Var}_{P}[Z]-{\rm
Var}_{Q}[Z]\big{|}\leq(\beta-\alpha)^{2}\sqrt{\frac{1}{2}D(P\|Q)};$ (46)

while for the zero-one loss,

$\displaystyle|H_{01}(P)-H_{01}(Q)|\leq\sqrt{\frac{1}{2}D(P\|Q)}.$ (47)

The results in Corollary 5 can also be derived from Theorem 1, Corollary 1, 2,
and 3 respectively, via Pinsker’s inequality [15].

####  2.2.4 Example: subgaussian log loss and connection to Rényi entropy
order

For the log loss, Theorem 2 also provide bounds for the case where
$\ell(\cdot,a_{Q})$ and $\ell(\cdot,a_{P})$ are unbounded but subgaussian, as
stated in Corollary 6 below. The results reveal a connection between the
continuity of the Shannon/differential entropy in distribution and the
deviation of the Rényi (cross) entropy from the ordinary (cross) entropy. We
define the _Rényi cross entropy_ as follows.

######  Definition 1.

For distributions $P$ and $Q$ on ${\mathsf{Z}}$, the Rényi cross entropy
between $Q$ and $P$ of order $\alpha$, where
$\alpha\in\mathbb{R}\setminus\\{1\\}$, is defined as

$\displaystyle
R_{\alpha}(Q,P)\triangleq\frac{1}{1-\alpha}\log\int_{{\mathsf{Z}}}Q({\rm
d}z)P(z)^{\alpha-1}.$ (48)

Using L’Hôspital’s rule, it can be shown that $\lim_{\alpha\rightarrow
1}R_{\alpha}(Q,P)=R_{1}(Q,P)\triangleq-\int_{{\mathsf{Z}}}Q({\rm d}z)\log
P(z),$ which is the ordinary cross entropy between $Q$ and $P$. When $P=Q$,
$R_{\alpha}(Q,Q)$ can be written as

$\displaystyle
R_{\alpha}(Q)\triangleq\frac{1}{1-\alpha}\log\int_{{\mathsf{Z}}}Q({\rm
d}z)Q(z)^{\alpha-1},\quad\alpha\neq 1,$ (49)

which is the Rényi entropy of order $\alpha$ of $Q$; and
$\lim_{\alpha\rightarrow 1}R_{\alpha}(Q)=R_{1}(Q)\triangleq H_{\log}(Q)$ is
the ordinary entropy of $Q$, which is the Shannon entropy if ${\mathsf{Z}}$ is
discrete and the differential entropy if ${\mathsf{Z}}$ is continuous. Note
that with the above definitions, $\alpha$ can take any value in $\mathbb{R}$,
so that $R_{\alpha}(Q,P)$ and $R_{\alpha}(Q)$ can be either positive or
negative.

######  Corollary 6.

For the log loss, if there exists $\sigma_{Q}>0$ such that
$R_{1-\lambda}(Q)-R_{1}(Q)\leq{\lambda\sigma_{Q}^{2}}/{2}$ for all
$\lambda>0$, then

$\displaystyle H_{\log}(P)-H_{\log}(Q)\leq\sqrt{2\sigma_{Q}^{2}D(P\|Q)}.$ (50)

For the other direction, if there exists $\sigma_{P}>0$ such that
$R_{1}(Q,P)-R_{1+\lambda}(Q,P)\leq{\lambda\sigma_{P}^{2}}/{2}$ for all
$\lambda>0$, then

$\displaystyle H_{\log}(Q)-H_{\log}(P)\leq\sqrt{2\sigma_{P}^{2}D(P\|Q)}.$ (51)

###### Proof.

To prove the first upper bound, note that

$\displaystyle\log\mathbb{E}_{Q}\big{[}e^{\lambda(-\log
Q(Z)-\mathbb{E}_{Q}[-\log Q(Z)])}\big{]}=\lambda(R_{1-\lambda}(Q)-R_{1}(Q)).$
(52)

If $R_{1-\lambda}(Q)-R_{1}(Q)\leq{\lambda\sigma_{Q}^{2}}/{2}$ for all
$\lambda>0$, then we can make use of (20) in Theorem 2 with
$\varphi_{Q}(\lambda)={\lambda^{2}\sigma_{Q}^{2}}/{2}$, and get

$\displaystyle H_{\log}(P)-H_{\log}(Q)\leq\sqrt{2\sigma_{Q}^{2}D(P\|Q)}.$ (53)

Similarly, for the second upper bound, note that

$\displaystyle\log\mathbb{E}_{Q}\big{[}e^{-\lambda(-\log
P(Z)-\mathbb{E}_{Q}[-\log
P(Z)])}\big{]}=\lambda(R_{1}(Q,P)-R_{1+\lambda}(Q,P)).$ (54)

If $R_{1}(Q,P)-R_{1+\lambda}(Q,P)\leq{\lambda\sigma_{P}^{2}}/{2}$ for all
$\lambda>0$, then we can make use of (22) in Theorem 2 with
$\varphi_{P}(\lambda)={\lambda^{2}\sigma_{P}^{2}}/{2}$, and get

$\displaystyle H_{\log}(Q)-H_{\log}(P)\leq\sqrt{2\sigma_{P}^{2}D(P\|Q)}.$ (55)

∎

The upper bound in (50) of Corollary 6 essentially states that if the Rényi
entropy of a distribution is Lipschitz continuous in the entropy order at
order 1, then the Shannon/differential entropy is upper-semicontinuous at that
distribution. Further, if both $\sigma_{Q}$ and $\sigma_{P}$ in Corollary 6
are upper-bounded by some $\beta>0$ for all $P$ within a small neighborhood of
$Q$ in terms of KL divergence, then it implies that the Shannon/differential
entropy is continuous at $Q$.

###  2.3 Bounds via $\chi^{2}$ divergence

####  2.3.1 General results

To further investigate the conditions for the generalized entropy with
unbounded loss functions to be continuous, we consider the continuity in terms
of the $\chi^{2}$ divergence, defined as
$\chi^{2}(P\|Q)\triangleq\mathbb{E}_{Q}[(\frac{{\rm d}P}{{\rm d}Q}-1)^{2}]$.

######  Theorem 3.

For distributions $P$ and $Q$ on ${\mathsf{Z}}$, if ${\rm
Var}_{Q}[\ell(Z,a_{Q})]$ and ${\rm Var}_{Q}[\ell(Z,a_{P})]$ exist, then

$\displaystyle H_{\ell}(P)-H_{\ell}(Q)$ $\displaystyle\leq\sqrt{{\rm
Var}_{Q}[\ell(Z,a_{Q})]\chi^{2}(P\|Q)},$ (56)

and

$\displaystyle H_{\ell}(Q)-H_{\ell}(P)$ $\displaystyle\leq\sqrt{{\rm
Var}_{Q}[\ell(Z,a_{P})]\chi^{2}(P\|Q)}.$ (57)

Remark. By exchanging the roles of $P$ and $Q$ in Theorem 3, we can obtain
another set of bounds for the entropy difference in terms of $\chi^{2}(Q\|P)$
under appropriate conditions.

###### Proof of Theorem 3.

The proof is based on the Hammersley-Chapman-Robbins (HCR) lower bound for
$\chi^{2}$ divergence [16], which states that for any distributions $P_{U}$
and $Q_{U}$ on a set ${\mathsf{U}}$,

$\displaystyle\chi^{2}(P_{U}\|Q_{U})\geq\frac{(\mathbb{E}[P_{U}]-\mathbb{E}[Q_{U}])^{2}}{{\rm
Var}[Q_{U}]}.$ (58)

Applying the HCR lower bound to $\ell(Z,a_{Q})$ and $\ell(Z,a_{P})$ in the
upper and lower bound in Lemma 1 respectively, and using the data processing
inequality for $\chi^{2}$ divergence, we obtain the bounds in (56) and (57). ∎

The upper bound in (56) of Theorem 3 implies that the generalized entropy is
upper semicontinuous at $Q$ in terms of $\chi^{2}$ divergence, as long as
${\rm Var}_{Q}[\ell(Z,a_{Q})]$ is finite. Further, if ${\rm
Var}_{Q}[\ell(Z,a_{P})]$ is upper-bounded by some $\beta>0$ for all $P$ within
a small neighborhood of $Q$ in terms of $\chi^{2}$ divergence, then Theorem 3
implies that the generalized entropy is continuous at $Q$. Compared with the
conditions for continuity in terms of total variation distance and KL
divergence as stated in Theorem 1 and Theorem 2, continuity of the generalized
entropy in terms of $\chi^{2}$ divergence requires minimal conditions on
$\ell$ and $Q$ as shown in Theorem 3.

####  2.3.2 Examples

Applying Theorem 3 to the log loss, we get the following results for
Shannon/differential entropy.

######  Corollary 7.

For distributions $P$ and $Q$ on ${\mathsf{Z}}$, we have

$\displaystyle H_{\log}(P)-H_{\log}(Q)\leq\sqrt{{\rm
Var}_{Q}[\log{Q(Z)}]\chi^{2}(P\|Q)},$ (59)

where ${\rm Var}_{Q}[\log{Q(Z)}]$ is known as the varentropy of distribution
$Q$ [17]. Moreover,

$\displaystyle H_{\log}(Q)-H_{\log}(P)\leq\sqrt{{\rm
Var}_{Q}[\log{P(Z)}]\chi^{2}(P\|Q)},$ (60)

where ${\rm Var}_{Q}[\log{P(Z)}]$ may be called the cross varentropy of
distribution $P$ under distribution $Q$.

Applying Theorem 3 to the quadratic loss, we can deduce the following bounds
on the variance difference.

######  Corollary 8.

For distributions $P$ and $Q$ on ${\mathsf{Z}}\subset\mathbb{R}$, we have

$\displaystyle{\rm Var}_{P}[Z]-{\rm Var}_{Q}[Z]\leq\sqrt{{\rm
Var}_{Q}\big{[}(Z-\mathbb{E}_{Q}[Z])^{2}\big{]}\chi^{2}(P\|Q)},$ (61)

and

$\displaystyle{\rm Var}_{Q}[Z]-{\rm Var}_{P}[Z]\leq\sqrt{{\rm
Var}_{Q}\big{[}(Z-\mathbb{E}_{P}[Z])^{2}\big{]}\chi^{2}(P\|Q)}.$ (62)

Compared with Corollary 1 and Corollary 2, we see that the results in
Corollary 7 and Corollary 8 do not require $Z$ or its log probability to take
values in a bounded interval.

###  2.4 Bounds via $D(P_{\ell},Q_{\ell})$

We have derived bounds for the entropy difference in terms of several
$f$-divergences between distributions $P$ and $Q$ on ${\mathsf{Z}}$, which
lead to sufficient conditions on the entropy continuity. If our purpose is
merely bounding the entropy difference rather than examining its dependence on
some statistical distance $D(P,Q)$, we may bound it in terms of the
distributional change of the loss when an optimal action is taken, e.g. either
$\ell(Z,a_{P})$ or $\ell(Z,a_{Q})$, when the distribution of $Z$ changes from
$P$ to $Q$. Specifically, the following result is a consequence of Lemma 1 and
the proof techniques used in the previous subsections.

######  Theorem 4.

For all the results derived in Sections 2.1, 2.2 and 2.3, the upper bounds for
$H_{\ell}(P)-H_{\ell}(Q)$ continue to hold when the corresponding statistical
distance $D(P,Q)$ is replaced by $D(P_{\ell(Z,a_{Q})},Q_{\ell(Z,a_{Q})})$; and
the upper bounds for $H_{\ell}(Q)-H_{\ell}(P)$ continue to hold when $D(P,Q)$
is replaced by $D(P_{\ell(Z,a_{P})},Q_{\ell(Z,a_{P})})$.

Due to the data processing inequality of the $f$-divergence, the bounds
described in Theorem 4 are tighter than their counterparts in the previous
sections. To illustrate the potential improvement, we examine a case where
${\mathsf{Z}}=\mathbb{R}^{p}$,
${\mathsf{A}}=\\{a\in\mathbb{R}^{p}:\|a\|=1\\}$, and $\ell(z,a)=-a^{\top}z$.
Let the distributions $P$ and $Q$ on ${\mathsf{Z}}$ be
$\mathcal{N}(\mu_{P},\sigma_{P}^{2}\mathbf{I})$ and
$\mathcal{N}(\mu_{Q},\sigma_{Q}^{2}\mathbf{I})$, with mean vectors
$\mu_{P},\mu_{Q}\in\mathbb{R}^{p}$ and elementwise variances $\sigma_{P}^{2}$
and $\sigma_{Q}^{2}$. Then, $H_{\ell}(P)=-\|\mu_{P}\|$ and
$H_{\ell}(Q)=-\|\mu_{Q}\|$, with $a_{P}=\mu_{P}/\|\mu_{P}\|$ and
$a_{Q}=\mu_{Q}/\|\mu_{Q}\|$. In addition, under $P$,
$\ell(Z,a_{P})\sim\mathcal{N}(-\|\mu_{P}\|,\sigma_{P}^{2})$ and
$\ell(Z,a_{Q})\sim\mathcal{N}(-\mu_{Q}^{\top}\mu_{P}/\|\mu_{Q}\|,\sigma_{P}^{2})$;
while under $Q$,
$\ell(Z,a_{P})\sim\mathcal{N}(-\mu_{P}^{\top}\mu_{Q}/\|\mu_{P}\|,\sigma_{Q}^{2})$
and $\ell(Z,a_{Q})\sim\mathcal{N}(-\|\mu_{Q}\|,\sigma_{Q}^{2})$. Applying
Theorem 4 to (17) and (18), respectively, in Theorem 2 yields

$\displaystyle
H_{\ell}(P)-H_{\ell}(Q)\leq\sqrt{\Big{(}\|\mu_{Q}\|-\frac{\mu_{Q}^{\top}\mu_{P}}{\|\mu_{Q}\|}\Big{)}^{2}+\sigma_{Q}^{2}\Big{(}\frac{\sigma_{P}^{2}}{\sigma_{Q}^{2}}-1-\log\frac{\sigma_{P}^{2}}{\sigma_{Q}^{2}}\Big{)}},$
(63)

and

$\displaystyle
H_{\ell}(Q)-H_{\ell}(P)\leq\sqrt{\Big{(}\|\mu_{P}\|-\frac{\mu_{P}^{\top}\mu_{Q}}{\|\mu_{P}\|}\Big{)}^{2}+\sigma_{Q}^{2}\Big{(}\frac{\sigma_{P}^{2}}{\sigma_{Q}^{2}}-1-\log\frac{\sigma_{P}^{2}}{\sigma_{Q}^{2}}\Big{)}},$
(64)

where the upper bounds do not depend on the dimension $p$ of ${\mathsf{Z}}$.
On the contrary, directly applying Theorem 2 yields

$\displaystyle|H_{\ell}(Q)-H_{\ell}(P)|\leq\sqrt{\|\mu_{P}-\mu_{Q}\|^{2}+p\sigma_{Q}^{2}\Big{(}\frac{\sigma_{P}^{2}}{\sigma_{Q}^{2}}-1-\log\frac{\sigma_{P}^{2}}{\sigma_{Q}^{2}}\Big{)}},$
(65)

where the upper bound scales in $p$ as $O(\sqrt{p})$. This example shows that
by considering the distributional change of the loss, Theorem 4 can provide
much tighter bounds on the entropy difference than the results obtained in the
previous subsections.

###  2.5 Bounds via Wasserstein distance

Another way to incorporate the loss function to the statistical distance
between $P$ and $Q$ on ${\mathsf{Z}}$ is by constructing a Wasserstein
distance according to the property of $\ell$. We propose a general method to
bound the entropy difference in terms of the Wasserstein distance. Suppose
${\mathsf{Z}}$ is a metric space with some metric
$d:{\mathsf{Z}}\times{\mathsf{Z}}\rightarrow\mathbb{R}_{+}$, then a
Wasserstein distance ${\mathcal{W}}_{d}$ w.r.t. $d$ can be defined for
distributions on ${\mathsf{Z}}$ as

$\displaystyle{\mathcal{W}}_{d}(P,Q)\triangleq\inf_{P_{U,V}\in\Pi(P,Q)}\mathbb{E}[d(U,V)],$
(66)

where $\Pi$ is the set of joint distributions on
${\mathsf{Z}}\times{\mathsf{Z}}$ with marginal distributions $P$ and $Q$. One
can also define the Wasserstein distance w.r.t. $d$ of order $q$, with
$q\in[1,\infty)$, as
$\mathcal{W}_{d,q}(P,Q)\triangleq\inf_{P_{U,V}\in\Pi(P,Q)}\mathbb{E}[d(U,V)^{q}]^{1/q}.$
A useful property of the Wasserstein distance is the Kantorovich-Rubinstein
duality,

$\displaystyle{\mathcal{W}}_{d}(P,Q)=\sup_{f:{\mathsf{Z}}\rightarrow\mathbb{R},\,\|f\|_{\rm
Lip}\leq 1}(\mathbb{E}_{P}f-\mathbb{E}_{Q}f),$ (67)

where $\|f\|_{\rm Lip}$ is the minimum value of $\alpha$ such that
$|f(z)-f(z^{\prime})|\leq\alpha d(z,z^{\prime})$ for all
$z,z^{\prime}\in{\mathsf{Z}}$. Under the assumption that the loss function
$\ell(\cdot,a)$ is $\rho$-Lipschitz in $z\in{\mathsf{Z}}$ w.r.t. $d$ for all
$a\in{\mathsf{A}}$, (67) can be invoked to show the following bound on entropy
difference.

######  Theorem 5.

Suppose ${\mathsf{Z}}$ is a metric space with metric $d$. If
$\ell(\cdot,a_{Q})$ is $\rho_{Q}$-Lipschitz in $z\in{\mathsf{Z}}$ w.r.t. $d$,
i.e. $|\ell(z,a_{Q})-\ell(z^{\prime},a_{Q})|\leq\rho d(z,z^{\prime})$ for all
$z,z^{\prime}\in{\mathsf{Z}}$, then

$\displaystyle H_{\ell}(P)-H_{\ell}(Q)$
$\displaystyle\leq\rho_{Q}{\mathcal{W}}_{d}(P,Q);$ (68)

for the other direction, if $\ell(\cdot,a_{P})$ is $\rho_{P}$-Lipschitz in
$z\in{\mathsf{Z}}$ w.r.t. $d$, then

$\displaystyle H_{\ell}(Q)-H_{\ell}(P)$
$\displaystyle\leq\rho_{P}{\mathcal{W}}_{d}(P,Q).$ (69)

###### Proof.

For one direction,

$\displaystyle H_{\ell}(P)-H_{\ell}(Q)$
$\displaystyle\leq\mathbb{E}_{P}[\ell(Z,a_{Q})]-\mathbb{E}_{Q}[\ell(Z,a_{Q})]$
(70)
$\displaystyle\leq\rho_{Q}\sup_{f:{\mathsf{Z}}\rightarrow\mathbb{R},\,\|f\|_{\rm
Lip}\leq 1}(\mathbb{E}_{P}f-\mathbb{E}_{Q}f)$ (71)
$\displaystyle=\rho_{Q}{\mathcal{W}}_{d}(P,Q),$ (72)

where the second inequality is due to the assumption that $\ell(\cdot,a_{Q})$
is $\rho_{Q}$-Lipschitz in $z\in{\mathsf{Z}}$; and the last step is due to the
Kantorovich-Rubinstein duality of Wasserstein distance (67). The other
direction can be proved by exchanging the roles of $P$ and $Q$ and noting that
${\mathcal{W}}_{d}(P,Q)={\mathcal{W}}_{d}(Q,P)$. ∎

As a special case, when ${\mathsf{Z}}={\mathsf{A}}$ and $\ell(\cdot,\cdot)$ is
a metric on ${\mathsf{Z}}$, then $\ell(\cdot,a)$ is $1$-Lipschitz in $z$ for
all $a$ due to the triangle inequality, and we have the following particularly
simple-looking bound.

######  Corollary 9.

If ${\mathsf{Z}}={\mathsf{A}}$ is a metric space with metric
$\ell(\cdot,\cdot)$, then

$\displaystyle|H_{\ell}(P)-H_{\ell}(Q)|$
$\displaystyle\leq\mathcal{W}_{\ell}(P,Q).$ (73)

For example, for the zero-one loss, $\mathcal{W}_{01}(P,Q)=d_{\rm TV}(P,Q)$.
Corollary 9 then implies that

$\displaystyle|H_{01}(P)-H_{01}(Q)|\leq d_{\rm TV}(P,Q),$ (74)

which is the same as the upper bound in Corollary 3. As another example, on
the Euclidean space we have the following result.

######  Corollary 10.

If ${\mathsf{Z}}={\mathsf{A}}=\mathbb{R}^{p}$ and $\ell(z,a)=\|z-a\|$ is the
Euclidean distance on $\mathbb{R}^{p}$, then Corollary 9 implies that

$\displaystyle|H_{\text{\tiny$\|\\!\cdot\\!\|$}}(P)-H_{\text{\tiny$\|\\!\cdot\\!\|$}}(Q)|\leq\mathcal{W}_{\text{\tiny$\|\\!\cdot\\!\|$}}(P,Q).$
(75)

In particular, for $p=1$, Corollary 10 implies that the difference between the
minimum mean absolute deviation under $P$ and $Q$ is upper-bounded by the
Wasserstein distance between $P$ and $Q$ w.r.t. the absolute difference.

In addition, in view of Theorem 4, we have the following bounds for the
entropy difference in terms of the Wasserstein distance between distributions
of the loss.

######  Theorem 6.

Due to Lemma 1 and the Kantorovich-Rubinstein duality of Wasserstein distance,

$\displaystyle H_{\ell}(P)-H_{\ell}(Q)$
$\displaystyle\leq\mathcal{W}_{|\cdot|}(P_{\ell(Z,a_{Q})},Q_{\ell(Z,a_{Q})}),$
(76)

and

$\displaystyle H_{\ell}(Q)-H_{\ell}(P)$
$\displaystyle\leq\mathcal{W}_{|\cdot|}(P_{\ell(Z,a_{P})},Q_{\ell(Z,a_{P})}).$
(77)

###  2.6 Bounds via $({\mathsf{A}},\ell)$-dependent distance

The bounds on entropy difference that have been studied so far are in terms of
various statistical distances between $P$ and $Q$ or between $P_{\ell}$ and
$Q_{\ell}$ that do not directly depend on the action space ${\mathsf{A}}$. To
obtain potentially tighter bounds, we consider distances that explicitly rely
on both ${\mathsf{A}}$ and $\ell$. One such distance can be defined as
follows.

######  Definition 2.

The $({\mathsf{A}},\ell)$-semidistance between distributions $P$ and $Q$ on
${\mathsf{Z}}$ is defined as

$\displaystyle
d_{{\mathsf{A}},\ell}(P,Q)\triangleq\sup_{a\in{\mathsf{A}}}\big{|}\mathbb{E}_{P}[\ell(Z,a)]-\mathbb{E}_{Q}[\ell(Z,a)]\big{|}.$
(78)

It can be checked that $d_{{\mathsf{A}},\ell}$ is symmetric and satisfies the
triangle inequality, but it may happen that $d_{{\mathsf{A}},\ell}(P,Q)=0$ for
$P\neq Q$, e.g. when $\ell\equiv 0$. For this reason, we call
$d_{{\mathsf{A}},\ell}$ a semidistance. Note that $({\mathsf{A}},\ell)$ also
induces a class of functions

$\displaystyle{\mathcal{L}}_{{\mathsf{A}},\ell}\triangleq\\{\ell(\cdot,a):{\mathsf{Z}}\rightarrow\mathbb{R},a\in{\mathsf{A}}\\},$
(79)

such that $d_{{\mathsf{A}},\ell}(P,Q)$ can be rewritten in terms of
${\mathcal{L}}_{{\mathsf{A}},\ell}$ as

$\displaystyle
d_{{\mathsf{A}},\ell}(P,Q)=\sup_{f\in{\mathcal{L}}_{{\mathsf{A}},\ell}}\big{|}\mathbb{E}_{P}[f(Z)]-\mathbb{E}_{Q}[f(Z)]\big{|}.$
(80)

We then see that $d_{\rm TV}(P,Q)$ is a special instance of
$d_{{\mathsf{A}},\ell}(P,Q)$ with ${\mathcal{L}}_{{\mathsf{A}},\ell}$ being
the set of measurable functions $f:{\mathsf{Z}}\rightarrow[0,1]$.
Additionally, $W_{\text{\tiny$\|\\!\cdot\\!\|$}}(P,Q)$ for $P$ and $Q$ on
$\mathbb{R}^{p}$ with finite $\mathbb{E}_{P}\|Z\|$ and $\mathbb{E}_{Q}\|Z\|$
is another instance of $d_{{\mathsf{A}},\ell}(P,Q)$, with
${\mathcal{L}}_{{\mathsf{A}},\ell}$ being the set of 1-Lipschitz functions
$f:\mathbb{R}^{p}\rightarrow\mathbb{R}$ w.r.t. the Euclidean distance. With
the definition of $d_{{\mathsf{A}},\ell}(P,Q)$ in (78) and Lemma 1, it is
straightforward to show the following bound on entropy difference.

######  Theorem 7.

For distributions $P$ and $Q$ on ${\mathsf{Z}}$,

$\displaystyle|H_{{\mathsf{A}},\ell}(P)-H_{{\mathsf{A}},\ell}(Q)|$
$\displaystyle\leq d_{{\mathsf{A}},\ell}(P,Q).$ (81)

We will find applications of this result in Section 3.4, where we study the
excess risk of the ERM algorithm in frequentist statistical learning.

###  2.7 Comparison with existing bounds

To date there has been no general results for the continuity of generalized
entropy. Existing entropy difference bounds in the literature are mainly for
the Shannon entropy and the differential entropy. We make comparisons between
the results presented in this work and some of the existing bounds.

For Shannon entropy, the following well-known result provides an upper bound
on the entropy difference in terms of total variation distance [6, Lemma
2.7], [7, Theorem 17.3.3].

######  Theorem 8.

For $P$ and $Q$ on a finite space ${\mathsf{Z}}$ such that $d_{\rm
TV}(P,Q)\leq{1}/{4}$,

$\displaystyle|H_{\log}(P)-H_{\log}(Q)|\leq 2d_{\rm
TV}(P,Q)\log\frac{|{\mathsf{Z}}|}{2d_{\rm TV}(P,Q)}.$ (82)

Compared with the upper bound (14) in Corollary 1 and the upper bounds (59)
and (60) in Corollary 7, we see that an advantage of the new upper bounds is
that they do not require the distance between $P$ and $Q$ to be small to hold.
While $\eqref{eq:log_abs_TV}$ requires the entries of the distributions to be
bounded away from zero for the upper bound to be finite, (59) and (60) only
require the varentropy of $Q$ and the cross varentropy of $P$ under $Q$ to be
finite. Moreover, the upper bound in Corollary 1 is tighter in $d_{\rm
TV}(P,Q)$ when it is small. For example, if $d_{\rm TV}(Q_{n},Q)$ is
$O(\frac{1}{n})$, then the upper bound in (82) scales as $O(\frac{\log
n}{n})$, while the upper bound in Corollary 1 scales as $O(\frac{1}{n})$.

Proved via an optimal coupling argument, another Shannon entropy difference
bound appears in [8] and states the following.

######  Theorem 9.

For distributions $P$ and $Q$ on a finite ${\mathsf{Z}}$,

$\displaystyle|H_{\log}(P)-H_{\log}(Q)|\leq d_{\rm
TV}(P,Q)\log(|{\mathsf{Z}}|-1)+h_{2}(d_{\rm TV}(P,Q))$ (83)

where $h_{2}$ is the binary entropy function.

This bound has been generalized and improved in [9] and [10]. While tighter
than the bound in Theorem 8, it still scales as $O(-d_{\rm TV}(P,Q)\log{d_{\rm
TV}(P,Q)})$ when $d_{\rm TV}(P,Q)$ is small, hence not as tight as the bound
in Corollary 1 when $d_{\rm TV}(P,Q)$ approaches zero. As an example, for two
Bernoulli distributions with biases $p$ and $q$, the white region in Fig. 1
indicates the collection of $(p,q)$ such that the bound in Corollary 1 is
tighter than the bound in Theorem 9.

Figure 1: Comparison of bounds in (14) and (83) for ${\rm Bernoulli}(p)$ and
${\rm Bernoulli}(q)$: the bound in (14) is tighter in the white region of
$(p,q)$.

For differential entropy, the entropy difference can be upper-bounded in terms
of the Wasserstein distance, as stated in the following result [11].

######  Theorem 10.

Let ${\mathsf{Z}}=\mathbb{R}^{p}$. If $Q$ has a $(c_{1},c_{2})$-regular
density, meaning that

$\displaystyle\|\nabla\log Q(z)\|\leq c_{1}\|z\|+c_{2},\quad\forall
z\in\mathbb{R}^{p}$ (84)

then

$\displaystyle
h(P)-h(Q)\leq\Big{(}\frac{c_{1}}{2}\sqrt{\mathbb{E}_{P}[\|Z\|^{2}]}+\frac{c_{1}}{2}\sqrt{\mathbb{E}_{Q}[\|Z\|^{2}]}+c_{2}\Big{)}W_{\|\cdot\|,2}(P,Q),$
(85)

where $W_{\|\cdot\|,2}(P,Q)$ is the Wasserstein distance w.r.t. the Euclidean
distance of order $2$.

Compared with the bound in (59), we see that (59) only requires the varentropy
of $Q$ to be finite, without other regularity conditions on $Q$. Moreover, the
upper bound in (59) depends on $P$ only through $\chi^{2}(P,Q)$, meaning that
for a fixed $Q$, the upper bound is monotonically decreasing as $P$ gets
closer to $Q$, which can be used to prove the upper semicontinuity of the
entropy.

For the quadratic loss, the following result given by Wu [18] upper-bounds the
variance difference in terms of the Wasserstein distance. It can be proved by
writing $\mathbb{E}_{P}[Z^{2}]$ and $\mathbb{E}_{Q}[Z^{2}]$ as
$W_{\|\cdot\|,2}^{2}(P,\delta_{0})$ and $W_{\|\cdot\|,2}^{2}(Q,\delta_{0})$,
and using the triangle inequality satisfied by the Wasserstein distance.

######  Theorem 11.

For $P$ and $Q$ on $\mathbb{R}$ with finite $\mathbb{E}_{P}[Z^{2}]$ and
$\mathbb{E}_{Q}[Z^{2}]$,

$\displaystyle{\rm Var}_{P}[Z]-{\rm Var}_{Q}[Z]\leq
2\Big{(}\sqrt{\mathbb{E}_{P}[Z^{2}]}+\sqrt{\mathbb{E}_{Q}[Z^{2}]}\Big{)}W_{\|\cdot\|,2}(P,Q).$
(86)

Compared with (61), the above upper bound only requires $P$ and $Q$ to have
finite second moments, while (61) requires $Q$ to have a finite fourth moment.
On the other hand, the upper bound in (61) depends on $P$ only through
$\chi^{2}(P,Q)$, hence monotonically decreasing as $P$ gets closer to $Q$,
which is sufficient to prove the upper semicontinuity.

###  2.8 An information-theoretic application: mutual information upper bound

As an application of the entropy difference bounds derived in the previous
subsections, we prove new upper bounds for mutual information by applying
Corollary 1 and Corollary 5 to the log loss.

######  Corollary 11.

For jointly distributed random variables $X$ and $Z$ that can be either
discrete or continuous, let

$\displaystyle\gamma(x)=\log\frac{\sup_{z\in{\mathsf{Z}}}P_{Z|X=x}(z)}{\inf_{z\in{\mathsf{Z}}}P_{Z|X=x}(z)}$
(87)

be the range of variation of $\log P_{Z|X=x}(\cdot)$. Then from Corollary 5,
we have

$\displaystyle
I(X;Z)\leq\sqrt{\frac{1}{2}\mathbb{E}\big{[}\gamma^{2}(X)\big{]}L(X;Z)}\bigwedge\frac{1}{2}\mathbb{E}\big{[}\gamma^{2}(X)\big{]}$
(88)

where $L(X;Z)=D(P_{X}\otimes P_{Z}\|P_{X,Z})$ is the Lautum information
between $X$ and $Z$ [19]. Moreover, from Corollary 1, we have

$\displaystyle
I(X;Z)\leq\Big{(}\sup\nolimits_{x\in{\mathsf{X}}}\gamma(x)\Big{)}\int_{{\mathsf{X}}}d_{\rm
TV}(P_{Z|X=x},P_{Z})P_{X}({\rm d}x),$ (89)

where $\int_{{\mathsf{X}}}d_{\rm TV}(P_{Z|X=x},P_{Z})P_{X}({\rm d}x)$ may be
regarded as a total variation information.

###### Proof.

From the definition of mutual information,

$\displaystyle I(X;Z)$ $\displaystyle=H_{\log}(Z)-H_{\log}(Z|X)$ (90)
$\displaystyle=\int_{{\mathsf{X}}}P_{X}({\rm
d}x)(H_{\log}(P_{Z})-H_{\log}(P_{Z|X=x})).$ (91)

If for any $x$, $\min_{z\in{\mathsf{Z}}}P_{Z|X=x}(z)>0$, then by Corollary 5,

$\displaystyle H_{\log}(P_{Z})-H_{\log}(P_{Z|X=x})$
$\displaystyle\leq\gamma(x)\sqrt{\frac{1}{2}\big{(}D(P_{Z}\|P_{Z|X=x})\wedge
D(P_{Z|X=x}\|P_{Z})\big{)}}.$ (92)

Taking expectations on both sides over $X$, and using Cauchy-Schwarz
inequality, we get

$\displaystyle
I(X;Z)\leq\sqrt{\frac{1}{2}\mathbb{E}\big{[}\gamma^{2}(X)\big{]}L(X;Z)},$ (93)

and

$\displaystyle
I(X;Z)\leq\sqrt{\frac{1}{2}\mathbb{E}\big{[}\gamma^{2}(X)\big{]}I(X;Z)}.$ (94)

The last inequality implies that

$\displaystyle I(X;Z)\leq\frac{1}{2}\mathbb{E}\big{[}\gamma^{2}(X)\big{]}.$
(95)

Finally, (89) follows from (91) and Corollary 1. ∎

##  3 Application to frequentist learning

Having studied the continuity property of the generalized entropy as a
functional of the underlying distribution, we now apply the results obtained
in Section 2 to the excess risk analysis of learning methods, the central
problem of statistical learning theory.

###  3.1 Excess risk of ERM algorithm

In the frequentist formulation of the statistical learning problem, there is a
sample space ${\mathsf{Z}}$, a fixed but unknown distribution $P$ on
${\mathsf{Z}}$, and a hypothesis space ${\mathsf{A}}$. A loss function
$\ell:{\mathsf{Z}}\times{\mathsf{A}}\rightarrow\mathbb{R}$ is chosen to
evaluate the hypotheses in ${\mathsf{A}}$. For any hypothesis
$a\in{\mathsf{A}}$, its population risk is $\mathbb{E}_{P}[\ell(Z,a)]$.
$H_{{\mathsf{A}},\ell}(P)$ is the _minimum population risk_ that would be
achieved among $a\in{\mathsf{A}}$ if $P$ were known. Neither
$\mathbb{E}_{P}[\ell(Z,a)]$ nor $H_{{\mathsf{A}},\ell}(P)$ is computable
however, due to the lack of knowledge of $P$. What is available instead is a
training dataset $Z^{n}\triangleq(Z_{1},\ldots,Z_{n})$ of size $n$ drawn
i.i.d. from $P$, with empirical distribution ${\widehat{P}}_{n}$. As a natural
choice, the empirical risk minimization (ERM) algorithm returns a hypothesis
$a_{{\widehat{P}}_{n}}$ that minimizes the empirical risk
$\mathbb{E}_{{\widehat{P}}_{n}}[\ell(Z,a)]$ among $a\in{\mathsf{A}}$, and the
_minimum empirical risk_ is equal to
$H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})$. Since ${\widehat{P}}_{n}$ depends
on $Z^{n}$, $H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})$ is a random variable.
The entropy difference
$|H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})-H_{{\mathsf{A}},\ell}(P)|$ tells us
how well the uncomputable minimum population risk can be approximated by the
minimum empirical risk that is computable in principle. The results in Section
2 enable us to upper-bound
$|H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})-H_{{\mathsf{A}},\ell}(P)|$ so as to
evaluate the quality of this approximation.

More importantly, the upper-bounding techniques developed in Section 2 provide
us with a means to analyze the _excess risk_ of the ERM algorithm, defined as
the gap between the population risk of the algorithm-returned hypothesis
$a_{{\widehat{P}}_{n}}$ and the minimum population risk,

$\displaystyle R_{\rm
excess}\triangleq\mathbb{E}_{P}\big{[}\ell(Z,a_{{\widehat{P}}_{n}})|Z^{n}\big{]}-H_{{\mathsf{A}},\ell}(P),$
(96)

where $Z$ is a fresh sample from $P$ independent of $Z^{n}$, so that
$P_{Z|Z^{n}}\equiv P$. Note that $R_{\rm excess}$ is a random variable, since
$\mathbb{E}_{P}\big{[}\ell(Z,a_{{\widehat{P}}_{n}})|Z^{n}\big{]}$ depends on
$Z^{n}$ through $a_{{\widehat{P}}_{n}}$. Writing $R_{\rm excess}$ as

$\displaystyle R_{\rm excess}$
$\displaystyle=\big{(}\mathbb{E}_{P}\big{[}\ell(Z,a_{{\widehat{P}}_{n}})|Z^{n}\big{]}-H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})\big{)}+\big{(}H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})-H_{{\mathsf{A}},\ell}(P)\big{)},$
(97)

and using the fact that all the entropy difference bounds in Section 2 are
based on Lemma 1, and the fact that every upper bound for
$H_{{\mathsf{A}},\ell}(P)-H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})$ obtained
based on Lemma 1 also upper-bounds
$\mathbb{E}_{P}\big{[}\ell(Z,a_{{\widehat{P}}_{n}})|Z^{n}\big{]}-H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})$,
we deduce the following result.

######  Lemma 3.

For any almost-sure upper bound $B$ for
$|H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})-H_{{\mathsf{A}},\ell}(P)|$ obtained
based on Lemma 1, in particular based on the results in Section 2, almost
surely we have

$\displaystyle R_{\rm excess}\leq 2B.$ (98)

We give three examples for the application of Lemma 3, using different upper
bounds for the entropy difference derived in Section 2.

###  3.2 Finite sample space

When the sample space ${\mathsf{Z}}$ has a finite number of elements, we can
make use of the entropy difference upper bounds in terms of total variation
distance (Theorem 1) and KL divergence (Corollary 5). The resulting upper
bounds for the excess risk hold virtually for _any_ hypothesis space
${\mathsf{A}}$. For simplicity, we consider the case where the loss function
takes values in $[0,1]$.

######  Theorem 12.

If ${\mathsf{Z}}$ is finite and $\ell(z,a)\in[0,1]$ for all
$(z,a)\in{\mathsf{Z}}\times{\mathsf{A}}$, then for any ${\mathsf{A}}$,

$\displaystyle\mathbb{E}[R_{\rm excess}]\leq\sqrt{\frac{|{\mathsf{Z}}|}{n}};$
(99)

and for any $\varepsilon>0$,

$\displaystyle{\mathbb{P}}[R_{\rm
excess}>\varepsilon]\leq\exp\Big{\\{}-n\Big{(}\frac{\varepsilon^{2}}{2}-\frac{|{\mathsf{Z}}|\log(n+1)}{n}\Big{)}\Big{\\}}.$
(100)

###### Proof.

The upper bound in (99) is a consequence of Lemma 3, Theorem 1, and the fact
that $\mathbb{E}[2d_{\rm
TV}({\widehat{P}}_{n},P)]\leq\sqrt{{|{\mathsf{Z}}|}/{n}}$ [20, Lemma 5]. The
upper bound in (100) is a consequence of Lemma 3, Corollary 5, and the fact
that
${\mathbb{P}}[D({\widehat{P}}_{n}\|P)>\varepsilon]\leq\exp\\{-n(\varepsilon-\frac{|{\mathsf{Z}}|\log(n+1)}{n})\\}$
[7, Theorem 11.2.1]. ∎

Remark. The upper bounds in Theorem 12 can be extended to the case where
${\mathsf{Z}}$ is countably infinite, using the results in [21, Lemma 8 and
Theorem 3]. In addition, via Pinsker’s inequality, the upper bound in (100)
can be used to bound ${\mathbb{P}}[d_{\rm
TV}({\widehat{P}}_{n},P)>\varepsilon]$, which complements the results in [21,
Theorem 3] and [22, Lemma 3] on the convergence of empirical distribution in
the total variation distance.

To evaluate the upper bounds in Theorem 12, consider the problem of binary
classification, where ${\mathsf{Z}}={\mathsf{X}}\times{\mathsf{Y}}$ with
${\mathsf{Y}}=\\{0,1\\}$. Let ${\mathsf{A}}$ be the space of _all mappings_
from ${\mathsf{X}}$ to ${\mathsf{Y}}$, and $\ell(z,a)=\mathbf{1}\\{y\neq
a(x)\\}$. From (99), we get an upper bound for the expected excess risk of the
ERM algorithm,

$\displaystyle\mathbb{E}[R_{\rm excess}]\leq\sqrt{\frac{2|{\mathsf{X}}|}{n}}.$
(101)

This bound is even better in prefactor than the bound $\mathbb{E}[R_{\rm
excess}]\leq 8\sqrt{\frac{|{\mathsf{X}}|\log 2}{n}}$ given by the classic
Rademacher complexity analysis, which is a consequence of the fact that the
cardinality of the hypothesis class ${\mathsf{A}}$ is $2^{|{\mathsf{X}}|}$
when ${\mathsf{X}}$ is finite [23].

###  3.3 Lipschitz-continuous loss function

When the loss function is Lipschitz-continuous in $z$ for all $a$, where $z$
can be continuous-valued, we can use the bound in Theorem 5 in terms of the
Wasserstein distance to control the excess risk.

######  Theorem 13.

Let ${\mathsf{Z}}={\mathsf{X}}\times{\mathsf{Y}}$ where ${\mathsf{Y}}=[-b,b]$
and ${\mathsf{X}}\subset\mathbb{R}^{p}$ with $p>1$. Suppose that
$\mathbb{E}[\|X\|^{2}]$ is finite under the unknown distribution. Consider an
action space ${\mathsf{A}}\subset\mathbb{R}^{k}$ with an arbitrary $k$, and a
function $f:{\mathsf{X}}\times{\mathsf{A}}\rightarrow[-b,b]$ such that
$f(\cdot,a)$ is $\rho_{f}$-Lipschitz in $x$ w.r.t. the Euclidean distance for
all $a\in{\mathsf{A}}$. Then for the loss function $\ell_{1}(z,a)=|y-f(x,a)|$,

$\displaystyle\mathbb{E}[R_{\rm excess}]\leq c(\rho_{f}\vee
1){\mathbb{E}\|Z\|}n^{-1/(p+1)};$ (102)

while for the loss function $\ell_{2}(z,a)=(y-f(x,a))^{2}$,

$\displaystyle\mathbb{E}[R_{\rm excess}]\leq 4cb(\rho_{f}\vee
1){\mathbb{E}\|Z\|}n^{-1/(p+1)},$ (103)

where $c$ is an absolute constant.

###### Proof.

We first show that the Lipschitz continuity of $f(\cdot,a)$ in $x$ can be
translated to the Lipschitz continuity of $|y-f(x,a)|$ in $z=(x,y)$. For any
$a\in{\mathsf{A}}$, and any $z,z^{\prime}\in{\mathsf{Z}}$,

$\displaystyle\big{|}|y-f(x,a)|-|y^{\prime}-f(x^{\prime},a)|\big{|}$
$\displaystyle\leq\big{|}y-f(x,a)-y^{\prime}+f(x^{\prime},a)\big{|}$ (104)
$\displaystyle\leq|f(x,a)-f(x^{\prime},a)|+|y-y^{\prime}|$ (105)
$\displaystyle\leq\rho_{f}\|x-x^{\prime}\|+|y-y^{\prime}|$ (106)
$\displaystyle\leq\sqrt{2}(\rho_{f}\vee 1)\|z-z^{\prime}\|,$ (107)

where in (107) we used the fact that $u+v\leq\sqrt{2u^{2}+2v^{2}}$ for
$u,v\in\mathbb{R}$. It implies that $\ell_{1}(z,a)=|y-f(x,a)|$ is
$\sqrt{2}(\rho_{f}\vee 1)$-Lipschitz in $z=(x,y)$ for all $a\in{\mathsf{A}}$.
Since $|y-f(x,a)|\in[0,2b]$, it further implies that
$\ell_{2}(z,a)=(y-f(x,a))^{2}$ is $4\sqrt{2}b(\rho_{f}\vee 1)$-Lipschitz in
$z$ for all $a\in{\mathsf{A}}$. It follows from Lemma 3 and Theorem 5 that for
$\ell_{1}(z,a)=|y-f(x,a)|$,

$\displaystyle R_{\rm excess}\leq 2\sqrt{2}(\rho_{f}\vee
1)W_{\text{\tiny$\|\\!\cdot\\!\|$}}({\widehat{P}}_{n},P);$ (108)

while for $\ell_{2}(z,a)=(y-f(x,a))^{2}$,

$\displaystyle R_{\rm excess}\leq 8\sqrt{2}b(\rho_{f}\vee
1)W_{\text{\tiny$\|\\!\cdot\\!\|$}}({\widehat{P}}_{n},P).$ (109)

The proof is completed with a result on the Wasserstein convergence of the
empirical distribution [24, Theorem 3.1][25, Proposition 10], which states
that for a distribution $P$ on ${\mathsf{Z}}\subset\mathbb{R}^{p+1}$ with
$p>1$,

$\displaystyle\mathbb{E}[W_{\text{\tiny$\|\\!\cdot\\!\|$}}({\widehat{P}}_{n},P)]\leq
c^{\prime}\mathbb{E}[\|Z\|]n^{-1/{(p+1)}},$ (110)

where $c^{\prime}$ is some absolute constant. ∎

We see that the upper bound in Theorem 13 does not depend on the dimension of
${\mathsf{A}}$, and converges to zero as $n\rightarrow\infty$ for any fixed
dimension $p$ of ${\mathsf{X}}$; however, the rate of convergence suffers from
the curse of dimensionality in $p$. An open question is whether there is a way
to leverage the results in Section 2.4 to bounding the excess risk in terms of
statistical distances between the distributions of
$\ell(Z,a_{{\widehat{p}}_{n}})$ when $Z$ is drawn from $P$ and from
${\widehat{P}}_{n}$. It may lead to tighter bounds when $f$ in Theorem 13 has
additional regularities beyond being Lipschitz in $x$. This question is
partially addressed by looking into a statistical distance that compares the
expected loss under distributions $P$ and ${\widehat{P}}_{n}$, but at a worst
hypothesis in ${\mathsf{A}}$, as discussed in the next subsection.

###  3.4 Learnability, typicality, and entropy continuity

The results in the two preceding subsections can be unified by considering the
entropy difference bound via the $({\mathsf{A}},\ell)$-semidistance defined in
(78). We have

$\displaystyle
d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)=\sup_{a\in{\mathsf{A}}}\big{|}\mathbb{E}_{{\widehat{P}}_{n}}[\ell(Z,a)]-\mathbb{E}_{P}[\ell(Z,a)]\big{|},$
(111)

which is essentially the _uniform deviation_ of the empirical risk from the
population risk w.r.t. $({\mathsf{A}},\ell)$. It follows from Lemma 3 and
Theorem 7 that

$\displaystyle R_{\rm excess}$ $\displaystyle\leq
2d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)\quad{\rm a.s.}$ (112)

This result recovers the classic upper bound on the excess risk of the ERM
algorithm in terms of the uniform deviation [26].

The conditions on the convergence of the uniform deviation to zero,

$\displaystyle
d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)\xrightarrow{\text{a.s.}}0\quad\text{as
$n\rightarrow\infty$}$ (113)

have been well-studied in the mathematical statistics and statistical learning
theory literature as a form of uniform law of large numbers [26, 23]. Recall
that $d_{{\mathsf{A}},\ell}$ can also be defined w.r.t. the function class
${\mathcal{L}}_{{\mathsf{A}},\ell}=\\{\ell(\cdot,a),a\in{\mathsf{A}}\\}$
induced by $({\mathsf{A}},\ell)$ as shown in (80), namely

$\displaystyle
d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)=\sup_{f\in{\mathcal{L}}_{{\mathsf{A}},\ell}}\big{|}\mathbb{E}_{{\widehat{P}}_{n}}[f(Z)]-\mathbb{E}_{P}[f(Z)]\big{|}.$
(114)

The function class ${\mathcal{L}}_{{\mathsf{A}},\ell}$ is called a _Glivenko-
Cantelli (GC) class_ if (113) holds for every distributon $P$ on
${\mathsf{Z}}$, c.f. [27]. Further, the hypothesis space ${\mathsf{A}}$ is
said to be _learnable_ w.r.t. $\ell$ if ${\mathcal{L}}_{{\mathsf{A}},\ell}$ is
a GC class. Theorem 12 and Theorem 13 each involves a special instance of the
GC class that has virtually no restriction on ${\mathsf{A}}$: one with all
measurable functions ${\mathsf{Z}}\rightarrow[0,1]$ and a _finite_
${\mathsf{Z}}$, such that

$d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)=d_{\rm
TV}({\widehat{P}}_{n},P)\xrightarrow{\text{a.s.}}0;$

and the other with all bounded Lipschitz-continuous functions
$\mathbb{R}^{p+1}\rightarrow[-b,b]$ with a common Lipschitz constant, such
that

$d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)\propto
W_{\text{\tiny$\|\\!\cdot\\!\|$}}({\widehat{P}}_{n},P)\xrightarrow{\text{a.s.}}0.$

In general, a GC class and the rate of convergence in (113) rely on the
properties of both ${\mathsf{A}}$ and $\ell$. A well-known example of such a
GC class is the class of indicator functions of a special collection of
subsets of ${\mathsf{Z}}$ which has a finite Vapnik-Chervonenkis (VC)
dimension [26]. For this class, with $\ell$ being the zero-one loss, and
${\mathsf{A}}$ being the collection of subsets of ${\mathsf{Z}}$ with a finite
VC dimension $V({\mathsf{A}})$,
$\mathbb{E}[d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)]$ explicitly depends on
${\mathsf{A}}$ through

$\displaystyle\mathbb{E}[d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)]\sim
O\big{(}\sqrt{{V({\mathsf{A}})}/{n}}\big{)}.$ (115)

Conceptually, given ${\mathsf{A}}$ and $\ell$, we can also define the
$({\mathsf{A}},\ell)$-_typical set_ of elements in ${\mathsf{Z}}^{n}$
according to $d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)$ as in [27,
Definition 4],

$\displaystyle{\mathcal{T}}_{{\mathsf{A}},\ell}(P,n,\varepsilon)\triangleq\big{\\{}z^{n}\in{\mathsf{Z}}^{n}:d_{{\mathsf{A}},\ell}({\widehat{P}}_{n},P)\leq\varepsilon\big{\\}},\quad\varepsilon>0.$
(116)

In words, a dataset $z^{n}$ is $({\mathsf{A}},\ell)$-typical if the empirical
risks on it, uniformly for all hypotheses in ${\mathsf{A}}$, are close to the
corresponding population risks. As a consequence of Theorem 7 in Section 2.6,
the minimum empirical risk on this typical set can closely approximate the
minimum population risk, as
$|H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})-H_{{\mathsf{A}},\ell}(P)|\leq\varepsilon$;
moreover, from (112), the ERM algorithm with an input drawn from this typical
set will output a near-optimal hypothesis, as $R_{\rm excess}\leq
2\varepsilon$. For example, when ${\mathsf{A}}$ and $\ell$ are such that
$\mathcal{L}_{{\mathsf{A}},\ell}$ is the set of measurable functions
${\mathsf{Z}}\rightarrow[0,1]$, the $({\mathsf{A}},\ell)$-typical set defined
in (116) reduces to the one characterized by the total variation distance
between ${\widehat{P}}_{n}$ and $P$,

$\displaystyle{\mathcal{T}}_{\rm
TV}(P,n,\varepsilon)=\big{\\{}z^{n}\in{\mathsf{Z}}^{n}:d_{\rm
TV}({\widehat{P}}_{n},P)\leq\varepsilon\big{\\}}$ (117)

which is proposed and used in [28]. When ${\mathsf{Z}}$ is finite, the above
typical set is almost equivalent to the notion of _strong typicality_ commonly
used in information theory [6] [7, (10.106)] as shown in [28], and will
include almost all elements in ${\mathsf{Z}}^{n}$ as $n\rightarrow\infty$.
Theorem 12 can thus be understood from the viewpoint of strong typitcality as
well, in that eventually almost every sequence has an empirical distribution
close to $P$. In general, the definition of
${\mathcal{T}}_{{\mathsf{A}},\ell}(P,n,\varepsilon)$ applies to uncountably
infinite ${\mathsf{Z}}$ as well. We then have the following connection among
typicality, entropy continuity, and learnability: if
${\mathcal{L}}_{{\mathsf{A}},\ell}$ is a GC class, then for any
$\varepsilon>0$, as $n\rightarrow\infty$,

$\displaystyle{\mathbb{P}}\big{[}{\mathcal{T}}_{{\mathsf{A}},\ell}(P,n,\varepsilon)\big{]}\rightarrow
1$ (118)

by the definition in (116), which implies that

$\displaystyle{\mathbb{P}}\big{[}|H_{{\mathsf{A}},\ell}({\widehat{P}}_{n})-H_{{\mathsf{A}},\ell}(P)|\leq\varepsilon\big{]}\rightarrow
1$ (119)

by Theorem 7, which further implies that

$\displaystyle{\mathbb{P}}\big{[}R_{\rm excess}\leq
2\varepsilon\big{]}\rightarrow 1$ (120)

by Lemma 3. The rate of convergence will depend on ${\mathsf{A}}$ and $\ell$
in general.

##  4 Application to Bayesian learning

Another application of the results in Section 2 to statistical learning is the
analysis of the minimum excess risk in Bayesian learning. This problem is
formulated and studied in detail in [4] using several different approaches.
Here we give an overview of the analysis based on the entropy continuity
presented in [4, Section 4].

###  4.1 Minimum excess risk in Bayesian learning

As an alternative to the frequentist formulation of the learning problem,
_Bayesian learning_ under a parametric generative model assumes that the data
$Z^{n}=((X_{1},Y_{1}),\ldots,(X_{n},Y_{n}))$, with
$Z_{i}\triangleq(X_{i},Y_{i})$, is generated from a member of a parametrized
family of probabilistic models $\\{P_{Z|w},w\in{\mathsf{W}}\\}$, where the
model parameter $W$ is an unknown random vector in ${\mathsf{W}}$ with a prior
distribution $P_{W}$. With a fresh sample $Z=(X,Y)$, $X$ is observed, and the
goal is to predict $Y$ based on $X$ and $Z^{n}$. Formally, the joint
distribution of the model parameter, the dataset and the fresh sample is

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

where $P_{Z_{i}|W}=P_{Z|W}$ for each $i$. Given an action space ${\mathsf{A}}$
and a loss function
$\ell:{\mathsf{Y}}\times{\mathsf{A}}\rightarrow\mathbb{R}$, the goal of
Bayesian learning can be phrased as seeking a decision rule
$\psi:{\mathsf{X}}\times{\mathsf{Z}}^{n}\rightarrow{\mathsf{A}}$ to make the
expected loss $\mathbb{E}[\ell(Y,\psi(X,Z^{n}))]$ small. In contrast to the
frequentist learning, since the joint distribution $P_{Z^{n},Z}$ is known, the
search space here is the collection of all decision rules such that
$\mathbb{E}[\ell(Y,\psi(X,Z^{n}))]$ is well-defined. The minimum achievable
expected loss is called the _Bayes risk_ in Bayesian learning:

$\displaystyle
H_{\ell}(Y|X,Z^{n})=\inf_{\psi:{\mathsf{X}}\times{\mathsf{Z}}^{n}\rightarrow{\mathsf{A}}}\mathbb{E}[\ell(Y,\psi(X,Z^{n}))],$
(122)

which is essentially the generalized conditional entropy of $Y$ given
$(X,Z^{n})$ in view of the definition in (2). As shown by a data processing
inequality for the Bayes risk [4, Lemma 1], $H_{\ell}(Y|X,Z^{n})$ decreases as
the data size $n$ increases. The fundamental limit of the Bayes risk can be
defined as the minimum expected loss when the model parameter $W$ is known:

$\displaystyle
H_{\ell}(Y|X,W)=\inf_{\Psi:{\mathsf{X}}\times{\mathsf{W}}\rightarrow{\mathsf{A}}}\mathbb{E}[\ell(Y,\Psi(X,W))].$
(123)

The _minimum excess risk_ (MER) in Bayesian learning is defined as the gap
between the Bayes risk and its fundamental limit, which is the minimum
achievable excess risk among all decision rules:

$\displaystyle{\rm MER}_{\ell}\triangleq H_{\ell}(Y|X,Z^{n})-H_{\ell}(Y|X,W).$
(124)

The MER is an algorithm-independent quantity. Its value and rate of
convergence quantify the difficulty of the _learning_ problem, which is due to
the lack of knowledge of $W$. It can serve as a formal definition of the
minimum epistemic uncertainty, with $H_{\ell}(Y|X,W)$ serving as the
definition of the _aleatoric uncertainty_ , which haven been only empirically
studied so far [29, 30].

###  4.2 Method of analysis based on entropy continuity

In what follows, we outline the idea of how the upper bounds on entropy
difference derived in Section 2 can be used to upper-bound the MER. We
consider the predictive modeling framework, a.k.a. probabilistic
discriminative model, where $P_{Z|W}=P_{X|W}\otimes K_{Y|X,W}$, with the
probability transition kernel $K_{Y|X,W}$ directly describing the predictive
model of the quantity of interest given the observation. First, we have the
following lemma that bounds the deviation of the posterior predictive
distribution $P_{Y|X,Z^{n}}$ from the true predictive model $K_{Y|X,W}$, which
is a simple consequence of the convexity of the statistical distance under
consideration.

######  Lemma 4.

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 $f$-divergence or Wasserstein distance $D$,

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

where the expectations are taken over the conditioning variables according to
the joint distribution of $(W,W^{\prime},X,Z^{n})$.

The main utility of Lemma 4 is that, whenever
$D(K_{Y|x,w^{\prime}},K_{Y|x,w})$ can be upper-bounded in terms of
$\|w^{\prime}-w\|^{2}$, we can invoke the fact that

$\displaystyle\mathbb{E}[\|W^{\prime}-W\|^{2}]=2H_{2}(W|X,Z^{n})$ (126)

as a consequence of the orthogonality principle in the minimum mean square
error (MMSE) estimation, so that the expected deviation
$\mathbb{E}[D(P_{Y|X,Z^{n}},K_{Y|X,W})]$ can be bounded in terms of
$H_{2}(W|X,Z^{n})$, the MMSE of estimating $W$ from $(X,Z^{n})$. Lemma 4 and
(126) give us a route to bounding the MER in terms of $H_{2}(W|X,Z^{n})$,
provided we can bound the entropy difference in (124) in terms of
$D(P_{Y|X,Z^{n}},K_{Y|X,W})$. The latter problem is precisely the subject of
Section 2.

###  4.3 Example: regression with quadratic loss

We give an example where the results in Section 2 can be applied to the
analysis of both linear and nonlinear regressions with quadratic loss.

######  Lemma 5.

For regression problems with ${\mathsf{Y}}={\mathsf{A}}=\mathbb{R}$, if
$K_{Y|X=x,W=w}$ is Gaussian with variance $\sigma^{2}$ for all $(x,w)$, then
under the quadratic loss

$\displaystyle{\rm MER}_{2}$ $\displaystyle\leq
2\sigma^{2}\Big{(}\sqrt{\mathbb{E}[D(K_{Y|X,W^{\prime}}\|K_{Y|X,W})]}+\mathbb{E}[D(K_{Y|X,W^{\prime}}\|K_{Y|X,W})]\Big{)},$
(127)

where $W^{\prime}$ is conditionally i.i.d. of $W$ given $(X,Z^{n})$, and the
expectations are taken over the conditioning variables.

###### Proof.

We have

$\displaystyle{\rm MER}_{2}$ $\displaystyle=\int\big{(}{\rm
Var}[Y|x,z^{n}]-{\rm Var}[Y|x,w]\big{)}P({\rm d}w,{\rm d}x,{\rm d}z^{n})$
(128) $\displaystyle\leq
2\sigma^{2}\int\Big{(}\sqrt{D(P_{Y|x,z^{n}}\|K_{Y|x,w})}+D(P_{Y|x,z^{n}}\|K_{Y|x,w})\Big{)}P({\rm
d}w,{\rm d}x,{\rm d}z^{n})$ (129) $\displaystyle\leq
2\sigma^{2}\Big{(}\sqrt{\mathbb{E}[D(K_{Y|X,Z^{n}}\|K_{Y|X,W})]}+\mathbb{E}[D(K_{Y|X,Z^{n}}\|K_{Y|X,W})]\Big{)}$
(130) $\displaystyle\leq
2\sigma^{2}\Big{(}\sqrt{\mathbb{E}[D(K_{Y|X,W^{\prime}}\|K_{Y|X,W})]}+\mathbb{E}[D(K_{Y|X,W^{\prime}}\|K_{Y|X,W})]\Big{)},$
(131)

with (129) from Corollary 4 in Section 2.2; (130) from Jensen’s inequality;
and (131) from Lemma 4. ∎

Now consider a general model of the form $Y=g(X,W)+V,$ where $X$ and $W$ are
independent, ${\mathsf{W}}$ is a convex subset of $\mathbb{R}^{p}$,
$V\sim\mathcal{N}(0,\sigma^{2})$ is independent of $(X,W)$, and the regression
function $g:{\mathsf{X}}\times{\mathsf{W}}\rightarrow\mathbb{R}$ is some
parametric nonlinearity, which may be approximated by a feedforward deep
neural net. We have the following result.

######  Theorem 14.

In the above setting with
$s_{g}^{2}\triangleq\mathbb{E}\big{[}\sup_{w\in{\mathsf{W}}}\|\nabla_{w}g(X,w)\|^{2}\big{]}$,
under the quadratic loss

$\displaystyle{\rm
MER}_{2}\leq\sqrt{4\sigma^{2}s_{g}^{2}H_{2}(W|Z^{n})}+2s_{g}^{2}H_{2}(W|Z^{n}).$
(132)

###### Proof.

For the model described above, the KL divergence between two different models
can be written as
$D(K_{Y|x,w^{\prime}}\|K_{Y|x,w})=(g(x,w^{\prime})-g(x,w))^{2}/2\sigma^{2}.$
We have

$\displaystyle\mathbb{E}[D(K_{Y|X,W^{\prime}}\|K_{Y|X,W})]$
$\displaystyle=\frac{1}{2\sigma^{2}}\mathbb{E}\big{[}(g(X,W^{\prime})-g(X,W))^{2}\big{]}$
(133)
$\displaystyle\leq\frac{s_{g}^{2}}{2\sigma^{2}}\mathbb{E}\big{[}\|W^{\prime}-W\|^{2}\big{]}$
(134) $\displaystyle=\frac{s_{g}^{2}}{\sigma^{2}}H_{2}(W|Z^{n})$ (135)

where (134) is based on the fact that bounded gradient norm implies Lipschitz
continuity of a function on a convex subset of $\mathbb{R}^{p}$, the
definition of $s_{g}$, and the independence between $X$ and $(W,W^{\prime})$;
and the last step follows from (126) and the fact that $X$ is independent of
$(W,Z^{n})$. The result then follows from Lemma 5. ∎

In the example above, we see that the MER upper bound depends on $n$ only
through $H_{2}(W|Z^{n})$, the MMSE of estimating $W$ from $Z^{n}$. For general
nonlinear regression models the closed-form expression for $H_{2}(W|Z^{n})$
may be intractable but can be upper-bounded. For the linear regression model,
where $g(x,w)=w^{\top}\phi(x)$ with some feature map
$\phi:{\mathsf{X}}\rightarrow\mathbb{R}^{p}$ and with
$W\sim\mathcal{N}(0,\Sigma_{W})$, a closed-form expression of ${\rm MER}_{2}$
can be derived, which can be relaxed to an upper bound in terms of
$H_{2}(W|Z^{n})$ as

$\displaystyle{\rm MER}_{2}\leq s_{g}^{2}H_{2}(W|Z^{n})$ (136)

with $s_{g}^{2}=\mathbb{E}[\|\phi(X)\|^{2}]$. Compared with (136), it implies
that when applied to linear regression, the upper bound given by Theorem 14 is
on the same order as (136) when $H_{2}(W|Z^{n})$ is large, but it is not
order-optimal for vanishing $H_{2}(W|Z^{n})$ as $n$ grows.

Nevertheless, the result in Theorem 14 explicitly shows how the model
uncertainty due to the estimation error of the model parameters translates to
the MER under the quadratic loss, which represents the minimum epistemic
uncertainty, and how it then contributes to the minimum overall prediction
uncertainty, which is the sum of the MER and the aleatoric uncertainty
$\sigma^{2}$. It thus provides a theoretical guidance on _uncertainty
quantification_ in Bayesian learning, which is an increasingly important
direction of research with wide range of applications.

##  5 Application to inference and learning with distributional drift

Based on Lemma 1, we have developed a number of approaches to bounding the
difference of the generalized _unconditional_ entropy in Section 2. We also
studied the applications of the results in both frequentist learning and
Bayesian learning in the two preceding sections. The idea behind Lemma 1 can
be extended to bounding the difference of the generalized _conditional_
entropy defined in (2). In this section, we work out this extension to derive
performance bounds for Bayes decision making under a mismatched distribution.
The results can be applied to analyzing the excess risk in learning by first
projecting the empirical distribution to a predefined family of distributions
and then using the projection as a surrogate of the data-generating
distribution for decision making.

###  5.1 Bounds on conditional entropy difference

Consider the Bayes decision making problem under which the generalized
conditional entropy is defined as in (2). Let $P=P_{X}\otimes P_{Y|X}$ and
$Q=Q_{X}\otimes Q_{Y|X}$ be two joint distributions on
${\mathsf{X}}\times{\mathsf{Y}}$, which may be referred as two _domains_ in
the subsequent discussion. Given an action space ${\mathsf{A}}$ and a loss
function $\ell:{\mathsf{Y}}\times{\mathsf{A}}\rightarrow\mathbb{R}$, let
$\psi_{P}:{\mathsf{X}}\rightarrow{\mathsf{A}}$ and
$\psi_{Q}:{\mathsf{X}}\rightarrow{\mathsf{A}}$ be the Bayes decision rules
w.r.t. $({\mathsf{A}},\ell)$ under $P$ and $Q$ respectively, such that
$H_{\ell}(P_{Y|X}|P_{X})=\mathbb{E}_{P}[\ell(Y,\psi_{P}(X))]$ and
$H_{\ell}(Q_{Y|X}|Q_{X})=\mathbb{E}_{Q}[\ell(Y,\psi_{Q}(X))].$ Note that
$\psi_{P}(x)$ and $\psi_{Q}(x)$ are the optimal actions that achieve the
generalized unconditional entropy of $P_{Y|X=x}$ and $Q_{Y|X=x}$ respectively.
Then, in the same spirit of Lemma 1, we have the following result for the
difference between generalized conditional entropy.

######  Lemma 6.

Let $P=P_{X}\otimes P_{Y|X}$ and $Q=Q_{X}\otimes Q_{Y|X}$ be two joint
distributions on ${\mathsf{X}}\times{\mathsf{Y}}$. Then the difference between
the generalized conditional entropy w.r.t. $({\mathsf{A}},\ell)$ under $P$ and
$Q$ satisfy

$\displaystyle H_{\ell}(P_{Y|X}|P_{X})-H_{\ell}(Q_{Y|X}|Q_{X})$
$\displaystyle\leq\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-\mathbb{E}_{Q}[\ell(Y,\psi_{Q}(X))]$
(137)

and

$\displaystyle H_{\ell}(Q_{Y|X}|Q_{X})-H_{\ell}(P_{Y|X}|P_{X})$
$\displaystyle\leq\mathbb{E}_{Q}[\ell(Y,\psi_{P}(X))]-\mathbb{E}_{P}[\ell(Y,\psi_{P}(X))].$
(138)

With Lemma 6, all the results developed in Section 2 on the entropy difference
can be extended to bounds for the conditional entropy difference. For example,
the results in Sections 2.1, 2.2 and 2.3 can be extended by replacing $a_{Q}$
and $a_{P}$ by $\psi_{Q}(X)$ and $\psi_{P}(X)$ respectively, in both the
conditions and the bounds, and by replacing the statistical distances between
$P$ and $Q$ by distances between $P_{X,Y}$ and $Q_{X,Y}$. In view of Theorem 4
in Section 2.4, the statistical distances between $P$ and $Q$ can even be
replaced by distances between $P_{\ell(Y,\psi_{Q}(X))}$ and
$Q_{\ell(Y,\psi_{Q}(X))}$, or between $P_{\ell(Y,\psi_{P}(X))}$ and
$Q_{\ell(Y,\psi_{P}(X))}$. In view of the results in Section 2.5, we can also
bound the conditional entropy difference by the Wasserstein distance between
$P_{X,Y}$ and $Q_{X,Y}$ if $\ell(Y,\psi_{Q}(X))$ or $\ell(Y,\psi_{P}(X))$ is
Lipschitz in $(X,Y)$. Moreover, we can define an
$({\mathsf{A}},\ell)$-semidistance between $P_{X,Y}$ and $Q_{X,Y}$ as

$\displaystyle
d_{{\mathsf{A}},\ell}(P_{X,Y},Q_{X,Y})\triangleq\sup_{\psi:{\mathsf{X}}\,\rightarrow{\mathsf{A}}}\big{|}\mathbb{E}_{P}[\ell(Y,\psi(X))]-\mathbb{E}_{Q}[\ell(Y,\psi(X))]\big{|},$
(139)

and use it to bound the conditional entropy difference, similar to the results
in Section 2.6.

As an illustrative example, suppose the loss function $\ell(y,a)\in[0,1]$ for
all $(y,a)\in{\mathsf{Y}}\times{\mathsf{A}}$. Then

$\displaystyle H_{\ell}(P_{Y|X}|P_{X})-H_{\ell}(Q_{Y|X}|Q_{X})$
$\displaystyle\leq\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(Q_{Y|X}|Q_{X})$
(140) $\displaystyle\leq\sqrt{\frac{1}{2}D(P_{X,Y}\|Q_{X,Y})}$ (141)
$\displaystyle=\sqrt{\frac{1}{2}\big{(}D(P_{X}\|Q_{X})+D(P_{Y|X}\|Q_{Y|X}|P_{X})\big{)}},$
(142)

where (140) is due to Lemma 6; (141) is due to (33); and (142) follows from
the chain rule of KL divergence. Not only serving as an upper bound for the
conditional entropy difference, the result also implies that when both
$D(P_{X}\|Q_{X})$ and $D(P_{Y|X}\|Q_{Y|X}|P_{X})$ are small,
$H_{\ell}(Q_{Y|X}|Q_{X})$ can closely approximate
$\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]$. As mentioned above, other methods
developed in Section 2 can be extended for this purpose as well, and may
provide even tighter performance guarantees.

In the special case where $P=P_{X}\otimes P_{Y|X}$ and $Q=P_{X}\otimes
Q_{Y|X}$ share the same marginal distribution of $X$, the decision rules
$\psi_{P}$ and $\psi_{Q}$ defined above preserve their optimality, and we have
the following alternative bounds due to the representation of the conditional
entropy via the unconditional entropy in (3) and Lemma 1.

######  Lemma 7.

Under $P=P_{X}\otimes P_{Y|X}$ and $Q=P_{X}\otimes Q_{Y|X}$, let
$P_{x}\triangleq P_{Y|X=x}$ and $Q_{x}\triangleq Q_{Y|X=x}$. Then

$\displaystyle H_{\ell}(P_{Y|X}|P_{X})-H_{\ell}(Q_{Y|X}|P_{X})$
$\displaystyle\leq\int_{\mathsf{X}}\big{(}\mathbb{E}_{P_{x}}[\ell(Y,\psi_{Q}(x))]-\mathbb{E}_{Q_{x}}[\ell(Y,\psi_{Q}(x))]\big{)}P_{X}({\rm
d}x)$ (143)

and

$\displaystyle H_{\ell}(Q_{Y|X}|P_{X})-H_{\ell}(P_{Y|X}|P_{X})$
$\displaystyle\leq\int_{\mathsf{X}}\big{(}\mathbb{E}_{Q_{x}}[\ell(Y,\psi_{P}(x))]-\mathbb{E}_{P_{x}}[\ell(Y,\psi_{P}(x))]\big{)}P_{X}({\rm
d}x).$ (144)

With Lemma 7, the results developed in Section 2 on unconditional entropy
difference can be applied to bounding the conditional entropy difference, by
bounding the integrands in (143) and (144).

The bounds for conditional entropy difference obtained in Lemma 6 or Lemma 7
combined with the techniques developed in Section 2 can provide performance
guarantees for decision making with distributional drift: the performance of a
decision rule $\psi_{Q}$ in a new domain $P$, represented by
$\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]$, may be approximated in terms of its
performance in the original domain $Q$ where it is optimally designed,
represented by $H_{\ell}(Q_{Y|X}|Q_{X})$. As illustrated by the preceding
example for $\ell\in[0,1]$, the simple upper bound for (140) given in (142) is
an analogue of the result in [31, Theorem 1] on binary classification with
distributional drift, and is an extension of it to general Bayesian inference
problems.

###  5.2 Excess risk bounds via entropy difference

Besides comparing $\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]$ against
$H_{\ell}(Q_{Y|X}|Q_{X})$, it is also of interest to study the gap between
$\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]$ and $H_{\ell}(P_{Y|X}|P_{X})$, which
amounts to the excess risk incurred by using $\psi_{Q}$ in domain $P$ rather
than using the optimal decision rule $\psi_{P}$. The following result, in the
same spirit of Lemma 3, shows that the excess risk can be upper-bounded in
terms of the previously developed upper bounds for the conditional entropy
difference $|H_{\ell}(Q_{Y|X}|Q_{X})-H_{\ell}(P_{Y|X}|P_{X})|$ or
$|H_{\ell}(Q_{Y|X}|P_{X})-H_{\ell}(P_{Y|X}|P_{X})|$.

######  Theorem 15.

The excess risk of using $\psi_{Q}$, the Bayes decision rule w.r.t.
$({\mathsf{A}},\ell)$ under $Q=Q_{X}\otimes Q_{Y|X}$, in another domain
$P=P_{X}\otimes P_{Y|X}$ satisfies

$\displaystyle\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(P_{Y|X}|P_{X})\leq
2B_{Q},$ (145)

where $B_{Q}$ is any upper bound for
$|H_{\ell}(Q_{Y|X}|Q_{X})-H_{\ell}(P_{Y|X}|P_{X})|$ obtained based on Lemma 6.
Additionally, it also holds that

$\displaystyle\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(P_{Y|X}|P_{X})\leq
2B_{P},$ (146)

where $B_{P}$ is any upper bound for
$|H_{\ell}(Q_{Y|X}|P_{X})-H_{\ell}(P_{Y|X}|P_{X})|$ obtained based on either
Lemma 6 or Lemma 7.

###### Proof.

To show (145), we can write the entropy difference
$\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(P_{Y|X}|P_{X})$ as

$\displaystyle\big{(}\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(Q_{Y|X}|Q_{X})\big{)}+\big{(}H_{\ell}(Q_{Y|X}|Q_{X})-H_{\ell}(P_{Y|X}|P_{X})\big{)}.$
(147)

The claim then follows from the fact that any upper bound for
$H_{\ell}(P_{Y|X}|P_{X})-H_{\ell}(Q_{Y|X}|Q_{X})$ obtained based on Lemma 6
also upper-bounds
$\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(Q_{Y|X}|Q_{X})$.

Next we prove (146). Adopting the same definitions of $P_{x}$ and $Q_{x}$ as
in Lemma 7, we have

$\displaystyle\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(P_{Y|X}|P_{X})$
$\displaystyle=$
$\displaystyle\big{(}\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(Q_{Y|X}|P_{X})\big{)}+\big{(}H_{\ell}(Q_{Y|X}|P_{X})-H_{\ell}(P_{Y|X}|P_{X})\big{)}$
(148) $\displaystyle=$
$\displaystyle\int_{\mathsf{X}}(\mathbb{E}_{P_{x}}[\ell(Y,\psi_{Q}(x))]-\mathbb{E}_{Q_{x}}[\ell(Y,\psi_{Q}(x))])P_{X}({\rm
d}x)+\big{(}H_{\ell}(Q_{Y|X}|P_{X})-H_{\ell}(P_{Y|X}|P_{X})\big{)}$ (149)
$\displaystyle\leq$
$\displaystyle\int_{\mathsf{X}}(\mathbb{E}_{P_{x}}[\ell(Y,\psi_{Q}(x))]-\mathbb{E}_{Q_{x}}[\ell(Y,\psi_{Q}(x))])P_{X}({\rm
d}x)+$
$\displaystyle\int_{\mathsf{X}}(\mathbb{E}_{Q_{x}}[\ell(Y,\psi_{P}(x))]-\mathbb{E}_{P_{x}}[\ell(Y,\psi_{P}(x))])P_{X}({\rm
d}x)$ (150)

where (149) uses the fact that $\psi_{Q}$ remains as a Bayes decision rule
under the joint distribution $P_{X}\otimes Q_{Y|X}$; and the last step is due
to (144) in Lemma 7.

Note that according to (137), any upper bound for
$H_{\ell}(P_{Y|X}|P_{X})-H_{\ell}(Q_{Y|X}|P_{X})$ obtained based on Lemma 6
also upper-bounds
$\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(Q_{Y|X}|P_{X})$. It then follows
from (148) that
$\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(P_{Y|X}|P_{X})\leq 2B$ for any
upper bound $B$ for $|H_{\ell}(P_{Y|X}|P_{X})-H_{\ell}(Q_{Y|X}|P_{X})|$
obtained by Lemma 6.

Moreover, any upper bound for
$H_{\ell}(P_{Y|X}|P_{X})-H_{\ell}(Q_{Y|X}|P_{X})$ or
$H_{\ell}(Q_{Y|X}|P_{X})-H_{\ell}(P_{Y|X}|P_{X})$ obtained based on Lemma 7
also upper-bounds one of the two integral in (150). It follows that
$\mathbb{E}_{P}[\ell(Y,\psi_{Q}(X))]-H_{\ell}(P_{Y|X}|P_{X})\leq 2B$ for any
upper bound $B$ for $|H_{\ell}(P_{Y|X}|P_{X})-H_{\ell}(Q_{Y|X}|P_{X})|$
obtained by Lemma 7. This proves (146). ∎

As an example, we can use Theorem 15 to bound the excess risk in estimating
$Y$ from a noisy observation $X$ when the distribution of $Y$ is wrongly
specified. For instance, when $Y\in\mathbb{R}$ has a distribution $P_{Y}$ and
$X={\alpha}Y+V$ with $V\sim\mathcal{N}(0,1)$ independent of $Y$, if the
distribution of $Y$ is assumed to be $Q_{Y}$, then the mismatched Bayes
estimator w.r.t. the quadratic loss is $\psi_{Q}(x)={\int
ye^{-(x-{\alpha}y)^{2}/2}Q({\rm d}y)}/{\int
e^{-(x-{\alpha}y^{\prime})^{2}/2}Q({\rm d}y^{\prime})}$ instead of the true
Bayes estimator $\psi_{P}(x)=\mathbb{E}_{P}[Y|X=x]$ [32]. The following
corollary bounds the excess risk of using a mismatched Bayes estimator in a
more general setting.

######  Corollary 12.

Suppose $Y\in\mathbb{R}$ has distribution $P_{Y}$, and $X=g(Y,V)$ with some
function $g$ and noise $V$ independent of $Y$. Let $\psi_{Q}$ be the Bayes
estimator w.r.t. the quadratic loss when the distribution of $Y$ is assumed to
be $Q_{Y}$ but $X$ is assumed to have the same form. Then

$\displaystyle\mathbb{E}_{P}[(Y-\psi_{Q}(X))^{2}]-H_{2}(P_{Y|X}|P_{X})\leq$
$\displaystyle\sqrt{\mathbb{E}_{Q}[(Y-\psi_{Q}(X))^{4}]\chi^{2}(P_{Y}\|Q_{Y})}\,+$
$\displaystyle\sqrt{\mathbb{E}_{P}[(Y-\psi_{P}(X))^{4}]\chi^{2}(Q_{Y}\|P_{Y})}.$
(151)

###### Proof.

This result is a slight variation of (145), but we follow the same line of its
proof:

$\displaystyle\mathbb{E}_{P}[(Y-\psi_{Q}(X))^{2}]-H_{2}(P_{Y|X}|P_{X})$
$\displaystyle=$
$\displaystyle\mathbb{E}_{P}[(Y-\psi_{Q}(X))^{2}]-\mathbb{E}_{Q}[(Y-\psi_{Q}(X))^{2}]+\mathbb{E}_{Q}[(Y-\psi_{Q}(X))^{2}]-H_{2}(P_{Y|X}|P_{X})$
(152) $\displaystyle\leq$
$\displaystyle\big{(}\mathbb{E}_{P}[(Y-\psi_{Q}(X))^{2}]-\mathbb{E}_{Q}[(Y-\psi_{Q}(X))^{2}]\big{)}+\big{(}\mathbb{E}_{Q}[(Y-\psi_{P}(X))^{2}]-H_{2}(P_{Y|X}|P_{X})\big{)}$
(153) $\displaystyle\leq$ $\displaystyle\sqrt{{\rm
Var}_{Q}[(Y-\psi_{Q}(X))^{2}]\chi^{2}(P_{X,Y}\|Q_{X,Y})}+\sqrt{{\rm
Var}_{P}[(Y-\psi_{P}(X))^{2}]\chi^{2}(Q_{X,Y}\|P_{X,Y})}$ (154)
$\displaystyle\leq$
$\displaystyle\sqrt{\mathbb{E}_{Q}[(Y-\psi_{Q}(X))^{4}]\chi^{2}(P_{Y}\|Q_{Y})}+\sqrt{\mathbb{E}_{P}[(Y-\psi_{P}(X))^{4}]\chi^{2}(Q_{Y}\|P_{Y})},$
(155)

where (154) follows from the same argument as in the proof of Theorem 3; and
the last step uses the fact that
$\chi^{2}(P_{X,Y}\|Q_{X,Y})=\chi^{2}(P_{Y}\|Q_{Y})$ and
$\chi^{2}(Q_{X,Y}\|P_{X,Y})=\chi^{2}(Q_{Y}\|P_{Y})$, which follows from the
definition of the $\chi^{2}$ divergence and the fact that $P_{X|Y}$ and
$Q_{X|Y}$ are identical and only depend on the distribution of $V$, as a
consequence of the assumed form of $X$. ∎

Theorem 15 can also be applied to statistical learning problems where the
learned decision rule is optimally designed under a data-determined
distribution $Q$. Combined with the results in Section 2, it can provide
excess risk upper bounds in terms of the statistical distances between $Q$ and
the data-generating distribution $P$. We give an example in the next
subsection.

###  5.3 Excess risk in learning by projecting to exponential family

We now consider a procedure for supervised learning that is different from
both the frequentist learning and the Bayesian learning discussed in the
previous sections. To precisely describe it, we need the following definitions
and properties of exponential family distributions. A parametrized family of
distributions
$\mathcal{Q}=\\{Q_{\theta}:\theta\in\mathsf{\Theta}\subset\mathbb{R}^{d}\\}$
on ${\mathsf{Z}}={\mathsf{X}}\times{\mathsf{Y}}$ is an exponential family if
each element can be written as
$Q_{\theta}(z)=\exp\\{\theta^{\top}\varphi(z)-A(\theta)\\}$ for some
$\theta\in\mathsf{\Theta}$, with
$\varphi:{\mathsf{Z}}\rightarrow\mathbb{R}^{d}$ as a potential function,
$A(\theta)\triangleq\log\int_{\mathsf{Z}}\exp\\{\theta^{\top}\varphi(z)\\}\nu({\rm
d}z)$ as the log partition function, and $\nu$ as a density on ${\mathsf{Z}}$.
For a distribution $P$ on ${\mathsf{Z}}$ which may not belong to
$\mathcal{Q}$, its projection to $\mathcal{Q}$, defined as
$\operatorname*{arg\,min}_{Q\in\mathcal{Q}}D(P\|Q)$, is given by
$Q^{*}\triangleq Q_{\theta^{*}}$ with a $\theta^{*}\in\Theta$ that satisfies

$\displaystyle\nabla A(\theta^{*})=\mu\triangleq\mathbb{E}_{P}[\varphi(Z)].$
(156)

Similarly, given a dataset $Z^{n}=((X_{1},Y_{1}),\ldots,(X_{n},Y_{n}))$ drawn
i.i.d. from $P$, the projection of its empirical distribution
${\widehat{P}}_{n}$ to $\mathcal{Q}$, defined as the solution to the maximum-
likelihood estimation
$\operatorname*{arg\,max}_{Q\in\mathcal{Q}}\sum_{i=1}^{n}\log Q(Z_{i})$, is
given by ${\widehat{Q}}\triangleq Q_{\hat{\theta}}$ with a
$\hat{\theta}\in\Theta$ that satisfies

$\displaystyle\nabla
A(\hat{\theta})=\hat{\mu}\triangleq\frac{1}{n}\sum_{i=1}^{n}\varphi(Z_{i}).$
(157)

Define the convex conjugate of $A$ as
$A^{*}(\mu)\triangleq\sup_{\theta\in\mathsf{\Theta}}\mu^{\top}\theta-A(\theta)$
for any $\mu$ that can be written as $\mathbb{E}_{Q_{\theta}}[\varphi(Z)]$ for
some $\theta\in\mathsf{\Theta}$. When $\mathcal{Q}$ is minimal, meaning that
$Q_{\theta}$ and $Q_{\theta^{\prime}}$ are different for any
$\theta\neq\theta^{\prime}\in\mathsf{\Theta}$, it is known from convex duality
[33] that $\theta^{*}$ and $\hat{\theta}$ implicitly defined above can be
explicitly written as $\theta^{*}=\nabla A^{*}(\mu)$ and $\hat{\theta}=\nabla
A^{*}(\hat{\mu})$. Figure 2 illustrates the above defined quantities.

Figure 2: Illustration of the projections of the data-generating distribution
$P$ and the empirical distribution ${\widehat{P}}_{n}$ to the exponential
family $\mathcal{Q}$.

With the above definitions, the learning procedure under consideration can be
described as follows: given a dataset $Z^{n}$ drawn i.i.d. from $P$, first
project its empirical distribution ${\widehat{P}}_{n}$ to a predefined
exponential family $\mathcal{Q}$ on ${\mathsf{Z}}$ to obtain ${\widehat{Q}}$,
then the learned decision rule for predicting $Y$ based on a fresh observation
$X$ is taken as the Bayes decision rule $\psi_{{\widehat{Q}}}$ that is optimal
under ${\widehat{Q}}$. The following result based on Theorem 15 provides upper
bounds for its expected excess risk.

######  Corollary 13.

For the learning procedure described above, under the assumptions that
$\mathcal{Q}$ is minimal and that the loss function $\ell$ takes values in
$[0,1]$, the expected excess risk of using $\psi_{{\widehat{Q}}}$ as the
learned decision rule under the data-generating distribution $P$ satisfies

$\displaystyle\mathbb{E}[\ell(Y,\psi_{{\widehat{Q}}}(X))]-$ $\displaystyle
H_{\ell}(P_{Y|X}|P_{X})\leq 2d_{\rm TV}(P,Q^{*})+$
$\displaystyle\sqrt{2\|\mu\|\cdot\mathbb{E}\|\nabla A^{*}(\mu)-\nabla
A^{*}(\hat{\mu})\|+2\mathbb{E}|A(\nabla A^{*}(\mu))-A(\nabla
A^{*}(\hat{\mu}))|},$ (158)

where the expectations are taken over either $(Z^{n},Z)$ or ${\widehat{\mu}}$
with $P$ as the underlying distribution.

###### Proof.

To make use of Theorem 15, we first bound the entropy difference. For any
realization of the dataset $Z^{n}$,

$\displaystyle|H_{\ell}({\widehat{Q}}_{Y|X}|{\widehat{Q}}_{X})-H_{\ell}(P_{Y|X}|P_{X})|$
$\displaystyle\leq d_{\rm TV}({\widehat{Q}},P)\leq d_{\rm TV}(P,Q^{*})+d_{\rm
TV}({\widehat{Q}},Q^{*})$ (159)

where the first inequality is due to Lemma 6 and the assumption that
$\ell\in[0,1]$ as used in the proof of Theorem 1, while the second inequality
is due to the triangle inequality satisfied by the total variation distance.
Further,

$\displaystyle d_{\rm TV}({\widehat{Q}},Q^{*})$
$\displaystyle\leq\sqrt{\frac{1}{2}D(Q^{*}\|{\widehat{Q}})}$ (160)
$\displaystyle=\sqrt{\frac{1}{2}\big{(}\mathbb{E}_{Q^{*}}[\varphi(Z)]^{\top}(\theta^{*}-\hat{\theta})-(A(\theta^{*})-A(\hat{\theta}))\big{)}}$
(161)
$\displaystyle\leq\sqrt{\frac{1}{2}\big{(}\|\mu\|\|\theta^{*}-\hat{\theta}\|+|A(\theta^{*})-A(\hat{\theta})|\big{)}}$
(162) $\displaystyle=\sqrt{\frac{1}{2}\big{(}\|\mu\|\|\nabla A^{*}(\mu)-\nabla
A^{*}(\hat{\mu})\|+|A(\nabla A^{*}(\mu))-A(\nabla A^{*}(\hat{\mu}))|\big{)}}$
(163)

where (160) uses the Pinsker’s inequality; (161) uses the property of the
exponential family distributions; (162) uses the fact that
$\mathbb{E}_{Q^{*}}\varphi(Z)=\mu$ and the Cauchy-Schwarz inequality; and
(163) uses (156) and (157) as well as the assumption that $\mathcal{Q}$ is
minimal so that $(\nabla A)^{-1}\equiv\nabla A^{*}$. It then follows from
(145) in Theorem 15 that

$\displaystyle\mathbb{E}[\ell(Y,\psi_{{\widehat{Q}}}(X))|Z^{n}]-$
$\displaystyle H_{\ell}(P_{Y|X}|P_{X})\leq 2d_{\rm TV}(P,Q^{*})+$
$\displaystyle\sqrt{2\big{(}\|\mu\|\|\nabla A^{*}(\mu)-\nabla
A^{*}(\hat{\mu})\|+|A(\nabla A^{*}(\mu))-A(\nabla A^{*}(\hat{\mu}))|\big{)}}$
(164)

almost surely for $Z^{n}$. The claim follows by taking expectations on both
sides of the above inequality over $Z^{n}$ and applying Jensen’s inequality on
the right side. ∎

Corollary 13 clearly shows that the excess risk for learning by projecting the
empirical distribution to an exponential family consists of two parts: the
_approximation error_ , represented by the first term on the right side of
(158), and the _estimation error_ , represented by the second term. The
approximation error depends on the total variation distance from the data-
generating distribution $P$ to the exponential family $\mathcal{Q}$ and does
not depend on the data size. The estimation error on the other hand vanishes
as $n$ grows whenever $A$ and $\nabla A^{*}$ are continuous, which is due to
the fact that $\hat{\mu}\rightarrow\mu$ almost surely as $n\rightarrow\infty$.

The learning procedure considered above can be extended to the cases where the
family of distributions $\mathcal{Q}$ is not predefined, but dependent on the
empirical distribution ${\widehat{P}}_{n}$, and where the distribution
${\widehat{Q}}$ under which the learned decision rule is optimally designed is
found by other criteria. An example is the recently proposed maximum
conditional entropy framework of learning [2], where $\mathcal{Q}$ is a set of
distributions centered at ${\widehat{P}}_{n}$, and ${\widehat{Q}}$ is chosen
to be an element of $\mathcal{Q}$ with the maximum generalized conditional
entropy w.r.t. some loss function. A special case of this framework with
moment-matching conditions to construct $\mathcal{Q}$ and with the log loss
may be interpreted as projecting the empirical conditional distribution
${\widehat{P}}_{Y|X}$ to an exponential family of conditional distributions
associated with a generalized linear model. More generally, the minimax
approach to statistical learning where the goal is to find a decision rule
that minimizes the worst-case expected loss in $\mathcal{Q}$, c.f. [2, 5] and
the reference therein, is equivalent to the maximum conditional entropy
approach under regularity conditions [2]. Whether Theorem 15, especially (146)
can be leveraged to analyze the excess risk in the maximum conditional entropy
framework of learning would be an interesting research problem.

## Appendix

##  Appendix A Proof of Lemma 2

The Donsker-Varadhan theorem states that

$\displaystyle
D(P\|Q)=\sup_{g:{\mathsf{Z}}\rightarrow\mathbb{R}}\mathbb{E}_{P}[g(Z)]-\log\mathbb{E}_{Q}[e^{g(Z)}].$
(165)

It implies that for any $f:{\mathsf{Z}}\rightarrow\mathbb{R}$ and any
$\lambda\in\mathbb{R}$,

$\displaystyle
D(P\|Q)\geq\lambda(\mathbb{E}_{P}[f(Z)]-\mathbb{E}_{Q}[f(Z)])-\log\mathbb{E}_{Q}[e^{\lambda(f(Z)-\mathbb{E}_{Q}f(Z))}].$
(166)

From the assumption that
$\log\mathbb{E}_{Q}[e^{\lambda(f(Z)-\mathbb{E}_{Q}f(Z))}]\leq\varphi_{+}(\lambda)$
for all $0\leq\lambda<b_{+}$ and the definition
$\varphi_{+}^{*}(\gamma)\triangleq\sup_{0\leq\lambda<b_{+}}\lambda\gamma-\varphi_{+}(\lambda)$
for $\gamma\in\mathbb{R}$, we have

$\displaystyle D(P\|Q)$
$\displaystyle\geq\sup_{0\leq\lambda<b_{+}}\lambda(\mathbb{E}_{P}[f(Z)]-\mathbb{E}_{Q}[f(Z)])-\varphi_{+}(\lambda)$
(167)
$\displaystyle=\varphi_{+}^{*}(\mathbb{E}_{P}[f(Z)]-\mathbb{E}_{Q}[f(Z)]).$
(168)

From the definition
$\varphi_{+}^{*-1}(x)\triangleq\sup\\{\gamma\in\mathbb{R}:\varphi_{+}^{*}(\gamma)\leq
x\\}$ for $x\in\mathbb{R}$, we have

$\displaystyle\mathbb{E}_{P}[f(Z)]-\mathbb{E}_{Q}[f(Z)]\leq\varphi_{+}^{*-1}(D(P\|Q)),$
(169)

which proves (24).

The Donsker-Varadhan theorem also implies that for any
$f:{\mathsf{Z}}\rightarrow\mathbb{R}$ and any $\lambda\in\mathbb{R}$,

$\displaystyle
D(P\|Q)\geq\lambda(\mathbb{E}_{Q}[f(Z)]-\mathbb{E}_{P}[f(Z)])-\log\mathbb{E}_{Q}[e^{-\lambda(f(Z)-\mathbb{E}_{Q}f(Z))}].$
(170)

From the assumption that
$\log\mathbb{E}_{Q}[e^{-\lambda(f(Z)-\mathbb{E}_{Q}f(Z))}]\leq\varphi_{-}(\lambda)$
for all $0\leq\lambda<b_{-}$ and the definition
$\varphi_{-}^{*}(\gamma)\triangleq\sup_{0\leq\lambda<b_{-}}\lambda\gamma-\varphi_{-}(\lambda)$
for $\gamma\in\mathbb{R}$, we have

$\displaystyle D(P\|Q)$
$\displaystyle\geq\sup_{0\leq\lambda<b_{-}}\lambda(\mathbb{E}_{Q}[f(Z)]-\mathbb{E}_{P}[f(Z)])-\varphi_{-}(\lambda)$
(171)
$\displaystyle=\varphi_{-}^{*}(\mathbb{E}_{Q}[f(Z)]-\mathbb{E}_{P}[f(Z)]).$
(172)

From the definition
$\varphi_{-}^{*-1}(x)\triangleq\sup\\{\gamma\in\mathbb{R}:\varphi_{-}^{*}(\gamma)\leq
x\\}$ for $x\in\mathbb{R}$, we have

$\displaystyle\mathbb{E}_{Q}[f(Z)]-\mathbb{E}_{P}[f(Z)]\leq\varphi_{-}^{*-1}(D(P\|Q)),$
(173)

which proves (26).

The assumption that $\varphi_{+}(\lambda)$ is strictly convex over $[0,b_{+}]$
and $\varphi_{+}(0)=\varphi_{+}^{\prime}(0)=0$ implies that its Legendre dual
$\varphi_{+}^{*}(\gamma)$ is strictly increasing over $\gamma\geq 0$ and
$\varphi_{+}^{*}(0)=0$. In addition, the fact that $\varphi_{+}^{*}(\gamma)$
is convex over $\gamma\geq 0$ implies that it is continuous over $\gamma\geq
0$. Together these imply that $\varphi_{+}^{*-1}(x)$ is strictly increasing
and continuous over $x\geq 0$, and $\varphi_{+}^{*-1}(0)=0$. It follows that
$\lim_{x\downarrow 0}\varphi_{+}^{*-1}(x)=0$. The same argument can be used to
show that 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$.

## Acknowledgement

The author would like to thank Prof. Maxim Raginsky, Prof. Yihong Wu, and
Jaeho Lee for helpful discussions.

## References

  * [1] 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.
  * [2] F. Farnia and D. Tse, “A minimax approach to supervised learning,” in _Conference on Neural Information Processing Systems_ , 2016.
  * [3] A. Xu, “Continuity of generalized entropy,” in _IEEE International Symposium on Information Theory_ , 2020.
  * [4] A. Xu and M. Raginsky, “Minimum excess risk in Bayesian learning,” _arXiv preprint_ , 2020.
  * [5] J. Lee and M. Raginsky, “Minimax statistical learning with Wasserstein distances,” in _Conference on Neural Information Processing Systems_ , 2018\.
  * [6] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_. Academic Press, 1981.
  * [7] T. Cover and J. Thomas, _Elements of Information Theory_ , 2nd ed. New York: Wiley, 2006.
  * [8] Z. Zhang, “Estimating mutual information via Kolmogorov distance,” _IEEE Transactions on Information Theory_ , vol. 53, no. 9, pp. 3280–3282, 2007.
  * [9] S. Ho and R. W. Yeung, “The interplay between entropy and variational distance,” _IEEE Transactions on Information Theory_ , vol. 56, no. 12, pp. 5906–5929, 2010.
  * [10] I. Sason, “Entropy bounds for discrete random variables via maximal coupling,” _IEEE Transactions on Information Theory_ , vol. 59, no. 11, pp. 7118–7131, 2013.
  * [11] Y. Polyanskiy and Y. Wu, “Wasserstein continuity of entropy and outer bounds for interference channels,” _IEEE Transactions on Information Theory_ , vol. 62, no. 7, 2016.
  * [12] S. Boucheron, G. Lugosi, and P. Massart, _Concentration Inequalities: A nonasymptotic theory of independence_. Oxford University Press, 2013.
  * [13] J. Jiao, Y. Han, and T. Weissman, “Dependence measures bounding the exploration bias for general measurements,” in _IEEE International Symposium on Information Theory (ISIT)_ , 2017.
  * [14] Y. Bu, S. Zou, and V. V. Veeravalli, “Tightening mutual information based bounds on generalization error,” in _IEEE International Symposium on Information Theory (ISIT)_ , 2019.
  * [15] I. Sason and S. Verdú, “$f$ -divergence inequalities,” _IEEE Transactions on Information Theory_ , vol. 62, no. 11, pp. 5973–6006, 2016.
  * [16] Y. Wu, “Lecture notes on information-theoretic methods in high-dimensional statistics,” University of Illinois/Yale University, 2016-2020.
  * [17] I. Kontoyiannis and S. Verdú, “Optimal lossless compression: Source varentropy and dispersion,” in _IEEE International Symposium on Information Theory_ , July 2013, pp. 1739–1743.
  * [18] Y. Wu, _personal communication_ , 2019.
  * [19] D. P. Palomar and S. Verdú, “Lautum information,” _IEEE Transactions on Information Theory_ , vol. 54, no. 3, pp. 964–975, March 2008\.
  * [20] D. Berend and A. Kontorovich, “A sharp estimate of the binomial mean absolute deviation with applications,” _Statistics and Probability Letters,_ , vol. 83, pp. 1254–1259, 2013.
  * [21] ——, “On the convergence of the empirical distribution,” _arXiv:1205.6711_ , 2012.
  * [22] L. Devroye, “The equivalence of weak, strong and complete convergence in $l_{1}$ for kernel density estimates,” vol. 11, no. 3, pp. 896–904, 09 1983.
  * [23] S. Shalev-Shwartz and S. Ben-David, _Understanding Machine Learning: From Theory to Algorithms_. Cambridge University Press, 2014.
  * [24] J. Lei, “Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces,” _Bernoulli_ , vol. 26, no. 1, pp. 767–798, 02 2020.
  * [25] J. Weed and F. Bach, “Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance,” _Bernoulli_ , vol. 25, no. 4A, pp. 2620–2648, 11 2019.
  * [26] L. Devroye, L. Györfi, and G. Lugosi, _A Probabilistic Theory of Pattern Recognition_. Springer, 1996.
  * [27] M. Raginsky, “Empirical processes, typical sequences, and coordinated actions in standard Borel spaces,” _IEEE Transactions on Information Theory_ , vol. 59, no. 3, pp. 1288–1301, March 2013.
  * [28] P. W. Cuff, H. H. Permuter, and T. M. Cover, “Coordination capacity,” _IEEE Transactions on Information Theory_ , vol. 56, no. 9, pp. 4181–4206, 2010.
  * [29] 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.
  * [30] E. Hüllermeier and W. Waegeman, “Aleatoric and epistemic uncertainty in machine learning: A tutorial introduction,” _ArXiv 1910.09457_ , 2019.
  * [31] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan, “A theory of learning from different domains,” _Machine Learning_ , vol. 79, no. 1, pp. 151–175, May 2010.
  * [32] S. Verdú, “Mismatched estimation and relative entropy,” _IEEE Transactions on Information Theory_ , vol. 56, no. 8, pp. 3712–3720, 2010.
  * [33] M. J. Wainwright and M. I. Jordan, “Graphical models, exponential families, and variational inference,” _Foundations and Trends in Machine Learning_ , vol. 1, no. 1–2, pp. 1–305, 2008.