Generalization Bounds for Rank-sparse Neural Networks

Many thanks for your positive review and your statement that our paper clearly where this work stands among other works, and that our theorems are clean and easy to absorb. We try our best to allay all your concerns below and stand ready to provide further clarifications upon request.

Re weaknesses:

1. Many thanks for your comment. We agree that this additional regularization in the fully-connected experiments favors our bound and somewhat departs from our general approach of minimizing optimization tricks. We believe that both our bounds would still outperform the baselines if we replaced this trick by spectral constraints, and that our sharper result (including loss augmentation) would still outperform the baselines with neither trick involved. We promise to incorporate a discussion of some additional such experiments in the camera ready version if accepted.

2. The architecture was chosen to be large enough to involve the rank-sparsity inducing effects of depth which we study, but also small enough to allow us to fun experiments for a wide range of widths without undue computational overload.

3. Yes, our numerical comparison ignores logarithmic factors and constants. This is in line with much of the recent literature. Therefore, the main message of our experimental section is that our bounds are less sensitive to increases in width, since they can capture the spontaneous reduction in function class capacity arising from low-rank representations. We would also like to point out that it is very difficult, if not impossible, to compare all bounds in the literature without ignoring logarithmic factors and constants. Indeed, many works (e.g. [2]) skip constants entirely, and many works (e.g. [2,3]) do not explicitly write down the proof of the post hoc step, leaving it as an exercise for the reader. This makes a comparison with our theorem E.2. unfair if one includes the logarithmic factors arising from the numerous post hoc steps over $s\_{\ell}, p\_{\ell}, \mathcal{M}\_{\ell},$ etc.

4. Yes, the bounds are vacuous at realistic scales if one incorporates all the logarithmic factors (though as explained above, this is a potentially questionable point). Our aim was to limit ourselves to uniform convergence bounds, excluding many of the tricks used to optimize bounds. For instance, to the best of our understanding, [9] rely on a compressionof the learned network, similarly, [10] assumes that the weights of the first and second layer are optimized on distinct subsets of the training set. We interpret these facts as warranting the classification of those results as belonging to a slightly different branch of the literature. However, we really enjoyed reading both papers [9,10] suggested (especially [10]) and promise to incorporate a further discussion of them in the camera ready version if accepted.

5. Many thanks for the suggestion. Although we have already included other references by the same authors which study the same phenomenon [13,14,15], we have missed this one, which we promise to discuss in the camera ready revision.

Re question 1:

Yes, you are right, and this is a very sharp observation. This is due to the Markov inequality argument in the key proof of Proposition F2, which we also recommend you check in the proof sketch we added in the response to reviewer 9AFC. The key reason is that the parameter counting component of the function class involves a factor of $[m+d]r$ and even the norm-based component involves a factor of $\min(m,d)\tau^2$, resulting in an unavoidable dependence on $[m+d]$ (or at least $\min(m,d)$).

To the best of our knowledge, it is difficult to smoothly remove this limitation except by trivially imposing a minimum between both bounds. This underscores the substantial differences between our application of parametric interpolation in the neural networks context as opposed to its original introduction in the context of matrix completion in [1]. However, we want to emphasize that this doesn't make our results uniformly inferior to either norm-based or parameter counting bounds. Indeed, counting parameters directly when estimating the capacity of the first layer of linear maps $A^1\in\mathbb{R}^{m\times d}$ would yield a sample complexity of at least $md$ instead of $[m+d]$, and the norm-based bound would be very large if the norms of the weights are large, though our own results involve norm based quantities only at a reduced and tunable power of $\frac{2p}{p+2}$. Furthermore, if all the weights are binary (making norm based and parameter counting approaches equal), then our result will coincide with both, indicating that there is no "pure loss": it can merely be said that although our bound interpolates between $p=0$ and $p=2$, a casualty of the interpolation is that even setting $p=2$ (which corresponds to the norm-based bound), the bound still leans slightly towards parameter counting despite incorporating strong norm-based aspects. Indeed, consider the one layer case in n idealised situation where each weight belongs to the set $\{-1,1\}$. In this case, the norm based bound gives a sample complexity of $\|A\|\_{Fr}^2=md$, which recovers the same bound as a pure parameter counting bound. In this case, our sample complexity bound for $p=2$ and $B=1$ scales as (cf Theorem 3.1) $\mathcal{M}^{\frac{2p}{p+2}} \min(m,d)^{\frac{p}{p+2}} [m+d]^{\frac{2}{p+2}}=\mathcal{M} [m+d]=O(\|A\|\_{Fr}\sqrt{\min(m,d) \max(m,d)} )=O(md)$, which also coincides with both norm based and parameter counting bounds. However, as explained in the main paper, our bound is also sensitive to the rank, approximate rank, etc.

Re Question 2: we meant to refer to the results in [12,13,14,15,16], and promise to clarify this further in the camera ready revision.

Re Limitations: many thanks, we will incorporate a full discussion as above in the revision. Re minor issues: many thanks for your help in improving the clarity of our manuscript. Regarding points 2 and 3, the confusion arises from the fact that we treat the Lipschitz constants as absolute constants in the informal discussion in the introduction, removing the need for the factor in question.

Once again, thank you for your thorough comments. We hope that our rebuttal has helped further convince you of the value of our work and that you will continue to engage with us in the discussion phase.

=================================References===========================

[1] Ledent, A.; Alves, R. Generalization Analysis of Deep Non-linear Matrix Completion. ICML 2024.

[2] Long, P. M.; Sedghi, H. Generalization Bounds for Deep Convolutional Neural Networks. ICLR 2020.

[3] Graf, F.; Zeng, S.; Rieck, B.; Niethammer, M.; Kwitt, R. On Measuring Excess Capacity in Neural Networks. NeurIPS 2022.

[4] Zhang, T. Covering Number Bounds of Certain Regularized Linear Function Classes. JMLR 2002.

[5] Bartlett, P. L.; Foster, D. J.; Telgarsky, M. Spectrally-Normalized Margin Bounds for Neural Networks. NeurIPS 2017.

[6] Suzanna Parkinson, Greg Ongie, Rebecca Willett. ReLU Neural Networks with Linear Layers are Biased Towards Single- and Multi-Index Models

[7] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, Daniel M. Roy. On the role of data in PAC-Bayes bounds

[8] Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, Franck Gabriel. Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity

Earlier version: Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Deep linear networks dynamics: Low-rank biases induced by initialization scale and l2 regularization.

[9] Zhou, Wenda, et al. "Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach."

[10] Biggs, Felix, and Benjamin Guedj. "Non-vacuous generalisation bounds for shallow neural networks." International Conference on Machine Learning. PMLR, 2022.

[11] Neyshabur, Bhojanapalli, Srebro. A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks. ICLR 2018.

[12] Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, Franck Gabriel. Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity

Earlier version: Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Deep linear networks dynamics: Low-rank biases induced by initialization scale and l2 regularization.

[13] Bottleneck structure in learned features: Low-dimension vs regularity tradeoff. NeurIPS 2023.

[14] Implicit bias of large depth networks: a notion of rank for nonlinear functions.

[15] Zihan Wang and Arthur Jacot. Implicit bias of SGD in $l_2$-regularized linear DNNs: One-way jumps from high to low rank. ICLR 2024.

[16] Laura Balzano, Tianjiao Ding, Benjamin D. Haeffele, Soo Min Kwon, Qing Qu, Peng Wang, Zhangyang Wang, Can Yaras. An Overview of Low-Rank Structures in the Training and Adaptation of Large Models. ArXiv 2025

Many thanks for your careful reading and for your appreciation of our work. We are happy that you deem our work to address meaningful problems and ** is clearly situated and motivated within the context of previous literature.**

Re **clarity **(especially the introduction): many thanks for your comment and for the typos identified. We promise to restructure the introduction to further improve clarity by defining the relevant quantities earlier and introducing further simplifications in the introduction.

Re L 281 "realistically smaller": yes, the improvement provided in this theorem is frequently significant, since it removes a factor of the product of spectral norms from layer 1 to layer $\ell-1$ (replacing it by an empirical estimate of the norms of the intermediary activations.

Re "full range $0\leq p\leq 2$"/ L8, conflict with abstract: for $p<1$, the resulting object is not a norm but only a quasi norm, though we agree it is a norm for $p\geq 1$. All norms are also quasi norms, but the opposite is not true, which makes it difficult to choose a single term since (as you observe) we cover the full range $p\in[0,2]$. Therefore, we use the term "quasi-norm" in all cases to avoid the more redundant term "quasi norm/norm". We promise to explain this more clearly earlier in the introduction and are willing to adapt to any further suggested change of terminology.

Re "low-rank weights, not low-rank activations": many thanks for the insightful comment. We do mention the distinction in various places including the conclusion/future directions. However, we agree to discuss it more clearly earlier in the introduction. As mentioned in the paper, the two are very closely related $\star$ and we believe that a significant extension of our techniques would allow us to directly capture the low-rank structure in the activations as well (without truncating the rank of the weights after training). However, this requires a much more careful treatment involving advanced uses of loss function augmentation, especially when the activations are only approximately low-rank. From our initial calculations, the singular value thresholds must be tuned simultaneously over all layers, which is very tedious.

Re typos: many thanks, we will fix all of them.

Many thanks again for your comments, we promise to discuss all the above issues in more detail in the camera ready revision if accepted and look forward to continuing our discussion during the author-reviewer discussion phase.

Footnote: $\star$ Indeed, treating only the exactly low-rank case for simplicity, if the inputs $x_1,\ldots,x_N$ lie in a low-rank space of dimension $r$, then for any high rank weight matrix $W\in\mathbb{R}^{m\times d}$, there exists a low rank weight matrix $\bar{W}$ of rank less than $r$ which has exactly the same effect on these inputs: $Wx_i=\bar{W} x_i$ for all $i$. Indeed, if $U\in \mathbb{R}^{d\times r}$ is an orthonormal basis of that subspace, then $\bar{W}=[WU ]U^\top$ will work because $UU^\top x_i =x_i$ for all $i$. Thus, if the activations are low-rank, then the same network can be represented with low-rank weights.

Many thanks for your efforts reading and reviewing our paper. We try our best to allay most of your concerns in this response and stand ready to answer any further questions you may have during the author discussion period.

Re weakness 1 "there is no any problem set up": The problem set up is described in the "main results" section, and is a standard supervised learning set up with neural networks where we study the excess risk in terms of an arbitrary $L^\infty$ loss function. As explained in that section, this setting can cover both classification [1,4] and regression [2] settings, and is a similar generic characterisation as in [3] (mentioned by reviewer wqbT).

Re weakness 1 "no empirical results and detailed experimental settings in the main text" and weakness 3 "There is no experimental verification of the tightness of these bounds beyond theoretical discussion (though they mention an appendix with MNIST/CIFAR10 references, it is not sufficiently emphasized and lacks of comparisons with recent approaches)":

Our paper contains a large amount of content including novel generalization bounds for linear classifiers as well as bounds for deep neural networks with a low rank structure, it is difficult to include every result in the main paper. However, the appendix does include substantial experimental verification on pages 31 to 36 where we demonstrate our bounds' competitiveness and ability to capture some of the phenomenon of unused function class capacity. Indeed, we demonstrate:

1. That our bounds are competitive with other uniform convergence bounds and 2. that our bounds are less sensitive to architecture changes than other bounds in the overparametrization setting. In particular, this demonstrates our bounds' ability to capture unused function class capacity via an alternative notion of effective capacity than the well-established alternative such as the distance to initialization and the margins.

Re weakness 1 "the experiments lack comparison to recent approaches": whilst our paper is mostly theoretical, we compare our work experimentally to 11 baselines from 7 papers including one from ICML 2024. The choice was based on a focus on bounds in the same category as ours: uniform convergence bounds which do not incorporate the optimization procedure into the bound and do not overly optimize the bound with data dependent priors or by splitting the dataset and learning different parameters on each subset (such as e.g. [3]). To the best of our knowledge, the compared approaches are state of the art in this category. Please let us know if you have another specific "recent approach" in mind for us to compare to. This would help us further improve the contextualisation of our work.

Re weakness 5 "no practical impact in terms of model design" and "assumption of low-rank matrices may not hold in practice": the main message in our submission is that the implicit low-rank condition which occurs with depth and overparametrization implies a reduction in effective function class capacity and therefore, estimation error. The convergence to low-rank representations is a broadly studied phenomenon which many recent works have demonstrated occurs at realistic scales. We believe that demonstrating the effects of this phenomenon on learning is worthy in itself, even if it may not yield completely new models (though it does provide some evidence for why depth can reduce rather than increase function capacity in some regimes.

On your questions:

1. As we tried to explain in lines 86-94, the parameters $p$ control the strictness of the low rank constraints and the bounds position on the spectrum between parameter counting bounds and norm-based bounds. Indeed, when $p\rightarrow 0$, the bound behaves as a parameter counting bound taking into account the rank of the weight matrices. For larger $p$s, the bound behaves more like a norm-based bound based on the approximate rank of the weight matrix, with a larger tolerance for moderately small singular values.

Next, note that as explained in line 289, the bounds hold simultaneously over all values of $p_l$. Therefore, the $p_\ell$s can be be optimized after training via grid search.

2. As can be seen from the (logarithmic) scale of the axes of Figures D1 and D4, the bounds are generally vacuous at realistic scales, even ignoring logarithmic factors. However, so are all comparable bounds in the literature when used directly. We acknowledge it is possible to obtain tighter bounds through a more aggressive optimization of the bound or by modifying the training procedure to validate certain parameters using the training data. However, such bounds are no longer directly comparable.

3. Our bounds include margin-based generalization analyses as particular cases of our results. In particular, our setting for the classification case is exactly the same as that in [1]. In that case, our result is generally tighter but nether uniformly superior nor inferior to most existing approaches. A combination of our results with bounds based on the Neural Tangent Kernel would be more subtle since such results ** rely heavily on the optimization procedure**. However, if one assumes that the neural network training is purely at the neural tangent kernel scale, then the problem becomes analogous to the study of linear predictors, which could in principle be combined with our results. However, to the best of our knowledge, the convergence of neural network learning to a neural tangent kernel limit has not been proved in a reasonable classification setting (all NTK results rely on the square loss).

We promise to incorporate a discussion of these concerns in the camera ready version.

4. As explained in lines 76 to 80, the emergence of the low-rank condition is well-documented in many influential recent papers [5,6,7,8], including large language models [8]. We also verified it experimentally, as can be seen in figures D2 and D4.

Re formatting concern 3" in line 248, "the above bound" refers to equation (11) in the theorem just above the remark inside which line 248 is found. We will replace the statement by a concrete reference to the equation as requested, many thanks for helping us improve the presentation of our work.

Re figure captions: in figures D2 and D4, the plots illustrate the spectral decay of the weight matrices: each given plot represents the singular values of a weight matrix, ordered from the largest one (on the left) to the smallest one (on the right). Hence, the x axis is referred to as "index" in the caption and the y axis similarly refers to the "magnitude" of the singular value. Thus, the graphs are always decreasing by definition, and a graph which hits 0 (i.e. the x axis) at index r would correspond to a matrix of rank exactly less than r. We will make sure to explain this in further details in the revision.

[1] Peter Bartlett, Dylan J. Foster, Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. NeurIPS 2017

[2] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. ICML 2019 [3] Biggs, Felix, and Benjamin Guedj. "Non-vacuous generalisation bounds for shallow neural networks." ICML 2022.

[4] Florian Graf, Sebastian Zeng, Bastian Rieck, Marc Niethammer, Roland Kwitt. NeurIPS 2022On Measuring Excess Capacity in Neural Networks.

[5] Arthur Jacot. Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff. NeurIPS 2023

[6] Zihan Wang, Arthur Jacot. Implicit bias of SGD in L2-regularized linear DNNs: One-way jumps from high to low rank. ICLR 2024

[7] Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity. Arxiv 2021

[8] Laura Balzano, Tianjiao Ding, Benjamin D. Haeffele, Soo Min Kwon, Qing Qu, Peng Wang, Zhangyang Wang, Can Yaras. An Overview of Low-Rank Structures in the Training and Adaptation of Large Models. ArXiv 2025

Many thanks for your detailed comments and interest in our work and promise to increase your score to 5 pending a satisfactory proof sketch of our main theorem. Due to the character limit, we include only the sketch here. Please note the answers to your other questions are provided in the response to reviewer Udna.

Simplified Prop F2 (covering number for one layer): Consider the following function class of linear maps from $\mathbb{R}^d$ to $\mathbb{R}^m$: $\mathcal{F}^p:=\{M \in\mathbb{R}^{m\times d}, \|M\|\_p\leq \mathcal{M}; \|M\|\leq s\}$. For any $\epsilon>0$ and for any dataset $x_1,\ldots,x_N\in\mathbb{R}^d$ such that $\|x_i\|\leq B$ for all $i$, we have the following bound on the $L^\infty$ covering number (cf Prop F2 for formal defn) of the class:

$\log(\mathcal{N}_{\infty}(\mathcal{F}_r^p,\epsilon))\lesssim [m+d]\Bigg[\frac{\mathcal{M}B}{\epsilon}\Bigg]^{\frac{2p}{p+2}}\log(\frac{mdN\mathcal{M}}{\epsilon}).$

Proof sketch (for simplicity we assume $B=1$ in the sketch):

For any $M\in\mathcal{F}^p$, write $\sum_{i=1}^{\min(m,d)} \rho_i u_iv_i^\top$ for its singular value decomposition. For a threshold $\tau>0$ to be determined later, we decompose every $M\in\mathcal{F}^p$ into $M=M_1+M_2$ where $M_1=\sum_\{i\leq T\} \rho_i u_iv_i^\top$ and $M_2=\sum_{i\geq T+1}\rho_i u_iv_i^\top$ where $T$ is the last index such that $\rho_{T}> \tau$.

By Markov's inequality, since $\|M\|\_p^p=\sum_i \rho_i^p \leq \mathcal{M}^p$, we have $\text{rank}(M_1)\leq \tau\leq \frac{\mathcal{M}^p}{\tau^p}$. In addition, the spectral norm of $M_1$ is bounded as: $\|M\_1\|=\rho_1=\|M\|\leq \|M\|\_{p}\leq \mathcal{M}$. Thus, $M_1$ belongs to the set ${\mathcal{F}^p}\_1:=\Big\{ Z\in\mathcal{F}^p:\text{rank}(Z)\leq \frac{\mathcal{M}^p}{\tau^p}, \quad \|Z\|\leq \mathcal{M}\Big\}$ (a function class with few parameters its members are low-rank) Furthermore, it is clear that $\|M_2\|\_{FR}^2=\sum_{k=T+1}^{\min(m,d)} \rho_k^{2} \leq \tau^2 {\min(m,d)}.$ Therefore $M_2$ belongs to the class $\mathcal{F}^p\_2:=\{Z\in\mathcal{F}^p: \|Z\|\_{\text{FR}}^2\leq \tau^2 {\min(m,d)}\}$ (a function class whose members have small norms).

By classic parameter counting arguments (cf. [2,3] etc., the specific result being Lemma D1 page 30 in [1]), we have the following bound on the $L^\infty$ covering number of $\mathcal{F}^p_1$: $\mathcal{N}_\infty(\mathcal{F}^p_1,\epsilon/2)\lesssim [m+d][\text{rank}] \log(\frac{\mathcal{M}}{\epsilon})\lesssim [m+d]\frac{\mathcal{M}^p}{\tau^p}\log(\frac{\mathcal{M}}{\epsilon}).$

By classic norm-based arguments (Theorem 4 in [4]), we can bound the covering number of the class $\mathcal{F}^p_2$ as follows: $\log(\mathcal{N}(\mathcal{F}^p_2,\epsilon/2))\lesssim [\text{max Frob norm}] \log(\frac{\tau^2 mdN}{\epsilon}) =\frac{\tau^2 {\min(m,d)}}{\epsilon^2} \log(\frac{\tau^2 mdN}{\epsilon}).$

Combining both covering number bounds gives $\log(\mathcal{N}_{\infty}(\mathcal{F}_r^p))\leq \log(\mathcal{N}(\mathcal{F}^p_1,\epsilon/2))+\log(\mathcal{N}(\mathcal{F}^p_2,\epsilon/2))\lesssim \frac{\tau^2 {\min(m,d)}}{\epsilon^2} \log(\frac{\tau^2 mdN}{\epsilon})+[m+d]\frac{\mathcal{M}^p}{\tau^p}\log(\frac{\mathcal{M}}{\epsilon})$

Setting $\tau=\mathcal{M}^{\frac{p}{p+2}} \epsilon^{\frac{2}{p+2}}$ gives $\log(\mathcal{N}_{\infty}(\mathcal{F}_r^p))\lesssim$ $[m+d]\left[\frac{\mathcal{M}}{\epsilon}\right]^{\frac{2p}{p+2}}\log(\frac{mdN\mathcal{M}}{\epsilon})$ as expected.

The above result forms the basis of the one-layer case. As requested, we now consider the two-layer case:

Simplified form of Proposition E.1.: Consider neural networks of the form $F_{A}:x\rightarrow A^2 \sigma(A^1 x)$ where $\sigma$ is an elementwise 1-Lipschitz activation function (e.g. ReLU) and $A_1\in \mathbb{R}^{m\times d}, A^2\in\mathbb{R}^{C\times m}$ are weight matrices. For fixed $p_1=p_2=p\in[0,2]$ and $s_1,s_2,\mathcal{M}_1,\mathcal{M}_2>0$, let $\mathcal{F}$ denote the class of such networks which further satisfy for all $i\in\{1,2\}$: $\|A^i\|\leq s_i; \> \|A^i\|_p\leq \mathcal{M}_i$. By abuse of notation, we also use $\mathcal{F}$ to refer to the set of matrices $(A^1,A^2)$ satisfying the above requirements.

Let $\ell: \mathbb{R}^C\times [C]\rightarrow \mathbb{R}^+$ be a 1-Lipschitz loss function w.r.t. the $L^\infty$ norm (e.g. a margin-based loss function as in [2,3,5] with margin 1) and assume we are given an i.i.d. training set $(x_1,y_1),\ldots, (x_N,y_N)$ from a joint distribution over $\mathbb{R}^d\times [C]$ such that $\|x_i\|\leq B$ w.p. 1.

For any $\delta>0$, w.p. $\geq 1-\delta$, any network $F_A\in\mathcal{F}$ satisfies the following generalization bound: $\mathbb{E}\ell(F(x,y))-\hat{\mathbb{E}}(\ell(F(x,y)))$ $\leq \tilde{O}\bigg([s_1s_2]^{\frac{p}{2+p}} \bigg[\big[\frac{\mathcal{M}_1^{p}}{s_1^{p}}\big]^{\frac{2}{p+2}} [m+d]^{1+\frac{p}{p+2}} + \big[\frac{\mathcal{M}_2^{p}}{s_2^{p}}\big]^{\frac{2}{p+2}} [m+C]\bigg]^{\frac{1}{2}} \frac{1}{\sqrt{N}} +\sqrt{\frac{\log(1/\delta)}{N}}\bigg).$ $< \tilde{O}\Bigg([s_1s_2]^{\frac{p}{2+p}} \bigg[\big[r_1[m+d]^{1+\frac{p}{p+2}} + r_2 [m+C]\bigg]^{\frac{1}{2}} \frac{1}{\sqrt{N}} +\sqrt{\frac{\log(1/\delta)}{N}} \Bigg),$

where for $i=1,2$, $r_i:=\big[\frac{\mathcal{M}_i^{p}}{s_i^{p}}\big]^{\frac{2}{p+2}}$ is a soft analogue of the rank.

Remarks: We assume the margin parameter is 1 because you specifically requested that the lipschitz constant be ignored. However, our full results include a fine analysis of the dependency on the margin parameter $\gamma\simeq 1/L_1$. The $\tilde{O}$ notation incorporates logarithmic factors of $N,m,d,C,1/\epsilon, s_1,s_2,\mathcal{M}_1,\mathcal{M}_2$.

Proof sketch:

Step 1 (key): bounding the $L^{\infty}$ covering number of $\mathcal{F}$. Since the loss function is 1 Lipschitz, we only need to find an $L^\infty$ cover of $\mathcal{F}$, i.e., a set $\mathcal{C}\subset \mathcal{F}$ such that for any $A=(A^1,A^2)\in\mathcal{F}$, there exists a cover element $(\bar{A}^1,\bar{A}^2)\in \mathcal{C}$ such that $\forall i, \|F_{A}(x_i)-F_{\bar{A}}(x_i)\|\_\infty\leq \epsilon$ (here, recall $F_{A}(x_i)\in\mathbb{R}^C$ is a vector of scores for all classes). We achieve this by adapting standard chaining techniques (see [3,5]), with the caveat that we need to change the norm of the cover at the intermediary layer, incurring a factor of $\sqrt{m}$. Let $\mathcal{F}^1,\mathcal{F}^2$ denote the set of matrices $A^1\in\mathcal{R}^{m\times d}$ and $A^2\in\mathcal{R}^{C\times m}$ satisfying the relevant constraints above. First, we can apply Proposition F2 above, with $\epsilon$ set to $\epsilon_1:=\epsilon/[2\sqrt{m}s_2]$, to achieve a $\mathcal{C}_1\subset\mathcal{F}_1$ such that for all $A\in\mathcal{F}$ there exists a $\bar{A}\in\mathcal{C}$ such that $\forall i$, $\|\sigma(A^1(x_i))-\sigma(\bar{A}^1(x_i))\|\leq \|A^1x_i-\bar{A}^1x_i\|\leq \sqrt{m} \|\leq \|A^1x_i-\bar{A}^1x_i\| \leq \sqrt{m}\epsilon_1 =\frac{\epsilon}{2s_2}.$ and $\log(|\mathcal{C}|)\in \tilde{O}\Bigg( [m+d] \Big[\frac{\mathcal{M}_1 B }{\epsilon_1}\Big]^{\frac{2p}{p+2}} \Bigg) =\tilde{O}\Bigg( [m+d] m^{\frac{p}{p+2}} [s_1 s_2B]^{\frac{2p}{p+2}}\Big[\frac{\mathcal{M}_1 }{s_2\epsilon}\Big]^{\frac{2p}{p+2}}\Bigg)$.

Similarly, for any $\bar{A}^1\in\mathcal{C}_1$, every $i\leq N$ satisfies $\|\sigma(\bar{A}^1x_1)\|\leq s_1 B$, and therefore another application of Proposition F2 above with $B$ replaced by $\tilde{B}:=s_1 B$ and $\epsilon$ replaced by $\epsilon_2:=\epsilon/2$ yields a cover $\mathcal{C}_2(\bar{A}^1)$ with size $\log(|\mathcal{C}_2(\bar{A}^1)|)\in \tilde{O}\Bigg( \Big[\frac{\mathcal{M}_2 [Bs_1] }{\epsilon_2}\Big]^{\frac{2p}{p+2}} \Bigg)=\tilde{O}\Bigg([Bs_1s_2]^{\frac{2p}{p+2}} \Big[\frac{\mathcal{M}_2 }{\epsilon s_2}\Big]^{\frac{2p}{p+2}} \Bigg)$.

The cover $\mathcal{C}:=U\_{\bar{A}^1\in\mathcal{C}_1} \mathcal{C}_2(\bar{A}^1)$ is now an $\epsilon$ cover of $\mathcal{F}$.

Indeed, for any $(A^1,A^2)\in\mathcal{F}$, we can define $\bar{A}^1$ to be the cover element associated to $A^1$ in $\mathcal{C}_1$ and subsequently $\bar{A}^2$ to be the cover element in $\mathcal{C}\_1(\bar{A}^1)$ associated to $A^2$, which yields for any $i\leq N$: $\|A^2\sigma(A^1x_i)-\bar{A}^2\sigma(\bar{A}^1x_i)\|\_{\infty}\leq \|A^2\sigma(A^1x_i)-A^2\sigma(\bar{A}^1x_i)\|\_{\infty}+\|A^2\sigma(\bar{A}^1x_i)-\bar{A}^2\sigma(\bar{A}^1x_i)\|\_{\infty}$ $\leq \epsilon_2+\|A^2\| \|\sigma(A^1(x_i))-\sigma(\bar{A}^1(x_i))\|\leq \epsilon/2+s_2\epsilon/[2s_2] =\epsilon.$ Furthermore, the resulting cover has cardinality bounded as $\log(|\mathcal{C}|)\in \tilde{O}\Bigg( \Big[\frac{Bs_1s_2}{\epsilon}\Big]^{\frac{2p}{p+2}} \Big[[m+d]^{1+\frac{p}{p+2}} \Big[\frac{\mathcal{M}_1 }{s_1}\Big]^{\frac{2p}{p+2}} +[m+C] \Big[\frac{\mathcal{M}_2 }{s_2}\Big]^{\frac{2p}{p+2}} \Big]\Bigg).$

Step 2: Apply Dudley's entropy integral to obtain Rademacher complexity and apply classic results. This step (cf. Proof of Prop E1) involves more straightforward calculations.

In prop E2, the result holds uniformly over all $p$s and all $\mathcal{M}_1,\mathcal{M}_2,s_1,s_2$. The idea of the proof is to apply Prop E1 to a each element of grid $\{0,2/K, 4/K,\ldots 2\}$ of $p$s with the failure probability replaced by $\delta/[K+1]$ and to tune the granularity $K$ together with a tedious continuity argument w.r.t $p$. Cf. pp 39 to 42 for details.

[1] Ledent, A.; Alves, R. Generalization Analysis of Deep Non-linear Matrix Completion. ICML 2024.

[2] Long, P. M.; Sedghi, H. Generalization Bounds for Deep Convolutional Neural Networks. ICLR 2020.

[3] Graf, F.; Zeng, S.; Rieck, B.; Niethammer, M.; Kwitt, R. On Measuring Excess Capacity in Neural Networks. NeurIPS 2022.

[4] Zhang, T. Covering Number Bounds of Certain Regularized Linear Function Classes. JMLR 2002.

[5] Bartlett, P. L.; Foster, D. J.; Telgarsky, M. Spectrally-Normalized Margin Bounds for Neural Networks. NeurIPS 2017.

Thank you for the very helpful proof sketch. While I believe there are a few minor typos in the proof sketch, the arguments are morally correct. Can you address the following?

• By Markov's inequality... $rank(M_1) \le T \le M^p/\tau^p$. That is, the middle $\tau$ in this line in proof sketch should be replaced with $T$, correct?
• Markov's inequality: Why do you call this inequality Markov's inequality? The fact that $rank(M_1) \le T \le M^p/\tau^p$ is straightforward to verify, but it's odd to call it Markov's inequality since there is no obvious probability distribution on the singular values. Unless you refer to a different inequality due to Markov than $P(X \ge a) \le \mathbb E[X]/a$?
• What is happening here?

$\le \sqrt{m} | \le |A^1 x_i - \bar A_i x_i|$

• I believe the bound on $\log(|C_1|)$ should have an $s_1$ instead of $s_2$ in the denominator, correct?
• The term $(m+C)$ appears to be missing from the bound on $\log(|C_2(\bar A^1)|)$
• It is suggested to state that the final bound on the metric entropy comes from the fact that $|C| \le |C_1| \sup_{\bar A^1 \in C_1} |C_2(\bar A^1)|$ to clarify how the metric entropies are combined.

Dear Reviewer,

Thank you again for your efforts in assessing our paper and for your valuable feedback and suggestions.

As the time for discussion is beginning to run out, we would like to reach out and hear about your thoughts on our rebuttal. Please let us know if any further clarification is needed, or if you would like us to elaborate on any particular aspect of the proof sketch, or provide a sketch for any of the other theorems.

Please let us know if our rebuttal has improved your opinion of our work.

Best regards,

Authors

Dear Reviewer,

Many thanks for increasing your score and for your help improving our work throughout the reviewing process. We promise take all your valuable comments into account and thoroughly polish our whole work for the camera-ready version if accepted.

Best regards,

Authors

Many thanks for your positive review and your interest in our work, as well as the efforts invested in reading our paper. We also appreciate your statements that our paper is very well written and comprehensively discusses a lot of related papers.

Re main weakness "Putting them together is a valuable contribution, but that also means that the mathematical novelty in this paper is limited. In case this is mistaken, the authors should do a more precise job of outlining their novel mathematical contributions":

Many thanks for your comment. We want to clarify that our bounds are the first to incorporate the technique of parametric interpolation into the study of neural networks. Thus, we are the first to provide generalization bounds in this context which are neither fully "parameter counting bounds" nor fully "norm-based" bounds. This is achieved by interpolating between the two regimes. More precisely, we the class $\mathcal{F}_p:\{A\in\mathbb{R}^{m\times d}: \|A\|\leq s, \|A\|_p\leq \mathcal{M}\}$ into two components: (1) a component with (exactly) low rank, to be treated with parameter counting techniques [2,3], and (2) a component with small norms, to be treated with norm based techniques [4,5]. For linear maps $A\in\mathbb{R}^{m\times d}: x\rightarrow Ax$, parameter counting bounds on the covering number of the class \{A\in \mathbb{R}^{m\times d}}: \|w\|\_{FR}}\leq a\} scale as $O\Big( D\text{Polylog}(\epsilon,a,b) \Big)$ where $b$ is a bound on the input samples' norms and $D=md$ is the number of parameters. On the other hand, norm-based bounds scale as $O\Big(\frac{a^2b^2}{\epsilon^2}\text{Polylog}(N,a,b,d)\Big)$. Combining them in an approximately low-rank context allows us to replace $D$ by $[m+d]r$ where $r$ is a threshold rank depending on the Schatten quasi norms, gives rise to a completely different dependency on $\epsilon, a,b$ and even the Lipschitz constant of the loss (i.e. the margin parameter in a classification context). The combination is not trivial and involves decomposing the function class by thresholding the singular values with a carefully tuned threshold (cf. eq F13). In addition, there are many additional technicalities which are new to this setting. For instance, the continuity argument to make the bounds post hoc with respect to all the Schatten indices $p\_{\ell}$ is relatively tedious. To further improve your assessment of the novelty of our method, we invite you to read the proof sketch of a minimum working product version of our theorem which is provided in our answer to reviewer 9AFC.

We promise to further emphasise the novelty of our techniques and provide the proof sketch in the camera ready version if accepted.

Re typos:

Line 56 (also pointed out by reviewer 9AFC): we will add the word "small" at the end of the sentence, many thanks. Line 137: thank you for the correction. Line 213: yes, you are right. Many thanks for helping us improve the quality of the manuscript.

E. 142: yes, you are right, we will fix this, which will harmonize the result with the version provided in the main paper. Idem for F12/F15. Once again, we *thank you8 warmly for your efforts in reading our main paper and appendix carefully. We stand ready to answer any further questions as required.

Re question 1 "is the bound larger than the test error": we appreciate your observation based on the axes of the graph. Yes, like most comparable works, the bounds are vacuous at realistic scales if we do not apply further tricks (e.g. compression, data dependent priors, aggressive optimization of the bound through additional spectral regularization). We wanted to compare how all bounds vary with architectural parameters in a reasonable simple pure uniform convergence setting which excludes applying too many post-processing tricks to make the bounds tighter. Our reasoning is that the numerical values of generalization bounds are not as important as how they behave when the architecture changes. Indeed, numerically tighter estimates of the test error can be obtained with a validation set. Our bounds demonstrate the validity of the approximate rank as a complement to margins [3,5] as a measure of unused function class capacity.

Re question 2: "route to non-vacuous bounds": yes, we believe it is possible to achieve non-vacuous bounds with more aggressive tricks. For instance, the bounds for the fully connected case are not far from being non vacuous if one ignores logarithmic factors. They may become non-vacuous if we were to tweak the architecture, explicitly compress the rank by removing higher order singular values, and apply spectral norm constraints. In addition, incorporating PAC-Bayesian techniques, including data-dependent priors [7,9,10] into our analysis is a tantalizing direction for future research with the potential for non-vacuous results. However, we wanted to limit our setup to uniform convergence as closely as possible to provide a fair proof of concept. We hope and believe our contributions are a sufficient component to warrant one publication, without having to combine it to even more other techniques to make the bounds numerically tighter, as we believe doing so would make the paper even less approachable to readers and reviewers.

On a side note, we would also like to point out that it is very difficult, if not impossible, to compare all bounds in the literature without ignoring logarithmic factors and constants. Indeed, many works (e.g. [2]) skip constants entirely, and many works (e.g. [2,3]) do not explicitly write down the proof of the post hoc step, leaving it as an exercise for the reader. This makes a comparison with our theorem E.2. unfair if one includes the logarithmic factors arising from the numerous post hoc steps over $s\_{\ell}, p\_{\ell}, \mathcal{M}\_{\ell},$ etc.

Once again, we thank you for your appreciation of our work and look forward to our further discussion with you.

============================Continuation of Answer to Reviewer 9AFC======================

Many thanks for your detailed comments. We appreciate the constructive suggestion of a proof sketch and the corrections of the typos found in the appendix. We promise to fix all of these typos and suggestions, including introducing a footnote at line 38. We also promise to cite and discuss [6] as requested. Re Line 115, we will remove the initialized matrices $M_\ell$ from the introduction to improve clarity. Many thanks. Re 250, both equation (2) and Neyshabur et al. refer to the same result, we will clarify this and fix the sentence. Re 285/266: many thanks, we will harmonize both notations by removing the initialized matrices $M\_{\ell}$ from the introduction.

Re dependency on the input space dimension:/possibility to remove the dependence on the input dimension or the hidden layer.

Many thanks for your comment, which is closely related to reviewer wqbT's insightful question 1. For the one layer case, we agree that our results translate to a sample complexity of at least $[m+d]$ where $d$ is the input dimension. This is a weakness compared to the purely norm-based bounds in [4,5], which only involve the Frobenius norm of the weights. In particular, even for $p=2$, the bound doesn't coincide with [4,5]. To the best of our knowledge, this limitation is extremely challenging to remove (we invite the reviewers to check the argument involving Markov's inequality in the proof sketch of Prop F2 to satisfy themselves that no simple modification of the technique can improve this). However, this limitation doesn't make our results uniformly inferior to either norm-based or parameter counting bounds.

We want to clarify that when we claim it could be possible to improve the dependence on the input dimension, we mean to achieve this under the assumption that the input samples approximately lie in a low-rank subspace. Similarly, taking into account the fact that activations approximately lie in a low-rank subspace may also allow us to further improve the dependency. However, these as-yet uncertain improvements require very significant technical modifications to the proofs which are better left to future work.

Cf answer to rev. wqbT for further details on these last questions.

We thank you again for your interest in our work and are looking forward to our further discussion.

=================================References===========================

[1] Ledent, A.; Alves, R. Generalization Analysis of Deep Non-linear Matrix Completion. ICML 2024.

[2] Long, P. M.; Sedghi, H. Generalization Bounds for Deep Convolutional Neural Networks. ICLR 2020.

[3] Graf, F.; Zeng, S.; Rieck, B.; Niethammer, M.; Kwitt, R. On Measuring Excess Capacity in Neural Networks. NeurIPS 2022.

[4] Zhang, T. Covering Number Bounds of Certain Regularized Linear Function Classes. JMLR 2002.

[5] Bartlett, P. L.; Foster, D. J.; Telgarsky, M. Spectrally-Normalized Margin Bounds for Neural Networks. NeurIPS 2017.

[6] Suzanna Parkinson, Greg Ongie, Rebecca Willett. ReLU Neural Networks with Linear Layers are Biased Towards Single- and Multi-Index Models

[7] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, Daniel M. Roy. On the role of data in PAC-Bayes bounds

[8] Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Deep linear networks dynamics: Low-rank biases induced by initialization scale and l2 regularization. https://arxiv.org/abs/2106.15933v1

[9] Zhou, Wenda, et al. "Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach."

[10] Biggs, Felix, and Benjamin Guedj. "Non-vacuous generalisation bounds for shallow neural networks." International Conference on Machine Learning. PMLR, 2022.

[11] Neyshabur, Bhojanapalli, Srebro. A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks. ICLR 2018.