$\lambda$ for the embeddings and classifiers; see Eqn. (1). Here, we discuss a
slight generalization allowing different regularizations $\lambda_{W}$ and
$\lambda_{H}$ for the classifiers and embeddings, respectively. This is
motivated by previous studies of the UFM in the literature, e.g. [41]. As we
show, this modification does _not_ change the SELI geometry modulo a relative
scaling factor between the embeddings and classifiers.

Concretely, consider the following slight generalization version of Eqn. (1):

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

which can be more conveniently reparameterized as follows:

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

where $\beta:=\sqrt{\frac{{\lambda}_{H}}{{\lambda}_{W}}}$ and
${\lambda}_{H},{\lambda}_{W}>0$. Now, consider the limit of vanishing
regularization ${\lambda}_{W}\rightarrow 0,{\lambda}_{H}\rightarrow 0$, with a
fixed finite and non-zero ratio $\beta^{2}={\lambda}_{H}/{\lambda}_{W}$.
Entirely analogous to Eqn. (2), this leads to the a $\beta$-parameterized UF-
SVM as follows:

$\displaystyle({\hat{\mathbf{W}}}_{\beta},{\hat{{\mathbf{H}}}}_{\beta})\in\arg\min_{\mathbf{W},{\mathbf{H}}}~{}\frac{1}{2\beta}\|\mathbf{W}\|_{F}^{2}+\frac{\beta}{2}\|{\mathbf{H}}\|_{F}^{2}\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}.$ (45)

Note that the UF-SVM we study in Eqn. (2) is a special case of the above for
$\beta=1$. For general values of $\beta>0$, it is not hard to see that there
is a one-to-one mapping of global solutions
$({\hat{\mathbf{W}}}_{\beta},{\hat{{\mathbf{H}}}}_{\beta})$ of (45) to global
solutions $({\hat{\mathbf{W}}}_{\beta},{\hat{{\mathbf{H}}}}_{\beta})$ of (2)
as follows:

$({\hat{\mathbf{W}}}_{\beta},{\hat{{\mathbf{H}}}}_{\beta})=(\sqrt{\beta}{\hat{\mathbf{W}}},\frac{1}{\sqrt{\beta}}{\hat{{\mathbf{H}}}}_{\beta}).$

Hence, from Theorem 1, it follows that the solutions of (45) satisfy for any
$\beta>0$ the following:

${\hat{\mathbf{W}}}_{\beta}^{T}{\hat{{\mathbf{H}}}}_{\beta}={\hat{\mathbf{Z}}},\quad{\hat{{\mathbf{H}}}}_{\beta}^{T}{\hat{{\mathbf{H}}}}_{\beta}=\frac{1}{\beta}\mathbf{U}\bm{\Lambda}\mathbf{U}^{T},\quad\text{and}\quad{\hat{\mathbf{W}}}_{\beta}^{T}{\hat{\mathbf{W}}}_{\beta}=\beta\mathbf{V}\bm{\Lambda}\mathbf{V}^{T}.$

Therefore, different regularization between embeddings and classifiers only
affects the geometry of global minimizers of the corresponding UF-SVM (i.e.,
at vanishing regularization) up to introducing an extra scaling factor between
the Gram matrices of embeddings and classifiers. Specifically, this only
affects the relative scaling between the norms of embeddings and classifiers.

##  Appendix D Nuclear-norm relaxations of the UFM

In this section, we gather useful properties of the nuclear-norm-regularized
CE minimization (7), repeated here for convenience:

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

These properties are useful in the proof of the results that appear in Sec. 4.
As a reminder, the nuclear-norm-regularized CE minimization is relevant to us
because of Theorem 2, i.e. it forms a tight convex relaxation of the non-
convex ridge-regularized CE-minimization for the UFM.

The following lemma gathers some basic properties, which we use later to study
the behavior of the solutions to (7) for different regularization strengths.

######  Lemma D.1 (Basic properties of (7)).

The following statements are true.

  1. (i)

There is a unique minimizer ${\hat{\mathbf{Z}}}_{\lambda}$.

  2. (ii)

${\hat{\mathbf{Z}}}_{\lambda}$ satisfies the following necessary and
sufficient first-order optimality conditions:

$\displaystyle\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\mathbf{U}_{\lambda}=-{\lambda}\mathbf{V}_{\lambda},\qquad\left(\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\right)^{T}\mathbf{V}_{\lambda}=-{\lambda}\mathbf{U}_{\lambda},\qquad\|\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\|_{2}\leq{\lambda}.$
(46)

where,
${\hat{\mathbf{Z}}}_{\lambda}=\mathbf{V}_{\lambda}\bm{\Lambda}_{\lambda}\mathbf{U}_{\lambda}^{T}$
is its compact SVD.

  3. (iii)

It holds $\mathds{1}_{k}^{T}\mathbf{V}_{\lambda}=0.$ Thus also,
$\mathds{1}_{k}^{T}{\hat{\mathbf{Z}}}_{\lambda}=0.$

###### Proof.

We prove each statement separately below.

Proof of (ii): This is straightforward from first-order optimality of the
convex program (7). For example, see [41, Lemma C.3] for details.

Proof of (iii): Start from Statement (ii) and use from Lemma A.2 that
$\mathds{1}_{k}^{T}\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})=0$.
Then, it must then be that
$\mathds{1}_{k}^{T}\mathbf{V}_{\lambda}=\frac{1}{{\lambda}}\mathds{1}_{k}^{T}\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\mathbf{U}_{\lambda}=0$,
which in turn implies $\mathds{1}_{k}^{T}{\hat{\mathbf{Z}}}_{\lambda}=0$.

Proof of (i): Now, we prove that ${\hat{\mathbf{Z}}}_{\lambda}$ is unique.
This is a consequence of Lemma D.2 stated below and the fact that
$\mathcal{L}(\mathbf{Z})=\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{)}=\sum_{i\in[n]}\ell_{y_{i}}(\mathbf{z}_{i})$
where $\mathbf{z}_{i}$ are the columns of $\mathbf{Z}$. Specifically, suppose
there were two minimizers
${\hat{\mathbf{Z}}}_{\lambda}=[\mathbf{z}_{1},\ldots,\mathbf{z}_{n}]$ and
${\hat{\mathbf{Z}}}_{\lambda}+\bm{\Delta}$ for
$\bm{\Delta}=[\bm{\delta}_{1},\ldots,\bm{\delta}_{n}]\neq 0$. From Statement
(iii), it must be that $\mathds{1}_{k}^{T}\bm{\Delta}=0$. Thus, there exists
$j\in[n]$ such that
$(\mathds{I}_{k}-\frac{1}{k}\mathds{1}_{k}\mathds{1}_{k}^{T})\bm{\delta}_{j}\neq
0$. With these, we have from Lemma D.2 that

$\displaystyle\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda}+\bm{\Delta})$
$\displaystyle=\ell_{y_{j}}(\mathbf{z}_{j}+\bm{\delta}_{j})+\sum_{i\neq
j}\ell_{y_{i}}(\mathbf{z}_{i}+\bm{\delta}_{i})$
$\displaystyle>\ell_{y_{j}}(\mathbf{z}_{j})+\big{(}\nabla_{\mathbf{z}}\ell_{y_{j}}(\mathbf{z}_{j})\big{)}^{T}\bm{\delta}_{j}+\sum_{i\neq
j}\ell_{y_{i}}(\mathbf{z}_{i})+\sum_{i\neq
j}\big{(}\nabla_{\mathbf{z}}\ell_{y_{i}}(\mathbf{z}_{i})\big{)}^{T}\bm{\delta}_{i}$
$\displaystyle=\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})+\operatorname{tr}\left(\big{(}\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\big{)}^{T}\bm{\Delta}\right)=\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda}),$

where the last equality uses optimality of ${\hat{\mathbf{Z}}}_{\lambda}$. The
above display contradicts optimality of
${\hat{\mathbf{Z}}}_{\lambda}+\bm{\Delta}$ and completes the proof. ∎

######  Lemma D.2 (Auxiliary result—Strict convexity of CE).

For some $y\in[k]$ and $\mathbf{z}=[z_{1},\ldots,z_{k}]$, let
$\ell_{y}(\mathbf{z}):=\log\left(1+\sum_{c\neq
y}e^{-(\mathbf{z}[y]-\mathbf{z}[c])}\right)$. The function $\ell_{y}$ is
strictly convex along any direction on the $(k-1)$-dimensional subspace
orthogonal to $\mathds{1}_{k}$. That is, for all _non-zero_
$\mathbf{v}\in\mathbb{R}^{k}$ such that
$(\mathds{I}_{k}-\frac{1}{k}\mathds{1}_{k}\mathds{1}_{k}^{T})\mathbf{v}\neq
0$, it holds for all $\mathbf{z}\in\mathbb{R}^{k}$ that
$\ell_{y}(\mathbf{z}+\mathbf{v})>\ell_{y}(\mathbf{z})+\big{(}\nabla_{\mathbf{z}}\ell_{y}(\mathbf{z})\big{)}^{T}\mathbf{v}.$

###### Proof.

Define univariate function $g(t)=\ell_{y}(\mathbf{z}+t\mathbf{v})$. From
Taylor’s expansion, for some $\theta\in(0,1)$

$\ell_{y}(\mathbf{z}+\mathbf{v})=\ell_{y}(\mathbf{z})+\big{(}\nabla_{\mathbf{z}}\ell_{y}(\mathbf{z})\big{)}^{T}\mathbf{v}+\frac{1}{2}\mathbf{v}^{T}\nabla_{\mathbf{z}}^{2}\ell_{y}(\mathbf{z}+\theta\mathbf{v})\mathbf{v}.$

Hence, it will suffice showing that
$\mathbf{v}^{T}\nabla_{\mathbf{z}}^{2}\ell_{y}(\mathbf{z})\mathbf{v}>0$ for
any $\mathbf{z}$. Denote for convenience vector $\mathbf{a}\in\mathbb{R}^{k}$
with
$\mathbf{a}[c]:=\frac{e^{-(\mathbf{z}[y]-\mathbf{z}[c])}}{1+\sum_{c^{\prime}\neq
y}e^{-(\mathbf{z}[y]-\mathbf{z}[c^{\prime}])}}$ for all $c\in[k]$. From Lemma
A.2, we have
$\nabla_{\mathbf{z}}\ell_{y}(\mathbf{z})=-\mathbf{e}_{y}+\mathbf{a}.$ Thus, a
straightforward calculation yields
$\nabla^{2}_{\mathbf{z}}\ell_{y}(\mathbf{z})=\operatorname{diag}(\mathbf{a})-\mathbf{a}\mathbf{a}^{T}.$
For the sake of contradiction assume
$\mathbf{v}^{T}\nabla_{\mathbf{z}}^{2}\ell_{y}(\mathbf{z})\mathbf{v}=0$. Then,
since $\sum_{c\in[k]}\mathbf{a}[c]=1$ and $\mathbf{a}[c]\geq 0$, it must be
from Cauchy-Schwartz:

$\sum_{c}\mathbf{v}[c]^{2}\mathbf{a}[c]=\Big{(}\sum_{c}\mathbf{v}[c]\mathbf{a}[c]\Big{)}^{2}\leq\Big{(}\sum_{c}\mathbf{v}[c]^{2}\mathbf{a}[c]\Big{)}^{2}\Big{(}\sum_{c}\mathbf{a}[c]\Big{)}^{2}=\sum_{c}\mathbf{v}[c]^{2}\mathbf{a}[c]$

that $\mathbf{v}=C\mathbf{a}$. But then, $\mathbf{v}^{T}\mathds{1}_{k}=0$,
which violates the lemma’s assumption. ∎

###  D.1 Large ${\lambda}$

######  Lemma D.3 (Large ${\lambda}$ behavior of (7)).

The minimizer is zero, i.e. ${\hat{\mathbf{Z}}}_{\lambda}=0$, if and only if
${\lambda}\geq\|{\hat{\mathbf{Z}}}\|_{2}$, where ${\hat{\mathbf{Z}}}$ is the
SEL matrix.

###### Proof.

From the KKT conditions in Lemma D.1(ii), ${\hat{\mathbf{Z}}}_{\lambda}=0$ is
optimal if and only if
$\|\nabla_{\mathbf{Z}}\mathcal{L}(0)\|_{2}\leq{\lambda}$. The key observation
here is that
$\nabla_{\mathbf{Z}}\mathcal{L}(0)=\mathbf{Y}-\frac{1}{k}\mathds{1}_{k}\mathds{1}_{n}^{T}={\hat{\mathbf{Z}}}.$
(See Lemma A.2 for a formula evaluating the gradient.) Thus,
$\|\nabla_{\mathbf{Z}}\mathcal{L}(0)\|_{2}=\|{\hat{\mathbf{Z}}}\|_{2}$, which
completes the proof. ∎

We note that, for $(R,\rho)$-STEP imbalance the necessary and sufficient
condition of the lemma for ${\hat{\mathbf{Z}}}_{\lambda}=0$ becomes
${\lambda}\geq\|{\hat{\mathbf{Z}}}\|_{2}=\sqrt{R}$ (see Lemma A.3.)

###  D.2 Small ${\lambda}$

######  Lemma D.4 (Small ${\lambda}$ behavior of (7)).

If ${\lambda}<\frac{1}{2}$, then ${\hat{\mathbf{Z}}}_{\lambda}$ is such that
it linearly separates the data, i.e. it holds
${\hat{\mathbf{Z}}}_{\lambda}[y_{i},i]-{\hat{\mathbf{Z}}}_{\lambda}[c,i]>0$
for all $i\in[n],c\neq y_{i}$.

###### Proof.

For the sake of contradiction assume ${\lambda}<1/2$ and there exists
$j\in[n]$ and $c\neq y_{j}$ such that
${\hat{\mathbf{Z}}}_{\lambda}[y_{j},j]-{\hat{\mathbf{Z}}}_{\lambda}[c,j]\leq
0$. Denote
$\mathbf{G}=\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})$ the
gradient. From KKT conditions in Lemma D.1(ii), it must be that

$\displaystyle\|\mathbf{G}\|_{2}\leq{\lambda}<1/2.$ (47)

A simple calculation (e.g., see Lemma A.2) gives
$\left|\mathbf{G}[y_{j},j]\right|=1-\frac{1}{1+\sum_{c^{\prime}\neq
y_{j}}e^{-({\hat{\mathbf{Z}}}_{\lambda}[y_{j},j]-{\hat{\mathbf{Z}}}_{\lambda}[c^{\prime},j])}}$.
But, from assumption on $j,c$:

$1+\sum_{c^{\prime}\neq
y_{j}}e^{-({\hat{\mathbf{Z}}}_{\lambda}[y_{j},j]-{\hat{\mathbf{Z}}}_{\lambda}[c^{\prime},j])}=1+e^{-({\hat{\mathbf{Z}}}_{\lambda}[y_{j},j]-{\hat{\mathbf{Z}}}_{\lambda}[c,j])}+\sum_{c^{\prime}\not\in\\{y_{j},c\\}}e^{-({\hat{\mathbf{Z}}}_{\lambda}[y_{j},j]-{\hat{\mathbf{Z}}}_{\lambda}[c^{\prime},j])}\geq
2.$

Hence, $\left|\mathbf{G}[y_{j},j]\right|\geq 1/2$. Since
$\|\mathbf{G}\|_{2}\geq|\mathbf{G}[y_{j},j]|$, this in turn implies that
$\|\mathbf{G}\|_{2}\geq 1/2$, which contradicts (47). ∎

In Sec. H we combine Theorem 2 with Lemma D.4 above to show that the solution
$({\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda})$ of (1) cannot
satisfy the minority collapse property.

###  D.3 Vanishing ${\lambda}$

######  Proposition 3 (Vanishing ${\lambda}$ behavior of (7)).

Assume $(R,\rho)$-STEP imbalance. Then

$\displaystyle\lim_{{\lambda}\rightarrow
0}\frac{{\hat{\mathbf{Z}}}_{\lambda}}{\|{\hat{\mathbf{Z}}}_{\lambda}\|_{*}}=\frac{{\hat{\mathbf{Z}}}}{\|{\hat{\mathbf{Z}}}\|_{*}}\,,$
(48)

where ${\hat{\mathbf{Z}}}$ is the SEL matrix.

The proposition is an extension of [28, Theorem 3.1] to nuclear-norm
regularization. Its proof follows the exact same steps as in Rosset et al.
[28] who studied $\ell_{p}$-regularization. The critical observation allowing
this is that ${\hat{\mathbf{Z}}}$ is the unique minimizer of (2) thanks to
Theorem 1. Because of that, we can get the following max-margin formulation
for (the normalized) ${\hat{\mathbf{Z}}}$, which is key in the proof of
Proposition 3.

######  Lemma D.5.

Assume $(R,\rho)$-STEP imbalance so that ${\hat{\mathbf{Z}}}$ is the unique
solution of (2) (see Theorem 1). Then, it holds that

$\displaystyle\frac{{\hat{\mathbf{Z}}}}{\|{\hat{\mathbf{Z}}}\|_{*}}:=\arg\max_{\|\mathbf{Z}\|_{*}\leq
1}~{}\min_{i\in[n],c\neq y_{i}}~{}\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i].$ (49)

We present the proof of Proposition 3 together with the proof of Lemma D.5 in
the next section.

####  D.3.1 Proof of Proposition 3

First, by KKT conditions (see Lemma D.1(ii)), as ${\lambda}\rightarrow 0$, we
have $\|\nabla\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\|_{2}\rightarrow 0$.
This, in turn, implies
$\|\nabla\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\|_{*}\rightarrow 0$ since
$\|\nabla\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\|_{*}\leq(k-1)\|\nabla\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\|_{2}$.
Moreover, it implies that

$m_{\lambda}:=\min_{i\in[n],c\neq
y_{i}}~{}{\hat{\mathbf{Z}}}_{\lambda}[y_{i},i]-{\hat{\mathbf{Z}}}_{\lambda}[c,i]$

diverges. To see this, denote
$\mathbf{G}_{\lambda}:=\nabla\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})$ and
note from Lemma A.2 that for all $i\in[n]$
$\mathbf{G}_{\lambda}[y_{i},i]:=-\big{(}1+1/\sum_{c\neq
y_{i}}e^{-({\hat{\mathbf{Z}}}_{\lambda}[y_{i},i]-{\hat{\mathbf{Z}}}_{\lambda}[c,i])}\big{)}^{-1}$.
But,

$\displaystyle\|\nabla\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\|_{2}\geq\max_{i\in[n]}|\mathbf{G}_{\lambda}[y_{i},i]|=\max_{i\in[n]}\big{(}1+1/\sum_{c\neq
y_{i}}e^{-({\hat{\mathbf{Z}}}_{\lambda}[y_{i},i]-{\hat{\mathbf{Z}}}_{\lambda}[c,i])}\big{)}^{-1}\geq\big{(}1+e^{m_{\lambda}}\big{)}^{-1}$
$\displaystyle\qquad\implies
m_{\lambda}\geq\log\big{(}\|\nabla\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\|_{2}^{-1}-1\big{)}.$

Thus, $\|\nabla\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\|_{2}\rightarrow
0\implies m_{\lambda}\rightarrow+\infty.$

Assume for the sake of contradiction that $\lim_{{\lambda}\rightarrow
0}\frac{{\hat{\mathbf{Z}}}_{\lambda}}{\|{\hat{\mathbf{Z}}}_{\lambda}\|_{*}}=\widetilde{\mathbf{Z}}$
for $\widetilde{\mathbf{Z}}\neq{\hat{\mathbf{Z}}}/\|{\hat{\mathbf{Z}}}\|_{*}.$
Then, by Lemma D.5, it must be that

$m=\min_{i\in[n],c\neq
y_{i}}~{}\widetilde{\mathbf{Z}}[y_{i},i]-\widetilde{\mathbf{Z}}[c,i]<\frac{1}{\|{\hat{\mathbf{Z}}}\|_{*}}\,\min_{i\in[n],c\neq
y_{i}}~{}{\hat{\mathbf{Z}}}[y_{i},i]-{\hat{\mathbf{Z}}}[c,i]=:m_{*}.$

Moreover, since $m_{\lambda}\rightarrow+\infty,$ we also have that $m>0$. The
rest of the argument follows mutatis-mutandis the proof of [28, Theorem 2.1].
We repeat here for completeness. By continuity of the minimum margin in
$\mathbf{Z}$, there exists open neighborhood of $\widetilde{\mathbf{Z}}$ on
the nuclear-norm sphere:

$\mathcal{N}_{\widetilde{\mathbf{Z}}}:=\\{\mathbf{Z}\,:\,\|\mathbf{Z}\|_{*}=1,\|\mathbf{Z}-\widetilde{\mathbf{Z}}\|_{2}\leq\delta\\}$

and an $\epsilon>0$ such that $\min_{i\in[n],c\neq
y_{i}}~{}\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i]<m_{*}-\epsilon$ for all
$\mathbf{Z}\in\mathcal{N}_{\widetilde{\mathbf{Z}}}.$ To continue, we use the
following lemma

######  Lemma D.6.

Assume $\mathbf{Z}_{1},\mathbf{Z}_{2}$ such that
$\|\mathbf{Z}_{1}\|_{*}=\|\mathbf{Z}_{2}\|_{*}=1$ and

$0<m_{2}=\min_{i\in[n],c\neq
y_{i}}~{}\mathbf{Z}_{2}[y_{i},i]-\mathbf{Z}_{2}[c,i]<\min_{i\in[n],c\neq
y_{i}}~{}\mathbf{Z}_{1}[y_{i},i]-\mathbf{Z}_{1}[c,i]=m_{1}.$

Then, there exists $T:=T(m_{1},m_{2})$ such that

$\forall t>T\,:\,\mathcal{L}(t\mathbf{Z}_{1})<\mathcal{L}(t\mathbf{Z}_{2}).$

By Lemma D.6, there exists $T:=T(m_{*},m_{*}-\epsilon)$ such that for all
$t>T$ and all $\mathbf{Z}\in\mathcal{N}_{\widetilde{\mathbf{Z}}}$,
$\mathcal{L}(t{\hat{\mathbf{Z}}}/\|{\hat{\mathbf{Z}}}\|_{*})<\mathcal{L}(t\mathbf{Z})$.
Therefore, $\widetilde{\mathbf{Z}}$ cannot be a convergence point of
${\hat{\mathbf{Z}}}_{\lambda}/\|{\hat{\mathbf{Z}}}_{\lambda}\|_{*}.$

We finish the proof by showing how to get Lemmas D.5 and D.6.

##### Proof of Lemma D.5.

Clearly, $\frac{{\hat{\mathbf{Z}}}}{\|{\hat{\mathbf{Z}}}\|_{*}}$ is feasible
in (49). Thus, $\max_{\|\mathbf{Z}\|_{*}\leq 1}~{}\min_{i\in[n],c\neq
y_{i}}~{}\mathbf{Z}[y_{i},i]-\mathbf{Z}[c,i]\geq
1/\|{\hat{\mathbf{Z}}}\|_{*}.$ Now, suppose there exists
$\widetilde{\mathbf{Z}}\neq\frac{{\hat{\mathbf{Z}}}}{\|{\hat{\mathbf{Z}}}\|_{*}}$
such that $\|\widetilde{\mathbf{Z}}\|_{*}\leq 1$ and is a maximizer in the
max-min problem in (49). Then, $\min_{i\in[n],c\neq
y_{i}}~{}\widetilde{\mathbf{Z}}[y_{i},i]-\widetilde{\mathbf{Z}}[c,i]\geq
1/\|{\hat{\mathbf{Z}}}\|_{*}.$ This means,
$\|{\hat{\mathbf{Z}}}\|_{*}\widetilde{\mathbf{Z}}$ is feasible in (2). But
then it must be optimal therein since
$\left\|\|{\hat{\mathbf{Z}}}\|_{*}\widetilde{\mathbf{Z}}\right\|_{*}=\|{\hat{\mathbf{Z}}}\|_{*}\|\widetilde{\mathbf{Z}}\|_{*}\leq\|{\hat{\mathbf{Z}}}\|_{*}$.
From Theorem 1, ${\hat{\mathbf{Z}}}$ is the unique minimizer of (49). Thus, we
have shown that
$\|{\hat{\mathbf{Z}}}\|_{*}\widetilde{\mathbf{Z}}={\hat{\mathbf{Z}}}$, which
contradicts the assumption on $\widetilde{\mathbf{Z}}$ and completes the
proof.

##### Proof of Lemma D.6.

Define $\epsilon:=m_{1}/m_{2}-1>0$ and let $T$ large enough such that
$e^{-T\epsilon m_{2}}n(k-1)<1/2$. We then have the following chain of
inequalities for $t>T$

$\displaystyle\mathcal{L}(t\mathbf{Z}_{1})$
$\displaystyle=\sum_{i\in[n]}\log\left(1+\sum_{c\neq
y_{i}}e^{-t(\mathbf{Z}_{1}[y_{i},i]-\mathbf{Z}_{1}[c,i])}\right)\leq
n\log(1+(k-1)e^{-t\,m_{1}})$ $\displaystyle\leq
n(k-1)e^{-t\,m_{1}}=n(k-1)e^{-t\frac{m_{1}}{m_{2}}\,m_{2}}=n(k-1)e^{-t\,\epsilon\,m_{2}}e^{-t\,m_{2}}$
$\displaystyle<n(k-1)e^{-T\,\epsilon\,m_{2}}e^{-t\,m_{2}}$
$\displaystyle<\frac{e^{-t\,m_{2}}}{2}\leq\frac{e^{-t\,m_{2}}}{1+e^{-t\,m_{2}}}$
$\displaystyle\leq\log(1+e^{-t\,m_{2}})$
$\displaystyle\leq\mathcal{L}(t\mathbf{Z}_{2}).$

The inequality in the third line used that $t>T$ and $\epsilon>0,m_{2}>0$. The
next inequality follows by our choice of $T$. Throughout, we also used both
sides of the inequality $\frac{x}{1+x}\leq\log(1+x)\leq x,x\geq 0.$

##  Appendix E Proofs for Regularized CE Section 4

###  E.1 Proof of Theorem 2

As mentioned in Remark 4.1 the theorem is drawn from [41, Theorem 3.2] with
the following three small adjustments. Since the main proof argument remains
essentially unaltered, we refer the reader to [41, Sec. C] for detailed
derivations. Instead here, we only overview the necessary adjustments.

First, Theorem 2 holds for imbalanced classes. Technically, Zhu et al. [41]
only consider balanced data. However, a close inspection of their proof shows
that such a restriction is not necessary.

Second, Theorem 2 further shows that the nuclear-norm CE minimization in (7)
has a unique solution. We prove this in Lemma D.1(i) in Sec. D.

Finally, Theorem 2 relaxes an assumption $d>k$ in [41, Theorem 3.2] to
$d>k-1$. (In fact, Zhu et al. [41] conjecture that this relaxation is
possible. We close the gap.) The assumption $d>k$ is only used by Zhu et al.
[41] to show there exists nonzero $\mathbf{a}\in\mathbb{R}^{d}$ such that
${\hat{\mathbf{W}}}_{\lambda}^{T}\mathbf{a}=0$ for a stationary point
$({\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda})$ of (1). (This
step is necessary to construct a negative curvature direction at stationary
points for which
$\|\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{W}}}_{\lambda}^{T}{\hat{{\mathbf{H}}}}_{\lambda})\|_{2}>{\lambda}$;
see [41, Sec. C.1].) Indeed, if $d>k$, then existence of $\mathbf{a}$ is
guaranteed because ${\hat{\mathbf{W}}}_{\lambda}$ has $k$ columns implying
$\operatorname{rank}({\hat{\mathbf{W}}}_{\lambda})\leq k$. To relax this
requirement to $d>k-1$, we show in Lemma E.1 below that
${\hat{\mathbf{W}}}_{\lambda}\mathds{1}_{k}=0$. Hence,
$\operatorname{rank}({\hat{\mathbf{W}}}_{\lambda})\leq k-1$.

######  Lemma E.1.

Let ${\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda}$ be a
stationary point of (1). Then, ${\hat{\mathbf{W}}}_{\lambda}\mathds{1}_{k}=0.$
Similarly, any global minimizer $(\hat{\mathbf{W}},\hat{\mathbf{H}})$ of (2)
is such that ${\hat{\mathbf{W}}}\mathds{1}_{k}=0.$

###### Proof.

If $({\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda})$ is a
stationary point of (1) and we denote
${\hat{\mathbf{Z}}}_{\lambda}={\hat{\mathbf{W}}}_{\lambda}^{T}{\hat{{\mathbf{H}}}}_{\lambda}$,
then by stationarity condition and Lemma A.2:

$\displaystyle\nabla_{\mathbf{W}}\mathcal{L}({\hat{\mathbf{W}}}_{\lambda}^{T}{\hat{{\mathbf{H}}}}_{\lambda})=-{\lambda}{\hat{\mathbf{W}}}_{\lambda}\implies{\hat{{\mathbf{H}}}}_{\lambda}\left(\nabla_{\mathbf{Z}}\mathcal{L}({\hat{\mathbf{Z}}}_{\lambda})\right)^{T}=-{\lambda}{\hat{\mathbf{W}}}_{\lambda}\stackrel{{\scriptstyle(\text{Lem.}~{}\ref{lem:grad_ones})}}{{\Longrightarrow}}{\hat{\mathbf{W}}}_{\lambda}\mathds{1}=0.$
(50)

Next, consider any global minimizer of (2). For the sake of contradiction
assume that
$\bar{\mathbf{w}}:=\frac{1}{k}\sum_{c\in[k]}\hat{\mathbf{w}}_{c}\neq\mathbf{0}$,
that is $\|\bar{\mathbf{w}}\|_{2}>0$. Consider the pair
$({\mathbf{V}},\hat{\mathbf{H}})$ where the columns of $\mathbf{V}$ are
defined each such that $\mathbf{v}_{c}=\hat{\mathbf{w}}_{c}-\bar{\mathbf{w}}$.
Clearly, the new pair is feasible, since $(\hat{\mathbf{W}},\hat{\mathbf{H}})$
is feasible. But,

$\sum_{c\in[k]}\|\mathbf{v}_{c}\|^{2}=\sum_{c\in[k]}\|\mathbf{w}_{c}\|^{2}+k\|\bar{\mathbf{w}}\|^{2}-\langle\bar{\mathbf{w}},\sum_{c\in[k]}\mathbf{w}_{c}\rangle=\sum_{c\in[k]}\|\mathbf{w}_{c}\|^{2}-k\|\bar{\mathbf{w}}\|^{2}<\sum_{c\in[k]}\|\mathbf{w}_{c}\|^{2},$

which contradicts optimality of $(\hat{\mathbf{W}},\hat{\mathbf{H}})$. Hence,
it must be that $\bar{\mathbf{w}}=\mathbf{0}$. ∎

###  E.2 Proof of Proposition 1

We prove the proposition right below its statement in Sec. 4.2. The only
remaining thing to show is that for $R>1$ and $k>2$, _not_ all eigenvalues of
the SEL matrix are same. This follows immediately from Lemma A.3 in Sec. A.2.
Specifically, we show in (9), that if $R>1$ and $k>2$, then the maximum
eigenvalue of $\bm{\Lambda}$ is $\sqrt{R}$ and the minimum one is $1$ (thus,
different).

###  E.3 Proof of Proposition 2

The proposition follows by combining Propisition 3 and Theorem 2. First,
thanks to Theorem 2, for all ${\lambda}>0$:

$\frac{{\hat{\mathbf{W}}}_{\lambda}^{T}{\hat{{\mathbf{H}}}}_{\lambda}}{{\|{\hat{\mathbf{W}}}_{\lambda}\|_{F}^{2}/2+\|{\hat{{\mathbf{H}}}}_{\lambda}\|_{F}^{2}/2}}=\frac{{\hat{\mathbf{Z}}}_{\lambda}}{\|{\hat{\mathbf{Z}}}_{\lambda}\|_{*}},$

where ${\hat{\mathbf{Z}}}_{\lambda}$ is the solution to (7). Here, we used the
fact from Equation (8) that

${\|{\hat{\mathbf{W}}}_{\lambda}\|_{F}^{2}}+{\|{\hat{{\mathbf{H}}}}_{\lambda}\|_{F}^{2}}={\operatorname{tr}({\hat{\mathbf{W}}}_{\lambda}^{T}{\hat{\mathbf{W}}}_{\lambda})}+{\operatorname{tr}({\hat{{\mathbf{H}}}}_{\lambda}^{T}{\hat{{\mathbf{H}}}}_{\lambda})}={\operatorname{tr}(\mathbf{V}_{\lambda}\bm{\Lambda}_{\lambda}\mathbf{V}_{\lambda}^{T})}+{\operatorname{tr}(\mathbf{U}_{\lambda}\bm{\Lambda}_{\lambda}\mathbf{U}_{\lambda}^{T})}=2\operatorname{tr}(\bm{\Lambda}_{\lambda})=2\|{\hat{\mathbf{Z}}}_{\lambda}\|_{*}.$

Next, from Proposition 3

$\lim_{{\lambda}\rightarrow
0}\frac{{\hat{\mathbf{Z}}}_{\lambda}}{\|{\hat{\mathbf{Z}}}_{\lambda}\|_{*}}=\frac{{\hat{\mathbf{Z}}}}{\|{\hat{\mathbf{Z}}}\|_{*}}.$

The desired follows by combining the above two displays.

###  E.4 Comparison to one-layer linear model

In Sec. 4.4, we compared the solution to the non-convex minimization (1),
corresponding to a two-layer linear model, to the solution found by an one-
layer linear model. Specifically, the one-layer linear model trains $k$-class
linear classifier $\bm{\Xi}_{k\times n}$ by solving the following convex
ridge-regularized CE:

$\displaystyle\min_{\bm{\Xi}}~{}\mathcal{L}(\bm{\Xi})+\frac{{\lambda}}{2}\|\bm{\Xi}\|_{F}^{2}.$
(51)

The following lemma computes the solution of this minimization.

######  Lemma E.2 (Linear model: Ridge-regularized CE).

Let $\hat{\bm{\Xi}}_{\lambda}$ denote the solution of the convex ridge-
regularized CE minimization. Irrespective of imbalances, for all
${\lambda}>0$, there exists $\alpha_{\lambda}>0$ such that
$\hat{\bm{\Xi}}_{\lambda}=\alpha_{\lambda}{\hat{\mathbf{Z}}}$. Moreover, in
the limit of ${\lambda}\rightarrow 0$, $\lim_{{\lambda}\rightarrow
0}\hat{\bm{\Xi}}_{\lambda}/\|\hat{\bm{\Xi}}_{\lambda}\|_{F}=\hat{\bm{\Xi}}_{0}/\|\hat{\bm{\Xi}}_{0}\|_{F},$
where

$\displaystyle\hat{\bm{\Xi}}_{0}:=\arg\min_{\bm{\Xi}}~{}\|\bm{\Xi}\|_{2}\qquad\text{sub.
to}~{}~{}\bm{\Xi}[y_{i},i]-\bm{\Xi}[c,i]\geq 1,~{}\forall i\in[n],c\neq
y_{i}.$ (52)

In fact, the solution to (52) is the SEL matrix, i.e.,
$\hat{\bm{\Xi}}_{0}={\hat{\mathbf{Z}}}.$

According to the lemma above, the one-layer linear model always finds the SEL
matrix: irrespective of imbalances and for any value of ${\lambda}$ (including
vanishing ones). On the other hand, by Proposition 1, we know that the end-to-
end models minimizing ridge-regularized CE for a two-layer linear network
correspond to the SEL matrix only if data are balanced, or there is two
classes, or regularization is vanishing. Specifically, the solution is
different when $k>2$, $R=1$ and ${\lambda}>0$.

It is also worth noting the following connection between the one- and two-
layer models. Thanks to the convex relaxation of Theorem 2 the end-to-end
model $\mathbf{W}^{T}{\mathbf{H}}$ found by the two-layer model solves CE
minimization with nuclear norm minimization (cf. (7)) compared to the ridge
regularization in (51). Correspondingly, for vanishing regularization, the
two-layer model corresponds to the “nuclear-norm SVM” in (5) compared to the
vanilla SVM in (52). Notably, Theorem 1 proves that the solution to the former
is always ${\hat{\mathbf{Z}}}$, i.e., the same as that of the latter.

###### Proof of Lemma E.2.

The minimization in (51) is convex. Hence, it suffices to prove there exists
$\alpha_{\lambda}$ such that that
$\nabla_{\mathbf{Z}}\mathcal{L}(\alpha_{\lambda}{\hat{\mathbf{Z}}})+{\lambda}\alpha_{\lambda}{\hat{\mathbf{Z}}}=0$.
Thanks to Lemma A.1(v), it suffices that $\exists\alpha_{\lambda}$ such that
${\lambda}\alpha_{\lambda}=\frac{k}{e^{\alpha_{\lambda}}+k-1}.$ It is easy to
check that this equation always has a positive solution $\alpha_{\lambda}>0$
since the LHS is increasing in $(0,\infty)$, the RHS is decreasing in the same
interval, and they both take values in $(1,\infty)$. The fact that following
the regularization path ${\lambda}\rightarrow 0$ leads (in direction) to the
SVM solution follows from [28]. These two combined also show that the solution
to (52) is ${\hat{\mathbf{Z}}}.$ ∎

##  Appendix F Additional results on UFM

EpochsNC error (a) NC

EpochsDistance to SELI/ETF (b) Classifiers

Epochs (c) Embeddings

Epochs (d) Logits

Figure 9:  SGD solution with ridge-regularized CE converging to
$({\hat{\mathbf{Z}}}_{\lambda},{\hat{\mathbf{W}}}_{\lambda},{\hat{{\mathbf{H}}}}_{\lambda})$
for $R=10$ and $\lambda/n=10^{-3}$. The iterates clearly converge towards
$\lambda$-SELI (see Eqn. (8) in Theorem 2) and are far away from ETF. The
distance to SELI also stays large as training progresses. However, note that
it tracks the curves measuring distance to ${\lambda}$-SELI until $\sim 5e3$
epochs.

###  F.1 Experiments with weight-decay

In this section, we show experiments on the UFM supporting the claim of
Theorem 2: the global solution $(\mathbf{W}_{\lambda},{\mathbf{H}}_{\lambda})$
of ridge-regularized CE in (1), call it “$\lambda$-SELI” for convenience (with
some abuse of the term SELI, as the logit matrix does not represent the
simplex encoding anymore for $\lambda>0$), satisfies (8). Moreover any first-
order method that avoids strict saddles converges to that global optimum [41].

Fig. 9 investigates the above claims in a setting of
$(R=10,\rho=\nicefrac{{1}}{{2}})$-STEP imbalance, $k=4$ classes and
$n_{\text{min}}=1$, where we ran SGD on the ridge-regularized CE with
$\lambda/n=10^{-3}$. We set learning rate to $1$ and implement ridge-
regularization as weight-decay on the parameters. We observe the following.
Fig. 9(b), 9(c), and 9(d) verify convergence to $\lambda$-SELI, while Fig.
9(a) verifies that the __(NC)__ property also holds. Also, the solution is
clearly away from ETF geometry (see green lines in Fig. 9). This is a
noteworthy difference of the behavior of learning with imbalanced data,
compared to that with balanced data. With balanced data, the geometry with
ridge-regularization $\lambda>0$ is always ETF. On the contrary, the geometry
for learning from imbalanced data is sensitive to $\lambda$, as discussed in
Sec. 4.2. While the distance from $\lambda$-SELI is the least, the distance to
SELI is smaller compared to ETF. Thus, while SELI is not the “true”
characterization when training with finite ridge-regularization, it is
nevertheless a significantly better approximation than the ETF. In addition,
compared to the ${\lambda}$-SELI solution, the SELI one admits explicit
closed-form expressions (see Sec. B), rather than requiring numerical solution
to a nuclear-norm CE minimization. Finally, note that, up to a certain point
of time during the training, the distances from SELI and $\lambda$-SELI are
comparable. Interestingly, the divergence between the two distances becomes
more prominent at epoch count that also corresponds to a sharp fall of the NC
error-curve in Fig. 9(a).

######  Remark F.1 (A note on $\lambda$ scaling).

In Equation (1), the CE loss is _not_ normalized by the number of examples. On
the other hand, in all our experiments, we normalize the CE loss by $1/n$.
This is why, when denoting the regularization used in experiments, we write
$\nicefrac{{\lambda}}{{n}}$ in the axis-labels of all figures.

###  F.2 Logit regularization and Ridge-decay

Our Proposition 2 proves that the optimal logits of CE minimization for the
UFM with vanishing ridge-regularization is the SEL matrix. However, we also
find in Fig. 5 that the convergence of SGD to the SEL matrix is rather slow.
Motivated by this slow convergence we discuss here _logit-regularized_ CE
minimization, i.e., the solution to the following (non-convex) program:

$\displaystyle\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}+{\lambda}_{L}\|\mathbf{W}^{T}{\mathbf{H}}\|_{F}^{2}.$
(53)

Note that when ${\lambda}=0$, the global solutions of the above minimization
give a logit matrix that aligns with the SEL matrix ${\hat{\mathbf{Z}}}$. This
is easy to see by noting the resemblance to the convex program in (51) and
invoking Lemma E.2.

Empirically, we observe that the above logit regularization helps achieve SGD
convergence to solutions with SEL matrix as logits converge much faster, even
without additional ridge-regularization. Specifically, for
$(R=10,\rho=\nicefrac{{1}}{{2}})$-STEP imbalance, $k=4$ classes and
$n_{\text{min}}=1$, we run SGD on the logit-regularized CE with
$\lambda_{L}/n=10^{-3}$ and with zero ridge-regularization ($\lambda=0$). We
also set the learning rate to $1$. Fig. 10 depicts convergence of the logit-
matrix $\mathbf{Z}$ in the direction of the SEL matrix ${\hat{\mathbf{Z}}}$.
However, we find that this does _not_ ensure of convergence for the individual
geometries of $\mathbf{W}$ and ${\mathbf{H}}$ towards SELI, although their
inner product $\mathbf{W}^{T}{\mathbf{H}}$ aligns well to the SEL matrix.

epochsDistance to SEL Figure 10: GD iterates on logit-regularized CE without
ridge-regularization favor yielding logit matrix in the direction of SEL
matrix ${\hat{\mathbf{Z}}}$.

EpochsNC error (a) NC

EpochsDistance to SELI/ETF (b) Classifiers

Epochs (c) Embeddings

Epochs (d) Logits

Figure 11:  Geometry of SGD solutions minimizing logit-regularized CE with
ridge-decay on UFM; SELI(Solid)/ETF(Dashed), $R=10$(Red)/$R=100$(Blue); See
Sec. F.2 for details.

epochs$\text{margin}_{y}(c)$$R=10$ (a) class $y=0$

epochs (b) class $y=1$

epochs (c) class $y=2$

epochs (d) class $y=3$

epochs$\text{margin}_{y}(c)$$R=100$ (e) class $y=0$

epochs (f) class $y=1$

epochs (g) class $y=2$

epochs (h) class $y=3$

Figure 12: Average Margins for 4 classes corresponding to the experiments of
$R=10$ (top row) and $R=100$ (bottom row) from Fig. 11. We run GD on logit-
regularized ($\lambda_{L}/n=10^{-3}$) CE with ridge-decay
$\lambda_{\text{initial}}/n=10^{-2}$ (see Sec. F.2 for details).

On the other hand, we also find that logit-regularized ERM on the UFM yields
the SELI geometry simultaneously for logits, classifiers and embeddings when
we follow a specific decaying schedule for the ridge-regularization parameter.
Specifically, in the experiments shown in Fig. 11 and 12 below, we start with
a large initial value ${\lambda}/n=10^{-2}$ and progressively decay
${\lambda}$ by a factor of $10$ after every few epochs. We also set a finite
strength of logit-regularization ${\lambda}_{L}/n=10^{-3}$, although the
convergence direction is not sensitive to that choice. We term this scheduling
“ridge-decay”. While the exact dynamics followed by the SGD with such a scheme
require further analysis, “ridge-decay” can be thought of as emulating the
regularization path of ridge-regularization with ${\lambda}\rightarrow 0$.

Fig. 11 show convergence of the GD solution with the above described ridge-
decay to the SELI geometry. Here, we choose $k=4$ classes, with
$(R=10,100,\rho=\nicefrac{{1}}{{2}})$-STEP imbalance and $n_{\text{min}}=1$.
The learning rate is again fixed to $1$. In this experiment, we use GD instead
of SGD since the number of examples is small. This is also useful as it shows
that GD is able to drive the solution towards the SELI geometry without
stochastic updates being necessary.

In summary, we make the following observations from Fig. 11. First, GD
iterates favor the SELI, instead of the ETF geometry, suggesting an implicit
bias towards global minimizers of the UF-SVM. Second, with logit-
regularization and ridge-decay, convergence towards SELI is achieved at a
faster rate than in the case of unregularized CE. Third, while Fig. 10 showed
that the logit matrix converges fast in direction of the SEL matrix
${\hat{\mathbf{Z}}}$ with only logit-regularization, Fig. 11(b) and 11(c) show
that ridge-decay promotes convergence of classifiers and embeddings to their
respective SELI geometries as well. Finally, for completeness, we also present
the NC convergence in Fig. 11(a). The metric used to measure NC is as
described in Sec. G.1.3.

The corresponding margins for the $4$ classes are shown in Fig. 12. For
examples belonging to class $y$, we define average margin with respect to
another class $c\neq y$ as follows:

$\displaystyle\text{margin}_{y}(c):=(\mathbf{w}_{y}-\mathbf{w}_{c})^{T}\bm{\mu}_{y}.$

Note that this is an average over examples from the class $y$ since by NC
property $\mathbf{h}_{i}\approx\bm{\mu}_{y},\forall i\,:\,y_{i}=c$.

We make the following remarks regarding Fig. 12. First, as training
progresses, the (average) margins are positive, thus zero training error is
achieved for all classes. Second, the average margins for a class $y$ with
respect to classes ${c:c\neq y}$ converge to a common value, even though their
initial values differ. This can be seen from the convergence of the four
different colored curves within a plot (e.g. Fig. 12(a)). Third, all margins
for all pairs of classes converge to the same quantity, irrespective of being
majority or minority classes. Note, for instance, from Fig. 12(a),12(b),12(c),
and 12(d) that the final value of all graphs is the same. Finally, the value
of margins stagnates to a level that is governed by the strength of the logit-
regularization $\lambda_{L}$.

##  Appendix G Additional results on real data

This section complements Sec. 5.3 with additional experiments.

###  G.1 Missing details on experiments of Section 5.3

####  G.1.1 Implementation details

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

####  G.1.2 Model accuracies

Consistent with the requirements of the neural collapse phenomenon by Papyan
et al. [26], all models are trained well beyond zero error. Specifically, as
illustrated in Fig. 2 and 6, most of the models achieve zero error around
epoch 120, while training continues until epoch $350$. Table 2 presents the
first epochs at which each model achieves 100 percent accuracy for each value
of the imbalance ratio $R$. For practical purposes, the minimal requirement
for majority classes to be declared having achieved zero training error is set
to $0.2\%$ error. For minority classes $n_{min}\leq 500$ we set $0.00\%$ for
the same requirements.

Zero Error Epoch | R = 1 | R = 5 | R = 10 | R = 100
---|---|---|---|---
ResNet (VGG)
CIFAR10 | 118 (121) | 117 (119) | 119 (119) | 120 (176)
MNIST | 10 (117) | 8 (125) | 11 (127) | 7 (117)
Fashion-MNIST | 117 (119) | 117 (119) | 118 (120) | 117 (141)
Table 2: First epoch that zero training error is achieved in deep-net
eperiments of Sec. G.

Balanced test errors are reported in Table 3. Majority and minority errors are
calculated by averaging the per-class majority and minority errors
respectively. The total error is calculated by averaging all per-class
accuracies. The averaging is done with equal weights. The test error for the
balanced case ($R=1$) is larger than errors reported in [26] since the model
is not trained on the whole dataset, but on $n=25250$ samples.

Test Error | R = 1 | R = 5 | R = 10 | R = 100
---|---|---|---|---
CIFAR10 - ResNet (VGG)
Total | 16.47% (17.27%) | 26.17% (21.08%) | 34.68% (30.03%) | 53.89% (53.21%)
Majority | 19.18% (20.60%) | 11.26% (12.64%) | 10.58% (11.30%) | 9.68% (10.28%)
Minority | 13.76% (13.94%) | 41.08% (30.96%) | 58.78% (48.76%) | 98.1% (96.14%)
MNIST - ResNet (VGG)
Total | 0.55% (0.52%) | 0.78% (0.70%) | 0.96% (0.81%) | 3.04% (4.75%)
Majority | 0.38% (0.35%) | 0.18% (0.25%) | 0.06% (0.06%) | 0.02% (0.08%)
Minority | 0.73% (0.70%) | 1.41% (1.16%) | 1.87% (1.60%) | 6.18% (9.62%)
Fashion-MNIST - ResNet (VGG)
Total | 7.64% (7.54%) | 10.27% (9.26%) | 11.63% (10.35%) | 16.68% (16.67%)
Majority | 8.56% (8.40%) | 5.72% (5.50%) | 5.12% (4.58%) | 4.78% (4.94%)
Minority | 6.72% (6.68%) | 14.82% (13.02%) | 18.14% (16.12%) | 28.58% (28.40%)
Table 3: Balanced test error of deep-net experiments in Sec. G.

####  G.1.3 NC property

From the __(NC)__ property, we expect that the embeddings collapse to their
class means. In order to quantify validity of this property, we follow [26].
Specifically, we compute the within-class covariance ($\bm{\Sigma}_{W}$) and
between-class covariance ($\bm{\Sigma}_{B}$) as,
$\bm{\Sigma}_{W}=\sum_{i\in[n]}(\mathbf{h}_{i}-\bm{\mu}_{y_{i}})(\mathbf{h}_{i}-\bm{\mu}_{y_{i}})^{T}\in\mathbb{R}^{d\times
d},$ and
$\bm{\Sigma}_{B}=\sum_{c\in[k]}(\bm{\mu}_{c}-\bm{\mu}_{G})(\bm{\mu}_{c}-\bm{\mu}_{G})^{T}\in\mathbb{R}^{d\times
d},$ where
$\bm{\mu}_{c}=\frac{1}{n_{c}}\sum_{i\,:\,y_{i}\in[c]}\mathbf{h}_{i}$ is the
mean embedding of class $c$ and
$\bm{\mu}_{G}=\frac{1}{k}\sum_{c\in[k]}\bm{\mu}_{c}$ is their (blanaced)
global mean. We can now measure NC by computing
$\operatorname{tr}(\bm{\Sigma}_{W}\bm{\Sigma}_{B}^{\dagger})/k$. Fig. 13
illustrates how this quantity indeed decreases as training evolves. This
confirms that feature embeddings converge to their class means, regardless of
the imbalance ratio $R$.

EpochsEpochsEpochsResNetVGGDistance to SELI/ETFCIFAR10MNISTFashion-MNIST
Figure 13: NC property for different imbalance levels $R$.

####  G.1.4 Norms of classifiers / embeddings

EpochsEpochsEpochsResNetVGGDistance to SELI/ETFCIFAR10MNISTFashion-MNIST
Figure 14: Convergence of embeddings norm ratio
($\|\bm{\mu}_{\rm{maj}}\|_{2}/\|\bm{\mu}_{\rm{minor}}\|_{2}$) to SELI (solid)
vs ETF (dashed) for different imbalance levels $R$.

Here, we further investigate the geometry of learned embeddings and
classifiers, by focusing on their norms. In particular, we study the ratios
$\tau_{\mathbf{h}}:=\|\mathbf{h}_{\rm{maj}}\|_{2}/\|\mathbf{h}_{\rm{minor}}\|_{2}$
and
$\tau_{\mathbf{w}}:=\|\mathbf{w}_{\rm{maj}}\|_{2}/\|\mathbf{w}_{\rm{minor}}\|_{2}$.
Assuming the classifiers and embeddings follow the SELI geometry, those ratios
admit explicit closed-form expressions thanks to Lemmas B.1 and B.2. To
determine deviations of the measured norm-ratios $\tau_{\mathbf{w}}$ and
$\tau_{\mathbf{h}}$ compared to those reference closed-form expressions, we
calculate and report the following quantity:

$\displaystyle\text{Average}_{c,c^{\prime}}\big{(}|\tau_{\mathbf{w}}(c,c^{\prime})-\hat{\tau}_{\mathbf{w}}|/\hat{\tau}_{\mathbf{w}}\big{)},$

where $\hat{\tau}_{\mathbf{w}}$ is given by Lemma B.1 for SELI and is equal to
$1$ for ETF, and,
$\tau_{\mathbf{w}}(c,c^{\prime})=\|\mathbf{w}_{c}\|_{2}/\|\mathbf{w}_{c^{\prime}}\|_{2}$
with $c$ being a majority and $c^{\prime}$ a minority class. Similarly, we
compute distances for the norm-ratios of centered mean embeddings
$\overline{\bm{\mu}_{c}}$. Fig. 7 and 14 depict these metrics during training
of the ResNet and VGG networks. The results confirm once more that the SELI
geometry accurately captures features of the learned geometries. On the
contrary, this is not the case for ETF when data are imbalanced. We observe
that convergence to SELI geometry (and respective deviation from ETF) is more
pronounced for the classifier weights and becomes elusive for the embeddings
particularly for large imbalance ratios ($R=100$.)

####  G.1.5 Non-alignment of classifiers and embeddings

EpochsEpochsEpochsResNetVGGDistance to SELI/ETFCIFAR10MNISTFashion-MNIST
Figure 15: Alignment of minority embeddings and classifiers. Convergence of
angles to SELI (solid) and ETF (dashed) for different imbalance levels $R$.

While from previous empirical results on balanced datasets [26], we expect an
alignment between the classifiers and embeddings, Lemma B.5 suggests these two
geometries deviate as data becomes more imbalanced. To verify this property,
we compute the angle between mean embeddings and their corresponding
classifiers, and measure the deviation from the SELI geometry. Namely, let
$\theta_{c}=\operatorname{Cos}(\mathbf{w}_{c},\mathbf{h}_{c})$. Then, similar
to the previous section, we compute,

$\displaystyle\text{Average}_{c}\big{(}|\theta_{c}-\hat{\theta}|/\hat{\theta}\big{)},$

where $c$ ranges over minority classes and $\hat{\theta}$ is given by (18).
Fig. 15 shows how this quantity evolves during training. From Fig. 8(b), we
know that the embeddings and classifiers of the majority classes remain
aligned even for highly imbalanced data, thus we only analyze the impact of
imbalance ratio on the minority classes.

####  G.1.6 Majority vs minority geometry

CIFAR10EpochsEpochsEpochsResNetVGGDistance to SELI/ETF

MNISTEpochsEpochsEpochsResNetVGGDistance to SELI/ETF

Fashion-MNISTEpochsEpochsEpochsResNetVGGDistance to SELI/ETF(b)
$\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{minor}}-{\text{minor}}}$(a)
$\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{maj}}}$(c)
$\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{minor}}}$

Figure 16: Convergence of learned classifiers’ majority and minority
individual geometries to the SELI (solid lines) vs ETF (dashed lines)
geometries.

CIFAR10EpochsEpochsEpochsResNetVGGDistance to SELI/ETF

MNISTEpochsEpochsEpochsResNetVGGDistance to SELI/ETF

Fashion-MNISTEpochsEpochsEpochsResNetVGGDistance to SELI/ETF(b)
$\underline{\mathbf{G}_{\mathbf{M}}}^{{\text{minor}}-{\text{minor}}}$(a)
$\underline{\mathbf{G}_{\mathbf{M}}}^{{\text{maj}}-{\text{maj}}}$(c)
$\underline{\mathbf{G}_{\mathbf{M}}}^{{\text{maj}}-{\text{minor}}}$

Figure 17: Convergence of learned classifiers’ majority and minority
individual geometries to the SELI (solid lines) vs ETF (dashed lines)
geometries.

In order to better understand the individual behavior of majorities and
minorities, we now compare individual quadrants of the (normalized)
$\underline{\mathbf{G}_{\mathbf{W}}}$ and
$\underline{\mathbf{G}_{\mathbf{H}}}$ matrices. Concretely, let

$\underline{\mathbf{G}_{\mathbf{W}}}=\begin{bmatrix}\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{maj}}}&\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{minor}}}\\\
\big{(}\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{minor}}}\big{)}^{T}&\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{minor}}-{\text{minor}}}\end{bmatrix}$

be a partition of the normalized
$\underline{\mathbf{G}_{\mathbf{W}}}=\mathbf{G}_{\mathbf{W}}/\|\mathbf{G}_{\mathbf{W}}\|_{F}$
to $(k/2)\times(k/2)$ sub-blocks. Comparing quadrants
$\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{maj}}},\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{minor}}}$
and $\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{minor}}-{\text{minor}}}$ to
the corresponding quadrants of the reference SELI/ETF matrix
$\hat{\mathbf{G}}_{\mathbf{W}}$ allows us to “zoom-in” the majority-majority,
majority-minority and minority-minority structures. Entirely analogous
calculations allow the same for the embeddings.

Classifiers Geometry. Fig. 16 confirms that both majority and minority
geometries converge to SELI properly. Interestingly, we see that the
minorities diverge the most from the equiangular structure of ETF geometry.

Embeddings Geometry. We find thanks to Fig. 17 that the “error” in convergence
of embeddings to SELI geometry (compare to the better convergence for
classifiers) shown previously in Fig. 2 and 6 is primarily due to the minority
class geometries. However, an overall inspection of the subfigures shows that
embeddings also tend to align better to SELI compared to ETF. This alignment
property is pronounced in the case of majority geometries (see
$\underline{\mathbf{G}_{\mathbf{M}}}^{{\text{maj}}-{\text{maj}}}$).

###  G.2 Capturing weight-decay with regularized UFM

EpochsDistance to $\lambda$ -SELI/SELI/ETF (a) Classifiers

Epochs (b) Embeddings

Figure 18: Distances of ResNet learned classifiers and mean-embeddings trained
on CIFAR10 data with imbalance ratio $R=10$ from the $\lambda$-SELI geometry
(aka solution to (7) as defined in Theorem 2) for different values of
$\lambda$, as well as, from the SELI and ETF geometries.

In Fig. 18 we compare for $R=10$ the distances of
$\underline{\mathbf{G}_{\mathbf{W}}}$ and
$\underline{\mathbf{G}_{\mathbf{M}}}$ matrices to various $\lambda$-SELI
geometries for different values of regularization $\lambda$. Specifically, for
the $\lambda$-SELI geometries, we obtained the reference matrices
$\hat{\mathbf{G}}_{\mathbf{W}}^{\lambda},\hat{\mathbf{G}}_{\mathbf{M}}^{\lambda}$
as follows. For each value of ${\lambda}$, we solve the nuclear-norm CE
minimization in (7) to find ${\hat{\mathbf{Z}}}_{\lambda}$ for $k=10$ and
$R=10$ (to match the CIFAR10 settings). We then form
$\hat{\mathbf{G}}_{\mathbf{W}}^{\lambda},\hat{\mathbf{G}}_{\mathbf{M}}^{\lambda}$
as described in the first paragraph of Sec. 5 only now using
${\hat{\mathbf{Z}}}_{\lambda}$ instead of the SELI ${\hat{\mathbf{Z}}}$. For
comparison, we also plot the distances to the SELI and ETF geometries.

Note that we have experimented with a wide range of values for the
regularization ${\lambda}$. Among those is the value $5e-4$ that matches with
the choice of weight-decay parameters in the deep-net experiments. Recall also
from the discussion in Sec. 4 that ${\hat{\mathbf{Z}}}_{\lambda}$ is sensitive
to $\lambda$ in this setting where $R=10,k=10.$

We make the following interesting observations from Fig. 18. First, note that
for classifiers the minimum distance is that to SELI. The distance of the
embeddings’ geometry to SELI is also among the lowest ones. Specifically,
despite being slightly larger than that from $\lambda$-SELI for a few values
of $\lambda$, the difference is very small. This suggests that SELI is indeed
a good approximation for the learned geometry even when training with finite
weight-decay. Besides, there are two key advantages of the SELI over the
$\lambda$-SELI geometry. First, it is unclear what the mapping ought to be (if
such a mapping exists) between training-implementation choices (such as
weight-decay) and ${\lambda}$. Second, even if such a mapping was known, the
SELI geometry has the unique advantage of being expressed simply in terms of
the (SVD of the) SEL matrix. In fact, as we show in Sec. B it is possible to
get closed-form expressions for the norms and angles describing the geometry.
This not only makes calculations much easier, but also it allows further
analysis of the properties (e.g. quantifying norm-ratios as in Fig. 7).

###  G.3 Additional experiments for minority ratios $\rho\neq 1/2$

Thus far, in our previous experiments we considered imbalanced data with
minority ratio $\rho=1/2$, i.e. same number of minorities and majorities.
However, note that our theoretical results hold for any value of $\rho$.
Specifically, Theorem 1 shows that the solution of the UF-SVM follows the SELI
geometry irrespective of $\rho$. Here, we empirically study convergence to the
SELI geometry for a ResNet-18 model on ($R$,$\rho$)-STEP imbalanced CIFAR10
data, for two values of minority ratio $\rho=0.3$ and $0.7$. These experiments
complement our previous demonstrations for $\rho=0.5$. Specifically, we create
training set of the same size of $n=15350$ in all experiments for a fair
comparison.999This is smaller than the total number $n=25250$ of examples used
previously in our experiments for $\rho=1/2$. The reason is that there is a
limited number of $5000$ images per class in CIFAR-10 making it impossible to
have $(R=100,\rho=0.7)$-STEP imbalanced CIFAR-10 data. All other experimental
settings are as described in Section G.1.1. Figs. 19, 20 and 21 demonstrate
how classifiers and embeddings converge to the proposed SELI geometry.
Consistent with the previous experiments, the learnt geometries of deep
networks are well-captured by the SELI. We also observe empirically that
larger values of $\rho$ exhibit slightly faster convergence.

Distance to SELI/ETF

$\rho=0.3$

EpochsDistance to SELI/ETF (a) Classifiers

$\rho=0.7$Epochs (b) Embeddings

Epochs (c) Logits

Figure 19: Impact of $\rho$ on the convergence of ResNet geometry to the SELI,
trained on CIFAR10.

$\rho=0.3$Distance to SELI/ETF

$\rho=0.7$EpochsEpochsEpochsDistance to SELI/ETF(b)
$\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{minor}}-{\text{minor}}}$(a)
$\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{maj}}}$(c)
$\underline{\mathbf{G}_{\mathbf{W}}}^{{\text{maj}}-{\text{minor}}}$

Figure 20: Impact of $\rho$ on the convergence of majority/minority
classifiers of ResNet model trained on CIFAR10.

$\rho=0.3$Distance to SELI/ETF

$\rho=0.7$EpochsEpochsEpochsDistance to SELI/ETF(b)
$\underline{\mathbf{G}_{\mathbf{M}}}^{{\text{minor}}-{\text{minor}}}$(a)
$\underline{\mathbf{G}_{\mathbf{M}}}^{{\text{maj}}-{\text{maj}}}$(c)
$\underline{\mathbf{G}_{\mathbf{M}}}^{{\text{maj}}-{\text{minor}}}$

Figure 21: Impact of $\rho$ on the convergence of majority/minority embeddings
of ResNet model trained on CIFAR10.

##  Appendix H Implications on minority collapse

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

##### Summary of findings by Fang et al. [3].

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

  1. FHLS(1)

In [3, Theorem 5] they prove for a constrained UFM, that
$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})=1$
(here, $\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime}$ are any two
distinct minority classifiers.)

  2. FHLS(2)

They also find numerically that the solution to the same constrained UFM gives
$\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})=1$
for any $R>R_{0}$ for some _finite_ threshold $R_{0}$.

  3. FHLS(3)

Their experiments, specifically [3, Fig. 3], suggest that for fixed number of
classes $k$, the value of the threshold $R_{0}$ increases as the constraint
parameter gets relaxed and also as the ratio $\rho$ of minority classes
increases.

  4. FHLS(4)

Finally, they validate the minority collapse phenomenon on real imbalanced
datasets trained with deep-nets. Their real-data experiments (e.g. [3, Fig.
2,4]) suggest the following.

    1. (a)

Consistently, as $R$ increases, the cosine similarity between minority classes
increases until it reaches one.

    2. (b)

The value of $R$ after which the cosine becomes one (i.e. minority collapse is
reached) depends critically on the weight-decay. For small weight decay ($\sim
5e-4$), it takes $R>1000$ to reach minority collapse. It is only for larger
weight decay ($\sim 5e-3$) that minority collapse occurs for $R\sim 100$.

##### Our novelties.

Before discussing implications of our results for minority collapse, we
highlight the following key features of our study.

  * •

Entire geometry: We describe the _entire geometry of classifiers and
embeddings for both majority and minority classes_ (not only the geometry of
minority classes.)

  * •

Finite imbalance levels: Our geometric characterizations (aka SELI geometry)
hold for _all finite values of the imbalance ratio $R$_ (not only
asymptotically.)

  * •

Vanishing regularization: We focus on CE training with vanishing
regularization. (As such, our geometry characterizations result from analyzing
the UF-SVM.)

##### Contact points: What do our results say about minority collapse?

  * •

For zero regularization (aka UF-SVM), there is no minority collapse for any
finite value of $R$. Specifically, we show in Lemma B.3 that for
$(R,1/2)$-STEP imbalance
$\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})=\nicefrac{{(R-7)}}{{\left(R-7+2k(2+\sqrt{(R+1)/2})\right)}}<1.$
This does not contradict Finding FHLS(2) since here we consider zero
regularization; all their numerical evaluations are with finite
regularization.

  * •

Minority collapse occurs (only) _asymptotically_ in $R$ for the UF-SVM.
Specifically, we show in Corollary 2.4 that
$\lim_{R\rightarrow\infty}\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})=1$;
see also Fig. 3(c). This can be seen as a different manifestation of the
Finding FHLS(1), this time for the UF-SVM, instead of constrained CE
minimization.

  * •

There is no minority collapse for small regularization strength when training
the UFM with regularized CE minimization. Specifically, we show in Lemma D.4
that for any finite imbalance values $R,\rho$, there is no minority collapse
in the solutions of Eqn. (1) when ${\lambda}<1/2.$ Instead, the CE solution
perfectly separates the training data. Our result theoretical justifies the
numerical Findings FHLS(3) and FHLS(4)(b). To establish the connection to the
setting of Fang et al. [3], we need to normalize the CE loss in (1) by a
factor of $1/n$ (see [3, Eqn. (15)]). For this normalized minimization, Lemma
D.4 ensures _no_ minority collapse provided that

$\displaystyle
2{\lambda}<\frac{1}{n}=\frac{1}{(\rho+R\overline{\rho})k}=\frac{1}{(R-\rho(R-1))k}\,.$
(54)

Put in terms of imbalance ratio, we prove that

$\displaystyle\text{Minority collapse
requires}~{}~{}R>f({\lambda},\rho):=\frac{\frac{1}{2k{\lambda}}-\rho}{1-\rho}\,.$
(55)

It is straightforward to check that $f({\lambda},\rho)$ is increasing in
$\rho$ and decreasing in ${\lambda}$. Thus, we show that the minority collapse
threshold $R_{0}$ (see Finding FHLS(3)) increases with the minority ratio
$\rho$ and with the inverse regularization parameter $1/{\lambda}$. This
finding explains the behavior reported empirically in [3, Fig. 3] for the UFM
and in [3, Fig. 2,4] for real data. 101010When referring to [3, Fig. 3] keep
in mind that they simulate constrained, rather than regularized, CE
minimization. Hence, larger constraint parameters mean larger _inverse_
regularization parameter $1/{\lambda}.$

  * •

The angle between minority classifiers decreases monotonically with the
imbalance ratio $R$ for the UF-SVM. Specifically, it can be checked easily by
direct differentiation that the formula in Lemma B.3 giving
$\operatorname{Cos}(\mathbf{w}_{\rm{minor}},\mathbf{w}_{\rm{minor}}^{\prime})$
is increasing in $R$. This can be seen as a theoretical justification of the
empirical Finding FHLS(4)(a).

##  Appendix I Additional related work

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

###  I.1 Additional works on Neural Collapse

Beyond CE minimization, a series of recent works study and analyze the neural
collapse phenomenon when training with square loss. Interestingly, Graf et al.
[5], Fang et al. [3] discover and analyze neural collapse for similarity-type
losses, such as the self-supervised contrastive loss, which trains only for
embeddings. To the best of our knowledge, all these works restrict attention
to balanced classification. Our work shows that it is possible to obtain
explicit geometric characterizations in class-imbalanced settings when
training with CE. Hence, it also opens the way to extending the analysis to
square-loss minimization.

Potential connections of neural collapse to generalization and transferability
is a less well-understood topic. Some initial investigations appear in the
recent works [11, 4, 9]. Our results are not immediately conclusive about
generalization. However, as mentioned in Sec. 6 our results have the potential
to offer new perspectives on generalization, since they uncover different
geometries (aka SELI for different $R$ values), each leading to different
generalization (worse for increasing $R$ [1, 2]).

######  Remark I.1 (Last-layer peeled model (LPM)).

Around the same time that the UFM was proposed by Mixon et al. [24] (see also
Lu and Steinerberger [21], Graf et al. [5]), the same model was independently
formulated and analyzed by Fang et al. [3] under the alternative name of
“last-layer peeled model (LPM)".

######  Remark I.2 (__(NC)__ and __(ETF)__ properties in [26]).

The formalization of Neural collapse by Papyan et al. [26] involved four NC
properties. The first property concerns the collapse of class embeddings to
their corresponding means. Properties two and three concern the geometry of
class-means and classifier-weights, specifically their alignment and
convergence to a simplex ETF geometry. Property four is a consequence of the
other three properties, hence is less important in the formalization and we do
not discuss it further. Motivated by our findings, we propose and use here a
regrouping/renaming of the aforementioned three properties. We refer to the
first property as the __(NC)__ property, and, to the second and third
properties as the __(ETF)__ property. We argue that this distinction is
important towards a formulation that is invariant across class-imbalances, by
showing that the ETF property is _not_ invariant and replacing it with the
__(SELI)__ property. For balanced data, the latter simplifies to the ETF
property.

###  I.2 Implicit bias

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

###  I.3 Matrix factorization and low-rank recovery

The connection between the study of the UFM for the purpose of neural collapse
analysis and the literatures on matrix factorization and low-rank matrix
recovery (see for example [36]) is uncovered and first exploited by Zhu et al.
[41] and Fang et al. [3]. Thus, we refer the interested reader to those papers
for a list of references and detailed discussion (specifically see Zhu et al.
[41, Sec. 3.2]). Specializing this discussion to the UF-SVM that is of main
interest to us, we note its close ties to the formulation of the hard-margin
matrix factorization problem as studied by Srebro et al. [31]. The author
formulated the problem of fitting a binary target matrix $\mathbf{Y}$ (ie.
with entries $\pm 1$) with a low-rank matrix $\mathbf{W}^{T}{\mathbf{H}}$ as
the minimization

$\displaystyle\min_{\mathbf{W},{\mathbf{H}}}\|\mathbf{W}^{T}{\mathbf{H}}\|_{*}\quad\text{sub.
to}~{}~{}\Big{(}\mathbf{Y}\odot\mathbf{W}^{T}{\mathbf{H}}\Big{)}[c,i]\geq
1,~{}\forall(c,i)\in{\mathcal{S}},$ (56)

where ${\mathcal{S}}$ is a given subset of observed entries of $\mathbf{Y}$.
Despite being non-convex, they derived a convex reformulation based on duality
and a corresponding procedure for finding a solution to (56) via essentially
solving an SDP and an appropriate system of linear equations corresponding to
the active constraints. The non-convex max-margin problem (2) that we
investigate bears similarities to (56). Specifically, for an one-hot encoding
and fully observed $\mathbf{Y}$, (56) is essentially the binary analogue of
(2). Importantly in our setting, we are able to calculate the solution to (2)
in closed form, that is without requiring numerically solving an SDP. Finally,
as mentioned in Sec. E.4 a byproduct of Theorem 1 is that the nuclear-norm
max-margin minimization (5) has the same solution as the vanilla max-margin
with Frobenius norm. Although different, somewhat related settings were
frobenius-norm penalized problems give same solutions as nuclear-norm
penalized ones have been studied in the low-rank representation literature,
e.g. [34, 27].

###  I.4 Class-imbalanced deep learning

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

Related ideas appeared very recently in the contemporaneous works [38, 37],
where the authors design loss functions for class-imbalanced learning in an
attempt to enforce a geometry that is alike the ETF geometry for balanced
data. However, they do not characterize the joint geometry of classifiers and
embeddings under class imbalances as we do here.

###  I.5 On the Simplex-encoding interpolation

Our analysis of the UF-SVM uncovers the unique role played by the SEL matrix.
Specifically, Theorem 1 shows that the global minimizers
$({\hat{\mathbf{W}}},{\hat{{\mathbf{H}}}})$ of the non-convex UF-SVM are such
that the resulting logit matrix ${\hat{\mathbf{W}}}^{T}{\hat{{\mathbf{H}}}}$
satisfies all constraints with equality and also it equals the SEL matrix
${\hat{\mathbf{Z}}}$. Our finding is related to (in fact, can be seen as an
extension of) a recent result by Wang et al. [35]. In a different context and
with different research objective, Wang et al. [35] derived a deterministic
condition under which the solution to the (convex) vanilla SVM (like the one
in (52) but with general inputs, not necessarily the basis vectors
$\mathbf{e}_{i}$ resulting in the UFM) finds logits that interpolate a simplex
encoding of the labels. Theorem 1 goes far beyond: it studies a non-convex SVM
and since it applies directly to the UFM, it does not involve deterministic
input conditions for the result to hold. That said, it might be interesting
future work to derive similar conditions on the inputs of the non-convex max-
margin problem such that it gives optimal logits interpolating the simplex
encoding of the labels.