On the difficulty of approximately maximizing agreements

By Shai Ben-David, Nadav Eiron, Philip M. Long. 2000

173 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

Theoretical Guarantees for Model Auditing with Finite Adversaries (2019, background): “roximates L k;Sn by L Sn (~h k). Observe that ~h k should be a minimizer of L Sn in order to have L k;Sn = L Sn (~h k). Although it is known that nding the ERM rule is, in general, an NP-hard problem [36], in the present context it is reasonable to assume that L Sn (~h k) is a good approximation for”
Kernel methods in machine learning (2007, neutral): “[15] show that finding even an approximate minimum classification error solution is difficult.”
On Agnostic Learning of Parities, Monomials, and Halfspaces (2009, background): “Ben-David et al. gave the first inapproximability result for this problem, proving that the maximum agreement rate is NP-hard to approximate within a factor of 770 767 for any constant > 0 [ BDEL03 ].”
Smart "Predict, then Optimize" (2017, methodology): “Moreover, since Proposition 1 demonstrates that our framework captures binary classification, solving (4) is at least as difficult as optimizing the 0-1 loss function, which may be NP-hard in many cases (Ben-David et al. 2003).”
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].”
A statistical approach to rule learning (2006, background): “Even worse, a recent result shows that it is NP-hard to approximate the maximal agreement of a rule set with a training set to within some fixed constant (Ben-David et al., 2003).”
An experimental evaluation of simplicity in rule learning (2008, background): “Unfortunately, the problem of finding a rule set of restricted size with the smallest error on a given training set is NP-hard (6), and unless P=NP, it cannot even be approximated in polynomial time up to some fixed constant (7).”
Hardness of Learning Halfspaces with Noise (2006, background): “The Maximum Agreement for Halfspaces problem, denoted HS-MA, was shown to be NP-hard to approximate within some constant factor for the {0, 1,−1} domain in [3, 6] (the factor was 261/262 + ε in [3] and 415/418 + ε in [6]).”
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”
A theory of learning from different domains (2010, methodology): “Unfortunately, this is computationally intractable for linear threshold classiﬁers, since ﬁnding a minimum error classiﬁer is hard in general (Ben-David et al. 2003).”
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.”
Margin-based first-order rule learning (2007, background): “It has been shown to be NP-hard and is also hard to approximate up to a fixed constant (Ben-David et al. 2003).”
Hardness results for agnostically learning low-degree polynomial threshold functions (2010, background): “The Maximum Agreement problem for halfspaces over R was shown to be NPhard to approximate within some constant factor in [1, 2].”