Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proves upper and lower bounds on neural networks for approximating Korobov functions $X^{2, \infty}$. Upper and lower bounds match for approximation in $L^\infty$ norm sense, and the rate is free of the curse of data dimensionality. The scope of network architectures discussed is extensive, including shallow (2-layer) networks, deep networks with ReLU(-like) activation functions and Sigmoidal activation functions.
main_review: The paper is nicely written, and the theoretical results are well explained. I believe the results are correct and sound, albeit I did not check every detail in the proof.

I feel it should be good to discuss whether it is possible to consider higher-order mixed derivatives in Korobov spaces, for example, $X^{3, \infty}$. On the other hand, extending to bounded $L^p$ derivatives with $p < \infty$ can be interesting. Frankly speaking, I think the extension relies on if there are function approximation guarantees similar to Theorem 2.2 in the paper.

Compared to Sobolev spaces, we see the approximation of Korobov functions is free of the curse of data dimensionality. My impression is that there should be some low-dimensional structures in Korobov space allowing the circumvention. The authors explains why Korobov is easier to approximate in Appendix A, while I think some high-level remarks should be placed in Section 2.

The authors may want to discuss more related works on efficient approximation theories of neural networks. There are works considering either structures in function spaces, e.g., Besov functions with dominated mixed smoothness, or structures in data space, e.g., manifold data. These works all demonstrate that the size of neural networks in function approximation does not suffer from the curse of data dimensionality.

=========================================================================

Thanks for authors' detailed response. The generalization to $L_p$ norm guarantees is interesting. I am glad to hold a positive opinion on this paper.


summary_of_the_review: I am positive on the paper, due to its clarity and technical depth. I think the paper can be rated a 7, yet there is no rating between 6 and 8.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the ability of shallow and deep neural networks to approximate Korobov functions, and analyses their representation power in terms of the number of used parameters. The authors first show that 2 layers neural networks using common activation functions can approximate any Korobov function within eps error in infinity norm using O(eps^{-1/2} (log 1/eps)^{3(d-1)/2}) parameters. This result improves the existing upper bound of O(eps^{-d/r}) parameters for approximating Sobolev functions in W^{r,p} using 1-hidden layer neural networks, hence reducing the curse of dimensionality.

For deep neural network, this paper provides a new result, showing that neural networks with depth O(log d) and O(eps^{-1/2} (log 1/eps)^{3(d-1)/2}) approximate Korobov functions in X^{2, infinity} within eps error in L-infinity norm. This improves the result of [1], by requiring a depth independent of the required accuracy. However, the current work requires a C^2 and non-linear activation function, and is hence not applicable to ReLU.

Finally, the authors show that any continuous function approximator for the Korobov space requires O(eps^{-1/2} (log 1/eps)^{(d-1)/2}) parameters for achieving error eps, hence matching the previous upper bound for NNs up to factor (log 1/eps)^{d-1}.

[1] Hadrien Montanelli, Haizhao Yang, and Qiang Du. Deep ReLU networks overcome the curse of dimensionality for bandlimited functions
main_review: I found paper to be very well written and easy to follow. The authors provide simple constructive proofs of the theorems, whose high-level ideas are well explained in the main text.

The discussion about the difference between Korobov and Sobolev spaces (Appendix A) is greatly appreciated. You mentioned there, that functions in Sobolev spaces can have more oscillations in various dimensions, and this can be the reason why they seem to be harder to approximate. It would be interesting to have a similar discussion to compare the Korobov space with the space of bandlimited function, which seem to avoid the curse of dimensionality. In particular, what do we intuitively gain in terms of expression power when extending the space of function from bandlimited functions to Korobov space ?

One question that would be interesting for practical purpose: By increasing the weights of the NN, one can approximate a function with any Korobov norm. In the proposed construction, what is the maximal weight magnitude that is used (in terms of dimension, accuracy and target function's Korobov norm) ? If the weight magnitude is restricted to a certain value, is it possible to design with a modified construction that account for such a constraint, and how does the number of required neurons/parameters would be affected. This question is of interest especially in scenarios where NNs are trained using weight decay or other regularisation.


Minor:
Pages 23-28 contain the formatting instruction which are of minor interest...
P.11 Sobolov
p.17 This proves the bound on the number of neutrons.
summary_of_the_review: This paper is well written, and provides good theoretical insights about the representation power of both shallow and deep neural networks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies what function class can be efficiently approximated by neural networks. This paper focuses on a special function class, namely the Korobov function space $X^{2, \infty}$, which contains function with $L^\infty$ bounded weak $\alpha$-order derivative, where $\| \alpha \|_\infty \le 2$. This is a local constraint on the local smoothness of the function space. This paper shows that shallow (with depth=$2$) and deep neural networks can efficiently approximate $X^{2, \infty}$, and the number of parameters does not scale with $\varepsilon^{-\mathrm{poly}(d)}$, thus efficiently escaping the curse of dimensionality. Furthermore, this paper shows the optimality of their parameters bound by showing a matching lower bound. 
main_review: 
#### Strengths
1. The paper gives matching upper bound and lower bound for the $X^{2, \infty}$ space. 

#### Weakness
1. The space seems far away from the practice of deep learning, and the contribution is mainly theoretical.
    * The bound still has dependency on $(\log \epsilon^{-1})^{O(d)}$, which is still exponential. (Note that $\log \epsilon^{-1}$ is about the number of bits to represent a float point number with $\epsilon$ accuracy.) This makes it less motivated to study this function space.
    * The approximation issue is not the main concern in deep learning theory. Deep neural network merits not only because they are universal function approximators, but also, and more importantly, they can be efficiently trained and can generalize well. The optimization and generalization issues are the main concerns, for which this paper does not provide much insight.
    * This paper looks tangential to the community of ICLR. Maybe this paper is more suitable to venues in applied math or numerical analysis?
2. The technical novelty is rather limited, and the techniques looks to be rather limited to this specific problem of approximating Koborov space.
    * The upper bound construction seems to be based on a simple interpolation argument. It is strange why the previous paper (Montanelli & Du, 2019) did not achieve this bound. Maybe the authors could highlight the main technical challenges?
    * The techniques in this paper seem to be ad-hoc for the Korobov space and do not provide much insight for the 
3. The authors should remove Appendices E-K when finalizing their paper.
summary_of_the_review: 
Because of concerns in the significance and technical novelty in this paper, I would recommend weak reject.

**After Rebuttal:** Thank the authors again for a detailed reply. The authors have addressed my main concerns. I would like to raise my recommendation to weak accept and increase the correctness and novelty scores, and confidence. I suggest the authors to incorporate their answers, especially 1.(a) and 2.(a), in their next revision.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies approximation capabilities of neural networks for the purpose of approximating Korobov functions which are multivariate functions of bounded second mixed derivatives.

The paper presents a complete study for approximating such functions with NNs: they study shallow nets and show that 2 layers with ReLUs and total #neurons of O(1/eps log^{1.5d}(1/eps))  where d is the dimension, can \eps-approximate  Korobov functions. Moreover, by allowing larger depths, close to logd, they can get a better depedence on \eps. Finally, they prove that any continuous function approximator requires a #params close to their upper bound in order to approximation Korobov functions.

This gives a complete picture for how Korobov functions behave wrt to function approximation with shallow or deep nets.


main_review: Strengths:
-in-depth study of Korobov function approximations
-several new ideas/gadgets on how to represent such functions with NNs


Weaknesses:
-unclear presentation in several places: how do the bounds break the curse of dimensionality as stated in bullet point 1? 
-lack of motivation: Korobov functions seem like an interesting object for study, however this falls outside the community's "standard" knowledge, so the reviewer would expect much better explanation for why one should care for these functions in the context of Machine Learning or so. For example, the Conclusion states: "This work therefore contributes to understanding the practical success of neural networks theoretically" --> How is this the conclusion? Are Korobov functions prevalent in practice? The bounds in Th. 4.1 also seem to suggest that increasing depth from 2 to logd only shaves an sqrt{\eps} factor which does not seem so significant, even though the depth increased substantially.


Q: Why do the authors claim that they break the curse of dimensionality (e.g., page 2 bullet point 1?)? There is a strong dependence on d, right? What am I missing?
summary_of_the_review: Except several relatively minor issues with presentation and clarification of the results, the reviewer thinks this paper to be a good paper on the topic of approximating Korobov functions. More work is needed for presentation of the paper, and fixing a few things here and there (see above as well)
review_title: null

Meta-review: The authors theoretically analyze the approximation of Korobov
functions by neural networks, obtaining upper and nearly matching
lower bounds, for shallow and deep networks, with different activation
functions.  The bounds are stronger than what can be proved for the
more commonly studied Sobolev functions.  But Korobov functions are a
natural and fairly wide class of functions.  This work makes a
substantial step forward in clarifying what kind of functions are
especially amenable to representation by neural networks.  The
reviewers also appreciated the clarity of the writing.
Decision: Accept (Poster)