Distances are pervasive in machine learning. They serve as similarity measures, loss functions, and learning targets; it is said that a good distance measure solves a task. When defining distances, the triangle inequality has proven to be a useful constraint, both theoretically-to prove convergence and optimality guaranteesand empirically-as an inductive bias. Deep metric learning architectures that respect the triangle inequality rely, almost exclusively, on Euclidean distance in the latent space. Though effective, this fails to model two broad classes of subadditive distances, common in graphs and reinforcement learning: asymmetric metrics, and metrics that cannot be embedded into Euclidean space. To address these problems, we introduce novel architectures that are guaranteed to satisfy the triangle inequality. We prove our architectures universally approximate norm-induced metrics on R n , and present a similar result for modified Input Convex Neural Networks. We show that our architectures outperform existing metric approaches when modeling graph distances and have a better inductive bias than non-metric approaches when training data is limited in the multi-goal reinforcement learning setting.
This paper is about learning and utilizing distance metrics in neural nets, particularly focusing on metrics that obey the triangle inequality. The paper's core contributions are three approaches to doing this (Deep Norms, Wide Norms, Neural Metrics), along with theoretical and empirical grounding for the metrics.
The hypothesis is clearly on the bottom of page 1 - "Is it possible to impose the triangle inequality architecturally, without the downsides of Euclidean distance?" The downsides are previously listed as 1) not being able to represent asymmetric distances and 2) that the Euclidean space is known to not be able to precisely model some metric spaces with an embedding.
The approach given is quite well motivated. At large, this paper is quite clear and does a good job of delineating why it is taking each step. That starts with a preliminary discussion of metric spaces and norms and what we get when we have the given properties in different combinations.
After describing the motivations and the differences between the three algorithms, the paper then goes on to show results on a couple of toy tasks (metric nearness, graph distances) and then a more challenging one in learning a UVFA. The most striking of the results is the UVFA one where all of the metrics do much better than the Euclidian norm on the asymmetric case, which is the usual one. If these results held in over bigger environments and/or much more data, that would be really intriguing.
I do feel as if this paper is missing a glaring experiment. It talks a lot at the beginning about Siamese Networks being a motivation. It then doesn't do anything with Siamese Networks. They are very common and, if the Euclidean Metric was really deficient relative to this one, we would see it in those results given how important is the relative differences of the embeddings in Siamese Networks. 
We also don't see an example where the Euclidean metric fails to come even close to the other metrics in efficacy (as appealed to in the second downside for the Euclidean metric). I don't think that the UVFA results are this because they are cut quite short - it could just be an artifact of the learning process being slow a la how SGD is frequently shown to be just as good as more complex optimizers given the right tuning.
Finally, while I do work on some areas of representation learning, this is not my forte and so I'm not too familiar with most results in this domain. That being said, I am not entirely convinced that this result is of huge consequence unless the empirical analysis is strengthened a lot. Examples of that would include the two I described above.
In its current form, I do not think that this passes the ICLR bar, however I do think its close and, if the experiments I prescribed continued the trend, I would suggest its inclusion.