Applied Science, Faculty of
Electrical and Computer Engineering, Department of
DSpace
UBCV
Behnia, Tina
Master of Applied Science - MASc
University of British Columbia
Machine learning has trended toward training overparameterized networks that can exactly fit the training set. In this regime, when the training data is class-imbalanced, traditional methods for mitigating imbalances are not effective and yield poor performance on minorities. Tailored to the over-parameterized setting, one successful technique to combat imbalances involves adjusting the logits during training by introducing several hyper-parameters in the cross-entropy loss. The idea behind these adjustments is rooted in the implicit bias analysis which, for linear models, explains why they successfully induce bias on the optimization path towards solutions that favor minorities. However, the impact of these adjustments is not well-understood for deep, non-linear models that simultaneously learn features from the data and fit classifiers on them. In this work, we take a step towards formalizing the impact of data imbalances and the choice of loss function when learning in over-parameterized setups. At the core of our analysis is the unconstrained features model (UFM), which recently provided partial theoretical justification for the empirical finding known as Neural-collapse. Limited to the balanced setting, Neural-collapse suggests that over-parameterized models learn features and classifiers that are arranged in a perfectly symmetric and maximally-separated geometry. Leveraging the UFM in our analysis, we analytically characterize the changes in the learned geometry as data becomes imbalanced or the loss function is modified. Our analysis characterizes the properties of the learned features and classifiers, justifying previously observed empirical findings on imbalanced training. To verify the accuracy of our theoretical predictions, we conduct experiments on benchmark networks and vision datasets. Additionally, we adopt the UFM to conduct a preliminary study on supervised contrastive loss, a recently proposed alternative to the cross-entropy. We observe that these two losses, under UFM, exhibit certain similarities. Furthermore, with a slight modification to the model, we discover that we can make the training geometry invariant to imbalances in this case. Overall, despite its simplicity, UFM uncovers certain biases of over-parameterized models at the training stage. Indeed, this simplification is not without its own limitations, which will become clear throughout our analysis.
Learning from Imbalanced Data:A Geometric Study onOver-parameterized ModelsbyTina BehniaB.Sc., Sharif University of Technology, 2021A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2023© Tina Behnia, 2023The following individuals certify that they have read, and recommend to the Faculty ofGraduate and Postdoctoral Studies for acceptance, the thesis entitled:Learning from Imbalanced Data: A Geometric Study on Over-parameterizedModelssubmitted by Tina Behnia in partial fulfillment of the requirements for the degree ofMaster of Applied Science in Electrical and Computer Engineering.Examining Committee:Christos Thrampoulidis, Assistant Professor, Department of Electrical and Computer En-gineering, UBCSupervisorPurang Abolmaesumi, Professor, Department of Electrical and Computer Engineering, UBCSupervisory Committee MemberMark Schmidt, Associate Professor, Department of Computer Science, UBCSupervisory Committee MemberiiAbstractMachine learning has trended toward training overparameterized networks that can exactlyfit the training set. In this regime, when the training data is class-imbalanced, traditionalmethods for mitigating imbalances are not effective and yield poor performance on minori-ties. Tailored to the over-parameterized setting, one successful technique to combat imbal-ances involves adjusting the logits during training by introducing several hyper-parametersin the cross-entropy loss. The idea behind these adjustments is rooted in the implicitbias analysis which, for linear models, explains why they successfully induce bias on theoptimization path towards solutions that favor minorities. However, the impact of theseadjustments is not well-understood for deep, non-linear models that simultaneously learnfeatures from the data and fit classifiers on them. In this work, we take a step towardsformalizing the impact of data imbalances and the choice of loss function when learning inover-parameterized setups.At the core of our analysis is the unconstrained features model (UFM), which recentlyprovided partial theoretical justification for the empirical finding known as Neural-collapse.Limited to the balanced setting, Neural-collapse suggests that over-parameterized modelslearn features and classifiers that are arranged in a perfectly symmetric and maximally-separated geometry. Leveraging the UFM in our analysis, we analytically characterize thechanges in the learned geometry as data becomes imbalanced or the loss function is modified.Our analysis characterizes the properties of the learned features and classifiers, justifyingpreviously observed empirical findings on imbalanced training. To verify the accuracy ofour theoretical predictions, we conduct experiments on benchmark networks and visiondatasets.Additionally, we adopt the UFM to conduct a preliminary study on supervised con-trastive loss, a recently proposed alternative to the cross-entropy. We observe that thesetwo losses, under UFM, exhibit certain similarities. Furthermore, with a slight modificationto the model, we discover that we can make the training geometry invariant to imbalances iniiithis case. Overall, despite its simplicity, UFM uncovers certain biases of over-parameterizedmodels at the training stage. Indeed, this simplification is not without its own limitations,which will become clear throughout our analysis.ivLay SummaryIn machine learning (ML), we often encounter imbalanced training sets, where only limitedinformation is available on certain minority classes. Modern models have an excessivenumber of parameters, enabling them to fully memorize the training data. This hamperstheir performance on unseen minorities. To address this issue, specialized techniques havebeen developed to favor minorities during training. However, the precise impact of thesetechniques on the training process remains unclear. In this study, we seek to demystifyhow these techniques influence the training of complex models when faced with imbalanceddata. To accomplish this, we employ a simplified proxy model that is amenable to theoreticalanalysis. We subsequently validate our theoretical insights through experiments conductedon benchmark models. Additionally, we discuss the implications of our findings and thelimitations of the proxy model in fully describing the dynamics of ML practice.vPrefaceThe work presented in this thesis is based on the following published materials,1. T. Behnia∗, G.R. Kini∗, V. Vakilian∗, and C. Thrampoulidis. On the Implicit Geom-etry of Cross-Entropy Parameterizations for Label-Imbalanced Data. In InternationalConference on Artificial Intelligence and Statistics, (pages 10815-10838). PMLR 2023,2. C. Thrampoulidis, G.R. Kini, V. Vakilian, and T. Behnia. Imbalance trouble: Revis-iting Neural-collapse Geometry. Advances in Neural Information Processing Systems,35, (pages 27225-27238), 2022,3. T. Behnia, K. Wang, and C. Thrampoulidis. On how to avoid exacerbating spu-rious correlations when models are overparameterized. International Symposium onInformation Theory (ISIT) (pages 121-126). IEEE 2022,and the recent manuscript under review below:4. G.R. Kini, V. Vakilian, T. Behnia, J. Gill, and C. Thrampoulidis. Supervised-Contrastive Loss Learns Orthogonal Frames and Batching Matters. arXiv preprintarXiv:2306.07960, 2023.All these collaborative works were conducted under the supervision of Dr. C. Thram-poulidis. Portions of the introductory material in Chapter 1 is taken from [1-4] of which Iam a (co-)author.Chapters 2, 3 and 4 cover closely-related material from [1, 2]. To provide a better pictureof the connections of these two works, Chapter 2 includes theoretical results from both [1]and [2]. Chapter 3 (resp. Chapter 4) includes relevant discussions and numerical resultsfrom [2] (resp. [1]). The experiments presented in [2] were conducted by myself, and V.Vakilian was in charge of the experiments in [1]. In terms of the theoretical results, [2] wasvideveloped by C. Thrampoulidis, G.R. Kini and by myself. The topics covered in [1] extendthe scope of the earlier work [2], and is primarily done by myself and G.R. Kini.The problem studied in Chapter 5 is inspired by [4]. Parts of the theoretical resultsin Chapter 5 are yet unpublished since they constitute very recent work by myself. Thepublished theoretical material were developed and written by G.R. Kini and I, while thenumerical experiments presented in this chapter were primarily conducted by V. Vakilianand J. Gill.I am the primary researcher and author of [3]. This work is related to the topic ofthis thesis, but not fully discussed in this manuscript. However, part of the introductorydiscussions were used in Chapter 1.viiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1 Introduction and Background . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Problem Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.1.1 Cross-entropy Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.2 Vector Scaling Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.3 Supervised Contrastive Loss . . . . . . . . . . . . . . . . . . . . . . 51.2 Learning with Imbalances: An Implicit Bias View . . . . . . . . . . . . . . 61.2.1 Prior Art: Binary Linear Classification . . . . . . . . . . . . . . . . 61.3 Neural-collapse Phenomenon and the ETF Geometry . . . . . . . . . . . . 81.3.1 Unconstrained Features Model . . . . . . . . . . . . . . . . . . . . . 91.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12viii2 Implicit Geometry of the VS Loss . . . . . . . . . . . . . . . . . . . . . . . 132.1 Special Parameterizations of the VS Loss . . . . . . . . . . . . . . . . . . . 142.2 Connections to CS-SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2.1 NC Holds at Any Global Solution . . . . . . . . . . . . . . . . . . . 162.3 CE Interpolates Simplex-encoded Labels . . . . . . . . . . . . . . . . . . . 172.3.1 The SELI Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3.2 Proof Sketch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3.3 Different Regularization on Classifiers and Embeddings . . . . . . . 212.4 Optimal Label Encoding with Cost-Sensitive Margins . . . . . . . . . . . . 222.4.1 CDT Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.4.2 LDT Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 The Imbalance Trouble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.1 ETF: A Special Case of SELI . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2 Numerical Results: Deep-nets Converge to SELI . . . . . . . . . . . . . . . 283.2.1 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2.2 Centering Heuristic for Deep-net Experiments . . . . . . . . . . . . 303.2.3 UFM: SGD Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . 303.2.4 Deep-net Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 313.3 How SELI Changes with Imbalances . . . . . . . . . . . . . . . . . . . . . . 343.3.1 Norm Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.3.2 Angles of Classifiers and Minoirty Collapse . . . . . . . . . . . . . . 363.3.3 (Non-)Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.4 On the Role of Regularization . . . . . . . . . . . . . . . . . . . . . . . . . 383.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 Engineering the Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.1.1 Centering of Embeddings . . . . . . . . . . . . . . . . . . . . . . . . 424.1.2 Optimization Behaviour . . . . . . . . . . . . . . . . . . . . . . . . . 434.2 Geometric Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2.1 Special Tunings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44ix4.2.2 Mitigating Minority Collapse . . . . . . . . . . . . . . . . . . . . . . 464.3 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.3.1 Impact of Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.3.2 Numerical Results on Generalization . . . . . . . . . . . . . . . . . 504.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525 Towards a Geometric View of Contrastive Learning . . . . . . . . . . . . 535.1 Practices in Contrastive Learning . . . . . . . . . . . . . . . . . . . . . . . 545.1.1 Modeling the SC Loss . . . . . . . . . . . . . . . . . . . . . . . . . . 555.1.2 Related Works and Overview . . . . . . . . . . . . . . . . . . . . . . 555.2 NC Holds at Local Optimal Solutions . . . . . . . . . . . . . . . . . . . . . 565.3 UFM: Landscape and Optimality Conditions . . . . . . . . . . . . . . . . . 575.3.1 Global Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.4 UFM+: Invariance to Imbalances . . . . . . . . . . . . . . . . . . . . . . . 605.5 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.5.1 Centering Heuristic: UFM vs UFM+ . . . . . . . . . . . . . . . . . 635.6 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68AppendicesA Properties of the SEL Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 74A.1 Eigen-Structure of the (δ,R)-SEL Matrix . . . . . . . . . . . . . . . . . . . 74B Properties of the SELI Geometry . . . . . . . . . . . . . . . . . . . . . . . 77B.1 Geometric Properties Induced by CDT . . . . . . . . . . . . . . . . . . . . 77B.1.1 Norms and Angles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78B.1.2 Asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81B.1.3 Centering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81B.2 Geometric Properties Induced by LDT . . . . . . . . . . . . . . . . . . . . 82B.2.1 Norms and Angles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82xB.2.2 Asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83B.2.3 Centering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83C Proofs of Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84C.1 Proof of Lemma 2.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84C.2 Proof of Theorems: Implicit Geometry of the VS Loss . . . . . . . . . . . . 86D Proofs of Chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92D.1 Properties of the SC Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92D.1.1 Gradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92D.1.2 Strict Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93D.2 Proof of Lemma 5.2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95D.3 Proof of Theorem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97D.4 Proof of Lemma 5.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101D.5 Proof of Theorem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104D.6 Proof of Proposition 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105E Additional Details on Numerical Experiments . . . . . . . . . . . . . . . 106E.1 Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106E.1.1 Additional Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106E.2 Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112E.3 Chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113xiList of Tables4.1 Asymptotic value (R→∞) of the classifier angles with LDT loss. . . . . . . 464.2 Asymptotic value (R→∞) of the classifier angles with CDT loss. . . . . . 47B.1 Asymptotic value (R→∞) of angles for the CDT loss. . . . . . . . . . . . . 81B.2 Asymptotic value (R→∞) of angles for the LDT loss. . . . . . . . . . . . . 83xiiList of Figures1.1 Simple illustration of implicit bias. . . . . . . . . . . . . . . . . . . . . . . . 71.2 The ETF geometry. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1 Illustration of the SELI geometry for the CE loss. . . . . . . . . . . . . . . . 202.2 Illustration of the SELI geometry for the CDT/LDT loss. . . . . . . . . . . 253.1 UFM trained with SGD converges to the global minimizer. . . . . . . . . . 313.2 NC property for last-layer embeddings of deep-nets with different imbalancelevels R. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3 Convergence of last-layer classifiers and embeddings of deep-nets to the SELIgeometry when trained with the CE loss. . . . . . . . . . . . . . . . . . . . 333.4 Norm ratio of the classifiers and embeddings in the SELI geometry with δ = 1k. 353.5 Angle between classifiers/embeddings in the SELI geometry with δ = 1k. . 363.6 Alignment of classifiers and embeddings in the SELI geometry with δ = 1k. 374.1 Convergence of SGD to the SELI geometry, the global optimizer of CS-SVM,for CDT/LDT loss. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2 Speed of convergence of SGD iterates to the SELI geometry for differentimbalance ratio and hyper-parameters. . . . . . . . . . . . . . . . . . . . . . 444.3 Impact of hyper-parameters on the training accuracy in deep-net experiments. 454.4 Gaussian mixture model for the generalization analysis. . . . . . . . . . . . 494.5 Balanced error of the SELI geometry in the Gaussian mixture model. . . . . 504.6 Test accuracy comparison between wCE, CDT and LDT losses. . . . . . . . 515.1 Embeddings trained with the SC loss converge to OF. . . . . . . . . . . . . 62E.1 Classifiers norm-ratio in deep-net experiments. . . . . . . . . . . . . . . . . 108xiiiE.2 Embeddings norm-ratio in deep-net experiments. . . . . . . . . . . . . . . . 108E.3 Alignment of minority classifiers and embeddings in deep-net experiments. . 109E.4 Majority vs minority geometry convergence for classifiers in deep-net exper-iments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110E.5 Majority vs minority geometry convergence for mean-embeddings in deep-netexperiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111xivList of AbbreviationsCDT Class-dependent Temperature.CE Cross-entropy.CS-SVM Cost-sensitive Support Vector Machine.ETF Equiangular Tight Frame.GD Gradient Descent.LA Logit-adjusted.LDT Label-dependent Temperature.MLP Multi-layer perceptron.NC Neural Collapse.NCC Nearest Class-center.SC Supervised-contrastive.SGD Stochastic Gradient Descent.UFM Unconstrained Features Model.VS Vector-scaling.wCE Weighted Cross-entropy.xvChapter 1Introduction and BackgroundDeep neural networks have a remarkable ability to learn high-quality representations fromraw data and make precise predictions on previously unseen samples. This has enabled manybreakthroughs addressing a wide range of practical problems that were unapproachable pre-viously, spanning various domains from vision tasks to natural language processing. Despitethese advances, our theoretical understanding of the recent progress is rather limited. Thus,in the absence of a rigorous theory, we often treat deep-nets as complex black-box modelsand we rely on a growing collection of heuristic approaches to train them efficiently andachieve desirable performance. This approach to training neural networks hides risks as itlimits our capabilities in developing reliable and efficient systems in critical areas.In particular, the modern paradigm of deep learning involves training over-parameterizedneural networks, meaning their number of trainable parameters far exceeds the size of thetraining set. Despite the fact that they can perfectly fit or interpolate the training set, theseover-parameterized models have repeatedly achieved empirical success. This contrasts withthe classical wisdom, which emphasized on regularizing the models’ capacity to control atrade-off between overfitting to the training data and achieving strong generalization on thetest set. Strikingly, over-parameterized models are trained well beyond the zero trainingerror regime to achieve the state-of-the-art performance [4, 36, 53]. On the optimization side,it is not obvious why we can train deep-nets to reach their global optima as the compositionof several layers, even without any activation function, can yield a highly non-convex andnon-linear optimization problem. On the other hand, from the generalization perspective,it is quite non-trivial that over-parameterized models can learn optimal solutions. This isdue to the fact that, in this regime, there are many solutions that perfectly interpolate thetraining data, while many of them perform poorly on the test distribution. These surprisingempirical findings have led to a surge of research activity towards developing a theory ofthe (so-called) harmless interpolation or benign overfitting [e.g., 1, 14, 29, 33].1A series of influential works [18, 32, 43] attirbute the success of over-parameterizationto the implicit bias or implicit regularization of the optimization algorithms, arguing thatgradient-based algorithms inherently favor solutions with certain properties that generalizewell. Soudry et al. [43] studied linear models trained on separable data with the cross-entropy (CE) loss. Although there are infinitely many directions that can achieve perfectclassification on separable data, they show that gradient flow converges (in direction) tothe max-margin classifier which also generalizes well. Follow-up works [19, 32], extend theimplicit bias analysis to non-linear models. However, the characterization is more obscurein this setup. Lyu and Li [32] shows that gradient descent (GD) on deep homogeneousnetworks converges (in direction) to a first-order stationary point of a corresponding max-margin classifier. The max-margin classifiers corresponding to multi-layer linear networksare non-convex. Hence there is no guarantee that the stationary point where gradientdescent converges to is a global optimum. Whether this is the case or not is investigatedfor various settings by Vardi et al. [47]. Specifically for linear fully-connected networks, thepoint of convergence is always a global optimum. However, the analysis is limited to binarysettings.Recently, Papyan et al. [38] has made remarkable new progress by empirically discoveringand formalizing the so-called Neural-collapse phenomenon. Neural-collapse describes thegeometric properties of the last-layer embeddings and classifier weights of deep-nets trainedwith the CE loss on balanced data far into the zero training-error regime. This phenomenonproduces a remarkably simple description of a particularly symmetric geometry: (i) Theembeddings of each class collapse to their class mean and (ii) The class means align with theclassifier weights while forming a simplex equiangular tight frame (ETF). The ETF geometrysignifies a symmetric structure where all the vectors have equal norms and are maximally-separated. Importantly, this simple geometry appears to be “cross-situational invariant”,as verified by extensive experiments on benchmark architectures and vision datasets [38].This discovery is intimately related to that of implicit bias. On the one hand, it is morerestrictive as it focuses only on the last-layer of the deep-nets, rather than the weights of theentire model. On the other hand, it offers a more explicit characterization that describesthe involved geometry of the weights and promises to be insensitive to architectures anddatasets [38]. A long line of follow-up works [e.g., 9–11, 13, 16, 17, 31, 35, 46, 49, 54, 56]have further investigated this phenomenon, attempting to extend this result to other lossfunctions and find theoretical insights to justify its emergence during training. Similar toPapyan et al. [38], the majority of these works focus on the balanced training setup, that is2when all the classes in the training set are represented with the same number of examples.However, in various practical settings, we only have access to imbalanced training setswhere some labels are associated to only a few examples and it is often challenging tofind models generalizing well on such labels with vanilla training techniques. In the over-parameterized regime in particular, we face more complications due to the inherent ability ofthe models to perfectly fit the training data. Specifically, it has been shown empirically thatconventional techniques for mitigating imbalances, such as weighted CE (wCE), lose theireffectiveness under over-parameterization [e.g., 6, 39, 40]. Thus, there are many suggestedalternatives [e.g., 7, 21, 23, 25, 26, 30, 34, 51] that are particularly suited for training largemodels. Many of these approaches are heuristics inspired by empirical observations. Thus,it is relevant to have a principled understanding of what deep-nets learn under imbalances.This deeper knowledge helps us gaining insights into both the strengths and limitations ofsuch heuristics in order to further improve them.In this thesis, we study deep-net training under class-imbalanced data through thelens of Neural-collapse. Our main concentration is on the popular CE loss as well as itsparameterizations, which as we will show become relevant under imbalances. We will alsodiscuss extensions of our analysis to the supervised contrastive loss [24]. In the remainingof this chapter, we formally define the problem setup and discuss the background conceptsin more details.1.1 Problem SetupWe consider the supervised classification setup with k classes involving a training set S ={(xi, yi) : i ∈ [n]} where xi ∈ Rp represents the i-th data sample and yi ∈ [k] is thecorresponding class label. We also use yi ∈ Rk to denote the one-hot label vector of samplei. We denote nc ≥ 1, c ∈ [k] as the number of examples in class c and, without loss ofgenerality, we assume examples are ordered. In other words, examples i = 1, ..., n1 havelabels yi = 1, examples i = n1 + 1, ...., n1 + n2 have labels yi = 2, and so on.We train the parameters of deep-nets by minimizing a loss function L(·) evaluated onthe training set S. It is common to consider a deep-net as a non-linear function f : Rp → Rkof the form,fθ,W(x) =W⊤hθ(x). (1.1)Here, the encoder hθ : Rp → Rd is a non-linear function mapping the input space to a3new feature-embedding space that is parameterized by the trainable variables θ. Then,W ∈ Rd×k is a linear classifier that acts on top of the embeddings hθ(x) found by theencoder, which is trained to classify the samples correctly into one of the k classes. Thefeature map hθ(·) can have different forms. For instance, in a vanilla deep-net with L layers,we can represent the feature map as hθ(x) = σ(WL−1 · · ·σ(W1x)), where θ = {Wℓ}ℓ∈[L−1],and σ(·) is a non-linear activation function.In general, we learn the parameters {θ,W} by solving an optimization program asfollows,W∗,θ∗ ∈ argminW,θL(W,θ) + λR(W,θ), (1.2)where R(·) is a regularization term on the model parameters and λ ≥ 0 is the regularizationhyper-parameter. In practice, we solve (1.2) by running iterative methods, such as stochasticgradient descent (SGD). In this work, our main focus is on the last-layer of the network,namely, the final layer classifiers W = [w1, , ...,wk] ∈ Rd×k and the final layer embeddingsH := Hθ = [h1, ...,hn] ∈ Rd×n, where hi := hθ(xi). In fact, we want to characterize theproperties of Wt, Hθt of SGD at step t >> t0, where at t0 we achieve zero error on thetraining set. We consider three options for the loss function L(·): the cross-entropy (CE)loss, the vector-scaling (VS) loss as a general parameterization of the CE loss, and thesupervised contrastive (SC) loss. We will introduce each of these loss functions next.1.1.1 Cross-entropy LossThe CE loss is one of the most widely used loss functions for classification problems and isdefined as follows,LCE(W⊤Hθ) := 1n∑i∈[n]log(1 +∑c∈[k], c ̸=yiexp(−(wyi −wc)⊤hθ(xi))). (1.3)Training neural networks with this loss function allows us to jointly learn the embeddingshθ(·) and the linear classifiers W. The CE loss in fact is a function of the logits matrixZk×n = [z1, ..., zn] := W⊤Hθ. For each sample i, CE measures how large the targetlogit Zyi,i is in relation to the other logits Zc,i, c ̸= yi. Several works [26, 34, 51] haveintroduced tunable hyper-parameters for the CE loss in order to improve the performancein the presence of data imbalances. We will discuss these adjustments next.41.1.2 Vector Scaling LossTraining vanilla CE on imbalanced datasets exhibits poor generalization on minority classesthat are represented by only a few samples in the training set. One of the many proposedalternatives is the so-called vector-scaling (VS) loss [26], which is a parameterization of theCE loss with tunable hyper-parameters. The idea behind this parameterization is rooted inthe theory of implicit bias (see Section 1.2) and is defined as follows,LVS(W⊤Hθ) := 1n∑i∈[n]ωyi log(1 +∑c ̸=yiexp(−(δyiwyi − δcwc)⊤hθ(xi)− ιyi + ιc)).(1.4)VS loss weights the contribution of each sample to the loss by scaling factors ωyi ≥ 0,and adjusts each element of the logits Zc,i with a multiplicative hyper-parameter δc > 0and additive hyper-parameters ιc > 0. As a special case, setting δc = 1, ιc = 0, recoversthe weighted CE (wCE) loss. Further setting ωc = 1 is equivalent to the CE loss. Withδc = 1 and only varying ιc, we get the logit-adjusted (LA) loss [34] that only adjusts thelogits by additive factors, while setting ιc = 0 and only varying δc gives the class-dependanttemperature (CDT) loss [51].1.1.3 Supervised Contrastive LossAfter the recent success of contrastive losses in self-supervised problems [e.g., 8, 45], su-pervised contrastive loss was introduced as an extension of the contrastive loss to the fullysupervised setting by Khosla et al. [24], and is defined as follows,LSC(θ) := 1n∑i∈[n]1nyi − 1∑j ̸=iyj=yilog(∑ℓ ̸=iexp(hθ(xi)⊤hθ(xℓ)− hθ(xi)⊤hθ(xj))). (1.5)The simple concept behind the SC loss involves pulling together the features of examplesbelonging to the same class while pushing away examples of different classes. In this ap-proach, we perform a two stage training: first we learn the embeddings by minimizingthe SC loss, and in the second stage, we train a simple classifier separately on top of thelearned embeddings. Despite its simplicity, SC loss surpasses the performance of the CEloss on standard vision classification datasets [24], while also being more robust to naturalcorruptions in the data and less sensitive to hyper-parameters. Further studies have also5emphasized the observed resilience of the SC loss and variants alike to distribution shifts,particularly in scenarios involving training with imbalanced data [12, 12, 20, 22, 28, 28, 41].These studies commonly involve training a combination of CE and SC-type losses.1.2 Learning with Imbalances: An Implicit Bias ViewIn the presence of imbalances, traditional techniques, such as training with wCE, fail underover-parameterization [e.g., 6, 39, 40]. Thus, various works [e.g., 7, 21, 23, 25, 26, 30, 34, 51]have proposed alternatives tailored to over-parameterized regime to ensure equitable per-formance across all classes. Among many heuristic proposals in the literature, one thatshowed promising performance on benchmark imbalanced datasets and attracted signifi-cant attention (perhaps also owing to its simplicity) is the LA loss [7, 34]. Compared towCE, LA loss (Equation (1.4) with δc = 1, c ∈ [k]) modifies the individual logits zi byadditive hyper-parameters that depend on the frequency of the corresponding example.While these additive adjustments were first introduced with the intention of creating largermargins for the minorities [7, 34], it was recently shown by Kini et al. [26], that trainingover-parameterized models for a large number of epochs can counter this effect (similar tocountering the effect of weights in wCE). As a remedy, VS loss uses multiplicative factors toadjust the CE logits. Inspired by the theory of implicit bias, for binary linear models, Kiniet al. [26] uncovers a favorable bias of the VS loss towards classifiers with larger margin forthe minority.1.2.1 Prior Art: Binary Linear ClassificationIn a binary setting with fixed feature map (non-trainable θ), Kini et al. [26] studies theimplicit bias of binary VS loss (1.6) and shows that in the zero-training-error regime, onlythe multiplicative factors δc determine the resulting classifier. Concretely, we state theirresult in Proposition 1.Proposition 1 (Kini et al. [26]). Consider a setting with binary labels υi ∈ {±1} and fixedfeature map hθ(·). Let hi := hθ(xi), i ∈ [n] and define the binary VS loss as follows.LVS,binary(w) := 1n∑i∈[n] ωυi log(1 + e−δυiυiwThi+ιυi ). (1.6)Then, GD with sufficiently small learning rate on the binary VS loss (1.6) converges (asymp-6y= +1y= 1Max MarginFigure 1.1: Simple illustration of implicit bias in linear models [43]. Linear modelstrained with GD on separable data converge (in direction) to the max-margin classifier(solid line). This is in spite of the fact that there are infintely many classifiers thatachieve perfect accuracy on the training set (dashed lines).totically in the number of training steps) in direction to the cost-sensitive support vectormachine (CS-SVM) classifier:argminw∥w∥2 subj. to υiδυiw⊤hi ≥ 1, i ∈ [n]. (1.7)Proposition 1 describes the impact of the hyper-parameters δ±1, in the asymptoticregime: the GD path is implicitly biased towards a classifier that assigns margins to thetwo classes with relative ratio δ−1/δ+1. As a special case, for CE loss with δ±1 = 1, (1.7)reduces to the SVM classifier [43]. This is despite the fact that on separable data, thereare infinitely many linear classifiers that can achieve 100 percent accuracy on the trainingset (see Figure 1.1). Tuning δ−1 > δ+1 if class υ = +1 is minority, the optimal classifierfavors the minority by assigning larger margin to it. This is in contrast to the additivehyper-parameters ι±1 or scaling factors ω±1 that do not have any effect on the implicit biasasymptotically. Our focus here is on the asymptotic training regime, hence onwards werestrict attention to the multiplicative hyper-parameters.Open problem: Beyond linear models. Proposition 1 is limited to a setting withfixed features. In the learned-feature setting, however, it is an open question to explicitlycharacterize the effect of the hyper-parameters on the learned solution. For instance, howdo they affect the relative margin between majorities and minorities or between minoritiesand minorities?71.3 Neural-collapse Phenomenon and the ETF GeometryIn their inspiring work, Papyan et al. [38] discovered that the overparameterized deep-netstrained with the CE loss beyond the zero training regime exhibit a common geometricpattern in their final layer. Specifically, across different image classification datasets andarchitectures, they empirically observed that, when the training set is balanced, the last layerclassifiers W and embeddings H can be characterized in terms of four simple properties(also see Figure 1.2):NC1: The within-class variations of embeddings hi tends to zero, and the embeddingscollapse to their class-means. In other words, for i : yi = c, hi → µc :=∑j:yj=chj .NC2: The class-means M = [µ1, ...,µk], centered at their global-mean, form a Sim-plex Equiangular Tight-Frame (ETF).NC3: The classifiers and the mean-embeddings align. In other words, W∥W∥F =M∥M∥F .NC4: The classifiers’ decision rule coincides with the Nearest Class-center (NCC);Given a new input x, the deep-net classifies the datapoint as argminc∈[k] ∥hθ(x)−µc∥2.In this characterization, the simplex ETF is formally defined as,Definition 1 (Simplex ETF). A set of k vectors V = [v1, · · · ,vk] ∈ Rd×k forms a simplexETF if V⊤V ∝ Ik− 1k1k1⊤k . In other words, for each pair of (i, j) ∈ [k], ∥vi∥2 = ∥vj∥2 andvTi vj∥vi∥2∥vj∥2 =−1k−1 .Put differently, when training with balanced dataset and the CE loss, modern deep-netslearn classifiers and embeddings that are arranged in a simple low-dimensional structure.Particularly, the embeddings hi align with the corresponding classifier wyi and they form aperfectly symmetric structure: they all have the same norm, and they are maximally sepa-rated from each other. On the other hand, given NC1-3, NC4 is direct to follow. Notably,this characterization is empirically shown to be cross-situationally invariant across differ-ent architectures and datasets. This finding connects to the implicit bias literature albeitfrom an empirical theory perspective. This way, they formalize the bias of large networksbeyond linear models, in a regime that both the classifiers and the feature-embeddings arejointly learned. They also highlight the fact that this striking common pattern emergesafter reaching the interpolation regime with zero training error, and it is in this regime thatwe observe improvements in generalization and robustness of the modern networks.8Figure 1.2: The ETF geometry in a setting with the number of classes k = 3.1.3.1 Unconstrained Features ModelIn order to develop a theory for the training dynamics of deep-nets, we ought to capture theinterplay between several non-linear hidden layers of the network. This makes the theoreticalanalysis of deep-networks challenging and motivates us to simplify the interactions betweenlayers. Important follow-up works [9, 11, 35] introduce the Unconstrained Features Model(UFM) to give (partial) theoretical justification of the discovery made by Papyan et al. [38].The UFM focuses on the last layer of the network and serves as a proxy model to deep-nets.This model relies on the power of over-parameterization and assumes that large deep-netsare expressive enough to (approximately) map any point in the input space to any point inthe embedding space. Hence, in this model, we assume deep-nets can learn unconstrainedfeatures and treat the last-layer embeddings as free optimization parameters. For instance,consider training the network with the CE loss,θ∗,W∗ ∈ argminθ,WLCE(W⊤Hθ) + λ(∥θ∥2F + ∥W∥2F ).Then, the UFM model is formally defined as follows,H∗,W∗ ∈ arg minH,WLCE(W⊤H) + λ(∥H∥2F + ∥W∥2F ), (1.8)where we relax the dependence of the embeddings hθ(xi) on the network parameters θ andoptimize the problem directly over H instead of θ. With this simplification, we study the9empirical patterns appearing in large deep-nets, restricting our attention to the interactionsof the only two elements that the Neural-collapse phenomena is concerned with: the last-layer classifiers and embeddings.It is also important to highlight that this optimization problem is still nonconvex. Pre-vious works [e.g., 9, 11, 17, 35, 44, 54–56] have studied the UFM problem for the CE lossshowing that with class-balanced training sets and as long as d ≥ k, all the global solutionsof (1.8) indeed satisfy the Neural-collapse properties and form a simplex ETF. Furthermore,Zhu et al. [56] proved that despite the non-convexity, (1.8) has a benign landscape: all localoptimals are global optimal, and there are no spurious saddle points. Thus, any optimiza-tion algorithm that can escape saddle points, converges to the global optimal, that is thesimplex ETF. Using UFM, the extensions of the geometry characterization to mean-squareloss [35, 46, 54] and contrastive loss [9, 11] have also been studied.While these works mainly study the balanced setup, Fang et al. [9] took a first stepin analyzing the UFM under imbalanced assumptions, and they discovered an intriguingphenomenon called minority collapse. They showed that in highly imbalanced regimes, asthe imbalance levels grow to infinity, the classifiers wc corresponding to minority classesbecome indistinguishable. They verify the emergnece of this phenomenon on both UFMand benchmark network architectures and datasets.1.4 ContributionsAs a proxy model, UFM gives a partial justification of why the symmetric ETF geometryemerges during the training of large networks on balanced data. However, when the data isimbalanced, the global solutions of UFM do not arrange as an ETF anymore. In fact, Fanget al. [9] verifies numerically, on both UFM and deep-nets, that this geometry character-ization is not invariant to class-imbalances and the symmetry breaks in this setup. Here,we ask whether we can find any common empirical patterns in imbalanced training thatcan provide insights into the challenging nature of this problem. Specifically, inspired bythe Neural-collapse analysis, we ask whether we can discover analogous characterizations inimbalanced setups. We focus on the family of CE loss functions, namely VS loss. As dis-cussed in Section 1.2, the driving force behind the design of this loss has been the theory ofimplicit bias. We aim to extend this theory to non-linear models by investigating geometryof classifiers and embeddings that are learned by different CE parameterizations.101.4.1 TerminologyThroughout this thesis, we use a slightly different terminology than the Neural-collapseliterature. Specifically, we use the term Neural-collapse (NC) particularly when referringto the collapse of the embeddings (NC1), and implicit geometry when referring to thearrangement of the last-layer classifiers W and feature-embeddings H (NC2-3 in balancedsetup). We do so to emphasize more on the geometrical properties of the learned parametersrather than NC1. More formally, by NC, we mean the following.Definition 2 (Neural-collapse (NC) property). Consider the embeddings matrix H. NCholds for H if hi = hj, ∀ i, j : yi = yj.Assuming that NC holds, the embeddings hi align with their class mean-embedding. Inother words, hi = µyi where we define the mean-embeddings matrix M as follows,Md×k = [µ1, ...,µk], µc =1nc∑i:yi=chi, (1.9)Thus, we can instead represent H with M and study the implicit geometry of W and M.For instance, in balanced setting, NC2-3 imply that W and M follow the ETF geometry,that is,Definition 3 (ETF Geometry). Classifiers and embeddings (W,M) follow the ETF geom-etry if W and M form a simplex ETF and W ∝M.1.4.2 NotationsIn this work, we use [n] to denote the set {1, 2, ..., n}. For matrixV ∈ Rm×n,Vi,j denotes its(i, j)-th entry, vj the j-th column, vi the i-th row, andV⊤ its transpose. Vj:k ∈ Rm×(k−j+1)chooses columns j, j + 1, . . . , k of V, and V⊤j:k ∈ Rn×(k−j+1) does so on V⊤. We denote∥V∥F , ∥V∥2, and, ∥V∥∗ the Frobenius, spectral, and, nuclear norms of V. V† is the Moore-Penrose pseudoinverse of the matrix. For a square matrix V, tr(V) denotes the trace of V,and diag(V) is a diagonal matrix that includes the diagonal elements of V. We use V ∝ Xwhenever the two matrices are equal up to a scalar constant. Furthermore, we use V ≽ 0to refer to positive semi-definite matrices, while V ≥ 0 denotes a matrix with non-negativeentries.For a vector v ∈ Rk, vc is the c-th entry, diag(v) ∈ Rk×k is the diagonal matrix with von its diagonal, and ∥v∥2 is its Euclidean norm. ⊙ and ⊗ denote Hadammard and Kronecker11products, respectively. We use 1m to denote an m-dimensional vector of all ones, Im forthe m-dimensional identity matrix, and we define Jm = 1m1⊤m. For vectors/matrices withall zero entries, we simply write 0, as dimensions are easily understood from context. ej isthe j-th standard basis vector, a column vector with a single non-zero entry of 1 in the j-thentry. Finally, we denote the set of positive rational numbers by Q+.1.4.3 OverviewThe organization of this thesis is as follows,1. We start by investigating the UFM, a proxy model of the deep-nets, when trainedwith VS loss on imbalanced data. In Chapter 2, we explore the implicit geometry ofthe UFM’s global solutions. We extend the geometry characterization to capture therole of imbalances and the hyper-parameters. Our analysis reveals that, regardless ofthe level of imbalance, the optimal logits interpolate (up to scaling factor) a specificencoding of the labels, which is dependant on the chosen hyper-parameters. How-ever, the properties of the optimal classifiers and embeddings depend heavily on theimbalance pattern.2. In Chapter 3, we focus specifically on understanding the role of imbalances on theoptimal solution of the UFM. We do so by concentrating on CE, as a special case ofthe VS loss. We validate our theoretical predictions from Chapter 2 through empiricalexperiments on benchmark deep-nets and vision datasets. In addition, we analyticallyformalize the impact of training with imbalanced datasets.3. Chapter 4 concentrates on the impact of the multiplicative hyper-parameters of theVS loss. We demonstrate that tuning the multiplicative factors in the loss (unlikeother hyper-parameters) provides a broad range of control over the geometry anddiscuss the implications of specific tunings of these hyper-parameters. As with theprevious chapter, we verify our analytical findings by comparing them to numericalresults obtained from deep-nets.4. Finally, in Chapter 5, we adopt the UFM to perform an analogous study of thelearned embeddings in the contrastive setting. We show that the UFM problem withthe SC loss shares some similarities with that of the CE loss. Furthermore, we studya modified version of the UFM model in this setup to reveal an implicit geometryinvariant to imbalances on the training set.12Chapter 2Implicit Geometry of the VS LossWe begin our study on over-parameterized models by investigating the UFM as a proxymodel of deep-nets. In this chapter, we consider optimizing UFM using the VS loss asthe general parameterization of the CE loss. Concentrating on the class-imbalanced sce-nario, we provide a theoretical framework for characterizing the optimal classifiersW∗ andembeddings H∗. We restate the UFM problem below for convenience.W∗,H∗ ∈ arg minW,HL(W⊤H) + λ2∥W∥2F +λ2∥H∥2F , (2.1)Our characterization is in terms of the imbalance profile and the hyper-parameters of theloss function. For simplicity, we assume that the training dataset is STEP imbalanced. Thisincludes balanced data as special case by setting R = 1.Definition 4 ((R, ρ)-STEP imbalanced data). In a (R, ρ)-STEP imbalanced setting withlabel-imbalance ratio R ≥ 1 and minority fraction ρ ∈ (0, 1), the following holds: all minority(resp. majority) classes have the same sample size nminor (resp. nmaj = Rnminor). Thereare ρk = (1− ρ)k majority and ρk minority classes. Without loss of generality, we assumeclasses {1, . . . , ρk} are majorities.We start with discussing a general formulation of the VS loss for the multi-class setting.While the analysis provided in this chapter can be extended to this general form, we choosethree specific parameterizations, including CE as the base, and build the theoretical resultsprogressively. Our results focus on the case of vanishing λ. In this regime, we show that theend-to-end model at the global solution W∗⊤H∗, interpolates a matrix that encodes thelabel information of the dataset. However, the choice of the loss function yields differentencodings. While this chapter focuses solely on the theoretical analysis of the UFM, laterin Chapters 3 and 4, we will investigate the accuracy of the derived theory on deep, over-parameterized settings.132.1 Special Parameterizations of the VS LossAs discussed in Section 1.2, Kini et al. [26] introduced the binary VS loss (1.6) as analternative to CE in imbalanced setups. Their motivation relies on the implicit bias analysisof binary linear models. While they introduce (1.4) as the extension of the binary VS lossto multi-class settings with k > 2, we can consider the more general extension below.LVS(W⊤Hθ) := 1n∑i∈[n]log(1 +∑c ̸=yiexp(−(δyi,yiwyi − δyi,cwc)⊤hθ(xi))). (2.2)It is easy to see that (1.4) is a special case of (2.2) when choosing δc,c′ := δc′ . While (1.4)adjusts the logits Zc,i = w⊤c hi by a factor δc that depends on the classifier index c, ingeneral we can choose this multiplicative factor to be dependent on both the classifier indexc and the sample label yi. In the remainder of this work, we use VS loss to denote (2.2).As we focus on the asymptotic regime, inspired by Proposition 1, we ignore the additivehyper-parameters ιc and weighting factors ωc. These two factors are shown to be ineffective(asymptotically) under over-parameterization.To have a simpler notation throughout this chapter, we build the theory progressivelyfor three special cases of the parameterization above. The same analysis indeed can beapplied for the general form of (2.2). We study L(·) for the following three loss functionsseparately in the next sections.1. Cross-entropy (CE) Loss: The common loss function defined in (1.3). This is thespecial case of the VS loss with δc,c′ = 1, ∀c, c′ ∈ [k].2. Class-dependant Temperature (CDT) Loss: Also studied in Ye et al. [51], thisloss corresponds to choosing δc,c′ := δc′ .LCDT(W⊤Hθ) := 1n∑i∈[n]log(1 +∑c ̸=yiexp(−(δyiwyi − δcwc)⊤hθ(xi))). (2.3)3. Label-dependant Temperature (LDT) Loss: Corresponding to the case δc,c′ :=δc, LDT is defined as follows,LLDT(W⊤Hθ) := 1n∑i∈[n]log(1 +∑c ̸=yiexp(−δyi(wyi −wc)⊤hθ(xi))). (2.4)14Both CDT and LDT are parameterized by a positive vector δ = [δ1, δ2, . . . , δk]⊤ ∈ Rk+of multiplicative hyper-parameters, and they reduce to CE by choosing δ = 1k. CDTassociates δ with the class index of the classifiers wc, while LDT associates the same hyper-parameters with the label of the feature vectors hi. CDT is equivalent to (1.4) (ignoringthe non-multiplicative hyper-parameters). Our initial motivation for introducing LDT isthe following observation.Lemma 2.1.1 (Binary linear model). Assume binary (k = 2) linearly separable data andtraining of linear classifiers by minimizing un-regularized LDT/CDT/binary-CE/binary-VSlosses. The LDT classification rule coincides with the rule of the binary VS loss assumingsame δ-tuning. On the other hand, minimizing CDT results in the same classification ruleas CE, irrespective of the δ-tuning.In other words, for binary linear settings CDT does not improve over CE, while LDTdoes so by reducing to the binary VS loss of Proposition 1. While Lemma 2.1.1 motivatesLDT, our results show that the intuition gained from binary linear settings can be restrictive.Indeed, we show that both LDT and CDT losses induce rich behaviors in the multi-classlearned-feature regime. We defer the proof of this lemma to Chapter C in the Appendix.It is reasonable to assume the hyper-parameters δc depend on nc the size of the class cin the training set. As we focus on the STEP-imbalanced setting (Definition 4), we let δ toalso share the same STEP structure. Namely, we choose the following structure for δ givensome δmaj, δminor > 0.∀c ∈ {1, · · · , ρk}, δc = δmaj, ∀c ∈ {ρk + 1, · · · , k}, δc = δminor. (2.5)2.2 Connections to CS-SVMSince neural-collapse is observed when training with small/vanishing regularization [38],it is reasonable to consider an unregularized version of (2.1). This is also relevant asemploying vanishing weight-decay is a common practice in over-parameterized classification[e.g., 3, 36, 52]. In this special case of λ = 0, gradient descent (with sufficiently small stepsize) on (2.1) produces iterates that diverge in norm, but converge in direction [17, 32]. Infact, it has been shown recently that GD iterates on (2.1) (with zero regularization) converge15in direction to a KKT point of the following margin maximization problem [17, 32]:W∗,H∗ ∈ arg minW,H12∥W∥2F+12∥H∥2Fsubj. to (wyi −wc)⊤hi ≥ 1, i ∈ [n], c ̸= yi, (2.6a)subj. to (δyiwyi − δcwc)⊤hi ≥ 1, i ∈ [n], c ̸= yi, (2.6b)subj. to δyi(wyi −wc)⊤hi ≥ 1, i ∈ [n], c ̸= yi, (2.6c)where (2.6a) corresponds to training UFM with the CE loss, (2.6b) corresponds to theCDT and (2.6c) to the LDT loss. Note the resemblance to the CS-SVM minimization ofProposition 1. But unlike that, the problems here are non-convex since minimization is alsoover H, the embeddings. As a result, there is no guarantee that the optimal solution isunique, or if the non-unique optimal points share any common geometric properties. Dueto this resemblance to max-margin problem (1.7), we refer to (2.6a) as SVM, and we denote(2.6b) and (2.6c) by CS-SVM.2.2.1 NC Holds at Any Global SolutionIn the subsequent sections, we will describe the global solutions of each of the problems(2.6a)-(2.6c). Here, as a warm-up, we state the follwoing lemma.Lemma 2.2.1. Consider the margin-maximization problems (2.6), and let H∗ be an optimalembedding matrix. H∗ satisfies the NC property (Definition 2).This simple lemma points that at any global solution the NC property must hold, whichis not surprising due to the symmetrical nature of the problem. Particularly, for any fixed(say optimal) W∗, the minimization over hi is: (i) separable and identical for all i : yi = cin same class c, and (ii) strongly convex. Hence, for all i : yi = c, there is a uniqueminimizer h∗i corresponding to the fixed W∗; this must be their class mean µ∗yi . However,we will see that the implicit geometry ofW∗ and H∗, that is the arrangement of the vectors{w∗c ,µ∗c}c∈[k] in the space of Rd, is not trivial. We start by the CE loss, and study thecorresponding optimal geometry next.162.3 CE Interpolates Simplex-encoded LabelsIn this section, we characterize the global minimizers of the non-convex program (2.6a),which corresponds to the UFM with vanishing regularization optmized by the CE loss.We show that they take a particularly simple form that is best described in terms of asimplex-encoding of the labels.Definition 5 (R−SEL matrix). In an (R, ρ)-STEP imbalanced setting, the correspondingsimplex-encoding label (SEL) matrix Ẑk×n is such that ∀c ∈ [k], i ∈ [n],Ẑc,i =1− 1/k, c = yi−1/k, c ̸= yi . (2.7)Further define α := nminor, and onwards let,Ẑ = VΛU⊤⊗ = VΛ[U⊤1:ρk⊗1⊤Rα U⊤(ρk+1):k⊗1⊤α], (2.8)be the compact SVD of Ẑ, where Λ ∈ R(k−1)×(k−1) is a positive diagonal matrix and U⊗ ∈Rn×(k−1), V ∈ Rk×(k−1) have orthonormal columns.This encoding matrix is parameterized by the imbalance ratio R as well as the minorityfraction ρ, and the number of classes k. We choose to drop the dependence on ρ and kfrom the name since our focus is on capturing the role of R, and k, ρ are easily understoodfrom the context. Also, we note that Ẑ has repeated columns. Specifically, column ẑi onlydepends on the class-label yi, and ẑi = ẑj if they both belong to the same class. Thus, itfollows easily that U⊗ in (2.8) shares the same pattern of repeated columns. We use U torefer to the k distinct columns of U⊗. It is also straightforward to see Ẑ⊤1k = 0, hencerank(Ẑ) = k − 1.Each column ẑi ∈ Rk of Ẑ represents a class-membership encoding of datapoint i ∈ [n]that relates to the one-hot encoding ŷi = eyi as ẑi = ŷi − 1k1k. In other words, letŶk×n = [ŷ1, · · · , ŷn] be the one-hot encoding label matrix. The two encoding matrices arerelated as follows: Ẑ = Ŷ − 1k1k1⊤n . We gather useful properties of Ẑ in Section A.1 in theAppendix. The eigen-structure of this label-encoding matrix is central to characterizing theoptimal solutions of (2.6a), which are described in Theorem 1.Theorem 1 (Implicit geometry of CE). Consider an (R, ρ)-STEP imbalance setting andassume d ≥ k − 1. Let (W∗,H∗) be any optimal solution and p∗ be the optimal cost of the17SVM problem (2.6a). Further, let Ẑ be the k×n SEL matrix with SVD factors Ẑ⊤ = VΛU⊤⊗.Then, p∗ = ∥Ẑ∥∗ = ∥H∗∥2F = ∥W∗∥2F . Moreover, the following statements characterize thegeometry of the global minimizers.(i) For the optimal logits Z∗, it holds that Z∗ :=W∗⊤H∗ = Ẑ.(ii) The Gram matrices satisfy H∗⊤H∗ = U⊗ΛU⊤⊗ and W∗⊤W∗ = VΛV⊤.(iii) For some partial orthonormal matrix R ∈ R(k−1)×d, W∗ = R⊤Λ1/2V⊤ and H∗ =R⊤Λ1/2U⊤⊗.We outline a proof sketch of the theorem in Section 2.3.2 and defer the details to SectionC.2 in the Appendix. Before providing the proof overview, we look into the statements ofthe theorem in more details.2.3.1 The SELI GeometryTheorem 1 provides an explicit characterization of the geometry of optimal embeddings andclassifiers. We first note that statement (iii) implies the collapse of the embeddings, as alsopreviously inspected in Lemma 2.2.1. Corollary 1 follows easily from the fact that U⊗ hasrepeated columns as in Ẑ.Corollary 1. The global optimizers of (2.6a) satisfy the NC property.Since NC holds, for the class-mean embeddings matrix M = [µ1, · · · ,µk], we havehi = µyi , i ∈ [n]. Beyond NC, Theorem 1 specifies the exact geometry of the solutions. Bystatement (i), at the optimal solution, the logit matrix Z =W⊤H, which is the end-to-endmodel, interpolates the label-encoding matrix Ẑ. Furthermore, this SEL matrix induces thegeometry of the optimal W∗ and H∗. Specifically, statements (i) and (ii) determine theexact arrangement of the classifier vectors wc, c ∈ [k] and embeddings hi, i ∈ [n], relativeto each other. Finally, although the global optimizer is not unique, statement (iii) ensuresthat all global optimizers are equal up to a rotation.This geometry can be fully characterized by the SEL matrix. Since at the optimalsolution, the end-to-end model interpolates this label encoding matrix, we call this geometrythe SEL-interpolation (SELI) and define it formally below.Definition 6 (R-SELI geometry). Consider the R-SEL matrix Ẑ, with SVD factorsUk×(k−1),Λ(k−1)×(k−1) and Vk×(k−1) defined as in (2.8). Let Wd×k, Hd×n, Md×k be the classifiers,18embeddings, and mean-embeddings matrices. We say W,H follow the R-SELI geometry ifthe NC property holds, and for some scalar τ , the three statements below hold (with thesame proportional factors).(i) W⊤W ∝ τVΛV⊤, (ii) M⊤M ∝ 1τUΛU⊤, (iii) W⊤M ∝ V⊤ΛU. (2.9)Here, we again note that the SELI geometry depends on the value ρ and k as well.However, to emphasize the impact of the imbalance ratio R, we omit the reference to thesetwo parameters in its name. The SELI geometry specifies the Gram matricesGW :=W⊤Wand GH := H⊤H, and the logit matrix Z = W⊤H (up to a global scaling). With thisdefinition, the corollary below is a restatement of Theorem 1.Corollary 2. The global optimizers of the SVM (2.6a) follow the R−SELI geometry.Remark 1. In constructing Ẑ in Definition 5, we see an immediate dependence on nminor,the number of samples in a minority class. However, keeping R, ρ and k fixed, the value ofnminor does not change the corresponding SELI geometry. In fact, scaling nminor by a factorof c ∈ N only changes the eigen-factors up to a constant: singular values scale by √c, Uscales by 1/√c and V remains unchanged. Thus, GW, GH and Z will only scale up by acommon constant.The key feature of this geometry is that the optimal logit matrix W∗⊤H∗ equals Ẑ (cf.Statement (i)). In other words, irrespective of the level of imbalance, the logit zi with labelyi = c is invariant across changing imbalances R and only depends on the class-label c.This also implies that at optimality all margins w⊤yihi − w⊤c hi, c ̸= yi are equal. On theother hand, although the optimal classifiers and embeddings are not unique, Statement (iii)ensures that they share the same geometry since they differ only up to a rotation.Despite these invariant properties, the particular arrangement of columns of Ẑ itselfdepends on the values of (R, ρ). As a result, the singular factors of Ẑ, determining thegeometry of embeddings and classifiers, depend implicitly on the same parameters. Here,we highlight the fact that the geometry differs for changing levels of imbalance. We illustratethis in Figure 2.1, where we depict the arrangement of the optimal W∗ and H∗ for R =1, 10, 100 given by Theorem 1. While the geometry in the balanced case of R = 1 is thesymmetric ETF geometry, the symmetry with respect to the majority and minority classesbreaks for larger values of R > 1. We will discuss this in more details later in Chapter 319R = 1 R = 10 R = 100Figure 2.1: R-SELI geometry characterizing the minimizers of the SVM (2.6a). Here,we consider number of classes k = 4 and (R, ρ = 1/2)-STEP imbalanced setting. R = 1corresponds to the ETF geometry [38]. In imbalanced settings (R > 1), the geometrydeviates from the ETF. See Chapter 3 for more discussions.where we show we can find closed-form expressions for the geometric properties of the SELIand capture the dependence on the imbalance pattern (R, ρ and k) analytically.2.3.2 Proof SketchWe begin with definingX =[W⊤H⊤] [W H]=[W⊤W W⊤HH⊤W H⊤H]∈ R(k+n)×(k+n),and relaxing problem (2.6a) as follows.q∗ = minX⪰012tr(X)(2.10)sub. to Xyi,(k+i) −Xc,(k+i) ≥ 1, ∀i ∈ [n], c ̸= yi.The key technical step is to express the dual problem of (2.10) such that it is parameterizedby the SEL matrix Ẑ:maxB∈Rn×ktr(ẐB) sub. to ∥B∥2 ≤ 1, B1k = 0, B⊙ Ẑ⊤ ≥ 0 . (2.11)20We prove that B∗ = UV⊤ is the unique maximizer of the re-parameterized dual problem in(2.11). While it is not hard to check that B∗ optimizes a relaxation of (2.11), it is far fromobvious that B∗ is unique, and even more, that it satisfies the third constraint. The keytechnical challenge here is that the third constraint acts entry-wise on B. In fact, to proceedwith the proof we need that the constraint is not active. In other words, B∗ ⊙ Ẑ⊤ > 0,or equivalently, that the sign pattern of the entries of B∗ agrees with the sign pattern ofthe transpose SEL matrix Ẑ⊤. We prove this by an explicit construction of the singularfactors U,V exploiting the structure of the SEL matrix. Once we have shown that B∗is the unique maximizer and is strictly feasible, we use the KKT conditions to show theoptimal X∗ in the primal problem (2.10) is unique and is characterized by Ẑ. To do this,we leverage that strict feasibility of B∗ implies by complementary slackness all constraintsin the primal (2.10) must be active at the optimum. The proof of the theorem completesby arguing that the relaxation (2.11) is tight when d ≥ k− 1. This allows us to connect theminimizers to the SEL matrix Ẑ. See Section C.2 in the Appendix for details.2.3.3 Different Regularization on Classifiers and EmbeddingsThus far in our analysis of the UFM, we assumed same regularization strength λ for theembeddings and classifiers; see (2.1). Here, we discuss a slight generalization allowingdifferent regularizations λW and λH for the classifiers and embeddings, respectively. Thisis motivated by previous studies of the UFM in the literature, [e.g., 56]. As we show, thismodification does not change the optimal solution modulo a relative scaling factor.Concretely, consider the following generalization of (2.1):(W∗(λW ,λH),H∗(λW ,λH)) := arg minW,HL(W⊤H) +√λWλH(12β∥W∥2F +β2∥H∥2F),where β :=√λHλWand λ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 analogousto the program (2.6a), this leads to a β-parameterized SVM as follows,(W∗β,H∗β) ∈ arg minW,H12β∥W∥2F +β2∥H∥2F sub. to (wyi −wc)⊤hi ≥ 1, i ∈ [n], c ̸= yi.(2.12)In Theorem 1, we studied the special case of the above for β = 1. The following proposition21specifies the optimal solutions for the general case of β > 0.Proposition 2. Consider β-weighted SVM (2.12).Then, we have,W∗β⊤H∗β = Ẑ, H∗β⊤H∗β =1βU⊗ΛU⊤⊗, and W∗β⊤W∗β = βVΛV⊤.This follows easily by noting that there is a one-to-one mapping between the globalsolutions (W∗β,H∗β) of (2.12) and the global solutions (W∗,H∗) of (2.6a) as (W∗,H∗) =(√βW∗, 1√βH∗β). Hence, at vanishing/small regularization, using different regularizationconstants for embeddings and classifiers only affects the geometry of global minimizers upto a scaling factor. We note that (W∗β,H∗β) follows the SELI geometry (Definition 6).We will see later that Proposition 2 is useful in Section 2.4.2 when studying the implicitgeometry of the LDT loss.2.4 Optimal Label Encoding with Cost-Sensitive MarginsWe started analyzing the CS-SVM programs (2.6) by (2.6a) (corresponding to the CE loss).In this section, we formalize how the optimal solutions change by adding the multiplicativehyper-parameters δ. As we will see, the global optimizers take a particularly similar form:the optimal logits interpolate a label-encoding matrix. However, this optimal label-encodingvaries as we change δ. We will discuss the case of CDT (2.6b) and LDT (2.6c) separately.2.4.1 CDT LossHere, we focus on the CS-SVM problem (2.6b) corresponding to the CDT loss. Similar tothe CE loss, the implicit geometry in this case is characterized in terms of a label encodingmatrix. However, this time, the encoding matrix is parameterized by the hyper-parametersδ as well as the imbalance profile. To extend Theorem 1 to the CDT loss, we define ageneralization of the SEL matrix (Definition 5) below.Definition 7 ((δ, R)-SEL matrix). For hyper-parameters δ ∈ Rk+ and (R, ρ)-STEP imbal-anced setup with k number of classes, we define the (δ, R)-SEL matrix Ẑ ∈ Rk×n as follows:22for all c ∈ [k] , i ∈ [n],Ẑc,i =δ−1yi(1− δ−2yi /∑c′∈[k] δ−2c′), c = yi−δ−1c(δ−2yi /∑c′∈[k] δ−2c′), c ̸= yi.For δ = 1k, (δ, R)-SEL reduces to Definition 5, the label encoding matrix correspondingto the CE loss. We provide some useful properties of this matrix in Section A.1 in theAppendix. Here, we note that Ẑ⊤ diag (δ)−11k = 0. Thus, rank(Ẑ) = k − 1.The SVD factors U, Λ and V of the generalized SEL matrix can be defined as in (2.8).Thus, we can extend the SELI geometry in Definition 6 for the (δ, R)-SEL matrix. Forconcreteness, we repeat the definition below.Definition 8 ((δ, R)-SELI geometry). Consider a (δ, R)-SEL matrix Ẑ, with SVD factorsU, Λ and V defined as in (2.8). Let Wd×k, Hd×n, Md×k be the classifiers, embeddings,and mean-embeddings matrices. We say W,H follow the (δ, R)-SELI geometry if the NCproperty holds, and for some scalar τ , the three statements below hold (with the same pro-portional factors).(i) W⊤W ∝ τVΛV⊤, (ii) M⊤M ∝ 1τUΛU⊤, (iii) W⊤M ∝ V⊤ΛU.The characterization of the geometry induced by CDT is related to the (δ, R)-SELmatrix in a similar fashion as Theorem 1.Theorem 2 (Implicit geometry of CDT). Suppose d ≥ k− 1 and a (R, ρ)-STEP imbalancesetting. Let (W∗,H∗) be any optimal solutions of the CS-SVM in (2.6b). (W∗,H∗) followsthe (δ, R)−SELI geometry.At a high-level, the key step in extending Theorem 1 to the case of CDT is formalizing the(δ, R)-SEL matrix as the appropriate generalization of the SEL matrix, which we presentedin Definition 7. Next, similar to Section 2.3.2, we express the dual of the CS-SVM (2.6b)in a form that, this time, involves the (δ, R)-SEL and showing that it admits an explicitsolution. The rest of the proof is similar to the case of CE loss. In Section C.2, we providethe detailed proof of Theorem 2.232.4.2 LDT LossIn this section, we provide a relatively more straightforward analysis for the LDT loss,by simply reducing the CS-SVM problem (2.6c) to the weighted version of SVM as in(2.12). Then, we can use Proposition 2 to characterize the implicit geometry of the optimalparameters. For technical details, we require R˜ = R(δminor/δmaj)2 ∈ Q in the followingargument.Specifically, consider the k-class CS-SVM problem of (2.6c) and recall that nc, c ∈ [k] isthe number of examples in class c. First, we note that by Lemma 2.2.1, NC property holdsat the optimal solutions. Given NC, it suffices to find the optimal mean-embeddings M.Thus, we can reformulate the problem as follows.(W∗,M∗) ∈ arg minW,M12∥W∥2F +12∑c∈[k]nc∥µc∥22 sub. to δc(wc −wc′)⊤µc ≥ 1, c ̸= c′.Now, let D = diag(δ) and define M˜ =MD. In other words, set µ˜c = δcµc. Applying thisre-parametrization, we have,(W∗, M˜∗) ∈ arg minW,M˜12∥W∥2F +12∑c∈[k]ncδ2c∥µ˜c∥22 sub. to (wc −wc′)⊤µ˜c ≥ 1, c ̸= c′.Let R˜ = R(δminor/δmaj)2, which is rational by assumption. Thus, there exists α ∈ N suchthat αR˜ is an integer. Now, set β2 = nminor/(αδ2minor). Then,(W∗, M˜∗) ∈ arg minW,M˜12β∥W∥2F +β2∑c∈[k]n˜c∥µ˜c∥22 sub. to (wc −wc′)⊤µ˜c ≥ 1, c ̸= c′,(2.13)where n˜c = αR˜ ∈ N if c is a majority class and n˜c = α ∈ N otherwise. Thus, we reducedthe original problem (2.6c) to the weighted SVM problem (2.12). This SVM is now overan artificial dataset with n˜c samples in class c and a different imbalance ratio R˜. Thisreduction, together with the general formalization of the (δ,R)-SEL matrix, then allows usto leverage the result in Proposition 2.Theorem 3 (Implicit geometry of LDT). Suppose d ≥ k− 1 and a (R, ρ)-STEP imbalancesetting. Let (W∗,H∗) be any optimal solutions of the CS-SVM in (2.6c). Define R˜ :=24CE: δc,c′ = 1 CDT: δc,c′ =√nc′ LDT: δc,c′ =√ncFigure 2.2: SELI geometry describing the structure of the CS-SVM minimizers (2.6)for different parameterizations of the VS loss (2.2). See Section 2.3 for CE, Section2.4.1 for CDT and Section 2.4.2 for LDT loss. Here, we consider number of classesk = 4 and (R = 10, ρ = 1/2)-STEP imbalanced setting. We choose δc =√nc for CDTand LDT. See Section 4.2.1 for more discussion.R(δminorδmaj)2 ∈ Q and let Dn×n be a diagonal matrix that Di,i = δyi. The optimal solutionsare such that (W∗,H∗D) follows the (1k, R˜)−SELI geometry.2.4.3 DiscussionAs indicated by Theorems 2 and 3, similar to the CE loss, the optimal logit z∗i = W∗⊤h∗iwhen trained by CDT or LDT, interpolates a vector ẑi that encodes the class-membershipof sample i. Specifically, the optimal logits in each case can be summarized as follows,CE: z∗i = ŷi −1k1k,CDT: z∗i = diag(δ−1)(ŷi −δ−2yi∑c∈[k] δ−2c1k),LDT: z∗i =1δyi(ŷi − 1k1k),where recall that ŷi represents the one-hot label-encoding of sample i. These label-encodingsremain unaffected by the imbalance ratio R. However, choosing different hyperparametervalues δ leads to distinct encodings. Consequently, for models trained with CDT/LDT, wecan adjust the margin between classes by modifying δ. This is in contrast to the case ofCE where all the margins are equal.25While the label-encoding is independent of the imbalance ratio R, the pattern of theoptimal SEL matrix Ẑ, and consequently its SVD factors, varies as R increases. Thus,different values of R yield different optimal geometries for the classifiersW∗ and embeddingsH∗. As with the the CE loss, the theorems in this section imply that the (W∗,H∗),although not unique, share the same geometric properties, i.e., same relative norms andangles. We will see in Chapter 4 how the hyper-parameters δ change the optimal geometry.We will derive the dependence of the geometry to the imbalance ratio and hyper-parametersexplicitly. Here, we refer the reader to Figure 2.2, where we plot the optimal solution ofCS-SVM for CDT and LDT for a special choice of the hyper-parameters when the trainingsetup is imbalanced (R = 10). Comparing with that of CE, the optimal geometries can besubstantially different.Finally we note that, scaling δ by αδ only changes the encoding matrix by a globalconstant 1/α. This does not change the corresponding SELI geometry, as our geometrycharacterization is valid up to a constant.2.5 SummaryIn this chapter, we found the global optimizers of the UFM problem (2.1) for three specialcases of the VS loss: (i) CE, (ii) CDT, and (iii) LDT loss. Our characterization of theoptimal solutions considers training with vanishing regularization λ. Although the problemis non-convex and the optimal classifiers and embeddings are not unique, we show that allthe global solutions are equal up to a rotation, and share the same geometry. In all thesecases, (W∗,H∗) follows the same rule: the optimal logits Z∗ =W∗⊤H∗ interpolate a labelencoding matrix whose SVD factors describeW∗ andH∗. However, depending on the valueof the hyper-parameters, the label-encoding matrix and the corresponding margin betweenclasses differ. Furthermore, the pattern of the encoding matrix, and thus the SVD factors,depend on the imbalance level. As a result, the global solutions depend heavily on theproblem setup (see Figures 2.1 and 2.2). We will discuss the impact of the imbalance leveland the hyper-parameters in Chapters 3 and 4 respectively.26Chapter 3The Imbalance TroubleIn Chapter 2, we used the UFM to characterize the optimal arrangement of the classi-fiers and embeddings, when training on imbalanced data and with different tunings of thehyper-parameters in the VS loss (2.2). We specified the global solutions of the UFM withvanishing regularization. This global optimizers can be expressed in terms of an appropri-ate SEL matrix (Definition 7), which encodes the label information of the samples. Wecalled the corresponding implicit geometry SELI (Definition 8), since the end-to-end modelinterpolates the SEL matrix when optimal.In this chapter, we focus on formalizing the impact of the imbalance ratio R on thelearned classifiers and embeddings. To decouple the interactions of R and the hyper-parameters δ in the loss function, we consider δ to be fixed in this chapter. Particularly,we choose δ = 1k, and study the CE loss. In the balanced setup, UFM optimizers providea relatively accurate prediction for the empirical observations on the learned last-layer em-beddings and classifiers of deep-nets [9, 35]. In Section 3.2, we begin with comparing theUFM solutions, characterized by Theorem 1, with what deep-nets (asymptotically) learnin the zero training-error regime under imbalanced training data. Later in Section 3.3, weformalize the impact of R on the geometry analytically. Before moving on to these topics,as a warm-up, we verify that the previously discovered ETF is indeed a special case of theSELI.3.1 ETF: A Special Case of SELIPapyan et al. [38] discovers ETF as the invariant (across network architecture and dataset)implicit geometry learned by deep-nets when trained on balanced data. Here, we verify thatTheorem 1 recovers the ETF geometry in this case. In fact, we show a more general result:SELI reduces to the ETF when the data is balanced (R = 1) or when the data is binary27(k = 2).Corollary 3 (R = 1 or k = 2). Assume balanced data (R = 1) or binary classification (k =2). Then, any optimal solution of (2.6a) (W∗,H∗) follows the ETF geometry (Definition1). Namely, let M∗ be the optimal mean-embeddings. Then,W∗ =M∗, and M∗⊤M∗ =W∗⊤W∗ = Ik − 1k1k1⊤k .We can see this directly from the SVD characterization of the SEL matrix (see SectionA.1 in the Appendix). Thus, when data is balanced or binary: (i) the norms of the classifiersand of the embeddings are all equal; (ii) the angles between any two classifiers or any twoembeddings are all equal to −1/k(k−1)/k = − 1k−1 ; and (iii) the set of classifiers and the set ofembeddings are aligned in the sense that hi = wyi .Based on our discussion in the previous chapter, recall that in balanced setting, theoptimal solution of (2.6a) is in fact (δ = 1k, R = 1)-SELI. Although in this special case, werecover the symmetric ETF geometry, this is not the case for general imbalance ratio andnumber of classes; see Figure 2.1.3.2 Numerical Results: Deep-nets Converge to SELIIn this section, we investigate the validity of UFM analysis in Theorem 1 in imbalancedsetups. Recall that Theorem 1 specifies the global solutions of the UFM (2.1) with zeroregularization. Since UFM is a non-convex model, we first examine whether we can reachthe global solutions by optimizing it through SGD. Next, we will move to the more practicaldeep-net setting, where we track the convergence of the last-layer classifiers and embeddingsto the expected geometry of Theorem 1. For concreteness, in all the experiments, weconsider equal number of minorities and majorities by choosing ρ = 1/2. We train thenetworks on (R, ρ = 1/2)-STEP imbalanced training sets, with varying imbalance ratio R.We measure the convergence to both (δ = 1k, R)-SELI, the optimal UFM geometry, andto (δ = 1k, R = 1)-SELI, which is the ETF previously predicted by Papyan et al. [38]. Westart by discussing the metrics used in our experiments.283.2.1 MetricsLetWt and Ht be the last-layer classifiers and embeddings at training epoch t. To measurethe convergence at each epoch, we compare the logits Zt :=W⊤t Ht, and the Gram matricesGWt := W⊤t Wt, GHt := H⊤t Ht, with the reference geometry. In experiments where nis large, computing GHt is computationally expensive. In this case, since we expect NCto hold at the end of the training, we measure the convergence of the embeddings by twometrics: (i) we capture the degree of collapse of the embeddings, and (ii) we compare themean-embeddings Gram matrix GMt :=M⊤t Mt to the reference geometry. For measuringNC, we follow Papyan et al. [38]. Specifically, we compute the within-class covariance,ΣW ∈ Rd×d, and between-class covariance, ΣB ∈ Rd×d, asΣW =1n∑i∈[n](hi − µyi)(hi − µyi)⊤, ΣB =1k∑c∈[k](µc − µG)(µc − µG)⊤,where µG =1k∑c∈[k] µc is the global mean ofM, and recall that µc =1nc∑i : yi∈[c] hi is themean embedding of class c. We can now measure NC by computing:dNC =1ktr(ΣWΣ†B) (3.1)To compare the Gram matrices, we compute the Frobenius distance of the (normalized)empirical variables to their theoretical counterparts. More specifically, define A = A∥A∥F tobe the normalized version of matrix A. Further, let Ẑ be the reference encoding matrix(ETF or SELI) and U, V and Λ be the SVD factors as defined in (2.8). Also, define G˜ :=Ik − 1k1k1⊤k . We evaluate the convergence of classifiers, embeddings and logits separately,as follows.Classifiers: dW := ∥GW − ĜW∥F , ĜW = VΛV⊤, (3.2a)Embeddings: dM := ∥GM − ĜM∥F , ĜM = UΛU⊤, (3.2b)Logits: dZ := ∥W⊤M− G˜∥F . (3.2c)When comparing to the ETF geometry, ĜW = ĜM = G˜. Also we note that when NC(approximately) holds, dZ is analogous to measuring ∥W⊤H− Ẑ∥F .293.2.2 Centering Heuristic for Deep-net ExperimentsIn the deep-net experiments in Section 3.2.4, prior to measuring the embeddings’ conver-gence, we employ an additional centering of the class meansM with their (balanced) globalmean. Specifically, to measure the distance dM, we use the centered M defined as follows.M = [µ1,µ2, ...,µk] ∈ Rd×k, µc := µc − µG, µG =1k∑c∈[k]µc.So, at each epoch, we compare, after normalization,GM =M⊤M to ĜM. The discrepancybetween the UFM solutions being already centered, while deep-net embeddings requirecentering before computation of the geometric measures is a common denominator in allprevious works on the UFM, [e.g., 9, 11, 13, 17, 31, 35, 54, 56].Here, the chosen centering µG is in general different (and the same only when classesare balanced) from the global centering µ′G :=1n∑i∈[n] hi used by Papyan et al. [38]. Ourchoice of the former is motivated by the fact that the SELI geometry (as predicted by theUFM) satisfies µG = 0, but not always µ′G = 0.To see this, first recall that H∗⊤H∗ = UΛU⊤. Second, check that Ẑω = 0 whereωi = 1/nyi , i ∈ [n]. Thus, U⊤ω = 0. Combining these two, it follows that H∗ω = 0. Now,recall that the NC property also holds at the optimal point. Then, we have,0 =∑i∈[n]1nyih∗i =∑c∈[k]1nc∑i : yi=ch∗i =∑c∈[k]µ∗c . (3.3)Therefore, in the UFM, the optimal class means are always centered around zero. However,in deep-nets, there might be an explicit constraint on the learned last-layer embeddings dueto the presence of activation functions such as ReLU. In such cases, even under high over-parameterization, we cannot consider the learned embeddings to be fully unconstrained.This centering heuristic has been used in the literature to account for such kind of discrep-ancies in the model. We note that the theoretical model does not fully explain the choiceof the centering. We will discuss more on this issue in Chapter 5.3.2.3 UFM: SGD SolutionsHere, we investigate whether the solutions found by SGD are consistent with the predictionof Theorem 1 about the global minimizers of the UFM. Specifically, we fix the number ofclasses k = 4 and, for each R, we select the sample size nminor for minorities so that the30101 102 103 104 10510 1100Epochs∥GWt − ĜW∥FDistancetoSELI/ETF101 102 103 104 10510 1100Epochs∥GHt − ĜH∥F101 102 103 104 10510 1100 R=1R=2R=10Epochs∥Zt − Ẑ∥FFigure 3.1: UFM trained with SGD with imbalance ratio R and minority fraction ρ = 1/2.SGD iterates converge to the SELI (solid) while stay far from the ETF (dashed).total number of samples n =((R + 1)/2)knminor is ≈ 400. The weights of the UFM areoptimized using SGD with constant learning rate 0.4, batch size 4 and no weight decay. Wetrain for 105 epochs, much beyond zero training error and plot the distance to SELI andETF geometries for classifiers, embeddings and logits over time by computing dWt , dZt ,dHt . Since the number of samples n is not large in these experiments, instead of dMt , wedirectly compute dHt , the distance of H⊤t Ht to the reference quantity. Figure 3.1 illustratesthe convergence for three values of R = 1, 10, 100 to both R-SELI (solid lines) and ETF(dashed lines). As shown in the figure, SGD iterates favor SELI over the ETF geometry.As a matter of fact, the distance to SELI is decreasing with epochs, while the distance toETF flattens, suggesting an implicit bias of SGD towards the global minimizers. However,we note that as we increase the imbalance ratio R, the metrics decrease with a worse rateand the convergence to SELI becomes much slower.3.2.4 Deep-net ExperimentsIn this section, we turn our attention to deep-nets, and we inspect the convergence of thelast-layer embeddings and classifiers to the proposed SELI geometry by Theorem 1. Wetrain two deep architectures, ResNet18 [15] and VGG13 [42] on MNIST, Fashion-MNISTand CIFAR10 datasets. Since the original datasets are balanced, for each experiment, wesample from the datasets to create a STEP imbalanced setup. We keep the size of thetraining set n = 25250 across all different imbalance ratios R = 1, 5, 10, 100. For thetraining setup, we follow the same training strategy as in Papyan et al. [38]. Specifically,the loss is optimized by SGD with batch size of 128, over 350 epochs with small weight3110 310 210 1100101102 R=1R=5R=10R=1000 50 100 150 200 250 300 35010 310 210 11001011020 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350EpochsEpochsEpochsResNetVGGNCproperty(dNC)CIFAR10 MNIST Fashion-MNISTFigure 3.2: NC property for last-layer embeddings of deep-nets across epochs with differentimbalance levels R.decay λ = 10−5 and momentum 0.9. The initial learning rate is set to 0.1 and decreased bya factor of 10 at epochs 120 and 240. For ResNet training on MNIST, we choose smallerinitial learning rate 0.05 which we empirically find that it interpolates data much faster.To evaluate the learned geometries, as discussed in Section 3.2.1, we measure the degreeof collapse by dNC and we track the classifiers, embeddings, and logits by computing dWt ,dMt and dZt over training. Recall also that following Papyan et al. [38], we first perform aglobal centering on the mean-embeddings (see Section 3.2.2). To further emphasize on thetraining regime, we mark the epoch at which the model reaches zero training error (underall imbalance ratios) by a vertical dashed line in each plot.We start by the NC measure in Figure 3.2. The within-class variation of embeddingskeeps decreasing as the training evolves. After reaching the zero training-error, the rate ofcollapse speeds up and dNC gets closer to zero. This phenomenon emerges with the samespeed regardless of the imbalance ratio R.The convergence to SELI and ETF for the classifiers, (centered) mean-embeddings, andlogits are illustrated in Figure 3.3. We note that in all plots, the distance to the (respective)SELI geometry decreases as training evolves. Also, convergence to SELI is consistentlybetter compared to the ETF geometry. However, convergence slows down for increasingimbalance level (see R = 100). This is consistent with our observation in Figure 3.1 onthe UFM. Additionally, compared to classifiers, embeddings exhibit worse convergence. Formore comparisons with the theoretical prediction, see Section E.1.1 in the Appendix.320 50 100 150 200 250 300 3500.10.20.30.40.50.60.70.80 Train Error∥GWt − ĜW∥FResNet+CIFAR100 50 100 150 200 250 300 3500.20.40.60.81.01.2∥GMt − ĜM∥F0 50 100 150 200 250 300 3500.20.40.60.81.01.2R=1R=5R=10R=100∥Zt − Ẑ∥F0 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80 Train ErrorResNet+MNIST0 50 100 150 200 250 300 3500.20.40.60.81.01.20 50 100 150 200 250 300 3500.10.20.30.40.50.60.70.80.9R=1R=5R=10R=1000 50 100 150 200 250 300 3500.10.20.30.40.50.60.70.80.90 Train ErrorResNet+FMNIST0 50 100 150 200 250 300 3500.20.40.60.81.01.21.40 50 100 150 200 250 300 3500.20.40.60.81.01.2 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.20.40.60.81.0 0 Train ErrorVGG+CIFAR100 50 100 150 200 250 300 3500.40.60.81.01.20 50 100 150 200 250 300 3500.20.40.60.81.01.21.4 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.20.40.60.81.0 0 Train ErrorVGG+MNIST0 50 100 150 200 250 300 3500.20.40.60.81.01.21.40 50 100 150 200 250 300 3500.20.40.60.81.01.2R=1R=5R=10R=1000 50 100 150 200 250 300 3500.20.30.40.50.60.70.80.9 0 Train ErrorEpochVGG+FMNIST0 50 100 150 200 250 300 3500.40.60.81.01.21.4Epoch0 50 100 150 200 250 300 3500.20.40.60.81.01.2 R=1R=5R=10R=100EpochFigure 3.3: Convergence of learned classifiers, embeddings and logits to the SELI (solid) vsETF (dashed) geometries; models trained by CE loss far beyond the zero training error onSTEP-Imbalanced datasets for different imbalance ratios R. See Section 3.2.4 for details.333.3 How SELI Changes with ImbalancesAs briefly discussed earlier, the SELI geometry captures all the geometric properties of(W,H) by characterizing the Gram matrices GW =W⊤W and GH = H⊤H and the logitmatrix Z =W⊤H. Specifically, the diagonals of the two Gram matrices specify the normsof the classifiers and of the embeddings. These, together with their off-diagonal entries,further specify the angles between different classifiers and between different embeddings.Finally, the norms together with the entries of the logit matrix determine the angles betweenthe two sets of {wc}c∈[k] and {hi}i∈[n]. Thus, they specify the degree of alignment betweenthe two sets of vectors.This description is in terms of the SVD factors of the corresponding SEL matrix. Forthe STEP-imbalanced setup, it is in fact possible to find an explicit characterizations ofthe SVD factors in terms of the problem setup, i.e., the number of classes k and imbalanceprofile (R, ρ). We provide these characterizations in Section A.1 in the Appendix. Notably,this allows us to obtain explicit closed-form formulas for the norms, angles and alignmentof the SELI geometry. For k > 3 and R > 1, the SELI geometry can significantly differfrom the ETF depending on the value of R and k. Using this framework, we discuss thedependence of the SELI geometry on the imbalance ratio in more details. We again focuson the case of equal number of minorities and majorities (ρ = 1/2) since the setting is ofsufficient interest to convey the main messages. Extension to the general case can be done ina similar fashion. In the discussions below, we assume (W,H) follow the (δ = 1k, R)-SELIgeometry. We use wmaj when referring to any majority classifier wc, c ∈ {1, · · · , k/2}, andwminor for any minority classifier wc, c ∈ {k/2 + 1, · · · , k}. Similarly, hmaj denotes any hjwith j ∈ {i ∈ [n] : yi = 1, · · · , k/2} and hminor denotes any hj with j ∈ {i ∈ [n] : yi =k/2 + 1, · · · , k}. We defer the proofs to Section B.1 in the Appendix.3.3.1 Norm RatioLemma 3.3.1 gives a formula for the ratio of majority and minority norms for the classifiersand embeddings.Lemma 3.3.1 (Norm ratios). The following statements are true about the norms of theclassifiers and embeddings.34100 101 1021.01.52.02.53.0100 101 1020.30.40.50.60.70.80.91.0k=2k=4k=10k=20∥wmaj∥2/∥wminor∥2 ∥hmaj∥2/∥hminor∥2R RFigure 3.4: Relative norms of the classifiers and embeddings in the SELI geometry varywith the number of classes k and the imbalance ratio R. The minorities fraction is setto ρ = 1/2.(i) The classifier/embeddings norms across all majority/minority classes are equal.∀c, c′ ∈ {1, . . . , k/2} , ∥wc∥2 = ∥wc′∥2, ∥hc∥2 = ∥hc′∥2,∀c, c′ ∈ {k/2 + 1, . . . , k} , ∥wc∥2 =: ∥wc′∥2, ∥hc∥2 = ∥hc′∥.(ii) The majority-minority norm ratio of the classifiers and embeddings follows,∥wmaj∥22∥wminor∥22=(1− 2k )√R+√(R+1)/2k(1− 2k ) +√(R+1)/2kand∥hmaj∥22∥hminor∥22=1√R(1− 2k ) + 1k√(R+1)/2(1− 2k ) + 1k√(R+1)/2.Thus, ∥wmaj∥2 ≥ ∥wminor∥2 and ∥hmaj∥2 ≤ ∥hminor∥2, with equalities if and only ifR = 1 or k = 2.We visulaize the statement of Lemma 3.3.1 in Figure 3.4 for k = 2, 4, 10, 20 and acrossdifferent values of the imbalance ratio R. Unless R = 1 or k = 2, the geometry differs fromthe ETF geometry, since the majority classifiers have strictly larger norms than minoritiesand the majority embeddings are smaller than the minoirties. The fact that CE learnsclassifiers of larger norm for majorities ∥wmaj∥2 ≥ ∥wminor∥2, has been empirically observedin the deep imbalanced-learning literature, e.g., by Kang et al. [21], Kim and Kim [25].Lemma 3.3.1, not only provides a theoretical justification for this observation, but it alsoprecisely quantifies the ratio.350.50.40.30.20.10.0100 102 1040.50.40.30.20.10.0Rcos(wmaj,w′ maj)cos(hmaj,h′ maj)Majority Angles0.250.000.250.500.751.00100 102 1041.00.80.60.40.20.0Rcos(wminor,w′ minor)cos(hminor,h′ minor)Minority Angles1.00.80.60.40.20.0100 102 1041.00.80.60.40.20.0k=2k=4k=10k=20k=2k=4k=10k=20Rcos(wmaj,wminor)cos(hmaj,hminor)Majority-Minority AnglesFigure 3.5: Cosine of angle between each pair of majority/minority classi-fier/embeddings vector in (δ = 1k, R)-SELI geometry. If k > 2 or R > 1 the geometrydeviates from the ETF geometry (dashed).3.3.2 Angles of Classifiers and Minoirty CollapseThe following lemma characterizes how the classifier vectors are arranged in the space.Lemma 3.3.2 (Angles of classifiers). Let (wmaj,w′maj)/(wminor,w′minor) be two classifiervectors corresponding to two majority/minority classes. Then,Cos(wmaj,w′maj) =−2√R+√(R+ 1)/2(k − 2)√R+√(R+ 1)/2Cos(wminor,w′minor) =R− 7R− 7 + 2k(2 +√(R+ 1)/2) . (3.4)It is easy to see that both these formulas evaluate to −1/(k − 1) for R = 1, which is aunique feature of ETF. As also visualized in Figure 3.5, with increasing imbalance ratio, theangle between majority classifiers is monotonically increasing, while the minority classifierskeep getting closer. For reference, we mark the value of −1/(k − 1) by dashed lines. Therate of change is more drastic for minorities. In both cases, the rate of change across R ismore pronounced for smaller k. From this characterization, it is also easy to see minoritycollapse [9] occurs in the asymptotic regime.36100 101 1020.9880.9900.9920.9940.9960.9981.000100 101 1020.650.700.750.800.850.900.951.00k=2k=4k=10k=20cos(wmaj,hmaj) cos(wminor,hminor)R RFigure 3.6: Alignment of embeddings hi with the corresponding classifier wyi in the(δ = 1k, R)-SELI geometryMinority CollapseWhile we focus on understanding the geometry at finite values of R, it is possible to evaluatelimits for our formulas giving asymptotic characterizations as R→∞. As an example, from(3.4) we can see that the angle between the minority classifiers collapses to zero in thatlimit. This phenomenon is called “minority collapse” [9]. Fang et al. [9] finds numericallythat for the solutions to the regularized UFM, the minority classes fully align when R > R0for a finite threshold R0. They report that R0 increases as the regularization is driven tozero. They also observe a similar behavior on deep-nets trained on imbalanced datasets.Here, we recover it as a special case of Theorem 1 corresponding to training with vanishingregularization. Note also that the rate at which the minority angles collapse is rather slow;see Figure 3.5.3.3.3 (Non-)AlignmentRecall that one of the main properties of the ETF geometry was that the embeddings hialign with the classifier wyi . We can similarly derive the degree of alignment in the SELIgeometry in closed-form for different values of R. We defer the characterization to LemmaB.1.3 in Section B.1. Here, we refer to Figure 3.6, where we plot the cosine between anymajority/minority classifier and corresponding embeddings belonging to the same class. Fork = 2 and R = 1 the cosines are equal to one indicating that classifiers and embeddings alignfor both majorities and minorities. This is consistent with the ETF geometry. On the otherhand, the alignment property breaks when k > 2 and R > 1. The effect is more drastic37for the minorities, while for majorities the alignment is approximately preserved (note they-axis scale is different in the two plots). Interestingly, alignment is in fact favored for largernumber of classes, but deteriorates with increasing R consistently for all values of k.3.4 On the Role of RegularizationIn Chapter 2, we characterized the minimizers of (2.1) with no regularization (λ = 0). Inour experiments we used a small, but non-zero, regularization. While we do not focus onthe role of regularization in this thesis, we briefly discuss relevant results in the imbalancedregime [44]. To make the dependence on λ explicit, let W∗λ,H∗λ be the optimal solutions ofthe UFM problem (2.1) with regularization parameter λ > 0. Our discussion below relieson a result from Zhu et al. [56]: the following nuclear-norm-regularized loss minimizationgives a tight convex relaxation of the non-convex problem (2.1).Z∗λ ∈ argminZL(Z) + λ∥Z∥∗ (3.5)Zhu et al. [56] studies the convex program (3.5) in the balanced case, proving that, regard-less of the value of λ, the optimal solution is uniquely ETF. However, when the data isimbalanced the regularization impacts the optimal solution [44]. Specifically,1. In an imbalanced setup, for all λ > 0, Z∗λ differs from the SEL matrix. Furthermore,there is no known explicit characterization of Z∗λ for non-zero regularization.2. When λ > 0, the non-convex problem (2.1) has a benign landscape. In other words,all saddle points are strict, and there are no spurious local solutions. Thus, anyoptimization method that can escape the saddle points, such as SGD, will converge tothe global solution. Furthermore, all optimal solutions (W∗λ,H∗λ) can be characterizedby the SVD factors of the corresponding convex relaxation solution Z∗λ.3. As λ→ 0, the optimal logits in (2.1) converge in direction to the SEL matrix. Specif-ically, it holds that limλ→0W∗λ⊤H∗λ/(∥W∗λ∥2F /2+∥H∗λ∥2F /2) = Ẑ/∥Ẑ∥∗.4. Finally, it can be numerically verified that convergence of W∗λ⊤H∗λ to Z∗λ gets slowerwith increasing imbalance ratio R.Put together: the tight convex relaxation (3.5) specifies the optimal geometry of the classi-fiers and embeddings for any value of the regularization. For balanced data, the solution is38always the same up to a global scaling. However, for imbalanced data, the solution changeswith λ and only in the limit of λ → 0 does Z∗λ align with the SEL matrix, the optimalsolution of the SVM (2.6a). This might be another explanation for why the prediction indeep-net experiments of Section 3.2.4 is less accurate for high imbalance level R. For moredetails, see [44, Section 4].3.5 SummaryIn this chapter, we focused on the implicit geometry learned by the CE loss to formalize thedependence of the geometry on the imbalance level R. We investigated the accuracy of theUFM predictions on the deep-nets. We observed slower converegence in highly imbalancedregimes both for unregularized UFM and regularized deep-nets.In the second part of this chapter, we formulated different geometric properties of theclassifiers and embeddings following the SELI geometry, and described how the learnedparameters deviate from the ETF geometry when the training set is imbalanced. Notably,in the (R > 1)-SELI geometry, the majority classifiers are more prominent, with largernorms and more separation from other classes. This is in contrast to the minoirty classifiersthat monotically get smaller and in the limit of R → ∞ become indistinguishable. As aresult, the final model becomes more biased towards the majority classes as R increases. Inthe next chapter, we explore the impact of the hyper-parameters δ that adjust the logits inthe CE loss.39Chapter 4Engineering the GeometryIn the previous section, focusing on the CE loss as a special case of the VS loss, we formalizedhow the geometry changes with varying values of R. This choice of the loss correspondsto the fixed value of multiplicative hyper-parameters δ = 1k. We observed that in non-binary imbalanced scenarios, the learned embeddings and classifiers deviate from the ETFgeometry. We used UFM as a proxy to predict the solutions found by SGD in this setup.We investigated the accuracy of UFM predictions on deep models. We further examinedthe changes in the geometry showing that in a setting with growing imbalance ratio R, the(relative) norm of the majority classifiers increases and they become more separated. Thisis in contrast to the minority classifiers that eventually collapse in the asymptotic case ofR→∞, hindering classification on these under-represented groups.In this chapter, we turn our attention to the role of the multiplicative hyper-parametersδ instead. Specifically, we perform a similar study for the CDT (2.3) and LDT (2.4) lossto see whether we can mitigate the impact of imbalances by properly tuning the hyper-parameters.As in the previous chapter, we start by validating UFM’s predictions in the deep-netsetting in Section 4.1. Later in Section 4.2, we discuss the properties of the predictedgeometry analytically and study the implications of special tunings of δ. In the last sectionof this chapter, we provide preliminary results on the generalization performance.Since a global scaling of the hyper-parameters δ → αδ leaves the underlying implicitgeometry unaffected, we characterize the results in terms of ∆ := δmaj/δminor (see (2.5)).It is reasonable to assume that ∆ relates to the imbalance ratio R. Thus, throughout thischapter, we parameterize ∆ by a scalar variable γ in the following manner.∆ :=δmajδminor= Rγ . (4.1)4005101520−1.0−0.8−0.6−0.4−0.20.00.20.4−1.0−0.50.00.51.0−1.0−0.8−0.6−0.4−0.20.00.20.4−2 −1 0 1 202468−2 −1 0 1 2−1.0−0.50.00.51.01.5−2 −1 0 1 2−1.0−0.8−0.6−0.4−0.20.00.20.4−2 −1 0 1 2−1.0−0.8−0.6−0.4−0.20.00.2ETFImplicit GeometrySGD UFMSGD MLPSGD ResnetNorm Ratios Majority Angles Minority Angles Majority-Minority AnglesCDT ∥wmaj∥2/∥wminor∥2∥hmaj∥2/∥hminor∥2cos(wmaj,wmaj)cos(hmaj,hmaj)cos(wminor,wminor)cos(hminor,hminor)cos(wmaj,wminor)cos(hmaj,hminor)05101520−1.0−0.8−0.6−0.4−0.20.00.20.4−1.0−0.50.00.51.0−1.0−0.8−0.6−0.4−0.20.00.20.4−2 −1 0 1 202468−2 −1 0 1 2−1.0−0.50.00.51.01.5−2 −1 0 1 2−1.0−0.8−0.6−0.4−0.20.00.20.4−2 −1 0 1 2−1.0−0.8−0.6−0.4−0.20.00.2ETFImplicit GeometrySGD UFMSGD MLPSGD ResnetLDT ∥wmaj∥2/∥wminor∥2∥hmaj∥2/∥hminor∥2cos(wmaj,wmaj)cos(hmaj,hmaj)cos(wminor,wminor)cos(hminor,hminor)cos(wmaj,wminor)cos(hmaj,hminor)γ γ γ γFigure 4.1: Geometric properties of the last-layer classifiers and embeddings learned bySGD (markers) vs the global optimizers of the CS-SVM (2.6) given by Theorem 2 forCDT and Theorem 3 for the LDT loss (solid lines). The hyper-parameters of the lossare parameterized by γ as in (4.1). All models are trained on the (R = 10, ρ = 1/2)-STEPimbalanced datasets. The markers show the properties of (i) UFM (yellow) (ii) MLP trainedon MNIST (green) and (iii) ResNet trained on CIFAR10 (red) at the final epoch of training.The dashed lines mark the ETF geometry [38].4.1 Numerical ResultsWe begin our analysis by examining the solutions learned by SGD in deep settings. Similarto Section 3.2.4, during training, we compare the last-layer embeddings and classifiers of thedeep-nets with the optimal solutions of UFM as specified by Theorem 2 for the CDT loss,and Theorem 3 for the LDT loss. Again in all experiments, we choose minority fractionρ = 1/2 in a STEP-imbalanced setup. We further choose a fixed imbalance ratio R = 10,and focus on the role of hyper-parameters δ.For each of the two losses and each value of γ (see (4.1)), we examine the convergenceof three models to the theoretical prediction: (i) UFM, (ii) a multi-layer perceptron (MLP)41trained on (imbalanced) MNIST, and (iii) ResNet18 on trained on (imbalanced) CIFAR10.We train the UFM by minimizing unregularized CDT/LDT, while for MLP and ResNetmodels, we use a small weight-decay (λ = 10−5). We use the same training setup as inSection 3.2.4 for experiments on the CE loss. We vary the value of γ, parametrizing thehyper-parameters δ, between (−1.5,+1.5). While with fixed γ, the norm of δ does not affectthe optimal geometry, we observe empirically, that the training speed is heavily influencedby the magnitude of δ. Thus, in all experiments, we normalize the hyper-parameters suchthat 1⊤k δ = k. We defer the rest of the experimental details to Section E.2 in the Appendix.For each model and value of the hyper-parameters (controlled by γ), we measure thegeometric properties of the learned embeddings and classifiers, comparing them to thepredictions of Theorems 2 and 3. We compute: (1) squared ratios of majority-minoritynorms, (2) cosine of angles between pairs of majority-majority, minority-minority, majority-minority classifiers and mean-embeddings. The theoretical values of these metrics can befound by calculating the Gram matrices GW∗ and GH∗ according to Theorem 2 (resp.Theorem 3) for CDT (resp. LDT) loss. In fact, we can find closed-form expressions for thesegeometric properties in terms of the imbalance level R and hyper-parameter ∆ (similar tothe case of CE). These characterizations are listed in Section B for reader’s reference. Forthe empirical values, we compute each metric on all the respective majority and/or minoritypairs, and compare their average to their theoretical counterpart.In Figure 4.1, we illustrate how the geometry of the SGD iterates at the final epoch ofthe training (markers) compares with the UFM’s global solution (solid lines). While thetheoretical predictions are accurate for small values of |γ|, we observe that the convergencebecomes more challenging with large |γ|. Interestingly, this is also the case for the UFM.Furthermore, the theory gives a more accurate prediction of the mean-embeddings’ geometryin case of the LDT, and of the classifiers’ in case of the CDT loss. This is consistent forboth UFM and deep-net models.4.1.1 Centering of EmbeddingsSimilar to the experiments on the CE loss, as described in Section 3.2.2, we center theembeddings before computing norms and angles in all our experiments. This is consistentwith the heuristic centering practice for experiments with balanced data [38, 44, 56]. Inthe case of CDT/LDT, our choice of centering vector is different for each loss function.42Specifically, for the implicit geometry predicted by Theorems 2 and 3, we have,CDT: µ∗G :=∑i∈[n]1nyih∗i =∑c∈[k]µ∗c = 0,LDT: µ∗G :=∑i∈[n]δyinyih∗i =∑c∈[k]δcµ∗c = 0.So, in our experiments, before computing the properties of the embeddings, we centerthem by µG as defined above. Consistent with previous experiments, we observe that thisheuristic centering makes the empirical values math the theoretical ones more closely. SeeSections 3.2.2 and 5.5.1 for more discussions.4.1.2 Optimization BehaviourSimilar to our observations on the CE loss in Section 3.2.4, in both UFM and deep-netexperiments, convergence to the theoretical predictions worsens as the imbalance ratio R in-creases. With CDT/LDT, this is also the case with increasing values of the hyper-parameter|γ|. We show this in Figure 4.2, where we plot dWt and dMt (see Section 3.2.1) for UFMand ResNet trained on CIFAR10 as a function of the training epoch t. While the classi-fiers/embeddings get closer to the predicted geometry as training progresses, the imbalanceratio and hyperparameter values can significantly slow down the convergence.In addition to the worse convergence, it becomes more challenging to enter the zerotraining-error regime as |γ| increases. We illustrate this in Figure 4.3, where we report thetraining accuracy of ResNet trained on imbalanced CIFAR10 per epoch. In general, it iseasier to reach 100% training accuracy by the LDT loss compared to the CDT loss. Thisis consistent with previous observations on CDT [26]. This can partially explain the worseconvergence of the the empirical quantities for large values of |γ| in Figure 4.1, since it getsharder to enter the zero training-error regime.4.2 Geometric AnalysisSimilar to the special case of δ = 1k discussed in Chapter 3, we can find the SVD factorsof the (δ, R)-SEL matrix for general value of the parameters in STEP imbalanced setup.This time the characterization explicitly depend on δ, as well as R, k, ρ. With the explicitcharacterization of the SVD factors, we can express the geometric properties of the global430 200 400 600 800 10000.300.350.400.45∥GWt − ĜW∥FUFM0 200 400 600 800 10000.350.400.450.50R = 20, γ = 0.5R = 20, γ = 1.0R = 2, γ = 0.5R = 2, γ = 1.0∥GMt − ĜM∥F0 100 200 3000.30.40.5EpochResNet+CIFAR100 100 200 3000.350.400.450.50R = 20, γ = 0.5R = 20, γ = 1.0R = 2, γ = 0.5R = 2, γ = 1.0EpochFigure 4.2: Convergence of the last-layer classifiers and mean-embeddings to the im-plicit geometry of Theorems 2 and 3 for UFM and ResNet18 trained on CIFAR10. Themodels are trained by SGD, minimizing the CDT loss. Larger imbalance ratio R andhyper-parameter γ slow down the convergence to the predicted structure.solutions in closed-form in terms of the problem parameters. We provide a complete listof these expressions in Section B.1 in the Appendix. Here, we discuss the implications ofspecial tunings of the hyper-parameters.4.2.1 Special TuningsWe emphasize two notable special cases of the geometries that arise respectively for LDTand CDT when setting δc =√nc ⇔ ∆ =√R.Corollary 4 (Achieving alignment with CDT). In (2.6b), set ∆ =√R. Then, ∀i ∈ [n],cos(w∗yi ,h∗i ) = 1. In other words, each embedding h∗i perfectly aligns with its correspondingclassifier w∗yi.This results from the angle calculations detailed in Section B.1. While this simple tuning440 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80.91.00 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80.91.00 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80.91.0γ =0.0γ =0.5γ =-0.5γ =1.0γ =-1.0γ =1.5γ =-1.5Balanced Accuracy Majority Accuracy Minority AccuracyLDT0 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80.91.00 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80.91.00 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80.91.0CDTEpochFigure 4.3: Training accuracy across epochs for ResNet18 trained on (R = 10, ρ=1/2)-STEP imbalanced CIFAR10 with CDT/LDT loss. It becomes harder to enter the zerotraining-error regime with larger hyper-parameter |γ|.leads to perfect alignment of classifiers and mean-embeddings geometries, it does not implyequal norms or maximal separation for all classes. Thus, the geometry in general is differentfrom the ETF geometry for balanced data. In fact, we can show that in this setting, CDTyields larger separation between the minority classifiers. On the other hand, we show nextthat under the same tuning the implicit geometry of the LDT is an ETF modulo the scalingof the embeddings.Corollary 5 (Achieving ETF with LDT). In (2.6c), set ∆ =√R. Then, (W∗,M∗ diag (δ))follows the ETF geometry.Corollary 5 follows immediately from Theorem 3 by noting that δc =√nc yields R˜ = 1and the (1k, 1)-SELI geometry coincides with the ETF geometry. This implies that not onlyclassifiers and embeddings are perfectly aligned, but also all classifiers w∗c , c ∈ [k] have equalnorms, and both the classifiers and embeddings are maximally separated. In other words,cos(w∗c ,w∗c′) = cos(h∗c ,h∗c′) = −1/(k − 1). Notably, this holds irrespective of the imbalanceratio R. See Figure 2.2 for a visualization with k = 4.We can also observe this behavior in the numerical results illustrated in Figure 4.1.For LDT, the prediction is well followed by UFM and ResNet empirics around the valueof γ = 1/2 (∆ =√R), with an exception of the majority classifier angles in the ResNet45experiments. As predicted by the theorem, in this case, the LDT geometry is the ETF, upto a scaling on the features: in Figure 4.1, the LDT cosine plots intersect with the ETFangles, i.e., −1/(k−1), thus achieving equiangularity and maximal angular separation. Theclassifier norm ratios also attain the value 1, which along with the equiangularity describean ETF structure for classifiers.4.2.2 Mitigating Minority CollapseAs also discussed in Section 3.3.2, Fang et al. [9] discovered that when R→∞, for any twominority classes cos(wminor,w′minor) → 1, and the minority classifiers collapse. We showhere that CDT and LDT losses can mitigate this effect when appropriately tuned. For this,we simply evaluate our closed-form formulas in Section B.1 in the limit R→∞. We repeatthe angle calculations here for reference.CDT: cos(wmin,w′min) =−2 + 2√R+ 1(√1 + ∆2)−3k − 2 + 2√R+ 1(√1 + ∆2)−3 ,LDT: cos(wmin,w′min) =−2∆ +√(R+∆2)/2(k − 2)∆ +√(R+∆2)/2 . (4.2)Corollary 6 (Mitigating classifier collapse with LDT). In (2.6c), set ∆ = Rγ , γ ∈ R.Then, as R→∞ the minority/majority angles satisfy,cos(wc,w′c) γ < 1/2 γ = 1/2 γ > 1/2c, c′ ∈ minority 1 − 1k−1 1−2√21+√2(k−2)c, c′ ∈ majority 1−2√21+√2(k−2) −1k−1 1Table 4.1: Asymptotic value (R→∞) of the minority/majority angles with LDT loss.Corollary 7 (Mitigating classifier collapse with CDT). In (2.6b), set ∆ = Rγ , γ ∈ R.Then, as R→∞ the minority/majority angles satisfy,46cos(wc,w′c) γ < 1/6 γ = 1/6 γ > 1/6c, c′ ∈ minority 1 0 − 2k−2cos(wc,w′c) γ < 0 γ = 0 γ > 0c, c′ ∈ majority − 2k−2 1−2√21+√2(k−2) 0Table 4.2: Asymptotic value (R→∞) of the minority/majority angles with CDT loss.From Corollary 6, LDT with γ ≥ 1/2 avoids minority collapse. However, for γ > 1/2,majority classifiers collapse instead. Thus, we find that γ = 1/2 is the only choice that keepsboth majority and minority classifiers from collapsing. In fact, for this choice the anglesof majorities and minorities are all equal, as expected by Corollary 5. On the other hand,from Corollary 7, CDT avoids minority collapse for any choice of γ ≥ 1/6. Also, in thisentire range the majority classifiers do not collapse either. Thus, for R → ∞, CDT offersa wide tuning range for γ that avoids classifiers collapse in the highly imbalanced regimes.Compare this to the single value of γ = 1/2 for LDT. This suggests that the CDT geometryis more robust to small changes in the hyperparameter γ compared to the LDT geometry.Specifically for γ = 1/2, when classifiers and features are aligned in both CDT and LDT(see Corollaries 4 and 5), the CDT minority angles are larger than the LDT angles since−2/(k − 2) < −1/(k − 1); see also Figure 2.2.While the experiments in Figure 4.1 correspond to a finite imbalance ratio of R = 10,there is resemblance to the asymptotic behavior of the classifier angles on LDT-trainedUFM. Corollary 6 suggests γ = 1/2 is the only choice for R → ∞ that avoids minority ormajority classifiers collapsing. A similar trend is seen in Figure 4.1, where the cosine ofthe minority classifiers goes towards 1 for γ < 1/2, while that of the majority classifiersapproaches 1 for the complementary open interval of γ > 1/2. On the other hand, CDTdoes not attain equiangularity, but majority and minority angles are well controlled for awider range of γ.4.3 GeneralizationUp to this point, we demonstrated that different CE parameterizations lead to distinctimplicit geometries for classifiers and embeddings during the training process. In this sec-tion, we provide preliminary results on the generalization of models trained with CDT/LDTlosses: In Section 4.3.1, we investigate a simple model that aims to capture the link between47generalization and implicit geometry. In Section 4.3.2, we present empirical results fromexperiments on benchmark data, which we compare to our model’s predictions.4.3.1 Impact of GeometryIn our analysis on UFM, we characterize the properties of the embeddings that the networklearns from the training samples. In order to assess generalization, it is necessary to definethe geometry of test embeddings rather than just those from the training. This is typicallychallenging for neural networks in general. Here, we simplify the scenario by assuming thatthe mean-embeddings at test time are similar to their training counterparts in a way thatwe formalize below. Using this model, we aim to acquire broader insights into the impactof various implicit geometries on the test performance.We are interested in the balanced test error that weighs all classes equally, unlike thestandard error that relies on class priors. This is a standard evaluation metric used indata-imbalanced training regimes in previous works [e.g., 7, 26, 27, 34, 51]. To evaluatethe balanced test error, we assume that the embeddings are concentrated around theirclass-means with some small variance. Specifically, suppose (W,M) are the classifiers andmean-embeddings induced by CDT/LDT loss at the end of training, and µc is the mean-embeddings of the training samples belonging to class c ∈ [k]. We assume that, at testtime, the emeddings h ∈ Rd with label c ∈ [k] follow an isotropic Gaussian distributioncentered at µc, and with variance σ2c . In other words, h|(y = c) ∼ N (µc, σ2c Id). With thisassumption, the balanced error rate can be found as follows,Rbal = 1k∑y∈[k]Ph∼N (µy ,σ2y Id)(maxc ̸=y(wc −wy)⊤h ≥ 0). (4.3)To simplify the analysis, we assume that at test time, the degree of within-class variationσ2c depends only on the class size at the training stage: observing fewer samples at thetraining stage yields larger variance on the test embeddings. Thus, in a STEP imbalancedsetting, we parameterize the distribution of the test embeddings by σmaj ≤ σminor such that,σc =σmaj, c is a majority classσminor, c is a minority class .We further assume that σminor/σmaj is related to the imbalance ratio R. In other words, the48Mean EmbeddingClassifierMajorityMinority(a)100 101 102100101102MNIST+VGGCIFAR10+VGGMNIST+ResNetCIFAR10+ResNetRσ̂2minor/σ̂2maj(b)Figure 4.4: Gaussian mixture model for the generalization analysis of Section 4.3.1:(a) Schematic of the test embeddings distribution for k = 3 classes with two minoritiesand one majority; (b) The variance of minority test embeddings vs the majorities as afunction of the imbalance ratio R in the deep-net experiments of Section 3.2.4.embeddings from majority classes are more concentrated around their means at test time,while the embeddings from minority classes spread more as the imbalance ratio R increases(see Figure 4.4a). We model this relationship as σminor/σmaj = Rα for some α > 0. Here,α captures the impact of the imbalance ratio on the variations of test embeddings. In fact,this model of test variance is on par with our observations on deep-nets trained with CE.Specifically, for the deep-net experiments of Section 3.2.4, we measure the average varianceof the test embeddings around their corresponding class-center for minority and majorityclasses as follows,σ̂2maj =1ρ k nmajρk∑c=1∑i: yi=c∥hi − µyi∥22, σ̂2minor =1ρ k nminork∑c=ρk+1∑i: yi=c∥hi − µyi∥22.Here hi represents the test embeddings and µc is the mean-embedding of the trainingsamples in class c ∈ [k]. In Figure 4.4b, we plot the ratio of minority-majority varianceversus the imbalance level R for different architectures and datasets. We observe thatσ̂2minor/σ̂2maj has log-linear dependence on the imbalance ratio R.To only capture the role of the geometry in the Gaussian model, we keep the total SNR49100 101 1020.20.40.60.8RCE LossClassificationError0 1 20.00.20.40.60.81.0γCDT Loss (R = 10)0 1 20.000.250.500.751.00Majority ErrorMinority ErrorBalanced ErrorγLDT Loss (R = 10)Figure 4.5: Test error (4.3) under the Gaussian mixture model of Section 4.3.1 fordifferent SELI geometries that are optimal in the CS-SVMs (2.6) corresponding to theCE, CDT and LDT loss. In all experiments k = 10 , ρ = 1/2, and α = 1. Error isplotted as a function of the imbalance ratio R for CE and as a function of the hyper-parameter γ for CDT and LDT.of the model fixed. We do so by choosing σ2maj such that∥µmaj∥22σ2maj+∥µminor∥22σ2minor=∥µmaj∥22σ2maj+∥µminor∥22σ2majRα= constant,across different geometries. For concreteness, we choose k = 10, ρ = 1/2 and α = 1. ForCE, we vary the value of the imbalance ratio R and measure the error rate (4.3) by Monte-Carlo simulations. For CDT and LDT, we fix R = 10, and vary the value of γ (see (4.1)) tocompute the error across different (δ, R)-SELI geometries. Figure 4.5 illustrates the errorfor different implicit geometries. Varying γ introduces a trade-off between the error on themajority and minority classes. Specifically, as γ increases and δmaj gets (relatively) larger,the model classifies the minority classes more accurately (despite their larger within-classvariance). On the other hand, the error on majorities raises significantly. The geometrywith the lowest error is achieved by γ ∈ [0, 1]. We note that the optimal value of γ variesfor different choices of α.4.3.2 Numerical Results on GeneralizationIn this section, we present preliminary empirical observations on the balanced test errorRbalachieved by minimizing CDT/LDT loss functions on benchmark datasets. We compare thetest accuracy of CDT, LDT and weighted CE (wCE) loss by evaluating the performanceof ResNet18 trained on CIFAR10 and of MLP trained on MNIST and Fashion-MNIST for50−0.25 0.00 0.25 0.50 0.75 1.00 1.250.840.860.880.90 WCELDTCDT−0.25 0.00 0.25 0.50 0.75 1.00 1.250.900.920.940.96−0.25 0.00 0.25 0.50 0.75 1.00 1.250.700.750.800.850.90Balanced Accuracy Majority Accuracy Minority AccuracyResNet+CIFAR10−0.25 0.00 0.25 0.50 0.75 1.00 1.250.9550.9600.9650.9700.975−0.25 0.00 0.25 0.50 0.75 1.00 1.250.9800.9850.9900.995−0.25 0.00 0.25 0.50 0.75 1.00 1.250.920.940.96MLP+MNIST−0.25 0.00 0.25 0.50 0.75 1.00 1.250.8600.8650.8700.8750.880−0.25 0.00 0.25 0.50 0.75 1.00 1.250.890.900.910.92−0.25 0.00 0.25 0.50 0.75 1.00 1.250.800.820.840.86MLP+FMNISTγγ γFigure 4.6: Test accuracy for ResNet18 and MLP trained on (R = 10, ρ=1/2)-STEPimbalanced datasets using CDT, LDT and wCE losses for different hyper-parametervalues. The accuracy is reported over 10 independent runs. Best test accuracies forCDT and LDT are generally achieved at γ = 0.75 and γ = 0.5 respectively with wCEshowing no major improvement compared to the other two losses.each loss function. In order to have results comparable to the state-of-the-art, we performdata augmentation on all three datasets [7, 51]. For all three losses, we control their hyper-parameters by a single variable γ: we choose ωminor/ωmaj := Rγ for the weights of wCEand δmaj/δminor = Rγ for CDT/LDT loss as in (4.1). We also normalize δ values similarto Section 4.1 to have δ⊤1k = k. We note that all these losses reduce to the CE loss whenγ = 0. In Figure 4.6, we present the average performance across 10 independent runs foreach value of γ and for each loss function.CDT loss has the best balanced accuracy on the test set for γ ∈ [0.5, 1.0]. On the otherhand, compared to CDT, LDT loss does not exhibit major improvements. The highest testaccuracy for LDT is achieved usually around γ = 0.5 which according to Corollary 5, is thesame value that leads to the ETF geometry up to scaling of embedding norms. wCE hasthe lowest accuracy among the losses with the best test performance being comparable toCE (γ = 0) across different experiments.51For CDT, we observe that larger values of γ lead to better test performance for minorityclasses, but worse performance for majorities which is consistent with our analysis in Section4.3.1. However, for LDT, the test accuracy for majority classes does not drop as much withlarger γ values and the accuracy for minority classes peaks at γ ∈ [0.5, 0.75] and drops ateither side. This is in contrast to our analysis from Section 4.3.1 where we expect LDT tohave a similar trend to that of CDT’s. These observations motivate further investigationinto the geometry of embeddings during the evaluation phase.4.4 SummaryIn this chapter, we specified how we can modify the implicit geometry learned at the trainingstage. We focused on two losses, CDT and LDT, that adjust the logits of the deep-netsby multiplicative factors. Through our analysis in Chapter 2, we saw that the optimallogits of the network are affected by the choice of the hyper-parameters. In this section, weformalized the implications of this change on the properties of the last-layer classifiers andembeddings. Both CDT and LDT enable us to control certain unfavorable observations inimbalanced setups, such as minority collapse. We further provide preliminary results onthe test performance in this setup, showing that CDT outperforms LDT in general. Thepriority of CDT at test may lie in the fact that CDT can lead to more separation betweenthe minority classifiers. Further investigation on the generalization analysis is required for amore principled understanding on the role of the hyper-parameters on the test performance.52Chapter 5Towards a Geometric View ofContrastive LearningIn the previous chapters, we adopted the UFM as a proxy model for deep-nets to outlinecertain characteristics of over-parameterized models trained with CE loss or its parame-terizations. With a focus on the last layer of the network, we formalized the properties ofthe classifiers and embeddings learned at the end of the training. In Chapter 3, we sawthe impact of imbalanced training sets on the learned parameters, and in Chapter 4 wediscussed the benefits of tunable hyper-parameters in the CE loss, providing control overthe learned geometry.Here, we look into the supervised contrastive (SC) loss. Contrastive techniques haveled to major improvements in the self-supervised representation learning [e.g., 8, 45], andrecently, Khosla et al. [24] introduced the SC loss as an extension of these techniques tailoredto the supervised problems. SC loss is applied on the embeddings generated by the networkand it penalizes the model by measuring the (dis)similarity between the embeddings learnedfor different samples. This is in contrast to CE that is applied on each sample individually,aiming to maximize the class-probability associated with the correct label. Unlike CE thatlearns the encoder and classifier simultaneously, training with the SC loss, involves twostages. First, the encoder is separately trained to learn the embeddings. The objectiveat this stage is to bring the embeddings with the same label close to each other whilekeeping them apart from those belonging to other classes. In the second stage, a classifieris separately trained on the frozen embeddings learned in the first stage.In this chapter, we use UFM to study the SC loss, similar to what we did in the previ-ous chapters for CE. Contrastive learning involves several heuristics for achieving optimalperformance in practice. We choose to overlook some of these common practices to sim-plify the analysis (we will elaborate on these assumptions in Section 5.1). While not being53fully consistent with the practice, we believe this preliminary analysis can provide usefulinsights for future works. In the remainder of this chapter, we focus on the first stage, thatis training an encoder by minimizing the SC loss.5.1 Practices in Contrastive LearningRecall that on a dataset S = {(xi, yi) : i ∈ [n]} of size n, the SC loss is as stated below.LSC(H; τ) := 1n∑i∈[n]1nyi − 1∑j ̸=i,yj=yi− log(exp(h⊤i hj/τ)∑ℓ ̸=i exp(h⊤i hℓ/τ)), (5.1)where hi := hθ(xi) is the embedding associated with the i-th training sample. Here, scalarτ is a positive temperature hyper-parameter. This parameter was introduced in the loss byKhosla et al. [24] as they observed it can boost the performance of the model by controllingthe smoothness of the loss. SC favors encoders hθ(·) that push each embedding hi closeto the samples j with similar labels, i.e., yj = yi, and away from others with yj ̸= yi.The encoder can be the same encoder used for training the CE loss, for instance a ResNetmodel after discarding the last-layer linear classifier. Due to the pair-wise comparison ofthe embeddings in the loss function, SC loss has a high computational cost. As a result, inpractice, the loss is approximated over random batches chosen from the training set, insteadof the whole set S.As introduced by Khosla et al. [24], SC requires normalized features, so we assume theencoder is followed by a normalization layer that maps the embeddings to the unit sphere.In other words, the encoder generates embeddings with ∥hi∥2 = 1, and SC penalizes themodel based on the cosine similarity of the embeddings.Furthermore, at the training stage, the SC loss is not directly computed on the em-beddings. In fact, the embeddings are passed through a projection layer (which can beas simple as a single-layer or shallow MLP), and the loss is minimized on the projectedembeddings. However, this projection layer is discarded at test time, as it is empiricallyshown that using the pre-projection embeddings boosts the performance on down-streamtasks.545.1.1 Modeling the SC LossFor simplicity, in our analysis, we only consider the full-batch scenario, where the lossfunction is calculated over the whole training set S as in (5.1). We also ignore the projectionhead of the network, and focus on studying the embeddings on which the loss is directlycomputed. This is similar to the analysis performed by previous works [9, 11, 48].On the other hand, we can view the temperature parameter τ as a scaling on theembeddings hi. Specifically, it is easy to see that LSC(H; τ) = LSC(H˜; 1) where H˜ = H/√τand as a result ∥h˜i∥22 = 1/τ for all i ∈ [n]. Since, constraining the norms to the sphereyields a non-convex feasibility set, we relax the norm constraints to a ball of radius 1/√τ .In other words, we study the UFM formulated as follows,H∗ ∈ argminHLSC(H) subj. to ∥hi∥22 ≤1τ, ∀i ∈ [n]. (5.2)We note here that, as before, the minimization is over the unconstrained embeddings Hthat do not depend on the network parameters θ. It is also worth mentioning that althoughwe simplified the problem to deal with a convex feasibility set, the problem (5.2) has anon-convex objective function.5.1.2 Related Works and OverviewIn the series of UFM inspired works, unlike CE or mean squared loss, less attention hasbeen devoted in the existing literature to the contrastive type losses. Graf et al. [11] is thefirst syudy that explicitly delves into understanding the embeddings geometry of the SCloss and comparing it with CE. They study the UFM trained by the SC loss (on normalizedembeddings ∥hi∥22 = 1/τ) and show that with balanced training distribution, the minimizeris ETF as in the case of the CE. They further provide the same analysis for the batch-wiseSC loss, proving that minimizing SC over all combination of batches of a fixed size yieldsthe ETF. Yet, they argue that with general batch structure the optimal solution might driftaway from ETF, and a full analysis of UFM with general batching remains unexplored.Fang et al. [9] also discusses SC in the UFM context, showing similar type of results forbalanced data. Later, Yaras et al. [50] conjecture that as for the UFM with CE loss (1.8), inthe UFM context SC (with normalized features) has a benign landscape, with no spuriouslocal minima. They claim this by numerically verifying that we can reach the global solutionof the UFM by running simple gradient methods.55Here, as stated earlier, we relax the norm constraints and study the UFM in (5.2) inSection 5.3. We will demonstrate that all stationary points in this problem satisfy the NCproperty. Leveraging this finding, we show that (5.2) exhibits a benign landscape. As aconsequence of this analysis, we are able to simplify problem (5.2) into a lower-dimensionalequivalent program under the STEP imbalanced assumption on the training set. For thespecial case of balanced training data, this program reveals ETF as the optimal geometry.However, it will become evident that ETF is not necessarily a global solution otherwise.We leave the charcterization of the geometry in imbalanced scenarios for future work.While our analysis shows that the geometry of the embeddings learned by SC loss issensitive to imbalances, in Section 5.4, we will see that a simple modification on the UFMmakes the optimal solution of the problem invariant to imbalances. Specfically, constrainingthe embeddings to the non-negative orthant, we observe that UFM+ (5.3), regardless of theimbalance profile, learns the same implicit geometry for the embeddings. We validate thisfinding on deep-net models, which also exhibit invariant geometry at the training stage.H∗ ∈ argminHLSC(H) subj. to H ≥ 0 and ∥hi∥2 ≤ 1τ, ∀i ∈ [n]. (5.3)5.2 NC Holds at Local Optimal SolutionsWe start our analysis by indicating a necessary condition for local optimality. The resultprovided in this section, holds for both UFM (5.2) and UFM+ (5.3). We re-iterate herethat despite the relaxed convex constraints in the problem, the problem is non-convex. Letnmax = maxc∈[k] nc be the size of the largest class, and recall the necessary condition forlocal optimality in a general optimization with convex constraints.Proposition 3 (Necessary stationarity condition [5, Chapter 2]). Consider the optimizationproblem minx∈C f(x) over a convex set C. Let x̂ ∈ C be a local minimum. Then,∇f(x̂)⊤(x− x̂) ≥ 0, ∀x ∈ C. (5.4)Lemma 5.2.1. Assume the temperature parameter τ > 2/log((n− 1)/(nmax − 1)). Let Ĥbe locally optimal in the UFM (5.2) / UFM+ (5.3) problem. The NC property holds at Ĥ.Lemma 5.2.1 shows all the feasible points that are locally optimal have a low-rankstructure and satisfy the collapse property. Thus, similar to the case of CE, it follows that56at the global solutions, the embeddings collapse to their class-means. The proof of thislemma simply relies on showing that condition (5.4) does not hold for a feasible Ĥ thatdoes not meet the NC property. Specifically, suppose y1 = y2 and ĥ1 ̸= ĥ2. Then, define Hby swapping the first two columns of Ĥ, i.e., H = [ĥ2, ĥ1, ĥ3, · · · , ĥn]. Then H− Ĥ gives anegative direction for ∇LSC(H). We defer the details to Section D.2 in the Appendix. Wefinally note that the condition on τ is only a sufficient requirement but not a necessary one.We conjecture that this condition can be relaxed.The rest of our results in this chapter, rely on Lemma 5.2.1. Thus, in the remainder ofthis work, we assumeτ > 2/log( n− 1nmax − 1). (5.5)For balanced data, nmax = n/k and the condition approximately becomes τ > 2/ log(k) forn >> k, which is not restrictive in practical settings. For brevity, we do not re-state thiscondition in the next sections.5.3 UFM: Landscape and Optimality ConditionsHere, we study the local and global optimality conditions for the UFM under the SC lossin (5.2). Since the problem is non-convex, it is not obvious whether (5.2) has a uniquesolution or if it has a landscape free from spurious local solutions (which are not globallyoptimal). In fact, it is easy to see that the global solution is not unique, since rotating theembeddings by an orthonormal matrix R, does not change the value of the loss function,i.e., LSC(R⊤H) = LSC(H). The next theorem ensures that all locally optimal solutions areglobal optimizers of the SC loss in (5.2).Theorem 4 (UFM landscape with SC loss). Assume the feature dimension exceeds thenumber of classes, d > k. Then, all the local solutions of the UFM (5.2) are global optima.Proof SketchWe defer the details of the proof to Section D.3 in the Appendix. Here, we give a proofsketch. The main idea is to relate the KKT points of the problem (5.2) to the KKT pointsof its convex relaxation. To define the convex relaxation, we note that the SC loss in (5.1)57is in fact a convex function of the Gram matrix G := H⊤H.LSC(H) = L̂(G) := 1n∑i∈[n]1nyi − 1∑j ̸=i,yj=yi− log(exp(Gi,j)∑ℓ̸=i exp(Gi,ℓ)).We can formulate the convex relaxation with the symmetrized objective function as follows.G∗ ∈ argminGLcvx(G) := 12(L̂(G) + L̂(G⊤)), subj. to G ≽ 0, Gi,i ≤ 1τ, ∀i ∈ [n]. (5.6)This convex program satisfies the Slater’s conditions. Hence, strong duality holds and anyKKT point Ĝ of (5.6) is a global solution.Suppose Ĥ is a local optima. Thus, it satisfies the KKT conditions of the non-convexproblem (5.2) along with the dual variable λ̂ ∈ Rn. Furthermore, by Lemma 5.2.1, the NCproperty holds at Ĥ and rank(Ĥ) ≤ k < d. Using this property, we can show that it isnecessary for (Ĥ, λ̂) to satisfy the following,∇Lcvx(Ĥ⊤Ĥ) + diag(λ̂)≽ 0.From here, it is straightforward to prove (Ĝ := Ĥ⊤Ĥ, λ̂) is a KKT point of the convexproblem (5.6). Equivalently, by strong duality, Ĝ is a global optimizer. On the other hand,since (5.6) is a relaxation of the original UFM (5.2), for the optimal solution H∗, we have,LSC(Ĥ) = Lcvx(Ĝ) ≤ Lcvx(H∗⊤H∗) = LSC(H∗). (5.7)In other words, Ĥ is a global optimum of (5.2), and the proof is complete. This furthershows that the relaxation in (5.6) is tight.Corollary 8. Suppose d > k. Then, the convex program (5.6) is a tight relaxation of (5.2).5.3.1 Global SolutionsBy Lemma 5.2.1, we know that the global solution of the UFM (5.2), as a first orderstationary point, has the NC property. Thus, to find the conditions of global optimality, weonly need to find the k mean-embedding vectors that are optimal. Given the NC propertyat the optimal solution, in the (R, ρ)-STEP imbalanced setting, we can use the symmetryin the size of the classes to even further simplify the structure of the global solution. LetKmaj = {1, · · · , ρk} and Kminor = {ρk+1, · · · , k} be the majority and minority class indices58respectively. The following lemma characterizes this result.Lemma 5.3.1. Assume an (R, ρ)-STEP imbalanced setting with k classes. Let H∗ be theglobal solution of (5.2). Then G∗ = H∗⊤H∗ is the unique optimizer of the convex program(5.6) and there exists scalars αmaj/minor, βmaj/minor, θ ∈ [−1/τ, 1/τ ] such that,∀i, j ∈ [n], G∗i,j = ⟨h∗i ,h∗j ⟩ =αmaj, if yi = yj , yi, yj ∈ Kmaj,αminor, if yi = yj , yi, yj ∈ Kminor,βmaj, if yi ̸= yj , yi, yj ∈ Kmaj,βminor, if yi ̸= yj , yi, yj ∈ Kminor,θ, if yi ∈ Kmaj/minor, yj ∈ Kminor/maj.We present the proof in Section D.4. Recall from Corollary 8, the relaxation (5.6) istight, and finding G∗ characterizes the geometry of the optimal H∗. This lemma reducesthe dimension of the original problem in the case of STEP imbalanced data. In the specificcase of balanced data (nc = n/k), the optimal solution reduces to ETF.Theorem 5. Assume that the training set is balanced. The optimal solution H∗ of theUFM (5.2) follows an ETF.The proof is deferred to Section D.5. This theorem follows from Lemma 5.3.1. Specifi-cally, in the balanced case, αmaj = αminor, βmaj = βminor, and the optimal G∗ satisfies,G∗ = (α− β) In + ((β − θ)Ik + θJk)⊗ J(nk),for some scalar α, β, θ ∈ R. On the other hand, G∗ is feasible if it is positive semi-definiteand its diagonal entries are less than 1/τ . Thus, we can show solving UFM (5.2) reducesto optimizing the following linear program.(α∗, β∗, θ∗) = arg minα,β,θθ − β, sub. to 1τ− α ≥ 0,α− β ≥ 0,α+ β(nk− 1)− θnk≥ 0,α+ β(nk− 1) + θ(n− nk) ≥ 0.59From above, we can see α∗ = β∗ = 1/τ and θ∗ = −1/(τ(k − 1)), and ETF is the onlysolution. However, this is not the case if the training set is imbalanced:Proposition 4. If classes in the training set are not balanced, the global solution of (5.2)is not necessarily an ETF.Overall, in balanced scenarios, as also previously shown [9, 11], SC learns the sameembeddings as the CE loss. Similarly, the optimal solutions of the SC loss change withimbalances. Its interesting on its own to specify the optimal solutions of the SC loss underthe imbalanced condition and copmare the behavior of the two losses. We will leave thisinvestigation for future works. Next, we will focus on a modified version of the UFM, thatis UFM+ (5.3).5.4 UFM+: Invariance to ImbalancesBy Lemma 5.2.1, for any global minimizer of the SC loss, the embeddings collapse to theirclass-means. In other words, h∗i = µ∗yi , i ∈ [n]. Thus, instead of optimizing the loss over H,we can solve the problem for mean-embeddings by minimizing the following SC loss overM. Note that the loss is modified to account for the number of samples in each class.L˜SC(M) := 1n∑c∈[k]nc log((nc − 1) +∑c′ ̸=cnc′ exp(− µ⊤c µc + µ⊤c µc′)).Suppose we constrain the embeddings to the non-negative orthant µc ≥ 0. This correspondsto the UFM+ in (5.3). Then, we have 0 ≤ µ⊤c µc′ ≤ 1/τ , and we can lower-bound the lossas follows,L˜SC(M) ≥ 1n∑c∈[k]nc log((nc − 1) + (n− nc) exp(− 1/τ)).The lower-bound can be achieved by an optimal H∗ that has no dependence on the distri-bution of the training labels. The following theorem formalizes this fact.Theorem 6 (SC minimizers). Let d ≥ k, and consider the UFM+ problem in (5.3). LetH∗ be the optimal embeddings and M∗ be the mean-embeddings at the optimal solution. H∗satisfies the NC property and M∗⊤M∗ = 1τ Ik.60In other words, all the optimal solutionsH∗ share the same geometry. We highlight thatthe optimal solution has no dependence on the number of samples in each class, {nc}c∈[k].We refer to this unique and invariant geometry as the orthogonal frame (OF).Definition 9 (OF geometry). We say that an embedding matrix H follows the OF geometryif it satisfies the NC property and the class-means form an orthogonal frame, i.e., for themean-embeddings matrix M, GM := M⊤M ∝ Ik. In other words, for each pair of (i, j) ∈[k], ∥µi∥2 = ∥µj∥2 and µ⊤i µj = 0.Unlike the rest of the results on the UFM, here we do not make any assumptions on thelabel configuration of the training set, suggesting that SC can learn embeddings that areinvariant to imbalances. In the next section, we test this theory in deep settings.5.5 Numerical ResultsModifying UFM by introducing non-negativity constraints, corresponds to adding a ReLUactivation after the encoder. According to Theorem 6, when training with SC in this case,we should learn features that share the same geometry regardless of how imbalanced thetraining set is. In this section, we provide preliminary results on training with the SCloss to verify Theorem 6 on deep-nets. For the encoder, we use ResNet18 encoder (bydiscarding the last classifier layer) followed by a normalization layer. We note that ResNetencoder applies ReLU activation on the embeddings. Thus, this choice of encoder fitsin the additional non-negativity constraint in the UFM+. We run the experiments on twoimbalance patterns: (i) R-STEP (Definition 4) and (ii) R-Long-tail (LT) imbalanced. In theLT setup, we assume n1 > n2 > ... > nk and the number of samples decreases exponentiallysuch that nk = n1R−1. Following [11, 24], we set the temperature parameter τ = 0.1. Weempirically find that convergence to OF is not highly dependent on τ for values near 0.1,yet the specific choice affects the speed of convergence. Besides this, Khosla et al. [24] havefound that τ = 0.1 leads to the best generalization performance. We defer the details onthe training setup to Section E.3.We use the metrics defined in Section 3.2.1. We track the collapse of the embeddingsby measuring dNC and the distance of Mt to the OF geometry by computing dMt withĜM = Ik (see Section 3.2.1). Figures 5.1a and 5.1b illustrate the value of these twometrics. Across our deep-net experiments, we consistently observe that the learned featuresduring training converge to the OF geometry, irrespective of the imbalance level R of the610 50 100 150 200 250 300 35010 310 210 11001011020 Train Error0 50 100 150 200 250 300 35010 310 210 11001011020 50 100 150 200 250 300 35010 310 210 1100101102 R = 1R = 5R = 10R = 100CIFAR10 MNIST FMNISTSTEP0 50 100 150 200 250 300 35010 310 210 11001011020 Train Error0 50 100 150 200 250 300 35010 310 210 11001011020 50 100 150 200 250 300 35010 310 210 1100101102 R = 1R = 5R = 10R = 100LT(a) NC measure dNC.0 50 100 150 200 250 300 3500.20.40.60.81.00 Train Error0 50 100 150 200 250 300 3500.20.40.60.81.00 50 100 150 200 250 300 3500.20.40.60.81.0R = 1R = 5R = 10R = 100STEP0 50 100 150 200 250 300 3500.20.40.60.81.00 Train Error0 50 100 150 200 250 300 3500.20.40.60.81.00 50 100 150 200 250 300 3500.20.40.60.81.0R = 1R = 5R = 10R = 100LTEpoch(b) Distance to the OF geometry dMt .Figure 5.1: ResNet18 trained on imbalanced data with the SC loss. Last-layer embeddingsconverge to OF when there is ReLU in the final layer of the encoder. The convergencebehaves similarly for a wide range of imbalance ratio R.62training set. For different values of R, there is no significant difference between the speed ofconvergence, unlike the CE loss, where we empirically observed that the rate worsens withlarger imbalance levels (see Figure 3.3).5.5.1 Centering Heuristic: UFM vs UFM+Many deep neural network models incorporate activation functions, resulting in embeddingsthat are explicitly constrained in the embeddings space. For instance, with ReLU activa-tions, the learned embeddings are always nonnegative at the last layer. In contrast, theUFM does not impose any constraints on the optimal H, allowing it to contain negative en-tries. As stated earlier in the case of the CE parameterizations, to bridge this gap, previousworks [e.g., 9, 38, 44, 54–56] apply a heuristic global centering on the learned embeddingsbefore comparing their arrangement with the theoretical prediction given by the UFM. Wediscussed this centering heuristic for CE loss in Section 3.2.2 and for CDT/LDT loss in Sec-tion 4.1.1. In short, this heuristic centering operation involves subtracting a vector µG fromthe embeddings, ensuring their weighted average is zero. The weights for each geometry isdefined by the property of the reference geometry and differs for each loss function.We numerically observe that UFM can (approximately) predict the centered embeddings.However, the UFM analysis itself does not provide any information regarding the necessityof the centering technique, which remains heuristic. Unlike the approach mentioned above,UFM+ does not require any heuristic embedding processing for comparing the geometries.This is because the model directly provides the geometry of the embeddings in their originalform.5.6 DiscussionsRole of non-linearity. From our discussion in this chapter, we observed that adding asimple non-linear component to the model can yield strikingly different behavior in theoptimization problem. Although it is not a common practice in the contrastive learningliterature to have ReLU activations on the last-layer embeddings, we leveraged this modi-fication in the UFM to emphasize on the different nature of linear and non-linear regimes.Centering heuristic. In all the previous analysis on the UFM, we were able to predict thetraining geometry only up to a global shift on the embeddings. This global centering wasjustified in the previous works to account for the activation functions at the final embedding63layer, which prevents the embeddings H to be fully unconstrained in the embedding space.The analysis on UFM+ did not require this centering as the explicit constraints of UFM+on H is consistent with the adopted deep-net in the experiments. Since UFM does notprovide an exact characterization for the required centering, we need more accurate modelsto capture the exact learning process in practical deep-nets.Robust convergence. In our experiments in this chapter, we notice that, for any label-imbalanced data, the geometry learned by SC exhibits a fast convergence to the OF, theminimizer of UFM+. This is in odds with the behavior observed in Chapter 3 for CEloss where the convergence of embeddings deteriorates as the imbalance ratio increases (seeFigure 3.3). It is interesting to explore whether this behavior lies in an intrinsic differencebetween the two losses, or whether the UFM mismatch from the practical setting is causingthe inconsistent convergence to the theoretical prediction.5.7 SummaryOur focus in this chapter was on training with a contrastive objective. While we do notprovide a complete analysis of the current practice in contrastive learning, we used thisproblem setup to explore the implications and limitations of the UFM analysis. We observedthat the SC loss in the UFM context shares similarities with the CE loss: (i) the optimalsolution in balanced case is ETF, (ii) optimal solutions vary with imbalances, and (iii)UFM has no spurious local optimums. While we did not characterize the exact optimalityconditions for imbalanced setups, we saw that applying ReLU on the final layer embeddingsyields a geometry that is invariant to label-imbalances. While not aligned with the currentpractice, we used this setting to emphasize on the importance of developing accurate modelsfor theoretical study and to highlight the role of non-linearity in a simple example.64Chapter 6ConclusionThis thesis investigates the learning biases of deep over-parameterized models particularlyin the context of class-imbalanced learning. Unlike linear models, the intricate interplay ofnumerous layers of parameters and non-linear operations within deep networks introducesa high degree of complexity in their analysis. However, inspired by previous studies in theNeural-collapse literature, a simple proxy model helps us uncover and formalize commonproperties among over-parameterized models.Our analysis relies on the unconstrained features model (UFM) for characterizing (i) thelast-layer embeddings that deep-nets learn from the training set, and (ii) the classificationrules they devise at the final layer. This abstract model is built upon the assumption thatdeep-nets, when sufficiently over-parameterized, are expressive enough to learn any mappingfrom the input to the embeddings space. Despite the strong assumption made in this model,we observe in our numerical experiments, that UFM reveals a close approximation of thelearned structures.Leveraging UFM, we devise an analytical framework for characterizing the geometricalproperties of the learned last-layer embeddings and classifiers. The majority of this workfocuses on cross-entropy and its different parameterizations that are empirically knownto boost the performance of deep-nets in imbalanced setups. Our analysis is based oncharacterizing the optimal geometry of classifiers and embeddings for the UFM. We showthat despite the non-convexity of this model, UFM has a unique optimizer (up to a rotation).Inspecting the geometric properties of the optimal solutions, UFM reveals the impact oflabel-imbalances on the optimal geometry and explains how the model becomes less fairtowards the minoirties with increasing imbalances. Additionally, it provides insights onhow introducing hyper-parameters for adjusting the logits in the loss function gives us theflexibility in engineering the geometry at the training stage and modifying the bias to favorminorities.65UFM provides a theoretically simple framework to build insights from complicated over-parameterized models. Not surprisingly, this simplification comes with several limitations.Specifically, the strong assumption made in the UFM, i.e., over-parameterized models canlearn unconstrained features, makes it incapable of addressing certain problems:Task complexity. As stated earlier, UFM relaxes the dependence of the learned embed-dings from the data distribution by assuming over-parameterizes models are expressiveenough to model any function from the input space to the embedding space. As a result,this model is agnostic to the distribution of the training samples and, equivalently, the taskcomplexity. From another point of view, this model can only describe what deep-nets learnin the asymptotic regime. Thus, the impact of task complexity, on the training dynamicsremains unexplained in this setting. For instance, it has been shown that deep-nets can fitdatasets with random labels. However, the training time grows linearly for cross-entropy[52], and super-linearly for supervised contrastive loss [11]. While UFM discovers the opti-mal geometry learned in this setup, it does not explain how the training is impacted by thedistribution of the training set.Group-imbalances. Relevant to the previous issue, it is empirically known that over-parameterized models are senstitive to spurious information in the training set, especiallywhen there are sub-groups within a class that are under-represented in the training set[e.g., 40]. The implicit bias results on linear models provide similar insights in the group-imbalanced scenario: (weighted) cross-entropy fails under over-parameterization, while withmultiplicative hyper-parameters we can learn models that predict more accurately on mi-nority groups [2]. Again, beyond linear models, the analysis of group-imbalanced setup istheoretically complicated. Since UFM is agnostic to the training distribution, it cannotaddress this issue in the current format of the model.Generalization. To evaluate and compare different training strategies, we need to havean understanding of what deep-nets learn from unseen test samples. UFM only describeslearning at the training stage. In fact, this model does not support a notion of general-ization as in the analysis, we decouple learning from the input feature vectors x ∈ Rd andonly capture the distribution of the labels y ∈ [k] in the training set. This is one of themost compelling unanswered question in the Neural-collapse literature. While some initialinvestigations appear in the recent works [10, 13, 16], we expect more investigations in thisdirection to follow.66Centering heuristic. UFM overlooks the role of several essential components in the deep-nets, such as non-linear activation functions or normalization layers. In many architectures,these components, in fact, enforce explicit constraints on the type of embeddings a networkcan learn. This mismatch between the UFM and deep-nets can be thought as a justificationfor the common centering heuristic in the UFM literature. More importantly, this mismatchhighlights the shortcomings of the model and the need for devising more accurate, buttractable, models.Optimization concerns. Through our deep-net experiments, we observed that the train-ing setup, such as the value of the imbalance ratio or the loss hyper-parameters, can severelyimpact the convergence to the theoretical prediction by UFM. Whether the poor conver-gence stems mainly from a harder optimization landscape or the inaccuracy of the modelis not well-explored yet. We observe this slower convergence in the UFM experiments aswell (see Figure 3.1). Furthermore, by Theorem 1, we only show GD on UFM convergesto a KKT point of the non-convex SVM [17, 32], which are not necessarily global minima.Based on our experiments, we conjecture that GD leads to global solutions, i.e., the SELIgeometry, asymptotically in the number of epochs. However, the conjecture remains to befurther investigated.The current practice of deep learning involves many successful heuristics whose impacton the models cannot be fully explained. While we acknowledge the shortcomings of UFMfor fully describing the dynamics of deep-nets, it is equally important to realize that theinsights provided by this simple model is non-trivial. We envision that such studies can leadto more computationally efficient and principled algorithmic designs in imbalanced deep-learning as they can facilitate studying the implicit-bias of the common training algorithms.67Bibliography[1] P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler. Benign overfitting in linearregression. Proceedings of the National Academy of Sciences, 117(48):30063–30070,2020.[2] T. Behnia, K. Wang, and C. Thrampoulidis. On how to avoid exacerbating spuriouscorrelations when models are overparameterized. In 2022 IEEE International Sympo-sium on Information Theory (ISIT), pages 121–126. IEEE, 2022.[3] M. Belkin, S. Ma, and S. Mandal. To understand deep learning we need to understandkernel learning. In International Conference on Machine Learning, pages 541–549,2018.[4] M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learningpractice and the classical bias–variance trade-off. Proceedings of the National Academyof Sciences, 116(32):15849–15854, 2019.[5] D. P. Bertsekas. Nonlinear programming. 1999.[6] J. Byrd and Z. Lipton. What is the effect of importance weighting in deep learning?In International Conference on Machine Learning, pages 872–881. PMLR, 2019.[7] K. Cao, C. Wei, A. Gaidon, N. Arechiga, and T. Ma. Learning imbalanced datasets withlabel-distribution-aware margin loss. In Advances in Neural Information ProcessingSystems, pages 1567–1578, 2019.[8] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. A simple framework for contrastivelearning of visual representations. In International conference on machine learning,pages 1597–1607. PMLR, 2020.68[9] C. Fang, H. He, Q. Long, and W. J. Su. Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training. Proceedings of the NationalAcademy of Sciences, 118(43), 2021.[10] T. Galanti, A. Gyo¨rgy, and M. Hutter. On the role of neural collapse in transferlearning. arXiv preprint arXiv:2112.15121, 2021.[11] F. Graf, C. Hofer, M. Niethammer, and R. Kwitt. Dissecting supervised constrastivelearning. In International Conference on Machine Learning, pages 3821–3830. PMLR,2021.[12] B. Gunel, J. Du, A. Conneau, and V. Stoyanov. Supervised contrastive learning forpre-trained language model fine-tuning. arXiv preprint arXiv:2011.01403, 2020.[13] X. Han, V. Papyan, and D. L. Donoho. Neural collapse under mse loss: Proximity toand dynamics on the central path. In International Conference on Learning Represen-tations, 2021.[14] T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensionalridgeless least squares interpolation. arXiv preprint arXiv:1903.08560, 2019.[15] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. InProceedings of the IEEE conference on computer vision and pattern recognition, pages770–778, 2016.[16] L. Hui, M. Belkin, and P. Nakkiran. Limitations of neural collapse for understandinggeneralization in deep learning. arXiv preprint arXiv:2202.08384, 2022.[17] W. Ji, Y. Lu, Y. Zhang, Z. Deng, and W. J. Su. An unconstrained layer-peeledperspective on neural collapse. arXiv preprint arXiv:2110.02796, 2021.[18] Z. Ji and M. Telgarsky. Risk and parameter convergence of logistic regression. arXivpreprint arXiv:1803.07300, 2018.[19] Z. Ji and M. Telgarsky. Directional convergence and alignment in deep learning. Ad-vances in Neural Information Processing Systems, 33:17176–17186, 2020.[20] W. Jitkrittum, A. K. Menon, A. S. Rawat, and S. Kumar. Elm: Embedding and logitmargins for long-tail learning. arXiv preprint arXiv:2204.13208, 2022.69[21] B. Kang, S. Xie, M. Rohrbach, Z. Yan, A. Gordo, J. Feng, and Y. Kalantidis. Decou-pling representation and classifier for long-tailed recognition, 2020.[22] B. Kang, Y. Li, S. Xie, Z. Yuan, and J. Feng. Exploring balanced feature spacesfor representation learning. In International Conference on Learning Representations,2021.[23] S. H. Khan, M. Hayat, M. Bennamoun, F. A. Sohel, and R. Togneri. Cost-sensitivelearning of deep feature representations from imbalanced data. IEEE transactions onneural networks and learning systems, 29(8):3573–3587, 2017.[24] P. Khosla, P. Teterwak, C. Wang, A. Sarna, Y. Tian, P. Isola, A. Maschinot, C. Liu,and D. Krishnan. Supervised contrastive learning. Advances in neural informationprocessing systems, 33:18661–18673, 2020.[25] B. Kim and J. Kim. Adjusting decision boundary for class imbalanced learning. IEEEAccess, 8:81674–81685, 2020. doi: 10.1109/ACCESS.2020.2991231.[26] G. R. Kini, O. Paraskevas, S. Oymak, and C. Thrampoulidis. Label-imbalanced andgroup-sensitive classification under overparameterization. Advances in Neural Infor-mation Processing Systems, 34:18970–18983, 2021.[27] M. Li, X. Zhang, C. Thrampoulidis, J. Chen, and S. Oymak. Autobalance: Opti-mized loss functions for imbalanced data. Advances in Neural Information ProcessingSystems, 34:3163–3177, 2021.[28] T. Li, P. Cao, Y. Yuan, L. Fan, Y. Yang, R. S. Feris, P. Indyk, and D. Katabi.Targeted supervised contrastive learning for long-tailed recognition. In Proceedingsof the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages6918–6928, 2022.[29] T. Liang and A. Rakhlin. Just interpolate: Kernel” ridgeless” regression can generalize.arXiv preprint arXiv:1808.00387, 2018.[30] T.-Y. Lin, P. Goyal, R. Girshick, K. He, and P. Dolla´r. Focal loss for dense objectdetection, 2018.[31] J. Lu and S. Steinerberger. Neural collapse with cross-entropy loss. arXiv preprintarXiv:2012.08465, 2020.70[32] K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neuralnetworks. arXiv preprint arXiv:1906.05890, 2019.[33] S. Mei and A. Montanari. The generalization error of random features regression:Precise asymptotics and double descent curve. arXiv preprint arXiv:1908.05355, 2019.[34] A. K. Menon, S. Jayasumana, A. S. Rawat, H. Jain, A. Veit, and S. Kumar. Long-taillearning via logit adjustment. arXiv preprint arXiv:2007.07314, 2020.[35] D. G. Mixon, H. Parshall, and J. Pi. Neural collapse with unconstrained features.arXiv preprint arXiv:2011.11619, 2020.[36] P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, and I. Sutskever. Deep doubledescent: Where bigger models and more data hurt. arXiv preprint arXiv:1912.02292,2019.[37] J. Nocedal and S. J. Wright. Numerical optimization. Springer, 1999.[38] V. Papyan, X. Han, and D. L. Donoho. Prevalence of neural collapse during the terminalphase of deep learning training. Proceedings of the National Academy of Sciences, 117(40):24652–24663, 2020.[39] S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang. Distributionally robust neuralnetworks for group shifts: On the importance of regularization for worst-case general-ization. arXiv preprint arXiv:1911.08731, 2019.[40] S. Sagawa, A. Raghunathan, P. W. Koh, and P. Liang. An investigation of why over-parameterization exacerbates spurious correlations. In International Conference onMachine Learning, pages 8346–8356. PMLR, 2020.[41] D. Samuel and G. Chechik. Distributional robustness loss for long-tail learning. InProceedings of the IEEE/CVF International Conference on Computer Vision, pages9495–9504, 2021.[42] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale imagerecognition. arXiv preprint arXiv:1409.1556, 2014.[43] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit biasof gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822–2878, 2018.71[44] C. Thrampoulidis, G. R. Kini, V. Vakilian, and T. Behnia. Imbalance trouble: Revis-iting neural-collapse geometry. arXiv preprint arXiv:2208.05512, 2022.[45] Y. Tian, D. Krishnan, and P. Isola. Contrastive multiview coding. arxiv. arXiv preprintarXiv:1906.05849, 2019.[46] T. Tirer and J. Bruna. Extended unconstrained features model for exploring deepneural collapse. arXiv preprint arXiv:2202.08087, 2022.[47] G. Vardi, O. Shamir, and N. Srebro. On margin maximization in linear and relunetworks. arXiv preprint arXiv:2110.02732, 2021.[48] T. Wang and P. Isola. Understanding contrastive representation learning throughalignment and uniformity on the hypersphere. In International Conference on MachineLearning, pages 9929–9939. PMLR, 2020.[49] L. Xie, Y. Yang, D. Cai, D. Tao, and X. He. Neural collapse inspired attraction-repulsion-balanced loss for imbalanced learning. arXiv preprint arXiv:2204.08735,2022.[50] C. Yaras, P. Wang, Z. Zhu, L. Balzano, and Q. Qu. Neural collapse with normal-ized features: A geometric analysis over the riemannian manifold. arXiv preprintarXiv:2209.09211, 2022.[51] H.-J. Ye, H.-Y. Chen, D.-C. Zhan, and W.-L. Chao. Identifying and compensating forfeature deviation in imbalanced deep learning, 2020.[52] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learningrequires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.[53] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning(still) requires rethinking generalization. Communications of the ACM, 64(3):107–115,2021.[54] J. Zhou, X. Li, T. Ding, C. You, Q. Qu, and Z. Zhu. On the optimization landscape ofneural collapse under mse loss: Global optimality with unconstrained features. arXivpreprint arXiv:2203.01238, 2022.72[55] J. Zhou, C. You, X. Li, K. Liu, S. Liu, Q. Qu, and Z. Zhu. Are all losses created equal:A neural collapse perspective. arXiv preprint arXiv:2210.02192, 2022.[56] Z. Zhu, T. Ding, J. Zhou, X. Li, C. You, J. Sulam, and Q. Qu. A geometric anal-ysis of neural collapse with unconstrained features. Advances in Neural InformationProcessing Systems, 34, 2021.73Appendix AProperties of the SEL MatrixA.1 Eigen-Structure of the (δ, R)-SEL MatrixIn this section, we compute the eigen-structure of (δ, R)-SEL matrix Ẑ (Definition 7). Asindicated in Definition 4, we consider the first ρk classes to represent the majority withnmaj = Rnminor, while the remaining ρk classes are the minority classes with number ofsamples nminor. From Remark 1, it only suffices to do the calculations for nminor = 1. Forgeneral nminor, the eigen-factors can be derived by applying the proper scaling. Furtherrecall form (2.5) that we assume δ shares the same STEP pattern as the class sizes. Forsimplicity, we let δminor = 1 and δmaj = ∆. Thus,∀c ∈ {1, · · · , ρk}, δc = ∆, ∀c ∈ {ρk + 1, · · · , k}, δc = 1.For m ∈ [k], define Pm ∈ Rm×(m−1) as an orthonormal basis of the subspace orthogonalto 1m, i.e., PmP⊤m = Im − 1m1m1⊤m and P⊤mPm = Im−1, and Sm(σ) := Im − σ1m1⊤m ∈ Rm.Finally, recall that we define the SVD factors U, Λ, V of Ẑ such that,Ẑ = VΛ[U⊤1:ρk⊗1⊤R U⊤(ρk+1):k]= VΛU⊤⊗. (A.1)With these notations, we express the properties of the SEL matrix.Lemma A.1.1 (SVD of (δ, R)-SEL matrix). Let Ẑ ∈ Rk×n be the (δ, R)-SEL matrixdescribed in Definition 7, with the SVD factors U, Λ and V as in (A.1). Further let74q := ρ+ ρ∆2 and r := ρ+ ρR. Then, the SVD factors are given by,Λ = diag([√R∆ 1⊤(ρk−1)√rq 1⊤(ρk−1)]),V =[Pρk −∆√ρ/(ρkq)1ρk 00√ρ/(ρkq)1ρk Pρk],U =[1√RPρk −√ρ/(ρkr)1ρk 00√ρ/(ρkr)1ρk Pρk].Proof. To prove the lemma, we only need to verify the correctness of the formulas. Inparticular: (i) U⊗ and V are unitary matrices, and (ii) VΛU⊤⊗ = Ẑ. By recalling thatP⊤mPm = Im−1 and P⊤m1m = 0 for m ∈ {ρk, ρk}, it is easy to confirm V⊤V = Ik−1 andU⊤⊗U⊗ = Ik−1. For the second part, as U⊗ and Ẑ have repeated columns, it is suffices toshow VΛU⊤ = Ξ where Ξ ∈ Rk×k is such that ∀ c, i ∈ [k],Ξc,i =δ−1c(1− δ−2c /∑c′∈[k] δ−2c′), c = i−δ−1c(δ−2i /∑c′∈[k] δ−2c′), c ̸= i.We start by expressing Ξ in block-form as follows:Ξ =[1∆Sρk(1kq) −∆kq1ρk1⊤ρk− 1kq1ρk1⊤ρk Sρk(∆2kq) ] . (A.2)Define Vmaj, Umaj ∈ Rk×(ρk−1), v, u ∈ Rk, Vmaj, Umaj ∈ Rk×(ρk−1) such that V =[Vmaj,v,Vminor] and U = [Umaj,u,Uminor]. We verify the equation by direct calculations:VΛU⊤ =√R∆VmajU⊤maj +√rqvu⊤ +VminorU⊤minor=[1∆PρkP⊤ρk 00 0]+1kq[∆ρρ1ρk1⊤ρk −∆1ρk1⊤ρk−1ρk1⊤ρk ρρ1ρk1⊤ρk]+[0 00 PρkP⊤ρk]=[1∆(Iρk − 1kq1ρk1⊤ρk) −∆kq1ρk1⊤ρk− 1kq1ρk1⊤ρk Iρk − ∆2kq 1ρk1⊤ρk]= Ξ.75With the eigen-structure of Ẑ at hand, we prove a useful property of the singular spacein Lemma A.1.2. We will use this property later in Section C.2 to characterize the globalsolutions of the CS-SVMs (2.6).Lemma A.1.2. Recall the setting of Lemma A.1.1 and the SVD Ẑ = VΛU⊤⊗. The matrixB∗ := U⊗V⊤ satisfies the following element-wise strict inequalities: B∗ ⊙ Ẑ⊤ > 0.Proof. Since both B∗ and Ẑ⊤ have repeated rows, it is enough to prove the inequality fortheir k distinct rows. Define B := UV⊤, where U is defined as in (A.1), and recall Ξ from(A.2). We compute B by plugging in the explicit SVD expressions from Lemma A.1.1.UV⊤ =[1√RPρkP⊤ρk 00 0]+1k√rq[∆ρρ1ρk1⊤ρk −1ρk1⊤ρk−∆1ρk1⊤ρk ρρ1ρk1⊤ρk]+[0 00 PρkP⊤ρk].Simplifying the expressions, for B =[B11 B12B21 B22], we have,B11 =1√R(Iρk − 1ρk(1− ρ∆√Rrq)1ρk1ρk),B12 = − 1k√r√ρ+ ρ∆21ρk1⊤ρk ,B21 = − ∆k√r√ρ+ ρ∆21ρk1⊤ρk ,B22 = Iρk − 1ρk1−√ρ2rq1ρk1⊤ρk.Comparing with Ξ from (A.2), the signs of the off-diagonal blocks of both Ξ and B arenegative. To inspect the sign agreement of the on-diagonal blocks, it is enough to see thefollowing inequalities are always strictly satisfied,1 > 1− ρ∆√Rrq> 0 and 1 > 1−√ρ2rq> 0.76Appendix BProperties of the SELI GeometryIn a STEP imbalanced setting, let k be the number of classes and ρ be the minority fraction.Suppose Ẑ is the (δ, R)-SELI matrix. Recall from Definition 8, that given the label encodingmatrix Ẑ, we say (W,H) follows the (δ, R)-SELI geometry if the embeddings H collapseto their class-means M, and(i) W⊤W ∝ τVΛV⊤, (ii) M⊤M ∝ 1τUΛU⊤, (iii) W⊤M ∝ V⊤ΛU, (B.1)where U,Λ,V are the SVD factors of Ẑ as defined in (A.1), and τ is a scalar. In this ge-ometry characterization, the Gram matrices of the embeddings and classifiers are expressedin terms of the SVD factors of the corresponding label-encoding matrix Ẑ. In Appendix A,we expressed the SVD factors of the (δ, R)-SEL matrix in closed-form. This allows us toderive analytical formulas for the properties of the SELI geometry.For simplicity, here we assume ρ = 1/2. In the same manner, we can derive the formulasfor general value of ρ ∈ (0, 1). Similar to Section A, we choose δminor = 1 and δmaj = ∆. Thischoice is without loss of generality since the geometry only depends on the ratio δmaj/δminor.Furthermore, we assume the proportionality constant and τ in (B.1) are equal to one. Thisis because these parameters solely affect the scale of the geometry. In this chapter, weuse wmaj when referring to any majority classifier wc, c ∈ {1, . . . , k/2}, and wminor for anyminority classifier wc, c ∈ {k/2 + 1, . . . , k}. Similarly, hmaj denotes any hj with j ∈ {i ∈[n] : yi = 1, . . . , k/2} and hminor denotes any hj with j ∈ {i ∈ [n] : yi = k/2 + 1, . . . , k}.B.1 Geometric Properties Induced by CDTBy Theorem 2, the global solution of the CS-SVM (2.6b) follows the SELI geometry with(δ, R)-SEL as the label encoding matrix. In the rest of this section, we assume W, H arethe optimal classifiers and embeddings in (2.6b), and specify their geometric properties.77Remark 2 (Implicit geometry of CE). Recall that by setting δ = 1k, CDT reduces to theCE loss. Thus, with this specific choice of δ, we can derive the geometric properties inducedby the CE loss. In other words, Lemmas 3.3.1 and 3.3.2 can be derived by setting ∆ = 1 in(B.2), (B.3) and (B.4).B.1.1 Norms and AnglesLemma B.1.1 (CDT classifiers). For the optimal classifier W of the CS-SVM (2.6b):(i) (Norms) The classifier norms across all majority/minority classes are all the sameand,∥wmaj∥22 =√R∆(1− 2k)+2∆2√R+ 1k(√1 + ∆2)3 ,∥wminor∥22 =(1− 2k)+2√R+ 1k(√1 + ∆2)3 .For the majority-minority norm-ratio, it holds that,∥wmaj∥22∥wminor∥22=√R∆ (k − 2)(1 + ∆2)3/2+ 2∆2√R+ 1(k − 2)(1 + ∆2)3/2 + 2√R+ 1 . (B.2)(ii) (Angles) For each pair of majority/minority classifiers the angles are equal and,Cos(wmaj,w′maj) =−2√R+ 2√R+ 1(√1 + ∆−2)−3(k − 2)√R+ 2√R+ 1(√1 + ∆−2)−3 (B.3)Cos(wminor,w′minor) =−2 + 2√R+ 1(√1 + ∆2)−3k − 2 + 2√R+ 1(√1 + ∆2)−3Cos(wmaj,wminor) = − 2∆√R+ 1k(√1 + ∆2)3 ∥wmaj∥2∥wminor∥2 .Proof. Let m = k/2. From Theorem 2, W⊤W = VΛV⊤. Adopting the same notation as78Lemma A.1.1, define r := (R+ 1)/2 and q := (1 + ∆2)/2. We have,VΛV⊤ =√R∆[PmP⊤m 00 0]+2√2rk(√2q)3[∆21m1⊤m −∆1m1⊤m−∆1m1⊤m 1m1⊤m]+[0 00 PmP⊤m]=√R∆ Ik/2 − 2k (√R∆ − ∆2√2r(√2q)3)1k/21⊤k/2 − 2∆√2rk(√2q)31k/21⊤k/2− 2∆√2rk(√2q)31k/21⊤k/2 Ik/2 − 2k(1−√2r(√2q)3)1k/21⊤k/2 .Inspecting the diagonal entries proves the norm equations. To prove the second part,we use the off-diagonals entries that specify the inner-product of each pair of classifiers.Particularly,w⊤majw′maj =−2√R+ 2√R+ 1(√∆−2 + 1)−3k∆,w⊤minorw′minor =−2 + 2√R+ 1(√1 + ∆2)−3k,w⊤minorwmaj =−2∆√R+ 1k(√∆2 + 1)3 .Combining these equations with the value of norms from the first part completes the proof.Lemma B.1.2 (CDT embeddings). Let H be the optimal embeddings of the CS-SVM(2.6b). Then,(i) (Norms) All the embeddings in the majority/minority classes have equal norms,∥hmaj∥22 =(1− 2/k)∆√R+2k√R+ 1√1 + ∆2,∥hminor∥22 = (1− 2/k) +2k√R+ 1√1 + ∆2,and the majority-minority norm-ratio is as follows,∥hmaj∥22∥hminor∥22=1∆√R(k − 2)√R+ 1√1 + ∆2 + 2(k − 2)√R+ 1√1 + ∆2 + 2 . (B.4)79(ii) (Angles) For each pair of majority/minority embeddings the angles are equal, and,Cos(hmaj,h′maj) =−2√∆−2 + 1√R+ 1 + 2√R(k − 2)√∆−2 + 1√R+ 1 + 2√RCos(hminor,h′minor) =−2√∆2 + 1√R+ 1 + 2(k − 2)√∆2 + 1√R+ 1 + 2Cos(hmaj,hminor) =−2k√∆2 + 1√R+ 1 ∥hmaj∥2∥hminor∥2.Proof. By the NC property, to find the norms and angles of the embeddings, it suffices toanalyze the mean-embeddings M. Following Theorem 2, we have M⊤M = UΛU⊤. ByLemma A.1.1, defining r := (R+ 1)/2 and q := (∆2 + 1)/2,UΛU⊤ =√R∆[1RPmP⊤m 00 0]+1k√rq[1m1⊤m −1m1⊤m−1m1⊤m 1m1⊤m]+[0 00 PmP⊤m]=( 1∆√RIk/2 − 2k ( 1∆√R − 12√rq)1k/21⊤k/2) − 1k√rq1k/21⊤k/2− 1k√rq1k/21⊤k/2 Ik/2 − 2k(1− 12√rq)1k/21⊤k/2 .The diagonal entries determine the norm of the embeddings as in part (i) and theoff-diagonals entries specify the inner-product of each pair of the embeddings. Particularly,h⊤majh′maj = −2k(1∆√R− 1√R+ 1√∆2 + 1),h⊤minorh′minor = −2k(1− 1√R+ 1√∆2 + 1),h⊤minorhmaj = −2k√R+ 1√∆2 + 1.Combining these with the norm calculations of part (i) completes the proof.In the next lemma, we calculate the angles between an embedding and its correspondingclassifier. Particularly, we give closed-form expression for Cos(wc,hi) for c ∈ [k], i : yi = c,which can be thought of the degree of alignment between classifiers and embeddings. Thecase Cos(wc,hi) = 1 corresponds to exact alignment between the W and H.Lemma B.1.3 (Alignment of classifiers and embeddings). Let H and W be the optimalembeddings and classifiers in (2.6b). The angles between majority/minority embeddings and80their corresponding classifiers are all equal:Cos(wmaj,hmaj) =k∆2 + (k − 2)k∆(∆2 + 1) ∥wmaj∥2∥hmaj∥2 ,Cos(wminor,hminor) =k∆−2 + (k − 2)k (∆−2 + 1) ∥wminor∥2∥hminor∥2 .Proof. The proof is immediate by recognizing under the SELI geometry,W⊤H = Ẑ. Then,for all c ∈ [k] and i : yi = c it holds that,w⊤c hi =∆−1(1− 2k(∆2+1)), if c a majority class,(1− 2k(∆−2+1)), if c a minority class.B.1.2 AsymptoticsWe present the limiting values of the angles in the asymptotic regime ∆ = Rγ , γ ∈ R andR → ∞. This parameterization is interesting because it can guide us on how to maintainfinite non-zero angles between classifiers and embeddings as the imbalance ratio grows large.Specifically, the angles are as shown in Table B.1.cos(wc,w′c) γ < 1/6 γ = 1/6 γ > 1/6c, c′ ∈ minority 1 0 − 2k−2cos(wc,w′c) γ < 0 γ = 0 γ > 0c, c′ ∈ majority − 2k−2 1−2√21+√2(k−2) 0cos(hc,h′c) γ < 0 γ = 0 γ > 0c, c′ ∈ minority 0 − 2k−2 − 2k−2c, c′ ∈ majority 0 2−2√22+(k−2)√2 −2k−2Table B.1: Asymptotic values of angles for CDT with ∆ = Rγ , γ ∈ R and R→∞.B.1.3 CenteringAssuming that the classifiers follow the geometry in Theorem 2, wc, c ∈ [k] are cen-tered around zero after some re-weighting, i.e.,∑c∈[k]wc/δc = 0. This is immediate from81VTD−11k = 0 and WTW = VΛVT .The embeddings hi, i ∈ [n] are also not centered around zero in general. Instead, it holdsthat ∑i∈[n]1nyihi = 0. (B.5)Note that this reduces to∑i∈[n] hi for balanced data, and remains unchanged for anychoice of the hyperparameters δ. Equation (B.5) is also equivalent to∑c∈[k]µc = 0, withµc, c ∈ [k] the mean embeddings of each class.B.2 Geometric Properties Induced by LDTB.2.1 Norms and AnglesFrom Theorem 3, solutions (W,MD), D = diag(δ) of the CS-SVM under LDT loss in(2.6c), follow the (δ = 1k, R˜)-SELI geometry, with imbalance ratio R˜ = R(δminor/δmaj)2.Thus, the corresponding geometric properties can be found (up to a norm scaling by D forthe mean-embeddings M) by choosing δ = 1k and R = R˜ in the expressions of SectionB.1. We repeat some key formulas below for showing their explicit dependence on ∆ :=δmaj/δminor.Corollary 9 (LDT: Norm ratios and classifier angles). For the optimal solution (W,H) ofthe CS-SVM (2.6c):∥wmaj∥22∥wminor∥22=(k − 2)√R+√(R+∆2)/2(k − 2)∆ +√(R+∆2)/2 ,∥hmaj∥22∥hminor∥22=1√R(k − 2) + 1√(R+∆2)/2(k − 2)∆ + ∆2√(R+∆2)/2,cos(wmaj,w′maj) =−2√R+√(R+∆2)/2(k − 2)√R+√(R+∆2)/2 ,cos(wmin,w′min) =−2∆ +√(R+∆2)/2(k − 2)∆ +√(R+∆2)/2 .82B.2.2 AsymptoticsSimilar to the calculations for the CDT case, we present the limiting values of angles in theasymptotic regime ∆ = Rγ , γ ∈ R and R→∞. Then, the angles are as given in Table B.2:cos(wc,w′c) γ < 1/2 γ = 1/2 γ > 1/2c, c′ ∈ minority 1 − 1k−1 1−2√21+√2(k−2)c, c′ ∈ majority 1−2√21+√2(k−2) −1k−1 1cos(hc,h′c) γ < 1/2 γ = 1/2 γ > 1/2c, c′ ∈ minority − 2k−2 − 1k−1 2−2√22+√2(k−2)c, c′ ∈ majority −√2−√2+k(1+√2) −1k−1 − 2k−2Table B.2: Asymptotic values of angles for LDT with ∆ = Rγ , γ ∈ R and R→∞.B.2.3 CenteringThe optimal classifiers and features (W,MD) follow the(1k, R˜ := R(δminor/δmaj)2)-SELIstructure. Thus, from Section B.1.3, the classifiers wc, c ∈ [k] are centered around zero.However the embeddings are centered around zero after a re-weighting that depends bothon δc and nc, c ∈ [k]. Specifically,∑c∈[k] δcµc = 0, or equivalently,∑i∈[n]δyinyihi = 0. (B.6)83Appendix CProofs of Chapter 2C.1 Proof of Lemma 2.1.1Let WCDT, WLDT ∈ Rd×2 denote the CDT and LDT classifiers respectively. The corre-sponding classification rules is: (w1 − w2)⊤xyˆ(W)=1≷yˆ(W)=20 for W =[w1,w2]either WCDTor WLDT, respectively. On the other hand, the CE or binary VS loss decision rule isx⊤w∗υˆ(w∗)=1≷υˆ(w∗)=−10, where w∗ denotes a minimizer of either the CE or the binary VS loss.Here, we use υ ∈ {±1} to denote the label encoding for binary CE loss, differentiating fromthe multiclass encoding y ∈ {1, 2} above. From the above two, we conclude that w⋆ =α(w1 −w2), α > 0 implies yˆ(W) = 1⇐⇒ υˆ(w∗) = 1 (eqv. yˆ(W) = 2⇐⇒ υˆ(w∗) = −1).Since we minimize all losses without regularization and the data are separable, it sufficesby implicit bias [26, 43] to consider the solutions to the corresponding max-margin problems,WCDT := argminW∥W∥2F subj. to (δyiwyi − δcwc)⊤hi ≥ 1, c ̸= yi (C.1a)WLDT := argminW∥W∥2F subj. to δyi(wyi −wc)⊤hi ≥ 1, c ̸= yi (C.1b)wCE,binary⋆ := argminw∥w∥22 subj. to υiw⊤⋆ hi ≥ 1, (C.1c)wVS,binary⋆ := argminw∥w∥22 subj. to υiδυiw⊤⋆ hi ≥ 1, (C.1d)First, we show yˆ(WLDT) = 1⇐⇒ υˆ(wVS,binary∗ ) = 1 provided that the LDT and VS lossparameters are matching, i.e., δLDT1 = δVS,binary1 and δLDT2 = δVS,binary−1 . This follows fromthe fact that wLDT1 +wLDT2 = 0 (see Lemma C.1.1). Thus, the minimization in (C.1b) doesnot change by adding the constraint w2 = −w1. But then, the solution set of (C.1b) is the84same as the solution set of the minimizationminw1∥w1∥2 subj. to2δ1w⊤1 hi ≥ 1 i : yi = 1−2δ2w⊤1 hi ≥ 1 i : yi = 2 .Comparing this to (C.1d), it follows immediately that wLDT1 = wVS,binary⋆ /2. Hence, wLDT1 −wLDT2 = wVS,binary⋆ , which proves the desired.Second, we show that yˆ(WCDT) = yˆ(wCE∗ ). This is a consequence of the fact thatδ−11 wCDT1 + δ−12 wCDT2 = 0 (see Lemma C.1.1). Indeed, we then have that the solution set of(C.1a) does not change by adding the constraint w2 = −(δ2/δ1)w1. But then, optimizationis equivalent to:minw1∥w1∥2 subj. to(δ1w1 − δ2w2)⊤hi = (δ1 + δ22/δ1)w⊤1 hi ≥ 1 i : yi = 1(δ2w2 − δ1w1)⊤hi = −(δ1 + δ22/δ1)w⊤1 hi ≥ 1 i : yi = 2 .Comparing this to (C.1c), we find that wCDT1 =δ1δ21+δ22wCE,binary⋆ . Thus also, wCDT2 =− δ2δ21+δ22wCE,binary⋆ . In conclusion, wCDT1 −wCDT2 = δ1+δ2δ21+δ22wCE,binary⋆ , from which the desiredfollows since δ1, δ2 > 0.Lemma C.1.1. For the CDT/LDT-SVM classifiers WCDT,WLDT defined in (C.1b) and(C.1a), it holds that wLDT1 +wLDT2 = 0 and δ−11 wCDT1 + δ−12 wCDT1 = 0.Proof. We prove the claim for CDT. The proof for LDT is the same and is omitted forbrevity. We use a symmetrization argument as follows. Setw¯ := (δ−11 wCDT1 + δ−12 wCDT2 )/(δ−21 + δ−22 ),and assume for the sake of contradiction that w¯ ̸= 0. Consider a new classifier definedas w˜1 = wCDT1 − δ−11 w¯ and w˜2 = wCDT2 − δ−12 w¯. Clearly, it holds that δ1w˜1 − δ2w˜2 =δ1wCDT1 − δ2wCDT2 . Thus, [w˜1, w˜2] is feasible in (C.1b). Moreover,∥w˜1∥22 + ∥w˜2∥22 = ∥wCDT1 ∥22 + ∥wCDT2 ∥22 − (δ−21 + δ−22 )∥w¯∥2 < ∥wCDT1 ∥22 + ∥wCDT2 ∥22.But, these together contradict the optimality of WCDT.85C.2 Proof of Theorems: Implicit Geometry of the VS LossIn Chapter 2, we outlined the implicit geometries of CE (Theorem 1), CDT (Theorem 2)and LDT loss (Theorem 3), as special cases of the VS loss. In this section, we discuss theproof of Theorem 2 for CDT loss. This theorem provides a central result that can be usedfor deriving Theorems 1 and 3 as well. Theorem 1 follows by selecting δ = 1k, by whichCDT reduces to the CE loss. Theorem 3 can be proved by a re-parameterization of theCS-SVM corresponding to LDT (2.6c) such that it reduces to a weighted version of (2.6a)corresponding to the CE loss. We discussed this re-parameterization in Section 2.4.2.At a high level, the key step in our proof for CDT relies on expressing the dual of theCS-SVM corresponding to CDT (2.6b) in a form that involves the (δ,R)-SEL and showingthat it admits an explicit solution.Proof of Theorem 2Consider the CS-SVM of (2.6b):p∗ = minW,H12∥W∥2F +12∥H∥2F sub. to (δyiwyi − δcwc)⊤hi ≥ 1, i ∈ [n], c ̸= yi, (C.2)with (W∗,H∗) as an optimal solution. We start by settingX =[W⊤H⊤] [W H]=[W⊤W W⊤HH⊤W H⊤H]∈ R(k+n)×(k+n),and formulating the convex-relaxation of (C.2) as follows,q∗ = minX⪰012tr(X)(C.3)sub. to δyiXyi,(k+i) − δcXc,(k+i) ≥ 1, ∀i ∈ [n], c ̸= yi.Clearly, p∗ ≥ q∗. We will characterize the optimal set of the semi-definite program (C.3)and use this to show that the relaxation is in fact tight. This allows us to find the globalsolutions of the original problem. The problem in (C.3) is convex and satisfies the Slater’sconditions. Hence, the strong duality holds and KKT conditions are necessary and sufficientfor optimality. Thus, we will formulate the dual problem of (C.3) next.86Dual of Problem (C.3)We can find the dual of (C.3) as follows,d∗ = max{βi,c}i∈[n],c̸=yi∑i∈[n]∑c ̸=yiβic (C.4)sub. to[Ik −B⊤−B In]⪰ 0βic ≥ 0, i ∈ [n], c ̸= yi, ∀i ∈ [n] : Bi,c =∑c′ ̸=yi δyiβic′ , yi = c,−δcβic, yi ̸= c.Also, the complementary slackness conditions are∀i ∈ [n], c ̸= yi : Bi,c(1− δyiXyi,(k+i) + δcXc,(k+i)) = 0 (C.5)[Ik −B⊤−B In]X = 0.Our key insight in the analysis of (C.3) is writing its dual in a way that explicitly involvesthe (δ, R)-SEL matrix Ẑ from Definition 7. Specifically, we can rewrite the dual in thefollowing more convenient form.d∗ = maxB∈Rn×ktr(ẐB) (C.6)sub. to[Id −B⊤−B In]⪰ 1BD−11k = 0B⊙ Ẑ⊤ ≥ 0 , (C.7)where D = diag (δ) ∈ Rk×k. To see the equivalence, define αi := δ−2yi /(∑c′∈[k] δ−2c′)andobserve that,∑c ̸=yiβi,c =1δyiBi,yi = −∑c ̸=yi1δcBi,c = (1− αi) 1δyiBi,yi − αi∑c ̸=yi1δcBi,c= Ẑyi,iBi,yi +∑c ̸=yiẐc,iBi,c.87We will characterize the optimal solutions of (C.6) next.Solutions of the Dual Problem (C.6)To solve (C.6), we first relax the problem by ignoring the constraint (C.7), and substitutingthe first constraint using Schur-complement argument:maxBn×ktr(ẐB) sub. to ∥B∥2 ≤ 1, BD−11k = 0, (C.8)where ∥B∥2 is the spectral norm of B. The following lemma characterizes the uniquemaximizer of (C.8).Lemma C.2.1. Let Ẑ = VΛU⊤⊗ be the SEL matrix. The optimal cost of the maximizationin (C.8) is ∥Ẑ∥∗, and B∗ = U⊗V⊤ is its unique maximizer.Proof. Any feasible B satisfies ∥B∥2 ≤ 1. Recalling that Ẑ has rank k − 1 (becauseV⊤D−11k = 0), let U⊗ = [u1, ...,uk−1] and V = [v1, ...,vk−1]. Hence,tr(ẐB) =k−1∑i=1Λi,i(u⊤i Bvi) ≤k−1∑i=1Λi,i = ∥Ẑ∥∗. (C.9)The inequality above is tight if and only if∀i ∈ [k − 1] : ϵi := u⊤i Bvi = 1, (C.10)which is indeed satisfied by B∗ = U⊗V⊤. Clearly, B∗ is also feasible. Hence, B∗ is amaximizer of (C.8).Next, we will show that there is no other maximizer, say B˜. Indeed, since B˜ is optimal,it must satisfy (C.10). Hence, it has rank at least k − 1. But since B˜D−11k = 0, wefind that B˜ has rank exactly k − 1. Let B˜ = UBΣBV⊤B be its compact SVD and denoteσi := ΣBi,i, i ∈ [k − 1] its singular values. Finally, define (k − 1)× (k − 1) matricesP = U⊤BU⊗ and Q = V⊤BV, (C.11)with columns pi,qi, i ∈ [k− 1]. By Equation (C.10) we have the following chain of inequal-88ities for all i ∈ [k − 1]:1 = u⊤i B˜vi = p⊤i ΣBqi =∑j∈[k−1]σjpi[j]qi[j] ≤∑j∈[k−1]σj |pi[j]qi[j]|≤∑j∈[k−1]|pi[j]qi[j]| ≤ ∥pi∥2∥qi∥2 ≤ 1.Inspecting this, we note that all inequalities must be equalities. The first inequality inthe second line follows because ∥B˜∥2 ≤ 1 =⇒ ∀j ∈ [k − 1] : σj ≤ 1. Hence, σj = 1for all j ∈ [k − 1]. Equivalently ΣB = Ik−1. The second inequality in that same line isCauchy-Schwarz and equality implies∀i ∈ [k − 1] : pi = ±qi. (C.12)The last inequality follows because∥pi∥2 = ∥U⊤Bui∥2 ≤ ∥UB∥2∥ui∥2 ≤ 1 and ∥qi∥2 = ∥V⊤Bvi∥2 ≤ ∥VB∥2∥vi∥2 ≤ 1.(C.13)Since UB (resp. VB) has orthonormal columns, equality in (C.13) holds if and only if forall i ∈ [k− 1], ui (resp. vi) is a column of UB (resp. VB). Then, it must be that P and Qare permutation matrices. Combined with (C.12) this givesP = Q = Π =⇒ U⊤BU⊗ = V⊤BV = Π, (C.14)for some permutation matrix Π. Continuing from this,U⊤BU⊗Π⊤ = V⊤BVΠ⊤ = Ik−1 =⇒ UB = U⊗Π⊤ and VB = VΠ⊤.Putting things together, we conclude thatB˜ = UBΣBV⊤B = UBV⊤B = U⊗Π⊤ΠV⊤ = U⊗V⊤ = B∗.This concludes the proof of the lemma.The lemma above shows that the relaxed dual problem (C.8) has a unique solution89B∗ = U⊗V⊤. On the other hand, from Lemma A.1.2, B∗ is strictly feasible in the relaxedcondition (C.7). Therefore, the relaxation in (C.8) is tight and B∗ is in fact the optimal dualvariable of the problem (C.3). Since, strong duality holds for (C.3), we also have q∗ = ∥Ẑ∥∗and the optimizer X∗ can be found by the complementary slackness conditions (C.5): letX∗ =[X∗11 X∗12X∗21 X∗22], and recall that B∗ satisfies (C.7) strictly. Then, the complementaryslackness conditions imply:∀i ∈ [n], c ̸= yi : 1− δyiX∗12[yi, i] + δcX∗12[c, i] = 0X∗11 = B∗⊤X∗⊤12, X∗22 = B∗X∗12, X∗12 = B∗⊤X∗22.From the last condition, it is straightforward to see X∗22 = U⊗Λ˜V⊤, X∗12 = VΛ˜U⊤⊗ andX∗11 = VΛ˜V⊤ for some Λ˜ ∈ R(k−1)×(k−1). Now, using the first condition, we have,δ−2c δyiX∗12[yi, i]− δ−1c X∗12[c, i] = δ−2c∑c ̸=yi=⇒ δyiX∗12[yi, i]∑c̸=yiδ−2c −∑c ̸=yiδ−1c X∗12[c, i] =∑c ̸=yiδ−2c=⇒ δyiX∗12[yi, i]∑c∈[k]δ−2c −∑c∈[k]δ−1c X∗12[c, i] =∑c ̸=yiδ−2c(i)=⇒ δyiX∗12[yi, i]∑c∈[k]δ−2c =∑c ̸=yiδ−2c=⇒ X∗12[yi, i] = δ−1yi(1− δ−2yi /∑c′∈[k]δ−2c′), X∗12[c, i] = −δ−1c(δ−2yi /∑c′∈[k]δ−2c′)=⇒ X∗12 = Ẑ. (C.15)In (i), we use the fact that V⊤D−11k = 0 and thus X∗12⊤D−11k = 0. By (C.15), and usingV⊤V = U⊤⊗U⊗ = Ik−1 it is easy to show Λ˜ = Λ and thus,X∗ =[VU⊗]Λ[V⊤ U⊤⊗]. (C.16)Now, it remains to show all the optimizers of (C.2) can be constructed byX∗ and that the re-laxation in (C.3) is tight. First, choose some partial orthonormal matrix R ∈ R(k−1)×d withRR⊤ = Ik−1, and construct W∗ = R⊤Λ1/2V⊤ and H∗ = R⊤Λ1/2U⊤⊗. Then, (W∗,H∗) is90by construction feasible in (C.2) and,q∗ ≤ p∗ ≤ 12∥W∗∥2F +12∥H∗∥2F =12tr(X∗) = q∗.Therefore, q∗ = p∗ and indeed the relaxation is tight. On the other hand, if (W˜, H˜) is aminimizer of (C.2), X˜ =[W˜⊤H˜⊤] [W˜ H˜]is feasible and optimal in (C.3) (since q∗ = p∗),which implies X˜ should satisfy (C.16). Hence, any minimizer of the CS-SVM (C.2) satisfies,[W∗⊤H∗⊤] [W∗ H∗]=[VU⊗]Λ[V⊤ U⊤⊗]. (C.17)The statement of the theorem is easy to see by (C.17).Remark 3 (Comparison to literature). The common analysis strategy in all other relatedworks is deriving tight bounds on the CE loss (or related quantities, such as the minimummargin), and, then identifying the structure in the parameters that achieves those bounds.For example, [9, 11, 56] lower bound the CE loss and [17] upper bounds the minimum mar-gin, all using a similar elegant argument based on Cauchy-Schwartz and Jensen inequalities.The ETF geometry is then uncovered by recognizing that it uniquely achieves those bounds.It is not clear how to employ such exercises in the presence of imbalances, due to the ab-sence of symmetry properties (e.g., alignment of classifiers with embeddings). Our proof ofthe theorem is more direct and is in large enabled by identifying the key role played by thelogit matrix.91Appendix DProofs of Chapter 5In this chapter, we gather the proofs of the results in Chapter 5. We start by deriving thegradient of the loss function in Section D.1. Recall that the SC loss and its symmetrizedconvex form is defined as follows,LSC(H) := 1n∑i∈[n]1nyi − 1∑j ̸=i,yj=yi− log(exp(h⊤i hj)∑ℓ̸=i exp(h⊤i hℓ)), (D.1)L̂(G) := 1n∑i∈[n]1nyi − 1∑j ̸=i,yj=yi− log(exp(Gi,j)∑ℓ̸=i exp(Gi,ℓ)),Lcvx(G) := 12(L̂(G) + L̂(G⊤)). (D.2)D.1 Properties of the SC LossD.1.1 GradientsLemma D.1.1 (Gradient of SC). For a given matrix Hd×n, let G = H⊤H and definePn×n and Qn×n as follows,Pi,j =0, i = jexp (Gi,j)/∑ℓ̸=i exp(Gi,ℓ) o.w. (D.3)Qi,j =0, i = j or yi ̸= yj1/(nc − 1) i ̸= j, yi = yj = c (D.4)92Then, the gradient of the SC loss (D.1) and the convex SC loss (D.2) are as follows,∇HLSC(H) = H(P+P⊤)− 2HQ, (D.5)∇GLcvx(G) = 12(P+P⊤)−Q. (D.6)Proof. Here, we prove (D.5). The proof of (D.6) can be derived similarly. First, we simplifythe expression of the loss.LSC(H) =∑i∈[n]1nyi − 1∑j ̸=iyj=yi− log(exp(h⊤i hj)∑ℓ ̸=i exp(h⊤i hℓ))=∑i∈[n]log(∑ℓ̸=iexp(h⊤i hℓ))−∑i∈[n]1nyi − 1∑j ̸=iyj=yih⊤i hj .Now we can compute the gradient with respect to each column hi as follows,∂LSC(H)∂hi=∑ℓ̸=i hℓ exp(h⊤i hℓ)∑ℓ ̸=i exp(h⊤i hℓ)+∑j ̸=ihj exp(h⊤j hi)∑ℓ ̸=j exp(h⊤j hℓ)− 2nyi − 1∑j ̸=iyj=yihj=∑j ̸=ihjPi,j +∑j ̸=ihjPj,i − 2nyi − 1∑j ̸=iyj=yihj=∑j∈[n]hj(Pi,j +Pj,i)−∑j ̸=iyj=yihjQi,j= 2H(pi + pi)− 2Hqi,where pi is the i-th row of P, and pi, qi are the i-th column of P and Q respectively.D.1.2 Strict ConvexityLemma D.1.2 (Strict-convexity of SC loss). For the convex SC loss (D.2), we have,Lcvx(G+V) > Lcvx(G) + tr(V⊤∇Lcvx(G)), if V − diag(V) ̸∝ 1n1⊤n − In, (D.7)93where diag(V) ∈ Rn×n is a diagonal matrix whose diagonal entries are the same as V.In other words, the convex SC loss (D.2) is strictly-convex in any direction satisfying thecondition in (D.7).Proof. For the vector g ∈ Rn, define fij(g) := log(∑ℓ ̸=i e−gj+gℓ) and let the rows andcolumns of G be defined as,G =[g1, · · · , gn]=[g1, · · · , gn]⊤.Then, we can rewrite the loss function as follows,Lcvx(G) = 12∑i∈[n]1nyi − 1∑j ̸=iyj=yi(fij(gi) + fij(gi)).Define ai := 1n−ei, andAi := (In− 1n−1aia⊤i ). We first show that for j ∈ [n], f(g) := fij(g)is strictly convex in any direction v such that Aiv ̸= 0. That is, for such v, f(g + v) >f(g) + v⊤∇f(g).From Taylor expansion, f(g + v) = f(g) + v⊤∇f(g) + 12v⊤∇2f(g + tv)v, for somet ∈ (0, 1). We will show that v⊤∇2f(g)v > 0 for all g, which together with the Taylorexpansion proves the statement. It is easy to verify that∇2f(g) = diag(u)− uu⊤, ur =e−gj+gr1+∑ℓ ̸=i,j e−gj+gℓ , r ̸= i0, r = i.Thus, we equivalently need to show, v⊤diag(u)v > (u⊤v)2. Since u ≥ 0, and u⊤1n = 1,v⊤diag(u)v =( ∑r∈[n]v2rur)( ∑r∈[n]ur)≥ ( ∑i∈[n]vrur)2= (u⊤v)2,where we used Cauchy-Schawrz inequality. The equality holds only if there exists a constantα such that for all r ̸= i, vr = α which contradicts the assumption Aiv ̸= 0.Now consider directionV satisfying condition (D.7). By convexity of fij(·), for all i ∈ [n]94and j ∈ {ℓ| yℓ = yi, ℓ ̸= i}, we have,fij(gi + vi) ≥ fij(gi) + v⊤i ∇fij(gi), fij(gi + vi) ≥ fij(gi) + vi⊤∇fij(gi).However, since V − diag(V) ̸∝ 1n1⊤n − In, there exists i′ ∈ [n] such that either Ai′vi′ ̸= 0or Ai′vi′ ̸= 0 (or both). Without loss of generality, suppose Ai′vi′ ̸= 0. Thus, by strict-convexity, for all j ∈ {ℓ| yℓ = yi, ℓ ̸= i}, for gi′ we have the following strict inequality.fi′j(gi′ + vi′) > fi′j(gi′) + v⊤i′∇fi′j(gi′).Summing the inequalities over all i ∈ [n] and j ∈ {ℓ| yℓ = yi, ℓ ̸= i}, we get (D.7), and theproof is complete.D.2 Proof of Lemma 5.2.1We prove the result for (5.2), and the proof for (5.3) with the ReLU constraints followssimilarly with a different threshold on the hyper-parameter τ . We will refer to this differencelater in the proof.Let C = {H ∈ Rd×n : ∥hi∥2 ≤ 1τ } be the convex feasible set, and suppose H ∈ C is afeasible point that does not satisfy the NC property. Without loss of generality, we assumey1 = y2 = 1 and h1 ̸= h2. Define Ĥ = [h2,h1,h3, ...,hn] by exchanging the first and secondcolumn of H. By the assumption Ĥ ̸= H and Ĥ − H = [h2 − h1,−(h2 − h1), 0, ..., 0].Clearly, Ĥ remains feasible in the problem. We will show thatf(H) := ⟨∇HLSC(H), Ĥ−H⟩ < 0.95Recall the gradient of the SC loss from Lemma D.1.1, and define G := H⊤H.f(H) = ⟨(h2 − h1), ∂LSC(H)∂h1− ∂LSC(H)∂h2⟩= (h2 − h1)⊤( ∑j∈[n]hj(P1,j +Pj,1 −P2,j −Pj,2) + 2n1 − 1(h1 − h2))=∑j∈[n](G2,j −G1,j)(P1,j +Pj,1 −P2,j −Pj,2)− 2n1 − 1∥h1 − h2∥22,=∑j ̸=1,2(G2,j −G1,j)(P1,j +Pj,1 −P2,j −Pj,2) + (P1,2 +P2,1 − 2n1 − 1)∥h1 − h2∥22,where recall that,Pi,j =0, i = jexp (Gi,j)/∑ℓ̸=i exp(Gi,ℓ) o.w.Define,α1 =∑j ̸=1,2(G2,j −G1,j)(P1,j −P2,j)α2 =∑j ̸=1,2(G2,j −G1,j)(Pj,1 −Pj,2) =∑j ̸=1,2(Gj,2 −Gj,1)(Pj,1 −Pj,2)α3 = (P1,2 +P2,1 − 2n1 − 1)∥h1 − h2∥22.Then, f(H1) = α1+α2+α3. We will show if τ is large enough, α1, α2 ≤ 0 and α3 < 0. Westart by α1:α1 =∑j ̸=1,2(G2,j −G1,j)(P1,j −P2,j)=∑j ̸=1,2(G2,j −G1,j)(exp(G1,j)∑ℓ̸=1 exp(G1,ℓ)− exp(G2,j)∑ℓ̸=2 exp(G2,ℓ))=∑j ̸=1,2(G2,j −G1,j)(exp(G1,j)∑ℓ̸=2 exp(G2,ℓ)− exp(G2,j)∑ℓ̸=1 exp(G1,ℓ))(∑ℓ̸=1 exp(G1,ℓ))(∑ℓ̸=2 exp(G2,ℓ)) =: β1β296Since the exponential function is monotonic, we haveβ1 = exp(G1,2)∑j ̸=1,2(G2,j −G1,j)(exp(G1,j)− exp(G2,i))+∑j ̸=1,2ℓ̸=1,2((G2,j +G1,ℓ)− (G2,ℓ +G1,j))(exp(G2,ℓ +G1,j)− exp(G2,j +G1,ℓ))≤ 0.Thus α1 ≤ 0. For α2, similarly with the monotonicity of the exponential function it isstraightforward to show α2 ≤ 0. It remains to show α3 < 0. Since ∥hi∥22 ≤ 1/τ , for alli, j ∈ [n], −1/τ ≤ Gi,j ≤ 1/τ . Thus, for P1,2 we haveP1,2 ≤ exp(1/τ)(n− 1) exp(−1/τ) .Now, suppose the condition on τ holds. Then,τ >2log( n−1nmax−1)≥ 2log( n−1n1−1)=⇒ 1n1 − 1 >exp(1/τ)(n− 1) exp(−1/τ) ≥ P1,2We can show the above inequality similarly holds for P2,1. Thus,P1,2 +P2,1 − 2n1 − 1 < 0 =⇒ α3 < 0,and f(H) < 0. This contradicts the first-order necessary condition for local optimality (5.4)and H cannot be the local minimum of (5.2).In case of UFM+, with non-neagativity constraints, we can bound the entries of G by0 ≤ Gi,j ≤ 1/τ . Thus, the proof holds similarly for τ > 1/log((n− 1)/(nmax − 1)).D.3 Proof of Theorem 4Before proving the theorem, we review useful tools from the constrained optimization liter-ature [37]. Consider the following constrained optimization.minxf(x) subj. to gi(x) ≤ 0, i ∈ [m1], (D.8)hi(x) = 0, i ∈ [m2],97where f(·), gi(·), i ∈ [m1], hi(·), i ∈ [m2] are real-valued and smooth functions. For a givenpoint x, we define the linear independence constraint qualification (LICQ) as follows.Definition 10 (LICQ, Nocedal and Wright [37, Chapter 12]). Let x be a feasible point in(D.8). LICQ holds at x if the gradients of the active constraints are linearly independent.In other words, the set of gradients A := {∇gi(x) | i ∈ [m1], gi(x) = 0}∪{∇hi(x) | i ∈ [m2]}is linearly independent.Consider the Lagrangian function corresponding to the constrained problem (D.8):Lag(x,λ,ν)= f(x) +∑i∈[m1]λi gi(x) +∑i∈[m2]νi hi(x),where λ ∈ Rm1 and ν ∈ Rm2 are the dual variables. The following theorem states the firstand second order necessary conditions for any local optimal point of (D.8).Theorem 7 (Nocedal and Wright [37, Chapter 12]). Let x̂ be a local optimal solution of(D.8) and suppose the LICQ condition is met at x̂.(i) First-order condition: There exists λ̂ ∈ Rm1 and ν̂ ∈ Rm2 that satisfy the KKTconditions of (D.8) at x̂. In other words,∇x Lag(x̂, λ̂, ν̂) = 0,gi(x̂) ≤ 0, hj(x̂) = 0 ∀i ∈ [m1], j ∈ [m2],λ̂ ≥ 0,λ̂i gi(x̂) = 0, ∀i ∈ [m1].(ii) Second-order condition: Let λ̂ and ν̂ be the dual variables that satisfy the KKTconditions at x̂. Then, for the Hessian of the Lagrangian, it holds that,d⊤∇2x Lag(x̂, λ̂, ν̂)d ≥ 0, ∀d ∈ D,where d ∈ D if, ∇x gi(x̂)⊤d = 0, if gi(x̂) = 0, λ̂i > 0∇x gi(x̂)⊤d ≥ 0, if gi(x) = 0, λ̂i = 0∇x hj(x̂)⊤d = 0, ∀j ∈ [m2].98Now, we have the necessary tools to prove Theorem 4. We re-state the optimizationproblem and its convex relaxation here for convenience and define their correponding La-grangian function.H∗ ∈ argminHLSC(H) subj. to ∥hi∥22 ≤1τ, ∀i ∈ [n], (D.9)LagH(H,λ) = LSC(H) +∑i∈[n]λi(h⊤i hi −1τ)G∗ ∈ argminGLcvx(G) subj. to G ≽ 0, Gi,i ≤ 1τ, ∀i ∈ [n]. (D.10)LagG(G,λ,U) = Lcvx(G) +∑i∈[n]λi(Gi,i − 1τ)− tr(GU⊤)First for problem (D.9), we check that for any feasible point H, LICQ holds. Let I = {i :gi(H) := ∥hi∥22 − 1/τ = 0} be the non-empty set of active constraints. If the gradient ofthe active constraints are linearly dependent, then there exists α ∈ Rn such that αj ̸= 0 forsome j ∈ I and ∑i∈[n]αi∇H gi(H) = 2[α1h1, · · · , αnhn] = 0.However, since ∥hj∥22 = 1/τ , hj ̸= 0 and thus αj = 0, which is a contradiction.Suppose Ĥ is a local optimal solution of (D.9). Thus, from Theorem (7), Ĥ should bea KKT point. Let λ̂ be the corresponding dual variable. Then we have,∇LagH(Ĥ, λ̂) = 2Ĥ(∇GLcvx(Ĥ⊤Ĥ) + diag(λ̂)) = 0,ĥ⊤i ĥi ≤1τ, ∀i ∈ [n],λ̂ ≥ 0,λ̂i(ĥ⊤i ĥi −1τ) = 0Let B := ∇GLcvx(Ĥ⊤Ĥ) + diag(λ̂). We consider two cases:99Case 1. Assume B has a negative eigenvalue. Then, there exists u ∈ Rn such that,u⊤Bu < 0.On the other hand, Ĥ satisfies the NC property from Lemma 5.2.1 and recall that byassumption, we had k < d. Thus, rank(Ĥ) ≤ k < d and Ĥ⊤ has a non-empty null-space:∃v ∈ Rd, Ĥ⊤v = 0.Define ∆d×n := vu⊤. We will show that the Hessian of the Lagrangian is strictly negativeand the second-order condition of Theorem 7 cannot hold for Ĥ. First, we note that ∆satisfies the direction constraints, since ∆⊤Ĥ = uv⊤Ĥ = 0. To prove our claim, we firstexpress the Hessian of the Lagrangian LagH(·, ·) in terms of the Hessian of the convex loss.In order to avoid vectorizing the variables in the Hessian computation, we use the followingnotation for the bilinear form of the Hessian of a scalar function f(H) in direction ∆.∇2Hf(H)[∆] =∑s,s′∈[d]∑i,i′∈[n]∂2f(H)∂Hs,i∂Hs′,i′∆s,i∆s′,i′ (D.11)With this notation, we can express the Lagrangian as follows,∇2H LagH(Ĥ)[∆] = 4∇2GLcvx(Ĥ⊤Ĥ)[Ĥ⊤∆] + 2 tr(B∆⊤∆)= 4∇2GLcvx(Ĥ⊤Ĥ)[0] + 2 tr(u⊤Buv⊤v)= 2∥v∥22(u⊤Bu)< 0,where we used ∆⊤Ĥ = 0, and that u is a negative eigen-vector of B. Thus, Ĥ does notsatisfy the second-order necessary condition of local optimality.Case 2. Assume B ≽ 0. Define Û = B and Ĝ := Ĥ⊤Ĥ. It is easy to check that (Ĝ, λ̂, Û)100satisfy the KKT conditions of the convex program:∇G LagG(Ĝ, λ̂, Û) = ∇GLcvx(Ĝ) + diag(λ)− Û = 0Ĝi,i ≤ 1τ, Ĝ ≽ 0Û ≽ 0tr(Û⊤Ĝ) = 0,where the last equality follows from the KKT condition of the non-convex program and thefact that ĤB = 0:tr(Û⊤Ĝ) = tr(BĤ⊤Ĥ) = tr(ĤBĤ⊤) = 0.On the other hand, the convex program (D.10) satisfies the Slater’s condition and thus anyKKT point is a global optimal. Now, for any H feasible in (D.9), H⊤H is feasible in (D.10)and we have,LSC(H) = Lcvx(H⊤H) ≥ Lcvx(Ĝ) = Lcvx(Ĥ⊤Ĥ) = LSC(Ĥ) (D.12)This follows since Ĝ is a global optimal solution of the convex program. Since (D.12) holdsfor any feasible H, Ĥ optimizes (D.9).In summary, if H is a local optimum and (Ĥ, λ̂) is the KKT point of (D.9), B ≽ 0.Given this condition, we can show Ĥ is a global solution, and this completes the proof.Finally we note that this proof also implies that the relaxation is tight.D.4 Proof of Lemma 5.3.1From Corollary 8, we can find the global solution of the UFM (D.9) from its convex re-laxation (D.10). As a result, to prove the lemma, we focus on characterizing the globalsolution of (D.10). Before doing so, recall from Lemma 5.2.1 that H∗ satisfies the NC prop-erty. Thus, G∗, given the samples are ordered, has a block-form and can be parameterizedby a symmetric k × k matrix as follows:∃Γ ∈ Rk×k, s.t. G∗i,j = Γyi,yj . (D.13)101We first argue that the global solution is unique.Lemma D.4.1 (Uniqueness). The convex problem (D.10) has a unique solution.Proof. We first show that at the optimal solution, we meet the condition in (D.7). SupposeG∗ − diag(G∗) = α(1n1⊤n − In), α ∈ R, and considerG1 =1τ[1n11⊤n1 00 1(n−n1)1⊤(n−n1)].G1 is positive semi-definite and feasible, so L(G∗) ≤ L(G1). Then, we have,L(G∗) ≤ L(G1) = n1 log((n1 − 1) + (n− n1)e− 1τ)+∑c ̸=1nc log(n− n1 − 1 + n1e− 1τ)< n1 log(n− 1)+∑c̸=1nc log(n− 1)= n log(n− 1)= L(G∗).That is L(G∗) < L(G∗) which is contradiction.Now, suppose G∗1 ̸= G∗2 are both optimal in (D.10). Since, both G∗1 and G∗2 are feasible,12(G∗1 +G∗2) is also feasible. Then, by optimality of G∗1,G∗2 and Lemma D.1.2,L(G∗1) ≤ L(G∗1 +G∗22)<12(L(G∗1) + L(G∗2)) = L(G∗1),which is a contradiction, and the proof is complete.Given (D.13), we can find G∗, the solution of (D.10), by the following problem.Γ∗,G∗ ∈ argminΓ,Gf(Γ) :=1n∑c∈[k]nc log((nc − 1) +∑c′ ̸=cnc′ exp(−Γc,c + Γc,c′)), (D.14)s.t. Γc,c ≤ 1τ∀c ∈ [k],Gi,j = Γyi,yj ∀i, j ∈ [n]G ≽ 0.We need the following lemma to complete the proof.102Lemma D.4.2. Consider problem (D.14). If nc1 = nc2, we haveΓ∗c1,c1 = Γ∗c2,c2 , Γ∗c,c1 = Γ∗c,c2 , ∀c ̸= c1, c2 (D.15)Proof. Without loss of generality, let c1 = 1 and c2 = 2, and define the permutation matrixR := Rc1 c2 as follows:Definition 11 (Permutation matrix). For i, j ∈ [k], the permutation matrix Rij ∈ Rk×k isthe matrix that swaps rows i and j of a matrix when multiplied by left. Equivalently, Rij isthe identity matrix In with the rows i and j swapped.Note that R⊤ = R. For any Γ ∈ Rk×k, RΓ swaps row c1 and c2 and ΓR swaps columnsc1 and c2.Recall that Γ∗ and G∗ are symmetric. We prove the lemma by contradiction. Specifi-cally, if the lemmas condition does not hold, we show that by swapping rows c1 and c2 ofΓ, followed by swapping the columns of the same index, the (optimal) loss value remainsthe same, while the optimizer changes.Suppose (D.15) does not hold. Define Γ˜ = RΓ∗R. Since n1 = n2, we have f(Γ∗) = f(Γ˜),while by assumption, Γ˜ ̸= Γ∗. Now, define R˜ as follows,R˜ :=0 In1 0 0 · · · 0In2 0 0 0 · · · 00 0 In3 0 · · · 00 0 0 In4 · · · 0............. . ....0 0 0 0 · · · Inkn×n.Then, it is straightforward to check G˜ = R˜G∗R˜ and Γ˜ are feasible in the problem (D.14).Since f(Γ∗) = f(Γ˜), (Γ˜, G˜) should also be optimal. This contradicts the uniqueness of thesolution by Lemma D.4.1, and the proof is complete.Given Lemma D.4.2, we can show that in the STEP-imbalanced or balanced case (as aspecial case) setup, the global solution G∗ has a simpler form. Recall that in a (R, ρ)-STEP103setting,nc = nc′ ifc, c′ ∈ {1, ..., ρk} (majority)c, c′ ∈ {ρk + 1, ..., k} (minority)Applying (D.15) for all pairs of classes with equal number of samples, we can show thatthere exists five scalars αmaj, αminor, βmaj, βminor, θ such that,Γ∗ =[Amaj θ1ρk1⊤ρkθ1ρk1⊤ρk Aminor],Amaj = (αmaj − βmaj)Iρk + βmaj1ρk1⊤ρkAminor = (αminor − βminor)Iρk + βminor1ρk1⊤ρk .This proves Lemma 5.3.1. In the special case of balanced data, we can further show thatαmaj = αminor =: α and βmaj = βminor =: β. This reduces to,G∗ = (α− β) In + ((β − θ)Ik + θJk)⊗ J(nk), (D.16)where Jm = 1m1⊤m.D.5 Proof of Theorem 5From Lemma D.4.2, the optimal solution of (D.10) in the balanced case follows (D.16).Thus, we can re-formulate the problem to optimize over α, β, θ.p∗ = minα,β,θlog((nk− 1) + (n− nk)e−β+θ)sub. to α ≤ 1τ,G = (α− β) In + ((β − θ)Ik + θJk)⊗ J(nk),G ≽ 0.It is easy to verify that the eigenvalues λ of G belong to the following set,λ ∈{α− β, α+ β(nk− 1)− θnk, α+ β(nk− 1) + θ(n− nk)}104Thus, the problem reduces to a linear program:(α∗, β∗, θ∗) = arg minα,β,θθ − β, sub. to 1τ− α ≥ 0,α− β ≥ 0,α+ β(nk− 1)− θnk≥ 0,α+ β(nk− 1) + θ(n− nk) ≥ 0.The unique solution of this program is α∗ = β∗ = 1/τ and θ∗ = −1/(τ(k−1)). This impliesG∗ is an ETF, and since d ≥ k, H∗d×n exists such that G∗ = H∗⊤H∗.D.6 Proof of Proposition 4We give a counter exmaple to rule out the optimality of ETF in imbalanced setups. Forsimplicity suppose τ = 1. We show ETF does not minimize the loss in a k = 3 classexample. Specifically, consider a STEP-imbalanced training set with 3 classes of sizes[Rα,α, α] with α ≥ 2 and R ≥ 10. Suppose HETF follows the ETF geometry. Then,from Definition 1 and the feasibility condition, for the mean-embeddings METF, we haveM⊤ETFMETF =kk−1(Ik − 1k1k1⊤k ). Thus, the value of the loss function at ETF isLSC(HETF) = α(R log(Rα− 1 + 2αe− 32 )+ 2 log (α− 1 + α(R+ 1)e− 32 )).Now, consider H˜ = [µ˜⊗1⊤Rα,−µ˜⊗1⊤α ,−µ˜⊗1⊤α ], where µ˜ is an arbitrary unit-norm vector.Since ∥µ˜∥2 = 1, it follows that H˜ is in the feasible set. With this choice of H˜, we have,LSC(H˜) = α(R log(Rα− 1 + 2αe−2)+ 2 log (2α− 1 +Rαe−2)).It is easy to check that, for imbalance levels higher than R ≥ 10,LSC(H˜) < LSC(HETF).In other words, ETF does not always attain the optimal cost in (5.2). The same argumentholds for general τ .105Appendix EAdditional Details on NumericalExperimentsE.1 Chapter 3Our experiments on deep models build on the code provided by Papyan et al. [38]1. Wetrain ResNet18 [15] and VGG13 [42] models, on three 10-class datasets, CIFAR10, MNISTand Fashion-MNIST. Following Papyan et al. [38], we use batch normalization in place ofthe dropout layers in VGG. For both models, we disable the biases of all the fully-connectedlayers, similar to the experiments on UFM. We train the models by SGD on CE loss, withmomentum (0.9), small weight decay (5 × 10−4), and learning rate 0.1 decayed at twostages (epochs 120 and 240) by a factor of 10. We train the network on a (R, 1/2)-STEPimbalance setting. To create imbalanced data, we use the data sampler provided by Caoet al. [7] 2. Following Papyan et al. [38] we do not use any data augmentation. In allthe experiments, we fix the first 5 classes to be majorities, and the rest as minorities. Tohave a fair comparison between the models with different imbalance ratios R, we samplethe datasets to have n = 25250 training images in all cases. While the training set isimbalanced, when measuring test performance of a trained model we do so on a balancedtest set, just like [6, 7].E.1.1 Additional ResultsTo complement the results in Section 3.2.4, here we use other metrics to compare the predic-tion of Theorem 1 with the learned classifiers and embeddings in the deep-net experiments.1https://colab.research.google.com/github/neuralcollapse/neuralcollapse/blob/main/neuralcollapse.ipynb2https://github.com/kaidic/LDAM-DRW106Norms of Classifiers/EmbeddingsIn this section, we investigate the geometry of learned embeddings and classifiers by focusingon their norms. For the classifier Wt := [w1, ...,wk] at epoch t, we define βWt(c, c′) =∥wc∥2/∥wc′∥2 with c being a majority and c′ a minority class. In the SELI geometry, thisquantity admits explicit closed-from expression thanks to Lemma 3.3.1. To determine thedeviation of the empirical norm-ratios βWt from the reference theoretical expression, wecalculate and report the following quantity:Averagec∈Kmajc′∈Kminor|βWt(c, c′)− β̂W|β̂W,where Kmaj = {c : nc = nmaj}, Kminor = {c : nc = nminor} are the indices of the majorityand minority classes, and β̂W is given by Lemma 3.3.1 for SELI and is equal to 1 for ETF.We can define a similar metric for the (centered) mean-embeddings, βMt(c, c′). FiguresE.1 and E.2 depict these metrics during training of the ResNet and VGG networks. Theresults confirm once more that the SELI geometry predicts the properties of the learnedgeometries. On the contrary, this is not the case for ETF when data are imbalanced. Weobserve that convergence to SELI geometry (and respective deviation from ETF) is morepronounced for the classifier weights and becomes elusive for the embeddings particularlyfor large imbalance ratios (R = 100).Non-alignment of Classifiers and EmbeddingsWhile in case of balanced datasets [38], we expect an alignment between the classifiers andembeddings, Lemma B.1.3 suggests W∗ and H∗ do not align in general for imbalanceddata. In fact, from Figure 3.6, while the majority embeddings remain aligned with theircorresponding classifier, for minority classes the alignment property can significantly breakdepending on the value of k and R. To verify this property in the learned models, wecompute the angle between minority mean-embeddings and classifiers, and measure thedeviation from the SELI prediction. Namely, let θc = Cos(wc,hc). Then, similar to theprevious section, we computeAveragec∈Kminor|θc − θ̂|θ̂,107012345R=1R=5R=10R=1000 50 100 150 200 250 300 3500123450 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350EpochsEpochsEpochsResNetVGGDistancetoSELI/ETFCIFAR10 MNIST Fashion-MNISTFigure E.1: Convergence of classifier norm ratio (∥wmaj∥2/∥wminor∥2) to SELI (solid) vsETF (dashed) for different imbalance levels R. The SELI geometry values are computed asper Lemma 3.3.1. For ETF this value is equal to one.012345R=1R=5R=10R=1000 50 100 150 200 250 300 3500123450 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350EpochsEpochsEpochsResNetVGGDistancetoSELI/ETFCIFAR10 MNIST Fashion-MNISTFigure E.2: Convergence of embeddings norm ratio (∥µmaj∥2/∥µminor∥2) to SELI (solid) vsETF (dashed) for different imbalance levels R. The SELI geometry values are computed asper Lemma 3.3.1. For ETF this value is equal to one.1080.00.10.20.30.40.50.6 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.00.20.40.60.81.00 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350EpochsEpochsEpochsResNetVGGDistancetoSELI/ETFCIFAR10 MNIST Fashion-MNISTFigure E.3: Alignment of minority embeddings and classifiers. Convergence of angles toSELI (solid) and ETF (dashed) for different imbalance levels R.where c ranges over minority classes and θ̂ is given by (B.1.3) for SELI and is equal to 1for ETF. Figure E.3 shows how this quantity evolves during training.Majority vs Minority Geometry ConvergenceIn order to better understand the individual behavior of majorities and minorities, we nowcompare individual quadrants of the (normalized) Gram matrices GW and GH matrices.Concretely, letGW =[GWmaj−maj GWmaj−minor(GWmaj−minor)⊤ GWminor−minor]be a partition of the normalized GW = GW/∥GW∥F to (k/2) × (k/2) sub-blocks (recallthat ρ = 1/2). Comparing quadrants GWmaj−maj,GWmaj−minor and GWminor−minor to thecorresponding quadrants of the reference SELI/ETF matrix ĜW allows us to zoom-in themajority-majority, majority-minority and minority-minority structures. Entirely analogouscalculations allow the same for the embeddings.Classifiers geometry. Figure E.4 confirms that both majority and minority geometriesconverge to SELI properly. Interestingly, we see that the minorities diverge the most fromthe equiangular structure of ETF geometry.Embeddings geometry. We find thanks to Figure E.5 that the distance of embeddings1090.00.10.20.30.40.50.60.70.8 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350Minority−MinorityMajority−Majority Majority−MinorityResNet+CIFAR10VGG+CIFAR100.00.10.20.30.40.50.60.70.8 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350ResNet+MNISTVGG+MNIST0.00.10.20.30.40.50.60.70.8 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.00.10.20.30.40.50.60.70.80 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350EpochsEpochs EpochsResNet+FMNISTVGG+FMNISTFigure E.4: Same setup as Figure 3.3 for learned classifiers. The distance metric dW iscomputed for the individual majority/minority blocks of the Gram matrix GWt .1100.00.20.40.60.81.0 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.00.20.40.60.81.00 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350Minority−MinorityMajority−Majority Majority−MinorityResNet+CIFAR10VGG+CIFAR100.00.20.40.60.81.0 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.00.20.40.60.81.00 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350ResNet+MNISTVGG+MNIST0.00.20.40.60.81.0 R=1R=5R=10R=1000 50 100 150 200 250 300 3500.00.20.40.60.81.00 50 100 150 200 250 300 350 0 50 100 150 200 250 300 350EpochsEpochs EpochsResNet+FMNISTVGG+FMNISTFigure E.5: Same setup as Figure 3.3 for learned embeddings. The distance metric dM iscomputed for the individual majority/minority blocks of the Gram matrix GMt .111to SELI geometry (compare to the better convergence for classifiers) shown previously inFigure 3.3 is primarily due to the minority class geometries. However, an overall inspectionof the subfigures shows that embeddings also tend to converge better to SELI compared toETF, in particular for majority geometries (see GMmaj−maj).E.2 Chapter 4UFM experiments. We train the UFM as a two-layer network (no biases) with n = 275inputs, d = 20 hidden units and k = 10 classes, trained on the basis vectors inRn. The labelsfor each vector are chosen such that the dataset is (R = 10, ρ = 1/2)-STEP imbalanced, withnminor = 5. We further use STEP logit adjustment, and choose ∆ = Rγ with γ ∈ [−1.5, 1.5].We train all models with the same constant learning rate for 6000 epochs. We normalizeδ so that 1Tk δ = k, since we empirically observe that for a fixed ratio ∆ the convergencespeed depends on the magnitude of δ.Deep-net experiments. We train (i) ResNet18 on CIFAR10, and (ii) an MLP on MNIST,both under a R = 10 imbalance ratio. The MLP model consists of 6 fully-connected layersof width 2048, each followed by batch-norm and ReLU activations. We train the models for350 epochs with an initial learning rate of 0.1 reduced at epochs 116 and 232 by a factor of10, with a batch size of 128. Following the same setting as Section E.1, we set momentumand weight decay to 0.9 and 10−5 respectively. We also normalize δ to sum to k, similar toUFM. We perform the experiments in Figure 4.1 without any data augmentation, remainingconsistent with previous works on neural collapse [e.g., 38].Generalization experiments (Section 4.3.2). In order to achieve results close to thestate-of-the-art, we perform data augmentation as in [7, 51] on all datasets: images areresized to 32 × 32, padded, randomly flipped and cropped. For MLP experimets, we usethe same architecture described above. We highlight two differences in our experiments.First, we use ResNet18 instead of ResNet32, and second, we train the models withoutapplying the delayed reweighting (DRW) technique [7]. Although DRW has been shown toimprove performance empirically, we refrained from using it in our experiments to evaluatethe performance of CDT and LDT independent of reweighting.112E.3 Chapter 5In our deep-net experiments, we use ResNet18 architecture. We replace the last layer linearclassifier with a normalization layer (∥hi∥2 = 1, i ∈ [n]) of feature dimension d = 512. Wedirectly optimize the normalized features that are then used for inference. (We note this isslightly different compared to Khosla et al. [24], where the authors train the output featuresof a projection head, then discard this projection head at inference time). We remark thatResNet has ReLU activations before the final output, which enforces a non-negativity onthe learned embeddings. Resnet18 models with CIFAR10, MNIST and FashionMNIST havebeen trained for 350 epochs with a constant learning rate of 0.1, no weight decay, batchsize of 1024, and temperature parameter τ = 0.1. All models, regardless of architecture ordataset, have been trained on a single Tesla V100 GPU machine.113
Thesis/Dissertation
eng
Electrical and Computer Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Thrampoulidis, Christos
Learning from imbalanced data : a geometric study on over-parameterized models
Text