Polynomial Approximation With Deep Networks

From Multiplication to Polynomial Approximation

A polynomial is assembled from simple operations: variables are multiplied to form monomials, monomials are scaled, and the results are added. ReLU networks implement affine operations directly, but multiplication is not affine. The key construction is therefore to replace each product by a network that approximates multiplication on a bounded input set, then control the errors as those blocks are composed.

The important accounting is not only the error of one multiplication block. A monomial of degree $k$ uses several blocks, and a polynomial combines errors across its monomials. The resulting size bound reflects the number of monomials actually present, their degrees, the coefficient magnitudes, and the target accuracy. Dimension enters through how many monomials can occur.

Definition: A ReLU network is a composition of affine maps and the activation $\sigma(t)=\max\{t,0\}$ on hidden layers, followed by an affine output map. Its depth is the number of affine layers. In the size bounds below, network size means the number of nonzero scalar weights and biases; coefficients are real-valued and their bit precision is not counted. A polynomial has total degree at most $m$ if every monomial in it has total exponent at most $m$.

The Multiplication Building Block

We use the standard ReLU multiplication approximation on a fixed bounded domain. The preceding material on ReLU networks for multiplication establishes that for $0<\eta\leq 1/2$, there is a ReLU network $M_\eta$ such that

\sup_{(u,v)\in[-2,2]^2}|M_\eta(u,v)-uv|\leq\eta, \qquad \operatorname{depth}(M_\eta),\ \operatorname{size}(M_\eta) \leq C\bigl(1+\log_2(1/\eta)\bigr),

where $C$ is a constant independent of $\eta$. The fixed input bound matters: all applications below feed this block values in $[-2,2]$. One way to understand the construction is the identity $uv=((u+v)^2-(u-v)^2)/4$, together with a ReLU approximation to the square function. We use the multiplication guarantee rather than re-derive that earlier construction.

Worked Example: Choosing Precision for a Quadratic

Consider $p(x,y)=x^2+2xy+y^2$ on $[-1,1]^2$, and suppose the desired uniform error is at most $0.01$. Approximate each of its three degree-two monomials with one multiplication block.

For $x^2$, feed $(x,x)$ to $M_\eta$; for $xy$, feed $(x,y)$; and for $y^2$, feed $(y,y)$. Each monomial approximation has error at most $\eta$. After multiplying the $xy$ output by 2 and adding the three outputs, the polynomial error is bounded by

|p(x,y)-\widetilde p(x,y)| \leq \eta+2\eta+\eta=4\eta.

Thus $\eta=0.0025$ guarantees error at most $0.01$. The multiplier inputs are in $[-1,1]$, which is contained in its guaranteed domain $[-2,2]$. This construction uses three multiplication blocks, each with size bounded by a constant times $1+\log_2(400)$, plus the affine output operations.

Error in a Product of Many Factors

A monomial can be formed by multiplying its variables one at a time. The following error bound is useful because every exact partial product of inputs from $[-1,1]$ remains in $[-1,1]$. If each multiplier has error at most $\eta$, the error accumulated through $k-1$ products is at most $(k-1)\eta$, provided the approximate intermediate values remain in the multiplier's domain.

Result: Let $x_1,\ldots,x_k\in[-1,1]$, with $k\geq 2$. Define $z_1=x_1$ and $z_j=M_\eta(z_{j-1},x_j)$ for $j=2,\ldots,k$. If $0<\eta\leq \min\{1/2,1/(k-1)\}$, then every multiplier input belongs to $[-2,2]^2$, and $$ \left|z_k-\prod_{j=1}^k x_j\right|\leq (k-1)\eta. $$

Proof. Write $q_j=\prod_{i=1}^j x_i$. For $j=1$, $z_1=q_1$, so $|z_1-q_1|=0$. Suppose for some $j\geq2$ that $|z_{j-1}-q_{j-1}|\leq(j-2)\eta$. Since $|q_{j-1}|\leq1$,

|z_{j-1}|\leq |q_{j-1}|+|z_{j-1}-q_{j-1}| \leq 1+(j-2)\eta\leq 1+(k-2)\eta\leq2.

Also $|x_j|\leq1$, so $M_\eta$'s approximation guarantee applies. Consequently,

|z_j-q_j| \leq |M_\eta(z_{j-1},x_j)-z_{j-1}x_j| +|z_{j-1}x_j-q_{j-1}x_j| \leq \eta+|z_{j-1}-q_{j-1}| \leq(j-1)\eta.

Induction gives the claimed error at $j=k$, as well as the required input bound at every multiplication. $\square$

Worked Example: A Degree-Four Monomial

Approximate $x_1^2x_2x_3$ on $[-1,1]^3$. Treat it as the product of the four factors $x_1,x_1,x_2,x_3$, and use three multiplier blocks with $\eta=0.001$.

The first output approximates $x_1^2$ with error at most $0.001$. The second block multiplies that output by $x_2$, and the third multiplies the result by $x_3$. By the result just proved, the final error is at most

(4-1)\eta=3(0.001)=0.003.

The domain condition can be checked directly from the induction bound: before the third multiplication, the approximate partial product has absolute value at most $1+2(0.001)=1.002<2$. Each new variable has absolute value at most 1. Thus all three multiplier calls are within $[-2,2]^2$.

A Polynomial Construction and Its Bound

Write a polynomial in $d$ variables as

p(x)=\sum_{\alpha\in I}c_\alpha x^\alpha, \qquad x^\alpha=\prod_{j=1}^d x_j^{\alpha_j}, \qquad |\alpha|=\sum_{j=1}^d\alpha_j,

where $x\in[-1,1]^d$, $I$ is a finite set of distinct multi-indices, and $|\alpha|\leq m$ for every $\alpha\in I$. Let $s=|I|$, and let $A=\sum_{\alpha\in I}|c_\alpha|$. The constant monomial requires no multiplication; a monomial of degree $k\geq1$ can be made using $k-1$ multiplications, with repeated variables included as repeated factors.

Theorem: Suppose $A>0$, $m\geq2$, and $0<\varepsilon\leq1/2$. There is a ReLU network $\widetilde p$ such that $$ \sup_{x\in[-1,1]^d}|p(x)-\widetilde p(x)|\leq\varepsilon. $$ If $A\leq\varepsilon$, take $\widetilde p=0$, which has error at most $\varepsilon$. If $A>\varepsilon$, set $\eta=\varepsilon/(Am)$; then $0<\eta<1/m\leq1/2$. In this case the construction uses at most $$ S=\sum_{\alpha\in I}\max\{|\alpha|-1,0\}\leq sm $$ multiplication blocks, each with size and depth at most $C(1+\log_2(1/\eta))$. In particular, counting the affine summation and allowing scalar paths to be padded to a common depth, the total number of nonzero parameters is bounded by a constant times $$ (sm+s)\bigl(1+\log_2(Am/\varepsilon)\bigr), $$ and the depth by a constant times $m\bigl(1+\log_2(Am/\varepsilon)\bigr)$. The constants do not depend on $d,m,s,A,\varepsilon$.

Proof. If $A\leq\varepsilon$, the zero network has uniform error at most $\varepsilon$, since $\sup_{[-1,1]^d}|p(x)|\leq A$. Suppose henceforth that $A>\varepsilon$, and use the choice

\eta=\frac{\varepsilon}{Am}.

This ensures the hypotheses of the monomial error result for every degree $k\leq m$, and $Am\eta\leq\varepsilon$. Build each monomial with successive multiplier blocks, leaving constants and linear terms exact. For every $\alpha$, its approximation error is at most $\max\{|\alpha|-1,0\}\eta\leq m\eta$; multiplying by its coefficient and adding all terms gives

|p(x)-\widetilde p(x)| \leq\sum_{\alpha\in I}|c_\alpha|m\eta =Am\eta\leq\varepsilon.

There are $S$ multiplication blocks. Each uses at most $C(1+\log_2(1/\eta))$ parameters and layers. The monomial branches can be run in parallel and their outputs combined by an affine map. Padding a scalar output to a common depth can be done with a constant number of ReLU units per added layer, using $t=\sigma(t)-\sigma(-t)$; the resulting padding cost is bounded by a constant times $sm(1+\log_2(1/\eta))$. Finally, in the case $A>\varepsilon$, the chosen $\eta=\varepsilon/(Am)$ gives

1+\log_2(1/\eta) = 1+\log_2(Am/\varepsilon)

Thus the stated complexity bounds follow in the case $A>\varepsilon$. Together with the zero-network case, this proves the theorem. $\square$

The proof also clarifies the role of dimension. If all monomials of total degree at most $m$ are allowed, their number is $\binom{d+m}{m}$. A dense polynomial may therefore require a number of blocks on the order of $m\binom{d+m}{m}$ under this direct construction. A sparse polynomial can be much cheaper: its bound depends on its actual support size $s$, not on the number of possible monomials in $d$ variables. This is a construction bound, not a claim that every polynomial requires this many parameters.

Worked Example: Dimension and Support for a Quadratic

Take $p(x_1,x_2,x_3)=(x_1+x_2+x_3)^2$, on $[-1,1]^3$. Its expansion is

p=\sum_{j=1}^3x_j^2+2x_1x_2+2x_1x_3+2x_2x_3.

There are six monomials: three with coefficient 1 and three with coefficient 2. Thus $s=6$, $m=2$, and $A=3+6=9$. Each degree-two monomial uses one multiplier, so $S=6$. For target error $\varepsilon=0.09$, choose $\eta=\min\{1/2,1/2,0.09/(9\cdot2)\}=0.005$. The weighted sum of monomial errors is at most

(1+1+1+2+2+2)\eta=9(0.005)=0.045\leq0.09.

For comparison, the number of all monomials in three variables of degree at most two is $\binom{3+2}{2}=10$, including the constant and linear terms. This particular polynomial has only six nonzero terms, so the construction uses six multiplications rather than building every possible quadratic monomial.

Interpreting the Bound and Avoiding a Pitfall

The logarithmic dependence on precision arises because each multiplication block can be made more accurate by increasing its depth and size logarithmically. Tightening the polynomial error requirement from $\varepsilon$ to a smaller value increases the multiplier cost through $\log(1/\eta)$. Increasing degree has two effects: a monomial requires more multiplication blocks, and the selected local tolerance must account for the possible accumulation across those blocks. Increasing the coefficient sum $A$ also requires finer local accuracy, since errors in large-coefficient terms are amplified in the final sum.

A common mistake is to count the error of one product block and treat it as the error of the entire polynomial. For a degree-$k$ monomial, the sequential construction has error up to $(k-1)\eta$; after scaling and summing, the polynomial error is bounded using the coefficient magnitudes as well. The tolerance must be chosen before assembling the network to account for both effects.

Another caution concerns the precision expression. The safe general complexity form is proportional to $1+\log_2(1/\eta)$, not simply $\log_2(1/\eta)$ for every possible tolerance. When $\eta$ is restricted to at most $1/2$, the logarithm is bounded away from zero, so the additive constant can be absorbed into a constant factor. Without such a restriction, a zero network can already approximate some small-amplitude targets at relatively coarse tolerances. A nonconstant target alone does not rule out a constant approximator at a specified error level.

Key takeaway: Compose approximate multipliers to build monomials, then sum the scaled monomial networks. On a bounded input domain, the resulting error is controlled by the local multiplication error times the degrees and coefficient magnitudes; the direct size bound is governed by the number of supported monomials and the accuracy required.

Check Your Understanding

Use the construction and error accounting developed above to answer these questions.

How many multiplication blocks does the sequential construction use for a monomial of total degree $k$?
For four factors in $[-1,1]$, what upper bound does the monomial error result give when each multiplication block has error at most $\eta$?
A polynomial has coefficient absolute values summing to $A$, and all its monomials have degree at most $m$. What conservative total error bound follows if every local multiplier has error at most $\eta$?
Why does the count of possible monomials depend on both dimension $d$ and degree $m$, while a sparse-polynomial construction can depend only on its actual support size?
Why is $1+\log_2(1/\eta)$ a safer general complexity expression than $\log_2(1/\eta)$ when no lower restriction on the local tolerance has been imposed?