The Dual Information Bottleneck
Authors: Zoe Piran
Naftali Tishby
Venue:  (2020)
Keywords: optimal prediction learning
exponential families
critical points
information theory

Abstract: The Information-Bottleneck (IB) framework suggests a general characterization of optimal representations in learning, and 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 framework, however, has practical drawbacks, in that mutual information is notoriously difficult to handle at high dimension, and only has closed form solutions in special cases. Further, because it aims to extract representations which are minimal sufficient statistics of the data with respect to the desired label, it does not necessarily optimize the actual prediction of unseen labels. Here we present a  formal dual problem to the IB which has several interesting properties. By switching the order in the KL-divergence between the representation decoder and data, the optimal decoder becomes the geometric rather than the arithmetic mean of the input points. While providing a good approximation to the original IB, it also preserves the form of exponential families, and optimizes the mutual information on the predicted label rather than the desired one. We also analyze the critical points of the dualIB and discuss their importance for the quality of this approach.

Under review as a conference paper at ICLR 2020
THE DUAL INFORMATION BOTTLENECK
Anonymous authors
Paper under double-blind review
ABSTRACT
The Information Bottleneck (IB) framework is general characterization of op- timal representations in large scale learning that suggests an intriguing interpre- tation of efficient representations in deep learning in particular. It is based on the optimal trade off between the representation complexity and accuracy, both which are quantified by mutual information. The problem is solved by alternat- ing projections between the encoder and decoder of the representation, which can be performed locally at each representation level. The non non-parametric IB frame- work, 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 op- timal decoder becomes the geometric rather than the arithmetic mean of the in- put points. This conversion preserves exponential forms of the original distribu- tion 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.
INTRODUCTION
1.1 THE INFORMATION BOTTLENECK METHOD
The Information Bottleneck (IB) method (Tihbyy et al. 1999), is an cnarmatiion-hhoretii frame- work for describing efficient representations of a large scale "input" random variable X (input pat- terns), 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 finite sample from this distribution. In general, we assume that p(y x) is strictly stochastic, and hence bounded away from The representation variable X is in general a stochastic function of X which forms a Markov chain Y + X, and only depends on Y through the input X. We call the map p(8 x) the en- coder 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.
{0, 1 I
The IB has direct successful applications for representation learning in various domains, from vision and speech processing (Ma al. 2019), to neuroscience (Schneidman et al. 2001), and Natural Language Processing (Li & Lisner; 2019). Due to the notorious difficulty in estimating mutual information 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 rypical in the information theoretic sense (Cover & Thomas 2006). the cardinality of the typical inputs is characterized by the pattern's 's entropy, HX) = >x p(x) log pxx). Under similar typicality assumption, the mutual
'This may seem like limitation of the method, but it can be shown that in the deterministic limit the TB is well defined. This stochastic assumption simplifies the analysis but does not pose any real limitation.

---

Under review as a conference paper at ICLR 2020
information (MI) of the encoder, I(X:X) = Ex.ep(x, 8) log p(xi8) characterizes the cardinality of p(x)
the typical representations, X. On the other hand, the mutual information of the Bayes optimal P(y, decoder, X E,, ply, &) log plyR)) equivalent to the cross-entropy generalization error. ply)
The IB trade off between the encoder and decoder mutual information values is defined by the minimization of the Lagrangiam:
Fipa(& (x): x)] = -(x:)) BI(Y;))
(1)
independently over the convex sets of the normalized distributions, {p x) {x) and {pa(y x)), given positive Lagrange multiplier 3. As shown in (Tishby et al. 1999) Shamir et al., 2010), this is natural generalization of the classical concept of Minimal Suffccentt 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) = [X; Y). The minimality of the statistics is captured by the minimization of T(X; X), due to the Data Processing Inequality (DPI). However, non-trivial minimal sufficient statistics only exist for very special para- metric distributions known exponential families (Brown 1986). Thus in general, the IB relaxes the minimal sufficiency problem to continuous family of representations X which are characterized by the trade off between compression, [X; X) Ix. and accuracy, XY Iy, along convex line in the Information-Plant (Iy vs. Tx)- When the rule p(x,y) y) is strictly stochastic, the convex op- timal line is smooth and each point along the line is uniquely characterized by the value of 3. We can then consider the optimal representations & = x(3) as encoder-decoder pairs: (p (x)xx,, (y|x) sy)x){{ I a point in the continuous manifold defined by the Cartesian product of these distribution simplexes. We also consider a small variation of these representations, d8, as an infinitesimal change in this Cencoder-decodest continuous manifold (not necessarily on the optimal line(s)).
1.2
IB AND RATE- DIST--DITTOTION THEORY
The IB optimization trade off can be considered as generalized rate-distortion problem (Cover & Thomas 2006 with the distortion function between a data point, x and representation point taken as the KL-divergence between their predictions of the desired label
p(y x)
dIB(x, x) = Dlp(y xy)]] > p(y x) log
Pa &)
The expected distortion (po(x..)(dmm (x, X)] for the optimal decoder is simply the label-information loss: ((;; - ((: Y). using the Markov chain condition. Thus minimizing the expected IB dis- tortion is equivalent to maximizing / [(;; Y), or minimizing equation Minimizing this distortion is equivalent to minimizing the log-loss or the cross-entropy loss, as done in most deep learning appli- cations, and it upper-bounds other loss functions such as the -lsss (due the Pinsker inequality, or (Painsky & Wornell 2018)). The Pinsker inequality shows that both orders of the cross-entropy upper bound to the L loss, or vataa-vaii distance, min min (D[gll)) D D|pll]]} 2 21og llp qll2.
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:
[ x) p*( BDippyl)s (ps(y())
[xx;3]
(ii)
(x( = Σ. (x x))(x)
(did) pa ()) = E, x)pa(x
where ((x; B) is the normalization function. Iterating these equations is a generalized, Blahut- Arimoto, alternating projection algorithm (Tusnady Csiszar 1984, Cover & Thomas (0066) and it converges to stationary point of the Lagrangian, equation I Tishby al. 1999). Notice that the minimizing decoder, (equation 3 (it)), is preciscly the Bayes optimal decoder for the representation x(3), given the Markov chain conditions.
Here we use the inverse encoder, which in the fixed dimension simplex of distributions X.
2

---

Under review as a conference paper at ICLR 2020
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. )003) and they form the skeleton of the information curve and representation space. Under the strict stochastic assumption, the information curre is a smooth function of the Lagrange multiplier B, but its derivative may not be smooth. Critical points are bifurcations of the solutions, which are values of /3 for which two different solutions (representations) co-exist. To identify such points we perform a perturbation amalysis of the IB equations, as (Zaslavsky & Tishby 2019). Taking small perturbation of the representation, denoted for brevity by ox, the changes in the log encoder and log decoder that satisfy equation for a given 3 can be determined through the nonlinear eigenvalues problem
b log P 8) 00 | 30 (8,3)
Olog DlogPa(y' (s 18) O,
[ - BC 3)
(4)
OR
with the two square matrices C' defined by:
CUB C (K = Σ ply x) Ps R) ply x)), ayp (8, 3) = Erly -
(x 8)
P 8) Ps(y 8) p(y' xx). (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 3. the bifurcation points of the IB solution. At these points the cardinality of the repre- sentation X (the number of "IB-clusters") changes due 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 critical point the convergence time, T3. of the iter- ations of equation 3 scales like: Ta ~ 1/(1 - B22), where X2 is the second eigenvalue of either "yy or CA At criticality, >²(()) = 3- and the number of iterations diverges. This phenomenon dominates any local minimization of equation 3 which based on alternate encoder-decoder opti- CBB
mization.
To illustrate the importance of the critical points and the critical slowing-down we consider a low- dimensional problem that is easy to visualize. Taking the joint distribution, p(y, x) with binary Y and only possible inputs. For a given 3, 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 distributions- - for each value of the Lagrange multiplier, B.
The evolution of the optimal decoder, p3(y = &). VX E X, as a function of B, is a bifurcation diagram (Figure a.). The critical points of the IB equations correspond to bifurcations in the decoders' graph. At these critical points the non-trivial eigenvalues of GBB (3) cross the 3-1 value (Figure bb)), and the number of iterations diverges (critical slowing down) (Figure I c)).
1.5 DRAWBACKS OF THE IB
The main theoretical and practical drawback of the IB is it's apparent reliance on the explicit knowl- edge 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.) (0100), the main problem remains the extension of the encoder. p(8 x), when trained from small sample, to new unobserved patterns x E 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.
We ignore here the interactions hetween the representations, for simplicity.
3

---

Under review as a conference paper at ICLR 2020
8
0.8
0.6
lo8% (ftters)
0.6
0.4
Pa
0.4
0.2
0.2
0
0.0
0.0
2.5
5.0
0.0
5.0
0.0
5.0
(a) Ioga (9)
(b) loga (9)
(c) loga (9)
Figure 1: Example of the evolution of the IB decoder with growing 3. (a) The bifurcation diagram;
each color corresponds one component of the representation
X and depicts the decoder (y = 0 8). in the simplex [0, 1]. The black dots correspond to the input distribution p(y = 0 x). (b) The second eigenvalue of Cyy (&; 3), (2(x), along with 3 as a function of B. (c) Convergence time of the algorithm as function of [3
1.6 CONTRIBUTIONS OF THIS WORK
Our main contribution is by providing general formal framework resolving the encoder exten- sion drawback of the IB. While the use of specific features and variational approximations to IB not new, here take different approach assuming that ply x) can be approximated by exponential families. This defines new rate-distortion problem, the Dual Infromation Bottleneck (dualIB).
We show that the new dualIB formulation preserves the sufficient statistics the original distribution for all values of the trade off parameter, |3 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 duallB 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 duallB problem I2 We discuss the duallB's critical points in {2.1 and prove general relation between the critical points of the dual and original IB in 22.2 In particular, we show that the dual critical points give the best approximation to the original IB information curve. } 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 small sample. We conclude in 44 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 representa- tions are used to predict labels of new input patterns. We add to our Markov chain another variable, Y, the predicted label which obtains the same values Y, but distributed differently:
training
Y +Y.
(6)
prediction
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 Y has not been part of the IB optimization problem. has been implicitly assumed that the Bayes optimal decoder, pa(y x), which minimizes the IB distortion given 9,
4

---

Under review as a conference paper at ICLR 2020
is also the best choice for making predictions of Y from the representation Xg through the right- hand Markov chain. That is, denoting py(y x) = pa(y x) the ML decoder the mixture over the internal representations:
pa($ x) = Σ pa(S ())p(( xx).
This, however, is not necessarily optimal when the encoder and decoder are trained from finite samples (Shamir al., (010)), when the decoder is not Bayes optimal. We define the duallB distortion by merely switching the order of the arguments in the KL-divergence of the original IB distortion, namely:
Paly 8) log Ps(y x) ply x)
(x, DIps(y 8)]lp(y x)] Eps(y
(8)
which in geometric terms is known as the dual distortion problem (Felice & Ay 2019
That is, given the "input" random variable (input patterns), the "output" random variable Y (de- sired label) and the "representation" X, the MI. optimal "predicted label" Y is given by the mixture distribution, equation
The duallB optimization can be written as the following rate-distortion problem:
('s(( PX) x)] = I(X; X) + (Bp(x.)) /ddualI (x, 8)],
(9)
with the average distortion given terms of mutual information on Y, I(X; Y) and [(X; Y):
E (plx.))ldauattBB x)] 1(x; Y) - 1(X; + EEpol x))lp(S [x)]]
(a)
I(x: Y) 1(X: Y)
(10)
This is similar to the known IB relation: Bp(x8) [din 8)] = T(Y;X) T(Y;X) with an extra positive term (b).
Both terms, (a) and (b), vanish precisely when X is a sufficient statistic for X with respect to Y, since we can then reverse the order of X and X in the Markov chain (equation 6). This replaces the roles of Y and Y as the variable for which X are approximately minimally sufficient statistics. In that sense the duallB shifts the emphasis from the training phase to the prediction phase. This implies that minimizing the duallB functional maximizes the mutual information between Y and Y, I(Y; Y), as well as the mutual information [X;; Y). This is illustrated figure b)-
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-Arimot iterations
berween the encoder and the decoder 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 's "geometric" mean of the data distributions p(y x).
The proof is given in
The alternating projections between the encoder and decoder, which converge to a solution of the dualIB given value of the Lagrange multiplier B, are implemented by the following iterative algorithn
"We use the notation p(ý xx) ply x), when there no B subscript.
Unless stated otherwise, log In log,
5

---

Under review as a conference paper at ICLR 2020
Algorithm duallB iterative algorithm
1: while
(y (y x) P/ x) > e do
x/x (x; = Exp/( -D0p))=-00)0
2:
1 x) = p2((2)
-DDD
3:
221x (x:a)
(xxA(
4:
(x) = =Exp3 1x (x x))(xx
y/R (x: = "E,eZ. P/ (x(8) log ((yx)
5:
P3 (y 8) Zyle(8:0) e
(x(8) (x1R) logr(l))
6:
7:
return (2( ps( { x), PayP))))) &)
Here the Z's 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 illustrates the behavior of the duallB algorithm for the same distribution in Figure D The overall behavior is very similar, but the critical points (representation splits) slightly change their location. In the following sections we provide detailed analysis and comparison between the two frameworks.
15
3
0.8
0.6
P5 1y 0 ())
log, iiters)
10
0.4
0.4
0.2
0.9
0
0.0
2.5
5.0
0.0
2.5
5.0
0.0
2.5
5.0
(a) loga (3)
(b) loga (6)
(c) logo (9)
Figure 2: Same as Figure 1 for the duallB solutions with the OdgalltB matrix. (a) The representations bifurcate at the critical values of B. (b) Critical points appear when an eigenvalue (color) crosses the 3-1 (black) line. (c) Near these points there is critical slowing down and the numbers of iterations of Algorithm diverge.
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. 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 eigen-
value problem:
@ Blgg 18) 00,
@ Plogpaly 18)
[ 3CduullBB (8, B)]
[I- BCduullB (x, 3)]
0, (11)
0R
0R
with the matrices CddualIB given by:
psly x))p(( x) log ply x)
-Pa(x' 1))p((y) x) log p(y x')
CdualllB (x: = Σ
p(y x)
p(y x')
p(y x)
-Paly' [x)pp(( 8)) log ply' x)
CddaaTB (x: = Σ
ps(x ())p(( 8) log
(12)
p(ý x)
p(y' {x)
x,
The proof theorem is given in A.3

---

Under review as a conference paper at ICLR 2020
Lemma 3. The matrices CdvallB
(&: B), Sy sy ( have the same eigenvalues {)e), with (x) = With binary Y, the critical points are obtained at (2) B-1
The proof lemma 3 given in section A.3.1
As in the IB, the critical points, _d the partial derivatives of the encoder and decoder with respect to B, Ô Óog (x 8)/03, ò log paly x)/03, have multiple (at least two) values. This re- sults 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, Ix (X; vs. ly Y), is the standard visualization of the ceppression-predicctn trade off of the IB. It can be defined for any encoder once the decoder is the Bayes optimal (equation (tte), for which the Iy is the actual information of the representation on the desired label (Tishby et al. 1999).
Comparing the dualIB information curve the IB curve shows the quality of this approximation. Figure 3a) depicts this comparison. While we know that (B3 is always higher, the two curves are almost indistinguishable. To better understand the relationship between these curves, we look at the values of Ix and ly as functions of the corresponding 3 (Figure (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 the dual critical points.
10
0.8
0.8
IB,
1(X: 1(X: ()
I(V: 20/000
0.6
dudlE. doar
0.6-
0.4
0.4
0.2
0.2
0.2
0.00
0.25
0.50
0.75
(6) (XX(X)
(0) log,(3)
(e) loga(d)
Figure 3: The IB's and duallB's Information Plane. (a) Iy Ix for the two algorithms. The black dots are the dualIB critical points, gdualTB and the grey triangles are the IB critical points, BIB The corresponding distortion functions are shown in the inset. (b) The functions ( and IX [ Both curves 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, 7 (8) and rdualiB(3) (3) 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 B.
Lemma 4. Ix(3) and Iv (ū),, along the optimal lines, are non non-decreasing piece-wise c tions of B. When their second derivative (with respect to 3) is defined, is strictly negative.
Lemma 5. For any sub-optimal information curve (Ix, Ix), I (B) < Ix(8) and I(P()) (3) S (3),, for all values of B.
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, 3 gduslIB < B!B (ii) The distance between the two information curves is minimized precisely at the dualIB critical points g gduall13 (iii) The two curves approach each other 3 +
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 the critical points, BB and gdualIB have
7

---

Under review as a conference paper at ICLR 2020
different left and right derivatives, they form cusps in the curves of the mutual information (Ix and Iy) as functions of B. These cusps can only be consistent with the optimality of the IB curves B (this is true for any sub-optimal distortion), otherwise the curves intersect.
Pe geualii
Moreover, at the duallB 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 &duall the distance between the curves has (local) minimum. This is depicted in Figure 3 comparing (3) and (3) and their differences for the two algorithms.
The two curves approach each other for large 33 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 I 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 exis- tence features, or statistics of the pattern, (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 (957) 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 tech- nical reason the duallB encoder and decoder preserve the exponential form of the original data distribution for all values of B. Furthermore, the new (assumed limited to finite dimension d) set of features/statistics are precisely the empirical expectations of these features. These empirical averages are the only numbers needed for predicting the label at the required accuracy, hence their advantage in reducing the encoder's ss computational complexity.
Assuming that the rule distribution is of the form:
ply x) =e- EiE
A (x) ---))))))-- -O0 Zy)a(()
II (7)) r=0
(13)
where (x) are d linearly independent functions of the input and (y) are functions of the label y. or the parameters of this exponential family. The A(y) can also be considered Lagrange multipli- ers associated with the constraints conditional expectations Ep(xty)
in entropy maximization.
The normalization factors, (x)x are written, for brevity, as X = log Cyy II e-*((s),,
with (x = 1. We do not constrain the marginal p(x).
The important fact about the exponential form is that all the mutual information, T(X; Y), is fully captured by the d conditional expectations, Ep(xty) [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 huge reduction in computational complexity (from dim 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 B.
Theorem 7. (dualExpIB) For data from an exponential equation 13 the optimal decoder of the dualIB, at given B, is given by:
Paly =x)==== Eiz (5 A2(()= = loog( Σ Ed (()))))())), (14)
and the respective encoder:
8

---

Under review as a conference paper at ICLR 2020
P x) P (O(X))-RA((8) -823(8)
(15)
(xxx(x;B)
with the constraints and multipliers expectations,
(x,)(R) Σ Pa(x (x),,(), 15(8)= = Paly (2(
(16)
The complete derivations for this section are given
A.S
This defines simplified iterative algorithm to solve the dualExplll problem, since we can replace the decoders' update rule at each iteration in the dualIB algorithm (Algorithm 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 exponential family, ply x) NN(0, b)si((cxx))) 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 (x). Given the assumption on the rule we assess the exponential form empirical distribution, Pexp() (y x; (x)). We then evaluate the IB on both empirical distributions, f and Pexpp and compare it to the dualExpIB given (x),, (
The comparison between the IB and the dualEXpIB, is given in Figure (a) function of the con- tinuous for 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 Y, where the expected maximization by the dualExpIB is observed, Figure ()) To evaluate the prediction ability of the dualExpIB we consider the Li-expected loss with respect to the original distribution. Looking at Figure ()) apparent that for all values of the trade off parameter, B, the dualExpIB minimizes the loss providing the superiority in prediction.
0.10
0.4
f
IB Dup dualExp1B
0.08
(1
0.15
eopperted loos
0.3-
1000 8)
0.10
0.06
0.2
0.05
IB
0.04
population sampled
Dop
0.1
dualExpfB
1.0
0.0
1.0
0.2
0.6
(0)
(e) loga(
Figure The IB's and dualExpIB's behavior over data sampled from p(y x) NOO b) sin(c]))]) and p(x) ~ ~((1111). (a) The decoder p5 ()) as function of for some f 1-1,1) at (8) (b) The Information Plane with respect Y, ((Y; Y) I(X; (c) The L Ei-eppected loss, Eppo x) - PP x)]I], as a function of the trade off parameter B.
4 CONCLUSION
We presented here the Dual Information Bottleneck (dualIB), a framework to preform the Informa- tion Bottleneck (IB) compression in parametric setting. We have shown that the duallBB 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 significantly reduce the complexity of finding good IB representations; (ii) it optimizes the information between the representation and the pre- dicted label rather than the desired label in the original IB, As have shown, this can improve
(y) are defined by the specific exponential family.

---

Under review as a conference paper at ICLR 2020
the generalization enror 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 satis- fied 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 other exponential families was open problem for many years; (iv) The exponential form of the optimal encoder-decodee 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 applications using finite samples or data with low internal dimensionality or special symmetries.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alexander A. Alemi, Ian Fischer, Joshua V. Dillon, and Kevin Murphy, Deep variational information bottleneck. ArXiv, abs/1612.00410, 2016.
Lawrence D. Brown. Fundamentals of statistical exponential families with applications in statistical
decision theory. Lecture Notes-Monograph Series, 9:i-279, 1986. ISSN 07492170. |
Gal Chechik, Amir Globerson, Nafaal Tishby, and Yair Weiss. Information bottleneck for gaussian variables. J. Mach. Learn. Res., 6:165-188, December 2005. ISSN 1532-4435, URL http: 7/dl acm. org/ //g/iiiaaionn....
Thomas M. Cover and Joy Thomas. Elements of Information Theory (Wiley Series Telecom- munications and Signal Processing). Wiley-Interscience, New York, NY, USA, 2006. ISBN 0471241954.
Domenico Felice and Nihat Ay. Divergence functions in information geometry. In Frank Nielsen and Frédéric Barbaresco (eds.), Geometric Science of Information 4th International Conference, GSI 2019, Toulouse, France, August 27-29, 2019, Proceedings, volume 11712 of Lecture Notes in Computer Science, pp. 133-442. Springer, 2019. ISBN 978-3-030-269799-1 doi: 10.1007/
178-3-030-26980- 45. ott.1/////.oooooo///000000000333
45
Ran Gilad-bachrach, Amir Navot, and Naftali Tishby. An information theoretic tradeoff between complexity and accuracy. In In Proceedings of the COLT, pp. 595-609. Springer, 2003.
Amir Globerson and Naftali Tishby. Sufficient dimensionality reduction. Journal of Machine Learn- ing Research, 3(Mar): 1307-1331, 2003.
E. T. Jaynes, Information theory and statistical mechanics. Phys. Rev, 106:620-630, May May 1957, doi: 10.1 10. 106.620. URL /tttps://link.ooo aps. http://ww...pppooo///o//////////
106. 620
S. Kullback. Information Theory and Statistics. Wiley, New York, 1959.
Xiang Lisa Li and Jason Eisner. Specializing word embeddings (for parsing) by information bottleneck. Proceedings of the 2019 Conference on Empirical Methods Natural Lan- guage Processing and 9th International Joint Conference on Natural Language Processing, pp. 2744-2754, Hong Kong, November 2019. URL /ttt:t/p://c.. ela.eedd/-jasoo/pppeer Best Paper Award.
#li-eisner- 2019
Shuang Ma, Daniel McDuff, and Yale Song. Unpaired image-to-speed synthesis with multimodal information bottleneck. In Proceedings of the IEEE International Conference on Computer Vi- sion, pp. 7598-7607, 2019.
Amichai Painsky and Gregory W. Wornell. Bregman Divergence Bounds and the Universality of the Logarithmic Loss. arXiv e-prints, art. arXiv:1810.07011 Oct 2018.
Sonali Parbhoo, Mario Wieser, and Volker Roth. Causal deep information bottleneck. ArXiv, abs/1807/ 180.00207.02...... 2018
Albert E. Parker, Tomáš Gedeon, and Alexander G. Dimitrov. Annealing and the rate distortion problem. In S. Becker, S. Thrun, and K. Obermayer (eds.), Advances in Neural Information Processing Systems 15, pp. 993-976. MIT Press, 2003. URL. httt:://pppppprrr www...iips..... ps............ ac/ paper/2264 anw.aaa2--annaaaaaaaaaa ling and the rate wistoortionnpoooleee...
Elad Schneidman, Noam Slonim, Naftali Tishby. R deRuyter van Steveninck. and William Bialek. Analyzing neural codes using the information bottleneck method. Advances in Neural Informa- tion Processing Systems, NIPS, 2001.
Ohad Shamir, Sivan Sabato, and Naftali Tishby. Learning and generalization with the information bottleneck. Theor. Comput. Sci., 1:2696-2711 2010.

---

Under review as a conference paper at ICLR 2020
Noam Slonim, Nir Friedman, and Naftali Tishby. Multivariate information bottleneck. Neural Computation, 18(8):1399-779,, 2006. doi: 10.1162/mec.2006 19.611888.7399 URL https://
doi 1ttp:/...11.2.... wtt.oo/g/...11//nnoooo.. 2006. 18 18.8.17.99 PMID: 16771652.
Naftali Tishby, Fernando C. Pereira, and William Bialek. The information bottleneck method. In Proc. of the 37-th Anmual Allerton Conference on Communication, Control and Computing, pp- 368-3 377, 1999.
R. Tredicce, G. L. Lippi, Paul Mandel, Charasse, A. Chevalier, and B. Piequ. Critical slowing down at bifurcation. American Journal of Physics, 72(6):79--809 2004. doi: 10.1119/1. 1688783. URL
org/10 http://..1111//1111 1119/1 688783
G. Tusnady and I. Csiszar. Information geometry and alternating minimization procedures. Statistics & Decisions: Supplement Issues, 1:205-237 1984.
Noga Zaslavsky and Naftali Tishby. Deterministic annealing and the evolution of optimal informa- tion bottleneck representations. Preprint, 2019.
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 DUALIB MATHEMATICAL FORMULATION
As presented in th dualIB is solved with respect to the full Markov chain (equation 6 in which introduce the new variable, Y, the predicted label. Thus, in analogy the IB we write the optimization problem in term of Y.
Developing the expected distortion we find:
ps(l | 8) log po | x) p(ý xx)
(x (ddualIB (x, x)] =
Σ (x, 8) x,
Σ 8
log (5 (8)
((x)ps(() x) pa(y x)
Σ
(a(X))s())
Σ
po(ý)
ps(ý)
x.9
Py(y x)
(())p=(8 xo
p(ý x)
((X; Y) - ((: Y) + E Ep(x) (Dls x)(p(( x)]
Allowing the dual optimization problem to be written as:
F'(((8 x):p(8);p(y x)] = (X: - =(1(x Y) Epto)Dlpst xx)lp(() X0]]]
A.2 THE DUALIB SOLUTIONS
To prove theorem we want to obtain the normalized distributions minimizing the dualIB rate- distortion 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 small perturbation the distortion ddnaaI (x, 8), with a(x) the normalization Lagrange multiplier, we obtain:
Σ py &)) log
log Pæ(y x) ply x)
+ a(x) E pely 18) (1)-1)
5d (x,
8ddual1 (x, 8) Pa(y (x)
log
+ +1+ a(x).
8ps(y 8) Hence, minimizing the expected distortion becomes:
p(y x)
log Pa(y ())
0 = Σ pa(x x)
ply x) +1 + axx)
ly ())
Σ p log xx 1+
which yields Algorithm row 6.
Considering the duallB encoder-decoder, Algorithm we find that (p.(xx))ddduaa (x, 8)] reduces to the expectation of the decoder's log partition function:
Py x)
(xp(x.) (x.2) [dduallB (x, x)] = Σ px x) Σ py x) log
p(y x)
-EE Eps(X) [log Zy x (8: 8)]
+
Σ (x)
Σ ps(x' loggly |x) ()>-pph (x (x) logply x)
8.y
-Fpp(() blog Zy x (x: 8)]
13

---

Under review as a conference paper at ICLR 2020
A.3
STABILITY ANALYSIS
Here we provide the detailed stability analysis allowing the definition of the matrices Cd Cuyali (equation 12 and which allows us claim that they obey the same rules as the C
"y
matrices (equation 5 in equation 4 Considering variation in & we get:
log p:a (x 8)
p(y
x)
log pa (8)
3
Σ py [8)
log
0R
8)
OR
Ölog alogps(y ())
B Σ pa(y 1x)
logply (x) - Σ Pa log x))
0x
+33 Σ log Zy1x( (x: (3) @pa(y 1x)
08
py {))p((X (8) log ply x) d Aogpa(y (8)
3
Σ
(17)
ply x)
0K
N,
① log paly (8)
1 (Zy)x($;3) 9)
2 log p 8)
Σ p () logp(y x)
0x
4 (x;
0x
08
i Plogpo(x 8)
--Eps(y pa(8 8) Σ ps(x 8) log
0x
Σ ( | logply | x) aogg ( l
08
Σ ps(x | k))s(( x) log ply x) a Plogps(x | x)
(18)
ply x)
0%
Substituting equation
18 into equation 17 and vice versa one obtains:
log (x x)
Poly {)pp({ X) log ply x)
B
0x
ply x)
log p(y x²) a log Px |x)
(x
x)pp(ý)
ply x²)
Ox
1og P3 (8)
3 Σ ps(x x)p=(8) x) log ply x)
0R
p(ý x)
x,y' x.
ply' x)
0.0log po (y' |x)
Paly' x)pp(X log ply' x)
0%
We now define the CdualIB matrices as follows:
dddaalB (x:3)= = Σ p x)ps(X () log p(y | x)
pps('' (x)p((}) I log ply x')
p(y x)
p(y x')
Cipy CyhaalIB/ (x: Σ ( x))p(" [o)log log p(y | x)
p(ý | x) ps(y') 18)ps(X log ply' x)
ply' xx]
x,
Using the above definition we have an equivalence equation in the form of:
a log px x)
=,, [I- T-BSChallB (x, 3)] & log Pa(y' 18) O.
[
T-BCduallBB (x, ]
0
08
Note that for the binary case, the matrices may be simplified to:
p(y x)
ply xx)
OdualIB (x: B) = Σ p [x)ps(X ()) log ply
px(x' x poly / x)) log
x)
1 - p(y xx)
y.
ply x)
"psly' ())p(( log ply' x) ply' x))
CdyalIB (8:3) Σ
px(x [8)(1= pa(y x)) log
1-ply x)
x.
14

---

Under review as a conference paper at ICLR 2020
A.3.1 PROOF OF LEMMA B
We show that the OduallB matrices share the same eigenvalues with Ax - O.
Proof. The matrices, Od (x; B), Ca (K; (), are given by:
CduallB (8; 5) = (x; (x: 3) Byx (8: 8), Cy Cyg (x: (xx B) (8: ();
with:
ply x) ply x)
B) = po(x x) Σ Eoll () log ply x) p(y x)
(xy(;; =
p po(y 8)
Σ (x log
Given that the matrices are obtained by the multiplication of the same matrices, it follows that they have the same eigenvalues (A.(x;
To prove that Y1 () = 0 we show that "y" = O. We present the exact calculation for binary label Y E {Yo Y1 } (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):
Σ p 8)pp(y, | 8) log plyo x) ply, x) Po(Yo {))p(( |x) log p(yo x) p(yo x)
det(C det(Crduali (x: yy'
x.
ps(x' x)ps(yo log ply | xx)
plyo x') "ps(y) 1))p((X') x) log ply xx) p(y; xx)
Σ xx,
ps(x 8)ps(yo log ply, x)
plyo x) -Ps {))p(( | log p(y, x)
Σ X.8
p(yo X)
Po(x' x)ps(y) (x) log p(yo xx) ply, xx)
ply; xx)
Σ x
Pa 18)p (X' xx) log
p (x)
plyo x)
ply, x))
Σ
pa(x x)ps(x') x)p3(y0 (yp {)pp({ x) log
Pa (x' ()) log
p(yo x)
ply; x')
x.x' ",
log p(yn x) ply; x) p(yu x') p(y, x)
ply, xx)
log plyo x)
ply: Ix') plyo x')
log
log
0.
Given that the determinant implies that A (x) O.
For binary problem we can describe the non-zero eigenvalue using x²(8) That is:
Tr(CrdualIB (8; B)).
yy'
A2(8)=
Σ
[ 8)ps(y1 x) log p(yo x) p(y, x)
paslo [x)ps({] x) log p(yo
x)
plyo x)
x,X
+ Σ [ x)pa(yo x) p(y x)
pps(y; {))p(( xx) log p(y;
x)
plyo x)
ply1 x)
x,
p(yo x)
p(yn x)
ply, [x)
-psly, 8)pss(y x) Σ p x))p(( x) log
log
log p(y, x))
ply;
x)
p(y, ()
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 (x.(). [d(x, 8)] with slope of -3.
We emphasis that this is a general result of rate-distortion thus holds for the dualIB well.
15

---

Under review as a conference paper at ICLR 2020
Lemma 9. For a fixed encoder pa( x) and the Bayes optimal decoder (y 18):
Eldmn (x, = [(: -
Thus, the information curve, Iv vs. Ix, is non-decreasing concave function with a positive slope,
3-1. The concavity implies that increases along the curve.
Cooerr & Thomas
2006; Gilad-bachrach et al. 2003).
A.4.1
PROOF OF LEMMA
4
In the following section we provide proof to lemma for the IB and dualIB problems.
Proof. We want to analyze the behavior of Ix(3), (8),, that is the change in each term function of the corresponding B. From lemma 9 the concavity of the information curve, we can deduce that both are non-decreasing functions B. As the two 3 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 fixed (clusters are "static"). For "static" clusters, the 3 derivative of Ix, along the optimal line is given by:
0I(X;X)
Σ
(x) Zx/x + Bd(x,
08
03
x.8
alog p. |x]
-33 d(x, x)
03
ps(x.))
3 Olog (x)x 3)
B d(x,8)
+ d(xx))
03
ps(xx))
B (d(x po(())) po(k)) (d(x, x)) (S())x)
Var(d(x))
p(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 3 decreases the clusters conditional entropy H (X X), as the encoder becomes more deterministic. The mutual information is bounded by HX) and it's B derivative decreases. Further, between the critical points there are no sign changes the second / derivative.
A.4.2 PROOF LEMMA
Proof. The information curve has a positive slope, 3-1, with 3 increasing along it, lemma That is, given value of B, there exists pair I (B). ( such that ar ( ( /a) 8 Now,
consider a sub-optimal information curve, 15, Ix There exist values 3r, 8" such that:
[x0)) (3), I208) 1 (B).
The optimality of the IB implies that sub-optimal curves lie below it; i.e the IB slope is steeper:
B > 3' 3 30-1
Thus, given that 3 increases along the information curve, it holds that:
(2() 1288) (3), 12(3) 1333)) (g))
16

---

Under review as a conference paper at ICLR 2020
A.5 DERIVATION OF THE DUALEXPIB
We provide elaborate derivations to theorem 7 that is, we obtain the duallB optimal encoder-decoder under the exponential assumption over the data. We use the notations defined in f
The decoder, equation 14
Substituting the exponential assumption into the duallB log-decoder yields:
logpa(y 8)
Σ p 8) log ply x) log (x;
pa(x ())(())4,(x)) log Zyix (8:
Σ s E p [12] - log (x;x B).
Taking closer look at the normalization term:
(x: Σ
Cw (x(x logp()))) (o]k)
= Pro001S Σ E Di (7)
y
log (8; - Bpo(1)) [22 log Σ c > A (
From which it follows that (x) is given by:
X N'63Ane())
xg log
and we can conclude that the dualExpIB decoder takes the form:
logpsly 8) = Σ (8))..
The encoder, equation 15 The core of the encoder is the dual distortion function which may now be written as:
Py x)
detaalis (x, 8) = Σ po(y &) log
ply x)
Σ ps x)) (1 1 --2((t)) + Σ (x,0((()))))
2 - 19(x) Σ
-
substituting this into the encoder's definition we obtain:
P8 x) = (x(x)
- DíE A..
7x|x(x; B)
-A (4)
Zxix (x:x(x:11)
17


Reviews:
[{"review_id": "S1xNKglJcH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a variant of the Information Bottleneck (IB) framework, which consists in permuting the conditional probabilities of y given x and y given \\hat{x} in a Kullback-Liebler divergence involved in the IB optimization criterion.\n\nInterestingly, this change only results in changing an arithmetic mean into a geometric mean in the algorithmic resolution.\n\nGood properties of the exponential families (existence of non-trivial minimal sufficient statistics) are preserved, and an analysis of the new critical points/information plane induced is carried out.\n\nThe paper is globally well written and clear, and the maths are rigorously introduced and treated. Two minor comments would concern the definition of the Mutual Information (MI), which could be recalled to help the unfamiliar reader and improve self-containedness, and the notation of the expected value (\\langle \\rangle_p), unusual in Machine Learning where \\mathbb{E} is often preferred.\n\nAnother point that could be enhanced is the intuition behind the IB and dualIB criteria: a small comment on their meaning/relevance as well as the rationale/implication of the probabilities permutation would be valuable addition.\n\nExhibiting a link with variational autoencoders (VAEs), and expliciting the differences in a VAE framework between the two criteria could also represent an interesting parallel, especially for machine learning oriented readers.\n\nOne of the main drawback of the present paper is however the lack of convincing experiments. Graphs showing the good behavior of the introduced framework are ok, but the clear interest of using dualIB rather than IB could be emphasized more. In particular, it does not seem that the issues about IB raised in the abstract (curse of dimensionality, no closed form solution) are solved with dualIB. Furthermore, dualIB optimizes the MI of the predicted labels, which is claimed to be beneficial contrary to the MI on the actual labels. However, no empirical demonstration of this superiority is produced, which is a bit disappointing.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxXpukrjH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Description:\n\nThe 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.\n\nIn 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).\nThe \"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. \n\n- An iterative algorithm (Algorithm 1) similar to the original IB algorithm but with a few more steps is provided.\n\n- 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.\n\n- 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.\n\n\n\nEvaluation:\n\nThis 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.\n\nOverall, 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:\n\n- 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.\n\n- 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.\n\nThe 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?\n\nIn 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.\n\nOther comments:\n\n\"Application to deep learning\" mentioned in Section 1.5 is only a sincle sentence in the conclusions.\n\nThere 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?\n\nSection 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.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Byl0gW8RFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new \"dual\" variant of the Information Bottleneck framework. The IB framework has been the subject of many papers in past years, with a focus on understanding the inner workings of deep learning. The framework poses machine learning as optimizing an internal representation to tradeoff between retaining less information about the input features and retaining more information about the output label (prediction). The existing framework measures the retained information about the prediction via mutual information, which can be expressed as a KL divergence. The new dual framework reverses the arguments of this divergence.\n\nThe paper shows that this dual IB closely mirrors the original IB while having several additional nice mathematical properties. In particular,  it can be shown that for exponential families the dual IB representation retains the exponential form.\n\nOverall, I think this paper adds a meaningful new perspective to the IB framework and the analysis appears to be thorough. As such, I support acceptance. \n\nThe paper could be improved by giving more interpretation of the formal results and experiments - i.e. tying this framework back to the higher-level questions and explaining what the quantities mean.\n\nFigures 1, 2 part a: The meaning of both axes is unclear. The horizontal axis beta is a lagrangian parameter with no meaning outside the framework. The vertical axis Pr[y=0|\\hat x] has no semantics since the problem has not been defined. What is the reader meant to take away from these figures?\n\nEquation 3, part i: The numerator should have a beta subscript. The meaning of the denominator is not clear (it is a normalizing constant).\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Main content:

Blind review #1 summarizes it well:

This paper introduces a variant of the Information Bottleneck (IB) framework, which consists in permuting the conditional probabilities of y given x and y given \hat{x} in a Kullback-Liebler divergence involved in the IB optimization criterion.

Interestingly, this change only results in changing an arithmetic mean into a geometric mean in the algorithmic resolution.

Good properties of the exponential families (existence of non-trivial minimal sufficient statistics) are preserved, and an analysis of the new critical points/information plane induced is carried out.

--

Discussion:

The reviews generally agree on the elegant mathematical result, but are critical of the fact that the paper lacks any empirical component whatsoever.

--

Recommendation and justification:

The paper would be good for ICLR if it had any decent empirical component at all; it is a shame that none was presented as this does not seem very difficult.
Decision: Reject