On the Learnability of Deep Random Networks

Very little is understood about the exact class of functions learnable with deep neural networks. Note that we are differentiating between representability and learnability. The former simply means that there exists a deep network that can represent the function to be learned, while the latter means that it can be learned in a reasonable amount of time via a method such as gradient descent. While several natural functions seem learnable, at least to some degree by deep networks, we do not quite understand the specific properties they exhibit that makes them learnable. The fact that they can be learned means that they can be represented by a deep network. Thus, it is important to understand the class of functions that can be represented by deep networks (as teacher networks) that are learnable (by any student network).