Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
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.
## Pros
- The idea of enforcing monotonicity is sound.
- Empirical results demonstrate a real gain from using monotonic sorting networks.

## Cons
- 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.
- 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.
- It is not very clear to me why you introduce Fc and Fr. 
- As fast sort is monotonic as well why doesn't it work better?
- What are the missing entries in table 3?
- 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?
## Additional remarks:
Shouldn't P in Figure 1 be doubly stochastic? (second columns does not sum up to 1).
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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
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.

I 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.

1)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. 

2)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?

3)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?

4)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_review: Nice contribution. Needs more empirics
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

The 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.

Notes and comments:
- 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.
- Typo in the definition of $h(x)$ in proof of Theorem 8.
- Could be helpful to reference Figure 2 in the intro to showcase the non-monotonic $min$ function constructed from logistic sigmoid.
- Some background on bitonic vs oe network would be helpful to have in the paper.

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.

Quality and clarity: The paper is well written and the presented results are easy to follow.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

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.
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).

*Strengths*
- This paper presents a well motivated idea
- The paper is well structured and contains strong theoretical results
- Clear figures are very helpful for understanding the differences to other sigmoid functions
- Empirical results illustrate the improved performance gained from monotonicity
- Sensitivity to hyperparameter Beta and choice of sigmoid functional form is clearly illustrated, which shows monotonic networks clearly outperform non-monotonic alternatives.

*Weaknesses*
- 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.
- 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.

*Minor comments/questions*
- 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)?
- 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)
- I'm a bit confused by 'for beta = 1' in Theorem 10, while beta appears in Eq. (13).
- 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.

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.

While 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.
review_title: null

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)