On Rademacher Complexity-based Generalization Bounds for Deep Learning
Deep Learning;CNN;Generalisation Errors
Thank you much for your comments on our paper. The following are our answers to your questions:

1. This paper only considers some specific types of activation functions

Answer:  Although our developed bounds are for any activation functions, but we think that they are only non-vacuous for CNNS with some special classes of activation functions. We believe that achieving non-vacuous bounds is a challenging task in deep neural networks in general. 

2.  The conclusion that the obtained Rademacher complexity does not explicitly depend on the depth of CNNs is not very convincing, since by Equations (30), (31), (34), the Rademacher complexity may exponentially depend on the depth of CNNs if the right-hand-side of (30), and (31) are large than 1. More discussions on this claim should be added.

Answer: In this work, by using Theorem 8 (or Theorem 2), we show that for CNNs or DNNs with some special classes of activation functions (ReLU, Leaky ReLU, PRLI, Sigmoid, and Tanh or odd functions in general), the Rademacher complexity can be upper bounded by
$$
O\bigg(\sqrt{\frac{1}{n}}\prod_{j=1}^L \mu_j M_{\infty} (j) \bigg),
$$ where $M_{\infty} (j)$ is the infinity-norm of the weight matrix of the $j$-the layer, and $\mu_j$ is the Lipschitz constant of the activation in the $j$-the layer. Note that $|\sigma_j(0)|/\sqrt{n}$ is usually very small compared to $\mu_j M_{\infty} (j)$. 

So what we meant here is that under the assumption that the product of norm of weight matrices is bounded, our bound does not depend on the network-length $L$, which is an improvement over Golowich et al.'s bound, especially when for DNNs with big network-length.  We borrowed the term "size-independent" from Golowich et al.'s work to show that meaning. We also note that our results hold for many class of activations, not only limited to ReLU as Golowich et al.'s work. We will add this discussion in our revised version. 

Based on our contributions, we look forward to receiving your better score.
Reply to Reviewer's comments
Next, we provide answers to your questions:

1. About the remark 3: 
The second bullet in remark 3 states that theorem 2 improves the bound for the case $m=1$. However, in Lemma 1 (Talagrand's lemma for $m=1$), the contraction rate is $\mu$, (not $2\mu$).

Answer: The Talagrand's contraction lemma in Lemma 1 is for 
$$
\mathbb{E}_{\epsilon}\bigg[\sup\_{h \in \mathcal{H}} \sum\_{i=1}^n \epsilon\_i (\psi \circ h)(\mathbf{x}_i) \bigg]. 
$$

If the expression inside the bracket is absolute value, i.e., 
$$
\mathbb{E}_{\epsilon}\bigg[\sup\_{h \in \mathcal{H}} \bigg|\sum\_{i=1}^n \epsilon\_i (\psi \circ h)(\mathbf{x}_i)\bigg| \bigg],
$$ 

then it is well-known that (Ledoux & Talagrand, 1991, Theorem 4.12)

$$
\mathbb{E}_{\epsilon}\bigg[\sup\_{h \in \mathcal{H}} \bigg|\sum\_{i=1}^n \epsilon\_i (\psi \circ h)(\mathbf{x}_i)\bigg| \bigg]
$$

$$
\leq 2 \mu \mathbb{E}_{\epsilon}\bigg[\sup\_{h \in \mathcal{H}} \bigg|\sum\_{i=1}^n \epsilon\_i h(\mathbf{x}_i)\bigg| \bigg] \qquad (2).
$$
Hence, our contraction lemma in Theorem 2 improves (2) for many special classes of activation functions (See our Theorem 2) since the contraction rate is only $\mu$. 

2. In Theorem 8, the upper bound $F_L$ of $\mathcal{R}_n(\mathcal{F})$ is defined using the recursive relation (34). Because of $\gamma_i$, $F_L$ seems depending on the depth, unlike the explanation in the remark 9. Could you provide a bit more details?

Answer: In this work, by using Theorem 8 (or Theorem 2), we show that for CNNs or DNNs with some special classes of activation functions (ReLU, Leaky ReLU, PRLI, Sigmoid, and Tanh or odd functions in general), the Rademacher complexity can be upper bounded by
$$
O\bigg(\sqrt{\frac{1}{n}}\prod_{j=1}^L \mu_j M_{\infty} (j) \bigg),
$$ where $M_{\infty} (j)$ is the infinity-norm of the weight matrix of the $j$-the layer, and $\mu_j$ is the Lipschitz constant of the activation in the $j$-the layer. Note that $|\sigma_j(0)|/\sqrt{n}$ is usually very small compared to $\mu_j M_{\infty} (j)$. 

So what we meant here is that under the assumption that the product of norm of weight matrices is bounded, our bound does not depend on the network-length $L$, which is an improvement over Golowich et al.'s bound, especially when for DNNs with big network-length.  We borrowed the term "size-independent" from Golowich et al.'s work to show that meaning. We also note that our results hold for many class of activations, not only limited to ReLU as Golowich et al.'s work. We will add this discussion on your revised version. 

Based on our responses to your questions, we believe that your evaluation of our work is not correct. Our results are significant from both theoretical and practical perspectives. Therefore, we kindly ask the reviewer to be fair in evaluating our contribution.
Reply to Reviewer's comments (next).
Thank you very much for your comments on our paper. 

First, we provide rebuttals to your comments on the weaknesses of our paper.

1. Questionable significance:

Answer: We believe that your comments on the significance of our paper is not correct. There are two reasons:
+ The contraction lemmas in Maurer (2016) and Foster and Rakhlin (2019) are different from our contraction lemma in Theorem 2. It does not have the same form as ours. We note that the contraction lemmas in Maurer (2016) and Foster and Rakhlin (2019) are used for mapping between $\mathbb{R}^m \to \mathbb{R}$. Our contraction lemmas are between $\mathbb{R}^m \to \mathbb{R}^m$. The contraction lemmas in  Maurer (2016) and Foster and Rakhlin (2019) look hard to apply for deep learning since the form of Rademacher complexity is changed after contracting (cf. (1) in Maurer 2016).
+ As the peeling process, by using our Theorem 2 or Lemma 7, our Rademacher upper bound has the following form:
$$
O\bigg(\sqrt{\frac{1}{n}}\prod_{j=1}^L \bigg(\mu_j M_{\infty} (j)+\frac{\sigma_j(0)}{\sqrt{n}} \bigg)=O\bigg(\sqrt{\frac{1}{n}}\prod_{j=1}^L \mu_j M_{\infty} (j) \bigg)  \qquad (1),
$$ 
where $M_{\infty} (j)$ is the infinity-norm of the weight matrix of the $j$-the layer, and $\mu_j$ is the Lipschitz constant of the activation in the $j$-the layer since $|\sigma_j(0)|/\sqrt{n}$ is usually very small compared to $\mu_j M_{\infty} (j)$ for a large number of training examples. However, if we apply contraction lemmas in Maurer (2016) and Foster and Rakhlin (2019) for DNNs with $L$ layers, we may achieve the following upper bound (although we believe that it is hard to apply these lemmas for deep learning as mentioned above)
$$
O\bigg((\sqrt{2})^L \sqrt{\frac{1}{n}}\prod_{j=1}^L \mu_j M_{\infty} (j) \bigg).
$$ This bound is inferior to Golowich et al. and our bounds since the constant term is exponential in $L$ (See a detailed discussion in  Golowich et al. (Size-independent sample complexity of neural networks)). 

2. Non-vacuous bound:

Answer: In this work, we choose the infinity-norm for developing our bound since we believe that this norm can lead to tight bounds (see our experiments). Choosing the right norm is a contribution of our paper. We note that Nagarajan and Kolter (2019) experimented on the bounds provided by Neyshabur et al. (2018) and Bartlett et al. (2017) for ReLU DNNs. However, these bounds are even inferior to Golowich et al.  (2018) (see a detailed discussions in Golowich et. al (Size-independent sample complexity of neural networks)). They also use different norms from ours. 

3. Comparison with other CNN bounds:

Answer: As analysed in Golowich et al. (Size-independent sample complexity of neural networks), Golowich et al.'s bound is the best in term of network depth dependence. Hence, we only compared with Golowich et al.'s results in our paper (See Section 6). Our results are based on our development of a new contraction lemma between vector spaces (Theorem 2), which is different from previous approaches. Based on your suggestions, we will add these notes in our revised version.

4. Clarity Concerns:

Answer: In the main text, we already provided a proof for Theorem 8. The proofs of other lemmas are given in Appendix since they are quite long. As you can see in Appendix, the proof of Theorem 2 are based on many lemmas, hence it requires a lot of spaces even for only stating these lemmas.
Reply to reviewer's comments
Thank you very much for your comments on our paper. 

First, we answer your comments question by question:
1. Lemma 1: $\boldsymbol{\epsilon}$ is not defined. 

Answer: We think that the readers can understand what is $\boldsymbol{\epsilon}$ from the context. However, based on your concern, we will define $\boldsymbol{\epsilon}=(\epsilon_1,\epsilon_2,\cdots,\epsilon_n)$ in our revised version. 

2. The definition of network length should be provided at the beginning of the paper. It actually refers to the number of layers in Section 6. It would be better to adopt the conventional name "network depth".

Answer: We mentioned about $L$ in Section 3.1 when we first introduced CNN. We will mention that $L$ is called "network-length" in Section 3.1 in the revised version as your suggestion.

3. What is the benefit of the bound that does not depends on the network length? It could not reflect the effects of depth in deep learning.

Answer: To answer this question, we should look at the best known bound by Theorem 1.2. in Golowich et al. (Size-independent sample complexity of neural networks, 2018) where the authors showed that the Rademacher complexity of DNNs with ReLU activation functions is upper bounded by
$$
\tilde{O}\bigg(\sqrt{\frac{L}{n}}\prod_{j=1}^L  M_F(j) \bigg).
$$
Here, $M_F(j)$ is the Frobenius norm of the weight matrix of the $j$-the layer, and $n$ is the number of training examples (Please also see Section 6 in our paper). 

In this work, by using Theorem 8 (or Theorem 2), we show that for CNNs or DNNs with some special classes of activation functions (ReLU, Leaky ReLU, PRLI, Sigmoid, and Tanh or odd functions in general), the Rademacher complexity can be upper bounded by
$$
O\bigg(\sqrt{\frac{1}{n}}\prod_{j=1}^L \mu_j M_{\infty} (j) \bigg),
$$ where $M_{\infty} (j)$ is the infinity-norm of the weight matrix of the $j$-the layer, and $\mu_j$ is the Lipschitz constant of the activation in the $j$-the layer. Note that $|\sigma_j(0)|/\sqrt{n}$ is usually very small compared to $\mu_j M_{\infty} (j)$. 

So what we meant here is that under the assumption that the product of norm of weight matrices is bounded, our bound does not depend on the network-length $L$, which is an improvement over Golowich et al.'s bound, especially when for DNNs with big network-length.  We borrowed the term "size-independent" from Golowich et al.'s work to show that meaning. We also note that our results hold for many class of activations, not only limited to ReLU as Golowich et al.'s work. We will add this discussion in our revised version. 

4. In Theorem 8, $L$ is not defined. Furthermore, $F_L$ depends on $L$. Does it contradict with the author's claim?

Answer: In Theorem 8, we mention that "we consider the CNN defined in Section 3.1" where we define $L$. Please re-check our paper more carefully.
For the second question, please refer to our answer for Question 3.

5. What do the numerical results in Section 5 imply? There is no elucidation. Furthermore, the authors only implement one experiment which is far from enough for verification.

Answer:  Our simulation results demonstrate that by refining the Rademacher complexity bound, we can derive non-vacuous generalization error estimates for certain CNN networks. To the best of our knowledge, this is the first result to show that the Rademacher complexity approach can yield meaningful (non-vacuous) generalization error bounds. This is particularly significant because our goal in developing generalization error bounds is to ensure they are applicable in practical settings.

We also provided two extra experiments in Appendix A.12 and mentioned this in Section 5. Please re-check our paper more carefully. 

6. The title is not accurate. This paper only studies CNNs.

Answer: Although we only limit our experiments on CNNs, however, our development results such as Theorem 2 and Lemma 7 can be applied for general DNNs. We can change the title to "On Rademacher Complexity-based Generalisation Bounds for CNNs" if necessary.   

Based on our responses to your questions, we believe that your evaluation of our work is not correct. Our results are significant from both theoretical and practical perspectives. Therefore, we kindly ask the reviewer to be fair in evaluating our contribution. We actually don't understand what are the maths or contribution problems in your comments and what is a "sound" paper related to developing generalisation error in your viewpoint.
Reply to reviewer's comments
Yes
No ethics review needed.
1. Lemma 1: $\epsilon$ is not defined.
2. The definition of network length should be provided at the beginning of the paper. It actually refers to the number of layers in Section 6. It would be better to adopt the conventional name "network depth".
3. What is the benefit of the bound that does not depends on the network length? It could not reflect the effects of depth in deep learning.
4. In Theorem 8, $L$ is not defined. Futhremore, $F_L$ depends on $L$. Does it contradict with the authors' claim?
5. What do the numerical results in Section 5 imply? There is no elucidation. Futhremore, the authors only implement one experiment which is far from enough for verification.
6. The title is not accurate. This paper only studies CNNs.
The authors employ the Talagrand's contraction lemma to develop novel   Rademacher-complexity-based generalization bound for CNNs and specialze the bounds to some common types of activation functions.
This paper explores the theoretical underpinnings of generalization in deep learning, specifically focusing on Convolutional Neural Networks (CNNs). The authors propose a new approach using Rademacher complexity to derive non-vacuous generalisation bounds for CNNs with certain activation functions like ReLU, Leaky ReLU, and Sigmoid. These bounds, unlike prior results, do not explicitly depend on the network depth. The authors validate their findings through experiments on MNIST image classification.
1. The paper's maths and presentation need to be significantly improved.
2. The theoretical contributions seem not sound enough.
Yes
No ethics review needed.
**1.About the remark 3**

The second bullet in remark 3 states that theorem 2 improves the bound for the case $m=1$. However, in Lemma 1 (Talagrand's lemma for $m=1$), the contraction rate is $\mu$, not $2\mu$.


**2. depth-dependent**

In theorem 8, the upper bound $F_L$ of $\mathcal{R}_{n}( \mathcal{F} )$ is defined using the recursive relation (34). 
Because of $\gamma_i$, $F_L$ seems depending on the depth, unlike the explanation in the remark 9. Could you provide a bit more details?

---

I am hoping that the authors will provide the clarifications stated therein in the rebuttal phase
They try to identify activation functions and consider wider hypothesis space (e.g. $\mathcal{H}_+$) to provide new contraction coefficients.
This work studies the Rademacher complexity for the class of CNNs using any of ReLU family activation functions. Based on the authors' new version of Talagrand's contraction lemma, they provide the upper bound on the Rademacher complexity. Also, they conducted numerical experiments verifying the gap between the upper bound and error.
**Questionable significance**

Though this work provides the new contraction lemma, in my opinion, the result is not so significant.
Compared to the known vector-valued Talagrands' contraction lemma ([1, 2]), theorem 2 seems to be able to have poor upper bounds since there is an additional term $\frac{1}{\sqrt{n}}| \psi (0) |$, which can even worsen the upper bound since the denominator is sublinear.
To clarify, please add more details and rigorously compare the lemmas in [1] and [2].
(e.g. why considering $\mathcal{H}_+$ lead better upper bound, ...)


**Non-vacuous bound**

The authors claim that the result provides a non-vacuous bound for CNNs with a small number of classes.
To verify this, they conducted several experiments under various setups.
However, as illustrated in Nagarajan & Kolter (2019), the bound may be vacuous depending on the norms of matrices (e.g. kernel) even if we carefully choose a set of parameters.
Thus, to prove the tightness, please provide a theoretical analysis of how their bounds behave under different matrix norm conditions in light of the results from Nagarajan & Kolter (2019).

**Comparison with other CNN bound**

Though there are lines of research studying generalization bound for CNNs, the authors do not provide any comparison with other known bounds. To highlight the novelty of the work, kindly suggest including a specific comparison section in their paper, highlighting key differences between their approach and existing CNN generalization bounds.

**Clarity Concerns**

There is no proof sketch or idea provided within the main text for any of the theorems; full proof in the main text or deferred to the appendix. For better readability, kindly suggest that the authors include brief proof sketches or key insights for the main theorems in the main text while keeping full proofs in the appendix.



**Reference**

[1] Maurer (2016), A vector-contraction inequality for Rademacher complexities

[2] Foster and Rakhlin (2019), $\ell_\infty$ Vector Contraction for Rademacher Complexity
Yes
No.
No ethics review needed.
See the Weaknesses part. In line 251, "Let $\psi(x)$ is" should be "Let $\psi(x)$ be" .
1. This paper provides a novel and useful contraction lemma, which extends the previous Talagrand contraction lemma to high-dimensional mapping case.
2. Based on the new contraction lemma, the authors derive the bounds of the Rademacher complexity for CNNs, which does not explicitly depend on the depth of CNNs. This improves the results in previous papers.
3. The authors derive some non-vacuous generalization bounds for CNNs.
This paper first generalizes the Talagrand contraction lemma to high-dimensional mapping case, then uses these new results to derive non-vacuous generalization bounds for CNNs. Their results show that the Rademacher complexity does not explicitly depend on the depth of the network for CNNs with some specific types of activation functions. some empirical results on the MNIST image classifications are also given.
1. This paper only considers some specific types of activation functions.
2. The conclusion that the obtained Rademacher complexity does not explicitly depend on the depth of CNNs is not very convincing, since by Equations (30), (31), (34), the Rademacher complexity may exponentially depend on the depth of CNNs if the right-hand-side of (30), and (31) are large than 1. More discussions on this claim should be added.
@inproceedings{
anonymous2024on,
title={On Rademacher Complexity-based Generalization Bounds for Deep Learning},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=Y7lc4aZ4iP},
note={under review}
}
We show that the Rademacher complexity-based approach can generate non-vacuous generalisation bounds on Convolutional Neural Networks (CNNs) for classifying a small number of classes of images. The development of new Talagrand's contraction lemmas for high-dimensional mappings between vector spaces and CNNs for general Lipschitz activation functions is a key technical contribution. Our results show that the Rademacher complexity does not explicitly depend on the network length for CNNs with some common types of activation functions such as ReLU, Leaky ReLU, Parametric Rectifier Linear Unit, Sigmoid, and Tanh.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Deep Learning CNN Generalisation Errors
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/09f551645b452debe986cc2ca6fbf12dff2eb967.pdf
learning theory
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/52a50504a1744bb72255699ebf12a355aabf368a.zip
On Rademacher Complexity-based Generalization Bounds for Deep Learning
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission