Logarithmic-size ReLU approximation of the square

Let $I_q$ be the linear interpolant of $x^2$ at the dyadic nodes $j{2}^{-q}$. On each interval of $I_{q-1}$, the difference $I_{q-1}-I_q$ is zero at its endpoints and has height $4^{-q}$ at the midpoint. By [F1], ${\tau }^q$ is the unit tent on each such interval, so $I_{q-1}-I_q=4^{-q}{\tau }^q$. Since $I_0(x)=x$, telescoping gives $I_m(x)=x-{\sum }_{q=1}^m{4}^{-q}{\tau }^q(x)$. To implement this with shared computation, set $t_0=x$ and for each $q=1,\dots ,m$ use one hidden layer with $u_q=\rho (2t_{q-1})$ and $v_q=\rho (2t_{q-1}-1)$, then define the affine expression $t_q=u_q-2v_q=\tau (t_{q-1})$. Thus $t_q={\tau }^q(x)$ and the $m$ iterates use only $2m$ hidden units in $m$ sequential layers. The final affine output reads the input and all hidden units, with coefficient $1$ on $x$ and contribution $-4^{-q}{u}_q+2\cdot 4^{-q}{v}_q$ from layer $q$, so it computes $I_m$ with only $O(m+1)$ additional skip connections.

On a dyadic interval $[a,b]$ of length $2^{-m}$, linear interpolation of $x^2$ has error $(x-a)(b-x)$, whose maximum is $(b-a{)}^2\mathrm{/}4=4^{-(m+1)}$. Choose $m$ with $4^{-(m+1)}\le \delta$. Then $I_m$ approximates $x^2$ within $\delta$ and $I_m(0)=0$.

The shared sequential construction in step 1.1 computes all required iterates in $m$ hidden layers, and its affine skip readout computes $I_m$ using $O(m+1)$ weights. The resulting network has $O(m+1)$ units, weights, and depth, and $m\le C^{\mathrm{\prime }}(1+\log (1\mathrm{/}\delta ))$ by the choice of $m$. Taking $Q_{\delta }=I_m$ proves the claim.