Deep Neural Collapse Is Provably Optimal for the Deep Unconstrained Features Model
Authors: Peter Súkeník
Marco Mondelli
Christoph H Lampert
Venue: NeurIPS 2023 spotlight (2023)
Keywords: neural collapse
unconstrained features model
deep learning
TL;DR: We prove the optimality of deep neural collapse for the deep unconstrained features model - an extension of the unconstrained features model to arbitrarily many layers - for binary classification, and we provide experiments to support our theory.

Abstract: Neural collapse (NC) refers to the surprising structure of the last layer of deep neural networks in the terminal phase of gradient descent training. Recently, an increasing amount of experimental evidence has pointed to the propagation of NC to earlier layers of neural networks. However, while the NC in the last layer is well studied theoretically, much less is known about its multi-layered counterpart - deep neural collapse (DNC). In particular, existing work focuses either on linear layers or only on the last two layers at the price of an extra assumption. Our work fills this gap by generalizing the established analytical framework for NC - the unconstrained features model - to multiple non-linear layers. Our key technical contribution is to show that, in a deep unconstrained features model, the unique global optimum for binary classification exhibits all the properties typical of DNC. This explains the existing experimental evidence of DNC. We also empirically show that (i) by optimizing deep unconstrained features models via gradient descent, the resulting solution agrees well with our theory, and (ii) trained networks recover the unconstrained features suitable for the occurrence of DNC, thus supporting the validity of this modeling principle.

Deep Neural Collapse Is Provably Optimal for the Deep Unconstrained Features Model
Peter Súkeník
Marco Mondelli'
Institute of Science and Technology Klosterneuburg, Austria peter swkenikkista. .c.at
Institute of Science and Technology
Klosterneuburg, Austria
marco. marroo.mndelli@istaa ac. at
Christoph H. Lampert" Institute of Science and Technology Klosterneuburg, Austria chl@ist. ac. at
Abstract
Neural collapse (NC) refers to the surprising structure the last layer of deep neural networks in the terminal phase of gradient descent training. Recently, an increasing amount of experimental evidence has pointed to the propagation of NC earlier layers of neural networks. However, while the NC in the last layer is well studied theoretically. much less is known about its multi-layered counterpart deep neural collapse (DNC). In partieular, existing work focuses either on linear layers or only on the last two layers at the price of an extra assumption. Our paper fills this gap by generalizing the established analytical framework for NC the unconstrained features model to multiple non-linear layers. Our key technical contribution is show that, in a deep unconstrained features model, the unique global optimum for binary classification exhibits all the properties typical of DNC. This explains the existing experimental evidence of DNC. We also empirically show that (i) by optimizing deep unconstrained features models via gradient descent, the resulting solution agrees well with our theory, and (ii) trained networks recover the unconstrained features suitable for the occurrence of DNC, thus supporting the validity of this modeling principle.
Introduction
In the thought-provooing paper (22), Papyan el al. uncovered a remarkable structure in the last layer of sufficiently expressive and well-trained deep neural networks (DNNs). This phenomenon is dubbed "neural collapse" (NC), and it has been linked to robustness and generalization of DNNs. In particular, in [22] it is shown that all training samples from single class have the same feature vectors after the penultimate layer (a property called NCI); the globally centered class-means form a simplex equiangular tight frame, the most "spread out" configuration of equally-sized vectors geometrically possible (NC2): the last layer's 's classifier vectors computing scores for each of the classes align with the centered class-means (NC3); finally, these three properties make the DNN's last layer act as nearest class-center classifier on the training data (NC4).
The intriguing phenomenon of neural collapse has spurred flurry of interest aimed understanding its emergence, and the unconstrained features model (UFM) (21) has emerged as a widely accepted theoretical framework for its analysis. In this model, one assumes that the network possesses such
"qqual contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

10
DNC1
10
DNC2
DNC3
layer_ 1
Inyer_1
10a
10a
layer_2 2
layer_a
10
leyer
layer_2
10-1
layer
2_pre_ relu
10a
10
10 2
10
layer__
10
10-
layer 2
10
layer 3
10
10
epoch
epoch
1c3
epoch
1e3
Figure 1: Deep neural collapse metrics as a function of training progression. On the left, DNC1 measures within-class variability collapse (the closer to 0, the more collapsed); in the middle, DNC2 measures closeness of feature activations to orthogonal frame (the closer to 1, the more collapsed); and on the right, DNC3 measures alignment between feature activations and weights (the closer to O, the more collapsed). The ResNet20 recovers the DNC metrics for DUFM, in accordance with our theory. This validates unconstrained features as a modeling principle for neural collapse.
expressive power that it can represent arbitrary features on the penultimate layer's 's output. Thus, the feature representations of the training samples on the penultimate layer are treated as free optimization variables, which are optimized for (instead of the previous layers' weights). Since its introduction.
the UFM has been understood rather exhaustively, see e.g. (21 19 31
12 42
and Section 2
Most recently, researchers started to wonder, whether NC affects solely the last layer. The "cascading neural collapse" is mentioned in [11] where it is pointed out that NC1 might propagate to the layers before the last one. Subsequently, mathematical model to study this deep version of NC has been proposed in [28). albeit only for two layers; and a deep model has been considered in (2). albeit only for linear activations. On the empirical side, the propagation of NC1 through the layers is demonstrated in [8). and the occurrence of all the NC properties in multiple layers is extensively measured [26]. All these works agree that neural collapse occurs to some extent on the penultimate and earlier layers, leaving as key open question the rigorous characterization of its emergence.
To address this question, generalize the UFM and its extensions in 28 to cover an arbitrary number of non-linear layers. We call this generalization the deep unconstrained features model (DUFM). The features, as in the original UFM, are still treated as free optimization variables, but they are now followed by an arbitrary number of fully-connected layers with ReLU activations between them, which leads neural collapse (DNC). Our main contribution is to prove (in Section 4 that DNC is the only globally optimal solution in the DUFM, for a binary classification problem with l2 loss and regularization. This extends the results in (28 and (2) by having more than two layers and non-lincarities, respectively. While the statements of (28) are formulated for an arbitrary number of classes, here we restrict ourselves to binary classification. However, we drop an important assumption on the features of the optimal solution made by 28 (see the corresponding Theorem 4.2 and footnote 3), which was only verified experimentally. In a nutshell, we provide the first theoretical validation of the occurrence of DNC in practice: deep neural collapse gives a globally optimal representation of the data under the unconstrained features assumption, for any arbitrary depth.
natural setup to investigate the theoretical underpinnings of deep
In addition our theoretical contribution, numerically validate in Section 4.2 the occurrence of DNC when training the DUFM with gradient descent. The loss achieved by the DUFM after training agrees well with the theoretically computed optimum, and the corresponding solution elearly exhibits the properties described by our main result. Finally, to check whether the main assumption of the DUFM the unconstrained features- is relevant in practical training, we show that DNNs trained on CIFAR-10 can indeed represent features suitable for the occurrence of DNC. In particular, (i) we pre-train a small DUFM to full collapse, (ii) attach the fulne-con layers (DUFM without the unconstrained features) to the end of a randomly initialized CNN, and finally (ii)) train the CNN with the DUFM's weights fixed. The plots in Figure [ show that the backbone recovers the unconstrained features leading to DNC. This is quite remarkable, as the collapse, being data-dependent, completely breaks after exchanging the trained unconstrained features with the output of the randomly initialized backbone. Additional details can be found in Section 4.2

---

2 Related work
Since the original paper [22]. neural collapse has been intensively studied, with [21 introducing the now widely accepted unconstrained features model (UFM), also called layer peeled model. In particular, the work on NC can be loosely categorized into (i) the study of the mathematical grounds behind NC 31 19
37.. (ii) the development of a connection between [6 and (iii) empirical observations concerning NC B5 20 The first line of work can be further divided into (i-a) a static analysis. that studies the
12 NC and DNN performance [22 5
29 36
global optimality of NC on suitable objectives 31
19
40
28 42 12, and (i-b) dynamic analysis,
that characterizes the emergence of NC in training with gradient- based methods [2 7 12 30). The
vast majority of works uses the UFM to derive their results, but there are attempts to derive NC
without it, see c.g. [25 33 23
24
14, 38). For additional references, see also the recent survey [13]
More specifically, 331 19 show global optimality of NC under UFM, when using the cross-entropy (CE) loss. Similar optimality results are obtained in 40 28 for the MSE loss. For CE loss, class-imbalanced setting is considered in B], where the danger of minority classes collapsing to a single representation (thus being indistinguishable by the network) is pointed out. This analysis is further refined in [27]]. where a generalization of the ETF geometry under class imbalance is discovered. On the edge between static and dynamic analysis are results which characterize the optimization landscape of UFM. They aim to show that all the stationary points are either global optima (thus exhibiting NC) or local maxima/strict saddle points with indefinite Hessian, which enables optimization methods capable of escaping strict saddles to reach the global optimum. For the CE loss, this property is proved in [42] and [12), while in the MSE setup this insight is provided by [4] A unified analysis for CE, MSE and some other losses is done in [I]. The convergence of the GD dynamics to NC is considered in 21 under MSE loss for near-zero initialization. The more refined analysis of (7) reveals that the last layer's weights of UFM are close to being conditionally optimal given the features and, assuming their exact optimality, the emergence of NC is demonstrated with renormalized gradient flow. For CE loss, 212 shows that gradient flow converges in direction to the KKT point of the max-margin optimization problem, even without any explicit regularization (unlike in the MSE loss setting). As the optimal solutions of this max-margin problem exhibit NC, this yields the convergence of gradient-based methods to NC as well. Quantitative results on the speed of convergence for both the MSE and CE losses are given in (30]
Most relevant to our paper, the emergence of NC on earlier layers of DNNs is empirically described in 8 26 4. In particular, it is demonstrated in [ that, at the end of training. the NC1 metric decreases -inealle with depth, thus showing a clear propagation of neural collapse. Most recently, the propagation of all the NC properties beyond the last layer is studied in (26). for setting that includes biases. On the theoretical side, the UFM with multiple linear layers is considered in [2]. where it is shown that NC is globally optimal for different formulations of the problem. The first result for a non-linear model with two layers (separated by a ReLU activation) is given by (28]. There, it is shown that NC, formulated in the bias-free setting, is globally optimal. However, additional assumption on the optimum is required, see the detailed discussion in Section
3 Preliminaries
Notation. Let N = Kn be the total number of training samples, where K is the number of classes and n the number of samples per class. We are interested in the last L layers of a DNN. The layers are counted from the beginning of indexing, i.e., the L-th layer denotes the last one. The layers are fully connected and bias-free with numbers of imput neurons
> 1 and weight matrices W1 E Rdd2xd; W2 E Rd2xd2_ ..... W,, E I8 1gxxx xx,, Let H, R H2 d ....,,,, Hr, E Rd XNN be the feature matrices before the application of the ReL.U activation function, which is denoted by i.e., H2 = W2 H, and H, = 1 (1) for 2 When indexing a particular sample, we denote by ( the i-th sample of the c-th class in the 1-th layer, i.e., a particular column of Hi. Moreover, let Me
(1) = - N be the activation class-mean for layer / and class and Hi the matrix containing (1)
(!)
Me the e-th column. For convenience, the training samples are arranged class-by-class (first all the samples of first class, then of the second, etc.). Thus, the label matrix containing the one-hot
encodings! Y E KXN can be written as Lg % 17 where IK denotes K x K identity matrix, &
3

---

denotes the Kronecker product and 1, row vector of all-ones of length n. With this, we can write Hi HTx & 1,) and we further denote of Hi) (H)) & I,).
Deep neural collapse. Since we assume the last L layers be bias-free, we formulate a version of the deep neural collapse (DNC) without biases (for formulation including biases, see [26)
Definition 1. The deep neural collapse at layer is described by the following three properties
DNCI:
The within-class variability after 1 layers is This property can be stated for the features either before or after the application of the acfivation function a. In the former case, the condition requires 1t l1 for all i, j. E [m] (or, in matrix notation, Hi = Hi @ 1, in (.)) for all i, E [n] (or, in matrix notation, o o(fi) = a (H) @ 1
the latter, a(h = o (1
DNC2: The feature representations of the class-means after I - layers form an orthogonal matrix. As for DNCI, this property can be stated for features either before or after a. In the former case, the condition requires H Hi Ik: in the latter, (HH)
"I' (Hi) Tk-
DNC3: The rows of the weight matrix Wi are either 0 or collinear with one of the columns of the class-means matrix a (Hi).
Note that, in practice, DNNs do not achieve such properties exactly, but they approach them as the training progresses.
Deep unconstrained features model. Next, we generalize the standard unconstrained features model and its extensions 228 2 to its deep, non-linear counterpart.
Definition The L-layer deep unconstrained features model (L-DUFM) denotes the following optimization problem:
1
Aw 2
AH.
min H
|
2 P
+
H
11
WL
2N
2
1=1
(1)
where |1-|| denotes the Frobenius norm and λH Aw - Awe
0 are regularization parameters.
4 Optimality of deep neural collapse
We are now state our main result (with proof sketch in Section 4.1 full proof in Appendix A Theorem 3. The optimal solutions of the I.-DUFM ( for binary elassification (K- 2) are s.l.
(L (I-1)
(Hi, Wi...., WE) exhibits DNC, if ndH, AWL < 24+1
(2)
More precisely, DNCI is present on all layers; DNC2 is present on (HH) for 2 2 and on Hi for I 2 3; and DNC3 is present for I 2. The optimal Wf, Hi do not necessarily exhibit DNC2 or DNC3. If the inequality in (2) holds with the opposite strict sign, then the optimal solution is only (Hi, wi..., W;) 00,0..... 0).
In words, Theorem 3 shows that, unless the regularization is so strong that the optimal solution is all-zeros, the optimal solutions of the DUFM exhibit all the DNC properties. Notice that (2) requires the per-layer regularization be most of order (LL+1) which is very mild restriction. If the condition in (2) holds with equality, the set of optimal solutions includes (i) solutions exhibiting DNC, (ii) the all-zero solution, and (ii)) additional solutions that do not exhibit DNC.
We highlight that Theorem 3 holds for arbitrarily deep non-linear unconstrained features models. This is significant improvement over both (28). which considers L 2, and (2). which considers the linear version of the DUFM. Furthermore, Theorem 4.2 of 28 has a similar statement for two layers
NC often involves additional fourth property the last layer acting as nearest class classifier. This property is well defined only for networks including biases, hence will not consider it here.

---

(although without considering the DNCI property on H1, H2), but it requires the extra assumption
[oo(H))l Il.. || ll., where ||-Il. denotes the nuclear norm. In particular, the argument of (28
crucially relies on the fact that ( |l. < H2 ll.- We remark that the inequality [MMMl < [|MI. does not hold for a generic matrix M (see Appendix
B for counterexample) and, at the optimum, it is only observed empirically in 28). In summary, our result is the first to theoretically
address the emerging evidence [26] 4 that neural collapse is not only a story of a single layer, but
rather affects multiple layers of DNN.
4.1 Proof sketch for Theorem
First, denote by S() an operator which takes any matrix A E R as an input and returns the set of minfe, f singular values of A. The singular values are denoted by 8; and ordered non-increasingly. We specifically label St,j the j-th singular value of (H,) for 1 2 2.
The argument consists of three steps. First, assume n 1, and prove that the optimal solutions of the L-DUFM problem exhibit DNC2-3 (as stated in Theorem 3). Second, we consider ni > 1 and show that DNCI holds. Third, we conclude that DNC2-3 hold for > 1.
Step 1: DNC2-3 for n = 1. The idea is to split the optimization problem ( into a series of simpler sub-problems, where in each sub-problem we solve for fraction of the free variables and condition on all the rest. Crucially, the optimal solutions of all the sub-problems only depend on the singular values of a (HH), for / 2 2. Thus, the final objective can be reformulated in terms of S(o I 2 2. By noticing that the objective is symmetric and separable w.r.t. the first and second singular values of the matrices, we can solve separately for {st, JesiSL and 2 At this point, we show that these separated problems have unique global optimum, which is either 0 or element-wise positive (depending on the values of the regularization parameters AH,, Aw,
for
AW,). ). Hence, the optimal $t will be equal for j and j = 2, which in turn yields that a (H)) is orthogonal. Finally, using the intermediate steps of this procedure, we are able to reverse- deduce the remaining properties.
We now sketch the step of splitting the problem into L sub-problems. As the 1-th sub-problem, we optimize over matrices with index L-/+ and condition all the other matrices, as well as singular values of {a H22 (keeping them fixed). We start by optimizing over WL and then optimize over Wi for 2 < 1 < L- (for all the optimization problem has the same form and thus this part is compressed into single lemma). If L = 2, we do not have any for which 2 < I < L L- 1 and, hence, we skip this part. Finally, we optimize jointly over W1, H1. We start by formulating the sub-prot sub-problem for WL.
Lemma 4. Fix H1, WI...., WL-1. Then, the optimal solution of the optimization problem
Awz
min WL
WWooWW W20(W, (W - 12
W|
2
is achieved at WT = (H + +2W,, Ia and equals
Aw + 2( 2Xww))
Aw.
(3)
2( 22w,)
The proof follows from the convexity of the problem in W,, and simple form of the derivative, the corresponding lemma in Appendix A for details.
We remark that the solution 3 resulting from the optimization over W, depends on a (Hr) only through the singular values s $1 SL,2 Thus, we can fix $L,1, $L2 and H1, WI...., WL-2, and optimize over WL-1 (provided L objective depends only on s1,1, $L-1,1, 8 1,2. Thus, we can now fix 9111,1, SL-1,2 and H1, Wi...., WL-3, and optimize over W (provided L 2 > 1). The optimal solution will, yet again, only depend on the singular values of a (H,-1), a (HL-)). Thus, we can fix $ $L-2,2 and H1 W1, Wi...., WZ-4 and repeat the procedure (provided L - > 1). In this way, we optimize over W, for all 1 2 2.
1). It turns out that the resulting optimal value of the
We formulate one step of this nested optimization chain in the following key lemma. Here, X abstractly represents H,-1 and {81, 82) represent (81,1 812] A proof sketch is provided below and the complete argument is deferred to Appendix A
5

---

Lemma's 5. Let X be any fixed two-column entry-wise non-negative matrix with at least two rows, and let its singular values be given by { S Then, for a given pair of singular values {81,82) and a given dimension d 2 2, the optimization problem
min W
s.t. {si, 82) = ((o(W))),
further constrained so that the number of rows of W is d, has optimal value equal to
82
82
if is full rank. If X is rank 1, then the optimal value is #1 as long as = 0, otherwise the problem in
is not feasible. If X = O, then necessarily $1 = = =0 with optimal solution O, otherwise the problem is not feasible.
Proof sketch of Lemma 5 Notice that, for any fixed value of the matrix A == [i==oWXi X), there is at least one W which achieves such a value of A, unless the rank of A is bigger than the rank of X, in which case the problem is not feasible (as mentioned the statement). Therefore, we can split the optimization into two nested sub-problems. The inner sub-problem fixes an output A for which {s1, }2} = S(A) and optimizes only over all W for which A = o(W The outer problem then takes the optimal value of this inner problem and optimizes over all the feasible outputs A satisfying the constraint on the singular values. We phrase the nested sub-prohe bob-problems as two separate lemmas.
Lemma 6. Let A with columns a, b and X with columns x. y be fixed two-column matrices with at least two rows, where X entry-wise non-negative Then, the optimal value of [[]]] subject to the constraint A = a (W X) is
a a y² Tb xT 1 6 xTx
(4)
x² x 1 (x 1)
unless x and y are aligned. In that case, the optimal value is y" and we require that a, b are aligned and Ily|l / ||=|==||00 [|b|| / ||a]
6Tb
for the problem be feasible. Moreover, the matrix W X at the optimal W is non-negative and thus W X o(W* X). If the matrix X is orthogonal, then the rows of the optimal W are either 0, or aligned with one of the columns of X.
Proof sketch of Lemma 0 The optimization problem is separable with respect to the rows of W, hence we can solve for each row separately. As the problem is convex and has linear constraints, the KKT conditions are necessary and sufficient for optimality. By solving such conditions explicitly and computing the objective value, the result follows. The details are deferred to Appendix A L
Now, we can plug 4 into the outer optimization problem, where we solve for the output matrix A given the constraint on singular values. We only optimize over the numerator of 4 as the denominator does not depend on the variable.
Lemma Let X be a fixed entry-wise non-negative rank-2 matrix (the rank-1 case is treated separately later) with columns y and A = oWW The minimum of the following optimization problem over this non-negative matrix A with columns a, b.
min d"bz"" x -2a bxx y + aT d'ay"u y.
S.1. S(A) {21
(5)
is ( $Z) 32 + ( (B) $2), where (31, S(X).
Proof sketch of Lemmal 7 The optimization problem (5) is non-convex and has non-linear constraints. It is still solvable using the KKT conditions, however some care is required as such conditions no longer necessary and sufficient. Using the Linear Independence Constraint Qualification (LICQ) rule, handle the necessity. Then, by solving for KKT conditions and comparing the objective value with solutions for which the LICQ condition does not hold, we obtain the desired description of the optimal solution. The details deferred to Appendix
At this point, we are ready to obtain the result of Lemma 3 82 * 0 then, by combining the result of Lemma 7 with (4), the proof is complete. If ž O. we can optimize {4. given 82 0 and the extra constraint a" =²z b ""y which follows from the requirement on the rank of A and the fact that X has rank The claim then follows from direct computation of the objective value using the constraint. The case 3 32 0 gives that X = 0, and is trivial. D

---

So far, we have reduced the optimization over {2i) to the optimization over the singular values of {o) We now do the same with the first layer's matrices W1, H1. For this, we again split the optimization of Awr || 11 + Ar || given {*1, (W, H))) into two nested sub-problems: the inner one performs the optimization for a fixed output H2 == W1 H1; the outer one optimizes over the output H2, given the optimal value of the inner problem.
The inner sub-problem is solved by the following Lemma, which describes a variational form of the nuclear norm. The statement equivalent Lemma C.I of (2]] Lemma 8. The optimization problem
AA 2
AB |B| 2
min A. A.BBC
|All
(6)
minimized at value VAAAB ||C and the minimizers are of the form A = - B By RT Here, the constants "A, YB only depend on X AB; UEVI T is the SVD of C; and is an orthogonal matrix.
To be more concrete, we apply Lemma with A = W and B H1 (so that C W1 H2). Thus, we are only left with optimizing H2ll. given S(o(H2) = {s1,,2), 82). We solve this problem in the following, much more general lemma, which might be of independent interest. Its proof is deferred to [
Lemma 9. Let L 2 2 be positive integer. Then, the optimal value of the optimization problem
min |
11
S(o(H)) $2)
equals (s1 + 52) Here I--ls, denotes the p-Schatten pseudo-norm.
Remark 10. As a by-product of the analysis in the proof of Lemma we obtain characterization of the minimizers of (7). which will be useful in Step 2. Let H" be an optimizer of (7). Then, o (HH)) has orthogonal columns. For L 2, its negative entries are set uniquely so that H² has rank 1. For L L= 2, its negative entries are arranged as follows. All the rows of a (H*) which contain exactly one positive entry on the first colunn will result in rows of H* that are multiples of each other. Similarly, all the rows of a (H") which contain exactly one positive entry on the second column will result in rows of H" that are multiples of each other. The zero rows of a ((H)) remain zero rows in H Moreover, the l2 norm of the negative entries of the rows of H* with positive entry in the first column equals the 22 norm of the negative entries of the rows of H* where the positive entry is in the second column. Finally, taking any two rows of H with counterfactual positioning of the signs of the entries, the product of negative entries does not exceed the product of positive entries.
Armed with Lemma 5 and 9 we reformulate the L-DUFM objective | only in terms of {st,1, 81,53 We then split this joint problem into two separate, identical optimizations over {st, and {11.2 JasIEL. which are solved via the lemma below (taking zi si, and x; == si.2 respectively). Its proof is deferred to Appendix A
Lemma 11. The optimization problem
min 2 + 2dW,))
AWL
Σ
Aw
Ii+1
V AwidHi vo
(8)
2 In
is optimized at entry-wise positive, unique solution if
II TIw. (L (1-1) 24+1
AH.
(9)
and at (2:2. (22....,IL) xL) = (0, ... 0) otherwise. When (9) holds with equality, both solutions are optimal. Here, 0/0 is defined to be O.
Note that (9) is equivalent to when = 1. Furthermore, if the optimization problem (8) has single non-zero solution, then the optimal si,1 and si are forced to coincide for all L. From this, we obtain the orthogonality (HH)) for > 2. Lemmaa6]thnn gives that the optimal Hí for 1 must be orthogonal as well, since it is non-negative and equal to o (H Finally, the statement about WT for 2 also follows from Lemma 6 This concludes the proof of DNC2-3 for n 1. As a by-product of Lemma g we additionally obtain a precise characterization of the optimal WT. HJ
7

---

W,) would achieve a smaller loss Step 2: DNC1 for n > 1. Now, we assume n > 1 and the conclusion of Step 1. We show that DNC1 holds for the optimizer of (T. We give a sketch here, deferring the proof to Appendix A
We proceed by contradiction. Assume there exist Hi, W :..... WI which achieve the minimum of LT. but Hi does not exhibit DNC1. Note that the objective in ①I is separable w.r.t. the columns of H1 Thus, for both classes E {1,2}, 2}, the partial objectives corresponding to the columns { J of Hi must be equal for all i. Indeed, if that is not the case, we can exchange all the columns of fij with the ones that achieve the smallest partial objective value and obtain a contradiction. Now, we can construct alternative Hi such that, for each class c, we pick any (1) and place (1)
it instead of ( fzzi. By construction, Hz exhibits DNCI and it is still an optimal solution. At this point, let us construct Hi from Hi by taking a single sample from both classes. We claim that (Hi, W ..... Wi) is an optimal solution of (1) with n = 1 and nAH, as the regularization term for H1, while kceping .j..... dg, and Aw..... Aw, the same. To see why this is the case, consider an alternative G1 achieving a smaller loss. Then, (G7 @ 1 than (Hi, Wi..... WE), which contradicts its optimality.
Recall that Hi is an optimal solution of ( with = 1. By Step 1, the columns 2,y of o (H2) are such that z. 2 0, zTy = 0, and x = |y/| (here, by the notation x 2 0 we mean an entry-wise inequality). Assume o (H3) * O. First show that z, y and thus the whole or (H2)) are uniquely determined by (Wr, Wi...... Wi))
For this we use the uniqueness of the scaling obtained in Lemma 11 and the DNC3 property for the (o(H)) W2) pair. Then, by Lemma 9 all the matrices A2 such that a (A2) = (H3) and || = =| I~ have columns of the form x ty, y to for t [0, 1]. Let A5 be matrix of that form for particular f. A series of steps which include computing the SVD of AG and the usage of Lemma 8 reveal that, among 0 S t < 1, there is a single t and
A = A5" such that WT solves the optimization problem (6) in Lemma if H2 = AG. Thus, having fixed AA that can be the output of the first layer, this in turn gives the uniqueness of the unconstrained features 11, solving O while W1 = Wi, Hl,- = HY Ag. However, as 1ł is not DNCI collapsed by assumption, there are multiple possible choices for Hi and then Hi, which gives a contradiction with the uniqueness of H₃ solving (6).
Step 3: DNC2-3 for n > 1. Having established DNCI, we obtain DNC2-3 by reducing again to the case n = 1, which allows us to conclude the proof of the main result. We finally remark that W and Hi do not need to be orthogonal, due to the E1/2 multiplication in the statement of Lemma g This means that Wf and Hi may not exhibit DNC2-3 (as stated in Theorem 3)
4.2 Numerical results
DUFM training. To support the validity of our theoretical result and to demonstrate that the global optimum the DUFM can be found efficiently, we conduct numerical experiments which we solve ① with randomly initialized weights using gradient descent. In Figure we plot the training progression of the DNC metrics for two choices of the depth: L = 3 (first row) and L = 6 (second row). In both cases, we use 50 training samples and constant layer width of 64. The learning rate is 0.5, though smaller learning rates produce the same results. We run full gradient descent for 10" steps, and the weight decay is set to 5 10-4 for all the layers. The plots are based 10 experiments and the error bands are computed as one empirical standard deviation to both sides. To measure the DNC occurrence, we plot the following metries as a function of training. For DNC1, we define 2/y = 1 2
! - p y as the within-class variability at layer Ei (1) ( (( 0. (1) as the between-class variability, where ((()) is the global feature mean at layer I. Then, the DNCI metric at layer is |[Ew E with being the pseudo-inverse operator. This is an upper bound on the trace of the same matrix, which is sometimes used in the literature for measuring NC1. An ideal DNC1 would show 0 on this metric. For DNC2, our metric at layer 1 is given by fL11 (recall that these are the singular values of o (H))), and we consider the feature matrices both after and before the ReLU activation. An ideal DNC2 would show I on this metric. For DNC3, we consider the weighted average sine of the angles between each row of W2 and the closest column of o (Hi); the weights are the l2 norms of the rows of Wi. To avoid
N
I and 20 = 2 (nC - PG (ue
8

---

DNC2
10
leyer_ _1
10a
leyer 1
10
10
ltyor_2 2
layer_3 3
layer
10
layer_2. 2_pre_relu
10
10
10"²
layer
10
10
layer_2
1000
layer
3
10-12
19
20
100
40
60
step
leB
step
step
DNC2
UNC1
layer_1
109
10a
keyer_1 1
layer_?
10
leyer_3
keyer
10a
leyer 3
10-2
byor_4
layer
layer_1
9
layer_5
layer 2
10
layer 6
layer_
Bayer_2_re__re_
10
layer 3
10
10-0
layer_5
19-15
10
10
layer_6
50
100
100
step
step
1c3
step
163
Figure 2: Deep neural collapse metrics as a function of training for the DUFM objective ( The first
(second) row corresponds L = 3 (L. 6). The metrics corresponding to DNC1 and DNC3 very small, and the metric corresponding to DNC2 is close to I, which means that the solution found by gradient descent exhibits neural collapse in all layers, as predicted by Theorem
numerical issues, we exclude rows of Wi whose l2 norm is smaller than 10- An ideal DNC3 would show 0 on this metric.
The plots in Figure
follow the predictions of Theorem 3 and, taken as a whole, show that DUFM training via gradient descent clearly exhibits deep neural collapse, for all the three metrics considered, and for both depths. More specifically, DNC1 progressively achieved in all layers, with the layers closer to the output being faster. DNC2 is achieved for all (Hi) with / 2 and H1 for 2 3 (though we didn't 't include this in plots to avoid too many lines) and, as predicted by our theory, it not achieved on H2 (the dotted line in the middle plot) and on H2 (the blue line). Interestingly, for these numbers of layers, SGD does not find solutions which would exhibit DNC2 on H1, even though such solutions exist. Hence, gradient descent is not implicitly biased towards them, see Appendix [Cfor a more detailed discussion. DNC3 is achieved on all layers even on the first, which not covered by our theory and where the effect is the most pronounced; the deeper layers achieve values of DNC3 of order 10-2, which translates into an angle of less than one degree between weight rows and feature columns. Finally, we highlight that the training loss matches the optimal value computed numerically via (17) (the corresponding plot is reported in Appendix ( and hence the solution found by gradient descent is globally optimal. Additional ablation studies concerning the number of layers, weight decay and width of the layers are reported in Appendix C
ResNet20 training with pre-trained DUFM. We support the validity of DUFM modeling principle for deep neural collapse via the following experiments. We first train an L-DUFM for L= with K 2 and 5000 to full optimality, as the previous paragraph. Then, we replace Hi with the output of a randomly initialized backbone, we fix the weight matrices in the DUFM, and we train end-to-end convergence on the classes 0 and of CIFAR-I0. 10. In Figure we report the DNC metrics of our 3-DUFM head, as the training of the backbone ResNet20 progresses. While the start of the training the features H₃ are random and, therefore, the model does not exhibit DNC, the ResNet20 recovers well the DNC properties after training. This suggests that the crucial assumption of DUFM the unconstrained features, indeed holds practice. The plots are based on 7 experiments with confidence bands of one empirical standard deviation to both sides. Additional details as well as the experiments with 5-DUFM and VGG13 and DenseNet122 are discussed in Appendix D

---

5 Conclusion
In this work, we propose the deep unconstrained features model (DUFM) - a mullti-aayered version of the popular unconstrained features model - as tool to theoretically understand the phenomenon of deep neural collapse (DNC). For binary classification, we show that DNC is globally optimal in the DUFM. This provides the first rigorous evidence of neural collapse occurring for arbitrarily many layers. Our numerical results show that gradient descent efficiently finds a solution in agreement with our theory- one which displays neural collapse in multiple layers. Finally, we provide evidence in favor of DUFM as a modeling principle, by showing that standard DNNs can learn the unconstrained features that exhibit all DNC properties.
Interesting open problems include (i) the generalization to multiple classes (K 2), (ii) the analysis of the gradient dynamics in the DUFM, and (iii) understanding the impact of biases on the collapsed solution, as well as that of the cross-entropy loss, As for the first point, a crucial issue is to control [|W; ll.. since the inequality [M) S ||M does not hold for general matrices M. In addition, while Lemma 5 still appears to be valid for K (and would be an interesting stand-alone result), its extension likely requires new argument.
Acknowledgments and Disclosure of Funding
M. M. is partially supported by the 2019 Lopez-Loreta Prize. The authors would like sincerely thank Eugenia lofinova, Bernd Prach and Simone Bombari for valuable feedback to our manuscript.
References
[1] Ido Ben-Shaul and Shai Dekel. Nearest class-center simplification through intermediate layers. In Topological, Algebraic and Geometric Learning Workshops, 2022.
[2] Hien Dang. Tan Nguyen, Tho Tran, Hung Tran, and Nhat Ho. Neural collapse in deep linear network: From balanced to imbalanced data, arXiv preprint arXiv:2301.00 000437,0077 2023.
[3] Cong Fang, Hangfeng He, Qi Long, and Weijie J Su. Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training. In Proceedings of the National Academy of Sciences (PNAS), volume 118, 2021.
[4] Tomer Galanti, Liane Galanti, and Ido Ben-Shaul. On the implicit bias towards minimal depth of deep neural networks. arXiv preprint arXiv:2202.09028. 2022.
[5] Tomer Galanti, András György, and Marcus Hutter. Improved generalization bounds for transfer learning via neural collapse. In First Workshop on Pre-training: Perspectives, Pitfalls, and Paths Forward at ICML, 2022.
[6] Jarrod Haas, William Yolland, and Bernhard T Rabus. Linking neural collapse and 12 normal- ization with improved out-of oif-iistribttion detection in deep neural networks. Transactions on Machine Learning Research (TMLR), 2022.
[7] X. Y. Han, Vardan Papyan, and David L Donoho. Neural collapse under mse loss: Proximity to and dynamics on the central path. In International Conference on Learning Representations (ICLR), 2022.
[8] Hangfeng He and Weijie Su. A law of data separation in deep learning. arXiv preprint ar 77020, 2022.
[9] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference computer vision (ICCV), 2015.
[10] Arthur E Hoerl and Robert W Kennard. Ridge regression: Biased estimation for nonorthogonal problems, In Technometrics, volume 12, 1970.
[11] Like Hui, Mikhail Belkin, and Preetum Nakkiran. Limitations of neural collapse for understand- ing generalization in deep learning. arXiv preprint wr.Xi:22022.83360 2022.
10

---

[12] Wenlong Ji, Yiping Lu, Yiliang Zhang, Zhun Deng, and Weijie J Su. An unconstrained layer- peeled perspective on neural collapse. In International Conference on Learning Representations (ICL.R) 2022.
[13] Vignesh Kothapalli. Neural collapse: A review on modelling principles and generalization. In Transactions on Machine Learning Research (TMLR), 2023.
[14] Daniel Kunin, Atsushi Yamamura, Chao Ma, and Surya Ganguli. The asymmetric maximum margin bias of quasi-homogeneous neural networks. arXiv preprint arXiv:2210.03880) 2022.
[15] Xiao Li, Sheng Liu, Jinxin Zhou, Xinyu Lu, Carlos Feranndez-Granda, Zhihui Zhu, and Qing Qu Principled and efficient transfer learning of deep models via neural collapse. arXiv preprint arXiv:2212. /2006, 2022.
[16] Zexi Li, Xinyi Shang, Rui He, Tao Lin, and Chao Wu. No fear of classifier biases: Neu- ral collapse inspired federated learning with synthetic and fixed classifier. arXiv preprint arXiv:2303. 10058, 2023.
[17] Tong Liang and Jim Davis. Inducing neural collapse to a fixed hierarchy- frame for reducing mistake severity. arXiv preprint arXiv:2303.0568) 2023.
[18] Weiyang Liu, Longhui Yu, Adrian Weller, and Bernhard Schölkopf. Generalizing and decoupling neural collapse via hyperspherical uniformity gap. In International Conference on Learning Representations (ICLR), 2023.
[19] Jianfeng Lu and Stefan Steinerherger. Neural collapse under cross-entropy loss. In Applied and Computational Harmonic Analysis, volume 59, 2022.
[20] Jiawei Ma, Chong You, Sashank J Reddi, Sadeep Jayasumana, Himanshu Jain, Felix Yu, Shih- Fu Chang, and Sanjiv Kumar. Do we need neural collapse? Learning diverse features for fine-grained and long-tail classification. 2023.
[21] Dustin G Mixon, Hans Parshall, and Jianzong Pi. Neural collapse with unconstrained features. arXiv preprint arXiv:2011.11611 2020.
[22] Vardan Papyan, X. Y. Han, and David I. Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. In Proceedings of the National Academy of Sciences (PNAS), volume 117, 2020.
[23] Tomaso Poggio and Qianli Liao. Explicit regularization and implicit bias in deep network classifiers trained with the square loss. arXiv preprint arXiv:2101.0000 2020.
[24] Tomaso Poggio and Qianli Liao. Implicit dynamic regularization in deep networks. Technical report, Center for Brains, Minds and Machines (CBMM), 2020.
[25] Akshay Rangamani and Andrzej Banburski-Fahey Neural collapse in deep homogeneous classifiers and the role of weight decay. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2022.
[26] Akshay Rangamani, Marius Lindegaard, Tomer Galanti, and Tomaso Poggio. Feature learning in deep classifiers through intermediate neural collapse. Technical Report, 2023.
[27] Christos Thrampoulidis, Ganesh Ramachandra Kini, Vala Vakilian, and Tina Behnia. Imbalance trouble: Revisiting neural-collapse geometry. Conference on Neural Information Processing Systems (NeurIPS), 2022.
[28] Tom Tirer and Joan Bruna. Extended unconstrained features model for exploring deep neural collapse. In International Conference on Machine Learning (ICML), 2022.
[29] Tom Tirer, Haoxiang Huang, and Jonathan Wiles-Weed. Perturbation analysis of neural collapse. arXiv preprint 22X1:22110.6668,, 2022.
[30] Peng Wang, Huikang Liu, Can Yaras, Laura Balzano, and Qing Qu. Linear convergence analysis of neural collapse with unconstrained features. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022 2022.

---

[31] E Weinan and Stephan Wojtowytsch. On the emergence of simplex symmetry in the final and penultimate layers of neural network classifiers. In Mathematical and Scientific Machine Learning, 2022.
[32] Liang Xie, Yibo Yang, Deng Cai, and Xiaofei He. Neural collapse inspired attraction-repulsionn balanced loss for imbalanced learning. In Neurocomputing. 2023.
[33] Mengjia Xu, Akshay Rangamani, Qianli Liao, Tomer Galanti, and Tomaso Poggio. Dynamics in deep classifiers trained with the square loss: Normalization, low rank, neural collapse, and generalization bounds. In Research, volume 6, 2023.
[34] Yibo Yang, Liang Xie, Shixiang Chen, Xiangtai Li, Zhouchen Lin, and Dacheng Tao. Do we really need learnable classifier at the end of deep neural network? Conference on Neural Information Processing Systems (NeurIPS), 2022.
[35] Yongyi Yang, Jacob Steinhardt, and Wei Hu, Are neurons actually collapsed? on the fine-grained structure neural representations. In Can't Believe It's Not Better Workshop: Understanding Deep Learning Through Empirical Falsification (NeurIPS 2022 Workshop), 2022.
[36] Can Yaras, Peng Wang, Zhihui Zhu, Laura Balzano, and Qing Qu. Neural collapse with normalized features: A geometric analysis over the riemannian manifold. arXiv preprint arXi::2209.092// 2022.
[37] John Zarka, Florentin Guth, and Stéphane Mallat. Separation and concentration in deep networks. International Conference on Learning Representations (ICLR), 2021.
[38] Jiayao Zhang, Hua Wang, and Weijie Su. Imitating deep learning dynamics via locally elastic stochastic differential equations. In Conference on Neural Information Processing Systems (NeurIPS), 2021.
[39] Zhisheng Zhong, Jiequan Cui, Yibo Yang. Xiaoyang Wu, Xiaojuan Qi, Xiangyu Zhang, and Jiaya Jia. Understanding imbalanced semantic segmentation through neural collapse. arXiv preprint arXiv: 100, 2023.
[40] Jinxin Zhou, Xiao Li, Tianyu Ding, Chong You, Qing Qu, and Zhihui Zhu. On the optimization landscape of neural collapse under mse loss: Global optimality with unconstrained features. In International Conference on Machine Learning (ICML), 2022.
[41] Jinxin Zhou, Chong You, Xiao Li, Kangning Liu, Sheng Liu, Qing Qu, and Zhihui Zhu. Are all losses created equal: A neural collapse perspective. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
[42] Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu. geometric analysis of neural collapse with unconstrained features. In Conference on Neural Information Processing Systems (NeurIPS), 2021.
12

---

A Proofs
Theorem 3. The optimal solutions of the L-DUFM
① for binary classification (K = 2) are s.t.
(Hi, WT.... Wi) exhibits DNC, if ndn, ....., (1-1) (1-1)66-1
(2)
2
More precisely, DNCI is present on all layers; DNC2 present on o oHH;) for forl= 2 2 and on H for 1 2 3; and DNC3 is present for I 2 2. The optimal Wf. H₃ do not necessarity exhibit DNC2 or DNC3. If the inequality (2) holds with the opposite strict sign, then the optimal solution is only (H7, WT WT) = (0,0, ..)))) 0).
Proof. We will split the proof into two distinct cases: and n > The proof for will require the statement to hold for = 1, so we start with this case. The explicit form of the problem goes as:
L Aw 2
AH 2
min Hy W. 2N
- 1211
[ F
|1 (10)
We will solve this problem using sequence of L sub-problems, where in sub-problem 1, we only optimize over matrices with index L- I+1 and condition on all the other matrices, as well as singular values of all o (H₂) for / 2 2 (keeping them fixed). Throughout the process, will strongly rely the crucial phenomenon that the optimal solutions of all the sub-problems will only depend on the singular values of the matrices a (HI). We will solve the problem starting from the last weight matrix Wi. through WT-1 and so on, and finishing with the joint optimization over W1, H1. We divide this procedure into 4 lemmas. The first lemma will only treat Wz. The second lemma will treat Wi for 2 < / S -- 1. This lemma will only be used if L 2 3. The third lemma will treat W1, Hi jointly and the fourth, final lemma will then treat the only free variables left the singular values of a (Hi) for all 2 2. Let us denote by S(.) an operator which returns a set of singular values of any given matrix (in full SVD, i.e. the SVD with number of singular values equal to the smaller dimension of the matrix). Moreover, let st, be the i-th singular value of a (Hi).
Lemma 4. Fix H1, W1, WL-1 Then, the optimal solution of the optimization problem
Awz.
min We
W 11) 12
achieved at W2 (o
22w lae) and equals
Awz
Awz
2( + 2 + 2( + 2Aw,))
Proof. This is well-known fact from the theory of ridge regression [0]. However, for readers'
convenience, we do the proof here too. If we denote the objective of this as L, then we get:
1 Oc = (WLO(HL) (H)) Xw, WL
awl
2
Since the objective is strongly convex in WL, the unique global optimum is found by setting to 0 the derivative. Solving for it, have
W₂ = (HL)) (HLL) + law)
Let denote (HHr) UEVT the rectangular SVD of (Hz) where U Rdx E Rd x2 V E _x22 Writing the optimal Wt in terms of SVD of (HH)) we get:
Wz = VYT U UU T + +2w,, lde) )
= "UTUTU('N" + lde) -UU -UT
= =VE" + 2Aw, la.))
13

---

Therefore, we obtain the SVD of WL and that (ΣΣ) + 2Aw, Iar)) Wr. from which we obtain:
is a matrix of singular values of
$2,5
W
i + 2Xw; )2
Furthermore, the first summand of the objective is
[[WLo(Ht)) -211 = ||VE (ΣET + +2W2, lde) - - -12 12112
= |I(E"* (ΣET + 2Aw, Taa))
- -12
$7
2
$ + 2Xw
Putting everything together, we get the following optimal value of the objective:
2
$
AWZ
2
$
4
L +
2dWL
2
( + 2Aw, )2
1=1
1=1
2
AW,,0r of
((
22 )2
2(57.. + 2xw,) )2
AWL
2(. + 2\w.))
which gives the desired result.
Note that the term we optimized for is the only part of the objective (10) which depends on Wr. Now we are ready to state the crucial lemma (necessary when L 2 3), which is presented in an abstract way so it can be easily applied outside of the scope of this work.
Lemma 5. Let X be any fixed two-column entry-wise non-negative matrix with at least two rows, and let its singular values be given by (51, = S(X). Then, for a given pair of singular values {s1, (2) and given dimension d 2 2, the optimization problem
min W
|
S.I. {81, 82) = ((o(W))),
further constrained so that the number of rows of W is d, has optimal value equal to
81
82
82
if X is full rank. 1f X is rank 1, then the optimal value is 51 as long as 82 = 0, otherwise the problem 55
is not feasible. If X = O, then necessarily 81 82 0 with optimal solution 0, otherwise the problem is not feasible.
A= (W X), there is at least one W which achieves such value of A, unless the rank of A is bigger than the rank of X, however this is special case explicitly mentioned in the statement of the lemma for which the problem is non-feasible. Therefore, we can split the optimization into solving two nested sub-problems. The inner sub aub-problem fixes an output A for which {8), 52) = S(A) and optimizes only over all W for which A = ( X). The outer problem then takes the optimal value of this inner problem and optimizes over all the feasible outputs A satisfying the constraint on the singular values. We will phrase both of the nested sub- problems as separate lemmas:
Proof. Notice that, for any fixed value of the matrix A:
Lemma 6. Let A with columns b and X with columns x, y be fixed two-column matrices with at least two rows, where X is entry-wis non-negative. Then, the optimal value of [[]]] subject to the constraint a (WX
a 8 y 2n T y + bFb TT
(4)
x² x n y - (x y)²
14

---

unless x and y are aligned. In that case, the optimal value is bCt J" and we require that a, b are aligned and Ilyll / || [[6|] / ||a for the problem be feasible. Moreover, the matrix W at the optimal W is non-negative and thus W X = oW X). . If the matrix X is orthogonal, then the rows of the optimal W are either 0, or aligned with one of the columus of X.
Proof. Note that this optimization problem is separable in rows of W. Thus it suffices to solve the problem for a single row wy and then sum up over all rows. We will, moreover, split the analysis into two cases.
Case 1: Here will assume that the row of A In this case, we are facing the following (simple) convex optimization problem:
optimizing for is (aj.by) where aj, by 0.
min "yy
||,
s.t. w x aj
w y bj
This has known solution - the pseudoinverse as it is the minimum interpolating solution a two-datapoint linear regression. However, using the formula would not simplify the expressions in the slightest and so we will solve this problem manually. The Lagrange function for this problem is
[(wj, 0)
Σ jj
Σ Wyy: 0j +
)
Σ WjsStt (onn-by by
where d is the dimension of the columns of X and rows of W. We know that solving the KKT conditions for a convex problem with linear constraints yields sufficient and necessary conditions for the optimality. Let write:
dc
2w + un, + uy: 0.
Owzz
Together with constraints, these the only KKT conditions for this problem. Solving for wye get:
ur. - 0y
Wis 2
(11)
Plugging in the constraints we get:
uy + uz,yi = =uy" + ux. -2bs-
Σ 1=1
u.x. vi ux x vx y -2aj.
We can solve for e from the first equation and plug in to the second equation. Since y y must be non-zero, otherwise the constraint w/f y bj could not be satsfied, know and well-defined. We get:
2b y 2a,y x xzy y (x y)2
(12)
unless ay, which we will deal with later. Now can plug in the expression and after some computations we get
2a,x" y 26,0"'x x xJ Toy y (xT y)²
v
Combining, we get the optimal wy
byr² a,5² y
any² y byo" y
2 xyy (x y)
I xzyy (x y)
x = ay. then it is clear from 12 that byx y = a,y"
TT y. from which we can deduce a = az/by.
From the expression (T] for Wyt. is clear that the only solution in this case is wy - and the same must hold for all other j E {l....,d) d). where d is the number of rows of W.
15

---

Case 2: Here we will assume that the row of A we are optimizing for is, w.l.o.g. (a,, 0), where
aj 0. In this case, we are facing the following (simple) convex optimization problem:
min |
s.t. w/ x z= aj
w リ S
Again, we can write the Lagrange function for this problem and again, solving for KKT conditions will provide full description of the optimal solution:
d
L(w,, u, v)
W
2
w W + v
Σ 8 Wj 0j
We obtain the same condition for Wij as in case 1. However, since one of our constraints is now an inequality, we will deal with complementarity conditions. Let us first assume that In that case Wji -ux; and from the first constraint
2aj Σ x
Thus, wy -. However judging from this, to satisfy the first constraint, must have r.t 0 for all (remember that Σ Wjilh must be non-positive and that z,y have non-negative entries). Therefore necessarily x² = O. However, looking at the solution of case 1, we see that after plugging in x²y y = and b, = 0, we get the same expression. Thus, this is a special case of case 1. The second option for complementarity condition is that Edjii = O. Then, we can proceed in the same way as in case to obtain the same formula after plugging in b = O. Then again, this a special case of the formula in case 1.
All in all, we have fully solved the optimization problem in question. Now it remains to compute the optimal value. In the special case that x ay, we must have bx" ay y. otherwise there is no feasible solution. In this case this equivalent to a a/b, wj b y)y and wif w; - (1/ v). Therefore, summing over all rows of W (and keeping mind that once x ay. 5"b 4
the same characterization holds for every row) we get || 1|
In the general case, let compute:
byx² x - a,2²
+ a y - 6 b,5t - 1 a b,r²Hyy
wT w; = xº ayy y (x y)2
xF xT (x 1)²
(5 xT (xf y)
(b,x² x -=a===zppp ) v y 2(0,22 x- a,x"
F) + (a.v y b, xTT
2)
63(x" 2)² 2b xy yx" + (1""" 26,a, xy yonyyz'n y 263 x y)²
-2a3v² u( 7) + ab, (2 4) + +d 2bjaza xy yu y + (xTT))2²
(Fry'yy 2)
b3(=T2))'' 62 xxx
T 3) a (v 1) v3y" y( y(=Ty) y)² 2a, xyyp" y ba,b,
(x ry y (x u)22
(b3TTx x + a² 2a by 7) ry y - (x y)
xxt xy y (x - 2)
1T x 2a 20, a" ry (x" y)
03
Summing up over rows of W, we get the desired expression:
6 bz'bx" x 2a bat y + a" azz
|
ITaY" (xTn)²
The rest of the statement of the lemma clearly follows from the formula on optimal rows of W.
16

---

Now, promised, we will optimize over the output matrix A given that we know what the partial optimal value for each A is.
Lemma 7. Let X be a fixed entry-wise non-negative rank-2 matrix (the rank-1 case is treated separately later) with columns z, y and A = (). The minimum of the following optimization problem over this non-negative matrix A with columns a, b:
min b² bxx x 22 bxx y + a² avy" y.
S.I. S(A) {5)
(5)
is
33 + (s] ( $2). where 181,82) S(X).
Proof. First note that since X is assumed to be rank 2, x * ay and so the expression in the objective exactly the numerator of the optimal value of the minimization problem over W stated in Lemma (the denominator is constant within the scope of this lemma). Now, using the well-known formulas for the sum and product of squared singular values, we can easily rephrase constraint in the following way:
a'a+b'b + 8 ^ a² ab² (n= 52.2.
a²a, First, noticing that both the constraints as well as the objective only depend on a² a, b" b, a² b, reduce the problem to one, where treat these quantities as free variables that optimizing for. The only thing we need to remember will be implicit constraints that a² a, b²bb 2 0 and b)² < a ab² b, which necessary from Cauchy-Schwarz inequality. We will solve this optimization problem using, again, KKT conditions. This time, we will use a stronger rule for deciding on the necessity of KKT conditions the linear independence constraint qualification (LICQ) rule. According to this rule. any optimal solution has to fulfill the KKT conditions if the gradients of the equality constraints (in this case only two) are linearly independent. In our case. if we order the variables as (a" b, a b²bb) and writing the gradients as: (1, 1, 0) and (b a a, 20,-24 -2a b) we see that they can only dependent if b and a² a bbb. This is only feasible solution We will return to this case later, showing that it achieves the same objective value as the one coming from KKT conditions.
Now, let us write down the Lagrange function to this problem:
L(a a, b",,bbbbbb
b, a b. v) =a T ay y 2a bx y + b" bx x ula a b ot --s)) -
+ +o(a" o b (a b)² siS5)
Computing the partial derivatives we get:
dc
Da y" + + vb b 0,
x² ITx x + + va=a -L-0 0,
ThTh
Da -2x vea T 1 0.
OC
First consider what would happen if v = 0. In this case, xTy = from the third equation and JTx: yT y from the first two. Then, however, the objective function is constant on the feasible set and equals 1 1/ + (3? + 22), which agrees with the statement of the Lemma.
Next, assume + 0. Then we can express all the variables as follows:
=T x
a'a
a
v bTb 4 y
a b x y
Plugging this back into the constraints, we can solve for u, u. We get:
xJ x
y/
2u
57 +
17

---

Plugging this into the second constraint together with the expressions for a² a. b and then simplify- ing we get:
(0" y + ()" () +3)2
(5" + s2)²
= 8/
(a x + y 2u)² (x²x+ y"y y + 2u)²
v² ya=x= (x" + (y" y xT x)u + +u²
8182
(x x + v v)
89 + 82
23132
28182
(1" x + 30 y)
u²
of +
87 +
(5) -
62)2 62)²
(5) 53
To x + +1 u + J.T xy
TT y - (x y)
8182
(x x + y y²yy²= = 0
+ $3)
(59 + 83
o7 + 82
(6) + 2 2
n² + (x x + y² y)u +
T ry
T y (x v)
8182
(x y² yf)² 0. (13)
(s} s2y
Recall that the case $1 82 is treated separately, so we do not divide by zero. Now we can rewrite this expression w.r.t. {$1.
(s] +
2 + (5 + 5 u
(3) + 82) =
{5} - 2
(0] - -3
We now simply solve for this to obtain the roots:
{ 52) (57 + 53)2
45733 (o
(57 83)2
(5 (8+
( 3733
M
2
which after some simplifications yields:
2 (57
82 -9-
(5)
$2
U+
The formula for can now be obtained:
Having this, we can now compute the objective value using these quantities. We write it down for U U4
- -xxTx x +
y)u
2(xTT.) y (xTu)²)
67 bx a ayy 2a Taabx""
- + 55) 25753 33)+
(5
35) +33) 45733
8-
2v
(2) (o}
8
35) + (sf 3 33) + 33) +
43
G + 3
53)
(5
5 83)
2
2
which is the expression we wanted to prove. Had we done the same computation, but for u_, we would get
(5} + 5
+ +
- - -3
2
which is at least as big as the previous expression, so we can drop this one. However, we still need to check, whether this solution of the KKT system is indeed feasible, because we imposed implicit constraints into the problem. Thus, we need to check: a" a, bTb b 2 0 and a" ab 2 (a b)2. The first two are analogous. We have: a can only analyze the sign of 2x T + 2u which is:
z'zta but since the optimal v4 strictly negative, we
3 2
2x x + 2u = x T x
y y
+
(3)
I
-TTT x y yl 2 0. 22
5
18

---

However, using the same formulas as the constraints in this optimization problem on $1, $2 instead, one can, using very simple computations, check that this indeed holds. For the next condition, consider that a² abb" b ba must have the same sign as (x² x: + u) y + u) x. *=ryyy y - (x²"y)² y)² + u² u(x=xx + y" y). This resembles the quadratic function root of that quadratic function. Both this new quadratic function, as well as the one in
(x²y)² y)²
13 44 is a
13 have the
same coefficients front of u² and u. Therefore, to test for the sign of the expression above, it only
suffices to check, whether this alternative quadratic function has at least as big absolute constant:
x ry y - (x v)
(0) +
(x
TayTyyy Ty (x v)) +
xy
5192
(0
T
+ y u) 20
(0]
)2
81
82
1 (5f $2
0132
$1
18
82
+ (sf 2) 2
(31 22) 2 0 (5f
2 2 2 0.
2
The last inequality trivially holds. Therefore, the solution of KKT conditions is feasible.
Now, let us consider the special case when a² 0, a= a bab and 82 for which the LICQ criterion is not satisfied. A very simple computation then yields that any feasible solution achieves the same objective value as the one above. This means that if the problem does have a global solution, it must be this one, otherwise the optimal solution would neither satisfy a KKT condition, nor be in the region where LICQ does not hold. Therefore, we must, finally, reason that this is indeed globally optimal solution, which is not guaranteed by KKT conditions themselves. For this, it is only necessary to note that the feasible set is obviously compact. Since the objective value is continuous, we can use the well well- fact that such an optimization problem indeed has a global solution. O
Now we are ready to finish the proof of Lemma combining @ommaooiit Lemma 7 we get:
Let us first still assume 31. 82 > 0. Then,
|W] 2
min
W
s.t. (() {s1,
equals
(sf + +2) (5? + $3
(s}
(5)
s
82
28132
82
Now consider the case &2 0. According to Lemma this implies 82 0. When optimizing over the matrix we are facing the following optimization problem:
6%b b
min y y
{81, s.t. S(A)
aTo x T x yTy"
bTh
where the second constraint clear from the considerations done in Lemma Combining these two constraints, one simply gets
8Tb y"u and plugging this in the objective value we have which is consistent with the statement of 37 Lemma 7 The case when X is O is trivial. This proves Lemma 5
IT x + v
Notice that, for all indices but = 1, we managed to reduce the optimization over full matrices Wi to the optimization over only the singular values of (H₂) matrices. We will do the same with the first
layer's matrices W1. H1. For this, we again split the optimization of Aw; [| Av, || || given 2
[81, = (WW(W, H))) into two nested sub-problems, the inner one optimizing the quantity only for a fixed output H2 := W, H, and the outer one optimizing over the output H2 given the optimal
value of the inner problem. We can solve the inner subproblem by direct use of the following lemma, which describes a variational form of nuclear norm.
19

---

Lemma 8. The optimization problem
AA
+ A |B 2
min A,B:C=AB
||ll
(6)
2
and the minimizers are of the form A = ~>AU> R², B In RE Here, the constants "Y,, only depend on XA An; UEVI is the SVD of C; and R an orthogonal matrix.
is minimized at value AB
||
Proof. See Lemma C.1 of 28
Using this Lemma g we know that the optimal value of the inner optimization problem is v Aw,An, |2ll. Therefore we only need to solve the outer problem:
min H2
H2
s.t. (H2)) {81, 82).
To solve this problem, will state much more general statement, which can be of independent interest, in the following lemma.
Lemma 9. Let L 2 2 be positive integer. Then, the optimal value of the optimization problem
min
H
S(o(H)) 82}
equals (#1 + 82) Here I--ls, denotes the p-Schatten pseudo-norm.
Proof. First note that this optimization problem has two free components: (i) or ((H) so that it satisfies the constraint, and (ii with (HH) being fixed. This enables us to split the problem into inner and outer minimization. However, the complexity of the problem will prevent us from doing this conditioning in a straightforward way. Further, us also implicitly note that within the proof we implicitly assume the matrix in question has least three rows. The case with two rows is very simple and follows the proof with more rows.
We start by explicitly computing the objective value as function of important statistics of H. Let (H) have columns r, Then,
(T r²'s (T ST')
o oH)
Using the well-known formula on the eigenvalues of such matrix, we know λι + A2 -f= 8 and bι r 2 (v'2's 5)2 Solving this system we get:
- of ( + 5F A(rIrsT's (TT')22
22 = A1.2
(14)
Let us, for now, fix this a (H). For while will only optimize over H a (HH) is fixed. We will think about the optimization problem in the following way: consider any 5 2 0. Assume we allowed to "inject" negative values in the place of zero entries of fixed (H) so that the of squares of those negative entries is exactly 5. What is the minimal value of the objective value given this and what the optimal injection? Let denote any quantity which was subject such injection (or perturbation) with an extra lower-index P.
To answer this question, first have closer look at (14). It is clear that after injecting the negative noise of total squared size ò, the -frp + spap in a perturbed matrix will increase by exactly 5 compared to o" + sTs. s. Therefore, if we condition on 8, the only degree of freedom lies in (rTss)²) in the perturbed matrix. Crucially, since the objective value is 1/5. + >2,,, by concavity of L/h power, for any fixed sum of λ1,P + dg, = + sT's we want the A to be as far apart as possible. This obtainable by maximizing the quantity -4(rFrpofp> (rffsp)2) which is equivalent to minimizing rfrpsf.sp (rfsp))2 Importantly, as it will be clear from the forthcoming reasoning, the minimal value of A2, is decrcasing with
the -4 -4rffrps
20

---

5. Therefore, it only makes sense to consider all the d values for which the minimal X2.P is still bigger than up to the value for which the minimal X2 hits for the first time. From that 5 on, every optimal 22 is O, but the AI, increases and thus becomes sub-optimal. Now let us split the 5 into ó1 and d2, denoting the total squared size of perturbations per column. If we also fix 61 and 82 and condition on them, even the quantity rfpppspsp is fixed and we are left with maximizing (r. Denote p = rT s. To make the next argument clear, let us split the matrix a (H) into four blocks of rows, where in each block there is one of the four following types of rows: +); (+, 0), +), (0.0). We will now define variables a, b, b, d as sum of squared entries corresponding to one column of one block. Specifically:
a Σ
(H)
b
E
(H)
no (0,0
Σ (H)
Σ
d
Σ
oH)
(0(()))0000000=000
t: (=)()))=000(())000
The value we are trying to minimize equals, for unperturbed o (H) written in this way, (a + c)(b d) - p². Of course, a (H) () might not have all the types blocks, in which case the empty sum is just defined as O. First, we argue that whatever is the optimal assignment of the negative values given 61, d2. they do not appear in both the (0, 0) block and (+. 0). (0, +) blocks. This is because the only variable are optimizing for in this conditioning is (rpsp)² Assume that, given the perturbation, the quantity r is negative. Then, any negative values present in the (0, () block can be moved to (+.0). (0, +) blocks strictly decreasing rpsp and thus increasing )2) On the other hand, if Tpp happens to be positive, then any negative values present in the (), (0, +) blocks can be moved to the (0,0) block, strictly increasing the rfsp value and thus (rfsp)² too. Therefore, we only need to consider cases when we inject the negative values either the (0, 0) block to (+. O), (0. +) blocks, but not both at once. Let us start with the second case and analyze it. Clearly, if of)) did not have either the (0, 0) block or (+, 0), (0. +) blocks, then we do not even need this reasoning anymore. Also it is clear, as we will see later, that a matrix o (H) which would completely lack entries suboptimal and thus there is always space to inject negative entries.
Case 1: Injecting negative values to (+, 0). (0, +) blocks. For the same definition of a, b, c, d as above, we further define the squared sizes of total injected negative values in the perturbed Hp per block as x, y, i.e.,
Σ
HP
Σ
HP
x
y
i (H)
( (
and thus x = 62, y 51, x + y 5. Trivially, such a construction only makes sense it is possible to make rfosp negative, otherwise it is strictly better to construct an alternative matrix (H) with a + c ā 7 - d = - d: p = F. but which includes the (0, 0) block and put all the negative value there (this is always possible for matrices with at least 3 rows, since we only need two rows to construct or (H) which satisfies the outlined constraints). This alternative matrix together with negative values in the (0, 0) block would be better, because obviously (TP" (TPT3p)* 3p)² 2 (rāsp)?.
Once 8 is negative, though, it is clear that it optimal, given the resources X, y. to produce as negative value as possible so as to maximize (r By the use of Sauchy-Schwart inequality, this is possible exactly when the injected negative vectors in the blocks are aligned with their positive counterparts of that block. Then, the inner product between the negative and positive part of a block will equal exactly ver or Vydd. Furthermore, if it is possible to construct (H) for which a+ō < a+ = a a b+d b+7 = b+d; == = (which is only possible if there are at least two rows in
the (+, +) block and pf ab- thanks to the fact that then the angle between columns in the (+,+) block is free variable and we can decrease it while decreasing a, b to keep p unchanged using the law of cosine), then our objective value strictly decreases, since Ver V Vei+ +V Therefore, it is always optimal for the first and second column of the (+.+) block to be aligned, which also yields ab 22. This value of p is necessary also if the (+, +) block has only one row. Thus, we have that the original value of n "T""" s- s)"s)² is (a + cb + d) - ab. The value after perturbation, using all the knowledge we acquired so far is (a+c+ (bb
(Vab - vcr 2 Subtracting, we get difference: by + + zy 2 Vabe + abd /J 2 2/cd /zy. Consider now an alternative
21

---

matrix Hp such that y y remain unchanged and moreover ā = = 0, a +b++d=++++++++ d and ēd = (a + c) + d) - ab, meaning that the o (Hp) has the same singular values as o (HH)). However, computing the same difference of the same quantities one gets: xy 2V /ay. This value is strictly smaller than the previous one for any fixed pair of x; Therefore, a matrix (H) which does not contain the (+.+) block the only possible optimal solution for the injection which goes into (+,0). (0, +) blocks. Thus, we can reduce the previous problem into considering matrix Hp with = b = 0 and minimizing the difference in objective values zy 2/ed//ry fry, given J + y = After plugging in y = - x, differentiating for x and putting equal to 0, we get 5 2x 26
Ved = 0. From here, we cd (8 2x) = 0, which is equivalent to (ō - 2x) /
see that either = 8/2 or cd z(66 -)), which after solving yields T1,2 1 If 82 I 4od then the only stationary point is 6/2 and this is clearly an optimal solution. For 8² 4ed, the optimal solution yields rank matrix so that λ2 = 0. This means we do not need to care about 5² > 4cd, as this would not achieve smaller value of P2, P. but would increase the value of A1, So, the solution where x = y = 5/2 optimal and the objective value is / s1 $1520. This is clearly smaller than so we actually achieved decrease in objective value.
Case 2: Injecting negative values to (0, 0) block. For this, it is not necessary distinguish (0, +)) blocks, so we treat them as one. We can define:
Σ
OHH
f= Σ
(H)
to
Σ
(H)
Σ
o(H)
y
(
The original objective value is ef -p², while the perturbed one is (e + xz - (p + /zy)² and so the difference is xf yee - 2py. However, using Cauchy-Schwarts inequality, this is bigger or equal to xf + ye - 2/Jery 2 0. Thus, it is not possible to improve the objective value in this case, unlike the previous case where it was. Therefore, this case is clearly sub-optimal and we do not need to deal with it.
The only thing that could potentially go wrong with this proof is that there is not enough rows to build our necessary blocks. This can only happen if (H) is 2 2 matrix. This case is, however. very simple and we will not explicitly treat it, but the statement and the proof path are the same for it.
We solved our optimization problem for every fixed allowed perturbation size 8. Now we just need to optimize over 0 < 8 < 22. So we face the following optimization problem:
$t + 2 +
2o + + + 0)2 4(573 5 (3/4-111200 s1820)
1
min 25
2
2
8
22 + 1
t
2 V (sf + 5)2 4(s7 52/4 -s1520
+
2
Denote 1 the value of the first summand of the above objective value (without 1/L-th power) and similarly A8,2 the value of the second summand (so those are the eigenvalues of optimal H.H.Ppp given exactly 8 allowed negative injection). The derivative of the objective w.r.t. ö equals:
(8) + 82)²
(8) + 82)²
2
+
+
2/2 2
L-I nAg.1
2
2D;
I-I nA
2D;
where D3- (s + 22 + 8/2 4 82/4 81820 denotes the square root part of the Aa;1,2 expression. We will prove that this derivative is either 0 for I, = or strictly negative on [0, 28 everywhere except a set of measure for L > 3. This guarantees for L the optimal value being equal to the unperturbed matrix while also defines the set of optimal solutions. For L > 3 the optimal value is attained at characterized by a single perturbation size. To test whether this expression is smaller than 0, nothing 26-22
32, the objective value easily expressible and the optimal solution is
happens if we multiply it with 2L 8,1
6.22
SO we get:
A
26-2
(1+
(s) + S2)²
A
L-1
A
L-1
1
(s1 + s2)
D3
Ds
22

---

We can now compute
(5) +3 +8)
($}
s2)²
2(3 + +2)8
[2 92 - 8%
2
A6,1
4
2
to get
2L-2 2
21--2 6.2
(81 + 82)2 1
28182 - 6
(81 + 82)²
+
1
D8
D3
This expression resembles form for which the use of Jensen incquality would be convenient. However, there are two issues. First, the coefficients, though summing up to I are not convex (s=+ combination since Dr 2 1. So this is a combination outside of the convex hull of the inputs. However, Jensen inequality outside the convex hull is applicable with opposite sign. The bigger issue is that the function to use the Jensen inequality on, f(x) = x 2/z2 is only easily defined on IR.. To make sure that though outside of the convex hull of the inputs, still lies in R4. We are therefore asking whether
safely use Jensen inequality, first need to check that the linear combination,
As, (1+
(31 + s2)2
23182 -
(s1 + 32)² Ds
2 0.
D3
2
Now, we can multiply out and simplify this expression (after multiplying by 2):
(31 + s2)²
(51 + s2)²
s + 25 + 5 - D3 + (o] + +3)
+ 6
(81 + 82)² + 28182
D6
Ds
- 28182(81 + $2)²
+ 5(81 + 82)
2 0 +
D8
D8
((s1- - 02)² + 20) 82)² 2 (s} >2) + + + 82)
but this holds even with equality. So we proved that the combination of inputs we are considering here is exactly for which x -4 well-defined. So we can freely use Jensen inequality:
282
21-2
($1 + 82)2 1
+ (28182 - 8) 2
1
($1 + $2)2
Do
D8
24-11
(s1 + $2)2
23182 - 8 (1 (1- (81 $2)²
1882
1
0.
Ds
D3
Note that if L = 2, the function we applied Jensen inequality was, in fact, linear and thus retained equality. L 2 3, then since the function in question is strictly convex, the equality can only hold if \τ,2 | 82 5. After writing down the expression λε,2 it becomes clear that this is equivalent to a quadratic equation on 6, which can have at most two solutions. So we proved that the derivative is smaller than 0 on the whole interval of interest except set of measure most where it is O. Therefore, the only optimum is at 8 = 28182 Plugging this in the objective value one gets (s1 + $2) and from the proof we also get the precise description of the optimizers for both L = 2 and L > cases.
Now we are ready to formally make the reduction of the optimization problem in 110) into the optimization over only singular values of the matrices oHH) for < 1 S L. We formulate this reduction in separate lemma for clarity.
Lemma 12. The optimal value of the following optimization problem:
min 1 i [I W20(W, -211 +
Aw 2
AH
||
_ +
|| 11?
WE... WL.... W.
2
S.1. {81,1; {1,1)8112) = ((a)))) V2 1.
with H1 having two columns and all the matrices having least two rows is
Σ
2
AWL.
L-1
Awi
$2 811,
+ v
\w,, 211
2(32. + 2xw,)
2
$7.
1=1
1=2
where the 2411 is defined as if ,
37,5
0.
23

---

Proof. The proof follows easily by applying the Lemmas 9 S and 4
Now we are only left with optimizing the objective over all the 81,5- Crucially, the objective function is separable and symmetric in the i index. Therefore we can optimize for each index separately. Importantly, if there is only a single solution to this problem, then the solution must be the same for both indices i, which will yield orthogonality of the (ltt) matrices. The ultimate goal is show that this is indeed the case modulo some special circumstances. The optimal value of this reduced optimization problem is presented in the following, final lemma with abstract notation of the free variables.
Lemma 11. The optimization problem
AWL
Aw, Ji+1 ) + Vww, v02
min 2
Σ
(8)
2( + 2Aw,))
2
1=2
optimized at entry-wise positive, unique solution if
L
Aw. < (L 11-1)
Am.
II
24+1
1=1
and at (22,...,,I)) = ....... . otherwise. When (9) holds with equality, both solutions are optimal. Here, 0/0 is defined to be O.
Proof. Here we will need to distinguish the cases L = and L 2. We start with the case L = 2. Let reparametrize the problem so that will work with y /2z. We get the following expression to optimize the over:
Awa 2(v² + 2\w,)
AH,
This function is simple enough so that we understand its shape. It has precisely one inflection point, below which is concave, later it is convex. The derivative is strictly positive. Judging from this, the function either has 0 as single global optimum, or it has two global optima, one at and one at a strictly positive local minimum of the strictly convex part of the function, or the global minimum is achieved uniquely at the strictly convex part of the function. To find out, only need to solve f(y) = f(0) for y, where f stands for the optimized function and determine the number of solutions. The quadratic equation this is equivalent to after excluding the point y 0 solution is 4y² /Aw, AH, y 8Åw, /Aw, As, O. This has unique solution if and only Aw,Aw, XH, = 1/256, which is precisely the threshold from the statement of the lemma. The cases outside of this threshold are easily mapped to the system having the global solution 0 some positive point.
Let us now consider the case L > 2. First note that, once for any lo the optimal æi, = 0. then at this particular solution all the x's must be O. If lo = L, then this claim is apparent nackward-inductiver optimizing always over x with one index lower. If 2 < to < L. then the claim is trivial backward- inductively for all / S lo, while for all > lo this solution forced by feasibility issues. From now on we will thus work with an implicit strict positiveness assumption. Taking derivatives of this objective w.r.t 2j for different and putting them equal 0 we arrive at three types of equations depending on l:
AWL Xww.
V XL 2dW2,
Aw 11418111,
x7 = Awi-
for 3 3 2 1-1,
Awa
22
(15)
VAW,Arg
Here we can notice two things. First, we have 1 equations for I. variables, so we should expect single solution in most of the cases. Second, the equations rather simple and recursive.
24

---

Having either a value of 22 or 2L, all other values are uniquely determined. Let us denote == 2L-1 Based on this, we can arrive the following formula:
LL j= AWa-J-1 q ZL.
(16)
k-1 Wi.-
for all 1 S --2. An empty product is defined 1. To derive this, for the statement is only about and is trivial. For L > 3, the ho = case is trivial, then one can proceed by induction using the recurrent formula 2 Aw; equation:
Aw; r1 1 From formula (16), one can derive another useful
xk+1
AWL
for 2 k --1
Tb
XW
Xw q². Combining now this equation with for- Xw, 201
Combining this with (55,, also get 22 mula T6 for 22 from before one gets:
XW. Xw, An
Il j=1 AWL-
L-1 Aw;
12
L-3
d -
FL
W
d
WL
AH 1=
Notice that we managed to express all the terms present in the main objective as simple functions of q and regularization parameters. Plugging all of these expressions back in the objective, we get:
AWz
LAW
q.
(17)
2
W
9² + 2AW1.
1 Aw;
Since we only care about relative values of this expression, the optimization will be equivalent after multiplying it by 2/Xw.-; get:
Lq.
(18)
IH Aw, dl 2A
Azy Awz
Differentiating this function twice we can see that the second derivative is negative from 0 up to single threshold which it is O, then is positive. Therefore, based on the value of the first derivative at this threshold, and taking into account that the first derivative at 0 is strictly positive, we can easily see that the function has either single global minimum or it has two global minima 0 and some positive or it has single global optimum at some positive To find out which of the cases we are at, can simply solve for
Ly 2dWL
A An, Aw; 1 Aw, 9² 2AW
After excluding the trivial solution O, this is equivalent to:
2AWz., - - 4LAH, Aw, M1 Aw,
0.
2-2
W
The case at which we stand w.r.t. the global solutions of the above objective function is equivalent to the number of solutions of this equation. Since the LHS of this equation a very simple function, is apparent that the number of solutions to this equation is equivalent to the sign of the LHS evaluated
the single rero-derivative positive q. The derivative is 22w.,,,'''' -' (L 1)g" 1-2 which
after solving for > yields q = 2AW T.z Plugging this back into the LHS above, we get the expression
4LAH, Aw, 11 Aw,
21 1.-II110 1-21 1-- (L - 1)2 (L 121 -ALL 22-21 W.
I.-2
XW--1
25

---

Thresholding this for O and simplifying, we get the final
L AH II Aw, = 11-1)4-1 J=1
21+
If the LHS is smaller than this threshold, the function in (18) has a single non-zero global optimum. If the LHS is at the threshold, the optimization problem has both 0 and some single non-zero point for a global solution. If the LHS is above the threshold, the optimization problem has only 0 as single solution.
With all this, Theorem follows very easily. We only need to conclude that if the optimization problem in Lemma| has a single non-zero solution, then both the optimal si and si are forced to be the same for each From this, we obtain the orthogonality of all the o(Hi) for 2 2. However, from Lemma 6 we know that even the optimal Hī for / 2 3 must be orthogonal, since it is non- negative and equal to a (H₂). From the same lemma, we conclude the statement about W7 for I 2 2. The optimal Wr, Hi follow easily from Lemma 8
By now, we only considered the case n 1. Now, we proceed to the general n case, where we need to also prove DNCI, We will proceed by contradiction. Assume there exist f7,, Wi,..., Wi which optimize L-DUFM, but Hi is not DNC1-collapsed. Now, since the objective function in 10 separable in the columns of H1. we know
1
Wio(...Woo
6c
+
Aw
|
2 +
An
1
(1)
2N
2
2
1=1
2N W W3o co
1
||
Awi
[W/
AH
h (1) c 2
2
where ( Aej are columns of 1if, for all c, i, applicable and e, is the c-th standard basis vector. Otherwise, we could have just exchanged all sub-optimal het with the optimal one and achieve better objective value. However, if the last equality holds, then we can construct an alternative Hi where for each class c, we pick any (/ and place it instead of all other 1/33 within the class c. In this way, the Hi will be DNCI-collapsed, while still an optimal solution. However, for Hi, we now know that if Hi is constructed by taking just a single sample from both classes (thus forcing n = 1), this must be optimal solution of the 1 L-DUFM with nλæ, the regularization term for H7 and same feature vector dimensions and other regularization terms. This is because if there was a better solution for the corresponding problem, then we could construct counterexample to optimality in the original L-DUFM problem by just simply taking this alternative, better solution and using the feature vectors of this solution for each sample of each individual class.
Therefore, since Hi must be optimal in the new n = 1 problem (with a slight abuse of notation, we re-label the nλæ, back to Ar. ). we know that a (H²) is collapsed in the way described by the theorem statement for n = 1. By non non-ncgatyyy of a H this means that oHH) ) has two columns, let's call them z, y for which: 2, y 2 0; 0, ||=]| = |ev/ll (by the notation > 0 we mean entry-wise inequality). This also implies that there is no such i that Fi, Vi > O. Moreover, let us assume o (H₂) * O. We can do that, otherwise simple arguments would lead into the degenerate solution where all W 0, for which obviously all the columns in the originally optimal A would need to be 0 implying simple DNC1 and reducing easily to the case of too big regularization explicitly stated in Theorem 3 We can now omit this case and assume non- non-tri -oi-vriviality of the solution. We will first show that for a given set of optimal weight matrices (Wi, W ..... W W. the matrix (HH; is uniquely determined regardless of what 1f is. First, by the uniqueness of the solutions in Lemma []] and by the fact that $2 depends monotonically on ||x]|, it follows that for any candidate direction
2, ||||||| = 1, there is unique multiplier a > 0 for which az can be a column of a (Hz). i.e. there is uniquely determined norm under which any candidate direction 2 must enter o (Hz). Now, however, by DNC3 for = 2 we know that rows of W₂ are either zero or aligned with the columns of a (Hz). Moreover, since H3 (which in case L = 2 shall be considered the output of the network) orthogonal and thus rank 2, the weight matrix W must contain both the columns of a (H)) as its rows in direction. However, it cannot contain more than 2 different directions, otherwise for any
26

---

fixed optimal o (H2), there would be an extra direction which would contradict DNC3. Thus, W2 contains exactly two linearly independent (orthogonal) directions. But then, in turn, only these two directions can be columns of ). So a (H2) is unique, possibly up to switching of its columns J. y. However, only one permutation of these columns is optimal, because we know that the output of the matrix, HL-1 is orthogonal and only one of its permutations is better aligned with 7g. Therefore o (H1) is fully unique.
Invoking Lemma 9 we know that the whole range of matrices Ag are such that (A2)) - ((1)),
while || = [Hgl, Namely, by Lemma 9 all the matrices Ag which satisfy that condition are represented by having columns of the form x ty, y tx for t E [o, 1]. This can be derived as follows. According to the lemma and the description of or (HH)) , this matrix is a good candidate for the non-negative part of the optimal solution of the corresponding optimization problem, and so the optimal solution (in the case of I. = 2 a solution for which the nuclear norms of it and its non-negative part are equal) whose non-negative part equals o o(H)) exists. The negative values, according to Lemma 9. must follow a strict, yet still non-unique pattern. The negative values of the (+, 0) rows of o (HH)) must be arranged that they are aligned with the positive values in the corresponding rows, thus being multiple of æ. The negative values of the (0, +) rows must be, on the other hand, aligned with y. The coefficients of homothety between and the negative part in the (+)0) rows and between y and the negative part of the (0, +) rows must be equal due to the condition on equal l2 norms of the negative parts corresponding to (+. 0). (0, rows and the fact that || = ||vl . Finally, the coefficients of homothety must be non- positive (yielding non- non-negative t) to retain the negativeness and no smaller than -1, due to the final condition of Lemma 9 stating that the product of any two negative values of counterfactually signed rows must be at most as big as the product of the corresponding positive entries and due to the already established alignment of positive and negative parts. In this way, the only matrices A₂ which satisfy these conditions are represented by having columns of the form x ty. y - to for t [o, 1J. as stated above (note that -ty is aligned with x on (+, 0) rows of a (Hi) and similarly for -tx).
Let us denote by A$ matrix of that form for particular 4. Now, the SVD of A₁ is as follows: U E' is diagonal matrix with diagonal entries equal to ||=]|| (1 + t) and || (1 - t), and V is composed of the vectors (1/v2, -1/V2) and (1/V2, 1/ For 1 * 0, this is the unique SVD up to + multiplications. For / = 0, AΩ is orthogonal and the SVD is non-unique. However, as we will see, this will not be relevant in the following argument. Invoking Lemma 8 we see that, for each the set of possible W which can be the optimal solution is St = (E From this representation, we see that the non-uniqueness of SVD is "wrapped" in the freedom of Rt", If l = O, Σd is diagonal and commutative and U Re obviously cover all possible representations of U in the SVD of A9. If > O, we can easily cover the freedom in signs by R too. Thus, we can assume fixed U and V for all t = [0. 1]. The question is, whether for S t1 < b2 S Sh S = 0. To find out, consider some R and R orthogonal. We want to know whether it is First, this obviously does not hold l2 1, because of the rank inequality. Assume 62 < and do the computation:
is composed of (z v)/(v2 ( [|==]] and (x + (v/(v22111))
for all possible orthogonal R of suitable dimensions.
possible that ex U (E"))\//(((""
= cx U² (/2')//((RR)))
ex ex (E1))")) = e₂ ( (2R
(( = (12
(111) = -157))1/2(1
(E ((RR)T((R*))
where in the first equivalence we used the established knowledge that we can use the unique repre- sentative U for all t. However, the diagonal elements of ( and (1-41)/(1 - 12). The first one is strictly greater than 1. On the other hand, all the entries of (R(*)((RR)) are inner products between columns of orthogonal matrices and thus at most 1 in absolute value. This proves Stx n St2 0 for 0 S f < 1.
are v(1 + t1) + f2)
Thus, there is just single t" for which W is optimal and, moreover, there is single A; = A that can be the output of the first layer. Then, if we analyze the two systems of linear equations A = WTX X, where X is the d x 2 matrix variable (each system for each column of X), we know that there a unique min-l2 norm solution per system. The min-l2 norm solution must be the only optimal solution, because Hi is regularized using the Frobenius norm. Thus, there is single Hi
27

---

which can be the optimal solution. However, this is contradiction with the assumption that we had a freedom while constructing Hí from Hi a possibility of choosing different columns from some classes as the representative of that class. Therefore, the Hi must have had single feature vector per class the first place, which contradicts the assumption that it is not DNCI collapsed.
Now that we have the DNC1 collapse, we can obtain the DNC2-3 collapse easily by just again going from the full H to the reduced n. = 1 version of it. Moreover, we know what are the forms of W and Hi orthogonal transformations of the SVD of Hīz However, must be said that these optimal matrices do not need be orthogonal themselves, due the (E multiplication, which makes the matrix non-orthogonal (consider for instance just taking the identity matrix extended to rectangularity for R). This concludes the proof of Theorem
B Extension to multiple classes
Here, we comment shortly on why it is challenging to formulate equivalent of Theorem K 2. First of all, it already unclear how carry out the proof of Lemma for K and even whether it holds. However, the bigger issue lies in Lemma 9 Note that ||2 2 [12))) only holds for matrices with two rows or columns. A simple counterexample with x 3 matrix goes as follows:
3 for
I 111 !)
A
0
1
for which ||A]. 3.464 and [|]())].. 3.494. However, this does not mean that Theorem does not hold for K" > 2. For instance, at orthogonal matrices, which are collapsed, one can show that this equation holds by computing the sub-gradient of the nuclear norm and using convexity. It is also hard to come up with counterexamples to the inequality for matrices which are close to orthogonal. Therefore, is our belief that the cost of losing orthogonality in other loss terms makes the compensation of achieving slightly lower nuclear norm insufficient. However, to make this argument formal, one needs sophisticated control over this quantity together with all the other results.
C Further numerical experiments on DUFM and ablations
In this section, we further investigate the effect of significant parameters on the training dynamics of DUFM. We focus on the effect of depth, regularization strength and width on the outcome of DUFM optimization. All the plots (except the one in Appendix C.5) are averaged over 10 runs with one standard deviation both sides displayed confidence band. First, however, we supplement the numerical results from Section 4.2 with the promised plots of the losses.
C.1 Extra material to the numerical results in Section 4.2
In Figure 3 we plot the loss functions and theoretical optimum, together with the disentangled loss functions computed separately on the term and the regularization terms for Hi, Wi, with 1 < 1 < L. As already discussed in Section 4.2 the DUFM finds the global optimum perfectly and exhibits superb DNC.
C.2 Effect of depth on DUFM training
As already seen by showing 3- and 6-layered DUFM, the depth does not play a significant role on the training of DUFM. However, an implicit bias of GD be observed for very deep DUFMs. To demonstrate this, we plot the 10-DUFM training results in Figure 4
Though not well visible on the plots, the DNC2 is sometimes achieved also on H1 H2, which in the shallower DUFMs was an exception. This shows that with increasing depth, GD is more and more implicitly biased towards finding DNC2 representations for these feature matrices too.
28

---

loss
loss
10a
100
total loss
total loss
10-1
It_soss
10
fit_ loss
theoretical capeetttmallootmmmm
theoreticalloptimme
10
10-2
-0
10 10-3
10
10
10-5
10
10-6
-8
0
20
40
60
80
100
20
40
60
80
100
step
1e3
step
1e3
Figure 3: Losses and partial losses for 3-DUFM (left) and 6-DUFM (right) as described in Section 4.2 The total training loss is compared the numerically computed optimum (based on (17). The unlabeled loss curves correspond to all the regularization losses.
loss
DNC1
109.
total Joss
layer 1
10-1
theoretical optimum
lass
10-2
10
layer
layer 2
layer
10
10
layer 5
10 -3
10-6
layer
layer 7
-
layer
10-1.
10-10
layer
layer 10
5
10
10 14
10
20
40
60
80
100
0
20
10
60
80
100
step
1e3
step
1e3
DNC2
DNC3
layer_1 1
10a
byye_
layer_3 3
10-2
layer
10
layer_s
ayer_1
bayr_2
layer_6
10-4
byar_3
layer_7
layer_8
10 5
byer_5
layer 9
byer
layer,
byar_?
layer_?_prx
2_pre__pp
10
byer_
byer_
10
kyer 10
20
40
20
40
60
80
100
step
1e3
step
1e3
Figure 4: Losses and DNC metric progressions as a function of training time. The unlabeled loss curves correspond all the regularization losses. Here, the 10-DUFM is trained. The variance in some the DNC metrics is due non-zero chance of qualitatively different behaviors for first and second layer.
29

---

C.3 Effect of width on DUFM training
Unlike depth, width has a significant effect on the DUFM training, especially at small widths. The reason is that the model parameters often get stuck in sub-optimal configurations due the difficult optimization landscape. To compare, we ran 4-DUFM training with the same hyperparameters except the width. We repeated the experiments for widths of 2, 5, 10, 20, 64, 1000. We plot all the results in Figure
The results suggest that the risk of DUFM not reaching the global optimum and thus DNC drastically decreases with the width. Already for width 20, the DUFM did not fail to reach the global optimum once in ten runs. On the other hand, for width of only 2, the DUFM did not reach the global optimum in any run. Interestingly, the smaller widths yielded less expected behaviour. For instance for width 10. we encountered two runs both reaching a perfect optimum and DNC, of which one exhibited DNC2 also for H1, H2, while the other did not. Noticeably, for width 1000 we see higher variance in some DNC metrics. This because some of these specific metrics converged to very low values for some runs and for some other stayed comparably higher. This effect appears to be an implicit bias of SGD.
C.4
The effect of weight decay on DUFM training
As expected for the MSE loss setup, the weight decay is the main driving force for the occur- rence of DNC. Therefore, predictably, the weight decay has direct influence on the speed of convergence towards both DNC and global optimality. This is clearly demonstrated in Figure 6 where we plot the training dynamics of 4-DUFM with width 64 and weight decays of sizes 0.0001, 0.0005, 0.0009, 0.0013, 0.0017. By increasing the value of the weight decay, the loss as well as DNC metries converge much faster. However, there is no qualitative change in the result of the training for different values of weight decay.
C.5 Interconnection of DNC and optimality of DUFM
As an interesting bonus, we show single, cherry-picked run for the 4-DUFM with width 10 (although such runs occur quite often at this width). This training first got stuck at an almost-optimal solution, then after long stay in the saddle point, it jumped to the optimum. The DNC metrics showed clear decrease at exactly that point of the training, as shown in Figure 7 This run clearly shows how interconnected the deep neural collapse is with optimality.
D Pre-trained DUFM experiments on CIFAR-10
Here, we specify the training conditions from Section 4.2 in more detail, and add results of further runs to provide more robust evidence. We use three different architectures ResNet20, 2 and VGG13. We only impose one change to these the standard backbone is extended with one extra fully-connected layer with output dimension 64 to enable free features and reasonable size of the DUFM. The weights are initialized with He initialization [9] with scaling 1. The DUFMs in question are and 5-layered of constant width 64. We train with weight decay 0.00001 and with learning rate 0.001 on 1000000 full GD steps. The backbone was then trained using stochastic gradient descent with batch size 128, learning rate 0.00001 and with 10000 epochs on classes 0 and of CIFAR-10. While in Figure I we plot results of single training of the 3-DUFM model followed by 7 independend trainings of independent initializations of the ResNet20, here we add two more independent trainings of the DUFM averaged over further independent runs of ResNet20 training. The results are qualitatively the same as in the main body, which suggests that the ability of ResNet20 to make unconstrained features suitable for the emergence of DNC is robust w.r.t. the well-trained DUFM head. The results of these two runs are depicted in Figure g
As side note, we remark that unlike end-to-end training or DUFM training, the ResNet20 training with pre-trained DUFM head more prone to undesired behaviours. First of all, we need a rather small learning rate to prevent divergence and even with that, minority of runs never jumps from 50% training accuracy. Therefore, in our results, we only report those runs, which converged to near 100% training accuracy.
30

---

DNC1
10
UWCZ
10"
layer_]
Myyr_
10-4
10
k
layer
kyet 2
10
10
syer
107
10-+
layat 4
10"44
Joax
101
retical, nattmum
10a
step
1w3
16.3
step
1e2
143
10
10a
CNC2
10
10"-
101-
10
10
163
305-
10
Toyor
10
Mntal Joss
Iserr
30
layer
10
91_ (965
wenee val, notimm
10
10
layer
Iayer:
10
80
160
10-11
69
80
100
0
20
40
80
100
10
60
80
103
20-1.
10a
loss
DNC1
bayer layer
DRAC
1ayer
1ayer 2
102
CNC3
20--
1n-1
10
3ayer
byye
102
layor 5
layo
layer pre ma
30
10"
10-1
10
Sotal
Shooret aptim.m
10"
10
20
80
200
100
10
300
30
60
60
102
step
3+3
2763
step
36.3
next
DNCE
10
10'
optimum
10-1
10:1
169
layer: 1
kyyo
kyyo 2
bayer 4
Iaper
layer:
layer
10"2
107
10-1
10-1
10
10
10
30
107
100
3842
305
4542
343
stop
365
203
1955
DNC3
10-1
1R,
Myyrr layer layer
laye
layor 1
107
10
10m4
Uecoratical optimum
10
10
koyer
16"4
10"
Gayer
10
10-1
10
1ayer
30
2003
step
143
DNC3
304
J0til Joss
10a
102
102
50m1
11
cticell rum
30:
ky
kywer
10
11-1
10-2
14
byer
10-1
10
laper:
10
10-1
10:13
laper:
10a
10
layer
60 00
40
350
20
20
100
Figure 5: Losses and DNC metric progressions function of training time. The unlabeled loss curves correspond to all the regularization losses. Each row represents different width, in increasing order ranging through {2,5, 10, 20, 64, 1000}. As the width increases, the training gets more stable. For width 2, no training converges to optimum. For width 5, the training only rarely converges to optimum. For width 10, the training usually converges optimum, but often after encountering saddle points. From width 20, we see a stable training behavior with almost no difference between different high-width trainings.
31

---

107
total iiKe
18, Joes
107
107
D0C3
10
theorstical mppbmum
10
20-1
10
leyer 2
Hyer
10
10
10-1
20
kayer_3
kyyer
100
20
90
80
300
40
40
MI
US0
10.1
10-1
107
thearatical Leptmum
tstall
1n-4
10th
107
DNC1
1ayer?
Iyer_
DROC2
Iayor_1
Iayer2
1014
20-4
lagnr 2.p
10
layer
20
layer
20-12
layer
10mm
22
60
80
100
20
00
100
307
20
40
60
80
100
1,y -4
20
40
60
80
103
CRAC2
PWC1
10"
layer
10
10-1
theorttica
1014
1ayer
laver
1017
1ayer 14
bbyer 2_pre_re
10-1
10
30"7
4.
10
loye
15yer
10
107
1ay
20
80
100
60
100
20
60
60
100
60
80
103
JAC3
lass
UNNC
10
10"
laye
layer
Nayor
10
layer
layer
layer
20"
10
10
Mayer
layer
layer 200 2e1u
30
10"
80
200
60
300
60
20ep
1+3
step
9767
DNC3
12a
10a
Byer_]
101
byyer 1
layer
107
layer
30-
20
30"
10-3
Byerr
10
10
141
16:1
50.0
161
Figure 6: Losses and DNC metric progressions as function of training time. The unlabeled loss curves correspond all the regularization losses. Each row represents different value of weight decay in increasing order through a set (0.0001, 0001,0000055, 0.0005, 0.0009, 0.0013, 0.0017). By increasing the weight decay, the training dynamics get faster.
32

---

10
loss
DNC1
total loss
aayer
10
fit loss
10
aaer
10
theoretical aptimmum
10
layer 3
10-4
layer_4 _
10
10-8
10
10"4.
10
10-5.
10
10 14
10-6
20
40
60
80
100
40
60
80
100
step
1e3
step
1e3
DNC2
DNC3
layer
10a
layer 1
104
layer 2
layer 2
layer
layer 3
layer_4 _
10 1.
layer_4
aayer_2_pre_relu
10
10
10-3
0
20
40
60
80
100
0
20
40
60
80
100
step
1e3
step
1e3
Figure 7: Losses and DNC metric progressions as a function of training time. The unlabeled loss curves correspond all the regularization losses. The plot shows single run of the training of 4- DUFM with width 10. After staying in a close-to-optimal saddle point, the model achieved optimum, the DNC metrics rapidly decreasing.
l85s
DNC1
DMC
DNC3
uyer:
107
30
107
layer
rel3
10
107
10-4
30
spoch
Jo5
000ch
103
steg
163
DNC3
10
324
total jois
regL 665
304
[ayer layer
10-
10
30"1
100h
30
10
107
loyer
307
lyyer
1C5
Figure 8: Loss functions and deep neural collapse metrics function of training progression. The rows correspond to different pre-training runs of the 3-DUFM model. On the left, the training loss function and its decomposition are displayed. Next, the DNC1-3 metrics are displayed. The ResNer20 recovers the DNC metrics for DUFM, in accordance with our theory. This validates unconstrained features modeling principle for neural collapse.
33

---

109
byer wyer 2
10-1
tota 1mn8
Jom
10
30
101
10"5.
10
30
DVC
DMC2
Dh-C
syer
Ryer22
10"4
Ryer3
sye___ee__el
521
10
10.1
10
layer.1
10:2
10
10-3
10a
0.5
3.5
3.5
0.0
1.0
opoct
opach
spech
Figure 9: Loss functions and deep neural collapse metrics as a function of training progression. The first row corresponds to VGG13 experiments, the second row corresponds DenseNet1 21 experiments with the pre-trained 3-DUFM model. On the left, the training loss function and its decomposition displayed. Next, the DNC1-3 metrics are displayed. Both architectures recover the DNC metrics for DUFM, in accordance with our theory. This validates unconstrained features as modeling principle for neural collapse.
10
20d. 313
lover
Iyer
kyer
32a
10"1
16-2
1.
30a
Dert
10"
10a4
30
opoch
opoca
opoch
Figure 10: Loss functions and deep neural collapse metrics as function of training progression. The head considered is pre-trained 5- 5-DUFM model. On the left, the training loss function and its decomposition are displayed. Next, the DNC1-3 metries are displayed. The ResNet20 recovers the DNC metrics for DUFM, in accordance with our theory. This validates unconstrained features as modeling principle for neural collapse.
We further present the results of the same experiment but with 5-DUFM attached to ResNet20 as well as 3-DUFM attached DenseNet121 and VGG13, to even further validate the robustness of our results. These results are presented in Figures and 10 and they are in full accordance with the ResNet20 experiments.
34


Reviews:
[{"review_id": "4MJoDbcpra", "reviewer": "Reviewer_nhUP", "summary": "This paper introduces the concept of deep neural collapse (DNC), extending the understanding of neural collapse to earlier layers of deep neural networks. It proposes the deep unconstrained features model (DUFM) as a theoretical framework to analyze DNC. The authors demonstrate that for binary classification, DNC is a globally optimal solution in the DUFM, providing rigorous evidence of its occurrence in multiple layers. Numerical experiments confirm that gradient descent efficiently finds solutions in line with the theory, exhibiting neural collapse in multiple layers. The paper concludes by highlighting open problems for future research, such as generalizing the analysis to multiple classes, exploring gradient dynamics in the DUFM, and understanding the impact of biases and loss functions on the collapsed solutions.", "questions": "$\\bf 1.$ The results in this paper are based on the L-layer deep unconstrained features model. This omits all the structures in the data input. A natural question is whether the analysis can be extended to the case where the data input has some special structures, such as the case where the data is whitened, i.e., assuming $H_1H_1^T=I$ in Definition 1.  \n\n$\\bf 2.$ What is the main technical difficulty in analyzing multiple-class cases?\n\n$\\bf 3.$ What is the role of the activations in deep neural networks? Why do DNC1 and DNC2 hold for layer l ≥ 2 before and after activations?", "limitations": "Not applicable", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "$\\bf (1)\\ \\textbf{Strong Technical Analysis}:$ A key strength of this paper is its strong and rigorous technical analysis. The authors provide a solid theoretical framework, specifically the deep unconstrained features model (DUFM), to analyze and understand the phenomenon of deep neural collapse (DNC). Theorems and empirical evidence are presented to support their findings, enhancing the credibility and reliability of the results.\n\n$\\bf (2)\\ \\textbf{Extension to Multiple Non-linear Layers:}$  This paper addresses a crucial gap in the existing literature by extending the analysis of neural collapse beyond the last layer to multiple non-linear layers. By generalizing the unconstrained features model, the authors provide insights into deep neural collapse (DNC) occurring in deeper layers of neural networks. This extension contributes to a more comprehensive understanding of the behavior of deep networks during training.\n\n$\\bf (3)\\ \\textbf{Empirical Validation:}$ The paper provides empirical evidence to validate the theoretical framework. The authors demonstrate that by optimizing deep unconstrained feature models using gradient descent, the resulting solutions align well with the theoretical predictions. This empirical validation reinforces the credibility of the proposed modeling principles and their applicability in real-world scenarios.\n\n$\\bf (4)\\ \\textbf{Relevance and Contribution to the Field:}$ The paper addresses a significant topic of interest in the field of deep learning by focusing on the phenomenon of neural collapse in deep neural networks. By providing theoretical insights and empirical evidence, the paper contributes to the existing body of knowledge and expands our understanding of the behavior of deep networks during training.", "weaknesses": "\n$\\bf (1)\\ \\textbf{Theorem 3 cannot explain the progressive neural collapse:}$ In Ref [8], the authors observe that each layer roughly improves a certain measure of data separation by an equal multiplicative factor. A similar observation is depicted in Figure 1 of the current paper. However, Theorem 3 contradicts this observation by demonstrating that for all layers $l \\ge 2$, the within-class variability of features becomes zero, and the features form an orthogonal matrix. This discrepancy suggests that there may be additional factors or dynamics at play in the behavior of the layers beyond what is captured by the initial observation. Further investigation is necessary to reconcile these contrasting findings and gain a more comprehensive understanding of the behavior and properties of features in deep neural networks.\n\n$\\bf (2) \\textbf{Role of activations:}$ One weakness of the paper is the limited discussion or exploration of the specific role and impact of activations in the context of deep neural collapse (DNC). While the paper acknowledges that DNC1 and DNC2 hold for layer l ≥ 2 before and after activations, it does not provide an in-depth analysis or explanation of how the activations influence or interact with DNC.\n\n$\\bf (3) \\textbf{Limited Scope:}$  The paper primarily focuses on deep neural collapse (DNC) in the context of binary classification. While this specific focus allows for in-depth analysis, it may limit the generalizability of the findings to other problem domains or network architectures. Further exploration of DNC in more diverse settings could strengthen the paper's applicability.\n\n$\\bf Typos:$ (1) At line 122, it should be $W_L \\in \\mathbb{R}^{K\\times d_L}$.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful assessment and for the positive evaluation of our work. We address the points raised in the review below. \n\n**Theorem 3 cannot explain the progressive neural collapse**\n\n*Response.* We agree that there is a gap between the predictions of the DUFM and the progressive neural collapse which has been observed empirically in real networks, and investigating this gap is an important future direction. Let us make two comments in this regard.\n\n*(i)* The progressivity of DNC may be due to the non-linearity of the data, which the neural network has to eliminate throughout the layers. One reason for the gradual removal of within-class variability through the layers could be the balance between the norms of the weight matrices of different layers. In fact, decreasing the within-class variability more quickly would require larger matrix norms, which is prevented by the regularization. \n\n*(ii)* A dynamic analysis of the trajectory of gradient descent could also show a progressive neural collapse: the final layers reduce the within-class variability faster than the first ones, as training progresses. \n\nFinally, we note that the phenomenon of progressive neural collapse is not entirely understood even at the experimental level: on the one hand, [8] observes a log-linear behavior in the DNC1 reduction; on the other hand, [26] observes a reduction which is no longer log-linear.\n\n**Lack of discussion on the role of activations**\n\n*Response.* This is a good point, we will expand the manuscript accordingly. Our theorem indeed reveals an intriguing insight into the role ReLU plays in the DNC. As we see from Lemma 6, the optimal intermediate layer activations, i.e. $H_l$ in our notation, are non-negative.\nThis is due to the fact that the ReLU disregards any negative activation by zeroing it out. From our computations, it follows that producing strictly negative values is suboptimal for the norm of $W_l$ and, therefore, all the activations are non-negative. \n\n**The paper only focuses on binary classification**\n\n*Response.* This issue was raised by multiple reviewers. Hence, we have opted to respond to it in the global response above.\n\n**Q1: Omitting the data structure + possible structure in $H_1$**\n\n*Response.* We agree with the reviewer that the unconstrained features model removes all structure from the data. In fact, the main assumption underlying the model is that the network’s backbone eliminates any structure from layer $H_1$. However, though we consider multiple last layers, we still assume that we only look at the relative end of the network, therefore the unconstrained features model is similarly motivated as in the last-layer collapse. Going beyond unconstrained features, understanding the effect of additional structure is certainly a natural question.\n\nNote that the rank of $H_1$ under DNC1 is at most $K$, and the row-dimension of $H_1$ is $d_1$. Thus, for $H_1H_1^T=I$ to hold, we need to look at $\\bar{H}_1$ (as defined in line 116) instead of $H_1$ and we need $d_1 = K$, which is rather restrictive. Hence, in general, the assumption $H_1H_1^T=I$ is not compatible with DNC1.\n\nInstead of considering an $l_2$ regularization on $H_1$, several papers (see e.g. [19, 31, 36]) assume the features to be normalized, which can be regarded as a way to add structure in the input data. Another attempt to assume *some* structure is done in [29], where the authors consider features that are only approximately unconstrained and admit an error. It is an interesting future direction to quantitatively understand the effect of such modeling assumptions on our results.\n\n**Q2: Main challenges in analyzing the multiclass case**\n\n*Response.* Please see the global response.  \n\n**Q3: The role ReLU plays in our theory**\n\n*Response.* The reason why DNC1 and DNC2 hold before and after the activation is rather subtle, and it follows from the results of Lemma 6. One intuitive way of reasoning about this is as follows: ReLU disregards negative values, hence it is useless for the network to create negative features. The computations of Lemma 6 formalize this idea: the network avoids creating negative features (before the application of ReLU), and by doing it, it yields a solution with the smallest possible Frobenius norm."}, {"review_id": "UPBcOq9oFf", "reviewer": "Reviewer_9Ryi", "summary": "The paper proposes a novel approach to investigating deep neural collapse in deep neural networks by presenting a generalization of the analytical framework for neural collapse (NC) to multiple non-linear layers. The paper introduces the deep unconstrained features model to demonstrate that the unique global optimum of the MSE loss for binary classification exhibits all the properties typical of deep neural collapse. However, the paper only considers the MSE loss without a bias term for binary classification, which may limit the applicability of deep neural collapse for other losses. Specifically, the theoretical conclusions may only be provably optimal in some cases.", "questions": "see weaknesses.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents a  generalization of the unconstrained features model  to multiple non-linear layers, filling a gap in the existing literature.\n- The paper contributes to a better understanding of deep neural collapse in binary classifcation deep neural networks, which has important implications for the design and optimization of deep learning models.", "weaknesses": "- The theoretical analysis only involves binary classification, and it is unclear whether the proposed approach can be extended to multi-class classification problems, especially for a large number of classes that would change the final form (DNC2) of the resulting deep neural collapse.\n- The paper only considers the MSE loss without a (last-layer) bias term, which may limit the applicability of deep neural collapse for other losses. Specifically, benifiting from the MSE loss without the bias term, the unique global solution can exhibit close-formed results, which may further allow the derivation of the proof to be greatly simplified.\n-  while neural collapse induces a simplex equiangular tight frame [1], which may not hold for other loss functions  or if a bias term is included [2]. \n- The paper lacks extensive experiments to validate deep neural collapse. Additional experiments on a variety of datasets (especially for a large number of classes) and deep neural networks would help to better understand and confirm the prevalence of deep neural collapse.\n- The paper could benefit from a more thorough discussion of the practical implications of the proposed approach for the design and optimization of deep learning models.\n\n[1] Vardan Papyan, X. Y. Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. In *Proceedings of the National Academy of Sciences (PNAS)*, volume 117, 2020.\n\n[2] Jinxin Zhou, Xiao Li, Tianyu Ding, Chong You, Qing Qu, and Zhihui Zhu. On the optimization landscape of neural collapse under mse loss: Global optimality with unconstrained features. In *International Conference on Machine Learning (ICML)*, 2022.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful assessment. We address all the points raised in the review below.\n\n**Extension to multi-class classification problems**\n\n*Response.* This issue was raised by multiple reviewers. Hence, we have opted to respond to it in the global response above. \n\n**The paper only analyzes the MSE loss without the bias term**\n\n*Response.* We agree that using the MSE loss does not provide a full insight into the usage of other losses. Indeed, as we see in the literature on neural collapse, the analysis and even the statements for MSE and cross-entropy (CE) losses differ significantly. For instance, the neural collapse for CE loss is not well-defined without feature normalization or weight decay.\n\nIn our work, we perform the analysis with the MSE loss, as it provides more options for mathematical treatment. We highlight that the MSE loss is a reasonable choice, as it is reported by [R1] that training with the MSE loss can perform on par with the training with the CE loss. For these reasons it is the setup of choice of a large number of papers on neural collapse [7, 21, 28, 30, 40, 41]. An extension to cross-entropy is a great direction for future work, however the corresponding analysis is likely to be quite different. In fact, the CE loss does not admit closed-form solutions, and it typically yields a structure described by an equiangular tight frame (ETF) at least in the last layer.\n\nAs for the omission of the bias term, we believe it is possible to extend our analysis to include the bias. In fact, Lemmas 5-9 are unchanged, and the only changes involve Lemma 4 and Lemma 11, which can also be adjusted to accommodate the bias. However, by the argument made in [29] that the ETF structure can be obtained from the orthogonal frame (OF) structure by simply centering it, we believe that including bias would not provide significant new insights on top of our existing results. Since the computations would get much more complicated, we thus opted to omit this case.\n\n\n**The paper lacks experiments to validate the neural collapse**\n\n*Response.* We agree that validating the DNC is a key prerequisite for its theoretical study. However, this validation was already extensively made in recent work (see [8, 26]). Our contribution crucially builds upon this experimental evidence and provides a theoretical analysis of the same phenomenon. \n\nThat being said, we still do experiments related to main take-away of our paper: \n\n*(i)* We have performed a rather extensive set of experiments on DUFM: different depths (ranging from 2 to 10), different widths (from very small to as wide as 1000 neurons), different weight decays, and different learning rates. Many of these experiments are discussed in detail in the ablation study in Appendix C, where we provide a concise description of the effects these hyperparameters have on the emergence of DNC. \n\n*(ii)* The experiments on real data validate the DUFM assumption, a point that was lacking in the related literature, see both the main paper and the additional results in Appendix D. We also provide extra experiments in the 1-page PDF attached to the global response above:\n\n*(ii-a)* We consider VGG13 and DenseNet121 architectures, keeping the rest of the experimental setup the same as in Figure 1 of the paper.\n\n*(ii-b)* We consider a 5-layer head on top of the ResNet20.\n\nAll these new experiments fully agree with the original one and support our theory. \n\n**The paper could benefit from further discussion on the practical applications of the proposed approach**\n\n*Response.* This is a good suggestion. We provide below two insights resulting from our theory. \n\n*(i)* Our results suggest that the $l_2$ regularization leads the deep neural network to find solutions with well-conditioned matrices (orthogonal in the ideal DNC case). This in turn provides more robust models.\n\n*(ii)* In principle, it should be possible to exchange the $l_2$ regularization on the weight matrices of the backbone with an $l_2$ regularization directly on $H_1$. In this way, we expect to be able to force the occurrence of the DNC more directly. Several works (e.g., [1, 5, 6, 15, 16, 17, 32, 34]) try to utilize the neural collapse for practical purposes (including transfer learning, out-of-distribution detection, robustness, and calibration), and this is a good way to better reach it.\n\n[R1] Demirkaya, Ahmet, Jiasi Chen, and Samet Oymak. \"Exploring the role of loss functions in multiclass classification.\" 2020 54th annual conference on information sciences and systems (ciss). IEEE, 2020.\n"}, {"review_id": "5i7fIgH4Yz", "reviewer": "Reviewer_Egs3", "summary": "The paper studied Deep Neural Collapse (DNC) which extends the structure of Neural Collapse of the last layer to multi-layers in deep neural networks. Theoretically, this paper generalizes the established unconstrained features model to the deep unconstrained features model (DUFM) of multi-layer non-linear models for binary classification. Based on the deep unconstrained features model, they show the global optimum exhibits several extended properties. Empirical experiments demonstrate that the results of the optimized deep unconstrained features model and trained networks agree with the theory. \n", "questions": "\n1. Most previous research[1,2, 3] focus on models with bias while in [3] they also study the unconstrained features model without bias and show the features exhibit OF rather than STF under UFM with bias. So I am just wondering if it is possible to extend the DUFM to the bias case and show the STF structure in DNC2?\n\n2. There are some experiments results for 3-layer Resnet-20 in the paper which also show DNC, but in [4] the results seem to show that the Neural Collapse process gradually across the layers of the neural network like the measure of NC1 decreases exponentially. I think this may be caused by the gap between the DUFM and real trained networks. Are there more experiments on real trained networks and whether they exhibit DNCs? If so, why is there such a difference between the results in this paper and the results in [4]. If not, is that mean there is a gap and needs other explanations for such a phenomenon? \n\n3. All experiments based on DUFM in this paper add the regularization term of the first layer feature. By the derivation of the DUFM, it seems that possible to add a regularization term on the intermediate layer feature, for example, add $||H_5||_2$ and optimize $W_l, l \\ge 5$, are there any experiment results can demonstrate in this case how the DNC performs?\n\n\nReference:\n[1] Zhu, Z., Ding, T., Zhou, J., Li, X., You, C., Sulam, J., & Qu, Q. (2021). A geometric analysis of neural collapse with unconstrained features. Advances in Neural Information Processing Systems, 34, 29820-29834.\n\n[2] Fang, C., He, H., Long, Q., & Su, W. J. (2021). Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training. Proceedings of the National Academy of Sciences, 118(43), e2103091118.\n\n[3] Tirer, T., & Bruna, J. (2022, June). Extended unconstrained features model for exploring deep neural collapse. In International Conference on Machine Learning (pp. 21478-21505). PMLR.\n\n[4]He, H., & Su, W. J. (2022). A law of data separation in deep learning. arXiv preprint arXiv:2210.17020.", "limitations": "The framework and the proof relies on the binary classification and no bias case which make the DUFM not so correlated to the real trained networks. \n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper generalizes the Neural Collapse to Deep Neural Collapse which describes the structure of the feature other than the last layer. The proof based on the deep unconstrained features model for binary classification is clear and easy to follow. It gives a framework to find and prove the feature structure of other layers in DUFM.\n\n2. The extensive experiments and numerical results shows that the theory successfully predicts the behavior of the deep unconstrained features model(DUFM) which exhibits proposed DNC properties. \n\n3. The paper is well written, it is smooth to follow the whole logic and the idea of the method. \n", "weaknesses": "1. Though the model and proof consider the Deep Neural Collapse which works for not only features of the last layer, the model and the proof are restrictive which works for binary classification and no bias case. Many proofs and derivations rely on binary classification like Lemma 5 - Lemma 7 which is the key to giving the conditional optimum of previous layers. \n\n2. In addition, the DUFM adds a regularization term for the first layer feature which is not fit with the real training of neural networks to some extent. \n\n3. Compared to the numerical results of DUFM, the experiments for real training of neural networks are limited to the 3-layer Resnet20. If there are more results for the training of other neural networks it will make the experiments more convincible.\n\n4. There are some typos in the proof, like L517 in the appendix where I think the $\\sigma_1^2$ should be $s_{L, i}^2$. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive, insightful and engaging review, and for pointing out the strengths of our work. We address all the points raised in the review below. \n\n**The paper only considers the binary classification and the bias-free case**\n\n*Response.* For the extension to multiple classes, please see the global response. As for the omission of the bias term, we believe it is possible to extend our analysis to include the bias. In fact, Lemmas 5-9 are unchanged, and the only changes involve Lemma 4 and Lemma 11, which can also be adjusted to accommodate the bias. However, by the argument made in [29] that the ETF structure can be obtained from the orthogonal frame (OF) structure by simply centering it, we believe that including bias would not provide significant new insights on top of our existing results. Since the computations would get much more complicated, we thus opted to omit this case.\n\n**DUFM adds a regularization term for the first layer feature which is not fit with real training of neural networks**\n\n*Response.* We agree with this point. Indeed, the regularization can be regarded as a simplification with respect to the (more complicated) nature of real training in which features are the output of regularized network layers. However, $l_2$ regularization on the unconstrained features is common to most works considering regularized UFM, see e.g. [2, 7, 25, 27, 28, 29, 30, 40, 42].\n\nFor standard last-layer neural collapse, global optimality was also demonstrated under different assumptions, such as $l_2$-norm constraints [19, 31, 36]. Thus, an interesting direction for future work is to consider constrained features instead of the $l_2$ regularization, in the context of the deep neural collapse. \n\nFinally, we highlight that our results can be readily generalized to the case where $H_1$ is regularized with any Schatten-$2/L$ pseudonorm. This pseudonorm constitutes a candidate for a more accurate regularization term. In fact, [R1] shows that regularizing a sequence of weight matrices without the ReLU activation (i.e., in a deep linear network) is equivalent to regularizing their product with the Schatten-$2/L$ pseudonorm, where $L$  is the number of the weight matrices.\n\n**Experiments for real training of neural networks are limited to the Resnet20 with 3-layer MLP on top.**\n\n*Response.* In the PDF attached to the general response above, we provide additional experiments:\n\n*(i)* We consider VGG13 and DenseNet121 architectures, keeping the rest of the experimental setup the same as in Figure 1 of the paper.\n\n(ii) We consider a 5-layer head on top of the ResNet20. \n\nAll these new experiments fully agree with the original one and support our theory. \n\n\n**Q1: is it possible to extend the DUFM to the bias case and show the STF structure in DNC2?**\n\n*Response.* We believe it is possible to do our analysis with the bias term included and this would yield results similar to the one-layer NC. Please see our response above in the weaknesses section.\n\n**Q2: In [4] the results seem to show that the Neural Collapse progresses gradually across the layers of the neural network like the measure of NC1 decreases exponentially**\n\n*Response.* We agree that there is a gap between the predictions of the DUFM and the progressive neural collapse which has been observed empirically in real networks, and investigating this gap is an important future direction. Let us make two comments in this regard.\n\n*(i)* The progressivity of DNC may be due to the non-linearity of the data, which the neural network has to eliminate throughout the layers. One reason for the gradual removal of within-class variability through the layers could be the balance between the norms of the weight matrices of different layers. In fact, decreasing the within-class variability more quickly would require larger matrix norms, which is prevented by the regularization. \n\n*(ii)* A dynamic analysis of the trajectory of gradient descent could also show a progressive neural collapse: the final layers reduce the within-class variability faster than the first ones, as training progresses. \n\nFinally, we note that the phenomenon of progressive neural collapse is not entirely understood even at the experimental level: on the one hand, [8] observes a log-linear behavior in the DNC1 reduction; on the other hand, [26] observes a reduction which is no longer log-linear.\n\n**Q3: Is it possible to directly regularize the intermediate features instead of the weight matrices from previous layers?**\n\n*Response.* Yes, this is indeed possible. This would also provide a more direct way of enforcing the occurrence of DNC, which could be beneficial for the applications of neural collapse (including e.g. transfer learning, out-of-distribution detection, robustness, and calibration, see [1, 5, 6, 15, 16, 17, 32, 34]). \n\n[R1] Shang, Fanhua, Yuanyuan Liu, and James Cheng. \"Unified scalable equivalent formulations for Schatten quasi-norms.\" arXiv preprint arXiv:1606.00668 (2016).\n"}, {"review_id": "8UWayTzi70", "reviewer": "Reviewer_FUzi", "summary": "The paper introduces an extension to the standard unconstrained features model in neural collapse theory by incorporating multiple layers above the unconstrained features. The study demonstrates that, under certain conditions and at optimality, all of the top layers exhibit all properties of neural collapse.", "questions": "See weaknesses.", "limitations": "There are no negative societal issues with this paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "-- The paper exhibits excellent writing and effectively surveys the existing literature.\n-- The paper contributes to a promising direction in the theory of neural collapse by presenting a significant extension, and it conducts a non-trivial theoretical analysis that offers compelling evidence for the occurrence of neural collapse at intermediate layers. This extension aligns with previous empirical findings, verifying the theoretical predictions made in earlier studies.\n\n", "weaknesses": "-- Like other papers in the field, the rationale behind asserting that SGD converges to a solution satisfying neural collapse solely based on optimality is not entirely clear. It would greatly benefit the paper if the authors could provide further clarification and expand upon this aspect.\n-- While the paper focuses on the binary classification case, which is acceptable, it would be valuable to discuss the feasibility and potential challenges of extending the analysis to a multiclass setting.\n-- I believe that expanding on the implications and interpretations of the results would significantly improve the paper. It would be beneficial for the authors to discuss how these findings relate to aspects like generalization and what implications they have for our understanding of deep learning in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful review and positive feedback. We address all the points raised in the review below. \n\n**The rationale behind asserting that SGD converges to a solution satisfying neural collapse solely based on optimality is not entirely clear** \n\n*Response.* We fully agree with the reviewer that the ‘static’ global optimality analysis by itself does not prove SGD convergence. Showing SGD convergence (and, thus, providing a ‘dynamic’ analysis of DNC) is a challenging future research direction.\n\nWe note that the full SGD convergence is not completely established even for the standard neural collapse, with [7, 21] giving partial solutions based on the assumptions discussed in our related work section.\n\n[12, 20, 42] try to argue the convergence by showing that the loss landscape of the unconstrained features model is benign. An equivalent statement for the DUFM is unlikely to even be true. In fact, [R1] shows that multi-layer deep linear networks exhibit spurious local minima. Including the ReLU activation intuitively does not simplify the loss landscape, nor does it make it benign. \n\n**While the paper focuses on the binary classification case, which is acceptable, it would be valuable to discuss the feasibility and potential challenges of extending the analysis to a multiclass setting**\n\n*Response.* This issue was raised by multiple reviewers. Hence, we have opted to respond to it in the global response above. \n\n**It would be beneficial to discuss the practical implications of our findings and how they relate to topics such as generalization and general understanding of neural networks.**\n\n*Response.* This is a good suggestion. We provide below three insights resulting from our theory. \n\n*(i)* Our results suggest that the $l_2$ regularization leads the deep neural network to find solutions with well-conditioned matrices (orthogonal in the ideal DNC case). This in turn provides more robust models, which also suggests better generalization. \n\n*(ii)* In principle, it should be possible to exchange the $l_2$ regularization on the weight matrices of the backbone with an $l_2$ regularization directly on $H_1$. In this way, we expect to be able to force the occurrence of the DNC more directly. Some works [1, 5, 6, 15, 16, 17, 32, 34] try to utilize the neural collapse for practical purposes (including transfer learning, out-of-distribution detection, robustness, and calibration) and this is a good way to better reach it. \n\n*(iii)* As for the general understanding of neural networks, we can learn from the DNC what is the ideal state at which deep neural networks are incentivized to represent the data, having been trained with MSE loss and $l_2$ regularization. In particular, the network tends to reduce the within-class variability and create structured feature representations. This suggests that we should treat the terms “features” and “feature extraction” with caution, as two different samples from the same class will have the same feature representation, despite being significantly different in nature (such as two images of a dog with considerably different background or coming from considerably different dog species). The after-relu DNC2 results of Theorem 3 suggest that two samples of different classes, having orthogonal, yet non-negative feature representations, cannot share the activation at any of the neurons. This means that even seemingly similar samples with different labels do not share the same feature representation at any neuron, despite perhaps sharing some major features (such as two different species of a dog with a different label, sharing most of the dog’s visual properties and only differing in fine details).  \n\n[R1] Kawaguchi, Kenji. \"Deep learning without poor local minima.\" Advances in neural information processing systems 29 (2016).\n"}]

Author rebuttal:
We would like to thank the reviewers for the positive feedback on our work. We reply to reviews separately and we address here one point raised by all reviewers.

**The paper only considers the binary classification case. Are the results generalizable to the multi-class classification and if yes, what are the main technical challenges?**

*Response.* We regard the generalization to multiple classes as an important open problem. We discuss below two technical challenges in this generalization:

*(i)* For more than two classes, Lemma 9 is false. We provide a counterexample in Appendix B for a multi-column matrix $H$ and $L=2$. This makes it difficult to obtain the optimal value of $H_2^*$, which is crucial for the rest of the analysis. On the other hand, even if Lemma 9 does not hold in full generality, [29] argues that the inequality cannot be violated for the (supposedly optimal) orthogonal matrices $H$. This indicates that counterexamples to Lemma 9 have to be ill-conditioned, which leads to an increase in the loss also in the multi-class case. Therefore, obtaining some bounds on $||H||_*$ could suffice to generalize the proof.

*(ii)* Computing the optimal solution of Lemma 5 appears to be challenging for multiple classes. In fact, a component-wise application of the ReLU activation can increase the rank of a matrix. In other words, even if $X$ is low rank, $\sigma(WX)$ can still have high rank, which significantly complicates the analysis. 

**Enclosed PDF:**

Some of the reviewers asked us to provide additional experiments supporting the validity of DUFM as a modeling principle. Therefore we provide experiments where we trained VGG13 and DenseNet121 as an alternative to ResNet20 for the 3-layer DUFM head and alternative ResNet20 training for 5-layer DUFM head. The results are in full accordance with those in the paper.


Meta-review: This paper presents a robust theoretical analysis of deep neural collapse through the deep unconstrained features model, expanding understanding of deep network behavior during training. While it offers substantial insights and empirical backing, it could benefit from extending its theoretical scope beyond binary classification and considering various loss functions. Nevertheless, its current contributions are promising.
Decision: Accept (spotlight)