A Caltech Library Service

Entropic Causality and Greedy Minimum Entropy Coupling

Kocaoglu, Murat and Dimakis, Alexandros G. and Vishwanath, Sriram and Hassibi, Babak (2017) Entropic Causality and Greedy Minimum Entropy Coupling. In: 2017 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscatway, NJ, pp. 1465-1469. ISBN 978-1-5090-4096-4.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We study the problem of identifying the causal relationship between two discrete random variables from observational data. We recently proposed a novel framework called entropie causality that works in a very general functional model but makes the assumption that the unobserved exogenous variable has small entropy in the true causal direction. This framework requires the solution of a minimum entropy coupling problem: Given marginal distributions of m discrete random variables, each on n states, find the joint distribution with minimum entropy, that respects the given marginals. This corresponds to minimizing a concave function of n^m variables over a convex polytope defined by nm linear constraints, called a transportation polytope. Unfortunately, it was recently shown that this minimum entropy coupling problem is NP-hard, even for 2 variables with n states. Even representing points (joint distributions) over this space can require exponential complexity (in n, m) if done naively. In our recent work we introduced an efficient greedy algorithm to find an approximate solution for this problem. In this paper we analyze this algorithm and establish two results: that our algorithm always finds a local minimum and also is within an additive approximation error from the unknown global optimum.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2017 IEEE. This research has been supported by NSF Grants CCF 1344364, 1407278, 1422549, 1618689, 1564167, ONR N000141512009 and ARO YIP W911NF-14-1-0258. The work of Babak Hassibi has been supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASA’s Jet Propulsion Laboratory through the President and Director’s Fund, and by King Abdullah University of Science and Technology.
Funding AgencyGrant Number
Office of Naval Research (ONR)N000141512009
Army Research Office (ARO)W911NF-14-1-0258
JPL President and Director's FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Record Number:CaltechAUTHORS:20170816-170538199
Persistent URL:
Official Citation:M. Koeaoglu, A. G. Dimakis, S. Vishwanath and B. Hassibi, "Entropie causality anc greedy minimum entropy coupling," 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017, pp. 1465-1469. doi: 10.1109/ISIT.2017.8006772
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80537
Deposited By: Kristin Buxton
Deposited On:17 Aug 2017 16:13
Last Modified:15 Nov 2021 19:36

Repository Staff Only: item control page