More data speeds up training time in learning halfspaces over sparse vectors
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 3-sparse vectors in {−1, 1, 0}
n . This class is inefficiently learnable using O n/ 2 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 3CNF formulas is hard, it is impossible to efficiently learn this class using only O n/ 2 examples. We further show that under stronger hardness assumptions, even O n 1.499 / 2 examples do not suffice. On the other hand, we show a new algorithm that learns this class efficiently usingΩ n 2 / 2 examples. This formally establishes the tradeoff between sample and computational complexity for a natural supervised learning problem.
On page 2 -- you say that it is impossible to use 
      standard reductions for proving NP-hardness. I'd say that this issue 
      is a bit more subtle: It seems that some classes of reduction will not 
      allow basing hardness of learning on RP \neq NP. (Cite the paper by 
      Applebaum, Barak and Xiao). You make the point that you are not 
      basing your results on cryptographic ssumptions. However, it is not clear 
      (at least to me) that the complexity-theoretic assumption you are 
      using is necessarily weaker than assuming the existence of one-way 
      functions. Possibly, there is some evidence that the assumption that 
      there are average-case hard functions in NP is "weaker" than one-way 
      functions exist. There are some results by Noam Livne indicating such 
      a possibility. You should discuss the relative hardness of assumptions you 
      are using vs. those that others have used. For example, is it obvious 
      that the result you have holds under a strong-enough cryptographic 
      assumption such as factoring is hard? I suspect it should be possible. 
      For the upper bounds: I think using your techniques, it should be 
      possible to show that H_{n, k+1} can be learnt using 
      \tilde{O}(n^k/\epsilon^2) samples? Is that right? Also, do you think 
      it is possible to push the lower-bound (using a different assumption?) 
      to show that as k gets large the gap between information-theoretic 
      sample complexity and complexity increases? Minor comments: 
      --------------- 1. Line 130: The proof **of** item 1. 2. On 
      line 343, you mean y_k = b right? -- I think adding a 
      discussion about your complexity assumption (with respect to other such 
      assumptions) will enhance the value of your paper, and will be 
      particularly appealing to a theory audience. In particular, your result 
      shows that "hardness conjectures" in learning appear to be weaker than 
      other conjectures that people have been willing to make in other areas. 
      I agree that showing a simple concept class for which a separation 
      exists is interesting. In that sense, I really like your result. However, 
      it may help if you clarify explicitly in the writing that you don't 
      necessarily claim your assumption to be weaker than existence of one-way 
      functions (as it may implicitly appear to say so).