Learning Juntas under Markov Random Fields
Authors: Gautam Chandrasekaran
Adam Klivans
Venue: NeurIPS 2025 poster ()
Keywords: pac learning
learning juntas
smoothed analysis
ising models
markov random fields
Primary area: theory
TL;DR: We give a polynomial time algorithm for learning $O(log n)$-juntas over smoothed Markov Random fields

Abstract: We give an algorithm for learning $O(\log n)$ juntas in polynomial-time with respect to Markov Random Fields (MRFs) in a smoothed analysis framework, where only the external field has been randomly perturbed.  This is a broad generalization of the work of Kalai and Teng, who gave an algorithm that succeeded with respect to smoothed *product* distributions (i.e., MRFs whose dependency graph has no edges). Our algorithm has two phases: (1) an unsupervised structure learning phase and (2) a greedy supervised learning algorithm. This is the first example where algorithms for learning the structure of undirected graphical models have downstream applications to supervised learning.

Learning Juntas under Markov Random Fields
Gautam Chandrasekaran gautamcêcs. utexas. edu UT Austin
Adam R. Klivans klivans@utexas edu UT Austin
Abstract
We give an algorithm for learning O n) juntas in polynomial-time with respect Markov Random Fields (MRFs) in smoothed analysis framework where only the external field has been randomly perturbed. This is a broad generalization of the work of Kalai and Teng, who gave an algorithm that succeeded with respect to smoothed product distributions (i.e., MRFs whose dependency graph has no edges). Our algorithm has two phases: (1) an unsupervised structure learning phase and (2) greedy supervised learning algorithm. This is the first example where algorithms for learning the structure undirected graphical models have downstream applications to supervised learning.
Introduction
function f [0, - {0, is k-junta if it depends only & of the input coordinates. The junta learning problem, introduced by Blum and Langley [Blu94, BI.97] in 1994, is as follows: given random samples labeled by an unknown k-junta, output classifier that closely approximates the k-junta. The problem of learning k-juntas is one of the most well-studied problems in computational learning theory over the last three decades. is considered notoriously difficult challenge to learn juntas with runtime and sample complexity n (K) and has important applications in pseudorandomness and cryptography (e.g., [ABW10))
The problem of learning juntas highlights the difficulty of designing learning algorithms that can succeed in the presence of a large number of irrelevant features (i.c., the n k irrelevant coordinates). Most prior work has focused on learning juntas when the marginal distribution is uniform over the hypercube. Observe that a brute force search over all subsets variables is possible in time ((?)), In the search for faster algorithms, [MOS04, Val12] gave algorithms that run in time approximately 0.7k 0.6k respectively when given uniform random examples. There is evidence to suggest that a runtime of n (k))) unavoidable, as there is a lower bound of (?) in the statistical query (SQ) framework of Kearns [Kсa93] and also cryptographic lower bounds [ABWIO] 10]. It is major open problem to find an algorithm for this problem with run time and sample complexity (o())
1.1 Beyond the Worst Case: Smooth Product Distributions
To bypass the above hardness results, learning juntas has been studied in the smoothed analysis framework of Spielman and Teng [ST04]. In particular, Kalai and Teng [KT08] introduced the notion of a (c, σ smooth product distribution, which is a product distribution with mean vector of the form = ū + A where fi E [-c, c)" is adversarially chosen and A is randomly sampled from the uniform distribution on [-a, a I" Under these smoothed distributions (with high probability over the smoothing), they showed that it is possible learn depth decision trees in time poly nn)
'the generalization is in distributional assumption, Kalai and Teng's result also gives a polynomial time learning algorithm for log-depth decision trees. "A similar statement for juntas also observed in [MOS04], see Fact 15
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The main takeaway from their result is that if the marginal distribution is slightly perturbed version of the uniform distribution, the task of junta learning becomes easy. This suggests that the lower bound for learning juntas is extremely brittle and that juntas are efficiently learnable over most product distributions.
A major drawback of all the aforementioned results is that they require the marginal distribution to be product. It is not clear how realistic this assumption is, as most real world data has interdependencies between variables. In [KST09], the authors asked if the smoothed analysis paradigm could be extended beyond product distributions.
We answer this question positively, and our main contribution an efficient algorithm for learning (log n) juntas with respect to Markov Random Fields (MRFs) with Ollog n1)-egree dependency graphs and smoothed external fields. This is a broad generalization of the Kalai et al. result, as (smoothed) product distributions correspond to trivial MRFs where the underlying dependency graph has no edges.
1.2 Beyond Products: Markov Random Fields
The class of distributions we study undirected graphical models, also known Markov Random Fields. These models- most famously the Ising model- have played a central role in probabilistic modeling and statistical physies.
Definition 1.1 (Undirected Graphical Model). An undirected graphical model D with dependency graph G is a probability distribution over {0, 11"h such that for X D, X; conditionally indepen- dent of the remaining coordinates of X when the conditioning is on {X, (i. is an edge in G}.
By the Hammersley-Cliffor Theorem [CH71], every distribution satisfying the above property (with the additional assumption that the density is positive everywhere) has a density function of the following form:
Pr XX = 2] x exp x~D
Σ (EC(G)
)s(())
exp exp (v(x))
(1)
where t [n]. C(G) is the set of cliques of G and vs are functions that only depend the coordinates of x in S. Any distribution of the above form is called a Markov Random Field. The factorization d of D is a polynomial of degree at most d where d is the degree of G. The famous Ising model corresponds to the case when the degree of &a is two. The linear part of the polynomial vi is called the external field.
As mentioned above, these distributions strictly generalize product distributions. A product distribu- tion is a graphical model where the graph contains only isolated vertices. The uniform distribution corresponds to an MRF with factorization ei = O. An arbitrary product distribution corresponds to an MRF with linear function as the factorization.
Note that again, brute force algorithm running in time O(()) exists for learning juntas over MRF distributions. The question we investigate is runtimes of the form poly n) are possible for perturbed versions of these distributions. We show that this is indeed the case for the following notion of (A, -smoooh MRFs where the external field of an adversarially chosen MRF is perturbed.
Definition 1.2 ((a, A)-smooth MRF). Let X R and 10.1 Markov random field D is (a, s)-smooth MRF if the factorization polynomial of D, denoted by &b is of the form
(xx) = ((x)) +
A
where A, = log((1 + a:) for iid Unif a)) and ||0,5|| S for all E [n].
In the above definition, & is the factorization of the adversarially chosen MRF and the upper bound on the norm of its derivatives is a standard assumption. This can be interpreted as a multiplicative perturbation of the density function as we have that
Pr X = x| x XnD
Pr X
(1 + +0.7))

---

where D is the MRF with factorization R. We note that we only perturb the external field (as compared to perturbing all coefficients) of the adversarially chosen factorization polynomial in this model. We show that this mild perturbation is sufficient for efficient learnability. We also note that the bound || | S is a natural non-degeneracy condition and a generalization of the condition of p-biasedness (see Claim 2.4) which prior work [KT08, KST09, BDM20) assume for smooth product distributions. Markov random fields with such a bound on derivatives are sometimes referred to as bounded width models and are exactly the class of MRFs for which efficient structure learning (dependency graph recovery) results are possible [Bre15, KM17, HKM17, VMLC16, SW12].
1.3 Our Results
We now state our theorem on junta learning over smooth Markov random fields.
Theorem 1.3. Let D be labelled distribution such that the marginal distribution is (X, o--sooth MRF with a known dependency graph G of degree at most and the labelling function is a k-junna. Then, Algorithm 2 run with N = (p n., exp(Xdd + k)), 2 .a- 11))) samples from D, graph G and appropriately chosen threshold will run in time at most poly(n, N) and learn the junta exactly, with probability at least 1 8 over the samples and smoothing of D. In particular, for d, k S Ollog n) and X, a = O(1), the algorithm runs in polynomial time.
This addresses an open question raised in [KST09] about extending their smoothed analysis frame- work beyond product distributions.
Remark 1.4. In the setting where the dependency graph G is not known, one can first recover G using existing structure learners for bounded-degree MRFs [KM17, HKM17] and then apply our algorithm. The sample complexity and run-time of these algorithms are poly(n', 2^),, where I is the degree of the factorization polynomial of the MRF This preprocessing is required only once and can be reused across multiple supervised learning tasks with respect to the same distribution. We note that to the best of our knowledge, this is the first example where algorithms for structure learning graphical models have downstream applications to supervised learning.
Remark 1.5. Our result is also tolerant random classification noise as the underlying algorithm falls in the Statistical Query framework [Kea93].
1.4 Related Work
Learning and Testing Juntas The problem of learning jumtas was introduced by Blum and Langley [Blu94, BL97] in 1994. The first non-trivial algorithm for learning over the uniform distribution was given by Mossel, O'Donnell, and Servedio [MOS04] who improved the naive (?) runtime from exhaustive search to roughly n n.7kk, This run-time was improved by Valiant [Val12] to approximately n 0.6kk The n R(k) runtime is widely believed to be optimal for uniform distribution learning, as there are statistical query and cryptographic lower bounds [Kea93, ABW10). 10]. Another well studied problem related to juntas is that of junta testing. Here, the goal is to identify if an input function is junta, or far from one, where the algorithm is given query access. The first algorithm was given by Parnas, Ron and Samorodnissky [PRSO1] where they give algorithm for dictator (1-junta) testing. The first algorithm for k-junta testing was given by Fischer et al. [FKR + +04] and later improved to almost optimal query complexity by Blais [Bla08, Bla09].
Smoothed Analysis and Learning The study of smoothed analysis of algorithms was initiated by Spielman and Teng [ST04] to theoretically study the empirical success of the Simplex algorithm which has exponential worst case run time. Their framework has subsequently been applied to various settings to analyze the good average case performance of various algorithms which have intractable worst case performance. Applying this framework to learning theory, Kalai and Teng [KT08] gave a polynomial time algorithm for PAC learning Olog n) -dephh decision trees over smoothed product distributions. Kalai, Samorodnitsky and Teng [KST09] extended the idea to polynomial time algorithms for PAC learning DNF's and agnostically learning decision trees with random examples. Brutzkus, Daniely and Malach [BDM20] proved that the empirically successful ID3 algorithm efficiently learns juntas over these distributions. More recent work applying the framework of smoothed analysis to learning theory include [HRS20, HRS22, CKK 24].
3

---

Learning from Random Walk Examples A complementary beyond worst case model for super- vised learning is that of learning from random walk samples. This was introduced by Bshouty et al. [BMOS03] where they give a polynomial time algorithm for PAC learning DNFs when given correlated samples corresponding to consecutive steps of an appropriate random walk over the cube whose stationary distribution is uniform. An algorithm for agnostic (log ni)juntas in polynomial time over the same model was given by Jackson and Wimmer [JW09]. This framework was further generalized to MRFs by Kanade and Mossel [KM15] where they give polynomial time algorithm for learning (log -jjntas but require correlated samples from a rapidly mixing Gibbs random walk whose stationary distribution is an MRF. We note that our algorithm requires only i.id. samples from the underlying MRF
Learning Markoy Random Fields Starting with the work of Chow and Liu [CL68] on learning tree Ising models, the problem of learning graphical models has been studied extensively [WLR06, AKN06, BMS08, NBSSIO, TR14]. Bresler [Bre15] obtained the first efficient structure learning algorithm for Ising models over bounded degree graphs, although with suboptimal sample complexity. This algorithm was generalized to higher order MRFs by Hamilton, Koehler and Moitra [HKM17]. Vuffray et al. [VMLC16] gave the first algorithm for learning Ising models with near-optimal sample complexity but with suboptimal runtime. Klivans and Meka [KM17] gave the first algorithm that achieves both near-optimal runtime and sample complexity. Other recent related works on structure learning MRFs in various settings include [WSD19, GKK19, PSBR20, MMS21, DKSS21, DDDK21, BGPV21, GMM24, CK24].
2
Preliminaries
Definition 2.1 (k-junta). A function f:: {0, 1] - 0, is said to be a k-junnaa if there exists function g: [0, 11 + {0,1) 1} and set S C [n] with [S] = k such that f(x) == g(rs).
Given a graph G, we use (i( to denote the neighbours of i in G. Given a distribution D with random variable D, we use [[= to denote expectations over these variables. We drop the distribution and random variable from the subscript when it is clear from context. Similarly, given a set S, [s[[]] to denote the expectation over the uniform distribution the set S.
useful property that we require is that of 6-unbiasedness.
Definition 2.2 (Unbiased distributions). Let [o, 1]. A distribution D is said to be 8-unbiased if for all b {0, 1), i [n] and x: E (0, 1] 1-1, it holds that
Pr X: = X~D
Fact 2.3. Let D be an MRF factorizaion polynomial tb. Then, for i E [m] and x E [0,1]"-1 holds that PIx~D[X, = X- a(),b(z))
It is easy to see that the MRFs we consider in this paper are sufficiently unbiased (proof in Ap- pendix A).
Claim 2.4. Let D be a (a, -m-soo MRF for E R and a e (0, 1/2). Then, it holds that D is exp( X) -uniaased.
The following is a useful consequence of the unbiasedness property (proof in Appendix A).
Lemma 2.5. Let 8 E (0, 1). Let D be a 8-unbiased distribution. Then, for any sets S, T S [n]] such that S T = é and any y E {0, (0,15, E (0,1)11) it holds that PIx-D[XT = Xx s] > 8|
3 Algorithm and Analysis
Throughout this section, let f be the ground truth junta that depends on l bits. Let Dx denote the marginal distribution. The joint distribution over features and labels, denoted by D, is a distribution on (0. 1)" {0, 1), where (x, y) drawn from is obtained by sampling from Dx and setting y f(x).

---

3.1 Prior Work: Learning over Smooth Product Distributions
Before describing our algorithm for learning juntas over smooth MRFs, we first discuss the prior work on learning juntas over smooth product distributions [KT008, MOS04, BDM20] and explain how their algorithms work. Let D be a product distribution with B[r;] = μ4 + A, for all where A, uniform
in [-a,a]. o.. They first define the quantity (2) as T(i) = I. (a.y)> [vr.] B (2.,))-DU ER ED [st]]] for any index i E [n]] Observe that f can always be uniquely expressed as f(x) = Ij (z(==))) (x-;) variables. Also, 2; a relevant variable and only if gi is
where Si and h; depend on at most non-zero. They showed that
I(i) E[yæ:] Blyj B[xs]| B[a.] [[ a; 1] [x)( B(xa]]
[| ([ 21 -1-1
[ + (2 x; = - E[ (1 (z=
[=].](1 - B[a:]) TE (=))(<=_))]== [a. [((i))) 10: + -)-+))--
The first three equalities follow from the fact that f(z) = zz 9: +
The penultimate
equality uses the fact that x; is independent from r-; and hence (1 x, = 1] = E h/ (x_)) The last equality follows from treating the function 9, as a polynomial of degree at most h 1 and using the product nature of the distribution conclude that EII 2,] = Ilees
A.). Thus, to lower bound (i), it suffices lower bound g: ((1 + A)):)) Clearly, we have that (ii 0 for i that is not relevant as gi is the zero polynomial. For relevant i, they used the following lemma from [KT08] on anticoncentration of polynomials to show that ((i) 2 (a) )2k with probability at least 1 - 8 (for more details, see the proof of Lemma 11 in [BDM201).
Lemma 3.1 (Lemma 4 from [KST09]). Lel C, E R. Let p Rn + I be degree é multilinear polynomial p(xx)= = Eisice ((S) Iles Ti. Suppose there exists set S with |S| and [p(S) 2 Then. for iid x; ~ Unif([-o,00 it holds that
Pr (-Unii((-o,op0)) [lx(X)] (
So0 co.: .e] 2
Since 1(1) is sufficiently large for relevant indices, by taking empirical estimates of this statistic from poly((2/a))) samples, one can find the relevant variables. Then, given the set of k relevant variables, even a brute force algorithm (constructing a truth table for all 2 possible combinations) has sample complexity and runtime that only scales with poly(n, (2/o)*).
3.2 Learning Over Smooth MRFs: Our Techniques
The product structure was crucial in the previous subsection for two main reasons. First, it was used to argue that Blg; (x: is a polynomial in μ + A. Second, the independence of x; and x-; was essential in showing that (i) = 0 for irrelevant indices. The former important guarantee non trivial correlation for relevant indices, while the latter was essential for distinguishing relevant from irrelevant variables.
We now try to extend this approach beyond products. Henceforth, the marginal distribution Dx that we consider is (a, A) -moothh MRF (Definition 1.2) with factorization vb. By our definition of smooth MRFs, we will show with additional technical work that the first property (E[g:) is a polynomial in perturbations) from earlier is still qualitatively true when we move beyond product distributions. In contrast, the second (T(i)= and does not extend to general distributions. Non-product distributions inherently allow correlations between variables, so an index that is irrelevant to a junta may still exhibit non-trivial correlation with the label. As result, any algorithm that selects variables purely based on their correlation with the labels risks including irrelevant variables. To address this, we must go beyond the correlation statistic I (i).
for irrelevant variables) is more fundamentally tied to product structure
Before we can go further, we need some additional notation. A restriction is a string p E (0, 1, Let supp(p) denote the support of the restriction defined as supp(p) = fi E [n] P: * *}. The size of a restriction o denoted by |e| is the size of the set supp(p). Given a distribution D on (0. ) and a restriction p. the restricted distribution D, is obtained by conditioning D on the event {X; = ps. for all i E supp(p) ). Similarly, given a set S C {0, 1)" and restriction & E {0, 1,+). use Sp to denote the set Sp {o S
Pt. pr. for all j supp(p)). Given function
5

---

f 13 + {0.1} and restriction E +0,,, the restricted function fo is defined as ==())=((xp))
To go past the correlation statistic and design an algorithm for learning over MRFs, we use a key structural property of MRFs: the Markov property. Recall from Definition 1.1 that the variables dn; and T-i are conditionally independent when conditioned on (o())( where G is the dependency graph of the MRF. This property motivates the statistic of measuring correlation between æ; and y after conditioning by the neighbors of i. Formally, for E [T]] and restricting p E {0, + with supp(p) = (i). we define the statistic [ p) as I(i. == ED, [yz,] ED, [y] ED, [ where Dp the joint distribution conditioned the event that <p) Psupp(p)- Let R be the set of relevant variables for f. We show the following properties for the statistic [ p):
1. for all i & R, for all restrictions P with supp(p) No(i), it holds that I(i, = 0 (Claim 3.3),
2. for all E R. with probability 1 y over the smoothing of Dx. there exists a restriction with supp(p) Na( such that (i p)1 2 7² ((o (((ee()))/16)++++ (Claim 3.4).
The first claim follows almost immediately from the Markov property. The second claim requires more technical work as the MRF density quite complicated when compared to the product example sketched in Section 3.1. The proofs of these claims are in Section 3.3. Once we show these claims, the rest of the algorithm is almost immediate: we estimate these statistics empirically for all indices and all restrictions of their neighborhoods and pick the indices for which the statistic is large (Algorithm 1). We note that sampling from these conditional distributions (using straightforward rejection sampling) costs us an exp(Ad) factor in the sample complexity (where d is the max degree of the dependency graph).
Algorithm 1: FindRelevantVarriabeesSS G,
Input: Sample set S C 10, x {0, 1}. Dependency Graph G, Threshold т
Rel + Φ
3 for i
[r] do
for e {0, 1, *) such that sppp(p) No do
Is(i, p) +
Es, [vl Es, [z;]]
if 11 p)1 > r then
Rel < RelU (i)
end
end 10 end
Return: Rel
Algorithm LearnJunta(S, G.T)
Input: Sample set C (0. 1)" x f0, Dependency Graph G, threshold т
Rel -iiiieeeleaataaaiaallSSS.......
Find Empirical Risk Minimizer f out of all functions that only depend on Rel
Return:
Finally, brute force learner on these indices (Algorithm 2). This is where use the fact that these distributions are unbiased (Claim 2.4 and Lemma 2.5). More specifically, the brute-force learner requires (eep((Xk)) samples (owing to unbiasedness) indices. This implies our main theorem (proof in Appendix B). Note that the final hypothesis we output is exact and has zero error with high probability.
see all possible fixings of the relevant
Theorem 3.2. Let D be labelled distribution over {0, 13 10 such that Dx is (A, --smoothhh MRF with dependency graph G of degree at most d and the labelling function is a k-junta. Then, Algorithm run with N (pplly n, exp(X(d+k)) 2 -k 1/5) samples from D. graph G and uppropriately chosen threshold T will output a hypothesis ʃ such that ((os))=D # v] = with probability at least 1 d over the samples and smoothing of D.

---

3.3 Proofs
We now prove the two claims (Claim 3.3 and Claim 3.4). Recall that for each E [n]], we have that
fx) = D2
9:(2 (2- + (z-x.)). For any p E {0, 1, *] with supp(p) = -Na(i), we have that
E [gx]] 1
E
E
E
[f(x) z; = 1] [f)
E
[x,]]
D. D,
D.
Dp
D.
D.
D.
= |E I (x((x
21 = 1] 11 [x.]) + E [1,(x_)) 8i = =11 1] E [h. (2 (x= Pp
D,
We now use the Markov property. We have that for (zz 1) D, with supp(p) p) (1) it holds that xy and x-; are independent. Thus, we have that ED, [1, (x==)) I; = 1| En, (x= Thus, we
obtain that (1 p)l - 1 [..l.- (1
EE ( [x Dp
21 I]l
by [x.]] (1
[=:]]| Dp
E Dp
(xx(x)))
Dp
Recall that for indices i not relevant to f. we have that gi O. Thus, obtain the following claim. Claim 3.3. Let i E [n] be such that f does not depend on index For any restriction p with supp(p) = (i), it holds that T(i, =0
We are now ready to prove that for every relevant index i, there is restriction of its neighbours such that [(i p)] is sufficiently large. The first observation that it suffices to bound E,, [9<(x=;)] as the distribution Dx is unbiased. After this the proof has two main parts. First, we show by writing out the densities and using appropriate algebraic manipulations that this quantity is lower bounded by polynomial in the smoothing variables. Finally we use polynomial anticoncentration from Lemma 3.1 to complete the proof.
Claim 3.4. Lel i E [n] be such that I depends on index i. Then, there exists a restriction p with supp(p)= = (i) such that [[(i,p)] 2 7² exp(->))11) with probability at least 1 - over the smoothing Dx.
Proof. First, from Claim 2.4, it holds that xx is exp(-A) -unbiased. Since i supp(p), Lemma 2.5 implies that
exp(-A)
min [x, 1 (xx)) Dj
D
Thus, it suffices to lower bound ED, (x_.)) Since x; relevant, there must exist restriction p with supp(p) = No (i) such that the function (g:), is not the zero function (otherwise f() = h, is not dependent on xz)). We consider such a restriction p.
Recall that [(x) = 24 ;i( + (x Since ís function on & variables, both gi and h;; are polynomials such that any non-zero coefficient in both these functions is at least 2- in magnitude.
Thus, we have that [z)] *
= [g,(1) 2 l:
Let R be the set of relevant variables of f. Let R, be R (1).). R, \ No(1) = Φ. then it holds that (g)) a constant function with magnitude greater than 2 2-k Thus, combining with Equations (3) and (4), we have that ED, [yx:] - [E, LE,, [z:]] > 2 exp(-2A) Thus, it only remains to consider the case where Rg \ (o(1) # o. Let T: = R, \ NN( Observe that
(z))
Σ
1lrT. 2} h(2)
(5)
=E{0.1)12
where ((z) = 0 or [x(2) 2 k Since the marginal Dx is (A, o -smoohh, Dx has the factorization ((x) (x)) + +E Aar; where (2.)(z)) < İ and A log(1 + ax) for iid a; ~ Unif([-o, a)). Let D; be the MRF with
factorization vi (r) = (xx) - Σjer: Ajag. We have that
[g((x_.)) = Σ D,
Prier: = 2] h(2)
D
=E(O.1) m
Pro, [KT; = z]
Σ
Pr [AT, = 2] h(2))
(6)
Pr(D.), = 2] (D.),
=E(0.13 T.
7

---

We now derive an expression for the density ratio. Note that the distribution (D:)p does not depend on Âr. by definition. Let Qi denote the (i) T, For ease of notation, assume that the elements for (i) come before T. Let up = PNa(1) be the string of fixed variables of p. We have that
Pro, [T, =x] Pr(D.), (T. =
Exg, (w,,)) expp)))))
E E exp(Vi(x))
Exxole=w, exp(((x))
Σ Ezq, =(we))) exp(ti(x))
EaNot exp(Vi(x))
- exxp(
Σ Aszz) JCT;
EuNg()=u exp(v((x)
The first equality follows from the expression of the densities of Dx and D, The second inequality follows from the fact that (x) = ((x) Ejer; AjT, Note that the second term in the last expression does not depend on z. We give a lower bound on this term.
ENNowEE, exp(Pi(z)) Ex exp(<(xx))
2 min No
exp(di(x)- - xb(x))
min =
exp(
Σ4 2
(8)
JET;
The first inequality follows from the mediant inequality. The second follows from the definition of s); and the last follows from the facts that (I) exp(A,) S (1 + oo) S 2, and (2) [Til S
Now, combining Equations (6) to (8), we obtain that
E EZNgrEEE exp(v)(x))
E D,
Σ
exp
Σ A52z)
Pr [.T, = h1()) (D.).
Σ Ennoto m, exp(<b(x))
=E/0.1 TM
JET: 2No0 exp(vi(x))
Σ exp( Σ A5zz)
Pr (on, = =2))(2)) h(z)) (Di),
Σ Σ exp(b((x)
=E/0,13131
JET.
2 2
Σ exp
Azzj)
Pr (D.)
[.T, = x] h(z))
jET.
Define h to be the function h(2) = Pr(m.), [T,, = 2] h(2). Note that h does not depend on Ar, by
definition of D, Combining the fact that h(2) = or [n(2)] 2 2 and Lemma 2.5, observe that
π(=) = [==]] 2- k. expl Til)
oxp(-AR)
412,1
8
Recall that A, log(1 + as) for iid a; Unif([-o, a]). We obtain that with probability at least 1 -- over the choice of ~ Unif([-a,,a]) a)"), it holds that
E [l((==)))1 2
Σ
II (1 a,z;)) h(z) (
=E (2, JET:
The first inequality follows from the way A is sampled. The second inequality follows from Lemma 3.1 using the facts that (1) the expression on its left hand side multilinear polynomial in of degree at most & with maximal coefficient equal to [z(2)] > exp(-Ak) for some z, and (2) ag are sampled iid and uniformly from [-a,a).
8
Thus, combining everything together, we obtain that for any relevant variable i, with probability 1 7 over the smooth marginal, there exists a restriction p E 10, *1, such that supp(p) No(1) and it holds that
E. D.
[y.
E
E [x]] Dr
72 (exp(- Sesp-~XVn (000-))o16))+2
D.

---

Open Questions
natural open question is that of learning decision trees smoothed Markov Random Fields. Recall that Kalai and Teng [KT08] gave polynomial time learning algorithm for log r--eppth decision trees over smooth product distributions. Theorem 3.2 implies polytime learnability for Ollog log n)- decision trees (as every depth k decision tree is a 2 -junta,, however it is still open how to get all the way to depth Oloo n) Even more ambitiously, one might ask how to learn polynomial size decision trees or poly-size DNFs over smoothed MRFs. Note that there are polynomial time algorithms that learn these classes over smoothed product distributions [KSTO9].
Finally, an interesting question is if one avoid the explicit structure learning step in the algorithm. Is there a way to learn juntas over smoothed MRF's without learning the full structure of the distribution?
Acknowledgments and Disclosure of Funding
Gautam Chandrasekaran is supported by the NSF AI Institute for Foundations of Machine Learning (IFML). Adam Klivans is supported by the NSF AI Institute for Foundations of Machine Learning (IFML).
References
[ABW10] Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from dif- ferent assumptions, STOC 100 page 171-180, New York, NY, USA, 2010. Association for Computing Machinery.
[AKN06] Pieter Abbeel, Daphne Koller, and Andrew Y Ng. Learning factor graphs in polynomial time and sample complexity. The Journal of Machine Learning Research, 7:1743-1788, 2006.
[BDM20] Alon Brutzkus, Amit Daniely, and Eran Malach. Id3 learns juntas for smoothed product distributions. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 902-915. PMLR, 09-12 Jul 2020.
[BGPV21] Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and NV Vinodchandran. Near-optimal learning of tree-structured distributions by chow-liu. In Proceedings of the 53rd annual acm SIGACT symposium on theory of computing, pages 147-160, 2021.
[BL97] Avrim L. Blum and Pat Langley. Selection of relevant features and examples in machine learning. Artificial Intelligence, 97(1):245-22 1997.
[Bla08] Eric Blais. Improved bounds for testing juntas. In Ashish Goel, Klaus Jansen, José D. P. Rolim, and Ronitt Rubinfeld, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 317-330, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
[Bla09] Eric Blais. Testing juntas nearly optimally. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, page 151-158, New York, NY, USA, 2009. Association for Computing Machinery.
[Blu94] Avrim Blum. Relevant examples and relevant features: Thoughts from computational learning theory. In AAA/ Fall Symposium on 'Relevance, volume 5, page 1, 1994.
[ВМОSО3] N. Bshouty, E. Mossel, R. O'Donnell, and R.A. Servedio. Learning dnf from random walks. In 44th Annual IEEE Symposiun Foundations of Computer Science, 2003. Proceedings., pages 189-198, 2003.
[BMS08] Guy Bresler, Elchanan Mossel, and Allan Sly. Reconstruction of markov random fields from samples: Some observations and algorithms. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 343-356. Springer, 2008.

---

[Bre15] Guy Bresler. Efficiently learning ising models on arbitrary graphs. In Rocco A. Serve- dio and Ronitt Rubinfeld, editors. Proceedings of the Porty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14- 17, 2015, pages 771-782. ACM, 2015.
[CH71] P Clifforr and JM Hammersley. Markov fields on finite graphs and lattices. 1971.
[CK24] Gautam Chandrasckaran and Adam R. Klivans. Learning the model even at low temperature. CoRR, abs/2411.11174 2024.
[CKK+24] Gautam Chandrasckaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, and Konstanti- nos Stavropoulos. Smoothed analysis for learning concepts with low intrinsic dimension. In The Thirty Seventh Annual Conference on Learning Theory, pages 876-922. PMI.,, 2024.
[CL68] CKCN Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory, 14(3):6624477, 1968.
[DDDK21] Yuval Dagan, Constamtinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros. Learning ising models from one or multiple samples. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 161-168, 2021.
[DKSS21] Ilaas Diakonikolas, Daniel M Kane, Alistair Stewart, and Yuxin Sun. Outlier-robust learning of ising models under dobrushin's 's condition. In Conference on Learning Theory, pages 1645-1682. PMLR, 2021.
[FKR+04] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. Journal of Computer and System Sciences, 68(4):753-787 2004.
[GKK19] Surbhi Goel, Daniel M Kane, and Adam R Klivans. Learning ising models with independent failures. In Conference on Learning Theory, pages 1449-1469, PMLR, 2019.
[GMM24] Jason Gaitonde, Ankur Moitra, and Elchanan Mossel. Efficiently learning markov random fields from dynamics. arXiv preprint arXiv:2409.05284 2024.
[HKM17] Linus Hamilton, Frederic Koehler, and Ankur Moitra. Information theoretic properties of markov random fields, and their algorithmic applications. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[HRS20] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems, 33:9203-9215, 2020.
[HRS22] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adap- tive adversaries. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 942-953, 2022.
[JW09] Jeffrey C. Jackson and Karl Wimmer. New results for random walk learning. In COLT 2009 The 22nd Conference Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
[Kea93] Michael Kearns. Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC '93, page 392 401, New York, NY, USA, 1993. Association for Computing Machinery.
[KM15) Varun Kanade and Elchanan Mossel. Meme learning. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1101-1128, Paris, France, 03-06 Jul 2015. PMLR.
10

---

[KM17] Adam R. Klivans and Raghu Meka. Learning graphical models using multiplicative weights. 2017 IEEE 58th Anmual Symposium on Foundations of Computer Science (FOCS), pages 343-354, 2017.
[KST09] Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng. Learning and smoothed analysis. In Proceedings of the 2009 50th Annual IEFE Symposium Foundations of Computer Science, FOCS '09, page 395-404, USA, 2009, IEEE Computer Society.
[KT08] Adam Tauman Kalai and Shang-Hur Teng. Decision trees are pac-Icarnable from most product distributions: a smoothed analysis. arXiv preprint arXiv:0812.0933, 2008.
[MMS21] Ankur Moitra, Elchanan Mossel, and Colin P Sandon. Learning to sample from censored markov random fields. In Conference on Learning Theory, pages 3419-3451, PMLR, 2021.
[MOS04] Elchanan Mossel, Ryan O'Donnell, and Rocco A. Servedio. Learning functions of k relevant variables. J. Comput. Syst. Sci., 69(3):421-434, November 2004.
[NBSS10] Praneeth Netrapalli, Siddhartha Banerjee, Sujay Sanghavi, and Sanjay Shakkottai. Greedy learning of markov network structure. In 2010 48th Annual Allerton Con- ference on Communication, Control, and Computing (Allerton), pages 1295-1302. IEEE, 2010.
[PRSO1] Michal Parnas, Dana Ron, and Alex Samorodnitsky. Proclaiming dictators and juntas or testing boolean formulae. In Michel Goemans, Klaus Jansen, José D. Rolim, and Luca Trevisan, editors, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, pages 273-285, Berlin, Heidelberg. 2001. Springer Berlin Heidelberg.
[PSBR20] Adarsh Prasad, Vishwak Srinivasan, Sivaraman Balakrishnan, and Pradeep Ravikumar. On learning ising models under huber's ' contamination model. Advances in neural information processing systems, 33: 13227-17333338, 2020.
[ST04] Daniel A. Spielman and Shang- Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385 -63,, May 2004.
[SW12] Narayana P Santhanam and Martin Wainwright. Information-thhoreet limits of selecting binary graphical models in high dimensions. IEEE Transactions on Information Theory, 58(7):411744134 2012.
[TR44] Rashish Tandon and Pradeep Ravikumar, Learning graphs with a few hubs. In Interna- tional conference on machine learning, pages 602-610. PMLR, 2014.
[Val12] Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 11-20. IEEE, 2012.
[VMLC16] Mare Vuffray, Sidhant Misra, Andrey Y. Lokhov, and Michael Chertkov. Interaction screening: Efficient and sample-optimal learning of ising models. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29; Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2016.
[WLR06] Martin J Wainwright, John Lafferty, and Pradeep Ravikumar. High-dimensional graphi- cal model selection using & regularizzd logistic regression. Advances in neural infor- mation processing systems, 19, 2006.
[WSD19] Shanshan Wu, Sujay Sanghavi, and Alexandros G Dimakis. Sparse logistic regression learns all discrete pairwise graphical models. Advances in Neural Information Processing Systems, 32, 2019.

---

A Omitted Proofs from Section 2
Claim A.I. Let X E Let be an MRF with factorization polynomial vp such that for all i [n].
holds that ||0, I X. Then, D is expi- uuniiased.
Proof. From, Fact 2.3, we have that for all i E [n] and z E (0.1)"-1, it holds that
X-, = z| o (a,b(z)) 2 (1/2) exp(-A). Similarly, holds that Prx~D[X, = x-
1 1- (0, (1/2) exp(-X)
Proof of Lemma 2.5. From the definition of conditional probability, for any i E [nd], set R E [n].
b E {0, 1 and {0,1) it holds that
Pr [ = b XR -
Pr XND g IR
Σ
xx b Pr [x=; (r. Xn = r] X~D
X~D
(10)
where the first equality follows from expanding the probability and the second inequality follows from the fact that D is d-unbiased. In the first inequality, we assumed for ease of notation that the elements of occur before the elements of [n] \ (RU (i)).
Without loss of generality, assume that T = [[]]] Then, we have that
P PXT = Xs = s]
Pr I = X = 1R-1), Xs = 8) 2 SITI X <E[[T]]
II
X~D
where the last inequality follows from Equation (10).
Finally, we show that the smooth MRFs we consider in this paper unbiased.
Proof of Claim 2.4. Let the factorization of D be vxxx) xbxx) + Σ Art We have that
exp(0,e((x))
exp( - (0)bb(
Pr |X = X a| (0.0(x)) 1 exp((xv((x)) X~D
exp( exp(-18:0((z))) expl)))xxppp))))))
exp(-A) min(exp(-An))) Ai), exp(Ai))
2
exp(-A)(1-o) (1) exp(-A)
where we used the definition (a, A)-smooth MRF the last three inequalitics.
B Proofs from Section 3.3
We show that with high probability over the smoothing of the distribution, Algorithm run on sufficiently large number of samples will find all the variables participating in the junta.
Theorem B.1. Let 'D be labelled distribution over (0, 13" x {0. 1} such that Dx is a (A, am-mmooth MRF with dependency graph G of degree most d and the labelling function is a k-junta. Then, Algorithm run with N = (pplly (log n. cxp(A(d + k)), 2d+h oa-k 1/8) samples from D, graph G and appropriately chosen threshold will find the relevant variables of with probability at least 1
over the samples and smoothing of D.
Proof. We choose the thresholds T such that 27 = (6/(k24))2 (a (xxx(())116) Let f be the
k-junta generating the labels. Fix variable E [n]. We analyze the quantity from Algorithm 1. Recall from Claim 3.4 that with probability 1 1 8/2 over the smoothing of Dxx for all coordinates (i such that [[ p) 2T.
i that are relevant to f. there exists a restriction p with supp(p)
Moreover, from Claim 3.3, we have that I(i,, p) = for any that not relevant. Since [Nc(1] < d. for all i [m). the total number of restrictions enumerated in Algorithm is at most 2d for each i. Thus, taking union bound over all relevant variables and restrictions of their neighbours, Claim 3.4
12

---

implies that with probability at least 1 - 6/2 over the smoothing of xx, it holds that for all i E [n]] that are relevant, there exists restriction p with supp(p) (i) such that
2 ( (cropp(-))/16)== / = 2T. |s| required such that
(11)
We use concentration of measure to bound the number of samples with probability 1 - 6/2 over $ ~ DaN it holds that (Ts(i, p) T(i. p)] S for all i E [m] and restrictions P with supp(p) = Na(i). We prove the following claim.
Claim B.2. Let E [n] and p {0, 1, + with (supp()) S d. Then for N Q((1/²))
poly(2", exp(Ad)) 1og(1/7)), it holds that [s(i,p) - I(t, (() S t with probability at least 1
over S D&N
Proof. Let T = supp(p) and up Pr. From Lemma 2.5, it holds that Prx-D, [X, =pp 2 (x)p(-A)44j_ Thus, for N 2 poly(2", exp(Ad)) log(1/7). Hoeffding's s inequality implies that with probability 1 - 7 over 5 ~ D&N we have that |Sp 2 N (exp(- (8))_-)8880 Observe that the distribution of the S, is identical inequality, choosing Nº (2(1172) log(1/7)), it holds that (1) Ess [2x.] [x, S
sample from D, of size N, 1Spl. Again, from Hoeffding's
7/10, (2)
Es, [b] - ER,,,y [u] S T 1/10 and (3) Rss, [yr.s DE, 1E,,, S T/10 with probability 1 - over Sp. Combining these three inequalities, we obtain that (Ls(i,)) ((., p)] < with probability 1
over Sp- Choosing N 2 (((1/7?) poly(22 exp(AAd) log(1/7)) is sufficient for N₂ to be large enough with high probability.
Setting 82(2n2 in the above claim and taking union bound over all indices and their corresponding restrictions, we obtain that for N 2 ((poly (log n, exp(A + k)), 2d+k o 1/))). with probability least 1 - 8 over the smoothing of Dx and the sample S ~ DeON for all i E [n] and restrictions such that supp(p) = (t), holds that [[(i,p) (s(i, p)1 < T. In the case of this event, Algorithm succesfully finds all the relevant variables.
Finally, we give the complete proof of the main theorem.
Proof of Theorem 3.2. From Theorem B.I, we have that Algorithm 2 run with appropriate parameters succeeds in finding the relevant variables with probability at least 1 8/2. Now, using standard concentration arguments (similar to Claim B.2) and taking a union bound over all fixings of the relevant variables, variables. Thus, the ERM hypothesis î will necessarily agree with the true labelling function on all
have that contains sample consistent with each assignment of the relevant
inputs. Note that computing the ERM is trivial in this case as the subset of the sample containing the different assignments of the relevant variables immediately yields the truth table of the function. O
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] pprovided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We give proofs for all claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discuss extensively the assumptions needed for our results to hold. We also have formal statements with proofs.
Justification:
14

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't I acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide complete proofs for all the statements that we make.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper is theoretical, there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper is theoretical. The paper has no experiments and hence no code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /CodeSodmmmiiicc SoooddeubmsssioPPooe
/ //nips... /tippscc/ppptt wttp:ccccppppppcccccceocococccca
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: Our paper is theoretical. We have no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Paper is theoretical. No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Paper theoretical. No experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /twprr////eu.s..eeee cc/ cwtppclicpcccceececcccccccccc htw.ee/tetiiisieeennneneeen
Answer: [Yes]
Justification: We read the code and our work conforms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our paper is purely theoretical. We negative applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper is theoretical. We release no data/models.
Guidelines:
The answer NA means that the paper poses such risks.
18

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper uses no existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We release no new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper involves crowasourcing/researchh with human subjects.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper is theoretical and uses no human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: We did not LLMs in this work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https cer.apeeeeceeeoooeeneneeseeee /ttp://ccee///2//2////// for what should or should not be described.
20


Reviews:
[{"review_id": "gnfjuEqunH", "reviewer": "Reviewer_Spcm", "summary": "This paper studies a theoretically deep question: the $k$-junta problem where marginal distributions are perturbed instead of uniform over the hypercube; in particular, the problem in this paper is over Markov random fields (MRF). The main result yields a successful two-phased algorithm (with high probability) with sample size $\\Omega(\\text{poly}(\\log n, \\exp(\\lambda(d+k)), 2^{d+k}, \\sigma^{-k}, 1/\\delta))$. Their result is a natural generalization of earlier works for smoothed product distributions.", "questions": "1. Please see Weakness\n2. Does the learning of $k$-junta problem have any relevance with the task of learning $k$-parity, or do results for one problem inspire the other? If the answer is yes, then discussions for $k$-parity learning may be helpful.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The generalization is natural and significant: Extending the problem scale to a broader class of distributions is a long standing open problem, and the authors gave an elegant solution and sound analysis.\n2. The techniques illustrated in Section 3 is theoretically rich and novel. It is refreshing by blending unsupervised and supervised methods. The algorithm, despite requiring a possibly high sample size (see Weakness), will very likely stimulate further research on this area and further optimization.\n\nWeakness:\nMy major concern is the size of $k$; it is only logarithmic and therefore may restrict the paper's scope. I understand that this constraint is necessary to bound sample complexity to polynomial, but, to the best of my knowledge, problems in similar themes ($k$-parity, $k$-junta, etc) usually assume $k$ to be a constant fraction of $n$.", "was_revised": true, "final_justification": "The authors addressed my concern and I have decided to keep my score.", "rebuttal": "- Thank you for your review and encouraging feedback. \n-   Concern about size of $k$: The regime $k\\leq O(\\log n)$ is the main regime of parameters studied in the literature of efficient junta learning algorithms. As correctly observed by the reviewer, going beyond this regime will require superpolynomial sample complexity for generalization. Thus, even information theoretically, this is the only regime where one can learn with polynomial samples. We are not aware of the line of work that the reviewer refers to, where $k$ is assumed to be a constant fraction of $n$. \n-   Yes, learning $k$-junta does have relevance to the $k$-parity problem. In fact any SQ algorithm for learning $k$-juntas also works for learning noisy $k$-parities (as $k$-parities are $k$-juntas and SQ algorithms are tolerant to random classification noise). Since our algorithm falls in the SQ framework, it works even for the noisy $k$-parity problem. We will add a discussion on this."}, {"review_id": "0mJtkj82sT", "reviewer": "Reviewer_RNxT", "summary": "This paper investigates the following problem: Given random samples i.i.d. drawn from a Markov Random Field (with a known dependency graph of degree $O(\\log n)$), under a smoothed analysis framework, and labeled by an unknown k-junta, is there an efficient algorithm to recover the underlying k-junta? This work represents a significant generalization of prior research, which was largely confined to product distributions. A key contribution is the introduction of a conditional correlation statistic, $I(i,\\rho)$, which effectively leverages the property of MRFs to distinguish relevant features from irrelevant ones. Building on this statistic, the authors develop an algorithm with both runtime and sample complexity bounded by $n^{o(k)}$.", "questions": "The method is designed specifically for learning k-juntas, which is a relatively restricted model. It would be helpful if the authors could clarify what makes it particularly challenging to recover more complex concept classes, such as k-depth decision trees or k-DNFs under MRF distributions.\n\nIn line 162, the lowercase variables  s and t appear to be undefined in the surrounding context, this seems to be a typographical error.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\nA nice and natural generalization of product distribution in terms of MRF beyond worst-case analysis\n\nWeaknesses:\nAs the authors themselves acknowledge, a notable limitation of the proposed method is its reliance on the assumption that the MRF’s dependency graph is known. In the absence of this knowledge, one would need to resort to structure learning techniques for bounded-degree MRFs, incurring substantial additional computational and sample complexity.", "was_revised": true, "final_justification": "The generalization from prodcut distribution to any given MRF is natural, and the technical approach is also interesting. The authors also does a decent job of literature review. I recommend acceptance for this paper.", "rebuttal": "-    Thank you for your review and positive feedback.\n-    We acknowledge the weakness regarding the substantial additional cost if the underlying graph is not known. It is indeed an interesting open problem if structure learning is necessary for this task. \n-    Difficulty in extending to decision trees/DNF:  One main problem is that the number of relevant variables can now be $2^{k}$ as opposed to $k$. Thus, applying our method naively will incur a run time of $2^{2^{k}}$. Kalai and Teng [KT08] relied heavily on Fourier techniques to learn decision trees over smooth product distributions. Their arguments seem to rely crucially on the orthogonality of the fourier basis. These Fourier arguments don't extend to MRFs as there is no explicit orthogonal basis. It is an interesting open question if we learn decision trees (even in the case of smooth product distributions) without the use of Fourier techniques. We will add a discussion on this to the paper.\n\n[KT08] Adam Tauman Kalai and Shang‑Hua Teng. Decision Trees Are PAC‑Learnable from Most Product Distributions: A Smoothed Analysis. arXiv 2008"}, {"review_id": "3zP9zIaX7s", "reviewer": "Reviewer_PUJX", "summary": "This paper presents a polynomial-time algorithm to learn a \"junta\" from data generated by an MRF. In this framework, juntas should be understood as classifiers that implement the irrelevance of certain features. The work represents an extension of a previous work roughly corresponding to fully factorised distributions (= MRF with disconnected nodes). This is a technical paper with detailed proofs in the main body, but it completely lacks empirical validation.", "questions": "As mentioned, my main issue with the paper is the lack of a clear connection with machine learning and the (consequent?) absence of any experimental analysis. My main question for the authors is whether they considered this link straightforward and decided to keep it implicit, or whether they believe that the result in the paper has an interest by itself from a learning theory perspective, with no need to establish a connection with machine learning.\n\nI would also like to know whether the choice of ending the paper with the statement of the theorem (and its proofs), and without conclusions, reflects the idea that the technical results do not require any additional commentary.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- The extension from the fully factorised case to that of an MRF, under some reasonable assumptions on the resulting joint distribution, is a clear advance in the SOTA.\nYet, the paper seems to focus on the application of the result to machine learning, but there are almost no efforts to highlight the real potential of the result in ML. In this perspective, the lack of any experiment is an evident weakness,  which is, in my view, sufficient to justify a negative recommendation and a low significance (for this particular conference).\nIndeed, I could imagine an ML application involving a classification dataset, with the junta playing the role of a feature selection mechanism paired with a classifier. Yet, I doubt whether this nice approach would lead to competitive results: we know from that literature that approaches based on logical formulae are typically sub-optimal in modern ML.", "was_revised": true, "final_justification": "After reading the rebuttals and the other reviews, taking into consideration my low confidence in learning theory, I decide to raise the rating (from 2 to 4) and the significance (from 1 to 3).", "rebuttal": "- Thank you for your review and for recognizing that extending junta‐learning from product distributions to MRFs is a clear advance in the state of the art.\n- The problem of learning juntas was first introduced in [Blu94, BL97] motivated by the problem of learning in the presence of irrelevant features. We have highlighted this in lines 18-19 of our paper. We will add a concrete example similar to the one suggested by the reviewer to further emphasize this point.\n- Our work is purely theoretical in nature, and given the significance of the junta learning problem (as discussed below) to learning theory, we believe that our results are interesting by themselves, even without empirical validation.\n    - The problem plays a central role in learning theory. Indeed, the influential paper [MOS04] calls the junta learning problem \"the single most important\nopen question in uniform distribution learning\" (see section 1.1 of their paper). We view the extension to non-product distributions as an important next step in our theoretical understanding as most real-world data distributions consist of variables that depend on each other. Our work takes a natural next step, by showing efficient learnability over a wide class of non-product distributions (MRFs).  MRFs are a natural non-product distribution on the boolean hypercube and they have been influential in the field of probabilistic modelling, statistical physics, computer science etc.\n- We believe that the introduction section gives sufficient context and discussion regarding the significance of our main theorem. This is why we state the main theorem in the introduction itself (section 1.3). The succeeding sections give technical details such as the description of the algorithm and supporting proofs.\n\n[Blu94] Avrim Blum. Relevant Examples and Relevant Features: Thoughts from Computational Learning Theory. AAAI Fall Symposium 1994\n\n[BL97] Avrim L. Blum and Pat Langley. Selection of Relevant Features and Examples in Machine Learning. Artificial Intelligence 1997\n\n[MOS04] Elchanan Mossel, Ryan O’Donnell and Rocco A. Servedio. Learning Functions of k Relevant Variables. J. Comput. Syst. Sci. 2004"}, {"review_id": "VTqfudG8IG", "reviewer": "Reviewer_HU3C", "summary": "This paper gives an efficient PAC learner for learning $O(\\log n)$-sized juntas when the examples are drawn from a Markov Random Fields. This result extends the setting of learning Boolean concept classes from smoothed product distributions (Kalai and Teng'08).", "questions": "1. Line 3, 44: The usage of the term _broad generalization_ in the context of Kalai and Teng (2008) may be misleading. $O(\\log n)$-sized juntas are a subclass of size-$n$ decision trees, and the results in this paper do not seem to straightforwardly extend to learning of decision trees. I would invite the authors to at least add a footnote clarifying this issue.\n\n2. Line 20: While learning under different marginal distributions is an important question in its own right - and merits standalone discussion, it is important to note that most prior work focused on learning juntas actually consider the setting of learning under label noise. Curiously, any reference to this entire line of learning and testing juntas is missing from the paper. This should be explicitly addressed in the work (at least with a few notable references), especially considering that the paper is considering an extremely classical problem that has been around in the literature for over three decades.\n\n3. Section 1.1, Lines 30-33: How does $c$ relate to $\\Delta$ or $\\sigma$? What is $n$ in this context?\n\n4. Line 38: If I were to understand the earlier setup, the joint distribution over the instances is a product distribution. Since we are in the noiseless setting (assuming no label noise), what exactly are we referring to as the marginal distribution in this case?\n\n5. Definition 1.1, Line 51 onwards: The definition needs to be heavily rewritten simply based on the fact that this is the _only_ definition (formal or informal) for undirected graphical models, and the venue of choice is NeurIPS, which is a general purpose machine learning conference, unlike specialized theoretical venues like COLT.\n\n- How do we define a graph $G$ in this context? Are we still considering finite simple graphs? What is the degree $d$ of $G$?\n- In the context of this paper, can we consider $G$ to simply be the Boolean hypercube?\n- In equation $1$, how exactly is $\\psi_S$ defined? In Line 61, the authors note that the linear part of the polynomial $\\psi$ is called the external field. What is the _linear part_ of $\\psi=\\sum_S \\psi_S$ in this context? What happens if $\\psi_S$ is always non-linear - does that indicate an absence of an external field?\n\n6. Definition 1.2: I believe it needs to be explicitly stated that $D$ is an undirected graphical model.\n\n7. Line 73-74, 79-80: Sources should be cited, or an argument needs to be provided. How is this a generalization of p-biasedness?\n\n8. Line 75, 76: In the absence of normalization constants everywhere, there should be short derivation of the expression for the multiplicative perturbation of the density function. Once again it is ambiguous what perturbing the external field exactly means here.", "limitations": "It is unclear if the results or techniques in this paper imply anything non-trivial about learning more structured concept classes such as Decision Trees. Can the authors provide experimental evaluations indicating the difficulty of learning juntas in this setting compared to the i.i.d. setting and the smoothed product setting?", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n\nThe novelty of this paper lies in connecting two important subfields of learning - learning graphical models and learning Boolean concept classes, and providing tools for analysis in this setting.\n\n# Weaknesses\n\nIn light of existing results in the literature, the paper does a poor job of motivating why the $(O(1), O(1))$-smoothed MRF setting is important or why Theorem 1.3 is interesting since we are constrained to learning only $O(\\log n)$-sized juntas over slightly perturbed MRFs. The paper is also quite poorly presented and there is an extreme lack of clarity in the non-technical sections. Please the questions section for more details.", "was_revised": true, "final_justification": "The authors have addressed all of the concerns I had raised earlier. The technical portion of the paper was already quite strong to begin with, and combined with the earlier clarifications, I believe this is a strong contribution to the field of computational learning theory.", "rebuttal": "-   Thank you for your detailed review and for highlighting both the novelty and areas for improvement. \n-   \"In light of existing results in the literature, the paper does a poor job of motivating why the $(O(1), O(1))$-smoothed MRF setting is important...\": \n    -    Could the reviewer please clarify which existing results in the literature they are referring to here? \n    -    We point to various sections of our paper that motivate and highlight the importance of Theorem 1.3. First, the significance of the problem of the junta learning is discussed throughout page 1 of the paper. Prior work on efficient junta learning (in beyond worst case models) have studied only the case of product distributions. Also, the standard benchmark is to learn $O(\\log n)$ juntas as even the VC dimension of the class scales with $2^k$. These points are discussed in section 1.1. We highlight the importance of going beyond product distributions in lines 38-41, including the fact that this was explicitly posed as an open question in [KT08]. We believe that MRFs are a natural class of non-product distributions which generalize product distributions. Furthermore $(O(1),O(1))$-MRFs naturally generalize the $O(1)$-smooth product distributions studied in the works of [KT08, KST09, BDM20] (we expand on this point further in a subsequent bullet). Given these reasons, we believe that theorem 1.3 is a significant step in the theoretical study of junta learning.\n-   We agree that there is room for improvement in the clarity of the non-technical sections. We now respond to each of the reviewer's questions:\n    -   \"Line 3, 44 ...\" : We agree with this point. We had meant a broad generalization on the distributional assumption but now see how this could be misleading. We will add a footnote highlighting that (1) the broad generalization is only on the distrbitional assumoptions and (2) the results don't extend to decision trees. \n    -    \"Line 20...\" : The focus of our work is on PAC learning (noiseless) juntas. All the difficulties of efficient junta learning are already present in this noiseless case. We also note that as a consequence of our algorithm being in the Statistical query (SQ) framework, it is already noise tolerant to random classification noise [Kea93]. We will add a discussion on this to our paper. Since our focus was on going beyond the $n^k$ runtime (which is a barrier for the noiseless case itself), we had not focussed on label noise variants of the problem. We have discussed the testing problem in Section 1.4 (lines 102-112). We kindly ask the reviewer to point to additional references that they believe are missing in our discussion of related work.\n    -    \"Section 1.1, Lines 30-33...\": Here, we have made a few typos. It should read \"Kalai and Teng [KT08] introduced the notion of a $(c,\\sigma)$-smooth product distribution, which is a product distribution with mean vector of the form $\\mu=\\bar{\\mu}+\\Delta$ where $\\bar{\\mu}\\in [-c,c]$ is adversarially chosen and $\\Delta$ is randomly sampled from the uniform distribution on $[-\\sigma,\\sigma]$\". Here $c$ plays a similar role to $\\lambda$ in our definition of $(\\lambda,\\sigma)$-smoothed MRF. $n$ is the number of input coordinates, as noted in line 11.\n    -    \"Line 38\": The marginal distribution is the distribution of the input features. Formally in the junta learning problem, we get samples $(X,Y)$ where $X\\sim D_{x}$ and $Y=f(X)$ for junta $f$. Here $D_{x}$ is the marginal distribution. This is a distribution on \\(\\{0,1\\}^n\\) and was assumed to be product in prior work.\n    - \"Definition 1.1, Line 51 onwards\":\n       -  Here $G$ is a simple undirected graph. The vertex set is $[n]$ and the graph represents dependencies between different coordinates of the feature vector as highlighted in Definition 1.1. Here $d$ is the max degree of the graph (we missed the word max). \n       -  $G$ is not the boolean hypercube. The vertex set of $G$ is the set $[n]$, corresponding to coordinates of the input vector. The boolean hypercube on the other hand has vertex set \\(\\{0,1\\}^n\\). \n       -  As mentioned in lines 57-58, $\\psi_S$ are functions that only depend on the coordinates of $x$ in the set $S$. Since $\\psi$ is a polynomial of degree atmost $d$, we have $\\psi(x)=\\sum_{|S|\\leq d} c_S\\cdot\\prod_{i\\in S}x_i$ where $c_S$ for some constanst $(c_S)_{|S|\\leq d}$. \n      - The linear part of $\\psi$ is the polynomial $\\sum_{i\\in [n]}c_{\\{i\\}}\\cdot x_i$. We will add this to the paper. Yes, if $\\psi$ has no linear part, then it's external field is $0$. \n    - \"Definition 1.2...\": Agreed. We will make this change.\n    -  \"Line 73-74, 79-80...\": The sources that make this non-degeneracy assumption are listed on line 83. A $p$-biased product distribution is one where $min_{b\\in \\{\\pm 1\\}} (Pr[X_i=b])\\geq p$ for all $i\\in [n]$. The notion of \"Unbiased\" distribution (Defn 2.2) generalizes this and we prove in Claim 2.4 that low-width MRFs are unbiased with appropriate parameters. We will add a reference to Claim 2.4 (in line 80) to make this clearer.\n    -  \"Line 75,76\": We are happy to add a short derivation. We hope that our previous comment on the linear part of the polynomial clarified the question about the external field.\n\n- Generalization to Decision trees: Since depth $k$ decision trees are $2^k$- juntas, our result gives an algorithm that runs in time $2^{2^{k}}\\cdot \\text{poly}(n)$ to learn depth $k$ decision trees. This is polynomial in $n$ as long as $k\\leq O(\\log \\log n)$. This is a weak result as the work of Kalai and Teng [KT09] achieve learnability all the way up to depth $O(\\log n)$. Regardless, we will add a discussion on this in our paper. \n- As the focus of our work is theoretical in nature, experimental evidence seems out of the scope of this work. However, we note that lines 192-196 highlight why the proof techniques for product distributions don't translate to our setting.\n\n[KT08] Adam Tauman Kalai and Shang‑Hua Teng. Decision Trees Are PAC‑Learnable from Most Product Distributions: A Smoothed Analysis. arXiv 2008\n\n[KST09] Adam Tauman Kalai, Alex Samorodnitsky and Shang‑Hua Teng. Learning and Smoothed Analysis. FOCS 2009\n\n[BDM20] Alon Brutzkus, Amit Daniely and Eran Malach. ID3 Learns Juntas for Smoothed Product Distributions. COLT 2020\n\n[Kea93] Michael Kearns. Efficient Noise‑Tolerant Learning from Statistical Queries. STOC 1993"}]

Author rebuttal:

Meta-review: This paper examines the problem of efficiently learning k-juntas in polynomial time when the marginal distribution follows a discrete Markov Random Field (MRF). This is a classical problem where efficient algorithms, beyond the naive exhaustive search, had only been established for the limited case of product distributions. The authors bridge this gap by presenting an efficient algorithm that extends to the broader class of MRF-type distributions, although the result depends on a specific perturbation method.

Four reviews were collected for this submission. All reviewers highlighted the technical depth of the work and the novelty of the proposed theoretical framework. The AC concurs, viewing this as a valuable theoretical contribution that introduces several new ideas. While reviewers raised some concerns and follow-up questions (for example, regarding the significance of the results and clarity in certain sections), the authors addressed these thoroughly in their response.

The AC thanks the authors for their strong contribution.
Decision: Accept (poster)