Learning Ill-Conditioned Gaussian Graphical Models

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=WScAfQhOZNw


Duration: 0:00
509 views
0

Raghu Meka (UCLA)
https://simons.berkeley.edu/talks/tbd-395
Algorithmic Aspects of Causal Inference

Gaussian Graphical models have wide-ranging applications in machine learning and the natural and social sciences where they are one of the most popular ways to model statistical relationships between observed variables. In most of the settings in which they are applied, the number of observed samples is much smaller than the dimension and the goal is to learn the model assuming the underlying model is sparse. While there are a variety of algorithms (e.g. Graphical Lasso, CLIME) that provably recover the graph structure with a logarithmic number of samples, they assume various conditions that require the precision matrix to be in some sense well-conditioned.

I will talk about the first fixed polynomial-time algorithms for learning attractive GGMs and walk-summable GGMs with a logarithmic number of samples without any such assumptions. In particular, our algorithms can tolerate strong dependencies among the variables. We complement our results with experiments showing that many existing algorithms fail even in some simple settings where there are long dependency chains.

Joint work with Jonathan Kelner, Frederick Koehler, Ankur Moitra.



Other Videos By Simons Institute for the Theory of Computing


2022-03-23A Multi-Group Approach To Algorithmic Fairness
2022-03-23Causalsim: Trace-Driven Simulation For Network Protocols
2022-03-23Stability Of Causal Identification From The Perspective Of Condition Numbers
2022-03-23Confounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement Learning
2022-03-23Identifying Mixtures Of Bayesian Network Distributions
2022-03-23Identifying Mixture Models
2022-03-22Efficient Distance Estimation And Causal Inference For Discrete Models
2022-03-22Parameter Estimation For Undirected Graphical Models With Hard Constraints
2022-03-22Causal Matrix Completion
2022-03-22Preconditioning In Sparse Linear Regression Using Graphical Structure
2022-03-22Learning Ill-Conditioned Gaussian Graphical Models
2022-03-22Learning Restricted Boltzman Machines
2022-03-22Neural Networks And Spurious Correlations
2022-03-21Tractable Probabilistic Circuits
2022-03-11The Impact of National Service on Beliefs, Mindsets, and Life Pathways...
2022-03-10Monitoring People and Their Vital Signs Using Radio Signals and Machine Learning
2022-03-08Causality and Autoencoders in Light of Drug Repurposing for COVID-19
2022-03-05Thinking Like a Journalist — Science Communicator in Residence Talk
2022-02-26Adversarial Machine Learning and Instrumental Variables for Flexible Causal Modeling
2022-02-26Online Adversarial Multicalibration And (Multi)Calibeating
2022-02-26Rebel: Combining Deep Reinforcement Learning and Search for Imperfect-Information Games