Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
We develop a general duality between neural networks and compositional kernel Hilbert spaces. We introduce the notion of a computation skeleton, an acyclic graph that succinctly describes both a family of neural networks and a kernel space. Random neural networks are generated from a skeleton through node replication followed by sampling from a normal distribution to assign weights. The kernel space consists of functions that arise by compositions, averaging, and non-linear transformations governed by the skeleton's graph topology and activation functions. We prove that random networks induce representations which approximate the kernel space. In particular, it follows that random weight initialization often yields a favorable starting point for optimization despite the worst-case intractability of training neural networks.
The authors introduce the notion of computational skeleton and show how a skeleton can be related to a RKHS (more precisely, to a compositional kernel) through the concept of "dual activation".  They also introduce a class of neural networks, called "realisation of a skeleton", defined through a given number of replications of a computational skeleton and a given number a of outputs (r and k, respectively).  The main results of the paper consist in analysing in what sense the representation generated by a random initialisation of such a neural network (i.e., a skeleton realisation) approximates the compositional kernel related to the underlying skeleton. 
# Some typos/remarks:  -At line 154, do the authors mean "any continuous PSD function"? -Two typos at lines 171 (y instead of x') and 177 ("of in the induced space").  -I am not sure about the meaning of the "2-norm" mentioned at lines 173 and 184, maybe the author should specify it.  -At line 190, S is a computational skeleton, and k_{S} is a compositional kernel.  -In Lemma 11 (appendix), I do not really understand what does b_{|A|} mean.    #Questions (maybe not founded...):  -Is it possible to interpret the fact that "for a random activation, the empirical kernel k_w approximates the kernel k_S", as a kind of "law of large numbers", in the sense: "the replication of the computation skeleton counterbalances the fact that the weight of the network are random"?   -What kind of impact the operation of "learning the weights of the network" could have, for instance, on the relation between k_w and k_S (and on the related Hilbert spaces)?   -Is it possible, in view of Thm. 5 and 6, to draw a parallel between "learning with a skeleton realisation" and "learning with a compositional kernel"?   ########################################### ### After rebuttal  My major concern about the paper is the lack of discussion on "why these results may be important or interesting". In fact, there is almost no discussion at all about the implication of the results of the paper.   The notions of "computational skeleton" and "realisation of a skeleton" seem relatively interesting and aim at generalising the kernel construction proposed in [13] and [29]. This "construction" is in my view the main contribution of the paper.   On a theoretical point of view and from my understanding, the main results of the paper are Thm 3. and 4. However, these results are not "so surprising", since, as confirmed by the authors, they can be interpreted as a kind of "law of large number": the random activation of the network is "counterbalanced" by the replication of the skeleton. Note that there is a big typo in eq. (12) of the supplementary material. As indicated by Table 1, some results of this type are already known.   From my understanding, Thm 5 and 6 are in fact just "advanced corollaries" of Thm 3. and 4 (as indicated at line 586 of the appendix, with a typo).  In their feedback, the authors indicate (about Thm 5 and 6) that: "this shows that training the final layer is essentially equivalent to learning with the corresponding kernel". However, for "kernel-based learning" (line 82), the authors deal with the classical "loss + regularisation" formulation, while classically, "only loss" is considered for "Neural Network-based learning" (line 74); so that I do not really understand how "training the final layer" could be sensitive to "the size of the ball in the RKHS".  In my view and from my understanding, these results are about "the difference between learning with K_S or K_w in the classical framework of kernel-based learning", so that I do not really agree with the answer of the authors.   Another "drawback" of the approach is, in my opinion, that the input space is restricted to be of "hypersphere-type".    Finally, the paper is quite difficult to read and its construction may, in my opinion, be improved in order to try to clarify and simplify the paper.