VC bounds for a fixed ReLU architecture

Remove all hidden units that have no path to the output. Also remove all hidden units having no input ancestor: for each fixed parameter assignment their values are constants in $x$, and their contributions to a remaining unit or the output can be added to its existing bias. Allowing these new biases to vary independently produces a fixed reduced architecture whose realization class contains the original class. No new coefficient slots are needed, because every surviving computation unit already has a bias; edges and removed units only disappear. If the output has no input ancestor, the original class consists of constant functions and has VC dimension at most $1$, which satisfies the conclusions. Otherwise the reduced graph has $w\le W$ counted slots, $U$ hidden units, and $U+1\le w$ because the output and every hidden unit have counted biases. Every remaining unit lies on an input-to-output path. Rank each hidden unit by the maximum number of computation units on an input-to-that-unit path, and give the output its analogous rank $K$. Then each edge increases rank, and $K\le L-1$ and $K\le U+1\le w$. Empty ranks can be omitted. It suffices to bound the reduced class.

Fix arbitrary sample points $x_1,\dots ,x_m$. For any prescribed binary mask $b\in \{0,1{\}}^U$, replace the ReLU at hidden unit $v$ by multiplication of its preactivation by $b_v$. Its preactivation and the final output are now polynomials in the $w$ parameters. By induction along the graph, a unit of rank $j$ has polynomial degree at most $j$: input values have degree zero, multiplication by an edge coefficient raises degree by one, addition of a bias has degree one, and multiplication by a fixed mask entry changes no degree. Thus every such polynomial has degree at most $K\le w$. On any actual parameter vector the convention $b_v={\mathbf{1}}_{z_v>0}$ gives a unique mask, even when a preactivation is zero, and the masked polynomials then reproduce every actual unit value.

For each sample point and each of the $2^U$ masks, form the $U$ preactivation polynomials and the output polynomial minus $a$. There are $M=m(U+1)2^U$ polynomials, all of degree at most $w$. Their strict-positivity vector determines the actual output classification at every sample point: evaluate units in topological order, determining their actual mask by the relevant preactivation entry, then read the output entry for that mask. Hence the number of label vectors is at most $(2Mw+1{)}^w\le (3m{w}^2{2}^w{)}^w$ by [F2]. If the classifier uses $\ge a$, take the hidden-unit mask ${\mathbf{1}}_{z_v\ge 0}$ and use nonnegativity vectors throughout; at zero, multiplying by either mask value still gives the ReLU value, so the same count holds.

For a second count, start with the single parameter-space cell ${\mathbb{R}}^w$. At stage $j$, refine every existing cell by the activation bits of all units of rank $j$ at all $m$ sample points; at the final stage refine by the output threshold bits. Within a cell, all earlier mask bits are fixed, so the relevant $m{N}_j$ preactivation polynomials, or output-minus-threshold polynomials, have degree at most $j\le K$ by step 2.1, where $N_j$ is the number of units at that rank, with $N_K=1$ for the output. By [F2] there are at most $(2m{N}_{j}K+1{)}^w\le (3mwK{)}^w$ refinements of each cell. This estimate holds on an arbitrary cell; no connectedness or openness is needed. After $K$ stages, the number of cells, hence the number of output label vectors, is at most $(3mwK{)}^{wK}$. The construction using $\ge 0$ activation bits and nonnegativity output bits proves the identical bound for the other threshold convention.

Put $m_0=64w^2$. At this sample size the base-two logarithm of the last bound is $w({\log }_{2}3+{\log }_2{m}_0+2{\log }_{2}w+w)=w(w+{\log }_{2}3+6+4{\log }_{2}w)\le 13w^2<m_0$, using ${\log }_{2}w\le w$ for integers $w\ge 1$. Thus no $m_0$-point set can be shattered, and [F3] rules out all larger shattered sets. Consequently $\mathrm{VC}({\mathcal{H}}_a)<64w^2\le 64W^2$.

Write $A=wK$ and $B={\log }_2(2w)\ge 1$, and take the integer $m_1=\lceil 64AB\rceil \le 65AB$. Since $K\le w$, one has ${\log }_{2}A\le 2{\log }_{2}w$ and ${\log }_{2}B\le B$. The base-two logarithm of the label-count bound at $m=m_1$ is at most $A{\log }_2(195A^{2}B)\le A(8+4{\log }_{2}w+{\log }_{2}B)\le A(4+5B)\le 9AB<m_1$. No set of $m_1$ points is shattered. Therefore $\mathrm{VC}({\mathcal{H}}_a)<m_1\le 65wK{\log }_2(2w)\le 65WL{\log }_2(2W)$. Conversion between logarithm bases changes only an absolute constant. For $W\ge 2$, $\log (2W)\le 2\log W$ and $L\ge 1$, so this implies the requested $C{L}^{2}W\log W$ estimate. Together with step 4.1 and the constant-output case, this proves every assertion.