#  Layer-Peeled Model: Toward Understanding Well-Trained
Deep Neural Networks

Cong Fang<EMAIL_ADDRESS>Hangfeng He<EMAIL_ADDRESS>Qi Long
<EMAIL_ADDRESS>Weijie J. Su<EMAIL_ADDRESS>
###### Abstract

In this paper, we introduce the Layer-Peeled Model, a nonconvex yet
analytically tractable optimization program, in a quest to better understand
deep neural networks that are trained for a sufficiently long time. As the
name suggests, this new model is derived by isolating the topmost layer from
the remainder of the neural network, followed by imposing certain constraints
separately on the two parts. We demonstrate that the Layer-Peeled Model,
albeit simple, inherits many characteristics of well-trained neural networks,
thereby offering an effective tool for explaining and predicting common
empirical patterns of deep learning training. First, when working on class-
balanced datasets, we prove that any solution to this model forms a simplex
equiangular tight frame, which in part explains the recently discovered
phenomenon of neural collapse in deep learning training [PHD20]. Moreover,
when moving to the imbalanced case, our analysis of the Layer-Peeled Model
reveals a hitherto unknown phenomenon that we term Minority Collapse, which
fundamentally limits the performance of deep learning models on the minority
classes. In addition, we use the Layer-Peeled Model to gain insights into how
to mitigate Minority Collapse. Interestingly, this phenomenon is first
predicted by the Layer-Peeled Model before its confirmation by our
computational experiments.

University of Pennsylvania

January 26, 2021

###### Contents

  1. 1 Introduction
    1. 1.1 Two Applications
    2. 1.2 Related Work
  2. 2 Derivation
  3. 3 Layer-Peeled Model for Explaining Neural Collapse
    1. 3.1 Cross-Entropy Loss
    2. 3.2 Extensions to Other Loss Functions
  4. 4 Layer-Peeled Model for Predicting Minority Collapse
    1. 4.1 Technique: Convex Relaxation
    2. 4.2 Minority Collapse
    3. 4.3 Experiments
  5. 5 How to Mitigate Minority Collapse?
  6. 6 Discussion
  7. A Proofs
    1. A.1 Balanced Case
      1. A.1.1 Proofs of Theorem 1 and Proposition 2
      2. A.1.2 Proofs of Theorems 3 and 4
    2. A.2 Imbalanced Case
      1. A.2.1 Proofs of Lemma 1 and Proposition 1
      2. A.2.2 Proof of Theorem 5
  8. B Additional Results

##  1 Introduction

In the past decade, deep learning has achieved remarkable performance across a
range of scientific and engineering domains [KSH17, LBH15, SHM+16].
Interestingly, these impressive accomplishments were mostly achieved by
empirical intuition and various maneuvers, though often plausible, without
much principled guidance from a theoretical perspective. On the flip side,
however, this reality also suggests the great potential a theory could have
for advancing the development of deep learning methodologies in the coming
decade.

Unfortunately, it is not easy to develop a theoretical foundation for deep
learning. Perhaps the most difficult hurdle lies in the nonconvexity of the
optimization problem for training neural networks, which, loosely speaking,
stems from the interaction between different layers of neural networks. To be
more precise, consider a neural network for $K$-class classification as a
function, which in its simplest form reads

$\bm{f}(\mathbf{x};\bm{W}_{\textnormal{full}})=\mathbf{W}_{L}\sigma(\mathbf{W}_{L-1}\sigma(\cdots\sigma(\mathbf{W}_{1}\mathbf{x}))).$

Here,
$\bm{W}_{\textnormal{full}}:=\\{\mathbf{W}_{1},\mathbf{W}_{2},\ldots,\mathbf{W}_{L}\\}$
denotes the partition of the weights in a matrix form according to layers and
$\sigma(\cdot)$ is a nonlinear activation function such as the ReLU.111Here
the function only outputs logits in $\mathbb{R}^{K}$, and we omit the softmax
step. The last-layer weights, $\mathbf{W}_{L}$, consists of $K$ vectors that
correspond to the $K$ classes. For simplicity, we omit the bias term and other
operations such as max-pooling. Owing to the complex and nonlinear interaction
between the $L$ layers, when applying stochastic gradient descent to the
optimization problem

$\min_{\bm{W}_{\textnormal{full}}}~{}\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\bm{f}(\mathbf{x}_{k,i};\bm{W}_{\textnormal{full}}),\mathbf{y}_{k})+\frac{\lambda}{2}\|\bm{W}_{\textnormal{full}}\|^{2}$
(1)

with a loss function $\mathcal{L}$ for training the neural network, it becomes
very difficult to pinpoint how a given layer influences the output $\bm{f}$
(above, $\\{\mathbf{x}_{k,i}\\}_{i=1}^{n_{k}}$ denotes the training examples
in the $k$-th class, with label $\mathbf{y}_{k}$,222We often encode
$\mathbf{y}_{k}$ as a $K$-dimensional one-hot vector with 1 in the $k$-th
entry. $N=n_{1}+\cdots+n_{K}$ is the total number of training examples,
$\lambda>0$ is the weight decay parameter, and $\|\cdot\|$ throughout the
paper is the $\ell_{2}$ norm). Worse, this difficulty in analyzing deep
learning models is compounded by an ever growing number of layers.

(a) 1-Layer-Peeled Model

(b) 2-Layer-Peeled Model

Figure 1: Illustration of Layer-Peeled Models. The right panel represents the
2-Layer-Peeled Model, which is discussed in Section 6. For each panel, we
maintain the details of the white (top) box, whereas the gray (bottom) box is
modeled by a simple decision variable for every training example.

Therefore, an attempt to develop a tractable and comprehensive theory for
demystifying deep learning would presumably first need to simplify the
interaction between a large number of layers. Following this intuition, in
this paper we introduce the following optimization program as a surrogate
model for Program (1) for unveiling quantitative patterns of deep neural
networks:

$\displaystyle\min_{\mathbf{W}_{L},\mathbf{H}}$
$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\mathbf{W}_{L}\bm{h}_{k,i},\mathbf{y}_{k})$
(2) subject to
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}\leq
E_{W},$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}\right\|^{2}\leq
E_{H},$

where the decision variables
$\mathbf{W}_{L}=\left[\mathbf{w}_{1},\ldots,\mathbf{w}_{K}\right]^{\top}\in\mathbb{R}^{K\times
p}$ is, as in Program (1), comprised of $K$ linear classifiers in the last
layer, $\bm{H}=[\mathbf{h}_{k,i}:1\leq k\leq K,1\leq i\leq
n_{k}]\in\mathbb{R}^{p\times N}$ correspond to the $p$-dimensional last-layer
activations/features of all $N$ training examples333Strictly speaking,
$\bm{H}$ is used to model the activations from the $L-1$ layer. Note that the
dimension of the vector $\mathbf{w}_{k}$ is also $p$., and $E_{H}$ and $E_{W}$
are two positive scalars. Although still nonconvex, this new optimization
program is presumably much more amenable for analysis than the old one (1) as
the interaction now is also between two variables.

In relating Program (2) to the optimization problem (1), a first simple
observation is that
$\bm{f}(\mathbf{x}_{k,i};\bm{W}_{\textnormal{full}})=\mathbf{W}_{L}\sigma(\mathbf{W}_{L-1}\sigma(\cdots\sigma(\mathbf{W}_{1}\mathbf{x}_{k,i})))$
in (1) is replaced by $\mathbf{W}_{L}\mathbf{h}_{k,i}$ in (2). Put
differently, the black-box nature of the last-layer features, namely
$\sigma(\mathbf{W}_{L-1}\sigma(\cdots\sigma(\mathbf{W}_{1}\mathbf{x}_{k,i})))$,
is now modeled by a simple decision variable $\mathbf{h}_{k,i}$ with a
constraint on its $\ell_{2}$ norm. Intuitively speaking, this simplification
is done via peeling off the topmost layer from the neural network. Thus, we
call the optimization program (2) the 1-Layer-Peeled Model, or simply the
Layer-Peeled Model.

At a high level, the Layer-Peeled Model takes a top-down approach to the
analysis of deep neural networks. As illustrated in Figure 1, the essence of
the modeling strategy is to break down the neural network from top to bottom,
specifically singling out the topmost layer and modeling all bottom layers
collectively as a single variable. In fact, the top-down perspective that we
took in the development of the Layer-Peeled Model was inspired by a recent
breakthrough made by Papyan, Han, and Donoho [PHD20], who discovered a
mathematically elegant and pervasive phenomenon, termed neural collapse,
through massive deep learning experiments on datasets with balanced classes.
Roughly speaking, neural collapse refers to the emergence of certain geometric
patterns of the last-layer features
$\sigma(\mathbf{W}_{L-1}\sigma(\cdots\sigma(\mathbf{W}_{1}\mathbf{x}_{k,i})))$
and the last-layer classifiers $\mathbf{W}_{L}$, when the neural network is
well-trained in the sense that it is toward not only zero misclassification
error but also negligible cross-entropy loss.444In general, any global
minimizer of Program (1) does not yield zero cross-entropy loss due to the
penalty term. This top-down approach was also taken in [WL90, SHN+18, OS20,
YCY+20, Sha20] to investigate various aspects of deep learning models.

###  1.1 Two Applications

Despite its plausibility, the ultimate test of the Layer-Peeled Model lies in
its ability to faithfully approximate deep learning models through explaining
empirical observations and even predicting new phenomena. In what follows, we
provide convincing evidence that the Layer-Peeled Model is up to this task by
presenting two findings. To be concrete, we remark that the results below are
concerned with well-trained deep learning models, which correspond to, in
rough terms, (near) optimal solutions of Program (1).

##### Balanced Data.

When the dataset has the same number of training examples in each class,
[PHD20] experimentally observed that neural collapse emerges in well-trained
deep learning models (1) with the cross-entropy loss: the last-layer features
from the same class tend to be very close to their class mean; these $K$ class
means centered at the global-mean have the same length and form the maximally
possible equal-sized angles between any pair; moreover, the last-layer
classifiers become dual to the class means in the sense that they are equal to
each other for each class up to a scaling factor.

While it seems hopeless to rigorously prove neural collapse for multiple-layer
neural networks (1) at the moment, alternatively, we seek to show that this
phenomenon emerges in the surrogate model (2). More precisely, when the size
of each class $n_{k}=n$ for all $k$, is it true that any global minimizer
$\mathbf{W}_{L}^{\star}=\left[\mathbf{w}_{1}^{\star},\ldots,\mathbf{w}_{K}^{\star}\right]^{\top},\bm{H}^{\star}=[\mathbf{h}_{k,i}^{\star}:1\leq
k\leq K,1\leq i\leq n]$ of Program (2) exhibits neural collapse (see its
formal definition in Section 1.2 and Theorem 1)? The following result answers
this question in the affirmative:

######  Finding 1.

Neural collapses occurs in the Layer-Peeled Model.

A formal statement of this result and a detailed discussion are given in
Section 3.

This result applies to a family of loss functions $\mathcal{L}$, particularly
including the cross-entropy loss and the contrastive loss (see, e.g.,
[CKNH20]). As an immediate implication, this result provides evidence of the
Layer-Peeled Model’s ability to characterize well-trained deep learning
models.

Figure 2:  Minority Collapse predicted by the Layer-Peeled Model (LPM, in
dotted lines) and empirically observed in deep learning (DL, in solid lines)
on imbalanced datasets with $K_{A}=7$ and $K_{B}=3$. The $y$-axis denotes the
average cosine of the angles between any pair of the minority classifier
$\mathbf{w}_{K_{A}+1}^{\star},\ldots,\mathbf{w}_{K}^{\star}$ for both LPM and
DL. The datasets we use are subsets of the CIFAR10 datasets [Kri09] and the
size of the majority classes is fixed to $5000$. The experiments use VGG13
[SZ14] as the deep learning architecture, with weight decay (wd)
$\lambda=5\times 10^{-3},5\times 10^{-4}$. The prediction is especially
accurate in capturing the phase transition point where the cosine becomes $1$
or, equivalently, the minority classifiers become identical to each other.
More details can be found in Section 4.3.

##### Imbalanced Data.

While a surrogate model would be satisfactory if it explains already observed
phenomena, we set a high standard for the model, asking whether it can predict
a new common empirical pattern. Encouragingly, the Layer-Peeled Model happens
to meet this standard. Specifically, we consider training deep learning models
on imbalanced datasets, where some classes contain many more training examples
than others. Despite the pervasiveness of imbalanced classification in many
practical applications [JK19], the literature remains scarce on its impact on
the trained neural networks from a theoretical standpoint. Here we provide
mathematical insights into this problem by using the Layer-Peeled Model. In
the following result, we consider optimal solutions to the Layer-Peeled Model
on a dataset with two different class sizes: the first $K_{A}$ majority
classes each contain $n_{A}$ training examples
($n_{1}=n_{2}=\dots=n_{K_{A}}=n_{A}$), and the remaining $K_{B}:=K-K_{A}$
minority classes each contain $n_{B}$ examples
($n_{K_{A}+1}=n_{K_{A}+2}=\dots=n_{K}=n_{B}$). We call $R:=n_{A}/n_{B}>1$ the
imbalance ratio.

######  Finding 2.

In the Layer-Peeled Model, the last-layer classifiers corresponding to the
minority classes, namely
$\mathbf{w}^{\star}_{K_{A}+1},\mathbf{w}^{\star}_{K_{A}+2},\ldots,\mathbf{w}^{\star}_{K}$,
collapse to a single vector when $R$ is sufficiently large.

This result is elaborated on in Section 4. The derivation involves some novel
elements to tackle the nonconvexity of the Layer-Peeled Model (2) and the
asymmetry due to the imbalance in class sizes.

In slightly more detail, we identify a phase transition as the imbalance ratio
$R$ increases: when $R$ is below a threshold, the minority classes are
distinguishable in terms of their classifiers; when $R$ is above the
threshold, they become indistinguishable. While this phenomenon is merely
predicted by the simple Layer-Peeled Model (2), it appears in our
computational experiments on deep neural networks. More surprisingly, our
prediction of the phase transition point is in excellent agreement with the
experiments, as shown in Figure 2.

This phenomenon, which we refer to as Minority Collapse, reveals the
fundamental difficulty in using deep learning for classification when the
dataset is widely imbalanced, even in terms of optimization, not to mention
generalization. This is not a priori evident given that neural networks have a
large approximation capacity (see, e.g., [Yar17]). Importantly, Minority
Collapse emerges at a finite value of the imbalance ratio rather than at
infinity. Moreover, even below the phase transition point of this ratio, we
find that the angles between any pair of the minority classifiers are already
smaller than those of the majority classes, both theoretically and
empirically.

###  1.2 Related Work

There is a venerable line of work attempting to gain insights into deep
learning from a theoretical point of view [JGH18, DLL+19, AZLS19, ZCZG18,
COB19, EMW19, BFT17, HS20, PBL20, MMN18, SS19, RVE18, FLYZ20, KWL+19, SSJ20].
See also the reviews [FDZ21, HT20, FMZ19, Sun19] and references therein.

The work of neural collapse by [PHD20] in this body of work is particularly
noticeable with its mathematically elegant and convincing insights. In brief,
[PHD20] observed the following four properties of the last-layer features and
classifiers in deep learning training:555See the mathematical description of
neural collapse in Theorem 1.

  * (NC1) Variability collapse: the within-class variation of the last-layer features becomes $0$, which means that these features collapse to their class means.

  * (NC2) The class means centered at their global mean collapse to the vertices of a simplex equiangular tight frame (ETF) up to scaling.

  * (NC3) Up to scaling, the last-layer classifiers each collapse to the corresponding class means.

  * (NC4) The classifier’s decision collapses to simply choosing the class with the closest Euclidean distance between its class mean and the activations of the test example.

Now we give the formal definition of ETF [SH03, PHD20].

######  Definition 1.

A $K$-simplex ETF is a collection of points in $\mathbb{R}^{p}$ specified by
the columns of the matrix

${\mathbf{M}^{\star}}=\sqrt{\frac{K}{K-1}}\mathbf{P}\left(\mathbf{I}_{K}-\frac{1}{K}\mathbf{1}_{K}\mathbf{1}_{K}^{\top}\right),$

where $\mathbf{I}_{K}\in\mathbb{R}^{K\times K}$ is the identity matrix,
$\mathbf{1}_{K}$ is the ones vector, and $\mathbf{P}\in\mathbb{R}^{p\times K}$
($p\geq K$)666To be complete, we only require $p\geq K-1$. When $p=K-1$, we
can choose $\mathbf{P}$ such that
$\left[\mathbf{P}^{\top},\mathbf{1}_{K}\right]$ is an orthogonal matrix.  is a
partial orthogonal matrix such that
$\mathbf{P}^{\top}\mathbf{P}=\mathbf{I}_{K}$.

These four properties emerge in massive experiments on popular network
architectures during the terminal phase of training—when the trained model
interpolates the in-sample training data—and a shared setting of these
experiments is the use of balanced datasets and the cross-entropy loss with
$\ell_{2}$ regularization. Using convincing arguments and numerical evidence,
[PHD20] demonstrated that the symmetry and stability of neural collapse
improve deep learning training in terms of generalization, robustness, and
interpretability. Notably, these improvements occur with the benign
overfitting phenomenon in deep neural networks [MBB18, BHMM19, LR20, BLLT20,
LSS20]. As an aside, while we were preparing the manuscript, we became aware
of [MPP20, EW20, LS20], which produced neural collapse using different models.

##  2 Derivation

In this section, we intuitively derive the Layer-Peeled Model as an analytical
surrogate for well-trained neural networks. Although our derivation lacks
rigor, the priority is to reduce the complexity of the optimization problem
(1) while roughly maintaining its structure. Notably, the penalty
$\frac{\lambda}{2}\|\bm{W}_{\textnormal{full}}\|^{2}$ corresponds to weight
decay used in training deep learning models, which is necessary for preventing
this optimization program from attaining its minimum at infinity when
$\mathcal{L}$ is the cross-entropy loss.

Taking a top-down standpoint, our modeling strategy starts by singling out the
weights $\mathbf{W}_{L}$ of the topmost layer and rewriting (1) as

$\min_{\mathbf{W}_{L},\bm{H}}~{}\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\mathbf{W}_{L}\mathbf{h}(\mathbf{x}_{k,i};\mathbf{W}_{-L}),\mathbf{y}_{k})+\frac{\lambda}{2}\|\mathbf{W}_{L}\|^{2}+\frac{\lambda}{2}\|\mathbf{W}_{-L}\|^{2},$
(3)

where $\mathbf{W}_{-L}$ denotes the weights from all layers except for the
last layer (for simplicity, we do not assume any bias terms). From the
Lagrangian dual viewpoint, a minimum of the optimization program above is also
an optimal solution to

$\displaystyle\min_{\mathbf{W}_{L},\mathbf{W}_{-L}}$
$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\mathbf{W}_{L}\mathbf{h}(\mathbf{x}_{k,i};\mathbf{W}_{-L}),\mathbf{y}_{k})$
(4) $\displaystyle\mathrm{s.t.}$ $\displaystyle\|\mathbf{W}_{L}\|^{2}\leq
C_{1},$ $\displaystyle\|\mathbf{W}_{-L}\|^{2}\leq C_{2},$

for some positive numbers $C_{1}$ and $C_{2}$.777Denoting by
$(\mathbf{W}_{L}^{\star},\mathbf{W}_{-L}^{\star})$ an optimal solution to (3),
then we can take $C_{1}=\|\mathbf{W}_{L}^{\star}\|^{2}$ and
$C_{2}=\|\mathbf{W}_{-L}^{\star}\|^{2}$. To clear up any confusion, note that
due to its nonconvexity, (3) may admit multiple global minima and each in
general correspond to different values of $C_{1},C_{2}$. Next, we can
equivalently write (4) as

$\displaystyle\min_{\mathbf{W}_{L},\bm{H}}$
$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\mathbf{W}_{L}\mathbf{h}_{k,i},\mathbf{y}_{k})$
(5) $\displaystyle\mathrm{s.t.}$ $\displaystyle\|\mathbf{W}_{L}\|^{2}\leq
C_{1},$
$\displaystyle\bm{H}\in\left\\{\bm{H}(\mathbf{W}_{-L}):\|\mathbf{W}_{-L}\|^{2}\leq
C_{2}\right\\},$

where $\bm{H}=[\mathbf{h}_{k,i}:1\leq k\leq K,1\leq i\leq n_{k}]$ denotes the
decision variable and the function $\bm{H}(\mathbf{W}_{-L})$ is defined as
$\bm{H}(\mathbf{W}_{-L}):=\left[\mathbf{h}(\mathbf{x}_{k,i};\mathbf{W}_{-L}):1\leq
k\leq K,1\leq i\leq n_{k}\right]$ for any $\mathbf{W}_{-L}$.

To simplify (5), we make the ansatz that the range of
$\mathbf{h}(\mathbf{x}_{k,i};\mathbf{W}_{-L})$ under the constraint
$\|\mathbf{W}_{-L}\|^{2}\leq C_{2}$ is approximately an ellipse in the sense
that

$\left\\{\bm{H}(\mathbf{W}_{-L}):\|\mathbf{W}_{-L}\|^{2}\leq
C_{2}\right\\}\approx\left\\{\bm{H}:\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\|\mathbf{h}_{k,i}\|^{2}\leq
C_{2}^{\prime}\right\\}$ (6)

for some $C_{2}^{\prime}>0$. Loosely speaking, this ansatz asserts that
$\bm{H}$ should be regarded as a variable in an $\ell_{2}$ space. To shed
light on this point, note that $\mathbf{h}_{k,i}$ intuitively lives in the
dual space of $\mathbf{W}$ in view of the appearance of the product
$\mathbf{W}\mathbf{h}_{k,i}$ in the objective. Furthermore, $\mathbf{W}$ is in
an $\ell_{2}$ space for the $\ell_{2}$ constraint on it. Hence, the rationale
behind the ansatz follows from the self-duality of $\ell_{2}$ spaces.

Inserting this approximation into (5), we obtain the following optimization
program, which we call the Layer-Peeled Model:

$\displaystyle\min_{\mathbf{W},\mathbf{H}}$
$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
(7) $\displaystyle\mathrm{s.t.}$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}\leq
E_{W},$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}\right\|^{2}\leq
E_{H},$

where, for simplicity, we henceforth write
$\mathbf{W}:=\mathbf{W}_{L}\equiv[\mathbf{w}_{1},\ldots,\mathbf{w}_{K}]^{\top}$
for the last-layer classifiers/weights and the thresholds $E_{W}=C_{1}/K$ and
$E_{H}=C_{2}^{\prime}/K$.

This optimization program is nonconvex but, as we will show soon, is generally
mathematically tractable for analysis. On the surface, the Layer-Peeled Model
has no dependence on the data $\\{\mathbf{x}_{k,i}\\}$, which however is not
the correct picture since the dependence has been implicitly incorporated into
the threshold $E_{H}$.

In passing, we remark that neural collapse does not emerge if the second
constraint of (7) uses the $\ell_{q}$ norm for any $q\neq 2$ and $q>1$, in
place of the $\ell_{2}$ norm. This fact in turn justifies in part the ansatz
(6). This result is formally stated in Proposition 2 in Section 6.

##  3 Layer-Peeled Model for Explaining Neural Collapse

In this section, we consider training deep neural networks on a balanced
dataset, meaning $n_{k}=n$ for all classes $1\leq k\leq K$, and our main
finding is that the Layer-Peeled Model displays the neural collapse
phenomenon, just as in deep learning training [PHD20]. The proofs are all
deferred to Appendix A.1. Throughout this section, we assume $p\geq K-1$
unless otherwise specified. This condition is satisfied by many popular
architectures, where $p$ is usually tens or hundreds of times of $K$.

###  3.1 Cross-Entropy Loss

The cross-entropy loss is perhaps the most popular loss used in training deep
learning models for classification tasks. This loss function takes the form

$\mathcal{L}(\mathbf{z},\mathbf{y}_{k})=-\log\left(\frac{\exp(\mathbf{z}(k))}{\sum_{{k^{\prime}}=1}^{K}\exp(\mathbf{z}({k^{\prime}}))}\right),$

where $\mathbf{z}(k^{\prime})$ denotes the $k^{\prime}$-th entry of
$\mathbf{z}$. Recall that $\mathbf{y}_{k}$ is the label of the $k$-th class
and the feature $\mathbf{z}$ is set to $\mathbf{W}\mathbf{h}_{k,i}$ in the
Layer-Peeled Model (7). In contrast to the complex deep neural networks, which
are often considered a black-box, the Layer-Peeled Model is much more amenable
to analysis. As an exemplary use case, the following result shows that any
minimizer of the Layer-Peeled Model (7) with the cross-entropy loss admits an
almost closed-form expression.

######  Theorem 1.

In the balanced case, any global minimizer
$\mathbf{W}^{\star}\equiv\left[\mathbf{w}_{1}^{\star},\ldots,\mathbf{w}_{K}^{\star}\right]^{\top},\bm{H}^{\star}\equiv[\mathbf{h}_{k,i}^{\star}:1\leq
k\leq K,1\leq i\leq n]$ of (7) with the cross-entropy loss obeys

$\bm{h}_{k,i}^{\star}=C\mathbf{w}_{k}^{\star}=C^{\prime}\mathbf{m}_{k}^{\star}$
(8)

for all $1\leq i\leq n,1\leq k\leq K$, where the constants
$C=\sqrt{E_{H}/E_{W}},C^{\prime}=\sqrt{E_{H}}$, and the matrix
$[\mathbf{m}_{1}^{\star},\ldots,\mathbf{m}_{K}^{\star}]$ forms a $K$-simplex
ETF specified in Definition 1.

######  Remark 2.

Note that the minimizers $(\mathbf{W}^{\star},\bm{H}^{\star})$’s are
equivalent to each other up to rotation because of the rational invariance of
simplex ETFs (see the rotation $\mathbf{P}$ in Definition 1).

This theorem demonstrates the highly symmetric geometry of the last-layer
features and weights of the Layer-Peeled Model, which is precisely the
phenomenon of neural collapse. Explicitly, (8) says that all within-class
(last-layer) features are the same:
$\mathbf{h}_{k,i}^{\star}=\mathbf{h}_{k,i^{\prime}}^{\star}$ for all $1\leq
i,i^{\prime}\leq n$; next, the $K$ class-mean features
$\mathbf{h}_{k}^{\star}:=\mathbf{h}_{k,i}^{\star}$ together exhibit a
$K$-simplex ETF up to scaling, from which we immediately conclude that

$\cos\measuredangle(\mathbf{h}_{k}^{\star},\mathbf{h}_{{k^{\prime}}}^{\star})=-\frac{1}{K-1}$
(9)

for any $k\neq k^{\prime}$ by Definition 1;888Note that the cosine value
$-\frac{1}{K-1}$ corresponds to the largest possible angle for any $K$ points
that have an equal $\ell_{2}$ norm and equal-sized angles between any pair. As
pointed out in [PHD20], the largest angle implies a large-margin solution
[SHN+18]. in addition, (8) also displays the precise duality between the last-
layer classifiers and features. Taken together, these facts indicate that the
minimizer $\left(\mathbf{W}^{\star},\bm{H}^{\star}\right)$ satisfies exactly
(NC1)–(NC3). Last, Property (NC4) is also satisfied by recognizing that, for
any given last-layer features $\mathbf{h}$, the predicted class is
$\operatorname*{arg\,max}_{k}\mathbf{w}_{k}^{\star}\mathop{\mathchoice{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\normalsize$\cdot$}}}{\vbox{\hbox{\small$\cdot$}}}}\mathbf{h}$,
where
$\bm{a}\mathop{\mathchoice{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\normalsize$\cdot$}}}{\vbox{\hbox{\small$\cdot$}}}}\bm{b}$
denotes the inner product of the two vectors. Note that the predicted which
satisfies

$\operatorname*{arg\,max}_{k}\mathbf{w}_{k}^{\star}\mathop{\mathchoice{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\normalsize$\cdot$}}}{\vbox{\hbox{\small$\cdot$}}}}\mathbf{h}=\operatorname*{arg\,max}_{k}\mathbf{h}_{k}^{\star}\mathop{\mathchoice{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\normalsize$\cdot$}}}{\vbox{\hbox{\small$\cdot$}}}}\mathbf{h}=\operatorname*{arg\,min}_{k}\|\mathbf{h}_{k}^{\star}-\mathbf{h}\|^{2}.$

Conversely, the presence of neural collapse in the Layer-Peeled Model offers
evidence of the effectiveness of our model as a tool for analyzing neural
networks. To be complete, we remark that other models were very recently
proposed to justify the neural collapse phenomenon [MPP20, EW20, LS20] (see
also [PL20]). For example, [EW20, LS20] considered models that impose a norm
constraint for each individual class, rather than an overall constraint as
employed in the Layer-Peeled Model.

###  3.2 Extensions to Other Loss Functions

In the modern practice of deep learning, various loss functions are employed
to take into account the problem characteristics. Here we show that the Layer-
Peeled Model continues to exhibit the phenomenon of neural collapse for some
popular loss functions.

##### Contrastive Loss.

Contrastive losses have been extensively used recently in both supervised and
unsupervised deep learning [PSM14, AKK+19, CKNH20, BZMA20]. These losses pull
similar training examples together in their embedding space while pushing
apart dissimilar examples. Here we consider the supervised contrastive loss
[KTW+20], which (in the balanced) case is defined through the last-layer
features as

$\mathcal{L}_{c}(\mathbf{h}_{k,i},\mathbf{y}_{k})=\frac{1}{n}\sum_{j=1}^{n}-\log\left(\frac{\exp(\bm{h}_{k,i}\mathop{\mathchoice{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\normalsize$\cdot$}}}{\vbox{\hbox{\small$\cdot$}}}}\bm{h}_{k,j}/\tau)}{\sum_{{k^{\prime}}=1}^{K}\sum_{\ell=1}^{n}\exp(\bm{h}_{k,i}\mathop{\mathchoice{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\LARGE$\cdot$}}}{\vbox{\hbox{\normalsize$\cdot$}}}{\vbox{\hbox{\small$\cdot$}}}}\bm{h}_{{k^{\prime}},\ell}/\tau)}\right),$
(10)

where $\tau>0$ is a parameter. As the loss does not involve the last-layer
classifiers explicitly, the Layer-Peeled Model in the case of the supervised
contrastive loss takes the form999In (10),
$\mathbf{h}_{k,i}\equiv\mathbf{h}(\mathbf{x}_{k,i},\mathbf{W}_{-L})$ depends
on the data, whereas in (11) $\mathbf{h}_{k,i}$’s form the decision variable
$\bm{H}$.

$\displaystyle\min_{\mathbf{H}}$
$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\mathcal{L}_{c}(\mathbf{h}_{k,i},\mathbf{y}_{k})$
(11) $\displaystyle\mathrm{s.t.}$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}\leq
E_{H}.$

We show that this Layer-Peeled Model also exhibits neural collapse in its
last-layer features, even though the label information is not explicitly
explored in the loss.

######  Theorem 3.

Any global minimizer of (11) satisfies

$\mathbf{h}_{k,i}^{\star}=\sqrt{E_{H}}\mathbf{m}_{k}^{\star}$ (12)

for all $1\leq k\leq K$ and $1\leq i\leq n$, where
$[\mathbf{m}_{1}^{\star},\ldots,\mathbf{m}_{K}^{\star}]$ forms a $K$-simplex
ETF.

Theorem 3 shows that the contrastive loss in the associated Layer-Peeled Model
does a perfect job in pulling together training examples from the same class.
Moreover, as seen from the denominator in (10), minimizing this loss would
intuitively render the between-class inner products of last-layer features as
small as possible, thereby pushing the features to form the vertices of a
$K$-simplex ETF up to scaling.

##### Softmax-Based Loss.

The cross-entropy loss can be thought of as a softmax-based loss. To see this,
define the softmax transform as

$\mathbf{S}(\mathbf{z})=\left[\frac{\exp(\mathbf{z}(1))}{\sum_{k=1}^{K}\exp(\mathbf{z}(k))},\ldots,\frac{\exp(\mathbf{z}(K))}{\sum_{k=1}^{K}\exp(\mathbf{z}(k))}\right]^{\top}$

for $\mathbf{z}\in\mathbb{R}^{K}$. Let $g_{1}$ be any nonincreasing convex
function and $g_{2}$ be any nondecreasing function, both defined on $(0,1)$.
We consider a softmax-based loss function that takes the form

$\mathcal{L}(\mathbf{z},\mathbf{y}_{k})=g_{1}\left(\mathbf{S}(\mathbf{z})(k)\right)+\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}g_{2}\left(\mathbf{S}(\mathbf{z})({k^{\prime}})\right).$ (13)

Here, $\mathbf{S}(\mathbf{z})(k)$ denotes the $k$-th element of
$\mathbf{S}(\mathbf{z})$. Taking $g_{1}(x)=-\log x$ and $g_{2}\equiv 0$, we
recover the cross-entropy loss. Another example is to take
$g_{1}(x)=(1-x)^{q}$ and $g_{2}(x)=x^{q}$ for $q>1$, which can be implemented
in most deep learning libraries such as PyTorch [PGM+19].

We have the following theorem regarding the softmax-based loss functions in
the balanced case.

######  Theorem 4.

Assume
$\sqrt{E_{H}E_{W}}>\frac{K-1}{K}\log\left(K^{2}\sqrt{E_{H}E_{W}}+(2K-1)(K-1)\right)$.
For any loss function defined in (13), $(\mathbf{W}^{\star},\bm{H}^{\star})$
given by (8) is a global minimizer of Program (7). Moreover, if $g_{2}$ is
strictly convex and at least one of $g_{1},g_{2}$ is strictly monotone, then
any global minimizer must be given by (8).

In other words, neural collapse continues to emerge with softmax-based losses
under mild regularity conditions. The first part of this theorem does not
preclude the possibility that the Layer-Peeled Model admits solutions other
than (8). When applied to the cross-entropy loss, it is worth pointing out
that this theorem is a weak version of Theorem 1, albeit more general.
Regarding the first assumption in Theorem 4, note that $E_{H}$ and $E_{W}$
would be arbitrarily large if the weight decay $\lambda$ in (1) is
sufficiently small, thereby meeting the assumption concerning
$\sqrt{E_{H}E_{W}}$ in this theorem.

We remark that Theorem 4 does not require the convexity of the loss
$\mathcal{L}$. To circumvent the hurdle of nonconvexity, our proof in Appendix
A.1 presents several novel elements.

In passing, we leave the experimental confirmation of neural collapse with
these loss functions for future work.

##  4 Layer-Peeled Model for Predicting Minority Collapse

Deep learning models are often trained on datasets where there is a
disproportionate ratio of observations in each class [WLW+16, HLLT16, MR17].
For example, in the Places2 challenge dataset [ZKL+16], the number of images
in its majority scene categories is about eight times that in its minority
classes. Another example is the Ontonotes dataset for part-of-speech tagging
[HMP+06], where the number of words in its majority classes can be more than
one hundred times that in its minority classes. While empirically the
imbalance in class sizes often leads to inferior model performance of deep
learning (see, e.g., [JK19]), there remains a lack of a solid theoretical
footing for understanding its effect, perhaps due to the complex details of
deep learning training.

In this section, we use the Layer-Peeled Model to seek a fine-grained
characterization of how class imbalance impacts neural networks that are
trained for a sufficiently long time. In short, our analysis predicts a
phenomenon we term Minority Collapse, which fundamentally limits the
performance of deep learning especially on the minority classes, both
theoretically and empirically. All omitted proofs are relegated to Appendix
A.2.

###  4.1 Technique: Convex Relaxation

When it comes to imbalanced datasets, the Layer-Peeled Model no longer admits
a simple expression for its minimizers as in the balanced case, due to the
lack of symmetry between classes. This fact results in, among others, an added
burden on numerically computing the solutions of the Layer-Peeled Model.

To overcome this difficulty, we introduce a convex optimization program as a
relaxation of the nonconvex Layer-Peeled Model (7), relying on the well-known
result for relaxing a quadratically constrained quadratic program as a
semidefinite program (see, e.g., [SZ03]). To begin with, defining
$\mathbf{h}_{k}$ as the feature mean of the $k$-th class (i.e.,
$\mathbf{h}_{k}:=\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\mathbf{h}_{k,i}$), we
introduce a new decision variable
$\mathbf{X}:=\left[\bm{h}_{1},\bm{h}_{2},\dots,\bm{h}_{K},\mathbf{W}^{\top}\right]^{\top}\left[\bm{h}_{1},\bm{h}_{2},\dots,\bm{h}_{K},\mathbf{W}^{\top}\right]\in\mathbb{R}^{2K\times
2K}$. By definition, $\mathbf{X}$ is positive semidefinite and satisfies

$\frac{1}{K}\sum_{k=1}^{K}\mathbf{X}(k,k)\\\
=\frac{1}{K}\sum_{k=1}^{K}\|\mathbf{h}_{k}\|^{2}\overset{a}{\leq}\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}\right\|^{2}\\\
\leq E_{H}$

and

$\frac{1}{K}\sum_{k=K+1}^{2K}\mathbf{X}(k,k)=\frac{1}{K}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2}\leq
E_{W},$

where $\overset{a}{\leq}$ follows from the Cauchy–Schwarz inequality. Thus, we
consider the following semidefinite programming problem:101010Although Program
(14) involves a semidefinite constraint, it is not a semidefinite program in
the strict sense because a semidefinite program uses a linear objective
function.

$\displaystyle\min_{\mathbf{X}\in\mathbb{R}^{2K\times 2K}}$
$\displaystyle\sum_{k=1}^{K}\frac{n_{k}}{N}\mathcal{L}(\mathbf{z}_{k},\mathbf{y}_{k})$
(14) $\displaystyle\mathrm{s.t.}$
$\displaystyle\mathbf{z}_{k}=\left[\mathbf{X}(k,K+1),\mathbf{X}(k,K+2),\dots,\mathbf{X}(k,2K)~{}\right]^{\top},~{}\text{
for all }1\leq k\leq K,$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbf{X}(k,k)\leq
E_{H},\quad\frac{1}{K}\sum_{k=K+1}^{2K}\mathbf{X}(k,k)\leq E_{W},$
$\displaystyle\mathbf{X}\succeq 0.$

Lemma 1 below relates the solutions of (14) to that of (7).

######  Lemma 1.

Assume $p\geq 2K$ and the loss function $\mathcal{L}$ is convex in its first
argument. Let $\mathbf{X}^{\star}$ be a minimizer of the convex program (14).
Define $\left(\mathbf{H}^{\star},\mathbf{W}^{\star}\right)$ as

$\displaystyle\left[\bm{h}_{1}^{\star},\bm{h}_{2}^{\star},\dots,\bm{h}_{K}^{\star},~{}(\mathbf{W}^{\star})^{\top}\right]=\mathbf{P}(\mathbf{X}^{\star})^{1/2},$
(15) $\displaystyle\bm{h}_{k,i}^{\star}=\bm{h}_{k}^{\star},~{}\text{ for all
}1\leq i\leq n,1\leq k\leq K,$

where $(\mathbf{X}^{\star})^{1/2}$ denotes the positive square root of
$\mathbf{X}^{\star}$ and $\mathbf{P}\in\mathbb{R}^{p\times 2K}$ is any partial
orthogonal matrix such that $\mathbf{P}^{\top}\mathbf{P}=\mathbf{I}_{2K}$.
Then $(\mathbf{H}^{\star},\mathbf{W}^{\star})$ is a minimizer of (7).
Moreover, if all $\mathbf{X}^{\star}$’s satisfy
$\frac{1}{K}\sum_{k=1}^{K}\mathbf{X}^{\star}(k,k)=E_{H}$, then all the
solutions of (7) are in the form of (15).

This lemma in effect says that the relaxation does not lead to any loss of
information when we study the Layer-Peeled Model through a convex program,
thereby offering a computationally efficient tool for gaining insights into
the terminal phase of training deep neural networks on imbalanced datasets. An
appealing feature is that the size of the program (14) is independent of the
number of training examples. Besides, this lemma predicts that even in the
imbalanced case the last-layer features collapse to their class means under
mild conditions. Therefore, Property (NC1) is satisfied (see more discussion
about the condition in Section B).

The assumption of the convexity of $\mathcal{L}$ in the first argument is
satisfied by a large class of loss functions, such as the cross-entropy loss.
We also remark that (14) is not the unique convex relaxation. An alternative
is to relax (7) via a nuclear norm-constrained convex program [BMP08, HV19]
(see more details in Section B).

###  4.2 Minority Collapse

With the technique of convex relaxation in place, now we numerically solve the
Layer-Peeled Model on imbalanced datasets, with the goal of identifying
nontrivial patterns in this regime. As a worthwhile starting point, we
consider a dataset that has $K_{A}$ majority classes each containing $n_{A}$
training examples and $K_{B}$ minority classes each containing $n_{B}$
training examples. That is, assume $n_{1}=n_{2}=\dots=n_{K_{A}}=n_{A}$ and
$n_{K_{A}+1}=n_{K_{A}+2}=\dots=n_{K}=n_{B}$. For convenience, call
$R:=n_{A}/n_{B}>1$ the imbalance ratio. Note that the case $R=1$ reduces to
the balanced setting.

(a) $E_{W}=1$, $E_{H}=5$

(b) $E_{W}=1$, $E_{H}=10$

Figure 3:  The average cosine of the angles between any pair of the minority
classifier solved from the Layer-Peeled Model. The average cosine reaches $1$
once $R$ is above some threshold. The total number of classes $K_{A}+K_{B}$ is
fixed to $10$. The gray dash-dotted line indicates the value of
$-\frac{1}{K-1}$, which is given by (9). The between-majority-class angles can
be large even when Minority Collapse emerges. For example, in the case
$K_{A}=5$ in Plot (a), the average between-majority-class cosine is $-0.17$,
which corresponds to $100$°, when Minority Collapse first occurs. Notably, our
simulation suggests that the minority classifiers exhibit an equiangular frame
and so do the majority classifiers.

An important question is to understand how the $K_{B}$ last-layer minority
classifiers behave as the imbalance ratio $R$ increases, as this is directly
related to the model performance on the minority classes. To address this
question, we show that the average cosine of the angles between any pair of
the $K_{B}$ minority classifiers in Figure 3 by solving the simple convex
program (14). This figure reveals a two-phase behavior of the minority
classifiers
$\mathbf{w}^{\star}_{K_{A}+1},\mathbf{w}^{\star}_{K_{A}+2},\ldots,\mathbf{w}^{\star}_{K}$
as $R$ increases:

  1. (1)

When $R<R_{0}$ for some $R_{0}>0$, the average between-minority-class angle
becomes smaller as $R$ increases.

  2. (2)

Once $R\geq R_{0}$, the average between-minority-class angle become zero,
implying that all the minority classifiers collapse to a single vector.

Above, the phase transition point $R_{0}$ depends on the imbalance
configuration $K_{A},K_{B}$ and the thresholds $E_{H},E_{W}$.

We refer to the phenomenon that appears in the second phase as Minority
Collapse. While it can be expected that the minority classifiers get closer to
each other as the level of imbalance increases, surprisingly, these
classifiers become completely indistinguishable once $R$ hits a finite value.
Once Minority Collapse takes place, the neural network would predict equal
probabilities for all the minority classes regardless of the input. As such,
its predictive ability is by no means better than a coin toss when conditioned
on the minority classes for both optimization and generalization, and this
situation would only get worse in the presence of adversarial perturbations.
This phenomenon is especially detrimental when the minority classes are more
frequent in the application domains than in the training data.

From an optimization point of view, the emergence of Minority Collapse would
prevent the model from achieving zero training error since its prediction is
simply uniform over the minority classes. While it seems to contradict
conventional wisdom on the approximation power of deep learning, a careful
examination indicates that the occurrence can be attributed to the two
constraints in the Layer-Peeled Model or the $\ell_{2}$ penalty in (1).
However, this issue does not disappear by simply setting a small penalty
coefficient $\lambda$ in deep learning because the imbalance ratio can be
arbitrarily large. Even outside the regime of Minority Collapse, the
classification might still be unreliable if the imbalance ratio is large since
the softmax predictions for the minority classes can be close to each other.

To put the observations in Figure 3 on a firm footing, we prove that Minority
Collapse indeed emerges in the Layer-Peeled Model as $R$ tends to infinity.

######  Theorem 5.

Assume $p\geq K$ and $n_{A}/n_{B}\to\infty$, and fix $K_{A}$ and $K_{B}$. Let
$\left(\mathbf{H}^{\star},\mathbf{W}^{\star}\right)$ be any global minimizer
of the Layer-Peeled Model (7) with the cross-entropy loss. As $R\equiv
n_{A}/n_{B}\to\infty$, we have

$\lim\mathbf{w}^{\star}_{k}-\mathbf{w}^{\star}_{{k^{\prime}}}=\bm{0}_{p},~{}\text{
for all }K_{A}<k<{k^{\prime}}\leq K.$

To intuitively see why Minority Collapse occurs, first note that the majority
classes become the predominant part of the risk function as the level of
imbalance increases. The minimization of the objective, therefore, pays too
much emphasis on the majority classifiers, encouraging the between-majority-
class angles to grow and meanwhile shrinking the between-minority-class angles
to zero. As an aside, an interesting question for future work is to prove that
$\mathbf{w}^{\star}_{k}$ and $\mathbf{w}^{\star}_{{k^{\prime}}}$ are exactly
equal for sufficiently large $R$.

###  4.3 Experiments

At the moment, Minority Collapse is merely a prediction of the Layer-Peeled
Model. An immediate question thus is: does this phenomenon really occur in
real-world neural networks? At first glance, it does not necessarily have to
be the case since the Layer-Peeled Model is a dramatic simplification of deep
neural networks.

To this end, we resort to computational experiments.111111Our code is publicly
available at https://github.com/HornHehhf/LPM. Explicitly, we consider
training two network architectures, VGG and ResNet [HZRS16], on the
FashionMNIST [XRV17] and CIFAR10 datasets, and in particular, replace the
dropout layers in VGG with batch normalization [IS15]. As both datasets have
10 classes, we use three combinations of $(K_{A},K_{B})=(3,7),(5,5),(7,3)$ to
split the data into majority classes and minority classes. In the case of
FashionMNIST (CIFAR10), we let the $K_{A}$ majority classes each contain all
the $n_{A}=6000$ ($n_{A}=5000$) training examples from the corresponding class
of FashionMNIST (CIFAR10), and the $K_{B}$ minority classes each have
$n_{B}=6000/R$ ($n_{B}=5000/R$) examples randomly sampled from the
corresponding class. The rest experiment setup is basically the same as
[PHD20]. In detail, we use the cross-entropy loss and stochastic gradient
descent with momentum $0.9$ and weight decay $\lambda=5\times 10^{-4}$. The
networks are trained for $350$ epochs with a batch size of $128$. The initial
learning is annealed by a factor of $10$ at $1/3$ and $2/3$ of the $350$
epochs. The only difference from [PHD20] is that we simply set the learning
rate to $0.1$ instead of sweeping over $25$ learning rates between $0.0001$
and $0.25$. This is because the test performance of our trained models is
already comparable with their best reported test accuracy.

(a) VGG11 on FashionMNIST

(b) VGG13 on CIFAR10

(c) ResNet18 on FashionMNIST

(d) ResNet18 on CIFAR10

Figure 4: The occurrence of Minority Collapse in deep neural networks. Each
curve denotes the average between-minority-class cosine. We fix
$K_{A}+K_{B}=10$. In particular, Figure 4(b) shares the same setting with
Figure 2 in Section 1, where the LPM-based predictions are given by
$(E_{W},E_{H})$ such that the two constraints in the Layer-Peeled Model become
active for the weights of the trained networks.

The results of the experiments above are displayed in Figure 4. This figure
clearly indicates that the angles between the minority classifiers collapse to
zero as soon as $R$ is large enough. Moreover, the numerical examination in
Table 1 shows that the norm of the classifier is constant across the minority
classes. Taken together, these two pieces clearly give evidence for the
emergence of Minority Collapse in these neural networks, thereby further
demonstrating the effectiveness of our Layer-Peeled Model. Besides, Figure 4
also shows that the issue of Minority Collapse is compounded when there are
more majority classes, which is consistent with Figure 3. For completeness, we
remark that, as with neural collapse, Minority Collapse only occurs during the
terminal phase of training with a non-diminishing weight decay parameter.

(a) VGG11 on FashionMNIST

(b) VGG13 on CIFAR10

(c) ResNet18 on FashionMNIST

(d) ResNet18 on CIFAR10

Figure 5: Comparison of the test accuracy on minority classes between $R=1$
and $R=1000$. We fix $K_{A}+K_{B}=10$. Note that when $R=1000$, the test
accuracy on the minority classes can be lower than $10\%$ because the trained
neural networks misclassify many examples in the minority classes as the
majority classes.

In order to get a handle on how Minority Collapse impacts the test accuracy,
we plot the results of another numerical study in Figure 5. The setting is the
same as Figure 4, except that now we randomly sample $6$ or $5$ examples per
class for the minority classes depending on whether the dataset is
FashionMNIST or CIFAR10. The results show that the performance of the trained
model deteriorates in the test data if the imbalance ratio $R=1000$, when
Minority Collapse has occurred or is about to occur. This is by no means
intuitive a priori as the test performance is only restricted to the minority
classes and a large value of $R$ only leads to more training data in the
majority classes without affecting that in the minority classes.

Dataset | FashionMNIST
---|---
Network architecture | VGG11 | ResNet18
No. of majority classes | $K_{A}=3$ | $K_{A}=5$ | $K_{A}=7$ | $K_{A}=3$ | $K_{A}=5$ | $K_{A}=7$
Norm variation | $2.7\times 10^{-5}$ | $4.4\times 10^{-8}$ | $6.0\times 10^{-8}$ | $1.4\times 10^{-5}$ | $5.0^{-8}$ | $6.3\times 10^{-8}$
Dataset | CIFAR10
Network architecture | VGG13 | ResNet18
No. of majority classes | $K_{A}=3$ | $K_{A}=5$ | $K_{A}=7$ | $K_{A}=3$ | $K_{A}=5$ | $K_{A}=7$
Norm variation | $1.4\times 10^{-4}$ | $9.0\times 10^{-7}$ | $5.2\times 10^{-8}$ | $5.4\times 10^{-5}$ | $3.5\times 10^{-7}$ | $5.4\times 10^{-8}$

Table 1: Variability of the lengths of the minority classifiers when
$R=\infty$. Each number in the row of “norm variation” is
$\mathrm{Std}(\|\mathbf{w}_{B}^{\star}\|)/\mathrm{Avg}(\|\mathbf{w}_{B}^{\star}\|)$,
where $\mathrm{Std}(\|\mathbf{w}_{B}^{\star}\|)$ denotes the standard
deviation of the lengths of the $K_{B}$ classifiers and the denominator
denotes the average. The results indicate that the classifiers of the minority
classes have almost the same length.

##  5 How to Mitigate Minority Collapse?

In this section, we further exploit the use of the Layer-Peeled Model in an
attempt to lessen the detrimental effect of Minority Collapse. Instead of
aiming to develop a full set of methodologies to overcome this issue, which is
beyond the scope of the paper, our focus is on the evaluation of some simple
techniques used for imbalanced datasets.

Among many approaches to handling class imbalance in deep learning (see the
review [JK19]), perhaps the most popular one is to oversample training
examples from the minority classes [BMM18, SXY+19, CJL+19, CWG+19]. In its
simplest form, this sampling scheme retains all majority training examples
while duplicating each training example from the minority classes for $w_{r}$
times, where the oversampling rate $w_{r}$ is a positive integer. Oversampling
in effect turns to the minimization of an adjusted optimization problem that
is derived by replacing the risk in the optimization program (1) with

$\frac{1}{n_{A}K_{A}+w_{r}n_{B}K_{B}}\left[\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\bm{f}(\mathbf{x}_{k,i};\bm{W}_{\textnormal{full}}),\mathbf{y}_{k})+w_{r}\sum_{k=K_{A}+1}^{K}\sum_{i=1}^{n_{B}}\mathcal{L}(\bm{f}(\mathbf{x}_{k,i};\bm{W}_{\textnormal{full}}),\mathbf{y}_{k})\right]$
(16)

while keeping the penalty term
$\frac{\lambda}{2}\|\bm{W}_{\textnormal{full}}\|^{2}$. Note that oversampling
is closely related to weight adjusting (see more discussion in Section B).

A close look at (16) suggests that the neural network obtained by minimizing
this new program might behave as if it were trained on a (larger) dataset with
$n_{A}$ and $w_{r}n_{B}$ examples in each majority class and minority class,
respectively. To formalize this intuition, as earlier, we start by considering
the Layer-Peeled Model in the case of oversampling:

$\displaystyle\min_{\mathbf{H},\mathbf{W}}$
$\displaystyle\frac{1}{n_{A}K_{A}+w_{r}n_{B}K_{B}}\left[\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})+w_{r}\sum_{k=K_{A}+1}^{K}\sum_{i=1}^{n_{B}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})\right]$
(17) $\displaystyle\mathrm{s.t.}$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}\leq
E_{W},$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K_{A}}\frac{1}{n_{A}}\sum_{i=1}^{n_{A}}\left\|\bm{h}_{k,i}\right\|^{2}+\frac{1}{K}\sum_{k=K_{A}+1}^{K}\frac{1}{n_{B}}\sum_{i=1}^{n_{B}}\left\|\bm{h}_{k,i}\right\|^{2}\leq
E_{H}.$

(a) VGG11 on FashionMNIST

(b) VGG13 on CIFAR10

(c) ResNet18 on FashionMNIST

(d) ResNet18 on CIFAR10

Figure 6: Effect of oversampling when the imbalance ratio is $R=1000$. Each
plot shows the average cosine of the between-minority-class angles. The
results indicate that increasing the oversampling rate would enlarge the
between-minority-class angles.

The following result confirms our intuition that oversampling indeed boosts
the size of the minority classes for the Layer-Peeled Model.

######  Proposition 1.

Assume $p\geq 2K$ and the loss function $\mathcal{L}$ is convex in the first
argument. Let $\mathbf{X}^{\star}$ be any minimizer of the convex program (14)
with $n_{1}=n_{2}=\dots=n_{K_{A}}=n_{A}$ and
$n_{K_{A}+1}=n_{K_{A}+2}=\dots=n_{K}=w_{r}n_{B}$. Define
$\left(\mathbf{H}^{\star},\mathbf{W}^{\star}\right)$ as

$\displaystyle\left[\bm{h}_{1}^{\star},\bm{h}_{2}^{\star},\dots,\bm{h}_{K}^{\star},(\mathbf{W}^{\star})^{\top}\right]=\mathbf{P}(\mathbf{X}^{\star})^{1/2},$
(18) $\displaystyle~{}~{}\bm{h}_{k,i}^{\star}=\bm{h}_{k}^{\star},~{}\text{ for
all }1\leq i\leq n_{A},1\leq k\leq K_{A},$
$\displaystyle~{}~{}\bm{h}_{k,i}^{\star}=\bm{h}_{k}^{\star},~{}\text{ for all
}1\leq i\leq n_{B},K_{A}<k\leq K,$

where $\mathbf{P}\in\mathbb{R}^{p\times 2K}$ is any partial orthogonal matrix
such that $\mathbf{P}^{\top}\mathbf{P}=\mathbf{I}_{2K}$. Then
$(\mathbf{H}^{\star},\mathbf{W}^{\star})$ is a global minimizer of the
oversampling-adjusted Layer-Peeled Model (17). Moreover, if all
$\mathbf{X}^{\star}$’s satisfy
$\frac{1}{K}\sum_{k=1}^{K}\mathbf{X}^{\star}(k,k)=E_{H}$, then all the
solutions of (17) are in the form of (18).

Together with Lemma 1, Proposition 1 shows that the number of training
examples in each minority class is now in effect $w_{r}n_{B}$, instead of
$n_{B}$.

We turn to Figure 6 for an illustration of the effects of oversampling on
real-world deep learning models, using the same experimental setup as in
Figure 5. From Figure 6, we see that the angles between pairs of the minority
classifiers become larger as the oversampling rate $w_{r}$ increases.
Consequently, the issue of Minority Collapse becomes less detrimental in terms
of training accuracy as $w_{r}$ increases. This again corroborates the
predictive ability of the Layer-Peeled Model.

Network architecture | VGG11 | ResNet18
---|---|---
No. of majority classes | $K_{A}=3$ | $K_{A}=5$ | $K_{A}=7$ | $K_{A}=3$ | $K_{A}=5$ | $K_{A}=7$
Original (minority) | 15.29 | 20.30 | 17.00 | 30.66 | 34.26 | 5.53
Oversampling (minority) | 41.13 | 57.22 | 30.50 | 37.86 | 53.46 | 8.13
Improvement (minority) | 25.84 | 36.92 | 13.50 | 7.20 | 19.20 | 2.60
Original (overall) | 40.10 | 57.61 | 69.09 | 50.88 | 64.89 | 66.13
Oversampling (overall) | 58.25 | 76.17 | 73.37 | 55.91 | 74.56 | 67.10
Improvement (overall) | 18.15 | 18.56 | 4.28 | 5.03 | 9.67 | 0.97

Table 2:  Test accuracy (%) on FashionMNIST when $R=1000$. “Original
(minority)” means that the test accuracy is evaluated only on the minority
classes and oversampling is not used. When oversampling is used, we report the
best test accuracy among four oversampling rates: $1$, $10$, $100$, and
$1000$. The best test accuracy is never achieved at $w_{r}=1000$, indicating
that oversampling with a large $w_{r}$ would impair the test performance.

Next, we refer to Table 2 for effect on the test performance. The results
clearly demonstrate the improvement in test accuracy brought by oversampling
for certain choices of the oversampling rates. The improvement is noticeable
on both the minority classes and all classes.

A closer look at the results of Table 2, however, reveals that issues remain
when addressing Minority Collapse by oversampling. Perhaps the most critical
one is that although oversampling with a very large value of $w_{r}$ can
mitigate Minority Collapse on the training set, it is at the cost of degrading
test accuracy. More specifically, how can we efficiently select an
oversampling rate for optimal test performance? More broadly, Minority
Collapse does not seem likely to be fully resolved by sampling-based
approaches alone, and the doors are widely open for future investigation.

##  6 Discussion

In this paper, we have developed the Layer-Peeled Model as a simple yet
effective modeling strategy toward understanding well-trained deep neural
networks. The derivation of this model follows a top-down strategy by
isolating the last layer from the remaining layers. Owing to the analytical
and numerical tractability of the Layer-Peeled Model, we provide some
explanation of a recently observed phenomenon called neural collapse in deep
neural networks trained on balanced datasets [PHD20]. Moving to imbalanced
datasets, an analysis of this model suggests that the last-layer classifiers
corresponding to the minority classes would collapse to a single point once
the imbalance level is above a certain threshold. This new phenomenon, which
we refer to as Minority Collapse, occurs consistently in our computational
experiments.

The efficacy of the Layer-Peeled Model in analyzing well-trained deep learning
models implies that the ansatz (6)—a crucial step in the derivation of this
model—is at least a useful approximation. Moreover, this ansatz can be further
justified by the following result in an indirect manner, which, together with
Theorem 1, shows that the $\ell_{2}$ norm suggested by the ansatz happens to
be the only choice among all the $\ell_{q}$ norms that is consistent with
empirical observations. Its proof is given in Appendix A.1.

######  Proposition 2.

Assume $p\geq K$. For any $q\in(1,2)\cup(2,\infty)$, consider the optimization
problem

$\displaystyle\min_{\mathbf{W},\bm{H}}$
$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
$\displaystyle\mathrm{s.t.}$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}\leq
E_{W},$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{q}_{q}\leq
E_{H},$

where $\mathcal{L}$ is the cross-entropy loss. Then, any global minimizer of
this program does not satisfy (8) for any positive numbers $C$ and
$C^{\prime}$. That is, neural collapse does not emerge in this model.

While the paper has demonstrated its noticeable effectiveness, the Layer-
Peeled Model requires future investigation for consolidation and extension.
First, an important question is to better justify the ansatz (6) used in the
development of this model, or equivalently, the second constraint of (7). For
example, is the permutation invariance of the weights within the same layer
useful for the justification? Moreover, an analysis of the gap between the
Layer-Peeled Model and well-trained deep learning models would be a welcome
advance. For example, how does the gap depend on the neural network
architectures? From a different angle, a possible extension is to retain
multiple layers following the top-down viewpoint. Explicitly, letting $1\leq
m<L$ be the number of the top layers we wish to retain in the model, we can
represent the prediction of the neural network as
$\bm{f}(\mathbf{x},\bm{W}_{\textnormal{full}})=\bm{f}(\mathbf{h}(\mathbf{x};\mathbf{W}_{1:(L-m)}),\mathbf{W}_{(L-m+1):L})$
by denoting by $\mathbf{W}_{1:(L-m)}$ and $\mathbf{W}_{(L-m+1):L}$ the first
$L-m$ layers and the last $m$ layers, respectively. Consider the $m$-Layer-
Peeled Model:

$\displaystyle\min_{\mathbf{W},\mathbf{H}}$
$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\bm{f}(\mathbf{h}_{k,i},\mathbf{W}_{(L-m+1):L}),\mathbf{y}_{k})$
$\displaystyle\mathrm{s.t.}$
$\displaystyle\frac{1}{K}\|\mathbf{W}_{(L-m+1):L})\|^{2}\leq E_{W},$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}\right\|^{2}\leq
E_{H}.$

The two constraints might be modified to take into account the network
architectures. An immediate question is whether this model with $m=2$ is
capable of capturing new patterns of deep learning training.

From a practical standpoint, the Layer-Peeled Model together with its convex
relaxation (14) offers an analytical and computationally efficient technique
to identify and mitigate bias induced by class imbalance when training deep
learning models. First, an interesting question is to extend Minority Collapse
from the case of two-valued class sizes to general imbalanced datasets.
Second, as suggested by our findings in Section 5, how should we choose loss
functions in order to mitigate Minority Collapse [CWG+19]. Last, a possible
use case of the Layer-Peeled Model is to design more efficient sampling
schemes to take into account fairness considerations [BG18, ZS18, MMS+19].

Broadly speaking, insights can be gained not only from the Layer-Peeled Model
but also from its modeling strategy. The details of empirical deep learning
models, though formidable, can often be simplified by rendering part of the
network modular. When the interest is about the top few layers, for example,
this paper clearly demonstrates the benefits of taking a top-down strategy for
modeling neural networks, especially in consolidating our understanding of
previous results and in discovering new patterns. Owing to its mathematical
convenience, the Layer-Peeled Model shall open the door for future research
extending these benefits.

### Acknowledgments

We are grateful to X.Y. Han for helpful discussions about some results of
[PHD20]. This work was supported in part by NIH through RF1AG063481, NSF
through CAREER DMS-1847415 and CCF-1934876, an Alfred Sloan Research
Fellowship, and the Wharton Dean’s Research Fund.

## References

  * [AKK+19] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi.  A theoretical analysis of contrastive unsupervised representation learning.  arXiv preprint arXiv:1902.09229, 2019.
  * [AZLS19] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International Conference on Machine Learning, pages 2388–2464, 2019.
  * [BCN18] Léon Bottou, Frank E Curtis, and Jorge Nocedal.  Optimization methods for large-scale machine learning.  Siam Review, 60(2):223–311, 2018.
  * [BFT17] Peter Bartlett, Dylan Foster, and Matus Telgarsky.  Spectrally-normalized margin bounds for neural networks.  Advances in Neural Information Processing Systems, 30:6241–6250, 2017.
  * [BG18] Joy Buolamwini and Timnit Gebru.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In Conference on fairness, accountability and transparency, pages 77–91, 2018.
  * [BHMM19] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal.  Reconciling modern machine-learning practice and the classical bias–variance trade-off.  Proceedings of the National Academy of Sciences, 116(32):15849–15854, 2019.
  * [BLLT20] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler.  Benign overfitting in linear regression.  Proceedings of the National Academy of Sciences, 2020.
  * [BMM18] Mateusz Buda, Atsuto Maki, and Maciej A Mazurowski.  A systematic study of the class imbalance problem in convolutional neural networks.  Neural Networks, 106:249–259, 2018.
  * [BMP08] Francis Bach, Julien Mairal, and Jean Ponce.  Convex sparse matrix factorizations.  arXiv preprint arXiv:0812.1869, 2008.
  * [BZMA20] Alexei Baevski, Henry Zhou, Abdelrahman Mohamed, and Michael Auli.  wav2vec 2.0: A framework for self-supervised learning of speech representations.  arXiv preprint arXiv:2006.11477, 2020.
  * [CJL+19] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie.  Class-balanced loss based on effective number of samples.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9268–9277, 2019.
  * [CKNH20] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  arXiv preprint arXiv:2002.05709, 2020.
  * [COB19] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In Advances in Neural Information Processing Systems, 2019.
  * [CWG+19] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma.  Learning imbalanced datasets with label-distribution-aware margin loss.  In Advances in Neural Information Processing Systems, volume 32, pages 1567–1578, 2019.
  * [DLL+19] Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In International Conference on Machine Learning, 2019.
  * [EMW19] Weinan E, Chao Ma, and Lei Wu.  A comparative analysis of the optimization and generalization property of two-layer neural network and random feature models under gradient descent dynamics.  arXiv preprint arXiv:1904.04326, 2019.
  * [EW20] Weinan E and Stephan Wojtowytsch.  On the emergence of tetrahedral symmetry in the final and penultimate layers of neural network classifiers.  arXiv preprint arXiv:2012.05420, 2020.
  * [FDZ21] Cong Fang, Han Dong, and Tong Zhang.  Mathematical models of overparameterized neural networks.  Proceedings of the IEEE, pages 1–21, 2021.
  * [FLLZ18] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang.  Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator.  In Advances in Neural Information Processing Systems, pages 689–699, 2018.
  * [FLYZ20] Cong Fang, Jason D Lee, Pengkun Yang, and Tong Zhang.  Modeling from features: a mean-field framework for over-parameterized deep neural networks.  arXiv preprint arXiv:2007.01452, 2020.
  * [FLZ19] Cong Fang, Zhouchen Lin, and Tong Zhang.  Sharp analysis for nonconvex SGD escaping from saddle points.  In Annual Conference on Learning Theory, pages 1192–1234, 2019\.
  * [FMZ19] Jianqing Fan, Cong Ma, and Yiqiao Zhong.  A selective overview of deep learning.  arXiv preprint arXiv:1904.05526, 2019.
  * [HLLT16] Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang.  Learning deep representation for imbalanced classification.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5375–5384, 2016.
  * [HMP+06] Eduard Hovy, Mitch Marcus, Martha Palmer, Lance Ramshaw, and Ralph Weischedel.  Ontonotes: the 90% solution.  In Proceedings of the human language technology conference of the NAACL, Companion Volume: Short Papers, pages 57–60, 2006.
  * [HS20] Hangfeng He and Weijie J Su.  The local elasticity of neural networks.  In International Conference on Learning Representations, 2020.
  * [HT20] Fengxiang He and Dacheng Tao.  Recent advances in deep learning theory.  arXiv preprint arXiv:2012.10931, 2020.
  * [HV19] Benjamin D Haeffele and René Vidal.  Structured low-rank matrix factorization: Global optimality, algorithms, and applications.  IEEE transactions on pattern analysis and machine intelligence, 42(6):1468–1482, 2019.
  * [HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [IS15] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In International Conference on Machine Learning, pages 448–456, 2015.
  * [JGH18] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In Advances in Neural Information Processing Systems, 2018.
  * [JK19] Justin M Johnson and Taghi M Khoshgoftaar.  Survey on deep learning with class imbalance.  Journal of Big Data, 6(1):27, 2019.
  * [Kri09] A Krizhevsky.  Learning multiple layers of features from tiny images.  Master’s thesis, University of Tront, 2009.
  * [KSH17] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Communications of the ACM, 60(6):84–90, 2017.
  * [KTW+20] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan.  Supervised contrastive learning.  arXiv preprint arXiv:2004.11362, 2020.
  * [KWL+19] Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Sanjeev Arora, and Rong Ge.  Explaining landscape connectivity of low-cost solutions for multilayer nets.  In Advances in Neural Information Processing Systems, pages 14601–14610, 2019.
  * [LBH15] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  Nature, 521(7553):436–444, 2015.
  * [LR20] Tengyuan Liang and Alexander Rakhlin.  Just interpolate: Kernel “ridgeless” regression can generalize.  Annals of Statistics, 48(3):1329–1347, 2020.
  * [LS20] Jianfeng Lu and Stefan Steinerberger.  Neural collapse with cross-entropy loss.  arXiv preprint arXiv:2012.08465, 2020.
  * [LSS20] Zhu Li, Weijie Su, and Dino Sejdinovic.  Benign overfitting and noisy features.  arXiv preprint arXiv:2008.02901, 2020.
  * [MBB18] Siyuan Ma, Raef Bassily, and Mikhail Belkin.  The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning.  In International Conference on Machine Learning, pages 3325–3334. PMLR, 2018.
  * [MMN18] Song Mei, Andrea Montanari, and Phan-Minh Nguyen.  A mean field view of the landscape of two-layer neural networks.  Proceedings of the National Academy of Sciences, 115(33):E7665–E7671, 2018.
  * [MMS+19] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.  A survey on bias and fairness in machine learning.  arXiv preprint arXiv:1908.09635, 2019.
  * [MPP20] Dustin G Mixon, Hans Parshall, and Jianzong Pi.  Neural collapse with unconstrained features.  arXiv preprint arXiv:2011.11619, 2020.
  * [MR17] K Madasamy and M Ramaswami.  Data imbalance and classifiers: impact and solutions from a big data perspective.  International Journal of Computational Intelligence Research, 13(9):2267–2281, 2017.
  * [OS20] Samet Oymak and Mahdi Soltanolkotabi.  Towards moderate overparameterization: global convergence guarantees for training shallow neural networks.  IEEE Journal on Selected Areas in Information Theory, 2020.
  * [PBL20] Tomaso Poggio, Andrzej Banburski, and Qianli Liao.  Theoretical issues in deep networks.  Proceedings of the National Academy of Sciences, 2020.
  * [PGM+19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  In Advances in neural information processing systems, pages 8026–8037, 2019.
  * [PHD20] Vardan Papyan, XY Han, and David 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.
  * [PL20] Tomaso Poggio and Qianli Liao.  Explicit regularization and implicit bias in deep network classifiers trained with the square loss.  arXiv preprint arXiv:2101.00072, 2020.
  * [PSM14] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014.
  * [RVE18] Grant M Rotskoff and Eric Vanden-Eijnden.  Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error.  In Advances in Neural Information Processing Systems, 2018.
  * [SH03] Thomas Strohmer and Robert W. Heath.  Grassmannian frames with applications to coding and communication.  Applied and Computational Harmonic Analysis, 14(3):257–275, 2003\.
  * [Sha20] Ohad Shamir.  Gradient methods never overfit on separable data.  arXiv preprint arXiv:2007.00028, 2020.
  * [SHM+16] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  Nature, 529(7587):484–489, 2016.
  * [SHN+18] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  The Journal of Machine Learning Research, 19(1):2822–2878, 2018\.
  * [SS19] Justin Sirignano and Konstantinos Spiliopoulos.  Mean field analysis of neural networks: A central limit theorem.  Stochastic Processes and their Applications, 2019.
  * [SSJ20] Bin Shi, Weijie J Su, and Michael I Jordan.  On learning rates and Schrödinger operators.  arXiv preprint arXiv:2004.06977, 2020.
  * [Sun19] Ruoyu Sun.  Optimization for deep learning: theory and algorithms.  arXiv preprint arXiv:1912.08957, 2019.
  * [SXY+19] Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng.  Meta-weight-net: Learning an explicit mapping for sample weighting.  arXiv preprint arXiv:1902.07379, 2019.
  * [SZ03] Jos F Sturm and Shuzhong Zhang.  On cones of nonnegative quadratic functions.  Mathematics of Operations Research, 28(2):246–267, 2003.
  * [SZ14] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [WL90] Andrew R Webb and David Lowe.  The optimised internal representation of multilayer classifier networks performs nonlinear discriminant analysis.  Neural Networks, 3(4):367–375, 1990.
  * [WLW+16] Shoujin Wang, Wei Liu, Jia Wu, Longbing Cao, Qinxue Meng, and Paul J Kennedy.  Training deep neural networks on imbalanced data sets.  In 2016 international joint conference on neural networks (IJCNN), pages 4368–4374. IEEE, 2016.
  * [XRV17] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [Yar17] Dmitry Yarotsky.  Error bounds for approximations with deep ReLU networks.  Neural Networks, 94:103–114, 2017.
  * [YCY+20] Yaodong Yu, Kwan Ho Ryan Chan, Chong You, Chaobing Song, and Yi Ma.  Learning diverse and discriminative representations via the principle of maximal coding rate reduction.  Advances in Neural Information Processing Systems, 33, 2020.
  * [ZCZG18] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu.  Stochastic gradient descent optimizes over-parameterized deep relu networks.  In Advances in Neural Information Processing Systems, 2018.
  * [ZKL+16] Bolei Zhou, Aditya Khosla, Agata Lapedriza, Antonio Torralba, and Aude Oliva.  Places: An image database for deep scene understanding.  arXiv preprint arXiv:1610.02055, 2016.
  * [ZS18] James Zou and Londa Schiebinger.  AI can be sexist and racist—it’s time to make it fair, 2018.

##  Appendix A Proofs

For simplicity, in this appendix we define
$[m_{1}:m_{2}]:=\\{m_{1},m_{1}+1,\dots,m_{2}\\}$ for
$m_{1},m_{2}\in\mathbb{N}$ with $m_{1}\leq m_{2}$ and $[m_{2}]:=[1:m_{2}]$ for
$m_{2}\geq 1$.

###  A.1 Balanced Case

####  A.1.1 Proofs of Theorem 1 and Proposition 2

Because there are multiplications of variables in the objective function,
Program (7) is nonconvex. Thus the KKT condition is not sufficient for
optimality. To prove Theorem 1, we directly determine the global minimum of
(7). During this procedure, one key step is to show that program (7) is
equivalent to minimize a symmetric quadratic function:

$\sum_{i=1}^{n}\left[\left(\sum_{k=1}^{K}\bm{h}_{k,i}\right)^{\top}\left(\sum_{k=1}^{K}\mathbf{w}_{k}\right)-K\sum_{k=1}^{K}\bm{h}_{k,i}^{\top}\mathbf{w}_{k}\right]$

under the same constraints with suitable conditions. Finally, by checking all
the conditions to reach the minimum, we obtain the minimizer of (7). The
detail is shown below.

###### Proof of Theorem 1.

By the concavity of $\log(\cdot)$, for any $\mathbf{z}\in\mathbb{R}^{K}$,
$k\in[K]$, constants $C_{a},C_{b}>0$, letting
$C_{c}=\frac{C_{b}}{(C_{a}+C_{b})(K-1)}$, we have

$\displaystyle-\log\left(\frac{\mathbf{z}(k)}{\sum_{{k^{\prime}}=1}^{K}\mathbf{z}({k^{\prime}})}\right)$
$\displaystyle=$
$\displaystyle-\log(\mathbf{z}(k))+\log\left(\frac{C_{a}}{C_{a}+C_{b}}\left(\frac{(C_{a}+C_{b})~{}\mathbf{z}(k)}{C_{a}}\right)+C_{c}\sum_{{k^{\prime}}=1,{k^{\prime}}\neq
k}^{K}\frac{\mathbf{z}({k^{\prime}})}{C_{c}}\right)$
$\displaystyle\overset{a}{\geq}$
$\displaystyle-\log(\mathbf{z}(k))+\frac{C_{a}}{C_{a}+C_{b}}\log\left(\frac{(C_{a}+C_{b})~{}\mathbf{z}(k)}{C_{a}}\right)+C_{c}\sum_{{k^{\prime}}=1,{k^{\prime}}\neq
k}^{K}\log\left(\frac{\mathbf{z}({k^{\prime}})}{C_{c}}\right)$
$\displaystyle\overset{b}{=}$
$\displaystyle-\frac{C_{b}}{C_{a}+C_{b}}\left[\log(\mathbf{z}(k))-\frac{1}{K-1}\sum_{{k^{\prime}}=1,{k^{\prime}}\neq
k}^{K}\log(\mathbf{z}({k^{\prime}}))\right]+C_{d},$ (19)

where $\overset{a}{\geq}$ applies the concavity of $\log(\cdot)$ and in
$\overset{b}{=}$, we define
$C_{d}:=\frac{C_{a}}{C_{a}+C_{b}}\log(\frac{C_{a}+C_{b}}{C_{a}})+\frac{C_{b}}{C_{a}+C_{b}}\log(1/C_{c})$.
Note that in (A.1.1), $C_{a}$ and $C_{b}$ can be any positive numbers. To
prove Theorem 1, we set $C_{a}:=\exp\left(\sqrt{E_{H}E_{W}}\right)$ and
$C_{b}:=\exp\left(-\sqrt{E_{H}E_{W}}/(K-1)\right)$, which shall lead to the
tightest lower bound for the objective of (7). Applying (A.1.1) on the
objective, we have

$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
(20) $\displaystyle\geq$
$\displaystyle\frac{C_{b}}{(C_{a}+C_{b})N(K-1)}\sum_{i=1}^{n}\left[\left(\sum_{k=1}^{K}\bm{h}_{k,i}\right)^{\top}\left(\sum_{k=1}^{K}\mathbf{w}_{k}\right)-K\sum_{k=1}^{K}\bm{h}_{k,i}^{\top}\mathbf{w}_{k}\right]+C_{d}.$

Defining $\bar{\bm{h}}_{i}:=\frac{1}{K}\sum_{k=1}^{K}\bm{h}_{k,i}$ for
$i\in[n]$, it follows by Young’s inequality that

$\displaystyle\sum_{i=1}^{n}\left[\left(\sum_{k=1}^{K}\bm{h}_{k,i}\right)^{\top}\left(\sum_{k=1}^{K}\mathbf{w}_{k}\right)-K\sum_{k=1}^{K}\bm{h}_{k,i}^{\top}\mathbf{w}_{k}\right]$
$\displaystyle=$ $\displaystyle
K\sum_{i=1}^{n}\sum_{k=1}^{K}(\bar{\bm{h}}_{i}-\bm{h}_{k,i})^{\top}\mathbf{w}_{k}$
$\displaystyle\geq$
$\displaystyle-\frac{K}{2}\sum_{k=1}^{K}\sum_{i=1}^{n}\|\bar{\bm{h}}_{i}-\bm{h}_{k,i}\|^{2}/C_{e}-\frac{C_{e}N}{2}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2},$
(21)

where we pick $C_{e}:=\sqrt{E_{H}/E_{W}}$. The two terms in the right hand
side of (A.1.1) can be bounded via the constraints of (7). Especially, we have

$\frac{C_{e}N}{2}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2}\leq\frac{KN\sqrt{E_{H}E_{W}}}{2},$
(22)

and

$\displaystyle\frac{K}{2}\sum_{k=1}^{K}\sum_{i=1}^{n}\|\bar{\bm{h}}_{i}-\bm{h}_{k,i}\|^{2}/C_{e}$
$\displaystyle\overset{a}{=}\frac{K^{2}}{2C_{e}}\sum_{i=1}^{n}\left(\frac{1}{K}\sum_{k=1}^{K}\|\bm{h}_{k,i}\|^{2}-\|\bar{\bm{h}}_{i}\|^{2}\right)$
$\displaystyle\leq\frac{K}{2C_{e}}\sum_{k=1}^{K}\sum_{i=1}^{n}\|\bm{h}_{k,i}\|^{2}\leq\frac{KN\sqrt{E_{H}E_{W}}}{2},$
(23)

where $\overset{a}{=}$ uses the fact that
$\mathbb{E}\|\mathbf{a}-\mathbb{E}[\mathbf{a}]\|^{2}=\mathbb{E}\|\mathbf{a}\|^{2}-\|\mathbb{E}[\mathbf{a}]\|^{2}$.
Thus plugging (A.1.1), (22), and (A.1.1) into (20), we have

$\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})\geq\frac{C_{b}}{C_{a}+C_{b}}\frac{K\sqrt{E_{H}E_{W}}}{K-1}+C_{d}:=L_{0}.$
(24)

Now we check the conditions to make the equality in (24) hold.

By the strict concavity of $\log(\cdot)$, the equality in (20) holds if and
only if

$\bm{h}_{k,i}\mathbf{w}_{k}=\bm{h}_{{k^{\prime}},i}\mathbf{w}_{{k^{\prime}}}+\log\left(\frac{C_{b}}{C_{a}}\right),$

for all
$(k,i,{k^{\prime}})\in\\{(k,i,{k^{\prime}}):k\in[K],{k^{\prime}}\in[K],{k^{\prime}}\neq
k,i\in[n]\\}$. The equality in (A.1.1) holds if and only if

$\bar{\bm{h}}_{i}-\bm{h}_{k,i}=-C_{e}\mathbf{w}_{k},\quad k\in[K],~{}i\in[n].$

The equalities in (22) and (A.1.1) hold if and only if:

$\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}=E_{H},\quad\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}=E_{W},\quad\bar{\bm{h}}_{i}=\mathbf{0}_{p},~{}i\in[n].$

Applying Lemma 2 shown in the end of the section, we have
$\left(\mathbf{H},\mathbf{W}\right)$ satisfies (8).

Reversely, it is easy to verify that the equality for (24) is reachable when
$(\mathbf{H},\mathbf{W})$ admits (8). So $L_{0}$ is the global minimum of (7)
and $(\mathbf{H},\mathbf{W})$ in (8) is the unique form for the minimizers. We
complete the proof of Theorem 1. ∎

###### Proof of Proposition 2.

We introduce the set $\mathcal{S}_{R}$ as

$\mathcal{S}_{R}:=\left\\{\left(\mathbf{H},\mathbf{W}\right):\begin{matrix}[\bm{h}_{1},\ldots,\bm{h}_{K}]=B_{1}b\mathbf{P}\left[(a+1)\mathbf{I}_{K}-\mathbf{1}_{K}\mathbf{1}_{K}^{\top}\right],\\\
\mathbf{W}=B_{2}B_{3}b\left[(a+1))\mathbf{I}_{K}-\mathbf{1}_{K}\mathbf{1}_{K}^{\top}\right]^{\top}\mathbf{P}^{\top}\\\
\bm{h}_{k,i}=\bm{h}_{k},\quad k\in[K],~{}i\in[n],\\\ b\geq 0,~{}a\geq
0,~{}b^{q}[a^{q}+(K-1)]=1,\\\
|B_{1}|\leq\sqrt{E_{H}},~{}|B_{2}|\leq\sqrt{E_{W}},~{}B_{3}\geq
0,~{}B_{3}^{2}b^{2}[a^{2}+(K-1)]=1,\\\ \mathbf{P}\in\mathbb{R}^{p\times
K},~{}\mathbf{P}^{\top}\mathbf{P}=\mathbf{I}_{K}.\end{matrix}\right\\}$

We can examine that $\mathcal{S}_{R}$ admits the constraints of (7). So any
$\left(\mathbf{H},\mathbf{W}\right)\in\mathcal{S}_{R}$ is a feasible solution.
Moreover, one can observe that this feasible solution has a special symmetry
structure: for each $k\in[K]$, the features in class $k$ collapse to their
mean $\bm{h}_{k}$, i.e., (NC1), and $\mathbf{w}_{k}$ is parallel to
$\bm{h}_{k}$, i.e., (NC3). However, weights do not form the vertices of ETF
unless $a=K-1$. Therefore, it suffices to show that the minimizer of
$\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
in the set $\mathcal{S}_{R}$ do not satisfy $a=K-1$.

In fact, for any $\left(\mathbf{H},\mathbf{W}\right)\in\mathcal{S}_{R}$, the
objective function value can be written as a function of $B_{1}$, $B_{2}$,
$B_{3}$, $a$, and $b$. We have

$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
$\displaystyle=$
$\displaystyle-\log\left(\frac{\exp(B_{1}B_{2}B_{3}b^{2}[a^{2}+(K-1)])}{\exp(B_{1}B_{2}B_{3}b^{2}[a^{2}+K-1])+(K-1)\exp(B_{1}B_{2}B_{3}b^{2}[K-2-2a])}\right)$
$\displaystyle=$
$\displaystyle-\log\left(\frac{1}{1+(K-1)\exp(-B_{1}B_{2}B_{3}b^{2}(a+1)^{2})}\right).$

It follows to maximize $B_{1}B_{2}B_{3}b^{2}(a+1)^{2}$ or equivalently
$\left[B_{1}B_{2}B_{3}b^{2}(a+1)^{2}\right]^{2}$. By
$B_{3}^{2}b^{2}[a^{2}+(K-1)]=1$ and $b^{q}[a^{q}+(K-1)]=1$, we have

$\displaystyle\left[B_{1}B_{2}B_{3}b^{2}(a+1)^{2}\right]^{2}$
$\displaystyle\overset{a}{\leq}E_{H}E_{W}\left[B_{3}^{2}b^{2}(a+1)^{2}\right]\left[b^{2}(a+1)^{2}\right]$
$\displaystyle=E_{H}E_{W}\left[\frac{(a+1)^{2}}{a^{2}+(K-1)}\right]\left[\frac{(a+1)^{q}}{a^{q}+K-1}\right]^{2/q}.$
(25)

where $\overset{a}{\leq}$ picks $B_{1}=\sqrt{E_{H}}$ and $B_{2}=\sqrt{E_{W}}$.
Let us consider function
$g:[0,+\infty)\to\mathbb{R}:g(x)=\left[\frac{(x+1)^{2}}{x^{2}+(K-1)}\right]\left[\frac{(x+1)^{q}}{x^{q}+K-1}\right]^{2/q}$.
Note that by the first-order optimality, once if $g^{\prime}(K-1)\neq 0$, then
(25) cannot achieve the maximum at $a=K-1$, which is our desired result.
Indeed, we have

$g^{\prime}(K-1)=\frac{2K^{4}}{\left[(K-1)^{2}+(K-1)\right]\left[(K-1)^{q}+K-1\right]^{2/q+1}}\left[(K-1)-(K-1)^{q-1}\right].$

So $a=K-1$ will not be the maximizer of (25) unless $q=2$. We complete the
proof. ∎

######  Lemma 2.

Suppose $\left(\mathbf{H},\mathbf{W}\right)$ satisfies

$\bar{\bm{h}}_{i}-\bm{h}_{k,i}=-\sqrt{\frac{E_{H}}{E_{W}}}\mathbf{w}_{k},\quad
k\in[K],\quad i\in[n],$ (26)

and

$\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}=E_{H},\quad\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}=E_{W},\quad\bar{\bm{h}}_{i}=\mathbf{0}_{p},~{}i\in[n],$
(27)

where $\bar{\bm{h}}_{i}:=\frac{1}{K}\sum_{k=1}^{K}\bm{h}_{k,i}$ with
$i\in[n]$. Moreover, there exists a constant $C$ such that for all
$(k,i,{k^{\prime}})\in\\{(k,i,{k^{\prime}}):k\in[K],{k^{\prime}}\in[K],{k^{\prime}}\neq
k,i\in[n]\\}$, we have

$\bm{h}_{k,i}\cdot\mathbf{w}_{k}=\bm{h}_{k,i}\cdot\mathbf{w}_{{k^{\prime}}}+C.$
(28)

Then $\left(\mathbf{H},\mathbf{W}\right)$ satisfies (8).

###### Proof.

Combining (26) with the last equality in (27), we have

$\mathbf{W}=\sqrt{\frac{E_{W}}{E_{H}}}~{}\bigg{[}\bm{h}_{1},\ldots,\bm{h}_{K}\bigg{]}^{\top},\quad\quad\bm{h}_{k,i}=\bm{h}_{k},~{}k\in[K],~{}i\in[n].$

Thus it remains to show

$\displaystyle\mathbf{W}=\sqrt{E_{W}}~{}\left({\mathbf{M}^{\star}}\right)^{\top},$
(29)

where ${\mathbf{M}^{\star}}$ is a $K$-simplex ETF.

Plugging $\bm{h}_{k}=\bm{h}_{k,i}=\sqrt{\frac{E_{W}}{E_{H}}}\mathbf{w}_{k}$
into (28), we have, for all
$(k,{k^{\prime}})\in\\{(k,{k^{\prime}}):k\in[K],{k^{\prime}}\in[K],{k^{\prime}}\neq
k\\}$,

$\sqrt{\frac{E_{H}}{E_{W}}}\|\mathbf{w}_{k}\|^{2}=\bm{h}_{k}\cdot\mathbf{w}_{k}=\bm{h}_{k}\cdot\mathbf{w}_{{k^{\prime}}}+C=\sqrt{\frac{E_{H}}{E_{W}}}\|\mathbf{w}_{{k^{\prime}}}\|^{2}+C,$

and

$\sqrt{\frac{E_{H}}{E_{W}}}\|\mathbf{w}_{{k^{\prime}}}\|^{2}=\bm{h}_{{k^{\prime}}}\cdot\mathbf{w}_{{k^{\prime}}}=\bm{h}_{{k^{\prime}}}\cdot\mathbf{w}_{k}+C=\sqrt{\frac{E_{W}}{E_{H}}}\|\bm{h}_{{k^{\prime}}}\|^{2}+C=\sqrt{\frac{E_{H}}{E_{W}}}\|\mathbf{w}_{{k^{\prime}}}\|^{2}+C.$

Therefore, from
$\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}=E_{W}$, we have
$\|\mathbf{w}_{k}\|=\sqrt{E_{W}}$ and
$\bm{h}_{k}\mathbf{w}_{{k^{\prime}}}=C^{\prime}:=\sqrt{E_{H}E_{W}}-C$.

On the other hand, recalling that $\bar{\bm{h}}_{i}=\mathbf{0}_{p}$ for
$i\in[n]$, we have $\sum_{k=1}^{K}\bm{h}_{k}=\mathbf{0}_{p}$, which further
yields $\sum_{k=1}^{K}\bm{h}_{k}\cdot\mathbf{w}_{k^{\prime}}=0$ for
${k^{\prime}}\in[K]$. Then it follows from
$\bm{h}_{k}\mathbf{w}_{{k^{\prime}}}=C^{\prime}$ and
$\bm{h}_{k}\mathbf{w}_{k}=\sqrt{E_{H}E_{W}}$ that
$\bm{h}_{k}\mathbf{w}_{{k^{\prime}}}=-\sqrt{E_{H}E_{W}}/(K-1)$. Thus we obtain

$\mathbf{W}\mathbf{W}^{\top}=\sqrt{\frac{E_{W}}{E_{H}}}\mathbf{W}[\bm{h}_{1},\ldots,\bm{h}_{K}]=E_{W}\left[\frac{K}{K-1}\left(\mathbf{I}_{K}-\frac{1}{K}\mathbf{1}_{K}\mathbf{1}_{K}^{\top}\right)\right],$

which implies (29). We complete the proof. ∎

####  A.1.2 Proofs of Theorems 3 and 4

The proof of Theorems 3 and 4 follow a similar argument of Theorem 1.

###### Proof of Theorem 3.

For $k\in[K]$, $i\in[n]$, and ${k^{\prime}}\in[K]$, define

$E_{k,i,{k^{\prime}}}:=\frac{1}{n}\sum_{j=1}^{n}\exp(\bm{h}_{k,i}\cdot\bm{h}_{{k^{\prime}},j}/\tau).$

For constants $C_{a}:=\exp\left(\sqrt{E_{H}E_{W}}\right)$ and
$C_{b}:=\exp\left(-\sqrt{E_{H}E_{W}}/(K-1)\right)$, let
$C_{c}:=\frac{C_{b}}{(C_{a}+C_{b})(K-1)}$. Using a similar argument as
(A.1.1), we have for $j\in[n]$,

$\displaystyle-\log\left(\frac{\exp(\bm{h}_{k,i}\cdot\bm{h}_{k,j}/\tau)}{\sum_{{k^{\prime}}=1}^{K}E_{k,i,{k^{\prime}}}}\right)$
(30) $\displaystyle=$
$\displaystyle-\bm{h}_{k,i}\cdot\bm{h}_{k,j}/\tau+\log\left(\frac{C_{a}}{C_{a}+C_{b}}\left(\frac{(C_{a}+C_{b})~{}E_{k,i,k}}{C_{a}}\right)+C_{c}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\frac{E_{k,i,{k^{\prime}}}}{C_{c}}\right)$
$\displaystyle\overset{a}{\geq}$
$\displaystyle-\bm{h}_{k,i}\cdot\bm{h}_{k,j}/\tau+\frac{C_{a}}{C_{a}+C_{b}}\log\left(\frac{(C_{a}+C_{b})~{}E_{k,i,k}}{C_{a}}\right)+C_{c}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\log\left(\frac{E_{k,i,{k^{\prime}}}}{C_{c}}\right)$
$\displaystyle\overset{b}{=}$
$\displaystyle-\bm{h}_{k,i}\cdot\bm{h}_{k,j}/\tau+\frac{C_{a}}{C_{a}+C_{b}}\log\left(E_{k,i,k}\right)+C_{c}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\log\left(E_{k,i,{k^{\prime}}}\right)+C_{d}$
$\displaystyle\overset{c}{\geq}$
$\displaystyle-\bm{h}_{k,i}\cdot\bm{h}_{k,j}/\tau+\frac{C_{a}}{(C_{a}+C_{b})n}\sum_{\ell=1}^{n}\bm{h}_{k,i}\cdot\bm{h}_{k,\ell}/\tau+\frac{C_{c}}{n}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\sum_{\ell=1}^{n}\bm{h}_{k,i}\cdot\bm{h}_{{k^{\prime}},\ell}/\tau+C_{d}.$

where $\overset{a}{\geq}$ and $\overset{c}{\geq}$ apply the concavity of
$\log(\cdot)$ and in $\overset{b}{=}$, we define
$C_{d}:=\frac{C_{a}}{C_{a}+C_{b}}\log(\frac{C_{a}+C_{b}}{C_{a}})+\frac{C_{b}}{C_{a}+C_{b}}\log(1/C_{c})$.
Then plugging (30) into the objective function, we have

$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\frac{1}{n}\sum_{j=1}^{n}-\log\left(\frac{\exp(\bm{h}_{k,i}\cdot\bm{h}_{k,j}/\tau)}{\sum_{{k^{\prime}}=1}^{K}\sum_{\ell=1}^{n}\exp(\bm{h}_{k,i}\cdot\bm{h}_{{k^{\prime}},\ell})}\right)$
(31) $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\frac{1}{n}\sum_{j=1}^{n}-\log\left(\frac{\exp(\bm{h}_{k,i}\cdot\bm{h}_{k,j}/\tau)}{\sum_{{k^{\prime}}=1}^{K}E_{k,i,{k^{\prime}}}}\right)+\log(n)$
$\displaystyle\overset{\eqref{eq:contral1}}{\geq}$
$\displaystyle\frac{C_{b}K}{(C_{a}+C_{b})N(K-1)\tau}\sum_{k=1}^{K}\sum_{i=1}^{n}\left(-\frac{1}{n}\sum_{j=1}^{n}\left(\bm{h}_{k,i}\cdot\bm{h}_{k,j}-\frac{1}{K}\sum_{{k^{\prime}}=1}^{K}\bm{h}_{k,i}\cdot\bm{h}_{{k^{\prime}},j}\right)\right)+C_{d}+\log(n).$

Now defining $\bar{\bm{h}}_{i}:=\frac{1}{K}\sum_{k=1}^{K}\bm{h}_{k,i}$ for
$i\in[n]$, a similar argument as (A.1.1) and (A.1.1) gives that

$\displaystyle\sum_{k=1}^{K}\sum_{i=1}^{n}\left(-\frac{1}{n}\sum_{j=1}^{n}\left(\bm{h}_{k,i}\cdot\bm{h}_{k,j}-\frac{1}{K}\sum_{{k^{\prime}}=1}^{K}\bm{h}_{k,i}\cdot\bm{h}_{{k^{\prime}},j}\right)\right)$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{i=1}^{n}\left(-\frac{1}{n}\sum_{j=1}^{n}\bm{h}_{k,i}\cdot(\bm{h}_{k,j}-\bar{\bm{h}}_{j})\right)$
$\displaystyle\overset{a}{\geq}$
$\displaystyle-\frac{1}{2}\sum_{k=1}^{K}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}-\frac{1}{2}\sum_{k=1}^{K}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}-\bar{\bm{h}}_{i}\right\|^{2}$
$\displaystyle\overset{b}{\geq}$
$\displaystyle-\frac{1}{2}\sum_{k=1}^{K}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}-\frac{K}{2}\sum_{i=1}^{n}\left(\frac{1}{K}\sum_{k=1}^{K}\left\|\bm{h}_{k,i}\right\|^{2}-\left\|\bar{\bm{h}}_{i}\right\|^{2}\right)$
$\displaystyle\geq$
$\displaystyle-\sum_{k=1}^{K}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}\overset{c}{\geq}-NE_{H},$
(32)

where $\overset{a}{\geq}$ follows from Young’s inequality, $\overset{b}{\geq}$
follows from
$\mathbb{E}\|\mathbf{a}-\mathbb{E}[\mathbf{a}]\|^{2}=\mathbb{E}\|\mathbf{a}\|^{2}-\|\mathbb{E}[\mathbf{a}]\|^{2}$,
and $\overset{c}{\geq}$ uses the constraint of (10). Therefore, plugging
(A.1.2) into (31) yields that

$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\frac{1}{n}\sum_{j=1}^{n}-\log\left(\frac{\exp(\bm{h}_{k,i}\cdot\bm{h}_{k,j}/\tau)}{\sum_{{k^{\prime}}=1}^{K}\sum_{\ell=1}^{n}\exp(\bm{h}_{k,i}\cdot\bm{h}_{{k^{\prime}},\ell}/\tau)}\right)$
$\displaystyle\geq$
$\displaystyle-\frac{C_{b}KE_{H}}{(C_{a}+C_{b})(K-1)\tau}+C_{d}+\log(n).$ (33)

Now we check the conditions to make the equality in (33) hold. By the strictly
concavity of $\log(\cdot)$, the equality in (30) holds only if for all
$(k,i,{k^{\prime}})\in\\{(k,i,{k^{\prime}}):k\in[K],{k^{\prime}}\in[K],{k^{\prime}}\neq
k,i\in[n]\\}$,

$\frac{E_{k,i,k}}{C_{a}}=\frac{E_{k,i,{k^{\prime}}}}{C_{b}}.$ (34)

The equality in (A.1.2) holds if and only if:

$\bm{h}_{k,i}=\bm{h}_{k},~{}i\in[n],~{}k\in[K],\quad\frac{1}{K}\sum_{k=1}^{K}\left\|\bm{h}_{k}\right\|^{2}=E_{H},\quad\sum_{k=1}^{K}\bm{h}_{k}=\mathbf{0}_{p}.$
(35)

Plugging $\bm{h}_{k,i}=\bm{h}_{k}$ into (34), we have for
$(k,{k^{\prime}})\in\\{k,{k^{\prime}}:k\in[K],{k^{\prime}}\in[K],{k^{\prime}}\neq
k\\}$,

$\frac{\exp(\|\bm{h}_{k}\|^{2})}{C_{a}}=\frac{\exp(\bm{h}_{k}\cdot\bm{h}_{{k^{\prime}}})}{C_{b}}=\frac{\exp(\|\bm{h}_{k^{\prime}}\|^{2})}{C_{a}}.$

Then it follows from
$\frac{1}{K}\sum_{k=1}^{K}\left\|\bm{h}_{k}\right\|^{2}=E_{H}$ that
$\|\bm{h}_{k}\|^{2}=E_{H}$ for $k\in[K]$. On the other hand, since
$\sum_{k=1}^{K}\bm{h}_{k}=\mathbf{0}_{p}$, we obtain

$\bm{h}_{k}\cdot\bm{h}_{{k^{\prime}}}=-\frac{E_{H}}{K-1}$

for
$(k,{k^{\prime}})\in\\{k,{k^{\prime}}:k\in[K],{k^{\prime}}\in[K],{k^{\prime}}\neq
k\\}$. Therefore,

$[\bm{h}_{1},\ldots,\bm{h}_{K}]^{\top}[\bm{h}_{1},\ldots,\bm{h}_{K}]=E_{H}\left[\frac{K}{K-1}\left(\mathbf{I}_{K}-\mathbf{1}_{K}\mathbf{1}_{K}^{\top}\right)\right],$

which implies (12).

Reversely, it is easy to verify that the equality for (33) is reachable when
$\mathbf{H}$ admits (12). We complete the proof of Theorem 3. ∎

###### Proof of Theorem 4.

We first determine the minimum value of (7). For the simplicity of our
expressions, we introduce $\mathbf{z}_{k,i}:=\mathbf{W}\bm{h}_{k,i}$ for
$k\in[K]$ and $i\in[n]$. By the convexity of $g_{2}$, for any $k\in[K]$ and
$i\in[n]$, we have

$\displaystyle\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}g_{2}\left(\mathbf{S}(\mathbf{z}_{k,j})({k^{\prime}})\right)$
$\displaystyle\geq(K-1)g_{2}\left(\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{S}(\mathbf{z}_{k,i})({k^{\prime}})\right)$
$\displaystyle\overset{a}{=}(K-1)g_{2}\left(1-\frac{1}{K-1}\mathbf{S}(\mathbf{z}_{k,i})(k)\right),$
(36)

where $\overset{a}{=}$ uses $\sum_{k=1}^{K}\mathbf{S}(\mathbf{a})(k)=1$ for
any $\mathbf{a}\in\mathbb{R}^{K}$. Then it follows by the convexity of $g_{1}$
and $g_{2}$ that

$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
(37) $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{i=1}^{n}\sum_{k=1}^{K}\left[g_{1}\left(\mathbf{S}(\mathbf{z}_{k,i})(k)\right)+\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}g_{2}\left(\mathbf{S}(\mathbf{z}_{{k^{\prime}},i})({k^{\prime}})\right)\right]$
$\displaystyle\overset{\eqref{eq:szz}}{\geq}$
$\displaystyle\frac{1}{N}\sum_{i=1}^{n}\sum_{k=1}^{K}\left[g_{1}\left(\mathbf{S}(\mathbf{z}_{k,i})(k)\right)+(K-1)g_{2}\left(1-\frac{1}{K-1}\mathbf{S}(\mathbf{z}_{k,i})(k)\right)\right]$
$\displaystyle\geq$ $\displaystyle
g_{1}\left(\frac{1}{N}\sum_{i=1}^{n}\sum_{k=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(k)\right)+(K-1)g_{2}\left(1-\frac{1}{N(K-1)}\sum_{i=1}^{n}\sum_{k=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(k)\right).$

Because $g_{1}(x)+(K-1)g_{2}(1-\frac{x}{K-1})$ is monotonously deceasing, it
suffices to maximize

$\frac{1}{N}\sum_{i=1}^{n}\sum_{k=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(k).$

To begin with, for any $\mathbf{z}_{k,i}$ with $k\in[K]$ and $i\in[n]$, by
convexity of exponential function and the monotonicity of $q(x)=\frac{a}{a+x}$
for $x>0$ if $a>0$, we have

$\displaystyle\mathbf{S}(\mathbf{z}_{k,i})(k)$
$\displaystyle=\frac{\exp(\mathbf{z}_{k,i}(k))}{\sum_{{k^{\prime}}=1}^{K}\exp(\mathbf{z}_{k,i}({k^{\prime}}))}$
$\displaystyle\leq\frac{\exp(\mathbf{z}_{k,i}(k))}{\exp(\mathbf{z}_{k,i}(k))+(K-1)\exp\left(\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{z}_{k,i}({k^{\prime}})\right)}$
$\displaystyle=\frac{1}{1+(K-1)\exp\left(\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{z}_{k,i}({k^{\prime}})-\mathbf{z}_{k,i}(k)\right)}.$ (38)

Consider function $g_{0}:\mathbb{R}\to\mathbb{R}$ as
$g_{0}(x)=\frac{1}{1+C\exp(x)}$ with $C:=(K-1)\geq 1$. We have

$g_{0}^{\prime\prime}(x)=-\frac{\exp(x)(1+C\exp(x))(1-C\exp(x))}{(1+C\exp(x))^{4}}.$
(39)

For any feasible solution $\left(\mathbf{H},\mathbf{W}\right)$ of (7), we
divide the index set $[n]$ into two subsets $\mathcal{S}_{1}$ and
$\mathcal{S}_{2}$ defined below:

  1. (A)

$i\in\mathcal{S}_{1}$ if there exists at least one $k\in[K]$ such that

$\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{z}_{k,i}({k^{\prime}})-\mathbf{z}_{k,i}(k)\geq\log\left(\frac{1}{K-1}\right).$

  2. (B)

$i\in\mathcal{S}_{2}$ if for all $k\in[K]$,
$\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{z}_{k,i}({k^{\prime}})-\mathbf{z}_{k,i}(k)<\log\left(\frac{1}{K-1}\right).$

Clearly, $\mathcal{S}_{1}\cap\mathcal{S}_{2}=\varnothing$. Let
$|\mathcal{S}_{1}|=t$, then $|\mathcal{S}_{2}|=n-t$. Define function
$L:[n]\to\mathbb{R}$ as

$L(t):=\begin{cases}N-\left(\frac{1}{2}t+\frac{K(n-t)}{1+\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)}\right),&\quad
t\in[0:n-1],\\\ N-\frac{n}{2},&\quad t=n.\end{cases}$ (40)

We show in Lemma 3 (see the end of the proof) that

$\frac{1}{N}\sum_{i=1}^{n}\sum_{k=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(i)\leq\frac{1}{N}L(0).$
(41)

Plugging (41) into (37), the objective function can be lower bounded as:

$\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})\geq
g_{1}\left(\frac{1}{N}L(0)\right)+(K-1)g_{2}\left(1-\frac{1}{N(K-1)}L(0)\right):=L_{0}.$
(42)

On the other hand, one can directly verify that the equality for (42) is
reachable when $(\mathbf{H},\mathbf{W})$ satisfies (8). So $L_{0}$ is the
global minimum of (7) and (8) is a minimizer of (7).

Now we show all the solutions are in form (8) under the assumption that
$g_{2}$ is strictly convex and $g_{1}$ (or $g_{2}$) are strictly monotone.

By the strict convexity of $g_{2}$, the equality in (A.1.2) holds if and only
if for any $k\in[K]$ and $i\in[n]$ and ${k^{\prime}}\in[K]$,
${k^{\prime\prime}}\in[K]$ such that ${k^{\prime}}\neq k$ and
${k^{\prime\prime}}\neq k$, we have

$\mathbf{S}(\mathbf{z}_{i,j})(k_{1})=\mathbf{S}(\mathbf{z}_{i,j})(k_{2}),$

which indicates that

$\bm{h}_{k,i}\cdot\mathbf{w}_{{k^{\prime}}}=\bm{h}_{k,i}\cdot\mathbf{w}_{{k^{\prime\prime}}}$
(43)

Again, by the strict convexity of $g_{2}$, (37) holds if and only if for all
$k\in[K]$, $i\in[n]$, and a suitable number $C^{\prime}\in(0,1)$, we have

$\mathcal{S}(\mathbf{z}_{k,i})(k):=C^{\prime}.$ (44)

Combining (43) with (44), we have for all
$(k,i,{k^{\prime}})\in\\{(k,i,{k^{\prime}}):k\in[K],{k^{\prime}}\in[K],{k^{\prime}}\neq
k,i\in[n]\\}$,

$\frac{\exp(\bm{h}_{k,i}\cdot\mathbf{w}_{k})}{\exp(\bm{h}_{k,i}\cdot\mathbf{w}_{{k^{\prime}}})}=\frac{C^{\prime}(K-1)}{1-C^{\prime}},$

which implies that

$\bm{h}_{k,i}\cdot\mathbf{w}_{k}=\bm{h}_{k,i}\cdot\mathbf{w}_{{k^{\prime}}}+\log\left(\frac{C^{\prime}(K-1)}{1-C^{\prime}}\right).$

On the other hand, by the strict monotonicity of
$g_{1}(x)+(K-1)g_{2}(1-\frac{x}{K-1})$, the equality in (42) holds if and only
if
$\frac{1}{N}\sum_{i=1}^{n}\sum_{k=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(k)=L(0)$.
Thus Lemma 3 reads

$\bar{\bm{h}}_{i}-\bm{h}_{k,i}=-\sqrt{\frac{E_{H}}{E_{W}}}\mathbf{w}_{k},\quad
k\in[K],\quad i\in[n],$

and

$\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}=E_{H},\quad\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}=E_{W},\quad\bar{\bm{h}}_{i}=\mathbf{0}_{p},~{}i\in[n],$

where $\bar{\bm{h}}_{i}:=\frac{1}{K}\sum_{k=1}^{K}\bm{h}_{k,i}$ with
$i\in[n]$. In all, from Lemma 2, we have $\left(\mathbf{H},\mathbf{W}\right)$
satisfies (8), achieving the uniqueness argument. We complete the proof of
Theorem 4. ∎

######  Lemma 3.

For any feasible solution $\left(\mathbf{H},\mathbf{W}\right)$, we have

$\sum_{i=1}^{n}\sum_{k=1}^{K}\mathbf{S}(\mathbf{W}\bm{h}_{k,i})(k)\leq L(0),$
(45)

with $L$ defined in (40). Moreover, recalling the definition of
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ in (A) and (B), the equality in (45)
holds if and only if $|\mathcal{S}_{1}|=0$,

$\bar{\bm{h}}_{i}-\bm{h}_{k,i}=-\sqrt{\frac{E_{H}}{E_{W}}}\mathbf{w}_{k},\quad
k\in[K],\quad i\in[n],$

and

$\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}=E_{H},\quad\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}=E_{W},\quad\bar{\bm{h}}_{i}=\mathbf{0}_{p},~{}i\in[n],$

where $\bar{\bm{h}}_{i}:=\frac{1}{K}\sum_{k=1}^{K}\bm{h}_{k,i}$ with
$i\in[n]$.

###### Proof of Lemma 3.

For any feasible solution $\left(\mathbf{H},\mathbf{W}\right)$, we separately
consider $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ defined in (A) and (B),
respectively. Let $t:=|\mathcal{S}_{1}|$.

  * •

For $i\in\mathcal{S}_{1}$, let $k\in[K]$ be any index such that
$\frac{1}{K-1}\sum_{{k^{\prime}}\neq
k}\mathbf{z}_{k,i}({k^{\prime}})-\mathbf{z}_{k,i}(k)\geq\log\left(\frac{1}{K-1}\right)$,
where $\mathbf{z}_{k,i}:=\mathbf{W}\bm{h}_{k,i}$. By the monotonicity of
$g_{0}(x)$, it follows from (38) that $S(\mathbf{z}_{k,i})(k)\leq 1/2$.
Furthermore, for the other index ${k^{\prime}}\in[K]$ such that
${k^{\prime}}\neq k$, using that
$\frac{\exp(\mathbf{z}_{{k^{\prime}},i}({k^{\prime}}))}{\sum_{{k^{\prime\prime}}=1}^{K}\exp(\mathbf{z}_{{k^{\prime}},i})({k^{\prime\prime}})}\leq
1$, we have

$\sum_{i\in\mathcal{S}_{1}}\sum_{k=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(k)\leq
t(1/2+K-1).$ (46)

  * •

For $i\in\mathcal{S}_{2}$, by the concavity of $g_{0}(x)$ when
$x<\log\left(\frac{1}{K-1}\right)$ from (39), we have, for
$\mathcal{S}_{2}\neq\varnothing$,

$\displaystyle\sum_{i\in\mathcal{S}_{2}}\sum_{k=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(k)$
(47) $\displaystyle\overset{\eqref{eq:expb}}{\leq}$
$\displaystyle\sum_{i\in\mathcal{S}_{2}}\sum_{k=1}^{K}\frac{1}{1+(K-1)\exp\left(\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{z}_{k,i}({k^{\prime}})-\mathbf{z}_{k,i}(k)\right)}$
$\displaystyle\leq$
$\displaystyle\frac{(n-t)K}{1+(K-1)\exp\left(\frac{1}{(n-t)K}\sum_{i\in\mathcal{S}_{2}}\sum_{k=1}^{K}\left(\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{z}_{k,i}({k^{\prime}})-\mathbf{z}_{k,i}(k)\right)\right)}.$

We can bound
$\sum_{i\in\mathcal{S}_{2}}\sum_{k=1}^{K}\left(\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{z}_{k,i}({k^{\prime}})-\mathbf{z}_{k,i}(k)\right)$ using the
similar arguments in (A.1.1) and (A.1.1). Especially, recalling
$\bar{\bm{h}}_{i}=\frac{1}{K}\sum_{k=1}^{K}\bm{h}_{k,i}$ for $i\in[n]$, we
have

$\displaystyle\sum_{i\in\mathcal{S}_{2}}\sum_{k=1}^{K}\left(\frac{1}{K-1}\sum_{{k^{\prime}}=1,~{}{k^{\prime}}\neq
k}^{K}\mathbf{z}_{k,i}({k^{\prime}})-\mathbf{z}_{k,i}(k)\right)$ (48)
$\displaystyle=$
$\displaystyle\frac{1}{K-1}\sum_{i\in\mathcal{S}_{2}}\left[\left(\sum_{k=1}^{K}\bm{h}_{k,i}\right)^{\top}\left(\sum_{k=1}^{K}\mathbf{w}_{k}\right)-K\sum_{K=1}^{K}\bm{h}_{k,i}^{\top}\mathbf{w}_{k}\right]$
$\displaystyle\overset{\eqref{eq:padd}}{\geq}$
$\displaystyle-\frac{K}{2(K-1)}\sum_{k=1}^{K}\sum_{i\in\mathcal{S}_{2}}\|\bar{\bm{h}}_{i}-\bm{h}_{k,i}\|^{2}/C^{\prime\prime}-\frac{C^{\prime\prime}K(n-t)}{2(K-1)}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2}$
$\displaystyle\overset{\eqref{eq:boundtheta}}{\geq}$
$\displaystyle-\frac{K}{2(K-1)}\sum_{k=1}^{K}\sum_{i\in\mathcal{S}_{2}}\|\bm{h}_{k,i}\|^{2}/C^{\prime\prime}-\frac{C^{\prime\prime}K(n-t)}{2(K-1)}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2}$
$\displaystyle\geq$
$\displaystyle-\frac{K}{2(K-1)}\sum_{k=1}^{K}\sum_{i=1}^{n}\|\bm{h}_{k,i}\|^{2}/C^{\prime\prime}-\frac{C^{\prime\prime}K(n-t)}{2(K-1)}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2}$
$\displaystyle\geq$
$\displaystyle-\frac{K^{2}}{(K-1)}\sqrt{E_{H}E_{W}(n-t)n},$

where in the last inequality we follow from the constrains of (7) and set
$C^{\prime\prime}:=\sqrt{\frac{nE_{H}}{(n-t)E_{W}}}$.

We combine the above two cases. When $t\in[0,n-1]$, by plugging (48) into
(47), using the monotonicity of $g_{0}(x)$, and adding (46), we have

$\displaystyle\sum_{k=1}^{n}\sum_{i=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(k)$
$\displaystyle\leq
N-\left(\frac{1}{2}t+\frac{K}{1+\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)}(n-t)\right)$
$\displaystyle=L(t).$ (49)

And when $t=n$, it directly follows from (47) that

$\sum_{k=1}^{n}\sum_{i=1}^{K}\mathbf{S}(\mathbf{z}_{k,i})(k)\leq
N-\frac{n}{2}=L(n).$

Therefore, it suffices to show $L(t)\leq L(0)$ for all $t\in[0:n]$. We first
consider the case when $t\in[0:N-1]$. We show that $L(t)$ is monotonously
decreasing. Indeed, define

$q(t):=\frac{K}{1+\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)}.$

We have

$\displaystyle q^{\prime}(t)$
$\displaystyle=\frac{-\frac{1}{2}K\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)\frac{K}{K-1}\sqrt{E_{H}E_{W}n}(n-t)^{-3/2}}{\left[1+\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)\right]^{2}}$
$\displaystyle\geq\frac{-\frac{1}{2}\frac{K^{2}}{K-1}\sqrt{E_{H}E_{W}n}(n-t)^{-3/2}}{1+\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)},$

which implies that

$\displaystyle
L^{\prime}(t)=-\left[\frac{1}{2}-q(t)+q^{\prime}(t)(n-t)\right]$
$\displaystyle\leq$
$\displaystyle\frac{\frac{1}{2}\frac{K^{2}}{K-1}\sqrt{E_{H}E_{W}n}(n-t)^{-1/2}+K}{1+\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)}-\frac{1}{2}$
$\displaystyle=$
$\displaystyle\frac{K\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}\right)+2K-1-\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)}{2\left[1+\exp\left(\frac{K}{K-1}\sqrt{n/(n-t)}\sqrt{E_{H}E_{W}}-\log(K-1)\right)\right]}.$

Consider function
$f(x):\left[\frac{K}{K-1}\sqrt{E_{H}E_{W}},\frac{K}{K-1}\sqrt{E_{H}E_{W}n}\right]\to
R$ as:

$f(x)=Kx+2K-1-\exp(x-\log(K-1)).$

We have

$f^{\prime}(x)=K-\exp(x)/(K-1)<0$

when
$x\in\left[\frac{K}{K-1}\sqrt{E_{H}E_{W}},\frac{K}{K-1}\sqrt{E_{H}E_{W}n}\right]$,
where we use the assumption that

$\sqrt{E_{H}E_{W}}>\frac{K-1}{K}\log\left(K^{2}\sqrt{E_{H}E_{W}}+(2K-1)(K-1)\right)\geq\frac{K-1}{K}\log\left(K(K-1)\right).$

Therefore, for all
$x\in\left[\frac{K}{K-1}\sqrt{E_{H}E_{W}},\frac{K}{K-1}\sqrt{E_{H}E_{W}n}\right]$,
we have

$f(x)\leq
f\left(\frac{K}{K-1}\sqrt{E_{H}E_{W}}\right)=\frac{K^{2}}{K-1}\sqrt{E_{H}E_{W}}+2K-1-\frac{1}{K-1}\exp\left(\frac{K}{K-1}\sqrt{E_{H}E_{W}}\right)\overset{a}{<}0,$

where $\overset{a}{<}$ use our assumption again. We obtain $L^{\prime}(t)<0$
for all $t\in[0:N-1]$. So $L(t)$ reaches the maximum if and only if $t=0$ when
$t\in[0:N-1]$. Moreover, under our assumption, one can verify that
$L(N)<L(0)$. We obtain (45) from (49) with $t=0$.

When $t=0$, the equality in the first inequality of (48) holds if and only if:

$\bar{\bm{h}}_{i}-\bm{h}_{k,i}=-\sqrt{\frac{E_{H}}{E_{W}}}\mathbf{w}_{k},\quad
k\in[K],\quad i\in[n].$

The equality in the second and third inequalities of (48) holds if and only
if:

$\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n}\sum_{i=1}^{n}\left\|\bm{h}_{k,i}\right\|^{2}=E_{H},\quad\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}=E_{W},\quad\bar{\bm{h}}_{i}=\mathbf{0}_{p},~{}i\in[n].$

We obtain Lemma 3. ∎

###  A.2 Imbalanced Case

####  A.2.1 Proofs of Lemma 1 and Proposition 1

###### Proof of Lemma 1.

For any feasible solution $\left(\bm{H},\mathbf{W}\right)$ for the original
program (7), we define

$\mathbf{h}_{k}:=\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\mathbf{h}_{k,i},~{}k\in[K],\quad\text{and}\quad\mathbf{X}:=\left[\bm{h}_{1},\bm{h}_{2},\dots,\bm{h}_{K},\mathbf{W}^{\top}\right]^{\top}\left[\bm{h}_{1},\bm{h}_{2},\dots,\bm{h}_{K},\mathbf{W}^{\top}\right].$

Clearly, $\mathbf{X}\succeq 0$. For the other two constraints of (14), we have

$\frac{1}{K}\sum_{k=1}^{K}\mathbf{X}(k,k)\\\
=\frac{1}{K}\sum_{k=1}^{K}\|\mathbf{h}_{k}\|^{2}\overset{a}{\leq}\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}\right\|^{2}\\\
\overset{b}{\leq}E_{H},$

and

$\frac{1}{K}\sum_{k=K+1}^{2K}\mathbf{X}(k,k)=\frac{1}{K}\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2}\overset{c}{\leq}E_{W},$

where $\overset{a}{\leq}$ applies Jensen’s inequality and $\overset{b}{\leq}$
and $\overset{c}{\leq}$ use that $\left(\bm{H},\mathbf{W}\right)$ is a
feasible solution. So $\mathbf{X}$ is a feasible solution for the convex
program (14). Letting $L_{0}$ be the global minimum of (14), for any feasible
solution $\left(\bm{H},\mathbf{W}\right)$, we obtain

$\displaystyle\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
$\displaystyle=\sum_{k=1}^{K}\frac{n_{k}}{N}\left[\frac{1}{n_{k}}\sum_{k=1}^{n_{k}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})\right]$
$\displaystyle\overset{a}{\geq}\sum_{k=1}^{K}\frac{n_{k}}{N}\mathcal{L}(\mathbf{W}\bm{h}_{k},\mathbf{y}_{k})=\sum_{k=1}^{K}\frac{n_{k}}{N}\mathcal{L}(\mathbf{z}_{k},\mathbf{y}_{k})\geq
L_{0},$ (50)

where in $\overset{a}{\geq}$, we use $\mathcal{L}$ is convex on the first
argument, and so $\mathcal{L}(\mathbf{W}\mathbf{h},\mathbf{y}_{k})$ is convex
on $\mathbf{h}$ given $\mathbf{W}$ and $k\in[K]$.

On the other hand, considering the solution
$\left(\bm{H}^{\star},\mathbf{W}^{\star}\right)$ defined in (15) with
$\mathbf{X}^{\star}$ being a minimizer of (14), we have
$\left[\bm{h}_{1}^{\star},\bm{h}_{2}^{\star},\dots,\bm{h}_{K}^{\star},(\mathbf{W}^{\star})^{\top}\right]^{\top}\left[\bm{h}_{1}^{\star},\bm{h}_{2}^{\star},\dots,\bm{h}_{K}^{\star},(\mathbf{W}^{\star})^{\top}\right]=\mathbf{X}^{\star}$
($p\geq 2K$ guarantees the existence of
$\left[\bm{h}_{1}^{\star},\bm{h}_{2}^{\star},\dots,\bm{h}_{K}^{\star},(\mathbf{W}^{\star})^{\top}\right]$).
We can verify that $\left(\bm{H}^{\star},\mathbf{W}^{\star}\right)$ is a
feasible solution for (7) and have

$\frac{1}{N}\sum_{k=1}^{K}\sum_{i=1}^{n_{k}}\mathcal{L}(\mathbf{W}^{\star}\bm{h}_{k,i}^{\star},\mathbf{y}_{k})=\sum_{k=1}^{K}\frac{n_{k}}{N}\mathcal{L}(\mathbf{z}_{k}^{\star},\mathbf{y}_{k})=L_{0},$
(51)

where
$\mathbf{z}_{k}^{\star}=\left[\mathbf{X}^{\star}(k,1+K),\mathbf{X}^{\star}(k,2+K),\dots,\mathbf{X}^{\star}(k,2K)~{}\right]^{\top}$
for $k\in[K]$.

Combing (A.2.1) and (51), we conclude that $L_{0}$ is the global minimum of
(7) and $(\mathbf{H}^{\star},\mathbf{W}^{\star})$ is a minimizer.

Suppose there is a minimizer
$\left(\bm{H}^{\prime},\mathbf{W}^{\prime}\right)$ that cannot be written as
(15). Let

$\mathbf{h}_{k}^{\prime}=\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\mathbf{h}_{k,i}^{\prime},~{}k\in[K],\quad\text{and}\quad\mathbf{X}^{\prime}=\left[\bm{h}_{1}^{\prime},\bm{h}_{2}^{\prime},\dots,\bm{h}_{K}^{\prime},(\mathbf{W}^{\prime})^{\top}\right]^{\top}\left[\bm{h}_{1}^{\prime},\bm{h}_{2}^{\prime},\dots,\bm{h}_{K}^{\prime},(\mathbf{W}^{\prime})^{\top}\right].$

(A.2.1) implies that $\mathbf{X}^{\prime}$ is a minimizer of (14). As
$\left(\bm{H}^{\prime},\mathbf{W}^{\prime}\right)$ cannot be written as (15)
with $\mathbf{X}^{\star}=\mathbf{X}^{\prime}$, then there is a
${k^{\prime}}\in[K]$, $i,j\in[n_{k^{\prime}}]$ with $i\neq j$ such that
$\mathbf{h}_{{k^{\prime}},i}\neq\mathbf{h}_{{k^{\prime}},j}$. We have

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}X^{\prime}(k,k)=\frac{1}{K}\sum_{k=1}^{K}\|\mathbf{h}_{k}^{\prime}\|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}^{\prime}\right\|^{2}-\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{k=1}^{K}\|\mathbf{h}_{k,i}^{\prime}-\mathbf{h}_{k}^{\prime}\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}^{\prime}\right\|^{2}-\frac{1}{K}\frac{1}{n_{k^{\prime}}}(\|\mathbf{h}_{{k^{\prime}},i}^{\prime}-\mathbf{h}_{{k^{\prime}}}^{\prime}\|^{2}+\|\mathbf{h}_{{k^{\prime}},j}^{\prime}-\mathbf{h}_{{k^{\prime}}}^{\prime}\|^{2})$
$\displaystyle\leq$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}^{\prime}\right\|^{2}-\frac{1}{K}\frac{1}{2n_{k^{\prime}}}\|\mathbf{h}_{{k^{\prime}},i}^{\prime}-\mathbf{h}_{{k^{\prime}},j}^{\prime}\|^{2}$
$\displaystyle<$ $\displaystyle E_{H}.$

By contraposition, if all $\mathbf{X}^{\star}$ satisfy that
$\frac{1}{K}\sum_{k=1}^{K}\mathbf{X}^{\star}(k,k)=E_{H}$, then all the
solutions of (7) are in form of (15). We complete the proof. ∎

Proposition 1 can be obtained by a same argument as Lemma 1. We omit the proof
here.

####  A.2.2 Proof of Theorem 5

To prove Theorem 5, we first study a limit case where we only learn the
classification for a partial classes. Especially, we solve the optimization
program:

$\displaystyle\min_{\mathbf{H},\mathbf{W}}$
$\displaystyle\frac{1}{K_{A}n_{A}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
(52) $\displaystyle\mathrm{s.t.}$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\left\|\bm{h}_{k,i}\right\|^{2}\leq
E_{H},$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}\right\|^{2}\leq
E_{W},$

where $n_{1}=n_{2}=\dots=n_{K_{A}}=n_{A}$ and
$n_{K_{A}+1}=n_{K_{A}+2}=\dots=n_{K}=n_{B}$. Lemma 4 characterizes useful
properties for the minimizer of (52).

######  Lemma 4.

Let $(\bm{H},\mathbf{W})$ be a minimzer of (52). We have
$\mathbf{h}_{k,i}=\mathbf{0}_{p}$ for all $k\in[K_{A}+1:K]$ and $i\in[n_{B}]$.
Define $L_{0}$ as the global minimum of (52), i.e.,

$L_{0}:=\frac{1}{K_{A}n_{A}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k}).$

Then $L_{0}$ only depends on $K_{A}$, $K_{B}$, $E_{H}$, and $E_{W}$. Moreover,
for any feasible solution $\left(\bm{H}^{\prime},\mathbf{W}^{\prime}\right)$,
if there exist $k,{k^{\prime}}\in[K_{A}+1:K]$ such that
$\left\|\mathbf{w}_{k}-\mathbf{w}_{k^{\prime}}\right\|=\varepsilon>0$, we have

$\frac{1}{K_{A}n_{A}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}\left(\mathbf{W}^{\prime}\bm{h}_{k,i}^{\prime},\mathbf{y}_{k}\right)\geq
L_{0}+\varepsilon^{\prime},$

where $\varepsilon^{\prime}>0$ depends on $\varepsilon$, $K_{A}$, $K_{B}$,
$E_{H}$, and $E_{W}$.

Now we are ready to prove Theorem 5. The proof is based on the contradiction.

###### Proof of Theorem 5.

Consider sequences $n_{A}^{\ell}$ and $n_{B}^{\ell}$ with
$R^{\ell}:=n_{A}^{\ell}/n^{\ell}_{B}$ for $\ell=1,2,\dots$. We have
$R^{\ell}\to\infty$. For each optimization program indexed by
$\ell\in\mathbb{N}_{+}$, we define
$(\bm{H}^{\ell,\star}.\mathbf{W}^{\ell,\star})$ as a minimizer and separate
the objective function into two parts. That is, we introduce

$\mathcal{L}^{\ell}\left(\mathbf{H}^{\ell},\mathbf{W}^{\ell}\right):=\frac{K_{A}n_{A}^{\ell}}{K_{A}n_{A}^{\ell}+K_{B}n_{B}^{\ell}}\mathcal{L}^{\ell}_{A}\left(\mathbf{H}^{\ell},\mathbf{W}^{\ell}\right)+\frac{K_{B}n_{B}^{\ell}}{K_{A}n_{A}^{\ell}+K_{B}n_{B}^{\ell}}\mathcal{L}^{\ell}_{B}\left(\mathbf{H}^{\ell},\mathbf{W}^{\ell}\right),$

with

$\mathcal{L}^{\ell}_{A}\left(\mathbf{H}^{\ell},\mathbf{W}^{\ell}\right):=\frac{1}{K_{A}n_{A}^{\ell}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}^{\ell}}\mathcal{L}\left(\mathbf{W}^{\ell}\bm{h}_{k,i}^{\ell},\mathbf{y}_{k}\right)$

and

$\mathcal{L}^{\ell}_{B}\left(\mathbf{H}^{\ell},\mathbf{W}^{\ell}\right):=\frac{1}{K_{B}n_{B}^{\ell}}\sum_{k=K_{A}+1}^{K}\sum_{i=1}^{n_{B}^{\ell}}\mathcal{L}\left(\mathbf{W}^{\ell}\bm{h}_{k,i}^{\ell},\mathbf{y}_{k}\right).$

We define $\left(\bm{H}^{\ell,A},\mathbf{W}^{\ell,A}\right)$ as a minimizer of
the optimization program:

$\displaystyle\min_{\bm{H}^{\ell},\mathbf{W}^{\ell}}$
$\displaystyle\mathcal{L}^{\ell}_{A}\left(\mathbf{H}^{\ell},\mathbf{W}^{\ell}\right)$
(53) $\displaystyle\mathrm{s.t.}$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}^{\ell}\right\|^{2}\leq
E_{W},$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K_{A}}\frac{1}{n_{A}^{\ell}}\sum_{i=1}^{n_{A}^{\ell}}\left\|\bm{h}_{k,i}\right\|^{2}+\frac{1}{K}\sum_{k=K_{A}+1}^{K}\frac{1}{n_{B}^{\ell}}\sum_{i=1}^{n_{B}^{\ell}}\left\|\bm{h}_{k,i}\right\|^{2}\leq
E_{H},$

and $\left(\bm{H}^{\ell,B},\mathbf{W}^{\ell,B}\right)$ as a minimizer of the
optimization program:

$\displaystyle\min_{\bm{H}^{\ell},\mathbf{W}^{\ell}}$
$\displaystyle\mathcal{L}^{\ell}_{B}\left(\mathbf{H}^{\ell},\mathbf{W}^{\ell}\right)$
(54) $\displaystyle\mathrm{s.t.}$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\left\|\mathbf{w}_{k}^{\ell}\right\|^{2}\leq
E_{W},$
$\displaystyle\frac{1}{K}\sum_{k=1}^{K_{A}}\frac{1}{n_{A}^{\ell}}\sum_{i=1}^{n_{A}^{\ell}}\left\|\bm{h}_{k,i}\right\|^{2}+\frac{1}{K}\sum_{k=K_{A}+1}^{K}\frac{1}{n_{B}^{\ell}}\sum_{i=1}^{n_{B}^{\ell}}\left\|\bm{h}_{k,i}\right\|^{2}\leq
E_{H}.$

Note that Programs (53) and (54) and their minimizers have been studied in
Lemma 4. We define:

$L_{A}:=\mathcal{L}^{\ell}_{A}\left(\mathbf{H}^{\ell,A},\mathbf{W}^{\ell,A}\right)\quad\text{and}\quad
L_{B}:=\mathcal{L}^{\ell}_{B}\left(\mathbf{H}^{\ell,B},\mathbf{W}^{\ell,B}\right).$

Then Lemma 4 implies that $L_{A}$ and $L_{B}$ only depend on $K_{A}$, $K_{B}$,
$E_{H}$, and $E_{W}$, and are independent of $\ell$. Moreover, since
$\mathbf{h}_{k,i}^{\ell,A}=\mathbf{0}_{p}$ for all $k\in[K_{A}+1:K]$ and
$i\in[n_{B}]$, we have

$\mathcal{L}^{\ell}_{B}\left(\mathbf{H}^{\ell,A},\mathbf{W}^{\ell,A}\right)=\log(K).$
(55)

Now we prove Theorem 5 by contradiction. Suppose there exists a pair
$(k,{k^{\prime}})$ such that
$\lim_{\ell\to\infty}\mathbf{w}^{\ell,\star}_{k}-\mathbf{w}^{\ell,\star}_{k^{\prime}}\neq\mathbf{0}_{p}$.
Then there exists $\varepsilon>0$ such that for a subsequence
$\left\\{\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)\right\\}_{\ell=1}^{\infty}$
and an index $\ell_{0}$ when $\ell\geq\ell_{0}$, we have
$\left\|\mathbf{w}^{a_{\ell},\star}_{k}-\mathbf{w}^{a_{\ell},\star}_{k^{\prime}}\right\|\geq\varepsilon$.
Now we figure out a contradiction by estimating the objective function value
on $\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)$. In
fact, because
$\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)$ is a
minimizer of $\mathcal{L}^{\ell}(\mathbf{H}^{\ell},\mathbf{W}^{\ell})$, we
have

$\displaystyle\mathcal{L}^{a_{\ell}}\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)\leq\mathcal{L}^{a_{\ell}}\left(\mathbf{H}^{a_{\ell},A},\mathbf{W}^{a_{\ell},A}\right)$
$\displaystyle\overset{\eqref{eq:lblog}}{=}\frac{K_{A}n_{A}^{a_{\ell}}}{K_{A}n_{A}^{a_{\ell}}+K_{B}n_{B}^{a_{\ell}}}L_{A}+\frac{K_{B}n_{B}^{a_{\ell}}}{K_{A}n_{A}^{a_{\ell}}+K_{B}n_{B}^{a_{\ell}}}\log(K)$
$\displaystyle=L_{A}+\frac{1}{K_{R}R^{a_{\ell}}+1}\left(\log(K)-L_{A}\right)\overset{\ell\to\infty}{\to}L_{A},$
(56)

where we define $K_{R}:=K_{A}/K_{B}$ and use
$R^{\ell}=n_{A}^{\ell}/n_{B}^{\ell}$.

However, when $\ell>\ell_{0}$, because
$\left\|\mathbf{w}^{a_{\ell},\star}_{k}-\mathbf{w}^{a_{\ell},\star}_{k^{\prime}}\right\|\geq\varepsilon>0$,
Lemma 4 implies that

$\mathcal{L}^{a_{\ell}}_{A}\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)\geq
L_{A}+\varepsilon_{2},$

where $\varepsilon_{2}>0$ only depends on $\varepsilon$, $K_{A}$, $K_{B}$,
$E_{H}$, and $E_{W}$, and is independent of $\ell$. We obtain

$\displaystyle\mathcal{L}^{a_{\ell}}\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)$
$\displaystyle=\mathcal{L}^{a_{\ell}}_{A}\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)+\mathcal{L}^{a_{\ell}}_{B}\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)$
$\displaystyle\overset{a}{\geq}\mathcal{L}^{a_{\ell}}_{A}\left(\mathbf{H}^{a_{\ell},\star},\mathbf{W}^{a_{\ell},\star}\right)+\mathcal{L}^{a_{\ell}}_{B}\left(\mathbf{H}^{a_{\ell},B},\mathbf{W}^{a_{\ell},B}\right)$
$\displaystyle=\frac{K_{A}n_{A}^{a_{\ell}}}{K_{A}n_{A}^{a_{\ell}}+K_{B}n_{B}^{a_{\ell}}}(L_{A}+\varepsilon_{2})+\frac{K_{B}n_{B}^{a_{\ell}}}{K_{A}n_{A}^{a_{\ell}}+K_{B}n_{B}^{a_{\ell}}}L_{B}$
$\displaystyle=L_{A}+\varepsilon_{2}+\frac{1}{K_{R}R^{a_{\ell}}+1}(L_{B}-L_{A}-\varepsilon_{2})\overset{\ell\to\infty}{\to}L_{A}+\varepsilon_{2},$
(57)

where $\overset{a}{\geq}$ uses
$\left(\mathbf{H}^{a_{\ell},B},\mathbf{W}^{a_{\ell},B}\right)$ is the
minimizer of (54). Thus we meet contradiction by comparing (A.2.2) with
(A.2.2) and achieve Theorem 5. ∎

###### Proof of Lemma 4.

For any constants $C_{a}>0$, $C_{b}>0$, and $C_{c}>0$, define
$C_{a}^{\prime}:=\frac{C_{a}}{C_{a}+(K_{A}-1)C_{b}+K_{B}C_{c}}\in(0,1)$,
$C_{b}^{\prime}:=\frac{C_{b}}{C_{a}+(K_{A}-1)C_{b}+K_{B}C_{c}}\in(0,1)$, and
$C_{c}^{\prime}:=\frac{C_{c}}{C_{a}+(K_{A}-1)C_{b}+K_{B}C_{c}}\in(0,1)$,
$C_{d}:=-C_{a}^{\prime}\log(C_{a}^{\prime})-C_{b}^{\prime}(K_{A}-1)\log(C_{b}^{\prime})-K_{B}C_{c}^{\prime}\log(C_{c}^{\prime})$,
$C_{e}:=\frac{K_{A}C_{b}}{K_{A}C_{b}+K_{B}C_{c}}\in(0,1)$,
$C_{f}:=\frac{K_{B}C_{c}}{K_{A}C_{b}+K_{B}C_{c}}\in(0,1)$, and
$C_{g}:=\frac{K_{A}C_{b}+K_{B}C_{c}}{C_{a}+(K_{A}-1)C_{b}+K_{B}C_{c}}>0$.
Using a similar argument as Theorem 1, we show in Lemma 5 (see the end of the
proof), for any feasible solution $(\bm{H},\mathbf{W})$ of (52), the objective
value can be bounded from below by:

$\displaystyle\frac{1}{K_{A}n_{A}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
(58) $\displaystyle\overset{a}{\geq}$
$\displaystyle-\frac{C_{g}}{K_{A}}\sqrt{KE_{H}}\sqrt{\sum_{k=1}^{K_{A}}\left\|C_{e}\mathbf{w}_{A}+C_{f}\mathbf{w}_{B}-\mathbf{w}_{k}\right\|^{2}}+C_{d}$
$\displaystyle\overset{b}{\geq}$
$\displaystyle-\frac{C_{g}}{K_{A}}\sqrt{KE_{H}}\sqrt{KE_{W}-K_{A}\left(1/K_{R}-C_{f}^{2}-\frac{C_{f}^{4}}{C_{e}(2-C_{e})}\right)\|\mathbf{w}_{B}\|^{2}-\sum_{k=K_{A}+1}^{K}\left\|\mathbf{w}_{k}-\mathbf{w}_{B}\right\|^{2}}+C_{d},$

where $\mathbf{w}_{A}:=\frac{1}{K_{A}}\sum_{k=1}^{K_{A}}\mathbf{w}_{k}$,
$\mathbf{w}_{B}:=\frac{1}{K_{B}}\sum_{k=K_{A}+1}^{K}\mathbf{w}_{k}$, and
$K_{R}:=\frac{K_{A}}{K_{B}}$. Moreover, the equality in $\overset{a}{\geq}$
holds only if $\mathbf{h}_{k,i}=\mathbf{0}_{p}$ for all $k\in[K_{A}+1:K]$ and
$i\in[n_{B}]$.

Though $C_{a}$, $C_{b}$, and $C_{c}$ can be any positive numbers, we need to
carefully pick them to exactly reach the global minimum of (52). In the
following, we separately consider three cases according to the values of
$K_{A}$, $K_{B}$, and $E_{H}E_{W}$.

  1. (i)

Consider the case when $K_{A}=1$. We pick
$C_{a}:=\exp\left(\sqrt{K_{B}(1+K_{B})E_{H}E_{W}}\right)$, $C_{b}:=1$, and
$C_{c}:=\exp\left(-\sqrt{(1+K_{B})E_{H}E_{W}/K_{B}}\right)$.

Then from $\overset{a}{\geq}$ in (58), we have

$\displaystyle\frac{1}{K_{A}n_{A}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})$
$\displaystyle\overset{a}{\geq}$ $\displaystyle-
C_{g}C_{f}\sqrt{KE_{H}}\sqrt{\left\|\mathbf{w}_{1}-\mathbf{w}_{B}\right\|^{2}}+C_{d}$
$\displaystyle=$ $\displaystyle-
C_{g}C_{f}\sqrt{KE_{H}}\sqrt{\|\mathbf{w}_{1}\|^{2}-2\mathbf{w}_{1}^{\top}\mathbf{w}_{B}+\|\mathbf{w}_{B}\|^{2}}+C_{d}$
$\displaystyle\overset{b}{\geq}$ $\displaystyle-
C_{g}C_{f}\sqrt{KE_{H}}\sqrt{(1+1/K_{B})(\|\mathbf{w}_{1}\|^{2}+K_{B}\|\mathbf{w}_{B}\|^{2})}+C_{d}$
$\displaystyle\overset{c}{\geq}$ $\displaystyle-
C_{g}C_{f}\sqrt{KE_{H}}\sqrt{(1+1/K_{B})\left(KE_{W}-\sum_{k=2}^{K}\|\mathbf{w}_{k}-\mathbf{w}_{B}\|^{2}\right)}+C_{d}$
$\displaystyle\geq$ $\displaystyle-
C_{g}C_{f}\sqrt{KE_{H}}\sqrt{(1+1/K_{B})KE_{W}}+C_{d}:=L_{1},$ (59)

where $\overset{a}{\geq}$ uses $C_{e}+C_{f}=1$, $\overset{b}{\geq}$ follows
from Young’s inequality, i.e.,
$-2\mathbf{w}_{1}^{\top}\mathbf{w}_{B}\leq(1/K_{B})\|\mathbf{w}_{1}\|^{2}+K_{B}\|\mathbf{w}_{B}\|^{2}$,
and $\overset{c}{\geq}$ follows from
$\sum_{k=2}^{K}\|\mathbf{w}_{k}\|^{2}=K_{B}\|\mathbf{w}_{B}\|^{2}+\sum_{k=2}^{K}\|\mathbf{w}_{k}-\mathbf{w}_{B}\|^{2}$
and the constraint that $\sum_{k=1}^{K}\|\mathbf{w}_{k}\|^{2}\leq KE_{W}$.

On the other hand, when $(\mathbf{H},\mathbf{W})$ satisfies that

$\displaystyle\begin{aligned}
\mathbf{w}_{1}&=\sqrt{K_{B}E_{W}}\mathbf{u},\quad\mathbf{w}_{k}=-\sqrt{1/K_{B}E_{W}}\mathbf{u},~{}k\in[2:K],\\\
\bm{h}_{1,i}=&\sqrt{(1+K_{B})E_{H}}\mathbf{u},~{}i\in[n_{A}],\quad\quad\bm{h}_{k,i}=\mathbf{0}_{p},~{}k\in[2:K],~{}i\in[n_{B}],\\\
\end{aligned}$

where $\mathbf{u}$ is any unit vector, $(\mathbf{H},\mathbf{W})$ can achieve
the equality in (i). So $L_{1}$ is the global minimum of (52). Moreover,
$L_{1}$ is achieved only if the equality in $\overset{a}{\geq}$ in (58) holds.
From Lemma 52, we have any minimizer satisfies that
$\mathbf{h}_{k,i}=\mathbf{0}_{p}$ for all $k\in[K_{A}+1:K]$ and $i\in[n_{B}]$.

Finally, for any feasible solution
$\left(\bm{H}^{\prime},\mathbf{W}^{\prime}\right)$, if there exist
$k,{k^{\prime}}\in[K_{A}+1:K]$ such that
$\left\|\mathbf{w}_{k}-\mathbf{w}_{k^{\prime}}\right\|=\varepsilon>0$, we have

$\sum_{k=K_{A}+1}^{K}\|\mathbf{w}_{k}-\mathbf{w}_{B}\|^{2}\geq\|\mathbf{w}_{k}-\mathbf{w}_{B}\|^{2}+\|\mathbf{w}_{k^{\prime}}-\mathbf{w}_{B}\|^{2}\geq\frac{\|\mathbf{w}_{k}-\mathbf{w}_{k^{\prime}}\|^{2}}{2}=\varepsilon^{2}/2.$
(60)

It follows from $\overset{c}{\geq}$ in (i) that

$\frac{1}{K_{A}n_{A}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})\geq-
C_{g}C_{f}\sqrt{KE_{H}}\sqrt{(1+1/K_{B})\left(KE_{W}-\varepsilon^{2}/2\right)}+C_{d}:=L_{1}+\varepsilon_{1}$

with $\varepsilon_{1}>0$ depending on $\varepsilon$, $K_{A}$, $K_{B}$,
$E_{H}$, and $E_{W}$.

  2. (ii)

Consider the case when $K_{A}>1$ and
$\exp\left((1+1/K_{R})\sqrt{E_{H}E_{W}}/(K_{A}-1)\right)<\sqrt{1+K_{R}}+1$.
Let us pick $C_{a}:=\exp\left((1+1/K_{R})\sqrt{E_{H}E_{W}}\right)$,
$C_{b}:=\exp\left(-\frac{1}{K_{A}-1}(1+1/K_{R})\sqrt{E_{H}E_{W}}\right)$, and
$C_{c}:=1$.

Following from $\overset{b}{\geq}$ in (58), we know if
$1/K_{R}-C_{f}^{2}-\frac{C_{f}^{4}}{C_{e}(2-C_{f})}>0$, then

$\displaystyle\frac{1}{K_{A}n_{A}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})\geq-
C_{g}(1+1/K_{R})\sqrt{E_{H}E_{W}}+C_{d}:=L_{2}.$ (61)

In fact, we do have $1/K_{R}-C_{f}^{2}-\frac{C_{f}^{4}}{C_{e}(2-C_{f})}>0$
because

$\displaystyle\begin{aligned}
\quad&1/K_{R}>C_{f}^{2}-\frac{C_{f}^{4}}{C_{e}(2-C_{e})}\quad\quad\quad\left(\text{by~{}}C_{e}+C_{f}=1\right)\\\
\iff\quad&C_{e}>\sqrt{\frac{1}{1+K_{R}}}\quad\quad\quad\left(\text{by~{}}C_{e}=\frac{K_{B}C_{c}}{K_{A}C_{b}+K_{B}C_{c}}\right)\\\
\iff\quad&\frac{C_{b}}{C_{c}}>\frac{1}{\sqrt{1+K_{R}}+1}\\\
\iff\quad&\exp\left((1+1/K_{R})\sqrt{E_{H}E_{W}}/(K_{A}-1)\right)<\sqrt{1+K_{R}}+1.\end{aligned}$

On the other hand, when $(\mathbf{H},\mathbf{W})$ satisfies that

$\displaystyle\begin{aligned}
\left[\mathbf{w}_{1},\mathbf{w}_{2},\ldots,\mathbf{w}_{K_{A}}\right]=&\sqrt{\frac{E_{W}}{E_{H}}}~{}\bigg{[}\bm{h}_{1},\ldots,\bm{h}_{K_{A}}\bigg{]}^{\top}=\sqrt{(1+1/K_{R})E_{W}}~{}(\mathbf{M}_{A}^{\star})^{\top},\\\
\bm{h}_{k,i}=&\bm{h}_{k},\quad k\in[K_{A}],~{}i\in[n_{A}]\\\
\bm{h}_{k,i}=&\mathbf{w}_{k}=\mathbf{0}_{p},\quad
k\in[K_{A}+1:K],~{}i\in[n_{B}],\\\ \end{aligned}$

where $\mathbf{M}_{A}^{\star}$ is a $K_{A}$-simplex ETF,
$(\mathbf{H},\mathbf{W})$ can achieve the equality in (61). So $L_{2}$ is the
global minimum of (52). Moreover, $L_{2}$ is achieved only if the equality in
$\overset{a}{\geq}$ of (58) holds. From Lemma 5, we have any minimizer
satisfies that $\mathbf{h}_{k,i}=\mathbf{0}_{p}$ for all $k\in[K_{A}+1:K]$ and
$i\in[n_{B}]$.

Finally, for any feasible solution
$\left(\bm{H}^{\prime},\mathbf{W}^{\prime}\right)$, if there exist
$k,{k^{\prime}}\in[K_{A}+1:K]$ such that
$\left\|\mathbf{w}_{k}-\mathbf{w}_{k^{\prime}}\right\|=\varepsilon>0$,
plugging (60) into (58), we have

$\frac{1}{K_{A}n_{A}}\sum_{k=1}^{K_{A}}\sum_{i=1}^{n_{A}}\mathcal{L}(\mathbf{W}\bm{h}_{k,i},\mathbf{y}_{k})\geq-\frac{C_{g}}{K_{A}}\sqrt{KE_{H}}\sqrt{KE_{W}-\varepsilon^{2}/2}+C_{d}:=L_{2}+\varepsilon_{2},$
(62)

with $\varepsilon_{2}>0$ depending on $\varepsilon$, $K_{A}$, $K_{B}$,
$E_{H}$, and $E_{W}$.

  3. (iii)

Consider the case when $K_{A}>1$ and
$\exp((1+1/K_{R})\sqrt{E_{H}E_{W}}/(K_{A}-1))\geq\sqrt{1+K_{R}}+1$. Let
$C_{f}^{\prime}:=\frac{1}{\sqrt{K_{R}+1}}$ and
$C_{e}^{\prime}:=1-C_{f}^{\prime}$. For $x\in[0,1]$, we define:

$\displaystyle\begin{aligned}
g_{N}(x):&=\sqrt{\frac{(1+K_{R})E_{W}}{K_{R}x^{2}+(K_{R}+K_{R}^{2})(1-x)^{2}}},\\\
g_{a}(x):&=\exp\left(\frac{g_{N}(x)\sqrt{(1+K_{R})E_{H}/K_{R}}}{\sqrt{x^{2}+\left(1+\frac{C_{e}^{\prime}}{C_{f}^{\prime}}\right)^{2}(1-x)^{2}}}\left[x^{2}+\left(1+\frac{C_{e}^{\prime}}{C_{f}^{\prime}}\right)(1-x)^{2}\right]\right),\\\
g_{b}(x):&=\exp\left(\frac{g_{N}(x)\sqrt{(1+K_{R})E_{H}/K_{R}}}{\sqrt{x^{2}+\left(1+\frac{C_{e}^{\prime}}{C_{f}^{\prime}}\right)^{2}(1-x)^{2}}}\left[-\frac{1}{K_{A}-1}x^{2}+\left(1+\frac{C_{e}^{\prime}}{C_{f}^{\prime}}\right)(1-x)^{2}\right]\right),\\\
g_{c}(x):&=\exp\left(\frac{g_{N}(x)\sqrt{(1+K_{R})E_{H}/K_{R}}}{\sqrt{x^{2}+\left(1+\frac{C_{e}^{\prime}}{C_{f}^{\prime}}\right)^{2}(1-x)^{2}}}\left[-\left(1+\frac{C_{e}^{\prime}}{C_{f}^{\prime}}\right)K_{R}(1-x)^{2}\right]\right).\end{aligned}$

Let $x_{0}\in[0,1]$ be a root of the equation

$g_{b}(x)/g_{c}(x)=\frac{1/C_{f}^{\prime}-1}{K_{R}}.$

We first show that the solution $x_{0}$ exists. First of all, one can directly
verify when $x\in[0,1]$, $g_{b}(x)/g_{c}(x)$ is continuous. It suffices to
prove that (1) $g_{b}(0)/g_{c}(0)\geq\frac{1/C_{f}^{\prime}-1}{K_{R}}$ and (2)
$g_{b}(1)/g_{c}(1)\leq\frac{1/C_{f}^{\prime}-1}{K_{R}}$.

    1. (1)

When $x=0$, we have $g_{b}(x)/g_{c}(x)\geq\exp(0)=1$. At the same time,
$\frac{1/C_{f}^{\prime}-1}{K_{R}}=\frac{\sqrt{K_{R}+1}-1}{K_{R}}=\frac{1}{\sqrt{K_{R}+1}+1}\leq
1$. Thus $(i)$ is achieved.

    2. (2)

When $x=1$, we have $g_{N}(1)=\sqrt{(1+1/K_{R})E_{W}}$, so

$\displaystyle\begin{aligned}
g_{b}(1)/g_{c}(1)=\exp\left(-(1+1/K_{R})\sqrt{E_{H}E_{W}}/(K_{A}-1)\right)\overset{a}{\leq}\frac{1}{\sqrt{K_{R}+1}+1}=\frac{1/C_{f}^{\prime}-1}{K_{R}}.\end{aligned}$

where $\overset{a}{\leq}$ is obtained by the condition that

$\exp\left((1+1/K_{R})\sqrt{E_{H}E_{W}}/(K_{A}-1)\right)\geq\sqrt{1+K_{R}}+1.$

Now we pick $C_{a}:=g_{a}(x_{0})$, $C_{b}:=g_{b}(x_{0})$, and
$C_{c}:=g_{c}(x_{0})$, because