Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the approximation and estimation errors of using neural networks (NNs) to fit functions on infinite-dimensional inputs that admit smoothness constraints. The authors first prove upper bounds on the approximation errors achieved by fully-connected neural networks (FNNs) that rely on certain smoothness measures of the target function, then derive more explicit bounds for using (1D diluted) convolutional neural networks (CNNs) to fit target functions that has smoothness with polynomial order increase, and finally extended the smoothness assumption to a form of sparsity constraint.
main_review: I appreciate the rigor of the theoretical framework but admit that I have not been able to check the proofs, and therefore will comment at a heuristic level below. The notations are a bit heavy, and I would suggest that the authors consider reducing the notations in the main text, adding more discussions on comparing the error rates obtained in the different settings and by the different works, adding more intuitions for the proofs and assumptions, as well as perhaps adding a pictorial illustration of the dilated CNN model. Otherwise it can be difficult to grasp the gist of the theoretical results. 

I am mainly curious about the implication of the assumption that the function has higher smoothness toward coordinates with larger indices (up to rearranging the indices). As the authors point out, this holds if the input corresponds to the Fourier coefficients and the target function is less sensitive to the higher-frequency components. However, this is not how we typically think about CNNs for image classification, where the convolutions are applied to the spatial domain rather than the frequency domain. Therefore, while the proposed model is interesting, I am not quite sure how helpful the theoretical guarantees for this scenario is for our understanding of FNNs or CNNs in actual applications. For example, I am not sure that the claim "our theoretical analysis supports the great practical success of convolutional networks" in the abstract is sufficiently convincing.

The claims that CNNs are able to “automatically extract the required index I(T, $\gamma$)” (on page 8) and “find the important indices that are relatively non-smooth compared with other indices” (on page 9) are intriguing, and I wonder if the authors could provide some further intuitive explanations behind these statements as well as about why dilation is important heuristically.

Some possible typos:
1) Page 5 top, "be back" -> "be dated back"
2) In Definition 4, if $W'$ is a number, what do ${W'}^{L'-1}, ..., {W'}^{l-1}$ mean? 
3) Page 6 before Remark 5, "an dilated" -> "a dilated"
4) Page 7 before Theorem 9, "sufficiently smoothness" -> "sufficiently smooth"
5) Page 9 in Theorem 9, "there exits" -> "there exists"
6) Page 8 before Section 5.3, "As fro" -> "As for"
7) Page 9 before Section 6, "learning rates" -> "error rates" ?
summary_of_the_review: This paper provides an interesting theoretical analysis on the ability of FNNs and (a type of) CNNs to fit functions on infinite-dimensional inputs that are smooth in certain senses, though how the results may relate to the actual usage of neural networks is not completely obvious in my opinion.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proves novel dimension-independent bounds for both approximation and estimation by convolutional neural networks when the input is infinite-dimensional and the target function has mixed and anisotropic smoothness. Moreover, the authors show the advantages of dilated convolution when the smoothness of the target function has a sparse structure.
main_review: The paper investigated the approximation error and estimation error of convolutional neural networks in the function spaces with mixed smoothness and anisotropic smoothness. It was shown that the convergence rates are determined by the smoothness of the target functions and independent of input dimension under mild conditions, which theoretically supports the practical success of convolutional neural networks and provides insights on how to avoid the curse of dimensionality by deep learning methods. These results are novel and of interest. I have some minor concerns as follows.

1. Are the obtained rates also minimax optimal when $1\leq p<2$?

2. Is it possible to extend the theoretical results (Theorems 9 and 10) to the case when $L'$ depends on $T$ and $L_1$ (or $L_2$) is fixed?

summary_of_the_review: Overall, the paper is well-written and technically sound. The results should be of great interest to the theoretical deep learning community.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies non-parametric regression for functions defined on infinite-dimensional input data (such as signals in $\ell^2$), using fully-connected networks or dilated convolutional networks (in the CNN case, convolutional layers are followed by a fully-connected network).
The authors consider certain smoothness classes similar to mixed or anisotropic smoothness but extended to infinite-dimensional input data, which requires per-coordinate smoothness orders ($a_i$ in Definition 2) that are non-decreasing or increasing with some rate.
For such classes, the authors obtain rates that only depend on $a_1$ for the mixed smoothness case, or $\sum_i a_i^{-1}$ for the anisotropic case, for the ERM under certain classes of FNNs or CNNs. Notably, CNNs avoid the need to selecting specific finite subsets of variables as inputs (needed by FNNs), and dilated CNNs additionally allow some adaptivity to sparsity in the $a_i$, in particular, by avoiding dependence on the specific order of the $a_i$ (the growth condition is on the sorted values instead of the unsorted ones for the non-dilated case with a single convolutional layer).
main_review: I find the paper very interesting and novel, in that it explores adaptivity of convolutional architectures to useful smoothness structure in the target, providing dimension-independent rates which may hold even for infinite-dimensional signals.
I am thus in favor of acceptance. Nevertheless, the paper is quite dense with notation, and I believe the clarity and presentation of the paper could be significantly improved:

* the definition of gamma-smoothness was a bit hard to digest, and would benefit from more intuition, perhaps relating to penalizing derivatives, if appropriate.

* the motivation about being more/less sensitive to high vs low frequencies in an image could be discussed further. In particular, the authors suggest that the $x_i$ for large $i$ could correspond to higher frequencies, but in practice these probably just correspond do different spatial locations of pixels. In this sense, the final result showing adaptivity to different orderings of $a_i$ for dilated CNNs is much more compelling than the previous ones.

* more comments on the requirements for the network architectures would be helpful, since they are quite heavy to read in the current presentation. For instance, it would be helpful to mention in the beginning of section 5.2 that the CNNs only use *one* convolutional layer here. In Definition 4, it would be helpful to make a remark that you're choosing h = W', and why.

* generally, more intuition on the results and their proofs, particularly why CNNs enable the adaptivity they do, would be helpful. More discussions after the main theorems, e.g. on limitations of FNNs and benefits of CNNs, would be welcome as well.

A question: would using strided convolutions (with stride = filter size) instead of dilated convolutions also allow for similar adaptivity?

Minor remarks:
- Table 1: what is meant by $d \ll n$? do such rates only hold asymptotically?
- Table 1: notation-wise, using $\tilde a$ to denote its inverse would perhaps make more sense?
- Section C.1 contains a "Comment: Needs more precise references"
summary_of_the_review: A good paper tackling an interesting question, namely studying adaptivity of convolutional architectures to certain function spaces.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors consider approximation and learning by deep neural networks in the setting with an infinite dimensional input space. They provide nice rates for approximating and learning functions with mixed or anisotropic smoothness. The networks studied in the paper include fully connected ReLU networks and those generated by linear convolutional layers followed by a fully connected layer. 
main_review: The setting with an infinite dimensional input space is a very interesting topic and is closely related to distribution regression. The rates of approximation and estimation for least squares regression by deep ReLU neural networks given in the paper are nice contributions to the theoretical study of deep learning. I recommend the paper to be accepted. 

The authors might discuss the following issues:

1. It would help the readers if the authors can point out the connection between the topic discussed in the paper and distribution regression. Though the setting with an infinite dimensional input space is valuable for describing some learning problems, it would improve the usage of the results if the implementation of deep neural networks in this setting could be discussed. 

2. For CNNs, the authors propose only linear maps for the convolutional layers without activation and argue in Remark 5 that their analysis can be applied straightforwardly when ReLU is used. This is arguable and the authors might give more details. To my opinion, the rates of approximation and learning in the paper are derived mainly by using the last fully connected layer. 

3. A theory for approximation and learning by 1-D CNNs with vector input spaces has been developed recently. The authors should mention some of the existing results in this development. 


summary_of_the_review: The setting with an infinite dimensional input space is very interesting. The rates of approximation and estimation by deep ReLU neural networks given in the paper are nice.
review_title: null

Meta-review: This work studies the approximation and estimation errors of using neural networks (NNs) to fit functions on infinite-dimensional inputs that admit smoothness constraints. By considering a certain notion of anisotropic smoothness, the authors show that convolutional neural networks avoid the curse of dimensionality. 
 
Reviewers all agreed that this is a strong submission, tackling a core question in the mathematics of DL, namely developing functional spaces that are compatible with efficient learning in high-dimensional structured data. The AC thus recommends acceptance.
Decision: Accept (Spotlight)