A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
This is an incremental improvement for researchers in causal inference and graphical models, addressing computational challenges in sparse directed acyclic graph learning.
The authors tackled the NP-hard problem of structure learning on linear structural causal models by developing a Bregman proximal gradient method that neutralizes curvature effects, allowing longer steps and significantly improving convergence, with efficient convex proximal steps.
We develop a Bregman proximal gradient method for structure learning on linear structural causal models. While the problem is non-convex, has high curvature and is in fact NP-hard, Bregman gradient methods allow us to neutralize at least part of the impact of curvature by measuring smoothness against a highly nonlinear kernel. This allows the method to make longer steps and significantly improves convergence. Each iteration requires solving a Bregman proximal step which is convex and efficiently solvable for our particular choice of kernel. We test our method on various synthetic and real data sets.