Year: 2018

Abstract:
We study the evolution of internal representations during deep neural network (DNN) training, aiming to demystify the compression aspect of the information bottleneck theory. The theory suggests that DNN training comprises a rapid fitting phase followed by a slower compression phase, in which the mutual information I(X;T ) between the input X and internal representations T decreases. Several papers observe compression of estimated mutual information on different DNN models, but the true I(X;T ) over these networks is provably either constant (discrete X) or infinite (continuous X). This work explains the discrepancy between theory and experiments, and clarifies what was actually measured by these past works. To this end, we introduce an auxiliary (noisy) DNN framework for which I(X;T ) is a meaningful quantity that depends on the network’s parameters. This noisy framework is shown to be a good proxy for the original (deterministic) DNN both in terms of performance and the learned representations. We then develop a rigorous estimator for I(X;T ) in noisy DNNs and observe compression in various models. By relating I(X;T ) in the noisy DNN to an information-theoretic communication problem, we show that compression is driven by the progressive clustering of hidden representations of inputs from the same class. Several methods to directly monitor clustering of hidden representations, both in noisy and deterministic DNNs, are used to show that meaningful clusters form in the T space. Finally, we return to the estimator of I(X;T ) employed in past works, and demonstrate that while it fails to capture the true (vacuous) mutual information, it does serve as a measure for clustering. This clarifies the past observations of compression and isolates the geometric clustering of hidden representations as the true phenomenon of interest.

heading: 1 INTRODUCTION
text: Recent work by Shwartz-Ziv & Tishby (2017) uses the Information Bottleneck framework (Tishby et al., 1999; Tishby & Zaslavsky, 2015) to study the dynamics of DNN learning. The framework considers the mutual information pair ( I(X;T`), I(Y ;T`) ) between the input X or the label Y and the network’s hidden layers T`. Plotting the evolution of these quantities during training, Shwartz-Ziv & Tishby (2017) made two interesting observations: (1) while I(Y ;T`) remains mostly constant as the layer index ` increases, I(X;T`) decreases, suggesting that layers gradually shed irrelevant information about X; and (2) after an initial fitting phase, there is a long compression phase during which I(X;T`) slowly decreases. It was suggested that this compression is responsible for the generalization performance of DNNs. A follow-up paper (Saxe et al., 2018) contends that compression is not inherent to DNN training, claiming double-sided saturating nonlinearities yield compression while single-sided/non-saturating ones do not necessarily compress. Shwartz-Ziv & Tishby (2017) and Saxe et al. (2018) present many plots of ( I(X;T`), I(Y ;T`)
) evolution across training epochs. These plots, however, are inadvertently misleading: they show a dynamically changing I(X;T`) when the true mutual information is provably either infinite or a constant independent of the DNN’s parameters (see (Amjad & Geiger, 2018) for a discussion of further degeneracies related to to the Information Bottleneck framework). Recall that the mutual information I(X;T`) is a functional of the joint distribution of (X,T`) ∼ PX,T` = PXPT`|X , and that, in standard DNNs, T` is a deterministic function of X . Hence, if PX is continuous, then so is T`, and thus I(X;T`) = ∞ (cf. (Polyanskiy & Wu, 2012-2017, Theorem 2.4)). If PX is discrete (e.g., when the features are discrete or if X adheres to an empirical distribution over the dataset), then the mutual information is a finite constant that does not depend on the parameters of the DNN. Specifically, for deterministic DNNs, the mapping from a discrete X to T` is injective for strictly
monotone nonlinearities such as tanh or sigmoid, except for a measure-zero set of weights. In other words, deterministic DNNs can encode all information about a discrete X in arbitrarily fine variations of T`, causing no loss of information and implying I(X;T`) = H(X), even if deeper layers ` have fewer neurons.
The compression observed in Shwartz-Ziv & Tishby (2017) and Saxe et al. (2018) therefore cannot be due to changes in mutual information. This discrepancy between theory and experiments originates from a theoretically unjustified discretization of neuron values in their approximation of I(X;T`). To clarify, the quantity computed and plotted in these works is I(X;Bin(T`)), where Bin is a per-neuron discretization of each hidden activity of T` into a user-selected number of bins. This I ( X;Bin(T`) ) is highly sensitive to the selection of bin size (as illustrated in Fig. 1) and does not track I(X;T`) for any choice of bin size.1 Nonetheless, compression results based on I ( X;Bin(T`) ) are observed by Shwartz-Ziv & Tishby (2017) and Saxe et al. (2018) in many interesting cases.
To understand this curious phenomenon we first develop a rigorous framework for tracking the flow of information in DNNs. In particular, to ensure I(X;T`) is meaningful for studying the learned representations, we need to make the map X 7→ T` a stochastic parameterized channel whose parameters are the DNN’s weights and biases. We identify several desirable criteria that such a stochastic DNN framework should fulfill for it to provide meaningful insights into commonly used practical systems. (1) The stochasticity should be intrinsic to the operation of the DNN, so that the characteristics of mutual information measures are related to the learned internal representations, and not to an arbitrary user-defined parameter. (2) The stochasticity should relate the mutual information to the deterministic binned version I ( X;Bin(T`) ) , since this is the object whose compression was observed; this requires the injected noise to be isotropic over the domain of T` analogously to the per-neuron binning operation. And most importantly, (3) the network trained under this stochastic model should be closely related to those trained in practice.
We propose a stochastic DNN framework in which independent and identically distributed (i.i.d.) Gaussian noise is added to the output of each of the DNN’s neurons. This makes the map from X to T` stochastic, ensures the data processing inequality (DPI) is satisfied, and makes I(X;T`) reflect the true operating conditions of the DNN, following Point (1). Since the noise is centered and isotropic, Point (2) holds. As for Point (3), Section 2 experimentally shows the DNN’s learned representations and performance are not meaningfully affected by the addition of noise, for variances β2 not too large. Furthermore, randomness during training has long been used to improve neural network performance, e.g., to escape poor local optima (Hinton et al., 1984), improve generalization performance (Srivastava et al., 2014), encourage learning of disentangled representations (Achille & Soatto, 2018), and ensure gradient flow with hard-saturating nonlinearities (Gulcehre et al., 2016).
Under the stochastic model, I(X;T`) has no exact analytic expression and is impossible to approximate numerically. In Section 3 we therefore propose a sampling technique that decomposes the estimation of I(X;T`) into several instances of a simpler differential entropy estimation problem: estimating h(S + Z) given n samples of the d-dimensional random vector S and knowing the distribution of Z ∼ N (0, β2Id). We analyze this problem theoretically and show that any differential entropy estimator over the noisy DNN requires at least exponentially many samples in the dimension d. Leveraging the explicit modeling of S + Z, we then propose a new estimator that converges
1Another approach taken in Saxe et al. (2018) considers I(X;T` + Z) (instead of I ( X;Bin(T`) ) ), where Z is an independent Gaussian with a user-defined variance. This approach has two issues: (i) the values as a function of ` may violate the data processing inequality, and (ii) they do not reflect the operation of the actual DNN, which was trained without noise. We focus on I ( X;Bin(T`) ) because it was commonly used in Shwartz-Ziv & Tishby (2017) and Saxe et al. (2018), and since both methods have a similar effect of blurring T`.
as O ( (log n)d/4/ √ n ) , which significantly outperforms the convergence rate of general-purpose differential entropy estimators when applied to the noisy DNN framework.
We find that I(X;T`) exhibits compression in many cases during training of small DNN classifiers. To explain compression in an insightful yet rigorous manner, Section 4 relates I(X;T`) to the well-understood notion of data transmission over additive white Gaussian noise (AWGN) channels. Namely, I(X;T`) is the aggregate information transmitted over the channel PT`|X with input X drawn from a constellation defined by the data samples and the noisy DNN parameters. As training progresses, the representations of inputs from the same class tend to cluster together and become increasingly indistinguishable at the channel’s output, thereby decreasing I(X;T`). Furthermore, these clusters tighten as one moves into deeper layers, providing evidence that the DNN’s layered structure progressively improves the representation of X to increase its relevance for Y .
Finally, we examine clustering in deterministic DNNs. We identify methods for measuring clustering that are valid for both noisy and deterministic DNNs, and show that clusters of inputs in learned representations typically form in both cases. We complete the circle back to I ( X;Bin(T`) ) by clarifying why this binned mutual information measures clustering. This explains what previous works were actually observing: not compression of mutual information, but increased clustering by hidden representations. The geometric clustering of hidden representations is thus the fundamental phenomenon of interest, and we aim to test its connection to generalization performance, theoretically and experimentally, in future work.
2 PRELIMINARY DEFINITIONS
Tℓ−1 σ ( W
Noisy DNNs: For integers k ≤ `, let [k : `] , { i ∈ Z ∣∣k ≤ i ≤ ` } and use [`] when k = 1. Consider a noisy DNN with L+ 1 layers {T`}`∈[0:L], with input T0 = X and output TL. The `th hidden layer, ` ∈ [L − 1], is described by T` = f`(T`−1) + Z`, where f` : Rd`−1 → Rd` is a deterministic function of the previous layer and Z` ∼ N ( 0, β2Id` ) ; no noise is injected to the output, i.e., TL = fL(TL−1). We set S` , f`(T`−1) and use ϕ for the probability density function (PDF) of Z`. The functions {f`}`∈[L] can represent any type of layer (fully connected, convolutional, max-pooling, etc.). Fig. 2 shows a neuron in the `th layer of a noisy DNN.
To explore the relation between noisy and deterministic DNNs under conditions representative of current machine learning practices, we trained four-layer convolutional neural networks (CNNs) on MNIST (LeCun et al., 1999). The CNNs used different levels of internal noise, including no noise, and one used dropout in place of additive noise. We measured their performance on the validation set and characterized the cosine similarities between their internal representations. Full details of the CNN architecture and training procedure are in Supplement 9.3. The results in Table 1 show small amounts of internal additive noise (β ≤ 0.1) have a minimal impact on classification performance, while dropout strongly improves it. The histograms in Fig. 3 show that the noisy (for small β) and dropout models learn internal representations similar to
the representations learned by the deterministic model. In this high-dimensional space, unrelated representations would create cosine similarity histograms with zero mean and standard deviation between 0.02–0.3, so the observed values are quite large. As expected, dissimilarity increases as the noise increases, and similarity is lower for the internal layers (2 and 3).
Mutual Information: Noisy DNNs induce a stochastic map from X to the rest of the network, described by the conditional distribution PT1,...,TL|X . The corresponding PDF
2 is pT1,...,TL|X=x. Its marginals are denoted by keeping only the relevant variables in the subscript. Let X , {xi}i∈[m] be
2PT1,...,TL|X=x is absolutely continuous with respect to (w.r.t.) the Lebesgue measure for all x ∈ X .
the input dataset, and P̂X be its empirical distribution, described by the probability mass function (PMF) p̂X (x) = 1m ∑ i∈[m] 1{xi=x}, for x ∈ X . Since data sets typically contain no repetitions, we assume p̂X (x) = 1m , ∀x ∈ X . The input and the hidden layers are jointly distributed according to3 PX,T1,...,TL , P̂XPT1,...,TL|X , under which X − T1 − . . .− TL−1 − TL forms a Markov chain. For each ` ∈ [L− 1], we study the mutual information (Supplement 7 explains this factorization)
I(X;T`) , ∫
X×Rd` dPX,T` log
( dPX,T`
dPX × PT`
) = h(pT`)− 1
m
∑
i∈[m] h(pT`|X=xi), (1)
where log(·) is with respect to the natural base. Although PT` and PT`|X are readily sampled from using the DNN’s forward pass, these distributions are too complicated (due to the composition of Gaussian noises and nonlinearities) to analytically compute I(X;T`) or even to evaluate their densities at the sampled points. Therefore, we must estimate I(X;T`) directly from the available samples.

heading: 3 MUTUAL INFORMATION ESTIMATION OVER NOISY DNNS
text: Expanding I(X;T`) as in (1), our goal is to estimate h(pT`) and h(pT`|X=x), ∀x ∈ X : a problem that we show is hard in high dimensions. Each differential entropy term is estimated and computed via a two-step process. First, we develop the sample propagation (SP) estimator, which exploits the ability to propagate samples up the DNN layers and the known noise distribution. This estimator approximates each true entropy by the differential entropy of a known Gaussian mixture (defined only through the available resources: the samples we obtain from the DNN and the noise parameter). This estimate is shown to converge to the true entropy when the number of samples grows. However, since the entropy of a Gaussian mixture has no closed-form expression, in the second (computational) step we use Monte Carlo (MC) integration to numerically evaluate it.

heading: 3.1 THE SAMPLE-PROPAGATION DIFFERENTIAL ENTROPY ESTIMATOR
text: In what follows, we denote the empirical PMF associated with a set A = {ai}i∈[n] ⊂ Rd by p̂A. Unconditional Entropy: Since T` = S` + Z`, where S` and Z` are independent, we have pT` = pS` ∗ ϕ. To estimate h(pT`), let {x̂j}j∈[n] be n i.i.d. samples from PX . Feed each x̂j into the DNN and collect the outputs it produces at the (`− 1)-th layer. The function f` is then applied on each collected output to obtain S` , { s`,1, s`,2, . . . , s`,n } , which is a set of n i.i.d. samples from pS` . We estimate h(pT`) by h(p̂S` ∗ ϕ), which is the differential entropy of a Gaussian mixture with centers s`,j , j ∈ [n]. The term h(p̂S` ∗ ϕ) is referred to as the SP estimator of h(pT`) = h(pS` ∗ ϕ). Conditional Entropies: Fix i ∈ [m] and consider the estimation of h(pT`|X=xi). Note that pT`|X=xi = pS`|X=xi ∗ ϕ since Z` is independent of (X,T`−1). To sample from pS`|X=xi , we feed xi into the DNN ni times, collect outputs from T`−1 corresponding to different noise realizations, and apply f` on each. The obtained samples S(i)` , { s (i) `,1, s (i) `,2, . . . , s (i) `,ni } are i.i.d. according to
pS`|X=xi . Each h(pT`|X=xi) = h(pS`|X=xi ∗ ϕ) is estimated by the SP estimator h ( p̂S(i)` ∗ ϕ ) .4 Mutual Information Estimator: Combining the above described pieces, we estimate I(X;T`) by
̂I(X;T`) = h(p̂S` ∗ ϕ)− 1
m ∑ i∈[m] h ( p̂S(i)` ∗ ϕ ) . (2)
3We set X ∼ Unif(X ) to conform with past works (Shwartz-Ziv & Tishby, 2017; Saxe et al., 2018). 4For ` = 1, we have h(T1|X) = h(Z1) = d12 log(2πeβ2) because its previous layer is X (fixed).

heading: 3.2 THEORETICAL GUARANTEES AND COMPUTING THE ESTIMATOR
text: The above sampling procedure unifies the estimation of h(pT`) and { h(pT`|X=x) } x∈X into a single new differential entropy estimation problem: estimate h(pS ∗ ϕ) based on i.i.d. samples Sn , (Si)i∈[n] from pS and knowledge of ϕ. The SP estimator solution approximates h(pS ∗ ϕ) by ĥSP(S
n, ϕ) , h(p̂Sn ∗ ϕ), where p̂Sn is the empirical PMF induced by Sn. Before analyzing the performance of ĥSP, we note that this estimation problem is statistically difficult in the sense that any good estimator of h(pS ∗ϕ) based on Sn and ϕ requires exponentially many samples in d (Theorem 2 from Supplement 10). Nonetheless, the following theorem shows that the SP estimator absolute-error risk converges at a satisfactory rate (Theorem 4 from Supplement 10 states this with all constants explicit, and Theorem 5 gives the results for ReLU).
Theorem 1 Fix β > 0, d ≥ 1, and let Fd be the class of d-dimensional PDFs supported inside [−1, 1]d. We have: suppS∈Fd E ∣∣h(pS ∗ ϕ)− ĥSP(Sn, ϕ) ∣∣ = O ( (log n)d/4/ √ n ) .
Evaluating the SP estimator ĥSP(Sn, ϕ) of the true entropy h(pS ∗ ϕ) requires computing the differential entropy of the (known) Gaussian mixture p̂sn ∗ ϕ since
ĥSP(S n, ϕ) = h ( p̂sn ∗ ϕ ) . (3)
Noting that the differential entropy h(p) = −EX∼p[log p(X)], we rewrite the SP estimator as
ĥSP(S n, ϕ) = h(G) = −E [ log ( (p̂sn ∗ ϕ)(G) )] , (4)
where G ∼ p̂sn ∗ ϕ is distributed according to the Gaussian mixture. We numerically approximate the right-hand side of (4) via efficient Monte Carlo (MC) integration (Robert, 2004). Specifically, we generate nMC i.i.d. samples from p̂sn ∗ ϕ and approximate the expectation by an empirical average. This unbiased approximation achieves a mean squared error of O ( (n · nMC)−1 ) (Supplement 10). This approximation thus only adds a negligible amount to the error of the SP estimator ∣∣h(pS ∗ ϕ) − ĥSP(Sn, ϕ)
∣∣ itself. There are other ways to numerically evaluate this expectation, such as the Gaussian mixture bounds from Kolchinsky & Tracey (2017); however, our proposed method is the fastest approach of which we are aware.
Remark 1 (Choosing Noise Parameter and Number of Samples) We describe practical guidelines for selecting the noise standard deviation β and the number of samples n for estimating I(X;T`) in an actual classifier. Ideally, β should be treated as a hyperparameter tuned to optimize the performance of the classifier on held-out data, since internal noise serves as a regularizer similar to dropout. In practice, we find it is sometimes necessary to back off from the β value that optimizes performance to a higher value to ensure accurate estimation of mutual information (the smaller β is, the more samples our estimator requires), depending on factors such as the dimensionality of the layer being analyzed and the number of data samples available for a task.
The number of samples n can be selected using the bound in Theorem 1, but because this theorem is a worst-case result, in practice it is quite pessimistic. Specifically, generating the estimated mutual information curves shown in Section 5 requires running the SP estimator multiple times5, which makes the number of samples dictated by Theorem 1 infeasible. To overcome this computational burden while adhering to the theoretical result, we tested the value of n given by the theorem on a few points of each curve and reduced it until the overall computation cost became reasonable. To ensure estimation accuracy was not compromised we empirically tested that the estimate remained stable.
As a concrete example, to achieve an error bound of 5% of Fig. 5 plot’s vertical scale (which amounts to an 0.4 absolute error bound), the number of samples required by Theorem 1 is n = 4 · 109. This number is too large for our computational budget. Performing the above procedure for reducing n, we find good accuracy is achieved for n = 4 · 106 samples (Theorem 1 has the pessimistic error bound of 3.74 for this value). Adding more samples beyond this value does not change the results.
5Each I(X;T`), for a given set of DNN parameters, involves computingm+1 differential entropy estimates, and our experiments estimate the trajectory of I(X;T`) across training epochs.

heading: 4 COMPRESSION AND CLUSTERING: A MINIMAL EXAMPLE
text: Before presenting our empirical results, we connect compression to clustering using an informationtheoretic perspective. Consider a single noisy neuron with a one-dimensional input X . Let T (k) = S(k) + Z be the neuron’s output at epoch k, where S(k) , σ(wkX + bk), for a strictly monotone nonlinearity σ, and Z ∼ N (0, β2). Invariance of mutual information to invertible operations implies
I ( X;T (k) ) = I ( σ(wkX + bk);σ(wkX + bk) + Z ) = I ( S(k);S(k) + Z ) . (5)
From an information-theoretic perspective, I ( S(k);S(k) +Z ) is the aggregate information transmitted over an AWGN channel with input constellation Sk , { σ(wkx+ bk) | x ∈ X } . In other words,
I ( S(k);S(k) + Z ) is a measure of how distinguishable the symbols of Sk are when composed with Gaussian noise (roughly equals log of the number of resolvable clusters under noise level β). Since the distribution of T (k) = S(k) + Z is a Gaussian mixture with means s ∈ Sk, the closer two constellation points s and s′ are, the more overlapping the Gaussians around them will be. Hence reducing point spacing in Sk (by changing wk and bk) directly reduces I ( X;T (k) ) . Let σ = tanh and β = 0.01, and set X = X−1 ∪ X1, with X−1 = {−3,−1, 1} and X1 = {3}, labeled −1 and 1, respectively. We train the neuron using mean squared loss and gradient descent (GD) with a fixed learning rate of 0.01 to best illustrate the behavior of I ( X;T (k) ) . The Gaussian mixture pT (k) is plotted across epochs k in Fig. 4(a)-(b). The learned bias is approximately −2.3w, ensuring that the tanh transition region correctly divides the two classes. Initially w = 0, so all four Gaussians in pT (0) are superimposed. As k increases, the Gaussians initially diverge, with the three from X−1 eventually re-converging as they each meet the tanh boundary. This is reflected in the mutual information trend in Fig. 4(c), with the dips in I ( X;T (k) ) around k = 103 and k = 104 corresponding to the second and third Gaussians respectively merging into the first. Thus, there is a direct connection between clustering and compression. Fig. 4(d) shows the mutual information for different noise levels β as a function of epoch. For small β (as above) the X−1 Gaussians are distinct and merge in two stages as w grows. For larger β, however, the X−1 Gaussians are indistinguishable for any w, making I(X;T ) only increase as the two classes gradually separate. A similar example for a two-neuron network with leaky-ReLU nonlinearities is provided in the Supplement 8.

heading: 5 EMPIRICAL RESULTS
text: We now show the observations from our minimal examples also hold for two larger networks. Namely, the presented experiments demonstrate the compression of mutual information in noisy networks is driven by clustering of internal representation, and that deterministic networks cluster samples as well (despite I(X;T`) being constant over these systems). The DNNs we consider are: (1) the small, fully connected network (FCN) studied in (Shwartz-Ziv & Tishby, 2017; Saxe et al., 2018), which we call the SZT model; and (2) a convolutional network for MNIST classification, called MNIST CNN. We present selected results; additional details and experiments are found in the supplement.
SZT model:
Consider the data and model of Shwartz-Ziv & Tishby (2017) for binary classification of 12- dimensional inputs using a fully connected 12–10–7–5–4–3–2 architecture. The FCN was tested with tanh and ReLU nonlinearities as well as a linear model. Fig. 5(a) presents results for the SZT model with tanh nonlinearity and β = 0.005 (test classification accuracy 99%), showing the relationship across training epochs between estimated I(X;T`), train/test losses and the distribution of neuron values in 5 layers (layers 0 (d0 = 12) and 6 (d7 = 2) are not shown). The rise and fall of mutual information corresponds to how spread out or clustered the representation in each layer are. For
example, I(X;T5) grows until epoch 28, when the Gaussians move away from each other along a curve (see scatter plots on the right). Around epoch 80 they start clustering and I(X;T5) drops. At the end of training, the saturating tanh nonlinearities push the Gaussians to two furthest corners of the cube, reducing I(X;T5) even more.
To confirm that clustering (via saturation) was central to the compression observed in Fig. 5(a), we also trained the model using the regularization from (Cisse et al., 2017) (test classification accuracy 96%), which encourages orthonormal weight matrices. The results are shown in Fig. 5(b). Apart from minor initial fluctuations, the bulk of compression is gone. The scatter plots show that the vast majority of neurons do not saturate and no clustering is observed at the later stages of training. Saturation is not the only mechanism that can cause clustering and consequently reduce I(X;T`). For example, in Fig. 5(c) we illustrate the clustering behavior in a linear SZT model (test
classification accuracy 89%). As seen from the scatter plots, due to the formation of several clusters and projection to a lower dimensional space, I(X;T`) drops even without the nonlinearities. The results in Fig. 5(a) and (b) also show that the relationship between compression and generalization performance is not a simple one. In Fig. 5(a), the test loss begins to increase at roughly epoch 3200 and continues to increase until training ends, while at the same time compression occurs in layers 4 and 5. In contrast, in Fig. 5(b) the test loss does not increase, and compression does not occur in layers 4 and 5. We believe that this is a subject that deserves further examination in future work.
To provide another perspective on clustering that is sensitive to class membership, we compute histograms of pairwise distances between representations of samples, distinguishing within-class distances from between-class distances. Fig. 6 shows histograms for the SZT models from Figs. 5(a) and (b). As training progresses, the formation of clusters is clearly seen (layer 3 and beyond) for the unnormalized SZT model in Fig. 5(a). In the normalized model (Fig. 5(b)), however, no tight clustering is apparent, supporting the connection between clustering and compression.
Once clustering is identified as the source of compression, we focus on it as the point of interest. To measure clustering, the discrete entropy of Bin(T`) is considered, where the number of equal-sized bins, B, is a tuning parameter. Note that Bin(T`) partitions the dynamic range (e.g., [−1, 1]d` for a tanh layer) into Bd` cells or bins. When hidden representations are spread out, many bins will be non-empty, each assigned with a positive probability mass. On the other hand, for clustered representations, the distribution is concentrated on a small number of bins, each with relatively high probability. Recalling that discrete entropy is maximized by the uniform distribution, we see why reduction in H ( Bin(T`) ) measures clustering. To illustrate this measure, we compute H ( Bin(T`) ) for each of the SZT models using bin size B = 10β (bottom plots in Fig. 5(a), (b) and (c)). We can see a clear correspondence between H ( Bin(T`) ) and I(X;T`), indicating that although H ( Bin(T`) ) does not capture the exact value of I(X;T`), it follows this mutual information in measuring clustering. This is particularly important when moving back to deterministic DNNs, where I(X;T`) is no longer an informative measure, being either a constant or infinity, for discrete or continuous X , respectively. Fig. 1 shows H ( Bin(T`) ) for the deterministic SZT model (β = 0). The bin size is a free parameter,
and depending on its value, H ( Bin(T`) ) reveals different clustering granularities. Moreover, since in
deterministic networks T` = f`(X), for a deterministic map f`, we have H ( Bin(T`) ∣∣X ) = 0, and
therefore I ( X;Bin(T`) ) = H ( Bin(T`) ) . Thus, the plots from (Shwartz-Ziv & Tishby, 2017), (Saxe et al., 2018) and our Figs. 1 and 5(a), (b) and (c) all show the entropy of the binned T`.
MNIST CNN: We now examine a model that is more representative of current machine learning practice: the MNIST CNN trained with dropout from Section 2. Fig. 7 portrays the near-injective behavior of this model. Even when only two bins are used to compute H ( Bin(T`) ) , it takes values that are approximately ln(10000) = 9.210, for all layers and training epochs, even though the two convolutional layers use max-pooling.
This binning merges two samples in the validation set, so the input has H ( Bin(T`) ) = 9.209. While Fig. 7 does not show compression at the level of entire layers, computing H ( Bin(T`(k)) ) for individual units k in layer 3 reveals a gradual decrease over epochs 1–128. To quantify this trend, we computed linear regressions predicting H ( Bin(T`(k)) ) from the epoch index, for all units k in layer 3. Then we found the mean and standard deviation of the slope of the linear predictions. If most slopes are negative, then compression occurs during training at the level of individual units. For a range of bin sizes from 10−4–10−1 the least negative mean slope was −0.002 nats/epoch with a maximum standard deviation of 0.001, showing that most units undergo compression.
In Fig. 8 we show histograms of pairwise distances between MNIST validation set samples in the input (pixel) space and in the four layers of the CNN. The histograms were computed for epochs 0, 1, 32, and 128, where epoch 0 is the initial random weights and epoch 128 is the final weights. The histogram for the input shows that the mode of within-class pairwise distances is lower than the mode of between-class pairwise distances, but that there is substantial overlap. Layers 1 and 2, which are convolutional and therefore do not contain any units that receive the full input, do little to reduce this overlap, suggesting that the features learned in these layers are somewhat generic. In contrast, even after one epoch of training, layers 3 and 4, which are fully connected, separate the distribution of within-class distances from the distribution of between-class distances.
To summarize, we made the following observations in our experiments. (i) Compression can be observed in a noisy network that is similar to the deterministic network in which (Shwartz-Ziv & Tishby, 2017) reported compression (upper left plot in Fig. 5(a)). (ii) Compression is caused by clustering of samples, with clusters most often comprising samples having the same class label, as seen in the scatter plots on the right sides of Figs. 5(a) and (c) and the distributions of pairwise distances between samples shown in Figs. 6 and 8. (iii) Regularization that limits the ability of a network to drive hidden units into saturation may limit or eliminate compression (and clustering) as seen in Fig. 5(b). Fig. 5 also demonstrated that I(X;T`) and H ( Bin(T`) ) are highly correlated, establishing the latter as an additional measure for clustering (applicable both in noisy and deterministic DNNs). (iv) Clustering of internal representations can also be observed in a somewhat larger, convolutional network trained on MNIST. While Fig. 7 shows that due to the dimensionality, H ( Bin(T`) ) fails to track compression in the larger CNN, strong evidence for clustering is found via estimates done at the level of individual units (described in the text on the MNIST CNN) and the analysis of pairwise distances between samples shown in Fig. 8.

heading: 6 CONCLUSIONS
text: In this work we reexamined the compression aspect of the Information Bottleneck theory (ShwartzZiv & Tishby, 2017), noting that fluctuations of I(X;T`) in deterministic networks with strictly
monotone nonlinearities are theoretically impossible. Setting out to discover the source of compression observed in past works, we: (i) created a rigorous framework for studying and accurately estimating information-theoretic quantities in DNNs whose weights are fixed; (ii) identified clustering of the learned representations as the phenomenon underlying compression; and (iii) demonstrated that the compression-related experiments from past works were in fact measuring this clustering through the lens of the binned mutual information. In the end, although binning-based measures do not accurately estimate mutual information, they are simple to compute and prove useful for tracking changes in clustering, which is the true effect of interest in deterministic DNNs. We believe that further study of geometric phenomena driven by DNN training is warranted to better understand the learned representations and to potentially establish connections with generalization.

heading: 7 MUTUAL INFORMATION
text: Let (A,B) be a pair of random variables with values in the product set A×B and a joint distribution PA,B (whose marginals are denoted by PA and PB). The mutual information between A and B is:
I(A;B) , ∫
A×B dPA,B log
( dPA,B
dPA × PB
) , (5)
where dPA,BdPA×PB is the Radon-Nikodym derivative of PA,B with respect to the product measure PA × PB . We are mostly interested in the scenario where A is discrete with a probability mass function (PMF) pA, and given A = a ∈ A, B is continuous with probability density function (PDF) pB|A=a , pB|A(·|a). In this case, (5) simplifies to
I(A;B) = ∑
a∈A pA(a)
∫
B pB|A(b|a) log ( pB|A(b|a) pB(b) ) db. (6)
Defining the differential entropy of a continuous random variable C with PDF pC supported in C as1
h(C) = h(pC) = − ∫
C pC(c) log pC(c)dc, (7)
the mutual information from (6) can also be expressed as
I(A;B) = h(pB)− ∑
a∈A pA(a)h(pB|A=a). (8)
The subtracted term above is the conditional differential entropy of B given A, denoted by h(B|A).

heading: 8 TWO-NEURON LEAKY-RELU NETWORK EXAMPLE
text: To expand upon Section 4, we provide here a second example to illustrate the relation between clustering and compression of mutual information. In particular, this example also shows that as opposed to the claim from (Saxe et al., 2018), non-saturating nonlinearities can achieve compression. Consider the non-saturating Leaky-ReLU nonlinearity R(x) , max(x, x/10). Let X = X0 ∪ X1/4, with X0 = {1, 2, 3, 4} and X1/4 = {5, 6, 7, 8}, and labels 0 and 1/4, respectively. We train the network via GD with learning rate 0.001 and mean squared loss. Initialization (shown in Fig. 9(a)) was chosen to best illustrate the connection between the Gaussians’ motion and mutual information. The network converges to a solution where w1 < 0 and b1 is such that the elements in X1/4 cluster. The output of the first layer is then negated using w2 < 0 and the bias ensures that the elements in X0 are clustered without spreading out the elements in X1/4. Figs. 9(b) show the Gaussian motion at the output of the first layer and the resulting clustering. For the second layer (Fig. 9(c)), the clustered bundle X1/4 is gradually raised by growing b2, such that its elements successively split as they cross the origin; further tightening of the bundle is due to shrinking |w2|. Fig. 9(d) shows the mutual information of the first (blue) and second (red) layers. The merging of the elements in X1/4 after their initial divergence is clearly reflected in the mutual information. Likewise, the spreading of the bundle, and successive splitting and coalescing of the elements in X1/4 are visible in the spikes in the red mutual information curve. The figure also shows how the bounds on I ( X;T (k) ) precisely track its evolution. 1Throughout this work we interchanging use h(C) and h(pC) for the differential entropy of C ∼ pC .

heading: 9 EXPERIMENTAL DETAILS

heading: 9.1 SZT MODEL
text: In this section we provide additional experimental details and results for the SZT model discussed in Section 5 of the main paper.
To regularize the network weights, we followed (Cisse et al., 2017) and adopted their approach for enforcing an orthonormality constraint. Specifically, we first update the weights {W`}`∈[L] using the standard gradient descent step, and then perform a secondary update to set
W` ←W` − α ( W`W T ` − Id` ) W`,
where the regularization parameter α controls the strength of the orthonormality constraint. The value of α was was selected from the set {1.0× 10−5, 2.0× 10−5, 3.0× 10−5, 4.0× 10−5, 5.0× 10−5, 6.0× 10−5, 7.0× 10−5} and the optimal value was found to be equal to 5.0× 10−5 for both the tanh and ReLU.
In Fig. 10 we present additional experimental results that provide further insight into the clustering and compression phenomena for both tanh and ReLU nonlinearities. Fig. 10(a) shows what happens when the additive noise has a high variance. In this case, although saturation still occurs (see the histograms on top of Fig. 10(a)) and the Gaussians still cluster together (see the scatter plots on the right for the epoch 54 and epoch 8990), compression overall is very mild. The effect of increasing the noise parameter was explained in Section 4 of the main text (see, in particular, Fig. 4(d) therein). Comparing Fig. 10(a) to Fig. 5(a) of the main text, for which β = 0.005 was used and compression was observed, further highlights the effect of large β. Recall that smaller β values correspond to narrow Gaussians, while larger β values correspond to wider Gaussians. When β is small, even Gaussians that belong to the same cluster are distinguishable so long as they are not too close. When clusters tighten, the in-class movement brings these Gaussians closer together, effectively merging them, and causing a reduction in mutual information (compression). One the other hand, for large β, the in-class movement is blurred at the outset (before clusters tighten). Thus, the only effect on mutual information is the separation between the clusters: as these blobs move away from each other, mutual information rises.
Based on the above observation, we can conclude that while the two notions of “clustering Gaussians” and “compression/decrease in mutual information” are strongly related in the low-beta regime, once the noise becomes large, these phenomena decouple, i.e., the network may cluster inputs and neurons may saturate, but this will not be reflected in a decrease of mutual information.
Finally, we present results for ReLU activation without weight normalization (Fig. 10(b)) and with orthonormal weight regularization (Fig. 10(c)). We see that both these networks exhibit almost no compression. For Fig. 10(c), the lack of compression is attributed to regularization of the weight matrices, as explained in Section 5 of the main text. For Fig. 10(b), the reduction in compression can be explained by the fact that although ReLU forces saturation of the neurons at the origin (which promotes clustering), since the positive axes remain unconstrained, the Gaussians can move off towards infinity without bound. This is visible from the histograms in the top row of Fig. 10(b), where, for example, in layer 5 the neurons can take arbitrarily large positive values (note that the bin corresponding to the value 5 accumulates all the values from 5 to infinity). Therefore, the clustering at the origin and the potential drop in mutual information is counterbalanced by the spread of Gaussians along the positive axes and the potential increase of mutual information it causes. Eventually, this leads to the approximately constant profile of the mutual information plot in Fig. 10(b).
The behavior of the weight-normalized ReLU in Fig. 10(c) is similar to Fig. 10(b), although now the growth of the network weights is bounded and the saturation around origin is reduced. For example, for layers 4 and 5 we can see an upward trend in the mutual information, which is then flattened at the end of training. This occurs since more Gaussians are moving away from the origin, although their motion remains bounded (see the histograms on the top and the scatter plots on the right), thus decreasing the clustering density, leading to the rise in the mutual information profile. Once the Gaussians are prevented from moving any further along the positive axes, a slight compression occurs and the mutual information flattens.

heading: 9.2 SPIRAL MODEL
text: In this section we present results for another synthetic example. We generated data in the form of spiral as in Fig. 11. The network architecture was similar to SZT model, except that the size of each layer was set to 3.
Fig. 12 shows MI estimates I(X;T`) computed using SP estimator and the discrete entropy estimates H ( Bin(T`) ) for weight un-normalized Fig. 12 (a) and normalized models Fig. 12 (b) and using additive noise β = 0.005. Similar as in the main paper, the results in the figure illustrate a connection between clustering and compression.
Finally, in Fig. 13 we also show an estimate of H ( Bin(T`) ) for the case of deterministic DNN trained on spiral data. For the particular choice of the bin size, the result of the estimated entropy reveal a certain level of clustering granularity.

heading: 9.3 MNIST CNN
text: In this section, we describe in detail the architecture of the MNIST CNN models used in Sections 2 and 5 in the main paper.
The MNIST CNNs were trained using PyTorch (Paszke et al., 2017) version 0.3.0.post4. The CNNs use the following fairly standard architecture with two convolutional layers, two fully connected layers, and batch normalization.
1. 2-d convolutional layer with 1 input channel, 16 output channels, 5x5 kernels, and input padding of 2 pixels
2. Batch normalization 3. Tanh() activation function 4. Zero-mean additive Gaussian noise with variance β2 or dropout with a dropout probability
of 0.2 5. 2x2 max-pooling 6. 2-d convolutional layer with 16 input channels, 32 output channels, 5x5 kernels, and input
padding of 2 pixels 7. Batch normalization 8. Tanh() activation function 9. Zero-mean additive Gaussian noise with variance β2 or dropout with a dropout probability
of 0.2 10. 2x2 max-pooling 11. Fully connected layer with 1586 (32x7x7) inputs and 128 outputs 12. Batch normalization 13. Tanh() activation function
14. Zero-mean additive Gaussian noise with variance β2 or dropout with a dropout probability of 0.2
15. Fully connected layer with 128 inputs and 10 outputs
All convolutional and fully connected layers have weights and biases, and the weights are initialized using the default initialization, which draws weights from Unif[−1/√m, 1/√m], with m the fanin to a neuron in the layer. Training uses cross-entropy loss, and is performed using stochastic gradient descent with no momentum, 128 training epochs, and 32-sample minibatches. The initial learning rate is 5 × 10−3, and it is reduced following a geometric schedule such that the learning rate in the final epoch is 5× 10−4. To improve the test set performance of our models, we applied data augmentation to the training set by translating, rotating, and shear-transforming each training example each time it was selected. Translations in the x- and y-directions were drawn uniformly from {−2,−1, 0, 1, 2}, rotations were drawn from Unif(−10◦, 10◦), and shear transforms were drawn from Unif(−10◦, 10◦). To obtain more reliable performance results, we train eight different models and report the mean number of errors and standard deviation of the number of errors on the MNIST validation set. To ensure that the internal representations of different models are comparable, which is necessary for the use of the cosine similarity measure between internal representations, for each noise condition (deterministic, noisy with β = 0.05, noisy with β = 0.1, noisy with β = 0.2, noisy with β = 0.5, and dropout with p = 0.2), we use a common random seed (different for the eight replications, of course) so the models have the same initial weights and access the training data in the same order (use the same minibatches).
At test time, all models are fully deterministic: the additive noise blocks and dropout layers are replaced by identities. Thus, in the figures and text in the main paper, “Layer 1” is the output of step 5 (2x2 max-pooling), “Layer 2” is the output of step 10 (2x2 max-pooling), “Layer 3” is the output of step 13 (Tanh() activation function), and “Layer 4” is the output of step 15 (fully connected layer with 10 outputs).

heading: 10 SAMPLE PROPAGATION ESTIMATOR - THEORETIC GUARANTEES
text: Both conditional and unconditional entropy estimators reduce to the problem of estimating h(pS ∗ ϕ) using i.i.d. samples Sn , (Si)i∈[n] from S ∼ pS while knowing ϕ. In this section we state performance guarantees for the SP estimator. These results are excerpted from our work (Anonymized, 2018), where this estimation problem is thoroughly studied. The interested reader is referred to (Anonymized, 2018) for proofs of the subsequently stated results.
10.0.1 PRELIMINARY DEFINITIONS
Let Fd be the set of distributions P with supp(P ) ⊆ [−1, 1]d.2 The minimax absolute-error risk over Fd is
R?d(n, β) , inf ĥ sup P∈Fd
ESn ∣∣∣h(P ∗ ϕ)− ĥ(Sn, β) ∣∣∣ , (9)
where ĥ is an estimator of h(P ∗ ϕ) based on the empirical data Sn = (S1, . . . , Sn) of i.i.d. samples from P and the noise parameter β2. In (9), by P ∗ ϕ we mean either: (i) (P ∗ ϕ)(x) =∫ Rd p(u)ϕ(x − u)du = (p ∗ ϕ)(x), when P is continuous with density p; or (ii) (P ∗ ϕ)(x) =∑ u: p(u)>0 p(u)ϕ(x− u), if P is discrete with PMF p. This convolved distribution can be defined generally in a way that the two instances above as special cases using measure-theoretic concepts (see (Anonymized, 2018)). Regardless of the nature of P , however, we stress that P ∗ ϕ is always a continuous distribution since it corresponds to the random variable S + Z, where Z is an isotropic Gaussian. The sample complexity n?d(η, β) is defined as the smallest number of samples (up to constant factors) for which estimation within an additive gap η is possible. Namely,
n?d(η, β) , min { n ∣∣R?d(n, β) ≤ η } . (10)
We also consider the class of distributions with subgaussian marginals; these will correspond to mutual information estimation over noisy DNNs with ReLU nonlinearities. A subgaussian random variable is defined as follows.
2Any support included in a compact subset of Rd would do. We focus on the case of supp(P ) ⊆ [−1, 1]d due to its correspondence to a noisy DNN with tanh nonlinearities.
Definition 1 (Subgaussian Random Variable) A random variable X is subgaussian if it satisfies either of the following equivalent properties
1. Tail condition: ∃K1 > 0, P ( |X| > t ) ≤ exp ( 1− t2
K21
) , for all t ≥ 0;
2. Moment condition: ∃K2 > 0, (E|X|p) 1 p ≤ K2√p, for all p ≥ 1; 3. Super-exponential moment: ∃K3 > 0, E exp ( X2
K23
) ≤ e,
where Ki, for i = 1, 2, 3, differ by at most an absolute constant. Furthermore, the subgaussian norm ‖X‖ψ2 of a subgaussian random variable X is defined as the smallest K2 in property 2, i.e., ‖X‖ψ2 , supp≥1 p− 1 2 (E|X|p) 1p .
Now, let F (SG)d,K be the class of distributions P of a d-dimensional random variable S =( S(1), . . . , S(d) ) whose coordinates are subgaussian with
∥∥S(i) ∥∥ ψ2 ≤ K, for all i ∈ [d]. The
risk and the sample complexity defined with respect to the nonparametric class F (SG)d,K are denoted by R?d,K(n, β) and n?d,K(δ, β), respectively. Clearly, for any S ∼ P with supp(P ) ⊆ [−1, 1]d we have
∥∥S(i) ∥∥ ψ2 ≤ 1, for all i ∈ [d], and therefore Fd ⊆ F (SG)d,1 . As a consequence we obtain
R?d(n, β) ≤ R?d,K(n, β) and n?d(δ, β) ≤ n?d,K(δ, β) for all n ∈ N and δ > 0, whenever K ≥ 1. As explained in the following remark, the considered subgaussianity requirement is naturally satisfied by our noisy DNN framework.
Remark 1 (Generality of Subgaussian Class F (SG)d,K and Noisy ReLU DNNs) The class F (SG) d,K accounts for distributions induced by noisy DNNs with various nonlinearities. Specifically, it captures the following important cases:
1. Distributions with bounded support (corresponding to noisy DNN with bounded activisions).
2. Discrete distributions over a finite set, which is a special case of bounded support.
3. Distributions of the random variable S` = f`(T`−1) in a noisy ReLU DNN, so long as the input X to the network is itself subgaussian. To see this recall that linear combinations of independent subgaussian random variables is also subgaussian. Furthermore, for any (scalar) random variable A, we have that ∣∣ReLU(A) ∣∣ = ∣∣max{0, A} ∣∣ ≤ |A|, almost surely.
Now, since each layer in a noisy ReLU DNN is nothing but a coordinate-wise ReLU applied to a linear transformation of the previous layer plus a Gaussian noise, one may upper bound( E ∣∣S(i)
∣∣p) 1p , for a d`-dimensional hidden layer S` and i ∈ [d`], as in Item (2) of Definition 1, provided that the input X is coordinate-wise subgaussian. The constant K2 will depend on the network’s weights and biases, the depth of the hidden layer, the subgaussian norm of the input ‖X‖ψ2 and the noise variance. This input subgaussianity assumption is, in particular, satisfied by the distribution of X considered herein, i.e., by X ∼ Unif(X ).

heading: 10.1 SAMPLE COMPLEXITY IS EXPONENTIAL IN DIMENSION
text: We start with two converse claims establishing that the sample complexity is exponential in d. The first claim states that there exists a class of distributions P , for which the estimation of h(P ∗ ϕ) cannot be done with fewer than exponentially many samples in d, when d is sufficiently large.
Theorem 2 (Asymptotic (in d) Exponential Sample-Complexity) For any β > 0 there exist γ(β) > 0 (monotonically decreasing in β) and a class of distributions in Fd, such that for any d sufficiently large and η > 0 sufficiently small, the sample complexity of estimating h(p ∗ ϕ) within an additive gap η > 0 over that class grows as Ω
( 2γ(β)d( η+δ
(1) β,d
) d
) , where limd→∞ δ (1) β,d = 0, for all
β > 0. In particular, n?d(η, β) = Ω (
2γ(β)d( η+δ
(1) β,d
) d
) in this regime.
The fact that the exponent γ(β) is monotonically decreasing in β suggests that larger values of β are favorable for estimation. Theorem 2 shows that an exponential sample complexity is inevitable when d is large. As a complementary result, the next theorem gives a sample complexity lower bound valid in any dimension but only for small enough noise variances. Nonetheless, the result is valid for orders of β considered in this work.
Theorem 3 (Asymptotic (in β) Exponential Sample-Complexity) Fix d ≥ 1. There exists a class of distributions in Fd such that for any β, η > 0 sufficiently small, the sample complexity of estimating h(S + Z) within an additive gap η > 0 over that class grows as Ω ( 2d(
η+δ (2) β,d
) d
) , where
limβ→0 δ (2) β,d = 0, for all d ≥ 1. In particular, n?d(η, β) = Ω
( 2d(
η+δ (2) β,d
) d
) in this regime.
Remark 2 We state Theorem 3 asymptotically in β for the sake of simplicity, but for any d it is possible to follow the constants through the proof to determine a value c such that Theorem 3 holds for all β < c. For example for d = 1, a careful analysis gives that Theorem 3 holds for all β < 0.08, which is satisfied by most of the experiments run in this paper. This threshold on β changes very slowly with increasing d due to the rapid decay of the PDF of the normal distribution.

heading: 10.2 MINIMAX RISK CONVERGENCE RATE OF THE SAMPLE PROPAGATION ESTIMATOR
text: We next focus on analyzing the performance of the SP estimator. For any fixed Sn = sn, denote the empirical PMF associated with sn by p̂sn . The SP estimator of h(T ) = h(pS ∗ ϕ) is
ĥSP(s n) , h(p̂sn ∗ ϕ). (11)
The estimator ĥSP(sn) also depends on β, but we omit this from our notation. The following theorem shows that the expected absolute error of ĥSP decays like O ( Polylog(n)√
n
) for all dimensions d. We
provide explicit constants (in terms of β and d), which present an exponential dependence on the dimension, in accordance to the results of Theorems 2 and 3.
Theorem 4 (SP Estimator Absolute-Error Risk for Bounded Support) Fix β > 0, d ≥ 1 and any > 0. The absolute-error risk of the SP estimator (11) over the class Fd, for all n sufficiently large, is bounded as
sup P∈Fd
ESn ∣∣∣h(P ∗ ϕ)− ĥSP(Sn) ∣∣∣
≤ 1 2(4πβ2) d 4 log
  n ( 2 + 2β √ (2 + ) log n )d
(πβ2) d 2
  ( 2 + 2β √ (2 + ) log n ) d
2 1√ n
+ ( c2β,d + 2cβ,dd(1 + β 2)
β2 +
8d(d+ 2β4 + dβ4)
β4
) 2
n , (12)
where cβ,d , d2 log(2πβ2) + d β2 . In particular,
sup P∈Fd
ESn ∣∣∣h(P ∗ ϕ)− ĥSP(Sn) ∣∣∣ = Oβ,d ( Polylog(n)√
n
) , (13)
and the right-hand sides (RHSs) of (12) and (13) are, respectively, explicit and implicit upper bounds on the minimax absolute-error riskR?d(n, β).
Remark 3 (Comparison to General-Purpose Estimators) Note that one could always sample ϕ and add up these noise samples to Sn to obtain a sample set from P ∗ ϕ. These samples can be used to get a proxy of h(P ∗ ϕ) via a kNN- or a KDE-based differential entropy estimator. However, P ∗ ϕ violated the boundedness away from zero assumption that most of the convergence rate results in the literature rely on (Levit, 1978; Hall, 1984; Joe, 1989; Hall & Morton, 1993; Tsybakov & der Meulen, 1996; Haje & Golubev, 2009; K et al., 2012; Singh & Póczos, 2016; Kandasamy
et al., 2015). The only result we are aware of that analyses a differential entropy estimator (namely, the kNN-based estimator from (A. Kraskov & Grassberger, 2004)) without assuming the density is bounded from below (Jiao et al., 2017) relies on the density being supported inside [0, 1]d, satisfying periodic boundary conditions and having a Hölder smoothness parameter s ∈ (0, 2]. The convolved density P ∗ ϕ satisfies neither of these three conditions. Furthermore, because the SP estimator is constructed to exploit the particular structure of our estimation setup it achieves a fast convergence rate of ( Polylog(n)√
n
) . The risk associated with unstructured differential entropy estimators typically
converges as the slower O ( n− αs βs+d ) . This highlights the advantage of ad-hoc estimation as opposed
to general-purpose estimation.
Theorem 1 provides convergence rates when estimating differential entropy (or mutual information) over DNNs with bounded activation functions, such as tanh or sigmoid. To account for networks with unbounded nonlinearities, such as ReLU networks, the following theorem gives a more general result of estimation over the nonparametric class F (SG)d,K of d-dimensional distributions with subgaussian marginals.
Theorem 5 (SP Estimator Absolute-Error Risk for Subgaussians) Fix β > 0 and d ≥ 1. The absolute-error risk of the SP estimator (11) over the class F (SG)d,K , for all n sufficiently large, is bounded as
sup P∈F(SG)d,K
ESn ∣∣∣h(P ∗ ϕ)− ĥSP(Sn) ∣∣∣ ≤ log ( √ n ( 8(K + β)2 (e− 1)πβ2 ) d 4 )( 2(K + β)2 (e− 1)πβ2 log n ) d 4 1√ n
+ ( ( c′β,d + 2dK 2 )2 + 2 ( c′β,d + 2dK 2 ) ( β2d+ 2dK2 )
β2 +
8 ( 16d2K4 + β4d(2 + d) )
β4
) ed
n ,
(14)
where c′β,d , d2 log(2πβ2). In particular,
sup P∈F(SG)d,K
ESn ∣∣∣h(P ∗ ϕ)− ĥSP(Sn) ∣∣∣ = Oβ,d ( Polylog(n)√
n
) , (15)
and the RHSs of (14) and (15) are, respectively, explicit and implicit upper bounds on the minimax absolute-error riskR?d,K(n, β).
As mentioned in Remark 1, the class F (SG)d,K is rather general, and, in particular, includes Fd whenever K ≥ 1. This means that Theorem 5 also provides an upper bound on the minimax risk under the setup of Theorem 1. Nonetheless, we chose to separately state Theorem 1 since the derivation under the bounded support assumption enables extracting slightly better constants (which is important for our applications - see Section 5). We do highlight, however, that the expressions from (12) and (14) with K = 1 not only have the same convergence rates, but their constants are also very close.
Remark 4 (Near Minimax Rate-Optimality) A convergence rate faster than 1√ n cannot be attained for parameter estimation under the absolute-error loss. This follows from, e.g., Proposition 1 of (Chen, 1997), which establishes this convergence rate as a lower bound for the parametric estimation problem given n i.i.d. samples. Consequently, the convergence rate of Oσ,d ( Polylog(n)√
n
)
established in Theorems 1 and 5 for the SP estimator is near minimax rate-optimal (i.e., up to logarithmic factors).
Remark 5 (Mutual Information Estimation) Denoting the upper bound on the estimation error from Theorem 1 or 5 by ∆n(β, d), we see that the error of the mutual information estimator from (2) is bounded as by 2∆n(β, d), which vanishes as n→∞.

heading: 10.2.1 SAMPLE PROPAGATION ESTIMATOR BIAS
text: The results of the previous subsection are of minimax flavor. That is, they state worst-case convergence rates of the SP estimation over a certain nonparametric class of distributions. In practice, the true distribution may very well not be one that attains these worst-case rates, and convergence may be faster. However, while variance of ĥSP(Sn) can be empirically evaluated using bootstrapping, there is no empirical test for the bias. Even if multiple estimations of h(P ∗ ϕ) via ĥSP(Sn) consistently produce similar values, this does not necessarily suggest that these values are close to the true h(P ∗ ϕ). To have a guideline to the least number of samples needed to avoid biased estimation, we present the following lower bound on supP∈Fd ESn ∣∣∣h(P ∗ ϕ)− ĥSP(Sn) ∣∣∣.
Theorem 6 (SP Estimator Bias Lower Bound) Fix d ≥ 1 and β > 0, and let ∈( 1− ( 1− 2Q ( 1 2β ))d , 1 ] , where Q is the Q-function.3 Set k? , ⌊ 1
βQ−1 (
1 2
( 1−(1− ) 1d
)) ⌋ , where
Q−1 is the inverse of the Q-function. By the choice of , clearly k? ≥ 2, and the bias of the SP estimator over the class Fd is bounded as
∣∣∣∣ sup P∈Fd h(P ∗ ϕ)− ESn ĥSP(Sn) ∣∣∣∣ ≥ log ( k d(1− ) ? n ) −Hb( ). (16)
Consequently, the bias cannot be less than a given δ > 0 so long as n ≤ kd(1− )? · e−(δ+Hb( )).
SinceHb( ) shrinks with , for sufficiently small values the lower bound from (16) essentially shows that the SP estimator will not have negligible bias unless n > kd(1− )? is satisfied. The condition
> 1 − ( 1− 2Q (
1 2β
))d is non-restrictive in any relevant regime of β and d. For instance, for
typical β values we work with - around 0.1 - this lower bound is at most 0.0057 for all dimensions up to at least d = 104. Setting, e.g., = 0.01 (for which Hb(0.01) ≈ 0.056), the corresponding k? equals 3 for d ≤ 11 and 2 for 12 ≤ d ≤ 104. Thus, with these parameters, the number of estimation samples n should be at least 20.99d, for any conceivably relevant dimension, in order to have negligible bias.

heading: 10.3 COMPUTING THE SAMPLE PROPAGATION ESTIMATOR
text: Evaluating the mutual information estimator from (2) requires computing the differential entropy of a Gaussian mixture. Although it cannot be computed in closed form, this section presents a method for approximate computation via MC integration (Robert, 2004). To simplify the presentation, we present the method for an arbitrary Gaussian mixture without referring to the notation of the estimation setup. Let g(t) , 1n ∑ i∈[n] ϕ(t− µi) be a d-dimensional, n-mode Gaussian mixture, with {µi}i∈[n] ⊂ Rd and ϕ as the PDF of N (0, β2Id). Let C ∼ Unif{µi}i∈[n] be independent of Z ∼ ϕ and note that V , C + Z ∼ g. We use Monte Carlo (MC) integration (Robert, 2004) to compute the h(g). First note that
h(g) = −E log g(V ) = − 1 n
∑ i∈[n] E [ log g(µi + Z) ∣∣∣C = µi ] = − 1 n ∑ i∈[n] E log g(µi + Z), (17)
where the last step follows by the independence of Z and C. Let { Z
(i) j } i∈[n] j∈[nMC] be n × nMC i.i.d.
samples from ϕ. For each i ∈ [n], we estimate the i-th summand on the RHS of (17) by
Î (i) MC ,
1
nMC
∑
j∈[nMC] log g
( µi + Z (i) j ) , (18a)
3The Q-function is defined as Q(x) , 1√ 2π ∫∞ x e− t2 2 dt.
which produces
ĥMC , 1
n
∑ i∈[n] Î (i) MC (18b)
as our estimate of h(g). Define the mean squared error (MSE) of ĥMC as
MSE ( ĥMC ) , E [( ĥMC − h(g) )2] . (19)
We have the following bounds on the MSE for tanh and ReLU networks.
Theorem 7 (MSE Bounds for MC Estimator)
(i) Assume C ∈ [−1, 1]d almost surely (i.e., tanh network), then
MSE ( ĥMC ) ≤ 1 n · nMC 2d(2 + β2) β2 . (20)
(ii) Assume MC , E‖C‖22 <∞ (e.g., ReLU network with bounded 2nd moments), then
MSE ( ĥMC ) ≤ 1 n · nMC
9dβ2 + 8(2 + β √ d)MC + 3(11β √ d+ 1) √ MC
β2 . (21)
The bounds on the MSE scale only linearly with the dimension d, making σ2 in the denominator often the dominating factor experimentally.
Remark 6 (Comparison to Generic Entropy Estimation) We briefly present empirical results illustrating the convergence of the SP estimator and comparing it to two current state-of-the-art methods: the KDE-based estimator of (Kandasamy et al., 2015) and the kNN-based estimator often known as the Kozachenko–Leonenko (KL) nearest neighbor estimator (Kozachenko & Leonenko, 1987; Jiao et al., 2017). In this example, the distribution P of S is set to be a mixture of Gaussians truncated to have support in [−1, 1]d. Before truncation, the mixture consists of 2d Gaussian components with means at the 2d corners of [−1, 1]d. The entropy of P ∗ φ, i.e., h(S + Z), where Z ∼ N (0, σ2Id), is estimated and various values of σ are examined. Fig. 14 shows the estimation error results as a function of the number of samples n for dimensions d = 5 and d = 10. The kernel width for the KDE estimate was chosen via cross-validation, varying with both d and n; the kNN estimator and ĥSP(Sn) require no tuning parameters. We found that the KDE estimate is highly sensitive to the choice of kernel width, the curves shown correspond to optimized values and are highly unstable to any change in kernel width. Note that both the kNN and the KDE estimators converge slowly, at a rate that degrades with increased d. This rate is worse than that of ĥSP, which also lower bounds the true entropy (as according to our theory - see (Anonymized, 2018, Equation (60))).

Review summaries:
This paper provides a principled way to examine the compression phrase, i.e, I(X;T) in deep neural networks. To achieve this, the authors provides an theoretical sounding entropy estimator to estimate mutual information.  Empirically, the paper did observe this compression phrase across both synthetic and real-world data and relates this compression behavior with geometric clustering. 

This paper studied the information bottleneck principle for deep learning. In the paper by (Schwatz-Ziv & Tishby 17'), it is empirically shown that the mutual information I(X;T) between input X and internal layers T decreases, which is called a compression phase. In this paper, the author found that the compression phase is not always happening and the shape of the curve of I(X;T) highly depends on the "bining size" which is used for estimating mutual information by (Schwatz-Ziv & Tishby 17'). Then the authors proposed to use a noisy DNN to make sure the map X->T is stochastic, then proposed a guaranteed mutual information estimator. Then some empirical results are shown.