# Mutual Information Learned Classifiers: an Information-theoretic Viewpoint
of Training Deep Learning Classification Systems

Jirong Yi, Qiaosheng Zhang, Zhen Chen
Qiao Liu, Wei Shao Jirong Yi is with CAD Science Group, Hologic Inc, Santa
Clara, CA 95054 and Department of Electrical and Computer Engineering,
University of Iowa, Iowa City, IA 52242. Qiaosheng Zhang is with Department of
Electrical and Computer Engineering at National University of Singapore,
Singapore 119077. Zhen Chen is with Department of Electrical Engineering and
Computer Science at University of California at Irvine, Irvine, CA 92697. Qiao
Liu is with Department of Statistics at Stanford University, Stanford, CA
94305. Wei Shao is with Department of Radiology at Stanford University,
Stanford, CA 94305. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding
emails should be sent to<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Deep learning systems have been reported to acheive state-of-the-art
performances in many applications, and one of the keys for achieving this is
the existence of well trained classifiers on benchmark datasets which can be
used as backbone feature extractors in downstream tasks. As a main-stream loss
function for training deep neural network (DNN) classifiers, the cross entropy
loss can easily lead us to find models which demonstrate severe overfitting
behavior when no other techniques are used for alleviating it such as data
augmentation. In this paper, we prove that the existing cross entropy loss
minimization for training DNN classifiers essentially learns the conditional
entropy of the underlying data distribution of the dataset, i.e., the
information or uncertainty remained in the labels after revealing the input.
In this paper, we propose a mutual information learning framework where we
train DNN classifiers via learning the mutual information between the label
and input. Theoretically, we give the population error probability lower bound
in terms of the mutual information. In addition, we derive the mutual
information lower and upper bounds for a concrete binary classification data
model in $\mathbb{R}^{n}$, and also the error probability lower bound in this
scenario. Besides, we establish the sample complexity for accurately learning
the mutual information from empirical data samples drawn from the underlying
data distribution. Empirically, we conduct extensive experiments on several
benchmark datasets to support our theory. Without whistles and bells, the
proposed mutual information learned classifiers (MILCs) acheive far better
generalization performances than the state-of-the-art classifiers with an
improvement which can exceed more than 10% in testing accuracy.

Keywords: classification; mutual information learning; error probability;
sample complexity; overfitting; deep neural network

##  1 Introduction

Ever since the breakthrough made by Krizhevsky et al. [1], deep learning has
been finding trenmdous applications in different areas such as computer
vision, natural language process, and traditonal signal processing [2, 3, 4],
and it achieved the state-of-the-art performances in almost all of them. In
nearly all of these applications, a fundamental classification task is usually
involved, i.e., determining the class to which a given input belongs. Examples
from computer vision include the image-level classification in recognition
tasks, the patch-level classification in object detection, and pixel-level
classification in image segmentation tasks [5, 6, 7]. For many other
applications which do not directly or explicitly involve classifications, they
still use model pretrained via classification tasks as a backbone for
extracting useful and meaningful representation for the specific tasks [8, 9].
In practice, such extracted representations have been reported to be
beneficial for the downstream tasks [8, 7, 9].

To train such classifiers, the deep learning community has been mainly using
the cross entropy loss or its variants as the objective function for guiding
the search of a good set of model weights [2]. However, the models trained
this way can easily overfit the data and result in pretty bad generalization
performance, and this motivates the proposal of many techniques for improved
generalization. These techniques can be broadly divided into several
categories. From the propsect of data, increasing the dataset size has been
proving to be beneficial for better generalization, but collecting huge amount
of data can be labor-consuming and costly. For example, in medical image
analysis and diagnostics, collecting the dataset can cost millions of dollars,
and the data size is usually very small for some rare disease such as cancer
[10]. The data augmentation is another commonly used technique to increase the
diversity of dataset such as random cropping, flipping, and color jittering
[9, 11, 12]. However, in situations where the dataset itself is scarce, the
data augmentation may not be enough for training a well-performing classifier
such as few shot learning [13].

From the angle of models, traditional machine learning theory shows that
decreasing the flexibility or complexity of the models can help alleviate the
overfitting phenomenon [14, 15, 16, 17]. However, under the background of deep
learning, this does not seem to be a feasible solution because the models
which achieve the state-of-the-art (SOTA) performance are becoming
increasingly more complex with parameters even over one trillion [18, 19, 8].
These huge models are motivated by the increasingly more challenging learning
problems which require the strong capability of huge models to extract useful
information and find meaningful patterns that can be used for solving them,
and which the smaller models are incapable of [19].

Another line of works for improving the generalization performance comes from
the regularization viewpoint, i.e., restricting the model space for searching
during training to avoid overfitting [2]. Examples includes the weight decay
(or $\ell_{2}$ regularization), $\ell_{1}$ regularization, and label smoothing
regularization [12]. The major limitations of these approaches are that they
require prior knowledge about the learning tasks. For example, the $\ell_{1}$
regularization usually requires the ground truth model to have sparse weights
while the $\ell_{2}$ regularization requires the ground truth model to have
small magnitude to achieve good generalization performance. Unfortunately,
such prior knowledge is not always available in practice. What makes things
worse is that it is recently reported that such prior knowledge may make the
learned models adversarially vulnerable such that adversarial attacks can be
easily acheived, and this is because the model can be underfitted to those
unseen adversarial examples [20, 21, 22].

###  1.1 Ignored Conditional Label Entropy

In this paper, we show that the existing cross entropy loss minimization for
training deep neural network classifiers essentially learns the conditional
entropy of the underlying data distribution of the input and the label. We
argue that this can be the fundamental reason which accounts for the severe
overfitting of models trained by cross entropy loss minimization, and the
extremely small training loss in practice implies that the learned model
completely ignores the conditional entropy about the label distribution. The
reasons for such ignorance of the conditional entropy include that the
marginal input entropy is very big when compared with the conditional label
entropy, and that the annotating of input samples in the data collection
process and the encoding of the labels during the training both ignore the
conditional entropy of label.

To see these, we consider the MNIST image recognition task from computer
vision where we want to train a model to predict which class from 10 classes a
given digit image belongs to111http://yann.lecun.com/exdb/mnist/. In this
example, the label has only 10 choices, and the maximum label entropy is
$\log_{2}(10)\approx 3.32$ bits. However, since the image input is in
$\mathbb{R}^{784}$, the maximum entropy of the image distribution can be very
big, i.e., $\log_{2}\left(256^{784}\right)=6272$ bits if we assume each pixel
to take value in $\\{0,1,\cdots,255\\}$ uniformly. The gap between the
information contained in the input image distribution and that contained in
the label distribution is so big that when the model is trained to learn the
conditional entropy of the label distribution after revealing the image input,
it has a strong tendency to simply ignore such remaining information and
directly treat it as zero. This is indeed the case in many machine learning
applications. In the MNIST classification task, when the image of the hand-
written digital is given, we are usually 100% sure which class the image
belongs to. In Figure 1(a), we show one of such images, and there is no doubt
that the digit is 1, thus the label entropy is 0 when this image is given.
However, this is not always case because we can have image samples whose
classes cannot determined with complete certainty. Some such examples are also
presented in Figure 1, the digit in Figure 1(b) has a truth label 1, but it
looks like 2. Similarly, the digit in Figure 1(c) has a truth label 4 but
looks like 9, and Figure 1(d) has a truth label 9 but looks like 4. Different
people can have different labels for these image samples, but their ground
truth annotations or labels are at the discretion of the creator of them. In
more complex image classification tasks such as ImageNet classification, a
single image itself can contain multiple objects, and thus belong to multiple
classes. However, it has only single annotation or label which depends on the
discretion of the human annotators [23]. In Figure 2, we show image examples
from the ImageNet-1K classification task where the goal is to classify a given
image into 1000 classes. Though Figure 2(a) contains also a pencil, the human
annotator only labeled it with cauliflower label. In deep learning practice,
since we usually use the one-hot encoding of the label for a given image,
i.e., assigning all the probability mass to the annotated class while zero to
all the other classes, this further encourages the model to ignore the
conditional information of the label [9, 12, 6]. The ignorance of label
entropy allows the classifiers to give over-confident label predictions,
resulting in unsatisfactory generalization performance.

(a) Truth label is 1

(b) Truth label is 1

(c) Truth label is 4

(d) Truth label is 9

Figure 1: Image examples from MNIST dataset.

(a) Truth label is cauliflower

(b) Truth label is cauliflower

Figure 2: Image examples from ImageNet dataset. Though Figure 2(a) contains
also a pencil, the human annotator only labeled it with cauliflower. In deep
learning practice, since we usually use the one-hot encoding of the label for
a given image, i.e., assigning all the probability mass to the annotated class
while zero to all the other classes, this further encourages the model to
ignore the conditional entropy of the label [9, 12, 6].

Based on the above observations, a naive way for improving the generalization
performance can be getting back the conditional entropy of label, e.g., giving
multiple annotations for a single image if it contains multiple objects during
the data generation process, and using other types of label encoding instead
of one-hot encoding during the training process. The deep learning community
seems to also realize the limitations of dataset with single annotation for
images containing multiple objects, thus created the ImageNet ReaL benchmark
in 2020 which is more than 10 years after the construction of the original
ImageNet dataset [23, 24]. However, these re-assessed labels only partially
fixed the conditional information loss of labels, and can still suffer the
conditional information loss when an object itself has uncertainty as we show
in Figure 1. Besides, annotating each object in an image can be extremely
labor-consuming, or even impossible in cases where some objects are so small
that they can hardly be perceivable [25].

As for using different label encoding methods instead of the one-hot encoding,
all of them assume implicitly that the annotations are reasonably good [12, 9,
26]. Examples of other label encodings include the label-smoothing
regularization (LSR), generalized entropy regularization (GER), and so on [12,
26]. In LSR, Szegedy et al. replaced the one-hot encoding of labels in the
cross entropy loss minimization with a mixture of the original one-hot
distribution and a uniform distribution, and this mixture encoding is obtained
by taking a small probability mass from the annotated class and then evenly
spreading it over all the other classes [12]. In GER, Meister et al. proposed
to use a skew-Jensen divergence to encourage the learned conditional
distribution to approximate the mixture encoding of label, and they add this
extra divergence term as a regularization to the original cross entropy loss
minimization [26]. However, these efforts can still have severe limitations.
First of all, the construction of mixture encoding of label can be quite
biased due to the similar reasons accounting for the conditional entropy loss
in dataset construction process. Secondly, their focus is still on improving
the conditional entropy, and this can be very challenging since the gap
between the conditional entropy of the label and the differential entropy of
the input is so big that after we reveal the the input, the conditional
entropy of the label distribution can be very small and hard to learn.

###  1.2 Mutual Information Learned Classifiers

In this paper, we propose a new learning framework, i.e., mutual information
learning (MIL) where we train classifiers via learning the mutual information
of the dataset, i.e., the dependency between the input and the label, and this
is motivated by several observations.

First of all, we show that the existing cross entropy loss minimization for
training DNN classifiers actualy learns the conditional entropy of the label
when the input is given. From an information theoretic viewpoint, the mutual
information between the input and the label quantifies the information shared
by them while the conditional entropy quantifies the information remained in
the label after revealing the input. Compared with the conditional entropy,
the magnitude of the mutual information can be much larger, and it may not be
easily ignored by the model during training, thus possible to alleviate the
overfitting phenomenon. An illustration of the relation among different
information quantities involved in a dataset is shown in Figure 3.

In addition, in 2020, there are several works which apply information
theoretic tools to investigate DNN models [27, 28, 29]. In [28], Yi et al.
investigated the adversarial attack problems from an information theoretic
viewpoint, and they proposed to acheive adversarial attacks by minimizing the
mutual information between the input and the label. Yi et al. also established
theoretical results for characterizing what the best an adversary can do for
attacking machine learning models [28]. Concurrently, in [27], Wang et al.
used information theoretic tools to derive interesting relations between the
existing adversarial training formulations and the conditional entropy
optimizations. These works imply that there are intrinsinc connections between
the properties of the model learned from the dataset and the information
contained in the dataset. Last but not least, some recent works on training
DNN reported that increasing entropy about the labels can improve the
generalization performance, and even make the model more adversarially robust
[12, 26, 30]. Though these results imply that the overfitting can be due to
the severe ignorance of the conditional entropy of the label during training,
we argue that a more appropriate quantity for guiding the learning and
training of classification systems can be the mutual information (MI) which
better characterizes the dependency between the input and the label. Besides,
the MI usually has larger magnitude than the conditional label entropy in
classification tasks, making it less to be ignored by the model and affected
by the numerical precisions. To see this, we can consider an extreme case
where the model gives uniform distribution for the label when an arbitrary
example is fed to the model. In this case, the conditional entropy of the
label acheives the maximum, but what the model learned can be meaningless
since it cannot accurately characterize the dependency between the input and
the label.

Figure 3: Information quantities involved in joint data distribution
$p_{X,Y}$. The big circle represents the differential entropy $h(X)$ or
information contained in input random variable $X$, and the small circle
represents the entropy $H(Y)$ or information contained in the label random
variable $Y$. The overlapped area corresponds to the mutual information or
information shared by the $X$ and the $Y$, and the area in the small circle
after excluding the overlapped area corresponds to the information remained in
the $Y$ after revealing the $X$.

Under our mutual information learning (MIL) framework, we design a new loss
for training the DNN classifiers, and the loss itself originates from a
representation of mutual information of the dataset generating distribution,
and we propose new pipelines associated with the proposed framework. We will
refer to this loss as mutual information learning loss (milLoss), and the
traditional cross entropy loss as conditional entropy learning loss (celLoss)
since it essentially learning the conditional entropy of the dataset
generating distribution. When reformulated as a regularized form of the
celLoss, the milLoss can be interpreted as a weighted sum of the conditional
label entropy loss and the label entropy loss. In the regularized form, the
milLoss encourages the model not only to accurately learn the conditional
entropy of the label when an input is given, but also to precisely learn the
entropy of the label. This is distinctly different from the label smoothing
regularization (LSR), confidence penalty (CP), label correction (LC) etc which
consider the conditional entropy of the label [11, 31, 26].

For the proposed MIL framework, we establish an error probability lower bound
for arbitrary classification models in terms of the mutual information (MI)
associated with the data generating distribution by using Fano’s inequality
[32] and an upper bound of error probability entropy developed by Yi et al.
[28]. These bounds explicitly characterize how the performance of the
classification models trained from a dataset is connected to the mutual
information contained in it, i.e., the dependency between the input and the
output. Compared to Fano’s inequality, our bound is tighter due to a carefully
designed relaxation. Our error probability bound is applicable for arbitrary
distribution and arbitrary learning algorithms. We also consider a concrete
binary classification problem in $\mathbb{R}^{n}$, and derive both lower and
an upper bounds of the mutual information associated with the data
distribution. Besides, we derive an error probability bound for this binary
classification data model. We also establish theoretical guarantees for
training models to accurately learn the mutual information associated with
arbitrary dataset generating distribution, and we give the sample complexity
for achieving this in practice. The keys for establishing these are the
universal approximation properties of neural networks and the concentration of
measure phenomenon from statistics [33, 34, 35, 33, 14, 17]. We conduct
extensive experiments to validate our theoretical analysis by using
classification tasks on benchmark dataset such as MNIST and
CIFAR-10222https://www.cs.toronto.edu/ kriz/cifar.html. The empirical results
show that the proposed MIL framework can achieve far superior generalization
performance than the existing conditional entropy learning approach and its
variants [11, 36, 31].

###  1.3 Related Works

Our work is highly related to the following several works, but there are
distinct differentiations between our work and them [6, 28, 29]. First of all,
in 2019, Yi et al. formulated the classification problem under the encoding-
encoding paradigm by assuming there is an observation synthesis process which
can generate observations or inputs for a given label, and the classification
task is simply about inferring the label from the observation. Under this
framework, they give theoretical characterizations of the robustness of
machine learning models to different types of perturbations [6]. They also
characterized the limit of an arbitrary adversarial attacking algorithm for an
arbitrary machine learning system for answering the question of what is the
best attack that an adversary can acheive and what the optimal adversarial
attacks look like [28]. We continue to investigate the classification tasks
using encoding-decoding paradigm. Though the works by Yi et al., are the major
motivations for this work, the goal of this work is completely different. We
investigate the learning of classification models without presence of
adversaries, and the connection between the models’ generalization performance
and the mutual information of the dataset generating distribution [6, 28, 29].

Our work is also highly related to that by [37] where the authors proposed a
difference-of-entropy (doe) formulation for estimating the mutual information
of a distribution from empirical observations sampled from it [37]. In their
formulation, two different neural networks are trained jointly to learn the
conditional entropy and the entropy, respectively. In this paper, our goal is
to train DNN classifiers with good generalization performances rather than
estimating the mutual information. We use a formulation similar to the doe in
[37], but we also consider the scenario where we use a single neural network
to learn both of them, and the new scenario follows the weight sharing ideas
in deep learning practice [2]. Besides, we prove that the existing cross
entropy loss minimization approach is essentially learning the conditional
entropy, and establish error probability lower bound in terms of the mutual
information. In addition, we give sample complexity for the accurate learning
of the mutual information from empirical samples, and derived the lower bound
and upper bounds of the mutual information in a binary classification data
model.

Our work is also related to [21] where Xu and Raginsky investigated the
generalization performance from an information-theoretic viewpoint, and they
derived upper bounds for generalization error (essentially equivalent to error
probability) in terms of mutual information between the dataset and the model
set (the model is also assumed to follow a distribution). Though we also
derived the error porbability lower bound in terms of the mutual information,
the mutual information we consider in this paper is associated with the
dataset only, i.e., the mutual information between the data input and the data
label while the mutual information considered by Xu and Raginsky is from the
joint distribution of data input, data output, and the model itself [21].

Loss obj. | Formula
---|---
celLoss | $H(P_{Y|X},Q_{Y|X})$
celLoss$+$LSR | $(1-\epsilon)H(P_{Y|X},Q_{Y|X})+\epsilon H(U_{Y|X},Q_{Y|X})$
celLoss$+$CP | $(1-\epsilon)H(P_{Y|X},Q_{Y|X})-\epsilon H(Q_{Y|X},Q_{Y|X})$
celLoss$+$LC | $(1-\epsilon)H(P_{Y|X},Q_{Y|X})+\epsilon H(Q_{Y|X},Q_{Y|X})$
milLoss (proposed) | $H(P_{Y|X},Q_{Y|X})+\lambda_{ent}H(P_{Y},Q_{Y})$
Table 1: Comparisons among celLoss, LSR+celLoss, CP+celLoss, LC+celLoss, and
regularized form of milLoss. The $P_{Y|X}$ and $P_{Y}$ are the conditional and
marginal label distribution, respectively. The $Q_{Y|X}$ and the $U_{Y|X}$ are
the predicted conditional label distribution and the uniform conditional label
distribution.

Another line of works which is highly related to this paper includes [12, 26,
36, 31] where the regularized forms of celLoss are considered such as the LSR,
CP, and LC. See the difference between these loss functions and the
regularized form of our proposed one in Table 1. The key assumption of the LSR
and the CP is that the one-hot label is too confident, and a less confident
prediction should be preferred. This is achieved by encouraging the prediction
to be also close to a uniform distribution in LSR, or to have high entropy in
CP [11, 36]. The LC assumes the model will fit to the data distribution before
overfitting to the noise during training, and the model should trust its
prediction after certain stages during training. This is achieved by
encouraging the model to have low-entropy or high-confidence prediction [31].
In both [12, 36, 31] and most of other related works, the regularizations
still look at the conditional label distribution only while the regularization
term in our formulation looks at the marginal label distribution.

###  1.4 Contributions

The contributions of this work are summarized as follows.

  * •

We show that the existing cross entropy loss minimization approach for
training DNN essentially learns the conditional entropy, and we point out some
of the fundamental limitations of this approach. These limitations motivate us
to propose a new training paradigm via mutual information learning.

  * •

For the proposed mutual information learning (MIL) framework, we give
theoretical anaysis to answer several fundamental questions, i.e., how the
error probability over the distribution is connected to the mutual information
between the data input and the data label, and what the sample complexity is
for accurately learning the mutual information and thus a classifiers with
excellent generalization performance. For the formal, we derive a lower bound
for the error probability in terms of the mutual information. For the later,
we derive the sample complexity for learning the MI from empirical risk
minimization. These results are applicable for arbitrary data distributions.
To better appreciate the MIL framework, we consider a concrete binary
classification data model, and derive bounds for the mutual information error
probability associated with the data distribution.

  * •

As a proof of concept, we conduct extensive experiments with training DNN
classifiers on several benchmark datasets to validate our theory, and the
empirical results show that the proposed MIL can improve greatly the
generalization performance of DNN classifiers.

This paper is organized as follows. In Section 2, we present necessary
definitions and relations which will be used in later sections. In Section 3,
we show that the existing cross entropy loss minimization is equivalent to
learning the conditional entropy of the label, and we also give upper bound of
estimating entropy or conditional entropy from empirical data samples. We
present the mutual information learning (MIL) framework in Section 4, derive
the error probability lower bound in terms of the mutual information in
Section 5, and establish the guarantees for learning the mutual information
from empirical data samples in Section 6. In Section 7, we consider a binary
classification data model, and derive bounds of the mutual information and the
error probability of the data distribution. We present experimental results in
Section 8, and conclude this paper in Section 9.

Notations: We use $X$ to represent a random variable or vector, and its
dimensions should be determined in the specific context. We denote by $P(X)$
or $P_{X}$ the probability mass function of $X$ if $X$ is a discrete random
variable or vector, and by $p(X)$ or $p_{X}$ the probability density function
of $X$ if $X$ is continuous. Without loss of generality, we will refer to both
as probability distribution. The joint distribution of a continuou radnom
variable $X$ and discrete random variable $Y$ will be denoted by $p_{X,Y}$ or
$p(X,Y)$. For the distribution $P_{X}$ of a discrete random variable $X$ with
$N$ realizations, we will alternatively use it as a vector representation
$P\in[0,1]^{N}$. Similarly, for the joint distribution $P_{X,Y}$ of discrete
random variable $X$ with $N$ realizations and discrete random variable $Y$
with $C$ realizations, the $P$ will be alternatively denoted as a matrix in
$[0,1]^{N\times C}$. We denote by $p_{X|U}$ or $P_{X|U}$ conditional
distribution of $X$ given $U$. The entropy (or the differential entropy) of a
discrete (or continuous) random variable $X$ is denoted by $H(X)$ (or $h(X)$).
Unless specified, all the entropy (or differential entropy), and mutual
information quantities are in nats. When it is necessary, we also use
subscript to emphasize the distribution with respect to which these quantities
are computed or simply for avoiding confusions, e.g., $I_{p_{X,Y}}(X;Y)$ means
that the mutual information between $X,Y$ is calculated under distribution
$p_{X,Y}$. For a distribution $Q_{Y}$ parameterized by $\theta$, we will
denote it alternatively by $Q_{Y;\theta}$ and $Q_{Y}(\cdot;\theta)$. The
probability mass (or the probability density) at a realization $y$ of discrete
(continuous) random variable $Y$ will be denoted by $P_{Y}(Y)$ and
$P_{Y}(Y=y)$ (or $p_{Y}(y)$ and $p_{Y}(Y=y)$) alternatively.

We use $[B]$ where $B$ is a positive integer to denote a set
$\\{1,2,\cdots,B\\}$. We denote by
$\mathcal{S}:=\\{(x_{i},y_{i})\\}_{i=1}^{N}\subset\mathbb{R}^{n}\times[C]$ a
set of data samples where $x_{i}\in\mathbb{R}^{n}$ is the input (or feature)
and $y_{i}$ is the corresponding output (or label, or prediction, or target),
and by $\mathcal{S}_{x}:=\\{x_{i}\\}_{i=1}^{N}$ a set of features or input by
dropping the labels. In this paper, we assume $\|x_{i}-x_{j}\|>0,\forall i\neq
j$. The $\mathcal{S}|_{x}$ denotes a subset of $\mathcal{S}$ with the input
being $x$, i.e.,
$\mathcal{S}|_{x}:=\\{(x_{i},y_{i})\in\mathcal{S}:x_{i}=x\\}$. We denote by
$\bm{0}$ a vector or a matrix whose elements are all zero, and by $\bm{1}$ a
vector or a matrix whose elements are 1. We use $I_{n}\in\mathbb{R}^{n\times
n}$ to denote an identity matrix. The $|Q|$ denotes the determinant of a
square matrix $Q$, and the cardinality of a set $\mathcal{S}$ is denoted by
${\rm card}(\mathcal{S})$ or $|\mathcal{S}|$. All the proofs can be found in
the Appendix.

##  2 Preliminaries

We consider the classification tasks in machine learning, i.e., given a
dataset $\mathcal{S}:=\\{(x_{i},y_{i})\\}_{i=1}^{N}$ drawn according to a
joint data distribution $p_{X,Y}$ where
$(x_{i},y_{i})\in\mathbb{R}^{n}\times[C]$ with $C$ being a positive integer,
we want to learn a mapping $M:\mathbb{R}^{n}\to[C]$ from $\mathcal{S}$ such
that $M$ can classify an unseen sample $x^{\prime}\sim p_{X}$ in
$\mathbb{R}^{n}$ to the correct class. The mutual information $I(X,Y)$ of the
input $X$ and the label $Y$ under the joint distribution $p_{X,Y}$ in this
setup can then be defined as

$\displaystyle I(X;Y)$
$\displaystyle:=\int_{x\in\mathbb{R}^{n}}\sum_{y\in[C]}p(x,y)\log\left(\frac{p(x,y)}{p(x)P(y)}\right)dx,$
(1)

where we also define $p(x,y):=p(x)P(y|x)$ and $p(x,y):=P(y)p(x|y),\forall
x\in\mathbb{R}^{n},y\in[C]$. Similar to the Shannon information theory
framework, we define several other information-theoretic quantities as in
Definition 1, 2, 3, and 4. The definitions of entropy, differential entropy,
and cross entropy are exactly the same as those in Shannon information theory,
and we present them for self-containedness.

######  Definition 1.

(Differential Entropy and Entropy) For a continuous random vector
$X\in\mathbb{R}^{n}$ with distribution $p_{X}$, we define its differential
entropy $h(X)$ as

$\displaystyle h(X):=-\int_{x\in\mathbb{R}^{n}}p(x)\log(p(x))dx.$ (2)

For a discrete random variable $Y\in[C]$ with distribution $P_{Y}$, we define
its entropy as

$\displaystyle H(Y):=-\sum_{y\in[C]}P(y)\log(P(y)).$ (3)

######  Definition 2.

(Conditional Differential Entropy and Conditional Entropy) For a joint
distribution $p_{X,Y}$ of a continuous random vector $X\in\mathbb{R}^{n}$ and
discrete random variable $Y\in[C]$, we define the conditional differential
entropy $h(X|Y)$ as

$\displaystyle
h(X|Y):=\sum_{y\in[C]}P(y)\int_{x\in\mathbb{R}^{n}}p(x|y)\log\left(\frac{1}{p(x|y)}\right)dx,$
(4)

and the instance conditional differential entropy at realization $y$ for $Y$
as

$\displaystyle
h(X|y):=\int_{\mathbb{R}^{n}}p(x|y)\log\left(\frac{1}{p(x|y)}\right)dx.$ (5)

We define the conditional entropy $H(Y|X)$ as

$\displaystyle
H(Y|X):=\int_{x\in\mathbb{R}^{n}}p(x)\sum_{y\in[C]}P(y|x)\log\left(\frac{1}{P(y|x)}\right)dx,$
(6)

and the instance conditional entropy at realization $x$ of $X$ as

$\displaystyle H(Y|x):=\sum_{y\in[C]}P(y|x)\log\left(\frac{1}{P(y|x)}\right).$
(7)

######  Definition 3.

(Cross Entropy) We define the cross entropy between two continuous
distributions $p_{X},q_{X}$ over the same continuous support set $\Omega$ as

$\displaystyle
h(p_{X},q_{X}):=\int_{x\in\Omega}p_{X}(x)\log\left(\frac{1}{q_{X}(x)}\right)dx.$
(8)

We define the cross entropy between discrete distributions $P_{Y},Q_{Y}$ over
the same discrete support set $\Omega$ as

$\displaystyle
H(P_{Y},Q_{Y}):=\sum_{y\in\Omega}P_{Y}(y)\log\left(\frac{1}{Q_{Y}(y)}\right).$
(9)

######  Definition 4.

(Conditional Cross Entropy) For two joint distributions $p_{X,Y}$ and
$q_{X,Y}$ of a continuous random vector $X\in\mathbb{R}^{n}$ and discrete
random variable $Y\in[C]$, we define the conditional cross entropy
$H(P_{Y|X},Q_{Y|X})$ as

$\displaystyle
H(P_{Y|X},Q_{Y|X}):=\int_{x\in\mathbb{R}^{n}}p_{X}(x)\sum_{y\in[C]}P_{Y|X}(y|x)\log\left(\frac{1}{Q_{Y|X}(y|x)}\right)dx,$
(10)

and the conditional cross entropy $H(P_{X|Y},Q_{X|Y})$ as

$\displaystyle
h(p_{X|Y},q_{X|Y}):=\sum_{y\in[C]}P_{Y}(y)\int_{x\in\mathbb{R}^{n}}p_{X|Y}(x|y)\log\left(\frac{1}{q_{X|Y(x|y)}}\right)dx.$
(11)

The proposed concept of conditional cross entropy will be used to derive a new
formulation for training classifiers. The connections among these information-
theoretic quantities are presented in Theorem 2.1. Theorem 2.1 shows that for
the joint distribution of a continous random variable and a discrete random
variable, the relations among the mutual information, the entropy, and the
conditional entropy are are exactly the same as those in the case where the
joint distribution is over two continuous random variables or over two
discrete random variables. The proof of Theorem 2.1 can be found in the
Appendix.

######  Theorem 2.1.

(Connections among different information-theoretic quantities) For a joint
distribution $p_{X,Y}$ over a continous random vector $X\in\mathbb{R}^{n}$ and
a discrete random variable $Y\in[C]$ where $C$ is a positive integer constant,
with the definition of mutual information in (1) and Defintion 1-4, we have

$\displaystyle I(X,Y)=H(Y)-H(Y|X),$ $\displaystyle I(X,Y)=h(X)-h(X|Y).$ (12)

##  3 Cross Entropy Loss Minimization as Conditional Entropy Learning

The common practice in the machine/deep learning commnunity separates the
training or learning process and the decision or inference process, i.e., by
first learning a conditional probability $Q_{Y|X}(y|x;\theta_{Y|X})\in[0,1]$of
$Y$ given a realization $x$ of $X$, and then making decisions about the labels
via checking which class achieves the highest probability. The $\theta_{Y|X}$
denotes the parameters associated with the function
$Q_{Y|X}(\cdot;\theta_{Y|X})$. The former process is achieved by minimizing
the cross entropy loss between an empirical conditional distribution
$\hat{P}_{Y|X}$ from data samples and the estimated conditional distribution
$Q_{Y|X}(\cdot;\theta_{Y|X})$, i.e.,

$\displaystyle\min_{\theta_{Y|X}}\frac{1}{N}\times\sum_{(x,y)\in\mathcal{S}}\left(\sum_{c\in[C]}\left(\hat{P}_{Y|X}(c|x)\log\left(\frac{1}{Q_{Y|X}(c|x;\theta_{Y|X})}\right)\right)\right),$
(13)

while the inference process is then achieved via

$\displaystyle\hat{y}_{i}=\arg\max_{c\in[C]}\left[Q_{Y|X}(x_{i};\theta_{Y|X})\right]_{c}.$
(14)

Thus, the mapping $M:\mathbb{R}^{n}\to[C]$ is a composite function of the
probability prediction function $Q_{Y|X}(\cdot;\theta_{Y|X})$ and the maximum
probability inference function $\arg\max$.

The empirical distribution $\hat{P}_{Y|X}$ is usually affected by the data
collection process and the encoding methods for labels. For example, in image
recognition tasks, a single image can have multiple objects, but it is at the
human annotators’ discretion about which label we want to use. Even for this
particular label, different label encoding methods can give different label
representations. When the one-hot representation is used for encoding labels,
the empirical distribution $\hat{P}_{Y|X}$ will be

$\displaystyle\hat{P}_{Y|X}(y|x_{i})=\begin{cases}1,{\rm if\ }y=y_{i},\\\
0,{\rm o.w.}\end{cases}$ (15)

which means that only the target class gets all the probability mass while all
the other classes have zero probability mass. When the label-smoothing
regularization is used, the $\hat{P}_{Y|X}$ is defined as

$\displaystyle\hat{P}_{Y|X}(y|x_{i})=\begin{cases}1-\epsilon,\text{ if
}y=y_{i},\\\ \frac{\epsilon}{C-1},\text{o.w.}\end{cases}$ (16)

where $\epsilon>0$ is a constant [12]. With the one-hot encoding for labels,
the cross entropy minimization (13) can be simplified as

$\displaystyle\min_{\theta_{Y|X}}\frac{1}{N}\times\sum_{(x,y)\in\mathcal{S}}\left(\log\left(\frac{1}{Q_{Y|X}(y|x;\theta_{Y|X})}\right)\right)$
(17)

The $Q_{Y|X}(\cdot;\theta_{Y|X})$ can be interpreted as estimated conditional
distribution of $Y$ when the realization $x$ of the continuous random variable
$X$ is given.

The
$\sum_{c\in[C]}\hat{P}_{Y|X}(c|x)\log\left(\frac{1}{Q_{Y|X}(c|x;\theta_{Y|X})}\right)$
in (13) can be interpreted as an estimate of the instance conditional entropy
of the truth data distribution $P_{Y|X}(Y|x)$ conditioning on the realization
$x$ of $X$, i.e.,

$\displaystyle
H(Y|x)\approx\sum_{c\in[C]}\hat{P}_{Y|X}(c|x)\log\left(\frac{1}{Q_{Y|X}(c|x;\theta_{Y|X})}\right).$
(18)

In Theorem 3.1, we will show that this is indeed the case under certain
conditions, and the cross entropy minimization in (13) learns the conditional
entropy of the truth data distribution $P_{Y|X}$. Thus, we will refer to (13)
as conditional entropy learning (CEL) and the corresponding loss function as
CEL loss (celLoss). In the later sections, we will propose a mutual
information learning (MIL) framework, and refer to the corresponding loss as
MIL loss (milLoss).

Similar to Shannon information theory, we define the $\hat{P}_{X}$ associated
with the input data $\mathcal{S}_{x}:=\\{x_{i}\\}_{i=1}^{N}$ of the data set
$\mathcal{S}:=\\{(x_{i},y_{i})\\}_{i=1}^{N}$ drawn from distribution $p_{X,Y}$
as

$\displaystyle\hat{P}(X=x_{i})=\frac{\left|\\{x\in\mathcal{S}_{x}:x=x_{i}\\}\right|}{N}\in[0,1],\forall
i\in[N],$ (19)

where we define $[N]:=\\{1,2,\cdots,N\\}$. Since we assume
$\|x_{i}-x_{j}\|>0,\forall i\neq j$, we have $\hat{P}(X=x_{i})=\frac{1}{N}$.
The objective function in (13) becomes an estimate of the conditional entropy
$H(Y|X)$ with respect to $P_{Y|X}$, i.e.,

$\displaystyle
H(Y|X)\approx\sum_{(x,y)\in\mathcal{S}}\left(\hat{P}_{X}(x)\hat{P}_{Y|X}(y|x)\log\left(\frac{1}{\left[Q_{Y|X}(x;\theta^{*}_{Y|X})\right]_{y}}\right)\right),$
(20)

where $Q_{Y|X}(\cdot;\theta^{*}_{Y|X})$ is an optimal conditional distribution
determined by $\theta_{Y|X}$. In Theorem 3.1 and its implications, we show
that the cross entropy minimization in (13) for training classifiers learns
the conditional entropy when $Q_{Y|X}(\cdot|\theta_{Y|X})$ is the solution to
an optimization problem.

######  Theorem 3.1.

(Cross Entropy Minimization as Entropy Learning) For an arbitrary discrete
distribution $P_{Y}$ in $[C]$, we have

$\displaystyle H(Y)\leq\inf_{Q_{Y}}H(P_{Y},Q_{Y}),$ (21)

where $Q_{Y}$ is a distribution of $Y$, and the equality holds if and only if
$P_{Y}=Q_{Y}$. When a set of $N$ data points
$\mathcal{S}:=\\{y_{i}\\}_{i=1}^{N}$ drawn independently from $P_{Y}$ is
given, by defining $R(y):=\frac{P_{Y}(y)}{\hat{P}_{Y}(y)}$ where $\hat{P}_{Y}$
is the empirical distribution associated with $\\{y_{i}\\}_{i=1}^{N}$, we have

$\displaystyle H(Y)\leq\inf_{Q^{g}_{Y}}H(\hat{P}_{Y}^{g},Q_{Y}^{g}),$ (22)

where $\hat{P}_{Y}^{g}$ is defined as

$\displaystyle\hat{P}_{Y}^{g}(y):=\hat{P}_{Y}(y)R(y),\forall{y\in[C]},$ (23)

and $Q_{Y}^{g}$ is defined as

$\displaystyle Q_{Y}^{g}(y)=Q_{Y}(y)R(y),\forall{y\in[C]},$ (24)

with $Q_{Y}$ being a distribution of $Y$. The inequality holds if and only if
$P_{Y}=\hat{P}_{Y}=Q_{Y}$.

The proof of Theorem 3.1 can be found in the Appendix. Theorem 3.1 shows that
the entropy $H(Y)$ is upper bounded by the cross entropy $H(P_{Y},Q_{Y})$, and
the calculation of $H(Y)$ can be achieved by finding $Q_{Y}$ to minimize
$H(P_{Y},Q_{Y})$. Theorem 3.1 also tells us that the entropy $H(Y)$ can
actually be estimated from the empirical distribution $\hat{P}_{Y}$ over the
sample set by minimizing a generalized cross entropy
$H(\hat{P}_{Y}^{g},{Q}_{Y}^{g})$. We want to emphasize that though we call
$H(\hat{P}_{Y}^{g},{Q}_{Y}^{g})$ generalized cross entropy, it may not
actually be an entropy since the $\hat{P}_{Y}^{g},{Q}_{Y}^{g}$ may not be
valid distributions. In practice, when we assume $R(y)=1,\forall y\in[C]$, and
this gives

$\displaystyle\hat{H}(Y):=\inf_{Q_{Y}}H(\hat{P}_{Y},{Q}_{Y})$ (25)

which is equal to $H(Y)$ if and only if $P_{Y}(y)=\hat{P}_{Y}(y)=Q_{Y}(y)$.
Theorem 3.1 essentially implies the possibility of learning entropy from
empirical samples.

In the classification tasks as we discussed in Section 2, we can have similar
formulation for $H(Y|X)$

$\displaystyle{H}(Y|X)$
$\displaystyle\approx\inf_{Q_{Y|X}}H(\hat{P}_{Y|X},{Q}_{Y|X})$
$\displaystyle=\inf_{Q_{Y|X}}\sum_{(x,y)\in\mathcal{S}}\hat{p}_{X,Y}(x,y)\log\left(\frac{1}{Q_{Y|X}(y|x)}\right)$
$\displaystyle=\inf_{Q_{Y|X}}\sum_{(x,y)\in\mathcal{S}}\hat{P}_{X}(x)\hat{P}_{Y|X}(y|x)\log\left(\frac{1}{Q_{Y|X}(y|x)}\right)$
(26)

where $\hat{P}_{Y|X}$ is the empirical conditional distribution of $Y$ given
$X$. In (13), the objective function in the cross entropy minimization is
essentially $H(\hat{P}_{Y|X},{Q}_{Y|X})$ with ${Q}_{Y|X}$ parameterized by
$\theta_{Y|X}$. This implies that if the $\hat{P}_{Y|X}$ and $\hat{P}_{X}$ are
the same as the ground truth distributions, then the optimal objective
function value in (13) will be the conditional entropy $H(Y|X)$, i.e., the
commonly used cross entropy loss minimization is essentially learning the
conditional entropy $H(Y|X)$. We will refer to these classifiers as
conditional entropy learning classifiers (CELC, /selk/).

From Theorem 2.1, the mutual information (MI) can be learned via

$\displaystyle I(X;Y)$ $\displaystyle=H(Y)-H(Y|X)$
$\displaystyle\approx\inf_{Q_{Y}}H(\hat{P}_{Y},Q_{Y})-\inf_{Q_{Y|X}}H(\hat{P}_{Y|X},Q_{Y|X}),$
(28)

where $\hat{P}_{Y}$ is the empirical distribution of $Y$ associated with the
label components $\mathcal{S}_{y}:=\\{y_{i}\\}_{i=1}^{N}$ in $\mathcal{S}$,
i.e.

$\displaystyle\hat{P}_{Y}(Y=c):=\frac{\left|\\{y\in\mathcal{S}_{y}:y=c\\}\right|}{N},c\in[C].$
(29)

We want to point out that in [37], McAllester and Stratos also proposed a
formula similar to (3) as an estimation for MI, i.e., estimating
$h(X)=\inf_{q_{X}}H(p_{X},q_{X})$ via

$\displaystyle\hat{H}^{N}(\hat{P}_{X},Q_{X})=\inf_{Q_{X}}\left(-\frac{1}{N}\sum_{i=1}^{N}\log(Q_{X}(x_{i}))\right),$
(30)

but they did not quantify the relation between the cross entropy computed via
the truth distribution and that computed via the empirical distribution.
Besides, there are other fundamental differentiations between their
formulation and the one we use for establishing the mutual information
learning framework in later sections, e.g., we will use a single neural
network to learn both the marginal distribution $Q_{Y}$ and the conditional
distribution $Q_{Y|X}$ while McAllester and Stratos used two separate neural
networks to acheive this.

##  4 Training Classifiers via Mutual Information Learning

In this section, we formally present a new framework for training classifiers,
i.e., via mutual information learning instead of the conditional entropy
learning in existing paradigm, and we refer to classifier trained in this way
as mutual information learned classifier (MILC, /milk/).

For the mutual information learning formulation in (3), we can parameterize
$Q_{Y}$ and $Q_{Y|X}$ via a group of parameters
$\theta_{Y|X}\in\mathbb{R}^{m}$, e.g., $Q_{Y}(Y;\theta_{Y|X})$ is completely
determined by $\theta_{Y|X}$. More specifically, we parameterize
$Q_{Y|X}(Y|X;\theta_{Y|X})$ using $\theta_{Y|X}$, and then calculate the
marginal estimation ${Q}_{Y}(Y;\theta_{Y|X})$ via

$\displaystyle{Q}_{Y}(Y=y;\theta_{Y|X})$
$\displaystyle:=\sum_{x\in\mathcal{S}_{x}}\hat{P}_{X}(x)Q_{Y|X}(y|x;\theta_{Y|X})$
(31)
$\displaystyle=\frac{1}{N}\sum_{(x_{i},y_{i})\in\mathcal{S}}1_{\\{y\\}}(y_{i})Q_{Y|X}(y_{i}|x;\theta_{Y|X})$
(32)

where $\mathcal{S}_{x}=\\{x_{i}\\}_{i=1}^{N}$ and $1_{A}(y)=1$ if $y$ is in
set $A$, and 0 if otherwise. Thus, the mutual information has the following
form

$\displaystyle
I(X;Y)\approx\inf_{\theta_{Y|X}}H(\hat{P}_{Y},{Q}_{Y}(Y;{\theta_{Y|X}}))-\inf_{\theta_{Y|X}}H(\hat{P}_{Y|X},Q_{Y|X}(Y|X;\theta_{Y|X})),$
(33)

which is a multi-object optimization problem [38].

An equivalent form of (33) can be a regularized form as follows

$\displaystyle\inf_{\theta_{Y|X}}\left(H(\hat{P}_{Y|X},Q_{Y|X}(Y|X;\theta_{Y|X}))+\lambda_{ent}H(\hat{P}_{Y},Q_{Y}(Y;\theta_{Y|X}))\right),$
(34)

where $\lambda_{ent}>0$ is a regularization hyperparameter. In (34), the
$H(\hat{P}_{Y|X},Q_{Y|X})$ essentially corresponds to the cross entropy loss
in multi-class classification while $H(\hat{P}_{Y},Q_{Y})$ can be treated as a
regularization term. The cross entropy term guides machine learning algorithms
to learn accurate estimation of condition entropy $H(Y|X)$, and the
regularization term encourages the model also to learn the label entropy
$H(Y)$. Intuitively, such a mutual information learning goal can guide the
model to learn more accurately the dependency between input $X$ and $Y$, thus
better generalization performance. To the best of our knowledge, the label
entropy has never been used to train machine learning systems by the
community, and we are the first to propose mutual information learning (MIL)
framework for training classifiers. Though similar ideas were proposed in
previous works, what considered previously is essentially the conditional
entropy instead of the entropy [26]. Their goal is to increase the conditional
entropy of the label when the the input is given while our formulation aims at
accurately characterizing the dependency between the input and ouput. Besides,
in previous work, the increase of conditional entropy of label is acheived by
encouraging the predicted label conditional distribution to be close to a
uniform label distribution. However, our formula encourages the model to give
predictions which characterize the mutual information well.

(a) Training/learn pipeline

(b) Inference/decision pipeline

Figure 4: Mutual information learning classifiers (MILC): $\theta^{*}_{Y|X}$
is an optimal solution to (34)

The overall DNN classifiers’ trainning or learning pipeline under the MIL
framework is presented in Figure 4(a), and the corresponding decision or
inference pipeline is presented in Figure 4(b). During the training process,
we sample a data batch from training dataset $\mathcal{S}$ in each iteration,
and then calculate the empirical marginal distributions $\hat{P}_{X}$,
$\hat{P}_{Y}$ and $\hat{P}_{Y|X}$. The inputs $\\{x_{i}\\}_{i=1}^{B}$ will be
fed to a machine learning system for it to learn the conditional distribution
$Q_{Y|X;\theta_{Y|X}}$. We then combine the $Q_{Y|X;\theta_{Y|X}}$ with
$\hat{P}_{X}$ and $\hat{P}_{Y|X}$ separately to calculate the learned marginal
distribution $Q_{Y;\theta_{Y|X}}$ and the learned conditional entropy
$\hat{H}(Y|X)$. The $Q_{Y;\theta_{Y|X}}$ is then combined with the
$\hat{P}_{Y}$ to calculate the label entropy. We finally calculate the mutual
information by subtracting conditional entropy from entropy. During inference,
we feed an input $x$ to the model to get a conditional distribution, and the
final class label prediction will be the one achieving the highest
probability.

One may want to estimate the MI via empirical distribution only, i.e.,

$\displaystyle I(X;Y)$ $\displaystyle=H(Y)-H(Y|X)$
$\displaystyle\approx\sum_{c\in[C]}\hat{P}_{Y}(Y=c)\log\left(\frac{1}{\hat{P}_{Y}(Y=c)}\right)-\sum_{i\in[N]}\hat{P}_{X}(x_{i})\times\sum_{c\in[C]}\hat{P}_{Y|X}(c|x_{i})\times\log\left(\frac{1}{\hat{P}_{Y|X}(c|x_{i})}\right),$
(35)

where

$\displaystyle\hat{P}(Y=c):=\frac{\left|\\{(x_{i},y_{i})\in\mathcal{S}:{y}_{i}=c\\}\right|}{N},\forall
c\in[C],$
$\displaystyle\hat{P}(X=x):=\frac{\left|\\{(x_{i},y_{i})\in\mathcal{S}:{x}_{i}=x\\}\right|}{N},\forall
x\in\mathcal{S}|_{x},$
$\displaystyle\hat{P}_{Y|X}(c|x_{i}):=\frac{|\\{(x,y)\in\mathcal{S}:x=x_{i},y=c\\}|}{|\\{(x,y)\in\mathcal{S}:x=x_{i}\\}|}.$

The problem is that the estimation of entropy or cross entropy from type only
can be quite inaccurate, and this is formally presented in Theorem 4.1 where
we give the error bound of estimating entropy of $Y$ via the empirical
distribution $\hat{p}_{Y}$. However, in our previous formulations, we use the
combination of the empirical distirbution and a learned distribution to avoid
this.

######  Theorem 4.1.

(Error Bound of Entropy Learning from Empirical Distribution) For two
arbitrary distributions $P_{Y}$ and $\hat{P}_{Y}$ of a discrete random
variable $Y$ over $[C]$, we have

$\displaystyle\sum_{y\in[C]}R(y)\log\left(\frac{1}{{P}_{Y}(y)}\right)\leq
H_{P_{Y}}(Y)-H_{\hat{P}_{Y}}(Y)\leq\sum_{y\in[C]}R(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right)$
(36)

where $R(y)=P_{Y}(y)-\hat{P}_{Y}(y),\forall y\in[C]$, and $H_{P_{Y}}(Y)$ is
the entropy of $Y$ calculated via $P_{Y}$. The equality holds if and only if
$P_{Y}=\hat{P}_{Y}$.

Theorem 4.1 gives a bound for the gap between entropies calculated using
different distributions, and it applies to arbitrary distributions. In the
special scenario where $P_{Y}$, and $\hat{P}_{Y}$ are the true data
distribution and the empirical distribution associated with data samples,
Theorem 4.1 actually gives error bound of estimating entropy using empirical
distribution.

We want to point out that though our formulation in (33) can be used to
estimate the mutual information because
$\inf_{\theta_{Y|X}}H(\hat{p}_{Y},\hat{Q}_{Y}(Y;{\theta_{Y|X}}))$ and
$\inf_{\theta_{Y|X}}H(\hat{p}_{Y|X},q_{Y|X}(Y|X;\theta_{Y|X}))$ can give
accurate estimate of entropy $H(Y)$ and conditional entropy $H(Y|X)$, our
primary goal is to learn classifiers with excellent generalization
performance. Besides, our Theorem 3.1 implies that our formulation can also be
used to estimate the joint entropy of the dataset $H(X,Y)$ via

$\displaystyle
H(X,Y)\approx\inf_{\theta_{X,Y}}H(\hat{P}_{X,Y},Q_{X,Y}(X,Y;\theta_{X,Y})),$
(37)

which quantifies the amount of information contained in a dataset. The
$\theta_{X,Y}$ is the model parameter. However, the joint entropy only
quantifies the information contained in the dataset, but gives no
characterization of the dependency between $X$ and $Y$, thus it may not help
with learning classifiers with good generalization performance.

##  5 Error Probability Lower Bounds via Mutual Information

In this section, we establish the error probability bound of an arbitrary
learning algorithm in terms of mutual information associated with the dataset
used to train the models. To do this, we first follow Yi et al. to model the
learning process as in Figure 5 [6, 39, 28, 29]. More specifically, we assume
there is a label distribution $P_{Y}$, and based on realizations from $P_{Y}$,
we can generate a set of observations from $p_{X}$. Given the observations, we
want to infer the label of them. By combining the ground truth labels sampled
from $P_{Y}$ and the predicted labels, we then calculate the error probability
as

$\displaystyle
P_{error}:=P_{Y,\hat{Y}}\left(\\{(Y,\hat{Y}):Y\neq\hat{Y}\\}\right).$ (38)

This learning process is consistent with practice. For example, in a dog-cat
image classification tasks, we first have the concepts of the two classes,
i.e., cat and dog. Then, we can generate observations of these
labels/concepts, i.e., images of cat and dog by taking pictures of them, or
simply drawing them. We then use these observations to train models, hoping
that they will finally be able to predict the correct labels. We want to
mention that the community has witnessed significant progress in image
generation, and it is fairly straightforward to general such dog and cat
images [40, 41, 42].

Figure 5: Information-theoretic view point of learning process.

Under this framework, we can show that the error probability associated with
the learning process as shown in Figure 5 can be bounded via mutual
information $I(X;Y)$. The results are formally shown in Theorem 5.2, and we
first present a useful lemma which will be used in Theorem 5.2.

######  Lemma 5.1.

([28]) For arbitrary $x\in[0,1]$, we have

$\displaystyle
x\log\left(\frac{1}{x}\right)+(1-x)\log\left(\frac{1}{1-x}\right)\leq
1-2(x-0.5)^{2}.$ (39)

Lemma 5.1 can be used to bound the entropy associated with a binary
distribution, and a simple visual illustration of it is presented in Figure 6
where we let $x$ be the error probability and $1-x$ be the correct probability
(or accuracy).

Figure 6: Upper bound of entropy assoicated with binary distribution: error
probability $x$ and correct probability $1-x$. The blue curve corresponds to
left hand side of (39), and the red curve corresponds to the right hand side
of (39).

######  Theorem 5.2.

(Error Probability Bound via Mutual Information) Assume that the learning
process $Y\to X\to\hat{Y}$ in Figure 5 is a Markov chain where $Y\in[C]$,
$X\in\mathbb{R}^{n}$, and $\hat{Y}\in[C]$, then for the prediction $\hat{Y}$
from an arbitrary learned model, we have

$\displaystyle\max\left(0,\frac{2+H(Y)-I(X;Y)-a}{4}\right)\leq P_{error}$ (40)

where $a:=\sqrt{(H(Y)-I(X;Y)-2)^{2}+4}$.

The proof of Theorem 5.2 can be found in the appendix. From (93) in the proof
of Theorem 5.2, we can see that $P_{error}\geq 1-\frac{1}{H(Y)-I(X;Y)}$, and
the $P_{error}$ lower bound will decrease when $I(X;Y)$ increases. The Theorem
also implies that $I(X;Y)\geq H(Y)-\frac{H(P_{error})}{1-P_{error}}$, which
means the mutual information between $X,Y$ should be at least
$H(Y)-\frac{H(P_{error})}{1-P_{error}}$ so that we can achieve an error
probability $P_{error}$. These are consistent with our intuitions. For
example, when the dependence or MI between the observation $X$ and the label
$Y$ gets weak, it will be more challenging to infer $Y$ from $X$, thus a
larger error probability can occur. We also want to mention that our bound is
tighter than the Fano’s inequality because Fano’s inequality relaxed
$H(Y|\hat{Y},E=1)$ to $\log(C-1)$, while we relax $H(Y|\hat{Y},E=1)$ to
$H(Y|\hat{Y})$ in (88) [32].

In Figure 7, we give illustrations of the relation between the error
probability lower bound and the mutual information for both a balanced
underlying data distribution and an unbalanced data distribution. For the
balanced data distribution, we assume uniform marginal distribution for the
label, while for the unbalanced data distribution, we assume one of the
classes takes probability mass $1-\delta$ and all the other classes share the
probability mass $\delta$ evenly. From the figure, we can see that when the
mutual information decreases, the error probability will increase, which is
consistent with our intuitions. For example, for the case with 100 classes, if
the label and the input has zero mutual information, i.e., no dependency
between them, we can only draw a random guess and get 0.99 error probability
while the lower bound from Theorem 5.2 is about 0.9. Figure 7 also shows that
under the same setup, the error probability associated with balanced dataset
will be larger than that associated with imbalanced dataset. For example, when
the mutual information is zero, the $P_{error}$ for balanced dataset is above
0.8 while the $P_{error}$ associated with imbalanced dataset is below 0.8.
This is also intuitive since for an imbalanced dataset, we can set the label
of the class which contains the most number of examples to all the examples.
Since more samples have the correct labels, the error probability cannot be
too big. However, for balanced dataset, since all classes have the same number
of examples, we cannot get a too small error probability.

(a) Balanced data distribution

(b) Unbalanced data distribution

Figure 7: Error probability lower bound and mutual information: : uniform
distirbution of labels is assumed for the balanced data distribution. For
unbalanced data disrtribution, one class takes probability mass 0.7, while the
other classes share the 0.3 evenly.

##  6 Guarantees for Mutual Information Learning

We have shown that the mutual information can be used to bound the error
probability in Section 5. In this section, we show that the ground truth
mutual information (MI) $I(X;Y)$ can be accurately learned from
$\mathcal{S}\subset\mathbb{R}^{n}\times[C]$ under certain conditions, and we
give the sample complexity for achieving this goal.

###  6.1 Weight Sharing for Learning Mutual Information via Single Neural
Network

From Theorem 3.1, we know that

$\displaystyle H(Y)\leq\inf_{Q_{Y}}H(P_{Y},Q_{Y}),$ (41) $\displaystyle
H(Y|X)\leq\inf_{Q_{Y|X}}H(P_{Y|X},Q_{Y|X}),$ (42)

where the equality holds if and only if $Q_{Y}=P_{Y}$ and $Q_{Y|X}=P_{Y|X}$.
This allows us to estimate the mutual information defined in (1) via solving

$\displaystyle\inf_{Q_{Y}}H(P_{Y},Q_{Y})-\inf_{Q_{Y|X}}H(P_{Y|X},Q_{Y|X}),$
(43)

and the ground truth MI is

$\displaystyle I(X;Y)$ $\displaystyle=H(P_{Y},P_{Y})-H(P_{Y|X},P_{Y|X})$
$\displaystyle=\mathbb{E}_{P_{Y}}[-\log(P_{Y})]-\mathbb{E}_{P_{X,Y}}[-\log(P_{Y|X})]$
$\displaystyle=\sum_{y\in[C]}-P_{Y}(y)\log(P_{Y}(y))-\int_{\mathbb{R}^{n}}p_{X}(x)\sum_{y\in[C]}-P_{Y|X}(y|x)\log(P_{Y|X}(y|x))dx$
(44)

In (43), we use two sets of parameters $\theta_{Y|X}$ and $\theta_{Y}$ to
learn the conditional entropy and the entropy separately. Under the deep
learning paradigma, two different neural networks can be used to acheive this
in practice.

Following the weight sharing idea in deep learning community for reducing
computational cost, we can use a single neural network with a single set of
parameter $\theta\in\mathbb{R}^{m}$ to parameterize both $Q_{Y}$ and
$Q_{Y|X}$. More specifically, we use a neural network with parameter $\theta$
to approximate the conditional distribution, i.e., $Q_{Y|X}(Y|X;\theta)$ , and
define $Q_{Y}(Y;\theta)$ as

$\displaystyle
Q_{Y}(y|\theta):=\int_{\mathbb{R}^{n}}p_{X}(x)Q_{Y|X}(y|x;\theta)dx,\forall
y\in[C].$ (45)

When the $p_{X}$ is not available, we can define $Q_{Y}(\cdot|\theta)$ by the
empirical distribution $\hat{P}_{X}$, i.e.,

$\displaystyle
Q_{Y}(y|\theta):=\sum_{x\in\mathcal{S}_{x}}\hat{P}(x)Q_{Y|X}(y|x;\theta),\forall
y\in[C].$ (46)

In the ideal situation as we pointed out previously, we find an optimal
$\theta^{*}$ such that $Q_{Y}(Y;\theta^{*})=P_{Y}(Y)$ and
$Q_{Y|X}(Y|X;\theta^{*})=P_{Y|X}(Y|X)$.

###  6.2 Parameterization and Empirical Minimization for Mutual Information
Learned Classifiers

To ensure efficiency for finding an optimal $\theta^{*}$ in practice, we
search for the optimum only from a domain $\Theta\subset\mathbb{R}^{m}$
instead of searching it in $\mathbb{R}^{m}$. Thus, we calulate the MI by
solving

$\displaystyle I_{\Theta}$
$\displaystyle:=\inf_{\theta\in\Theta}H(P_{Y},Q_{Y}(Y;\theta))-\inf_{\theta\in\Theta}H(P_{Y|X},Q_{Y|X}(Y|X;\theta))$
$\displaystyle=\inf_{\theta\in\Theta}\mathbb{E}_{P_{Y}}[-\log(Q_{Y}(Y;\theta))]-\inf_{\theta\in\Theta}\mathbb{E}_{p_{X,Y}}[-\log(Q_{Y|X}(Y|X;\theta))]$
$\displaystyle=\inf_{\theta\in\Theta}\mathbb{E}_{P_{Y}}\left[-\log\left(\int_{\mathbb{R}^{n}}p_{X}(x)Q_{Y|X}(Y|x;\theta)dx\right)\right]-\inf_{\theta\in\Theta}\mathbb{E}_{p_{X,Y}}[-\log(Q_{Y|X}(Y|X;\theta))],$
(47)

or

$\displaystyle\theta^{*}:=\arg\min_{\theta\in\Theta}(H(P_{Y},Q_{Y}(Y;\theta)),H(P_{Y|X},Q_{Y|X}(Y|X;\theta))),$
(48)

where $\theta^{*}$ is an optimal solution to a multi-objective function [38].
The price we pay for such efficiency from constraining $\theta$ is the
introduction of model approximation error, i.e., the $\theta$ that corresponds
to the ground truth MI can be out of $\Theta$.

Since the ground truth distribution is not available in practice, we seek to
solve an empirical form of (6.2) using sample set
$\mathcal{S}:=\\{(x_{i},y_{i})\\}_{i=1}^{N}$ from the distribution $p_{X,Y}$.
This motivates us to solve

$\displaystyle I_{\Theta}^{(N)}$
$\displaystyle:=\inf_{\theta\in\Theta}\mathbb{E}_{\hat{P}_{Y}}[-\log(Q_{Y}(\theta))]-\inf_{\theta\in\Theta}\mathbb{E}_{\hat{p}_{X,Y}}\left[-\log(Q_{Y|X}(\theta))\right]$
$\displaystyle=\inf_{\theta\in\Theta}\sum_{y\in[C]}-\hat{P}(y)\log\left(\sum_{i=1}^{N}\hat{P}(x_{i})Q_{Y|X}(y|x_{i};\theta)\right)-\inf_{\theta\in\Theta}\sum_{i=1}^{N}\hat{P}_{X}(x_{i})\sum_{y\in[C]}-\hat{P}_{Y|X}(y|x_{i})\log(Q_{Y|X}(y|x_{i};\theta))$
$\displaystyle:=\inf_{\theta\in\Theta}\sum_{y\in[C]}-\hat{P}(y)\log\left(\frac{1}{N}\sum_{i=1}^{N}Q_{Y|X}(y|x_{i};\theta)\right)-\inf_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}\sum_{y\in[C]}-\hat{P}_{Y|X}(y|x_{i})\log(Q_{Y|X}(y|x_{i};\theta)),$
(49)

where we used that assumption that $\|x_{i}-x_{j}\|>0,\forall i\neq j$, i.e.,
uniform empirical distribution with $\hat{P}(x_{i})=\frac{1}{N}$. When the
empirical conditional distribution $\hat{P}_{Y|X}$ uses one-hot
representation, the (6.2) can be further simplified. The empirical estimation
error can occur due to the fact that the sample set $\mathcal{S}$ cannot
completely characterize the data distribution $p_{X,Y}$.

Similarly, when we use two separate neural networks with two sets of
parameters $\theta\in\mathbb{R}^{m},\gamma\in\mathbb{R}^{m^{\prime}}$ to
parameterize $Q_{Y}$ and $Q_{Y|X}$, respectively, i.e., $Q_{Y}(Y;\gamma)$ and
$Q_{Y|X}(Y|X;\theta)$, we can similarly define

$\displaystyle I_{\Gamma,\Theta}$
$\displaystyle:=\inf_{\gamma\in\Gamma}H(P_{Y},Q_{Y}(Y;\gamma))-\inf_{\theta\in\Theta}H(P_{Y|X},Q_{Y|X}(Y|X;\theta))$
$\displaystyle=\inf_{\gamma\in\Gamma}\mathbb{E}_{P_{Y}}[-\log(Q_{Y}(Y;\gamma))]-\inf_{\theta\in\Theta}\mathbb{E}_{p_{X,Y}}[-\log(Q_{Y|X}(Y|X;\theta))]$
$\displaystyle=\inf_{\gamma\in\Gamma}\sum_{y\in[C]}-P_{Y}(y)\log\left(Q_{Y}(y;\gamma)\right)-\inf_{\theta\in\Theta}\int_{\mathbb{R}^{n}}p_{X}(x)\sum_{y\in[C]}-P_{Y|X}(y|x)\log(Q_{Y|X}(y|x;\theta))dx,$
(50)

where $\Theta\subset\mathbb{R}^{m}$ and
$\Gamma\subset\mathbb{R}^{m^{\prime}}$. An empirical estimation form of
$I_{\Theta,\Gamma}$ can be

$\displaystyle I_{\Gamma,\Theta}^{(N)}$
$\displaystyle:=\inf_{\gamma\in\Gamma}\mathbb{E}_{\hat{P}_{Y}}[-\log(Q_{Y}(\gamma))]-\inf_{\theta\in\Theta}\mathbb{E}_{\hat{p}_{X,Y}}\left[-\log(Q_{Y|X}(\theta))\right]$
$\displaystyle:=\inf_{\gamma\in\Gamma}\sum_{y\in[C]}-\hat{P}(y)\log\left(Q_{Y}(y;\gamma)\right)-\inf_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}\sum_{y\in[C]}-\hat{P}_{Y|X}(y|x_{i})\log(Q_{Y|X}(y|x_{i};\theta)).$
(51)

As we can see from the above, the error for learning MI comes mainly from two
sources, i.e., the model approximation error and empirical estimation error.
The model approximation error can be easily bounded via the universal
approximating properties of neural networks [34]. In this paper, we focus on
the emprical estimation error. In Theorem 6.6, we give the sample complexity
for bounding the empirical estimation error by using concentration of measure
arguments.

###  6.3 Empirical Estimation Guarantees

Before we give the guarantees for accurate learning of MI from empirical
sample set $\mathcal{S}$, we introduce some useful technical lemmas which will
be used in later sections.

######  Lemma 6.1.

(Theorem 2.8 in [33]) Let $X_{1},\cdots,X_{n}$ be independent random variables
such that $X_{i}$ takes its values in $[a_{i},b_{i}]$ almost surely for all
$i\leq n$. Let $S=\sum_{i=1}^{n}(X_{i}-\mathbb{E}[X_{i}])$. Then, for every
$t>0$,

$\displaystyle P(\\{X_{1},\cdots,X_{n}:S\geq
t\\})\leq\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$
(52)

Lemma 6.1 shows that for a sequence of bounded I.I.D. random variables, their
empirical mean has a small probability to be much greater than the
distribution mean. In Corollary 1, we show that the empirical mean can neither
be much greater nor much smaller than the distribution mean.

######  Corollary 1.

(Double sided Hoeffiding inequality) Let $X_{1},\cdots,X_{n}$ be independent
random variables such that $X_{i}$ takes its values in $[a_{i},b_{i}]$ almost
surely for all $i\leq n$. Let $S=\sum_{i=1}^{n}(X_{i}-\mathbb{E}[X_{i}])$.
Then, for every $t>0$,

$\displaystyle P\left(\\{X_{1},\cdots,X_{n}:|S|\geq t\\}\right)\leq
2\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$ (53)

Corollary 1 generalizes the Hoeffiding’ inequality from single-sided to
double-sided. With Lemma 6.1 and Corollary 1, we can derive the concentration
inequalities for the contional cross entropy random variable and the marginal
distribution random variable as in Lemma 6.2.

######  Lemma 6.2.

(Concentration Inequality for Conditional Cross Entropy) We consider a set of
random variable pairs $\mathcal{S}:\\{(X_{i},Y_{i})\\}_{i=1}^{N}$ with each
$(X_{i},Y_{i})$ I.I.D. according to $p_{X,Y}$ in $\mathbb{R}^{n}\times[C]$,
and define

$\displaystyle
D:=\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(Y|X;\theta))\right],$
(54)

where $\theta\in\Theta_{c}$, $\Theta_{c}$ is a countable set, and
$Q_{Y|X}(Y|X;\theta)$ is a function of $X,Y$ with parameters $\theta$. Assume
$Q_{Y|X}(y|x;\theta)\geq P^{\\#},\forall x,y,\theta$ where $P^{\\#}>0$ is a
constant. Then, we have

$\displaystyle P(\\{\mathcal{S}:\max_{\theta\in\Theta_{c}}|D|\geq t\\})\leq
2|\Theta_{c}|\exp\left(-\frac{2Nt^{2}}{(\log(P^{\\#}))^{2}}\right)$ (55)

where $t>0$ is a constant.

Theorem 6.2 shows that when we randomly sample data points $(X_{i},Y_{i})$
from $p_{X,Y}$ to form a dataset $\mathcal{S}$, then with high probability
over the dataset $\mathcal{S}$, the empirical mean
$\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta))$ will be
concentrated around the distribution mean
$\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]$. When $Q_{Y|X}$
becomes the $P_{Y|X}$, the negative of the distribution mean is essentially
the conditional entropy $H(Y|X)$, and Theorem 6.2 shows that the empirical
estimation will be close the the truth conditional entropy for large $N$.
Simlarly, we can derive the concentration inequality for cross entropy, and
the results are presented in Lemma 6.3.

######  Lemma 6.3.

(Concentration Inequality for Cross Entropy) We consider a set of random
variable pairs $\mathcal{S}:\\{(Y_{i})\\}_{i=1}^{N}$ with each $Y_{i}$
independently and identically distributed according to $p_{Y}$ in
$\mathbb{R}^{n}\times[C]$, and define

$\displaystyle
D:=\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma))-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\cdot;\gamma))\right],$
(56)

where $\gamma\in\Gamma_{c}$, $\Gamma_{c}$ is a countable set, and
$Q_{Y}(Y;\gamma)$ is a function of $Y$ with parameters $\gamma$. Assume
$Q_{Y}(y;\gamma)\geq P^{\\#},\forall y,\gamma$ where $P^{\\#}>0$ is a
constant. Then, we have

$\displaystyle P(\\{\mathcal{S}:\max_{\theta\in\Theta_{c}}|D|\geq t\\})\leq
2|\Gamma_{c}|\exp\left(-\frac{2Nt^{2}}{(\log(P^{\\#}))^{2}}\right)$ (57)

where $t>0$ is a constant.

###### Proof.

(of Lemma 6.3) We can follow similar arguments as in the proof of Lemma 6.2 to
get Lemma 6.3, and we leave it out here.

∎

To get the sample complexity results, we need two more technical lemma as
presented in Lemma 6.4 which gives upper bound of the distance between two
infimum over the same domain, and Lemma 6.5 which gives the covering number
for constructing a set of balls for covering a uncountable set. Lemma 6.5 will
be used to construct countable set for approximating a noncountable set.

######  Lemma 6.4.

(Upper Bound of Minimums Difference) For two arbitrary functions $f(x)$ and
$g(x)$ defined over the same domain $\mathcal{X}$, we have

$\displaystyle\left|\inf_{x\in\mathcal{X}}f(x)-\inf_{x\in\mathcal{X}}g(x)\right|\leq\sup_{x\in\mathcal{X}}|f(x)-g(x)|.$
(58)

###### Proof.

(of Lemma 6.4) Assume $x_{f}:=\arg\inf_{x\in\mathcal{X}}f(x)$ and
$x_{g}:=\arg\inf_{x\in\mathcal{X}}g(x)$, then the Lemma 6.4 is obvious since
$|f(x_{f})-g(x_{g})|\leq\sup_{x\in\mathcal{X}}|f(x)-g(x)|.$ ∎

######  Lemma 6.5.

(Covering Number of Subspace in $\mathbb{R}^{m}$, Example 27.1 in [14])
Suppose that $A\subset\mathbb{R}^{m}$, let $c=\max_{a\in A}\|a\|$, and assume
that $A$ lies in a $d$-dimensional subspace of $\mathbb{R}^{m}$. Then,
$N(r,A)\leq(2c\sqrt{d}/r)^{d}$.

We now derive the sample complexity for achieving an accurate estimate of
$I_{\Gamma,\Theta}$ in (6.2) by solving (6.2) with the samples in the dataset
$\mathcal{S}:\\{(X_{i},Y_{i})\\}_{i=1}^{N}$ independently and identically
distributed (IID) and follow $p_{X,Y}$.

######  Theorem 6.6.

(Sample Complexity for Estimation Error Bound) We consider a joint
distirbution $p_{X,Y}$ in $\mathbb{R}^{n}\times[C]$ where $X\in\mathbb{R}^{n}$
is a continuous random vector, and $Y\in[C]$ is a discrete random variable. We
define $I_{\Gamma,\Theta}$ associated with $p_{X,Y}$ similar to (6.2), i.e.,

$\displaystyle
I_{\Gamma,\Theta}=\inf_{\gamma\in\Gamma}\mathbb{E}_{P_{Y}}[-\log\left(Q_{Y}(Y;\gamma)\right)]-\inf_{\theta\in\Theta}\mathbb{E}_{p_{X,Y}}[-\log(Q_{Y|X}(Y|X;\theta))],$
(59)

where $Q_{Y|X}(Y|X;\theta)$ is a neural network with parameters
$\theta\in\Theta\subset\mathbb{R}^{m}$ which predicts the conditional
probability of $Y$ conditioning on $X$, and $Q_{Y}(Y;\gamma)$ is another
neural network with parameters $\gamma\in\Gamma\subset\mathbb{R}^{m^{\prime}}$
which predicts the marginal probability of $Y$. Assume that we are given a set
of random examples $\mathcal{S}:\\{(X_{i},Y_{i})\\}_{i=1}^{N}$ such that
$(X_{i},Y_{i}),i=1\cdots,N$ are I.I.D. and follow $p_{X,Y}$. Define
$I_{\Gamma,\Theta}^{(N)}$ similar to that in (6.2), i.e.,

$\displaystyle
I_{\Gamma,\Theta}^{(N)}=\inf_{\gamma\in\Gamma}\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y}(Y_{i};\gamma))-\inf_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y|X}(Y_{i}|X_{i};\theta)).$
(60)

Assume both $\Theta$ and $\Gamma$ are compact sets, and bounded, i.e.,
$\|\theta\|\leq M_{\theta}$ and $\|\gamma\|\leq M_{\gamma}$ where
$M_{\theta}>0,M_{\gamma}>0$ are constants. We assume both
$Q_{Y}(\cdot;\gamma)$ and $Q_{Y|X}(\cdot;\theta)$ are lower bounded by
$P^{\\#}$, and they are Lipschitz continuous with respect to $\theta$ for all
$y\in[C]$ and all $(x,y)\in\mathbb{R}^{n}\times[C]$, and the Lipschitz
constants are $L_{\gamma}>0$ and $L_{\theta}>0$, respectively. Then, when
$N\geq\frac{2\log\left(\frac{1}{\epsilon}\right)\left(P^{\\#}\log(P^{\\#})\right)^{2}}{\left(\delta
P^{\\#}-4^{\frac{1+m^{\prime}}{m^{\prime}}}L_{\gamma}M_{\gamma}\sqrt{m^{\prime}}-4^{\frac{1+m}{m}}L_{\theta}M_{\theta}\sqrt{m}\right)^{2}}$,
we have

$\displaystyle
P\left(\left\\{\mathcal{S}:\left|I_{\Theta}^{(N)}-I_{\Theta}\right|\leq\delta\right\\}\right)\geq
1-\epsilon.$ (61)

Theorem 6.6 essentially gives the sample complexity for learning mutual
information $I_{\Gamma,\Theta}$ from empirical samples via
$I_{\Gamma,\Theta}^{(N)}$ to acheive arbitrary precision $\delta$ with
arbitrary probability over a dataset
$\mathcal{S}:\\{(X_{i},Y_{i})\\}_{i=1}^{N}$ where $(X_{i},Y_{i})$ are I.I.D.
and follow $p_{X,Y}$. The above sample complexity is also consistent with our
intuitions, e.g., if we want to achieve higher precision (smaller $\delta$)
with higher probability (smaller $\epsilon$), we need higher sample complexity
(lower bound of $N$ will increase). We want to point out that Theorem 6.6
gives the sample complexity for mutual information learning using two neural
networks without weight sharing, similar sample complexity bounds can also be
established for the case where a single neural network is used, and we leave
it for future work.

top-1 accuracy | celLoss | celLoss$+$LSR | celLoss$+$CP | celLoss$+$LC | milLoss (ours)
---|---|---|---|---|---
MLP | $0.934\pm 0.000$ | 0.934$\pm$0.001 | 0.930$\pm$0.002 | 0.932$\pm$0.000 | $0.945\pm 0.001$
CNN | $0.981\pm 0.000$ | 0.982$\pm$0.001 | 0.980$\pm$0.000 | 0.980$\pm$0.001 | $0.984\pm 0.001$
Table 2: Top-1 accuracy on MNIST dataset associated with different models which are trained with different loss objective function. top-1 accuracy | celLoss | celLoss$+$LSR | celLoss$+$CP | celLoss$+$LC | milLoss (ours)
---|---|---|---|---|---
GoogLeNet | $0.803\pm 0.006$ | 0.766$\pm$0.004 | 0.784$\pm$0.006 | 0.791$\pm$0.002 | $0.866\pm 0.000$
ResNet-18 | $0.732\pm 0.002$ | 0.679$\pm$0.001 | 0.703$\pm$0.006 | 0.726$\pm$0.005 | $0.832\pm 0.004$
MobileNetV2 | 0.676$\pm$0.007 | 0.647$\pm$0.005 | 0.660$\pm$0.008 | 0.677$\pm$0.004 | 0.762$\pm$0.006
EfficientNet-B0 | 0.524$\pm$0.013 | 0.510$\pm$0.006 | 0.503$\pm$0.008 | 0.524$\pm$0.009 | 0.682$\pm$0.006
ShuffleNetV2 | 0.604$\pm$0.003 | 0.554$\pm$0.005 | 0.578$\pm$0.005 | 0.600$\pm$0.004 | 0.677$\pm$0.003
Table 3: Top-1 accuracy on CIFAR-10 dataset associated with different models which are trained with different loss objective function. top-1 (top-5) accuracy | celLoss |  celLoss$+$LSR |  celLoss$+$CP |  celLoss$+$LC | milLoss (ours)
---|---|---|---|---|---
DenseNet-121 | 0.502 (0.781) | 0.497 (0.766) | 0.485 (0.766) | 0.509 (0.788) | 0.627 (0.869)
Inception-Resnet-V2 | 0.488 (0.771) | 0.451 (0.715) | 0.434 (0.711) | 0.486 (0.760) | 0.554 (0.824)
Inception-V3 | 0.503 (0.770) | 0.472 (0.735) | 0.484 (0.749) | 0.510 (0.769) | 0.624 (0.859)
PreAct-Resnet-18 | 0.382 (0.684) | 0.383 (0.700) | 0.377 (0.693) | 0.367 (0.688) | 0.480 (0.766)
RreAct-Resnet-101 | 0.404 (0.689) | 0.385 (0.640) | 0.386 (0.683) | 0.404 (0.700) | 0.490 (0.766)
ResNet-34 | 0.408 (0.701) | 0.405 (0.659) | 0.400 (0.683) | 0.412 (0.697) | 0.520 (0.790)
ResNet-50 | 0.365 (0.644) | 0.357 (0.611) | 0.349 (0.632) | 0.359 (0.642) | 0.492 (0.769)
VGG-16 | 0.430 (0.699) | 0.400 (0.663) | 0.405 (0.6828) | 0.420 (0.694) | 0.524 (0.780)
Table 4: Top-1 and top-5 accuracy on CIFAR-100 dataset associated with
different models which are trained with different loss objective function.

##  7 Mutual Information and Error Probability Bound of Binary Classification
Data Model in $\mathbb{R}^{n}$

In this section, we derive the mutual information bounds for a binary
classification data model $P_{X,Y}$ in $\mathbb{R}^{n}\times\\{-1,1\\}$. In
the data generation process, we first sample a label $y\in\\{-1,1\\}$, and
then a corresponding feature $x$ from a Gaussian distribution. We model the
feature as a Gaussian random vector $X$ with sample space $\mathbb{R}^{n}$,
i.e.,

$\displaystyle P(Y=-1)=q,P(Y=1)=1-q,$ $\displaystyle
p(X=x|y)=\frac{1}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-y\mu)^{T}\Sigma^{-1}(x-y\mu)}{2}\right),$
(62)

where $\mu\in\mathbb{R}^{n}$ is a mean vector, and
$\Sigma\in\mathbb{R}^{n\times n}$ is a positive semidefinite matrix. In this
data model, we can derive lower and upper bounds of the mutual information
$I(X;Y)$, and the results are presented in Theorem 7.2. Before getting to
Theorem 7.2, we first derive the expectation of quadratic forms of Gaussian
random vector in Lemma 7.1, which will be used for deriving the bounds of
mutual information in the data model (7).

######  Lemma 7.1.

(Expectation of Quadratic Form of Gaussian Random Vector) For a Gaussian
random vector $X\in\mathbb{R}^{n}$ following $\mathcal{N}(\mu,\Sigma)$, we
have

$\displaystyle\mathbb{E}_{X}\left[X^{T}AX\right]=\rm{Tr}(A\Sigma)+\mu^{T}\Sigma^{-1}\mu,$
$\displaystyle\mathbb{E}_{X}\left[(X-\mu)^{T}A(X-\mu)\right]=\rm{Tr}(A\Sigma),$
$\displaystyle\mathbb{E}_{X}\left[(X+\mu)^{T}A(X+\mu)\right]=\rm{Tr}(A\Sigma)+4\mu^{T}\Sigma\mu,$
(63)

where $A\in\mathbb{R}^{n\times n}$ is a square matrix.

From Lemma 7.1, we know that when $A=\Sigma^{-1}$, we have

$\displaystyle\mathbb{E}_{X}\left[X^{T}\Sigma^{-1}X\right]=n+\mu^{T}\Sigma^{-1}\mu,$
(64)
$\displaystyle\mathbb{E}_{X}\left[(X-\mu)^{T}\Sigma^{-1}(X-\mu)\right]=n,$
(65)
$\displaystyle\mathbb{E}_{X}\left[(X+\mu)^{T}\Sigma^{-1}(X+\mu)\right]=n+4\mu^{T}\Sigma\mu.$
(66)

When $X\sim\mathcal{N}(-\mu,\Sigma)$,
$\mathbb{E}_{X}[X^{T}AX]=\rm{Tr}(A\Sigma)+\mu^{T}A\mu$. When
$X\sim\mathcal{N}(-\mu,\Sigma)$,
$\mathbb{E}_{X}[(X-\mu)^{T}A(X-\mu)]=\rm{Tr}(A\Sigma)+4\mu^{T}\Sigma\mu$.

######  Theorem 7.2.

(Mutual Information of Binary Classification Dataset Model) For the data model
with distribution defined in (7), we have the mutual information $I(X;Y)$
satisfying

$\displaystyle 2\min(q,1-q)\mu^{T}\Sigma^{-1}\mu\leq I(X;Y)\leq
4q(1-q)\mu^{T}\Sigma^{-1}\mu.$ (67)

From Theorem 7.2, we can see that for the mutual information $I(X;Y)$, the
maximum upper bound is acheived when $q=0.5$. For a simplified case in
$\mathbb{R}$ with $\mu=1$ and variance $\sigma^{2}=1$, when the variance
becomes bigger, the two distributions $\mathcal{N}(1,\sigma^{2})$ and
$\mathcal{N}(-1,\sigma^{2})$ get closer to each other. Thus, conditioning on
$X$ can give very little information about $Y$, making it difficult to
differentiate the two class labels. In Figure 8, we give illustrations for
this phenomenon. As we can see in Figure 8, as the $\sigma^{2}$ increases from
1 to 100, the two conditional distributions $\mathcal{N}(1,\sigma^{2})$ and
$\mathcal{N}(-1,\sigma^{2})$ get closer to each other. This results in that
less information is revealed about $Y$ when we condition on $X$ with larger
variance $\sigma^{2}$. We also give illustrations of the mutual information
bounds for the data distribution in $\mathbb{R}$ in Figure 9. Theorem 7.2 can
be easily generalized to multi-class classification in $\mathbb{R}^{n}$, and
we leave this for future work.

(a) Variance $\sigma^{2}=1$

(b) Variance $\sigma^{2}=100$

Figure 8: Conditional distribution $p_{X|Y}$ with different variance
$\sigma^{2}$.

(a) $q=0.4$

(b) $\sigma^{2}=1$

Figure 9: Mutual information bounds of binary classification data model in
(7).

Based on Theorem 4.1 and 7.2, we derive a error probability lower bound for
the binary classification data model (7) in Corollary 2.

(a) celLoss

(b) milLoss

(c) milLoss

(d) milLoss

(e) Error rates

Figure 10: GoogLeNet on CIFAR-10. 10(a): error rate and loss during training
and test at different epochs. 10(b): loss during training and testing at
different epochs. 10(c): error rate, mutual information, label conditional
entropy, and label entropy during test at different epochs. 10(d): mutual
information and error rate during training and testing at different epoch.
10(e): testing error rate curves associated with different loss functions.

######  Corollary 2.

For the data distribution defined in (7), we assume the $Y\to X\to\hat{Y}$
forms a Markov chain where $\hat{Y}$ is the prediction from a classifier, and
we follow the learning process in Figure 5 to learn the classifier. Then, the
error probability for an arbitrary classifier must satisfy

$\displaystyle\max\left(0,\frac{2+H(Y)-4q(1-q)\mu^{T}\Sigma^{-1}\mu-a}{4}\right)\leq
P_{error},$

where $a:=\sqrt{(H(Y)-I(X;Y)-2)^{2}+4}$.

We can simply plug in the bounds of MI from Theorem 7.2 to Theorem 4.1 to get
Corollary 2. This is also intuitive. For example, when we consider the model
in $\mathbb{R}$ with mean $\mu\in\mathbb{R}$ and $\sigma^{2}\in[0,+\infty)$,
we have
$\max\left(0,\frac{2+H(Y)-4q(1-q)\mu^{T}\Sigma^{-1}\mu-a}{4}\right)\leq
P_{error}$. When we increase $\mu$ (the distributions from two classes become
farther from each other) and decrease $\sigma^{2}$ (the distributions from two
classes become more concentrated), we are more likely to classify them
correctly, thus a lower error probability. We also want to mention that the
results from Theorem 4.1 applies to arbitrary data distribution and arbitrary
learning algorithms, but Corollary 2 only applies for the binary
classification data model in (7) with arbitrary learning algorithms.

(a) celLoss

(b) milLoss

(c) milLoss

(d) milLoss

(e) Error rates

Figure 11: ResNet18 on CIFAR-10. 11(a): error rate and loss during training
and test at different epochs. 11(b): loss during training and testing at
different epochs. 11(c): error rate, mutual information, label conditional
entropy, and label entropy during test at different epochs. 11(d): mutual
information and error rate during training and testing at different epoch.
11(e): testing error rate curves associated with different loss functions.

##  8 Experimental Results

In this section, we present experimental results from multi-class
classification on the MNIST, CIFAR-10 , and CIFAR-100 to validate our theory
[9]. All our experiments are conducted on a Windows machine with Intel
Core(TM) i9 CPU @ 3.7GHz, 64Gb RAM, and 1 NVIDIA RTX 3090 GPU card.

Implementations and Configurations of Baseline Models The MNIST classification
task is in $[0,255]^{784}\times\\{0,1,\cdots,9\\}$, and our goal is to
classify a given hand-written digital image into one of the 10 classes. The
MNIST dataset has 60,000 examples for training, and another 10,000 examles for
testing. We use both a multiple layer perceptron (MLP) and a convolutional
neural network (CNN) to train two different classifiers by using the
regularized form of the mutual information learning loss in (34), the
conditional entropy learning loss in 13, and also its regularized forms as
discussed in previous sections, i.e., celLoss with label smoothing
regularization (LSR), celLoss with confidence penalty regularization (CP),
celLoss with label correction regularization (LC) [11, 36, 31]. The
regularization parameter $\lambda_{ent}$ is set to be $1e5$. The MLP is a
3-layer fully connected neural network with 64, 64, and 10 neurons in each
layer. All the layers except the final layer use a relu activation function.
The CNN is a 4-layer neural network with 2 convolutional layers followed by 2
fully connected layers. The first convolutional layer has 10 kernels of size
$5\times 5$, and the second convolutional layer has 20 kernels of size
$5\times 5$. A maxpooling layer with stride 2 is applied after each
convolutional layer. The two fully connected layers have 50 and 10 neurons,
respectively, and the first fully connected layer uses relu activation
function. We use SGD optimizer with a constant learning rate 1e-3 and a
momentum 0.9, and we do not use weight decay. During training, we use a batch
size of 512, and no data augmentation is used. When the classifiers are
trained with milLoss, the regularization parameter $\lambda_{ent}=50$. Each
model is trained for 77 epochs.

(a) celLoss

(b) milLoss

(c) milLoss

(d) milLoss

(e) Error rates

Figure 12: CNN on MNIST. 12(a): error rate and loss during training and test
at different epochs. 12(b): loss during training and testing at different
epochs. 12(c): error rate, mutual information, label conditional entropy, and
label entropy during test at different epochs. 12(d): mutual information and
error rate during training and testing at different epoch. 12(e): testing
error rate curve associated with different loss function.

Similarly, the CIFAR-10 classification task is in
$[0,255]^{3072}\times\\{0,1,\cdots,9\\}$, and we want to assign each image a
label. The dataset has 50,000 images for training and another 10,000 images
for testing. We use the ResNet-18, GoogLeNet, MobileNetV2, EfficientNetB0,
ResNeXt29_2x64d, and ShuffleNetV2 [9, 11, 43, 44, 45, 46] to train classifiers
by the conditional entropy learning loss minimization and the mutual
information learning loss minimization, respectively. We use SGD optimizer
with a constant learning rate 1e-3 and a momentum 0.9. The batch size is set
to be 256. The $\lambda_{ent}$ takes value 5e1 when the mutual information
learning loss is used to train the models. Each model is trained for 100
epochs.

(a) celLoss

(b) milLoss

(c) milLoss

(d) milLoss

(e) Error rates

Figure 13: Multiple layer perceptron on MNIST. 13(a): error rate and loss
during training and test at different epochs. 13(b): loss during training and
testing at different epochs. 13(c): error rate, mutual information, label
conditional entropy, and label entropy during test at different epochs. 13(d):
mutual information and error rate during training and testing at different
epoch. 13(e): testing error rate curves associated with different loss
functions.

The CIFAR-100 dataset is similar to the CIFAR-10 dataset except that we have
totally $C=100$ classes. We use DenseNet-121, Inception-ResNet-V2,
Inception-V3, PreAct-ResNet-18, PreAct-ResNet-101, ResNet-34, ResNet-50,
VGG-16 [47, 48, 49, 50, 9]. The label entropy regularization (LER) parameter
$\lambda_{ent}$ associated with the mutual information learning is set to be
1e1. The batch size is fixed at 256. Each model is trained for 200 epochs. For
each model under each setup for MNIST, CIFAR-10, and CIFAR-100, the
regularization parameter $\epsilon$ associated with the LSR, CP, and LC is
fixed at 0.1 [36]. We do not use any data augmentations, nor do we use the
weight decays for the baseline models. Instead, we perform ablation studies
over these training techniques under the mutual information learning
framework. For MNIST and CIFAR-10, we conduct 3 trials for each model, and the
reported results are averaged over the 3 trial. However, for CIFAR-100, we
conduct single trial for each model as we do not see much variations in the
results across differential trials for MNIST and CIFAR-10 datasets.

Classification Performance The first set of experimental results associated
with the baseline models for MNIST, CIFAR-10, and CIFAR-100 datasets are
presented in Table 2, 3 and 4 where we present the testing data accuracy. From
the results, we can see the proposed mutual information learning loss
(milLoss) in (33) achieved improvements of large margin when compared with the
conditional entropy learning loss (celLoss) and its variants in (13), e.g.,
from 0.52 to 0.68 when the EfficientNet-B0 is used. In fact, under our
experiments setup, none of LSR, CP, and LC show any improvements in accuracy.

(a) Batch size

(b) Loss coefficient $\lambda_{ent}$

Figure 14: Pinpoint batch size and $\lambda_{ent}$ parameters.

Learning Curves We plot the learning curves over MNIST and CIFAR-10 datasets
in Figure 10, 11, 12, and 13 for illustrations. From the results, we can see
that the proposed approach can train classifiers with much better
classification performances. We can also see a very strong connection between
the mutual information and the error rate. The MILCs seems to take longer time
to converge than the conditional entropy learned classifiers (CELCs), and we
conjecture this is because learning the joint distribution $p_{X,Y}$ is more
challenging than learning the conditional distribution $p_{Y|X}$. In the
celLoss training approach, we can see that the conditional entropy learned
over CIFAR-10 is very small. This means that when a CIFAR-10 image is given,
there will be almost no uncertainty left for the label of the CIFAR-10 sample.
However, this is not case in practice. As we can see from Figure 15 in the
Appendix , there should be much more uncertainty left about the label
associated with the CIFAR-10 sample.

We can also see a very strong connection between the mutual information and
the error rate. For example, in Figure 12(c), the error rate decreases as the
mutual information increases. When the mutual information finally converges to
about 2.1, the error rate converges to about 0.06. Notice that the maximum
possible entropy of the label is $\log(10)=2.3$ nats, and the empirical
results shows that the label entropy can be easily learned in very small
number of epochs. The gap between the learned mutual information 2.1 and the
learned conditional entropy 0.1 is about 2.0 which is 20 times larger than the
conditional entropy itself. What seems to be surprising is that under our
experimental settings, the existing LSR, CP, and LC regularizations for the
conditional entropy learning loss (celLoss) do not bring any benefits over the
celLoss itself alone. The benefits of of the proposed approach in
generalization is even more obvious and significant in the CIFAR-10
classification task. For example, in Figure 11, the error rate of the model
trained by celLoss minimization cannot even go below 0.25, while the model
trained via milLoss minimization can achieve error rate of about 0.15.

Effects of Batch Size and Entropy Regularization Coefficient We conduct
experiments with typical neural network architectures to investigate how the
batch size and the $\lambda_{ent}$ affect the performance, the experimental
setup except the batch size or $\lambda_{ent}$ is exactly the same as that of
the baseline models. When evaluating effect of the batch size (or the
$\lambda_{ent}$), we use fixed $\lambda_{ent}=5e1$ (or fixed batch size of 512
for MNIST and 256 for CIFAR-10). The results are presented in Figure 14. From
the results we can see that for both MNIST and CIFAR-10 dataset, the testing
accuracy does not always go up as the batch size increases, which is quite
different what is expected for CELCs. When the batch size increases, both the
signal pattern and the noise pattern will become stronger. The milLoss
essentially learns the mutual information associated with the joint data
generation distribution, and it can overfit to the noise pattern as the batch
size increases since the mutual information itself encourage the model to
consider the overall data generation distribution. This then results in the
classification performance degradation. However, for CELCs, despite the
stronger noise pattern caused by a larger batch size, the conditional entropy
learning loss can help the model avoid overfitting to the noise pattern
because it encourages the model to give high confidence prediction of labels.
The cost is a less accurate characterization of the joint distribution
$p_{X,Y}$ by CELCs.

##  9 Conclusions

In this paper, we showed that the existing cross entropy loss minimization
essentially learns the conditional entropy of the label when the input is
revealed. We pointed out some fundamental limitations of this approach which
motivate us to propose a mutual information learning framework. For the
proposed learning framework, we established rigorous relation between the
error probability associated with a model trained on a dataset and the mutual
information associated with the distribution for generating the dataset.
Besides, we derive the sample complexity for accurately training the mutual
information learned classifiers. The application of our theory to a concrete
binary classification data model in $\mathbb{R}^{n}$ was given, and we derived
the bounds of the mutual information and the error probability associated with
it. We also conducted extensive experiments to validate our theory, and the
empirical results shows that the proposed mutual information learned
classifiers (MILCs) acheive far better generalization performance than those
trained via cross entropy minimization.

## Acknowledgement

We would like to thank Dr. Rui Yan from Microsoft Redmond for inspiring and
constructive discussions about loss function design. We would also like to
thank Dr. Praneeth Narayanamurthy and Prof. Urbashi Mitra from University of
Southern California for inspiring discussions about information bottleneck and
mutual information estimation.

## Appendix

### Appendix A1: Proof of Theorem 2.1

######  Theorem .1.

(Connections among different information-theoretic quantities) For a joint
distribution $p_{X,Y}$ over a continous random vector $X\in\mathbb{R}^{n}$ and
a discrete random variable $Y\in[C]$ where $C$ is a positive integer constant,
with the definition of mutual information in (1) and Defintion 1-4, we have

$\displaystyle I(X,Y)=H(Y)-H(Y|X),$ $\displaystyle I(X,Y)=h(X)-h(X|Y).$ (68)

###### Proof.

(of Theorem .1) From (1), we have

$\displaystyle I(X,Y)$
$\displaystyle=\int_{\mathbb{R}^{n}}p(x)\sum_{y\in[C]}P(y|x)\left(\log\left(\frac{p(x,y)}{P(y)}\right)-\log\left({p(x)}\right)\right)dx$
$\displaystyle=\int_{\mathbb{R}^{n}}p(x)\sum_{y\in[C]}P(y|x)\log\left(\frac{p(x,y)}{P(y)}\right)dx-\int_{\mathbb{R}^{n}}p(x)\sum_{y\in[C]}P(y|x)\log\left({p(x)}\right)dx$
$\displaystyle=\int_{\mathbb{R}^{n}}\sum_{y\in[C]}p(x,y)\log\left({p(x|y)}\right)dx-\int_{\mathbb{R}^{n}}p(x)\log\left({p(x)}\right)dx$
$\displaystyle=-\int_{\mathbb{R}^{n}}\sum_{y\in[C]}P(y)p(x|y)\log\left(\frac{1}{p(x|y)}\right)dx+h(X)$
$\displaystyle=h(X)-\sum_{y\in[C]}P(y)\int_{\mathbb{R}^{n}}p(x|y)\log\left(\frac{1}{p(x|y)}\right)dx$
$\displaystyle=h(X)-h(X|Y).$ (69)

Similarly, we have from (1)

$\displaystyle I(X,Y)$
$\displaystyle=\sum_{y\in[C]}P(y)\int_{\mathbb{R}^{n}}p(x|y)\left(\log\left(\frac{p(x,y)}{p(x)}\right)-\log\left({P(y)}\right)\right)dx$
$\displaystyle=\sum_{y\in[C]}P(y)\int_{\mathbb{R}^{n}}p(x|y)\log\left(\frac{p(x,y)}{p(x)}\right)dx-\sum_{y\in[C]}P(y)\int_{\mathbb{R}^{n}}p(x|y)\log\left({P(y)}\right)dx$
$\displaystyle=\sum_{y\in[C]}P(y)\int_{\mathbb{R}^{n}}p(x|y)\log\left(\frac{p(x,y)}{p(x)}\right)dx-\sum_{y\in[C]}P(y)\log\left({P(y)}\right)$
$\displaystyle=H(Y)-\sum_{y\in[C]}P(y)\int_{\mathbb{R}^{n}}p(x|y)\log\left(\frac{1}{P(y|x)}\right)dx$
$\displaystyle=H(Y)-\int_{\mathbb{R}^{n}}\sum_{y\in[C]}P(y)p(x|y)\log\left(\frac{1}{P(y|x)}\right)dx$
$\displaystyle=H(Y)-\int_{\mathbb{R}^{n}}\sum_{y\in[C]}p(x)P(y|x)\log\left(\frac{1}{P(y|x)}\right)dx$
$\displaystyle=H(Y)-\int_{\mathbb{R}^{n}}p(x)\sum_{y\in[C]}P(y|x)\log\left(\frac{1}{P(y|x)}\right)dx$
$\displaystyle=H(Y)-H(Y|X).$ (70)

∎

### Appendix A2: Proof of Theorem 3.1

######  Theorem .2.

(Cross Entropy Minimization as Entropy Learning) For an arbitrary discrete
distribution $P_{Y}$ in $[C]$, we have

$\displaystyle H(Y)\leq\inf_{Q_{Y}}H(P_{Y},Q_{Y}),$ (71)

where $Q_{Y}$ is a distribution of $Y$, and the equality holds if and only if
$P_{Y}=Q_{Y}$. When a set of $N$ data points
$\mathcal{S}:=\\{y_{i}\\}_{i=1}^{N}$ drawn independently from $P_{Y}$ is
given, by defining $R(y):=\frac{P_{Y}(y)}{\hat{P}_{Y}(y)}$ where $\hat{P}_{Y}$
is the empirical distribution associated with $\\{y_{i}\\}_{i=1}^{N}$, we have

$\displaystyle H(Y)\leq\inf_{Q^{g}_{Y}}H(\hat{P}_{Y}^{g},Q_{Y}^{g}),$ (72)

where $\hat{P}_{Y}^{g}$ is defined as

$\displaystyle\hat{P}_{Y}^{g}(y):=\hat{P}_{Y}(y)R(y),\forall{y\in[C]},$ (73)

and $Q_{Y}^{g}$ is defined as

$\displaystyle Q_{Y}^{g}(y)=Q_{Y}(y)R(y),\forall{y\in[C]},$ (74)

with $Q_{Y}$ being a distribution of $Y$. The inequality holds if and only if
$P_{Y}=\hat{P}_{Y}=Q_{Y}$.

###### Proof.

(of Theorem 3.1) From the definition of entropy, we have for an arbitrary
distribution $Q_{Y}$ over $Y$

$\displaystyle H(Y)$
$\displaystyle=\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{1}{P_{Y}(y)}\right)$
$\displaystyle=\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{Q_{Y}(y)}{P_{Y}(y)}\frac{1}{Q_{Y}(y)}\right)$
$\displaystyle=\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{Q_{Y}(y)}{P_{Y}(y)}\right)+\sum_{y}P_{Y}(y)\log\left(\frac{1}{Q_{Y}(y)}\right)$
$\displaystyle=H(P_{Y},Q_{Y})-D_{KL}(P_{Y}||Q_{Y})$ $\displaystyle\leq
H(P_{Y},Q_{Y}),$ (75)

where

$\displaystyle
H(P_{Y},Q_{Y}):=\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{1}{Q_{Y}(y)}\right)$
(76)

is the cross entropy between $P_{Y}$ and $Q_{Y}$, and

$\displaystyle
D_{KL}(P_{Y}||Q_{Y}):=\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{P_{Y}(y)}{Q_{Y}(y)}\right)$
(77)

is the KL divergence between $P_{Y}$ and $Q_{Y}$, and we used the fact that
$D_{KL}(P_{Y}||Q_{Y})\geq 0$. The equality holds iff
$Q_{Y}(y)=P_{Y}(y),\forall{y\in[C]}$. The (Proof.) holds for arbitrary
$Q_{Y}$, thus,

$\displaystyle H(Y)=\inf_{Q_{Y}}H(P_{Y},Q_{Y}).$ (78)

For the cross entropy $H(P_{Y},Q_{Y})$, we have

$\displaystyle H(P_{Y},Q_{Y})$
$\displaystyle=\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{1}{Q_{Y}(y)}\right)$
$\displaystyle=\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{1}{Q_{Y}(y)}\frac{P_{Y}(y)}{\hat{P}_{Y}(y)}\frac{\hat{P}_{Y}(y)}{{P}_{Y}(y)}\right)$
$\displaystyle=\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{1}{Q_{Y}(y)}\frac{P_{Y}(y)}{\hat{P}_{Y}(y)}\right)+\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{\hat{P}_{Y}(y)}{{P}_{Y}(y)}\right)$
$\displaystyle=-\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{P_{Y}(y)}{\hat{P}_{Y}(y)}\right)+\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{1}{Q_{Y}(y)}\frac{{P}_{Y}(y)}{\hat{P}_{Y}(y)}\right)$
$\displaystyle=-D_{KL}(P_{Y}||\hat{P}_{Y})+\sum_{y\in[C]}P_{Y}(y)\log\left(\frac{1}{Q_{Y}(y)}\frac{{P}_{Y}(y)}{\hat{P}_{Y}(y)}\right)$
(79)

Thus

$\displaystyle H(P_{Y},Q_{Y})$
$\displaystyle\leq\sum_{y\in[C]}\hat{P}_{Y}(y)\frac{P_{Y}(y)}{\hat{P}_{Y}(y)}\log\left(\frac{1}{Q_{Y}(y)}\frac{{P}_{Y}(y)}{\hat{P}_{Y}(y)}\right)$
$\displaystyle\leq\sum_{y\in[C]}\hat{P}_{Y}(y)R(y)\log\left(\frac{1}{Q_{Y}(y)/R(y)}\right)$
(80)
$\displaystyle\leq\sum_{y\in[C]}\hat{P}_{Y}^{g}(y)\log\left(\frac{1}{Q_{Y}^{g}(y)}\right)$
$\displaystyle=H(\hat{P}_{Y}^{g},Q_{Y}^{g}),$ (81)

where we used $\hat{P}_{Y}^{g}(y)=\hat{P}_{Y}(y)R(y)$, and
$Q_{Y}^{g}(y)=Q_{Y}(y)/R(y)$, and $R(y)=\frac{{P}_{Y}(x)}{\hat{P}_{Y}(y)}$.
The equality holds iff $P_{Y}(y)=\hat{P}_{Y}(y),\forall{y\in[C]}$ which
implies that $D_{KL}(P_{Y}||\hat{P}_{Y})=0$ and $R(y)=1$. Thus,
$H(Y)=H(P_{Y},Q_{Y})=H(P_{Y}^{g},Q_{Y}^{g})$ if and only if
$P_{Y}=Q_{Y}=\hat{P}_{Y}$. Thus,

$\displaystyle
H(Y)=\inf_{Q_{Y}}H(P_{Y},Q_{Y})=\inf_{Q^{g}_{Y}}H(\hat{P}_{Y}^{g},{Q}_{Y}^{g}).$
(82)

∎

### Appendix A3: Proof of Theorem 4.1

######  Theorem .3.

(Error Bound of Entropy Learning from Empirical Distribution) For two
arbitrary distributions $P_{Y}$ and $\hat{P}_{Y}$ of a discrete random
variable $Y$ over $[C]$, we have

$\displaystyle\sum_{y\in[C]}R(y)\log\left(\frac{1}{{P}_{Y}(y)}\right)\leq
H_{P_{Y}}(Y)-H_{\hat{P}_{Y}}(Y)\leq\sum_{y\in[C]}R(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right)$
(83)

where $R(y)=P_{Y}(y)-\hat{P}_{Y}(y),\forall y\in[C]$, and $H_{P_{Y}}(Y)$ is
the entropy of $Y$ calculated via $P_{Y}$. The equality holds if and only if
$P_{Y}=\hat{P}_{Y}$.

###### Proof.

(of Theorem 4.1) From the definition of entropy, we have

$\displaystyle H_{P_{Y}}(Y)-H_{\hat{P}_{Y}}(Y)$
$\displaystyle=\sum_{y\in[C]}\left(P_{Y}(y)\log\left(\frac{1}{{P}_{Y}(y)}\right)\right)-\sum_{y\in[C]}\left(\hat{P}_{Y}(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right)\right)$
$\displaystyle=\sum_{y\in[C]}\left(P_{Y}(y)\log\left(\frac{\hat{P}_{Y}(y)}{{P}_{Y}(y)}\frac{1}{\hat{P}_{Y}(y)}\right)\right)-\sum_{y\in[C]}\left(\hat{P}_{Y}(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right)\right)$
$\displaystyle=-\sum_{y\in[C]}\left(P_{Y}(y)\log\left(\frac{{P}_{Y}(y)}{\hat{P}_{Y}(y)}\right)\right)+\sum_{y\in[C]}\left(P_{Y}(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right)\right)-\sum_{y\in[C]}\left(\hat{P}_{Y}(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right)\right)$
$\displaystyle=-D_{KL}(p_{Y}||\hat{P}_{Y})+\sum_{y\in[C]}\left(P_{Y}(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right)\right)-\sum_{y\in[C]}\left(\hat{P}_{Y}(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right)\right),$
$\displaystyle\leq\sum_{y\in[C]}R(y)\log\left(\frac{1}{\hat{P}_{Y}(y)}\right).$

The equality holds if and only if $\hat{P}_{Y}=P_{Y}$. Similarly, we can show
$\sum_{y\in[C]}R(y)\log\left(\frac{1}{{P}_{Y}(y)}\right)\leq
H_{P_{Y}}(Y)-H_{\hat{P}_{Y}}(Y)$. ∎

### Appendix A4: Proof of Theorem 5.2

######  Theorem .4.

(Error Probability Bound via Mutual Information) Assume that the learning
process $Y\to X\to\hat{Y}$ in Figure 5 is a Markov chain where $Y\in[C]$,
$X\in\mathbb{R}^{n}$, and $\hat{Y}\in[C]$, then for the prediction $\hat{Y}$
from an arbitrary learned model, we have

$\displaystyle\max\left(0,\frac{2+H(Y)-I(X;Y)-a}{4}\right)\leq P_{error}$ (84)

where $a:=\sqrt{(H(Y)-I(X;Y)-2)^{2}+4}$.

###### Proof.

(of Theorem 5.2) We define a random variable $E$

$\displaystyle E=\begin{cases}0,\text{if }Y=\hat{Y},\\\ 1,\text{if
}Y\neq\hat{Y},\end{cases}$ (85)

then the error probability will become

$\displaystyle P_{error}=P_{E}(E=1).$ (86)

From the properties of conditional joint entropy, we have

$\displaystyle H(E,Y|\hat{Y})$ $\displaystyle=H(E|\hat{Y})+H(Y|E,\hat{Y})$
$\displaystyle=H(E|\hat{Y})+P_{E}(E=0)H(Y|\hat{Y},E=0)+P_{E}(E=1)H(Y|\hat{Y},E=1)$
$\displaystyle=H(E|\hat{Y})+P_{E}(E=1)H(Y|\hat{Y},E=1)$ $\displaystyle\leq
H(E|\hat{Y})+P_{E}(E=1)H(Y|\hat{Y})$ $\displaystyle\leq
H(E)+P_{E}(E=1)H(Y|\hat{Y})$
$\displaystyle=H(P_{error})+P_{error}H(Y|\hat{Y}),$ (87)

where we used the fact that $H(Y|\hat{Y},E=0)=0$, $H(Y|\hat{Y},E=1)\leq
H(Y|\hat{Y})$, and $H(E|\hat{Y})\leq H(E)=H(P_{error})$ with $H(P_{error})$
defined as follows

$\displaystyle
H(P_{error}):=-P_{error}\log(P_{error})-(1-P_{error})\log(1-P_{error}).$

We also have

$\displaystyle H(E,Y|\hat{Y})$ $\displaystyle=H(Y|\hat{Y})+H(E|Y,\hat{Y})$
$\displaystyle=H(Y|\hat{Y})$ (88) $\displaystyle=H(Y)-I(Y;\hat{Y})$ (89)
$\displaystyle\geq H(Y)-I(X;Y),$ (90)

where we used the fact that $H(E|Y,\hat{Y})=0$, and the data processing
inequality associated with Markov process $Y\to X\to\hat{Y}$, i.e.,

$\displaystyle I(X;Y)\geq I(Y;\hat{Y}).$ (91)

Thus, from (Proof.) and (88), we have

$\displaystyle H(P_{error})+P_{error}H(Y|\hat{Y})\geq H(Y|\hat{Y}).$ (92)

Combining the above and (89), we get

$\displaystyle H(P_{error})\geq(1-P_{error})\left(H(Y)-I(X;Y)\right),$ (93)

which implies $P_{error}\geq 1-\frac{H(P_{error})}{H(Y)-I(X;Y)}$.

From Lemma 5.1, we have

$\displaystyle(1-P_{error})\left(H(Y)-I(X;Y)\right)\leq
1-2(P_{error}-0.5)^{2},$

or

$\displaystyle 2P_{error}^{2}-(2+H(Y)-I(X;Y))P_{error}+H(Y)-I(X;Y)-0.5\leq 0.$
(94)

By solving the above inequality for $P_{error}$, we get

$\displaystyle\frac{2+H(Y)-I(X;Y)-a}{4}\leq
P_{error}\leq\frac{2+H(Y)-I(X;Y)+a}{4},$

where $a$ is defined as

$\displaystyle a:=\sqrt{(H(Y)-I(X;Y)-2)^{2}+4}.$

Since $P_{error}\in[0,1]$, we have

$\displaystyle\max\left(0,\frac{2+H(Y)-I(X;Y)-a}{4}\right)\leq
P_{error}\leq\min\left(1,\frac{2+H(Y)-I(X;Y)+a}{4}\right),$ (95)

where the upper bound is trivial.

∎

### Appendix A5: Proof of Corollary 1

######  Corollary 3.

(Double sided Hoeffiding inequality) Let $X_{1},\cdots,X_{n}$ be independent
random variables such that $X_{i}$ takes its values in $[a_{i},b_{i}]$ almost
surely for all $i\leq n$. Let $S=\sum_{i=1}^{n}(X_{i}-\mathbb{E}[X_{i}])$.
Then, for every $t>0$,

$\displaystyle P\left(\\{X_{1},\cdots,X_{n}:|S|\geq t\\}\right)\leq
2\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$ (96)

###### Proof.

(of Corollary 1) We can define another set of random variables
$Y_{i}:=-X_{i},i=1,\cdots,n$, then all $i$ are independent such that $Y_{i}$
takes values in $[-b_{i},-a_{i}]$. We define
$S^{\prime}=\sum_{i=1}^{n}(Y_{i}-\mathbb{E}[Y_{i}])$, then from Lemma 6.1, we
have

$\displaystyle\exp\left(\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right)\geq
P\left(\\{X_{1},\cdots,X_{n}:S^{\prime}\geq
t\\}\right)=P\left(\\{X_{1},\cdots,X_{n}:S\leq-t\\}\right).$ (97)

Thus combine the above inequality with Lemma 6.1, we get the double sided
Hoeffding inequality, i.e.,

$\displaystyle P\left(\\{X_{1},\cdots,X_{n}:|S|\geq t\\}\right)$
$\displaystyle=P\left(\\{X_{1},\cdots,X_{n}:S\leq-t,\text{ or }S\geq
t\\}\right)$ (98) $\displaystyle\leq
P\left(\\{X_{1},\cdots,X_{n}:S\leq-t\\}\right)+P\left(\\{X_{1},\cdots,X_{n}:S\geq
t\\}\right)$ (99) $\displaystyle\leq
2\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$ (100)

∎

### Appendix A6: Proof of Lemma 6.2

######  Lemma .5.

(Concentration Inequality for Conditional Cross Entropy) We consider a set of
random variable pairs $\mathcal{S}:\\{(X_{i},Y_{i})\\}_{i=1}^{N}$ with each
$(X_{i},Y_{i})$ I.I.D. according to $p_{X,Y}$ in $\mathbb{R}^{n}\times[C]$,
and define

$\displaystyle
D:=\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(Y|X;\theta))\right],$
(101)

where $\theta\in\Theta_{c}$, $\Theta_{c}$ is a countable set, and
$Q_{Y|X}(Y|X;\theta)$ is a function of $X,Y$ with parameters $\theta$. Assume
$Q_{Y|X}(Y|X;\theta)\geq P^{\\#},\forall X,Y,\theta$ where $P^{\\#}>0$ is a
constant. Then, we have

$\displaystyle P(\\{\mathcal{S}:\max_{\theta\in\Theta_{c}}|D|\geq t\\})\leq
2|\Theta_{c}|\exp\left(-\frac{2Nt^{2}}{(\log(P^{\\#}))^{2}}\right)$ (102)

where $t>0$ is a constant.

###### Proof.

(of Lemma 6.2) From the definitions, we have for an arbitrary
$\theta_{j}\in\Theta_{c}$

$\displaystyle
P\left(\left\\{\mathcal{S}:\max_{\theta_{j}\in\Theta_{c}}\left|\frac{1}{N}\sum_{i=1}^{N}\left[\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))\right]-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|\geq
t\right\\}\right)$ (103)
$\displaystyle=P\left(\left\\{\mathcal{S}:\max_{\theta_{j}\in\Theta_{c}}\left|\frac{1}{N}\sum_{i=1}^{N}\left(\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))\right]\right)\right|\geq
t\right\\}\right)$ (104)
$\displaystyle=P\left(\left\\{\mathcal{S}:\exists\theta_{j}\in\Theta_{c}\text{
such that
}\left|\frac{1}{N}\sum_{i=1}^{N}\left(\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))\right]\right)\right|\geq
t\right\\}\right)$ (105)
$\displaystyle\leq\sum_{\theta_{j}\in\Theta_{c}}P\left(\left\\{\mathcal{S}:\left|\frac{1}{N}\sum_{i=1}^{N}\left[\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))\right]\right]\right|\geq
t\right\\}\right),$ (106)

where $\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j})),i=1,\cdots,N$ are I.I.D. because
$(X_{i},Y_{i}),i=1,\cdots,N$ are I.I.D. Since
$Q_{Y|X}(y|x;\theta)\in[P^{\\#},1],\forall(x,y)\in\mathbb{R}^{n}\times[C]$,
then $\log(Q_{Y|X}(y|x;\theta))\in[\log(P^{\\#}),0]$. From Corollary 1, we
have

$\displaystyle
P\left(\left\\{\mathcal{S}:\left|\frac{1}{N}\sum_{i=1}^{N}\left[\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))\right]\right]\right|\geq
t\right\\}\right)$ (107) $\displaystyle\leq
2\exp\left(-\frac{2N^{2}t^{2}}{\sum_{i=1}^{N}(\log(P^{\\#}))^{2}}\right)$
(108) $\displaystyle=2\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right).$
(109)

Thus,

$\displaystyle P(\\{\mathcal{S}:\max_{\theta\in\Theta_{c}}|D|\geq t\\})$
$\displaystyle=P\left(\left\\{\mathcal{S}:\max_{\theta_{j}\in\Theta_{c}}\left|\frac{1}{N}\sum_{i=1}^{N}\left[\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))\right]-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|\geq
t\right\\}\right)$
$\displaystyle\leq\sum_{\theta_{j}\in\Theta_{c}}2\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right)$
$\displaystyle=2|\Theta_{c}|\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right).$
(110)

∎

### Appendix A7: Proof of Theorem 6.6

######  Theorem .6.

(Sample Complexity for Estimation Error Bound) We consider a joint
distirbution $p_{X,Y}$ in $\mathbb{R}^{n}\times[C]$ where $X\in\mathbb{R}^{n}$
is a continuous random vector, and $Y\in[C]$ is a discrete random variable. We
define $I_{\Gamma,\Theta}$ associated with $p_{X,Y}$ similar to (6.2), i.e.,

$\displaystyle
I_{\Gamma,\Theta}=\inf_{\gamma\in\Gamma}\mathbb{E}_{P_{Y}}[-\log\left(Q_{Y}(Y;\gamma)\right)]-\inf_{\theta\in\Theta}\mathbb{E}_{p_{X,Y}}[-\log(Q_{Y|X}(Y|X;\theta))],$
(111)

where $Q_{Y|X}(Y|X;\theta)$ is a neural network with parameters
$\theta\in\Theta\subset\mathbb{R}^{m}$ which predicts the conditional
probability of $Y$ conditioning on $X$, and $Q_{Y}(Y;\gamma)$ is another
neural network with parameters $\gamma\in\Gamma\subset\mathbb{R}^{m^{\prime}}$
which predicts the marginal probability of $Y$. Assume that we are given a set
of random examples $\mathcal{S}:\\{(X_{i},Y_{i})\\}_{i=1}^{N}$ such that
$(X_{i},Y_{i}),i=1\cdots,N$ are I.I.D. and follow $p_{X,Y}$. Define
$I_{\Gamma,\Theta}^{(N)}$ similar to that in (6.2), i.e.,

$\displaystyle
I_{\Gamma,\Theta}^{(N)}=\inf_{\gamma\in\Gamma}\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y}(Y_{i};\gamma))-\inf_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y|X}(Y_{i}|X_{i};\theta)).$
(112)

Assume both $\Theta$ and $\Gamma$ are compact sets, and bounded, i.e.,
$\|\theta\|\leq M_{\theta}$ and $\|\gamma\|\leq M_{\gamma}$ where
$M_{\theta}>0,M_{\gamma}>0$ are constants. We assume both
$Q_{Y}(\cdot;\gamma)$ and $Q_{Y|X}(\cdot;\theta)$ are lower bounded by
$P^{\\#}$, and they are Lipschitz continuous with respect to $\theta$ for all
$y\in[C]$ and all $(x,y)\in\mathbb{R}^{n}\times[C]$, and the Lipschitz
constants are $L_{\gamma}>0$ and $L_{\theta}>0$, respectively. Then, when
$N\geq\frac{2\log\left(\frac{1}{\epsilon}\right)\left(P^{\\#}\log(P^{\\#})\right)^{2}}{\left(\delta
P^{\\#}-4^{\frac{1+m^{\prime}}{m^{\prime}}}L_{\gamma}M_{\gamma}\sqrt{m^{\prime}}-4^{\frac{1+m}{m}}L_{\theta}M_{\theta}\sqrt{m}\right)^{2}}$,
we have

$\displaystyle
P\left(\left\\{\mathcal{S}:\left|I_{\Theta}^{(N)}-I_{\Theta}\right|\leq\delta\right\\}\right)\geq
1-\epsilon.$ (113)

###### Proof.

(of Theorem 6.6) From the definition of $I_{\Gamma,\Theta}$ and
$I_{\Gamma,\Theta}^{(N)}$ in (6.2) and (6.2), we have

$\displaystyle\left|I_{\Gamma,\Theta}^{(N)}-I_{\Gamma,\Theta}\right|$
$\displaystyle=\Bigg{|}\inf_{\gamma\in\Gamma}\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y}(Y_{i};\gamma))-\inf_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y|X}(Y_{i}|X_{i};\theta))$
$\displaystyle\quad-\left(\inf_{\gamma\in\Gamma}\mathbb{E}_{P_{Y}}[-\log\left(Q_{Y}(Y;\gamma)\right)]-\inf_{\theta\in\Theta}\mathbb{E}_{p_{X,Y}}[-\log(Q_{Y|X}(Y|X;\theta))]\right)\Bigg{|}$
$\displaystyle\leq\left|\inf_{\gamma\in\Gamma}\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y}(Y_{i};\gamma))-\inf_{\theta\in\Theta}\mathbb{E}_{P_{Y}}\left[-\log(Q_{Y}(Y;\gamma))\right]\right|$
$\displaystyle\quad+\left|\inf_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\inf_{\theta\in\Theta}\mathbb{E}_{P_{Y,X}}\left[-\log(Q_{Y|X}(Y|X;\theta))\right]\right|$
$\displaystyle\leq\sup_{\gamma\in\Gamma}\left|\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y}(Y_{i};\gamma))-\mathbb{E}_{P_{Y}}\left[-\log(Q_{Y}(\gamma))\right]\right|$
$\displaystyle\quad+\sup_{\theta\in\Theta}\left|\frac{1}{N}\sum_{i=1}^{N}-\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\mathbb{E}_{P_{Y,X}}\left[-\log(Q_{Y|X}(\theta))\right]\right|$
(114)
$\displaystyle=\sup_{\gamma\in\Gamma}\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma))-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\gamma))\right]\right|$
$\displaystyle\quad+\sup_{\theta\in\Theta}\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta))\right]\right|$
$\displaystyle=\sup_{\gamma\in\Gamma}A+\sup_{\theta\in\Theta}B$ (115)

where (114) is due to Lemma 6.4, and we define

$\displaystyle
A:=\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma))-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\gamma))\right]\right|,$
(116) $\displaystyle
B:=\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta))\right]\right|.$
(117)

We will bound both $A$ and $B$. Before this, we introduce the concept of
covering set for $\Theta$ and $\Gamma$. For the $\Theta\subset\mathbb{R}^{m}$,
we construct a cover, i.e., a set of balls
$\left\\{B_{r_{\theta}}(\theta_{j})\right\\}_{j=1}^{N(r_{\theta},\Theta)}$
with radius $r_{\theta}$ and centered at
$\theta_{j},j=1,\cdots,N(r_{\theta},\Theta)$ such that
$\Theta\subset\cup_{j=1}^{N(r_{\theta},\Theta)}B_{r_{\theta}}(\theta_{j})$.
From Lemma 6.5, we know that

$\displaystyle
N(r_{\theta},\Theta)\leq\left(\frac{2M_{\theta}\sqrt{m}}{r_{\theta}}\right)^{m},$
(118)

where $M_{\theta}$ is the upper bound of $\theta$, i.e., $\|\theta\|\leq
M_{\theta},\forall\theta\in\Theta$. Similarly, for
$\Gamma\subset\mathbb{R}^{m^{\prime}}$, we can construct a set of balls
$\\{B_{r_{\gamma}}(\gamma_{j})\\}_{j=1}^{N(r_{\gamma},\Gamma)}$ which covers
$\Gamma$, and

$\displaystyle
N(r_{\gamma},\Gamma)\leq\left(\frac{2M_{\gamma}\sqrt{m^{\prime}}}{r_{\gamma}}\right)^{m^{\prime}}.$
(119)

Upper bound of $A$ For $A$, we can find a $\gamma_{j}$ so that
$B_{r_{\gamma}}(\gamma_{j})$ covers $\gamma$, i.e., $\|\gamma-\gamma_{j}\|\leq
r_{\gamma}$. Then,

$\displaystyle A$
$\displaystyle=\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma))-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\gamma))\right]\right|$
(120)
$\displaystyle\leq\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma))-\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma_{j}))\right|+\left|\mathbb{E}_{{P}_{Y}}\left[\log(Q_{Y}(\gamma))\right]-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\gamma_{j}))\right]\right|$
(121)
$\displaystyle\quad+\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma_{j}))-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\gamma_{j}))\right]\right|$
(122)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\left[\left|\log(Q_{Y}(Y_{i};\gamma))-\log(Q_{Y}(Y_{i};\gamma_{j}))\right|\right]+\mathbb{E}_{{P}_{Y}}\left[\left|\log(Q_{Y}(\gamma))-\log(Q_{Y}(\gamma_{j}))\right|\right]$
(123)
$\displaystyle\quad+\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma_{j}))-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\gamma_{j}))\right]\right|$
(124)
$\displaystyle\leq\frac{1}{P^{\\#}}\frac{1}{N}\sum_{i=1}^{N}\left[\left|Q_{Y}(Y_{i};\gamma)-Q_{Y}(Y_{i};\gamma_{j})\right|\right]+\frac{1}{P^{\\#}}\mathbb{E}_{{P}_{Y}}\left[\left|Q_{Y}(\gamma)-Q_{Y}(\gamma_{j})\right|\right]$
(125)
$\displaystyle\quad+\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y}(Y_{i};\gamma_{j}))-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\gamma_{j}))\right]\right|,$
(126)

where we used the Lipschitz continuity of $\log(\cdot)$.

Since

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\left[\left|Q_{Y}(Y_{i};\gamma)-Q_{Y}(Y_{i};\gamma_{j})\right|\right]\leq
L_{\gamma}\|\gamma-\gamma_{j}\|\leq L_{\gamma}r_{\gamma},$ (127)

and

$\displaystyle\mathbb{E}_{{P}_{Y}}\left[\left|Q_{Y}(\gamma)-Q_{Y}(\gamma_{j})\right|\right]\leq
L_{\gamma}\|\gamma-\gamma_{j}\|\leq L_{\gamma}r_{\gamma},$ (128)

where we used the Lipschitz continuity of $Q_{Y}(\cdot;\gamma)$ with respect
to $\gamma$, then

$\displaystyle A$
$\displaystyle\leq\frac{2L_{\gamma}r_{\gamma}}{P^{\\#}}+\left|\frac{1}{N}\sum_{i=1}^{N}\left[\log(Q_{Y}(Y_{i};\theta_{j}))\right]-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\theta_{j}))\right]\right|.$
(129)

From Lemma 6.3, the following holds with probability at least
$1-2\left(\frac{2M_{\gamma}\sqrt{m^{\prime}}}{r_{\gamma}}\right)^{m^{\prime}}\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right)$
over $\\{Y_{i}\\}_{i=1}^{N}$,

$\displaystyle\left|\frac{1}{N}\sum_{i=1}^{N}\left[\log(Q_{Y}(Y_{i};\gamma_{j}))\right]-\mathbb{E}_{P_{Y}}\left[\log(Q_{Y}(\gamma_{j}))\right]\right|\leq
t.$ (130)

Thus, with high probability,

$\displaystyle A\leq\frac{2L_{\gamma}r_{\gamma}}{P^{\\#}}+t,$ (131)

where $t>0$ is a constant.

Upper bound of $B$ For $B$, we can also find a $\theta_{j}$ such that
$B_{r_{\gamma}}(\theta_{j})$ covers $\theta$, thus, $\|\theta-\theta_{j}\|\leq
r_{\gamma}$. Then,

$\displaystyle B$
$\displaystyle=\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta))\right]\right|$
$\displaystyle\leq\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))\right|+\left|\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta))\right]-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|$
$\displaystyle\quad+\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\left|\log(Q_{Y|X}(Y_{i}|X_{i};\theta))-\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))\right|+\mathbb{E}_{P_{Y,X}}\left[\left|\log(Q_{Y|X}(\theta))-\log(Q_{Y|X}(\theta_{j}))\right|\right]$
$\displaystyle\quad+\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|$
$\displaystyle\leq\frac{1}{P^{\\#}}\frac{1}{N}\sum_{i=1}^{N}\left[\left|Q_{Y|X}(Y_{i};\theta)-Q_{Y|X}(Y_{i};\theta_{j})\right|\right]+\frac{1}{P^{\\#}}\mathbb{E}_{P_{Y,X}}\left[\left|Q_{Y|X}(\theta)-Q_{Y|X}(\theta_{j})\right|\right]$
$\displaystyle\quad+\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|$
$\displaystyle\leq\frac{1}{P^{\\#}}L_{\theta}\|\theta-\theta_{j}\|+\frac{1}{P^{\\#}}L_{\theta}\|\theta-\theta_{j}\|+\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|$
$\displaystyle\leq\frac{2L_{\theta}r_{\theta}}{P^{\\#}}+\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|,$

where we used the Lipschitz continuity of $\log(\cdot)$ and
$Q_{Y|X}(\cdot;\theta)$.

From Lemma 6.2, with probability at least
$1-2\left(\frac{2M_{\theta}\sqrt{m}}{r_{\theta}}\right)^{m}\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right)$
over $\\{(X_{i},Y_{i})\\}_{i=1}^{N}$, we have

$\displaystyle\left|\frac{1}{N}\sum_{i=1}^{N}\log(Q_{Y|X}(Y_{i}|X_{i};\theta_{j}))-\mathbb{E}_{P_{Y,X}}\left[\log(Q_{Y|X}(\theta_{j}))\right]\right|\leq
t,$ (132)

where we used
$|\Theta_{c}|=N(r,\Theta)\leq\left(\frac{2M_{\theta}\sqrt{m}}{r}\right)^{m}$.
Thus, with high probability

$\displaystyle B\leq\frac{2L_{\theta}r_{\theta}}{P^{\\#}}+t.$ (133)

Since

$\displaystyle
P\left(\left\\{S:A\leq\frac{2L_{\gamma}r_{\gamma}}{P^{\\#}}+t,B\leq\frac{2L_{\theta}r_{\theta}}{P^{\\#}}+t\right\\}\right)$
$\displaystyle=1-P\left(\left\\{S:A\geq\frac{2L_{\gamma}r_{\gamma}}{P^{\\#}}+t\text{
or }B\geq\frac{2L_{\theta}r_{\theta}}{P^{\\#}}+t\right\\}\right)$ (134)
$\displaystyle\geq
1-P\left(\left\\{S:A\geq\frac{2L_{\gamma}r_{\gamma}}{P^{\\#}}+t\right\\}\right)-P\left(\left\\{S:B\geq\frac{2L_{\theta}r_{\theta}}{P^{\\#}}+t\right\\}\right)$
(135) $\displaystyle\geq
1-2\left(\frac{2M_{\gamma}\sqrt{m^{\prime}}}{r_{\gamma}}\right)^{m^{\prime}}\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right)$
(136)
$\displaystyle\quad-2\left(\frac{2M_{\theta}\sqrt{m}}{r_{\theta}}\right)^{m}\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right),$
(137)

then with high probability, the following holds

$\displaystyle\left|I_{\Theta}^{(N)}-I_{\Theta}\right|$
$\displaystyle\leq\sup_{\theta\in\Theta}A+\sup_{\theta\in\Theta_{c}}B$ (138)
$\displaystyle\leq\frac{2L_{\gamma}r_{\gamma}}{P^{\\#}}+\frac{2L_{\theta}r_{\theta}}{P^{\\#}}+2t$
(139)

By taking $t=\frac{\delta
P^{\\#}-2L_{\gamma}r_{\gamma}-2L_{\theta}r_{\theta}}{2P^{\\#}}$, we have

$\displaystyle\left|I_{\Theta}^{(N)}-I_{\Theta}\right|\leq\delta,$ (140)

where $\delta>0$ is a constant. Take
$r_{\gamma}=4^{\frac{1}{2}+\frac{1}{m^{\prime}}}M_{\gamma}\sqrt{m^{\prime}}$
and $r_{\theta}=4^{\frac{1}{2}+\frac{1}{m}}M_{\theta}\sqrt{m}$, and then let

$\displaystyle
2\left(\frac{2M_{\gamma}\sqrt{m^{\prime}}}{r_{\gamma}}\right)^{m^{\prime}}\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right)+2\left(\frac{2M_{\theta}\sqrt{m}}{r_{\theta}}\right)^{m}\exp\left(-2N\frac{t^{2}}{(\log(P^{\\#}))^{2}}\right)\leq\epsilon,$
(141)

we have

$\displaystyle
N\geq\frac{2\log\left(\frac{1}{\epsilon}\right)\left(P^{\\#}\log(P^{\\#})\right)^{2}}{\left(\delta
P^{\\#}-4^{\frac{1+m^{\prime}}{m^{\prime}}}L_{\gamma}M_{\gamma}\sqrt{m^{\prime}}-4^{\frac{1+m}{m}}L_{\theta}M_{\theta}\sqrt{m}\right)^{2}}.$
(142)

Thus, when
$N\geq\frac{2\log\left(\frac{1}{\epsilon}\right)\left(P^{\\#}\log(P^{\\#})\right)^{2}}{\left(\delta
P^{\\#}-4^{\frac{1+m^{\prime}}{m^{\prime}}}L_{\gamma}M_{\gamma}\sqrt{m^{\prime}}-4^{\frac{1+m}{m}}L_{\theta}M_{\theta}\sqrt{m}\right)^{2}}$,
we have

$\displaystyle
P\left(\\{\mathcal{S}:\left|I_{\Theta}^{(N)}-I_{\Theta}\right|\leq\delta\\}\right)\geq
1-\epsilon.$ (143)

∎

### Appendix A8: Proof of Lemma 7.1

######  Lemma .7.

(Expectation of Quadratic Form of Gaussian Random Vector) For a Gaussian
random vector $X\in\mathbb{R}^{n}$ following $\mathcal{N}(\mu,\Sigma)$, we
have

$\displaystyle\mathbb{E}_{X}\left[X^{T}AX\right]=\rm{Tr}(A\Sigma)+\mu^{T}\Sigma^{-1}\mu,$
$\displaystyle\mathbb{E}_{X}\left[(X-\mu)^{T}A(X-\mu)\right]=\rm{Tr}(A\Sigma),$
$\displaystyle\mathbb{E}_{X}\left[(X+\mu)^{T}A(X+\mu)\right]=\rm{Tr}(A\Sigma)+4\mu^{T}\Sigma\mu,$
(144)

where $A\in\mathbb{R}^{n\times n}$ is a square matrix.

###### Proof.

(of Lemma 7.1) From the definition of expectation, we have

$\displaystyle\mathbb{E}_{X}\left[X^{T}AX\right]$
$\displaystyle=\int_{\mathbb{R}^{n}}\frac{1}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)x^{T}Axdx$
$\displaystyle=\int_{\mathbb{R}^{n}}\frac{1}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)\rm{Tr}(Axx^{T})dx$
$\displaystyle=\int_{\mathbb{R}^{n}}\frac{1}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)\rm{Tr}\left(A(x-\mu)(x-\mu)^{T}-A\mu\mu^{T}+Ax\mu^{T}+A\mu
x^{T}\right)dx$
$\displaystyle=\int_{\mathbb{R}^{n}}\frac{1}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)\left(\rm{Tr}(A(x-\mu)(x-\mu)^{T})-\mu^{T}A\mu+\mu^{T}Ax+x^{T}A\mu\right)dx$
$\displaystyle=\int_{\mathbb{R}^{n}}\frac{1}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)\rm{Tr}(A(x-\mu)(x-\mu)^{T})dx+\mu^{T}A\mu$
$\displaystyle=\rm{Tr}(A\Sigma)+\mu^{T}A\mu.$

Similarly, we can derive the other two equations in (.7). ∎

### Appendix A9: Proof of Theorem 7.2

######  Theorem .8.

(Mutual Information of Binary Classification Dataset Model) For the data model
with distribution defined in (7), we have the mutual information $I(X;Y)$
satisfying

$\displaystyle 2\min(q,1-q)\mu^{T}\Sigma^{-1}\mu\leq I(X;Y)\leq
4q(1-q)\mu^{T}\Sigma^{-1}\mu.$ (145)

###### Proof.

(of Theorem 7.2) From the definition of mutual information, we have

$\displaystyle I(X,Y):=h(X)-h(X|Y),$ (146)

where the differential entropy $h(X|Y=1)=h(X|Y=-1)=\frac{1}{2}\log(|2\pi
e\Sigma|)$ and $e$ is the natural number. Thus

$\displaystyle h(X|Y)=P(Y=1)\times h(X|Y=1)+P(Y=-1)\times
h(X|Y=-1)=\frac{1}{2}\log(|2\pi e\Sigma|).$ (147)

From the definition of data model in (7), we have the marginal distirbution
$p_{X}$

$\displaystyle p_{X}(x)$ $\displaystyle=P_{Y}(Y=1)\times
p_{X|Y=1}(X=x)+P_{Y}(Y=-1)\times p_{X|Y=-1}(X=x)$
$\displaystyle=\frac{(1-q)}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+\frac{q}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right).$
(148)

we have

$\displaystyle h(X)$
$\displaystyle:=\int_{\mathbb{R}}p_{X}(x)\log\left(\frac{1}{p_{X}(x)}\right)dx$
$\displaystyle=\int_{\mathbb{R}}p_{X}(x)\times\log\left(\frac{1}{\frac{(1-q)}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+\frac{q}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)}\right)dx$
$\displaystyle=(-1)\times\int_{\mathbb{R}}p_{X}(x)\log\left(\frac{(1-q)}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+\frac{q}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)dx.$
(149)

From Jensen’s inequality for convex function $\exp(x)$, we have

$\displaystyle\log\left(\frac{(1-q)}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+\frac{q}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)$
$\displaystyle=\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\log\left({(1-q)\times\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+q\times\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)}\right)$
$\displaystyle\geq\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\log\left(\exp\left((1-q)\times\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+q\times\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)\right)$
$\displaystyle=\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\left((1-q)\times\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+q\times\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)$
$\displaystyle=\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\left(-\frac{1}{2}x^{T}\Sigma^{-1}x-\frac{1}{2}\mu^{T}\Sigma^{-1}\mu+(1-2q)x^{T}\Sigma^{-1}\mu\right).$

Since

$\displaystyle\int_{\mathbb{R}}p_{X}(x)\left(\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)-\frac{1}{2}\mu^{T}\Sigma^{-1}\mu\right)dx=\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)-\frac{1}{2}\mu^{T}\Sigma^{-1}\mu,$
$\displaystyle\int_{\mathbb{R}^{n}}p_{X}(x)(1-2q)x^{T}\Sigma^{-1}\mu dx$
$\displaystyle=(1-q)(1-2q)\mu^{T}\Sigma^{-1}\mu+q(1-2q)(-\mu)^{T}\Sigma^{-1}\mu$
$\displaystyle=(1-2q)^{2}\mu^{T}\Sigma^{-1}\mu,$

and

$\displaystyle\int_{\mathbb{R}^{n}}p_{X}(x)\left(-\frac{1}{2}x^{T}\Sigma^{-1}x\right)dx=-\frac{1}{2}\left(n+\mu^{T}\Sigma^{-1}\mu\right),$

where we used Lemma 7.1, then we have from (Proof.)

$\displaystyle h(X)$
$\displaystyle\leq(-1)\int_{\mathbb{R}^{n}}p_{X}(x)+\left(\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)-\frac{1}{2}x^{T}\Sigma^{-1}x-\frac{1}{2}\mu^{T}\Sigma^{-1}\mu+(1-2q)x^{T}\Sigma^{-1}\mu\right)$
$\displaystyle=(-1)\left(\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)-\frac{1}{2}\mu^{T}\Sigma^{-1}\mu+(1-2q)^{2}\mu^{T}\Sigma^{-1}\mu-\frac{1}{2}\left(n+\mu^{T}\Sigma^{-1}\mu\right)\right)$
$\displaystyle=\frac{1}{2}\log|2\pi e\Sigma|+4q(1-q)\mu^{T}\Sigma^{-1}\mu.$
(150)

Thus, combining (146), (147), and (Proof.), we can get

$\displaystyle I(X;Y)$ $\displaystyle\leq\frac{1}{2}\log|2\pi
e\Sigma|+4q(1-q)\mu^{T}\Sigma^{-1}\mu-\frac{1}{2}\log|2\pi e\Sigma|$ (151)
$\displaystyle=4q(1-q)\mu^{T}\Sigma^{-1}\mu.$ (152)

We now derive the lower bound of $I(X;Y)$. Since

$\displaystyle\log\left(\frac{(1-q)}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+\frac{q}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)$
$\displaystyle=\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\log\left({(1-q)\times\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+q\times\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)}\right)$
$\displaystyle\leq\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\log\left(\max\left(\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right),\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)\right)$
$\displaystyle=\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\log\left(\exp\left(\max\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2},-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)\right)$
$\displaystyle=\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\max\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2},-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)$

then

$\displaystyle h(X)$
$\displaystyle\geq(-1)\times\int_{\mathbb{R}}p_{X}(x)\left(\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\max\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2},-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)dx$
$\displaystyle=-\log\left(\frac{1}{\sqrt{|2\pi\Sigma|}}\right)+\min\left(I_{-},I_{+}\right),$
(153)

where

$\displaystyle I_{-}$
$\displaystyle:=\int_{\mathbb{R}^{n}}p_{X}(x)\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}dx$
$\displaystyle=\int_{\mathbb{R}}\left(\frac{(1-q)}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+\frac{q}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)$
$\displaystyle\quad\times\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}dx$

and

$\displaystyle I_{+}$
$\displaystyle:=\int_{\mathbb{R}^{n}}p_{X}(x)\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}dx$
$\displaystyle=\int_{\mathbb{R}}\left(\frac{(1-q)}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x-\mu)^{T}\Sigma^{-1}(x-\mu)}{2}\right)+\frac{q}{\sqrt{|2\pi\Sigma|}}\exp\left(-\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}\right)\right)$
$\displaystyle\quad\times\frac{(x+\mu)^{T}\Sigma^{-1}(x+\mu)}{2}dx.$

From Lemma 7.1, we have

$\displaystyle L_{-}$