  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: $\text{IB}_\beta[p(z|x)] = I(X; Z) - \beta 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 \beta$ and prediction accuracy are
observed with increasing $\beta$. 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.
