<p>I will formalize a variant of this question where "efficiency" is replaced by "computability".</p>

<p>Let <span class="math-container">$C_n$</span> be the concept class of all languages <span class="math-container">$L\subseteq\Sigma^*$</span>
recognizable by Turing machines on <span class="math-container">$n$</span> states or fewer.
In general, for <span class="math-container">$x\in\Sigma^*$</span> and <span class="math-container">$f\in C_n$</span>, the problem of evaluating
<span class="math-container">$f(x)$</span> is undecidable.</p>

<p>However, suppose we have access to a (proper, realizable)
PAC-learning oracle <span class="math-container">$A$</span>
for <span class="math-container">$C_n$</span>. That is, for any <span class="math-container">$\epsilon,\delta&gt;0$</span>,
the oracle requests
a labeled sample of size
<span class="math-container">$m_0(n,\epsilon,\delta)$</span> 
such that, assuming such a sample was drawn iid from
an unknown distribution <span class="math-container">$D$</span>,
the oracle <span class="math-container">$A$</span> outputs a hypothesis <span class="math-container">$\hat f\in C_n$</span>
which, with probability at least <span class="math-container">$1-\delta$</span>, has <span class="math-container">$D$</span>-generalization error
not more than <span class="math-container">$\epsilon$</span>.
We will show that this oracle is not Turing-computable.</p>

<p>Actually, we will show that a simpler problem is undecidable:
One of determining,
given a labeled sample <span class="math-container">$S$</span>,
whether there exists an <span class="math-container">$f\in C_n$</span> consistent with <span class="math-container">$S$</span>.
Suppose (to get a contradiction) that <span class="math-container">$K$</span> is a Turing machine
that decides the consistency problem.</p>

<p>We make the following notational conventions.
Identify <span class="math-container">$\Sigma^*$</span> with <span class="math-container">$\mathbb{N}=\{0,1,2,\ldots\}$</span> via the usual
lexicographic ordering.
For <span class="math-container">$x\in\{0,1\}^*$</span>, we say that a TM <span class="math-container">$M$</span> "S-prints"
<span class="math-container">$x$</span> if it accepts all of the strings in <span class="math-container">$\Sigma^*$</span>
corresponding to the indices <span class="math-container">$i$</span> s.t. <span class="math-container">$x_i=1$</span>
and does not accept (possibly by not halting)
any of the strings
corresponding to the indices <span class="math-container">$x_i=0$</span>.
Since (by assumption) <span class="math-container">$K$</span> is
decidable,
it follows that the function <span class="math-container">$\tilde K:x\mapsto k$</span>,
defined to be the smallest <span class="math-container">$k$</span> such that some TM in <span class="math-container">$C_k$</span>
S-prints <span class="math-container">$x$</span>, is Turing-computable.
It further follows that
the function
<span class="math-container">$g:k\mapsto x$</span>, which maps a <span class="math-container">$k\in\mathbb{N}$</span>
to the least (lexicographically) string <span class="math-container">$x\in\{0,1\}^*$</span>
such that <span class="math-container">$\tilde K(x)&gt;k$</span>, is also computable.</p>

<p>Now define the TM <span class="math-container">$M$</span> as follows: <span class="math-container">$M$</span> S-prints <span class="math-container">$g(|\langle M\rangle|)$</span>,
where
<span class="math-container">$\langle M\rangle$</span> is the encoding of <span class="math-container">$M$</span>,
<span class="math-container">$|x|$</span> denotes string length, and the recursion theorem
is being invoked to assert the existence of such an <span class="math-container">$M$</span>.
Then <span class="math-container">$M$</span> has some encoding length, <span class="math-container">$\ell=|\langle M\rangle|$</span>,
and it S-prints some string, <span class="math-container">$x_M\in\{0,1\}^*$</span>.
By construction, <span class="math-container">$\tilde K(x_M)&gt;\ell$</span>, and so <span class="math-container">$x_M$</span> cannot be S-printed
by any TM with description length <span class="math-container">$\ell$</span> or shorter. And yet it is defined
as the S-print output of a TM with description length <span class="math-container">$\ell$</span> --- a contradiction.</p>

CC BY-SA 3.0
2017-10-09T10:29:11.520Z
Challenge: convert my "infinitary" argument via computability to a finitary one via efficiency. I think the answer to @minkov's question is negative: You cannot efficiently learn a function class which you cannot efficiently evaluate. I think this will continue to be true if you move beyond proper or realizable PAC.
Aryeh
CC BY-SA 4.0
2017-10-09T10:25:31.360Z
2018-11-17T22:23:21.563Z
2018-11-17T22:23:21.563Z
Aryeh
<p>We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable") can be expressed by polynomial neural networks with reasonable sizes, and thus can be learned with polynomial sample complexity ("learnable") under any input distributions. </p>

<p>Here "learnable" only concerns the sample complexity, regardless of the computational complexity. </p>

<p>I am wondering about a very closely related problem: does there exist a function that can not be efficiently computed by Turing machine in polynomial time ("not efficiently computable"), but meanwhile, can be learned with polynomial sample complexity ("learnable") under any input distributions?</p>

<ul>
<li>[1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, "<a href="https://arxiv.org/abs/1410.1141" rel="nofollow noreferrer">On the Computational Efficiency of Training Neural Networks</a>", 2014</li>
</ul>

CC BY-SA 3.0
2017-10-05T17:41:18.303Z
I take issue with "and thus can be learned". There are very efficiently computable functions (say, DFAs) that are VERY difficult to learn, even approximately.
Aryeh
CC BY-SA 3.0
2017-10-05T18:23:43.743Z
@Aryeh Yes you are right. But if I am correct the difficulty in learning DFAs is in its computational complexity. Given infinite computational power, we may still be able to learn them with polynomial samples via ERM?
Minkov
CC BY-SA 3.0
2017-10-05T21:02:00.963Z
Yes, of course -- just find the smallest DFA consistent with the sample (for the realizable case).
Aryeh
CC BY-SA 3.0
2017-10-05T23:19:18.517Z
Good question, and more subtle than appears at first.
Aryeh
CC BY-SA 3.0
2017-10-06T00:34:16.557Z
@Aryeh Thanks for pointing out the example of DFA!
Minkov
CC BY-SA 3.0
2017-10-06T20:17:31.370Z
This is probably missing the point, but what about the class of (say) $2^{-\sqrt{n}}$-biased Boolean functions? (I.e., more or less, a random function with each value being independently $1$ with probability $2^{-\sqrt{n}}$). For any $\varepsilon > 2^{-\sqrt{n}}$, PAC-learning under the uniform distribution is trivial (0 sample needed, the constant function $0$ is a good hypothesis), but it seems like any evaluation algorithm would need to spend superpolynomial time (as there is no structure to the function). I'm most likely misunderstanding the question, though.
Clement C.
CC BY-SA 3.0
2017-10-07T13:08:05.493Z
Your terminology is a bit confusing. When we say “efficiently learnable,” we usually refer to computational efficiency. Just saying “learnable” is sufficient to imply sample efficiency.
Lev Reyzin
CC BY-SA 3.0
2017-10-07T21:36:01.980Z
@ClementC. Good point! I think we need to impose the same requirement on the approximation accuracy of computation as for learning. In your example, if we only require $\epsilon$ approximation accuracy of computation, then the evaluation algorithm can directly return $0$ as the answer without any computation.
Minkov
CC BY-SA 3.0
2017-10-07T21:36:31.893Z
@LevReyzin Thanks for pointing out. I have revised the question accordingly.
Minkov
CC BY-SA 3.0
2017-10-07T21:40:10.347Z
@Minkov To PAC learn, you should learn with respect to any distribution. Otherwise the question is not interesting (as Clement points out).
Lev Reyzin
CC BY-SA 3.0
2017-10-07T23:07:39.537Z
@LevReyzin You are absolutely right. But on the computation side, what would be a more natural way to impose the input distribution?
Minkov
CC BY-SA 3.0
2017-10-08T01:47:50.760Z
You don't impose a distribution, you try to prove it for all distributions.
Lev Reyzin
CC BY-SA 3.0
2017-10-09T10:26:13.380Z
Why are people voting to close? I think this is a deep and subtle question!
Aryeh
<cc.complexity-theory><np-hardness><machine-learning><turing-machines><lg.learning>
Functions that are Not Efficiently Computable but Learnable
Minkov
# Functions that are Not Efficiently Computable but Learnable

(Asked by: username_0 on 2017-10-05)

We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable") can be expressed by polynomial neural networks with reasonable sizes, and thus can be learned with polynomial sample complexity ("learnable") under any input distributions.

Here "learnable" only concerns the sample complexity, regardless of the computational complexity.

I am wondering about a very closely related problem: does there exist a function that can not be efficiently computed by Turing machine in polynomial time ("not efficiently computable"), but meanwhile, can be learned with polynomial sample complexity ("learnable") under any input distributions?

* [1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, "[On the Computational Efficiency of Training Neural Networks](https://arxiv.org/abs/1410.1141)", 2014

**Tags:** cc.complexity-theory, np-hardness, machine-learning, turing-machines, lg.learning

> **Comments:**
> **username_1**: I take issue with "and thus can be learned". There are very efficiently computable functions (say, DFAs) that are VERY difficult to learn, even approximately.  
> **username_0**: @username_1 Yes you are right. But if I am correct the difficulty in learning DFAs is in its computational complexity. Given infinite computational power, we may still be able to learn them with polynomial samples via ERM?  
> **username_1**: Yes, of course -- just find the smallest DFA consistent with the sample (for the realizable case).  
> **username_1**: Good question, and more subtle than appears at first.  
> **username_0**: @username_1 Thanks for pointing out the example of DFA!  
> **username_2**: This is probably missing the point, but what about the class of (say) $2^{-\sqrt{n}}$-biased Boolean functions? (I.e., more or less, a random function with each value being independently $1$ with probability $2^{-\sqrt{n}}$). For any $\varepsilon > 2^{-\sqrt{n}}$, PAC-learning under the uniform distribution is trivial (0 sample needed, the constant function $0$ is a good hypothesis), but it seems like any evaluation algorithm would need to spend superpolynomial time (as there is no structure to the function). I'm most likely misunderstanding the question, though.  
> **username_3**: Your terminology is a bit confusing. When we say “efficiently learnable,” we usually refer to computational efficiency. Just saying “learnable” is sufficient to imply sample efficiency.  
> **username_0**: @ClementC. Good point! I think we need to impose the same requirement on the approximation accuracy of computation as for learning. In your example, if we only require $\epsilon$ approximation accuracy of computation, then the evaluation algorithm can directly return $0$ as the answer without any computation.  
> **username_0**: @LevReyzin Thanks for pointing out. I have revised the question accordingly.  
> **username_3**: @username_0 To PAC learn, you should learn with respect to any distribution. Otherwise the question is not interesting (as Clement points out).  
> **username_0**: @LevReyzin You are absolutely right. But on the computation side, what would be a more natural way to impose the input distribution?  
> **username_3**: You don't impose a distribution, you try to prove it for all distributions.  
> **username_1**: Why are people voting to close? I think this is a deep and subtle question!  

---

## 1 answers

### Answer by username_1 on 2017-10-09. Score: 12

I will formalize a variant of this question where "efficiency" is replaced by "computability".

Let $C\_n$ be the concept class of all languages $L\subseteq\Sigma^\*$
recognizable by Turing machines on $n$ states or fewer.
In general, for $x\in\Sigma^\*$ and $f\in C\_n$, the problem of evaluating
$f(x)$ is undecidable.

However, suppose we have access to a (proper, realizable)
PAC-learning oracle $A$
for $C\_n$. That is, for any $\epsilon,\delta>0$,
the oracle requests
a labeled sample of size
$m\_0(n,\epsilon,\delta)$
such that, assuming such a sample was drawn iid from
an unknown distribution $D$,
the oracle $A$ outputs a hypothesis $\hat f\in C\_n$
which, with probability at least $1-\delta$, has $D$-generalization error
not more than $\epsilon$.
We will show that this oracle is not Turing-computable.

Actually, we will show that a simpler problem is undecidable:
One of determining,
given a labeled sample $S$,
whether there exists an $f\in C\_n$ consistent with $S$.
Suppose (to get a contradiction) that $K$ is a Turing machine
that decides the consistency problem.

We make the following notational conventions.
Identify $\Sigma^\*$ with $\mathbb{N}=\{0,1,2,\ldots\}$ via the usual
lexicographic ordering.
For $x\in\{0,1\}^\*$, we say that a TM $M$ "S-prints"
$x$ if it accepts all of the strings in $\Sigma^\*$
corresponding to the indices $i$ s.t. $x\_i=1$
and does not accept (possibly by not halting)
any of the strings
corresponding to the indices $x\_i=0$.
Since (by assumption) $K$ is
decidable,
it follows that the function $\tilde K:x\mapsto k$,
defined to be the smallest $k$ such that some TM in $C\_k$
S-prints $x$, is Turing-computable.
It further follows that
the function
$g:k\mapsto x$, which maps a $k\in\mathbb{N}$
to the least (lexicographically) string $x\in\{0,1\}^\*$
such that $\tilde K(x)>k$, is also computable.

Now define the TM $M$ as follows: $M$ S-prints $g(|\langle M\rangle|)$,
where
$\langle M\rangle$ is the encoding of $M$,
$|x|$ denotes string length, and the recursion theorem
is being invoked to assert the existence of such an $M$.
Then $M$ has some encoding length, $\ell=|\langle M\rangle|$,
and it S-prints some string, $x\_M\in\{0,1\}^\*$.
By construction, $\tilde K(x\_M)>\ell$, and so $x\_M$ cannot be S-printed
by any TM with description length $\ell$ or shorter. And yet it is defined
as the S-print output of a TM with description length $\ell$ --- a contradiction.

> **Comments:**
> **username_1**: Challenge: convert my "infinitary" argument via computability to a finitary one via efficiency. I think the answer to @minkov's question is negative: You cannot efficiently learn a function class which you cannot efficiently evaluate. I think this will continue to be true if you move beyond proper or realizable PAC.  

---

