Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks

Dear reviewer,

Thank you for taking the time to review the ICLR paper. I would like to address the question you've raised with the following response.

Weakness 1: The lack of a strong comparison with previous works makes it difficult to appreciate the impact of the result. The adaptivity to the data distribution is a well-known property of fully connected networks of any depth (even in the kernel regime), which makes me doubt the necessity of developing a theory of ConvResNeXts. What insights do we get from the analysis that requires using ConvResNeXts?

We are not sure whether the reviewer is referring to the analysis based on the neural tangent kernel. Chen and Xu (2020, arXiv 2009.10683) show that the neural tangent kernel of deep feedforward networks essentially corresponds to a function class induced by the Laplacian kernel. Though the theoretical analysis relies on the eigendecomposition of the corresponding reproducing kernel Hilbert space, which depends on the underlying data distribution, the obtained statistical rates of convergence are not necessarily adaptive to the intrinsic dimension of the Riemannian manifolds considered in this paper, and therefore still suffer from the curse of dimensionality. For example, Bach (2014, arXiv 1412.8690) only proves the adaptivity to the linear subspace, not more general manifolds. Moreover, to estimate Besov functions optimally, it is essential that the method uses a different kernel "bandwidth" parameters for each local neighborhood. This is something that DNNs in the NTK regime are not capable of (more of this in our Answer 2!).

Existing results on neural networks, such as Chen et al. (2021), do show that feedforward networks can adapt to the low dimensional manifolds. However, their results are not applicable to overparameterized neural networks considered in this paper.

A recent paper (Zhang and Wang, 2023) highlights that weight-decay and overparameterized DNNs in parallel blocks can be optimal for Besov functions due to the weight-decay induced sparsity, but it was left as an open problem whether the parallel blocks were crucial. They also did not consider adapting to the manifold. The architectural insight we proved in this paper is that we don't necessarily need parallel blocks when we have residual connections, and that we can exchange Depth $M$ and Width $N$ as long as their product remains the same. To say it differently, while we did not show that the Convolutional layers are essential, we did provide new insight into why "residual connection" and "parallel blocks' ' in ResNeXts are useful in both approximation and generalization.

Weakness 2: I found the definition of Besov spaces too dense and, hence, difficult to understand. Perhaps a few examples would help, as well as a more detailed account of how such spaces generalize Sobolev and Holder spaces, which are known to a wider audience.

Defining the Besov space is essential for illustrating the merits of overparameterized NN over kernels. Kernel ridge regression with any kernel choices was proven to be suboptimal for estimating functions in the Besov class from the work of Donoho, Liu, MacGibbon in 1990. This includes NTKs. As for Sobolev and Holder classes, they are smaller function classes that do not include functions with heterogeneous smoothness. We have included a new Appendix A which illustrates what ``functions with heterogeneous smoothness'' means concretely and clarifies the relationship between Holder, Sobolev and Besov classes. We hope this addresses your concern.

Q1: The brief definition of ConvResNeXts at the end of the second paragraph does not suffice to understand the architecture.

A1: We have introduced the architecture of ConvResNeXts in Section 2.3 and also see Figure 1(b) for illustration. In the updated paper, we have added a pointer to Section 2.3 and Figure 1(b) in the introduction to enhance the accessibility of our ConvResNeXt architecture description.

Q2: Adding a quick definition of Besov spaces when they are first mentioned in the third paragraph would improve readability. In addition, the paragraph explaining besov spaces in the conclusions would benefit from further clarification.

A2: We have added a quick introduction of Besov spaces in the third paragraph of the introduction to improve readability in the updated version. Thanks for the suggestion! Moreover, we have added a detailed comparison among different functional spaces in the appendix due to the space limit. Roughly speaking, the Besov space contains functions with heterogeneous smoothness while Holder and Sobolev classes contain functions with homogeneous smoothness. ConvResNeXts can achieve a near optimal convergence rate for estimating functions in Besov classes, while this is not achievable by kernel methods. This separation does not exist in smaller function classes such as Sobolev and Holders because they are more homogeneously smooth.

Dear reviewer,

Thank you for providing a thoughtful review of our paper. We appreciate your feedback and would like to address the points you have raised in a rebuttal.

Q1: Which of the results in the paper also apply to feedforward networks?

I believe there might be misunderstanding here. Our work focuses on ConvResNexts, which includes the popular ConvResNet as a special example. Our techniques also work for (non-convolutional) ResNets and ResNeXts. However, our results are not directly applicable to feedforward networks without residual connections.

Q2: For the results that apply to feedforward networks, which of them are novel to this work? E.g., has the approximation bound on smooth functions on a manifold been already established for feedforward networks?

Similar results have been established in Chen et. al. (2019) for feedforward networks but without overparameterization or adaptivity to the Besov class. An intermediate result from our theory does apply to overparameterized feedforward networks with residual connections. The decomposition from feedforward networks to convolutional networks enables us to further investigate the depth and width tradeoff in the ConvResNeXts architectures.

The novelty of our theorems is that we consider a more complex model structure, ResNeXt, where there are $N$ residual blocks and each of them has $M$ parallel paths with identity connections. In comparison, existing work only focuses on dense-connected feedforward neural networks. Moreover, our network can be overparameterized by manipulating either a large $M$, a large $N$, or both. This stands in stark contrast to the constraints in Zhang and Wang (2022), where $M$ must be large and $N=1$, and in Liu et al. (2019), where $M=1$ and $N$ must be properly upper bounded. Even though our network is highly overparameterized, we prove that it can efficiently learn the ground-truth function when trained with weight decay. However, classical statistical theories cannot explain this phenomenon due to the huge variance of the neural network class.

In addition, compared to Zhang and Wang (2022), our paper considers the problem where the ground-truth Besov function is supported on a low-dimensional manifold. We develop a close-to-optimal convergence rate which only depends on the intrinsic dimension of the manifold, thus circumventing the curse of the ambient dimensionality.

Q3: In which results is there an actual benefit for using convolutional networks compared to feedforward dense networks?

Convolutional networks (convnets) have long exhibited advantages over feedforward networks, particularly in vision tasks. Our study focused on non-parametric regression and classification with data on a smooth manifold, an abstraction of vision problems where images reside on a "natural image" manifold. Our results show they both ConvResNet, (feedforward) ResNet and whether or not there are parallel blocks as in ResNeXt, they all could work, and one can replace width with depth as long as $MN$ remains sufficiently large. As for whether the convnet is better or worse than the feedforward net, it really depends on which manifold and what kind of functions on the manifold we are estimating.

One important property that helps us prove the convergence rate is the sparsity, which is induced by the block-wise architecture in a ResNeXt. Feedforward neural networks do not have such an architecture, and typically do not have sparsity after training. Because of that, to the best of our knowledge, it has been completely untouched on whether feedforward neural networks without cardinality constraints have the same or better sample efficiency than ResNexts in learning functions in Besov space, not to mention Besov functions on a manifold.

Considering the popularity of ConvResNets, the theoretical study on ConvResNets or ConvResNeXts is quite limited. We are not aware of any existing results on the approximation and statistical theories for such practical networks. Our work attempts to bridge the gap by establishing a close-to-optimal statistical rate of convergence. Though we are not able to show the benefits of ConvResNeXts, our work should still be considered as a substantial contribution, as our setting is very close to real applications in several aspects: Practical architectures with overparameterization, training with weight decay and the data exhibiting low dimensional structures.

Dear reviewer,

Thank you for taking the time to review the ICLR paper and for your positive feedback. I'm grateful for your engagement and would like to address the question you've raised with the following response.

Weakness: Since Theorem 4 depends on finding the global optimizer, I wonder if this is too strong of an assumption.

We concede that some existing work that studies the effect of overparameterization does study the optimization dynamics and prove statistical learning bounds for the solution that optimization algorithms converge to, e.g., those in the NTK regime. We love these works as they actively unroll! On the other hand, none of these techniques thus far are applicable to our problem. Our Appendix A illustrates why it is provably impossible for NTK to be optimal for estimating functions in Besov classes. So in short, we gained something quite nice by giving up on end-to-end analyzing the optimization algorithm and analyzing the regularized ERM. This approach to decouple learning and optimization has its origin in the pioneering work of Vapnik, Bartlett, and many other learning theorists. We essentially made the same choice for the interest of getting a more fine-grained (in our opinion, the correct way to approach overparameterization) learning theory. We hope the reviewer could see the complementary nature of our work and how it pushes along a different direction in the shared goal of understanding deep learning. Finally, we have added empirical studies to illustrate that while finding global optimal solutions may not be tractable, our theory does match the outcome of training ConvResNeXt using SGD (see Appendix B) in mildly overparameterized regime with representation learning --- something that the NTK theory falls short on.

Thanks again for your appreciation, and I trust that this response adequately addresses your query. Should you have any further feedback or questions, please don't hesitate to share them. Your perspective is invaluable to us.

Dear reviewer,

Thank you for your valuable evaluation of our manuscript. We provide responses to your questions and comments in the following.

Weakness 1: The paper does not provide a direct comparison with prior research on different NN architectures and function spaces. It's not clear to me how this work differs from prior ones, and what are the theoretical advantages of your network structure.

Note that we have already compared our results with related works in Section 1. Here we summarize the difference again as follows:

(1) Neural network architecture: In contrast to prior works, exemplified by Zhang and Wang (2022), which predominantly focus on parallel feedforward neural networks, our investigation centers on the intricacies of stacked ConvResNeXts. This architectural choice introduces a significantly more complex nested function form, presenting us with the challenge of addressing novel issues in bounding the metric entropy --- this is one of our major contributions. Specifically, we adopted a more advanced method that leverages the Dudley's chaining of the metric entropy (via critical radius / local Gaussian/Rademacher complexity, Bartlett et al., 2005), which resulted in a tighter bound even for the much simpler setting of Zhang and Wang (2022).

Reference:

P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. Annals of Statistics, 33(4):1497–1537, 2005.

(2) Overparameterization regime: Our network architecture comprises $N$ residual blocks, each containing $M$ paths. Consequently, the network can be overparameterized by manipulating either a large $M$, a large $N$, or both. This stands in stark contrast to the constraints in Zhang and Wang (2022), where $M$ must be large and $N=1$, and in Liu et al. (2021), where $M=1$ and $N$ must be properly upper bounded. Even though our network is highly overparameterized, we prove that it can efficiently learn the ground-truth function when trained with weight decay. However, classical statistical theories cannot explain this phenomenon due to the huge variance of the neural network class.

(3) Manifold setting: Compared to Zhang and Wang (2022), our paper considers the case when the ground-truth Besov function is supported on a low-dimensional manifold and we develop a close-to-optimal convergence rate which only depends on the intrinsic dimension of the manifold, thus circumventing the curse of the ambient dimensionality.

The advantages of ConvResNeXts include that it provides a flexible way to design overparameterized networks where either the number of residual blocks or the number of paths in each block can be large. In addition, the skip-layer connections in ConvResNeXts effectively mitigates the vanishing or exploding gradient issues. Notably, the practical training of ConvResNeXts proves to be more straightforward compared to simpler structures such as FNNs, resulting in outstanding performance across various real-world applications, notably in the domain of image recognition.

Weakness 2: The paper is restricted to binary classification with empirical logistic loss. Are your findings extendable to other losses?

Our findings can be generalized to encompass any loss function that exhibits Lipschitz continuity concerning the model's output, including but not limited to the cross-entropy loss. While our paper predominantly relies on the logistic loss for the sake of clarity and simplicity, the applicability of our results extends to a broader range of loss functions.

Weakness 3: Typo.

Thanks for pointing out the typo. We have corrected it in the latest updated version.

Weakness 4: No numerical experiments are conducted to support the theoretical findings.

We conducted a numerical simulation where we learn a regression function that is supported on the low-dimensional space, and show that ConvResNeXts outperforms other methods with a relatively small model complexity. The results of ConvResNeXts are almost dimension-independent due to the representation learning that helps identify the low-dimensional manifold, while standard non-parametric methods, such as kernel ridge regression and Gaussian processes deteriorate quickly as the ambient dimension gets bigger. We have added the simulation to Appendix B in the updated paper.