Understanding the Approximation Gap of Neural Networks

Thanks for your feedback! Please see the following responses:

Weaknesses:

1. A direct implication of non-compactness is that the global minimum may not exist, which then poses challenge to obtaining a good approximation numerically. The approximation gap is, even if a neural network is capable of approximating a function very well, we still have no way to realize a good representation via any usable techniques. The sigmoid neuron example in the Introduction is a simple illustration of this.

2. The results in our paper are not isolated; instead, they are correlated in a way that forms a chain leading to the approximation gap of neural networks. In Section 3, we provided a different perspective on the universal approximation theorem, emphasizing that the approximation power of neural networks is closely related to the non-compactness of their image sets, as demonstrated in Section 4. As a consequence, the global minimum may not exist due to such non-compactness. However, someone might argue that even if the global minimum does not exist, we can still achieve arbitrarily small error by employing very large weights. In Section 5, we demonstrate that it is impossible due to the machine precision and exponential decay of gradient. We also demonstrated that this issue cannot be simply resolved by increasing the depth alone, and we provide numerical examples to support this assertion.

3. We agree that the application of neural nets in scientific computing is not as popular as in CV and NLP, though there have been numerous works on it. In fact, we are skeptical about whether neural networks can match the performance achieved by classical methods in traditional fields. As you suggested, approximating a discontinuous function using continuous NN is hard is not surprising and we theoretically provide a lower bound for the attainable error in this paper. However, classical methods have already proved their strength in handling those problems, and the question we want to address is whether people continue pursuing this direction, given the fundamental limitations that hinder neural networks from working as well as traditional methods.

And the questions:

1. Actually, there are numerous potential factors that can lead to a failure, such as incorrect loss function, poor initialization, wrong step size in gradient descent, etc.. Learning-based methods sometimes more or less yield a solution to the PDE, while at other times, they fail and generate garbage. Therefore, it is very difficult to locate the cause directly. Instead, our claim is that even if they provided a relatively reasonable solution, the absolute error between their solution and the true solution is still above certain threshold as demonstrated in our paper. Therefore, our result can be understood in the way that there is a gap for neural networks in solving PDEs, resulting in significantly higher errors compared to classical methods.

2. They are related in the way that for many PDEs in fluid mechanics, the level sets are highly disconnected and increasing the depth alone cannot resolve this issue.

3. The issue is that the global minimum is usually attained at infinity when the target function is discontinuous, leading to numerical difficulties. When the target function is sufficiently smooth, however, there is still no guarantee that the global minimum exists due to the non-compactness of image set. In the work "Characterizing possible failure modes in physics-informed neural networks" by Krishnapriyan et al., the absolute errors are still of order $\mathcal{O}(\sqrt{\Delta x})$ even if the solution is smooth.

Thanks for your review. Regarding the specific question you raised on Theorem 3.1 (Universal Approximation Theorem), indeed it has been proposed decades ago as you suggested. However, the original derivation was rather in a formal manner using functional analysis/Fourier transform. In this paper, we derived it using step functions that are in the closure of the image set $Im(f)$, which further implies that the best approximation may not be achieved by any finite parameters. The main contribution of our work is demonstrating the non-compactness of the image set $Im(f)$ and elaborating how it is attributed to the practical approximation gap.

Regarding $S_K(N)$, the symbol $N$ stands for the dimension of the parameter space $\mathbb{R}^N$, not the set of integers.

Thanks for your detailed comments. Regarding your questions, please see the following items:

1. It is a good question. Aside from the Gibbs phenomenon, there is also a famous example called "Runge's phenomenon" in polynomial interpolation so we agree that some classical methods may have trouble as well when approximating discontinuous functions. However, for traditional schemes, those issues can be easily handled by using different set of basis functions. In particular, the Gibbs phenomenon can be eliminated by replacing Fourier series with Fejer kernel, and the Runge's phenomenon can be ameliorated by switching to Bernstein polynomials. However, there is no such measure for neural networks, as all of them suffer from the non-existence of global minima as we demonstrated, regardless of their size and activation function.

2. Actually, the example we showed in Introduction is just to help the audience to quickly grasp the idea. As suggested by reviewer oTBq, we could begin with a non-trivial example of parabolic PDE whose solution can be well-approximated by spectral methods because of their exponential convergence property in the function space. In contrast, achieving the same accuracy using neural networks is not possible due to the non-existence of global minima. However, we doubt if it is really fine for a paper to begin with such complicated discussions.

3. It can be understood in two ways: first, it should note that though machine precision is everywhere, it becomes a serious matter when the target function is not smooth. In fact, the error bound is derived when the norm of the gradient decays exponentially as weights approach infinity since the global minimum does not exist. Therefore, if the target function is sufficiently smooth so that there is a global minimum, weights do not need to approach infinity to attain it, thereby mitigating the effect of machine precision. Second, making $\Delta x$ finer directly incurs the curse of dimensionality, as the number of sample nodes grows exponentially with the dimension. One main claimed advantage of using neural networks over traditional methods is their capability of approximating functions with fewer data points, and our results provide a negative answer to it.

   In particular, in Section 6, we solved the PDE using spectral method and neural network on the same grid, and result in different accuracy. This suggests that neural networks are more sensitive to the discretization error than classical methods.

4. Similar results were reported in works that are cited in our paper, such as Liang (2016) and Elbrächter (2019). In fact, this question is close to the next question on the approximation power of neural nets. In all those papers including the one you suggested, their claims are addressed through a carefully-designed example in which we happen to know the global minimum of approximation. However, having a low infimum does not justify the approximation power, as there is no concrete algorithm to reach it. Our training results on the Cantor set and Ackley function serve as such evidence.

5. In this paper, we aim to show that the approximation power involves two aspects: the capability to represent a target function and the difficulty of realizing that representation. Although the Universal Approximation Theorem states that neural networks satisfy the first part, and we showed that it is sometimes impossible to realize a good approximation due to the non-compactness of image set. In contrast, classical methods do not face the challenge of difficult realization, as they often have closed-form expressions for the best approximation (see Appendix B), and hence there is no need to find the global minimum through gradient-based algorithms. The situation that optimization algorithms never reach it due to complications arising from non-convexity itself, as you suggested, is itself a limitation of neural network approximation.

   Just one more thing we want to mention, it is totally acceptable that neural networks are unable to converge towards global minima in applications of CV or NLP where on classical methods can handle. However, we should be very cautious when applying neural networks to scientific computing where classical methods have already exhibited and proved their full strength. The question we try to address is whether people should continue to use neural networks in a field where they are plagued by various issues that seldom affect traditional methods.

Thanks for the review. Please see the following responses to your concerns:

1. The connection between theoretical results and their practical implications is that, given the non-compactness of the image set, no good approximation may be achieved due to the non-existence of global minima. Consider the approximation problem $\min_{f \in S} \| f - g \|_2$ for some $g \in L^2(D)$ and $S \subset L^2(D)$. It is clear that there always exists $f^*$ when $S$ is compact. Indeed, such a best approximation $f^*$ may not exist when $S$ is not compact. All neural network training algorithms are gradient-based, which are expected to converge towards the global minimum. However, the global minimum itself may not even exist due to that non-compactness, then how much can we trust the results they yield?

2. In principle, finite machine precision can occur anywhere as we use machines, though it becomes more significant in certain cases than in others. In this paper, the error bound is derived when the norm of the gradient decays exponentially as weights approach infinity. In other words, if the global minimum exists, the weights do not necessarily need to approach infinity to attain it, thereby mitigating the effect of machine precision.

3. In fact, the results in our paper collaborate to form a fundamental claim regarding the approximation gap of neural networks: first, we show that the universal approximation power is somewhat due to the non-compactness of its non-compact set; second, we take a topological perspective to show that the compactness is indeed a fundamental distinction between neural networks and classical methods; third, one important implication of the non-compactness is the non-existence of global minima in certain cases, especially when the target function is not smooth enough; fourth, the approximation error is directly affected by the machine precision when global min does not exist; finally, we also showed that this issue cannot be resolved by simply increasing the depth alone.

4. Regarding the presentation, although numerous works attempting to solve PDEs using neural networks have been proposed, it would still be too difficult for those who are not familiar with the topic. We believe that providing an example with a single sigmoid neuron can help a larger audience quickly grasp the idea.