Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: In this paper the authors have constructed new error bounds for approximating functions in Sobolev and Holder space using deep CNNs. While such bounds have been constructed before, the authors show that there is more flexibility in decreasing these bounds by controlling network depth and filter size in comparison to previous studies. Furthermore, the new error bounds have been shown to depend on the functions’ ambient space dimension polynomially instead of exponentially. In this way the new bounds are much tighter. They also show that if the target function is approximately supported over a lower dimensional manifold, then the tightness of the error bound is further increased phenomenally, thus mitigating the curse of dimensionality and providing faster convergence.
Next, they apply the new approximation error bounds to error analysis of binary classification tasks using deep CNNs. If Y is the target binary label, and f(X) is the function modeled by a deep CNN to estimate Y, the task is to find an appropriate function from the functional space where f(X)  minimizes the expected value of some convex loss function of Y and f(X). As relevant probability distributions over f(X) and Y are unknown  beforehand, an empirical version of the misclassification risk is minimized. The authors show that the difference between the expected misclassification risk and the empirical one is lower bounded by a sum of a stochastic error and an approximation error. They further calculate upper bounds on these two error terms as well.
The stochastic error depends on the complexity of the space of f(X). Sobolev space ensures some degree of smoothness in this case. The approximation error depends on the approximating power of f(X). Furthermore, they show that the bounds on stochastic error don’t require the parameters of the CNN to be uniformly bounded. Earlier studies have enforced such constraints. Thus, the authors’ bounds aid in providing more flexibility over the range of parameter values. Then, the authors show that the bound on approximation error can be further controlled by the controlling overall bound of f(X) itself. The bound for the stochastic error increases with the size and the depth of CNN while that of approximation error decreases.
Finally in their detailed appendix, the authors construct these bounds explicitly for common loss functions for binary classification namely, least squares, hinge, logistic and exponential loss. 

strengths_and_weaknesses: The work is original and provides a  good set of  references 
The authors have provided detailed substantiation of the results  presented in the paper. They have also provided detailed calculations of the relevant bounds for common loss functions used in binary classification tasks.

Quality: The paper appears sound and is clear in stating the objectives and results.
The work is of potential  significance.
The bounds presented apply to a large class of deep CNN’s used for binary classification. 
However, the work is presented only for binary classification tasks, and the authors appear to have overlooked some recent work on exactly the same topic  H. Jiang, Z. Li  and Q. Li and P. Combettes and J.C. Pesquet.



questions: 1. Why did not the authors include more real functional approximation/regress including denoising and such where smoothness issues are front and center  rather than binary function cases?

limitations: As noted in the last rubric, the authors’ derivations depend on binary misclassification risk. However, CNNs may have numerous objectives including multivariate classification and regression tasks. The authors admit these limitations. While deriving bounds for multivariate classifications could be straightforward, it would be far more important  to see  similar tighter bounds  for regression tasks in general.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper shows new error bounds for approximating functions in Sobolev spaces with deep convolutional neural networks. The estimates depend on the dimension of the space in a polynomial way only, and explicitly show the relation to the depth and filter length of the network. By assuming that the domain of the function is well-approximated by a low-dimensional manifold, the authors can improve the error bounds significantly and thus address the curse of dimensionality. This result is exploited for deriving an error bound on the excess risk in classification tasks by separately bounding the stochastic and the approximation error, and subsequently exemplified by making the bound more concrete for the cross-entropy loss. 
strengths_and_weaknesses: Without being an expert on the topic, this appears to be a nice contribution to me. Despite the technical nature of the paper, it is well-written and the authors make their results more accessible to non-experts by clearly defining all mathematical objects (even more standard one like Sobolev spaces). Furthermore, I like the structure of explaining the general bounds first and utilizing/exemplifying them in increasingly concrete applications (excess risk in classification; then cross-entropy in particular + more losses in the appendix). Finally, not assuming a strict manifold structure of the domain, but rather an approximate one is a strength as this assumption is surely more realistic. 

Due to my limited background in the area I cannot judge how novel/significant the contribution is in comparison to prior work. From a practical perspective, I would have liked to see a toy example for some (artificial) problem on which the theoretical function approximation bounds could have been compared to numerical ones in order to get an impression of how tight or loose such estimates are. A second thing I am mostly just wondering about is if the 'approximate low dimensional manifold' assumption and the generic space of Sobolev functions is enough to capture why CNNs work well? The theoretical results in the paper partly say 'yes' (in the sense of the polynomial behavior), but practitioners often argue for CNNs if some (approximate) type of spatial invariance makes sense for the particular application. This could suggest that a much more restricted setting allow to still improve the bounds significantly (which is also the reason why I'd still expect a large gap between the derived theory and many practical applications of CNNs). 

Typos: "choiceof" (without space) in equation (2); "be th number" two lines below (2). 
questions: - Please address whether a toy example for comparing theoretical and practical bounds would be feasible. 
- Please briefly motivate the consideration of Sobolev functions (and/or their remaining gap to common CNN applications). 
limitations: The authors have suitably addressed limitations of their work. I do not think a potential negative societal impact applies for this work.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider deep convolutional neural networks (CNNs) for classification. Their main results include rates of approximating Sobolev smooth functions by CNNs in L_p spaces (Theorems 2.1-2.4 and 4.5), sample error bounds (Theorem 4.2), and estimates for the excess misclassification error of the induced classification algorithm (Theorems 4.6 and 4.7). 
strengths_and_weaknesses: CNNs are the most important family of structured deep neural networks used in practice which are particularly efficient for image classification. Because of the convolutional structure, their analysis is different from that for fully-connected networks. Recently there are some results on CNNs for classification such as those of Kohler et.al. and Feng-Huang-Zhou (Generalization Analysis of CNNs
for Classification on Spheres, IEEE TNNLS, in press). 

What is nice in this paper under review is the treatment of the approximation error when the target function f_0 is unbounded or not Lipschitz. The authors use a truncation operator to estimate the approximation error. 

Another interesting idea of the paper is to consider an almost manifold structure of the input space and to derive learning rates in Theorem 4.7 which depend on the ambient dimension weakly. The authors should comment on the absolute continuity of the marginal distribution with respect to the Lebesgue measure. 

In the proof of Theorem 4.5, the set \{x: |f_{0, T}(x)| \leq T\} is obviously the whole input space, which should be a typo. The author might mean the set \{x: |f_{0}(x)| \leq T\}. Please comment on the Hoelder smoothness of f_0 on this subset. 

The parameter {\mathcal W} defined in Equation (4) should be given a network meaning. Does it stand for the maximum network width?

For the comparison theorem in terms of \psi mentioned on page 6, a simple form valid for almost all loss functions is one with \psi(u)=u^2 given by Chen-Wu-Ying-Zhou (Support vector machine soft margin classifiers: Error analysis, JMLR 5 (2004), 1143–1175). 

The authors have compared their results on approximation error with the existing ones. They should do the same for the excess misclassification error. 

Overall, this is an excellent paper. 
questions: Some questions have been asked in the previous section. 
limitations: Yes, they admit in Assumption 4.3 that they require the loss \phi to be C^1, hence the hinge loss is not included.
review_title: null

Meta-review: metareview: This paper provides an approximation error for Sobolev type functions by using deep CNNs. The approximation error achieves the optimal rate and has adaptivity to the low dimensionality of the support of the input data distribution. They also derive a classification error bound using the approximation error result.   
This paper gives a novel and important theoretical result. Due to the CNN structure, it requires a different techniques from that for FNNs and thus the analysis is not trivial. This gives an important contribution to the literature. Thus, I recommend acceptance for this paper.
confidence: Certain
Decision: Accept