# An Information Bottleneck Approach to Secrecy-Preserving Gaussian Mixture
Classification

Yi Song, Kai Wan, Yuan Zhang, Di Xie, Zhengyu Liao, Giuseppe Caire Y. Song and
G. Caire are with Faculty of Electrical Engineering and Computer Science,
Technical University of Berlin, Berlin, Germany (email<EMAIL_ADDRESS>caire@tu-berlin.de).K. Wan and Z. Liao are with School of Electronic
Information and Communications, Huazhong University of Science and Technology,
Wuhan, China (email<EMAIL_ADDRESS>zhenyu_liao@hust.edu.cn). Y. Zhang
and D. Xie are with Hikvision Research Institute, Hangzhou, China.

###### Abstract

The information bottleneck (IB) approach, initially introduced by [1] to
assess the “compression–relevance” tradeoff for a remote source coding problem
in communication, quickly gains popularity recently in its application to
modern machine learning (ML). Unlike the use of most – if not all – IB in the
literature, either for the analysis of, say deep neural networks, or as an
optimization objective, in this paper, we propose to address the secrecy issue
in ML, by considering the fundamental model of Gaussian mixture
classification. We derive, for the first time, _closed-form achievable_ bounds
for the IB problem under the above setting, and provide _precise_
characterization of the underlying “performance–secrecy” tradeoff. Experiments
on both synthetic and real-world data are performed to confirm the
satisfactory performance of the proposed scheme.

##  I Introduction

Large-scale machine learning (ML) models, and in particular, deep neural
networks (DNNs), have made significant progress over the past decade, with a
rapidly growing list of applications ranging from computer vision [2], game
[3], to speech and natural language processing [4], as well as AI-generated
content [5], just to name a few.

Despite their sophisticated and task-specific structures (that help boost the
performance to a superhuman level), many basic concepts, design principles,
and building blocks of modern ML models are deeply rooted in some simple but
highly non-trivial ideas in probability, information theory (IT), and
optimization. As an instance, the concepts of mutual information and cross-
entropy are widely used in ML [6, Section 3.13], for features and/or model
selection [7], the (loss) design of generative [8, 9, 10, 11], unsupervised
[12] as well as self-supervised [13] learning methods.

In this respect, the information bottleneck (IB) approach introduced by [1],
initially proposed to characterize the tradeoff between the compression and
the relevance rate for a remote source coding problem, adopts mutual
information as the figure of merit. In recent years, IB has received
significant research attention in ML, see, for example [14, 15, 16, 17, 18,
19, 20], to name a few. In plain words, the IB framework describes the
procedure of information extraction from a target random variable $y$ through
an observable random variable $x$ (that is correlated to $y$), by forming the
Markov chain $y\longrightarrow x\longrightarrow t(x)$, with $t(x)$ a (possibly
random) function $x$ that “extracts” information from the observation $x$. In
the methodology of IB, the extracted information, or the _feature_ $t(x)$, is
good if it is a “compact” (in an information-theoretic sense) representation
of $x$, and at the same time retains sufficiently rich information about the
target $y$, in such a way that the mutual information $I(x;t)$ is small while
$I(y;t)$ remains large; that is, the IB method solves the optimization
problem:

$\displaystyle\max_{p(t|x)}\quad$ $\displaystyle I(y;t)$ s.t. $\displaystyle
I(x;t)\leq R,$ (1)

for any given non-negative number $R$.

It is important to note here that the classical IB problem is described in the
term of the mutual information, and therefore of the _distributions_ of the
target/label $y$, data $x$, as well as the intermediate representation $t(x)$.
These distributions are, a priori, inaccessible in ML practice when _only_ a
finite number of training samples are given, and should in fact be “learnt”
during the training of ML models such as DNNs. Also, due to the mathematically
involved form of IB, the optimal design of $t(x)$ is known in closed-form only
in the case of binary symmetric or jointly Gaussian $(x,y)$ [19], which
prohibits the further theoretical analysis of (e.g., the statistical
properties of) the obtained representation.

As a consequence, most – if not all – existing works that apply IB ideas to ML
either

  * (i)

analyze or explain the training of, e.g., DNN models, to justify the choice of
network depth, structure, activation function, and/or optimizer [14, 21]; or

  * (ii)

use IB formulation as an optimization objective to enhance generalization,
robustness to adversarial examples [15], and/or sufficiency as well as
disentanglement of representations [22].

In this paper, we focus on the problem of IB for learning, by considering
Bernoulli distributed target $y$ and Gaussian mixture data $x$, the explicit
_and/or_ optimal solution of which remains largely open in the IT community
[20].

Unlike most existing works on the applications of IB in ML which seek the
tradeoff between the relevance and complexity of NN, we consider, in this
paper, the secrecy issue and aim to derive _closed-form achievable_ solution
to the IB problem that provides direct secrecy guarantee on the obtained
representation $t(x)$, under the above setting. More precisely, given the
input random variable $x$, by using the IB method we intend to characterize
the fundamental tradeoff between the secrecy leakage rate of $x$ when
observing $t(x)$ and the relevance between $t(x)$ and the target $y$.111The
information-theoretic secrecy leakage rate of $x$ while observing $t(x)$ is
measured via the mutual information between $x$ and $t(x)$ [23, 24]. A natural
application of the considered model could be in federated learning (FL) [25],
where a notable advantage of FL with respect to other distributed learning
scenarios, is the security protection on the training node’s raw local data
against the server.

Interestingly, the proposed (variational) IB solution takes a similar form to
the output weight of a neural network model with tangent hyperbolic
activation. Built upon this fortuitous connection, we further propose an IB-
inspired heuristic training approach of $\tanh$ neural nets, the
test/generalization performance of which, as well as the associated
_performance–secrecy tradeoff_ , thanks to its explicit solution, can be
_precisely_ assessed in the infinite data limit.

Despite being derived here for Bernoulli target and Gaussian mixture data of
natural interest in classification (which is, as shall be re-emphasized,
already an open information-theoretic problem), an unexpected satisfactory
performance is observed for the proposed IB scheme when applied on real-world
datasets, suggesting possibly wider applicability for the proposed approach.
Looking forward, we expect that our analysis will open the door to a closer
and deeper connection between the field of information theory and machine
learning, which will demystify the seemingly striking empirical observations
in, say, modern large-scale ML models such as DNNs.

###  I-A Our contribution

Our main contributions are the following:

  * (i)

We derive, in Theorem 1, a _closed-form_ solution to the open IB problem with
Bernoulli source and Gaussian mixture data. This is, to the best of our
knowledge, the first time an achievable _closed-form_ solution is proposed to
IB problem under this setting.

  * (ii)

Based on the derived IB explicit solution, we propose a heuristic algorithm
that solves the IB problem _at a distributional level_. This further allows us
to characterize, in Corollary 1, the _precise_ “performance–secrecy” tradeoff
on Gaussian mixture classification with the proposed approach.

  * (iii)

Numerical experiments on both synthetic Gaussian mixture and real-world non-
Gaussian data are performed, showing the satisfactory performance of the
proposed analytic IB scheme when compared to the (numerically) optimal
solution given in [1] or the popular Information Dropout approach [22].

###  I-B Related works

Here, we provide a brief review of related previous efforts.

#### IB and privacy funnel.

An information-theoretic problem closely related to the considered IB secrecy
problem is privacy funnel (PF) [26]. With the Markov chain $y\longrightarrow
x\longrightarrow t(x)$, the PF problem seeks to extract a representation
$t(x)$ from the data $x$, where the leakage rate of $y$ observing $t(x)$ is
minimized while the relevance between $t(x)$ and $x$ is no less than a given
number. Obviously, the optimal PF rate is a lower bound of the IB rate [27,
28].

#### Information theoretic approach to secrecy in ML.

Information-theoretic tools have been widely used in ML to characterize the
fundamental tradeoff between secrecy and learning accuracy [29, 30, 31] and to
design the protocols securely aggregating the users’ updated model at the
server in FL (i.e., secure aggregation) [32, 33, 34, 35, 36]. In this vein, we
only consider, in this paper, a single training node and design the
representation of its local data under some secrecy constraints. The results
obtained in this paper can be perfectly combined with the above secure
aggregation protocols for a FL system.

#### Variational IB and neural nets.

The connection between the IB approach and deep neural nets was first made in
[14], in which the authors stated that any DNN can be quantified by the mutual
information between the layers and the input and output variables. In
addition, the goal of any supervised learning can be translated as an IB
problem. Due to the complexity in deriving closed-form solutions, various
efforts have been made to obtain algorithmic variational IB solutions, see,
for example [15, 37, 38, 22, 39]. The main difference between this paper and
the aforementioned works is that we aim to derive _closed-form achievable_
bounds for the IB problem, which does not need to run an algorithm to measure
the performance.

#### Precise performance analysis of neural nets.

As a consequence of its mathematically involved form and its successful
applications in various fields of science and technology, the theory of NN is
receiving unprecedented research interest. Built upon recent advances in
functional analysis [40], optimization theory [41], high-dimensional
statistics [42], and/or random matrix theory [43], NN theories (e.g., the
_double descent_ [44] and the _neural tangent kernel_ [40]) have been proposed
to improve the practical design of these large-scale ML systems.

###  I-C Notations and organization of the paper

We denote scalars by lowercase letters and vectors by bold lowercase. For a
random variable $x$ defined on the probability space $(\Omega,\mathcal{F},p)$,
we denote ${\mathbb{E}}[x]$ and $h(x)$ the expectation and differential
entropy of $x$, respectively. For two random variables $x$ and $y$, we use
$I(x;y)$ to denote their mutual information.

This paper is organized as follows. The system model of the IB problem under
study is introduced in Section II. Our main technical results on an achievable
closed-form solution to the IB problem is given in Section III, together with
an IB-inspired heuristic NN training approach. Numerical results are provided
in Section IV to validate the proposed IB scheme, showing a better
_performance–secrecy tradeoff_ can be achieved with our approach. Finally,
conclusion and future perspective are placed in Section V.

##  II System Model

Consider the following binary classification problem: for label
$y\in{\mathbb{R}}$ drawn from a symmetric Bernoulli distribution (that is,
$y=\pm 1$ with $\Pr(y=-1)=\Pr(y=1)=1/2$), the data vector
$\mathbf{x}=(x_{1},\ldots,x_{d_{0}})\in{\mathbb{R}}^{d_{0}}$ follows a
Gaussian mixture model (GMM) and depends on the label $y$ in such as way that

$\mathbf{x}=y\cdot\bm{\beta}+\bm{\epsilon},$ (2)

for some _deterministic_ vector
$\bm{\beta}=(\beta_{1},\ldots,\beta_{d_{0}})\in{\mathbb{R}}^{d_{0}}$ and
Gaussian random noise
$\bm{\epsilon}=(\epsilon_{1},\ldots,\epsilon_{d_{0}})\sim\mathcal{N}(\mathbf{0},\mathbf{I}_{d_{0}})$.

Consider the setting in which the data vector $\mathbf{x}$ contains the
privacy of user, we are interested in constructing an intermediate
representation $\mathbf{t}=(t_{1},\ldots,t_{d})\in{\mathbb{R}}^{d}$ of
$\mathbf{x}$ that

  * (i)

contains sufficiently rich information (so with $I(y;\mathbf{t})$ large) on
the source random variable $y$ for, say downstream classification; and

  * (ii)

the secrecy leakage of $\mathbf{x}$ is small,

by solving the following constrained optimization problem (which is, in fact,
an IB problem)

$\displaystyle\max_{p(\mathbf{t}|\mathbf{x})}\quad$ $\displaystyle
I(y;\mathbf{t})$ (3a) s.t. $\displaystyle I(\mathbf{x};\mathbf{t})\leq R,$
(3b)

for a given $R\geq 0$ representing the secrecy leakage rate of $\mathbf{x}$
when one observes $\mathbf{t}$ [23, 24].

Here we focus on the setting of $d=d_{0}$, and the case $d<d_{0}$ that is of
more computational interest will be briefly discussed in Section V. Due to the
difficulty to derive analytic results for (3), we propose an achievable entry-
wise strategy,

$x_{i}=y\beta_{i}+\epsilon_{i},\quad\epsilon\sim\mathcal{N}(0,1),$ (4)

with222The idea of applying $\tanh$ function is inspired from that the MMSE
estimation of the binary source $y_{i}$ given the Gaussian mixture $x_{i}$ is
$\tanh{(\beta x_{i})}$ [45].

$t_{i}|x_{i}\sim\mathcal{N}\left(\alpha_{i}\tanh(\beta_{i}x_{i}),1\right).$
(5)

For each $i\in[1:d_{0}]$, we determine the coefficient $\alpha_{i}$ by solving
the following variational IB problem,

$\displaystyle\max_{\alpha_{i}}\quad$ $\displaystyle I(y;t_{i})$ (6a) s.t.
$\displaystyle I(x_{i};t_{i})\leq R_{i},$ (6b) $\displaystyle
t_{i}|x_{i}\sim\mathcal{N}\left(\alpha_{i}\tanh(\beta_{i}x_{i}),1\right),$
(6c)

for some $R_{i}\geq 0$ where $R_{1}+\cdots+R_{d_{0}}=R$. In Appendix A, we
prove that any achievable solution of (6) is also an achievable solution of
the problem in (3); i.e., any $\\{p(t_{i}|x_{i}):i\in[1:d_{0}]\\}$ satisfying
the constraints (6b) and (6c) also leads a distribution
$p(\mathbf{t}|\mathbf{x})$ satisfying the secrecy constraint (3b).

In the remainder of the paper, we drop the index $i$ for notational
convenience. Note that the formulation in (5) of the $i$th entry of the
intermediate representation $\mathbf{t}\in{\mathbb{R}}^{d}$ resembles that
obtained from the $i$th neuron of a fully-connected neural net with $\tanh$
activation and additive Gaussian random noise of unit variance, and it remains
to determine, for fixed $\beta$, the weight parameter $\alpha\geq 0$ to solve
(6). This is visually illustrated in Figure 1.

$\tanh$$x$$\mathcal{N}(0,1)$$t$$\beta$$\alpha$ Figure 1: Illustration of the
proposed scheme with $\tanh$ activation.

We also note that the injection of Gaussian noise $\varepsilon$ in the
proposed (variational) scheme above is in line with the intuition of noisy
DNNs framework introduced in [46], which yields equally good generalization
performance compared to deterministic nets.

##  III Main Results

A closed-form solution to the vanilla IB problem in (3), or to the proposed
variational IB problem in (6), beyond the case of jointly Gaussian $(x,y)$ is,
to the best of our knowledge, still an open problem [20]. In the sequel, we
will briefly discuss the main technical challenges in obtaining an explicit
solution to (6), as well as our proposed approach to address these challenges.

###  III-A Analytic achievable solution to variational IB

To solve (6), we first develop the objective mutual information as

$\displaystyle I(y;t)=h(t)-h(t|y),$ (7a)
$\displaystyle=\\!\\!-\\!\int_{\\!-\\!\infty}^{\infty}\\!\frac{p(t|y\\!=\\!1)\\!+\\!p(t|y\\!=\\!-1)}{2}\\!\ln\\!\frac{p(t|y\\!=\\!1)\\!+\\!p(t|y\\!=\\!-1)}{2}\\!dt$
$\displaystyle~{}~{}~{}~{}~{}+\int_{-\infty}^{\infty}\frac{p(t|y=1)}{2}\ln
p(t|y=1)dt$
$\displaystyle~{}~{}~{}~{}~{}+\int_{-\infty}^{\infty}\frac{p(t|y=-1)}{2}\ln
p(t|y=-1)dt,$ (7b)

where two conditional probabilities $p(t|y=1)$ and $p(t|y=-1)$ are given by

$\displaystyle p(t|y=1)$
$\displaystyle=\int_{-\infty}^{\infty}\frac{1}{2\pi}\exp\left(-\frac{(x-1)^{2}}{2}\right)\exp\left(-\frac{(t\\!-\\!\alpha\hat{x})^{2}}{2}\right)\\!dx,$
(8a) $\displaystyle p(t|y=-1)$
$\displaystyle=\int_{-\infty}^{\infty}\frac{1}{2\pi}\exp\left(-\frac{(x+1)^{2}}{2}\right)\exp\left(-\frac{(t\\!-\\!\alpha\hat{x})^{2}}{2}\right)\\!dx,$
(8b)

where we use the shortcut $\hat{x}:=\tanh{(\beta x)}$.

It can be seen from (7) and (8) that given the system parameter $\beta$, the
mutual information $I(y;t)$ only depends on $\alpha$. For the further ease of
notation, we define $I(\alpha)$ as the mutual information $I(y;t)$ given
$\alpha$. Clearly, if $\alpha$ satisfies the constraints in (6b) and (6c),
$I(\alpha)$ is a lower bound (i.e., achievable bound) of the optimal mutual
information $I^{\star}(y;t)$ in (6).

Compared to the existing works [47, 15, 48, 49, 50, 22], we derive, for the
first time, analytic achievable bounds (in closed-form) for the variational IB
problem in (6) beyond the jointly Gaussian setting.

The main ingredients of our solution is as follows:

  * (i)

Due to the mathematically involved form of mutual information, we propose two
upper bounds of $I(x;t)$, which are then forced to equal $R$. As such,
$I(x;t)$ is upper bounded by $R$ satisfying the secrecy constraint in (6b).
The upper bounds on $I(x;t)$ boil down to finding lower bounds on
$\ln(\cosh{\alpha t})$ by applying the Bernoulli variational distribution of
$\tanh{\beta x}$. Since $\ln(\cosh(x))\geq\sqrt{1+x^{2}}-1,~{}\forall~{}x\geq
0$, the first bound can provide an upper bound on $I(x;t)$ for all $R$, while
the second bound is based on $\ln(\cosh(x))\geq x-\ln 2,~{}\forall~{}x\geq 0$,
which is tighter than the first lower bound on $\ln(\cosh{x})$ when $x$ is
relatively large, resulting in a tighter upper bound on $I(x;t)$. However, the
second bound only works if $R$ is not less than $\ln 2$.

  * (ii)

We then solve the equation where each proposed upper bound of $I(x;t)$ is
equal to $R$, to obtain the _analytic solution_ of $\alpha$.

  * (iii)

Finally, the value of the mutual information $I(y;t)$ is obtained by taking
the value of $\alpha$.

######  Theorem 1 (Lower bounds of $I^{\star}(y;t)$ in closed-form).

For the variational IB problem defined in (6) with symmetric Bernoulli $y$ and
$x|y\sim\mathcal{N}(y\beta,1)$, the optimal rate $I^{\star}(y;t)$ is lower
bounded by $\max\\{I(\alpha_{\text{lb}_{1}}),I(\alpha_{\text{lb}_{2}})\\}$ if
$R\geq\ln 2$, and lower bounded by $I(\alpha_{\text{lb}_{1}})$ otherwise, by
defining

$\displaystyle\alpha_{\text{lb}_{1}}\\!$
$\displaystyle=\\!\small{\sqrt{\\!\frac{(R\\!-\\!1)(1\\!\\!+\\!\\!f(\beta))\\!+\\!\\!\sqrt{((1\\!\\!+\\!\\!f(\beta))^{2}\\!\\!+\\!4g\\!^{2}(\beta)(R^{2}\\!\\!-\\!\\!2R))}}{((1\\!+\\!f(\beta))^{2}\\!-\\!4g^{2}(\beta))/2}}},$
(9a) $\displaystyle\alpha_{\text{lb}_{2}}\\!$
$\displaystyle=\\!\sqrt{\frac{R-\ln
2}{\frac{1}{2}+\frac{f(\beta)}{2}-g(\beta)}},~{}~{}~{}\text{if}~{}R\geq\ln 2,$
(9b)

where, for the ease of notation, we define $I(\alpha)$ the mutual information
$I(y;t)$ given $\alpha$, $\hat{x}:=\tanh{(\beta x)}$, and333Note that
$f(\beta)$ and $g(\beta)$ are constants given $\beta$.

$\displaystyle f(\beta)$
$\displaystyle=\int_{-1}^{1}p(\hat{x})\hat{x}^{2}d\hat{x},$ (10a)
$\displaystyle g(\beta)$
$\displaystyle=\int_{-1}^{1}p(\hat{x})|\hat{x}|d\hat{x}.$ (10b)

###### Proof of Theorem 1.

See Appendix B. ∎

To the best of our knowledge, Theorem 1 provide, for the first time, analytic
achievable solutions to the variational IB problem in (6), and thus to the
original IB problem in (3). For known signal strength $\beta$ of the input
$x$, $f(\beta)$ and $g(\beta)$ are constants, and thus, for any given secrecy
budge $R$, the analytic solution $\alpha$ is given in (9), which further leads
to achievable bounds of the IB optimal rate $I^{\star}(y;t)$.

The analytic achievable solution given in Theorem 1 can be directly applied to
remote source coding in communications. As illustrated in Figure 2, consider
$y=\pm 1$ as the output of a Binary Phase Shift Keying (BPSK) modulation and
$x$ as the output of a Gaussian channel, and that a remote node (e.g., a
relay) receives the channel output and takes a further compression on the
channel output to attain the (optimal) tradeoff between the compression and
the relevance rates.

Figure 2: Gaussian channel with BPSK input and channel output compression.

Its theoretical connection to secrecy-preserving design and/or training of DNN
models are, however, less immediate. In the following subsection, inspired by
the similar form between the analytic IB solution in Theorem 1 and fully-
connected neural network model with tangent hyperbolic activation (as
discussed at the end of Section II), we introduce an IB heuristic training
approach of $\tanh$ nets, and show, in Corollary 1, how our theoretical
results apply to provide asymptotic characterization of classification
performance of the obtain network in the infinite data limit.

###  III-B IB heuristic training scheme of NN and its asymptotic performance
analysis

Note that the analytic (variational) IB solution proposed in Theorem 1 depends
on the _deterministic_ signal strength (or signal-to-noise ratio) $\bm{\beta}$
of the input $\mathbf{x}$, which is a priori _unknown_ in practice, but can be
consistently estimated from (a huge amount of) labelled training data
$[(\mathbf{x}_{i},y_{i})]_{i=1}^{n}$ for $n$ large. With such an estimate
$\hat{\bm{\beta}}$ (which can be seen as the input weights of the network) and
the (entry-wise) secrecy budge $R_{1},\ldots,R_{n}\geq 0$ such that
$R_{1}+\cdots+R_{d_{0}}=R$, we can then use the closed-form solution in (9) of
Theorem 1 to obtain the $\alpha_{i},\forall i\in\\{1,2,...,d_{0}\\}$, which
are, in essence, the output weights of the network shown in Figure 1. This
completes the training process of the network. During the testing process, for
an _independent_ test datum $\mathbf{x}$, we use the trained network (with
input weights $\hat{\bm{\beta}}$ and output weights
$\bm{\alpha}:=(\alpha_{1},\ldots,\alpha_{d_{0}})$ now fixed) to get the
intermediate representation $\mathbf{t}$ of $\mathbf{x}$ as
$\mathbf{t}|\mathbf{x}\sim\mathcal{N}(\bm{\alpha}\tanh(\bm{\beta}\odot\mathbf{x}),\mathbf{I}_{d_{0}})$,
with $\bm{\beta}\odot\mathbf{x}$ the (entry-wise) Hadamard product between
$\bm{\beta}$ and $\mathbf{x}$. The corresponding label $y$ of $\mathbf{x}$ can
then be estimated, e.g., by evaluating the entry-wise behavior of the
intermediate representation $\mathbf{t}$.

This IB inspired NN design is detailed in Algorithm 1.

Input: training data vectors
$\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\in{\mathbb{R}}^{d_{0}}$ of size $n$, the
associated labels $y_{1},\ldots,y_{n}\in[\pm 1]$, test data vector
$\mathbf{x}\in{\mathbb{R}}^{d_{0}}$, and entry-wise secrecy budge
$R_{1},\ldots,R_{n}\geq 0$ such that $R_{1}+\cdots+R_{d_{0}}=R$.

Output: predicted label $\hat{y}$ associated to $\mathbf{x}$.

Estimate the signal strength $\bm{\beta}$ with
$\hat{\bm{\beta}}=\frac{1}{n}\sum_{j=1}^{n}y_{j}\mathbf{x}_{j}$;

for $i=1$ to $d_{0}$ do

training: solve the variational IB problem in (6) with $\hat{\beta}_{i}$ and
$R_{i}$, to get $\alpha_{i}$ as given in (9) of Theorem 1;

testing: draw intermediate representation as
$t_{i}\sim\mathcal{N}(\alpha_{i}\tanh(\hat{\beta}_{i}x_{i}),1)$, with
$\hat{\beta}_{i}$ and $x_{i}$ the $i$th entry of $\hat{\bm{\beta}}$ and the
test datum $\mathbf{x}$, respectively;

end for

predict label as $\hat{y}={\rm sign}(\sum_{i=1}^{d_{0}}t_{i})$;

return $\hat{y}$.

Algorithm 1 IB heuristic training of $\tanh$ network

In the following result, we show how Theorem 1 applies to characterize the
(asymptotic) misclassification rate of Algorithm 1, and thus, to provide an
_explicit performance–secrecy_ tradeoff in the context of Gaussian mixture
classification.

######  Corollary 1 (Asymptotic performance of Algorithm 1 for $d_{0}=1$).

Consider i.i.d. symmetric Bernoulli labels $y_{1},\ldots,y_{n}\in\\{\pm 1\\}$,
and the training data $x_{1},\ldots,x_{n}\in{\mathbb{R}}$ _independently_
drawn from the Gaussian mixture model in (2) with $d_{0}=1$ and
$|\beta|<\infty$, then, for test datum $x$ with associated label $y$ and
secrecy budge $R\geq 0$, one has, as $n\to\infty$, that the asymptotic
misclassification rate of Algorithm 1 is given by

$\Pr\left(\hat{y}\neq
y\right)\to\frac{1}{2}\int_{0}^{\infty}p(t|y=-1)dt+\frac{1}{2}\int_{-\infty}^{0}p(t|y=1)dt,$

with $\hat{y}$ the output of Algorithm 1, and conditional probabilities
$p(t|y=\pm 1)$ given in (8).

###### Proof of Corollary 1.

By the strong law of large numbers, we have, for samples $x_{1},\ldots,x_{n}$
drawn from (2) with associated labels $y_{1},\ldots,y_{n}$ that

$\hat{\beta}:=\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}\to\beta,$ (11)

almost surely as $n\to\infty$. For $\hat{\alpha}$ obtained from Algorithm 1
with training sample $[(x_{i},y_{i})]_{i=1}^{n}$, it follows from the
continuous mapping theorem that $\hat{\alpha}\to\alpha$, with $\alpha$ defined
similarly as $\hat{\alpha}$, but with the true $\beta$ instead of
$\hat{\beta}$ in (9) of Theorem 1, Then, conditioned on the test datum $x$
(which is _independent_ of all training $x_{i}$s and $y_{i}$s),

$t\to\mathcal{N}\left(\alpha\tanh(\beta x),1\right),$ (12)

in law as $n\to\infty$, the limiting p.d.f. of which is given in (8). Since
Algorithm 1 predicts $\hat{y}={\rm sign}(t)$ and , we have

$\displaystyle\Pr\left(\hat{y}\neq
y\right)=\frac{1}{2}\Pr(\hat{y}>0|y=-1)+\frac{1}{2}\Pr(\hat{y}<0|y=1)$
$\displaystyle\to\frac{1}{2}\int_{0}^{\infty}p(t|y=-1)dt+\frac{1}{2}\int_{-\infty}^{0}p(t|y=1)dt,$

as $n\to\infty$, with $p(t|y=\pm 1)$ given in (8). This concludes the proof of
Corollary 1. ∎

$0$$0.5$$1$$1.5$$2$$2.5$$3$$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$0.45$$0.5$Secrecy
Leakage Rate $R$Asymptotic Misclassification
Rate$\max\\{I(\alpha_{\text{lb}_{1}}),I(\alpha_{\text{lb}_{2}})\\}~{}~{}\beta=0.5$$\max\\{I(\alpha_{\text{lb}_{1}}),I(\alpha_{\text{lb}_{2}})\\}~{}~{}\beta=0.7$$\max\\{I(\alpha_{\text{lb}_{1}}),I(\alpha_{\text{lb}_{2}})\\}~{}~{}\beta=\sqrt{2}$
Figure 3: Asymptotic misclassification rate versus secrecy leakage rate $R$
for the proposed IB lower bound in Theorem 1, for signal strength
$\beta\in[0.5,0.7,\sqrt{2}]$. The optimal misclassification rates (achieved
with $t=x$) are displayed in dashed lines.

Figure 3 depicts the explicit _performance–secrecy_ tradeoff of the proposed
IB approach obtained from Theorem 1 and Corollary 1, by showing the
(asymptotic) misclassification rate of GMM data as a function of the secrecy
budge $R$, for different signal strength $\beta=0.5$, $\beta=0.7$, and
$\beta=\sqrt{2}$. We see that the misclassification rate $\Pr(y\neq\hat{y})$
decreases rapidly as the secrecy leakage rate $R$ increases. This allows us to
trade (limited) secrecy leakage for more satisfactory classification
performance. Moreover, for $R=0$, the optimal (in an IB sense) intermediate
representation $t$ should be independent of the input $x$, which, being a
random guess of $y$, leads to a misclassification rate of $50\%$. On the other
hand, for $R\to\infty$, the optimal solution is $t=x$, with associated
misclassification rate given by
$\frac{1}{2}\int_{0}^{\infty}p(x|y=-1)dx+\frac{1}{2}\int_{-\infty}^{0}p(x|y=1)dx$,
which is in fact the performance of classifying the raw GMM data and decreases
as $\beta$ increases. It is interesting to note from Figure 3 that, for large
signal strength such as $\beta=\sqrt{2}$, near-optimal classification
performance can be obtained as long as $R\geq 1$, and it is unwise to set a
(much) larger secrecy budge for the sake of better performance in this case.

##  IV Numerical Evaluations and Discussions

In this section, we provide numerical experiments to validate our theoretical
results in Theorem 1, on both synthetic data (such as univariate and
multivariate Gaussian mixture data) and real-world data (e.g., the popular
MNIST handwritten digit data [51]). Despite derived here for GMM data, our
approach yields satisfactory performance on real-world _non-Gaussian_ features
obtained from the MNIST dataset, suggesting possibly wider applicability for
the proposed analytic IB scheme.

Numerical results show our proposed closed-form achievable bounds are close to
the (numerically) optimal solution of the (generalized) Blahut-Arimoto (BA)
algorithm introduced in [1], not only in the univariate case but also in the
multivariate setting, and yield better results compared to existing IB
approaches such as the popular Information Dropout method [22].

$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$1.6$$1.8$$2$$0$$5\cdot
10^{-2}$$0.1$$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$I(x;t)$$I(y;t)$BA
Alg.$\max\\{I(\alpha_{\text{lb}_{1}}),I(\alpha_{\text{lb}_{2}})\\}$Information
Dropout Figure 4: Three methods compared in terms of the objective mutual
information $I(y;t)$ and the constraint $I(x;t)$ for Bernoulli source and
univariate mixture Gaussian observation when $\beta=1$.
$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$I(x;t)$$I(y;t)$BA
Alg.$\max\\{I(\alpha_{\text{lb}_{1}}),I(\alpha_{\text{lb}_{2}})\\}$Information
Dropout Figure 5: Three methods compared with respect to the objective mutual
information $I(y;t)$ and the constraint $I(x;t)$ for Bernoulli source and
univariate mixture Gaussian data when $\beta=\sqrt{2}$.
$0$$1$$2$$3$$4$$5$$6$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$\sum_{i=1}^{3}I(y;x_{i})$$I(y;\mathbf{t})$BA
Alg.$\max\\{I(\alpha_{\text{lb}_{1}}),I(\alpha_{\text{lb}_{2}})\\}$Information
Dropout Figure 6: Three methods compared with the respect to the objective
mutual information $I(y;\mathbf{t})$ and the constraint
$\sum_{i=1}^{3}I(x_{i};t_{i})$ for Bernoulli source and three-dimensional
mixture multivariate Gaussian observation when $\beta=(0.9,1,1.1)$.
$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$\sum_{i=1}^{3}I(y;x_{i})$$\sum_{i=1}^{3}I(y;t_{i})$BA
Alg.$\max\\{I(\alpha_{\text{lb}_{1}}),I(\alpha_{\text{lb}_{2}})\\}$Information
Dropout Figure 7: Three methods compared with the respect to the objective
mutual information $I(y;\mathbf{t})$ and the constraint
$\sum_{i=1}^{3}I(x_{i};t_{i})$ for dimension-reduced MNIST data (class $4$
versus class $9$).

In the following, we briefly discuss the (generalized) BA algorithm [1] and
the Information Dropout method [22]. These two methods are designed to the
following equivalent Lagrange form of the IB problem in (1)

$\displaystyle\min_{p(t|x)}\quad$ $\displaystyle I(x;t)-\lambda I(y;t),$ (13)

where $\lambda$ is a predefined tradeoff parameter. Inspired by the rate
distortion theory calculation and by discretizing the continuous space of $x$
and $t$, [1] proposed to apply the BA algorithm [52, 53] to solve the
optimization problem in (13) numerically, by alternating among the three
probability distributions $p(t)$, $p(y|t)$, and $p(t|x)$, starting from random
initialization. With the three distributions, the objective mutual information
$I(y;t)$ and $I(x;t)$ can then be computed. [1] also gave a short proof of the
convergence of the BA algorithm, which, however, does _not_ necessarily imply
the uniqueness of the solution.

The Information Dropout method introduced by [22] proposes to design the
intermediate representation $t$ as $t=f_{1}(x)\odot\eta$, where $f_{1}(x)$ is
the output of a fully-connected NN with input $x$, and $\eta$ follows the log-
normal distribution, i.e., $\eta\sim\log\mathcal{N}(0,f_{2}^{2}(x))$, with
variance parameter $f_{2}(x)$ also given by the output of a fully-connected NN
with input $x$. Here, we use single-hidden-layer neural network models for
both $f_{1}$ and $f_{2}$, i.e., $f_{1}(x)=\sigma(w_{1}x)+1$ and
$f_{2}(x)=\sigma(w_{2}x)$, with $\sigma(t)=(1+\exp(-t))^{-1}$ the logistic
sigmoid function. An additional bias term $b=1$ is added to $f_{1}(x)$ to
avoid $0$ for calculating the conditional probability $p(t|x)$. Then, brute-
force search (over the space of $w_{1}$ and $w_{2}$) can be applied to solve
the optimization problem in (13), and to further determine $I(y;t)$ and
$I(x;t)$. In the simulation, the discretization step in each dimension for all
methods is set as $\frac{1}{20}$.

Figure 4 and 5 compare the proposed _explicit_ lower bound given in Theorem 1
on the IB optimal rate $I^{\star}(y;t)$, to those obtained from the BA
algorithm (which serves as a numerical “proxy” of the IB optimal rate
$I^{\star}(y;t)$) and the Information Dropout method, for Bernoulli source
label and _univariate_ Gaussian mixture data with $\beta=1$ and
$\beta=\sqrt{2}$. Figure 6 extends the above experiments to multivariate
setting with $\mathbf{\beta}=(0.9,1.0,1.1)$, by solving the IB problem in an
entry-wise manner. In all three figures, we consistently observe a close match
between our proposed lower bounds and the numerically optimal BA solution when
the secrecy budge $R$ is relatively large. And the gap between the BA
algorithm and our proposed lower bounds (for large $R$ particularly) decreases
as the signal strength $\beta$ becomes larger. However, a non-negligible gap
is still observed for not-so-large $R$.

The Information Dropout method performs slightly better than the proposed
approach in the small $R$ region, but worse for $R$ large. This also shows
that within the Information Dropout framework, the single-hidden-layer NN
model, despite being universal approximators with a sufficiently large number
of neurons [54], is less efficient in solving the IB problem. This is also
(empirically) supported by the fact that some (large) value of mutual
information $I(x;t)$ _cannot_ be reached with the Information Dropout approach
in Figure 4–6.

From a computational perspective, the proposed analytic IB scheme is almost
computation-free, while the BA and the Information Dropout approach both
involve rather heavy optimization (of the discretized distributions or of the
network weights).

We also apply the derived analytic IB scheme in Theorem 1 to real-world (so
non-Gaussian) data drawn from the popular MNIST database [51]. To reduce the
computational complexity of BA algorithm (which grows exponentially as the
dimension), we reduce the dimension of the original vectorized MNIST images
(of dimension $784$) by randomly projecting through a random Gaussian matrix
(of size $3$ by $784$) to obtain MNIST features of dimension $d_{0}=3$.

In Figure 7 we compare the objective mutual information $I(y;\mathbf{t})$
versus the secrecy leakage rate $\sum_{i}I(x_{i};t_{i})$ for dimension-reduced
MNIST features444See Appendix C for the details of MNIST data pre-processing.
using the aforementioned methods. We see, perhaps surprisingly, that the
performance of the proposed analytic IB scheme on real-world non-Gaussian data
is consistent with that on the synthetic Gaussian mixture data.

##  V Conclusion, Limitation, and Future Perspective

In this paper, we provided a closed-form solution to the IB problem with
Bernoulli source and Gaussian mixture data. The theoretical result is based on
the scalar case, and we further extended it to the multidimensional case.
Numerical experiments have been performed to validate the theoretical results.
The proposed results can be also applied to the remote source coding problem
in communications or to the secrecy-preserving heuristic training scheme of
DNN models as in Algorithm 1.

However, when we extend it to the multidimensional case, the key factor for
our proposed methods is $d=d_{0}$. In this case, there is a gap if we operate
on each dimension of $\mathbf{x}$ independently, since some information will
be lost. How to optimize in the vector space might be an interesting problem
to think about. In addition, considering the case where $d<d_{0}$, a direct
way is to delete some elements in $\mathbf{x}$ that are connected to small
$\beta_{i}$ to force the dimensions of $\mathbf{x}$ and $\mathbf{t}$ to be
equal. It is also an interesting open problem to find better compression
strategies than simple deletion.

## References

  * [1] N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” _arXiv_ , 2000.
  * [2] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet classification with deep convolutional neural networks,” _Communications of the ACM_ , vol. 60, no. 6, pp. 84–90, 2017.
  * [3] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. v. d. Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, “Mastering the game of Go with deep neural networks and tree search,” _Nature_ , vol. 529, no. 7587, pp. 484–489, 2016.
  * [4] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems_ , vol. 30. Curran Associates, Inc., 2017. [Online]. Available: https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * [5] J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” in _Advances in Neural Information Processing Systems_ , vol. 33. Curran Associates, Inc., 2020, pp. 6840–6851. [Online]. Available: https://proceedings.neurips.cc/paper/2020/file/4c5bcfec8584af0d967f1ab10179ca4b-Paper.pdf
  * [6] I. Goodfellow, Y. Bengio, and A. Courville, _Deep Learning_ , ser. Adaptive Computation and Machine Learning series, F. Bach, Ed. MIT Press, 2016. [Online]. Available: http://www.deeplearningbook.org
  * [7] R. Battiti, “Using mutual information for selecting features in supervised neural net learning,” _IEEE Transactions on Neural Networks_ , vol. 5, no. 4, pp. 537–550, 1994.
  * [8] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative Adversarial Nets,” in _Advances in Neural Information Processing Systems_ , ser. NIPS’14, vol. 27. Curran Associates, Inc., 2014, pp. 2672–2680. [Online]. Available: https://proceedings.neurips.cc/paper/2014/file/5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf
  * [9] M. Arjovsky, S. Chintala, and L. Bottou, “Wasserstein generative adversarial networks,” in _Proceedings of the 34th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, D. Precup and Y. W. Teh, Eds., vol. 70. PMLR, 06–11 Aug 2017, pp. 214–223. [Online]. Available: https://proceedings.mlr.press/v70/arjovsky17a.html
  * [10] X. Chen, Y. Duan, R. Houthooft, J. Schulman, I. Sutskever, and P. Abbeel, “Infogan: Interpretable representation learning by information maximizing generative adversarial nets,” in _Advances in Neural Information Processing Systems_ , vol. 29. Curran Associates, Inc., 2016. [Online]. Available: https://proceedings.neurips.cc/paper/2016/file/7c9d0b1f96aebd7b5eca8c3edaa19ebb-Paper.pdf
  * [11] G. Biau, B. Cadre, M. Sangnier, and U. Tanielian, “Some theoretical properties of GANS,” _The Annals of Statistics_ , vol. 48, no. 3, pp. 1539–1566, 2020.
  * [12] R. D. Hjelm, A. Fedorov, S. Lavoie-Marchildon, K. Grewal, P. Bachman, A. Trischler, and Y. Bengio, “Learning deep representations by mutual information estimation and maximization,” in _International Conference on Learning Representations_ , 2019. [Online]. Available: https://openreview.net/forum?id=Bklr3j0cKX
  * [13] P. Bachman, R. D. Hjelm, and W. Buchwalter, “Learning representations by maximizing mutual information across views,” in _Advances in Neural Information Processing Systems_ , vol. 32. Curran Associates, Inc., 2019. [Online]. Available: https://proceedings.neurips.cc/paper/2019/file/ddf354219aac374f1d40b7e760ee5bb7-Paper.pdf
  * [14] N. Tishby and N. Zaslavsky, “Deep Learning and the Information Bottleneck Principle,” in _2015 IEEE Information Theory Workshop (ITW)_ , ser. 2015 IEEE Information Theory Workshop (ITW), 2015, pp. 1–5.
  * [15] A. A. Alemi, I. Fischer, J. V. Dillon, and K. Murphy, “Deep variational information bottleneck,” in _International Conference on Learning Representations_ , 2017. [Online]. Available: https://openreview.net/forum?id=HyxQzBceg
  * [16] R. Shwartz-Ziv and N. Tishby, “Opening the black box of deep neural networks via information,” _arXiv preprint arXiv:1703.00810_ , 2017.
  * [17] A. M. Saxe, Y. Bansal, J. Dapello, M. Advani, A. Kolchinsky, B. D. Tracey, and D. D. Cox, “On the information bottleneck theory of deep learning,” _Journal of Statistical Mechanics: Theory and Experiment_ , vol. 2019, no. 12, p. 124020, 2019.
  * [18] R. A. Amjad and B. C. Geiger, “Learning representations for neural network-based classification using the information bottleneck principle,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 42, no. 9, pp. 2225–2239, 2019.
  * [19] A. Zaidi, I. Estella-Aguerri, and S. Shamai, “On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views,” _Entropy 2020_ , vol. 151, no. 22, 2020.
  * [20] Z. Goldfeld and Y. Polyanskiy, “The Information Bottleneck Problem and its Applications in Machine Learning,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 1, pp. 19–38, 2020.
  * [21] R. Shwartz-Ziv and N. Tishby, “Opening the Black Box of Deep Neural Networks via Information,” _arXiv_ , 2017.
  * [22] A. Achille and S. Soatto, “Information Dropout: Learning Optimal Representations Through Noisy Computation.” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 40, no. 12, pp. 2897–2905, 2018\.
  * [23] . D. Wyner, “The wire-tap channel,” _Bell Syst. Tech. J._ , vol. 54, p. 1355–1387, 1975.
  * [24] I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” _IEEE Trans. Inf. Theory_ , vol. 24, no. 3, p. 339–348, 1978\.
  * [25] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [26] A. Makhdoumi, S. Salamatian, N. Fawaz, and M. Médard, “From the information bottleneck to the privacy funnel,” in _2014 IEEE Information Theory Workshop (ITW 2014)_ , 2014, pp. 501–505.
  * [27] S. Asoodeh and F. P. Calmon, “Bottleneck problems: An information and estimation-theoretic view,” _Entropy_ , vol. 22, no. 11, 2020.
  * [28] H. Hsu, S. Asoodeh, S. Salamatian, and F. P. Calmon, “Generalizing bottleneck problems,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , 2018, pp. 531–535.
  * [29] M. Bertran, N. Martinez, A. Papadaki, Q. Qiu, M. Rodrigues, G. Reeves, and G. Sapiro, “Adversarially learned representations for information obfuscation and inference,” in _Proceedings of the 36th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97, 09–15 Jun 2019, pp. 614–623.
  * [30] C. Huang, P. Kairouz, X. Chen, L. Sankar, and R. Rajagopal, “Generative adversarial privacy,” _arXiv:1807.0530_ , Jun. 2019.
  * [31] H. Hsu, N. Martinez, M. Bertran, G. Sapiro, and F. P. Calmon, “A survey on statistical, information, and estimation—theoretic views on privacy,” _IEEE BITS the Information Theory Magazine_ , vol. 1, no. 1, pp. 45–56, 2021\.
  * [32] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in _2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1175–1191.
  * [33] J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova, “Secure single-server aggregation with (poly) logarithmic overhead,” in _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 1253–1269.
  * [34] Y. Zhao and H. Sun, “Information theoretic secure aggregation with user dropouts,” _IEEE Transactions on Information Theory_ , vol. 68, no. 11, pp. 7471–7484, 2022.
  * [35] J. So, C. J. Nolet, C.-S. Yang, S. Li, Q. Yu, R. E. Ali, B. Guler, and S. Avestimehr, “Lightsecagg: a lightweight and versatile design for secure aggregation in federated learning,” in _Proceedings of Machine Learning and Systems_ , D. Marculescu, Y. Chi, and C. Wu, Eds., vol. 4, 2022, pp. 694–720.
  * [36] K. Wan, H. Sun, M. Ji, and G. Caire, “Information theoretic secure aggregation with uncoded groupwise keys,” _arXiv:2204.11364_ , 2022.
  * [37] M. Chalk, O. Marre, and G. Tkacik, “Relevant sparse codes with variational information bottleneck,” _Advances in Neural Information Processing Systems_ , vol. 29, 2016.
  * [38] B. Dai, C. Zhu, B. Guo, and D. Wipf, “Compressing neural networks using the variational information bottleneck,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 1135–1144.
  * [39] I. Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerchner, “beta-VAE: Learning basic visual concepts with a constrained variational framework,” in _International Conference on Learning Representations_ , 2017.
  * [40] A. Jacot, F. Gabriel, and C. Hongler, “Neural Tangent Kernel: Convergence and Generalization in Neural Networks,” in _Advances in Neural Information Processing Systems_ , ser. NIPS’18, vol. 31. Curran Associates, Inc., 2018, pp. 8571–8580. [Online]. Available: https://proceedings.neurips.cc/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf
  * [41] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai, “Gradient Descent Finds Global Minima of Deep Neural Networks,” in _Proceedings of the 36th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 97. PMLR, 2019, pp. 1675–1685. [Online]. Available: http://proceedings.mlr.press/v97/du19c.html
  * [42] S. Mei and A. Montanari, “The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve,” _Communications on Pure and Applied Mathematics_ , 2021.
  * [43] R. Couillet and Z. Liao, _Random Matrix Methods for Machine Learning_. Cambridge University Press, 2022\.
  * [44] M. Belkin, D. Hsu, S. Ma, and S. Mandal, “Reconciling modern machine-learning practice and the classical bias–variance trade-off,” _Proceedings of the National Academy of Sciences_ , vol. 116, no. 32, pp. 15 849–15 854, 2019\.
  * [45] D. Guo, S. Shamai, and S. Verdu, “Mutual information and minimum mean-square error in gaussian channels,” _IEEE Transactions on Information Theory_ , vol. 51, no. 4, pp. 1261–1282, 2005.
  * [46] Z. Goldfeld, E. Van Den Berg, K. Greenewald, I. Melnyk, N. Nguyen, B. Kingsbury, and Y. Polyanskiy, “Estimating information flow in deep neural networks,” in _Proceedings of the 36th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 97. PMLR, 09–15 Jun 2019, pp. 2299–2308. [Online]. Available: https://proceedings.mlr.press/v97/goldfeld19a.html
  * [47] G. Chechik, A. Globerson, N. Tishby, and Y. Weiss, “Information bottleneck for gaussian variables,” _Advances in Neural Information Processing Systems_ , vol. 16, 2003.
  * [48] S. Hassanpour, D. Wuebben, and A. Dekorsy, “Overview and investigation of algorithms for the information bottleneck method,” in _SCC 2017; 11th International ITG Conference on Systems, Communications and Coding_ , 2017, pp. 1–6.
  * [49] H. Xu, T. Yang, G. Caire, and S. Shamai, “Information bottleneck for a rayleigh fading mimo channel with an oblivious relay,” _Information_ , vol. 12, no. 4, p. 155, 2021.
  * [50] A. Zaidi, I. Estella-Aguerri, and S. Shamai, “On the information bottleneck problems: Models, connections, applications and information theoretic views,” _Entropy_ , vol. 22, no. 2, p. 151, 2020.
  * [51] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [52] R. Blahut, “Computation of channel capacity and rate-distortion functions,” _IEEE Transactions on Information Theory_ , vol. 18, no. 4, pp. 460–473, 1972\.
  * [53] S. Arimoto, “An algorithm for computing the capacity of arbitrary discrete memoryless channels,” _IEEE Transactions on Information Theory_ , vol. 18, no. 1, pp. 14–20, 1972.
  * [54] K. Hornik, “Approximation capabilities of multilayer feedforward networks,” _Neural Networks_ , vol. 4, no. 2, pp. 251–257, 1991. [Online]. Available: https://www.sciencedirect.com/science/article/pii/089360809190009T
  * [55] T. M. Cover and J. A. Thomas, _Elements of Information Theory (2nd edition)_. Hoboken, NJ: Wiley, 2006.
  * [56] P. Chen, G. Chen, and S. Zhang, “Log hyperbolic cosine loss improves variational auto-encoder,” 2018.

##  Appendix A Achievability Proof of (6)

In order to prove that a solution of (6) is also a solution of (3), we only
need to prove

$\displaystyle
I(\mathbf{x};\mathbf{t})\leq\sum_{i\in[1:d_{0}]}I(x_{i};t_{i}),$ (14)

where $t_{i}~{}|~{}x_{i}\sim\mathcal{N}\left(\alpha_{i}\tanh(\beta
x_{i}),1\right)$. This is because by (6), we have
$\sum_{i\in[1:d_{0}]}I(x_{i};t_{i})=\sum_{i\in[1:d_{0}]}R_{i}=R$. If (14)
holds, we also have $I(\mathbf{x};\mathbf{t})\leq R$, coinciding with the
secrecy constraint in (3b). In the rest of this section, we will prove (14).

By our construction in (5), it can be seen that for each $i\in[1:d_{0}]$, we
have the following Markov chain

$\displaystyle(x_{1},t_{1},x_{2},t_{2},\ldots,x_{i-1},t_{i-1},x_{i+1},t_{i+1},\ldots,x_{d_{0}},t_{d_{0}})\longrightarrow
x_{i}\longrightarrow t_{i}.$ (15)

By the chain rule of mutual information, we have

$\displaystyle
I(\mathbf{x};\mathbf{t})=I(\mathbf{x};t_{1})+I(\mathbf{x};t_{2}|t_{1})+\cdots+I(\mathbf{x};t_{d_{0}}|t_{1},\ldots,t_{d_{0}-1}).$
(16)

We then focus on each term on the RHS of (16). For each $i\in[1:d_{0}]$, we
have

$\displaystyle I(\mathbf{x};t_{i}|t_{1},\ldots,t_{i-1})$
$\displaystyle=I(x_{i};t_{i}|t_{1},\ldots,t_{i-1})+I(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{d_{0}};t_{i}|x_{i},t_{1},\ldots,t_{i-1})$
(17a) $\displaystyle=I(x_{i};t_{i}|t_{1},\ldots,t_{i-1})$ (17b)
$\displaystyle\leq I(x_{i},t_{1},\ldots,t_{i-1};t_{i})$ (17c)
$\displaystyle=I(x_{i};t_{i})+I(t_{1},\ldots,t_{i-1};t_{i}|x_{i})$ (17d)
$\displaystyle=I(x_{i};t_{i}),$ (17e)

where (17b) and (17e) come from the Markov chain (15). By taking (17e) into
(16), we can directly prove (14).

##  Appendix B Proof of Theorem 1

Since $\hat{x}$ is a one-to-one mapping of $x$, we have

$\displaystyle I(x;t)=h(t)-h(t|x)=h(t)-h(t|\hat{x})=I(\hat{x};t).$ (18)

Since $t|\hat{x}$ is a Gaussian distribution with unit variance, the
conditional differential entropy is $h(t|\hat{x})=\frac{1}{2}\ln(2\pi e)$. In
addition, we can compute the probability of $\hat{x}$ as

$\displaystyle p(\hat{x})\\!$ $\displaystyle=\\!p(x)\frac{\partial
x}{\partial\hat{x}},$
$\displaystyle=\\!\frac{1}{\beta\sqrt{2\pi}}\exp{(\\!-\frac{(1/\beta\tanh^{-1}(\hat{x}))^{2}\\!+\\!\beta^{2}}{2})}\frac{1}{(1\\!-\\!\hat{x}^{2})^{1.5}}.$
(19)

By the information inequality [55], for any probability distribution $q(t)$,
we have

$\displaystyle h(t)=-\int p(t)\ln(p(t))dt\leq-\int p(t)\ln(q(t))dt.$ (20)

Then by (18) and (20), we can derive an upper bound of $I(\hat{x};t)$ based on
variational distribution $q(t)$,

$\displaystyle I(\hat{x};t)\leq-\int p(t)\ln(q(t))dt-\frac{1}{2}\ln(2\pi e).$
(21)

Moreover, the distribution of $t$ is much complicated due to the distribution
of $\hat{x}$ in (B). Therefore, instead of introducing variational
distribution of $t$, we come up with the variational distribution $\hat{x}$.
Since $\hat{x}$ is the MMSE Estimation of $y$ given observation $x$, for
simplicity, we design the variational distribution of $\hat{x}$ as Bernoulli
distribution, i.e., $q(\hat{x}=-1)=q(\hat{x}=1)=\frac{1}{2}$. Intuitively
speaking, the less the noise power of $x$ is, the closer the variational
distribution $q(\hat{x})$ gets to true distribution $p(\hat{x})$. Therefore,
the variational distribution of $t$ is given by

$\displaystyle q(t)$
$\displaystyle=\int_{-1}^{1}p(t|\hat{x})q(\hat{x})d\hat{x},$ (22a)
$\displaystyle=\frac{1}{\sqrt{2\pi}}\exp(-\frac{t^{2}+{\alpha}^{2}}{2})(\cosh{(\alpha
t)}).$ (22b)

Hence, by taking (22b) into (21), we have

$\displaystyle I(\hat{x};t)\\!$
$\displaystyle\leq\\!-\\!\int_{-\infty}^{\infty}\\!\left(\int_{-1}^{1}\\!p(t|\hat{x})p(\hat{x})d\hat{x}\right)\\!\ln
q(t)dt$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\!-\\!\frac{1}{2}\ln(2\pi
e),$ (23a)
$\displaystyle=\frac{{\alpha}^{2}-1}{2}+\underbrace{\int_{-1}^{1}p(\hat{x})\left(\int_{-\infty}^{\infty}p(t|\hat{x})\frac{t^{2}}{2}dt\right)d\hat{x}}_{(c)}-\int_{-\infty}^{\infty}\left(\int_{-1}^{1}p(t|\hat{x})p(\hat{x})d\hat{x}\right)\ln(\cosh(\alpha
t))dt.$ (23b)

Since $t|\hat{x}$ follows a Gaussian distribution
$\mathcal{N}(\alpha\hat{x},1)$, then $(c)$ in (23b) is given by

$\displaystyle\int_{-1}^{1}p(\hat{x})\left(\int_{-\infty}^{\infty}p(t|\hat{x})\frac{t^{2}}{2}dt\right)d\hat{x}$
$\displaystyle=\int_{-1}^{1}p(\hat{x})\frac{1+{\alpha}^{2}\hat{x}^{2}}{2}d\hat{x},$
$\displaystyle=\frac{1}{2}+\frac{{\alpha}^{2}}{2}f(\beta).$ (24)

By taking (B) into (23b), we have

$\displaystyle I(\hat{x};t)$
$\displaystyle\leq\frac{{\alpha}^{2}}{2}(1+f(\beta))-\int_{-\infty}^{\infty}\left(\int_{-1}^{1}p(t|\hat{x})p(\hat{x})d\hat{x}\right)\ln(\cosh(\alpha
t))dt.$ (25)

The RHS of (25) is hard to compute in closed-form due to the term
$\ln(\cosh{\alpha t})$. Hence, in the following we will propose three lower
bounds of $\ln(\cosh{\alpha t})$ to derive a loosen lower bound of
$I(\hat{x};t)$ with respect to (25).

First lower bound of $\ln(\cosh{\alpha t})$. By
$\ln(\cosh(x))\geq\sqrt{1+x^{2}}-1,~{}\forall~{}x\geq 0$, we have

$\displaystyle\\!-\\!\int_{-1}^{1}p(\hat{x})\\!\int_{\\!-\infty}^{\infty}\\!\frac{1}{\sqrt{2\pi}}\exp(-\frac{(t\\!-\\!\alpha\hat{x})^{2}}{2})\ln(\cosh(\alpha
t))dtd\hat{x}$
$\displaystyle\leq\\!-\\!\int_{-1}^{1}p(\hat{x})\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}\exp(-\frac{(t-\alpha\hat{x})^{2}}{2})\left[\sqrt{1+\alpha^{2}t^{2}}-1\right]dtd\hat{x},$
$\displaystyle\leq\\!-\\!\int_{-1}^{1}p(\hat{x})\left[\sqrt{1+\alpha^{4}\hat{x}^{2}}\right]d\hat{x}+1,$
(26a)
$\displaystyle=-\int_{-1}^{0}2p(\hat{x})\left[\sqrt{1+\alpha^{4}\hat{x}^{2}}\right]d\hat{x}+1,$
(26b)

where (26a) comes from the convexity of function
$f(t)=\sqrt{1+\alpha^{2}t^{2}}$, i.e.,
$\mathbb{E}[\sqrt{1+\alpha^{2}t^{2}}]\geq\sqrt{1+\alpha^{2}(\mathbb{E}[t])^{2}}$,
and (26b) follows since $p(\hat{x})$ and $\sqrt{1+\alpha^{4}{\hat{x}}^{2}}$
are both even functions regarding to $\hat{x}$.

Furthermore, by $\int_{-1}^{0}2p(\hat{x})d\hat{x}=1$, we have

$\displaystyle\int_{-1}^{0}2p(\hat{x})\hat{x}d\hat{x}=-g(\beta).$ (27)

Based on the Jensen’s inequality, an upper bound of the RHS of (26b) is given
by

$\displaystyle-\int_{-1}^{0}2p(\hat{x})\left[\sqrt{1+{\alpha}^{4}\hat{x}^{2}}\right]d\hat{x}+1$
$\displaystyle-\leq\sqrt{1+{\alpha}^{4}(\int_{-1}^{0}2p(\hat{x})\hat{x}d\hat{x})^{2}}+1,$
(28a) $\displaystyle=-\sqrt{1+{\alpha}^{4}(g(\beta))^{2}}+1.$ (28b)

By taking (28b) and (26b) into (25), we obtain the following upper bound of
$I(\hat{x};t)$,

$\displaystyle
I(\hat{x};t)\leq\frac{{\alpha}^{2}}{2}(1+f(\beta))-\sqrt{1+{\alpha}^{4}(g(\beta))^{2}}+1,$
(29)

the RHS of which will be then forced to equal $R$, i.e.,

$\displaystyle\frac{{\alpha}^{2}}{2}(1+f(\beta))-\sqrt{1+{\alpha}^{4}(g(\beta))^{2}}+1=R.$
(30)

The next step is to solve the equation (30). Assuming that $x=\alpha^{2}$ ,
$a=\frac{(1+f(\beta))^{2}-4(g(\beta))^{2}}{4}$, $b=(1-R)(1+f(\beta))$,
$c=R^{2}-2R$. and $\Delta=b^{2}-4ac$. First in order to check whether there
exists a real solution, we need to check whether $\Delta$ is always non-
negative when $R\geq 0$. Then we have

$\displaystyle\Delta$
$\displaystyle=(1+f(\beta))^{2}+4(g(\beta))^{2}(R^{2}-2R)$ (31a)
$\displaystyle\geq(1+f(\beta))^{2}+4(g(\beta))^{2}(-1)$ (31b)
$\displaystyle=(1+f(\beta)-2(g(\beta)))(1+f(\beta)+2(g(\beta))).$ (31c)

Note that the term $1+f(\beta)+2(g(\beta))$ in (31c) is always non-negative,
and based on (27), the term $1+f(\beta)-2(g(\beta))$ can be further developed
as

$\displaystyle 1+f(\beta)\\!-\\!2(g(\beta))\\!$
$\displaystyle=\\!1\\!+\\!2\int_{-1}^{0}p(\hat{x})\hat{x}^{2}d\hat{x}\\!+\\!4\int_{-1}^{0}p(\hat{x})\hat{x}d\hat{x},$
$\displaystyle=1+2\int_{-1}^{0}p(\hat{x})\left[(\hat{x}+1)^{2}-1\right]d\hat{x},$
$\displaystyle>1+2\int_{-1}^{0}p(\hat{x})(-1)d\hat{x},$ $\displaystyle=0.$
(32)

Hence, the term $1+f(\beta)-2(g(\beta))$ is always positive, and thus
$\Delta\geq 0$ holds when $R\geq 0$. Therefore, there always exists some real
solution of (30).

Secondly, we need to check whether there exists a positive solution in problem
(30). From (B), it can be seen that $a$ is always positive. When $0\leq R\leq
1$, $b$ is also positive. In this way, we need to compare $-b$ and
$\sqrt{\Delta}$, so we have

$\displaystyle b^{2}-\Delta$
$\displaystyle=(R^{2}-2R)\underbrace{\left[\right(1+f(\beta)))^{2}-4(g(\beta))^{2}]}_{(d)}.$
(33)

Therefore, since $(d)$ in (33) is always positive, when $0\leq R\leq 2$,
$R^{2}-2R$ is non-positive, it results in $\|b\|\leq\sqrt{\Delta}$ while
$R\geq 2$, it comes to $\|b\|\geq\sqrt{\Delta}$.

As a result, when $R\leq 1$, we have $\|b\|\leq\sqrt{\Delta}$ and
$-b+\sqrt{\Delta}\geq 0$; thus there exists one positive and real solution of
(30), which is

$\displaystyle\alpha_{\text{lb}_{1}}=\sqrt{\frac{-b+\sqrt{\Delta}}{2a}}.$ (34)

In addition, when $R>1$, we have $-b$ is positive and $\sqrt{\Delta}$ is also
positive; thus there always exists some positive solution of (30). However, it
may exist two positive solutions. Since the larger correlation factor $\alpha$
will result in the larger $I(y;t)$, we will choose the larger solution when
two positive solutions occur. Therefore, the solution is also

$\displaystyle\alpha_{\text{lb}_{1}}=\sqrt{\frac{-b+\sqrt{\Delta}}{2a}}.$ (35)

Second lower bound of $\ln(\cosh{\alpha t})$. By $\ln(\cosh(x))\geq x-\ln
2,~{}\forall~{}x\geq 0$ [56], separating the negative part and positive part
of $t$ and denoting $p$ as an auxiliary variable of $t-\alpha\hat{x}$, i.e.,
$p=t-\alpha\hat{x}$, we have

$\displaystyle-\int_{-\infty}^{\infty}\left(\int_{-1}^{1}p(t|\hat{x})p(\hat{x})d\hat{x}\right)\ln(\cosh(\alpha
t))dt$
$\displaystyle\leq-\int_{-1}^{1}p(\hat{x})\left(\int_{-\infty}^{0}p(t|\hat{x})\left[-\alpha
t-\ln
2\right]dt\right)d\hat{x}-\int_{-1}^{1}p(\hat{x})\left(\int_{0}^{\infty}p(t|\hat{x})\left[\alpha
t-\ln 2\right]dt\right)d\hat{x},$ (36a)
$\displaystyle=\\!\\!-\\!\int_{-1}^{1}\\!p(\hat{x})\\!\left(\int_{-\infty}^{\\!-\\!\alpha\hat{x}}\\!\frac{1}{\sqrt{2\pi}}\\!\exp\\!(\\!-\frac{p^{2}}{2})\left[\\!-\\!\alpha(p\\!+\\!\alpha\hat{x})\right]\\!dp\\!\right)\\!d\hat{x}\\!-\\!\\!\int_{-1}^{1}\\!p(\hat{x})\\!\left(\\!\int_{\\!-\\!\alpha\hat{x}}^{\infty}\\!\frac{1}{\sqrt{2\pi}}\\!\exp(-\frac{p^{2}}{2})\left[\alpha(p\\!+\\!\alpha\hat{x})\\!\right]dp\right)\\!d\hat{x}\\!+\\!\ln\\!2$
(36b)

Moreover, using that fact that
$\int\exp(-\frac{p^{2}}{2})pdp=-\exp(-\frac{p^{2}}{2})$, and separating the
negative part and positive part of $\hat{x}$, (36b) is further developed as

$\displaystyle\ln
2-\frac{2\alpha}{\sqrt{2\pi}}\int_{-1}^{1}p(\hat{x})\exp(-\frac{{\alpha}^{2}\hat{x}^{2}}{2})d\hat{x}-\int_{-1}^{1}p(\hat{x})\left[-\alpha^{2}\hat{x}\right]\int_{-\infty}^{-\alpha\hat{x}}\frac{1}{\sqrt{2\pi}}\exp(-\frac{p^{2}}{2})dpd\hat{x}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}-\int_{-1}^{1}p(\hat{x})\left[\alpha^{2}\hat{x}\right]\int_{-\alpha\hat{x}}^{\infty}\frac{1}{\sqrt{2\pi}}\exp(-\frac{p^{2}}{2})dpd\hat{x},$
(37a) $\displaystyle=\ln
2-\frac{2\alpha}{\sqrt{2\pi}}\int_{-1}^{1}p(\hat{x})\exp(-\frac{{\alpha}^{2}\hat{x}^{2}}{2})d\hat{x}+\frac{\alpha^{2}}{\sqrt{2\pi}}\int_{-1}^{0}\hat{x}p(\hat{x})\left[\int_{\alpha\hat{x}}^{-\alpha\hat{x}}\exp(-\frac{p^{2}}{2})dp\right]d\hat{x}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\frac{\alpha^{2}}{\sqrt{2\pi}}\int_{0}^{1}\hat{x}p(\hat{x})\left[-\int_{-\alpha\hat{x}}^{\alpha\hat{x}}\exp(-\frac{p^{2}}{2})dp\right]d\hat{x},$
(37b) $\displaystyle=\ln
2-\frac{2\alpha}{\sqrt{2\pi}}\int_{-1}^{1}p(\hat{x})\exp(-\frac{{\alpha}^{2}\hat{x}^{2}}{2})d\hat{x}+\underbrace{2\alpha^{2}\int_{-1}^{0}\hat{x}p(\hat{x})\left[\int_{\alpha\hat{x}}^{-\alpha\hat{x}}\frac{1}{\sqrt{2\pi}}\exp(-\frac{p^{2}}{2})dp\right]d\hat{x}}_{(e)}.$
(37c)

Suppose that a random variable $P\sim\mathcal{N}(0,1)$ follows unit Gaussian
distribution. For any non-negative real number $\alpha$ and negative real
number $\hat{x}<0$, we have the following inequality

$\displaystyle\text{Pr}(P\geq-\alpha\hat{x})$
$\displaystyle=\int_{-\alpha\hat{x}}^{\infty}\frac{1}{\sqrt{2\pi}}\exp(-\frac{p^{2}}{2})dp,$
(38a)
$\displaystyle\leq\int_{-\alpha\hat{x}}^{\infty}\frac{1}{\sqrt{2\pi}}\frac{p}{-\alpha\hat{x}}\exp(-\frac{p^{2}}{2})dp,$
(38b)
$\displaystyle=\frac{1}{\alpha\hat{x}\sqrt{2\pi}}(-\exp(-\frac{\alpha^{2}\hat{x}^{2}}{2})).$
(38c)

Based on the inequality (38), we can derive an upper bound on $(e)$ in (37c)
as

$\displaystyle(e)$
$\displaystyle=2{\alpha}^{2}\int_{-1}^{0}p(\hat{x})\hat{x}\left[1-2\text{Pr}(P\geq(-a\hat{x}))\right]d\hat{x},$
(39a) $\displaystyle\leq
2\alpha^{2}\int_{-1}^{0}p(\hat{x})\hat{x}\left[1-\frac{2}{\alpha\hat{x}\sqrt{2\pi}}(-\exp(-\frac{\alpha^{2}\hat{x}^{2}}{2}))\right]d\hat{x}$
(39b)

Hence, by taking (39b) into (37c) and combining (25), we can further relax the
constraint and obtain the following upper bound on $I(\hat{x};t)$

$\displaystyle I(\hat{x};t)$ $\displaystyle\leq\ln
2+2\alpha^{2}\int_{-1}^{0}p(\hat{x})\hat{x}d\hat{x}+\frac{\alpha^{2}}{2}(1+f(\beta)),$
(40a)
$\displaystyle=\alpha^{2}\left[\frac{1}{2}+\frac{f(\beta)}{2}-g(\beta)\right]+\ln
2,$ (40b)

the RHS of which will be then forced to equal $R$, i.e.,

$\displaystyle\alpha^{2}\underbrace{\left[\frac{1}{2}+\frac{f(\beta)}{2}-g(\beta)\right]}_{(f)}+\ln
2=R.$ (41)

According to (B), the term $(f)$ in (41) is always positive. Therefore, when
$R\geq\ln 2$, there exists a positive solution to (41), which is

$\displaystyle\alpha_{\text{lb}_{2}}=\sqrt{\frac{R-\ln
2}{\frac{1}{2}+\frac{f(\beta)}{2}-g(\beta)}}$ (42)

In the end, by replacing $\alpha$ in (8) with $\alpha_{\text{lb}_{1}}$, and
$\alpha_{\text{lb}_{2}}$, through (7) we can compute the lower bound on
$I(y;t)$, i.e., $I(\alpha_{\text{lb}_{1}})$, and $I(\alpha_{\text{lb}_{2}})$,
respectively.

##  Appendix C MNIST Data Pre-processing

Recall that our theoretical results assume that the input data
$\mathbf{x}\in{\mathbb{R}}^{d_{0}}$ are drawn from the following symmetric
binary Gaussian mixture model

$\mathcal{C}_{1}:\mathbf{x}\sim\mathcal{N}(-\bm{\beta},\mathbf{I}_{d_{0}}),\quad\mathcal{C}_{2}:\mathbf{x}\sim\mathcal{N}(+\bm{\beta},\mathbf{I}_{d_{0}}).$
(43)

For vectorized MNIST images of dimension $p=784$ composed of ten classes
(number $0$ to $9$), here we choose the images of number $4$ versus $9$ to
perform binary classification. For the sake of computational complexity (for
BA algorithm particularly), we apply a random projection that reduce the
$784$-dimensional raw data vector $\tilde{\mathbf{x}}$ to obtain a three-
dimensional feature $\mathbf{x}$, i.e.,
$\mathbf{x}=\mathbf{W}\tilde{\mathbf{x}}\in{\mathbb{R}}^{3}$, with the i.i.d.
entries of $\mathbf{W}\in{\mathbb{R}}^{3\times 783}$ following a standard
Gaussian distribution. Then, we collect three-dimensional feature matrices
$\mathbf{X}_{1}\in{\mathbb{R}}^{3\times n_{1}}$ and
$\mathbf{X}_{2}\in{\mathbb{R}}^{3\times n_{2}}$ of class $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$, and we perform further pre-processing to make them closer
to (43). First, the empirical means of each class are computed as
$\hat{\bm{\mu}}_{1}=\frac{1}{n_{1}}\mathbf{X}_{1}\mathbf{1}_{n_{1}}$ and
$\hat{\bm{\mu}}_{2}=\frac{1}{n_{2}}\mathbf{X}_{2}\mathbf{1}_{n_{2}}$. We then
compute the empirical covariances as
$\hat{\mathbf{C}}_{1}=\frac{1}{n_{1}}(\mathbf{X}_{1}-\hat{\mu}_{1}\mathbf{1}_{n_{1}}^{\sf
T})(\mathbf{X}_{1}-\hat{\mu}_{1}\mathbf{1}_{n_{1}}^{\sf T})^{\sf T}$ and
similarly for $\mathbf{X}_{2}$. Finally, whitened features matrices are
obtained via

$\tilde{\mathbf{X}}_{1}=\frac{1}{2}(\hat{\bm{\mu}}_{1}-\hat{\bm{\mu}}_{2})+\hat{\mathbf{C}}_{1}^{-\frac{1}{2}}(\mathbf{X}_{1}-\hat{\bm{\mu}}_{1}\mathbf{1}_{n_{1}}^{\sf
T}),$ (44)

for class $\mathcal{C}_{1}$ and similarly $\tilde{\mathbf{X}}_{2}$ for class
$\mathcal{C}_{1}$.