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

Yu Cheng, Honghao Lin

Introduction

Bayesian networks are fundamental tools in probabilistic graphical modeling, used to represent complex dependencies among high-dimensional variables. When the structure of the network—a directed acyclic graph (DAG)—is known and the data is clean, estimating the parameters (conditional probability tables, or CPTs) is a straightforward task of counting empirical frequencies. However, real-world datasets are rarely pristine. They are often subject to the strong contamination model, where an adversary can inspect the data and arbitrarily corrupt an $\epsilon$-fraction of the samples.

While recent theoretical breakthroughs have established polynomial-time algorithms for robustly learning these parameters with dimension-independent error, these methods remain computationally expensive. Previous state-of-the-art algorithms typically scaled at $\Omega(Nd^2/\epsilon)$, where $N$ is the number of samples and $d$ is the number of variables. This paper introduces the first algorithm to achieve this task in nearly-linear time, $\tilde{O}(Nd)$, effectively matching the time it takes to simply read the input data.

The Challenge of Contaminated Data

In the presence of adversarial noise, standard empirical estimators fail. A single outlier can significantly skew the conditional probability estimates. To combat this, robust statistics seeks estimators that remain close to the true distribution despite the $\epsilon$-fraction of corrupted points. The primary goal is to achieve an error guarantee in terms of Total Variation (TV) distance that depends only on the corruption level $\epsilon$ and specific network properties, rather than the dimensionality $d$ of the system.

Algorithmic Framework: Reduction to Mean Estimation

The authors achieve their speedup by reducing the problem of parameter learning to a sequence of robust mean estimation tasks. The process follows an iterative refinement loop:

  1. Data Expansion: The algorithm begins with an initial estimate of the conditional probabilities. Each $d$-dimensional sample is "expanded" into a much larger $m$-dimensional vector, where $m$ represents the total number of entries across all conditional probability tables.
  2. Iterative Refinement: The expected value of these expanded vectors represents the gradient or "gap" between the current estimate and the true underlying probabilities. By robustly estimating the mean of these expanded vectors, the algorithm can update its guess.
  3. Exploiting Sparsity: While the expanded dimension $m$ can be exponentially larger than $d$ in the worst case, the authors observe a critical structural property: the expanded vectors are highly sparse. For any given sample, only one configuration of parents is active for each node, meaning the $m$-dimensional vector contains exactly $d$ non-zero entries.

Sparse Robust Mean Estimation

The core technical contribution is a novel robust mean estimation subroutine designed specifically for sparse inputs. To avoid the computational penalty of working in $m$ dimensions, the authors optimize the Matrix Multiplicative Weight Update (MMWU) method. By integrating the Johnson-Lindenstrauss lemma for dimensionality reduction and utilizing sparse matrix multiplication, the subroutine's runtime scales with the number of non-zero entries ($Nd$) rather than the full dimension ($Nm$). This allows the algorithm to bypass the "computational tax" usually associated with high-dimensional robust estimation.

Key Results and Performance

The resulting algorithm provides several significant theoretical guarantees:

  • Computational Efficiency: The total runtime is $\tilde{O}(Nd)$, making it significantly faster than the previous $\Omega(Nd^2/\epsilon)$ benchmark and nearly optimal for processing large datasets.
  • Sample Complexity: The algorithm requires $N = \tilde{\Omega}(m/\epsilon^2)$ samples, matching known information-theoretic lower bounds up to logarithmic factors.
  • Dimension-Independent Error: The algorithm achieves a TV distance error of $O(\epsilon \sqrt{\log(1/\epsilon)} / \sqrt{\alpha c})$. Crucially, this error does not grow with the number of variables $d$, though it does depend on the minimum probability of parental configurations ($\alpha$) and how close probabilities are to the boundaries (0 or 1, represented by $c$).

Limitations and Future Directions

While the algorithm represents a major step forward in efficient robust statistics, some limitations remain. The error guarantee is sensitive to "extreme" probabilities (where $\alpha$ or $c$ are very small), and the current framework assumes a fixed, known graph structure with fully observable binary variables. Future work may explore extending these nearly-linear time techniques to settings with unknown structures or latent variables, further bridging the gap between theoretical robust statistics and practical large-scale machine learning applications.

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