Perturbation Theory for the Information Bottleneck
Year: 2021

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. 1 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, we instinctively ignore pixel-level noise when looking for a face in a photo. A failure to disregard irrelevant bits could lead to suboptimal generalization performance especially when the data contains spurious correlations. For instance, an image classifier that relies on 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 a precise notion of relevance with respect to a prediction target: the relevant information in a source (-) is the bits that carry information about the target (. ) [26]. The relevant bits in are summarized in a representation (/) via a stochastic map defined by an encoder @(I |G), obeying the Markov constraint /↔-↔. .1 In general a trade-off exists between the amount of discarded information (compression) and the remaining relevant information in / (prediction), thus motivating the IB cost function,2 ! [@(I |G)] = (/; -) − V (/;. ), (1) where V>0 denotes the trade-off parameter and ( ; ) 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 . at fixed compression, parametrized by the Lagrange multiplier V (see, Fig 1a). The IB method offers a highly versatile framework with wide-ranging applications, including neural coding [16], evolutionary population dynamics [22], statistical physics [9], clustering [25], deep 1This Markov chain implies %. |-,/ = %. |and %/ |-,. = %/ |(see, e.g., Ref [6]). 2The optimization problem involving Eq (1) first appeared in a different context (see, e.g., Ref [27]). 35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1 Information Bottleneck
text: 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, we instinctively ignore pixel-level noise when looking for a face in a photo. A failure to disregard irrelevant bits could lead to suboptimal generalization performance especially when the data contains spurious correlations. For instance, an image classifier that relies on 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 a precise notion of relevance with respect to a prediction target: the relevant information in a source (-) is the bits that carry information about the target (. ) [26]. The relevant bits in - are summarized in a representation (/) via a stochastic map defined by an encoder @(I |G), obeying the Markov constraint /↔-↔. .1 In general a trade-off exists between the amount of discarded information (compression) and the remaining relevant information in / (prediction), thus motivating the IB cost function,2
! [@(I |G)] = (/; -) − V (/;. ), (1) where V>0 denotes the trade-off parameter and ( ; ) 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 . at fixed compression, parametrized by the Lagrange multiplier V (see, Fig 1a).
The IB method offers a highly versatile framework with wide-ranging applications, including neural coding [16], evolutionary population dynamics [22], statistical physics [9], clustering [25], deep
1This Markov chain implies %. |-,/ = %. |- and %/ |-,. = %/ |- (see, e.g., Ref [6]). 2The optimization problem involving Eq (1) first appeared in a different context (see, e.g., Ref [27]).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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 a 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.

heading: 2 Learning Onset
text: Although the IB loss in Eq (1) favors a representation that encodes every relevant bit in - when V → ∞,3 the optimal representation needs not contain any relevant information at finite V. To see this, we note that the loss vanishes for any uninformative representation (/; -) = (/;. ) = 0, and thus an informative representation yields a lower loss only when the relevant information in / is adequately large: a negative IB loss requires (/;. ) > V−1 (/; -). But the relevant information is also bounded from above by the data processing inequality (DPI), (/ ;. ) ≤ (/ ; -), resulting from the the Markov constraint /↔-↔. [6] (see, Fig 1a). Combining these inequalities yields
V−1 (/; -) < (/;. ) ≤ (/; -), (2) which cannot be met when V−1 > 1. Hence the existence of an informative IB minimizer requires V−1 ≤ 1. Indeed for any %-,. with (-;. ) > 0, there exists a critical trade-off parameter V2 (- → . ) ≥ 1 that marks the learning onset, separating two qualitatively distinct regimes: uninformative regime at V < V2 and informative regime at V > V2 . The learning onset is the first in a series of transitions that emerges from the hierarchy of relevant information in the data [26].
Galvanized in part by the recent applications of the IB principle in deep learning, several works have attempted to characterized the IB transitions [8, 17, 28, 29]. However the IB problem remains intractable even in limiting cases and a complete characterization of the IB transitions remains elusive. In fact the only exception is the special case of Gaussian variables for which an exact solution exists [5]. In this work we derive a perturbation theory for the IB problem and offer the first complete description of the learning onset. We elaborate 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
3The compression term, while infinitesimally small in this limit, still penalizes irrelevant information and prefers a representation / that is the minimal sufficient statistics of - for . .
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 correlation 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 V2 might help weed out non-viable values of hyperparameters in deep learning techniques such as the variational information bottleneck [28, 29].

heading: 2.1 Strong data processing inequality
text: We can improve the bound on V2 with the tight version of the DPI, the strong data processing inequality (SDPI) [4, 18, 20] (see, Fig 1a)
(/;. ) ≤ [KL (- → . ) (/; -) (3) where [KL (-→. ) denotes the contraction coefficient for the Kullback-Leibler divergence, defined via
[KL (- → . ) ≡ sup '-≠%- DKL ('. ‖%. ) DKL ('- ‖%- ) . (4)
Here %- and %. denote the probability distributions of - and . . The supremum is over all allowed distributions given the space of - , and '. is related to '- via the channel %. |- . Replacing the DPI with the SDPI in Eq (2), we obtain
V2 (- → . ) ≥ [KL (- → . )−1. (5) In the following section we show that the equality holds, as expected (since the SDPI is tight). Note that [KL (-→. ) and V2 (-→. ) are generally asymmetric under -↔. .

heading: 3 Perturbation Theory
text: We investigate the learning onset through the lens of perturbation theory. This method constructs the solution for a problem as a power series in a small parameter Y, when the solution for the limiting case Y=0, the unperturbed solution, is accessible. For small Y, the higher order terms in this series represent ever smaller corrections to 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 Y, truncated at appropriate order. For example, the first-order theory drops all quadratic and higher terms (those proportional to Y2, Y3, . . . ), resulting in a consistency condition for the linear correction (i.e., the term proportional to Y). Requiring consistency up to Y= leads to the nth-order perturbation theory. In practice the first few corrections suffice for a characterization of the problem in the vicinity of Y=0. Our theory is based on a controlled expansion around the critical trade-off parameter V2 and some uninformative encoder @0 (I |G) = @0 (I),
@(I |G) = @0 (I |G) + Y@1 (I |G) + Y2@2 (I |G) + . . . (6) (/; -) = Y (1)/ ;- [@1] + Y2 (2) / ;- [@1, @2] + . . . , (7)
where Y ≡ V − V2 → 0+ and ∑I @= (I |G) = 0 for = ≥ 1 to ensure normalization. Note that (0)/ ;- vanishes for uninformative @0. The first and second-order informations capture the first and secondorder growths of information as V rises above V2 and are given by (see Appendix for derivation)
(1)/ ;- [@1] = ∑ G ?(G) ∑ I∈Z1 @1 (I |G) ln @1 (I |G) @1 (I) (8)
(2)/ ;- [@1, @2] = ∑ G ?(G) ( ∑ I∈Z0 @1 (I |G)2 − @1 (I)2 2@0 (I) + ∑ I∈Z1 @2 (I |G) ln @1 (I |G) @1 (I)
+ ∑ I∈Z2 @2 (I |G) ln @2 (I |G) @2 (I) ) , (9)
where Z0 = supp(@0) and Z= = supp(@=) \ ⋃=−18=0 Z8 (i.e., Z= contains representation classes or space that first appear in the support of the =th-order encoder).4 The expansions for @(I) and @(I |H)
4Our theory generalizes the expansions in Refs [28, 29] which considered the caseZ1=Z2=∅.
take the same form as Eq (6), and the expressions for (/;. ) are identical to Eqs (7)-(9) but with . replacing - everywhere. Finally we write down the loss function as a power series in Y,
! [@(I |G)] = Y! (1) [@1] + Y2! (2) [@1, @2] + . . . , (10) where
! (1) [@1] = (1)/ ;- [@1] − V2 (1) / ;. [@1] (11)
! (2) [@1, @2] = (2)/ ;- [@1, @2] − V2 (2) / ;. [@1, @2] − (1) / ;. [@1] . (12)

heading: 3.1 First-order theory
text: Minimizing the first-order loss yields5
min ! (1) = ! (1) [@∗1] = 0 with @∗1 (I |G) @∗1 (I) = exp
( V2 ∑ H ?(H |G) ln @ ∗ 1 (I |H) @∗1 (I) ) for I ∈ Z1. (13)
As the ratio @1 (I |G)/@1 (I) does not depend on I, we eliminate the superfluous dependence on I by defining
A (G) ≡ @ ∗ 1 (I |G)?(G) @∗1 (I) for I ∈ Z1, and A (H) ≡ ∑ G ?(H |G)A (G). (14)
Note that both A (G) and A (H) are non-negative and normalized: ∑G A (G) = ∑H A (H) = 1. Substituting Eqs (14) in (8) & (13), we obtain
(1)/ ;- = DKL [A (G)‖?(G)] ∑ I∈Z1 @∗1 (I)
(1)/ ;. = DKL [A (H)‖?(H)] ∑ I∈Z1 @∗1 (I), (15)
where A (G) = ?(G)4−V2 (DKL [? (H |G) ‖A (H) ]−DKL [? (H |G) ‖? (H) ]) . (16)
Since the first-order loss vanishes [see, Eq (13)], we have (1)/ ;- [@∗1] − V2 (1) / ;. [@∗1] = 0 and thus
V2 = (1)/ ;- [@∗1] (1)/ ;. [@∗1] = DKL [A (G)‖?(G)] DKL [A (H)‖?(H)] . (17)
Note that an uninformative solution A (G) = ?(G) always satisfies Eq (16) and we must seek a nontrivial solution A (G) ≠ ?(G). We now show that the critical trade-off parameter is equivalent to the inverse contraction coefficient. First we note that A (G) in Eq (16) is a solution to a different optimization, described by a loss function L[ 5 ] = DKL [ 5 (G)‖?(G)] − V2 DKL [ 5 (H)‖?(H)]. That is, XL/X 5 | 5 →A = 0 and minL = L[A] = 0. It follows immediately that X ( DKL [ 5 (H) ‖? (H) ] DKL [ 5 (G) ‖? (G) ] ) /X 5 | 5 →A = 0 for DKL [A (G)‖?(G)] > 0, therefore
V−12 = DKL [A (H)‖?(H)] DKL [A (G)‖?(G)] = sup5 ≠? DKL [ 5 (H)‖?(H)] DKL [ 5 (G)‖?(G)] = [KL (- → . ), (18)
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 KL divergence [4, 18].
While our first-order theory provides a method for identifying the critical trade-off parameter by solving Eqs (16) & (17), it 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 @1 (I) which can take any positive value (for I ∈ Z1). This unphysical scale invariance is broken in the second-order theory. 5Unlike in the original IB problem, here the optimization is unconstrained since the normalization∑ I @1 (I |G) = 0 sums over bothZ0 andZ1, and only the latter enters our first-order theory.

heading: 3.2 Second-order theory
text: From Eqs (9) & (12), we write down the second-order loss ! (2) [@1, @2] = ∑ I∈Z0 ∑ G,G′ @1 (I |G) (G, G ′)@1 (I |G ′) 2@0 (I) − (1) / ;. [@1] (19a)
+ ∑ G ?(G) ∑ I∈Z1 @2 (I |G) ( ln @1 (I |G) @1 (I) − V2 ∑ H ?(H |G) ln @1 (I |H) @1 (I) ) (19b)
+ ∑ G ?(G) ∑ I∈Z2 @2 (I |G) ( ln @2 (I |G) @2 (I) − V2 ∑ H ?(H |G) ln @2 (I |H) @2 (I) ) , (19c)
where we define (G, G ′) ≡ X(G, G ′)?(G) + (V2 − 1)?(G)?(G ′) − V2 ∑ H ?(H)?(G |H)?(G ′ |H). (20)
Optimizing ! (2) with respect to @2 (forZ1 andZ2 separately) results in stationary conditions, which equate the terms in the parentheses of Eqs (19b) & (19c) to zero.6 Eliminating (1)/ ;. in Eq (19a) with Eq (15), we have
! (2) [@1] = −DKL [A (H)‖?(H)] ∑ I∈Z1 @∗1 (I) + ∑ I∈Z0 ∑ G,G′ @1 (I |G) (G, G ′)@1 (I |G ′) 2@0 (I) . (21)
Minimizing this loss function with respect to @1 and subject to the normalization ∑
I @1 (I |G) = 0 gives ∑
G′ (G, G ′) @ ∗ 1 (I |G ′) @0 (I) = − ( ∑ I′∈Z1 @∗1 (I′) ) ∑ G′ (G, G ′) A (G ′) ?(G ′) for I ∈ Z0. (22)
Substituting the above in Eq (21) leads to
! (2) [@∗1] = −DKL [A (H)‖?(H)] ∑ I∈Z1 @∗1 (I) + ^ 2 ( ∑ I∈Z1 @∗1 (I) )2 , (23)
where we define ^ ≡ ∑ G,G′ A (G) (G, G ′)A (G ′) ?(G)?(G ′) . (24)
Assuming ^ > 0,7 the final minimization with respect to ∑I∈Z1 @1 (I) yields∑ I∈Z1 @∗1 (I) = 1 ^ DKL [A (H)‖?(H)], (25)
! (2) [@∗] = − 1 2^ DKL [A (H)‖?(H)]2. (26)
Finally we eliminate the remaining dependence on @1 in Eq (15) and write down the first-order information
(1)/ ;- = 1 ^ DKL [A (G)‖?(G)] DKL [A (H)‖?(H)] (1)/ ;. = 1 ^ DKL [A (H)‖?(H)]2. (27)
We see that the second-order perturbation theory fixes the scales of the leading corrections to mutual information, thus completing our analysis of the learning onset. Furthermore these leading corrections are related via (1)/ ;- = V2 (1) / ;. and !
(2) = − (1)/ ;. /2. 6This optimization is unconstrained since the second-order loss does not depend on @2 with I ∈ Z0 (see, footnote 5). The resulting stationary conditions are identical to Eq (13) for @1 with I ∈ Z1 and @2 with I ∈ Z2. 7For ^ ≤ 0, the loss function in Eq (23) is unbounded from below and a higher order perturbation theory is required to fix the scale of @1.
𝑝 (𝑥 |𝑌= 𝑦1) ∼𝒩 (0, 1) 𝑝 (𝑥 |𝑌= 𝑦2) ∼𝒩 (𝜇, 𝜎2) a 𝑝 (𝑥 |𝑌= 𝑦1) = 𝑒−𝑥 𝑝 (𝑥 |𝑌= 𝑦2) = 𝜆𝑒−𝜆𝑥 b 𝑝 (𝑥 |𝑌= 𝑦1) ∼Poisson(𝜆1) 𝑝 (𝑥 |𝑌= 𝑦2) ∼Poisson(𝜆2) c

heading: 4 Numerical Results
text: We now turn to 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 a synthetic joint distribution (shown in Fig 1e). Our theory correctly identifies the critical trade-off parameter and captures the leading corrections to the mutual information and IB loss in the vicinity of the learning onset (see, Fig 1b-d). The inverse critical trade-off parameter V−12 coincides with the slope of the strong data processing inequality (SDPI) which provides a tight upper bound for the IB frontier (Fig 1a). Note that the SDPI is tight at the origin [ (/; -) = (/;. ) = 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 in which the target. is a binary random variable with equal probability for each class and the source variable - is drawn from a distribution that depends on the realization of . . In other words, provided with some data G, we ask whether it was drawn from blue or red distributions in the top panel of Fig 2. In all cases we see a general trend that the inverse critical trade-off parameter V−12 and the relevant information response (1)/ ;. increase with available information (-;. ). Indeed for the Gaussian case (Fig 2a), the information response diverges in the high information limit (equivalent to a large difference in
the means of the Gaussian distributions) which is also the limit where binary classification becomes deterministic, (-;. ) → 1 bit.
Noise dependence In Fig 3, we depict the critical trade-off parameter and information response for joint distributions generated from - ∼ Unif (−1, 1) and . ∼ 5 (-) + (0, f2) for various functional associations (Panel a). We see that the critical trade-off tends to one in the low noise limit, as expected for a deterministic functional relationship [14]. At higher noise level, V2 increases with f as it becomes harder to extract relevant bits from the data. This fact is also reflected in the first-order information (1)/ ;. which measures the change in relevant information as the trade-off parameter V exceeds the critical value. For all functions considered, (1)/ ;. decreases with increasing noise standard deviation. Interestingly we see that the information response diverges in the deterministic limit similar to the binary classification example shown in Fig 2a. Note that (1)/ ;- = V2 (1) / ;. and !
(2) = − (1)/ ;. /2 [see Eqs (26) & (27)].

heading: 5 Learning Onset for Gaussian Variables
text: At first sight it seems that our theory, which is agnostic about the discrete or continuous nature of the representation, is at odd with the exact solution for Gaussian variables which is based on a continuous representation [5]. In this section we show that our theory captures the learning onset for joint Gaussian variables. Importantly we demonstrate that a discrete representation of continuous variables can describe the learning onset just as well as continuous ones. Consider joint Gaussian variables[ - . ] ∼ ( [ 0 0 ] , [ Σ- Σ-. Σ.- Σ. ] ) . (28)
A convenient ansatz for A (G) and A (H) [for definitions, see, Eq (14)] is a Gaussian distribution, '- = (a- ,Λ- ) and '. = (a. ,Λ. ). (29)
where (a- ,Λ- ) denotes the mean vector and covariance matrix for '- and (a. ,Λ. ) for '. . Using this ansatz, we write down the KL divergences in the exponent of Eq (16),
DKL [?(H |G)‖A (H)] = 12 ( (`. |G − a. )TΛ−1. (`. |G − a. ) + tr[Λ−1. Σ. |- ] − 3. + ln |Λ. | |Σ. |- | ) (30)
DKL [?(H |G)‖?(H)] = 12 ( `T. |GΣ −1 . `. |G + tr[Σ−1. Σ. |- ] − 3. + ln |Σ. | |Σ. |- | ) , (31)
where Σ. |- = Σ. −Σ.-Σ−1- Σ-. , 3. denotes the dimensionality of. and we define `. |G ≡ Σ.-Σ−1- G. The ratio between A (G) and ?(G) is given by
ln A (G) ?(G) = 1 2 ( −(G − a- )TΛ−1- (G − a- ) + GTΣ−1- G + ln |Σ- | |Λ- | ) . (32)
Since Eqs (30)-(32) are related via Eq (16) which holds for all values of G, we take the logarithm of Eq (16) and equate the terms quadratic in G, linear in G and constants separately, yielding
Λ−1- − Σ−1- = V2Σ−1- Σ-. (Λ−1. − Σ−1. )Σ.-Σ−1- (33) Λ−1- a- = V2Σ −1 - Σ-.Λ −1 . a. (34)
aT-Λ −1 - a- = ln |Σ- | |Λ- | + V2
( aT.Λ −1 . a. + tr[(Λ−1. − Σ−1. )Σ. |- ] − ln
|Σ. | |Λ. |
) . (35)
We can find a solution to this set of equations by letting Λ- = Σ- (which also leads to Λ. = Σ. ). For this choice of covariance matrix, both sides of Eq (33) vanish and Eqs (34) & (35) reduce to8(
1 − V2 (1 − Σ- |.Σ−1- ) ) a- = 0. (36)
Solving the above eigenproblem for the smallest possible critical trade-off parameter, we find V2 = (1 − _min)−1 and a- ∝ qmin where _min denotes the smallest eigenvalue of Σ- |.Σ−1- and qmin the corresponding eigenvector. While both [5] and our work identify the same critical trade-off parameter and reveal the importance of the spectrum of Σ- |.Σ−1- , the analyses are distinct in that the representation is continuous in [5] but can be discrete in our theory.9

heading: 6 Comparisons to Previous Works
text: 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 a direct manifestation of the hierarchical structure of the relevant information in the data [5, 8, 17, 28, 29]. However the attempts to derive a perturbation theory for the learning onset are plagued by a flawed assumption that the representation space does not expand beyond the support of the unperturbed, uninformative encoder [8, 28, 29]. Equivalent to settingZ1 = Z2 = ∅ in Eqs (8) & (9) in our 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 particular we argue that the theory in previous work describes the learning onset of a non-standard IB problem, defined with j2–information (instead of Shannon information).
8Equation (35) becomes the same as Eq (34) but with aT-Σ −1 - multiplied from the left.
9We can always choose the unperturbed encoder to be an all-to-one map (@0 (I0 |G) = 1) and let the linear correction have access to one additional alphabet (@1 (I1 |G) > 0).
10Our set-up differs slightly from Refs [28, 29] in that we ask how optimal encoders respond to a small change in V as opposed to how the loss function changes in response to a small perturbation to 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 a perturbation theory is constructed.
SettingZ1 = Z2 = ∅, the leading correction to the IB loss is of second order and is given by the first term of Eq (19a),11
! (2) [@1] = ∑ I∈Z0 ∑ G,G′ @1 (I |G) (G, G ′)@1 (I |G ′) 2@0 (I) , (37)
where the dependence on V2 is implicit [see, Eq (20), for the definition of (G, G ′)]. We see that (G, G ′) is the Hessian of the loss function and its eigenvalues determine the curvatures of the loss landscape in the vicinity of the unperturbed encoder. In this theory the learning onset corresponds to the emergence of a direction along which the loss decreases quadratically—i.e., when the smallest eigenvalue first becomes negative. Note that (G, G ′) always has a vanishing eigenvalue, resulting from the fact that all uninformative perturbations @1 (I |G) = @1 (I) 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 j2–information 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., withZ1 ≠ ∅). Indeed the resulting learning onset coincides with the SDPI for j2–information. The contraction coefficient for j2–information, [j2 , is exactly the squared maximal correlation (for a review, see, e.g., Ref [15]) and is therefore symmetric under - ↔ . and equal to the square of the second largest singular value of the divergence transition matrix [12, 21],
(G, H) ≡ ?(G, H)√ ?(G)?(H) for ?(G)?(H) > 0, and (G, H) ≡ 0 otherwise. (38)
Finally we note that [j2 ≤ [KL [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 V̂2 = [−1j2 (empty circles), does not correctly identify the learning onset (filled circles). For the set of examples shown, we see that the discrepancy between V2 and V̂2 is greatest for the Gaussian case and at lower available information. Note that in the deterministic limit [ (-;. ) = 1 bit for binary classification] all contraction coefficients tend to one and we do not expect any discrepancy there.

heading: 7 Discussion & Outlook
text: We derive a perturbation theory for the IB problem and offer a 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 a discrete representation can also capture the learning onset for Gaussian variables. 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 to define the IB loss with j2–information instead of Shannon information. The IB principle based on other 5 –information could provide a more tractable formulation for certain problems and offer an insight not readily available otherwise.
11Note that this loss depends only on the first-order encoder @1. The second-order encoder @2 appears in higher order theories. 12It is easy to verify that ∑
G′ (G, G′) = 0. 13The j2–information is defined as follows, j2 (-;. ) ≡ ∑ G,H ?(G)?(H) ( ? (G,H) ? (G) ? (H) − 1 )2
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.

Review summaries:
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. 

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. 

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.