ReLU Networks For Multiplication

Why Multiplication Is a Useful Network Building Block

Multiplication is a simple operation for an arithmetic circuit, but it is not a linear operation: a ReLU network is piecewise affine, so it cannot represent $xy$ exactly on a two-dimensional region. It can, however, approximate multiplication uniformly on a bounded input domain. This construction matters because products occur in interaction terms, gated models, and many nonlinear compositions. Here the goal is specific: build a ReLU network for multiplication, quantify its error and size, and control the error when the construction is repeated.

We use $\sigma(t)=\max\{t,0\}$ for the ReLU activation. Network size below means the number of nonzero weights and biases; depth means the number of hidden layers. The constructions use bounded width, so both depth and size grow linearly with the refinement level.

A ReLU Construction for the Square Function

The construction starts with piecewise-linear interpolation of $x^2$ on increasingly fine dyadic grids. A tent map identifies the midpoints where each refinement changes the interpolant.

Definition: On $[0,1]$, define the tent map $$ T(x)=2\sigma(x)-4\sigma\left(x-\frac{1}{2}\right)+2\sigma(x-1). $$ For $s\geq 1$, let $T_s$ be its $s$-fold composition, so $T_1=T$ and $T_s=T\circ T_{s-1}$ for $s\geq 2$. Define $$ I_m(x)=x-\sum_{s=1}^{m}4^{-s}T_s(x),\qquad 0\leq x\leq 1, $$ with $I_0(x)=x$.

On $[0,1]$, $T$ is zero at the endpoints, equals one at $1/2$, and is linear on either side of $1/2$. Each further composition creates a tent on each interval of the preceding dyadic grid. In particular, $T_s$ is zero at $j/2^{s-1}$ and equals one at the midpoint of each interval between consecutive such grid points.

Theorem: For every integer $m\geq 0$, $I_m$ is the linear interpolant of $x^2$ at the grid points $j/2^m$, $j=0,\ldots,2^m$. Consequently, $$ \sup_{0\leq x\leq 1}|I_m(x)-x^2|\leq 4^{-(m+1)}. $$ Moreover, $I_m$ is represented exactly by a ReLU network of depth $O(m)$, bounded width, and $O(m)$ nonzero parameters.

Proof. At level zero the grid consists of 0 and 1, and its linear interpolant is $I_0(x)=x$. Suppose the interpolant at level $s-1$ has been constructed. On each interval of that grid, the new grid adds its midpoint. The tent $T_s$ is zero at the old grid points and one at every new midpoint. The old interval length is $2^{-(s-1)}$. For a quadratic, the old chord exceeds the value at the midpoint by one quarter of the squared interval length, namely $$ \frac{(2^{-(s-1)})^2}{4}=4^{-s}. $$ Thus subtracting $4^{-s}T_s$ leaves the old endpoint values unchanged and sets the midpoint value to the exact square. The result is linear on each half-interval, so it is precisely the interpolant on the refined grid. Induction gives the stated formula and interpolation property.

For the error bound, consider any grid interval $[a,a+h]$, where $h=2^{-m}$. The chord $L$ of $x^2$ on this interval satisfies $$ L(x)-x^2=(x-a)(a+h-x). $$ This nonnegative quadratic is maximized at the midpoint, where its value is $h^2/4=4^{-(m+1)}$. This proves the uniform bound. Finally, $T$ is a linear combination of three ReLU units. Its iterates can be computed successively, while the running sum in $I_m$ and the input are carried through the layers. Signed quantities can be carried using $\sigma(z)-\sigma(-z)=z$. This requires only a fixed number of units per layer and a fixed number of connections per refinement step, giving bounded width, depth $O(m)$, and $O(m)$ nonzero parameters. $\square$

For a bounded interval $[-A,A]$, where $A>0$, define $$ S_{m,A}(z)=A^2 I_m\left(\frac{|z|}{A}\right). $$ The absolute value is exactly representable as $\sigma(z)+\sigma(-z)$. Scaling the square approximation therefore gives $$ \sup_{|z|\leq A}|S_{m,A}(z)-z^2|\leq A^2 4^{-(m+1)}. $$ The network still has depth and size $O(m)$. The parameter $A$ affects its weights and its error bound, but not the order of its size.

From Squaring to Multiplication

The identity $(x+y)^2-(x-y)^2=4xy$ turns a square approximator into a multiplication network. It is important to account for both square errors: one comes from the input $x+y$, and the other from $x-y$.

Theorem: Fix $B>0$ and an integer $m\geq 0$. There is a ReLU network $M_{m,B}$ such that, for all $(x,y)\in[-B,B]^2$, $$ M_{m,B}(x,y)=\frac{S_{m,2B}(x+y)-S_{m,2B}(x-y)}{4}, $$ and $$ \sup_{(x,y)\in[-B,B]^2}|M_{m,B}(x,y)-xy| \leq \frac{B^2}{2}4^{-m}. $$ Its depth and number of nonzero parameters are $O(m)$.

Proof. Since $|x+y|\leq 2B$ and $|x-y|\leq 2B$, each square approximation has error at most $$ (2B)^2 4^{-(m+1)}=B^2 4^{-m}. $$ Write the two errors as $e_+$ and $e_-$, so that $S_{m,2B}(x+y)=(x+y)^2+e_+$ and $S_{m,2B}(x-y)=(x-y)^2+e_-$, with $|e_+|,|e_-|\leq B^2 4^{-m}$. The polarization identity gives $$ M_{m,B}(x,y)-xy=\frac{e_+-e_-}{4}, \qquad |M_{m,B}(x,y)-xy| \leq\frac{|e_+|+|e_-|}{4} \leq\frac{B^2}{2}4^{-m}. $$ The two square networks can be run in parallel and their outputs combined by an affine output layer. Parallel composition and this final combination preserve the claimed $O(m)$ depth and size. $\square$

In particular, to guarantee uniform error at most $\varepsilon>0$, it is enough to choose an integer $m\geq 0$ satisfying $$ \frac{B^2}{2}4^{-m}\leq\varepsilon. $$ When $2\varepsilon<B^2$, one sufficient choice is $m=\left\lceil\log_4\left(B^2/(2\varepsilon)\right)\right\rceil$. Thus the depth and number of nonzero parameters grow on the order of $\log(1/\varepsilon)$ for fixed $B$.

Worked Example: Multiplication on the Unit Square

Suppose $x,y\in[-1,1]$ and the desired uniform error is at most $0.01$. Here $B=1$, so the bound for level $m$ is $\frac12 4^{-m}$. At $m=2$, it is $0.5/16=0.03125$, which is too large. At $m=3$, it is $0.5/64=0.0078125$, which is below $0.01$. The level-three network therefore meets the requested bound, with depth and nonzero parameter count of order three.

For example, take $x=0.75$ and $y=0.5$. Both $x+y=1.25$ and $x-y=0.25$ lie on the level-three square grid after scaling their absolute values to $[0,1]$: $1.25/2=0.625=5/8$, and $0.25/2=0.125=1/8$. At grid points the interpolant equals the square exactly. Hence the network returns $$ \frac{1.25^2-(-0.25)^2}{4} =\frac{1.5625-0.0625}{4} =0.375, $$ which equals $0.75\times0.5$. Exactness at these grid inputs is consistent with, but stronger than, the uniform error guarantee.

Worked Example: Changing the Input Bound

Now suppose $x,y\in[-3,3]$ and the target error is $0.01$. With $B=3$, the bound becomes $\frac{9}{2}4^{-m}$. At $m=4$, this is $4.5/256=0.017578125$, so level four does not certify the target. At $m=5$, the bound is $4.5/1024=0.00439453125$, which does. The construction uses square approximators on $[-6,6]$, because both $x+y$ and $x-y$ lie in that interval. The larger input range changes the number of refinement levels needed, while the network size remains $O(m)$.

Repeated Products and Error Accumulation

The same multiplication module can be composed to approximate a product of several inputs. A useful case is $q$ inputs in $[-1,1]$. The exact running product remains in $[-1,1]$; the approximate running product may drift slightly outside this range. To keep every call within its stated domain, use a module whose inputs lie in $[-2,2]$ and explicitly bound that drift.

Theorem: Let $q\geq 2$ and $0<\varepsilon\leq 1$. There is a ReLU network $P$ such that $$ \sup_{(x_1,\ldots,x_q)\in[-1,1]^q} \left|P(x_1,\ldots,x_q)-\prod_{j=1}^q x_j\right| \leq\varepsilon. $$ One construction uses $q-1$ sequential multiplication modules with bound $B=2$ and level $$ m=\left\lceil\log_4\left(\frac{2(q-1)}{\varepsilon}\right)\right\rceil. $$ Its depth and number of nonzero parameters are $O(qm)$.

Proof. Let $z_1=x_1$, and for $j=2,\ldots,q$, set $z_j=M_{m,2}(z_{j-1},x_j)$. The module error is at most $\delta=2\,4^{-m}$. By the choice of $m$, $\delta\leq\varepsilon/(q-1)$. Let $p_j=\prod_{i=1}^j x_i$ be the exact partial product, and put $e_j=|z_j-p_j|$. Since $|x_j|\leq1$, whenever the module inputs are in $[-2,2]$, $$ e_j\leq |x_j|e_{j-1}+\delta\leq e_{j-1}+\delta. $$ Starting from $e_1=0$, induction yields $e_j\leq(j-1)\delta$. In particular, $|z_j|\leq |p_j|+e_j\leq1+(j-1)\delta\leq1+\varepsilon\leq2$, so every module input is indeed in its required domain. Finally, $e_q\leq(q-1)\delta\leq\varepsilon$. Composing $q-1$ modules gives depth and size $O(qm)$. $\square$

Worked Example: A Product of Four Inputs

Consider $x_1=0.5$, $x_2=0.8$, $x_3=0.25$, and $x_4=1$, and request error at most $0.05$. Here $q=4$, so the prescribed module level is $$ m=\left\lceil\log_4\left(\frac{2(4-1)}{0.05}\right)\right\rceil =\lceil\log_4(120)\rceil=4, $$ since $4^3=64<120\leq256=4^4$. Each multiplication error is at most $\delta=2/256=0.0078125$. The accumulated error is at most $3\delta=0.0234375<0.05$. The exact product is $$ 0.5\times0.8\times0.25\times1=0.1. $$ The approximate partial products stay within the module domain: after $j$ inputs their absolute values are at most $1+(j-1)\delta$, which is at most $1.0234375<2$. Thus the final error guarantee applies at every stage, and the resulting network has depth and size $O(4\times4)$.

Common Pitfall and Practical Interpretation

A common mistake is to say that the error of a product of $q$ inputs is just the error of one multiplication module. Each stage introduces a new error. The recurrence $e_j\leq e_{j-1}+\delta$ shows why a valid general guarantee is $(q-1)\delta$, not $\delta$. There is a second issue: the approximate intermediate value need not remain in the exact product's range. The bound $|z_j|\leq1+(j-1)\delta$ checks that the subsequent module is still being used on its certified domain.

For a fixed input bound, the square-and-polarization construction provides a concrete way to trade network size for uniform accuracy: each additional refinement level reduces the error bound by a factor of four. The repeated-product result makes the dependence on the number of factors explicit as well. These are approximation guarantees, not claims that training will find the constructed weights or that every multiplication-based model needs this particular architecture.

Check Your Understanding

Use the constructions and bounds in this tutorial to answer the following.

What is the uniform error bound for $I_m$ on $[0,1]$, and how does it change when $m$ increases by one?
For inputs in $[-B,B]$, why must the square approximator in the polarization construction cover $[-2B,2B]$?
Using the stated bound, find the smallest level $m$ that certifies error at most $0.02$ for multiplication on $[-2,2]^2$.
For a sequential product of $q$ inputs in $[-1,1]$, explain why the accumulated error bound is proportional to $q-1$.
What additional check is needed to ensure that approximate intermediate products remain within the domain of the multiplication module?