The Cardinality Bound on the Information Bottleneck Representations is Tight

The information bottleneck (IB) method aims to find compressed representations of a variable X that retain the most relevant information about a target variable Y. We show that for a wide family of distributions – namely, when Y is generated by X through a Hamming channel, under mild conditions – the optimal IB representations require an alphabet strictly larger than that of X. This implies that, despite several recent works, the cardinality …