Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time
Authors: Yu Cheng
Honghao Lin
Venue: ICLR 2021 Poster (2021)
Keywords: Bayesian networks
robust statistics
learning theory

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.

Published as a conference paper at ICLR 2021
ROBUST LEARNING OF FIXED-STRUCTURE BAYESIAN NETWORKS IN NEARLY-LINEAR TIME
Yu Cheng
Honghao Lin
Department of Mathematics (MSCS) University of Illinois at Chicago yucheng28us uic.
Institute for Theoretical Computer Science Shanghai University of Finance and Economics Gu Muillan301@@mm com
ABSTRACT
We study the problem of learning Bayesian networks where e-fraction of the samples are adversarially corrupted. We focus on the fully-obserrablec case where the underlying graph structure is known. In this work, present the first nearly- linear time algorithm for this problem with a coamension-independeee antee. Previous robust algorithms with comparable error guarantees slower by at least a factor of (d/e), where d is the number of variables in the Bayesian network and is the fraction of corrupted samples. Our algorithm and analysis are considerably simpler than those in previous work. We achieve this by establish- ing 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 nearly-linear in the number of nonzeros the input samples, which may be of independent interest.
error guar-
INTRODUCTION
Probabilistic graphical models (Koller & Friedman, 2009) offer elegant and succinct way to represent structured high-dimensional distributions. The problem of inference and learning in prob- abilistic graphical models is important problem that arises in many disciplines (see WWiiwwrihht & Jordan (2008) and the references therein). which has been studied extensively during the past decades (see, e.g.. Chow & Liu| (1968); Dasguptal (1997); Abbeel et (2006); |Wainwright et al. [ Anandkumma et al. (2012): Santhanam & Wainwright (2012): Loh & Wainwright (2012);
Bresler et al. (2013 2014): Bresler 2015)).
Bayesian networks (Jensen & Nielsen 2007) are an important family of probabilistic graphical mod- els that represent conditional dependence by a directed graph (see Section formal definition). In this paper, we study the problem of learning Bayesian networks where an e-fraction of the sam- ples are adversarially corrupted. We focus on the simplest setting: variables are binary and observable, and the structure of the Bayesian network is given to the algorithm.
Formally, we work with the following corruption model:
Definition 1.1 (c-Corrupted Set of Samples). Given c < and a distribution family P on TRd, the algorithm first specifies the number of samples N, and N samples X1,X2....,5 X x are drawn from some unknown P E P. The udversary inspects the samples, the ground-truth distribution P. and the algorithm, and then replaces eN samples with arbitrary points. The set of N points is given to the algorithm as input. We say that a set of samples is e-corrupted if is generated by this process.
This a strong corruption model which generalizes many existing models. In particular, it stronger than Huber's contamination model (Huber, 1964), because we allow the adversary add bad samples and remove good samples, and he can do so adaptively.
Our goal is to design robust algorithms for learning Bayesian networks with dimenssonninddepedeen error. More specifically, given as input an e-corrupted set of samples drawn from some ground- truth Bayesian network P and the graph structure of P. want the algorithm output a Bayesian network Q, such that the total variation distance between P and Q is upper bounded by a function that depends only (the fraction of corruption) but not d (the number of variables in P).

---

Published as a conference paper at ICLR 2021
In the fully-observable fixed-structure setting, the problem is straightforward when there is ruption. We know that the empirical estimator (which computes the empirical conditional probabil- ities) is sample efficient and runs in linear time (Dasgupta 1997p.
turns out that the problem becomes much more challenging when there is corruption. Even for robust learning of binary product distributions (i.e., Bayesian network with empty dependency graph), the first computational efficient algorithms with ciimension-indeenndn covered in (Diakonikolas al. 2019a). Subsequently, (Cheng al. (2018) gave the first polynomial- time algorithms for robust learning of fixed-structured Bayesian networks. The main drawback of the algorithm in (Cheng al., 2018) is that it runs in time (2 /c), which slower by at least factor of (d/e) compared to the fastest non-robust estimator.
error was only dis-
Motivated by this gap the running time, in this work we want resolve the following question:
Can design robust algorithm for learning Bayesian networks in the fixed- structure fully-observable seiting that runs in nearly-linear time?
1.1 OUR RESULTS AND CONTRIBUTIONS
We resolve this question affirmatively by proving Theorem 1.2 We say Bayesian network is c- bulanced if all conditional probabilities are between and c. For the ground-truth Bayesian network P. let be the size of its conditional probubility table and a be its minimum parental configuration probability (see Section 2 for formal definitions).
Theorem 1.2 (informal statement). Consider an c-corrupted set of N = (2mm/²2) samples drawn from d-dimensional Bayesian network P. Suppose P is e-balanced and has minimum parental configuration probubility a, where both e and or are universal constants. We can compute a Bayesian network Q in time ((Nd) such that drv (Pvv(,.)) () S <v/nn(1/c..)
For simplicity, we stated our result in the very special case where both c and are 221).. Our approach works for general values of a and c, where our error guarantee degrades gracefully as a and gets smaller. A formal version of Theorem 1.2 is given as Theorem 4.1 in Section
Our algorithm has optimal error guarantee, sample complexity, and running time (up to logarithmic factors). There is an information-theoree lower bound of 22(c) on the error guarantee, which holds even for Bayesian networks with only one variable. A sample complexity lower bound of (mm/²²) holds even without corruption (see, e.g.. (Canonne et al. 2017)).
Our Contributions. We establish a novel connection between robust learning of Bayesian net- works and robust mean estimation. At high level, we show that one can essentially reduce the former to the latter. This allows us to take advantage of the recent (and future) advances in robust mean estimation and apply the algorithms almost directly to obtain new algorithms for learning Bayesian networks.
Our algorithm and analysis are considerably simpler than those in previous work. For simplicity, consider learning binary product distributions an example. [Cheng al. (2018) tried to remove samples to make the empirical covariance matrix closer to a diagonal matrix (since the true covari- ance matrix is diagonal because each coordinate is independent). They used a "filtering" approach which requires proving specific tail bounds on the samples. In contrast, we show that it suffices to any robust mean estimation algorithms which minimize the spectral norm of the empirical covariance matrix (regardless of whether it close to being diagonal or not).
As subroutine in our approach, we develop the first robust mean estimation algorithm that runs in nearly input-sparsity time (i.e., in time nearly linear in the total number of nonzero entries in the input), which may be of independent interest. The main computation bottleneck of current nearly- linear time robust mean estimation algorithms (Cheng et al. (2019a] Depersin & Lecué 2019 Dong al. 2019)) rumning matrix multiplication weight update with the Johnson-Lindensen which we show can be done in nearly input-sparsity time.
lemma,
TThroughout the paper, we use Ō(f) to denote Off polylog(f))-
2

---

Published as a conference paper at ICLR 2021
1.2 RELATED WORK
Bayesian Networks. Probabilistic graphical models (Koller & Friedman 2009) provide an ap- pealing and unifying formalism succinetly represent structured high-dimensional distributions. The general problem of inference in graphical models is of fundamental importance and arises in many applications across several scientific disciplines (see Wainwright Jordan (2008) and refer- ences therein). The problem of learning graphical models from data (Neapolitan 2003 Daly et al.) 2011] has many variants: (i) the family of graphical models (e.g.. directed, undirected), (ii) whether the data is fully or partially observable, and (iii) whether the graph structure is known or not. This learning problem has been studied extensively (see, e.g., Choo & Liu (1968); Dasgupta (1997); Abbeel et al. (2006); Wainwright al. (206);; Anandkumar et al. [2012): Santhanam & Wainwright ;2012); Loh & Wainwright )2012); Bresler et al. (2013) 2014); Bresler (2015), resulting in a beau- tiful theory and collection of algorithms in various settings.
Robust Statistics. Learning in the presence of outliers has been studied since the 1960s (Huber 1964). For the most basic problem of robust mean estimation, it is well-known that the empirical median works one dimension. However, most natural generalizations of the median to high
dimensions (e.g., coordinate-wise median, geometric median) would incur an error of (e(v d). even in the infinite sample regime (see, e.g.. "g..Diaooiiklas et al. (2019a); [ai al. (2016)) After decades of work, sample-efficient robust estimators have been discovered (e.g., the Tukey median (Tukey) 1975 Devroye Györfi 1983] Chen al. 2018)). However, the Tukey median is NP-Hard to
compute in the worse case (Johnson & Preparata 1978 Amaldi & Kann 1995) and many heuristics
for approximating it perform poorly as the dimension scales (Clarkson al., 1993
Chan 2004
Miller & (rrechy20100)
Computational Efficient Robust Estimators. Recent work (Diakonikolas al. 2019a Lai et al. 2016) gave the first polynomial-time algorithms several high-dimensional unsupervised learning tasks (e.g., mean and covariance estimation) with cumeession-inepenniee the dissemination of (Diakonikolas et al. 2019a Lai et al.. 2016), algorithmic high-dimensional robust statistics has attracted a lot of recent attention and there has been a flurry of research that obtained polynomial-time robust algorithms for wide range of machine learning and statistical tasks (see, e.g., Balakrishnan et al. (2017); Charikar et al. (2017); Diakonikolas et al. (2017a b); Steinhardt et al. (2018); : Diakonikolas
error guarantees. After
al. (2018): (Hopkins & Li (2018)
: Kothari al. (201 8);
Prasad et al. (2020); Diakonikolas et al. 12); Klivans et al. (2018): Diakonikolas et al. 2019c);
Liu et al. (2020); Cheng al. (2020); Zhu
(2020)). In particular, the most relevant prior work is (Cheng et 2018)) which gave the first polynomial-timg algorithms for robust learning of
fixed-structure Bayesian networks.
Faster Robust Estimators. While recent work gave polynomial-time robust algorithms for many tasks, these algorithms are often significantly slower than the fastest non-robust ones (e.g., sample average for mean estimation). Cheng et al. (2019a) gave the first nearly-linear time algorithm for robust mean estimation and initiated the research direction of designing robust estimators that are efficient their non-robust counterparts. Since then, there have been several works that develop faster robust algorithms for various learning and statistical tasks, including robust mean estimation for heavy-tailed distributions Dong et al. (2019); [Depersin & Lecué 2019), robust covariance esti- mation Cheng et al. (2019)); Li & Ye (020). robust linear regression Cherapanamjeri et al. (2020a) and list-decodable mean estimation Cherapanamjeri al. (002bb) Diakonikolas et al. (2020).
Organization. In Section 2 we define our notations and provide some background on robust learn- ing of Bayesian networks and robust mean estimation. In Section we give an overview of our approach and highlight some of our key technical results. In Section we present our algorithm for robust learning of Bayesian networks and prove our main result.
PRELIMINARIES
Bayesian Networks. Fix d-node directed acyelic graph H whose nodes are labelled [d] (1,2...., d} in topological order (every edge goes from a node with smaller index to one with larger index). Let Parents(i) be the parents of node in H. A probability distribution P on
3

---

Published as a conference paper at ICLR 2021
{0, 1 is Bayesian network (or Bayes net) with graph H if, for each [d] we have that Prx~p [X; = ( depends only on the values X, where j E Parents(i).
Conditional Probability Table. Let P be a Bayesian network with graph H. Let I { a) i E [d] {0, 1) be the set of all possible parental configurations, Let m = [T]. For
(i,a) the parental configuration 1T is defined to be the event that X (Parentssi)) a. The
conditional probability table E [0, 11 of P is given by Pi.a = Prx-P (x = [[;a].
In this paper, often index p as an m-ddimensional vector. We use the notation ps and the associated events l2. where each k E [m]]] stands for an (i, a) E lexicographically ordered.
Notations. For vector let ||e|l and || be the &g and loo norm of v respectively. We write ve and 1/c for the entrywise square root and entrywise inverse of a vector respectively, For two vectors and y, we write x² y for their inner product, and x y for their entrywise product.
We use / to denote the identity matrix. For matrix M, let M, be the i-th column of M, and let [|M ll be the spectral norm of M. For vector R", let diag(v) E R=x= denote diagonal matrix with v on the diagonal.
Throughout this paper, we use P denote the ground-truth Bayesian network. We use d for the dimension (i.e., the number of nodes) of P. N for the number of samples, for the fraction of corrupted samples, and = Σi -i=1 2)Parents(()) for the size of the conditional probability table of P. We use E R to denote the (unknown) ground-truth conditional probabilities of P, and E R for our current guess of p.
Let G* be the original set of N uncorrupted samples drawn from P. After the adversary corrupts an e-fraction of G*, let G C G be the remaining of good samples, and B be the set of bad samples added by the adversary. The set of samples S = G U B given to the algorithm as input. Let X Tx denote the sample matrix whose i-th column X, Rd is the i-th input sample. Abusing notation, we sometimes also use X as a random variable (e.g., a sample drawn from P).
We use TP RT denote the parental configuration probabilities of P. That is, o Prx XX E MT]. For configuration probabilities over S: मं = Prx [X E [Tg] where is uniformly drawn from S.
of samples, we use S Rm to denote the empirical parental
Balance and Minimum Configuration Probability. We say a Bayesian network P is c- c-balanced all conditional probabilities of P are between e and 1 We use a for the minimum probability of parental configuration of P: a = ming =f.
In this paper, we assume that the ground-truth Bayesian network is e-balanced, and its minimum parental configuration probability a satisfies that generality, we further assume that both e and a are given to the algorithm.
Without loss of
2.1 TOTAL VARIATION DISTANCE BETWEEN BAYESIAN NETWORKS
Let P and Q be two distributions supported on a finite domain D. For a set of outcomes A, let P(A) = PIx~P(X X E A]. The total variation distance between 1' and Q is defined as
drv (P. Q) max ((A) Q(A))
AÇD
For two balanced Bayesian networks that share the same structure, is well-known that the closeness their conditional probabilities implies their closeness total variation distance. Formally, we use the following lemma from Cheng al. (2018), which upper bounds the total variation distance between two Bayesian networks in terms of their conditional probabilities.
Lemma 2.1 (Cheng et al. (2018), Let P and Q be two Bayesian networks that share the same structure. Let and denote the conditional probability tables of P and Q respectively. We have
(pk ]²
(drv < Σ
T
T (pr + (2) Pk 9k
b
4

---

Published as a conference paper at ICLR 2021
2.2 EXPANDING THE DISTRIBUTION TO MATCH CONDITIONAL PROBABILITY TABLE
Lemma 2.1 states that to learn a Known-structure Bayesian network P. it is sufficient to learn its conditional probabilities p. However, a given coordinate of X P may contain information about multiple conditional probabilities (depending on which parental configuration happens).
To address this issue, we use a similar approach as in Cheng al. (2018). We expand each sample X into an m-dimensional vector f(X, q). such that each coordinate of f(X, g) corresponds to an entry in the conditional probability table. Intuitively, q E R is our current guess for p. and initially we set to be the empirical conditional probabilities. We use 9 to fill in the missing entries in f(X. for which the parental configurations fail to happen.
Definition 2.2. Let q) for {0, 1]d x 1 + I be defined as follows:
X; qi,a El, {or
((X,9)ss
otherwise
When X ~ P and q p, the distribution of (XX,)) p) has many good properties. Using the condi- tional independence of Bayesian networks, we can compute the first and second moment of f((.p) and show that / /Xx,2) has subgaussian tails.
Lemma 2.3. For X P and f(X,p) p) as defined in Definition 2.2 we have
(i) ((f(X. p)) = O. (ii) Covlf(X, p)] = diag(T" o o (1-p)). (iii) For any unit vector v E R" we have Prx~p [|v f(X.p)) 2 T| s 2 exxp(-T2/2)
We defer the proof of Lemma 2.3 Appendix A. A slightly stronger version of Lemma 2.3 was proved in Cheng et al. 2018), which discusses tail bounds for s(X,q). For our analysis, Lemma 2.3 sufficient.
For general values of we can similarly compute the mean of f(X, g):
Lemma 2.4. Let T" denote the parental configuration of P. For X ~ and f(X, q) as defined in
Definition 2.2 we have [X] 4)] TT" (p q).
2.3
DETERMINISTIC CONDITIONS ON GOOD SAMPLES
To avoid dealing with the randomness of the good samples, we require the following deterministic conditions to hold for the original set G* of N good samples (before the adversary's corruption).
We prove in Appendix A that these three conditions hold simultaneously with probability at least 7 if we draw N (m log(m/r)/e² samples from
The first condition states that we can obtain good estimation of p from G*. Let p denote the empirical conditional probabilities over G*. We have
|| V o (p- s0(c.
(1)
The second condition says that we can estimate the parental configuration probabilities x from any (1 fra-ftaci of G*. Formally, for any subset T C G* with [T] 2 (1 - -2c)N, we have
| - π Pl < 5(()).
The third condition is that the empirical mean and covariance of any 2c fracctin of G* are very close to the true mean and covariance of f(X, p). Formally, for any subset T C G* with [T] (1 Ne)N, require the following to hold for óN cvin 1/c and 82 cln(1/c):
1/1
1
E((X,,) p)
20()))
Σ f(X. ((xx)))(xx.)) - <0(())
(3)
T
T
iET
2
iET
2
where == Cov(S(XX
diag(= opo (1 p)).
5

---

Published as a conference paper at ICLR 2021
2.4 ROBUST MEAN ESTIMATION AND STABILITY CONDITIONS
Robust mean estimation is the problem of learning the mean of d-dimensional distribution from an e-corrupted set of samples. As we will see in later sections, to robustly learn Bayesian networks, we repeatedly use robust mean estimation algorithms as a subroutine.
Recent work (Diakonikolas et al. 2019a Lai et al. 2016) gave the first polynomial-tinn algorithms robust mean estimation with dimension-inddeeendenn error guarantees. The key observation in Di- akonikolas et al. (2019)) is the following: if the empirical mean is inaccurate, then many samples must be far from the true mean in roughly the same direction. Consequently, these samples must alter the variance in this direction more than they distort the mean. Therefore, the empirical co- variance behaves mean.
expect it to be, then the empirical mean provides a good estimate to the true
Many robust mean estimation algorithms follow the above intuition, and they require the following stability condition to work (Definition (.3]. Roughly speaking, the stability condition states that the mean and covariance of the good samples are close to that of the true distribution, and more importantly, this continues to hold if we remove any 2e-fraction of the samples.
Definition 2.5 (Stability Condition (see, e.g.. Diakonikolas & Kane 2019 Fix 0 <<0<<<> 2.2 Fix d-dimensional distribution X with mean μ.x We say a set of samples (c, (. with respect to X, for every subset T C S with [T] 2 (1 - 2c){s), (S) the following conditions hold:
(i) Exer (X (x-xxx)))
-x) $ (ii)
प. Exer (x - uxx - xx) - S7.
Subsequent work (Cheng et al. 2019a Dong et al. 2019 Depersin & Lecué 2019) improved the
runtime of robust mean estimation to nearly-linear time. Formally, we use the following result from Dong et al. (011)). A set S is an e-corrupted version of a set 7 if |S| = [7] and |SS S {
Lemma 2.6 (Robust Mean Estimation in Nearly-Linear Time (Dong et al. 2019). Fix of N samples G in Rdd Suppose G* is (e, 3,7) (B,7)-stabbl with respect to a d-dimensional distribution X with mean Px E Rd. Let S be e-corrupted version of G Given input S, 3, y, there exists an algorithm that can outpul an estimator is E IRd in time Ö (Nd). such that with high probability, ll 4xll2 S O(ver + + ev 1/e).
As we will see later, a black-box use of Lemma 2.6 does not give the desired runtime in our setting. Instead, we extend Lemma 2.6 to handle sparse input such that it runs in time nearly-lines in the number of non-zeros in the input (see Lemma 3.3
3 OVERVIEW OF OUR APPROACH
In this section, we give an overview of our approach and highlight some of our key technical results.
To robustly learn the ground-truth Bayesian network P, it is sufficient to learn its conditional prob- abilities p Rm At high level, we start with guess g E R for p and then iteratively improve our guess to get closer to For any E RT" we can expand the input samples into m-dimennional vectors s(X,)) .) as in Definition 2.2 We first show that the expectation of f(X.g) g) gives us useful information about (p 1-4) 4).
Recall that r" is the parental configuration probabilities of P. By Lemma 2.4 we have
E Ex-r(f(X.g)) P (p q)
Note that if we had access to this expectation and the vector R., we can set q' = [X q)] o (1/x") + q which simplifies to q'
could recover p immediately:
Note that since S is an e-corrppeed set of samples of P. we know that (f(X,, hes is e-corrupted set of samples of the distribution f(X,o q) (with X ~ P). Therefore, we can run robust mean estimation algorithms on {f(X,, q)ees to leam E(f(X, q)]. It turns out good approximation of (X, g)) can help us improve our current guess q.
There two main difficulties in getting this approach to work.

---

Published as a conference paper at ICLR 2021
The first difficulty is that, to use robust mean estimation algorithms, need to show that f(x, g) satisfies the stability condition in Definition 2.5 This requires us to analyze the first two moments and tail bounds of ()X,q). Consider the second moment for example. Ideally, we would like to have a statement of the form Cov[s(X, q) ~ [ov[s(X,p) p)] + (p () q) but this is false because only have f(X,p), p)s [(X, Q) = (p - q)s if the k-th parental configuration happens for X. Intuitively, the "error" (p q) is shattered into all samples where each sample only gives d out of m coordinates of (p- q). and there no succinct representation for (o, g)).
The second difficulty is that _(X, q) is mn-dimensional. We cannot explicitly write down all the sam- ples {f 9) { because this takes time (()m)) which could be much slower than our desired running time of (Nd). Similarly, a black-box use of nearly-linear time robust mean estimation algorithms (e.g.. Lemma 2.6p runs in time ((Nm), which is too slow.
In the rest of this section, we explain how we handle these two issues.
Stability Condition of f(X, q). Because the second-order stability condition in Lemma 2.3 defined with respect to 1, we first scale the samples so that the covariance of f(X, p) becomes I. diag(= coollppooll11
Lemma 2.3 shows that Cfv[f(X pX]] the k-th coordinate of f(X. p) by (Tf'Px<L Px pk))) 1/2 However, we do not know the exact value of TT or p. instead we use the corresponding empirical estimates 75 and q² (see Algorithm D
To make it close to I, we can multiply
Definition 3.1. = and qº denote the parental configuration probabilities and conditional means estimated over S. Let s 1/V(TT q² o (1 - (1-q²)). Throughout this paper, for vector v E IR"", we use i E Thmm to denote u o s. In particular, we have X, = X, o a (and similarly D. 4. f(x, q))
Now we analyze the concentration bounds for f(X, 9). Formally, we prove the following lemma.
Lemma 3.2. Assume the conditions in Section 2.3 hold for the original set of good samples G Then, for 81 = evlog I/c and 82 = e elog(1/e)) the set of samples {f q)} vea. is
e, 0
81
+e 11 ( allb) o
82 + )B) -stable,
Vac
ac
where B = PP o (p- 1)
We provide some intuition for Lemma 3.2 and defer its proof to Appendix B.
For the first moment, the difference between E[f(X, q)] and the empirical mean of q(),g) comes from several places. Even if = p, we would incur an error of 6, from the concentration bound in Equation equation 3 which is at most ó1 (ac)-1// after the scaling by s. Moreover, on average T fraction of the samples gives us information about (p- k. Since an e-fraction of the samples are removed when proving stability, we may only have (= P c)-fraction instead, which introduces an error of é ||ø - 2112- This is why the first-moment parameter is (ac()c) 112 + e |1ğ 3ill)).
(ac)-1/2
Ideally, we would like to prove Covif(X g)] = + (I o (p- (T (p- - 1)) but this is too good to be true. For two coordinates k * f, whether sample gives information about (Đ-q)ı (p- -); is not independent. We can upper bound the probability that both parental configurations happen by min( .t() ). If they were independent we would have a bound of x P Tp. The difference in these two upper bounds is intuitively why VT appears in the second-moment parameter. See Appendix B for more details.
For the second moment, after the scaling, we have Cov[f p)]
Robust Mean Estimation with Sparse Input. To overcome the second difficulty, we exploit the sparsity of the expanded vectors. Observe that each vector f(X. q) is guaranteed to be d-sparse because exactly d parental configuration can happen (see Definition 2.2). The same is true for f(X,) q) because scaling does not change the number of nonzeros. Therefore, there are in total O(Nd) nonzero entries in the set of samples {f ((XXg))ees h)ss
We develop a robust mean estimation algorithm that runs in time nearly-linear in the number of nonzeros in the input. Combined with the above argument, if we only invoke this mean estimation algorithm polylogarithmic times, get the desired running time of ((N)).
7

---

Published as a conference paper at ICLR 2021
Lemma 3.3. Consider the same setting in Lemma 2.6 Suppose ||X S R. all X E S. There an algorithm mmean with the same error guarantee that runs in time Ollog R. (miz(S)+N + where unz(S) is the total number of nonzeros in S. That is, given an e-corrupted version of an (e, B.7r)-atable set of N samples w.E.. a d-dimensional distribution with mean μxx, the algorithm Amean outputs an estimator jt E IR in time (log R (mnz(S) + N + d)) such that with high probability, || 2xl12 S OlVET + 3 +ee+eeooo <eolo 1/e)
We prove Lemma 3.3 by extending the algorithm in Dong et al. (2019) to handle sparse input. The main computation bottleneck of recent nearly-linear time robust mean estimation algorithms (Cheng et al.] 2018 Dong et al. (2019) is in using the matrix multiplicative weight update (MMWU) method. In each iteration of MMWU, a score is computed for each sample. Roughly speaking, this score in- dicates whether one should continue to increase the weight on the corresponding sample. Previous algorithms use the Johnson-Lindenstrann multaneously. We show that the sparsity of the input vectors allows for faster application of the Coanson-Lindenstenn lemma, and all N scores can be computed in time nearly-linear in nnz(S).
lemma to approximate the scores for all N samples si-
We defer the proof of Lemma 3.3 to Appendix C.
4 ROBUST LEARNING OF BAYESIAN NETWORKS IN NEARLY-LINEAR TIME
In this section, we prove our main result. We present our algorithm (Algorithm [ and prove its correctness and analyze its running time (Theorem 4.Ip.
Theorem 4.1. Fix 0 E Eo where en is sufficiently small universal constant. Let P be o-balanced Bayesian network on 13 with known structure H. Let a be the minimum parental configuration probability of P. Assume = (2(22(c-1/33)
Let S be an e-corrupted set of N 51m/2) samples drawn from P. Given H, c, c, and a, Algorithm 1 outputs a Bayesian network Q in time ((N)) such that, with probability at least 9/10, drv (P, Q) S. (l///oogl//e///e/ooooooo/o
Vac). Vac).
The e and a terms in the error guarantee also appear in prior work (Cheng et al. 2018). Removing this dependence is an important technical question that is beyond the scope of this paper.
Theorem 4.1 follows from three key technical lemmas. At the beginning of Algorithm I we first scale all the input vectors as in Definition 3.1 We maintain guess closer to p. In our analysis, we track our progress by the En-norm - for p and gradually move it (δ- qQ).
Initially, we set q to be the empirical conditional mean over S. Lemma | o (p- -1f0-")l 20)112 is not too large for our first guess. Lemma 4.3 shows that, as long as is still relatively far from p. we can compute new guess such that n (p- ( decreases by a con- stant factor. Lemma 4.4 states that, when the algorithm terminates and || o (p 11 small, we can conclude that the output Q is close to the ground-truth P in total variation distance.
proves that
11)l12
In the following three lemmas, we consider the same setting as Theorem 4.1 and assume the conditions in Section 2.3 hold.
Lemma 4.2 (Initialization). In Algorithm 7 we have
(p- O(eVd/Vac)
Lemma 4.3 (Iterative Refinement). Fix an iteration t in Algorithm ! Assume the robust mean
estimation algorithm Amean succeeds. If I| (p-18 r') -p-i'))l S p² and p = [(ee/log(1/e)) Vac)) then we have | (p- -00 S cip² for some universal constant 01 <
Lemma 4.4. Let Q be Bayesian network that has the same structure as P. Suppose that (1) P is c-balanced, (2) a = Q(r + c/c), and (3) || o (p- 7)12 S r/2.. Then we have drv (P. Q) S r.
We defer the proofs of Lemmas 4.2
and 4.4 1.4g to Appendix and we first prove Theorem
Proof of Theorem 4.7
We first prove the correctness of Algorithm i
8

---

Published as a conference paper at ICLR 2021
Algorithm 1: Robustly Learning Bayesian Networks
Input :
The dependency graph H of c-balanced Bayesian network P with minimum parental configuration a, an e-corrupted set S of N (((m/²)) samples {X,}= drawn from P. and the values of e, and a.
Output: Bayesian network Q such that, with probability at least 9/10,
(P, Q) & O( (log(1/ /ax)).
Compute the empirical probabilities T where (i, - Prxes [lk Compute the empirical conditional probabilities q² where q¹ (i, a) = Prxes [X(i) = =1 I1:a]:
Compute the scaling vector 1/v(m> q o (1-
Let T (log d) and q" = q²:
Let p² = (/ Vac). (We maintain upper bounds of s.t. || (f 3 S pf for all 0
for t = 0 to 1 do
3r = =O(pp'/ /a), +
Solve robust mean estimation problem. Let =d=aa
3'))
- (1/s) (1/x5) g': p²+1 cap²:
return the Bayesian network Q with graph H and conditional probabilities q²:
The original set of N [mm (ogmm/e)e)))) good samples drawn from P satisfies the conditions in Section 2.3 with probability at least 20 With high probability, the robust mean estimation oracle Amean succeeds in all iterations. For the rest of this proof, we assume the above conditions hold, which by union bound happens with probability at least 9/10.
From Lemma 4.2 we have the following condition on the initial estimate yº.
P (p 19) = O(cVa/Vac)
We start with an upper bound 0 of | o (p - - -(cV/ By Lemma 4.3 in each iteration, if p' a( /ogl//og///e///// /cc). we can obtain new estimate q and an upper bound p*+1 on || P o (p- l such that p²+ is smaller than p² by constant factor. Hence after (llgg(d)
iterations, we can get vector 7¹ such that
- r3) O(ev/o////)/// =
Let Q be the Bayesian network with conditional probability table q'. The assumption that a ((62/36-1/3) allows us to apply Lemma 4.4 with r O(e//oo(L//e) Vac), which gives the claimed upper bound on drv (P.v(P,C)) Q).
Now we analyze the runtime of Algorithm First, g and ~ can be computed in time Ö(Nd) because each sample only affects d entries of We do not explicitly write down f(X,)) q). In each which takes time iteration, we solve a robust mean estimation problem with input { {f(X,, (z) "ES"
Ö(Nd). This because there are N input vectors, each vector d-sparse, and the robust mean estimation algorithm runs in time nearly- linear in the number of nonzeros in the input (Lemma 3.3 We can compute gi+l v o (1/s) 1/75)
) + g² in time in time 0(m).
Since there are Olog d) iterations, the overall running time is
Ō(Nd) O(log d) (ō(Nd) + +0m) Ö(Nd).
ACKNOWLEDGMENTS
Part of this work was done while Yu Cheng was visiting the Institute of Advanced Study. Part of this work was done while Honghao Lin was undergraduate student Shanghai Jiao Tong University.

---

Published as a conference paper at ICLR 2021
REFERENCES
P. Abbeel, D. Koller, and A. Y. Ng. Learning factor graphs in polynomial time and sample complex- ity. J. Mach. Learn. Res., 7:1743-1788, 2006.
E. Amaldi and Kann. The complexity and approximability of finding maximum feasible subsys- tems of linear relations. Theoretical Computer Science, 147:181-210, 1995.
A. Anandkumar, D. J. Hsu, F. Huang, and Kakade. Learning mixtures of tree graphical models. In Proc. 26th Advances in Neural Information Processing Systems (NeurlPS), pp. 1061-1069, 2012.
S. Balakrishnan, S. S. Du, J. Li, and A. Singh. Computationally efficient robust sparse estimation in high dimensions. In Proc. 30th Conference on Learning Theory (COLT), pp. 169-212, 2017.
G. Bresler. Efficiently learning Ising models on arbitrary graphs. In Proc. 47th Annual ACM Sym- posium on Theory of Computing (STOC), pp. 771-782, 2015.
G. Bresler, E. Mossel, and A. Sly. Reconstruction of Markov random fields from samples: Some observations and algorithms. SIAM J. Comput., 42(2):563-577 2013.
G. Bresler, D. Gamarnik, and D. Shah. Structure learning of antiferromagnetic Ising models. In Proc. 28th Advances in Neural Information Processing Systems (NeessNeeeee (NeurIPS), pp. 2852-2860, 2014.
C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing Bayesian networks. In Proc. 30th Conference on Learning Theory (COLT), volume 65, pp. 370-448, 2017.
T. M. Chan. An optimal randomized algorithm for maximum Tukey depth. In Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 430-436, 2004.
M. Charikar, J. Steinhardt, and G. Valiant. Learning from untrusted data. Proc. 49th Annual ACM Symposium Theory Computing (STOC), pp. 47-60. 2017.
M. Chen, C. Gao, and Z. Ren. Robust covariance and seatter matrix estimation under Huber's contamination model. The Annals of Statistics, 46(5):1932-1966) 2018.
Y. Cheng, I. Diakonikolas, D. M. Kane, and A. Stewart. Robust learning of fixed-structure Bayesian networks. In Proc. 32nd Advances in Neural Information Processing Systems (NewrIPS), pp- 10304-10316, 2018.
Y. Cheng, Diakonikolas, and Ge. High-dimensional robust mean estimation in hearly-linear time. In Proc. 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2775-2771, 2019a.
Y. Cheng, I. Diakonikolas, R. Ge, and D. P. Woodruff. Faster algorithms for high-dimensional robust covariance estimation. Proc. 32nd Conference Learning Theory (COLT), pp. 727- 757, 2019b.
Y. Cheng, I. Diakonikolas, R. Ge, and M. Soltanolkotabi. High-dimensional robust mean estimation via gradient descent. In Proc. 37th International Conference on Machine Learning (ICML), pp. 1768-1778, 2020.
Y. Cherapanamjeri, E. Aras, N. Tripuraneni, M. I. Jordan, N. Flammarion, and Bartlett. Optimal robust linear regression in nearly linear time. arXiv preprint arXiv:2007.08137, 2020a.
Y. Cherapanamjeri. S. Mohanty, and M. Yau. List decodable mean estimation in nearly linear time. In Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 141- 148, 2020b.
C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theor, 14(3):462-46) 1968.
K. L. Clarkson, D. Eppstein, G. L. Miller, C. Sturtivant, and S.-H. Teng. Approximating center points with iterated Radon points. Proc. 9th Annual Symposium on Computational Geometry (SoCG), pp. 91-98, 1993.
10

---

Published as a conference paper at ICLR 2021
R. Daly, Q. Shen, and S. Aitken. Learning Bayesian networks: approaches and issues. The Knowl- edge Engineering Review, 16:99-157, 2011. ISSN 1469-8005.
S. Dasgupta. The sample complexity of learning fixed-structure Bayesian networks. Machine Learn- ing, 29(2-)):165-1800 1997.
Depersin and G. Lecué. Robust subgaussian estimation of mean vector in nearly linear time. arXiv preprint
2019.
L. Devroye and L. Györfi. Nonparametrie Density Estimation: The L View. John Wiley & Sons, 1985.
I. Diakonikolas and D. M. Kane, Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv: /91 1905919,, 2019.
Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Being robust (in high di- mensions) can be practical. In Proc. 34th International Conference on Machine Learning (ICML), pp. 999-1008, 2017a.
1. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estima- tion of high-dimensional Gaussians and Gaussian mixtures. Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 73-84, 2017b.
I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical Gaussians. In Proc. 50th Annual ACM Symposium Theory of Computing (STOC), pp. 1047-1060, 2018.
I. Diakonikolas, G. Kamath, D. M. Kane, Li, A. Moitra, and A. Stewart. Robust estimators in high dimensions without the computational intractability. SIAM Journal on Computing, 48(2): 742-864, 864, 2019a.
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, J. Steinhardt, and A. Stewart. SEVER: A robust meta-algorithm for stochastic optimization. Proc. 36th International Conference on Machine Learning (ICML), pp. 1596-1606, 2019b.
I. Diakonikolas, W. Kong, and Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proc. 30th ACM-MIANS Symposium Discrete Algorithms (SODA), pp. 2745-2754, 2019c.
I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. List-decodable mean estimation in nearly-PCA time. arXiv preprint arXiv:2011.09975 2020.
Y. Dong. S. B. Hopkins, and J. Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. In Proc. 33rd Advances in Neural Information Processing Systems (NeurIPS), pp. 6065-6075. 2019.
S. B. Hopkins and J. Li. Mixture models, robustness, and sum of squares proofs. In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC), pp. 1021-1034, 2018.
P. J. Huber. Robust estimation of location parameter. Ann. Math. Statist,, 35(1):73-101, 03 1964.
Jensen and D. Nielsen. Bayesian Networks and Decision Gruphs. Springer Publishing Company, Incorporated, 2nd edition, 2007.
D. Johnson and Preparata. The densest hemisphere problem. Theoretical Computer Science, 6:93-107, 1978.
A. Klivans, P. Kothari, and R. Meka. Efficient algorithms for outlier-robust regression. In Proc. 31st Conference Learning Theory (COLT), pp. 1420-1430, 2018.
D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques Adaptive Computation and Machine Learning. The MIT Press, 2009.

---

Published as a conference paper at ICLR 2021
P. K. Kothari, J. Steinhardt, and D. Steurer. Robust moment estimation and improved clustering via sum of squares. In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). pp- 1035-1046, 2018.
K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS), 2016.
J. Li and G. Ye. Robust Gaussian covariance estimation in nearly-matrix multiplication time. In Proc. 34th Advances Neural Information Processing Systems (NeurIPS), 2020.
L. Liu, Y. Shen, T. Li, and C. Caramanis. High dimensional robust sparse regression. Proc. 23rd International Conference Artificial Intelligence and Statistics (AISTA7S), pp. 11144114211 2020.
L. Loh and M. J. Wainwright. Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses. In Proc. 26th Advances in Neural Information Processing Systems (NeurIPS). pp. 2096-2104, 2012.
G.L. Miller and D. Sheehy. Approximate centerpoints with proofs. Comput. Geom., 4348)-6477 2010.
R. E. Neapolitan. Learning Bayesian Networks. Prentice-Hall Hall, Inc., 2003.
A. Prasad, A. S. Suggala, S. Balakrishnan, and P. Ravikumar. Robust estimation via robust gradient estimation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(3): 601-627, 2020.
N. Santhanam and Wainwright. Information-theoreti limits of selecting binary graphical models in high dimensions. IEEE Trans. Information Theory, 58(7)4117-4134, 2012.
J. Steinhardt, M. Charikar, and G. Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. In Proc. 9th Innovations Theoretical Computer Science Conference (ITCS), pp. 45:1-45:21, 2018.
J. W. Tukey. Mathematics and picturing of data. In Proceedings ICM, volume 6, pp. 523-531, 1975.
R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1rXiv:1011.3027, 2010.
M. J. Wainwright and M. I. Jordan. Graphical models, exponential families, and variational infer- ence. Found. Trends Mach. Learn., 1(1-2):1-305, 2008.
M. J. Wainwright, P. Ravikumar, and J. D. Lafferty. High-dimensional graphical model selection using & reguulrrrd logistic regression. In Proc. 20th Advances in Neural Information Processing Systems (NeurIPS). pp. 1465-1472, 2006.
B. Zhu, J. Jiao, and J. Steinhardt. Robust estimation via generalized quasi-gradients. arXiv preprint 20X5 2020.
12

---

Published as a conference paper at ICLR 2021
A DETERMINISTIC CONDITIONS ON GOOD SAMPLES
In this section, we will first prove Lemma 2.3 then we prove that the deterministic conditions in Section 2.3 hold with high probability if we take enough samples.
Lemma A.1. For X P and f(X, p) as defined in Definition 2.2
we have
(i) B(f(X, = O.
(i) Cov[s(X,,)) - diag(= ope oppce (1 p)).
(iit) For any unit vector o E R"" we have Prx~p [|E f(X, 2 T] s 2exp(-12/2)
f(X. p)x=] for all [m]. Let k (i, a). conditioned on f(X,p) ())],,., .... f(X, p)k the event Tia may may not happen. A simple calculation shows that in both cases, we have Ex-r[[(X (xx = =0
Proof. We first claim that Ex~plf Px
For (t), we have [[f(X,p)] = x pp -pp---))p--ppp-ppppp
For (it), we first show that for any (t. + (j.b), we have (I af (X,, 0. For the case i = j. we can see at least one of II, and H1 does not occur, so f(X, (X.P)).f(X,p is always 0. For the case + J. we assume without loss of generality that > J. then we have P)j.. = O.
For all ai) E [m], we have B[f(X, = B. Pi,a) I[T = ThaPtt, - Pi,a)- Com- bining these two, we get Cov Cov[s(X,p) diag(= op 0 (1 pl).
For (tii), we recall that Ei-n vxJ(X, ()x for 1 S S m is a martingale, and we can apply Azuma's inequality. Note that |va| 2 (x) hence we have Prx-p || f(X,p) 2 T 2exp(_12/2 |(ul()) (exp(-T2/1
(x..)el((x.p,....... p).,.., f(X, = O, thus the sequence
The conditions in Equations equation Inmaationaand and equation 2 are proved in Lemma A.2 and the conditions in Equation equation 3 are proved in Corollary A.4
Lemma A.2. Let P be a Bayesian network. Let G* a 52(m (og((m/))) samples drawn from P. Let G and p be the empirical parental configuration probabilities and conditional
probabilities of P given by G Then with probability 1 1- T. the following conditions hold:
(i) For any subset T C. G* with [T] (1 22)N,, we have
NTT π p 50(c).
(ü)
TP (p p | 50
Proof. For (t), first consider the of T G* and fix an entry 1 < k S m in the conditional probability table. Because each sample is drawn independently from P. by the Chernoff bound, we have that when = (m)))/mm)))/²) |- - F < e holds with probability at least - T 7/m. Hence, after taking an union bound over k, we have that ||~T" - > < E holds with probability at least 1 - T. Now for a general subset T C G notice that removing O(e)-fraction of samples can change n by at most Oee) Thus, condition (i) holds with probability least 1
For (ii), for any A (i, a). note that p is estimated from T N samples. In these samples, the parental configuration 11, happens and the value of X; is decided independently. By the Chernoff
bound and the union bound, we get that when N 22(m log(m/r))/e3) lof - -pal I e/ s/ holds for every A with probability at least T. which implics
V G
V G. (p- -0) O(e).
Combining this with 1| G 1l Se, get that condition (ii) holds.
13

---

Published as a conference paper at ICLR 2021
To prove Equation equation B use the following concentration bounds for subgaussian distribu-
tions. Recall that a distribution D on R with mean i is subgaussian if for any unit vector o E Rd have PIæ=Dll(U, 1\ 2 e exp(-ct"), where is universal constant.
Lemma A.3. Let G be a set of d d-dimensional subgaussian distribution with mean μ and covariance matrix E 3 I. Here A N B means that B - A is a positive semi-definite matrix. Then, with probability T, the following conditions hold:
Di(ee /log 1/d)-2(d log(1/T))) samples drawn from
For 61 = ci /og 1/c) and d2 = ci(E log 1/e) where ei is an universal constant, we have that for any subset T C G* with [T) 2 N,)NN
Σ ST
(X2 - 1))
S 891
S 62
(4)
T
T
FET
/ is proved in Diakonikolas et al. (2019a). The proof for the general case where Σ < I is almost identical. In particular, the concentration inequali-
A special case of Lemma
A.3 where
ties used in Diakonikolas et al. (2019a) for subgaussian distributions still hold when Σ N (see,
e.g., Vershynin (2010))
From Lemma A.3 and 2.3 we have the following corollary:
Corollary A.4. Let G* be a set of N = 2((e 1/c)-2(m + log(1/7))) samples drawn P. Then, with probubility 1 - T, the following conditions to hold: For ô1 c2(e /lg 1/e) and 82 e1 (cc 1/c), where 01 is an universal constant, we have that for any subset c G with |T] 2 (1 2,)
1 T
| [F(x,P)((X.)) [T|
Σ f(X,,p) IE
50()))
- 50(6))
(S)
iET
where Σ Covlf(X, p)] diag(T" opo 21 p)).
B STABILITY CONDITION OF f(X,q) .))
In this section, we prove the stability condition for the samples f(X, q) (Lemma 3.2)
Recall the
definition of f(X,q) 4) from Definitions 2.2 and 3.1 We first restate Lemma 3.2
Lemma
3.2
Assume the conditions in Section 2.3 hold for the original set of good samples G
Then, for 8 = e /lg I/c and 82 = e log( 1/e), the set of samples {f(X 4) lea- is
(c,0( 81 + vellp-a0 (ill-(1l)) ( 82 Vac
+B+VB) -stable,
ac
where B - 1IV (p- Q)
We will prove the stability of f(X,q). The stability of f(X, N5.4) follows directly. We introduce a matrix CD.g which is crucial in proving the stability of f(X.9) Intuitively, the matrix Cp is related the difference in the covariance of f(X. p) and that of f(X,9) on the sample set D.
Definition B.I. For any D of samples (Xi)eD. define the following x matrix
CD.
Σ (1(X..)) f(X,, ((),))))((x..))) f(X..))) IED
[D]
Observe that for x E {0, 13dd with x & 1l, we have f(x, p)s = f(z g)x = 0. On the other hand, Ie for some to = (i, a), have f(. p)) f(x (xt pk) (2; 9k)) 9 Pk-
In the very special case where all parental configurations happen (i.e., a binary product distribution), would have CD (p- (p T. However, in general the information related to (p 9) is spread among the samples. We show that even though Cp does not have a succinct representation, can prove the following upper bound on the spectral norm of CD.q-
14

---

Published as a conference paper at ICLR 2021
Lemma B.2. |CD,qll2 - Ex Th (px q:))
Proof. For notational convenience, let C. = CD.g. For every S k, S m, we have
CCk.el (
(Pr (P) qs)(pe - qe) I min(frg =² 1(P= gi)(pe - -eel
(V gell
We can upper bound the spectral norm of C' in term of its Frobenius norm:
2
| s ||C|? Σ &
Σ k
( (pp(pe - xx)²) (T ( qe)²) s
Σ Th (pE - 9x)
The following lemma essentially proves the stability of f(X, q), except that in the second-order condition, we should have (ov( .)) instead of Σ. We will bridge this gap in Lemma [..4|
Lemma B.3. Assume the conditions Section 2.3 hold. For d1 = t /loog 1/c and 82 e log(1/e)
we have that for any subset T C G with [T] [I e)
Σ
-) -
4))
- 0 E ||p -411)) and
VET
Σ (((();,)) - 2 (p-p-)))((0)) (f(()) 9) - - o (p (p)) - Σ 50 B VB)
T
1ET
where B = VT o (p 9) | - - (p - 4)11 and Σ = diag(T" opo (1 p)) is the true.
covariance of f(X,p).
Proof. For the first moment, we have
(f(X..)) - (p-))))) -
T
iET
(f(Xt,)) 1(Xi,g) ((Xi,p) - = o (p o
-3) (p--)))
IE
2
<
f ((t,p)
+ |7
- ()
T (p 9))
I
ET
EE
f(X
+ || n P) (p 1)1 -66 +e 1p 91122)
SET
For the second moment, consider any unit vector u E Rm We have
1
1
T
f(xx,))(X..9))
0= [T]
(f(XX, u)
T
iET
SE
(U((..))))) (((xip)) ((Xi,g), o) -0(xxi) -[X,,x)
ET
(U((E))) o/ + (F(X..)) f(X..9). v)?)
T
ET
+2,
[T'
Σ (F(X))))
(
[T]
Σ
( f(X:,9),
15

---

Published as a conference paper at ICLR 2021
where the last inequality follows from the Cauchy-Schward inequality. Therefore, have
(xx0))
-5
T
iE
2
(Xx,)))((x..)))
-
iET
+
((x f(X..9))
ET
2
+
Σ EE
((X:)))((Xxp))
E(((x.)) - - -(X,, - 5(x,,9))
[
iET
S 62 + ||Cr,gll2 + +2 1+ 82 / |Crr o (02 +1Crrlll + vICrrall2)
Finally, we show that the second moment matrix the empirical covariance matrix of f(X,
[ (X:))(X is not too far from
f(X,, ()x,)))
Σ - ( - q) x (1--))]]
T
[T
iET
GET
2
Σ
o 9))
T (p)0l2 + T (p- - 2
T
EE
< 0 ((6) + +ellp alle) |TP o (p- 1)2 S 50 O -)11
Putting everything together and using Lemma B.2 conclude this proof.
The stability of f(X, 9) follows from the stability of f(X,g) (Lemma B.3
scaling all samples by
and replacing E with in the second-order condition using Lemma B.4
Lemma B.4. Assume the conditions Section
2.3 hold. Then after scaling. we have
$ - 7 111 $0(5)
ac
where E is the covariance matrix of f(X.p).
Proof. We recall that Tf p1 pk) 2 1 min(pk. p4) ?(ac). Because ||s||
0(1/ /ac), it suffices to show that
[[ov((s s(X,p)) - 71l2 0(c).
In other words, need show
| op -1 p) - (1 1 0())
Let O" and n be the empirical parental configuration probabilities and conditional probabilities of given by G We first prove that
n op G' o (1 (1-p3') -5 - 00 (1--9)][- = =
Note that || - 2 = O(e) and g - و < 1, so is sufficient to show that
0 o o o (1 (1- o S a (1 - +3) =0()).
16

---

Published as a conference paper at ICLR 2021
We have
n op o 0 (1-pp") x o -1-11)))
G
n op x or x G o (0 + +19) (p s3 o (p - - 1
Let n& denote the number of times that the event ΠI happens over G", and let ty be the number of times that X (x) = when II Iaaa happens. Because S is obtained by changing at most eN samples in G*, get
(P
Th N
lo eN
ny(ns + ENN
2ngeN
4c
n eN
n2
Nn - eN)
0.5NM
The last inequality follows from is S ni and nik - eN 2 0.5mz (because we assume the minimum parental configuration probability is (E))).
This concludes || opc (1-pe)) T o (1 -0000==0000))))) =0())
Similarly, in order to prove that
| o po (1 -1-1) -p) = σ pp о 01 (1-po)) O(t))
We just need to show || - (p p "0)) Il2 = Oe)), which is follows from (ii) in Lemma A.2
An application of triangle inequality finishes this proof.
We are now ready to prove Lemma 3.2
Proof of Lemma 3.2
By Lemma B.3 and the fact that ||0|| = O(1/Vac), we know that for any
subset T C G* with T (1 G we have
(f(X. ②) - - o ( 4))
S 0 61 Vac
+ +ellp- 4112) and
ITI
82 <0
Σ (f(X,) - o 1-(0-0))- i)) - p of -
1)) T
<
+ VB)
[T
ac
iET
where B= VT o (p- i) 2 and E the true covariance of f(X, p). This because the scaling
applied to all vectors on both sides of the inequalities, so we only need scale the scalars 61 and 82 appropriately.
We conclude the proof by replacing Σ in the second-order condition with I using Lemma B.4
C ROBUST MEAN ESTIMATION WITH SPARSE INPUT
In this section, we give robust mean estimation algorithm that runs in nearly input-sparsity time. We build on the following lemma, which is essentially the main result of Dong et al. (209))
Lemma C.1 (essentially Dong et al. (2019)). Given an e-corrupted version of an (e, 3, 7)-sbable set of N samples w.r.t. d-dimensional distribution with mean px. Suppose further that [| 2 S
for all X E there is an algorithm outputs an estimator P E Bd such that with high probability.
pxl12 O c//g +
Moreover, this algorithm runs in time ((nnz(S)) +N +NN+++++- a(ppx) + log R), where unz(S) is the total number of nonzeros in the samples in and T @gzz)) is the runtime of an approximate score oracle defined in Definition C.2
17

---

Published as a conference paper at ICLR 2021
Lemma C.I is different from the way it is stated in Dong al. (2019). This is because use
more concise stability condition than the one in Dong et al. (2019) We will show that Lemma C.1
is equivalent to the version in Dong et al. (2019) in Appendix C.1
The computational bottleneck of the algorithm in Dong ct al. 2019) is logarithmic uses of matrix multiplicative weight update (MMWU). In each iteration of every MMWU, they need to compute score for each sample. Intuitively, these scores help the algorithm decide whether should continue increase the weight on each sample not.
We define some notations before we formally define the approximate score oracle. Let AN = fw E RN 0 w; E wi = =} be the N-dimensional simplex. Given set of N samples X X and a weight vector w E AN. let plw) = |e Σ w,X,, and [(w) Tu Σ wi - (X I (w))) denote the empirical mean and covariance weighted by w.
Definition C.2 (Approximate Score Oracle). Given as imput set of N samples X1,..., XN E Rd, sequence of t + 1 = O(log(d) weight vectors w., w...... w' AN. and parameter > 0, an approximate score oracle Oopz outputs = = approxxtptiss (Tr) to each of the N scores
Ti = (Xi -)(0)) TU(X; - p(w²))
for
U cxp(a Σ/ I(w'))
trexp(a 2i E(w())
In addition, Oapz outputs scalar q such that
S 0.1g + 0.05 [[(w") 71|2 where q (E(w²) T,U).
These scores are computed using the Johmson-Linddestraass lemma. Our algorithm for computing these scores are given Algorithm 2
Let = Olog N log(1 (1))). = (log d), and Q Rexd be matrix with i.idd entries drawn from (O 1/r). Algorithm 2 computes an r x matrix
H-1
A A= Q P
E(w'))
(6)
2
where P.(Y) -1j))>E=0000
Ej=u Y 2 is degree-L Taylor approximation to eXp(Y).
The estimates for the individual scores are then given by
#. tr (AAT))
||(XX, p(w'))ll2
(7)
and the estimate for is given by
q = 77 1)
(8)
1=1
Algorithm 2: Nearly-linear time approximate score computation
Input: A set S of N samples XI,...,X X E Rdd sequence of weight vectors w ...,, w/
parameter a, and failure probability 5 > 0.
Let (log N log(1/5)) and L Ollo d): Let Q E xd have entries drawn i.i.d. from (0, 1/r): Compute the matrix A E Rx as in Equation equation 6
return N given by Equation equation and given by Equation equation g
The correctness of Algorithm
was proved in Dong et al. 2019).
Lemma C.3 (Dong et al. (019 With probability at least 1-8, 8, the output of Algorithm Sattisifess satisfies l gl 0.1g 0.05 w
/||2 and 1. 7al S 0. for all < & N.
18

---

Published as a conference paper at ICLR 2021
Consequently, only need to analyze the runtime of Algorithm Lemma C.4. Algorithm runs in time Ö(t (N + d mnz(S)) log
Proof. We first show that matrix A E R can be computed in time
Ö( (N d mnz(S)) log 1/6).
We will multiply each row of Q (from the left) through the matrix polynomial to obtain Let TT Rixd be one of the rows of Q and let E R be any weight vector. Observe that we
compute all (v" (X; - p(w))) N in time
Σ unz X + N (nnx((S) + N + d).
This is because compute u(w) and v² u(w) just once, and then compute v X, for every i and subtract o ((w) from it.
Then, compute
N Σ
v. )'E(w)= T
wx(Xx -(x)(x( a(w))
wi (v (X; - (X::-(w)))) x._
Σ wi (v (X: (x:=va(p) n(w)) u(wr)
as the sum of N sparse vectors subtracting a dense vector in time ((nnx(S) N + d).
Therefore, for any R", evaluate e' Σ x== E(w") in time O(t (nnz(S) + N)).
Because Pt is a degree-f matrix polynomial of Σ D E(w*), we can use Horner's method for poly- nomial evaluation to compute T P: C
time (m(tt We need multiply each of rows of through, we can compute A in time O(r e (nnz(S) d N))-
remains to show that (7)) and i as defined in Equations 7 and can be computed quickly. Note that tr(AAT) is the entrywise inner product of A with itself, so it can be computed in time O(rd). The vectors (A(X, ((w*))) can be computed in time O (r C unz(X,) + d)) O(r (unz(S) + d)), because each AX, x can be compute time (nn(Xn)())) and Ap(w") can be computed only once in time (rdd). Because O(r (nnz + d)). Given the T, 's, q can be computed in O(N) time.
Ollog N log(1/8)).
compute all 7; in time
Recall that Ollog N log(1/8)) and l O(log d). Putting everything together, the overall runtime of the oracle is
( (nnz(S))
+0 (nnz N) ((tt(nnz((S) + ((nz((n()))+))))) log((/8)) -ogg///1)( O
By Lemma C.4 and the fact that O(lo d) and 1/ poly(d), we can implement an approxi-
mate score oracle that succeeds with high probability and runs in time Ö(mnz(S) + N + d).
Lemma 3.3 follows from Lemma C.I and the correctness and the runtime of the approximate score oracle (Lemmas C.3 and C.4 (Note that we have nnz(S) = Nd, N = N, and d = m when invoking these lemmas.)
and
C.1 PROOF LEMMA
In this section, we will show the equivalence between Lemma C.1 and Lemma C.6 Lemma C.6 a restatement of the result of Dong et al. (2019) using their stability notations.
We first state the stability condition used throughout Dong et al. 2019).
Definition C.5 (Dong et al. (2019)). We say a set of points is (e,7),2.,2 31.32 with respect to distribution D with true mean I if the following two properties hold:
19

---

Published as a conference paper at ICLR 2021
Il(()) - 2l12 s m, | Eies (X, (Xs)) - -(()) - 1/ 92
For any subset T C S so that [T|
-2e|51, we have
X
- 31,
Σ IET
(X,
S 3
T
IT
Then, Dong et al. (219)) showed the following result.
Lemma C.6. Let D be distribution
Rd with unknown mean μ.. Let 0 < < 60 for some universal constant Eg. Let S be a set of N samples with S = S, U U.A,S, where |Sp], |S.| I e|S), and Sg is (e, 72:72: 31, 32) -good with respect to D. Let Sapz be approximate score oracle for S.
Suppose || 1l I R for all X E S. Then, there is an algorithu QUEScoreFilters, Oapz. 6) that outputs fa such that with high probability,
[1 1122 - Olcvlog 1/c+ V + m)),
where
{ 12 + 2 + 4c2 + 2r32 + OOclog
Moreover, QUEScoreFilter (log R Rogg d) calls the score oracle O Oapz- and the rest of the algorithm runs in time (N log(R))
We first show the connection between our stability notion (Definition 2.5 and theirs (Definition C.5
Lemma C.7. Fix a d-dimensional distribution D with mean μ. if a set of N samples is (c, 3) stable with respect to D, then S is (c, B, 7/,,,// + 352 / ]-god with respect to D.
Proof. For any subset T C with [T] = 2e|S], we have
Σ
X1
1
Σ
X,
2e 1
1
Σ
X;
2E -1
1
T
T
[
EE
2
iES
iESYT
2
(1 2c)
Σ
X3
X; H
2E
N
2e
(1 - 2c)
iES
iESYT
1
1
Σ
X;
+
2c
1
Σ
X, p
2c
N
2c
1
iS
iESTT
1
3
<
3
26
2c
The last line follows from the assumption that S is (c, -sta-s with respect to D. Similarly, we have
(x - -Xx= -R)
T
IET
(X: -
-1) -1) (1-2c)
Σ (Xi-)((X;- - -M)T -1)
2x
(1-2c]N
VESiT
1 2
Σ
-- (X, -)()) -M) -1
1-2c
Σ (1)+)((x--) TTT -1
2
[T-2,
iES(T
1 1 7
<
7
+
26
26
20

---

Published as a conference paper at ICLR 2021
Notice that
(X (X)=
T
ET
Σ
(X; (X)x- -M) + ( -u-pic (u--m())(a-u(90
iEr
Σ
- (1 ( ((S))²
+ (1+ (s))
T
FET
GET
Combining the above two inequalities, by the triangle inequality, we get
Σ (x Xx: - (()) - v(S))
- ||
28 u(S)
11 ((5)
FET
2
3,2
22
When S is (c, -)stable by Lemma C.6 know that S is (c,71 B, = 77,8 3/c,
7/c + 3,2 ( )-goo.. The parameter g in Lemma C.7 is
{ = 3- + 6,32 +,3
and error guarantee Lemma needed in Lemma C.6
C.7 translates to V + O(ver+ which is exactly what
D OMITTED PROOFS FROM SECTION 4
In this section, we prove the technical lemmas in Section 4 We restate each lemma before proving
Lemma 4.2 states that the (scaled) initial estimation is not too far from the true conditional proba- bilities p.
Lemma Consider the same setting as in Theorem 4.1 hold. In Algorithm 7 we have
Assume the conditions in Section 2.3
T o - - OleVd//ac)).
Proof. Recall that qº = ds the empirical conditional probabilities over S, and ē u where is the scaling vector with || I (ac)
Let G and g be the empirical parental configuration probabilities and conditional probabilities given by G
We first show that
T S 2d
Let n and n denote the number of times that 1Ig happens G* and Note that changing one sample in G can increase or decrease n by at most 1. Moreover, in a single sample, exactly parental configuration events happen, so changing sample can affect at most 2d G+ 's. Since S is obtained from G* by changing cN samples, we have In n I cN for all k. and Ex In
ng! < 2edN. Together they imply [ - I 2d
By a similar argument, we can show that
G o ooD
n
S ed
because G " " is the probability that IT happens and X ((k) 1 over G
21

---

Published as a conference paper at ICLR 2021
By the triangle inequality, have
I (p - ,8)111 T opc 7 o g n-00 - s 33vd.
Using the condition in Equation equation get
from Section 2.3 ie.,
-p)l $ O((),, we | (p"--p)<
(p g²)
O(vvd).
Now by Equation equation 2 from Section 2.3 and the assumption that the minimum parental con-
figuration probability min; T a = (e))), we have के S + O(e) s O (0((') ) and hence
| p (p- - 18)6 s ((evd).
After scaling by 8, we have
n (p - s O(eVa//ac))
Lemma 4.3 | o (p-
shows that, when g is relatively far from p. the algorithm can find a new q such that 2 decreases by a constant factor.
Lemma 4.3 Consider the same setting as in Theorem 4.1 Assume the conditions in Section 2.3 2.3 hold. Fix an iteration t in Algorithm] 7 Assume the robust mean estimation algorithm m succeeds. If || o (p 40)1l2 S p² and p² = (( /lo///////////////////////////// Vac). then we have
|| - 10 S eap'
for some universal constant C1 <1
Proof. We assume p' > co(e/log(1/))//a)) and esc for some sufficiently large universal constants C4 and cs.
Because | o 12)112 S p², Lemma 3.2 shows that {f(x)9') Jier. is
< EvVlog// Vac
1/e
2p0 a
e log 1/e
+ (0')² v ( stable.
ac
By Lemma 3.3, the robust mean estimation oracle Ameans which we assume to succeed, outputs E R. such that, for some universal constant C3.
pt + +-pt + (Vlo((//))
||- x ( - -0--4))l2 c3
V
a
vac
C3
C3
C3
p:
06
From Section 2.3 we have ||
n TPI 0
= Oc)). which implies
[| ) 1')12 -
| o (p 10- r')ll2 =p'
By the triangle inequality, we have
|| S 10)12
C3
+
C3
C3
+
C3
p².
C5
Vai
c5
C4
Algorithm D sets g++1 = vo (1/Ts) + q which is equivalent to
x (p- g(+1) . (p 7³) v.
22

---

Published as a conference paper at ICLR 2021
Since || TP| 1=1 O(e) and Qt(c), have
-..² s 1.15%
VI visis..
Putting everything together, letting = 1.1
c
+
ca
ca+1
+
we have
vea
ca
+
|| - 1.1 |.1| o ( 2 <1.
cap
C5
C1
C5
c1
Because C₁ and C3 can be sufficiently large, we have c1 < 1 as needed.
Lemma shows that when the algorithm terminates, we can conclude that the output Q is close to the ground-truth in total variation distance.
Lemma 4.4 Consider the same setting as in Theorem 4.1 Assume the conditions in Section 2.3
hold. Let Q be a Bayesian network that shares the same structure with P. Suppose that (1) P e-balanced, (2) a = Q + e/c), and (3) || o (p 1)1l $ r/2. Then we have
drv (P. Q) Sr.
Proof of Lemma
4.4 We have (pk- + 9h (2 Pk - 9k) 2 Pa P&). Hence,
(px 92)
(px- 9%))
Σ
Th Th (pk (2 pk qu)
T Th
T
T Pk (1 pk)
k
From the proof of Lemma B.4 ((r). so we have
we know | p& (1 -pss)
= Oc)) and म pa (1 - -Px) 2 क Pe
ot
(pk- -4x)2
Σ
$ 1.1 Σ
T TH Th (pk 5
T Th
pp - pPk)
1.1 Σ
T Th mh (fr 9x)2
It suffices to show that mff T Q S which implies T Q 2 1.1Tg" and further implies
drv (P, Q) = o (p -)11
Let Ps: and Qsi be the distributions of the first i coordinates of P and Q respectively. We prove mnf" Q < r by induction on i. Suppose that for 1 S j i and all a' E {0, 13 |pppreeuts(]]) < r. Because that events IT only depends on j < i, IT - oda s drv (rv(Ps((-)) Q5(-1)) S r for all a. Consequently, we have (P, Q) = drv (Pe. Qua) Sr.
Q I r, then we have drv (P |T "'a''
23


Reviews:
[{"review_id": "vPKqjSkD-KV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the problem of robust learning of fixed-structure Bayesian networks under the eps-adversarial corruptions model. Fixed-structure means a known structure of the underlying Bayesian network. Robust learning is an important area of research and this particular question has been studied in prior work. The main contribution of this work is in improving the running time of the algorithm. On a d-node Bayes net, let m denote the total number of parental configurations possible. Prior work of Cheng et al showed a robust learning algorithm using O(m/eps^2) samples and runs in time O(md^2/eps^2).\nThe current paper reduces the running time to O(md/eps^2). The core subroutine is a robust mean finding algorithm for general distributions. A nearly linear time algorithm for this problem was recently given in the work of Dong et al which the current paper uses.\nThe ideas in the current paper use similar constructions to those of Cheng et al and seem to rely on the improvement in the running time of robust mean estimation provided by the work of Dong et al. Given this, I feel, although the paper has a clear improvement on a result for a specific problem it is a bit derivative.\n\nMinor typos:  \n1. Lemma 2.6: “these” -> “there”\n2. Page 6: intuition for Lemma B.3 (should be Lemma 3.2?)\n\n\n\n---------------\nI thank the authors for their response. However, I am inclined to keep my rating after having read their response.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "v4w_neUeKSJ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\nThis work shows how to learn a ground truth Bayesian network where an\n$\\epsilon$-fraction of the samples are adversarially corrupted. The authors\nfocus on the fully observable case when all the variables are binary and the\nunderlying graph is given to the algorithm. The main results in this paper are\n(1) a nearly-linear time algorithm for this problem with a dimension-independent\nerror guarantee, and (2) a direct connection between robust mean estimation and\nlearning Bayesian networks. The authors achieve this by extending the robust\nmean estimation algorithm of [Dong et al., NeurIPS 2019] to handle sparse input.\n\n**Strengths**\nThis paper is technically very strong. Learning Bayesian networks is becoming\nan increasingly important problem, as is the need for robust algorithms. One of\nthe main contributions in this work is the direct connection to robust mean\nestimation, which has received a flurry of attention in the past several years.\nMinimizing the spectral norm of the covariance matrix (as opposed to trying to\nmake it diagonal) is also a nice deviation from [Cheng et al., NeurIPS 2018].\nThe well-planned presentation of the results is an added bonus.\n\n**Weaknesses**\nWhile this is primarily a theory paper, a set of accompanying experiments would\nbe nice. Applications of learning Bayesian networks could also be discussed in\nmore detail in the introduction of the paper.\n\n**Suggestions**\n- [ 1] Typo: \"corruption\" --> \"corruptions\"\n- [ 2] Typo: Extra parenthesis at the end of Theorem 1.2.\n- [ 2] Typo: \"previous work\" --> \"previous works\"\n- [ 2] Typo: \"Previous algorithm\" --> \"Previous algorithms\"\n- [ 2] Typo: \"either has\" --> \"either have\"\n- [ 3] It might be helpful to use 'n' instead of 'N' for the number of samples.\n- [ 3] Typo: X \\in \\R^{N \\times d} should be X \\in \\R^{d \\times N}.", "extra_scores": {}, "extra_text": {}}, {"review_id": "6Hw0ss2Dq4K", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of robustly learning fixed structure Bayesian networks in nearly-linear time. Previous work by Cheng et al. gives a runtime of O(Nd^2/eps). The paper improves this to O(Nd). The algorithm works by directly relating the problem to robust mean estimation, and then leveraging the algorithm of Dong et al. for robust mean estimation which works in nearly-linear time. The authors have to modify the runtime analysis of the algorithm of Dong et al. to work in time linear in the sparsity, rather than dimension.\n\nI found the current contribution to be a bit limited. The connection between robust mean estimation and robustly learning Bayesian networks is already made and leveraged in Cheng et al. The new contribution here is to show that robust mean estimation can be used as a black-box. This is done by showing that the recent stability condition established to be sufficient for robust mean estimation can be satisfied for robustly learning Bayesian networks by scaling the moments by empirical estimates, for example scaling the covariance to be identity.\n\nOnce the reduction is established, the the paper leverages the algorithm of Dong et al. for robust mean estimation. However, the vectors arising in learning Bayesian networks are sparse, but Dong et al. does not exploit this sparsity. Dong et al. does run in time linear in sparsity, except for calls to a score oracle. The scores are computed in Dong et al. using the JL lemma. This papers shows that this part can also be done in time linear in sparsity. A lot of work has shown that JL style dimensionality reduction can be done in  input sparsity time, I don't see why these cannot be directly applied here (for example Clarkson-Woodruff, \"Low Rank Approximation and Regression in Input Sparsity Time\")?\n\nI think if the authors can extend the results and the proposed black-box reduction/input sparsity time robust mean estimation to apply to other regimes of robustly learning Bayesian networks, or some other problems, then it would be interesting. I also think that it would be good if the paper had experiments to back the algorithm---it would especially make the paper more interesting and relevant to the ICLR audience. Note that the algorithms of both Cheng et al. and Dong et al. are practical and the papers have experimental evaluations. If the authors can show that their algorithm empirically improves on the performance of Cheng et al. and other approaches that they compare to, then that would make the paper stronger.\n\n----------Update after author response----------\n\nI thank the authors for the detailed response. I think the fact that the near-linear time JL approach follows more or less from previous work needs to be clearly mentioned in the paper. I also think some experiments would be nice, and it would be reasonable to use some of the heuristics which the authors suggested, and sparse JL can often be reasonably efficient in practice. In light of all this I am keeping my score, but would encourage the authors to perhaps further pursue these directions.", "extra_scores": {}, "extra_text": {}}, {"review_id": "1d_yrxS0zsF", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "OVERVIEW\n==============\n\nThis paper studies the problem of learning Bayes nets using adversarially corrupted data. The model is that $N$ samples are made from a Bayes net on d nodes, out of which an unknown $\\varepsilon$ fraction are changed arbitrarily. The structure of the Bayes net is already given, but it remains to learn the probability distribution.\n\nWhen there are no corruptions, it is well known that in $O(N)$ time (for sufficiently large $N$), one can estimate the Bayes net upto TV distance $\\varepsilon$. This is without any extra assumptions.\n\nIn this paper, it's shown that in the above corruption model, there is an algorithm requiring $\\tilde{O}(Nd)$ time that learns the Bayes net within TV distance $\\varepsilon \\cdot \\sqrt{\\ln(1/\\varepsilon)}$. However, they also require two extra assumptions of \"balanced\"-ness and \"minimum parental configuration probability\". The previous best running time (under the same assumptions) was $\\tilde{O}(Nd^2)$.\n\nThe key contribution of the work is that they show a clean reduction to robust mean estimation. Unlike previous work on this problem, they make their algorithm super simple and natural, at the expense of making their analysis somewhat more complicated.\n\nTechnically, there are two new innovations compared to the earlier work. The first is a data-adaptive scaling which allows them to prove a certain stability property of an expanded conditional probability table. The second is a speed-up for robust mean estimation that runs in time nearly linear in the number of nonzeros in the input.\n\nEVALUATION\n============\n\n(There is a technical point which seems to be not discussed. In Lemma 3.2, what if s blows up to infinity because q^S at some particular (i,a) is almost 0 or 1? I don't believe this is a fatal issue but it should be clarified.)\n\nPositives:\n* solves a natural high-dimensional inference problem in the robust setting \n* improvement to the running time uses nice ideas that may have other applications\n* paper is well-written\n\nNegatives:\n* Given that this is ICLR, I'd have liked to see some experiments validating the improvement in runtime.\n* The assumptions are taken completely for granted in this paper, while they are very artificial and clearly not needed in the non-robust setting. I'd have liked more discussion as to why they are necessary for the analysis (perhaps, a counter-example which makes a step in their analysis fail?)\n\nOverall, I am in favor of accepting the paper.\n\nMORE DETAILED COMMENTS\n========================\n\n* Page 1, second para of intro: I'd change \"fundamental\" to \"simplest\". One could argue structure learning is more 'fundamental'.\n\n* Page 1, next-to-last para: Actually, Dasgupta doesn't exactly use the empirical estimator. He \"shifts\" the empirical distribution so that probabilities are bounded away from 0 and 1.\n\n* Page 4, second para: Balancedness is in fact not necessary for closeness in conditional probabilities to imply closeness in the global distribution (this is why Dasgupta's analysis works)\n\n* Page 6, second para: S is not defined here. Mention that it's the set of corrupted samples.\n\n* Page 7, Lemma 4.3 and elsewhere: Please change the > O(.) notation to > \\Theta(.).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main contribution of this paper is a nearly linear time algorithm for learning Bayesian networks with a known structure when an epsilon fraction of the samples are contaminated. The model assumes that the directed graph is known and the goal is to estimate a vector of length m that describes the conditional distribution of any node for any configuration if its parents. Let N be the number of samples and let d be the number of nodes. Prior work gave an algorithm that runs in time N d^2 time. This is now improved to roughly Nd time under natural conditions on the "balancedness" and the "minimum parental configuration probability". The algorithm itself is simple, and is a more direct reduction to robust mean estimation. 

The reviewers had somewhat differing opinions. The pros are that it's a basic problem, the algorithm is clean and the ingredients in the improved running time could have further applications. The negative is that there are no experiments, even synthetic ones, to demonstrate practicality. Overall it still seems that there is enough excitement about the work to merit acceptance. 
Decision: Accept (Poster)