Learning Large-Scale MTP$_2$ Gaussian Graphical Models via Bridge-Block Decomposition
This work addresses computational bottlenecks in learning large-scale MTP$_2$ Gaussian graphical models, offering a method that improves efficiency for researchers and practitioners in fields like statistics and machine learning, though it is incremental as it builds on existing algorithms.
The paper tackles the problem of learning large-scale Gaussian graphical models under multivariate total positivity of order two (MTP$_2$) constraints by introducing a bridge-block decomposition method, which breaks the problem into smaller sub-problems and explicit solutions, resulting in significant computational speed-ups in synthetic and real-world experiments.
This paper studies the problem of learning the large-scale Gaussian graphical models that are multivariate totally positive of order two ($\text{MTP}_2$). By introducing the concept of bridge, which commonly exists in large-scale sparse graphs, we show that the entire problem can be equivalently optimized through (1) several smaller-scaled sub-problems induced by a \emph{bridge-block decomposition} on the thresholded sample covariance graph and (2) a set of explicit solutions on entries corresponding to bridges. From practical aspect, this simple and provable discipline can be applied to break down a large problem into small tractable ones, leading to enormous reduction on the computational complexity and substantial improvements for all existing algorithms. The synthetic and real-world experiments demonstrate that our proposed method presents a significant speed-up compared to the state-of-the-art benchmarks.