Local Bracketing Bounds from Bernstein’s Inequality

Bernstein’s inequality distinguishes the variance of a summand from its uniform bound. This distinction is useful for a small neighborhood of functions: their variances can be small even when their common envelope is not. We first turn the one-function tail estimate into a finite-class bound, then examine how brackets at decreasing scales can control the whole neighborhood.

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.

Lemma 1 (Bernstein tail for a fixed bounded summand). Let \(Y_1,\dots,Y_n\) be i.i.d. mean-zero with \(|Y_i|\le b\) a.s. and \(\mathbb{E}[Y_i^2]\le \sigma^2\). Then for all \(t>0\),

\[\mathbf P\,\,\!\!\left(\Big|\frac1{\sqrt n}\sum_{i=1}^n Y_i\Big|\ge t\right) \le 2\exp \left(-\frac{t^2}{2\big(\sigma^2+\frac{b}{3\sqrt n}t\big)}\right).\]

Proof. Independence and the power-series estimate \(P|Y|^k\le b^{k-2}PY^2\), for \(k\ge2\), give

\[\log\mathbb E e^{\lambda\sum_iY_i}\le\frac{n\sigma^2\lambda^2}{2(1-\lambda b/3)},\qquad 0<\lambda<3/b.\]

Here we used \(k!\ge2\cdot3^{k-2}\). Chernoff's inequality with \(\lambda=x/(n\sigma^2+bx/3)\) bounds the upper tail by \(\exp\{-x^2/[2(n\sigma^2+bx/3)]\}\). Apply the same estimate to \(-Y_i\), add the two tails, and set \(x=t\sqrt n\). If \(\sigma=0\), the summands vanish almost surely; the result is immediate. ◻

Lemma 2 (Finite-class maximal inequality, bounded case). Let \(\{f_1,\dots,f_N\}\) be a finite collection with \(Pf_k=0\), \(\|f_k\|_\infty\le M\), and \(\|f_k\|_{P,2}\le \delta\) for all \(k\). Then

\[\mathbb{E}\Big[\max_{1\le k\le N}|\mathbb G_n f_k|\Big] \lesssim \delta\,\sqrt{\log(2N)} + \frac{M}{\sqrt n}\log(2N).\]

Proof. For \(0<t<3\sqrt n/M\), the power-series proof of Bernstein's inequality gives

\[\log\mathbb{E}e^{\pm t\mathbb G_nf_k}\le\frac{t^2\delta^2}{2(1-tM/(3\sqrt n))}.\]

Put \(L=\log(2N)\). Jensen and the bound of a maximum by a sum of exponentials imply

\[\mathbb{E}\max_k|\mathbb G_nf_k|\le\frac Lt+\frac{t\delta^2}{2(1-tM/(3\sqrt n))}.\]

Choose \(t=\min\{\sqrt L/\delta,\sqrt n/M\}\). The denominator stays at least \(2/3\). If the first choice is smaller, both terms are bounded by a constant times \(\delta\sqrt L\); otherwise \(\delta^2\sqrt n/M\le\delta\sqrt L\) and \(L/t=ML/\sqrt n\). The zero-variance case is immediate. ◻

1. A local maximal inequality under bracketing (bounded case)

Write \(\operatorname{Log}x=\max(1,\log x)\), and use the same convention as the preceding post:

\[J_{[\:]}(r,\mathcal G,\|\cdot\|)=\int_0^r\sqrt{\operatorname{Log}N_{[\:]}(u,\mathcal G\cup\{0\},\|\cdot\|)}du.\]

Lemma 3 (Local bounded bracketing inequality). Let \(\mathcal G\) be pointwise measurable, with \(|g|\le1\) and \(Pg^2<r^2\) for every \(g\). Then

\[\mathbb{E}\|\mathbb G_n\|_{\mathcal G}\lesssim J_{[\:]}(r)\left(1+\frac{J_{[\:]}(r)}{r^2\sqrt n}\right).\tag{1}\]

The same bound holds for the Rademacher process \(n^{-1/2}\sum_i\varepsilon_i g(X_i)\).

Proof. We use the nested brackets and first-failure decomposition from Theorem 6 of the preceding note, but allow failure already at the coarsest scale. This supplies the extra quadratic entropy term. It also proves the bounded local theorem stated in van der Vaart, Asymptotic Statistics, Lemma 19.36, p. 288.

Write \(H(u)=\operatorname{Log}N_{[\:]}(u,\mathcal G\cup\{0\},L^2(P))\), \(r_q=4r2^{-q}\), and \(J=\int_0^r\sqrt{H(u)}du\). The case \(J=\infty\) is immediate. Refine the brackets at levels \(0,\ldots,q\) into nested cells, with at most \(K_q=\prod_{j=0}^qN_{[\:]}(r_j)\) cells. Intersect their brackets and clip endpoints to \([-1,1]\). Let \(\Delta_q\) be the resulting width and choose a representative \(\pi_qg\in\mathcal G\cup\{0\}\) in each nonempty cell. Then \(\Delta_q\le\Delta_{q-1}\), \(P\Delta_q^2\le r_q^2\), and both \(g\) and \(\pi_qg\) lie in that bracket. Put

\[L_q=1+\sum_{j=0}^q\log N_{[\:]}(r_j),\qquad a_q=\frac{r_q}{\sqrt{L_{q+1}}},\qquad A_q=\prod_{j=0}^q1\{\Delta_j\le\sqrt n a_j\},\quad A_{-1}=1,\quad B_q=A_{q-1}-A_q.\]

Unlike the globally truncated proof, \(B_0\) need not vanish. The exact decomposition is

\[g=\pi_0g+(g-\pi_0g)B_0+\sum_{q=1}^m(\pi_qg-\pi_{q-1}g)A_{q-1}+\sum_{q=1}^m(g-\pi_qg)B_q+(g-\pi_mg)A_m.\]

The last term has absolute value at most \(\sqrt n a_m\), so its centered empirical process is at most \(2na_m\), uniformly in \(g\), and tends to zero. For every \(q\ge1\), the same finite-class Bernstein bounds as in Theorem 6 give a bound \(C r_q\sqrt{L_{q+1}}\) for the expected supremum of the increment and stopped residual at that level. Explicitly, increments have \(L^2(P)\) size at most \(2r_q\) and uniform bound \(\sqrt n a_{q-1}\). For residuals use the finite majorants \(v_q=\Delta_qB_q\), with

\[Pv_q\le\frac{P\Delta_q^2}{\sqrt n a_q}\le\frac{r_q^2}{\sqrt n a_q},\qquad |(g-\pi_qg)B_q|\le v_q,\qquad |\mathbb G_nh|\le|\mathbb G_nv_q|+2\sqrt n Pv_q\quad(|h|\le v_q).\]

All these classes have at most \(K_q\) elements. Centering doubles their uniform bounds at most. Thus the finite-class lemma applies without assuming the functions themselves have mean zero. The geometric-scale summation proved in Theorem 6 gives

\[\sum_{q\ge1}r_q\sqrt{L_{q+1}}\le C J.\]

It remains to control level zero. Its representatives satisfy \(P(\pi_0g)^2<r^2\) and \(|\pi_0g|\le1\). Its residual majorants \(v_0=\Delta_0B_0\) have \(Pv_0^2\le r_0^2\), \(|v_0|\le2\), and \(Pv_0\le r_0^2/(\sqrt n a_0)\). Lemma 2 and the preceding majorant inequality therefore bound these two terms by

\[C\left(r\sqrt{L_0}+\frac{L_0}{\sqrt n}+\frac{r_0^2}{a_0}\right)\le C\left(r\sqrt{H(r)}+\frac{H(r)}{\sqrt n}\right)\le C\left(J+\frac{J^2}{r^2\sqrt n}\right).\]

Here \(L_0\le2H(r)\), \(L_1\le3H(r)\), and \(r\sqrt{H(r)}\le J\). Combining the coarse and fine terms proves the centered assertion. The proof bounds every supremum by finite measurable majorants and a deterministic remainder; consequently it also gives the corresponding outer-expectation bound without pointwise measurability.

For the symmetrized assertion, apply the same theorem on the product space with law \(Q=P\otimes\operatorname{Unif}\{-1,1\}\), to \(h_g(x,e)=eg(x)\). These functions have \(Qh_g=0\), \(Qh_g^2=Pg^2<r^2\), and absolute bound one. A bracket \([l,u]\) for \(g\) induces the bracket with endpoints

\[L(x,e)=\begin{cases}l(x),&e=1,\\-u(x),&e=-1,\end{cases}\qquad U(x,e)=\begin{cases}u(x),&e=1,\\-l(x),&e=-1.\end{cases}\]

Its width is \(u-l\) for both signs, so its \(L^2(Q)\) width equals the original \(L^2(P)\) width. Thus the product-space entropy is no larger, and its centered empirical process is exactly the Rademacher process. ◻

The stopping step is essential here. Small population bracket widths do not by themselves imply that the expected supremum of their empirical widths is small. Nor can one sum a fixed uniform Bernstein bound at every finer scale: its linear terms need not be summable. The stopped-chain proof accounts for both difficulties, and produces the quadratic entropy term \(J_{[\:]}(r)^2/(r^2\sqrt n)\) in (1).

2. A simple inequality connecting \(J_{[\:]}\) and the top bracket count

Lemma 4. With the definition above,

\[\operatorname{Log}N_{[\:]}(\delta,\mathcal F\cup\{0\},\|\cdot\|)\le\frac{J_{[\:]}(\delta,\mathcal F,\|\cdot\|)^2}{\delta^2}.\]

Proof. The bracketing count is nonincreasing in its radius. Its integrand on \((0,\delta)\) is therefore at least its value at \(\delta\). Integrate and square. ◻

2.1. Proof of Theorem 8

If \(M=0\), the class is zero and the result is immediate. For \(M>0\), set \(\mathcal G=\{f/M:f\in\mathcal F\}\) and \(r=\delta/M\). The hypotheses of Lemma 3 hold. Scaling the bracket endpoints gives the exact identity

\[J_{[\:]}(r,\mathcal G,L^2(P))=M^{-1}J_{[\:]}(\delta,\mathcal F,L^2(P)).\]

Multiply the bound in Lemma 3 by \(M\). Since \(r^2=\delta^2/M^2\), the result is

\[\mathbb{E}\|\mathbb G_n\|_{\mathcal F}\lesssim J_{[\:]}(\delta)\left(1+\frac{M J_{[\:]}(\delta)}{\delta^2\sqrt n}\right),\]

which proves Theorem 8. Lemma 4 explains why a contribution from the coarsest bracket count fits this order; the stopped-chain argument in Lemma 3 controls all finer scales.

2.2. Proof of Theorem 9

We first prove the exponential-moment estimate, then prove its local bracketing consequence by the stopped-chain construction.

Definition 5 (Bernstein size). For a measurable \(f:\mathscr X\to\mathbb R\) define

\[\|f\|_{P,B}^2 \equiv 2\mathbf P\,\,\!\!\big(e^{|f|}-1-|f|\big).\]

This quantity is finite only under an exponential-moment condition, and is not a norm: it is not homogeneous. Bracketing uses it as a monotone measure of the size of a nonnegative width. The scalar inequality \(e^{|x|}-1-|x|\ge x^2/2\) gives \(\|f\|_{P,2}\le\|f\|_{P,B}\).

Lemma 6 (Key exponential-moment inequality from \(\|\cdot\|_{P,B}\)). Let \(f\) be measurable and set \(b^2 \equiv \|f\|_{P,B}^2<\infty\). Then for every \(|t|\le1\),

\[\log \mathbf P\,\,\!\!\exp\big(t(f-\mathbf P\,\,\!\!f)\big) \le \frac{t^2}{2}\,b^2.\]

Consequently, for every \(|t|\le\sqrt n\),

\[\log \mathbb{E}\exp\big(t\,\mathbb G_n f\big) \le \frac{t^2}{2}\,b^2.\]

Proof of Lemma 6. The finite Bernstein quantity implies integrability of the terms below.

2.2.1. Step 1: a scalar inequality.

For every real \(x\) and \(|t|\le1\), the exponential power series gives

\[e^{tx}-1-tx\le\sum_{j\ge2}\frac{|t|^j|x|^j}{j!}\le t^2(e^{|x|}-1-|x|).\]

2.2.2. Step 2: bound on the moment generating function.

Integrate the scalar inequality without replacing its linear term by an absolute value:

\[Pe^{tf}\le1+tPf+\frac{t^2b^2}{2}.\]

Using \(\log y\le y-1\) for \(y>0\), we obtain the exact cancellation on centering:

\[\log Pe^{t(f-Pf)}=\log Pe^{tf}-tPf\le\frac{t^2b^2}{2}.\]

2.2.3. Step 3: extend to \(\mathbb G_n f\).

For \(|t|\le\sqrt n\), independence gives

\[\log\mathbb{E}e^{t\mathbb G_nf}=n\log Pe^{(t/\sqrt n)(f-Pf)}\le\frac{t^2b^2}{2}.\]

This proves both signs of the mgf bound. ◻

Lemma 7 (Finite-class maximal inequality, Bernstein case). Let \(\{f_1,\dots,f_N\}\) be a finite collection with \(\|f_k\|_{P,B}\le \delta\) for all \(k\). Then

\[\mathbb{E}\Big[\max_{1\le k\le N}|\mathbb G_n f_k|\Big] \lesssim \delta\sqrt{\log(2N)} + \frac1{\sqrt n}\log(2N).\]

Proof of Lemma 7. Put \(L=\log(2N)\). Lemma 6 and log-sum-exp imply, for \(0<t\le\sqrt n\),

\[\mathbb{E}\max_k|\mathbb G_nf_k|\le\frac Lt+\frac{t\delta^2}{2}.\]

Choose \(t=\min\{\sqrt{2L}/\delta,\sqrt n\}\). If the constraint is active then \(\delta^2\sqrt n/2\le L/\sqrt n\); otherwise the two terms balance. This proves the claimed bound. ◻

Lemma 8 (Local Bernstein bracketing inequality). Let \(\mathcal G\) be pointwise measurable and \(\|g\|_{P,B}<r\) for every \(g\). With \(J_B(r)=J_{[\:]}(r,\mathcal G,\|\cdot\|_{P,B})\),

\[\mathbb{E}\|\mathbb G_n\|_{\mathcal G}\lesssim J_B(r)\left(1+\frac{J_B(r)}{r^2\sqrt n}\right).\]

Proof. Use the preceding proof of Lemma 3 with \(H(u)=\operatorname{Log}N_{[\:]}(u,\mathcal G\cup\{0\},\|\cdot\|_{P,B})\), the same scales \(r_q=4r2^{-q}\), nested cells, and stopping thresholds. Intersections only decrease nonnegative bracket widths. Hence their Bernstein sizes remain at most \(r_q\), and their \(L^2(P)\) sizes are at most \(r_q\) because \(x^2\le2(e^{|x|}-1-|x|)\). Representatives are selected from their cells, so \(\|\pi_0g\|_{P,B}<r\).

At every level \(q\ge1\), the stopped increments and majorants are uniformly bounded by \(\sqrt n a_{q-1}\). Thus the bounded finite-class inequality applies exactly as before: this part of the proof requires only their \(L^2(P)\) widths and the stopping bound, and contributes at most \(CJ_B(r)\). The remainder still vanishes uniformly, being bounded by \(2na_m\).

At level zero the functions need not be uniformly bounded. Apply Lemma 7 instead. The representatives have Bernstein size less than \(r\). The majorants \(v_0=\Delta_0B_0\) have Bernstein size at most \(r_0\), by monotonicity, and

\[Pv_0\le\frac{P\Delta_0^2}{\sqrt n a_0}\le\frac{r_0^2}{\sqrt n a_0}.\]

Consequently their total contribution is bounded by

\[C\left(r\sqrt{L_0}+\frac{L_0}{\sqrt n}+\frac{r_0^2}{a_0}\right)\le C\left(J_B(r)+\frac{J_B(r)^2}{r^2\sqrt n}\right).\]

This proves the result, including its outer-expectation version. No triangle inequality or homogeneity for the Bernstein size is used. The statement agrees with van der Vaart, Asymptotic Statistics, Lemma 19.37, p. 289. ◻

To obtain Theorem 9, apply Lemma 8 with \(\mathcal G=\mathcal F\) and \(r=\delta\). Its moment assumption, bracket widths and entropy integral agree exactly with those in that theorem, so the displayed inequality is the required conclusion. No homogeneity of the Bernstein size is used.