Title: THE DUAL INFORMATION BOTTLENECK

Abstract: The Information Bottleneck (IB) framework is a general characterization of optimal representations in large scale learning that suggests an intriguing interpretation of efficient representations in deep learning in particular. It is based on the optimal trade off between the representation complexity and accuracy, both of which are quantified by mutual information. The problem is solved by alternating projections between the encoder and decoder of the representation, which can be performed locally at each representation level. The non-parametric IB framework, however, has several drawbacks: (i) the difficult estimation of information measures in high dimensions; (ii) the inability to extend the encoder beyond the training data -the need to to know the full joint distribution of the inputs and labels; (iii) the IB does not necessarily optimize the actual prediction of unseen labels, which can be critical when training the encoder from finite samples. Here we present a new framework, the Dual Information Bottleneck (dualIB), which improves all the above drawbacks. By switching the order in the KL-divergence between the representation decoder and data, formally the dual distortion, the optimal decoder becomes the geometric rather than the arithmetic mean of the input points. This conversion preserves exponential forms of the original distribution and consequently conserves the original features of the data. We show how to solve this new representation learning formulation and illustrate it's favorable properties over the original IB when trained from a small sample. We also analyze the critical points of the dualIB and discuss their importance for the quality of this approach.

1. INTRODUCTION 1.THE INFORMATION BOTTLENECK METHOD:

The Information Bottleneck (IB) method (Tishby et al., 1999) , is an information-theoretic framework for describing efficient representations of a large scale "input" random variable X (input patterns), for predicting an "output" variable Y (desired label). In this setting the joint distribution of X and Y, p(x, y) defines the problem, or rule, and the training data are a finite sample from this distribution. In general, we assume that p(y | x) is strictly stochastic, and hence bounded away from {0, 1}1 . The representation variable X is in general a stochastic function of X which forms a Markov chain Y → X → X, and only depends on Y through the input X. We call the map p(x | x) the encoder of the representation and denote by p(y | x) the Bayes optimal decoder for this representation; i.e., the best possible prediction of the desired label Y from the representation X.

The IB has direct successful applications for representation learning in various domains, from vision and speech processing (Ma et al., 2019) , to neuroscience (Schneidman et al., 2001) , and Natural Language Processing (Li & Eisner, 2019) . Due to the notorious difficulty in estimating mutual information in high dimension, variational approximations to the IB have been suggested and applied also to Deep Learning (Alemi et al., 2016; Parbhoo et al., 2018) .

For large scale learning, when almost all input patterns can be considered typical in the information theoretic sense (Cover & Thomas, 2006) , the cardinality of the typical inputs is characterized by the pattern's entropy, H(X) =x p(x) log p(x). Under similar typicality assumption, the mutual information (MI) of the encoder, I(X; X) = x,x p(x, x) log p(x|x) p(x) characterizes the cardinality of the typical representations, X. On the other hand, the mutual information of the Bayes optimal decoder, I(Y; X) = y,x p(y, x) log p(y|x) p(y) , is equivalent to the cross-entropy generalization error. The IB trade off between the encoder and decoder mutual information values is defined by the minimization of the Lagrangian:

EQUATION

independently over the convex sets of the normalized distributions, {p β (x | x)}, {p β (x)} and {p β (y | x)}, given a positive Lagrange multiplier β. As shown in (Tishby et al., 1999; Shamir et al., 2010) , this is a natural generalization of the classical concept of Minimal Sufficient Statistics (Cover & Thomas, 2006) , where the estimated parameter is replaced by the output variable Y and exact statistical sufficiency is characterized by the mutual information equality: I( X; Y) = I(X; Y). The minimality of the statistics is captured by the minimization of I(X; X), due to the Data Processing Inequality (DPI). However, non-trivial minimal sufficient statistics only exist for very special parametric distributions known as exponential families (Brown, 1986) . Thus in general, the IB relaxes the minimal sufficiency problem to a continuous family of representations X which are characterized by the trade off between compression, I(X; X) ≡ I X , and accuracy, I(Y; X) ≡ I Y , along a convex line in the Information-Plane (I Y vs. I X ). When the rule p(x, y) is strictly stochastic, the convex optimal line is smooth and each point along the line is uniquely characterized by the value of β. We can then consider the optimal representations x = x(β) as encoder-decoder pairs: (p β (x|x), p β (y|x))2 a point in the continuous manifold defined by the Cartesian product of these distribution simplexes.

We also consider a small variation of these representations, δx, as an infinitesimal change in this (encoder-decoder) continuous manifold (not necessarily on the optimal line(s)).

1.2. IB AND RATE-DISTORTION THEORY:

The IB optimization trade off can be considered as a generalized rate-distortion problem (Cover & Thomas, 2006) with the distortion function between a data point, x and a representation point x taken as the KL-divergence between their predictions of the desired label y:

EQUATION

The expected distortion E p β (x,x) [d IB (x, x)] for the optimal decoder is simply the label-information loss: I(X; Y) -I( X; Y), using the Markov chain condition. Thus minimizing the expected IB distortion is equivalent to maximizing I( X; Y), or minimizing equation 1. Minimizing this distortion is equivalent to minimizing the log-loss or the cross-entropy loss, as done in most deep learning applications, and it upper-bounds other loss functions such as the L 1 -loss (due to the Pinsker inequality, or (Painsky & Wornell, 2018) ). The Pinsker inequality shows that both orders of the cross-entropy upper bound to the L 1 -loss, or total-variation distance, min{D[q||p], D[p||q]} ≥ 1 2 log 2 pq 2 1 .

1.3. THE IB EQUATIONS:

For discrete X and Y, a necessary condition for the IB (local) minimization is given by the three self-consistent equations for the optimal encoder-decoder pairs, known as the IB equations:

EQUATION

where Z(x; β) is the normalization function. Iterating these equations is a generalized, Blahut-Arimoto, alternating projection algorithm (Tusnady & Csiszar, 1984; Cover & Thomas, 2006) and it converges to a stationary point of the Lagrangian, equation 1 (Tishby et al., 1999) . Notice that the minimizing decoder, (equation 3-(iii)), is precisely the Bayes optimal decoder for the representation x(β), given the Markov chain conditions.

1.4. CRITICAL POINTS AND CRITICAL SLOWING DOWN:

One of the most interesting aspects of the IB equations is the existence of critical points along the optimal line of solutions in the Information-Plane (i.e. the information curve). At these points the representations change topology and cardinality (number of clusters) (Zaslavsky & Tishby, 2019; Parker et al., 2003) and they form the skeleton of the information curve and representation space.

Under the strict stochastic assumption, the information-curve is a smooth function of the Lagrange multiplier β, but its derivative may not be smooth. Critical points are bifurcations of the solutions, which are values of β for which two different solutions (representations) co-exist. To identify such points we perform a perturbation analysis of the IB equations, as in (Zaslavsky & Tishby, 2019) .

Taking a small perturbation of the representation, denoted for brevity by δx, the changes in the log encoder and log decoder that satisfy equation 3 for a given β can be determined through the nonlinear eigenvalues problems3 :

EQUATION

with the two square matrices C defined by:

C IB xx (x, β) = y p(y | x) p β (x | x) p β (y | x) p(y | x ) , C IB yy (x, β) = x p(y | x) p β (x | x) p β (y | x) p(y | x). (5)

As shown in (Zaslavsky & Tishby, 2019) , these two matrices have the same eigenvalues and have non-trivial eigenvectors (i.e., different co-existing optimal representations) precisely at the critical values of β, the bifurcation points of the IB solution. At these points the cardinality of the representation X (the number of "IB-clusters") changes due to splits of clusters, resulting in topological phase transitions in the encoder. These critical points form the "skeleton" of the topology of the optimal representations. Between critical points the optimal representations change continuously (with β).

The important computational consequence of critical points is known as critical slowing down (Tredicce et al., 2004) . For binary Y, near a critical point the convergence time, τ β , of the iterations of equation 3 scales like:

τ β ∼ 1/(1 -βλ 2 )

, where λ 2 is the second eigenvalue of either C IB yy or C IB xx . At criticality, λ 2 (x) = β -1 and the number of iterations diverges. This phenomenon dominates any local minimization of equation 3 which is based on alternate encoder-decoder optimization.

To illustrate the importance of the critical points and the critical slowing-down we consider a lowdimensional problem that is easy to visualize. Taking the joint distribution, p(y, x) with a binary Y and only 5 possible inputs. For a given β, the Blahut-Arimoto iterations converge to a stationary solutions of the IB equations, which amounts to discrete points in the interval [0, 1] -the simplex of the p(y) distributions -for each value of the Lagrange multiplier, β.

The evolution of the optimal decoder, p β (y = 0 | x), ∀x ∈ X, as a function of β, is a bifurcation diagram (Figure 1(a) ). The critical points of the IB equations correspond to bifurcations in the decoders' graph. At these critical points the non-trivial eigenvalues of C IB yy (β) cross the β -1 value (Figure 1(b) ), and the number of iterations diverges (critical slowing down) (Figure 1(c) ).

1.5. DRAWBACKS OF THE IB:

The main theoretical and practical drawback of the IB is it's apparent reliance on the explicit knowledge of the joint distribution p(x, y). In the context of representation learning this is often considered a major flaw, as we are always given only a sample from the distribution. While the generalization properties of the finite sample IB representations have been studied in the past (Shamir et al., 2010) , the main problem remains the extension of the encoder, p(x | x), when trained from a small sample, to new unobserved patterns x ∈ X. The standard approach in representation learning is to assume (at least implicitly) the existence of features of x with their topology, or a specific parametric form for the encoder. The original IB is completely non-parametric and does not assume any topology on the input space, beyond label similarity. A related drawback of the IB is it's poor scalability with the size of the pattern-space X, which makes the reliable estimation of the encoder mutual information impractical for large learning problems. 

1.6. CONTRIBUTIONS OF THIS WORK:

Our main contribution is by providing a general formal framework resolving the encoder extension drawback of the IB. While the use of specific features and variational approximations to the IB are not new, here we take a different approach assuming that p(y | x) can be approximated by exponential families. This defines a new rate-distortion problem, the Dual Infromation Bottleneck (dualIB).

We show that the new dualIB formulation preserves the sufficient statistics of the original distribution for all values of the trade off parameter, β. A desired property upon predictions of a parametrized distribution. Furthermore, it obtains a significant improvement of the finite sample label prediction. We demonstrate numerically that the dualIB encoder-decoder pairs improve the prediction of unseen labels when trained from small samples, compared to the original IB. We also discuss in detail the critical points of the new formulation and their relation to those of the original IB. Interestingly, as we elaborate in the following sections, all these desirable properties are achieved by merely switching the order of the arguments in the KL-divergence of the IB distortion.

The remainder of the paper is organized as follows. We present and solve the dualIB problem in §2. We discuss the dualIB's critical points in §2.1 and prove a general relation between the critical points of the dual and original IB in §2.2. In particular, we show that the dual critical points give the best approximation to the original IB information curve. In §3 we discuss the dualIB for exponential families, dualExpIB, and demonstrate the advantages of our framework in this case. We also demonstrate numerically the improvement in the label prediction of the dualIB when trained from a small sample. We conclude in §4 with further extensions and possible applications.

2. THE DUALIB: MAXIMIZING THE PREDICTION INFORMATION:

Supervised learning is generally separated into two phases: the training phase, where the internal representations are formed from the training data, and the prediction phase, where these representations are used to predict labels of new input patterns. We add to our Markov chain another variable, Ŷ, the predicted label which obtains the same values as Y, but distributed differently:

EQUATION

The left-hand part of this chain describes the representation training, and the right-hand part is the Maximum Likelihood (ML) prediction using these representations (Slonim et al., 2006) . So far the prediction variable Ŷ has not been part of the IB optimization problem. It has been implicitly assumed that the Bayes optimal decoder, p β (y | x), which minimizes the IB distortion at a given β, is also the best choice for making predictions of Ŷ from the representation Xβ through the righthand Markov chain. That is, denoting p β (ŷ | x) ≡ p β (y | x) the ML decoder is the mixture over the internal representations:

EQUATION

This, however, is not necessarily optimal when the encoder and decoder are trained from finite samples (Shamir et al., 2010) , or when the decoder is not Bayes optimal. We define the dualIB distortion by merely switching the order of the arguments in the KL-divergence of the original IB distortion, namely:

EQUATION

which in geometric terms is known as the dual distortion problem (Felice & Ay, 2019) .

That is, given the "input" random variable X (input patterns), the "output" random variable Y (desired label) and the "representation" X, the ML optimal "predicted label" Ŷ is given by the mixture distribution, equation 7. 4The dualIB optimization can be written as the following rate-distortion problem:

EQUATION

with the average distortion given in terms of mutual information on Ŷ, I( X; Ŷ) and I(X; Ŷ): Both terms, (a) and (b), vanish precisely when X is a sufficient statistic for X with respect to Ŷ, since we can then reverse the order of X and X in the Markov chain (equation 6). This replaces the roles of Y and Ŷ as the variable for which Xβ are approximately minimally sufficient statistics.

EQUATION

In that sense the dualIB shifts the emphasis from the training phase to the prediction phase. This implies that minimizing the dualIB functional maximizes the mutual information between Y and Ŷ, I(Y; Ŷ), as well as the mutual information I(X; Ŷ). This is illustrated in figure 4(b)-c .

The next theorem states the form of the solutions of the Dual Information Bottleneck:

Theorem 1. The minima of equation 9, can be obtained by generalized Blahut-Arimoto iterations between the encoder and the decoder as in the original IB, with the following modifications: (i) Replace the distortion by its dual in the encoder update; (ii) Update the decoder by the encoder's "geometric" mean of the data distributions p(y | x).

The proof is given in §A.2.

The alternating projections between the encoder and decoder, which converge to a solution of the dualIB at a given value of the Lagrange multiplier β, are implemented by the following iterative algorithm5 :

Algorithm 1 dualIB iterative algorithm 1: while p t+1 β (y | x) -p t β (y | x) > do 2: Z t+1 x|x (x; β) = x p t β (x)e -βD[p t β (y|x) p(y|x)]

3:

p t+1 β (x | x) = p t β (x) Z t+1 x|x (x;β) e -βD[p t β (y|x) p(y|x)] 4: p t+1 β (x) = x p t+1 β (x | x)p(x) 5: Z t+1 y|x (x; β) = y e x p t+1 β (x|x) log p(y|x)

6:

p t+1 β (y | x) = 1 Z y|x (x;β) e x p t+1 β (x|x) log p(y|x) 7: return p β (x), p β (x | x), p β (y | x)

Here the Z's are standard normalization factors (partition functions).

As in the IB, the encoder update (row 3) and decoder update (row 6) are the core of the algorithm.

Figure 2 illustrates the behavior of the dualIB algorithm for the same distribution as in Figure 1 . The overall behavior is very similar, but the critical points (representation splits) slightly change their location. In the following sections we provide a detailed analysis and comparison between the two frameworks. 

2.1. THE CRITICAL POINTS OF THE dualIB:

As discussed in §1.4 the skeleton of the IB optimal bound (the information curve) is constituted by the critical points in which the topology (cardinality) of the representation changes. A similar stability analysis of the dualIB equations reveals similar conditions for the critical points. Theorem 2. The dualIB critical points are detected by non-trivial solutions of the nonlinear eigenvalue problem:

EQUATION

)

with the matrices C dualIB given by:

EQUATION

)

The proof to theorem 2 is given in §A.3. The proof of lemma 3 given in section §A.3.1.

As in the IB, at the critical points, β dualIB c , the partial derivatives of the encoder and decoder with respect to β, ∂ log p β (x | x)/∂β, ∂ log p β (y | x)/∂β, have multiple (at least two) values. This results in discontinuities (cusps) in the encoder and decoder mutual information values as functions of β along the optimal line, with an undefined second derivative.

2.2. THE INFORMATION PLANE OF THE dualIB:

The Information Plane, I X = I( X; X) vs. I Y = I( X; Y), is the standard visualization of the compression-prediction trade off of the IB. It can be defined for any encoder once the decoder is the Bayes optimal (equation 3-(iii)), for which the I Y is the actual information of the representation on the desired label (Tishby et al., 1999) .

Comparing the dualIB information curve to the IB curve shows the quality of this approximation. Figure 3 (a) depicts this comparison. While we know that I IB Y (β) is always higher, the two curves are almost indistinguishable. To better understand the relationship between these two curves, we look at the values of I X and I Y as functions of the corresponding β (Figure 3(b), (c) ). The important role of the critical points is revealed as the corresponding cusps along these curves. As we argue below, the IB information values are strictly below those of the dualIB, but the distance between them is minimized precisely at the dual critical points. Proof. The proof follows from lemmas 4 and 5, together with the critical points analysis above, and is only sketched here. As the encoder and decoder at the critical points, β IB c and β dualIB c , have different left and right derivatives, they form cusps in the curves of the mutual information (I X and I Y ) as functions of β. These cusps can only be consistent with the optimality of the IB curves if β dualIB c < β IB c (this is true for any sub-optimal distortion), otherwise the curves intersect. Moreover, at the dualIB critical points, the distance between the curves is minimized due to the strict concavity of the functions segments between the critical points. As the critical points imply discontinuity in the derivative, this results in a "jump" in the information values. Therefore, at any β dualIB c the distance between the curves has a (local) minimum. This is depicted in Figure 3 , comparing I X (β) and I Y (β) and their differences for the two algorithms.

The two curves approach each other for large β since the two distortion functions become close in the low distortion limit (as long as p(y | x) is bounded away from 0).

3. THE EXPONENTIAL FAMILY dualIB:

As discussed in §1, one of the major drawbacks of the IB is the extension of the decoder inputs from an empirical sample to new unseen patterns. To address this issue we can assume the existence of features, or statistics of the pattern, A r (x), which are sufficient or approximately sufficient for the prediction of the label Y. That is, we consider the rule's distribution, p(y | x), to be an exponential family with these features. Exponential families form the elegant theoretical core of parametric statistics and often emerge as maximum entropy (Jaynes, 1957) or stochastic equilibrium distributions, subject to observed expectation constraints. They also form the class of parametric distributions for which exact, finite dimensional and additive, Minimal Sufficient Statistics exist (Kullback, 1959) . Such distributions should also best match the rational behind the IB as extracting approximate sufficient statistics.

A key property of exponential families is their invariance under geometric averages. For this technical reason the dualIB encoder and decoder preserve the exponential form of the original data distribution for all values of β. Furthermore, the new (assumed limited to a finite dimension d) set of features/statistics are precisely the empirical expectations of these features. These d empirical averages are the only numbers needed for predicting the label at the required accuracy, hence their advantage in reducing the encoder's computational complexity.

Assuming that the rule distribution is of the form:

EQUATION

where A r (x) are d linearly independent functions of the input x and λ r (y) are functions of the label y, or the parameters of this exponential family. The λ(y) can also be considered Lagrange multipliers associated with the constraints conditional expectations E p(x|y) [A r (x)] in entropy maximization. The normalization factors, Z y|x (x), are written, for brevity, as λ 0 x ≡ log( y d r=1 e -λ r (y)Ar(x) ) with A 0 (x) ≡ 1. We do not constrain the marginal p(x).

The important fact about the exponential form is that all the mutual information, I(X; Y), is fully captured by the d conditional expectations, E p(x|y) [A r (x)], since these are the (minimal) sufficient statistics for the parameters. This means that all the relevant information (in the training sample) is captured solely by d-dimensional empirical expectations. This can lead to a huge reduction in computational complexity (from dim(X) to d).

We next show that for the dualIB, this dimension reduction is preserved or improved along the dual information curve, for all values of β.

Theorem 7. (dualExpIB) For data from an exponential family, equation 13, the optimal decoder of the dualIB, at a given β, is given by:

EQUATION

)

and the respective encoder:

EQUATION

with the constraints and multipliers expectations,

EQUATION

)

The complete derivations for this section are given in §A.5.

This defines a simplified iterative algorithm to solve the dualExpIB problem, since we can replace the decoders' update rule at each iteration in the dualIB algorithm (Algorithm 1, row 6) with the simplified expression given in equation 14.

As a concrete illustration to the performance of the dualExpIB we examine a problem in which the rule distribution is given by an exponential family, p(y | x) ∼ N (0, a + b|sin(cπx)|), as in Globerson & Tishby (2003) . Setting the constants a, b, c we produce a sample S (of size N = 1000) on which we calculate the empirical distribution, p(y | x) and the empirical sufficient statistics Âr (x). Given the assumption on the rule we assess the exponential form empirical distribution, pexp (y | x; Âr (x)). We then evaluate the IB on both empirical distributions, p and pexp , and compare it to the dualExpIB given Âr (x), λ r (y)6 .

The comparison between the IB and the dualExpIB, is given in Figure 4 (a) as function of the continuous ŷ for a fixed x. It can be seen that the dualExpIB better captures the structure of the original data and is much less affected by the sampling noise. Next, we consider the Information Plane with respect to Ŷ, where the expected maximization by the dualExpIB is observed, Figure 4 (b). To evaluate the prediction ability of the dualExpIB we consider the L 1 -expected loss with respect to the original distribution. Looking at Figure 4 (c) it is apparent that for all values of the trade off parameter, β, the dualExpIB minimizes the loss providing the superiority in prediction. 

4. CONCLUSION:

We presented here the Dual Information Bottleneck (dualIB), a framework to preform the Information Bottleneck (IB) compression in a parametric setting. We have shown that the dualIB has several interesting properties: (i) it provides a good approximation to the original IB while using the low relevant dimensions of the original data. This can significantly reduce the complexity of finding good IB representations; (ii) it optimizes the information between the representation and the predicted label rather than the desired label as in the original IB. As we have shown, this can improve the generalization error when trained on small samples since the predicted label is the one used in practice; (iii) It preserves the exponential form of data from exponential families, while reducing the dimensionality of the compressed representations. This important property was known to be satisfied by the Gaussian IB (Chechik et al., 2005) but not known for other distributions. The Gaussian case is self-dual in that sense. Generalizing this property to other exponential families was an open problem for many years; (iv) The exponential form of the optimal encoder-decoder pairs allows for the application to distributions with special symmetries, which can be naturally expressed in this form.

We conclude that the exponential Dual Information Bottleneck (dualExpIB) framework allows us now to approach problems previously considered intractable by the IB. Furthermore, it may allow better predictions to IB applications using finite samples or data with low internal dimensionality or special symmetries.

A APPENDIX A.1 DUALIB MATHEMATICAL FORMULATION:

As presented in §1.6 the dualIB is solved with respect to the full Markov chain (equation 6) in which we introduce the new variable, Ŷ, the predicted label. Thus, in analogy to the IB we want to write the optimization problem in term of Ŷ.

Developing the expected distortion we find:

E p β (x,x) [d dualIB (x, x)] = x,x p β (x, x) ŷ p β (ŷ | x) log p β (ŷ | x) p(ŷ | x) = x,ŷ p β (x)p β (ŷ | x) log p β (ŷ | x) p β (ŷ) - x,ŷ p(x)p β (ŷ | x) log p β (ŷ | x) p β (ŷ) + x,ŷ p(x)p β (ŷ | x) log p β (ŷ | x) p(ŷ | x) = I( X; Ŷ) -I(X; Ŷ) + E p(x) [D[p β (ŷ | x) p(ŷ | x)]].

Allowing the dual optimization problem to be written as:

F * [p(x | x); p(x); p(y | x)] = I(X; X) -β I(X; Ŷ) -I( X; Ŷ) -E p(x) [D[p β (ŷ | x) p(ŷ | x)]] .

A.2 THE DUALIB SOLUTIONS:

To prove theorem 1 we want to obtain the normalized distributions minimizing the dualIB ratedistortion problem.

Proof. (i) Given that the problem is formulated as a rate-distortion problem the encoder's update rule must be the known minimizer of the distortion function (Cover & Thomas, 2006) . Thus the IB encoder with the dual distortion is plugged in. (ii) For the decoder, by considering a small perturbation in the distortion d dualIB (x, x), with α(x) the normalization Lagrange multiplier, we obtain:

δd dualIB (x, x) = δ y p β (y | x) log p β (y | x) p(y | x) + α(x) y p β (y | x) -1 δd dualIB (x, x) δp β (y | x) = log p β (y | x) p(y | x) + 1 + α(x).

Hence, minimizing the expected distortion becomes:

0 = x p β (x | x) log p β (y | x) p(y | x) + 1 + α(x) = log p β (y | x) - x p β (x | x) log p(y | x) + 1 + α(x),

which yields Algorithm 1, row 6.

Considering the dualIB encoder-decoder, Algorithm 1, we find that E p β (x,x) [d dualIB (x, x)] reduces to the expectation of the decoder's log partition function:

E p β (x,x) [d dualIB (x, x)] = x,x p β (x, x) y p β (y | x) log p β (y | x) p(y | x) = -E p β (x) log Z y|x (x; β) + x,y p β (x) x p β (x | x) log p(y | x ) - x p β (x | x) log p(y | x)

= -E p β (x) log Z y|x (x; β) .

A.3 STABILITY ANALYSIS:

Here we provide the detailed stability analysis allowing the definition of the matrices C dualIB xx , C dualIB yy (equation 12) and which allows us to claim that they obey the same rules as the C matrices (equation 5) in equation 4. Considering a variation in x we get:

EQUATION

EQUATION

Substituting equation 18 into equation 17 and vice versa one obtains:

∂ log p β (x | x) ∂x = β x ,y,ỹ,x p β (y | x)p β (x | x) log p(y | x) p(y | x) • p β (x | x)p β (ỹ | x) log p(y | x ) p(ỹ | x ) ∂ log p β (x | x) ∂x ∂ log p β (y | x) ∂x = β x,y ,x,ỹ p β (x | x)p β (ỹ | x) log p(y | x) p(ỹ | x) • p β (y | x)p β (x | x) log p(y | x) p(y | x) ∂ log p β (y | x) ∂x .

We now define the C dualIB matrices as follows:

C dualIB xx (x; β) = y,ỹ,x p β (y | x)p β (x | x) log p(y | x) p(y | x) • p β (x | x)p β (ỹ | x) log p(y | x ) p(ỹ | x ) C dualIB yy (x; β) = x,x,ỹ p β (x | x)p β (ỹ | x) log p(y | x) p(ỹ | x) • p β (y | x)p β (x | x) log p(y | x) p(y | x) .

Using the above definition we have an equivalence to equation 4 in the form of:

I -βC dualIB xx (x, β) ∂ log p β (x | x) ∂x = 0 , I -βC dualIB yy (x, β) ∂ log p β (y | x) ∂x = 0.

Note that for the binary case, the matrices may be simplified to:

C dualIB xx (x; β) = y,x p β (y | x)p β (x | x) log p(y | x) p(y | x) • p β (x | x)(1 -p β (y | x)) log p(y | x ) 1 -p(y | x ) C dualIB yy (x; β) = x,x p β (x | x)(1 -p β (y | x)) log p(y | x) 1 -p(y | x) • p β (y | x)p β (x | x) log p(y | x) p(y | x) . A.3.1 PROOF OF LEMMA 3

We show that the C dualIB matrices share the same eigenvalues with λ 1 (x) = 0.

Proof. The matrices, C dualIB xx (x; β), C dualIB yy (x; β), are given by:

C dualIB xx (x; β) = A xy (x; β)B yx (x; β) , C dualIB yy (x; β) = B yx (x; β)A xy (x; β),

with:

A xy (x; β) = p β (y | x) x p β (x | x) log p(y | x) p(y | x) , B yx (x; β) = p β (x | x) ỹ p β (ỹ | x) log p(y | x) p(ỹ | x) .

Given that the matrices are obtained by the multiplication of the same matrices, it follows that they have the same eigenvalues {λ i (x; β)}.

To prove that λ 1 (x; β) = 0 we show that det(C dualIB yy ) = 0. We present the exact calculation for a binary label Y ∈ {y 0 , y 1 } (the argument for general Y follows by encoding the label as a sequence of bits and discussing the first bit only, as a binary case):

det(C dualIB yy (x; β)) = x,x p β (x | x)p β (y 1 | x) log p(y 0 | x) p(y 1 | x) • p β (y 0 | x)p β (x | x) log p(y 0 | x) p(y 0 | x) • x ,x , p β (x | x)p β (y 0 | x) log p(y 1 | x ) p(y 0 | x ) • p β (y 1 | x)p β x | x log p(y 1 | x ) p y 1 | x - x,x p β (x | x)p β (y 0 | x) log p(y 1 | x) p(y 0 | x) • p β (y 0 | x)p β (x | x) log p(y 0 | x) p(y 0 | x) • x ,x p β (x | x)p β (y 1 | x) log p(y 0 | x ) p(y 1 | x ) • p β (y 1 | x)p β x | x log p(y 1 | x ) p y 1 | x = x,x ,x,x p β (x | x)p β (x | x)p 2 β (y 0 | x)p 2 β (y 1 | x)p β (x | x) log p(y 0 | x) p(y 0 | x) p β x | x log p(y 1 | x ) p y 1 | x • log p(y 0 | x) p(y 1 | x) log p(y 1 | x ) p(y 0 | x ) -log p(y 0 | x) p(y 1 | x) log p(y 1 | x ) p(y 0 | x ) = 0.

Given that the determinant is 0 implies that λ 1 (x) = 0.

For a binary problem we can describe the non-zero eigenvalue using λ 2 (x) = Tr(C dualIB yy (x; β)). That is:

λ 2 (x) = x,x p β (x | x)p β (y 1 | x) log p(y 0 | x) p(y 1 | x) • p β (y 0 | x)p β (x | x) log p(y 0 | x) p(y 0 | x) + x,x p β (x | x)p β (y 0 | x) log p(y 1 | x) p(y 0 | x) • p β (y 1 | x)p β (x | x) log p(y 1 | x) p(y 1 | x) =p β (y 1 | x)p β (y 0 | x) x,x p β (x | x)p β (x | x) log p(y 0 | x) p(y 1 | x) log p(y 0 | x) p(y 0 | x) -log p(y 1 | x) p(y 1 | x) .

A.4 INFORMATION PLANE ANALYSIS:

We rely on known results for the rate-distortion problem and the information plane:

Lemma 8. I(X; X) is a non-increasing convex function of the distortion E p β (x,x) [d(x, x) ] with a slope of -β.

We emphasis that this is a general result of rate-distortion thus holds for the dualIB as well.

Lemma 9. For a fixed encoder p β (x | x) and the Bayes optimal decoder p β (y | x):

E[d IB (x, x)] = I(X; Y) -I( X; Y).

Thus, the information curve, I Y vs. I X , is a non-decreasing concave function with a positive slope, β -1 . The concavity implies that β increases along the curve. (Cover & Thomas, 2006; Gilad-bachrach et al., 2003) .

A.4.1 PROOF OF LEMMA 4

In the following section we provide a proof to lemma 4, for the IB and dualIB problems.

Proof. We want to analyze the behavior of I X (β), I Y (β), that is the change in each term as a function of the corresponding β. From lemma 9, the concavity of the information curve, we can deduce that both are non-decreasing functions of β. As the two β derivatives are proportional it's enough to discuss the first one.

Next, we focus on their behavior between two critical points. That is, where the cardinality of X is fixed (clusters are "static"). For "static" clusters, the β derivative of I X , along the optimal line is given by: ∂I(X; X) .

This first of all reassures that the function is non-decreasing as Var(d(x)) ≥ 0.

The piece-wise concavity follows from the fact that when the number of clusters is fixed (between the critical points) -increasing β decreases the clusters conditional entropy H( X | X), as the encoder becomes more deterministic. The mutual information is bounded by H( X) and it's β derivative decreases. Further, between the critical points there are no sign changes in the second β derivative.

A.4.2 PROOF OF LEMMA 5

Proof. The information curve has a positive slope, β -1 , with β increasing along it, lemma 9. That is, given a value of β, there exists a pair I IB Y (β), I IB X (β) such that ∂I IB Y (β)/∂I IB X (β) = β -1 . Now, consider a sub-optimal information curve, I * Y , I * X . There exist values β , β such that:

I * X (β ) = I IB X (β) , I * Y (β ) = I IB Y (β).

The optimality of the IB implies that sub-optimal curves lie below it; i.e, the IB slope is steeper:

β -1 > β -1 , β -1 > β -1 .

Thus, given that β increases along the information curve, it holds that: 

EQUATION

A.5 DERIVATION OF THE DUALEXPIB:

We provide elaborate derivations to theorem 7; that is, we obtain the dualIB optimal encoder-decoder under the exponential assumption over the data. We use the notations defined in §3.

• The decoder, equation 14.

Substituting the exponential assumption into the dualIB log-decoder yields: From which it follows that λ 0 β (x) is given by: • The encoder, equation 15.

λ 0 β (x) = log

The core of the encoder is the dual distortion function which may now be written as: 

:

This may seem like a limitation of the method, but it can be shown that in the deterministic limit the IB is well defined. This stochastic assumption simplifies the analysis but does not pose any real limitation.

Here we use the inverse encoder, which is in the fixed dimension simplex of distributions over X.

We ignore here the interactions between the representations, for simplicity.

We use the notation p(ŷ | x) ≡ p(y | x), when there is no β subscript.

Unless stated otherwise, log = ln ≡ log e

λ r (y) are defined by the specific exponential family.

Figures and Tables:

Figure 1: Example of the evolution of the IB decoder with growing β. (a) The bifurcation diagram; each color corresponds to one component of the representation x ∈ X and depicts the decoder p β (y = 0 | x), in the simplex [0, 1]. The black dots correspond to the input distribution p(y = 0 | x). (b) The second eigenvalue of C yy (x; β), λ 2 (x), along with β -1 as a function of β. (c) Convergence time of the algorithm as a function of β.

This is similar to the known IB relation: E p(x,x) [d IB (x, x)] = I(Y; X) -I(Y; X) with an extra positive term (b).

Figure 2: Same as Figure 1 for the dualIB solutions with the C dualIB yy matrix. (a) The representations bifurcate at the critical values of β. (b) Critical points appear when an eigenvalue (color) crosses the β -1 (black) line. (c) Near these points there is critical slowing down and the numbers of iterations of Algorithm 1 diverge.

The matrices C dualIB xx (x; β), C dualIB yy (x; β) have the same eigenvalues {λ i }, with λ 1 (x) = 0. With binary Y, the critical points are obtained at λ 2 (x) = β -1 .

Figure 3: The IB's and dualIB's Information Plane. (a) I Y vs. I X for the two algorithms. The black dots are the dualIB critical points, β dualIB c , and the grey triangles are the IB critical points, β IB c . The corresponding distortion functions are shown in the inset. (b) The functions I IB X (β) and I dualIB X (β). Both curves are monotonic and concave between the critical points. The inset indicates the relative difference between the curves, where the alternating order of the critical points is clearly observed. (c) Similarly, I IB Y (β) and I dualIB Y (β) are monotonic and piece-wise concave.The relative discrepancy between the information curves is clearly minimized at the dualIB critical points (inset). The functions approach each other for large β.

I X (β) and I Y (β), along the optimal lines, are non-decreasing piece-wise concave, functions of β. When their second derivative (with respect to β) is defined, it is strictly negative. Lemma 5. For any sub-optimal information curve (I X , I Y ),I IB X (β) ≤ I X (β) and I IB Y (β) ≤ I Y (β), for all values of β.Proofs of the above are given in §A.4.The information plane properties are summarized by the following theorem. Theorem 6. (i) The critical points of the two algorithms alternate: for each critical point,β dualIB c ≤ β IB c .(ii)  The distance between the two information curves is minimized precisely at the dualIB critical points β dualIB c . (iii) The two curves approach each other as β → ∞.

Figure 4: The IB's and dualExpIB's behavior over data sampled from p(y | x) ∼ N (0, a + b| sin(cπx)|) and p(x) ∼ U(-1, 1). (a) The decoder p β (ŷ | x) as a function of ŷ for some x ∈ (-1, 1) at log 2 (β) = 4. (b) The Information Plane with respect to Ŷ, I(Y; Ŷ) vs. I(X; X). (c) The L 1 -expected loss, E p(x) [ p(ŷ | x)p β (ŷ | x) ], as a function of the trade off parameter β.

p β (x, x) log Z x|x (x; β) + βd(x, x)   = -β d(x, x) ∂ log p β (x | x) ∂β p β (x,x) ≈ β d(x, x) ∂ log Z x|x (x; β) ∂β + d(x, x) p β (x,x) ≈ β d 2 (x, x) p β (x|x)d(x, x)

β) > I * X (β ) = I IB X (β) , I * Y (β) > I * Y (β ) = I IB Y (β).

log p β (y | x) = x p β (x | x) log p(y | x)log Z y|x (x; β) x | x)λ r (y)A r (x)log Z y|x (x; β) y)A r,β (x) -E p β (x|x) λ 0 xlog Z y|x (x; β).Taking a closer look at the normalization term:Z y|x (x; β) = y e x p β (x|x) log p(y|x) = e -E p β (x|x) [λ 0 x ] y e -d r=1 λ r (y)A r,β (x) log Z y|x (x; β) = -E p β (x|x) λ 0x + log y e -d r=1 λ r (y)A r,β (x) .

λ r (y)A r,β (x) , and we can conclude that the dualExpIB decoder takes the form:log p β (y | x) = -d r=0λ r (y)A r,β (x).

dualIB (x, x) = y p β (y | x) log p β (y | x) p(y | x) (A r (x) -A r,β (x)),substituting this into the encoder's definition we obtain:p β (x | x) = p β (x) Z x|x (x; β) e -β[λ 0 x -λ 0 β (x)+ d r=1 λ r β (x)[Ar(x)-A r,β (x)]] = p β (x)e βλ 0 β (x) Z x|x (x; β) e -β d r=1 λ r β (x)[Ar(x)-A r,β (x)] .

Peer review (iclr2020):
Description: The information bottleneck (IB) is an information theoretic principle for optimizing a mapping (encoding, e.g. clustering) of an input, to trade off two kinds of mutual information: minimize mutual information between the original input and the mapped version (to compress the input), and maximize mutual information between the mapped input and an output variable. It is related to a minimization of an (expected) Kullback-Leibler divergence betwen conditional distributions of an output variable. In this paper, instead of the original IB, authors consider a previously presented dual problem of Felice and Ay, where the Kullback-Leibler divergence is minimized in the reverse direction: from the conditional distribution of output given encoding, p(y|hat x), to the conditional distribution given the original input, p(y|x). The *dual problem* itself has a more complicated form than the original IB, authors claim this is *a good approximation* of the original bottleneck formulation, and aim to prove various *interesting properties* of it. - An iterative algorithm (Algorithm 1) similar to the original IB algorithm but with a few more steps is provided. - A theorem about critical points where cardinality of the representation changes is given, similar to the IB critical points, and another theorem about difference of curves on an information plane between the IB and dual-IB solutions. - Authors also show that if the true conditional distribution of outputs given inputs has an exponential-family form, the dual-IB decoder also has a form in the same family, which is said to reduce computational complexity of the algorithm. Evaluation: This is an entirely theory-based paper; although an algorithm is given, it is not instantiated for any concrete representation learning task, and no experiments at all are demonstrated. Overall, I feel the motivation is not clear and strong enough. The abstract does not illustrate the importance of the mentioned *interesting properties* well enough for concrete tasks. Reading the paper, the clearest motivations seem to be improving computational complexity, and having a clearer connection to output prediction in cases where the predictor may be sub-optimal. However, authors do not quantify these well: - The computational complexity improvement is not made clear (quantified) in a concrete IB optimization task: it seems it is only for exponential families, and even for them only affects one part of the algorithm, reducing its complexity from dim(X) to d; the impact of this is not tried out in any experiment. - For output prediction, authors motivate that dual-IB could have a more direct connection e.g. *due to finite sample, in which it can be very different from the one obtained from the full distribution*). Authors further claim that the dual-IB formulation can *improve the generalization error when trained on small samples since the predicted label is the one used in practice*. However, this is not tested at all: no prediction experiments, no quantification of generalization error, and no comparisons are done, thus the impact of the clearer connection to output prediction is not tested at all, and no clear theorems are given about it either. The property that the algorithm *preserves exponential form of the original data distribution, if one exists* is interesting in principle, but it is unclear if any real data would anyway precisely have such a distribution; what happens if the data is not exactly in an exponential family? In its current state the paper, although based on an interesting direction, in my opinion does not make a sufficient impact to be accepted to ICLR. Other comments: *Application to deep learning* mentioned in Section 1.5 is only a sincle sentence in the conclusions. There have been some other suggested alternative IB formulations, for example the Deterministic IB of Strouse and Schwab (Neural Computation 2017) which also claim improved computational efficiency. How does the method compare to those? Section 1.5 claims the algorithm *preserves the low dimensional sufficient statistics of the data*: it is not clear what *preserves* means here, certainly it seems the decoder in Theorem 7 uses the same kinds of sufficient statistics as in the original data, but it is not clear that hat(x) would somehow preserve the same values of the sufficient statistics.