Generalizing Bottleneck Problems

Given a pair of random variables $(X,\ Y)\sim P_{XY}$ and two convex functions $f_{1}$ and $f_{2}$, we introduce two bottleneck functionals as the lower and upper boundaries of the two-dimensional convex set that consists of the pairs $(I_{f_{1}}(W;X),\ I_{f_{2}}(W;Y))$, where $I_{f}$ denotes $f$-information and $W$ varies over the set of all discrete random variables satisfying the Markov condition $W\rightarrow X\rightarrow Y$. Applying Witsenhausen and Wyner's approach, we provide an algorithm for computing boundaries of this set for $f_{1}, f_{2}$, and discrete $P_{XY}$. In the binary symmetric case, we fully characterize the set when (i) $f_{1}(t)=f_{2}(t)=t\log t$, (ii) $f_{1}(t)=-f_{2}(t)=t^{2}-1$, and (iii) $f_{1}$ and $f_{2}$ are both $\ell^{\beta}$ norm function for $\beta\geq 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. An extended version of this paper is available in [1].