Learnability for the Information Bottleneck

The Information Bottleneck (IB) method provides an insightful and principled approach for balancing compression and prediction for representation learning. The IB objective [Formula: see text] employs a Lagrange multiplier [Formula: see text] to tune this trade-off. However, in practice, not only is [Formula: see text] chosen empirically without theoretical guidance, there is also a lack of theoretical understanding between [Formula: see text] , learnability, the intrinsic nature of the dataset and model capacity. In this paper, we show that if [Formula: see text] is improperly chosen, learning cannot happen—the trivial representation [Formula: see text] becomes the global minimum of the IB objective. We show how this can be avoided, by identifying a sharp phase transition between the unlearnable and the learnable which arises as [Formula: see text] is varied. This phase transition defines the concept of IB-Learnability. We prove several sufficient conditions for IB-Learnability, which provides theoretical guidance for choosing a good [Formula: see text]. We further show that IB-learnability is determined by the largest confident, typical and imbalanced subset of the examples (the conspicuous subset), and discuss its relation with model capacity. We give practical algorithms to estimate the minimum [Formula: see text] for a given dataset. We also empirically demonstrate our theoretical conditions with analyses of synthetic datasets, MNIST and CIFAR10.