We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution @math on @math . We define @math as the least error of a halfspace classifier for @math . A learner who can access @math has to return a hypothesis whose error is small compared to @math . Using the recently developed method of the author, Linial and Shalev-Shwartz we prove hardness of learning results under a natural assumption on the complexity of refuting random @math - @math formulas. We show that no efficient learning algorithm has non-trivial worst-case performance even under the guarantees that @math for arbitrarily small constant @math , and that @math is supported in @math . Namely, even under these favorable conditions its error must be @math for every @math . In particular, no efficient algorithm can achieve a constant approximation ratio. Under a stronger version of the assumption (where @math can be poly-logarithmic in @math ), we can take @math for arbitrarily small @math . Interestingly, this is even stronger than the best known lower bounds (Arora et. al. 1993, Feldamn et. al. 2006, Guruswami and Raghavendra 2006) for the case that the learner is restricted to return a halfspace classifier (i.e. proper learning).
@cite_35: 
@cite_64: The computational complexity of learning Boolean concepts from examples is investigated. It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP. These classes include (a) disjunctions of two monomials, (b) Boolean threshold functions, and (c) Boolean formulas in which each variable occurs at most once. Relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.
@cite_70: We prove the following about the Nearest Lattice Vector Problem (in any l sub p norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some spl epsiv >0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2 sup log(0.5- spl epsiv ) sup n then NP is in quasi-polynomial deterministic time: NP spl sube DTIME(n sup poly(log sup n) ). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l sub spl infin norm. Improving the factor 2 sup log(0.5- spl epsiv ) sup n to spl radic (dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l sub 2 norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem. >
@cite_54: 
@cite_59: We investigate the computational complexity of two closely related classes of combinatorial optimization problems for linear systems which arise in various fields such as machine learning, operations research and pattern recognition. In the first class (Min ULR) one wishes, given a possibly infeasible system of linear relations, to find a solution that violates as few relations as possible while satisfying all the others. In the second class (Min RVLS) the linear system is supposed to be feasible and one looks for a solution with as few nonzero variables as possible. For both Min ULR and Min RVLS the four basic types of relational operators =, ⩾, > and ≠ are considered. While Min RVLS with equations was mentioned to be NP-hard in (Garey and Johnson, 1979), we established in (Amaldi; 1992; Amaldi and Kann, 1995) that min ULR with equalities and inequalities are NP-hard even when restricted to homogeneous systems with bipolar coefficients. The latter problems have been shown hard to approximate in (, 1993). In this paper we determine strong bounds on the approximability of various variants of Min RVLS and min ULR, including constrained ones where the variables are restricted to take binary values or where some relations are mandatory while others are optional. The various NP-hard versions turn out to have different approximability properties depending on the type of relations and the additional constraints, but none of them can be approximated within any constant factor, unless P = NP. Particular attention is devoted to two interesting special cases that occur in discriminant analysis and machine learning. In particular, we disprove a conjecture of van Horn and Martinez (1992) regarding the existence of a polynomial-time algorithm to design linear classifiers (or perceptrons) that involve a close-to-minimum number of features.
@cite_49: We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random classification noise, also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding learning under the uniform distribution to learning of noisy parities. We show that under the uniform distribution, learning parities with adversarial classification noise reduces to learning parities with random classification noise. Together with the parity learning algorithm of [5], this gives the first nontrivial algorithm for learning parities with adversarial noise. We show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables. We show that learning of k-juntas reduces to learning noisy parities of k variables. These reductions work even in the presence of random classification noise in the original DNF or junta. We then consider the problem of learning halfspaces over Q ^n with adversarial noise or finding a halfspace that maximizes the agreement rate with a given set of examples. We prove an essentially optimal hardness factor of 2- , improving the factor of 85 84 - due to Bshouty and Burroughs [8]. Finally, we show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem.
@cite_31: 
@cite_10: 
@cite_25: Throughout the 1960s I worked on combinatorial optimization problems including logic circuit design with Paul Roth and assembly line balancing and the traveling salesman problem with Mike Held. These experiences made me aware that seemingly simple discrete optimization problems could hold the seeds of combinatorial explosions. The work of Dantzig, Fulkerson, Hoffman, Edmonds, Lawler and other pioneers on network flows, matching and matroids acquainted me with the elegant and efficient algorithms that were sometimes possible. Jack Edmonds’ papers and a few key discussions with him drew my attention to the crucial distinction between polynomial-time and superpolynomial-time solvability. I was also influenced by Jack’s emphasis on min-max theorems as a tool for fast verification of optimal solutions, which foreshadowed Steve Cook’s definition of the complexity class NP. Another influence was George Dantzig’s suggestion that integer programming could serve as a universal format for combinatorial optimization problems.
When we restrict the algorithms to return a halfspace classifier, the problem of learning halfspaces is essentially equivalent @cite_64 to the computational problem of minimizing disagreements . In this problem we are given a sample @math , and the goal is to find a vector @math that minimizes the fraction of pairs with @math . The optimal fraction is called the error of the sample. As a standard" and basic computational problem, much is known about it. The problem have been shown @math -hard already in Karp's famous paper @cite_25 . Soon after the discovery of the PCP theorem, Arora, Babai, Stern and Sweedyk @cite_70 have shown that assuming that no quasi-polynomial time algorithm can solve @math -hard problems, there is no efficient algorithm with an approximation ratio of @math . Later on, the corresponding maximization problem was considered by several authors @cite_59 @cite_10 @cite_31 @cite_35 @cite_54 , culminating with Feldman, Gopalan, Khot and Ponnuswami @cite_49 who showed that assuming that no quasi-polynomial time algorithm can solve @math hard problems, no efficient algorithm can distinguish samples with error @math from samples with error @math .