Bootstrapped Information Bottleneck (BIB)

The Information Bottleneck (IB) balances prediction sufficiency and input compression. IB methods rely on data-dependent estimates of these two quantities and typically select a trade-off parameter from single-point estimates of these quantities without taking into account estimation uncertainty. We introduce the Bootstrapped Information Bottleneck (BIB), which provides it a distribution over prediction sufficiency vs. compression summarized with confidence ellipses. We provide the theoretical foundation for BIB by proving it asymptotic consistency of the bootstrap for mutual information estimators. BIB ensures that sufficiency constraints are met with high probability on unseen data and it improves held-out test accuracy by >7% compared to point estimate baselines on ImageNet. Finally, we show experimentally that the BIB data-dependent confidence regions are three orders of magnitude tighter than existing high-probability bounds on mutual information.