1

Data efficiency, dimensionality reduction, and the generalized symmetric
information bottleneck

K. Michael Martini1,3 and Ilya Nemenman1,2,3
1 Department of Physics, Emory University, Atlanta, GA 30322.
2 Department of Biology, Emory University, Atlanta, GA 30322.
3 Initiative in Theory and Modeling of Living Systems, Emory University,
Atlanta, GA 30322.

Keywords: Information Bottleneck, Symmetric Information Bottleneck,
Dimensionality Reduction, Error Bounds, Data Efficiency

Abstract

The Symmetric Information Bottleneck (SIB), an extension of the more familiar
Information Bottleneck, is a dimensionality reduction technique that
simultaneously compresses two random variables to preserve information between
their compressed versions. We introduce the Generalized Symmetric Information
Bottleneck (GSIB), which explores different functional forms of the cost of
such simultaneous reduction. We then explore the dataset size requirements of
such simultaneous compression. We do this by deriving bounds and root-mean-
squared estimates of statistical fluctuations of the involved loss functions.
We show that, in typical situations, the simultaneous GSIB compression
requires qualitatively less data to achieve the same errors compared to
compressing variables one at a time. We suggest that this is an example of a
more general principle that simultaneous compression is more data efficient
than independent compression of each of the input variables.

##  1 Introduction

Recent years have seen an explosion of large-dimensional experimental data
sets (de Vries et al.,, 2020; Siegle et al.,, 2021; Haghighi et al.,, 2022)
and the parallel growth in the number of methods for dimensionality reduction
(DR)—that is, for extracting low-dimensional structure from large-dimensional
data (Carreira-Perpinán,, 1997; Van Der Maaten et al.,, 2009; Nanga et al.,,
2021). Broadly speaking, we classify dimensionality reduction methods into two
classes: unsupervised and supervised. Unsupervised DR methods seek a low-
dimensional description, $T_{X}$, of a large-dimensional variable, $X$, that
preserves its variance, entropy, or another measure of diversity of the data.
Such methods include the familiar principal component analysis (PCA)
(Hotelling,, 1933), non-negative matrix factorization (Lee and Seung,, 1999),
multidimensional scaling (MDS) (Kruskal,, 1964), t-distributed stochastic
neighbor embedding (t-SNE) (Van der Maaten and Hinton,, 2008), Isomap
(Tenenbaum et al.,, 2000), Uniform Manifold Approximation and Projection
(UMAP) (McInnes et al.,, 2018), autoencoders (Hinton and Salakhutdinov,,
2006), and related techniques (Kingma and Welling,, 2014). In contrast,
supervised DR techniques aim to find a low-dimensional description, $T_{X}$,
of a large dimensional $X$, while preserving $T_{X}$’s ability to explain
another variable $Y$, which provides an effective relevance or supervision
signal. Common examples include variable selection in regression (Andersen and
Bro,, 2010; Kuo and Mallick,, 1998), cross-encoders, Bayesian Ising
Approximation (BIA) (Fisher and Mehta,, 2015), and the Information Bottleneck
(IB) (Tishby et al.,, 2000; Tishby and Slonim,, 2000). A particularly
interesting class of such supervised dimensionality reduction problems is when
both the reduced variable $X$ and the relevance variable $Y$ are large-
dimensional. In these situations, finding significant correlations within
combinatorially many groups of components of $X$ and $Y$ is hard, suggesting
parallel dimensionality reduction of both $X$ and $Y$ into $T_{X}$ and
$T_{Y}$, respectively.

We distinguish three classes of approaches to this problem. In the first,
which we call the Independent Unsupervised Dimensionality Reduction (IUDR),
one applies unsupervised DR methods to $X$ and $Y$ independently. One then
searches for statistical dependencies between $T_{X}$ and $Y$ or $T_{Y}$ and
$X$ or $T_{X}$ and $T_{Y}$, but the dimensionality reduction itself is
agnostic of this subsequent step. A familiar example of this is the Principal
Components Regression, where the projections on the principal components of
$X$ are regressed against $Y$. We also distinguish Independent Supervised
Dimensionality Reduction (ISDR), where $T_{X}$ is produced by compressing $X$
with $Y$ as the supervision signal, while $T_{Y}$ emerges from compressing $Y$
with $X$ as the supervision. The Information Bottleneck (IB) (Tishby et al.,,
2000), the Generalized and Deterministic Information Bottleneck (GIB) (Strouse
and Schwab,, 2017), and cross-encoders are examples of such approaches.
Finally, Simultaneous Supervised Dimensionality Reduction (SSDR) is a class of
methods where $T_{X}$ and $T_{Y}$ are produced simultaneously, typically being
supervision signals of each other.111SSDR methods are sometimes referred to as
dual DR (Sponberg et al.,, 2015). We believe that the terminology we propose
here is better suited for classifying the breadth of DR approaches. Examples
of SSDR include the Canonical Correlation Analysis (CCA) (Hotelling,, 1936;
Yang et al.,, 2021) and its modern nonlinear neural network based
generalizations (Andrew et al.,, 2013; Chapman and Wang,, 2021), Partial Least
Squares (PLS) (Wold,, 1966; Wold et al.,, 2001), and the Symmetric version of
the Information Bottleneck (SIB) (Slonim et al.,, 2006).222Different sources
refer to CCA or PLS as both supervised or unsupervised techniques or something
inbetween (Holbrook et al.,, 2017; Scott and Crone,, 2021; Zhuang et al.,,
2020). Within our classification scheme, these are supervised methods. In this
paper we introduce a Generalized version of the Symmetric Information
Bottleneck (GSIB) by interpolating between the compression cost measured by
entropy and information. This parallels for SSDR the introduction of the
Generalized Information Bottleneck (GIB) for ISDR, of which the Deterministic
Information Bottleneck and the Information Bottleneck are limits (Strouse and
Schwab,, 2017).

We then argue that SSDR approaches can require a lot less data than their ISDR
counter parts to achieve the same accuracy. We demonstrate this by comparing
the bias and statistical fluctuations in the objective functions of
independent GIB reductions of variables $X$ and $Y$ (ISDR approach) with the
corresponding bias and fluctuations for the GSIB (SSDR approach). We show that
the bias for the GSIB scales as the product of cardinalities of the compressed
variables, while the bias for the GIB scales as the (typically much larger)
product of cardinalities of the supervision signal and the compressed
variable. We do the comparison for both typical fluctuations and for the upper
bounds on the fluctuations. While our derivations are done for the IB
approaches only, the intuitive explanation of the differences between the
approaches suggests that SSDR methods are likely to require less data than
their ISDR analogues more generally.

##  2 Background: Information Bottleneck and the Symmetric Information
Bottleneck

###  2.1 Information Bottleneck and Its Generalizations

The goal of Information Bottleneck (IB) is to produce a compression, $T_{X}$
of a random variable $X$, such that the compression retains as much
information as possible about another random variable $Y$, which is called the
relevant (or, in our language, the supervising) variable. The information is
measured using Shannon’s mutual information (Shannon,, 1948), which quantifies
the difference between the joint probability distribution $p(x,y)$ and the
product of the marginal distributions $p(x)p(y)$:

$I(X,Y)=\sum_{X,Y}p(x,y)\frac{\log(p(x,y))}{p(x)p(y)}=H(X)-H(X|Y),$ (1)

where $H(X)$ is the entropy of the variable $X$ and $H(X|Y)$ is the
conditional entropy of $X$ given $Y$,
$H(X|Y)=\sum_{Y}p(y)H(X|Y=y)=\sum_{Y}p(y)\sum_{X}p(x|y)\log(p(x|y))$. Mutual
information is symmetric, always non-negative, and is only zero when the
random variables are independent (Cover,, 1999).

To achieve its goal, IB produces a probabilistic mapping from $X$ to $T_{X}$,
$p(t_{x}|x)$, which minimizes a specific cost function. The cost function
trades off preserving the information in the compression about the relevant
variable, $I(T_{X},Y)$, against losing the information about $X$ (reducing the
variable), $I(T_{X},X)$:

$L_{\rm IB}=I(T_{X},X)-\beta I(T_{X},Y).$ (2)

Here $\beta$ is the trade-off parameter, which controls how important the
compression $I(T_{X},X)$ is compared to preserving the relevant information
$I(T_{X},Y)$. As $\beta\to\infty$, the cost function is minimized by having no
compression, $X=T$. Recently a Generalized version of IB was proposed (GIB)
(Strouse and Schwab,, 2017), which changes the cost function to

$L_{\rm GIB}=H(T_{X})-\alpha_{x}H(T_{X}|X)-\beta I(T_{X},Y),$ (3)

which has a formal solution

$\displaystyle p(t_{x}|x)$
$\displaystyle=\frac{1}{Z(\beta,\alpha)}\exp\left[\frac{1}{\alpha_{x}}\left(\log
p(t_{x})-\beta D_{\rm KL}(p(y|x)||p(y|t_{x}))\right)\right],$ (4)
$\displaystyle p(y|t_{x})$
$\displaystyle=\frac{1}{p(t_{x})}\sum_{X}p(t_{x}|x)p(x,y),$ (5)

where $D_{\rm KL}$ is the usual Kullback–Leibler divergence (Kullback and
Leibler,, 1951).

The original IB is recovered from GIB when $\alpha_{x}=1$. In contrast, when
$\alpha_{x}\to 0$, $I(T_{X},X)$ is replaced with $H(T_{X})$ in the cost
function. This corresponds to replacing the cost of having a noisy channel
encoding $X$ into $T_{X}$ with the cost of directly storing $T_{X}$. In this
case, the formal solution results in a deterministic mapping between $X$ and
$T_{X}$, and the resulting problem is known as the Deterministic Information
Bottleneck (DIB) (Strouse and Schwab,, 2017).

If both $X$ and $Y$ are large-dimensional and require dimensionality
reduction, one can apply IB to produce the mapping $X\to T_{X}$ with $Y$ as
the relevant variable, and then solve a separate IB problem to map $Y\to
T_{Y}$ with $X$ as the supervision. This approach would fall into the ISDR
class in our nomenclature.

###  2.2 Symmetric Information Bottleneck and its Generalization

The Symmetric Information Bottleneck (SIB), introduced in Slonim et al.,
(2006), is an SSDR approach, where $X$ and $Y$ are compressed simultaneously,
such that the compressed versions $T_{X}$, and $T_{Y}$ contain the maximal
amount of information about each other. This corresponds to optimizing the
loss function:

$L_{\rm SIB}=I(T_{X};X)+I(T_{Y};Y)-\beta I(T_{X};T_{Y}),$ (6)

where optimization is over all possible probabilistic compressions
$p(t_{x}|x)$ and $p(t_{y}|y)$. As before, $\beta$ determines the strength of
the trade-off between the compression and preserving the relevant information.

For generality, here we propose a Generalized SIB (GSIB), which incorporates
flexible compression terms, similar to how GIB was optained from IB. The new
cost function is

$\displaystyle L_{\rm GSIB}$
$\displaystyle=I_{\alpha_{X}}(T_{X};X)+I_{\alpha_{Y}}(T_{Y};Y)-\beta
I(T_{X};T_{Y})$ (7)
$\displaystyle=H(T_{X})-\alpha_{X}H(T_{X}|X)+H(T_{Y})-\alpha_{Y}H(T_{Y}|Y)-\beta
I(T_{X},T_{Y}).$ (8)

Here we defined shorthands
$I_{\alpha_{X}}(T_{X},X)=H(T_{X})-\alpha_{X}H(T_{X}|X)$, and similarly for
$I_{\alpha_{Y}}$, and the cost function must be minimized with respect to
$p(t_{x}|x)$ and $p(t_{y}|y)$. The parameters $\alpha_{X}$ and $\alpha_{Y}$
are what dictates how probabilistic the mapping between the uncompressed
variables and their compressed versions is. In the limit
$\alpha_{x},\alpha_{Y}\to 0$, the mapping can be verified to be deterministic
(see below), resulting in the Determistic SIB (DSIB). When
$\alpha_{X},\alpha_{Y}\to 1$, GSIB becomes the usual SIB.

Optimization of the cost function has a formal solution:

$\displaystyle p(t_{x}|x)$
$\displaystyle=\frac{\exp\left[\frac{1}{\alpha_{X}}\left(\ln p(t_{x})-\beta
D_{\rm
KL}(p(t_{y}|x)||p(t_{y}|t_{x})\right)\right]}{Z_{x}(x,\alpha_{X},\beta)},$ (9)
$\displaystyle p(t_{y}|y)$
$\displaystyle=\frac{\exp\left[\frac{1}{\alpha_{Y}}\left(\ln p(t_{y})-\beta
D_{\rm
KL}(p(t_{x}|y)||p(t_{x}|t_{y})\right)\right]}{Z_{y}(y,\alpha_{Y},\beta)},$
(10) $\displaystyle p(t_{y}|x)$
$\displaystyle=\frac{\sum_{Y}p(t_{y}|y)p(x,y)}{p(x)},\;\;\;\;\;p(t_{y}|t_{x})=\frac{\sum_{X,Y}p(t_{y}|y)p(t_{x}|x)p(x,y)}{\sum_{X}p(t_{x}|x)p(x)},$
(11) $\displaystyle p(t_{x}|y)$
$\displaystyle=\frac{\sum_{X}p(t_{x}|x)p(x,y)}{p(y)},\;\;\;\;\;p(t_{x}|t_{y})=\frac{\sum_{X,Y}p(t_{y}|y)p(t_{x}|x)p(x,y)}{\sum_{Y}p(t_{y}|y)p(y)}.$
(12)

Similar to IB, this formal solution can be iterated starting from an initial
guess for both $p(t_{x}|x)$ and $p(t_{y}|y)$.

Interestingly, parenthetically we note that, unlike for IB, there are now
exponentially many, $\sim 2^{|T_{X}|+|T_{Y}|}$, trivial fixed points for this
iteration scheme (here $|\cdot|$ denotes cardinality of the variable, so that
the rest of our discussion focuses on random variables defined on discrete,
finite sets of possible values). For example, a uniform distribution for both
random mappings, $p(t_{x}|x)=1/|T_{X}|$ and $p(t_{y}|y)=1/|T_{Y}|$ is a fixed
point of the iteration with the cost of zero, even though a uniform mapping,
independent of the conditioning variable, is clearly not a useful compression.
Furthermore, all distributions, where $p(t_{x}|x)$ is zero for several values
of $t_{x}$ and uniform otherwise, are also trivial fixed points. There are
exponentially many distributions of this type. When $\alpha_{x}=\alpha_{y}=1$,
these distributions are part of a larger class of trivial fixed points, which
includes all mappings independent of the data, i. e., $p(t_{x}|x)=A(t_{x})$
and $p(t_{y}|y)=B(t_{y})$. One can easily verify that the first derivative of
$L_{\rm GSIB}$ vanishes for these solutions. The second derivative, which
controls if these solutions are minima or maxima, is:

$\frac{\partial^{2}L_{\rm GSIB}}{\partial p(t_{x}|x)\partial
p(t_{x}^{\prime}|x^{\prime})}=\frac{-p(x)}{A(t_{x})}(p(x)-\alpha_{X})\delta(x,x^{\prime})\delta(t,t_{x}^{\prime})-\frac{p(x)p(x^{\prime})}{A(t_{x})}\delta(t_{x},t_{x}^{\prime})(1-\delta(x,x^{\prime})),$
(13)

(with similar expression for the compression of $Y$). These trivial fixed
points are maxima when $\alpha_{x}<p(x)$, and $\alpha_{y}<p(y)$. When
$\alpha_{x}>p(x)$ and $\alpha_{y}>p(y)$, such as in the case of SIB, when
$\alpha_{X}=\alpha_{Y}=1$, the trivial fixed points are saddles. Thus
solutions found by the iterative algorithm must be viewed with suspicion, and
one should always verify if the algorithm got trapped by one of the trivial
solutions.

In the limit of $\alpha_{X},\alpha_{Y}\to 0$, the exponent in the formal
solution blows up. As a result, one obtains a deterministic mapping from
uncompressed variables to their compressions:

$\displaystyle p(t_{x}|x)$ $\displaystyle=\delta(t_{x},\tau_{x}(x))$ (14)
$\displaystyle\tau_{x}(x)$ $\displaystyle=\textrm{argmax}_{t_{x}}\left[\ln
p(t_{x})-\beta D_{\rm KL}(p(t_{y}|x)||p(t_{y}|t_{x}))\right],$ (15)
$\displaystyle p(t_{y}|y)$ $\displaystyle=\delta(t_{y},\tau_{y}(y))$ (16)
$\displaystyle\tau_{y}(y)$ $\displaystyle=\textrm{argmax}_{t_{y}}\left[\ln
p(t_{y})-\beta D_{\rm KL}(p(t_{x}|y)||p(t_{x}|t_{y}))\right].$ (17)

This is the Deterministic SIB (DSIB).

##  3 Results

To show that GSIB is more data efficient than two GIBs applied independently
to $X$ and to $Y$, we notice that, in practical applications, all of the
information and entropy terms in the loss functions must be estimated from
data. Estimation of information-theoretic quantities is a hard task,
potentially as hard as estimating the underlying distributions themselves,
largely due to the estimation bias (Antos and Kontoyiannis,, 2001; Paninski,,
2003). Crucially, for a DR algorithm to produce meaningful results, the
empirically estimated loss function must accurately represent the true loss
function, which is unknown to us. Thus the question of which algorithm is more
data efficient is equivalent to a different question: for which of the
considered IB algorithms does the estimate of the respective loss function
converge faster to its true value as the sample size grows?

A lot of ink has been expended on the problem of mutual information estimation
(Roulston,, 1999; Kraskov et al.,, 2004; Goebel et al.,, 2005; Belghazi et
al.,, 2018). Here we do not try to produce better estimation techniques.
Instead we focus on discrete random variables with finite cardinalities, and
we use the simplest estimator, known as plug-in, naive, or maximum likelihood
estimator, for estimation of all of the terms in the loss functions
(Roulston,, 1999; Paninski,, 2003). For this estimator, which we denote with
$\hat{\cdot}$, the probability distribution $p(x)$ is estimated by its maximum
likelihood (ML) value, namely the frequency of an outcome in the sample,
$\hat{p}(x)=n(x)/N$, where $n(x)$ is the number of times $x$ occurred, and $N$
is the total number of samples. Then $\hat{H}$, $\hat{I}$, and $\hat{L}$ are
all given by plugging in $\hat{p}$ instead of $p$ in the expression for these
quantities. Shamir et al., (2010) showed that, while the ML estimator of
mutual information $\hat{I}(X,Y)$ is guaranteed to converge to the true value
only when $N\gg|X||Y|$, ML estimator of the loss function, $\hat{L}_{\rm IB}$,
converges at much smaller $N$, making IB more practical than one would naively
think.

Here we continue this line of analysis and examine the convergence properties
of $\hat{L}_{\rm GSIB}$ and $\hat{L}_{\rm GIB}$ when both $|X|,|Y|\gg 1$ in
two different ways. First, we extend the derivations of Shamir et al., (2010)
and bound the error of estimating each information-theoretic term in each of
the loss functions from data. This allows us to build bounds on how close $L$
and $\hat{L}$ are, and we can compare these bounds for GSIB and GIBs. Second,
inspired by Still and Bialek, (2004), we calculate the standard deviation and
bias of $L-\hat{L}$ for different versions of the IB. By both measures, for
$|X|,|Y|\gg 1$, $\hat{L}_{\rm GSIB}$ will have a smaller bias then
$\hat{L}_{\rm GIB}$. This is our main result, allowing us to claim that the
symmetric version of IB is more data efficient.

###  3.1 Bounds on The Loss Functions

The loss functions $L_{\rm GSIB}$ and $L_{\rm GIB}$ consist of multiple mutual
information and entropy terms. We calculate bounds on the fluctuations between
each of these terms and their estimators, and then combine them into a single
estimate of the fluctuations of each loss function. We do this below in detail
for $I(T_{X};X)$ and its estimator $\hat{I}(T_{X};X)$. Analysis of the other
terms is similar. Furthermore, for our analysis, we assume that the mappings
$p(t_{x}|x)$ and $p(t_{y}|y)$ are fixed. The expressions we develop will hold
for all mappings, not just the mappings that minimize their respective loss
functions.

To estimate $|I(T_{X};X)-\hat{I}(T_{X};X)|$, we compare both terms to the
expected value of the empirical information $E(I(T_{X};X))$:

$|\hat{I}(T_{X};X)-{I}(T_{X};X)|=|\hat{I}(T_{X};X)-E(\hat{I}(T_{X};X))+E(\hat{I}(T_{X};X))-{I}(T_{X};X)|\\\
\leq|\hat{I}(T_{X};X)-E(\hat{I}(T_{X};X))|+|I(T_{X};X)-E(\hat{I}(T_{X};X))|.$
(18)

This is the usual bias-variance decomposition for bounds on the magnitude of
fluctuations, with the first term in Eq. (18) representing the bias, and the
second the variance. We now bound the bias and the the variance terms
separately.

First we focus on the variance (second) term in Eq. (18). For this, we follow
Shamir et al., (2010) and rely on the the McDiarmid’s inequality. This
concentration inequality bounds the probability of the difference between a
function of an empirical sample and its expected value. The bound is
constructed from bounds on the change in the function due to changes in
individual data points:

$\displaystyle
P\left[\left|f(x_{1},x_{2},\dots,x_{N})-E\left(f(x_{1},x_{2},\dots,x_{N})\right)\right|\geq\epsilon\right]$
$\displaystyle\leq 2\exp\left[-\frac{2\epsilon^{2}}{\sum
c_{i}}\right]\equiv\delta_{1},$ (19)
$\displaystyle\mbox{where}\quad\left|f(x_{1},\dots,x_{i},\dots,x_{N})-f(x_{1},\dots,x_{i}^{\prime},\dots,x_{N})\right|$
$\displaystyle\leq c_{i}.$ (20)

Thus, to use the inequality, we consider the maximum change in $\hat{I}$ if a
single datum is changed. That is, suppose the data point $(x,y)$ is replaced
by another data point $(x^{\prime},y^{\prime})$. Then the maximum likelihood
estimator at the point $(x,y)$, $\hat{p}(x,y)$, decreases by $1/N$. In
contrast, $\hat{p}(x^{\prime},y^{\prime})$ increases by $1/N$, and the
estimate does not change at all other $x$, $y$ values. Similarly, the
marginals $\hat{p}(x)$, $\hat{p}(x^{\prime})$, $\hat{p}(y)$, and
$\hat{p}(y^{\prime})$ change by at most $1/N$, while marginals at all other
values remain the same. For a fixed compression mapping, we calculate
$\hat{p}(t_{x})=\sum_{x}p(t_{x}|x)\hat{p}(x)$. We see that, with a single
datum moving, $\hat{p}(t_{x})$ can change by at most
$|p((t_{x}|x^{\prime})-p(t_{x}|x))|/N\leq 1/N$ for each $t_{x}\in T_{X}$.
Similarly $\hat{p}(t_{y})$ can change by at most $1/N$ for each $t_{y}\in
T_{Y}$.

We now express the relevant mutual information in terms of entropy,
$\hat{I}_{\alpha_{X}}(T_{X};X)=\hat{H}(T_{X})-\alpha_{X}\hat{H}(T_{X}|X)$,
where the entropy $\hat{H}(T_{X})$ depends on the probability density
$\hat{p}(t_{x})$:

$\hat{H}(T_{X})=-\sum_{t_{x}}\hat{p}(t_{x})\log\hat{p}(t_{x}).$ (21)

The change in entropy from moving a single datum can be bounded using the
following inequality, again borrowed from Shamir et al., (2010):

$|(a+\delta)\log(a+\delta)-a\log a|\leq\log(N)/N$ (22)

for any positive integer $N$ and for any $a\in[0,1-1/N]$ and $\delta\leq 1/N$.
We apply this identity for each term in the sum in Eq. (21) and find that the
change in $\hat{H}(T_{X})$ is bounded by $|T_{X}|\log N/N$.

We bound the change in $\hat{H}(T_{X}|X)=\sum_{x}\hat{p}(x)H(T_{X}|X=x)$.
$H(T_{X}|X=x)$ only depends on $p(t_{x}|x)$, which we consider fixed.
$\hat{p}(x)$ changes by at most $1/N$ for two values of $x$. Thus the largest
change is
$|H(T_{X}|x^{\prime})-H(T_{X}|x)|/N\leq|\max(H(T_{X}|x^{\prime}),H(T_{X}|x))|/N\leq\log|T_{X}|/N$.
The last inequality comes from $H(T_{X}|X=x)\leq\log|T_{X}|$, with the bound
achieved for the uniform distribution.

Finally, combining the results for both entropy terms, we see that
$\hat{I}_{\alpha_{X}}(T_{X};X)$ can change by at most $(|T_{X}|\log
N+\alpha_{X}\log|T_{X}|)/N$. Now we apply the McDiarmid inequality, Eqs. (19,
20) to finally obtain that, with probability of at least $1-\delta_{1}$:

$|\hat{I}_{\alpha_{X}}(T_{X};X)-E(\hat{I}_{\alpha_{X}}(T_{X};X))|\leq(|T_{X}|\log
N+\alpha_{X}\log|T_{X}|)\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}.$ (23)

This generalizes the result of Shamir et al., (2010) to $\alpha_{X}\neq 1$.
Similarly, we get that, with probability of at least $1-\delta_{1}$,

$|\hat{I}_{\alpha_{Y}}(T_{Y};Y)-E(\hat{I}_{\alpha_{Y}}(T_{Y};Y))|\leq(|T_{Y}|\log
N+\alpha_{Y}\log|T_{Y}|)\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}.$ (24)

This leaves us with the final bound on the difference between the ML
estimators of various informations and their expectations, namely for
$\hat{I}(T_{X};T_{Y})$; this quantity is not analysed in Shamir et al.,
(2010), but we proceed very similarly. First, we calculate how much this term
changes from a single datum being moved by using the identity
$\hat{I}(T_{X};T_{X})=\hat{H}(T_{X})+\hat{H}(T_{Y})-\hat{H}(T_{X},T_{Y})$.
Luckily we already calculated that $\hat{H}(T_{X})$ changes by, at most,
$|T_{X}|\log N/N$, and $\hat{H}(T_{Y})$ changes by, at most, $|T_{Y}|\log
N/N$. We are left to calculate how much $\hat{H}(T_{X},T_{Y})$ can change. We
write
$\hat{H}(T_{X},T_{Y})=-\sum_{t_{x},t_{y}}\hat{p}(t_{x},t_{y})\log\hat{p}(t_{x},t_{y})$,
where $\hat{p}(t_{x},t_{y})=\sum_{x,y}p(t_{x}|x)p(t_{y}|y)\hat{p}(x,y)$.
Therefore, $\hat{p}(t_{x},t_{y})$ can change by, at most, $1/N$ for all
$(t_{x},t_{y})\in(T_{X},T_{Y})$. Thus, $\hat{H}(T_{X},T_{Y})$ can change by at
most $|T_{X}||T_{Y}|\log N/N$. We again use the McDiarmid’s inequality and we
determine that, with probability of at least $1-\delta_{1}$, the difference
between the ML estimate $\hat{I}(T_{X};T_{Y})$ and its expected value is
bounded by

$|\hat{I}(T_{X};T_{Y})-E(\hat{I}(T_{X};T_{Y}))|\leq((|T_{X}|+|T_{Y}|+|T_{X}||T_{Y}|)\log
N)\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}.$ (25)

Now we need to calculate bounds on the bias (first) terms in Eq. (18) and
similar expressions for the other information quantities. For this, we use
results from Paninski, (2003), namely:

$\displaystyle|H(T_{X})-E(\hat{H}(T_{X}))|$
$\displaystyle\leq\log\left(1+\frac{|T_{X}|-1}{N}\right)\leq\frac{|T_{X}|-1}{N},$
(26) $\displaystyle|H(T_{Y})-E(\hat{H}(T_{Y}))|$
$\displaystyle\leq\log\left(1+\frac{|T_{Y}|-1}{N}\right)\leq\frac{|T_{Y}|-1}{N},$
(27) $\displaystyle|H(T_{X},T_{X})-E(\hat{H}(T_{X},T_{X}))|$
$\displaystyle\leq\log\left(1+\frac{|T_{X}||T_{Y}|-1}{N}\right)\leq\frac{|T_{X}||T_{Y}|-1}{N}.$
(28)

Since we consider mapping $p(t_{x}|x)$ as fixed and known for this analysis,
there is no bias $H(T_{X}|X)-E(\hat{H}(T_{X}|X))$. This means that the bias
$|I_{\alpha_{X}}(T_{X};X)-\hat{I}_{\alpha_{X}}(T_{X};X)|$ only comes from the
$|H(T_{X})-\hat{H}(T_{X})|$ term and does not have an $|X|$ or $\alpha_{x}$
dependence.

Putting the bounds on deviations of the estimates from their expectations and
of expectations from the true values together, we get bounds on fluctuations
of various information quantities that contribute to the GSIB loss function

$\displaystyle|I_{\alpha_{X}}(T_{X};X)-\hat{I}_{\alpha_{X}}(T_{X};X)|\leq$
$\displaystyle(|T_{X}|\log
N+\alpha_{X}\log|T_{X}|)\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}+\frac{|T_{X}|-1}{N},$
(29)
$\displaystyle|I_{\alpha_{Y}}(T_{Y};Y)-\hat{I}_{\alpha_{Y}}(T_{Y};Y)|\leq$
$\displaystyle(|T_{Y}|\log
N+\alpha_{Y}\log|T_{Y}|)\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}+\frac{|T_{Y}|-1}{N},$
(30) $\displaystyle|I(T_{X};T_{Y})-\hat{I}(T_{X};T_{Y})|\leq$
$\displaystyle(|T_{X}|+|T_{Y}|+|T_{X}||T_{Y}|)\log
N\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}$
$\displaystyle+\frac{|T_{X}|-1}{N}+\frac{|T_{Y}|-1}{N}+\frac{|T_{X}||T_{Y}|-1}{N}$
$\displaystyle=$ $\displaystyle((|T_{X}|+1)(|T_{Y}|+1)-1)\log
N\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}$
$\displaystyle+\frac{(|T_{X}|+1)(|T_{Y}|+1)-4}{N}.$ (31)

For comparison, the term
$|I_{\alpha_{x}}(T_{X};X)-\hat{I}_{\alpha_{x}}(T_{X};X)|$ in the error of the
GIB loss function has the same bounds as the corresponding term in GSIB, Eq.
(29). Further the term $|I(T_{X};Y)-\hat{I}(T_{X};Y)|$ in the error of the GIB
loss function is the same as for the traditional IB. Shamir et al., (2010)
calculated it to be:

$\displaystyle|I(T_{X};Y)-\hat{I}(T_{X};Y)|$
$\displaystyle\leq(3|T_{X}|+2)\log
N\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}+\frac{(|T_{X}|+1)(|Y|+1)-4}{N}.$
(32)

All of these bounds have a similar structure. The term proportional to
$1/\sqrt{N}$ comes from the variance of the estimators. Its contribution is
controlled by $\delta_{1}$, so that if a high certainty is required
($\delta_{1}\to 0$), then these terms are large. The terms proportional to
$1/N$ are the bias terms.

The most crucial observation is that, even though the data comes from the
joint probability distribution $p(x,y)$, which has the cardinality of
$|X||Y|$, the terms proportional to this joint cardinality do not appear in
the bounds, similar to Shamir et al., (2010). In other words, one does not
need to have the joint distribution well-sampled to apply any of the IB
variants.

The second observation from the bounds is that the deterministic versions,
$\alpha=\alpha_{X}=\alpha_{Y}=0$, of both the SIB and the IB have slightly
tighter bounds than their generalized counterparts, including the original IB
versions with $\alpha=\alpha_{X}=\alpha_{Y}=1$. The tightening does not affect
the bias component of the bounds, but provides a small correction to the
variance, eliminating the terms similar to
$\alpha\log|T_{X}|\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}$, which are
subdominant in the size of the reduced representations compared to the terms
like $|T_{X}|\log N\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}$.

We now compare the data efficiency of GSIB with that of two GIBs applied to
reduce $X$ and $Y$ independently. We do so by bounding the error of the
estimates of the loss for the GSIB vs. for two GIBs run in parallel.

The GSIB loss function error is:

$|L_{\rm GSIB}-\hat{L}_{\rm GSIB}|\leq\left(\left(|T_{X}|+|T_{Y}|\right)\log
N+\alpha_{X}\log|T_{X}|+\alpha_{Y}\log|T_{Y}|\right)\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}\\\
+\beta\left(\left(|T_{X}|+1\right)\left(|T_{Y}|+1\right)-1\right)\log
N\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}\\\
+\frac{|T_{X}|-1}{N}+\frac{|T_{Y}|-1}{N}+\beta\frac{(|T_{X}|+1)(|T_{Y}|+1)-4}{N}.$
(33)

The combined loss of two GIBs reducing $X$ and $Y$ independently is:

$|L_{\rm GIB}-\hat{L}_{\rm GIB}|\leq\left(\left(|T_{X}|+|T_{Y}|\right)\log
N+\alpha_{X}\log|T_{X}|+\alpha_{Y}\log|T_{Y}|\right)\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}\\\
+\beta\left(3|T_{X}|+3|T_{Y}|+4\right)\log
N\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}\\\
+\frac{|T_{X}|-1}{N}+\frac{|T_{Y}|-1}{N}+\beta\frac{(|T_{X}|+1)(|Y|+1)+(|T_{Y}|+1)(|X|+1)-8}{N}.$
(34)

We see that the dominant contribution to the variance part of $L_{\rm GSIB}$
bound is $\beta|T_{X}||T_{Y}|\log
N\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}$. For two GIBs run in parallel,
Eq. (34) says that the dominant contributions to the variance would be
$3\beta(|T_{X}|+|T_{Y}|)\log N\frac{\sqrt{\log(2/\delta_{1})}}{\sqrt{2N}}$.
That is, the two GIBs have smaller variances than GSIB for all but the
smallest cardinalities of the compressed variables. However, notice that the
cardinality of the compressed variables is usually not large, almost by
definition, so that this loosening of the bound may be too small to notice for
realistic $N\gg 1$. The behavior of the bias contributions to the bounds is
different. The leading term for GSIB is $|T_{X}||T_{Y}|/N$, while for two GIBs
it is $(|T_{X}||Y|+|X||T_{Y}|)/N$. Thus, when $|X|,|Y|\sim N$, the GSIB can be
significantly more efficient that GIBs. When $|X|,|Y|\gg N$, the bias bounds
for GIBs become meaningless, but GSIB bounds do not depend on the cardinality
of the data variables. This is the reason for our assertion that GSIB has
better data efficiency than two GIBs run in parallel for realistic
cardinalities of variables and sample sizes.

###  3.2 Mean error and Mean squared error

The error bounds for the mutual information estimators must hold for worst
case underlying distributions. Thus there are many cases when the error is
significantly smaller than the calculated bounds. To explore if typical errors
are different from the worst case bounds, here we calculate the mean squared
error of $L_{\rm GSIB}-\hat{L}_{\rm GSIB}$, and similarly for the GIB. As
always, the mean squared error is the sum of the squared bias and the variance
of the estimator

$E(L_{\rm GSIB}-\hat{L}_{\rm GSIB})^{2}=(L_{\rm GSIB}-E(\hat{L}_{\rm
GSIB}))^{2}+E((\hat{L}_{\rm GSIB}-E(\hat{L}_{\rm GSIB}))^{2}),$ (35)

and similarly for the GIB. This expression is the equivalent of the bias-
variance decomposition for the bounds, Eq. (18). However, instead of bounding
terms, we now calculate them. For this, we decompose every mutual information
term in the loss functions into the corresponding entropy components.

We use the notation $\delta h\equiv\hat{h}-h$ for any variable that is being
estimated via the ML estimator. For the ML estimator of the probability
distribution $p(x,y)$, multinomial counting statistics textbook results give

$\displaystyle E(\delta p(x,y))$ $\displaystyle=0,$ (36) $\displaystyle
E(\delta p(x,y)\delta p(x^{\prime},y^{\prime}))$
$\displaystyle=\frac{p(x,y)\delta_{x,x^{\prime}}\delta_{y,y^{\prime}}}{N}-\frac{p(x,y)p(x^{\prime},y^{\prime})}{N}.$
(37)

Expectations for fluctuations of marginal distributions can be obtained by
marginalizing Eqs. (36, 37).

In what follows, we will focus on $N\gg 1$, so that fluctuations $\delta
p(x,y)$ have a small relative variance. Then, to obtain expressions for the
variance of entropies, we follow Still and Bialek, (2004) and expand $\hat{H}$
around the true value $H$ for small $\delta p$. For $H(X)$, we get
(expressions for other entropy terms are similar):

$\displaystyle\hat{H}(X)$ $\displaystyle=-\sum_{X}(p(x)+\delta
p(x))\log(p(x)+\delta p(x))$ $\displaystyle=-\sum_{X}\left[p(x)\log p(x)+(\log
p(x)+1)\delta p(x)+\sum_{n=2}^{\infty}\frac{(-1)^{n}(\delta
p(x))^{n}}{n(n-1)p(x)^{n-1}}\right]$ $\displaystyle=H(X)-\sum_{X}\left[(\log
p(x)+1)\delta p(x)+\sum_{n=2}^{\infty}\frac{(-1)^{n}(\delta
p(x))^{n}}{n(n-1)p(x)^{n-1}}\right].$ (38)

From this, it follows that $\delta H(X)=-\sum_{X}\left[(\log p(x)+1)\delta
p(x)+\frac{(\delta p(x))^{2}}{2p(x)}\right.$ $\left.+O((\delta
p(x))^{3}))\right]$. Noticing that terms first order in $\delta p$ vanish
under averaging, we immediately calculate $|E(\delta H(X))|=\frac{|X|-1}{2N}$
and $|E(\delta H(Y))|=\frac{|Y|-1}{2N}$. Similarly, because $p(t_{x}|x)$ is
fixed, we get $|E(\delta H(X,T_{X}))|=\frac{|X|-1}{2N}$, $|E(\delta
H(Y,T_{Y}))|=\frac{|Y|-1}{2N}$. Further, $|E(\delta
H(T_{X}))|=\frac{\sum_{T_{X},X}p(t_{x}|x)p(x|t_{x})-1}{2N}\leq\frac{|T_{X}|-1}{2N}$
and $|E(\delta H(T_{Y}))|=\leq\frac{|T_{Y}|-1}{2N}$ where the inequalities
comes from $p(t_{x}|x),p(t_{y}|y)\leq 1$. Combining these and similar results,
we get biases of estimators of mutual information terms, which enter the GSIB
loss functions:

$\displaystyle|E(\delta I_{\alpha_{X}}(X,T_{X}))|$
$\displaystyle\leq\frac{|T_{X}|-1}{2N},$ (39) $\displaystyle|E(\delta
I_{\alpha_{Y}}(Y,T_{Y}))|$ $\displaystyle\leq\frac{|T_{Y}|-1}{2N},$ (40)
$\displaystyle|E(\delta I(T_{X},T_{Y}))|$
$\displaystyle\leq\frac{(|T_{X}|+1)(|T_{Y}|+1)-4}{2N}.$ (41)

For the terms in the GIB loss function, we similarly get

$\displaystyle|E(\delta I(Y,T_{X}))|$
$\displaystyle\leq\frac{(|Y|+1)(|T_{X}|+1)-4}{2N},$ (42)
$\displaystyle|E(\delta I(Y,T_{Y}))|$
$\displaystyle\leq\frac{(|X|+1)(|T_{Y}|+1)-4}{2N}.$ (43)

Note that these biases, to the two leading orders in $\delta p$, are half of
the bound on the biases obtained in the previous Section, Eqs. (29-32). Thus
the same scaling analyses apply. Crucially, we again observe that the bias of
the symmetric variant of GIB only depends on the cardinalities of the
compressed variables and not the uncompressed ones. Hence it is much smaller
than for two GIBs applied in parallel, where the bias depends on $|X||T_{Y}|$
and $|Y||T_{X}|$.

Similarly we now calculate the mean squared error (see Appendix for details):

$E(\delta I(X,T_{X})^{2})=\\\
=\frac{1}{N}\left[\sum_{X,T_{X},T_{X}^{\prime}}p(t_{x}|x)p(t_{x}^{\prime}|x)p(x)\log\frac{p(x,t_{x})}{p(x)p(t_{x})}\log\frac{p(x,t_{x}^{\prime})}{p(x)p(t_{x}^{\prime})}-I(X,T_{X})^{2}\right].$
(44)

This expression can be simplified in two important limits. First, we consider
the trivial minimum of the loss function, discussed earlier. There the mapping
is uniform, $p(t_{x}|x)=1/|T_{X}|$, so that also $p(t_{x})=1/|T_{X}|$. We get:

$E(I(X,T_{X})-\hat{I}(X,T_{X}))^{2}=\\\
=\sum_{X,T_{X},T_{X}^{\prime}}\frac{p(x)}{N|T_{X}|^{2}}\log\frac{p(x)/|T_{X}|}{p(x)/|T_{X}|}\log\frac{p(x)/|T_{X}|}{p(x)/|T_{X}|}-\frac{0^{2}}{N}=0.$
(45)

That is, fluctuations vanish in this case. This is expected since there is no
information between $T_{X}$ and $X$, and measuring more data points does not
result in a more accurate estimate of the mutual information.

The second interesting case is a “winner-take-all” mapping,
$p(t_{x}|x)=\delta(t_{x},\tau(x))$, which would correspond to a deterministic
clustering of multiple values of $x$ into one $t_{x}$. This results in

$\displaystyle E(I(X,T_{X})-\hat{I}(X,T_{X}))^{2}$
$\displaystyle=\frac{1}{N}\left[\sum_{X}p(x)\log\frac{1}{p(\tau(x))}\log\frac{1}{p(\tau(x))}-I(X,T_{X})^{2}\right]$
$\displaystyle\leq\frac{1}{N}\left[\log(\min(|T_{X}|,|X|))^{2}-I(X,T_{X})^{2}\right].$
(46)

Thus, here the average squared error is bound by
$\frac{\log|T_{X}|^{2}-I(X,T_{X})^{2}}{N}\leq\frac{\log|T_{X}|^{2}}{N}$, which
means that the RMS error for $I(T_{X},X)$ is
$\leq\frac{\log|T_{X}|}{\sqrt{N}}$. Similarly, the RMS errors for $I(T_{Y},Y)$
and $I(T_{X},T_{Y})$ are $\leq\frac{\log|T_{Y}|}{\sqrt{N}}$ and
$\leq\frac{\log\min(|T_{X}|,|T_{Y}|)}{\sqrt{N}}$, respectively. For the
traditional IB, the RMS error for $I(T,X)$ is $\leq\frac{\log|T|}{\sqrt{N}}$,
and the RMS error for $I(T,Y)$ is $\leq\frac{\log|T|}{\sqrt{N}}$. Thus, the
average fluctuations are small and are of the same order of magnitude for both
the symmetric bottleneck and the traditional bottleneck. This means that the
dominant term is the average bias. As we saw earlier, the latter can be much
worse for the traditional IB than for the symmetric IB.

##  4 Conclusion

Here we defined the generalized symmetric version of the information
bottleneck (GSIB). We calculated the error bounds for each term within the
loss function of GSIB and of the loss functions of the traditional generalized
information bottleneck (GIB). We showed that the bias in estimating the loss
function, and hence the error in finding the solution to the optimization
problem from a finite dataset, is smaller for the GSIB compared to applying
traditional GIB to each of the input variables, in parallel. We also
calculated the average error and RMS error for each of these terms, resulting
in essentially the same conclusions. All of these results suggest that when
the cardinality of the measured variables $X$ and $Y$ are both large, and both
variables require compression, then simultaneous compression is more data
efficient than independently compressing each of the input variables.

While making extrapolations from a simple discrete variable case to more
complex scenarios is difficult, we hope that these results are only the first
of many to demonstrate a more general point that simultaneous dimensionality
reduction is typically more data efficient than independent dimensionality
reduction. In fact, in a forthcoming publication, we expect to show this for a
class of linear dimensionality reduction techniques for continuous variables.
If true, such findings would suggest a general paradigm for efficient
dimensionality reduction in complex multivariate datasets. Since physical
theories are often formulated in terms of collective, coarse-grained
representations (e.g., magnetization or temperature, which are expectation
values of microscopic spins or energies of molecules), existence of data
efficient algorithms for finding such reduced representations bodes well for
using data-driven approaches for building physical theories of complex
systems.

### Acknowledgments

The authors are grateful to Eslam Abdelaleem and Ahmed Roman for useful
discussions and Sean Ridout for providing feedback on the manuscript. This
work was supported, in part, by the Simons Investigator award and NSF Grant
No. 2010524.

##  5 Appendix

###  5.1 Appendix: Derivation of the Generalized Symmetric Bottleneck

In what follows, we will derive the formal solution for the generalized
symmetric bottleneck for $p(t_{x}|x)$. The formal solution is found by
minimizing the cost function, Eq. (8) with respect to $p(t_{x}|x)$, subject to
the normalization constraint. For this, we calculate the following useful
derivatives:

$\displaystyle\frac{\partial p(t_{x})}{\partial p(t_{x}^{\prime}|x^{\prime})}$
$\displaystyle=\frac{\partial}{\partial
p(t_{x}^{\prime}|x^{\prime})}\sum_{X}p(t_{x}|x)p(x)=\delta(t_{x},t_{x}^{\prime})p(x^{\prime}),$
(47) $\displaystyle\frac{\partial p(t_{y})}{\partial
p(t_{x}^{\prime}|x^{\prime})}$ $\displaystyle=0,$ (48)
$\displaystyle\frac{\partial p(t_{x},t_{y})}{\partial
p(t_{x}^{\prime}|x^{\prime})}$ $\displaystyle=\frac{\partial}{\partial
p(t_{x}^{\prime}|x^{\prime})}\sum_{X}p(t_{x}|x)p(x,t_{y})=\delta(t_{x},t_{x}^{\prime})p(x^{\prime},t_{y}).$
(49)

To enforce the normalization of $p(t_{x}|x)$, we add a Lagrange multiplier
$\lambda$ times the normalization constraint to the cost function. With the
helpful identities above, we now find the first derivative:

$\displaystyle\frac{\partial(L_{\rm
GSIB}+\lambda(\sum_{X,T_{X}}p(t_{x}|x)p(x)-1))}{\partial
p(t_{x}^{\prime}|x^{\prime})}=$
$\displaystyle\quad\quad\quad=\frac{\partial}{\partial
p(t_{x}^{\prime}|x^{\prime})}\left[-\sum_{T_{X}}p(t_{x})\ln
p(t_{x})+\alpha_{x}\sum_{X,T_{X}}p(x)p(t_{x}|x)\ln p(t_{x}|x)\right.$
$\displaystyle\quad\quad\quad\quad\quad\left.-\sum_{T_{Y}}p(t_{y})\ln
p(t_{y})+\alpha_{y}\sum_{Y,T_{Y}}p(y)p(t_{y}|y)\ln p(t_{y}|y)\right.$
$\displaystyle\quad\quad\quad\quad\quad\left.-\beta\sum_{T_{X},T_{Y}}p(t_{x},t_{y})\ln\frac{p(t_{x},t_{y})}{p(t_{x})p(t_{y})}+\lambda\left(\sum_{X,T_{X}}p(t_{x}|x)p(x)-1\right)\right]$
$\displaystyle\quad\quad\quad=-p(x^{\prime})\ln
p(t_{x}^{\prime})-p(x^{\prime})+\alpha_{x}[p(x^{\prime})\ln
p(t_{x}^{\prime}|x^{\prime})+p(x^{\prime})]$
$\displaystyle\quad\quad\quad\quad\quad-\beta\sum_{T_{Y}}p(x^{\prime},t_{y})\ln\frac{p(t_{x}^{\prime},t_{y})}{p(t_{x}^{\prime})p(t_{y})}+\lambda
p(x^{\prime})$ $\displaystyle\quad\quad\quad=-p(x^{\prime})\left[\ln
p(t_{x}^{\prime})+1-\lambda-\alpha_{x}\left(\ln
p(t_{x}^{\prime}|x^{\prime})+1\right)\right.$
$\displaystyle\left.\quad\quad\quad\quad\quad+\beta\sum_{T_{Y}}p(t_{y}|x^{\prime})\ln\frac{p(t_{y}|t_{x}^{\prime})}{p(t_{y})}\frac{p(t_{y}|x^{\prime})}{p(t_{y}|x^{\prime})}\right]$
$\displaystyle\quad\quad\quad=-p(x^{\prime})\left[\ln
p(t_{x}^{\prime}))+1-\lambda-\alpha_{x}\left(\ln
p(t_{x}^{\prime}|x^{\prime})+1\right)\right.$
$\displaystyle\quad\quad\quad\quad\left.+\beta\sum_{T_{Y}}p(t_{y}|x^{\prime})\ln\frac{p(t_{y}|t_{x}^{\prime})p(t_{y}|x^{\prime})}{p(t_{y})p(t_{y}|x^{\prime})}\right]$
$\displaystyle\quad\quad\quad=-p(x^{\prime})\left[\ln
p(t_{x}^{\prime})+1-\lambda-\alpha_{x}\left(\ln
p(t_{x}^{\prime}|x^{\prime})+1\right)\right.$
$\displaystyle\quad\quad\quad\quad\quad\left.+\beta\sum_{T_{Y}}p(t_{y}|x^{\prime})\left(\ln\frac{p(t_{y}|x^{\prime})}{p(t_{y})}-\ln\frac{p(t_{y}|x^{\prime})}{p(t_{y}|t_{x}^{\prime})}\right)\right]$
$\displaystyle\quad\quad\quad=-p(x^{\prime})\left[\ln
p(t_{x}^{\prime})+1-\lambda-\alpha_{x}\left(\ln
p(t_{x}^{\prime}|x^{\prime})+1\right)\right.$
$\displaystyle\left.\quad\quad\quad\quad\quad+\beta D_{\rm
KL}(p(t_{y}|x^{\prime})||p(t_{y}))-\beta D_{\rm
KL}(p(t_{y}|x^{\prime})||p(t_{y}|t_{x}^{\prime}))\right].$ (50)

We now find the minimum of the cost function subject to the constraint that
$p(t_{x}|x)$ is normalized by setting this derivative to zero and solving for
$p(t_{x}^{\prime}|x^{\prime})$. Doing this, we find a formal solution:

$p(t_{x}^{\prime}|x^{\prime})=\frac{\exp\left[\frac{1}{\alpha_{x}}\left(\ln
p(t_{x}^{\prime})-\beta D_{\rm
KL}(p(t_{y}|x^{\prime})||p(t_{y}|t_{x}^{\prime})\right)\right]}{Z_{x}(x^{\prime},\alpha_{x},\beta)},$
(51)

where
$Z_{x}(x^{\prime},\alpha_{x},\beta)=\exp\left[-1+\lambda+\alpha_{x}-\beta
D_{\rm KL}(p(t_{y}|x^{\prime})||p(t_{y}))\right]$, and $\lambda$ is chosen
such that $p(t_{x}^{\prime}|x^{\prime})$ is normalized. Notice that the
normalization constant $Z_{x}$ is independent of $t_{y}$ and $t_{x}^{\prime}$.
It only depends on $x^{\prime}$, $\alpha_{x}$, and $\beta$. The same procedure
can be followed to find the solution of the generalized symmetric information
bottleneck for $p(t_{y}|y)$.

$p(t_{y}^{\prime}|y^{\prime})=\frac{\exp\left[\frac{1}{\alpha_{y}}\left(\ln
p(t_{y}^{\prime})-\beta D_{\rm
KL}(p(t_{x}|y^{\prime})||p(t_{x}|t_{y}^{\prime})\right)\right]}{Z_{y}(y^{\prime},\alpha_{y},\beta)},$
(52)

###  5.2 Appendix: Mean Error

Here we make explicit the calculations started in Section 3.2. Using Eq. (38)
from the main text we, find the expected bias to be:

$\displaystyle|E(\delta H(X))|$ $\displaystyle=\sum_{X}\frac{E(\delta
p(x)^{2})}{2p(x)}=\sum_{X}\frac{E(\sum_{Y}\delta
p(x,y))^{2}}{2\sum_{Y}p(x,y)}$
$\displaystyle=\sum_{X}\frac{\sum_{Y,Y^{\prime}}E(\delta p(x,y)\delta
p(x,y^{\prime}))}{2\sum_{Y}p(x,y)}$
$\displaystyle=\sum_{X}\frac{\sum_{Y}p(x,y)-\sum_{Y,Y^{\prime}}p(x,y)p(x,y^{\prime})}{2N\sum_{Y}p(x,y)}$
$\displaystyle=\sum_{X}\frac{p(x)-p^{2}(x)}{2Np(x)}=\frac{|X|-1}{2N}.$ (53)

Similarly, $|E(\delta H(Y))|=\frac{|Y|-1}{2N}$, and $|E(\delta
H(X,T_{X}))|=\frac{|X|-1}{2N}$.

Now we write:

$\displaystyle|E(\delta H(T_{X}))|$ $\displaystyle=\sum_{T_{X}}\frac{E(\delta
p(t_{x})^{2})}{2p(t_{x})}=\sum_{T_{X}}\frac{E(\sum_{X,Y}\delta
p(t_{x}|x)p(x,y))^{2}}{2\sum_{X,Y}p(x,y)}$
$\displaystyle=\sum_{T_{X}}\frac{\sum_{X,X^{\prime},Y,Y^{\prime}}E(p(t_{x}|x)p(t_{x}|x^{\prime})\delta
p(x,y)\delta p(x^{\prime},y^{\prime}))}{2\sum_{X,Y}p(t_{x}|x)p(x,y)}$
$\displaystyle=\sum_{T_{X}}\frac{\sum_{X,Y}p(t_{x}|x)^{2}p(x,y)-\sum_{X,X^{\prime},Y,Y^{\prime}}p(t_{x}|x)p(t_{x}|x^{\prime})p(x,y)p(x^{\prime},y^{\prime})}{2N\sum_{X,Y}p(t_{x}|x)p(x,y)}$
$\displaystyle=\sum_{T_{X}}\frac{\sum_{X}p(t_{x}|x)^{2}p(x)-p(t_{x})^{2}}{2Np(t_{x})}=\sum_{T_{X}}\frac{\sum_{X}p(t_{x}|x)p(x|t_{x})-p(t_{x})}{2N}$
$\displaystyle=\frac{\sum_{T_{X},X}[p(t_{x}|x)p(x|t_{x})]-1}{2N}\leq\frac{|T_{X}|-1}{2N},$
(54)

where the inequality comes from $p(t|x)\leq 1$, so that $p(t|x)^{2}p(x)\leq
p(t|x)p(x)$.

We can combine these results to find the overall bias for $\hat{I}(X,T_{X})$:

$\displaystyle|E(\delta I(X,T_{X}))|$ $\displaystyle=|E(\delta H(X))+E(\delta
H(T_{X}))-E(\delta H(X,T_{X}))|$
$\displaystyle=\frac{|X|-1}{2N}+\frac{\sum_{T_{X},X}p(t_{x}|x)p(x|t_{x})-1}{2N}-\frac{|X|-1}{2N}$
$\displaystyle=\frac{\sum_{T_{X},X}p(t_{x}|x)p(x|t_{x})-1}{2N}\leq\frac{|T_{X}|-1}{2N}.$
(55)

Similarly,

$\displaystyle|E(\delta I(Y,T_{Y}))|$ $\displaystyle=|E(\delta H(Y))+E(\delta
H(T_{Y}))-E(\delta H(Y,T_{Y}))|$
$\displaystyle=\frac{|Y|-1}{2N}+\frac{\sum_{T_{Y},Y}p(t_{y}|y)p(y|t_{y})-1}{2N}-\frac{|Y|-1}{2N}$
$\displaystyle=\frac{\sum_{T_{Y},Y}p(t_{y}|y)p(y|t_{y})-1}{2N}\leq\frac{|T_{Y}|-1}{2N}.$
(56)

Finally, we calculate the bias for $\hat{I}(T_{X},T_{Y})$:

$\displaystyle|E(\delta I(T_{X},T_{Y}))|=$ $\displaystyle|E(\delta
H(T_{X}))+E(\delta H(T_{Y}))-E(\delta H(T_{X},T_{Y}))|$ $\displaystyle=$
$\displaystyle\frac{\sum_{T_{X},X}p(t_{x}|x)p(x|t_{x})-1}{2N}+\frac{\sum_{T_{Y},Y}p(t_{y}|y)p(y|t_{y})-1}{2N}$
(57)
$\displaystyle-\frac{\sum_{T_{X},T_{Y},X,Y}p(t_{x},t_{y}|x,y)p(x,y|t_{x},t_{y})-1}{2N},$
(58)

and

$\displaystyle|E(\delta I(T_{X},T_{Y}))|$ $\displaystyle\leq|E(\delta
H(T_{X}))|+|E(\delta H(T_{Y}))|+|E(\delta H(T_{X},T_{Y}))|$
$\displaystyle\leq\frac{|T_{X}|-1}{2N}+\frac{|T_{Y}|-1}{2N}+\frac{|T_{X}||T_{Y}|-1}{2N}.$
(59)

We can perform similar calculations for the original bottleneck to obtain:

$\displaystyle|E(\delta I(Y,T))|$ $\displaystyle\leq|E(\delta H(Y))|+|E(\delta
H(T))|+|E(\delta H(Y,T))|$
$\displaystyle=\frac{|Y|-1}{2N}+\frac{\sum_{T,X}p(t|x)p(x|t)-1}{2N}+\sum_{Y,T}\frac{\sum_{X}p(t|x)p(x|t,y)}{2N}-\frac{1}{2N}$
$\displaystyle\leq\frac{|Y|-1}{2N}+\frac{|T|-1}{2N}+\frac{|Y||T|-1}{2N}.$ (60)

###  5.3 Appendix: Mean Squared Error

Using a method inspired by Still and Bialek, (2004), we start by calculating
the expected squared error for the mutual information between two arbitrary
variables $A$ and $B$, where the estimated probabilities are different from
the true ones by a small error $\delta$, $\hat{p}(a,b)=p(a,b)+\delta p(a,b)$,
$\hat{p}(a)=p(a)+\delta p(a)$ and $\hat{p}(b)=p(b)+\delta p(b)$. First, let’s
calculate the mutual information to the first order in $\delta p$:

$\displaystyle\hat{I}(A,B)$ $\displaystyle=\sum_{A,B}(p(a,b)+\delta
p(a,b))\log\frac{p(a,b)+\delta p(a,b)}{(p(a)+\delta p(a))(p(b)+\delta p(b))}$
$\displaystyle=\sum_{A,B}(p(a,b)+\delta
p(a,b))\log\left[\frac{p(a,b)}{p(a)p(b)}\frac{1+\delta
p(a,b)/p(a,b)}{(1+\delta p(a)/p(a))(1+\delta p(b)/p(b))}\right]$
$\displaystyle=\sum_{A,B}(p(a,b)+\delta
p(a,b))\left[\log\frac{p(a,b)}{p(a)p(b)}+\log\left(1+\frac{\delta
p(a,b)}{p(a,b)}\right)\right.$
$\displaystyle\left.\quad\quad\quad-\log\left(1+\frac{\delta
p(a)}{p(a)}\right)-\log\left(1+\frac{\delta p(b)}{p(b)}\right)\right]$
$\displaystyle\approx\sum_{A,B}(p(a,b)+\delta
p(a,b))\left[\log\frac{p(a,b)}{p(a)p(b)}+\frac{\delta
p(a,b)}{p(a,b)}-\frac{\delta p(a)}{p(a)}-\frac{\delta
p(b)}{p(b)}+\dots\right]$ $\displaystyle\approx\sum_{A,B}\left[\delta
p(a,b)\log\frac{p(a,b)}{p(a)p(b)}+p(a,b)\left(\frac{\delta
p(a,b)}{p(a,b)}-\frac{\delta p(a)}{p(a)}-\frac{\delta
p(b)}{p(b)}+\dots\right)\right]$ $\displaystyle=\sum_{A,B}\left[\delta
p(a,b)\log\frac{p(a,b)}{p(a)p(b)}+\left(\delta p(a,b)-p(b|a)\delta
p(a)-p(a|b)\delta p(b))+\dots\right)\right]$
$\displaystyle\quad\quad\quad+I(A,B)$ $\displaystyle=\sum_{A,B}\delta
p(a,b)\log\frac{p(a,b)}{p(a)p(b)}+\sum_{A,B}\delta p(a,b)-\sum_{A}\delta
p(a)-\sum_{B}\delta p(b)+\dots$ $\displaystyle\quad\quad\quad+I(A,B)$
$\displaystyle=I(A,B)+\sum_{A,B}\delta
p(a,b)\left(\log\frac{p(a,b)}{p(a)p(b)}-1\right)+\dots$ (61)

Where in the last two lines, we used $\sum_{B}p(b|a)=1$, $\sum_{A}p(a|b)=1$,
and $\delta p(a)=\sum_{B}\delta p(a,b)$, $\delta p(b)=\sum_{A}\delta p(a,b)$,
respectively.

Thus, we see that $\delta I(A,B)=\sum_{A,B}\delta
p(a,b)(\log\frac{p(a,b)}{p(a)p(b)}-1)$ to first order in $\delta p(a,b)$. We
can now calculate the average squared error:

$\displaystyle E[\delta I(A,B)^{2}]$ $\displaystyle=E\left[\sum_{A,B}\delta
p(a,b)\left(\log\frac{p(a,b)}{p(a)p(b)}-1\right)\right.$
$\displaystyle\left.\quad\quad\quad\quad\times\sum_{A^{\prime},B^{\prime}}\delta
p(a^{\prime},b^{\prime})\left(\log\frac{p(a^{\prime},b^{\prime})}{p(a^{\prime})p(b^{\prime})}-1\right)\right]$
$\displaystyle=\sum_{A,B,A^{\prime},B^{\prime}}E\left[\delta p(a,b)\delta
p(a^{\prime},b^{\prime})\right]$
$\displaystyle\quad\quad\quad\quad\times\left(\log\frac{p(a,b)}{p(a)p(b)}-1\right)\left(\log\frac{p(a^{\prime},b^{\prime})}{p(a^{\prime})p(b^{\prime})}-1\right).$
(62)

We can use this generic expression to find the squared error for the estimator
of information between the variables $X$ and $T_{X}$, where $\delta
p(x,t_{x})=p(t_{x}|x)\delta p(x)$, and $E(\delta p(x)\delta
p(x^{\prime}))=1/N[\delta(x,x^{\prime})p(x)-p(x)p(x^{\prime})]$. We calculate
$E[\delta I(X,T_{X})^{2}]$ as follows:

$\displaystyle E[\delta I(X,T_{X})^{2}]$
$\displaystyle=\sum_{X,T,X^{\prime},T^{\prime}}E\left[\delta p(x,t_{x})\delta
p(x^{\prime},t_{x}^{\prime})\right]\left(\log\frac{p(x,t_{x})}{p(x)p(t_{x})}-1\right)\left(\log\frac{p(x^{\prime},t_{x}^{\prime})}{p(x^{\prime})p(t_{x}^{\prime})}-1\right)$
$\displaystyle=\sum_{X,T_{X},X^{\prime},T_{X}^{\prime}}p(t_{x}|x)p(t_{x}^{\prime}|x^{\prime})E\left[\delta
p(x)\delta
p(x^{\prime})\right]\left(\log\frac{p(x,t_{x})}{p(x)p(t_{x})}-1\right)$
$\displaystyle\quad\quad\quad\quad\times\left(\log\frac{p(x^{\prime},t_{x}^{\prime})}{p(x^{\prime})p(t_{x}^{\prime})}-1\right)$
$\displaystyle=\sum_{X,T_{X},X^{\prime},T_{X}^{\prime}}p(t_{x}|x)p(t_{x}^{\prime}|x^{\prime})\frac{p(x)\delta(x,x^{\prime})-p(x)p(x^{\prime})}{N}$
$\displaystyle\quad\quad\quad\quad\times\left(\log\frac{p(x,t_{x})}{p(x)p(t_{x})}-1\right)\left(\log\frac{p(x^{\prime},t_{x}^{\prime})}{p(x^{\prime})p(t_{x}^{\prime})}-1\right)$
$\displaystyle=\frac{1}{N}\left[\sum_{X,T_{X},T_{X}^{\prime}}p(t_{x}|x)p(t_{x}^{\prime}|x)p(x)\right.$
$\displaystyle\left.\quad\quad\quad\quad\times\left(\log\frac{p(x,t_{x})}{p(x)p(t_{x})}\log\frac{p(x,t_{x}^{\prime})}{p(x)p(t_{x}^{\prime})}-\log\frac{p(x,t_{x})}{p(x)p(t_{x})}-\log\frac{p(x,t_{x}^{\prime})}{p(x)p(t_{x}^{\prime})}+1\right)\right]$
$\displaystyle-\frac{1}{N}\left[\sum_{X,T_{X}}p(t_{x}|x)p(x)\left(\log\frac{p(x,t_{x})}{p(x)p(t_{x})}-1\right)\right.$
$\displaystyle\left.\quad\quad\quad\quad\times\sum_{X^{\prime},T_{X}^{\prime}}p(t_{x}^{\prime}|x^{\prime})p(x^{\prime})\left(\log\frac{p(x^{\prime},t_{x}^{\prime})}{p(x^{\prime})p(t_{x})^{\prime}}-1\right)\right]$
$\displaystyle=\frac{1}{N}\left[\sum_{X,T_{X},T_{X}^{\prime}}p(t_{x}|x)p(t_{x}^{\prime}|x)p(x)\log\frac{p(x,t_{x})}{p(x)p(t_{x})}\log\frac{p(x,t_{x}^{\prime})}{p(x)p(t_{x}^{\prime})}\right.$
$\displaystyle\left.\quad\quad\quad\quad-2I(X,T_{X})+1-(I(X,T_{X})-1)^{2}\right]$
$\displaystyle=\frac{1}{N}\left[\sum_{X,T_{X},T_{X}^{\prime}}p(t_{x}|x)p(t_{x}^{\prime}|x)p(x)\log\frac{p(x,t_{x})}{p(x)p(t_{x})}\log\frac{p(x,t_{x}^{\prime})}{p(x)p(t_{x}^{\prime})}-I(X,T_{X})^{2}\right].$
(63)

Now let’s look at two limits when we can simplify the above expression. In the
first limit, we assume that the mapping is uniform, $p(t_{x}|x)=1/|T_{X}|$,
which means that $p(t_{x})=1/|T_{X}|$ as well. Then

$E[(I(X,T_{X})-\hat{I}(X,T_{X}))^{2}]=\sum_{X,T_{X},T_{X}^{\prime}}\frac{p(x)}{|T_{X}|^{2}}\log\frac{p(x)/|T_{X}|}{p(x)/|T_{X}|}\log\frac{p(x)/|T_{X}|}{p(x)/|T_{X}|}\frac{1}{N}-\frac{0^{2}}{N}=0.$
(64)

In the other limit, we assume a “winner takes all” mapping, where
$p(t_{x}|x)=\delta(t_{x},\tau(x))$. We can reduce the expression to:

$\displaystyle E[\delta I(X,T_{X})^{2}]=$
$\displaystyle\quad\quad=\frac{1}{N}\left[\sum_{X,T_{X},T_{X}^{\prime}}\delta(t_{x},\tau(x))\delta(t_{x}^{\prime},\tau(x))p(x)\log\frac{\delta(t_{x},\tau(x))}{p(t_{x})}\log\frac{\delta(t_{x}^{\prime},\tau(x))}{p(t_{x}^{\prime})}\right.$
$\displaystyle\quad\quad\quad\quad\quad\left.-I(X,T_{X})^{2}\right]$
$\displaystyle\quad\quad=\frac{1}{N}\left[\sum_{X}p(x)\log\frac{1}{p(\tau(x))}\log\frac{1}{p(\tau(x))}-I(X,T_{X})^{2}\right]$
$\displaystyle\quad\quad\leq\frac{1}{N}\left[\log(\min(|T_{X}|,|X|))^{2}-I(X,T_{X})^{2}\right]\leq\frac{1}{N}\left[\log(\min(|T_{X}|,|X|))^{2}\right].$
(65)

The result for $E[\delta I(Y,T_{Y})^{2}]$ is similar to that for $E[\delta
I(X,T_{X})^{2}]$, Eq. (63:

$E[\delta I(Y,T_{Y})^{2}]=\\\
=\frac{1}{N}\left[\sum_{Y,T_{Y},T_{Y}^{\prime}}p(t_{y}|y)p(t_{y}^{\prime}|y)p(y)\log\frac{p(y,t_{y})}{p(y)p(t_{y})}\log\frac{p(y,t_{y}^{\prime})}{p(y)p(t_{y}^{\prime})}-I(Y,T_{Y})^{2}\right].$
(66)

Finally we can calculate the covariance of fluctuations in the compressed
variables, $T_{X}$ and $T_{Y}$. Here $\delta
p(t_{x},t_{y})=\sum_{X,Y}p(t_{x}|x)p(t_{y}|y)\delta p(x,y)$, and

$\displaystyle E[\delta p(t_{x},t_{y})\delta
p(t_{x}^{\prime},t_{y}^{\prime})]$
$\displaystyle=E\left[\sum_{X,Y}p(t_{x}|x)p(t_{y}|y)\delta
p(x,y)\sum_{X^{\prime},Y^{\prime}}p(t_{x}^{\prime}|x^{\prime})p(t_{y}^{\prime}|y^{\prime})\delta
p(x^{\prime},y^{\prime})\right]$
$\displaystyle=\sum_{X,Y,X^{\prime},Y^{\prime}}p(t_{x}|x)p(t_{y}|y)p(t_{x}^{\prime}|x^{\prime})p(t_{y}^{\prime}|y^{\prime})E[\delta
p(x,y)\delta p(x,y)]$
$\displaystyle=\sum_{X,Y,X^{\prime},Y^{\prime}}p(t_{x}|x)p(t_{y}|y)p(t_{x}^{\prime}|x^{\prime})p(t_{y}^{\prime}|y^{\prime})$
$\displaystyle\quad\quad\quad\times\frac{p(x,y)\delta(x,x^{\prime})\delta(y,y^{\prime})-p(x,y)p(x^{\prime},y^{\prime})}{N}$
$\displaystyle=\left[\frac{\sum_{X,Y}p(t_{x}|x)p(t_{y}|y)p(t_{x}^{\prime}|x)p(t_{y}^{\prime}|y)p(x,y)}{N}\right]$
$\displaystyle\quad\quad\quad-\left[\frac{p(t_{x},t_{y})p(t_{x}^{\prime},t_{y}^{\prime})}{N}\right].$
(67)

Using the previous result and Eq. (62), we find:

$\displaystyle E[\delta I(T_{X},T_{Y})^{2}]$
$\displaystyle=\sum_{T_{X},T_{Y},T_{X}^{\prime},T_{Y}^{\prime}}E[\delta
p(t_{x},t_{y})\delta
p(t_{x}^{\prime},t_{y}^{\prime})]\left(\log\frac{p(t_{x},t_{y})}{p(t_{x})p(t_{y})}-1\right)$
$\displaystyle\quad\quad\quad\times\left(\log\frac{p(t_{x}^{\prime},t_{y}^{\prime})}{p(t_{x}^{\prime})p(t_{y}^{\prime})}-1\right)$
$\displaystyle=\sum_{T_{X},T_{Y},T_{X}^{\prime},T_{Y}^{\prime}}\left[\frac{\sum_{X,Y}p(t_{x}|x)p(t_{y}|y)p(t_{x}^{\prime}|x)p(t_{y}^{\prime}|y)p(x,y)}{N}\right.$
$\displaystyle\quad\quad\quad\times\left.\log\frac{p(t_{x},t_{y})}{p(t_{x})p(t_{y})}\log\frac{p(t_{x}^{\prime},t_{y}^{\prime})}{p(t_{x}^{\prime})p(t_{y}^{\prime})}\right]-I(T_{X},T_{Y})^{2}/N.$
(68)

In the “winner takes all limit”, where $p(t_{x}|x)=\delta(t_{x},\tau_{x}(x))$,
and $p(t_{y}|y)=\delta(t_{y},\tau_{y}(y))$, we find:

$\displaystyle E[\delta I(T_{X},T_{Y})^{2}]=$
$\displaystyle\quad\quad=\sum_{T_{X},T_{Y},T_{X}^{\prime},T_{Y}^{\prime}}\left[\frac{\sum_{X,Y}\delta(t_{x},\tau_{x}(x))\delta(t_{y},\tau_{y}(y))\delta(t_{x}^{\prime},\tau_{x}(x))\delta(t_{y}^{\prime},\tau_{y}(y))p(x,y)}{N}\right.$
$\displaystyle\quad\quad\quad\quad\quad\times\left.\log\frac{p(t_{x},t_{y})}{p(t_{x})p(t_{y})}\log\frac{p(t_{x}^{\prime},t_{y}^{\prime})}{p(t_{x}^{\prime})p(t_{y}^{\prime})}\right]-I(T_{X},T_{Y})^{2}/N$
$\displaystyle\quad\quad=\sum_{X,Y}\left[\frac{p(x,y)}{N}\log\left(\frac{p(\tau_{x}(x),\tau_{y}(y))}{p(\tau_{x}(x))p(\tau_{y}(y))}\right)^{2}\right]-I(T_{X},T_{Y})^{2}/N$
$\displaystyle\quad\quad\leq\frac{1}{N}\log\left(\min(|T_{X}|,|T_{Y}|)\right)^{2}-I(T_{X},T_{Y})^{2}/N.$
(69)

Here we have calculate the average bias and variance for each term in the GSIB
and the GIB. We found, in general, that the variance decays as $1/N$ and
depends only on the cardinality of the compressed variables $|T_{X}|$ and
$|T_{Y}|$. The expected bias for the GSIB depends on the cardinality of the
compressed variables, while the bias for the GIB can depend on both the
cardinality of the compressed variables and the cardinality of the
uncompressed supervisor variables $|X|$ and $|Y|$.

## References

  * Andersen and Bro, (2010) Andersen, C. M. and Bro, R. (2010).  Variable selection in regression—a tutorial.  Journal of chemometrics, 24(11-12):728–737.
  * Andrew et al., (2013) Andrew, G., Arora, R., Bilmes, J., and Livescu, K. (2013).  Deep canonical correlation analysis.  In Dasgupta, S. and McAllester, D., editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1247–1255, Atlanta, Georgia, USA. PMLR.
  * Antos and Kontoyiannis, (2001) Antos, A. and Kontoyiannis, I. (2001).  Convergence properties of functional estimates for discrete distributions.  Random Structures & Algorithms, 19(3-4):163–193.
  * Belghazi et al., (2018) Belghazi, M. I., Baratin, A., Rajeshwar, S., Ozair, S., Bengio, Y., Courville, A., and Hjelm, D. (2018).  Mutual information neural estimation.  In International conference on machine learning, pages 531–540. PMLR.
  * Carreira-Perpinán, (1997) Carreira-Perpinán, M. A. (1997).  A review of dimension reduction techniques.  Department of Computer Science. University of Sheffield. Tech. Rep. CS-96-09, 9:1–69.
  * Chapman and Wang, (2021) Chapman, J. and Wang, H.-T. (2021).  Cca-zoo: A collection of regularized, deep learning based, kernel, and probabilistic cca methods in a scikit-learn style framework.  Journal of Open Source Software, 6(68):3823.
  * Cover, (1999) Cover, T. M. (1999).  Elements of information theory.  John Wiley & Sons.
  * de Vries et al., (2020) de Vries, S. E., Lecoq, J. A., Buice, M. A., Groblewski, P. A., Ocker, G. K., Oliver, M., Feng, D., Cain, N., Ledochowitsch, P., Millman, D., et al. (2020).  A large-scale standardized physiological survey reveals functional organization of the mouse visual cortex.  Nature neuroscience, 23(1):138–151.
  * Fisher and Mehta, (2015) Fisher, C. K. and Mehta, P. (2015).  Bayesian feature selection for high-dimensional linear regression via the ising approximation with applications to genomics.  Bioinformatics, 31(11):1754–1761.
  * Goebel et al., (2005) Goebel, B., Dawy, Z., Hagenauer, J., and Mueller, J. (2005).  An approximation to the distribution of finite sample size mutual information estimates.  In IEEE Int Conf Commun (ICC), volume 2, pages 1102–1106. IEEE.
  * Haghighi et al., (2022) Haghighi, M., Caicedo, J. C., Cimini, B. A., Carpenter, A. E., and Singh, S. (2022).  High-dimensional gene expression and morphology profiles of cells across 28,000 genetic and chemical perturbations.  Nature methods, 19(12):1550–1557.
  * Hinton and Salakhutdinov, (2006) Hinton, G. E. and Salakhutdinov, R. R. (2006).  Reducing the dimensionality of data with neural networks.  science, 313(5786):504–507.
  * Holbrook et al., (2017) Holbrook, A., Vandenberg-Rodes, A., Fortin, N., and Shahbaba, B. (2017).  A bayesian supervised dual-dimensionality reduction model for simultaneous decoding of lfp and spike train signals.  Stat, 6(1):53–67.
  * Hotelling, (1933) Hotelling, H. (1933).  Analysis of a complex of statistical variables into principal components.  Journal of educational psychology, 24(6):417.
  * Hotelling, (1936) Hotelling, H. (1936).  Relations between two sets of variates.  Biometrika.
  * Kingma and Welling, (2014) Kingma, D. P. and Welling, M. (2014).  Auto-Encoding Variational Bayes.  In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings.
  * Kraskov et al., (2004) Kraskov, A., Stögbauer, H., and Grassberger, P. (2004).  Estimating mutual information.  Phys Rev E, 69(6):066138.
  * Kruskal, (1964) Kruskal, J. B. (1964).  Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis.  Psychometrika, 29(1):1–27.
  * Kullback and Leibler, (1951) Kullback, S. and Leibler, R. A. (1951).  On information and sufficiency.  The annals of mathematical statistics, 22(1):79–86.
  * Kuo and Mallick, (1998) Kuo, L. and Mallick, B. (1998).  Variable selection for regression models.  Sankhyā: The Indian Journal of Statistics, Series B, pages 65–81.
  * Lee and Seung, (1999) Lee, D. D. and Seung, H. S. (1999).  Learning the parts of objects by non-negative matrix factorization.  Nature, 401(6755):788–791.
  * McInnes et al., (2018) McInnes, L., Healy, J., and Melville, J. (2018).  Umap: Uniform manifold approximation and projection for dimension reduction.  arXiv preprint arXiv:1802.03426.
  * Nanga et al., (2021) Nanga, S., Bawah, A. T., Acquaye, B. A., Billa, M.-I., Baeta, F. D., Odai, N. A., Obeng, S. K., and Nsiah, A. D. (2021).  Review of dimension reduction methods.  Journal of Data Analysis and Information Processing, 9(3):189–231.
  * Paninski, (2003) Paninski, L. (2003).  Estimation of entropy and mutual information.  Neural computation, 15(6):1191–1253.
  * Roulston, (1999) Roulston, M. (1999).  Estimating the errors on measured entropy and mutual information.  Physica D, 125(3-4):285–294.
  * Scott and Crone, (2021) Scott, E. R. and Crone, E. E. (2021).  Using the right tool for the job: the difference between unsupervised and supervised analyses of multivariate ecological data.  Oecologia, 196(1):13–25.
  * Shamir et al., (2010) Shamir, O., Sabato, S., and Tishby, N. (2010).  Learning and generalization with the information bottleneck.  Theoretical Computer Science, 411(29-30):2696–2711.
  * Shannon, (1948) Shannon, C. E. (1948).  A mathematical theory of communication.  The Bell system technical journal, 27(3):379–423.
  * Siegle et al., (2021) Siegle, J. H., Jia, X., Durand, S., Gale, S., Bennett, C., Graddis, N., Heller, G., Ramirez, T. K., Choi, H., Luviano, J. A., et al. (2021).  Survey of spiking in the mouse visual system reveals functional hierarchy.  Nature, 592(7852):86–92.
  * Slonim et al., (2006) Slonim, N., Friedman, N., and Tishby, N. (2006).  Multivariate information bottleneck.  Neural computation, 18(8):1739–1789.
  * Sponberg et al., (2015) Sponberg, S., Daniel, T. L., and Fairhall, A. L. (2015).  Dual dimensionality reduction reveals independent encoding of motor features in a muscle synergy for insect flight control.  PLoS Computational Biology, 11(4):e1004168.
  * Still and Bialek, (2004) Still, S. and Bialek, W. (2004).  How many clusters? an information-theoretic perspective.  Neural computation, 16(12):2483–2506.
  * Strouse and Schwab, (2017) Strouse, D. and Schwab, D. (2017).  The deterministic information bottleneck.  Neural computation, 29(6):1611–1630.
  * Tenenbaum et al., (2000) Tenenbaum, J. B., Silva, V. d., and Langford, J. C. (2000).  A global geometric framework for nonlinear dimensionality reduction.  science, 290(5500):2319–2323.
  * Tishby et al., (2000) Tishby, N., Pereira, F., and Bialek, W. (2000).  The information bottleneck method.  arXiv preprint physics/0004057.
  * Tishby and Slonim, (2000) Tishby, N. and Slonim, N. (2000).  Data clustering by markovian relaxation and the information bottleneck method.  Adv Neural Inf Proc Syst, 13.
  * Van der Maaten and Hinton, (2008) Van der Maaten, L. and Hinton, G. (2008).  Visualizing data using t-sne.  Journal of machine learning research, 9(11).
  * Van Der Maaten et al., (2009) Van Der Maaten, L., Postma, E. O., van den Herik, H. J., et al. (2009).  Dimensionality reduction: A comparative review.  Journal of Machine Learning Research, 10(66-71):13.
  * Wold, (1966) Wold, H. (1966).  Estimation of principal components and related models by iterative least squares.  Multivariate analysis, pages 391–420.
  * Wold et al., (2001) Wold, S., Sjöström, M., and Eriksson, L. (2001).  Pls-regression: a basic tool of chemometrics.  Chemometrics and Intelligent Laboratory Systems, 58(2):109–130.  PLS Methods.
  * Yang et al., (2021) Yang, X., Liu, W., Liu, W., and Tao, D. (2021).  A survey on canonical correlation analysis.  IEEE Transactions on Knowledge and Data Engineering, 33(6):2349–2368.
  * Zhuang et al., (2020) Zhuang, X., Yang, Z., and Cordes, D. (2020).  A technical review of canonical correlation analysis for neuroscience applications.  Human Brain Mapping, 41(13):3807–3833.