Localization and the Uniform Law
Global complexity bounds measure the entire class, including functions far from the part relevant to estimation. Localization restricts attention to a ball in the population or empirical quadratic norm. The radius must be chosen consistently with the fluctuation bound inside that ball. A critical-radius inequality expresses this balance and lets us compare empirical norms with population norms.
Let \(X_1,\ldots,X_n\) be i.i.d. with law \(P\). For a function \(f\), write \(Pf=\mathbb{E} f(X_1)\), \(P_nf=n^{-1}\sum_{i=1}^n f(X_i)\), and \(\mathbb G_nf=\sqrt n(P_n-P)f\). Rademacher variables are independent random signs, independent of the observations. See the empirical-process setup for measurability conventions.
We compare the empirical norm \(\|f\|_n=(P_nf^2)^{1/2}\) with \(\|f\|_P=(Pf^2)^{1/2}\). Assume the class is star-shaped about zero and uniformly bounded by \(b>0\). All the localized suprema below are assumed measurable and determined by countable subclasses, as for the usual pointwise measurable separable classes. The case \(b=0\) is immediate. We first use \(b=1\); rescaling gives the general case.1
Three quantities must be distinguished:
Every supremum is over \(f\in\mathcal F\). Thus \(R(t)=\mathbb E_XA_X(t)\), while \(\widehat R_X\) localizes using the empirical norm. In particular, conditioning on the observations does not by itself change a population ball into an empirical ball. The normalization \(1/n\) is used throughout.
Fix the numerical constant \(A=128\). Define critical radii by
The symbols \(R,\widehat R_X\) replace \(\overline{\mathcal R}_n,\breve{\mathcal R}_n\), respectively. Star-shapedness implies that each complexity is nondecreasing and its ratio to \(t\) is nonincreasing. Indeed, if \(0<u\le t\), then \((u/t)f\in\mathcal F\) and its relevant norm is at most \(u\) whenever the norm of \(f\) is at most \(t\). Taking suprema and expectations gives
Together with monotonicity this proves continuity at every positive radius. The admissible radii form an upper interval, since \(R(t)/t^2\) is nonincreasing. As the complexities are bounded by \(b\), this interval is nonempty. At a positive critical radius equality holds in (1); at every larger radius the defining inequality holds. The convention \(\inf=0\) handles a degenerate zero class.
Concentration input. We use the two-sided bounded empirical-process concentration theorem of Klein and Rio (2005), Theorems 1.1–1.2, pp. 2–3 of the author reprint. For a countable class of mean-zero functions bounded in absolute value by one, let \(Z\) be the supremum of their sums and \(v=\sup\sum_i\operatorname{Var}(h(X_i))+2\mathbb EZ\). Their Laplace-transform bounds imply, for universal constants,
The second form follows by Chernoff with \(|\lambda|\) the smaller of a fixed constant and a constant times \(x/v\). Absolute suprema are covered by adjoining negatives. We state this external concentration theorem explicitly; the normalization, variance estimates, and localization arguments below are proved here.
Lemma 1 (comparison of critical radii). For the bounded star-shaped class and the normalization (1), there are universal \(c_1,c_2>0\) such that
with probability at least \(1-c_1e^{-c_2n\delta_n^2/b^2}\).
Proof. Work first with \(b=1\) and \(\delta=\delta_n>0\). Theorem 2 below, whose proof is independent of this lemma, gives with probability at least \(1-Ce^{-cn\delta^2}\) the event
On this event, rearranging the squared inequalities gives \(\|f\|_P^2\le2\|f\|_n^2+\delta^2\) and \(\|f\|_n^2\le(3/2)\|f\|_P^2+\delta^2/2\). In particular each norm is at most twice the other plus \(\delta\). Hence
For the other needed event, apply the concentration input on the product space of observations and signs to \(\{(x,e)\mapsto\pm ef(x):\|f\|_P\le t\}\). The summands are centered, bounded by one, and have variance at most \(t^2\). If \(Z_t\) is their supremum of sums, then \(\mathbb EZ_t=nR(t)\) and \(\mathbb E_\varepsilon Z_t=nA_X(t)\). For either sign of \(\lambda\), conditional Jensen gives
Thus the same Laplace bound, followed by Chernoff, yields
For \(t=\alpha\delta\), \(\alpha\ge1\), star-shapedness gives the needed upper bound \(R(t)\le\alpha\delta^2/A\). Taking \(u=\alpha\delta^2/(8A)\) shows that
fails with probability at most \(2e^{-c'n\delta^2}\), where the fixed \(A\) is absorbed into the universal constant. We need only \(\alpha=1,7\).
On \(B_1\cap B_0(7\delta)\),
So \(\widehat\delta_n\le3\delta\). On \(B_0(\delta)\), \(A_X(\delta)\ge7\delta^2/(8A)>0\); (2) then implies \(\widehat\delta_n>0\). Since \(3\delta\ge\widehat\delta_n\), the scaling inequality and the equality at the empirical critical radius give2
Therefore \(\widehat\delta_n\ge7\delta/24>\delta/4\). A union bound proves the asserted probability. If \(\delta_n=0\), scaling from arbitrarily small admissible radii gives \(R(t)=0\) for every \(t>0\); countable determination then implies all sample evaluations vanish almost surely, so \(\widehat\delta_n=0\) as well. Finally apply the result to \(\mathcal F/b\), whose critical radii are \(\delta_n/b\) and \(\widehat\delta_n/b\). ◻
Theorem 2 (localized comparison of quadratic norms). Let \(|f|\le b\), let \(\mathcal F\) be star-shaped, and let \(\delta>0\) satisfy \(R(\delta)\le\delta^2/(128b)\). For every \(t\ge\delta\), with probability at least \(1-Ce^{-cnt^2/b^2}\), simultaneously for all \(f\in\mathcal F\),
This is a statement about squared norms. For the norms themselves, if \(0<\delta<b\) and \(m=\lceil\log_2(b/\delta)\rceil\), then
In particular, if \(cn\delta^2/(2b^2)\ge\log(1+m)\), the right side is at most \(Ce^{-cn\delta^2/(2b^2)}\). If \(\delta\ge b\), the norm comparison is deterministic.
Proof. Normalize to \(b=1\), and define the squared-norm fluctuation
For \(r\ge\delta\), symmetrization and the Rademacher contraction inequality on \([-1,1]\) give
We use the conservative contraction constant four for the absolute supremum: \(x\mapsto x^2\) is two-Lipschitz on \([-1,1]\), and passing from a one-sided supremum to an absolute one costs at most another factor two. The preceding uniform-entropy note proves this contraction step. The last inequality is exactly star-shaped scaling and the critical inequality; the factor \(r\) must be retained.
For the centered functions \(\pm(f^2-Pf^2)\), the absolute bound is one and the variance is at most \(Pf^4\le Pf^2\le r^2\). Applying the concentration input to \(nM_n(r)\) gives
Take \(u=s^2/8\). Since \(r\ge\delta\), the expectation is at most \(r^2/16\), and its sum with \(s^2/8\) is at most \((r\delta+s^2)/4\). Consequently, for \(r,s\ge\delta\),
From one ball to the relative bound. Take \(r=s=t\) in (5). Except on an event of probability at most \(2e^{-c'nt^2}\), \(M_n(t)\le t^2/2\). If \(a=\|f\|_P\le t\), this gives \(|(P_n-P)f^2|\le t^2/2\). If \(a>t\), star-shapedness puts \(g=(t/a)f\) in the radius-\(t\) ball, so
This proves (3) uniformly over the entire class using just one ball. The multiplier \(t/a\) lies in \([0,1]\); scaling a function upwards is not justified by star-shapedness.
From squared norms to absolute norm error. First apply (5) with \(r=s=\delta\), so \(M_n(\delta)\le\delta^2/2\) outside a set of probability \(2e^{-c'n\delta^2}\). For each \(j=1,\ldots,m\), set \(r_j=2^j\delta\) and \(s_j^2=r_j\delta\). Formula (5) gives \(M_n(r_j)\le r_j\delta/2\), with failure probability at most \(2e^{-c'n\delta^2}\) for each \(j\). Indeed, \(s_j^4/r_j^2=\delta^2\) and \(s_j^2\ge\delta^2\).
On the intersection of these events, if \(a\le\delta\), then
If \(r_j/2<a\le r_j\), then
These deterministic shells cover every population radius up to one. A union bound over the \(m+1\) events proves (4). The displayed condition on \(n\delta^2\) absorbs the number of shells. For \(b\ne1\), apply the proof to \(f/b\), \(r/b\), \(\delta/b\), and \(t/b\); both sides of (3) scale by \(b^2\), while the norm error scales by \(b\). ◻
Remark 3 (why the critical-radius bounds scale). The inequalities used in Lemma 1 are deterministic consequences of star-shapedness, not additional tail estimates.3 For example, \(\widehat R_X(t)/t\le\widehat R_X(u)/u\) for \(t\ge u>0\). At a positive empirical critical radius this gives \(\widehat R_X(t)\le t\widehat\delta_n/(Ab)\) whenever \(t\ge\widehat\delta_n\); the population version is identical. Concentration is needed only to compare \(A_X\) with its mean and to compare the two norms. The proof above establishes those events before using them.
Example 4 (quadratic polynomials). Let \(P\) be the uniform probability law on \([-1,1]\) and \(\mathcal P_2=\{a_0+a_1x+a_2x^2:\|f\|_\infty\le1\}\). An orthonormal basis for \(L^2(P)\) on this subspace is
These are normalized for the probability measure \(dx/2\). If \(f_\eta=\eta^\top\phi\), then \(\|f_\eta\|_P=\|\eta\|_2\). Let \(D_{ij}=\phi_j(X_i)\), \(j=0,1,2\). Cauchy–Schwarz and Jensen give
The final equality follows from \(\mathbb E_\varepsilon\|D^\top\varepsilon\|_2^2=\operatorname{tr}(D^\top D)\) and \(\mathbb E\operatorname{tr}(D^\top D)=3n\). Thus \(\delta=128\sqrt{3/n}\) satisfies the critical inequality. This is obtained by solving \(t\sqrt{3/n}\le t^2/128\); the radius on the right is not a second independent parameter.
For this fixed three-dimensional class, a direct Gram-matrix argument proves the sharper uniform \(O_P(n^{-1/2})\) conclusion without the general peeling condition. Set \(G_n=D^\top D/n\), so \(\mathbb EG_n=I_3\). Since \(\|\eta\|_2\le1\) for \(f_\eta\in\mathcal P_2\),
For \(\eta\ne0\), divide the difference of squares by \(\sqrt{\eta^\top G_n\eta}+\|\eta\|_2\ge\|\eta\|_2\); \(\eta=0\) is immediate. Each of the nine entries of \(G_n-I_3\) is an average of bounded, centered variables. Hoeffding and \(\|H\|_{\mathrm{op}}\le3\max_{j,k}|H_{jk}|\) give a bound \(18e^{-cnt^2}\) for exceeding \(t\), with a universal \(c>0\). Thus the uniform norm error is \(O_P(n^{-1/2})\).
This order cannot be improved to \(o_P(n^{-1/2})\): the single function \(f(x)=x\) belongs to the class, and the scalar CLT and delta method give
because \(\operatorname{Var}(X^2)=1/5-1/9=4/45\).
Remark 5. Localization keeps the radius factor in \(R(t)\le t\sqrt{3/n}\). A global complexity bound also proves a uniform law, but by itself does not give the same control near zero in the population norm. In the quadratic example, the Gram matrix gives a direct route to the uniform root-\(n\) rate.
Proposition 6 (expected empirical radius). Let \(\mathcal F\) be uniformly bounded by one and star-shaped, and let \(R(\delta)\le\delta^2/128\). Then, for all \(t\ge\delta\),
Uniform boundedness, rather than Lipschitz continuity on the sample space, is the hypothesis needed here.
Proof. Pointwise, \(\sup_{\|f\|_P\le t}P_nf^2\le t^2+M_n(t)\). Jensen and the mean bound already proved give
No square of an expected supremum of squared-norm errors is needed. ◻
Remark 7 (conditional global complexity). For a fixed sample, \(Z_f=n^{-1}\sum_i\varepsilon_if(X_i)\) has increments satisfying
This mgf calculation proves the subgaussian property; a variance calculation alone would not. Its increment variance is exactly \(\|f-g\|_n^2/n\).
The evaluation vectors of \(\mathcal P_2\) lie in the column space of \(D\), of dimension \(d_n\le3\), and in its empirical unit ball. Work in this image space, which removes any kernel of \(D\); the coefficient-to-evaluation map need not be an isomorphism. The Euclidean packing-volume argument yields
Dudley's inequality for the signed class, which contains zero, now gives
The integral is finite: near zero its integrand is bounded by a constant times \(\sqrt{1+\log(1/u)}\), whose integral converges under \(u=e^{-v}\). This holds for every sample. It is a global bound and complements, rather than improves, the radius-dependent population bound in Example 4.