Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivatives

Summary

The paper proposed a method to estimate the Vapnik-Chervonenkis (VC) dimension and pseudo-dimension of deep neural network (DNN) derivatives with the ReLU activation function, which have important applications such as characterizing the generalization error of machine learning methods and establishing the optimal approximation of DNNs in Sobolev spaces. The authors provided theoretical analysis and proofs for their proposed method, which fills a gap in learning error estimations for many physics-informed machine learning models and applications, including solving partial differential equations, operator learning, network compression, and regularization. Another contribution of the paper is the demonstration of how DNNs can be used to approximate functions in Sobolev spaces using ReLU activation functions in a deep feedforward neural network architecture, with a nearly-optimal approximation rate. Overall, the study provides a framework for analyzing and optimizing DNNs for different applications while taking into account mathematical concepts such as VC-dimension and pseudo-dimension.

Strengths

* The topic of the paper is highly relevant to the field of deep learning and offers an interesting approach to estimate VC-dimension and pseudo-dimension of derivatives of deep neural networks. * The paper is well-written and clearly presents the mathematical language and definitions used in the study. The proofs provided are detailed and structured in a logical manner. * The paper presents two important theorems that provide a solution to the approximation rate problem of DNNs in Sobolev spaces and the degree of generalization error in loss functions involving derivatives of DNNs. * The proposed approach has the potential to be applied in different areas of physics-informed machine learning such as solving partial differential equations, operator learning, and generative models.

Weaknesses

- Some aspects of the paper could be clearer and more thoroughly explained. The introduction, for instance, could better demonstrate the main contribution of the paper and provide a more detailed overview of the state-of-the-art and the limitations of existing research. - The section on references could be more comprehensive, covering more related studies and presenting a more thorough overview of the existing literature.

Questions

1. Pseudo dimension is a more general concept than VC dimension, while the bounds in Theorem 1 and Theorem 2 seems similar to each other except two constants $\hat{C}$ and $\overline{C}$, is there any relationship between $\hat{C}$ and $\overline{C}$ ? 2. Are those results in this paper holds only for ReLU networks?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

This paper facilitates the understandings of Sobolev training and performances of DNNs in Sobolev spaces by providing the near optimal VC-dimension and pseudo-dimension of DNN derivatives.

Strengths

Technically, they improve the bounds on VC and pseudo-dimensions of DNN derivatives in reference [10].

Weaknesses

Though I think the theoretical contributions of this paper is great, but in terms of readability of the paper, there are some rooms for the improvements. \\ First, this paper assumes that the readers are very familiar with the notions of Sobolev training. In my opinion, authors should defer some technical proofs in the appendix, and introduce the notion briefly in the main paper, and motivate readers why the Sobolev training is interesting problem to consider. \\ Second, some notations should be introduced first, before being stated. I realized the Sobolev Spaces $W^{n,\infty}([0,1]^{d})$ first appeared in line 59, then introduced in line 114, formally.\\ Third, some sentences are repeated quite often. For instance, line numbers 125-127 are same with line numbers 167-169.

Questions

1. To my knowledge, VC-dimension and Pseudo-dimension are essentially same notion. (Reference [4].) I am wondering why the results in Theorem 1 and Theorem 2 are surprising in a sense that they have the same bound. Is there any intuitive reason on why it is non-trivial to expect they should be same for the DNN derivatives? \\ 2. What is the meaning of approximating functions in $W^{n, \infty}([0,1]^{d})$ with Sobolev norm $W^{1,\infty}([0,1]^{d})$? Why this is interesting? \\ 3. How do we know the bound is optimal? To my knowledge, we commonly refer that we have an optimal bound when we have the matching orders of lower bound and upper bounds. But the author only provides the upper bounds in the paper.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This work has no negative societal impact.

Summary

The authors provide estimates on two measures of statistical complexity, the VC-dimension and the pseudo-dimension, of derivatives of deep neural networks. The estimate of the VC-dimension is shown to be optimal up to logarithmic factors. They also propose a constructive method for approximating functions in Sobolev spaces by deep neural networks. The VC-dimension bound is used to show that the obtained approximation rate is optimal as a function of the width and depth of the network. Finally, they prove a generalization bound in terms of Sobolev norm by leveraging the pseudo-dimension upper bound.

Strengths

The paper is globally well-written and pleasant to read. It brings several new results regarding the statistical and approximation properties of deep neural networks in terms of Sobolev norms, which could be of broad use, in particular in the community of deep learning for PDEs. I like that most of the presented bounds have matching lower bounds. I have not checked the proofs in details, so I cannot provide evidence on their soundness, but the mathematical statements presented in the main paper are easy to understand and unambiguous.

Weaknesses

I do not have any strong reservation, a few questions are list below. The only part of the paper that I found hard to follow is the proof of Theorem 1. I suggest that authors take advantage of the additional page to expand a bit on the proof. Perhaps a drawing would help?

Questions

+ Line 77: you claim that the estimate of the pseudo-dimension is nearly optimal, but I do not see a lower bound in the paper. Could you provide a lower-bound or at least an argument on how to obtain one, or otherwise change the phrasing of this sentence (and similar ones elsewhere in the paper)? + Line 101: I don’t understand the \leq sign. Shouldn’t it be an equal sign? Otherwise, I feel the argument of lines 184-187 breaks down, since \sigma_2 networks include ReLU networks. + Line 129: the dependence of the width on the dimension d is exponential. Is this expected? Do you think that you could get a matching dependence in the lower boud? + Line 224 and Theorem 5: I think it would be clearer to upper bound your generalization error term by 2 sup_{\theta} |\Esp(R_S(\theta)) - R_D(\theta)|. Otherwise it is a bit confusing since, without further clarification, the expectation applies both to the estimator \theta_S and to the random function R_S. Similarly, in the proof of Lemma 12, I don’t think that the proof is correct as it is if you apply it for \theta_S, since \theta_S depends on the random sample. However, it is correct if you write it for any (deterministic) \theta, thereby getting the sup over \theta as in the LHS of Lemma 11, which you can then apply to get the same upper bound that you get with your proof.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

See weaknesses.

Summary

The main contribution of the paper are new VC dimension and pseudo-dimension bounds for derivatives of functions implemented by deep neural networks. The utility of these bounds is demonstrated by proving the tightness of approximation error bounds in the Sobolev norm for networks with ReLU and ReLU squared activations, and by giving an improved generalization bound in a similar setting.

Strengths

**Contribution.** This is a good technical paper that improves state of the art in the theoretical studies of VC/pseudo-dimensions and approximation and generalization rates of DNNs. The focus of the paper is the setting where VC/pseudo-dimensions are estimated for model derivatives, and approximation/generalization is considered with respect to Sobolev norms. This setting is not so well-explored as the more common setting where the fitted functions are assumed to belong to a Sobolev space, but the error of fitting does not involve the derivatives. The main results claimed in the paper are new VC/pseudo-dimensions bounds. The other results are new approximation and generalization bounds. The VC/pseudo-dimension bounds naturally help to obtain the generalization bounds and show the tightness of approximation bounds. It appears that all the results established in the paper improve previous analogous results in terms of giving more accurate/tight rates. **Quality and clarity.** The paper is fairly well written. All the results are precisely stated, sketches of proofs are provided where appropriate (full proofs provided in the appendix), connections between the results are well-explained, previous work is duly mentioned.

Weaknesses

I don't see any major issues in the paper, but my overall impression is that it is fairly technical and lacks significant new insights. Virtually all results in the paper rely very heavily on previous research, and most of them look like being assembled from ideas scattered across many previous publications. I find it hard to name new ideas that never appeared before. I would say that this paper is more suitable for a journal. I think that the claims of achievement in this paper are exaggerated. The main claim is connected with the new VC-dimension bound: "obtaining such bounds for DNN derivatives is much more difficult", "DNN derivatives consist of a series of interdependent parts...rendering existing methods for estimating bounds inapplicable". In fact, the bound for VC-dimension of derivatives given in Theorem 1 is very close to the bound for the original network function given in Theorem 7 of Bartlett et al (2019), and the proof of Theorem 1 is just a slight modification of the proof of Theorem 7 in Bartlett et al (2019). This is not surprising because the chain rule expression (13) for the derivatives of the network function is only slightly more complicated than the original function for the purpose of partitioning the parameter domain into piecewise polynomial components and estimating the degrees of the resulting polynomials, as required for the proof. The authors claim "we propose a method to achieve nearly optimal estimations of the VC-dimension and pseudo-dimension of DNN derivatives", but I don't see here any new method.

Questions

What are the important non-technical takeaways from this paper?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See above

Thank you for your rebuttal.

I have no further questions. I will raise the score to 6.

Thank you

Thank you for your replies, I find them generally reasonable. I still think, however, that it is not quite fair for you to write "*there are similarities between our method and Bartlett et al. [2019] in proving the upper bound of VC-dimension*". In fact, your proof very closely follows the structure and specific elements of the original proof. Your contribution is, indeed, in extending it to the more complex scenario involving derivatives. It might be reasonable to add a comment to the paper explaining in more detail the relation of your proof to the original proof, and the associated challenges. Anyway, I'm increasing my score.