In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$.

Now how is the hypothesis output? In the sense, should the learner write down the truth table/ circuit description? Is the time in describing the hypothesis included in $t$? Or does one only worry about how long it takes to evaluate $h$? If the output is a truth table, can't every hypothesis be evaluated in time $1$ already?

  • 2
    $\begingroup$ I will let someone who is more of an expert on learning theory answer, but let me say that all of these are valid concerns and, as far as I remember, are nicely discussed in Kearns and Vazirani's Computational Learning Theory book. Usually you fix a way to represent a concept (which is almost never a truth table, but could be a circuit) so that the concept can be evaluated efficiently from the representation. Then an efficient learner is allowed to run in time polynomial in the size of the smallest representation. $\endgroup$ – Sasho Nikolov Mar 24 '19 at 16:52
  • $\begingroup$ To complement what @SashoNikolov wrote: this is Section 1.2 of the Kearns—Vazirani book, discussing the representation scheme. See Definition 2 "(The PAC model, Modified Definition)" which incorporates it. $\endgroup$ – Clement C. Mar 28 '19 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.