The Information Bottleneck and the Privacy Funnel are NP-hard

arXiv:2610.22272 · cs.IT, math.IT · Submitted 2026-10-15 · Read on arXiv

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

Where the paper says it

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 authors establish computational hardness for both formulations (1. p. 1
Where the paper says it

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.

1) and (1.2), proving that their threshold decision problems are NP-hard. p. 1
Where the paper says it

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.

Specifically, they prove that the threshold decision problems are NP-hard by a reduction from the well-known Clique problem. p. 4
Where the paper says it

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].

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

Where the paper says it

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.

p. 5
Where the paper says it

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.

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. p. 5
Where the paper says it

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.

p. 5
Where the paper says it

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.

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

Where the paper says it

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).

Similarly, IB(PXY, R) cannot be approximated within additive error 1/(576X 3/2). p. 0
Where the paper says it

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 .

These results hold for standard bit models with rational input distributions and rational rate budgets. p. 1
Where the paper says it

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.

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

Where the paper says it

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).

Consequently, IB-Lagrangianβ is NP-hard, and no polynomial-time algorithm approximates Lβ(PXY) within an additive error of order κβ/(216X 3/2) unless P = NP. p. 0
Where the paper says it

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 .

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

Where the paper says it

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 .

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

Where the paper says it

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.

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

Where the paper says it

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.

The results hold for arbitrary stochastic encoders and rational input distributions. p. 1
Where the paper says it

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.

Conclusion

The authors have established NP-hardness of the threshold decision problems for both formulations of the information bottleneck. p. 1

Where the paper says it

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.

Theorems 1 and 2 also rule out polynomial-time approximation within the stated additive errors of order X −3/2, unless P = NP. p. 0
Where the paper says it

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 .

p. 0
Where the paper says it

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 .

The paper concludes that an elementary transformation extends Lagrangian hardness to every fixed rational β ∈ (0, 1) with corresponding inapproximability bounds. p. 1
Where the paper says it

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).

References

[1] S. Asoodeh and F. p. 1

Where the paper says it

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.

p. 1
Where the paper says it

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.

P. Calmon, Bottleneck Problems: An Information and EstimationTheoretic View, Entropy, vol. p. 2
Where the paper says it

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).

p. 2
Where the paper says it

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).

22, pp. 1325, 2020

[2] E. Benger, S. Asoodeh and J. p. 1

Where the paper says it

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.

Chen, The cardinality bound on the information bottleneck representations is tight, in Proc. p. 0
Where the paper says it

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 .

IEEE International Symposium on Information Theory (ISIT), pp. p. 0
Where the paper says it

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.

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. p. 1

Where the paper says it

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].

Inf. Theory 35 (1989), no. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 5

Where the paper says it

Finally, in Sections 3. 6, we combine the previous results, providing the proofs of Theorems 1 and 2.

London Math. Soc. 113 (2026), no. p. 0
Where the paper says it

22272v1 [cs. IT] 15 Oct 2026

p. 0
Where the paper says it

22272v1 [cs. IT] 15 Oct 2026

3, Paper No. p. 1
Where the paper says it

2) remains open. 2 Notation and Preliminaries All alphabets throughout the paper are finite, and we denote by log the logarithm in base 2.

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. p. 0

Where the paper says it

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.

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. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 1

Where the paper says it

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.

IEEE Trans. Inf. Theory 1973, 19, 772–777

[20] Witsenhausen H; Wyner A. A conditional entropy bound for a pair of discrete random variables, IEEE Trans. p. 1

Where the paper says it

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.

Inf. Theory 1975, 21, 493–501

[21] Zaidi A; Estella-Aguerri I; Shamai S. On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views. p. 0

Where the paper says it

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].

Entropy 2020, 22, 151

[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

Where the paper says it

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.

The paper establishes NP-hardness of the threshold decision problems for both formulations of the information bottleneck. p. 1

Where the paper says it

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.

Theorems 1 and 2 also rule out polynomial-time approximation within the stated additive errors of order X −3/2, unless P = NP. The authors have established NP-hardness of the threshold decision problems for both formulations of the information bottleneck. They also extend Lagrangian hardness to every fixed rational β ∈ (0, 1) with corresponding inapproximability bounds. p. 1
Where the paper says it

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).

p. 1
Where the paper says it

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).

The paper concludes that an elementary transformation extends Lagrangian hardness to every fixed polynomial-time computable real multiplier in this interval. p. 1
Where the paper says it

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).

p. 1
Where the paper says it

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).

The paper establishes NP-hardness of the threshold decision problems for both formulations of the information bottleneck. They also extend Lagrangian hardness to every fixed rational β ∈ (0, 1) with corresponding inapproximability bounds. The paper concludes that an elementary transformation extends Lagrangian hardness to every fixed polynomial-time computable real multiplier in this interval.

[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

  1. 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.

  2. 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.

  3. 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.

  4. 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