Generalizing Bottleneck Problems
share
Given a pair of random variables (X,Y)∼ 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 → X → 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 t, (ii) f_1(t)=f_2(t)=t^2-1, and (iii) f_1 and f_2 are both ℓ^β norm function for β > 1. 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.
READ FULL TEXT