- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper proposes bounding the Rademacher complexity of MLPs, ResNets, Neural ODEs and Transformers by propagating a per-coordinate complexity vector through the network. An "absolute" Rademacher complexity is used to avoid assuming positive homogeneity of the activation.
Critical strengths
The comparison-system view is intuitive. The skip connection shows up as an identity term, and in the continuous limit the complexity follows a simple linear ODE. Extending norm-based analysis to Neural ODEs and attention, and to non-homogeneous activations, is a relevant direction.
Critical weaknesses
My main concern is novelty. Peeling layers with sub-additivity and contraction is essentially the approach of Neyshabur et al. (2015), and the exponential depth factor that comes with it is hidden here in the constraint normalization (|W| ≤ A/2, or 2A/3 for ReLU). This should be discussed directly, especially compared to Golowich et al. (2018). The absolute Rademacher complexity is also the original Bartlett & Mendelson (2002) definition. The paper misses Gonon et al. (ICLR 2024), which already covers biases, ResNets and general architectures (though still assuming homogeneity), so the claim that path-norm theory is "mostly empirical" is not accurate. Several proofs are incomplete. For example, the proof of Lemma 5 is a copy of Lemma 4. In Theorem 6, both parts of the approximation argument start from f ∈ F_ODE, so the direction F_n → F_ODE is never actually shown. The identification of residual blocks with Euler steps also silently uses ReLU homogeneity, which is in tension with the paper's framing of removing the homogeneity assumption, and the concluding sentence of the proof is cut off. The Transformer results assume bounds on data-dependent quantities like |XW_Q| and |Z_{l-1}W|, so the hypothesis class depends on the sample. The claim that the ODE bound is independent of d also seems overstated, since Z(t) is d-dimensional. The experiments only report rank correlations, with no baselines and no actual bound values, and from Figure 2 the bounds appear to be vacuous. MSE with Gaussian noise also doesn't satisfy the bounded-loss assumption of Theorem 1. Finally, there are many wrong theorem references, inconsistent numbers and typos, which make the paper hard to verify.
Questions for authors
- How does the bound compare to Neyshabur et al. and Golowich et al. when written explicitly in terms of the weights?
- How is the discrete-to-continuous approximation in Theorem 6 justified, and does it require homogeneity?
- What are the actual bound values in the experiments?
2 comments
W6.
We thank the reviewer for raising the concern regarding the asymptotic dependence of our bound on the input dimension.
For a true target function being approximated and a sufficient number of samples, if $ |f^{*}| \leq C $ then the large model function we eventually train will roughly satisfy $ |f| = O(C) $(We denote as sup norm). Furthermore, is very directly determined by the path norm. In fact, for ReLU-based MLPs or ResNets, we can reasonably set the signs of the weights to ensure that the maximum value is achieved by the path norm. Therefore, we can heuristically assume that this path norm is controlled by the output magnitude of the true function, thereby achieving dimension-independence.
Take an MLP for example: We can set such that each element of is positive. In this case, the ReLU activation acts as the identity mapping (). Then, by setting subsequent weights to be non-negative, we have where denotes taking the element-wise absolute value. This is exactly the path norm in neural networks. However, the assumption that "there exists a parameterization such that the path norm has a direct relationship with the function output" relies on the assumption that the model can well approximate the true function. This is based on empirical observations rather than rigorous theoretical proof, which is the reason why we did not elaborate extensively on this point in the paper.
W1: Comparison with Neyshabur et al. (2015) ,Golowich et al. (2018)& Fundamental Difference in Proof Techniques. The reviewer mentioned a potential overlap with Neyshabur et al. (2015). Since the review did not specify the exact overlapping parts, we carefully re-examined their original paper and summarize the most likely points of confusion below to clarify our fundamental differences. Although work of Neyashabur(2015) provided complexity bound based on form of the path norm, the proof technique is different from our paper where we provide a very straight forward complexity propagation: Rad(rk+1)=AkRad(rk)+Bk/m. While the core technique of Neyashabur is by adjusting most row columns to zero column except an single expection wi, and it relies on homogeneity of activation function and cannot be transferred to other network structure including resnets. Thus clearly our work is intrinsically different by examining technical details.
The bound for Golowich is $(\prod_{j=1}^{L}|W_j|_{2,2}) \min{\frac{1}{n^{1/4}},\sqrt{\frac{L}{n}}}$。The main advantage is that it does not depend on number of layers exponentially; however, the disadvange is that the proof is very technical, and cannot be exrended to even mlp with non-bias networks. Neither the technique can be extended to complicated modern neural network structure including transformer.
The power of our framework is that this recursive technique extends naturally and consistently to ResNets, Neural ODEs, and Transformers without needing complex, architecture-specific proof techniques.
w2.The Role of MLP in our Paper. We included MLP as we used the basic feed-forward network merely as an illustrative example to help readers intuitively understand how complexity propagates through compositions. It should be not be supposed as the main contribution our our work, but a comprehensive analytical framework of MLP, Resnets, Neural ODE and transformer.
w3.We respectfully but strongly disagree with the reviewer's assessment of the technical correctness of our analysis. We believe that several of the concerns raised in the review stem from misunderstandings of the mathematical arguments presented in the paper.
In particular, the criticism regarding Theorem 6 overlooks the key approximation argument established in our proof. We clarify the relevant steps below and explain why the claimed approximation direction does follow from our construction.
In line 1317- 1320 we sho following result:
Therefore, for every ϵ>0, there exists N such that for all n>N, fn∈Fn
inff∈FODEsupx∥fn(x)−f(x)∥2<ϵ.
From this result we gain
Fn→FODE
since all neural networks of Fn is a slice of a neural ODE.
Similarly, the identification of residual blocks with Euler discretization does not rely on the positive homogeneity of ReLU, as can be verified directly from the derivation.
We therefore believe that these technical concerns do not justify the assessment of the soundness of our results. As review claims that there are many wrong theorem references, inconsistent numbers and typos, which make the paper hard to verify, we sincerely expect review to mention the specific technical detail so that we can rectify.
w4. The repetition of Lemma 5 and Lemma is an accidental typo. The conclusion is actually trivial. we will correct this mistake and it does not affect other proofs.
w5.We would like to clarify the objective of our empirical evaluation. The Kendall tau correlation is primarily used to assess whether our theoretical complexity measure serves as a meaningful predictor of relative generalization performance across different models, rather than to demonstrate that the resulting upper bound is numerically tight.
We believe that the value of a generalization bound is not limited to its numerical tightness. In particular, for modern over-parameterized neural networks, theoretical analyses can also provide structural insights into the relationship between parameter configurations and generalization behavior, and offer guidance for designing effective regularization objectives. As discussed above, identifying an appropriate regularizer is itself an important practical challenge, since a norm that admits a theoretically appealing bound does not necessarily bound actual generalization performance strictly.
While empirical tightness is valuable, we respectfully argue that for modern over-parameterized networks, the primary significance of generalization bounds lies in: (1) providing an efficient theoretical objective for model regularization (helping practitioners choose better norm constraints), and (2) offering asymptotic analysis in the over-parameterized regime (�0� and sample size →∞.