Metric Entropy And Fano Lower Bounds

Why Packing Size Matters

A minimax lower bound asks how well any estimator can perform in the worst case over a function class. One useful way to show that estimation is difficult is to find many functions that are far apart in the loss metric, while their data distributions remain hard to distinguish. The number of such functions matters: a procedure must identify which one generated the observations, and a large collection of plausible candidates makes that task more demanding.

This strategy has two ingredients. First, construct a finite packing of the function class: a set whose distinct elements have a prescribed minimum distance. Second, control the information in the observations about which packed function is the truth. Fano’s inequality combines these ingredients. In contrast to a two-point argument, the packing argument uses the logarithm of the number of alternatives, so it is especially effective when the class contains many independently placeable local perturbations.

For integrated squared-error risk, the relevant metric is the \(L_2\) norm under the design distribution: \(d(f,g)=\|f-g\|_{L_2(P_X)}\). A packing with norm separation \(\delta\) has squared-error separation \(\delta^2\). Keep that distinction in mind: the loss is squared, but the packing is often first described in the norm.

Building a Hölder Packing

Consider regression on \([0,1]^d\), with uniform design, and an isotropic Hölder ball of smoothness \(\beta>0\) and fixed radius \(L\). A smooth function supported inside a unit cube can be rescaled to a small cell. At cell width \(h\), give the rescaled bump amplitude proportional to \(h^\beta\). This scaling keeps its Hölder size bounded while its squared \(L_2\) norm is proportional to \(h^{2\beta+d}\).

Partition the domain into \(N=h^{-d}\) cells, taking \(h=1/m\) for an integer \(m\). Place one translated bump in each cell, with supports strictly inside their cells. For a binary vector \(\omega=(\omega_1,\ldots,\omega_N)\), include the bump in cell \(j\) if and only if \(\omega_j=1\). If the bump is \(\psi_j\), write \(f_\omega=a h^\beta\sum_{j=1}^N\omega_j\psi_j\), where \(a>0\) is a sufficiently small fixed constant. By scaling and disjoint supports, these functions lie in the Hölder ball when \(a\) is chosen small enough.

For two binary vectors, the squared \(L_2\) distance between their functions is the number of differing coordinates times the squared norm of one bump. A binary code with pairwise Hamming distance proportional to \(N\) therefore gives a function packing with squared \(L_2\) separation proportional to \(h^{2\beta}\), and with exponentially many elements in \(N\).

To verify the distance claim, let \(w\) be the number of coordinates at which two codewords differ. Each bump has squared norm \(a^2h^{2\beta+d}\|\psi\|_2^2\). Disjoint supports make the squared norms add, so the functions’ squared distance is \(w a^2h^{2\beta+d}\|\psi\|_2^2\). The code has \(w\geq cN\) for a fixed \(c>0\), and \(N=h^{-d}\); hence the distance is at least \(c a^2\|\psi\|_2^2 h^{2\beta}\). The code-count calculation gives \(\log M\geq c_1N\). This proves both claims.

The same construction principle applies to Sobolev balls: use smooth localized bumps, and choose their amplitude so that the Sobolev norm remains bounded as the cell width shrinks. For the standard \(L_2\)-Sobolev scaling of order \(s\), an amplitude proportional to \(h^s\) keeps the aggregate Sobolev size bounded across \(h^{-d}\) cells, while the resulting squared \(L_2\) separation is of order \(h^{2s}\). Constants and boundary conventions depend on the Sobolev class. The argument below needs only a packing’s size and separation, not a particular smoothness representation.

Statistical Distinguishability in Gaussian Regression

Take independent observations \(X_i\sim P_X\) and \(Y_i=f(X_i)+\varepsilon_i\), for \(i=1,\ldots,n\), where \(\varepsilon_i\sim N(0,\sigma^2)\) independently of the design and of one another. Denote the joint data distribution under regression function \(f\) by \(P_f\). The Kullback–Leibler divergence between two probability distributions with densities \(p\) and \(q\) is \(D(P\|Q)=\int p\log(p/q)\), when this integral is defined.

Proof. The design distribution is the same under both models. Conditional on \(X_1,\ldots,X_n\), the responses are independent normal variables with respective means \(f(X_i)\) and \(g(X_i)\), and common variance \(\sigma^2\). The divergence between \(N(\mu,\sigma^2)\) and \(N(\nu,\sigma^2)\) is \((\mu-\nu)^2/(2\sigma^2)\), as follows by taking the expectation under the first normal distribution of the log-density ratio. Conditional divergences add over independent responses, giving \(\sum_{i=1}^n(f(X_i)-g(X_i))^2/(2\sigma^2)\). Averaging over the common design distribution yields \(nE[(f(X)-g(X))^2]/(2\sigma^2)\), which is the stated expression. \(\square\)

Fano’s Inequality and the Minimax Bound

Suppose \(f_1,\ldots,f_M\) are candidate functions, with \(M\geq2\), and the data have distribution \(P_j=P_{f_j}\) when \(f_j\) is the truth. Let \(J\) be uniform on \(\{1,\ldots,M\}\), and conditionally on \(J=j\), draw the data \(Z\) from \(P_j\). Any procedure that identifies the index from \(Z\) has an error probability. Fano’s inequality bounds how small that error can be if the data contain little information about \(J\).

Proof. Let \(E\) be the indicator of the event \(\widehat J\neq J\). Conditional entropy satisfies \(H(J\mid Z)\leq H(E\mid Z)+H(J\mid E,Z)\). The first term is at most \(\log 2\). When \(E=0\), \(J\) is determined by \(Z\) and the decoder, so its conditional entropy is zero; when \(E=1\), it is at most \(\log M\). Consequently \(H(J\mid Z)\leq\log2+P(E=1)\log M\). Since \(J\) is uniform, \(H(J)=\log M\), and \(I(J;Z)=H(J)-H(J\mid Z)\). Rearranging proves the first inequality.

For the second inequality, let \(\bar P=M^{-1}\sum_jP_j\) be the mixture distribution. The definition of mutual information gives \(I(J;Z)=M^{-1}\sum_jD(P_j\|\bar P)\). Direct expansion of the logarithms gives \(M^{-1}\sum_jD(P_j\|Q)=M^{-1}\sum_jD(P_j\|\bar P)+D(\bar P\|Q)\). Since divergence is nonnegative, the right side is at least \(I(J;Z)\). This proves the claim. The statements hold when the displayed divergences are finite; otherwise the upper bound is vacuous. \(\square\)

The reference distribution is often chosen as \(P_0\), the data law under the zero regression function, even when zero is not one of the packing elements. Combining the divergence identity with Fano gives a useful criterion: if the average divergence to \(P_0\) is at most a small fraction of \(\log M\), then decoding the packed function has error bounded away from zero.

To transfer decoding error to estimation error, let \(\widehat f\) be any estimator and decode by choosing the closest packed function in \(L_2(P_X)\), breaking ties by the smallest index. If the true function is \(f_j\) and the decoded index is wrong, then some \(f_k\), \(k\neq j\), is at least as close to \(\widehat f\) as \(f_j\) is. By the triangle inequality, \(\|f_j-f_k\|_2\leq\|f_j-\widehat f\|_2+\|\widehat f-f_k\|_2\leq2\|\widehat f-f_j\|_2\). Thus a decoding error implies \(\|\widehat f-f_j\|_2\geq\delta/2\) for a \(\delta\)-separated packing.

Proof. Decode \(\widehat f\) by its nearest packing element. The preceding triangle-inequality argument shows that squared estimation loss is at least \(\delta^2/4\) whenever the decoder errs. Average risk over the uniform random index \(J\); it is at least \((\delta^2/4)P(\widehat J\neq J)\). Fano’s inequality and the assumed divergence bound give \(P(\widehat J\neq J)\geq1-\alpha-\log2/\log M\). The supremum of the risks over the packing is at least their average, proving the result. \(\square\)

Rate Implication and a Common Pitfall

For the Hölder packing above, \(\log M\geq c_1h^{-d}\) and \(\delta^2\geq c_2h^{2\beta}\). The divergence of every packed function from zero is at most a constant times \(nh^{2\beta}\). To make that information small relative to the packing logarithm, it suffices to require \(nh^{2\beta}\leq c h^{-d}\), or \(nh^{2\beta+d}\leq c\), for a suitably small constant \(c>0\). Choose a grid width of order \(h=n^{-1/(2\beta+d)}\), with constants adjusted to meet the information condition. For sufficiently large \(n\), the packing has enough elements that \(\log2/\log M\) is bounded away from one. The theorem then yields a minimax integrated squared-error lower bound of order \(h^{2\beta}=n^{-2\beta/(2\beta+d)}\). The matching upper-bound question is separate; the packing argument establishes that no estimator can improve this order uniformly over the class.

Common pitfall: treating packing size as sufficient by itself. It is tempting to argue that exponentially many separated functions automatically force a large estimation error. That reasoning omits the sampling distribution: if the observations reveal the index almost perfectly, many candidates need not make estimation difficult. The correction is to calculate a divergence or another information bound and verify that it is small compared with \(\log M\). A second frequent error is to compare a one-bump divergence with the entropy of a many-bump packing without accounting for the possible number of active bumps. The divergence must be bounded for every candidate, or on average over candidates, as required by the stated Fano bound.

Metric entropy is therefore a bridge between geometry and statistical difficulty. Smoothness controls how finely local perturbations can be placed and how large they can be; coding supplies many separated combinations; divergence determines whether the data can distinguish those combinations. The balance between the number of cells and the information per candidate sets the minimax rate.