Agnostically learning decision trees

By Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans. 2008

79 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Fairness Through Computationally-Bounded Awareness (2018, background): “Additionally, distribution-specific learners and learners with query access to the function have been studied [12, 7].”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, methodology): “This is the first extension of Jackson’s celebrated “Harmonic Sieve” algorithm for learning DNFs to a non-iid noise model and improves the approach of Gopalan et al. (2008) for agnostically learning decision trees.”
Provable guarantees for decision tree induction: the agnostic setting (2020, methodology): “The work of (Gopalan et al., 2008) gives a uniform-distribution algorithm that runs in poly(n, s, 1/ε) time; however, their algorithm requires the use of mem bership queries, and is also improper.”
Learning and Smoothed Analysis (2009, unknown): “…assumption and any algorithm which agnostically learns in this model can be generalized to learn from joint distributions over x × {0, 1} (see, e.g., [5]). is to output a hypothesis h ∶ {−1, 1} n → {0, 1} with low error err(h) = Pr x∼D [h(x) ≠ f (x)] on future examples from the same distribution.”
On the Power of Membership Queries in Agnostic Learning (2009, background): “Designing algorithms that learn efﬁciently in this model is notoriously hard and very few positive results are known (Kearns et al., 1994; Lee et al., 1995; Goldman et al., 2001; Gopalan et al., 2008; Kalai et al., 2008a,b).”
Distribution-Specific Agnostic Boosting (2009, methodology): “In addition Kalai and Kanade give a simpler version of the agnostic halfspace learning algorithm of Kalai et al. [21] and include results from an empirical evaluation of their algorithm.”
Learning DNF Expressions from Fourier Spectrum (2012, methodology): “The approximation algorithm of Kalai et al. (2009b) is based on an elaborate combination of the positive-reliable DNF learning algorithm of Kalai et al. (2009a) and the agnostic learning algorithm for decisions trees of Gopalan et al. (2008).”