Localized Dudley Entropy Integral

Part of the STAT 210B Results Toolbox: the result as stated in my 210B notes (§9.7, Prop. 9.19), plus the one proof step to recall to remember why it is true.

Statement

Proposition 9.19 (§9.7): with the localization \(T_n(\delta) = \{g\in\mathcal{F}^\star : \lVert g\rVert_n\le\delta\}\) — note the shifted class \(\mathcal{F}^\star\), which is star-shaped around \(0\) — the localized Gaussian complexity satisfies

Setup from the 210B proof: the increments \(X_g = \frac1n\sum_i w_i g(X_i)\) form a Gaussian process whose canonical metric is \(\frac{1}{\sqrt n}\lVert\cdot\rVert_n\); star-shapedness of \(\mathcal{F}^\star\) gives \(0\in T_n(\delta)\), and \(\operatorname{diam}\le 2\delta/\sqrt n\) caps the integral. (§9.6’s Prop. 9.16 is an earlier, uncleaned draft of the same bound, not a rougher precursor.) Downstream in 210B: Cor. 9.21 is the critical-radius condition (Remark 9.22 gives the fixed-point reading), Thm. 9.23 shows that for polynomial entropy \(\log N \le A\epsilon^{-p}\) with \(p\in(0,2)\), \(\delta_n = C_{A,p}(\sigma^2/n)^{1/(p+2)}\) is a valid radius, giving the rate \((\sigma^2/n)^{2/(p+2)}\), and Remark 9.20 gives the chaining intuition.

The fundamental step

Chaining: apply the maximal inequality once per resolution scale and sum. Approximate each \(g\) by its nearest neighbor in an \(\epsilon_k\)-net at dyadic scales \(\epsilon_k = \delta 2^{-k}\), and telescope:

At level \(k\) there are at most \(N(\epsilon_k)\cdot N(\epsilon_{k-1})\) possible increments, each sub-Gaussian with scale \(\propto \epsilon_{k-1}/\sqrt n\) (the canonical metric), so the maximal inequality prices level \(k\) at \(\epsilon_{k-1}\sqrt{\log N(\epsilon_k)}/\sqrt n\). Summing the levels is, up to constants, a Riemann sum for \(\int_0^\delta\sqrt{\log N(\epsilon)}\,d\epsilon\).

The memory hook: a single net pays \(\text{radius}\times\sqrt{\log(\text{net size})}\) and you’re stuck choosing one scale; chaining refuses to choose, pays at every scale, and the geometric decay of the radii makes the total an integral. Localization just caps the top of the integral at \(\delta\).

Where it’s used

• The covering-number route to deep networks in the Rademacher complexity notes: Ma’s \(\log N \le R/\epsilon^2\) bounds (Zhang 2002; Bartlett et al. 2017) feed localized Dudley to produce \(R_S = \widetilde O(\sqrt{R/n})\).
• The 210B Remark 9.25 boundary: \(\int_0^\delta \epsilon^{-p/2}d\epsilon\) converges iff \(p<2\), and \(\log N \le R/\epsilon^2\) sits exactly at the \(p=2\) borderline. Remark 9.25 calls \(p\ge2\) a genuine limitation of the chaining technique — bracketing entropy, Talagrand’s \(\gamma_2\) functional, or generic chaining are needed there. The \(\widetilde O\) log factor in Ma (5.95) is the Ma notes’ way of handling that logarithmic divergence at the endpoint.