Abstract
This work establishes a novel connection between PAC-learning of high-dimensional graphical models with efficient counting and sampling of graph structures using the well-studied online learning framework. The problem of efficiently counting and sampling graphical structures, such as spanning trees and acyclic orientations, has been a vibrant area of research in algorithms with significant advances over the past decade. We show that this rich algorithmic foundation can be leveraged to develop new algorithms for learning high-dimensional graphical models.
We observe that if we apply the exponentially weighted average (EWA) or randomized weighted majority (RWM) algorithms (two algorithms extensively studied in the online learning literature) on a sequence of samples from an unknown distribution P with the log loss function, the average regret can bound the expected KL divergence between P and the predictions of EWA and RWM. This results in new sample complexity bounds for learning Bayes nets. Moreover, using this connection, we design the first efficient polynomial sample and time algorithm for sampling Bayes nets with a given chordal skeleton. Additionally, this approach gives a new algorithm of learning tree-structured distributions, different from the well-known Chow-Liu algorithm.
This is a joint work with Arnab Bhattacharyya, Sutanu Gayen, Philips George John and N. V. Vinodchandran, and preprint is available at https://arxiv.org/abs/2405.07914.