Supremum-Norm Rates And Logarithmic Factors

Why the Largest Error Costs More

Integrated squared error averages performance over the covariate space. Supremum-norm error instead asks how badly an estimator performs at its worst location. Even if errors in individual regions are modest, taking the largest across many regions makes large fluctuations more likely. In regular Hölder regression settings, this distinction introduces a logarithmic factor into the expected squared supremum-norm rate.

We work with a regression function \(m\) on \([0,1]^d\), with smoothness \(0<\beta<1\). The results below use a regular fixed design and sub-Gaussian noise for the upper bound, and Gaussian noise for the lower bound. This is a deliberately specified setting in which both the rate and the source of the logarithm can be seen directly.

For definiteness, let \(\mathcal H^\beta(L)\) be the Hölder class of functions satisfying \(\|m\|_\infty\le L\) and \(|m(x)-m(y)|\le L\|x-y\|_2^\beta\) for all \(x,y\in[0,1]^d\). In the regression model, \(Y_i=m(x_i)+\varepsilon_i\), where the design points \(x_i\) are fixed. Assume the errors are independent, have mean zero, and are \(\sigma\)-sub-Gaussian: \(E[\exp(t\varepsilon_i)]\le \exp(\sigma^2t^2/2)\) for every real \(t\). The design is regular in the sense that partitioning the cube into equal cubes of side \(h\) gives between \(cnh^d\) and \(Cnh^d\) design points in every cube, for fixed positive constants \(c,C\), at the resolutions used below.

The Rate and Its Comparison

Under these conditions, the characteristic expected squared supremum-norm rate is \((\log n/n)^{2\beta/(2\beta+d)}\). The corresponding integrated squared-error rate under regular design is \(n^{-2\beta/(2\beta+d)}\). Here integrated risk means \(E_m[\int_{[0,1]^d}(\hat m(x)-m(x))^2\,dx]\). The powers of \(n\) agree, but supremum loss has an extra logarithmic factor.

The upper bound balances two contributions. A partition with side length \(h\) approximates a Hölder function to order \(h^\beta\), so squared bias is of order \(h^{2\beta}\). There are about \(h^{-d}\) cells, and the largest noise fluctuation among their averages has squared size of order \(\log(1/h)/(nh^d)\). Balancing these terms yields the logarithmic rate.

Upper Bound: Controlling the Maximum Over Cells

Divide \([0,1]^d\) into \(K\) equal cubes of side \(h\), where \(K=h^{-d}\). On each cube, define \(\hat m\) to be the average of the responses whose design points fall in that cube. If \(x\) lies in a cube \(B\), the estimator’s mean on that cube is the average of \(m(x_i)\) over its design points. Every such \(x_i\) is within distance \(\sqrt d\,h\) of \(x\), so the Hölder condition gives

Write the centered noise average in cell \(B\) as \(Z_B\), and let \(N_B\) be its number of design points. Independence and the sub-Gaussian assumption imply \(P(|Z_B|>t)\le 2\exp(-N_Bt^2/(2\sigma^2))\). Since there are \(K\) cells and \(N_B\ge cnh^d\), the union bound gives

Integrating this tail bound yields \(E[\max_B|Z_B|^2]\le C_1\sigma^2\log(2K)/(nh^d)\) for a constant \(C_1\). For example, split the integral \(E[W^2]=\int_0^\infty P(W^2>s)\,ds\), with \(W=\max_B|Z_B|\), at \(s_0=2\sigma^2\log(2K)/(cnh^d)\). The integral below \(s_0\) is at most \(s_0\); above \(s_0\), the displayed exponential tail integrates to at most \(2\sigma^2/(cnh^d)\). Thus the stated bound follows.

For any \(x\), the estimation error is the sum of its cell’s bias and noise average. The inequality \((a+b)^2\le 2a^2+2b^2\) therefore gives

Choose \(h\) of order \((\log n/n)^{1/(2\beta+d)}\), rounding to an available partition resolution. Then \(h^{2\beta}\) has order \((\log n/n)^{2\beta/(2\beta+d)}\). Also \(\log(2h^{-d})\) has order \(\log n\), so the variance term has that same order. This proves the upper bound. \(\square\)

Lower Bound: Many Possible Locations for a Difficult Feature

The logarithm is not merely a weakness of the histogram estimator. To see why it is necessary, construct many regression functions that each contain one small, localized bump, with the bump placed in a different region. Each function is separated from the zero function by the same amount in supremum norm. Yet when the bump is narrow, its effect on the data is limited to a small part of the design. Distinguishing among many possible bump locations requires enough information to identify which location is active.

Here are the details of the lower-bound argument. Choose a fixed smooth function \(\phi\), supported strictly inside the unit cube, with \(\|\phi\|_\infty=1\). At a small scale \(h\), place \(M\) disjoint cubes inside \([0,1]^d\), with \(M\) of order \(h^{-d}\), and let \(z_j\) be the lower corner of cube \(j\). For a sufficiently small constant \(a>0\), define

The supports are disjoint, and scaling the bump by \(h^\beta\) keeps its Hölder-\(\beta\) constant bounded uniformly in \(h\). Choosing \(a\) small enough places every \(m_j\) in \(\mathcal H^\beta(L)\). Their pairwise supremum distances are \(a h^\beta\). If the errors are Gaussian with variance \(\sigma^2\), the Kullback–Leibler divergence from the data distribution under \(m_j\) to that under the zero function is

The inequality follows because the bump is bounded by \(a h^\beta\) and its support contains at most a constant times \(nh^d\) design points. Take \(h\) of order \((\log n/n)^{1/(2\beta+d)}\). Then \(\log M\) is of order \(\log n\), and the divergence bound is at most a sufficiently small constant times \(\log M\), by choosing \(a\) small enough.

Fano’s inequality states that, for \(M\) possible labels with uniform prior, the probability of incorrectly identifying the label is at least \(1-(I+\log 2)/\log M\), where \(I\) is the mutual information between the label and the data. In this construction, \(I\) is at most the average divergence to the zero-function distribution, so the choice just made ensures a classification error probability bounded away from zero for large \(n\). Given any estimator, classify it by the closest \(m_j\) in supremum norm. If its supremum error is less than \(a h^\beta/2\), the classification is correct, because the alternatives are separated by \(a h^\beta\). Thus its worst-case expected squared supremum error is at least a positive constant times \(h^{2\beta}\). Substituting the chosen \(h\) gives the lower rate \((\log n/n)^{2\beta/(2\beta+d)}\). \(\square\)

What the Logarithm Means in Practice

A useful way to remember the contrast is that integrated loss aggregates errors across locations, whereas supremum loss is sensitive to the worst one. A resolution with \(K\) local regions requires controlling all \(K\) noise averages at once; their maximum typically brings in a factor of order \(\log K\) in squared error. At the optimal resolution, \(K\) grows with \(n\), and \(\log K\) is of order \(\log n\). This is the source of the extra factor in the rate.

The theorem’s assumptions matter. The design must supply enough observations in every region at the selected resolution; a region with very few observations can have much larger noise. The noise tail condition supports the maximum-fluctuation bound, while the lower bound uses Gaussian noise to exhibit a concrete hard subproblem. The stated result is for \(0<\beta<1\); higher smoothness requires approximation methods that use the additional smoothness, while the same logarithmic comparison is the standard one in regular settings.

• Mistake: Reusing the integrated squared-error rate as the supremum-norm rate because their powers of \(n\) match. Correction: The supremum rate also contains \((\log n)^{2\beta/(2\beta+d)}\).
• Mistake: Treating the logarithm as an arbitrary penalty caused only by a crude union bound. Correction: The localized-bump lower bound shows that identifying the worst region creates a genuine minimax cost.
• Mistake: Comparing rates while changing the loss or omitting the square. Correction: Here both displayed rates concern squared error; the supremum loss squares \(\|\hat m-m\|_\infty\).