CAVEATS FOR INFORMATION BOTTLENECK IN DETERMINISTIC SCENARIOS
Year: 2019

Abstract:
Information bottleneck (IB) is a method for extracting information from one random variable X that is relevant for predicting another random variable Y . To do so, IB identifies an intermediate “bottleneck” variable T that has low mutual information I(X;T ) and high mutual information I(Y ;T ). The IB curve characterizes the set of bottleneck variables that achieve maximal I(Y ;T ) for a given I(X;T ), and is typically explored by maximizing the IB Lagrangian, I(Y ;T )−βI(X;T ). In some cases, Y is a deterministic function of X , including many classification problems in supervised learning where the output class Y is a deterministic function of the input X . We demonstrate three caveats when using IB in any situation where Y is a deterministic function of X: (1) the IB curve cannot be recovered by maximizing the IB Lagrangian for different values of β; (2) there are “uninteresting” trivial solutions at all points of the IB curve; and (3) for multi-layer classifiers that achieve low prediction error, different layers cannot exhibit a strict trade-off between compression and prediction, contrary to a recent proposal. We also show that when Y is a small perturbation away from being a deterministic function of X , these three caveats arise in an approximate way. To address problem (1), we propose a functional that, unlike the IB Lagrangian, can recover the IB curve in all cases. We demonstrate the three caveats on the MNIST dataset.

heading: 1 INTRODUCTION
text: The information bottleneck (IB) method (Tishby et al., 1999) provides a principled way to extract information that is present in one variable that is relevant for predicting another variable. Given two random variables X and Y , IB posits a “bottleneck” variable T that obeys the Markov condition Y − X − T . By the data processing inequality (DPI) (Cover & Thomas, 2012), this Markov condition implies that I(X;T ) ≥ I(Y ;T ), meaning that the bottleneck variable cannot contain more information about Y than it does about X . In fact, any particular choice of the bottleneck variable T can be quantified by two terms: the mutual information I(X;T ), which reflects how much T compresses X , and the mutual information I(Y ;T ), which reflects how well T predicts Y . In IB, bottleneck variables are chosen to maximize prediction given a constraint on compression (Witsenhausen & Wyner, 1975; Ahlswede & Körner, 1975; Gilad-Bachrach et al., 2003),
F (r) := max T∈∆
I(Y ;T ) s.t. I(X;T ) ≤ r , (1)
where ∆ is the set of random variables T obeying the Markov condition Y − X − T . The values of F (r) for different r specify the IB curve. In order to explore the IB curve, one must find optimal T for different values of r. It is known that the IB curve is concave in r but may not be strictly concave. This seemingly minor issue of non-strict concavity will play a central role in our analysis.
In practice, the IB curve is almost always explored not via the constrained optimization problem of Eq. (1), but rather by maximizing the so-called IB Lagrangian,
LβIB(T ) := I(Y ;T )− βI(X;T ) , (2) ∗Dept of Aeronautics & Astronautics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
where β ∈ [0, 1] is a parameter that controls the trade-off between compression and prediction. The advantage of optimizing LβIB is that it avoids the non-linear constraint in Eq. (1)1. Several recent papers have drawn connections between IB and supervised learning, in particular classification using neural networks. In this context, X represents input vectors, Y represents the output classes, and T represents intermediate representations used by the network architecture, such as the activity of hidden layer(s) (Tishby & Zaslavsky, 2015). Some of these papers modify neural network training algorithms so as to optimize the IB Lagrangian (Alemi et al., 2016; Chalk et al., 2016; Kolchinsky et al., 2017), thereby permitting the use of IB with high-dimensional, continuousvalued random variables. Some papers have also suggested that by controlling the amount of compression, one can tune desired characteristics of trained models such as generalization error (Shamir et al., 2010; Tishby & Zaslavsky, 2015; Vera et al., 2018), robustness to adversarial inputs (Alemi et al., 2016), and detection of out-of-distribution data (Alemi et al., 2018). Other research (ShwartzZiv & Tishby, 2017) has suggested — somewhat controversially (Saxe et al., 2018) — that stochastic gradient descent (SGD) training dynamics may implicitly favor hidden layer mappings that balances compression and prediction, with earlier hidden layers favoring prediction over compression and latter hidden layers favoring compression over prediction. Finally, there is the general notion that intermediate representations that are optimal in the IB sense correspond to “interesting” or “useful” compressions of input vectors (Amjad & Geiger, 2018).
There are also numerous application domains of IB beyond supervised learning, including clustering (Slonim & Tishby, 2000), coding theory and quantization (Cardinal, 2003; Zeitler et al., 2008; Courtade & Wesel, 2011), and cognitive science (Zaslavsky et al., 2018). In most of these applications, it is of central interest to explore solutions at different points on the IB curve, for example to control the number of detected clusters, or to adapt codes to available channel capacity.
In some scenarios, Y may be a deterministic function of X , i.e., Y = f(X) for some single-valued function f . For example, in many classification problems, it is assumed that any given input belongs to a single class, which implies a deterministic relationship between X and Y . In this paper, we demonstrate three caveats for IB that appear whenever Y is a deterministic function of X: 1. There is no one-to-one mapping between different points on the IB curve and maximizers of the
IB LagrangianLβIB for different β, thus the IB curve cannot be explored by maximizingL β IB while varying β. This occurs because when Y = f(X), the IB curve has a piecewise linear shape and is therefore not strictly concave. The dependence of the IB Lagrangian on the strict concavity of F (r) has been previously noted (Gilad-Bachrach et al., 2003; Shwartz-Ziv & Tishby, 2017), but the implications and pervasiveness of this problem (e.g., in many classification scenarios) has not been fully recognized. We analyze this issue and propose a solution in the form of an alternative objective function, which can be used to explore the IB curve even when Y = f(X).
2. All points on the IB curve contain uninteresting trivial solutions (in particular, stochastic mixtures of two very simple solutions). This suggests that IB-optimality is not sufficient for an intermediate representation to be an interesting or useful compression of input data.
3. For a neural network with several hidden layers that achieves a low probability of error, the hidden layers cannot display a strict trade-off between compression and prediction (in particular, different layers can only differ in the amount of compression, not prediction).
In Appendix B, we show that the above three caveats also apply to the recently proposed deterministic IB variant of IB (Strouse & Schwab, 2017), in which the compression term is quantified using the entropy H(T ) rather than the mutual information I(X;T ). In that Appendix, we propose an alternative objective function that can be used to resolve the first problem for dIB.
We also show, in Appendix C, that our results apply when Y is not exactly a deterministic function of X , but -close to one. In this case: (1) it is hard to explore the IB curve by optimizing the IB Lagrangian, because all optimizers will fall within O(− log ) of a single “corner” point on the information plane; (2) along all points on the IB curve, there are “uninteresting” trivial solutions that are no more thanO(− log ) away from being optimal; (3) different layers of a neural networks can trade-off at most O(− log ) amount of prediction. A recent paper (Amjad & Geiger, 2018) also discusses several difficulties in using IB to analyze intermediate representations in supervised learning. That paper does not consider the particular
1Note that optimizing LβIB is still a constrained problem in that p(t|x) must be a valid conditional probability. However, this constraint is usually easier to handle, e.g., by using an appropriate parameterization.
issues that arise when Y is a deterministic function of X , and its arguments are complementary to ours. Shwartz-Ziv & Tishby (2017)[Sec. 2.4] discuss another caveat for IB in deterministic settings, concerning the relationship between sufficient statistics and the complexity of the inputoutput mapping, which is orthogonal to the three caveats analyzed here. Finally, Saxe et al. (2018) and Amjad & Geiger (2018) observed that when T is continuous-valued and a deterministic function of a continuous-valued X , I(X;T ) can be unbounded, making the application of the IB framework problematic. We emphasize that the caveats discussed in this paper are unrelated to that problem.
Note that our results are based on analytically-provable properties of the IB curve, i.e., global optima of Eq. (1), and do not concern practical issues of optimization (which may be important in realworld scenarios). Our theoretical results are also independent of the practical issue of estimating MI between neural network layers, an active area of recent research (Belghazi et al., 2018; Goldfeld et al., 2018; Dai et al., 2018; Gabrié et al., 2018), though our empirical experiments in Section 7 rely on the estimator proposed in (Kolchinsky & Tracey, 2017; Kolchinsky et al., 2017). Finally, our results are also independent of issues related to the relationship between IB, finite data sampling, and generalization error (Shamir et al., 2010; Tishby & Zaslavsky, 2015; Vera et al., 2018).
In the next section, we review some of the connections between supervised learning and IB. In Section 3, we show that when Y = f(X), the IB curve has a piecewise linear (not strictly concave) shape. In Sections 4, 5 and 6, we discuss the three caveats mentioned above. In Section 7, we demonstrate the caveats using a neural-network implementation of IB on the MNIST dataset.

heading: 2 SUPERVISED CLASSIFICATION AND IB
text: In supervised learning, one is given a training dataset {xi, yi}i=1..N of inputs and outputs. In this case, the random variablesX and Y refer to the inputs and outputs respectively, and p̄(x, y) indicates their joint empirical distribution in the training data. It is usually assumed that the x’s and y’s are sampled i.i.d. from some “true” distributionw(y|x)w(x). The high-level goal of supervised learning is to use the dataset to select a particular conditional distribution qθ(ŷ|x) of outputs given inputs parameterized by θ that is a good approximation of w(y|x). For clarity, we use Ŷ (and ŷ) to indicate a random variable (and its outcome) corresponding to the predicted outputs. We use X to indicate the set of outcomes of X , and Y to indicate the set of outcomes of Y and Ŷ . Supervised learning is called classification when Y takes a finite set of values, and regression when Y is continuousvalued. Here we focus on classification, where the set of possible output values can be written as Y = {0, 1, . . . ,m}. We expect our results to also apply in some regression scenarios (with some care regarding evaluating MI measures, see Footnote 2), but leave this for future work.
In practice, many supervised learning architectures use some kind of intermediate representation to make predictions about the output, such as hidden layers in neural networks. In this case, the random variable T represents the activity of some particular hidden layer in a neural network. Let T be a (possibly stochastic) function of the inputs, as determined by some parameterized conditional distribution qθ(t|x), so that T obeys the Markov condition Y −X − T . The mapping from inputs to hidden layer activity can be either deterministic, as traditionally done in neural networks, or stochastic, as used in some architectures (Alemi et al., 2016; Kolchinsky et al., 2017; Achille & Soatto, 2018)2. The mapping from hidden layer activity to predicted outputs is represented by the parameterized conditional distribution qθ(ŷ|t), so the full Markov condition between true outputs, inputs, hidden layer activity, and predicted outputs is Y −X − T − Ŷ . The overall mapping from inputs to predicted outputs implemented by a neural network with a hidden layer can be written as
qθ(ŷ|x) := ∫ qθ(ŷ|t)qθ(t|x)dt . (3)
Note that T does not have to represent a particular hidden layer, but could instead represent the activity of the neurons in a set of contiguous hidden layers, or in fact any arbitrary set of neurons that separate inputs from predicted outputs (in the sense of conditional independence, so that Eq. (3) holds). More generally yet, T could also represent some intermediate representation in a non-neuralnetwork supervised learning architecture, again as long as Eq. (3) holds.
2If T is continuous-valued and a deterministic function of a continuous-valuedX , then one should consider noisy or quantized mappings from inputs to hidden layers, such that I(X;T ) is finite.
For classification problems, training often involves selecting θ to minimize cross-entropy loss, sometimes while stochastically sampling the activity of hidden layers. When T is the last hidden layer, or when the mapping from T to the last hidden layer is deterministic, cross-entropy loss can be written
LCE(θ) = − 1
N ∑ i ∫ qθ(t|xi) log qθ(ŷi|t) dt = Ep̄θ(Y,T ) [ − log qθ(Ŷ |T ) ] , (4)
where E indicates expectation, p̄θ(y, t) := 1N ∑ i δ(y, yi)qθ(t|xi) is the empirical distribution of outputs and hidden layer activity, and δ is the Kronecker delta. Eq. (4) can also be written as LCE(θ) = H(p̄θ(Y |T )) +DKL(p̄θ(Y |T )‖qθ(Ŷ |T )) (5) whereH is (conditional) Shannon entropy, DKL is Kullback-Leibler (KL) divergence, and p̄θ(y|t) is defined via the definition of p̄θ(y, t) above. Since KL is non-negative, LCE(θ) is an upper bound on the conditional entropy H(p̄θ(Y |T )). During training, one can decrease LCE either by decreasing the conditional entropy H(p̄θ(Y |T )), or decreasing the KL term by changing qθ(Ŷ |T ) to better approximate p̄θ(Y |T ). Minimizing LCE thus minimizes an upper bound on H(p̄θ(Y |T )), which is equivalent to maximizing a lower bound on Ip̄θ (Y ;T ) = H(p̄(Y ))−H(p̄θ(Y |T )) (since H(p̄(Y )) is a constant that doesn’t depend on θ).
We can now make explicit the relationship between supervised learning and IB. In IB, one is given a joint distribution p(x, y), and then seeks a bottleneck variable T that obeys the Markov condition Y − X − T and minimizes I(X;T ) while maximizing I(Y ;T ). In supervised learning, one is given an empirical distribution p̄(x, y) and defines an intermediate representation T that obeys the Markov condition Y −X−T ; during training, cross-entropy loss is minimized, which is equivalent to maximizing a lower bound on I(Y ;T ) (given assumptions of Eq. (4) hold). To complete the analogy, one might choose θ so as to also minimize I(X;T ), i.e., choose hidden layer mappings that provide compressed representations of input data (Alemi et al., 2016; Chalk et al., 2016; Kolchinsky et al., 2017; Achille & Soatto, 2018). In fact, we use such an approach in our experiments on the MNIST dataset in Section 7.
In many supervised classification problems, there is only one correct class label associated with each possible input. Formally, this means that given the empirical training dataset distribution p̄(y|x), one can write Y = f(X) for some single-valued function f . This relationship between X and Y may arise because it holds under the “true” distribution w(y|x) from which the training dataset is sampled, or simply because each input vector x occurs at most once in the training data (as happens in most real-world classification training datasets). Note that we make no assumptions about the relationship between X and Ŷ under qθ(ŷ|x), the distribution of predicted outputs given inputs implemented by the supervised learning architecture, and our analysis holds even if qθ(ŷ|x) is nondeterministic (e.g., the softmax function).
It is important to note that not all classification problems are deterministic. The map from X to Y may be intrinsically noisy or non-deterministic (e.g., if human labelers cannot agree on a class for some x), or noise may be intentionally added as a regularization technique (e.g., as done in the label smoothing method (Szegedy et al., 2016)). Moreover, one of the pioneering papers on the relationship between IB and supervised learning (Shwartz-Ziv & Tishby, 2017) analyzed an artificially-constructed classification problem in which p(y|x) was explicitly defined to be noisy (see their Eq. 10). However, we believe that many if not most real-world classification problems do in fact exhibit a deterministic relation between X and Y . In addition, as we show in Appendix C, even if the relationship between X and Y is not perfectly deterministic but close to being so, then the three caveats discussed in this paper still apply in an approximate sense.

heading: 3 THE IB CURVE WHEN Y IS A DETERMINISTIC FUNCTION OF X
text: Consider the random variables X,Y where Y is discrete-valued and a deterministic function of X , i.e., Y = f(X). I(Y ;T ) can be upper bounded as I(Y ;T ) ≤ I(X;T ) by the DPI, and I(Y ;T ) ≤ H(Y ) by basic properties of MI (Cover & Thomas, 2012). To visualize these bounds, as well as other results of our analysis, we use so-called “information plane” diagrams (Tishby et al., 1999). The information plane represents various possible bottleneck variables in terms of their compression (I(X;T ), horizontal axis) and prediction (I(Y ;T ), vertical axis). The two bounds mentioned above are plotted on an information plane in Fig. 1. In this section, we show that when Y = f(X), the IB curve saturates both bounds, and is not strictly concave but rather piece-wise linear.
To show that the IB curve saturates the DPI bound I(Y ;T ) ≤ I(X;T ) for I(X;T ) ∈ [0, H(Y )], let Bα be a Bernoulli random variable that is equal to 1 with probability α. Then, define a manifold of bottleneck variables Tα parameterized by α ∈ [0, 1],
Tα := Bα · Y = Bα · f(X) . (6)
Thus, Tα is equal to Y with probability α, and equal to 0 with probability 1 − α. From Eq. (6), it is clear that Tα can be written either as a (stochastic) function of X or a (stochastic) function of Y , thus both Markov conditions Y −X − Tα and X − Y − Tα hold. Applying the DPI to both Markov conditions implies that I(X;Tα) = I(Y ;Tα) for any Tα. Note that for α = 1, Tα = Y and thus I(Y ;Tα) = H(Y ), while for α = 0, Tα = 0
and thus I(Y ;Tα) = 0. Since MI is continuous in probabilities, the manifold of bottleneck variables Tα sweeps the full range of values 〈I(X;Tα), I(Y ;Tα)〉 = 〈0, 0〉 to 〈I(X;Tα), I(Y ;Tα)〉 = 〈H(Y ), H(Y )〉 as α ranges from 0 to 1, while obeying I(X;Tα) = I(Y ;Tα). Thus, the manifold of Tα bottleneck variables achieves the DPI bound over I(X;T ) ∈ [0, H(Y )]. Given its definition in Eq. (1), the IB curve is monotonically increasing. Since 〈H(Y ), H(Y )〉 is on the IB curve (e.g., Tα for α = 1), it must be that I(Y ;T ) ≥ H(Y ) when I(X;T ) ≥ H(Y ) for optimal T . At the same time, it is always the case that I(Y ;T ) ≤ H(Y ), by basic properties of MI. Thus, the IB curve is a flat line at I(Y ;T ) = H(Y ) for I(X;T ) ≥ H(Y ). Thus, when Y = f(X), the IB curve is piecewise linear and therefore not strictly concave.3

heading: 4 ISSUE 1: IB CURVE CANNOT BE EXPLORED USING THE IB LAGRANGIAN
text: We now show that when Y = f(X), one cannot explore the IB curve by solving arg maxT∈∆ L β IB while varying β, because there is no one-to-one mapping between points on the IB curve and optimizers of LβIB for different β. This issue is diagrammed in Fig. 2, and explained formally below. Assume Y = f(X). For any bottleneck variable T and all β ∈ [0, 1],4 LβIB is upper bounded by
LβIB(T ) = I(Y ;T )− βI(X;T ) ≤ (1− β)I(Y ;T ) ≤ (1− β)H(Y ) (7)
where the first inequality uses the DPI, and the second I(Y ;T ) ≤ H(Y ). Now consider the bottleneck variable Tcopy := f(X) = Y (or, equivalently, any one-to-one transformation of Tcopy), which corresponds to Tα for α = 1 in Eq. (6), and is the “corner point” of the IB curve in Fig. 1. Observe that LβIB(Tcopy) = (1− β)H(Y ), so Tcopy achieves the bound of Eq. (7). Thus, Tcopy optimizes LβIB for all β ∈ [0, 1], though it represents only a single point on the IB curve. The above argument shows that a single point on the IB curve optimizes LβIB for many different β. Conversely, many points on the curve can simultaneously optimize LβIB for a single β. In particular, for β = 1, LβIB(T ) = I(Y ;T ) − I(X;T ) ≤ 0 (the inequality follows from the DPI). Any T that has I(X;T ) = I(Y ;T ) — such as the manifold of Tα defined in Eq. (6) — achieves the maximum LβIB(T ) = 0 for β = 1, so all points on the non-flat part of IB curve in Fig. 1 simultaneously maximize LβIB for this β. For β = 0, L β
IB(T ) = I(Y ;T ) ≤ H(Y ), and this upper bound is achieved by all T that have I(Y ;T ) = H(Y ). Thus, all solutions on the flat part of the IB curve in Fig. 1 simultaneously maximize LβIB for β = 0. Note that common supervised learning algorithms that minimize cross-entropy loss can be considered to have β = 0, where there is no explicit benefit to compression, and their intermediate representations will typically fall into this regime.
The problem is illustrated visually in Fig. 2, which shows two hypothetical IB curves (in thick gray lines): a not strictly concave (piecewise linear) curve (left), as occurs when Y is a deterministic
3The IB curve may be not strictly concave in other cases as well. A sufficient condition for the IB curve to be strictly concave is for p(y|x) > 0 for all x, y (Gilad-Bachrach et al., 2003, Lemma 6).
4It is sufficient to consider β ∈ [0, 1] because for β < 0, uncompressed solutions like T = X are maximizers of LβIB, while for β > 1, L β IB is non-positive and trivial solutions such as T = const are maximizers.
0 I(X; T) 0
H(Y) I(Y ;T )
Not strictly concave
0 I(X; T)
Strictly concave
0.0 0.2 0.4 0.6 0.8 1.0
Figure 2: Failure of IB Lagrangian. Thick gray lines shows two possible IB curves, thin lines are isolines of LβIB for different β (colors indicate different β), stars indicate achievable 〈I(X;T ), I(Y ;T )〉 that maximize LβIB. For not strictly concave IB curve, different β ∈ (0, 1) only recover a single point. For strictly concave IB curve, different β recover different points.
function of X , and a strictly concave curve (right). In both subplots, the colored lines indicate isolines of the IB Lagrangian. The highest point on the IB curve crossed by a given colored line is marked by a star, and represents the 〈I(X;T ), I(Y ;T )〉 values for a T which optimizes LβIB for the corresponding β. For the piecewise linear IB curve, all β ∈ (0, 1) only recover a single solution (Tcopy). For the strictly concave IB curve, different β values recover different solutions.
To summarize, when Y = f(X), the IB curve is piecewise linear and cannot be explored by optimizing LβIB while varying β. On the flip side, if Y = f(X) and one’s goal is precisely to find the corner point 〈H(Y ), H(Y )〉 (maximum compression at no prediction loss), then our results suggest that the IB Lagrangian provides a robust way to do so, being invariant to the particular choice of β. Moreover, if one does want to recover solutions at different points on the IB curve, and f : X → Y is fully known, our results show how to do so in a closed-form way (via Tα), without any optimization.
Is there a single procedure that can be used to explore the IB curve in all cases, whether it is strictly convex or not? In principle, this can be done by solving the constrained optimization of Eq. (1) for different values of r. In practice, however, solving this constrained optimization problem — even approximately — is far from a simple task, in part due to the non-linear constraint on I(X;T ), and many off-the-shelf optimization tools cannot handle this kind of problem. It is desirable to have an unconstrained objective function that can be used to explore any IB curve. For this purpose, we propose an alternative objective function, which we call the squared-IB functional,
Lβsq-IB(T ) := I(Y ;T )− βI(X;T ) 2 . (8)
We show that maximizing Lβsq-IB while varying β recovers the IB curve, whether it is strictly concave or not. To do so, we first analyze why the IB Lagrangian fails when Y = f(X) (or, more generally, when the IB curve is piecewise linear). Over the increasing region of the IB curve, the inequality constraint in Eq. (1) can be replaced by an equality constraint (Witsenhausen & Wyner, 1975, Thm. 2.5), so maximizing LβIB can be written as maxT I(Y ;T )− βI(X;T ) = maxr F (r)− βr (i.e., the Legendre transform of−F (r)). The derivative of F (r)−βr is zero when F ′(r) = β, and any point on the IB curve that has F ′(r) = β will maximize LβIB for that β. When Y = f(X), all points on the increasing part of the curve have F ′(r) = 1, and will all simultaneously maximize LβIB for β = 1. More generally, all points on a linear segment of a piecewise linear IB curve will have the same F ′(r), and will all simultaneously maximize LβIB for the corresponding β. Using a similar argument as above, we write maxT Lβsq-IB = maxr F (r) − βr2. The derivative of F (r) − βr2 is 0 when F ′(r)/(2r) = β. Since F is concave, F ′(r) is decreasing in r, though it is not strictly decreasing when F is not strictly concave. F ′(r)/(2r), on the other hand, is strictly decreasing in r in all cases, thus there can be only one r such that F ′(r)/(2r) = β for a given β. For this reason, for any IB curve, there can be only one point that maximizes Lβsq-IB for a given β.5
Note also that any r that satisfiesF ′(r) = β also satisfiesF ′(r)/(2r) = β/(2r). Thus, any point that maximizes LβIB for a given β also maximizes L β
sq-IB under the transformation β 7→ β/(2 · I(X;T )), and vice versa. Importantly, unlike for LβIB, there can be non-trivial maximizers of L β sq-IB for β > 1.
The effect of optimizing Lβsq-IB is illustrated in Fig. 3, which shows two different IB curves (not strictly concave and strictly concave), isolines of Lβsq-IB for different β, and points on the curves that maximize Lβsq-IB. For both curves, the maximizers for different β are at different points of the curve.
5For simplicity, we consider only the differentiable points on the IB curve (a more thorough analysis would look at the superderivatives of F ). Since F is concave, however, it must be differentiable almost everywhere (Rockafellar, 2015, Thm 25.5).
0 I(X; T) 0
H(Y) I(Y ;T )
0 I(X; T)
0.0 0.5 1.0 1.5 2.0 2.5
Finally, note that the IB curve is the Pareto front of the multi-objective optimization problem, {max I(Y ;T ),min I(X;T )}. Lβsq-IB is one modification of L β
IB that allows us to explore a nonstrictly-concave Pareto front. However, it is not the only possible modification, and other alternatives may be considered. For a full treatment of multi-objective optimization, see Miettinen (1999).

heading: 5 ISSUE 2: ALL POINTS ON IB CURVE HAVE “UNINTERESTING” SOLUTIONS
text: It is often implicitly or explicitly assumed that IB optimal variables provide “useful” or “interesting” representations of the relevant information in X about Y (see also discussion and proposed criteria in (Amjad & Geiger, 2018)). While concepts like usefulness and interestingness are subjective, the intuition can be illustrated using the following example. Consider the ImageNet task (Deng et al., 2009), which labels images into 1000 classes, such as border collie, golden retriever, coffeepot, teapot, etc. It is natural to expect that as one explores the IB curve for the ImageNet dataset, one will identify useful compressed representations of the space of images. Such useful representations might, for instance, specify hard-clusterings that merge together inputs belonging to perceptually similar classes, such as border collie and golden retriever (but not border collie and teapot). Here we show that such intuitions will not generally hold when Y is a deterministic function of X .
Recall the analysis in Section 3, where Eq. (6) defines the manifold of bottleneck variables Tα parameterized by α ∈ [0, 1]. The manifold of Tα, which spans the entire increasing portion of the IB curve, represents a mixture of two trivial solutions: a constant mapping to 0, and an exact copy of Y . Although the bottleneck variables on this manifold are IB-optimal, they do not offer interesting or useful representations of the input data. The compression offered by Tα arises by “forgetting” the input with some probability 1− α, rather than performing any kind of useful hard-clustering, while the prediction comes from full knowledge of the function mapping inputs to outputs, f : X → Y . To summarize, when Y is a deterministic function of X , the fact that a variable T is on the IB curve does not necessarily imply that T is an interesting compressed representation of X . At the same time, we do not claim that Eq. (6) provides unique solutions. There may also be IB-optimal variables that do compress X in interesting and useful ways (however such notions may be formalized). Nonetheless, when Y is a deterministic function of X , for any “interesting” T , there will also be an “uninteresting” Tα that achieves the same compression I(X;T ) and prediction I(Y ;T ) values, and IB does not distinguish between the two. Therefore, identifying useful compressed representations must generally require the use of quality functions other than just IB.

heading: 6 ISSUE 3: NO TRADE-OFF AMONG DIFFERENT NEURAL NETWORK LAYERS
text: So far we’ve analyzed IB in terms of a single intermediate representation T (e.g., a single hidden layer in a neural network). Recent research in machine learning, however, has focused on “deep” neural networks, with multiple successive hidden layers. What is the relationship between the compression and prediction achieved by these different layers? Recently, Shwartz-Ziv & Tishby (2017) suggested that due to SGD dynamics, different layers will explore a strict trade-off between compression and prediction: early layers will sacrifice compression (high I(X;T )) for good prediction (high I(Y ;T )), while latter layers will sacrifice prediction (low I(Y ;T )) for good compression (low I(X;T )). The authors demonstrated a strict trade-off using an artificial classification dataset,
in which Y was defined to be a noisy function of X (their Eq. 10 and Fig. 6). As we show, however, this outcome cannot generally hold when Y is a deterministic function of X .
Recall that we consider IB in terms of the empirical distribution of inputs, hidden layers, and outputs given the training data (Section 2). Suppose that a classifier achieves 0 probability of error (i.e., classifies every input correctly) on training data. This event, which can only occur when Y is a deterministic function of X , is in fact commonly observed in real-world deep neural networks (Zhang et al., 2017). In such cases, we show that while latter layers may have better compression than earlier layers, they cannot have worse prediction than earlier layers. Therefore, different layers can only demonstrate a weak trade-off between compression and prediction. (The same argument holds if the neural network achieves 0 probability of error on held-out testing data, as long as the information-theoretic measures are evaluated on the same held-out data distribution.)
Consider a neural network with k hidden layers, where each successive layer is a (possibly stochastic) function of the preceding one, and let T1, T2, . . . , Tk indicate the activity of layer 1, 2, . . . , k. Given the predicted distribution of outputs, qθ(Ŷ = ŷ|Tk = tk), one can make a “point prediction” Ỹ , e.g., by choosing the class with the highest predicted probability, Ỹ := arg maxŷ qθ(ŷ|Tk). Given that the true output Y is a function of X , the above architecture obeys the Markov condition
Y −X − T1 − T2 − · · · − Tk − Ŷ − Ỹ . (9)
By the DPI, for any i < j we have the inequalities
I(Y ;Ti) ≥ I(Y ;Tj) , (10) I(X;Ti) ≥ I(X;Tj) . (11)
Applying Fano’s inequality (Cover & Thomas, 2012, p. 39) to the chain Y − Tk − Ỹ gives
H(Pe) + Pe log(|Y| − 1) ≥ H(Y |Tk) , (12)
where |Y| is the number of output classes, Pe = Pr(Y 6= Ỹ ) is the probability of error, andH(x) := −x log x − (1 − x) log(1 − x) is the binary entropy function. Given our assumption that Pe = 0, Eq. (12) implies that H(Y |Tk) = 0 and thus I(Tk;Y ) = H(Y )−H(Y |Tk) = H(Y ). Combining with Eq. (10) and I(Ti;Y ) ≤ H(Y ) means that I(Ti;Y ) = H(Y ) for all i = 1, . . . , k. The above argument neither proves nor disproves the proposal in (Shwartz-Ziv & Tishby, 2017) that SGD dynamics favor hidden layer mappings that provide compressed representations of the input. Instead, our point is that for classifiers that achieve 0 prediction error, a strict compression/prediction trade-off is not possible. Even so, by Eq. (11) it is possible that latter layers have more compression than earlier layers while achieving the same prediction level (i.e., a weak trade-off). In terms of Fig. 1, this means that different layers will be on the flat part of the IB curve.
Note that some neural network architectures do not have a simple layer structure, in which each layer’s activity is a stochastic function of the previous layer’s, but rather allow information to flow in parallel across different channels (Szegedy et al., 2015) or to skip across some layers (He et al., 2016). The analysis in this section can still apply to such cases, as long as the different T1, . . . , Tk are chosen to correspond to groups of neurons that satisfy the Markov condition in Eq. (9).

heading: 7 A REAL-WORLD EXAMPLE: MNIST
text: We demonstrate the three caveats using the MNIST dataset of hand-written digits. To do so, we use the “nonlinear IB” method (Kolchinsky et al., 2017), which uses gradient-descent-based training to minimize cross-entropy loss plus a differentiable non-parametric estimate of I(X;T ) (Kolchinsky & Tracey, 2017). We use this technique to maximize a lower bound on the IB Lagrangian, as explained in (Kolchinsky et al., 2017), as well as a lower bound on the squared-IB functional.
In our architecture, the bottleneck variable, T ∈ R2, corresponds to the activity of a hidden layer with two hidden units. Using a two-dimensional bottleneck variable facilitates easy visual analysis of its activity. The map from inputX to variable T has the form T = aθ(X)+Z, whereZ ∼ N (0, I) is noise, and aθ is a deterministic function implemented using three fully-connected layers: two layers with 800 ReLU units each, and a third layer with two linear units. Note that the stochasticity in the mapping from X to T makes our mutual information term, I(X;T ), well-defined and finite. The decoding map, qθ(ŷ|t), uses a fully-connected layer with 800 ReLU units, followed by an
output layer of 10 softmax units. Results are reported for training data. See Appendix A for more details and figures, including results on testing data. TensorFlow code can be found at https: //github.com/artemyk/ibcurve .
Like other practical general-purpose IB methods, “nonlinear IB” is not guaranteed to find globallyoptimal bottleneck variables due to factors like: (a) difficulty of optimizing the non-convex IB objective; (b) error in estimating I(X;T ); (c) limited model class of T (i.e., T must be expressible in the form of T = aθ(X) + Z); (d) mismatch between actual decoder qθ(Ŷ |T ) and optimal decoder p̄θ(Y |T ) (see Section 2); and (e) stochasticity of training due to SGD. Nonetheless, in practice, the solutions discovered by nonlinear IB were very close to IB-optimal, and are sufficient to demonstrate the three caveats discussed in the previous sections.
Issue 1: IB Curve cannot be explored using the IB Lagrangian
We first demonstrate that the IB curve cannot be explored by maximizing the IB Lagrangian, but can be explored by maximizing the squared-IB functional, thus supporting the arguments in Section 4. Fig. 4 shows the theoretical IB curve for the MNIST dataset, as well as the IB curve empirically recovered by maximizing these two functionals (see also Fig. A5 for more details).
By optimizing the IB Lagrangian (Fig. 4A), we are only able to find three IB-optimal points: (1) Maximum prediction accuracy and no compression, I(Y ;T ) = H(Y ), I(X;T ) ≈ 8 nats; (2) Maximum compression possible at maximum prediction, I(Y ;T ) = I(X;T ) = H(Y ); (3) Total compression and zero prediction, I(X;T ) = I(Y ;T ) = 0.
Note that the identified solutions are all very close to the theoretically-predicted IB-curve. However, the switch between the 2nd regime (maximal compression possible at maximum prediction) and 3rd regime (total compression and zero prediction) in practice happens at β ≈ 0.45. This is different from the theoretical prediction, which states that this switch should occur at β = 1.0. The deviation from the theoretical prediction likely arises due to various practical details of our optimization procedure, as mentioned above. The switch from the 1st regime (no compression) to the 2nd regime happened as soon as β > 0, as predicted theoretically.
In contrast to the IB Lagrangian, by optimizing the squared-IB functional (Fig. 4B), we discover solutions located along different points on the IB curve for different values of β.
Additional insight is provided by visualizing the bottleneck variable T ∈ R2 (i.e., hidden layer activity) for both experiments. This is shown for different β in the scatter plot insets in Fig. 4. As expected, the IB Lagrangian experiments displayed three types of bottleneck variables: noncompressed variables (regime 1), compressed variables where each of the 10 classes is represented by its own compact cluster (regime 2), and a trivial solution where all activity is collapsed to a single cluster (regime 3). For the squared-IB functional, a different behavior was observed: As β increases, multiple classes become clustered together and the total number of clusters decreased.
Thus, nonlinear IB with the squared-IB functional learned to group X into a varying number of clusters, in this way exploring the full trade-off between compression and prediction.
Issue 2: All points on IB curve have “uninteresting” solutions
By maximizing the squared-IB functional, we could find (nearly) IB-optimal solutions along different points of the IB curve. Here we show that such solutions do not provide particularly useful representations of the input data, supporting the arguments made in Section 5.
Note that “stochastic mixture”-type solutions, in particular the family Tα (Eq. (6)), are not in our model class, since they cannot be expressed in the form T = aθ(X) + Z. Instead, our implementation favors “hard-clusterings” in which all inputs belonging to a given output class are mapped to a compact, well-separated cluster in the activation space of the hidden layer (note that inputs belonging to multiple output classes may be mapped to a single cluster). For instance, Fig. 4B, shows solutions with 10 clusters (β = 0.05), 6 clusters (β = 0.2), 3 clusters (β = 0.5), and 1 cluster (β = 2.0). Interestingly, such hard-clusterings are characteristic of optimal solutions for deterministic IB (dIB), as discussed in Appendix B. At the same time, in our results, the classes are not clustered in any particularly meaningful or useful way, and clusters contain different combinations of classes for different solutions. For instance, the solution shown for squared-IB functional with β = 0.5 has 3 clusters, one of which contains the classes {0, 2, 3, 4, 5, 6, 8, 9}, another contains the class 1, and the last contains the class 7. However, in other runs for the same β value, different clusterings of the classes arose. Moreover, because the different classes appear with close-to-uniform frequency in the MNIST dataset, any solution that groups the 10 classes into 3 clusters of size {8, 1, 1} will achieve similar values of I(X;T ), I(Y ;T ) as the solution shown for β = 0.5.
Issue 3: No trade-off among different neural network layers
For both types of experiments, runs with β = 0 minimize cross-entropy loss only, without any regularization term that favors compression. (Such runs are examples of “vanilla” supervised learning, though with stochasticity in the mapping between the input and the 2-node hidden layer.) These runs achieved nearly-perfect prediction, so I(Y ;T ) ≈ H(Y ). However, as shown in the scatter plots in Fig. 4, these hidden layer activations fell into spread-out clusters, rather than point-like clusters seen for β > 0. This shows that hidden layer activity was not compressed, in that it retained information about X that was irrelevant for predicting the class Y , and fell onto the flat part of the IB curve.
Recall that our neural network architecture has three hidden layers before T , and one hidden layer after it. Due to the DPI inequalities Eqs. (10) and (11), the earlier hidden layers must have less compression than T , while the latter hidden layer must have more compression than T . At the same time, β = 0 runs achieve nearly 0 probability of error on the training dataset (results not shown), meaning that all layers must achieve I(Y ;T ) ≈ H(Y ), the maximum possible. Thus, for β = 0 runs, as in regular supervised learning, the activity of the all hidden layers is located on the flat part of the IB curve, demonstrating a lack of a strict trade-off between prediction and compression.

heading: 8 CONCLUSION
text: The information bottleneck principle has attracted a great deal of attention in various fields, including information theory, cognitive science, and machine learning, particularly in the context of classification using neural networks. In this work, we showed that in any scenario where Y is a deterministic function ofX — which includes many classification problems — IB demonstrates behavior that is qualitatively different from when the mapping fromX to Y is stochastic. In particular, in such cases: (1) the IB curve cannot be recovered by maximizing the IB Lagrangian I(Y ;T )− βI(X;T ) while varying β; (2) all points on the IB curve contain “uninteresting” representations of inputs; (3) multi-layer classifiers that achieve zero probability of error cannot have a strict trade-off between prediction and compression among successive layers, contrary to a recent proposal.
Our results should not be taken to mean that the application of IB to supervised learning is without merit. First, they do not apply to various non-deterministic classification problems where the output is stochastic. Second, even for deterministic scenarios, one may still wish to control the amount of compression during training, e.g., to improve generalization or robustness to adversarial inputs. In this case, however, our work shows that to achieve varying rates of compression, one should use a different objective function than the IB Lagrangian.

heading: ACKNOWLEDGMENTS
text: We would like to thank the Santa Fe Institute for helping to support this research. Artemy Kolchinsky was supported by Grant No. FQXi-RFP-1622 from the FQXi foundation and Grant No. CHE-1648973 from the US National Science Foundation. Brendan D. Tracey was supported by the AFOSR MURI on multi-information sources of multi-physics systems under Award Number FA9550-15-1-0038.

heading: A DETAILS OF MNIST EXPERIMENTS
text: In Section 7, we demonstrate our results on the MNIST dataset (LeCun et al., 1998). This dataset contains a training set of 60,000 images and a test set of 10,000 images, each labeled according to digit. X ∈ R784 is defined to be a vector of pixels for a single 28 × 28 image, and Y ∈ {0, 1, ..., 9} is defined to be the class label. Our experiments were carried out using the “nonlinear IB” method (Kolchinsky et al., 2017). I(X;T ) was computed using the kernel-based mutual information upper bound (Kolchinsky & Tracey, 2017; Kolchinsky et al., 2017) and I(Y ;T ) was computed using the lower bound I(Y ;T ) ≥ H(Y )− Ep̄θ(Y,T ) [ − log qθ(Ŷ |T ) ] (see Eq. (5)).
The neural network was trained using the Adam algorithm (Kingma & Ba, 2014) with a mini-batch size of 128 and a learning rate of 10−4. Unlike the implementation in (Kolchinsky et al., 2017), the same mini-batch was used to estimate the gradients of both Iθ(X;T ) and the cross-entropy term. Training was run for 200 epochs. At the beginning of each epoch, the order of training examples was randomized. To eliminate the effect of the local minima, for each possible value of β, we carried out 20 runs and then selected the run that achieved the best value of the objective function. TensorFlow code is available at https://github.com/artemyk/ibcurve .
Results for the MNIST dataset are shown in Fig. 4 and Fig. A5, computed for a range of β values. Fig. A5 shows results for both training and testing datasets, though the main text focuses exclusively on training data. It can be seen that while the solutions found by IB Lagrangian jump discontinuously from the “fully clustered” solution (I(X;T ) = I(Y ;T ) = H(Y )) to the trivial solution (I(X;T ) = I(Y ;T ) = 0), solutions found by the squared-IB functional explore the trade-off in a continuous manner. See figure captions for details.

heading: B DETERMINISTIC INFORMATION BOTTLENECK
text: Here we show that our analysis also applies to a recently-proposed (Strouse & Schwab, 2017) variant of IB called deterministic IB (dIB). dIB replaces the standard IB compression cost, I(X;T ), with the entropy of the bottleneck variable, H(T ). This can be interpreted as operationalizing compression costs via a source-coding, rather than a channel-coding, scenario.
Formally, in dIB one is given random variables X and Y . One then identifies bottleneck variables T that obey the Markov condition Y −X − T and maximize the dIB Lagrangian,
LβdIB(T ) := I(Y ;T )− βH(T ) (A13)
for β ∈ [0, 1], which can be considered as a relaxation of the constrained optimization problem
FdIB(r) := max T∈∆
I(Y ;T ) s.t. H(T ) ≤ r . (A14)
To guarantee that the compression cost is well-defined, T is typically assumed to be discretevalued (Strouse & Schwab, 2017). We call FdIB the dIB curve.
Before proceeding, we note that the inequality constraint in the definition of FdIB(r) can be replaced by an equality constraint,
FdIB(r) := max T∈∆ I(Y ;T ) s.t. H(T ) = r (A15)
We do so by showing that FdIB(r) is monotonically increasing in r. Consider any T which maximizes I(Y ;T ) subject to the constraint H(T ) = r, and obeys the Markov condition Y − X − T . Now imagine some random variable D which obeys the Markov condition Y − X − T − D, and define a new bottleneck variable T ′ := (T,D) (i.e., the joint outcome of T and D). We have
I(Y ;T ′) = I(Y ;T,D) = I(Y ;T ) + I(Y ;D|T ) = I(Y ;T ) ,
where we’ve used the chain rule for mutual information. At the same time, D can always be chosen so that H(T ′) = H(T,D) = r′ for any r′ ≥ r. Thus, we have shown that there are always random variables T ′ that achieve at least I(Y ;T ′) = maxT :H(T )=r I(Y ;T ) and have H(T ′) > r, meaning that FdIB(r) is monotonically increasing in r. This means the inequality constraint in Eq. (A14) can be replaced with an equality constraint.
As we will see, unlike the standard IB curve, FdIB is not necessarily concave. Since FdIB can be defined using equality constraints, one can rewrite maximization ofLβdIB as maxT I(Y ;T )−βH(T ) = maxr FdIB(r) − βr, the Legendre-Fenchel transform of −FdIB(r). By properties of the LegendreFenchel transform, the optimizers of LβdIB must lie on the concave envelope of FdIB, which we indicate as F ∗dIB.
B.1 THE DIB CURVE WHEN Y IS A DETERMINISTIC FUNCTION OF X
As in standard IB, for a discrete-valued Y we have the inequality
I(Y ;T ) ≤ H(Y ) . (A16)
However, instead of the standard IB inequality I(Y ;T ) ≤ I(X;T ), we now employ
I(Y ;T ) ≤ H(T ) , (A17)
which makes use of the assumption that T is discrete-valued. The dIB curve will have the same bounds as those shown for the standard IB curve (Fig. 1), except that H(T ) replaces I(X;T ) on the horizontal axis.
Now consider the case where Y is a deterministic function of X , i.e., Y = f(X). It is easy to check that Tcopy := f(X) = Y achieves equality for both Eqs. (A16) and (A17), and thus lies on the dIB curve. Since FdIB is monotonically increasing, the dIB curve is flat and achieves I(Y ;T ) = H(Y ) for all H(T ) ≥ H(Y ). We now consider the increasing part of the curve, H(T ) ∈ [0, H(Y )]. We call any T which is a deterministic function of Y (that is, any T = g(Y ) = g(f(X)), where g is any deterministic function) a “hard-clustering” of Y . Any hard-clustering of Y has H(T ) ≤ H(Y ). At the same
time, any hard-clustering of Y has H(T |Y ) = 0, thus I(Y ;T ) = H(T ) − H(T |Y ) = H(T ), achieving the bound of Eq. (A17). Thus, any hard-clustering of Y lies on the increasing part of the dIB curve. Note that any hard-clustering of Y will also be a deterministic function of X , thus have H(T |X) = 0 and I(X;T ) = H(T )−H(T |X) = H(T ) = I(Y ;T ), and will therefore also fall on the increasing part of the standard IB curve.
0 H(Y)H(T) 0
H(Y)
I(Y ;T
)
I(Y; T) H(T) I(Y; T) H(Y) dIB curve for Y = f(X)
Figure A6: A schematic of the dIB curve. Dashed line is the bound I(Y ;T ) ≤ H(T ), dotted line is I(Y ;T ) ≤ H(Y ). When Y is a deterministic function ofX , the dIB curve saturate the second bound always. Furthermore, it also saturates the first bound for any T that is a deterministic function of Y . The qualitative shape of the resulting dIB curve is shown as thick gray line.
At the same time, the dIB curve cannot be composed entirely of hard-clustering, since — under the assumption that Y is discrete-valued — there can only be a countable number of T ’s that are hard-clusterings of Y . Thus, the dIB curve must also contain bottleneck variables that are not deterministic functions of Y , thus haveH(T |Y ) > 0 and I(Y ;T ) < H(T ), and do not achieve the bound of Eq. (A17). Geometrically-speaking, when Y is a deterministic function of X , the dIB curve must have a “step-like” structure overH(T ) ∈ [0, H(Y )], rather than increasing smoothly like the standard IB curve. These results are shown schematically in Fig. A6, where blue dots indicate hard clusters of Y .
As mentioned, optimizers of LβdIB must lie on the concave envelope of FdIB, indicated by F ∗dIB. Clearly, the step-like dIB curve that occurs when Y is a deterministic function of X is not concave, and only hard-clusterings of Y lie on its concave envelope for H(T ) ∈ [0, H(Y )]. In the analysis below, we will generally concern ourselves with optimizers which are hard-clusterings.
B.2 THE THREE CAVEATS
We now briefly consider the three issues discussed in the main text, in the context of dIB. As usual, we assume that Y is a deterministic function of X .
Issue 1: dIB Curve cannot be explored using the dIB Lagrangian
In analogy to the analysis done in Section 4, we use the inequalities Eqs. (A16) and (A17) to bound the dIB Lagrangian as
LβdIB(T ) = I(Y ;T )− βH(T ) ≤ (1− β)I(Y ;T ) ≤ (1− β)H(Y ) . Now consider the bottleneck variable Tcopy, for which LβdIB(Tcopy) = (1−β)H(Y ). Therefore, Tcopy (or any one-to-one transformation of Tcopy) will maximize LβdIB for all β ∈ [0, 1]. It is also straightforward to show that when β = 0, all bottleneck variables residing on the flat part of the dIB curve will simultaneously optimize the dIB Lagrangian. Similarly, one can show that all hard-clusterings of Y , which achieve the bound of Eq. (A17), will simultaneously optimize the dIB Lagrangian for β = 1. As before, this means that there is no one-to-one map between points on the dIB curve and optimizers of the dIB Lagrangian for different β.
As in Section 4, we propose to resolve this problem by maximizing an alternative objective function, which we call the squared-dIB functional,
Lβsq-dIB(T ) := I(Y ;T )− βH(T ) 2 . (A18)
We first demonstrate that any optimizer of the dIB Lagrangian must also be an optimizer of the squared-dIB functional. Consider that maximization of LβdIB can be written as maxT I(Y ;T ) − βH(T ) = maxr F ∗ dIB(r) − r. Then, for the point 〈r, F ∗dIB(r)〉 on the dIB curve to maximize L β
dIB, it must have β ∈ ∂rF ∗dIB(r), where ∂r indicates the superderivative with regard to r. At the same time, for the point 〈r, F ∗dIB(r)〉 to maximize L β sq-dIB, it must satisfy 0 ∈ ∂r [ F ∗dIB(r)− βr2 ] , or after rearranging,
2rβ ∈ ∂rF ∗dIB(r) . (A19) It is easy to see that if β ∈ ∂rF ∗dIB(r) is satisfied, then Eq. (A19) is also satisfied under the transformation β 7→ β2r . Thus, any optimizer of L β dIB will also optimize L β sq-dIB, given β 7→ β 2r .
0 H(T) 0
H(Y) I(Y ;T )
I(Y; T) H(T)
0 H(T)
I(Y; T) H(T)2
0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.5 1.0 1.5 2.0 2.5
Figure A7: Success of squared-dIB functional. Colored lines indicate manifolds which have the same value of the dIB Lagrangian (left) and the squared-dIB functional (right) for different values of β, the stars indicate achievable 〈H(T ), I(Y ;T )〉 that maximize each function. For the dIB curve when Y = f(X), different β values recover different solutions only for the squared-dIB functional.
We now show that different hard-clusterings of Y will optimize the squared-dIB functional for different values of β, meaning that we can explore the envelope of the dIB curve by optimizing Lβsq-dIB while varying β. Formally, we show that for any given β > 0, the point
〈H(T ), I(Y ;T )〉 = 〈 1
2β ,
1
2β
〉 (A20)
on the dIB curve will be a unique maximizer of Lβsq-dIB for the corresponding β. Consider the value of Lβsq-dIB for any T satisfying Eq. (A20),
Lβsq-dIB(T ) = 1
2β − β
( 1
2β
)2 = 1
2β − 1 4β = 1 4β
Now consider the value of of Lβsq-dIB for any other T ′ on the dIB curve which has H(T ′) 6= 1 2β ,
Lβsq-dIB(T ′) = I(Y ;T ′)− βH(T ′)2
= I(Y ;T ′)− β (( H(T ′)− 1
2β
)2 + H(T ′)
β − 1 4β2 ) (a) < (I(Y ;T ′)−H(T ′)) + 1 4β (b) ≤ 1 4β = Lβsq-dIB(T ) .
Inequality (a) comes from the assumption that H(T ′) 6= 12β , thus (H(T ′)− 1/(2β))2 > 0, while inequality (b) comes from the bound I(Y ;T ′) ≤ H(T ′). We have shown that Lβsq-dIB(T ′) < Lβsq-dIB(T ), meaning that any point on the dIB curve satisfying Eq. (A20) for a given β, assuming it exists, will be the unique maximizer of Lβsq-dIB. The situation is diagrammed visually in Fig. A7. Issue 2: All points on dIB curve have “uninteresting” solutions
The family of bottleneck variables Tα defined in Eq. (6), i.e., the mixture of two trivial solutions, are no longer optimal from the point of view of dIB. However, as mentioned above, any T that is a hard-clustering of Y achieves the bound of Eq. (A17), and is thus on the dIB curve.
However, given a hard-clustering of Y , there is no reason for the clusters to obey any intuitions about semantic or perceptual similarity between grouped-together classes. To use the ImageNet example from Section 5, there is no reason for dIB to prefer a coarse-graining with “natural” groups like {border collie, golden retriever} and {teapot, coffeepot}, rather than a coarse-graining with groups like {border collie, teapot} and {golden retriever, coffeepot}, assuming those classes are of the same
size. Distinguishing between such different clusterings requires some similarity or distortion measure between classes, which is not provided by the standard information theoretic measures.
Issue 3: No trade-off among different neural network layers
In Section 6, we showed that for a neural network with many hidden layers and zero probability of error, the activity of the different layers will lie along the flat part of the standard IB curve, where there is no strict trade-off between compression I(X;T ) and prediction I(Y ;T ). Note that any bottleneck variable that lies along the flat part of a standard IB curve will have I(X;T ) ≥ H(Y ) and I(Y ;T ) = H(Y ). Using the standard information-theoretic inequality H(T ) ≥ I(X;T ), the same bottleneck variable must therefore have H(T ) ≥ H(Y ) and I(Y ;T ) = H(Y ), thus also lying on the flat part of the dIB curve. Thus, for a neural network with many hidden layers and zero probability of error, the activity of the different layers will also lie along the flat part of the dIB curve, and not demonstrate any strict trade-off between compression H(T ) and prediction I(Y ;T ).

heading: C CAVEATS WHEN Y IS APPROXIMATELY A DETERMINISTIC FUNCTION OF X
text: In this Appendix, we show that when Y is a small perturbation away from being a deterministic function of X , the three caveats discussed in the main text persist in an approximate manner.
To derive our results, we first prove several useful theorems. In our proofs, we make central use of Thm. 17.3.3 from Cover & Thomas (2012), which states that, for two distributions a and b over the same finite set of outcomes Y , if the `1 distance is bounded as |a − b|1 ≤ ≤ 12 , then |H(a)−H(b)| ≤ − log |Y| . We will also use the weaker bound |H(a)−H(b)| ≤ log |Y|, which is based on the maximum and minimum entropy for any distribution over outcomes Y . Theorem 1. Let Z be a random variable (continuous or discrete), and Y a random variable with a finite set of outcomes Y . Consider two joint distributions over Z and Y , pZY and p̃ZY , which have the same marginal over Z, p(z) = p̃(z), and obey |pZY − p̃ZY |1 ≤ ≤ 1 2 . Then,
|H(p(Y |Z))−H(p̃(Y |Z))| ≤ − log |Y|3 .
Proof. For this proof, we will assume that Z is a continuous-valued. In case it is discrete-valued, the below proof applies after replacing all integrals over the outcomes of Z with summations.
Let ̂ := |pZY − p̃ZY |1 = ∫ ∑
y |pZY (z, y)− p̃ZY (z, y)| dz be the actual `1 distance between pZY and p̃ZY , and note that ̂ ≤ by assumption. Without loss of generality, we assume that ̂ > 0. Then, define the following probability distribution,
q(z) := 1
̂ p(z) ∣∣pY |Z=z − p̃Y |Z=z∣∣ = 1 ̂ p(z) ∑ y |p(y|z)− p̃(y|z)| .
Note that q(z) integrates to 1 and is absolutely continuous with respect to p(z) (p(z) = 0 implies q(z) = 0), and that ∣∣pY |Z=z − p̃Y |Z=z∣∣ = ̂ q(z)p(z) . When then have |H(p(Y |z))−H(p̃(Y |z))| ≤ { −̂ q(z)p(z) log ̂ |Y| q(z) p(z) if ̂ q(z) p(z) ≤ 1 2
log |Y| otherwise ,
where the first case follows from (Cover & Thomas, 2012, Thm. 17.3.3), and the second case by considering minimum vs. maximum possible entropy values.
We now bound the difference in conditional entropies, using [·] to indicate the Iverson bracket, H(p(Y |Z))−H(p̃(Y |Z)) = ∫ p(z) [H(p(Y |z))−H(p̃(Y |z))] dz ≤∫
p(z) [ ̂ q(z)
p(z) ≤ 1 2
]( −̂ q(z)
p(z) log
̂ |Y| q(z) p(z)
) dz + log |Y| ∫ p(z) [ ̂ q(z)
p(z) >
1
2
] dz . (A21)
We upper bound the first integral in Eq. (A21) as∫ p(z) [ ̂ q(z)
p(z) ≤ 1 2
] ( −̂ q(z)
p(z) log
̂ |Y| q(z) p(z)
) dz
≤ ∫ p(z) ( −̂ q(z)
p(z) log
̂ |Y| q(z) p(z)
) dz (A22)
= −̂ ∫ q(z) ( log ̂
|Y| + log
q(z)
p(z)
) dz
= −̂ log ̂ |Y| − ̂DKL(q(Z)‖p(Z)) ≤ −̂ log ̂ |Y| (A23)
where in Eq. (A22) we dropped the Iverson bracket, in Eq. (A23) we used the definition of KL divergence, and then its non-negativity.
To upper bound the second integral in Eq. (A21), observe that∫ p(z) [ ̂ q(z)
p(z) >
1
2
] dz = ∫ p(z) [∣∣pY |Z=z − p̃Y |Z=z∣∣ > 1 2 ] dx
≤ ∫ p(z) 2 ∣∣pY |Z=z − p̃Y |Z=z∣∣ [∣∣pY |Z=z − p̃Y |Z=z∣∣ > 1 2 ] dz
≤ 2 ∫ p(z) ∣∣pY |Z=z − p̃Y |Z=z∣∣ dz ≤ 2̂ (A24) Combining Eqs. (A21), (A23) and (A24) gives
H(p(Y |Z))−H(p̃(Y |Z)) ≤ −̂ log ̂ |Y| + 2̂ log |Y| = −̂ log ̂ |Y|3
The theorem follows by noting that −̂ log ̂ is monotonically increasing for ̂ ≤ 12 , and by assumption ̂ ≤ ≤ 12 .
In the following theorems, we use the notation Iq(Z;Y ) to indicate mutual information between Z and Y evaluated under some joint distribution q over Z and Y . Theorem 2. Let Z be a random variable (continuous or discrete), and Y a random variable with a finite set of outcomes. Consider two joint distribution over X × Y , pXY and p̃XY , which have the same marginal over Z, p(z) = p̃(z), and obey |pZY − p̃ZY |1 ≤ ≤ 1 2 . Then,
|Ip(Z;Y )− Ip̃(Z;Y )| ≤ −2 log
|Y|2 .
Proof. We first bound the `1 distance between pY and p̃Y ,
|pY − p̃Y |1 = ∑ |pY (y)− p̃Y (y)| = ∑ y ∣∣∣∣∫ (pZY (z, y)− p̃XY (z, y)) dz∣∣∣∣ ≤ ∑ y ∫ |pZY (z, y)− p̃ZY (z, y)| dz = |pZY − p̃ZY |1 ≤
By (Cover & Thomas, 2012, Thm. 17.3.3),
|H(p(Y ))−H(p̃(Y ))| ≤ − log |Y| . (A25)
We now bound the magnitude of the difference of mutual informations as
|Ip(Z;Y )− Ip̃(Z;Y )| = |H(p(Y ))−H(p̃(Y ))− (H(p(Y |Z))−H(p̃(Y |Z)))| ≤ |H(p(Y ))−H(p̃(Y ))|+ |H(p(Y |Z))−H(p̃(Y |Z))|
≤ − log |Y| − log |Y|3 = −2 log |Y|2 ,
where in the last line we’ve used Eq. (A25) and Theorem 1.
Theorem 3. Let X be a random variable (continuous or discrete), and Y a random variable with a finite set of outcomes Y . Consider two joint distribution over X and Y , pXY and p̃XY , which have the same marginal over X , p(x) = p̃(x) and obey |pXY − p̃XY |1 ≤ ≤ 1 2 . Let F (r) and F̃ (r) indicate the IB curves for pXY and p̃XY respectively, as defined in Eq. (1). Then for any r > 0,
|F (r)− F̃ (r)| ≤ −2 log |Y|2 .
Proof. For any compression level r > 0, let T and T̃ be optimal bottleneck variables for pXY and p̃XY respectively,
I(X;T ) ≤ r ; Ip(Y ;T ) = F (r) I(X; T̃ ) ≤ r ; Ip̃(Y ; T̃ ) = F̃ (r) .
Let T be defined by the stochastic map q(t|x), and note that pT (t) = ∫ p(x)q(t|x) dx =∫
p̃(x)q(t|x) dx = p̃T (t). Consider two joint distributions over T and Y ,
pTY (t, y) = ∫ pXY (x, y)q(t|x) dx ; p̃TY (t, y) = ∫ p̃XY (x, y)q(t|x) dx ,
and observe that |pTY − p̃TY |1 = ∫ dt ∑ y ∣∣∣∣∫ pXY (x, y)q(t|x) dx− ∫ p̃XY (x, y)q(t|x) dx∣∣∣∣ ≤ ∫ dt ∑ y ∫ q(t|x) |pXY (x, y)− p̃XY (x, y)| dx
≤ ∑ y ∫ |pXY (x, y)− p̃XY (x, y)| dx ≤
We now apply Theorem 2 with Z = T and Y = Y to give Ip(Y ;T )+2 log |Y|2 ≤ Ip̃(Y ;T ). At the same time, by definition of the IB curve, it must be that Ip̃(Y ;T ) ≤ F̃ (r) = Ip̃(Y ; T̃ ). Combining the last two inequalities gives
Ip(Y ;T ) + 2 log |Y|2 ≤ Ip̃(Y ; T̃ ) . (A26)
The same argument can be repeated while exchanging the roles of T and T̃ (thus defining the joint distributions pT̃ Y and p̃T̃ Y , etc.). This gives the inequality
Ip̃(Y ; T̃ ) + 2 log |Y|2 ≤ Ip(Y ;T ) . (A27)
The theorem follows by combining Eqs. (A26) and (A27), and using the relations Ip(Y ;T ) = F (r), Ip̃(Y ;T ) = F̃ (r).
It is important to emphasize that having a small `1 distance between the joint distributions pXY and pXY does not imply that the conditional distributions pY |X=x and p̃Y |X=x have to be close for all x. In fact, the conditional distributions can be arbitrarily different for some x, as long as such x do not have much probability under p(x).
We use these theorems to demonstrate how, if the joint distribution of X and Y is -close to having Y be a deterministic function of X , then the three caveats discussed in the main text all apply in an approximate manner, meaning that can only be avoided up to order O(− log ).
C.1 THE THREE CAVEATS WHEN Y IS APPROXIMATELY A DETERMINISTIC FUNCTION OF X
Issue 1: IB curve cannot be explored using the IB Lagrangian
In the main text, we demonstrated that when Y is a deterministic function of X , the single point 〈H(Y ), H(Y )〉 on the information plane optimizes the IB Lagrangian for all β ∈ [0, 1]. We now consider the case where the joint distribution of X and Y is -close to having Y be a deterministic function of X . The next theorem shows that in this case, optimizers of the IB Lagrangian must still be close to 〈H(Y ), H(Y )〉. Formally, for any fixed β ∈ (0, 1), the maximum possible distance from 〈H(Y ), H(Y )〉 scales as O(− log ), though the scaling constant increases as β approaches 0 or 1. This implies that for small , it will difficult to find solutions substantially different from 〈H(Y ), H(Y )〉, as one would have to search using β very close to 0 or very close to 1. Theorem 4. Let X be a random variable (continuous or discrete), and Y a random variable with a finite set of outcomes Y . Let p̃XY be a joint distribution over X and Y under which Y = f(X). Let pXY be a joint distribution over X and Y which has the same marginal over X as p̃XY , p(x) = p̃(x), and obeys |pXY − p̃XY |1 ≤ ≤ 1 2 .
Then, for any β ∈ (0, 1) and T which maximizes the pXY IB Lagrangian Ip(Y ;T )− βIp(X;T ),
− γ 1− β ≤ Ip(X;T )−H(p(Y )) ≤ γ β (A28) − γ 1− β ≤ Ip(Y ;T )−H(p(Y )) ≤ 0 (A29)
where γ := −3 log + 5 log |Y|.
Proof. First, note that if |pXY − p̃XY |1 ≤ , then |pY − p̃Y |1 ≤ and (see proof of Theorem 2)
|H(p(Y ))−H(p̃(Y ))| ≤ − log |Y| . (A30)
Let F and F̃ indicate the IB curves for pXY and p̃XY , respectively, defined as in Eq. (1). Because p̃XY is deterministic, the IB curve F̃ is the piecewise linear function F̃ (x) = min{x,H(p̃(Y ))}. Given Eq. (A30), this means that
F̃ (H(p(Y ))) ≥ H(p(Y )) + log |Y| . (A31)
We now to bound F (H(p(Y ))) as
F (H(p(Y ))) ≥ F̃ (H(p(Y ))) + 2 log |Y|2
≥ H(p(Y )) + 2 log |Y|2 + log
|Y| = H(p(Y ))− γ , (A32)
where in the first line we’ve used Theorem 3, and in the second line we used Eq. (A31).
Now consider T , the bottleneck variable that optimizes the pXY IB Lagrangian for some β ∈ (0, 1). By concavity of the IB curve F , all points on the IB curve must fall below the line with slope β that passes through the point 〈Ip(X;T ), Ip(Y ;T )〉 on the information plane, including the point 〈H(p(Y )), F (H(p(Y ))〉. Formally, we write this condition as
Ip(Y ;T ) + β (H(p(Y ))− Ip(X;T )) ≥ F (H(p(Y )) ≥ H(p(Y ))− γ , (A33)
where the second inequality uses Eq. (A32). Note that by the DPI, Ip(X;T ) ≥ Ip(Y ;T ). Combining with Eq. (A33) gives
Ip(X;T ) + β (H(p(Y ))− Ip(X;T )) ≥ H(p(Y ))− γ (β − 1) (H(p(Y ))− Ip(X;T )) ≥ −γ
H(p(Y ))− Ip(X;T ) ≤ γ
1− β . (A34)
At the same time, by properties of mutual information, H(p(Y )) ≥ Ip(Y ;T ). Combining again with Eq. (A33) gives
H(p(Y )) + β (H(p(Y ))− Ip(X;T )) ≥ H(p(Y ))− γ
H(p(Y ))− Ip(X;T ) ≥ − γ
β (A35)
The result Eq. (A28) follows immediately from Eq. (A34) and Eq. (A35) and rearranging.
We now derive Eq. (A29). The upper bound arises from basic properties of mutual information, H(p(Y )) ≥ Ip(Y ;T ). To derive the lower bound, we rewrite Eq. (A33) as
Ip(Y ;T ) ≥ H(p(Y ))− γ + β(Ip(X;T )−H(p(Y ))) (A36)
≥ H(p(Y ))− γ − β 1− β γ = H(p(Y ))− γ 1− β , (A37)
where in the second line we used Eq. (A28) and then combined terms.
Issue 2: All points on the IB curve are O(− log ) away from trivial solutions. In the main text, we show that when Y is a deterministic function of X , there are trivial bottleneck variables which are optimal for all points of the IB curve. We now consider the case where the joint distribution of X and Y is -close to having Y be a deterministic function of X . In this case, by using Theorem 3, it is straightforward to show that there are trivial bottleneck variables that are O(− log ) away from being optimal along all points on the IB curve. Theorem 5. Let X be a random variable (continuous or discrete), and Y a random variable with a finite set of outcomes Y . Let p̃XY be a joint distribution over X and Y under which Y = f(X). Let pXY be a joint distribution over X and Y which has the same marginal over X as p̃XY , p(x) = p̃(x), and obeys |pXY − p̃XY |1 ≤ ≤ 1 2 .
Then, for any r > 0, there is some value of α ∈ [0, 1] such that the bottleneck variable Tα defined by the conditional distribution qα(Tα = t|X = x) = αδ(t, f(x)) + (1− α)δ(t, 0) satisfies
Ip(Tα;X) ≤ r ; Ip(Tα;Y ) ≥ F (r)− γ , where γ := −3 log + 5 log |Y|.
Proof. First, note that if |pXY − p̃XY |1 ≤ , then |pY − p̃Y |1 ≤ and
|H(p(Y ))−H(p̃(Y ))| ≤ − log |Y| . (A38)
(See proof of Theorem 2.)
Let F (r) and F̃ (r) indicate the IB curve for pXY and p̃XY , respectively, as defined in Eq. (1). By properties of mutual information and Eq. (A38), we have
F (r) ≤ H(p(Y )) ≤ H(p̃(Y ))− log |Y| . (A39)
We now consider two cases.
The first case is when r ≤ H(p̃(Y )). Recall that because p̃XY is deterministic, the IB curve F̃ is the piecewise linear function F̃ (x) = min{x,H(p̃(Y ))}. Thus, we choose an α so that Ip(X;Tα) = r and, using Theorem 3,
Ip(X;Tα) = F̃ (r) ≥ F (r) + 2 log |Y|2 ≥ F (r)− γ .
Second, when r > H(p̃(Y )), we choose α = 1 and note that Ip(Tα;X) = H(p̃(Y )) ≤ r. It can be verified (see for instance proof of Theorem 3) that the joint distributions pTαY (t, y) =∫ pXY (x, y)qα(t|x) dx and p̃TαY (t, y) = ∫ p̃XY (x, y)qα(t|x) dx satisfy the conditions of Theorem 2 with Z = Tα, Y = Y . Applying that theorem gives
Ip(Y ;Tα) ≥ Ip̃(Y ;Tα) + 2 log
|Y|2 = H(p̃(Y )) + 2 log |Y|2 ≥ H(p(Y ))− γ ,
where the last inequality uses Eq. (A39).
Issue 3: Prediction/compression trade-off can be most of order O(− log ) In the main text, we consider a neural network consisting of k layers, and show that when Y is a deterministic function of X , there can be no strict prediction/compression trade-off between the different layers. We now consider the case where the joint distribution of X and Y is -close to having Y be a deterministic function of X .
As before, we let X be a (continuous or discrete) random variable, and Y a random variable with a finite set of outcomes Y . Let p̃XY be a joint distribution over X and Y under which Y = f(X). Let pXY be a joint distribution overX and Y which has the same marginal overX as p̃XY , p(x) = p̃(x), and obeys |pXY − p̃XY |1 ≤ ≤ 1 2 .
We assume that for each input X , our classifier outputs the prediction Ỹ = f(X) — that is, it predicts according to the deterministic input-output mapping f . For small , this is an optimal prediction strategy in terms of Pe, the probability of error. We write Pe for this classifier as
Pe =
∫ p(x) ( 1− pY |X=x(f(x)|x) ) dx
= 1
2
∫ p(x) (1− pY |X=x(f(x)|x))+ ∑ y:y 6=f(x) pY |X=x(y|x)  = 1
2 ∫ ∑ y p(x) |pY |X=x(y|x)− p̃Y |X=x(y|x)| dx
= 1
2 |pXY − p̃XY |1 ≤
1
2
We now restate Fano’s inequality (Eq. (12)) for the activity of the last layer, Tk, as
H(Y |Tk) ≤ H(Pe) + Pe log(|Y| − 1) ≤ −2Pe log 2Pe |Y| = − log |Y| , (A40)
where the second inequality is found in Zhang (2007).
As before, we note that latter layers may compress input information more than earlier ones, in that I(Tk;X) may be smaller than I(T1;X). Moreover, when Y is not exactly a deterministic function of X , then in principle a strict prediction/compression trade-off between different layers is possible (i.e., I(Ti;Y ) can decrease for latter layers). However, if the joint distribution of X and Y is -close to having Y = f(X), then the magnitude this trade-off is limited in size,
I(T1;Y )− I(Tk;Y ) = H(Y |Tk)−H(Y |T1) ≤ − log
|Y| ,
where we use non-negativity of conditional entropy and Eq. (A40).

Review summaries:
This paper is about potential problems of the information bottleneck principle in cases where the output variable Y is a deterministic function of the inputs X. Such a deterministic relationship between outputs and inputs induces the problem that the the IB "information curve" (i.e. I(T;Y) as a function of I(X;T)) is piece-wise linear and, thus, no longer strictly concave, which is crucial for non-degenerate ("interesting") solutions. The authors argue that most real classification problems indeed show such a deterministic relation between the class labels and the inputs X, and they explore several issues that result from such pathologies.