Pseudo-Dimension Bounds for Neural Network Classes

Why Pseudo-Dimension Enters Neural Generalization

A neural network class can contain many real-valued predictors, even when all networks share the same architecture. To understand how well empirical averages represent population averages uniformly over that class, we need a measure of how flexibly its functions can respond to data. Pseudo-dimension provides such a measure by asking how many input-threshold pairs the class can label in every possible way.

This is a capacity statement, not an approximation statement: it does not say whether the class contains a good predictor for a particular target. Instead, it controls the sampling cost of comparing empirical and population averages across the class. The key result below combines pseudo-dimension with boundedness to give a uniform-deviation guarantee.

Definition and the Uniform-Deviation Bound

Definition: Let \(\mathcal{F}\) be a class of real-valued functions on a set \(\mathcal{X}\). Its pseudo-dimension, denoted \(\operatorname{Pdim}(\mathcal{F})\), is the largest integer \(q\) for which there exist \(x_1,\ldots,x_q\in\mathcal{X}\) and \(t_1,\ldots,t_q\in\mathbb{R}\) such that, for every \((b_1,\ldots,b_q)\in\{0,1\}^q\), some \(f\in\mathcal{F}\) satisfies \(f(x_i)>t_i\) when \(b_i=1\) and \(f(x_i)\leq t_i\) when \(b_i=0\). If arbitrarily large \(q\) are possible, the pseudo-dimension is infinite.

The thresholds \(t_i\) may differ across inputs. Equivalently, the pseudo-dimension is the VC dimension of the subgraph sets \(\{(x,t):t<f(x)\}\), as \(f\) ranges over \(\mathcal{F}\). When all functions take values in \(\{0,1\}\), pseudo-dimension agrees with the VC dimension of the corresponding set class.

Here is a uniform-deviation result for a bounded real-valued class. Let \(X_1,\ldots,X_n\) be independent and identically distributed with distribution \(P\). Write \(P f=E[f(X)]\) and \(P_n f=n^{-1}\sum_{i=1}^n f(X_i)\). Assume every \(f\in\mathcal{F}\) is measurable and takes values in \([0,1]\), and assume the relevant suprema are measurable. If \(q=\operatorname{Pdim}(\mathcal{F})\) is finite and \(n\geq q\geq1\), then for \(0<\delta<1\),

P\left\{ \sup_{f\in\mathcal{F}}|P_n f-P f| \leq 2\sqrt{\frac{2\{\log 2+q\log(en/q)\}}{n}} +\sqrt{\frac{\log(1/\delta)}{2n}} \right\}\geq 1-\delta.

The displayed bound is deliberately explicit rather than optimized. Its first term reflects class complexity and sample size; the second reflects confidence. For functions taking values in an interval of length \(R\), rescaling gives the same bound multiplied by \(R\).

Why the Bound Holds

For a class \(\mathcal{A}\) of measurable sets, let \(\Pi_{\mathcal{A}}(n)\) be the largest number of distinct membership patterns that sets in \(\mathcal{A}\) can produce on \(n\) points. If \(\mathcal{A}\) has VC dimension at most \(q\), Sauer’s bound gives \(\Pi_{\mathcal{A}}(n)\leq\sum_{j=0}^{q}{n\choose j}\leq(en/q)^q\) for \(n\geq q\). The first inequality counts possible patterns; the second is the standard binomial-sum bound.

For completeness, the deviation bound for sets follows by symmetrization and a finite-class exponential bound. Take an independent sample \(X'_1,\ldots,X'_n\) from \(P\). Conditional Jensen’s inequality, followed by swapping each pair \((X_i,X'_i)\) at random, yields

E\sup_{A\in\mathcal{A}}|P_n(A)-P(A)| \leq 2E_{X,\varepsilon}\sup_{A\in\mathcal{A}} \left|\frac{1}{n}\sum_{i=1}^n\varepsilon_i\mathbf{1}_{A}(X_i)\right|,

where the \(\varepsilon_i\) are independent random signs, each equal to \(1\) or \(-1\) with probability \(1/2\). Conditional on the sample, at most \(\Pi_{\mathcal{A}}(n)\) distinct indicator vectors occur. For any such vector \(v\), \(\|v\|_2^2\leq n\), so the sign sum divided by \(n\) has moment generating function bounded by \(\exp(\lambda^2/(2n))\). Applying the exponential bound to the maximum of the positive and negative sums over these vectors, then optimizing over \(\lambda>0\), gives

E\sup_{A\in\mathcal{A}}|P_n(A)-P(A)| \leq 2\sqrt{\frac{2\log\{2\Pi_{\mathcal{A}}(n)\}}{n}}.

To pass from sets to functions, use the layer-cake identity \(f(x)=\int_0^1\mathbf{1}\{f(x)>t\}\,dt\), valid for \(0\leq f(x)\leq1\). Therefore

\sup_{f\in\mathcal{F}}|P_n f-P f| \leq \int_0^1\sup_{f\in\mathcal{F}} \left|P_n\{f>t\}-P\{f>t\}\right|\,dt.

For each fixed \(t\), the sets \(\{x:f(x)>t\}\) have VC dimension at most \(q\): shattering points at that common threshold is a special case of pseudo-shattering. Taking expectations, applying the set bound at each \(t\), and using \(\Pi(n)\leq(en/q)^q\) gives the expectation bound with first term \(2\sqrt{2\{\log 2+q\log(en/q)\}/n}\). Finally, the supremum deviation changes by at most \(1/n\) if one observation is replaced. McDiarmid’s inequality adds \(\sqrt{\log(1/\delta)/(2n)}\) with probability at least \(1-\delta\). This proves the stated result. \(\square\)

The measurability assumption above can be replaced by the usual outer-probability formulation when a class is not pointwise measurable. It is important because the proof takes expectations and probabilities of suprema over a function class.

Worked Example: Pseudo-Dimension of Constant Predictors

Let \(\mathcal{F}\) be all constant functions \(f_c(x)=c\) with \(c\in[0,1]\), on a nonempty input space. We show that \(\operatorname{Pdim}(\mathcal{F})=1\).

One point can be pseudo-shattered: choose any \(x_1\) and threshold \(t_1=1/2\). The choice \(c=3/4\) labels it above threshold, and \(c=1/4\) labels it at or below threshold.

No two points can be pseudo-shattered. For any \(x_1,x_2\), the function has the same value \(c\) at both. If \(t_1\leq t_2\), the pattern \((0,1)\) would require \(c\leq t_1\) and \(c>t_2\), which is impossible. If \(t_2<t_1\), the pattern \((1,0)\) would require \(c>t_1\) and \(c\leq t_2\), also impossible. Thus the largest pseudo-shattered set has size one.

ReLU Networks: Parameters, Depth, and Width

For a fixed architecture, let \(P\) be the number of trainable scalar weights and biases, and let \(L\) be the number of affine layers. Consider scalar-output networks with ReLU activations in hidden layers and an affine output layer. The standard piecewise-linear network dimension bound of Bartlett, Harvey, Liaw, and Mehrabian gives a universal constant \(C\) such that

Theorem: For a fixed feedforward ReLU architecture with unshared trainable parameters, the class of real-valued network outputs satisfies \(\operatorname{Pdim}(\mathcal{F})\leq C P L\log(P+1)\). The input weights and biases are included in \(P\). The constant does not depend on the data distribution.

This theorem concerns the architecture’s capacity as its parameters vary freely; it does not require a bound on their magnitudes. In a fully connected network with input dimension \(p\), hidden widths \(m_1,\ldots,m_{L-1}\), and one output, the parameter count is

P=\sum_{\ell=1}^{L}(m_{\ell-1}+1)m_\ell, \qquad m_0=p,\quad m_L=1.

Thus width affects the bound through the number of weights and biases, while depth appears both through the number of parameters and through the additional factor \(L\). A sparse architecture can have a smaller \(P\) than a dense architecture with the same layer widths. The theorem as stated is for the specified unshared-parameter architecture; a different parameterization or activation function needs an applicable dimension result of its own.

If network outputs are not bounded, the \([0,1]\) deviation theorem does not apply directly. One can instead restrict or clip predictions to a bounded interval and apply a corresponding complexity bound to that resulting function class. For a statistical risk guarantee, the relevant class is often the class of losses, so its boundedness and complexity must also be checked.

Worked Example: Counting Parameters in a Network

Consider a fully connected ReLU network with input dimension \(5\), hidden widths \(8\) and \(4\), and one scalar output. There are \(L=3\) affine layers. Including biases, the first layer has \((5+1)8=48\) parameters, the second has \((8+1)4=36\), and the output layer has \((4+1)1=5\). Therefore \(P=48+36+5=89\).

The dimension theorem gives

\operatorname{Pdim}(\mathcal{F}) \leq C\cdot 89\cdot 3\log(90).

Since \(\log(90)\) is approximately \(4.50\), this is about \(1{,}202C\). The result is an upper bound, not a claim that the network’s actual pseudo-dimension equals that number. Increasing either hidden width generally increases \(P\); adding layers can increase both \(P\) and the explicit depth factor.

Turning Complexity into a Sample-Size Guarantee

Suppose a bounded neural function class has pseudo-dimension at most \(q\). Substituting the network dimension theorem into the deviation result gives a direct guarantee: with probability at least \(1-\delta\), all functions in the class have empirical and population averages within the displayed deviation bound. In particular, a sufficient sample size is of order

n \ \gtrsim\ \frac{q\log(1/\epsilon)+\log(1/\delta)}{\epsilon^2}

to make the uniform deviation at most a target tolerance \(\epsilon\), for \(0<\epsilon<1\). Here the implicit constant is universal; the logarithmic factor in \(\epsilon\) accommodates the growth term \(\log(en/q)\) in the explicit bound. For a ReLU architecture, one may substitute \(q=CPL\log(P+1)\). The resulting guarantee is distribution-free, but can be conservative.

Worked Example: Evaluating an Explicit Deviation Bound

Suppose a bounded function class has pseudo-dimension at most \(q=10\), and \(n=10{,}000\) independent observations are available. Take \(\delta=0.05\). Since \(n\geq q\), the explicit bound applies. First,

\log 2+q\log(en/q) = \log 2+10\log(e\cdot 1000) \approx 0.693+79.08=79.77.

The complexity term is \(2\sqrt{2(79.77)/10{,}000}\approx0.253\). The confidence term is \(\sqrt{\log(20)/(2\cdot10{,}000)}\approx0.012\). Thus, with probability at least \(0.95\),

\sup_{f\in\mathcal{F}}|P_n f-P f|\leq 0.265.

This is a valid, though potentially loose, guarantee. It applies simultaneously to every function in the class, not just to a predictor selected after observing the sample.

Interpretation and a Common Pitfall

A uniform bound matters because a data-dependent choice of network lies in the same class over which the supremum is taken. If the relevant loss functions are bounded and their class has controlled pseudo-dimension, the bound limits the gap between empirical and population loss even after a predictor is selected using the data. This is one way complexity can support the generalization analysis of empirical risk minimizers.

Common mistake: counting parameters and stopping there. It is tempting to reason that two networks with the same number of trainable parameters must have the same bound. The network dimension theorem has an explicit depth factor as well as the parameter factor, and the sample bound also includes a growth logarithm and a confidence term. The correction is to identify the relevant class, calculate its parameter count and depth, and then substitute its pseudo-dimension bound into the uniform-deviation result. Parameter count is informative, but it is not the entire guarantee.

Key takeaway: Pseudo-dimension measures thresholding capacity for real-valued predictors. For fixed ReLU architectures it is bounded in terms of trainable parameters and depth; for bounded functions, that capacity yields a high-probability uniform-deviation guarantee whose sample cost scales roughly as complexity divided by \(\epsilon^2\).

Check Your Understanding

Check that you can use the definitions, theorem, and calculations without relying on a memorized formula alone.

In the definition of pseudo-dimension, why are thresholds allowed to differ across the input points?
What measurability and boundedness conditions are used in the uniform-deviation result, and where does boundedness enter its proof?
A fully connected network has input dimension \(3\), hidden widths \(6\) and \(6\), and one scalar output. Calculate its number of trainable weights and biases and state the resulting form of the pseudo-dimension bound.
Why does the set class \(\{x:f(x)>t\}\), for a fixed \(t\), have VC dimension no greater than the pseudo-dimension of \(\mathcal{F}\)?
Explain why a uniform-deviation guarantee applies to a predictor chosen using the observed sample, and why it does not by itself guarantee that the chosen predictor has small population risk.