Generalizing Bottleneck Problems

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.