A PAC-BAYESIAN APPROACH TO SPECTRALLY-NORMALIZED MARGIN BOUNDS FOR NEURAL NETWORKS
We present a generalization bound for feedforward neural networks with ReLU activations in terms of the product of the spectral norm of the layers and the Frobenius norm of the weights. The key ingredient is a bound on the changes in the output of a network with respect to perturbation of its weights, thereby bounding the sharpness of the network. We combine this perturbation bound with the PAC-Bayes analysis to derive the generalization bound.
This paper combines a simple PAC-Bayes argument with a simple perturbation analysis (Lemma 2) to get a margin based generalization error bound for ReLU neural networks (Theorem 1) which depends on the product of the spectral norms of the layer parameters as well as their Frobenius norm. The main contribution of the paper is the simple proof technique to derive Theorem 1, much simpler than the one use in the very interesting work [Bartlett et al. 2017] (appearing at NIPS 2017) which got an analogous bound but with a dependence on the l1-norm of the layers instead of the Frobenius norm. The authors make a useful comparison between these bounds in Section 3 showing that none is dominating the others, but still analyzing their properties in terms of structural properties of the weight matrices.
I enjoyed reading this paper. One could think that it makes a somewhat incremental contribution with respect to the more complete work (both theory and practice) from [Bartlett et al. 2017]. Nevertheless, the simplicity and elegance of the proof as well as the result might be useful for the community to get progress on the theoretical analysis of NNs.
The paper is well written, though I make some suggestions for the camera ready version below to improve clarity.
I verified most of the math.
== Detailed suggestions ==
1) The authors should specify in the abstract and in the introduction that they are analyzing feedforward neural networks *with ReLU activation functions* so that the current context of the result is more transparent. It is quite unclear how one could generalize the Theorem 1 to arbitrary activation functions phi given the crucial use of the homogeneity of the ReLU at the beginning of p.4. Though the proof of Lemma 2 only appears to be using the 1-Lipschitzness property of phi as well as phi(0) =0. (Unless they can generalize further; I also suggest that they explicitly state in the (interesting) Lemma 2 that it is for the ReLU activations (like they did in Theorem 1)).
2) A footnote (or citation) could be useful to give a hint on how the inequality 1/e beta^(d-1) <= tilde{beta}^(d-1) <= e beta^(d-1) is proven from the property |beta-tilde{beta}|<= 1/d beta (middle of p.4).
3) Equation (3) -- put the missing 2 subscript for the l2 norm of |f_(w+u)(x) - f_w(x)|_2 on the LHS (for clarity).
4) One extra line of derivation would be helpful for the reader to rederive the bound|w|^2/2sigma^2  <= O(...) just above equation (4). I.e. first doing the expansion keeping the beta terms and Frobenius norm sum, and then going directly to the current O(...) term.
5) bottom of p.4: use hat{L}_gamma = 1 instead of L_gamma =1 for more clarity.
6) Top of p.5: the sentence "Since we need tilde{beta} to satisfy (...)" is currently awkwardly stated. I suggest instead to say that "|tilde{beta}- beta| <= 1/d (gamma/2B)^(1/d) is a sufficient condition to have the needed condition |tilde{beta}-beta| <= 1/d beta over this range, thus we can use a cover of size dm^(1/2d)."
7) Typo below (6): citetbarlett2017...
8) Last paragraph p.5: "Recalling that W_i is *at most* a hxh matrix" (as your result do not require constant size layers and covers the rectangular case).