#  Imbalance Trouble: Revisiting Neural-Collapse Geometry

Christos Thrampoulidis⋆, Ganesh R. Kini†, Vala Vakilian⋆, Tina Behnia⋆ 111This
work is supported by an NSERC Undergraduate Student Research Grant, an NSERC
Discovery Grant, NSF Grant CCF-2009030, and by a CRG8-KAUST award. The authors
also acknowledge use of the Sockeye cluster by UBC Advanced Research
Computing.
⋆University of British Columbia, Canada
†University of California, Santa Barbara, USA

###### Abstract

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

##  1 Introduction

What are the unique structural properties of models learned by training deep
neural networks to zero training error? Is there an _implicit bias_ towards
solutions of certain geometry? How does this vary across training instances,
architectures, and data? These questions are at the core of understanding the
optimization landscape of deep-nets. Also, they are naturally informative
about the role of models since different parameterizations might affect
preferred geometries. Ultimately, such understanding makes progress towards
explaining generalization of overparameterized models.

Recently, remarkable new progress in answering these questions has been made
by Papyan et al. [26], who empirically discover and formalize the so-called
_Neural-collapse_ (NC) phenomenon. NC describes geometric properties of the
learned embeddings (aka last-layer features) and of the classifier weights of
deep-nets, trained with cross-entropy (CE) loss and _balanced_ data far into
the zero training-error regime. The NC phenomenon produces a remarkably simple
description of a particularly symmetric geometry: (i) The embeddings of each
class collapse to their class mean (see __(NC)__ property); and (ii) The class
means align with the classifier weights and they form a simplex equiangular
tight frame (see __(ETF)__ property). Importantly, as noted by Papyan et al.
[26], this simple geometry appears to be “cross-situational _invariant_ ”
across different architectures and different _balanced_ datasets.

In this paper, we study Neural collapse with imbalanced classes: _Is there a
(ideally equally simple) description of the geometry that is invariant across
class-imbalanced datasets? _

(a) SELI geometry;
$(10,\nicefrac{{1}}{{2}})$-STEP imbalance, $k=4$ classes

(b) ETF geometry;
$k=4$ balanced classes

Figure 1: Visualization of the SELI and ETF geometries.

Contributions. We propose a new description capturing the geometric structure
of learned-embeddings and classifier-weights on possibly _class-imbalanced
data_ , which we call the _Simplex-Encoded-Labels Interpolation_ __(SELI)__
geometry. This new geometry is a generalization of the ETF geometry: It
recovers the latter when data are balanced or when there are only two classes,
and also, unlike ETF, it remains invariant across different _imbalance
levels_. Importantly, it too, has a simple description: The matrix of learned
logits interpolates a simplex-encoded label (SEL) matrix ${\hat{\mathbf{Z}}}$,
and, the individual geometries of the embeddings and classifiers are
determined by the SVD factors of this same SEL matrix. Because the particular
arrangement of columns of the SEL matrix changes with the imbalance level,
this also impacts the geometric arrangement of the embedding and classifier
vectors. Overall, the norms and angles of these vectors admit simple closed-
form expressions in terms of the imbalance characteristics and the number of
classes.

We use an example to illustrate this. Fig. 1(a) depicts the SEL matrix
${\hat{\mathbf{Z}}}\in\mathbb{R}^{4\times 110}$ for a STEP-imbalanced
$k=4$-class dataset with two majority classes of $50$ examples each, and, two
minority classes of $5$ examples each. Each column of ${\hat{\mathbf{Z}}}$
includes the $k$ learned logits for each one of the $110$ examples in the
dataset. Each such column has exactly one entry equal to $1-1/k=0.75$ and
three entries equal to $-1/k=-0.25$. The corresponding geometry of the
embeddings and classifiers, shown in the 3D plot, is found by an SVD of
${\hat{\mathbf{Z}}}$: the left eigenvectors determine the classifiers and the
right ones the embeddings. Note that ${\hat{\mathbf{Z}}}$ is rank 3, hence the
geometry is 3D. Since embeddings collapse to their class means (see __(NC)__
property), we only show the four class-mean embeddings and the corresponding
four classifiers. Two of each correspond to majorities (“$\bullet$” marker)
and two to minorities (“$+$” marker). The radii of the two concentric spheres
are equal to the norms of the minority classifiers (red sphere) and of the
minority embeddings (blue sphere), respectively. Note that the norms of
minorities and majorities are different, and so are the angles. Moreover, the
classifiers are _not_ aligned with the embeddings. Overall, the geometry is
different compared to the ETF geometry seen in the balanced case, which is
shown in Fig. 1(b). What remains invariant across class-imbalances is that the
logits (i.e. inner products between classifiers and embeddings) only take
values either $1-1/k$ or $-1/k$, so that the logit matrix is equal to the SEL
matrix. Equivalently, the learned model interpolates the simplex-encoding of
the labels.

Below we explain the conception of this geometry and our contributions in
detail. The initial major challenge was: _Assuming a class-imbalance-invariant
geometry exists, how to find it?_

To answer this question, we adopted the _Unconstrained Feature Model (UFM_)
previously introduced in the literature as a two-layer proxy model to
theoretically justify neural collapse [24, 3, 41]. Motivated by deep-learning
practice and by studies on implicit bias of gradient descent (GD) for
unregularized CE minimization, we analyze the geometry of solutions to an
unconstrained-features Support Vector Machines (UF-SVM) problem. We prove, for
STEP-imbalanced data, any solution of the UF-SVM follows the SELI geometry.
Thus, the learned end-to-end model always interpolates a simplex labels
encoding. We show that __(ETF)__ $\implies$__(SELI)__. However, __(SELI)__
$\not\implies$__(ETF)__ unless classes are balanced or there is just two of
them ($k=2$).

Next, we analyze training of the UFM with ridge-regularized CE. Unlike
previous studies, we find in the presence of imbalances that regularization
matters as it changes the geometry of solutions. In fact, we show that there
is _no_ finite regularization that leads to the SELI geometry. However, we
also show that as regularization vanishes, the solutions do interpolate the
SEL matrix (after appropriate normalization.) Finally, we show that the SELI
geometry differs from the minority-collapse phenomenon [3], since the latter
does not correspond to solutions with zero training error. In fact, we show
for minority collapse that: (i) It does _not_ occur for small finite
regularization and finite imbalance ratio, and (ii) It occurs asymptotically
for vanishing regularization, but only asymptotically as the imbalance ratio
grows.

We numerically test convergence to the proposed SELI geometry in both
synthetic and real class-imbalanced datasets. For different imbalance levels,
the learned geometries approach the SELI geometry significantly faster
compared to the ETF geometry. See Fig. 2. However, we also observe that
convergence _worsens_ with increasing level of imbalance. A plausible
theoretical justification is that as we show regularization plays critical
role under imbalances. We also consistently get better convergence rate for
the classifiers. We believe our observations strongly motivate further
investigations regarding potential frailties of “asymptotic” implicit bias
characterizations and how these might vary in multiclass and possibly
imbalanced settings.

Distance to SELI/ETF

CIFAR10

Distance to SELI/ETF

MNIST

EpochsDistance to SELI/ETF (a) Classifiers

Fashion-MNISTEpochs (b) Embeddings

Epochs (c) Logits

Figure 2: Convergence of learned classifiers, embeddings and corresponding
logits to the SELI (solid lines) vs ETF (dashed lines) geometries, measured
using a ResNet-18 model, trained far beyond zero training error on STEP-
Imbalanced CIFAR10, MNIST and Fashion-MNIST, for different imbalance ratios
$R$; see Sec. 5 for metrics and discussion.

Why imbalanced? Investigating structural geometric properties under data
imbalances is important for the following reasons. First, data-imbalances
appear in various learning tasks more often than not. Thus, it is relevant
understanding what deep neural networks learn in these settings. Second, the
previously discovered, perfectly symmetric, ETF geometry only holds when the
data distribution is itself symmetric. This naturally raises a question, which
we answer here: when this data symmetry breaks, is it still possible to
characterize potentially non-symmetric geometries? We argue this result is
nontrivial, particularly so because the new geometry is richer than the ETF as
it is parameterized by not only the number of classes, but also by the
imbalance ratio and the fraction of minorities. Third, while previous work has
shown the simplified unconstrained-features model is powerful to predict the
exact geometry when classes are balanced, it is not a priori known whether the
model is also able to predict the corresponding geometry when classes are
imbalanced. Our paper shows this to be the case and also uncovers several
unique features when data are imbalanced: (i) the UFM solution depends on the
regularization parameter, and, (ii) epoch-wise convergence of SGD slows down
with increasing imbalance and is generally better for classifiers compared to
embeddings. Finally, it is known that data imbalances affect generalization
since vanilla training with cross-entropy loss results in poor generalization
for minority classes. We envision that understanding how the properties of the
learnt geometries vary for minorities versus majorities could help create
links between structural results and generalization towards explaining the
effectiveness of existing or inspiring new techniques for mitigating
imbalances.

Geometry of global minimizers for UFM
---
|  UF-RidgeCE (Eqn. (1)) |  UF-SVM (Eqn. (2))
Balanced |  ETF [21, 5, 41, 3, 32] |  ETF [12], [Cor. 1.3]
Imbalanced |  $\forall{\lambda}$: NO SELI [Prop. 1] ${\lambda}\rightarrow 0$: SELI [Prop. 2] ${\lambda}<\frac{1}{2}$: NO minority collapse [Sec. H] |  SELI [Thm. 1]

Table 1: Summary of contributions and comparison to most-closely related work.

###  1.1 Related works

The original contribution by Papyan et al. [26] has attracted lots of
attention resulting in numerous followups within short time period, e.g., [41,
12, 3, 9, 21, 24, 5, 40, 32]. (See also [9, Sec. E] for a review of the recent
literature.) Several works have proposed and/or used the UFM with CE training
to analyze theoretical abstractions of NC [41, 12, 3, 5]. Other works analyze
the UFM with square loss [24, 9, 40, 32] and recent model extensions
accounting for additional layers and nonlinearities are studied in [32]. Here,
we drove particular inspiration from Zhu et al. [41], who presented a
particularly transparent and complete analysis of the optimization landscape
of ridge-regularized CE minimization for the UFM under balanced data. In the
same spirit, we also relied on the UFM. However, our work is, to the best of
our knowledge, the first explicit geometry analysis for class-imbalanced data.
See also Table 1 for a comparison.

The only previous work on neural collapse with imbalances is [3], which was
the first to note that collapse of the embeddings is preserved, but otherwise
the geometry might skew away from ETF. Also, Fang et al. [3] first proposed
studying the new geometry using the UFM and appropriate convex relaxations.
With this setup, they presented an intriguing finding, which they termed
_minority collapse_ : for large imbalance levels, the minorities’ classifiers
collapse to the same vector. As mentioned above, our focus is on the,
particularly relevant for deep-learning practice, zero-training error
scenarios. This excludes minority collapse by definition. More importantly, we
derive an explicit geometric characterization of _both_ embeddings and
classifiers for _both_ majorities and minorities and for _all_ imbalance
levels. Specializing these findings to vanishing regularization and imbalance
ratio growing to infinity recovers and gives new insights to minority
collapse.

Our results also draw from and relate to the literatures on implicit bias,
matrix factorization, and imbalanced deep-learning. We defer a detailed
discussion on these to Sec. I of the Supplementary Material.

###  1.2 Organization

In Sec. 2 we setup some necessary terminology and introduce the unconstrained
features model. In Sec. 3 we formally introduce the SELI geometry as the
geometry of the global minimizers of the non-convex max-margin minimization
over the UFM. We also relate the new SELI geometry to the ETF and derive
closed-form expressions for the former in terms of the level of imbalance.
Next in Sec. 4, we investigate the impact of data imbalances on the structure
of the ridge-regularized CE minimization with the UFM. In Sec. 5 we present
experimental results corroborating our theoretical findings. Specifically, we
conduct experiments on both synthetic data under the UFM and on benchmark
class-imbalanced datasets. Concluding remarks and some directions for future
research are included in Sec. 6.

The proofs of our results are presented in Secs. A–C of the Supplementary
Material (SM). Several additional experimental results on the UFM and on real
data are also included in Sec.s F and G, respectively. Sec. H of the SM
discusses in detail implications of our findings to minority collapse.
Finally, Sec. I includes additional remarks and comparisons to previous works.

Notation. For matrix $\mathbf{V}\in\mathbb{R}^{m\times n}$, $\mathbf{V}[i,j]$
denotes its $(i,j)$-th entry, $\mathbf{v}_{j}$ denotes the $j$-th _column_ ,
$\mathbf{V}^{T}$ its transpose and $\mathbf{V}^{\dagger}$ its Moore-Penrose
pseudoinverse. We denote $\|\mathbf{V}\|_{F},\|\mathbf{V}\|_{2}$, and,
$\|\mathbf{V}\|_{*}$ the Frobenius, spectral, and, nuclear norms of
$\mathbf{V}$. $\operatorname{tr}(\mathbf{V})$ denotes the trace of
$\mathbf{V}$. $\odot$ and $\otimes$ denote Hadammard and Kronecker products,
respectively. $\mathbf{V}\succ 0$ denotes $\mathbf{V}$ is positive
semidefinite and $\mathbf{V}\geq 0$ that $\mathbf{V}$ has nonnegative entries.
$\nabla_{\mathbf{V}}\mathcal{L}\in\mathbb{R}^{m\times n}$ is the gradient of a
scalar function $\mathcal{L}(.)$ with respect to $\mathbf{V}$. We use
$\mathds{1}_{m}$ to denote an $m$-dimensional vector of all ones and
$\mathds{I}_{m}$ for the $m$-dimensional identity matrix. For vectors/matrices
with all zero entries, we simply write $0$, as dimensions are easily
understood from context. $\mathbf{e}_{j}$ denotes a column with a single non-
zero entry of $1$ in the $j$-th entry.

##  2 Problem setup

We adopt the _unconstrained feature model_ (UFM) [24, 3] in a $k$-class
classification setting. Let $\mathbf{W}_{d\times
k}=[\mathbf{w}_{1},\mathbf{w}_{2},\cdots,\mathbf{w}_{k}]$ be the matrix of
classifier weights corresponding to the $k$ classes. Here, $d$ is the feature
dimension. We assume throughout that $d\geq k-1$. Next, we let
${\mathbf{H}}_{d\times
n}=[\mathbf{h}_{1},\mathbf{h}_{2},\cdots,\mathbf{h}_{n}]$ denote a matrix of
$n$ feature embeddings, each corresponding to a different example in the
training set. We assume each class $c\in[k]$ has $n_{c}\geq 1$ examples (thus,
$n_{c}$ embeddings) so that $\sum_{c\in[k]}n_{c}=n.$ Without loss of
generality, we assume examples are ordered. Formally, we assume that examples
$i=1,\ldots,n_{1}$ have labels $y_{i}=1$, examples
$i=n_{1}+1,\ldots,n_{1}+n_{2}$ have labels $y_{i}=2$, and so on. The UFM
trains the features $\mathbf{h}_{i},i\in[n]$ (jointly with the weights
$\mathbf{w}_{c},c\in[k]$) without any further constraints, i.e., by minimizing
the ridge-regularized cross-entropy (CE) loss as follows [41]:

$\displaystyle({\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda}):=\arg\min_{\mathbf{W},{\mathbf{H}}}~{}\mathcal{L}(\mathbf{W}^{T}{\mathbf{H}})+\frac{{\lambda}}{2}\|\mathbf{W}\|_{F}^{2}+\frac{{\lambda}}{2}\|{\mathbf{H}}\|_{F}^{2},$
(1)

where
$\mathcal{L}(\mathbf{W}^{T}{\mathbf{H}}):=\sum_{i\in[N]}\log\big{(}1+\sum_{c\neq
y_{i}}e^{-(\mathbf{w}_{y_{i}}-\mathbf{w}_{c})^{T}\mathbf{h}_{i}}\big{)}$ is
the CE loss.

UFM as two-layer linear net. The formulation above does not explicitly specify
inputs for each example. An alternative view follows by considering training a
2-layer linear net with hidden dimension $d$, first layer ${\mathbf{H}}$, and
second layer $\mathbf{W}$, over $n$ examples with $n$-dimensional inputs
$\mathbf{x}_{i}=\mathbf{e}_{i}\in\mathbb{R}^{n},\in[n]$ and labels $y_{i}$ as
above: $y_{i}=1$ for $i=1,\ldots,n_{1}$, $y_{i}=2$ for
$i=n_{1}+1,\ldots,n_{1}+n_{2}$, and so on.

###  2.1 Unconstrained-features SVM (UF-SVM)

Since neural-collapse is observed when training with small / vanishing
regularization [26], it is reasonable to consider an unregularized version of
(1). In this special case, gradient descent (with sufficiently small step
size) on (1) produces iterates that diverge in norm, but converge in direction
[22, 12]. In fact, it has been recently shown that the GD solutions converge
in direction to a KKT point of the following max-margin classifier [22, 12]:

$\displaystyle({\hat{\mathbf{W}}},{\hat{{\mathbf{H}}}})\in\arg\min_{\mathbf{W},{\mathbf{H}}}~{}\frac{1}{2}\|\mathbf{W}\|_{F}^{2}+\frac{1}{2}\|{\mathbf{H}}\|_{F}^{2}\quad\quad\text{sub.
to}\quad(\mathbf{w}_{y_{i}}-\mathbf{w}_{c})^{T}\mathbf{h}_{i}\geq
1,~{}i\in[n],c\neq y_{i}.$ (2)

For convenience, we refer to the optimization problem in (2) as unconstrained-
features SVM (UF-SVM). This minimization (unlike ‘standard’ SVM) is non-
convex. Hence, KKT points (thus, GD convergence directions) are not
necessarily global minimizers; see discussion in Sec. 6.

###  2.2 Class-imbalance model

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

######  Definition 1 ($(R,\rho)$-STEP imbalance).

In a $(R,\rho)$-STEP imbalance setting with label-imbalance ratio $R\geq 1$
and minority fraction $\rho\in(0,1)$, the following hold. All minority (resp.
majority) classes have the same sample size $n_{\text{min}}$ (resp.
$Rn_{\text{min}}$). There are $(1-\rho)k$ majority and $\rho k$ minority
classes. Without loss of generality, we assume classes
$\\{1,\ldots,(1-\rho)k\\}$ are majorities.

##  3 Global structure of the UF-SVM: SELI geometry

In this section, we characterize the global minimizers of the non-convex
program in (2). Perhaps surprisingly, we show that they take a particularly
simple form that is best described in terms of a _simplex-encoding_ of the
labels.

######  Definition 2 (SEL matrix).

The _simplex-encoding label (SEL) matrix_ ${\hat{\mathbf{Z}}}_{k\times n}$ is
such that

$\displaystyle\forall
c\in[k],i\in[n]\,:\,\,\,\,{\hat{\mathbf{Z}}}[c,i]=\begin{cases}1-1/k&,\,c=y_{i}\\\
-1/k&,\,c\neq y_{i}\end{cases}.$ (3)

Onwards, let ${\hat{\mathbf{Z}}}^{T}=\mathbf{U}\bm{\Lambda}\mathbf{V}^{T}$ be
the compact SVD of ${\hat{\mathbf{Z}}}^{T}$. Specifically, $\bm{\Lambda}$ is a
positive $(k-1)$-dimensional diagonal matrix and $\mathbf{U}_{n\times(k-1)}$,
$\mathbf{V}_{k\times(k-1)}$ have orthonormal columns.

Each column ${\hat{\mathbf{z}}}_{i}\in\mathbb{R}^{k}$ of ${\hat{\mathbf{Z}}}$
represents a class-membership encoding of datapoint $i\in[n]$. This differs
from the vanilla one-hot encoding $\hat{\mathbf{y}}_{i}=\mathbf{e}_{y_{i}}$ in
that ${\hat{\mathbf{z}}}_{i}=\hat{\mathbf{y}}_{i}-\frac{1}{k}\mathds{1}_{k}$.
Specifically, ${\hat{\mathbf{Z}}}$ has exactly $k$ different and affinely
independent columns, which together with the zero vector form a
$k$-dimensional simplex, motivating the SEL name. Finally, note that
${\hat{\mathbf{Z}}}^{T}\mathds{1}_{k}=0$; thus,
$\operatorname{rank}({\hat{\mathbf{Z}}})=k-1$. We gather useful properties
about the eigenstructure of ${\hat{\mathbf{Z}}}$ in Sec. A.

######  Theorem 1 (Structure of the UF-SVM minimizers).

Suppose $d\geq k-1$ and a $(R,\rho)$-STEP imbalance setting. Let
$({\hat{\mathbf{W}}},{\hat{{\mathbf{H}}}})$ be any solution and
$\mathrm{p}_{*}$ the optimal cost of the UF-SVM in (2). Then,
$\mathrm{p}_{*}={\|{\hat{\mathbf{Z}}}\|_{*}}={\|{\hat{{\mathbf{H}}}}\|_{F}^{2}}={\|{\hat{\mathbf{W}}}\|_{F}^{2}}$.
Moreover, the following statements characterize the geometry of global
minimizers in terms of the the SEL matrix and its SVD.

  1. (i)

For the optimal logits it holds that
${\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}}={\hat{\mathbf{Z}}}$.

  2. (ii)

The Gram matrices satisfy
${\hat{{\mathbf{H}}}}^{T}{\hat{{\mathbf{H}}}}=\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$
and
${\hat{\mathbf{W}}}^{T}{\hat{\mathbf{W}}}=\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}.$

  3. (iii)

For some partial orthonormal matrix $\mathbf{R}\in\mathbb{R}^{(k-1)\times d}$,
${\hat{\mathbf{W}}}=\mathbf{R}^{T}\bm{\Lambda}^{1/2}\mathbf{V}^{T}$ and
${\hat{{\mathbf{H}}}}=\mathbf{R}^{T}\bm{\Lambda}^{1/2}\mathbf{U}^{T}.$

We outline the theorem’s proof in Sec. 3.3 and defer the details to Sec. C.1.
The theorem provides an explicit characterization of the geometry of optimal
embeddings and classifiers that relies around the key finding that the optimal
logit matrix is always equal to the SEL matrix. We highlight the following key
features of this characterization.

Simplicity. The lack of symmetry in the imbalanced setting, makes it a priori
unclear whether a simple geometry description is still possible, as in the
balanced case. But, the theorem shows this to be the case. The key observation
is that the optimal logit matrix ${\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}}$
equals ${\hat{\mathbf{Z}}}$ (cf. Statement (i)). Then, the Gram matrices of
embeddings and classifiers are given simply in terms of the singular factors
of the SEL matrix (cf. Statements (ii),(iii)).

Invariance to imbalances. The theorem’s characterization is valid for all
types of $(R,\rho)$-STEP imbalances. In particular, equality of the optimal
logit matrix to the SEL matrix is the key invariant characterization across
changing imbalances. This also implies that at optimality all margins are
equal irrespective of the imbalance type. The description of Gram matrices in
terms of the SVD of ${\hat{\mathbf{Z}}}$ is also invariant. Of course, the
particular arrangement of columns of ${\hat{\mathbf{Z}}}$ itself depends on
the values of $(R,\rho)$. In turn, the singular factors determining the
geometry of embeddings and classifiers depend implicitly on the same
parameters. Thus, as we show next, the geometry differs for different
imbalance levels; see Fig. 1 for an example.

###  3.1 Invariant properties: NC and SELI

Here, we further discuss the geometry of embeddings and classifiers induced by
the SVD of the SEL matrix. The first realization is that the embeddings
collapse under _all_ settings.

######  Corollary 1.1.

The UF-SVM solutions satisfy the following property irrespective of imbalance:

  1. _(NC)_

The embeddings collapse to their class means
$\hat{\mathbf{h}}_{i}=\hat{\bm{\mu}}_{c}:=\frac{1}{n_{c}}\sum_{j:y_{j}=c}\hat{\mathbf{h}}_{j}$,
$\forall c\in[k]$, $i:y_{i}=c$.

This statement can be inferred from Theorem 1 (specifically from Statement
(iii) and that $\mathbf{U}$ has repeated columns.) A more straightforward
argument is possible by directly inspecting the UF-SVM optimization in (2).
For any fixed (say optimal) ${\hat{\mathbf{W}}}$, the minimization over
$\mathbf{h}_{i}$ is: (i) separable and identical for all $i\,:\,y_{i}=c$ in
same class $c$, and (ii) strongly convex. Hence, for all $i\,:\,y_{i}=c$,
there is unique minimizer corresponding to the fixed ${\hat{\mathbf{W}}}$;
this must be their class mean.

Beyond (NC), Theorem 1 specifies the exact geometry of solutions. The
corollary below is a restatement of Theorem 1 under the following
formalization of what we call the SELI geometry.

######  Definition 3 (SELI geometry).

The embedding and classifier matrices ${\mathbf{H}}_{d\times n}$ and
$\mathbf{W}_{d\times k}$ follow the simplex-encoded-labels interpolation
geometry when for some scaling $\alpha>0$:

  1. _(SELI)_

$\begin{bmatrix}\mathbf{W}^{T}\\\
{{\mathbf{H}}}^{T}\end{bmatrix}\begin{bmatrix}\mathbf{W}&{\mathbf{H}}\end{bmatrix}=\alpha\begin{bmatrix}\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}&{\hat{\mathbf{Z}}}\\\
{\hat{\mathbf{Z}}}^{T}&\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}\end{bmatrix},$
where ${\hat{\mathbf{Z}}}=\mathbf{V}\bm{\Lambda}\mathbf{U}^{T}$ is the SEL
matrix.

######  Corollary 1.2.

The UF-SVM solutions follow the SELI geometry, irrespective of imbalance.

The __(SELI)__ geometry characterization specifies (up to a global positive
scaling) the Gram matrices $\mathbf{G}_{\mathbf{W}}:=\mathbf{W}^{T}\mathbf{W}$
and $\mathbf{G}_{\mathbf{H}}:={\mathbf{H}}^{T}{\mathbf{H}}$, and the logit
matrix $\mathbf{Z}:=\mathbf{W}^{T}{\mathbf{H}}$. Specifically, the diagonals
of the two Gram matrices specify the _norms_ of the classifiers and of the
embeddings 222To simplify the exposition, we assume throughout that the
regularization strength is same for embeddings and classifiers. For
completeness we treat the general case in Sec. C.3 in the SM, where it is
shown that different regularization values do _not_ change the SELI geometry
as per Definition 3 apart from introducing a (global) relative scaling factor
between the norms of the embeddings and classifiers.. These, together with
their off-diagonal entries, further specify the _angles_ between different
classifiers and between different embeddings. Because of the __(NC)__
property, the norms and angles of the embeddings $\mathbf{h}_{i},i\in[n]$ are
uniquely determined in terms of the norms and angles of the mean-embeddings
$\bm{\mu}_{c},c\in[k]$. In other words, the Gram matrix
$\mathbf{G}_{\mathbf{H}}={\mathbf{H}}^{T}{\mathbf{H}}\in\mathbb{R}^{n\times
n}$ is such that for all $i\in[n]$,
$\mathbf{G}_{{\mathbf{H}}}[i,j]=\mathbf{G}_{{\mathbf{H}}}[i,\ell]$ if
$y_{j}=y_{\ell}$. Finally, the norms together with the entries of the logit
matrix determine the angles between the two sets of: (a) the $k$ classifiers
and (b) the $k$ mean embeddings. Thus, they specify the degree of alignment
between the two sets of vectors. In the next section, we show that it is in
fact possible to obtain explicit closed-form formulas describing the norms,
angles and alignment of classifier and embedding vectors, in terms of the
imbalance characteristics and the number of classes.

######  Remark 3.1 (Why “SELI”?).

For the UFM, $\mathbf{Z}=\mathbf{W}^{T}{\mathbf{H}}$ is the learned end-to-end
model. According to its definition, the SELI geometry implies
$\mathbf{W}^{T}{\mathbf{H}}=\alpha{\hat{\mathbf{Z}}}$. Thus, the learned model
_interpolates_ (a scaling of) the SEL matrix, motivates the naming in
Definition 3.

####  3.1.1 Special case: Balanced or binary data

For the special cases of balanced or binary data, Theorem 1 recovers the ETF
structure, i.e. __(SELI)__ $\equiv$__(ETF)__. Let
$\hat{\mathbf{M}}=[\hat{\bm{\mu}}_{1},\ldots,\hat{\bm{\mu}}_{k}]$ denote the
matrix of mean embeddings.

######  Corollary 1.3 ($R=1$ or $k=2$).

Assume balanced data ($R=1$) or binary classification ($k=2$). Then, any UF-
SVM solution $(\hat{\mathbf{W}},\hat{\mathbf{H}})$ follows the ETF geometry as
defined in [26]:

  1. _(ETF)_

$\hat{\mathbf{W}}=\hat{\mathbf{M}}$ and
$\hat{\mathbf{M}}^{T}\hat{\mathbf{M}}=\hat{\mathbf{W}}^{T}\hat{\mathbf{W}}=\mathds{I}_{k}-\frac{1}{k}\mathds{1}_{k}\mathds{1}_{k}^{T}$.

Thus, when data are balanced or binary: (i) the norms of the classifiers and
of the embeddings are all equal; (ii) the angles between any two classifiers
or any two embeddings are all equal to $\frac{-1/k}{(k-1)/k}=-\frac{1}{k-1}.$;
and, (iii) the set of classifiers and the set of embeddings are aligned.

###  3.2 How the SELI geometry changes with imbalances

For $k>3$ and $R>1$, __(SELI)__ $\not\implies$__(ETF)__. In this general case,
the norms and angles specifying the geometry are determined in terms of the
SVD factors of the SEL matrix as per Definition 3. In Sec. A, we give an
explicit characterization of these SVD factors. Notably, this allows us to
obtain explicit closed-form formulas for the norms, angles and alignment of
the SELI geometry in terms of $R,\rho$ and $k,n_{\min}$. The following lemma
is an example: it gives a formula for the ratio of majority and minority norms
for the classifiers and embeddings. For simplicity, we focus on the default
case of equal numbers of minorities and majorities, i.e. $\rho=1/2$.

######  Lemma 3.1 (Norm ratios).

Assume $(R,\nicefrac{{1}}{{2}})$-STEP imbalance. Suppose
$(\mathbf{W},{\mathbf{H}})$ satisfies the _(SELI)_ property. Let
$\mathbf{w}_{\rm{maj}},\mathbf{h}_{\rm{maj}}$ (resp.
$\mathbf{w}_{\rm{minor}},\mathbf{h}_{\rm{minor}}$) denote majority (resp.
minority) classifiers and embeddings, respectively. Then,

$\displaystyle\frac{\|\mathbf{w}_{\rm{maj}}\|_{2}^{2}}{\|\mathbf{w}_{\rm{minor}}\|_{2}^{2}}=\frac{(1-2/k)\sqrt{R}+\frac{\sqrt{(R+1)/2}}{k}}{(1-2/k)+\frac{\sqrt{(R+1)/2}}{k}}~{}~{}\text{
and
}~{}~{}\frac{\|\mathbf{h}_{\rm{maj}}\|_{2}^{2}}{\|\mathbf{h}_{\rm{minor}}\|_{2}^{2}}=\frac{\frac{1}{\sqrt{R}}(1-2/k)+\frac{1}{k\sqrt{(R+1)/2}}}{(1-2/k)+\frac{1}{k\sqrt{(R+1)/2}}}.$

Thus, $\|\mathbf{w}_{\rm{maj}}\|_{2}\geq\|\mathbf{w}_{\rm{minor}}\|_{2}$ and
$\|\mathbf{h}_{\rm{maj}}\|_{2}\leq\|\mathbf{h}_{\rm{minor}}\|_{2}$, with
equalities if and only if $R=1$ or $k=2$.

The fact that CE learns classifiers of larger norm for majorities (i.e.
$\|\mathbf{w}_{\rm{maj}}\|_{2}\geq\|\mathbf{w}_{\rm{minor}}\|_{2}$), has been
empirically observed in the deep imbalanced-learning literature, e.g. by Kang
et al. [17], Kim and Kim [18]. Lemma 3.1, not only provides a theoretical
justification for this empirical observation, but it also precisely quantifies
the ratio. Moreover, it specifies the norm-ratio between majorities and
minorities, not only for classifiers, but also for the learned embeddings.

(a) Norms of classifiers and embeddings.

(b) Alignment of classifiers and embeddings.

(c) Angles of classifiers and embeddings. Dashed lines show the value
$-1/(k-1)$ characterizing the ETF geometry.

Figure 3: Illustration of how norms and angles of the SELI geometry vary with
the number of classes $k$ and the imbalance ratio $R$. The minorities fraction
is set to $\rho=1/2$. Unless $R=1$ or $k=2$, the geometry differs from the ETF
geometry. For example, majority classifiers have larger norms than minorities
(see Fig. 3(a)), minority classifiers are less aligned with their
corresponding class mean-embeddings (see Fig. 3(b)), and the angle between
minority classifiers decreases (see Fig. 3(c)). The depicted values are
computed thanks to closed-form formulas. See Sec. 3.2 and Sec. B.

Sec. B includes additional closed-form formulas for the angles and alignment
of classifiers and embeddings. Thanks to these, it is easy to precisely
quantify the changes in the geometry as a function of the imbalance ratio and
of number of classes. As another example of this, besides Lemma 3.1, the SELI
geometry leads to majority / minority angles for the classifiers satisfying
the following formulas: (with $(R,\nicefrac{{1}}{{2}})$-STEP imbalance; see
Sec. B.1.2 for details)

$\displaystyle\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{w}_{\rm{maj}}^{\prime})$
$\displaystyle=\frac{-2\sqrt{R}+\sqrt{(R+1)/2}}{(k-2)\sqrt{R}+\sqrt{(R+1)/2}}$
$\displaystyle\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})$
$\displaystyle=\frac{R-7}{R-7+2k\big{(}2+\sqrt{(R+1)/2}\big{)}}\,.$ (4)

Here, $\mathbf{w}_{\rm{maj}},\mathbf{w}_{\rm{maj}}^{\prime}$ are two
classifier vectors corresponding to any two majority classes (similarly for
the minorities.) It is easy to see that both these formulas evaluate to
$-1/(k-1)$ for $R=1$. Furthermore, the cosine of majorities is strictly
decreasing, while the cosine of minorities is strictly increasing. That is,
with increasing imbalance ratio majority classifiers go further away from each
other, while minority classifiers come closer. These properties, together with
the fact from Lemma 3.1 that majority classifiers have larger norms compared
to minorities, is visualized in Fig. 1 for $R=10$ and $k=4$. Additionally,
Fig. 3 shows how all the norms and angles of the geometry vary with the
imbalance ratio $R$ for several values of $k=2,4,10,20.$

######  Remark 3.2 (Asymptotics).

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

###  3.3 Proof sketch

We start from the following (by now, relatively standard) convex relaxation of
the UF-SVM [31, 8, 41, 3]:

$\displaystyle\min_{\mathbf{Z}\in\mathbb{R}^{k\times
n}}\|\mathbf{Z}\|_{*}\quad\text{ subj. to
}~{}\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i]\geq 1,\,\forall c\neq y_{i},i\in[n].$
(5)

The relaxation follows by setting $\mathbf{Z}=\mathbf{W}^{T}{\mathbf{H}}$,
thus $\mathbf{Z}$ is the logit matrix (also, the end-to-end model) of the non-
convex UF-SVM. Our key technical innovation is proving that
${\hat{\mathbf{Z}}}$ is the unique minimizer of (5). There are three key
ingredients in this. First, is a clever re-parameterization of the dual
program to (5), introducing the SEL matrix ${\hat{\mathbf{Z}}}$ in the dual:

$\displaystyle\max_{\mathbf{B}\in\mathbb{R}^{n\times
k}}~{}~{}~{}\operatorname{tr}({\hat{\mathbf{Z}}}\mathbf{B})\quad\text{sub.~{}to}~{}\|\mathbf{B}\|_{2}\leq
1,~{}~{}\mathbf{B}\mathds{1}_{k}=0,~{}~{}\mathbf{B}\odot{\hat{\mathbf{Z}}}^{T}\geq
0\,.$ (6)

Second, we prove that $\hat{\mathbf{B}}=\mathbf{U}\mathbf{V}^{T}$ is the
unique maximizer of the re-parameterized dual problem in (6). While it is not
hard to check that $\hat{\mathbf{B}}$ optimizes a relaxation of (6), it is far
from obvious that $\hat{\mathbf{B}}$ is unique, and, even more that it
satisfies the third constraint. The key technical challenge here is that the
third constraint acts entry-wise on $\mathbf{B}$. In fact, to proceed with the
proof we need that the constraint is _not_ active, i.e.
$\hat{\mathbf{B}}\odot{\hat{\mathbf{Z}}}^{T}>0$, or equivalently, that the
sign pattern of the entries of $\hat{\mathbf{B}}$ agrees with the sign pattern
of the transpose SEL matrix ${\hat{\mathbf{Z}}}^{T}$. We prove this by an
explicit construction of the singular factors $\mathbf{U},\mathbf{V}$
exploiting the structure of the SEL matrix. Once we have shown that
$\hat{\mathbf{B}}$ is the unique maximizer and is strictly feasible, we use
the KKT conditions to prove that ${\hat{\mathbf{Z}}}$ is the unique minimizer
of the nuclear-norm relaxation in (5). To do this, we leverage that strict
feasibility of $\hat{\mathbf{B}}$ implies by complementary slackness all
constraints in the primal (5) must be active at the optimum. The proof of the
theorem completes by arguing that the relaxation (6) is tight when $d\geq k-1$
allowing us to connect the UF-SVM minimizers to the SEL matrix
${\hat{\mathbf{Z}}}$. See Sec. C.1 for details.

######  Remark 3.3 (Comparison to literature).

The common analysis strategy in _all_ other related works is deriving tight
bounds on the CE loss (or related quantities, such as the minimum margin),
and, then identifying the structure in the parameters that achieves those
bounds. For example, [41, 5, 3] lower bound the CE loss and [12] upper bounds
the minimum margin, 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 absence of
symmetry properties (e.g. alignment of classifiers with embeddings). Our proof
of Theorem 1 is more direct and is in large enabled by identifying the key
role played by the logit matrix.

##  4 The role of regularization

In this section, we focus on the ridge-regularized CE loss minimization in
(1). Specifically, we study the geometry of solutions
$({\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda})$ as a function
of both the imbalance and the regularization parameter ${\lambda}$.

###  4.1 Global minimizers as solutions to a convex relaxation

The regularized CE minimization in (1) is non-convex. Yet, its landscape is
benign and the global solution can be described in terms of the solution to a
convex relaxation program [41].

######  Theorem 2 (Reformulated from [41]).

Let ${\lambda}>0$, $d>k-1$ and a $(R,\rho)$-STEP imbalance setting. Let
${\hat{\mathbf{Z}}}_{\lambda}\in\mathbb{R}^{k\times n}$ be the unique
minimizer of the convex nuclear-norm-regularized loss minimization,

$\displaystyle{\hat{\mathbf{Z}}}_{\lambda}:=\arg\min_{\mathbf{Z}}\,\mathcal{L}(\mathbf{Z})+{\lambda}\|\mathbf{Z}\|_{*}\,,$
(7)

and, denote
${\hat{\mathbf{Z}}}_{\lambda}=\mathbf{V}_{\lambda}\bm{\Lambda}_{\lambda}\mathbf{U}_{\lambda}^{T}$
its SVD. Any stationary point of (1) satisfies exactly one of the following
two. Either it is a strict saddle, or, it is a global minimizer
$({\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda})$ and satisfies

$\displaystyle\begin{bmatrix}{\hat{\mathbf{W}}}_{\lambda}^{T}\\\
{{\hat{{\mathbf{H}}}}_{\lambda}}^{T}\end{bmatrix}\begin{bmatrix}{\hat{\mathbf{W}}}_{\lambda}&{\hat{{\mathbf{H}}}}_{\lambda}\end{bmatrix}=\begin{bmatrix}\mathbf{V}_{\lambda}\\\
\mathbf{U}_{\lambda}\end{bmatrix}\bm{\Lambda}_{\lambda}\begin{bmatrix}\mathbf{V}_{\lambda}^{T}&\mathbf{U}_{\lambda}^{T}\end{bmatrix}.$
(8)

First, the statement ensures that any first-order method escaping strict
saddles finds a stationary point that is a global minimizer [41]. Moreover, it
describes the structure of the global minimizers of (1) in terms of
${\hat{\mathbf{Z}}}_{\lambda}$, the solution to the _convex_ minimization in
(7). Structurally, the characterization in (8) resembles the characterization
in Theorem 1 regarding the UF-SVM. However, Theorem 1 goes a step further and
gives an _explicit_ form for the logit matrix, namely the SEL matrix
${\hat{\mathbf{Z}}}$. Instead, ${\hat{\mathbf{Z}}}_{\lambda}$ in Theorem 2 is
given implicitly as the solution to a convex program. In the remaining of this
section, we ask: _how does ${\hat{\mathbf{Z}}}_{\lambda}$ compare to
${\hat{\mathbf{Z}}}$ for different values of the regularizer?_ Also, _how does
the answer depend on the imbalance level?_

######  Remark 4.1.

Although not stated explicitly in this form, Theorem 2 is essentially
retrieved from the proof of [41, Theorem 3.2] with two small adjustments.
First, Zhu et al. [41] only considers balanced data. Here, we realize their
proof actually carries over to the imbalanced setting. Second (less
important), we relax their assumption $d>k$ to $d>k-1$ thanks to a simple
observation:
$\mathds{1}_{k}^{T}\nabla_{\mathbf{Z}}\mathcal{L}(\mathbf{Z})=\mathbf{0}$,
hence the CE gradient drops rank (see Sec. E.1 for details).

###  4.2 Regularization matters

For balanced data, previous works have shown that the minimizers
${\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda}$ of (1) satisfy
the __(NC)__ and __(ETF)__ properties (up to scaling by a constant) for
_every_ value of the regularization parameter ${\lambda}>0$ [41] (see also [5,
3, 21].) In our language, for all ${\lambda}>0$, there exists scalar
$\alpha_{\lambda}$ such that a scaling
$(\alpha_{\lambda}{\hat{\mathbf{W}}}_{\lambda},\alpha_{\lambda}{\hat{{\mathbf{H}}}}_{\lambda})$
of any global solution of the regularized CE minimization in (1) satisfies the
ETF geometry. Thus,_for balanced data, up to a global scaling, the geometry
is: (i) insensitive to ${\lambda}>0$ and (ii) the same as that of the UF-SVM
minimizers. _

Here, we show that the situation changes drastically with imbalances: the
regularization now plays a critical role and the solution is never the same as
that of UF-SVM for finite ${\lambda}$.

######  Proposition 1 (Imbalanced data: Regularization matters).

Assume imbalanced data _and_ $k>2$. There does not exist finite $\lambda>0$
and corresponding scaling $\alpha_{\lambda}$ such that the scaled solution
$(\alpha_{\lambda}{\hat{\mathbf{W}}}_{\lambda},\alpha_{\lambda}{\hat{{\mathbf{H}}}}_{\lambda})$
of (1) follows the _(SELI)_ geometry. Equivalently, there does not exist
${\lambda}>0$ and $\alpha_{\lambda}$ such that a scaling of the UF-SVM
solution solves (1).

###### Proof.

The proof relies on Theorem 1 as follows. For the sake of contradiction assume
there exists ${\lambda}>0$ and some $\alpha_{\lambda}>0$ such that the scaled
UF-SVM minimizer
$(\alpha_{\lambda}{\hat{\mathbf{W}}},\alpha_{\lambda}{\hat{{\mathbf{H}}}})$
solves (1). Since then
$(\alpha_{\lambda}{\hat{\mathbf{W}}},\alpha_{\lambda}{\hat{{\mathbf{H}}}})$ is
a stationary point, it satisfies

$\displaystyle\nabla_{\mathbf{W}}\mathcal{L}(\alpha_{\lambda}^{2}{\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}})+{\lambda}\alpha_{\lambda}\hat{\mathbf{W}}=0$
$\displaystyle\implies\alpha_{\lambda}{\hat{{\mathbf{H}}}}\,\left(\nabla_{\mathbf{Z}}\mathcal{L}(\alpha_{\lambda}^{2}{\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}})\right)^{T}=-{\lambda}{\hat{\mathbf{W}}}$
$\displaystyle\implies\alpha_{\lambda}{\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}}\,\left(\nabla_{\mathbf{Z}}\mathcal{L}(\alpha_{\lambda}^{2}{\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}})\right)^{T}=-{\lambda}{\hat{\mathbf{W}}}^{T}{\hat{\mathbf{W}}}.$

But, by Theorem 1:
${\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}}={\hat{\mathbf{Z}}}$ and
${\hat{\mathbf{W}}}^{T}{\hat{\mathbf{W}}}=\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}$.
Moreover, thanks to the special structure of ${\hat{\mathbf{Z}}}$ we can check
that
$\nabla_{\mathbf{Z}}\mathcal{L}(\alpha_{\lambda}^{2}{\hat{\mathbf{Z}}})=-\alpha_{\lambda}^{\prime}{\hat{\mathbf{Z}}}$
for
$\alpha_{\lambda}^{\prime}:={k}\big{/}({\exp({\alpha_{\lambda}^{2}})+k-1)}$;
see Lemma A.1(v). With these, and denoting
$\alpha_{\lambda}^{\prime\prime}:=\alpha_{\lambda}\alpha_{\lambda}^{\prime}$,
we arrive at the following about the singular values of ${\hat{\mathbf{Z}}}$:

$\alpha_{\lambda}^{\prime\prime}{\hat{\mathbf{Z}}}{\hat{\mathbf{Z}}}^{T}={\lambda}{\hat{\mathbf{W}}}^{T}{\hat{\mathbf{W}}}\implies\alpha_{\lambda}^{\prime\prime}\mathbf{V}\bm{\Lambda}^{2}\mathbf{V}^{T}={\lambda}\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}\implies\alpha_{\lambda}^{\prime\prime}\bm{\Lambda}^{2}={\lambda}\bm{\Lambda}\implies\bm{\Lambda}=\big{(}{{\lambda}}/{\alpha_{\lambda}^{\prime\prime}}\big{)}\mathds{I}_{k-1}.$

Thus, all singular values of ${\hat{\mathbf{Z}}}$ must be the same. However,
we show in Lemma A.3 that this is _not_ the case unless data are balanced or
$k=2$. Thus, we arrive at a contradiction completing the proof of the
proposition. ∎

###  4.3 Vanishing regularization

As ${\lambda}$ vanishes, it is not hard to check that minimizers diverge in
norm and the relevant question becomes: where do they converge in direction?
The following answers this.

######  Proposition 2 (Regularization path leads to UF-SVM).

Suppose $d>k-1$ and $(R,\rho)$-STEP imbalance. It then holds that
$\lim_{{\lambda}\rightarrow
0}\nicefrac{{{\hat{\mathbf{W}}}_{\lambda}^{T}{\hat{{\mathbf{H}}}}_{\lambda}}}{{{(\|\\\
{\hat{\mathbf{W}}}_{\lambda}\|_{F}^{2}/2+\|{\hat{{\mathbf{H}}}}_{\lambda}\|_{F}^{2}/2)}}}=\nicefrac{{{\hat{\mathbf{Z}}}}}{{\|{\hat{\mathbf{Z}}}\|_{*}}}$.

Put together with the content of the previous section: For balanced data, the
solution is always the same up to global scaling. However, for imbalanced
data, the solution changes with ${\lambda}$ and only in the limit of
${\lambda}\rightarrow 0$ does it align with that of the UF-SVM.

Regarding the proof of the proposition, we note that thanks to Theorems 1 and
2, it suffices that the solution ${\hat{\mathbf{Z}}}_{\lambda}$ of (7)
converges in direction to the SEL matrix ${\hat{\mathbf{Z}}}$; see Proposition
3 in Sec. D. To show this, we critically use from Theorem 1 that
${\hat{\mathbf{Z}}}$ is _unique_ minimizer of (5). See Sec. E.3 for details.
The most closely related results are those of [28, 16], who studied the
regularization path of $p$-norm regularized CE.

###  4.4 Imbalance emphasizes the impact of non-convexity

Recall interpreting the UFM as a two-layer linear net trained on the standard
basis $\mathbf{e}_{i}\in\mathbb{R}^{n}.$ Suppose instead that we train a
simple $k$-class linear classifier $\bm{\Xi}_{k\times n}$ on the same data by
minimizing ridge regularized CE:
$\min_{\bm{\Xi}}~{}\mathcal{L}(\bm{\Xi})+\frac{{\lambda}}{2}\|\bm{\Xi}\|_{F}^{2}.$
It is easy to check that (after scaling) ${\hat{\mathbf{Z}}}$ satisfies first-
order optimality conditions. Thus, the optimal linear classifier is such that
for all ${\lambda}>0$, there exists $\alpha_{\lambda}$ such that
$\hat{\bm{\Xi}}_{\lambda}=\alpha_{\lambda}{\hat{\mathbf{Z}}}$. Contrasting
this to Proposition 1, we find that the end-to-end models minimizing ridge-
regularized CE for a linear versus a two-layer linear network are the same (in
direction) when data are balanced, but differ under imbalances.

##  5 Experiments

In our experiments we choose $(R,\nicefrac{{1}}{{2}})$-STEP imbalances with
varying imalance ratio $R$. In all cases we measure convergence to either the
__(SELI)__ or the __(ETF)__ geometries, in terms of the three metrics below
corresponding to classifiers, embeddings, and logits, respectively. Denote
$\underline{\mathbf{A}}=\nicefrac{{\mathbf{A}}}{{\|\mathbf{A}\|_{F}}}$ the
Euclidean normalization and $\mathbf{G}_{\mathbf{A}}=\mathbf{A}^{T}\mathbf{A}$
the Gram matrix of matrix $\mathbf{A}$.

  * $\square$

Classifiers: We measure
$\|\underline{\mathbf{G}_{\mathbf{W}}}-\underline{\hat{\mathbf{G}}_{\mathbf{W}}}\|_{F}$,
where
$\hat{\mathbf{G}}_{\mathbf{W}}^{\text{ETF}}=\mathds{I}_{k}-\frac{1}{k}\mathds{1}_{k}\mathds{1}_{k}^{T}=:\mathbf{G}^{\star}$
and
$\hat{\mathbf{G}}_{\mathbf{W}}^{\text{SELI}}=\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}$
(see Definition 3).

  * $\square$

Embeddings: Because of the NC property, it suffices to work with the class
means $\bm{\mu}_{c}$ and the corresponding matrix $\mathbf{M}$ of mean
embeddings (see Sec. 3.1.) Specifically, we measure
$\|\underline{\mathbf{G}_{\mathbf{M}}}-\underline{\hat{\mathbf{G}}_{\mathbf{M}}}\|_{F}$,
where $\hat{\mathbf{G}}_{\mathbf{M}}^{\text{ETF}}=\mathbf{G}^{\star}$ and
$\hat{\mathbf{G}}_{\mathbf{M}}^{\text{SELI}}$ is computed from the
$n$-dimensional
$\hat{\mathbf{G}}_{\mathbf{H}}^{\text{SELI}}=\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$
by only keeping the $k$ columns/rows corresponding to the first example of
each class.

  * $\square$

Logits: We measure
$\|\underline{\mathbf{W}^{T}\mathbf{M}}-\underline{\mathbf{G}^{\star}}\|_{F}$.
Note that, when NC holds this metric is essentially analogous to measuring
$\|\underline{\mathbf{W}^{T}{\mathbf{H}}}-\underline{{\hat{\mathbf{Z}}}}\|_{F}.$

Centering for deep-net experiments. In the experiments in Sec. 5.3, when
investigating the embeddings’ geometry, we employ an additional centering of
the class means with their (balanced) global mean. Specifically, we compute
for each $c\in[k]:$ $\overline{\bm{\mu}_{c}}=\bm{\mu}_{c}-\bm{\mu}_{G}$ with
$\bm{\mu}_{G}=\frac{1}{k}\sum_{c\in[k]}\bm{\mu}_{c}$. Thus, at each epoch, we
compute
$\overline{\mathbf{M}}=[\overline{\bm{\mu}_{1}},\overline{\bm{\mu}_{2}},...,\overline{\bm{\mu}_{k}}]\in\mathbb{R}^{d\times
k}$ and compare, after normalization,
$\mathbf{G}_{\mathbf{M}}=\overline{\mathbf{M}}^{T}\overline{\mathbf{M}}$ to
$\hat{\mathbf{G}}_{\mathbf{M}}$, which we calculate as described above for the
ETF and SELI geometries, respectively. On the other hand, for the logits
calculations, we compute $\mathbf{Z}=\mathbf{W}^{T}\mathbf{M}$ without
centering. The discrepancy between the UFM solutions being already centered,
while deep-net embeddings require centering before computation of geometric
measures is a common denominator in all previous works on the UFM, e.g. [41,
12, 3, 9, 21, 24, 5, 40]. Here, the chosen centering
$\bm{\mu}_{G}=\frac{1}{k}\sum_{i\in[n]}\frac{1}{n_{y_{i}}}\mathbf{h}_{i}$ is
in general different (and the same only when classes are balanced) from the
global centering $\mathbf{h}_{G}:=\frac{1}{n}\sum_{i\in[n]}\mathbf{h}_{i}$
used by Papyan et al. [26]. Our choice of the former is motivated by the fact
that the SELI geometry (as predicted by the UFM) satisfies
$\sum_{c\in[k]}\overline{\bm{\mu}_{c}}=0$ (see Eqn. (20) in Sec. ), but not
always $\frac{1}{n}\sum_{i\in[n]}{\mathbf{h}_{i}}=0.$

$n/\lambda$Distance to SELI (a) SELI Convergence.

$n/\lambda$Min. margin (b) Minimum margin.

$n/\lambda$Distance to ETF (c) ETF convergence.

Figure 4: Numerical study of global solutions
$({\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda})$ of (1) across
the regularization path.

###  5.1 UFM: Global minimizers

Fig. 4 numerically investigates the behavior of global minimizers of
regularized CE (1) for the UFM and $k=4$ classes. Thanks to Theorem 2, we
obtain such minimizers by solving the convex program (7) with CVX [6], and
then, using (8) to infer the Gram matrices
$\mathbf{G}_{\mathbf{W}},\mathbf{G}_{\mathbf{M}}$ and logits
$\mathbf{W}^{T}{\mathbf{H}}$. Fig. 4(c) shows that the distance to ETF is
large and not approaching zero for any value of ${\lambda}$. On the other
hand, Fig. 4(a) numerically validates Propositions 1 and 2: the distance to
SELI for all three metrics is non-zero for any finite ${\lambda}>0$, but
converges to zero as ${\lambda}\rightarrow 0$. However, this convergence is
slow and the rate becomes even worse as $R$ increases. Finally, Fig. 4(b)
depicts the minimum margins of solutions across ${\lambda}$. Note that for all
sufficiently small ${\lambda}$ values, the minimum margin is strictly
positive. We prove this in Lemma D.4 in Sec. D.2. As a byproduct, this shows
that the “minority collapse” of [3] can only possibly occur for large
${\lambda}$; see also Sec. H.

EpochsDistance to SELI/ETF (a) Classifiers

Epochs (b) Embeddings

Epochs (c) Logits

Figure 5: Geometry of SGD solutions on minimizing CE for the UFM;
SELI(Solid)/ETF(Dashed).

###  5.2 UFM: SGD solutions

Fig. 5 investigates whether the solutions found by SGD are consistent with the
prediction of Theorem 1 about global minimizers of the UF-SVM. Specifically,
we fix $k=4$ and, for each $R$, we select the sample size $n_{\text{min}}$ for
minorities so that the total number of samples
$n=\big{(}(R+1)/2\big{)}kn_{\text{min}}$ is $\approx 400$. The weights of the
UFM are optimized using SGD with constant learning rate $0.4$, batch size $4$
and no weight decay. We train for $10^{5}$ epochs, much beyond zero training
error and plot the distance to SELI and ETF geometries for classifiers,
embeddings and logits over time. We highlight the following three
observations: (i) SGD iterates favor the SELI, instead of the ETF geometry. As
a matter of fact, the distance to SELI is decreasing with epochs, suggesting
an implicit bias of SGD towards global minimizers of the UF-SVM. (ii) However,
convergence is rather slow and rates get worse with increasing imbalance.
(iii) Also, the embeddings convergence is more elusive compared to that of the
classifiers. Interestingly, the last two observations are reminiscent of the
trends we observed in Fig. 4(a), suggesting connections between regularization
path and (S)GD iterates, worth investigating further.

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

Distance to SELI/ETF

CIFAR10

Distance to SELI/ETF

MNIST

EpochsDistance to SELI/ETF (a) Classifiers

Fashion-MNISTEpochs (b) Embeddings

Epochs (c) Logits

Figure 6: Same setup as Fig. 2 only now training with a VGG-13 model.

###  5.3 Deep-learning experiments

We investigate convergence to the proposed SELI geometry in deep-net training
of $(R,\rho)$-STEP imbalanced MNIST, Fashion-MNIST and CIFAR10 datasets. For
concreteness, we consider here equal number of minorities and majorities, i.e.
$\rho=1/2$. Additional experimental results for other values of the minority
ratio are deferred to Sec. G.3. For all datasets, we keep the same total
number of $n=100\times 50\times 5+50\times 5=25250$ examples across all
different imbalance ratios $R=1,5,10$ and $100$. No data augmentation was used
following [26]. We train two deep architectures, ResNet-18 [10] and VGG-13
[29], and optimize the models using CE loss with SGD over $350$ epochs. In all
experiments, the initial learning rate is set to $0.1$ and decreased by a
factor of $10$ at epochs $120$ and $240$. For ResNet training on MNIST, we
choose smaller initial learning rate $0.05$ which we empirically find that it
interpolates data much faster. Weight decay and momentum are set to $5\times
10^{-4}$ and $0.9$ respectively. Models are trained on a single GPU with a
dataloader batchsize of $128$. To evaluate the learnt geometries, we track the
three metrics that we defined at the beginning of this section. Recall also
that following [26], we first perform a global centering by subtracting from
the mean embeddings their global average.

The convergence to SELI and ETF for the classifiers, (centered) mean-
embeddings, and logits are illustrated in Fig. 2 and 6 for ResNet and VGG
models, respectively. The vertical dashed lines mark the epoch at which the
model reaches zero training error under all imbalance ratios; see Sec. G.1.2
for details. Note that in all plots, the distance to SELI geometry decreases
as training evolves. Also, convergence to the SELI geometry is consistently
better compared to the ETF geometry. However, convergence slows down for
increasing imbalance (see $R=100$). Another interesting observation is that
convergence is worse for the embeddings compared to classifiers. In Sec. G.1.6
we compare individual quadrants of the (normalized)
$\underline{\mathbf{G}_{\mathbf{W}}}$ and
$\underline{\mathbf{G}_{\mathbf{H}}}$ matrices, which facilitates
understanding the _individual_ behavior of majorities and minorities.

In Fig. 7 we focus on predicting the norms of the classifiers. In particular,
we measure the norm ratio of the classifiers during training and compute its
distance from the predicted closed-form SELI characterization in Lemma 3.1. We
see that the (relative) magnitude of the classifiers agrees with the value
predicted by the SELI geometry. Analogous plots for the embeddings’ norms are
given in Sec. G.1.4.

EpochsEpochsEpochsResNetVGGDistance to SELI/ETFCIFAR10MNISTFashion-MNIST
Figure 7: Convergence of classifier norm ratio
($\|\mathbf{w}_{\rm{maj}}\|_{2}/\|\mathbf{w}_{\rm{minor}}\|_{2}$) to SELI
(solid) vs ETF (dashed) for different imbalance levels $R$. The SELI geometry
values are computed as per Lemma 3.1.

##  6 Outlook: Imbalance troubles and opportunities

We propose __(SELI)__ as the class-imbalance-invariant geometry of classifiers
and embeddings learnt by overparameterized models when trained beyond zero
training error. We arrive at it after showing that the UF-SVM global
minimizers follow this geometry. Subsequently, we conjecture that: (C1) GD on
the UFM leads to solutions approaching the SELI geometry asymptotically in the
number of epochs; (C2) training of deep-nets beyond zero training error learns
models that approach the SELI geometry.

Statement (C1) is a conjecture and does not follow from Theorem 1. This is
because GD is only known to converge to KKT points of the non-convex UF-SVM
[22, 12], which are not necessarily global minima. Thus, while Proposition 2
combined with the benign landscape of the corresponding ridge-regularized
minimization, as well as, our experiments suggest its validity, the conjecture
remains to be further investigated.333Relying on [15], Vardi et al. [33]
showed gradient flow finds global minimizers in deep linear nets. However,
these only apply to binary classification. We show that interesting behaviors
might occur (e.g. in the role of regularization and geometry) when $k>2$ and
$R>1$ calling further studies. We also note that convergence rates appear
slower with increasing imbalance levels; a feature which is interesting to
study further.

Regarding conjecture (C2), we deem our experiments encouraging: the
classifiers’ and embeddings’ geometries get closer to the SELI geometry as
neural-network training progresses. Specifically, the Gram matrices
$\mathbf{G}_{\mathbf{W}}$ and $\mathbf{G}_{\mathbf{H}}$ of the classifiers and
embeddings, respectively, align increasingly better with their SELI
counterparts $\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}$ and
$\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$; see Fig. 2. Also, Fig. 7 shows that
Lemma 3.1 is able to make predictions regarding the norms of majorities versus
minorities. We note that, similar to the UFM experiments, convergence appears
slower for larger imbalance ratios. Also, we observe better convergence for
classifiers compared to embeddings and for norm predictions compared to angle
predictions. Overall, we hope our results motivate further theoretical and
experimental investigations, especially since data imbalances appear
frequently across applications.

Beyond that, we believe that further similar studies on identifying geometric
structures of learned embeddings and classifiers could offer new perspectives
on generalization. Our results could pave that way since they uncover
different geometries (aka SELI for different $R$ values), each leading to
different generalization (worse for increasing $R$ [1]). Relatedly, we
envision that further such studies lead to algorithmic contributions in
imbalanced deep-learning as they can facilitate studying the implicit-bias
effect of CE adjustments and post-hoc techniques tailored to imbalanced data
[2, 23, 39, 18, 17, 19, 20].

## References

  * Byrd and Lipton [2019] 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.
  * Cao et al. [2019] K. Cao, C. Wei, A. Gaidon, N. Arechiga, and T. Ma.  Learning imbalanced datasets with label-distribution-aware margin loss.  In _Advances in Neural Information Processing Systems_ , pages 1567–1578, 2019.
  * Fang et al. [2021] 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 National Academy of Sciences_ , 118(43), 2021.
  * Galanti et al. [2021] T. Galanti, A. György, and M. Hutter.  On the role of neural collapse in transfer learning.  _arXiv preprint arXiv:2112.15121_ , 2021.
  * Graf et al. [2021] F. Graf, C. Hofer, M. Niethammer, and R. Kwitt.  Dissecting supervised constrastive learning.  In _International Conference on Machine Learning_ , pages 3821–3830. PMLR, 2021.
  * Grant and Boyd [2014] M. Grant and S. Boyd.  CVX: Matlab software for disciplined convex programming, version 2.1.  http://cvxr.com/cvx, Mar. 2014.
  * Gunasekar et al. [2018] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro.  Characterizing implicit bias in terms of optimization geometry.  In _International Conference on Machine Learning_ , pages 1832–1841. PMLR, 2018.
  * Haeffele and Vidal [2019] B. D. Haeffele and R. Vidal.  Structured low-rank matrix factorization: Global optimality, algorithms, and applications.  _IEEE transactions on pattern analysis and machine intelligence_ , 42(6):1468–1482, 2019.
  * Han et al. [2021] X. Han, V. Papyan, and D. L. Donoho.  Neural collapse under mse loss: Proximity to and dynamics on the central path.  _arXiv preprint arXiv:2106.02073_ , 2021.
  * He et al. [2015] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition." computer vision and pattern recognition (2015).  _Google Scholar There is no corresponding record for this reference_ , pages 770–778, 2015.
  * Hui et al. [2022] L. Hui, M. Belkin, and P. Nakkiran.  Limitations of neural collapse for understanding generalization in deep learning.  _arXiv preprint arXiv:2202.08384_ , 2022.
  * Ji et al. [2021] W. Ji, Y. Lu, Y. Zhang, Z. Deng, and W. J. Su.  An unconstrained layer-peeled perspective on neural collapse.  _arXiv preprint arXiv:2110.02796_ , 2021.
  * Ji and Telgarsky [2018] Z. Ji and M. Telgarsky.  Risk and parameter convergence of logistic regression.  _arXiv preprint arXiv:1803.07300_ , 2018.
  * Ji and Telgarsky [2019] Z. Ji and M. Telgarsky.  The implicit bias of gradient descent on nonseparable data.  In _Conference on Learning Theory_ , pages 1772–1798. PMLR, 2019\.
  * Ji and Telgarsky [2020] Z. Ji and M. Telgarsky.  Directional convergence and alignment in deep learning.  _Advances in Neural Information Processing Systems_ , 33:17176–17186, 2020.
  * Ji et al. [2020] Z. Ji, M. Dudík, R. E. Schapire, and M. Telgarsky.  Gradient descent follows the regularization path for general losses.  In _Conference on Learning Theory_ , pages 2109–2136. PMLR, 2020\.
  * Kang et al. [2020] B. Kang, S. Xie, M. Rohrbach, Z. Yan, A. Gordo, J. Feng, and Y. Kalantidis.  Decoupling representation and classifier for long-tailed recognition, 2020\.
  * Kim and Kim [2020] B. Kim and J. Kim.  Adjusting decision boundary for class imbalanced learning.  _IEEE Access_ , 8:81674–81685, 2020.  doi: 10.1109/ACCESS.2020.2991231.
  * Kini et al. [2021] G. R. Kini, O. Paraskevas, S. Oymak, and C. Thrampoulidis.  Label-imbalanced and group-sensitive classification under overparameterization.  _Advances in Neural Information Processing Systems_ , 34:18970–18983, 2021.
  * Li et al. [2021] M. Li, X. Zhang, C. Thrampoulidis, J. Chen, and S. Oymak.  Autobalance: Optimized loss functions for imbalanced data.  _Advances in Neural Information Processing Systems_ , 34:3163–3177, 2021.
  * Lu and Steinerberger [2020] J. Lu and S. Steinerberger.  Neural collapse with cross-entropy loss.  _arXiv preprint arXiv:2012.08465_ , 2020.
  * Lyu and Li [2019] K. Lyu and J. Li.  Gradient descent maximizes the margin of homogeneous neural networks.  _arXiv preprint arXiv:1906.05890_ , 2019.
  * Menon et al. [2020] A. K. Menon, S. Jayasumana, A. S. Rawat, H. Jain, A. Veit, and S. Kumar.  Long-tail learning via logit adjustment.  _arXiv preprint arXiv:2007.07314_ , 2020.
  * Mixon et al. [2020] D. G. Mixon, H. Parshall, and J. Pi.  Neural collapse with unconstrained features.  _arXiv preprint arXiv:2011.11619_ , 2020.
  * Nacson et al. [2019] M. S. Nacson, J. Lee, S. Gunasekar, P. H. P. Savarese, N. Srebro, and D. Soudry.  Convergence of gradient descent on separable data.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 3420–3428. PMLR, 2019.
  * Papyan et al. [2020] V. Papyan, X. Han, and D. L. Donoho.  Prevalence of neural collapse during the terminal phase of deep learning training.  _Proceedings of the National Academy of Sciences_ , 117(40):24652–24663, 2020.
  * Peng et al. [2016] X. Peng, C. Lu, Z. Yi, and H. Tang.  Connections between nuclear-norm and frobenius-norm-based representations.  _IEEE transactions on neural networks and learning systems_ , 29(1):218–224, 2016.
  * Rosset et al. [2003] S. Rosset, J. Zhu, and T. Hastie.  Margin maximizing loss functions.  In _NIPS_ , pages 1237–1244, 2003.
  * Simonyan and Zisserman [2014] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Soudry et al. [2018] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro.  The implicit bias of gradient descent on separable data.  _The Journal of Machine Learning Research_ , 19(1):2822–2878, 2018.
  * Srebro et al. [2004] N. Srebro, J. Rennie, and T. Jaakkola.  Maximum-margin matrix factorization.  _Advances in neural information processing systems_ , 17, 2004.
  * Tirer and Bruna [2022] T. Tirer and J. Bruna.  Extended unconstrained features model for exploring deep neural collapse.  _arXiv preprint arXiv:2202.08087_ , 2022.
  * Vardi et al. [2021] G. Vardi, O. Shamir, and N. Srebro.  On margin maximization in linear and relu networks.  _arXiv preprint arXiv:2110.02732_ , 2021.
  * Vidal and Favaro [2014] R. Vidal and P. Favaro.  Low rank subspace clustering (lrsc).  _Pattern Recognition Letters_ , 43:47–61, 2014.
  * Wang et al. [2021] K. Wang, V. Muthukumar, and C. Thrampoulidis.  Benign overfitting in multiclass classification: All roads lead to interpolation.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Wright and Ma [2022] J. Wright and Y. Ma.  _High-dimensional data analysis with low-dimensional models: Principles, computation, and applications_.  Cambridge University Press, 2022.
  * Xie et al. [2022] 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.
  * Yang et al. [2022] Y. Yang, L. Xie, S. Chen, X. Li, Z. Lin, and D. Tao.  Do we really need a learnable classifier at the end of deep neural network?  _arXiv preprint arXiv:2203.09081_ , 2022.
  * Ye et al. [2020] H.-J. Ye, H.-Y. Chen, D.-C. Zhan, and W.-L. Chao.  Identifying and compensating for feature deviation in imbalanced deep learning, 2020.
  * Zhou et al. [2022] J. Zhou, X. Li, T. Ding, C. You, Q. Qu, and Z. Zhu.  On the optimization landscape of neural collapse under mse loss: Global optimality with unconstrained features.  _arXiv preprint arXiv:2203.01238_ , 2022.
  * Zhu et al. [2021] Z. Zhu, T. Ding, J. Zhou, X. Li, C. You, J. Sulam, and Q. Qu.  A geometric analysis of neural collapse with unconstrained features.  _Advances in Neural Information Processing Systems_ , 34, 2021.

## Roadmap to the Supplementary material

The SM contains the following. In Section A we derive several useful
properties of the simplex-encoded-label (SEL) matrix, which we then use in
Section B to present closed-form characterizations of the embeddings and
classifiers geometries. Notably, these include explicit expressions for the
norms and angles of both majority and minority classes, which we accompany
with numerical illustrations shedding further light on the features of the
proposed __(SELI)__ geometry. Next, in Section C, we use the derived
properties of the SEL matrix to prove our main Theorem 1 and its corollaries.
In Section D we derive several useful properties of the nuclear-norm penalized
CE minimization, which we then use in Section E to prove the statements of
Section 4. Section F contains additional numerical results on the UFM, such as
experiments with varying weight-decay and regularization choices. Additional
experiments on real data (such as, isolated minority/majority geometry
investigations, and classifiers/embeddings norm ratios), as well as further
implementation details, are included in Section G. In Section H we show how
results relate to minority collapse providing additional theoretical
justifications and novel perspectives to empirical observations reported by
previous work. Finally, an elaborate discussion on additional related works is
contained in Section I.

###### Contents

  1. 1 Introduction
    1. 1.1 Related works
    2. 1.2 Organization
  2. 2 Problem setup
    1. 2.1 Unconstrained-features SVM (UF-SVM)
    2. 2.2 Class-imbalance model
  3. 3 Global structure of the UF-SVM: SELI geometry
    1. 3.1 Invariant properties: NC and SELI
      1. 3.1.1 Special case: Balanced or binary data
    2. 3.2 How the SELI geometry changes with imbalances
    3. 3.3 Proof sketch
  4. 4 The role of regularization
    1. 4.1 Global minimizers as solutions to a convex relaxation
    2. 4.2 Regularization matters
    3. 4.3 Vanishing regularization
    4. 4.4 Imbalance emphasizes the impact of non-convexity
  5. 5 Experiments
    1. 5.1 UFM: Global minimizers
    2. 5.2 UFM: SGD solutions
    3. 5.3 Deep-learning experiments
  6. 6 Outlook: Imbalance troubles and opportunities
  7. A Properties of the SEL matrix
    1. A.1 Basic facts
    2. A.2 Eigen-structure
      1. A.2.1 Special case: Balanced data
      2. A.2.2 Special case: Equal minorities / majorities ($\rho=1/2$)
    3. A.3 A useful property of the singular spaces
  8. B The SELI geometry
    1. B.1 Closed-form expressions
      1. B.1.1 Norms
      2. B.1.2 Angles
      3. B.1.3 (Non)-alignment
      4. B.1.4 Centering
    2. B.2 Illustrations and discussion on dependence on $R$ and $k$
    3. B.3 Special cases
      1. B.3.1 Balanced classes and binary classification
      2. B.3.2 Asymptotics
  9. C Proofs for UF-SVM Section 3
    1. C.1 Proof of Theorem 1
    2. C.2 Proofs of Corollaries 1.1, 1.2, 1.3 and of Lemma 3.1
    3. C.3 On different regularization hyperparameters between embeddings and classifiers
  10. D Nuclear-norm relaxations of the UFM
    1. D.1 Large ${\lambda}$
    2. D.2 Small ${\lambda}$
    3. D.3 Vanishing ${\lambda}$
      1. D.3.1 Proof of Proposition 3
  11. E Proofs for Regularized CE Section 4
    1. E.1 Proof of Theorem 2
    2. E.2 Proof of Proposition 1
    3. E.3 Proof of Proposition 2
    4. E.4 Comparison to one-layer linear model
  12. F Additional results on UFM
    1. F.1 Experiments with weight-decay
    2. F.2 Logit regularization and Ridge-decay
  13. G Additional results on real data
    1. G.1 Missing details on experiments of Section 5.3
      1. G.1.1 Implementation details
      2. G.1.2 Model accuracies
      3. G.1.3 NC property
      4. G.1.4 Norms of classifiers / embeddings
      5. G.1.5 Non-alignment of classifiers and embeddings
      6. G.1.6 Majority vs minority geometry
    2. G.2 Capturing weight-decay with regularized UFM
    3. G.3 Additional experiments for minority ratios $\rho\neq 1/2$
  14. H Implications on minority collapse
  15. I Additional related work
    1. I.1 Additional works on Neural Collapse
    2. I.2 Implicit bias
    3. I.3 Matrix factorization and low-rank recovery
    4. I.4 Class-imbalanced deep learning
    5. I.5 On the Simplex-encoding interpolation

##  Appendix A Properties of the SEL matrix

###  A.1 Basic facts

We gather some basic properties about the SEL matrix below. These properties
hold without any assumptions on the number of examples $n_{1},\ldots,n_{k}$
per class other than $n_{c}\geq 1,\forall c\in[k].$

######  Lemma A.1 (SEL matrix — Basic Facts).

The following statements are true.

  1. (i)

Let $\mathbf{Y}$ be the zero-one hot encoding label matrix, i.e.
$\mathbf{Y}[c,i]=\begin{cases}1&,\,c=y_{i}\\\ 0&,\,c\neq
y_{i}\end{cases},~{}\forall c\in[k],i\in[n].$ Then,
${\hat{\mathbf{Z}}}=\mathbf{Y}-\frac{1}{k}\mathds{1}_{k}\mathds{1}_{n}^{T}$.

  2. (ii)

${\hat{\mathbf{Z}}}^{T}\mathds{1}_{k}=0$ and
$\operatorname{rank}({\hat{\mathbf{Z}}})=k-1$.

  3. (iii)

${\hat{\mathbf{Z}}}^{T}$ admits a compact SVD
${\hat{\mathbf{Z}}}^{T}=\mathbf{U}\bm{\Lambda}\mathbf{V}^{T}$, such that
$\bm{\Lambda}$ is a $(k-1)$-diagonal, and
$\mathbf{U}\in\mathbb{R}^{n\times(k-1)}$,
$\mathbf{V}\in\mathbb{R}^{k\times(k-1)}$ are partial orthogonal matrices, i.e.
$\mathbf{U}^{T}\mathbf{U}=\mathbf{V}^{T}\mathbf{V}=\mathds{I}_{k-1}$. Moreover
$\mathbf{V}^{T}\mathds{1}_{k}=0,$ and the $k-1$ columns of $\mathbf{V}$ span
the subspace orthogonal to $\mathds{1}_{k}$, i.e.
$\mathbf{V}\mathbf{V}^{T}=\mathds{I}_{k}-\frac{1}{k}\mathds{1}_{k}\mathds{1}_{k}^{T}.$

  4. (iv)

${\hat{\mathbf{Z}}}^{T}{\hat{\mathbf{Z}}}=\mathbf{Y}^{T}\mathbf{Y}-\frac{1}{k}\mathds{1}\mathds{1}^{T}$
and
${\hat{\mathbf{Z}}}{\hat{\mathbf{Z}}}^{T}=\operatorname{diag}(\mathbf{n})+\frac{n}{k^{2}}\mathds{1}_{k}\mathds{1}_{k}^{T}-\frac{1}{k}\mathbf{n}\mathds{1}_{k}^{T}-\frac{1}{k}\mathds{1}_{k}\mathbf{n}^{T}$,
where we defined $\mathbf{n}=[n_{1},n_{2},\ldots,n_{k}]^{T}$

  5. (v)

Let $\mathcal{L}(\mathbf{Z})=\sum_{i\in[n]}\log\big{(}1+\sum_{c\neq
y_{i}}e^{-(\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i])}\big{)}$. Then,
$\nabla_{\mathbf{Z}}\mathcal{L}(\alpha{\hat{\mathbf{Z}}})=-\frac{k}{e^{\alpha}+k-1}{\hat{\mathbf{Z}}}$,
for all $\alpha\in\mathbb{R}$.

###### Proof.

Proof of (i): Follows directly from the definition.

Proof of (ii): The fact that ${\hat{\mathbf{Z}}}^{T}\mathds{1}_{k}=0$ is easy
to check. Hence, the rank is at most $k-1$. The fact that the rank is exactly
$k-1$ follows by noting that the vectors
$\mathbf{e}_{c}-\frac{1}{k}\mathds{1}_{k},c\in[k-1]$ are linearly independent.

Proof of (iii): Follows directly from Statement (ii).

Proof of (iv): Follows easily by direct calculations.

Proof of (v): We show in Lemma A.2 below that
$-\nabla_{\mathbf{Z}}\mathcal{L}(\mathbf{Z})=\mathbf{Y}-\mathbf{A}$ with
$\mathbf{A}[c,i]:=\frac{e^{-(\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i])}}{1+\sum_{c^{\prime}\neq
y_{i}}e^{-(\mathbf{Z}[y_{i},i]-\mathbf{Z}[c^{\prime},i])}}.$ It is easy to see
that for $\mathbf{Z}=\alpha{\hat{\mathbf{Z}}}$, the matrix $\mathbf{A}$ can be
written as
$\mathbf{A}=\frac{e^{\alpha}-1}{k-1+e^{\alpha}}\mathbf{Y}+\frac{1}{k-1+e^{\alpha}}\mathds{1}_{k}\mathds{1}_{n}^{T}$.
The desired then follows by recalling Statement (i). ∎

######  Lemma A.2 (Auxiliary result—Gradient of CE).

The negative gradient of the cross-entropy loss
$\mathcal{L}(\mathbf{Z})=\sum_{i=1}^{n}\log\left(1+\sum_{c\neq
y_{i}}e^{-(\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i])}\right)$ takes the form
$-\nabla_{\mathbf{Z}}\mathcal{L}(\mathbf{Z})=\mathbf{Y}-\mathbf{A}$ where
$\mathbf{Y}$ is the one-hot encoding label matrix and for $i\in[n],c\in[k]$ we
denote
$\mathbf{A}[c,i]:=\frac{e^{-(\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i])}}{1+\sum_{c^{\prime}\neq
y_{i}}e^{-(\mathbf{Z}[y_{i},i]-\mathbf{Z}[c^{\prime},i])}}$. Thus, for any
$\mathbf{Z}\in\mathbb{R}^{k\times n}$, it holds that
$\mathds{1}_{k}^{T}\nabla_{\mathbf{Z}}\mathcal{L}(\mathbf{Z})=\mathbf{0}$.

###### Proof.

The proof is straightforward. Denote for convenience,
$Z_{ci}:=\mathbf{Z}[c,i]$ and $s_{ci}:=\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i]$.
Taking derivatives with respect to $Z_{ci},c\in[k]$ we have for $c=y_{i}$,

$\frac{\partial\mathcal{L}}{\partial Z_{y_{i}i}}=-\frac{\sum_{c^{\prime}\neq
y_{i}}e^{-s_{c^{\prime}i}}}{1+\sum_{c^{\prime\prime}\neq
y_{i}}e^{-s_{c^{\prime\prime}i}}}\frac{\partial s_{c^{\prime}i}}{\partial
Z_{y_{i}i}}=-\frac{\sum_{c^{\prime}\neq
y_{i}}e^{-s_{c^{\prime}i}}}{1+\sum_{c^{\prime\prime}\neq
y_{i}}e^{-s_{c^{\prime\prime}i}}}=-\Big{(}1-\frac{1}{1+\sum_{c^{\prime}\neq
y_{i}}e^{-s_{c^{\prime}i}}}\Big{)}=-(1-\mathbf{A}[y_{i},i])$

and, for $c\neq y_{i}$,

$\frac{\partial\mathcal{L}}{\partial
Z_{ci}}=-\frac{e^{-s_{ci}}}{1+\sum_{c^{\prime}\neq
y_{i}}e^{-s_{c^{\prime}i}}}\frac{\partial s_{ci}}{\partial
Z_{ci}}=\frac{e^{-s_{ci}}}{1+\sum_{c^{\prime}\neq
y_{i}}e^{-s_{c^{\prime}i}}}=\mathbf{A}[c,i].$

Thus, $\sum_{c=1}^{k}\frac{\partial\mathcal{L}}{\partial Z_{ci}}=0,\forall
i\in[n]$. Hence,
$\mathds{1}_{k}^{T}\nabla_{\mathbf{Z}}\mathcal{L}(\mathbf{Z})=\mathbf{0}$ for
every $\mathbf{Z}$. ∎

###  A.2 Eigen-structure

In this section, we explicitly compute the eigenstructure of the SEL matrix
for $(R,\rho)$-STEP imbalanced data. To simplify the expressions, we assume
$n_{\min}=1$. 444It is rather easy to derive all formulas without this
requirement. Concretely, the singular values in (9) are multiplied by
$\sqrt{n_{\min}}$, the $(1,1)$– and $(2,3)$– blocks of $\mathbf{U}$ in (11)
are multiplied by $1/\sqrt{n_{\min}}$ and the dimensions of $\mathbf{U}$ also
adjust appropriately. Nevertheless, this does not change the values of
$\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$ and of
$\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}$ aside from a global scaling. Besides,
the assumption $n_{\text{min}}=1$ is essentially without loss of generality
because the __(NC)__ property holds under the SELI property. Also, we need the
following definitions. For $m\in[k]$, let
$\mathds{P}_{m}\in\mathbb{R}^{m\times(m-1)}$ denote an orthonormal basis of
the subspace orthogonal to $\mathds{1}_{m}$, i.e.
$\mathds{P}_{m}\mathds{P}_{m}^{T}=\mathds{I}_{m}-\frac{1}{m}\mathds{1}_{m}\mathds{1}_{m}^{T}$
and $\mathds{P}_{m}^{T}\mathds{P}_{m}=\mathds{I}_{m-1}.$ We will also denote
$\mathbf{S}_{m}:=\mathds{I}_{m}-\frac{1}{k}\mathds{1}_{m}\mathds{1}_{m}^{T}\in\mathbb{R}^{m}.$

######  Lemma A.3 (SEL matrix — SVD for STEP imbalance).

Assume $(R,\rho)$-STEP imbalanced data and $n_{\min}=1$. Also, denote
$\overline{\rho}=1-\rho$ and recall that the total number of examples is
$n=(\rho+R\overline{\rho})k.$ Then, the SVD factors of
${\hat{\mathbf{Z}}}=\mathbf{V}\bm{\Lambda}\mathbf{U}^{T}$ are given as
follows:

$\displaystyle\bm{\Lambda}=\operatorname{diag}{\left(\begin{bmatrix}\sqrt{R}\mathds{1}_{(\overline{\rho}k-1)}^{T}&\sqrt{\overline{\rho}+R\rho}&\mathds{1}_{(\rho
k-1)}^{T}\end{bmatrix}\right)}\,$ (9) $\displaystyle\mathbf{V}$
$\displaystyle=\begin{bmatrix}\mathds{P}_{\overline{\rho}k}&-\sqrt{\frac{\rho/\overline{\rho}}{k}}\,\mathds{1}_{\overline{\rho}k}&0_{(\overline{\rho}k)\times{(\rho
k-1)}}\\\ 0_{(\rho
k)\times{(\overline{\rho}k-1)}}&\sqrt{\frac{\overline{\rho}/\rho}{k}}\mathds{1}_{\rho
k}&\mathds{P}_{\rho k}\end{bmatrix}$ (10) $\displaystyle\mathbf{U}$
$\displaystyle=\begin{bmatrix}\frac{1}{\sqrt{R}}\mathds{P}_{\overline{\rho}k}\otimes\mathds{1}_{R}&-\sqrt{\frac{\rho/\overline{\rho}}{(\overline{\rho}+R\rho)k}}\mathds{1}_{R\overline{\rho}k}&0_{(R\overline{\rho}k)\times{(\rho
k-1)}}\\\ 0_{(\rho
k)\times{(\overline{\rho}k-1)}}&\sqrt{\frac{\overline{\rho}/\rho}{(\overline{\rho}+R\rho)k}}\mathds{1}_{\rho
k}&\mathds{P}_{\rho k}\end{bmatrix}\,.$ (11)

###### Proof.

The challenging part is coming up with the formulas in (9), (10) and (11) for
the SVD factors. The lemma already does this for us. Hence, proving that the
formulas are correct involves a few tedious calculations, which we present
below.

Let us define for convenience:

$\displaystyle\mathbf{V}_{\text{maj}}:=\begin{bmatrix}\mathds{P}_{\overline{\rho}k}\\\
0_{(\rho
k)\times{(\overline{\rho}k-1)}}\end{bmatrix}\quad\mathbf{v}=\frac{1}{\sqrt{k}}\begin{bmatrix}-\sqrt{\frac{\rho}{\overline{\rho}}}\mathds{1}_{\overline{\rho}k}\\\
\sqrt{\frac{\overline{\rho}}{\rho}}\mathds{1}_{\rho
k}\end{bmatrix}\quad\mathbf{V}_{\text{min}}:=\begin{bmatrix}0_{(\overline{\rho}k)\times{(\rho
k-1)}}\\\ \mathds{P}_{\rho k}\end{bmatrix}$

so that
$\mathbf{V}=[\mathbf{V}_{\text{maj}},\mathbf{v},\mathbf{V}_{\text{min}}]$.
Recalling for $m=\overline{\rho}k$ or $m=\rho k$ that
$\mathds{P}_{m}^{T}\mathds{P}_{m}=\mathds{I}_{m-1}$ and
$\mathds{P}_{m}^{T}\mathds{1}_{m}=0$ it is easy to check that
$\mathbf{V}^{T}\mathbf{V}=\mathds{I}_{k-1}.$

Similarly, let

$\displaystyle\mathbf{U}_{\text{maj}}:=\begin{bmatrix}\frac{1}{\sqrt{R}}\mathds{P}_{\overline{\rho}k}\otimes\mathds{1}_{R}\\\
0_{(\rho
k)\times{(\overline{\rho}k-1)}}\end{bmatrix}\quad\mathbf{u}=\frac{1}{\sqrt{(\overline{\rho}+R\rho)k}}\begin{bmatrix}-\sqrt{\frac{\rho}{\overline{\rho}}}\mathds{1}_{R\overline{\rho}k}\\\
\sqrt{\frac{\overline{\rho}}{\rho}}\mathds{1}_{\rho
k}\end{bmatrix}\quad\mathbf{U}_{\text{min}}:=\begin{bmatrix}0_{(R\overline{\rho}k)\times{(\rho
k-1)}}\\\ \mathds{P}_{\rho k}\end{bmatrix}$

so that
$\mathbf{U}=[\mathbf{U}_{\text{maj}},\mathbf{u},\mathbf{U}_{\text{min}}]$.
With same argument as above, it is easy to check that
$\mathbf{U}^{T}\mathbf{U}=\mathds{I}_{k-1}.$ Here, we also use that

$\displaystyle\frac{1}{R}(\mathds{P}_{\overline{\rho}k}\otimes\mathds{1}_{R})^{T}(\mathds{P}_{\overline{\rho}k}\otimes\mathds{1}_{R})=\frac{1}{R}(\mathds{P}_{\overline{\rho}k}^{T}\otimes\mathds{1}_{R}^{T})(\mathds{P}_{\overline{\rho}k}\otimes\mathds{1}_{R})=\frac{1}{R}\mathds{P}_{\overline{\rho}k}^{T}\mathds{P}_{\overline{\rho}k}\otimes\mathds{1}_{R}^{T}\mathds{1}_{R}=\mathds{I}_{\overline{\rho}k}$

Thus, it suffices to show that
$\mathbf{V}\bm{\Lambda}\mathbf{U}^{T}={\hat{\mathbf{Z}}}.$ The key observation
here is that ${\hat{\mathbf{Z}}}$ can be written in block-form as follows

$\displaystyle{\hat{\mathbf{Z}}}=\begin{bmatrix}\mathbf{S}_{\overline{\rho}k}\otimes\mathds{1}_{R}^{T}&-\frac{1}{k}\mathds{1}_{\overline{\rho}k}\mathds{1}^{T}_{\rho
k}\\\ -\frac{1}{k}\mathds{1}_{\rho
k}\mathds{1}^{T}_{R\overline{\rho}k}&\mathbf{S}_{\rho k}\end{bmatrix}.$ (12)

With these, we have the following direct calculations:

$\displaystyle\mathbf{V}\bm{\Lambda}\mathbf{U}^{T}$
$\displaystyle=\sqrt{R}\mathbf{V}_{\text{maj}}\mathbf{U}_{\text{maj}}^{T}+\big{(}\sqrt{\overline{\rho}+R\rho}\big{)}\mathbf{v}\mathbf{u}^{T}+\mathbf{V}_{\text{min}}\mathbf{U}_{\text{min}}^{T}$
$\displaystyle=\begin{bmatrix}\mathds{P}_{\overline{\rho}k}\mathds{P}_{\overline{\rho}k}^{T}\otimes\mathds{1}_{R}^{T}&0\\\
0&0\end{bmatrix}+\frac{1}{k}\begin{bmatrix}\frac{\rho}{\overline{\rho}}\mathds{1}_{\overline{\rho}k}\mathds{1}_{R\overline{\rho}k}^{T}&-\mathds{1}_{\overline{\rho}k}\mathds{1}_{\rho
k}^{T}\\\ -\mathds{1}_{\rho
k}\mathds{1}_{R\overline{\rho}k}^{T}&\frac{\overline{\rho}}{\rho}\mathds{1}_{\rho
k}\mathds{1}_{\rho k}^{T}\end{bmatrix}+\begin{bmatrix}0&0\\\
0&\mathds{P}_{\rho k}\mathds{P}_{\rho k}^{T}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\big{(}\mathds{I}_{\overline{\rho}k}-\frac{1}{\overline{\rho}k}\mathds{1}_{\overline{\rho}k}\mathds{1}_{\overline{\rho}k}^{T}\big{)}\otimes\mathds{1}_{R}^{T}&0\\\
0&0\end{bmatrix}+\frac{1}{k}\begin{bmatrix}\frac{\rho}{\overline{\rho}}\mathds{1}_{\overline{\rho}k}\mathds{1}_{\overline{\rho}k}^{T}\otimes\mathds{1}_{R}^{T}&-\mathds{1}_{\overline{\rho}k}\mathds{1}_{\rho
k}^{T}\\\ -\mathds{1}_{\rho
k}\mathds{1}_{R\overline{\rho}k}^{T}&\frac{\overline{\rho}}{\rho}\mathds{1}_{\rho
k}\mathds{1}_{\rho k}^{T}\end{bmatrix}+\begin{bmatrix}0&0\\\
0&\mathds{I}_{\rho k}-\frac{1}{\rho k}\mathds{1}_{\rho k}\mathds{1}_{\rho
k}^{T}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\big{(}\mathds{I}_{\overline{\rho}k}-\frac{1}{k}\mathds{1}_{\overline{\rho}k}\mathds{1}_{\overline{\rho}k}^{T}\big{)}\otimes\mathds{1}_{R}^{T}&-\frac{1}{k}\mathds{1}_{\overline{\rho}k}\mathds{1}_{\rho
k}^{T}\\\ -\frac{1}{k}\mathds{1}_{\rho
k}\mathds{1}_{R\overline{\rho}k}^{T}&\mathds{I}_{\rho
k}-\frac{1}{k}\mathds{1}_{\rho k}\mathds{1}_{\rho k}^{T}\end{bmatrix}$
$\displaystyle={\hat{\mathbf{Z}}}.$

∎

####  A.2.1 Special case: Balanced data

When classes are balanced, i.e. $R=1$, the following simple description of the
SVD factors is immediate to see from Lemma A.3.

######  Corollary 2.1.

Assume balanced data and $n_{\min}=1$. Recall that
$\mathds{P}_{k}\in\mathbb{R}^{k\times(k-1)}$ denotes an orthonormal basis of
the subspace orthogonal to $\mathds{1}_{k}$. Then,
${\hat{\mathbf{Z}}}=\mathds{P}_{k}\mathds{P}_{k}^{T}$, that is

$\bm{\Lambda}=\mathds{I}_{k-1},\quad\mathbf{U}=\mathbf{V}=\mathds{P}_{k}.$

####  A.2.2 Special case: Equal minorities / majorities ($\rho=1/2$)

Another special case of interest is when the numbers of minorities and
majorities are the same, i.e. $\rho=1/2$. In this case, we get the following
simplification of Lemma A.3.

######  Corollary 2.2.

Consider the setting of step imbalance with even number $k=2m,m\geq 1$ of
classes. Let $n_{\min}=1$. Then, the SVD of ${\hat{\mathbf{Z}}}$ is as
follows:

$\displaystyle\bm{\Lambda}$
$\displaystyle=\operatorname{diag}{\left(\begin{bmatrix}\sqrt{R}\mathds{1}_{(m-1)}^{T}&\sqrt{(R+1)/2}&\mathds{1}_{(m-1)}^{T}\end{bmatrix}\right)}\,,$
$\displaystyle\mathbf{V}$
$\displaystyle=\begin{bmatrix}\mathds{P}_{m}&-\frac{1}{\sqrt{k}}\mathds{1}_{m}&0_{m\times{(m-1)}}\\\
0_{m\times{(m-1)}}&+\frac{1}{\sqrt{k}}\mathds{1}_{m}&\mathds{P}_{m}\end{bmatrix}$
$\displaystyle\mathbf{U}$
$\displaystyle=\begin{bmatrix}\frac{1}{\sqrt{R}}\mathds{P}_{m}\otimes\mathds{1}_{R}&-\frac{1}{\sqrt{n}}\mathds{1}_{Rm}&0_{(Rm)\times{(m-1)}}\\\
0_{m\times{(m-1)}}&+\frac{1}{\sqrt{n}}\mathds{1}_{m}&\mathds{P}_{m}\end{bmatrix}\,.$

###  A.3 A useful property of the singular spaces

The following result is particularly important for the proof of Theorem 1. It
shows that the singular spaces $\mathbf{V},\mathbf{U}$ of ${\hat{\mathbf{Z}}}$
are such that the matrix $\mathbf{U}\mathbf{V}^{T}$ has entries that agree on
their sign with the sign of the entries of ${\hat{\mathbf{Z}}}^{T}.$

######  Lemma A.4.

Recall the setting of Lemma A.3 and the SVD
${\hat{\mathbf{Z}}}=\mathbf{V}\bm{\Lambda}\mathbf{U}^{T}$. The matrix
$\hat{\mathbf{B}}=\mathbf{U}\mathbf{V}^{T}$ satisfies the following element-
wise _strict_ inequalities: $\hat{\mathbf{B}}\odot{\hat{\mathbf{Z}}}^{T}>0.$

###### Proof.

From Lemma A.3, we have explicit expressions for the SVD factors $\mathbf{U}$
and $\mathbf{V}$. From these, we can directly compute that

$\displaystyle\begin{bmatrix}\hat{\mathbf{B}}_{11}&\hat{\mathbf{B}}_{12}\\\
\hat{\mathbf{B}}_{21}&\hat{\mathbf{B}}_{22}\end{bmatrix}:=\hat{\mathbf{B}}=\mathbf{U}\mathbf{V}^{T}=\begin{bmatrix}\frac{1}{\sqrt{R}}\mathds{P}_{\overline{\rho}k}\mathds{P}_{\overline{\rho}k}^{T}\otimes\mathds{1}_{R}&0\\\
0&0\end{bmatrix}+\frac{1}{k\sqrt{\overline{\rho}+R\rho}}\begin{bmatrix}\frac{\rho}{\overline{\rho}}\mathds{1}_{R\overline{\rho}k}\mathds{1}_{\overline{\rho}k}^{T}&-\mathds{1}_{R\overline{\rho}k}\mathds{1}_{\rho
k}^{T}\\\ -\mathds{1}_{\rho
k}\mathds{1}_{\overline{\rho}k}^{T}&\frac{\overline{\rho}}{\rho}\mathds{1}_{\rho
k}\mathds{1}_{\rho k}^{T}\end{bmatrix}+\begin{bmatrix}0&0\\\
0&\mathds{P}_{\rho k}\mathds{P}_{\rho k}^{T}\end{bmatrix}.$

To continue, recall again that for any integer $m$:
$\mathds{P}_{m}\mathds{P}_{m}^{T}=\mathds{I}_{m}-\frac{1}{m}\mathds{1}_{m}\mathds{1}_{m}^{T}$.
Also note that
$\mathds{1}_{R\overline{\rho}k}\mathds{1}_{\overline{\rho}k}^{T}=(\mathds{1}_{\overline{\rho}k}\mathds{1}_{\overline{\rho}k}^{T})\otimes\mathds{1}_{R}$.
Hence continuing from the display above we find that

$\displaystyle\hat{\mathbf{B}}_{11}$
$\displaystyle=\left(\frac{1}{\sqrt{R}}\mathds{I}_{\overline{\rho}k}-\left(\frac{1}{\overline{\rho}k\sqrt{R}}-\frac{\rho/\overline{\rho}}{k\sqrt{\overline{\rho}+R\rho}}\right)\mathds{1}_{\overline{\rho}k}\mathds{1}_{\overline{\rho}k}\right)\otimes\mathds{1}_{R}=\frac{1}{\sqrt{R}}\left(\mathds{I}_{\overline{\rho}k}-\frac{1}{\overline{\rho}k}\left(1-\sqrt{\frac{{R\rho}}{R+{\overline{\rho}}/{\rho}}}\right)\mathds{1}_{\overline{\rho}k}\mathds{1}_{\overline{\rho}k}\right)\otimes\mathds{1}_{R}$
$\displaystyle\hat{\mathbf{B}}_{12}$
$\displaystyle=-\frac{1}{k\sqrt{\overline{\rho}+R\rho}}\mathds{1}_{R\overline{\rho}k}\mathds{1}_{\rho
k}^{T}\qquad\text{ and
}\qquad\hat{\mathbf{B}}_{21}=-\frac{1}{k\sqrt{\overline{\rho}+R\rho}}\mathds{1}_{\rho
k}\mathds{1}_{\overline{\rho}k}^{T}$ $\displaystyle\hat{\mathbf{B}}_{22}$
$\displaystyle=\mathds{I}_{\rho k}-\left(\frac{1}{\rho
k}-\frac{\overline{\rho}/\rho}{k\sqrt{\overline{\rho}+R\rho}}\right)\mathds{1}_{\rho
k}\mathds{1}_{\rho k}^{T}=\mathds{I}_{\rho k}-\frac{1}{\rho
k}\left(1-\sqrt{\frac{\overline{\rho}}{{1+R\left({\rho}/{\overline{\rho}}\right)}}}\right)\mathds{1}_{\rho
k}\mathds{1}_{\rho k}^{T}.$

Finally, recall from (12) the block-form of ${\hat{\mathbf{Z}}}$ repeated here
for convenience

${\hat{\mathbf{Z}}}^{T}:=\begin{bmatrix}{\hat{\mathbf{Z}}}_{11}^{T}&{\hat{\mathbf{Z}}}_{12}^{T}\\\
{\hat{\mathbf{Z}}}_{21}^{T}&{\hat{\mathbf{Z}}}_{22}^{T}\end{bmatrix}=\begin{bmatrix}\mathbf{S}_{\overline{\rho}k}\otimes\mathds{1}_{R}&-\frac{1}{k}\mathds{1}_{R\overline{\rho}k}\mathds{1}^{T}_{\rho
k}\\\ -\frac{1}{k}\mathds{1}_{\rho
k}\mathds{1}^{T}_{\overline{\rho}k}&\mathbf{S}_{\rho k}\end{bmatrix}.$

By inspection, the signs of $\hat{\mathbf{B}}_{12}$, $\hat{\mathbf{B}}_{21}$
are negative, same as the signs of ${\hat{\mathbf{Z}}}_{21}^{T}$,
${\hat{\mathbf{Z}}}_{12}^{T}$. To see that the signs of the diagonal blocks
also agree it suffices to check that the following strict inequalities always
hold

$1>1-\sqrt{\frac{{R\rho}}{R+{\overline{\rho}}/{\rho}}}>0\qquad\text{and}\qquad
1>1-\sqrt{\frac{\overline{\rho}}{1+R\left({\rho}/{\overline{\rho}}\right)}}>0.$

This completes the proof of the lemma. ∎

##  Appendix B The SELI geometry

As mentioned the SELI geometry is described in terms of the SVD of the SEL
matrix ${\hat{\mathbf{Z}}}$. In this section, we show that it is in fact
possible to get explicit closed-form expressions describing the SELI geometry
in terms of the parameters $R,\rho,k$. Key to this is the explicit
construction of the SVD factors in Sec. A.2.

For concreteness, we focus on the case of equal numbers of minorities and
majorities (i.e. $\rho=1/2$) since the formulas are somewhat simpler and the
setting is of sufficient interest to convey main messages. Extension to the
general case can be done in a similar fashion.

All results in this section hold under the following assumptions (assumed
throughout without further explicit reference):

  * •

A $(R,1/2)$-STEP imbalanced setting.

  * •

The classifiers $\mathbf{w}_{c},c\in[k]$ and the embeddings
$\mathbf{h}_{i},i\in[n]$ follow the SELI geometry in Definition 3.

###  B.1 Closed-form expressions

####  B.1.1 Norms

The following two lemmas are essentially restatements of Lemma 3.1.

######  Lemma B.1 (Norms of classifiers).

The following statements are true about the norms of the classifiers.

  1. (i)

The classifier norms across all majority / minority classes are all the same.
That is,

$\forall
c=1,\ldots,k/2\,,\quad\|\mathbf{w}_{c}\|_{2}=:\|\mathbf{w}_{\rm{maj}}\|_{2}\quad\text{and}\quad\forall
c=k/2+1,\ldots,k\,,\quad\|\mathbf{w}_{c}\|_{2}=:\|\mathbf{w}_{\rm{minor}}\|_{2}$

where we let $\|\mathbf{w}_{\rm{maj}}\|_{2}$ /
$\|\mathbf{w}_{\rm{minor}}\|_{2}$ denote the majority / minority norm of an
arbitrary class of the corresponding type.

  2. (ii)

It holds that

$\displaystyle\|\mathbf{w}_{\rm{maj}}\|_{2}^{2}=\sqrt{R}(1-2/k)+\frac{\sqrt{(R+1)/2}}{k}\quad\text{and}\quad\|\mathbf{w}_{\rm{minor}}\|_{2}^{2}=(1-2/k)+\frac{\sqrt{(R+1)/2}}{k}.$
(13)

Thus, $\|\mathbf{w}_{\rm{maj}}\|_{2}\geq\|\mathbf{w}_{\rm{minor}}\|_{2}$ with
equality if and only if $R=1$ or $k=2$.

###### Proof.

Recall, since the classifiers follow the SELI geometry, it holds that
$\mathbf{W}^{T}\mathbf{W}=\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}.$ Hence, it
suffices to compute the diagonal of the matrix
$\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}$. We have

$\displaystyle\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}$
$\displaystyle=\sqrt{R}\begin{bmatrix}\mathds{P}_{m}\mathds{P}_{m}^{T}&0\\\
0&0\end{bmatrix}+\frac{\sqrt{(R+1)/2}}{k}\begin{bmatrix}\mathds{1}_{m}\mathds{1}_{m}^{T}&-\mathds{1}_{m}\mathds{1}_{m}^{T}\\\
-\mathds{1}_{m}\mathds{1}_{m}^{T}&\mathds{1}_{m}\mathds{1}_{m}^{T}\end{bmatrix}+\begin{bmatrix}0&0\\\
0&\mathds{P}_{m}\mathds{P}_{m}^{T}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\sqrt{R}\mathds{I}_{k/2}-\frac{1}{k}\left(2\sqrt{R}-\sqrt{(R+1)/2}\right)\mathds{1}_{k/2}\mathds{1}_{k/2}^{T}&-\frac{\sqrt{(R+1)/2}}{k}\mathds{1}_{k/2}\mathds{1}_{k/2}^{T}\\\
-\frac{\sqrt{(R+1)/2}}{k}\mathds{1}_{k/2}\mathds{1}_{k/2}^{T}&\mathds{I}_{k/2}-\frac{1}{k}\left(2-\sqrt{(R+1)/2}\right)\mathds{1}_{k/2}\mathds{1}_{k/2}^{T}\end{bmatrix}\,.$
(14)

From this, the statements of the lemma follow readily. ∎

######  Lemma B.2 (Norms of embeddings).

The following statements are true about the norms of the embeddings:

  1. (i)

The embedding norms across all majority / minority classes are all the same.
That is,

$\displaystyle\forall
j\in\\{i\in[n]\,:\,y_{i}=1,\ldots,k/2\\}\,,\quad\|\mathbf{h}_{j}\|_{2}$
$\displaystyle=:\|\mathbf{h}_{\rm{maj}}\|_{2},\qquad\text{and}$
$\displaystyle\forall
j\in\\{i\in[n]\,:\,y_{i}=k/2+1,\ldots,k\\}\,,\quad\|\mathbf{h}_{j}\|_{2}$
$\displaystyle=:\|\mathbf{h}_{\rm{minor}}\|_{2}.$

where we let $\|\mathbf{h}_{\rm{maj}}\|_{2}$ /
$\|\mathbf{h}_{\rm{minor}}\|_{2}$ denote the majority / minority norm of an
arbitrary example of the corresponding type.

  2. (ii)

It holds that

$\displaystyle\|\mathbf{h}_{\rm{maj}}\|_{2}^{2}=\frac{1}{\sqrt{R}}(1-2/k)+\frac{1}{k\sqrt{(R+1)/2}}\quad\text{and}\quad\|\mathbf{h}_{\rm{minor}}\|_{2}^{2}=(1-2/k)+\frac{1}{k\sqrt{(R+1)/2}}.$
(15)

Thus, $\|\mathbf{h}_{\rm{maj}}\|_{2}\leq\|\mathbf{h}_{\rm{minor}}\|_{2}$ with
equality if and only if $R=1$ or $k=2$.

###### Proof.

Recall, since the classifiers follow the SELI geometry, it holds that
${\mathbf{H}}^{T}{\mathbf{H}}=\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}.$ Hence, it
suffices to compute the diagonal of the matrix
$\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$. Recalling that $n=k(R+1)/2$ We have

$\displaystyle\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$
$\displaystyle=\sqrt{R}\begin{bmatrix}\frac{1}{R}\mathds{P}_{m}\mathds{P}_{m}^{T}\otimes\mathds{1}_{R}\mathds{1}_{R}^{T}&0\\\
0&0\end{bmatrix}+\frac{1}{k\sqrt{(R+1)/2}}\begin{bmatrix}\mathds{1}_{Rm}\mathds{1}_{Rm}^{T}&-\mathds{1}_{Rm}\mathds{1}_{m}^{T}\\\
-\mathds{1}_{m}\mathds{1}_{Rm}^{T}&\mathds{1}_{m}\mathds{1}_{m}^{T}\end{bmatrix}+\begin{bmatrix}0&0\\\
0&\mathds{P}_{m}\mathds{P}_{m}^{T}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\left(\frac{1}{\sqrt{R}}\mathds{I}_{k/2}-\frac{1}{k}\left(\frac{2}{\sqrt{R}}-\frac{1}{\sqrt{(R+1)/2}}\right)\mathds{1}_{k/2}\mathds{1}_{k/2}^{T}\right)\otimes\mathds{1}_{R}\mathds{1}_{R}^{T}&-\frac{1}{k\sqrt{(R+1)/2}}\mathds{1}_{k/2}\mathds{1}_{k/2}^{T}\\\
-\frac{1}{k\sqrt{(R+1)/2}}\mathds{1}_{k/2}\mathds{1}_{k/2}^{T}&\mathds{I}_{k/2}-\frac{1}{k}\left(2-\frac{1}{\sqrt{(R+1)/2}}\right)\mathds{1}_{k/2}\mathds{1}_{k/2}^{T}\end{bmatrix}\,.$
(16)

From this, the statements of the lemma follow readily by reading out the
diagonal. ∎

####  B.1.2 Angles

######  Lemma B.3 (Angles of classifiers).

The following statements are true about the angles of the classifiers.

  1. (i)

The classifiers’ angles across all majority / minority classes are all the
same. That is,

$\displaystyle\forall c\neq
c^{\prime}\in\\{1,\ldots,k/2\\}\,,\quad\operatorname{Cos}(\mathbf{w}_{c},\mathbf{w}_{c^{\prime}})$
$\displaystyle=:\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{w}_{\rm{maj}}^{\prime})$
$\displaystyle\forall c\neq
c^{\prime}\in\\{k/2+1,\ldots,k\\}\,,\quad\operatorname{Cos}(\mathbf{w}_{c},\mathbf{w}_{c^{\prime}})$
$\displaystyle=:\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})$
$\displaystyle\forall
c\in\\{1,\ldots,k/2\\},c^{\prime}\in\\{k/2+1,\ldots,k\\}\,,\quad\operatorname{Cos}(\mathbf{w}_{c},\mathbf{w}_{c^{\prime}})$
$\displaystyle=:\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{w}_{\rm{minor}})\,.$

  2. (ii)

It holds that

$\displaystyle\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{w}_{\rm{maj}}^{\prime})$
$\displaystyle=\frac{-2\sqrt{R}+\sqrt{(R+1)/2}}{(k-2)\sqrt{R}+\sqrt{(R+1)/2}}$
$\displaystyle\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})$
$\displaystyle=\frac{R-7}{R-7+2k\left(2+\sqrt{(R+1)/2}\right)}$
$\displaystyle\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{w}_{\rm{minor}})$
$\displaystyle=-\frac{\sqrt{(R+1)/2}}{k\|\mathbf{w}_{\rm{maj}}\|_{2}\|\mathbf{w}_{\rm{minor}}\|_{2}}\,.$

###### Proof.

Recall under the SELI geometry that
$\mathbf{W}^{T}\mathbf{W}=\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}$. Hence,
inspecting the off-diagonal entries of the matrix computed in Equation (14)
gives Statement (i) and the following inner-product relations:

$\displaystyle\mathbf{w}_{\rm{maj}}^{T}\mathbf{w}_{\rm{maj}}^{\prime}$
$\displaystyle=-\frac{1}{k}\left({2}{\sqrt{R}}-{\sqrt{(R+1)/2}}\right)$
$\displaystyle\mathbf{w}_{\rm{minor}}^{T}\mathbf{w}_{\rm{minor}}^{\prime}$
$\displaystyle=-\frac{1}{k}\left(2-{\sqrt{(R+1)/2}}\right)$
$\displaystyle\mathbf{w}_{\rm{minor}}^{T}\mathbf{w}_{\rm{maj}}$
$\displaystyle=-\frac{\sqrt{(R+1)/2}}{k}\,.$

Combine these with the norm calculations in Lemma B.1 to prove Statement (ii).
∎

######  Lemma B.4 (Angles of classifiers).

The following statements are true about the angles of the embeddings.

  1. (i)

The embeddings’ angles across all majority / minority classes are all the
same. That is,

$\displaystyle\forall c\neq
c^{\prime}\in\\{1,\ldots,k/2\\}\,,\quad\operatorname{Cos}(\mathbf{h}_{c},\mathbf{h}_{c^{\prime}})$
$\displaystyle=:\operatorname{Cos}(\mathbf{h}_{\rm{maj}},\mathbf{h}_{\rm{maj}}^{\prime})$
$\displaystyle\forall c\neq
c^{\prime}\in\\{k/2+1,\ldots,k\\}\,,\quad\operatorname{Cos}(\mathbf{h}_{c},\mathbf{h}_{c^{\prime}})$
$\displaystyle=:\operatorname{Cos}(\mathbf{h}_{\rm{minor}},\mathbf{h}_{\rm{minor}}^{\prime})$
$\displaystyle\forall
c\in\\{1,\ldots,k/2\\},c^{\prime}\in\\{k/2+1,\ldots,k\\}\,,\quad\operatorname{Cos}(\mathbf{h}_{c},\mathbf{h}_{c^{\prime}})$
$\displaystyle=:\operatorname{Cos}(\mathbf{h}_{\rm{maj}},\mathbf{h}_{\rm{minor}})\,.$

  2. (ii)

It holds that

$\displaystyle\operatorname{Cos}(\mathbf{h}_{\rm{maj}},\mathbf{h}_{\rm{maj}}^{\prime})$
$\displaystyle=\frac{-(R+2)}{-(R+2)+k\left(R+1+\sqrt{R}\sqrt{(R+1)/2}\right)}$
$\displaystyle\operatorname{Cos}(\mathbf{h}_{\rm{minor}},\mathbf{h}_{\rm{minor}}^{\prime})$
$\displaystyle=\frac{1-\sqrt{2}\sqrt{R+1}}{1-\sqrt{2}\sqrt{R+1}+k\sqrt{(R+1)/2}}$
$\displaystyle\operatorname{Cos}(\mathbf{h}_{\rm{maj}},\mathbf{h}_{\rm{minor}})$
$\displaystyle=-\frac{1}{\|\mathbf{h}_{\rm{maj}}\|_{2}\|\mathbf{h}_{\rm{minor}}\|_{2}\,k\,\sqrt{(R+1)/2}}\,.$

###### Proof.

Recall under the SELI geometry that
${\mathbf{H}}^{T}{\mathbf{H}}=\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$. Hence,
inspecting the off-diagonal entries of the matrix computed in Equation (16)
gives Statement (i) and the following inner-product relations:

$\displaystyle\mathbf{h}_{\rm{maj}}^{T}\mathbf{h}_{\rm{maj}}^{\prime}$
$\displaystyle=-\frac{1}{k}\left(\frac{2}{\sqrt{R}}-\frac{1}{\sqrt{(R+1)/2}}\right)$
$\displaystyle\mathbf{h}_{\rm{minor}}^{T}\mathbf{h}_{\rm{minor}}^{\prime}$
$\displaystyle=-\frac{1}{k}\left(2-\frac{1}{\sqrt{(R+1)/2}}\right)$
$\displaystyle\mathbf{h}_{\rm{minor}}^{T}\mathbf{h}_{\rm{maj}}$
$\displaystyle=-\frac{1}{k\sqrt{(R+1)/2}}\,.$

Combine these with the norm calculations in Lemma B.2 to prove Statement (ii).
∎

####  B.1.3 (Non)-alignment

In the previous lemmas we compute the angles between classifiers of different
classes and between embeddings of different classes. Here, we also also
compute the angles between classifiers and embeddings. Specifically, for each
$c\in[k]$, we compute the angle
$\operatorname{Cos}(\mathbf{w}_{c},\mathbf{h}_{i})$ for an example $i:y_{i}=c$
that belongs to the same class. These values can be thought of as the degree
of alignment between classifiers and embeddings, as
$\operatorname{Cos}(\mathbf{w}_{c},\mathbf{h}_{i})=1$ corresponds to exact
alignment between the two.

######  Lemma B.5 (Alignment of classifiers and embeddings).

The following statements are true about the degree of alignment between class-
embeddings and their corresponding classifiers.

  1. (i)

The angles between majority- / minority- class embeddings and their
corresponding classifiers are all the same. That is,

$\displaystyle\forall c\in\\{1,\ldots,k/2\\}\text{ and
}i\,:\,y_{i}=c,~{}\operatorname{Cos}(\mathbf{w}_{c},\mathbf{h}_{i})$
$\displaystyle=\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{h}_{\rm{maj}})$
$\displaystyle\forall c\in\\{k/2+1,\ldots,k\\}\text{ and
}i\,:\,y_{i}=c,~{}\operatorname{Cos}(\mathbf{w}_{c},\mathbf{h}_{i})$
$\displaystyle=\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{h}_{\rm{minor}}).$

  2. (ii)

It holds that

$\displaystyle\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{h}_{\rm{maj}})$
$\displaystyle=\frac{1-1/k}{\|\mathbf{w}_{\rm{maj}}\|_{2}\|\mathbf{h}_{\rm{maj}}\|_{2}}$
(17)
$\displaystyle\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{h}_{\rm{minor}})$
$\displaystyle=\frac{1-1/k}{\|\mathbf{w}_{\rm{minor}}\|_{2}\|\mathbf{h}_{\rm{minor}}\|_{2}}.$
(18)

###### Proof.

The proof is immediate by recognizing that under the SELI geometry for all
$c\in[k]$ and $i:y_{i}=c$ it holds that
$\mathbf{w}_{c}^{T}\mathbf{h}_{i}=1-1/k$. ∎

####  B.1.4 Centering

It is easy to see that the classifiers $\mathbf{w}_{c},c\in[k]$ following the
SELI geometry are centered, i.e. $\sum_{c\in[k]}\mathbf{w}_{c}=0$. For
example, we can see this from the facts that
$\mathbf{W}^{T}\mathbf{W}=\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}$ and
$\mathbf{V}^{T}\mathds{1}_{k}=0.$ See also Lemma E.1 for an alternative proof.

On the other hand, the embeddings $\mathbf{h}_{i},i\in[n]$ are _not_ centered
around zero in general. Instead, it holds that

$\displaystyle\sum_{i\in[n]}\frac{1}{n_{y_{i}}}\mathbf{h}_{i}=0.$ (19)

Note that this reduces to $\sum_{i\in[n]}\mathbf{h}_{i}$ for balanced data,
but is not true otherwise. To see (19) recall first that
${\mathbf{H}}^{T}{\mathbf{H}}=\mathbf{U}\bm{\Lambda}\mathbf{U}^{T}$. Second,
check that $\sum_{i\in[n]}\frac{1}{n_{y_{i}}}{\hat{\mathbf{z}}}_{i}=0$, i.e.
${\hat{\mathbf{Z}}}\bm{\omega}=0$ where $\bm{\omega}[i]=1/n_{y_{i}},i\in[n]$.
Thus, $\mathbf{U}^{T}\bm{\omega}=0$. Combining these two it follows that
${\mathbf{H}}\bm{\omega}=0$, which gives the desired.

Now, suppose that the __(NC)__ property also holds, i.e. the embeddings
collapse to their class means, that is,

$\forall
i\in[n],~{}~{}\mathbf{h}_{i}=\bm{\mu}_{y_{i}}:=\frac{1}{n_{y_{i}}}\sum_{j\,:\,y_{j}=y_{i}}\mathbf{h}_{j}.$

Then, (19) implies the following about the class means:

$\displaystyle
0=\sum_{i\in[n]}\frac{1}{n_{y_{i}}}\mathbf{h}_{i}=\sum_{c\in[k]}\frac{1}{n_{c}}\sum_{i\,:\,y_{i}=c}\mathbf{h}_{i}=\sum_{c\in[k]}\bm{\mu}_{c}.$
(20)

Therefore, the class means are always centered around zero.

###  B.2 Illustrations and discussion on dependence on $R$ and $k$

In the previous section, we derived closed-form expressions for the features
describing the SELI geometry. Here, we use these expressions to study how
varying values of class-number $k$ and imbalance-ratio $R$ change the
geometry. We use the numerical illustration in Fig. 8 to guide the discussion.
Specifically, in Fig. 8 we compute and plot the norm ratios, alignment and
angles between embeddings and classifiers for $k=2,4,10,20$ classes and
imbalance ratio varying from $1$ (aka balanced) to $100$.

(a) Norms of classifiers and embeddings.

(b) Alignment of classifiers and embeddings.

(c) Angles of classifiers and embeddings. Dashed lines are are at
$-1/{(k-1)}$.

Figure 8:  Same as Fig. 3 only $R$ varies from $1$ to $100$ to ease
visualizations of how the geometry changes for finite $R$ values.

##### Norms.

Fig. 8(a) shows the ratios of majority vs minority norms for both classifiers
and embeddings. The values are computed using Lemmas B.1 and B.2. For binary
problems (aka $k=2$), the norm ratio is always equal to one irrespective of
imbalance. For larger values of $k$, the norm ratio is equal to one only for
balanced classes (aka $R=1$). Recall that equal norm ratios is a feature of
the ETF geometry [26]. On the other hand, for $k\neq 2$ and $R>1$, the
majorities have strictly larger norms for the classifiers and strictly smaller
norms for the embeddings. Thus, in general the SELI geometry is very different
from the ETF geometry. Interestingly, the difference is already evident when
going from $k=2$ to $k=4$ classes. Also, the change in the ratios for
classifiers is more pronounced than that for embeddings, which is changing
progressively slower as $k$ increases (see how close are the green and blue
curves in the right plot).

##### Alignment.

Fig. 8(b) shows the degree to which the geometries of classifiers and
embeddings are aligned to each other. Specifically, we plot the cosine between
any majority (left) / minority (right) classifier and corresponding embeddings
belonging to the same class; see also Lemma B.5. For $k=2$ and $R=1$ the
cosines are equal to one indicating that classifiers and embeddings align for
both majorities and minorities. This is consistent with the ETF geometry. On
the other hand, the alignment property breaks when $k>2$ and $R>1$. The effect
is more drastic for the minorities (right plot), while for majorities the
alignment is approximately preserved (note the y-axis scale is different in
the two plots). Interestingly, alignment is in fact favored for larger number
of classes, but deteriorates with increasing $R$ consistently for all values
of $k$.

##### Angles.

Fig. 8(c) shows the angles between majority/majority (left), minority/minority
(center), and minority/majority (right) for both classifiers (top) and
embeddings (bottom). The values are computed using Lemmas B.3 and B.4. For
binary problems (aka $k=2$), there is only one majority and one minority
class. Thus, we only plot the minority/majority cosines, which are always
equal to $-1/(k-1)$ irrespective of imbalance. For larger values of $k$, the
cosines are equal to that same value $-1/(k-1)$ only for balanced classes (aka
$R=1$). Recall that cosine value equal to $-1/(k-1)$ is a unique feature of
the ETF geometry. On the other hand, for $k\neq 2$ and $R>1$, the cosines are
different. For reference, we plot the values of $-1/(k-1)$ in dashed lines.
For the classifiers, the majority angles increase, while the minority angles
decrease. The rate of change is more drastic for minorities. In both cases,
the rate of change across $R$ is more pronounced for smaller $k$. The
majority-minority angles also increase with $R$. The trend is reversed for
embeddings. For example, the angles between minority embeddings become larger
with increasing $R$. Again, the effect of imbalance (at least for the values
of $R$ shown) is more pronounced here for smaller values of $k$.

###  B.3 Special cases

####  B.3.1 Balanced classes and binary classification

The following result follows directly by combining Lemmas B.1, B.2, B.3, B.4
and B.5.

######  Corollary 2.3 ($k=2$ or $R=1$: __(SELI)__ $\equiv$__(ETF)__).

Assume $k=2$ or $R=1$. The following hold.

$\displaystyle\|\mathbf{w}_{1}\|_{2}=\ldots=\|\mathbf{w}_{k}\|_{2}\quad\text{
and }\quad\|\mathbf{h}_{1}\|_{2}=\ldots=\|\mathbf{h}_{n}\|_{2}\,,$
$\displaystyle\forall c\neq
c^{\prime}\in[k],~{}\operatorname{Cos}(\mathbf{w}_{c},\mathbf{w}_{c}^{\prime})=-1/(k-1)\quad\text{
and }\quad$ $\displaystyle\forall i\neq
i^{\prime}\in[n],~{}\operatorname{Cos}(\mathbf{h}_{i},\mathbf{h}_{i}^{\prime})=-1/(k-1)\,,$
$\displaystyle\forall
c\in[k],i\,:\,y_{i}=c,~{}\operatorname{Cos}(\mathbf{w}_{c},\mathbf{h}_{i})=1.$

Thus, the SELI geometry is same as the ETF geometry in balanced and in binary
classification.

####  B.3.2 Asymptotics

We can also use the results of Sec. B.1 to understand the SELI geometric
features asymptotically as $R$ increases. These are included in Corollary 2.4
below. See also Fig. 3 for a numerical illustration of the limiting behavior
for large imbalance ratios.

######  Corollary 2.4 ($R\rightarrow\infty$).

Fix even $k>2$. Then, the following limits hold.

  1. (i)

$\lim_{R\rightarrow\infty}\frac{\|\mathbf{w}_{\rm{maj}}\|_{2}^{2}}{\|\mathbf{w}_{\rm{minor}}\|_{2}^{2}}=1+(k-2)\sqrt{2}$

  2. (ii)

$\lim_{R\rightarrow\infty}\frac{\|\mathbf{h}_{\rm{maj}}\|_{2}^{2}}{\|\mathbf{h}_{\rm{minor}}\|_{2}^{2}}=0$

  3. (iii)

$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{w}_{\rm{maj}}^{\prime})=\frac{-4+\sqrt{2}}{\sqrt{2}+2(k-2)}$

  4. (iv)

$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})=1$

  5. (v)

$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{w}_{\rm{minor}})=-\frac{1}{\sqrt{\sqrt{2}+2(k-2)}}$

  6. (vi)

$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{h}_{\rm{maj}},\mathbf{h}_{\rm{maj}}^{\prime})=\frac{1}{k\left(1+\sqrt{2}/2\right)-1}$

  7. (vii)

$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{h}_{\rm{minor}},\mathbf{h}_{\rm{minor}}^{\prime})=-\frac{2}{k-2}$

  8. (viii)

$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{h}_{\rm{maj}},\mathbf{h}_{\rm{minor}})=0$

  9. (ix)

$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{w}_{\rm{maj}},\mathbf{h}_{\rm{maj}})=\frac{k-1}{\sqrt{k+\sqrt{2}-2}\sqrt{k+\sqrt{2}/2-2}}$

  10. (x)

$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{h}_{\rm{minor}})=0$

###### Proof.

The expressions that appear in the lemmas in Sec. B.1 hold for any value of
$R$. Take the limit of $R\rightarrow\infty$ to yield the expressions above. We
omit the details for brevity. ∎

Several interesting conclusions are immediate from the formulas above. For
example, Statement (iv) shows that, asymptotically in $R$, the minority
classes collapse to the same vector. This is a manifestation of the minority
collapse phenomenon discovered by Fang et al. [3]. Asymptotic minority
collapse had not been shown before for the UF-SVM. See also Sec. H for an
extended discussion. We note that beyond minority classifiers, Corollary 2.4
is further conclusive about the behavior of majority classifiers, as well as,
minority and majority embeddings. For example, Statement (viii) suggests that
the minority and majority embeddings become orthogonal to each other
asymptotically. Further investigations of the validity of such asymptotic
conclusions in deep-net training is beyond our scope.

##  Appendix C Proofs for UF-SVM Section 3

###  C.1 Proof of Theorem 1

We consider a relaxation of the non-convex SVM in (2) by setting

$\displaystyle\mathbf{X}=\begin{bmatrix}\mathbf{W}^{T}\\\
{{\mathbf{H}}}^{T}\end{bmatrix}\begin{bmatrix}\mathbf{W}&{\mathbf{H}}\end{bmatrix}=\begin{bmatrix}\mathbf{W}^{T}\mathbf{W}&\mathbf{W}^{T}{\mathbf{H}}\\\
{\mathbf{H}}^{T}\mathbf{W}&{\mathbf{H}}^{T}{\mathbf{H}}\end{bmatrix}\in\mathbb{R}^{(k+n)\times(k+n)}.$
(21)

With this consider the following semidefinite program:

$\displaystyle\mathrm{q}_{*}$ $\displaystyle=\min_{\mathbf{X}\succeq
0}~{}~{}~{}~{}~{}~{}\frac{1}{2}\operatorname{tr}\Big{(}\mathbf{X}\Big{)}$ (22)
$\displaystyle~{}~{}~{}\text{sub.~{}to}~{}~{}~{}~{}\mathbf{X}[y_{i},k+i]-\mathbf{X}[c,k+i]\geq
1,~{}\forall i\in[n],c\neq y_{i}.$

It is not hard to see that $\mathrm{q}_{*}\leq\mathrm{p}_{*}$. In what
follows, we will compute the optimal set of (22) and use this to show that the
relaxation is in fact tight. This will allow us to characterize the solution
of the original problem.

_Dual of the convex relaxation:_ The optimization in (22) is convex and
satisfies Slater’s conditions. (Since constraints are affine, it suffices to
check feasibility, which is easily verified.) Hence, strong duality holds and
KKT conditions are necessary and sufficient for optimality. The dual of (22)
is written as follows:

$\displaystyle\mathrm{d}_{*}$
$\displaystyle=\max_{\\{a_{i,c}\\}_{i\in[n],c\neq
y_{i}}}~{}~{}\sum_{i\in[n]}\sum_{c\neq y_{i}}\alpha_{ic}$ (23)
$\displaystyle~{}~{}~{}~{}~{}\text{sub.~{}to}~{}~{}~{}~{}~{}~{}\begin{bmatrix}\mathds{I}_{k}&\mathbf{A}^{T}\\\
\mathbf{A}&\mathds{I}_{n}\end{bmatrix}\succeq 0$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\alpha_{ic}\geq
0,i\in[n],c\neq y_{i},~{}~{}\forall
i\in[n]:\mathbf{A}[{i,c}]=\begin{cases}-\sum_{c^{\prime}\neq
y_{i}}\alpha_{ic^{\prime}},&y_{i}=c,\\\ \alpha_{ic},&y_{i}\neq c.\end{cases}$

Also, the complementary slackness conditions are

$\displaystyle\begin{bmatrix}\mathds{I}_{k}&\mathbf{A}^{T}\\\
\mathbf{A}&\mathds{I}_{n}\end{bmatrix}\mathbf{X}=0\qquad\text{and}\qquad\forall
i\in[n],c\neq
y_{i}\,:\,\alpha_{ic}(1-\mathbf{X}[y_{i},k+i]+\mathbf{X}[c,k+i])=0.$ (24)

Instead of working with the dual in the above standard form, it is convenient
to work with an alternative representation by (re)-defining dual variables
$\beta_{ic},i\in[n],c\in[k]$ such that 555The same re-parameterization trick,
but for a simpler (convex) max-margin program was used by Wang et al. [35].

$\displaystyle\beta_{ic}=\begin{cases}\sum_{c^{\prime}\neq
y_{i}}\alpha_{ic^{\prime}},&y_{i}=c,\\\ -\alpha_{ic},&y_{i}\neq c.\end{cases}$
(25)

Specifically, arrange these new dual variable representations in a matrix
$\mathbf{B}\in\mathbb{R}^{n\times k}$ with entries
$\mathbf{B}[i,c]=\beta_{ic},i\in[n],c\in[k]$ and recall the SEL matrix
${\hat{\mathbf{Z}}}\in\mathbb{R}^{k\times n}$ in Definition 2. With these, we
can rewrite the dual in (23) in the following more convenient form:

$\displaystyle\mathrm{d}_{*}$
$\displaystyle=\max_{\mathbf{B}\in\mathbb{R}^{n\times
k}}~{}~{}~{}~{}\operatorname{tr}({\hat{\mathbf{Z}}}\mathbf{B})$ (26)
$\displaystyle~{}~{}~{}~{}\text{sub.~{}to}~{}~{}\begin{bmatrix}\mathds{I}_{k}&-\mathbf{B}^{T}\\\
-\mathbf{B}&\mathds{I}_{n}\end{bmatrix}\succeq 0$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
i\in[n]:\mathbf{B}[i,y_{i}]=-\sum_{c\neq y_{i}}\mathbf{B}[i,c]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mathbf{B}\odot{\hat{\mathbf{Z}}}^{T}\geq
0\,.$ (27)

Analogously, the complementary slackness conditions in (24) are equivalent to
the following:

$\displaystyle\begin{bmatrix}\mathds{I}_{k}&-\mathbf{B}^{T}\\\
-\mathbf{B}&\mathds{I}_{n}\end{bmatrix}\mathbf{X}=0\quad\text{and}\quad\forall
i\in[n],c\neq
y_{i}\,:\,\mathbf{B}[i,c]\,(1-\mathbf{X}[y_{i},k+i]+\mathbf{X}[c,k+i])=0.$
(28)

To see the equivalence of the objective of (26) denote
$A=\sum_{i\in[n]}\sum_{c\neq y_{i}}\alpha_{ic}$ the objective in (23) and note
that we get simultaneously
$A=\sum_{i\in[n]}\beta_{iy_{i}}=\sum_{i\in[n]}\sum_{c\neq
y_{i}}\big{(}-\beta_{ic}\big{)}$ following the definition in Equation (25).
Then, we have
$A=\frac{k-1}{k}A+\frac{1}{k}A=\sum_{i\in[n]}\sum_{c\in[k]}\hat{z}_{ic}\beta_{ic}=\operatorname{tr}\left({\hat{\mathbf{Z}}}\mathbf{B}\right)$.

_Solution to the dual:_ To continue, we consider the following relaxation of
the dual problem (26) (by removing the constraint in Equation (27)):

$\displaystyle\hat{\mathrm{d}}=\max_{\mathbf{B}\in\mathbb{R}^{n\times
k}}~{}~{}\operatorname{tr}({\hat{\mathbf{Z}}}\mathbf{B})\qquad\text{sub.
to}~{}~{}\|\mathbf{B}\|_{2}\leq 1\quad\text{ and
}\quad\mathbf{B}\mathds{1}_{k}=0.$ (29)

Here, recall that $\|\mathbf{B}\|_{2}$ denotes the spectral norm, hence the
first constraint is equivalent to the first constraint in the maximization in
(26) by Schur-complement argument. Using standard arguments, it can be shown
that $\hat{\mathrm{d}}\leq\|{\hat{\mathbf{Z}}}\|_{*}$ and equality holds by
setting

$\displaystyle\hat{\mathbf{B}}$ $\displaystyle=\mathbf{U}\mathbf{V}^{T},$ (30)

where we recalled the compact SVD
${\hat{\mathbf{Z}}}=\mathbf{V}\bm{\Lambda}\mathbf{U}^{T}$. It is also not hard
to see that $\hat{\mathbf{B}}$ is feasible in (29) (recall here that
$\mathbf{V}^{T}\mathds{1}_{k}=0$). Hence, $\hat{\mathbf{B}}$ is a maximizer
and $\hat{\mathrm{d}}=\|{\hat{\mathbf{Z}}}\|_{*}$. The following lemma, the
proof of which we defer to the end of this section, proves something stronger:
$\hat{\mathbf{B}}$ is in fact the only maximizer in (29).

######  Lemma C.1.

The optimal cost of the maximization in (29) is $\|{\hat{\mathbf{Z}}}\|_{*}$
and $\hat{\mathbf{B}}=\mathbf{U}\mathbf{V}^{T}$ is its unique maximizer.

Next, we use Lemma C.1 to show that $\hat{\mathbf{B}}$ also satisfies the
inequality constraints in (27). To do this, we use an explicit construction of
the singular factors $\mathbf{U}$ and $\mathbf{V}$ presented in Sec. A.2,
which is possible thanks to the special structure of ${\hat{\mathbf{Z}}}$.
Specifically, we prove in Lemma A.3 that

$\displaystyle\hat{\mathbf{B}}\odot{\hat{\mathbf{Z}}}^{T}=(\mathbf{U}\mathbf{V}^{T})\odot{\hat{\mathbf{Z}}}^{T}>0.$
(31)

Hence, $\hat{\mathbf{B}}$ is feasible in (26). In fact, the feasibility
inequalities are strict, which we will use soon. For now, note that
feasibility of $\hat{\mathbf{B}}$ in (26) guarantees that it is its unique
maximizer (since it is the unique maximizer of the program’s relaxation, as
established in Lemma C.1.) Therefore,

$\displaystyle\mathrm{d}_{*}=\hat{\mathrm{d}}=\|{\hat{\mathbf{Z}}}\|_{*}\,,$
(32)

and $\hat{\mathbf{B}}$ in (30) is dual optimal for the semidefinite program in
(22).

_Solution to the primal relaxation:_ By strong duality, this implies
$\mathrm{q}_{*}=\mathrm{d}_{*}=\|{\hat{\mathbf{Z}}}\|_{*}$ and that any primal
minimizer
$\hat{\mathbf{X}}=\begin{bmatrix}\hat{\mathbf{X}}_{11}&\hat{\mathbf{X}}_{12}\\\
\hat{\mathbf{X}}_{12}^{T}&\hat{\mathbf{X}}_{22}\end{bmatrix}$ satisfies the
complementary slackness conditions in (28) with $\mathbf{B}=\hat{\mathbf{B}}$,
i.e.,

$\displaystyle\forall i\in[n],c\neq
y_{i}\,:\,\hat{\mathbf{X}}_{12}[y_{i},i]-\hat{\mathbf{X}}_{12}[c,i]-1$
$\displaystyle=0$ (33)
$\displaystyle\hat{\mathbf{X}}_{11}-\hat{\mathbf{B}}^{T}\hat{\mathbf{X}}_{12}^{T}=\hat{\mathbf{X}}_{12}-\hat{\mathbf{B}}^{T}\hat{\mathbf{X}}_{22}=-\hat{\mathbf{B}}\hat{\mathbf{X}}_{12}+\hat{\mathbf{X}}_{22}$
$\displaystyle=0\,.$ (34)

In (33) we used from (31) that inequalities are strict; thus, $\beta_{ic}>0$
for all $i\in[n],c\neq y_{i}$. Now, from (34) it follows that

$\displaystyle\hat{\mathbf{X}}_{11}=\hat{\mathbf{B}}^{T}\hat{\mathbf{X}}_{12}^{T},\quad\hat{\mathbf{X}}_{22}=\hat{\mathbf{B}}\hat{\mathbf{X}}_{12},\quad\hat{\mathbf{X}}_{12}=\hat{\mathbf{B}}^{T}\hat{\mathbf{X}}_{22}\,.$

Combining the last two equations shows

$\displaystyle(\mathds{I}_{n}-\hat{\mathbf{B}}\hat{\mathbf{B}}^{T})\hat{\mathbf{X}}_{22}=0$
$\displaystyle\implies(\mathds{I}_{n}-\mathbf{U}\mathbf{U}^{T})\hat{\mathbf{X}}_{22}=0\implies\hat{\mathbf{X}}_{22}=\mathbf{U}\mathbf{D}\mathbf{U}^{T},$
$\displaystyle\implies\hat{\mathbf{X}}_{12}=\hat{\mathbf{B}}^{T}\hat{\mathbf{X}}_{22}=\mathbf{V}\mathbf{D}\mathbf{U}^{T}\qquad\text{and}\qquad\hat{\mathbf{X}}_{11}=\hat{\mathbf{B}}^{T}\hat{\mathbf{X}}_{12}^{T}=\mathbf{V}\mathbf{D}\mathbf{V}^{T}$

for some (k-1)–dimensional matrix
$\mathbf{D}\in\mathbb{R}^{(k-1)\times(k-1)}$.

Next, we will use $\hat{\mathbf{X}}_{12}=\mathbf{V}\mathbf{D}\mathbf{U}^{T}$
in (33) to compute $\mathbf{D}$. For convenience denote
$\mathbf{e}_{k,c}\in\mathbb{R}^{k}$ the $c$-th standard basis vector in
$\mathbb{R}^{k}$ and $\mathbf{e}_{n,i}\in\mathbb{R}^{n}$ the $i$-th standard
basis vector in $\mathbb{R}^{n}$. Then, starting with (33), we get the
following chain of implications:

$\displaystyle\forall i\in[n],c\neq y_{i}\,$
$\displaystyle:\,(\mathbf{e}_{k,y_{i}}-\mathbf{e}_{k,c})^{T}\mathbf{V}\mathbf{D}\mathbf{U}^{T}\mathbf{e}_{n,i}=1$
(35) $\displaystyle\stackrel{{\scriptstyle(\sum_{c\neq
y_{i}}\cdot)}}{{\implies}}\forall i\in[n]\,$
$\displaystyle:\,\big{(}(k-1)\mathbf{e}_{k,y_{i}}-(\mathds{1}_{k}-\mathbf{e}_{k,y_{i}})\big{)}^{T}\mathbf{V}\mathbf{D}\mathbf{U}^{T}\mathbf{e}_{n,i}=k-1$
$\displaystyle\implies\forall i\in[n]\,$
$\displaystyle:\,\big{(}k\mathbf{e}_{k,y_{i}}-\mathds{1}_{k}\big{)}^{T}\mathbf{V}\mathbf{D}\mathbf{U}^{T}\mathbf{e}_{n,i}=k-1$
$\displaystyle\stackrel{{\scriptstyle(\mathbf{V}^{T}\mathds{1}_{k}=0)}}{{\implies}}\forall
i\in[n]\,$
$\displaystyle:\,\mathbf{e}_{k,y_{i}}^{T}\mathbf{V}\mathbf{D}\mathbf{U}^{T}\mathbf{e}_{n,i}=1-1/k$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:comp1a_2}}}{{\implies}}\forall
i\in[n]\,$
$\displaystyle:\,\mathbf{e}_{k,y_{i}}^{T}\mathbf{V}\mathbf{D}\mathbf{U}^{T}\mathbf{e}_{n,i}=1-1/k\qquad\text{and}\qquad\mathbf{e}_{k,c}^{T}\mathbf{V}\mathbf{D}\mathbf{U}^{T}\mathbf{e}_{n,i}=-1/k,\,c\neq
y_{i}$

Specifically, the last equation written in matrix form gives 666 Note that the
derivation and conclusion following (35) is general. Specifically, the display
above shows that ${\hat{\mathbf{Z}}}$ is the only $k\times n$ matrix for which
it holds simultaneously that $\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i]=1,\forall
i\in[n],c\neq y_{i}$ and $\mathds{1}_{k}^{T}\mathbf{Z}=0$.

$\displaystyle\mathbf{V}\mathbf{D}\mathbf{U}^{T}={\hat{\mathbf{Z}}}\stackrel{{\scriptstyle}}{{\implies}}\mathbf{D}=\mathbf{V}^{T}{\hat{\mathbf{Z}}}\mathbf{U}\implies\mathbf{D}=\bm{\Lambda},$
(36)

where the second and third equalities used
$\mathbf{V}^{T}\mathbf{V}=\mathbf{U}^{T}\mathbf{U}=\mathds{I}_{k-1}$.

To conclude, we have shown that any optimal point $\hat{\mathbf{X}}$ of (22)
satisfies

$\displaystyle\hat{\mathbf{X}}=\begin{bmatrix}\mathbf{V}\\\
\mathbf{U}\end{bmatrix}\bm{\Lambda}\begin{bmatrix}\mathbf{V}^{T}&\mathbf{U}^{T}\end{bmatrix}.$
(37)

_Solving the original problem:_ Now, we show that the convex relaxation in
(22) is tight. For some partial orthonormal matrix
$\mathbf{R}\in\mathbb{R}^{(k-1)\times d}$ (recall that $d\geq k-1$) with
$\mathbf{R}\mathbf{R}^{T}=\mathds{I}_{k-1}$, let

$\displaystyle{\hat{\mathbf{W}}}=\mathbf{R}^{T}\bm{\Lambda}^{1/2}\mathbf{V}^{T}\qquad\text{and}\qquad{\hat{{\mathbf{H}}}}=\mathbf{R}^{T}\bm{\Lambda}^{1/2}\mathbf{U}^{T}.$
(38)

By construnction
${\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}}=\hat{\mathbf{X}}_{12}$. Hence,
$({\hat{\mathbf{W}}},{\hat{{\mathbf{H}}}})$ is feasible in (2). Thus,
$\mathrm{p}_{*}\leq\frac{1}{2}\|{\hat{\mathbf{W}}}\|_{F}^{2}+\frac{1}{2}\|{\hat{{\mathbf{H}}}}\|_{F}^{2}=\frac{1}{2}\operatorname{tr}(\hat{\mathbf{X}})=\mathrm{q}_{*}$.
But, we have already argued that $\mathrm{p}_{*}\geq\mathrm{q}_{*}$. Hence,
$\mathrm{p}_{*}=\mathrm{q}_{*}$.

Take now any minimizer $({\hat{\mathbf{W}}},{\hat{{\mathbf{H}}}})$ of the
original problem (2). By feasibility of
$({\hat{\mathbf{W}}},{\hat{{\mathbf{H}}}})$, the matrix
$\bm{\Omega}:=\begin{bmatrix}{\hat{\mathbf{W}}}^{T}\\\
{{\hat{{\mathbf{H}}}}}^{T}\end{bmatrix}\begin{bmatrix}{\hat{\mathbf{W}}}&{\hat{{\mathbf{H}}}}\end{bmatrix}$
is feasible in (22). Also,
$\frac{1}{2}\operatorname{tr}(\bm{\Omega})=\frac{1}{2}\|{\hat{\mathbf{W}}}\|_{F}^{2}+\frac{1}{2}\|{\hat{{\mathbf{H}}}}\|_{F}^{2}=\mathrm{p}_{*}$.
But, $\mathrm{p}_{*}=\mathrm{q}_{*}$. Hence,
$\frac{1}{2}\operatorname{tr}(\bm{\Omega})=\mathrm{q}_{*}$, which implies that
$\bm{\Omega}$ is optimal. It must then be from (37) that

$\begin{bmatrix}{\hat{\mathbf{W}}}^{T}\\\
{{\hat{{\mathbf{H}}}}}^{T}\end{bmatrix}\begin{bmatrix}{\hat{\mathbf{W}}}&{\hat{{\mathbf{H}}}}\end{bmatrix}=\bm{\Omega}=\hat{\mathbf{X}}=\begin{bmatrix}\mathbf{V}\\\
\mathbf{U}\end{bmatrix}\bm{\Lambda}\begin{bmatrix}\mathbf{V}^{T}&\mathbf{U}^{T}\end{bmatrix}.$

This completes the proof of the theorem.

_Proof of Lemma C.1:_ It only remains to prove Lemma C.1, which we do here.
Any feasible $\mathbf{B}$ satisfies $\|\mathbf{B}\|_{2}\leq 1$. Hence, also
recalling that ${\hat{\mathbf{Z}}}$ has rank $k-1$ (because
$\mathbf{V}^{T}\mathds{1}_{k}=0$):

$\displaystyle\operatorname{tr}({\hat{\mathbf{Z}}}\mathbf{B})=\sum_{i=1}^{k-1}\bm{\Lambda}[i,i](\mathbf{u}_{i}^{T}\mathbf{B}\mathbf{v}_{i})\leq\sum_{i=1}^{k-1}\bm{\Lambda}[i,i]=\|{\hat{\mathbf{Z}}}\|_{*}.$
(39)

The inequality above is tight if and only if

$\displaystyle\forall
i\in[k-1]\,:\,\epsilon_{i}:=\mathbf{u}_{i}^{T}\mathbf{B}\mathbf{v}_{i}=1,$
(40)

which is indeed satisfied by $\hat{\mathbf{B}}=\mathbf{U}\mathbf{V}^{T}$.
Clearly, $\hat{\mathbf{B}}$ is also feasible. Hence, $\hat{\mathbf{B}}$ is a
maximizer of (29).

Next, we will show that there is no other maximizer, say
$\widetilde{\mathbf{B}}$. Indeed, since $\widetilde{\mathbf{B}}$ is optimal,
it must satisfy (40). Hence, it has rank at least $k-1$. But since
$\widetilde{\mathbf{B}}\mathds{1}_{k}=0$, we find that
$\widetilde{\mathbf{B}}$ has rank exactly $k-1$. Let
$\widetilde{\mathbf{B}}=\mathbf{U}_{\mathbf{B}}\bm{\Sigma}_{\mathbf{B}}\mathbf{V}_{\mathbf{B}}^{T}$
be its compact SVD and denote
$\sigma_{i}:=\bm{\Sigma}_{\mathbf{B}}[i,i],~{}i\in[k-1]$ its singular values.
Finally, define $(k-1)\times(k-1)$ matrices

$\displaystyle\mathbf{P}=\mathbf{U}_{\mathbf{B}}^{T}\mathbf{U}\qquad\text{and}\qquad\mathbf{Q}=\mathbf{V}_{\mathbf{B}}^{T}\mathbf{V}$
(41)

with columns $\mathbf{p}_{i},\mathbf{q}_{i},\,i\in[k-1].$ By Equation (40) we
have the following chain of inequalities for all $i\in[k-1]$:

$\displaystyle
1=\mathbf{u}_{i}^{T}\mathbf{B}\mathbf{v}_{i}=\mathbf{p}_{i}^{T}\bm{\Sigma}_{\mathbf{B}}\mathbf{q}_{i}$
$\displaystyle=\sum_{j\in[k-1]}\sigma_{j}\mathbf{p}_{i}[j]\mathbf{q}_{i}[j]\leq\sum_{j\in[k-1]}\sigma_{j}|\mathbf{p}_{i}[j]\mathbf{q}_{i}[j]|$
$\displaystyle\leq\sum_{j\in[k-1]}|\mathbf{p}_{i}[j]\mathbf{q}_{i}[j]|\leq\|\mathbf{p}_{i}\|_{2}\|\mathbf{q}_{i}\|_{2}\leq
1.$

Inspecting this, we note that all inequalities must be equalities. The first
inequality in the second line follows because
$\|\widetilde{\mathbf{B}}\|_{2}\leq 1\implies\forall
j\in[k-1]\,:\,\sigma_{j}\leq 1.$ Hence, $\sigma_{j}=1$ for all $j\in[k-1]$.
Equivalently $\bm{\Sigma}_{\mathbf{B}}=\mathds{I}_{k-1}.$ The second
inequality in that same line is Cauchy-Schwarz and equality implies

$\displaystyle\forall i\in[k-1]\,:\,\mathbf{p}_{i}=\pm\mathbf{q}_{i}.$ (42)

The last inequality follows because

$\displaystyle\|\mathbf{p}_{i}\|_{2}=\|\mathbf{U}_{\mathbf{B}}^{T}\mathbf{u}_{i}\|_{2}\leq\|\mathbf{U}_{\mathbf{B}}\|_{2}\|\mathbf{u}_{i}\|_{2}\leq
1\qquad\text{and}\qquad\|\mathbf{q}_{i}\|_{2}=\|\mathbf{V}_{\mathbf{B}}^{T}\mathbf{v}_{i}\|_{2}\leq\|\mathbf{V}_{\mathbf{B}}\|_{2}\|\mathbf{v}_{i}\|_{2}\leq
1.$ (43)

Since $\mathbf{U}_{\mathbf{B}}$ (resp. $\mathbf{V}_{\mathbf{B}}$) has
orthonormal columns, equality in (43) holds if and only if for all
$i\in[k-1]$, $\mathbf{u}_{i}$ (resp. $\mathbf{v}_{i}$) is a column of
$\mathbf{U}_{\mathbf{B}}$ (resp. $\mathbf{V}_{\mathbf{B}}$). Then, it must be
that $\mathbf{P}$ and $\mathbf{Q}$ are permutation matrices. Combined with
(42) this gives

$\displaystyle\mathbf{P}=\mathbf{Q}=\bm{\Pi}\implies\mathbf{U}_{\mathbf{B}}^{T}\mathbf{U}=\mathbf{V}_{\mathbf{B}}^{T}\mathbf{V}=\bm{\Pi}$
(44)

for some permutation matrix $\bm{\Pi}$. Continuing from this,

$\mathbf{U}_{\mathbf{B}}^{T}\mathbf{U}\bm{\Pi}^{T}=\mathbf{V}_{\mathbf{B}}^{T}\mathbf{V}\bm{\Pi}^{T}=\mathds{I}_{k-1}\implies\mathbf{U}_{\mathbf{B}}=\mathbf{U}\bm{\Pi}^{T}\text{
and }\mathbf{V}_{\mathbf{B}}=\mathbf{V}\bm{\Pi}^{T}.$

Putting things together, we conclude that

$\widetilde{\mathbf{B}}=\mathbf{U}_{\mathbf{B}}\bm{\Sigma}_{\mathbf{B}}\mathbf{V}_{\mathbf{B}}^{T}=\mathbf{U}_{\mathbf{B}}\mathbf{V}_{\mathbf{B}}^{T}=\mathbf{U}\bm{\Pi}^{T}\bm{\Pi}\mathbf{V}^{T}=\mathbf{U}\mathbf{V}^{T}=\hat{\mathbf{B}}.$

This concludes the proof of the lemma.

###  C.2 Proofs of Corollaries 1.1, 1.2, 1.3 and of Lemma 3.1

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

  * •

Corollary 1.1: See paragraph below the statement of the corollary in Sec. 3.1.

  * •

Corollary 1.2: As already mentioned in Sec. 3.1 this is nothing but a
reformulation of Theorem1(i)–(ii) in view of Definition 3 of the SELI
property.

  * •

Corollary 1.3: See Corollary 2.3 in Sec. B.

  * •

Lemma 3.1: See Lemma B.1 in Sec. B.

###  C.3 On different regularization hyperparameters between embeddings and
classifiers

Thus far in our analysis of the UFM, we assumed same regularization strength