Robust Learning of Fixed-Structure Bayesian Networks
We investigate the problem of learning Bayesian networks in a robust model where an -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.
I preface this by saying that I have reviewed this paper once for NIPS 2016, and re-read it. It seems the paper has no essential changes, so my opinion is largely the same.   The paper considers the problem of learning the parameters of a Bayes net with known structure, given samples from it with potentially adversarial noise. The main goal is to get bounds on the samples that are independent of dimension. The main requirements on the Bayes net parameters are reasonable: the probability of any configuration of the parents is reasonable and the conditional probabilities on any edge are bounded away from 0 and 1.   The algorithm is quite similar morally to [DKK+16] -- on a high level it designs a quantity F(X,q), s.t. E[F(X,p)] = p, where p is the conditional probability "table" specified by the Bayes net and q is the empirical conditional probability table. The covariance matrix of F(X,q) on the other hand, "catches" the adversarial noise: if the covariance has a large eigenvalue, one can "filter" the "culprit" samples, and repeat the process. Otherwise, the empirical estimate is close in TV distance.    The paper is well-written, though the proofs are straightforward and natural (and largely follow the structure of [DKK+16]). There are some new tricks (e.g. how one "fills in" F(X,q) in the unobserved spots; why the mean of F(X,p) is diagonal; and how to use the spikes in the spectrum to produce a filter), but I feel like it's a poor fit for NIPS for two reasons.    For one, the techniques are quite similar to [DKK+16];  For another, it may be of interest to a relatively specialized crowd, both in terms of theoretical tools and practical algorithms.   As mentioned a previous time I reviewed this paper: the more interesting question is structure-learning Bayes nets, even under "benign" noise assumptions.  _______________________ Edit after rebuttal: after the rebuttal/discussions with other reviewers, my opinion is largely the same, though I may have scored a bit harshly. Correspondingly, I raised my score up by a point.