Bottleneck Problems:
Information and Estimation-Theoretic View^††thanks: This work was supported in part by NSF under grants CIF 1922971, 1815361, 1742836, 1900750, and CIF CAREER 1845852.

Optimization formulations that involve information-theoretic quantities (e.g., mutual information) have been instrumental in a variety of learning problems found in machine learning. A notable example is the information bottleneck ($\mathsf{IB}$) method [tishby2000information]. Suppose $Y$ is a target variable and $X$ is an observable correlated variable with joint distribution $P_{XY}$. The goal of $\mathsf{IB}$ is to learn a "compact" summary (aka bottleneck) $T$ of $X$ that is maximally "informative" for inferring $Y$. The bottleneck variable $T$ is assumed to be generated from $X$ by applying a random function $F$ to $X$, i.e., $T=F(X)$, in such a way that it is conditionally independent of $Y$ given $X$, that we denote by

The $\mathsf{IB}$ quantifies this goal by measuring the “compactness” of $T$ using the mutual information $I(X;T)$ and, similarly, “informativeness” by $I(Y;T)$. For a given level of compactness $R\geq 0$, $\mathsf{IB}$ extracts the bottleneck variable $T$ that solves the constrained optimization problem

where the supremum is taken over all randomized functions $T=F(X)$ satisfying $Y\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}X\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}T$.

The optimization problem that underlies the information bottleneck has been studied in the information theory literature as early as the 1970’s — see [Gerber, Witsenhausen_Wyner, Gerbator_Ahlswede1977, Wyner_Gerber] — as a technique to prove impossibility results in information theory and also to study the common information between $X$ and $Y$. Wyner and Ziv [Gerber] explicitly determined the value of $\mathsf{IB}(R)$ for the special case of binary $X$ and $Y$ — a result widely known as Mrs. Gerber’s Lemma [Gerber, networkinfotheory]. More than twenty years later, the information bottleneck function was studied by Tishby et al. [tishby2000information] and re-formulated in a data analytic context. Here, the random variable $X$ represents a high-dimensional observation with a corresponding low-dimensional feature $Y$. $\mathsf{IB}$ aims at specifying a compressed description of image which is maximally informative about feature $Y$. This framework led to several applications in clustering [slonim2000document, IB_clustering, Agglomerative_IB] and quantization [Quantization_IB, Quantization2_IB].

A closely-related framework to $\mathsf{IB}$ is the privacy funnel ($\mathsf{PF}$) problem [Makhdoumi2014FromTI, Calmon_fundamental-Limit, Asoodeh_Allerton]. In the $\mathsf{PF}$ framework, a bottleneck variable $T$ is sought to maximally preserve "information" contained in $X$ while revealing as little about $Y$ as possible. This framework aims to capture the inherent trade-off between revealing $X$ perfectly and leaking a sensitive attribute $Y$. For instance, suppose a user wishes to share an image $X$ for some classification tasks. The image might carry information about attributes, say $Y$, that the user might consider as sensitive, even when such information is of limited use for the tasks, e.g, location, or emotion. The $\mathsf{PF}$ framework seeks to extract a representation of $X$ from which the original image can be recovered with maximal accuracy while minimizing the privacy leakage with respect to $Y$. Using mutual information for both privacy leakage and informativeness, the privacy funnel can be formulated as

where the infumum is taken over all randomized function $T=F(X)$ and $r$ is the parameter specifying the level of informativeness. It is evident from the formulations (2) and (3) that $\mathsf{IB}$ and $\mathsf{PF}$ are closely related. In fact, we shall see later that they correspond to the upper and lower boundaries of a two-dimensional compact convex set. This duality has led to design of greedy algorithms [Makhdoumi2014FromTI, Sadeghi_PF] for estimating $\mathsf{PF}$ based on the agglomerative information bottleneck [Agglomerative_IB] algorithm. A similar formulation has recently been proposed in [PF_Adverserially] as a tool to train a neural network for learning a private representation of data $X$. Solving $\mathsf{IB}$ and $\mathsf{PF}$ optimization problems analytically is challenging. However, recent machine learning applications, and deep learning algorithms in particular, have reignited the study of both $\mathsf{IB}$ and $\mathsf{PF}$ (see Related Work).

In this paper, we first give a cohesive overview of the existing results surrounding the $\mathsf{IB}$ and the $\mathsf{PF}$ formulations. We then provide a comprehensive analysis of $\mathsf{IB}$ and $\mathsf{PF}$ from an information-theoretic perspective, as well as a survey of several formulations connected to the $\mathsf{IB}$ and $\mathsf{PF}$ that have been introduced in the information theory and machine learning literature. Moreover, we overview connections with coding problems such as remote source-coding [Noisy_SourceCoding_Dobrushin], testing against independence [Hypothesis_Testing_Ahslwede], and dependence dilution [Asoode_submitted]. Leveraging these connections, we prove a new cardinality bound for the bottleneck variable in $\mathsf{IB}$, leading to more tractable optimization problem for $\mathsf{IB}$. We then consider a broad family of optimization problems by going beyond mutual information in formulations (2) and (3). We propose two candidates for this task: Arimoto’s mutual information [Arimoto_Original_Paper] and $f$-information [Maxim_Strong_TIT]. By replacing $I(Y;T)$ and/or $I(X;T)$ with either of these measures, we generate a family of optimization problems that we referred to as the bottleneck problems. These problems are shown to better capture the underlying trade-offs intended by $\mathsf{IB}$ and $\mathsf{PF}$. More specifically, our main contributions are listed next.

• •

  Computing $\mathsf{IB}$ and $\mathsf{PF}$ are notoriously challenging when $X$ takes values in a set with infinite cardinality (e.g., $X$ is drawn from a continuous probability distribution). We consider three different scenarios to circumvent this difficulty. First, we assume that $X$ is a Gaussian perturbation of $Y$, i.e., $X=Y+N^{\mathsf{G}}$ where $N^{\mathsf{G}}$ is a noise variable sampled from a Gaussian distribution independent of $Y$. Building upon the recent advances in entropy power inequality in [EPI_Courtade], we derive a sharp upper bound for $\mathsf{IB}(R)$. As a special case, we consider jointly Gaussian $(X,Y)$ for which the upper bound becomes tight. This then provides a significantly simpler proof for the fact that in this special case the optimal bottleneck variable $T$ is also Gaussian than the original proof given in [GaussianIB]. In the second scenario, we assume that $Y$ is a Gaussian perturbation of $X$, i.e., $Y=X+N^{\mathsf{G}}$. This corresponds to a practical setup where the feature $Y$ might be perfectly obtained from a noisy observation of $X$. Relying on the recent results in strong data processing inequality [calmon2015strong], we obtain an upper bound on $\mathsf{IB}(R)$ which is tight for small values of $R$. In the last scenario, we compute second-order approximation of $\mathsf{PF}(r)$ under the assumption that $T$ is obtained by Gaussian perturbation of $X$, i.e., $T=X+N^{\mathsf{G}}$. Interestingly, the rate of increase of $\mathsf{PF}(r)$ for small values of $r$ is shown to be dictated by an asymmetric measure of dependence introduced by Rényi [Renyi-dependence-measure].

• •

  We extend the Witsenhausen and Wyner’s approach [Witsenhausen_Wyner] for analytically computing $\mathsf{IB}$ and $\mathsf{PF}$. This technique converts solving the optimization problems in $\mathsf{IB}$ and $\mathsf{PF}$ to determining the convex and concave envelopes of a certain function, respectively. We apply this technique to binary $X$ and $Y$ and derive a closed form expression for $\mathsf{PF}(r)$– we call this result Mr. Gerber’s Lemma.

• •

  Relying on the connection between $\mathsf{IB}$ and noisy source coding [Noisy_SourceCoding_Dobrushin] (see [Bottleneck_Polyanskiy, Bottleneck_Shamai]), we show that the optimal bottleneck variable $T$ in optimization problem (2) takes values in a set ${\mathcal{T}}$ with cardinality $|{\mathcal{T}}|\leq|{\mathcal{X}}|$. Compared to the best cardinality bound previously known (i.e., $|{\mathcal{T}}|\leq|{\mathcal{X}}|+1$), this result leads to a reduction in the search space’s dimension of the optimization problem (2) from $\mathbb{R}^{|{\mathcal{X}}|^{2}}$ to $\mathbb{R}^{|{\mathcal{X}}|(|{\mathcal{X}}|-1)}$. Moreover, we show that this does not hold for $\mathsf{PF}$, indicating a fundamental difference in optimizations problems (2) and (3).

• •

  Following [strouse2017dib, Asoodeh_Allerton], we study the deterministic $\mathsf{IB}$ and $\mathsf{PF}$ (denoted by $\mathsf{dIB}$ and $\mathsf{dPF}$) in which $T$ is assumed to be a deterministic function of $X$, i.e., $T=f(X)$ for some function $f$. By connecting $\mathsf{dIB}$ and $\mathsf{dPF}$ with entropy-constrained scalar quantization problems in information theory [Polyanskiy_Distilling], we obtain bounds on them explicitly in terms of $|{\mathcal{X}}|$. Applying these bounds to $\mathsf{IB}$, we obtain that $\frac{\mathsf{IB}(R)}{I(X;Y)}$ is bounded by one from above and by $\min\{\frac{R}{H(X)},\frac{e^{R}-1}{|{\mathcal{X}}|}\}$ from below.

• •

  By replacing $I(Y;T)$ and/or $I(X;T)$ in (2) and (3) with Arimoto’s mutual information or $f$-information, we generate a family of bottleneck problems. We then argue that these new functionals better describe the trade-offs that were intended to be captured by $\mathsf{IB}$ and $\mathsf{PF}$. The main reason is three-fold: First, as illustrated in Section II-C, mutual information in $\mathsf{IB}$ and $\mathsf{PF}$ are mainly justified when $n\gg 1$ independent samples $(X_{1},Y_{1}),\dots,(X_{n},Y_{n})$ of $P_{XY}$ are considered. However, Arimoto’s mutual information allows for operational interpretation even in the single-shot regime (i.e., for $n=1$). Second, $I(Y;T)$ in $\mathsf{IB}$ and $\mathsf{PF}$ is meant to be a proxy for the efficiency of reconstructing $Y$ given observation $T$. However, this can be accurately formalized by probability of correctly guessing $Y$ given $T$ (i.e., Bayes risk) or minimum mean-square error (MMSE) in estimating $Y$ given $T$. While $I(Y;T)$ bounds these two measures, we show that they are precisely characterized by Arimoto’s mutual information and $f$-information, respectively. Finally, when $P_{XY}$ is unknown, mutual information is known to be notoriously difficult to estimate. Nevertheless, Arimoto’s mutual information and $f$-information are easier to estimate: While mutual information can be estimated with estimation error that scales as $O(\log n/\sqrt{n})$ [Shamir_IB], Diaz et a. [Diaz_Robustness] showed that this estimation error for Arimoto’s mutual information and $f$-information is $O(1/\sqrt{n})$.

  We also generalize our computation technique that enables us to analytically compute these bottleneck problems. Similar as before, this technique converts computing bottleneck problems to determining convex and concave envelopes of certain functions. Focusing on binary $X$ and $Y$, we derive closed form expressions for some of the bottleneck problems.

In this section, we review the information bottleneck and its closely related functional, the privacy funnel. We then prove some analytical properties of these two functionals and develop a convex analytic approach which enables us to compute closed-form expressions for both these two functionals in some simple cases.

To precisely quantify the trade-off between these two conflicting goals, the $\mathsf{IB}$ optimization problem (2) was proposed [tishby2000information]. Since any randomized function $T=F(X)$ can be equivalently characterized by a conditional distribution, (2) can be instead expressed as

where $R$ and $\tilde{R}$ denote the level of desired compression and informativeness, respectively. We use $\mathsf{IB}(R)$ and $\widetilde{\mathsf{IB}}(\tilde{R})$ to denote $\mathsf{IB}(P_{XY},R)$ and $\widetilde{\mathsf{IB}}(P_{XY},\tilde{R})$, respectively, when the joint distribution is clear from the context. Notice that if $\mathsf{IB}(P_{XY},R)=\tilde{R}$, then $\widetilde{\mathsf{IB}}(P_{XY},\tilde{R})=R$.

Now consider the setup where data $X$ is required to be disclosed while maintaining the privacy of a sensitive attribute, represented by $Y$. This goal was formulated by $\mathsf{PF}$ in (3). As before, replacing randomized function $T=F(X)$ with conditional distribution $P_{T|X}$, we can equivalently express (3) as

where $\tilde{r}$ and $r$ denote the level of desired privacy and informativeness, respectively. The case $\tilde{r}=0$ is particularly interesting in practice and specifies perfect privacy, see e.g., [Calmon_fundamental-Limit, Rassouli_Perfect]. As before, we write $\widetilde{\mathsf{PF}}(\tilde{r})$ and $\mathsf{PF}(r)$ for $\widetilde{\mathsf{PF}}(P_{XY},\tilde{r})$ and $\mathsf{PF}(P_{XY},r)$ when $P_{XY}$ is clear from the context.

The following properties of $\mathsf{IB}$ and $\mathsf{PF}$ follow directly from their definitions. The proof of this result (and any other results in this section) is given in Appendix LABEL:Appendix_ProofSecIB_PF.

According to this theorem, we can always restrict both $R$ and $r$ in (4) and (5), respectively, to $[0,H(X)]$ as $\mathsf{IB}(R)=\mathsf{PF}(r)=I(X;Y)$ for all $r,R\geq H(X)$.

Define ${\mathcal{M}}={\mathcal{M}}(P_{XY})\subset\mathbb{R}^{2}$ as

It can be directly verified that ${\mathcal{M}}$ is convex. According to this theorem, $R\mapsto\mathsf{IB}(R)$ and $r\mapsto\mathsf{PF}(r)$ correspond to the upper and lower boundary of ${\mathcal{M}}$, respectively. The convexity of ${\mathcal{M}}$ then implies the concavity and convexity of $\mathsf{IB}$ and $\mathsf{PF}$. Fig. 1 illustrates the set ${\mathcal{M}}$ for the simple case of binary $X$ and $Y$.

While both $\mathsf{IB}(0)=0$ and $\mathsf{PF}(0)=0$, their behavior in the neighborhood around zero might be completely different. As illustrated in Fig. 1, $\mathsf{IB}(R)>0$ for all $R>0$, whereas $\mathsf{PF}(r)=0$ for $r\in[0,r_{0}]$ for some $r_{0}>0$. When such $r_{0}>0$ exists, we say perfect privacy occurs: there exists a variable $T$ satisfying $Y\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}X\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}T$ such that $I(Y;T)=0$ while $I(X;T)>0$; making $T$ a representation of $X$ having perfect privacy (i.e., no information leakage about $Y$). A necessary and sufficient condition for the existence of such $T$ is given in [Asoode_submitted, Lemma 10] and [Calmon_fundamental-Limit, Theorem 3], described next.

In light of this theorem, we obtain that perfect privacy occurs if $|{\mathcal{X}}|>|{\mathcal{Y}}|$. It also follows from the theorem that for binary $X$, perfect privacy cannot occur (see Fig. 1(a)).

Theorem 1 enables us to derive a simple bounds for $\mathsf{IB}$ and $\mathsf{PF}$. Specifically, the facts that $\frac{\mathsf{PF}(r)}{r}$ is non-decreasing and $\frac{\mathsf{IB}(R)}{R}$ is non-increasing immediately result in the the following linear bounds.

In light of this theorem, if $\mathsf{PF}(r)=r$, then $I(X;Y)=H(X)$, implying $X=g(Y)$ for a deterministic function $g$. Conversely, if $X=g(Y)$ then $\mathsf{PF}(r)=r$ because for all $T$ forming the Markov relation $Y\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}g(Y)\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}T$, we have $I(Y;T)=I(g(Y);T)$. On the other hand, we have $\mathsf{IB}(R)=R$ if and only if there exists a variable $T^{*}$ satisfying $I(X;T^{*})=I(Y;T^{*})$ and thus the following double Markov relations

It can be verified (see [csiszarbook, Problem 16.25]) that this double Markov condition is equivalent to the existence of a pair of functions $f$ and $g$ such that $f(X)=g(Y)$ and $(X,Y)\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}f(X)\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}T^{*}$. One special case of this setting, namely where $g$ is an identity function, has been recently studied in details in [kolchinsky2018caveats] and will be reviewed in Section II-E. Theorem 3 also enables us to characterize the "worst" joint distribution $P_{XY}$ with respect to $\mathsf{IB}$ and $\mathsf{PF}$. As demonstrated in the following lemma, if $P_{Y|X}$ is an erasure channel then $\frac{\mathsf{PF}(r)}{r}=\frac{\mathsf{IB}(R)}{R}=\frac{I(X;Y)}{H(X)}$.

The bounds in Theorem 3 hold for all $r$ and $R$ in the interval $[0,H(X)]$. We can, however, improve them when $r$ and $R$ are sufficiently small. Let $\mathsf{PF}^{\prime}(0)$ and $\mathsf{IB}^{\prime}(0)$ denote the slope of $\mathsf{PF}(\cdot)$ and $\mathsf{IB}(\cdot)$ at zero, i.e., $\mathsf{PF}^{\prime}(0)\coloneqq\lim_{r\to 0^{+}}\frac{\mathsf{PF}(r)}{r}$ and $\mathsf{IB}^{\prime}(0)\coloneqq\lim_{R\to 0^{+}}\frac{\mathsf{IB}(R)}{R}$.

This theorem provides the exact values of $\mathsf{PF}^{\prime}(0)$ and $\mathsf{IB}^{\prime}(0)$ and also simple bounds for them. Although the exact expressions for $\mathsf{PF}^{\prime}(0)$ and $\mathsf{IB}^{\prime}(0)$ are usually difficult to compute, a simple plug-in estimator is proposed in [Hypercontractivity_NIPS2017] for $\mathsf{IB}^{\prime}(0)$. This estimator can be readily adapted to estimate $\mathsf{PF}^{\prime}(0)$. Theorem 4 reveals a profound connection between $\mathsf{IB}$ and the strong data processing inequality (SDPI) [Ahlswede_Gacs]. More precisely, thanks to the pioneering work of Anantharam et al. [anantharam], it is known that the supremum of $\frac{D_{\mathsf{KL}}(Q_{Y}\|P_{Y})}{D_{\mathsf{KL}}(Q_{X}\|P_{X})}$ over all $Q_{X}\neq P_{X}$ is equal the supremum of $\frac{I(Y;T)}{I(X;T)}$ over all $P_{T|X}$ satisfying $Y\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}X\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}T$ and hence $\mathsf{IB}^{\prime}(0)$ specifies the strengthening of the data processing inequality of mutual information. This connection may open a new avenue for new theoretical results for $\mathsf{IB}$, especially when $X$ or $Y$ are continuous random variables. In particular, the recent non-multiplicative SDPI results [Polyanskiy, calmon2015strong] seem insightful for this purpose.

In many practical cases, we might have $n$ i.i.d. samples $(X_{1},Y_{1}),\dots,(X_{n},Y_{n})$ of $(X,Y)\sim P_{XY}$. We now study how $\mathsf{IB}$ behaves in $n$. Let $X^{n}\coloneqq(X_{1},\dots,X_{n})$ and $Y^{n}\coloneqq(Y_{1},\dots,Y_{n})$. Due to the i.i.d. assumption, we have $P_{X^{n}Y^{n}}(x^{n},y^{n})=\prod_{i=1}^{n}P_{XY}(x_{i},y_{i})$. This can also be described by independently feeding $X_{i}$, $i\in[n]$, to channel $P_{Y|X}$ producing $Y_{i}$. The following theorem, demonstrated first in [Witsenhausen_Wyner, Theorem 2.4], gives a formula for $\mathsf{IB}$ in terms of $n$.

This theorem demonstrates that an optimal channel $P_{T^{n}|X^{n}}$ for i.i.d. samples $(X^{n},Y^{n})\sim P_{XY}$ is obtained by the Kronecker product of an optimal channel $P_{T|X}$ for $(X,Y)\sim P_{XY}$. This, however, may not hold in general for $\mathsf{PF}$, that is, we might have $\mathsf{PF}(P_{X^{n}Y^{n}},nr)<n\mathsf{PF}(P_{XY},r)$, see [Calmon_fundamental-Limit, Proposition 1] for an example.