Venue: ICLR 2018 conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Quality: The paper is built on solid theoretical grounds and supplemented by experimental demonstrations. Specifically, the justification for using the Sinkhorn operator is given by theorem 1 with proof given in the appendix. Because the theoretical limit is unachievable, the authors propose to truncate the Sinkhorn operator at level $L$. The effect of approximation for the truncation level $L$ as well as the effect of temperature $\tau$ are demonstrated nicely through figures 1 and 2(a). The paper also presents a nice probabilistic approach to permutation learning, where the doubly stochastic matrix arises from Gumbel matching distribution. 

Clarity: The paper has a good flow, starting out with the theoretical foundation, description of how to construct the network, followed by the probabilistic formulation. However, I found some of the notation used to be a bit confusing.

1. The notation $l$ appears in Section 2 to denote the number of iterations of Sinkhorn operator. In Section 3, the notation $l$ appears as $g_l$, where in this case, it refers to the layers in the neural network. This led me to believe that there is one Sinkhorn operator for each layer of neural network. But after reading the paper a few times, it seemed to me that the Sinkhorn operator is used only at the end, just before the final output step (the part where it says the truncation level was set to $L=20$ for all of the experiments confirmed this). If I'm correct in my understanding, perhaps different notation need to be used for the layers in the NN and the Sinkhorn operator. Additionally, it would have been nice to see a figure of the entire network architecture, at least for one of the applications considered in the paper. 

2. The distinction between $g$ and $g_l$ was also a bit unclear. Because the input to $M$ (and $S$) is a square matrix, the function $g$ seems to be carrying out the task of preparing the final output of the neural network into the input formate accepted by the Sinkhorn operator. However, $g$ is stated as "the output of the computations involving $g_l$". I found this statement to be a bit unclear and did not really describe what $g$ does; of course my understanding may be incorrect so a clarification on this statement would be helpful.

Originality: I think there is enough novelty to warrant publication.  The paper does build on a set of previous works, in particular Sinkhorn operator, which achieves continuous relaxation for permutation valued variables. However, the paper proposes how this operator can be used with standard neural network architectures for learning permutation valued latent variable. The probabilistic approach also seems novel. The applications are interesting, in particular, it is always nice to see a machine learning method applied to a unique application; in this case from computational neuroscience.

Other comments:

1. What are the differences between this paper and the paper by Adams and Zemel (2011)? Adams and Zemel also seems to propose Sinkhorn operator for neural network. Although they focus only on the document ranking problem, it would be good to hear the authors' view on what differentiates their work from Adams and Zemel.

2. As pointed out in the paper, there is a concurrent work: DeepPermNet. Few comments regarding the difference between their work and this work would also be helpful as well.

Significance: The Sinkhorn network proposed in the paper is useful as demonstrated in the experiments. The methodology appears to be straight forward  to implement using the existing software libraries, which should help increase its usability. 

The significance of the paper can greatly improve if the methodology is applied to other popular machine learning applications such as document ranking, image matching, DNA sequence alignment, and etc. I wonder how difficult it is to extend this methodology to bipartite matching problem with uneven number of objects in each partition, which is the case for document ranking. And for problems such as image matching (e.g., matching landmark points), where each point is associated with a feature (e.g., SIFT), how would one formulate such problem in this setting? 

review_title: The paper utilizes finite approximation of the Sinkhorn operator to describe how one can construct a neural network for learning from permutation valued training data. A probabilistic view of permutation via injection of Gumbel noise is also presented in the paper.

final_score: rating: 7: Good paper, accept
review_content: Learning latent permutations or matchings is inherently difficult because the marginalization and partition function computation problems at its core are intractable. The authors propose a new method that approximates the discrete max-weight matching by a continuous Sinkhorn operator, which looks like an analog of softmax operator on matrices. They extend the Gumbel softmax method (Jang et al., Maddison et al. 2016) to define a Gumbel-Sinkhorn method for distributions over latent matchings. Their empirical study shows that this method outperforms competitive baselines for tasks such as sorting numbers, solving jigsaw puzzles etc.

In Theorem 1, the authors show that Sinkhorn operator solves a certain entropy-regularized problem over the Birkhoff polytope (doubly stochastic matrices). As the regularization parameter or temperature \tau tends to zero, the continuous solution approaches the desired best matching or permutation. An immediate question is, can one show a convergence bound to determine a reasonable choice of \tau?

The authors use the Gumbel trick that recasts a difficult sampling problem as an easier optimization problem. To get around non-differentiable re-parametrization under the Gumbel trick, they extend the Gumbel softmax distribution idea (Jang et al., Maddison et al. 2016) and consider Gumbel-Sinkhorn distributions. They illustrate that at low temperature \tau, Gumbel-matching and Gumbel-Sinkhorn distributions are indistinguishable. This is still not sufficient as Gumbel-matching and Gumbel-Sinkhorn distributions have intractable densities. The authors address this with variational inference (Blei et al., 2017) as discussed in detail in Section 5.4.

The empirical results do well against competitive baselines. They significantly outperform Vinyals et al. 2015 by sorting up to N = 120 uniform random numbers in [0, 1] with great accuracy < 0.01, as opposed to Vinyals et al. who used a more complex recurrent neural network even for N = 15 and accuracy 0.9. 

The empirical study on jigsaw puzzles over MNIST, Celeba, Imagenet gives good results on Kendall tau, l1 and l2 losses, is slightly better than Cruz et al. (arxiv 2017) for Kendall tau on Imagenet 3x3 but does not have a significant literature to compare against. I hope the other reviewers point out references that could make this comparison more complete and meaningful.

The third empirical study on the C. elegans neural inference problem shows significant improvement over Linderman et al. (arxiv 2017).

Overall, I feel the main idea and the experiments (especially, the sorting and C. elegance neural inference) merit acceptance. I am not an expert in this line of research, so I hope other reviewers can more thoroughly examine the heuristics discussed by the authors in Section 5.4 and Appendix C.3 to get around the intractable sub-problems in their approach.    
review_title: Gumbel-Sinkhorn networks for learning permutations

final_score: rating: 6: Marginally above acceptance threshold
review_content: The idea on which the paper is based - that the limit of the entropic regularisation over Birkhoff polytope is on the vertices = permutation matrices -, and the link with optimal transport, is very interesting. The core of the paper, Section 3, is interesting and represents a valuable contribution.

I am wondering whether the paper's approach and its Theorem 1 can be extended to other regularised versions of the optimal transport cost, such as this family (Tsallis) that generalises the entropic one:

https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14584/14420

Also, it would be good to keep in mind the actual proportion of errors that would make a random choice of a permutation matrix for your Jigsaws. When you look at your numbers, the expected proportion of parts wrong for a random assignment could be competitive with your results on the smallest puzzles (typically, 2x2). Perhaps you can put the *difference* between your result and the expected result of a random permutation; this will give a better understanding of what you gain from the non-informative baseline.
(also, it would be good to define "Prop. wrong" and "Prop. any wrong". I think I got it but it is better to be written down)

There should also be better metrics for bigger jigsaws -- for example, I would accept bigger errors if pieces that are close in the solution tend also to be put close in the err'ed solution.

Typos:

* Rewrite definition 2 in appendix. Some notations do not really make sense.
review_title: An interesting paper, based on a simple and neat idea, with good experimental results

Meta-review: This paper with the self-explanatory title was well received by the reviewers and, additionally, comes with available code. The paper builds on prior work (Sinkhorn operator) but shows additional, significant amount of work to enable its application and inference in neural networks.  There were no major criticisms by the reviewers, other than obvious directions for improvement which should have been already incorporated in the paper, issues with clarity and a little more experimentation. To some extent, the authors addressed the issues in the revised version.   
Decision: Accept (Poster)