Approximation Error in Uniform And Lp Norms

Why Approximation Error Needs a Norm

A network produces a function, while a target describes the function we would like it to reproduce. Saying that the network is “close” to the target is incomplete until we specify how discrepancies across the input domain are combined. A large error at one input can matter greatly under a uniform criterion, whereas an \(L^p\) criterion averages error according to a chosen measure. Both criteria concern functions over a domain, not just the observed training points.

Throughout, let \(\mathcal X\) be a domain, let \(f:\mathcal X\to\mathbb R\) be a measurable target, and let \(\mathcal N\) be a fixed class of network output functions. Let \(\mu\) be a specified probability measure on \(\mathcal X\). The approximation error depends on all three choices: the target, the candidate class, and the measure or norm.

Definition: For a measurable function \(g\), its uniform norm on \(\mathcal X\) is \(\|g\|_{\infty,\mathcal X}=\sup_{x\in\mathcal X}|g(x)|\), when this supremum is finite. For \(1\le p<\infty\), its \(L^p(\mu)\) norm is \(\|g\|_{L^p(\mu)}=(\int_{\mathcal X}|g(x)|^p\,d\mu(x))^{1/p}\). Its \(L^\infty(\mu)\) norm is the essential supremum of \(|g|\) with respect to \(\mu\): the smallest \(c\ge 0\) such that \(|g(x)|\le c\) for \(\mu\)-almost every \(x\).

The uniform norm and the \(L^\infty(\mu)\) norm need not agree. The former considers every point of the domain; the latter ignores sets of \(\mu\)-measure zero. For continuous functions on a compact domain with a measure that assigns positive mass to every nonempty open set, they agree. For a discontinuous target, that agreement may fail at isolated points. When a probability measure is used, \(L^p(\mu)\) errors are averages with respect to that measure, not necessarily averages over the geometric domain.

Definition: The best uniform approximation error of \(\mathcal N\) to \(f\) on \(\mathcal X\) is \(A_\infty(f,\mathcal N;\mathcal X)=\inf_{h\in\mathcal N}\|f-h\|_{\infty,\mathcal X}\). For \(1\le p\le\infty\), the best \(L^p(\mu)\) approximation error is \(A_p(f,\mathcal N;\mu)=\inf_{h\in\mathcal N}\|f-h\|_{L^p(\mu)}\). These are infima; a function attaining the infimum need not exist unless additional conditions on the class are imposed.

A network architecture and parameter constraints determine \(\mathcal N\), but these definitions do not require a particular architecture. They measure the smallest possible discrepancy within the chosen class, not the result of a particular optimization algorithm. In the calculations below, \(\mathcal N_C\) denotes all constant functions, and \(\mathcal N_A\) denotes all affine functions \(h(x)=a+bx\) on \([0,1]\). We take \(\mu\) to be the uniform probability measure on \([0,1]\), so integrals with respect to \(\mu\) are ordinary integrals over that interval.

Uniform Error Controls Average Error

On a probability space, a uniform bound implies a bound on every finite-\(p\) error. This gives a useful comparison, but not an equality: an error confined to a small region can have a modest \(L^p\) norm while remaining large in the uniform norm.

Theorem: If \(\mu\) is a probability measure and \(1\le p<\infty\), then every measurable \(g\) with finite uniform norm satisfies \(\|g\|_{L^p(\mu)}\le \|g\|_{\infty,\mathcal X}\). Consequently, \(A_p(f,\mathcal N;\mu)\le A_\infty(f,\mathcal N;\mathcal X)\) whenever the uniform errors are finite.

Bound the integrand.
By the definition of the uniform norm, \(|g(x)|^p\le \|g\|_{\infty,\mathcal X}^p\) for every \(x\).

Integrate under a probability measure.
Integrating gives \(\int |g|^p\,d\mu\le \|g\|_{\infty,\mathcal X}^p\mu(\mathcal X)=\|g\|_{\infty,\mathcal X}^p\).

Take roots and infima.
Taking the \(p\)th root proves the norm inequality. Applying it to \(g=f-h\) for each \(h\in\mathcal N\), then taking the infimum over \(h\), proves the approximation-error inequality. \(\square

The probability-measure assumption matters. If \(\mu\) has total mass \(M\), the same argument gives \(\|g\|_{L^p(\mu)}\le M^{1/p}\|g\|_{\infty,\mathcal X}\). Also, the theorem compares errors only after the measure and domain have been specified; changing the measure changes the \(L^p\) approximation problem.

Best Constant Approximation

The class \(\mathcal N_C\) gives transparent calculations. It is also a useful baseline: it shows that even when the candidate class is simple, the loss criterion changes what “best” means.

Result: For any bounded target \(f\) on \(\mathcal X\), the best uniform constant error is half its range: \(\inf_{c\in\mathbb R}\sup_{x\in\mathcal X}|f(x)-c|=(\sup_x f(x)-\inf_x f(x))/2\). A minimizing constant is the midpoint of the supremum and infimum.

To prove this, write \(M=\sup_x f(x)\) and \(m=\inf_x f(x)\). For every constant \(c\), the triangle inequality gives \(M-m\le |M-c|+|c-m|\le 2\sup_x|f(x)-c|\), where the same bound follows by taking sequences of function values approaching \(M\) and \(m\) if either extremum is not attained. Thus the error is at least \((M-m)/2\). Taking \(c=(M+m)/2\) gives \(|f(x)-c|\le(M-m)/2\) for every \(x\), proving equality. \(\square\)

Worked Example: A Constant Target

Let \(f(x)=3\) on \([0,1]\), and use \(\mathcal N_C\). Choosing the constant \(c=3\) gives \(|f(x)-c|=0\) at every point. Since an error norm cannot be negative, this is the minimum. Therefore \(A_\infty=0\), and for every \(1\le p\le\infty\), \(A_p=0\). The uniform and \(L^p\) criteria agree because the target itself belongs to the candidate class.

Worked Example: A Linear Target Approximated by Constants

Let \(f(x)=x\) on \([0,1]\), first with \(\mathcal N_C\). For the uniform error, a constant \(c\) has error \(\max(|c|,|1-c|)\). This maximum is minimized at \(c=1/2\), where both endpoint errors are \(1/2\). Hence \(A_\infty=1/2\).

For \(1\le p<\infty\), define \(J(c)=\int_0^1|x-c|^p\,dx\). This is a convex function of \(c\), since \(c\mapsto |x-c|^p\) is convex for each \(x\). Changing variables from \(x\) to \(1-x\) shows \(J(c)=J(1-c)\). Convexity and this symmetry imply \(J(1/2)\le [J(c)+J(1-c)]/2=J(c)\), so \(c=1/2\) minimizes the integral. Its value is \(J(1/2)=2\int_0^{1/2}(1/2-x)^p\,dx=2(1/2)^{p+1}/(p+1)=1/[2^p(p+1)]\). Thus \(A_p=1/[2(p+1)^{1/p}]\). For example, \(A_2=1/\sqrt{12}\).

If the candidate class is instead \(\mathcal N_A\), the target \(f(x)=x\) itself is in the class, with \(a=0\) and \(b=1\). Both the uniform and every \(L^p\) best approximation error are then zero.

Worked Example: A Step Target Under Two Criteria

Define \(f(x)=0\) for \(0\le x<1/2\) and \(f(x)=1\) for \(1/2\le x\le1\). For constant approximants \(c\), the uniform error is \(\max(|c|,|1-c|)\): values of the target occur arbitrarily close to both levels. The minimum is \(1/2\), attained at \(c=1/2\).

For finite \(p\), the two halves of the interval each have probability \(1/2\), so \(\|f-c\|_{L^p(\mu)}^p=(|c|^p+|1-c|^p)/2\). This expression is convex and symmetric about \(c=1/2\), hence is minimized there. Substitution gives \(( (1/2)^p+(1/2)^p)/2=(1/2)^p\), so \(A_p=1/2\) for every finite \(p\). The same value holds for \(p=\infty\).

Now allow affine approximants \(h(x)=a+bx\). The uniform error cannot be less than \(1/2\): continuity of \(h\) means its value as \(x\) approaches \(1/2\) from the left and right is the same, while the target levels on those sides are 0 and 1. If the uniform error is at most \(e\), taking these one-sided limits gives \(|h(1/2)|\le e\) and \(|1-h(1/2)|\le e\), which together imply \(e\ge1/2\). The constant \(h=1/2\) attains this bound.

For \(L^2(\mu)\), the minimizing affine function is the least-squares projection of \(f\) onto the span of \(1\) and \(x\). Its slope is \(\operatorname{Cov}(X,f(X))/\operatorname{Var}(X)\), with \(X\) uniform on \([0,1]\). Directly, \(E[X]=1/2\), \(E[f(X)]=1/2\), \(E[X^2]=1/3\), and \(E[Xf(X)]=\int_{1/2}^1x\,dx=3/8\). Therefore \(\operatorname{Var}(X)=1/12\) and \(\operatorname{Cov}(X,f(X))=3/8-1/4=1/8\), giving slope \(3/2\) and intercept \(1/2-(3/2)(1/2)=-1/4\). Also \(\operatorname{Var}(f(X))=1/4\). The squared residual norm is \(1/4-(1/8)^2/(1/12)=1/4-3/16=1/16\), so \(A_2=1/4\). Thus the affine class has uniform error \(1/2\) but \(L^2\) error \(1/4\); these are distinct measures of approximation, not conflicting answers.

Approximation Error Is Not Empirical Fit

The definitions above take norms over a domain or integrate under a specified measure. In contrast, for observed inputs \(X_1,\ldots,X_n\), the empirical \(L^p\) error of a function \(h\) is \((n^{-1}\sum_{i=1}^n|f(X_i)-h(X_i)|^p)^{1/p}\), with the empirical maximum as its uniform-sample counterpart. Minimizing this quantity over network parameters describes fit at the observed inputs. It does not, by definition, minimize error at unobserved inputs or under a population measure.

For a concrete contrast, take the step target above and observe only \(X_1=0.1\) and \(X_2=0.2\). The constant function \(h=0\) has empirical error zero because both observed target values are zero. Yet its population \(L^2\) error under the uniform measure is \((\int_0^1f(x)^2\,dx)^{1/2}=\sqrt{1/2}\), and its uniform error is 1. The discrepancy arises because the sample does not cover the right half of the domain.

A frequent mistake is to call the smallest training loss “the network approximation error.” That wording confuses two different objects. Approximation error is determined by the target, the candidate class, and the specified norm or measure. Empirical fit additionally depends on the observed sample and the optimization outcome. Good empirical fit alone does not establish small uniform or population \(L^p\) error.

Key takeaway: Always report the candidate function class and the criterion defining the error. Uniform error protects against large discrepancies anywhere in the domain; \(L^p\) error weights discrepancies through a measure. Neither one is interchangeable with training error.

Check Your Understanding

Work through these questions using the stated domain, function class, and measure.

For \(f(x)=2x-1\) on \([0,1]\), what is its best uniform approximation error using constant functions, and which constant attains it?
Why can the uniform norm differ from \(L^\infty(\mu)\) for a function that changes at a single point?
For the step target in the worked example, compute the \(L^2(\mu)\) error of the constant approximant \(h=0\).
State the probability-measure assumption used to conclude that an \(L^p\) error is no larger than the uniform error.
Give one reason why zero empirical error does not imply zero population approximation error.

Approximation Error in Uniform And Lp Norms

What You'll Learn