Distribution Learning Meets Graph Structure Sampling

Explore a groundbreaking connection between PAC-learning of high-dimensional graphical models and efficient counting and sampling of graph structures in this 27-minute talk by Sayantan Sen from the Centre for Quantum Technologies, National University of Singapore. Delivered as part of the Workshop on Local Algorithms (WoLA) at the Simons Institute, discover how the online learning framework can be leveraged to develop new algorithms for learning high-dimensional graphical models. Learn about the application of exponentially weighted average (EWA) and randomized weighted majority (RWM) algorithms to bound the expected KL divergence between an unknown distribution and algorithm predictions. Gain insights into new sample complexity bounds for learning Bayes nets, the first efficient polynomial sample and time algorithm for sampling Bayes nets with a given chordal skeleton, and a novel approach to learning tree-structured distributions. Delve into this joint work with Arnab Bhattacharyya, Sutanu Gayen, Philips George John, and N. V. Vinodchandran, bridging the gap between distribution learning and graph structure sampling.