Agnostically learning halfspaces

By Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio. IEEE Annual Symposium on Foundations of Computer Science, 2005

366 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/b0cfc923781bda9704a814819eb5d9a3f3f89ad2

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

In Computational Theory and Mathematics

Citations in the corpus

Agnostic Learning of Monomials by Halfspaces Is Hard (2009, background): “gave the first non-trivial algorithm for agnostic learning monomials in time 2 √ n) [23].”
Learning Kernel-Based Halfspaces with the 0-1 Loss (2011, methodology): “The idea of approximating the 0-1 transfer function with a polynomial was first proposed by [16] who studied the problem of agnostically learning halfspaces without kernels in R under distributional assumption.”
Equal Opportunity in Online Classification with Partial Feedback (2019, background): “…reduction above is unavoidable, because we measure the regret of our learner with respect to 0/1 classiﬁcation error, which is computationally hard to minimize, even for very simple classes H (see, e.g., [22, 16, 11]). our However, we can still hope to give an oracle efﬁcient algorithm for problem.”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, background): “• u(LTF), generalizing majorities of linear threshold functions (Kalai et al. (2008)).”
On the Computational Efficiency of Training Neural Networks (2014, background): “We note that algorithms for efﬁciently learning (real-valued) sparse or low-degree polynomials has been studied in several previous works (e.g. [13, 14, 8, 2, 1]).”
Theory of Disagreement-Based Active Learning (2014, methodology): “3 below continue to hold (with appropriate modification to constant factors) even if we replace the Euclidean metric (in the Lipschitz condition and definition of δ̄`) with an arbitrary pseudometric bounded on Ȳ2, which thereby admits such losses as the truncated quadratic loss [Bartlett, Jordan, an”
Provable guarantees for decision tree induction: the agnostic setting (2020, methodology): “For the ag nostic setting, the results of Kalai, Klivans, Mansour, and Servedio (Kalai et al., 2008) can be used to give a uniform O(log(s/ε)) anddistribution algorithm that runs in time n outputs a hypothesis that achieves error opt + ε. Compared s to Theorem 2, this algorithm does not require f…”
Agnostically learning decision trees (2008, methodology): “Further, Kalai et al. [13] (KKMS) showed that any concept class C with “good” low-degree Fourier concentration can be weakly agnostically learned; i.e., they showed that LMN could be easily modiﬁed to output a hypothesis with error O ( opt ) + (cid:15) in the agnostic setting.”
Reliably Learning the ReLU in Polynomial Time (2016, methodology): “[19] (Theorem 5) observed that in order output a hypothesis h with error opt+ ǫ it suffices to minimize (to within ǫ) the following quantity:”
Learning Halfspaces with Malicious Noise (2009, background): “Indeed, known algorithms for learning halfspaces [25, 11] or even simpler target functions [19] with malicious noise typically make strong assumptions about the underlying distribution D, and can learn to accuracy 1− only for noise rates η much smaller than .”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “Recently, there has been a flurry of work developing provable algorithms for learning the weights of a neural network under varying assumptions on the activation functions, input distributions, and noise models Sedghi et al. (2016); Arora et al.”
Learning Halfspaces and Neural Networks with Random Initialization (2015, background): “When no assumption is made on the noise, Kalai et al. (2008) show that if the data are drawn from the uniform distribution on a unit sphere, then there is an algorithm whose time complexity is polynomial in the input dimension, but exponential in 1 /(cid:15) (where (cid:15) is the additive error).”
The power of localization for efficiently learning linear separators with noise (2013, background): “We note that the results from our theorems in this model translate immediately into similar guarantees for the agnostic model of [34] (used commonly both in passive and active learning (e.g., [31, 3, 28]).”
Margin Based Active Learning (2007, methodology): “the marginal distribution over the inst ance space is uniform, as in section 4) one could use the recent results of Kalai et. al. fo r Agnostically Learning Halfspaces [ 11 ].”
Efficient Algorithms for Outlier-Robust Regression (2018, background): “h with ’ x[h(x) ,f(x)] as small as possible. The nasty noise model is considered the most challenging noise model for classiﬁcation problems in computational learning theory. Applying a result due to [KKMS08] (c.f. Theorem 5) for learning with respect to adversarial label noise only (standard agnost”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, background): “, [52], [58], [40], [59], [20], [19] for the problems of learning halfspaces and learning intersections thereof.”
Complexity Theoretic Limitations on Learning DNF's (2014, background): “Hardness of agnostically learning halfspaces also follows from the hardness of learning parities with noise [23].”