A key element of understanding the efficacy of overparameterized neural networks is characterizing how they represent functions as the number of weights in the network approaches infinity. In this paper, we characterize the norm required to realize a function f : R d → R as a single hidden-layer ReLU network with an unbounded number of units (infinite width), but where the Euclidean norm of the weights is bounded, including precisely characterizing which functions can be realized with finite norm. This was settled for univariate functions f : R → R in Savarese et al. (2019), where it was shown that the required norm is determined by the L 1 -norm of the second derivative of the function. We extend the characterization to multi-variate functions (d ≥ 2, i.e., multiple input units), relating the required norm to the L 1 -norm of the Radon transform of a (d + 1)/2-power Laplacian of the function. This characterization allows us to show that all functions in Sobolev spaces W s,1 (R d ), s ≥ d + 1, can be represented with bounded norm, to calculate the required norm for several specific functions, and to obtain a depth separation result. These results have important implications for understanding generalization performance and the distinction between neural networks and more traditional kernel learning.
The paper studies the function space regularization behavior of learning with an infinite-width ReLU network with a bound on the l2 norm of weights, in arbitrary dimension, extending the univariate study of Savarese et al. (2019).
The authors show that the corresponding regularization function is more or less an L1 norm of the (weak) (d+1)st derivatives of the function, and provide a rigorous formal characterization in terms of the "R-norm", which is expressed via duality through the Radon transform and powers of the Laplacian.
In addition, the paper provides a number of implications of this study, such as approximation results through Sobolev spaces, an analysis of the norm of radial bump functions, and a new type of depth separation result in terms of norm as opposed to width.
Overall, this is a strong paper making several interesting and important contributions for our understanding of the inductive bias of ReLU networks. I thus recommend acceptance.
A few comments:
* is it possible to obtain precise characterizations of interpolating solutions in this setting (other than a mere representer theorem with ReLUs), as done in Savarese et al (2019, Theorem 3.3) for the univariate case?
* perhaps the results of Section 5.1 should be contrasted with those of Bach (2017, e.g. Prop. 5), which only require ~ d/2 derivatives instead of ~ d here, albeit with stronger requirements, for essentially the same functional space (though the approximation result is obtained from an associated RKHS, which is smaller).
* are the results on radial bump functions intended to provide insight on approximation or depth separation? what was the motivation behind this section?
Other minor comments/typos:
- after Prop. 1: "intertwining" appears twice
- eq. (22): missing f in l.h.s.
- eq. (23): is the first minus sign needed?
- before Thm. 1: point to which Appendix
- Section 4.1, "In particular, this is what would happen ... d+1": this should be further explained
- Section 4.1, final paragraph, "in order R-norm to be": rephrase
- Section 5.4, "required norm with three layers is finite": which norm? maybe point to a reference? Also, Example 5 could be explained in further detail
- Section 5.5: what is an RKHS semi-norm? you'd always have ||f|| = 0 => f = 0 in an RKHS, by the reproducing property