Approximating Oscillatory Functions With Deep Networks

Why Oscillation Challenges Approximation

A function can be smooth and still be difficult to approximate with a small network. For example, \(f_k(x)=\sin(2\pi kx)\) on \([0,1]\) has derivatives of every order, but its number of oscillations grows with the positive integer frequency \(k\). Uniform approximation must capture those oscillations across the whole interval; matching the function at a few points is not enough.

Network size alone does not determine how well a function can be approximated. The way a target is structured matters too. A shallow ReLU network is piecewise affine and gains at most one additional linear region per hidden unit in one dimension. A deep network can compose simple maps to create many regions. That capacity gives a striking advantage for some deliberately structured alternating targets, but it does not by itself imply an equally small network for every high-frequency sine wave.

A Lower Bound From Alternating Values

The basic obstruction is visible without differentiating the network. If target values alternate above and below a fixed level, a sufficiently accurate approximation must cross that level between each consecutive pair. A one-dimensional piecewise-affine function with \(S\) affine intervals can make at most \(S\) such crossings. For a shallow ReLU network, \(S\leq m+1\), because each of its \(m\) hidden units can introduce at most one breakpoint.

Proof. At each \(x_i\), the strict error bound implies that \(g(x_i)-c\) has the same sign as \(f(x_i)-c\). Those signs alternate. By continuity, on each of the \(r-1\) disjoint open intervals \((x_i,x_{i+1})\), \(g-c\) has a zero. A piecewise-affine function with \(S\) affine intervals cannot have more than \(S\) such distinct crossings: on each interval where it is affine, it has at most one zero unless it is identically zero, and an interval on which it is identically zero cannot connect sample points with nonzero values of opposite signs. Thus \(S\geq r-1\). Since a width-\(m\) shallow network has at most \(m+1\) affine intervals, \(m+1\geq r-1\). \(\square\)

The bound depends on the error tolerance as well as on frequency: the argument applies when the error is below the amplitude of the alternating values relative to the crossing level. It is a useful lower bound for fixed accuracy, but does not describe the full dependence of the required width on an arbitrarily small tolerance.

A Uniform-Error Upper Bound for Sine

A direct upper bound comes from linearly interpolating the target on a fine grid. For a twice continuously differentiable function with \(|f''(x)|\leq M\), interpolation over an interval of length \(h\) has error at most \(Mh^2/8\). The next result establishes this bound and connects it to shallow ReLU size.

Proof. Consider one grid interval \([a,b]\) of length \(h=1/N\), and let \(p\) be the linear function agreeing with \(f\) at \(a\) and \(b\). Put \(e=f-p\), so \(e(a)=e(b)=0\). For an interior point \(x\), set \(C=e(x)/((x-a)(x-b))\) and \(q(t)=e(t)-C(t-a)(t-b)\). Then \(q(a)=q(x)=q(b)=0\). Applying Rolle’s theorem twice gives a point \(\xi\in(a,b)\) for which \(q''(\xi)=0\). Since \(p''=0\), this implies \(C=e''(\xi)/2=f''(\xi)/2\). Therefore \(|e(x)|\leq (M/2)(x-a)(b-x)\leq Mh^2/8\). The bound also holds at the endpoints, where the error is zero. Applying it on every grid interval proves the uniform error claim.

To see the representation claim, let the grid knots be \(t_i=i/N\), and let \(s_i\) be the slope of the interpolant on \([t_i,t_{i+1}]\), for \(i=0,\ldots,N-1\). Its slope changes by \(s_i-s_{i-1}\) at \(t_i\). Hence the interpolant is \(I_Nf(x)=f(0)+s_0x+\sum_{i=1}^{N-1}(s_i-s_{i-1})\max\{0,x-t_i\}\). This uses \(N-1\) ReLU units and represents every segment, including the first, exactly. \(\square\)

For \(f_k(x)=\sin(2\pi kx)\), the second derivative is \(-(2\pi k)^2\sin(2\pi kx)\), so \(M=(2\pi k)^2\). The interpolation result gives \(\|f_k-I_Nf_k\|_\infty\leq (2\pi k)^2/(8N^2)\). Thus choosing \(N\geq \pi k/\sqrt{2\varepsilon}\) guarantees error at most \(\varepsilon\), and this particular construction uses at most \(N-1\) hidden units. The frequency dependence is explicit: finer oscillations require a finer grid for the same interpolation guarantee.

Depth Can Exploit Alternating Structure

A different comparison uses an exactly compositional target. Define the tent map on \([0,1]\) by \(T(x)=2x\) for \(0\leq x\leq1/2\), and \(T(x)=2-2x\) for \(1/2\leq x\leq1\). Let \(g_L=T^{\circ L}\) denote \(L\) repeated compositions of \(T\). Each composition doubles the number of linear pieces, while the map remains in \([0,1]\).

Proof. On \([0,1]\), \(T(x)=2\max\{0,x\}-4\max\{0,x-1/2\}\). A layer can therefore form the two ReLU values \(\max\{0,x\}\) and \(\max\{0,x-1/2\}\), and an affine output combines them to produce \(T(x)\). Repeating this two-unit computation \(L\) times represents \(T^{\circ L}\) with depth \(L\) and width at most \(2\).

The map \(T\) consists of two linear branches, each mapping its half-interval onto \([0,1]\). Inductively, each branch of \(T^{\circ L}\) is divided into two branches at the next composition, so there are \(2^L\) affine intervals. Equivalently, \(T^{\circ L}(j/2^L)=0\) for even \(j\) and \(1\) for odd \(j\); this follows by induction from the two branches of \(T\). These grid values alternate. If a network approximates \(g_L\) with error less than \(1/2\), its values at the grid points lie below \(1/2\) at the zeros and above \(1/2\) at the ones. There are \(2^L\) consecutive pairs with opposite sides of \(1/2\). The alternating-values argument requires at least \(2^L\) affine intervals, so \(m+1\geq2^L\), or \(m\geq2^L-1\). \(\square\)

What the Comparison Does—and Does Not—Say

For sine waves, the alternating-extrema argument gives a shallow width lower bound proportional to \(k\) at error below \(1\), while interpolation gives a shallow construction whose sufficient width is proportional to \(k/\sqrt{\varepsilon}\). These bounds show how fixed-accuracy approximation must respond to increasing frequency and how the smoothness-based interpolation guarantee responds to tighter tolerance. They do not establish a logarithmic-size deep approximation to a general high-frequency sine wave.

For the iterated tent target, by contrast, the target itself is built by repeatedly applying one simple map. A deep network reproduces that compositional structure with size proportional to \(L\), even though the number of alternating affine pieces is \(2^L\). This is a genuine depth advantage for that target. A large number of linear regions is a capacity statement, not a universal guarantee of accurate approximation: the regions must be arranged with the right values and slopes for the target at hand.