Comparing Growth and Metric Entropy Rates

Why Compare Two Complexity Routes?

A VC class can control uniform deviations in two related ways. One route counts how many distinct patterns the class can produce on a finite sample. The other measures how many functions are needed to approximate the class at different metric scales. Both routes use the same underlying combinatorial restriction, but they do not necessarily yield the same displayed rate.

The distinction matters when translating a deviation bound into a sample-size requirement. A growth-count argument typically leaves a logarithm involving the sample size, or equivalently a logarithm of the target accuracy after the bound is inverted. A uniform metric-entropy argument can remove that factor by integrating covering numbers across scales. This is a difference between bounds obtained by the two arguments; it does not by itself establish that every class must have the slower rate.

Two Complexity Quantities

Let \(\mathcal A\) be a measurable class of measurable subsets of a sample space, with VC dimension \(v\geq 1\). Let \(X_1,\ldots,X_n\) be independent observations with common distribution \(P\), and let \(P_n(A)=n^{-1}\sum_{i=1}^n \mathbf 1\{X_i\in A\}\). Assume the suprema below are measurable; otherwise the probability statements can be formulated using outer probability.

The Sauer–Shelah bound states that, for \(m\geq v\), \(\Pi_{\mathcal A}(m)\leq\sum_{j=0}^v {m\choose j}\leq (em/v)^v\). The metric counterpart used here is a uniform VC covering bound: there are universal constants \(A\geq 1\) and \(B\geq 1\) such that, for every probability measure \(Q\) and \(0<u\leq 1\), \(N(u,\mathcal A,L_2(Q))\leq(A/u^2)^{Bv}\). The constants do not depend on \(Q\), \(n\), or the particular class.

What the Growth-Count Route Gives

A finite set of \(M\) vectors, each with Euclidean norm at most \(\sqrt n\), has expected maximum absolute Rademacher sum at most \(\sqrt{2n\log(2M)}\). Conditional on the observations, the indicator vectors from \(\mathcal A\) form at most \(\Pi_{\mathcal A}(n)\) such vectors. Symmetrization then yields the following bound.

To see the first inequality, let \(\epsilon_1,\ldots,\epsilon_n\) be independent random signs. Symmetrization bounds the expected deviation by twice \(E\sup_{A\in\mathcal A}|n^{-1}\sum_i\epsilon_i\mathbf 1\{X_i\in A\}|\). Conditional on \(X_1,\ldots,X_n\), there are at most \(\Pi_{\mathcal A}(n)\) distinct vectors, each of norm at most \(\sqrt n\). Applying the finite-vector bound and dividing by \(n\) gives the first inequality. Applying Sauer–Shelah and taking logarithms gives the second.

The map \(Z=\sup_{A\in\mathcal A}|P_n(A)-P(A)|\) changes by at most \(1/n\) when one observation is replaced. McDiarmid’s inequality therefore adds a deviation term \(\sqrt{\log(1/\delta)/(2n)}\) with probability at least \(1-\delta\). In particular,

For fixed \(v\), the leading term contains \(\log(en/v)\). When the target deviation is \(\varepsilon\), this route suggests a sample size of order \(\varepsilon^{-2}\{v\log(1/\varepsilon)+\log(1/\delta)\}\), up to constants and the usual conditions ensuring the bound is small. The logarithm arises because the number of sample patterns grows with \(n\).

Why Entropy Integration Can Remove a Logarithm

A covering bound controls approximation at each scale, while an entropy integral accumulates the cost across scales. For indicator functions, \(L_2(Q)\) distance squared equals \(L_1(Q)\) distance, which accounts for the \(u^2\) in the uniform covering bound. A chaining inequality for Rademacher averages states, in a form that includes the necessary anchor term, that for any nonempty class \(\mathcal F\) of functions bounded in absolute value by one,

Here \(D\) is the \(L_2(P_n)\) diameter of the class and \(C\) is a universal constant. The first term can be taken as the expected absolute Rademacher sum at a fixed anchor \(f_0\in\mathcal F\): by Cauchy–Schwarz it is at most \(\sqrt{P_n f_0^2/n}\leq 1/\sqrt n\). This term cannot simply be omitted for an uncentered class.

For indicators, \(D\leq 1\). The uniform VC covering bound gives \(\log N(u,\mathcal A,L_2(P_n))\leq Bv\log(A/u^2)\). The integral is finite and has order \(\sqrt v\):

For the inequality, use \(\sqrt{a+b}\leq\sqrt a+\sqrt b\). For the equality, set \(t=-\log u\), giving \(\int_0^\infty e^{-t}\sqrt t\,dt=\Gamma(3/2)=\sqrt\pi/2\). Thus the small scales do not produce a factor \(\sqrt{\log(1/u)}\) evaluated at one chosen resolution; that factor is integrated over scales.

Combining the entropy integral with symmetrization and the same bounded-differences inequality proves the following comparison bound.

Consequently, the metric-entropy route gives a sufficient sample-size order \(\varepsilon^{-2}\{v+\log(1/\delta)\}\), with universal constants. Unlike the growth-count expression, it has no \(\log(1/\varepsilon)\) multiplying \(v\).

Comparing Sample-Size Expressions

The two routes can be summarized by their leading complexity terms. Inverting the growth-count rate introduces a logarithm of the target accuracy; integrating uniform metric entropy avoids it. Both bounds also pay for confidence through \(\log(1/\delta)\).

These are rate comparisons, not equalities with identical constants. A covering-number argument that uses only a single resolution and a union bound may still retain a logarithm of the resolution. The improvement comes from using the entropy bound across scales and integrating it, not merely from changing the name of the complexity measure.

When the Difference Matters

For a fixed accuracy and confidence level, the growth route is often a direct way to obtain a finite-sample guarantee from the number of sample patterns. Its logarithmic term can be acceptable, particularly when only a rough bound is needed. The entropy route is useful when the uniform covering theorem is available and a sharper dependence on accuracy matters.

The logarithmic factor in the growth bound should not automatically be interpreted as an intrinsic lower bound. It can be a cost of controlling all traces at once with a finite-count argument. Conversely, the entropy rate does not follow from any covering estimate whatsoever: it relies on a VC covering bound uniform over probability measures and on a valid entropy-integral argument. The integral must include an anchor term for an uncentered Rademacher average; for indicator classes that term is harmless when \(v\geq1\), but it is not identically zero.

Common Pitfall

A common mistake is to see that the entropy integral is finite and conclude that the Rademacher average is bounded by that integral alone. For a class containing only the constant function \(f\equiv1\), every covering number is one, so the integral is zero. Yet \(E|n^{-1}\sum_i\epsilon_i|>0\). The missing contribution is the fluctuation at the anchor function. Include its order-\(1/\sqrt n\) term, then absorb it into \(C\sqrt{v/n}\) for indicator classes with \(v\geq1\).