Supremum-Norm Risk and Logarithmic Factors

Why Uniform Accuracy Costs More

An estimator can be accurate on average over the support and still make a noticeable error at one particular location. Supremum-norm risk asks for control of the largest error anywhere, so it is a stricter target than integrated risk. A useful way to anticipate the difference is to imagine estimating a density at many locations: even if the error at each location is usually modest, the largest of many errors tends to be larger.

For a density on a \(d\)-dimensional support and a Hölder smoothness index \(\beta\), the characteristic uniform-error rate is \((\log n/n)^{\beta/(2\beta+d)}\), under standard boundedness and regularity conditions. The logarithm arises from controlling errors at many locations simultaneously. The argument has two parts: an upper bound, where a union bound over bins or locations introduces \(\log n\), and a lower bound, where many distinguishable alternatives show that this price cannot generally be removed.

Uniform Error for a Histogram

Begin with a histogram on \([0,1]^d\), partitioning the cube into bins of side length \(h\). For a bin \(B_j\), let \(N_j\) be the number of observations in it, and define \(\hat f(x)=N_j/(n h^d)\) for \(x\in B_j\). Suppose \(0<\beta\leq1\), the density is bounded above by \(M\), and it satisfies the Hölder condition \(|f(x)-f(y)|\leq L\|x-y\|^\beta\). The histogram’s expectation in a bin is the average density over that bin. Its difference from the density at any point in the bin is at most \(L(\sqrt d\,h)^\beta\), because the bin diameter is \(\sqrt d\,h\).

Here is the stochastic part of the argument. For each bin, \(N_j\) is binomial with parameters \(n\) and \(p_j=P_f(X\in B_j)\), and \(p_j\leq M h^d\). Bernstein’s inequality for a binomial count gives, for \(t>0\), $$ P_f\left(\left|\frac{N_j}{nh^d}-\frac{p_j}{h^d}\right|>t\right) \leq 2\exp\left\{-\frac{n h^d t^2}{2(M+t/3)}\right\}. $$ This bound does not require the bin counts to be independent. A union bound over \(m=h^{-d}\) bins multiplies the right-hand side by \(m\). Consequently, choosing a sufficiently large constant \(A\), the maximum stochastic error has a tail bound of the form $$ P_f\left(\max_{1\leq j\leq m} \left|\frac{N_j}{nh^d}-\frac{p_j}{h^d}\right| >A\left\{\sqrt{\frac{\log(2m)+u}{nh^d}}+ \frac{\log(2m)+u}{nh^d}\right\}\right) \leq e^{-u},\qquad u\geq0. $$

Integrating this tail bound over \(u\geq0\) yields an expectation bounded by a constant times \(\sqrt{\log(2m)/(nh^d)}+\log(2m)/(nh^d)\), provided \(nh^d\) is large enough. The total error is no more than the stochastic maximum plus the largest binwise bias. The bias bound above and \(m=h^{-d}\) give the theorem. Thus the logarithm appears when one controls the maximum across \(m\) bins, not in the pointwise bias.

Balancing Bias and the Maximum Fluctuation

For a fixed-dimensional support, \(\log(2h^{-d})\) is of the same order as \(\log n\) at the optimal bandwidth. Balancing \(h^\beta\) against \(\sqrt{\log n/(nh^d)}\) gives $$ h^\beta\asymp\sqrt{\frac{\log n}{nh^d}} \quad\Longleftrightarrow\quad h^{2\beta+d}\asymp\frac{\log n}{n}. $$ Therefore \(h\asymp(\log n/n)^{1/(2\beta+d)}\), and the resulting error scale is \((\log n/n)^{\beta/(2\beta+d)}\). At this choice, the remaining linear term \(\log n/(nh^d)\) is smaller than the square-root term: their ratio is \(\sqrt{\log n/(nh^d)}\), which tends to zero for fixed \(\beta,d\). The same rate follows by optimizing the displayed histogram bound.

For smoothness \(\beta>1\), the same balance applies when the estimator has uniform bias \(O(h^\beta)\). Higher-order kernels or local polynomial constructions can supply that bias under suitable smoothness, kernel-moment, and boundary conditions. At a boundary, an uncorrected kernel can have a different bias order, so the required bias bound must be checked rather than assumed. The stochastic maximum still reflects the number of effectively distinct locations at resolution \(h\), which is of order \(h^{-d}\).

Why the Logarithm Cannot Usually Be Removed

An upper bound alone does not establish that a logarithm is necessary. A multiple-hypothesis construction gives the matching lower-bound order. The argument places many small, separated perturbations inside a smooth density class. Under supremum loss, confusing even one perturbation creates an error of the perturbation’s full height.

To see the construction, take the uniform density \(f_0=1\) on the cube. Choose a smooth function \(\psi\), supported inside the unit cube, with integral zero and \(\|\psi\|_\infty=1\). For small \(h\), place \(M\geq c h^{-d}\) disjoint translated cubes in the interior. For each cube location \(j\), define $$ f_j(x)=1+a\psi\left(\frac{x-z_j}{h}\right), \qquad a=c_0h^\beta, $$ where the translated function is zero outside its cube and \(c_0>0\) is a sufficiently small fixed constant. Each \(f_j\) integrates to one because \(\int\psi=0\). For small enough \(c_0\), it is nonnegative, and the scaled smooth bump has Hölder size bounded uniformly in \(h\). Thus these are members of the stipulated class. Since the supports are disjoint, \(\|f_j-f_k\|_\infty=a\) for distinct \(j,k\).

The Kullback–Leibler divergence from one observation under \(f_j\) to one under \(f_0\) is at most \(\int(f_j-1)^2\). Indeed, \(\log t\leq t-1\) gives $$ \int f_j\log f_j \leq\int f_j(f_j-1) =\int(f_j-1)^2 =a^2h^d\int\psi(u)^2\,du. $$ For \(n\) independent observations, the divergence is therefore at most \(C n h^{2\beta+d}\).

For completeness, the information step is as follows. Let \(J\) be uniform on the \(M\) alternatives and let the observations have density \(f_J\). If \(I(J;X_1,\ldots,X_n)\) denotes their mutual information with \(J\), then $$ I(J;X_1,\ldots,X_n)\leq \frac1M\sum_{j=1}^M \operatorname{KL}(f_j^{\,n},f_0^{\,n})\leq C n h^{2\beta+d}. $$ The first inequality follows by writing the average divergence to \(f_0^{\,n}\) as the mutual information plus the nonnegative divergence of the mixture distribution to \(f_0^{\,n}\). Fano’s inequality says that any rule \(\hat J\) for identifying \(J\) has error probability at least \(1-(I+\log 2)/\log M\). This follows from \(H(J)=\log M\) and \(H(J\mid X_1,\ldots,X_n)\leq\log2+P(\hat J\ne J)\log(M-1)\).

Choose \(h\) so that \(n h^{2\beta+d}\leq c_1\log M\), with \(c_1\) small enough to keep Fano’s error probability bounded away from zero. Because \(M\geq c h^{-d}\), this choice has order \(h\asymp(\log n/n)^{1/(2\beta+d)}\). Any density estimator can be turned into a classifier by choosing the closest \(f_j\) in supremum norm. If its error from the true \(f_j\) is less than \(a/2\), the nearest alternative must be \(f_j\), since the alternatives are \(a\) apart. Thus a classification error implies estimation error at least \(a/2\). The expected supremum loss is consequently at least a constant times \(a=h^\beta\), proving the stated lower-bound order. \(\square\)

Common Pitfall and Practical Meaning

A common mistake is to take a pointwise variance or error bound and report it as a supremum-norm bound. For example, the reasoning “the standard deviation at each point is of order \((nh^d)^{-1/2}\), so the uniform stochastic error has that same order” ignores the maximum over locations. The correction is to control the tail at every location and account for their number, typically with a union bound or an appropriate maximal inequality. At resolution \(h\), the effective number is of order \(h^{-d}\), producing a factor involving \(\sqrt{\log(h^{-d})}\) in the stochastic term.

The logarithmic factor is not a universal penalty attached to every risk. It belongs to the uniform loss and the need to control many locations at once. Integrated losses average errors over the support, while supremum loss is determined by the worst location. For density estimation over standard Hölder classes, the upper and lower arguments show that this distinction changes the rate from the pointwise scale by a logarithmic factor. It matters when the scientific aim is a simultaneous guarantee—for example, a density estimate that is uniformly accurate across an entire range—not merely good average performance.