Neural collapse vs. low-rank bias: Is deep neural collapse really optimal?

Authors: peter  súkeník
christoph  lampert
marco  mondelli
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 16:13:56

Abstract: Deep neural networks (DNNs) exhibit a surprising structure in their final layer known as neural collapse (NC), and a growing body of works is currently investigated the propagation of neural collapse to earlier layers of DNNs -- a phenomenon called deep neural collapse (DNC). However, existing theoretical results are restricted to either linear models, the last two layers or binary classification. In contrast, we focus on non-linear models of arbitrary depth in multi-class classification and reveal a surprising qualitative shift. As soon as we go beyond two layers or two classes, DNC stops being optimal for the deep unconstrained features model (DUFM) -- the standard theoretical framework for the analysis of collapse. The main culprit is the low-rank bias of multi-layer regularization schemes. This bias leads to optimal solutions of even lower rank than the neural collapse. We support our theoretical findings with experiments on both DUFM and real data, which show the emergence of the low-rank structure in the solution found by gradient descent.

Main paper: 
 introduction: 
 What is the geometric structure of layers and learned representations in deep neural networks (DNNs)? To address this question, Papyan et al. [39] focused on the very last layer of DNNs at convergence and experimentally measured what is now widely known as Neural Collapse (NC). This phenomenon refers to four properties that simultaneously emerge during the terminal phase of training: feature vectors of training samples from the same class collapse to the common class-mean (NC1); the class means form a simplex equiangular tight frame or an orthogonal frame (NC2); the class means are aligned with the rows of the last layer's weight matrix (NC3); and, finally, the classifier in the last layer is a nearest class center classifier (NC4). Since the influential paper [39] , a line of research has aimed at explaining the emergence of NC theoretically, mostly focusing on the unconstrained features model (UFM) [36] . In this model, motivated by the network's perfect expressivity, one treats the last layer's feature vectors as a free variable and explicitly optimizes them together with the last layer's weight matrix, "peeling off" the rest of the network [9, 23] . With UFM, the NC was demonstrated in a variety of settings, both as the global optimum and as the convergence point of gradient flow.The emergence of the NC in the last layer led to a natural research question -does some form of collapse propagate beyond the last layer to earlier layers of DNNs? A number of empirical works [20, 17, 43, 40, 35] gave evidence that this is indeed the case, and we will refer to this phenomenon as Deep Neural Collapse (DNC). On the theoretical side, the optimality of the DNC was obtained (i) for the UFM with two layers connected by a non-linearity in [51] , (ii) for the UFM with several linear layers in [7] , and (iii) for the deep UFM (DUFM) with non-linear activations in the context of binary classification [48] . No existing work handles the general case in which there are multiple classes and the UFM is deep and non-linear.In this work, we close the gap and reveal a surprising behavior not occurring in the simpler settings above: for multiple classes and layers, the DNC as formulated in previous works is not an optimal solution of DUFM. In particular, the class means at the optimum do not form an orthogonal frame (nor an equiangular tight frame), thus violating the second property of DNC.Let L and K denote the number of layers and classes, respectively. Then, if either L ≥ 3 and K ≥ 10 or L ≥ 4 and K ≥ 6, we provide an explicit combinatorial construction of a class of solutions that outperforms DNC. Specifically, the loss achieved by our construction is a factor K (L-3)/(2L+2) lower than the loss of the DNC solution. Our result holds as long as all matrices are regularized.We also identify the reason behind the sub-optimality of DNC: a low-rank bias. Intuitively, this bias arises from the representation cost of a DNN with l 2 regularization, which equals the Schatten-p quasi norm [37] in the deep linear case. The quasi norm is well approximated by the rank, and this intuition carries over to the non-linear case as well. In fact, the rank of our construction is Θ( √ K), while the rank of the DNC solution is K. We note that after the application of the ReLU, the rank of the final layer is again equal to K, in order to fit the training data. We also show that the first property of neural collapse (convergence to class means) continues to be strictly optimal even in this general setting and its deep counterpart is approximately optimal with smoothed ReLU activations.We support our theoretical results with empirical findings in three regimes: (i) DUFM training, (ii) training on standard datasets (MNIST [31] , CIFAR-10 [28] ) with DUFM-like regularization, and (iii) training on standard datasets with standard regularization. In all cases, gradient descent retrieves solutions with very low rank, which can exhibit symmetric structures in agreement with our combinatorial construction, see e.g. the lower-right plot of Figure 4 . We also investigate the effect of three common hyperparameters -weight decay, learning rate and width -on the rank of the solution at convergence. On the one hand, high weight decay, high learning rate and small width lead to a strong low-rank bias. On the other hand, small (yet still non-zero!) weight decay, small learning rate or large width (and more complex datasets as well) lead to a higher-rank solution, even if that is not the global optimum, and this solution often coincides with DNC, which is in agreement with earlier experimental evidence. Altogether, our findings show that if a DNC solution is found, it is not because of its global optimality, but just because of an implicit bias of the optimization procedure.The implications of our results go beyond deep neural collapse. In fact, our theory suggests that even the NC2 in the last layer is not optimal, and this is corroborated by our experiments, where the singular value structure of the last layer's class-mean matrices is imbalanced, ruling out orthogonality. This means that standard single-layer UFM, as well as its deep-linear or two-layer extensions, are not sufficient to describe the full picture, as they display a qualitatively different phenomenology. 
related work: 
 Neural Collapse. Several papers (a non-exhaustive list includes [12, 15, 5, 32, 33, 58] ) use neural collapse as a practical tool in applications, among which OOD detection and transfer learning are the most prevalent. On the theoretical side, the emergence of NC has been investigated, with the majority of works considering some form of UFM [36, 9] . [55, 34] show global optimality of NC under the cross-entropy (CE) loss, and [59] under the MSE loss. Similar results are obtained by [9, 49, 18, 8] for the class-imbalanced setting. [61, 23, 59 ] refine the analysis by showing that the loss landscape of the UFM model is benign -all stationary points are either local minima or strict saddle points which can be escaped by conventional optimizers. A more loss-agnostic approach connecting CE and MSE loss is considered in [60] . NC has also been analyzed for a large number of classes [25] , in an NTK regime [45] , or in graph neural networks [27] . We refer the reader to [26] for a survey.The emergence of NC has also been studied through the lens of the gradient flow dynamics. [36] considers MSE loss and small initialization, and [16] a renormalized gradient flow of the last layer's features after fixing the last layer's weights to be conditionally optimal. [23] studies the CE loss dynamics and shows convergence in direction of the gradient flow to a KKT point of the max-margin problem of the UFM, extending a similar analysis for the last layer's weights in [47] . The convergence speed under both losses is described in [53] . Going beyond UFM, [57, 41, 42, 29] study the emergence of NC in homogeneous networks under gradient flow; [38] provides sufficient conditions for neural collapse; and [52] perturbs the unconstrained features to account for the limitations of the model. More recently, [20] mentions a possible propagation of the NC to earlier layers of DNNs, giving preliminary measurements. These are then significantly extended in [17, 43, 11, 40] , which measure the emergence of some form of DNC in DNNs. On the theoretical front, an extension to a two-layer non-linear model is provided in [51] , to a deep linear model in [7, 14] and to a deep non-linear model for binary classification in [48] . Alternatively to DUFM, [4] studies DNC in an end-to-end setting with a special layer-wise training procedure.Low-rank bias. The low-rank bias is a well-known phenomenon, especially in the context of matrix/tensor factorization and deep linear networks (see e.g. [2, 6, 44, 24, 54] ). For non-linear DNNs, [50] studies the gradient flow optimization of ReLU networks, giving lower and upper bounds on the average soft rank. [13] studies SGD training on deep ReLU networks, showing upper bounds on the rank of the weight matrices as a function of batch size, weight decay and learning rate. [30] proves several training invariances that may lead to low-rank, but the results require the norm of at least one weight matrix to diverge and the architecture to end with a couple of linear layers. [3] presents bounds on the singular values of non-linear layers in a rather generic setting, not necessarily at convergence. More closely related to our work is [37] , which considers a deep linear network followed by a single non-linearity and then by a single layer. Their arguments to study the low-rank bias are similar to the intuitive explanation of Section 4. [19] shows that increasing the depth results in lower effective rank of the penultimate layer's Gram matrix both at initialization and at convergence. The true rank is also measured, but on rather shallow networks and it is far above the DNC rank. [1] shows a strong low-rank bias of sharpness-aware minimization, although only in layers where DNC does not yet occur and the rank is high. [10, 22] study special functional ranks (Jacobi and bottleneck) of DNNs, providing asymptotic results and empirical measurements. These results are refined in [21, 56] , which show a bottleneck structure of the rank both experimentally and theoretically. The measurements of the singular values at convergence in [56] are in agreement with those of Section 6.3. We highlight that none of the results above allows to reason about DNC optimality, as they focus on infinite width/depth, effective or functional ranks, orthogonal settings, or are not quantitative enough. 
preliminaries: 
 We study the class balanced setting with N = Kn samples from K classes, n per class. Let f (x) = W L σ(W L-1 σ(. . . W 1 B(x) . . . )) be a DNN with backbone B(•). The backbone represents the majority of the deep network before the last L layers, e.g. the convolutional part of a ResNet20. Let X ∈ R d×N be the training data, andH 1 = B(X) ∈ R d1×N , H 2 = σ(W 1 H 1 ) ∈ R d2×N , . . . , H L = σ(W L-1 H L-1 ) ∈ R d L ×Nits feature vector representations in the last L layers, with Hl denoting their counterparts before applying the ReLU σ. We refer to h l ci and hl ci as to the i-th sample of c-th class of H l and Hl , respectively. Letµ l c = 1 n n i=1 h l ci and μl c = 1 n n i=1hl ci be the class means at layer l after and before applying σ, and M l , Ml the matrices of the respective class means stacked into columns. We organize the training samples so that the labels Y ∈ R K×N equal I K ⊗ 1 T n , where I K is a K × K identity matrix, ⊗ is the Kronecker product and 1 n the all-one vector of size n.As there are no biases in our network model, the second property of DNC requires the class mean matrices to be orthogonal (instead of forming an ETF) [43, 48] . Definition 1. We say that layer l exhibits DNC 1, 2 or 3 if the corresponding conditions are satisfied (the properties can be stated for both after and before the application of ReLU): DNC1: The within-class variability of either H l or Hl is 0. Formally,h l ci = h l cj , hl ci = hl cj for all i, j ∈ [n] or, in matrix notation, H l = M l ⊗ 1 T n , Hl = Ml ⊗ 1 T n . DNC2: The class-mean matrices M l , Ml are orthogonal, i.e., M T l M l ∝ I K , M T l Ml ∝ I K . DNC3:The rows of the weight matrix W l are either 0 or collinear with one of the columns of the class-means matrix M l .Deep unconstrained features model. To define DUFM, we generalize the model in [48] to an arbitrary number of classes K.Definition 2. The L-layer deep unconstrained features model (L-DUFM) denotes the following optimization problem:EQUATIONwhere ∥•∥ F denotes the Frobenius norm and λ H1 , λ W1 , . . . , λ W L > 0 are regularization parameters.4 Low-rank solutions outperform deep neural collapseIntuitive explanation of the low-rank bias. Consider a simplified version of L-DUFM:EQUATIONCompared to (1), ( 2) removes all non-linearities except in the last layer, making the remaining part of the network a deep linear model, a construction similar to the one in [37] . Now, we leverage the variational form of the Schatten-p quasi-norm [46] , which givesc HL 2/L S 2/L = min H1,W1,...,W L-1 :H1W1...W L-1 = HL L-1 l=1 λ W l 2 ∥W l ∥ 2 F + λ H1 2 ∥H 1 ∥ 2 F ,where c can be computed explicitly. Thus, after solving for H 1 , W 1 , . . . , W L-1 , the simplified L-DUFM problem (2) can be reduced tomin HL W L 1 2N W L σ( HL ) -Y 2 F + λ W L 2 ∥W L ∥ 2 F + λ HL 2 HL 2/L S 2/L .For large values of L, HL2/L S 2/Lis well approximated by the rank of HL . Hence, the objective value is low when the output W L H L fits Y closely, while keeping HL low-rank, which justifies the low-rank bias. Crucially, the presence of additional non-linearities in the L-DUFM model (1) does not change this effect much, as long as one is able to define solutions for which most of the intermediate feature matrices Hl are non-negative (so that ReLU does not have an effect).Low-rank solution outperforming DNC. We define the combinatorial solution that outperforms DNC, starting from the graph structure on which the construction is based. Definition 3. A triangular graph T n of order n is a line graph of a complete graph K n of order n.T n has n 2 vertices, each representing an edge of the complete graph, and there is an edge between a pair of vertices if and only if the corresponding edges in the complete graph share a vertex. Moreover, let T n be the normalized incidence matrix of K n , i.e., (T n ) i,j = 1 √ n-1 if vertex i belongs to edge j and 0 otherwise. Let G n denote the adjacency matrix of T n .We recall that T n is a strongly regular graph with parameters (n(n -1)/2, 2(n -2), n -2, 4) and spectrum 2(n -2) with multiplicity 1, n -4 with multiplicity n -1 and -2 with multiplicity n(n -3)/2. Next, we construct an explicit solution (H 1 , W 1 , . . . , W L ) based on the triangular graph. For ease of exposition, we focus on the case where the number of classes K equals r 2 for some r ≥ 4, deferring the general definition to Appendix A.1. Definition 4. Let K = r 2 for r ≥ 4. Then, a strongly regular graph (SRG) solution of the L-DUFM problem (1) is obtained by setting the matrices (H 1 , W 1 , . . . , W L ) as follows:• For all l, the feature matrices H l , Hl are DNC1 collapsed, i.e.,H l = M l ⊗ 1 T n , Hl = Ml ⊗ 1 T n .• For 2 ≤ l ≤ L -1, M l = Ml , each row of Ml is a non-negative multiple of a row of T r (as in Definition 3), and the sum of squared norms of the rows of Ml corresponding to a row of T r is the same for each row of T r . Since Ml is entry-wise non-negative, M l = Ml .• For l = 1, W 1 , M 1 are any pair of matrices minimizing the objective conditionally on M 2 defined above. • For l ≥ 2, W l minimizes the objective conditional to input and output to that layer.• As for the last layer L, let A L be a K × r matrix where the set of rows equals the set of vectors with two (-1) entries and r -2 (+1) entries. Then, M L = σ( ML ), the rows of ML are a non-negative multiple of A L T r , and the sum of their squared norms corresponding to either row of A L T r is equal.• Finally, the Frobenius norms (i.e. scales) of M 1 , W 1 , . . . , W L are chosen so as to minimize (1) while satisfying the construction above.In this construction, columns and rows of class-mean matrices are associated to edges and vertices of the complete graph K r . Each row (corresponding to a vertex) has non-zero entries at columns that correspond to edges containing the vertex. In the final layer, each row of ML corresponds to a weighting of vertices in K r s.t. exactly two vertices get -1 weight and the rest +1, and the value at a column is the sum of the values of the vertices of the edge. The class-mean matrices of the SRG solution are illustrated in Figure 1 Let us highlight the properties of the SRG solution, which are crucial to outperform DNC. First, the rank of the intermediate feature and weight matrices is very low, only of order Θ(K 1/2 ), since by construction there are only r = Θ(K 1/2 ) linearly independent rows. This is contrasted with the DNC solution that has rank K in all intermediate feature and weight matrices. The low rank of the SRG solution is due to the specific structure of the triangular graph, which has many eigenvalues equal to -2 that become 0 after adding twice a diagonal matrix. Second, the definition of ML ensures that M L = σ( ML ) has full rank K. This allows the output W L M L to also have full rank and, therefore, fit the identity matrix I K , thus reducing the first term in the loss (1) . Finally, the highly symmetric nature of the SRG solution balances the feature and weight matrices so as to minimize large entries and, therefore, the Frobenius norms, thus reducing the other terms in the loss (1).Main result. For any L-DUFM problem (specified by K, n and all the regularization parameters), let L SRG , L DN C be the losses incurred by the SRG and DNC solutions, see Definitions 4 and 1, respectively. At this point we are ready to state our key result. Theorem 5. If K ≥ 6, L ≥ 4 or K ≥ 10, L = 3 and d l ≥ K for all l, then L SRG < L DN C . Moreover, consider any sequence of L-DUFM problems for which K -→ ∞ so that 0.499 > L DN C for each problem. In that case,EQUATIONIn words, as long as the number of classes and layers is not too small, the SRG solution always outperforms the collapsed one and the gap grows with the number of classes K.The proof first computes the conditionally optimal values of ∥W l ∥ 2 F for both the SRG and DNC solutions. The specific structure of these solutions enables to calculate pseudoinverses of the intermediate features, thus enabling the explicit computation of the weight norms. All these values depend only on the singular values of the feature matrices, which are explicitly given by their scale. As a result, both L SRG and L DN C are expressed via an optimization problem in a single scalar variable and, by comparing these problems, the statement follows. The details are deferred to Appendix A.1.Although the argument requires L = 3, K ≥ 10 or L ≥ 4, K ≥ 6, the experiments in Appendix B.1 show that the DNC solution is not optimal when L ≥ 4, K ≥ 3 or L = 3, K ≥ 7. Furthermore, for L = 3 and large K, there is a large gap between L SRG and L DN C (even if (3) trivializes). For either K = 2 or L = 2, the DNC is optimal, as shown in [51, 48] . 
within-class variability collapse is still optimal: 
 While the DNC2 property conflicts with the low-rank bias, the same is not true for DNC1, as the within-class variability collapse supports a low rank. We show below that the last-layer NC1 property remains optimal for any L-DUFM problem. A proof sketch follows, with the complete argument deferred to Appendix A.2. Theorem 6. The optimal solutions of the L-DUFM (1) exhibit DNC1 at layer L, i.e.,H * L = M * L ⊗ 1 T n holds for any optimal solution (H * 1 , W * 1 , . . . , W * L ) of the L-DUFM problem.Proof sketch: Assume by contradiction that there exists an optimal solution of (1) with regularization parameters (λ H1 , λ W1 , . . . , λ W L ), denoted as (H * 1 , W * 1 , . . . , W * L ), which does not exhibit neural collapse at layer L. Then, we can construct two different optimal solutions of the L-DUFM problem with n = 1 and regularization parameters (nλ H1 , λ W1 , . . . , λ W L ) of the form (H(1) 1 , W * 1 , . . . , W * L ) and (H (2) 1 , W * 1 , . . . , W * L ). These two solutions share the weight matrices, and H 1 (and, therefore, H L ) only differs in a single column (w.l.o.g., the first column). The optimality of these solutions can be proved using separability and symmetry of the loss function w.r.t. the columns of H 1 .L and H(2)L as x and y, respectively. By exploiting the linearity of the loss function on a ray {th 1 11 , t ≥ 0} for any h 1 11 , a direct computation gives that x and y are not aligned. Let L be the loss in (1) . By optimality of both solutions, we getEQUATIONAn application of the chain rule gives∂L ∂W L = ∂L F ∂ HL+1 ∂ HL+1 ∂W L + λ W L W L = ∂L F ∂ HL+1 H T L + λ W L W L ,where HL+1 is the model output and L F the first term of L, corresponding to the label fit. Plugging this back into (4) and using that W * L is the same in both expressions, we get A(HEQUATIONL ) T , where we have denoted by A and B the partial derivatives ∂L F ∂ HL+1 evaluated at (H(1) 1 , W * 1 , . . . , W * L ) and (H (2)1 , W * 1 , . . . , W * L ), respectively. As L F is separable with respect to the columns of H l , Hl for all l, the matrices A, B can only differ in their first columns (denoted by a, b), and they are identical otherwise. This implies that ax T = by T . After some simple considerations and using that x and y are not aligned, we reach a contradiction, as we conclude that x ̸ = y is impossible.The difficulty in extending Theorem 6 to a result on the unique optimality of DNC1 for all layers stems from the special role of W L as the loss is differentiable w.r.t. it. By considering a differentiable relaxation of ReLU, we show below an approximate result for a relaxed L-DUFM model. Definition 7. We denote by ReLU ϵ (or σ ϵ ) a function satisfying the following conditions: (i) σ ϵ (x) = σ(x), for x ∈ (-∞, 0] ∪ [ϵ, ∞), (ii) 0 < σ ϵ (x) < σ(x) for x ∈ (0, ϵ), and (iii) σ ϵ is continuously differentiable with derivative bounded by a universal constant and strictly positive on (0, ϵ). Theorem 8. Denote by L-DUFM ϵ the equivalent of (1), with σ replaced by σ ϵ . Let D = max{d 2 , d 3 , . . . , d L } and λ = λ H1 λ W1 . . . λ W L , with the regularization parameters upper bounded by 1/(L + 1). Then, for any globally optimal solution of the L-DUFM ϵ problem, the distance between any two feature vectors of the same class in any layer is at mostEQUATIONIn words, as the activation function approaches ReLU (i.e., ϵ → 0), the within-class variability tends to 0. The proof starts with a similar strategy as the argument of Theorem 6 and then explicitly tracks the error due to replacing σ with σ ϵ through the layers. The full argument is in Appendix A.2. 
numerical results: 
 We employ the standard DNC1 metric tr(Σ W )/tr(Σ B ), where Σ W , Σ B are the within and between class variabilities. This is widely used in the literature [52, 43, 4] and considered more stable than other metrics [43] . We measure the DNC2 metric as the condition number of M l for l ≥ 1 [48] .We do not measure DNC3 here, as it is not well-defined for solutions that do not satisfy DNC2.For end-to-end DNN experiments, we employ a model from [48] where an MLP with a few layers is attached to a ResNet20 backbone. The output of the backbone is then treated as unconstrained features, and DNC metrics are measured for the MLP layers.We start with the L-DUFM model ( 1), training both features and weights. In the top row of Figure 2 , we consider a 4-DUFM, with K = 10 and n = 50, presenting the training progression of the losses (left plot), the DNC1 metrics (center plot) and the singular values at convergence (right plot).The results are in excellent agreement with our theory. First, the training loss outperforms that of the DNC solution, and it is rather close to that of the SRG solution. Second, DNC1 holds in a clear way in all layers, especially in the last ones. Third, the solution at convergence exhibits a strong low rank bias: the ranks of intermediate layers range from 5 to 8, and they are always the same in all intermediate layers within one run. For comparison, we recall that the intermediate layers of the DNC solution have full rank K = 10. Third, for a few runs, the Gram matrices of the intermediate class means resulting from gradient descent training coincide with those of an SRG solution. Finally we highlight that, similarly to our theory, the solutions found in all our experiments in the entire Section 6 have non-negative pre-activations in all intermediate layers of the MLP head except the last one.Impact of number of classes and depth. For K = 2 or L = 2, we recover the results of [48, 51] irrespective of other hyperparameters. The higher the number of classes, the more prevalent are lowrank solutions, while finding DNC solutions becomes challenging. The same holds for increasing the number of layers. For L = 3 and low number of classes (K ≤ 6), we weren't able to experimentally find solutions that would outperform DNC, which aligns nicely with the fact that SRG outperforms DNC only from K = 10 for L = 3. For large number of classes, the difference between the loss of low-rank solutions and the DNC loss is considerable already for L = 3 and becomes even larger for higher L. This is illustrated in the left plot of Figure 3 .For L ≤ 5 and moderate number of classes (K ≤ 30), gradient descent solutions are as follows: until layer L -1, feature matrices share the same rank and have similar Gram matrices; intermediate activations are typically non-negative, and the ReLU has no effect; then, the rank jumps to K after the final ReLU, as pre-activations are also negative. For large L or large K, the rank of the first few layers is low, growing gradually in the last couple of layers (see Figure 6 in Appendix B.1); the ReLU is active only in the final layers. This means that not only very low-rank solutions outperform DNC (as shown by our theory), but such solutions are routinely reached by gradient descent.Impact of weight decay and width. While neither weight decay nor width influence Theorem 5which shows that DNC is not optimal -both quantities influence the nature of the solutions found by gradient descent. In particular, the stronger the weight decay, the lower the rank, see the middle plot in Figure 3 . For very small weight decay, DNC is sometimes recovered; for very high weight decay, it is never recovered. The width has an opposite effect, see the right plot of Figure 3 . For small width, low-rank solutions are much more likely to be found; large width has a strong implicit bias towards DNC and, thus, rank K solutions. This means that, surprisingly, a larger width leads to a larger loss, since low-rank solutions exhibit a smaller loss than DNC. Thus, at least in DUFM, the infinite-width limit prevents gradient descent from finding a globally optimal solution, and sub-optimal solutions are reached with increasingly high probability.Next, we train a DNN backbone with an MLP head, regularizing only the output of the backbone and the layers of the MLP head (and not the layers of the backbone). This regularization is closer to our theory than the standard one, since we explicitly regularize the Frobenius norm of the unconstrained features. We also note that training with such a regularization scheme is easier than training with the standard regularization scheme. In the bottom row of Figure 2 , we consider a ResNet20 backbone with a 4-layer MLP head trained on CIFAR10. The results agree well with our theory, and they are qualitatively similar to those of Section 6.1 for DUFM training. The DNNs consistently outperform the DNC loss, but still achieve DNC1. The ranks of class-mean matrices range from 5 to 6, and they are always the same in all intermediate layers within one run. Remarkably, the SRG solution was found by gradient descent also in this setting.Both weight decay and learning rate affect the average rank of the solutions found by gradient descent. Varying the width can lead to unexpected results, as it changes the ratio between the number of parameters in the MLP and that in the backbone, so the effect of the width is harder to interpret. Similar results can be seen on MNIST.Finally, we perform experiments with standard regularization and the same architecture (i.e., DNN backbone plus MLP head) as in Section 6.2. In particular, in Figure 4 we consider a ResNet20 backbone with a 5-layer MLP head trained on CIFAR10 and MNIST with standard weight regularization.Overall, the results remain qualitatively similar to those discussed above. This demonstrates that, in spite of a different loss landscape compared to previous settings, the low-rank bias is still responsible for DNC2 not being attained. Specifically, for CIFAR10, the rank in the third layer ranges between 8 and 9, and for MNIST ranges between 5 and 7; in contrast, the DNC solution has rank K = 10. All DNNs display DNC1 across all layers. Remarkably, for the MNIST experiment the solution displayed in Figure 4 found by gradient descent is the SRG solution (compare the gram matrices in bottom right plot of Figure 4 with the right-most plot of Figure 1 ).The difficulty of the learning task plays a significant role in this setting: when training on MNIST, it is rather easy to reach low-rank solutions and rather difficult to reach DNC solutions and the rank depends heavily on the regularization strength as shown in Figure 10 of Appendix B.3; when training on CIFAR-10, the weight decay needs to be high for the class mean matrices to be rank deficient. Moreover, the learning rate no longer exhibits a clear relation with the rank, since gradient descent diverges when the learning is too large. We also observe that the rank deficiency is the strongest in the mid-layer of the MLP head, creating a "rank bottleneck". This can be seen by a closer look at the tails of the singular values, which better match zero at intermediate layers (the green and red curves corresponding to layers 3 and 4 have tails slightly lower than the other curves). In a more precise manner, we further measured effective ranks of all the layers in Figure 4 . For instance, the effective ranks of CIFAR10 experiment layers are 8.96, 7.46, 6.88, 7.04, 7.73), which shows the middle layer is closest to a low hard rank matrix. The rank bottleneck is also mentioned in [22, 21, 56] . In fact, these works also measure extremely low ranks, but [22, 21] do it on synthetic data with very low inner dimension, while [56] focuses on fully convolutional architectures trained with CE loss and including biases. In summary, Figure 4 shows that both the low-rank bias and the optimality of DNC1 carry over to the standard training regime. This means that there are hyperparameter settings for which deep neural collapse, including in the very last layer, is not reached (and likely not even optimal). Although the sub-optimality of DNC in the last layer is not proved formally, this phenomenon is supported by evidence across all experimental settings and further corroborated by our theory where our SRG construction is far from being DNC2-collapsed in the last layer. 
conclusion: 
 In this work, we reveal that the deep neural collapse is not an optimal solution of the deep unconstrained features model -the extension of the widely used unconstrained features model. This finding considerably changes our overall understanding of DNC, as all the previous models in simplified settings showed the global optimality of neural collapse and of its deep counterpart. The main culpritthe low-rank bias -makes the orthogonal frame property of DNC, and thus DNC as a whole, too high rank to be optimal. We demonstrate this low-rank bias across a variety of experimental settings, from DUFM training to end-to-end training with the standard weight regularization. While the structure of the Gram matrices of class means is not captured by orthogonal matrices (or by the ETF), the within-class variability collapse remains optimal. Our theoretical analysis proves this for the DUFM problem, and our numerical results showcase the phenomenon across various settings.Our analysis focuses on the MSE loss, but we expect similar results to hold for the cross-entropy loss and, in particular, that the same SRG construction proposed here would still refute the optimality of DNC. We leave as an open question whether DNC1 is strictly optimal across all layers. While proving this would likely require new ideas, we note that none of our experiments converged to a solution that would not be DNC1-collapsed. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: no societal impact of the work performed Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We provide references for the datasets used.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We start by providing more detailed definitions of SRG and DNC solutions. Definition 9. Let K = r 2 for r ≥ 4. Then, a strongly regular graph (SRG) solution of the L-DUFM problem (1) is obtained by setting the matrices (H 1 , W 1 , . . . , W L ) as follows. For all l, the feature matrices H l , Hl are DNC1 collapsed, i.e.,H l = M l ⊗ 1 T n , Hl = Ml ⊗ 1 T n . For 2 ≤ l ≤ L -1, M l = Ml and M l = A l T r, where each row of A l is a multiple of the standard basis vector of dimension r and the sum of squared multiples corresponding to one basis vector equals the same parameter α l . In other words, each row of M l is a multiple of a row of T r and the sum of squared norms of the rows of M l corresponding to a row of T r is the same for each row of T r . For l = 1, W 1 , M 1 are any pair of matrices that minimize the objective conditionally on M 2 being defined as above. For l ≥ 2, W l minimizes the objective conditional to the input and output to that layer. Let A(1) L be a K × r matrix where each row has exactly two (-1) entries and exactly r -2 (+1) entries. Then, normalize the matrixA (1)L T r so that each row is unit norm and multiply from the left with A(2) L of dimension d L × K, where each of the rows of A(2) l is a multiple of a standard basis vector of dimension K and the total sum of squared multiples corresponding to each basis vector is α L . Then, ML is obtained via this procedure, and M L = σ( ML ). Finally, the parameters {α l } L l=2 satisfyEQUATIONand the parameter q ≥ 0 is chosen to minimize the objective function in (1). Definition 10. A deep neural collapse (DNC) solution for any number of classes K of the L-DUFM problem (1) is obtained by setting the matrices (H 1 , W 1 , . . . , W L ) as follows. For all l, the feature matrices H l , Hl are DNC1 collapsed, i.e., H l = M l ⊗ 1 T n , Hl = Ml ⊗ 1 T n . For 2 ≤ l ≤ L, M l = Ml and M T l M l = α l I K . For l = 1, W 1 , M 1 are any pair of matrices that minimize the objective conditionally on M 2 being defined as above. For l ≥ 2, W l minimizes the objective conditional to the input and output to that layer. Finally, the parameters {α l } L l=2 satisfyα l-1 = λ l-1 W L-1 λ H1 n l-1 i=1 λ Wi q l-1 , 2 ≤ l ≤ L -1, α L = λ L-1 W L-1 λ H1 n L-2 i=1 λ Wi q L ,and the parameter q ≥ 0 is chosen to minimize the objective function in (1) .Next, we define the SRG solution when K ̸ = r 2 for any r, and provide two constructions, each useful for different parts of the proof of Theorem 5. Definition 11. A strongly regular graph (SRG) solution for K ≥ 6 of the L-DUFM problem (1), is obtained in one of the two following ways.1. First, we take the largest r s.t. K ≥ r 2 and construct the SRG solution ( H1 , W1 , . . . , WL ) as in Definition 9 setting the number of classes to r 2 . Next, we construct a DNC solution ( H1 , W1 , . . . , WL ) as in Definition 10 setting the number of classes to K -r 2 . Then, to construct H 1 of the SRG solution, we create it as a diagonal block matrix with number of columns equal to K and number of rows equal to d1 + d1 , where these are the numbers of rows of the respective H matrices; the first block is H1 , the second block is H12 , and the off-diagonal blocks are zero matrices. Similarly, we extend the weight matrices such that, for any l, W l is a block diagonal matrix where the number of rows is dl+1 + dl+1 and the number of columns is dl + dl ; the first block is Wl , the second block is Wl , and the off-diagonal blocks are zero matrices.2. First, we take the smallest r s.t. K ≤ r 2 and construct the SRG solution as in Definition 9 setting the number of classes to r 2 . Then, we just remove the r 2 -K columns of H 1 that achieve the highest individual fit losses (in case of a tie choose arbitrarily), and define the SRG solution as the original solution without these columns.We recall our main result and give the proof. Theorem 5. If K ≥ 6, L ≥ 4 or K ≥ 10, L = 3 and d l ≥ K for all l, then L SRG < L DN C . Moreover, consider any sequence of L-DUFM problems for which K -→ ∞ so that 0.499 > L DN C for each problem. In that case,EQUATIONProof. We start by considering the case K = r 2 for some r. Without loss of generality we can assume n = 1, because all comparisons are between solutions that are by definition DNC1 collapsed, and the ratio L SRG /L DN C in the theorem statement does not depend on n.We first compute the loss of the SRG solution as in Definition 9 up to only one degree of freedom. Let us go term-by-term. The simplest to evaluate isλ W l 2 ∥W l ∥ 2 F for 2 ≤ l ≤ L -2.Using Lemma 13 (which relies on Lemma 12), we getλ W l 2 ∥W l ∥ 2 F = rλ W l 2 α l+1 α l .Similarly, for layer L -1, we use Lemma 14 (again relying on Lemma 12) to compute:λ W L-1 2 ∥W L-1 ∥ 2 F = r 2 (r -1) 2 λ W L-1 8((r -2)(r -3) + 2) α L α L-1.Combining Lemma 15 with Lemma 18 we get:λ W1 2 ∥W 1 ∥ 2 F + λ H1 2 ∥H 1 ∥ 2 F = λ W1 λ H-1 √ 2 + (r -1)(r -2) α 1 22 . Finally, combining Lemma 17 with Lemma 16 we get:1 2K ∥W L M L -I K ∥ 2 F + λ W L 2 ∥W L ∥ 2 F = λ W L 2 1 (r-2)(5r-19) (r-2)(r-3)+2 α L + r(r-1) 2 λ W L + λ W L 2 r -1 2(r-3) 2 (r-2)(r-3)+2 α L + r(r-1) 2 λ W L + λ W L 2 r(r-3) 2 2 (r-2)(r-3)+2 α L + r(r-1) 2 λ W L .The total loss of the SRG solution is just the sum of all these terms, which is expressed in terms of α 2 , α 3 , . . . , α L . We now verify that the choice in (6) minimizes the loss, having set q ≡ α 1/2 2 . To do so, we compute the partial derivatives of L w.r.t. the α l 's and set them to 0:0 = ∂L ∂α 2 = -rλ W2 α 3 α 2 2 + λ W1 λ H-1 √ 2 + (r -1)(r -2) α -1 2 2 ⇐⇒ α 3 α 2 = λ W1 λ H-1 √ 2 + (r -1)(r -2) rλ W2 q.For 3 ≤ l ≤ L -2, we have0 = ∂L ∂α l = - rλ W l 2 α l+1 α 2 l + rλ W l-1 2 1 α l-1 ⇐⇒ α l+1 α l = λ W l-1 λ W l α l α l-1 .And finally, for layer L -1, we have0 = ∂L ∂α L-1 = - λ W L-1 2 r 2 (r -1) 2 4((r -2)(r -3) + 2) α L α 2 L-1 + rλ W L-2 2 1 α L-2 ⇐⇒ α L α L-1 = λ W L-2 λ W L-1 4((r -2)(r -3) + 2) r(r -1) 2 α L-1 α L-2 .Denoting by p = λ W1 λ H1 √ 2 + (r -1)(r -2) , we can express these fractions asα l+1 α l = p rλ W l q, 2 ≤ l ≤ L -2, α L α L-1 = 4((r -2)(r -3) + 2)p r 2 (r -1) 2 λ W L-1 q,which gives the expressions in (6) . Finally, plugging this back into the loss function we get a univariate q-dependent function of the following form:L SRG (q) = λ W L 2 1 4(r-2)(5r-19) √ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2) L-2 r L-1 (r-1) 2 L-1 i=2 λ W i q L + r(r-1) 2 λ W L + λ W L 2 r -1 8(r-3) 2 √ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2) L-2 r L-1 (r-1) 2 L-1 i=2 λ W i q L + r(r-1) 2 λ W L + λ W L 2 r(r-3) 2 8 √ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2) L-2 r L-1 (r-1) 2 L-1 i=2 λ W i q L + r(r-1) 2 λ W L + L 2 λ W1 λ H1 √ 2 + (r -1)(r -2) q.The loss of the DNC solution can be computed by a simple extension of the expression (17) from [48] :L DN C (q) = λ W L 2 r(r-1) 2 λ L-1 W L-1 λ H 1 L-2 i=1 λ W i q L + r(r-1) 2 λ W L + L 2 r(r -1) 2 λ W L-1 q.At this point, we split our analysis for L = 3 and for L > 3. We start with L > 3, which is simpler.Analysis for L > 3. As K ≥ 6, the following upper bound holds:L SRG (q) ≤ LSRG (q) := λ W L 2 r(r-1) 2 8 √ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2) L-2 r L-1 (r-1) 2 L-1 i=2 λ W i q L + r(r-1) 2 λ W L + L 2 λ W1 λ H1 √ 2 + (r -1)(r -2) q.Now we reparametrize L DN C (q) and the upper bound on L SRG (q), so that they look as similar as possible. By replacing λ W L-1 q with q, we getEQUATIONSimilarly, by replacing√ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2)r q with q, we get:min q≥0 LSRG (q) = min q≥0 λ W L 2 r(r-1) 2 8r √ 2+ √ (r-1)(r-2) 2 (r-1) 2 λ H 1 L-1 i=1 λ W i q L + r(r-1) 2 λ W L + L 2 rq.Next, by replacing8r √ 2+ √ (r-1)(r-2) 2 (r-1) 2 1 Lq with q, we get:min q≥0 LSRG (q) = min q≥0 λ W L 2 r(r-1) 2 1 λ H 1 L-1 i=1 λ W i q L + r(r-1) 2 λ W L (8) + L 2 r    √ 2 + (r -1)(r -2) 2 (r -1) 2 8r    1 L q.After the reparameterization, L DN C (q) and LSRG (q) have almost the same form except for the multiplier r-1 2 in the DNC case and   √ 2 + (r -1)(r -2) 2 (r -1) 2 8r    1 Lin the SRG case. Therefore, the inequality between L DN C and LSRG is fully determined by the inequality between these two terms. We can write:r -1 2 >    √ 2 + (r -1)(r -2) 2 (r -1) 2 8r    1 L ⇐⇒ r(r -1) L-2 > 2 L-3 √ 2 + (r -1)(r -2)2We first solve it for L = 4 and any r ≥ 4 (which is guaranteed by K ≥ 6). We get the inequality r(r -1) 2 > 2(r -1)(r -2) + 4 + 4 2(r -1)(r -2). This inequality is equivalent to (r -1)(r 2 -3r + 4) > 4 + 4 2(r -1)(r -2), which holds for all r ≥ 4.Compared to the case L = 4, for general L the LHS gets multiplied by (r -1) L-4 and the RHS gets multiplied by 2 L-4 , which is smaller for r ≥ 4. Hence, the inequality holds as well.Analysis for L = 3. Here, we need a tighter upper bound than LSRG (q). Thus, we writeL SRG (q) ≤ λ W3 2 r 8(r-3) 2 √ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2) r 2 (r-1) 2 λ W 2 q 3 + r(r-1) 2 λ W3 + λ W3 2 r(r-3) 2 8 √ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2) r L-1 (r-1) 2 λ W 2 q 3 + r(r-1) 2 λ W3 + 3 2 λ W1 λ H1 √ 2 + (r -1)(r -2) q.We equivalently re-write this by extending both of the ratios by r-2 r-2 r-1 r-1 and then moving r-2 r-1 to denominator. Thus,L SRG (q) ≤ LSRG (q) := λ W3 2 r(r-1) r-2 8(r-3) 2 √ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2) r 2 (r-1)(r-2)λ W 2 q 3 + r(r-1) 2 λ W3 + λ W3 2 r(r-3)(r-1) 2(r-2) 8 √ λ W 1 λ H 1 √ 2+ √ (r-1)(r-2) r 2 (r-1)(r-2)λ W 2 q 3 + r(r-1) 2 λ W3 + 3 2 λ W1 λ H1 √ 2 + (r -1)(r -2) q.Now, we perform the same reparametrizations as for L > 4, with the only exception of treating (r -1)(r -2) in the denominator of the denominator of the current ratios as (r -1) 2 in the previous case. Then, we havemin q≥0 LSRG (q) = min q≥0 λ W3 2 r(r-1) r-2 (r-3) 2 λ H 1 λ W 1 λ W 2 q 3 + r(r-1) 2 λ W3 + λ W3 2 r(r-3)(r-1) 2(r-2) 1 λ H 1 λ W 1 λ W 2 q 3 + r(r-1) 2 λ W3 + 3 2 r    √ 2 + (r -1)(r -2) 2 (r -1)(r -2) 8r    1 3q.Assume that the following inequality holds:EQUATIONThen,min q≥0 LSRG (q) ≤ min q≥0 LSRG (q) := min q≥0 λ W3 2 r(r-1) 2 1 λ H 1 λ W 1 λ W 2 q 3 + r(r-1) 2 λ W3 + 3 2 r    √ 2 + (r -1)(r -2) 2 (r -1)(r -2) 8r    1 3q.The only difference between the expression considered here and the one considered in the L > 3 case is that here we have (r -1)(r -2) instead of (r -1) 2 within the expression. By comparing against L DN C again, we get that LSRG < L DN C if and only if r(r-1)2 > √ 2 + (r -1)(r -2) 2 (r-2). This is equivalent to (r -1)(3r -4) > 2(r -2) + 2(r -2) 2(r -1)(r -2), which holds for all r ≥ 4.It remains to show that (9) holds, and it suffices to do so for the minimizer q * of L DN C , as min q≥0 LSRG (q) ≤ LSRG (q * ) ≤ LSRG (q * ) < L DN C (q * ) = min q≥0 L DN C (q). Note that this is equivalent tor(r -1) 2 λ W3 < (r -3) 2 -2 λ W1 λ W2 λ H1 (q * ) 3 .Note that the minimum of the function in (7) (having the same reparametrization as LSRG ) -if it is not at q * = 0, in which case the statement of the theorem is trivial -must come after the unique inflection point of the function. A direct computation yields that this inflection point satisfiesr(r -1) 2 λ W3 = 2 λ W1 λ W2 λ H1 q 3 .Therefore, the minimum of ( 7) is attained at q * for whichr(r -1) 2 λ W3 < 2 λ W2 λ W1 λ H1 (q * ) 3 .For r ≥ 5, this implies that such a q * satisfies (9), which concludes the argument for K = r 2 . For a general K, the extension is rather simple. Note that the first type of SRG solution in Definition 11 is constructed in a way so that the losses attained by the SRG and DNC parts sum up. Therefore, we can split the analysis for the SRG and DNC parts. The DNC part obviously attains equal loss to the DNC solution. For the SRG part, the analysis done above applies, and the argument is complete.It remains to show the statement on the asymptotic relationship between L SRG and L DN C for K -→ ∞ when L ≥ 4. Formally, we should consider sequences of the problems and label everything with an extra index corresponding to the order within the sequence. However, with an abuse of notation, we drop this indexing and switch to the O, Θ notations whenever convenient.As before, we start by considering K of the form r 2 for some r. Let Λ = λ H1 L i=1 λ Wi andΨ(K) = 2 L-3 √ 2+ √ (r-1)(r-2) 2 r(r-1) L-2 1 L, where r corresponds to the value s.t. r 2 = K. We note that Ψ(K) = Θ(K). Since we are interested in the ratio L SRG L DN C , we do a few changes and reparametrizations to the expressions in ( 7) and ( 8): we multiply both by 2, divide all terms in the left summands by λ W L , rewrite r(r-1) 2 as K, plug in the defined quantities, divide all the terms in the left summands by K and finally replace Λ -1 L K -1 L q with q to obtain the following expression1 q L + 1 + LK L+1 L Λ 1 L q (10)for the DNC loss, and the following expressionEQUATIONfor the SRG loss. Using a similar trick as in the previous analysis for L = 3, we have that the minimum of the function in ( 10) is achieved when q > 1. Hence, we can lower bound (10) by1 3 q -L + LK L+1 L Λ 1 L q.For this convex expression, we can find the optimal solution by setting to zero the derivative, which gives that the optimal solution is (1+ L)3 -1 L+1 KΛ 1 L+1. Similarly, we can upper bound (11) byq -L + LK L+1 L Λ 1 L Ψ(K)qand after finding the optimal solution we get that it equals (1 + L)KΛ1 L+1 Ψ(K) L L+1. This allows us to conclude thatL SRG L DN C = O(K 3-L 2(L+1) ).To get the same formula when the number of classes is not of the form r 2 , we only need simple adjustments. For this part, we will employ the upper-index notation to denote the number of classes K to which the solution corresponds. First, note that the optimal value of ( 10) is continuous in the coefficient in front of the linear term q. Therefore, if L K DN C < 0.499, then, choosing the smallest r for which K ≤ r 2 := K, we see that L K DN C < 0.5 for the same set of regularization parameters, as K K K-→∞ ----→ 1. Since the argument above does not need L DN C < 0.499 but only L DN C < 0.5, we can now use that L K SRG with the same regularization parameters is still O(K 3-L 2(L+1) ). Finally, choosing the second construction in Definition 11, we construct the SRG solution for K classes from the SRG solution for K classes with the same regularization parameters (thus also the same regularization as for the DNC solution with K classes). To conclude, it just suffices to see that L K SRG ≥ L K SRG because we removed columns from H 1 , decreasing its norm and the fit loss is at most as big because the columns with the worst fit loss were removed and the fit loss is an average over the columns. This concludes the proof also for general K.We conclude the section by stating and proving a few auxiliary lemmas that were used in the proof of Theorem 5. Lemma 12. Consider the following optimization problem:min w ∥w∥ 2 (12) s.t. z T = w T A l T r .(13) Then, the value of the optimal solution is (r -1)2 α l (r -2) 2 z T T T r I r - 3r -4 4(r -1) 2 1 r 1 T r T r z.Proof. Multiplying the constraint with T T r (T r T T r ) -1 from the right we get z T T T r (T r T T r ) -1 = w T A l . Now, we can use that the minimum l 2 norm solution of such a system can be computed by multiplying with the right pseudoinverse of A l . Thus, we get w= A l (A T l A l ) -1 (T r T T r ) -1 T r z = 1/α l A l (T r T T r ) -1 T r z.Then the squared norm of this is simply:w T w = 1 α 2 l z T T T r (T r T T r ) -1 A T l A l (T r T T r ) -1 T r z = 1 α l z T T T r (T r T T r ) -2 T r z.Now, we know thatT r T T r = r -2 r -1 I r + 1 r -1 11 T = r -2 r -1 I + 1 r -2 11 T .This can be seen by looking at the structure of K n where two vertices have exactly one edge between them. Now we can compute the the inverse of this matrix using the Sherman-Morrison formulaI + 1 r -2 11 T -1 = I - 1 2(r -1) 11 Tand the square is:I + 1 r -2 11 T -2 = I - 3r -4 4(r -1) 2 11 T .Putting this all together, the proof is complete.Lemma 13. Let 2 ≤ l ≤ L -2.Consider Ml+1 , M l as in Definition 9 of the SRG solution. Then, the following optimization problem:EQUATIONachieves optimal value of rα l+1 α l .Proof. This is a direct consequence of Lemma 12. Denote γz 0 a row from Ml+1 which corresponds to the first row of T r and such that ∥z 0 ∥ = 1. Then, T r γz 0 = γ(1, 1/(r -1), . . . , 1/(r -1)) T . Directly evaluating the expression in Lemma 12 will yield γ 2 α -1 l for a single row and thus for all rows we get the value from the lemma statement. Lemma 14. Consider ML , M L-1 as in Definition 9 of the SRG solution. Then, the following optimization problem:EQUATIONachieves optimal value of αL α L-1 r 2 (r -1) 2 4((r -2)(r -3) + 2).Proof. We first need to characterize the rows of ML . Note that ML comes from the multiplication of T r and AL , see Definition 9. This operation can be seen as weighting vertices of K r (rows of T r ) and then looking at what the sum of the weights of adjacent vertices of each edge (column of T r ) is. We can easily see that the resulting vector has exactly one "-1" entry (for the edge corresponding to the two vertices given negative weight) and exactly r-2 2 entries with "+1". Therefore, it must be scaled with the inverse of s := (r-2)(r-3) 2 + 1 to be unit norm. Now, let z 1 be one of these vectors with the negative edge between first two vertices. Then,T r z 1 = - 1 s √ r -1 , - 1 s √ r -1 , r -3 s √ r -1 , r -3 s √ r -1 , . . . T ,which can be easily derived if we imagine doing edge-wise dot-product between two vertex weightings, one with two "-1s" for z 1 and the other type with one "+1" representing the rows of T r . For the other vectors in HL , the resulting vectors would be similar, except they would have the negative entries for different pairs of vertices of K r . Note thatz T 1 T T r T r z = 2 s 2 (r -1) + (r -3) 2 (r -2) s 2 (r -1) , z T 1 T T r 1 r 1 T r T r z = ((r -3)(r -2) -2) 2 s 2 (r -1).Therefore, if we are optimizing for γz 1 , then an application of Lemma 12 givesw T w = γ 2 α -1 L-1 (r -1) 2 (r -2) 2 2 s 2 (r -1) + (r -3) 2 (r -2) s 2 (r -1) - 3r -4 4(r -1) 2 ((r -3)(r -2) -2) 2 s 2 (r -1) ,where w denotes a row of W . Simplifying this expression, we getw T w = γ 2 α -1 L-1 r(r -1) 2((r -2)(r -3) + 2).To conclude, it suffices to sum up r(r-1) 2 such rows having total l 2 norm squared α L (and, hence,γ 2 = α L ), which gives ∥W ∥ 2 F = α L α L-1 r 2 (r -1) 2 4((r -2)(r -3) + 2) ,and concludes the proof.Lemma 15. For 2 ≤ l ≤ L -1, consider M l , Ml as in Definition 9 of the SRG solution. Then, M l = Ml and the eigenvalues of M T l M l are: µ 1 = 2α l with multiplicity 1,µ 2 =r -2 r -1 α l with multiplicity r -1,µ 3 = 0 with multiplicity r(r -3) 2 .Proof. From the definition, it readily follows that M l = Ml , so let us compute M T l M l . Looking at any row of M l , we see that it has non-negative equal entries of value √ α ij / √ r -1, where j α ij = α l on all the r -1 edges of K r that contain the vertex corresponding to that row. Therefore, by definition of α l , the sum of squares of all entries corresponding to one row type within any column is α l /(r -1). Each edge (and, thus, column) contains exactly two vertices, thus the diagonal elements of M T l M l , which are the l 2 norms squared of the columns of M l , are simply equal to 2α l r-1 . There are two possible off-diagonal values. One is for the pairs of columns that correspond to edges that share a vertex and one is for those pairs that do not share a vertex. The pairs of columns whose edges do not share a vertex do not have any entries which would both be jointly positive, because either a vertex does not belong to one edge or to the other. Therefore, the value of off-diagonal entries corresponding to such pairs is simply 0. On the other hand, there is exactly one vertex that has non-zero values for both edges corresponding to columns whose edges do share a vertex -it is the shared vertex. Therefore the value of off-diagonal entries of this type is α L r-1 . Crucially, the structure of the off-diagonal entries is fully determined by the graph T r , because two edges in K r share a vertex if and only if they are connected in the graph T r . Therefore, M T l M l can be written as a weighted sum of I K and the adjacency matrix G r of T r , where the weight of I K simply corresponds to the size of the diagonal term and the weight of G r to the positive off-diagonal term. In conclusion, we getM T l M l = 2α l r -1 I K + α l r -1 G r .As T r is a strongly regular graph with parameters (r(r -1)/2, 2(r -2), r -2, 4), G r has a single eigenvalue equal to 2(r -2), r -1 eigenvalues equal to r -4 and r(r -3)/2 eigenvalues equal to -2, which concludes the proof.Lemma 16. Consider M L as in Definition 9 of the SRG solution. Then, the eigenvalues of M T L M L are:µ 1 = (r -2)(5r -19)α L (r -2)(r -3) + 2 with multiplicity 1, µ 2 = 2(r -3) 2 α L (r -2)(r -3) + 2with multiplicity r -1,µ 3 = 2α L (r -2)(r -3) + 2with multiplicity r(r -3) 2 .Proof. Let us compute M T L M L . Looking at any row of M L , we see that it has non-negative equal entries of value √ α ij /s, where s = (r-2)(r-3) 2 + 1 and j α ij = α L on all edges in a subgraph of K r of size r -2. Therefore, by definition of α L , the sum of squares of all entries corresponding to one row type within any column is α L /s 2 . However, not all row types have non-zero value on any particular column. Namely, a row type will only have non-zero value on a column, if the row-type corresponds to such a subgraph of K r , which is disjoint with the edge corresponding to the column. This is because all edges outside the complete subgraph of r -2 vertices corresponding to the row type are assigned 0 in M L . Therefore, the number of row types that assign non-zero value in a particular column is equal to the number of r -2 vertex sets. This corresponds to the number of edges in K r , which is equal to r-2 2 = s 2 -1. Thus, the diagonal elements of M T L M L , which are the l 2 norms squared of the columns of M L , are simply equal to (s 2 -1)α L s 2. There are two possible off-diagonal values. One is for the pairs of columns that correspond to edges that share a vertex, and one is for those pairs that don't share a vertex. Let us compute the number of row types assigning positive value to both of these columns jointly. Using the same interpretation, the columns correspond to edges and only row types that correspond to r -2 vertex subsets disjoint with them assign positive value to the column of that edge. If we want this to be satisfied for both rows jointly, we need to take the intersection of those r -2 vertex subsets, which in this case will result in an r -3 vertex subset. Thus, exactly r-3 2 row types will jointly assign a positive value. Therefore, we have value(r-3)(r-4)α L 2s 2on these off-diagonal entries. For the pairs of columns that correspond to edges with disjoint vertices, the same intersection will now yield a set of vertices of size only r -4. Therefore, the value of this off-diagonal entry is (r-4)(r-5)α L 2s 2. Crucially, the structure of the off-diagonal entries is fully determined by the graph T r , because two edges in K r share a vertex if and only if they are connected in the graph T r . Therefore, M T L M L can be written as a weighted sum of 1 K 1 T K , I K and the adjacency matrix G r of T r . The weights can be determined as follows: we first subtract a multiple of 1 K 1 T K to make the smaller off-diagonal entry of M T L M L zero, then we subtract what is left of the diagonal and we take the rest to be a multiple of G r . In conclusion, we getM T L M L = (r -4)(r -5)α L 2s 2 1 K 1 T K + (s 2 -1)α L s 2 - (r -4)(r -5)α L 2s 2 I K + (r -3)(r -4)α L 2s 2 - (r -4)(r -5)α L 2s 2 G r .As T r is a strongly regular graph with parameters (r(r -1)/2, 2(r -2), r -2, 4), G r has a single eigenvalue equal to 2(r -2), r -1 eigenvalues equal to r -4 and r(r -3)/2 eigenvalues equal to -2. The summation with I K only shifts all the eigenvalues. The term 1 K 1 T K has only one non-zero eigenvalue, and the eigenvector is identical to that of the eigenvector corresponding to the dominant eigenvalue of G r . This concludes the proof.Lemma 17. Assuming DNC1, let M L be the mean matrix of the last layer. Let M L = U ΣV T be the full SVD of M L and let σ i , i ∈ [K], be the singular values of M L . Then, the following optimization problem:min W L 1 2K ∥W L M L -I K ∥ 2 F + λ W L 2 ∥W L ∥ 2 Fattains the minimum ofλ W L 2 K i=1 1 σ 2 i + Kλ W L .Proof. The proof consists in a direct computation. Let W * L denote the minimizer. Computing the gradient and setting it to 0 gives thatW * L = M T L (M L M T L + λ W L KI d L ) -1 = V Σ T (ΣΣ T + λ W L KI d L ) -1 U T , which readily implies that ∥W * L ∥ 2 F = K i=1 σ 2 i (σ 2 i + λ W L K) 2 , ∥W L M L -I K ∥ 2 F = V Σ T (ΣΣ T + λ W L KI d L ) -1 ΣV T -V V T 2 F = K i=1 σ 2 i σ 2 i + λ W L K -1 2 = K i=1 K 2 λ 2 W L (σ 2 i + λ W L K) 2 ,thus concluding the argument.Lemma 18. The optimization problem min A,B;C=ABEQUATION)attains the minimum of √ λ A λ B ∥C∥ * , and the minimizers are of the formA * = γ A U Σ 1/2 R T , B * = γ B RΣ 1/2 V T .Here, the constants γ A , γ B only depend on λ A , λ B ; U ΣV T is the SVD of C; and R is an orthogonal matrix.Proof. See Lemma C.1 of [51] .A.2 No within-class variability is still optimal Theorem 6. The optimal solutions of the L-DUFM (1) exhibit at layer L, i.e.,H * L = M * L ⊗ 1 T n holds for any optimal solution (H * 1 , W * 1 , . . . , W * L ) of the L-DUFM problem.Proof.Step 1: Reduction to n = 1. In the first step, assume by contradiction that there exists an optimal solution of (1) with regularization parameters (λ H1 , λ W1 , . . . , λ W L ) denoted as (H * 1 , W * 1 , . . . , W * L ) which does not exhibit deep neural collapse at layer L. This means that there exist indices c, i, j s.t.h L ci ̸ = h L cj .Let us construct two solutions of the n = 1 L-DUFM. They will share the weight matrices which will equal (W * 1 , . . . , W * L ) -the weight matrices of the original solution. To construct the features, for every class except the c-th, pick any sample and share it between both solutions. For the class c, take the samples h L ci , h L cj and put one in one solution and the other one in the other solution. Denote H 1 , W * 1 , . . . , W * L ) are optimal solutions of (1) with regularization parameters (nλ H1 , λ W1 , . . . , λ W L ). To prove it, assume by contradiction that, without loss of generality, (H(2) 1 , W * 1 , . . . , W * L )is not an optimal solution of the corresponding problem. Then, there exists an alternative (H(0) 1 , Ŵ * 1 , . . . , Ŵ * L )that achieves smaller loss for this problem. Let us duplicate all the samples of Ĥ(0)1 for n times, thus constructing Ĥ * 1 = H (0) 1 ⊗ 1 T n . The solution ( Ĥ * 1 , Ŵ * 1 , . . . , Ŵ * L )has the same loss under the L-DUFM problem with regularization parameters (λ H1 , λ W1 , . . . , λ W L ) as the solution (H(0) 1 , Ŵ * 1 , . . . , Ŵ * L )for the L-DUFM with n = 1 and parameters (nλ H1 , λ W1 , . . . , λ W L ). This is easy to see from the separability of both ∥H 1 ∥ 2 F and the fit part of the loss in (1) w.r.t. the columns of H 1 . For the same reasons, the loss functions for (H * 1 , W * 1 , . . . , W * L ) in the original problem equals the loss function of the solutions (HEQUATION1 , W * 1 , . . . , W * L ) in the reduced problem. In fact, if this was not the case, there would need to be an inequality between the losses exhibited by two different columns of H 1 belonging to the same class, from which we could arrive at a contradiction by taking the better column and multiplying it to all columns within that class, thereby obtaining a better solution. This means that the loss of ( Ĥ * 1 , Ŵ * 1 , . . . , Ŵ * L ) in the original problem is smaller than the loss of (H * 1 , W * 1 , . . . , W * L ), which is a contradiction.Step 2: Excluding an aligned case. By assumption we know that not onlyH (1)1 and H(2) 1 differ in the c-th column (from now on we assume without loss of generality that it is the first column) but also HL and HL do. Denote for simplicity the first (differing) columns of HL and HL as x, y respectively. We now show that it is not possible that y = αx. First, α has to be non-negative since x, y are entry-wise non-negative given that they come after the application of σ. Assume w.l.o.g. α > 1 (otherwise, we can just exchange the roles of x and y). Consider a reduced problem where we only optimize for the size of the first column of either HL or HL , focusing on that part of the problem (1) which is relevant for this column, being:min t≥0 1 2N tW L h L(i) 11 -e 1 2 2 + nλ H1 2 th 1(i) 11 2 2 .This problem is strongly convex, quadratic and simple enough to give the following: if α > 1, thenEQUATIONand simultaneouslyEQUATION. This means that H1 is a strictly better solution thanH (1)1 -a contradiction.Step 3: Contradiction by zero gradient condition. By optimality of both solutions we get∂L ∂W L (H1,W1,...,W L )=(H (1) 1 ,W * 1 ,...,W * L ) = 0 = ∂L ∂W L (H1,W1,...,W L )=(H (2) 1 ,W * 1 ,...,W * L ).An application of the chain rule gives∂L ∂W L = ∂L F ∂ HL+1 ∂ HL+1 ∂W L + λ W L W L = ∂L F ∂ HL+1 H T L + λ W L W L ,where HL+1 is the output of our model. Plugging this back to the previous equation and using that W * L is the same in both expressions, we getEQUATIONEQUATIONL ) T .A = ∂L F ∂ HL+1 (H1,W1,...,W L )=(H (1) 1 ,W * 1 ,...,W * L ) , B = ∂L F ∂ HL+1 (H1,W1,...,W L )=(H (2) 1 ,W * 1 ,...,W * L ).Due to the separability of L F with respect to the columns of H 1 (and, thus, also of H l , Hl for all l ≤ L + 1), we get that the matrices A, B can only differ in their first columns and are identical otherwise. We denote these columns a, b for A, B, respectively. This implies that ax T = by T . Now we exclude a few cases. First, neither a nor b can be zero, because by the exact formula that exists for them, this would mean that exact fit was achieved for either of the columns. This is impossible with non-zero weight-decay, because decreasing the norm of the column of H1 or H(2) 1that achieves the exact fit by a sufficiently small value would necessarily lead to an improvement on the objective value. Moreover, if x = y = 0, then this is a contradiction with the assumption that x ̸ = y. Finally, the case x ̸ = y = 0 or 0 = x ̸ = y is excluded already in the step 2.Thus we get x, y, a, b are all non-zero. Looking at any fixed row (column) of ax T and by T we see that necessarily x, y (a, b) are aligned. However, this case is already solved in step 2 and leads to x = y, which is the contradiction. This concludes the proof.Theorem 8. Denote by L-DUFM ϵ the equivalent of (1), with σ replaced by σ ϵ . Let D = max{d 2 , d 3 , . . . , d L } and λ = λ H1 λ W1 . . . λ W L , with the regularization parameters upper bounded by 1/(L + 1). Then, for any globally optimal solution of the L-DUFM ϵ problem, the distance between any two feature vectors of the same class in any layer is at mostEQUATIONProof. In order not to mix approximation technical details with the gist of the proof, we split the argument into two parts: in the first part, we provide a heuristic for ϵ = 0 by assuming that ReLU is differentiable at 0; in the second part, we discuss what changes in the proof if we use the relaxation and then execute a technical computation that bounds the error based on the strength of the approximation (the size of ϵ). It is useful to split the loss function L into the two terms L F and L R . The former represents the fit part of the loss (which penalizes for deviation of the predictions from Y ), and the latter represents the regularization part of the loss.Part 1: Heuristic for ϵ = 0. We start identically to the proof of Theorem 6. As in Step 1 of that argument, if we have a globally optimal solution that does not exhibit DNC1 in the first layer, we can construct two different solutions of the n = 1 L-DUFM problem where the two solutions only differ in the first column of the H 1 matrix. Let us denote two such constructions H x 1 ̸ = H y 1 , where we denote x ̸ = y, to be the mentioned first columns, respectively. We emphasize that H x 1 , H y 1 both form optimal solutions of the n = 1 L-DUFM with the same tuple of weight matrices (W * 1 , . . . , W * L ). In particular, this means that∂L ∂W 1 (H1,W1,...,W L )=(H x 1 ,W * 1 ,...,W * L ) = 0 = ∂L ∂W 1 (H1,W1,...,W L )=(H y 1 ,W * 1 ,...,W * L ).An application of the chain rule gives∂L ∂W 1 = ∂L F ∂ H2 ∂ H2 ∂W 1 + λ W1 W 1 = ∂L F ∂ H2 H T 1 + λ W1 W 1 .Plugging this back to the previous equation and using that the W * 1 is the same in both expressions, we get∂L F ∂ H2 (H1,W1,...,W L )=(H x 1 ,W * 1 ,...,W * L ) (H x 1 ) T = ∂L F ∂ H2 (H1,W1,...,W L )=(H y 1 ,W * 1 ,...,W * L ) (H y 1 ) T .A = ∂L F ∂ H2 (H1,W1,...,W L )=(H x 1 ,W * 1 ,...,W * L ) , B = ∂L F ∂ H2 (H1,W1,...,W L )=(H y 1 ,W * 1 ,...,W * L ).Due to the separability of L F with respect to the columns of H 1 (and, thus, also H l for all l ≤ L), we get that the matrices A, B can only differ in their first columns and are identical otherwise. We denote these columns a, b for A, B, respectively. This implies that ax T = by T . Now, we treat a few cases. First, assume a = b = 0. Since it holds that (H x 1 , W * 1 , . . . , W * L ) is the optimal solution, then necessarily0 = ∂L ∂h 1 11 (H1,W1,...,W L )=(H x 1 ,W * 1 ,...,W * L ) = (W * 1 ) T a + λ H1 x ⇐⇒ 0 = x.Similarly, we get y = 0, but that is a contradiction with x ̸ = y. Therefore, at least one of a, b is non-zero. Next assume x = 0. Then ax T = 0. If b = 0 then y = 0 and we have a contradiction. On the other hand, if b ̸ = 0, then the row of by T that corresponds to a non-zero entry of b must be zero and thus y = 0. Similarly, if y = 0 we can get x = 0.Let us therefore assume x, y are both non-zero, which also implies a, b are both non-zero. Looking at any fixed row (column) of ax T and by T we see that necessarily x, y (a, b) are aligned. Let us write x = αy and αa = b for some α ̸ = 0. We will first show that if α > 0 then necessarily α = 1 and x = y. For this, let us fix any ray r ∈ R d1 . The ray r represents a set of possible first columns in H 1 . Let us fix any (W 1 , . . . , W L ). Since L is separable in the columns of H 1 , we can consider an optimization over β ≥ 0 to minimize L on (βr, W 1 , . . . , W L ). However, L F is convex by assumption and the mapping h 1 11 -→ h L 11 is ray-linear, therefore L F is convex in β. Moreover L R is strongly convex in h 1 11 and therefore L is strongly convex in β. This means it has a unique optimal solution β * .We have just showed that, if α > 0, then since x, y are aligned and thus lie on the same ray and are both optimal together with the same tuple of weight matrices, they must necessarily be identical and so α = 1, x = y. This is a contradiction and thus we are left with the case α < 0. Denote s = W * 1 x, t = W * 1 y. From linearity, we have s = αt. Note that if s = t = 0, then necessarily x = y = 0 because they don't have any effect on L F and they minimize L at 0. Thus, s, t are non-zero and negative entries of s are positive entries of t and vice-versa. This means that σ(s) and σ(t) have different sets of positive entries. However, from the optimality of the both solutions we know:∂L ∂W 2 (H1,W1,...,W L )=(H x 1 ,W * 1 ,...,W * L ) = 0 = ∂L ∂W 2 (H1,W1,...,W L )=(H y 1 ,W * 1 ,...,W * L ).Again, using the chain rule we get:∂L ∂W 2 = ∂L F ∂ H3 ∂ H3 ∂W 2 + λ W2 W 2 = ∂L F ∂ H3 H T 2 + λ W2 W 2 .Plugging this back to the previous equation and using that W * 2 is the same in both expressions, we get∂L F ∂ H3 (H1,W1,...,W L )=(H x 1 ,W * 1 ,...,W * L ) (H x 2 ) T = ∂L F ∂ H3 (H1,W1,...,W L )=(H y 1 ,W * 1 ,...,W * L ) (H y 2 ) T .Let us denoteC = ∂L F ∂ H3 (H1,W1,...,W L )=(H x 1 ,W * 1 ,...,W * L ) , D = ∂L F ∂ H3 (H1,W1,...,W L )=(H y 1 ,W * 1 ,...,W * L ).Due to the separability of L F with respect to the columns of H 1 (and, thus, also H l for all l ≤ L), we get that the matrices C, D can only differ in their first columns and are identical otherwise. We denote these columns c, d for C, D respectively. This implies that cσ(s) T = dσ(t) T .As above, if either c or d is zero, using the chain rule we would get that x or y (respectively) are zero too, which cannot happen. Therefore, both c and d are non-zero and σ(s), σ(t) must be aligned. Since they are non-zero, non-negative and with different supports, we have reached a contradiction. This proves that α < 0 is also impossible and the only possible case is α = 1, but that forces x = y, which is also a contradiction.Part 2: Relaxation to ReLU ϵ . The difficulty in making the previous heuristic rigorous is that ReLU is not differentiable at 0 and, thus, we do not have the desired analytical statement that global solutions must necessarily admit zero derivative (because the loss might not be differentiable at them at all). If we tried to use the same proof as in part 1 with the differentiable relaxed version of ReLU -ReLU ϵ , an issue would occur when showing that, if x, y are aligned and α ≥ 0, then α must be 1.The reason is that the mapping h 1 11 -→ h L 11 is no longer ray-linear and the corresponding optimization problem on any fixed ray is no longer quadratic and strongly convex. However, we can prove that the optimization problem admits a solution that is close to the solution of the corresponding ReLU optimization problem. For this, let us fix any direction r such that ∥r∥ = 1 and an optimization parameter t ≥ 0, and define the following two losses:EQUATIONEQUATION)We now bound max t≥0 |L 0 (t, r) -L ϵ (t, r)|. For this, we fix any t ≥ 0, and bound the accumulated l 2 error of using σ ϵ instead of σ throughout the layers. For this, a useful statement that we will need is the following:λ W L 2 ∥W * L ∥ 2 F = λ W L-1 2 W * L-1 2 F = • • • = λ W1 2 ∥W * 1 ∥ 2 F = nλ H1 2 ∥H * 1 ∥ 2 F ≤ 1 2(L + 1).This is true because, by a simple computation, we get that the terms must be balanced and the inequality comes from the fact that the solution (0, 0, . . . , 0) achieves full loss 1/2 in the L-DUFM as well as L-DUFM ϵ problems and, thus, L R is trivially upper-bounded by this. This implies that, for each W l (andH 1 ), ∥W l ∥ ≤ ∥W l ∥ F ≤ 1 √ (L+1)λ W l.For ease of exposition, we set t = 1 (the same argument would work for all t). We see that W 1 r does not introduce any l 2 error. Then, the l 2 error that is introduced in the application of the ReLU is trivially upper-bounded by ϵ √ d 2 . After applying W 2 , we can use the bound on the operator norm ∥W 2 ∥ obtained above to upper bound the propagated l 2 error by1 (L + 1)λ W2 ϵ d 2 .After that, we obtain an additive l 2 error of ϵ √ d 3 by applying σ ϵ , which gives a total l 2 error of1 (L + 1)λ W2 ϵ d 2 + ϵ d 3 .Then, again, we multiply this whole expression with1 √ (L+1)λ W 3to account for the multiplication byW 3 .Inductively, the upper bound on the l 2 error in the output space isϵ L l=2 √ d l (L + 1) L-l+1 2 L j=l 1 λ Wj .This can be further upper bounded asϵ √ D λ H1 λ W1 (L + 1) L-1 2 √ λ .Using the triangle inequality, the upper bound on |L 0 (t, r) -L ϵ (t, r)| is this expression squared. On the other hand, the second derivative of L 0 (t, r) with respect to t is lower bounded by nλ H1 .Given two functions f 1 and f 2 , with f 1 strongly convex with second derivative at least c and f 2 everywhere at most d distant from f 1 , then the distance between their global minimizers is at most 2 d/c. Applying this to our case, we get that the distance between the minimizers t 0 and t ϵ of L 0 (t, r) and L ϵ (t, r) is at most 2ϵ D(L + 1)(L + 1) L+1 2 √ λn .Since the ray r is unit-norm, this is also the upper bound on the distance between two feature vectors of any globally optimal solution in the first layer. To obtain the upper bound on the distance between two vectors in any layer, we proceed as follows.Assume we have two input vectors of the first class (now we know they need to be aligned):x 1 , y 1 = α 1 x 1 , where α 1 > 1. As before, xl , x l , ỹl , y l are the l-th layer representations of these vectors before and after σ ϵ . If we would compute ∂L ∂W l with respect to any layer l ≥ 2 and used the same arguments as in part 1 (that still carry to the analysis for σ ϵ ), we would find out that in each layer, we need to have y l = α l x l . Moreover, we can assume that xl , x l , ỹl , y l are non-zero at all layers because otherwise the same argument in part 1 would trivialize the rest of the proof. By a simple inductive argument, since α 1 > 1, we know that α 2 > 1 as well because σ ϵ is strictly increasing on [0, ∞). Similarly, α l > 1 for all l. Note that, if there exists at least one index i on which x l i is bigger or equal than ϵ, then necessarily α l = α l-1 , because σ ϵ is the identity on inputs of at least ϵ, and the α l can be uniquely determined from y l i /x l i = y l-1 i /x l-1 i . Having α l = α l-1 makes us have more control over the distance between x l and y l . If this fails to hold at some layer, we need a separate analysis.For this, let l 0 denote the first layer (assuming it exists), where xl0 does not have any entries that are bigger or equal than ϵ. This means that x l0 ≤ ϵ d l0 . We now compute the maximal possible norm of y l0 . Since α 1 = α 2 = • • • = α l0-1 , for all 2 ≤ l < l 0 and for each index i, either xl i , ỹl i ≤ ϵ or ϵ ≤ xl i , ỹl i . Otherwise, since σ ϵ (x) < x ∀x ∈ (0, ϵ), y l i /x l i > α l , a contradiction. Thus, we get xl -ỹl ≥ x l -y l . Therefore, x l -y l can only grow by applying W l . Thus, after applying W 1 , W 2 , . . . , W l0-1 and using the operator norm bound with all of the matrices, we getx l -y l ≤ 2ϵ D(L + 1) (L + 1) L+1 2 √ λn 1 (L + 1) l 0 -1 2 λ W1 λ W2 . . . λ W l 0 -1 .Combining with x l0 ≤ ϵ d l0 and using the triangle inequality, we gety l ≤ 2ϵ D(L + 1) (L + 1) L+1 2 √ λn 1 (L + 1) l 0 -1 2 λ W1 λ W2 . . . λ W l 0 -1 + ϵ d l0 .Applying the operator norm bound with W l0 , W l0+1 , . . . , W L-1 , we get:y L ≤ 2ϵ D(L + 1) (L + 1) L+1 2 √ λn 1 (L + 1) L-1 2 λ W1 λ W2 . . . λ W L-1 + ϵ d l0 1 (L + 1) L-l 0 2 λ W l 0 λ W l 0 +1 . . . λ W L-1 ≤ 3ϵ D(L + 1) (L + 1) L+1 λ√ n .Since x L ≤ y L we can use the triangle inequality again to obtain the final:x L -y L ≤ 6ϵ D(L + 1) (L + 1) L+1 λ√ n .Note that the same bound is an upper bound for any layer, since in each layer we are increasing the upper bound by at least a factor (L + 1) -1/2 λ -1/2 W l . In case such a layer l 0 does not exist, the upper bound above is still valid, since we can simply use the error propagation through all the layers, as we did for l < l 0 in the previous case. We would arrive at the same bound as above but with 4 instead of 6 as a multiplicative factor (because we would not introduce the additive error ϵ d l0 ).Experiments on small number of classes and layers. For L = 3, we weren't able to find any solutions that would outperform DNC for K ≤ 6. For K = 7, the difference in the losses is extremely small. For K = 6, we did find some low rank solutions, but these were either slightly worse than DNC or the losses were the same up to four decimal places. Already for L ≥ 4, we find low-rank solutions for all K ≥ 3. We present some of them for K ∈ {3, 4, 5} in Figure 5 . Note, that all these solutions were found automatically by gradient descent through the optimization process.We specifically highlight the solution for K = 4, as it represents another graph structure different from SRG. Namely, this solution is based on the square graph. We see that each column (edge) has positive scalar product with exactly two other columns (the corresponding edges share a vertex), and it is orthogonal to one other column (the non-touching sides of a square). Each row (vertex) has only two positive values, and these correspond to the two sides (edges) to which they belong.Experiments on large number of classes or layers. For large L or K, the behavior of the low-rank solutions is slightly different from the behavior when both L and K are moderate. When l is close to L, it no longer holds that Ml = M l , and the rank of M l is larger as the singular values do not decay sharply to 0. However, we note that the singular values are rather small and, thus, it is not clear whether they would disappear with a longer training (we trained for 200000 steps of full gradient descent with learning rate 0.5). In Figure 6 , we take L = 7, K = 15, and weight decay 0.0025 in all layers. We highlight that M6 ̸ = M 6 and the singular values of M 6 are small but non-zero after the 3 dominant values. We also highlight that the rank of previous layers is 3, which is remarkably small (and also smaller than the rank of the SRG solution). SRG solutions. In Figure 1 presented in the main body, we recover the SRG solution for K = 10. In Figures 7 and 8 , we show that solutions very similar to SRG are recovered for K = 6 and K = 15, respectively. The only difference with SRG is in the construction of ML . We note that the losses of these solutions are slightly lower than the loss of our construction, which proves that the SRG solution itself is not necessarily globally optimal.We complement the experiments of Figure 3 with two extra ablation studies for ResNet20 trained on CIFAR-10 with a 4-layer MLP head. We focus on the dependence of the average rank on the weight decay and the learning rate, and present the results in Figure 9 . The weight decay has a clear effect on the rank of the solutions found by gradient descent, similarly to the results in Figure 3 for the L-DUFM model. The effect of the learning rate is slightly less clear, but we still see a general downward trend.Finally, in Figure 10 , we include the analysis of the average rank as a function of weight decay in the standard regularization setting for training on the MNIST dataset. The results confirm the trend from the previous experimental settings, showing that the weight decay strength is a crucial predictor of the final rank even in standard regularization setting, which has a different loss landscape compared to the L-DUFM. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: The experiments do not require any specific hardware setup.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).Justification: The research conducted in the paper conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).The order is not important, both the rows and the columns can afterward be permuted if we accordingly permute also the weight matrices. 


Decision: This paper studies the Neural Collapse phenomenon (NC) in deep nonlinear networks. They prove that a collapsed solution is not optimal under the widely-used “deep unconstrained feature model.” This highlights a surprising aspect of neural collapse in deep nonlinear networks, which was not present in prior analyses. Further, the authors explore the low-rank bias of regularization as a potential mechanisms for this suboptimal behavior.

Reviewers agree that this is a strong, well-motivated technical contribution which yields insight on a timely topic. I recommend acceptance.

Reviews: review: paper_summary: paper_summary: Papyan et. al that showed that at the terminal phase of training there are four phenomena called neural collapse on the last layer of a deep neural network architecture. The authors extended Papyan's work by considering the earlier layers of nonlinear deep neural networks. They proved the first neural collapse condition (convergence to class means) is optimal for DNNs (Theorem 6 in manuscript). They also proved the second neural collapse condition (within-class variability) does not hold if number of layers and classes are high enough by showing there exists a scenario with better performance (Theorem 5). The claims are also supported by the experiments.
strength_weakness: strength_weakness: The results only hold under certain assumptions such as using multi-layer regularization.
questions: questions: -
limitations: limitations: The authors adequately addressed the limitations.
paper_summary: paper_summary: This paper theoretically explores the deep neural collapse (DNC) phenomenon within non-linear deep models for multi-class classification. Neural collapse (NC) is a phenomenon in deep overparameterized networks where, the last layer's feature vectors align with class means and their corresponding classifier vectors, while also maximizing separation between classes. Previous works have studied the propagation of this symmetric geometry to earlier layers and proved its optimality which is termed as DNC. These works focus on DNC's optimality in multi-class linear networks or binary non-linear networks. This paper, however, extends the analysis to multi-class non-linear deep networks with ReLU activation, using the deep unconstrained features model (DUFM), where input features are treated as unconstrained parameters in the training objective.

While in the binary or linear case, DNC was shown to be optimal across all layers of DUFM, the authors show that in the multi-class case and in the presence of non-linearity, DNC is not always optimal. They prove this by explicitly constructing a solution, called SRG, that achieves a lower objective value than DNC. They show SRG is rank-deficit and the rank/loss gap between SRG and DNC increases as the network becomes deeper or the number of classes increases. They further numerically show on DUFM that, although DNC is not optimal, wider networks have an implicit bias toward finding the DNC solution. To further support their findings, they conduct additional experiments on benchmark datasets MNIST and CIFAR10 and ResNet architecture.
strength_weakness: strength_weakness: The proof of non-optimality of DNC in the paper relies on constructing a solution (SRG) that has a lower objective value. However, SRG might not be optimal. So, showing that SRG has a lower rank does not necessarily mean that the optimal solution also follows this low-rank structure. Still, the results and observations presented in this work remain interesting.
questions: questions: 1. As discussed in the paper, the last-layer feature vectors before the activation ($\tilde{M}_L$), have a lower rank, and after activation ($M_L$) recover the full rank structure of NC. This is also clear from Fig. 2 (right). However, what I find missing is whether after activation $M_L$ follows the NC geometry or not, i.e., $M_L \propto I_K$? Or does it follow a different rank $K$ structure?

2. Line 263 mentions that only for a few runs the training solutions match SRG. In the rest of the runs, do the solutions achieve a lower objective value than SRG (thus proving that SRG is a local optimal at best)?

3. What about $W_\ell$'s? Do they also exhibit a similar low-rank structure in the SRG solution as well as the numerical experiments? 

    I also don't see why DNC3 is not well-defined in this setup (line 250). Still, at optimality, we might have the mean feature vectors $M_\ell$ and classifiers $W_\ell$ align in a low-rank structure. This alignment property doesn't hold in either the SRG or SGD solutions in the experiments?

4. Is there a small typo in Fig. 4 caption? The bottom right heatmap cannot be $M_5$ since the features after ReLU are non-negative and the heatmap cannot have negative values.
limitations: limitations: Yes
paper_summary: paper_summary: Deep Neural Collapse (DNC) refers the the neural collapse phenomenon that has been observed on intermediate layers of a deep network (nb. whereas neural collapse (NC) focuses only on the penultimate layer). Similar to Unconstrained Feature Model (UFM) for analyzing NC, Deep UFM (DUFM) is the comparable framework to study DNC. However, as opposed to UFM for NC, it's been observed that once you go beyond two layers or two classes, DNC is no longer optimal for DUFM. 

In this paper, the authors suggest that the reason for this is a low-rank bias of commonly used multi-layer regularization schemes, meaning the low-rank bias leads to optimal solutions that are lower rank than the neural collapse. 

This paper extends the current research by looking at DUFM when there are more than two classes and the model is non-linear. Previous work has focused only on DUFM for binary classification with non-linear models or deep linear models or shallow models with multiple classes.

Most notably, they show that in this more complicated setting, DNC is not optimal wrt DUFM. Namely, the class means fail one of the original conditions of NC; i.e., they fail to form an orthogonal frame. The authors suggest that the reason for this is the low-rank bias under L2 regularization. It is worth noting that the condition DFC1 (which states within class variability goes to zero) is still optimal and it's only the DNC2 property (which states that class means are orthogonal) that conflicts with the low-rank bias.

Their findings are supported with strong theoretical proofs and empirically on benchmark datasets such as MNIST and CIFAR10.

One of the main takeaways from this paper is that…if a DNC solution is found, it is not because of DUFM or global optimality. Instead, it is because of an implicit bias of the optimization procedure.
strength_weakness: strength_weakness: Based on my understanding of the current work, I don't see any major weaknesses. I have some minor points of clarification or questions below but no major flaws.
questions: questions: line 209 (clarification): Does the statement regarding K=2 or L=2 indicate that the argument of your theorem also be used to show DNC is optimal in this setting as shown in [51, 48] or are you just saying that as comparison when K=2 or L=2 by [51, 48] we know DNC is in fact optimal?

line 343: why the MSE loss? I didn't catch that part.

(typos/nits)
line 206 (typo): according to Theorem 5, should L \geq 3 be replaced with L = 3?
limitations: limitations: N/A
paper_summary: paper_summary: The paper studies the optimality of neural collapse in intermediate layers of a deep neural network on classification tasks with more than 2 classes.

1. The paper shows that the NC2 property (formation of a simplex ETF/orthogonal frame) in the intermediate layer features is not optimal, and constructs a strongly regular graph (SRG) based lower-rank solution leading to lower loss than previously proposed deep neural collapse (DNC) optimal solutions.

2. The NC1 property (variability collapse of features) is still shown to be optimal in these settings.
strength_weakness: strength_weakness: 1. There seems to be an error in the Sherman-Morrison formula-based inverse in the final result of Lemma 12, i.e, $(I + \frac{1}{r-1}11^\top)^{-1} = I - \frac{1}{2(r-1)}11^\top$. (The authors can correct me on this). Since this result is used in Lemma 13 and affects the results in Theorem 5, verifying this result is important.

2. Can Definition 4 be split into multiple parts for better readability? For instance, split it into parts w.r.t:

- collapsed class means are unaffected by non-linearity.
- The class means are scaled versions of $T_r$ where each row is scaled individually.
- Choice of $A_L$ for the final layer.

This breakdown highlights a major assumption that the non-linearity is not in effect till the last layer. Additionally, the complete set of trainable and non-trainable parameters should be made clear. The full definition in Appendix A.1 mentions extra trainable terms corresponding to $q$ terms.

3. In section 6.1 (DUFM training) Figure 2 (first row, last column), the plots for the singular values of class means seem to have a rank of around 7 or 8 for intermediate layers as well. The ideal rank $K=10$ might not exactly hold for intermediate layers but these observations should be discussed since it is one of the main claims in the paper. 

4. The experimental results in section 6.3 for MNIST datasets claim that the network trained using gradient descent is the SRG solution. A justification for this observation is missing. The heatmap for MNIST in Figure 4 corresponds to $M_5$ which as per notation indicates the class-means of the penultimate layer post-activations. However, shouldn't the SRG solution correspond to similar heat maps across intermediate layers? Also, a statement such as low-rank implying an SRG solution is not justified.
questions: questions: 1. Do numerical experiments with the 5-layer MLP head include a ReLU activation for L-DUFM and end-end training?

2. The authors mention in section 6.3 that "We also observe that the rank deficiency is the strongest in the mid-layer of the MLP head". Can further justification be provided for this? Especially which aspect of the spectrum of Layer 3 or 4 in Figure 5 justifies this observation? 

3. Since the SRG solution relies on feature class means being non-negative, how valid is this assumption (based on your practical experiments)?

nit: In the notation for $H_L = \sigma(W_{L-1}X_{L-1})$ in section 3, shouldn't $X_{L-1}$ be replaced with $H_{L-1}$ ? The same applies to $\widetilde{X}_l$.

nit: Please fix the formula for NC1 in the first line of section 6. The pseudo-inverse is not required when dividing the traces.
limitations: limitations: N/A

Comments: title: Effective ranks for Figure 4
reply
Area Chair to Authors
comment: For completness of the discussion, we computed mean effective ranks (computed as exponential of the entropy of singular values after normalizing to sum one) for the two series of experiments in the Figure 4. Here are the results: 

CIFAR10: {'layer_1_er': 8.96, 'layer_2_er': 7.46, 'layer_3_er': 6.88, 'layer_4_er': 7.04, 'layer_5_er': 7.73, 'layer_5_er_post_relu': 9.52}

MNIST: {'layer_1_er': 6.82, 'layer_2_er': 5.43, 'layer_3_er': 5.37, 'layer_4_er': 5.44, 'layer_5_er': 6.12, 'layer_5_er_post_relu': 9.47}

Although the main message of our paper is orthogonal to to these quantitative values, they still reinforce our side claim that the low-rank bias is most pronounced somewhere in the middle of the MLP head, something we discussed previously. Thanks for suggesting this, there is indeed some value to these numbers, we will add them to the manuscript.
Thank you. We can now incorporate this review.
Dear Area Chair,

I kept my review brief as I think the contributions are clear and significant, and the manuscript is well-written. As you requested for further justification, I would like  to provide additional comments on why I believe this manuscript is very strong:

i) The paper builds upon the foundational work by Papyan et al., who identified neural collapse at the terminal phase of training. By extending this analysis to earlier layers in nonlinear deep neural networks, the authors address an important gap in the literature. This extension provides a more comprehensive view of how neural collapse manifests across the entire network, not just in the final layer. Previous research following Papyan's work primarily focused on simple models such as linear networks and indicated that deep neural collapse is optimal across all layers. To my knowledge, it is the first work showing that neural collapse may not be optimal in certain layers of certain models.

ii) The manuscript makes significant theoretical contributions. Specifically, Theorem 6 provides evidence that the convergence to class means in neural collapse is optimal for all layers. As most of the models used in practice have many layers, it extends the application of neural collapse significantly. Conversely, Theorem 5 challenges the validity of the within-class variability condition under certain conditions, suggesting that there are scenarios where performance could be optimized beyond the classical framework. These theorems provide new insights that could reshape existing theories and practices about how deep neural networks work.

iii) The authors support their theoretical claims with many experimental results. The experiments not only validate the theoretical findings but also provide practical insights into how the neural collapse phenomena can be observed and leveraged in real-world scenarios.
Authors: Unfortunately this review will not be considered as part of the decision, unless the reviewer updates their review to include a justification of the score. The reviewer has already been reminded twice, but the review is unusable in its current form.
Thank you for your appreciation.
Thank you for your appreciation.
Thank you for reconsidering your evaluation. 

Thank you for suggesting using effective ranks, it is an interesting idea. We will shortly report results with effective rank measures in the revision. However, to best convey our message the best rank measure is hard rank or its thresholded approximation.
Thanks for your detailed response. I find the results interesting, and I believe clarifying these additional points can help with the message. I'll maintain my score.
Ok. Thank you for the clarification. I have no further concerns. I'll keep my score as it is. Nice work.
Thank you for addressing the concerns. I have increased my score based on the responses.

One more suggestion to consider [optional]
- I think it would be better to also quantitatively measure the rank. For example, a simple measure such as effective-rank can be used. If the notion of a low-rank used here is purely qualitative, and quantitative measures have limitations [if any], then such a discussion can further improve the paper quality.