Sparse Network Representations For Approximation

What Sparsity Measures

An architecture specifies how many parameters a network could use; a representation specifies which of those parameters it actually uses. This distinction matters for approximation: two networks may have the same width and depth but very different numbers of nonzero weights and biases. A sparse approximation bound controls the latter, not merely the dimensions of the architecture.

We develop a concrete bound using ReLU networks and linear spline interpolation. The construction is exact for the interpolating spline, and its approximation error for a smooth target can be bounded explicitly. The resulting theorem applies to univariate functions and, by combining coordinate-wise constructions, to additive functions. It is not a general rate for every smooth multivariate function.

For a width-\(W\) network of this form, the ambient count is \(3W+1\): \(W\) input weights, \(W\) hidden-layer biases, \(W\) output weights, and one output bias. A zero parameter is still an architectural slot, but it does not contribute to sparsity. Thus, saying that a network has width \(W\) does not by itself say that its representation uses \(W\) nonzero units or parameters.

From Smoothness to a Sparse Spline

Take \(f:[0,1]\to\mathbb{R}\) with two continuous derivatives. Divide the interval into \(m\) equal subintervals, with knots \(x_j=j/m\) for \(j=0,\ldots,m\). Let \(I_m f\) be the continuous function that agrees with \(f\) at every knot and is linear between consecutive knots. Write \(s_j=m\{f(x_{j+1})-f(x_j)\}\) for the slope on subinterval \([x_j,x_{j+1}]\).

The change in slope at knot \(x_j\) is \(s_j-s_{j-1}\). Adding a ReLU hinge at each interior knot creates exactly this slope change: \((x-x_j)_+\) is zero to the left of the knot and has slope one to its right. Consequently, the spline has the representation

On this domain, \(x=\sigma(x)\), so the initial linear term is also a ReLU unit. This representation uses at most \(m\) hidden units: one for the initial linear term and \(m-1\) for the interior knots. Each hinge unit has an input weight, a bias, and an output weight; the initial unit has an input weight and an output weight. Including the output bias, the number of nonzero parameters is at most \(3m+1\). Some coefficients may be zero, so this is an upper bound.

Proof. The ReLU formula follows by matching values and slopes. At \(x=0\), the formula equals \(f(0)\). On the first subinterval its slope is \(s_0\). At knot \(x_j\), the hinge with that knot increases the slope by \(s_j-s_{j-1}\); after the change, the slope is \(s_j\). Induction over the intervals shows that the formula has the same initial value and interval slopes as the interpolating spline, so it equals \(I_m f\).

For the error, consider one subinterval \([a,b]\) of length \(h=1/m\), and let \(q\) be the linear interpolant there. The function \(r=f-q\) vanishes at \(a\) and \(b\). For \(x\in(a,b)\), set \(C=r(x)/\{(x-a)(x-b)\}\) and define \(w(t)=r(t)-C(t-a)(t-b)\). Then \(w(a)=w(x)=w(b)=0\). Rolle’s theorem applied twice gives a point \(\xi\in(a,b)\) with \(w''(\xi)=0\). Since \(q''=0\), this implies \(f''(\xi)-2C=0\), and hence \[ |f(x)-q(x)|=\frac{|f''(\xi)|}{2}|(x-a)(x-b)| \leq \frac{M}{2}\frac{h^2}{4} =\frac{M}{8m^2}. \] The same bound holds at the endpoints, where the error is zero. Taking the maximum over all subintervals proves the stated uniform error bound. \(\square\)

A Sparse Bound for Additive Smooth Functions

The same construction gives a multivariate bound when the target is additive across coordinates. This is a useful setting in which smoothness and sparsity can both be made explicit without requiring a network to build interactions between inputs.

Proof. Apply the univariate spline construction with \(m\) subintervals to each \(g_j\). For coordinate \(j\), the initial linear term uses a ReLU unit whose input weight is nonzero only for coordinate \(j\); each interior hinge also depends only on \(x_j\). Put all these units in one hidden layer and sum their outputs. Add \(c+\sum_{j=1}^d g_j(0)\) as the output bias. There are \(dm\) units in total. Each has at most one nonzero input weight and one nonzero output weight; each of the \(d(m-1)\) hinge units may also have a nonzero bias. Including the output bias gives at most \(2dm+d(m-1)+1\leq3dm+1\) nonzero parameters.

Write \(I_m g_j\) for the interpolant of \(g_j\). At any \(x\in[0,1]^d\), the error is bounded by the triangle inequality and the univariate theorem:

This bound holds for every \(x\), so it also holds for the supremum over the domain. If \(M_\Sigma>0\), choosing \(m=\lceil\sqrt{M_\Sigma/(8\varepsilon)}\rceil\) makes the error at most \(\varepsilon\); if \(M_\Sigma=0\), each component is affine and the construction is exact for \(m=1\). \(\square\)

Interpreting the Bound

For the additive class, the construction gives a transparent relation between three quantities: curvature, approximation error, and parameter sparsity. Increasing \(m\) reduces the error at order \(m^{-2}\) for twice-differentiable components, while the number of nonzero parameters grows at most linearly in \(dm\). The architecture can be made wider than the construction requires, but that does not improve the stated approximation unless the additional units are used.

This is a constructive upper bound, not a claim that every smooth multivariate function has the same rate or that the parameter count is optimal. The additive assumption is essential to the multivariate result proved here. More general approximation theorems use different constructions and assumptions.

Common Pitfall: Counting Slots Instead of Nonzeros

A common mistake is to see a width-\(W\) network and conclude that the represented function needs \(W\) active units, or to report the full parameter count as its sparsity. The correction is to count the nonzero scalar weights and biases in the particular representation. Conversely, a small nonzero count alone does not guarantee a useful approximation: the error bound also depends on the target’s smoothness and on the chosen grid size.

Sparsity is also not the same as coefficient size. A representation may contain a nonzero weight that is extremely small; it still counts as nonzero under the definition used here. Any threshold-based notion of approximate sparsity requires a separate threshold and an accompanying error analysis. The explicit spline bounds avoid that ambiguity by counting exact zeros and bounding approximation error directly.