Supremum-Norm Adaptation and Logarithmic Penalties

Why Supremum-Norm Adaptation Changes the Noise Calculation

A smoothing estimator can have small error at each prespecified location and bandwidth, yet behave differently when the goal is to control its largest error over many locations and candidate bandwidths. The reason is selection: a data-driven procedure searches among several noisy estimates, and the selected one can be unusually favorable or unfavorable by chance. Supremum-norm analysis must therefore control fluctuations simultaneously, not one location and scale at a time.

This distinction explains the logarithmic penalties that arise in adaptive uniform estimation. The penalty is not an automatic surcharge for using a bandwidth selector: its size depends on how many locations and scales must be controlled, on their dependence, and on the target probability or risk. The finite-family calculation below makes these dependencies explicit.

Finite-Family Setup and Definition

Consider fixed design points \(x_1,\ldots,x_n\) and observations \(Y_i=m(x_i)+\varepsilon_i\), where \(m\) is the regression function. Assume the errors are independent, have mean zero, and are sub-Gaussian with common parameter \(\sigma\): for every real \(t\), \(E[\exp(t\varepsilon_i)]\leq \exp(\sigma^2t^2/2)\). For each candidate bandwidth \(h_j\), let a linear smoother at location \(x_r\) be \(\hat m_j(x_r)=\sum_{i=1}^n w_{j,r,i}Y_i\), with deterministic weights. The stochastic part is \(Z_{j,r}=\sum_i w_{j,r,i}\varepsilon_i\).

The weight vector determines the noise scale. Independence and the sub-Gaussian assumption imply that \(Z_{j,r}\) is sub-Gaussian with variance proxy \(\tau_{j,r}^2=\sigma^2\sum_i w_{j,r,i}^2\). Indeed, its moment generating function is bounded by multiplying the individual bounds: \(E[\exp(tZ_{j,r})]\leq\exp(t^2\tau_{j,r}^2/2)\). No independence between different locations or bandwidths is required for the maximum bounds below.

A Simultaneous Tail Bound

Proof. For any centered sub-Gaussian variable \(Z\) with proxy \(\tau^2\), the Chernoff bound gives \(P(Z>u)\leq\exp(-u^2/(2\tau^2))\): for \(t>0\), Markov's inequality and the moment generating function bound give \(P(Z>u)\leq\exp(-tu+t^2\tau^2/2)\), and minimizing at \(t=u/\tau^2\) yields the claim. Applying it to \(Z\) and \(-Z\) gives \(P(|Z|>u)\leq2\exp(-u^2/(2\tau^2))\). By the union bound, \[ P\!\left(\max_{r,j}|Z_{j,r}|>u\right) \leq 2MN\exp(-u^2/(2\tau^2)). \] Set \(u=\tau\sqrt{2\log(2MN/\delta)}\). The right side becomes \(2MN\exp[-\log(2MN/\delta)]=\delta\), proving the result. \(\square\)

The logarithm counts the family being controlled. If the location and bandwidth indices are treated as one finite family, its size is \(MN\). Dependence can make the union bound conservative, but cannot invalidate it. If the proxies vary, one may use the largest proxy \(\tau^2=\max_{r,j}\tau_{j,r}^2\), or apply a separate bound to each term with thresholds suited to its proxy.

Expected Maximum and the Cost of Searching

A probability guarantee is useful for selecting a threshold. For risk calculations, it is also useful to bound the expected maximum. Write \(W=\max_{r,j}|Z_{j,r}|\), and suppose again that there are \(K=MN\) terms with proxy at most \(\tau^2\).

Derivation. The same union bound gives \(P(W>t)\leq2K\exp(-t^2/(2\tau^2))\). For a nonnegative random variable, \(E[W]=\int_0^\infty P(W>t)\,dt\). Set \(a=\tau\sqrt{2\log(2K)}\). Bounding the integrand by 1 up to \(a\), and using the tail bound thereafter, gives \[ E[W]\leq a+2K\int_a^\infty\exp(-t^2/(2\tau^2))\,dt. \] For \(t\geq a>0\), \(1\leq t/a\). Hence \[ \int_a^\infty\exp(-t^2/(2\tau^2))\,dt \leq \frac{1}{a}\int_a^\infty t\exp(-t^2/(2\tau^2))\,dt =\frac{\tau^2}{a}\exp(-a^2/(2\tau^2)). \] Since \(\exp(-a^2/(2\tau^2))=1/(2K)\), the tail contribution is at most \(\tau^2/a\). Substituting the value of \(a\) proves the stated bound. \(\square\)

From Simultaneous Noise to a Logarithmic Rate Factor

A familiar bias-variance calculation illustrates how a simultaneous noise bound can change a smoothing rate. Suppose a one-dimensional smoother has worst-case bias bounded by \(C_bh^\beta\) over a Hölder class of smoothness \(\beta>0\), and its pointwise noise proxy is bounded by \(C_v\sigma^2/(nh)\). If its stochastic error must be controlled over \(M\) locations and \(N\) candidate bandwidths, the finite-family bound has stochastic size of order \(\sigma\sqrt{\log(2MN/\delta)/(nh)}\), up to constants.

Ignoring fixed constants and taking a fixed confidence level, balance the bias \(h^\beta\) with this stochastic size. The resulting bandwidth and error scale are

This is a calculation under the stated bias and variance bounds, not a universal minimax claim or a guarantee for every bandwidth selector. It shows exactly how a simultaneous stochastic requirement can insert a logarithmic factor into a supremum-norm benchmark. A selector based on pairwise comparisons must likewise calibrate its comparisons to simultaneous fluctuations; the earlier material on Lepski’s method supplies the selection principle, while the present calculation explains the scale of the noise threshold.

How Many Scales Are Being Searched?

The logarithm depends on the actual family that needs simultaneous control. At a single fixed location, searching \(N\) scales gives a threshold proportional to \(\sqrt{\log N}\). If scales are dyadic over a range whose endpoints differ by a power of \(n\), then \(N\) is typically of order \(\log n\), so \(\log N\) is of order \(\log\log n\). By contrast, controlling \(M\) locations with \(M\) of order \(n\) contributes \(\log M\), of order \(\log n\). In that setting, adding a logarithmic number of scales changes \(\log(MN)\) to \(\log n+\log\log n\), not to a new multiple of \(\log n\).

These are bookkeeping statements about a specified family, not a claim that every continuous-domain supremum has exactly \(n\) independent locations. Nearby smoother estimates are often strongly dependent, and a carefully justified maximal inequality or discretization may improve a crude union bound. Conversely, if the supremum is genuinely over a continuum, simply checking a finite grid is insufficient unless approximation between grid points is controlled.

Common Pitfall: Reusing a Pointwise Threshold After Selection

A common error is to calculate a valid error threshold for one prespecified bandwidth and then use that same threshold after choosing the bandwidth that looks best in the data. The reasoning silently treats the selected scale as fixed. It is not: the selection depends on the observed noise, so a favorable or unfavorable fluctuation can be selected along with the scale.

The correction is to identify the full family over which the guarantee must hold and control its maximum, using a threshold such as \(\tau\sqrt{2\log(2MN/\delta)}\) under the finite-family assumptions above. For pairwise bandwidth comparisons, apply a corresponding bound to the comparison errors, whose proxies depend on the differences between weight vectors. The number of comparisons and their proxies must be included in the calibration; a pointwise standard error alone does not provide simultaneous control.