Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks

Summary

The authors study the performance of ConvResNets trained with weight decay from the perspective of nonparametric classification. Specifically, the authors consider a smooth target function supported on a low-dimensional manifold, then prove that ConvResNets can adapt to the function smoothness and low-dimensional structures and efficiently learn the function without suffering from the curse of dimensionality.

Strengths

This is an excellent, novel and strong work. The paper provides theoretical guarantees for the ConvResNets in the setting of nonparametric classification. The minimax optimal rate under ConvResNets has been an open problem which was successfully resolved by the authors in the conditional class probability.

Weaknesses

Literature review is not sufficient. Minimax optimal nonparametric classification using DNN has been recently studied by other authors, though the current paper consider another novel neural network, the ConvResNets, which is different from the traditional DNN.

Questions

Nonparametric classification can be done in different frameworks such as (1) smooth decision boundary, (2) smooth conditional class probability or (3) smooth margin. The minimax optimal rates in the above settings are different. For instance, some authors find that DNN classification in (1) and (2) yield different minimax rates. In particular, the minimax optimal rate under (1) is an open problem (see Kim's work) which was recently addressed by Hu et al. The minimax rate under (2) has been recently established for ultrahigh-dimensional case for DNN classification by Wang's work. The minimax rates under (1) and (2) may have different expressions. I guess that this paper considers the setting of smooth conditional class probability, and the manifold dimension D is fixed. It would be great to comment on its extension to ultrahigh-dimensional case as in Wang's work.

Rating

8

Confidence

5

Soundness

4

Presentation

4

Contribution

3

Limitations

NA

Summary

The paper studies the performance of an overparametrized convolutional residual network architecture on a nonparametric classification problem trained with weight decay. This model, known as ConvResNeXt, involves N residual blocks, where each residual block has a parallel architecture of M building blocks, and each building block with L layers. As such it generalizes alternative ConvResNets in the literature and includes them as a special case, e.g., ConvResNet [He et al 2016] when M=1 and aggregated Resnet [Xie et at 2017] when N=1. Specifically, the analysis results consider infinitely many building blocks and shows that weight decay training implicitly enforces sparsity of these blocks considering that the optimal classifier is supported on a low dimensional smooth manifold. As such, they show that this model can efficiently learn the assumed function class without suffering from the curse of dimensionality.

Strengths

1) The paper shows that for learning Besov functions trained with weight decay out of n samples, the rate of convergence depends only on the intrinsic low dimension enabling the curse of dimensionality. 2) They also provide a tighter bound for the weight-decayed ConvResNeXt in computing the critical radius of local Gaussian complexity.

Weaknesses

1) The actual benefit of having parallel paths in the proposed ConvResNeXt model was not addressed fully. Indeed, the results stating that only the product of number of parallel paths M and depth N determines the convergence rate, and one may not need parallel blocks when residual connections are present contradict with some of the earlier findings in the literature. For example, in [Xie et at 2017]. In the mentioned prior work, several experimental results focus on the posive effect of having higher cardinality (more multiple parallel paths) than increased depth and width. 2) If there is no additional benefit of having additional parallel paths, and an equivalent performance can be achieved by increasing the depth only, this will limit the capability of the proposed ConvResNeXt over the ConvResNets unline the claimed benefits of the former.

Questions

1) This new architecture introduce significantly more complex nested function form, but similar performance in both approximation and estimation errors can be achieved by rather simpler one. The provided bounds on the two errors do not suggest any practical benefit of ConvResNeXts over ConvResNets. If so, what would be the motivation to generalize for the former? 2) In Sec 3.2, it was stated that the number of building blocks M does not influence the estimation error as long as it is large enough. This must be contrasted with the earlier findings about the cardinality of the parallel paths, and any difference must be clearly stated. 3) In Sec 3.2, the tradeoff between width and depth was mentioned to be less important in ResNext. In particular, it was stated that the lower bound on the error does not depend on the arrangements of the blocks M and N as long as their product remains same and large enough. One should further address the reason behind this and compare it with the literature again. Moreover, if that’s so, does this suggest that an equivalent model that can achieve equivalent performance without parallel paths?

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

No, authors did not adequately address the limitations of their work, and no potential negative societal impact of their work is identified.

Summary

This paper builds the deep learning theory for studying convolutional residual neural networks with data lying on an embedded lower-dimensional manifold. Theoretical results on both approximation error and estimation error are provided, and interesting implications from the theory are discussed.

Strengths

1. The paper is well-written and I have enjoyed reading it. 2. The theory is well-developed and clear. 3. Good contributions are made to the deep learning theory.

Weaknesses

1. This paper avoids the curse of dimensionality through assuming that the data lies in a low-dimensional manifold embedded in the ambient space. While real world data typically exhibit manifold structure, they commonly don't lie precisely on a manifold, but instead are surrounding a manifold (i.e. + noise). The theory of this paper highly depends on the exact manifold assumption since it needs the associated partition of unity to split the problem into local charts. 2. Among the remarks/implications made on page 7, it is said that overparameterization is fine. However, to my understanding, the problem of overparameterization is not about an overparameterized model not being expressive enough (which this paper addresses), but really about the difficulty in finding a good enough local minimizer for it during optimization. To this regard, Theorem 3.3 based on the global minimizer doesn't really answer it.

Questions

1. The remarks on tradeoff between width and depth are very interesting. Have you tried this in numerical experiments to see if this theoretical driven intuition actually appears in experiments? 2. Other than the analysis being more general, what are the theoretical benefits of adding the identity map (i.e. the residual network) and multiple CNN blocks together compared to just using a CNN block?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See weaknesses and limitations.

Summary

The paper provide theoretical analysis for the good prediction performance of convolutional residual neural networks, even overparameterized.

Strengths

1. The theory they developed with overparamterized ConvResNeXts trained with weight decay is novel. 2. their theory does not suffer from the curse of dimensionality.

Weaknesses

In line 71, 72, the overparameterization is defined as " the number of blocks is larger than the order of the sample size n". Where is this definition comes from?

Questions

1. Can you generalize from the empirical logistic risk to other risks? How will the choice of loss change the bound? 2. Can you explain in details about the extra effort (underlying theoretical techinique) you made in this paper to differentiate from Liu et al. 2021 (Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks)? How do you generalize it to over-parameterized setting and ConvResNeXt?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The analysis is limited to convolutional networks. It's interensting to see if it can be further generalized to other architectures like transformers.

Thanks for responses!

My concerns were well addressed unless some other references in DNN classification are still missing. For instance, I notice the following works are relevant: Minimax optimal deep neural network classifiers under smooth decision boundary Sharp rate of convergence for deep neural network classifiers under the teacher-student setting Deep neural network classifier for multidimensional functional data Minimax optimal high‐dimensional classification using deep neural networks