Perturbation Theory for the Information Bottleneck
Authors: Vudtiwat Ngampruetikorn
David J. Schwab
Venue: NeurIPS 2021 Poster (2021)
Keywords: Information bottleneck
Perturbation theory
Strong data processing inequality

Abstract: Extracting relevant information from data is crucial for all forms of learning. The information bottleneck (IB) method formalizes this, offering a mathematically precise and conceptually appealing framework for understanding learning phenomena. However the nonlinearity of the IB problem makes it computationally expensive and analytically intractable in general. Here we derive a perturbation theory for the IB method and report the first complete characterization of the learning onset, the limit of maximum relevant information per bit extracted from data. We test our results on synthetic probability distributions, finding good agreement with the exact numerical solution near the onset of learning. We explore the difference and subtleties in our derivation and previous attempts at deriving a perturbation theory for the learning onset and attribute the discrepancy to a flawed assumption. Our work also provides a fresh perspective on the intimate relationship between the IB method and the strong data processing inequality.

Perturbation Theory for the Information Bottleneck
Vudtiwat Ngampruetikorn," . David J. Schwab Initiative for the Theoretical Sciences, The Graduate Center, CUNY vngamprueti cuny. edu
Abstract
Extracting relevant information from data is crucial for all forms of learning. The information bottleneck (IB) method formalizes this, offering mathematically pre- cise and conceptually appealing framework for understanding learning phenomena. However the nonlinearity the IB problem makes it computationally expensive and analytically intractable in general. Here we derive perturbation theory for the IB method and report the first complete characterization of the learning onset- the limit of maximum relevant information per bit extracted from data. We test our results on synthetic probability distributions, finding good agreement with the exact numerical solution near the onset of learning. We explore the difference and subtleties in our derivation and previous attempts at deriving a perturbation theory for the learning onset and attribute the discrepancy to flawed assumption. Our work also provides fresh perspective on the intimate relationship between the IB method and the strong data processing inequality.
Information Bottleneck
Extracting relevant information from data is crucial for all forms of learning. Animals are very adept at isolating biologically useful information from complicated real-world sensory stimuli: for example, instinctively ignore pixel-level noise when looking for face in photo. A failure to disregard irrelevant bits could lead to suboptimal generalization performance especially when the data contains spurious correlations. For instance, image classifier that relies background texture to identify objects is likely to fail when presented with a new image showing an object in an 'unusual" background (see, e.g., Refs [7, 30)). Understanding the principles behind the identification and extraction of relevant bits is therefore of fundamental and practical importance.
Formalizing this aspect of learning, the information bottleneck (IB) method provides precise notion of relevance with respect to prediction target: the relevant information a source (X) is the bits that earry information about the target (Y) [26]. The relevant bits in X are summarized in representation (Z) via a stochastic map defined by an encoder ((2]x), obeying the Markov constraint 2 ++> X Y. In general trade-off exists between the amount of discarded information (compression) and the remaining relevant information Z (prediction), thus motivating the IB cost function,?
l[[(<z|x) = I(Z; BI(Z:Y),
(1)
where B> denotes the trade-off parameter and I(A: B) the mutual information. The first term favors succinct representations whereas the second encourages predictive ones. The IB loss is minimized by the representations that are most predictive of Y fixed compression, parametrized by the Lagrange multiplier B (see, Fig la).
The IB method offers highly versatile framework with wide-ranging applications, including neural coding [16], evolutionary population dynamics [22]. statistical physics [9], clustering [25], deep
This Markov chain implies Pylx.z z Prix and Pzix.r = Pz ix (see, e.g., Ref [6]).
The optimization problem involving Eq (1) first appeared in different context (sec, c.g., Ref [27]).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Iz:Y
I2.Y S (DPI)
Iz: (SDPI)
!ziX
Px
Rx
0.4
0.6
Sp Izx
IB frontier
Izyy
Px,y
Py
0.4
0.2
Y
0.2
BL
Exact solution
Perturbation theory
0.1
Ry
0.5
1z:X
1.5
2
B
X
Figure Information bottleneck & Learning onset. a. The IB frontier (solid) is parametrized by the trade-off parameter B whose inverse is the slope of this curve. The relevant information is bounded from above by the data processing inequality (DPI) [dotted line] and its tight version, the strong data processing inequality (SDPI) [Eq (3), dashed line] which touches the IB curve at the origin. The slope at the origin equal to the inverse critical trade-off parameter BT which marks the learning onset (circles in (b-d)). b-d. Our controlled expansions (dashed) vs the exact solution (solid) for the joint distribution Px.y shown in (e). The red curves (e) depict the the perturbative IB encoder defined in Eq (14). We obtain the SDPI from Eqs (16) & (17) and the perturbative expansions in (b-d) from Eqs (26) & (27), see Appendix for relevant algorithms. Information is bits.
learning [1-3] and reinforcement learning [10]. However the nonlinearity of the IB problem makes it computationally expensive and difficult to analyze, barring a few special cases [5]. This necessitates an investigation of tractable methods for solving the IB problem. The use of variational approximations to reduce the computational cost has paved the way for massive scale-up of the IB method [3]. Complementing this approach, we report a new analytical result for the IB problem in the tractable limiting case of learning onset.
Learning Onset
Although the IB loss in Eq (1) favors representation that encodes every relevant bit in X when B + o the optimal representation needs not contain any relevant information at finite B. To see this, note that the loss vanishes for any uninformative representation ((; /(Z;Y) 0, and thus an informative representation yields a lower loss only when the relevant information in Z is adequately large: negative IB loss requires I(Z; > ((z X). But the relevant information is also bounded from above by the data processing inequality (DPI, I(Z;Y) s I(Z: X), resulting from the the Markov constraint X y [6] (see, Fig Ia). Combining these inequalities yields
B I(Z I(Z,Y) S (Z;
(2)
which cannot be met when B-1 > Hence the existence of an informative IB minimizer requires 8-1 < 1. Indeed for any Px,y with I(X; Y) > O, there exists critical trade-off parameter B. (X Y) 2 that marks the learning onset, separating two qualitatively distinct regimes: uninformative regime < Be and informative regime transitions that emerges from the hierarchy of relevant information in the data [26].
Be. The learning onset is the first in series of
Galvanized in part by the recent applications of the IB principle in deep learning, several works have attempted to characterized the transitions [8, 17, 28, 29]. However the IB problem remains intractable even in limiting cases and complete characterization of the IB transitions remains elusive. In fact the only exception the special case of Gaussian variables for which an exact solution exists [5]. In this work derive perturbation theory for the IB problem and offer the first complete description of the learning onset. We claborate on the subtle differences between our theory and the previous works in Sec 6.
The learning onset is not only a special limit in the IB problem but also physically and practically relevant. It corresponds to the region where the relevant information per encoded bit is greatest and
3 Thee compression term. while infinitesimally small in this limit, still penalizes irrelevant information and prefers representation Z that is the minimal sufficient statistics of X for Y.

---

thus places a tight bound on the thermodynamic efficiency of predictive systems [23, 24]. An analysis the IB learning onset has recently found applications in statistical physics [9]. The (inverse) critical trade-off parameter is also a useful measure of comelatiin between two random variables [13]; indeed its square root satisfies all but the symmetry property of Rényi's axioms for statistical dependence measures [21]. Finally estimating the upper bound of Be might help weed out non-viable values of hyperparameters in deep learning techniques such as the variational information bottleneck [28, 29].
2.1 Strong data processing inequality
We can improve the bound on Be with the tight version of the DPI, the strong data processing inequality (SDPI) [4, 18, 20] (see, Fig la)
((: 7X - (2)
where MKL (X denotes the contraction coefficient for the Kullback- divergence, defindd via
DKL (Ry (RyllPy)
7K1. (X Y)
sup Rx*Px
(4)
DKL DxI(Rx (Rxllxx)
Here Px and Py denote the probability distributions of X and Y. The supremum is over all allowed distributions given the space of X, and Ry is related to Rx via the channel Py Replacing the DPI with the SDPI in Eq (2), we obtain
nX - B. 2xx-))) ry-
(5)
In the following section we show that the equality holds, as expected (since the SDPI is tight). Note that (/.. (X- and (X-x))) Y) are generally asymmetric under X Y
3 Perturbation Theory
We investigate the learning onset through the lens of perturbation theory. This method constructs the solution for problem as power series in small parameter E, when the solution for the limiting case == the unperturbed solution, is accessible. For small the higher order terms in this series represent ever smaller corrections the unperturbed solution. To obtain these corrections, we insert the series solution into the initial problem and expand the resulting expressions as power series in e, truncated at appropriate order. For example, the first-order theory drops all quadratic and higher terms (those proportional to s², s.....) ), resulting in consistency condition for the linear correction (i.e., the term proportional to ø). Requiring consistency up g" leads the nh -order perturbation theory. In practice the first few corrections suffice for a characterization of the problem in the vicinity of =00.
Our theory is based on a controlled expansion around the critical trade-off parameter B. and some uninformative encoder (0(2|x) = q0(2),
((2|x) = qo(2/x)) + (2)x) (2/2(2)x) + = (IZ:X)=:ff)
(6)
[qi] 2 x 92)
(7)
where & = - 0+ and Σ> 9n (z]x) = for n to ensure normalization. Note that /0)
vanishes for uninformative qo- The first and second-order informations capture the first and second- order growths of information as / rises above Be and are given by (see Appendix for derivation)
q](x[x) In (2(xx) zeZi
2 -Epx)
Σ
(8)
(ı(Z)
(1(x(x) -1)))) (z)2
(1(xxx
(2) 2:x (q1. = Ex(x)
Σ
Σ (2(2(x) In
2g0(z)
(I())
zeZo
z6
+ Σ 42(x)xx g2(z|x)
q2(2)
where Zo supp(go) and Z, supp(gn) U Zi (i.e., Zn contains representation classes or space that first appear in the support of the nth-order encoder).* 4 The expansions for q(z) and (zly)
*Our theory generalizes the expansions in Ref' [28, 29] which considered the ===
3

---

take the same form as Eg (6), and the expressions for ((Z are identical to Eqs (7)-(9) but with Y replacing everywhere. Finally we write down the loss function as a power series in E,
L[q(z|x)) = EL (1) [qı] x²LL 191. q2l +20..21....
(10)
where
L (
[q1] [q1]
= =12x[qi Be [q1]
(11)
(2) [41 =
2:x 122x(11111 [91, -Be I91 92. 2z 141l-
(12)
3.1 First-order theory
Minimizing the first-order loss yields
(2(x)) 91(2))
= exp Be E(yk)) In T q7(z)
min ( = 1. [4i] 0 with
for z Zt. (13)
As the ratio (1(x))//q1 does not depend on z, we eliminate the superfluous dependence on z by defining
9 (x)x))(xx
(x)
for E Zi, and r()) p((()))(x))
(14)
(2)
Note that both r(x) and r(y) non-negative and normalized: Σx rx) My r(y) Substituting
Eqs (14) in (8) & (13), we obtain
( DxLlr(x))lp()) Σ qi())
ZX
26Zi
(15)
(1] 2Y8 = DxL[r())ll(<) Σ (z))),
zeZi
where
r(x) = p(x)e B. (Da (tt.Da/.poo///llll))llo.loollola
(16)
Since the first-order loss vanishes [see, Eq (13)), we have ( [4 - B. [4 and thus
2:X [qi] (xL[[(x))lp(x)]
Be
(17)
(1) Z:Y [qq]
Dx.[r(>))
Note that an uninformative solution r(x) = pxx) always satisfies Eq (16) and we must seek nontrivial solution r(x) p(x).
We now show that the critical trade-off parameter is equivalent to the inverse contraction coefficient.
First note that r(x) in Eq (16) is solution to different optimization, described by loss function
[[ Dxu p()) B. (())))) That is, 6L/8fly -r = 0 and min [ = L[r] =
It follows immediately that 5 DKi. (x)lptt)) /6 = 0 for Dxu (xL(r())lp(x)) > 0, therefore
BC¹ DxLIr(y)llp(>) sup
(xLL)()))P(0)
f+p DRL (x) 7/K (X - Y).
(18)
(xL[F(x)]lpx)]]
where the first and last equalities come from Eqs (17) & (4), respectively. The above analysis provides an alternative derivation of the equivalence between the contraction coefficients of mutual information and KI. divergence [4, 18].
While our first-order theory provides a method identifying the critical trade-off parameter by solving Eqs (16) & (17), is incomplete. The optimal encoder in Eq (13) is determined only up to a multiplicative factor. Consequently the informations in Eq (15) still depend on (z) which can take any positive value (for z Z1). This unphysical scale invariance is broken in the second-order theory.
Unlike in the original IB problem. here the optimization is unconstrained since the normalization L' 91 (zlx) sums over both Zo and Z1. and only the latter enters first-order theory.

---

3.2 Second-order theory
From Eqs (9) (12), we write down the second-order loss
Σxx (x,
L 22)
92]
E
-1 1911
(19a)
2q0(z)
ZeZo
In /1(21x)
Be Σ p(yl)) In g)
Σ p(x) Σ (2((1/x
(19b)
91(2)
q1(2)
zF21
In 92(22xx
92(zly)
Σ p(x) Σ (2(2(x)
92(2) Be p(yx))
(19c)
q2(2)
ze22
where we define
K(x,x') = 6(x,x (x() + (B. - ())p(1))()ppx)----
- Be E, p())p(()y)))(x1)
(20)
Optimizing (2) with respect to q2 (for Zi and Z2 separately) results stationary conditions, which (1) in Eq (19a) with
equate the terms in the parentheses of Eqs (19b) & (19c) to zero. Eliminating zz Eq (15), we have
Ex.x (1)2)))((xx))))((()))) 290(z)
I. () [qil = - -xL(F()))P())
Σn (z) + Σ
(21)
zeZi
ZeZo
Minimizing this loss function with respect to 9ı and subject to the normalization Σ, qz(xx)) gives
Σ x(xx') (Elx')
r(x))
Σ
qi(z')
Σ
K(x,x')
for E Zo-
(22)
go(2)
p(x')
2'eZi
Substituting the above in Eq (21) leads to
L [ -RIl(())))0>))
Σ (i())+
+
Σ gi(2)
(23)
zeZ1
12EZ1
where we define
(())((x))))('')
K
p(x)p(x')
(24)
Assuming x > 0,? the final minimization with respect to Ezez, qı(z) yields
qī()) = 1 -
Σ ZEZi
(25)
K
1 DxI.Fr()lP(())
0
1
[q"]
(26)
2x
Finally we eliminate the remaining dependence 9ı in Eq (15) and write down the first-order information
1 D (ri(((x))))(xt) D (r.((()))pp)))))
K (1) 1 -xu.fr(>)ll(>))]
(27)
We see that the second-order perturbation theory fixes the scales of the leading corrections mutual information, thus completing our analysis of the learning onset. Furthermore these leading corrections related via 111) B.1 Z.y and L(3 -
6This optimization unconstrained since the second-orde order loss does not depend on 42 with E Zo (see. footnote 5). The resulting stationary conditions are identical Eq (13) for di with Z and 92 with 2 Zz- For x z O, the loss function in Eq (23) is unbounded from below and a higher order perturbation theory is required to fix the scale of 41-
5

---

p(x]r=y))==f0011
p(x(Y=y1) =e p(x(Y=y2) de
p(x[V=y1) Polsson( pxx(== Poisson
a
Be MKL Pe 122
Pc Bc
1
Be² P
0.1
0.1
A1
GOOO0O wAA.EORR
& xxY
0.01
00
&c Ix.Y
1x.
0.01
0.1
(()
4 (1)
(1)
100
2:Y
2:Y
10
22Y
1
10-3
0.01
PAN
0.01
Ix.y
Ix.Y
10-
Ix:y
10-6
0.1
0.001
0.01
0.1
0.01
0.1
Figure 2: Learning onset in binary classification. We illustrate the results of our theory for the case a binary target variable with equal probability assigned to each class, i.e., Y E {y1, and p(Y=y1) = p(==y2) 1/2, for three different sets of conditional distributions p(xly) (a-c, top row). a. The source data X are drawn from a Gaussian distribution whose mean and variance depend on (top panel). We set the mean to zero and variance one for Y y1 and solve the IB learning onset for various values of mean μ and variance or for Y= y2. The middle panel depict the critical trade-off parameter, predicted by our theory in Sec 3 (filled circles) and the methods from previous works described in See 6 (empty circles). The bottom panel shows the information response to small perturbation in trade-off parameter [for definition see, Eq (7)]. The theory predictions plotted against the data mutual information, parametrized by the mean μ of pxxly2) for four different values of standard deviations (see legend). The dotted lines display the power dependence and serves only as a guide to the eye to aid comparisons. b. Same as (a) but for exponential distributions and the curves are parametrized by the rate parameter 2 of the exponential distributions (see, top panel). Same as (a) but for Poisson distributions and the curves are parametrized by A2 [mean of p(x[y2)) for four values of d1 [mean of p(xly1)] (see legend). Information is in bits.
4 Numerical Results
We now turn comparing our theory to numerical results. In Fig 1, we compare the results from our perturbation theory (Eqs (16), (17), (26) & (27)) to the numerically exact solution of the IB problem for synthetic joint distribution (shown in Fig le). Our theory correctly identifies the critical trade-off parameter and captures the leading corrections the mutual information and IB loss in the vicinity of the learning onset (see, Fig lb-d). The inverse critical trade-off parameter B coincides with the slope the strong data processing inequality (SDPI) which provides a tight upper bound for IB frontier (Fig la). Note that the SDPI is tight at the origin [/(Z: X) = I(Z: Y) 0] and is therefore fully characterized by our analysis of the learning onset.
Binary classification In Fig 2, we consider the onset of learning for binary classification which the target Y is binary random variable with equal probability for each class and the source variable X drawn from a distribution that depends on the realization Y. other words, provided with some data ask whether
drawn from blue red distributions in the top panel of Fig In all cases we see general trend that the inverse critical trade-off parameter B-1 and the relevant information response (1) increase with available information 1(X; Y). Indeed for the Gaussian case (Fig 2a), the information response diverges in the high information limit (equivalent to a large difference in

---

X ~ Unif(-1,,) ~~ f(x) + N 100,0
B
Be
1
1x-Y
linear
Vabsolute
0.1
0.01
1x
quadratic
cosine
(1)
(1)
z:Y
Z-Y
100
Pxx
cubic
0.01
10-4
Ix.y
0.01 0.1
Figure 3: Learning onset for noisy functional relationships. Functions used in data generation: The inverse critical trade-off parameter B:¹ vs noise
Unif(-1, 1) and y (V level parametrized by the noise standard deviation (left) and by available information I(X; Y) (right). c.
The first-order growth of information vs noise level parametrized by or (left) and by I(X:Y) (right). Both the maximum relevant information per extract bit B.¹ and the first-order relevant information (I) information. The dashed lines display the power dependence and serves only guide to the eye to aid comparisons. Information is in bits.
Z.Y decrease with noise level as it becomes increasingly difficult to extract relevant
the means of the Gaussian distributions) which is also the limit where binary classification becomes deterministic, I( bit.
Noise dependence In Fig 3, we depict the critical trade-off parameter and information response for joint distributions generated from X Unif(-1, 1, 1) and f(X) + J (O, o²) for various functional associations (Panel a). We see that the critical trade-off tends to one in the low noise limit, as expected a deterministic functional relationship [14]. At higher noise level, Be increases with as becomes harder to extract relevant bits from the data. This fact is also reflected in the first-order information ZzY which measures the change in relevant information as the trade-off parameter B exceeds the critical value. For all functions considered, (1) decreases with increasing noise standard deviation. Interestingly see that the information response diverges in the deterministic limit similar
(1))
the binary classification example shown in Fig 2a. Note that (1) 1. and (2) =-122 /2 [see Eqs (26) & (27)).
Z:X
5 Learning Onset for Gaussian Variables
At first sight it seems that our theory, which is agnostic about the discrete or continuous nature of the representation, is odd with the exact solution for Gaussian variables which based on continuous representation [5]. In this section we show that our theory captures the learning onset for joint Gaussian variables. Importantly we demonstrate that discrete representation of continuous variables can describe the learning onset just as well as continuous ones.
Consider joint Gaussian variables
x y
1
Σx Eyx
Exy Σy
(28)
convenient ansatz for r(x) and r(y) [for definitions, see, Eq (14)) a Gaussian distribution,
Rx Ax) and = M
(29)

---

where (xx,Ax) denotes the mean vector and covariance matrix for Rx and Ay) for Ry. Using this ansatz, we write down the KL divergences in the exponent of Eq (16),
1 (Uylx - vy) -y (My vy) + 1r[ My E dy In
|Ayl
DKLLP(>1))11<(>)] =
(30)
E
1 | by My 1 Exl dy + In
|r Σ
(31)
where Σylx= = Ey -yx Σxy. dy denotes the dimensionality Yf and we define py = Σyx x. The ratio between r(x) and pxx) is given by
r(x) = (x) 2 - -x
1
Σx |xx
In
(32)
Since Eqs (30) are related via Eq (16) which holds for all values xf we take the logarithm of Eq (16) and equate the terms quadratic in x, linear in x and constants separately, yielding
N - Σل' B Ex
Exy
Exx
(33)
Ax' vx B. Exy vy
(34)
Σx
|Eyl MA
A vx =
+ Be
vy N vy tr[(AT'' Ey
(35)
|Ax
We can find solution to this set of equations by letting Ax = Σx (which also leads to Ay Σy). For this choice of covariance matrix, both sides of Eq (33) vanish and Eqs (34) & (35) reduce to
(1 B1- -x vx O.
(36)
Solving the above eigenproblem for the smallest possible critical trade-off parameter, we find Be Amid and yx @mio where Amin denotes the smallest eigenvalue of Σx Eg and min the corresponding eigenvector. While both [5] and our work identify the same critical trade-off parameter and reveal the importance of the spectrum of Σxjy Ex! the analyses are distinct in that the
representation continuous in [5] but can be discrete in theory.
6 Comparisons to Previous Works
The recent applications of the IB principle in machine learning [1-3, 7] have sparked much interest in characterizing the structure of the IB problem [28, 29]. Several works underscore the learning onset and IB transitions as important limiting cases, not least because they are direct manifestation of the hierarchical structure of the relevant information in the data [5, 8, 17. 28, 29]. However the plagued by flawed assumption
attempts to derive perturbation theory for the learning onset that the representation space does not expand beyond the support of the unperturbed, uninformative encoder [8, 28, 29]. Equivalent setting Zi Z2 0 in Eqs (8) & (9) in theory, this assumption significantly simplifies the analysis but the resulting theory generally fails to identify the critical trade-off parameter." 10 This raises serious questions about the insights gleaned from such expansions around a seemingly arbitrary point. In the following we explore the differences between our full treatment and the perturbation theory derived in previous works. In partieular we argue that the theory in previous work describes the learning onset of a non-standard IB problem, defined with x² -iinformationn (instead of Shannon information).
8 Eqquation (35) becomes the same as Eq (34) but with 5-1 multiplied from the left. 'x= -x
We can always choose the unperturbed encoder to be all-to-one map (go(zolx) 1) and let the linear correction have access to one additional alphabet (g1 (2) (x) > O).
10rrr set-up differs slightly from Refs [28, 29] in that ask how optimal encoders respond to small change in 8 as opposed to how the loss function changes in response to a small perturbation an encoder. However this difference is not the reason why our theory produces a tight bound on the learning onset. Allowing the representation to take values outside the support of the unperturbed encoder is key to capturing the learning onset regardless of how perturbation theory constructed.

---

Setting Z1 = Z2 = 0, the leading correction to the IB loss is of second order and is given by the first term of Eq (19a),"
7 Ld [q)== - Ex,x (((()))(((xxx)))(((
(37)
2q0(z)
ZEZ0
where the dependence on Be is implicit [see, Eq (20), for the definition of (xx,x') We that K (x,x') is the Hessian of the loss function and its eigenvalues determine the curvatures of the loss landscape in the vieinity of the unperturbed encoder. In this theory the learning onset corresponds to the emergence of a direction along which the loss decreases quadraticall--ie. when the smallest eigenvalue first becomes negative. Note that Kxx,x) always has vanishing eigenvalue, resulting from the fact that all uninformative perturbations (ı(xxx) qı(z) lead to the same loss." 12 In practice we may identify the learning onset with the point where the second smallest eigenvalue becomes zero but a more efficient method exists, see below. Similarly to our first-order theory (Sec 3.1), this eigenvalue problem yields only the direction of the first-order encoder and a higher order theory is required to fix the scale.
It is worth pointing out that if we define the IB problem [Eq (1) with -nnformmaioon instead of the standard Shannon information," 13 Eq (37) is identical (up to a multiplicative factor) to the first-order loss in our full treatment (i.e., with Zi 0). Indeed the resulting learning onset coincides with the SDPT for x2 xi-information. The contraction coefficient for x²-information, 222, is exactly the squared maximal correlation (for a review, see, e.g., Ref [15]) and therefore symmetric under X Y and equal to the square of the second largest singular value of the divergence transition matrix [12, 21J,
B(x, y) y(x,y) for p(x)p(y) > O, and B(x, y) = 0 otherwise.
(38)
vp(x)p(y)
Finally we note that 17,2 S 7KL [19, 20]. hence the perturbation theory based on fixed representation space gives an upper bound to the critical trade-off parameter of the standard IB problem.
Figure 2 demonstrates that even for simple binary classification, the theory with fixed representation space, which predicts B.- " nr1 (empty circles), does not correctly identify the learning onset (filled circles). For the set of examples shown, we see that the discrepancy between B. and B. is greatest for the Gaussian case and at lower available information. Note that in the deterministic limit (I(X; 1 bit for binary classification] all contraction coefficients tend to one and we do not expect any discrepancy there.
Discussion & Outlook
We derive a perturbation theory for the IB problem and offer glimpse of the intimate connections between the learning onset and the strong data processing inequality. In future works we aim to build on our results to develop an algorithm for estimating the contraction coefficient from samples and explore novel methods for solving the IB problem in this limit. It would be interesting to further leverage the wealth of rigorous results from the literature on hypercontractivity and strong data processing inequalities to better understand the learning onset in the IB problem. In addition, various numerical techniques developed for the IB problem could significantly extend the range of applicability of contraction coefficients.
In Sec 5, we show that discrete representation can also capture the learning onset for Gaussian vari- ables. Our approach contrasts with the exact solution of Ref [5] which uses continuous representation. This highlights the degeneracy of the global minimum in the IB problem and implies that discrete representations of continuous variables needs not be suboptimal.
While the IB problem formulated with Shannon information is somewhat unique [11], our work reveals that the analyses of the learning onset would be much simplified if one were define the IB loss with iiinforraaionn instead of Shannon information. The IB principle based on other f-information could provide more tractable formulation for certain problems and offer insight not readily available otherwise.
11 Note that this loss depends only on the first-order encoder 41- The second-order encoder 42 appears in higher order thcories.
12 is easy to verify that Σ. K(x.x')=
13 The x² informaaiin is defined as follows, 1x2(X:)) Σx,y p(x)p()) p(x,y)
(pt0pt) - 1)²
9

---

Acknowledgments and Disclosure of Funding
We thank Shervin Parsi and Sarang Gopalakrishnan for useful discussions during the early stages of the project. This work was supported in part by the National Institutes of Health BRAIN initiative (R01EB026943), the National Science Foundation, through the Center for the Physics of Biological Function (PHY-1734030), the Simons Foundation and the Sloan Foundation.
References
[1] A. Achille and S. Soatto. Information dropout: noisy computation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(12):
Learning optimal representations through
2897-2905, 2018. 110.1110///AM.2211.777444444
[2] A. Achille and S. Soatto. Emergence invariance and disentanglement in deep representations. Journal of Machine Learning Research, 19(50):1-34, 2018. http://jmlr org wtteeorgggpppppeeee werggpapers/vile
77-646.24 html.
[3] A. A. Alemi, I. Fischer, V. Dillon, and K. Murphy, Deep variational information bottleneck. In International Conference on Learning Representations, 2017. https://openrevieet net/ f forum?id-HyxQzzoce
[4] V. Anantharam, A. A. Gohari, S. Kamath, and C. Nair. On maximal correlation, hyper- contractivity, and the data processing inequality studied by Erkip and Cover, 2013. https: / //arxiv..e org..brg////... abs/ /134. 6133.
[5] G. Chechik, A. Globerson, N. Tishby, and Y. Weiss. Information bottleneck for Gaussian variables. Journal of Machine Learning Research, 6:165-188, 2005, https://www wwwp:wwwwwl...............w..www org org/papers/v6. wwwchihhsa..cccccccoe html.
[6] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience, 2 ed., 2006.
[7] Y. Dubois, D. Kiela, J. Schwab, and R. Vedantam. Learning optimal representations with the decodable information bottleneck. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, eds., Advances in Neural Information Processing Systems, vol. 33, pp. 18674-18690. Curran Associates, Inc., 2020. https://prroeeddingg neurnig....uur....eeeerr...... cttes.cccpaaaaeeeee pttpppppap//////11///// (Be=5f5ccbbe007722555555333 Papere
[8] Gedeon, A. E. Parker, and G. Dimitrov. The mathematical structure of information
bottleneck methods. Entropy, 14(3):456 479, 2012. doi:100.330/e1400044
[9] A. Gordon, A. Banerjee, M. Koch-Janusz, and Z. Ringel. Relevance in the renormalization group and in information theory, 2020. attps://arzis attp:///aaii...o/aaaaa////////// /202. 01447.
[10] A. Goyal, R. Islam, DJ Strouse, Z. Ahmed, H. Larochelle, M. Botvinick. S. Levine, and
Y. Bengio. Transfer and exploration via the information bottleneck. International Conference on Learning Representations, 2019. https: https:///pppeevieeeeee net//ooruniidrrrgeee..
[11) P. Harremoes and N. Tishby. The information bottleneck revisited or how to choose good distortion measure. 2007 IEEE International Symposium on Information Theory, pp. 566-570, 2007. doi: 10. 109.1100T000000.0.... 45557285.
[12] H. O. Hirschfeld. A connection between correlation and contingency. Mathe- matical Proceedings of the Cambridge Philosophical Society, 31(4):520 524, 1935. doi: 00000000711003000000011131
[13] H. Kim, W. Gao, S. Kannan, S. Oh, and P. Viswanath. Discovering potential correlations via hypercontractivity. In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett, eds., Advances in Neural Information Processing Systems 30 (NIPS 2017), pp. 4577-4587. Curran Associates, Inc., 2017. http:://apers: wwwppprrs.iipp....mm cc/paper////////////pppp/pp/ 7044-discovering -tt--aasoorriiggpttaaaaaaaao-oo cnttential-corelattie www.rooiiiiibbeeeerooraaaaiiiiie
pdf.
[14] A. Kolchinsky, B. D. Tracey, and S. V. Kuyk. Caveats for information bottleneck in
deterministic scenarios. In International Conference on Learning Representations, 2019. https://openreve http://pwwreiieeeeeeeeefreeeeeee nwt//foruum http//orumiddrreeeeeee Aid=ree4HAccYT..
[15] A. Makur. Information contraction and decomposition. PhD thesis, Massachusetts Institute of Technology, 2019.
10

---

[16] S. E. Palmer, O. Marre, M. J. Berry II, and W. Bialek. Predictive information in sensory population. Proceedings of the National Academy of Sciences, 112(22):6908-69) 6913, 2015. doi:10. 10..0..///pa....... 1506855112.
[17] A. Parker, T. Gedeon, and A. Dimitrov. Annealing and the rate distortion problem. In S. Becker, S. Thrun, and K. Obermayer, eds., Advances in Neural Information Processing Systems 15 (NIPS 2002), vol. 15, pp. 993-976, 2003. http:////c0Baa000000041111111111
cc/paper/
[18] Y. Polyanskiy and Y. Wu. Dissipation of information in channels with imput constraints. IEEE Transactions on Information Theory, 32555555,5 2016. doi: 219TTTT.011.2442977
[19] Y. Polyanskiy and Wu. Strong data-processing inequalities for channels and Bayesian networks. In E. Carlen, M. Madiman, and E. M. Werner, eds., Convexity and Concentration, pp. 211-249, New York, NY, 2017. Springer New York.
[20] M. Raginsky. Strong data processing inequalities and 4-Sobolev incqualities for dis- crete channels. IEEE Transactions on Information Theory, 62(6):3355-3389, 2016. 00210.1119//11:206625544444
[21] A. Rényi. On measures of dependence. Acta Mathematica Academiae Scientiarum Hungarica, 10(3):441-455 1959. doi: 1e.11...00// 00000///F0002
[22] V. Sachdeva, T. Mora, A. M. Walezak, and S. Palmer. Optimal prediction with resource constraints using the information bottleneck. PLOS Computational Biology, 1008)44 2021. 1tt.10..3//jourallpppp percii.1008744 1008743.
[23] S. Still. Thermodynamic cost and benefit of memory. Physical Review Letters, 124:050601, Feb 2020. 10.: 103/PhysRevLeet. 124.050601.
[24] S. Still, D. A. Sivak, A. J. Bell, and G. E. Crooks. Thermodynamics prediction. Physical Review Letters, 109:120604, 2012. doi:10. 103//hysseeLett.... 109.1206044
[25] DJ Strouse and D. J. Schwab. The information bottleneck and geometric clustering. Neural Computation, 31 316))599-611, 2019. doi: 112.1..11/////oaaeee 136.
[26] N. Tishby, C. N. Pereira, and W. Bialek. The information bottleneck method. In B. Hajek and R. S. Sreenivas, eds., 37th Allerton Conference on Communication, Control and Computing, http:/ysssssssss/////
pp. 368 368-377. 337. University of Illinois, 1999. http:// http:://xxxvv..ove
[27] H. Witsenhausen and A. Wyner. A conditional entropy bound for pair of discrete random variables. IEEE Transactions on Information Theory, 21(5):493-501 1975. 105543..
[28] T. Wu and I. Fischer. Phase transitions for the information bottleneck in representation learning. In International Conference on Learning Representations, 2020. https /ttpps///opnrreview net/ HerumidddHJJoEllBvee
[29] T. Wu, I. Fischer, I. L. Chuang, and M. Tegmark. Learnability for the information bottleneck. Entropy, 21(10)9924 2019. doi: 10.339933//22 100924.
[30] K. Xiao, L. Engstrom, A. Ilyas, and A. Madry, Noise or signal: The role of image backgrounds in object recognition, 2020. https: //arxiv///ii//a//a org/ars 2006. 09994.


Reviews:
[{"review_id": "Yaj7gOaKQGO", "reviewer": "Reviewer_hqTY", "summary": "The paper studies the learning onset of Information Bottleneck (IB). The authors derive perturbation theory for the IB method and characterize the learning onset, and verifies with experiments. The authors also compare the difference and subtleties in their derivation and previous attempts at deriving a perturbation theory for the learning onset. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "In terms of originality, the perturbative approach to address the IB learning onset is not new, but the details of the perturbation, and characterization of the information quantities at the onset is new. \n\nIn terms of comparison with the previous work \"Learnability for the Information Bottleneck\" (Wu et al 2019), there is a difference between the meaning of \\epsilon. In (Wu et al 2019), the epsilon is defined as an infinitesimal number which is used for series expansion, which is independent of \\beta-\\beta_c, and the perturbation on the probability q(z|x) is the global difference between the perturbed probability and the trivial q_0(z|x)=q_0(z), and is allowed on the full support of Z. In the current work, \\epsilon is defined as \\epsilon=\\beta-\\beta_c, and therefore there are multiple terms q(z|x) = q0(z|x) + ε q1(z|x) + ε^2 q2(z|x) + ... , w.r.t. \\beta-\\beta_c. In (Wu et al 2019), the perturbative theory is used for deriving an upper bound of beta_c using sufficient conditions of non-trivial representation, while in the current work, since \\epsilon is defined as \\epsilon=\\beta-\\beta_c, it can obtain a tight bound of the onset. In the paper, it will be appropriate if the authors clarify the difference in the above perspective.\n\nApart from the above, the paper is mostly clear. In terms of significance, the result is incremental, but will be interesting to the IB and representation learning community.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is clear about its limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 hours"}, "extra_text": {}}, {"review_id": "S7UX4q4ol-X", "reviewer": "Reviewer_o32a", "summary": "The authors investigate the learning onset for the information bottleneck method, i.e., the behavior of the problem at \\beta being close to the critical parameter \\beta_c. More specifically, the IB curve is studied via a perturbation around the optimal compression map. In contrast to previous work, the authors allow this perturbation also outside of the alphabet of the optimal compression.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "The manuscript is well-written and seems mathematically correct (although I have to admit that I did not check every single detail). Understanding the properties of such an important and popular optimization problem is relevant in its own right. The insights are thus interesting and relevant, albeit only for a very small community (e.g., while the IB framework is often used for training neural networks, it is rarely the IB functional that is directly optimized, but some variational (or other) approximations). I am therefore generally in favor of this paper.\n\nThere are a few consideration that I would like to add:\n- In equations (8)-(9) it is not clear whether these are definitions or calculations. If they are calculations, I would appreciate to see these carried out in an appendix. These two equations are central to the paper, as the remaining derivations start from these assumptions.\n- In line 100 you claim that the ratio q1(z|x)/q1(z) does not depend on z. This is not obvious to me. It may very well be that I misunderstood some central part of the paper, but then it may be that this also escapes the attention of the occasional reader. May I ask you to expand on this statement a bit?\n- In equations (21)-(23) it is not exactly clear where and why the optimum q1* should be used. (And I assume that q1* is the optimizer of Section 3.1.) For example, why is q1* used in (21), but not in (22) and (23)? I would expect that q1* should at least be used in (23), as in its left-hand side of the equation.\n- In (22) is the r(x') defined via (14) or via (16), or is this the same by selecting q1(z|x)=q1*(z|x) as in (13)? This also leaves unclear to me whether in (15) the sums should run over q1* instead of q1, as (15) is obtained via inserting (13) into (14), and (13) uses the minimizer q1*. Again, I may have missed an important point here, in which case I apologize.\n- In Fig. 2 you add the proportionality to I(X;Y) in the figures. Are these proportionalities derived from or consistent with theory? I did not see this clearly mentioned in the paper. Even then, it is peculiar that the Gaussian case exhibits a bigger difference between the proportionality and the numerical results than previous approaches yielded. I would appreciate if you could expand on this fact somewhere in the text.\n- In lines 161-163 you connect the leading corrections for I(Z;Y) and I(Z;X), and you justify this via equations (26)-(27). If these equations hold true in general, then I would appreciate to see lines 161-163 in the general part of the paper (e.g., Section 3), rather than just at the end of the numerical experiments.\n- In line 165 you mention that the theory is agnostic about the discrete or continuous nature of the representation, while in line 184 you claim that the representations are discrete in this work. Which of the two statements is correct? They appear to be in conflict, at least to me. More generally, you claim in lines 183-184 that the analyses are distinct. I wonder if, using a Gaussian assumption, the functions r(x) and r(y) would have the same shape as they do in the discrete case. More generally, where is the discreteness of your assumption essential, and where can it be generalized to continuous distributions? I acknowledge that this last question is a very complicated one and I would fully accept as answer that this investigation is out of scope. However, I would be willing to share an educated guess here in the replies, I would read it with interest.\n\n\nFinally, there are some minor comments that I have, but that did not influence the score of the review:\n- in lines 82-83, I think you mean that the corrections get larger if \\epsilon deviates from zero, right?\n- in line 91, the notation \\delta_n,0 is not fully clear. I prefer the notation in eq. (20) or in line 126.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mention that the results concern only the learning onset, which is sufficient in my opinion. I also agree with the authors that no societal impacts are to be anticipated from this theoretical work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "8RUy5yK9alM", "reviewer": "Reviewer_DnfR", "summary": "This paper investigates the perturbation theory for the information bottleneck method to characterize the learning onset, i.e., the threshold parameter that governs the transition between the informative and uninformative regimes. First order theory and second order perturbation analyses to estimate the learning onset are presented. The utility of the theoretical results is demonstrated with the help of experiments. The authors also show the recovery of known results for Gaussian case using their analysis techniques. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "1. Since learning onset is central to the theoretical claims in the paper, I expected Section 2 to be more detailed and self contained. It's unclear why the learning onset corresponds to a transition characteristic and why the threshold parameter $\\beta_c$ is related to the maximum relevant information encoded per bit. \n\n2. The paper is well organized and mathematical details are reasonably clear, however, some parts of the analysis are not motivated well enough. What's the basis for expansions in (6) and (7)? Are these expansions valid for all stochastic encoders $q(z\\mid x)$? What do the quantities $I_{Z;X}^{(1)}[q_1]$ and $I_{Z;X}^{(1)}[q_1,q_2]$ signify? \n\nThe paper provides a worthy contribution to the information bottleneck theory by theoretically characterizing the learning onset. However, some parts of the paper could be improved with better motivation and discussions. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agree that this work is a clear, well-written theory paper that will be of interest to the growing community of researchers working with models trained using the Information Bottleneck and related objective functions. Consequently, we are recommending the paper for acceptance.
Decision: Accept (Poster)