On Agnostic Learning of Parities, Monomials, and Halfspaces

By Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami. 2009

96 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

Stronger data poisoning attacks break data sanitization defenses (2018, background): “There are also known hardness results for even approximately minimizing the 0/1-loss (Feldman et al., 2009; Guruswami & Raghavendra, 2009), but it is possible that they do not apply in practice.”
Distribution-Specific Agnostic Boosting (2009, unknown): “[4, 5, 9]).”
Theory of Disagreement-Based Active Learning (2014, result): “As for the value of the disagreement coefficient for this class, Balcan, Hanneke, and Wortman [2008] claimed that for P the uniform distribution over [0, 1]k, any h ∈ C with P(x : h(x) = +1) > 0 has θh(0) < ∞ (as a special case of their result for ordinary binary classification trees); as mentioned ”
Pseudorandom Functions: Three Decades Later (2017, background): “, degree-1 polynomials) is polynomially equivalent to learning noisy parities [55].”
Agnostic Learning of Monomials by Halfspaces Is Hard (2009, methodology): “[17] showing NP-hardness of approximating the Maximum Agreement problem for halfspaces within (1/2 + ) for every constant > 0.”
Reliably Learning the ReLU in Polynomial Time (2016, background): “2 is thought to be computationally intractable due to the many existing hardness results in the literature [7, 11,19,21].”
Hardness results for agnostically learning low-degree polynomial threshold functions (2010, background): “Finally, a tight inapproximability result was established independently in [10] and [7]; these works showed that for any constant ǫ > 0, it is NP-hard to find a halfspace consistent with (12 + ǫ) of the examples even if there exists a halfspace consistent with (1 − ǫ) of the examples.”