Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time

Yu Cheng, Honghao Lin

Introduction

Bayesian networks are fundamental tools for representing complex, high-dimensional probability distributions. However, real-world data is rarely pristine. Often, a small fraction ($\epsilon$) of the data might be "adversarially corrupted"—meaning an attacker or systemic error could have arbitrarily altered those samples, potentially derailing standard learning algorithms.

This paper presents the first nearly-linear time algorithm for robustly learning the parameters of a Bayesian network with a known structure. By establishing a clever reduction to robust mean estimation and developing a new, faster mean estimation subroutine for sparse data, the authors achieve a significant speedup over previous methods—improving runtime by a factor of $d/\epsilon$—while maintaining an error guarantee that does not explode as the number of variables increases.

The Challenge of Adversarial Corruptions

The core goal is robust learning: given a fixed graph structure and a set of corrupted samples, can we estimate the underlying distribution such that our error depends only on the fraction of corruption ($\epsilon$), and not on the number of variables ($d$)?

While previous researchers have developed algorithms to achieve this dimension-independent error, their methods were computationally expensive. For a network with $d$ variables and $N$ samples, the best prior robust algorithms were significantly slower than standard, non-robust estimators. Specifically, prior state-of-the-art methods ran in $\Omega(Nd^2/\epsilon)$ time. This paper aims to close that gap, making robust learning nearly as fast as naive learning.

Methodology: A Sparse Reduction to Mean Estimation

The authors' approach relies on two major technical pillars to bypass the computational bottlenecks of prior work:

  1. Reduction to Robust Mean Estimation: The authors demonstrate that learning the Conditional Probability Table (CPT) of a Bayesian network can be framed as a robust mean estimation problem. They conceptually "expand" each $d$-dimensional sample into a much larger $m$-dimensional vector, where $m$ is the total number of entries in the CPT. They prove that the mean of these expanded vectors directly relates to the true parameters of the network.
  2. Exploiting Sparsity: A naive expansion to $m$ dimensions would be disastrous for performance because $m$ can be exponentially larger than $d$. However, the authors observe a crucial structural property: each expanded vector is exactly $d$-sparse (only $d$ entries are non-zero). They develop a novel robust mean estimation algorithm that runs in time proportional to the number of non-zero entries ($nnz$), rather than the total dimension $m$. This sparsity exploitation is the key to achieving nearly-linear runtime.
  3. Iterative Refinement: The algorithm proceeds iteratively. Starting with an initial guess of the parameters, it uses the sparse robust mean estimation subroutine to find the "direction" toward the true parameters, updating the guess until convergence.

Key Insights

  • The Sparsity Advantage: Even though a Bayesian network's parameter space can be enormous, any single data point only provides information about $d$ specific conditional probabilities. By designing a mean estimation algorithm that capitalizes on this sparsity, the authors bypass the curse of dimensionality in their runtime.
  • Simplicity over Filtering: Previous robust Bayesian network algorithms relied on complex "filtering" techniques to prune bad samples based on specific tail bounds. This paper shows that treating the problem as a black-box mean estimation task significantly simplifies both the mathematical analysis and the algorithmic implementation.
  • Dimension-Independent Error: The algorithm achieves an error guarantee (measured in Total Variation distance) that is independent of $d$. Consequently, the algorithm remains accurate even as the network grows very large, provided the corruption fraction $\epsilon$ remains small.

Theoretical Results

As a theoretical machine learning paper, the results are validated through rigorous mathematical proofs of sample and computational complexity, assuming an $\epsilon$-corrupted set of $N$ samples drawn from a $c$-balanced Bayesian network.

  • Nearly-Linear Runtime: The algorithm runs in $\tilde{O}(Nd)$ time. This is a major improvement over the previous state-of-the-art, effectively removing the $d/\epsilon$ overhead.
  • Optimal Error: The algorithm outputs a network $Q$ such that the distance to the true network $P$ is $d_{TV}(P, Q) \leq O(\epsilon \sqrt{\ln(1/\epsilon)} / \sqrt{\alpha c})$. This matches the best-known error guarantees for this problem.
  • Sample Complexity: The algorithm requires $N = \tilde{\Omega}(m/\epsilon^2)$ samples, which is near-optimal even in the non-robust setting.

Limitations and Future Work

While this work represents a significant leap forward in robust learning, the authors note a few limitations that pave the way for future research:

  • Binary Variables: The current proofs and algorithm are tailored for Bayesian networks where all variables are binary. Extending this framework to categorical or continuous variables is a natural next step.
  • Fixed Structure: The algorithm assumes the graph structure (the directed acyclic graph) is already known. Robustly learning the structure of the graph in nearly-linear time remains an open and considerably harder challenge.
  • Dependence on Network Parameters: The error guarantee depends on the "balance" of the network ($c$) and the minimum probability of any parental configuration ($\alpha$). Removing this dependence is an important technical question for future robust estimators.

Summary updated

Abstract

We study the problem of learning Bayesian networks where an $\epsilon$-fraction of the samples are adversarially corrupted. We focus on the fully-observable case where the underlying graph structure is known. In this work, we present the first nearly-linear time algorithm for this problem with a dimension-independent error guarantee. Previous robust algorithms with comparable error guarantees are slower by at least a factor of $(d/\epsilon)$, where $d$ is the number of variables in the Bayesian network and $\epsilon$ is the fraction of corrupted samples. Our algorithm and analysis are considerably simpler than those in previous work. We achieve this by establishing a direct connection between robust learning of Bayesian networks and robust mean estimation. As a subroutine in our algorithm, we develop a robust mean estimation algorithm whose runtime is nearly-linear in the number of nonzeros in the input samples, which may be of independent interest.
BibTeX
@inproceedings{cheng2021robust,
  author = {Yu Cheng and Honghao Lin},
  title = {{Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=euDnVs0Ynts},
}

Loading related content...

Figure