Target-dependent depth-six approximation of Lipschitz functions

By [A1] and [F2], the Countable Choice convention in [F1] holds. Choose the Lipschitz representative on $(0,1)$ and extend it uniquely to $[0,1]$: values along any sequence approaching an endpoint are Cauchy and any two such limits agree by the Lipschitz bound. The continuous representative satisfies $\mathrm{\mid }f\mathrm{\mid }\le 1$ everywhere, since any interior value with modulus greater than $1$ would by continuity violate the almost-everywhere bound on an interval of positive measure. Let $T\ge 1$ be an integer and let $f_1$ linearly interpolate $f$ at $t\mathrm{/}T$, $0\le t\le T$. Then $f_1$ is $1$-Lipschitz, and $f_2=f-f_1$ vanishes at every grid endpoint and is $2$-Lipschitz. Indeed, both summands are $1$-Lipschitz.

Let $m\ge 1$ and let $\mathrm{\Gamma }$ be the set of piecewise-linear functions on the grid $r\mathrm{/}m$, $0\le r\le m$, with endpoint values zero and successive increments in $\{-2\mathrm{/}m,0,2\mathrm{/}m\}$. Thus $\mathrm{\mid }\mathrm{\Gamma }\mathrm{\mid }\le 3^m$. For each coarse interval $I_t=[t\mathrm{/}T,(t+1)\mathrm{/}T)$, rescale $g_t(y)=T{f}_2((t+y)\mathrm{/}T)$. This function is $2$-Lipschitz and vanishes at both endpoints. Quantize each node value down to the nearest multiple of $2\mathrm{/}m$; adjacent quantized values differ by one of the three allowed increments. At a fraction $\theta$ of a grid subinterval, a $2$-Lipschitz function differs from its endpoint chord by at most $4\theta (1-\theta )\mathrm{/}m\le 1\mathrm{/}m$; quantizing both endpoint values changes that chord by at most $2\mathrm{/}m$. Hence some ${\gamma }_t\in \mathrm{\Gamma }$ satisfies ${\sup }_{x\in I_t}\mathrm{\mid }{f}_2(x)-T^{-1}{\gamma }_t(Tx-t)\mathrm{\mid }\le 3\mathrm{/}(Tm)$.

Define the discontinuous selector $\chi (z)=z$ for $0\le z<1$ and $0$ otherwise. For $x\in [0,1)$, exactly the index $t$ with $x\in I_t$ has $\chi (Tx-t)=Tx-t$; all other terms vanish. Therefore ${\tilde{f}}_2(x)=\frac{1}{T}{\sum }_{\gamma \in \mathrm{\Gamma }}\gamma \text{\hspace{0.17em}⁣}({\sum }_{t:{\gamma }_t=\gamma }\chi (Tx-t))$ equals the local interpolant $T^{-1}{\gamma }_t(Tx-t)$ and has error at most $3\mathrm{/}(Tm)$. If $s_{\gamma ,r}$ is the slope of $\gamma$ on $[r\mathrm{/}m,(r+1)\mathrm{/}m]$, then its zero value at $0$ gives $\gamma (z)=s_{\gamma ,0}\rho (z)+{\sum }_{r=1}^{m-1}(s_{\gamma ,r}-s_{\gamma ,r-1})\rho (z-r\mathrm{/}m),0\le z\le 1,$ by matching the initial slope and each slope jump. This uses $m$ ReLU hinges. The cache is a depth-five mixed-gate network with $O(T+m{3}^m)$ units and weights: $T$ selector units, at most $3^m$ grouped sums, $m{3}^m$ ReLU hinge units, and an affine output. For the coarse interpolant, set $s_t=T(f((t+1)\mathrm{/}T)-f(t\mathrm{/}T))$ for $0\le t<T$; then $f_1(x)=f(0)+s_0\rho (x)+{\sum }_{t=1}^{T-1}(s_t-s_{t-1})\rho (x-t\mathrm{/}T)$ on $[0,1]$. This slope-jump identity has $T$ ReLU units and one affine output, so $f_1$ is a depth-three ReLU network of size $O(T)$.

Replace each discontinuous selector by ${\chi }_{\delta }(z)=\rho (z)-{\delta }^{-1}\rho (z-(1-\delta ))+({\delta }^{-1}-1)\rho (z-1)\mathrm{.}$ This continuous piecewise-linear function agrees with $\chi$ on $[0,1-\delta ]$, decreases linearly to zero on $[1-\delta ,1]$, and is zero outside $[0,1]$. Let ${\phi }_{\delta }$ be the piecewise-linear tent that is zero outside $[0,1-\delta ]$, rises from $0$ to $1$ on $[0,\delta ]$, equals $1$ on $[\delta ,1-2\delta ]$, and falls to $0$ on $[1-2\delta ,1-\delta ]$. Its four slope jumps give a representation by at most four ReLU hinges as in step 3.1. Put ${\mathrm{\Phi }}_{\delta }(x)={\sum }_{t=0}^{T-1}{\phi }_{\delta }(Tx-t)$; this comb is a ReLU spline with $O(T)$ units and weights. Replacing the $T$ selectors by three ReLU units each and adding the comb keeps the cache size $O(T+m{3}^m)$ independently of $\delta$.

Let ${\tilde{f}}_{2,\delta }$ be the cache network using ${\chi }_{\delta }$, and set $f_{2,\delta }(x)=\rho ({\tilde{f}}_{2,\delta }(x)+2{\mathrm{\Phi }}_{\delta }(x)-1)-\rho (2{\mathrm{\Phi }}_{\delta }(x)-1)\mathrm{.}$ At most one selector is nonzero at any $x$, its value lies in $[0,1]$, and each rescaled ${\gamma }_t$ vanishes at both endpoints and is $2$-Lipschitz; hence $\mathrm{\mid }{\tilde{f}}_{2,\delta }(x)\mathrm{\mid }\le 1$. On each plateau where ${\mathrm{\Phi }}_{\delta }=1$, the selector is unchanged and the gate outputs the cache. Where ${\mathrm{\Phi }}_{\delta }=0$, the two ReLU terms cancel. On the transition strips $y\in [0,\delta ]$ or $y\in [1-2\delta ,1-\delta ]$ in a coarse coordinate $y=Tx-t$, ${\chi }_{\delta }(y)=\chi (y)$, so the cache equals the continuous piecewise-linear spline ${\tilde{f}}_2$ from step 3.1. For $0\le p\le 1$, the map $a\mapsto \rho (a+2p-1)-\rho (2p-1)$ is $1$-Lipschitz and vanishes at $a=0$, hence its output has modulus at most $\mathrm{\mid }a\mathrm{\mid }$. Every point where $0<{\mathrm{\Phi }}_{\delta }<1$ is within $2\delta \mathrm{/}T$ of a coarse endpoint; both $f_2$ and ${\tilde{f}}_2$ vanish there and are $2$-Lipschitz, so on those strips $\mathrm{\mid }{f}_2-f_{2,\delta }\mathrm{\mid }\le 8\delta \mathrm{/}T$. Where ${\mathrm{\Phi }}_{\delta }=0$, $f_{2,\delta }=0$ and $\mathrm{\mid }{f}_2\mathrm{\mid }\le 4\delta \mathrm{/}T$, which is also within this bound. On plateaus the quantization error is at most $3\mathrm{/}(Tm)$ by step 2.1. Thus $\mathrm{\parallel }{f}_2-f_{2,\delta }{\mathrm{\parallel }}_{\mathrm{\infty }}\le 8\delta \mathrm{/}T+3\mathrm{/}(Tm)\mathrm{.}$ The two final ReLU preactivations absorb the former affine cache output, followed by a shared affine output, so depth increases from five to six; complexity remains $O(T+m{3}^m)$.

Choose $m=\lceil \frac{1}{2}{\log }_3(1\mathrm{/}\epsilon )\rceil$, $T=\lceil 6\mathrm{/}(m\epsilon )\rceil$, and $0<\delta \le \min \{1\mathrm{/}4,\epsilon T\mathrm{/}16\}$. Then both error terms in step 5.1 are at most $\epsilon \mathrm{/}2$, while $T+m{3}^m\le C\mathrm{/}[\epsilon \log (1\mathrm{/}\epsilon )]$: here $T=O(1\mathrm{/}(\epsilon m))$, $3^m=O({\epsilon }^{-1\mathrm{/}2})$, and $m{\epsilon }^{-1\mathrm{/}2}=O(1\mathrm{/}(\epsilon m))$ because ${\epsilon }^{1\mathrm{/}2}(\log (1\mathrm{/}\epsilon ){)}^2$ is bounded on $(0,1\mathrm{/}2)$. The sum $f_1+f_{2,\delta }$ is the required ReLU approximation.