Choosing Among Neural Network Complexity Measures

Why the Complexity Measure Matters

A neural network can have many parameters yet represent a comparatively restricted set of functions, or have a small parameter count while being sensitive to changes in its weights. A complexity measure makes a particular aspect of this distinction quantitative. The central question is not which measure is universally best, but which measure controls the generalization quantity of interest under assumptions that are credible for the problem.

This tutorial compares five common choices: pseudo-dimension, covering numbers, spectral norms, path norms, and PAC-Bayesian divergence. They describe different things. Pseudo-dimension measures combinatorial richness; covering numbers measure metric size at a chosen resolution; spectral and path norms constrain the weights or paths of a network; and PAC-Bayes divergence measures how far a data-dependent distribution over predictors moves from a sample-independent prior. A value from one measure cannot be directly substituted for a value from another.

Definitions and What They Measure

Pseudo-dimension is a distribution-free, combinatorial measure of how many patterns a function class can produce. For a binary-valued class, it agrees with the VC dimension. It does not describe how far apart two predictions are numerically, nor does it use the particular input distribution. A finite pseudo-dimension can support uniform generalization bounds when the relevant loss class is also controlled; applying a function-class dimension to a loss class requires checking that link rather than assuming it.

A covering number is inseparable from both its metric and its scale \(\varepsilon\). The empirical metric depends on the observed inputs, whereas a population metric depends on an input distribution. Covering numbers can describe approximation at several resolutions, but a generalization result using them needs conditions connecting the chosen metric to the loss and controlling the relevant entropy.

For a network with weight matrices \(W_1,\ldots,W_L\), a common spectral quantity is the product \(\prod_{\ell=1}^L\|W_\ell\|_2\), where \(\|\cdot\|_2\) is the operator norm induced by Euclidean norms. Generalization bounds often use this product together with additional factors, such as input-radius or width-dependent terms. It is not, by itself, a generalization bound. One must check the activation, input, output, and loss assumptions in the particular theorem being used.

For a network with nonnegative homogeneous activations such as ReLU, the path norm sums the absolute products of weights along input-to-output paths. In a scalar-input, one-hidden-layer network \(f(x)=\sum_j a_j\sigma(w_jx)\), with no biases, this is \(\sum_j |a_j||w_j|\). Path norms and spectral norms are weight-based controls, but they summarize weights differently. ReLU homogeneity makes the path product invariant to rescaling a hidden unit’s incoming weights by a positive constant and its outgoing weight by the reciprocal constant.

Unlike a norm constraint, PAC-Bayes can be applied to a distribution over predictors rather than just one network. Its price depends on the chosen prior, posterior, loss, and sample size. The prior must be fixed independently of the data for the standard guarantee below; a data-dependent choice needs a separate justification.

Worked Examples

Two Guarantees and Their Assumptions

The following PAC-Bayesian result makes explicit why divergence is one kind of complexity control. Let \(Z_1,\ldots,Z_n\) be independent observations from a common distribution \(D\), and let \(\ell(h,Z)\in[0,1]\) for every predictor \(h\). Write \(L(h)=E_{Z\sim D}[\ell(h,Z)]\) and \(\widehat L(h)=n^{-1}\sum_i\ell(h,Z_i)\). Assume a prior \(P\) is fixed independently of the sample. Then, for each fixed, sample-independent \(\lambda>0\), with probability at least \(1-\delta\) over the sample, simultaneously for every posterior \(Q\),

Proof. For fixed \(h\), Hoeffding’s lemma applied to the independent bounded losses gives \(E_S\exp\{\lambda(L(h)-\widehat L(h))\}\le\exp\{\lambda^2/(8n)\}\). Integrating with respect to the sample-independent prior and using Tonelli’s theorem for the nonnegative integrand yields \(E_S E_{h\sim P}\exp\{\lambda(L(h)-\widehat L(h))\}\le\exp\{\lambda^2/(8n)\}\). Markov’s inequality therefore implies that, with probability at least \(1-\delta\), \(E_{h\sim P}\exp\{\lambda(L(h)-\widehat L(h))\}\le\exp\{\lambda^2/(8n)+\log(1/\delta)\}\). For any \(Q\ll P\), the change-of-measure inequality \(E_Q g\le\operatorname{KL}(Q\|P)+\log E_P e^g\) applied to \(g(h)=\lambda(L(h)-\widehat L(h))\) gives the claimed bound after division by \(\lambda\). For each fixed, sample-independent \(\lambda>0\), this event is uniform in \(Q\), since it is a single event defined using \(P\). The argument does not establish one event that works simultaneously for all \(\lambda>0\). If \(Q\not\ll P\), the right side is infinite and the inequality is vacuous. \(\square\)

A second guarantee explains what spectral norms can control directly. Consider depth-\(L\) networks without biases, with hidden activations that are 1-Lipschitz and satisfy \(\sigma(0)=0\), and a linear output layer. Let \(f_W\) and \(f_V\) have the same architecture, and assume \(\|x\|_2\le B\). Then

Derivation. Replace the layers of \(V\) by those of \(W\), one at a time, starting at the output end. The difference between the two final outputs is the sum of the \(L\) successive output changes, so the triangle inequality bounds its norm by the sum of their norms. For the change at layer \(j\), the preceding layers are \(V_1,\ldots,V_{j-1}\), and their output norm is at most \(B\prod_{k<j}\|V_k\|_2\), because each activation is 1-Lipschitz and vanishes at zero. The change at layer \(j\) has norm at most \(\|W_j-V_j\|_2\) times this quantity. The following layers use \(W_{j+1},\ldots,W_L\); their activations are 1-Lipschitz and their linear maps have operator norms \(\|W_k\|_2\), so they multiply the change by at most \(\prod_{k>j}\|W_k\|_2\). Summing these \(L\) bounds gives the result. \(\square\)

This perturbation inequality is a stability statement for outputs, not a stand-alone generalization theorem. Turning it into a statistical bound requires additional arguments, such as covering the admissible networks at an appropriate resolution and linking output changes to changes in loss. It clarifies why spectral norms can matter: they control how weight perturbations propagate, given the stated architectural and input conditions.

How to Choose Among the Measures

These choices answer different questions. Pseudo-dimension asks how many label-like patterns are possible. A covering number asks how many distinguishable functions remain at a specified resolution. Spectral and path norms impose different geometric restrictions on network weights. PAC-Bayes asks whether a posterior concentrated on useful predictors can be supported by a prior without paying too large a divergence penalty. A good analysis selects the measure whose theorem matches the predictor, data, and loss, rather than choosing a measure merely because it is easy to calculate.

Common Pitfall

Wrong reasoning: “This network has a small spectral-norm product, so its generalization error must be small.” The product alone does not imply that conclusion. A bound may also depend on input magnitude, depth, a covering scale, the loss, sample size, or other quantities; its assumptions may fail for the model at hand.

Correction: Identify the precise theorem and verify each hypothesis before interpreting its complexity term. Likewise, do not compare a pseudo-dimension, a covering number, a norm, and a KL divergence as though they shared units or a common scale. They can each support generalization control, but only through their own assumptions and bound.