Year: 2021

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.

text: 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.

heading: 1 INTRODUCTION
text: Recently, the idea of end-to-end training of neural networks with ordering supervision by a 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 for training with a sorting algorithm in the architecture, the error needs to be propagated in a meaningful way back to the neural network, it is necessary to use a differentiable sorting function. Several such differentiable sorting functions have been introduced, e.g., by Grover et al. [1], Cuturi et al. [2], Blondel et al. [3], and Petersen et al. [4]. In 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 is 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-implementation, e.g., in ASICs, as well as on highly parallelized general-purpose hardware like GPUs. Differentiable sorting networks [4] continuously relax the conditional swap operations by relaxing their step function to a logistic sigmoid function.
One problem that arises in this context is 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 a 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, we demonstrate monotonicity for different choices of sigmoid functions. As can be seen in Figure 4, existing differentiable sorting operators are either non-monotonic or 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 as well as the SVHN ranking task.
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.

heading: 2 RELATED WORK
text: 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 et al. [1] proposed NeuralSort, a continuous relaxation of the argsort operator. A (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 a 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 et 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 a 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 a linear program over a permutahedron. To smooth the resulting discontinuous function and provide useful derivatives, they introduce a strongly convex regularization. They evaluate the proposed approach in the context of Top-k classification and label ranking accuracy via a soft Spearman’s rank correlation coefficient.
Recently, Petersen et al. [4] proposed differentiable sorting networks, a differentiable sorting operator based on sorting networks with differentiably relaxed conditional swap operations. Differentiable sorting networks achieved a new state-of-the-art on both the four-digit MNIST sorting benchmark and the SVHN sorting benchmark.
Applications and Broader Impact. In the domain of recommender systems, Lee et al. [10] propose differentiable ranking metrics, and Swezey et al. [11] propose PiRank, a learning-to-rank method using differentiable sorting. Other works explore differentiable sorting-based top-k for applications such as differentiable image patch selection [12], differentiable k-nearest-neighbor [1], [13], top-k attention for machine translation [13], and differentiable beam search methods [13], [14].

heading: 3 BACKGROUND: SORTING NETWORKS
text: 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 a specific order. This is achieved by simply passing through the inputs 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 are a and b and the outputs a′ and b′, a swap operator ensures a′ ≤ b′ and can easily be formalized as a′ = min(a, b) and b′ = max(a, b). Examples of sorting nets are the odd-even network [15], which alternatingly swaps odd and even wires with their successors, and the bitonic network [16], which repeatedly merges and sorts bitonic sequences. While to odd-even network requires n layers, the bitonic networks uses the divide-and-conquer principle to sort within only (log2 n)(1 + log2 n)/2 layers.
Note that, while they are similar in name, sorting networks are not neural networks that sort.

heading: 3.1 DIFFERENTIABLE SORTING NETWORKS
text: 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 in Section 3. These operators can be relaxed to differentiable min and max . Note that we denote the differentiable relaxations in italic font and their hard counterparts in roman font. Note that the differentiable relaxations min and max are different from the commonly used softmin and softmax, which are relaxations of argmin and argmax [17].
One example for such a relaxation of minσ and maxσ is the logistic relaxation
minσ(a, b) = a · σ(b− a) + b · σ(a− b) and maxσ(a, b) = a · σ(a− b) + b · σ(b− a) (1)
where σ is the logistic sigmoid function with inverse temperature β > 0:
σ : x 7→ 1 1 + e−βx . (2)
Any layer of a sorting network can also be represented as a relaxed and doubly-stochastic permutation matrix. Multiplying these (layer-wise) permutation matrices yields a (relaxed) total permutation matrix P. Multiplying P with an input x yields the differentiably sorted vector x̂ = Px, which is also the output of the differentiable sorting network. Whether it is necessary to compute P, or whether x̂ 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 a ground truth permutation matrix Q.
In the next section, we build on these concepts to introduce monotonic differentiable sorting networks, i.e., all differentiably sorted outputs x̂ are non-decreasingly monotonic in all inputs x.

heading: 4 MONOTONIC DIFFERENTIABLE SORTING NETWORKS
text: In this section, we start by introducing definitions and building theorems upon them. In Section 4.2, we use these definitions and properties to discuss different relaxations of sorting networks.

heading: 4.1 THEORY
text: 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-decreasing odd-symmetric (around 12 ) function f with
f : R→ [0, 1] with lim x→−∞ f(x) = 0 and lim x→∞ f(x) = 1.
Definition 2 (Continuous Conditional Swaps). Following [4], we define a continuous conditional swap in terms of a sigmoid function f : R→ [0, 1] as
minf (a, b) := a · f(b− a) + b · f(a− b) max f (a, b) = a · f(a− b) + b · f(b− a) (3) argminf (a, b) = ( f(b− a), f(a− b) ) argmax f (a, b) = ( f(a− b), f(b− a) ) . (4)
We require a continuous odd-symmetric sigmoid function to preserve most of the properties of min and max while also making argmin and argmax 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. Theorem 3 (Doubly-Stochasticity and Differentiability of P). (i) The relaxed permutation matrix P, produced by a differentiable sorting network, is doubly-stochastic. (ii) P has the same differentiability as f , e.g., if f is continuously differentiable in the input, P 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 at the diagonal except for rows i and j: at points i, i and j, j the value is v ∈ [0, 1], at points i, j and j, i the value is 1− v and all other entries are 0. This is doubly-stochastic as all rows and columns add up to 1 by construction. As the product of doubly-stochastic matrices is doubly-stochastic, the relaxed permutation matrix P, produced by a differentiable sorting network, is doubly-stochastic.
(ii) The composition of differentiable functions is differentiable and the addition and multiplication of differentiable functions is also differentiable. Thus, a sorting network is differentiable if the employed sigmoid function is differentiable. “Differentiable” may be replaced with any other form of differentiability, such as “differentiable a.e.”
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 minf (x, 0) is non-decreasingly monotonic in x, i.e., min ′f (x, 0) ≥ 0 for all x.
It is sufficient to define it w.l.o.g. in terms of minf (x, 0) due to its commutativity, stability, and odd-symmetry of the operators (cf. SM). Theorem 5 (Monotonicity of Continuous Conditional Swaps). A continuous conditional swap (in terms of a differentiable sigmoid function f ) being non-decreasingly monotonic in all arguments and outputs requires that the derivative of f decays no faster than 1/x2, i.e.,
f ′(x) ∈ Ω ( 1
x2
) . (5)
Proof. We show that Equation 5 is a necessary criterion for monotonicity of the conditional swap. Because f is a continuous sigmoid function with f : R→ [0, 1], minf (x, 0) = f(−x) · x > 0 for some x > 0. Thus, montononicity of minf (x, 0) implies lim supx→∞minf (x, 0) > 0 (otherwise the value would decrease again from a value > 0.) Thus,
lim x→∞ minf (x, 0) = lim x→∞ f(−x) · x = lim x→∞ f(−x) 1/x (L’Hôpital’s rule) = lim x→∞ −f ′(−x) −1/x2
(6)
= lim x→∞ f ′(−x) 1/x2 = lim x→∞ f ′(x) 1/x2 = lim sup
x→∞
f ′(x) 1/x2 > 0⇐⇒ f ′(x) ∈ Ω
( 1
x2
) . (7)
assuming limx→∞ f ′(x) 1/x2 exists. Otherwise, it can be proven analogously via a proof by contradiction.
Corollary 6 (Monotonic Sorting Networks). If the individual conditional swaps of a sorting network are monotonic, the sorting network is also monotonic.
Proof. If single layers g, h are non-decreasingly monotonic in all arguments and outputs, their composition h ◦ g is also non-decreasingly monotonic in all arguments and outputs. Thus, a network of arbitrarily many layers is non-decreasingly monotonic.
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 (Error-Bounded Continuous Conditional Swaps). A continuous conditional swap has a bounded error if and only if supxminf (x, 0) = c is finite. The continuous conditional swap is therefore said to have an error bounded by c.
It is sufficient to define it w.l.o.g. in terms of minf (x, 0) due to its commutativity, stability, and odd-symmetry of the operators (cf. SM). In general, for better comparability between functions, we assume a Lipschitz continuous function f with Lipschitz constant 1.
Theorem 8 (Error-Bounds of Continuous Conditional Swaps). (i) A differentiable continuous conditional swap has a bounded error if f ′(x) ∈ O ( 1
x2
) . (8)
(ii) If it is additionally monotonic, the error bound can be found as limx→∞minf (x, 0) and additionally the error is bound only if Equation 8 holds.
Proof. (i) W.l.o.g. we consider x > 0. Let g(z) := f(−1/z), g(0) = 0. Thus, g′(z) = 1/z2 · f ′(−1/z) ≤ c according to Equation 8. Thus, g(z) = g(0) + ∫ z 0 g′(t)dt ≤ c · z. Therefore, f(−1/z) ≤ c · z =⇒ 1/z · f(−1/z) ≤ c and with x = 1/z =⇒ x · f(−x) = minf (x, 0) ≤ c. (ii) Let minf (x, 0) be monotonic and bound by minf (x, 0) ≤ c. For x > 0 and h(x) := minf (x, 0),
h′(x) = −x · f ′(−x) + f(−x) =⇒ x2f ′(−x) = −xh′(x)︸ ︷︷ ︸ ≤0 +x · f(−x) ≤ x · f(−x) ≤ c . (9)
And thus f ′(x) ∈ O (
1 x2
) .
Theorem 9 (Error-Bounds of Diff. Sorting Networks). If the error of individual conditional swaps of a sorting network is bounded by and the network has ` layers, the total error is bounded by · `.
Proof. For the proof, cf. Supplementary Material C.
Discussion. Monotonicity is highly desirable as otherwise adverse effects such as an input requiring to be decreased to increase the output can occur. In gradient-based training, non-mononicity is problematic as it produces gradients with the opposite sign. In addition, as monotonicity is also given in hard sorting networks, it 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.

heading: 4.2 SIGMOID FUNCTIONS
text: Above, we have specified the space of functions for the differentiable swap operation as well as their desirable properties. In the following, we discuss five notable candidates as well as their properties. The properties of these functions are visualized in Figures 2 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) as proposed in [4]:
σ : x 7→ 1 1 + e−βx
(10)
This function is the de-facto default sigmoid function in machine learning. It provides a continuous, error-bounded, and Lipschitz continuous conditional swap. However, for the logistic function, monotonicity is not given, as displayed in Figure 2.
Reciprocal Sigmoid Function. To obtain a function that yields a monotonic as well as errorbound differentiable sorting network, a necessary criterion is f ′(x) ∈ Θ(1/x2) (the intersection of Equations 5 and 8.) A natural choice is, therefore, f ′R(x) = 1 (2|x|+1)2 , which produces
fR(x) = ∫ x −∞
1
(2β|t|+ 1)2 dt =
1
2
2βx
1 + 2β|x| +
1 2 . (11)
fR fulfills all criteria, i.e., it is an adequate sigmoid function and produces monotonic and error-bound conditional swaps. It has an -bounded-error of = 0.25. It is also an affine transformation of the elementary bipolar sigmoid function x 7→ x|x|+1 . Properties of this function are visualized in Table 1 and Figures 2 and 3. Proofs for monotonicity can be found in Supplementary Material C.
Cauchy distributions. By using the CDF of the Cauchy distribution, we maintain montonicity while reducing the error bound to = 1/π2 ≈ 0.101. It is defined as
fC : x 7→ CDFC ( βx ) = 1
π ∫ x −∞
β
1 + (βt)2 dt =
1 π arctan
( βx ) + 1
2 (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, we set 1-Lipschitz continuity again as a 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 = 1/16 Theorem 10 (Optimal Sigmoid Function). The optimal sigmoid function minimizing the error-bound, while producing a monotonic and 1-Lipschitz continuous (with β = 1) conditional swap operation, is
fO(x) =  − 116βx if βx < − 1 4 , 1− 116βx if βx > + 1 4 ,
βx+ 12 otherwise.
(13)
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 minf (x, 0) = x · f(−x) or max f (0, x) = −x · f(x). Due to symmetry and inversion, it suffices to consider minf (x, 0) = x · f(−x) for x > 0. Since min(x, 0) = 0 for x > 0, we have to choose f in such a way as to make minf (x, 0) = x·f(−x) as small as possible, but not negative. For this, f(−x) must be made as small as possible. Since we know that f(0) = 12 and we are limited to functions f that are Lipschitz continuous with α = 1, f(−x) cannot be made smaller than 12 − x, and hence minf (x, 0) cannot be made smaller than x ( 1 2 − x ) . To make minf (x, 0) as small as possible, we have to follow x( 12 − x) as far as possible (i.e., to values x as large as possible). Monotonicity requires that this function can be followed only up to x = 14 , at which point we have minf ( 1 4 , 0) = 1 4 ( 1 2 − 1 4 ) = 116 . For larger x, that is, for x > 1 4 ,
the value of x ( 1 2 − x ) decreases again and hence the functional form of the sigmoid function f has to change at x = 14 to remain monotonic.
The best that can be achieved for x > 14 is to make it constant, as it must not decrease (due to monotonicity) and should not increase (to minimize the deviation from the crisp/hard version). That is, minf (x, 0) = 116 for x > 1 4 . It follows x · f(−x) = 1 16 and hence f(−x) = 1 16x for x > 1 4 . Note that, if the transition from the linear part to the hyperbolic part were at |x| < 14 , 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, fC and fO in this order get closer to x+ 12 (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 1 also indicates whether a sigmoid function yields a monotonic swap operation or not, which is visualized in Figure 2: clearly σ-based sorting networks are not monotonic, while all others are. It also states whether the error is bounded, which for a monotonic swap operation means limx→∞minf (x, 0) < ∞, and gives their bound relative to the Lipschitz constant α.
Figure 3 displays the loss for a sorting network with n = 3 inputs. We project the hexagon-shaped 3-value permutahedron onto the x-y-plane, while the z-axis indicates the loss. Note that, at the rightmost point
5 MONOTONICITY OF OTHER DIFFERENTIABLE SORTING OPERATORS
For the special case of n = 2, i.e., for sorting two elements, NeuralSort is equivalent to differentiable sorting networks with the logistic sigmoid function. Thus, it is non-monotonic as displayed in Figure 4.
For the Sinkhorn sorting algorithm, we can simply construct an example of non-monotonicity by keeping one value fixed, e.g., at zero, and varying the second value (x) as in Figure 4 and displaying the minimum. Interestingly, for the case of n = 2, this function is numerically equal to NeuralSort and differentiable sorting networks with the logistic function.
For fast sort, we follow the same principle and find that it is indeed monotonic (in this example); however, the error is unbounded, which is undesirable.
For differentiable sorting networks, [4] proposed to extend the sigmoid function by the activation
replacement trick, which avoids extensive blurring as well as vanishing gradients. They apply the activation replacement trick ϕ before feeding the values into the logistic sigmoid function; thus, the sigmoid function is effectively σ ◦ ϕ. Here, ϕ : x 7→ x|x|λ+ where λ ∈ [0, 1] and ≈ 10−10. Here, the asymptotic character of σ ◦ ϕ does not fulfill the requirement set by Theorem 5, and is thereby non-monotonic as also displayed in Figure 4 (purple).
We summarize monotonicity and error-boundness for all differentiable sorting functions in Table 2.

heading: 6 EMPIRICAL EVALUATION
text: 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 a network to produce a scalar output value for each image such that the ordering of the outputs follows the respective ordering of the images. Specifically, the metrics 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 [18] dataset with the difference that the images are already multi-digit numbers as shown in [4].
Comparison to the State-of-the-Art. We first compare the proposed functions to other state-ofthe-art approaches using the same network architecture and training setup as 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 state-of-the-art methods by a 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 n. The computational complexity of the proposed method depends on the employed sorting network architecture leading to a complexity ofO(n3) for odd-even networks and a complexity ofO(n2 log2 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].
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 is small. However, for the more complex bitonic sorting networks, fC (Cauchy) performs better than fO. This is because fO does not provide a higher-order smoothness and is only C1 smooth, while the Cauchy function fC is analytic and C∞ smooth.
Evaluation of Inverse Temperature β. To further understand the behavior of the proposed monotonic functions compared to the logistic sigmoid function, we evaluate all sigmoid functions for different inverse temperatures β during training. We investigate four settings: odd-even networks for n ∈ {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 n = 32, while the odd-even networks for n = 15 also has 15 layers. We display the results of this evaluation in Figure 5. 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 different number of layers. The bitonic network for n = 32 (bottom right) has the same number of layers as n = 15 in the odd-even network (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 n = 32 (bottom left) are shifted almost an order of magnitude to the right.
For all configurations, the proposed sigmoid functions for monotonic sorting networks improve over the standard logistic sigmoid function, as well as the ART.

heading: 7 CONCLUSION
text: In this work, we 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 differentiable 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.
REPRODUCIBILITY STATEMENT
We will make the source code and experiments of this work publicly available to foster future research in this direction. All data sets are publicly available. We specify all necessary hyperparameters for each experiment. We use same model architectures as in previous works. We demonstrate how the choice of hyperparameter β affects the performance in Figure 5. Each experiment can be reproduced on a single GPU.

heading: C ADDITIONAL PROOFS
text: Theorem 11 (Error-Bounds of Diff. Sorting Networks). If the error of individual conditional swaps of a sorting network is bounded by and the network has ` layers, the total error is bounded by · `.
Proof. Induction over number k of executed layers. Let x(k) be input x differentially sorted for k layers and x(k) be input x hard sorted for k layers as an anchor. We require this anchor, as it is possible that x(k)i < x (k) j but x (k) i > x (k) j for some i, j, k.
Begin of induction: k = 0. Input vector x equals the vector x(0) after 0 layers. Thus, the error is equal to 0 · . Step of induction: Given that after k− 1 layers the error is smaller than or equal to (k− 1) , we need to show that the error after k layers is smaller than or equal to k .
The layer consists of comparator pairs i, j. W.l.o.g. we assume x(k−1)i ≤ x (k−1) j . W.l.o.g. we assume that wire i will be the min and that wire j will be the max, therefore x(k)i ≤ x (k) j . This implies x (k−1) i = x (k) i and x (k−1) j = x (k) j . We distinguish two cases:
• ( x (k−1) i ≤ x (k−1) j and x (k−1) i ≤ x (k−1) j ) According to the assumption, ∣∣x(k−1)i −x(k)i ∣∣ ≤ and∣∣x(k−1)j −x(k)j ∣∣ ≤ . Thus, ∣∣x(k)i −x(k)i ∣∣ ≤ ∣∣x(k−1)i −x(k−1)i ∣∣+ ∣∣x(k−1)i −x(k)i ∣∣ ≤ (k−1) + = k . • ( x (k−1) i ≤ x (k−1) j but x (k−1) i > x (k−1) j ) This case can only occur if
∣∣x(k−1)j − x(k−1)i ∣∣ ≤ (k−1) and
∣∣x(k−1)i −x(k−1)j ∣∣ ≤ (k−1) because x(k−1)i and x(k−1)j have to be so close that within margin of error such a reversed order is possible. According to the assumption,
∣∣x(k−1)j −x(k)i ∣∣ ≤ and∣∣x(k−1)i −x(k)j ∣∣ ≤ . Thus, ∣∣x(k)i −x(k)i ∣∣ ≤ ∣∣x(k−1)j −x(k−1)i ∣∣+ ∣∣x(k−1)j −x(k)i ∣∣ ≤ (k−1) + = k . Theorem 12. minfR and maxfR are monotonic functions with the sigmoid function fR.
Proof. Wlog., we assume ai = x and aj = 0.
minfR(x, 0) = x · fR(−x) = x 1
2
( x
1 + |x| + 1
) (14)
To show monotonicity, we consider its derivative / slope.
d
dx minfR(x, 0) =
d
dx
( x 1
2
( x
1 + |x| + 1
)) (15)
= 1
2
( x
1 + |x| + 1
) + x 1
2
d
dx
( x
1 + |x| + 1
) (16)
= 1
2
( x
1 + |x| + 1
) + x 1
2
d
dx
( x
1 + |x|
) (17)
= 1
2
( x
1 + |x| + 1
) + x 1
2
dx dx · (1 + |x|)− x · d|x|+1 dx
(1 + |x|)2 (18)
= 1
2
( x
1 + |x| + 1
) + x 1
2 (1 + |x|)− x sgn(x) (1 + |x|)2
(19)
= 1
2
( x
1 + |x| + 1
) + x 1
2 1 + |x| − |x| (1 + |x|)2
(20)
= 1
2
( x
1 + |x| + 1
) + x 1
2
1
1 + 2|x|+ |x|2 (21)
= 1
2
( x
1 + |x| + 1 +
x
1 + 2|x|+ |x|2
) (22)
= 1
2
( x(1 + |x|)
1 + 2|x|+ |x|2 +
1 + 2|x|+ |x|2 1 + 2|x|+ |x|2 +
x
1 + 2|x|+ |x|2
) (23)
= 1
2
( 2x+ 2|x|+ x|x|+ |x|2 + 1
1 + 2|x|+ |x|2
) (24)
= 1
2
( 2(x+ |x|) + |x|(x+ |x|) + 1
1 + 2|x|+ |x|2
) (25)
≥ 1 2
( 1
1 + 2|x|+ |x|2
) (because x+ |x| ≥ 0) (26)
> 0 (27) maxfR is analogous.
Theorem 13. minfC and maxfC are monotonic functions with the sigmoid function fC .
Proof. Wlog., we assume ai = x and aj = 0. minfC (x, 0) = x · fC(−x) = x · ( 1
π arctan(−βx) + 1 2
) (28)
To show monotonicity, we consider its derivative. ∂
∂x minfC (0, x) =
∂
∂x (fC(−x) · x) = x ·
∂
∂x fC(−x) + fC(−x) ·
∂
∂x x
= x · ∂ ∂x
( 1
π arctan(−βx) + 1 2
) + 1
π arctan(−βx) + 1 2
= x · 1 π −β 1 + (βx)2 − 1 π arctan(βx) + 1 2
= 1 2 − 1 π arctan(βx)− 1 π
βx
1 + (βx)2
= 1 2 − 1 π arctan(z)− 1 π z 1 + z2 (with z = βx) (29)
To reason about the derivative, we also consider the second derivative:
lim z→∞
1 2 − 1 π arctan(z)− 1 π z 1 + z2 = 1 2 − lim z→∞ 1 π arctan(z)− lim z→∞ 1 π z 1 + z2
= 1 2 − 1 π π 2 − 0 = 0 (30)
lim z→−∞
1 2 − 1 π arctan(z)− 1 π z 1 + z2 = 1 2 − lim z→−∞ 1 π arctan(z)− lim z→−∞ 1 π z 1 + z2
= 1 2 − 1 π −π 2 − 0 = 1 2 + 1 π π 2 − 0 = 1 (31)
For z ∈ (−∞, 0]: The derivative of minfC (0, x) converges to 1 for z → −∞ (Eq. 31). For z ∈ [0,∞): The derivative of minfC (0, x) converges to 0 for z →∞ (Eq. 30).
∂
∂z
1 2 − 1 π arctan(z)− 1 π z 1 + z2 = − 2 π(1 + z2)2 < 0 (32)
The second derivative (Eq. 32) of minfC (0, x) is always negative.
Therefore, the derivative is always in (0, 1), and therefore always positive. Thus, minfC (0, x) is strictly monotonic. maxfC is analogous.

Review summaries:
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

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. 

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.

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.  By 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.  Experiments 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.