\section{Introduction}\label{sec:introduction}}




\IEEEPARstart{M}{achine} learning is instrumental to recent advances in artificial intelligence and big data analysis. They have been used in almost every area of computer science and many fields of natural sciences, engineering, and social sciences. Practical applications of machine learning algorithms are also abundant – it is not an exaggeration to say that without efficient and effective machine learning algorithms, many industries such as internet advertisement, automatic driving, and social network mining would not have flourished.

To date, most machine learning models are trained by minimizing a learning objective over a set of training samples. The learning objective is composed of the learning loss corresponding to the errors on the training set, regularizers that control the model complexity, and constraints that incorporate conditions on the model parameters. 

In forming the learning objective, the training loss is a critical component. The loss function is often constructed by aggregating a set of individual values into a single numerical value. The loss measures the quality of the model on a single training sample and is referred to as the \textit{individual loss}. For example, in binary classification, the individual loss usually quantifies the discrepancy between prediction score and label.
On the other hand, the loss that works over all training data is referred to as the \textit{aggregate loss}, which combines individual losses or scores (prediction scores from a model on samples) of a learning model over each training sample. For example, to evaluate the empirical risk of the model on a dataset, the aggregate loss uses the average of individual losses for all training examples. 
The prevalent practice in machine learning is first to choose the form of the individual loss, then construct the aggregate loss. 
For example, in binary classification, we first design the individual loss function based on the hinge function. Second, we calculate each individual loss of samples. Finally, we design aggregate loss based on the average operator to calculate the average loss score among all samples.  


The aggregate losses can be categorized as  decomposable and non-decomposable. The decomposable aggregate loss means it can be decomposed into individual terms for each training sample. The non-decomposable aggregate loss is a function of the entire set of training samples \cite{ranjbar2012optimizing}. For example, the most popular decomposable aggregate loss is the average loss, or empirical risk minimization \cite{vapnik1999nature}. This loss calculates the average value of all individual losses obtained from training samples. In addition, the non-decomposable aggregate losses such as the area under the ROC curve (AUC) loss \cite{yan2003optimizing} and the average precision (AP) loss \cite{baeza1999modern} are widely discussed in the topic of information retrieval. 
On the other hand, most existing individual losses can be decomposed into a combination of individual scores from each class label. 
For example, the cross-entropy loss \cite{murphy2022probabilistic} and the conventional multi-class loss \cite{crammer2001algorithmic}. In this survey, we focus on the decomposable losses, including aggregate losses and individual losses.  Note that we call decomposable aggregate losses as aggregate losses in the following whenever there is no confusion.

To form the decomposable aggregate losses or individual losses, the ranking order is the most significant relation among the individual values that needs to be considered. In addition, a set function \cite{kolmogorov1975introductory} that needs to be applied to map a set of elements to a single value. Therefore, it is natural to define the rank-based set function, named \textit{aggregator}, to construct the specific decomposable aggregate loss and individual loss. For example, the aggregator works on a set of individual losses to construct a specific aggregate loss, and the aggregator works on a set of individual scores that can define an individual loss. Therefore, the rank-based decomposable losses are most important for designing machine learning models, and they have drawn much attention  \cite{fan2017learning, shen2019learning, shen2019iterative, shah2020choosing, roh2021sample, hu2020learning, hu2021sum, hu2021tkml, lapin2015top, lapin2016loss, lapin2017analysis} in the recent years. However, to the best of our knowledge, no systematic survey exists of the rank-based decomposable loss in the current machine learning literature. 


There are several important issues concerning the rank-based decomposable losses.
\begin{enumerate}
    \item \textbf{Definitions of rank-based decomposable aggregate losses and individual losses.} Finding a suitable method to classify and analyze the rank-based decomposable loss is significant. Through the existing works discussed in this survey, we categorize it into two aspects: aggregate loss from sample level and individual loss from label level. However, the formal definitions of these two notions are not evident in the current literature. 
    
    \item \textbf{Aggregator.} Since we need to design a rank-based decomposable loss, we must first determine a specific aggregator (or rank-based set function). The different aggregators may involve different meanings. However, there are no existing systematic studies about the aggregator. 
    In addition,  different aggregators may have relationships with each other. A loss designed based on one aggregator may extend to another task that only needs to change the current aggregator to another aggregator. Therefore, the flexibility of the aggregator is significant. However, a comprehensive relationship among these aggregators is unknown.  
    
    \item \textbf{Geometric  interpretability.}
    The interpretability of the different rank-based decomposable losses is vital in real-world applications because we need to provide convincing evidence to support the final obtained model performance. Several works \cite{blondel2020learning, lapin2015top, kong2020rankmax, lyu2020average} have explored the geometric interpretation of the designed rank-based decomposable losses. However, for more complicated rank-based decomposable losses, their interpretability is still not explored. How to define a general framework that can explain all rank-based decomposable losses in the ranking level is worth exploring.  
    
    \item \textbf{High training time complexity.}
    Training time complexity is significant for a learning model using a rank-based loss. As we know, some aggregators usually involve sorting operation, which may causes more than $O(n\log n)$ time complexity, where $n$ is the total number of elements in a ranked list. As such, directly sort the elements may slow the training, especially for a large number of training samples or class labels. How to find an efficient optimization strategy remains critical for the applicability of the rank-based decomposable losses.
    
   
   
\end{enumerate}



\subsection{Related Works}
There exist several surveys \cite{wang2021survey, jadon2020survey, tian2022recent, li2011short, ranjbar2012optimizing, li2014learning, yang2022auc, nie2018investigation, wang2020comprehensive} on loss functions. Specifically, \cite{wang2021survey, jadon2020survey, tian2022recent} focus on loss functions that are used in specific learning tasks or domains such as face recognition, semantic segmentation, computer vision, etc. 
\cite{nie2018investigation} investigates the commonly used loss functions in general machine learning, such as classification and regression. \cite{wang2020comprehensive} revisits many existing loss functions in machine learning from two aspects: traditional machine learning (classification, regression, and unsupervised learning) and deep learning (object detection and face recognition). However, the loss functions discussed in these surveys are only focused on the individual loss level. They assume the loss functions use the average operator in the sample level. On the other hand, 
\cite{li2011short, ranjbar2012optimizing, li2014learning, yang2022auc} discuss the losses from the information retrieval area. However, they only view the losses from the perspective of evaluation metrics. \textit{There is no system survey about rank-based decomposable Losses, especially view losses from the aggregator that aggregates a set of values to a single value. }



    
    
 
 

\subsection{Contributions}
\begin{enumerate}
    \item This is the first comprehensive survey on rank-based decomposable losses in machine learning. Some of the relevant surveys in the past only focus on the loss functions from a specific topic. Others summarize very commonly used loss functions in machine learning. 
   
   
    Up to now, there is no dedicated and comprehensive survey on rank-based decomposable losses. This work fills this gap. Through this organized and systematic survey, we expect to help push research in this field forward.
    
    
    \item We organized this survey for rank-based decomposable loss functions from two novel aspects: aggregate loss level and individual loss level. This perspective has not been discovered in the past. Furthermore, this taxonomy can be extended to the general losses in machine learning, deep learning, data mining, etc., and can help  researchers to design loss more flexibly in the future.
    
    \item We introduce a new set function based on ranking, named aggregator, and use it to formulate aggregate and individual losses. Based on existing rank-based decomposable losses, we classify the aggregator into eight categories and analyze their relationships and properties.
 
    \item This survey reviews the most up-to-date rank-based decomposable losses in machine learning. The related topics include  general machine learning, deep learning, trustworthy machine learning, application, etc. Most of the papers are published in top-tier conferences and leading journals in machine learning, data science, deep learning, and artificial intelligence. We first summarize two types of loss functions based on our defined aggregator. Then, we comprehensively review existing works from the perspectives of rank-based aggregate loss and rank-based individual loss. In particular, each perspective is organized according to the types of aggregators. 
    
    \item 
    We also provide six directions for future works including new aggregators and nested aggregators, geometric interpretation of losses, converting non-decomposable losses to decomposable ones, statistical machine learning theory, aggregate gradients, and hyperparameter learning. These opportunities indicate that the issues we discussed have not been fully solved.   
    
\end{enumerate}
The remainder of this survey is organized as follows. 
\begin{itemize}
    \item In Section \ref{sec:background}, we introduce some notations and the formula of the learning objective.
    
    \item In Section \ref{sec:loss_functions}, we formulate loss functions from aggregate loss and individual loss aspects. We also provide examples from supervised and unsupervised learning to explain these two types of losses.
    
    \item In Section \ref{sec:set_operation}, we introduce a rank-based set function named aggregator. We also define aggregate loss and individual loss based on the aggregator. Then we analyze the general properties of the aggregator.
    
    \item In Section \ref{sec:aggregate_loss}, we provide a collection of published works in rank-based aggregate losses and summarize them into different aggregators. 
    
    \item In Section \ref{sec:individual_loss}, we survey recent papers about rank-based individual losses and summarize them into different aggregators. 
    
    \item In Section \ref{sec:other_topics}, we connect the rank-based losses with several hot topics in machine learning to demonstrate their applicability and popularity.
    
    \item In Section \ref{sec:future_directions}, we discuss remaining and emerging issues in rank-based losses. In the meantime, we provide suggestions about the directions for future works. We conclude this survey in Section \ref{sec:conclusion}. 
\end{itemize}
   





\section{Background}\label{sec:background}

\subsection{Notation} \label{sec:notation}
We introduce some necessary notations that will be used in the following sections. Let $\mathbb{R}$ be the real domain and $\mathbb{R}_+$ is the nonnegative domain of $\mathbb{R}$. Denote $\mathbb{N}_n$ as the set $\{1,\cdots,n\}$, $\mathbb{N}_C$ as the set $\{1,\cdots,C\}$, and $\mathbb{I}_{a}$ as an indicator function with $\mathbb{I}_{a}=1$ if $a$ is true and 0 otherwise. 
A hinge function is defined as $[x]_+=\max\{0,x\}$. Let $\|\mathbf{x}\|_1$, $\|\mathbf{x}\|_2$, $\|\mathbf{x}\|_\infty$ be the $l_1$, $l_2$, and $l_\infty$ norms of a vector $\mathbf{x}$, respectively. For a set $S=\{s_1,\cdots,s_n\}\subset \mathbb{R}^n$, we define its ranked version as an ordered set (ranked list) $\left<S\right>=\left<s_{[1]},\cdots,s_{[n]}\right>$, with $s_{[1]}\geq\cdots\geq s_{[n]}$, obtained by sorting elements of $S$ in the descending order. $|S|$ is the cardinality of a set $S$. $s_{[k]}$ denotes the top-$k$ element, which is the $k$-th largest element in $S$ (as well as $\left<S\right>$). Without loss of generality, we only consider $S$ with no ties since ties can be broken in any consistent way.


\subsection{Learning Objective}
The central task of a machine learning algorithm is to ``train'' a model using training data, which entails seeking models that minimize certain performance metrics known as the \textit{losses}. The losses are usually combined with the regularization terms and constraints to form a \textit{learning objective}, which is a quantity to be optimized in training. 
A general learning objective can be represented as follows,
\begin{equation*}
    \begin{aligned}
    \min_f \ \mathcal{L}(f, \mathcal{D}) + \alpha \Omega(f), \ \ \ 
    \mbox{s.t.} \ \mathcal{C},
    \end{aligned}
\end{equation*}
where $f\in \mathcal{H}$ is a function ({\em i.e.}, learning model.) from the hypothesis space (function family) $\mathcal{H}$. $\mathcal{D}$ is a training dataset. $\mathcal{L}(\cdot, \cdot)$ is the loss or empirical risk. $\Omega(f)$ is the regularization term representing the model complexity. $\alpha$ is the trade-off to balance the loss and the model complexity. $\mathcal{C}$ represents the constraints for specific learning scenarios. The loss is the core part of the learning objective. 


\section{Loss Functions}\label{sec:loss_functions}
In this section, we will introduce the definitions of aggregate loss and individual loss, and provide a few examples in supervised and unsupervised learning. 

\begin{figure*}[t]
\centering
\includegraphics[trim=1 1 1 1, clip,keepaspectratio, width=1\textwidth]{figs/loss_relationship.pdf}
\caption{\it Illustrative examples of the relationships between individual loss and aggregate loss in binary classification, multi-class/label classification, regression, and unsupervised learning.
}
\vspace{-0.5cm}
\label{fig:losses}
\end{figure*}


\subsection{Aggregate Loss and Individual Loss }
We refer to the loss over all training data as the \textbf{aggregate loss}, in order to distinguish it from the
\textbf{individual loss} that measures the quality of the model on a single training sample. The relationship between aggregate loss and individual loss can be found in Fig. \ref{fig:losses}. 

We denote $\mathcal{X}$ and $\mathcal{Y}$ as the input feature domain and target domain, respectively. Then a joint domain can be represented as $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$. 
A training dataset is $\mathcal{D}=\{\mathbf{z}_1,\cdots,\mathbf{z}_n\}$, where $\mathbf{z}_i=(\mathbf{x}_i,\mathbf{y}_i)$ is a finite subset of $\mathcal{Z}$. 
The aggregate loss and individual loss can be represented as,
\begin{equation*}
    \begin{aligned}
    \mathcal{L}(f, \mathcal{D}) = \underbrace{\mathcal{L}\big(\{\overbrace{\ell(f(\mathbf{x}_i),\mathbf{y}_i)}^{\textbf{\mbox{individual loss}}}|i\in \mathbb{N}_n\}\big)}_{\textbf{\mbox{aggregate loss}}},
    \end{aligned}
\end{equation*}
where the aggregate loss function $\mathcal{L}(\cdot)$ can be constructed by a linear combination of individual loss function $\ell(\cdot,\cdot)$ over individual samples. For example, the most popular decomposable aggregate loss is the average loss, which is also called empirical risk \cite{vapnik1999nature}. 

The aggregate loss can be \textit{decomposable} or \textit{non-decomposable}. The decomposable aggregate loss can be formed from the ensemble of individual losses, while the non-decomposable aggregate loss cannot. We focus on the decomposable aggregate losses in this survey since many non-decomposable aggregate losses have been studied and discussed in the existing literature, especially from the information retrieval area \cite{liu2009learning, li2011short, ranjbar2012optimizing}. We mention aggregate loss, meaning decomposable aggregate loss, whenever there is no confusion. 

\subsection{Examples of Loss functions in (Un)Supervised Learning}

We give a few examples of individual and aggregate losses in supervised and unsupervised learning.




\textbf{Supervised learning}. For a supervised learning problem, the goal of the learning task is to find a parametric predictor (or model) $f:\mathcal{X}\rightarrow \mathcal{Y}$ from a function family $\mathcal{H}$ that can be used to predict the label or value of a new sample $\mathbf{x}$. We introduce an \textit{individual loss} $\ell$ as a bi-variate function $\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow \mathbb{R}_+$ for evaluating the fitting quality of $f$. $\ell(f(\mathbf{x}), \mathbf{y})$ quantifies the discrepancy between the prediction $f(\mathbf{x})$ and ground truth target $\mathbf{y}$, with $\ell(f(\mathbf{x}),\mathbf{y})=0$ when they are in agreement. 
\begin{itemize}
    \item The explicit form of individual loss is dominated by a specific learning task. 
    \begin{itemize}
        \item In binary classification ({\em i.e.}, $\mathbf{y}\in\mathcal{Y}=\{\pm 1\}$), $\ell$ can be the 0/1 loss $\mathbb{I}_{\mathbf{y} f(\mathbf{x})<0}$, the logistic loss $\log_2(1+e^{-\mathbf{y} f(\mathbf{x})})$, the hinge loss $[ 1-\mathbf{y} f(\mathbf{x})]_+$, and the binary cross entropy loss $-\mathbf{y}\log f(\mathbf{x})-(1-\mathbf{y})\log(1-f(\mathbf{x}))$, etc.
        \item In multi-class classification ({\em i.e.}, $\mathbf{y}\in\mathcal{Y}=\{1, \cdots, C\}$, where $C> 2$.), $\ell$ can be the conventional multi-class loss \cite{crammer2001algorithmic}: $\max_{j\in\mathcal{Y}}\{\mathbb{I}_{j\neq\mathbf{y}}+f_j(\mathbf{x})-f_{\mathbf{y}}(\mathbf{x})\}$, where $f_j(\mathbf{x})\in \mathbb{R}$ corresponding to the prediction score of $\mathbf{x}$ with regards to the $j$-th class. 
        \item In multi-label classification ({\em i.e.}, $\mathbf{y}\subset\mathcal{Y}=\{1, \cdots, C\}$, where $C> 2$.), $\ell$ can be the conventional multi-label loss \cite{crammer2003family}: $[1+\max_{j\notin \mathbf{y}} f_j(\mathbf{x})-\min_{j\in\mathbf{y}}f_j(\mathbf{x})]_+$.
        \item In regression ({\em i.e.}, $\mathbf{y}\in\mathcal{Y}=\mathbb{R}$), $\ell$ can be the squared $l_2$ difference $\|\mathbf{y}-f(\mathbf{x})\|_2^2$, absolute difference $\|\mathbf{y}-f(\mathbf{x})\|_1$, and Huber loss\cite{friedman2001elements}. 
    \end{itemize}
    More types of individual losses can be found in a survey paper \cite{wang2020comprehensive}.
    \item The most popular aggregate loss is the average loss \cite{vapnik1999nature}, which using the average of individual losses for all training samples and can be defined as $\mathcal{L}(f, \mathcal{D})=\frac{1}{n}\sum_{i\in \mathbb{N}_n}\ell(f(\mathbf{x}_i),\mathbf{y}_i)$. The maximum aggregate loss \cite{shalev2016minimizing} $\mathcal{L}(f, \mathcal{D})=\max_{i\in \mathbb{N}_n}\ell(f(\mathbf{x}_i),\mathbf{y}_i)$ is also widely used in the supervised learning tasks. It uses the maximum individual loss to learn the model.
   
\end{itemize}



\textbf{Unsupervised learning}. In unsupervised learning, there are two major learning tasks: clustering and dimension reduction. For clustering, the objective is to divide samples into different clusters according to the similarity index. For dimension reduction, a projector is applied to project the original high-dimensional feature space into low-dimensional space. Then the similarity is calculated between these two spaces to determine the preserving ability of data structure and usefulness. Since there are no ground truth targets in the learning problems, the individual loss will only depend on the scores and features. 
For example,
\begin{itemize}
    \item The implicit form of individual loss can be the reconstruction error in dimension reduction problems, which is applied to measure the distance between the original sample and the reconstructed sample according to the inverse projection mapping. For example, in principal component analysis (PCA) \cite{wold1987principal},  the loss can be defined as $\|h^{-1}(\widetilde{\mathbf{x}}_i)-\mathbf{x}_i\|_2$, where $\widetilde{\mathbf{x}}_i$ is the low-dimensional representation of $\mathbf{x}_i$ and $h$ is the projection mapping. 
    \item The aggregate loss can simply be an average or sum of reconstruction errors over all samples, as  $\sum_{i=1}^n\|h^{-1}(\widetilde{\mathbf{x}}_i)-\mathbf{x}_i\|_2$.
   
   
   
   
   
    
   
    
\end{itemize}


\section{Aggregator for Decomposable Losses}\label{sec:set_operation}
In this section, we will introduce and define a rank-based set function, named aggregator. Then we will discuss its general properties.






\subsection{Aggregator}\label{sec:aggregator}
For a set of real numbers representing individual values, the ranking order reflects the most fundamental relation among them. Therefore, designing aggregate loss and individual loss can be achieved by choosing operations defined based on the ranking order of the individual values. Such individual values can be the individual losses for aggregate loss on the data sample level or can be the individual scores for individual loss on the data label level, where the number of labels should be greater than 1. 
Therefore, in this survey, we focus on rank-based aggregate loss and rank-based individual loss.  






At a more general level, we noticed that once the set of all individual losses, $\ell(\mathcal{D}):=\{\ell_1,\cdots, \ell_n\}$ with $\ell_i=\ell(f(\mathbf{x}_i), \mathbf{y}_i)$ (or $\ell_i=\ell(f(\mathbf{x}_i))$ if targets (labels) are not available in unsupervised learning scenario), is determined, a decomposable aggregate loss can be constructed without concerning the form of the learning model $f$, the choice of the individual loss $\ell$, and the training data $\mathcal{D}$. This means that a decomposable aggregate loss is completely determined by a rank-based \textit{set function} \cite{kolmogorov1975introductory} that maps a set, {\em i.e.}, $\ell(\mathcal{D})$, to a real number while considering the ranking order among elements in the set. In this survey, we term such function as an \textbf{\textit{aggregator}}. Therefore, the relationship of aggregate loss, aggregator, and individual loss is as follows,
\begin{equation*}
    \begin{aligned}
    \underbrace{\mathcal{L}(\ell(\mathcal{D}))}_{\textbf{\mbox{aggregate  loss}}}:=\underbrace{\mathcal{L}}_{\textbf{\mbox{aggregator}}}\big(\{\underbrace{\ell_i}_{\textbf{\mbox{individual  loss}}}|i\in \mathbb{N}_n\}\big).
    \end{aligned}
\end{equation*}
Note that $\mathcal{L}(\ell(\mathcal{D}))$ is just  $\mathcal{L}(f,\mathcal{D})$, which we used in the previous section. For instance, the average loss is constructed from the average aggregator that computes the arithmetic average of a set $\mathcal{L}_{avg}(\ell(\mathcal{D}))=\frac{1}{n}\sum_{i=1}^n\ell_i$. The maximum loss corresponds to the maximum aggregator, $\mathcal{L}_{max}(\ell(\mathcal{D}))=\max_{i\in \mathbb{N}_n}\ell_i$. Similarly, the average top-$k$ (AT$_k$) loss originates from the AT$_k$ aggregator, which is defined as $\mathcal{L}_{at-k}(\ell(\mathcal{D}))=\frac{1}{k}\sum_{i=1}^k\ell_{[i]}$.



In the aggregate loss, the aggregator works at the data sample level. However, the aggregator can also work at the label level, which corresponds to the aggregator for the individual loss. Therefore, the relationship between  individual loss, aggregator, and the individual score is as follows,
\begin{equation*}
    \begin{aligned}
    \underbrace{\ell_i}_{\textbf{\mbox{individual  loss}}}:=\underbrace{\mathcal{L}}_{\textbf{\mbox{aggregator}}}\big(\{\mathcal{O}(\underbrace{f_j(\mathbf{x}_i)}_{\textbf{\mbox{individual  score}}}, \mathbf{y}_i)|j\in \mathbb{N}_C\}\big),
    \end{aligned}
\end{equation*}
where $f_j(\mathbf{x}_i)$ is the prediction score of $\mathbf{x}_i$ on $j$-th class. $\mathcal{O}$ is a function, which can output a value based on $f_j(\mathbf{x}_i)$ and $\mathbf{y}_i$. To simplify the notation, we let $\mathbb{O}(f(\mathbf{x}_i))=\{\mathcal{O}(f_j(\mathbf{x}_i), \mathbf{y}_i)|j\in \mathbb{N}_C\}$. The rank-based individual losses are widely used in multi-label and multi-class learning. 
For example, let us assume a general multi-label classification problem with a total of $C> 2$ possible labels. For an input $\mathbf{x}_i\in \mathcal{X}$, its true labels are represented by a set of labels $\oldemptyset \neq \mathbf{y}_i\subset\{1,\cdots, C\}$. We introduce a continuous multi-label prediction set $F(\mathbf{x}_i)=\{f_1(\mathbf{x}_i),\cdots, f_C(\mathbf{x}_i)\}$ and $\mathcal{O}(f_j(\mathbf{x}_i),\mathbf{y}_i)=[1+f_j(\mathbf{x}_i)\times \mathbb{I}_{j\notin \mathbf{y}_i}-\min_{y\in \mathbf{y}_i}f_y(\mathbf{x}_i)]_+$. The conventional multi-label loss \cite{crammer2003family} can be constructed from the maximum aggregator such as $\ell_i=\mathcal{L}_{max}(\mathbb{O}(f(\mathbf{x}_i)))= \max_{j\in\mathbb{N}_C}\mathcal{O}(f_j(\mathbf{x}_i),\mathbf{y}_i)=[1+\max_{j\notin \mathbf{y}_i}f_j(\mathbf{x}_i)-\min_{j\in \mathbf{y}_i}f_j(\mathbf{x}_i)]_+ $. Note that it becomes the conventional multi-class loss \cite{crammer2001algorithmic} when $|\mathbf{y}_i|=1, \forall i\in \mathbb{N}_n$. 



\subsection{General Properties of Aggregator} \label{sec:prop_agg}
Before we study the properties of the aggregator, we first summarize all existing aggregators in the literature. We will introduce more details about using them in the following sections. By using the notation from Section \ref{sec:notation}, the existing aggregators can be organized as follows, 
\begin{enumerate}
    \item \textbf{Average}:
    \begin{equation*}
        \mathcal{L}_{avg}(S)=\frac{1}{n}\sum_{i=1}^ns_i.
    \end{equation*}
    Note that there is a variant of the average aggregator, which omits the factor $\frac{1}{n}$ and then becomes the sum aggregator. We do not distinguish `sum' from `average' for notational clarity.  This also holds for the following aggregators. 
    \item \textbf{Maximum}:
    \begin{equation*}
        \mathcal{L}_{max}(S)=\max_{1\leq i\leq n}s_i=s_{[1]}.
    \end{equation*}
    
    \item \textbf{Median}: 
    \begin{equation*}
        \mathcal{L}_{med}(S)={1 \over 2}
    \left(s_{\left[\lfloor \frac{n+1}{2}\rfloor\right]} + s_{\left[\lceil \frac{n+1}{2} \rceil\right]}\right).
    \end{equation*}

    
    \item \textbf{Top-$k$}:
    \begin{equation*}
        \mathcal{L}_{top-k}(S)=s_{[k]}.
    \end{equation*}
    
    \item \textbf{Average Top-$k$ (AT$_k$)}:
    \begin{equation*}
        \mathcal{L}_{at-k}(S)=\frac{1}{k}\sum_{i=1}^ks_{[i]}.
    \end{equation*}
    
    \item \textbf{Average Bottom-$k$ (AB$_k$)}:
    \begin{equation*}
        \mathcal{L}_{ab-k}(S)=\frac{1}{k}\sum_{i=n-k+1}^ns_{[i]}.
    \end{equation*}
    
    \item \textbf{Average of Ranked Range (AoRR)}:
    \begin{equation*}
        \mathcal{L}_{aorr}(S)=\frac{1}{k-m}\sum_{i=m+1}^ks_{[i]}.
    \end{equation*}
    
    \item \textbf{Close-$k$}:
    \begin{equation*}
        \mathcal{L}_{close-k}(S)=\sum_{i=1}^n\Big[s_{[n-i+1]}\cdot\mathbb{I}_{i\leq k}+M\cdot\mathbb{I}_{i>k \& \text{condition}}\Big],
    \end{equation*}
    where `condition' means $s_{[n-i+1]}$ incorrectly  classified, $M$ is a preset constant, and $s_{[n-i+1]}$ is the individual loss $s_j$ with the ($n-i+1$)-th largest $|s_j-T|$ such that T is another preset constant.
\end{enumerate}
The relationships between these aggregators can be found in Fig. \ref{fig:aggregators}.

\begin{figure}[t]
\vspace{-\intextsep}
\centering
\includegraphics[trim=1 1 1 1, clip,keepaspectratio, width=0.45\textwidth]{figs/aggregators.PNG}
\caption{\it The relationships between aggregators. $k$ or $m$ are the hyperparameters of the source aggregator. $n$ is the total number of samples (for aggregate loss) or total number of labels (for individual loss). And $0\leq m< k\leq n$. $T$ is a specific hyperparameter for Close-k aggregator. 
}
\vspace{-0.5cm}
\label{fig:aggregators}
\end{figure}

By further studying the properties of general aggregator, we can gain more insights into its role in machine learning algorithms. 
We identify a list of properties that desirable aggregators tend to possess: 

\begin{enumerate}
    \item \textbf{Invariant to permutations}: $\mathcal{L}(S)$ should not change as the elements of $S$ undergone a permutation operation, {\em i.e.}, $\mathcal{L}(S)=\mathcal{L}(\left<S\right>)$.
    \item \textbf{Stable with input size}: a large set does not have an advantage over a smaller set as input,  {\em i.e.}, $\mathcal{L}(S)/|S|=O(1)$.
    \item \textbf{(Convexity,) continuous and differentiable}: an aggregator invariant to permutation is uniquely determined by a function of the vector with $s_1\geq\cdots \geq s_n$ and that function is differentiable (and convex \cite{boyd2004convex}).
\end{enumerate}

For instance, in aggregate loss scenario, it is not difficult to prove that $\mathcal{L}_{avg}$ satisfies properties 1)-3). In \cite{fan2017learning}, the authors show that the AT$_k$ aggregator is permutation invariant, size invariant, convex and continuous, and so does $\mathcal{L}_{max}$ as a special case of $\mathcal{L}_{at-k}$. On the other hand, the top-$k$ aggregator, $\mathcal{L}_{top-k}(S)=s_{[k]}$, which leads to the top-$k$ loss, {\em i.e.}, $\mathcal{L}_{top-k}(\ell(\mathcal{D}))=\ell_{[k]}$ as the $k$-th largest individual loss, is a continuous but non-convex and non-differentiable aggregator. This is because $s_{[k]}=k\mathcal{L}_{at-k}(S)-(k-1)\mathcal{L}_{at-(k-1)}(S)$. Therefore, it is the difference of two convex functions. In general, it is not a convex function of sorted elements of $S$. 


As we discussed before, for a set of real numbers representing individual values, the ranking order reflects the most basic relation among them. Therefore, designing aggregate losses and individual losses can be achieved by choosing operations of aggregator defined based on the ranking order of the individual values. This makes the top-$k$ aggregator $\mathcal{L}_{top-k}$ the basic building block of permutation invariant aggregators. A special case of $\mathcal{L}_{top-k}$ is when $k=\lfloor \frac{n+1}{2}\rfloor$ (assume $n$ is odd), which corresponds to the median aggregator that is known to be robust to outliers in individual losses. However, as shown earlier, one drawback of $\mathcal{L}_{top-k}$ is that it is non-convex, which makes the aggregate loss difficult to use in practice. On the other hand, there are some interesting relations between $\mathcal{L}_{top-k}$ and $\mathcal{L}_{at-k}$: both are generalizations of the maximum operator $\mathcal{L}_{max}$ ($k=1$), and the latter is a tight convex upper-bound of the former, as $\mathcal{L}_{at-k}\geq \mathcal{L}_{top-k}$ with equality holds when all $s_i$ are the same. All these suggest that the AT$_k$ aggregator has some uniqueness in all rank-based aggregators. $\mathcal{L}_{at-k}$ can be the minimal convex rank-based aggregator, and $\mathcal{L}_{at-k}$ of different degree $k$ form a subspace of rank-based aggregator that can be used to approximate other aggregators based on order statistics \cite{arnold2008first}.













\section{Rank-based Aggregate Losses }\label{sec:aggregate_loss}
In this section, we will introduce seven types of rank-based aggregate losses and connect them with many popular topics in machine learning. 


\subsection{Average Aggregate Loss}
The prevalent practice in machine learning is first to choose the form of the individual loss, then construct the aggregate loss using the average of individual loss for all training examples. We term this specific aggregate loss as the average (aggregate) loss \cite{vapnik1999nature}, which can be formulated by
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{avg}(\ell(\mathcal{D}))=\frac{1}{n}\sum_{i=1}^n\ell_i=\frac{1}{n}\sum_{i=1}^n \ell_{[i]},
    \end{aligned}
\end{equation*}
where $\ell_i=\ell(f(\mathbf{x}_i), y_i)$ and $\ell_{[i]}$ is the top-$i$ individual loss in the set $\{\ell_1,\cdots, \ell_n\}$. From the above, we can find the average loss can also be viewed as a rank-based aggregate loss.

The average loss is the dominant  paradigm for performance evaluation in machine learning. A possible consensus \cite{holland2021designing} is that it comes from the Perceptron of Frank Rosenblatt in the 1950s \cite{rosenblatt1958perceptron}, and the proof in the 1962s of the convergence of the perceptron learning algorithm for linearly separable data \cite{novikoff1963convergence} \cite[Chapter 11]{minsky1969introduction}. This significant result has been recognized as having effectively \textit{statistical learning theory} \cite{vapnik1999nature}.
Besides the simplicity, there are important reasons favoring the average loss. First, finding individual loss that bears relevance to the corresponding machine learning task is practically easier. For instance, logistic loss, hinge loss, or cross-entropy loss are typical choices for individual losses for classification, as the squared $l_2$ loss, absolute loss, or Huber loss for regression. Similarly, in unsupervised learning or probabilistic modeling, individual loss can be interpreted as \textit{empirical risk minimization} (ERM) \cite{bartlett2006convexity, de2005model, steinwart2003optimal, wu2006learning} in supervised learning or \textit{maximum (log)-likelihood} in unsupervised learning \cite{friedman2001elements}, which further provide theoretical underpinning for this choice. The last but not least important factor for using the average loss is that minimizing the average loss can be solved with efficient stochastic gradient descent \cite{robbins1951stochastic} algorithms on huge datasets.


\subsection{Maximum Aggregate Loss}
The work \cite{shalev2016minimizing} has shown some drawbacks of the average loss in adapting to imbalanced data distributions and explored choices other than the average loss for the aggregate loss formed from individual losses, {\em e.g.}, the maximum (aggregate) loss,
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{max}(\ell(\mathcal{D}))=\max_{i\in \mathbb{N}_n}\ell_i=\ell_{[1]}.
    \end{aligned}
\end{equation*}
It is obvious that the maximum loss also belongs to the rank-based aggregate loss because it only extracts the largest (top-1) individual loss for learning. 

Problems of maximum loss play significant roles in optimization and machine learning. When $\ell_i$ is a linear function, the maximum loss will be equivalent to hard-margin SVM training (with $\ell_i$ representing the negative margin on the $i$-th sample) \cite{clarkson2012sublinear, hazan2011beating}, which is particularly important for machine learning. Going beyond the linear case, the authors in \cite{shalev2016minimizing} argue that minimizing the maximum loss can benefit training speed and generalization in the presence of rare informative samples. Furthermore, it is also the basic paradigm of robust optimization \cite{ben2002robust, namkoong2016stochastic}. Several works follow \cite{shalev2016minimizing} to discuss the optimization of maximum loss since the learning objective based on the maximum loss is known as the minimax learning \cite{lan2020first}. For example, the goal of \cite{chen2017robust} is to find a minimax solution that optimizes in the worst case over all individual losses. A recent work \cite{carmon2021thinking} addresses the complexity of minimizing the maximum loss for convex, Lipschitz, and non-smooth functions of $\ell_i$. In \cite{mohri2019agnostic}, the maximum loss is applied to subsets of the dataset instead of single data points in federated learning.    

\subsection{Median Aggregate Loss}
It is clear that the average aggregate loss is not stable and does not allow overcoming  the outlier problem. Therefore, instead of the average loss, for robust estimating of the mean, one may use the median aggregate loss \cite{shibzukhov2021principle, shibzukhov2022minimizing} as follows,
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{med}(\ell(\mathcal{D}))={1 \over 2}
    \left(\ell_{\left[\lfloor \frac{n+1}{2}\rfloor\right]} + \ell_{\left[\lceil \frac{n+1}{2} \rceil\right]}\right).
    \end{aligned}
\end{equation*}
We have $\mathcal{L}_{med}(\ell(\mathcal{D}))=\ell_{[\frac{n+1}{2}]}$ if $n$ is odd and $\mathcal{L}_{med}(\ell(\mathcal{D}))=\frac{1}{2}(\ell_{[\frac{n}{2}]}+\ell_{[\frac{n+2}{2}]})$ if $n$ is even. 

\textbf{Connect with least median squares (LMS)}. The median loss is also widely used in regression and classification. For example, to construct a robust regression, the method of the least median squares (LMS) \cite{rousseeuw1984least, rousseeuw1984robust} is proposed. Since a few outliers with significant errors cannot affect the value of median squared error, LMS is regarded as one of the most robust aggregate losses in regression. Inspired by the LMS, a robust class conditional median loss is proposed for the classification task in \cite{ma2011robust}, which uses the summation of the median individual losses in each class. Directly optimizing the median loss is impossible since it is not continuously differentiable. Therefore, some works \cite{shibzukhov2021principle,shibzukhov2022minimizing} have proposed an iterative reweighting scheme that can be used to optimize it. 

\textbf{Connect with median-of-means (MOM)}. The median-of-means estimator is proposed by Nemirovsky and Yudin \cite{nemirovskij1983problem}, which has been proved robust to outliers. It can be regarded as a variant of median aggregate loss. The traditional MOM estimator procedure is as follows, first, randomly partition N samples into M batches. Then calculates the mean for each batch. Finally, outputs the median of these batch mean. Very recently, MOM estimators have been used for high dimensional robust regression \cite{brownlees2015empirical, hsu2016loss, jalal2020robust, lecue2020robust, lugosi2019risk} by applying MOM estimator on the loss function of empirical risk minimization process. A recent work \cite{liu2022robust} proposes a robust imitation learning model by minimizing a MOM-based learning objective. 



\subsection{Average Top-$k$ (AT$_k$) Aggregate Loss}\label{sec:atk}
The median loss can solve the outlier problem. However, it loses a good property of the maximum loss, which cannot adapt to the imbalanced data scenario. In addition, the median loss generally does not lead to a convex learning objective. 
To mitigate these drawbacks, the average top-$k$ (AT$_k$) loss \cite{fan2017learning} is proposed, which is the average of the largest $k$ individual losses, that is defined as:
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{at-k}(\ell(\mathcal{D}))=\frac{1}{k}\sum_{i=1}^k\ell_{[i]},
    \end{aligned}
\end{equation*}
where $1\leq k\leq n$. We can find that the AT$_k$ loss generalizes the average loss ($k=n$) and the maximum loss ($k=1$). Therefore, it can adapt to imbalanced and/or multi-modal data distributions better than the average loss and is less sensitive to outliers than the maximum loss.

Since the AT$_k$ loss involved the sorting operation, it will bring a high time complexity in the training when directly optimizing it. Therefore, \cite{fan2017learning} proposes a reformulation of the AT$_k$ loss as the minimum of the average of the individual losses over all training examples transformed by a hinge function as $\mathcal{L}_{at-k}(\ell(\mathcal{D}))=\min_{\lambda}\frac{1}{n}\sum_{i=1}^n[\ell_i-\lambda]_++\frac{k}{n}\lambda$.

\textbf{Connect with condition value at risk (CVaR)}. Many works \cite{williamson2019fairness, curi2020adaptive, lee2020learning, laguel2021superquantiles, holland2021spectral, laguel2022superquantile} study and prove that the reformulated AT$_k$ loss is equivalent to the risk measure called CVaR \cite[Chapter~6]{ shapiro2021lectures} in portfolio optimization for effective risk management, which leads another reason why AT$_k$ loss is a robust learning approach for training machine learning models.
The work \cite{williamson2019fairness} also studies the connection between AT$_k$ loss and fairness based on CVaR. Robey et al. \cite{robey2022probabilistically} connect CVaR with Adversarial Training and then design a probabilistically robust learning model.  

\textbf{Connect with support vector machine (SVM)}. If the individual loss is the hinge loss, the AT$_k$ loss can generalize two convex SVMs such as the C-SVM \cite{cortes1995support} and the $\nu$-SVM \cite{scholkopf2000new}. In addition, the extended $\nu$-SVM (E$\nu$-SVM) \cite{perez2003extension} is also related to AT$_k$ loss, which is only add one additional non-convex constraint to the $\nu$-SVM. Furthermore, Takeda and Sugiyama \cite{takeda2008nu} show that E$\nu$-SVM minimizes CVaR, which is exactly equivalent to minimizing  AT$_k$ loss.  

\textbf{Connect with distributionally robust optimization (DRO)}. Many works such as \cite{lyu2020average, levy2020large, roux2021efficient} connect AT$_k$ loss with DRO \cite{rahimian2019distributionally}, which is a hot topic in operations research and statistical learning communities \cite{ben2002robust} that can handle the data distribution shift problems between training and testing. \cite{zhu2019robust} applies the DRO version of AT$_k$ loss to design a robust game framework for pool-based active learning. \cite{qi2020simple} proposes a DRO-TopK framework based on AT$_k$ loss for pairwise deep metric learning. \cite{sapkota2021distributionally} uses AT$_k$ as a constraint to add into a Gaussian processes mixture framework to design a robust Deep Kernel Multiple Instance Learning model.


\textbf{Connect with learning strategies}. 
In deep learning, the (mini-batch) stochastic gradient descent (SGD) is an effective and efficient optimization approach to optimize the model parameters. Due to all training samples are not equally important and most of them could be ignored after a few epochs of training without affecting the final model performance, \cite{kawaguchi2020ordered} proposes an ordered SGD approach based on AT$_k$, which is used to learn a deep learning model that can improve the testing performance. The constructed optimization and generalization properties confirm the applicability of the ordered SGD. Inspired by ordered SGD, \cite{wu2020curricula} connects AT$_k$ loss to the large current loss minimization.
In addition, \cite{li2020tilted, li2021tilted} propose a tilted empirical risk minimization framework, which generalizes the AT$_k$ loss. In \cite{yuan2020group}, the authors employ the AT$_k$ loss as a classification error measure and propose AT$_k$ group sparse additive machine (AT$_k$-GSAM) for high-dimensional variable selection.

\textbf{Connect with deep learning applications}. The AT$_k$ loss also has many applications in real-world scenarios. For example, \cite{xu2019mixed} combines the average loss and AT$_k$ loss for optic disc and optic cup segmentation with deep learning from imbalanced samples. \cite{lee2018deep,lee2019deep} applies AT$_k$ loss to train a deep learning model for sonar image generation. \cite{huang2020improving} applies the AT$_k$ loss for regression to improve head pose estimation. In a similar task, \cite{jeon2020prima6d} introduce a rotational primitive reconstruction for 6D pose estimation based on AT$_k$ loss.
The authors in \cite{oh2020cnn} design a supervised learning approach based on AT$_k$ loss for identifying ChIP-seq (one of the core experimental resources available to understand genome-wide epigenetic
interactions and identify the functional elements associated with diseases) using convolutional neural networks (CNNs). A top-$k$ cross-entropy loss based on AT$_k$ loss is proposed in \cite{wang2021simultaneous} to design a  multi-task learning framework for simultaneously identifying the right ventricle end-diastolic and end-systolic frames
and detecting anatomical landmarks for echocardiography. The top-$k$ aggregate loss is also extended to generative adversarial network (GAN) models, named top-$k$ GAN in \cite{sinha2020top}. It trains the generator by removing the elements of the mini-batch with the lowest critic outputs. By performing the top-$k$ operation on the predictions from the critic, the generator can generate samples close to the target distribution and make them more realistic.



\subsection{Average Bottom-$k$ (AB$_k$) Aggregate Loss} The AT$_k$ loss can dilute but not exclude the influences of the outliers and noisy labels, which usually appear
as the top individual losses. Therefore, many works \cite{shen2019learning, shen2019iterative, shah2020choosing, roh2021sample} only consider the small losses for the optimization during the training. In this case,  the average bottom-$k$ (AB$_k$) loss is proposed based on these works and can be defined as 
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{ab-k}(\ell(\mathcal{D}))=\frac{1}{k}\sum_{i=n-k+1}^n \ell_{[i]},
    \end{aligned}
\end{equation*}
where $1\leq k\leq n$.

\textbf{Connect with the trimmed loss}. The least trimmed square (LTS) estimator is one of the robust estimators \cite{huber2004robust}, which is proposed by \cite{rousseeuw1984least} for regression. The LTS strategy minimizes the loss of only a fraction of samples.  Following the idea of LTS, an iterative trimmed minimization approach is designed in \cite{shen2019learning}. Omit the factor $\frac{1}{k}$ in $\mathcal{L}_{ab-k}$, the authors of \cite{shen2019learning} propose the iterative LTS (ILTS), which can iteratively minimizes $\mathcal{L}_{ab-k}$ loss to obtain an optimal classifier under the consideration of a fraction of training samples are corrupted in the real-world applications. Therefore, ILTS involves alternating between selecting a subset of samples with the lowest current loss and re-fitting the model only on that subset. The authors in \cite{shen2019learning} also connect ILTS to GAN models. They consider training a GAN model when some fraction of the training samples from a lousy dataset. To solve this problem, they train the critic (discriminator) on the selected samples with small discriminator's loss, which is corresponding to learning with the bottom $k$ discriminator's losses. 

Based on ILTS, the authors in \cite{shen2019iterative} apply ILTS to solve mixed linear regression with adversarial corruptions. The Min-$k$ SGD (MKL-SGD) proposed in \cite{shah2020choosing} has a similar idea to ILTS, which also belongs to the AB$_k$ learning strategy. In each iteration during the training, the authors of \cite{shah2020choosing} first choose a set of $k$ samples and then select the sample with the smallest current loss. Then the gradient of this sample is used for the model parameters update step. In \cite{yuan2020learning}, the authors utilizes ILTS to learn entangled single-sample distribution. Their goal is to estimate some common parameter shared by a family of distributions, given one single sample from each distribution. To avoid the risk of overfitting in deep neural networks (DNNs) on noisy-labeled data, in \cite{song2020no}, the authors propose a DNN training approach with sample selection based on adaptive $k$-set selection, which selects $k$ samples with a small noise-risk from the whole noisy training samples at each training epoch. This training method can also be regarded as a type of AB$_k$ strategy. To understand why the DNNs using the small-loss criterion lean well from noisy labels, in \cite{gui2021towards}, the authors formalize the small-loss criterion to better tackle noisy labels and view this criterion from a theoretical perspective.


\textbf{Connect with fairness}. AB$_k$ is also studied in the most recent works for designing fair and robust models such as \cite{roh2021sample}. In \cite{roh2021sample}, the authors address fairness and robustness jointly. In other words, they consider learning an unbiased and robust model from corrupted data. To track this, they add a fairness constraint named demographic parity disparity into the AB$_k$ loss to formulate the final learning objective. 

\textbf{Connect with inverted CVaR}. To make a connection between AB$_k$ and CVaR, the authors in \cite{lee2020learning} propose an inverted version of CVaR. They prove that the AB$_k$ loss is equivalent to the inverted CVaR, which can be used to describe the algorithms that disregard samples with high loss. In addition, Han et al. \cite{han2018co} propose a learning framework that can handle noisy labels. They train two models simultaneously by selecting and feeding a fraction of samples with the lowest loss to each other. Their training objective can be regarded as an inverted CVaR, which is also the AB$_k$ loss.

\textbf{Connect with unsupervised learning}. AB$_k$ can also be used in designing robust unsupervised learning models. As mentioned by Hampel \cite{hampel2001robust}, outliers do not fit the pattern set by the majority of the data. The authors in \cite{maurer2021robust} suggest focusing on a sufficient portion of the data during the model training. To this end, they propose applying L-estimators \cite{serfling2009approximation}, which are formed by a weighted average of the order statistics. Given a candidate learning model, they first rank its losses on the training data and then take a weighted average emphasizing small losses more. In other words, this construction can be the average of a fraction of the smallest losses, which is exactly the AB$_k$ loss. They leverage the weighted AB$_k$ loss to design a robust $k$-Means clustering model and study the robustness of Principal Subspace Analysis.

\subsection{Average of Ranked Range (AoRR) Aggregate Loss}
As we mentioned, the average loss is insensitive to minority sub-groups, while the maximum loss is sensitive to outliers.
The AT$_K$ can dilute but not exclude the influences of the outliers. The AB$_k$ is also insensitive to minority sub-group data since they focus on more samples with lower loss values. To this end, the average of ranked range (AoRR) loss is proposed in \cite{hu2020learning}. Unlike previous aggregate losses, the AoRR loss can completely eliminate the influence of outliers if their proportion in training data is known and it is robust to the imbalanced data. The AoRR aggregate loss can be defined as:
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{aorr}(\ell(\mathcal{D}))
    = \frac{1}{k-m}\sum_{i=m+1}^k \ell_{[i]},
    \end{aligned}
\end{equation*}
where $0\leq m<k\leq n$. The AoRR loss can be generalized to the average loss ($k=n$ and $m=0$), the maximum loss ($k=1$ and $m=0$), the median loss ($k=\lceil \frac{n+1}{2} \rceil$ and $m= \lfloor \frac{n+1}{2}\rfloor-1$), the AT$_k$ loss ($m=0$), and the AB$_k$ loss ($k=n$, $m=n-k$). In addition, the robust version of the maximum loss  \cite{shalev2016minimizing}, which is a maximum loss on a subset of samples of size at least $n-(k-1)$, where the number of outliers is at most $k-1$, is equivalent to the top-$k$ loss, a special case of the AoRR aggregate loss ($m=k-1$).

\textbf{Connect with bilevel optimization}. The following work \cite{hu2021sum} studies the connection between AoRR loss and the bilevel optimization problem. The authors in \cite{hu2021sum} reformulate the AoRR loss to a cardinality constrained bilevel optimization problem. Therefore, it is possible to adapt the existing bilevel optimization algorithm from \cite{borsos2020coresets} to solve this problem.

\textbf{Connect with interval CVaR}. In \cite{hu2021sum}, Hu et al. reformulate AoRR as the difference between two sums of the top ranked values such that $\mathcal{L}_{aorr}(\ell(\mathcal{D}))
= \frac{1}{k-m}[\sum_{i=1}^k \ell_{[i]} - \sum_{i=1}^m \ell_{[i]}]$. Each sum of the top ranked value can be represented as a variant of AT$_k$ loss. As we discussed in Section \ref{sec:atk}, the AT$_k$ loss is equivalent to the formula of CVaR. Therefore, Hu et al. further reformulate AoRR loss to the difference between two CVaRs, which is named Interval Condition Value at Risks (ICVaRs). A recent work \cite{liu2022risk} further statistical studies ICVaR for robust regression and classification in nonsmooth settings. 

\textbf{Connect with difference of convex optimization}. As we mentioned, the AoRR loss can be represented as the difference of top sums of the top-ranked values, and each of them is a convex optimization problem if we consider using the convex individual loss function. Therefore, the AoRR becomes a difference of convex (DC) programming problem \cite{le2018dc}, which is first discussed in \cite{hu2020learning}. Since DC problem can be efficiently and effectively solve via DC algorithm (DCA) \cite{tao1986algorithms}, Yao et al. \cite{yao2022large} apply the AoRR loss and DCA to optimize partial AUC \cite{narasimhan2013svmpauctight}.  

\textbf{Connect with SVM}. When the $\ell$ individual loss function is a hinge loss function that works on a linear model and constrains the $l_2$ norm of the model parameters to 1, the AoRR loss becomes the extended robust SVM (ER-SVM), which is proposed in \cite{fujiwara2017dc}. The authors also proved that the ramp-loss SVM \cite{collobert2006trading} and the robust outlier detection (ROD) method \cite{xu2006robust} are special cases of ER-SVM, which means AoRR can also generalize to these two methods. A similar model, CVaR-($\alpha_L$, $\alpha_U$)-SVM, which relaxes the constraint of the $l_2$ norm of the model parameters less than 1, was proposed in \cite{tsyurmasto2013support}. Note that $\alpha_L$, $\alpha_U$ are the same as $k$, $m$, which control the range size. Without constraint, the ER-SVM will be reduced to ($\nu$, $\mu$)-SVM \cite{kanamori2017breakdown, kanamori2017robustness}, which is exactly equivalent to AoRR using hinge loss function and has been theoretically evaluated the robustness for outliers. Similarly, $\nu$ and $\mu$ have the same properties of $k$ and $m$. 

\textbf{Connect with the trimmed root mean squared
error (tRMSE)}. When $\ell$ individual loss function is a mean squared error loss, the AoRR loss becomes the tRMSE, which is used to measure the performance of the recommender system in \cite{ortis2019predicting}. 









\subsection{ Close-$k$ Aggregate Loss}\label{sec:close-k}
When the training data contains ambiguous samples that cannot be classified correctly, the AT$_k$ aggregate loss cannot make an optimal classification. The reason is that the AT$_k$ loss is still rewarded for reducing the loss of the ambiguous samples, even if these samples cannot be classified correctly. To solve this problem, He et al. in \cite{he2018minimizing} propose a close-$k$ aggregate loss, which is defined as:
\begin{equation*}
    \begin{aligned}
    &\mathcal{L}_{close-k}(\ell(\mathcal{D}))\\
    =&\sum_{i=1}^n \begin{cases}
\ell_{[n-i+1]} & \text{ if } i\leq k \\
0 & \text{ if } i>k \ \text{and} \ \ell_{[n-i+1]} \text{correctly  classified} \\
M & \text{ if } i>k \ \text{and} \ \ell_{[n-i+1]} \text{incorrectly  classified} 
\end{cases},
    \end{aligned}
\end{equation*}
where $M$ is a constant and $\ell_{[n-i+1]}$ is the individual loss $\ell_j$ with the ($n-i+1$)-th largest $|\ell_j-T|$ such that T is another constant. By applying this operation, they can select the individual loss of the ($n-i+1$)-th closest sample to the decision boundary.


























\section{Rank-based Individual Losses}\label{sec:individual_loss}
In this section, we will introduce four types of rank-based individual losses and 
show their broad application in machine learning. 


\subsection{Average Individual Losses} Similar to the aggregate loss, the average operator is the traditional aggregator that appears in the individual loss. We can represent the average individual loss as
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{avg}(\mathbb{O}(f(\mathbf{x})))= \frac{1}{C}\sum_{j\in\mathbb{N}_C}\mathcal{O}(f_j(\mathbf{x}),\mathbf{y})=\frac{1}{C}\sum_{j=1}^C\mathcal{O}(f_{[j]}(\mathbf{x}),\mathbf{y}),
    \end{aligned}
\end{equation*}
where $\mathcal{O}(f_{[j]}(\mathbf{x}),\mathbf{y})$ represents the top-$j$ value in  $\mathbb{O}(f(\mathbf{x}))$.

\textbf{Connect with multi-class classification}. 
The first all-in-one approach, which casts the learning problem into a single quadratic program that allows taking all class relationships into account simultaneously, for SVM multi-class classification is proposed in \cite{weston1999support}.
This approach can be expressed with the above framework $C\cdot\mathcal{L}_{avg}(\mathbb{O}(f(\mathbf{x})))$ as the machine relying on the sum operator applied to relative margins in $\mathbb{O}(f(\mathbf{x}))$. Inspired by \cite{weston1999support}, two independent and similar methods are proposed in \cite{bredensteiner1999multicategory} and \cite{vapnik1999nature} (Section 10.10) at the same time. Several techniques exist to build a multi-category classifier based on some binary classifiers. One of the most popular methods is called one-versus-all (OVA). It relies on $C$ different binary decision functions, each separating one class from all the rest \cite[Section 10.10]{vapnik1999nature}. Therefore, OVA sums all binary problems into one learning problem, which can be viewed as a sum aggregation that adapts the average aggregator.

In addition, Lee et al. \cite{lee2004multicategory} proposed a distinct approach to multi-class SVM. It can be called as LLW method, which uses absolute margins in an all-in-one approach. The absolute margin violations are combined by using the average aggregator. Reinforced multicategory SVM (RM-SVM) is proposed by Liu et al. \cite{liu2011reinforced}, which also uses an average aggregator to aggregate margins. However, the margins are weighted according to the ground truth class.

\textbf{Connect with multi-label classification}. The average aggregator is also widely used in multi-label classification. For example, the instance-F1 loss \cite{zhang2013review} applies the average aggregator to calculate F-measure \cite{sasaki2007truth} based on all labels, and it can be decomposable.
The Hamming loss \cite{schapire2000boostexter, zhang2013review} reduces multi-label learning to $C$ independent binary classification problems (one for each label) and ignores label dependencies that are helpful to multi-label learning. It is a typical example that uses the average aggregator.




\subsection{Maximum Individual Loss}
Many multi-class and multi-label classification problems design the individual losses based on the maximum aggregator. Following the notations that we defined before, we can represent the maximum guided individual loss as follows,
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{max}(\mathbb{O}(f(\mathbf{x})))= \max_{j\in\mathbb{N}_C}\mathcal{O}(f_j(\mathbf{x}),\mathbf{y})=\mathcal{O}(f_{[1]}(\mathbf{x}),\mathbf{y}),
    \end{aligned}
\end{equation*}
where $\mathcal{O}(f_{[1]}(\mathbf{x}),\mathbf{y})$ represents the top-$1$ value in  $\mathbb{O}(f(\mathbf{x}))$.

\textbf{Connect with multi-class classification}. In binary classification, the 0-1 loss is the standard performance measure. However, the popular surrogate losses, such as the SVM hinge loss, are applied to replace 0-1 loss because it is hard to be optimized. Inspired by this trick, the researchers naturally extend this surrogate loss to solve multi-class classification problems when the number of classes increases in the data set. For example, one of the most popular surrogate losses is the multi-class SVM, which is proposed by Grammer and Singer \cite{crammer2001algorithmic} and  $\mathcal{O}(f_j(\mathbf{x}),\mathbf{y})$ can be defined as $[1+f_j(\mathbf{x})\times \mathbb{I}_{j\neq \mathbf{y}}-f_{\mathbf{y}}(\mathbf{x})]_+$ or $[\mathbb{I}_{j\neq\mathbf{y}}+f_j(\mathbf{x})-f_{\mathbf{y}}(\mathbf{x})]$. The loss becomes large if the ground truth label $\mathbf{y}$ score is below the largest score from other class labels. Two similar losses named AMO and ATM are proposed in \cite{dogan2016unified}. Both of them are based on the maximum aggregator.

\textbf{Connect with multi-label classification}. The maximum aggregator can also be used to design loss functions in multi-label learning tasks, where each sample is associated with multiple labels reflecting its multitude of semantic relevance. One of the conventional multi-label losses  is proposed in \cite{crammer2003family} such that $\mathcal{O}(f_j(\mathbf{x}),\mathbf{y})$ is represented as $[1+f_j(\mathbf{x})\times \mathbb{I}_{j\notin \mathbf{y}}-\min_{y\in \mathbf{y}}f_y(\mathbf{x})]_+$. It is clear that the multi-label loss can be reduced to multi-class loss if $|\mathbf{y}|=1$. Similarly, the loss function can be read as the minimal prediction score from ground truth labels should be larger than the maximal score from non-ground truth labels. This loss is also known as the multiclass multilabel perceptron (MMP) \cite{furnkranz2008multilabel}, and the separation ranking loss \cite{guo2011adaptive}. One-error and Coverage losses \cite{schapire2000boostexter, zhang2013review} also belong to the maximum guided individual losses, where they penalize if the label of the top predictions does not belong to ground truth labels. 

\textbf{Connect with Adversarial Attacks}. Nowadays, DNNs have significantly improved, or in some cases, revolutionized, the state-of-the-art performance of many computer vision problems. Notwithstanding this tremendous success, the omnipotent DNN models are surprisingly vulnerable to adversarial attacks \cite{szegedy2013intriguing,goodfellow2014explaining,liu2016delving}. In particular, inputs with specially designed perturbations, commonly known as {\it adversarial examples}, can easily mislead a DNN model to make erroneous predictions. This motivates the explorations of algorithms generating adversarial examples \cite{carlini2017towards,moosavi2016deepfool,madry2017towards} as a means to analyze the vulnerabilities of DNN models and improve their security. 

Most existing adversarial attacking methods target multi-class classification problems. These methods often target the top prediction and aim to change it with perturbations. Therefore, the maximum guided individual loss is broadly designed and used. For untargeted attacks, DeepFool \cite{moosavi2016deepfool} is a generalization of the minimum attack under general decision boundaries by swapping labels from the top-$2$ prediction.  Following DeepFool, the work of \cite{moosavi2017universal} (UAP) aims to find universal adversarial perturbations independent of individual input images.  Both DeepFool and UAPs aim to make the top-1 predicted label from the perturbed sample different from the top-1 predicted label from the original sample. For targeted attacks, the CW method \cite{carlini2017towards} aims to enforce the  top-1 predicted label from the perturbed sample that is equivalent to the pre-defined label (which is different from the ground truth label) when designing the loss function.  

The authors of \cite{song2018multi} describe an adversarial targeted attack to multi-label classification, extending existing attacks to multi-class classification.  This method is further studied in \cite{zhou2020generating}, which transfers the problem of generating an attack to a linear programming problem.  To make the predictions of adversarial examples lying inside of the training data distribution, \cite{melacci2020can} propose a multi-label attack procedure with an additional domain knowledge-constrained classifier. These are all for multi-label learning. They use the maximum operator to design the individual loss that can make the targeted labels ranked before all ground truth labels.





\subsection{Top-$k$ Individual Loss} Class overlap, multi-label nature of samples, and class ambiguity problems appear when the number of classes increases in image classification. Top-$k$ error is explored and studied when a predictor allows $k$ guesses instead of one and is not penalized for $k-1$ mistakes. It is regarded as a robust evaluation measure in the current research and competition, such as the top-1 to top-5 performances are evaluated in ImageNet challenge \cite{russakovsky2015imagenet}. In such a case, top-$k$ accuracy is an important metric that estimates whether the candidates include correct targets, which limits total performance. Therefore, the top-$k$ guided individual loss is proposed and can be defined as 
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{top-k}(\mathbb{O}(f(\mathbf{x})))= \mathcal{O}(f_{[k]}(\mathbf{x}),\mathbf{y}),
    \end{aligned}
\end{equation*}
where $\mathcal{O}(f_{[k]}(\mathbf{x}),\mathbf{y})$ represents the top-$k$ value in  $\mathbb{O}(f(\mathbf{x}))$.

\textbf{Connect with multi-class classification}. The top-$k$ SVM method is first proposed by Lapin et al. in \cite{lapin2015top} for the linear model. The main motivation for top-$k$ loss is to relax the penalty for making an error in the top-$k$ predictions for multi-class classification. In this case, the function $\mathcal{O}$ is just the traditional multi-class function that we have defined before. Inspired by this method, Yan et al. \cite{yan2018top} integrate multiple feature fusion into the top-$k$ multi-class framework to improve the classification performance. To mitigate the instance ambiguity problem in the image-sentence matching scenario, Zhang et al. \cite{zhang2019deep} extend top-$k$ SVM and propose a deep multi-modal network with a top-$k$ ranking loss for large-scale image-sentence matching with indistinguishable data. Moreover, the classes in hierarchical classification are formed as a structured hierarchy. So, the misclassification costs depend on the relation
between the correct class and the incorrect class in the
hierarchy. The combination of top-$k$ classification and hierarchical classification is first proposed in \cite{oh2017top}. In \cite{oh2017top}, the authors define a top-$k$ hierarchical loss function based on top-$k$ SVM loss and then provide the Bayes-optimal solution that minimizes the expected
top-$k$ hierarchical misclassification cost. Chzhen et al. \cite{chzhen2021set} view top-$k$ SVM from set-value classification aspect. They classify it as a point-wise size control problem. Tan et al. in \cite{tan2019exact} formulate the top-$k$ multi-class classification problem as an $l_0$ norm minimization problem and consider an exact penalty method to solve it.

The practical success of the top-$k$ SVM method motivates the theoretical analysis of consistent top-$k$ classification, which is a property of top-$k$ error and its surrogate loss. The consistency of surrogate loss states that the learned classifier converges to the population optimal prediction in the infinite sample limit. However, as Yang et al. studied in \cite{yang2020consistency}, the top-$k$ SVM method does not satisfy this top-$k$ consistency property. Therefore, they proposed another top-($k+1$) loss, which satisfies the top-$k$ calibration (a necessary condition of top-$k$ consistency) and further satisfies top-$k$ consistency under mild conditions. It can be represented as $\mathcal{O}(f_{[k+1]}(\mathbf{x}),\mathbf{y})$, where $\mathcal{O}(f_j(\mathbf{x}),\mathbf{y}):=[1+f_j(\mathbf{x})-f_{\mathbf{y}}(\mathbf{x})]_+$. However, the top-$k$ calibrated loss proposed by \cite{yang2020consistency} is not a smooth loss function. Therefore, it cannot be directly used for training a deep neural network. In addition, it cannot handle imbalanced data. So it is not robust for the long-tailed dataset. To this end, following \cite{yang2020consistency}, Garcin et al. \cite{garcin2022stochastic} propose a smooth version of $\mathcal{O}(f_{[k+1]}(\mathbf{x}),\mathbf{y})$ and a new loss for imbalanced top-$k$ classification. Specifically, they proposed to smooth the top-$k$ calibrated loss $\mathcal{O}(f_{[k+1]}(\mathbf{x}),\mathbf{y})$ with the perturbed optimizers method developed by \cite{berthet2020learning}. In other words, they add Gaussian noise into the logits predicted by neural networks. To handle imbalanced data, they follow \cite{cao2019learning} and replace the margin parameter 1 from the formulation $\mathcal{O}(f_j(\mathbf{x}),\mathbf{y})$ with another margin parameter which is determined by the number of samples in training set with ground truth class. 


\textbf{Connect with multi-label classification}. Inspired by \cite{yang2020consistency}, Hu et al. \cite{hu2020learning} extend the top-$k$ calibrated multi-class loss to multi-label learning. The motivation is that the classifier is expected to include as many true labels as possible in the top $k$ outputs during the training. They design a top-$k$ multi-label (TKML) loss, which can also be represented as $\mathcal{O}(f_{[k+1]}(\mathbf{x}),\mathbf{y})$ but $\mathcal{O}(f_j(\mathbf{x}),\mathbf{y}):=[1+f_j(\mathbf{x})-\min_{y\in\mathbf{y}}f_y(\mathbf{x})]_+$, where $|\mathbf{y}|\geq 2$. It is clear that the TKML loss can generalize the conventional multi-class loss ($|\mathbf{y}|=k=1$) and the top-$k$ calibrated $k$-guesses multi-class classification \cite{yang2020consistency} ($1=|\mathbf{y}|\leq k < C$). \cite{li2017improving} leverages the top-$k$ in label decision to improve pairwise ranking for multi-label image classification. In \cite{hu2021sum}, the authors proposed a TKML-AoRR loss, which combines the AoRR and the TKML methods. It can improve the robustness of top-$k$ multi-label learning in the face of outliers in sample and labels alike.

\textbf{Connect with Adversarial Attacks}. Realizing that only attacking the top predictions may not be effective, several works introduce attacks to the top-$k$ (for $k > 1$) predictions in a multi-class classification system. 
$k$Fool \cite{tursynbek2022geometry} and CW$^k$ \cite{zhang2020learning} extend the original DeepFool \cite{moosavi2016deepfool} and CW \cite{carlini2017towards} methods to exclude the truth label out of the top-$k$ predictions. Specifically, $k$Fool is based on a geometry view of the decision boundary between $k$ labels and the truth label in the multi-class problem. The UAP method is extended in \cite{tursynbek2022geometry} to top-$k$ Universal Adversarial Perturbations ($k$UAPs). In addition, the CW method is extended to a top-$k$ version known as CW$^k$ in \cite{zhang2020learning}. For multi-label learning, Hu et al., \cite{hu2021tkml} propose an untargeted adversarial attack (TKML-AP-U) loss for TKML learning. TKML-AP-U attack aims to only replace the top-$k$ labels with a set of arbitrary $k$ labels that are not true classes of the untampered input. Furthermore, they propose TKML-AP-Uv loss, which extends TKML-AP-U to a universal adversarial attack independent of input \cite{moosavi2017universal} so it can be shared by all instances. 

\subsection{Average Top-$k$ (AT$_k$) Individual Loss}
One potential reason to introduce the average top-$k$ aggregator for individual loss is that the top-$k$ aggregator is nonconvex. Therefore, finding a globally optimal solution is computationally intractable. As we discussed in Section \ref{sec:prop_agg}, the average top-$k$ is a convex upper bound of top-$k$. So the average top-$k$ aggregator is widely used to replace the top-$k$ aggregator in the learning tasks. The average top-$k$ guided individual loss can be defined as follows,
\begin{equation*}
    \begin{aligned}
    \mathcal{L}_{at-k}(\mathbb{O}(f(\mathbf{x})))=\frac{1}{k}\sum_{j=1}^k \mathcal{O}(f_{[j]}(\mathbf{x}),\mathbf{y}).
    \end{aligned}
\end{equation*}


\textbf{Connect with multi-class classification}. According to the above motivation, Lapin et al. \cite{lapin2015top} propose two top-$k$ SVM losses named top-$k$ SVM$^\alpha$ and top-$k$ SVM$^\beta$ to relax the original top-$k$ SVM method for optimization inspired by ranking losses in \cite{usunier2009ranking}. Both of them adapt the AT$_k$ aggregator to replace the Top-$k$ aggregator in the original top-$k$ SVM. In addition, they apply a stochastic dual coordinate ascent algorithm to optimize the proposed losses. However, this algorithm relies on the scoring method, which yields a high time complexity. Therefore, the following work \cite{chu2018optimizing} leverages the semismoothness of the problem and proposes to use the semismooth newton algorithm for solving top-$k$ SVM$^\alpha$ and improve the training speed. 
Due to the above two losses being non-smooth, in their following works \cite{lapin2016loss, lapin2017analysis}, they propose different smooth versions of both losses based on Moreau-Yosida regularization \cite{nesterov2005smooth}. They conduct the experiments on linear models or pre-trained deep networks that are fine-tuned. However, the proposed losses cannot be directly used for training deep neural networks from a random initialization because of the non-smoothness of the top-$k$ SVM loss part and the sparsity of its gradient. Therefore, the following work \cite{berrada2018smooth} introduces another smooth version of top-$k$ SVM$^\alpha$ with a temperature parameter for deep top-$k$ classification. The main principle of the proposed loss is based on rewriting the top-$k$ SVM loss \cite{lapin2015top} as a difference of two max with logsumexp and using a divide-and-conquer approach to make the loss tractable. They mentioned the importance of smoothness and gradient density of loss in applying it to DL for successful optimization.
The work of \cite{rawat2020doubly} propose a doubly-stochastic mining method, which combines the methods of ordered SGD from \cite{kawaguchi2020ordered} and top-$k$ SVM$^\beta$ from \cite{lapin2015top}. They use the average top-$k$ methods both in the data sample level and label level to construct the final loss function. Then the constructed loss is applied to solve modern retrieval problems, which are characterized by training sets with a vast number of labels and heterogeneous data distributions across sub-populations.


Another work in \cite{chang2017robust} proposes a robust top-$k$ SVM based on the top-$k$ SVM$^\alpha$ to address the outliers by using a hyperparameter to cap the values of the individual losses for visual category recognition.
Gong et al. \cite{gong2021top} extend top-$k$ SVM$^\alpha$ to deal with ambiguities in partial label learning (PLL) that aims to train a classifier from partially labeled data in order to automatically predict the ground truth label for an unseen instance. The proposed top-$k$ partial loss and convex top-$k$ partial hinge loss work well on partial label classification. 
Zhang et al. \cite{zhang2019deep} apply the top-$k$ SVM$^\alpha$ method to solve the image-sentence matching problem. Zhu et al. \cite{zhu2021unified} propose another top-$k$ calibrated loss named label-distributionally robust (LDR)-$k$ loss, which converts the top-$k$ SVM$^\beta$ method to a distributionally robust optimization problem and introduces a strongly convex regularizer. 
The above losses can be regarded as the unweighted average top-$k$ SVM. In addition, two weighted top-$k$ SVMs based on top-$k$ SVM$^\alpha$ and top-$k$ SVM$^\beta$ are proposed in \cite{kato2019learning, tajima2021frank}.  However, all of these losses cannot scale to extremely large output spaces because computing the value of them are required computing scores of all labels. To extend these losses to a large output space, the ordered weighted losses (OWLs) are proposed by Reddi et al. in \cite{reddi2019stochastic}. They also provide a stochastic negative mining approach to optimize the OWLs, which randomly sample a few classes other than the given positive class and treat them as negative classes with some additional correction while computing the loss based on the negative sampling approach from \cite{mikolov2013distributed}. 

Meantime, Lapin et al. \cite{lapin2016loss, lapin2017analysis} find the softmax loss only aims at top-1 performance and produces a reasonably good solution in top-1 error but ignores the top-2 error. Thus, they adapt the softmax loss to top-$k$ error optimization for multi-class classification. Then they propose two new average top-$k$ losses named top-$k$ entropy loss and truncated top-$k$ entropy loss for multi-class classification based on the softmax loss. They show that cross-entropy (CE) loss is top-$k$ calibrated for any $k$, which means the minimizers of CE will minimize the top-$k$ error for all $k$ under ideal conditions. This may be why CE loss succeeds in the top-$k$ performance of models in deep learning with large datasets.  The proposed losses are applied to the application of App usage prediction in \cite{zhao2019appusage2vec}. In particular, the authors in \cite{zhao2019appusage2vec} adjust the entropy loss by introducing hinge loss on top $k$. Such losses are also applied to solve egocentric action anticipation problems in \cite{furnari2018leveraging}. Later, Sawada et al. \cite{sawada2020trade} analyze that CE loss penalizes top-$k$ correct predictions similarly to incorrect predictions when it is incorrect in top-1 predictions. This leads to a sacrifice in top-$k$ correct prediction on samples challenging to predict correctly in top-1 prediction, instead of achieving top-1 correct prediction on other samples, to minimize the average of losses over all training samples. Therefore, CE is potentially not the best choice to obtain the best top-$k$ accuracy of all
possible predictions within practical limitations. Thus, they propose top-$k$ grouping loss, which contains two parts. The first part groups top-$k$ classes as a single class and apply CE loss to it. The second part is the traditional CE loss on the remaining classes. To keep a stable training performance, they define a top-$k$ transition loss that uses CE loss at the beginning of training and gradually transitions from CE loss to top-$k$ grouping loss.



\textbf{Connect with multi-label classification}. Groupwise ranking loss (GRLS) \cite{fan2020groupwise} is proposed for multi-label learning that implements the top-$k$ label principle. The GRLS loss is defined as the difference between the average predicted relevancy score of predicted positive labels ({\em i.e.}, labels with top-$k$ largest prediction scores) and the average predicted relevancy score of ground truth positive labels. Therefore, we can set $k=|\mathbf{y}|$ and $\mathcal{O}(f_{j}(\mathbf{x}),\mathbf{y}) := f_{j}(\mathbf{x})-\frac{1}{|\mathbf{y}|}\sum_{y\in\mathbf{y}}f_y(\mathbf{x})$ to construct the GRLS loss based on $\mathcal{L}_{at-k}(\mathbb{O}(f(\mathbf{x})))$. This loss is straightforward to understand. It tries to push the ground truth labels to the top list according to the value of the prediction score. Following the smooth top-$k$ entropy loss and truncated top-$k$ entropy loss from \cite{lapin2016loss}, Amos et al. \cite{amos2019limited} propose the limited multi-label (LML) projection layer as a primitive operation for end-to-end learning systems. The LML layer provides a probabilistic way of modeling multi-label predictions limited to having exactly $k$ labels. 

\textbf{Connect with Adversarial Attacks}. Since the loss with top-$k$ operator is hard to be optimized, the authors in $k$Fool \cite{tursynbek2022geometry} and CW$^k$ \cite{zhang2020learning} use sum of top-$k$ (a variant of AT$_k$ operator) to replace the top-$k$ operator. Hu et al., in \cite{hu2021tkml} propose a TKML-AP-T attack loss based on the sum of top-$k$, which aims to coerce the TKML classifier to use a specific set of $k$ labels that are not true classes of the input as the top-$k$ predictions. The idea of TKML-AP-T is also extended and further studied by Qaraei et al., in \cite{qaraei2021adversarial} for adversarial targeted attacks for extreme multilabel text classification with application in recommendation systems and automatic tagging of web-scale documents.
Hu et al. \cite{hu2021tkml} also replace the top-$k$ operator in the original TKML-AP-U and TKML-AP-Uv attacks with the average top-$k$ operator because they realized the average of top-$k$ is a tight upper-bound of the top-$k$ and the average of top-$k$ can be reformulated as a minimization problem, which is very easy to be optimized.  











































                  
    
                  
                  
                  


                  
                  



\section{Connections with Other Topics}\label{sec:other_topics}
In this section, we will discuss the connection between rank-based losses with several related topics (data subset selection, hard example mining, DRO, and CVaR) 
in machine learning. These connections demonstrate the applicability and popularity of rank-based losses. Furthermore, these connections provide potential techniques to optimize and design algorithms for learning rank-based losses. On the other hand, from these connections, the rank-based losses can enhance the diversity and research scope of existing machine learning topics. 

\begin{itemize}
    \item \textbf{Data subset selection} \cite{wei2015submodularity}. One related topic in the existing machine learning literature is the data subset selection problem, which is about selecting a subset from a large training dataset to train a model while incurring a minimal average loss.  For example, curriculum learning \cite{bengio2009curriculum}, and self-paced learning \cite{kumar2010self, jiang2015self} are two learning schemes that organize the training process into several iterative passes to include training data gradually from those that are easy to those that are hard to learn, where the level of difficulty is measured with the individual losses. As such, each pass of training in these methods corresponds to an average aggregate loss over the selected subset. Coreset\cite{borsos2020coresets, yoon2021online} is another method of data subset selection. The coreset is constructed by a small data subset that extracts from the original dataset and can approximate it. Solving the problem on the coreset usually yields similar results as solving the same problem on the original dataset. It is regarded as an efficient method to handle massive datasets and streams, especially for online learning. All of these methods are related to the above-discussed aggregate losses. For example, if we select a subset of samples with the largest individual losses, then they are related to average top-$k$ aggregate loss. 
    
    \item \textbf{Hard example mining}. Currently, training deep neural networks usually applies the hard example mining approach \cite{gidaris2015object, liu2016ssd, shrivastava2016training, lin2017focal}, which is an effective method that bears a resemblance to the rank-based aggregate losses. For instance, \cite{shrivastava2016training} propose online hard example mining that updates model parameters by using the top-$k$ samples ({\em i.e.}, object proposal regions of interest) with the largest losses for each training image in object detection. The work \cite{lin2017focal} propose a weighted cross-entropy loss that assigns more weights to candidate bounding boxes with large losses and vice-versa, and demonstrated that it is more suitable for object detection than the classical cross-entropy loss. However, it should be noted that the connections of these works to the aggregate loss are incidental.
    
    \item \textbf{Distributionally robust optimization (DRO)}. DRO \cite{namkoong2017variance, rahimian2019distributionally, chen2020distributionally} is one of the most popular methods in robust learning. It regards the data uncertainty from the probabilistic aspect, and the main goal is to make the trained model from the observed data work well on the unseen data. During the training, it minimizes the worst-case weighted expected loss function on all training data, where the weight follows a constructed probabilistic ambiguity set around the actual training data distribution. In fact, the aggregate loss has a strong connection with DRO as discussed in Section \ref{sec:atk}, {\em e.g.}, the average top-$k$ aggregate loss can be reformulated as a DRO problem. On the other hand, the DRO has severe instability during the training and results in bad performance when working on a training dataset that includes outliers. To solve this problem,  \cite{zhai2021doro} proposes a robust outlier refinement of DRO named DORO. It adaptive removes a small fraction of examples with the largest individual losses in training. This new learning function is similar to AB$_k$ aggregate loss and AoRR aggregate loss. 
    
    \item \textbf{Condition Value at Risk (CVaR)}. It is worthy of connecting rank-based losses to CVaR. CVaR \cite[Chapter~6]{ shapiro2021lectures} is one of the most popular statistics used in risk-sensitive machine learning. It has many applications in operations research and machine learning communities and is originally introduced in economics research as a tool for quantifying the risk associated with a portfolio \cite{rockafellar2000optimization}. In machine learning, we face many learning tasks requiring models with a good tail performance. Specifically, the model has a high performance on the worst-off examples in the dataset. CVaR loss works well in such scenarios, which computes the average risk over the tails of the loss. This has the same property with AT$_k$ aggregate loss. Both of them focus on the largest individual losses. Therefore, \cite{fan2017learning} is the first work to connect these two topics based on \cite{ogryczak2003minimizing}. After that, \cite{hu2021sum} extends this connection to AoRR aggregate loss. 
   
    
   
\end{itemize}





\section{Future Directions}\label{sec:future_directions}
In this section, we suggest six directions that can be explored in the future.

\begin{table*}[t]
\centering
\scalebox{0.94}{
\begin{tabular}{|c|c|c|}
\hline
Aggregators & Aggregate Losses & Individual Losses \\ \hline\hline
Average & \makecell[l]{
$\cdot$\textbf{Empirical Risk Minimization (ERM)} \cite{vapnik1999nature}, \cite{bartlett2006convexity, de2005model, steinwart2003optimal, wu2006learning}
\\ $\cdot$\textbf{Maximum (Log)-Likelihood} \cite{friedman2001elements}
}  
& \makecell[l]{$\cdot$\textbf{Multi-class Classification} \\ \ \ --\textit{All-in-One} \cite{weston1999support, bredensteiner1999multicategory, vapnik1999nature}; \textit{One-versus-All} \cite{vapnik1999nature}; \textit{LLW} \cite{lee2004multicategory}; \\ \ \ \ \textit{RM-SVM}\cite{liu2011reinforced} \\ $\cdot$\textbf{Multi-Label Classification} \\ \ \ --\textit{Instance-F1 Loss} \cite{zhang2013review}; \textit{Hamming Loss}\cite{schapire2000boostexter, zhang2013review}}\\ \hline

Maximum & \makecell[l]{$\cdot$\textbf{Support Vector Machine (SVM)} \cite{clarkson2012sublinear, hazan2011beating}
\\$\cdot$\textbf{Robust Learning}  \cite{shalev2016minimizing, ben2002robust, namkoong2016stochastic}
\\$\cdot$\textbf{Minimax Learning} \cite{lan2020first, chen2017robust, carmon2021thinking}
\\$\cdot$\textbf{Federated Learning}  \cite{mohri2019agnostic}} & \makecell[l]{$\cdot$\textbf{Multi-class Classification} \\ \ \ --\textit{Multi-class SVM (Grammer and Singer)}\cite{crammer2001algorithmic}; \textit{AMO}\cite{dogan2016unified}; \textit{ATM}\cite{dogan2016unified} \\ $\cdot$\textbf{Multi-Label Classification} \\ \ \ --\textit{Conventional Multi-label Loss (Grammer and Singer)} \cite{crammer2003family}; \textit{MMP} \cite{furnkranz2008multilabel}; \\ \ \ \ \textit{Separation Ranking Loss} \cite{guo2011adaptive};\\ \ \ \ \textit{One-error Loss and Coverage Loss} \cite{schapire2000boostexter, zhang2013review}
 \\ $\cdot$\textbf{Adversarial Attacks} \\ \ \ --\textit{DeepFool} \cite{moosavi2016deepfool}; \textit{UAP} \cite{moosavi2017universal}; \textit{CW} \cite{carlini2017towards}; \\ \ \ \  \textit{Multi-label Adversarial Perturbation} \cite{song2018multi, zhou2020generating, melacci2020can}
} \\ \hline

Median & \makecell[l]{$\cdot$\textbf{Least Median Squares (LMS)} \cite{shibzukhov2021principle, shibzukhov2022minimizing, rousseeuw1984least, rousseeuw1984robust, ma2011robust}
\\$\cdot$\textbf{Median-of-Means (MOM)} \cite{nemirovskij1983problem} \\ \ \ --\textit{Robust Regression} \cite{brownlees2015empirical, hsu2016loss, jalal2020robust, lecue2020robust, lugosi2019risk}; \textit{Imitation Learning} \cite{liu2022robust}}  & -- \\ \hline

Top-$k$ & -- & \makecell[l]{$\cdot$\textbf{Multi-class Classification} \\ \ \ --\textit{Top-$k$ SVM} \cite{lapin2015top, yan2018top, zhang2019deep, oh2017top, chzhen2021set, tan2019exact}; \textit{Top-$k$ Calibrated Loss} \cite{yang2020consistency}; \\ \ \ \  \textit{Smoothed Top-$k$ Calibrated Loss} \cite{garcin2022stochastic}
 \\ $\cdot$\textbf{Multi-Label Classification} \cite{li2017improving} \\ \ \ --\textit{TKML} \cite{hu2020learning}; \textit{TKML-AoRR}\cite{hu2021sum}
 \\ $\cdot$\textbf{Adversarial Attacks} \\ \ \ --\textit{$k$Fool}\cite{tursynbek2022geometry}; \textit{CW$^k$}\cite{zhang2020learning}; \textit{$k$UAPs} \cite{tursynbek2022geometry}; \\ \ \ \  \textit{TKML-AP-U}\cite{hu2021tkml}; \textit{TKML-AP-Uv}\cite{hu2021tkml}
} \\ \hline

AT$_k$ & \makecell[l]{$\cdot$\textbf{Conditional Value at Risk (CVaR)} \cite{fan2017learning}, \cite{williamson2019fairness, curi2020adaptive, lee2020learning, laguel2021superquantiles, holland2021spectral, laguel2022superquantile} \\ \ \ --\textit{Fairness} \cite{williamson2019fairness}; \textit{Adversarial Training} \cite{robey2022probabilistically} \\$\cdot$\textbf{SVM} \\ \ \ --\textit{C-SVM} \cite{cortes1995support}; \textit{$\nu$-SVM} \cite{scholkopf2000new}; \textit{E$\nu$-SVM}\cite{perez2003extension, takeda2008nu} \\ $\cdot$\textbf{Distributionally Robust Optimization (DRO)}\cite{lyu2020average, levy2020large, roux2021efficient} \\ \ \ --\textit{Active Learning}\cite{zhu2019robust}; \textit{DRO-TopK}\cite{qi2020simple}; \\ \ \ \ \textit{Multiple Instance Learning}\cite{sapkota2021distributionally} \\ $\cdot$\textbf{Learning Strategies} \\ \ \ --\textit{Ordered SGD}\cite{kawaguchi2020ordered}; \textit{Large Current Loss Minimization}\cite{wu2020curricula}; \\ \ \ \ \textit{Tilted ERM}\cite{li2020tilted, li2021tilted}; \textit{AT$_k$-GSAM}\cite{yuan2020group} \\ $\cdot$\textbf{Deep Learning Applications} \\ \ \ --\textit{Optic Disc and Optic Cup Segmentation}\cite{xu2019mixed}; \\ \ \ \ \textit{Sonar Image Generation}\cite{lee2018deep,lee2019deep};\\ \ \ \  \textit{Head Pose Estimation}\cite{huang2020improving}; \textit{6D Pose Estimation}\cite{jeon2020prima6d}; \\ \ \ \ \textit{ChIP-seq Identification}\cite{oh2020cnn}; \textit{Multi-task  Learning}\cite{wang2021simultaneous};  \\ \ \ \ \textit{Top-k Generative Adversarial Network (GAN)}\cite{sinha2020top}}
 & \makecell[l]{$\cdot$\textbf{Multi-class Classification} \\ \ \ --\textit{(Smoothed) Top-$k$ SVM$^{\alpha}$}\cite{lapin2015top, chu2018optimizing, lapin2016loss, lapin2017analysis, berrada2018smooth, zhang2019deep}; \\ \ \ \  \textit{(Smoothed) Top-$k$ SVM$^{\beta}$}\cite{lapin2015top, lapin2016loss, lapin2017analysis, rawat2020doubly}; \textit{Robust Top-$k$ SVM} \cite{chang2017robust}; \\ \ \ \ \textit{Convex Top-$k$ Partial Loss} \cite{gong2021top}; \textit{(LDR)-$k$} \cite{zhu2021unified};\\ \ \ \  \textit{Weighted Top-$k$ SVM$^{\alpha}$ and Weighted Top-$k$ SVM$^{\beta}$ }\cite{kato2019learning, tajima2021frank}; \\ \ \ \   \textit{OWLs}\cite{reddi2019stochastic};  \textit{(Truncated) Top-$k$ Entropy Loss} \cite{lapin2016loss, lapin2017analysis, zhao2019appusage2vec, furnari2018leveraging}; \\ \ \ \ \textit{Top-$k$ Grouping Loss}\cite{sawada2020trade}
 \\ $\cdot$\textbf{Multi-Label Classification}\cite{amos2019limited} \\ \ \ --\textit{GRLS} \cite{fan2020groupwise}
 \\ $\cdot$\textbf{Adversarial Attacks} \cite{qaraei2021adversarial} \\ \ \ --\textit{$k$Fool} \cite{tursynbek2022geometry}; \textit{CW$^k$}\cite{zhang2020learning}; \\ \ \ \ \textit{TKML-AP-T} \cite{hu2021tkml}; \textit{TKML-AP-U} \cite{hu2021tkml}; \textit{TKML-AP-Uv} \cite{hu2021tkml}
}  \\ \hline
 
AB$_k$ & \makecell[l]{$\cdot$\textbf{Trimmed Loss} \cite{yuan2020learning, song2020no, gui2021towards}\\ \ \ --\textit{Least Trimmed Square (LTS)} \cite{rousseeuw1984least}; \textit{Iterative LTS} \cite{shen2019learning}; \\ \ \ \ \textit{GAN} \cite{shen2019learning}; \textit{Mixed Linear Regression} \cite{shen2019iterative}; \textit{MKL-SGD} \cite{shah2020choosing} \\ $\cdot$\textbf{Fairness} \cite{roh2021sample}
 \\ $\cdot$\textbf{Inverted CVaR} \cite{lee2020learning, han2018co} \\ $\cdot$\textbf{Robust Unsupervised 
Learning} \cite{maurer2021robust}} & -- \\ \hline

AoRR & \makecell[l]{$\cdot$\textbf{Bilevel Optimization} \cite{hu2021sum} \\ $\cdot$\textbf{Interval CVaR} \cite{hu2021sum, liu2022risk} \\$\cdot$\textbf{Difference of Convex Optimization} \cite{hu2020learning, yao2022large} \\$\cdot$\textbf{SVM} \\ \ \ --\textit{ER-SVM} \cite{fujiwara2017dc}; \textit{Ramp-loss 
SVM} \cite{collobert2006trading}; \\ \ \ \ \textit{Robust Outlier Detection (ROD)} \cite{xu2006robust}; \\ \ \ \ \textit{CVaR-($\alpha_L$, $\alpha_U$)-SVM} \cite{tsyurmasto2013support}; \textit{($\nu$, $\mu$)-SVM} \cite{kanamori2017breakdown, kanamori2017robustness}  \\$\cdot$\textbf{Trimmed Root Mean Square Error (tRMSE)}\cite{ortis2019predicting} } & -- \\ \hline
 
Close-$k$ & \makecell[l]{$\cdot$\textbf{Robust Learning} \cite{he2018minimizing}}  & -- \\ \hline
\end{tabular}
}
\caption{\em An overview of related references on rank-based decomposable aggregate losses and rank-based decomposable individual losses. The empty block means the current aggregator in the corresponding aggregate losses/individual losses field has not been explored. The major topics are shown in bold. The sub-topics (in the Aggregate Losses column) and the existing losses (in the Individual Losses column) are shown in italic.
}
\label{table:summary}
\vspace{-0.5cm}
\end{table*}










\subsection{New Aggregators and Nested Aggregators}
We summarize previously discussed works in types of aggregate loss and individual loss with different aggregators in Table \ref{table:summary}. From Table \ref{table:summary}, we can find that no existing works are using the top-$k$ aggregator for designing aggregate losses. In addition, four aggregators are not investigated in individual losses, including Median, AB$_k$, AoRR, and Close-$k$. Different aggregators have unique advantages and may be suitable in specific scenarios and tasks when designing loss functions.  
Therefore, studying these missing aggregators in aggregate and individual losses is meaningful.

On the other hand, from Fig. \ref{fig:aggregators}, we can find the relationships between all aggregators. The AoRR aggregator is supremacy and can generalize to most aggregators.  However, this hierarchical relationship also prompts us to further explore the development of new aggregators. We believe it is possible to design a new aggregator that is more general than AoRR. Digging into the ranking relationships between individual values can be a good way to develop more aggregators.

Furthermore, the rank-based aggregate loss and the rank-based individual loss are not independent.  Two existing works \cite{rawat2020doubly, hu2021sum} have explored their new combination. Specifically, \cite{rawat2020doubly} uses AT$_k$ aggregator on both aggregate and individual loss levels. \cite{hu2021sum} applies AoRR aggregator for aggregate loss level and Top-$k$ aggregator for individual loss level. Inspired by these two works and excluding these two existing methods,  we can imagine at least $7\times 4-2 = 26$ possible combination methods can be tried, where 7 and 4 are the number of aggregators that have existed in aggregate loss and individual loss, respectively. In addition, the combination should not be only restricted between the aggregate loss level and the individual loss level. It may exist only on one side.  For example, in meta-learning\cite{finn2017model}, the goal of a learning task is to learn a new task efficiently by meta-training a meta-model (called meta-learner) from a set of historical tasks (called base-learner when working on each historical task). In this case, the aggregator can be applied to learn both the meta-learner and the base-learner.
In general, such combined aggregators can be termed nested aggregators, an exciting topic that can be explored more.





\subsection{Geometric Interpretation of Rank-based Losses}
\begin{figure}[t]
\vspace{-\intextsep}
\centering
\includegraphics[trim=1 1 1 1, clip,keepaspectratio, width=0.45\textwidth]{figs/geometry.JPG}
\caption{\it 3D (top) and 2D (bottom) interpretation of three aggregators. \textbf{Left}: average aggregator. \textbf{Middle}: AT$_k$ aggregator.  \textbf{Right}: maximum aggregator.}
\vspace{-0.5cm}
\label{fig:interpretation}
\end{figure}
To better understand the rank-based decomposable aggregate and individual losses, it is necessary to view them from a geometry perspective. However, they are not extensively studied from this direction in the current literature. 
In \cite{blondel2020learning}, Blondel et al. view ranking as a structured prediction problem. In addition, Lapin et al. \cite{lapin2015top} regard the AT$_k$ simplex as a convex polytope in multi-class SVM for individual loss. Similarly, Kong et al. \cite{kong2020rankmax} view the softmax function from the projection on the ($n$, $k$)-simplex. Furthermore, Lyu et al. \cite{lyu2020average} discuss the interpretation of AT$_k$ aggregate loss based on its connection with DRO. All of them regard the aggregators ({\em i.e.}, average, maximum, and AT$_k$) as a constrained learning problem, which can be defined as 
\begin{equation*}
    \begin{aligned}
    &\mathcal{L}(\ell(\mathcal{D})):= \max_{\mathbf{w}}\sum_{i=1}^n \mathbf{w}_i\ell_i \ \text{or} \  \mathcal{L}(\mathbb{O}(f(\mathbf{x})))=\max_{\mathbf{w}}\sum_{i=1}^n \mathbf{w}_i \mathcal{O}_i,\\
    &\mbox{s.t.} \ \mathbf{w}^\top \mathbf{1}= 1, \mathbf{w}\geq 0, \ \|\mathbf{w}\|_{\infty}\leq \epsilon, \mbox{with} \ \epsilon\in \left[1/n, 1\right]. 
    \end{aligned}
\end{equation*}
where $\mathcal{O}_i =\mathcal{O}(f_{i}(\mathbf{x}),\mathbf{y}_i)$.

From the above constraints, we know $\mathbf{w}$ belongs to a n-dimensional probability simplex $\Delta_n$ such that $\Delta_n:=\{\mathbf{w}\in \mathbb{R}_+^n: \mathbf{w}^\top \mathbf{1}= 1\}$. On the other hand, $\mathbf{w}$ within an $l_\infty$-ball centered at $\frac{1}{n}\mathbf{1}$ with radius $\epsilon>0$. Suppose $n=3$, we provide several examples below:
\begin{itemize}
    \item If $\epsilon=1/3$, the learning objective will generalize to the average loss, which is shown in Fig. \ref{fig:interpretation} (left).
    \item If $\epsilon=1/2$, the learning objective becomes the average top-2 loss. Fig. \ref{fig:interpretation} (middle) shows its geometry interpretation. Note that such constraints sometimes referred to as the capped probability simplex \cite{warmuth2008randomized, lim2016efficient} as mentioned in \cite{blondel2020learning}.
    \item If $\epsilon=1$, the learning objective will be reduced to the maximum loss. See Fig. \ref{fig:interpretation} (right) for more details.
\end{itemize}
As we have seen, geometric interpretation is one of the best ways to understand rank-based losses and aggregators. However, it is unclear what their geometric interpretation is for other aggregators such as AB$_k$, AoRR, and close-$k$. This is an open question.

\subsection{Converting Non-decomposable Aggregate Losses to Decomposable Aggregate Losses}

Many applications in sensitive domains such as medicine and biometrics require to use \textit{non-decomposable} loss functions \cite{ranjbar2012optimizing, narasimhan2014statistical,eban2017scalable, kumar2021implicit, narasimhan2021training}. In particular, the rank-based non-decomposable aggregate losses fall into the Learning to Rank area for Information Retrieval (IR) in general, and image retrieval in particular \cite{hu2008multiple}, 
see \cite{liu2009learning, li2011short} for more discussions about learning to rank for IR. One of the advantages of these losses is the ability to learn the data with label imbalance.
To make the learned models have better performance on specific evaluation measures (metrics), some existing works direct optimize them. However, most evaluation metrics are partially or not decomposed across samples. This will make the optimization more difficult and suffer from computational scalability issues. Converting rank-based non-decomposable aggregate loss to rank-based decomposable aggregate loss is a good way to achieve the same learning goal but is more efficient and effective in optimization procedures. 

For example, Eban et al. \cite{eban2017scalable} give convex relaxations for information retrieval metrics with decomposable objectives, leading to training that scales to large datasets. Boyd et al. in \cite{boyd2012accuracy} propose a new notion of classification accuracy named accuracy at the top (AATP), which indicates the accuracy based on the top $\tau$-quantile values of a scoring function such that $\tau\in[0,1]$. AATP loss is also proposed to push the examples whose scores are among the top $\tau$-quantile are as relevant as possible in an ordering of all examples, which can be defined as, $\mathcal{L} (f, \mathcal{D}) := \frac{1}{|\mathcal{D}|}\left[\sum_{i\in \mathcal{D}^+}\mathbb{I}_{f(x_i^+)< q_f}+\sum_{j\in \mathcal{D}^-}\mathbb{I}_{f(x_i^-)> q_f}\right],$
where $q_f$ is the top $\tau$-quantile of the values taken by $f$, $|\mathcal{D}|$ is the total number of examples, and $\mathcal{D}^+$ and $\mathcal{D}^-$ represent the positive and negative example set, respectively. The area under receiver operating characteristics curves (AUC) is a useful quantitative metric for assessing binary classification performance. However, it cannot directly be used as a learning objective due to the discontinuous indicator function and pairwise comparison between all positive and negative examples in training data. Lyu et al. \cite{lyu2018univariate} propose a surrogate loss to AUC, which uses the sum of the top-$|\mathcal{P}|$ prediction scores in the prediction score list to subtract the sum of the prediction scores of all the positive examples, where $|\mathcal{P}|$ is the total number of all the positive examples. 

All of these methods can only handle some simple metrics. However, there are many complicate metrics that are not been well studied and explored to connect with non-decomposable aggregate losses. For example, the average precision (AP) \cite{baeza1999modern}, discounted cumulative gain (DCG) \cite{jarvelin2017ir, jarvelin2002cumulated}, partial AUC \cite{narasimhan2013svmpauctight, narasimhan2013structural, narasimhan2017support}, pAp@$k$ \cite{hiranandani2020optimization}, Mean reciprocal rank (MRR) \cite{craswell2009mean}, ERR-IA \cite{chapelle2009expected}, rank aggregation \cite{dwork2001rank}, etc. 


\subsection{Statistical Machine Learning Theory on Rank-based Losses}
When designing a loss, we need to analyze its statistical machine learning properties. Furthermore, we should design an efficient and effective algorithm to optimize it. Therefore, the classification calibration and consistency, generalization capability, and optimization error or convergence guarantee are significant factors to justify the applicability of the designed loss function. In the following, we will discuss each of them.
\begin{itemize}
    \item \textbf{Classification Calibration and Consistency}. A fundamental question in learning theory for classification is to investigate when the best possible estimator from a learning objective is consistent with the best possible, \textit{i.e.}, the Bayes rule.
    Thus, to design a robust model, we need to design a surrogate loss first because optimizing the 0/1 loss is an NP-hard problem for most hypothesis sets. The 0/1 loss can represent the optimal Bayes error of the model. A significant learning property of the surrogate loss is its consistency, which requires the optimal minimizers of the surrogate loss to be near to or exact to the optimal minimizers of the 0/1 loss \cite{awasthi2021calibration}. The consistency property has been extensively extended, explored, and studied in binary \cite{zhang2004statistical, bartlett2006convexity}, multi-class \cite{tewari2007consistency}, and multi-label classification \cite{gao2011consistency}. A more convenient notion in the study of consistency is classification calibration, which is a sufficient condition for consistency. We usually say a surrogate loss function is calibrated if a model's predicted probabilities match the empirical frequencies. A well-calibrated model is useful to avoid making the wrong decision when the outcome is too uncertain \cite[Chapter~13.2.2]{ murphy2023probabilistic}.
    
    The consistency and calibration properties of the average aggregate loss have been studied in \cite{zhang2004statistical, bartlett2006convexity}. Then Fan et al. \cite{fan2017learning} and Lyu et al. \cite{lyu2020average} expand these results to AT$_k$ aggregate loss. Recently, Hu et al. \cite{hu2020learning, hu2021sum} discuss the classification calibration on AoRR aggregate loss. However, it is still not clear these properties for Median, AB$_k$, and Close-$k$ aggregate losses. Note that the calibration property of the Maximum aggregate loss as a special case of Close-$k$ is discussed in \cite{he2018minimizing}. 
    On the other hand, for Average and Maximum guided individual losses, \cite{tewari2007consistency, gao2011consistency} have explored their consistency and calibration properties based on the binary case results. However, the properties of Top-$k$ and AT$_k$ guided individual losses are very hard to be analyzed based on existing consistency and calibration definitions. Therefore, \cite{lapin2016loss, lapin2017analysis} define top-$k$ calibration for the notion of calibration for the top-$k$ error. Inspired by these two works, \cite{yang2020consistency} defines a new top-$k$ consistency based on top-$k$ calibration under some moderate conditions. However, both top-$k$ calibration and consistency are defined for multi-class classification. No existing works discuss the top-$k$ calibration and consistency for multi-label learning. For example, these properties for TKML loss \cite{hu2020learning} have not been studied. This is a new direction that can be explored in the future.  
    
    \item \textbf{Generalization Capability}. In machine learning, optimal values for the model parameters are calculated from a finite training dataset and this model is then used to infer over other test datasets, all of which are typically assumed to be identically distributed samples. However, in real-world applications, any two finite datasets sampled from the same underlying distribution can violate the identical distribution assumption, leading to poor generalization. The generalization gap is obtained by the difference between training and test errors. The goal of the learning is to try to make this gap as small as possible in order to let the generalization capability will become strong.

    The average aggregate loss is also called the empirical risk minimization (ERM), which has been widely studied in its generalization capability through Vapnik–Chervonenkis (VC) dimension in Probably Approximately Correct (PAC) learning \cite{shalev2014understanding} or Rademacher complexity \cite{mohri2018foundations}. Similarly, the generalization capability of maximum aggregate loss is discussed in \cite{shalev2016minimizing} based on the VC dimension. \cite{fan2017learning, lyu2020average} connect AT$_k$ to SVM and then analyze its generalization bound. In addition, AB$_k$'s generalization bound is studied in 
    \cite{lee2020learning}. Hu et al. \cite{hu2021sum} provide a generalization bound for AoRR aggregate loss based on the generalization bound from CVaR. 
    However, the generalization capability of Median and Close-$k$ aggregate losses is not extensively studied.  
    
    \item \textbf{Optimization Error (Convergence Guarantee) of Learning Strategies}. When we design a loss function, the next step is to find an efficient and effective algorithm to optimize it. The applied algorithms usually dominate the final model performance. Difference algorithms can output different model performances. In addition, the loss functions are not always convex, which means the algorithms cannot always return the global optimal of the model parameters due to the non-convex of the loss function. Therefore, studying the optimization error or convergence guarantee of learning strategies (algorithms) combined with the designed loss function is essential.
    
    Most aggregate losses (Average, Maximum, Median, AT$_k$, AB$_k$, and AoRR) are optimized via gradient or sub-gradient-based descent or ascent algorithms. Their optimization errors are studied under specific conditions and tasks. For example, the AT$_k$ loss is usually connected with CVaR. Thus, some optimization approaches \cite{curi2020adaptive, namkoong2016stochastic} for CVaR can be regarded as the optimization methods for AT$_k$ aggregate loss, and the optimization error analyzed on CVaR can be extended to AT$_k$ aggregate loss. Similarly, Hu et al. in \cite{hu2021sum} adapt a difference-of-convex algorithm (DCA) to solve AoRR. Therefore, the optimization error on AoRR is directly dominated by DCA, while the convergence guarantee of DCA has been discussed in \cite{tao1986algorithms}. However, the Close-$k$ aggregate loss has not been explored in the current literature. For most of rank-based individual losses, they are optimized by using popular effective algorithms with existing convergence guarantee ({\em e.g.}, average guided \cite{lee2004multicategory, liu2011reinforced}, maximum guided \cite{guo2011adaptive}, top-$k$ guided \cite{lapin2015top}, and average top-$k$ guided \cite{lapin2015top}.) or heuristic algorithms without convergence guarantee ({\em e.g.}, average guided \cite{bredensteiner1999multicategory}, maximum guided \cite{crammer2001algorithmic, crammer2003family}, top-$k$ guided \cite{yan2018top}, and average top-$k$ guided \cite{fan2020groupwise}.). Therefore, exploring effective algorithms with low optimization errors for solving rank-based aggregate losses and individual losses is significant and worthwhile in the future. 
\end{itemize}

\subsection{Aggregate Gradients} Rank-based losses, especially aggregate losses, are usually connected with gradients since optimizing the selected individual losses is equivalent to selecting their corresponding gradients to update the model parameters during the training. In importance sampling \cite{katharopoulos2017biased, katharopoulos2018not, johnson2018training}, the technique suggests that the sampling example with probability proportional to the norm of loss term's gradient. Therefore, the gradient norm can be regarded as a significant informative cue to select necessary samples to speed up SGD-based algorithms and reduce the stochastic gradient's variance. Paul et al. in \cite{paul2021deep} find that the loss gradient norm of individual training samples can be applied to identify a smaller subset of the training dataset that can benefit the model generalization during the beginning of the training. They also find that the gradient norm can be used to prune a significant fraction of the training set without sacrificing the model generalization ability after a few training epochs. In addition, the gradient norm is further studied in \cite{liu2021learning} for training DNNs in the presence of corrupted supervision. The proposed method in \cite{liu2021learning} focuses on controlling the collective impact of data points on the average gradient. They observed that the gradient norm-based method is better than the loss value-based for handling the corrupted data in experiments.  Therefore, learning with a rank-based gradient norm is a potential direction that can be explored in the future. Most important, studying the aggregators on gradient norms is an exciting topic.

\subsection{Hyperparameter Tuning}
From the observations in rank-based aggregate and individual losses, we can find most of them are based on several significant hyperparameters. These hyperparameters have a substantial impact on the final model performance. For example, in AoRR aggregate loss,  the hyperparameter $m$ controls the number of potential outliers that will be ignored during the training. If it is smaller than the actual number of outliers, the model will be influenced by the outliers. If it is too large, some necessary samples will be discarded in training. Then the final model is not optimal. 

To this end, several works have tried to design new learning strategies for determining the hyperparameters in the model training. For example, in \cite{kawaguchi2020ordered}, Kawaguchi et al. apply AT$_k$ aggregator to design ordered SGD optimization methods. In order to automatically determine the value of $k$ during the training, they use an adaptive setting for decreasing $k$ when the model performance achieves preset-specific criteria. A similar method is applied in \cite{hu2020learning} for learning AoRR aggregate loss. In addition, they use greedy search to determine the outlier number related hyperparameter $m$. Recognized that the above methods may not be efficient for training models on large-scale datasets, Hu et al. in \cite{hu2021sum} design an auxiliary learning framework to determine the hyperparameters using a clean dataset, which is extracted from the original dataset that may contain outliers. However, this method has a drawback, which may not work when the designers don't have access to a clean dataset. Therefore, explorations into determining hyperparameters in rank-based decomposable losses will likely to emerge as a fruitful future direction.     








\section{Conclusion}\label{sec:conclusion}
This paper provides the first systematic and comprehensive survey of rank-based decomposable losses in machine learning. Concretely, we define a rank-based set function named aggregator and apply it to formulate aggregate and individual losses. Then, we review the literature from two aspects: rank-based decomposable aggregate losses and rank-based decomposable individual losses. We demonstrate the applicability and popularity of these losses by connecting them with several research topics in machine learning. We further provide six potential directions for future work. We find that the rank-based decomposable losses are indeed interested by many researchers from different fields in machine learning.  We believe this survey can push forward future research in this area and hope to help researchers to apply these existing losses and investigate new rank-based decomposable losses.  













\ifCLASSOPTIONcaptionsoff
  \newpage
\fi








\bibliographystyle{IEEEtran}
