The Information Bottleneck is NP-hard

Abstract

Given a joint distribution $P_{XY}$ on a finite alphabet, the information bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$, where $T$ and $Y$ are conditionally independent given $X$. We show that computing the optimal value $\mathrm{IB}(P_{XY},R)={\sup }_T\{I(Y;T):I(X;T)\le R\}$ of the information bottleneck problem, as well as its Lagrangian relaxation $L_{\beta }(P_{XY})={\sup }_T[I(Y;T)-\beta I(X;T)]$, is NP-hard. Moreover, unless $\mathrm{P}=\mathrm{NP}$, neither $\mathrm{IB}(P_{XY},R)$ nor $L_{\beta }(P_{XY})$ can be approximated in polynomial time within an additive error of order $|\mathcal{X}{|}^{-3/2}$.

arXiv commentPreliminary version