# Generalizing Bottleneck Problems

arXiv: https://arxiv.org/abs/1802.05861 · HTML: https://mlsanity.com/paper/1802.05861/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2018.

## Built on by (most cited first, 5 of 5)

- [No Free Lunch Theorem for Security and Utility in Federated Learning](https://mlsanity.com/paper/2203.05816/) (2022)
- [f-divergences and their applications in lossy compression and bounding generalization error](https://mlsanity.com/paper/2206.11042/) (2022)
- [Fundamental Limits of Perfect Concept Erasure](https://mlsanity.com/paper/2503.20098/) (2025)
- [Classification Utility, Fairness, and Compactness via Tunable Information Bottleneck and R'enyi Measures](https://mlsanity.com/paper/2206.10043/) (2022)
- [Source-Side Sufficiency for the Information Bottleneck: Exact Reduction and Finite-Block Equivalence](https://mlsanity.com/paper/2604.26744/) (2026)

## Abstract (arXiv)

Given a pair of random variables (X,Y)~ PXY and two convex functions f1 and f2, we introduce two bottleneck functionals as the lower and upper boundaries of the two-dimensional convex set that consists of the pairs left(If1(W; X), If2(W; Y)right), where If denotes f-information and W varies over the set of all discrete random variables satisfying the Markov condition W → X → Y. Applying Witsenhausen and Wyner's approach, we provide an algorithm for computing boundaries of this set for f1, f2, and discrete PXY. In the binary symmetric case, we fully characterize the set when (i) f1(t)=f2(t)=tlog t, (ii) f1(t)=f2(t)=t2-1, and (iii) f1 and f2 are both ℓβ norm function for β ≥ 2. We then argue that upper and lower boundaries in (i) correspond to Mrs. Gerber's Lemma and its inverse (which we call Mr. Gerber's Lemma), in (ii) correspond to estimation-theoretic variants of Information Bottleneck and Privacy Funnel, and in (iii) correspond to Arimoto Information Bottleneck and Privacy Funnel.