Computing information bottleneck values is computationally hard
The Information Bottleneck is NP-hard
Information Theory
Summary
The paper shows that finding the best way to summarize data while keeping important information is very hard for computers to do efficiently. Specifically, the problem, called the information bottleneck, is classified as NP-hard, meaning no quick method is known to solve it exactly for all cases. The authors also prove it is hard to even get close to the best solution within small error in reasonable time. This means efforts to simplify data representation while preserving meaning have fundamental computational barriers.
What this means in practice
- •For data compression engineers: Recognize inherent computational limits when designing optimal compression preserving relevance to another variable in complex datasets.
- •For machine learning system builders: Understand that approximate solutions to information bottleneck objectives may be necessary due to the problem’s computational hardness.
A theory result. No direct application yet.
Authors
Roberto Bruno, Ugo Vaccaro
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_β(P_{XY}) = \sup_T \big[I(Y;T) - βI(X;T)\big]$, is NP-hard. Moreover, unless $\mathrm{P} = \mathrm{NP}$, neither $\mathrm{IB}(P_{XY},R)$ nor $L_β(P_{XY})$ can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-3/2}$.