Differentiable Top-k Classification Learning
Authors: Felix Petersen
Hilde Kuehne
Christian Borgelt
Oliver Deussen
Venue: ICLR 2022 Submitted (2022)
Keywords: top-k
top-5
imagenet

Abstract: The top-k classification accuracy is one of the core metrics in machine learning. Here, k is conventionally a positive integer, such as 1 or 5. In this work, we relax this assumption and propose to draw k from a probability distribution for training. Combining this with recent advances in differentiable sorting and ranking, we propose a new family of differentiable top-k cross-entropy classification losses. We find that relaxing k does not only produce better top-5 accuracies, but also makes models more robust, which leads to top-1 accuracy improvements. When fine-tuning publicly available ImageNet models, we achieve a new state-of-the-art on ImageNet for publicly available models with an 88.36% top-1 and a 98.71% top-5 accuracy. 

Under review as a conference paper at ICLR 2022
DIFFERENTIABLE TOP-k CLASSIFICATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
The top-k classification accuracy is of the core metrics in machine learning. Here, k is conventionally a positive integer, such as 1 or 5. In this work, we relax this assumption and propose draw & from probability distribution for training. Combining this with recent advances in differentiable sorting and ranking, we pro- pose new family of differentiable top-k cross-entropy classification losses. We find that relaxing it does not only produce better top-5 accuracies, but also makes models more robust, which leads to top-1 accuracy improvements. When fine- tuning publicly available ImageNet models, we achieve a new state-of-the-- art on ImageNet for publicly available models with an 88.37% top-1 and a 08.68% top-5 accuracy.
INTRODUCTION
Classification is one of the core disciplines in machine learning and computer vision. With the advent of classification problems with hundreds or even thousands of classes, the top-k classification accuracy has established itself an important task, i.e., algorithm can suggest & classes and one of them has to be the correct class. Usually, models are trained to optimize the top-1 accuracy and top-5 etc. are used for evaluation only. Some works (Lapin al., 2016 Berrada et al.) 2018 have challenged this idea and proposed top-k losses, such as a smooth top-5 margin loss. These methods have demonstrated superior robustness over the established top-1 softmax cross-entropy in presence of additional label noise (Berrada et al.) 2018). In standard classification settings, however, these methods have so far not shown improvements over the established top-1 softmax cross-entropy.
In this work, instead of selecting single top-k metric such as top-1 or top-5 for defining the loss, we propose to specify to be drawn from probability distribution Pk. which may or may not depend the confidence of specific data points
the class label. Examples for distributions Pk are [.5, 0, 0, 0, (50% top-1 and 50% top-5). [,1,0,0, 0,O, 0, 9 (10% top-1 and 90% top-5), and [.2, 2, 2, 2, .2) (20% top-k for each is from to 5). Note that, when k is drawn from distribution, as we can compute the expectation value in closed form.
this is done sampling-
Conventionally, given scores returned by neural network, softmax produces probability distribu- tion over the top-1 rank. Recent advances in differentiable sorting and ranking (Grover et al.) 2019 Prillo & Eisenschlos, 20200 Cuturi al., 2019 Petersen et al.) (22T)) provide methods for generaliz- ing this to probability distributions over all ranks represented by matrix P. Based on diffcrentiable ranking, multiple differentiable top-k operators have recently been proposed. They found applica- tions in differentiable k-nearest neighbor, differentiable beam search, attention mechanisms, and differentiable image patch selection (Cordonnier et al., (02T). In these areas, integrating differen- tiable top-k improved results considerably by creating a more natural end-to-end learning setting. However, to date, none of the differentiable top-k operators have been employed as neural network losses for top-k classification learning with k > 1.
Building on differentiable sorting and ranking methods, we propose a new family of differentiable top-k classification losses where t is drawn from probability distribution. We find that our top-k losses improve not only top-k accuracies, but also top-1 accuracy on multiple learning tasks.
We empirically evaluate our method using four differentiable sorting and ranking methods on the CIFAR- 100 (Krizhevsky et al., 2009), ImageNet- IK (Deng et al. 2009). and the ImageNet-21K-P (Ridnik et al., 2021) data sets. Using CIFAR-100, to train models from scratch. On ImageNet- IK, we demonstrate that our losses are capable of fine-tuning state-of-the-art models and achieve new state-of-the-art for publicly available mod-
demonstrate the capabilities of our losses

---

Under review as a conference paper at ICLR 2022
els on both top-1 and top-5 accuracy. We benchmark method multiple recent models and demonstrate that our proposed method consistently outperforms the baselines for the best two dif- ferentiable sorting and ranking methods. With ImageNet-2IK-P, where many classes overlap (but only one is the ground truth), we demonstrate that our losses are scalable to more than 10000 classes and achieve improvements of over 1% with only last layer fine-tuning.
Overall, while the performance improvements on fine-tume tuning are rather limited (because we retrain only the classification head), they are consistent and can be achieved without the large cost of train- ing from seratch. The absolute 0.2% improvement that we achieve on the ResNeXt- 101 32x48d WSL top-5 accuracy corresponds an error reduction by approximately 10%, and can be achieved at much less than the computational cost of (re- )triititinng the full model in the first place.
We summarize our contributions follows:
We derive a novel family of top-k cross- cross-entropy losses and relax the assumption of fixed k.
We find that they improve both top-k and top-1 accuracy.
We demonstrate its scalability more than 10 000 classes.
We propose splitter selection nets, which require fewer layers than existing selection nets.
We achieve new state-of-the the--trrrrt art results (for publicly available models) on ImageNetI
BACKGROUND: DIFFERENTIABLE SORTING AND RANKING
We briefly review NeuralSort, SoftSort, Optimal Transport Sort, and Differentiable Sorting Net- works. We omit the fast differentiable sorting and ranking method (Blondel et al. 2020b) as it does not provide relaxed permutation matrices / probability scores, but rather only sorted ranked vectors.
2.1 NEURALSORT SOFTSORT
To make the sorting operation differentiable, Grover et al. (019) proposed relaxing permutation matrices to unimodal row-stochastic matrices. For this, they use the softmax of pairwise differ- ences of (cumulative) sums of the top elements. They prove that this, for the temperature parameter approaching 0, is the correct permutation matrix, and propose variety of deep learning differen- tiable sorting benchmark tasks. They propose deterministic softmax based variant, as well as Gumbel-Softmax variant of their algorithm. Note that NeuralSort is not based on sorting networks.
Prillo & Eisenschlos (2020) build on this idea but simplify the formulation and provide SoftSort, a Taster alternative to NeuralSort. They show that it is sufficient to build on pairwise differences of elements of the vectors to be sorted instead of the cumulative sums. They find that SoftSort performs approximately equivalent in their experiments to NeuralSort.
2.2 OPTIMAL TRANSPORT / SINKHORN SORT
Cuturi et al. (2019) propose an entropy regularized optimal transport formulation of the sorting operation. They solve this by applying the Sinkhorn algorithm (Cuturi 2013) and produce gradients via automatic differentiation rather than the implicit function theorem, which resolves the need of solving linear equation system. As the Sinkhorn algorithm produces relaxed permutation matrix, we can also apply the Sinkhorn sort to top-k classification learning.
2.3 DIFFERENTIABLA SORTING NETWORKS
Petersen et (2021) propose differentiable sorting networks, continuous relaxation of sorting networks. Sorting networks are kind of sorting algorithm that consist of wires carrying the values and comparators, which swap the values on two wires if they are not in the desired order. Sorting networks can be made differentiable by perturbing the values on the wires of the sorting network in each layer of the sorting network by a logistic distribution, i.c., instead of min and max they use softmin and softmax. Similar to the methods above, this method produces relaxed permutation matrix, which allows us to apply it to top-k classification learning. Note that sorting networks are a classic algorithmic concept (Knuth) 1998a) not neural networks nor refer to differentiable sort- ing. Differentiable sorting networks are one of multiple differentiable sorting and ranking methods.
2

---

Under review as a conference paper at ICLR 2022
P
Pk|.3 5 0.
O..]
78785
Diff.
rank
rank2
[0
.0
.6
3
3
.7
.0
x.5
x1
P
CNN
rank 3
.1
.1
-0
.0
x0
Σ 6
6 .05]
Rank
rank 4
7
.0
.2
.0
X0
rankn
_
.0
.8
.0
.0]
x0
Pis the probability for
aiplett
and
goldhan
huwy
class to be among the top-k where k is drawn from Pk
Figure 1: Overview of the proposed architecture: A CNN predicts scores for image, which then ranked by a differentiable ranking algorithm returning the probability distribution for each rank in matrix P. The rows of this distribution correspond ranks, and the columns correspond to the respective classes. In the example, we use a 50% top-1 and 50% top-2 loss, i.c., Pk = [.5, .5, O, O, O]. Here, the kth value refers the top-k component, which is satisfied if the prediction at any of rank- 1 to rank-k. Thus, the weights for the different ranks can be computed via cumulative sum and are [1,.5, 5, O, O, 0). The correspondingly weighted sum of rows of P yields the probability distribution which can then be used in cross-entropy loss. Photo by Chris Curry on Unsplash.
ToP-k LEARNING
In this section, we start by introducing our objective, elaborate its exact formulation, and then build on differentiable sorting principles to efficiently approximate the objective. A visual overview over the loss architecture is also given in Figure !
The goal of top-k learning is to extend the learning criterion from only accepting exact (top-1) predictions to accepting l predictions among which the correct class has be. In its general form, for top-k learning, k may differ for each application, class, data point, or a combination thereof. For example, one practitioner may want to rank 5 predictions and assign score that depends on the rank of the true class among these ranked predictions, while, on the other hand, another practitioner may want to obtain 5 predictions but does not care about their order. Yet another practitioner in image classification may want to enforce a top-1 accuracy images from the "person" super-class, but resign to a top-3 accuracy for the "animal" super-class, as may have more ambiguities in class- labels. We model this by random variable K, following distribution Px that deseribes the relative importance of different values k. The discrete distribution Pк is either a marginalized distribution conditional distribution for each class, data
for given setting (such as the uniform distribution), point, etc. This allows the practitioner to specify a marginalized conditional distribution k ~ Pk- This generalizes the ideas of conventional top-1 supervision (usually softmax cross-entropy) and top-k supervision for a & like & 5 (usually based on surrogate top-k margin/hinge losses like (Lapin et al. 2016 Berrada et al. 2018) and unifies them.
The objective of top-k learning is maximizing the probability of accepted predictions of the model fe on data X.y ~ 'D given marginal distribution Px (or conditional Pkix.,, if it depends on the class y and/or data point X). In the following, Pk,y is the predicted probability of y being the kth-best prediction for data point X.
arg max Ex.yD [oo Ex
DEm Pm..)
(I)
To evaluate the probability of y to be the top-1 prediction, we can simply use softmax,(Jee (X)). However, & requires more consideration. Here, require probability scores PR.c for the kth prediction over classes e E C, where >n Pk.o = 1 (i.e., it P is row stochastic) and ideally additionally Σ Px.c = (i.e., it P is also column stochastic and thus doubly stochastic.) With this, optimize our model by minimizing the following loss
k Pmm Emoo(fe(X)) ))
Crop- (X, y) = - log Σ (k(K))
which is the cross entropy over the probabilities that the true class is among the top-k class for each possible k. Note that -k=1 Px (k<))) 1.
3

---

Under review as a conference paper at ICLR 2022
To compute Pk.c. we require function mapping from vector of real-valued scores an (ideally) doubly stochastic matrix P. The most suitable for this are the differentiable relaxations of the sorting and ranking functions, which produce differentiable permutation matrices P, which we introduced in Section 2 We build on these approximation: to propose instances of top-k learning losses and extend differentiable sorting networks to differentiable top-k networks, just finding the top-k scores is computationally cheaper than sorting all elements and reduces the approximation error.
3.1 ToP-k PROBABILITY MATRICES
The discussed differentiable sorting algorithms produce relaxed permutation matrices of size n X n. However, for top-k classification learning, we require only the top k rows for the number & of top- ranked classes to consider. Here, the largest & that considered for the objective, i.c., where (k(k) > 0. As n >> k. producing a k x matrix instead of n x n matrix is much faster.
For NeuralSort and SoftSort, is possible to simply compute only the top rows, as the algorithm is defined row-wise.
For the differentiable Sinkhorn sorting algorithm, it is not directly possible to improve the runtime, as in each Sinkhorn iteration the full matrix is required.
For differentiable sorting networks, is (via a bi-directional evaluation) possible to reduce the cost from On log" (n)) to (nk log" (n)). Here, it is important note the shape and order of multi- plications for obtaining P. As we only need those elements, which are (after the last layer of the sorting network) at the top ranks that we want to consider, we can omit all remaining rows of the permutation matrix of the last layer (layer f) and thus it is only of size (k x n).
(ke x n
(ke x
x n
(n
(3)
P
layer
layer t
layer 1
Note that during execution of the sorting network, P is conventionally computed from layer 1 to layer 4, i.e., from right to left. If we computed it this order, we would only save tiny fraction of the computational cost and only during the last layer. Thus, we propose to execute the differentiable sorting network, save the values that populate the (sparse) n X n layer-wise permutation matrices, and compute P in second pass from the back to the front, i.e., from layer to layer 1, or from left to right in Equation 3 This allows executing t dense-sparse matrix multiplications with dense k x n and sparse x n matrices. With this, reduce the asymptotic complexity from O(n² log" (n)) to Onk log" (n)).
matrices and sparse x n matrices instead of dense
3.1.1 DIFFERENTIABLE ToP-k : NETWORKS
As only the top-k rows of relaxed permutation matrix are required for top-k classification learning, it is possible to improve the efficiency of computing the top-k probability distribution via differen- tiable sorting networks by reducing the number of differentiable layers and comparators. Thus, we propose differentiable top-k networks, which relax selection networks in analogy how differen- tiable sorting networks relax sorting networks. Selection networks are networks that select only the top-k out of elements (Knuth 1998b). We propose splitter selection networks (SSN), novel class of selection networks that requires only Oloog n) layers (instead of the Ologg" n) layers for sorting networks) which makes top-k supervision with differentiable top-k networks more efficient and reduces the eттor (which is introduced in each layer.) SSNs follow the idea that the input is split into locally sorted sublists and then all wires that are not candidates to be among the global top-k can be eliminated. For example, for n 1024, Ie 5, SSNs require only 22 layers, while the best previous selection network requires 34 layers and full sorting (with bitonic network) requires even 55 layers. For n = 10450, A = 5 (i.e., for ImageNet-2IK-PP SNNs require 27 layers, the best previous requires 50 layers, and full sorting requires 105 layers. In addition, the layers of SSNs are less computationally expensive than those of the bitonic sorting network. Details on SSNs, as well as their full construction, can be found in Supplementary Material B Concluding, the contribution of differentiable top-k networks is two-fold: first, we propose a novel kind of selection networks that needs fewer layers, and second, relax those similarly differentiable sorting networks.
4

---

Under review as a conference paper at ICLR 2022
3.2 IMPLEMENTATION DETAILS
Despite those performance improvements, evaluating the differentiable ranking operators still re- quires considerable amount of computational effort for large numbers of classes. Especially if the number n. of elements to be ranked is = 000 (ImageNet- (K) or even n > 10 000 (ImageNet- 21K-P), the differentiable ranking operators can dominate the overall computational costs. addi- tion, for large numbers of elements to be ranked, the performance of differentiable ranking op- erators decreases as differentially ranking more elements naturally introduces larger errors (Grover et al. 2019 Prillo & Eisenschlos 2020 Cuturi et al.) 2019 Petersen et al. 2021). Thus, we reduce the number of outputs to be ranked differentially by only considering those classes (for each input) that have
make that the ground truth class is among those top-m scores, by replacing the lowest of the top-m scores by the ground truth class, necessary. For 1000, we choose this greatly improves training performance.
among the top-m scores. For this,
16, and for n 10 000, choose 50. We find that
Because the differentiable ranking operators (by their nature of being differentiable) only ap- proximations to the hard ranking operator, they each have their characteristics and inconsistencies. Thus, for training models from scratch, we replace the top-1 component of the loss by the regular softmax, which has a better and more consistent behavior. This guides the other loss if the differen- tiable ranking operator behaves inconsistently. To avoid the top-k components affecting the guiding softmax component and avoid probabilities greater than 1 in p. we can separate the cross-entropy into a mixture of the softmax cross-entropy (for the top-1 component) and the top-k cross-entropy (for the top-k 2 2 components) as follows:
fam (X,,)) = Px(1) SottsmaaCCrrsfsoooooooooooo/osos
(4)
-1 - (1-Px(1)) log
Σ PPmo(f((X)) 2= m=
Pk()))
4
RELATED WORK
We structure the related work into three broad sections: works that derive and apply differentiable top-k operators, works that use ranking and top-k training objectives in general, and works that present classic selection networks.
4.1 DIFFERENTIABLE ToP-k OPERATORS
Grover et al. (219)) include an experiment where they use the NeuralSort differentiable top-k oper-
ator for kNN learning. Cuturi al. (2019). Blondel al. (2020b), and Petersen et al. (202I) each apply their differentiable sorting and ranking methods to top-k supervision with A 1.
Xie et al. 2020b) propose a differentiable top-k operator based on optimal transport and the Sinkhorn algorithm (Cuturi 2013). They apply their method to k- d-nnarest-neighhor learning (kNN), differential beam search with sorted soft top-k; and top-k attention for machine translation. Cor- donnier et al. (202T) use perturbed optimizers (Blondel et al. (2020a) derive a differentiable top-k operator, which they use for differentiable image patch selection. Lee et al. (202T) propose using NeuralSort for a differentiable top-k operator to produce differenniable ranking metrics for recom- mender systems. Goyal et al. (2018) propose a continuous top-k operator for differentiable beam search. Pietruszka al. (2020) propose the differentiable successive halving top-k operator to ap- proximate the normalized Chamfer Cosine Similarity (nCCSak).
4.2 RANKING AND ToP-k TRAINING OBJECTIVES
Fan et al. (017) propose the "average top-k" loss, an aggregate loss that averages over the k largest individual losses of training data set. They apply this aggregate loss to SVMs for classification tasks. Note that this is not a differentiable top-k loss in the sense this work. Instead, the top-k is not differentiable and used for deciding which data points' losses are aggregated into the loss.
Lapin et al. (2015) 2016) propose relaxed top-k surrogate error functions for multiclass SVMs. In- spired by learning-to- -torank losses, they propose top-k calibration, a top-k hinge loss, top-k entropy
5

---

Under review as a conference paper at ICLR 2022
loss, well as truncated top-k entropy loss. They apply their method to multiclass SVMs and learn via stochastic dual coordinate ascent (SDCA).
Berrada et al. (2018) build on these ideas and propose smooth loss functions for deep top-k classifi- cation. Their surrogate top-k loss achieves good performance on the CIFAR- 100 and ImageNet K tasks. While their method does not improve performance on the raw data sets in comparison the strong Softmax Cross-Entropy baseline, in settings of label noise and data set subsets, they improve classification accuracy. Specifically, with label noise of 20% or more on CIFAR-I00, they improve top-1 and top-5 accuracy and for subsets of ImageNet1 of up to 50% they improve top-5 accuracy. This work is closest to ours in the sense that our goal is to improve learning of neural networks. However, in contrast to (Berrada et al., 2018), our method improves classification accuracy in un- modified settings. In our experiments, for the special case of k being a concrete integer and not being drawn from a distribution, we provide comparisons to the smooth top-k surrogate loss.
Yang & Koyejo| 2020) provide theoretical analysis of top-k surrogate losses as well as produce a new surrogate top-k loss, which they evaluate in synthetic data experiments.
related idea is set-valued classification, where a set of labels predicted. We refer to Chzhen et al. (202T) for an extensive overview. We note that our goal is not to predict set of labels, but instead we return a score for each class corresponding to a ranking, where only one class can correspond to the ground truth.
4.3 SELECTION NETWORKS
Previous selection networks have been proposed by, i..., (Wah & Chen 1984 Zazon-Ivry & Codish 2012 Karpiński& & Piotrów 2015). All of these are based on classic divide-and andiid--n-- sorting net- works, which recursively sort subsequences and merge them. In selection networks, during merg- ing, only the top-k elements are merged instead of the full (sorted) subsequences. In comparison to those earlier works, we propose new class of selection networks, which achieve tighter bounds (for k < n1), and additionally we continuously relax them.
5 EXPERIMENTS
5.1 SETUP
We evaluate the proposed top-k classification loss for four differentiable ranking operators on CIFAR- 100, ImageNet-IKK as well as the winter 2021 edition of mageNett221K-4 CIFAR-100 may be considered a small-scale data set with only 100 classes. We use CIFAR-100 to train a ResNetl 88 model (He et al., 2016) from scratch and show the impact of the proposed loss function on the top-1 and top-5 accuracy. In comparison, ImageNet-IK and ImageNet-21 K-P provide rather large-scale data sets with 000 and 10 450 classes, respectively. To avoid the unreasonable carbon- frotprtt of training many models from scratch, we decided to exclusively use publicly available backbones for all ImageNet experiments. This has the additional benefit of allowing more settings, making different seeds improve
work easily reproducible, and allowing perform multiple the statistical significance of the results. For ImageNet- we use two publicly available state-of- the-art architectures as backbones: First, the (four) ResNeXt-101 WSL architectures by Mahajan et al. (2018), which were pretrained in a weakly-supervised fashion on a billion-scale data set from Instagram. Second, the Noisy Student EfficientNet-L2 (Xie et al., 2020a), which was pretrained on the unlabeled JFT-300M data set (Sun et al., 2017). For ResNeXt-101 WSL, we extract 2 048- dimensional embeddings and for the Noisy Student EfficientNet-L2. we extract dimensonaii embeddings of ImageNet-1K K and fine-tune on them.
We apply the proposed loss in combination with various available differentiable sorting and ranking approaches, namely NeuralSort, SoftSort, Sinkhornort,, and DiffSortNets. The most important hyperparameter for each method is the temperature (or reparameterized as the inverse temperature). To determine the optimal temperature for each approach via grid search at resolution of factor 2. For training, we use the Adam optimizer (Kingma & Ba 2015). For training on CIFAR-100 from scratch, we train for up to 200 epochs with batch size of 100 at a learning rate of 10 10-3 For
ImageNet- 1K, we train for up to 100 epochs at a batch size of 500 and a learning rate of 10 4.5 For
ImageNet-21K-PP K-P, we train for up to 40 epochs batch size of 500 and learning rate of 10-1.

---

Under review as a conference paper at ICLR 2022
Method
Public
Top-1 acc.
Top-5
ResNet50
He al
2015
79.26
94.75
ResNet152
Hc
80.62
95.51
ResNeXt-101 32x48d WSL
Mahajan aTal.
2018
85.43
97.57
VIT-L/16
Dosovitskiy al.
2021
87.76
Noisy Student EfficiemtNet-222
Xie al 2020a
88.35
98.65
BiT-L
Kolesnikov 2020
87.54
98.46
CLIP (w/ Noisy Student EffNet-L22
Radlord 2021
X
AJ 88
VIT-H/14
Dosovilskiy al. 2021
X
88.55
ALIGN (EfficientNet-L.2)
Jia et al. 2022
X 88.64
98.67
Meta Pscudo Labels (Efficiem(Net-L22)
Pham ct al. 202
X 90.20
98.8
VIT-G/14
Zhar el al. 2021
X 90.45
CoAdNet-7
Dai et al. 2021
90.88 X
ResNeXt-101 32x48d WSL (used as backbone below)
86.06
97.80
Top-k Sort
86.29
97.97
Top-k SinkhorSort
(Top-5 focussed)
86.18
97.99
Top-k Sirt
(Equal focus on is from 1 to 5)
86.22
97.99
Top-k DiffSortNets
86.24
97.94
Top-k DiffSortNets
(Top-5 focussed)
86.04
97.98
Top-k DiffSortNets
(Equal focus on is from 1 to 5)
86.21
98.00
Noisy Student EfficientNet-L2
(used us backbone below)
88.33
98.65
Top-k SinkhornSott
88.32
98.66
Top-k DiffSortNes
88.37
98.68
Table 1: ImageNet-1K result comparison to state-of-the-art. Among the overall best performing differentiable sorting ranking methods, almost results in reasonable settings outperform their respective baseline Top-1 and Top-5 accuracy. For publicly available models backbones, achieve a new state-of-the-ar for top-1 and top-5 accuracy. Our results are averaged over runs.
We early stopping and found that these settings lead to convergence in all settings. As baselines, we use the respective original models, softmax cross-entropy, as well as learning with the smooth surrogate top-k loss (Berrada et al., 2018).
5.2 COMPARISON THE STATE-OF -EE---OTTTTEEEEE THE-ART
We compare the proposed results current state- of-the-art methods in Table [ We focus on meth- ods that publicly available and build upon two of the best performing models, namely Noisy Student EfficientNet-22 (Xie al.) (2020a). and ResNeXt- 101 32x48d WSL (Mahajan et al.) 2018). Using both backbones, we achieve improvements on both metrics, and when fine-tuning on the Noisy Student EfficientNet-.2. we achieve a new state-of-the-ar for publicly available models.
Tep-3 anc
400
(00
600
In Figure 2
we demonstrate our improvements on the four model sizes of ResNeXt-101 WSL. (32x8d, 32x16d, 32x32d, 32x48d). Our method improves the model in all settings.
Figure ImageNet- accuracy improvements for all ResNeXt-101 WSL model sizes (32x8d, 32x16d, 32x32d, 32x48d). Blue is the original model and orange with top-k fine-tuning.
Significance Tests. To evaluate the significance of the results, we perform a t-lest (with significance level of 0.01). We find that model is significantly better than the original model both top-1 and top-5 accuracy metrics. Comparing to the observed accuracies of the baseline (88.33 98 98.65), DiffSortNets are significantly better (p=0.00001 0.00005). Comparing to the reported accuracies of the baseline (88.35 98.65), DiffSortNets are also significantly better (p=0.00087 0 0..00005..
5.3 IMPACT OF THE DISTRIBUTION PK AND DIFFERENTIABLE SORTING METHODS
We start by demonstrating the impact Pk. which is the distribution from which we draw Let first consider the where & is 5 with probability and with probability 1 a, i.e., Pk
7

---

Under review as a conference paper at ICLR 2022
0.863
0.9798
0.862
0.9796
0.861
Top-1 acc
0.861
0.9794
0.9790
Top-5 acc
0.880
0.9792
Top-1
0.860
-0.9785
0.859
0.859
Top acc.
0.9788
Top-1
0.9780
Top-5 acc
0.858
Top-5
0.857
0.9775
0.0
0.2
0.4
0.8
1.0
10
15
20
25
30
35
40
where Px 1-1l
0,
Effects of varying the ratio between top-1 and top-5 (left) and varying the size of dif- ferentially ranked subset Both experiments are done with the differentiable Sinkhorn ranking algorithm (Cuturi et al. 2019). On the left, m 16, on the right, a = 0.75. Averaged over 5 runs.
Figure 3:
[1 -1- o. 0,0, In Figure 3 (left), we demonstrate the impact that changing a, i.e., transitioning from a pure top-1 loss a pure top-5 loss, has on tin-tuning ResNeXt-100 W'LL with our loss using the SinkhornSort algorithm. Increasing the weight of the top-5 component does not only increase top-5 accuracy but also improves the top-1 accuracy up to around 60% top-5; when using only k = 5, the top-1 accuracy drastically decays as the incentive for the true class to be at the top-1 position vanishes (or is only indirectly given by being among the top-5.) While the top-5 accuracy in this plot is largest for pure top-5 loss, this generally only applies to the Sinkhorn algorithm and overall training is stable a pure top-5 is avoided. This can also be seen on the left of Table 2
In Table 2] we consider more additional settings with all diff. ranking methods. Specifically, compare four notable settings: [.5, 0, 0, 05), i.e., equally weighted top-1 and top-5; [.25, O, O, 0, ..5]
and [.1, 0, 0, 0,-9. -9), i.e., top-5 has larger weights; [.2, .2, 2, .2). i.e., the case of having an equal weight of 0.2 for top-1 to top-5. The [,5 0,0, setting is rather canonical setting which usually performs well on both metrics, while the others tend favor top-5. In the [.5.0, O, .5] setting, all sorting methods improve upon the softmax baseline on both top-1 and top-5 accuracy. When increasing the weight of the top-5 component, the top-5 generally improves while top-1 decays.
Here we find the main insight of this paper: the best performance cannot be achieved by optimizing top-k for only a single k, but instead relaxing this constraint improves performance for all metrics.
ImageNet-IK / Px 11,0,0,0,0
0,
0,0,0,00..55
[,25, 0, 0,0,0, .7
[1,0,0,0,
22,
Softmax (bascline)
86.06 97.795
Smooth top-k loss [Berrada al. 2018
85.15
97.540
NeuralSort
33.37
94.748
86.30
97.896
34:26
95.410
34.32
94.889
85.75
86.
SoftSort
18.23 94.965
86.26
97.963
86.16
97.954
27.30
95.915
86.18
97.979
SinkhornSort
85.65
97.991
86.29
97.971
86.24
97.989
86.18
97.987
86.22
97.989
DiffSortNets
69.00 00.05 97.389
86.24
97.937
86.15
97.936
86.04
97.980
86.21
98.003
Table 2: ImageNet-Ie IK results for fine-tuning the head of ResNeXt-100 101
32x48d WSL (Mahajan
et al. 2018 averaged over 10 runs. The displayed metrics are Top-1 Top-5 accuracies.
1mageNet-21K.P. / Px 1,0,0,0,0]
[0,0,0,0,1
[,,0,0,0
2, 0,0.75
0, 0,0,
[.2, 2.2.2.24
Softmax (baseline)
39.29 69.63
Smooth top-k loss (Berrada 2018
34.03
63.56
NeuralSort
15.87
33.81
37.85
68.08
36.16
67.6 60
33.02
67. 67.29
37 09
67.
SoftSort
33.61
69.82
39.93
70.63
39.08
70.27
37.78
70.07
39.68
70.57
SinkhornSort
36.93
69.80
39.85
70.56
39.21
70.41
38.42
70.12
39.22
70.49
DifiSortNets
35.96
69.76
40.22
70.88
39.56
70.58
38.48
70.25
39.69
70.69
Table 3: ImageNet-211 2-KP results for fine-tuning the head of ResNeXt-101
32x48d WSL (Mahajan
al. 2018). The metries are Top-1 Top--5 accuracy averaged over 2 seeds.
8

---

Under review as a conference paper at ICLR 2022
CIFAR-100 / Pk
[,0,0,0,0]
[0,0,0,0,1]
15.00.00,.8
[25 0,5,0,0000 0.75
[1,
11.00000
0,0.0.0.11 0,.9
[22 22
22.22,222
Softmax (baseline)
61.27 85.31
Smooth top-k loss
Berrada al
2018
53.07
|5.22
NeuralSort
22.58
84.41
61.12
86.47
61.07
87.23
52.57
85.76
61.46
86.03
SoftSort
1.01 5.09
61.17
83.95
61.05
83.10
58.16
79.26
61.53
82.39
SinkhornSort
55.62 87.04
61.34
86.38
61.50
86.68
57.35
86.34
61.89
86.94
DiftSortNets
52.81
84.21
60.07
86.44
61.57
86.51
61.74
87.22
62.00
86.73
Table 4: CIFAR-100 results for training ResNet18 from scratch averaged over 2 seeds.
Comparing the differentiable ranking methods, can find the overall trend that SoftSort outper- forms NeuralSort, and that SinkhornSort as well as DiffSortNets perform best. We can see that some sorting algorithms are more sensitive the overall Pk than others: Whereas SinkhornSort (Cuturi ctt al. 2019) and Dift (Petersen et al. 2021 continuously outperform the softmax baseline, NouralSort (Grover et al., 2019) and SoftSort (Prillo & Eisenschlos 2020) tend collapse when over-weighting the top-5 components.
Comparing the performance on the medium-scale ImageNet-IK to the larger ImageNet-21K-P in Table we observe similar pattern. Here, again, using the top-k loss alone is not enough to significantly increase accuracy, but combining both, top-1 and top-k loss helps improve accuracy on both reported metrics. While NeuralSort struggles with good loss for this large-scale ranking problem and stays below the softmax baseline, DiffSortNets (Petersen et al. 2021 provide the best top-1 and top-5 accuracy with 40.22% and 70.88%, respectively.
We note that we do not claim that all settings (especially all differentiable sorting methods) im- prove the classification performance. Instead, we include all methods and also additional settings to demonstrate the capabilities and limitations cach differentiable sorting method.
It is notable that SinkhornSort overall achieves the most robust training behavior, while also being by far the slowest sorting method and thus potentially slowing down training drastically, especially when the task is only fine-tuning. SinkhornSort tends to require more Sinkhorn iterations towards the end of training. DifsSortNets are considerably faster, especially it is possible to only compute the top-k probability matrices and because of our advances for more efficient selection networks.
5.4 DIFFERENTIABLE RANKING SET SIZE m
We consider how accuracy is affected by varying the number of scores m to be differentially ranked. Generally, the runtime of differentiable top-k operators depends between linearly and cubic on thus it is important to choose an adequate value for m. The choice of m between 10 and 40 has only moderate impact on the accuracy can be seen in Figure (right). However, when setting m to large values such as (000 or larger, we observe that the differentiable sorting methods tend to become unstable. We note that did not specifically tune m, and that better performance can be achieved by fine-tuning m, as displayed in the plot.
5.5 TRAINING FROM SCRATCH
Finally, we demonstrate that the proposed loss can also be used to train a network from scratch. As reference baseline, we train ResNet18 from scratch on CIFAR-I00, considering the same settings as above. The results are shown in Table 4 Again, we find that training with top-k alone slightly improves the top-5 but not the top-1 accuracy, whereas weighted combination of both losses can significantly improve the performance on both metrics. Notably, here, [.2, 2, 2, 2, 2] with Diff- SortNets yields the best results on top-1 accuracy.
extension to learning with top-10 and top-20 components on In Supplementary Material A
I can be found.
CONCLUSION
In this work, we presented a novel loss, which relaxes the assumption of using a fixed & for top-k classification learning. For this, we leveraged recent differentiable sorting and ranking operators. We performed an array of experiments to explore different top-k classification learning settings and achieved state-of-the on ImageNet for publicly available models.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
The source code for the experiments will be made available upon publication. We only use publicly available resources, and each experiment can be reproduced using small-scale hardware. We used (wherever possible) multiple seeds for our experiments.
REFERENCES
Kenneth E. Batcher. Sorting networks and their applications. In Proc. AFIPS Spring Joint Com- puling Conference (Atlantic City, NJ), pp. 307-314, Washington, DC, USA, 1968. American Federation of Information Processing Societies.
Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Smooth loss functions for deep top-k classification. In International Conference on Learning Representations (ICLR), 2018.
Mathieu Blondel, Arthur Mensch, and lean-Philippe Vert. Differentiable divergences between time series. arXiv preprint arXiv:2010.08354, 2020a.
Mathieu Blondel, Olivier Teboul,, Quentin Berthet, and Josip Djolonga. Fast Differentiable Sorting and Ranking. In International Conference on Machine Learning (ICML), 2020b.
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, and Titouan Lorieul. Set-valued classifiattinn-vvevee via a unified framework. arXiv preprint arXiv:2102.1. 1231.. 2021.
Jean-Baptiste Cordonnier, Aravindh Mahendran, Alexey Dosovitskiy, Dirk Weissenborn, Jakob Uszkoreit, and Thomas Unterthiner. Differentiable patch selection for image recognition. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2351- 2360, 2021.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Proc. Neural Information Processing Systems (NIPS), 2013.
Marco Cuturi, Olivier Teboul, and lean-Philippe Vert. Differentiable ranking and sorting using optimal transport. In Proc. Neural Information Processing Systems (NIPS), 2019.
Zihang Dai, Hanxiao Liu, Quoe V Le, and Mingxing Tan. Coatnet: Marrying convolution and attention for all data sizes. arXiv preprint arXiv:2106.044: 04803, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255 255. leee, 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An im- age is worth 16x16 words: Transformers for image recognition at scale. International Confer- ence on Learning Representations (ICLR), 2021.
Yanbo Fan, Siwei Lyu, Yiming Ying, and Bao-Gang Hu. Learning with average top-k loss. In Proc. Neural Information Processing Systems (NIPS), 2017.
Kartik Goyal, Graham Neubig, Chris Dyer, and Taylor Kirk-iirkat continuous relaxation of beam search for end-to-end training of neural sequence models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic Optimization of Sorting Networks via Continuous Relaxations. In International Conference Learning Representations (ICLR), 2019.
Kaiming He,, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual lcarning for image recog- nition. arxiv 2015. arXiv preprint 15% 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
10

---

Under review as a conference paper at ICLR 2022
Chao Jia, Yinfei Yang. Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc V Le, Yunhsuan Sung, Zhen Li, and Tom Duerig. Scaling up visual and uisio-laagurdd representation learning with noisy text supervision. In International Conference Machine Learning (ICML), 2021.
Michat Karpiński and Marek Piotrów. Smaller selection networks for cardinality constraints encod- ing. In Proc. Principles and Practice of Constraint Programming (CP 2015, Cork, Ireland), pp- 210-20 225, Heidelberg/Berlin, Germany, 2015. Springer.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., 1998a.
Donald Ervin Knuth. The Art of Computer Programminng Volume 3: Sorting and Searching (2nd ed.). Addison Wesley, Reading, MA, USA, 1998b.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In Computer Vision- ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part V 16, pp. 491-507. Springer, 2020.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced search). 2009. URL ReLLhttp:/ www. cs toronto..oo.......... wtt..ttttooooooooooeoeeoee.e.ee. /ft.://...dd///.r.///./........ html
Maksim Lapin, Matthias Hein, and Bernt Schiele. Top-k multiclass svm. In Proc. Neural Informa- fion Processing Systems (NIPS), 2015.
Maksim Lapin, Matthias Hein, and Bernt Schiele. Loss functions for top-k error: Analysis and insights. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1468-1477, 2016.
Hyunsung Lee, Sangwoo Cho, Yeongjae Jang, Jaekwang Kim, and Honguk Woo. Differentiable ranking metric using relaxed sorting for top-k recommendation. JEEE Access, 9:1 2211449-1146555 2021.
Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens Van Der Maaten. Exploring the limits of weakly supervised pretraining. In Proceedings of the European conference on computer vision (ECCV), 2018.
Ian Parberry. The pairwise sorting network. Parallel Processing Letters, 2:205-211, 1992.
Felix Petersen, Christian Borgelt, Hilde Kuehne, and Oliver Deussen. Differentiable sorting net-
works for scalable sorting and ranking supervision. In International Conference on Machine Learning (ICML), 2021.
Hieu Pham, Zihang Dai, Qizhe Xie, and Quoc V Le. Meta pseudo labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp- 11557-11568, 2021.
Michat Pictruszka, Lukasz Borchmann. and Filip Graliński. Successive halving top-k operator.
arXiv preprint arXiv:2010./5555 2020.
Sebastian Prillo and Julian Eisenschlos. Softsort: A continuous relaxation for the argsort operator.
In International Conference on Machine Learning (ICML), 2020.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. arXiv preprint (xXiv:2103.0002) 2021.
Tal Ridnik, Emanuel Ben-Baruch, Asaf Noy, and Lihi Zelnik-Manor. Imagenet-21k pretraining for the masses. In Proc. Neural Information Processing Systems (NIPS), 2021.
Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable ef- fectiveness of data in deep learning era. In Proceedings of the IEEE international conference on computer vision, pp. 843 852, 2017.
11

---

Under review as a conference paper at ICLR 2022
Benjamin W. Wah and Kuo-Liang Chen. A partitioning approach to the design of selection networks. IEEE Trans. Computers, 33:261-268, 1984.
Qizhe Xie, Minh-Thine Kinh-Thang Luong, Eduard Hovy, and Quoc V Le. Self-training with noisy student improves imagenet classification. In Proceedings the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 10687-10698, 2020a.
Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. Differentiable top-k with optimal transport. Proc. Neural Information Processing Systems (NIPS), 2020b.
Forest Yang and Sanmi Koyejo. On the consistency of top-k surrogate losses. In International Conference on Machine Learning (ICML), pp. 10727-10735. PMLR, 2020.
Moshe Zazon-Ivry and Michael Codish. Pairwise networks are superior for selection. Unpublished manuscript, 2012.
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. arXiv preprint arXiv: 106.0460, 2021.
12

---

Under review as a conference paper at ICLR 2022
A EXTENSION TO TOP-10 AND TOP-20
We further extend the training settings, measuring the impact of top-10 and top-20 components on the large-scale ImageNet-2IK44 21 dataset. The results are diplayed in Table where we report top-1, top-5, top-10, and top-20 accuracy for all configurations. Again, we observe that 50% top-1 and 50% top-k produces the overall best performance and that training with top-5 yields the best top-1, top-5, and top-10 accuracy. We observe that the performance decays for top-20 components because (even among 10 450 classes) there are virtually no top-20 ambiguities, and artifacts of differentiable sorting methods can cause adverse effects. Note that top- 10 ambiguities do exist in ImageNet-21ER e.g., there are 11 class hierarchy levels Ridnik al. 20211
IN-21K-P Px (96)
1......
5. 0 0.... 0..5
0, ... 0,.76
0, O....
Ietw6
Ies-5
Softmax (baseline)
39.29
78.55
78.55
(85.33
NeuralSont
37.85
66808
77.
84.21
36.16
67.60
76.96
81.08
33.02
6T.29
86
81.05
SoftSort
39.93
70.63
79.45
85.96
39.08
70.27
79.29
85.94
37. 37
70.07
79.19
85.87
SinkhomSort
39.85
70.56 56
79.53 03
86.13
39.21
70.41
79.54
86.18
38 42
70.12
41
DiffSoriNets
40.22
70.88
79.54
86,03
39.56
70.58
79.44
86.01
38. 48.48
70.25
79.29
85.90
IN-2IK-P Pk (810)
O..0...
L3, 0
0,.5
[,25, O.... 0,.76
[1,00 ... 0,.9
km=10
1ene10
Ios
Softmax (baseline)
39.33
| 78.55
885.36
NeuralSort
37.22
67
02
76.75
84.10
31.59
66.09
76.46
81101
29.
65.16
76.26
81.01
SoftSort
39.26
69 52
79.13
85.93
37.71
68.56
78.
155778
33.65
67.35
78.43
85. 70
SinkhomSort
39.65
25
79.47
86.22
38.90
69.91
79. 11
86.
37
69.57
79.33
86 16
DiffSortNets
39.92
70.13
79.38
86.02
39.10
69.60
79.21
56.03
37 .8
69.07
79.04
85.91
IN-21K-P Px (920)
O1.0...
1,, 0, .... 0,.5)
1.25, O.... 0,.76
[.1. ... 0,.9
Softmax (baseline)
39.33 / 78.55
85.36
NeuralSort
36.32 33
75.82
83.99
33.00
62.99
T1.84
83.83
27.3 27.35
60.31
71.02
83.
SoftSort
38.04
66 98
77.17
85.45
34.30
62.89
76.03
85.19
24.02
56.35
74.32
84.82
SinkhomSort
39.76
69.76 76
79.17
86.17
38.77
69.18
78
37.71
68.68
78.86
86, 16
DiffSortNets
39.54
68.59
77.95
85.49
35.62
67.62
77.43 85.37
37.46
66.80
77.01
85.17
Table 5: ImageNet 21K with top-5, top-10 and top-20 components. column are (Top-1 Top-5| Top-10 Top-20).
The displayed metrics per
B SPLITTER SELECTION NETWORKS
Similar to a sorting network, a selection network is generally a comparator network and hence consists of wires (or lanes) carrying values and comparators (or conditional swap devices) connect- ing pairs of wires. A comparator swaps the values on the wires it connects if they are not in a desired order. However, contrast to sorting network, which sorts all the values carried by its wires, a (ks n) selection network, which has n wires, moves the k S n largest (or, alternatively, the l smallest) values to a specific set of wires (Knuth 1998b), most conveniently consecutive wires on one side of the wire array. Note that the notion of selection network usually does not require that the selected values are sorted. However, in our context it is preferable that they are, so that Px can easily be applied, and the selection networks discussed below all have this property.
Clearly, any sorting network could be used as a selection network, namely by focusing only on the top & (or bottom k) wires. However, especially if A is small compared to it is possible to construct selection networks with smaller size (i.e. fewer comparators) and often lower depth (i.e. a smaller number of layers, where layer is set of comparators that can be executed in parallel).
A core idea of constructing selection networks was proposed in (Wah & Chen 1984), based on the odd-even merge and bitonic sorting networks (Batcher 1968): partition the wires into sub- sets of at least & wires (preferably 2 [kog((k)] wires per subset) and sort each subset with odd-even mergesort. Then merge the (sorted) top & elements of each subsets with bitonic merge, thus haly- ing the number of (sorted) subsets. Repeat merging pairs of (sorted) subsets until only single (sorted) subset remains, the top lo elements of which are the desired selection. This approach re- quires? & (4) + 1) ([og)(n)] (k))()))(([)lgg)) + 1) layers.
13

---

Under review as a conference paper at ICLR 2022
0
3
3
4
4
3
5
6
6
7
Figure 4: Minimum ranks after splitter cascade resulting from the transitive closure of the swaps.
0
0
2
0
3 v
3
4
0
4
X
0
4
x
7
0
5 X
8
0
x
9
10
X
x
X
13
0
x
15 0
15X
5
10
Figure 5: (5, 16) selection network constructed with the method described in the text. The num- bers on the wires are the minimum ranks (starting at 0) that can be occupied by the values on these wires. Red crosses mark where wires can be excluded, green check marks where a top rank is de- termined. Swaps in blocks of equal color belong to the same splitter cascade. Swaps in gray boxes would be needed for full splitter cascades, but are not needed to determine the top ranks.
Improvements to this basic scheme were developed in (Zazon-Ivry Codish 2012 Karpiñski & Piotrów 2015) and either rely entirely odd-even merge (Batcher] 1968) entirely pairwise sorting networks (Parberry 1992). Especially selection networks based on pairwise sorting networks have advantages terms of the size of the resulting network (i.e. number of needed comparators), However, these improvements do not change the depth of the networks, that is, the number of layers, which is most important in the context considered here.
Our own selection network construction draws on this work by focussing specific ingredient of pairwise sorting networks, namely a so-called splitter (which happens to identical to a single bitonic merge layer, but for our purposes it is more comprehensible to refer to it as splitter). splitter for a list of m wires having indices (fo,-.. fm-1) 1] has comparators connecting wires l for i
and l+p where = [log2(m]]
{0, (0....,m, m
2 (mg)
A pairwise sorting network starts with what we call splitter cascade. That is, an initial splitter partitions the input wires into subsets (roughly) equal size. Each subset is split recursively until wire singletons result (Zazon-Ivry & Codish 2012). An example of such splitter cascade is shown in Figure for wires and in purple color for wires in Figure (arrows point to where the larger value is desired).
After a splitter cascade, the value carried by wire l has a minimum rank r = (2)()) where b(i) counts the number of set bits in the binary number representation of i. This minimum rank results from the transitivity of the swap operations in the splitter cascade, as is illustrated in Figure 4 for 8 wires: By following upward paths (in splitters the left) through the splitter cascade,
find
14

---

Under review as a conference paper at ICLR 2022
k
full
addeewen//airriiss/htoni selection
splitter selection
7
sort
3
4
6
8
3
4
6
8
16
10
4
7
9
9
10
10
10
10
4
6
7
8
10
11
12
13
1024
55
19
27
27
34
34
34
34
10
14
16
18
22
25
27
29
10450
105
14
27
39
39
50
50
50
50
14
18
20
23
27
30
32
34
65536
136
16
31
45
45
58
58
58
58
16
20
22
25
29
32
34
36
Table 6: Depths of sorting networks and selection networks (which are equal for odd-even, pairwise, bitonic networks) compared to selection networks constructed with splitter-base approach. Note that for small n and comparatively large k an oddd-even/parrvise/biio
selection network even a full sorting network may be preferable (e.g- 16 and k: 5), but that for larger considerable savings can be obtained for small k, even compared to other selection networks.
for each wire & exactly 20 wires with smaller indices that must carry values less than the value carried by wire f, This yields the minimum ranks shown in Figure on the right.
The core idea of our selection network construction is mum ranks of (the values carried by) wires. If such a minimum rank exceeds & (or equals k, since wire
splitter cascades to increase the mini-
be dis- carded, since its value is certainly not among the top k. On the other hand. if there is only one wire with minimum rank O, the top value has been determined. More generally, if all minimum ranks no greater than some value occur for one wire only, the top r + 1 values have been determined.
work with zero-based ranks and hence interested in ranks {0, {0...., (0....,k-1]] 1}).
k-1))
We exploit this as follows: Initially all wires are assigned minimum rank of since the begin- ning we do not know anything about the values they carry. We then repeat the following construction: traversing the values r l- descendingly. we collect for each all wires with minimum rank and apply splitter cascade them (provided there are at least two such wires). Suppose the wires collected for minimum rank have indices (Ca. -o.....,, (m(r)-1). After the splitter cascade we update the minimum rank of wire & to + 21, because before the splitter cascade there is no known relationship between wires with the same minimum rank, while the splitter cascade es- tablishes relationships between them, increasing their ranks by 26(1) -11))-1.10 The procedure of traversing the minimum ranks k k-1,..., 0 descendingly, collecting wires with the same minimum rank and applying splitter cascades them is repeated until all minimum ranks 0, O.... k-1 occur only once.
As an example, Figure 5 shows a (5, 16) selection network constructed is this manner, in which the minimum ranks of the wires indicated after certain layers well when certain wires can be discarded (red crosses) and when certain top ranks are determined (green check marks). Comparators belonging to the same splitter cascade are shown in the same color.
While selection networks resulting from adaptations of sorting networks (see above) have the ad- vantage that they guarantee that their number of layers is never greater than that of a full sorting network, our approach may produce networks with more layers. However, if & is sufficiently small compared (in particular, l < (n)), our approach can produce selection networks with considerably fewer layers, as is demonstrated in Table 6 Since in the context we consider here we can expect à & (n), splitter- plitter-basee selection networks are often superior.
15


Reviews:
[{"review_id": "rOwo0LGbjx", "reviewer": "Reviewer_RKLW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The efforts on optimizing the top-k classification learning through differentiable sorting appear novel to me. The discussion on differential sorting is comprehensive. The paper specifically discusses each of the options and how it is optimized for the studied scenario. \n- Experiments are thorough \n- The work is also interesting because the performance gains come only because of fine-tuning.\n\n\nWeaknesses\n\n- The second term and eqn 2 would be constant with k=5 (if only the top five rows of the P matrix are constructed). Expanding eqn2 for the given example in Fig1, the loss would be: -log(0.5 *.03 + 0.5 (0.3+0.6)), assuming Panda is the ground truth class. Consider a case of P_K [0.5 0 0 0 0.5], the equation would be -log (0.5 top1 + 0.5 (top1+top2+top3+top4+top5)). If only five columns are reconstructed and if they are column stochastic, then the sum of top1 to top5 would always be 1. Then the second term will always give a constant value. Requesting the authors to clarify this aspect.\n\n- At first, it appears that the distribution would be a sample. However, fixed distribution is used for a set of experiments. For example, it is either [0.5 0 0 0 0.5] or [0.2 0.2 0.2 0.2 0.2] for the entire experiment. Hence, presenting it as \"sampled\" is confusing. The best results come when you have the top1 and the sum of the top five values. Hence, the initial discussion and intuition can be improved a bit.\n\n- The improvements on Noisy Student EfficientNet-L2 are negligible. 88.35 to 88.36 is certainly not statistically significant. Were experiments for Table1 were also ran 10 times (like table 2?).\n\n- Please mention the number of rows that were reconstructed for each experiment. The number of columns (m) is mentioned in the experiments but not the number of rows.\n\n- Berrada et al. was used to train the model from scratch. It would be worth comparing their loss for fine-tuning purposes as well. I think that would be a fairer comparison. \n\n", "summary_of_the_paper": "The paper proposes a method to employ the benefits of differential sorting methods towards top-k classification learning. The presents several experiments with sampling weights for different ranks and presents the results. The loss is used for fine-tuning in most experiments (apart from the CIFAR100 case). The method seems to give minor improvements on the ResNeXt-101 32*48d baseline. ", "summary_of_the_review": " Although the paper brings several novel perspectives, there remain several ambiguities as well. Some additional experiments, clarifications can also strengthen the draft. Overall, in the current form, the paper is a borderline one and the final decision will depend a lot on the discussion during the rebuttal phase. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gknz7esELlT", "reviewer": "Reviewer_Abaq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths\n1. The idea of using different probability distributions for k is interesting. The results also demonstrate the effectiveness of this idea.\n2. The experiments of incorporating different sorting methods are comprehensive.\n\n\nweaknesses\n1. In my opinion, the P_K is more like a set of weights, rather than a probability distribution. If it is the case, I recommend improving the descriptions to reduce confusion.\n2. It would be nice to present an experiment with conditional probability distributions for k of different classes based on their semantic meaning (like person, animal). I think it is also a significant contribution of this paper.\n", "summary_of_the_paper": "This paper addresses Top-k classification learning. Based on the recent progress on differentiable sorting and ranking, the author proposes a loss function for top-k classification where the k is not fixed but follows a given probability distribution. To improve the efficiency, a splitter selection network is proposed so that fewer layers are required for the sorting network. \n\nThe proposed loss function can be combined with different sorting methods. In experiments, the loss function is shown to be effective in training a model from scratch on Cifar10. It can also be used in fine-tuning on ImageNet dataset and has performance gain. ", "summary_of_the_review": "This paper proposes a flexible loss function for top-k classification, providing useful insights for image classification. So it is worth of reading for the researchers in this area.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XY-jt234yxO", "reviewer": "Reviewer_575y", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\tThe motivation of this paper is clear to draw k from a probability distribution for training. \n\tThe idea of this paper is pretty novel and exciting which makes the classification model robust.\n\tThe extensive experiments conducted on five data sets are sufficient to show the advantages of the proposed idea\nWeaknesses:\n\tThe details of the differentiable sorting networks is not represented. How to rank the predicted scores of the final classification layer and get the probability distribution?\n\tIn figure 1, the first row (rank1) are multiplied by 1 and the second row(rank2) are multiplied by 0.5. Please explain the reason.\n", "summary_of_the_paper": "This paper proposes a loss to relax the assumption of using a fixed k for top-k classification learning. The authors use the existing differentiable sorting and ranking operators. Experimental results also achieve a state-of-the-art on ImageNet.", "summary_of_the_review": "This paper derives a family of top-k cross entropy losses which is a novel practice. The experimental analysis on ImageNet including the impact of the distribution and ranking set size m, etc, is concrete and sufficient.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BI03bTZqSEF", "reviewer": "Reviewer_FWmd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- Set-valued classification is an important topic to cope with class ambiguity. Few works (only one as far as I know [1]) have proposed a top-k loss for neural networks and there is room for improvements \n- The proposed approach is different from [1] as it relies on sorting networks to determine the set of the most likely classes rather than a purely top-k objective\n\nWeaknesses\n- A first weakness is that the contribution is quite incremental and not well justified from a theoretical point of view. Using sorting networks for top-k is an acceptable strategy from a practical point of view but a bit over-kill and not very new from a theoretical point of view. The proposal to use several values of K is also not really justified. The principle of top-K is to predict sets of fixed size contrary to other set-valued classification approaches that attempt to solve other objectives (e.g. adaptive set sizes but equal to K on average). We let the authors refer to [2] for a clear overview of the different objectives. Here, the objective is not really clear. If K is supposed to be a random variable (e.g. 50% chance of being 1 and  50% chance of being 5), that means that for the same image x, the classifier is supposed to return randomly either one class or 5 classes without any consideration with regard to the image content itself. \n- another main weakness is that no significant improvement of the proposed loss over cross-entropy is shown. The reported top-K accuracy gains are not systematic and so low that they may be not statistically significant. As a first step towards a better understanding of the results, the authors should first compute some significance tests (e.g. p-values on several runs and a clear cross-validation procedure for model selection among epochs). But even so, it won’t resolve the fact that the performance gain is observed only for some specific configurations (e.g. a specific sorting network and specific values of K probabilities) and remains very low even in such advantageous conditions. \n\n[1] Berrada, L., Zisserman, A., & Kumar, M. P. (2018). Smooth loss functions for deep top-k classification. arXiv preprint arXiv:1802.07595.\n[2] Chzhen, E., Denis, C., Hebiri, M., & Lorieul, T. (2021). Set-valued classification--overview via a unified framework. arXiv preprint arXiv:2102.12318.\n", "summary_of_the_paper": "The paper proposes a differentiable loss for top-K classification based on differentiable sorting networks, i.e. sorting neural networks in which basic min/max operations are replaced by smoothed versions (i.e. softmax/softmin). The main principle is to use the sorting network to estimate the probability of the rank of each class and then filter only the top-k. An extension consists in considering that k can take several possible values at random (e.g. 50% chance of being 1 and  50% chance of being 5). \n\nThe resulting loss is experimented on three datasets (CIFAR-100, ImageNet-1K and ImageNet-21K-P) and with three existing sorting networks. Performances are mainly compared to cross-entropy showing low improvements. ", "summary_of_the_review": "An interesting attempt to improve the top-K classification but consistent limitations:  \n(I) an incremental contribution and no clear justification of considering k as a random variable\n(ii) no significant improvement of the proposed loss over cross-entropy\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main consensus among the reviewers was that although the approach is interesting, this submission suffers from two main weaknesses:

- The methodology is not very novel, and the proposed parts of the method not well justified (in particular regarding the interplay of a differentiable sorting approach and of the random choice of k)

- The results, compared to a standard cross-entropy loss are not very convincing: there does not seem to be a statistically significant advantage.
Decision: Reject