Robust Learning of Fixed-Structure Bayesian Networks

We investigate the problem of learning Bayesian networks in a robust model where an $\epsilon$-fraction of the samples are adversarially corrupted. In this work, we study the fully observable discrete case where the structure of the network is given. Even in this basic setting, previous learning algorithms either run in exponential time or lose dimension-dependent factors in their error guarantees. We provide the first computationally efficient robust learning algorithm for this problem with dimension-independent error guarantees. Our algorithm has near-optimal sample complexity, runs in polynomial time, and achieves error that scales nearly-linearly with the fraction of adversarially corrupted samples. Finally, we show on both synthetic and semi-synthetic data that our algorithm performs well in practice.

• Publication year

  2016

• Venue

  Neural Information Processing Systems

• Publication date

  2016-06-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1606.07384
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Graphical Models

  2020cited by this paper
• Mixture Models

  2019cited by this paper
• Efficient Algorithms and Lower Bounds for Robust Linear Regression

  2018cited by this paper
• High Dimensional Robust Sparse Regression

  2018cited by this paper
• Robust Statistics

  2018cited by this paper
• Efficient Algorithms for Outlier-Robust Regression

  2018cited by this paper
• Sever: A Robust Meta-Algorithm for Stochastic Optimization

  2018cited by this paper
• Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms

  2018cited by this paper
• Robust estimation via robust gradient estimation

  2018cited by this paper
• Robust moment estimation and improved clustering via sum of squares

  2018cited by this paper
• List-decodable robust mean estimation and learning mixtures of spherical gaussians

  2017cited by this paper
• Being Robust (in High Dimensions) Can Be Practical

  2017cited by this paper
• Learning geometric concepts with nasty noise

  2017cited by this paper
• Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

  2017cited by this paper
• Mixture models, robustness, and sum of squares proofs

  2017cited by this paper
• Computationally Efficient Robust Sparse Estimation in High Dimensions

  2017cited by this paper
• A general decision theory for Huber’s (cid:2) -contamination model

  2017cited by this paper
• Robust Estimators in High Dimensions without the Computational Intractability

  2016cited by this paper
• Agnostic Estimation of Mean and Covariance

  2016cited by this paper
• Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures

  2016cited by this paper
• Testing Bayesian Networks

  2016cited by this paper
• Fast Algorithms for Segmented Regression

  2016cited by this paper
• Robust covariance and scatter matrix estimation under Huber’s contamination model

  2015cited by this paper
• Sample-Optimal Density Estimation in Nearly-Linear Time

  2015cited by this paper
• Robust Covariance Matrix Estimation via Matrix Depth

  2015cited by this paper
• Structure learning of antiferromagnetic Ising models

  2014cited by this paper
• Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms

  2014cited by this paper
• Efficiently Learning Ising Models on Arbitrary Graphs

  2014cited by this paper
• Efficient density estimation via piecewise polynomial approximation

  2013cited by this paper
• Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses

  2012cited by this paper
• Learning Mixtures of Tree Graphical Models

  2012cited by this paper
• Algorithms and Hardness for Robust Subspace Recovery

  2012cited by this paper
• Learning mixtures of structured distributions over discrete domains

  2012cited by this paper
• Learning k-Modal Distributions via Testing

  2012cited by this paper
• Learning Bayesian networks: approaches and issues

  2011cited by this paper
• Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning

  2009cited by this paper
• Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions

  2009cited by this paper
• Graphical Models, Exponential Families, and Variational Inference

  2008cited by this paper
• High-Dimensional Graphical Model Selection Using $\ell_1$-Regularized Logistic Regression

  2008cited by this paper
• Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms

  2007cited by this paper
• Learning Bayesian networks

  2007cited by this paper
• High-Dimensional Graphical Model Selection Using ℓ1-Regularized Logistic Regression

  2006cited by this paper
• Robust Estimators are Hard to Compute

  2006cited by this paper
• Learning Factor Graphs in Polynomial Time and Sample Complexity

  2006cited by this paper
• Bayesian Networks and Decision Graphs

  2001cited by this paper
• The Sample Complexity of Learning Fixed-Structure Bayesian Networks

  1997cited by this paper
• The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality

  1990cited by this paper
• The ALARM Monitoring System: A Case Study with two Probabilistic Inference Techniques for Belief Networks

  1989cited by this paper
• Robust Statistics—The Approach Based on Influence Functions

  1986cited by this paper
• On robust estimation of the location parameter

  1980cited by this paper
• The Densest Hemisphere Problem

  1978cited by this paper
• Mathematics and the Picturing of Data

  1975cited by this paper
• Approximating discrete probability distributions with dependence trees

  1968cited by this paper
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator

  1956cited by this paper

• Brain-inspired semantic data augmentation for multi-style images

  2024cites this paper
• On Deterministically Approximating Total Variation Distance

  2023cites this paper
• Beyond Performative Prediction: Open-environment Learning with Presence of Corruptions

  2023cites this paper
• A hyper-heuristic guided by a probabilistic graphical model for single-objective real-parameter optimization

  2022cites this paper
• MBGDT: Robust Mini-Batch Gradient Descent

  2022cites this paper
• On Approximating Total Variation Distance

  2022cites this paper
• Streaming Algorithms for High-Dimensional Robust Statistics

  2022cites this paper
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples

  2021cites this paper
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition

  2021cites this paper
• Robust Estimation for Random Graphs

  2021cites this paper
• Deep learning in ECG diagnosis: A review

  2021cites this paper
• Clustering mixture models in almost-linear time via list-decodable mean estimation

  2021cites this paper
• Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time

  2021influential citation
• Saving computational budget in Bayesian network-based evolutionary algorithms

  2021cites this paper
• A survey on deep learning and its applications

  2021cites this paper
• List-Decodable Mean Estimation in Nearly-PCA Time

  2020cites this paper
• Combining information from thresholding techniques through an evolutionary Bayesian network algorithm

  2020cites this paper
• Exact Asymptotics for Learning Tree-Structured Graphical Models With Side Information: Noiseless and Noisy Samples

  2020cites this paper
• Robustly Learning any Clusterable Mixture of Gaussians

  2020cites this paper
• List Decodable Mean Estimation in Nearly Linear Time

  2020cites this paper
• List-Decodable Mean Estimation via Iterative Multi-Filtering

  2020cites this paper
• Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers

  2020influential citation
• Towards capsule routing as reconstruction with sparsity constraints

  2020cites this paper
• The FEDHC Bayesian network learning algorithm

  2020cites this paper
• Robustly learning mixtures of k arbitrary Gaussians

  2020cites this paper
• How Hard Is Robust Mean Estimation?

  2019cites this paper
• On resampling vs. adjusting probabilistic graphical models in estimation of distribution algorithms

  2019cites this paper
• Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering

  2019cites this paper
• Recent Advances in Algorithmic High-Dimensional Robust Statistics

  2019cites this paper
• On Updating Probabilistic Graphical Models in Bayesian Optimisation Algorithm

  2019cites this paper
• Faster Algorithms for High-Dimensional Robust Covariance Estimation

  2019cites this paper
• Efficient Algorithms and Lower Bounds for Robust Linear Regression

  2018cites this paper
• Sever: A Robust Meta-Algorithm for Stochastic Optimization

  2018cites this paper
• High-Dimensional Robust Mean Estimation in Nearly-Linear Time

  2018cites this paper
• Deep Neural Network Concepts for Background Subtraction: A Systematic Review and Comparative Evaluation

  2018cites this paper
• Robust Estimation and Generative Adversarial Nets

  2018cites this paper
• On Robust Learning of Ising Models

  2018cites this paper
• Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

  2017cites this paper
• Being Robust (in High Dimensions) Can Be Practical

  2017cites this paper
• List-decodable robust mean estimation and learning mixtures of spherical gaussians

  2017cites this paper
• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers

  2017influential citation
• Robust Sparse Estimation Tasks in High Dimensions

  2017cites this paper
• Learning geometric concepts with nasty noise

  2017cites this paper
• Testing Symmetric Markov Chains From a Single Trajectory

  2017cites this paper
• Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures

  2016cites this paper
• Testing Bayesian Networks

  2016cites this paper