Timezone: »
We study the problem of discovering the simplest latent variable that can make two observed discrete variables conditionally independent. The minimum entropy required for such a latent is known as common entropy in information theory. We extend this notion to Renyi common entropy by minimizing the Renyi entropy of the latent variable. To efficiently compute common entropy, we propose an iterative algorithm that can be used to discover the trade-off between the entropy of the latent variable and the conditional mutual information of the observed variables. We show two applications of common entropy in causal inference: First, under the assumption that there are no low-entropy mediators, it can be used to distinguish direct causation from spurious correlation among almost all joint distributions on simple causal graphs with two observed variables. Second, common entropy can be used to improve constraint-based methods such as PC or FCI algorithms in the small-sample regime, where these methods are known to struggle. We propose a modification to these constraint-based methods to assess if a separating set found by these algorithms are valid using common entropy. We finally evaluate our algorithms on synthetic and real data to establish their performance.
Author Information
Murat Kocaoglu (Purdue University)
Sanjay Shakkottai (University of Texas at Austin)
Alex Dimakis (University of Texas, Austin)
Constantine Caramanis (UT Austin)
Sriram Vishwanath (University of Texas at Austin)
More from the Same Authors
-
2021 Spotlight: RL for Latent MDPs: Regret Guarantees and a Lower Bound »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2021 : Reinforcement Learning in Reward-Mixing MDPs »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2022 : Score-based Seismic Inverse Problems »
Sriram Ravula · Dimitri Voytan · Elad Liebman · Ram Tuvi · Yash Gandhi · Hamza Ghani · Alex Ardel · Mrinal Sen · Alex Dimakis -
2022 : HotProtein: A Novel Framework for Protein Thermostability Prediction and Editing »
Tianlong Chen · Chengyue Gong · Daniel Diaz · Xuxi Chen · Jordan Wells · Qiang Liu · Zhangyang Wang · Andrew Ellington · Alex Dimakis · Adam Klivans -
2022 : Learning Certifiably Robust Controllers Using Fragile Perception »
Dawei Sun · Negin Musavi · Geir Dullerud · Sanjay Shakkottai · Sayan Mitra -
2022 : Discovering the Hidden Vocabulary of DALLE-2 »
Giannis Daras · Alex Dimakis -
2022 : Multiresolution Textual Inversion »
Giannis Daras · Alex Dimakis -
2022 : Learning Certifiably Robust Controllers Using Fragile Perception »
Dawei Sun · Negin Musavi · Geir Dullerud · Sanjay Shakkottai · Sayan Mitra -
2022 Poster: Multitasking Models are Robust to Structural Failure: A Neural Model for Bilingual Cognitive Reserve »
Giannis Daras · Negin Raoof · Zoi Gkalitsiou · Alex Dimakis -
2022 Poster: Tractable Optimality in Episodic Latent MABs »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2022 Poster: Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret »
Orestis Papadigenopoulos · Constantine Caramanis · Sanjay Shakkottai -
2022 Poster: Minimax Regret for Cascading Bandits »
Daniel Vial · Sujay Sanghavi · Sanjay Shakkottai · R. Srikant -
2022 Poster: Zonotope Domains for Lagrangian Neural Network Verification »
Matt Jordan · Jonathan Hayase · Alex Dimakis · Sewoong Oh -
2022 Poster: FedAvg with Fine Tuning: Local Updates Lead to Representation Learning »
Liam Collins · Hamed Hassani · Aryan Mokhtari · Sanjay Shakkottai -
2022 Poster: Root Cause Analysis of Failures in Microservices through Causal Discovery »
Azam Ikram · Sarthak Chakraborty · Subrata Mitra · Shiv Saini · Saurabh Bagchi · Murat Kocaoglu -
2021 : Alex Dimakis Talk »
Alex Dimakis -
2021 Poster: Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators »
Zaiwei Chen · Siva Theja Maguluri · Sanjay Shakkottai · Karthikeyan Shanmugam -
2021 Poster: Inverse Problems Leveraging Pre-trained Contrastive Representations »
Sriram Ravula · Georgios Smyrnis · Matt Jordan · Alex Dimakis -
2021 Poster: RL for Latent MDPs: Regret Guarantees and a Lower Bound »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2021 Poster: Robust Compressed Sensing MRI with Deep Generative Priors »
Ajil Jalal · Marius Arvinte · Giannis Daras · Eric Price · Alex Dimakis · Jon Tamir -
2021 Poster: Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits »
Orestis Papadigenopoulos · Constantine Caramanis -
2021 Poster: Reinforcement Learning in Reward-Mixing MDPs »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2020 Poster: SMYRF - Efficient Attention using Asymmetric Clustering »
Giannis Daras · Nikita Kitaev · Augustus Odena · Alex Dimakis -
2020 Poster: Active Structure Learning of Causal DAGs via Directed Clique Trees »
Chandler Squires · Sara Magliacane · Kristjan Greenewald · Dmitriy Katz · Murat Kocaoglu · Karthikeyan Shanmugam -
2020 Poster: Task-Robust Model-Agnostic Meta-Learning »
Liam Collins · Aryan Mokhtari · Sanjay Shakkottai -
2020 Poster: Causal Discovery from Soft Interventions with Unknown Targets: Characterization and Learning »
Amin Jaber · Murat Kocaoglu · Karthikeyan Shanmugam · Elias Bareinboim -
2020 Poster: Second Order Optimality in Decentralized Non-Convex Optimization via Perturbed Gradient Tracking »
Isidoros Tziotis · Constantine Caramanis · Aryan Mokhtari -
2020 Poster: Mix and Match: An Optimistic Tree-Search Approach for Learning Models from Mixture Distributions »
Matthew Faw · Rajat Sen · Karthikeyan Shanmugam · Constantine Caramanis · Sanjay Shakkottai -
2020 Poster: Entropic Causal Inference: Identifiability and Finite Sample Results »
Spencer Compton · Murat Kocaoglu · Kristjan Greenewald · Dmitriy Katz -
2020 Poster: Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes »
Zaiwei Chen · Siva Theja Maguluri · Sanjay Shakkottai · Karthikeyan Shanmugam -
2020 Poster: Exactly Computing the Local Lipschitz Constant of ReLU Networks »
Matt Jordan · Alex Dimakis -
2020 Poster: Robust compressed sensing using generative models »
Ajil Jalal · Liu Liu · Alex Dimakis · Constantine Caramanis -
2019 : Opening Remarks »
Reinhard Heckel · Paul Hand · Alex Dimakis · Joan Bruna · Deanna Needell · Richard Baraniuk -
2019 Workshop: Information Theory and Machine Learning »
Shengjia Zhao · Jiaming Song · Yanjun Han · Kristy Choi · Pratyusha Kalluri · Ben Poole · Alex Dimakis · Jiantao Jiao · Tsachy Weissman · Stefano Ermon -
2019 Workshop: Solving inverse problems with deep networks: New architectures, theoretical foundations, and applications »
Reinhard Heckel · Paul Hand · Richard Baraniuk · Joan Bruna · Alex Dimakis · Deanna Needell -
2019 Poster: Inverting Deep Generative models, One layer at a time »
Qi Lei · Ajil Jalal · Inderjit Dhillon · Alex Dimakis -
2019 Poster: Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes »
Matt Jordan · Justin Lewis · Alex Dimakis -
2019 Poster: Primal-Dual Block Generalized Frank-Wolfe »
Qi Lei · JIACHENG ZHUO · Constantine Caramanis · Inderjit Dhillon · Alex Dimakis -
2019 Poster: Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models »
Shanshan Wu · Sujay Sanghavi · Alex Dimakis -
2019 Spotlight: Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models »
Shanshan Wu · Sujay Sanghavi · Alex Dimakis -
2019 Poster: Blocking Bandits »
Soumya Basu · Rajat Sen · Sujay Sanghavi · Sanjay Shakkottai -
2019 Poster: Learning Distributions Generated by One-Layer ReLU Networks »
Shanshan Wu · Alex Dimakis · Sujay Sanghavi -
2018 Poster: Experimental Design for Cost-Aware Learning of Causal Graphs »
Erik Lindgren · Murat Kocaoglu · Alex Dimakis · Sriram Vishwanath -
2017 Workshop: NIPS Highlights (MLTrain), Learn How to code a paper with state of the art frameworks »
Alex Dimakis · Nikolaos Vasiloglou · Guy Van den Broeck · Alexander Ihler · Assaf Araki -
2017 Poster: Streaming Weak Submodularity: Interpreting Neural Networks on the Fly »
Ethan Elenberg · Alex Dimakis · Moran Feldman · Amin Karbasi -
2017 Oral: Streaming Weak Submodularity: Interpreting Neural Networks on the Fly »
Ethan Elenberg · Alex Dimakis · Moran Feldman · Amin Karbasi -
2017 Poster: Model-Powered Conditional Independence Test »
Rajat Sen · Ananda Theertha Suresh · Karthikeyan Shanmugam · Alex Dimakis · Sanjay Shakkottai -
2016 Poster: Leveraging Sparsity for Efficient Submodular Data Summarization »
Erik Lindgren · Shanshan Wu · Alex Dimakis -
2016 Poster: Single Pass PCA of Matrix Products »
Shanshan Wu · Srinadh Bhojanapalli · Sujay Sanghavi · Alex Dimakis -
2016 Poster: Fast Algorithms for Robust PCA via Gradient Descent »
Xinyang Yi · Dohyung Park · Yudong Chen · Constantine Caramanis -
2016 Poster: More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning »
Xinyang Yi · Zhaoran Wang · Zhuoran Yang · Constantine Caramanis · Han Liu -
2016 Poster: Regret of Queueing Bandits »
Subhashini Krishnasamy · Rajat Sen · Ramesh Johari · Sanjay Shakkottai -
2015 Poster: Orthogonal NMF through Subspace Exploration »
Megasthenis Asteris · Dimitris Papailiopoulos · Alex Dimakis -
2015 Poster: Optimal Linear Estimation under Unknown Nonlinear Transform »
Xinyang Yi · Zhaoran Wang · Constantine Caramanis · Han Liu -
2015 Poster: Sparse PCA via Bipartite Matchings »
Megasthenis Asteris · Dimitris Papailiopoulos · Anastasios Kyrillidis · Alex Dimakis -
2015 Poster: Learning Causal Graphs with Small Interventions »
Karthikeyan Shanmugam · Murat Kocaoglu · Alex Dimakis · Sriram Vishwanath -
2015 Poster: Regularized EM Algorithms: A Unified Framework and Statistical Guarantees »
Xinyang Yi · Constantine Caramanis -
2014 Poster: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alex Dimakis · Adam Klivans -
2014 Poster: On the Information Theoretic Limits of Learning Ising Models »
Rashish Tandon · Karthikeyan Shanmugam · Pradeep Ravikumar · Alex Dimakis -
2014 Oral: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alex Dimakis · Adam Klivans -
2014 Poster: Greedy Subspace Clustering »
Dohyung Park · Constantine Caramanis · Sujay Sanghavi -
2013 Poster: Memory Limited, Streaming PCA »
Ioannis Mitliagkas · Constantine Caramanis · Prateek Jain