ReLU Approximation Rates For Hölder Functions

From Smoothness to a Uniform Approximation Rate

A function is easier to approximate when nearby inputs have similar outputs. Hölder smoothness quantifies that property: if the input changes by at most $h$, the output changes by at most a constant times $h^\alpha$. A mesh with spacing $h$ can therefore support an approximation whose uniform error is of order $h^\alpha$. To turn this into a neural approximation result, we need both an error bound and a way to represent the mesh interpolant with ReLU units.

This tutorial treats Hölder exponents $0<\alpha\leq 1$ on the cube $\Omega=[0,1]^d$. This range includes Lipschitz functions and functions such as the square root near zero. The construction uses affine interpolation on a simplicial mesh; it does not require fitting the function from data.

Definition: A function $f:\Omega\to\mathbb{R}$ is Hölder continuous of exponent $\alpha$ with constant $L$ if $0<\alpha\leq 1$, $L\geq 0$, and $$ |f(x)-f(y)|\leq L\|x-y\|_2^\alpha \qquad\text{for all }x,y\in\Omega. $$ The uniform norm of an error function $g$ is $\|g\|_\infty=\sup_{x\in\Omega}|g(x)|$.

A ReLU is the function $\rho(t)=\max\{t,0\}$. A ReLU network here means a feedforward network with affine maps between layers, ReLU applied to hidden units, and an affine scalar output. We measure its size by the number of nonzero weights and biases, allowing sparse connections. This convention makes the count describe the actual construction rather than the number of entries in a dense matrix.

Constructing the Mesh Interpolant

Divide each coordinate interval into $m$ equal pieces. Each of the $m^d$ resulting cubes can be divided into $d!$ simplices by ordering the within-cube coordinates. The simplices fit together along shared faces and have diameter at most $$ h_m=\frac{\sqrt{d}}{m}. $$ The number of simplices is $R=d!m^d$. At every mesh vertex $v$, assign the value $f(v)$. On a simplex with vertices $v_0,\ldots,v_d$, define $I_m f$ by affine interpolation: if $x=\sum_{j=0}^d\lambda_jv_j$, where $\lambda_j\geq0$ and $\sum_j\lambda_j=1$, set $I_m f(x)=\sum_{j=0}^d\lambda_j f(v_j)$. On a shared face, this definition gives the same interpolation from either adjacent simplex, so $I_m f$ is continuous and piecewise affine.

Theorem: If $f$ is Hölder continuous of exponent $\alpha$ and constant $L$ on $[0,1]^d$, its simplicial interpolant satisfies $$ \|f-I_m f\|_\infty\leq L\left(\frac{\sqrt d}{m}\right)^\alpha. $$

Proof. Fix $x$ in a simplex with vertices $v_0,\ldots,v_d$, and write its barycentric coordinates as $\lambda_0,\ldots,\lambda_d$. Since these coordinates are nonnegative and sum to one, $$ \begin{aligned} |f(x)-I_m f(x)| &=\left|\sum_{j=0}^d\lambda_j\big(f(x)-f(v_j)\big)\right|\\ &\leq \sum_{j=0}^d\lambda_j|f(x)-f(v_j)|\\ &\leq \sum_{j=0}^d\lambda_j L\|x-v_j\|_2^\alpha\\ &\leq L h_m^\alpha\sum_{j=0}^d\lambda_j =L h_m^\alpha. \end{aligned} $$ This holds on every simplex, including its faces, so taking the supremum over the cube proves the result. $\square$

The argument uses only the Hölder inequality and the fact that the interpolant is a convex combination of vertex values. It does not require derivatives of $f$, nor does it assume that $f$ is well approximated by a global affine function.

Worked Example: Square Root Smoothness at the Boundary

Let $f(x)=\sqrt{x}$ on $[0,1]$. We first verify that it is Hölder with exponent $1/2$ and constant $1$. For $x,y\geq0$ with $x+y>0$, $$ |\sqrt{x}-\sqrt{y}|^2 =|x-y|\frac{|\sqrt{x}-\sqrt{y}|}{\sqrt{x}+\sqrt{y}} \leq |x-y|, $$ because $|\sqrt{x}-\sqrt{y}|\leq\sqrt{x}+\sqrt{y}$. If $x=y=0$, the desired inequality holds directly since both sides are zero. Thus $|f(x)-f(y)|\leq |x-y|^{1/2}$ for all $x,y\in[0,1]$.

With $m=100$ equal intervals, the mesh width is $h_m=0.01$. The interpolation theorem gives $$ \|f-I_{100}f\|_\infty\leq (0.01)^{1/2}=0.1. $$ The bound applies even on the first interval adjoining zero, where the derivative of $\sqrt{x}$ is unbounded. The estimate is uniform over the whole interval, not just at the grid points.

Realizing a Piecewise-Affine Function with ReLUs

The interpolant is continuous and piecewise affine, but it is not generally a single affine function. A useful exact representation fact is the finite lattice representation theorem for continuous piecewise-affine functions: if such a function has affine pieces $\ell_1,\ldots,\ell_R$, it can be written on its domain in the form $$ g(x)=\max_{1\leq i\leq R}\ \min_{j\in S_i}\ell_j(x), $$ where each $S_i$ is a nonempty subset of $\{1,\ldots,R\}$. Repetitions or redundant terms are allowed. The formula is a finite combination of maxima and minima of affine functions; it does not assert that $g$ is convex.

Each maximum and minimum can be computed exactly with ReLUs. For real numbers $a,b$, $$ \max(a,b)=\rho(a-b)+b,\qquad \min(a,b)=a-\rho(a-b). $$ Applying these identities repeatedly computes the maximum or minimum of any finite list. For an interpolant with $R$ affine pieces, each of the $R$ inner minima uses at most $R$ affine terms, and the outer maximum uses $R$ results. The affine forms and the reductions can therefore be implemented with at most $C_dR^2$ nonzero parameters for a constant $C_d$ depending only on dimension and the chosen network encoding. The affine coefficients themselves are the values and slopes of the interpolant; the bound counts their positions, not their magnitudes.

Constructive rate: For every integer $m\geq1$, there is a ReLU network $N_m$ such that $$ \|f-N_m\|_\infty\leq L\left(\frac{\sqrt d}{m}\right)^\alpha, \qquad \operatorname{size}(N_m)\leq C_d(d!m^d)^2. $$ Thus the mesh resolution is proportional to $m^{-1}$, while this general realization bound is proportional to $m^{2d}$.

The size bound combines two ingredients: the mesh has $R=d!m^d$ simplices and hence at most that many affine pieces, and the finite max-min construction has size of order $R^2$. In one dimension, exact ReLU spline representations can give a sharper count; the quadratic realization bound above is a convenient general multidimensional construction, not a claim of optimality.

Worked Example: A Lipschitz Function on a Square

Consider $f(x,y)=|x-y|$ on $[0,1]^2$. For $z=(x,y)$ and $z'=(u,v)$, the reverse triangle inequality and Cauchy–Schwarz give $$ \begin{aligned} |f(x,y)-f(u,v)| &\leq |(x-y)-(u-v)|\\ &\leq |x-u|+|y-v|\\ &\leq \sqrt{2}\sqrt{(x-u)^2+(y-v)^2}. \end{aligned} $$ So $f$ is Hölder with $\alpha=1$ and $L=\sqrt2$.

Take $m=10$. The mesh diameter is $\sqrt2/10$, so the uniform interpolation error is at most $$ Lh_m=\sqrt2\frac{\sqrt2}{10}=\frac{2}{10}=0.2. $$ There are $R=2m^2=200$ triangles in the specified square mesh. The general network construction therefore has size at most $C_2(200)^2=40{,}000C_2$, and its uniform error is at most $0.2$. The numerical bound on size is conservative, but the mesh, error, and dependence on $m$ are explicit.

Expressing the Bound in Terms of Network Size

Let $P$ be a size budget. Since the construction has size at most $C'_d m^{2d}$, where $C'_d=C_d(d!)^2$, we may choose an integer $m$ of order $(P/C'_d)^{1/(2d)}$, provided $P$ is large enough for $m\geq1$. Substitution into the interpolation error bound yields a constant $A_{d,\alpha}$, depending only on $d,\alpha$ and the construction, such that $$ \|f-N\|_\infty\leq A_{d,\alpha}L P^{-\alpha/(2d)} $$ for a network of size at most $P$, up to integer rounding and a fixed minimum budget. This is an upper bound from this particular construction; it is not a lower bound on what all ReLU networks can achieve.

Worked Example: Turning a Desired Error into a Mesh Size

Suppose $d=2$, $\alpha=1/2$, $L=1$, and the target uniform error is at most $\varepsilon=0.1$. The interpolation bound requires $$ \left(\frac{\sqrt2}{m}\right)^{1/2}\leq0.1. $$ Squaring both sides gives $\sqrt2/m\leq0.01$, hence $m\geq100\sqrt2$. The smallest integer choice is $m=142$. Indeed, $\sqrt2/142\leq0.01$, so the error bound is at most $0.1$. There are $R=2m^2=40{,}328$ triangles, and the general realization has size at most $C_2(40{,}328)^2$.

This example illustrates the cost of the conservative representation bound: the mesh resolution is dictated by the desired error, while the stated network-size estimate squares the number of mesh pieces. Other approximation constructions can improve such counts under additional structure or different realization arguments; the present bound makes the mesh-based reasoning transparent.

Why the Smoothness Exponent Matters

For a fixed mesh, increasing $\alpha$ improves the error rate $m^{-\alpha}$: more regular functions change less over a cell of diameter $m^{-1}$. Conversely, in high dimension the number of mesh cells grows rapidly, at rate $m^d$, and the general network realization adds another factor of order $m^d$. The dimension therefore affects the cost even when the smoothness constant and exponent are fixed.

The rate is a uniform approximation statement: it controls the largest error anywhere in the domain. This is stronger than an average-error guarantee. It depends on the target function belonging to a specified Hölder class, but it makes no claim about estimation from noisy observations, optimization, or generalization from a training sample.

Common Mistakes

Using only the mesh error as a network-size rate. The interpolant has error of order $m^{-\alpha}$, but the cost of realizing it must also be counted. Here the general realization has size of order $m^{2d}$, giving the stated size-based exponent $\alpha/(2d)$.
Calling an upper bound optimal. The construction proves that a network with a certain size achieves an error bound. It does not show that every network of that size must have at least that error.
Ignoring the domain and norm. The displayed constants use the Euclidean diameter of simplices in $[0,1]^d$ and a Euclidean Hölder condition. Changing the domain or norm changes the geometric constants.
Dividing by a quantity that can be zero. In the square-root verification, the rationalized expression uses $\sqrt{x}+\sqrt{y}$ in a denominator. It is used only when $x+y>0$; the case $x=y=0$ is checked separately.

Key takeaway: Hölder smoothness gives a uniform interpolation error of order $h^\alpha$ on a mesh of diameter $h$. A finite piecewise-affine realization then converts the mesh into a ReLU network. Keep approximation error, network size, and the assumptions on the target function distinct when interpreting the resulting rate.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

For a Hölder function on $[0,1]^d$, what is the interpolation-error bound when the mesh uses $m$ subdivisions per coordinate?
Why does the proof of the interpolation bound apply on a simplex face shared by two mesh cells?
If the number of affine pieces is $R$, what feature of the max-min construction leads to a size bound proportional to $R^2$?
For a Hölder function with exponent $\alpha=1$, how does the mesh-based uniform error change when $m$ is doubled?
Why does the network-size rate derived here not establish a lower bound or an optimal rate for all ReLU networks?