Motivation
An existence statement about universal approximation becomes more useful when we can see the weights being constructed, identify the quantity that controls error, and count the required computational units. In several variables, a one-dimensional interpolation argument no longer suffices: interpolation weights multiply across coordinates. ReLU networks are piecewise affine, so an exact multiplication gate is unavailable. We must approximate multiplication and then track how its errors accumulate through the construction.
The method below separates two tasks. A tensor grid gives a classical continuous interpolant whose error follows from the target's modulus of continuity. A finite ReLU circuit approximates each product of interpolation weights. Adding the two errors produces an explicit network guarantee. The resulting size bound is intentionally elementary and can be expensive in dimension. Seeing that expense is part of understanding the theorem, rather than an inconvenience to hide behind the word universal.
Architecture matters throughout. We count scalar ReLU gates in an acyclic circuit whose affine edges may skip intermediate layers. We then explain a conversion to ordinary layers. A gate count is not a count of dense trainable parameters, nor a proof that a learning algorithm can infer the constructed weights from a small sample. These distinctions keep an approximation theorem from silently turning into an optimization or statistical claim.
Definitions
Definition 6.1.1
(Target class, grid hats, and circuit size)
Let , , satisfy and . Choose integer , mesh , and scalar grid hats
restricted to , where . They are nonnegative and sum to one. For each grid vertex , set . Circuit size counts ReLU gates; affine combinations and output biases are allowed. Depth is the largest number of ReLU gates along an input-to-output path.
The hats at boundary nodes are simply restrictions of the same formula. On each grid interval only two hats are nonzero, and they are the usual linear interpolation weights. Their tensor products therefore also form a nonnegative partition of unity. The ideal interpolant is , with vertices.
Concept lensAlgebraic
The tensor-hat interpolant is multilinear on each cell
On a cell write . Each factor of is then or , so is a polynomial of degree at most one in each separately. It is the unique such function taking the values at the corners. For this is bilinear interpolation, , and the products of weights are exactly what the ReLU multiplier must approximate.
For an integer , let be the linear interpolant of the square function on with equal intervals. Define , the clipping map onto , and the approximate multiplier
Its inputs will always lie in , so all square evaluations remain inside their declared interval. Clipping does not claim to approximate multiplication outside this input range.
Theorem/Proposition
Theorem 6.1.2
(A constructive approximation with an explicit error budget)
With the preceding assumptions, a ReLU circuit satisfies
One construction uses at most ReLU gates and depth at most . For and requested error , it suffices to choose
A continuous target on the cube also admits arbitrarily accurate such approximants: replace by its modulus of continuity .
Theorem 6.1.3
(Finite affine regions limit exactness and accuracy)
Restrict a standard ReLU network to a line segment. If its hidden-layer widths are , its output is piecewise affine on at most subintervals. Any piecewise affine function with at most intervals approximating on has uniform error at least . In particular no finite ReLU network represents a quadratic with nonzero second derivative exactly on a line interval.
The region bound is an upper bound, often loose. It does not assert that every choice of weights realizes that many intervals. The lower error bound uses the actual number of intervals, so replacing it by this upper bound gives a valid but potentially weak architectural limitation. The result concerns a restriction to one line and is not a sharp multidimensional lower bound.
Proof sketch or proof idea
We prove the two theorems in turn. The first proof adds an exact interpolation error to a separately controlled multiplication error.
Proof
(Interpolate exactly, then multiply approximately)
At any , the ideal weights sum to one. Every vertex with positive weight lies within infinity-distance of . Therefore
For a merely continuous target, the same argument gives . Compactness of the cube makes the modulus tend to zero, while also providing a finite bound . This interpolation step is exact and contains no neural-network approximation yet.
On a scalar interval , the linear interpolant of exceeds it by . With square mesh , the error is nonnegative and at most . The piecewise affine interpolant itself has the explicit hinge formula
Thus it uses ReLU gates plus an affine term. The algebraic identity shows that the un-clipped multiplier has error at most . Clipping cannot increase distance from the true product, which lies in : for any in that interval, . The multiplier therefore has error at most , output in , gate count , and ReLU depth at most two.
Approximate a -fold product sequentially. Begin with and put . Since both actual and approximate partial products remain in ,
Induction gives error at most .
Construct this way for every vertex and set . The coefficient bound gives . Add interpolation error to obtain the error bound. Duplicate all scalar hats for each vertex, charging gates per vertex; charge multipliers, each with gates. This proves the stated size upper bound without relying on sharing. One hat layer followed by the sequential two-layer multipliers gives depth . Finally, when , and the multiplication term is at most when .
Proof X-ray
Where clipping and the vertex count enter
The proof has two independent error sources joined by one triangle inequality: interpolation, which uses only the Lipschitz hypothesis and the partition of unity, and circuit error, which uses only the bound and the multiplier accuracy. Neither estimate knows about the other, so the parameters can be chosen in order: first for interpolation, then for the circuit, since depends on .
Clipping is used twice, and both uses are needed for the induction. It keeps each approximate partial product in , so the next multiplier's arguments stay inside the interval where has its stated accuracy; and it allows the bound that stops earlier errors from being amplified. The factor appears because independently approximated products need not retain an exact sum of one, so absolute errors are summed over all coefficients. Dropping this factor would require a new normalization or locality argument. Some specially designed multipliers preserve additional zero properties and permit sharper constructions; those improvements must be proved, not assumed for the current circuit.
To obtain ordinary consecutive layers, carry earlier gate outputs and the cube inputs through identity ReLU gates whenever needed. These quantities are nonnegative. Organizing by circuit depth uses at most ReLU units, with an affine output. This deliberately coarse conversion shows that the construction belongs to an ordinary finite feedforward architecture; it does not identify the smallest possible width. Counting trainable weights requires counting edges as well. Our acyclic circuit has at most directed weighted edges, a coarse upper bound that makes no sparsity promise.
The second theorem needs only a counting argument and one identity for the square.
Proof
(Count cuts layer by layer, then use a second difference)
Start with one interval on the input line. On each existing interval, the inputs to the next layer are affine functions of the line parameter. Each of its preactivations has at most one isolated zero there, unless it is identically zero and creates no new cut. The interval is therefore divided into at most pieces. Induct over layers; the affine output adds no cuts.
At least one of at most affine intervals has length . If is affine on this interval and its uniform error from the square is at most , subtract the affine identity from the corresponding quadratic identity
The three error terms have total absolute bound , so . This proves both the quantitative limitation and the impossibility of exact representation.
What the size formula teaches
The number of grid vertices grows as . Making the mesh finer therefore becomes expensive with dimension, even before multiplication accuracy is considered. This is an explicit manifestation of dimensional difficulty for a broad target class. Extra structure, such as dependence on few coordinates or a compositional target, can support different constructions, but no such structure was assumed here. A theorem for all Lipschitz functions should not quietly borrow a favorable structure from selected examples.
This upper bound lets the weights change with the target and the accuracy; it does not provide one fixed finite set of weights that approximates every target at once. The output coefficients are vertex values of the target, and the grid slopes change with the accuracy. If weight size, quantization precision or the way the data are obtained are also restricted, those restrictions must be tracked again; the present gate count does not already include their cost.
Sharper approximation constructions are developed in Yarotsky's research paper, including square and multiplication subnetworks. The present proof uses elementary uniform interpolation and has its own stated error and size constants. It does not claim that its polynomial square-gate cost is the strongest available depth-dependent result.
Worked examples
Worked example 6.1.4
(A two-input product)
For , one bilinear cell already interpolates the target exactly: only the vertex has nonzero label, and its tensor weight is . Use the inputs directly in . It has at most 29 ReLU gates, depth two and uniform error at most . This example benefits from its special algebraic structure; applying the general duplicate-every-vertex bound would count many unnecessary gates.
Worked example 6.1.5
(Tracking an intentionally conservative budget)
Take , , , requested error . Choose , so , then , since . The interpolation term is , and the multiplication term is . Their sum is below . The circuit count is at most , with depth three. This is a constructive sufficient budget, not evidence that every particular target needs sixteen thousand gates.
Worked example 6.1.6
(A line restriction limits a multivariate network)
Suppose a two-hidden-layer network has widths three and four. Along any input line its output has at most affine intervals. If the target restricted to that line is , uniform error cannot be below by the theorem. The numerical bound is weak but nonzero. Increasing dimension elsewhere does not remove a limitation already visible on one line; different weights may realize fewer intervals and therefore face a stronger lower bound.
Common mistakes
Counterexample mode
Exact multiplication is not a finite ReLU operation
If a finite ReLU network represented exactly on the unit square, restricting it to would represent exactly on . The finite-region theorem rules this out. The repair is to use an approximate multiplication module on a declared bounded domain and propagate its error through the subsequent computation.
Uniform continuity gives existence of a fine enough grid but no numerical mesh rate without a known modulus. Likewise, a gate count does not specify dense parameter count, bit precision, or sample complexity. Our construction uses target values at every grid vertex; a learning procedure with different information must justify how those values or comparable weights are obtained. Increasing depth can enlarge the available number of regions, but the simple region bound alone does not prove that a given optimization method will exploit them.
Common mistake
(Choosing the multiplier accuracy before the grid)
The circuit term contains , so can be fixed only after . If is chosen for a guessed grid and the mesh is later refined, the circuit term grows with and the error budget is no longer met. In the example with , keeping but refining to gives and a circuit term of about , which alone exceeds .
Common mistake
(Feeding an unclipped partial product into the next multiplier)
The multiplier guarantee is stated only for inputs in . Without , an approximate partial product can fall slightly outside ; the next square evaluation may then leave , where is a linear extrapolation with no guarantee, and the recurrence loses the bound . Clipping costs two gates per multiplier and is what makes the induction valid.
Summary
Tensor hats supply a controlled classical interpolant, square gates supply approximate multiplication, and clipping keeps the composition within its valid range. Error and gate counts can then be tracked explicitly. Finite affine regions also impose genuine limitations, so constructive universality and architectural constraints can be studied in the same calculation.
Exercises
Quick check
(Verify the partition-of-unity identity for scalar hats on one grid interval, then derive it for tensor weights.)
Write on the interval from to .
Solution · Answer
Between nodes and , only and are positive, with values and , where . Their sum is one, including endpoints. Summing all tensor products factors as the product over coordinates of these scalar sums, hence also equals one.
Quick check
(For , bound the square-gate error and multiplier error, and count multiplier ReLU gates.)
Solution · Answer
The square error is at most . The multiplier error is at most , and its gate count is . These are uniform upper bounds; clipping may improve the error at individual inputs.
Quick check
(Three numbers in are multiplied sequentially by modules each accurate within and clipped to . Bound the total error and identify the induction assumption that is needed.)
Solution · Answer
The first multiplication has error at most . Multiplying that approximation by the third number does not enlarge the propagated error, because the third factor is at most one; the new module adds at most . The result is within . Clipping guarantees that the intermediate approximate factor belongs to the domain on which the next module's error guarantee applies.
Quick check
(A piecewise affine approximant to on has at most ten intervals. What uniform error lower bound follows? Compare it with the error of interpolation on ten equal intervals.)
Solution · Answer
The lower bound is . Equal-mesh linear interpolation has exact maximum error for , because the interpolant lies above by . Subtracting the constant keeps the function continuous and piecewise affine and makes the error lie in , so the error is attained: the lower bound is sharp for ten intervals.