A Submodularitybased Clustering Algorithm for the Information Bottleneck and Privacy Funnel For the relevant data S that nests in the observation X, the information bottleneck (IB) aims to encode X into hat X in order to maximize the extracted useful information I(S;hat X) with the minimum coding rate I(X;hat X). For the dual privacy tunnel (PF) problem where S denotes the sensitivemathrm pmathrm rmathrm imathrm vmathrm amathrm tmathrm ewedge  data, the goal is to minimize the privacy leakage I(S;X) while maintain a certain level of utility I(X;hat X). For both problems, we propose an efficient iterative agglomerative clustering algorithm based on the minimization of the difference of submodular functions (IACMDSF). It starts with the original alphabet hat mathcal X: mathcal X and iteratively merges the elements in the current alphabet  hat mathcal X that optimizes the Lagrangian function I(S;hat X)lambda I(X;X). We prove that the best merge in each iteration of IACMDSF can be searched efficiently over all subsets of hat mathcal X by the existing MDSF algorithms. By varying the value of the Lagrangian multiplier lambda , we obtain the experimental results on a heart disease data set in terms of the Pareto frontier: I(S;hat X) mathrm vmathrm s. I(X;hat X). We show that our IACMDSF algorithm outperforms the existing iterative pairwise merge approaches for both PF and IB and is computationally much less complex.

The Convex Information Bottleneck Lagrangian The information bottleneck (IB) problem tackles the issue of obtaining relevant compressed representations T of some random variable X for the task of predicting Y. It is defined as a constrained optimization problem that maximizes the information the representation has about the task,     I ( T ; Y )    , while ensuring that a certain level of compression r is achieved (i.e.,     I ( X ; T ) xe2x89xa4 r    ). For practical reasons, the problem is usually solved by maximizing the IB Lagrangian (i.e.,      L IB   ( T ; xcexb2 )   I  ( T ; Y )  xe2x88x92 xcexb2 I  ( X ; T )     ) for many values of     xcexb2 xe2x88x88  0 , 1     . Then, the curve of maximal     I ( T ; Y )     for a given     I ( X ; T )     is drawn and a representation with the desired predictability and compression is selected. It is known when Y is a deterministic function of X, the IB curve cannot be explored and another Lagrangian has been proposed to tackle this problem: the squared IB Lagrangian:      L  sq xe2x88x92 IB    ( T ;  xcexb2 sq  )   I  ( T ; Y )  xe2x88x92  xcexb2 sq  I   ( X ; T )  2     . In this paper, we (i) present a general family of Lagrangians which allow for the exploration of the IB curve in all scenarios; (ii) provide the exact onetoone mapping between the Lagrange multiplier and the desired compression rate r for known IB curve shapes; and (iii) show we can approximately obtain a specific compression level with the convex IB Lagrangian for both known and unknown IB curve shapes. This eliminates the burden of solving the optimization problem for many values of the Lagrange multiplier. That is, we prove that we can solve the original constrained problem with a single optimization.