Weaknesses
First, I should stress that I read this paper with great enthusiasm and excitement for the results that it promised in the title and abstract. However, it is my opinion that the biggest weaknesses of this paper are the soundness of their main results. I expand on this at length below but, in nutshell, some are simple corollaries of known results, others are new but unable to convey any useful information, and others have potentially some important technical problems. I'm hoping that my understanding is amiss, and that the authors can correct my observations below. For the same reason, don't put much (or any) importance on my rating of the paper for now, as this will completely depend on the authors' responses and discussions, which I look forward to.
Questions
1. **Theorem 4.1 and implications**
Th. 4.1 shows that, for the unconstrained feature model (Zhu et al, 2021), trained with cross entropy loss (Eq 1), if the loss tends to 0, then the margin on the training set tends to infinity.
This result is very similar to previous results (Soudry et al, 2018; Ji & Telgarsky 2019) which show that gradient descent on separable data converges to a max margin classifier and to the global minimum of the training problem. Note: these results provide a much tighter analysis as they provide convergence rates, also. The results in 4.1 is not exactly the same, as here the authors talk about gradient flow instead of gradient descent, but I would happily argue that the latter is significantly more relevant as it is what is actually computed in practice. Furthermore, note that the only reason that the margin in Thm 4.1 diverges to infinity is because the authors consider the un-normalized margin, and the classifier diverge in norm. Thus, in light of these previous results, I don't see what novelty Th4.1 provides.
2. **Theorem 4.4 and implications**
This result, which is one of the two main results of this paper, provides a bound on the risk of the classifier $F(x) = \arg\max M f(x,w)$, where $f(x,w)$ is a representation computed by some deep network. The bound depends on the empirical margin risk, as well as a generalization gap bound based on the Radamacher complexity of the function class (plus a term that ensure that the bound holds uniformly for any margin). In particular, this gap is $\tilde{\mathcal O}(\mathfrak R(\mathcal F))/\gamma$, where $\gamma$ is the required/observed margin.
I have a few comments on this result:
* i) The hypothesis/function class is defined as $\mathcal F$ is defined for all $M$ and $w$ in their respected spaces. Thus, as defined, $K$ is unbounded (unless $f$ is trivial/useless) because this allows for $||M||\to\infty$, or for $||f(x,w)||\to\infty$ because either $||w||\to\infty$ or even because $||x||\to\infty$ (since we don't even know if $\mathcal X$ is unbounded). So, all of these should be put in place.
* ii) A main concern I have is that this results is nothing else than a standard margin bound; see e.g. Theorem 5.9. in (Mohi et al, "Foundations of Machine Learning", 2018). The only difference here is the muti-class setting, but these are also standard/direct extensions.
* iii) A second main concern with this results is that, while the characterization of the margin in the last layer is fine (and, as per the previous point, known), everything naturally hinges on the Radamacher complexity of the function class, $\mathfrak R(\mathcal F)$. Now, in their Remark 4.6, the authors explain that this result (Thm 4.4, or Corollary 4.5: ``The reason for generalization improvement when NC emerges") explains the improvements in generalization because the margin increases (i.e. $\gamma_{i,j}\geq p_{min}$), thus decreasing the term $\tilde{\mathcal O}(\mathfrak R(\mathcal F))/\gamma$. However, in this setting of bounded parameter spaces, the margin cannot increase indefinitely (as it can in the unconstrained feature model/linear regression setting of Thm 4.1). Moreover, the increase in margin will naturally come at the expense of increasing the complexity of the function class, i.e. increasing $\tilde{\mathcal O}(\mathfrak R(\mathcal F))$. This trade-off is not knew, and indeed all results that use margin theory to provide generalization bounds for deep nets rely on characterizing and controlling this trade-off most effectively. Such a trade-off depends typically on the different norms of the parameters $w$; the authors might want to look at refs (A,B) in detail. As a result, without telling us how $\tilde{\mathcal O}(\mathfrak R(\mathcal F))$ varies with the obtained $\gamma$, this results says nothing new and it certainly does not explain or demystify why networks generalize well during neural collapse.
3. **Theorem 4.8**
This theorem attempts to provide a generalization bound relying on the covering number of the support of the data for a Lipschitz continuous $f(\cdot,w)$, basically providing $\mathbb P (\text{missclassification}) \leq \frac{1}{2N}\sum_y \max_{y'\not y}\mathcal N(\epsilon,\mathcal M_y)$ where the resolution $\epsilon = \gamma_{y,y'}/(L||M_y - M_{y'}||)$.
* i) Again, $L$ might be unbounded if the hypothesis space is unbounded.
* ii) In remark 4.9 the authors attempt to explain how this results might be able to explain why different models with similar collapse have the different risks. In particular, the authors write that permuting $\hat\gamma_{i,j}$ to $\hat\gamma_{\pi(i),\pi(j)}$, which might differ under approximate collapse, might result in different upper bounds on the risk. This is interesting, but the proposed covering number (as presented) is not computable and, as the authors mention, the number of data points required would depend exponentially on the dimension.
4. **Theorem 4.10**
In order to alleviate the shortcomings of Thm 4.8, here the authors provide an improved results which seems to show that the risk decays exponentially fast with the number of samples.
* i) Again, note that $\rho$ might be unbounded.
* ii) My main observation here is that I don't think this result is correct: the authors employ a tail bound (Hoeffding's) on the learned features but, unfortunately, Hoeffding's requires samples to be i.i.d for concentration. More specifically, looking at their proof, page 19, they write:
$\mathbb P_{S_y}( || \hat{\mu}_y - \mu_y || \geq \epsilon ) \leq 2d \exp(-n\epsilon^2 / 2d^2\rho^2_y)$
where
$\hat{\mu_y} = \frac{1}{N_y} \sum_{x_j \in S_y} f(x_j,w)$ and $\mu_y = \mathbb E \hat{\mu}_y$.
However, the samples $f(x_j,w)$ that are empirically averaged need to be independent, and they *are not* independent because $w$ depends on the sample $S$. More generally, this is the reason why concentration bounds are not sufficient to provide generalization bounds.
---
References:
A: Bartlett, Peter L., Dylan J. Foster, and Matus J. Telgarsky. "Spectrally-normalized margin bounds for neural networks." Advances in neural information processing systems 30 (2017).
B: Wei, Colin, and Tengyu Ma. "Improved sample complexities for deep neural networks and robust classification via an all-layer margin." International Conference on Learning Representations. 2019.
---
**Minor comments**
* CE in abstract is undefined.
* first sentence of second paragraph: "physics" -> "mechanisms"? there's really no physics here.
* Thm 4.4: "uppder" -> "upper".
* Thm 4.8: what does "tight" support mean? Did you mean bounded?
* Right before the discussions, the authors mention an interesting connection to sparsity and its role in generalization. I wonder if the authors believe that their intuition could be related to the work in (Muthukumar et al. "Sparsity-aware generalization theory for deep neural networks." COLT, 2023)