Structure Learning with Side Information: Sample Complexity

Graphical models are widely used to compactly model the conditional interdependence among multiple random variables Lauritzen [1996] and Pearl [2009]. The vertices of the graph represent the random variables (RVs), while the edges encode the inter-dependence among the RVs. The complete structure of the graph is analytically captured by the joint probability distribution of the random variables. Graphical models offer effective and tractable solutions to various inferential and decision-making solutions in different domains, e.g., computer vision Won and Derin [1992], genetics Chen et al. [2013], Fang et al. [2016], Dobra et al. [2004], social networks Jacob et al. [2014], and power systems Dvijotham et al. [2017].