Learning Gaussian DAG Models without Condition Number Bounds

Constantinos Daskalakis, Vardis Kandiros, Rui Yao · 2025

Read Learning Gaussian DAG Models without Condition Number Bounds by Constantinos Daskalakis, Vardis Kandiros, Rui Yao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06164.txt.

Introduction

Constantinos Daskalakis, Vardis Kandiros, and Rui Yao study how many samples it takes to learn the wiring of a Gaussian directed graph model. Under an equal-variance assumption, earlier methods already used few samples. Their hidden cost was dependence on the covariance matrix's condition number, a measure that can grow large and ruin the sample counts.

The authors give an algorithm whose sample needs do not depend on that condition number at all. Matching lower bounds show their count is nearly the true cost of the problem. With one extra bounded-variance assumption, they also obtain a polynomial-time version, and simulations on synthetic data confirm the predicted behavior.

Catalog record

CREATORConstantinos Daskalakis, Vardis Kandiros, Rui Yao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE117 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06164

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Gaussian DAG Models without Condition Number Bounds Constantinos Daskalakis, Vardis Kandiros, Rui Yao Abstract We study the problem of learning the topology of a directed Gaussian Graphical Model under the equal-variance assumption, where the graph has n n nodes and maximum in-degree d d . Prior work has established that O ⁡ ( d ​ log ⁡ n ) O(d\log n) samples are sufficient for this task. However, an important factor that is often overlooked in these analyses is the dependence on the condition number of the covariance matrix of the model. Indeed, all algorithms from prior work require a number of samples that grows polynomially with this condition number. In many cases this is unsatisfactory, since the condition number could grow polynomially with n n , rendering these prior approaches impractical in high-dimensional settings. In this work, we provide an algorithm that recovers the underlying graph and prove that the number of samples required is independent of the condition number. Furthermore, we establish lower bounds that nearly match the upper bound up to a d d -factor, thus providing an almost tight characterization of the true sample complexity of the problem. Moreover, under a further assumption that all the variances of the variables are bounded, we design a polynomial-time algorithm that recovers the underlying graph, at the cost of an additional polynomial dependence of the sample complexity on d d . We complement our theoretical findings with simulations on synthetic datasets that confirm our predictions. 1 Introduction and Background A common problem that arises in many scientific disciplines is inferring the underlying dependency structure of a vector of observations [ 12 ] . In particular, this is one of the fundamental goals of causal inference, where the emphasis is on discovering cause-and-effect relationships between variables. Perhaps the most popular way of approaching this problem is through the formalization of Directed Acyclic Graph (DAG) models, or Bayesian Networks , where variables are sampled sequentially, with the order induced by a DAG G [ 28 , 47 ] . These models have been widely adopted in the social sciences, starting from their introduction in the seminal work [ 33 ] . They have also found applicability in fields as diverse as human geography [ 30 , 2 ] , the environment [ 21 ] , and ecology [ 4 ] . The problem of determining G from observations of the variables is referred to in the literature as causal structure learning . In the general case, some popular approaches for solving this problem include the PC algorithm [ 40 ] and Greedy Equivalence Search (GES) [ 10 ] . However, these often require strict assumptions, such as strong faithfulness [ 43 ] , or encounter computational issues. Indeed, in general, the problem of recovering the true Bayesian Network is NP-hard [ 8 ] . The problem becomes more structured using the formalization of Structural Equation Models (SEMs), where each variable is equal to a function of its parents with some added independent noise. Identifiability for these models has been established when the functions are sufficiently non-linear or when the noise is non-Gaussian [ 35 , 38 ] . For linear Gaussian SEMs, which is the focus of this work, finding the graph in general is impossible. Identifiability was established in [ 34 ] , under the additional assumption that all \varepsilon_{i} have the same variance ( equal variances assumption ). A subsequent flurry of works [ 19 , 18 , 20 , 7 , 15 , 16 ] established upper and lower bounds on the number of samples needed ( sample complexity ) for inferring the graph in the high dimensional sparse setting where the maximum in-degree of any node is bounded by d and the number of nodes n>>d . Often, the goal in these works is to obtain sample complexity that scales as O(d\log n) . However, an important factor that is often overlooked in prior work is the role of the condition number \kappa of the covariance matrix of observations. Indeed, all previous analyses typically assume some type of condition that implies a bound on \kappa , independent of n . However, in many interesting examples and simple examples, \kappa scales polynomially with the number of nodes n . This would imply that all algorithms in prior work require \mathrm{poly}(n) samples, which is problematic in high-dimensional settings. For example, in the directed path graph or the tree graph, \kappa grows polynomially with n , but the structure can clearly be identified easily using O(\log n) samples. Thus, a natural question that arises is whether it is even information theoretically possible to design an algorithm that is truly high-dimensional, with a sample complexity independent of the condition number. In this work, we answer this question in the affirmative. In particular, we design and analyze an algorithm that achieves graph recovery with sample complexity independent of the condition number while at the same time retaining the optimal O(d\log n) scaling. We identify a key quantity \tau(G) of the graph (see ( 2 )) that determines this sample complexity, which is always upper bounded by the condition number \kappa . Furthermore, we provide a lower bound for the sample complexity of any algorithm, which also contains \tau and matches our upper bound up to a single factor of d (this d -factor discrepancy of the upper and lower bound is a known limitation of all prior lower bound approaches for Markov Random Fields [ 49 , 32 , 25 ] ). Thus, we obtain an almost tight characterization of the optimal sample complexity of the problem. Another natural question is whether we can design an efficient algorithm that solves the problem without condition number assumptions. To this end, we provide such an algorithm, which works under the natural assumption that the maximum variance of a node is bounded by a constant. We also show that this is a strictly weaker assumption than the boundedness of the condition number. In terms of techniques, the problem of learning a DAG is information-theoretically different in nature from that of learning undirected graphical models due to the combinatorial nature involved in finding the right topological ordering of the nodes. Despite that, our approach brings together a variety of tools from the literature on learning directed as well as undirected graphical models. We hope this serves as an inspiration for further fruitful investigations that would uncover connections between the two problems. The rest of the paper is organized as follows. Section 1.1 discusses prior work related to the problem, and Section 1.2 contains some preliminary definitions and facts about the model. The main Algorithm that achieves information-theoretic discovery is given in Section 2.1 , with the matching lower bound following in Section 2.2 . An efficient Algorithm is presented in 2.3 . For completeness, we provide a more detailed technical comparison of our results with prior work in Section 2.4 . Finally, we give a proof sketch for the main results in Section 3 and simulation results in Section 4 . 1.1 Prior work There is a long line of work that focuses on recovering the underlying directed acyclic graph (DAG) in structural equation models.

Read the complete text