acceptodds
Under review as a conference paper at ICLR 2027

A Structural Approach to Path-Norm-Based Generalization Bounds for Neural Networks

Abstract

While the path-norm has emerged as a theoretically grounded measure of neural network generalization, existing generalization bounds often rely on restrictive assumptions—such as the positive homogeneity of activation functions—and predominantly target basic feedforward or residual architectures. In this paper, we develop an analytical framework that broadens the scope of path-norm theory to modern neural network architectures without relying on potentially loose covering-number estimates. First, by introducing the Absolute Rademacher Complexity, we remove the traditional positive homogeneity requirement and extend path-norm-based bounds to arbitrary Lipschitz-continuous activation functions. Second, we establish continuous-limit path-norm bounds for Neural Ordinary Differential Equations (Neural ODEs). By proving the uniform convergence of Rademacher complexities under Euler discretization, we characterize their generalization complexity through a differential comparison system. Finally, we decompose the self-attention mechanism and combine an element-wise matrix inequality with vector contraction to derive explicit, layer-wise bounds for Transformers. Our structural decomposition approach avoids the theoretical bottlenecks of traditional covering-number methods and provides architectural insights into how continuous-depth dynamics and attention operators contribute to model capacity.

Primary area:
learning theory
Keywords:
Generalization Bounds, Rademacher Complexity, Path Norm, Neural Networks, Deep Learning, Transformers, Neural ODEs, ResNets

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_195qOpenReview ↗
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
  1. How does the bound compare to Neyshabur et al. and Golowich et al. when written explicitly in terms of the weights?
  2. How is the discrete-to-continuous approximation in Theorem 6 justified, and does it require homogeneity?
  3. What are the actual bound values in the experiments?
2 comments

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/mRad(r_{k+1})=A_k Rad(r_k) + B_k/\sqrt{m}. While the core technique of Neyashabur is by adjusting most row columns to zero column except an single expection wiw_i, 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\text{Therefore, for every } \epsilon > 0, \text{ there exists } N \text{ such that for all } n > N,\ f_n \in \mathcal{F}_n

inf⁡f∈FODEsup⁡x∥fn(x)−f(x)∥2<ϵ.\inf_{f \in \mathcal{F}_{\mathrm{ODE}}} \sup_x \|f_n(x)-f(x)\|_2 < \epsilon.

From this result we gain

Fn→FODE\mathcal{F}_n \to \mathcal{F}_{ODE}

since all neural networks of Fn\mathcal{F}_n 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�(�0� and sample size →∞\to \infty.

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 f∗f^{*} being approximated and a sufficient number of samples, if $ |f^{*}| \leq C $ then the large model function ff we eventually train will roughly satisfy $ |f| = O(C) $(We denote ∣⋅∣| \cdot | as sup norm). Furthermore, ∥f∥\|f\| 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: f=Wkσ(Wk−1…σ(W0x))f = W_k \sigma(W_{k-1} \dots \sigma(W_0 x)) We can set W0W_0 such that each element wijxjw_{ij}x_j of W0xW_0 x is positive. In this case, the ReLU activation acts as the identity mapping (ReLU=id\text{ReLU} = \text{id}). Then, by setting subsequent weights WiW_i to be non-negative, we have ∥f∥=∣Wk∣∣Wk−1∣…∣W0∣∣x∣\|f\| = |W_k||W_{k-1}|\dots|W_0||x| where ∣x∣|x| 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.

Reviewer_XpMCOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper constructs path-norm generalization bounds that are directly applicable to a wide class of architectures, including ResNets, Neural ODEs, and Attention layers. The author's approach is to bound the generalization gap using Rademacher complexity (which is a classical approach), and then, to bound the Rademacher complexity with, basically, a network output for which all weights are replaced with their upper-bounds, evaluated at element-wise upper-bound of the input. The paper evaluates the resulting bounds by computing Kendall's tau between the test MSE and generalization gap, and their theoretical Rademacher complexity bound.

Critical strengths

None

Critical weaknesses
  1. The paper's approach, while being advertised as "brand-new", seems only incrementally novel. Indeed, equation (3.9) of [1] provide similar bounds for ResNets, but assuming globally path-norm bounded classes, while the submitted manuscript assumes entry-wise bounded classes. The proof technique also seems similar: it is induction through the layers, using Rademacher contraction and the decomposition of residual connections. [1] is not cited in the manuscript. Moreover, it is not clear how to choose the entry-wise constraints A,BA,B for a trained network. Choosing the entrywise constraints adaptively for a trained network would generally require an additional argument to make the generalization guarantee valid simultaneously over the possible choices. Unlike a global path-norm constraint, the number of independently chosen constraints could be as large as the number of parameters, potentially introducing a substantial additional complexity penalty. In the experiments, authors provide no information on how these constraints are chosen. Moreover, the empirical evaluation primarily reports rank correlations between the proposed bounds and test MSE or the generalization gap. These correlations do not establish whether the resulting generalization bounds are non-vacuous, nor how they compare quantitatively with existing bounds.
  2. While mentioning complexity terms of some bounds in Table 1, the manuscript does not provide any proper comparison to them. In particular, it is not clear how their bounds depend on input and hidden dimensionalities and weight norms. Moreover, their claim "our work establishes a O(1/n)O(1/\sqrt{n}) generalization bound that only depends on norm of parameters." is not sufficiently justified. Although the proposed inequalities exhibit a formal 1/n1/\sqrt n factor, the remaining terms depend on the input complexity and on products of parameter-bound matrices, whose dependence on the input and hidden dimensions is not analyzed. In particular, the bound in Theorem 2 uses coordinate-wise sample maxima, which can themselves grow with the sample size (e.g., as log⁡n\sqrt{\log n} for Gaussian inputs). Consequently, the claimed sample-size and dimension dependence is not fully established without further assumptions.

[1] E, Ma and Wang. Rademacher Complexity and the Generalization Error of Residual Networks. 2020.

Questions for authors

None

2 comments
AuthorsOpenReview ↗

Response to the Reviewer's Concerns

We thank the reviewer for the detailed and constructive feedback. Below we address the concerns point by point.

W1.

We omitted this article when we were searching for relevant contents and we regretted this oversight.We will add this citation to our paper and make comparisons. The main distinction lies in the type of parameter constraints and the resulting complexity characterization. E, Ma, and Wang (2020) derive their bounds using path-based norm constraints, whereas our analysis considers entry-wise constraints on the weight matrices and bias vectors. Specifically, we impose constraints of the form $ |W_k|{ij}\leq \frac{2}{3}(A_k){ij}, \qquad |b_k|i\leq \frac{2}{3}(B_k)i. $ This allows us to derive a coordinate-wise recursion for the absolute Rademacher complexities: $ \rho_{k+1} \leq (I+A_{k+1})\rho_k +\frac{B_{k+1}}{\sqrt m}, $ where (ρk\rho_k) collects the coordinate-wise complexity measures at layer (k).

In contrast, the work by Weinan E directly expands the path norm element-by-element and compares the recurrence relations between them, rather than directly computing the recursion of Rademacher complexity. Therefore, our work represents a paradigm innovation, allowing us to directly analyze the recurrence of complexity and thereby providing a structural framework for more complex computations. The ResNet analysis occupies only a minor portion of the paper; it serves primarily as an illustrative demonstration and a foundational lemma for computing the complexity of Neural ODEs, and thus should not be regarded as the primary contribution of our work.

W2.

We would like to clarify the practical motivation behind our choice of parameter constraints. In practical deep learning, one typically does not prescribe a fixed upper bound on a particular parameter norm before training. Instead, regularization is commonly introduced through the training objective, and its strength is adjusted to balance fitting the training data with controlling the complexity of the learned model. In the interpolation regime, this can be viewed as seeking models that approximately interpolate the training data while having a relatively small value of a chosen regularizer.

This raises a fundamental question: which parameter norm or structural regularizer should one use? A norm that yields a theoretically appealing generalization bound is not necessarily a good practical regularizer. Indeed, previous empirical studies have reported that certain norm measures, such as the matrix (W_{2,2}) norm, may exhibit weak or even negative correlation with generalization performance in particular settings. Our goal is therefore not merely to establish a bound under an arbitrarily prescribed norm constraint, but also to provide a theoretical framework for understanding how entry-wise parameter magnitudes affect complexity propagation through residual networks. Such a characterization may offer guidance for designing and evaluating regularization objectives.

We agree, however, that the distinction between fixed constraints and data-dependent constraint selection should be made explicit. Our theorem establishes the complexity bound conditional on a given set of entry-wise constraints. It does not, by itself, establish a uniform generalization guarantee for constraints selected adaptively using the same training sample.

AuthorsOpenReview ↗

Response to the Reviewer's Concerns

W3.

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.

W4.

We thank the reviewer for raising the concern regarding the asymptotic dependence of our bound on the input dimension.

For a true target function f∗f^{*} being approximated and a sufficient number of samples, if $ |f^{*}| \leq C $ then the large model function ff we eventually train will roughly satisfy $ |f| = O(C) $(We denote ∣⋅∣| \cdot | as sup norm). Furthermore, ∥f∥\|f\| 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: f=Wkσ(Wk−1…σ(W0x))f = W_k \sigma(W_{k-1} \dots \sigma(W_0 x)) We can set W0W_0 such that each element wijxjw_{ij}x_j of W0xW_0 x is positive. In this case, the ReLU activation acts as the identity mapping (ReLU=id\text{ReLU} = \text{id}). Then, by setting subsequent weights WiW_i to be non-negative, we have ∥f∥=∣Wk∣∣Wk−1∣…∣W0∣∣x∣\|f\| = |W_k||W_{k-1}|\dots|W_0||x| where ∣x∣|x| 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.

Reviewer_jmWHOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper develops architecture-aware complexity bounds for networks with entrywise norm constraints. The authors derive Rademacher-complexity bounds with entrywise norm constraints for various hypothesis classes including feedforward networks, ResNets, Neural ODEs and a simplified Transformer. The bounds require propagating a vector of coordinatewise complexity bounds through the architecture. For feedforward networks, the resulting recursion accumulates the products of parameter entrywise bounds along network paths, naturally leading to the path norm.

This paper studies the empirical rademacher complexity and an absolute value variant RadSabs(F)Rad_{S}^{abs}(\mathcal{F}). The absolute value variant is well suited for controlling for signed parameters and enables certain convenient properties the standard empirical version does not admit.

The calculations needed to compute the bounds lead to a recurrence relation: zk+1=Akzk+Bk/mz_{k+1}=A_kz_k+B_k/\sqrt m with zk∈R+dkz_k\in\mathbb R_+^{d_k} bounds the complexity of the dkd_k intermediate class. The recurrence relation captures the complexity bound of the hidden layers, while Ak∈R+dk+1×dkA_k\in\mathbb R_+^{d_{k+1}\times d_k} and Bk∈R+dk+1B_k\in\mathbb R_+^{d_{k+1}} are parameter bounds and other constants. These results are later adapted for different scenarios. In summary, this paper contributes to a long line of research that aims to improve generalization bounds by effectively capturing structure inherent in the interatctions between a predictor and an input.

Critical strengths
  • The recurrence formulation provides a useful perspective for unifying the analysis across diverse architectures and also intuitively motivates the continuous-depth case. The bounds for feedforwards also remove the need for positive homogenity assumptions.

  • The entrywise formulations provides a way to assess contributions across different neurons. The bounds make the dependence on the connectivity between layer parametes more explicit. This property while useful does not immediately correspond to tighter bounds

Critical weaknesses

I had trouble identifying the contribution in comparison to the existing path-norm literature. It describes earlier path-norm work as predominantly empirical. But Neyshabur, Tomioka and Srebro (2015)'s "Norm-Based Capacity Control in Neural Networks" do provide an explicit path-norm Rademacher bound for feedforward relu networks. I think the comparison with this requires more discussion. Also, Bartlett and Mendelson, 2002 Definition 2 does discuss an absolute value variant of the more common defintion of empirical rademacher complexity. It is unclear whether these ideas translate to better/tighter bounds. Note: This point however doesnt inlcude the other aspects of the authors work like the neural ode part.

Questions for authors

The attention bound derivation might need some work. In Eq. (9), the residual term is there in one line but not in the other (see 1574 and 1579) but the f_1 function does appear to be correct. I suggest the authors check their derivations.

1 comment
AuthorsOpenReview ↗

Response to the Reviewer's Concerns

We thank the reviewer for the detailed and constructive feedback. Below we address the concerns point by point.

W1: Comparison with Neyshabur et al. (2015) & 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/mRad(r_{k+1})=A_k Rad(r_k) + B_k/\sqrt{m}. While the core technique of Neyashabur is by adjusting most row columns to zero column except an single expection wiw_i, 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 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: Regarding Tighter Bounds. We appreciate the reviewer's desire for tighter bounds. 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�(�0� and sample size →∞\to \infty. Our framework achieves these structural and asymptotic goals, even if the absolute constant in the bound is not empirically tight for large language models.

W4: Missing Direct Comparison. We appreciate your suggestion to explicitly compare our work with existing path-norm literature. Our initial focus was on illustrating the generalizability of our own framework across diverse architectures. However, we completely agree that a direct comparison is necessary for clarity. We will add a new part in the revised version to formally contrast our derivation and bounds with Neyshabur (2015), highlighting how our coordinate-wise approach sheds new light on capacity control.

W5 Derivation issue in Eq (9): We sincerely thank the reviewer for catching this. You are absolutely correct that there is an apparent skip between lines 1574 and 1579. We checked our derivation and found a minor algebraic jump omitted in the camera-ready formatting. It is clear that Radabs({c})≤∣c∣mRad^{abs}(\{c\}) \leq \frac{|c|}{\sqrt{m}} where cc is a constant function and data set x1,⋯ ,xm{x_1, \cdots, x_m}. Recall that when we attempt to apply Maurer's contraction lemma we expect h(0,⋯ ,0)=0h(0, \cdots, 0) = 0 for softmax function but it is not true. Therefore we have Radabs(softmax(⋯ ))≤Radabs(softmax′(⋯ ))+Radabs({1n})Rad^{abs}(softmax( \cdots))\leq Rad^{abs}(softmax'(\cdots))+Rad^{abs}(\{\frac{1}{n}\}), where softmax′=softmax−softmax(0,⋯0)softmax'=softmax - softmax(0,\cdots 0) and softmax(0,⋯0)=1nsoftmax(0, \cdots 0)=\frac{1}{n}

We hope these clarifications address your concerns, particularly regarding the fundamental technical novelty of our framework and its broad applicability.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.