Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper investigates the theoretical properties of deep feed-forward neural networks (FNN) with ReLU activation function when the target function belongs to a Sobolev space defined over the $d$-dimensional unit sphere with smoothness index $r>0$. The bounds for both approximation error and excess risk are derived for two different regimes as $d\rightarrow\infty$, which explicitly depend on the data dimension $d$ as follows

1. In the regime where $r=O(1)$: at most $d^d$ active parameters to get the approximation rate of $d^{-C}$ with $C>0$ being a constant; Moreover, the excess risk bound has a $d^d$ factor

2. In the regime where $r=O(d)$: at most $d^2$ active parameters to get the approximation rate of $d^{-d^{\beta}}$ with $0<\beta<1$; Moreover, the excess risk bound has a $d^{O(1)}$ factor

The authors make comparisons to the case where the input space is d-dimensional cubes and highlight the novelty of their results.
strength_and_weaknesses: $\textbf{Strength}$

1. To my best knowledge this is a novel contribution that broadens the understanding of deep ReLU FNN for approximating Sobolev functions defined on the high-dimensional sphere ($d\rightarrow\infty$), a topic of great interest to the ICLR community

2. The paper explicitly describes the dependence of the approximation error and excess risk on the data dimension $d$, which shows that the curse of dimensionality may be avoided when $r=O(d)$.

3. Excess risk bounds are derived through the lens of pseudo-dimension, which removes the boundedness requirement of the weight parameters in the literature, e.g., Schmidt-Hieber (2020).

4. A different phenomenon is observed compared to the case for $d$-dimensional cubes, which is interesting and novel.

$\textbf{Concerns}$

1. Can the results or analysis be extended to other neural networks, e.g. convolutional neural networks?

2. Will it make any difference if we consider the regime $r=O(d^\alpha)$ for some $0<\alpha<1$?

Minor typos:

1. In Table 1, 4th row & 3rd column, should $O(d^2)$ be $O(d^d)$?
clarity,_quality,_novelty_and_reproducibility: The paper is well-written with a sufficient literature review. The theoretical analysis is neat and well-presented. The results are novel, significant, and of great interest.
summary_of_the_review: The paper presents novel results on how the approximation rate (excess risk) of deep ReLU FNN depends on the data dimension when the input space is a high-dimensional sphere, which provides new insights into the approximation analysis of deep neural networks and will be of great interest to the community of deep learning theory. The intuition is clearly explained and the theorems are technically sound.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the approximation of functions using neural networks with ReLU activations. They showed that, for the functions defined on some Sobolev spaces over the d-dimensional unit, there exists a fast approximation error rate of $d^{-d^\beta}$ by some neural networks, which is very sharp. Also, the construction of the suggested neural networks is given.
strength_and_weaknesses: The main results in this paper will certainly help us have a better understating of the approximation of deep neural networks from a theoretical way. The techniques in this paper may be extended to more general architectures.
clarity,_quality,_novelty_and_reproducibility: Clarity: This paper is clearly written and well organized. I find it easy to follow.

Quality: This paper is technically sound.

Novelty: I think the results in this paper are significant, as explained above. 
summary_of_the_review: In summary, I think the contribution of this paper is enough and this paper is suitable for ICLR, as explained above.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper concerns the approximation power of ReLU FNNs for Sobolev (or actually Hölder) smooth functions defined on spheres. This paper constructs ReLU FNNs with certain architectures to obtain their approximation results. The main idea is to leverage approximation capability of the homogeneous harmonic polynomials on spheres. The obtained results are mainly compared with those in Schmidt-Hieber (2020), which nevertheless concerns the ReLU FNN approximation on functions defined on $d$-cubes. By comparison, it is claimed that their approximation results can alleviate the dependence of network size (number of total parameters) on dimension $d$ to achieve similar approximation error bounds in Schmidt-Hieber (2020). In addition, the paper has also discussed on the approximation results when the smoothness of the target function $r$ varies w.r.t $d$.
strength_and_weaknesses: Strength:
1.In general, the paper is well organized with a clear presentation.
2.The paper derived new approximate results for Sobolev functions defined on spheres in the sense of tracking the explicit dependency on $d$ in the constant factor compared to existing ones. 
3.The paper talked about the results when the smoothness $r$ varies with respect to dimension $d$.

Weakness
1.The obtained estimation error rate does not achieve the expected optimal minimax rate.  Regarding to the comparison in Table 1, it looks a bit weird for me since sphere $\mathcal{S}^{d-1}$ is a subset of the cube $[0,1]^d$, but the estimation rate on a subset 
Is even slower. Is there a way to fix it? Or is there a reasonable explanation?

2.Regarding to the main result in Theorem 3.1, the approximation error has basically dependence $d^{N+d} \times N^{d}/\sqrt{M}$. This result seems also cursed by $d$ in numerator, otherwise one has to set a very large $M$, e.g. $M=d^d$ to get a good approximation accuracy. Please explain more on this.

3.The condition $r=O(d)$ is restrictive. The author may explain more on this condition, especially it’s better to give an example on in what scenarios the condition $r=O(d)$ holds. In addition, I wonder if the condition $r=O(d)$ can be plugged in other existing results, e.g., Schmidt-Hieber (2020) to have a comparison with the obtained results in these $d, r$ varying cases. If it’s not possible, please also explain why $r=O(d)$ can not directly be plugged in other results.

4.The comparison can be fairer since Schmidt-Hieber (2020) focus on the approximation on hyper-cubes instead of sphere. The authors can compare their results with Fang et al. (2020) and Feng et al. (2021) since a large part of the proof follows that of Fang et al. (2020). The most notable difference between Fang et al. (2020) and this paper is that this paper track the explicit dependence of the constant factor on $d$. In addition, though Fang et al. (2020) and Feng et al. (2021) considered CNN approximations, Zhou, D.X. (2020). has shown that any CNN can be equivalently computed by a FNN with parameters at most 8 times larger than that of CNN. In light of this, the author should compare their results with Fang et al. (2020) and Feng et al. (2021).

5.Within the studies of ReLU FNN approximation, the author can also compare with more recent results which have already improved the results in Schmidt-Hieber (2020). For example, Shen, Yang, and Zhang. (2020) and Lu, Shen, Yang, and Zhang. (2021) have already demonstrated the clear dependence on dimension $d$ for ReLU approximation results. In line with these works, Jiao, Shen, Lin and Huang (2021) has also shown the explicit dependence of ReLU approximation results on $d$ as well as obtained polynomial dependence results.

Minor comment:
1.For reference, the issues about the dependence on dimension $d$ was also discussed in Ghorbani et al. (2020).
2.The obtained approximation results are for Sobolev function space $W^r_\infty$, which is actually Hölder function space. This is also mentioned in Appendix A.

Reference

SCHMIDT-HIEBER, J. (2020). Nonparametric regression using deep neural networks with ReLU activation function(with discussion). Ann. Statist. 48 1875–1897.

Ding-Xuan Zhou. Theory of deep convolutional neural networks: Downsampling. Neural Networks,
124:319–327, 2020.

SHEN, Z., YANG, H. and ZHANG, S. (2020). Deep network approximation characterized by number of neurons.
Commun. Comput. Phys. 28 1768–1811.

LU, J., SHEN, Z., YANG, H. and ZHANG, S. (2021). Deep network approximation for smooth functions. SIAM
Journal on Mathematical Analysis 53 5465–5506.

Jiao, Y., Shen, G., Lin, Y., & Huang, J. (2021). Deep nonparametric regression on approximately low-dimensional manifolds. arXiv preprint arXiv:2104.06708.

GHORBANI, B., MEI, S., MISIAKIEWICZ, T. and MONTANARI, A. (2020). Discussion of: “Nonparametric regression using deep neural networks with ReLU activation function”. Ann. Statist. 48 1898–1901.
clarity,_quality,_novelty_and_reproducibility: Clarity: The presentation is clear.
Quality: Fair.
Novelty: Fair.
Reproducibility: N.A.
summary_of_the_review: In general, the paper is well organized with a clear presentation. This paper concerns the approximation power of ReLU FNNs for Hölder smooth functions defined on spheres. This paper constructs ReLU FNNs with certain architectures to obtain their approximation results, while a large part of the proof follows that of Fang et al. (2020). The most notable difference between Fang et al. (2020) and this paper is that this paper track the explicit dependence of the constant factor on $d$. Besides, several major questions raised in “Weakness” part need to be addressed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the approximation of Sobolev functions over the high-dimensional spheres, using deep fully connected neural networks. It develops bounds on the width and depth required for accurate approximation, and on the number of active parameters. These bounds have three interesting features compared to previous work. First, they explicitly track all dependencies on the dimension d. Second, it shows that for extremely smooth functions (Sobolev parameter r ~ d), we can have rates which are polynomial in dimension d. Third, it contrasts these rates with analogous results for the Sobolev functions over the cube (including upper and lower bounds) and shows that this phenomenon does not arise over the cube. Proofs go through an expansion of the target function in spherical harmonics, which can then be approximated individually by subnetworks. The paper upper bounds the risk associated with the best approximating network; the approach differs from corresponding results on the cube, in that it does not require the weights of the approximating network to be bounded. 

Reviewers found that the paper makes a solid contribution to the understanding of the approximation capabilities of ReLU networks, in particular clarifying dimension dependencies (which are critical for high-dimensional data) and illustrating an interesting contrast with learning over the cube. 
justification_for_why_not_higher_score: The paper makes a solid contribution to the understanding of approximation properties of ReLU networks, and identifying an intriguing phenomenon. The broad approach follows an existing line of argument (through harmonic polynomials), but clarifies the dependence on dimension. 
justification_for_why_not_lower_score: The paper advances our understanding of approximation properties of neural networks, clarifying dimension dependencies (which are important for high-dimensional problems), identifying highly smooth regimes where high-dimensional learning is possible, and identifying intriguing contrasts with learning over the cube.
Decision: Accept: poster