Towards Demystifying the Generalization Behaviors When Neural Collapse Emerges

as mentioned in the weakness part

The paper is clearly written and I have no questions.

1. Theorem 4.10 depends on less strict assumptions and has a better convergence rate than Theorem 4.8, is there any practical benefit of Theorem 4.8 on top of Theorem 4.10? Because otherwise why not just delete Theorem 4.8?
2. In Figure 3, it seems like $p_{min}$ is smaller than 0 for the CIFAR-100 dataset even at the end of the training, does this mean the training accuracy is not reaching 100%?
3. In Section 5.2, the paper talks about the influence of permutation/rotation of the Simplex ETF on the test results, is there an optimal configuration, perhaps a specific permutation or rotation, that consistently delivers the highest test accuracy?

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)