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:
- 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.
- 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.
- 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