Phase Transitions for the Information Bottleneck in Representation Learning
Authors: Tailin Wu
Ian Fischer
Venue:  (2020)
Keywords: Information Theory
Representation Learning
Phase Transition

Abstract: In the Information Bottleneck (IB), when tuning the relative strength between compression and prediction terms, how do the two terms behave, and what's their relationship with the dataset and the learned representation? In this paper, we set out to answer these questions by studying multiple phase transitions in the IB objective: IB_β[p(z|x)] = I(X; Z) − βI(Y; Z) defined on the encoding distribution p(z|x) for input X, target Y and representation Z, where sudden jumps of dI(Y; Z)/dβ and prediction accuracy are observed with increasing β. We introduce a definition for IB phase transitions as a qualitative change of the IB loss landscape, and show that the transitions correspond to the onset of learning new classes. Using second-order calculus of variations, we derive a formula that provides a practical condition for IB phase transitions, and draw its connection with the Fisher information matrix for parameterized models. We provide two perspectives to understand the formula, revealing that each IB phase transition is finding a component of maximum (nonlinear) correlation between X and Y orthogonal to the learned representation, in close analogy with canonical-correlation analysis (CCA) in linear settings. Based on the theory, we present an algorithm for discovering phase transition points. Finally, we verify that our theory and algorithm accurately predict phase transitions in categorical datasets, predict the onset of learning new classes and class difficulty in MNIST, and predict prominent phase transitions in CIFAR10.


Published as a conference paper at ICLR 2020
PHASE TRANSITIONS FOR THE INFORMATION BOTTLE- NECK IN REPRESENTATION LEARNING
Tailin Wu
Ian Fischer
Stanford
Google Research
ta ctteiicssstaforr.eei.
ians f google com
ABSTRACT
In the Information Bottleneck (IB), when tuning the relative strength between compression and prediction terms, how do the two terms behave, and what's their relationship with the dataset and the learned representation? In this paper, we set out answer these questions by studying multiple phase transitions in the IB objective: IB [B=[p(=[=)] I(X; 2)-3I(Y; Z) defined on the encoding distribution p(z|z) for input X, target and representation Z, where sudden jumps of (2) d8 and prediction accuracy are observed with increasing 3. We introduce a definition for IB phase transitions as a qualitative change of the IB loss landscape, and show that the transitions correspond to the onset of learning new classes. Using second- order calculus of variations, we derive formula that provides practical condition for IB phase transitions, and draw its connection with the Fisher information matrix for parameterized models. We provide two perspectives to understand the formula, revealing that each IB phase transition is finding a component of maximum (nonlinear) correlation between X and Y orthogonal the learned representation, in close amalogy with canonical-correlation analysis (CCA) in linear settings. Based on the theory. we present an algorithm for discovering phase transition points. Finally, we verify that our theory and algorithm accurately predict phase transitions categorical datasets, predict the onset of learning new classes and class difficulty in MNIST, and predict prominent phase transitions in CIFAR10.
INTRODUCTION
The Information Bottleneck (IB) objective (Tihbyy al. 2000):
[Ba[r(2|=)] == T(X; 2) (T( 2)
explicitly trades off model compression (I(X; I(::-) denoting mutual information) with pre- dictive performance (I(Y; using the Lagrange multiplier 8. where X, Y are observed random variables, and Z is learned representation of X. The IB method has proved effective in variety of scenarios, including improving the robustness against adversarial attacks (Alemi et al., 2016 Fiicherr 2018), learning invariant and disentangled representations (Achille & Soatto 2018 b). underlying information-base geometric clustering (Strouse & Schwab] (017b)) improving the training and performance in adversarial learning (Peng et al. 2018), and facilitating skill discovery (Sharma et al. 2019) and learning goal-come coal-conditioned policy (Goyal et al. 2019) in reinforcement learning.
From Eq. I see that when 3 > 0 it will encourage I(X; Z) 0 which leads to trivial representation Z that is independent of X, while when 3 - +00, it reduces to a maximum likelihood objective that does not constrain the information flow. Between these extremes, how will the IB objective behave? Will prediction and compression performance change smoothly, or do there exist interesting transitions in between? In Wu et al. (2019), the authors observe and study the learnability transition, i.e. the 3 value such that the IB objective transitions from a trivial global minimum to learning a nontrivial representation. They also show how this first phase transition relates to the structure of the dataset. However, to answer the full question, we need to consider the full range of B.
For example, in classification, it reduces cross-entropy loss.

---

Published as a conference paper at ICLR 2020
10)
XXA
14 Af:40
Figure 1: CIFARIO plots (a) showing the information plane, as well as 8 vs (b) [[X; Z) and [(: Z). and (c) accuracy, all on the training with 20% label noise. The arrows point empirically-obseee phase transitions. The vertical lines correspond to phase transitions found with Alg.
of how I(Y; Z) and [X; Z) vary with 8, train Variational Infor- mation Bottleneck (VIB) models (Alemi et al. 2016) on the CIFARIO dataset (Krizhevsky & Hinton 2009), where each experiment
Motivation. To get
different and random initialization of the model. Fig. shows the T(;; Z), T(Y: 7) and accuracy vs. 8, as well as T(Y; Z) vs. T(X; Z) for CIFAR10 10 with 20% label noise (see Appendix forr details).
From Fig. [b)(), we see that we increase B, instead of going up smoothly, both I(X; Z) and IY;; 2) show multiple phase transitions, where the slopes dr(x;Z) and dr(Y; are discontinuous ds
and the accuracy has discrete jumps. The observation lets us refine our question: When do the phase transitions occur, and how do they depend on the structure of the dataset? These questions are important, since answering them will help us gain a better understanding the IB objective and its close interplay with the dataset and the learned representation.
Moreover, the objective belongs a general form of two-term trade-offs in many machine learning objectives: L Prediction-low loss + 3 Complexity, where the complexity term generally takes the form of regularization. Usually, learning is set at a specific 3. Many more insights can gained we understand the behavior of the prediction loss and model complexity with varying 3, and how they depend on the dataset. The techniques developed to address the question in the IB setting may also help understand the two-term tradeoff in other learning objectives.
Contributions. In this work, we begin to address the above question in IB settings. Specifically:
We identify a qualitative change of the IB loss landscape w.r.t. p(=[z) for varying 3 as IB phase transitions (Section 3).
Based the definition, introduce a quantity G G'p(z1z)) and use it to prove a theorem giving a practical condition for IB phase transitions. We further reveal the connection between G G'p(22<=)] and the Fisher information matrix when p(2(x: is parameterized by 0 (Section 33.
We reveal the close interplay between the IB objective, the dataset and the learned represen- tation, by showing that in IB, each phase transition corresponds to learning new nonlinear component of maximum correlation between. X and Y. orthogonal to the previously- leamned Z, and each with decreasing strength (Section 4).
To the best of our knowledge, our work provides the first theoretical formula to address IB phase transitions in the most general setting. In addition, we present an algorithm for iteratively finding the IB phase transition points (Section 5). We show that our theory and algorithm give tight matches with the observed phase transitions categorical datasets, predict the onset of learning new classes and class difficulty in MNIST, and predict prominent transitions in CIFAR10 experiments (Section 6
RELATED WORK
The Information Bottleneck Method (Tishby al.) (0000) provides tabular method based on the Blahut- Arimmoo- (BA) Algorithm (Blahut) 1972) to numerically solve the IB functional for the optimal encoder distribution X), given the trade-off parameter /3 and the cardinality of the representation
2

---

Published as a conference paper at ICLR 2020
variable Z. This work has been extended in a variety of directions, including to the case where all three variables X, Y. Z are multivariate Gaussians (Chechik et al. (205)) cases of variational bounds on the IB and related functionals for amortized learning (Alemi al. 2016; Achille & Soatto| 2018a Fischer, 2018), and a more generalized interpretation of the constraint on model complexity as a
Kolmogorov Structure Function (Achille al. 2018). Previous theoretical analyses of IB include Rey & Roth (2012), which looks at IB through the lens of copula functions, and Shamir et al. (2010).
which starts to tackle the question of how bound generalization with IB, We will make practical use of the original IB algorithm, as well as the amortized bounds of the Variational Informormation Bottleneck (Alemi et al. 2016) and the Conditional Entropy Bottleneck (Fischer 2018).
Phase transitions, where key quantities change discontinuously with varying relative strength in the two-term trade-off, have been observed in many different learning domains, for multiple learning ob- jectives. In Rezende & Viola (2088) the authors observe phase transitions in the latent representation of (-VAE for varying 33. [Strouse Schwab (2017b) utilize the kink angle of the phase transitions in the Deterministic Information Bottleneck (DIB) (Strouse & Schwab 2017a) to determine the optimal number of clusters for geometric clustering. Tegmark & Wul (2019) explicitly considers critical points in binary classification tasks using discrete information bottleneck with non-convex opttmaal frontier. In Accille & Soatto (2018a), the authors observe a transition on the tradeoff of T(; X, Y) vs. [ 0) in Iroour Under IB settings, Chechik al. (2005) study the Gaussian Information Bottleneck, and analytically solve the critical values 13, I-x," where X are
eigenvalues of the matrix En and Eg is the covariance matrix. This work provides valuable insights for IB, but is limited to the special case that X, Y and Z are jointly Gaussian. Phase transitions in the general IB setting have also been observed, which [Tishby] (2018) describes as "information bifurcation". : In Wu et al. (2019), the authors study the first phase transition, i.e. the learnability phase transition, and provide insights Our work is the first work that addresses all the IB phase transitions in the most general setting, and provides theoretical insights on the interplay between the IB objective, its phase transitions, the dataset, and the learned representation.
how the learnability depends the dataset.
3 FORMULA FOR IB PHASE TRANSITIONS
3.1 DEFINITIONS
Let X X,Y E V/ Z be random variables denoting the input, target and representation,
respectively, having a joint probability distribution p(X, Y, Z), with X x y x Z its support. X, Y and Z satisfy the Markov chain Z X Y.i.. i.e. Y and Z are conditionally independent given X. We assume that the integral (or summing if X, Y or Z are discrete random variables) is on X' x ) x Z. We use x, y and to denote the instances of the respective random variables. The above settings are used throughout the paper. We can view the IB objective (p(2(xr) (Fq. [ as functional of the encoding distribution p(=(zr). To prepare for the introduction of IB phase transitions, we first define relative perturbation function and second variation, follows.
Definition 1. Relative perturbation function: For p(z]z), its relative perturbation function r r(2(x) is bounded function that maps X x Z to RR and satisfies Bg (n) [r[=[=:)] = 0. Formally, define and EM > O... VX E X, Z e 2,|r(z|x) S M). We have that r(z(a) E 221x iff (2(2x) is a relative perturbation function of p(2[0). The perturbed probability (density) is p' (=|xr) p(2(x) (1 + r((22=)) for some >> O.
Qzix == {r(z]x) X Z + I Ez-ntalz) [r[2[=)] [=]]=])
Definition 2. Second variation: Let functional F[[(x)) be defined on some normed linear space R. Let us add a perturbative funturriivefunncton e h(xx) to fxx, and now the functional F(f(x) + h(x)) can be expanded as
((f()))=F[f[) = +
= =pplee -(xx]] + p2le h(x)] + prle M(x)) ||e h(x))12
such that lim (r h())] = 0, where ||-I| denotes the norm, wile M(x) - af(((a) is linear c- functional of ch(()) and is called the first variation, denoted as (F) (2(ch(())] d(f(el is quadratic fanctional of h((x), and is called the second variation, denoted as 82 (()))
de
3

---

Published as a conference paper at ICLR 2020
We think of the perturbation function h(()) an flfinite-dmmensions "vector" (æ being the indices), with e being its amplitude and h(x) its direction. With the above preparations, we define the IB phase transition as change in the local curvature on the global minimum of IB [=]
Definition 3. IB phase transitions: Let r(2[z) E Qzix be a perturbation function of p(z(zr) P's (z(a)) denote the optimal solution of [Bg[p(z[z)] at 9, where the IB functional IB(.) is defined in Eq. 4. The phase transitions 8 are the B values satisfying the following two conditions:
(1) Vr(z/a) E 22 [=B=)o(()<)))11[( 2
(2) lim inf - r(zi))e@2ix
8B [p(]=p( pz(+|>> p3(=11)))))))))) = O
Here 3 and 0 denote one-sided limits.
We can understand the 8B (IBa(p(z(ar) as a local "curvature" of the IB objective IB,, (Eq. w.r.t. p(z|z)) along some relative perturbation r(2[z). A phase transition occurs when the convexity of IB [Ba[p(z(z)) w.r.t. p(z[2) changes from minimum
saddle point in the neighborhood of its optimal solution p5 (2(2) ) as / increases from Be to 8. + 0+ This means that there exists perturbation to go downhill and find better minimum. We validate this definition empirically below.
3.2 CONDITION FOR IB PHASE TRANSITIONS
The definition for IB phase transition (Definition) 3 indicates the important role 1B |p==z>)] plays on the optimal solution in providing the condition for phase transitions. To concretize and prepare for more practical condition for IB phase transitions, expand IB IBp[p(z|z) + r(2[x))] to the second order of e, giving:
Lemma 0.1. For [B)[p(2(x)), the condition of Vr(z|z) e 2zμx, ('1B2[p(z|22] 2 0 is equivalent to 3 < G[p(2|=)) The threshold function G[p(2[z)] is given by: inf (|((2)=):p<2(a)]
Gly(=|z)] r(xx))R21x
Ex,sopla.)) (y Esup(=) (Benple) =) (r((x))))
By.zmp(y.=)
(B (Benp(aly.=)) [r([==)]]] - Bzsp(=)
(Benptate))r(aaa))
The proof is given in Appendix B in which we also give Eq. (20) for empirical estimation. Note that Lemma is very general and can be applied any p(z|z), not only at the optimal solution p3(2|z).
The Fisher Information matrix. In practice, the encoder pe (2|2²) is usually parameterized by some parameter vector 0 = (0.,0....0p)) E O. c.g. weights and biases in a neural net, where é is the parameter field. An infinitesimal change O' < + AO induces relative perturbation e (-(2((z) x)) ~ 2OT Blogne (a la) on po (=(xx) from which we can compute the threshold function Ge Ge(po(z(z)]-
80
Lemma 0.2. For IB 1Bşlpa (=]=)] objective, the condition VAD E O, (²IB,(po(=((x) 2 0 is equiva- lent to Ge (=(())))), where
Gelpo(E|z)] = inf A (Izix(0) Iz(()) A0 A A@T (Izly (0) Iz (0)) A0 T (Blgga(2)) 30
Amax
where Iz
I ddppo(=)
(Inepa(s) 00
is the Fisher information matrix (Dlopoo ) Izjy
of 0 for Z. Iz (0)
dxdzz(())) ())(()))) Ologpa(slu)
(
(Ilgpo(=lv) (Hlggo(=ll)) T are the conditional Fisher information matrix Zegers 2015) of 0 for conditioned on X and Y, respectively. Amax is the largest eigenvalue C IZZ ()) Iz (0) (CT)-1 with Umax the corresponding eigenvector, where CCT is the
J ddydzp(y)ool
Cholesky decomposition of the matrix (0) Iz (0), and Umax is the eigenvector for Amax. The infimum is altained at AO -
4

---

Published as a conference paper at ICLR 2020
The proof is in appendix We see that for parameterized encoders po(2|z), each term of G|p(2[[)) in Eq. (2) can be replaced by bilinear form with the Fisher information matrix of the respective variables. Although this lemma is not required to understand the general setting of Lemma 0.1 where the model is described in a functional space, Lemma 0.2 helps understand G[p(2|0) for parameterized models, which permits directly linking the phase transitions to the model's parameters.
Phase Transitions. Now we introduce Theorem | that gives a concrete and practical condition for IB phase transitions, which is the core result of the paper:
Theorem 1. The IB phase transition points { as defined in Definition 3 are given by the roots of the following equation:
G[vā(=|=)] =
where G[p(2|/)) is given by Eq. 22 and (3 > is the optimal solution of [Bglp(2(2) at 3.
We understand Eq. (4) the condition when [p]((()) is abou to be able be negative
at the optimal solution p ) for a given B. The proof for Theorem iis given in Appendix D In
Section 4
we will analyze Theorem D detail.
4 UNDERSTANDING THE FORMULA FOR IB PHASE TRANSITIONS
In this section set out to understand G[p(z|=)] as given by Eq. and the phase transition condition as given by Theorem from the perspectives of Jensen's 's inequality and representational maximum correlation.
4.1 JENSEN'S S INEQUALITY
The condition for IB phase transitions given by Theorem [ involves G[p(z[z)] inf ([r(=]=);p==(= which is in itself an optimization problem. We can understand r(()))ERzix
G[p(z|z)]= = inf A-C in Eq. (2) using Jensen's 's inequality:
B-C e
E Ea,spp(o (2|xr) 2 pappp())))) (Berptaaaaaal(((aat)) 2 Besp(e) ([(()
(5) The equality between A and B holds when the perturbation r(2[æ) is constant w.r.t. x for any 2; the equality between B and C' holds when [x=p(==p.=)) [=[]==]] (=(]==/) is constant w.r.t. y for any z. Therefore, the minimization B-C encourages the relative perturbation function r r(2(z) to be as constant w.r.t. x as possible (minimizing intra-class difference), but as different w.r.t. different y as possible (maximizing inter-class difference), resulting in clustering of the values of r(=(z² for different examples x according to their class y. Because of this clustering property in classification problems, conjecture that there are at most |)] 1 phase transitions, where [}] is the number of classes, with each phase transition differentiating one or more classes.
A-C
4.2 REPRESENTATIONAL MAXIMUM CORRELATION
Under certain conditions we can further simplify G G(p(z[=) and gain deeper understanding of it. Firstly, inspired by maximum correlation (Anantharam et al. 2013). we introduce two new concepts, representational maximum correlation and conditional maximum correlation, as follows.
Definition 4. Given joint distribution p( XX Y), and a representation 7 satisfying the Markov chain
Z X Y, the representational maximum correlation pr(X, (X,Y; 7) is defined as sup
Pr (X(YY; =
E Ee 2)g(y,2))
(6)
(f(:))).
where S₁ = {(f X x 2 Rgg y x Z R) f.g bounded, and Bx= 2)] Ey Ey--polle)lg1 = 0, Ex,x<p(2,>) 1 2)] By By,a~~((ne)) (9 (v, 2)] 1}.
5

---

Published as a conference paper at ICLR 2020
The conditional maximum correlation Pm (Z) is defined as:
Pin (X,Y2)) = sup E (ee.s--ttssaall(((ggg))
(f(w),((u)EES
where S2 = {(f : X - g y + R) f.g bounded, and V2 E 2 Ex-o(ate]((x)) = E Ey-p(ols)(g()) = 0, E (2==p()))) = pupp(lls) (g =
We prove the following Theorem 2 which expresses G[p(2|z)] in terms of representational maximum correlation and related quantities, with proof given in Appendix F
Theorem 2. Define 2 2/ = fr(z[z) X x
2 + R r bounded If 2 and Qz1x satisfy:
Vr(=/=) 2 there exist (z 221x, s(2) {=(z)= 2 + R 8 bounded) r(z/w)
(2(2)) + s(2), then we have:
(i) The representation maximum correlation and G:
G[p(z|=) (x
(8)
(ii) The representational maximum correlation and conditional maximum correlation:
(r 2: -sup Pm (X, Y [
Zez
(ii) When 7 is continuous, optimal relative perturbation function r(=(x) for G[p(=[z)) is given by
(=(x())= = 1: (1) 8(z - 2*)
(10)
p(2)
Pm,X., where arg max Pm (X, Y 2), and (x())) the optimal solution for the learn-
ability threshold function h² (x)) (h:A bounded)
arg min
Bolh(x)] with p(X, Y 2*)
(B]((())] is given in Theorem 4 of Wu et al. 2019))
(iv) For discrete X, Y and Z. we have
(x = max 02 (2)
(1I)
ZEZ
where o2(Z) is the second largest singular value of the matrix Qx,yIz p(z,ylz)
p(u.) Vrlz)p(o)
p(=
Vp(z(=)rtulz)
p(a|M)
2.
Theorem furthers understanding of Gly(2[|=) and the phase transition condition (Theorem) which we elaborate as follows.
Discovering maximum correlation in the orthogonal space of learned representation: Intu- itively, the representational maximum correlation measures the maximum linear correlation between f(X,2) Z) and gYY, Z) among all real-valued functions f, g. under the constraint that f(X, Z) is "orthogonal" to pZX and g(Y, Z) is "orthogonal" to pZY Theorem 2 (i) reveals that G|p(s[=)] the inverse square of this representational maximum correlation. Theorem 2 (ii) further shows that G G'p(2(2:) is finding specific = which maximum (nonlinear) correlation between X and Y
FFor discrete X, such that cardinality | 2 X'). this generally true since in this scenario, A(x, :) and s(2) have | + [Z] unknown variables, but the condition has only |X|| Z| + |X| linear equations. The difference between 2z and 210) is that 20) does not have the requirement of Ep(ale) [p(ete][[(][o) 0.
Combined with Lemma 2.2 this condition allows us to replace r(2))) 2zjx by r(]|x) 200 in Eq.

---

Published as a conference paper at ICLR 2020
conditioned on Z can be found. Combined with Theorem D have that when continuously in- crease B, for the optimal representation Z given by P3 (2) at 3, pr (X, Y; 23) shall monotonically decrease due to that X and Y has to find their maximum correlation on the orthogonal space of an increasingly better representation Z3 that captures more information about X. A phase transition occurs when pr (X, Z3) reduces to V/ after which as 3 continues to increase, pr (X, Y: Zg)
will try to find maximum correlation between X and Y orthogonal to the full previously learned representation. This is reminiscent of canonical-correlation analysis (CCA) (Hotelling 1992) in linear settings, where components with decreasing linear maximum correlation that are orthogonal to previous components are found one by one. In comparison, we show that in IB, each phase transition corresponds to learning new nonlinear component of maximum correlation between X and Y in Z, orthogonal to the previously-leameed Z. In the case of classification where different classes may have different difficulty (e.g. due to label noise or support overlap), we should expect that classes that are less difficult as measured by larger maximum correlation between X and Y are learned earlier.
Conspicuous subset conditioned on a single 2: Furthermore, we show in (iii) that an optimal
relative perturbation function r(2/z)) can be decomposed into a product of two factors, a (5(=-a))
p(a)
factor that only focus on perturbing specific point 2" in the representation space, and an h (z) factor that is finding the "conspicuous subset" (Wu et al.) 2019). i.c. the most confident, large, typical, and imbalanced subset in the X space for the distribution (X,Y) ~ Y
Singular values In categorical settings, (iv) reveals a connection between G[p(z|z)] and the singular value of the Qx,yiz matrix. Due the property of SVD, we know that the square of the singular values of Qx,r equals the non-negative eigenvalue of the matrix Q% 2x Then the phase transition condition in Theorem is equivalent to a (nonlinear) eigenvalue problem. This is resonant with previous analogy with CCA in linear settings, and is also reminiscent of the linear eigenvalue problem in Gaussian IB (Chechik et al. 2005).
ALGORITHM FOR PHASE TRANSITIONS DISCOVERY IN CLASSIFICATION
As consequence of the theoretical analysis above, we are able to derive an algorithm efficiently estimate the phase transitions for given model architecture and dataset. This algorithm also permits us to empirically confirm some of our theoretical results in Section
Typically, classification involves high-dimensional inputs X. Without sweeping the full range of B where at each is a full learning problem, in general difficult task to estimate the phase transitions. In Algorithm we present a two-stage approach.
In the first stage, we train a single maximum likelihood neural network fo with the same encoder architecture in the (variational) IB to estimate p(y|z)), and obtain an N x C' matrix p(y]zz) where N is the number of examples in the dataset and is the number classes. In the second stage, we perform an iterative algorithm w.r.t. G and alternatively, converge to a phase transition point.
Specifically, for a given 3, we use a Blahut- type IB algorithm (Tishby et al. 2000) to efficiently reach IB optimal p))(2( at B, then use SVD (with the formula given in Theorem 2 (iv)) to efficiently estimate (2]](= at B (step 8). We then use the C(pg(=(x)) value as the , and do it again (step 7 in the next iteration). At convergence, we will reach the phase transition point given by (=|x)] 3 (Theorem 1). After convergence measured by patience parameter K, we slightly increase 3 by (step 13), so that the algorithm can discover the subsequent phase transitions.
6 EMPIRICAL STUDY
We quantitatively and qualitatively test the ability of our theory and Algorithm I to provide good predictions for IB phase transitions. We first verify them in fully categorical settings, where X, Y, Z all discrete, and we show that the phase transitions can correspond to learning new classes increase 3. We then test our algorithm on versions of the MNIST and CIFAR1O datasets with added label noise.
7

---

Published as a conference paper at ICLR 2020
Algorithm Phase transitions discovery for IB
Require (X,Y): the dataset
Require fe: a neural net with the same encoder architecture as the (variational)
Require K': patience
Require 5: precision floor
Require R: maximum ratio between 3(th) and B..
I1 First stage: fit ply]az) using neural net fo:
1: plylz)) < fitting (X, Y) using fe via maximum likelihood.
2: p(x) +
Second stage: coordinate descent using G G'p(z|z)] and IB algorithm:
3: 96 f- 3(th)
4: B + (66 /BB is set collecting the phase transition points
5: (g(now), 8, count) < (56. 1,.1..))
6: while g(eem)
R do:
7:
x ((new)
8:
g(new) t 3(th) (3)
9:
if (((enw) 3 < 8 do:
10:
count count
11:
if count > K do:
12:
B B U { (now) }
13:
(new)) B (new)
14:
end if
15:
else: count +-
16: end if
17:
end while
18:
return
subroutine ((th)
sl: Compute p3 (=(xr) using the IB algorithm (Tishby et al. 2000).
s2: g(mew) + G using SVD (Eq. 8 and
s3: return (new)
6.1 CATEGORICAL DATASET
For categorical datasets, and are discrete, and p(X) and ((Y| are given. To Theorem we use the Blahut-Arimoto IB algorithm to compute the optimal p xx) for each B. I(Y: (")
vs. 3 is plotted in Fig. 2 (a). There are two phase transitions at 35 and B4. For each 3 and the corresponding (=|=))
the SVD formula (Theorem 2) compute G[p}(z|=))] shown in Fig. (b). We see that (2p = exactly the observed phase transition points f and 04. 1, Alg. converges each phase transition points within few iterations. Our other experiments with random categorical datasets show similarly tight matches.
Moreover, starting
Furthermore, in Appendix we show that the phase transitions correspond the onset of separation of p(2) x) for subsets of X that correspond to different classes. This supports our conjecture from Section 4.1 that there are most [ phase transitions classification problems.
6.2 MNIST DATASET
For continuous X, how does our algorithm perform, and will it reveal aspects of the dataset? We first test our algorithm in a 4-class MNIST with noisy labels whose confusion matrix and experimental settings are given in Appendix H Fig.
shows the path Alg. takes. We see again that in each
We use classes since it is simpler than the full 10 classes, but still potentially possesses phase transitions. We noisy lahel to mimic realistic settings where the data may be noisy and also to have controllable difficulty for different classes.
8

---

Published as a conference paper at ICLR 2020
0.30
0.25
0.20
0.15
0.10
IT:22
Alg. path
(a)
(b)
Figure 2: (a) I(Y; 2*) vs. 3 for a categorical dataset with X | = - 3, where Z is given by (2|a), and the vertical lines are the experimentally discovered phase transition points S6 and f9. (b) Glp3 (=]ar) vs. 3 for the same dataset, and the path for Alg. with (6 and f in (a) also plotted. The dataset is given in Fig. 5
13
1.1-0.1.2
6-
0.4
(a)
(b)
Figure 3: (a) Path of Alg. I starting with 3 1, where maximum likelihood model fe using the same encoder architecture as in the CEB model. This stairstep path shows that Alg. D able to ignore very large regions of 8, while quickly and precisely finding the phase transition points. Also plotted is accumulation of G[p (2[x)) vs. 3 by rumning Alg. 1 with varying starting 3 (blue dots). (b) Per-class accuracy vs. 8, where the accuracy at each 0 is from training independent CEB model on the dataset. The per-class accuracy denotes the fraction correctly predicted labels by the CEB model for the observed label ÿ.
phase Alg. T converges to the phase transition points within few iterations, and it discovers in total 3 phase transition points. Similar the categorical case, expect that each phase transition corresponds to the onset of learning new class, and that the last class is much harder to learn due to larger separation of 3. Therefore, this class should have much larger label noise that it is hard to capture this component of maximum correlation between X and Y, as analyzed in representational maximum correlation (Section 4.2p. Fig. (b) plots the per-class accuracy with increasing for running the Conditional Entropy Bottleneck (Fischer 2018) (another variational bound on IB). We see that the first two predicted phase transition points Mi .f closely match the observed onset of learning class 3 and class O. Class is observed to learn earlier than expected, possibly due to the gap between the variational IB objective and the true objective in continuous settings. By looking at the confusion matrix for the label noise (Fig. 7) we see that the ordering of onset of learning: class 2, 3, 0. 1, corresponds exactly to the decreasing diagonal element p(ğ = 1yy = 1) (increasing noise) of the classes, and predicted, class has much smaller diagonal element p(ū 1ly 1) than the other three classes, which makes much more difficult to learn. This ordering classes by difficulty what representational maximum correlation predicts.

---

where accuracy Published as a conference paper at ICLR 2020
30
XV-A
23
12
10
15
26
35
30
35
60
(a)
(b)
(c)
Figure 4: (a) Accumulated Glp3(2la)) vs. B by running Alg. with varying starting 3 (blue dots). Also plotted are predicted phase transition points. (b) [(x; Z) and I(Y; 2) vs. 8. The manually- identified phase transition points are labelled with arrows. The vertical black lines are the phase transitions identified by Alg. [1] denoted as Pi. ..... gg. from left to right. (c) Accuracy vs. f with the same sets of points identified. The most interesting region right before 3 decreases with B. Alg. identifies both sides of that region, as well as points at or near all of the early obvious phase transitions. also seems to miss later transitions, possibly due to the gap between the variational IB objective and the true IB objective in continuous settings.
6.3 CIFARIO DATASET
Finally, we investigate the CIFARIO experiment from Section The details of the experimental setup are described in Appendix[] This experiment stretches the current limits of our discrete approximation the underlying continuous representation being learned by the models. Nevertheless, we can see in Fig. 4 that many of the visible empirical phase transitions the onset of learning is predicted quite accurately; the large interval between the predicted 33 = 1.21 and B4 1.61 corresponds well to the continuous increase of I(X; Z) and I(Y: Z) the same interval. And Alg. able to identify many dense transitions not obviously seen by just looking at I(Y; Z) vs. curve alone. Alg. predicts 9 phase transitions, exactly equal to | 1 for CIFAR1O.
tightly identified by Alg. [ Particularly,
CONCLUSION
In this work, we observe and study the phase transitions in IB vary B. We introduce the definition for IB phase transitions, and based on derive a formula that gives a practical condition for IB phase transitions. We further understand the formula via Jensen's inequality and representational maximum correlation. We reveal the close interplay between the IB objective, the dataset and the learned representation, as each phase transition is learning a nonlinear maximum correlation component in the orthogonal space of the learned representation. We present an algorithm for finding the phase transitions, and show that it gives tight matches with observed phase transitions in categorical datasets, predicts onset of learning new classes and class difficulty in MNIST, and predicts prominent transitions CIFAR 10 experiments. This work is a first theoretical step towards deeper understanding of the phenomenon of phase transitions in the Information Bottleneck. We believe our approach will be applicable to other "trade-off" objectives, like 3- 3-VAE (Higgins et al. 2017) and InfoDropout (Achille & Soatto 2018a), where the model's ability to predict is balanced against a measure complexity.
8
ACKNOWLEDGEMEENTS
The authors would like to thank Alex Alemi, Kevin Murphy, Sergey Ioffe, Isaac Chuang and Max Tegmark for helpful discussions.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Alessandro Achille and Stefano Soatto. Hmergence of invariance and disentanglement in deep representations. The Journal of Machine Learning Research, 19(1):1447-1880, 2018a.
Alessandro Achille and Stefano Soatto. Information dropout: Learning optimal representations through noisy computation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018b.
Alessandro Achille, Glen Mbeng, and Stefano Soatto. The dynamics of differential learning i: Information-dynamies and task reachability, arXiv preprini
2018.
Alexander A Alemi, lan Fischer, Joshua V Dillon, and Kevin Murphy. Deep variational information bottleneck. arXiv preprint 161.:0161, 2016.
Venkat Anantharam, Amin Gohari, Sudcep Kamath, and Chandra Nair. On maximal correlation, hypereontracttvity, and the data processing inequality studied by erkip and cover. arXiv preprint arXiv: 2013.
Richard Blahut. Computation of channel capacity and rate-distortion functions. IEEE transactions Information Theory, 18(4):460-44 473, 1972.
Gal Chechik, Amir Globerson, Naftali Tishby, and Yair Weiss. Information bottleneck for gaussian variables. Journal of machine learning research, 6(Jan):155-18,, 2005.
Ekin D Cubuk, Barret Zoph. Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment:
Learning augmentation policies from data. arXiv preprint arX1v:1805.0950,, 2018.
Ian Fischer. The conditional entropy bottleneck, 2018. URL openreview. www.nnneefffoememm IkVOXhAqY7
Anirudh Goyal, Riashat Islam, Daniel Strouse, Zafarali Ahmed, Matthew Botvinick, Hugo Larochelle, Sergey Levine, and Yoshua Bengio. Infobot: Transfer and exploration via the information bottleneck. arXiv preprint /901. 10902, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with a constrained variational framework. In International Conference Learning Representations, 2017. URL
Harold Hotelling, Relations between two sets of variates. In Breakthroughs in statistics, pp. 162-190. Springer, 1992.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. URL http::////.axx...g..../// abb/111 6980
Diederik Kingma and Max Welling. Auto-encoding variational bayes. 14 2013.
arXiv preprint
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, CIFAR, 2009.
Xue Bin Peng, Angjoo Kanazawa, Sam Toyer, Pieter Abbeel, and Sergey Levine. Variational discriminator bottleneck: Improving imitation learning, inverse rl, and gans by constraining information flow. arXiv preprint arXiv:/810.0082/,, 2018.
Mélanie Rey and Volker Roth. Meta-gaussian information bottleneck. In Advances in Neural Information Processing Systems, pp. 1916-1924 2012.
Danilo Jimenez. Rezende and Fabio Viola. Taming VAEs. arXiv preprint
2018
11

---

Published as a conference paper at ICLR 2020
Ohad Shamir, Sivan Sabato, and Naftali Tishby. Learning and generalization with the information bottleneck. Theoretical Computer Science, 41 ((22-30):2696222)) 2711,, 2010.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-aware unsupervised discovery of skills. arXiv preprint arXiv:7907.01657 2019.
DJ Strouse and David Schwab. The deterministic information bottleneck. Neural computation, 29 (6):161111300 2017a.
DJ Strouse and David J Schwab. The information bottleneck and geometric clustering. arXiv preprint arXiv:1712.099557, 2017b.
Max Tegmark and Tailin Wu. Pareto-optimal data compression for binary classification tasks. arXiv preprint arXiv:1908.00 1908:0808...1111 2019.
Naftali Tishby. Lecture: the information theory of deep neural networks: the sta-
tistical physics aspects. https://www. htt::://wwwwwp.. o htt.:pppwcettrrrisiiiieetcaaaooo
2018.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physiccs0004057, 2000.
Tailin Wu, lan Fischer, Isaac Chuang, and Max Tegmark. Learnability for the information bottleneck. arXiv preprint arXiv:190..07331, 2019.
Zagoruyko and Komodakis. Wide Residual Networks. arXiv: 1605.07146, 2016.
Pablo Zegers. Fisher information properties. Entropy, 17(7):911-49399 2015.
12

---

Published as a conference paper at ICLR 2020
Appendix
A CALCULUS OF VARIATIONS AT ANY ORDER OF IB [B((p(2(>)]
Here prove the Lemma 2.1 which will be crucial in the lemmas and theorems in this paper that follows.
Lemma 2.1. For a relative perurbation r(2(=) E Oz x for p(2[x),, where r(2[x) satisfies [= have that the IB objective can be expanded
(1 [B,||(2|<)]] +
E Expspp(a,s) [x]/r)log p(z|x)
((eew))oog p(=ly)
) p(z)
3 p..xp((
p(z)
(- ((B(r() - (l)r 3 (EErr - {(rr(=)))}
(n - 1)
n=2
(E.xpp(ans)) [(2|r)]og p(2|z)
r(zly)]og p(210)]
IB B/[p(2|x)] +
p(z) - 3 S-EEp By.=~((u.=)
p(2)
1.2 (2)r) - E(rr(x))) - 8 (8(r((2)00 (=)))
e²
(1))) (z)) 8 (xw)
2.3
3.4 (1)) B
(12)
where r(2ly) Eegpppall w) [+(][=])] and ((2) p( [=((==)) The expectations in the equations all w.r.t all variables. For example [x|((=|=)] E )r (2]x)).
Proof. Suppose that we perform relative perturbation r(zlz) on p(z|z) such that the perturbed conditional probability is ps (2|2z = p(2(2) (1 + e r((l))))) then we have
p'()) p(x))'( (2(x))r= drp(z))((2z))
p(z) te. dap(t))((al)))(aa))
Therefore, can denote the corresponding relative perturbation r(z) on p(z) as
r(z) 1 1p p(=) p(=)
p(z)
ʃ dappa))(sla)r(all)- = E. Ex
Similarly, we have
2))
p(y) /
dxp(e.))p(z1p) ()(()()) e r(((=)) p(21g) + p(v) / drp(a,)))(ela))
p'(zly) p(y)
And we can denote the corresponding relative perturbation r(zl)) on p(zl)) as
r(zly) = (=lp)) p(zly)
p(zlv)p(y) /
dæp((z, vtpple.))((eaar(all = En
p(zly)
Since
--: / dzdzp(æ, z 2)g p(2|z) B.
dydzply, e)g p(zlv) p(2l)) p(2)
IBo[p(z[x)] = -
p(2)
13

---

Published as a conference paper at ICLR 2020
We have
IB, (Bal2(=(<) = (Bslo(z)o)(1 + +
(adep(z))p (2(x))
f((2) - 3. (oylap(u)'(=lll))og ('(2))
p'(z)
fʃ (1 (2)))))))) (12))) +c.
p(=) +e.)))
- -B. ( - +
(c.
[ (Idep(s)p(zla)(( (z)r()))
log (<2|=)
+ log (1 (( - log (1
p(z)
-B. - d r(ll)) log p(=ly) + log (1 (e r(zl)) log (1 + (
p(z)
= -ʃ
log p(2(xr) p(z)
+ 2
(-1)m-1e (r(z|z) r(=))
n
n=1
- -B. f dydgeppppupptteelll ( r(ll)))
log p(zly)
+ Σ
80
(r(zly) - r(())) (-1)
m
p(2)
n
The 00th-oder term is simply IB [B=(=() The first order term is
3IBs|p(z|<) = (Eesspplass) r(2/2))og p(=[x) p(z) - B- E p.
(2 p(aly))
p(=) )
The th -odde term for n is
=(-1)"²" / dodep(a))pzlo) (-1 (sl)))) (())
n 1 (2|x)) r0()))
1
/dddep())p(zl)) ( (-2 +r(z/y) (2 (m))
- - (-1)-e""
(-1)"e"
n(n 1)) (Eexsx))ta.sl - (())))))))) (z)] -nnllim((npppppppp
1)lE (2)))
(-1)me"
B n(n - (r (Bt (x) (n (r=x
(-1)"e" Eir" (BB
n(n 1)
In the last equality we have used
(((=)))) (=)] = Essp(=) (E) = P = Es (r")
Combining the terms with all orders, we have
IBa[p(2|x) + r(2[2))]
((=|sr)log p(z|z) p(z)
p(ayy)
-IBa[p(2(x) +e-
B- E Ey.e<p(u.s)
((zly)log
p(=)
(-1)"e²
n=2 n(n - -br" - B (IIr" (x)")))
14

---

Published as a conference paper at ICLR 2020
As side note, the KL-divergence between p'(2))) p(21x)(1 te. re-r(z))) and p(z|z) is
+1 (1 +c.r(z))))
KL (1((e)))
p(z|z)
/ dap(=/<)( +6-r(2)))) (
(.((2/)) _ 2
(=lc)) + +((2)
2
2² / d=p(z//))(((zx) 2
(c)() 0(2)
2 (xle)) 0((5))
Therefore, to the second order, have
Ex-p(a) [KL (p((sl=))ll(<xx)) _-
2² (2(=)
(13)
Similarly, have (xp [KL (p(z|=)]l (z|x)) up the second order. Using similar procedure, we have up to the second-order,
= Ey-p(r) KL (p<e\w)ll(())))) = ?
By-p(r) KL (p((lv))lp<=)e))
2 (212)
KL (+'(2)llp())) KL (p())))()()) [[]
B PROOF OF LEMMA 0.1
Proof. From Lemma
we have
8 (1(p))((2)))
-Err())) B -E))))))
(14)
The condition of is equivalent to Using Jensen's 's inequality and the convexity of the square function, we have
vr(z|0) E @zj (II,)(((=/=)) 2
(15)
Vr(z|æ) Qzix, 3
- -(>>())
(16)
E (zly] = E Ey.emp().s)
Ey-p(ulz) (B (Bree)
Ez-p(()
> E
(By-p(yle) B (r)e))
Espp(*)
E[rr(=))
The equality holds iff r(2ly) Ex-pptr [r(2[xr]] is constant w.r.t. y. for any
Using Jensen's inequality on [=)) we have E[r)(=)] = EEmp(() (Bee))aa s
Ez<p(z) [Ex=p(ats)(?(( = (2(x() where the equality holds iff r(2(2) is constant w.r.t. x for any
15

---

Published as a conference paper at ICLR 2020
When E| (2lv)] - (2) O, we have that the condition Eq. (66 is equivalent to Vr(222) 221x, 8 - Br
- i.e.
(1))( - (x) r(al))eRzix (x (z)
B S G|p([/=) inf
(17)
where r(=ly) [==p(=/v.=) [=[[=)] and r(z) = (m=
((r(()))) - [=)] = substituting into Eq. (16). we have
8.0 (2(x) (x)
(18)
which is always true due to that EE (=|x0]] 2 (=)], and will be looser condition than Eq. 17
above. Above all, we have Eq.
Empirical estimate of G|p(z[=)] empirically estimate G|p(z|=)) from a minibatch of {( v)), ....V and the encoder p(z[æ), we make the following Monte Carlo im- portance sampling estimation, where we use the samples {x₂} ~ p(z) and also get samples of {2i) p(2) p==))(=2(r) and have:
Eg,z=p((r [=(()= (= = dzdzp(z)pp2) p(x,=) (2(2(x
p(z)p(z)
plz,, 2)
1 (2)1z,)
p(z,)p(Z))
(r= =E =E zxp(=>
( (Ba+)))
( dxp(al=)))(a(z))
2
( dap((>) p(Zel(t) r(z((z))
p(2s)
N
p(zz(1z5)
r(2)(1z)
N j=1
p(z))
N
p(2)21z))
((2)22;))
N
E p(2 2 p( p(z))))) 1
j=1
N
16

---

Published as a conference paper at ICLR 2020
E p. [r2(xl = (ypepplnne)
1 ddappuunidttwwllaaaaaabbat (p(ri. z:)
/
Σ
dapp (wpppt)pppu
(m) ( p(2
E0, p()))
Dj= p(z 1 1ys = =yp
[ = Mil
N
Here (y:) denotes the set of x examples that has label of ye. and [-) is an indicator function that takes value if its argument is true, O otherwise.
The requirement of E [x (=(2 [2[=r] = yields
E (x)n((t)))(((a))) dzp(=) p(z|z) p(z) r(21z) =
N p(,](,,) p(z))
r (2z) (22))
(19)
for any Tz--
Combining all terms, we have that the empirical ([p(2|1)) is given by
EN pla,ke ((als,))
N E En
p (2)lz;)) - Em= p(a))((2))
Σx p(z)(1))
G[p(2|=)]
inf
2
2 (o Ex ((glos))
ii
(20)
where {2,} ~ p(2) and {x+} ~ p(z). It is also possible to use different distributions for importance sampling, which will results in different formulas for empirical estimation of G[p(z[x)).
C Gelpe(z(x)) FOR PARAMETERIZED DISTRIBUTION pa(z(x)
Proof. For the parameterized Pa (2|2)) with e O, after 6' + 0 + A0. where Ae e θ is an infinitesimal perturbation on O, we have that the distribution changes from po (=(pr) to po+ p0+20
IIn this paper, (01, 02 0x))T and
(va(alm) de
(pg((ala) 201
2po(=le) 062 .... 89g
@po(sla)
are all column
vectors. (ana(zia) is l: & matrix with (i.7) element of 0² (=llm))) 288
08:00;
NNoe that since O is field, it closed under subtraction, have A0 E e.
17

---

Published as a conference paper at ICLR 2020
and thus the relative perturbation pe (2|2r) is
e r-r(2/ P0+A0 pe
p=(=
(2(2222) + ~ Opo (2|z)
~0T 0 pr
AO + +0 - po (2/22)
pe (2|(r
00
002
= ~00"= 0
0º pp((z)
logra (=|ær) + 2
0O + 0111001)))
00
Po
(=(2)))
002
where | is the norm of A in the parameter field e.
Similarly, we have
('po(=lv)
e-r(zly) = A0" log poppol (=lv) +
A
AO + 001400)))
00
Po(=lu)
002
+ -eT Po(oz)
1
e r.r(z) A log log
AO + +011001))
00
2
Pe (z)
002
Substituting the above expressions into the expansion of [B<sp(=] in Eq. 12) and preserving to the second order | 2 we have
(=)x)) + (((())))
IB IBolpe (=|æ)] + (eeero(eie r(2l2))ogg (2(x)x)
r(21y)log Po(2|1))
B (o (vi2)
(2(2)
p2(2)
+ 1.2 (Bensn-o((as))
- Ezznno
(x))) (r
33 (Byyz-no (1.
[r (2|1)] - E -z-po()) (/ (2)())
A0T 2
0² (2po(z(x)
log po(2|rr)
=IB 1B, (2|2²) + (mp
log log (2(xx)
+ A0T
A0
00
2
Po(2|z) x))
002
po (z
AoT d
0a (2o(2
log po (2(1))
8-
log po + ~00
AO
00
(=(z)y)
002
pa
~ δ 00
27
AOT a
log po(p)())))
E Ezmpo(=)
log
30
8
(y.sopo(vvs)
A0 ②
log log
27
E Ex)po(s)
A0
θ log log
2
00
00
Po (=(2) a log
log po(2(z) θ po(2) 00 logno (=|10)
-IBr(po(2(x3]
A0T
E Bx,snpo((..)
logno (2|or)
-B E Ex,eeppo((,)
(=) 00
~00 { (Iz) [z)) -3 - [z)) A0
2
In the last equality we have used Ex,z~pa(x. (o() 80 d²
8 pppa(=
= dæp(x) 8² depo(z(<) = pPe
f drp(2) a02 O, and similarly Ey,zrpo(y. Po (=
In other words, the | terms in the first-order variation 8IB / 2/))] vanish, and the remaining || are all is the (Blggna (Zlggn (z(ar) T 80
0.
802
in I'I s ()). Also in the last expression. Iz 0 = f (z)o
(logpe(s) 80
(loggo(a) 80
Fisher information matrix of 0 for 7, I2 (0) =
x:)
(Hagga(=)ax)
80
Izj (0) dydzp(y)pe (zly) (Bagga(=(y)
(logpe(z)y) 80 are the conditional Fisher information
80
matrix (Zegers) 2015) of 0 for Z conditioned on X and Y. respectively.
18

---

Published as a conference paper at ICLR 2020
Let us look at
1 -000' (z) (Iz]x(0) Iz(0))) Ao
8 (B
(21)
2
Firstly, note that 8 FIBB:lpo( (2 []]] is quadratic function 20, and the scale of AO does not change the sign of 3 (2[z)], so the condition of Aλ4 E θ, 1B (p 2 is invariant to
the scale of A0, and is describing the "curvature" in the infinitesimal neighborhood of 0. There- fore, AO can explore any value O. Secondly, we see that Eq. (2T) special case of Eq. 14 with c r(2ax) = A0"
[z|r( (z)) ae log po((a)) Therefore, The inequalities due to Jensen still hold: AOT (I) - [z)) AO 2 0, c² (B[r" - E(r) = o -0) AO 2 O. If AO" (IZ)r Iz Iz())) AO 0, then the condition of AAA E θ, (1))) 2 0 is equivalent to 42O E θ
AO (Izzx (0) In (0) AO
B < N0T (Iz Iz (0) AB
i.e
AO (I2)x I2( A0 AOES AOT (IZzr Iz [z)) AO
8 Golpo(z|o)]
inf
(22)
AOT (0) - Ix)) AO = 0, we have that Eq. 21 always holds, which is looser condition than Eq. (22). Above all, we have that the condition of AAO θ 8BIB (z/²)] equivalent to Ge po (2|z)]
Moreover, (G) given by Eq. 22 has the format of generalized Rayleigh quotient A0" Ase where = Iz ( (0) and = Iz (0) (0) are both Hermitian @ which can be reduced to Rayleigh quotient R(D, AT))) = (C* 20) D Ao)
R(A, B:z) = 20 BA0 matrices
(C" 20) (C A0; with the transformation D = C=-TA((T)-- where CC is the Cholesky decomposition of x
(0). Moreover, we have that when (elpo(((z>)) attains its minimum value, the Reyleigh quotient R(D, CT A0) attains its maximum value of Amax with C AO Umax, i.c. A0 where Amax is the largest eigenvalue of and Umax the corresponding eigenvector.
(CT)
Umax
D PROOF OF THEOREM
Proof. Define
(3()') inf (E)(r Ex)r - B¹. (Egl> - Eg(r> r(slz)e@aix
(23)
where E31-] denotes taking expectation w.r.t. the optimal solution (. v, p(=, p(a, at B. Using Lemma 2.1 we have that the IB phase transition as defined in Definition corresponds to satisfying the following two equations:
(3( 2
(24)
lim B
T3(3") = 0
(25)
Now prove that (33)") is continuous at B B, i.c. Ve 0. 38 S.t. V3 (8 8,8 8), have [Ta(8') - [B) e.
'Hrr all the Fisher information matrices real symmetric, thus Hermitian.
19

---

Published as a conference paper at ICLR 2020
From Eq. (23) we have -To()) -33' 3) (Ba[r"(zlb)]
(3) - E3 (z]r) Since r(2(x) is
bounded, i.e. AM > s.t. 422 E 2, E |r(/a/))) M, we have
Ep (=1v)]] = [B (Em-ptalus)) [r(2|2)]) |] - Es (En-p(alus)) [M]] M22
Similarly, we have
[p [z)] = Eg (Ezmp(slz) (r(2|=))) |] - Es (Bemp(al=) [M1)*]] = 122
Hence, [Ta(5' - [T(3)] = 13' - -33 Eslr Eg(r"
- 2|33" - -31M2.
To prove that (3') is continuous at 3' B, we have Vs > 0, 36 2N
s.t. 4B
(B 31-6,7 6.3 - 5), we have
(Ta(0') - T3( s 2/3' B1M² 28M
M E
2M
Hence (8') is continuous 33' =3.
Combining the continuity of T at 8 = B, and Eq. equivalent to Glg)(alz>) after simple manipulation.
24 and 25 we have Tg(3) = 0, which is
E INVARIANCE OF (2((2))))(2)1x TO ADDITION OF A GLOBAL REPRESENTATION
Here prove the following lemma:
Lemma 2.2. (|r(sl=):p</=)) defined in Lemma 0.1 is invariant to the transformation r' (=|æ) + (z((z)+55 5()).
Proof. When we r(2|z) is shifted by global transformation (=(=)) <- r(=(=)) + s(2), we have (z) + (x=p(e)s)((((zz)) + s())] = [=-=[t))] + 5(2)
= r(2) + s(x), and
similarly ('(2)) r(al)) + s(2).
The numerator of G[r(2])): is then
(r'(=|=)))* Ex-p(e) [v'()))]]
E Eg,
-E -g,,op((n.)
(r(s)2)) + =()))²] - Benp(e) (r(=) + s()))²
(B (Bn,z~((z,.)
[>²()|x)] - 21 2E, (r(2)z)s(2)) + Enpswpla.)) [x)))
(Esnp(s)
[r²(z) + -) (x(=)s(2)) + E Expp(=) (x)())))
(E (xxxx)(( [-²(=|=)] - 2E
|s( B ( [r(:|=]]] + Bemp(a) [ (x)))
(Eznp(z) [r²(z) + +2E=~((s) |r(2 (z)s(z))) Expp(=) (x)))
(Eg,swp(z.e) [r2()[x)] - 2E (p)) [r())a(=)] + Espp(s) [>²()))
(Eenp(*) [r²(=]] + 2R +F2F5ppa [+())s(=)] + Esppte) [>)()))
-Er,z=p(r..)) [2]())) - E2-p(z) [+)())
Symmetrically, we have
By,2~p((..) (+'(2l1))*] Exnp(s) (r(2))) Eg.z))((.s) [+((v])]] Es-p(z) [r²
F..nn((n.s) (=(m)) R Pampea) (+)
Therefore, ((((2]
is invariant to r'(2)z) f r(2lx) +
By.s<p(v.e) (= w) Bem [=]]
s(2).
20

---

Published as a conference paper at ICLR 2020
F PROOF OF THEOREM 2
Proof. Using the condition of the theorem, we have that Vr(2|z) e 221x there exists rz(z)z) 2zix and s(2) {a - IR|s Is bounded] s.t. r(2(z) r=(2)) + s(2). Note that the only difference between 22ix and 2 is that 22ir requires (p 0. Using Lemma 2.2 we have
inf p] 2
=
inf (1
(|m<sl)):=<(lar) - G[p()|=)]
where r(=[z)) doesn't it have the constraint of B =0
After dropping the constraint of [xxp(s|==](((zx)) Bx=p((==) [=[[==]] 0 (since can perform the transformation (2(2)) r(z(x) r(z), so that
O, again using Lemma 2.2 we can let r(=)
the new r' (2) = 0). Now get simpler formula for G[p(2[z)). as follows:
Ex,enp(e, /r (2|xr)
G|p(s|>)] =
inf 2( 2| E. pxppp())
(26)
(B (Benp)ehhb
where 22 = (r: X' 2 Ex- (r = 0, bounded].
From Eq. 26
further require that E Ep (r2
Define
(xx = sup
[[ 20|Y, 21)
sup
By.z~p(vis) (f x)]) =)
(27)
where 2 x = fr
X xx:Xx 2 + [ 0, (1 1, bounded).
Comparing with Fq. 2 immediately follows that
G[p(z|=)] (e(X,Y:2)
(i) We only have to prove that 2)
px px, 22), where pr (Y, 2) is defined in Defini-
tion 4
We have
(V(X,2)g(Y,
dzdydzp(z v v. 2)
/ dydzply, 2)g(v. 2)
dop(ely,
/ dydzply. () 2)
s/ / dydzp(u.
/ dydap(y, 2) F2
2) dydep(u:)))
where Fly, 2) == f drp(xly, 2zf z). We have used Cauchy-Schwar inequality, where the equal- ity holds when g(u, =) of (y, z) for some a. Since Eyg"(y, =)] = 1, we have (2 1.
In the definition of pr(X, Y; Z), we have used an equivalent format f(r, 2) instead of r(=[z).
21

---

Published as a conference paper at ICLR 2020
Taking the supremum of (EIf(X, (), 2) w.r.t. and 9, we have Z)) Z)))
(X,
sup
((())2)).
dydzp(y, dydzp(y,z)g (ys z) I dydzply, d) =){?(1,))
sup ((
dydzply, =) F)
sup
f(1,))0
(ʃ 21)x (()])(X
sup (
dydzply, =)
sup 5(X,Z)e0 (2)
(X;
Here S is defined in Definition values. Therefore,
By definition both (r Y; and (x 2) take non-negative
P. =xx
(28)
(ii) Using the definition of px(XXY;; 2), we have
(xXXY;
[ dydzp(u, (fappalo.:))s(..
sup =(=
deple) / dep(vle) ( dap(alu.
sup (1 21x
d=p(2)W([(<==2) ((
= sup
where Wif(x, = dyp(y/z) (J dxp(=ly, 2) (xx, 2))²
Denote c(z) == p(=)((()))))) p<=))==ppl) ( (z, =}],
have c(22)d B ex (f2 2)] Then the
supremum yx sup I da( 2)] is equivalent the following two-stage
supremum:
sup c(x):f c(s)de=1 2(X,Y:Z)
dzp(z)
sup Wif(r,2)
(29)
( Zix
where 2/2 = x RR
Ex-plets ([(r,
c(=)
E =]] = 0, f bounded]
We think of the inner supremum sup (1 (ff(x,)) only x. for some given
Now let's consider another supremum:
sup I (dppbult) (f (cop(alu,=))(())
(30)
b
where (/21 (h X + R
[p()))))(=)] 0, Eptr =) [1)(2x) 1, bounded). Using similar technique in (ii), it is easy to prove that it equals p (X, ZIZ) as defined in Definition
22

---

Published as a conference paper at ICLR 2020
Comparing Eq. (30) and the supremum:
sup ((
we see that the only difference is that the latter [x)p (x, (f) 2)] equals c(a)
instead of 1. Since p(a)
W[[(x, =)] is quadratic functional of f(x we have
c(z) p (X,
sup ((r,))
w[f(z,z)]
p(z)
Therefore,
Pr (x))
sup c(>): c(=)d==1
dz dzp(z)
sup W[[(x;
(1 2
/ dz dzp(2) C(2)
sup d(z): o(=)d==1
Pm (X, Y1Z)
p(2)
sup c(*): c(=)d==1
dzc(z) IZ = =)
sup Pm (X, 2
zez
where in the last equality we have let c(z) have "mass" only on the place where p², (X,Y =) attains supremum w.r.t.
(iii) When Z is continuous variable, let f(z,2) = fx(x) 6(=-20) pl=) where 6(-) is the Dirac-delta
function, is parameter, fx(x) E 2/ with 2 (/x X - R fx bounded; 4Z 2
(xx = 0, XxEx [f3 = 1}. We have
E Expp(e))) ([(,, = p(xr==) z)dæ
8(2 - 20)
/ p(x)2))x(()dz
p(z)
6(2 10--00 =0)
p(2) 0
0
And
BX = / p(1,, 2) z)dxd=
I p(x, 2)13 5(z 20)
drdz
p(2)
I |dz0(= 20) / ddxpl(2)) (x)dx
/ dzø(2 20) -1
=1
Therefore, such constructed f(x, 2) fx(x))
A(= zo
E ( 2|x satisfying the requirement for
p(a)
Px(X, Y; Z) (which equals (xXX Y; by Eq.
28
23

---

Published as a conference paper at ICLR 2020
Substituting in the special form of fax 2) into the expression of (x, 2) in Eq. (27). have
/ deple)
/ dep(ulz) ( drp(zty,2)f(z.
2
sup 315-30 pla)
2
dzp(z) / dgp(ull)) ( x12
6(z 20) p(z)
sup (x(m)
sup / dzp(2) 8(2 20)
/ duplulz) (J d 1x(1)=0112
2
sup
p(z)
/ dzó(z 20)
sup =002
= Ix(N)ERf1
sup
/
d2ō(2 Pm (X,Y 2)
sup soEZ
sup pm (X, 2 = 20)
#gE2
sup Pm (X, Y1Z) ZEZ
We can identify sup (X)) XX = 2]) = with (X, = 2) because
(x) satisfies the requirement for conditional maximum correlation that Eppe [/x (x)) 0 and
Ep(e (x) for any z, and using the same technique in (i), is straightforward prove that sup, fx ( (X Z 2 2] equals the conditional maximum correlation as defined in Definition
Since the conditional maximum correlation can be viewed as the maximum correlation between X and Y. where X, Y p(X, Y|Z), using the equality of (Bo[h(z))) et al. )2019), we can identify the h(x)) in 3u [x()] with the fx (X) here, and an optimal fx (X) that maximizes P (X, Y 2) is also an optimal (x) that minimizes (o[h(r)].
p (X; Y) (Eq. in Wu
( p(z.g/=)
(iv) For discrete X, Y and 7 and given Z 2, let QX,YZ
(VD(ele)p(wi)))
x.
p(a.y) Vp(e)p(e)
V
p(sle) p(el))
we first prove that its second largest singular value is (X, YIZ) =
2,y
sup E Bewsptaetel ((())())))))))))))))))))))))) (S2 is defined in Definition (f.9)e8,
Let column vectors ii p()))) and ii V p(y|=) (note that = is given and fixed). Also let
U2 = f(x) and 82 = g v p(y|z). Denote inner product (u, v) = Σ, 4ae, and the length
of a vector as ||n|| = / (u, u). We have ||w||| = 1|22 = 1 due to the normalization of probability.
| = | = 1 due to E Ex-p(r))) (f((() = Ey--ptrl= [x) = 1, and (u,, u2) = (U1, 02) 0
due to E. Ex-p(r))) [f()]] = 1g = O. Furthermore, we have
Bxsrolle = max df Qx,Yizu 0,8
sup (f-g)eS,
which is exactly the second largest singular value o2(Z) of the matrix Qx,rız Using the result in (ii), have that or (X, YX Z)
max (Z). Z=2
24

---

Published as a conference paper at ICLR 2020
G SUBSET SEPARATION AT PHASE TRANSITIONS
In this section we study the behavior of p(=(z) on the phase transitions. We the same categorical dataset (where X = |Y| = | = and p(x) is uniform, and p(y|z) is given in Fig. 5). In Fig. we show the p(z|z) on the simplex before and after each phase transition. We see that the first phase transition corresponds to the separation of r 2 (belonging to 2) w.rt. z E {0, 1 (belonging to classes // E (0, 1},, on the p(2[2) simplex. The second phase transition corresponds to the separation of x: = 0 with æ: = 1. Therefore, each phase transition corresponds to the ability to distinguish subset of examples, and learning of new classes.
H MNIST EXPERIMENT DETAILS
We use the MNIST training examples with class 0, 2, with a hidden label-noise matrix as given in Fig. 7 based on which at each minibatch we dynamically sample the observed label. We use conditional entropy bottleneck (CEB) (Fischer 2018)) as the variational IB objective, and run multiple independent instances with different the target 3. We jump start learning by started training at 3 = 100 for 100 epochs, annealing 3 from 100 down to the target | over 600 epochs, and continue to train at the target epoch for another 800 epochs. The encoder is a three-layer neural net, where each hidden layer has 512 neurons and Re activation, and the last layer has linear activation. The classifier p(y] z) is a 2-layer neural net with a 128-neuron ReLUU hidden layer. The backward encoder p(zly) is also 2-layer neural net with 128-neuron ReLU hidden layer. We trained with Adam (Kingma & Welling, 2013) at learning rate of 10-3 and anneal down with factor 1/(1 + 0.01 epoch). For Alg. for the to 1.
the same architecture as the encoder of CEB, and use |Z| 50 in Alg.
I CIFARIO EXPERIMENT DETAILS
We the same CIFARIO class confusion matrix provided in Wu et al. (2019) generate noisy labels with about 20% label noise on average (reproduced in Table 1). We trained 28 x Wide ResNet (He al. 2016 Zagoruyko & Komodakis 2016) models using the open source implementa- tion from Cubuk et al. (2018) as encoders for the Variational Information Bottleneck (VIB) (Alemi al. 2016). The 10 dimensional output of the encoder parameterized mean-field Gaussian with unit covariance. Samples from the encoder were passed to the classifier, a 2 layer MIP. The marginal distributions were mixtures of 500 fully covariate 10-dimensional Gaussians, all parameters of which trained.
With this standard model, we trained 251 different models at 3 from 1.0 to 6.0 with step size 0.02. As in Wu et al. (2019), we jump-start learning by annealing 3 from 100 down to the target 3. We do this over the first 4000 steps of training. The models continued to train for another 56,000 gradient base learning
steps after that, total of 600 epochs. We trained with Adam (Kingma & Bal 2015)) rate of 10 -3, and reduced the learning rate by a factor of 0.5 at 300, 400, and 500 epochs. The models converged to essentially their final accuracy within 40,000 gradient steps, and then remained stable.
08
0.700
0.150
0.150
07
0.300
0.500
0.200
95
03
0.075
0.025
0.900
Figure 5: p(y|z) for the categorical dataset in Fig. and Fig. denotes p(u j/æ i). p(x:) is uniform.
The value 7th row and jth column
25

---

Published as a conference paper at ICLR 2020
0.30
0.25
0.20
((Y:2)
0.15
0.10
I(Y:Z)
0.05
86
8i
0.00
8
B
(a)
0.2
0.2
21 94
REg 24
(b)
(c)
(d)
(c)
Figure 6: (a) T(Y; Z) for the dataset given in Fig. The phase transitions are marked with
vertical dashed line, with 3 = 2.065571 and oi = 5.623333. (b)-(c) Optimal (z(xz) for four values of B, i.e. (b) B = 2.060, (c) 8 = 2.070, (d) = 5.620 (e) B 5.625 (their 8 values are also marked in (a)), where each marker denotes p(z |/x i) for given {0, 1, 2).
26

---

Published as a conference paper at ICLR 2020
0.150
077
0.200
0.500
0.200
0.100
95
9A
0.050
0.025
0.900
0.025
03
02
0.025
0.975
0.100
Figure 7: Confusion matrix for MNIST experiment. The value in 2t row and jth column denotes p = jly i) for the label noise.
The accuracies reported in Figure are averaged across five passes over the training set. We use Z
50 in Alg. 1.
Table Class confusion matrix used in CIFARIO experiments. reproduced from (Wu et al. 2019). The value in row i, column means for class i, the probability of labeling it as class j. The mean confusion across the classes 20%.
Plane
Auto.
Bird
Cat
Deer
Dog
Frog
Horse
Ship
Truck
Plane
0.82232
0.00238
0.021
0.00069
0.00108
0.00017
0.00019
0.1473
0.00489
Auto.
0.00233
0.83419
0.00009
0.00011
0
0.00001
0.00002
0.00946
0.15379
Bird
0.03139
0.00026
0.76082
0.0095
0.07764
0.01389
0.1031
0.00309
0.00031
0
Cat
0.00096
0.0001
0.00273
0.69325
0,00557
0.28067
0,01471
0.00191
0.00002
0.0001
Deer 0.00199
0
0.03866
0.00542
0.83435
0.01273
0.02567
0.08066
0.00052
0.00001
Dog
0.00004
0.00391
0,2498
0.00531
0.73191
0.00477
0.00423
0.00001
Frog 0.00067
0.00008
0.06303
0.05025
0.0337
0.00842
0.8433
0.00054
Horse
0.00157
0.00006
0.00649
0.00295
0.13058
0.02287
0.83328
0.00023
0.00196
Ship
0.1288
0.01668
0.00029
0.00002
0.00164
0,00006
0.00027
0,00017
0.83385
0.01822
Truck
0.01007
0.15107
0
0.00015
0.00001
0.00001
0.00048
0.02549
0.81273
27


Reviews:
[{"review_id": "r1gosu5aFB", "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": "In this paper, the authors studied the phase transition in the information bottleneck, which is defined as the point where the IB loss landscape changes. The authors give a theorem showing the practical condition for IB phase transitions which is related to Fisher information. Then an algorithm finding IB phase transitions are proposed and applied to MNIST and CIFAR10 dataset.\n\nThe paper is well-organized. The problem formulation, definition, theorem, algorithm and application form a whole story about finding IB phase transition. However, I found that the motivation of this paper is not very clear. Why do we want to find the IB phase transition accurately by running such a complicated algorithm (Algorithm 1). Usually, the scalar \\beta is considered as a hyperparameter. By tuning \\beta, one can easily produce Figure 1 and see some phase transition points. One can also tune \\beta to learn different classed as shown in Figure 3(b). So designing a complicated coordinate-descent based algorithm to find a parameter seems overkilling the problem.\n\nMoreover, the mathematical part of this paper can be made more accurate. For example, in definition 1, the authors write \"\\eta << \\beta\" and \"|\\epsilon| << 1\", where the quantities \\eta and \\epsilon are used many times in the proof. However,  \"<<\" is not a rigorous mathematical symbol. The authors should consider rewrite their proof by using limit.\n\nTherefore, I think the motivation and the mathematical quality of this paper can be further improved before getting accepted.  ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SklpmME05H", "reviewer": "AnonReviewer4", "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 studies the phase transition problem in the information bottleneck (IB) objective and derives a formula for IB phase transitions. Based on the theory developed in the paper, an algorithm is developed to find phase transition points. The interesting observation is phase transition can correspond to learning new class and this paper conjectures in IB for classification, the number of phase transitions is at most C-1, C the number of classes.  This observation deserves to be further explored and may be a key to a deeper understanding of neural networks. \n\nThe theory developed connects the IB objective, dataset and the representation, and thorough proofs are given.  The experiments matches the theoretical findings. \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "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": "HkgODnIrtr", "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 contributes theoretically to the information bottleneck (IB) principle. In particular, the author(s) provided theoretical reasoning on the phase transition phenomenon: when the beta parameter of IB varies, the generalization performance changes in a stepwise manner rather than continuously. The core result is given by theorem 1: the phase transition betas necessarily satisfy an equation, where the LHS is expressed in terms of an optimal perturbation of the encoding function X->Z.\n\nOverall, the reviewer believes that this work is a solid contribution to the IB principle, and should be accepted. Remarkably, this work gives the first formulation on the phase transition of IB, which was an empirical observation. Furthermore, the author(s) give an algorithm to find the transition betas, which agrees with empirical studies on CIFAR and MNIST datasets.\n\nThe reasons for the weak acceptance instead of a strong acceptance are explained by the following weaknesses.\n\nAs a theoretical contribution, it is important to have good formulations and clear statements. The quality of the mathematical statements is not satisfactory and can be largely improved.\n\nDefinition 1: introduce the concept of relative perturbation first. As a definition, it must be self-contained. Therefore introduce the second-order variation first (don't point to the appendix).\n\nLemma 0.1: inf_r(z|x) \\mathcal{G} \\ge \\beta, is equivalent to \\forall r(z|x), \\mathcal{G}\\ge\\beta, the latter is more elegant. What is \\mathcal{G}, anyway?\n\nLemma 0.2:  State the condition on the scale of the $\\Delta\\theta$. The reviewer suspects that if $\\Delta\\theta$ is large enough, the statement can be violated.  This lemma feels like a digress. Why the Fisher information is needed for explaining the phase transition?\n\nTheorem 1: the statement is fine. It is better to have all conditions/assumptions listed as this is the core theorem. To be more complete, the authors can discuss the number of roots after the theorem and what happens if there is no root. In general, there have to be a few remarks after theorem 1.\n\nDefinition 2: \\rho_r(X,Y;Z) is defined with respect to what? For example, state \"Given a joined distribution p(X,Y), the representation maximum correlation....\". Use a different equivalent symbol for definition, such as \":=\".\n\nTheorem 2: Again, \\forall{f(x,z)} is with respect to what? In the \"if\" part of the \"if-then\" statement, \"\\forall{f(x,z}}, it can be decomposed as ..\" is a false statement, change to \"If f{x,z} can be decomposed\"\n\nIn the abstract, avoid citations, and explain X, Y, Z, p(z|x), for completeness.\n\nAs the paper is over the recommended length,  the reviewer is asked to be harsher in the assessment.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission presents a theoretical study of phase transitions in IB: adjusting the IB parameter leads to step-wise behaviour of the prediction.  Quoting R3: “The core result is given by theorem 1: the phase transition betas necessarily satisfy an equation, where the LHS is expressed in terms of an optimal perturbation of the encoding function X->Z.”
This paper received a borderline review and two votes for weak accept.  The main comment for the borderline review was about the rigor of a proof and the use of << symbols.  The authors have updated the proof using limits as requested, addressing this primary concern.  On the balance, the paper makes a strong contribution to understanding an important learning setting and a contribution to theoretical understanding of the behavior of information bottleneck predictors.  
Decision: Accept (Poster)