Pith. sign in

REVIEW 1 major objections 6 minor 43 references

Learning Juntas under Markov Random Fields

T0 review · 1 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For Markov random fields whose external field is randomly perturbed, functions of only O(log n) of n variables are exactly learnable in polynomial time.

desk verdict A real generalization of smoothed junta learning to MRFs with a repairable gap in the Claim 3.4 anticoncentration step. read the letter →

arxiv 2506.00764 v1 pith:SWPE3XTV submitted 2025-06-01 cs.LG cs.DS

Gautam Chandrasekaran , Adam Klivans This is my paper
classification cs.LGcs.DS MSC 68Q3268T05
keywords juntalearningMarkovrandomfieldssmoothedanalysisexternalfieldperturbationconditionalcorrelationstatisticpolynomialanticoncentrationgraphicalmodelstructureundirectedmodels
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that functions depending on only $k$ of $n$ input bits (called $k$-juntas) — which are believed to require $n^{\Omega(k)}$ time over the uniform distribution — become exactly learnable in polynomial time when the input distribution is a Markov random field (MRF) whose external field has been randomly perturbed, as long as the MRF's dependency graph has degree at most $O(\log n)$ and $k \le O(\log n)$. This extends the smoothed-analysis result of Kalai and Teng, which handled only product distributions (MRFs with no edges), and answers an open question from that line of work. The algorithm first identifies the relevant coordinates by measuring, for each coordinate, its correlation with the label after conditioning on that coordinate's neighbors in the dependency graph, then reconstructs the junta's truth table by brute force over the found variables. The significance is that real data has interdependencies between features, and this is the first proof that unsupervised structure learning of graphical models can be turned into a provably efficient supervised learning algorithm.

What carries the argument

The engine is the conditional correlation statistic $I(i,\rho) = |\mathbb{E}_{D_\rho}[y x_i] - \mathbb{E}_{D_\rho}[y] \mathbb{E}_{D_\rho}[x_i]|$, where $D_\rho$ is the labelled distribution conditioned on the event that the neighbor variables $x_{N_G(i)}$ equal the restriction $\rho$. Two structural facts make this statistic separate signal from noise: the Markov property, which renders $x_i$ conditionally independent of everything else once its neighbors are fixed (so $I(i,\rho)=0$ exactly for irrelevant $i$), and the smoothness model, which lets the authors express the leftover dependence $\mathbb{E}_{D_\rho}[g_i(x_{-i})]$ as a multilinear polynomial in the smoothing variables $\Delta_j = \log(1+\alpha_j)$ whose nonzero coefficients are bounded below by $\exp(-\lambda k)/8^k$. A polynomial anticoncentration lemma, adapted from earlier smoothed-analysis work, then shows the polynomial is at least $\sigma^k$-scale with high probability, producing the lower bound on $I(i,\rho)$ for each relevant variable. The unbiasedness claims of the paper supply the probability estimates that keep both the enumeration over neighbor-fixings and the final brute-force truth table within the stated sample budget.

What would settle it

Run the algorithm's core statistic on the smallest nontrivial case the theorem covers — an Ising model on a 10-variable cycle graph with a known 2-junta label — and, by exhaustive enumeration of all $2^{10}$ configurations, compute the exact value of $I(i,\rho)$ for every relevant variable and neighbor-pattern across many smoothing draws $\alpha \sim \mathrm{Unif}([-\sigma,\sigma]^{10})$. The theorem predicts that with probability at least $1-\gamma$ over those draws some pattern satisfies $|I(i,\rho)| \ge \gamma^2(\sigma \exp(-\lambda)/16)^{k+2}$; if the observed fraction drops substantially below $1-\gamma$, or if the samples needed for exact recovery grow faster than $\mathrm{poly}(\log n, 2^{d+k}, \sigma^{-k})$ as $\sigma$ shrinks, the central claim is wrong.

Watch

Extended reading notes

Core claim

The central claim, Theorem 3.2, is that if the marginal distribution is a $(\lambda,\sigma)$-smooth MRF — an adversarially chosen Gibbs distribution whose external field is perturbed entrywise by factors $1+\alpha_i$ with $\alpha_i$ iid uniform on $[-\sigma,\sigma]$ — and the dependency graph of degree at most $d$ is known, then Algorithm 2 learns any $k$-junta exactly, with zero error and probability at least $1-\delta$ over samples and smoothing, using $N = \Omega(\mathrm{poly}(\log n, \exp(\lambda(d+k)), 2^{d+k}, \sigma^{-k}, 1/\delta))$ samples and at most $\mathrm{poly}(n,N)$ time, which is polynomial for $d,k \le O(\log n)$ and $\lambda, \sigma = O(1)$. The proof centers on the statistic $I(i,\rho)$, the correlation between coordinate $i$ and the label under the distribution conditioned on fixing $i$'s graph-neighbors to the pattern $\rho$; the Markov property makes this statistic zero exactly for irrelevant coordinates, while density-ratio algebra and a polynomial anticoncentration lemma show that for every relevant coordinate some neighbor-pattern yields $|I(i,\rho)| \ge \gamma^2(\sigma \exp(-\lambda)/16)^{k+2}$ with probability at least $1-\gamma$ over the smoothing. The paper also proves every such MRF is $\exp(-\lambda)/4$-unbiased, which guarantees that the brute-force truth-table phase observes every assignment of the relevant variables.

Load-bearing premise

The smoothing perturbs only the linear part of the Gibbs potential (the external field), the adversarial part's coordinate derivatives must be bounded by $\lambda$, and the main theorem assumes the dependency graph is known; the unknown-graph case gets only a remark citing structure learners, not a theorem.

Editorial extensions

If this is right

  • Juntas of size $k \le O(\log n)$ become exactly learnable in polynomial time over any smoothed MRF with a known bounded-degree dependency graph — the first guarantee of its kind beyond product distributions.
  • The open question raised by Kalai, Samorodnitsky, and Teng about extending smoothed learning beyond product marginals is answered affirmatively.
  • The dependency graph is a one-time unsupervised investment: once learned, it supports many supervised learning tasks over the same distribution, giving the first proven pipeline from graphical-model structure learning to efficient supervised learning.
  • The resulting hypothesis has zero expected error with high probability — not merely small error — because the relevant-variable filter is exact and the brute-force phase reconstructs the complete truth table.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The known-graph assumption is the fragile spot: an imperfectly recovered neighborhood would disturb the exact zero/nonzero separation of $I(i,\rho)$, so a quantitative analysis of how much graph-recovery error the statistic tolerates is the natural next step; the paper's remark about structure learners does not by itself prove an end-to-end theorem.
  • Because the guarantee degrades as $\sigma^{-k}$, the algorithm's power comes from the perturbation itself: as $\sigma \to 0$ the sample bound diverges and worst-case hardness returns, so one can probe the theory by measuring recovery difficulty across a continuum of $\sigma$ values.
  • The multiplicative perturbation structure suggests the same condition-on-neighbors-plus-anticoncentration recipe might extend to smoothing higher-order interaction coefficients, although the density-ratio algebra would need reworking for nonlinear terms.
  • The brute-force final phase needs to see all $2^k$ assignments of the found variables, which is where the $\exp(\lambda k)$ factor enters; for constant $\lambda$ this caps $k$ at $O(\log n)$, so pushing beyond logarithmic junta size would require a more efficient final phase than exhaustive truth-table reconstruction.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

Summary. The paper studies the problem of learning k-juntas under Markov random field (MRF) marginals in a smoothed analysis setting. The proposed model, the (λ,σ)-smooth MRF, perturbs only the external field of an adversarially chosen MRF whose higher-order interactions have bounded derivatives. The main result (Theorem 3.2) states that, when the dependency graph G of degree at most d is known, Algorithm 2 learns the junta exactly with high probability using poly(log n, exp(λ(d+k)), 2^{d+k}, σ^{-k}, 1/δ) samples, and runs in polynomial time for d,k=O(log n) and constant λ,σ. The key technical claim is that conditioning on the neighbors of a variable i makes the correlation statistic I(i,ρ) vanish for irrelevant variables and, with high probability over the smoothing, be bounded below by γ²(σ e^{-λ}/16)^{k+2} for relevant variables. The proof combines the Markov property, the unbiasedness of smooth MRFs, and a polynomial anticoncentration lemma to lower bound a conditional expectation. The paper also remarks that unknown graphs can be handled by existing structure learners, but the main theorem assumes the graph is known.

Significance. If the proof gap discussed below is repaired, this would be a meaningful extension of the Kalai-Teng smoothed analysis framework from product distributions to non-product MRF distributions, directly addressing a question raised in KST09. The algorithmic idea of using the Markov property to design a localized correlation statistic is natural and appealing, and the paper is the first to explicitly connect structure learning algorithms for graphical models to efficient supervised learning. The manuscript is a clean theoretical contribution: the thresholds are derived from the lower bounds, no parameters are fitted to data, and the analysis is self-contained modulo standard cited lemmas. These are strengths. However, the central anticoncentration step in Claim 3.4 is currently incomplete, and because that claim is load-bearing for finding the relevant variables, the main theorem is not yet proven as written.

major comments (1)
  1. [Section 3.3, Claim 3.4, after Eq. (9)] The application of Lemma 3.1 is invalid as written. The polynomial F(α) = Σ_z \bar h(z) Π_{j∈T_i}(1+α_j z_j) does not have its maximal coefficient equal to |\bar h(z)| for some z. For a monomial α_S, the coefficient is c_S = Σ_{z⊇S} \bar h(z), a signed sum of up to 2^{|T_i|} terms, and cancellations can make all coefficients much smaller than max_z|\bar h(z)|. Therefore the asserted lower bound on |E_{Dρ}[g_i]| is not established by the argument given. The gap appears repairable: Möbius inversion on the Boolean lattice gives max_S |c_S| ≥ max_z|\bar h(z)| / 2^{|T_i|}, which changes only the constant in the exponential base and should preserve the polynomial-time conclusion of Theorem 3.2 for constant λ and σ. The authors should also address the related point that Lemma 3.1 is stated for a coefficient of a degree-ℓ monomial, whereas after the Möbius-inversion bound the surviving coefficient may be of smaller degree; either a version of Lemma 3.1 for arbitrary nonzero monomial coefficients or an embedding argument is needed.
minor comments (6)
  1. [Definitions 1.2 and Fact 2.3] The symbol σ is used both for the perturbation magnitude in Definition 1.2 and for the logistic function in Fact 2.3; please disambiguate the notation.
  2. [Definition 1.2] The parameter λ is introduced as λ ∈ R, but the intended assumption is λ ≥ 0; please state this explicitly, since the bounds use exp(−λ).
  3. [Section 3.3, Eq. (8)] In the lower bound on the density ratio, the text says 'exp(Δ_j) ≤ (1+σ) ≤ 2', but the argument requires exp(−Δ_j) ≤ 1/(1−σ) ≤ 2, because Δ_j = log(1+α_j) with α_j ≥ −σ. Please correct this direction.
  4. [Abstract and Remark 1.4] The abstract and Remark 1.4 advertise an algorithm with an unsupervised structure-learning phase, but Theorem 3.2 assumes the dependency graph G is known, and no end-to-end theorem for unknown G is proved. The 'first example' claim should be qualified to the known-graph setting or supported by a combined theorem.
  5. [Proof of Theorem B.1] In the threshold choice, 2τ = (δ/(k2^d))^2 · base does not match the union bound with γ = δ/(2k2^d), which gives γ² = δ²/(4k²2^{2d}); the constants should be reconciled so that the formal choice of τ is consistent with the stated probability guarantee.
  6. [Section 3.3, after Eq. (7)] The phrase 'The second inequality follows' should read 'The second equality follows', since the displayed step is an equality derived from ψ_i(x) = ψ(x) − Σ_{j∈T_i} Δ_j x_j.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the junta-learning theorem is proved from the stated smooth-MRF assumptions using external anticoncentration and structure-learning references; no fitted parameter is later renamed as a prediction.

full rationale

The paper's central claim is an analytic sample-complexity guarantee for learning O(log n)-juntas over (sigma,lambda)-smooth MRFs. The algorithm's threshold is set from the lower bound derived in Claim 3.4, not fit to data; the relevant-variable statistic is estimated from samples and the proof gives explicit concentration bounds. The two load-bearing claims, Claim 3.3 and Claim 3.4, are established from the Markov property, the smooth-MRF factorization, and the external anticoncentration lemma of Kalai, Samorodnitsky, and Teng (Lemma 3.1), which is cited from prior work by other authors. The self-citations that appear, e.g. [CK24], [CKK+24], and [KM17], are used only in related work or in the optional remark that an unknown dependency graph could first be recovered by existing structure learners; [KM17] is an independent FOCS theorem and is not used to prove the main theorem, whose statement assumes the dependency graph is known. Nothing is defined in terms of the target result, and no fitted quantity is renamed as a prediction. A possible algebraic gap in the proof of Claim 3.4 (the asserted maximal coefficient of a multilinear polynomial) would be a correctness or soundness issue, not circularity, because the step relies on an external lemma rather than on the paper's own assumptions being reused as conclusions. Accordingly, no circular step is identified.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard tools (Hammersley-Clifford, anticoncentration) and on the modeling assumption that only the external field is smoothed. The known-graph assumption is an input to the theorem. No new entities or fitted parameters are introduced.

assumptions (5)
  • standard math Hammersley-Clifford theorem: any positive MRF has density proportional to exp(ψ(x)) for a clique potential ψ.
    Used in Definition 1.1 to write the MRF density as a Gibbs measure.
  • standard math Lemma 3.1 (KST09): anticoncentration of multilinear polynomials over uniform intervals.
    Used in Claim 3.4 to lower bound the probability that the polynomial in α is not too small.
  • domain assumption The factorization ψ of the MRF has all coordinate derivatives ∂iψ bounded in L1 norm by λ for the adversarial part ψ̄.
    This is a non-degeneracy condition that ensures the distribution is unbiased; it is assumed to hold for the adversarial part ψ̄.
  • domain assumption Only the external field is perturbed; interaction terms are fixed.
    The smoothing model perturbs Δ_i in the linear part only. The proof's density ratio relies on this specific form.
  • domain assumption The dependency graph G is known to the learner (Theorem 3.2).
    The main theorem takes G as input; the remark about recovering it is not a theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Juntas under Markov Random Fields." pith.science (2026). https://pith.science/paper/SWPE3XTV

@misc{pith2026250600764,
  author       = {Pith},
  title        = {Pith review of: Learning Juntas under Markov Random Fields},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SWPE3XTV}},
  note         = {Machine review of arXiv:2506.00764}
}
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 an undirected graphical model lead to provably efficient algorithms for supervised learning.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 41 canonical work pages

  1. [1]

    Public-key cryptography from different assumptions

    Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. STOC '10, page 171–180, New York, NY, USA, 2010. Association for Computing Machinery

    work page 2010

  2. [2]

    Learning factor graphs in polynomial time and sample complexity

    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

    work page 2006

  3. [3]

    Agnostically learning juntas from random walks, 2008

    Jan Arpe and Elchanan Mossel. Agnostically learning juntas from random walks, 2008

    work page 2008

  4. [4]

    Id3 learns juntas for smoothed product distributions

    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

    work page 2020

  5. [5]

    Weakly learning dnf and characterizing statistical query learning using fourier analysis

    Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing , STOC '94, page 253–262, New York, NY, USA, 1994. Association for Computing Machinery

    work page 1994

  6. [6]

    Near-optimal learning of tree-structured distributions by chow-liu

    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

    work page 2021

  7. [7]

    Blum and Pat Langley

    Avrim L. Blum and Pat Langley. Selection of relevant features and examples in machine learning. Artificial Intelligence , 97(1):245--271, 1997

    work page 1997

  8. [8]

    Improved bounds for testing juntas

    Eric Blais. Improved bounds for testing juntas. In Ashish Goel, Klaus Jansen, Jos \'e D. P. Rolim, and Ronitt Rubinfeld, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques , pages 317--330, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg

    work page 2008

Show all 43 references
  1. [9]

    Testing juntas nearly optimally

    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

    2009

  2. [10]

    Relevant examples and relevant features: Thoughts from computational learning theory

    Avrim Blum. Relevant examples and relevant features: Thoughts from computational learning theory. In AAAI Fall Symposium on ‘Relevance , volume 5, page 1, 1994

    1994

  3. [11]

    Bshouty, E

    N. Bshouty, E. Mossel, R. O'Donnell, and R.A. Servedio. Learning dnf from random walks. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. , pages 189--198, 2003

    2003

  4. [12]

    Reconstruction of markov random fields from samples: Some observations and algorithms

    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

    2008

  5. [13]

    Efficiently learning ising models on arbitrary graphs

    Guy Bresler. Efficiently learning ising models on arbitrary graphs. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 , pages 771--782. ACM , 2015

    2015

  6. [14]

    Markov fields on finite graphs and lattices

    P Clifford and JM Hammersley. Markov fields on finite graphs and lattices. 1971

    1971

  7. [15]

    Gautam Chandrasekaran and Adam R. Klivans. Learning the sherrington-kirkpatrick model even at low temperature. CoRR , abs/2411.11174, 2024

    2024 arXiv

  8. [16]

    Smoothed analysis for learning concepts with low intrinsic dimension

    Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, and Konstantinos Stavropoulos. Smoothed analysis for learning concepts with low intrinsic dimension. In The Thirty Seventh Annual Conference on Learning Theory , pages 876--922. PMLR, 2024

    2024

  9. [17]

    Approximating discrete probability distributions with dependence trees

    CKCN Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory , 14(3):462--467, 1968

    1968

  10. [18]

    Learning ising models from one or multiple samples

    Yuval Dagan, Constantinos 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

    2021

  11. [19]

    Outlier-robust learning of ising models under dobrushin’s condition

    Ilias Diakonikolas, Daniel M Kane, Alistair Stewart, and Yuxin Sun. Outlier-robust learning of ising models under dobrushin’s condition. In Conference on Learning Theory , pages 1645--1682. PMLR, 2021

    2021

  12. [20]

    Testing juntas

    Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. Journal of Computer and System Sciences , 68(4):753--787, 2004

    2004

  13. [21]

    Learning ising models with independent failures

    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

    2019

  14. [22]

    Efficiently learning markov random fields from dynamics

    Jason Gaitonde, Ankur Moitra, and Elchanan Mossel. Efficiently learning markov random fields from dynamics. arXiv preprint arXiv:2409.05284 , 2024

    2024 arXiv

  15. [23]

    Information theoretic properties of markov random fields, and their algorithmic applications

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

    2017

  16. [24]

    Smoothed analysis of online and differentially private learning

    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

    2020

  17. [25]

    Smoothed analysis with adaptive adversaries

    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 942--953, 2022

    2021

  18. [26]

    Jackson and Karl Wimmer

    Jeffrey C. Jackson and Karl Wimmer. New results for random walk learning. In COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009 , 2009

    2009

  19. [27]

    Efficient noise-tolerant learning from statistical queries

    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

    1993

  20. [28]

    Mcmc learning

    Varun Kanade and Elchanan Mossel. Mcmc 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

    2015

  21. [29]

    Klivans and Raghu Meka

    Adam R. Klivans and Raghu Meka. Learning graphical models using multiplicative weights. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 343--354, 2017

    2017

  22. [30]

    Learning and smoothed analysis

    Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng. Learning and smoothed analysis. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science , FOCS '09, page 395–404, USA, 2009. IEEE Computer Society

    2009

  23. [31]

    Decision trees are pac-learnable from most product distributions: a smoothed analysis

    Adam Tauman Kalai and Shang-Hua Teng. Decision trees are pac-learnable from most product distributions: a smoothed analysis. arXiv preprint arXiv:0812.0933 , 2008

    2008 arXiv

  24. [32]

    Learning to sample from censored markov random fields

    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

    2021

  25. [33]

    Servedio

    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

    2004

  26. [34]

    Greedy learning of markov network structure

    Praneeth Netrapalli, Siddhartha Banerjee, Sujay Sanghavi, and Sanjay Shakkottai. Greedy learning of markov network structure. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages 1295--1302. IEEE, 2010

    2010

  27. [35]

    Proclaiming dictators and juntas or testing boolean formulae

    Michal Parnas, Dana Ron, and Alex Samorodnitsky. Proclaiming dictators and juntas or testing boolean formulae. In Michel Goemans, Klaus Jansen, Jos \'e D. P. Rolim, and Luca Trevisan, editors, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniq...

    2001

  28. [36]

    On learning ising models under huber's contamination model

    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:16327--16338, 2020

    2020

  29. [37]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM , 51(3):385–463, May 2004

    2004

  30. [38]

    Information-theoretic limits of selecting binary graphical models in high dimensions

    Narayana P Santhanam and Martin J Wainwright. Information-theoretic limits of selecting binary graphical models in high dimensions. IEEE Transactions on Information Theory , 58(7):4117--4134, 2012

    2012

  31. [39]

    Learning graphs with a few hubs

    Rashish Tandon and Pradeep Ravikumar. Learning graphs with a few hubs. In International conference on machine learning , pages 602--610. PMLR, 2014

    2014

  32. [40]

    Finding correlations in subquadratic time, with applications to learning parities and juntas

    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

    2012

  33. [41]

    Lokhov, and Michael Chertkov

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

    2016

  34. [42]

    High-dimensional graphical model selection using _1 -regularized logistic regression

    Martin J Wainwright, John Lafferty, and Pradeep Ravikumar. High-dimensional graphical model selection using _1 -regularized logistic regression. Advances in neural information processing systems , 19, 2006

    2006

  35. [43]

    Sparse logistic regression learns all discrete pairwise graphical models

    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

    2019

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.