Optimal Neural Network Approximation for High-Dimensional Continuous Functions

• The construction of the universal approximator only has a theoretical meaning. While this is the case for many UAT results, the particular construction in this paper is based on extending a continuous function on a Cantor set to the interval $[0,1]$. This can never be done stably in practice, which impairs the significance of the paper to the ICLR community.
• The work is very incremental. It is a straightforward assembly of Yarotsky's result and Shen's result. It is not made clear in the paper what is the originality of this particular work. While the paper contains in-text proofs, some of the proofs are not self-contained and are hard to interpret without referring to Shen's result.
• The sharpness part of the paper (section 3) is questionable. In particular, if I understood correctly, then it is shown that for a single-layer NN, we need at least a width of $d$ to do universal approximation. However, as far as I understood, the UAT result (Theorem 3) is for multi-layer NNs. Hence, sharpness is actually not shown. In particular, in a single-layer case, the statement made in section 3 is almost obvious, because the possible level sets of such a NN form a subspace of dimension $< d$, which cannot be used to do universal approximation.
• The activation functions used in the UAT are not standard in the deep learning society.
• The paper has not been carefully proofread by the author(s). The statements of the theorems are not always clear, and there are a lot of typos. To name a few:
  • The definition of $f$ in section 1.4 does not make sense without variables $x_1, \ldots, x_d$ on the right-hand side.
  • In the second paragraph of section 2, the uniform norm is not properly denoted and the family $\mathcal{A}$ is not in math mode.
  • In the third paragraph of section 3, most of all standard activation functions is not a standard expression.
  • In the statement of Theorem 2, it is unclear what $N_1$ and $N_2$ are without referring to the paragraph before. Then, in the proof, it is said that It will be enough for us to prove that for any $\epsilon > 0$ there exist functions $N_1, N_2$. The functions $N_1$ and $N_2$ are prescribed and used in the statement of Theorem 2. Why should you find those functions in your proof?
  • In Theorem 3, it is unclear what is the quantifier on with a combination of super expressive activation functions and EUAF. Do you prefix a set of possible activation functions or it depends on the function you will approximate? Can they be used arbitrarily in the NN you construct, or do you have to use a certain activation function for a specific neuron?
  • In Theorem 4, it is never mentioned what the activation functions are.
  • Therefore is misspelled on page 5. The condition $d = 2$ is not in math mode in the proof of Theorem 4. In the same paragraph, $g$ a continuous needs to be corrected. The word ''cannot'' should not be spelled as ''can not.''

Although the bound $O(d)$ is optimal and the construction on achieving $O(d)$ neurons is given, I found that the setting of activation functions is artificial in some sense. For example, in the main Theorem 3, the authors require a combination of super-expressive activation functions and EUAF, which makes the DNN not very practical. It would be interesting to derive the results for one fixed activation function and for more architectures used in practice.

• There is significant room for improvement in the organization and writing of the paper.
• Only a part of the claim in Theorem 4 is proved. Specifically, for general $d$, the proof is only given to the case of the form $\sum_i \sin(x_i)$.
• I have a question about the proof of Theorem 4, as I have a counterexample for it. Let $d=2$, $w_{11} = w_{12} = w$, and $F_1 = F_2 = \sin$. Then, the solution of the system $[w_{11} w_{12}][x_1 x_2]^\top = 0$ is $(x, -x)$. However, when we have $\sin(x) - \sin(x) = 0$.

• It seems that the theorems are obtained by combining previously obtained results by Shen et al., and Yarotsky, and there are not many innovations. Per se, this is not necessarily bad, but combined with the other weaknesses, it makes this paper much less appealing.
• Is a minimum $d$ width not trivial? If we only have access to $k<d$ ridge functions $\sigma (\< w_k , x \>)$, then the neural network only depend son a $k$-dimensional projection of the data and none of section 3 seems to be necessary.
• The problem is very niche, and seems to be a purely mathematical curiosity rather than anything relevant for practice. Non-standard activations and small width neural networks are hard to train. Hence, I wonder how much the ICLR community will enjoy that paper.
• The paper seems to have been written in a rush. There are many typos, either in the text or in the equations. The introduction, discussions and related work are poorly written and very hard to follow. A lot of statements are imprecise, which makes understanding the motivations, difficulties and achievements hard to parse for someone that is not already well aware with this literature. Overall the paper is extremely difficult to read because of all these points. I encourage the authors to dedicate a lot of time improving the writing and clarity of the text, possibly with the help of a writing assistant software.