Perturbation Theory for the Information Bottleneck
  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.
