• Thank you for your detailed review and for highlighting both the novelty and areas for improvement.

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

  • Could the reviewer please clarify which existing results in the literature they are referring to here?
  • 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.

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

  • "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.
  • "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.
  • "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.
  • "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.
  • "Definition 1.1, Line 51 onwards":
    • 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).
    • $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$.
    • 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}$.
    • 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$.
  • "Definition 1.2...": Agreed. We will make this change.
  • "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.
  • "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.

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

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

[KT08] Adam Tauman Kalai and Shang‑Hua Teng. Decision Trees Are PAC‑Learnable from Most Product Distributions: A Smoothed Analysis. arXiv 2008

[KST09] Adam Tauman Kalai, Alex Samorodnitsky and Shang‑Hua Teng. Learning and Smoothed Analysis. FOCS 2009

[BDM20] Alon Brutzkus, Amit Daniely and Eran Malach. ID3 Learns Juntas for Smoothed Product Distributions. COLT 2020

[Kea93] Michael Kearns. Efficient Noise‑Tolerant Learning from Statistical Queries. STOC 1993

We thank the reviewer for raising their score. The usage of term "marginal distribution" is quite standard in the PAC learning literature, even in the noiseless case. We agree that it is the only distribution being considered here(and hence may be confusing), however we have used the term to be consistent (and not use a new term just for the noiseless case).

• 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.
• 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.
• 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.
  • The problem plays a central role in learning theory. Indeed, the influential paper [MOS04] calls the junta learning problem "the single most important open 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.
• 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.

[Blu94] Avrim Blum. Relevant Examples and Relevant Features: Thoughts from Computational Learning Theory. AAAI Fall Symposium 1994

[BL97] Avrim L. Blum and Pat Langley. Selection of Relevant Features and Examples in Machine Learning. Artificial Intelligence 1997

[MOS04] Elchanan Mossel, Ryan O’Donnell and Rocco A. Servedio. Learning Functions of k Relevant Variables. J. Comput. Syst. Sci. 2004

• Thank you for your review and positive feedback.
• 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.
• 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.

[KT08] Adam Tauman Kalai and Shang‑Hua Teng. Decision Trees Are PAC‑Learnable from Most Product Distributions: A Smoothed Analysis. arXiv 2008

• Thank you for your review and encouraging feedback.
• 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$.
• 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.