A Theory of Usable Information under Computational Constraints
Authors: Yilun Xu
Shengjia Zhao
Jiaming Song
Russell Stewart
Stefano Ermon
Venue:  (2020)

Abstract: 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 V-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, V-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, V-information can be reliably estimated from data even in high dimensions with PAC-style guarantees. Empirically, we demonstrate predictive V-information is more effective than mutual information for structure learning and fair representation learning. Codes are available at https://github.com/Newbeeer/V-information .

Published as a conference paper at ICLR 2020
A THEORY OF USABLE INFORMATION UNDER COMPUTATIONAL CONSTRAINTS
Yilun Xu
Shengjia Zhao Stanford University
Jiaming Song
CFCS, Peking University xuyilanêpku, edu.
Stanford University
s j whhaassttafoodd...
t toongics stanford.ed:
Russell Stewart
Stefano Ermon
russell. sb. nebeleeeee e emaami ila com
Stanford University ermonêcs stafford.edd
ABSTRACT
We propose new framework for reasoning about information in complex systems. Our foundation is based on variational extension of Shannon's information theory that takes into account the modeling power and computational constraints of the observer. The resulting predictive V-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, V-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, V-information can be reliably estimated from data even in high dimensions with PtC-style guarantees. Empirically, we demonstrate predictive V-information more effective than mutual information for structure learning and fair representation learning.
INTRODUCTION
Extracting actionable information from noisy, possibly redundant, and nigh-dimenssooal data sources key computational and statistical challenge at the core of Al and machine learning. Information theory, which lies at the foundation of Al and machine learning, provides a conceptual framework characterize information in mathematically rigorous sense (Shannon & Weaver, 1948; Cover & Thomas, 1991). However, important computational aspects are not considered in information theory. To illustrate this, consider dataset of encrypted messages intercepted from an opponent. According to information theory, these encrypted messages have high mutual information with the opponent's plans. Indeed, with infinite computation, the messages Modern cryptography originated from this observation by Shannon that perfect secrecy is (essentially) impossible if the adversary is computationally unbounded (Shannon & Weaver, 1948). This motivated cryptographers to consider restricted classes of adversaries that have access to limited computational resources (Pass & Shelat, 2010). More generally, it known that information theoretic quantities can be expressed in terms of betting games (Cover & Thomas, 1991). For example, the (conditional) entropy of random variable X is directly related how predictable X is in certain betting game, where an agent is rewarded for correct guesses. Yet, the standard definition unrealistically assumes agents computationally unbounded, i.e., they can employ arbitrarily complex prediction schemes.
be decrypted and the plans revealed.
Leveraging modern ideas from variational inference and learning (Ranganath et al., 2013; Kingma & Welling, 2013; LeCun et al., 2015), we propose an alternative formulation based realistic computational constraints that in many ways closer to our intuitive notion of information, which term predictive V-information. Without constraints, predictive V-information specializes to classic mutual information. Under natural restrictions, V-information specializes to other well-known notions of predictiveness, such the coefficient of determination (R²). A consequence of this new formulation that computation can "create usable information" (e.g.. by decrypting the intercepted messages), invalidating the famous data processing inequality. This generalizes the idea that clever

---

Published as a conference paper at ICLR 2020
feature extraction enables prediction with extremely simple (e.g., linear) classifiers, key notion in modern representation and deep learning (LeCun et al., 2015).
As an additional benefit, we show that predictive y-information can be estimated with statistical guarantees using the Probably Approximately Correct framework (Valiant, 1984). This is in sharp contrast with Shannon information, which is well known to be difficult to estimate for high dimen- sional or continuous random variables (Battiti, 1994). Theoretically we show that the statistical guarantees of estimating / information translate to statistical guarantees for a variant of the Chow-Liu algorithm for structure learning. practice, when the observer employs deep neural networks as a prediction scheme, V-information outperforms methods that approximate Shannon information in various applications, including Chow-Liu tree contruction in high dimension and gene regulatory network inference.
DEFINITIONS AND NOTATIONS
To formally define the predictive V-information, we begin with formal model of computationally bounded agent trying to predict the outcome of a real-valued random variable Y; the agent is either provided another real-valued random variable X as side information, provided no side information Øs We use X' and y to denote the samples spaces of and Y respectively (while assuming they are separable), and use P(X)) to denote the set of all probability measures over the Borel algebra on X (P()) similarly defined for )).
Definition 1 (Predictive Family). 'Let Ω = {f X (0) + P())). We say that V C Q is predictive family if it satisfies
Yf E V, VP E range(f),
s.t. Vx =
(I)
A predictive family is set of predictive models the agent is allowed to use, e.g., due to computational or statistical constraints. We refer to the additional condition in (1. as optional ignorance. Intuitively, it means that the agent can, in the context of the prediction game define next, ignore the side information if she chooses to.
Definition 2 (Predictive conditional V-entropy). Let X, be two random variables taking values in X' x y, and V be predictive family. Then the predictive conditional V-entropy is defined as
Hv(Y = inf Ex [- log (x)]
JEV
Hy = inf Eyyy [o [v)]
SEV
We additionally call ()( the V-entropy, and also denote it as Hv(Y)
In notation f is function X' U (Ø) P()), so [(r) E P(Y) is a probability measure y chosen based on the received side information & (we use f({] instead of the more conventional f(-)); and [3r (1)) IR is the value of the density evaluated y E Intuitively, V (conditional) entropy is the smallest expected negative log-likelihood that can be achieved predicting Y given observation (side information) X (or side information Ø), using models from V. (1) means that whenever the agent can use P to predict Y's outcomes, has the option to ignore the input, and use P no matter whether X is observed or not.
Definition 2 generalizes several known definitions of uncertainty. For example, as shown in proposition 2, if the V is the largest possible predictive family that includes all possible mod- H X) and
els, i.e. V = Ω2 then Definition 2 reduces to Shannon entropy: HY|Y))) Hy (Y) HYY). By choosing more restrictive families V, recover several other notions of uncertainty such as trace of covariance, as will be shown in Proposition 1.
Shannon mutual information is measure of changes in entropy when conditioning on new variables:
(Y Here, we will use predictive V-entropy define an analogous quantity, (x - Y), to represent the change in predictability of an output variable Y when given side information X.
Y(;;Y) HYY) H(| Hn((Y)
Regularity Conditions: To minimize technical overhead we restrict out discussion only to distributions with probability density functions (PDF) or probability mass functions (PMF) with respect to the underlying measure. Also & X.
2

---

Published as a conference paper at ICLR 2020
Definition 3 (Predictive V-information), Let X, be two random variables taking values in X x ) and V be a predictive family. The predictive V- V-information from X to Y is defined as
Tv(X + Y) Hy(()2)) -Xx(x)
(3)
2.1 IMPORTANT SPECIAL CASES
Several important notions of uncertainty and predictiveness special cases of our definition. Note that when we are defining V--ntropy of a random variable in sample space ) E R (without side information), out of convenience we can assume X is empty X' = Ø (this does not violate our requirement that Ø & X.)
Proposition 1. For V-entropy and V-information, we have
1. Let S2 be as in Def. 1. Then HY(Y) is the Shannon entropy, Ho(Y XX) is the Shannon conditional entropy, and lY - X) is the Shannon mutual information.
2. Let y= =
Rd and V = [f {2) + PH μ E R where Pa is the distribution with density + --lls-nllzz where Z = -1ll--plle dy, then the V-entropy of a random variable Y equals ils mean absolute deviation, up an additive constant.
3. Let y =Rd and V =tf: (0) + Nu, Σ) e R 11/21axa). then the V-entropy of a random variable Y equals the trace of its covariance tr (Cov(Y)), up to an additive constant.
4. Let (f: Qc,0, θ). where Qe,o a distribution in a minimal exponential family with sufficient statistics y Rd and set of natural parameters Q. For a random variable Y with expected sufficient statistics py = E[t(Y)), the V-entropy of Y is the maximum Shannon entropy over all random variables Y with identical expected sufficient statistics, i.e. E{((())= pyy
5. Let y Rdd be any vector space, and V {f : N((()), X:0 H N(, EH E 1/2Iaxa. E D). where 4 is the set of linear functions (ó X - ]. then V-information [v(X Y) equals the (unnormalized) maximum coefficient of determination R². tr (Cov(Y)) for linear regression.
The trace of covariance represents a natural notion of uncertainty for example, a random variable with zero variance (when d = 1,tr (Cov(Y)) = Var(Y))) is trivial to predict. Proposition 1.3 shows that the trace of covariance corresponds an agent restricted to make predictions using certain Gaussian models. More broadly, similar analogy can be drawn for other exponential families of distributions. the same spirit, the coefficient of determination, also known as the fraction of variance explained, represents a natural notion of informativeness for computationally bounded agents. Also note that in the case of Proposition 1.4, the V-entropy is invariant if the expected sufficient statistics remain the same.
notion of surprise (in the Shannon sense) for
PROPERTIES OF V- V-INFORMATION
3.1 ELEMENTARY PROPERTIES
We first show several elementary properties of V-entropy and V-information. In particular, V- information preserves many properties of Shannon information that are desirable in machine learning context. For example, mutual information (and V-information) should be non non-negative as conditioning on additional side information X should not reduce an agent's 's ability to predict Y.
Proposition 2. Let Y and X be any random variables on y and X, and V and U be any predictive families, then we have
1. Monotonicity: If C U, then Hy(Y) 2 Hu(Y), Hv X) 2 Hu(Y |X).
2. Non-Negativity: [x(X 2.)20.
3. Independence: 1f X is independent YYY, Ty(X -Y = Tv(Y X)= 0.
3

---

Published as a conference paper at ICLR 2020
The optional ignorance requirement in Eq.(1) is technical condition needed for these properties to hold. Intuitively, it guarantees that conditioning on side information does not restrict the class of densities the agent can use to predict Y. This property is satisfied by many existing machine learning models, often by setting some weights to zero so that an input is effectively ignored.
3.2 ON THE PRODUCTION OF INFORMATION THROUGH PREPROCESSING
The Data Processing Inequality guarantees that computing data cannot increase its mutual infor- mation with other random variables. Formally, letting & X + X' be any function, {(X) cannot have higher mutual information with Y than X: [(t(X);;))))) Y) s YY; But is this property desirable? In analyzing optimal communication, yes - demonstrates a fundamental limit the number of bits that can be transmitted through a communication channel. However, we argue that in machine learning settings this property is less appropriate.
Consider an RSA encryption scheme where the public key is known. Given plain text and its corresponding enerypted text X, if we have infinite computation, we can perfectly compute one from the other. Therefore, the plain text and the encrypted text should have identical Shannon mutual information with respect to any label Y we want to predict. However, to any human (or machine learning algorithm), it is certainly easier to predict the label from the plain text than the encrypted text. In other words, decryption increases a human's is ability to predict the label: processing increases the "usable information". More formally, denoting & as the decryption algorithm and V as a class of natural language processing functions, we have that: [v(t(X) - Y) > (y(X - Y) x O.
As another example, consider the mutual information between image's pixels and its label. Due to data processing inequality, we cannot expect to use a function to map raw pixels to "features" that have higher mutual information with the label. However, the fundamental principle of representation learning precisely the ability to learn predictive features - functions of the raw inputs that enable predictions with higher accuracy. Because of this key difference between V-information and Shannon information, machine learning practices such as representation learning can be justified in the information theoretic context.
3.3 ON THE ASYMMETRY OF PREDICTIVE V-INFORMATION
V-information also captures the intuition that sometimes, it is easy to predict from X but not vice versa. In fact, modern cryptography is founded on the assumption that certain functions h : X' - y are one-way, meaning that there exists an polynomial algorithm to compute h(x) but no polynomial algorithm to compute h -yy- This means that if V contains all polynomial-time computable functions, then Tx(X- M(X) > (x()) + X).
This property is also reasonable in the machine learning context. For example, several important methods for causal discovery (Peters al., 2017) rely on this asymmetry: if X causes Y, then usually it is easier to predict Y from X than vice versa, another commonly used assumption is that Y Y|X can be accurately modeled by a Gaussian distribution, while X|Y cannot (Pearl, 2000).
PAC GUARANTEES FOR V-INFORMATION ESTIMATION
For many practical applications of mutual information (e.g., structure learning), we do not know the joint distribution of X, Y. so cannot directly compute the mutual information. Instead we only have samples ((x;, y:)) ) X, Y and need to estimate mutual information from data.
Shannon information is notoriously difficult to estimate for high dimensional random variables. Although non- pan-mmrmettiic estimators of mutual information exist (Kraskov et al., 2004; Darbellay & Vajda, 1999; Gao et al., 2017), these estimators do not scale to high dimensions. Several variational estimators for Shannon information have been recently proposed (van den Oord et al., 2018; Nguyen et al., 2010; Belghazi et al., 2018), but have two shortcomings: due to their variational assumptions, their bias/variance tradeoffs are poorly understood and they are still not efficient enough for high dimensional problems. For example, the CPC estimator suffers from large bias, since its estimates saturate log N where N is the batch size (van den Oord et al., 2018; Poole et al., 2019); the NWJ estimator suffers from large variance that grows at least exponentially in the ground-truth mutual information (Song& & Ermon, 2019). Please see Appendix for more details and proofs.
4

---

Published as a conference paper at ICLR 2020
On the other hand, V-information is explicit about the assumptions (as feature instead of bug). V-information is also easy to estimate with guarantees we can bound the complexity of V (such as its Radamacher or covering number complexity) As we will show, bounds on the complexity of V directly translate to PAC (Valiant, 1984) bounds for V-information estimation. In practice, we can efficiently optimize over V. e.g., via gradient descent. In this paper we will present the Rademacher complexity version; other complexity measures (such as covering number) can be derived similarly.
Definition (Empirical V-information), Let X, be two random variables taking values x.Y and D = (1 H=) ~ X. denotes the set of samples drawn from the joint distribution over X and V. is predictive family. The empirical V-information (under D) is the following V-information under the empirical distribution defined via D:
inf 1 JeV [
1
-Y;));
= inf JEV D
log
log
(4)
f(0((y))
f(r.((y))
Then we have the following PAC bound the empirical V-information:
Theorem 1. Assume f E V. x E X, E log [v) E [-B, B). Then for any ā E (0,0.5),
with probability at least 26, we have:
2oog
-X -(x - Y:D) S 49 (Gv) + 2B
(5)
|D]
where we define the function family Gv {glg(z, y) = log f f(), e V}. and Ry (g) denotes the Rademacher complexity of G with sample number N.
Typically, the Rademacher complexity term satisfies Ri p (Gv) -(P))) (Bartlett & Mendelson, 2001; Gao & Zhou, 2016). It's worth noticing that complex function family V (i.c., with large Rademacher complexity) could lead to overfitting. On the other hand, an overly-simple V may not be expressive enough to capture the relationship between X and Y. As an example of the theorem, we provide a concrete estimation bound when V is chosen to be linear functions mapping X' to the mean of Gaussian distribution. This shown in Proposition
lead to the coefficient of determination.
Corollary 1.1. Assume X' {xr E Rdd, ||0/|2 S kiz} and y ty E Rd,, |1yl|2 S k. If
V (f : f(x) = N(Wx + b, 1), f = (c, T), W E TRduxd= b, d, RR., ([ b)ll I 1}
Denote M = (ke + k2y) 2 + log 2n, then vo E (0, 0.5). with probability at least 26:
Iv(x +)) -) -
M
1 2 log 1 g
/
Similar results can be obtained using other classes of machine learning models with known (Rademacher) complexity.
5
STRUCTURE LEARNING WITH W V-INFORMATION
Among many possible applications of V-information, we show how to use it to perform structure learning with provable guarantees. The goal of structure learning is to learn a directed graphical model (Bayesian network) or undirected graphical model (Markov network) that best captures the (conditional) independence structure of an underlying data generating process. Structure learning is difficult in general, but if we restrict ourselves to certain set of graphs G, there are efficient algorithms. In particular, the Chow-Liu algorithm (Chow & Liu, 1968) can efficiently learn tree graphs (i.e. G is the set of trees). Chow & Liu (1968) show that the problem can be reduced to:
g* arg max gEGere
Σ
T(X;, X,)
66)
(Eedggo)))))
where I(X,, X,) is the Shannon mutual information between variables X; and X,. In other words, suffices to construct the maximal weighted spanning tree where the weight between two vertices is
5

---

Published as a conference paper at ICLR 2020
their Shannon mutual information. Chow & Wagner (1973) show that the Chow-Liu algorithm is consistent, i.c. it recovers the true solution as the dataset size goes to infinity. However, the finite sample behavior of the Chow-Liu algorithm for high dimensional problems is much less studied, due to the difficulty of estimating mutual information. In fact, we show in our experiments that the empirical performance is often poor, even with state-of-the art estimators. Additionally, methods based on mutual information cannot take advantage of intrinsically asymmetric relationships, which common for example in gene regulatory networks (Meyer et al., 2007).
To address these issues, we propose a new structure learning algorithm based on V-information instead of Shannon information. The idea is that we can associate to each directed edge in G' (i.e., each pair of variables) a suitable predictive family Vi, (cf. Def 1). The main challenge is that we cannot simply replace mutual information with V-information in Eq. 6 because V-information is asymmetric we now have to optimize over directed trees:
Σ Trssettr (X (Xi(0) + X2)
= arg max
gEGa- 1=2
where Ga-tree is the set of directed trees, and (g)) N N is the function mapping each non-root node of directed tree y to its parent, and Vi, is the predictive family for random variables X; and X,- After estimating V-informatiin construct the maximal directed spanning tree. This allows us to solve (7) exactly, even though there a combinatorially large number of trees to consider. Pseudocode is summarized in Algorithm in Appendix. Denote C'(g)= = th Vieeoo, ( + X2), we show in the following theorem that unlike the original Chow-Liu algorithm, our algorithm has guarantees in the finite samples regime, in continuous settings:
each edge, we use the Chu-Liu algorithm (Chu & Liu, 1965) to
Theorem 2. Let {X,} be the set of m random variables, Dig (resp. Dj) be the set of samples drawn from P(X,, X3) (resp. P(),)). Denote the optimal directed tree with maximum expected edge weights sum C(g) as g" and the optimal directed tree constructed on the dataset D as g. Then with the assumption in theorem for any ö (0, 2m( ), with probability at least 2m(m 1)6,
we have:
C()) 2 C(g") 2mm 1) max 1.j
2DD, (9v,.) + 29v, + BV 2 (1D,1- +
1D.
(8)
Theorem 2 shows that the total edge weights of the maximal directed spanning tree constructed by algorithm 1 would be close to the optimal total edge weights if the Rademacher term is small, Although larger C(g) does not necessarily lead better Chow-Liu trees, empirically we find that the optimal tree in the sense of equation (7) is consistent with the optimal tree in equation (6) under commonly used V.
6 EXPERIMENTAL RESULTS
6.1 STRUCTURE LEARNING WITH CONTINUOUS HIGH-DIMENSIONAL DATA
We generate synthetic data using various ground-truth tree structures g" with between 7 and 20 variables, where each variable is 10-dimensional. We use Gaussians, Exponentials, and Uniforms as ground truth edge-conditionals. We use >-infornationGGausiin and V-information(Logisteee denote Algorithm with two different V families. Please refer to Appendix D.1 for more details. We compare with the original Chow-Liu algorithm equipped with state-of-the-art mutual information estimators: CPC (van den Oord et al., 2018), NWJ (Nguyen et al., 2010) and MINE (Belghazi et al., 2018), with the same neural network architecture the V-families for fair comparison. All the experiments are repeated for 10 times. As a performance metric, we use the wrong-edges-ree ratio of edges that different from ground truth) a function of the amount of training data.
to
(the
We show two illustrative experiments in figure la; please refer to Appendix D.I for all simulations. We can that although the two V-families used are misspecified with respect to the true underlying (conditional) distributions, the estimated Chow-Liu trees are much more accurate across all data regimes, with CPC (blue) being the best alternative. Surprisingly, V-information (aaussian) works consistently well in all cases and only requires about 100 samples to recover the ground-truth Chow-Liu tree in simulation-A.

---

Published as a conference paper at ICLR 2020
Simuletion-A
Simulation-B
Simulation-C
Expected vrrong- elges-naioo
24
02
1000
2000
3000
4000
2002
1003
2000
3000
6000
2003
1000
2003
3000
4000
2003
Sample Size
Sample Size
Sample Size
MiinoorationGGussian
Cinformation((aalaccian))
(a) Chow-Liu tree Construction
stochastic dynamic deterministic dynamic
V-information
AUC
V- information
KSG
KDE
0.58
Parttioning
Mixed
0.8
12.5
Sample Size
Frame Distance
(b) Gene network inference
(c) V-information of frames
Figure (a) The expected wrong-edges-ratii algorithm with different and other mutual
information estimators- algorithms from sample size 10 to 5 x 10 (b) AUC curve for gene regulatory network inference. (c) The predictive Y-information versus frame distance.
6.2 GENE REGULATORY NETWORK INFERENCE
Mutual information between pairs of gene expressions often used to construct gene regulatory networks. We evaluate V-information et al., 2012) and use the setup of Gao et al. (2017), where 20 genes with 660 datapoints are utilized to evaluate all methods. We compare with state-of-the-art non-parametric Shannon mutual information estimators in this low dimensional setting: KDE, the traditional kernel density estimator; the KSG estimator (Kraskov al., 2004); the Mixed KSG estimator (Gao al., 2017) and Partitioning, adaptive partitioning estimator (Darbellay Vajda, 1999) implemented by Szabó (2014). For fair comparison with these low dimensional estimators, select V {f f[æ] Ng((x), 2), X; f[ø]= (n, 4 | E range(g)), where is 3-rd order polynomial.
the in-silico dataset from the DREAM5 challenge (Marbach
The task is to predict whether directed edge between genes exists in the ground gene network. We use the estimated mutual information and V-information for gene pairs as the test statistic to obtain the AUC for various methods. As shown in Figure 1b, our method outperforms all other methods in network inference under different fractions of data used for estimation. The natural information measure in this task is asymmetry since the goal is to find the pairs of genes (A,, B;)s in which A, regulates B, thus V-information is suitable for such than mutual information.
7

---

Published as a conference paper at ICLR 2020
6.3 RECOVERING THE ORDER OF VIDEO FRAMES
Let Xi...., X20 be random variables each representing a frame in videos from the Moving- -NNIS dataset, which contains 10,000 sequences each of length 20 showing two digits moving with stochastic dynamics. Can Algorithm 1 be used recover the natural (causal) order of the frames? Intuitively, predictability should be inversely related with frame distance, thus enabling structure learning. Using a conditional PixeICNN+ (Salimans al., 2017) as predictive family V, we shown in Figure Ic that predictive V-information does indeed decrease with frame distance, despite some fluctuations when the frame distances are large. Using Algorithm to construct a Chow-Liu tree, we find that the tree perfectly recovers the relative order of the frames.
We also generate Deterministic-Movin--MMii ministic dynamics. From the perspective of Shamnon mutual information, every pair of frames has the same mutual information. Hence, standard Chow-Liu tree learning algorithm would fail to discover the natural ordering of the frames (causal structure). In contrast, once we constrain the observer to PixcICNN+ models, algorithm with predictive V-information can still recover the order of different frames when the frame distances are relatively small (less than 9). Compared to the stochastic dynamics case, V-information is more irregular with increasing frame distance, since the PixeICNN+ tends to overfit.
dataset, where digits move according to deter-
6.4
INFORMATION THEORETIC APPROACHES TO FAIRNESS
The goal of fair representation learnnng is to map inputs X E X' to feature space Z Z such that the mutual information between Z and some sensitive attribute U E U (such as race or gender) is minimized. The motivation is that using Z (instead of X) input we can longer use the sensitive attributes to make decisions, thus ensuring some notion of fairness. Existing methods obtain fair representations by optimizing against "adversarial" discriminator predict from 2 (Edwards & Storkey, 2015; Louizos et al., 2015; Madras et al., 2018; Song et al., 2018). Under some assumptions on U and V, show in Appendix D.2 that these works actually use V-information minimization as part of their objective, where V depends on the functional form the discriminator.
that the discriminator cannot
However, it is clear from the V-information perspective that features trained with VA "a-information minimization might not generalize to Vg-information and vice versa. To illustrate this, we use function family V, as the attacker to extract information from features trained with Iv, l2 - U) minimization, where all the Vs are neural nets. On three datasets commonly used in the fairness literature (Adult, German, Heritage), previous methods work well at preventing information "leak" against the class of ad adversary they've been trained on, but fail when consider different ones. As shown in Figure 3b in Appendix, the diagonal elements in the matrix are usually the smallest in rows, indicating that the attacker function family V; extracts more information on featured trained with V information minimization. This challenges the generalizability of fair representations in previous works. Please refer to Appendix D.2 for details.
7 RELATED WORK
Alternative definitions of Information Several alternative definitions of mutual information are available in the literature. Renyi entropy and Renyi mutual information (Lenzi al., 2000) extend Shannon information by replacing KL divergence with f-divergences. However, they have the same difficulty when applied to high dimensional problems Shannon information.
The line of work most related to ours is the entropy and H mutual information (DeGroot et al., 1962; Grünwald et al., 2004), which associate definition of entropy every prediction loss. However, there are two key differences. First, literatures in H entropy only consider a few special types of prediction functions that serve unique theoretical purposes; for example, (Duchi et al., 2018) considers the set of all functions on a feature space to prove surrogate risk consistency, and (Grünwald et al., 2004) only considers the H entropy prove the duality between maximum entropy and worst-case loss minimization. In contrast, our definition takes a completely different perspective - emphasizing bounded computation and intuitive properties of "usable" information. Furthermore H entropy still suffers from difficulty of estimation in high dimension because the definitions do not restrict to functions with small complexity (e.g. Rademacher complexity).
8

---

Published as a conference paper at ICLR 2020
Mutual information estimation The estimation of mutual information in the machine learning field often on the continuous underlying distribution. For non non-maraettric mutual information estimators, many methods have exploited the 3H principle to calculate the mutual information, such as the Kernel density estimator (Paninski & Yajima, 2008), x-Necarst-Necighbrr estimator and the KSG estimator (Kraskov et al., 2004). However, these non-parametric estimators usually aren't t scalable to high dimension. Recently, several works utilize the variational lower bounds of MI to design MI estimator based on deep neural network in order to estimate MI of high dimension continuous random variables (Nguyen et al., 2010; van den Oord et al., 2018; Belghazi et al., 2018).
CONCLUSION
We defined and investigated V-information, a variational extension to classic mutual information that incorporates computational constraints. Unlike Shannon mutual information, V-inffommtionn attempts to capture usable information, and has very different properties, such as invalidating the data processing inequality. In addition, V-information can be provably estimated, and thus be more effective for structure learning and fair representation learning.
ACKNOWLEDGEMENTS
This research was supported by AFOSR (FA9550-19-1-0022 NSF (#1651565, #1522054, #1733686), ONR, and FLI.
REFERENCES
Peter L.. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463-482, 2001.
Roberto Battiti. Using mutual information for selecting features in supervised neural net learning. IEEE Transactions on neural networks, 5(4):537-550, 1994.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, R. Devon Hjelm, and Aaron C. Courville. Mutual information neural estimation. In ICML,, 2018.
C Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory, 14(3):462-467, 1968.
C. K. Chow and Terry J. Wagner. Consistency of an estimate of tree-dependent probability distribu- tions (corresp.). IEEE Trans. Information Theory, 19:369-371, 1973.
Yau Chu and T. Liu. On the shortest arborescence of directed graph. Scientia Sinica, 14:1396-1400. 1965.
Thomas M. Cover and Joy A. Thomas. Elements of information theory. 1991.
Georges A. Darbellay and Igor Vajda. Estimation of the information by an adaptive partitioning of the observation space. IEEE Trans. Information Theory, 45:1315-1321, 1999.
Morris H DeGroot et al. Uncertainty, information, and sequential experiments. The Annals of Mathematical Statistics, 33(2):404 1962.
John Duchi, Khashayar Khosravi, Feng Ruan, et al. Multiclass classification, information, divergence and surrogate risk. The Annals of Statistics, 46(6B):3246-3775 2018.
Harrison A Edwards and Amos J. Storkey. Censoring representations with an adversary. CoRR, abs/1511 1. 105897, 2015.
Wei Gao and Zhi-Hua Zhou. Dropout rademacher complexity of deep neural networks. Science China Information Sciences, 59(7):072104, 2016.
Weihao Gao, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath, Estimating mutual information for discrete-continuous mixtures. In NIPS, 2017.

---

Published as a conference paper at ICLR 2020
Peter D Grünwald, A Philip Dawid, et al. Game theory, maximum entropy, minimum discrepancy and robust bayesian decision theory. the Annals of Statistics, 32(4):1367-1433 1433, 2004.
Edwin T Jaynes. On the rationale of maximum-entropp methods. Proceedings of the IEEE, 70(9): 939-952, 1982.
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In NIPS, 2008.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. CoRR, abs/aa/2../11111 14, 2013.
Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information. Phys. Rev. E, 69:066138, Jun 2004, doi: 10.1 1a.110//yyReev..9..00 Pev. 1133/hh/pyssseee 69. 066138
URL https://iikk..ap
org/doi /10. 1103
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521:436-444, 2015.
Michel Ledoux and Michel Talagrand. Probability Banach Spaces: isoperimetry and processes. processses. Springer Science & Business Media, 2013.
EK Lenzi, RS Mendes, and LR Da Silva. Statistical mechanies based on renyi entropy. Physica A: Statistical Mechanics and its Applications, 280(3-4):337-445 2000.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard S. Zemel. The variational fair autoencoder. CoRR, 0tbs//511.008.. 2015.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. ArXiv, Abs//802.06309, 2018.
Daniel Marbach, James C. Costello, Robert Küffner, N. Vega, Robert J. Prill, Diogo M Camacho, Kyle R. Allison, Manolis Kellis, James J. Collins, and Gustavo Stolovitzky, Wisdom of crowds for robust gene network inference. In Nature Methods, 2012.
Patrick E. Meyer, Kevin Kontos, Frédéric Lafitte, and Gianluca Bontempi. information-theoreee inference of large transcriptional regulatory networks. In EURASIP J. Bioinformatics and Systems Biology, 2007.
XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56:5847-5861, 2010.
Liam Paninski and Masanao Yajima. Undersmoothed kernel entropy estimators. IEEE Transactions on Information Theory, 54:4384 2008.
Rafael Pass and Abhi Shelat. A course in eryptography. 2010.
Judea Pearl. Causality: Models, reasoning, and inference. 2000.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. MIT press, 2017.
Ben Poole, Sherjil Ozair, Aaron van den Oord, Alexander A Alemi, and George Tucker. On variational bounds of mutual information. arXiv preprint
2019.
Rajesh Ranganath, Sean Gerrish, and David M. Blei. Black box variational inference. In AISTATS, 2013.
Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik Kingma. Pixelcnn++: Improving the pixel- cnn with discretized logistic mixture likelihood and other modifications. ArXiv, abs/1701 055517, 2017.
Claude E. Shannon and Warren Weaver. The mathematical theory communication. 1948.
Jiaming Song and Stefano Ermon. Understanding the limitations of variational mutual information estimators. arXiv preprint 1rXvv:1910.06222, 2019.
10

---

Published as a conference paper at ICLR 2020
Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learning controllable fair representations. In AISTATS, 2018.
Zoltán Szabó. Information theoretical estimators toolbox. J. Mach. Learn. Res., 15:283-287, 2014.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27111:1133441111 1984.
Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. ArXiv, abss/800..035 0077403778. 2018.
Martin Wainwright, Michael Jordan, al. Graphical models, exponential families, and variational inference. Foundations and Trends(R) in Machine Learning, 1(1-2):1-305, 2008.

---

Published as a conference paper at ICLR 2020
A PROOFS
A.1 PROOF OF PROPOSITION 1
Proposition 1. For V-entropy and V-information, we have
1. Let Qt be as Def. Then HY(Y) is the Shannon entropy, Hn X) is the Shannon conditional entropy, and (Y 7 X) is the Shannon mutual information.
2. Let y and = {f [0) - PH μ R where P. is the distribution with density y --llo-plllz where Z = e e-llv-plla dy, then the V-entropy of random variable Y equals its mean absolute deviation, up to an additive constant.
3. Yety= EE and V {f (2) + (R, Σ) luE TUERR.. =1/2Iaxxa then the V-entropy of a random variable Y equals the trace of its covariance tr (Cov(Y)), up to an additive constant.
4. Let = + Qt,, }). where Qt is distribution in a minimal exponential family with sufficient statistics t y + R& and set of natural parameters O For random variable Y with expected sufficient statistics jy = Ett(Y)), the V-entropy of is the maximum Shannon entropy over all random variables Y with identical expected sufficient statistics, i.e. EE[(Y)] py.
5. Let y = =R, X be any vector space, and V = (f N((())) Nu, M) - 1/21axa. Φ E 4). where 4 is the set of linear functions { : X - T. then V-information Iv(X + Y) equals the (unnormalized) maximum coefficient of determination R tr (Cov(Y)) for linear regression.
X:0 +
Proof. (1)
Let Py| denote the density function of random variable Y conditioned on X = x (we denote this random variable as Y x))
Ha(Y|X) inf X JEN
log 1 inf E E JER
log
Pr)
f[x](y)
inf E (2 + H({{))
JEn
E [H({)))] H(
where infimum is achieved for where [(x] = Py la and H is the Shannon (conditional) entropy. The same proof technique be used show that HY H(Y), with the infimum achieved by where f(Ø]- = Py. Hence we have
In(Y X) Ha(Y) Ha(Y H(Y) (1111)=1((Y:3)
(10)
(2)
Hv(Y) = inf By-y (- log [v)]
inf Eyyw WERd
log 7
11 ull
JEV
inf Eysy [II 1/ [|2] log Z HER4
MAD(Y) + log Z
(11)
where MAD denotes mean absolute deviation Eyyy III y EEY] l12].
12

---

Published as a conference paper at ICLR 2020
(3)
Hy(Y)= inf Byny [- log [[0 SEV
inf Byyr MERd
-log
1
=(=-1) (w-H)
(2T) $ |
inn Ey-r (y 11)²((8 pt] + log π
MER"
2
inf Ey-y (tr ((y - (v) - 14) n,) + log n
(Cyclic property trace)
HERd
2
d
= (Cov((() + log π
(Linearity of trace)
(4) The density function of an exponential family distribution with sufficient statistics t is y H exp t(y) A())) where A() is the partition function.
Hv(Y) = inf E log [v) = inf Eyny |- log exp (0- Eyny [t(v)] - A(0))
fEV
AEe
sup (0 Eyyy [t(y)] A(0))
AE
A (ty)))((t))))
(12)
where A is the Fenchel dual of the log-partinn ong-patition function A()). Under mild conditions (Wainwright et al., 2008)
- A = ((p)) where Pp. is the maximum entropy distribution out of distributions satisfying Ey-r, [t(y) = j (Jaynes, 1982), and (-) is the Shannon entropy.
(5) Assume random variable Y E Rd, V U ((o()),)) E) E X;0 + Ni, 2) R4; Σ Laxd; & E .). Then the V-information from X to i [v(X + Y)= Hv(Y) Hv(Y
inf Eyny nER
log (2T) $ +
1
inf Ex Ex OE
loog
e
11 1 <
(2T)) + |
inf Exyyx.x neRd
[1] y [1]]
inf E Ex,y,x,Y [1 x(x) [1]
GE#
inf E Ex |I| y ((x) seo
12
tr =Cr((())
1
(Cov(Y))
tr (Cov((() R²
(13)
A.2 PROOF OF PROPOSITION 2
Proposition 2. Let Y and be any random variables on y and X, and V and U be any predictive families, then have
1. Monotonicity: IfV C u, then Hv((Y) 2 HY( 11y (X) 2 HY 1X).
2. Non-Negativity: Ix(X +
3. Independence: If X is independent Yf Iv(X + Iv + X) 0.
Proof. (1)
1
Hy(Y) inf Eyny JeV
log
inf Byny Fell
log {(0(())
Hu(Y)
(14)
f|ø] (10((1)
Xv(1IX)= inf E. fev
EryxX
log
inf E yeu
Exyx
log f(x((1)
Hu((IX) (15)
f[x((y)
13

---

Published as a conference paper at ICLR 2020
The inequalities (14) and (15) are because are taking the infimum over a larger set.
(2)
Denote Vo C V as the subset of that satisfy f[z] = f(0),, Vo X.
Hv(Y) inf B |- log [
JEV
inf Ex Ex - log f(0( (v)
(By Optional Ignorance)
SEVe
inf Ex - log of [[][x)]
SEVe
inf B - log f[x[[y)] Hy x)
JEV
Therefore
Hv(Y 2
(3)
Denote Va C V as the subset of f that satisfy f/z] = f(Ø), Ve X.
Hy(Y X)
inf Ee.g.x,yl-oogg log JEV
inf Ex Ex [[x fEV
(Independence)
2 E
inf Bywy log fl [[](w]]]]
(Jensen)
SEV
Exax
inf Byn B f[][[]]]
(Optional Ignorance)
SEVo
inf Eyny 1- log / f(2)(1)] SEVe
(No dependence on x))
Byn -- log f (2](1)) Hv inf JeV
Therefore ly(Y + X) Hlv(Y) Hy(( < 0. Combined with the Proposition 2.2 that 1v(X + Y) must be non-negative, 1v(X + Y) must 0.
A.3 PROOF OF THEOREM 1
Theorem 1. Assume vf E V,x E X, 1olo [-B,B]. B). Then for any 8 e (0,0.5).
with probability at least 1 25, we have:
2 log A
1
Y: < 4 (9v) +2B
(5)
|D]
where we define the function family Gv (z. y) log / [x) f E V}, and Ry (G) denotes the Rademacher complexity of G with sample number N.
Before proving theorem 1, we introduce two lemmas. Proofs for these Lemmas follow the same strategy as theorem 8 in Bartlett & Mendelson (2001):
Lemma 3. Let X, Y be two random variables taking values in X,Y and D denotes the set of samples drawn from the joint distribution over X x y Assume v V, E X, y E Y, log [xx](y) [ B, B). log f [. (1.), then V8 (0, 1), with probability least we
Take f arg min JEV
Σ
(D]
Z..:ED
have:
2 log 1 [D]
Hv(YIX)-
Σ
log f f(x))(e))
< (D + 2B
3
(16)
D
14

---

Published as a conference paper at ICLR 2020
Proof. We apply McDiarmid's inequality to the function & defined for any sample D by
(D)
sup fev
Bz.y |- log [x][[v]]
D Σ
log f (1))(())
(17)
Let D and D' be two samples differing by exactly one point, then since the difference of suprema does not exceed the supremum of the difference and vf VV E N. E Volog f(z((y) E -, B). have:
(D) (D')
sup feV
1
Σ
log [a]((w)) Buy [log (x]
log [ai](us) - Eny Dog / [xr
[D]
D
ED
sup feV
Σ #LDEED
log f(z;|(ui)1 |D4|
Σ
log (x:)((s))
[D]
2B
D
then by McDiarmid's inequality, for any (0,1), 1), with probability at least 6, the following holds:
log Y [D]
+ (D) ED (D] B
(18)
Then we bound the Ep (D( term:
Ep [D( Ep
sup fEV
En,y [- log [[][[v]]
[
Σ
-
log S [ara] (1:)
(19)
Ep
sup IEV
EDi
Σ
log f(a
Σ
log f(zi((u))
(20)
DD'
D
RLMEED
< EE
sup ED SEV
Σ o dLWiED
log fla11(161
log f(x)((1))
(21)
D
[
I.BiEE
< EDDD'
sup feV
log [(((((/))
log [xx(((e))
(22)
D
DD
D
ED,D'
sup JEV
(log f f11/1(4/) log loggflollll flo:((u)))
(23)
D
ED..'.o
sup
o, (log (211(1)) log flai(()))
(24)
fEV
D
P
P
<
Ep,
sup fEV
σ log f f1.))
+ EDD.
sup fEV
5 log f [x]((1))
D
(25)
ID
1
2Ep,o
sup
σ log f (3:)
(26)
SeV
(
1=1
15

---

Published as a conference paper at ICLR 2020
1 D
2E
sup gEG
aig vs vi)
(gv)
(27)
where 0,s Rademacher variables that is uniform in {-1, +1}- Inequality (22) follows from the convexity of sup, inequality (24) follows from the symmetrization argument for & norm for Radermacher random variables (Ledoux & Talagrand (2013), Section 6.1), inequality (21) follows from the convexity of x - cl. (27) follows from the definition of G and Rademacher complexity.
Finally, combining inequality (18) and (27) yields for all f E V. with probability least -
E log [()]
1 D
Σ
llog ((rs((s)))
S D) (9v) + BV
2 2
(28)
[D]
In particular, the inequality holds for f
arg min JEV
Σ
- log [xr))(v)) and f
arg min Ez, X |- log f[)] Then we have: JEV
E Ex
- log [v)
Σ
- log flvil(u)) & Hv(Y
Σ
- log (1))(11))
[D]
D
ELDEED
I..9EED
<
R
log [v)
Σ E.D
log f(xx](v))
D
Hence the bound (16) holds.
Similar bounds can be derived for Hy(Y) when we choose the domain of a to be X' = {2)
Lemma 4. Let Y be random variable taking values in y and 'D denotes the of samples drawn from the underlying distribution P(Y). Assume ff E V. E V,log f(ø](y) E [-B, B). Take
f f= =arg min
Σ
-log f [()))))) then for any d E (0, 1), with probubility at least 1 8, we
TDT
feV
IL.DEED
have:
1
2 log D
Hv(Y)
Σ - log f(0)(y))
S 2D (G B
(29)
D
MED
log 1 [D]
$ 22 + BV
(30)
where Gye = (glo(v) = log fle
Proof. The first inequality (29) can be derived similarly as Lemma 3. Since is a predictive family, hence there exits function h V + V, such that h(f) = f' and Vr X, ['[x] f[Ø].
DD
R (Gya) Ep,
sup
T log f(Ø)(1))
SEV
D
[D]
Ep,
sup
o log h (z)
D
fev
ED
sup fEV
or log f(.](v))
(31)
D
(Sv)
The inequality (31) holds because of 1(V) C V.
16

---

Published as a conference paper at ICLR 2020
Now prove theorem 1:
Theorem 1. Assume vʃ V, 2 E V log Mx)(() E [[- (-B, BJ, for any (0, 0.,),), with
probability at least 1 26, we have:
2 2
-n + Y:D) s / (Gv) 2B
[D]
Proof. Define f arg min Σ -log f(x) and fo arg Σ jEV I..IED
log f(Ø)(1s). Using
JEV
WED
the triangular inequality we have:
1x(x +) - 1x(x - YY:D)
(1v( -
Σ
- log fol
Σ
log ff (wil(())
PD]
[D]
-
BLED
ELYEED
Hv(Y) [D]
Σ
log fo (0(60((()))
Hv(YIX)
Σ K.IDEED
log ff ((zi((ss))
D
W.ED
X)
Σ
- log f(o
+ Hv(Y) D
log fa f2(2)(y6)
(32)
D
E.B.ED
IIED
For simplicity let
Drjx = Hv(Y
Σ
log ((r)
D
and
Dy Hv(Y) 1 -
Σ
log foe (1))
D
MED
With inequality (32), Lemma and Lemma 4, we have:
| [ - - + +Y:D > 49 (Gv) + 2B
2 log 1 [D]
Pr
8
2og
<
Pr
Drix Dy > (9 + 2B
(Inequality (32))
D
2 log à |D]
2log |D]
< Pr
Dyix > (9v) + B1.
v
Dr > 221 () + BV
2 log 1 D
2 log 1
< Dyix > (9v) + B
+ Pr
Dy > ( + +B/
|D]
(Union bound)
28
(Lemma 3 and Lemma 4)
Hence we have:
Pr (1ix-)) - Y:D) < (G +BB
2 log 1 [D]
2 -1-9 1-28 28
which completes the proof.
17

---

Published as a conference paper at ICLR 2020
A.4 PROOF OF COROLLARY 1.1
Corollary 1.1. Assume X' {ar E RRd,, ||r|| S k22 and y (v E Rdd, 11lll2 - k If
= V = ( [[]] = -N +,, b, 1 (c, 1). W E Rddxdda b, c E TR 11(,, b)ll s 1}
Denote M = (kg + hiny)² + log 2n, then Vo E (0, 0.5), with probability at least 26:
M
1 1/ log 1 8
1v(X + Y) 1x (X; <
/4|Di
The proof is adaptation of the proof for theorem 3 in Kakade et al. (2008).
Proof. From theorem 1 we have:
2 log à
( + YYD) s 4 (Gv) 2B
[D]
In the following (W,b)ll2 is the matrix 2-norm of (W.b) then the Rademacher term can be bounded as follows:
1
1 Wa: - -b13
R Ryp
E
sup
Ti
log
2l1:
D
W.
22T
2
PP]
|
12
1
<
E,
sup
11 - Wa: 6112
+
E,
log
D
w.b. (,b,II(W,
(1,,)
2
DD
/2x
km
2mm
(33)
The second term in RHS can be bounded follows:
27
1
1
Eg
oi log
<
E
oi log
(concavity x
D
22T
D
/2T
|D]
(log
)2
(Independence of a;s)
[D]
22T
(log
1)
)2
V2n
(34)
[D]
The first term in RHS can be bounded as follows:
DDI
1
Ep,
sup
2 11y/
Wx, - b1l2)
D
W.
DD1
Ep,
sup W. b) 1las1
Σ as (1ly:
Wx: - -113))
2|D
max; maxx/|Bull1
max; 1lva
max (2:l222
D
D
+ 2|D)
Ep.a
sup W.A.I (W, D)
(IIW 2, + 6113)
(35)
18

---

Published as a conference paper at ICLR 2020
max; 1osklluell3
max; |1 1
+ max max|| Izellay
2
V
(D]
D
max; || lelll
+
ED.
sup W,
3. (1) x3 + b11)
(36)
2/D1
max; max;/lBull
1
max; 11 11
max; |
max, 22 11
+ max
(37)
V D
D
2
M
V
The inequalities (36) and (35) follow the same proof in (34).
Hence we have:
M
R (gv) S
(38)
V
In this example, can bound the upper bound of functions g E Gy by
B
sup sc EEX.EE>. (W (Wll
log
1
Wx - -112 2 ll
V2T
1
<
sup
log
+
(11l11
I| + bl12 + + + b1l)
NEX, (.......,, (W, b)lla51
2m
2
1 kyy) M
$ log
22 2 (ke
Combining inequality (38) we arrive at the theorem.
A.5 PROOF OF THEOREM? 2
Theorem 2. Let {x be the set of m random variables, Di, (resp. Dj) be the set of samples drawn from P(X;, Xÿ) (resp. P(X,)). Denote the optimal directed tree with maximum expected edge weights sum (gg) as g" and the optimal directed tree constructed on the dataset D as 9. Then with the assumption in theorem for any 8 (0, 2m(m-1)) with probability least 2m(m 1)6,
we have:
C()) 2 C(g") 2(m max 2nD. (Gv,g) + 2Ro,(9v)) + BV 2 (1D,1-
|Di, +²)
(8)
Proof. Let Cp(g") be the estimated sum of edge weights on dataset D of the tree g", i.c.,
Clg") Ivurro (X + D)
where 1(g) N the function mapping each non-root node of directed tree y to its parent. The same notation for tree Let
c= ( 1J
[vx(
X,) ix(x, x5; DD
be the maximum absolute estimation error of single edge weight. By the definition of e we have
Vg. C(g) CD(r)l < (m 1)e, then:
C(Ø) (m 1)c 2 Co(g) 2 Co(g") C(g') (m 1)c
(39)
19

---

Published as a conference paper at ICLR 2020
From lemma and lemma 3 we have:
+ 2RDL., ( (9,, + BV 2log j (1D,) 1- |Dill (
1
Pr
> max b2
< Pr
Ji Ius (X; (X, + x2) - lu (X; + X3: > 2R,, + 29,,, + By 2 log g (1D) - + |Di -1))
< Pr
J و
Hv, 1Dyl 2YED;
Σ
- log fal0)(z)) - Hv,,
1
Σ
- log f(zz)(2z))
iDail
> 2RD, (G()) + 29i,, (9₂) + B
2 2og (1Dy) - +Dassl
3i,h (11/((3))
Pr
1
Σ
-log Sol
1 1D > 2RD, (9,) + B 2//2ogg BB/2bgg
1Dyl
2jED,
(
|Di, { =))
HH,,
Σ
log f(xi((z))
2RD. (9r,) B 2 log 1
[Dasl
m2se ED.
mm(m- -)228
(By lemma 3, 4 and union bound)
Hence
Pr 6 S max 2RD.,((S..) + (G,) + BV 2 log 3 (1D,1 + 2 m(m - 1)28
(40)
Then combining inequality (39) and (40) arrive at the result.
B ANALYSIS OF APPROXIMATE ESTIMATORS FOR SHANNON INFORMATION
We consider two approximate estimators for Shannon information. The first is the CPC (or InfoNCE in Poole et al. (2019)) estimator (Icrc) proposed by van den Oord et al. (2018):
N log
fo He)
ICPC = E
< (X)
(41)
N
N Σ fo
where the expectation over N independent samples form the joint distribution II((,
The second is the NWJ estimator (INwJ) proposed by Nguyen et al. (2010):
INwJ = E...yy-pa.. [f y)] e -E..y--p(epp()) (oot..)))
S <((;YY)
(42)
In both cases, fo is a parameterized function, and the objectives are to maximize these lower bounds parameterized by 0 to approximate mutual information. Ideally, with sufficiently flexible models and data, we would be able recover the true mutual information. However, these ideal cases does not carry over to practical scenarios.
For Icrc, van den Oord et al. (2018) show that Icrc is no larger than log N, where N is the batch size. This means that the Terc estimator will ineur large bias when T(X; Y) 2 log N. We provide proof for completeness as follows.
Proposition 3. Vfo X y + RRt
Terc & log N.
(43)
20

---

Published as a conference paper at ICLR 2020
Proof. We have:
1
(oz, Mo log
ICPC == E
(44)
N
1ド= f0 365
N
50 Vs)
N
S
E
log
R
N log N = log N
(45)
N
f0 (0, w/)
which completes the proof.
For NWJ, note that the INwJ involves term denoted as Eg (x.)p)(())p()) [efo(x.s)] /e, which could be dominated by rare data-points that have high fo values. Intuitively, this would make it a poor mutual information estimator by optimizing 0. The NWJ estimator may suffer from high variance when the estimator is optimal (Song & Ermon, 2019), this is also empirically observed in Poole et al. (2019). We provide a proof for completeness follows.
Proposition 4. Assume that fe achieves the optimum value for INWI. Then the variance of the empirical NWJ estimator satisfies Var (iwwa) c(X-)0 where
N
1 N N
iNwJ-
Σ
N
is the empirical NWJ estimator with N iidd samples {(1i, (1)))) J from pla, v) and N i.i.d. samples {(,,, 1.)) from p(z)
Proof. Let us denote p(z.)p(tn)
2(
Clearly Ep(r)p()) [zi] = 1. Then we have:
Var(z;)
Ep(x)p())
[=]] (Ep()))(s) (z])²
Ep(e)p(w)
[>]] -
p(z;, Wi) ((xx))((s)))
2
Ep(e)p(e)
p( Mi)
-Ep(r.))
(46)
p(rr) (p)))(()))
2 B
log plmlive) (CR()P(957
e ((x;))
(47)
where we use Jensen's inequality for log at the last step. From Nguyen al. (2010), have:
fo(z, log p(x,y) p(x)p(y)
(48)
for all x, Since {(x;, ys) 1 (resp. ((5,, DO)N are N datapoints independently sampled from the distribution p(æ, y) (resp. ((x)) we have
N
e1 N
Var ([NWJ) = Var
[fo(
Σ [oo
N
N
1=1
2 Var
N
1
!(x))) -
Var
Σ
21
(49)
N
N
which completes the proof.
n
21

---

Published as a conference paper at ICLR 2020
Algorithm I Construct Chow-Liu Trees with V-Information
Require: D = [x)), with each X, being a set of datapoints sampled from the underlying
distribution of random variable X₃. The set of function families (Vid)y=11s between all the nodes.
1: for = I...,, m do
2: for j= do
3:
i then
4:
Calculate the edge weight: E;-1 = Ivi,, (X, + Xzi (,I, 5: end if
6: end for
7: end for
8: Construct the fully connected graph G = (V, E), with node set V
and edge
set E = (ei-))"j=1.Hz
9: Construct the maximal directed spanning tree y on G by Chow-Liu algorithm, where mutual information is replaced by V-information.
10: return g
C
THE NEW ALGORITHM FOR CHU-LIU TREE CONSTRUCTION
See Algorithm 1ii,,(2 (X, - X5; (X,, X,)) denotes the empirical V-information.
D DETAILED EXPERIMENTS SETUP
D.1 CHU-LIU TREE CONSTRUCTION
Figure shows the Chu-Liu tree construction of Simulation- Sortulaatonn-~-Simann 1~~Simulation-6. The Simulation-A and Simulation-B B in the main body correspond to Simulation-1 and Simulation-4.
Simulation-1 ~ Simulation-3
The ground-truth Chu-Liu tree is star tree (i.e. all random variables conditionally independent
given X1). We conduct all experiments for 10 times, each time with random simulated orthogonal matrices {W:) ) J==2- Simulation-I: X1 24 10) and X₃ X1 (W,,X,, 67), (2 < < 20);
Simulation-2: X1 ~ L0, 10) and X, X, ~ W, +6)), (2 S i 20). ~ E(0.1); Simulation-
3 is mixed version:X, (0, 10), X; X1 ~ (WW 61) ( (2 s 20).
Simulation-4 Simulation-6
The ground-truth Chu-Liu tree is a tree of depth two. We conduct all experiments for 10 times, each
time with random simulated orthogonal matrices (W;) Simulation-4: X1 (1( 10). X, X1
N(W,X, 2/) 2), X; X2 ~~ N(W,X2,
4,5),
X3 ~ NVW 2/) 6, 7): X2 W&
X1 Simulation-5: X1 ~ -0, x
4,5).
X; Xa W,E(X, (i 6,7), ((01));; Simulation-6 is a mixed version: X1
4(0, 10), X; X1
+ 2,3)) X₁ X2 2 4,5), X;
X3
N(W,X, (i) = 6, 7).4 ~ 8(0.)).
D.2 FAIRNESS
We can adapt the V-information perspective to fairness. Denote the random variable that represents sensitive data and the representation as U and Z respectively. Assume U is discrete and V belongs to preditive family 1. Then we have (U) (U)) long as has softmax on the top and belongs to predictive family. In this case, minimizing Iv Z + U) equals to minimize - (Y)X). Let the joint distribution of and U be paramterized by Φ. Hence the final objective is:
min(Lv(u;2)) 2)} = min
sup E, (x [log PoloogP((o (2(2))) fEV
In Edwards & Storkey (2015); Madras et al. (2018); Louizos et (2015); Song et al. (2018), functions in y are parameterized by discriminator.
22

---

Published as a conference paper at ICLR 2020
Simulatioo--1
Simulation-22
Simulaation-3
Expeced wrong wrong-dgees-- edges-rtio
1000
2000
3850
4000
5000
1000
2000
3800 4000
5000
1000
2000
3300
4000
5003
Sample Size
Sample Size
Sample Size
Simulation-4
Simulation-S
Simulatioon66
Expected wrong elges-ntt
6.4
62
1002
2003
3000
4000
2002
1000
2003
3000
4000
2003
1000
2000
3000
4000
5002
Sample Size
Sample Size
Sample Size
Siinormatoon@Guassian))
Finfomatioo(Lapaacca)
MINE
CPC
NNJ
Figure 2:
Chu-Liu Tree Construction: The expected wrong-edges-rade of algorithm with different V and other mutual information estimators-ban -based algorithms from sample size 10 to 5 x 103.
For the Eb) elements described in the main body, please refer to figure 3b. The three datasets are: the UCI Adult dataset? which has gender as the sensitive attribute; the UCI German credit dataset² which has age the sensitive attribute and the Heritage Health dataset' which has the 18 configurations of ages and gender as the sensitive attribute.
The models in the figure are:
/1 (ELD))DD Eig dl - * I(u; u), / E IJ, where D is
VA = (f: 2 + P(4))
Σ
the training set.
VB = (f : f(z] = softmax(g(3)) where is a two-layer MLP with Relu as the activation function.
Vo [f f[ softmax(g(=))), where g is three-layer MLP with LeakyRelu as the activation function.
We further visualize special of the (VA, VB) pair in figure 3a, where the V, {f Z P(U)]{l=(u))
<1
Σ (ED Ees,,,)e -11 Ilu, u), R} explicitly makes the features
of different sensitivity attributes more evenly spread, and functions in Va is simple two layers MLP with softmax the top. The leaned features by V -i-iforrmation minimization appear more evenly spread as expected, however, the attacker functions in VB can still achieve a high AUC of 0.857.
The (i,j) elements of tables in Figure 3b stand for using function family V; to attack features trained with Vj-information minimization. The diagonal elements in the matrix are usually the smallest in rows, indicating that the attacker function family V; extracts more information on featured trained minimization.
with V
htttps//archive.ics.cii... iec..........u//////assssaaatttt
'httpss//archie.... icw..iiiiiiiiiiiiie. uci edu/ml/datasets thtps::/www.kageett wwg.geecom/////hh
23

---

Published as a conference paper at ICLR 2020
PHEEA SAE
How Ich
Me
6.678
1/
WL eated with Soafena
991
601
0. 0.6888
0.635
673
C. 0.689
0. 660
6.000
0. 607
0.987
0. 647
0.635 0.434
(a) visualization
(b) AUC of predicted sensitive attribute
Figure 3: T-SNE Visualization and AUC of predicted sensitive attribute
E MINIMALITY OF PREDICTIVE FAMILY
Define VX- = {g: X x E V. E ggg[z] = f[z]}. Similarly define Væ-PP()) = {g : Ø + Bf E V.g[ø] = f[ø]). Intuitively, Vx-P(O) (resp. Ve-p(y)) restricts the domain of functions in V to X' (resp. Ø).
Non-Negativity As we demonstrated in Proposition 2, optional-ignorance guarantees that informa- tion will be non-negative for any X and Y. Conversely, given any discrete X, Z, Va-P(y), VX-P(()) that does not satisfy optional-ignorance, there exists distribution X, Y such that Tv(X + Y) Choose ~
1 [Ø] where /* is the function that has no corresponding E <V-+P(y) that can ignore its inputs. Pick X as the uniform distribution, and note that for all g E G, there exists some measurable subset X' C X on which will produce a distribution unequal to f (2)) and therefore having higher cross entropy. The expected cross entropy expressed in Hyx-pay (Y XX) ) is thus higher
than in Hyz-r(y1 (Y), and (y(X Y) 0. Thus, the function class does satisfy optional ignorance, then the V-information could be negative.
Given any discrete X, Y, Ve Vx-P(>)) that does not satisfy optional- ignorance, there exists an independent X, Y such that ly(X + Y) > 0. Choose Y such that the distribution Py can be expressed as g|æ]] for some
Independence
X,g E VV->P(y)) but cannot be expressed by any f E Væ-P(y) Let X be the distribution with all its mass on x;; note that the cross entropy of Py with /f g[z] will be zero, and is less than that of the function /(2] (because [ and Py differs on measurable subset, the cross entropy will be positive). Thus, if the function class does not satisfy optional ignorance, then the V-information does not take value 0 when the two distributions are independent.
F LIMITATIONS AND FUTURE WORK
V-information is empirically useful, has several intuitive theoretical properties, but exhibits certain limitations. For example, Shannon information can be manipulated with certain additive algebra (e.g. H) H(X) H(Y X)). while the same does not hold true for general Y-Information. However, this could be possible we choose V to be a mathematically simple set, such as the set of polynomial time computable functions. It would be interesting find special classes of V-Information where additional theoretical development is possible.
Another interesting direction is better integration of V-Information with machine learning. The production usable information (representation learning), acquisition of usable information (active learning) and exploitation of usable information (classification and reinforcement learning) could potentially be framed in similar y-information- fruitful theories arise from these analyses.
manner. It is interesting to see whether
24


Reviews:
[{"review_id": "ryl1OrQ0KS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThe 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).\n\nContributions\ni) 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.\n\nii) PAC guarantees for estimating F-information quantities from data. A nice result that justifies some optimism about the scalability of F-information estimation.\n\niii) Modification of a tree-structure learning algorithm, and application to four types of experiments with comparisons against methods for estimating Shannon(-mutual)-information. \n\nQuality, Clarity, Novelty, Impact\nThe 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.\n\nImprovements\ni) Please add a short section of current shortcomings and caveats, especially with regard to applying the methods in practice. \n\nii) 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)?\n\niii) 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).\n\n\nMinor Comments\na) 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.\n\nb) 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.\n\nc) When choosing function classes that allow for universal function approximation, would F-information degrade to Shannon information? ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1eqrvhf5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a generalization of classical definitions of entropy and mutual information that can capture computational constraints. Intuitively, information theoretic results assume infinite computational resources, so they may not correspond to how we treat \"information\" in practice. One example is public-key encryption. An adversary that has infinite time will eventually break the code so the decrypted message conveys the same amount of information (in a classical sense) as the plaintext message. In practice, this depends on computational time. \n\nThe authors' approach is to first restrict the class of conditional probability distribution p(Y|X) to a restricted family F that satisfies certain conditions. Unfortunately, the main condition in Def 1 that the authors assume is not natural and is only added to ensure that mutual information remains positive. However, putting this aside, the subsequent definitions that general entropy, conditional entropy, and mutual information are well-motivated. \n\nThe authors, then, show that many measures of \"uncertainty\" can be viewed as \"entropies\" under this generalized definition including the Mean Absolute Deviation and the Coefficient of Determination. \n\nThe overall framework can justify practices that we commonly use in machine learning, which would be justifiable using classical information. One important example is Representation Learning, which is a post-processing of data to aid the prediction task. According to classical information theory, this post-processing shouldn't help because it cannot add more information about the label Y than what was original available in X. Under the formulation presented in this paper, postprocessing can help if we keep in mind information about Y in X are hard to extract to begin with. \n\nIn terms of practical applications, the main advantage of the new definition is that F-information can be estimated from a finite sample, simply because F is a restricted set. However, this restriction helps compared to using state-of-the-art estimators for Shannon mutual information as shown in the experiments. \n\nFinally, the literature review section is quite excellent. \n\nI find the overall approach to be quite interesting and definitely worth publishing. The only suggestion I have is that the authors include immediately after Definition 1 a concrete example that illustrates it. For example, suppose that Y is a scalar and X is a noisy estimate of Y. Suppose we restrict F to the family of Gaussian distributions. That is, with side information x, f[x](y)  = N(x, s). Without side information, f[empty](y) = N(u, s). The functions f are parameterized by u and s. \nIs this a \"predictive family\"? To make sure I understand it correctly, can you please walk me through the Eq 1 for this particular example? \n\nSome minor remarks:\n- Reference Shannon and Weaver was published in 1963, not 1948. \n- In Page 5, \"maybe not expressive\" should be \"may not be expressive\". \n \n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers unanimously accept the paper.
Decision: Accept (Talk)