Step functions #

First, let us start with some definitions. For us, an interval on the real line can be either open, closed, or half-open. A step function \(s : \mathbb{R} \rightarrow \mathbb{R}\) is a function of the form \[s(x) = \sum_i c_i \chi_{I_i}(x) \] where each \(I_i\) is an interval. We assume that each such sum has a finite number of terms. In lab, you found that every step function can be approximated by a dense neural network with one hidden layer. In this exercise you will show how to approximate a certain class of continuous functions using step functions and bound the number of intervals required.

Homework exercise: Suppose that \(f:[0,1] \rightarrow \mathbb{R}\) is Lipschitz continuous with Lipschitz constant \(L\).

• Show that for every \(\epsilon > 0\), there exists a step function \(s : [0,1] \rightarrow \mathbb{R}\) so that \[ \text{sup}_{x \in [0,1]} |f(x) - s(x)| < \epsilon. \] In other words, that the family of step functions is dense in the set of Lipschitz continuous functions on the unit interval.
• Bound the number of intervals required for this approximation in terms of \(\epsilon\) and \(L\).
• What conclusions can you draw about approximations of Lipschitz continuous functions using dense neural networks? In particular, estimate the size of a neural network that will be necessary to approximate a Lipschitz continuous with Lipschitz constant \(L\) to within \(\epsilon\).