Distribution Learning Meets Graph Structure Sampling
Authors: Arnab Bhattacharyya
Sutanu Gayen
Philips George John
Sayantan Sen
N. V. Vinodchandran
Venue: NeurIPS 2025 poster ()
Keywords: Distribution learning
Bayesian networks
Chordal graphs
Online learning
Primary area: general_machine_learning
TL;DR: We develop efficient algorithms for non-uniformly sampling over directed acyclic graph structures, and use these along with results from online learning, to develop efficient algorithms for agnostically-learning Bayes nets in KL divergence.

Abstract: This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an 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. We show that this rich algorithmic foundation can be leveraged to develop new algorithms for learning high-dimensional graphical models.

We present the first efficient algorithm for (both realizable and agnostic) learning of Bayes nets with a chordal skeleton. In particular, we present an algorithm that, given integers $k,d > 0$, error parameter $\varepsilon > 0$, an undirected chordal graph $G$ on $n$ vertices, and sample access to a distribution $P^\ast$ on $[k]^n$; (1) returns a Bayes net $\widehat{P}$ with skeleton $G$ and indegree $d$, whose KL-divergence from $P^\ast$ is at most $\varepsilon$ more than the optimal KL-divergence between $P^\ast$ and any Bayes net with skeleton $G$ and indegree $d$, (2) uses $\widetilde{O}(n^3k^{d+1}/\varepsilon^2)$ samples from $P^\ast$ and runs in time $\mathrm{poly}(n,k,\varepsilon^{-1})$ for constant $d$. Prior results in this spirit were for only for trees ($d=1$, tree skeleton) via Chow-Liu, and in the realizable setting for polytrees (arbitrary $d$ but tree skeleton). Thus, our result significantly extends the state-of-the-art in learning Bayes net distributions. We also establish new results for learning tree and polytree distributions.

Distribution Learning Meets Graph Structure Sampling
Arnab Bhattacharyya
Sutanu Gayen IIT Kanpur sutanugayendgmail. com
University of Warwick
arnab. bhattacharyya@warriick ac. uk
Philips George John
Sayantan Sen
CRESCCEATE& & Dept of Computer Science National University of Singapore
Centre for Quantum Technologies National University of Singapore sayantan789@gmail com
hailips-george john@u. .
N. V. Vinodchandran University of Nebraska-l.incol vinodêcse unl edu
Abstract
This work establishes novel link between the problem of PAC-learning high- dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an 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. We show that this rich algorithmic foundation can be leveraged to develop new algorithms for learning high-dimensional graphical models.
We present the first efficient algorithm for (both realizable and agnostic) learning of Bayes nets with chordal skeleton. In particular, that, given integers k; d > O, error parameter E >> 0, an undirected chordal graph G on n vertices, and sample access distribution f* on [k]"; (1) returns a Bayes net P with skeleton G and indegree d, whose KL-divergence from P at most
present algorithm
than the optimal KL-divergence between P and any Bayes net with skeleton G and indegree d, (2) uses 1: samples from p and runs in time poly(n, k -) for constant d. Prior results in this spirit were for only for trees (d 1, tree skeleton) via Chow-Liu, and in the realizable setting for polytrees (arbitrary but tree skeleton). Thus, our result significantly extends the state-of-the-are learning Bayes net distributions. We also establish results for learning tree and polytree distributions.
Introduction
High-dimensional distributions are pivotal in contemporary machine learning, with widespread
applications across various domains such gene regulation networks [46] 16 17 40], protein
signaling networks [39 72 75), brain connectivity networks [53] 78). and psychiatric symptom
networks [13 67 82 Probabilistic graphical models provide succinct representations of high-
dimensional distributions over an exponentially large sample space such as IR" or {0, 1)". These models leverage the limited dependence between component variables, encoded by dependency graph, to describe joint probability distributions over a large set of variables a succinct and interpretable manner. Probabilistic graphical models such Bayesian networks, Ising models, and
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Gaussian graphical models are extensively utilized to model a wide range of data generation processes in practice (refer [ 79 58 and the references therein). Learning distributions represented by these graphical models is central challenge with significant theoretical and practical implications.
The present work focuses on learning an unknown Bayesian network from sample data. A Bayesian network (Bayes net) with n variables and alphabet size k is a probability distribution over [K]" defined by directed acyclic graph (DAG) G on [n]. Each node represents a random variable, which is conditionally independent of non-descendants given its parents. By Bayes rule, the distribution factorizes into n conditional probabilities. If G has in-degree at most d. requires at most nhd+1 parameters to describe the distribution, significantly reducing the descriptional complexity from ke parameters required for an arbitrary distribution.
Learning Bayesian network distributions involves two steps: structure learning (identifying the dependency graph) and parameter learning (estimating conditional probability tables). Structure learning methods fall into two categories: constraint-based which iteratively removes edges by testing for conditional independence, and score-based. which assigns scores to DAGs and frames structure recovery as an opúmization problem, often solved using heuristics like greedy hill climbing, The current work broadly fits in the framework of score-based approach. However, instead of optimizing the score directly, we use the framework of online learning to reduce the problem to sampling from a family of high- dimensional structures.
In the online learning framework, the goal is to design a forecaster that observes a sequence of examples 201), 2222), x(("), and at each time (or round) t, outputs a prediction fa, based only on ,r(1), .(t....((...)) (1--1), After predicting Pe. it observes 211), and it incurs loss E(fr, (x)) for a loss function f. The cumulative loss of the forecaster is benchmarked against that of a fixed and known set of experts. The goal of the algorithm is to minimize the regret, defined as the difference between the cumulative loss over all rounds and the loss it would incur if it were to follow the best expert. Online learning is well-established field with a wide range of applications theoretical computer science, including game theory, approximation algorithms, and complexity theory (see 42 and the references therein).
31
69 9 60)
In distribution learning, the experts are all the possible candidate Bayesian networks (up to sufficient discretization). The observations are random samples from the unknown distribution, and we set the loss function to be the negative logeliill ( z) applying the online approach to distribution learning lies ensuring computational efficiency. All the standard forecasting algorithms have running time at least linear in the number of experts. In our case, the experts are all the discretization of all candidate Bayes nets, which is exponentially many. A key insight of our work is the discovery of the close relationship between this computational challenge and the task of efficient counting and sampling of DAGs from a class of DAGs. This link allows us to transfer techniques and algorithms from the counting and sampling literature to the realm of distribution learning, leading to significant new results in learning Bayes net distributions.
log p(z). The primary obstacle in
2 Our Results
We first set up the framework of PAC-Iearning (76) for distributions; formal definitions appear in Appendix A We use KL-divergence (denoted as DKL) as the notion of similarity between probability distributions, and we will work with distributions on [k]* = (1..... k)). Let C be a class of such distributions; in our applications, C will correspond to some family of Bayes nets.
For > 0,A21 1 and two distributions P and P over [k]] we say i an (c, apprroxiaaaii for P with respect to C if (Pl) P) < A mingec DKL (PIIQ) + E. When A = 1, we simply say P is an E-approximation of P. An algorithm is said to be agnostic PAC-learner for C if for any e, 0 and access to i.i.d. samples from an input distribution |R' it outputs a distribution P which is an e-approximation for P* with probability least 1 5. If P not necessarily in C, the algorithm is called improper; otherwise, it is called proper. Also, the realizable setting corresponds to the case when the input p* is guaranteed to be in C.
It is well-known (c.g.. (12) that given a DAG G, the minimum KL divergence between P and a Bayes net over G can be written as Jp-- Eiev(ay (Xao()))())) where X ~ p*, is the mutual
'There is polylog(1/8) (1/8)) dependency here (as opposed 1/52 for the proper learner) hidden in Ö(-)

---

Chordal graph with indegree S d and known skeleton
Tree with unknown skeleton
Proper
Ö max
na 2402
nk*+1
max
na
})
Realizable
=
=
uk²
Improper
Agnostic
Proper
max
2282
nk++1
δ max
n 2282
nk-
nkdi1
n
nk?
Improper
max
max
(e
Table 1: Our results: Sample complexities for (s, 6)-PA learning (the O()) notation hides polylog factors)
information, and Jp- is constant independent of G. Hence, if C is the class of Bayes nets over DAGs of in-degree d, a natural strategy for designing agnostic learning for is the following: First approximate the mutual information between any node and any set of d other nodes up to a suitable additive error. Next, maximize the sum of mutual informations between node and parents, over all possible DAGs with in-degree d. Iterating over all possible DAG structures would then lead to an algorithm with sample complexity Ön 2 g- However, this algorithm has exponential time complexity and the sample complexity is also suboptimal compared to known lower bounds.
In this work, we give improper agnostic learning algorithm for Bayes nets with indegree d with sam- ple complexity 0(nk=+11== which is sample-optimal upto polylogarithmic factors. The algorithm is computationally inefficient. Our main contribution is the design of sample and computational- efficient algorithms for new natural classes of Bayes nets, extending the state of the art. In particular, modifying our algorithm for general bounded-indegres Bayes nets, we give computational and time efficient algorithms for learning chordal-structute algorithms are currently known only for learning tree-structured distributions (112) 30 25 and for
Bayes nets with a known skeleton. Efficient
learning polytree-structured distributions with given skeleton
(24]
An undirected graph is chordal every cycle of length four or more has a chord (an edge connecting two non-adjacent vertices in the cycle). Chordal graphs form a significantly broader class than trees and encompass several well-studied graph families, including interval graphs and k-trees. Consequently, results represent major advancement in the state of the for learning Bayesian network distributions. Beyond their structural significance, chordal graphs play a crucial role in the study of Bayesian networks particularly in causal Bayesian networks [ 188.. We describe our results next. The sample complexities of our results are summarized in Table
Learning with Known Chordal Skeleton The skeleton of a DAG refers to its underlying undirected graph. We consider Bayes nets having known chordal skeleton with bounded indegree and present an efficient algorithm for learning such distributions.
Theorem 2.1. Let G be an undirected chordal graph on n nodes, and suppose is a fixed constant. Consider the problem of agnostically learning distribution w.r.t the class of Bayes nets having skeleton G with indegree S d. There exist (i) an agnostic improper PAC-learner for this problem mixture of such Bayes nets, and
using δ (=+ _kd
samples that returns an
(ii) an agnostic proper PAC-learner using Ō net. Both algorithms have poly(n, k. 1/s, 1/8) running time.
n²
+ nk*+1
samples that returns a single Bayes
2-
=
This is the first result yielding efficient algorithms for agnostic learning Bayes nets non-tree skeletons without further distributional assumptions; see Section 4 for discussion of previous work.
For efficiently learning chordal and polytree distributions, we need to know the correct skeleton (underlying undirected graph). To the best of our knowledge, there is currently no computational hardness result regarding this. Additionally, there have been several works with the known skeleton assumption, even in the context beyond PAC distribution learning. [71] designed an FPT algorithm (in terms of total degree and treewidth) for counting the Markov Equivalence Classes with given skeleton. On the practical side, several works for Bayes net structure learning first learn a skeleton from the data and then fix the orientations (c.g., the survey [27], section 4.9. However, the
3

---

approach of first learning the skeleton and then performing the distribution learning does not have sound theoretical guarantees, since the distance measures in these two contexts are different.
well-investigated class of Bayes nets is the class of polytree distributions: whose DAGs have tree
(acyclic) skeletons. Polytrees are especially interesting because they admit fast exact inference [66]. [29] investigated the problem of learning polytree distributions in terms of the negative log- fog-likelihood cost, and showed that it is NP-hard to get 2-polytree (where indegree is - 2) whose cost is at most c times that of the optimal 2-polytree for some constant c > 1, even if we have oracle access to the true entropies (equivalently, infinite samples). Our distribution learning algorithms in contrast achieve an additive approximation in the reverse-KL KL cost. As a direct corollary of the above theorem, we have the following result for bounded indegree polytrees with known skeleton.
Corollary 2.2. Let d > O be a fixed constant and G be a given undirected tree. Consider the problem of agnostically learning a distribution w.r. the class of Bayes nets having skeleton G with indegree S d, i.e. d-polytrees with skeleton G. There exist (i) an agnostic improper PAC-leamer for this problem using Ö ( nk-11
samples that returns an fifciinntl--amplaattt mixture of such samples that returns a m
polytrees, and (ii) an agnostic proper PAC-learner using Ō single polytree. Both algorithms have poly(n, 1/e,1/11///// running time.
(
The closest related result is that of [4 who designed a PAC-learner in the realizable setting for polytrees with optima sample complexity Ö(nAa=1e log 8 8- However, their analysis crucially uses the realizability assumption, and it was left as an open question in that work to find an efficient agnostic learner for polytrees. The above corollary answers this question.
Remark 2.3. We can bound the running time of our learning algorithms for chordal-structured Bayes nets (with known skeleton) as follows: At the outset, for every node E [n] and for every choice of the S parents (i),,, we learn the conditional distribution associated with node given that choice of parents pa These are add-one conditional distributions computed from a sufficiently-large
(Ö(nk*/=) set of samples. Subsequently, the learning algorithm focuses only the combinatorial problem of learning an acyclic orientation. The running time contribution from the node-distribution learning part is (((Ak) (nn
dn²/e), where A is the maximum (undirected) degree of the skeleton. Here, (a) I ndd (for d < n)) bounds the number of all possible (node, parent-set) pairings and Ö(dnk" /E) is the time for computing a "good" add-one conditional distribution for given node and parent-set. Note that the runtime is polynomial even if both A and d are Ologn).. If d is unbounded, then the runtime can grow at an exponential (d rate. Note that, for unbounded d, an exponential dependence on the runtime and sample complexity inevitable since chordal- -sructurd indegree-(n - 1) Bayes nets with fixed skeleton (the complete graph on [m)) can capture arbitrary n n-dimensional distributions (we do not use faithfulness or similar assumptions for distribution learning).
Learning Tree-structured Distributions By tree-structured distributions (or simply, trees when the meaning is clear), we mean Bayes nets whose underlying DAG has in-degree 1. They can be cquivalently defined undirected Markov models over (undirected) trees. The celebrated work of (25] developed polynomial time algorithm for learning steustruct distributions, if the algorithm is provided the exact mutual information between each pair of variables. PAC-learning guarantees with sample complexity bounds came later [30 [2]. In particular, the highlight of these works was establishing that in the realizable setting, i.e.. when the samples are being generated by a tree-structured distribution on [Ai'". the Chow-Liu algorithm is PAC-learne with sample complexity
Ö(nk3/ /s). While the dependence on and is tight, it was left as an open question whether a better dependence on k is possible.
Our work answers this in the affirmative:
Theorem 2.4. Let C be the family of tree-structured distributions over [k] There exists an algorithm that for any 8 >> O, given sample access to a distribution Pa C returns an 6-approximation P of pe with probability at least 2/3 and uses m = Ö(nk²==1) samples and poly(m) running time. The distribution P is mixture of distributions from C and is samplable in polynomial time.
2 AAthough not stated in the corollary above, in the realizable setting, our techniques also yield sample complexity with the optimal dependence on n, ks and E.

---

Note that in contrast to Theorem 2.1 here, the algorithm does not know the true skeleton a priori. The output distribution P is a mixture of exponentially many trees but can nevertheless be sampled in polynomial time by using the matrix-tree theorem, as we explain later. We note that the dependence of k on the sample complexity is tight. This follows from [14 Theorem 13] (see also (3I), which proves that learning a Bayes net with in-degree d requires 1(nka=1) samples, and for tree Bayes nets, the in-degree being d = 1, requiring ((nk²) samples. Learning with mixtures of trees has been studied before (644 61 3 70) but in other contexts.
We also note that going beyond trees, the same approach allows us to develop polynomial sample and time algorithms for learning Bayes nets on an unknown DAG whose moralization promised to have constant vertex cover size. Here, instead of sampling using the matrix-tree theorem, we can utilize a recent result of [50) to sample such DAGs, Details appear in Appendix
Why KL divergence? We briefly discuss why learning KL divergence is relevant. The study of agnostic learning of distributions in KL divergence goes back to at least three decades ago by the works of 2 and 28 29]. The authors argued that given random samples from an unknown distribution P. minimizing the KI. divergence is the same as maximizing the log-likelihoon in expectation, due to
the following equation: DKL [1)) = (P) Ez~pllog Q(x)], where (P) is the entropy of P. KL divergence also appears in the study of density estimation such as Yang-Barron's 's construction and covering complexity (84 ()). (56) also studied the complexity of distribution learning in terms of KL divergence and gave a coding-theoreti interpretation to choosing KL divergence as the distance function. Finally, several recent works have investigated the problem of learning high- high-dimensional
distributions in this stronger KL divergence guarantee, such
[12 32
24
11 80)
3 Our Techniques
Online Learning Framework to Learning in reverse KL Given i..dd samples from distribution P we are trying to learn it. Roughly, for a random x ~ P a good approximate Bayes net P should maximize the probability P(z), or equivalently, minimize the expected log-likelln likeliiooood Egwp= log P(a) Keeping this in mind, we define the loss of any Bayes net P predicted by the algorithm to be log P(x)
for a sample x.
We follow the online learning framework. Here the algorithm A observes a set of samples x(1), "",,,..,,"" (T) ~ P over T rounds from an unknown Bayes net P The goal of the algorithm is to learn a distribution P which is close to P After observing each sample ((1), A predicts a Bayes net P, and incurs loss of log Pi(z(o) for this round. However, there is a set of experts to help A. For simplicity, we can assume each expert E E is simply one Bayes net among all possible Bayes nets. Had A stuck to any particular expert E E E, it would ineur total loss Σt log B(atrry over all the T rounds. The algorithm can change the experts in between or do some
randomized strategy for choosing the expert among E. Let P. be its prediction after round t. The regret is defined to be the difference between the loss of the algorithm and that of the best expert:
Σ log B(alu)" minnee Σ' log B(2toj)
In our setting, the expert set consists of one Bayes net per DAG from the class of DAGs under consideration (e.g., acyclic orientations of given skeleton). To associate Bayes net with DAG, we approximately learn the conditional distributions at each node using the add-one or Laplace estimator on separate set of samples. We have the guarantee that these finitely many Bayes nets form a "cover" for the class of Bayes nets we wish to learn.
We relate the regret mentioned above to the expected average of the KL. divergence over the rounds: B1J (P1 [.)]. Once we control the average KL divergence, using the convexity of KL, we can show that the mixture distribution + ΣT_ P. is also close to P* Finally, we translate the above bounds from expectation to high probability using McDiarmid's bounded difference inequality.
We use known bounds on the regret for two classic online learning algorithms: the Exponential Weighted Average (EWA) algorithm and the Randomized Weighted Majority (RWM) algorithm. EWA returns us the mixture $ ΣT= P, which improperly learns Ps in (reverse) KL. RWM returns
5

---

random Bayes net P which properly learns P in expected KL. The pseudocode for these algorithms given in Algorithm and Algorithm @
Algorithm 1: EWA-based learning for Bayes nets
Algorithm 2: RWM-based learning for
Input
= (P,....... P...T.
Bayes nets
hyperparameter 17 > 0.
Input . =
Output: Sampler for P.
hyperparameter 1) > 0.
00,0 + 1 for each i E [N].
Output: P P.W.
for 1 + 1 to T do
W1,0 f for each i E [N].
Observe sample xx(1) P
for f 1 to T do
Update W + Wi,t-1 (1 for each i E [N].
Sample i, from [N] with
Pr(i: = i)
ΣjeN *sa
5 function EWA-SAME SAMPLER)
Observe sample x(1)) P for i E [N] do
Sample --21 [7] uniformly, then
sample ~ [M] with probability
Wh, < wi Pz(x(0)))
d4% 1-1
6
DjE(N] "A
return x P..
Sample uniformly from [T].
return EWA- SWA-LAMPLER /* This is sampler for P.
return P Pa.
Efficient Learning of Restricted Classes of Bayes Nets Our learning algorithm for Bayes nets mentioned above sample-optimal but time-efficient in general since the number of experts to be maintained is of exponential size. However, we observe that for special cases of Bayes nets, we efficiently sample from the experts according to the randomized strategy of the algorithm. As remark, the idea that the computational barrier of RWM or EWA may be side-stepped by developing efficient sampling schemes was also used in recent work on fast equilibrium computation in structured games [8] and partly motivated our work.
To see the simplest example of this idea, suppose P PP1, ..... PNY } is set of distributions over [k], and let pm = P x P x ... x P be a set of product distributions over [ki". Each element of pen is indexed P. for (41 ($1...., in), so that Pi [[ P., (zz,). The size of pa* is clearly N", it is infeasible work with it directly. The RWM algorithm maintains distribution over pon so that the probability that RWM picks P. for its prediction P. at time proportional to Pi(a()))y), where 2x(5) is the observed sample time 8 and 1 >> is a parameter. Therefore:
I'' Pi(o(llyn Σr II (x(00)))
- P., (2 (z) y
Pr P.: P] = RWM
II
J=1 J=1
The crucial observation is that RWM maintains a product distribution over product distributions, and so we can sample each Ps.. from P independently.
When the underlying Bayes net is a tree, i.e. of indegree 1, we show that RWM samples a random rooted spanning arborescence from weighted complete graph. The probability to output a particular arborescence A is proportional to IL We where each w. is weight that can be explicitly computed in terms of the observed samples and the parameters of the algorithm. is well-known that the matrix- tree theorem (more precisely, Tutte's 's theorem) for counting weighted arborescences can be used for this purpose, and hence, we obtain an alternative the Chow-Liu algorithm for approximately learning tree Bayes net efficiently and sumple-optimally
Next, we generalize our algorithm to polytree-structured Bayes nets where the underlying skeleton is acyclic. Here, we are assuming that the skeleton is given, so that the goal of the algorithm is to learn an acyclic orientation of the skeleton. For simplicity, suppose the skeleton is known be the path. Given a particular orientation of the edges, we obtain particular Bayes net structure. Once the structure is fixed, the conditional probability distribution corresponding to each edge parent-<child is set according to the empirical statistics in a separate batch of samples. This will completely specify a Bayes net P, which can assign probability (()( for the sample (1) Therefore, we can also
compute the total loss E Σ log (0) Then, each structure P will be chosen proportional

---

to e Th in the RWM algorithm. In order to sample particular Bayes net among the entire class using RWM, we need to first compute the normalization constant of the RWM sampler's is distribution: Pepe Erepe-ner n- over the class P of all (discretized) path Bayes nets. A particular path Bayes net P will be chosen with probability e e- /Z by the RWM's sampler. We first show how to compute Z efficiently using dynamic programming.
We now show how to compute Z by induction on the set of vertices of the path. Suppose Zj is the normalization constant obtained by only restricting to the first j + nodes in the path. That is, Pj is the class of Bayes nets corresponding to all orientations of the undirected path on + 1 nodes, then 2 = = PEP, e e-w', where l only computes the loss based on the first j + 1 variables. For the induction, we maintain more refined information for each j. Let PJ, -- and p..- be the class of all discretized Bayes nets on j + 1 variables with a path skeleton and the last edge pointing left and right, respectively. Correspondingly, define Zj.- and ž clearly, Zj- Z₁ - j. Inductively, assume that Zj.-- and Z are already computed. We then need to compute 1,+ and Zj+1,->-
If the +++1 1-th edge orients rightward, then the parents of nodes .,....J+ ++ j+1
do not change, while the new node j+ 2 has parent j + 1. We can accommodate this new edge by simply adding the negative log of the conditional probability due to this new edge to the loss restricted to the first j + 1 variables.
We can compute Z = (Z + 7e - by computing = Σr log P(x)42
-/(")) -
If the (j + 1)-th edge orients leftward, the adjustment is slightly trickier as node j 1 will get a new parent j + 2, while the new node j + 2 has no parent. In that case, we need to first subtract out the previous sum of negative log conditional probabilities at j + 1. Let us define:
A
Σ log P(= (1)
A2
log P(= As Σ log P( (0)
(1) (0) ,
4+
Σ log P( j+1 1it2)
(0) As Σ log P(x -1
If node is not a parent of node j + 1. then node j + contributed Ag loss to Zj.- while now it contributes Ag loss to Z,-1,-. Otherwise, it contributed A loss to Zi while now it contributes A3 loss to Zj+1,t. The new node j + contributes As loss to 1,+ independent of what happens to the other variables. Summarizing:
Zj+1.- = Zz,t- e - 10 A2t + Zg,- . AAs A Ads)
It is easy see that these updates can be performed efficiently using an appropriate dynamic programming table. Once we have computed the total sum Z = Zn,- + Zn..,, sampling a structure according to the sampler's distribution can simply be done by suitably unrolling the DP table.
Figure 1: Given rooted polytree skeleton, for each node v, and for each fixed orientation of edges incident v. we maintain the total weight of all consistent orientations of the subtree rooted at v. Above, the orientations of edges incident to B and C' are fixed, This is needed when computing the weight for the subtree rooted at A, since in the first two panels, the in in-degree of C' change from I to 2, while in the second two panels, C's in- degeree does not change.
B
B
B
B
D
E
D
E
D
E
D
E
The argument described above extends to learning bounded indegree polytrees and bounded indegree chordal graphs. For polytrees, the idea is illustrated in Figure [] For chordal graphs, the algorithm first builds a clique tree decomposition and uses this structure for dynamic programming. The obvious issue with chordal graphs is that some orientations may lead to cycles, unlike the case for polytrees. However, chordal graphs enjoy certain nice property (see Lemma C.6) that allows us to independently perform weighted counting/sampling of acyclic orientations in each subtree of the clique tree.
7

---

Agnostic Learning via Maximum Likelihood Estimation An arguably more natural approach to PAC learning in KL divergence is to maximize the empirical log- ligeeiilioood (MLE) over a suitably- discretized class of distributions (e.g., see [41], Theorem 17). The Chow-Liu algorithm for tree distributions can also be viewed through this lens. Note however that, despite a long history of study, Chow-Liu is not known to attain the sample complexity bound in theorem 2.4 for learning trees in the realizable setting.
For the problem of learning polytrees and chordal-structure distributions, we can in fact adapt our algorithm to maximize likelihood and thus, get sample complexity bound which is comparable to our Theorem B.12 (up to log factors) for proper learning in KL. But it does not yield the near-optimal bounds (for constant failure probabílity) that we get for improper learning (Theorem [.I1] in the realizable case. The challenge of implementing the Maximum Likelihood (ML) algorithm over an exponential-sized class of distributions efficiency- - a naive approach would take exponential time. The dynamic programming algorithms that we develop for efficient weighted counting and sampling of DAG structures (which we use to implement EWA/ / RWM) can also be used to implement MLE efficiently for colytreecchrddal-strutttut distributions given the skeleton. We give outline of this in Appendix G
Related Works
51 gave the first sample complexity bounds for agnostic learning of Bayes net with known structure from samples in KL divergence. This work also gave an efficient algorithm for special cases such trees using the classical Chow-Liu algorithm. Subsequently, (28) gave efficient algorithm for learning an unknown Bayes net (discrete and Gaussian) on a fixed structure. This result was
improved to sample-optimal learning of fxxe-structure Bayes nets in [10 [2].
The general problem of distribution learning of Bayes networks with unknown DAG structure has remained elusive so far. It has not been shown to be NP-hard, although some related problems and specific approaches are NP-hard [2 26 55 Many of the early approaches required faithfulness,
a condition which permits learning of the Markov equivalence class, e.g. [73] 22 47). Finite sample complexity of such algorithms has also been studied, e.g. [45]. Specifically for polytrees, [68] 49]
studied recovery of the DAG for polytrees under the infinite sample regime and in the realizable setting, while 24 gave finite sample complexity for this problem. 48) studied the more general problem of learning Bayes nets, and their sufficient conditions simplified in the setting of polytrees.
notable prior work in the context of the current paper is the work by M.]. which also explores the improper learning of Bayesian networks with polynomial sample and time complexities. However, our research diverges from theirs in three critical ways: firstly, their study does not offer any proper learning algorithms; secondly. it lacks agnostic learning guarantees; and thirdly, their approach does not achieve optimal sample complexity in the realizable setting. While they do demonstrate a "graceful degradation" as inputs deviate from the hypothesis class, this does not equate to a definitive agnostic learning guarantee as provided our work. On a positive note, their research does attain polynomial sample and time complexities for learning any Bayesian network with a bounded total degree in the realizable setting. It is worth noting that our results for distributions with chordal skeleton are applicable even when the total degree unbounded, provided that the indegree remains bounded, a scenario where the findings of Abbeel, Koller, and Ng would not be applicable.
Online Learning of Structured Distributions The approach of using the online learning frame- work for distribution learning has been considered in the literature [8 83 777. These works use EWA algorithm and output the mixture distribution. However, they primarily focus on minimizing the number of samples, and are not computationally efficient in general. Since we are interested in computationally efficient learning of high -igh-dimensional distributions, their approaches do not directly translate to our context. The closest we get is the Sparsitron algorithm by Klivans and Meka ((57)) which learns an unknown Ising model from samples. However, Sparsitron is typical to Ising models where the conditional distribution at any component follows a logistic regression model which the Sparsitron algorithm learns.
Although not for distribution learning, a similar use of the multiplicative weights update method appears in Freund and Schapire's well-known AdaBoost algorithm (443 where the algorithm
"hii work studies more general notion of factor graphs.
8

---

Structure
Efficient? Agnostic? Additional assumptions
Tree
Yes
Yes
None
24
Polytree
Yes
No
Known skeleton
Bounded total degree
Yes
No
None
Bounded in in-degree
No
No
None
Tree
Yes
Yes
None
Our results Chordal skeleton,
Yes
Yes
Known skeleton
bounded in-degree
Table Comparison with existing works.
implicitly creates sequence of probability measures. Later work on the hard-core lemma, such as 7. explicitly focus on efficient sampling from the iterates of multiplicative weights update.
Robust Learning In the field of distribution learning. it commonly assumed that all samples consistently coming from an unknown distribution. However, real-world conditions often challenge this assumption, samples may become corrupted- removed substituted by samples from alternate distribution. Under such circumstances, the theoretical assurances of traditional algorithms may no longer apply. This discrepancy has spurred interest in developing robust learning algorithms capable of tolerating sample corruption. Recent years have seen notable advancements in this area, including the development of algorithms for robustly learning Bernoulli product distributions [37].
and enhancing the robustness of learning Bayes nets [20]. See 62 34 35,
52,
[59
B5
36
19 15
and the references therein for sample of current works in this area. These works primarily focus on guarantees with respect to the total variation distance.
Of particular relevance is the TV-contamination model. Here, if the distribution to be learnt is P. one gets samples from a 'contaminated distribution Q with (Pv Q) < v). Note that this is a stronger model than Huber contamination (154),, where the noise is restricted be additive, meaning that adversary adds a limited number of noisy points to set of uncontaminated samples from P.
One can interpret our results using KL-contamination model. If the distribution to be learnt is an unknown P promised to belong to a class C, the contaminated distribution Q is some distribution satisfying DKL PP contamination. Any (7, A) approximation for Q with respect to C yields a distribution P such that DKL(Q]IP) <
77. The noise is again non-additive, but the model is weaker than TV-
(A + 1)7. Therefore, we get that for Hellinger distance:
H(P,
s + VA+ 1)n S (2A (21+3)m-
Similarly, one can also bound dTv PP) O(VT) for constant A. To the best of our knowledge, the one were to directly apply the results of 20) with the assumption that (Q][ I 17. one would obtain a distribution such that (Pv P) O( /n log 1/n), worse than ours by a /log 1/1 factor which seems unavoidable using their approach (38. Moreover, their results require that be a class of balanced Bayes nets, technical condition which is not needed for our analysis [ However, we would like to note that DKL P)) can be large as compared dTv(Q, P), so this holds when DKL (Q small.
KL-contamination model has not been explicitly considered before,
Discussion
Conclusion In this work, established novel connection between distribution learning and graphical structure sampling algorithms via the framework of online learning. Leveraging this connec- tion, we designed efficient algorithms for agnostically learning bounded indegree chordal-structured distributions, with polynomial sample complexity. These algorithms only require knowledge of the
A Bayes net is said be e-balanced for if all conditional probability table values [c. 1 cl.

---

distribution's 's skeleton, without needing information on the edge directions. Since polytree- polytree-structured distributions are a subset of ahordal-structured distributions, our result also gives new results on the well-studied problem of learning polytre--trructur distributions. Interestingly, our method also leads to a new algorithm for learning vee-structured distributions, which is significantly different from the extremely well studied Chow-Liu algorithm. Finally, we also give an improper learning algorithm that, with probability 2/3, gives an (s, 3) -aproxximaaoo with respect to tree-structured distributions, which has quadratic sample complexity advantage over Chow-Liu.
Organization of the supplementary material Due to shortage of space, the rest of the paper is presented in the supplementary material. It is organized as follows. In Appendix A we present the preliminaries required for this work. Appendix[B cstablishes the connection between regret in online learning to KL divergence in the scenario of agnostic learning of distributions. It also presents several necessary techniques from online learning along with the EWA and RWM algorithms that will be used later in work. In Appendix C present results on learning chordal- structured distributions. In Appendix D we discuss our results on learning tree-structured distributions and present our alternative proper learning algorithm. In Appendix[E] we give the lower bound of learning tree-structured distributions. In Appendix F we design efficient learning algorithms for Bayes nets over graphs with bounded vertex cover. Finally, in Appendix G outline how our algorithms can be adapted to efficiently compute maximum likelihood.
6
Open Problems
Our work opens up several interesting research avenues.
An intriguing question is whether we can extend our result for chordal graphs of bounded indegree to general graphs of bounded treewidth and bounded indegree. Interestingly, [74] showed that counting the number of acyclic orientations reduces to the evaluation of the Tutte polynomial at the point (2,0), and the Tutte polynomial can be evaluated efficiently for bounded treewidth graphs 665 5 This is relevant because the weights that EWA/RWM maintain are in some sense a weighted count of the number of acyclic orientations of the skeleton. However, we did not find a deletion-contraction recurrence for these weights, and so their connection to the Tutte polynomial is unclear.
Another important follow-up direction for learning Bayes nets would be to search over Markov equivalence classes rather than DAG's. A Markov equivalence class corresponds to the set of DAGs that represent the same class of Bayes nets, and they can be represented as partially directed graphs (essential gruphs) that satisfy some special graphical properties. It would be interesting to explore the structure of essential graphs can be used to speed up weighted counting and sampling: indeed, a very recent work by (71) gives polynomial time algorithm for uniformly sampling an essential graph that is consistent with given skeleton.
What is the role of approximate sampling in the context of distribution learning? So far, in this work, we have only used exact sampling algorithms for spanning arborescences and acyclic orientations. Can Markov chain techniques be brought to good use here? Our work further motivates settling the complexity status of approximately counting the number of acyclic orientations of an undirected graph; this question is a long-standing open problem in the counting/sampling literature.
Finally, while we have restricted ourselves to learning Bayes nets here, our framework is quite general and also applies to learning other classes of distributions, such as Ising models and factor models. We leave these questions for future work.
Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their comments which improved the presentation of the paper. AB and PGJ's research were supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. SS's research is supported by the NRF Investigatorship award ANRF-NRFL10-2024 2024-000)) and CQT Young Researcher Career Development Grant (25- (2-YYRDDG-SS).
10

---

AB and SS were also supported by National Research Foundation Singapore under its NRF Fellowship Programme CEF-NRRFFAI-2011-0000 AB was additionally supported by an Amazon Research Award and Google South/Southeast Asia Research Award. SG's work is partially supported by the SERB CRG Award CRG/2022/007985. NVV's work was supported in part by NSF CCF grants 2130608 and 2342244 and UNL Grand Challenges Catalyst Competition Grant.
We would like to thank Debojyoti Dey, Ph.D, student at IIT Kanpur, for discussions regarding robust learning algorithms in high dimensions. AB would also like to thank Daniel Beaglchole for short meeting which seeded the idea for this work.
References
[1] Pieter Abbeel, Daphne Koller, and Andrew Y Ng. Learning factor graphs in polynomial time and sample complexity. Journal of Machine Learning Research, 7:1743-1788, 2006.
[2] Naoki Abe, Manfred K Warmuth, and Jun-ichi Takeuchi. Polynomial learnability of probabilistic concepts with respect the kullback-leibler divergence. In Proceedings of the Fourth Annual Workshop on Computational Learning Theory, pages 277-289, 1991.
[3] Animashree Anandkumar, Daniel J. Hsu, Furong Huang, and Sham M. Kakade. Learning mixtures of tree graphical models. In Advances in Neural Information Processing Systems, pages 1061-1069, 2012.
[4] Steen A Andersson, David Madigan, and Michael D Perlman. A characterization of markov cquivalence classes for acyclic digraphs. The Annals of Statistics, 15(2):505-541,1999
[5] Artur Andrzejak. algorithm for the tutte polynomials of graphs of bounded treewidth. Discrete mathematics, 190(1-3):39-$5 54, 1998.
[6] Sivaraman Balakrishnan, Simon Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Conference on Learning Theory, pages (69-212, 2017.
[7] Boaz Barak, Moritz Hardt, and Satyen Kale. The uniform hardcore lemma via approximate bregman projections. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithmss pages 1190-1200, 2009.
[8] Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, and Shachar Lovett. Sampling equilibria: Fast no-regret learning structured games. Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 3817-3855. SIAM, 2023.
[9] Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, MohammadTagh Hajiaghayi, Christos H Papadimitriou, and Saeed Seddighin. Optimal strategies of blotto games: Beyond convexity. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 597-616,
2019.
[10) Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S Meel, and NV Vinodchandran. Efficient distance approximation for structured digh-dimensional distributions via learning. Advances in Neural Information Processing Systems, 33:1 14699-147111 2020.
[11] Arnab Bhattacharyya, Davin Choo, Rishikesh Gajjala, Sutanu Gayen, and Yuhao Wang. Learn- ing sparse fixed-structure gaussian bayesian networks. In International Conference Artificial Intelligence and Statistics, pages 9400-9429, 2022.
[12] Arnab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent YF Tan, and NV Vinodchandran. Near- optimal learning of tree-structured distributions by chow and liu. SIAM Journal on Computing, 52(3):761-793, 2023.
[13] Lynn Boschloo, Claudia D van Borkulo, Mijke Rhemtulla, Katherine M Keyes, Denny Bors- boom, and Robert Schoevers. The network structure of symptoms of the diagnostic and statistical manual of mental disorders. PloS one, 10(9):c0136621, 2015.
11

---

[14] Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-item mechanisms without tiem-independence: Learnability via robustness. Proceedings of the 21st ACM Conference on Economics and Computation, pages 715- 2020.
[15] Clément Canonne, Samuel B Hopkins, Jerry Li, Allen Liu, and Shyam Narayanan. The full landscape of robust mean testing: Sharp separations between oblivious and adaptive contamination. In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2159-2168, 2023.
[16] Robert Castelo and Alberto Roverato. A robust procedure for gaussian graphical model search from microarray data with p larger than Journal of Machine Learning Research, 7:2621-2650, 2006.
[17] Robert Castelo and Alberto Roverato. Reverse engineering molecular regulatory networks from microarray data with qp-graphs. Journal of Computational Biology. 16(2):213-227, 2009.
[18] Olivier Catoni. The mixture approach to universal model selection. In Preprints of École Normale Supérieure, 1997.
[19] Yu Cheng and Honghao Lin. Robust learning of fixed-structure bayesian networks in nearly- linear time. In 9th International Conference Learning Representations (ICLR), 2021.
[20] Yu Cheng, Ilias Diakonikolas, Daniel Kane, and Alistair Stewart. Robust learning of fixed- structure bayesian networks. Advances in Neural Information Processing Systems, 31:10304- 10316, 2018.
[21] David Maxwell Chickering. Learning bayesian networks is no-complete. In Learning from Data Fifth International Workshop Artificial Intelligence and Statistics (AISTATS), pages 121-130, 1995.
[22] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3:507-554, 2002.
[23] Max Chickering, David Heckerman, and Chris Meek. Large-sample learning bayesian networks is np-hard. Journal of Machine Learning Research, 1:127713330, 2004.
[24] Davin Choo, Joy Qiping Yang, Arnb Bhattacharyya, and Clément L. Canonne. Learning bounded-degres polytrees with known skeleton. In International Conference on Algorithmic Learning Theory, volume 237, pages 402 443, 2024.
[25] C. K. Chow and N. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory, 14(3):462-467, 1968.
[26] Paul Dagum and Michael Luby. An optimal approximation algorithm for bayesian inference. Artificial Intelligence, 93(1): 1997.
[27] Ronan Daly, Shen Qiang, and Stuart Aitken. Learning bayesian networks: Approaches and issues. Knowledge Engineering Review, 26(2):99-127, June 2011.
[28] Sanjoy Dasgupta. The sample complexity of learning fixed-structure bayesian networks. Ma- chine Learning. 29:165-180, 1997.
[29] Sanjoy Dasgupta. Learning polytrees. In Proceedings the Fifteenth conference on Uncertainty in artificial intelligence, pages 134-141, 1999.
[30] Constantinos Daskalakis and Qinxuan Pan. Sample-optimal and efficient learning of tree ising models. In In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 133-146, 2021.
[31] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing nash equilibrium. Communications of the ACM, 52(2):89-97, 2009.
[32] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath. Testing ising models. IEEE Transactions Information Theory, (5((1):6829-63) 2019.
12

---

[33] Luc Devroye and Gábor Lugosi. Combinatorial Methods in Density Estimation. Springer New York. NY, 2001.
[34] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, pages 999-1008, 2017.
[35] Ilaas Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robustly learning gaussian: Getting optimal error, efficiently. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages
2018.
[36] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061-1073, 2018.
[37] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability, SIAM Journal on Computing, 48(2):742-864, 2019.
[38] Ilias Diakonikolas, Daniel M Kane, and Yuxin Sun, Optimal sq lower bounds for robustly learning discrete product distributions and ising models. In Conference on Learning Theory, pages 3936-3978, 2022.
[39] Richard Durbin, Sean R Eddy, Anders Krogh, and Graeme Mitchison. Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge university press, 1998.
[40] David Edwards, Gabriel CG De Abreu, and Rodrigo Labouriau. Selecting high- nigh-dimensional mixed graphical models using minimal aic or bic forests. BMC bioinformatics, 11:1-13, 2010.
[41] Jon Feldman, Ryan O'Donnell, and Rocco A. Servedio. Learning mixtures of product distribu- tions over discrete domains. SIAM Journal on Computing, 3565)1153-1154, 2008
[42] Yoav Freund and Robert E Schapire. Game theory, on-line prediction and boosting. In Proceedings of the ninth annual conference on Computational learning theory, pages 325-332, 1996.
[43] Yoav Freund and Robert E Schapire. A theision-theoretccc generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):1 19-11199111 139, 1997.
[44] Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103 1999.
[45] Nir Friedman and Zohar Yakhini. On the sample complexity of learning bayesian networks, In Proceedings of the Twelfth Annual Conference on Uncertainty in Articial Intelligence (UAI), pages 274-282, 1996.
[46] Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er. Using bayesian networks to analyze expression data. In Proceedings of the fourth annual international conference Computational molecular biology. pages 127-135, 2000.
[47] Nir Friedman, Iftach Nachman, and Dana Pe'er. Learning bayesian network structure from massive datasets: The "sparse candidate" algorithm. arXiv preprini arXiv:/301.600 2013.
[48] Ming Gao and Bryon Aragam. Efficient bayesian network structure learning via local markov boundary search. Advances in Neural Information Processing Systems, 34:4301-4313, 2021.
[49] Dan Geiger, Azaria Paz, and Judea Pearl. Learning causal trees from dependence information. In AAAI, pages 770-776, 1990.
[50] Juha Harviainen and Mikko Koivisto. Revisiting bayesian network learning with small vertex cover. In Uncertainty in Artificial Intelligence, pages 8 819-828, PMLR, 2023.
[51] Klaus-U Höffgen. Learning and robust learning of product distributions. Proceedings of the sixth annual conference Computational learning theory, pages 77-83, 1993.
13

---

[52] Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1021-1034, 2018.
[53] Shuai Huang, Jing Li, Liang Sun, Jieping Ye, Adam Fleisher, Teresa Wu, Kewei Chen, Eric Reiman, Alzheimer's Disease Neurolmaging Initiative. et al. Learning brain connectivity of alzheimer's disease by sparse inverse covariance estimation. Neurolmage, 50())935-999 949, 2010.
[54] Peter J Huber. Robust estimation of a location parameter. In Breakthroughs in statistics: Methodology and distribution, pages 492-518. Springer, 1992.
[55] David R. Karger and Nathan Srebro. Learning markov networks: maximum bounded tree-width graphs. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (SODA), pages 392-401, 2001.
[56] Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. On the learnability of discrete distributions. Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 273-282, 1994.
[57] Adam R. Klivans and Raghu Meka. Learning graphical models using multiplicative weights. In Symposium Foundations of Computer Science (FOCS), pages 343-354, 2017.
[58] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[59] Pravesh K Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1035-1046, 2018
[60] Dan Kovenock and Brian Roberson. Coalitional colonel blotto games with application to the economics of alliances. Journal of Public Economic Theory, 14(4):653-670 2012.
[61] M. Pawan Kumar and Daphne Koller. Learning a small mixture of trees. Advances in Neural Information Processing Systems, pages 1051-1059, 2009.
[62] Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665-674, 2016.
[63] Steffen L Lauritzen. Graphical models, volume 17. Clarendon Press, 1996.
[64] Marina Meila and Michael I. Jordan. Learning with mixtures of trees. Journal of Machine Learning Research, 1:1-48, 2000.
[65] Steven D Noble. Evaluating the tutte polynomial for graphs of bounded tree-width. Combina- torics, probability and computing, 7(3):077-321, 1998.
[66] Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier, 2014.
[67] Victor Peralta, Gustavo J Gil-Berrozpe, Julián Librero, Ana Sánchez- Torres, and Manuel J Cuesta. The symptom and domain structure of psychotic disorders: network analysis approach. Schizophrenia Bulletin Open, 1(1) (():sgaa0008 2020.
[68] George Rebane and Judea Pearl. The recovery of causal poly-trees from statistical data. Int. J. Approx. Reason., 2(3):341, 1988.
[69] Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. ACM SIGecom Exchanges, 15(2):45-49, 2017.
[70] Nikil Roashan Selvam, Honghua Zhang, and Guy Van den Broeck. Mixtures of all trees. In International Conference on Artificial Intelligence and Statistics, pages 1004--11558. PMLR,
2023.
14

---

[71] Vidya Sagar Sharma. A fixed-pane parameter tractable algorithm for counting markov equivalence classes with the same skeleton. In Thirtt-Eighth AAAI Conference on Artificial Intelligence. (AAAT), pages 20532-20539, 2024.
[72] Victor Spirin and Leonid A Mimy. Protein complexes and functional modules in molecular networks. Proceedings of the national Academy of sciences, 100(21):12123-12111 2003.
[73] Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 91)::22-72, 1991.
[74] Richard P Stanley. Acyclic orientations of graphs. Discrete Mathematics, 5(2):171-178; 1973.
[75] John Thomas, Naren Ramakrishnan, and Chris Mailey-Kellogg. Graphical models of residue coupling in protein families. In Proceedings of the Sth international workshop on Bioinformatics, pages 12-20, 2005.
[76] Leslie Valiant. theory of the learnable. Communications of the ACM, 1331111133-1111 1984.
[77] Dirk van der Hoeven, Nikita Zhivotovskiy, and Nicolò Cesa-Bianchi. High-probability risk bounds via sequential predictors. arXiv preprint arXiv:2308.07588, 2023.
[78] Gaël Varoquaux, Alexandre Gramfort, Ycan-Baptiste Poline, and Bertrand Thirion. Brain covariance selection: better individual functional connectivity models using population prior. In Advances in Neural Information Processing Systems, volume 23, pages 2334-2342, 2010.
[79] Martin J Wainwright, Michael Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008.
[80] Yuhao Wang, Ming Gao, Wai Ming Tai, Bryon Aragam, and Arnab Bhattacharyya. Optimal estimation of gaussian (poly) trees. In International Conference Artificial Intelligence and Statistics, pages 3619-3627. PMLR, 2024.
[81] Yihong Wu. Lecture notes on cntemattion-thhoeetie methods for high-dimensional statistics. Lecture Notes for ECE598YW (UIUC), 16:15, 2017.
[82] Shanghong Xie, Erin McDonnell, and Yuanjia Wang. Conditional gaussian graphical model for estimating personalized disease symptom networks. Statistics in medicine, 41(3):543-553, 2022.
[83] Yuhong Yang. Mixing strategies for density estimation. Annals of Statistics, pages 75-87, 2000.
[84] Yuhong Yang and Andrew Barron. cotommttion-thooretie determination of minimax rates of convergence. Annals of Statistics, pages 1564-1999, 1999.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract states some learning sample complexities (in concise form) which match the theorems, and the introduction section has the formal theorem statements, problem definitions, etc.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: It is a theoretical paper, and we give the problem statements and theorems precisely including all assumptions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer: [Yes]
Justification:
All these things are included, with complete proofs in the supplementary
appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper has no experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper has no experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//guuddeeeeedeuuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper has no experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper has no experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
18

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper has no experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics htttps://neuripgs http:///cwcp.c.cccccccicieaaceee
Answer: [Yes]
Justification: The authors have reviewed the guidelines. We use no human subjects, no datasets, and the paper is entirely theoretical in nature and only considers abstract problems (no socictal impact).
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification; The work is entirely theoretical on an abstract problem, and there is societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
19

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not propose datasets models, only algorithms.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does existing assets, except for other papers which have been properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, batasets.papersstt paperswi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets, other than the algorithms documented in the paper.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not use crowdsourrcin/hhuman subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper is entirely theoretical and does not require such approvals.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We have not used LLMs at all in obtaining the algorihmms/theoremskoherr results in the paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
22


Reviews:
[{"review_id": "1skTPGUYfI", "reviewer": "Reviewer_aMQD", "summary": "This paper gives computationally efficient on-line learning algorithms for certain families of Bayesian Networks, models with a known skeleton with a chordal graph of bounded in-degree, and trees. A computationally efficient algorithm for trees was known (indeed, the algorithm itself, by Chow and Liu, is very old) but the proposed method obtains optimal sample complexity -- the dependence on the size of the range of the random variables is improved to quadratic, rather than cubic. The method yields guarantees for agnostic improper learning of such structures. (A further extension to learning Bayes Nets with a moralization with a O(1)-size vertex cover, using another prior work for sampling, is described in an appendix.)\n\nThese results are obtained by leveraging the following simple observation: the multiplicative updates used in existing on-line learning methods can be distributed across the factors of the probabilistic model. This is essentially equivalent to running a separate learner for the conditional probability tables for each of the factors; this corresponds to a mixture of models that can be sampled by independently sampling a table for each factor.", "questions": "Do you have a deeper link between counting/sampling of graph structures and learning graphical models? (Besides the application here, and the casting of the computation of partition functions as a counting problem; I mean, is there a tight link between these problems, as the abstract and introduction seems to suggest? Where is it spelled out in the paper?)", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper has two main strengths. The first is that the underlying idea is very clean and well-suited to these kinds of probabilistic models. The second is that it indeed obtains quantitatively improved guarantees for specific problems, like learning tree-structured distributions.\n\nThe main weaknesses are first, that the approach relies on running the learner on a discretization of the conditional probability tables. Although the conditional probability tables themselves are inherently exponential in the number of assignments to the parents, and such a dependence is to be expected, the requirement to maintain parameters for the individual table values seems somewhat impractical. Second, the chordal graph learner relies on possession of a known skeleton for the DAG, and this approach doesn't address the structure learning problem that poses the more fundamental barrier to the use of probabilistic graphical models in practice. It is a theoretical improvement -- I am not aware of a method that is guaranteed to learn such structures -- but it is not clear if it makes a difference in practice.\n\nThe \"novel link\" between learning graphical models and sampling structures, described in the abstract, seems like an over-sell. The work uses sampling methods for improper learning of the models, but this is (just) an application, not the discovery of a deeper connection between the problems. (For example, the paper does not seem to establish a connection in the other direction.)", "was_revised": true, "final_justification": "My recommendation remains more or less unchanged: \n\nOn the positive side, there is still a cute theoretical idea in the maintenance of the weights node-wise that yields a polynomial time algorithm where one was previously not known. \n\nBut, on the negative side, the discussion with the authors seems to confirm the main weaknesses: (1) that the algorithm is still wildly impractical on account of the number of discretized conditional probability tables, each of which must maintain a weight per node, as well as (2) that the \"connection\" to sampling methods is, rather, just an application and (3) the paper only gives methods for fitting the local tables and edge orientations, not learning the structure.\n\nThe main idea has merit, and there is something to learn from the paper, but the weaknesses temper my enthusiasm. I am not sure about the impact. Hence, \"weak accept\".", "rebuttal": "Thank you for your review. We address your comments and questions below:\n\n**Exponential size conditional probability table:** We would like to note that while the EWA/RWM-based algorithms implemented “as is” (as described in Section B of the supplementary material) would use exponential-size tables and take exponential time, the way we implement it for trees/bounded-indegree chordal graphs via sampling does not use exponential-size tables (in the chordal graph case, if we assume that the indegree is constant). Thus, our results on learning tree and bounded-indegree chordal and polytree distributions work in polynomial time, as opposed to exponential time if we had used an exponential-size table. The computational efficiency of our algorithms is the non-trivial contribution of our paper.\n\n**Known skeleton assumption:** This is indeed a part left open by our paper (in terms of getting formal guarantees for structure learning). In practice, any structure learning method might be used, and the agnostic learning guarantee will hold with respect to the closest Bayes net (to the input distribution) having that structure. \n\n**Novel link between learning graphical models and sampling structures:** In this work, we have used the online learning and recursive graph structure sampling framework to efficiently learn tree, polytree and chordal structured distributions in KL divergence. We note in Section 3 that we can replace the online learning framework with maximum likelihood estimation (sacrificing the near-optimal sample complexities for improper learning), but even then the graph structure sampling is crucial for getting computationally-efficient algorithms. Unfortunately, we are not aware of a connection in the other direction (graph structure sampling via distribution learning), which seems unlikely in general. It is possible that given a learnt Bayes-net distribution as a density oracle, it could be used to learn the graph structure of that distribution in some non-trivial way which differs from learning the structure through samples (which is NP hard as shown in Chickering (2004)). \n\n**Reference:**\nMax Chickering, David Heckerman, and Chris Meek. Large-sample learning of bayesian networks is NP-hard. JMLR, 2004."}, {"review_id": "knC3dDIprZ", "reviewer": "Reviewer_c9e7", "summary": "This paper proposes a novel distribution learning algorithm for graphical models. The proposed method is the first to enable PAC learning of bounded indegree chordal-structured distributions using only the skeleton of the graphical model as prior information. It can also be applied to learning polytree-structured and tree-structured distributions, and is shown to outperform existing methods theoretically. The key idea behind the proposed approach is to leverage algorithms from the online learning literature, such as the Exponential Weighted Average algorithm and the Randomized Weighted Majority algorithm. By exploiting structural properties of graphical models, the method enables efficient sampling of experts within the algorithm.", "questions": "- While the proposed method relies on several assumptions—such as the distribution being a bounded indegree chordal-structured distribution and the skeleton being known—can these limitations be addressed or relaxed through extensions of the proposed framework?\n- In the context of practical applications, to what extent do the assumptions made by the proposed method (e.g., known skeleton, chordal structure) pose a barrier? Are they relatively benign, or could they significantly hinder real-world deployment?", "limitations": "The proposed method makes various assumptions about the shape and input of graphical models, limiting the problems to which it can be applied.", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "As I am not an expert in the learning theory of graphical models, I may not be able to accurately assess the validity or correctness of the authors’ claims. I have not wholly followed all the proofs provided in the appendix.\n\n# Strengths\n\n- The proposed method is innovative and elegant. It applies techniques from online learning to estimating distributions over graphical problems and suggests promising directions for future research.\n- The method is extensively analyzed from a theoretical perspective, and improvements over existing approaches are clearly demonstrated.\n\n# Weaknesses\n\n- Certain assumptions limit the applicability of the proposed method, such as the requirement that knowledge of the graphical model's skeleton and the distribution's chordal structure. \n- The paper has a complex structure, making it difficult to follow. Understanding the overall framework requires reading the appendix in detail. While key components necessary for understanding the method are deferred to the appendix, some arguably less critical content (e.g., the paragraph \"Why KL divergence?\") remains in the main text. The organization between the main body and the appendix warrants reconsideration.", "was_revised": true, "final_justification": "My concerns have been resolved. Since I had originally given a score leaning toward acceptance, I will keep the score as it is.", "rebuttal": "Thank you for your review. We address your comments and questions below:\n\n**Assumptions about the knowledge of the graphical model's skeleton and the distribution's chordal structure on the proposed method:** The general framework presented in Section B of the supplementary material does not rely on these assumptions. Of course, the weakness is that the meta-algorithms (Algorithms 3 and 4 in Section B) would take exponential time (even with good sample complexity) and are thus not useful in practice. The tree-structured distribution assumption and the known chordal skeleton assumption are used in the algorithms developed in Sections C and D (Algorithm 8 and Algorithm 7 in the supplementary material) to make the learning process computationally efficient. Note that the sample complexity as well as the computational efficiency of learning Bayes nets in this framework is tied to the indegree bound. This is because without an indegree bound or some other bound on the number of parameters, the sample complexity of learning Bayes nets would be exponential since they can represent general distributions of exponential size.\n\n**Complex structure:** Thanks for your suggestion. Unfortunately, due to space constraints in the main paper, we came up with this organization of the paper. We will make suitable changes in the final version.\n\n**Assumptions of the proposed method in the context of practical applications:** The algorithm in practice does not rely on the known skeleton assumption (of course, it is required in the analysis). Any structure learning algorithm (not necessarily with theoretical guarantees) that gives a chordal skeleton (with bounded indegree) $G_{err}$ as output (when $G$ is input) can be combined with our distribution learning algorithm to give an efficiently-samplable distribution as the output. However, the agnostic learning guarantee would only hold with respect to the set of distributions with structure $G_{err}$ rather than the true skeleton $G$. On the other hand, the chordal-structure and bounded-indegree assumptions are fundamentally required for our computationally-efficient algorithm."}, {"review_id": "OrSliBxF1m", "reviewer": "Reviewer_eruZ", "summary": "This paper tackles the PAC-learning of Bayesian network distributions by reducing the problem to online expert learning over all DAGs with a given chordal skeleton. The authors propose treating each possible DAG as an expert, aggregating them via efficient combinatorial counting of acyclic orientations. They prove that for a chordal skeleton with max indegree d, their algorithm learns a distribution within ε in KL-divergence using $$Õ(n³k^{d+1}/ε^²)$$ samples, extending classic Chow–Liu tree and polytree results.", "questions": "1. **Skeleton acquisition:** How would one obtain a correct chordal skeleton in practice? Would skeleton estimation errors undermine the guarantees?  \n2. **Unknown structure:** Can the online framework be extended to learn the skeleton itself (beyond the tree case), or is that inherently intractable?  \n3. **Causal interpretation:** Please clarify the role of “latent confounders” in this setting—does your method handle hidden-variable models, or is it purely observational?  \n4. **Empirical feasibility:** Have you attempted small-scale simulations (e.g., n≈20) to evaluate sample complexity and runtime in practice?", "limitations": "The authors do not experimentally assess limitations; a discussion of skeleton errors, runtime constants, and potential failure modes would be beneficial.", "rating": 2, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**  \n- **Novel theoretical bridge:** Clever reduction of Bayes net learning to online no-regret expert aggregation using combinatorial graph algorithms.  \n- **Generalization:** First efficient agnostic PAC learner for chordal-skeleton Bayes nets, subsuming tree and polytree cases.  \n- **Rigorous bounds:** Provable sample complexity and runtime guarantees grounded in well-established online learning theory.  \n\n**Weaknesses**  \n- **Known skeleton assumption:** Sidesteps the hardest part—structure discovery—raising questions about practical usability when the skeleton is unknown or estimated.  \n- **No experiments:** Lacks any empirical validation or simulations to gauge performance, leaving constants and scalability unclear.  \n- **Misleading framing:** Title mentions “latent confounder” and causality, but the work focuses purely on distribution learning under a known graph, which may confuse readers.", "was_revised": true, "final_justification": "This paper makes a good theoretical contribution by giving the first efficient agnostic PAC learner for bounded‐indegree chordal‐skeleton Bayes nets, extending known results for trees and polytrees. The online learning–based reduction to structure sampling is elegant and well‐proved. However, the reliance on a known skeleton, no analysis of robustness to skeleton errors, and no empirical validation limit the work’s applicability. Given these gaps, I lean towards weak reject to reject recommendation, despite appreciating the theoretical advances.", "rebuttal": "Thank you for your review. We address your comments and questions below:\n\n**Known skeleton assumption:** We can still combine our algorithm with a practical structure learning algorithm, as noted in our reply to Reviewer c9e7.  If the structure learning algorithm has theoretical guarantee that it ``exactly’’ recovers the structure, we can get a theoretical guarantee for this combined algorithm. Otherwise, this does not give the proper theoretical guarantee with respect to the true distribution. Unfortunately, to the best of our knowledge, we do not know of such an efficient structure learning algorithm with exact recovery guarantees.\n\n**Misleading framing:** We are afraid that we do not know why the reviewer makes such a comment. Our title (“Distribution Learning Meets Graph Structure Sampling”) clearly does not mention “latent confounder” or “causality”. Furthermore, we do not mention “latent confounders” anywhere in our paper, and the only place where we mention “causality” is lines 99-100 where we say that chordal graphs play a crucial role in the study of causal Bayesian networks. We stand by this statement and we do not feel it is misleading in any way.\n\n**Skeleton acquisition:** There have been existing works on practical structured learning algorithms (cite survey by Daly et al., 2011). Unfortunately, these do not often have theoretical guarantees for “exact recovery”. If we combine a structure learning algorithm with our distribution learning approach, it would give us the proper guarantee as we state in the paper (without the skeleton assumption) if the correct skeleton is output by the structure learning algorithm. If the structure learning phase outputs a wrong skeleton $G_{err}$, we can get an agnostic learning guarantee with respect to the set of distributions with that structure $G_{err}$ (not wrt the true skeleton $G$). The KL divergence (from the output distribution to the true distribution) in this case may be high, even for “structurally-close” skeletons (e.g., if the learnt skeleton $G_{err}$ is missing a single edge from $G$).\n\n**Unknown structure:** The general framework in Section B in the supplementary material does not rely on having a known skeleton, and neither does the online-learning based tree-structured distribution learning algorithm in Section D in the supplementary material. In that sense, the online learning framework can indeed be applied to efficiently learn the skeleton as well as the probabilities without knowing the skeleton in advance. But this efficient algorithm does rely on a strong combinatorics result (the generalization of the matrix-tree theorem, Lemma D.13 in the supplementary material), which applies only to rooted trees as far as we know. We do not have a general computationally-efficient algorithm that goes over all possible skeletons for polytrees/chordal graphs.\n\n**Causal interpretation:** Unfortunately, our work does not mention “latent confounders” anywhere in the main paper, as well as in the supplementary material. \n\n**Empirical feasibility:** In this work, we focused on proving sound theoretical guarantees of our results, which will continue to hold in practice. We defer the practical implementation of our results for future work.\n\n**Reference:**\n\nDaly, R, Qiang, S & Aitken, S, Learning Bayesian Networks: Approaches and Issues, Knowledge Engineering Review, 2011."}, {"review_id": "dSW2YK8em3", "reviewer": "Reviewer_exoZ", "summary": "This paper uses ideas from online learning to make progress on PAC learning of Bayes networks.\nThey present an efficient (agnostic) PAC learning algorithm when the Bayes networks has a known chordal skeleton and improve in several ways in the case where the graph is a known tree which was studied in recent work [11].", "questions": "While the high level picture is clear - I am not quite sure I see the argument but this may be due to space constraints. \nIn particular it would be good to at least hint at the body of the paper as to: \n1. Where do you use the fact that the graph is chordal? \n2. It is not clear how local estimates are sufficient to compute the probability of each particular orientation.\n3. Moreover, given that you consider potentially unbounded degree graphs, it is not clear how much data do you need in order to estimate the local weights especially as these need to be very accurate to apply randomized weighted majority.", "limitations": "The main limitation is the sparsity of the arguments provided. There is just not enough to convince that it works out.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The idea of treating different orientations as different experts is definitely attractive. \nSimilarly improving the efficiency by using conditional independence and estimate conditional probabilities from samples is very natural. \n\nOf course restricting to a known graphical structure where only the orientation is unknown is theoretically interesting but maybe hard to motivate from applications?\n\nThe ideas of the proofs are a bit too high level and I am not sure how confident I am in their correctness.", "was_revised": true, "final_justification": "This is nice theoretical progress on a hard problem. It is not clear in which case the graphical model is known but not the orientation. Finding some neat application would make the paper stronger. Similarly hinting as to how the algorithm works in the body of the paper would make it more attractive if possible.", "rebuttal": "Thank you for your review. We address your comments and questions below:\n\n**Use of the chordal property of graph:** In the chordal distribution learning algorithm (Algorithm 7 in Section C in supplementary material), we crucially use the clique tree decomposition of the skeleton of the chordal graph in the subroutine SamplingChordalDist (Algorithm 6). Moreover, the chordal structure assumption is used for the correctness proof of our algorithm (Lemma C.6) \n\n**Computing the probability of each particular orientation using local estimates:** We would like to note that we formally prove that local estimates (of the add-one distribution) are sufficient (Lemma B.4 and Lemma B.6 in Section B in supplementary material). This does rely on the tensorization properties of KL divergence etc.\n\n**Estimating the local weights:** We do formally prove the sample complexity bounds, taking the indegree as a parameter. The sample complexities are, of course, polynomial only when the indegree is a constant, but this is similar to the information-theoretic lower bounds to learn Bayesian network (Canonne et al., 2020, Appendix B), which are exponential in terms of indegree. Especially, our improper learning sample complexities for general match the lower bounds up to log-factors (for indegree $n-1$, exponential samples are required in any case since general distributions on $[k]^n$ can be represented by such Bayes nets).\n\n**Sparsity of the arguments:** Unfortunately, space constraints prevented us from including the arguments in the main paper.  We have included the complete arguments in the supplementary material.\n\n**Reference**\n\nClément L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Testing Bayesian Networks, IEEE Trans. Inf. Theory, 2020."}]

Author rebuttal:

Meta-review: This paper considers the task of learning directed graphical models with specific graphical structure. The main contribution is a method that leverages online learning to reduce learning to sampling certain high-dimensional distributions. This reduction is used to obtain improved sample complexity bounds and, in some cases, tractable computational complexity. With the exception of a single review with an unjustifiably low score, the other reviewers viewed this contribution as borderline with an inclination towards accepting the work. Given my own reading and understanding, I recommend borderline acceptance.
Decision: Accept (poster)