# Supervised Contrastive Representation Learning:
Landscape Analysis with Unconstrained Features

Tina Behnia, Christos Thrampoulidis This work is supported by an NSERC
Discovery Grant, a CRG8-KAUST award, and funding from AML-TN program at UBC.
Department of Electrical and Computer Engineering
University of British Columbia
Vancouver, BC, Canada
Email: {tina.behnia<EMAIL_ADDRESS>
###### Abstract

Recent findings reveal that over-parameterized deep neural networks, trained
beyond zero training-error, exhibit a distinctive structural pattern at the
final layer, termed as Neural-collapse (NC). These results indicate that the
final hidden-layer outputs in such networks display minimal within-class
variations over the training set. While existing research extensively
investigates this phenomenon under cross-entropy loss, there are fewer studies
focusing on its contrastive counterpart, supervised contrastive (SC) loss.
Through the lens of NC, this paper employs an analytical approach to study the
solutions derived from optimizing the SC loss. We adopt the unconstrained
features model (UFM) as a representative proxy for unveiling NC-related
phenomena in sufficiently over-parameterized deep networks. We show that,
despite the non-convexity of SC loss minimization, all local minima are global
minima. Furthermore, the minimizer is unique (up to a rotation). We prove our
results by formalizing a tight convex relaxation of the UFM. Finally, through
this convex formulation, we delve deeper into characterizing the properties of
global solutions under label-imbalanced training data.

##  I Introduction

Contrastive techniques (e.g., [1, 2]) have led to major improvements in the
self-supervised representation learning, and recently, [3] introduced the
supervised contrastive (SC) loss as an extension of these techniques tailored
to the supervised problems. SC loss is applied on the embeddings generated by
the network and it penalizes the model by measuring how similar or dissimilar
the learned embeddings are for different samples based on their class
membership. The objective with the SC loss is to bring the embeddings with the
same label close to each other while keeping them apart from those belonging
to other classes. In other words, the loss value emphasizes on the
interactions of pairs of samples from the training set. This is in contrast to
other widely used loss functions like cross-entropy (CE) where the loss is
computed on each sample individually, aiming to maximize the class-probability
associated with the correct label.

Focusing on the CE loss, [4] recently discovered a common pattern at the final
layer of the over-parameterized deep-nets, whose number of parameters far
exceeds the number of training samples. According to their observations, in
the modern deep learning regime where deep-nets are trained beyond zero-
training error, at the last layer, the network learns to compress the training
data by forcing the embeddings to collapse to their class-means, exhibiting a
low-rank structure. Furthermore, when the training data is balanced, the
class-means exhibit a symmetric pattern. In particular, they form a simplex
_equiangular tight frame_ (ETF), where all the class-mean vectors have equal
norms and are maximally-separated. Importantly, this simple geometry appears
to be “ _cross-situationally invariant_ ”, as it appears at the final layer of
various architectures trained on benchmark datasets [4]. Seeking to explain
the optimality of this structure, [4] links the feature learning process to an
abstract optimal coding task. Treating each embedding as a codeword for the
class membership, and the classification task as a decoding of the noisy
codeword, [4] demonstrates that this shared geometry yields the optimal
codebook. This discovery, termed as Neural collapse (NC), has led to a long
line of follow-up works, e.g., [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16].
The majority of these works focus on the CE and mean-squared-error loss, and a
few consider analyzing contrastive techniques in this context.

The NC discovery was an empirical attempt to demystify the black-box nature of
the deep-nets and to more formally characterize what large networks learn at
the training stage. NC also shares connections with the implicit bias
literature (e.g., [17, 18, 19]) where the success of over-parameterization is
attributed to the optimization algorithms, arguing that gradient-based
algorithms inherently favor solutions with certain properties that generalize
well. However, the emergence of NC in deep overparameterized networks remains
hard to theoretically explain due to the complex interactions of their
parameters and layers. This challenge motivated a series of theoretical
studies to justify the NC phenomenon from an optimization perspective (e.g.,
[15, 20, 7, 21, 22, 12, 5, 16, 10, 23]). These works rely on a proxy model
called _unconstrained features model_ (UFM). This model leverges the powerful
expressivity of large deep-nets to simplify the mathematical formulation of
the training objective. This is made possible by only focusing on the
interactions of the last-layer parameters of the network in the loss function.
Despite its simplicity, UFM has proved a useful tool for predicting certain
empirical patterns learned by deep-nets during training.

###  I-A Related Works

Neural-collapse. After the influential paper [4], important follow-up works
introduced UFM [12, 5, 7] as an abstract model for theoretically studying the
last-layer of over-parameterized deep-nets. In this model the focus is only on
the structure of the parameters in the final layer that optimize the desired
objective. Previous works [12, 5, 7, 15, 16, 10, 20, 23] have studied the UFM
problem for the CE loss showing that with class-balanced training sets all the
global solutions satisfy the NC property and form a simplex ETF as empirically
reported by [4]. Despite being a non-convex problem, [15] proves that UFM with
CE loss has a benign landscape: all local optimals are global optimal, and
there are no spurious saddle points. Thus, any optimization algorithm that can
escape saddle points, converges to the global optimal, that is the simplex
ETF. While most of these works study the balanced setup, several works use the
UFM to predict the learned final-layer embeddings for class-imbalanced
training data [5, 20, 21], and support their theoretical findings by
experiments on benchmark datasets and architectures. The geometric
characterization of the embeddings under the mean-squared [12, 16, 13] and
contrastive [7, 5] loss have also been investigated by adopting the UFM.
Several works [9, 6, 24] also explore the potential links of NC to
generalization and down-stream tasks.

Supervised contrastive loss. Unlike CE and mean-squared-error loss, there are
fewer works on the geometry characterization of the constrastive loss through
the lens of NC. The SC loss is known to exhibit more robustness to noise and
hyper-parameter values [3]. Its resilience has inspired a series of works
where the variants of the SC loss combined with CE are used for training
models that tackle distribution shifts in the data with better performance
[25, 26, 27, 28, 29]. In the context of self-supervised learning, [30]
investigates the properties of the contrastive feature learning. For
supervised classification, [7] is the first to compare how the CE and SC loss
encode the training data by studying the UFM. They show that with balanced
training data, the global optimizer of the SC loss is ETF similar to CE and
demonstrate that deep-nets trained with the SC loss reach this global
optimizer. However, unlike CE, they emphasize on the fact that the optimality
of this geometry can be violated depending on the mini-batch selection in
practical scenarios. Later, [22] suggests adjustments on the training to
ensure learning an embedding geometry that is invariant to the randomness in
batching and level of class-imbalance. Furthermore, [31] conjecture that as
with the CE loss, the UFM trained by the SC loss also has a benign landscape
with no spurious local minima despite its non-convex nature. Their claim is
motivated by numerical verifications that show we can reach the global
solution of the UFM by running simple gradient methods for minimizing the SC
loss.

###  I-B Contributions

In this work, we theoretically analyze the local solutions of the SC loss
under the UFM assumptions. We first demonstrate that all the stationary points
exhibit the collapse property (see Definition 1). Leveraging this low-rank
structure at the stationary points, we prove that the SC loss has a benign
landscape: we show that although the optimal solution is not unique, all the
local solutions only differ up to a rotation and are equivalent to the global
solution. Our results rely on introducing a tight convex relaxation of the
UFM. As a consequence of this analysis, we are able to simplify finding the
global optimizer into a lower-dimensional equivalent program under the STEP
imbalanced assumption on the training set. For the special case of balanced
training data, this program reveals ETF as the optimal geometry as also
previously shown in [7]. However, ETF is not a global solution otherwise.

Notations. We use $[n]$ to denote the set $\\{1,2,...,n\\}$. For matrix
$\mathbf{V}_{m\times n}$, $\mathbf{V}_{i,j}$ denotes its $(i,j)$-th entry,
$\mathbf{v}_{j}$ the $j$-th _column_ , and $\mathbf{V}^{\top}$ its transpose.
When $m=n$, $\mathbf{V}\succeq 0$ is a PSD matrix and
$\operatorname{diag}(\mathbf{V})$ is a diagonal matrix that includes the
diagonal elements of $\mathbf{V}$. We use $\mathbf{1}_{m}$ and
$\mathds{I}_{m}$ to denote the $m$-dimensional vector of all ones and the
identity matrix respectively. Finally, $\otimes$ refers to the Kronecker
product.

##  II Problem Setup

Consider a supervised classification setup with $k$ classes and a training set
$\mathcal{S}=\\{(\mathbf{x}_{i},y_{i}):i\in[n]\\}$ where
$\mathbf{x}_{i}\in\mathds{R}^{p}$ and $y_{i}\in[k]$ are the $i$-th data sample
and its class label. We also let $n_{c}\geq 1$, $c\in[k]$ to be the number of
examples in class $c$.

We consider the deep-net as a non-linear encoder
$\mathbf{h}_{\boldsymbol{\theta}}:\mathds{R}^{p}\to\mathds{R}^{d}$ mapping the
input space to a new embedding space that is parameterized by the trainable
variables ${\boldsymbol{\theta}}$. Define
$\mathbf{h}_{{\boldsymbol{\theta}},i}:=\mathbf{h}_{\boldsymbol{\theta}}(\mathbf{x}_{i}),\,i\in[n]$
and let
$\mathbf{H}_{\boldsymbol{\theta}}:=[\mathbf{h}_{{\boldsymbol{\theta}},1},...,\mathbf{h}_{{\boldsymbol{\theta}},n}]_{d\times
n}$ be the training embeddings learned by the deep-net. With the SC loss, we
seek to find the optimal parameters by minimizing $\mathcal{L}_{\text{SC}}$
defined as follows:

$\displaystyle\mathcal{L}_{\text{SC}}(\mathbf{H}_{\boldsymbol{\theta}};\tau)={\frac{1}{n}}\sum_{i\in[n]}\frac{-1}{n_{y_{i}}-1}\sum_{\begin{subarray}{c}j\neq
i\\\
y_{j}=y_{i}\end{subarray}}\log\bigg{(}\frac{e^{{\mathbf{h}_{{\boldsymbol{\theta}},i}^{\top}\mathbf{h}_{{\boldsymbol{\theta}},j}}/{\tau}}}{\sum\limits_{\ell\neq
i}e^{\mathbf{h}_{{\boldsymbol{\theta}},i}^{\top}\mathbf{h}_{{\boldsymbol{\theta}},\ell}/\tau}}\bigg{)}.$
(1)

Here, the scalar $\tau$ is a positive temperature hyper-parameter. This
parameter was introduced in the loss by [3] as they observed it can boost the
performance of the model by controlling the smoothness of the loss.

By minimizing the SC loss, we favor parameters ${\boldsymbol{\theta}}$ that
pull the examples belonging to the same class closer while simultaneously
pushing the samples from different classes away from each other. Training a
model with this loss usually involves two stages: first we learn the
embeddings $\mathbf{h}_{\boldsymbol{\theta}}(\cdot)$ by minimizing the SC
loss, and second, we train a (simple) classifier separately on top of the
learned representations. In this work, we focus on the first representation
learning stage.

######  Remark 1.

In the definition of the SC loss, introduced by [3], the embeddings
$\mathbf{h}_{\boldsymbol{\theta}}(\cdot)$ are normalized to the unit sphere.
In other words, the loss is a function of the cosine similarity of the
embeddings learned by the deep-net. Alternatively, we can assume the deep-net
at the final layer is followed by a normalization layer that maps the
embeddings to the unit sphere so that
$\lVert\mathbf{h}_{\boldsymbol{\theta}}(\mathbf{x}_{i})\rVert_{2}=1$.

###  II-A Unconstrained Features Model (UFM)

In order to develop a theory for the training dynamics of deep-nets, we ought
to capture the interplay between several non-linear hidden layers of the
network. This makes the theoretical analysis of deep-networks challenging and
motivates us to simplify the interactions between layers. UFM [12, 5, 7]
serves as an abstract model that gives (partial) theoretical justification of
the discovery made by [4]. Focusing on the last layer of the network, UFM
relies on the power of over-parameterization, and assumes that large deep-nets
are expressive enough to (approximately) map any point in the input space to
any point in the embedding space. Hence, in this model, we assume deep-nets
can learn _unconstrained features_ and treat the last-layer embeddings as free
optimization parameters. In other words, we relax the dependence of the
embeddings $\mathbf{H}_{\boldsymbol{\theta}}$ on the network parameters
${\boldsymbol{\theta}}$ and optimize the problem directly over $\mathbf{H}$.
Thus, under UFM, our problem reduces to:

$\displaystyle\mathbf{H}^{*}\in\arg\min_{\mathbf{H}}\mathcal{L}_{\text{SC}}(\mathbf{H};\tau)~{}~{}\text{{subj.
to}}~{}\,\|\mathbf{h}_{i}\|^{2}_{2}=1,\,\forall i\in[n].$ (2)

With this simplification, we study the patterns appearing in large deep-nets,
restricting our attention to the interactions of the only element that the NC
property is concerned with: the last-layer embeddings. It is also important to
highlight that the objective of this optimization problem is still nonconvex
as the loss is computed over the non-linear interactions of embeddings, i.e.,
$\mathbf{H}^{\top}\mathbf{H}$.

######  Remark 2.

Throughout this paper, we use a slightly different terminology than the
Neural-collapse literature. We borrow the terminology from [21]: we use
_Neural-collapse_ (NC) particularly when referring to the collapse of the
embeddings, and (implicit) geometry when referring to the arrangement of the
last-layer feature-embeddings $\mathbf{H}$ (e.g., ETF in balanced case). More
formally, by NC, we mean the following:

######  Definition 1 (Neural-collapse (NC) property).

Consider the embeddings matrix $\mathbf{H}$. NC holds for $\mathbf{H}$ if
$\mathbf{h}_{i}=\mathbf{h}_{j}$, $\forall\,i,j:y_{i}=y_{j}$.

###  II-B Practices in Contrastive Learning

Contrastive learning involves several heuristics for achieving optimal
performance in practice. We choose to overlook some of these common practices
to simplify the analysis. We elaborate on these assumptions in this section.
While not being fully consistent with the practice, we believe this
preliminary analysis can provide useful insights for future works.

Computational cost. Due to the pair-wise comparison of the embeddings in the
loss function, SC loss has a high computational cost when computed over the
whole training set as in (1). As a result, in practice, the loss is
approximated over random batches chosen from the training set, instead of the
whole set $\mathcal{S}$. However, in our theory we consider the full-batch
scenario (1).

Projection head. At the training stage, the SC loss is not directly computed
on the embeddings. In fact, the embeddings are passed through a projection
layer (which can be as simple as a single-layer or shallow MLP), and the loss
is minimized on the projected embeddings. This projection layer is discarded
at test time, as it is empirically shown that using the pre-projection
embeddings yield better performance for downstream tasks. In our analysis, we
ignore the projection head of the network, and focus on studying the
embeddings on which the loss is directly computed. This is similar to the
analysis performed by previous works [7, 5, 30].

Embedding constraints. As discussed in Remark 1, the SC loss is computed over
unit norm embeddings. Since, constraining the norms to the sphere yields a
non-convex feasibility set, we relax the norm constraints to a ball of radius
1. On the other hand, we can view the temperature parameter $\tau$ as a
scaling on the embeddings $\mathbf{h}_{i}$. Specifically, it is easy to see
that
$\mathcal{L}_{\text{SC}}(\mathbf{H};\tau)=\mathcal{L}_{\text{SC}}(\widetilde{\mathbf{H}};1)$
where $\widetilde{\mathbf{H}}=\mathbf{H}/\sqrt{\tau}$ and as a result
$\lVert\widetilde{\mathbf{h}}_{i}\rVert^{2}_{2}=1/\tau$ for all $i\in[n]$. In
other words, after relaxing the constraints, we study the UFM formulated as
follows,

$\displaystyle\mathbf{H}^{*}\in\arg\min_{\mathbf{H}}\mathcal{L}_{\text{SC}}(\mathbf{H})~{}~{}\text{{subj.
to}}~{}\,\|\mathbf{h}_{i}\|^{2}_{2}\leq\frac{1}{\tau},\,\forall i\in[n],$ (3)

where
$\mathcal{L}_{\text{SC}}(\mathbf{H}):=\mathcal{L}_{\text{SC}}(\mathbf{H};\tau=1)$.
Here we recall that, the minimization is over the _unconstrained_ embeddings
$\mathbf{H}$ that do not depend on the network parameters
${\boldsymbol{\theta}}$. Although we simplified the problem to deal with a
convex feasibility set, the problem (3) still has a non-convex objective
function.

##  III Results

In this section, we perform an analysis of the local minimizers of the SC loss
with the UFM (3). As part of the analysis, we rely on the characterization of
a tight convex relaxation of (3) which we use later for taking a closer look
at the structure of the global solutions. We first start by stating a general
property of the local optimal points of (3).

###  III-A NC Holds at Local Optimal Solutions

Let $n_{\text{max}}=\max_{c\in[k]}n_{c}$ be the size of the largest class, and
recall the necessary condition for local optimality in a general optimization
with convex constraints.

######  Proposition 1 (Necessary stationarity condition [32, Chapter 2]).

Consider the optimization problem
$\min_{\mathbf{x}\in\mathcal{C}}f(\mathbf{x})$ over a convex set
$\mathcal{C}$. Let $\widehat{\mathbf{x}}\in\mathcal{C}$ be a local minimum.
Then,

$\displaystyle\nabla
f(\widehat{\mathbf{x}})^{\top}(\mathbf{x}-\widehat{\mathbf{x}})\geq 0,$
$\displaystyle\quad\forall\mathbf{x}\in\mathcal{C}.$ (4)

######  Lemma 1.

Assume $\tau>{2}/{\log({(n-1)}/{(n_{\text{\emph{max}}}-1)})}$. Let
$\widehat{\mathbf{H}}$ be locally optimal in the UFM problem (3). The NC
property (Definition 1) holds at $\widehat{\mathbf{H}}$.

Lemma 1 shows all the feasible points that are locally optimal have a low-rank
structure and satisfy the collapse property. Thus, similar to the case of CE
[12, 15], it follows that at the global solutions, the embeddings collapse to
their class-means.

The proof of this lemma simply follows by showing that condition (4) does not
hold for a feasible $\widehat{\mathbf{H}}$ that does not satisfy the NC
property (recall that the feasible set in (3) is convex). Specifically,
suppose $y_{1}=y_{2}$ and
$\widehat{\mathbf{h}}_{1}\neq\widehat{\mathbf{h}}_{2}$. Then, define
$\mathbf{H}$ by swapping the first two columns of $\widehat{\mathbf{H}}$,
i.e.,
$\mathbf{H}=[\widehat{\mathbf{h}}_{2},\widehat{\mathbf{h}}_{1},\widehat{\mathbf{h}}_{3},\cdots,\widehat{\mathbf{h}}_{n}]$.
It is then possible to show that if the condition on $\tau$ holds,
$\nabla\mathcal{L}_{\text{SC}}(\mathbf{H})^{\top}(\mathbf{H}-\widehat{\mathbf{H}})<0$,
which contradicts the necessary condition of local optimality (4). The rest of
our results in this section, rely on Lemma 1. Thus, in what follows, we assume

$\displaystyle\tau>{2}/{\log\big{(}\frac{n-1}{n_{\text{{max}}}-1}\big{)}}.$

For balanced data, $n_{\text{max}}=n/k$ and the condition approximately
becomes $\tau>2/\log(k)$ for $n>>k$, which is not restrictive in practical
settings. For brevity, we do not re-state this condition in the next sections.
We finally note that the condition on $\tau$ is a sufficient requirement but
not a necessary one. We conjecture that this condition can be relaxed.

###  III-B UFM: Landscape and Optimality Conditions

Here, we study the local and global optimality conditions for the UFM under
the SC loss in (3). Since the problem is non-convex, it is not obvious whether
(3) has a unique solution or if it has a landscape free from spurious local
solutions (which are not globally optimal). In fact, it is easy to see that
the global solution is not unique, since rotating the embeddings by an
orthonormal matrix $\mathbf{R}$, does not change the value of the loss
function, i.e.,
$\mathcal{L}_{\text{SC}}(\mathbf{R}^{\top}\mathbf{H})=\mathcal{L}_{\text{SC}}(\mathbf{H})$.
The next theorem characterizes the local and global solutions of (3).

######  Theorem 1 (UFM landscape with SC loss).

Assume the feature dimension exceeds the number of classes, $d>k$. Then,
(i) all the local solutions of the UFM (3) are global optima.
(ii) if $\mathbf{H}^{*}_{1}$ and $\mathbf{H}^{*}_{2}$ are global minimizers,
${\mathbf{H}^{*}_{1}}^{\top}\mathbf{H}^{*}_{1}$=${\mathbf{H}^{*}_{2}}^{\top}\mathbf{H}^{*}_{2}$.

This theorem proves that although the global optimizer of the non-convex
problem (3) is not unique, it has a unique _implicit geometry_. Furthermore,
it ensures that the landscape of this problem has no non-global local
solutions. We will next discuss the proof sketch.

###  III-C Proof Sketch

The main idea in the proof is to relate the KKT points of the problem (3) to
the KKT points of its convex relaxation. We start by formalizing the convex
relaxation.

Convex relaxation. To define the convex relaxation, we note that the SC loss
is in fact a convex function of the Gram matrix
$\mathbf{G}:=\mathbf{H}^{\top}\mathbf{H}$.

$\displaystyle\mathcal{L}_{\text{SC}}(\mathbf{H})=\widehat{\mathcal{L}}(\mathbf{G})$
$\displaystyle:={\frac{1}{n}}\sum_{i\in[n]}\frac{-1}{n_{y_{i}}-1}\sum_{\begin{subarray}{c}j\neq
i\\\
y_{j}=y_{i}\end{subarray}}\log\bigg{(}\frac{e^{\mathbf{G}_{i,j}}}{\sum\limits_{\ell\neq
i}e^{\mathbf{G}_{i,\ell}}}\bigg{)}.$

To make the convex loss function symmetric, we define
$\mathcal{L}_{\text{cvx}}(\mathbf{G}):=\frac{1}{2}\Big{(}\widehat{\mathcal{L}}(\mathbf{G})+\widehat{\mathcal{L}}(\mathbf{G}^{\top})\Big{)}$
and we formulate the relaxed convex problem with the symmetrized objective
function as follows.

$\displaystyle\mathbf{G}^{*}\in\arg\min_{\mathbf{G}}\mathcal{L}_{\text{cvx}}(\mathbf{G}),~{}\text{{subj.
to}}~{}~{}\mathbf{G}\succcurlyeq
0,~{}\mathbf{G}_{i,i}\leq\frac{1}{\tau},\,\forall i\in[n].$ (5)

This convex program satisfies the Slater’s conditions. Hence, strong duality
holds and any KKT point of (5) specifies a global solution.

Proof of Theorem 1. Suppose $\widehat{\mathbf{H}}$ is a local optima. Thus, it
satisfies the first order and second order necessary condition for local
optimality for constrained problems [33, Theorems 12.1 and 12.5]. In
particular, consider the Lagrangian function

$\text{Lag}(\mathbf{H},\boldsymbol{\lambda})=\mathcal{L}_{\text{SC}}(\mathbf{H})+\sum_{i\in[n]}\boldsymbol{\lambda}_{i}(\mathbf{h}_{i}^{\top}\mathbf{h}_{i}-{1}/{\tau}),$

where $\boldsymbol{\lambda}\in\mathds{R}^{n}$. By the first-order conditions,
there exists a dual variable $\widehat{\boldsymbol{\lambda}}\in\mathds{R}^{n}$
such that $(\widehat{\mathbf{H}},\widehat{\boldsymbol{\lambda}})$ are the KKT
points of (3). Specifically,
$\nabla_{\mathbf{H}}\text{Lag}(\widehat{\mathbf{H}},\widehat{\boldsymbol{\lambda}})=0$,
i.e.,

$\displaystyle
2\widehat{\mathbf{H}}(\nabla_{\mathbf{G}}\mathcal{L}_{\text{cvx}}(\widehat{\mathbf{H}}^{\top}\widehat{\mathbf{H}})+\operatorname{diag}(\widehat{\boldsymbol{\lambda}}))=0$

By the second-order conditions, the Hessian of the Lagrangian should have
positive curvature in every direction $\mathbf{\Delta}_{d\times
n}=[\mathbf{d}_{1},...,\mathbf{d}_{n}]$ such that

$\displaystyle\mathbf{d}_{i}^{\top}\widehat{\mathbf{h}}_{i}=0,\quad\text{if
}\lVert\widehat{\mathbf{h}}_{i}\rVert_{2}^{2}=\frac{1}{\tau},\,\widehat{\lambda}_{i}>0,$
$\displaystyle\mathbf{d}_{i}^{\top}\widehat{\mathbf{h}}_{i}\geq
0,\quad\text{if
}\lVert\widehat{\mathbf{h}}_{i}\rVert_{2}^{2}=\frac{1}{\tau},\,\widehat{\lambda}_{i}=0,$

Suppose
$\mathbf{B}:=\nabla_{\mathbf{G}}\mathcal{L}_{\text{cvx}}(\widehat{\mathbf{H}}^{\top}\widehat{\mathbf{H}})+\operatorname{diag}(\widehat{\boldsymbol{\lambda}})$
has a negative eigen-value, i.e., there exists $\mathbf{u}\in\mathds{R}^{n}$
such that $\mathbf{u}^{\top}\mathbf{B}\mathbf{u}<0$. On the other hand, by
Lemma 1, the NC property holds at $\widehat{\mathbf{H}}$ and
$\operatorname{rank}(\widehat{\mathbf{H}})\leq k<d$. This implies that for
some $\mathbf{v}\in\mathds{R}^{d}$, $\widehat{\mathbf{H}}^{\top}\mathbf{v}=0$.
As a result, it is possible to show that The Hessian of the Lagrangian
$\nabla^{2}_{\mathbf{H}}\text{Lag}(\widehat{\mathbf{H}},\widehat{\boldsymbol{\lambda}})$
has a negative curvature in the direction
$\mathbf{\Delta}:=\mathbf{v}\mathbf{u}^{\top}$. This contradicts the second
order condition of local optimality [33, Theorems 12.5] since
$\mathbf{\Delta}^{\top}\widehat{\mathbf{H}}=0$, i.e.,
$\mathbf{d}_{i}^{\top}\widehat{\mathbf{h}}_{i}=0,\,\forall i\in[n]$.

Therefore, it is necessary for
$(\widehat{\mathbf{H}},\widehat{\boldsymbol{\lambda}})$ to satisfy,

$\nabla\mathcal{L}_{\text{cvx}}(\widehat{\mathbf{H}}^{\top}\widehat{\mathbf{H}})+\operatorname{diag}\big{(}\widehat{\boldsymbol{\lambda}}\big{)}\succcurlyeq
0.$

From here, it is straightforward to prove
$(\widehat{\mathbf{G}}:=\widehat{\mathbf{H}}^{\top}\widehat{\mathbf{H}},\widehat{\boldsymbol{\lambda}},\mathbf{B})$
is a KKT point of the convex problem (5). Equivalently, by strong duality,
$\widehat{\mathbf{G}}$ is a global optimizer. On the other hand, since (5) is
a relaxation of the original UFM (3), for the optimal solution
$\mathbf{H}^{*}$, we have,

$\mathcal{L}_{\text{SC}}(\widehat{\mathbf{H}})=\mathcal{L}_{\text{cvx}}(\widehat{\mathbf{G}})\leq\mathcal{L}_{\text{cvx}}({\mathbf{H}^{*}}^{\top}\mathbf{H}^{*})=\mathcal{L}_{\text{SC}}(\mathbf{H}^{*}).$
(6)

Therefore, $\widehat{\mathbf{H}}$ is a global optimum of (3), and the proof is
complete. This further shows the relaxation in (5) is tight.

######  Corollary 1.

Suppose $d>k$. Then, the convex program (5) is a tight relaxation of (3).

We can further show that the optimal solution of (5) is unique. We use this
useful result in the next section.

######  Lemma 2.

The convex UFM problem (5) has a unique minimizer.

For the proof of this lemma, we note two facts: 1) If
$\mathbf{G}-\operatorname{diag}(\mathbf{G})\propto\mathbf{1}_{n}\mathbf{1}_{n}^{\top}-\mathds{I}_{n}$,
$\mathbf{G}$ is not a global optima, and 2) the objective
$\mathcal{L}_{\text{cvx}}(\cdot)$ is strictly convex in any direction
$\mathbf{V}$ such that
$\mathbf{V}-\operatorname{diag}(\mathbf{V})\not\propto\mathbf{1}_{n}\mathbf{1}_{n}^{\top}-\mathds{I}_{n}.$

###  III-D Global Solutions

By Lemma 1, we know that the global solution of the UFM (3), as a first order
stationary point, has the NC property. That is, there exists
$\mathbf{M}^{*}_{d\times
k}=[\boldsymbol{\mu}^{*}_{1},...\boldsymbol{\mu}^{*}_{k}]$ such that
$\mathbf{h}^{*}_{i}=\boldsymbol{\mu}^{*}_{y_{i}}$. Thus, to find the
conditions of global optimality, we only need to find the $k$ optimal mean-
embedding vectors $\boldsymbol{\mu}^{*}_{c},\,c\in[k]$. To analyze the global
solutions, we restrict our attention to a specific training data distribution
defined as follows.

######  Definition 2 ($(R,\rho)$-STEP imbalanced data).

With $R\geq 1$ as the imbalance ratio $\rho\in(0,1)$ as the minority fraction,
the following holds: classes $c\in\\{1,\ldots,\overline{\rho}k\\}$ are
majority classes, all with the same sample size of $n_{c}=n_{\text{maj}}$ and
classes $c\in\\{\overline{\rho}k+1,\cdots,k\\}$ are minority classes, all with
the same sample size of $n_{c}=n_{\text{minor}}$, where
$n_{\operatorname{maj}}=Rn_{\operatorname{minor}}$.

Given the NC property at the optimal solution, in the $(R,\rho)$-STEP
imbalanced setting, we can use the symmetry in the size of the classes to even
further simplify the structure of the global solution. The following lemma
formalizes this argument.

######  Lemma 3.

Assume an $(R,\rho)$-STEP imbalanced setting with $k$ classes. Let
$\mathbf{H}^{*}$ be the global solution of (3). Then
$\mathbf{G}^{*}={\mathbf{H}^{*}}^{\top}\mathbf{H}^{*}$ is the unique optimizer
of the convex program (5). Furthermore, $\mathbf{G}^{*}$ has a block
structure: there exists scalars
$\alpha_{\text{\emph{maj/minor}}},\,\beta_{\text{\emph{maj/minor}}},\,\theta\in[{-1}/{\tau},{1}/{\tau}]$
such that,
$\mathbf{G}^{*}=\begin{bmatrix}\mathbf{G}^{*}_{1,1}&\mathbf{G}^{*}_{1,2}\\\
\mathbf{G}^{*}_{2,1}&\mathbf{G}^{*}_{2,2}\end{bmatrix},$ and

$\displaystyle\mathbf{G}^{*}_{1,1}$
$\displaystyle=\bigg{(}(\alpha_{\emph{maj}}-\beta_{\emph{maj}})\mathds{I}_{\overline{\rho}k}+\beta_{\emph{maj}}\mathbf{1}_{\overline{\rho}k}\mathbf{1}_{\overline{\rho}k}^{\top}\bigg{)}\otimes\mathbf{1}_{n_{\emph{maj}}}\mathbf{1}_{n_{\emph{maj}}}^{\top}$
$\displaystyle\mathbf{G}^{*}_{1,2}$
$\displaystyle=\theta\mathbf{1}_{\overline{\rho}kn_{\emph{maj}}}\mathbf{1}_{\rho
kn_{\emph{minor}}}^{\top}$ $\displaystyle\mathbf{G}^{*}_{2,1}$
$\displaystyle=\theta\mathbf{1}_{\rho
kn_{\emph{minor}}}\mathbf{1}_{\overline{\rho}kn_{\emph{maj}}}^{\top}$
$\displaystyle\mathbf{G}^{*}_{2,2}$
$\displaystyle=\bigg{(}(\alpha_{\emph{minor}}-\beta_{\emph{minor}})\mathds{I}_{\rho
k}+\beta_{\emph{minor}}\mathbf{1}_{\rho k}\mathbf{1}_{\rho
k}^{\top}\bigg{)}\otimes\mathbf{1}_{n_{\emph{minor}}}\mathbf{1}_{n_{\emph{minor}}}^{\top}$

This lemma follows from a simple symmetry argument that uses the fact that for
two classes with equal sizes, their corresponding (mean-)embeddings are
weighted similarly in the objective of problem (5):

######  Lemma 4.

Consider problem (5). If $n_{c_{1}}=n_{c_{2}}$ for $c_{1}\neq c_{2}\in[k]$,
then $\forall i,j,\ell\in[n]$, such that $y_{i}=c_{1},\,y_{j}=c_{2}$, and
$y_{\ell}\neq c_{1},c_{2}$, $\mathbf{G}^{*}_{i,\ell}=\mathbf{G}^{*}_{j,\ell}$.

Recall from Corollary 1, the relaxation (5) is tight, and finding
$\mathbf{G}^{*}$ characterizes the optimal $\mathbf{H}^{*}$ up to a rotation.
This lemma reduces the dimension of the original problem in the case of STEP
imbalanced data. In the specific case of balanced data ($n_{c}=n/k$), the
optimal solution reduces to ETF, as also previously shown [7].

######  Theorem 2.

Assume that the training set is balanced ($R=1$). The optimal solution
$\mathbf{H}^{*}$ of the UFM (3) follows an ETF. In other words, there exists
vectors $\boldsymbol{\mu}_{1}....\boldsymbol{\mu}_{k}$ such that for
$\mathbf{M}=[\boldsymbol{\mu}_{1},...\boldsymbol{\mu}_{k}]$ we have
$\mathbf{M}^{\top}\mathbf{M}\propto\mathds{I}_{k}-\frac{1}{k}\mathbf{1}_{k}\mathbf{1}_{k}^{\top}$
and $\mathbf{h}^{*}_{i}=\boldsymbol{\mu}_{y_{i}}$.

This result follows directly from Lemma 3. Specifically, in the balanced case,
$\alpha_{\text{maj}}=\alpha_{\text{minor}}$,
$\beta_{\text{maj}}=\beta_{\text{minor}}$, and the optimal $\mathbf{G}^{*}$
satisfies,

$\displaystyle\mathbf{G}^{*}=\left(\alpha-\beta\right)\mathds{I}_{n}+\left((\beta-\theta)\mathds{I}_{k}+\theta\mathds{J}_{k}\right)\otimes\mathds{J}_{(\frac{n}{k})},$

for some scalar $\alpha,\,\beta,\,\theta\in\mathds{R}$. On the other hand,
$\mathbf{G}^{*}$ is feasible if it is positive semi-definite and its diagonal
entries are less than $1/\tau$. Thus, we can show solving UFM (3) reduces to
optimizing a linear program as follows

$\displaystyle(\alpha^{*},\beta^{*},\theta^{*})=\arg\min_{\alpha,\beta,\theta}$
$\displaystyle\,\theta-\beta,\quad$ (7) sub. to
$\displaystyle\quad\frac{1}{\tau}-\alpha\geq 0,$
$\displaystyle\alpha-\beta\geq 0,$
$\displaystyle\alpha+\beta(\frac{n}{k}-1)-\theta\frac{n}{k}\geq 0,$
$\displaystyle\alpha+\beta(\frac{n}{k}-1)+\theta(n-\frac{n}{k})\geq 0.$

From above, we can see $\alpha^{*}=\beta^{*}=1/\tau$ and
$\theta^{*}=-1/(\tau(k-1))$, and ETF is the only solution. However, this is
not the case if the training set is imbalanced:

######  Proposition 2.

[22, Lemma D.2] If classes in the training set are not balanced, the global
solution of (3) is not an ETF.

Overall, in balanced scenarios, as also previously shown [7, 5], SC learns the
same embeddings as the CE loss. Similarly, the optimal solutions of the SC
loss change with imbalances. We leave further investigations for comparing the
solutions in the imbalanced case for CE and SC loss for future work.

##  IV Discussion

In this paper, complementing the claims and observations in [7, 31], we show
that the SC loss has no spurious local optimal solutions under the UFM despite
being non-convex. Although we leave the characterization of global solutions
for general training distributions to future works, we exploit how the convex
relaxation of the problem can be used for uncovering the properties of the
unique global minimizer. We believe studying the SC loss is an intermediary
step for expanding our understanding of embeddings geometry to the less-
understood self-supervised setting. While our focus is on discovering the
local/global optimal embeddings geometries in the supervised contrastive
learning, it is interesting to study the optimization dynamics analytically as
a future direction. Previous works have empirically investigated the degree of
convergence of the UFM and benchmark deep models to the optimal geometries for
both the CE [4, 15, 20] and the SC [7, 22] loss. Based on these reports, the
training setup, such as the imbalance ratio or the loss hyper-parameters, play
a significant role on the degree of convergence to the theoretical prediction
by UFM. We hypothesize that the training setup can lead to more complex loss
landscape, but gradient descent eventually leads to the global solutions
asymptotically in the number of epochs. This conjecture remains to be further
investigated and formalized.

## References

  * [1] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in _International conference on machine learning_. PMLR, 2020, pp. 1597–1607.
  * [2] Y. Tian, D. Krishnan, and P. Isola, “Contrastive multiview coding,” in _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XI 16_. Springer, 2020, pp. 776–794.
  * [3] P. Khosla, P. Teterwak, C. Wang, A. Sarna, Y. Tian, P. Isola, A. Maschinot, C. Liu, and D. Krishnan, “Supervised contrastive learning,” _Advances in neural information processing systems_ , vol. 33, pp. 18 661–18 673, 2020.
  * [4] V. Papyan, X. Han, and D. L. Donoho, “Prevalence of neural collapse during the terminal phase of deep learning training,” _Proceedings of the National Academy of Sciences_ , vol. 117, no. 40, pp. 24 652–24 663, 2020.
  * [5] C. Fang, H. He, Q. Long, and W. J. Su, “Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training,” _Proceedings of the National Academy of Sciences_ , vol. 118, no. 43, 2021.
  * [6] T. Galanti, A. György, and M. Hutter, “On the role of neural collapse in transfer learning,” _arXiv preprint arXiv:2112.15121_ , 2021.
  * [7] F. Graf, C. Hofer, M. Niethammer, and R. Kwitt, “Dissecting supervised constrastive learning,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 3821–3830.
  * [8] X. Han, V. Papyan, and D. L. Donoho, “Neural collapse under mse loss: Proximity to and dynamics on the central path,” in _International Conference on Learning Representations_ , 2021.
  * [9] L. Hui, M. Belkin, and P. Nakkiran, “Limitations of neural collapse for understanding generalization in deep learning,” _arXiv preprint arXiv:2202.08384_ , 2022.
  * [10] W. Ji, Y. Lu, Y. Zhang, Z. Deng, and W. J. Su, “An unconstrained layer-peeled perspective on neural collapse,” _arXiv preprint arXiv:2110.02796_ , 2021.
  * [11] J. Lu and S. Steinerberger, “Neural collapse with cross-entropy loss,” _arXiv preprint arXiv:2012.08465_ , 2020.
  * [12] D. G. Mixon, H. Parshall, and J. Pi, “Neural collapse with unconstrained features,” _arXiv preprint arXiv:2011.11619_ , 2020.
  * [13] T. Tirer and J. Bruna, “Extended unconstrained features model for exploring deep neural collapse,” _arXiv preprint arXiv:2202.08087_ , 2022.
  * [14] L. Xie, Y. Yang, D. Cai, D. Tao, and X. He, “Neural collapse inspired attraction-repulsion-balanced loss for imbalanced learning,” _arXiv preprint arXiv:2204.08735_ , 2022.
  * [15] Z. Zhu, T. Ding, J. Zhou, X. Li, C. You, J. Sulam, and Q. Qu, “A geometric analysis of neural collapse with unconstrained features,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [16] J. Zhou, X. Li, T. Ding, C. You, Q. Qu, and Z. Zhu, “On the optimization landscape of neural collapse under mse loss: Global optimality with unconstrained features,” _arXiv preprint arXiv:2203.01238_ , 2022.
  * [17] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro, “The implicit bias of gradient descent on separable data,” _The Journal of Machine Learning Research_ , vol. 19, no. 1, pp. 2822–2878, 2018.
  * [18] Z. Ji and M. Telgarsky, “Risk and parameter convergence of logistic regression,” _arXiv preprint arXiv:1803.07300_ , 2018.
  * [19] K. Lyu and J. Li, “Gradient descent maximizes the margin of homogeneous neural networks,” _arXiv preprint arXiv:1906.05890_ , 2019.
  * [20] C. Thrampoulidis, G. R. Kini, V. Vakilian, and T. Behnia, “Imbalance trouble: Revisiting neural-collapse geometry,” _arXiv preprint arXiv:2208.05512_ , 2022.
  * [21] T. Behnia, G. R. Kini, V. Vakilian, and C. Thrampoulidis, “On the implicit geometry of cross-entropy parameterizations for label-imbalanced data,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2023, pp. 10 815–10 838.
  * [22] G. R. Kini, V. Vakilian, T. Behnia, J. Gill, and C. Thrampoulidis, “Supervised-contrastive loss learns orthogonal frames and batching matters,” _arXiv preprint arXiv:2306.07960_ , 2023.
  * [23] J. Zhou, C. You, X. Li, K. Liu, S. Liu, Q. Qu, and Z. Zhu, “Are all losses created equal: A neural collapse perspective,” _arXiv preprint arXiv:2210.02192_ , 2022.
  * [24] T. Galanti, A. György, and M. Hutter, “Generalization bounds for transfer learning with pretrained classifiers,” _arXiv preprint arXiv:2212.12532_ , 2022.
  * [25] W. Jitkrittum, A. K. Menon, A. S. Rawat, and S. Kumar, “Elm: Embedding and logit margins for long-tail learning,” _arXiv preprint arXiv:2204.13208_ , 2022.
  * [26] D. Samuel and G. Chechik, “Distributional robustness loss for long-tail learning,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 9495–9504.
  * [27] B. Gunel, J. Du, A. Conneau, and V. Stoyanov, “Supervised contrastive learning for pre-trained language model fine-tuning,” _arXiv preprint arXiv:2011.01403_ , 2020.
  * [28] B. Kang, Y. Li, S. Xie, Z. Yuan, and J. Feng, “Exploring balanced feature spaces for representation learning,” in _International Conference on Learning Representations_ , 2021.
  * [29] T. Li, P. Cao, Y. Yuan, L. Fan, Y. Yang, R. S. Feris, P. Indyk, and D. Katabi, “Targeted supervised contrastive learning for long-tailed recognition,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 6918–6928.
  * [30] T. Wang and P. Isola, “Understanding contrastive representation learning through alignment and uniformity on the hypersphere,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 9929–9939.
  * [31] C. Yaras, P. Wang, Z. Zhu, L. Balzano, and Q. Qu, “Neural collapse with normalized features: A geometric analysis over the riemannian manifold,” _arXiv preprint arXiv:2209.09211_ , 2022.
  * [32] D. P. Bertsekas, “Nonlinear programming,” 1999.
  * [33] J. Nocedal and S. J. Wright, _Numerical optimization_. Springer, 1999.

##  Appendix A Proof of Lemma 1

######  Lemma 5 (Gradient of SC).

For a given matrix $\mathbf{H}_{d\times n}$, let
$\mathbf{G}=\mathbf{H}^{\top}\mathbf{H}$ and define $\mathbf{P}_{n\times n}$
and $\mathbf{Q}_{n\times n}$ as follows,

$\displaystyle\mathbf{P}_{i,j}$ $\displaystyle=\begin{cases}0,&i=j\\\
{\exp{(\mathbf{G}_{i,j}})}/{\sum_{\ell\neq
i}\exp(\mathbf{G}_{i,\ell})}&\text{\emph{o.w.}}\end{cases}$ (8)
$\displaystyle\mathbf{Q}_{i,j}$
$\displaystyle=\begin{cases}0,&i=j\,\text{\emph{ or }}\,y_{i}\neq y_{j}\\\
1/(n_{c}-1)&i\neq j,~{}y_{i}=y_{j}=c\end{cases}$ (9)

Then, the gradient of the SC loss $\mathcal{L}_{\text{SC}}(\cdot)$ and the
convex SC loss $\mathcal{L}_{\text{cvx}}(\cdot)$ are as follows,

$\displaystyle\nabla_{\mathbf{H}}\mathcal{L}_{\text{\emph{SC}}}(\mathbf{H})$
$\displaystyle=\mathbf{H}\big{(}\mathbf{P}+\mathbf{P}^{\top})-2\mathbf{H}\mathbf{Q},$
(10)
$\displaystyle\nabla_{\mathbf{G}}\mathcal{L}_{\text{\emph{cvx}}}(\mathbf{G})$
$\displaystyle=\frac{1}{2}\big{(}\mathbf{P}+\mathbf{P}^{\top})-\mathbf{Q}.$
(11)

###### Proof.

Here, we prove (10). The proof of (11) can be derived similarly. First, we
simplify the expression of the loss.

$\displaystyle\mathcal{L}_{\text{SC}}(\mathbf{H})$
$\displaystyle=\sum_{i\in[n]}\frac{1}{n_{y_{i}}-1}\sum_{\begin{subarray}{c}j\neq
i\\\
y_{j}=y_{i}\end{subarray}}-\log\bigg{(}\frac{\exp(\mathbf{h}_{i}^{\top}\mathbf{h}_{j})}{\sum_{\ell\neq
i}\exp(\mathbf{h}_{i}^{\top}\mathbf{h}_{\ell})}\bigg{)}$
$\displaystyle=\sum_{i\in[n]}\log\bigg{(}{\sum_{\ell\neq
i}\exp(\mathbf{h}_{i}^{\top}\mathbf{h}_{\ell})}\bigg{)}-\sum_{i\in[n]}\frac{1}{n_{y_{i}}-1}\sum_{\begin{subarray}{c}j\neq
i\\\ y_{j}=y_{i}\end{subarray}}\mathbf{h}_{i}^{\top}\mathbf{h}_{j}.$

Now we can compute the gradient with respect to each column $\mathbf{h}_{i}$
as follows,

$\displaystyle\frac{\partial\mathcal{L}_{\text{SC}}(\mathbf{H})}{\partial\mathbf{h}_{i}}$
$\displaystyle=\frac{{\sum_{\ell\neq
i}\mathbf{h}_{\ell}\exp(\mathbf{h}_{i}^{\top}\mathbf{h}_{\ell})}}{{\sum_{\ell\neq
i}\exp(\mathbf{h}_{i}^{\top}\mathbf{h}_{\ell})}}+\sum_{j\neq
i}\frac{{\mathbf{h}_{j}\exp(\mathbf{h}_{j}^{\top}\mathbf{h}_{i})}}{{\sum_{\ell\neq
j}\exp(\mathbf{h}_{j}^{\top}\mathbf{h}_{\ell})}}-\frac{2}{n_{y_{i}}-1}\sum_{\begin{subarray}{c}j\neq
i\\\ y_{j}=y_{i}\end{subarray}}\mathbf{h}_{j}$ $\displaystyle=\sum_{j\neq
i}\mathbf{h}_{j}\mathbf{P}_{i,j}+\sum_{j\neq
i}\mathbf{h}_{j}\mathbf{P}_{j,i}-\frac{2}{n_{y_{i}}-1}\sum_{\begin{subarray}{c}j\neq
i\\\ y_{j}=y_{i}\end{subarray}}\mathbf{h}_{j}$
$\displaystyle=\sum_{j\in[n]}\mathbf{h}_{j}(\mathbf{P}_{i,j}+\mathbf{P}_{j,i})-\sum_{\begin{subarray}{c}j\neq
i\\\ y_{j}=y_{i}\end{subarray}}\mathbf{h}_{j}\mathbf{Q}_{i,j}$
$\displaystyle=2\mathbf{H}(\mathbf{p}_{i}+{\mathbf{p}^{i}})-2\mathbf{H}\mathbf{q}_{i},$

where ${\mathbf{p}^{i}}$ is the $i$-th row of $\mathbf{P}$, and
$\mathbf{p}_{i},\,\mathbf{q}_{i}$ are the $i$-th column of $\mathbf{P}$ and
$\mathbf{Q}$ respectively. ∎

Proof of Lemma 1. Let $\mathcal{C}=\\{\mathbf{H}\in\mathds{R}^{d\times
n}:\lVert\mathbf{h}_{i}\rVert^{2}\leq\frac{1}{\tau}\\}$ be the convex feasible
set, and suppose ${\mathbf{H}}\in\mathcal{C}$ is a feasible point that does
not satisfy the NC property. Without loss of generality, we assume
$y_{1}=y_{2}=1$ and ${\mathbf{h}}_{1}\neq{\mathbf{h}}_{2}$. Define
$\widehat{\mathbf{H}}=[{\mathbf{h}}_{2},{\mathbf{h}}_{1},{\mathbf{h}}_{3},...,{\mathbf{h}}_{n}]$
by exchanging the first and second column of ${\mathbf{H}}$. By the assumption
$\widehat{\mathbf{H}}\neq{\mathbf{H}}$ and
$\widehat{\mathbf{H}}-{\mathbf{H}}=[{\mathbf{h}}_{2}-{\mathbf{h}}_{1},-({\mathbf{h}}_{2}-{\mathbf{h}}_{1}),0,...,0]$.
Clearly, $\widehat{\mathbf{H}}$ remains feasible in the problem. We will show
that
$f(\mathbf{H}):=\langle\nabla_{\mathbf{H}}\mathcal{L}_{\text{SC}}({\mathbf{H}}),\,\widehat{\mathbf{H}}-{\mathbf{H}}\rangle<0.$
Recall the gradient of the SC loss from Lemma 5, and define
$\mathbf{G}:=\mathbf{H}^{\top}\mathbf{H}$.

$\displaystyle f(\mathbf{H})$
$\displaystyle=\langle({\mathbf{h}}_{2}-{\mathbf{h}}_{1}),\frac{\partial\mathcal{L}_{\text{SC}}({\mathbf{H}})}{\partial{\mathbf{h}}_{1}}-\frac{\partial\mathcal{L}_{\text{SC}}({\mathbf{H}})}{\partial{\mathbf{h}}_{2}}\rangle$
$\displaystyle=({\mathbf{h}}_{2}-{\mathbf{h}}_{1})^{\top}\Big{(}\sum_{j\in[n]}{\mathbf{h}}_{j}(\mathbf{P}_{1,j}+\mathbf{P}_{j,1}-\mathbf{P}_{2,j}-\mathbf{P}_{j,2})+\frac{2}{n_{1}-1}({\mathbf{h}}_{1}-{\mathbf{h}}_{2})\Big{)}$
$\displaystyle=\sum_{j\in[n]}({\mathbf{G}}_{2,j}-{\mathbf{G}}_{1,j})(\mathbf{P}_{1,j}+\mathbf{P}_{j,1}-\mathbf{P}_{2,j}-\mathbf{P}_{j,2})-\frac{2}{n_{1}-1}\lVert{\mathbf{h}}_{1}-{\mathbf{h}}_{2}\rVert_{2}^{2},$
$\displaystyle=\sum_{j\neq
1,2}({\mathbf{G}}_{2,j}-{\mathbf{G}}_{1,j})(\mathbf{P}_{1,j}+\mathbf{P}_{j,1}-\mathbf{P}_{2,j}-\mathbf{P}_{j,2})+(\mathbf{P}_{1,2}+\mathbf{P}_{2,1}-\frac{2}{n_{1}-1})\lVert{\mathbf{h}}_{1}-{\mathbf{h}}_{2}\rVert_{2}^{2},$

Define,

$\displaystyle\alpha_{1}$ $\displaystyle=\sum_{j\neq
1,2}({\mathbf{G}}_{2,j}-{\mathbf{G}}_{1,j})(\mathbf{P}_{1,j}-\mathbf{P}_{2,j})$
$\displaystyle\alpha_{2}$ $\displaystyle=\sum_{j\neq
1,2}({\mathbf{G}}_{2,j}-{\mathbf{G}}_{1,j})(\mathbf{P}_{j,1}-\mathbf{P}_{j,2})=\sum_{j\neq
1,2}({\mathbf{G}}_{j,2}-{\mathbf{G}}_{j,1})(\mathbf{P}_{j,1}-\mathbf{P}_{j,2})$
$\displaystyle\alpha_{3}$
$\displaystyle=(\mathbf{P}_{1,2}+\mathbf{P}_{2,1}-\frac{2}{n_{1}-1})\lVert{\mathbf{h}}_{1}-{\mathbf{h}}_{2}\rVert_{2}^{2}.$

Then, $f(\mathbf{H}_{1})=\alpha_{1}+\alpha_{2}+\alpha_{3}$. We will show if
$\tau$ is large enough, $\alpha_{1},\alpha_{2}\leq 0$ and $\alpha_{3}<0$. We
start by $\alpha_{1}$:

$\displaystyle\alpha_{1}$ $\displaystyle=\sum_{j\neq
1,2}({\mathbf{G}}_{2,j}-{\mathbf{G}}_{1,j})(\mathbf{P}_{1,j}-\mathbf{P}_{2,j})$
$\displaystyle=\sum_{j\neq
1,2}({\mathbf{G}}_{2,j}-{\mathbf{G}}_{1,j})\Bigg{(}\frac{\exp({\mathbf{G}}_{1,j})}{\sum_{\ell\neq
1}\exp({\mathbf{G}}_{1,\ell})}-\frac{\exp({\mathbf{G}}_{2,j})}{\sum_{\ell\neq
2}\exp({\mathbf{G}}_{2,\ell})}\Bigg{)}$ $\displaystyle=\frac{\sum_{j\neq
1,2}({\mathbf{G}}_{2,j}-{\mathbf{G}}_{1,j})\bigg{(}\exp({\mathbf{G}}_{1,j}){\sum_{\ell\neq
2}\exp({\mathbf{G}}_{2,\ell})}-\exp({\mathbf{G}}_{2,j}){\sum_{\ell\neq
1}\exp({\mathbf{G}}_{1,\ell})}\bigg{)}}{\bigg{(}{\sum_{\ell\neq
1}\exp({\mathbf{G}}_{1,\ell})}\bigg{)}\bigg{(}{\sum_{\ell\neq
2}\exp({\mathbf{G}}_{2,\ell})}\bigg{)}}=:\frac{\beta_{1}}{\beta_{2}}$

Since the exponential function is monotonic, we have

$\displaystyle\beta_{1}$ $\displaystyle=\exp(\mathbf{G}_{1,2})\sum_{j\neq
1,2}(\mathbf{G}_{2,j}-\mathbf{G}_{1,j})\Big{(}\exp(\mathbf{G}_{1,j})-\exp(\mathbf{G}_{2,i})\Big{)}$
$\displaystyle\quad+\sum_{\begin{subarray}{c}j\neq 1,2\\\ \ell\neq
1,2\end{subarray}}((\mathbf{G}_{2,j}+\mathbf{G}_{1,\ell})-(\mathbf{G}_{2,\ell}+\mathbf{G}_{1,j}))\Big{(}\exp(\mathbf{G}_{2,\ell}+\mathbf{G}_{1,j})-\exp(\mathbf{G}_{2,j}+\mathbf{G}_{1,\ell})\Big{)}\leq
0.$

Thus $\alpha_{1}\leq 0$. For $\alpha_{2}$, similarly with the monotonicity of
the exponential function it is straightforward to show $\alpha_{2}\leq 0$. It
remains to show $\alpha_{3}<0$. Since $\lVert\mathbf{h}_{i}\rVert_{2}^{2}\leq
1/\tau$, for all $i,j\in[n]$, $-1/\tau\leq\mathbf{G}_{i,j}\leq 1/\tau$. Thus,
for $\mathbf{P}_{1,2}$ we have

$\displaystyle\mathbf{P}_{1,2}\leq\frac{\exp(1/\tau)}{(n-1)\exp(-1/\tau)}.$

Now, suppose the condition on $\tau$ holds. Then,

$\displaystyle\tau>\frac{2}{\log(\frac{n-1}{n_{\text{max}}-1})}\geq\frac{2}{\log(\frac{n-1}{n_{1}-1})}\quad\implies\quad\frac{1}{n_{1}-1}>\frac{\exp(1/\tau)}{(n-1)\exp(-1/\tau)}\geq\mathbf{P}_{1,2}$

We can show the above inequality similarly holds for $\mathbf{P}_{2,1}$. Thus,

$\displaystyle\mathbf{P}_{1,2}+\mathbf{P}_{2,1}-\frac{2}{n_{1}-1}<0\quad\implies\quad\alpha_{3}<0,$

and $f(\mathbf{H})<0$. This contradicts the first-order necessary condition
for local optimality (4). ∎

##  Appendix B Proof of Lemma 2

######  Lemma 6 (Strict-convexity of SC loss).

For the convex SC loss $\mathcal{L}_{\text{cvx}}(\cdot)$, we have,

$\displaystyle\mathcal{L}_{\text{\emph{cvx}}}(\mathbf{G}+\mathbf{V})>\mathcal{L}_{\text{\emph{cvx}}}(\mathbf{G})+\operatorname{tr}\big{(}\mathbf{V}^{\top}\nabla\mathcal{L}_{\text{\emph{cvx}}}(\mathbf{G})\big{)},\quad\text{if}\quad\mathbf{V}-\text{\emph{diag}}(\mathbf{V})\not\propto\mathbf{1}_{n}\mathbf{1}_{n}^{\top}-\mathds{I}_{n},$
(12)

where $\text{\emph{diag}}(\mathbf{V})\in\mathds{R}^{n\times n}$ is a diagonal
matrix whose diagonal entries are the same as $\mathbf{V}$. In other words,
the loss is strictly-convex in any direction satisfying the condition in (12).

###### Proof.

For the vector $\mathbf{g}\in\mathds{R}^{n}$, define
$f_{ij}(\mathbf{g}):=\log\big{(}\sum_{\ell\neq
i}e^{-\mathbf{g}_{j}+\mathbf{g}_{\ell}}\big{)}$ and let the rows and columns
of $\mathbf{G}$ be defined as,

$\mathbf{G}=\begin{bmatrix}\mathbf{g}_{1},&\cdots,&\mathbf{g}_{n}\end{bmatrix}=\begin{bmatrix}{\mathbf{g}^{1}},&\cdots,&{\mathbf{g}^{n}}\end{bmatrix}^{\top}.$

Then, we can rewrite the loss function as follows,

$\displaystyle\mathcal{L}_{\text{{cvx}}}(\mathbf{G})=\frac{1}{2}\sum_{i\in[n]}\frac{1}{n_{y_{i}}-1}\sum_{\begin{subarray}{c}j\neq
i\\\
y_{j}=y_{i}\end{subarray}}(f_{ij}(\mathbf{g}_{i})+f_{ij}({\mathbf{g}^{i}})).$

Define $\mathbf{a}_{i}:=\mathbf{1}_{n}-\mathbf{e}_{i}$, and
$\mathbf{A}_{i}:=(\mathds{I}_{n}-\frac{1}{n-1}\mathbf{a}_{i}\mathbf{a}_{i}^{\top})$.
We first show that for $j\in[n]$, $f(\mathbf{g}):=f_{ij}(\mathbf{g})$ is
strictly convex in any direction $\mathbf{v}$ such that
$\mathbf{A}_{i}\mathbf{v}\neq 0$. That is, for such $\mathbf{v}$,
$f(\mathbf{g}+\mathbf{v})>f(\mathbf{g})+\mathbf{v}^{\top}\nabla
f(\mathbf{g})$.

From Taylor expansion,
$f(\mathbf{g}+\mathbf{v})=f(\mathbf{g})+\mathbf{v}^{\top}\nabla
f(\mathbf{g})+\frac{1}{2}\mathbf{v}^{\top}\nabla^{2}f(\mathbf{g}+t\mathbf{v})\mathbf{v},$
for some $t\in(0,1)$. We will show that
$\mathbf{v}^{\top}\nabla^{2}f(\mathbf{g})\mathbf{v}>0$ for all $\mathbf{g}$,
which together with the Taylor expansion proves the statement. It is easy to
verify that

$\nabla^{2}f(\mathbf{g})=\text{diag}(\mathbf{u})-\mathbf{u}\mathbf{u}^{\top},\quad\mathbf{u}_{r}=\begin{cases}\frac{e^{-\mathbf{g}_{j}+\mathbf{g}_{r}}}{1+\sum_{\ell\neq
i,j}e^{-\mathbf{g}_{j}+\mathbf{g}_{\ell}}},&r\neq i\\\ 0,&r=i\end{cases}.$

Thus, we equivalently need to show,
$\mathbf{v}^{\top}\text{diag}(\mathbf{u})\mathbf{v}>(\mathbf{u}^{\top}\mathbf{v})^{2}$.
Since $\mathbf{u}\geq 0$, and $\mathbf{u}^{\top}\mathbf{1}_{n}=1$,

$\displaystyle\mathbf{v}^{\top}\text{diag}(\mathbf{u})\mathbf{v}$
$\displaystyle=\big{(}\sum_{r\in[n]}\mathbf{v}_{r}^{2}\mathbf{u}_{r}\big{)}\big{(}\sum_{r\in[n]}\mathbf{u}_{r}\big{)}$
$\displaystyle\geq\big{(}\sum_{i\in[n]}\mathbf{v}_{r}\mathbf{u}_{r}\big{)}^{2}=(\mathbf{u}^{\top}\mathbf{v})^{2},$

where we used Cauchy-Schawrz inequality. The equality holds only if there
exists a constant $\alpha$ such that for all $r\neq i$,
$\mathbf{v}_{r}=\alpha$ which contradicts the assumption
$\mathbf{A}_{i}\mathbf{v}\neq 0$.

Now consider direction $\mathbf{V}$ satisfying condition (12). By convexity of
$f_{ij}(\cdot)$, for all $i\in[n]$ and
$j\in\\{\ell|\,y_{\ell}=y_{i},\,\ell\neq i\\}$, we have,

$\displaystyle f_{ij}(\mathbf{g}_{i}+\mathbf{v}_{i})\geq
f_{ij}(\mathbf{g}_{i})+\mathbf{v}_{i}^{\top}\nabla
f_{ij}(\mathbf{g}_{i}),\quad f_{ij}({\mathbf{g}^{i}}+{\mathbf{v}^{i}})\geq
f_{ij}({\mathbf{g}^{i}})+{\mathbf{v}^{i}}^{\top}\nabla
f_{ij}(\mathbf{g}^{i}).$

However, since
$\mathbf{V}-\text{{diag}}(\mathbf{V})\not\propto\mathbf{1}_{n}\mathbf{1}_{n}^{\top}-\mathds{I}_{n}$,
there exists ${i^{\prime}}\in[n]$ such that either
$\mathbf{A}_{i^{\prime}}\mathbf{v}_{i^{\prime}}\neq 0$ or
$\mathbf{A}_{i^{\prime}}\mathbf{v}^{i^{\prime}}\neq 0$ (or both). Without loss
of generality, suppose $\mathbf{A}_{i^{\prime}}\mathbf{v}_{i^{\prime}}\neq 0$.
Thus, by strict-convexity, for all $j\in\\{\ell|\,y_{\ell}=y_{i},\,\ell\neq
i\\}$, for $\mathbf{g}_{i^{\prime}}$ we have the following strict inequality.

$\displaystyle
f_{i^{\prime}j}(\mathbf{g}_{i^{\prime}}+\mathbf{v}_{i^{\prime}})>f_{i^{\prime}j}(\mathbf{g}_{i^{\prime}})+\mathbf{v}_{i^{\prime}}^{\top}\nabla
f_{i^{\prime}j}(\mathbf{g}_{i^{\prime}}).$

Summing the inequalities over all $i\in[n]$ and
$j\in\\{\ell|\,y_{\ell}=y_{i},\,\ell\neq i\\}$, we get (12), and the proof is
complete. ∎

Proof of Lemma 2 We first show that at the optimal solution, we meet the
condition (12). Suppose
$\mathbf{G}^{*}-\operatorname{diag}(\mathbf{G}^{*})=\alpha(\mathbf{1}_{n}\mathbf{1}_{n}^{\top}-\mathds{I}_{n}),\,\,\alpha\in\mathds{R}$,
and consider

$\displaystyle\mathbf{G}_{1}=\frac{1}{\tau}\begin{bmatrix}\mathbf{1}_{n_{1}}\mathbf{1}_{n_{1}}^{\top}&0\\\
0&\mathbf{1}_{(n-n_{1})}\mathbf{1}_{(n-n_{1})}^{\top}\end{bmatrix}.$

$\mathbf{G}_{1}$ is positive semi-definite and feasible, so
$\mathcal{L}(\mathbf{G}^{*})\leq\mathcal{L}(\mathbf{G}_{1})$. Then, we have,

$\displaystyle\mathcal{L}(\mathbf{G}^{*})\leq\mathcal{L}(\mathbf{G}_{1})$
$\displaystyle=n_{1}\log\big{(}(n_{1}-1)+(n-n_{1})e^{-\frac{1}{\tau}}\big{)}+\sum_{c\neq
1}n_{c}\log\big{(}n-n_{1}-1+n_{1}e^{-\frac{1}{\tau}}\big{)}$
$\displaystyle<n_{1}\log\big{(}n-1\big{)}+\sum_{c\neq
1}n_{c}\log\big{(}n-1\big{)}$ $\displaystyle=n\log\big{(}n-1\big{)}$
$\displaystyle=\mathcal{L}(\mathbf{G}^{*}).$

That is $\mathcal{L}(\mathbf{G}^{*})<\mathcal{L}(\mathbf{G}^{*})$ which is
contradiction.

Now, suppose $\mathbf{G}^{*}_{1}\neq\mathbf{G}^{*}_{2}$ are both optimal in
$\eqref{eq:SCL_UFM_cvx}$. Since, both $\mathbf{G}_{1}^{*}$ and
$\mathbf{G}_{2}^{*}$ are feasible,
$\frac{1}{2}(\mathbf{G}_{1}^{*}+\mathbf{G}_{2}^{*})$ is also feasible. Then,
by optimality of $\mathbf{G}_{1}^{*},\mathbf{G}_{2}^{*}$ and Lemma 6,

$\displaystyle\mathcal{L}(\mathbf{G}_{1}^{*})\leq\mathcal{L}\Big{(}\frac{\mathbf{G}_{1}^{*}+\mathbf{G}_{2}^{*}}{2}\Big{)}<\frac{1}{2}(\mathcal{L}(\mathbf{G}_{1}^{*})+\mathcal{L}(\mathbf{G}_{2}^{*}))=\mathcal{L}(\mathbf{G}_{1}^{*}),$

which is a contradiction, and the proof is complete. ∎

##  Appendix C Proof of Lemma 3

Recall from Lemma 1 that $\mathbf{H}^{*}$ satisfies the NC property. Thus,
$\mathbf{G}^{*}$, given the samples are ordered, has a block-form and can be
parameterized by a symmetric $k\times k$ matrix as follows:

$\displaystyle\exists\,\mathbf{\Gamma}\in\mathds{R}^{k\times
k},\quad\text{s.t.}\quad\mathbf{G}^{*}_{i,j}=\mathbf{\Gamma}_{y_{i},y_{j}}.$
(13)

Also, recall from Lemma 2 that the global solution is unique.

Given (13), we can find $\mathbf{G}^{*}$, the solution of (5), by the
following equivalent problem.

$\displaystyle\mathbf{\Gamma}^{*},\mathbf{G}^{*}\in\arg\min_{\mathbf{\Gamma},\mathbf{G}}f(\mathbf{\Gamma}):=\frac{1}{n}\sum_{c\in[k]}n_{c}$
$\displaystyle\log\bigg{(}(n_{c}-1)+\sum_{c^{\prime}\neq
c}n_{c^{\prime}}\exp({-\mathbf{\Gamma}_{c,c}+\mathbf{\Gamma}_{c,c^{\prime}}})\bigg{)},\quad$
(14) s.t. $\displaystyle\mathbf{\Gamma}_{c,c}\leq\frac{1}{\tau}\,\quad\forall
c\in[k],\quad$
$\displaystyle\mathbf{G}_{i,j}=\mathbf{\Gamma}_{y_{i},y_{j}}\,\quad\forall
i,j\in[n]$ $\displaystyle\mathbf{G}\succcurlyeq 0.$

We need the following lemma to complete the proof.

######  Lemma 7 (Restatement of Lemma 4).

Consider problem (14). If $n_{c_{1}}=n_{c_{2}}$, we have

$\displaystyle\mathbf{\Gamma}^{*}_{c_{1},c_{1}}=\mathbf{\Gamma}^{*}_{c_{2},c_{2}},\qquad\mathbf{\Gamma}^{*}_{c,c_{1}}=\mathbf{\Gamma}^{*}_{c,c_{2}},\quad\forall
c\neq c_{1},c_{2}$ (15)

###### Proof.

Without loss of generality, let $c_{1}=1$ and $c_{2}=2$, and define the
permutation matrix $\mathbf{R}:=\mathbf{R}_{c_{1}\,c_{2}}$ as follows:

######  Definition 3 (Permutation matrix).

For $i,j\in[k]$, the permutation matrix $\mathbf{R}_{ij}\in\mathds{R}^{k\times
k}$ is the matrix that swaps rows $i$ and $j$ of a matrix when multiplied by
left. Equivalently, $\mathbf{R}_{ij}$ is the identity matrix $\mathds{I}_{n}$
with the rows $i$ and $j$ swapped.

Note that $\mathbf{R}^{\top}=\mathbf{R}$. For any
$\mathbf{\Gamma}\in\mathds{R}^{k\times k}$, $\mathbf{R}\mathbf{\Gamma}$ swaps
row $c_{1}$ and $c_{2}$ and $\mathbf{\Gamma}\mathbf{R}$ swaps columns $c_{1}$
and $c_{2}$.

Recall that $\mathbf{\Gamma}^{*}$ and $\mathbf{G}^{*}$ are symmetric. We prove
the lemma by contradiction. Specifically, if the lemmas condition does not
hold, we show that by swapping rows $c_{1}$ and $c_{2}$ of $\mathbf{\Gamma}$,
followed by swapping the columns of the same index, the (optimal) loss value
remains the same, while the optimizer changes.

Suppose (15) does not hold. Define
$\widetilde{\mathbf{\Gamma}}=\mathbf{R}\mathbf{\Gamma}^{*}\mathbf{R}$. Since
$n_{1}=n_{2}$, we have
$f(\mathbf{\Gamma}^{*})=f(\widetilde{\mathbf{\Gamma}})$, while by assumption,
$\widetilde{\mathbf{\Gamma}}\neq\mathbf{\Gamma}^{*}$. Now, define
$\widetilde{\mathbf{R}}$ as follows,

$\displaystyle\widetilde{\mathbf{R}}:=\begin{bmatrix}0&\mathds{I}_{n_{1}}&0&0&\cdots&0\\\
\mathds{I}_{n_{2}}&0&0&0&\cdots&0\\\ 0&0&\mathds{I}_{n_{3}}&0&\cdots&0\\\
0&0&0&\mathds{I}_{n_{4}}&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&0&\cdots&\mathds{I}_{n_{k}}\end{bmatrix}_{n\times n}.$

Then, it is straightforward to check
$\widetilde{\mathbf{G}}=\widetilde{\mathbf{R}}\mathbf{G}^{*}\widetilde{\mathbf{R}}$
and $\widetilde{\mathbf{\Gamma}}$ are feasible in the problem (14). Since
$f(\mathbf{\Gamma}^{*})=f(\widetilde{\mathbf{\Gamma}})$,
$(\widetilde{\mathbf{\Gamma}},\widetilde{\mathbf{G}})$ should also be optimal.
This contradicts the uniqueness of the solution by Lemma 2, and the proof is
complete.

∎

Given Lemma 7, we can show that in the STEP-imbalanced or balanced case (as a
special case) setup, the global solution $\mathbf{G}^{*}$ has a simpler form.
Recall that in a $(R,\rho)$-STEP setting,

$\displaystyle
n_{c}=n_{c^{\prime}}\quad\text{if}\quad\begin{cases}c,c^{\prime}\in\\{1,...,\overline{\rho}k\\}\quad\text{(majority)}\\\
c,c^{\prime}\in\\{\overline{\rho}k+1,...,k\\}\quad\text{(minority)}\end{cases}$

Applying (15) for all pairs of classes with equal number of samples, we can
show that there exists five scalars
$\alpha_{\text{maj}},\alpha_{\text{minor}}$,
$\beta_{\text{maj}},\beta_{\text{minor}}$, $\theta$ such that,

$\displaystyle\mathbf{\Gamma}^{*}=\begin{bmatrix}\mathbf{A}_{\text{maj}}&&\theta\mathbf{1}_{\overline{\rho}k}\mathbf{1}^{\top}_{\rho
k}\\\ \theta\mathbf{1}_{\rho
k}\mathbf{1}^{\top}_{\overline{\rho}k}&&\mathbf{A}_{\text{minor}}\end{bmatrix},\qquad\begin{cases}\mathbf{A}_{\text{maj}}=(\alpha_{\text{maj}}-\beta_{\text{maj}})\mathds{I}_{\overline{\rho}k}+\beta_{\text{maj}}\mathbf{1}_{\overline{\rho}k}\mathbf{1}_{\overline{\rho}k}^{\top}\\\
\mathbf{A}_{\text{minor}}=(\alpha_{\text{minor}}-\beta_{\text{minor}})\mathds{I}_{\overline{\rho}k}+\beta_{\text{minor}}\mathbf{1}_{\overline{\rho}k}\mathbf{1}_{\overline{\rho}k}^{\top}\end{cases}.$

This proves Lemma 3. In the special case of balanced data, we can further show
that $\alpha_{\text{maj}}=\alpha_{\text{minor}}=:\alpha$ and
$\beta_{\text{maj}}=\beta_{\text{minor}}=:\beta$. This reduces to,

$\displaystyle\mathbf{G}^{*}=\left(\alpha-\beta\right)\mathds{I}_{n}+\left((\beta-\theta)\mathds{I}_{k}+\theta\mathds{J}_{k}\right)\otimes\mathds{J}_{(\frac{n}{k})},$
(16)

where $\mathds{J}_{m}=\mathbf{1}_{m}\mathbf{1}_{m}^{\top}$. ∎


11institutetext: 1 Purdue University, West Lafayette, Indiana, 47907, USA
11email: {kauru, pabbaraj, mccarth<EMAIL_ADDRESS>
11email: + Corresponding author

# Clutter Slices Approach for Identification-on-the-fly of Indoor Spaces

Upinder Kaur equal contribution11 Praveen Abbaraju 11++** Harrison McCarty 11
Richard M. Voyles 11

###### Abstract

Construction spaces are constantly evolving, dynamic environments in need of
continuous surveying, inspection, and assessment. Traditional manual
inspection of such spaces proves to be an arduous and time-consuming activity.
Automation using robotic agents can be an effective solution. Robots, with
perception capabilities can autonomously classify and survey indoor
construction spaces. In this paper, we present a novel identification-on-the-
fly approach for coarse classification of indoor spaces using the unique
signature of clutter. Using the context granted by clutter, we recognize
common indoor spaces such as corridors, staircases, shared spaces, and
restrooms. The proposed clutter slices pipeline achieves a maximum accuracy of
93.6% on the presented clutter slices dataset. This sensor independent
approach can be generalized to various domains to equip intelligent autonomous
agents in better perceiving their environment.

###### Keywords:

Mobile Robots Identification-on-the-fly Clutter Slices

##  1 Introduction

Large-scale construction spaces need periodic surveying, inspection, and
renovation [3]. Continuous assessment helps to identify the completion status
as well as localize problems which may arise [1]. Traditionally, this requires
a well-coordinated surveillance activity which consumes enormous man-hours,
even resulting in delays and overheads. Further, the inherent complexity of
such spaces, in terms of design, inter-connectivity, and scale complicate this
already arduous undertaking. Automation of processes in such activities has
the potential to greatly reduce the effort required and boost overall
productivity, at the same time reducing overhead costs and delays. This need
for process automation in the complex and fast-paced world of construction
calls for innovation at all levels.

Inspection and surveying of outdoor large-scale construction activities now
utilizes satellite imagery and Global Positioning Systems (GPS) based
localization [15, 5]. While these methods are robust and cost effective
solutions for outdoor spaces, they prove to be in-effective for indoor spaces.
Moreover, indoor GPS-based navigation is not effective for multi-level
structures and the signal in itself becomes unreliable [5]. Alternative
solutions including WiFi signals and quantum sensors require expensive
equipment for implementation [4]. Further, these limitations of expenses,
time, and resources for efficient inspection and surveillance is withholding
the extensive application of Building Information Modelling (BIM) in
construction activities [1, 10]. Robotic technologies, such as mobile robots,
rovers, and aerial manipulators, are proving to be an efficient automation
solution for construction activities [2]. Mobile robots, such as aerial
manipulators (UAV) [7] and ground-based manipulators (wheeled and legged) [12]
are a cost-effective solution for real-time large scale inspections due to
their robust and reliable performance.

Mobile robots with capabilities of perception are proving to be a paradigm
shifting technology in inspection and surveillance. Perception sensors such as
LiDARs (2D and 3D), stereo cameras, RGB-D cameras, ultrasonic and infrared
proximity sensors have been extensively used in robot vision to identify the
surrounding of a robot and its subsequent localization [9, 14]. This is
similar to human perceiving their surroundings through multiple modal sensing.
For example, humans use vision and their knowledge base to comprehend the
characteristics of a construction site. They also use tactile sensing to
provide an understanding over various states and properties of surfaces [12,
13]. However, humans have the ability to inherently perform these
identification procedures as a secondary task, while performing primary
targeted tasks such as reaching a target location, navigating among obstacles,
etc. We call this identification-on-the-fly as it enables multi modal
perception for intelligent and self-adaptive systems. [8]. Extending this
methodology to coarse identification and classification of indoor spaces
yields systems capable of multi-modal perception and intelligent operation yet
efficient, especially for BIM development.

In this paper, the identification-on-the-fly method is used to coarsely
identify human-built spaces based on the distribution of clutter. Each space
has its own distinct signature. Clutter, the things which occupy space in an
indoor environments such as doors, desks, and wall fittings, grant context to
a space. The aim of this study is to develop the ability to identify and
classify spaces based on this inherent signature. Hence, we present a unique
sensor independent approach for classifying indoor spaces based on their
inherent signatures. A sensor independent approach allows generalization of
this method to numerous avenues and also allows for fast and inexpensive
implementations.

In order to develop and validate this approach, we first present the Clutter
Slices dataset. This initial dataset is developed with 2D LiDAR scans of
indoor areas, such as staircases, washrooms, corridors, and shared spaces;
spaces are common to most developments. We then propose the clutter slices
pipeline which utilizes commonly used classifiers to train and subsequently
test the approach on the collected dataset. Hence, the contributions of this
study are as follows:

  * •

The Clutter Slices dataset of common indoor spaces along with the analysis of
its distribution. This dataset is publicly available.

  * •

The clutter slices classification pipeline, including widely used classifiers,
is presented. The evaluation of this model on the clutter slices dataset is
presented as a baseline.

  * •

A new pipeline for clutter slices classification independent of sensor type,
including widely used classifiers. The evaluation of this model on the clutter
slices dataset is presented as a baseline.

  * •

Performance analysis of the selected classifiers in the proposed pipeline is
presented on the clutter slices dataset.

The organization of this paper is as follows: Section 2 describes the
Identification-on-the-fly approach using clutter slices to decipher the unique
signatures of indoor spaces. Further, Section 3 presents the Clutter Slices
dataset. In this section, we describe the methodology of data collection and
the structure of the dataset. Section 4 presents the model and the
classification methods used on the Clutter Slices dataset for identification
of spaces. Experiments and results are presented in Section 5, followed by the
conclusion in Section 6.

##  2 Identification-on-the-fly

Embedding intelligence and self-adaptive features into robots requires them to
perform multi-modal tasks, simultaneously, to extract a rich understanding of
their environment. Such rich comprehension is based on contextual as well as
state information of the environment which is extracted while navigating or
interacting with it. Humans, exhibit this quality of multi-modal perception
and cognition, which helps them decipher the surroundings in a way that they
are even able to navigate unseen environments. Moreover, humans are able to
perform such navigation and classification as a secondary task, while the goal
of such movement can be varied. Example scenarios would include identification
of different areas while navigation, using vision and tactile sensing to
understand the current state of a surface or object. Another such example is
performing status checks while navigating an unseen construction space.
Identification-on-the-fly incorporates this ability of comprehending the
unseen environment as an almost intuitive capability (performed as a secondary
task) into autonomous robots, thereby taking them one step closer to human-
like intelligence.

In this paper, an identification-on-the-fly approach is utilized to address
problems associated with coarse identification of human-built indoor spaces
while navigating through them. This is accomplished based on an intuitive
assumption that each class of space has its own unique signature. Moreover,
common spaces exhibit similar patterns as they are built for specific
purposes, such as staircases, corridors, etc. Hence, these unique signatures
can be generalized throughout indoor spaces to learn and recognize the class
of spaces for unseen environments too.

###  2.1 Indoor Construction Spaces

Indoor construction spaces are unique environments in the sense that they have
both static and dynamic elements. While the structure and walls may not change
significantly over the course of time, the dynamic objects such as furniture,
fittings, etc. can change drastically even over a short period of time. These
changes pose a challenge to most autonomous system which rely on precise and
real-time mappings. However, the coarse signature of the space remains rather
constant. In this study, we leverage the overall signature of a space for
coarse classification of the space.

###  2.2 Clutter-Slices

Clutter is the class of things which add context to a room. A room is
primarily just four walls, however, if there are stairs in it then it becomes
a staircase. Similarly, if the stairs are replaced by desks, it becomes a
working space. Hence, there is inherent information, albeit coarse, in the
distribution of objects in a four wall enclosure. Moreover, there is also
information in the structure of the placement of the four walls. A corridor
and an office, both have four walls but the structure is inherently
dissimilar. The clutter-slices method leverages this inherent information in
the distribution of objects and the basic structure of the enclosed spaces to
classify the human-built environments.

Clutter includes both static (wall fittings, doors, pillars, sinks) and
dynamic objects (tables, chairs, table-top equipment, humans, cabinets). These
objects occupy the scans with respect to their position in the environment. At
different heights, different objects appear on the scan relative to their
position in the environment, as illustrated in Fig. 1. Based on the
information available from the clutter-slices, different indoor facilities can
exhibit unique distributions.

Figure 1: 2D lidar scans of a room at multiple heights

Clutter slices do not just coarsely map the area, but they also coarsely
localize the observer in the scene. The information from clutter slices
enables abstraction of details such as the closeness of the observer to
ceiling or ground and to the nearby walls. This information can be used to
estimate the pose of the observer in the scene and subsequently map their
trajectory.

##  3 Clutter Slices Dataset

Robust identification of construction spaces, especially indoor spaces, needs
intelligent models that can comprehend the environment efficiently. The first
step in building such models is creating adequate datasets for training.
Hence, we present a diverse dataset of real-life indoor spaces. The clutter
slices dataset is a collection of scans of common indoor spaces, such as
corridors, staircases, restrooms, and large shared spaces (including
cafeterias, common areas, and shared working offices), as shown in Fig. 2.
This is a fully annotated dataset which enables models to learn the
distribution of clutter in such common areas, and thereby contributes to
efficient recognition of spaces.

Figure 2: Images and respective 2D LiDAR plots of indoor spaces with the
sensor capturing scans of (a)Corridor and (b) Staircase.

The Clutter Slices dataset was created by taking two-dimensional (2D) LiDAR
scans of areas such as restrooms, staircases, shared spaces and corridors
around the various buildings of Purdue University. We chose a LiDAR sensor for
this data collection as it is one of the most widely used sensors in
navigation and mapping in robotic vision. Using this sensor, we measure
spatial distribution $270{{}^{\circ}}$ around a point, as shown in Fig. 2. The
maximum range of this sensor is 30 meters. Various positions around the space
were used for the data collection to ensure a holistic capture of data. The
height of the data collection was varied in steps of 1 meter.

Figure 3: Frequency Distribution of Classes of Clutter Slices Dataset

There are four classes in the Clutter Slices dataset: corridors, staircases,
restrooms, and large shared spaces. These classes are common to most indoor
construction areas and hence are useful for researchers in future work. The
distribution of instances of these classes in the dataset are shown in Fig. 3.
The dataset is publicly available at
https://github.com/CRLPurdue/Clutter_Slices [11].

##  4 Clutter Slices Pipeline

The clutter slices approach with identification-on-the-fly aims to understand
inherent patterns in the data, rather than relying on explicit feature
engineering. Hence, by just using the distances of clutter around a point, we
derive a clutter slice at a fixed height. A stack of these slices would build
the clutter signature of the space. However, the goal here is to understand
the strength of just a single clutter slice in deriving the class of a space.
Therefore, we use a single 2D scan of the space to understand the distribution
of clutter and subsequently, classify it.

Figure 4: Flowchart of Clutter Slices Pipeline

In the clutter slices pipeline, the input 2D scan is translated to distances
around the point. This allows for use of multiple sensors, as a variety of
sensors such as LiDARs, cameras, and infrared sensors can be used to get the
distance measurements. These distances are then vectorized as the feature
space $D{{}_{i}}$, wherein
$D{{}_{i}}=[D{{}_{i}}{{}_{,}}{{}_{0}},...,D{{}_{i}}{{}_{,}}{{}_{2}}{{}_{7}}{{}_{0}}]$.
The labels for this feature space are defined as $y{{}_{i}}$ where $i\in[0,3]$
for the clutter slices dataset. The feature space is then scaled using Box-Cox
power transformations to standardize the data. The prepared data is then input
to the classifiers. In this study, we used six classifiers which are widely
used in machine learning: Random Forests, Logistic Regression, Support Vector
Machines, AdaBoost, Artificial Neural Network, and Convolutional Neural
Network. These classifiers present a baseline on the clutter slices dataset,
and prove its effectiveness.

##  5 Experiments and Results

The validation of the proposed pipeline on the clutter slices dataset using
the selected classifiers is presented in this section. We first present the
experimental setup, including the hyperparameters selected for the
classifiers, and consequently, present the performance in terms of accuracy,
precision and recall for the classifiers.

###  5.1 Experimental Setup

The experiments were conducted with the Clutter Slices dataset using the
described pipeline with six classification models. Since this is a multi-class
classification task, the dataset was stratified and shuffled, then split into
a train and test set with an 80-20 ratio. We followed a five fold cross
validation to ensure coverage of the entire dataset. The scikit-learn
implementation of Random Forests (RF), Adaboost, Suppport Vector Machine
(SVM), and Logistic Regression (LR) were all used [6]. A total of 100
estimators were used for RF with the total depth of 100. In case of Adaboost,
the number of estimators used were 200. The polynomial kernel was used for
SVM.

The architecture of the artificial neural network (ANN) constitutes of six
fully connected dense layers. The number of units in the layers are: 481,364,
256, 125, 50 and 4. The last layer has Softmax activation with rectified
linear units (ReLU) activation being used for the previous layers. We also
incorporated two dropout layers in this network. The architecture of the
convolutional neural network (CNN) comprises of two convolutional layers
followed by a MaxPooling layer and three dense, fully-connected layers. The
dense layers have 125, 50 and 4 units, respectively. Dropout and input
flattening layers were also used in this network. Softmax activation was used
at the last layer with ReLU being used in all others. The CNN and the ANN,
both used the Adam optimizer with a learning rate of 0.01. The categorical
cross-entropy was used as a measure of loss. Both neural network models were
trained for 30 epochs with a mini-batch size of 32.

The training and testing was conducted on a computer with 32GB RAM, NVIDIA GTX
1080 Ti GPU and Intel Core i9 CPU.

Table 1: Accuracy on test set for the Clutter Slices Dataset Classifiers | Cross validation Accuracy | Overall Accuracy
---|---|---
1st Fold | 2nd Fold | 3rd Fold | 4th Fold | 5th Fold
RF | $0.907$ | $0.88$ | $0.94$ | $0.96$ | $0.94$ | $0.928\pm 0.03$
AdaBoost | $0.57$ | $0.396$ | $0.53$ | $0.60$ | $0.37$ | $0.495\pm 0.09$
SVM | $0.83$ | $0.88$ | $0.867$ | $0.924$ | $0.886$ | $0.88\pm 0.03$
Logistic Regression | 0.759 | 0.849 | 0.83 | 0.79 | 0.849 | $0.82\pm 0.035$
CNN | 0.907 | 0.905 | 0.94 | 0.96 | 0.96 | $0.936\pm 0.03$
ANN | 0.87 | 0.87 | 0.925 | 0.96 | 0.89 | $0.90\pm 0.04$
|  |  |  |  |  |

###  5.2 Results

The tests were performed using the Clutter Slices dataset. The accuracy of the
six classifiers for each fold, along with the overall accuracy is presented in
Table LABEL:table:acc. The results indicate that the clutter slices dataset is
able to present enough information for recognition of classes, even with just
a single scan as input. While random forests, CNN, and ANN models showed more
than 90% accuracy, models like SVM and Logistic regression also showed good
performance with very little hyper-parameter tuning. The low accuracy of
Adaboost can be attributed to over-fitting by the model.

Figure 5 shows the class-wise precision recall curves for the overall
performance of the six classifiers. These curves highlight that the models
were able to identify classes Staircases and Shared Spaces without much loss,
but Restrooms and Corridors were showing overlap with other classes. The
overlap can be intuitively explained as restrooms can have characteristics
similar to shared spaces. Nevertheless, despite these challenges, the area-
under-the-curve (auc) values prove the performance of these models.

Figure 5: Overall classifier performance

##  6 Conclusion

In this paper we introduce the identification-on-the-fly approach to imbue
human-like intelligence into robotic systems. The proposed clutter slices
approach leverages the unique signatures of common indoor spaces for coarse
classification. The initial validation of the clutter slices approach is
performed on the dataset using 2D LiDAR sensor. Further, we present a scalable
pipeline that supports this approach. The pipeline is flexible enough to
accommodate varied classifiers. We used some of the widely used classifiers
such as random forests, logistic regression, and neural network models to
establish a baseline for the dataset. A maximum accuracy of 93.6% was achieved
with this approach without significant hyperparameter tuning. The precision-
recall plots show the convergence of the models in recognizing the classes of
spaces.

The clutter slices approach captures the unique signatures of common indoor
spaces and proves the potential of this approach in their coarse
classification. Nevertheless, the clutter slices approach is not sensor
specific and can be potentially generalized across domains. In the future,
this approach of identification-on-the-fly can be an essential tool for
perceiving and assessing surroundings of intelligent autonomous agents.
Clutter slices is one implementation of the identification-on-the-fly method
used for coarse classification of indoor spaces, adding contextual information
to the robot perception. However, there are endless opportunities to perform
identification-on-the-fly to understand the surrounding while still
identifying potential dangers and outcome of future actions.

## Acknowledgment

This work was supported, in part, by the Dept. of Energy, the NSF Center for
Robots and Sensor for the Human Well-Being (RoSe-HUB) and by the National
Science Foundation under grant CNS-1439717 and the USDA under grant
2018-67007-28439. The authors greatly acknowledge the contribution of coffee
for the actualization of this work.

## References

  * [1] Becerik-Gerber, B., Jazizadeh, F., Li, N., Calis, G.: Application areas and data requirements for bim-enabled facilities management. Journal of construction engineering and management 138(3), 431–442 (2012)
  * [2] Bock, T.: Construction robotics. Autonomous Robots 22, 201–209 (2007). https://doi.org/10.1007/s10514-006-9008-5
  * [3] Jupp, J.: 4d bim for environmental planning and management. Procedia engineering 180, 190–201 (2017)
  * [4] McKinlay, R.: Technology: Use or lose our navigation skills. Nature 531(7596), 573–575 (2016)
  * [5] Ozdenizci, B., Ok, K., Coskun, V., Aydin, M.N.: Development of an indoor navigation system using nfc technology. In: 2011 Fourth International Conference on Information and Computing. pp. 11–14 (2011)
  * [6] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12, 2825–2830 (2011)
  * [7] Praveen, A., Haoguang, Y., Hyukjun, J., Richard, M.V.: Aerial mobile manipulator system to enable dexterous manipulations with increased precision. In: 2019 IEEE ICRA 2019 workshop on High Accuracy Mobile Manipulation in Challenging Environments. Preprint arXiv:2010.09618 (2019)
  * [8] Praveen, A., Xin, M., Harikrishnan, M., Vishnunandan, L.V., Mo, R., Richard, M.V.: Inspection-on-the-fly using hybrid physical interaction control for aerial manipulators. In: 2020 IEEE International Conference on Intelligent Robots and Systems (IROS). Preprint arXiv:2010.09605 (2020)
  * [9] Su, Z., Zhou, X., Cheng, T., Zhang, H., Xu, B., Chen, W.: Global localization of a mobile robot using lidar and visual features. In: 2017 IEEE International Conference on Robotics and Biomimetics (ROBIO). pp. 2377–2383 (2017)
  * [10] Sun, C., Jiang, S., Skibniewski, M.J., Man, Q., Shen, L.: A literature review of the factors limiting the application of bim in the construction industry. Technological and Economic Development of Economy 23(5), 764–779 (2017)
  * [11] Upinder, K., Praveen, A.: Clutter slices dataset. Collaborative Robotics Lab. Available: https://github.com/CRLPurdue/Clutter_Slices (2020)
  * [12] Wang, B., Guo, R., Li, B., Han, L., Sun, Y., Wang, M.: Smartguard: An autonomous robotic system for inspecting substation equipment. Journal of Field Robotics 29(1), 123–137 (2012)
  * [13] Wang, H., Li, J., Zhou, Y., Fu, M., Yang, S.: Research on the technology of indoor and outdoor integration robot inspection in substation. In: 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). pp. 2366–2369 (2019)
  * [14] Xu, Y., Shmaliy, Y.S., Li, Y., Chen, X., Guo, H.: Indoor ins/lidar-based robot localization with improved robustness using cascaded fir filter. IEEE Access 7, 34189–34197 (2019)
  * [15] Zhang, F., Duarte, F., Ma, R., Milioris, D., Lin, H., Ratti, C.: Indoor space recognition using deep convolutional neural network: a case study at mit campus. arXiv preprint arXiv:1610.02414 (2016)