Learning Large Graphs from Compressed and Subsampled Data

Many machine learning and statistical inference tasks involve estimating graphical representations of correlations or dependencies in data. However, in various naturally arising scenarios, it can be expensive or impossible to obtain joint measurements of all the involved variables. For example, collecting simultaneous measurements from a large network of sensors may require a prohibitive level of communication and coordination and building a protein-protein interaction network may need a prohibitive number of pairwise correlation tests. In this talk, I will describe a new research agenda motivated by this important consideration, focusing in particular on two approaches that instantiate it.
In the first part, I will describe a framework for learning covariance (or, dependence) graphs from compressed data. Specifically, I will outline a procedure for learning the covariance structure by first grouping the underlying variables and measuring interactions (or correlations) at this grouped level. By drawing connections between high-dimensional convex geometry and novel combinatorial properties of certain random graphs, we will see that this procedure is computationally efficient and statistically consistent while requiring a considerably fewer number of pairwise correlations. I will also talk about a recently discovered compression-statistics tradeoff in this context.
In the second part, I will describe a new framework for learning a graphical model (or, a conditional dependence graph) by sequentially and interactively subsampling the underlying system. The algorithms proposed adapt to the structure of the unknown graph and focus attention on its denser regions. Both theory and experiments show that such algorithms significantly outperform their classical counterparts in terms of the total measurement resources needed.
Gautam Dasarathy is a Postdoctoral Fellow in the Electrical and Computer Engineering department at Rice University where he works with Rich Baraniuk. Before this, he spent two great years at the Machine Learning Department at Carnegie Mellon University working with Aarti Singh. He received his Ph.D. in Electrical Engineering from the University of Wisconsin – Madison, where he was advised by Dr. Robert Nowak and Dr. Stark Draper. His research interests include topics in machine learning, signal processing, statistics, and information theory. In particular, he is interested in understanding how to model, learn, and leverage interactions in large complex systems.
Gautam is co-organizing a workshop in NIPS 2017 titled "Advances in Modeling and Learning Interactions from Complex Data" which has a stellar list of confirmed speakers. Please consider sending your best work! https://sites.google.com/view/nips2017interactions/