The Information Bottleneck (IB) framework is a general characterization of optimal representations in large scale learning that suggests an intriguing interpretation of efficient representations in deep learning in particular. It is based on the optimal trade off between the representation complexity and accuracy, both of which are quantified by mutual information. The problem is solved by alternating projections between the encoder and decoder of the representation, which can be performed locally at each representation level. The non-parametric IB framework, however, has several drawbacks: (i) the difficult estimation of information measures in high dimensions; (ii) the inability to extend the encoder beyond the training data -the need to to know the full joint distribution of the inputs and labels; (iii) the IB does not necessarily optimize the actual prediction of unseen labels, which can be critical when training the encoder from finite samples. Here we present a new framework, the Dual Information Bottleneck (dualIB), which improves all the above drawbacks. By switching the order in the KL-divergence between the representation decoder and data, formally the dual distortion, the optimal decoder becomes the geometric rather than the arithmetic mean of the input points. This conversion preserves exponential forms of the original distribution and consequently conserves the original features of the data. We show how to solve this new representation learning formulation and illustrate it's favorable properties over the original IB when trained from a small sample. We also analyze the critical points of the dualIB and discuss their importance for the quality of this approach.
Description:
The information bottleneck (IB) is an information theoretic principle for optimizing a mapping (encoding, e.g. clustering) of an input, to trade off two kinds of mutual information: minimize mutual information between the original input and the mapped version (to compress the input), and maximize mutual information between the mapped input and an output variable. It is related to a minimization of an (expected) Kullback-Leibler divergence betwen conditional distributions of an output variable.
In this paper, instead of the original IB, authors consider a previously presented dual problem of Felice and Ay, where the Kullback-Leibler divergence is minimized in the reverse direction: from the conditional distribution of output given encoding, p(y|hat x), to the conditional distribution given the original input, p(y|x).
The "dual problem" itself has a more complicated form than the original IB, authors claim this is "a good approximation" of the original bottleneck formulation, and aim to prove various "interesting properties" of it. 
- An iterative algorithm (Algorithm 1) similar to the original IB algorithm but with a few more steps is provided.
- A theorem about critical points where cardinality of the representation changes is given, similar to the IB critical points, and another theorem about difference of curves on an information plane between the IB and dual-IB solutions.
- Authors also show that if the true conditional distribution of outputs given inputs has an exponential-family form, the dual-IB decoder also has a form in the same family, which is said to reduce computational complexity of the algorithm.
Evaluation:
This is an entirely theory-based paper; although an algorithm is given, it is not instantiated for any concrete representation learning task, and no experiments at all are demonstrated.
Overall, I feel the motivation is not clear and strong enough. The abstract does not illustrate the importance of the mentioned "interesting properties" well enough for concrete tasks. Reading the paper, the clearest motivations seem to be improving computational complexity, and having a clearer connection to output prediction in cases where the predictor may be sub-optimal. However, authors do not quantify these well:
- The computational complexity improvement is not made clear (quantified) in a concrete IB optimization task: it seems it is only for exponential families, and even for them only affects one part of the algorithm, reducing its complexity from dim(X) to d; the impact of this is not tried out in any experiment.
- For output prediction, authors motivate that dual-IB could have a more direct connection e.g. "due to finite sample, in which it can be very different from the one obtained from the full distribution"). Authors further claim that the dual-IB formulation can "improve the generalization error when trained on small samples since the predicted label is the one used in practice". However, this is not tested at all: no prediction experiments, no quantification of generalization error, and no comparisons are done, thus the impact of the clearer connection to output prediction is not tested at all, and no clear theorems are given about it either.
The property that the algorithm "preserves exponential form of the original data distribution, if one exists" is interesting in principle, but it is unclear if any real data would anyway precisely have such a distribution; what happens if the data is not exactly in an exponential family?
In its current state the paper, although based on an interesting direction, in my opinion does not make a sufficient impact to be accepted to ICLR.
Other comments:
"Application to deep learning" mentioned in Section 1.5 is only a sincle sentence in the conclusions.
There have been some other suggested alternative IB formulations, for example the Deterministic IB of Strouse and Schwab (Neural Computation 2017) which also claim improved computational efficiency. How does the method compare to those?
Section 1.5 claims the algorithm "preserves the low dimensional sufficient statistics of the data": it is not clear what "preserves" means here, certainly it seems the decoder in Theorem 7 uses the same kinds of sufficient statistics as in the original data, but it is not clear that hat(x) would somehow preserve the same values of the sufficient statistics.