We develop new approximation and statistical learning theories of convolutional neural networks (CNNs) via the ResNet-type structure where the channel size, filter size, and width are fixed. It is shown that a ResNet-type CNN is a universal approximator and its expression ability is no worse than fully-connected neural networks (FNNs) with a block-sparse structure even if the size of each layer in the CNN is fixed. Our result is general in the sense that we can automatically translate any approximation rate achieved by block-sparse FNNs into that by CNNs. Thanks to the general theory, it is shown that learning on CNNs satisfies optimality in approximation and estimation of several important function classes. As applications, we consider two types of function classes to be estimated: the Barron class and Hölder class. We prove the clipped empirical risk minimization (ERM) estimator can achieve the same rate as FNNs even the channel size, filter size, and width of CNNs are constant with respect to the sample size. This is minimax optimal (up to logarithmic factors) for the Hölder class. Our proof is based on sophisticated evaluations of the covering number of CNNs and the nontrivial parameter rescaling technique to control the Lipschitz constant of CNNs to be constructed.
The paper studies approximation and estimation properties of CNNs with residual blocks in the context
of non-parametric regression, by constructing equivalent fully-connected architectures (with a block-sparse structure),
and leveraging previous approximation results for such functions.
Explicit risk bounds are obtained for regression functions in Barron and Holder classes.
The main contribution of the paper is Theorem 1, which shows that a class of ResNet-type CNNs
contains a class of "block-sparse" fully-connected networks, with appropriate constraints on various size quantities.
This result allows the authors to obtain a general risk bound for the ResNet CNN that minimizes empirical risk
(Theorem 2, which mostly follows Schmidt-Hieber (2017)),
as well as adaptations of the bound for the Barron and Holder classes, by relying on existing approximation results.
The construction of Theorem 1 is interesting, and shows that ResNet CNNs can be quite powerful function approximators,
even with a filter size that is arbitrarily fixed.
However, the obtained CNN approximating architectures look quite unrealistic compared to most practical use-cases of CNNs,
since they specifically try to reproduce a fully-connected architecture, leading to residual blocks of depth ~= D/K,
which is very deep compared to usual CNNs/ResNets (considering, e.g. K=3 and D in the hundreds for images).
In particular, CNNs are typically used when there is some relevant inductive bias such as equivariance
to translations (and invariance with pooling operations) to take advantage of,
so removing this inductive bias by approximating fully-connected architectures seems a bit twisted.
The approach of reducing the function class to be approximated would seem more relevant here,
as in the cited papers Petersen & Voigtlaender (2018) and Yarotsky (2018), and perhaps the results of
the present paper can be useful in such a scenario as well.
Separately, the presentation of the paper could be significantly improved,
for instance by introducing relevant notions more clearly in the introduction and related work sections,
and by providing more insight and discussion of the obtained results in the main paper.
More specific comments:
- Section 1, p.2: define M? define D? M seems to be used for different things in different paragraphs
- Section 2: Explain what is "s" in the Barron class, or at least point to the relevant definition in the paper
- Section 3.1:
  * 'estimation error' is usually called '(expected) risk' in the statistical literature (also in the introduction). estimation error would have to do with relating R and R^hat
  * why is the estimator "regularized"?
- Definition 2: shouldn't it be D_m^(0) = D instead of 1?
- Theorem 1: What is L? Also, it would be helpful to sketch the construction in the main paper given that this is the main result.
- Section 4.2: M_1 is the Lipschitz constant of what function?
- Section 5.1: "M = 1" this is confusing, maybe use a different letter for the ridge expansion? The discussion on 'relative scale' could be made clearer.
- Section 5.2, 'if we carefully look at their proofs': more details on this should be provided.