Hardness of Learning Halfspaces with Noise

By Venkatesan Guruswami, Prasad Raghavendra. 2006

200 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.”
Learning from untrusted data (2016, background): “Guruswami and Raghavendra (2009) and Feldman et al. (2009) show that learning half-spaces is NP-hard for any α < 1, while Hardt and Moitra (2013) show that learning k-dimensional subspaces in Rd is hard if α < kd .”
The landscape of empirical risk for nonconvex losses (2016, background): “[9, 10] prove that, if the joint distribution of (Y,X) is arbitrary, no polynomial time algorithm exists to construct a classifier that is better than random – even when a good approximate classifier exists.”
Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization (2018, background): “Since globally optimizing (16) is in general NP-hard (Guruswami and Raghavendra, 2009), we instead focus on understanding the effect of the normalized parameterization when searching for a stationary point.”
Learning with Annotation Noise (2009, background): “However, 0-1 loss minimization is computationally intractable for large datasets (Feldman et al., 2006; Guruswami and Raghavendra, 2006); substitute loss functions are often used in practice.”
Theory of Disagreement-Based Active Learning (2014, background): “the formal details is referred to the original article of Hanneke [2007a]. Balcan and Hanneke [2012] have recently applied this same technique in a more general setting, allowing general abstract families of queries, beyond label requests: for instance, queries that propose a set”
Agnostically learning halfspaces (2005, background): “In this model the learner receives labeled examples(x, y) drawn from a fixed distribution over example-label pairs, but (in contrast with Valiant’s standard PAC learning model [29]) the learner cannot assume that the labelsy are generated by applying some target functionf to the examples x.”
Learning Kernel-Based Halfspaces with the 0-1 Loss (2011, background): “There are also strong hardness of approximation results for proper learning without margin (see for example [14] and the references therein).”
Agnostic Learning of Monomials by Halfspaces Is Hard (2009, methodology): “An optimal inapproximability result was established independently by Guruswami and Raghavendra [19] and Feldman et al.”
The power of localization for efficiently learning linear separators with noise (2013, background): “In the context of theoretical computer science more broadly, problems of noisy learning are related to seminal results in approximation-hardness [1, 27], cryptographic assumptions [14, 39], and are connected to other classic questions in learning theory (e.g., learning DNF formulas [34]), and…”
A General Agnostic Active Learning Algorithm (2007, background): “On the other hand, agnostic learning suﬀers from severe computational intractability for many hypothesis classes (e.g. [17]), and of course, agnostic active learning is at least as hard in the worst case.”
Complexity theoretic limitations on learning halfspaces (2015, background): “Later on, the corresponding maximization problem was considered by several authors [5, 16, 23, 41, 38], culminating with Feldman, Gopalan, Khot and Ponnuswami [38] who showed that assuming that no quasi-polynomial time algorithm can solve NP hard problems, no efficient algorithm can distinguish samp”
On the Power of Membership Queries in Agnostic Learning (2009, background): “Furthermore, strong computational hardness results are known for ag-nostic learning of even the simplest classes of functions such as parities, monomials and halfspaces (H˚astad, 2001; Feldman, 2006; Feldman et al., 2006; Guruswami and Raghavendra, 2006) (albeit only for proper learning).”
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.”
Learning Halfspaces and Neural Networks with Random Initialization (2015, background): “It is known that for any constant approximation ratio, the problem of approximately minimizing the zero-one loss is computationally hard (Guruswami and Raghavendra, 2009; Daniely et al., 2014).”