Covering Neural Classes Through Parameter Perturbations

Why Cover Neural Classes by Perturbing Parameters?

A neural network is indexed by its weights and biases, but statistical learning depends on the functions those parameters produce. To bound the size of a network class, one useful route is to cover a bounded set of parameters with a finite grid and show that nearby parameter vectors produce nearby functions. The essential step is the second one: a small change in every parameter must be translated into a controlled change in the network output.

The resulting bound is generally not sharp. Its value is that it gives an explicit, finite covering number in terms of the number of parameters, the allowed parameter range, the input domain, and the architecture. In particular, it makes clear why depth and width can make a straightforward parameter-grid bound large.

Network Class and Covering Number

Consider a fully connected network with $L$ layers, input dimension $d_0$, hidden-layer widths $d_1,\ldots,d_{L-1}$, and scalar output $d_L=1$. For layer $l$, let $W_l$ be a $d_l$ by $d_{l-1}$ weight matrix and $b_l$ its bias vector. The hidden activation is the ReLU function $\sigma(t)=\max\{0,t\}$, applied coordinatewise. The output layer is linear:

h_0(x)=x,\qquad h_l(x)=\sigma(W_lh_{l-1}(x)+b_l)\quad (1\le l<L),\qquad f_\theta(x)=W_Lh_{L-1}(x)+b_L.

Here $\theta$ collects all weights and biases. Suppose the input domain $\mathcal X$ satisfies $\|x\|_2\le R$, and every parameter coordinate has absolute value at most $B$, where $B>0$. The parameter set is the cube $\Theta_B=[-B,B]^P$, with

P=\sum_{l=1}^L d_l(d_{l-1}+1).

Write $\mathcal F_B=\{f_\theta:\theta\in\Theta_B\}$. For functions on $\mathcal X$, the uniform distance is $\|f-g\|_\infty=\sup_{x\in\mathcal X}|f(x)-g(x)|$. A finite set $\mathcal G$ is an $\varepsilon$-cover of $\mathcal F_B$ in this distance if every $f\in\mathcal F_B$ is within distance $\varepsilon$ of at least one member of $\mathcal G$. The smallest possible size of such a cover is the covering number $N(\varepsilon,\mathcal F_B,\|\cdot\|_\infty)$.

Definition: A parameter perturbation of size $\delta$ means that the absolute difference between each corresponding weight and bias coordinate of $\theta,\theta'\in\Theta_B$ is at most $\delta$. This is the parameter-vector distance $\|\theta-\theta'\|_\infty$. A parameter-space cover becomes a function-space cover only after output changes have been bounded.

From Parameter Changes to Output Changes

We first bound the size of the activations. Define $A_0=R$ and, for $1\le l\le L$, define

A_l=B\sqrt{d_ld_{l-1}}\,A_{l-1}+B\sqrt{d_l}.

Then $\|h_l(x)\|_2\le A_l$ for hidden layers, and $|f_\theta(x)|\le A_L$ at the output. To see why, a matrix whose entries have magnitude at most $B$ has Frobenius norm at most $B\sqrt{d_ld_{l-1}}$, and hence operator norm at most that amount. Also, $\|b_l\|_2\le B\sqrt{d_l}$. ReLU does not increase the Euclidean norm. The triangle inequality therefore gives the stated recursion, with the same argument applying to the linear output.

Lemma: Let $\theta,\theta'\in\Theta_B$ have parameter-vector distance at most $\delta$. Define $C_0=0$ and $$ C_l=B\sqrt{d_ld_{l-1}}\,C_{l-1}+\sqrt{d_ld_{l-1}}\,A_{l-1}+\sqrt{d_l}, \qquad 1\le l\le L. $$ Then, for every $x\in\mathcal X$, $|f_\theta(x)-f_{\theta'}(x)|\le\delta C_L$.

Proof. Let $h_l,h'_l$ be the layer outputs for the two networks. At layer $l$, the weight-matrix difference has Frobenius norm at most $\delta\sqrt{d_ld_{l-1}}$, and the bias difference has Euclidean norm at most $\delta\sqrt{d_l}$. ReLU is 1-Lipschitz in Euclidean norm: coordinatewise, $|\sigma(a)-\sigma(b)|\le |a-b|$, so summing the squared inequalities proves the vector statement. The identity map in the output layer is also 1-Lipschitz.

Add and subtract $W_lh'_{l-1}$ inside the difference of the layer pre-activations. The triangle inequality and the operator-norm bound give

\begin{aligned} \|h_l-h'_l\|_2 &\le \|W_l(h_{l-1}-h'_{l-1})\|_2 +\|(W_l-W'_l)h'_{l-1}\|_2+\|b_l-b'_l\|_2\\ &\le B\sqrt{d_ld_{l-1}}\,\|h_{l-1}-h'_{l-1}\|_2 +\delta\sqrt{d_ld_{l-1}}\,A_{l-1}+\delta\sqrt{d_l}. \end{aligned}

The activation bound applies to $h'_{l-1}$, and $h_0=h'_0=x$, so the initial difference is zero. Induction using the definition of $C_l$ yields $\|h_l-h'_l\|_2\le\delta C_l$ at every layer. At $l=L$, the output is scalar, giving the claimed bound uniformly over $x\in\mathcal X$. $\square$

Worked Example: A One-Layer Affine Class

Let $f_{w,b}(x)=wx+b$, with $x\in[-1,1]$ and $w,b\in[-1,1]$. There is one layer, $d_0=d_1=1$, $B=R=1$, and $P=1(1+1)=2$. The activation bound is $A_0=1$, and the perturbation constant is

C_1=B\sqrt{1\cdot1}\,C_0+\sqrt{1\cdot1}\,A_0+\sqrt{1}=0+1+1=2.

This also follows directly: if $|w-w'|\le\delta$ and $|b-b'|\le\delta$, then \[ |f_{w,b}(x)-f_{w',b'}(x)| \le |w-w'|\,|x|+|b-b'| \le 2\delta. \] For a uniform error tolerance $\varepsilon=0.5$, it is enough to cover the parameter square at distance $\delta=\varepsilon/C_1=0.25$. The covering argument below gives at most $(1+2/0.25)^2=9^2=81$ functions. This is a valid bound, although a more careful calculation could improve it.

The Parameter-Grid Covering Bound

Theorem: For the network class above, let $C_L$ be given by the recursion in the lemma. For every $\varepsilon>0$, $$ N(\varepsilon,\mathcal F_B,\|\cdot\|_\infty) \le \left(1+\frac{2BC_L}{\varepsilon}\right)^P. $$

Proof. Set $\delta=\varepsilon/C_L$. Partition each coordinate interval $[-B,B]$ into at most $\lceil 2B/\delta\rceil$ intervals of length at most $\delta$, using a consistent assignment of boundary points so the intervals cover the whole interval. Their Cartesian products partition the parameter cube into at most $\lceil 2B/\delta\rceil^P$ cells. From each nonempty cell choose one parameter vector in that cell. These chosen vectors are all in $\Theta_B$, and any parameter vector in a cell differs coordinatewise from its chosen representative by at most $\delta$.

The lemma implies that the corresponding network outputs differ by at most $\delta C_L=\varepsilon$, uniformly on $\mathcal X$. Thus these networks form an $\varepsilon$-cover. Finally, $\lceil u\rceil\le 1+u$ for $u>0$, so the number of selected vectors is at most

\left\lceil\frac{2B}{\delta}\right\rceil^P \le \left(1+\frac{2B}{\delta}\right)^P =\left(1+\frac{2BC_L}{\varepsilon}\right)^P.

This proves the theorem. $\square$

Taking logarithms makes the dependence especially visible:

\log N(\varepsilon,\mathcal F_B,\|\cdot\|_\infty) \le P\log\left(1+\frac{2BC_L}{\varepsilon}\right).

The parameter count $P$ appears as an exponent, while $C_L$ measures how sensitively the network output can respond to parameter changes under the specified bounds. This is a uniform cover: the same finite set approximates the functions at every input in $\mathcal X$. Consequently it also covers the class under weaker distances such as empirical root-mean-square distance on any fixed sample, since an everywhere pointwise error at most $\varepsilon$ implies an empirical root-mean-square error at most $\varepsilon$.

Worked Example: A Two-Hidden-Unit ReLU Network

Take input domain $[-1,1]$, widths $d_0=1,d_1=2,d_2=1$, and $B=1$. There are $P=2(1+1)+1(2+1)=7$ parameters. The input bound is $A_0=1$. For the hidden layer,

A_1=\sqrt{2\cdot1}\,A_0+\sqrt2=2\sqrt2,\qquad C_1=\sqrt{2\cdot1}\,A_0+\sqrt2=2\sqrt2.

For the scalar linear output, the recursions give

A_2=\sqrt{1\cdot2}\,A_1+1=2\sqrt2\cdot\sqrt2+1=5, \qquad C_2=\sqrt2\,C_1+\sqrt2\,A_1+1=4+4+1=9.

At tolerance $\varepsilon=0.9$, the theorem therefore gives \[ N(0.9,\mathcal F_1,\|\cdot\|_\infty) \le \left(1+\frac{2\cdot1\cdot9}{0.9}\right)^7 =21^7=1{,}801{,}088{,}541. \] The bound is large, but it is a concrete finite upper bound derived from the parameter cube and a verified output-stability constant.

Worked Example: How Depth Enters the Bound

Consider a scalar-input network with three hidden layers of width one and a scalar output, so $d_0=d_1=d_2=d_3=d_4=1$. Set $B=R=1$. Each layer has one weight and one bias, so $P=4\cdot2=8$. Since every square-root width factor is one, the activation bounds are

A_0=1,\quad A_1=2,\quad A_2=3,\quad A_3=4,\quad A_4=5.

For the perturbation constants, the recursion becomes $C_l=C_{l-1}+A_{l-1}+1$, starting at $C_0=0$. Hence

C_1=2,\quad C_2=2+2+1=5,\quad C_3=5+3+1=9,\quad C_4=9+4+1=14.

At $\varepsilon=2$, a sufficient parameter-grid resolution is $\delta=2/14=1/7$. The bound is \[ N(2,\mathcal F_1,\|\cdot\|_\infty) \le (1+2/(1/7))^8=15^8=2{,}562{,}890{,}625. \] The calculation illustrates how the layer-by-layer stability constants accumulate. It does not assert that the actual class requires anything close to this many covering functions.

Interpretation and a Common Pitfall

The bound is a direct conversion from a finite-dimensional parameter cube to a set of functions. It is useful when the architecture and parameter ranges are explicit, and when a later statistical argument needs a finite approximation to the prediction class. A uniform function cover also remains valid for a particular observed sample, regardless of which inputs appear in that sample.

Common mistake: treating a parameter grid as a function cover without checking output sensitivity. It is not enough to say that each parameter coordinate changes by at most $\delta$, and then conclude that outputs change by at most $\delta$. A network composes layer maps; changes in early layers affect the inputs to later layers, and the effect can be multiplied by bounds on later weights. The correction is to propagate both activation-size bounds and perturbation bounds through every layer, as in the recursions for $A_l$ and $C_l$, before choosing $\delta=\varepsilon/C_L$.

The result can be loose for several reasons: it covers a full coordinate cube, counts every parameter independently, and controls the largest output error over the entire input domain. Its role here is to establish a valid covering bound from bounded parameters and explicit stability, rather than to claim an optimal description of neural-network complexity.

Key takeaway: To obtain a function-space cover from a parameter-space grid, first prove a uniform perturbation inequality. For bounded ReLU networks, layerwise activation and perturbation recursions yield such an inequality; a grid of resolution $\varepsilon/C_L$ then gives a covering number at most $(1+2BC_L/\varepsilon)^P$.

Check Your Understanding

Check that you can connect parameter resolution, output stability, and the resulting cover.

For a network with parameter count $P$, why does a parameter grid by itself not guarantee an $\varepsilon$-cover of the functions?
Explain the roles of $A_l$ and $C_l$ in the perturbation argument.
If a valid stability inequality is $\|f_\theta-f_{\theta'}\|_\infty\le 6\|\theta-\theta'\|_\infty$, what parameter-grid resolution suffices for a function-space cover of radius $0.3$?
Why does a uniform $\varepsilon$-cover also give an empirical root-mean-square cover with radius $\varepsilon$ on any fixed sample?
Which features of the parameter-grid argument make its covering-number bound potentially loose?