Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 38 min ago
PreprintCC BY 4.0arXiv

The Information Bottleneck is NP-hard

  • Roberto Bruno
  • Ugo Vaccaro
Open at sourcePDFDOICite

Abstract

Given a joint distribution PXY of random variables X,Y on finite alphabets, the information bottleneck method seeks a representation T of X that is as informative as possible about Y while compressing X; the privacy funnel asks for a representation that discloses much about X while leaking little about Y. In both scenarios T and Y are conditionally independent given X. We show that computing the optimal value IB(PXY,R) = supT { I(Y;T) : I(X;T) ≤ R } of the information bottleneck problem, as well as its Lagrangian relaxation Lβ(PXY) = supT [ I(Y;T) − βI(X;T) ], is NP-hard. Moreover, unless P = NP, neither IB(PXY,R) nor Lβ(PXY) can be approximated in polynomial time within an additive error of order |𝒳|−(1+α), for every fixed α> 0. We also prove that computing the privacy funnel PF(PXY,r) = infT { I(Y;T) : I(X;T) ≥ r } and its Lagrangian relaxation Λβ(PXY) = infT [ I(Y;T) − βI(X;T) ] is NP-hard, and that, unless P = NP, neither can be approximated in polynomial time within an additive error of order |𝒳|−2.

Related

  1. On the Information Bottleneck for Stable Variables
    Dongmin Park, Jihad Fahs, Mohamad Assaad
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  2. Dynamics Aware Past-Future Information Bottleneck
    Wooyoung Chung, Stas Tiomkin
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  3. Optimal Multitask Representations Under a Rate Constraint: An Information Bottleneck Analysis
    Nicholas Stiles, Gregory W. Wornell
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  4. On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck
    Dier Tang, Jun Chen
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Training-Adaptive Convolutional Sparse Coding via Information Bottleneck for Robust Visual Representation
    Meng'en Qin, Yinchen Liu, Mingxuan Cui +1
    arXivPreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bruno2026information,
  title = {{The Information Bottleneck is NP-hard}},
  author = {Roberto Bruno and Ugo Vaccaro},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.22272},
  eprint = {2610.22272},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.22272},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Information Bottleneck is NP-hard
AU  - Roberto Bruno
AU  - Ugo Vaccaro
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.22272
UR  - https://arxiv.org/abs/2610.22272
AB  - Given a joint distribution P_XY of random variables X,Y on finite alphabets, the information bottleneck method seeks a representation T of X that is as informative as possible about Y while compressing X; the privacy funnel asks for a representation that discloses much about X while leaking little about Y. In both scenarios T and Y are conditionally independent given X. We show that computing the optimal value IB(P_XY,R) = sup_T { I(Y;T) : I(X;T) ≤ R } of the information bottleneck problem, as well as its Lagrangian relaxation L_β(P_XY) = sup_T [ I(Y;T) − βI(X;T) ], is NP-hard. Moreover, unless P = NP, neither IB(P_XY,R) nor L_β(P_XY) can be approximated in polynomial time within an additive error of order |𝒳|^−(1+α), for every fixed α> 0. We also prove that computing the privacy funnel PF(P_XY,r) = inf_T { I(Y;T) : I(X;T) ≥ r } and its Lagrangian relaxation Λ_β(P_XY) = inf_T [ I(Y;T) − βI(X;T) ] is NP-hard, and that, unless P = NP, neither can be approximated in polynomial time within an additive error of order |𝒳|^−2.
ER  -