The Information Bottleneck and the Privacy Funnel are NP-hard
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "The Information Bottleneck and the Privacy Funnel are NP-hard".
Jane: Here's the gist of the paper. The Information Bottleneck is NP-hard because computing its optimal value IB(PXY, R) and its Lagrangian relaxation Lβ(PXY) is NPhard Problem Formulation and Hardness Results The Information Bottleneck problem is formally defined by the optimization problem IB(PXY, R) = sup PT X: T −X−Y I(X;T)≤R I(Y; T).
Tom: The Lagrangian formulation Lβ(PXY) = sup PT X: T −X−Y I(Y; T)−βI(X; T) 0.
Jane: The authors establish computational hardness for both formulations (1.1) and (1.2), proving that their threshold decision problems are NP-hard.
Tom: Specifically, they prove that the threshold decision problems are NP-hard by a reduction from the well-known Clique problem.
Paper summary: Tom: We started by looking at "The Information Bottleneck and the Privacy Funnel are NP-hard," and what they claim is that computing the optimal value IB of PXY R, which is about maximizing information about Y while compressing X under a rate constraint R, and also its Lagrangian relaxation L beta of PXY, is NP-hard.
Jane: The core thesis here is that these two problems are computationally hard to solve exactly <ref:2610.22272#pg1>. They establish this by showing a reduction from the well-known Clique problem twelve <ref:2610.22272#pg2>.
Lu: Their proof construction involves building a larger graph, G bar, by inserting cliques around every edge of the original graph G. They then define a joint distribution PXY on this structure where X is related to oriented edges and Y is related to the vertices.
Meng: So they’re using a clique problem—which we know is hard—to prove that finding an optimal information bottleneck representation is just as hard <ref:2610.22272#pg1>. It connects a graph problem to information theory, which is interesting because it shows the structural difficulty isn't just in the math itself.
Lalam: This hardness result also applies to the privacy funnel problem one, suggesting that these types of trade-offs are inherently difficult when you try to optimize them perfectly <ref:2610.22272#pg1>.
Tom: They go further than just showing it’s hard; they give inapproximability results too, which is where it gets really concrete for practical applications.
Jane: They show that unless P equals NP, no polynomial-time algorithm can approximate L beta of PXY within an additive error of order one over X to the power of three over two <ref:2610.22272#pg1>.
Lu: This approximation limit holds for standard bit models with rational input distributions and rational rate budgets <ref:2610.22272#pg1>. It sets a benchmark for what we can hope to achieve algorithmically.
Meng: For us at the startup level, that means if we are trying to find the best way to compress data for our models, we can't rely on finding a good approximation unless P equals NP <ref:2610.22272#pg1>. It’s a hard barrier.
Lalam: And they extend this hardness result to every fixed rational multiplier beta between zero and one <ref:2610.22272#pg3>. They can construct a distribution Ptilde XZ that gives you the Lagrangian relaxation L beta of PXY, and it's still hard to approximate within an error related to kappa beta over two times six over three over two times X cubed <ref:2610.22272#pg3>.
Tom: And they extend it even further, showing that for every fixed polynomial-time computable real multiplier in that interval, the Lagrangian version is NP-hard <ref:2610.22272#pg3>.
Jane: So they've covered both the exact computation difficulty and the approximation difficulty across a lot of parameter choices <ref:2610.22272#pg3>. They show that even slight changes in our parameters don't make it easy.
Lu: The implication is that the structure of the information bottleneck problem is inherently complex, regardless of whether you look at the exact optimum or a relaxed version involving a multiplier <ref:2610.22272#pg3>.
Meng: I guess for deployment, that means we need to be very careful about how we define our rate constraints R and how we choose our multiplier beta <ref:2610.22272#pg3>. A small change in those choices could mean the difference between a feasible solution and one that's just not reachable by a fast algorithm.
Lalam: The whole paper, "The Information Bottleneck and the Privacy Funnel are NP-hard," is about showing that these information trade-offs have inherent computational difficulty <ref:2610.22272#pg1>.
Conclusion: Tom: So to wrap up, the authors of "The Information Bottleneck and the Privacy Funnel are NP-hard" proved that both the constrained and Lagrangian formulations of this problem are NP-hard <ref:2610.22272#pg1>.
Jane: They also proved that unless P equals NP, neither IB nor L beta can be approximated in polynomial time within those stated additive errors of order one over X to the power of three over two <ref:2610.22272#pg1>.
Lu: And they extended this to every fixed rational multiplier beta between zero and one, showing that the Lagrangian version is still NP-hard with corresponding inapproximability bounds <ref:2610.22272#pg3>.
Meng: The main implication for us is that we can't expect a fast algorithm to find the absolute best way to compress data under these constraints <ref:2610.22272#pg1>.
Lalam: This means that for real-world applications, we must rely on heuristics or approximations, and those approximations will have limits defined by those error bounds <ref:2610.22272#pg3>.
Tom: The authors have established NP-hardness of the threshold decision problems for both formulations of the information bottleneck <ref:2610.22272#pg1>.
Jane: They
University of Salerno
cs.IT, math.IT
Submitted: 2026-10-15
Updated: 2026-11-02
Comments: Updated version of the manuscript with additional results. Submitted for publication
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 77/100
The gist: The Information Bottleneck is NP-hard because computing its optimal value IB(PXY, R) and its Lagrangian relaxation Lβ(PXY) is NPhard Problem Formulation and Hardness Results The Information…
Key concepts
- Information Bottleneck (IB)
- This is an optimization problem where the goal is to find a representation of data (X) that retains as much relevant information about some target variable (Y) as possible, while simultaneously minimizing the mutual information between X and some other variable T. It balances compression and relevance.
- Lagrangian Relaxation ($Leta(PXY)$)
- This is a relaxed version of the main IB problem introduced by adding a penalty term ($eta I(X;T)$). By relaxing this constraint using a multiplier $eta$, the authors show that even this simplified version remains NP-hard, proving complexity for related optimization tasks.
- Clique Problem
- The Clique problem is a classic NP-complete problem in graph theory. It asks if there exists a subset of vertices in a graph where every pair of vertices in that subset is connected by an edge. The paper uses this problem to construct reductions proving the hardness of the IB formulations.
- Inapproximability
- This result means that unless P=NP, no algorithm can find a solution to the Information Bottleneck problem (or its Lagrangian version) that is guaranteed to be close to the true optimal value within certain specified error margins. These bounds are very tight.
Terminology
Summary
The Information Bottleneck is NP-hard because computing its optimal value IB(PXY, R) and its Lagrangian relaxation Lβ(PXY) is NPhard
Problem Formulation and Hardness Results
The Information Bottleneck problem is formally defined by the optimization problem IB(PXY, R) = sup PT X: T −X−Y I(X;T)≤R I(Y; T). The Lagrangian formulation Lβ(PXY) = sup PT X: T −X−Y I(Y; T)−βI(X; T) 0. p. 0 The quantities I(X; T) and I(Y ; T) measure the information retained about the input and the
target, respectively. We also consider the Lagrangian formulation
Lβ(PXY ) = sup
PT |X: T −X−Y
I(Y ; T) − βI(X; T)
, β > 0. The above exact solutions exploit structural assumptions on the joint distribution, whereas
the present work addresses the computational complexity of the problem for arbitrary finitealphabet distributions. More precisely, we establish computational hardness for both formulations (1. More precisely, we establish computational hardness for both formulations (1. We prove that their threshold decision problems are NP-hard, the
NP-hardness of (1. 23)
We notice that IB-Lagrangian asks whether L1/2
(PXY ) ≥ τ , where L1/2
(PXY ) is defined
in (1. We prove the NP-hardness of IB-Threshold and IB-Lagrangian by a reduction from
the well-known Clique problem [12].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Reduction from Clique
The proof of NP-hardness for both IB-Threshold and IB-Lagrangian is achieved by a polynomial-time reduction from the Clique problem. Given an instance (G, k) of Clique, they construct a larger graph G¯ by inserting for each edge e of G a clique Ce of size m − 2 new vertices, and adding all the edges needed to make Ce = u, v ∪ Se a clique of size m. p. 5 We briefly describe
the idea of the reduction for IB-Lagrangian. Given an instance (G, k) of Clique, we
construct a larger graph G¯ by inserting for each edge e of G a clique Ce of size k −1 containing
only the edge e from the edges of G. We briefly describe
the idea of the reduction for IB-Lagrangian. Given an instance (G, k) of Clique, we
construct a larger graph G¯ by inserting for each edge e of G a clique Ce of size k −1 containing
only the edge e from the edges of G. This construction ensures that the cliques Ce partition
the edges of G¯, and that no clique of size larger than k − 1 is created, apart from those already
present in G. We then construct a joint distribution PXY where X is a uniformly random
variable on the oriented edges of G¯ and, given X = x, the random variable Y is one of the two
vertices of the edge x, chosen uniformly at random. This construction ensures that the cliques Ce partition
the edges of G¯, and that no clique of size larger than k − 1 is created, apart from those already
present in G. We then construct a joint distribution PXY where X is a uniformly random
variable on the oriented edges of G¯ and, given X = x, the random variable Y is one of the two
vertices of the edge x, chosen uniformly at random.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Approximation Limits
The paper establishes inapproximability results for both formulations. Unless P = NP, no polynomial-time algorithm can approximate Lβ(PXY) within an additive error of order X −3/2. p. 1 2) is first obtained with the Lagrangian multiplier fixed at β = 1/2, then
extended to general rational β ∈ (0, 1). Moreover, unless P = NP, no polynomial-time algorithm can approximate Lβ(PXY ) within additive error 1/(216 |X |3/2
), or IB(PXY , R) within
additive error 1/(576 |X |3/2
) (Theorems 1 and 2). 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 NPhard. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. Moreover, unless P = NP, no polynomial-time algorithm can approximate Lβ(PXY ) within additive error 1/(216 |X |3/2
), or IB(PXY , R) within
additive error 1/(576 |X |3/2
) (Theorems 1 and 2). These results hold in the standard bit model
of computation, with rational input distributions and rational rate budgets.Where the paper says it
Where the paper says it
Where the paper says it
Extension to General Multipliers
The hardness result for the Lagrangian multiplier β = 1/2 can be extended to any other fixed multiplier β ∈ (0, 1) using an elementary transformation of the target variable. Proposition 3 shows that for a fixed rational number β ∈ Q ∩ (0, 1), one can construct in polynomial time a rational joint distribution P˜XZ with the same marginal PX such that Lβ(P˜XZ) = κβ L1/2(PXY). p. 5 Moreover, unless P = NP, there is
no polynomial time algorithm that, given an arbitrary rational joint distribution PXY of (X, Y )
on a finite alphabet X × Y, outputs a value v such that
v − L1/2
(PXY )
≤
1
216 |X |3/2
. 1)
An easy reduction from the β = 1/2 case allows us to extend Theorem 1 to any β ∈ (0, 1)
(see Proposition 3). 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 NPhard. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
.Where the paper says it
Where the paper says it
Extension to Real Multipliers
The conclusions are extended to every fixed polynomial-time computable real multiplier in this interval by applying a rational approximation argument. This shows that for every fixed polynomial-time computable real β in (0, 1) IB-Lagrangianβ is NP-hard and Lβ cannot be approximated within an additive error of order X −3/2 unless P = NP. p. 0 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 NPhard. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
.Where the paper says it
Inapproximability for Threshold Problems
The hardness for the threshold decision problems is also established. The reduction from Clique to IB-Threshold shows that any approximation of IB(PXY, R) within an additive error smaller than δ4 lies on the same side of ϑ as IB(PXY, R), thus deciding Clique in polynomial time unless P = NP. p. 5 By a reduction from Clique, we
prove that both IB-Threshold and IB-Lagrangian are NP-Hard. Moreover, we also show
that approximating the optimal values IB(PXY , R) and L1/2
(PXY ) within an additive error
that is polynomial in 1/|X |, where |X | is size of the alphabet of X, is NP-hard.Where the paper says it
Complexity of Rate Computation
The rate budget R for the threshold problem is computed by approximating a value R∗, which depends only on N and k, within an additive error δ4. This approximation can be done in polynomial time because R∗ is an explicit expression involving polynomially many logarithms of rational numbers with O(log n) bits.
Summary of Findings
The paper establishes NP-hardness for both the constrained and Lagrangian formulations of the information bottleneck. Furthermore, it proves that no polynomial-time approximation exists within stated additive errors unless P = NP. p. 1 Our results establish a worst-case computational barrier to evaluating the optimal IB
tradeoff even when the joint distribution is explicitly known and arbitrary stochastic encoders
are allowed. They delimit the accuracy guarantees attainable in polynomial time on general
inputs and motivate the study of tractable distribution classes; the complexity of approximation
within a constant additive error of (1. These results hold in the standard bit model
of computation, with rational input distributions and rational rate budgets. Our results establish a worst-case computational barrier to evaluating the optimal IB
tradeoff even when the joint distribution is explicitly known and arbitrary stochastic encoders
are allowed.Where the paper says it
Where the paper says it
Conclusion
The authors have established NP-hardness of the threshold decision problems for both formulations of the information bottleneck. p. 1 More precisely, we establish computational hardness for both formulations (1. We prove that their threshold decision problems are NP-hard, the
NP-hardness of (1. 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 NPhard. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 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 NPhard. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. We prove that their threshold decision problems are NP-hard, the
NP-hardness of (1. 2) is first obtained with the Lagrangian multiplier fixed at β = 1/2, then
extended to general rational β ∈ (0, 1).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
References
[1] S. Asoodeh and F. p. 1 Gerber’s lemma [18]; extensions cover binaryinput memoryless symmetric channels with uniform input [4, 16]. For nonbinary Hamming
channels with uniform input, Benger, Asoodeh and Chen [2] characterize the entire curve as
the upper concave envelope of an explicit scalar function. Gerber’s lemma [18]; extensions cover binaryinput memoryless symmetric channels with uniform input [4, 16]. For nonbinary Hamming
channels with uniform input, Benger, Asoodeh and Chen [2] characterize the entire curve as
the upper concave envelope of an explicit scalar function. More generally, we recall that the conditional entropy of Y given X is defined as the
average of H(Y | X = x) with respect to PX, that is,
H(Y | X) = EX[H(Y | X)] = X
x∈X
PX(x)H(Y | X = x). 7)
Then, the mutual information between X and Y is defined as
I(X; Y ) = H(Y ) − H(Y | X). More generally, we recall that the conditional entropy of Y given X is defined as the
average of H(Y | X = x) with respect to PX, that is,
H(Y | X) = EX[H(Y | X)] = X
x∈X
PX(x)H(Y | X = x). 7)
Then, the mutual information between X and Y is defined as
I(X; Y ) = H(Y ) − H(Y | X).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[2] E. Benger, S. Asoodeh and J. p. 1 Gerber’s lemma [18]; extensions cover binaryinput memoryless symmetric channels with uniform input [4, 16]. For nonbinary Hamming
channels with uniform input, Benger, Asoodeh and Chen [2] characterize the entire curve as
the upper concave envelope of an explicit scalar function. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning. The information bottleneck
(IB) method, introduced by Tishby, Pereira and Bialek in 1999 [17]
1
, formulates this problem
as a trade-off between compressing an observed random variable X and retaining information
about a target variable Y . Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning.Where the paper says it
Where the paper says it
Where the paper says it
[3] R. Brent, Fast multiple-precision evaluation of elementary functions, Journal of the ACM (JACM), vol. 23, pp. 242–251, 1976
[4] N. Chayat and S. Shamai, Extension of an entropy property for binary input memoryless symmetric channels, IEEE Trans. p. 1 For binary sources observed through a binary symmetric
channel, the exact tradeoff follows from Mrs. Gerber’s lemma [18]; extensions cover binaryinput memoryless symmetric channels with uniform input [4, 16]. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning.Where the paper says it
Where the paper says it
Where the paper says it
[5] T.-W. Chao and H.-H. H. Yu, When entropy meets Turán: new proofs and hypergraph Turán results, J. p. 5 Finally, in Sections 3. 6, we combine the
previous results, providing the proofs of Theorems 1 and 2. 22272v1 [cs. IT] 15 Oct 2026 22272v1 [cs. IT] 15 Oct 2026 2) remains open. 2 Notation and Preliminaries
All alphabets throughout the paper are finite, and we denote by log the logarithm in base 2.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[6] G. Chechik, A Globerson, N Tishby and Y Weiss, Information bottleneck for Gaussian variables, Journal of Machine Learning Research 6 (2005), 165–188
[7] M Dikshtein, N Weinberger and S Shamai, On information bottleneck for Gaussian processes, in Proc. IEEE Information Theory Workshop (ITW), 2022, pp. p. 0 Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning.Where the paper says it
[8] K Etessami, A Stewart and M Yannakakis, A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing, ACM Trans. Comput. Theory 6 (2014), no. p. 0 Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning.Where the paper says it
Where the paper says it
[9] M R Garey and D S Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W H Freeman, 1979
[10] Z Goldfeld and Y Polyanskiy, The Information Bottleneck Problem and its Applications in Machine Learning, IEEE J Sel. Areas Inf. Theory. 2020. Vol. 1(1):19-38
[11] S Hu, Z Lou, X Yan and Y Ye, A Survey on Information Bottleneck, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 46, no. 8, pp. 5325-5344
[12] R M Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (R E Miller and J W Thatcher, eds.), Plenum Press, New York, 1972, pp. 85–103
[13] A Kolchinsky, B D Tracey and S Van Kuyk, Caveats for information bottleneck in deterministic scenarios, in Proc. International Conference on Learning Representations (ICLR), 2019
[14] T S Motzkin and E G Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., vol. 17, pp- 533–540, 1965
[15] I Sason and S Verdú, f-divergence inequalities, IEEE Transactions On Information Theory, vol. 62, pp. 5973–6006, 2016
[16] I Sutskover, S Shamai and J Ziv, Extremes of information combining, IEEE Trans. Inf. Theory 51 (2005), no. p. 0 Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning. Moreover, unless P = NP, neither IB(PXY , R) nor Lβ(PXY ) can be approximated
in polynomial time within an additive error of order |X |−3/2
. 1 Introduction
Extracting compact representations that preserve information relevant to a task is a central
problem in information theory, statistics, and machine learning.Where the paper says it
Where the paper says it
[17] N Tishby, F C Pereira and W Bialek, The information bottleneck method, in Proc. 37th Annual Allerton Conference on Communication, Control, and Computing, 1999
[18] Wyner A; Ziv J. A theorem on the entropy of certain binary sequences and applications: Part I. IEEE Trans. Inf. Theory 1973, 19, 769–772
[19] Wyner A. A theorem on the entropy of certain binary sequences and applications—II. p. 1 To the best of our knowledge, exact characterizations of the information bottleneck curve
are known in a handful of cases only. For binary sources observed through a binary symmetric
channel, the exact tradeoff follows from Mrs.Where the paper says it
[20] Witsenhausen H; Wyner A. A conditional entropy bound for a pair of discrete random variables, IEEE Trans. p. 1 Moreover, since H(X) depends only on the distribution PX, we
also write H(PX) to denote the entropy of the distribution PX. Let (X, Y ) be a pair of random variables assuming values in the finite alphabet X × Y,
with a joint probability distribution PXY :
PXY (x, y) = P(X = x, Y = y), ∀x ∈ X and y ∈ Y, (2.Where the paper says it
[21] Zaidi A; Estella-Aguerri I; Shamai S. On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views. p. 0 Applications of IB include clustering and document classification [17], as well as the
design of representations for neural classifiers and generative models [10]. Its operational
interpretation through remote source coding under logarithmic loss, together with extensions to
distributed learning and communication, connects these applications to information-theoretic
performance limits [21].Where the paper says it
[24] R S Ziv and Y Le Cun, To Compress or Not to Compress—Self-Supervised Learning and Information Theory: A Review, Entropy 2024, 26(3), 252
[30] A Approximation of Logarithms>
--- Page 30 ---
The Information Bottleneck is NP-hard because computing its optimal value IB(PXY, R) and its Lagrangian relaxation Lβ(PXY) is NPhard
Pruning redundant reasoning tokens
The Information Bottleneck is NP-hard because computing its optimal value IB(PXY, R) and its Lagrangian relaxation Lβ(PXY) is NPhard
How the training signal is built
The proof of NP-hardness for both IB-Threshold and IB-Lagrangian is achieved by a polynomial-time reduction from the Clique problem. Given an instance (G, k) of Clique, they construct a larger graph G¯ by inserting for each edge e of G a clique Ce of size m − 2 new vertices, and adding all the edges needed to make Ce = u, v ∪ Se a clique of size m. They then construct a joint distribution PXY where X is uniformly distributed on the oriented edges of G¯ and, given X = x, Y is one of the two vertices of the edge x, chosen uniforml random.
Where the gains come from
The proof for IB-Lagrangian follows a construction where if G has no k-clique, L1/2(PXY) is achieved by a simple deterministic encoder T0, and if G contains a k-clique K, there exists an encoder that strictly improves over T0. This leads to the conclusion that L1/2(PXY) = Λ0 whenever ω(G) Λ0 + δ whenever ω(G) ≥ k. p. 3 15)
In other words, T and Y are conditionally independent given X. To simplify the notation, in what follows we identify an encoder with the random variable
T it induces, and refer to T itself as the encoder whenever the channel PT|X is clear from the
context.Where the paper says it
The paper establishes NP-hardness of the threshold decision problems for both formulations of the information bottleneck. p. 1 More precisely, we establish computational hardness for both formulations (1. We prove that their threshold decision problems are NP-hard, the
NP-hardness of (1. We prove that their threshold decision problems are NP-hard, the
NP-hardness of (1. 2) is first obtained with the Lagrangian multiplier fixed at β = 1/2, then
extended to general rational β ∈ (0, 1). We prove that their threshold decision problems are NP-hard, the
NP-hardness of (1. 2) is first obtained with the Lagrangian multiplier fixed at β = 1/2, then
extended to general rational β ∈ (0, 1). 2) is first obtained with the Lagrangian multiplier fixed at β = 1/2, then
extended to general rational β ∈ (0, 1). Moreover, unless P = NP, no polynomial-time algorithm can approximate Lβ(PXY ) within additive error 1/(216 |X |3/2
), or IB(PXY , R) within
additive error 1/(576 |X |3/2
) (Theorems 1 and 2). 2) is first obtained with the Lagrangian multiplier fixed at β = 1/2, then
extended to general rational β ∈ (0, 1). Moreover, unless P = NP, no polynomial-time algorithm can approximate Lβ(PXY ) within additive error 1/(216 |X |3/2
), or IB(PXY , R) within
additive error 1/(576 |X |3/2
) (Theorems 1 and 2).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[1] S. Asoodeh and F.P. Calmon, Bottleneck Problems: An Information and EstimationTheoretic View, Entropy, vol. 22, pp. 1325, 2020
[2] E Benger S Asoodeh and J Chen The cardinality bound on the information bottleneck representations is tight in Proc IEEE International Symposium on Information Theory (ISIT), pp. 1478–1483, 2023
[3] R Brent Fast multiple-precision evaluation of elementary functions Journal of the ACM (JACM), vol. 23, pp. 242–251, 1976
[4] N Chayat and S Shamai Extension of an entropy property for binary input memoryless symmetric channels IEEE Trans. Inf. Theory 35 (1989), no. 5, 1077–1079
[5] T-W Chao and H-H H Yu When entropy meets Turán: new proofs and hypergraph Turán results, J London Math Soc. 113 (2026), no. 3, Paper No e70473
[6] G Chechik A Globerson N Tishby and Y Weiss Information bottleneck for Gaussian variables Journal of Machine Learning Research 6 (2005), 165–188
[7] M Dikshtein N Weinberger and S Shamai On information bottleneck for Gaussian processes in Proc IEEE Information Theory Workshop ITW, 2022, pp. 546–551
[8] K Etessami A Stewart and M Yannakakis A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing ACM Trans. Comput. Theory 6 (2014), no. 2, Art. 9
[9] M R Garey and D S Johnson Computers and Intractability: A Guide to the Theory of NP-completeness, W H Freeman, 1979
[10] Z Goldfeld and Y Polyanskiy The Information Bottleneck Problem and its Applications in Machine Learning IEEE J Sel. Areas Inf. Theory. 2020. Vol. 1(1):19-38
[11] S Hu Z Lou X Yan and Y Ye A Survey on Information Bottleneck, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 46, no. 8, pp. 5325-5344
[12] R M Karp Reducibility among combinatorial problems in Complexity of Computer Computations (R E Miller and J W Thatcher, eds.), Plenum Press, New York, 1972, pp. 85–103
[13] A Kolchinsky B D Tracey and S Van Kuyk Caveats for information bottleneck in deterministic scenarios, in Proc. International Conference on Learning Representations (ICLR), 2019
[14] T S Motzkin and E G Straus Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., vol. 17, pp- 533–540, 1965
[15] I Sason and S Verdú f-divergence inequalities, IEEE Transactions On Information Theory, vol. 62, pp. 5973–6006, 2016
[16] I Sutskover S Shamai and J Ziv Extremes of information combining IEEE Trans. Inf. Theory 51 (2005), no. 4, 1313–1325
[17] N Tishby F C Pereira and W Bialek The information bottleneck method in Proc. 37th Annual Allerton Conference on Communication, Control, and Computing, 1999
[18] Wyner A Ziv J A theorem on the entropy of certain binary sequences and applications Part I IEEE Trans. Inf. Theory 1973, 19, 769–772
[19] Wyner A A theorem on the entropy of certain binary sequences and applications—II. IEEE Trans. Inf. Theory 1973, 19, 772–777
[20] Witsenhausen H Wyner A conditional entropy bound for a pair of discrete random variables IEEE Trans. Inf.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved representation learning for tasks involving target variable Y given input X by finding a representation T such that I(Y; T) is maximized subject to a compression constraint I(X; T) <= R. This allows AI systems to create more compact feature sets that retain the most relevant information about the desired output while minimizing complexity.
-
Enhanced algorithm design for finding optimal representations using Lagrangian relaxation, which allows AI systems to optimize a trade-off between compressing input data X and retaining information about Y, even when the exact solution is computationally intractable.
-
Development of robust decision-making frameworks that can determine if a given representation T satisfies specific information criteria like I(Y; T) >= ϑ and I(X; T) <= R in polynomial time, which is crucial for setting quality benchmarks for learned models.
-
Creation of rigorous error bounds on the performance of these representations, showing that any polynomial-time approximation within a certain additive error is impossible unless P=NP, guiding researchers toward tractable distribution classes where exact computation or provable guarantees are achievable.
Abstract
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) = T I(Y;T): I(X;T) at most R of the information bottleneck problem, as well as its Lagrangian relaxation L β(P XY) = 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 X-(1+α), for every fixed α> 0. We also prove that computing the privacy funnel PF(P XY,r) = T I(Y;T): I(X;T) at least r and its Lagrangian relaxation Λ β(P XY) = 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 X-2.
Sources
Related papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Electromagnetic Signal and Information Theory: A Continuous-Aperture Array Perspective
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound