Path-Norm Bounds for Neural Network Generalization

Why Measure a Network by Its Paths?

A neural network can have many parameters without producing a complicated predictor: for example, it may contain many small contributions that add up to a fixed function. Conversely, a modest number of parameters can have large magnitudes and produce a predictor with a large effective scale. A path norm measures the total absolute weight carried along input-to-output paths. It is unchanged by certain rescalings of hidden units and can therefore describe a network differently from simply counting its parameters.

We define the path norm for layered networks, then derive a capacity bound for a one-hidden-layer ReLU class. The bound illustrates the key point precisely: for this class, a path-norm constraint controls Rademacher complexity without depending on hidden-layer width. The result is not a claim that every deep-network generalization bound is independent of depth or architecture.

Definition and Basic Properties

Consider a scalar-output network with $L$ weight matrices $W_1,\ldots,W_L$, no biases, and ReLU activation $\sigma(z)=\max\{z,0\}$ at each hidden layer. Write $d_0=d$ for the input dimension, $d_L=1$ for the output dimension, and let $d_1,\ldots,d_{L-1}$ be the hidden-layer widths. A path is an index sequence $(i_0,\ldots,i_L)$ with $1\leq i_k\leq d_k$. Its weight product is $\prod_{k=1}^L (W_k)_{i_k i_{k-1}}$.

Definition: The (absolute) path norm of this network is $$ \|\theta\|_{\mathrm{path}} = \sum_{i_0=1}^{d_0}\cdots\sum_{i_L=1}^{d_L} \prod_{k=1}^L |(W_k)_{i_k i_{k-1}}|. $$ Equivalently, with $|W_k|$ denoting entrywise absolute values and $\mathbf{1}$ an all-ones vector of the appropriate dimension, $$ \|\theta\|_{\mathrm{path}}=\mathbf{1}^{T}|W_L|\cdots |W_1|\mathbf{1}. $$

For a one-hidden-layer network, write $f(x)=\sum_{j=1}^{m}a_j\sigma(w_j^T x)$, where $w_j\in\mathbb{R}^d$. Its path norm is $\sum_{j=1}^{m}|a_j|\|w_j\|_1$: each hidden unit contributes one path for each input coordinate. The absence of biases is part of the setup here; a bias can be handled by augmenting the input with a constant coordinate, but that changes the input-bound convention.

Positive homogeneity, $\sigma(cz)=c\sigma(z)$ for $c\geq0$, explains one useful feature. If a hidden unit's incoming weights are multiplied by $c>0$ and its outgoing weight is divided by $c$, its represented function and the products along its paths do not change. The path norm is not a count of units; it records the absolute path products.

Worked Example: Computing a Path Norm

Let $d=2$ and consider $f(x)=2\sigma(x_1-2x_2)-\sigma(3x_1+x_2)$. There are two hidden units. The first has output weight $2$ and incoming weights $(1,-2)$; the second has output weight $-1$ and incoming weights $(3,1)$.

The first unit contributes $|2|(|1|+|-2|)=2(3)=6$. The second contributes $|-1|(|3|+|1|)=1(4)=4$. Therefore $\|\theta\|_{\mathrm{path}}=6+4=10$. Equivalently, the four input-to-output path products have absolute values $2,4,3,1$, whose sum is $10$. As a check on the represented function, $f(1,0)=2(1)-1(3)=-1$.

Proposition: For a one-hidden-layer network with path norm at most $A$, if $\|x\|_\infty\leq R$, then $|f(x)|\leq AR$.

Proof. Since $\sigma(z)\leq |z|$ and $|w_j^T x|\leq\|w_j\|_1\|x\|_\infty$, $$ |f(x)| \leq \sum_{j=1}^{m}|a_j|\sigma(w_j^T x) \leq \sum_{j=1}^{m}|a_j|\|w_j\|_1\|x\|_\infty \leq AR. $$ This proposition will also give a uniform bound on predictions when we discuss a bounded loss. $\square$

A Width-Independent Capacity Bound

For a fixed sample $x_1,\ldots,x_n$, define the empirical absolute Rademacher complexity of a function class $\mathcal F$ by $$ \widehat{\mathfrak R}_S(\mathcal F) = E_{\varepsilon}\left[ \sup_{f\in\mathcal F} \left|\frac{1}{n}\sum_{i=1}^n\varepsilon_i f(x_i)\right| \right], $$ where $\varepsilon_1,\ldots,\varepsilon_n$ are independent random signs, each equal to $1$ or $-1$ with probability $1/2$. The expected complexity $\mathfrak R_n(\mathcal F)$ is this quantity averaged over an independent sample from the input distribution.

Theorem: Let $\mathcal F_A$ contain all finite-width one-hidden-layer ReLU networks $f(x)=\sum_j a_j\sigma(w_j^Tx)$ with $\sum_j |a_j|\|w_j\|_1\leq A$. If every sample input satisfies $\|x_i\|_\infty\leq R$, then $$ \widehat{\mathfrak R}_S(\mathcal F_A) \leq 2AR\sqrt{\frac{2\log(2d)}{n}}. $$ The same bound holds for $\mathfrak R_n(\mathcal F_A)$ when the input distribution is supported on $\{x:\|x\|_\infty\leq R\}$.

Proof. A nonzero unit can be written with $u_j=w_j/\|w_j\|_1$ and $c_j=|a_j|\|w_j\|_1$. Its contribution is $c_j s_j\sigma(u_j^Tx)$, where $s_j\in\{-1,1\}$ and $\|u_j\|_1=1$. The coefficients satisfy $\sum_j c_j\leq A$. Thus the class is contained in $A$ times the convex hull of the zero function and the signed atoms $x\mapsto s\sigma(u^Tx)$, with $\|u\|_1\leq1$. A linear functional's supremum over a convex hull is its supremum over the atoms, so $$ \widehat{\mathfrak R}_S(\mathcal F_A) \leq \frac{A}{n}E_\varepsilon \sup_{\|u\|_1\leq1} \left|\sum_{i=1}^n\varepsilon_i\sigma(u^Tx_i)\right|. $$ Here the supremum over both signs $s$ is exactly the absolute value shown.

The Rademacher contraction inequality states that for a set $T\subseteq\mathbb R^n$ and coordinatewise $1$-Lipschitz maps $\phi_i$ with $\phi_i(0)=0$, $$ E_\varepsilon\sup_{t\in T}\left|\sum_i\varepsilon_i\phi_i(t_i)\right| \leq 2E_\varepsilon\sup_{t\in T}\left|\sum_i\varepsilon_i t_i\right|. $$ Apply it with $t_i=u^Tx_i$ and $\phi_i=\sigma$, which is $1$-Lipschitz and vanishes at zero. The right-hand supremum becomes $\sup_{\|u\|_1\leq1}|u^T\sum_i\varepsilon_i x_i| =\|\sum_i\varepsilon_i x_i\|_\infty$, by duality of the $\ell_1$ and $\ell_\infty$ norms.

For each coordinate $k$, the bound $|x_{ik}|\leq R$ gives $E_\varepsilon\exp(t\sum_i\varepsilon_i x_{ik})\leq\exp(t^2nR^2/2)$. The log-sum-exp bound, applied to the $2d$ signed coordinate sums, therefore gives $$ E_\varepsilon\max_{1\leq k\leq d}\left|\sum_i\varepsilon_i x_{ik}\right| \leq \inf_{t>0}\frac{\log(2d)}{t}+\frac{tnR^2}{2} =R\sqrt{2n\log(2d)}. $$ Combining the contraction and coordinate bounds, then dividing by $n$ and multiplying by $A$, proves the stated inequality. Averaging over samples proves the expected-complexity version. $\square$

Worked Example: Many Parameters, the Same Path Norm

For any positive integer $m$, take the scalar-input network $f_m(x)=\sum_{j=1}^{m}(1/m)\sigma(x)$. Its output is exactly $\sigma(x)$, since the $m$ identical terms have coefficients summing to $1$. Each unit has $|a_j|\|w_j\|_1=1/m$, so the total path norm is $m(1/m)=1$.

Counting one output weight and one input weight per unit gives $2m$ scalar parameters. At $m=100$, there are $200$ such parameters, while the path norm remains $1$ and the function remains $\sigma(x)$. The theorem's bound for this representation is governed by $A=1$, input dimension $d=1$, and the sample size, not by $m$. This does not say that all networks with 200 parameters have the same capacity; it shows that parameter count alone does not capture this representation's path scale.

From Capacity to a Generalization Guarantee

Here is one direct risk consequence. Let observations $(X_i,Y_i)$ be independent and identically distributed. Suppose $\|X_i\|_\infty\leq R$ almost surely, $|Y_i|\leq Y_{\max}$ almost surely, and use absolute loss $\ell_f(x,y)=|f(x)-y|$. For $f\in\mathcal F_A$, the proposition gives $|f(x)|\leq AR$, so the loss lies in $[0,M]$, where $M=AR+Y_{\max}$, and is $1$-Lipschitz in the prediction.

Write $P\ell_f=E[\ell_f(X,Y)]$ and $P_n\ell_f=n^{-1}\sum_{i=1}^n\ell_f(X_i,Y_i)$. The standard Rademacher generalization inequality for a class of losses in $[0,M]$ is $$ \sup_f(P\ell_f-P_n\ell_f) \leq 2\mathfrak R_n(\{\ell_f:f\in\mathcal F_A\}) +M\sqrt{\frac{\log(1/\delta)}{2n}} $$ with probability at least $1-\delta$, for $0<\delta<1$. Its expectation term follows from symmetrization with an independent ghost sample; the deviation term follows from McDiarmid's inequality, since changing one observation changes the supremum by at most $M/n$. The contraction inequality, after subtracting the constants $\ell_f(0,Y_i)$, gives $\mathfrak R_n(\{\ell_f\})\leq2\mathfrak R_n(\mathcal F_A)$. Substituting the theorem yields the explicit, slightly conservative bound $$ \sup_{f\in\mathcal F_A}(P\ell_f-P_n\ell_f) \leq 8AR\sqrt{\frac{2\log(2d)}{n}} + (AR+Y_{\max})\sqrt{\frac{\log(1/\delta)}{2n}}. $$

Worked Example: Evaluating the Risk Bound

Suppose $d=2$, $R=1$, $A=0.5$, $Y_{\max}=1$, $n=500$, and $\delta=0.05$. Then $M=AR+Y_{\max}=1.5$. First, the complexity theorem gives $$ \mathfrak R_n(\mathcal F_A) \leq 2(0.5)(1)\sqrt{\frac{2\log(4)}{500}} =\sqrt{\frac{2.7726}{500}} \approx 0.0745. $$

The loss-class term in the risk inequality is at most $4\mathfrak R_n(\mathcal F_A)$, hence at most $4(0.0745)=0.298$. The confidence term is $1.5\sqrt{\log(20)/1000} =1.5\sqrt{0.002996}\approx0.0821$. Adding them gives approximately $0.380$. Thus, with probability at least $0.95$, every predictor in this class has population absolute risk at most its empirical absolute risk plus about $0.380$. This numerical bound can be conservative; its value is to make the dependence on $A$, $d$, and $n$ explicit.

What the Bound Does—and Does Not—Say

The derived capacity bound has a logarithmic dependence on input dimension and no dependence on the number $m$ of hidden units. It is therefore different from a parameter-count bound: the relevant scale here is the total absolute path weight. A large path norm weakens the guarantee, even if the network has few parameters; a large width does not by itself weaken this particular bound when the path norm stays fixed.

The theorem was proved for one-hidden-layer, bias-free ReLU networks. Although the path norm is defined for deeper layered networks, this proof does not establish the same bound for arbitrary depth. Depth, biases, architecture, the loss, and any data-dependent choice of norm constraints require assumptions and arguments appropriate to the bound being used.

Common Pitfall

Wrong reasoning: “The path norm is unchanged by rescaling a hidden unit, so the network's capacity is unchanged under every parameter change.” Rescaling invariance applies to particular transformations that preserve path products and the represented function; it is not a claim that arbitrary changes in weights leave the norm or capacity fixed.
Correction: Compute the sum of absolute path products for the specified weights, and apply a generalization result only under its stated architecture, input, and loss assumptions. In particular, a width-independent one-hidden-layer bound is not automatically a depth-independent bound.

Key takeaway: A path norm constrains the total absolute weight transmitted from inputs to output. For one-hidden-layer ReLU networks on bounded inputs, that constraint yields a Rademacher bound proportional to $AR\sqrt{\log(2d)/n}$, with no hidden-width term.

Check Your Understanding

Use the definitions and derivations above to answer these questions.

For a one-hidden-layer network, why does each hidden unit's path-norm contribution equal $|a_j|\|w_j\|_1$?
If every input satisfies $\|x\|_\infty\leq R$, what prediction bound follows from a path norm at most $A$, and which inequality gives it?
Which step in the Rademacher-complexity proof introduces the dependence on input dimension, and why is it logarithmic?
How can a network's parameter count grow while its function and path norm remain fixed?
Name two assumptions or settings for which the one-hidden-layer theorem above does not, by itself, establish a generalization bound.