# Label Distributionally Robust Losses for Multi-class Classification:
Consistency, Robustness and Adaptivity

Dixian Zhu  Yiming Ying  Tianbao Yang

###### Abstract

We study a family of loss functions named label-distributionally robust (LDR)
losses for multi-class classification that are formulated from
distributionally robust optimization (DRO) perspective, where the uncertainty
in the given label information are modeled and captured by taking the worse
case of distributional weights. The benefits of this perspective are several
fold: (i) it provides a unified framework to explain the classical cross-
entropy (CE) loss and SVM loss and their variants, (ii) it includes a special
family corresponding to the temperature-scaled CE loss, which is widely
adopted but poorly understood; (iii) it allows us to achieve adaptivity to the
uncertainty degree of label information at an instance level. Our
contributions include: (1) we study both consistency and robustness by
establishing top-$k$ ($\forall k\geq 1$) consistency of LDR losses for multi-
class classification, and a negative result that a top-$1$ consistent and
symmetric robust loss cannot achieve top-$k$ consistency simultaneously for
all $k\geq 2$; (2) we propose a new adaptive LDR loss that automatically
adapts the individualized temperature parameter to the noise degree of class
label of each instance; (3) we demonstrate stable and competitive performance
for the proposed adaptive LDR loss on 7 benchmark datasets under 6 noisy label
and 1 clean settings against 13 loss functions, and on one real-world noisy
dataset. The method is open-sourced at https://github.com/Optimization-
AI/ICML2023_LDR.

Machine Learning, ICML

##  1 Introduction

In the past decades, multi-class classification has been used in a variety of
areas, including image recognition (Krizhevsky et al., 2009; Deng et al.,
2009; Geusebroek et al., 2005; Hsu & Lin, 2002), natural language processing
(Lang, 1995; Brown et al., 2020; Howard & Ruder, 2018), etc. Loss functions
have played an important role in multi-class classification (Janocha &
Czarnecki, 2017; Kornblith et al., 2021).

In machine learning (ML), the most classical loss functions include the cross-
entropy (CE) loss and the Crammer-Singer (CS) Loss (aka the SVM loss). Before
the deep learning era, the CS loss have been widely studied and utilized for
learning a linear or kernelized model (Crammer & Singer, 2002). However, in
the deep learning era the CE loss seems to dominate the CS loss in practical
usage (He et al., 2016). One reason is that the CE loss is consistent for
multi-class classification (i.e., yielding Bayes optimal classifier with
infinite number of samples), while the CS loss is generally not consistent
unless under an exceptional condition that the maximum conditional probability
of a class label given the input is larger than $0.5$ (Zhang, 2004), which
might hold for simple tasks such as MNIST classification but unlikely holds
for complicated tasks, e.g., ImageNet classification (Beyer et al., 2020;
Tsipras et al., 2020). Nevertheless, the CE loss has been found to be
vulnerable to noise in the labels (Ghosh et al., 2017; Wang et al., 2019).
Hence, efforts have been devoted to robustifying the CE loss such that it
becomes noise-tolerant. A sufficient condition for the loss function to be
noise-tolerant is known as the symmetric property (Ghosh et al., 2017), i.e.,
the sum of losses over all possible class labels for a given data point is a
constant. Following the symmetric property, multiple variants of CE loss have
been proposed to enjoy the noise-tolerance property. However, a symmetric loss
alone is usually not enough to achieve good performance in practice due to
slow convergence (Zhang & Sabuncu, 2018; Ma et al., 2020). Hence, a loss that
interpolates between the CE loss and a symmetric loss usually achieves better
performance on real-world noisy datasets (Wang et al., 2019; Zhang & Sabuncu,
2018; Englesson & Azizpour, 2021; Ma et al., 2020), e.g., on the WebVision
data with 20% noisy data (Li et al., 2017).

These existing results can be explained from the degree of uncertainty of the
given label information. If the given label information of an instance is
certain (e.g., MNIST data), then the CS loss is a good choice (Tang, 2013); if
the given label information is little uncertain (e.g., Imagenet Data), then
the CE loss is a better choice; if the given label information is highly
uncertain (e.g., WebVision data), then a loss that interpolates between the CE
loss and a symmetric loss wins. While the parameter tuning (e.g., the weights
for combining the CE loss and a symmetric loss) can achieve dataset
adaptivity, an open problem exists: "Can we define a loss to achieve instance
adaptivity, i.e., adaptivity to the uncertainty degree of label information of
each instance?"

To address this question, this paper proposes to capture the uncertainty in
the given label information of each instance by using the distributionally
robust optimization (DRO) framework. For any instance, we assign each class
label a distributional weight and define the loss in the worst case of the
distributional weights properly regularized by a function, which is referred
to as label distributionally robust (LDR) losses. The benefits of using the
DRO framework to model the uncertainty of the given label information include:
(i) it provides a unified framework of many existing loss functions, including
the CE loss, the CS loss, and some of their variants, e.g., top-$k$ SVM loss.
(ii) it includes an interesting family of losses by choosing the
regularization function of the distributional weights as Kullback?Leibler (KL)
divergence, which is referred to as LDR-KL loss for multi-class
classification. The LDR-KL loss is closely related to the temperature-scaled
CE loss that has been widely used in other scenarios (Hinton et al., 2015;
Chen et al., 2020), where the temperature corresponds to the regularization
parameter of the distribibutional weights. Hence, our theoretical analysis of
LDR-KL loss can potentially shed light on using the temperature-scaled CE loss
in different scenarios. (iii) The LDR-KL loss can interpolate between the CS
loss (at one end), the (margin-aware) CE loss (in between) and a symmetric
loss (at the other end) by varying the regularization parameter, hence
providing more flexibility for adapting to the noisy degree of given label
information. Our contributions are the following:

  * •

We establish a strong consistency of the LDR-KL loss namely All-$k$
consistency that is top-$k$ consistency (corresponding to the Bayes optimal
top-$k$ error) for all $k\geq 1$, and a sufficient condition for the general
family of LDR losses to be All-$k$ consistent.

  * •

We show that an extreme case of the LDR-KL loss satisfies the symmetric
property, making it tolerant to label noise. In addition, we establish a
negative result that a non-negative symmetric loss function cannot achieve
top-$k$ consistency for $k=1$ and $k=2$ simultaneously. Hence, we conclude
that existing top-$1$ consistent symmetric losses cannot be All-$k$
consistent.

  * •

We propose an adaptive LDR-KL loss, which allows us to automatically learn the
personalized temperature parameter of each instance adapting to its own noisy
degree. We develop an efficient algorithm for empirical risk minimization
based on the adaptive LDR-KL loss without incurring much additional
computational burden.

  * •

We conduct extensive experiments on multiple datasets under different noisy
label settings, and demonstrate the stable and competitive performance of the
proposed adaptive LDR-KL loss in all settings.

Table 1: Comparison between different loss functions. Notice that for SCE, we
simplify the loss combination by convex combination ($\beta=1-\alpha$ and
$0\leq\alpha\leq 1$). Detailed expressions of different loss functions are
included in the Appendix A. ‘NA’ means not available or unknown. * means that
the results are derived by us (proofs are included in the Appendix J).
Expressions in parentheses mean the conditions about the hyper-parameters
under which the properties hold.

Category | Loss | Top-$1$ consistent | All-$k$ consistent | Symmetric |  instance adaptivity
---|---|---|---|---|---
| CE | Yes | Yes | No | No
Traditional | CS (Crammer & Singer, 2002) | No | No | No | No
| WW (Weston & Watkins, 1998) | No | No | No | No
Symmetric | MAE (RCE, clipped) (Ghosh et al., 2017) | Yes | No | Yes | No
NCE (Ma et al., 2020) | Yes | No | Yes | No
| RLL (Patel & Sastry, 2021) | No | No | Yes | No
Interpolation between | GCE (Zhang & Sabuncu, 2018) | Yes | Yes∗ ($0\leq q<1$) | Yes ($q=1$) | No
CE and MAE | SCE (Wang et al., 2019) | Yes | Yes∗ ($0\leq\alpha<1$) | Yes ($\alpha=0$) | No
| JS (Englesson & Azizpour, 2021) | NA | NA | Yes ($\pi_{1}=1$) | No
Bounded | MSE (Ghosh et al., 2017) | Yes | Yes∗ | No | No
TGCE (Zhang & Sabuncu, 2018) | NA | NA | No | No
Asymmetric | AGCE (Zhou et al., 2021) | Yes | No | No | No
AUL (Zhou et al., 2021) | Yes | No | No | No
LDR | LDR-KL (this work) | Yes ($\lambda>0$) | Yes ($\lambda=\infty$) | No
ALDR-KL (this work) | Yes ($\lambda_{0}>0,\alpha>\frac{\log K}{\lambda_{0}}$) | Yes ($\lambda_{0}=\infty$) | Yes

##  2 Related Work

Traditional multi-class loss functions. Multi-class loss functions have been
studied extensively in conventional ML literature (Weston & Watkins, 1998;
Tewari & Bartlett, 2007; Zhang, 2004; Crammer & Singer, 2002). Besides the CE
loss, well-known loss functions include the CS loss and the Weston-Watkins
(WW) loss. Consistency has been studied for these loss for achieving Bayes
optimal solution under infinite amount of data. The CE loss is shown to be
consistent (producing Bayes optimal classifier for minimizing zero-one loss,
i.e., top-$1$ error), while the CS and WW loss are shown to be inconsistent
(Zhang, 2004). Variants of these standard losses have been developed for
minimizing top-$k$ error ($k>1$), such as (smoothed) top-$k$ SVM loss, top-$k$
CE loss (Lapin et al., 2015, 2016, 2018; Yang & Koyejo, 2020). Top-$k$
consistency has been studied in these papers showing some losses are top-$k$
consistent while other are not. However, the relationship between these losses
and the CE loss is still unclear, which hinders the understanding of their
insights. Hence, it is important to provide a unified view of these different
losses, which could not only help us understand the existing losses but also
provide new and potentially better choices.

Robust Loss functions. While may different methods have been developed for
tackling label noise (Goldberger & Ben-Reuven, 2017; Han et al., 2018;
Hendrycks et al., 2018; Patrini et al., 2017; Zhang et al., 2021; Madry et
al., 2017; Zhang & Sabuncu, 2018; Wang et al., 2019), of most relevance to the
present work are the symmetric losses and their combinations with the CE loss
or its variants. Ghosh et al. (2017) established that a symmetric loss is
robust against symmetric or uniform label noise where a true label is
uniformly flipped to another class, i.e., the optimal model that minimizes the
risk under the noisy data distribution also minimizes the risk under the true
data distribution. When the optimal risk under the true data distribution is
zero, the symmetric loss is also noise tolerant to the non-uniform label
noise. The most well-known symmetric loss is the mean-absolute-error (MAE)
loss (aka unhinged loss) (van Rooyen et al., 2015). An equivalent (up to a
constant) symmetric loss named the reverse-CE (RCE) loss is proposed (Wang et
al., 2019), which reverses the predicted class probabilities and provided one-
hot vector encoding the given label information in computing the KL
divergence. Ma et al. (2020) show that a simple normalization trick can make
any loss functions to be symmetric, e.g., normalized CE (NCE) loss. However, a
symmetric loss alone might suffer from slow convergence issue for training
(Zhang & Sabuncu, 2018; Wang et al., 2019; Ma et al., 2020). To address this
issue, a loss that interpolates between the CE loss and a symmetric loss is
usually employed. This includes the symmetric-CE (SCE) loss (Wang et al.,
2019) that interpolates between the RCE loss and the CE loss, the generalized
CE loss (GCE) that interpolates the MAE loss and the CE loss, Jensen-Shannon
divergence (JS) loss that interpolates the MAE loss and the CE loss (Englesson
& Azizpour, 2021). These losses differ in the way of interpolation. Ma et al.
(2020) has generalized this principle to combine an active loss and a passive
loss and proposed several variants of robust losses, e.g., NCE + MAE.
Moreover, the symmetric property has been relaxed to bounded condition enjoyed
by the robust logistic loss (RLL) (Patel & Sastry, 2021) and mean-square-error
(MSE) loss (Ghosh et al., 2017), and also relaxed to asymmetric property (Zhou
et al., 2021) enjoyed by a class of asymmetric functions. The asymmetric loss
functions have been proved to be top-1 calibrated and hence top-1 consistent
(Zhou et al., 2021). However, according to their definition the asymmetric
losses cannot be top-$k$ consistent for any $k\geq 2$ because it contradicts
to the top-$k$ calibration (Yang & Koyejo, 2020) \- a necessary condition for
top-$k$ consistency. We provide a summary for the related robust and
traditional multi-class loss functions in Table 4.

Distributional robust optimization (DRO) Objective. It is worth mentioning the
difference from existing literature that leverages the DRO framework to model
the distributional shift between the training data distribution and testing
data distribution (Shalev-Shwartz & Wexler, 2016; Namkoong & Duchi, 2017; Qi
et al., 2020; Levy et al., 2020; Duchi et al., 2016; Duchi & Namkoong, 2021).
These existing works assign a distributional weight to each instance and
define an aggregate objective over all instances by taking the worse case over
the distributional weights in an uncertainty set that is formed by a
constraint function explicitly or a regularization implicitly. In contrast, we
study the loss function of an individual instance by using the DRO framework
to model the uncertainty in the label information, which models a
distributional shift between the true class distribution and the observed
class distribution given an instance.

##  3 The LDR Losses

Notations. Let $(\mathbf{x},y)\sim\mathbb{P}$ be a random data following
underlying true distribution $\mathbb{P}$, where
$\mathbf{x}\in\mathcal{X}\subseteq\mathbb{R}^{d}$ denotes an input data,
$y\in[K]:=\\{1,\ldots,K\\}$ denotes its class label. Let
$f(\mathbf{x})\in\mathcal{C}\subset\mathbb{R}^{K}$ denote the prediction
scores by a predictive function $f$ on data $\mathbf{x}$. Let
$f_{k}(\mathbf{x})$ denote the $k$-th entry of $f(\mathbf{x})$. Without
causing any confusion, we simply use the notation
$\mathbf{f}=(f_{1},\ldots,f_{K})=f(\mathbf{x})\in\mathcal{C}$ to denote the
prediction for any data $\mathbf{x}$. Interchangeably, we also use one-hot
encoding vector $\mathbf{y}\in\mathbb{R}^{K}$ to denote the label information
of a data. For any vector $\mathbf{q}\in\mathbb{R}^{K}$, let $q_{[k]}$ denote
the $k$-largest entry of $\mathbf{q}$ with ties breaking arbitrarily. Let
$\Delta_{K}=\\{\mathbf{p}\in\mathbb{R}^{K}:\sum_{k=1}^{K}p_{k}=1,p_{k}\geq
0\\}$ denote a $K$-dimensional simplex. Let
$\delta_{k,y}(f(\mathbf{x}))=f_{k}(\mathbf{x})-f_{y}(\mathbf{x})$ denote the
difference between two coordinates of the prediction scores $f(\mathbf{x})$.

###  3.1 Label-Distributionally Robust (LDR) Losses

A straightforward idea for learning a good prediction function is to enforce
that $f_{y}$ to be larger than any other coordinates of $\mathbf{f}$ with
possibly a large margin. However, this approach could mis-guide the learning
process due to that the label information $\mathbf{y}$ is often noisy, meaning
that the zero entries in $\mathbf{y}$ are not necessarily true zero, the entry
equal to one in $\mathbf{y}$ is not necessarily true one. To handle such
uncertainty in the label information, we propose to use a regularized DRO
framework to capture the inherent uncertainty in the label information.
Specifically, the proposed family of LDR losses is defined by:

$\displaystyle\psi_{\lambda}(\mathbf{x},y)=\max_{\mathbf{p}\in\Omega}\sum_{k=1}^{K}p_{k}(\delta_{k,y}(f(\mathbf{x}))+c_{k,y})-\lambda
R(\mathbf{p}),$ (1)

where $\mathbf{p}$ is referred to as Distributional Weight (DW) vector,
$\Omega\subseteq\\{\mathbf{p}\in\mathbb{R}^{K}:p_{k}\geq 0,\sum_{k}p_{k}\leq
1\\}$ is a convex constraint set for the DW vector $\mathbf{p}$,
$c_{k,y}=c_{y}\mathbb{I}(y\neq k)$ denotes the margin parameter with
$c_{y}\geq 0$, $\lambda>0$ is the DW regularization parameter, and
$R(\mathbf{p})$ is a regularization term of $\mathbf{p}$ which is set by a
strongly convex function. The strong convexity of $R(\mathbf{p})$ makes the
LDR losses smooth in terms of $f(\mathbf{x})$ due to the duality between
strongly convexity and smoothness (Kakade & Shalev-Shwartz, 2009; Nesterov,
2005). With a LDR loss, the risk minimization problem is formulated as
following, where $\mathrm{E}$ denotes the expectation:

$\displaystyle\min_{f:\mathcal{X}\rightarrow\mathbb{R}^{K}}L_{\psi}(f):=\mathrm{E}_{(\mathbf{x},y)\sim\mathbb{P}}[\psi_{\lambda}(\mathbf{x},y)].$
(2)

#### The LDR-KL Loss.

A special loss in the family of LDR losses is called the LDR-KL loss defined
by specifying $\Omega=\Delta_{K}$, and $R(\mathbf{p})$ as the KL divergence
between $\mathbf{p}$ and the uniform probabilities $(1/K,\ldots,1/K)$, i.e.,
$R(\mathbf{p})=\text{KL}(\mathbf{p},1/K)=\sum_{k=1}^{K}p_{k}\log(p_{k}K)$. In
this case, we can derive a closed-form expression of
$\psi_{\lambda}(\mathbf{x},y)$, denoted by
$\psi^{\text{KL}}_{\lambda}(\mathbf{x},y)$ (cf. Appendix B),

$\displaystyle\psi^{\text{KL}}_{\lambda}(\mathbf{x},y)=\lambda\log\bigg{[}\frac{1}{K}\sum_{k=1}^{K}\exp\left(\frac{f_{k}(\mathbf{x})+c_{k,y}-f_{y}(\mathbf{x})}{\lambda}\right)\bigg{]}.$
(3)

It is notable that the DW regularization parameter $\lambda$ is a key feature
of this loss. In many literature, this parameter is called the temperature
parameter, e.g., (Hinton et al., 2015; Chen et al., 2020). It is interesting
to see that the LDR-KL loss covers several existing losses as special cases or
extreme cases by varying the value of $\lambda$. We include the proof for the
analytical forms of these cases in the appendix for completeness.

Extreme Case I. $\lambda=0$. The loss function becomes:
$\psi^{\text{KL}}_{0}(\mathbf{x},y)=\max(0,\max_{k\neq
y}f_{k}(\mathbf{x})+c_{y}-f_{y}(\mathbf{x}))$ which is known as Crammer-Singer
loss (an extension of hinge loss) for multi-class SVM (Crammer & Singer,
2002).

Extreme Case II. $\lambda=\infty$. The loss function becomes:
$\psi^{\text{KL}}_{\infty}(\mathbf{x},y)=\frac{1}{K}\sum_{k=1}^{K}(f_{k}(\mathbf{x})-f_{y}(\mathbf{x})+c_{k,y})$,
which is similar to the Weston-Watkins (WW) loss (Weston & Watkins, 1998)
given by $\sum_{k\neq y}\max(0,f_{k}(\mathbf{x})-f_{y}(\mathbf{x})+1)$.
However, WW loss is not top-1 consistent but the LDR-KL loss when
$\lambda=\infty$ is top-1 consistent (Zhang, 2004).

A Special Case. When $\lambda=1$, the LDR-KL loss becomes the CE loss (with a
margin parameter):
$\psi^{\text{KL}}_{1}(\mathbf{x},y)=\log\left(\sum_{k}\exp\left(f_{k}(\mathbf{x})+c_{k,y}-f_{y}(\mathbf{x})\right)\right)$.
It is notable that in standard CE loss, the margin parameter $c_{y}$ is
usually set to be zero. Adding a margin parameter makes the above CE loss
enjoys the large-margin benefit. This also recovers the label-distribution-
aware margin loss proposed by (Cao et al., 2019) for imbalanced data
classification with different margin values $c_{y}$ for different classes.

###  3.2 Consistency

Consistency is an important property of a loss function. In this section, we
establish the consistency of LDR losses. A standard consistency is for
achieving Bayes optimal top-$1$ error. We will show much stronger consistency
for achieving Bayes optimal top-$k$ error for any $k\in[K]$. To this end, we
first introduce some definitions and an existing result of sufficient
condition of top-$k$ consistency by top-$k$ calibration (Yang & Koyejo, 2020).

For any vector $\mathbf{f}\in\mathbb{R}^{K}$, we let $r_{k}(\mathbf{f})$
denote a top-$k$ selector that selects the $k$ indices of the largest entries
of $\mathbf{f}$ by breaking ties arbitrarily. Given a data $(\mathbf{x},y)$,
its top-$k$ error is defined as
$\text{err}_{k}(f,\mathbf{x},y)=\mathbb{I}(y\not\in r_{k}(f(\mathbf{x})))$.
The goal of a classification algorithm under the top-$k$ error metric is to
learn a predictor $f$ that minimizes the error:
$L_{\text{err}_{k}}(f)=\mathrm{E}_{(\mathbf{x},y)\sim\mathbb{P}}[\text{err}_{k}(f,\mathbf{x},y)]$.
The predictor $f^{*}(\cdot):\mathcal{X}\rightarrow\mathbb{R}^{K}$ is top-$k$
Bayes optimal if
$L_{\text{err}_{k}}(f^{*})=L^{*}_{\text{err}_{k}}:=\inf_{f\in\mathcal{F}}L_{\text{err}_{k}}(f)$.
Since we can not directly optimize the top-$k$ error, we usually optimize a
risk function using a surrogate loss, e.g., (2). A central question of
consistency is that whether optimizing the risk function can optimize the
top-$k$ error.

######  Definition 1.

For a fixed $k\in[K]$, a loss function $\psi$ is top-$k$ consistent if for any
sequence of measurable functions
$f^{(n)}:\mathcal{X}\rightarrow\mathbb{R}^{K}$, we have

$\displaystyle L_{\psi}(f^{(n)})\rightarrow L^{*}_{\psi}\Longrightarrow
L_{\text{err}_{k}}(f^{(n)})\rightarrow L_{\text{err}_{k}}^{*}$

where $L_{\psi}^{*}=\min_{f}L_{\psi}(f)$. If the above holds for all
$k\in[K]$, it is referred to as All-$k$ consistency.

According to (Yang & Koyejo, 2020), a necessary condition for top-$k$
consistency of a multi-class loss function is that the loss function is
top-$k$ calibrated defined below. Since top-$k$ calibration characterizes when
minimizing $\psi$ for a fixed $\mathbf{x}$ leads to the Bayes decision for
that $\mathbf{x}$, we will consider $\mathbf{f}=f(\mathbf{x})$ for any fixed
$\mathbf{x}\in\mathcal{X}$ and let
$\mathbf{q}=\mathbf{q}(\mathbf{x})=(\Pr(y=1|\mathbf{x}),\ldots,\Pr(y=K|\mathbf{x}))$
be the underlying conditional label distribution. Define
$L_{\psi}(\mathbf{f},\mathbf{q})=\sum_{l}q_{l}\psi(\mathbf{x},l)$. Let
$P_{k}(\mathbf{f},\mathbf{q})$ denote that $\mathbf{f}$ is top-$k$ preserving
with respect to the underlying label distribution $\mathbf{q}$, i.e., if for
all $l\in[K]$, $q_{l}>q_{[k+1]}\Longrightarrow f_{l}>f_{[k+1]}$, and
$q_{l}<q_{[k]}\Longrightarrow f_{l}<f_{[k]}$.

######  Definition 2.

For a fixed $k\in[K]$, a loss function $\psi$ is called top-$k$ calibrated if
for all $\mathbf{q}\in\Delta_{K}$ it holds that:
$\inf_{\mathbf{f}\in\mathbb{R}^{K}:\neg
P_{k}(\mathbf{f},\mathbf{q})}L_{\psi}(\mathbf{f},\mathbf{q})>\inf_{\mathbf{f}\in\mathbb{R}^{K}}L_{\psi}(\mathbf{f},\mathbf{q})$.
A loss function is called All-$k$ calibrated if the loss function $\psi$ is
top-$k$ calibrated for all $k\in[K]$.

Unlike (Yang & Koyejo, 2020) that relies on top-$k$ preserving property of
optimal predictions, we will use rank preserving property of optimal
predictions to prove All-$k$ calibration and consistency. $\mathbf{f}$ is
called rank preserving w.r.t $\mathbf{q}$, i.e., if for any pair $q_{i}<q_{j}$
it holds that $f_{i}<f_{j}$. Our lemma below shows that if the optimal
predictions for minimizing $L_{\psi}$ is rank preserving, then $\psi$ is
All-$k$ calibrated. All missing proofs are included in appendix.

######  Lemma 1.

For any $\mathbf{q}\in\Delta_{K}$, if
$\mathbf{f}^{*}=\arg\min_{\mathbf{f}\in\mathbb{R}^{K}}L_{\psi}(\mathbf{f},\mathbf{q})$
is rank preserving with respect to $\mathbf{q}$, then $\psi$ is All-$k$
calibrated.

Our first main result of consistency is the following.

######  Theorem 1.

If $c_{y}=c$, $\forall y\in[K]$, then
$\mathbf{f}^{*}=\arg\min_{\mathbf{f}\in\mathbb{R}^{K}}L_{\psi_{\lambda}^{\text{KL}}}(\mathbf{f},\mathbf{q})$
is rank preserving for any $\lambda\in(0,\infty)$ and hence the LDR-KL loss
$\psi_{\lambda}^{\text{KL}}$ with any $\lambda\in(0,\infty)$ is All-$k$
calibrated. Therefore, it is All-$k$ consistent.

Calibration of the general LDR losses: we present a sufficient condition on
the DW regularization function $R$ such that the resulting LDR loss
$\psi_{\lambda}$ is All-$k$ calibrated. The result below will address an open
problem in (Lapin et al., 2018) regarding the consistency of smoothed top-$k$
SVM loss.

######  Definition 3.

A function $R(\mathbf{p})$ is input-symmetric if its value is the same, no
matter the order of its arguments. A set $\Omega$ is symmetric, if a point
$\mathbf{p}$ is in the set then so is any point obtained by interchanging any
two coordinates of $\mathbf{p}$.

######  Theorem 2.

If $c_{y}=c,\forall y\in[K]$, $R$ and $\Omega$ are (input-) symmetric, $R$ is
strongly convex satisfying $\partial R(0)<0$ and $[\partial
R(p)]_{i}>0\Longrightarrow p_{i}\neq 0$, then the family of LDR losses
$\psi_{\lambda}$ with any $\lambda\in(0,\infty)$ is All-$k$ calibrated.

Remark:  Examples of $R$ that satisfy the above conditions include
$R(\mathbf{p})=\sum_{i}p_{i}\log(Kp_{i})$ and
$R(\mathbf{p})=\|\mathbf{p}-1/K\|^{2}$.

Consistency of smoothed top-$k$ SVM losses. As an application of our result
above, we restrict our attention to
$\Omega=\Omega(k)=\\{\mathbf{p}\in\mathbb{R}^{K}:\sum_{l=1}^{K}p_{l}\leq
1,p_{l}\leq 1/k,\forall l\\}$. When $\lambda=0$, the LDR loss becomes the
top-$k$ SVM loss (Lapin et al., 2018), i.e.,

$\displaystyle\psi^{k}_{\lambda=0}(\mathbf{x},y)$
$\displaystyle=\max_{\mathbf{p}\in\Omega(k)}\sum_{l}p_{l}(\delta_{l,y}(f(\mathbf{x}))+c_{l,y})$
$\displaystyle=\frac{1}{k}\sum_{i=1}^{k}\max(0,\mathbf{f}-f_{y}+\mathbf{c}_{y})_{[i]},$

where $\mathbf{c}_{y}=(c_{1,y},\ldots,c_{K,y})$. This top-$k$ SVM loss is not
consistent acoording to (Lapin et al., 2018). But, we can make it consistent
by adding a strongly convex regularizer $R(\mathbf{p})$ satisfying the
conditions in Theorem 2. This addresses the open problem raised in (Lapin et
al., 2018) regarding the consistency of smoothed top-$k$ SVM loss for multi-
class classification.

###  3.3 Robustness

######  Definition 4.

A loss function $\psi$ is symmetric if:
$\sum_{j=1}^{K}\psi\big{(}\mathbf{x},j\big{)}$ is a constant for any
$f,\mathbf{x}$.

A loss with the symmetric property is noise-tolerant against uniform noise and
class dependent noise under certain conditions (Ghosh et al., 2017). For
example, under uniform noise if the probability of noise label $\hat{y}$ not
equal to true label $y$ is not significantly large, i.e., $\Pr(\hat{y}\neq
y|y)<1-\frac{1}{K}$, then the optimal predictor for optimizing
$\mathrm{E}_{\mathbf{x},\hat{y}}[\psi(\mathbf{x},\hat{y})]$ is the same as
optimizing the true risk $\mathrm{E}_{\mathbf{x},y}[\psi(\mathbf{x},y)]$.

Next, we present a negative result showing that a non-negative symmetric loss
cannot be All-$k$ consistent.

######  Theorem 3.

A non-negative symmetric loss function cannot be top-$1,2$ consistent
simultaneously when $K\geq 3$.

Remark:  The above theorem indicates that it is impossible to design a non-
negative loss that is not only symmetric but also All-$k$ consistent. Exemplar
non-negative symmetric losses include MAE (or SCE or unhinged loss) and NCE,
which are top-1 consistent but not All-$k$ consistent.

Next, we show a way to break the impossibility by using a symmetric loss that
is not necessarily non-negative, e.g., the LDR-KL loss with $\lambda=+\infty$.

######  Theorem 4.

When $\lambda=\infty$, the LDR-KL loss enjoys symmetric property, and is
All-$k$ consistent when
$\mathcal{C}=\\{\mathbf{f}\in\mathbb{R}^{K},\|\mathbf{f}\|_{2}\leq B\\}$.

Remark:  Theorem 3 is proved for general case, and Theorem 4 only holds with
the extra constrain.

###  3.4 Adaptive LDR-KL (ALDR-KL) Loss

Although LDR-KL with $\lambda=\infty$ is both robust and consistent, it may
suffer from the slow convergence issue similar to the MAE loss (Zhang &
Sabuncu, 2018). We design an Adaptive LDR-KL (ALDR-KL) loss for the data with
label noises, which can automatically adjust DW regularization parameter
$\lambda$ for individual data. The motivation is: i) for those noisy data, the
model is less confident and we want to make the $\lambda$ to be larger, so
that loss function is more robust; ii) for those clean data, the model is more
confident and we want to make the $\lambda$ to be smaller to enjoy the large
margin property of the CS loss.

To this end, we propose the following ALDR-KL loss:

$\displaystyle\psi_{\alpha,\lambda_{0}}^{\text{KL}}(\mathbf{x},y)=$
$\displaystyle\max_{\lambda\in\mathbb{R}_{+}}\max_{\mathbf{p}\in\Delta_{K}}\sum_{k=1}^{K}p_{k}(\delta_{k,y}(f(\mathbf{x}))+c_{k,y})$
$\displaystyle-\lambda\text{KL}(\mathbf{p},\frac{1}{K})-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}.$
(4)

where $\alpha>0$ is a hyper-parameter, and $\lambda_{0}$ is a relatively large
value. To intuitively understand this loss, we consider when the given label
is clean and noisy. If the given label is clean, then it is better to push the
largest $f_{k}(\mathbf{x}),k\neq y$ to be small, hence a spiked $\mathbf{p}$
would be better, as a result $\text{KL}(\mathbf{p},1/K)$ would be large; so by
maximizing $\lambda$ it will push $\lambda$ to be smaller. On the other hand,
if the given label is noisy, then it is better to use uniform $\mathbf{p}$
(otherwise it may wrongly penalize more on predictions for the “good" class
labels), as a result $\text{KL}(\mathbf{p},1/K)$ would be small, then by
maximizing over $\lambda$ it will push $\lambda$ to be close to the prior
$\lambda_{0}$.

To elaborate this intuition, we conduct an experiment on a simple synthetic
data. We generate data for three classes from four normal distributions with
means at (0.8,0.8), (0.8,-0.8), (-0.8,0.8), (-0.8,-0.8) and standard
deviations equal to (0.3, 0.3) as shown in Figure 1 (left). To demonstrate the
adpative $\lambda$ mechanism of ALDR-KL, we first pretrain the model by
optimizing the CE loss by 1000 epochs with momentum optimizer and learning
rate as 0.01. Then, we add an extra hard but clean example from the $\circ$
class (the blue point in the dashed circle), and a noisy data from the $\circ$
class but mislabeled as the $\diamond$ class (the red point in the dashed
circle), and then finetune the model with extra 100 epochs by optimizing our
ALDR-KL loss with Algorithm 1 and optimizing CE loss with momentum SGD. We set
the $\lambda_{0}=10,\alpha=0.05$ for ALDR-KL loss. The learned model of using
ALDR-KL loss (right) is more robust than that of using CE loss (middle). We
also show the corresponding learned $\lambda_{T}$ values at the last iteration
for the two added examples, which show that the noisy data has a large
$\lambda=8.4$ and the clean data has a small $\lambda=0.001$. We also plot the
averaged $\lambda_{t}$ and the KL-divergence values
$\text{KL}(\mathbf{p}_{t},1/K)$ during the training process in Figure 3 of
Appendix, which clearly shows the negative relationship between them.
Additionally, we provide more synthetic experiments for LDR-KL loss by
training from scratch in Appendix L.6, where the observations are consistent
with the conclusion here.

The theoretical properties of ALDR-KL are stated below.

######  Theorem 5.

The ALDR-KL loss is All-$k$ consistent when $c_{y}=0,\forall
y,\lambda_{0}\in(0,\infty),\alpha>\frac{\log K}{\lambda_{0}}$ or
$\lambda_{0}=\infty,\mathcal{C}=\\{\mathbf{f}\in\mathbb{R}^{K},\|\mathbf{f}\|_{2}\leq
B\\}$, and is Symmetric when $\lambda_{0}=\infty$.

Algorithm 1 Stochastic Optimization for ALDR-KL loss

0: $\eta,\alpha,\beta,\lambda_{0}$

1: Random initialize model parameters $\mathbf{w}_{0}$; initialize
$\lambda^{i}_{0}$ as $\lambda_{0}$ for each data sample, $i\in[n]$; initialize
$\mathbf{m}_{0}=0$.

2: for $t=1,...T$ do

3: Sample mini-batch of data indices $\mathcal{B}_{t}$

4: for each sample $i\in\mathcal{B}_{t}$ do

5: Compute $\mathbf{p}^{i}_{t-1}$ by E.q. 6 with $\lambda_{t-1}^{i}$,
$f(\mathbf{x}_{i},\mathbf{w}_{t-1})$.

6: Update
$\lambda_{t}^{i}=[\lambda_{0}-\frac{1}{\alpha}\text{KL}(\mathbf{p}^{i}_{t-1},\frac{1}{K})]_{+}$

7: Compute $G(\lambda^{i}_{t},\mathbf{w}_{t-1},\mathbf{x}_{i})$ by E.q. 8

8: end for

9: Compute mini-batch gradient estimation
by:$G(\mathbf{w}_{t-1})=\frac{1}{|\mathcal{B}_{t}|}\sum_{i\in\mathcal{B}_{t}}G(\lambda^{i}_{t},\mathbf{w}_{t-1},\mathbf{x}_{i})$

10: Compute
$\mathbf{m}_{t}=\beta\mathbf{m}_{t-1}+(1-\beta)G(\mathbf{w}_{t-1})$

11: Update $\mathbf{w}_{t}=\mathbf{w}_{t-1}-\eta\mathbf{m}_{t}$

12: end for

Figure 1: Left: pretrained model on a synthetic data; Middle: a new model
learned by optimizing the CE loss after adding two examples in dashed circle;
Right: a new model learned by optimizing the ALDR-KL loss after adding two
examples in dashed circle. Shape denotes the true label, and color denotes the
given label.

Optimization for ALDR-KL loss: Using ALDR-KL loss and with a finite set of
examples $\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$, the empirical risk
minimization problem becomes:

$\displaystyle\min_{\mathbf{w}}\frac{1}{n}\sum\nolimits_{i=1}^{n}\psi_{\alpha,\lambda_{0}}^{\text{KL}}(\mathbf{x}_{i},y_{i}),$
(5)

where $\mathbf{w}$ denotes the parameter of the prediction function
$f(\cdot;\mathbf{w})$. Below, we will present how to solve this problem
without causing significant more burden than optimizing traditional CE loss.
Recall that the formulation for LDR-KL in (3), it is easy to show that:

$\displaystyle\psi_{\alpha,\lambda_{0}}^{\text{KL}}(\mathbf{x},y)=\max_{\lambda\in\mathbb{R}_{+}}-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}$
$\displaystyle+$
$\displaystyle\lambda\log\left(\sum_{k=1}^{K}\exp\left(\frac{f_{k}(\mathbf{x})+c_{k,y}-f_{y}(\mathbf{x})}{\lambda}\right)\right),$

where we have used the closed-form solution for $\mathbf{p}$ given $\lambda$:

$\displaystyle
p^{*}_{k}(\lambda)\propto\exp\left(\frac{f_{k}(\mathbf{x};\mathbf{w})+c_{k,y}-f_{y}(\mathbf{x};\mathbf{w})}{\lambda}\right),\forall
k.$ (6)

To compute the $\lambda$, first by optimality condition ignoring the non-
negative constraint we have
$-\text{KL}(\mathbf{p}^{*},\frac{1}{K})-\alpha(\lambda-\lambda_{0})=0.$ This
motivate us to update $\lambda$ alternatively with $\mathbf{p}$. Given
$\lambda^{i}_{t-1}$ for an individual data $\mathbf{x}_{i}$ at the $(t-1)$-th
iteration, we compute $\mathbf{p}^{i}_{t-1}$ according to (6) then we update
$\lambda^{i}_{t}$ according to the above equation with $\mathbf{p}^{*}$
replaced by $\mathbf{p}^{i}_{t-1}$ and a projection onto non-negative orthant
$\mathbb{R}_{+}$:

$\displaystyle\lambda^{i}_{t}=\left[\lambda_{0}-\frac{1}{\alpha}\text{KL}(\mathbf{p}^{i}_{t-1},\frac{1}{K})\right]_{+}.$
(7)

For updating the model parameter $\mathbf{w}$, at iteration $t$ suppose we
have the current estimation for $\lambda_{t}$, we can compute the stochastic
gradient estimation for $\mathbf{w}_{t-1}$ as:

$\displaystyle G(\lambda^{i}_{t},\mathbf{w}_{t-1},\mathbf{x}_{i})=$ (8)
$\displaystyle\nabla_{\mathbf{w}}\lambda^{i}_{t}\log\sum_{k=1}^{K}\exp\left(\frac{f_{k}(\mathbf{x}_{i},\mathbf{w}_{t-1})+c_{k,y}-f_{y}(\mathbf{x}_{i},\mathbf{w}_{t-1})}{\lambda^{i}_{t}}\right)$

Finally, we provide the algorithm using the momentum update for optimizing
ALDR-KL loss in Alg. 1. It is notable that other updates (e.g., SGD, Adam) can
be used for updating $\mathbf{w}_{t}$ as well. It is worth noting that we
could also use gradient method to optimize $\lambda$ and $\mathbf{p}$, but it
will involve tuning two extra learning rates. Empirically we verify that Alg.
1 converges well for optimizing the ALDR-KL loss, which is presented in
Appendix L for interested readers and the convergence analysis is left as a
future work.

##  4 Experiments

In this section, we present the datasets, experimental settings, experimental
results, and ablation study regarding the adaptiveness in terms of $\lambda$
for ALDR-KL loss. For all the experiments unless specified otherwise, we
manually add label noises to the training and validation data, but keep the
testing data clean. A similar setup was used in (Zhang & Sabuncu, 2018), which
simulates the noisy datasets in practice. We compare with all loss functions
in Table 4 except for NCE, which is replaced by NCE+RCE following (Ma et al.,
2020) and NCE+AGCE, NCE+AUL following (Zhou et al., 2021). Detailed
expressions of these losses with hyper-parameters are shown in Table 4. We do
not compare the Generalized JS Loss (GJS) because it relies on extra
unsupervised data augmentation and need more computational cost (Englesson &
Azizpour, 2021). For all experiments, we utilize the identical optimization
procedures and models, only with different losses.

###  4.1 Benchmark Datasets with Synthetic Noise

We conduct experiments on 7 benchmark datasets, namely ALOI, News20, Letter,
Vowel (Fan & Lin, ), Kuzushiji-49, CIFAR-100 and Tiny-ImageNet (Clanuwat et
al., 2018; Deng et al., 2009). The number of classes vary from 11 to 1000. The
statistics of the datasets are summarized in Table 5 in the Appendix. We
manually add different noises to the datasets. Similar to previous works
(Zhang & Sabuncu, 2018; Wang et al., 2019), we consider two different noise
settings, uniform (symmetric) noise and class dependent (asymmetric) noise.
For uniform noise, we impose a uniform random noise with the probability
$\xi\in\\{0.3,0.6,0.9\\}$ such that a data label is changed to any label in
$\\{1,...,K\\}$ with a probability $\xi$. We would like to point out that the
uniform noise rate $0.9$ should be tolerable according the theory of a
symmetric loss, which can tolerate uniform noise rate up to $(1-1/K)>0.9$,
where $K$ is larger than 10 for the considered datasets. For class dependent
noise, with the probability in $\xi\in\\{0.1,0.3,0.5\\}$, a data label could
be changed to another label by following pre-defined transition rules. For
letter dataset: $B\leftrightarrow D$, $C\leftrightarrow G$, $E\leftrightarrow
F$, $H\leftrightarrow N$, $I\leftrightarrow L$, $K\leftrightarrow X$,
$M\leftrightarrow W$, $O\leftrightarrow Q$, $P\leftrightarrow R$,
$U\leftrightarrow V$. For news20 dataset: comp.os.ms-windows.misc
$\leftrightarrow$ comp.windows.x, comp.sys.ibm.pc.hardware $\leftrightarrow$
comp.sys.mac.hardware, rec.autos $\leftrightarrow$ rec.motorcycles,
rec.sport.baseball $\leftrightarrow$ rec.sport.hockey, sci.crypt
$\leftrightarrow$ sci.electronics, soc.religion.christian $\leftrightarrow$
talk.politics.misc. For vowel dataset: $i\leftrightarrow I$, $E\leftrightarrow
A$, $a:\leftrightarrow Y$, $C:\leftrightarrow O$, $u:\leftrightarrow U$. For
ALOI, Kuzushiji-49, CIFAR-100 and Tiny-ImageNet datasets, we simulate class-
dependent noise by flipping each class into the next one circularly with
probability $\xi$.

For all datasets except for Kuzushiji-49, CIFAR-100 and Tiny-ImageNet, we
uniformly randomly split 10% of the whole data as testing data, and the
remaining as training set. For Kuzushiji-49 and CIFAR-100 dataset, we use its
original train/test splitting. For Tiny-ImageNet, we use its original
train/validation splitting and treat the validation data as the testing data
in this work. For News20 dataset, because the original dimension is too large,
we apply PCA to reduce the dimension to 80% variance level.

###  4.2 Experimental Settings

Since ALOI, News20, Letter and Vowel datasets are tabular data, we use a
2-layer feed forward neural network, with a number of neurons in the hidden
layer same as the number of features or the number of classes (whichever is
smaller) as the backbone model for these four datasets. ResNet18 is utilized
as the backbone model for Kuzushiji-49, CIFAR100 and Tiny-ImageNet image
datasets (He et al., 2016). We apply 5-fold-cross-validation to conduct the
training and evaluation, and report the mean and standard deviation for the
testing top-$k$ accuracy, where $k\in\\{1,2,3,4,5\\}$. We use early stopping
according to the highest accuracy on the validation data. For Kuzushiji-49
dataset, the top-$k$ accuracy is first computed in class level, and then
averaged across the classes according to (Clanuwat et al., 2018) because the
classes are imbalanced.

We fix the weight decay as 5e-3, batch size as 64, and total running epochs as
100 for all the datasets except Kuzushiji, CIFAR100 and Tiny-ImageNet (we run
30 epochs for them because the data sizes are large). We utilize the momentum
optimizer with the initial learning rate tuned in {1e-1, 1e-2, 1e-3} for all
experiments. We decrease the learning rate by ten-fold at the end of the 50th
and 75th epoch for 100-total-epoch experiments, and at the end of 10th and
20th epoch for 30-total-epoch experiments. For CE, MSE and MAE loss, there is
no extra parameters need to be tuned; for CS and WW loss, we tune the margin
parameter at {0.1, 1, 10}; for RLL loss, we tune the $\alpha$ parameter at
{0.1, 1, 10}; for GCE and TGCE loss, we tune the power parameter $q$ at {0.05,
0.7, 0.95} and set truncate parameter as 0.5 for TGCE; for SCE, as suggested
in the original paper, we fix A=-4 and tune the simplified balance parameter
between CE and RCE at {0.05, 0.5, 0.95}; for JS loss, we tune the balance
parameter at {0.1, 0.5, 0.9}; for NCE+(RCE,AGCE,AUL) loss, we keep the default
parameters for each individual loss, and tune the two weight parameters
$\alpha/\beta$ in {0.1/9.9, 5/5, 9.9/0.1} following the original papers. For
LDR-KL and ALDR-KL loss, we tune the DW regularization parameter $\lambda$ or
the $\lambda_{0}$ at $\\{0.1,1,10\\}$. We normalize model logits
$\mathbf{f}(\mathbf{x};\mathbf{w})$ by
$\frac{\|\mathbf{f}(\mathbf{x};\mathbf{w})\|_{1}}{K}$ so that different
$\lambda$ values can achieve the different intended effects for LDR-KL and
ALDR-KL loss. The margin parameter is fixed as 0.1 for all experiments. For
ALDR-KL, we set the $\alpha=\frac{2\log K}{\lambda_{0}}$, so that
$\lambda_{t}^{i}=\lambda_{0}-\frac{1}{\alpha}\text{KL}(\mathbf{p}_{t-1}(\mathbf{x}_{i})\|\frac{1}{K})\in[\lambda_{0}/2,\lambda_{0}]$,
which maintains an appropriate adaptive adjustment level from $\lambda_{0}$.

###  4.3 Leaderboard on seven benchmark data

We compare 15 losses on 7 benchmark datasets over 6 noisy and 1 clean settings
for 5 metrics with 3,675 numbers. However, due to limit of space it is
difficult to include the results here. Instead, we focus on the overall
results on all datasets in all settings by presenting a leaderboard in Table
3. For each data in each setting, we rank different losses from $1$ to $15$
according to their performance from high to low (the smaller the rank value
meaning the better of the performance). We average the ranks across all the
benchmark datasets in all settings for top-$k$ accuracy with different $k$ and
we also provide an overall rank.

We present the full results and their analysis for different performance
metrics in the Appendix L. From the leaderboard in Table 3, we observe that
the ALDR-KL loss is the strongest and followed by LDR-KL loss. Besides, the CE
loss and two variants (SCE, GCE) are more competitive than the other loss
functions. The symmetric MAE loss is non-surprisingly the worst which implies
consistency is also an important factor for learning with noisy data.

Table 2: leaderboard for comparing 15 different loss functions on 7 datasets
in 6 noise and 1 clean settings. The reported numbers are averaged ranks of
performance. The smaller the better.

Loss Function | top-1 | top-2 | top-3 | top-4 | top-5 | overall
---|---|---|---|---|---|---
ALDR-KL | 2.163 | 2.449 | 2.184 | 2.224 | 2.633 | 2.331
LDR-KL | 2.429 | 2.571 | 2.816 | 2.939 | 2.959 | 2.743
CE | 4.714 | 4.592 | 4.224 | 4.449 | 4.388 | 4.473
SCE | 4.898 | 4.776 | 4.429 | 4.837 | 4.327 | 4.653
GCE | 5.816 | 5.347 | 6.041 | 5.571 | 5.551 | 5.665
TGCE | 6.204 | 6.224 | 6.265 | 6.224 | 6.306 | 6.245
WW | 7.673 | 6.592 | 6.082 | 5.959 | 5.551 | 6.371
JS | 7.816 | 7.837 | 7.857 | 7.98 | 8.245 | 7.947
CS | 8.673 | 8.878 | 8.816 | 8.592 | 8.735 | 8.739
RLL | 10.224 | 10.204 | 10.224 | 10.49 | 10.49 | 10.326
NCE+RCE | 9.694 | 10.633 | 10.878 | 10.612 | 10.714 | 10.506
NCE+AUL | 10.449 | 10.959 | 11.102 | 11.224 | 11.122 | 10.971
NCE+AGCE | 11.714 | 11.837 | 11.837 | 11.51 | 11.714 | 11.722
MSE | 12.796 | 12.653 | 12.776 | 12.959 | 12.898 | 12.816
MAE | 14.735 | 14.449 | 14.469 | 14.429 | 14.367 | 14.49

Table 3: Top-1 Accuracy on ILSVRC12 validation data with models trained on
mini-webvision.

Loss | NCE+RCE | SCE | GCE | JS | CE | AGCE | LDR-KL | ALDR-KL
---|---|---|---|---|---|---|---|---
ACC | 60.24 | 62.44 | 62.76 | 65.00 | 66.40 | 67.52 | 69.00 | 69.92

(a) $\lambda_{0}=1$, CD(0.1) (b) $\lambda_{0}=10$, CD(0.1) (c)
$\lambda_{0}=1$, U(0.3) (d) $\lambda_{0}=10$, U(0.3)

Figure 2:  Averaged $\lambda_{t}$ values for noisy samples and clean samples
with error bar for ALDR-KL loss on Vowel dataset, ‘U’ is short for uniform
noise, ‘CD’ is short for class-dependent noise.

###  4.4 Real-world Noisy Data

We evaluate the proposed methods on a real-world noisy dataset, namely
webvision (Li et al., 2017). It contains more than 2.4 million of web images
crawled from the Internet by using queries generated from the same 1,000
semantic concepts as the benchmark ILSVRC 2012 dataset. We mainly follow the
settings on the previously work (Zhou et al., 2021; Ma et al., 2020; Englesson
& Azizpour, 2021) by using a mini version, i.e., taking the first 50 classes
from webvision as training data, and evaluating the results on ILSVRC12
validation data. More details about the experimental settings are summarized
in the Appendix L.3. ResNet50 is utilized as the backbone model (He et al.,
2016). The results summarized in Table 3 show ALDR-KL performs the best
followed by LDR-KL. We notice that (Englesson & Azizpour, 2021) reports a
higher result for JS than that in Table 3, which is due to different setups,
especially with more epochs, larger weight decay and tuning of learning rates.
Following the same experimental setup as (Englesson & Azizpour, 2021), our
ALDR-KL and LDR-KL achieve 70.80 and 70.64 for top-1 accuracy, respectively,
while JS’s is reported as 70.36.

###  4.5 Adaptive $\lambda$ for ALDR-KL loss

Lastly, we conduct experiments to illustrate the adaptive $\lambda_{t}^{i}$
values learned by using ALDR-KL loss on the Vowel dataset with uniform noise
($\xi=0.3$) and class dependent noise ($\xi=0.1$). We maintain the adaptive
$\lambda_{t}^{i}$ values for noisy data samples and clean data samples
separately at each epoch. Then we output the mean and standard deviation for
the adaptive $\lambda_{t}^{i}$ values for noisy data and clean data.
$\lambda_{0}\in\\{1,10\\}$ are adopted for ALDR-KL at this subsection. All the
settings are identical with previous experimental setups except initial
learning rate is fixed as $1e-2$ for this specific justification experiment.
The results are presented in Figure 2. From the figures, we observe that ALDR-
KL applies larger DW regularization parameter $\lambda$ for the noisy data,
which makes ALDR-KL loss closer to symmetric loss function, and therefore it
is more robust to certain types of noises (e.g. uniform noise, simple non-
uniform noise and class dependent noise) (Ghosh et al., 2017). Besides, the
adaptive $\lambda_{t}^{i}$ values are generally decreasing for both noisy and
clean data because the model is more certain about its predictions with more
training steps.

###  4.6 Running Time

We provide the running time analysis for the LDR-KL and ALDR-KL loss in Table
17 in Appendix L.7. We observe that the running time of optimizing ALDR-KL is
slightly higher than that of optimizing the CE loss, it is still comparable
with optimizing other robust losses such as TGCE, SCE, RLL, etc.

##  5 Conclusions

We proposed a novel family of Label Distributional Robust (LDR) losses. We
studied consistency and robustness of proposed losses. We also proposed an
adaptive LDR loss to adapt to the noisy degree of individual data. Extensive
experiments demonstrate the effectiveness of our new losses, LDR-KL and ALDR-
KL losses.

##  6 Acknowledgement

This work is partially supported by NSF Career Award 2246753, NSF Grant
2246757 and NSF Grant 2246756. The work of Yiming Ying is partially supported
by NSF (DMS-2110836, IIS-2110546, and IIS-2103450).

## References

  * Beyer et al. (2020) Beyer, L., Hénaff, O. J., Kolesnikov, A., Zhai, X., and van den Oord, A.  Are we done with imagenet?  _CoRR_ , abs/2006.07159, 2020.  URL https://arxiv.org/abs/2006.07159.
  * Brown et al. (2020) Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D.  Language models are few-shot learners.  _CoRR_ , abs/2005.14165, 2020.  URL https://arxiv.org/abs/2005.14165.
  * Cao et al. (2019) Cao, K., Wei, C., Gaidon, A., Arechiga, N., and Ma, T.  Learning imbalanced datasets with label-distribution-aware margin loss.  In _Advances in Neural Information Processing Systems 32 (NeurIPS)_ , pp. 1567–1578, 2019.
  * Chen et al. (2020) Chen, T., Kornblith, S., Norouzi, M., and Hinton, G.  A simple framework for contrastive learning of visual representations.  In _Proceedings of the 37th International Conference on Machine Learning_ , pp. 1597–1607, 2020.
  * Clanuwat et al. (2018) Clanuwat, T., Bober-Irizar, M., Kitamoto, A., Lamb, A., Yamamoto, K., and Ha, D.  Deep learning for classical japanese literature.  _arXiv preprint arXiv:1812.01718_ , 2018.
  * Crammer & Singer (2002) Crammer, K. and Singer, Y.  On the algorithmic implementation of multiclass kernel-based vector machines.  _J. Mach. Learn. Res._ , 2:265–292, March 2002.  ISSN 1532-4435.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 248–255, 2009.
  * Duchi et al. (2016) Duchi, C. J., Glynn, W. P., and Namkoong, H.  Statistics of robust optimization: A generalized empirical likelihood approach.  _Mathematics of Operations Research_ , 2016.
  * Duchi & Namkoong (2021) Duchi, J. C. and Namkoong, H.  Learning models with uniform performance via distributionally robust optimization.  _The Annals of Statistics_ , 49(3):1378–1406, 2021.
  * Englesson & Azizpour (2021) Englesson, E. and Azizpour, H.  Generalized jensen-shannon divergence loss for learning with noisy labels.  _Advances in Neural Information Processing Systems_ , 34:30284–30297, 2021.
  * (11) Fan, R.-E. and Lin, C.-J.  Libsvm data.  https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.
  * Geusebroek et al. (2005) Geusebroek, J.-M., Burghouts, G. J., and Smeulders, A. W.  The amsterdam library of object images.  _International Journal of Computer Vision_ , 61(1):103–112, 2005.
  * Ghosh et al. (2017) Ghosh, A., Kumar, H., and Sastry, P.  Robust loss functions under label noise for deep neural networks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 31, 2017.
  * Goldberger & Ben-Reuven (2017) Goldberger, J. and Ben-Reuven, E.  Training deep neural-networks using a noise adaptation layer.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/forum?id=H12GRgcxg.
  * Han et al. (2018) Han, B., Yao, J., Niu, G., Zhou, M., Tsang, I. W., Zhang, Y., and Sugiyama, M.  Masking: A new perspective of noisy supervision.  _CoRR_ , abs/1805.08193, 2018.  URL http://arxiv.org/abs/1805.08193.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hendrycks et al. (2018) Hendrycks, D., Mazeika, M., Wilson, D., and Gimpel, K.  Using trusted data to train deep networks on labels corrupted by severe noise.  In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/ad554d8c3b06d6b97ee76a2448bd7913-Paper.pdf.
  * Hinton et al. (2015) Hinton, G., Vinyals, O., and Dean, J.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ , 2015.  URL https://arxiv.org/abs/1503.02531v1.
  * Howard & Ruder (2018) Howard, J. and Ruder, S.  Fine-tuned language models for text classification.  _CoRR_ , abs/1801.06146, 2018.  URL http://arxiv.org/abs/1801.06146.
  * Hsu & Lin (2002) Hsu, C. W. and Lin, C. J.  A comparision of methods for multiclass support vector machines.  _IEEE Transactions on Neural Networks_ , 13:415–425, 2002\.
  * Janocha & Czarnecki (2017) Janocha, K. and Czarnecki, W. M.  On loss functions for deep neural networks in classification.  _CoRR_ , abs/1702.05659, 2017.  URL http://arxiv.org/abs/1702.05659.
  * Kakade & Shalev-Shwartz (2009) Kakade, S. M. and Shalev-Shwartz, S.  On the duality of strong convexity and strong smoothness : Learning applications and matrix regularization.  2009\.
  * Kornblith et al. (2021) Kornblith, S., Chen, T., Lee, H., and Norouzi, M.  Why do better loss functions lead to less transferable features?  In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=8twKpG5s8Qh.
  * Krizhevsky et al. (2009) Krizhevsky, A., Nair, V., and Hinton, G.  CIFAR-10 and CIFAR-100 datasets.  _URl: https://www. cs. toronto. edu/kriz/cifar. html_ , 6:1, 2009.
  * Lang (1995) Lang, K.  Newsweeder: Learning to filter netnews.  In _Machine Learning Proceedings 1995_ , pp. 331–339. Elsevier, 1995.
  * Lapin et al. (2015) Lapin, M., Hein, M., and Schiele, B.  Top-k multiclass svm.  In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 28, pp. 325–333. Curran Associates, Inc., 2015.  URL https://proceedings.neurips.cc/paper/2015/file/0336dcbab05b9d5ad24f4333c7658a0e-Paper.pdf.
  * Lapin et al. (2016) Lapin, M., Hein, M., and Schiele, B.  Loss functions for top-k error: Analysis and insights.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016_ , pp. 1468–1477. IEEE Computer Society, 2016.  doi: 10.1109/CVPR.2016.163.  URL https://doi.org/10.1109/CVPR.2016.163.
  * Lapin et al. (2018) Lapin, M., Hein, M., and Schiele, B.  Analysis and optimization of loss functions for multiclass, top-k, and multilabel classification.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 40(7):1533–1554, 2018.  doi: 10.1109/TPAMI.2017.2751607.  URL https://doi.org/10.1109/TPAMI.2017.2751607.
  * Levy et al. (2020) Levy, D., Carmon, Y., Duchi, J. C., and Sidford, A.  Large-scale methods for distributionally robust optimization.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Li et al. (2017) Li, W., Wang, L., Li, W., Agustsson, E., and Gool, L. V.  Webvision database: Visual learning and understanding from web data.  _CoRR_ , abs/1708.02862, 2017.  URL http://arxiv.org/abs/1708.02862.
  * Ma et al. (2020) Ma, X., Huang, H., Wang, Y., Romano, S., Erfani, S., and Bailey, J.  Normalized loss functions for deep learning with noisy labels.  In _International conference on machine learning_ , pp. 6543–6553. PMLR, 2020.
  * Madry et al. (2017) Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ , 2017.
  * Namkoong & Duchi (2017) Namkoong, H. and Duchi, J. C.  Variance-based regularization with convex objectives.  In _Advances in Neural Information Processing Systems_ , pp. 2971–2980, 2017.
  * Nesterov (2005) Nesterov, Y.  Smooth minimization of non-smooth functions.  _Mathematical Programming_ , 103:127–152, 2005.
  * Patel & Sastry (2021) Patel, D. and Sastry, P.  Memorization in deep neural networks: Does the loss function matter?  In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_ , pp. 131–142. Springer, 2021.
  * Patrini et al. (2017) Patrini, G., Rozza, A., Menon, A. K., Nock, R., and Qu, L.  Making deep neural networks robust to label noise: A loss correction approach.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017_ , pp. 2233–2241. IEEE Computer Society, 2017.  doi: 10.1109/CVPR.2017.240.  URL https://doi.org/10.1109/CVPR.2017.240.
  * Qi et al. (2020) Qi, Q., Guo, Z., Xu, Y., Jin, R., and Yang, T.  A practical online method for distributionally deep robust optimization.  _arXiv preprint arXiv:2006.10138_ , 2020.
  * Shalev-Shwartz & Wexler (2016) Shalev-Shwartz, S. and Wexler, Y.  Minimizing the maximal loss: How and why.  In _ICML_ , pp. 793–801, 2016.
  * Tang (2013) Tang, Y.  Deep learning using support vector machines.  _CoRR_ , abs/1306.0239, 2013.  URL http://arxiv.org/abs/1306.0239.
  * Tewari & Bartlett (2007) Tewari, A. and Bartlett, P. L.  On the consistency of multiclass classification methods.  _Journal of Machine Learning Research_ , 8(May):1007–1025, 2007.
  * Tsipras et al. (2020) Tsipras, D., Santurkar, S., Engstrom, L., Ilyas, A., and Madry, A.  From imagenet to image classification: Contextualizing progress on benchmarks.  In _ArXiv preprint arXiv:2005.11295_ , 2020.
  * van Rooyen et al. (2015) van Rooyen, B., Menon, A., and Williamson, R. C.  Learning with symmetric label noise: The importance of being unhinged.  In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015.  URL https://proceedings.neurips.cc/paper/2015/file/45c48cce2e2d7fbdea1afc51c7c6ad26-Paper.pdf.
  * Wang et al. (2019) Wang, Y., Ma, X., Chen, Z., Luo, Y., Yi, J., and Bailey, J.  Symmetric cross entropy for robust learning with noisy labels.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 322–330, 2019.
  * Weston & Watkins (1998) Weston, J. and Watkins, C.  Multi-class support vector machines.  Technical report, Technical Report CSD-TR-98-04, Department of Computer Science, Royal Holloway, University of London, May, 1998.
  * Yang & Koyejo (2020) Yang, F. and Koyejo, S.  On the consistency of top-k surrogate losses.  In _International Conference on Machine Learning_ , pp. 10727–10735. PMLR, 2020.
  * Zhang (2004) Zhang, T.  Statistical analysis of some multi-category large margin classification methods.  _J. Mach. Learn. Res._ , 5:1225–1251, December 2004.  ISSN 1532-4435.
  * Zhang et al. (2021) Zhang, Y., Niu, G., and Sugiyama, M.  Learning noise transition matrix from only noisy labels via total variation regularization.  In _International Conference on Machine Learning_ , pp. 12501–12512. PMLR, 2021.
  * Zhang & Sabuncu (2018) Zhang, Z. and Sabuncu, M.  Generalized cross entropy loss for training deep neural networks with noisy labels.  _Advances in neural information processing systems_ , 31, 2018.
  * Zhou et al. (2021) Zhou, X., Liu, X., Jiang, J., Gao, X., and Ji, X.  Asymmetric loss functions for learning with noisy labels.  In _International conference on machine learning_ , pp. 12846–12856. PMLR, 2021.

##  Appendix A Explicit expressions of all relevant losses

Table 4: Comparison between different loss functions. Notice that $A$ from SCE
loss is a negative value, which is suggested to be set as $-4$ in the original
paper (Wang et al., 2019). For JS loss,
$\mathbf{m}=\pi_{1}\mathbf{e}_{y}+(1-\pi_{1})\mathbf{p}$. NA means not
available or unknown. * means that the results are derived by us (proofs are
included in the appendix J).

Category | Loss |  $p_{y}=\frac{\exp(f_{y})}{\sum_{k}\exp(f_{k})}$, $\mathbf{p}=(p_{1},\ldots,p_{K})$, $\mathbf{e}_{y}$ one-hot vector | Top-$1$ consistent | All-$k$ consistent | Symmetric |  instance addaptivity
---|---|---|---|---|---|---
| CE | $\psi_{\text{CE}}(\mathbf{f},y)=-\log\left(p_{y}\right)$ | Yes | Yes | No | No
Traditional | CS (Crammer & Singer, 2002) | $\psi_{\text{CS}}(\mathbf{f},y,c)=\max(0,\max_{k\neq y}f_{k}-f_{y}+c)$ | No | No | No | No
| WW (Weston & Watkins, 1998) | $\psi_{\text{WW}}(\mathbf{f},y,c)=\sum_{k\neq y}\max(0,f_{k}-f_{y}+c)$ | No | No | No | No
Symmetric | MAE (RCE, clipped) (Ghosh et al., 2017) | $\psi_{\text{MAE}}(\mathbf{f},y)=2(1-p_{y})$ | Yes | No | Yes | No
NCE (Ma et al., 2020) | $\psi_{\text{NCE}}(\mathbf{f},y)=\log\left(p_{y}\right)/\sum_{k}\log\left(p_{k}\right)$ | Yes | No | Yes | No
| RLL (Patel & Sastry, 2021) | $\psi_{\text{RL}}(\mathbf{f},y,\alpha)=-\log(\alpha+p_{y})+\frac{1}{K-1}\sum_{i\neq y}\log(\alpha+p_{i})$ | No | No | Yes | No
Interpolation between | GCE (Zhang & Sabuncu, 2018) |  $\psi_{\text{GCE}}(\mathbf{f},y,q)=(1-p_{y}^{q})/q$ where ($q\in[0,1]$) | Yes | Yes∗ ($0\leq q<1$) | Yes ($q=1$) | No
CE and MAE | SCE (Wang et al., 2019) | $\psi_{\text{SCE}}(\mathbf{f},y,\alpha,A)=\alpha\psi_{\text{CE}}(\mathbf{f},y)-(1-\alpha)\frac{A}{2}\psi_{\text{MAE}}(\mathbf{f},y)$ | Yes | Yes∗ ($0\leq\alpha<1$) | Yes ($\alpha=0$) | No
| JS (Englesson & Azizpour, 2021) | $\psi_{\text{JS}}(\mathbf{f},y,\pi_{1})=(\pi_{1}\text{KL}(\mathbf{e}_{y},\mathbf{m})+(1-\pi_{1})\text{KL}(\mathbf{p},\mathbf{m}))/Z$ | NA | NA | Yes ($\pi_{1}=1$) | No
Bounded | MSE (Ghosh et al., 2017) | $\psi_{\text{MSE}}(\mathbf{f},y)=1-2p_{y}+\|\mathbf{p}\|_{2}^{2}$ | Yes | Yes∗ | No | No
TGCE (Zhang & Sabuncu, 2018) |  $\psi_{\text{TGCE}}(\mathbf{f},y,q,k)=(1-\max(p_{y},k)^{q})/q$ where ($q\in[0,1]$) | NA | NA | No | No
Asymmetric | AGCE (Zhou et al., 2021) |  $\psi_{\text{AGCE}}(\mathbf{f},y,q)=((a+1)^{q}-(a+p_{y})^{q})/q$, ($a>0,q>0$) | Yes | No | No | No
AUL (Zhou et al., 2021) |  $\psi_{\text{AUL}}(\mathbf{f},y,q)=((a-p_{y})^{q}-(a-1)^{q})/q$ ($a>1,q>0$) | Yes | No | No | No
LDR | LDR-KL | $\psi^{\text{KL}}_{\lambda}(f,\mathbf{x},y)=\lambda\log\left(\sum_{k=1}^{K}\exp\left(\frac{f_{k}+c_{y,k}-f_{y}}{\lambda}\right)\right)$ | Yes∗ ($\lambda>0$) | Yes∗ ($\lambda=\infty$) | No
ALDR-KL | $\psi^{\text{KL}}_{\alpha,\lambda_{0}}(f,\mathbf{x},y)=\max_{\lambda\geq 0}\psi^{\text{KL}}_{\lambda}(f,\mathbf{x},y)-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}$ | Yes∗ ($\lambda_{0}>0,\alpha>\frac{\log K}{\lambda_{0}}$) | Yes∗ ($\lambda_{0}=\infty$) | Yes

##  Appendix B Proof for LDR-KL Formulation and Special cases.

###### Proof.

Let $\mathbf{q}=\mathbf{f}-\mathbf{f}_{y}+\mathbf{c}_{y}$, we want to solve:

$\max_{\mathbf{p}\in\Delta}\mathbf{p}^{\top}\mathbf{q}-\lambda\sum_{i}\mathbf{p}_{i}\log
K\mathbf{p}_{i}.$

Using Langrangian duality theory to handle the constraint $\sum_{i}p_{i}=1$,
we have

$\min_{\eta}\max_{\mathbf{p}\in\Delta}\mathbf{p}^{\top}\mathbf{q}-\lambda\sum_{i}\mathbf{p}_{i}\log
K\mathbf{p}_{i}-\eta(\sum_{i}p_{i}-1).$

By maximizing over $\mathbf{p}$, we have
$p^{*}_{i}=\exp((q_{i}-\eta)/\lambda)$. With the Karush?Kuhn?Tucker (KKT)
condition $\sum_{i}p_{i}^{*}=1$, we have
$p^{*}_{i}=\frac{\exp(q_{i}/\lambda)}{\sum_{i}\exp(q_{i}/\lambda)}$. By
plugging this back we obtain the formulation of LDR-KL loss, i.e,

$\displaystyle\psi^{\text{KL}}_{\lambda}(\mathbf{x},y)=\lambda\log\left(\frac{1}{K}\sum_{k=1}^{K}\exp\left(\frac{f_{k}+c_{k,y}-f_{y}}{\lambda}\right)\right).$

Extreme Case $\lambda=0$:, with $\lambda=0$, the optimal $\mathbf{p}_{*}$ will
be one-hot vector that is only 1 for the $k$ such that
$f_{k}(\mathbf{x})-f_{y}(\mathbf{x})+c_{k,y}$ is largest. Since
$f_{y}(\mathbf{x})-f_{y}(\mathbf{x})+c_{y,y}=0$. Hence, we have
$\sum_{k}p_{k}^{*}(f_{k}(\mathbf{x})-f_{y}(\mathbf{x})+c_{k,y})=\max(0,\max_{k\neq
y}f_{k}(\mathbf{x})-f_{y}(\mathbf{x})+c_{y})$.

Extreme Case $\lambda=\infty$: , with $\lambda=\infty$, the optimal
$\mathbf{p}_{*}=1/K$. Hence, we have
$\psi^{\text{KL}}_{\lambda}(\mathbf{x},y)=\sum_{k}p_{k}^{*}(f_{k}(\mathbf{x})-f_{y}(\mathbf{x})+c_{k,y})-\lambda\sum_{i}p_{i}^{*}\log
p_{i}^{*}K=\frac{1}{K}\sum_{k=1}^{K}(f_{k}(\mathbf{x})-f_{y}(\mathbf{x})+c_{k,y})$.

∎

##  Appendix C Proof for Lemma 1

###### Proof.

Fix $\mathbf{x}$, with
$\mathbf{q}=(\Pr(y=1|\mathbf{x}),\ldots,\Pr(y=K|\mathbf{x}))$, we will prove
that if $\mathbf{f}$ is rank consistent with respect to $\mathbf{q}$, then
$P_{k}(\mathbf{f},\mathbf{q})$, i.e., $\mathbf{f}$ is top-$k$ preserving with
respect to $\mathbf{q}$ for any $k\in[K]$. Fix $k$, let $r_{k}(\mathbf{f})$ be
any top-$k$ selector of $\mathbf{f}$. First we have $1-\sum_{m\in
r_{k}(\mathbf{f})}\mathbf{q}_{m}\geq 1-\sum_{m=1}^{j}\mathbf{q}_{[k]}$. If $f$
is rank consistent, then the equality holds, i.e., $\sum_{m\in
r_{k}(\mathbf{f})}q_{m}=\sum_{m=1}^{j}\mathbf{q}_{[k]}$. This is because that
if the equality does not hold, then there exists $i\in r_{k}(f)$ and
$j\in[K]\backslash r_{k}(f)$ (i.e., $f_{j}\leq f_{i}$) such that
$q_{j}>q_{i}$. This would not happen as $\mathbf{f}$ is rank consistent with
$\mathbf{q}$ according to assumption.

The following argument follows (Yang & Koyejo, 2020). If $\neg
P_{k}(\mathbf{f},\mathbf{q})$, then there exists $i\in[K]$ such that
$q_{i}>q_{[k+1]}$ but $f_{i}\leq f_{[k+1]}$, or $q_{i}<q_{[k]}$ but $f_{i}\geq
f_{[k]}$. In the first case, there is an $r_{k}$ such that $i\not\in
r_{k}(\mathbf{f})$, because there are at least $k$ indices $j\in[K]$, $j\neq
i$ such that $f_{j}>f_{i}$. In the second case, there is an $r_{k}$ such that
$i\in r_{k}(\mathbf{f})$, because $f_{i}$ is one of the top $k$ values of
$\mathbf{f}$. In either case, there is an $r_{k}$ such that$\sum_{m\in
r_{k}(\mathbf{f})}\mathbf{q}_{m}<\sum_{m=1}^{j}\mathbf{q}_{[k]}$. This
contradicts to the conclusion derived before. Hence, we can conclude that if
$f$ is rank consistent with $\mathbf{q}$, we have $P_{k}(\mathbf{f},q)$ for
any $k\in[K]$. As a result, we conclude that
$\inf_{\mathbf{f}\in\mathbb{R}^{K}:\neg
P_{k}(\mathbf{f},\mathbf{q})}L_{\psi}(\mathbf{f},\mathbf{q})>L_{\psi}(\mathbf{f}^{*},\mathbf{q})$
if $\mathbf{f}^{*}$ is rank consistent with repect to $\mathbf{q}$. ∎

##  Appendix D Proof for Theorem 1

###### Proof.

For simplicity, we consider $\lambda=1$. The extension to $\lambda>0$ is
trivial. Let us consider the optimization problem:

$\displaystyle\min_{\mathbf{f}\in\mathbb{R}^{K}}F(\mathbf{f})$
$\displaystyle:=\sum_{k}q_{k}\psi^{\lambda}_{k}(\mathbf{f})=\sum_{k}q_{k}\log\left(\sum_{l}\exp(f_{l}-f_{k}+c(l,k))\right)$

By the first-order optimality condition $\partial F(f)/\partial f_{j}=0$, we
have:

$\displaystyle-q_{j}$ $\displaystyle\frac{\sum_{l\neq
j}\exp(f_{l}-f_{j}+c(l,j))}{\sum_{l}\exp(f_{l}-f_{j}+c(l,j))}+\sum_{k\neq
j}q_{k}\frac{\exp(f_{j}-f_{k}+c(j,k))}{\sum_{l}\exp(f_{l}-f_{k}+c(l,k))}=0$

Move the negative term to the right and add
$\frac{q_{j}}{\sum_{l}\exp(f_{l}-f_{j}+c(l,j))}$ to both sides:

$\displaystyle
q_{j}\frac{\sum_{l}\exp(f_{l}-f_{j}+c(l,j))}{\sum_{l}\exp(f_{l}-f_{j}+c(l,j))}$
$\displaystyle=\sum_{k\neq
j}\frac{q_{k}\exp(f_{j}-f_{k}+c(j,k))}{\sum_{l}\exp(f_{l}-f_{k}+c(l,k))}+\frac{q_{j}}{\sum_{l}\exp(f_{l}-f_{j}+c(l,j))}$
$\displaystyle=\sum_{k}\frac{q_{k}\exp(f_{j}-f_{k}+c(j,k))}{\sum_{l}\exp(f_{l}-f_{k}+c(l,k))}$
$\displaystyle=\exp(f_{j})\sum_{k}\frac{q_{k}}{\sum_{l}\exp(f_{l}+c(l,k)-c(j,k))}$

Moreover:

$\displaystyle\sum_{k}\frac{q_{k}}{\sum_{l}\exp(f_{l}+c(l,k)-c(j,k))}$
$\displaystyle=\frac{q_{j}}{\exp(f_{j})+\sum_{l\neq
j}\exp(f_{l}+c_{j})}+\sum_{k\neq j}\frac{q_{k}}{\exp(f_{k}-c_{k})+\sum_{l\neq
k}\exp(f_{l})}$ $\displaystyle=\frac{q_{j}}{\exp(f_{j})+\sum_{l\neq
j}\exp(f_{l}+c_{j})}+\sum_{k\neq
j}\frac{q_{k}\exp(c_{k})}{\exp(f_{k})+\sum_{l\neq k}\exp(f_{l}+c_{k})}$
$\displaystyle=\sum_{k}\frac{q_{k}\exp(c(j,k))}{\exp(f_{k})+\sum_{l\neq
k}\exp(f_{l}+c_{k})}$ $\displaystyle=\frac{\sum_{k}q_{k}\exp(c(j,k))}{Z}$

where $Z>0$ is independent of $j$. Then

$\displaystyle\exp(f_{j}^{*})=\frac{q_{j}Z}{\sum_{k}q_{k}\exp(c(j,k))}=\frac{q_{j}Z}{q_{j}+\sum_{k\neq
j}q_{k}\exp(c_{k})}$

If $c_{k}=c$, we have

$\displaystyle\exp(f_{j}^{*})$
$\displaystyle=\frac{q_{j}Z}{\sum_{k}q_{k}\exp(c(j,k))}$
$\displaystyle=\frac{q_{j}Z}{q_{j}+\sum_{k}q_{k}\exp(c_{k})-q_{j}\exp(c_{j})}$
$\displaystyle=\frac{q_{j}Z}{\sum_{k}q_{k}\exp(c_{k})-q_{j}(\exp(c_{j})-1)}$

Hence the larger $q_{j}$, the larger $f_{j}^{*}$. For $q_{i}<q_{j}$, we have

$\displaystyle 1/\exp(f_{i}^{*})-1/\exp(f_{j}^{*})$
$\displaystyle=\frac{\exp(c)}{q_{i}Z}-\frac{\exp(c)-1}{Z}-\frac{\exp(c)}{q_{j}Z}+\frac{\exp(c)-1}{Z}>0$

It implies that $f_{i}^{*}<f_{j}^{*}$. ∎

##  Appendix E Proof of Theorem 2

######  Definition 5.

For a function $R:\Omega\rightarrow\mathbb{R}\cap\\{-\infty,\infty\\}$ taking
values on extended real number line, its convex conjugate is defined as

$\displaystyle
R^{*}(\mathbf{u})=\max_{\mathbf{p}\in\Omega}\mathbf{p}^{\top}\mathbf{u}-R(\mathbf{p})$

######  Lemma 2.

If $R(\cdot)$ and $\Omega$ are (input-) symmetric, then $R^{*}$ is also input-
symmetric.

###### Proof.

$\displaystyle
R^{*}(\mathbf{u})=\max_{\mathbf{p}\in\Omega}\mathbf{p}^{\top}\mathbf{u}-R(\mathbf{p})$

For any $i,j$, let $\widehat{\mathbf{u}}$ be a shuffled version of
$\mathbf{u}$ such that
$\widehat{\mathbf{u}}_{i}=\mathbf{u}_{j},\widehat{\mathbf{u}}_{j}=\mathbf{u}_{i},\widehat{\mathbf{u}}_{k}=\mathbf{u}_{k},\forall
k\neq i,j$. Then

$\displaystyle R^{*}(\widehat{\mathbf{u}})$
$\displaystyle=\max_{\mathbf{p}\in\Omega}\mathbf{p}^{\top}\widehat{\mathbf{u}}-R(\mathbf{p})=\max_{\mathbf{p}\in\Omega}\sum_{k}p_{k}\widehat{\mathbf{u}}_{k}-R(\mathbf{p})$
$\displaystyle=\max_{\mathbf{p}\in\Omega}p_{i}\mathbf{u}_{j}+p_{j}\mathbf{u}_{i}+\sum_{k\neq
i,j}p_{k}\mathbf{u}_{k}-R(\mathbf{p})$
$\displaystyle=\max_{\mathbf{p}\in\Omega}\widehat{\mathbf{p}}^{\top}\mathbf{u}-R(\mathbf{p})=\max_{\widehat{\mathbf{p}}\in\Omega}\widehat{\mathbf{p}}^{\top}\mathbf{u}-R(\widehat{\mathbf{p}})$
$\displaystyle=R^{*}(\mathbf{u})$

where $\widehat{\mathbf{p}}$ is a shuffled version of $\mathbf{p}$. ∎

###### Proof.

Proof of Theorem 2 , without loss of generalization, we assume $\lambda=1$.

$\displaystyle\psi_{y}(\mathbf{f})$
$\displaystyle=\max_{\mathbf{p}\in\Omega}\sum_{k}p_{k}(f_{k}-f_{y}+c_{k,y})-R(\mathbf{p})$
$\displaystyle=R^{*}(\mathbf{f}-f_{y}\mathbf{1}+\mathbf{c}_{y})$

where $\mathbf{c}_{y}=c(1-\mathbf{e}_{y})$, $\mathbf{e}_{y}$ is the $y$-th
column of identity matrix. Let us consider the optimization problem:

$\displaystyle\mathbf{f}^{*}$
$\displaystyle=\arg\min_{\mathbf{f}\in\mathbb{R}^{K}}F(\mathbf{f}):=\sum_{k}q_{k}\psi_{k}(\mathbf{f})$
$\displaystyle=\sum_{k}q_{k}R^{*}(\mathbf{f}-f_{k}\mathbf{1}+\mathbf{c}_{k})$

Consider $\mathbf{q}$ such that $q_{1}<q_{2}$, we prove that $\mathbf{f}^{*}$
is order preserving. We prove by contradiction. Assume
$\mathbf{f}^{*}_{1}>\mathbf{f}^{*}_{2}$. Define $\widehat{\mathbf{f}}$ as
$\widehat{\mathbf{f}}_{1}=\mathbf{f}^{*}_{2}$ and
$\widehat{\mathbf{f}}_{2}=\mathbf{f}^{*}_{1}$ and
$\widehat{\mathbf{f}}_{k}=\mathbf{f}^{*}_{k},k>2$. Then

$\displaystyle F(\widehat{\mathbf{f}})$
$\displaystyle=\sum_{k}q_{k}R^{*}(\widehat{\mathbf{f}}-\widehat{f}_{k}\mathbf{1}+\mathbf{c}_{k})$
$\displaystyle=q_{1}R^{*}(\widehat{\mathbf{f}}-\widehat{f}_{1}\mathbf{1}+\mathbf{c}_{1})+q_{2}R^{*}(\widehat{\mathbf{f}}-\widehat{f}_{2}\mathbf{1}+\mathbf{c}_{2})+\sum_{k>2}q_{k}R^{*}(\widehat{\mathbf{f}}-\widehat{f}_{k}\mathbf{1}+\mathbf{c}_{k})$
$\displaystyle=q_{1}R^{*}(\widehat{\mathbf{f}}-f_{2}^{*}\mathbf{1}+\mathbf{c}_{1})+q_{2}R^{*}(\widehat{\mathbf{f}}-f_{1}^{*}\mathbf{1}+\mathbf{c}_{2})+\sum_{k>2}q_{k}R^{*}(\mathbf{f}-f_{k}^{*}\mathbf{1}+\mathbf{c}_{k})$

Then

$\displaystyle F(\widehat{\mathbf{f}})-F(\mathbf{f}^{*})$
$\displaystyle=q_{1}(R^{*}(\widehat{\mathbf{f}}-f_{2}^{*}\mathbf{1}+\mathbf{c}_{1})-R^{*}(\mathbf{f}-f_{1}^{*}\mathbf{1}+\mathbf{c}_{1}))+q_{2}(R^{*}(\widehat{\mathbf{f}}-f_{1}^{*}\mathbf{1}+\mathbf{c}_{2})-R^{*}(\mathbf{f}-f_{2}^{*}\mathbf{1}+\mathbf{c}_{2}))$

Since $[\widehat{\mathbf{f}}-f_{2}^{*}\mathbf{1}+\mathbf{c}_{1}]_{1}=0$,
$[\widehat{\mathbf{f}}-f_{2}^{*}\mathbf{1}+\mathbf{c}_{1}]_{2}=f_{1}^{*}-f^{*}_{2}+c$,
$[\widehat{\mathbf{f}}-f^{*}_{2}\mathbf{1}+\mathbf{c}_{1}]_{k}=f^{*}_{k}-f^{*}_{2}+c,k>2$,
similarly
$[\mathbf{f}-f^{*}_{2}\mathbf{1}+\mathbf{c}_{2}]_{1}=f^{*}_{1}-f^{*}_{2}+c$,
$[\mathbf{f}-f^{*}_{2}\mathbf{1}+\mathbf{c}_{2}]_{2}=0$,
$[\mathbf{f}^{*}-f^{*}_{2}\mathbf{1}+\mathbf{c}_{2}]_{k}=f^{*}_{k}-f^{*}_{2}+c,k>2$,
hence
$R^{*}(\widehat{\mathbf{f}}-f^{*}_{2}\mathbf{1}+\mathbf{c}_{1})=R^{*}(\mathbf{f}-f^{*}_{2}\mathbf{1}+\mathbf{c}_{2})$.
Similarly
$R^{*}(\mathbf{f}^{*}-f^{*}_{1}\mathbf{1}+\mathbf{c}_{1})=R^{*}(\widehat{\mathbf{f}}-f_{1}^{*}\mathbf{1}+\mathbf{c}_{2})$.
Hence, we have

$\displaystyle F(\widehat{\mathbf{f}})-F(\mathbf{f}^{*})=(q_{2}-q_{1})$
$\displaystyle(R^{*}(\mathbf{f}^{*}-f^{*}_{1}\mathbf{1}+\mathbf{c}_{1})-R^{*}(\mathbf{f}^{*}-f^{*}_{2}\mathbf{1}+\mathbf{c}_{2}))$

Define $\mathbf{f}^{\sharp}=\mathbf{f}^{*}-f^{*}_{1}\mathbf{1}+\mathbf{c}_{1}$
with
$[\mathbf{f}^{\sharp}]_{1}=0,[\mathbf{f}^{\sharp}]_{k}=f^{*}_{k}-f^{*}_{1}+c,k>1$,
and $\mathbf{f}^{\dagger}=\mathbf{f}^{*}-f^{*}_{2}\mathbf{1}+\mathbf{c}_{2}$
with
$[\mathbf{f}^{\dagger}]_{2}=0,[\mathbf{f}^{\dagger}]_{k}=f^{*}_{k}-f^{*}_{2}+c,k\neq
2$. Let $\mathbf{f}^{\ddagger}$ be a shuffled version of
$\mathbf{f}^{\dagger}$ with
$[\mathbf{f}^{\ddagger}]_{1}=0,[\mathbf{f}^{\ddagger}]_{k}=f^{*}_{1}-f^{*}_{2}+c,k=2,[\mathbf{f}^{\ddagger}]_{k}=f^{*}_{k}-f^{*}_{2}+c,k>2$.
Under the assumption that $f^{*}_{1}>f^{*}_{2}$, we have
$\mathbf{f}^{\sharp}\leq\mathbf{f}^{\ddagger}$. Then

$\displaystyle
F(\widehat{\mathbf{f}})-F(\mathbf{f}^{*})=(q_{2}-q_{1})(R^{*}(\mathbf{f}^{\sharp})-R^{*}(\mathbf{f}^{\ddagger}))$

Note that

$R^{*}(\mathbf{f})=\max_{\mathbf{p}\in\Omega}\mathbf{p}^{\top}\mathbf{f}-R(\mathbf{p})$

Below, we prove $R^{*}(\mathbf{f}^{\sharp})-R^{*}(\mathbf{f}^{\ddagger})<0$.
We will consider two scenarios. First, consider $f^{*}_{2}-f^{*}_{1}+c>0$. Let
$\mathbf{p}^{*}=\arg\max_{\mathbf{p}\in\Omega}\sum_{k>1}p_{k}[\mathbf{f}^{\sharp}]_{k}-R(\mathbf{p})$.
We have $\mathbf{f}^{\sharp}\in\nabla R(\mathbf{p}^{*})$. Since
$[\mathbf{f}^{\sharp}]_{2}>0$, we have $p^{*}_{2}>0$ (due to the assumption on
$R$). Hence
$R^{*}(\mathbf{f}^{\sharp})=\max_{\mathbf{p}\in\Omega}\sum_{k>1}p_{k}[\mathbf{f}^{\sharp}]_{k}-R(\mathbf{p})=\sum_{k>1}p^{*}_{k}[\mathbf{f}^{\sharp}]_{k}-R(\mathbf{p}^{*})<\sum_{k>1}p^{*}_{k}[\mathbf{f}^{\ddagger}]_{k}-R(\mathbf{p}^{*})\leq
R^{*}(\mathbf{f}^{\ddagger})$. Next, consider $f^{*}_{2}-f^{*}_{1}+c\leq 0$.
By the convexity of $R^{*}$, we have
$R^{*}(\mathbf{f}^{\sharp})-R^{*}(\mathbf{f}^{\dagger})\leq\nabla
R^{*}(\mathbf{f}^{\sharp})(\mathbf{f}^{\sharp}-\mathbf{f}^{\dagger})=[\nabla
R^{*}(\mathbf{f}^{\sharp})]_{1}(f_{2}-f_{1}-c)+[\nabla
R^{*}(\mathbf{f}^{\sharp})]_{2}(f^{*}_{2}-f^{*}_{1}+c)+\sum_{k>2}[\nabla
R^{*}(\mathbf{f}^{\sharp})]_{k}(f_{2}-f_{1})\leq c([\nabla
R^{*}(\mathbf{f}^{\sharp})]_{2}-[\nabla
R^{*}(\mathbf{f}^{\sharp})]_{1})+\sum_{k}[\nabla
R^{*}(\mathbf{f}^{\sharp})]_{k}(f^{*}_{2}-f^{*}_{1})<0$ due to that (i)
$[\nabla R^{*}(\mathbf{f}^{\sharp})]_{2}\leq[\nabla
R^{*}(\mathbf{f}^{\sharp})]_{1}$ due to
$[\mathbf{f}^{\sharp}]_{2}\leq[\mathbf{f}^{\sharp}]_{1}$; (ii) and
$\sum_{k}[\nabla R^{*}(\mathbf{f}^{\sharp})]_{k}=\sum_{k}p^{*}_{k}>0$. This is
because $\mathbf{p}^{*}$ cannot be all zeros otherwise increasing the first
coordinate of $\mathbf{p}^{*}$ will decrease the value of $R(\mathbf{p})$ and
therefore increase the value of $Q$. However, such a solution $\mathbf{p}^{*}$
is impossible since for the function
$Q(\mathbf{p})=\mathbf{p}^{\top}\mathbf{f}^{\sharp}-R(\mathbf{p})$, which has
a unique maximizer due to strong concavity of $Q(\mathbf{p})$. This will prove
that $R^{*}(\mathbf{f}^{\sharp})-R^{*}(\mathbf{f}^{\ddagger})<0$. As a result,
we prove that if $f^{*}_{1}>f^{*}_{2}$, then
$F(\widehat{\mathbf{f}})<F(\mathbf{f}^{*})$, which is impossible since
$\mathbf{f}^{*}$ is the minimizer of $F$. Hence, we have $f^{*}_{1}\leq
f^{*}_{2}$.

Next, we prove that $f^{*}_{1}<f^{*}_{2}$. Assume $f^{*}_{1}=f^{*}_{2}$, we
establish a contradiction. By the first-order optimality condition, we have

$\displaystyle\frac{\partial F(f)}{\partial f_{k}}$
$\displaystyle=q_{k}\frac{\psi_{k}(\mathbf{f})}{\partial f_{k}}+\sum_{l\neq
k}q_{l}\frac{\partial\psi_{l}(\mathbf{f})}{\partial f_{k}}$
$\displaystyle=q_{k}(\mathbf{e}_{k}-1)^{\top}\nabla
R^{*}(\mathbf{f}-f_{k}\mathbf{1}-\mathbf{c}_{k})+\sum_{l\neq
k}q_{l}\mathbf{e}_{k}^{\top}\nabla
R^{*}(\mathbf{f}-f_{l}\mathbf{1}-\mathbf{c}_{l})=0$

Hence

$\displaystyle q_{k}\mathbf{1}^{\top}\nabla
R^{*}(\mathbf{f}^{*}-f^{*}_{k}\mathbf{1}-\mathbf{c}_{k})=\mathbf{e}_{k}^{\top}\sum_{l}q_{l}\nabla
R^{*}(\mathbf{f}^{*}-f^{*}_{l}\mathbf{1}-\mathbf{c}_{l})$

Next, we prove that for any $\mathbf{f}$ such that
$[\mathbf{f}]_{1}=[\mathbf{f}]_{2}$, then $[\nabla
R^{*}(\mathbf{f})]_{1}=[\nabla R^{*}(\mathbf{f})]_{2}$. To this end, we
consider the equation,
$R(\mathbf{p})+R^{*}(\mathbf{f})=\mathbf{p}^{\top}\mathbf{f}$, where
$\mathbf{p}=\arg\max_{\mathbf{p}\in\Omega}Q(\mathbf{p}):=\mathbf{p}^{\top}\mathbf{f}-R(\mathbf{p})$
satisfying $\mathbf{p}=\nabla R^{*}(\mathbf{f})\in\Omega$. If $[\nabla
R^{*}(\mathbf{f})]_{1}\neq[\nabla R^{*}(\mathbf{f})]_{2}$, which means
$p_{1}\neq p_{2}$. We can define another vector
$\mathbf{p}^{\prime}=(p_{2},p_{1},p_{3},\ldots,p_{K})\in\Omega,\mathbf{p}^{\prime}\neq\mathbf{p}$,
which satisfies
$Q(\mathbf{p}^{\prime})=\mathbf{p}^{\prime\top}\mathbf{f}-R(\mathbf{p}^{\prime})=Q(\mathbf{p})$,
which contradicts to the fact that $Q(\cdot)$ has a unique maximizer. Then for
any $\mathbf{f}$ with $[\mathbf{f}]_{1}=[\mathbf{f}]_{2}$, we have
$[\mathbf{f}-f_{l}\mathbf{1}-\mathbf{c}_{l}]_{1}=[\mathbf{f}-f_{l}\mathbf{1}-\mathbf{c}_{l}]_{2}$.
As a result,

$\displaystyle q_{1}\mathbf{1}^{\top}\nabla
R^{*}(\mathbf{f}^{*}-f^{*}_{1}\mathbf{1}-\mathbf{c}_{1})=q_{2}\mathbf{1}^{\top}\nabla
R^{*}(\mathbf{f}^{*}-f^{*}_{2}\mathbf{1}-\mathbf{c}_{2})$

It is clear that the above equation is impossible if $f_{1}^{*}=f_{2}^{*}$
since $\nabla R^{*}(\mathbf{f})$ is symmetric, $q_{1}<q_{2}$ and
$\mathbf{1}^{\top}\nabla R^{*}(\mathbf{f})\neq 0,\forall\mathbf{f}$ with
$[f]_{1}=0$. The later is due to the assumption $\nabla R(0)<0$, the optimal
solution
$\mathbf{p}=\arg\max_{\mathbf{p}\in\Omega}Q(\mathbf{p}):=\mathbf{p}^{\top}\mathbf{f}-R(\mathbf{p})$
satisfying $\mathbf{p}=\nabla R^{*}(\mathbf{f})\in\Omega$ cannot be all zeros
(otherwise we can find a better solution by increasing the first component of
$\mathbf{p}$ with a larger value of
$\mathbf{p}^{\top}\mathbf{f}-R(\mathbf{p})$. ∎

##  Appendix F Proof for Theorem 3

Let $\mathbf{q}=\mathbf{q}(\mathbf{x})$ be class distribution for a given
$\mathbf{x}$. Let $\pi^{q}_{k}$ denote the index of $q$ whose corresponding
value is the $k$-th largest entry. We define
$\psi(\mathbf{f},l)=\psi(f,\mathbf{x},l)$.

######  Lemma 3.

If $\psi$ is top-$1,2$ consistent simultaneously when class number $K\geq 3$,
then $\exists~{}\mathbf{q}=\mathbf{q}(\mathbf{x})$ such that
$q_{[3]}<q_{[2]}<q_{[1]}$ makes
$\psi(\mathbf{f}^{*},\pi^{q}_{1})<\psi(\mathbf{f}^{*},\pi^{q}_{2})<\psi(\mathbf{f}^{*},\pi^{q}_{3})$,
here $\mathbf{f}^{*}=\inf
L_{\psi}(\mathbf{f},\mathbf{q})=\sum_{l}q_{l}\psi(\mathbf{f},l)$.

###### Proof.

Without loss of generality, we consider $q_{1}>q_{2}>q_{3}$ and prove that if
$\psi(\mathbf{f}^{*},1)<\psi(\mathbf{f}^{*},2)<\psi(\mathbf{f}^{*},3)$ does
not hold, then we can construct $\mathbf{q}^{\prime}$ such that
$q^{\prime}_{[3]}<q^{\prime}_{[2]}<q^{\prime}_{[1]}$ and
$\psi(\mathbf{f}^{*},\pi^{q^{\prime}}_{1})<\psi(\mathbf{f}^{*},\pi^{q^{\prime}}_{2})<\psi(\mathbf{f}^{*},\pi^{q^{\prime}}_{3})$.

If $\psi(\mathbf{f}^{*},1)\geq\psi(\mathbf{f}^{*},2)$ and we construct
$\mathbf{q}^{\prime}$ such that
$q^{\prime}_{[3]}<q^{\prime}_{[2]}<q^{\prime}_{[1]}$ and
$\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{1})<\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{2})$,
where $\hat{\mathbf{f}}^{*}$ be the optimal solution to $\inf
L_{\psi}(\mathbf{f},\mathbf{q}^{\prime})=\sum_{l}q^{\prime}_{l}\psi(\mathbf{f},l)$.
Then we construct $\mathbf{q}^{\prime}$ by switching the 1st and 2nd entry of
$\mathbf{q}$. Then we have $L_{\psi}(\mathbf{f}^{*},\mathbf{q})\geq
L_{\psi}(\mathbf{f}^{*},\mathbf{q}^{\prime})$ because
$\psi(\mathbf{f}^{*},1)q_{1}+\psi(\mathbf{f}^{*},2)q_{2}\geq\psi(\mathbf{f}^{*},1)q^{\prime}_{1}+\psi(\mathbf{f}^{*},2)q^{\prime}_{2}$
due to $q^{\prime}_{1}=q_{2},q^{\prime}_{2}=q_{1}$ and $q_{1}>q_{2}$. Due to
that $\psi$ is top-1, 2 consistent, it is top-1,2 calibrated and hence
$P_{k}(\mathbf{f}^{*},\mathbf{q})$ and
$P_{k}(\hat{\mathbf{f}}^{*},\mathbf{q}^{\prime})$ hold for $k=1,2$. As a
result, we can prove that
$\mathbf{f}^{*}_{1}>\mathbf{f}^{*}_{2}>\mathbf{f}^{*}_{3}$ and
$\hat{\mathbf{f}}^{*}_{2}>\hat{\mathbf{f}}^{*}_{1}>\mathbf{f}^{*}_{3}$. As a
result, $\mathbf{f}_{*}\neq\hat{\mathbf{f}}_{*}$. Next, we prove that
$\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{1})<\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{2})$.
If
$\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{1})\geq\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{2})$,
then $L_{\psi}(\hat{\mathbf{f}}^{*},\mathbf{q}^{\prime})\geq
L_{\psi}(\hat{\mathbf{f}}^{*},\mathbf{q})$ because
$\psi(\hat{\mathbf{f}}^{*},1)q^{\prime}_{1}+\psi(\hat{\mathbf{f}}^{*},2)q^{\prime}_{2}\geq\psi(\hat{\mathbf{f}}^{*},1)q_{1}+\psi(\hat{\mathbf{f}}^{*},2)q_{2}$
due to
$\psi(\hat{\mathbf{f}}^{*},2)=\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{1})$
and
$\psi(\hat{\mathbf{f}}^{*},1)=\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{2})$
and $q_{1}>q_{2}$. Hence, we derive a fact that
$L_{\psi}(\mathbf{f}^{*},\mathbf{q})\geq
L_{\psi}(\mathbf{f}^{*},\mathbf{q}^{\prime})\geq
L_{\psi}(\hat{\mathbf{f}}^{*},\mathbf{q}^{\prime})\geq
L_{\psi}(\hat{\mathbf{f}}^{*},\mathbf{q})$ under the assumption that
$\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{1})\geq\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{2})$,
which is impossible as $\hat{\mathbf{f}}^{*}$ is not the optimal solution to
$\inf L_{\psi}(\mathbf{f},\mathbf{q})=\sum_{l}q_{l}\psi(\mathbf{f},l)$. Thus,
we have
$\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{1})<\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{2})$.
As a result, there exists $\mathbf{q}^{\prime}$ such that
$q^{\prime}_{[3]}<q^{\prime}_{[2]}<q^{\prime}_{[1]}$ and
$\psi(\mathbf{f}^{*},\pi^{q^{\prime}}_{1})<\psi(\mathbf{f}^{*},\pi^{q^{\prime}}_{2})$.

If $\psi(\mathbf{f}^{*},3)\geq\psi(\mathbf{f}^{*},2)$ and construct
$\mathbf{q}^{\prime}$ such that
$q^{\prime}_{[3]}<q^{\prime}_{[2]}<q^{\prime}_{[1]}$ and
$\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{2})<\psi(\hat{\mathbf{f}}^{*},\pi^{q^{\prime}}_{3})$.
This case can be proved similarly as above.

∎

Based on above lemma, we can finish the proof of Theorem 3. For any
$f(\mathbf{x})$, let
$\psi_{f}=(\psi(f,\mathbf{x},1),\ldots,\psi(f,\mathbf{x},K))$. Then
$\min_{f}\sum_{l}\psi(f,\mathbf{x},l)q_{l}=\min_{\psi_{f}\in\mathbb{R}^{K}}\psi_{f}^{\top}\mathbf{q}$.
Since $\psi_{f}^{\top}1=C$ due to the symmetry property. As a result, there
exists
$\psi_{f_{*}}\in\arg\min_{\psi_{f}\in\mathbb{R}^{K}}\psi_{f}^{\top}\mathbf{q},s.t.\quad\psi_{f}^{\top}1=C,\psi_{f}\geq
0$ such that it is at a vertex of the feasible region (a generalized simplex),
i.e., there only exist one $i\in[K]$ such that $[\psi_{f_{*}}]_{i}\neq 0$.
This holds for any $\mathbf{q}$. Combining with the above lemma, we can
conclude a contradiction, i.e., a non-negative symmetric loss cannot be top-1,
2 consistent simultaneously.

##  Appendix G Proof for Theorem 4

###### Proof.

When $\lambda=\infty$, the loss function becomes:
$\psi^{\text{KL}}_{\infty}(\mathbf{x},y)=\frac{1}{K}\sum_{k=1}^{K}(f_{k}(\mathbf{x})-f_{y}(\mathbf{x})+c(k,y))$.
To show it is symmetric:
$\sum_{j=1}^{K}\psi^{\text{KL}}_{\infty}\big{(}\mathbf{x},y=j\big{)}=C,~{}\forall
f(\mathbf{x})$, we have

$\displaystyle\sum_{j=1}^{K}\psi^{\text{KL}}_{\infty}\big{(}\mathbf{x},y=j\big{)}=\frac{1}{K}\sum_{j=1}^{K}\sum_{k=1}^{K}(f_{k}(\mathbf{x})-f_{j}(\mathbf{x})+c(k,j))=\frac{1}{K}\sum_{j=1}^{K}\sum_{k=1}^{K}c(k,j)=C$

where $C$ is a constant only depending on the predefined margins.

To prove All-$k$ consistency, we prove that minimizing the expected loss
function is rank preserving, i.e.,
$\mathbf{f}^{*}=\arg\min_{\mathbf{f}\in\mathcal{C}}\sum_{k}q_{k}\psi_{k}(\mathbf{f})$
is rank preserving, where
$\psi_{y}(\mathbf{f})=\psi^{\text{KL}}_{\infty}(\mathbf{x},y)=\frac{1}{K}\sum_{k=1}^{K}([\mathbf{f}]_{k}-[\mathbf{f}]_{y}+c(k,y))$.
We can write
$\psi_{y}(\mathbf{f})=\frac{1}{K}\mathbf{a}_{y}^{\top}\mathbf{f}+\frac{(K-1)c_{y}}{K}$,
where $[\mathbf{a}_{y}]_{y}=1-K,[\mathbf{a}_{y}]_{k}=1,\forall k\neq y$. As a
result, we have
$\sum_{k}q_{k}\psi_{k}(\mathbf{f})=(\sum_{k}q_{k}\mathbf{a}_{k})^{\top}\mathbf{f}+\frac{(K-1)\sum_{k}q_{k}c_{k}}{K}$,
where $[\sum_{k}q_{k}\mathbf{a}_{k}]_{i}=1-Kq_{i}$. Then minimizing
$\arg\min_{\|\mathbf{f}\|_{2}\leq
B}\sum_{k}q_{k}\psi_{k}(\mathbf{f})=\arg\max_{\|\mathbf{f}\|_{2}\leq
B}\mathbf{f}^{\top}\hat{\mathbf{a}}$, where $[\hat{\mathbf{a}}]_{i}=Kq_{i}-1$.
As a result,
$\mathbf{f}^{*}=\frac{B\hat{\mathbf{a}}}{\|\hat{\mathbf{a}}\|_{2}}$. Hence, if
$q_{i}>q_{j}$, then $\mathbf{f}^{*}_{i}>\mathbf{f}^{*}_{j}$, which proves the
rank preserving property of the optimal solution. Then, the conclusion follows
the Lemma 1.

∎

##  Appendix H Proof for Theorem 5

###### Proof.

We first consider $\alpha,\lambda_{0}\in(0,\infty)$. For the ALDR-KL loss,

$\displaystyle\psi_{\alpha,\lambda_{0}}^{\text{KL}}(\mathbf{x},y)=$
$\displaystyle\max_{\lambda\in\mathbb{R}_{+}}\max_{\mathbf{p}\in\Delta_{K}}\sum_{k=1}^{K}p_{k}(\delta_{k,y}(f(\mathbf{x}))+c_{k,y})$
$\displaystyle-\lambda\text{KL}(\mathbf{p},\frac{1}{K})-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}$
(9) $\displaystyle=$
$\displaystyle\max_{\lambda\in\mathbb{R}_{+}}\lambda\log\frac{1}{K}\sum_{k=1}^{K}\exp(\frac{f_{k}-f_{y}+c(k,y)}{\lambda})-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}$

Then the expected loss is given by

$\displaystyle
F(\mathbf{f})=\sum_{k}q_{k}\psi_{\alpha,\lambda_{0}}^{\text{KL}}(\mathbf{x},k)=\sum_{k}q_{k}\max_{\lambda\in\mathbb{R}_{+}}\lambda\log\frac{1}{K}\sum_{l=1}^{K}\exp(\frac{f_{l}-f_{k}+c(l,k)}{\lambda})-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}$
$\displaystyle=\sum_{k}q_{k}\max_{\lambda\in\mathbb{R}_{+}}(-f_{k}+\log\frac{1}{K}\sum_{l=1}^{K}\exp(\frac{f_{l}+c(l,k)}{\lambda})-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}).$

Assuming that $c_{l,k}=0$ (i.e., no margin is used), then we have

$\displaystyle
F(\mathbf{f})=\sum_{k}q_{k}\psi_{\alpha,\lambda_{0}}^{\text{KL}}(\mathbf{x},k)=\sum_{k}-q_{k}f_{k}+\sum_{k}q_{k}\max_{\lambda\in\mathbb{R}_{+}}\log\frac{1}{K}\sum_{l=1}^{K}\exp(\frac{f_{l}}{\lambda})-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}$
$\displaystyle=\sum_{k}-q_{k}f_{k}+\max_{\lambda\in\mathbb{R}_{+}}\log\frac{1}{K}\sum_{l=1}^{K}\exp(\frac{f_{l}}{\lambda})-\frac{\alpha}{2}(\lambda-\lambda_{0})^{2}$

Similar to Theorem 1, we need to show the optimal solution $\mathbf{f}^{*}$ to
the above problem is rank preserving as $\mathbf{q}$. Denote by the optimal
solution to $\lambda$ as $\lambda_{*}$ and to $\mathbf{p}$ as
$\mathbf{p}_{*}$. Then
$[\mathbf{p}_{*}]_{j}=\exp((f_{j}-f_{y}+c_{j,y})/\lambda_{*})/\sum_{k}\exp((f_{k}-f_{y}+c_{k,y})/\lambda_{*})$.
Then $\partial F/\partial\mathbf{f}$ is same as $\partial
F_{\lambda^{*}}/\partial\mathbf{f}$. Hence as long as $\lambda_{*}>0$ is
finite, we can follow the proof of Theorem 1 to prove the rank preserving. We
know that
$\lambda_{*}=[\lambda_{0}-\frac{1}{\alpha}\text{KL}(\mathbf{p}_{*},1/K)]_{+}$.
Hence, if $\lambda_{0}$ is finite, $\text{KL}(\mathbf{p}_{*},1/K)$ is clearly
finite, so $\lambda_{*}$ is finite. $\lambda_{*}>0$ is ensured if $\frac{\log
K}{\lambda_{0}}<\alpha$ as
$\max_{\mathbf{p}\in\Delta}\text{KL}(\mathbf{p},1/K)=\log K$. Then the
conclusion follows.

If $\lambda_{0}=\infty$, then we have $\lambda_{*}=\infty$; otherwise the loss
is negative infinity. As a result, $\mathbf{p}_{*}=1/K$. Then it reduces to
that of Theorem 4.

∎

##  Appendix I Efficient Computation of LDR-$k$–KL loss.

As an interesting application of our general LDR-$k$ loss, we restrict our
attention to the use of KL divergence for the regularization term
$R(\mathbf{p})=\sum_{i=1}p_{i}\log(Kp_{i})$ in the definition of E.q. 10,

$\displaystyle\psi^{k}_{\lambda}(\mathbf{x},y)=$
$\displaystyle\max_{\mathbf{p}\in\Omega(k)}\sum_{l}p_{l}(\delta_{l,y}(f(\mathbf{x}))+c_{l,y})-\lambda
R(\mathbf{p})$ (10)

to which we refer as LDR-$k$-KL loss. In particular, we consider how to
efficiently compute the LDR-$k$-KL loss. We present an efficient solution with
$O(K\log K)$ complexity.

######  Theorem 6.

Consider the problem
$\max_{\mathbf{p}\in\Omega(k)}\sum_{i}p_{i}q_{i}-\lambda\sum_{i=1}p_{i}\log(Kp_{i})$.
To compute the optimal solution, let the $\mathbf{q}$ to be sorted and $[i]$
denote the index for its $i$-th largest value. Given $a\in[K]$ define a vector
$\mathbf{p}(a)$ as

$\displaystyle[\mathbf{p}(a)]_{[i]}$ $\displaystyle=\frac{1}{k},i<a,$
$\displaystyle[\mathbf{p}(a)]_{[i]}$
$\displaystyle=\exp(\frac{\mathbf{q}_{[i]}}{\lambda}-1)\times\min(\frac{1}{K},\frac{1-\frac{a-1}{k}}{\sum_{j=a}^{K}\exp(\frac{\mathbf{q}_{[j]}}{\lambda}-1)}),~{}~{}i\geq
a$

The optimal solution $\mathbf{p}_{*}$ is given by $\mathbf{p}(a)$ such that
$a$ is the smallest number in $\\{1,\ldots,K\\}$ satisfying
$[\mathbf{p}(a)]_{[a]}\leq\frac{1}{k}$. The overall time complexity is
$O(K\log(K))$.

Given that the algorithm would be simple with the presented theorem 6, we do
not present a formal algorithm box here. Instead, we simply describe it as
follows:

  1. 1.

scan (from largest to smallest) through vector $\mathbf{q}$ to get cumulative
summation $\sum_{j=a}^{K}\exp(\frac{\mathbf{q}_{[j]}}{\lambda}-1)$ for all
possible values of $a$.

  2. 2.

apply the theorem 6 to calculate $[\mathbf{p}(a)]_{[a]}$ for all possible
values of $a$. It is obvious that the cost is linear with $K$.

It is worth noting that the bottleneck for computing the analytical solution
is sorting for $\mathbf{q}$, which usually costs O$(K\log K)$. Hence, the
computation of the LDR-$k$-KL loss can be efficient conducted.

###### Proof.

Apply Lagrangian multiplier:

$\displaystyle\max_{\mathbf{p}\geq 0}\min_{\beta\geq 0,\boldsymbol{\gamma}\geq
0}\mathbf{p}^{\top}\frac{\mathbf{q}}{\lambda}$
$\displaystyle-\sum_{i}\mathbf{p}_{i}\log
K\mathbf{p}_{i}+\beta(1-\sum_{i}\mathbf{p}_{i})+\sum_{i}\gamma_{i}(\frac{1}{k}-\mathbf{p}_{i})$

Stationary condition of $\mathbf{p}$:

$K\mathbf{p}^{*}_{i}=\exp(\frac{\mathbf{q}_{i}}{\lambda}-\beta-\gamma_{i}-1)$

Dual form:

$\min_{\beta\geq 0,\boldsymbol{\gamma}\geq
0}\sum_{i}\frac{1}{K}\exp(\frac{\mathbf{q}_{i}}{\lambda}-\beta-\gamma_{i}-1)+\beta+\sum_{i}\frac{\gamma_{i}}{k}$

Stationary condition for $\beta$ and $\boldsymbol{\gamma}$:

$\gamma^{*}_{i}=\max\big{(}\log\frac{k}{K}\exp(\frac{\mathbf{q}_{i}}{\lambda}-\beta^{*}-1),0\big{)}$
$\beta^{*}=\max\big{(}\log\sum_{i}\frac{1}{K}\exp(\frac{\mathbf{q}_{i}}{\lambda}-\gamma^{*}_{i}-1),0\big{)}$

Checkpoint I: for the $[a]$ that $\boldsymbol{\gamma}_{[a]}^{*}=0$ and
$\boldsymbol{\gamma}_{[a-1]}^{*}>0$, where $2\leq a\leq k+1$, (or $a=1$,
$\boldsymbol{\gamma}_{[a-1]}^{*}$ is undefined):

  * •

We first consider the case when $\beta^{*}=0$, then the
$[\mathbf{p}(a)]^{*}_{[i]}=\frac{1}{k}$ for $i<a$, and
$[\mathbf{p}(a)]^{*}_{[i]}=\frac{1}{K}\exp(\frac{\mathbf{q}_{[i]}}{\lambda}-1)$
for $i\geq a$.

  * •

Otherwise, if $\beta^{*}>0$:

$\displaystyle[\mathbf{p}(a)]^{*}_{[a]}$
$\displaystyle=\frac{1}{K}\exp(\frac{\mathbf{q}_{[a]}}{\lambda}-\beta^{*}-1)=\frac{\exp(\frac{\mathbf{q}_{[a]}}{\lambda}-1)}{\sum_{j}\exp(\frac{\mathbf{q}_{j}}{\lambda}-\gamma_{j}^{*}-1)}$
$\displaystyle=\frac{\exp(\frac{\mathbf{q}_{[a]}}{\lambda}-1)}{\sum_{j=a}^{K}\exp(\frac{\mathbf{q}_{[j]}}{\lambda}-\gamma_{[j]}^{*}-1)}\times\frac{\sum_{j=a}^{K}\exp(\frac{\mathbf{q}_{[j]}}{\lambda}-\gamma_{[j]}^{*}-1)}{\sum_{j=1}^{K}\exp(\frac{\mathbf{q}_{j}}{\lambda}-\gamma_{j}^{*}-1)}$
$\displaystyle=\frac{\exp(\frac{\mathbf{q}_{[a]}}{\lambda}-1)}{\sum_{j=a}^{K}\exp(\frac{\mathbf{q}_{[j]}}{\lambda}-1)}(1-\frac{a-1}{k})$

It is similar to show for any $i$ that $i>a$:

$[\mathbf{p}(a)]^{*}_{[i]}=\frac{\exp(\frac{\mathbf{q}_{[i]}}{\lambda}-1)}{\sum_{j=a}^{K}\exp(\frac{\mathbf{q}_{[j]}}{\lambda}-1)}(1-\frac{a-1}{k})$

For those $i<a$ that $\gamma_{[i]}^{*}>0$:

$\displaystyle[\mathbf{p}(a)]^{*}_{[i]}$
$\displaystyle=\frac{1}{K}\exp(\frac{\mathbf{q}_{i}}{\lambda}-\beta^{*}-\gamma_{i}^{*}-1)$
$\displaystyle=\frac{\exp(\frac{\mathbf{q}_{i}}{\lambda}-\gamma_{i}^{*}-1)}{K\exp(\beta^{*})}$
$\displaystyle=\frac{\frac{K}{k}\exp(\beta^{*}-\frac{\mathbf{q}_{i}}{\lambda}+1)\exp(\frac{\mathbf{q}_{i}}{\lambda}-1)}{K\exp(\beta^{*})}=\frac{1}{k}$

So we can get the analytical solution as far as we know $a$ subject to
$\gamma_{[a]}^{*}=0$ and $\gamma_{[a-1]}^{*}>0$. The
$[\mathbf{p}(a)]^{*}_{[i]}=\frac{1}{k}$ for $i<a$, and
$[\mathbf{p}(a)]^{*}_{[i]}=\frac{\exp(\frac{\mathbf{q}_{[i]}}{\lambda}-1)}{\sum_{j=a}^{K}\exp(\frac{\mathbf{q}_{[j]}}{\lambda}-1)}(1-\frac{a-1}{k})$
for $i\geq a$.

Checkpoint II: next, we show that as far as we find the smallest $a$ such that
$\boldsymbol{\gamma}_{[a]}^{*}=0$ and $\boldsymbol{\gamma}_{[a-1]}^{*}>0$,
then it is the optimal solution.

  * •

Suppose $a^{\prime}<a$: because $\forall a^{\prime}~{}~{}s.t.~{}~{}k+1\geq
a>a^{\prime}\geq 1$, assume
$[\mathbf{p}(a^{\prime})]_{[a^{\prime}]}\leq\frac{1}{k}\implies a^{\prime}$ is
another smaller valid $a$, which violates the pre-condition; therefore,
$[\mathbf{p}(a^{\prime})]_{[a^{\prime}]}>[\mathbf{p}(a)]_{[a^{\prime}]}=\frac{1}{k}$,
the $a^{*}$ must lead to a $\mathbf{p}^{*}$ that violate the $\Omega^{k}$
constrain, hence can’t be the optimal solution, contradiction.

  * •

Suppose $a^{\prime}>a$:

i) if $\beta^{*}(a)=0$, then by pre-condition
$[\boldsymbol{\gamma}(a)]^{*}_{[a]}=0$ and
$[\boldsymbol{\gamma}(a^{\prime})]^{*}_{[a]}>0,~{}\text{consequently}~{}\beta^{*}(a^{\prime})=0$,
which deviates from the optimality of the objective function:

$\min_{\beta\geq 0,\boldsymbol{\gamma}\geq
0}\sum_{i}\frac{1}{K}\exp(\frac{\mathbf{q}_{i}}{\lambda}-\beta-\boldsymbol{\gamma}_{i}-1)+\beta+\sum_{i}\frac{\boldsymbol{\gamma}_{i}}{k}$

(notice that
$[\boldsymbol{\gamma}(a)]^{*}_{[i]}=[\boldsymbol{\gamma}(a^{\prime})]^{*}_{[i]}>0,\forall
i<a$ in order to hold the $\Omega(k)$ constrain).

ii) if $\beta^{*}(a)>0$, then $[\boldsymbol{\gamma}(a)]^{*}_{[a]}=0$ and
$[\boldsymbol{\gamma}(a^{\prime})]^{*}_{[a]}>0$
$\implies\beta^{*}(a^{\prime})<\beta^{*}(a)$ $\implies\forall i\geq
a^{\prime},~{}[\mathbf{p}(a^{\prime})]_{[i]}>[\mathbf{p}(a)]_{[i]}$.

On the other hand, $\forall j<a^{\prime}$,
$[\mathbf{p}(a^{\prime})]_{[j]}=\frac{1}{k}\geq[\mathbf{p}(a)]_{[j]}$
$\implies\sum_{i=a^{\prime}}^{K}[\mathbf{p}(a^{\prime})]_{[i]}\leq
1-\sum_{i=1}^{a^{\prime}-1}[\mathbf{p}(a^{\prime})]_{[i]}\leq
1-\sum_{i=1}^{a^{\prime}-1}[\mathbf{p}(a)]_{[i]}=\sum_{i=a^{\prime}}^{K}[\mathbf{p}(a)]_{[i]}$,
which is contradictory with $\forall i\geq
a^{\prime},~{}~{}[\mathbf{p}(a^{\prime})]_{[i]}>[\mathbf{p}(a)]_{[i]}$.

∎

##  Appendix J Extensive Discussion for Loss Functions

From our theorem 5, we conclude that MAE, RCE, NCE and RLL are not All-$k$
consistent. We have already proved the All-$k$ consistency for LDR loss family
by theorem 1 and theorem 2 (e.g. LDR-KL loss).

Next, we provide proofs for the All-$k$ consistency of GCE ($0\leq q<1$), SCE
($0\leq\alpha<1$) and MSE.

Proof of All-$k$ consistency for GCE ($0\leq q<1$)

To make the presentation clearer, we rename the $q$ parameter in GCE loss
function as $\lambda$, in order to not confuse with underlying class
distribution notation $\mathbf{q}$. Objective:

$\min_{\mathbf{p}\in\Delta_{K}}L_{\psi_{\text{GCE}}}(\mathbf{p},\mathbf{q})=\sum_{i=1}^{K}q_{i}\frac{1-p_{i}^{\lambda}}{\lambda}$

###### Proof.

We will first show $\mathbf{p}^{*}$ is rank consistent with $\mathbf{q}$;
then, show $\mathbf{f}^{*}$ is rank consistent with $\mathbf{p}^{*}$; finally,
it is easy to see that $\mathbf{f}^{*}$ is rank consistent with $\mathbf{q}$
by transitivity rule.

By Lagrangian multiplier:

$\min_{\mathbf{p}}\max_{\alpha,\beta_{i}\geq
0}\sum_{i=1}^{K}q_{i}\frac{1-p_{i}^{\lambda}}{\lambda}+\alpha(\sum_{i=1}^{K}p_{i}-1)-\sum_{i=1}^{K}\beta_{i}p_{i}$

The stationary condition for $\mathbf{p}$:

$p_{i}^{*}=\left(\frac{q_{i}}{\alpha-\beta_{i}}\right)^{\frac{1}{1-\lambda}}$

Notice that the underlying class distribution $\mathbf{q}\in\Delta_{K}$, and
$0\leq\lambda<1\implies 1\leq\frac{1}{1-\lambda}$; moreover, with primal
feasibility for KKT condition, $p^{*}_{i}\geq 0$ and
$\sum_{i=1}^{K}p^{*}_{i}=1$ (it also practically holds because the model
requires the output $\mathbf{p}\in\Delta_{K}$, e.g. softmax); then, consider
the complementary slackness: $p^{*}_{i}>0\implies\beta^{*}_{i}=0$; besides,
$p^{*}_{i}\geq 0,q_{i}\geq 0\implies\alpha>0$; therefore, $p^{*}_{i}\propto
q_{i}^{\frac{1}{1-\lambda}}$ and consequently $\mathbf{p}^{*}$ is rank
consistent with $\mathbf{q}$.

Next, it is clear that
$p_{i}=\frac{\exp(f_{i})}{\sum_{k}\exp(f_{k})}\implies\exp(f^{*}_{i})\propto
p^{*}_{i}$; therefore, $\mathbf{f}^{*}$ is rank consistent with
$\mathbf{p}^{*}$ (notice that the proof is not restricted with softmax). By
transitivity, $\mathbf{f}^{*}$ is rank consistent with $\mathbf{q}$. ∎

Proof of All-$k$ consistency for SCE ($0<\alpha\leq 1$)

Without loss of generality, we consider the case $A=-1$ but it could be
generalized to any $A<0$. We rename the $\alpha$ parameter for SCE loss as
$1-\lambda$ for a better presentation. Objective:

$\min_{\mathbf{p}\in\Delta_{K}}L_{\psi_{\text{SCE}}}(\mathbf{p},\mathbf{q})=\sum_{i=1}^{K}q_{i}\left(-(1-\lambda)\log
p_{i}+\lambda(1-p_{i})\right)$

By Lagrangian multiplier:

$\min_{\mathbf{p}}\max_{\alpha,\beta_{i}\geq
0}\sum_{i=1}^{K}q_{i}\left(-(1-\lambda)\log
p_{i}+\lambda(1-p_{i})\right)+\alpha(\sum_{i=1}^{K}p_{i}-1)-\sum_{i=1}^{K}\beta_{i}p_{i}$

The stationary condition for $\mathbf{p}$:

$p_{i}^{*}=\frac{(1-\lambda)q_{i}}{\alpha-\beta_{i}-\lambda q_{i}}$
$\frac{1}{p_{i}^{*}}=\frac{\alpha-\beta_{i}-\lambda
q_{i}}{(1-\lambda)q_{i}}=\frac{\alpha-\beta_{i}}{(1-\lambda)q_{i}}-\frac{\lambda}{1-\lambda},~{}~{}~{}0<p_{i}^{*}<1$

By primal feasibility for KKT condition, $p^{*}_{i}\geq 0$ and
$\sum_{i=1}^{K}p^{*}_{i}=1$. By complementary slackness:
$p^{*}_{i}>0\implies\beta^{*}_{i}=0$. Besides, $p^{*}_{i}\geq 0,q_{i}\geq
0\implies\alpha>0$. Notice that $0<1-\lambda\leq 1$. Therefore,
$(\frac{1}{p_{i}^{*}}+\frac{\lambda}{1-\lambda})\propto\frac{1}{q_{i}}$, and
consequently $\mathbf{p}^{*}$ is rank consistent with $\mathbf{q}$.

Next, it is obvious that
$p_{i}=\frac{\exp(f_{i})}{\sum_{k}\exp(f_{k})}\implies\exp(f^{*}_{i})\propto
p^{*}_{i}$; therefore, $\mathbf{f}^{*}$ is rank consistent with
$\mathbf{p}^{*}$. By transitivity, $\mathbf{f}^{*}$ is rank consistent with
$\mathbf{q}$.

Notice that the proof is for the empirical form of SCE. For the theoretical
form:
$L_{\psi_{\text{SCE}}}(\mathbf{p},\mathbf{q})=H(\mathbf{q},\mathbf{p})+H(\mathbf{p},\mathbf{q})$,
where $H(\mathbf{q},\mathbf{p})=-\mathrm{E}_{q}[\log p]$ denotes cross
entropy, it can be proved with the similar logic.

Proof of All-$k$ consistency for MSE

Objective:

$\min_{\mathbf{p}\in\Delta_{K}}L_{\psi_{\text{MSE}}}(\mathbf{p},\mathbf{q})=\sum_{i=1}^{K}q_{i}(1-2p_{i}+\|\mathbf{p}\|_{2}^{2})$

By Lagrangian multiplier:

$\min_{\mathbf{p}}\max_{\alpha,\beta_{i}\geq
0}\sum_{i=1}^{K}q_{i}(1-2p_{i}+\|\mathbf{p}\|_{2}^{2})+\alpha(\sum_{i=1}^{K}p_{i}-1)-\sum_{i=1}^{K}\beta_{i}p_{i}$

The stationary condition for $\mathbf{p}$:

$p_{i}^{*}=q_{i}+\frac{\beta_{i}-\alpha}{2}$

By the primal feasibility for KKT condition, we have $p^{*}_{i}\geq 0$ and
$\sum_{i=1}^{K}p^{*}_{i}=1$. By complementary slackness:
$p^{*}_{i}>0\implies\beta^{*}_{i}=0$. Furthermore, $p^{*}_{i}=0$, we can prove
$\beta_{i}^{*}=0$ holds; otherwise, $\exists
j,~{}s.t.~{}p^{*}_{j}=0,\beta_{j}^{*}>0$, with primal feasibility
$\sum_{i=1}^{K}\left(q_{i}+\frac{\beta^{*}_{i}-\alpha^{*}}{2}\right)=1\implies\alpha^{*}>0$
given that $\sum_{i=1}^{K}q_{i}=1$. As a consequence, for the $p^{*}_{i}=0$,
we conclude $p^{*}_{i}\leq q_{i}$; for the $p^{*}_{i}>0$, because
$\beta^{*}_{i}=0,\alpha^{*}>0$, we conclude
$p^{*}_{i}=q_{i}+\frac{\beta_{i}^{*}-\alpha^{*}}{2}<q_{i}$; therefore,
$\sum_{i=1}^{K}p^{*}_{i}<\sum_{i=1}^{K}q_{i}=1$, a contraction. Hence,
$\mathbf{p}^{*}=\mathbf{q}$ and is rank consistent with $\mathbf{q}$.

Next, it is obvious that
$p_{i}=\frac{\exp(f_{i})}{\sum_{k}\exp(f_{k})}\implies\exp(f^{*}_{i})\propto
p^{*}_{i}$; therefore, $\mathbf{f}^{*}$ is rank consistent with
$\mathbf{p}^{*}$. By transitivity, $\mathbf{f}^{*}$ is rank consistent with
$\mathbf{q}$.

##  Appendix K Dataset Statistics

Table 5: statistics for the benchmark datasets Dataset | # of samples | # of features | # of classes
---|---|---|---
ALOI | 108000 | 128 | 1,000
News20 | 15935 | 62060 | 20
Letter | 15000 | 16 | 26
Vowel | 990 | 10 | 11
Kuzushiji-49 | 232365 / 38547 | 28x28 | 49
CIFAR-100 | 50000 / 10000 | 32x32x3 | 100
Tiny-ImageNet | 100000 / 10000 | 64x64x3 | 200

##  Appendix L More Experimental Results

###  L.1 Relationship between $\lambda$ and KL divergence values
$\text{KL}(\mathbf{p},1/K)$ for ALDR-KL on Synthetic Data

We present the averaged learned $\lambda_{t}$ and
$\text{KL}(\mathbf{p}_{t},\frac{\mathbf{1}}{K})$ values for ALDR-KL loss at
Figure 3. It justifies our motivation that we prefer to give the uncertain
data with larger $\lambda$ value.

Figure 3: The averaged $\lambda_{t}$ and
$\text{KL}(\mathbf{p}_{t},\frac{\mathbf{1}}{K})$ values across all iterations
for each instance on the synthetic dataset.

###  L.2 Comprehensive Accuracy Results on Benchmark datasets

The top-$1,2,3,4,5$ accuracy results are summarized at Table 6, 7, 8, 9, 10,
11, 12, 13, 14, 15. From the results, we can see that (i) the performance of
ALDR-KL and LDR-KL are stable; (ii) MAE has very poor performance, which is
consistent with many earlier works; (ii) CE is still competitive in most
cases.

Table 6: Testing Top-1 Accuracy (%) with mean and standard deviation for
tabular dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Vowel | ALDR-KL | 71.3(3.1) | 58.2(6.38) | 39.8(6.25) | 15.2(6.13) | 69.1(3.36) | 61.2(2.08) | 39.4(3.06)
LDR-KL | 74.1(2.18) | 56.4(5.32) | 35.4(4.65) | 13.7(4.02) | 73.1(2.68) | 58.6(6.39) | 41.0(3.7)
CE | 63.0(3.48) | 53.9(3.42) | 41.0(2.9) | 14.3(4.88) | 65.9(3.52) | 56.4(4.88) | 35.2(2.34)
SCE | 64.4(3.69) | 55.4(4.35) | 37.4(4.19) | 11.9(2.96) | 65.5(2.16) | 55.6(3.94) | 34.7(3.17)
GCE | 64.2(4.41) | 52.1(4.81) | 39.2(2.51) | 11.9(6.65) | 64.6(2.47) | 56.4(3.58) | 39.0(3.23)
TGCE | 64.6(3.61) | 52.1(4.81) | 38.6(2.74) | 11.9(6.65) | 64.6(2.47) | 56.4(3.58) | 38.8(3.48)
WW | 58.0(4.22) | 47.9(1.51) | 34.1(6.83) | 11.3(6.56) | 57.0(1.87) | 50.9(2.08) | 37.2(3.4)
JS | 62.6(2.3) | 57.4(2.42) | 39.0(3.1) | 14.1(1.92) | 63.8(4.06) | 53.5(3.5) | 34.5(2.51)
CS | 70.1(3.23) | 49.3(2.74) | 32.9(6.41) | 9.7(3.23) | 65.5(2.74) | 56.2(3.97) | 36.8(3.42)
RLL | 61.8(2.25) | 56.4(2.06) | 38.6(3.75) | 9.29(5.4) | 63.6(0.903) | 49.1(2.27) | 34.9(3.87)
NCE+RCE | 61.0(7.58) | 47.3(5.21) | 32.7(3.04) | 13.3(6.77) | 56.2(4.89) | 45.5(3.67) | 32.5(7.01)
NCE+AUL | 54.1(3.92) | 53.7(8.74) | 29.9(1.87) | 12.3(5.09) | 50.1(6.21) | 46.7(3.75) | 32.1(6.62)
NCE+AGCE | 57.6(3.78) | 51.3(10.3) | 32.7(3.92) | 12.1(4.95) | 57.6(5.46) | 45.0(3.17) | 31.7(3.92)
MSE | 56.0(1.37) | 43.2(3.58) | 29.3(1.69) | 9.9(4.4) | 52.5(2.3) | 45.0(5.01) | 32.7(1.03)
MAE | 10.1(2.12) | 10.1(2.12) | 9.09(2.71) | 8.48(2.36) | 8.69(4.27) | 8.69(4.27) | 9.09(4.04)
Letter | ALDR-KL | 79.9(0.254) | 76.1(0.445) | 68.6(0.543) | 36.1(2.12) | 79.2(0.504) | 77.2(0.463) | 50.8(0.667)
LDR-KL | 80.1(0.124) | 75.7(0.847) | 68.8(0.676) | 36.0(2.19) | 78.8(0.178) | 75.8(0.434) | 51.6(0.893)
CE | 74.2(0.538) | 68.2(0.414) | 56.9(0.495) | 16.1(1.81) | 73.6(0.183) | 70.5(0.767) | 48.1(1.29)
SCE | 74.0(0.585) | 67.9(0.431) | 55.9(0.546) | 15.0(1.66) | 73.2(0.341) | 70.5(0.969) | 48.1(1.76)
GCE | 73.2(0.428) | 67.0(0.409) | 54.2(0.494) | 13.7(1.96) | 72.7(0.392) | 69.8(0.877) | 47.1(1.87)
TGCE | 73.2(0.44) | 66.3(0.284) | 54.3(1.18) | 14.1(2.1) | 72.7(0.392) | 69.8(0.888) | 46.4(1.45)
WW | 65.3(1.04) | 61.6(0.969) | 56.1(1.26) | 14.9(1.6) | 65.2(0.222) | 62.2(0.912) | 42.1(1.66)
JS | 72.6(0.361) | 65.9(0.518) | 45.0(1.55) | 8.33(2.37) | 71.3(0.325) | 68.5(0.741) | 46.6(1.96)
CS | 71.5(0.284) | 65.0(0.739) | 60.6(0.606) | 24.4(3.58) | 67.7(1.04) | 61.5(1.05) | 43.0(2.04)
RLL | 69.2(0.515) | 57.8(0.501) | 28.0(0.479) | 5.1(1.35) | 67.7(0.651) | 61.8(0.598) | 42.5(1.22)
NCE+RCE | 65.8(1.66) | 60.2(2.46) | 51.6(4.7) | 19.6(3.2) | 63.4(1.52) | 49.5(1.94) | 44.6(2.0)
NCE+AUL | 64.7(2.78) | 58.3(1.84) | 49.3(2.75) | 13.1(1.31) | 58.7(1.47) | 49.2(2.71) | 42.0(1.5)
NCE+AGCE | 57.5(1.0) | 51.0(3.19) | 40.1(4.16) | 5.07(1.42) | 54.0(2.57) | 43.2(2.29) | 38.6(2.82)
MSE | 27.1(2.17) | 15.0(2.44) | 11.7(1.99) | 5.7(1.68) | 20.9(0.429) | 16.9(1.5) | 15.6(1.76)
MAE | 5.03(1.22) | 5.14(1.08) | 4.86(1.27) | 4.4(0.499) | 5.04(1.2) | 5.09(1.19) | 5.05(1.23)
News20 | ALDR-KL | 91.6(0.161) | 88.2(0.376) | 77.9(1.0) | 22.4(2.39) | 90.1(0.157) | 86.0(0.281) | 63.9(0.882)
LDR-KL | 92.3(0.256) | 88.2(0.371) | 78.1(1.29) | 18.0(1.67) | 89.7(0.472) | 86.2(0.291) | 64.3(1.12)
CE | 62.0(1.0) | 30.0(0.821) | 14.5(1.64) | 5.59(0.562) | 53.4(0.936) | 53.0(1.42) | 49.7(0.671)
SCE | 57.3(1.11) | 27.2(0.714) | 14.0(1.6) | 5.46(1.2) | 51.5(0.651) | 50.7(1.51) | 47.8(0.931)
GCE | 46.0(0.526) | 19.8(0.95) | 12.8(1.34) | 5.41(1.08) | 46.2(0.847) | 44.5(0.839) | 41.4(1.05)
TGCE | 45.8(0.635) | 20.8(1.38) | 12.7(1.48) | 5.41(1.08) | 45.9(1.02) | 44.1(0.973) | 40.7(1.34)
WW | 53.2(3.31) | 36.9(5.36) | 23.7(2.16) | 6.72(2.8) | 51.6(1.81) | 47.6(1.23) | 42.8(0.875)
JS | 25.5(0.196) | 12.2(0.714) | 10.3(1.57) | 4.7(0.675) | 23.5(0.923) | 19.5(1.23) | 17.2(1.35)
CS | 77.5(2.51) | 73.5(0.906) | 55.3(1.65) | 9.7(2.07) | 75.4(1.85) | 64.7(1.2) | 54.4(0.713)
RLL | 11.4(1.41) | 10.1(1.67) | 7.39(1.28) | 5.16(0.871) | 10.9(1.01) | 10.3(0.748) | 10.2(0.754)
NCE+RCE | 90.4(0.213) | 72.0(1.18) | 28.8(2.17) | 6.0(0.785) | 86.4(2.56) | 65.2(1.01) | 63.0(0.945)
NCE+AUL | 63.1(2.0) | 31.0(1.92) | 15.0(0.265) | 5.72(0.619) | 54.1(1.87) | 47.2(3.4) | 44.0(2.32)
NCE+AGCE | 39.9(3.09) | 19.3(1.78) | 10.3(0.519) | 5.78(0.738) | 34.2(1.9) | 29.8(3.19) | 29.7(0.31)
MSE | 7.86(1.19) | 8.35(1.43) | 6.31(0.97) | 4.99(0.484) | 6.58(1.08) | 8.39(3.02) | 8.0(1.18)
MAE | 5.01(0.241) | 5.24(0.155) | 5.12(0.119) | 4.88(0.703) | 5.17(0.261) | 4.99(0.336) | 5.04(0.39)
ALOI | ALDR-KL | 94.4(0.103) | 89.2(0.054) | 82.7(0.197) | 32.7(0.307) | 91.9(0.163) | 79.4(0.206) | 45.7(0.273)
LDR-KL | 92.7(0.101) | 89.3(0.105) | 83.3(0.117) | 32.9(0.544) | 91.1(0.13) | 83.2(0.221) | 44.5(0.497)
CE | 75.7(0.148) | 65.8(0.298) | 40.9(0.611) | 3.93(0.254) | 73.3(0.394) | 61.5(0.259) | 26.4(0.31)
SCE | 74.7(0.181) | 63.8(0.312) | 38.8(0.614) | 3.74(0.307) | 71.8(0.317) | 59.6(0.241) | 25.3(0.127)
GCE | 71.4(0.205) | 56.5(0.151) | 29.6(0.655) | 2.64(0.324) | 67.7(0.31) | 52.7(0.492) | 20.9(0.305)
TGCE | 70.2(0.389) | 54.9(0.331) | 28.5(0.78) | 2.64(0.324) | 66.2(0.068) | 50.6(0.512) | 20.0(0.154)
WW | 57.3(0.464) | 43.5(0.349) | 24.2(0.435) | 2.4(0.315) | 44.8(0.476) | 23.5(0.179) | 9.34(0.194)
JS | 3.53(0.595) | 2.88(0.443) | 1.72(0.338) | 0.189(0.058) | 3.45(0.488) | 2.43(0.266) | 1.63(0.282)
CS | 84.5(0.18) | 73.4(0.113) | 30.2(0.411) | 1.63(0.23) | 81.5(0.224) | 75.6(0.215) | 38.7(0.479)
RLL | 0.572(0.138) | 0.413(0.145) | 0.22(0.073) | 0.15(0.061) | 0.55(0.149) | 0.381(0.136) | 0.207(0.109)
NCE+RCE | 3.9(0.49) | 2.73(0.155) | 2.02(0.535) | 0.269(0.109) | 2.93(0.266) | 1.87(0.209) | 1.56(0.196)
NCE+AUL | 2.64(0.537) | 1.81(0.278) | 0.806(0.203) | 0.157(0.055) | 2.51(0.543) | 1.84(0.248) | 1.22(0.203)
NCE+AGCE | 2.26(0.429) | 1.22(0.313) | 0.432(0.105) | 0.128(0.042) | 2.03(0.494) | 1.36(0.206) | 0.826(0.193)
MSE | 0.217(0.084) | 0.185(0.089) | 0.172(0.059) | 0.096(0.051) | 0.2(0.09) | 0.187(0.067) | 0.137(0.102)
MAE | 0.152(0.067) | 0.144(0.062) | 0.124(0.047) | 0.089(0.038) | 0.152(0.067) | 0.137(0.077) | 0.139(0.051)

Table 7: Testing Top-1 Accuracy (%) with mean and standard deviation for image
dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Kuzushiji-49 | ALDR-KL | 96.6(0.132) | 94.5(0.248) | 91.5(0.154) | 48.2(1.54) | 96.0(0.256) | 95.5(0.11) | 54.4(5.84)
LDR-KL | 96.6(0.06) | 94.8(0.145) | 91.2(0.295) | 48.1(1.27) | 95.9(0.089) | 95.2(0.132) | 54.1(3.69)
CE | 96.9(0.09) | 94.0(0.102) | 85.5(0.219) | 29.4(1.45) | 96.2(0.064) | 95.2(0.098) | 47.7(3.17)
SCE | 96.9(0.074) | 94.4(0.186) | 85.5(0.235) | 29.1(0.836) | 96.2(0.096) | 95.2(0.17) | 49.7(2.1)
GCE | 96.9(0.069) | 94.5(0.161) | 85.5(0.347) | 28.6(0.684) | 96.2(0.076) | 95.2(0.085) | 48.8(1.69)
TGCE | 96.8(0.019) | 94.4(0.115) | 85.5(0.221) | 28.7(0.359) | 96.2(0.05) | 95.2(0.114) | 48.2(2.22)
WW | 97.1(0.091) | 90.0(0.341) | 80.1(0.236) | 26.3(1.45) | 95.5(0.452) | 94.5(0.381) | 49.8(1.22)
JS | 96.8(0.052) | 92.2(0.598) | 87.4(0.742) | 31.2(1.09) | 94.8(0.723) | 93.0(0.188) | 49.3(2.71)
CS | 97.0(0.03) | 86.8(3.0) | 6.93(2.46) | 2.1(0.087) | 96.3(0.2) | 91.2(0.729) | 37.1(2.93)
RLL | 91.4(0.031) | 90.5(0.082) | 81.1(1.32) | 30.6(0.866) | 90.8(0.069) | 86.6(1.05) | 47.8(3.13)
NCE+RCE | 90.7(0.104) | 90.0(0.134) | 69.2(0.778) | 8.48(1.08) | 87.1(0.062) | 81.2(0.877) | 43.2(0.64)
NCE+AUL | 91.0(0.06) | 85.3(0.923) | 65.6(1.43) | 6.9(1.16) | 89.0(0.058) | 83.0(0.905) | 45.0(1.8)
NCE+AGCE | 90.8(0.088) | 77.4(0.83) | 58.2(2.15) | 6.51(0.769) | 88.1(0.873) | 79.0(0.9) | 42.6(1.33)
MSE | 82.6(1.65) | 57.7(1.53) | 35.8(1.56) | 4.18(0.796) | 63.6(1.7) | 46.9(1.59) | 28.4(1.14)
MAE | 2.09(0.062) | 35.2(2.1) | 20.0(3.03) | 3.81(0.702) | 39.1(2.01) | 24.2(1.81) | 18.2(1.33)
CIFAR100 | ALDR-KL | 60.6(0.725) | 51.9(0.378) | 36.0(0.495) | 3.52(0.536) | 57.5(0.584) | 51.7(0.711) | 30.0(1.23)
LDR-KL | 60.5(0.535) | 51.8(0.75) | 36.3(0.698) | 3.7(0.544) | 57.6(0.574) | 51.2(0.397) | 29.5(0.982)
CE | 59.5(0.545) | 48.7(0.617) | 32.0(0.941) | 3.26(0.357) | 57.0(0.61) | 50.1(0.399) | 29.5(0.7)
SCE | 59.5(0.773) | 49.9(0.846) | 30.7(1.03) | 3.87(0.251) | 57.0(0.245) | 50.7(0.754) | 30.0(0.488)
GCE | 60.1(0.558) | 49.2(0.925) | 31.9(0.831) | 3.69(0.392) | 57.0(0.92) | 50.4(0.806) | 30.2(0.616)
TGCE | 59.5(0.689) | 49.8(0.555) | 28.8(0.568) | 3.59(0.398) | 56.9(0.602) | 53.5(0.445) | 30.1(0.77)
WW | 50.2(0.625) | 36.1(0.976) | 21.3(0.71) | 4.1(0.346) | 48.2(0.505) | 44.6(0.252) | 25.9(0.505)
JS | 58.7(0.424) | 52.2(0.794) | 30.3(1.18) | 3.5(0.438) | 57.2(0.363) | 49.5(1.06) | 29.1(0.429)
CS | 11.0(0.404) | 4.85(0.345) | 1.59(0.217) | 1.0(0.004) | 8.07(0.333) | 5.42(0.468) | 3.71(0.194)
RLL | 42.5(1.95) | 35.4(0.438) | 18.3(1.16) | 3.57(0.428) | 40.3(0.855) | 34.7(1.84) | 17.9(1.21)
NCE+RCE | 13.5(1.22) | 8.29(0.949) | 5.03(0.563) | 2.06(0.697) | 12.5(1.28) | 8.32(0.439) | 4.6(0.429)
NCE+AUL | 11.5(0.368) | 7.73(0.403) | 5.79(0.125) | 2.44(0.839) | 9.9(0.792) | 7.6(0.316) | 4.33(0.189)
NCE+AGCE | 10.3(0.498) | 7.52(0.298) | 5.61(0.123) | 2.03(0.896) | 9.16(0.516) | 7.51(0.277) | 4.06(0.224)
MSE | 19.0(0.663) | 10.1(0.545) | 8.22(0.476) | 4.61(0.524) | 16.0(0.579) | 9.83(0.358) | 5.99(1.02)
MAE | 1.07(0.152) | 1.05(0.063) | 0.918(0.153) | 1.01(0.182) | 1.03(0.093) | 1.09(0.127) | 0.968(0.28)
Tiny-ImageNet | ALDR-KL | 47.8(0.226) | 38.4(0.136) | 23.7(0.216) | 1.3(0.145) | 44.9(0.167) | 38.1(0.634) | 21.6(0.39)
LDR-KL | 47.6(0.39) | 38.4(0.521) | 23.4(0.563) | 1.29(0.201) | 45.1(0.171) | 37.4(0.112) | 22.1(0.333)
CE | 47.7(0.375) | 36.3(0.246) | 14.5(0.316) | 1.23(0.187) | 45.5(0.149) | 41.5(0.262) | 22.0(0.544)
SCE | 47.9(0.286) | 36.1(0.175) | 14.0(0.453) | 1.53(0.449) | 45.4(0.254) | 41.5(0.244) | 22.1(0.345)
GCE | 47.8(0.397) | 36.1(0.327) | 11.9(0.572) | 0.968(0.281) | 45.7(0.099) | 41.6(0.296) | 22.0(0.267)
TGCE | 45.7(0.106) | 31.7(0.367) | 10.7(0.564) | 1.06(0.271) | 43.3(0.324) | 39.8(0.227) | 19.7(0.362)
WW | 31.3(0.159) | 20.7(0.354) | 10.2(0.418) | 0.99(0.109) | 28.4(0.204) | 24.9(0.631) | 13.9(0.283)
JS | 39.9(0.405) | 21.6(0.744) | 4.26(0.235) | 1.11(0.294) | 35.5(0.334) | 24.1(0.21) | 10.1(0.786)
CS | 0.968(0.123) | 0.672(0.127) | 0.496(0.008) | 0.502(0.004) | 0.81(0.078) | 0.66(0.07) | 0.514(0.02)
RLL | 11.1(1.14) | 3.9(0.566) | 2.42(0.25) | 0.648(0.242) | 7.47(0.53) | 3.53(0.18) | 2.27(0.301)
NCE+RCE | 1.71(0.214) | 1.5(0.119) | 1.21(0.041) | 0.802(0.107) | 1.65(0.131) | 1.55(0.19) | 1.05(0.2)
NCE+AUL | 2.05(0.117) | 1.66(0.094) | 1.44(0.121) | 0.866(0.234) | 1.9(0.206) | 1.66(0.226) | 1.21(0.394)
NCE+AGCE | 1.98(0.145) | 1.74(0.191) | 1.51(0.166) | 0.914(0.316) | 1.97(0.221) | 1.67(0.098) | 1.18(0.235)
MSE | 2.53(0.179) | 1.29(0.104) | 0.998(0.087) | 0.72(0.125) | 1.29(0.071) | 1.24(0.137) | 1.1(0.163)
MAE | 0.548(0.083) | 0.996(0.138) | 0.838(0.087) | 0.732(0.136) | 1.07(0.165) | 1.07(0.175) | 1.01(0.189)

Table 8: Testing Top-2 Accuracy (%) with mean and standard deviation for
tabular dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Vowel | ALDR-KL | 93.9(2.3) | 83.0(2.67) | 61.0(4.27) | 23.4(5.97) | 92.7(1.96) | 93.3(2.27) | 86.3(1.98)
LDR-KL | 93.5(1.76) | 81.4(3.29) | 60.6(4.52) | 23.6(5.44) | 91.9(1.11) | 90.1(1.74) | 86.1(1.62)
CE | 88.7(1.49) | 77.8(2.12) | 57.8(1.34) | 19.8(5.37) | 90.3(2.83) | 85.9(3.5) | 82.6(3.52)
SCE | 88.5(1.51) | 77.4(2.27) | 57.2(6.6) | 21.0(3.52) | 88.5(4.07) | 86.1(3.09) | 80.2(2.08)
GCE | 88.7(1.18) | 79.0(1.49) | 58.0(2.6) | 20.4(6.17) | 88.9(4.74) | 86.3(3.42) | 80.2(2.75)
TGCE | 88.5(1.03) | 79.0(1.49) | 57.6(2.3) | 20.4(6.17) | 88.3(4.5) | 86.3(3.42) | 79.8(3.06)
WW | 84.6(2.06) | 75.8(3.78) | 55.2(4.36) | 25.5(3.91) | 86.7(3.09) | 82.8(3.44) | 76.0(3.34)
JS | 87.1(2.16) | 81.2(1.51) | 59.4(2.06) | 19.8(7.02) | 84.2(3.81) | 85.1(2.06) | 78.6(2.67)
CS | 88.7(1.85) | 74.3(3.59) | 49.1(8.75) | 20.8(5.29) | 84.6(1.85) | 82.0(3.8) | 70.9(2.34)
RLL | 82.2(1.76) | 77.6(2.74) | 57.4(3.58) | 22.4(6.27) | 83.2(2.36) | 83.0(1.96) | 77.0(3.28)
NCE+RCE | 73.7(3.61) | 70.1(1.51) | 47.5(3.0) | 20.6(6.84) | 73.5(1.85) | 71.5(3.69) | 74.5(0.756)
NCE+AUL | 73.9(2.25) | 67.3(3.92) | 43.0(6.57) | 22.2(5.15) | 72.9(0.756) | 74.3(1.64) | 71.9(2.25)
NCE+AGCE | 74.1(2.44) | 65.3(3.1) | 42.4(5.79) | 18.0(6.04) | 72.5(0.756) | 72.9(0.99) | 70.7(1.28)
MSE | 72.7(2.47) | 67.5(2.34) | 44.4(4.14) | 23.4(4.35) | 75.4(1.37) | 69.3(2.36) | 68.3(4.07)
MAE | 18.4(3.16) | 18.4(3.16) | 22.2(3.44) | 22.4(3.4) | 18.4(3.16) | 19.4(2.74) | 19.0(1.74)
Letter | ALDR-KL | 86.3(0.366) | 84.7(0.318) | 79.8(0.733) | 50.6(1.5) | 86.4(0.588) | 84.9(0.231) | 81.4(0.56)
LDR-KL | 86.1(0.16) | 84.3(0.416) | 80.2(0.519) | 50.9(1.78) | 85.9(0.073) | 84.0(0.446) | 80.3(0.543)
CE | 83.5(0.208) | 80.5(0.308) | 72.5(1.0) | 24.6(3.34) | 83.3(0.271) | 81.3(0.222) | 75.6(0.331)
SCE | 83.4(0.139) | 80.2(0.336) | 71.8(1.08) | 25.1(3.52) | 83.4(0.224) | 81.2(0.29) | 75.3(0.452)
GCE | 82.9(0.275) | 80.0(0.22) | 70.5(0.924) | 22.7(5.18) | 82.7(0.132) | 80.8(0.212) | 74.8(0.35)
TGCE | 82.9(0.166) | 79.9(0.248) | 70.1(1.41) | 22.7(5.18) | 82.7(0.13) | 80.6(0.232) | 74.7(0.349)
WW | 81.2(0.314) | 79.9(0.3) | 75.1(0.92) | 26.0(1.8) | 80.9(0.236) | 77.1(0.213) | 70.5(0.408)
JS | 82.0(0.277) | 78.7(0.548) | 62.7(0.947) | 16.1(2.3) | 81.8(0.33) | 79.5(0.354) | 72.8(0.376)
CS | 82.2(0.256) | 78.4(0.467) | 73.9(1.06) | 36.9(5.1) | 81.0(0.384) | 77.9(0.585) | 71.3(0.576)
RLL | 79.7(0.635) | 70.9(0.946) | 39.0(1.0) | 9.53(1.78) | 78.9(0.379) | 75.0(0.61) | 66.3(0.624)
NCE+RCE | 69.0(1.46) | 63.0(2.12) | 53.9(4.76) | 20.8(3.81) | 65.9(1.98) | 51.7(1.79) | 47.2(1.54)
NCE+AUL | 67.6(3.46) | 61.1(1.91) | 51.8(2.97) | 12.4(3.06) | 61.2(1.64) | 51.8(3.07) | 44.4(1.32)
NCE+AGCE | 60.0(1.3) | 53.7(3.3) | 41.6(4.46) | 10.6(1.22) | 56.2(2.43) | 45.0(2.56) | 40.7(2.99)
MSE | 31.9(0.666) | 24.5(3.14) | 18.9(2.76) | 9.33(2.23) | 27.9(3.09) | 26.7(2.26) | 26.1(2.76)
MAE | 8.98(0.98) | 8.87(0.827) | 8.86(0.854) | 7.86(0.857) | 9.09(1.02) | 9.05(1.07) | 9.06(1.08)
News20 | ALDR-KL | 96.4(0.294) | 94.3(0.176) | 86.4(0.635) | 30.3(4.97) | 95.2(0.214) | 93.9(0.474) | 92.5(0.494)
LDR-KL | 96.6(0.2) | 94.2(0.243) | 86.6(0.929) | 31.3(3.8) | 95.9(0.229) | 94.2(0.328) | 93.0(0.4)
CE | 78.9(0.557) | 46.7(2.5) | 22.2(0.871) | 9.73(1.16) | 76.4(0.627) | 77.6(0.825) | 76.3(0.699)
SCE | 75.7(0.425) | 41.5(1.61) | 20.9(1.52) | 10.2(0.544) | 73.8(0.705) | 75.1(1.2) | 73.7(0.974)
GCE | 67.7(1.02) | 34.1(1.32) | 18.7(1.03) | 9.89(0.675) | 66.6(1.08) | 67.8(1.29) | 66.6(1.41)
TGCE | 66.8(1.08) | 34.1(1.36) | 18.7(1.29) | 9.89(0.675) | 66.1(1.57) | 66.7(1.52) | 65.3(1.56)
WW | 71.3(1.49) | 49.2(4.92) | 32.4(2.38) | 13.2(3.9) | 69.5(1.48) | 71.0(1.72) | 69.3(1.18)
JS | 35.1(0.868) | 19.3(0.16) | 14.5(1.25) | 11.1(1.15) | 34.2(1.54) | 31.4(1.02) | 31.1(1.47)
CS | 87.3(1.6) | 87.6(0.527) | 69.2(1.1) | 13.9(1.28) | 86.6(1.62) | 81.6(1.45) | 78.8(1.7)
RLL | 18.3(0.375) | 15.2(1.72) | 15.3(0.738) | 9.85(0.707) | 18.8(1.47) | 18.6(0.291) | 18.2(0.759)
NCE+RCE | 94.5(0.263) | 78.7(2.01) | 32.5(2.11) | 10.4(0.362) | 92.4(2.44) | 70.9(1.38) | 66.7(0.689)
NCE+AUL | 65.0(2.38) | 31.8(1.72) | 19.0(1.52) | 11.4(1.0) | 55.7(1.96) | 49.1(3.02) | 46.7(1.9)
NCE+AGCE | 40.8(3.28) | 20.2(1.26) | 14.9(1.39) | 11.8(0.839) | 35.8(0.718) | 30.8(3.36) | 30.9(0.703)
MSE | 16.3(2.1) | 13.4(0.99) | 12.3(1.45) | 9.37(0.252) | 14.5(1.1) | 15.1(1.68) | 13.4(0.983)
MAE | 10.1(0.37) | 10.1(0.476) | 10.4(0.718) | 10.2(0.641) | 10.2(0.333) | 10.2(0.459) | 10.0(0.361)
ALOI | ALDR-KL | 97.5(0.065) | 93.8(0.119) | 88.5(0.191) | 40.4(0.881) | 96.0(0.044) | 92.5(0.098) | 87.6(0.179)
LDR-KL | 96.3(0.126) | 93.7(0.046) | 89.0(0.099) | 40.6(0.671) | 95.0(0.063) | 91.5(0.184) | 85.6(0.185)
CE | 83.4(0.161) | 76.5(0.178) | 53.2(0.725) | 6.14(0.299) | 81.8(0.201) | 72.9(0.215) | 44.0(0.439)
SCE | 82.7(0.168) | 75.0(0.2) | 51.3(0.728) | 6.37(0.36) | 80.9(0.153) | 71.8(0.313) | 42.0(0.235)
GCE | 80.2(0.225) | 69.1(0.329) | 41.1(0.469) | 4.63(0.463) | 77.7(0.189) | 65.2(0.416) | 33.8(0.419)
TGCE | 79.1(0.288) | 67.7(0.345) | 39.9(0.68) | 4.63(0.463) | 76.6(0.183) | 63.7(0.277) | 32.3(0.439)
WW | 71.3(0.462) | 58.4(0.513) | 37.3(0.474) | 4.79(0.159) | 58.8(0.507) | 36.2(0.263) | 16.6(0.255)
JS | 5.75(0.464) | 5.06(0.549) | 2.84(0.399) | 0.267(0.079) | 5.47(0.58) | 4.24(0.419) | 2.74(0.351)
CS | 89.4(0.151) | 80.6(0.246) | 37.8(0.524) | 2.76(0.036) | 87.4(0.07) | 83.0(0.081) | 63.3(0.467)
RLL | 1.15(0.278) | 0.756(0.144) | 0.404(0.14) | 0.28(0.071) | 0.993(0.203) | 0.763(0.149) | 0.578(0.099)
NCE+RCE | 4.47(0.236) | 4.36(0.224) | 3.32(0.498) | 0.433(0.178) | 4.6(0.105) | 3.44(0.237) | 2.4(0.303)
NCE+AUL | 4.58(0.365) | 3.01(0.42) | 1.38(0.339) | 0.222(0.058) | 4.13(0.504) | 2.99(0.308) | 2.04(0.355)
NCE+AGCE | 3.62(0.488) | 1.98(0.42) | 0.887(0.179) | 0.23(0.04) | 3.12(0.648) | 2.18(0.348) | 1.47(0.274)
MSE | 0.483(0.117) | 0.38(0.076) | 0.343(0.071) | 0.222(0.045) | 0.441(0.123) | 0.372(0.08) | 0.38(0.055)
MAE | 0.33(0.087) | 0.313(0.087) | 0.302(0.08) | 0.228(0.039) | 0.313(0.087) | 0.289(0.093) | 0.306(0.097)

Table 9: Testing Top-2 Accuracy (%) with mean and standard deviation for image
dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Kuzushiji-49 | ALDR-KL | 98.2(0.072) | 97.1(0.122) | 94.1(1.39) | 56.2(1.17) | 97.2(0.068) | 96.5(0.306) | 95.8(0.159)
LDR-KL | 98.3(0.022) | 97.0(0.144) | 95.0(0.136) | 55.8(1.09) | 97.2(0.132) | 96.6(0.079) | 95.9(0.207)
CE | 98.4(0.105) | 96.9(0.091) | 89.3(0.318) | 41.5(2.13) | 97.4(0.055) | 96.7(0.136) | 96.1(0.112)
SCE | 98.4(0.133) | 97.1(0.127) | 89.1(0.335) | 41.0(1.29) | 97.4(0.034) | 96.7(0.069) | 96.1(0.1)
GCE | 98.5(0.089) | 97.2(0.104) | 89.1(0.315) | 38.5(1.23) | 97.4(0.057) | 96.7(0.062) | 96.1(0.09)
TGCE | 98.4(0.047) | 97.0(0.261) | 89.2(0.243) | 39.9(1.58) | 97.4(0.071) | 96.7(0.107) | 96.1(0.081)
WW | 98.6(0.129) | 96.1(0.127) | 87.7(0.35) | 38.5(1.47) | 97.6(0.055) | 97.1(0.067) | 96.8(0.079)
JS | 98.3(0.02) | 94.5(0.694) | 90.2(0.839) | 39.8(0.984) | 96.4(0.902) | 94.4(0.11) | 93.8(0.101)
CS | 98.3(0.033) | 90.5(2.17) | 9.45(2.2) | 4.16(0.157) | 97.5(0.148) | 94.1(0.706) | 60.0(2.78)
RLL | 92.7(0.063) | 92.2(0.068) | 83.4(1.25) | 37.5(0.809) | 92.3(0.046) | 89.6(0.896) | 90.4(0.946)
NCE+RCE | 92.1(0.106) | 91.7(0.157) | 71.1(0.649) | 12.0(1.47) | 89.0(0.282) | 84.3(0.436) | 72.3(1.63)
NCE+AUL | 92.3(0.087) | 86.8(0.868) | 67.4(1.33) | 12.9(1.0) | 90.3(0.041) | 87.0(0.349) | 84.3(0.397)
NCE+AGCE | 92.1(0.039) | 78.9(0.777) | 59.1(1.52) | 12.2(0.945) | 89.4(0.867) | 84.3(0.725) | 83.6(0.793)
MSE | 83.8(1.69) | 58.5(1.55) | 36.4(1.54) | 7.29(0.425) | 64.4(1.74) | 48.1(1.43) | 35.5(3.24)
MAE | 4.11(0.125) | 35.6(2.18) | 20.3(2.95) | 6.56(0.394) | 39.5(2.05) | 24.5(1.85) | 18.9(1.57)
CIFAR100 | ALDR-KL | 73.3(0.545) | 65.6(0.435) | 49.0(0.581) | 7.04(0.566) | 70.2(0.503) | 63.7(0.909) | 55.8(0.718)
LDR-KL | 73.5(0.835) | 65.2(0.623) | 49.1(0.759) | 7.09(0.673) | 69.8(0.649) | 63.4(0.647) | 56.6(0.791)
CE | 72.5(0.46) | 62.3(0.622) | 44.5(1.31) | 6.98(0.658) | 69.3(0.36) | 62.0(0.399) | 56.7(0.256)
SCE | 72.5(0.891) | 62.7(0.833) | 43.2(0.764) | 7.41(0.26) | 68.8(0.291) | 62.5(0.761) | 56.7(0.669)
GCE | 73.0(0.409) | 62.5(1.01) | 44.4(0.824) | 7.52(0.318) | 68.9(0.559) | 62.8(0.613) | 56.8(0.51)
TGCE | 72.4(0.447) | 63.5(0.568) | 41.2(0.437) | 7.46(0.358) | 69.5(0.342) | 64.1(0.358) | 55.4(0.447)
WW | 65.8(0.454) | 51.4(0.83) | 32.8(0.992) | 7.65(0.448) | 63.7(0.408) | 60.0(0.319) | 49.7(0.616)
JS | 71.4(0.534) | 65.0(0.837) | 40.1(1.44) | 7.44(0.336) | 70.0(0.362) | 61.8(1.02) | 53.2(0.684)
CS | 16.9(0.687) | 8.32(0.821) | 2.93(0.252) | 2.0(0.008) | 13.2(0.251) | 8.94(0.539) | 5.86(0.63)
RLL | 50.7(2.22) | 43.1(1.08) | 23.6(0.998) | 6.9(0.751) | 48.4(1.02) | 42.4(2.53) | 28.1(1.66)
NCE+RCE | 14.9(1.15) | 10.1(0.349) | 8.23(0.308) | 3.6(1.18) | 13.7(1.34) | 9.88(0.57) | 6.15(0.388)
NCE+AUL | 15.4(0.516) | 12.4(0.327) | 9.48(0.264) | 5.09(1.52) | 14.1(0.742) | 11.9(0.431) | 8.02(0.514)
NCE+AGCE | 15.1(0.399) | 12.3(0.494) | 9.52(0.492) | 4.96(1.71) | 14.1(0.414) | 11.9(0.596) | 8.04(0.371)
MSE | 22.1(0.783) | 16.4(0.64) | 13.6(0.382) | 7.95(0.614) | 18.7(0.426) | 15.2(0.316) | 10.3(0.728)
MAE | 2.13(0.175) | 2.13(0.174) | 1.77(0.284) | 2.01(0.205) | 2.13(0.175) | 2.07(0.087) | 1.93(0.378)
Tiny-ImageNet | ALDR-KL | 59.5(0.166) | 49.9(0.199) | 32.7(0.358) | 2.13(0.681) | 55.9(0.295) | 49.2(0.557) | 42.5(0.248)
LDR-KL | 59.1(0.443) | 49.6(0.361) | 32.6(0.255) | 2.21(0.702) | 55.6(0.222) | 48.9(0.27) | 43.8(0.21)
CE | 59.6(0.258) | 47.8(0.347) | 22.8(0.435) | 2.1(0.356) | 57.1(0.3) | 51.7(0.439) | 43.3(0.31)
SCE | 59.4(0.364) | 47.5(0.566) | 22.3(0.766) | 2.75(0.925) | 57.0(0.288) | 51.7(0.456) | 43.2(0.301)
GCE | 59.5(0.364) | 47.3(0.53) | 19.6(0.816) | 2.19(0.133) | 57.2(0.276) | 51.7(0.263) | 42.9(0.32)
TGCE | 57.8(0.215) | 43.0(0.394) | 17.7(0.783) | 1.85(0.301) | 54.9(0.253) | 49.4(0.281) | 38.6(0.503)
WW | 44.4(0.49) | 31.8(0.349) | 17.3(0.502) | 1.98(0.199) | 41.3(0.214) | 37.4(0.273) | 26.2(0.408)
JS | 49.9(0.386) | 28.3(0.797) | 7.49(0.93) | 2.55(0.349) | 44.8(0.538) | 30.7(0.292) | 19.7(1.37)
CS | 1.86(0.209) | 1.28(0.135) | 1.0(0.0) | 0.988(0.024) | 1.47(0.14) | 1.32(0.087) | 1.14(0.141)
RLL | 13.2(1.22) | 5.82(0.359) | 4.33(0.254) | 1.96(0.603) | 9.55(0.64) | 5.66(0.352) | 4.09(0.178)
NCE+RCE | 2.96(0.125) | 2.93(0.105) | 2.35(0.191) | 1.28(0.18) | 2.73(0.243) | 2.59(0.25) | 2.18(0.243)
NCE+AUL | 3.42(0.135) | 3.07(0.167) | 2.75(0.361) | 1.43(0.37) | 3.26(0.258) | 3.13(0.171) | 2.41(0.206)
NCE+AGCE | 3.44(0.28) | 3.24(0.155) | 2.66(0.31) | 1.47(0.407) | 3.49(0.194) | 3.1(0.161) | 2.39(0.229)
MSE | 4.45(0.162) | 1.99(0.215) | 1.95(0.202) | 1.47(0.154) | 2.18(0.231) | 1.99(0.173) | 1.84(0.167)
MAE | 1.06(0.051) | 1.82(0.183) | 1.43(0.176) | 1.41(0.226) | 1.77(0.186) | 1.75(0.175) | 1.7(0.239)

Table 10: Testing Top-3 Accuracy (%) with mean and standard deviation for
tabular dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Vowel | ALDR-KL | 97.2(0.404) | 89.9(2.02) | 71.9(5.73) | 33.9(8.04) | 97.8(1.34) | 97.8(1.96) | 93.5(1.51)
LDR-KL | 97.2(1.18) | 88.3(2.08) | 63.4(4.44) | 32.9(7.58) | 96.4(1.21) | 96.6(1.03) | 92.9(2.12)
CE | 94.7(2.25) | 89.3(2.9) | 72.1(4.12) | 33.7(3.04) | 97.4(0.495) | 94.7(2.34) | 91.3(1.03)
SCE | 96.6(1.03) | 89.7(1.62) | 69.5(5.21) | 29.5(4.62) | 95.6(1.87) | 95.0(1.69) | 90.9(2.63)
GCE | 95.0(1.43) | 88.9(2.12) | 73.3(2.36) | 28.7(5.44) | 94.3(1.87) | 95.6(1.03) | 90.5(1.37)
TGCE | 95.4(1.87) | 87.1(3.75) | 73.9(2.16) | 28.7(5.44) | 94.3(1.87) | 95.6(1.03) | 90.5(1.37)
WW | 95.8(2.06) | 88.5(0.495) | 68.9(7.27) | 33.9(4.07) | 95.6(1.51) | 93.3(2.97) | 91.1(2.06)
JS | 93.3(1.98) | 89.5(2.27) | 73.3(3.92) | 31.9(3.76) | 93.7(0.756) | 91.7(2.96) | 89.3(1.76)
CS | 95.8(0.756) | 85.7(3.69) | 60.6(6.61) | 31.1(5.25) | 94.3(3.53) | 92.3(1.64) | 87.3(2.44)
RLL | 90.7(1.96) | 88.1(1.62) | 73.5(1.62) | 27.3(6.09) | 90.7(1.49) | 90.5(2.44) | 87.3(0.808)
NCE+RCE | 86.3(1.37) | 82.0(2.06) | 57.4(7.27) | 29.3(3.0) | 88.5(2.27) | 88.3(2.08) | 85.3(1.76)
NCE+AUL | 84.2(1.21) | 81.2(2.68) | 55.6(7.34) | 32.1(3.28) | 86.5(1.03) | 87.1(1.96) | 85.3(1.64)
NCE+AGCE | 83.8(1.81) | 81.6(2.96) | 53.7(6.11) | 26.1(5.25) | 86.9(0.903) | 87.5(1.98) | 84.8(1.81)
MSE | 86.7(3.34) | 81.6(2.16) | 58.8(4.62) | 29.1(5.97) | 86.9(1.43) | 83.0(1.49) | 81.4(2.44)
MAE | 29.3(2.21) | 30.5(3.96) | 29.1(2.59) | 33.3(4.19) | 29.9(4.59) | 30.5(4.67) | 30.7(4.85)
Letter | ALDR-KL | 90.1(0.366) | 88.1(0.264) | 84.7(0.182) | 60.5(2.37) | 90.3(0.471) | 89.0(0.276) | 86.3(0.293)
LDR-KL | 89.3(0.136) | 88.1(0.443) | 84.9(0.481) | 59.8(1.9) | 88.8(0.208) | 88.4(0.35) | 85.5(0.279)
CE | 87.7(0.22) | 85.1(0.246) | 79.6(0.817) | 32.0(3.8) | 87.1(0.185) | 85.9(0.36) | 81.2(0.297)
SCE | 87.5(0.34) | 85.1(0.211) | 79.0(0.997) | 32.0(3.56) | 87.1(0.191) | 85.7(0.225) | 80.8(0.802)
GCE | 87.3(0.294) | 84.6(0.287) | 77.9(0.858) | 29.4(4.31) | 86.9(0.28) | 85.6(0.288) | 80.5(0.329)
TGCE | 87.2(0.186) | 84.6(0.217) | 78.8(1.35) | 29.5(4.42) | 86.9(0.33) | 85.5(0.217) | 80.6(0.215)
WW | 86.8(0.297) | 85.4(0.45) | 81.8(1.0) | 32.6(1.77) | 85.5(0.256) | 83.6(0.134) | 78.5(1.01)
JS | 86.0(0.402) | 83.4(0.22) | 71.5(1.03) | 21.7(3.88) | 85.9(0.22) | 84.4(0.555) | 78.3(0.83)
CS | 86.7(0.301) | 84.3(0.25) | 81.1(0.331) | 47.2(2.34) | 86.0(0.173) | 83.9(0.439) | 78.6(0.48)
RLL | 83.6(0.236) | 76.9(0.927) | 49.3(1.38) | 11.8(2.55) | 83.1(0.34) | 81.5(0.499) | 72.0(0.661)
NCE+RCE | 70.2(1.46) | 64.1(2.54) | 55.3(5.12) | 23.6(3.49) | 67.1(2.24) | 52.9(2.01) | 48.6(1.68)
NCE+AUL | 69.0(3.48) | 62.4(1.84) | 53.1(3.17) | 18.3(2.56) | 62.6(1.67) | 52.9(3.25) | 45.7(1.75)