Monotonic Differentiable Sorting Networks
Authors: Felix Petersen
Christian Borgelt
Hilde Kuehne
Oliver Deussen
Venue: ICLR 2022 Poster (2022)
Keywords: differentiable sorting
monotonic
sorting
ranking
sorting networks

Abstract: Differentiable sorting algorithms allow training with sorting and ranking supervision, where only the ordering or ranking of samples is known. Various methods have been proposed to address this challenge, ranging from optimal transport-based differentiable Sinkhorn sorting algorithms to making classic sorting networks differentiable. One problem of current differentiable sorting methods is that they are non-monotonic. To address this issue, we propose a novel relaxation of conditional swap operations that guarantees monotonicity in differentiable sorting networks. We introduce a family of sigmoid functions and prove that they produce differentiable sorting networks that are monotonic. Monotonicity ensures that the gradients always have the correct sign, which is an advantage in gradient-based optimization. We demonstrate that monotonic differentiable sorting networks improve upon previous differentiable sorting methods.

Published as a conference paper at ICLR 2022
MONOTONIC DIFFERENTIABLE SORTING NETWORKS
Felix Petersen', Christian Borgelt', Hilde Kuehne Oliver Deussen' Universityy of Konstanz, ?University of Salzburg, "University of Frankfurt, 'IBM-MIT Watson AI Lab, felix. peterseettrssn watpeeennnni--nnntaaaaaaaaa koosskonss...................... de
ABSTRACT
Differentiable sorting algorithms allow training with sorting and ranking supervi- sion, where only the ordering or ranking of samples is known. Various methods have been proposed to address this challenge, ranging from optimal transport-bar -aase differentiable Sinkhorn sorting algorithms to making classic sorting networks dif- ferentiable. One problem of current differentiable sorting methods is that they are non-monotonic. To address this issue, propose novel relaxation of conditional swap operations that guarantees monotonicity in differentiable sorting networks. We introduce family of sigmoid functions and prove that they produce differen- tiable sorting networks that are monotonic. Monotonicity ensures that the gradients always have the correct sign, which is advantage in gradient-based optimiza- tion. We demonstrate that monotonic differentiable sorting networks improve upon previous differentiable sorting methods.
INTRODUCTION
Recently, the idea of end-to-end training of neural networks with ordering supervision via continuous relaxation of the sorting function has been presented by Grover et al. [1]. The idea of ordering supervision is that the ground truth order of some samples is known while their absolute values remain unsupervised. This is done by integrating a sorting algorithm in the neural architecture. As the eтror needs to be propagated in meaningful way back to the neural network when training with a sorting algorithm in the architecture, it necessary to use differentiable sorting function. Several such differentiable sorting functions have been introduced, e.g.. by Grover el al. [1], Cuturi et al. [2], Blondel el al. [3], and Petersen el al. [4]. this work, we focus on analyzing differentiable sorting functions [1]-[4] and demonstrate how monotonicity improves differentiable sorting networks [4].
Sorting networks are a family of sorting algorithms that consist of two basic components: so called "wires" (or "lanes") carrying values, and conditional swap operations that connect pairs of wires [5]. An example of such a sorting network shown in the center of Figure 1. The conditional swap operations swap the values carried by these wires if they are not in the desired order. They allow for fast hardware-implementttio hardware like GPUs. Differentiable sorting networks [4] continuously relax the conditional swap operations by relaxing their step function to logistic sigmoid function.
e.g., in ASICs, as well as on highly parallelized general-purpose
One problem that arises in this context that using a logistic sigmoid function does not preserve monotonicity of the relaxed sorting operation, which can cause gradients with the wrong sign. In this work, we present a family of sigmoid functions that preserve monotonicity of differentiable sorting networks. These include the cumulative density function (CDF) of the Cauchy distribution, as well as function that minimizes the error-bound and thus induces the smallest possible approximation error. For all sigmoid functions, we prove and visualize the respective properties and validate their advantages empirically. In fact, by making the sorting function monotonic, it also becomes quasiconvex, which has been shown to produce favorable convergence rates [6]. In Figure 2, demonstrate monotonicity for different choices of sigmoid functions. As can be seen in Figure 4, existing differentiable sorting operators are either mon-ooooooicc have an unbounded error.
Following recent work [1], [2]. [4], we benchmark our continuous relaxations by predicting values displayed on four-digit MNIST images [7] supervised only by their ground truth order. The evaluation shows that our method outperforms existing relaxations of the sorting function on the four-digit MNIST ordering task well as the SVHN ranking task.

---

Published as a conference paper at ICLR 2022
O
3 4
7
CNN
40
6g
6 8 2 1
CNN
0
4 6
CNN
42
0
1 8 5
2
CNN
0/
P
LT
1
.1
6 2 O
CNN
1
11
11
10
4
66 7
CNN 45
66
2
11
Figure 1: The architecture for training with ordering supervision. Left: imput values are fed separately into a Convolutional Neural Network (CNN) that has the same weights for all instances. The CNN maps these values to scalar values do,,.., 05. Center: the odd-even sorting network sorts the scalars by parallel conditional swap operations such that all inputs can be propagated to their correct ordered position. Right: It produces a differentiable permutation matrix P. this experiment, the training objective is the cross-entropy between P and the ground truth permutation matrix Q. By propagating the error backward through the sorting network, we can train the CNN.
Contributions. In this work, we show that sigmoid functions with specific characteristics produce monotonic and error-bounded differentiable sorting networks. We provide theoretical guarantees for these functions and also give the monotonic function that minimizes the approximation error. We empirically demonstrate that the proposed functions improve performance.
RELATED WORK
Recently, differentiable approximations of the sorting function for weak supervision were introduced by Grover et al. [1], Cuturi et al. [2], Blondel et al. [3], and Petersen et al. [4].
In 2019, Grover al. [1] proposed NeuralSort, a continuous relaxation of the argsort operator. (hard) permutation matrix is a square matrix with entries 0 and 1 such that every row and every column sums up to 1, which defines the permutation necessary to sort sequence. Grover et al. relax hard permutation matrices by approximating them as unimodal row-stochastic matrices. This relaxation allows for gradient- based stochastic optimization. On various tasks, including sorting four-digit MNIST numbers, they benchmark their relaxation against the Sinkhorn and Gumbel-Sinkhorn approaches proposed by Mena et al. [8].
Cuturi al. [2] follow this idea and approach differentiable sorting by smoothed ranking and sorting operators using optimal transport. As the optimal transport problem alone is costly, they regularize it and solve it using the Sinkhorn algorithm [9]. By relaxing the permutation matrix, which sorts sequence of scalars, they also train a scalar predictor of values displayed by four-digit numbers while supervising their relative order only.
Blondel et al. [3] cast the problem of sorting and ranking as linear program over a permutahedron. To smooth the resulting discontinuous function and provide useful derivatives. they introduce strongly convex regularization. They evaluate the proposed approach in the context of top-k classification and label ranking accuracy via a soft Spearman's 's rank correlation coefficient.
Recently, Petersen et al. [4] proposed differentiable sorting networks, differentiable sorting operator based on sorting networks with differentiably relaxed conditional swap operations. Differentiable sorting networks achieved a new nate-of-the-art on both the four-digit MNIST sorting benchmark and the SVHN sorting benchmark. Petersen al. [10] also proposed a general method for continuously relaxing algorithms via logistic distributions. They apply it, i.a., to the bubble sort algorithm and benchmark in on the MNIST sorting benchmark.
Applications and Broader Impact. In the domain of recommender systems, Lee al. [11] propose differentiable ranking metrics, and Swezey er al. [12] propose PiRank, a learning-to- to-rank method using differentiable sorting. Other works explore differentiable sorting- based top-k for applications such as differentiable image patch selection [13], differentiable k-ncarest-neighhoo neighbor [1]. [14], top-k attention for machine translation [14], and differentiable beam search methods [14], [15].
2

---

Published as a conference paper at ICLR 2022
3 BACKGROUND: SORTING NETWORKS
Sorting networks have a long tradition in computer science since the 1950s [5]. They are highly parallel data-oblivious sorting algorithms. They are based on so-called conditional pairwise swap operators that map two inputs to two outputs and ensure that these outputs are in specific order. This achieved by simply passing through the imputs if they are already in the desired order and swapping them otherwise. The order of executing conditional swaps is independent of the input values, which makes them data-oblivious. Conditional swap operators can be implemented using only min and max. That is, if the inputs a and b and the outputs a' and V/ a swap operator ensures a' S V and can easily be formalized as a' = min(a, a. b) and d' = max(a, b). Examples of sorting nets are the odd-even network [16], which alternatingly swaps odd and even wires with their successors, and the bitonic network [17], which repeatedly merges and sorts bitonic sequences. While the odd-even network requires n layers, the bitonic network uses the only (log2 n1 + loga / layers.
and-conquer principle to sort within
Note that, while they are similar in name, sorting networks are not neural networks that sort.
3.1 DIFFERENTIABLE SORTING NETWORKS
In the following, we recapitulate the core concepts of differentiable sorting networks [4]. An example of an odd-even sorting network is shown in the center of Figure 1. Here, odd and even neighbors are conditionally swapped until the entire sequence is sorted. Each conditional swap operation can be defined in terms of min and max as detailed above. These operators can be relaxed to differentiable min and maz. Note that we denote the differentiable relaxations in stalic font and their hard counterparts in roman font. Note that the differentiable relaxations min and mar are different from the commonly used softmin and softmax, which are relaxations of argmin and argmax [18).
One example for such a relaxation of min and max the logistic relaxation
mina (a, b) = a (bb - a) + b- (a b) and maz, (a, b) = a o(a - b) + b a(b - a) (1)
where a is the logistic sigmoid function with inverse temperature 3 > 0:
(2)
1 e-
Any layer of a sorting network can also be represented as a relaxed and doubly permutation matrix. Multiplying these (layer-wiss permutation matrices yields (relaxed) total permutation matrix P. Multiplying P with an input x yields the differentiably sorted vector & = Px. which is also the output of the differentiable sorting network. Whether it is necessary to compute P. or whether å suffices, depends on the specific application. For example, for a cross-entropy ranking / sorting loss as used in the experiments in Section 6, P can be used to compute the cross-entropy to ground truth permutation matrix Q.
In the next section, we build on these concepts introduce monotonic differentiable sorting networks, i.e,, all differentiably sorted outputs i are non-decreasingly monotonic in all inputs z.
MONOTONIC DIFFERENTIABLE SORTING NETWORKS
In this section, we start by introducing definitions and building thcorems upon them. In Section 4.2, use these definitions and properties to discuss different relaxations of sorting networks.
4.1 THEORY
We start by defining sigmoid functions and will then use them to define continuous conditional swaps. Definition 1 (Sigmoid Function). We define a (unipolar) sigmoid (i.e., s-shaped) function as a continuous monotonically non non-decreasing odd- symmmermtt (around 2) function with
f: R T= 10
with
lim f(x) 0 and 2---0
lim f(x) 1.
2-400
3

---

Published as a conference paper at ICLR 2022
Definition 2 (Continuous Conditional Swaps). Following [4]. define continuous conditional swap in terms of a sigmoid function f :R + [0, 1|
as
min, b) = a f(bb a) + b- f(a -o-bb,, b): maz (a. b) a. - b) f(b ( a), argrivim y ( (5(b- a),
(3)
arymaa ( (S(a- 5(b a) )
We require a continuous odd-symmetric sigmoid function to preserve most of the properties of min and max while also making aryman and arymaz: continuous as shown in Supplementary Material B. In the following, we establish doubly-stochasticity and differentiability of P, which are important properties for differentiable sorting and ranking operators.
Lemma (Doubly- Stochasticity and Differentiability of P). (i) The relaxed permutation matrix P. produced by differentiable sorting network, is Joubly-stochastic (ii) P has the same differentiability as J, e.g., if f is continuously differentiable in the input, will be continuously differentiable in the input to the sorting network. If f is differentiable almost everywhere (a.e.), P will be diff. a.e.
Proof. (i) For each conditional swap between two elements i,j. the relaxed permutation matrix is 1 the diagonal except for rows and] j: at points i, i and j.j the value E [0, 1]. at points i, and j, i the value is V and all other entries are 0. This is doubly-stochastic all rows and columns add up to 1 by construction. As the product of doubly-stochastic matrices is doubly-stochastee the relaxed permutation matrix P. produced by differentiable sorting network, is doubly-stochaste
(ii) The composition of differentiable functions is differentiable and the addition and multiplication of differentiable functions is also differentiable. Thus, sorting network is differentiable if the employed sigmoid function is differentiable. "Diffcrentiable" may be replaced with any other form of differentiability, such "differentiable a.c."
Now that we have established the ingredients to differentiable sorting networks, we can focus on the monotonicity of differentiable sorting networks.
Definition 4 (Monotonic Continuous Conditional Swaps). We say f produces monotonic conditional swaps if m (z, 0) is non-decreasingly monotonic in x. i.e., min 0) 2 for all x.
sufficient to define w.l.o.g. in terms of min ((z 0) due to its commutativity, stability, and odd-symmetry of the operators (cf. Supplementary Material B).
Theorem (Monotonicity of Continuous Conditional Swaps). continuous conditional swap (in terms of differentiable sigmoid function f) being non non-decreasingly monotonic in all arguments and outputs requires that the derivative of f decays no faster than 1/2², i.e.,
f'(x) E Ω
Proof. We show that Equation 5 is necessary criterion for monotonicity of the conditional swap.
Because f is a continuous sigmoid function with f R + [0, 1]. ( 0) f(-x) x > 0 for
some I > 0. Thus, montononicity of min y (z, 0) implies lim supa->o0 min (xx 0) > 0 (otherwise the value would decrease again from a value 0.) Thus,
f(-x) (L'Hópital's rulo)
-f'(-x)
lim min 0) = lim f - = lim 2-000
lim
(6)
x
x- 30
-4000
1/x
a=000
-1/22
lim f((zz) lim f(xx) = limsup x0000
f((x) 0++ eQ
1/x2
x 1/2²
1/2²
x
assuming
[() lim 1/22
exists. Otherwise, it can be proven analogously via proof by contradiction.
Corollary 6 (Monotonic Sorting Networks). If the individual conditional swaps of a sorting network are monotonic, the sorting network also monotonic.
Proof. If single layers g, h non-decreayyngly monotonic in all arguments and outputs, their composition h is also non -on-decreayy monotonic in all arguments and outputs. Thus, a network of arbitrarily many layers is non-decreasingly monotonic.
n
4

---

Published as a conference paper at ICLR 2022
Above, we formalized the property of monotonicity. Another important aspect is whether the error of the differentiable sorting network is bounded. It is very desirable to have a bounded error because without bounded errors the result of the differentiable sorting network diverges from the result of the hard sorting function. Minimizing this error is desirable.
Definition 7 BronndB Continuous Conditional Swaps). A continuous conditional swap has a bounded error if and only if sup, min (ar, 0) = c is finite. The continuous conditional swap is therefore said to have an error bounded by
It is sufficient to define it w.l.o.g. in terms of min m 0) due to its commutativity, stability, and odd-symmetry the operators (cf. Supplementary Material B). general, for better comparability between functions, assume Lipschitz continuous function f with Lipschitz constant 1.
Theorem 8 (Error-Bounds of Continuous Conditional Swaps). (i) A differentiable continuous condi- tional swap has a bounded error if
f'(x) E
(8)
x²
(ii) If it is additionally monotonic, the error-bound can be found as limg- min (2, 0) and addi- tionally the error is bound only if Equation 8 holds.
Proof. (i) W.l.o.g. we consider æ > 0. Let g(z) = ((-1/1)),,//)
= 0. Thus, g g()= = 1/22.
f1/2//2 S according to Equation Thus, g(2) (0) + So g') S c 2. Therefore.
1(-1/2) se 1/2 1(-1/2) I and with x = =1/2 = x f(=() min 0) S
(ii) Let min, (2r, 0) be monotonic and bound by miny(x,0) S c. For > 0 and h(x) = min (z,, 0),
h' h'(x) x. f0-z)
= x²
+ f(-x) S x(-z) cc (9)
And thus fx(x E 0 )
Theorem 9 (Error-Bound) of Diff. Sorting Networks). If the error of individual conditional swaps of a sorting network is bounded by and the network has E layers, the total error is bounded by
Proof. For the proof, cf. Supplementary Material D.
Discussion. Monotonicity is highly desirable as otherwise adverse effects such as an input requiring to be decreased increase the output can occur. In gradient-based based training, non-mononicity is problematic as it produces gradients with the opposite sign. In addition, as monotonicity is also given hard sorting networks, is desirable to preserve this property in the relaxation. Further, monotonic differentiable sorting networks are quasiconvex and quasiconcave as any monotonic function is both quasiconvex and quasiconcave, which leads to favorable convergence rates [6]. Bounding and reducing the deviation from its hard counterpart reduces the relaxation error, and thus is desirable.
4.2 SIGMOID FUNCTIONS
Above, we have specified the space of functions for the differentiable swap operation, as well as their desirable properties. In the following, we discuss four notable candidates well as their properties. The properties of these functions are visualized in Figures and 3 and an overview over their properties is given in Table 1.
Logistic distributions. The first candidate is the logistic sigmoid function (the CDF of a logistic distribution) proposed in [4]:
1
CDF e (3x) 1 Bm
(10)
This function is the de-facto default sigmoid function in machine learning. It provides continuous, error-bounded, and Lipschitz continuous conditional swap. However, for the logistic function, monotonicity not given, displayed in Figure 2.
5

---

Published as a conference paper at ICLR 2022
Table For each function, we display the function, its derivative, and indicate whether the respective relaxed sorting network is monotonic and has bounded error.
Function
f (CDF)
f' (PDF)
Eq.
Mono.
Bounded Error
(10)
x
(~ .0996/o)
fR
(11)
V (1/44/0)
fc fo
(12) / (11/52/0)
(13) / o (L/116/a)
Reciprocal Sigmoid Function. To obtain a function that yields monotonic well as error- bound differentiable sorting network, a necessary criterion is fxxx) E @(1/²²) (the intersection of Equations 5 and 8.) A natural choice is, therefore. fk(2) (x) [1]+++1]= which produces
1 (R(x) - (2 + 1)2
2/xz
dt 21 23
(11)
2
fR fulfills all criteria, i.e., it an adequate sigmoid function and produces monotonic and error-bound conditional swaps. It has an e-bounded-error of e = 0.25. It is also an affine transformation of the elementary bipolar sigmoid function x + | Properties of this function are visualized in Table 1
and Figures 2 and 3. Proofs for monotonicity can be found in Supplementary Material D.
Cauchy distributions. By using the CDF of the Cauchy distribution, we maintain montonicity while reducing the error-bound to = 1/m²3 ss 0.101. It is defined as
fc(2) CDF (Bx) /
B
(B1jz dl arctan (3x)
(12)
In the experimental evaluation, we find that tightening the error improves the performance.
Optimal Monotonic Sigmoid Function. At this point, we are interested in the monotonic swap operation that minimizes the error-bound. Here, set 1-Lipschitz continuity again requirement to make different relaxations of conditional swaps comparable. We show that fo is the best possible sigmoid function achieving an error-bound of only e 1/16
Theorem 10 (Optimal Sigmoid Function). The optimal sigmoid function minimizing the error-bourd bound, while producing monotonic and 1-Lipschitz continuous (with 1) conditional swap operation,
Br < 1.
1632
fo(x)
1
1 168
if +
(13)
Br + 1
otherwise.
Proof. Given the above conditions, the optimal sigmoid function is uniquely determined and can easily be derived as follows: Due to stability. it suffices to consider min, 0) = x f(-z) or marr x) = = fx)). Due to symmetry and inversion, it suffices consider miny 0) x f(-x) for > 0.
Since min 0) = 0 for > 0, we have to choose ff in such a way as to make min (2, = x(=x) as small as possible, but not negative. For this, f(-z) must be made as small as possible. Since we know that f())) = and we are limited to functions that are Lipschitz continuous with a = 1, f(-z) cannot be made smaller than 1/ - x, and hence miny( (x, 0) cannot be made smaller than x. (1 w). To make (I, 0) as small as possible, we have to follow x- x) as far as possible (i.e., to values I as large as possible). Monotonicity requires that this function can be followed only up to = 1. at which point we have min (1. 0) 1/ ( 1) 1 For larger æ, that is. for x > 4.
To
the value of x (1 .r) decreases again and hence the functional form of the sigmoid function has to change at ī to remain monotonic.

---

Published as a conference paper at ICLR 2022
The best that can be achieved for 1 is to make it constant, it must not decrease (due to monotonicity) and should not increase (to minimize the deviation from the crisp / hard version). That is, m 0) TE for 4. It follows x f(-z) To and hence f(-z) _ for x: > 7. Note
The
that, if the transition from the linear part to the hyperbolic part were |ar 1. the function would
not be Lipschitz continuous with = 1.
An overview of the selection of sigmoid functions we consider is shown in Table 1. Note how fR. Je and fo in this order get closer x + 2 (the gray diagonal line) and hence steeper in their middle part. This is reflected by a widening region of values of the derivatives that are close to or even equal to 1.
Table also indicates whether a sigmoid function yields a monotonic swap operation or not, which is vi- sualized in Figure clearly o-based sorting networks 0.2 are not monotonic, while all others are. It also states whether the error bounded, which for monotonic swap operation means limz-too min (xx 0) < co, and gives their bound relative to the Lipschitz con- stant a.
fR.
fc
0.1
fo
0
1/2
Figure displays the loss for a sorting network with inputs. We project the maxagon-shaper 3-value permutahedron onto the z-y-plane, while the z-axis indicates the loss. Note that, at the rightmost point
Figure 2: min (r. 0) for different sigmoid
functions f; color coding in Table 1.
21,2,3, 3), the loss is 0 because all ele- ments are in the correct order, while at the left front (2,3, 1) and rear (3, 2) the loss is at its maximum because all elements
80
12
at the wrong positions. Along the red center line, the loss rises logarithmic for the optimal sigmoid function on the right. Note that the monotonic sigmoid functions produce a loss that is larger when more ele- ments are in the wrong order. For the logistic function, (3, 2, 1) has the same loss as (,, 1) even though one of the ranks is correct at (3, 2, 1), while for (2, 3, 1) all three ranks are incorrect.
60
12.1.3)
11,,21
11.
2321111
(1,3,21
(2.3
Figure 3: Loss for a 3-wire odd-even sorting network, drawn over permutahedron projected onto the x-y-plane. For logistic sigmoid (left) and optimal sigmoid (right).
5 MONOTONICITY OF OTHER DIFFERENTIABLE SORTING OPERATORS
For the special case of n = 2, i.c., for sorting two elements, NeuralSort [1] and Relaxed Bubble sort [10] are equivalent to differentiable sorting net- works with the logistic sigmoid function. Thus, it is non-monotonic, as displayed in Figure 4.
0.10
Sinkhamn
NeuralSort
Relaxed Bubble
Lngistic
Logistic w/ WAT
0.05-
FustSort
For the Sinkhorn sorting algorithm [2], can sim- ply construct an example of monotnnotyy by keeping one value fixed, c.g., at zero, and varying the second value (I)) as in Figure 4 and displaying the minimum. Notably, for the case of function is numerically equal to NeuralSort and differ- entiable sorting networks with the logistic function.
1/2
3/2
2
2, this
Figure 4: min(x, 0) for Sinkhorn sort (red), NeuralSort (red), Relaxed Bubble sort (red), diffsort with logistic sigmoid (red), diffsort with activation replacement trick (purple), and Fast Sort (orange).
For fast sort [3], we follow the same principle and find that it is indeed monotonic (in this example); however, the emoor is unbounded, which is undesirable.
For differentiable sorting networks, Petersen el al. [4] proposed to extend the sigmoid function by the
7

---

Published as a conference paper at ICLR 2022
activation replacement trick, which avoids extensive blurring as well as vanishing gradients. They ap- ply the activation replacement trick to before feeding the values into the logistic sigmoid function; thus, the sigmoid function is effectively a s. Here, p + lx|* where À E [0, 1] and e x 10 Here, the asymptotic character of ip does not ful- fill the requirement set by Theorem 5, and is thereby non-monotonic as also displayed in Figure (purple).
Table 2: For each differentiable sorting opera- tor, whether it is monotonic (M), and whether it has a bounded error (BE).
Method
M
BE
NeuralSort
X
Sinkhorn Sort
X
Fast Sort
V
X
Relaxed Bubble Sort
X
Diff. Sorting Networks a
X
V
We summarize monotonicity and error- bruudebuuddeess for all differentiable sorting functions in Table
Diff. Sorting Networks
a o
X
Diff. Sorting Networks
fR
/
Diff. Sorting Networks fc
/
6 EMPIRICAL EVALUATION
Diff. Sorting Networks fo
/
To evaluate the properties of the proposed function as well as their practical impact in the context of sorting supervision, we evaluate them with respect to two standard benchmark datasets. The MNIST sorting dataset [1]-[4] consists of images of numbers from 0000 to 9999 composed of four MNIST digits [7]. Here, the task is training network to produce scalar output value for each image such that the ordering of the outputs follows the respective ordering of the images. Specifically, the metries here are the proportion of full rankings correctly identified, and the proportion of individual element ranks correctly identified [1]. The same task can also be extended to the more realistic SVHN [19] dataset with the difference that the images already multi-digit numbers shown in [4].
Comparison to the State-of-the-Are the-art approaches using the same network architecture and training setup used in previous works, as well as among themselves. The respective hyperparameters for each setting can be found in Supplementary Material A. We report the results in Table 3. The proposed monotonic differentiable sorting networks outperform current ofte-offthhe-at methods by considerable margin. Especially for those cases where more samples needed to be sorted, the gap between monotonic sorting nets and other techniques grows with larger The computational complexity of the proposed method depends on the employed sorting network architecture leading to a complexity of O(n)) for odd-even networks and a complexity of On2 log" n) for bitonic networks because all of the employed sigmoid functions can be computed in closed form. This leads to the same runtime as in [4].
We first compare the proposed functions to other state-of-
Comparing the three proposed functions among themselves, we observe that for odd-even networks on MNIST, the error-optimal function fo performs best. This is because here the approximation error small. However, for the more complex bitonic sorting networks, fc (Cauchy) performs better than fo- This is because fo does not provide higher-order smoothness and is only C' smooth, while the Cauchy function fc is analytic and O smooth.
Table 3: Results on the four-digit MNIST and SVHN tasks using the same architecture as previous works [1]-[4) The metric is the proportion of rankings correctly identified, and the value in parentheses is the proportion of individual element ranks correctly identified. All results are averaged over 5 runs. SVHN w/ n 32 omitted reduce the carbon impact of the evaluation.
MNIST
=
==
==7
15
= 32
16 (bitonic)
N = 32 (bitonic)
NeuralSort
91.9 (94.5)
77.7 (90.1)
61.0 (86.2)
43.4 (82.4)
9.7 (71.6)
0.0 (38.8)
Sinkhorn Sort
(95.0)
81.1 (91.7)
65.6
19.7 (1.7)
12.6 (712)
(11.2)
Past Sort & Rank
00.6
(17.2
49.7 (81.3)
29.0 (75.2)
2.8 (G0.9)
Diffsort logistic)
02.0 (94.5)
77.2 (89.8)
54.8 (83.6)
37.2 (7..4)
4.7 (62.3)
0.0 (56.3)
10.8 (72.6)
0.3 (63.2)
Dillson: (Log. w/ ART)
94.3 (96.1)
83.4 (92.6)
71.6 (90.0)
56.3 (86.7)
23.5 (79.4)
0.5 (64.9)
19.0 (77.5)
0.8 (63.0)
fa: Reciprocal Sigmoid
91.4(96.11
85.0 (93.3)
73.4 (90.7)
60.8 (88.1)
30.2 (81.9)
1.0 (66.8)
28.7 (82.
1.3 (08.0)
fe: Cauchy CDF
91.2 (96.0)
84.9 (93.2)
73.3 (90.5)
63.8 (89.1)
31.1 (82.2)
0.8 (63.3)
29.0 (82 1)
1.6 (G8.
fo Optimal Sigmoid
94.6 (96.3)
85.0 (93.3)
73.6 (90.7)
62.2 (88.5)
31.8 (82.3)
1.4 (67.9)
28.4 (81.9)
(07.7)
SYHN
==
=
16 (bitonic)
Diflsort (Logistic)
76.3 (83.2)
46.0 (72.7)
21.8 (63.9)
13.5 (61.7)
0.3 (45.9)
1.2 (50.6)
Diffsort (Log. w/ ART)
83.2 (88.1)
64.1 (82.1)
43.8 (76.5)
21.2 (89.6)
2.4 (56.8)
3.4 (59.2)
fa. Reciprocal Signooid
85.7 (89.8)
68.8 (84.2)
53.3 (80.0)
40.0 (76.3)
13.2 (66.0)
11.5 (64.9)
fo: Cauchty CDF
85.5 (89.6)
68.5 (84.1)
52.9 (70.8)
39.9 (75.8)
13.7 (66.0)
12.2 (65.6)
fo: Optimal Sigmoid
86.0 (90.0)
67.5 (83.5)
53.1 (80.0)
39.1 (76.0)
13.2 (66.3)
10.6 (66.8)
8

---

Published as a conference paper at ICLR 2022
0.825
0.815
0.956
0.805
0.054
0.80
0.95
0.75
Logletic
Logistic
R-3 Logietic wr ART
1- Logistic wi ART
|eccprocalf
15 Reciprocal
0..0
Eauchy
Cauchy
2-3 1.00mmal f.
7- 15 Optimall
0.66
0.66
MWN
0.54
0.64
0.00
0.60
10.07.0 Logiatic
32 Logisiic
81 12 Logietic w/ ART
n= 12 Logietic w/ ART
Rediprocal
Redppoccal
Cauchly
Cauchy
-0-0. 2--0---3 S..Dpimmma
20.-2---22222 Pa0-Spiimall fa
Figure 5: Evaluating different sigmoid functions on the sorting MNIST task for ranges of different inverse temperatures B. The metric is the proportion individual element ranks correctly identified. In all settings, the monotonic sorting networks clearly outperform the non-monotonic ones. Top: Odd-Even sorting networks with
(left) and 15 (right). Bottom: n 32 with an Odd-Even (left) and a Bitonic network (right). For small such as 3, Cauchy performs best because it has a low error but is smooth at the same time. For larger n, such as 15 and 32, the optimal sigmoid function (wrt. error) So performs better because it, while not being smooth, has the smallest possible approximation error which is more important for deeper networks. For the bitonic network with its more complex structure at 32 (bottom right), the reciprocal sigmoid fR performs best.
Evaluation of Inverse Temperature 8. To further understand the behavior of the proposed mono- tonic functions compared to the logistic sigmoid function, we evaluate all sigmoid functions for different inverse temperatures B during training. We investigate four settings: odd-even networks for E {3, 15, 32} and a bitonic sorting network with n 32 on the MNIST data set. Notably, there are 15 layers in the bitonic sorting networks with 32, while the odd-even networks for n 15 also has 15 layers. We display the results of this evaluation in Figure 5. In Supplementary Material C, we show an analogous figure with additional settings. Note that here, we train for only 50% of the training steps compared to Table 3 to reduce the computational cost.
We observe that the optimal inverse temperature depends on the number of layers, rather than the overall number of samples n. This can be seen when comparing the peak accuracy of each function for the odd-even sorting network for different n and thus for different numbers of layers. The bitonic network for 32 (bottom right) has the same number of layers (top right). Here, the peak performances for each sigmoid function fall within the same range, whereas the peak performances for the odd-even network for 32 (bottom left) shifted almost order of magnitude to the right. For all configurations, the proposed sigmoid functions for monotonic sorting networks improve over the standard logistic sigmoid function, well as the ART.
15 in the odd-even network
The source code of this work is publicly available at
7 CONCLUSION
In this work, addressed and analyzed monotonicity and error-boundness in differentiable sorting and ranking operators. Specifically, we focussed on differentiable sorting networks and presented a family of sigmoid functions that preserve monotonicity and bound approximation errors in differen- tiable sorting networks. This makes the sorting functions quasiconvex, and we empirically observe that the resulting method outperforms the state-of-the-art in differentiable sorting supervision.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS & FUNDING DISCLOSURE
We warmly thank Robert Denk for helpful discussions. This work was supported by the Goethe Center for Scientific Computing (G-CSC) at Goethe University Frankfurt, the IBM-MIT Watson AI Lab, the DFG in the Cluster Excellence EXC 2117 "Centre for the Advanced Study of Collective Behaviour" (Project-ID 390829875), and the Land Salzburg within the WISS 2025 project IDA-Lab (20102-F1901 166- and 20004-WSS7725/97222009
REPRODUCIBILITY STATEMENT
We made the source code and experiments of this work publicly available at corfFb.com/Felix Petersen/diffsort to foster future research in this direction. All data sets are publicly available. We specify all necessary hyperparameters for each experiment, We use the same model architectures as in previous works. We demonstrate how the choice of hyperparameter 3 affects the performance in Figure 5. Each experiment can be reproduced on single GPU.
REFERENCES
[I] A. Grover, Wang, A. Zweig, and S. Ermon, "Stochastic Optimization of Sorting Networks via Continuous Relaxations," International Conference on Learning Representations (ICLR), 2019.
[2] M. Cuturi, O. Teboul, and J.-P. Vert, "Differentiable ranking and sorting using optimal transport," in Proc. Neural Information Processing Systems (NewrIPS). 2019.
[3] M. Blondel, O. Teboul, Q. Benthet and J. Djolonga, "Fast Differentiable Sorting and Ranking," in Proc. Machine Learning Research (PMLR), International Conference on Machine Learning (ICMI.), 2020.
[4] F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen, "Differentiable sorting networks for scalable sorting and ranking supervision." in Proc. Machine Learning Research (PMLR), International Conference on Machine Learning (ICMI), 2021.
[5] D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Ed.) Addison Wesley, 1998.
[6] K. C. Kiwiel, "Convergence and efficiency of subgradient methods for quasiconvex minimization,"
Mathematical Programming, vol. 90, 2001.
[7] Y. LeCun, C. Cortes, and C. Burges, "Mnist handwritten digit database," 2010. [Online]. Available: Lecun com/ ex /nbb/tni.t.....
http://yame Lecunn
[8] G. Mena, D. Belanger. S. Linderman, and J. Snoek, "Learning latent permutations with gumbel-sinkhom
networks," International Conference on Learning Representations (ICLR). 2018.
[9] M. Cuturi, "Sinkhorn distances: Lightspeed computation of optimal transport," in Proc. Neural Informa-
tion Processing Systems (NeurIPS), 2013.
[10] F. Petersen, C. Borgelt, Kuchne, and O. Deussen, "Learning with algorithmic supervision via continu- ous relaxations," in Proc. Neural Information Processing Systems (NeurIPS), 2021.
[11] Lee. Cho. Jang, J. Kim, H. Woo, "Differentiable ranking metric using relaxed sorting for top-k recommendation," IEEE Access, 2021.
[12] R. Swezey, A. Grover, B. Charron, and Ermon, "Pirank: Learning to rank via differentiable sorting," "
in Proc. Neural Information Processing Systems (NeurIPS), 2021.
[13] J.-B. Cordonnier, A. Mahendran, A. Dosovitskiy, D. Weissenborn, J. Uszkoreit, and T. Unterthiner, "Differentiable patch selection for image recognition," in Proc. International Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
[14] Y. Xie, H. Dai. M. Chen, B. Dai, T. Zhao, H. Zha, W. Wei, and T. Pfister, "Differentiable top-k with optimal transport," in Proc. Neural Information Processing Systems (NeurIPS), 2020.
[15] K. Goyal, G. Neubig, C. Dyer, and T. Berg- Kirkpatrick, "A continuous relaxation of beam search for end-to-end training of neural sequence models," AAAI Conference Artificial Intelligence, 2018.
[16] A. N. Habermann, "Parallel neighbor-sort (or the glory of the induction principle)." 1972.
[17] K. E. Batcher, "Sorting networks and their applications," in Proc. AFIPS Spring Joint Computing
Conference (Atlantic City, NJ). 1968, pp. 307-314
[18] I. J. Goodfellow, J. Pbadet-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y.
Bengio, "Generative adversarial networks." in Proc. Neural Information Processing Systems (NeurlPS), 2014.
[19] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. "Reading digits in natural images with unsupervised feature learning." 2011.
10

---

Published as a conference paper at ICLR 2022
[20] D. Kingma and J. Ba, "Adam: A method for stochastic optimization," in International Conference Learning Representations (ICLR), 2015.
[21] 1. Goodfellow. Y. Bulatov. J. Ibarz, S. Arnoud, and Shet, "Multi-digit number recognition from
street view imagery using deep convolutional neural networks," " Computing Research Repository (CoRR) in arXiv, 2013.

---

Published as a conference paper at ICLR 2022
A IMPLEMENTATION DETAILS
For training, we the same network architecture in previous works [1], [2], [4] and also use the Adam optimizer [20] at a learning rate of 3 10 For Figure 5, we train for 100 000 steps. For Table we train for 200 000 steps on MNIST and 000 000 steps SVHN. We preprocess SVHN as done by Goodfellow et al. [21].
A.1 INVERSE TEMPERATURE |
For the inverse temperature 8, we use the following values, which correspond to the optima in Figure and were found via grid search:
Method
3
5
7
9
15
32
16
32
odd-even/ bitonic
oe
de
0e
0c
0c
oc
Logistic
79
30
33
54
32
128
0 O
Log. w/ ART
15
20
13
34
16
29
28
26
fR.
Reciprocal Sigmoid
14
60
69
44
120
1140
124
76
fc
Cauchy CDF
14.5x
51m
71
15x
40
169T
12x
48.5x
45.6
160.2
223.
47.1
125.7
531.0
37.7
152.4
fo Optimal Sigmoid
6
20
29
32
25
124
25
B PROPERTIES OF min AND max
The core element of differentiable sorting networks is the relaxation of the conditional swap operation, allowing for a soft transition between passing through and swapping, such that the sorting operator becomes differentiable. It is natural to try to achieve this by using soft versions of the minimum (denoted by min) and maximum operators (denoted by mar). But before we consider concrete examples, let collect some desirable properties that such relaxations should have. Naturally, min and mar should satisfy many properties that their crisp / hard counterparts min and max satisfy, as well as few others (for a, b,c IR)::
Symmetry/ / Commutativity. Since min and max are symmetricccommuttivvc, so should be their soft counterparts: (a, b) min a) and mar(a, b) mar a).
Ordering. Certainly (soft) maximum of two numbers should be at least as large as (soft) minimum of the same two numbers: min b) < max a).
Continuity in Both Arguments. Both min and maz should be continuous in both arguments.
Idempotency. If the two arguments are equal in value, this value should be the result of min and mar, that is, mén(a, a) mar (a, a)
Inversion. As for min and max, the two operators min and max should be connected in such way that the result of operator equals the negated result of the other operator applied negated arguments: min(a, b) mar a, -b) b) and mar(a, (a, b) min( a, -b).
Stability/ Shift Invariance. Shifting both arguments by some value R should shift each operator's s result by the same value: min(a + c, b + c) min(a, b) - and max(a + c, + mar(o (a, b) + c. Stability implies that the values of min and mar depend effectively only on the difference of their arguments. Specifically, choosing
yields min(a, b) min b a)
and max (a. b) = maz(O. max (a, b) mar(a- b. 0) b.
a) + a, and c = -b yields min(a, = min(a - b, 0) + and
12

---

Published as a conference paper at ICLR 2022
Sum preservation. The sum of min and maz should equal the sum of min and max: min(a, b) mar (a, b) = min(a, b) + max(a, b) = a + b. Note that sum preservation follows from stability, inversion and symmetry: min(a, b) min (a (alaa---a b, +b b- maz (0, b- a) b- b-(maz(a, b)a) a + b max (a, b)
Bounded by Hard Versions. Soft operators should not yield values more extreme than their crisp / hard counterparts: min b) I min(a, b) and mar b) I max(a, b). Note that together with ordering this property implies idempotency, vi7.: a = min(a, a) I min(a, a) S mar a) S max(a, a) = a. Otherwise, they cannot be defined via convex combination of their inputs, making impossible to define proper arymin and arymar, and hence we could not compute differentiable permutation matrices.
Monotonicity in Both Arguments. For any > 0, it should be min(a + +.c. 2 min(a, b). min(a, b c) 2 min(a, b), max(a + b) 2 max (a, and mar(a, b b c) 2 mar(a, b). Note that the second expression for each operator follows from the first with the help of symmetry / commutativity.
Bounded Error / Minimum Deviation from Hard Versions. Soft versions of minimum and maximum should differ as little as possible from their crisp hard counterparts. However, this condition needs to be made more precise to yield concrete properties (see below for details).
Note that min and max cannot satisfy associativity, as this would force them to be identical to their hard counterparts. Associativity means that mar(a, max(b, c)) = maz mmzzmarra (a, b), c) and min( (a, min c)) = min (min (a, b), c). Now consider a, 6 with a < b. Then with associativity and idempotency mar (a, mar (a, b)) max (maz(a, a), b) mar (a. b) and hence mar(a, b) b = max(a, b) (by comparison of the second arguments). Analogously, one can show that associativity held, would have min(a, b)
min(a, b). That is, one cannot have both associativity and idempotency. Note that without idempotency, the soft operators would not be bounded by their hard versions. As idempotency is thus necessary, associativity has to be given up.
If min and mar are to be bounded by the crisp / hard version and symmetry, ordering, inversion and stability (which imply sum preservation) hold, they must be convex combinations of the arguments and b with weights that depend only on the difference of and b. That is,
min(a, b) = mar(a, b) f1- a)) a f(b a) b,
f(b- - a) a + (1 - fl-f(b- a))
where f(x) yields a value in [0, 1] (due to boundedness of min and max by their crisp / hard counterparts). Due to inversion, f must satisfy fxx = 1 f(=x) and hence f(0) = 2- Monotonicity of min and maz requires that f is monotonically increasing function. Continuity requires that is a continuous function. summary, f must be continuous sigmoid function (in the older meaning of this term, i... s-shaped function, of which the logistic function is only special case) satisfying (z) = f(-x).
As mentioned, the condition that the soft versions of minimum and maximum should deviate as little as possible from the crisp hard versions causes a slight problem: this deviation can always be made smaller by making the sigmoid function steeper (reaching the crisp hard versions in the limit for infinite inverse temperature, when the sigmoid function turns into the Heaviside step function). Hence, in order to find the best shape of the sigmoid function, we have limit its inverse temperature. Therefore, w.l.o.g., we require the sigmoid function to be Lipschitz-continouus with Lipschitz constant a
C ADDITIONAL EXPERIMENTS
In Figure 6, we display additional results for more setting analogous Figure 5.
13

---

Published as a conference paper at ICLR 2022
0.890
0.950
0.528
0.924
0.92
0.95
0.90
Logietic
Logletic
Logietic
2- Reciprocal
R=5 Recppocall Ea
Courhy
Cauchy
Optimal
Optimal
5
107
10a
0.9050
0.885
3,9025
0.880
3.8950
0.85
Logietic
Logletic
Logletic
8-7 Raciprocal
0-9 Recorocal
Cauchyy
Cauchy f.
Optimal
10
3
10a
101
107
10*
0.825
0.58
0.830
MWN
0.80
0.75
Logistic
Logistic
6- Rederocal
- Rediprocal fg
Cauchy
-1 Cartchty
Optimal
Optttmal
101
3
10a
10>
1.-
0.815
0.68
0.66
0.805
0.80
0.75
0.77
Logistic
LogizlE
-- 18 Reciprocal
-0 a- 32 Reciprocal
Cauchy
Cauchy
Optimal
Optiinal
207
107
10a
Figure 6: Additional results analogous to Figure 5. Evaluating different sigmoid functions on the sorting MNIST task for ranges of different inverse temperatures B. The metric the proportion of individual element ranks correctly identified. In all settings, the monotonic sorting networks clearly outperform the non-monotonic ones. The first three rows odd-even networks with n E {3, 5, 7, 9, 15, 32). The last row uses bitonic networks with n E {16, 323.
14

---

Published as a conference paper at ICLR 2022
D ADDITIONAL PROOFS
Theorem (Error-Bounde of Diff. Sorting Networks). the ervor of individual conditional swaps of a sorting network is bounded by and the network has E layers, the total error is bounded by f.
Proof. Induction over number k of executed layers. Let x: (R) be input differentially sorted for ls layers and !kk) be input x hard sorted for k layers as an anchor. We require this anchor, as it is (k)
possible that (1) <x, but (k)
(k) for some j, k.
> x
Begin of induction: & = O. Input vector x equals the vector (0)) after 0 layers. Thus, the error is equal to 0-
Step of induction: Given that after layers the error is smaller than or equal to (k 1]e, we need to show that the error after A layers is smaller than equal to kc.
The layer consists of comparator pairs i.j. W.l.o.g. we assume x ((-11) (k-1)
W.l.o.g. we assume
that wire i will be the min and that wire j will be the max, therefore x; S x (k) This implies x ((-11) x
(k) and x (k-11) (h) We distinguish two cases:
x 1 S x (k-1) and ii
1k-1) S 2 ()-
According to the assumption, | (1( -x² (16) S and
lyy (k-1) - x S E. Thus, x - -x; (k)
[k)
(k)
S |
(k-1)
x; (k (k-1)) + +|
2; S - 11)=-) = ke.
(x(t) s x but x;
11- > xÿ 1)
This case can only occur if (a - -x(x x S
(k - 1)e and |بح ( xj (k-1) I (k: - 1)e because x (k-1) and xj (k-1) have to be so close that within
margin of error such a reversed order is possible. According to the assumption, [z) (k-1) -x: (k) I and
| (k-1) [ S Thus, | (k) (k) < 12 (k-1) x; 11+ 1 (k-1) (k) I (k - 1)e+e = ke.
Theorem 11. minse and fax are monotonic functions with the sigmaid function fR.
Proof. Wlog., we assume a; and 0j- = O.
1 x
+1)
min (x. 0) = x. (R(- = 222
(14)
1 |x|
To show monotonicity, consider its derivative slope.
d
min fr (x, 0)
d
1
x
+ 1
(15)
dx
dr
2
1
+
[
1
1 d
+ 1
+
1 [ + 1
(16)
2
+
2 dr
1
T
1 d
(
+1
+ x 2 dr
(17)
2
+
[x||
(1 |x|
2
1
+
I
[x|
x
2
1
de
de
(1 + (x:) - x
(1+ |x|)
dz
dr
(18)
1
x
1 (1 + [o:))
x sgn(1)) (x:)
+1
+
(19)
2
1+ [
2
(1 + [x |
1
11 + |x|| [0||
+1
+ 2
(20)
2
1+
[x|
(1 1+
xx))
15

---

Published as a conference paper at ICLR 2022
1
+1
+
T
(21)
2
1 [
2 + 2/ + 1x72
1
x
+ +1+
(22)
2
1+ [0]
1 + 2/ + |x|
1
x11 + [x])
1 2
+ |x
+
(23)
2
1 2//
+ |z|
1+
+ |x
+ 2/z) + |x/
1
2r + 2/2| + + 1 +1
(24)
2
1 2|
2(x + [x)) + (x [x) +
(25)
2
1 2/x]
+ |0|2
1
(because r + |-| 11200 0)
(26)
2
1 2/xz
+ +
> 0
(27)
m is analogous.
Theorem 12. minse and maxfe are monotonic functions with the sigmoid function Sc-
Proof. Wlog., we assume a; = x and 02 =
( (arctan(-888 2)
2)
màn fe (s, 0) sc(-=)= =
(28)
To show monotonicity, we consider its derivative.
i
① min (0, x) (Je(-x) =x005c(-10)
0
0
x. sc(-x) Sc(c-())
dr
Ox 2x0
Ox x
0
1
1
x Or
arctan(- (aannn-Brr) Br) + 2)
+
arctan -Bx) +
π
2
1
-B
1
1
arctan (3z)
+
+ (Bx)²
π
2
1
1
Dx
arctan(3x)
+ (Bx)²
π
arctan(z)
1 x² (with 2 = Bz)
(29)
2
π
To reason about the derivative, also consider the second derivative:
lim 20000 2
1 1
arctan(2)
1
z
lim lim arctan(z)
1 2
11
2
20000
1 x²
1
n
-0=0 0
(30)
2
2
1 2
1 2
lim -aretan
lim
- *arctan(2)
lim
2- 00 2
1 z2
2
2--
= π
1 z2
1- π
1 - 0 0=
0 =
(31)
2
2
2 2
For E (-o0, 0]: The derivative of min (0, x) converges to for 2 - oc (Eq. 31).
For 2 E co): The derivative of min je (0, æ) converges to 0 for + xc (Eq. 30).
0 1
2 711 + 22)2 < 0
arctan(2 22) 111+
(32)
0= 2
The second derivative (Eq. 32) of min fo (0,xr) xx) is always negative.
Therefore, the derivative is always in (0, 1), and therefore always positive. Thus, min (0, x) is strictly monotonic. maxfe is analogous.
16

---

Published as a conference paper at ICLR 2022
E ADDITIONAL DISCUSSION
"How would the following baseline perform? Hard rank the predictions and compare it with the ground truth rank. Then, use their difference as the learning signal (i.e., instead of the gradient)."
This kind of supervision does not converge, even for small learning rates and in simplified settings. Specifically, we observed in our experiments that the range of values produced by the CNN gets compressed heavily by training in this fashion. Also counteracting it by explicitly adding term to spread out again did not help, and training was very unstable. Despite testing various hyperparameters (learning rate, adaptation factor, both absolute and relative to the range of values in a batch in the whole data set, spread factor, etc.) it did not work, even on toy data like single-digit MNIST with n 5.
"Could 3 be jointly trained as purameter with the model?"
Yes, it could; however, in our experiments, we found that the entire training performs better is fixed. If B is also parameter to be trained, its learning rate should be very small as it (i) should not change too fast and (ii) already accumulates many gradient signals as it is used many times.
17


Reviews:
[{"review_id": "y1M-Ykfvjqz", "reviewer": "Reviewer_28Ue", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "First of all, I want to say that I am not an expert on differentiable sorting and so my opinion reflects the one from a novice but curious reader.\n## Pros\n- The idea of enforcing monotonicity is sound.\n- Empirical results demonstrate a real gain from using monotonic sorting networks.\n\n## Cons\n- Overall, I have the feeling this paper was written in a rush. Section 4 is not very readable as it is just a series of theorems and proofs without any flow between them. Proofs are also very poorly shaped and sometimes does not seem very rigorous (e.g. proof of theorem 5 is missing some strict logical relationships between some steps). Moreover, as a novice it quite difficult to understand how Figure 5 should be analysed, and the long caption does not help much.\n- You provide some necessary conditions for monotonicity but not any sufficient one. And you do not prove explicitly that the functions you introduced are monotonic.\n- It is not very clear to me why you introduce Fc and Fr. \n- As fast sort is monotonic as well why doesn't it work better?\n- What are the missing entries in table 3?\n- Quasi convexity is mentioned once in the intro and second time in the conclusion but never elsewhere. This contributed to my feeling that the paper was not well polished. Maybe this is something that could be stated more explicitly and motivated somewhere in the section 4 or 5?\n## Additional remarks:\nShouldn't P in Figure 1 be doubly stochastic? (second columns does not sum up to 1).", "summary_of_the_paper": "This paper presents monotonic differentiable sorting networks. It argues that monotonicity is lacking in most differentiable sorting networks whereas this may lead to incorrect gradient signs and inconsistent outputs. The first part of the paper motivates the problem and provides a brief review of other differentiable sorting networks. Then the paper provides a necessary condition for monotonicity and study bounds on the error of continuous conditional swaps. Finally, experiments demonstrate that monotonic swaps outperform non-monotonic ones for training a network to order MNIST, especially on larger numbers. ", "summary_of_the_review": "I believe the idea proposed in this paper is interesting. However, the paper presentation should be improved and further discussion is required to make it a strong paper.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "x5EEbcxgSJ", "reviewer": "Reviewer_iDKW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Overall I think this is a good paper that should be accepted, as it presents a well motivated idea, contains strong theoretic results and supports their usefulness by improved experimental results on an existing problem setting (sorting images of numbers).\n\n*Strengths*\n- This paper presents a well motivated idea\n- The paper is well structured and contains strong theoretical results\n- Clear figures are very helpful for understanding the differences to other sigmoid functions\n- Empirical results illustrate the improved performance gained from monotonicity\n- Sensitivity to hyperparameter Beta and choice of sigmoid functional form is clearly illustrated, which shows monotonic networks clearly outperform non-monotonic alternatives.\n\n*Weaknesses*\n- The paper is a bit math heavy, which does hurt the flow of reading the paper a bit. I think some proofs could be deferred to the appendix, which would improve the overall readability of the paper.\n- The experimental section is a bit limited as it only considers a sorting task. Related works consider additional experimental settings, for example quantile regression (Grover et al. 2019), which I think could also serve as a good test for this model.\n\n*Minor comments/questions*\n- Using italic vs roman font to distinguish relaxations can be confusing when skimming the paper. Maybe consider (additionally) using different names for the function. Maybe use the subscript min_sigma(a,b) in Eq. (1)?\n- I am not sure, but do we need differentiability at all for the sorting task? I am curious how the following baseline would perform: simply sort the predictions and compare the rank with the ground truth rank and use their difference as learning signal ('gradient') for each item? It is obviously biased but it provides the correct direction, so in a sense is similar to monotonic differentiable sorting? (maybe this has already been tried or I'm missing something here)\n- I'm a bit confused by 'for beta = 1' in Theorem 10, while beta appears in Eq. (13).\n- In Figure 5, why are different ranges for Beta displayed for different functions? This would be good to clarify since (unlikely but in theory) the missing parts can change the picture. Also, given the explanation in the text, I suggest to align the horizontal axes so the figures can be compared.\n", "summary_of_the_paper": "This paper proposes sigmoidal functions f for which, roughly speaking, x * f(-x) is non-decreasingly monotonic and bounded from above (this does not hold for the standard sigmoid). These are used to define continuous relaxations of min and max operations (not to confuse with softmax which is a relaxation for argmax) which are monotonic in their inputs.\n\nBy stacking multiple layers of these 'monotonic continuous conditional swaps' the authors obtain a sorting network for which all outputs are monotonic in all inputs. This ensures that the gradient is in the right direction when training a sorting network to sort data using only ground truth order.\n\nExperiments on sorting 4-digit MNIST numbers or SVHN  show that the resulting network is able to predict the order more accurately than a number of alternatives, especially non-monotonic differentiable sorting networks.", "summary_of_the_review": "This paper is a strong theoretic paper that proposes to replace the sigmoid function in differentiable sorting networks by one such that the network becomes monotonic and has bounded error, which guarantees the correct gradient direction when training sorting networks. Empirical results show the effectiveness on the task of sorting 4-digit MNIST numbers and SVHN.\n\nWhile I think some additional experiments could be performed, I think this paper should be accepted given the well motivated idea, strong theoretical results, clear presentation illustrated by figures and the resulting empirical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uuKDCCaZRJ2", "reviewer": "Reviewer_vsFK", "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": "The paper presents an overview of differentiable sorting networks and the construction of soft min/max functions used in the swap operator. It follows that the construction of such operators need to follow a specific functional form, requiring the use of a generic sigmoid function. The paper presents a set of theorems to show that the derivative of this sigmoid function should be $\\Omega(1/x^2)$ to guarantee end-to-end monotonicity, and should be $O(1/x^2)$ to guarantee end-to-end bounded error. A monotonic sorting network can be more easily trained (better behaved objectives) and has better logical consistency.\n\nThe paper introduces 3 candidates for the sigmoid functions that satisfy the conditions above. There is a limited set of experiments on multi-digit image ordering tasks constructed from MNIST and SVHN that show the new candidate sigmoids match or outperform all baselines across all network sizes. The paper also presents a study on the role of the inverse temperature hyper papermeter in the evaluation metric of the sorting network, suggesting that the optimal choice might be a function of the depth of the network rather than the number of elements being sorted.\n\nNotes and comments:\n- Can $\\beta$ be a (shared) parameter to be trained jointly with the scoring model? That is assuming the objective is still well behaved for sgd.\n- Typo in the definition of $h(x)$ in proof of Theorem 8.\n- Could be helpful to reference Figure 2 in the intro to showcase the non-monotonic $min$ function constructed from logistic sigmoid.\n- Some background on bitonic vs oe network would be helpful to have in the paper.\n", "summary_of_the_paper": "This work introduces methods to construct differentiable sorting networks that are provably monotonic and have bounded error. To provide such guarantees, the paper derives a set of necessary and sufficient conditions on sigmoid function used for the soft swap operators in the network. It then studies a set of candidate sigmoid functions for such construction, detailing their monotonicity and error guarantees. The experimental results show that the use of monotonic networks can achieve SOTA results when applied to multi-digit ordering on images constructed from MNIST and SVHN.", "summary_of_the_review": "Originality and significance: The main theoretical results presented in the paper (conditions on the monotonicity and bounded error) are novel to the best of my knowledge. The conclusions on using well suited sigmoid functions are interesting and relevant to the body of work on differentiable sorting networks.\n\nQuality and clarity: The paper is well written and the presented results are easy to follow.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "rontKBs3Uca", "reviewer": "Reviewer_QCdx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "This is a nice contribution, the paper is well-written, the interest in finding mononicity is well-explained and motivated; it is no surprise then that we get better results.\n\nI do believe on its current form the paper is a bit incremental and lacking substance which motivate my judgement. I do believe all of the points are addressable.\n\n1)On the one hand, the theoretical findings, although they are meaningful, as mostly straightforward observations. Framing them as theorems appears to me as an overstatement. Proofs are simple and I would recommend them moving them to the appendix. \n\n2)It takes 7 pages to get to the experiment section. This is consistent with my belief that experimental validation is weak. I understand it makes sense to have thorough discussion about functions, moninicity, etc, as authors excel at, but I believe that experiments should be extended. Other papers, such as https://arxiv.org/pdf/2105.04019.pdf provide a much more thorough experimental validation. Why this is not the case here? What happens with large n?\n\n3)I appreciate environmental concerns by authors. However, this raises the point about scalability. Authors should comment on how scalable the proposed method is, hopefully making claims about computational complexity and/or reporting times. Is the proposed method as scalable as alternatives?\n\n4)General interest. Sorting networks are a nice construction but I wonder whether the impact of this area of research is doomed to remain quite limited, or if it could produce impact in broader areas of machine learning as well. It would be good if authors can elaborate on broader impact of their work. As currently stated, beyond the genuine intellectual interest that these constructions may spark, this work appears a bit focused on a niche and with a compromised capacity of reaching a broader audience (I believe this is shared by all other cited works on sorting networks, though).", "summary_of_the_paper": "This paper introduces monotic differentiable sinkhorn networks. Authors argue that mononicity is a desired property because it leads to better bounds in errors. Authors show their proposed approach beats the state of the art on sorting MNIST and SVHN digits", "summary_of_the_review": "Nice contribution. Needs more empirics", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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: This submission presents an interesting contribution on differentiable sorting, providing an analysis of monotonicity for these operations.

The reviewers overall argue for acceptance.
Decision: Accept (Poster)