The only way I can think of doing this is to use a method similar to back propagation.
A traditional FFNN has L layers where each layer will have a set of input responses $a^{(l)} = \{a^{(l)}_1, a^{(l)}_2, \dots, a^{(l)}_n\}$ and a matrix of weights $W^{(l)}$ where $W^{(l)}_{jk}$ represents the weight connecting the j-th node from the previous layer to the i-th node of the current layer. There are also activation functions $f^{(l)}(z^{(l)}_k)$ where $z^{(l)}_k = [W^{(l)}_{1k}a^{(l)}_1, W^{(l)}_{2k}a^{(l)}_2, \dots, W^{(l)}_{nk}a^{(l)}_n]$ that are applied to every node in every layer. What you are looking for is the gradient of the activation function of the output layer $\nabla{f}^{(L)}$ (in this case just one node) with respect to the input of the first layer. Using the chain rule,
$$
\nabla (f^{(l)}(z^{(l)}_k)) = \nabla f^{(l)}(z^{(l)}_k)\nabla z^{(l)}_k \\
= \nabla f^{(l)}(z^{(l)}_k) \cdot \sum_j W_{jk}\nabla(f^{(l - 1)}(z^{(l - 1)}_j))
$$
Using this equation you can calculate the gradient in terms of the input space through a process similar to back propagation where instead of propagating the gradient of the loss function, you are propagating the gradient of the activation function.
$\nabla f^{(l)}$ can be calculated analytically from the activation function. $z^{(l)}_k$ should already be calculated during the forward pass. By propagating backwards you will eventually calculate $\nabla_{a^{(1)}} f^{(L)}$
I'm not sure how to convert this for Stochastic Gradient Descent as there is no data set to sample from. Using regular gradient descent will likely get stuck on local optima. You could potentially use gradient descent as a local search method in a broader search policy such as basin hopping. Honestly, it may just be better to use black box optimization methods (e.g. Simulated Annealing, Genetic Algorithms, Particle Swarm Optimization, etc) instead of gradient-based methods.
Since you mention the universal approximation theorem, I think that the explanation that you are looking for is one in the framework of approximation theory. In that regard, there are many works, and I will list a couple of them below, that show that deep networks allow for a more efficient approximation than shallow networks.
Let me recall a couple of results and a suitable framework below and, at the end, I also address polynomial and Fourier approximation.
1. Approximation theory of feed-forward networks
To understand this better, we need to give a complexity measure to neural networks. Recall that a feed-forward neural network is a function of the form
$$
\Phi(x) = T_L(\rho(T_{L-1}(\rho(\dots \rho(T_1(x)))))),
$$
where $\rho:\mathbb{R} \to \mathbb{R} $ is the so-called activation function, which we apply coordinate-wise here. The maps $T_\ell: \mathbf{R}^{N_{\ell-1}} \to \mathbf{R}^{N_\ell}$ are affine linear maps, $N_{\ell-1} \in \mathbb{N}$, for all $\ell \in \{1, \dots, L+1\}$, and $L$ is the number of layers. Here $\Phi$ is a map from $N_0$ to $N_L$. In this notation, the number $N_{\ell}$ corresponds to the number of neurons in the $\ell$'s layer.
In most works on this topic, people now measure the complexity of a network in one of two ways:
- Count the number of neurons: $N(\Phi) := \sum_{\ell = 1}^L N_\ell$.
- Count the number of parameters: Here, one observes that $T_\ell = A_\ell(\cdot) + b_\ell$ for a matrix $A_\ell$ and a vector $b_\ell$. A way to measure the complexity of the full network is using the number of nonzero entries of both $A_\ell$ and $b_\ell$: $W(\Phi) := \sum_{\ell = 1}^L \|A_\ell\|_0 + \|b_\ell\|_0$. Here $\|.\|_0$ denotes the number of nonzero entries of a matrix/vector.
We have now associated a complexity measure to every network. This means we can ask a more nuanced question than the one of the universal approximation theorem.
Neural network approximation theory:
Let $f \in L^\infty(\mathbb R^d)$ and $\epsilon>0$, does there exist a network $\Phi$ with $L$ layers such that
$$
\|f-\Phi\|_\infty \leq \epsilon,
$$
and how large do $N(\Phi), W(\Phi)$ need to be?
2. Power of depth
The beautiful thing about the question above is that for types of functions $f$ if $L$ is allowed to be large, then for the same accuracy $\epsilon$ the numbers of neurons/parameters, $N(\Phi), W(\Phi)$, can be significantly smaller than if $L$ is small. Let me list a number of results in this direction. This list is certainly not complete.
In all of these papers, some functions are identified which, when approximated with shallow networks, need much higher $N(\Phi), W(\Phi)$ than when deep networks are used.
Now there are other advantages of deep networks over shallow networks from an approximation point of view, such as, that shallow networks do not allow for something that people call localized approximation. But I do not want to go into detail on this.
3. Convolutional networks
Let me also make a second point. You ask "Why do deep networks work so well?". Another answer to this question is that they don't. Deep feed-forward networks do not work at all. In virtually every application people use convolutional neural networks. You could, of course, try to approach this problem from an approximation theoretical perspective again. I know of three works that explain the power of depth for CNNs:
- On the Expressive Power of Deep Learning: A Tensor Analysis
- Equivalence of approximation by convolutional neural networks and fully-connected networks
- Benefits of depth in neural networks:
The first two works consider quite specific CNN architectures but highlight that deep CNNs yield better approximation rates for some functions than shallow networks. (In the second paper this is not explicit, but it says that every approximation rate from feed-forward networks translates to a similar one for convolutional networks and vice versa. So the aforementioned results for feedforward networks carry over.) The third result does not restrict the architecture, but only shows that for some very specific functions deep convolutional networks are better approximators than shallow ones.
Here a lot more work needs to be done especially relating to understanding the role of pooling.
There are other aspects of deep convolutional networks that potentially make them work well such as, that they introduce invariances which makes them good classifiers. Since this is not approximation theoretical I shall not go into detail here but I want to mention Mallat's original work on this: Understanding Deep Convolutional Networks.
4. Comparison to polynomials and Fourier series
You also asked for a comparison to polynomial approximation or Fourier approximation. The approximation spaces of these function classes are well known, and one can simply check for which types of functions deep networks yield better approximation rates.
One point is that both polynomials and Fourier series are terrible at approximating functions with discontinuities. For example, in Optimal approximation of piecewise smooth functions using deep ReLU neural networks it was shown that deep networks approximate piecewise n-times differentiable functions essentially as well as n-times differentiable functions. The second point is, that deep networks are very efficient at representing polynomials as famously shown for ReLU networks in Error bounds for approximations with deep ReLU networks. Clearly, if each polynomial can be well approximated, then also sums of polynomials can be approximated, so the approximation rates carry over. Similarly, Approximation properties of a multilayered feedforward artificial neural network shows that certain neural networks are at least as good as a polynomial approximation. As for Fourier approximation Deep Neural Network Approximation Theory has some results on how to reapproximate sinusoidal functions.
Many other works show that DNNs are in fact optimal in approximating certain function classes in a certain framework, e.g. Optimal Approximation with Sparsely Connected Deep Neural Networks but also Error bounds for approximations with deep ReLU networks. In this case, they are of course at least as good as polynomials or Fourier series.
In essence, deep networks are in almost all approximation tasks as good as polynomials/Fourier series and in some tasks they are way better.
Best Answer
There cannot be such a function because $\phi(\cos(2\pi-x))=\phi(\cos x)$ while $\sin(2\pi-x)=-\sin x$.