Functions that are Not Efficiently Computable but Learnable 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", 2014
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&gt;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)&gt;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)&gt;\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.