Supervised learning with no prior information I am now reading two modern books on machine learning theory. Both of them emphasize that, in order to succeed in supervised learning, one must choose a good hypothesis class. "Good" means that it is sufficiently simple (formally, has a low VC dimension) and that it contains the true hypothesis or sufficiently close hypotheses. One also mentions the "no free lunch theorem", which says that, without such prior knowledge, you cannot have meaningful learning.

But what do I do if I have no prior knowledge? I have no idea how the correct hypothesis looks like, I do not know if it will be simple or complex. All I have is the training data. Isn't there anything useful I can do with them?

I am thinking of a newly born child. He has no prior knowledge, all he has are "training samples" given by his parents/teachers, and it is still sufficient for meaningful learning.  You could say that each child is born with some prior knowledge wired into his brain, but then the question is:  where such prior knowledge comes from? And again, what should a person do in a new situation on which his wired prior-knowledge is useless?

To sum, my question is: what is a supervised learning paradigm that can be applied without any prior knowledge on the set of possible hypotheses?
I think that the success of a newborn child follows from the fact that the phenomena he's trying to learn is describable (or can be sufficiently approximated) by the hypothesis class generated by the learning algorithm which is going on in his brain. 

This is of course, not formal in any way, but say a baby is equipped with some neural network (of fixed depth), and upon receiving new data, the weights are updated accordingly using some algorithm.

The choice of neural network doesn't really matter, simply imagine that you have carefully studied the processes going on inside the human brain, and found out that the human learning process is similar to using a neural net.

In that case, the image of the learning algorithm is some class $\mathcal{F}$, say functions expressible by some fixed depth nets, and the success of the baby in learning new things simply means that the phenomena he's trying to learn is captured by $\mathcal{F}$ (so nothing magical/contradicting what you quoted is going on).

To make sure this answer does more than just contain some of my random thoughts, I will add that if you truly know nothing, there is nothing you can hope to learn. The data you're receiving could always be generated from the uniform distribution, i.e. someone is tossing a coin and giving you the outcome. Obviously, in that case, you can not hope for a small generalization error.