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_22: 
@cite_36: We investigate relations between average case complexity and the complexity of approximation. Our preliminary findings indicate that this is a research direction that leads to interesting insights. Under the assumption that refuting 3SAT is hard on average on a natural distribution, we derive hardness of approximation results for min bisection, dense k-subgraph, max bipartite clique and the 2-catalog segmentation problem. No NP-hardness of approximation results are currently known for these problems.
@cite_21: Using the recently developed framework of (2014), we show that under a natural assumption on the complexity of random K-SAT, learning DNF formulas is hard. Furthermore, the same assumption implies the hardness of various learning problems, including intersections of !(log(n)) halfspaces, agnostically learning conjunctions, as well as virtually all (distribution free) learning problems that were previously shown hard (under various complexity assumptions).
@cite_13: The increased availability of data in recent years has led several authors to ask whether it is possible to use data as a computational resource. That is, if more data is available, beyond the sample complexity limit, is it possible to use the extra examples to speed up the computation time required to perform the learning task? We give the first positive answer to this question for a natural supervised learning problem --- we consider agnostic PAC learning of halfspaces over @math -sparse vectors in @math . This class is inefficiently learnable using @math examples. Our main contribution is a novel, non-cryptographic, methodology for establishing computational-statistical gaps, which allows us to show that, under a widely believed assumption that refuting random @math formulas is hard, it is impossible to efficiently learn this class using only @math examples. We further show that under stronger hardness assumptions, even @math examples do not suffice. On the other hand, we show a new algorithm that learns this class efficiently using @math examples. This formally establishes the tradeoff between sample and computational complexity for a natural supervised learning problem.
@cite_66: Let @math be a @math -ary predicate over a finite alphabet. Consider a random CSP @math instance @math over @math variables with @math constraints. When @math the instance @math will be unsatisfiable with high probability, and we want to find a refutation - i.e., a certificate of unsatisfiability. When @math is the @math -ary OR predicate, this is the well studied problem of refuting random @math -SAT formulas, and an efficient algorithm is known only when @math . Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a @math -ary predicate, having @math constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if @math fails to support a @math -wise uniform distribution, then there is an efficient algorithm that refutes random CSP @math instances @math whp when @math . Indeed, our algorithm will "somewhat strongly" refute @math , certifying @math , if @math then we get the strongest possible refutation, certifying @math . This last result is new even in the context of random @math -SAT. Regarding the optimality of our @math requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP @math may be impossible when @math . Thus there is an indication our algorithm's dependence on @math is optimal for every @math , at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the @math -round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.
In a recent paper @cite_22 (see also @cite_13 ) we, together with Linial and Shalev-Shwartz, developed a new framework to prove hardness of learning based on hardness on average of CSP problems. Yet, in @cite_22 we were not able to use our technique to establish hardness results that are based on a natural assumption on a well studied problem. Rather, we made a rather speculative hardness assumption, that is concerned with general @math problems, most of which were never studied explicitly. We recognized it as the main weakness of our approach, and therefore the main direction for further research. About a year after, Allen, O'Donnell and Witmer @cite_66 refuted the assumption of @cite_22 . On the other hand we @cite_21 were able to overcome the use of our speculative assumption, and prove hardness of learning of DNF formulas (and other problems) based on a natural assumption on the complexity of refuting random @math -SAT instances, in the spirit of Feige's assumption @cite_36 . The current paper continues this line of work.