extfieldsofstudy:
Computer Science
Mathematics

text:
Imbalance Trouble: Revisiting Neural-Collapse Geometry

Neural Collapse refers to the remarkable structural properties characterizing the geometry of class embeddings and classifier weights, found by deep nets when trained beyond zero training error. However, this characterization only holds for balanced data. Here we thus ask whether it can be made invariant to class imbalances. Towards this end, we adopt the unconstrained-features model (UFM), a recent theoretical model for studying neural collapse, and introduce Simplex-Encoded-Labels Interpolation (SELI) as an invariant characterization of the neural collapse phenomenon. Specifically, we prove for the UFM with cross-entropy loss and vanishing regularization that, irrespective of class imbalances, the embeddings and classifiers always interpolate a simplex-encoded label matrix and that their individual geometries are determined by the SVD factors of this same label matrix. We then present extensive experiments on synthetic and real datasets that confirm convergence to the SELI geometry. However, we caution that convergence worsens with increasing imbalances. We theoretically support this finding by showing that unlike the balanced case, when minorities are present, ridge-regularization plays a critical role in tweaking the geometry. This defines new questions and motivates further investigations into the impact of class imbalances on the rates at which first-order methods converge to their asymptotically preferred solutions.

Introduction
What are the unique structural properties of models learned by training deep neural networks to zero training error? Is there an implicit bias towards solutions of certain geometry? How does this vary across training instances, architectures, and data? These questions are at the core of understanding the optimization landscape of deep-nets. Also, they are naturally informative about the role of models since different parameterizations might affect preferred geometries. Ultimately, such understanding makes progress towards explaining generalization of overparameterized models.
Recently, remarkable new progress in answering these questions has been made by Papyan et al. [26], who empirically discover and formalize the so-called Neural-collapse (NC) phenomenon. NC describes geometric properties of the learned embeddings (aka last-layer features) and of the classifier weights of deep-nets, trained with cross-entropy (CE) loss and balanced data far into the zero training-error regime. The NC phenomenon produces a remarkably simple description of a particularly symmetric geometry: (i) The embeddings of each class collapse to their class mean (see (NC) property); and (ii) The class means align with the classifier weights and they form a simplex equiangular tight frame (see (ETF) property). Importantly, as noted by Papyan et al. [26], this simple geometry appears to be "cross-situational invariant" across different architectures and different balanced datasets.
In this paper, we study Neural collapse with imbalanced classes: Is there a (ideally equally simple) description of the geometry that is invariant across class-imbalanced datasets?  [24,3,41]. Motivated by deep-learning practice and by studies on implicit bias of gradient descent (GD) for unregularized CE minimization, we analyze the geometry of solutions to an unconstrained-features Support Vector Machines (UF-SVM) problem. We prove, for STEPimbalanced data, any solution of the UF-SVM follows the SELI geometry. Thus, the learned endto-end model always interpolates a simplex labels encoding. We show that (ETF) ⇒ (SELI). However, (SELI) ⇒ (ETF) unless classes are balanced or there is just two of them (k = 2).
Next, we analyze training of the UFM with ridge-regularized CE. Unlike previous studies, we find in the presence of imbalances that regularization matters as it changes the geometry of solutions. In fact, we show that there is no finite regularization that leads to the SELI geometry. However, we also show that as regularization vanishes, the solutions do interpolate the SEL matrix (after appropriate normalization.) Finally, we show that the SELI geometry differs from the minority-collapse phenomenon [3], since the latter does not correspond to solutions with zero training error. In fact, we show for minority collapse that: (i) It does not occur for small finite regularization and finite imbalance ratio, and (ii) It occurs asymptotically for vanishing regularization, but only asymptotically as the imbalance ratio grows.
We numerically test convergence to the proposed SELI geometry in both synthetic and real class-imbalanced datasets. For different imbalance levels, the learned geometries approach the SELI geometry significantly faster compared to the ETF geometry. See Fig. 2. However, we also observe that convergence worsens with increasing level of imbalance. A plausible theoretical justification is that as we show regularization plays critical role under imbalances. We also consistently get better convergence rate for the classifiers. We believe our observations strongly motivate further investigations regarding potential frailties of "asymptotic" implicit bias characterizations and how these might vary in multiclass and possibly imbalanced settings.

Related works
The original contribution by Papyan et al. [26] has attracted lots of attention resulting in numerous followups within short time period, e.g., [41,12,3,9,21,24,5,40,32]. (See also [9, Sec. E] for a review of the recent literature.) Several works have proposed and/or used the UFM with CE training to analyze theoretical abstractions of NC [41,12,3,5]. Other works analyze the UFM with square loss [24,9,40,32] and recent model extensions accounting for additional layers and nonlinearities are studied in [32]. Here, we drove particular inspiration from Zhu et al. [41], who presented a particularly transparent and complete analysis of the optimization landscape of ridge-regularized CE minimization for the UFM under balanced data. In the same spirit, we also relied on the UFM. However, our work is, to the best of our knowledge, the first explicit geometry analysis for class-imbalanced data. See also Table 1 for a comparison.
The only previous work on neural collapse with imbalances is [3], which was the first to note that collapse of the embeddings is preserved, but otherwise the geometry might skew away from ETF. Also, Fang et al. [3] first proposed studying the new geometry using the UFM and appropriate convex relaxations. With this setup, they presented an intriguing finding, which they termed minority collapse: for large imbalance levels, the minorities' classifiers collapse to the same vector. As mentioned above, our focus is on the, particularly relevant for deep-learning practice, zero-training error scenarios. This excludes minority collapse by definition. More importantly, we derive an explicit geometric characterization of both embeddings and classifiers for both majorities and minorities and for all imbalance levels. Specializing these findings to vanishing regularization and imbalance ratio growing to infinity recovers and gives new insights to minority collapse.
Our results also draw from and relate to the literatures on implicit bias, matrix factorization, and imbalanced deep-learning. We defer a detailed discussion on these to Sec. I of the Supplementary Material.

Organization
In Sec. 2 we setup some necessary terminology and introduce the unconstrained features model. In Sec. 3 we formally introduce the SELI geometry as the geometry of the global minimizers of the non-convex max-margin minimization over the UFM. We also relate the new SELI geometry to the ETF and derive closed-form expressions for the former in terms of the level of imbalance. Next in Sec. 4, we investigate the impact of data imbalances on the structure of the ridge-regularized CE minimization with the UFM. In Sec. 5 we present experimental results corroborating our theoretical findings. Specifically, we conduct experiments on both synthetic data under the UFM and on benchmark class-imbalanced datasets. Concluding remarks and some directions for future research are included in Sec. 6.
The proofs of our results are presented in Secs. A-C of the Supplementary Material (SM). Several additional experimental results on the UFM and on real data are also included in Sec.s F and G, respectively. Sec. H of the SM discusses in detail implications of our findings to minority collapse. Finally, Sec. I includes additional remarks and comparisons to previous works.
Notation. For matrix V ∈ R m×n , V[i, j] denotes its (i, j)-th entry, v j denotes the j-th column, V T its transpose and V † its Moore-Penrose pseudoinverse. We denote V F , V 2 , and, V * the Frobenius, spectral, and, nuclear norms of V. tr(V) denotes the trace of V. ⊙ and ⊗ denote Hadammard and Kronecker products, respectively. V ≻ 0 denotes V is positive semidefinite and V ≥ 0 that V has nonnegative entries. ∇ V L ∈ R m×n is the gradient of a scalar function L(.) with respect to V. We use 1 m to denote an m-dimensional vector of all ones and I m for the m-dimensional identity matrix. For vectors/matrices with all zero entries, we simply write 0, as dimensions are easily understood from context. e j denotes a column with a single non-zero entry of 1 in the j-th entry.

Problem setup
We adopt the unconstrained feature model (UFM) [24,3] in a k-class classification setting. Let W d×k = [w 1 , w 2 , ⋯, w k ] be the matrix of classifier weights corresponding to the k classes. Here, d is the feature dimension. We assume throughout that d ≥ k−1. Next, we let H d×n = [h 1 , h 2 , ⋯, h n ] denote a matrix of n feature embeddings, each corresponding to a different example in the training set. We assume each class c ∈ [k] has n c ≥ 1 examples (thus, n c embeddings) so that ∑ c∈ [k] n c = n. Without loss of generality, we assume examples are ordered. Formally, we assume that examples i = 1, . . . , n 1 have labels y i = 1, examples i = n 1 + 1, . . . , n 1 + n 2 have labels y i = 2, and so on. The UFM trains the features h i , i ∈ [n] (jointly with the weights w c , c ∈ [k]) without any further constraints, i.e., by minimizing the ridge-regularized cross-entropy (CE) loss as follows [41]: where L(W T H) ∶= ∑ i∈[N ] log 1 + ∑ c≠y i e −(wy i −wc) T h i is the CE loss.
UFM as two-layer linear net. The formulation above does not explicitly specify inputs for each example. An alternative view follows by considering training a 2-layer linear net with hidden dimension d, first layer H, and second layer W, over n examples with n-dimensional inputs x i = e i ∈ R n , ∈ [n] and labels y i as above: y i = 1 for i = 1, . . . , n 1 , y i = 2 for i = n 1 + 1, . . . , n 1 + n 2 , and so on.

Unconstrained-features SVM (UF-SVM)
Since neural-collapse is observed when training with small / vanishing regularization [26], it is reasonable to consider an unregularized version of (1). In this special case, gradient descent (with sufficiently small step size) on (1) produces iterates that diverge in norm, but converge in direction [22,12]. In fact, it has been recently shown that the GD solutions converge in direction to a KKT point of the following max-margin classifier [22,12]: (Ŵ,Ĥ) ∈ arg min W,H For convenience, we refer to the optimization problem in (2) as unconstrained-features SVM (UF-SVM). This minimization (unlike 'standard' SVM) is non-convex. Hence, KKT points (thus, GD convergence directions) are not necessarily global minimizers; see discussion in Sec. 6.

Class-imbalance model
To streamline the presentation, we focus on a setting with STEP imbalances. This includes balanced data as special case by setting R = 1.

Global structure of the UF-SVM: SELI geometry
In this section, we characterize the global minimizers of the non-convex program in (2). Perhaps surprisingly, we show that they take a particularly simple form that is best described in terms of a simplex-encoding of the labels.
Each columnẑ i ∈ R k ofẐ represents a class-membership encoding of datapoint i ∈ [n]. This differs from the vanilla one-hot encodingŷ i = e y i in thatẑ i =ŷ i − 1 k 1 k . Specifically,Ẑ has exactly k different and affinely independent columns, which together with the zero vector form a k-dimensional simplex, motivating the SEL name. Finally, note thatẐ T 1 k = 0; thus, rank(Ẑ) = k − 1. We gather useful properties about the eigenstructure ofẐ in Sec. A.
Moreover, the following statements characterize the geometry of global minimizers in terms of the the SEL matrix and its SVD.
(iii) For some partial orthonormal matrix R ∈ R (k−1)×d ,Ŵ = R T Λ 1 2 We outline the theorem's proof in Sec. 3.3 and defer the details to Sec. C.1. The theorem provides an explicit characterization of the geometry of optimal embeddings and classifiers that relies around the key finding that the optimal logit matrix is always equal to the SEL matrix. We highlight the following key features of this characterization.
Simplicity. The lack of symmetry in the imbalanced setting, makes it a priori unclear whether a simple geometry description is still possible, as in the balanced case. But, the theorem shows this to be the case. The key observation is that the optimal logit matrixŴ TĤ equalsẐ (cf. Statement (i)). Then, the Gram matrices of embeddings and classifiers are given simply in terms of the singular factors of the SEL matrix (cf. Statements (ii),(iii)).
Invariance to imbalances. The theorem's characterization is valid for all types of (R, ρ)-STEP imbalances. In particular, equality of the optimal logit matrix to the SEL matrix is the key invariant characterization across changing imbalances. This also implies that at optimality all margins are equal irrespective of the imbalance type. The description of Gram matrices in terms of the SVD ofẐ is also invariant. Of course, the particular arrangement of columns ofẐ itself depends on the values of (R, ρ). In turn, the singular factors determining the geometry of embeddings and classifiers depend implicitly on the same parameters. Thus, as we show next, the geometry differs for different imbalance levels; see Fig. 1 for an example.

Invariant properties: NC and SELI
Here, we further discuss the geometry of embeddings and classifiers induced by the SVD of the SEL matrix. The first realization is that the embeddings collapse under all settings.
This statement can be inferred from Theorem 1 (specifically from Statement (iii) and that U has repeated columns.) A more straightforward argument is possible by directly inspecting the UF-SVM optimization in (2). For any fixed (say optimal)Ŵ, the minimization over h i is: (i) separable and identical for all i ∶ y i = c in same class c, and (ii) strongly convex. Hence, for all i ∶ y i = c, there is unique minimizer corresponding to the fixedŴ; this must be their class mean.
Beyond (NC), Theorem 1 specifies the exact geometry of solutions. The corollary below is a restatement of Theorem 1 under the following formalization of what we call the SELI geometry. Definition 3 (SELI geometry). The embedding and classifier matrices H d×n and W d×k follow the simplex-encoded-labels interpolation geometry when for some scaling α > 0: Corollary 1.2. The UF-SVM solutions follow the SELI geometry, irrespective of imbalance.
The (SELI) geometry characterization specifies (up to a global positive scaling) the Gram matrices G W ∶= W T W and G H ∶= H T H, and the logit matrix Z ∶= W T H. Specifically, the diagonals of the two Gram matrices specify the norms of the classifiers and of the embeddings 1 . These, together with their off-diagonal entries, further specify the angles between different classifiers and between different embeddings. Because of the (NC) property, the norms and angles of the embeddings h i , i ∈ [n] are uniquely determined in terms of the norms and angles of the mean-embeddings µ c , c ∈ [k]. In other words, the Gram matrix Finally, the norms together with the entries of the logit matrix determine the angles between the two sets of: (a) the k classifiers and (b) the k mean embeddings. Thus, they specify the degree of alignment between the two sets of vectors. In the next section, we show that it is in fact possible to obtain explicit closed-form formulas describing the norms, angles and alignment of classifier and embedding vectors, in terms of the imbalance characteristics and the number of classes. Remark 3.1 (Why "SELI"?). For the UFM, Z = W T H is the learned end-to-end model. According to its definition, the SELI geometry implies W T H = αẐ. Thus, the learned model interpolates (a scaling of) the SEL matrix, motivates the naming in Definition 3.

Special case: Balanced or binary data
For the special cases of balanced or binary data, Theorem 1 recovers the ETF structure, i.e. (SELI)≡(ETF). LetM = [μ 1 , . . . ,μ k ] denote the matrix of mean embeddings. Corollary 1.3 (R = 1 or k = 2). Assume balanced data (R = 1) or binary classification (k = 2). Then, any UF-SVM solution (Ŵ,Ĥ) follows the ETF geometry as defined in [26]: Thus, when data are balanced or binary: (i) the norms of the classifiers and of the embeddings are all equal; (ii) the angles between any two classifiers or any two embeddings are all equal to ; and, (iii) the set of classifiers and the set of embeddings are aligned.

How the SELI geometry changes with imbalances
For k > 3 and R > 1, (SELI) ⇒ (ETF). In this general case, the norms and angles specifying the geometry are determined in terms of the SVD factors of the SEL matrix as per Definition 3. In Sec. A, we give an explicit characterization of these SVD factors. Notably, this allows us to obtain explicit closed-form formulas for the norms, angles and alignment of the SELI geometry in terms of R, ρ and k, n min . The following lemma is an example: it gives a formula for the ratio of majority and minority norms for the classifiers and embeddings. For simplicity, we focus on the default case of equal numbers of minorities and majorities, i.e. ρ = 1 2.
Thus, w maj 2 ≥ w minor 2 and h maj 2 ≤ h minor 2 , with equalities if and only if R = 1 or k = 2.
The fact that CE learns classifiers of larger norm for majorities (i.e. w maj 2 ≥ w minor 2 ), has been empirically observed in the deep imbalanced-learning literature, e.g. by Kang et al. [17], Kim and Kim [18]. Lemma 3.1, not only provides a theoretical justification for this empirical observation, but it also precisely quantifies the ratio. Moreover, it specifies the norm-ratio between majorities and minorities, not only for classifiers, but also for the learned embeddings.
Sec. B includes additional closed-form formulas for the angles and alignment of classifiers and embeddings. Thanks to these, it is easy to precisely quantify the changes in the geometry as a function of the imbalance ratio and of number of classes. As another example of this, besides  : Illustration of how norms and angles of the SELI geometry vary with the number of classes k and the imbalance ratio R. The minorities fraction is set to ρ = 1 2. Unless R = 1 or k = 2, the geometry differs from the ETF geometry. For example, majority classifiers have larger norms than minorities (see Fig. 3a), minority classifiers are less aligned with their corresponding class mean-embeddings (see Fig. 3b), and the angle between minority classifiers decreases (see Fig. 3c).
The depicted values are computed thanks to closed-form formulas. See Sec. 3.2 and Sec. B. Lemma 3.1, the SELI geometry leads to majority / minority angles for the classifiers satisfying the following formulas: (with (R, 1 2)-STEP imbalance; see Sec. B.1.2 for details) Here, w maj , w ′ maj are two classifier vectors corresponding to any two majority classes (similarly for the minorities.) It is easy to see that both these formulas evaluate to −1 (k − 1) for R = 1. Furthermore, the cosine of majorities is strictly decreasing, while the cosine of minorities is strictly increasing. That is, with increasing imbalance ratio majority classifiers go further away from each other, while minority classifiers come closer. These properties, together with the fact from Lemma 3.1 that majority classifiers have larger norms compared to minorities, is visualized in Fig. 1 for R = 10 and k = 4. Additionally, Fig. 3 shows how all the norms and angles of the geometry vary with the imbalance ratio R for several values of k = 2, 4, 10, 20.

Remark 3.2 (Asymptotics).
While we focus on understanding the geometry at finite values of R, it is possible to evaluate limits for our formulas giving asymptotic characterizations as R → ∞. The asymptotic behaviors can also be observed in Fig. 3. As an example, it is easy to see from (4) that the angle between the minority classifiers collapses to zero in that limit. This phenomenon is called "minority collapse" by Fang et al. [3]. Here, we recover it as a special case of Theorem 1 and of the SELI characterization. Note also that the rate at which the minority angle collapses is rather slow (e.g. see Fig. 3c). Additional details and discussion on the SELI geometry are included in Sec. B.

Proof sketch
We start from the following (by now, relatively standard) convex relaxation of the UF-SVM [31,8,41,3]: The relaxation follows by setting Z = W T H, thus Z is the logit matrix (also, the end-to-end model) of the non-convex UF-SVM. Our key technical innovation is proving thatẐ is the unique minimizer of (5). There are three key ingredients in this. First, is a clever re-parameterization of the dual program to (5), introducing the SEL matrixẐ in the dual: Second, we prove thatB = UV T is the unique maximizer of the re-parameterized dual problem in (6). While it is not hard to check thatB optimizes a relaxation of (6), it is far from obvious that B is unique, and, even more that it satisfies the third constraint. The key technical challenge here is that the third constraint acts entry-wise on B. In fact, to proceed with the proof we need that the constraint is not active, i.e.B ⊙Ẑ T > 0, or equivalently, that the sign pattern of the entries ofB agrees with the sign pattern of the transpose SEL matrixẐ T . We prove this by an explicit construction of the singular factors U, V exploiting the structure of the SEL matrix.
Once we have shown thatB is the unique maximizer and is strictly feasible, we use the KKT conditions to prove thatẐ is the unique minimizer of the nuclear-norm relaxation in (5). To do this, we leverage that strict feasibility ofB implies by complementary slackness all constraints in the primal (5) must be active at the optimum. The proof of the theorem completes by arguing that the relaxation (6)

The role of regularization
In this section, we focus on the ridge-regularized CE loss minimization in (1). Specifically, we study the geometry of solutions (Ŵ λ ,Ĥ λ ) as a function of both the imbalance and the regularization parameter λ.

Global minimizers as solutions to a convex relaxation
The regularized CE minimization in (1) is non-convex. Yet, its landscape is benign and the global solution can be described in terms of the solution to a convex relaxation program [41].
Theorem 2 (Reformulated from [41]). Let λ > 0, d > k − 1 and a (R, ρ)-STEP imbalance setting. LetẐ λ ∈ R k×n be the unique minimizer of the convex nuclear-norm-regularized loss minimization, and, denoteẐ λ = V λ Λ λ U T λ its SVD. Any stationary point of (1) satisfies exactly one of the following two. Either it is a strict saddle, or, it is a global minimizer (Ŵ λ ,Ĥ λ ) and satisfies First, the statement ensures that any first-order method escaping strict saddles finds a stationary point that is a global minimizer [41]. Moreover, it describes the structure of the global minimizers of (1) in terms ofẐ λ , the solution to the convex minimization in (7). Structurally, the characterization in (8) resembles the characterization in Theorem 1 regarding the UF-SVM. However, Theorem 1 goes a step further and gives an explicit form for the logit matrix, namely the SEL matrixẐ. Instead,Ẑ λ in Theorem 2 is given implicitly as the solution to a convex program. In the remaining of this section, we ask: how doesẐ λ compare toẐ for different values of the regularizer? Also, how does the answer depend on the imbalance level?

Regularization matters
For balanced data, previous works have shown that the minimizersŴ λ ,Ĥ λ of (1) satisfy the (NC) and (ETF) properties (up to scaling by a constant) for every value of the regularization parameter λ > 0 [41] (see also [5,3,21].) In our language, for all λ > 0, there exists scalar α λ such that a scaling (α λŴλ , α λĤλ ) of any global solution of the regularized CE minimization in (1) satisfies the ETF geometry. Thus, for balanced data, up to a global scaling, the geometry is: (i) insensitive to λ > 0 and (ii) the same as that of the UF-SVM minimizers.
Here, we show that the situation changes drastically with imbalances: the regularization now plays a critical role and the solution is never the same as that of UF-SVM for finite λ. Proposition 1 (Imbalanced data: Regularization matters). Assume imbalanced data and k > 2. There does not exist finite λ > 0 and corresponding scaling α λ such that the scaled solution (α λŴλ , α λĤλ ) of (1) follows the (SELI) geometry. Equivalently, there does not exist λ > 0 and α λ such that a scaling of the UF-SVM solution solves (1).

Vanishing regularization
As λ vanishes, it is not hard to check that minimizers diverge in norm and the relevant question becomes: where do they converge in direction? The following answers this.
Proposition 2 (Regularization path leads to UF-SVM). Suppose d > k − 1 and (R, ρ)-STEP imbalance. It then holds that lim λ→0Ŵ Put together with the content of the previous section: For balanced data, the solution is always the same up to global scaling. However, for imbalanced data, the solution changes with λ and only in the limit of λ → 0 does it align with that of the UF-SVM.
Regarding the proof of the proposition, we note that thanks to Theorems 1 and 2, it suffices that the solutionẐ λ of (7) converges in direction to the SEL matrixẐ; see Proposition 3 in Sec. D. To show this, we critically use from Theorem 1 thatẐ is unique minimizer of (5). See Sec. E.3 for details. The most closely related results are those of [28,16], who studied the regularization path of p-norm regularized CE.

Imbalance emphasizes the impact of non-convexity
Recall interpreting the UFM as a two-layer linear net trained on the standard basis e i ∈ R n . Suppose instead that we train a simple k-class linear classifier Ξ k×n on the same data by minimizing ridge regularized CE: min Ξ L(Ξ) + λ 2 Ξ 2 F . It is easy to check that (after scaling) Z satisfies first-order optimality conditions. Thus, the optimal linear classifier is such that for all λ > 0, there exists α λ such thatΞ λ = α λẐ . Contrasting this to Proposition 1, we find that the end-to-end models minimizing ridge-regularized CE for a linear versus a two-layer linear network are the same (in direction) when data are balanced, but differ under imbalances.

Experiments
In our experiments we choose (R, 1 2)-STEP imbalances with varying imalance ratio R. In all cases we measure convergence to either the (SELI) or the (ETF) geometries, in terms of the three metrics below corresponding to classifiers, embeddings, and logits, respectively. Denote A = A A F the Euclidean normalization and G A = A T A the Gram matrix of matrix A.      G M = M T M toĜ M , which we calculate as described above for the ETF and SELI geometries, respectively. On the other hand, for the logits calculations, we compute Z = W T M without centering. The discrepancy between the UFM solutions being already centered, while deepnet embeddings require centering before computation of geometric measures is a common denominator in all previous works on the UFM, e.g. [41,12,3,9,21,24,5,40]. Here, the chosen centering µ G = 1 k ∑ i∈[n] 1 ny i h i is in general different (and the same only when classes are balanced) from the global centering h G ∶= 1 n ∑ i∈ [n] h i used by Papyan et al. [26]. Our choice of the former is motivated by the fact that the SELI geometry (as predicted by the UFM) satisfies ∑ c∈[k] µ c = 0 (see Eqn. (20) in Sec. ), but not always 1 n ∑ i∈[n] h i = 0.  (7) with CVX [6], and then, using (8) to infer the Gram matrices G W , G M and logits W T H. Fig. 4c shows that the distance to ETF is large and not approaching zero for any value of λ. On the other hand, Fig. 4a numerically validates Propositions 1 and 2: the distance to SELI for all three metrics is non-zero for any finite λ > 0, but converges to zero as λ → 0. However, this convergence is slow and the rate becomes even worse as R increases. Finally, Fig. 4b depicts the minimum margins of solutions across λ. Note that for all sufficiently small λ values, the minimum margin is strictly positive. We prove this in Lemma D.4 in Sec. D.2. As a byproduct, this shows that the "minority collapse" of [3] can only possibly occur for large λ; see also Sec. H.  each R, we select the sample size n min for minorities so that the total number of samples n = (R + 1) 2 kn min is ≈ 400. The weights of the UFM are optimized using SGD with constant learning rate 0.4, batch size 4 and no weight decay. We train for 10 5 epochs, much beyond zero training error and plot the distance to SELI and ETF geometries for classifiers, embeddings and logits over time. We highlight the following three observations: (i) SGD iterates favor the SELI, instead of the ETF geometry. As a matter of fact, the distance to SELI is decreasing with epochs, suggesting an implicit bias of SGD towards global minimizers of the UF-SVM. (ii) However, convergence is rather slow and rates get worse with increasing imbalance. (iii) Also, the embeddings convergence is more elusive compared to that of the classifiers. Interestingly, the last two observations are reminiscent of the trends we observed in Fig. 4a, suggesting connections between regularization path and (S)GD iterates, worth investigating further.

UFM: SGD solutions
We refer the reader to Sec. F for additional numerical results on the UFM, such as experiments with varying weight-decay and regularization choices.

Deep-learning experiments
We investigate convergence to the proposed SELI geometry in deep-net training of (R, ρ)-STEP imbalanced MNIST, Fashion-MNIST and CIFAR10 datasets. For concreteness, we consider here equal number of minorities and majorities, i.e. ρ = 1 2. Additional experimental results for other values of the minority ratio are deferred to Sec. G.3. For all datasets, we keep the same total number of n = 100 × 50 × 5 + 50 × 5 = 25250 examples across all different imbalance ratios R = 1, 5, 10 and 100. No data augmentation was used following [26]. We train two deep architectures, ResNet-18 [10] and VGG-13 [29], and optimize the models using CE loss with SGD over 350 epochs. In all experiments, the initial learning rate is set to 0.1 and decreased by a factor of 10 at epochs 120 and 240. For ResNet training on MNIST, we choose smaller initial learning rate 0.05 which we empirically find that it interpolates data much faster. Weight decay and momentum are set to 5 × 10 −4 and 0.9 respectively. Models are trained on a single GPU with a dataloader batchsize of 128. To evaluate the learnt geometries, we track the three metrics that we defined at the beginning of this section. Recall also that following [26], we first perform a global centering by subtracting from the mean embeddings their global average. The convergence to SELI and ETF for the classifiers, (centered) mean-embeddings, and logits are illustrated in Fig. 2 and 6 for ResNet and VGG models, respectively. The vertical dashed lines mark the epoch at which the model reaches zero training error under all imbalance ratios; see Sec. G.1.2 for details. Note that in all plots, the distance to SELI geometry decreases as training evolves. Also, convergence to the SELI geometry is consistently better compared to the ETF geometry. However, convergence slows down for increasing imbalance (see R = 100). Another interesting observation is that convergence is worse for the embeddings compared to classifiers. In Sec. G.1.6 we compare individual quadrants of the (normalized) G W and G H matrices, which facilitates understanding the individual behavior of majorities and minorities.
In Fig. 7 we focus on predicting the norms of the classifiers. In particular, we measure the norm ratio of the classifiers during training and compute its distance from the predicted closed-form SELI characterization in Lemma 3.1. We see that the (relative) magnitude of the classifiers agrees with the value predicted by the SELI geometry. Analogous plots for the embeddings' norms are given in Sec. G.1.4.

Outlook: Imbalance troubles and opportunities
We propose (SELI) as the class-imbalance-invariant geometry of classifiers and embeddings learnt by overparameterized models when trained beyond zero training error. We arrive at it after showing that the UF-SVM global minimizers follow this geometry. Subsequently, we conjecture that: (C1) GD on the UFM leads to solutions approaching the SELI geometry asymptotically in the number of epochs; (C2) training of deep-nets beyond zero training error learns models that approach the SELI geometry. Statement (C1) is a conjecture and does not follow from Theorem 1. This is because GD is only known to converge to KKT points of the non-convex UF-SVM [22,12], which are not necessarily global minima. Thus, while Proposition 2 combined with the benign landscape of the corresponding ridge-regularized minimization, as well as, our experiments suggest its validity, the conjecture remains to be further investigated. 2 We also note that convergence rates appear slower with increasing imbalance levels; a feature which is interesting to study further.
Regarding conjecture (C2), we deem our experiments encouraging: the classifiers' and embeddings' geometries get closer to the SELI geometry as neural-network training progresses. Specifically, the Gram matrices G W and G H of the classifiers and embeddings, respectively, align increasingly better with their SELI counterparts VΛV T and UΛU T ; see Fig. 2. Also, Fig. 7 shows that Lemma 3.1 is able to make predictions regarding the norms of majorities versus minorities. We note that, similar to the UFM experiments, convergence appears slower for larger imbalance ratios. Also, we observe better convergence for classifiers compared to embeddings and for norm predictions compared to angle predictions. Overall, we hope our results motivate further theoretical and experimental investigations, especially since data imbalances appear frequently across applications.
Beyond that, we believe that further similar studies on identifying geometric structures of learned embeddings and classifiers could offer new perspectives on generalization. Our results could pave that way since they uncover different geometries (aka SELI for different R values), each leading to different generalization (worse for increasing R [1]). Relatedly, we envision that further such studies lead to algorithmic contributions in imbalanced deep-learning as they can facilitate studying the implicit-bias effect of CE adjustments and post-hoc techniques tailored to imbalanced data [2,23,39,18,17,19,20].

Roadmap to the Supplementary material
The SM contains the following. In Section A we derive several useful properties of the simplexencoded-label (SEL) matrix, which we then use in Section B to present closed-form characterizations of the embeddings and classifiers geometries. Notably, these include explicit expressions for the norms and angles of both majority and minority classes, which we accompany with numerical illustrations shedding further light on the features of the proposed (SELI) geometry. Next, in Section C, we use the derived properties of the SEL matrix to prove our main Theorem 1 and its corollaries. In Section D we derive several useful properties of the nuclear-norm penalized CE minimization, which we then use in Section E to prove the statements of Section 4. Section F contains additional numerical results on the UFM, such as experiments with varying weight-decay and regularization choices. Additional experiments on real data (such as, isolated minority/majority geometry investigations, and classifiers/embeddings norm ratios), as well as further implementation details, are included in Section G. In Section H we show how results relate to minority collapse providing additional theoretical justifications and novel perspectives to empirical observations reported by previous work. Finally, an elaborate discussion on additional related works is contained in Section I.
Proof. Proof of (i): Follows directly from the definition. Proof of (ii): The fact thatẐ T 1 k = 0 is easy to check. Hence, the rank is at most k − 1. The fact that the rank is exactly k − 1 follows by noting that the vectors e c − 1 Proof of (iii): Follows directly from Statement (ii). Proof of (iv): Follows easily by direct calculations.
It is easy to see that for Z = αẐ, the matrix A can be written as The desired then follows by recalling Statement (i).
and, for c ≠ y i ,

A.2 Eigen-structure
In this section, we explicitly compute the eigenstructure of the SEL matrix for (R, ρ)-STEP imbalanced data. To simplify the expressions, we assume n min = 1. 3 Also, we need the following definitions. For m ∈ [k], let P m ∈ R m×(m−1) denote an orthonormal basis of the subspace orthogonal to 1 m , i.e. P m P T m = I m − 1 m 1 m 1 T m and P T m P m = I m−1 . We will also denote . Assume (R, ρ)-STEP imbalanced data and n min = 1. Also, denote ρ = 1 − ρ and recall that the total number of examples is n = (ρ + Rρ)k. Then, the SVD factors ofẐ = VΛU T are given as follows: 3 It is rather easy to derive all formulas without this requirement. Concretely, the singular values in (9) Proof. The challenging part is coming up with the formulas in (9), (10) and (11) for the SVD factors. The lemma already does this for us. Hence, proving that the formulas are correct involves a few tedious calculations, which we present below. Let us define for convenience: Similarly, let With same argument as above, it is easy to check that U T U = I k−1 .
Here, we also use that Thus, it suffices to show that VΛU T =Ẑ. The key observation here is thatẐ can be written in block-form as followsẐ With these, we have the following direct calculations:

A.2.1 Special case: Balanced data
When classes are balanced, i.e. R = 1, the following simple description of the SVD factors is immediate to see from Lemma A.3.

Corollary 2.1.
Assume balanced data and n min = 1. Recall that P k ∈ R k×(k−1) denotes an orthonormal basis of the subspace orthogonal to 1 k . Then,Ẑ = P k P T k , that is A.2.2 Special case: Equal minorities / majorities (ρ = 1 2) Another special case of interest is when the numbers of minorities and majorities are the same, i.e. ρ = 1 2. In this case, we get the following simplification of Lemma A.3.

Corollary 2.2.
Consider the setting of step imbalance with even number k = 2m, m ≥ 1 of classes. Let n min = 1. Then, the SVD ofẐ is as follows:

A.3 A useful property of the singular spaces
The following result is particularly important for the proof of Theorem 1. It shows that the singular spaces V, U ofẐ are such that the matrix UV T has entries that agree on their sign with the sign of the entries ofẐ T . Proof. From Lemma A.3, we have explicit expressions for the SVD factors U and V. From these, we can directly compute that To continue, recall again that for any integer m: Hence continuing from the display above we find that Finally, recall from (12) the block-form ofẐ repeated here for conveniencê By inspection, the signs ofB 12 ,B 21 are negative, same as the signs ofẐ T 21 ,Ẑ T 12 . To see that the signs of the diagonal blocks also agree it suffices to check that the following strict inequalities always hold This completes the proof of the lemma.

B The SELI geometry
As mentioned the SELI geometry is described in terms of the SVD of the SEL matrixẐ. In this section, we show that it is in fact possible to get explicit closed-form expressions describing the SELI geometry in terms of the parameters R, ρ, k. Key to this is the explicit construction of the SVD factors in Sec. A.2.
For concreteness, we focus on the case of equal numbers of minorities and majorities (i.e. ρ = 1 2) since the formulas are somewhat simpler and the setting is of sufficient interest to convey main messages. Extension to the general case can be done in a similar fashion.
All results in this section hold under the following assumptions (assumed throughout without further explicit reference): • A (R, 1 2)-STEP imbalanced setting.
• The classifiers w c , c ∈ [k] and the embeddings h i , i ∈ [n] follow the SELI geometry in Definition 3.

B.1.1 Norms
The following two lemmas are essentially restatements of Lemma 3.1. where we let w maj 2 / w minor 2 denote the majority / minority norm of an arbitrary class of the corresponding type.
(ii) It holds that Thus, w maj 2 ≥ w minor 2 with equality if and only if R = 1 or k = 2.
Proof. Recall, since the classifiers follow the SELI geometry, it holds that W T W = VΛV T . Hence, it suffices to compute the diagonal of the matrix VΛV T . We have From this, the statements of the lemma follow readily. where we let h maj 2 / h minor 2 denote the majority / minority norm of an arbitrary example of the corresponding type.

Lemma B.2 (Norms of embeddings
(ii) It holds that Thus, h maj 2 ≤ h minor 2 with equality if and only if R = 1 or k = 2.
Proof. Recall, since the classifiers follow the SELI geometry, it holds that H T H = UΛU T . Hence, it suffices to compute the diagonal of the matrix UΛU T . Recalling that n = k(R + 1) 2 We have From this, the statements of the lemma follow readily by reading out the diagonal.
Proof. Recall under the SELI geometry that W T W = VΛV T . Hence, inspecting the offdiagonal entries of the matrix computed in Equation (14) gives Statement (i) and the following inner-product relations: Combine these with the norm calculations in Lemma B.1 to prove Statement (ii).

(ii) It holds that
Proof. Recall under the SELI geometry that H T H = UΛU T . Hence, inspecting the off-diagonal entries of the matrix computed in Equation (16) gives Statement (i) and the following innerproduct relations: Combine these with the norm calculations in Lemma B.2 to prove Statement (ii).

B.1.3 (Non)-alignment
In the previous lemmas we compute the angles between classifiers of different classes and between embeddings of different classes. Here, we also also compute the angles between classifiers and embeddings. Specifically, for each c ∈ [k], we compute the angle Cos(w c , h i ) for an example i ∶ y i = c that belongs to the same class. These values can be thought of as the degree of alignment between classifiers and embeddings, as Cos(w c , h i ) = 1 corresponds to exact alignment between the two. (ii) It holds that Proof. The proof is immediate by recognizing that under the SELI geometry for all c ∈ [k] and i ∶ y i = c it holds that w T c h i = 1 − 1 k.

B.1.4 Centering
It is easy to see that the classifiers w c , c ∈ Note that this reduces to ∑ i∈[n] h i for balanced data, but is not true otherwise. To see (19) recall first that H T H = UΛU T . Second, check that ∑ i∈[n] . Thus, U T ω = 0. Combining these two it follows that Hω = 0, which gives the desired. Now, suppose that the (NC) property also holds, i.e. the embeddings collapse to their class means, that is, Then, (19) implies the following about the class means: Therefore, the class means are always centered around zero.

B.2 Illustrations and discussion on dependence on R and k
In the previous section, we derived closed-form expressions for the features describing the SELI geometry. Here, we use these expressions to study how varying values of class-number k and imbalance-ratio R change the geometry. We use the numerical illustration in Fig. 8 to guide the discussion. Specifically, in Fig. 8 we compute and plot the norm ratios, alignment and angles between embeddings and classifiers for k = 2, 4, 10, 20 classes and imbalance ratio varying from 1 (aka balanced) to 100.  Norms. Fig. 8a shows the ratios of majority vs minority norms for both classifiers and embeddings. The values are computed using Lemmas B.1 and B.2. For binary problems (aka k = 2), the norm ratio is always equal to one irrespective of imbalance. For larger values of k, the norm ratio is equal to one only for balanced classes (aka R = 1). Recall that equal norm ratios is a feature of the ETF geometry [26]. On the other hand, for k ≠ 2 and R > 1, the majorities have strictly larger norms for the classifiers and strictly smaller norms for the embeddings. Thus, in general the SELI geometry is very different from the ETF geometry. Interestingly, the difference is already evident when going from k = 2 to k = 4 classes. Also, the change in the ratios for classifiers is more pronounced than that for embeddings, which is changing progressively slower as k increases (see how close are the green and blue curves in the right plot).
Alignment. Fig. 8b shows the degree to which the geometries of classifiers and embeddings are aligned to each other. Specifically, we plot the cosine between any majority (left) / minority (right) classifier and corresponding embeddings belonging to the same class; see also Lemma B.5. For k = 2 and R = 1 the cosines are equal to one indicating that classifiers and embeddings align for both majorities and minorities. This is consistent with the ETF geometry. On the other hand, the alignment property breaks when k > 2 and R > 1. The effect is more drastic for the minorities (right plot), while for majorities the alignment is approximately preserved (note the y-axis scale is different in the two plots). Interestingly, alignment is in fact favored for larger number of classes, but deteriorates with increasing R consistently for all values of k.
Angles. Fig. 8c shows the angles between majority/majority (left), minority/minority (center), and minority/majority (right) for both classifiers (top) and embeddings (bottom). The values are computed using Lemmas B.3 and B.4. For binary problems (aka k = 2), there is only one majority and one minority class. Thus, we only plot the minority/majority cosines, which are always equal to −1 (k − 1) irrespective of imbalance. For larger values of k, the cosines are equal to that same value −1 (k − 1) only for balanced classes (aka R = 1). Recall that cosine value equal to −1 (k − 1) is a unique feature of the ETF geometry. On the other hand, for k ≠ 2 and R > 1, the cosines are different. For reference, we plot the values of −1 (k − 1) in dashed lines. For the classifiers, the majority angles increase, while the minority angles decrease. The rate of change is more drastic for minorities. In both cases, the rate of change across R is more pronounced for smaller k. The majority-minority angles also increase with R. The trend is reversed for embeddings. For example, the angles between minority embeddings become larger with increasing R. Again, the effect of imbalance (at least for the values of R shown) is more pronounced here for smaller values of k.

B.3.1 Balanced classes and binary classification
The

B.3.2 Asymptotics
We can also use the results of Sec. B.1 to understand the SELI geometric features asymptotically as R increases. These are included in Corollary 2.4 below. See also Fig. 3 for a numerical illustration of the limiting behavior for large imbalance ratios.
Proof. The expressions that appear in the lemmas in Sec. B.1 hold for any value of R. Take the limit of R → ∞ to yield the expressions above. We omit the details for brevity.
Several interesting conclusions are immediate from the formulas above. For example, Statement (iv) shows that, asymptotically in R, the minority classes collapse to the same vector. This is a manifestation of the minority collapse phenomenon discovered by Fang et al. [3]. Asymptotic minority collapse had not been shown before for the UF-SVM. See also Sec. H for an extended discussion. We note that beyond minority classifiers, Corollary 2.4 is further conclusive about the behavior of majority classifiers, as well as, minority and majority embeddings. For example, Statement (viii) suggests that the minority and majority embeddings become orthogonal to each other asymptotically. Further investigations of the validity of such asymptotic conclusions in deep-net training is beyond our scope.

C Proofs for UF-SVM Section 3 C.1 Proof of Theorem 1
We consider a relaxation of the non-convex SVM in (2) by setting With this consider the following semidefinite program: It is not hard to see that q * ≤ p * . In what follows, we will compute the optimal set of (22) and use this to show that the relaxation is in fact tight. This will allow us to characterize the solution of the original problem. (22) is convex and satisfies Slater's conditions. (Since constraints are affine, it suffices to check feasibility, which is easily verified.) Hence, strong duality holds and KKT conditions are necessary and sufficient for optimality. The dual of (22) is written as follows:

Dual of the convex relaxation: The optimization in
sub. to Also, the complementary slackness conditions are Instead of working with the dual in the above standard form, it is convenient to work with an alternative representation by (re)-defining dual variables β ic , i ∈ [n], c ∈ [k] such that 4 sub. to Analogously, the complementary slackness conditions in (24) are equivalent to the following: To see the equivalence of the objective of (26) denote A = ∑ i∈[n] ∑ c≠y i α ic the objective in (23) and note that we get simultaneously A = ∑ i∈[n] β iy i = ∑ i∈[n] ∑ c≠y i − β ic following the definition in Equation (25). Then, we have Solution to the dual: To continue, we consider the following relaxation of the dual problem (26) (by removing the constraint in Equation (27)): Here, recall that B 2 denotes the spectral norm, hence the first constraint is equivalent to the first constraint in the maximization in (26) by Schur-complement argument. Using standard arguments, it can be shown thatd ≤ Ẑ * and equality holds by settinĝ where we recalled the compact SVDẐ = VΛU T . It is also not hard to see thatB is feasible in (29) (recall here that V T 1 k = 0). Hence,B is a maximizer andd = Ẑ * . The following lemma, the proof of which we defer to the end of this section, proves something stronger:B is in fact the only maximizer in (29). (29) is Ẑ * andB = UV T is its unique maximizer.

Lemma C.1. The optimal cost of the maximization in
Next, we use Lemma C.1 to show thatB also satisfies the inequality constraints in (27). To do this, we use an explicit construction of the singular factors U and V presented in Sec. A.2, which is possible thanks to the special structure ofẐ. Specifically, we prove in Lemma A.3 that Hence,B is feasible in (26). In fact, the feasibility inequalities are strict, which we will use soon. For now, note that feasibility ofB in (26) guarantees that it is its unique maximizer (since it is the unique maximizer of the program's relaxation, as established in Lemma C.1.) Therefore, andB in (30) is dual optimal for the semidefinite program in (22).
Solution to the primal relaxation: By strong duality, this implies q * = d * = Ẑ * and that any primal minimizerX = X 11X12 X T

12X 22
satisfies the complementary slackness conditions in (28) with In (33)  Combining the last two equations shows Next, we will useX 12 = VDU T in (33) to compute D. For convenience denote e k,c ∈ R k the c-th standard basis vector in R k and e n,i ∈ R n the i-th standard basis vector in R n . Then, starting with (33), we get the following chain of implications: where the second and third equalities used V T V = U T U = I k−1 . To conclude, we have shown that any optimal pointX of (22) satisfieŝ Solving the original problem: Now, we show that the convex relaxation in (22) is tight. For some partial orthonormal matrix R ∈ R (k−1)×d (recall that d ≥ k − 1) with RR T = I k−1 , let By construnctionŴ TĤ =X 12 . Hence, (Ŵ,Ĥ) is feasible in (2). Thus, p * ≤ 1 2 tr(X) = q * . But, we have already argued that p * ≥ q * . Hence, p * = q * .
Proof of Lemma C.1: It only remains to prove Lemma C.1, which we do here. Any feasible B satisfies B 2 ≤ 1. Hence, also recalling thatẐ has rank k − 1 (because V T 1 k = 0): The inequality above is tight if and only if which is indeed satisfied byB = UV T . Clearly,B is also feasible. Hence,B is a maximizer of (29). Next, we will show that there is no other maximizer, sayB. Indeed, sinceB is optimal, it must satisfy (40). Hence, it has rank at least k − 1. But sinceB1 k = 0, we find thatB has rank exactly k − 1.
with columns p i , q i , i ∈ [k − 1]. By Equation (40) we have the following chain of inequalities for all i ∈ [k − 1]: Inspecting this, we note that all inequalities must be equalities. The first inequality in the second line follows because B 2 ≤ 1 ⇒ ∀j ∈ [k − 1] ∶ σ j ≤ 1. Hence, σ j = 1 for all j ∈ [k − 1]. Equivalently Σ B = I k−1 . The second inequality in that same line is Cauchy-Schwarz and equality implies The last inequality follows because Since U B (resp. V B ) has orthonormal columns, equality in (43) holds if and only if for all i ∈ [k − 1], u i (resp. v i ) is a column of U B (resp. V B ). Then, it must be that P and Q are permutation matrices. Combined with (42) this gives for some permutation matrix Π. Continuing from this, Putting things together, we conclude that This concludes the proof of the lemma. 1.1, 1.2, 1.3

and of Lemma 3.1
The proofs of the rest of the results of Sec. 3 are presented in the following sections.

C.3 On different regularization hyperparameters between embeddings and classifiers
Thus far in our analysis of the UFM, we assumed same regularization strength λ for the embeddings and classifiers; see Eqn. (1). Here, we discuss a slight generalization allowing different regularizations λ W and λ H for the classifiers and embeddings, respectively. This is motivated by previous studies of the UFM in the literature, e.g. [41]. As we show, this modification does not change the SELI geometry modulo a relative scaling factor between the embeddings and classifiers. Concretely, consider the following slight generalization version of Eqn. (1): which can be more conveniently reparameterized as follows: where β ∶= λ H λ W and λ H , λ W > 0. Now, consider the limit of vanishing regularization λ W → 0, λ H → 0, with a fixed finite and non-zero ratio β 2 = λ H λ W . Entirely analogous to Eqn. (2), this leads to the a β-parameterized UF-SVM as follows: Note that the UF-SVM we study in Eqn. (2) is a special case of the above for β = 1. For general values of β > 0, it is not hard to see that there is a one-to-one mapping of global solutions (Ŵ β ,Ĥ β ) of (45) to global solutions (Ŵ β ,Ĥ β ) of (2) as follows: Hence, from Theorem 1, it follows that the solutions of (45) satisfy for any β > 0 the following: Therefore, different regularization between embeddings and classifiers only affects the geometry of global minimizers of the corresponding UF-SVM (i.e., at vanishing regularization) up to introducing an extra scaling factor between the Gram matrices of embeddings and classifiers. Specifically, this only affects the relative scaling between the norms of embeddings and classifiers.

D Nuclear-norm relaxations of the UFM
In this section, we gather useful properties of the nuclear-norm-regularized CE minimization (7), repeated here for convenience:Ẑ These properties are useful in the proof of the results that appear in Sec. 4. As a reminder, the nuclear-norm-regularized CE minimization is relevant to us because of Theorem 2, i.e. it forms a tight convex relaxation of the non-convex ridge-regularized CE-minimization for the UFM.
The following lemma gathers some basic properties, which we use later to study the behavior of the solutions to (7) for different regularization strengths.
Lemma D.1 (Basic properties of (7)). The following statements are true.
(i) There is a unique minimizerẐ λ .
(ii)Ẑ λ satisfies the following necessary and sufficient first-order optimality conditions: Proof. We prove each statement separately below.
Proof of (ii): This is straightforward from first-order optimality of the convex program (7). For example, see [41,Lemma C.3] for details.
Proof of (iii): Start from Statement (ii) and use from Lemma A.2 that 1 T k ∇ Z L(Ẑ λ ) = 0. Then, it must then be that 1 T where the last equality uses optimality ofẐ λ . The above display contradicts optimality ofẐ λ + ∆ and completes the proof. . The function y is strictly convex along any direction on the (k − 1)-dimensional subspace orthogonal to 1 k . That is, for all non-zero v ∈ R k such that Proof. Define univariate function g(t) = y (z + tv). From Taylor's expansion, for some θ ∈ (0, 1) Hence, it will suffice showing that v T ∇ 2 z y (z)v > 0 for any z. that v = Ca. But then, v T 1 k = 0, which violates the lemma's assumption.
The key observation here is that 2 for a formula evaluating the gradient.) Thus, ∇ Z L(0) 2 = Ẑ 2 , which completes the proof.
We note that, for (R, ρ)-STEP imbalance the necessary and sufficient condition of the lemma
In Sec. H we combine Theorem 2 with Lemma D.4 above to show that the solution (Ŵ λ ,Ĥ λ ) of (1) cannot satisfy the minority collapse property.
The proposition is an extension of [28, Theorem 3.1] to nuclear-norm regularization. Its proof follows the exact same steps as in Rosset et al. [28] who studied p -regularization. The critical observation allowing this is thatẐ is the unique minimizer of (2) thanks to Theorem 1. Because of that, we can get the following max-margin formulation for (the normalized)Ẑ, which is key in the proof of Proposition 3. Lemma D.5. Assume (R, ρ)-STEP imbalance so thatẐ is the unique solution of (2) (see Theorem 1). Then, it holds that We present the proof of Proposition 3 together with the proof of Lemma D.5 in the next section.

D.3.1 Proof of Proposition 3
First, by KKT conditions (see Lemma D.1(ii)), as λ → 0, we have ∇L(Ẑ λ ) 2 → 0. This, in turn, diverges. To see this, denote G λ ∶= ∇L(Ẑ λ ) and note from Lemma A.2 that for all Assume for the sake of contradiction that lim λ→0Ẑ λ Ẑ λ * =Z forZ ≠Ẑ Ẑ * . Then, by Lemma D.5, it must be that Moreover, since m λ → +∞, we also have that m > 0. The rest of the argument follows mutatismutandis the proof of [28, Theorem 2.1]. We repeat here for completeness. By continuity of the minimum margin in Z, there exists open neighborhood ofZ on the nuclear-norm sphere: and an > 0 such that min i∈ [n], To continue, we use the following lemma Lemma D.6. Assume Z 1 , Z 2 such that Z 1 * = Z 2 * = 1 and Then, there exists T ∶= T (m 1 , m 2 ) such that ∀t > T ∶ L(tZ 1 ) < L(tZ 2 ).
We finish the proof by showing how to get Lemmas D.5 and D.6.  (2). But then it must be optimal therein since Ẑ * Z * = Ẑ * Z * ≤ Ẑ * . From Theorem 1,Ẑ is the unique minimizer of (49). Thus, we have shown that Ẑ * Z =Ẑ, which contradicts the assumption onZ and completes the proof.

Proof of Lemma D.5. Clearly,Ẑ Ẑ
Proof of Lemma D.6. Define ∶= m 1 m 2 −1 > 0 and let T large enough such that e −T m 2 n(k − 1) < 1 2. We then have the following chain of inequalities for t > T The inequality in the third line used that t > T and > 0, m 2 > 0. The next inequality follows by our choice of T . Throughout, we also used both sides of the inequality x

E Proofs for Regularized CE Section 4 E.1 Proof of Theorem 2
As mentioned in Remark 4.1 the theorem is drawn from [41, Theorem 3.2] with the following three small adjustments. Since the main proof argument remains essentially unaltered, we refer the reader to [41, Sec. C] for detailed derivations. Instead here, we only overview the necessary adjustments. First, Theorem 2 holds for imbalanced classes. Technically, Zhu et al. [41] only consider balanced data. However, a close inspection of their proof shows that such a restriction is not necessary.
Second, Theorem 2 further shows that the nuclear-norm CE minimization in (7) has a unique solution. We prove this in Lemma D.1(i) in Sec. D.
Finally, Theorem 2 relaxes an assumption d > k in [41, Theorem 3.2] to d > k − 1. (In fact, Zhu et al. [41] conjecture that this relaxation is possible. We close the gap.) The assumption d > k is only used by Zhu et al. [41] to show there exists nonzero a ∈ R d such thatŴ T λ a = 0 for a stationary point (Ŵ λ ,Ĥ λ ) of (1). (This step is necessary to construct a negative curvature direction at stationary points for which ∇ Z L(Ŵ T λĤ λ ) 2 > λ; see [41, Sec. C.1].) Indeed, if d > k, then existence of a is guaranteed becauseŴ λ has k columns implying rank(Ŵ λ ) ≤ k. To relax this requirement to d > k − 1, we show in Lemma E.1 below thatŴ λ 1 k = 0. Hence, rank(Ŵ λ ) ≤ k − 1.

E.2 Proof of Proposition 1
We prove the proposition right below its statement in Sec. 4.2. The only remaining thing to show is that for R > 1 and k > 2, not all eigenvalues of the SEL matrix are same. This follows immediately from Lemma A.3 in Sec. A.2. Specifically, we show in (9), that if R > 1 and k > 2, then the maximum eigenvalue of Λ is √ R and the minimum one is 1 (thus, different).

E.3 Proof of Proposition 2
The proposition follows by combining Propisition 3 and Theorem 2. First, thanks to Theorem 2, for all λ > 0:Ŵ whereẐ λ is the solution to (7). Here, we used the fact from Equation (8) that Next, from Proposition 3 The desired follows by combining the above two displays.

E.4 Comparison to one-layer linear model
In Sec. 4.4, we compared the solution to the non-convex minimization (1), corresponding to a two-layer linear model, to the solution found by an one-layer linear model. Specifically, the one-layer linear model trains k-class linear classifier Ξ k×n by solving the following convex ridge-regularized CE: The following lemma computes the solution of this minimization.
According to the lemma above, the one-layer linear model always finds the SEL matrix: irrespective of imbalances and for any value of λ (including vanishing ones). On the other hand, by Proposition 1, we know that the end-to-end models minimizing ridge-regularized CE for a two-layer linear network correspond to the SEL matrix only if data are balanced, or there is two classes, or regularization is vanishing. Specifically, the solution is different when k > 2, R = 1 and λ > 0.
It is also worth noting the following connection between the one-and two-layer models. Thanks to the convex relaxation of Theorem 2 the end-to-end model W T H found by the twolayer model solves CE minimization with nuclear norm minimization (cf. (7)) compared to the ridge regularization in (51). Correspondingly, for vanishing regularization, the two-layer model corresponds to the "nuclear-norm SVM" in (5) compared to the vanilla SVM in (52). Notably, Theorem 1 proves that the solution to the former is alwaysẐ, i.e., the same as that of the latter.
Proof of Lemma E.2. The minimization in (51) is convex. Hence, it suffices to prove there exists α λ such that that ∇ Z L(α λẐ ) + λα λẐ = 0. Thanks to Lemma A.1(v), it suffices that ∃α λ such that λα λ = k e α λ +k−1 . It is easy to check that this equation always has a positive solution α λ > 0 since the LHS is increasing in (0, ∞), the RHS is decreasing in the same interval, and they both take values in (1, ∞). The fact that following the regularization path λ → 0 leads (in direction) to the SVM solution follows from [28]. These two combined also show that the solution to (52) isẐ.

F.1 Experiments with weight-decay
In this section, we show experiments on the UFM supporting the claim of Theorem 2: the global solution (W λ , H λ ) of ridge-regularized CE in (1), call it "λ-SELI" for convenience (with some abuse of the term SELI, as the logit matrix does not represent the simplex encoding anymore for λ > 0), satisfies (8). Moreover any first-order method that avoids strict saddles converges to that global optimum [41]. Fig. 9 investigates the above claims in a setting of (R = 10, ρ = 1 2)-STEP imbalance, k = 4 classes and n min = 1, where we ran SGD on the ridge-regularized CE with λ n = 10 −3 . We set learning rate to 1 and implement ridge-regularization as weight-decay on the parameters. We observe the following. Fig. 9b, 9c, and 9d verify convergence to λ-SELI, while Fig. 9a verifies that the (NC) property also holds. Also, the solution is clearly away from ETF geometry (see green lines in Fig. 9). This is a noteworthy difference of the behavior of learning with imbalanced data, compared to that with balanced data. With balanced data, the geometry with ridge-regularization λ > 0 is always ETF. On the contrary, the geometry for learning from imbalanced data is sensitive to λ, as discussed in Sec. 4.2. While the distance from λ-SELI is the least, the distance to SELI is smaller compared to ETF. Thus, while SELI is not the "true" characterization when training with finite ridge-regularization, it is nevertheless a significantly better approximation than the ETF. In addition, compared to the λ-SELI solution, the SELI one admits explicit closed-form expressions (see Sec. B), rather than requiring numerical solution to a nuclear-norm CE minimization. Finally, note that, up to a certain point of time during the training, the distances from SELI and λ-SELI are comparable. Interestingly, the divergence between the two distances becomes more prominent at epoch count that also corresponds to a sharp fall of the NC error-curve in Fig. 9a.

Remark F.1 (A note on λ scaling). In Equation (1), the CE loss is not normalized by the number of examples. On the other hand, in all our experiments, we normalize the CE loss by
1 n. This is why, when denoting the regularization used in experiments, we write λ n in the axis-labels of all figures.

F.2 Logit regularization and Ridge-decay
Our Proposition 2 proves that the optimal logits of CE minimization for the UFM with vanishing ridge-regularization is the SEL matrix. However, we also find in Fig. 5 that the convergence of SGD to the SEL matrix is rather slow. Motivated by this slow convergence we discuss here logit-regularized CE minimization, i.e., the solution to the following (non-convex) program: Note that when λ = 0, the global solutions of the above minimization give a logit matrix that aligns with the SEL matrixẐ. This is easy to see by noting the resemblance to the convex program in (51) and invoking Lemma E.2. Empirically, we observe that the above logit regularization helps achieve SGD convergence to solutions with SEL matrix as logits converge much faster, even without additional ridgeregularization. Specifically, for (R = 10, ρ = 1 2)-STEP imbalance, k = 4 classes and n min = 1, we run SGD on the logit-regularized CE with λ L n = 10 −3 and with zero ridge-regularization (λ = 0). We also set the learning rate to 1. Fig. 10 depicts convergence of the logit-matrix Z in the direction of the SEL matrixẐ. However, we find that this does not ensure of convergence for the individual geometries of W and H towards SELI, although their inner product W T H aligns well to the SEL matrix.
On the other hand, we also find that logit-regularized ERM on the UFM yields the SELI geometry simultaneously for logits, classifiers and embeddings when we follow a specific decaying schedule for the ridge-regularization parameter. Specifically, in the experiments shown in Fig. 11 and 12 below, we start with a large initial value λ n = 10 −2 and progressively decay λ by a factor of 10 after every few epochs. We also set a finite strength of logit-regularization λ L n = 10 −3 , although the convergence direction is not sensitive to that choice. We term this   scheduling "ridge-decay". While the exact dynamics followed by the SGD with such a scheme require further analysis, "ridge-decay" can be thought of as emulating the regularization path of ridge-regularization with λ → 0. Fig. 11 show convergence of the GD solution with the above described ridge-decay to the SELI geometry. Here, we choose k = 4 classes, with (R = 10, 100, ρ = 1 2)-STEP imbalance and n min = 1. The learning rate is again fixed to 1. In this experiment, we use GD instead of SGD since the number of examples is small. This is also useful as it shows that GD is able to drive the solution towards the SELI geometry without stochastic updates being necessary.
In summary, we make the following observations from Fig. 11. First, GD iterates favor the SELI, instead of the ETF geometry, suggesting an implicit bias towards global minimizers of the UF-SVM. Second, with logit-regularization and ridge-decay, convergence towards SELI is achieved at a faster rate than in the case of unregularized CE. Third, while Fig. 10 showed that the logit matrix converges fast in direction of the SEL matrixẐ with only logit-regularization, Fig. 11b and 11c show that ridge-decay promotes convergence of classifiers and embeddings to their respective SELI geometries as well. Finally, for completeness, we also present the NC convergence in Fig. 11a. The metric used to measure NC is as described in Sec. G.1.3.
The corresponding margins for the 4 classes are shown in Fig. 12. For examples belonging to class y, we define average margin with respect to another class c ≠ y as follows: Note that this is an average over examples from the class y since by NC property h i ≈ µ y , ∀i ∶ y i = c.
We make the following remarks regarding Fig. 12. First, as training progresses, the (average) margins are positive, thus zero training error is achieved for all classes. Second, the average margins for a class y with respect to classes c ∶ c ≠ y converge to a common value, even though their initial values differ. This can be seen from the convergence of the four different colored curves within a plot (e.g. Fig. 12a). Third, all margins for all pairs of classes converge to the same quantity, irrespective of being majority or minority classes. Note, for instance, from Fig. 12a,12b,12c, and 12d that the final value of all graphs is the same. Finally, the value of margins stagnates to a level that is governed by the strength of the logit-regularization λ L .

G Additional results on real data
This section complements Sec. 5.3 with additional experiments.

G.1.1 Implementation details
Our experiments on deep models build on the code provided by [26] 6 . We train ResNet-18 [10] and VGG-13 [29] models, on three 10-class datasets, CIFAR10, MNIST and Fashion-MNIST. Following [26], we use batch normalization in place of the dropout layers in VGG-13. For both models, we disable the biases of all the fully-connected layers, similar to the experiments on UFM. We adopt the same training strategy as [26], namely SGD on CE loss, with momentum (0.9), small weight decay (5 × 10 −4 ), and learning rate 0.1 decayed at two stages (epochs 120 and 240) by a factor of 10. We train the network on a (R, 1 2)-STEP imbalance setting. To create imbalanced data, we use the data sampler provided by Cao et al. [2] 7 . Following [26] we do not use any data augmentation. In all the experiments, we fix the first 5 classes to be majorities, and the rest as minorities. To have a fair comparison between the models with different imbalance ratios R, we sample the datasets to have n = 25250 training images in all cases. While the training set is imbalanced, when measuring test performance of a trained model we do so on a balanced test set, e.g. just like [1,2]. We measure the metrics at certain epochs, and similar to [26], we sample epochs more frequently at the start of the training as the network parameters change more quickly in the beginning.

G.1.2 Model accuracies
Consistent with the requirements of the neural collapse phenomenon by Papyan et al. [26], all models are trained well beyond zero error. Specifically, as illustrated in Fig. 2 and 6, most of the models achieve zero error around epoch 120, while training continues until epoch 350. Table 2 presents the first epochs at which each model achieves 100 percent accuracy for each value of the imbalance ratio R. For practical purposes, the minimal requirement for majority classes to be declared having achieved zero training error is set to 0.2% error. For minority classes n min ≤ 500 we set 0.00% for the same requirements.
Balanced test errors are reported in Table 3. Majority and minority errors are calculated by averaging the per-class majority and minority errors respectively. The total error is calculated

G.1.3 NC property
From the (NC) property, we expect that the embeddings collapse to their class means. In order to quantify validity of this property, we follow [26]. Specifically, we compute the within-class covariance (Σ W ) and between-class covariance (Σ B ) as, h i is the mean embedding of class c and µ G = 1 k ∑ c∈[k] µ c is their (blanaced) global mean. We can now measure NC by computing tr(Σ W Σ † B ) k. Fig. 13 illustrates how this quantity indeed decreases as training evolves. This confirms that feature embeddings converge to their class means, regardless of the imbalance ratio R.

G.1.4 Norms of classifiers / embeddings
Here, we further investigate the geometry of learned embeddings and classifiers, by focusing on their norms. In particular, we study the ratios τ h ∶= h maj 2 h minor 2 and τ w ∶= w maj 2 w minor 2 . Assuming the classifiers and embeddings follow the SELI geometry, those ratios admit explicit closed-form expressions thanks to Lemmas B.1 and B.2. To determine deviations of the measured norm-ratios τ w and τ h compared to those reference closed-form expressions, we calculate and report the following quantity: whereτ w is given by Lemma B.1 for SELI and is equal to 1 for ETF, and, τ w (c, c ′ ) = w c 2 w c ′ 2 with c being a majority and c ′ a minority class. Similarly, we compute distances for the normratios of centered mean embeddings µ c . Fig. 7 and 14 depict these metrics during training of the ResNet and VGG networks. The results confirm once more that the SELI geometry accurately captures features of the learned geometries. On the contrary, this is not the case for ETF when data are imbalanced. We observe that convergence to SELI geometry (and respective deviation from ETF) is more pronounced for the classifier weights and becomes elusive for the embeddings particularly for large imbalance ratios (R = 100.)

G.1.5 Non-alignment of classifiers and embeddings
While from previous empirical results on balanced datasets [26], we expect an alignment between the classifiers and embeddings, Lemma B.5 suggests these two geometries deviate as data becomes more imbalanced. To verify this property, we compute the angle between mean embeddings and their corresponding classifiers, and measure the deviation from the SELI geometry. Namely, let θ c = Cos(w c , h c ). Then, similar to the previous section, we compute, where c ranges over minority classes andθ is given by (18). Fig. 15 shows how this quantity evolves during training. From Fig. 8b, we know that the embeddings and classifiers of the majority classes remain aligned even for highly imbalanced data, thus we only analyze the impact of imbalance ratio on the minority classes.

G.1.6 Majority vs minority geometry
In order to better understand the individual behavior of majorities and minorities, we now compare individual quadrants of the (normalized) G W and G H matrices. Concretely, let be a partition of the normalized G W = G W G W F to (k 2) × (k 2) sub-blocks. Comparing quadrants G W maj−maj , G W maj−minor and G W minor−minor to the corresponding quadrants of the reference SELI/ETF matrixĜ W allows us to "zoom-in" the majority-majority, majority-minority and minority-minority structures. Entirely analogous calculations allow the same for the embeddings.
Classifiers Geometry. Fig. 16 confirms that both majority and minority geometries converge to SELI properly. Interestingly, we see that the minorities diverge the most from the equiangular structure of ETF geometry.
Embeddings Geometry. We find thanks to Fig. 17 that the "error" in convergence of embeddings to SELI geometry (compare to the better convergence for classifiers) shown previously in Fig. 2 and 6 is primarily due to the minority class geometries. However, an overall inspection of the subfigures shows that embeddings also tend to align better to SELI compared to ETF. This alignment property is pronounced in the case of majority geometries (see G M maj−maj ).

G.2 Capturing weight-decay with regularized UFM
In Fig. 18 we compare for R = 10 the distances of G W and G M matrices to various λ-SELI geometries for different values of regularization λ. Specifically, for the λ-SELI geometries, we obtained the reference matricesĜ λ W ,Ĝ λ M as follows. For each value of λ, we solve the nuclearnorm CE minimization in (7) to findẐ λ for k = 10 and R = 10 (to match the CIFAR10 settings). We then formĜ λ W ,Ĝ λ M as described in the first paragraph of Sec. 5 only now usingẐ λ instead of the SELIẐ. For comparison, we also plot the distances to the SELI and ETF geometries.    Figure 18: Distances of ResNet learned classifiers and mean-embeddings trained on CIFAR10 data with imbalance ratio R = 10 from the λ-SELI geometry (aka solution to (7) as defined in Theorem 2) for different values of λ, as well as, from the SELI and ETF geometries.
Note that we have experimented with a wide range of values for the regularization λ. Among those is the value 5e − 4 that matches with the choice of weight-decay parameters in the deep-net experiments. Recall also from the discussion in Sec. 4 thatẐ λ is sensitive to λ in this setting where R = 10, k = 10.
We make the following interesting observations from Fig. 18. First, note that for classifiers the minimum distance is that to SELI. The distance of the embeddings' geometry to SELI is also among the lowest ones. Specifically, despite being slightly larger than that from λ-SELI for a few values of λ, the difference is very small. This suggests that SELI is indeed a good approximation for the learned geometry even when training with finite weight-decay. Besides, there are two key advantages of the SELI over the λ-SELI geometry. First, it is unclear what the mapping ought to be (if such a mapping exists) between training-implementation choices (such as weight-decay) and λ. Second, even if such a mapping was known, the SELI geometry has the unique advantage of being expressed simply in terms of the (SVD of the) SEL matrix. In fact, as we show in Sec. B it is possible to get closed-form expressions for the norms and angles describing the geometry. This not only makes calculations much easier, but also it allows further analysis of the properties (e.g. quantifying norm-ratios as in Fig. 7).

G.3 Additional experiments for minority ratios ρ ≠ 1 2
Thus far, in our previous experiments we considered imbalanced data with minority ratio ρ = 1 2, i.e. same number of minorities and majorities. However, note that our theoretical results hold for any value of ρ. Specifically, Theorem 1 shows that the solution of the UF-SVM follows the SELI geometry irrespective of ρ. Here, we empirically study convergence to the SELI geometry for a ResNet-18 model on (R,ρ)-STEP imbalanced CIFAR10 data, for two values of minority ratio ρ = 0.3 and 0.7. These experiments complement our previous demonstrations for ρ = 0.5. Specifically, we create training set of the same size of n = 15350 in all experiments for a fair comparison. 8 All other experimental settings are as described in Section G. 1

H Implications on minority collapse
In this section, we further elaborate on how our results relate to the minority collapse phenomenon, which is defined by Fang et al. [3] as the phenomenon during which minority classifiers become completely indistinguishable. Notably, Fang et al. [3] discover its occurrence both in the UFM and in real datasets trained with deep-nets. Below, we first state their concrete findings and then we discuss how our results extend them.

Summary of findings by Fang et al. [3].
Fang et al. [3] make the following key findings.

FHLS(2)
They also find numerically that the solution to the same constrained UFM gives Cos(w minor , w ′ minor ) = 1 for any R > R 0 for some finite threshold R 0 .

FHLS(3)
Their experiments, specifically [3, Fig. 3], suggest that for fixed number of classes k, the value of the threshold R 0 increases as the constraint parameter gets relaxed and also as the ratio ρ of minority classes increases.
(a) Consistently, as R increases, the cosine similarity between minority classes increases until it reaches one.
(b) The value of R after which the cosine becomes one (i.e. minority collapse is reached) depends critically on the weight-decay. For small weight decay (∼ 5e − 4), it takes R > 1000 to reach minority collapse. It is only for larger weight decay (∼ 5e − 3) that minority collapse occurs for R ∼ 100.
Our novelties. Before discussing implications of our results for minority collapse, we highlight the following key features of our study.
• Entire geometry: We describe the entire geometry of classifiers and embeddings for both majority and minority classes (not only the geometry of minority classes.) • Finite imbalance levels: Our geometric characterizations (aka SELI geometry) hold for all finite values of the imbalance ratio R (not only asymptotically.) • Vanishing regularization: We focus on CE training with vanishing regularization. (As such, our geometry characterizations result from analyzing the UF-SVM.)

Contact points: What do our results say about minority collapse?
• For zero regularization (aka UF-SVM), there is no minority collapse for any finite value of R. Specifically, we show in Lemma B.3 that for (R, 1 2)-STEP imbalance Cos(w minor , w ′ minor ) = (R−7) R−7+2k(2+ (R+1) 2) < 1. This does not contradict Finding FHLS(2) since here we consider zero regularization; all their numerical evaluations are with finite regularization.
Put in terms of imbalance ratio, we prove that It is straightforward to check that f (λ, ρ) is increasing in ρ and decreasing in λ. Thus, we show that the minority collapse threshold R 0 (see Finding FHLS(3)) increases with the minority ratio ρ and with the inverse regularization parameter 1 λ. This finding explains the behavior reported empirically in [3, Fig. 3] for the UFM and in [3, Fig. 2,4] for real data. 9 • The angle between minority classifiers decreases monotonically with the imbalance ratio R for the UF-SVM. Specifically, it can be checked easily by direct differentiation that the formula in Lemma B.3 giving Cos(w minor , w ′ minor ) is increasing in R. This can be seen as a theoretical justification of the empirical Finding FHLS(4)(a).

I Additional related work
As discussed in Sec. 1.1, our work is inspired and is most closely related to the recent literature on Neural Collapse. In Sec. 1.1 we reviewed the most closely related of these works. A few others are referenced in Sec. I.1 below. Beyond Neural collapse, our results and analysis tools are also related to the literatures on implicit bias, matrix factorization and imbalanced deep-learning. We elaborate on these connections below.

I.1 Additional works on Neural Collapse
Beyond CE minimization, a series of recent works study and analyze the neural collapse phenomenon when training with square loss. Interestingly, Graf et al. [5], Fang et al. [3] discover and analyze neural collapse for similarity-type losses, such as the self-supervised contrastive loss, which trains only for embeddings. To the best of our knowledge, all these works restrict attention to balanced classification. Our work shows that it is possible to obtain explicit geometric characterizations in class-imbalanced settings when training with CE. Hence, it also opens the way to extending the analysis to square-loss minimization.
Potential connections of neural collapse to generalization and transferability is a less wellunderstood topic. Some initial investigations appear in the recent works [11,4,9]. Our results are not immediately conclusive about generalization. However, as mentioned in Sec. 6 our results have the potential to offer new perspectives on generalization, since they uncover different geometries (aka SELI for different R values), each leading to different generalization (worse for increasing R [1,2]).
Remark I.1 (Last-layer peeled model (LPM)). Around the same time that the UFM was proposed by Mixon et al. [24] (see also Lu and Steinerberger [21], Graf et al. [5]), the same model was independently formulated and analyzed by Fang et al. [3] under the alternative name of "last-layer peeled model (LPM)".
Remark I.2 ((NC) and (ETF) properties in [26]). The formalization of Neural collapse by Papyan et al. [26] involved four NC properties. The first property concerns the collapse of class embeddings to their corresponding means. Properties two and three concern the geometry of class-means and classifier-weights, specifically their alignment and convergence to a simplex ETF geometry. Property four is a consequence of the other three properties, hence is less important in the formalization and we do not discuss it further. Motivated by our findings, we propose and use here a regrouping/renaming of the aforementioned three properties. We refer to the first property as the (NC) property, and, to the second and third properties as the (ETF) property. We argue that this distinction is important towards a formulation that is invariant across class-imbalances, by showing that the ETF property is not invariant and replacing it with the (SELI) property. For balanced data, the latter simplifies to the ETF property.

I.2 Implicit bias
Neural collapse is intimately related to the recent literature on implicit bias, which started from a series of influential works [30,13,7,14,25]. (This connection is already recognized by the seminal work of Papyan et al. [26].) For example, [7, Theorem 7, Remark 2] concerns a bilinear non-convex SVM-type minimization that bears similarities to the UF-SVM and establishes a connection to a convex nuclear-norm minimization problem. However, the two factors in their bilinear formulation are the same (unlike the UF-SVM) and also they restrict attention to binary classification. Another very closely related work is that by Lyu and Li [22] who show that gradient descent on deep homogeneous networks converges (in direction) to a KKT point of a corresponding non-convex max-margin classifier. While their focus is again on binary classification, they briefly discuss extension to multiclass settings in their appendix. Recently, Ji et al. [12] leveraged their results and formally showed that gradient descent on (1) with zero regularization converges to a KKT point of the UF-SVM. The max-margin classifiers corresponding to multi-layer linear networks (with the UF-SVM being a special case) are nonconvex. Hence there is no guarantee that the KKT point where gradient descent converges to is a global optimum. Whether this is the case or not is investigated for various settings by Vardi et al. [33]. Specifically for linear fully-connected networks, which are of interest to us, they show that, when trained on binary data, the point of convergence is always a global optimum [33,Theorem 3.1]. Their proof uses another nice result on implicit bias by Ji and Telgarsky [15]. In fact, their results are more intimately connected to neural collapse as it can be checked that [15,Proposition 4.4] provides a direct proof that gradient descent on unregularized CE for the UFM and binary data finds embeddings and a classifier that satisfy the NC and ETF properties (irrespective of imbalance). Note here that all these works focus almost exclusively on binary settings. A salient message of our results is that rich and possibly complicated behaviors can occur in multiclass (k > 2) settings. There are several findings supporting this. For example, we show that regularization in the UFM only matters when data are multiclass and imbalanced. Similarly, it is only then that the model found by the two-layer UFM can differ from what a one-layer convex network would find. We also show empirically for the UFM that convergence rates in the absence of regularization can be heavily impacted by imbalances. Related to this, we highlight a missing piece in our analysis: we characterize the global optimum of the UF-SVM, but we do not prove, or are aware of a proof, that gradient descent converges to this global optimum. Proving or disproving this can be of great interest in its own way. On the one hand, if the conjecture holds, then our results warn that imbalance levels can severely impact convergence rates. On the other hand, if the conjecture is refuted, then this would be the simplest model to have been discovered where convergence to global optimum fails.

I.3 Matrix factorization and low-rank recovery
The connection between the study of the UFM for the purpose of neural collapse analysis and the literatures on matrix factorization and low-rank matrix recovery (see for example [36]) is uncovered and first exploited by Zhu et al. [41] and Fang et al. [3]. Thus, we refer the interested reader to those papers for a list of references and detailed discussion (specifically see Zhu et al. [41,Sec. 3.2]). Specializing this discussion to the UF-SVM that is of main interest to us, we note its close ties to the formulation of the hard-margin matrix factorization problem as studied by Srebro et al. [31]. The author formulated the problem of fitting a binary target matrix Y (ie. with entries ±1) with a low-rank matrix W T H as the minimization min W,H where S is a given subset of observed entries of Y. Despite being non-convex, they derived a convex reformulation based on duality and a corresponding procedure for finding a solution to (56) via essentially solving an SDP and an appropriate system of linear equations corresponding to the active constraints. The non-convex max-margin problem (2) that we investigate bears similarities to (56). Specifically, for an one-hot encoding and fully observed Y, (56) is essentially the binary analogue of (2). Importantly in our setting, we are able to calculate the solution to (2) in closed form, that is without requiring numerically solving an SDP. Finally, as mentioned in Sec. E.4 a byproduct of Theorem 1 is that the nuclear-norm max-margin minimization (5) has the same solution as the vanilla max-margin with Frobenius norm. Although different, somewhat related settings were frobenius-norm penalized problems give same solutions as nuclear-norm penalized ones have been studied in the low-rank representation literature, e.g. [34,27].

I.4 Class-imbalanced deep learning
The past few years have seen a surge of research activity towards substituting the vanilla CE empirical risk minimization, which leads to poor accuracy for minorities, with better alternatives that are particularly suited for training large models, e.g. [17,18,2,23,39]. Among the many solutions suggested in the recent literature, most closely related to the topic of neural collapse are [17,18]. Interestingly (as it happened chronologically before the conception of Neural collapse by Papyan et al. [26]), Kang et al. [17] and Kim and Kim [18] observed that the classifier weights found by deep-nets when trained with CE on class-imbalanced data yield larger norms for majority rather than minority classes. This empirical observation led them to propose post-hoc schemes that normalize the logits before deciding on the correct class, thus leading to better performance on the minorities. Our Lemma B.1, not only proves this behavior for the unconstrained feature model, but it also precisely quantifies the norm-ratio between minorities and majorities. Interestingly, our deep-net experiments in Fig. 7 confirm the predicted behavior. Evidently then, Lemma 3.1 offers a plausible theoretical justification of the empirical findings by Kang et al. [17], Kim and Kim [18] and also quantifies the norm ratio. It is conceivable, that this