Summary
This paper presents the state of art result on generalizaiton bound of deep neural networks using path norm. In detail, it allows to consider any neural netowrks whose backbone is a DAG and the activation function is either identity, ReLU, or max pooling. Because this result handles any DAG, one can append a dimension of value equal to constant 1 for all data to extend the analysis networks with bias. Because the theoretical result in thie paper is so general, for the first time, the authors are able to evaluate the actual generalization bound on ResNet trained on Imagenet. Though the path norm based bound presented in this paper is still vacuous, this paper contains several instereting experimental findings and shed light to future researches.
Strengths
1. This paper is very well-written. It is very easy for me to understand the main result and the main theoretical challenges to overcome. The notations are consistent and the mathematical statements are precise. I checked the proofs of several core lemmas and they all look correct to me.
2. The result presented in this paper is very elegant, which unifies several previous results on path-norm. The core proof strategy is a new peeling argument, which relates the Rademacher complexity over a set of nodes to that of the incoming nodes of the set of nodes. The proof uses several new lemmas, which generalizes previous results.
3. The authors not only derive a better and unified path-norm generalization bound but also apply their bound on real datasets and architectures, i.e. ResNets of various sizes on Imagenets. Though their experimental results indicate that the new path norm-based bounds are still vacuous, they note that sparse networks greatly reduce the bound, which may shed light for future research.
Weaknesses
1. I think Setting 1 of Lemma C.1 can be obtained by a simple application of the well-known scalar contraction inequality (Ledoux & Talagrand, 1991). Given $v\in V$ and $t\in T^v$, we can embed it into a higher dimensional space $\mathbb{R}^{I\times T}$ by defining $\tilde t(v,t) = [0, 0 ,\ldots, v,\ldots, 0]$ as a $I\times T$ matrix. We further define $\tilde f_{i,v}(x) = f_i(x)$ for all $x\in\mathbb{R}$. Therefore we have the following which is exactly the conclusion of Setting 1 of Lemma C.1
$$\mathbb{E} \max_{v \in V} \sup_{t \in T^v} G \left( \sum_{i \in I} \varepsilon_{i,v} f_i(t_i) \right) $$
$$=\mathbb{E} \max_{v \in V} \sup_{t \in T^v} G \left( \sum_{i \in I} \varepsilon_{i,v} f_i([\tilde t(v,t)] _{i,v}) \right)$$
$$=\mathbb{E} \max_{v \in V} \sup_{t \in T^v} G \left( \sum_{i \in I, v' \in V} \varepsilon_{i,v'} \tilde f_{i,v'}([\tilde t(v,t)] _{i,v'}) \right)$$
$$= \mathbb{E} \max_{v \in V} \sup_{t \in T^v} G \left( \sum_{i \in I, v' \in V} \varepsilon_{i,v'} [\tilde t(v,t)] _{i,v'} \right) $$
$$=\mathbb{E} \max_{v \in V} \sup_{t \in T^v} G \left( \sum_{i \in I} \varepsilon_{i,v} [\tilde t(v,t)] _{i,v} \right)$$
$$=\mathbb{E} \max_{v \in V} \sup_{t \in T^v} G \left( \sum_{i \in I} \varepsilon_{i,v} t_i \right) $$
Questions
1. measurable condition in Lemma D.1 seems unnecessary?
2. Why 2-norm of $\Phi(\theta)$ is relevant? Isn't it small just because the number of paths is huge? It doesn't seem to be a valid generalization bound even for a very simple 2-layer linear network. Is there any real evidence that 2-norm of $\Phi(\theta)$ could be useful for indicating generalization?
3. Some minor typos: (1). $\overline N_{in}$ seems not defined in appendix A; (2). The third row of the first equation on page 29 seems missing a factor of $5^d$
4. I wonder if the authors can just ignore all the linear activations by linking the incoming nodes of the current nodes to the outgoing nodes of the current node. This should not change the path norm. If this is true, then we should not count the number of Conv layers in ResNet, but the max number of ReLU and max pooling along the path, which is smaller than the former for ResNets.
5. Though the writing quality is already great, I still feel like the paper can benefit from first providing a result without any bias, which would greatly simplify the notations in the theoretical statement and the proof. Then the authors can point out that the results can be generalized to networks with bias by appending a constant 1 dimension in the input (as it is done now), adding an edge between the constant 1 input dimension to the neuron, and then calling the main result. Writing the theorem in this way would clearly explain to the readers where the plus one in $d_{in}+1$ and the $\max(n,\ldots)$ in $\sigma$ comes from. (Theorem 3.1)
6. The statement of Lemma D.2 is a little bit confusing because $\Theta$ is not arbitrary, but the one preprocessed by Algorithm 1. Maybe it is more clear to just define $r$ as the sup of 1-norm of the last layer of $\Theta$? A similar issue occurs for Lemma D.3, where the authors can just say the 1-norm of incoming weights of non-output node in $\Theta$ are bounded. In this way, Lemma D.2 and Lemma D.2 will together motivate Algorithm 1 and the path norm as a generalization metric.
Rating
8: accept, good paper
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.