Agnostic Learning of Monomials by Halfspaces Is Hard

By Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu. 2009

165 citations recorded by the source corpus.

We prove the following strong hardness result for learning: Given a distribution on labeled examples from the hypercube such that there exists a monomial (or conjunction) consistent with (1-ε)-fraction of the examples, it is NP-hard to find a halfspace that is correct on ( 1/2 +ε)-fraction of the examples, for arbitrary constant ε ≫ 0. In learning theory terms, weak agnostic learning of monomials by halfspaces is NP-hard. This hardness result bridges between and subsumes two previous results which showed similar hardness results for the proper learning of monomials and halfspaces. As immediate corollaries of our result, we give the first optimal hardness results for weak agnostic learning of decision lists and majorities. Our techniques are quite different from previous hardness proofs for learning. We use an invariance principle and sparse approximation of halfspaces from recent work on fooling halfspaces to give a new natural list decoding of a halfspace in the context of dictatorship tests/label cover reductions. In addition, unlike previous invariance principle based proofs which are only known to give Unique Games hardness, we give a reduction from a smooth version of Label Cover that is known to be NP-hard.

How researchers see this paper

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

Citations in the corpus

Fairness Through Computationally-Bounded Awareness (2018, background): “In general, agnostic learning is considered a notoriously hard computational problem [15, 17, 8]; that said, in the context of fairness in machine learning, [16] show that using heuristic methods to agnostically learn linear hypotheses seems to work well in practice.”
Tikhonov, Ivanov and Morozov regularization for support vector machine learning (2016, background): “…· Morozov regularization · Support vector machine B Luca Oneto Luca.Oneto@unige.it Sandro Ridella Sandro.Ridella@unige.it Davide Anguita Davide.Anguita@unige.it 1 DITEN - University of Genoa, Via Opera Pia 11a, 16145 Genoa, Italy 2 DIBRIS - University of Genoa, Via Opera Pia 13, 16145 Genoa, Italy”
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.”
On the Consistency of Ordinal Regression Methods (2014, background): “Second, due to the nonconvexity and discontinuity of `, the risk is dicult to optimize and can lead to NP-hard problems [3, 8] (note that binary classication can be seen as a particular case of ordinal regression).”
Algorithms for Direct 0-1 Loss Optimization in Binary Classification (2013, background): “Unfortunately, it is NP–hard to optimize directly (Feldman et al., 2009; Ben-David et al., 2003) and thus most work has sought alternative losses with better computational guarantees.”
A Minimax Approach to Supervised Learning (2016, background): “The minimax SVM, which is a relaxed version of the standard SVM, minimizes the worst-case 0-1 loss and by our numerical experiments outperforms the SVM. Note that ERM with the 0-1 loss is known to be NP-hard [9].”
On Symmetric Losses for Learning from Corrupted Labels (2019, background): “The main motivation to use a surrogate loss in binary classiﬁcation is that the zero-one loss is discontinuous and therefore diﬃcult to optimize [Ben-David et al., 2003; Feldman et al., 2012].”
Eliciting and Enforcing Subjective Individual Fairness (2019, background): “Even absent fairness constraints, learning to minimize 0/1 loss (even over linear classiﬁers) is computationally hard in the worst case (see e.g. Feldman et al. [2012, 2009]).”