We propose a new framework for reasoning about information in complex systems. Our foundation is based on a variational extension of Shannon's information theory that takes into account the modeling power and computational constraints of the observer. The resulting predictive F-information encompasses mutual information and other notions of informativeness such as the coefficient of determination. Unlike Shannon's mutual information and in violation of the data processing inequality, F-information can be created through computation. This is consistent with deep neural networks extracting hierarchies of progressively more informative features in representation learning. Additionally, we show that by incorporating computational constraints, F-information can be reliably estimated from data even in high dimensions with PAC-style guarantees. Empirically, we demonstrate predictive F-information is more effective than mutual information for structure learning and fair representation learning.
Summary
The paper introduces a framework for quantifying information about one random variable, given another random variable (“side information”) and, importantly, a function class of allowed transformations that can be applied to the latter. This matches the typical scenario in machine learning, where observations (playing the role of side information) can be transformed (with a restricted class of transformation-functions) such that they become maximally predictive about another random variable of interest (“labels”). Using this framework, the paper defines the notion of conditional F-entropy and F-entropy (by conditioning on an empty set). Interestingly, both entropic quantities are shown to have many desirable properties known from Shannon entropy - and when allowing the function class of transformations to include all possible models F-entropies are equivalent to Shannon entropies. The paper then further defines “predictive F-information” which quantifies the increase in predictability about one random variable when given side information, under a restricted function-class of allowed transformations of the side information. Importantly, transformations of side information can increase predictive F-information (which is the basis for the notion of “usable” information), which is in contrast to the data processing inequality that applies to Shannon information and states that no transformation of a variable can increase predictability of another variable further than the un-transformed variable (information cannot be generated by transforming random variables). The paper highlights interesting properties of the F-quantities, most notably a PAC bound on F-information estimation from data, which gives reason to expect F-information estimation to be more data-efficient than estimating Shannon-information (particularly in the high-dimensional regime). This finding is confirmed by four types of interesting experiments, some of which make use of a modified version of a tree-structure learning algorithm proposed in the paper (using predictive F-information instead of Shannon mutual information).
Contributions
i) Proposal of a framework for measuring and reasoning about information that transformed random variables have about other random variables, when the class of transformation functions is restricted. Interesting properties are highlighted and corresponding proofs are given. Important conclusions to Shannon-information measures are drawn.
ii) PAC guarantees for estimating F-information quantities from data. A nice result that justifies some optimism about the scalability of F-information estimation.
iii) Modification of a tree-structure learning algorithm, and application to four types of experiments with comparisons against methods for estimating Shannon(-mutual)-information. 
Quality, Clarity, Novelty, Impact
The paper is very well written, the motivation and main results are clear and connections to known measures for information in complex systems are drawn (which often appear as corner-cases, or unrestricted cases of F-information). I am not an expert on various information measures, thus I cannot fully judge the novelty of the framework (given that the central idea is fairly simple and quite elegant, the main work lies in the proofs and connections to other frameworks). However, I have not seen the framework being discussed in the machine learning literature before. I personally would rate the potential impact of the F-information framework as high because it addresses many problems that Shannon-(mutual-)information has (hard to estimate, generality means complete blindness against model-classes). The experiments in the paper already illustrate how F-information could be very useful for a range of ML problems that cannot be tackled by strong competitor methods based on Shannon-information estimation. My only criticism is that the paper does not clearly state current limitations and shortcomings and does not comment on the difficulties / potential problems with solving the variational problem that is part of the definition of (conditional) F-information. I currently vote and argue for accepting the paper, though my assessment is of medium confidence only, and I am happy to take issues raised by the other reviewers and the rebuttal into account. I have not checked the proofs in the appendix in great detail.
Improvements
i) Please add a short section of current shortcomings and caveats, especially with regard to applying the methods in practice. 
ii) Please comment on solving the variational optimization problem (the infimum) which is part of the definition of (conditional) F-information. In particular, are there any theoretical statements / bounds / etc. to be made for the case where the infimum is not found exactly - does the measure degrade gracefully or can small errors in this optimization lead to wildly varying/divergent F-information? From a practical point-of-view: how was this optimization done in the experiments (particularly when involving a neural network model), how much computational overhead did this optimization add (and how does it compare against other methods, e.g. in terms of wall-clock time or other reasonable metrics, the more the better)?
iii) This is a minor one and feel free to completely ignore it. The name F-information might easily get confused with the use of f-divergences, perhaps there is a better, more informative name. Also, while I personally like the term “usable” in the title, I’m not so sure about “computational constraints” - the latter somehow suggests that the method has small computational footprint, or can easily scale to different computational budget. Perhaps there is a way that more strongly indicates that this refers to restrictions on the model-/function-class (which the term “usable” does already to some degree admittedly).
Minor Comments
a) Have you had any thoughts on how F-information could be used in a rate-distortion / information-bottleneck type framework for a theory of “relevant usable information”? This is probably beyond the scope of this paper, just out of curiosity.
b) The paragraph above 3.3 almost sounds a bit like Shannon (and the data processing inequality) was wrong. I’d rather phrase this as a “no-free-lunch problem” - while the DPI and Shannon (mutual) information is very elegant, it is necessary to make further assumptions/restrictions (the function class of allowed transformations) to make more fine-grained statements and define more precise (but less general) informational-quantities tailored to the specific function class.
c) When choosing function classes that allow for universal function approximation, would F-information degrade to Shannon information?