<p>In general, when we say an algorithm <span class="math-container">$A$</span> PAC learns <span class="math-container">$C$</span> in time <span class="math-container">$t$</span>, we say <span class="math-container">$A$</span> takes time <span class="math-container">$t$</span> before outputting a hypothesis <span class="math-container">$h$</span>, and the hypothesis can be evaluated (on every <span class="math-container">$x$</span>) in time <span class="math-container">$t$</span>. </p>

<p>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 <span class="math-container">$t$</span>? Or does one only worry about how long it takes to evaluate <span class="math-container">$h$</span>? If the output is a truth table, can't every hypothesis be evaluated in time <span class="math-container">$1$</span> already?</p>

CC BY-SA 4.0
2019-03-24T16:52:22.257Z
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.
Sasho Nikolov
CC BY-SA 4.0
2019-03-28T18:30:27.167Z
To complement what @SashoNikolov wrote: this is Section 1.2 of the [Kearns—Vazirani book](https://mitpress.mit.edu/books/introduction-computational-learning-theory), discussing the *representation scheme*. See Definition 2 "(The PAC model, Modified Definition)" which incorporates it.
Clement C.
<cc.complexity-theory><computability><machine-learning><time-complexity><lg.learning>
how is time complexity defined in computational learning theory
wwjohnsmith
# how is time complexity defined in computational learning theory

(Asked by: username_0 on 2019-03-23)

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?

**Tags:** cc.complexity-theory, computability, machine-learning, time-complexity, lg.learning
> **Comments:**
> **username_1**: 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.  
> **username_2**: To complement what @SashoNikolov wrote: this is Section 1.2 of the [Kearns—Vazirani book](https://mitpress.mit.edu/books/introduction-computational-learning-theory), discussing the *representation scheme*. See Definition 2 "(The PAC model, Modified Definition)" which incorporates it.  

---

## 0 answers

