Koopman-based generalization bound: New aspect for full-rank weights

Factor $\Vert K_{\sigma_j}\Vert$

To derive a bound of $\Vert K_{\sigma_j}\Vert$, we bound $\sum_{\vert \alpha\vert\le s}c_{\alpha,s,d}\Vert \partial^{\alpha}(h\circ\sigma)\Vert^2$ by $\sum_{\vert \alpha\vert\le s}c_{\alpha,s,d}\Vert\partial^{\alpha}h\Vert^2$. As the proof of the boundedness of $\Vert K_{\sigma}\Vert$, one strategy is using the Faa di Bruno formula. However, as we added explanations in Appendix B, this strategy does not give us a tight bound since it involves a summation of derivatives, and the bound depends on the number of terms in the sum. Moreover, estimating the number of terms in the sum is difficult.

Our main goal of this paper is to investigate how the property of the weight matrices affects the generalization property. Since the norm of $K_{\sigma}$ does not depend on the weight matrices, if we assume the structure of the network is given, the property of the weight matrices does not affect the norm of $K_{\sigma}$. As we stated in Conclusion, investigating $K_{\sigma}$ and deriving a tighter bound is future work.

In addition, the dependency of $\Vert K_{\sigma}\Vert$ on $d_j$ and $s_j$ can be alleviated to $d_{j-1}$ and $s_{j-1}$ by the factor $G_j$. Please see Remark 5 and Appendix C for more details. We admit that if the network is deep and if the width is sequentially increased, then the factor $G_j$ does not remove the dependency on the width of the intermediate layers. In this work, we considered the Koopman operator for each transformation. However, combining several layers that have similar roles together and considering the Koopman operator for the combined transformation may alleviate the dependency on the width of the intermediate layers. In our future work, we will try to derive a tight bound by combining several layers together.

Clarification of Appendix B (Appendix E in the current version)

We updated Appendix E and added the explanation of the derivative of $\psi$. Assume $\delta_L=1$, $\psi(x)=1$ for $x\in\Omega$, and $\Omega$ is an interval (e.g., $\psi$ is the bump function defined in Appendix D). Then we can create a new function $\tilde{\psi}$ that satisfies $\Vert \tilde{\psi}^{(i)}\Vert_{L^2(\mathbb{R})}=\Vert \psi^{(i)}\Vert_{L^2(\mathbb{R})}$ for any $i=1,2,\ldots$, from $\psi$. Here, $\psi^{(i)}$ is the $i$th derivative of $\psi$.

Concrete bound

We added a section for showing concrete examples of our bounds in Appendix (Appendix H). In Example 3, we consider a shallow network. In this case, the bound depends only on the input dimension $d_0$. In Example 4, we combine our bound with an existing bound and obtain a bound of the network with an additional weight matrix to the one considered in Example 3. In this case, the bound depends on $d_1$ linearly. Please note that our bound does not depend on the loss function.

Minor comments

Thank you for your comments. We revised the paper based on your comments.

Dear Authors,

First of all, thank you so much for the detailed revision. I am working my way through the details as best as possible. I especially appreciate the fact that you have added additional details in some of the mathematical derivations as I have requested.

I do have a couple more questions, the first one of which concerns the $G_j$ and the additional section Appendix H with the two layer example. Apologies if I misunderstood something, please kindly provide more explanations.

I appreciate the discussion of the calculation of $G_j$ and the admission that "your, the main goal of this paper is to investigate how the property of the weight matrices affects generalization" (without regards to existing dependence on architectural parameters). This is an enormous restriction that severely restricts the applicability of your results, but if you had been able to completely circumvent this difficulty, the work would have been nothing short of exceptional.

So my first (most important) question is: in remark 5 (appendix C), at the second equality in the calculation of $G_j$, you are using the rotational symmetry of the Gaussian function $f_j$. But I don't see how this could possibly hold when there are several layers. Could you explain a bit more whether this step holds in general without having to assume something about $f_j$ (which is a little bit like cheating) and instead relying only on a definition of $g$?

Section question: In Section H where you consider the case of a two layer neural network (example 3), the same thing bothers me a bit: is your network 2-layer or 1-layer (assuming we consider $g$ as the loss function)? There seems to be some confusion as to the role of $\tilde{f}$ versus $g$.

My final question in this post relates to example 4: I am very happy that your conclusion is that there is dependence on the input dimension (but not on the hidden dimension). **This is exactly what I would expect at an intuitive level and what makes your approach unique! **

Could you write down the detailed proof using the "peeling technique"? The current version still looks more like a sketch. Also, what is $g$ in this case? Will the result hold with the square loss? How about a classification context with the cross entropy or a margin based loss?

Dear Reviewer ebFP,

Thank you very much for checking the rebuttal and the modified version of the paper. Below, we provide additional comments. We also revised the paper. The revised parts are colored in blue. We hope these comments answer your questions and that the revision gives readers more information.

Factor $G_j$

We investigated $G_j$ in more detail. We first obtain a result that shows the average of $G_j$ is bounded by a constant that is independent of $f_j$. Please see Appendix C for more details. In this result, the upper bound depends seriously on $s_j$ and $d_j$. Also, we need an assumption that $f_j$ does not have its support near $0$. We admit that this bound is not tight, and we need an assumption regarding the support of $f_j$. However, the fact that $G_j$ is bounded by a constant that is independent of $f_j$ is not trivial.

In addition, we can generalize the result about the upper bound of $G_j$ in the previous version. The previous result was for the case where $f_j$ is the Gaussian. The new result is valid for $\hat{f}_j$ that decays slower or equal to the speed of the Gaussian in the direction of $\mathcal{R}(W_j)^{\perp}$.

For now, we need some assumptions regarding $f_j$ to derive an upper bound of $G_j$. Removing these assumptions and dealing with more general cases are future work. However, we believe that the above additional results help readers understand the property of $G_j$.

There were small errors in Appendices C and H. We corrected them. They do not change the dependence of the final results on $s_j$ and $d_j$. Since the factor is complicated, for simplicity, we left only the asymptotically essential terms in the final result.

About Example 3

We basically consider $g$ as the nonlinear transformation in the last layer. In this case, the network $f$ in Example 3 is a 2-layer network. Our result is just about the Rademacher complexity of the function class of neural networks and is independent of the loss function. For connecting our results to generalization error, if the loss function is Lipschitz continuous, then we can use, e.g., Corollary 1 by Maurer, ALT 2016. For example, the squared error $L_i(x)=\vert x-y_i\vert^2$ is not Lipschitz continuous on $\mathbb{R}$. However, in practical situations, we do not need to consider the whole space for the loss function. For example, if we consider the classification task, the output of the network is always on $[0,1]$, and the label $y_i$ are also in $[0,1]$, then $L_i$ is Lipschitz continuous on $[0,1]$.

On the other hand, we can also consider $g$ as a loss function, as you pointed out. In this case, the network $f$ in Example 3 is a 1-layer network.

As for the relationship with $\tilde{f}$, we are sorry that the explanation was misleading. We just wanted to explain that the network $f=g(Wx+b)$ that we are considering is similar to the standard shallow network $\tilde{f}(x)=W_2\sigma(W_1x+b)$. The final transformation $g$ has a similar role to that of $W_2\sigma(\cdot)$ in $\tilde{f}$. In fact, we do not need $\tilde{f}$ for obtaining the result in Example 3. To avoid confusion, we removed the explanation of $\tilde{f}$ in Example 3 in the paper.

About Example 4

We added detailed explanations in Appendix G and Example 4 about the combination with the "peeling" approaches. Also, the Frobenius norm was denoted as $\Vert\cdot\Vert_{2,2}$ in the main text, but as $\Vert\cdot\Vert_{\mathrm{F}}$ in the appendix. We corrected that to make the notation consistent. For Example 4, $g$ is the identity function. Since we used the existing result for the last layer, $g$ does not have to be in the Sobolev space. Please note that as we stated above, we can use Corollary 1 by Maurer, ALT 2016, to get the result for the Rademacher complexity for Lipschitz continuous loss functions.

About Example 1

We can show the representation of the Sobolev norm with the derivatives by using the properties of the Fourier transform. We added the explanation in Appendix K. (To keep the section number consistent with the response to other reviewers, we put the explanation in the last part of the appendix. However, we will put it in an appropriate place in the camera-ready version.)