Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This manuscript proposes a general framework to learn non-Euclidean distances from data using neural networks. The authors provide a combination of theoretical and experimental results in support of the use of several neural architectures to learn such distances. In particular, the develop “deep norms” and “wide norms”, based either on a deep or shallow neural network. Metrics are elaborated based on norms by combining them with a learnt embedding function mapping the input space de R^n. Theoretical results are mostly application textbook results and intuitive, the overall work forms a coherent line of research bridging theory and applications that sets well justified reference approaches for this topic.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: This paper proposes a modeling approach for norm and metric learning that ensures triangle inequalities are satisfied by the very design of the architecture. The main idea is that convexity together with homogeneity imply subadditivity, so starting from an input-convex architecture and using activations that preserve homogeneity implies the resulting model is sub-additive at every point. This architecture is used to model a norm, and in conjunction with an embedding - a metric. The authors also propose a mixture-based approach that combines a given set of metrics into a new one using a max-mean approach. Universal approximation results are presented for both architectures. The results are illustrated on a few mostly synthetic examples including metric nearness for random matrices, value functions for maze MDPs and distances between nodes on a graph (some problems here are sourced from open street map).

I think this is one of those papers where there is nothing much to complain about. I found the paper to be very-well written. The basic modeling approach of propagating homogeneity through an input-convex net is elegant, and conceptually appealing. 

My only suggestion to the authors is that it looks as if a lot of importance is placed on modeling asymmetry, however, that problem seems relatively easily solvable with existing approaches. One could just have two separate embedding functions for the two positional arguments. I don't know if there are obvious reasons why this wouldn't work, but it looks like a very sensible idea that could solve asymmetry. I think that the other issue, that of nonembeddability is much more important, yet it was not emphasized particularly strongly except for one example. I think expanding on this would strengthen the motivation significantly. There is a rich literature on (non)embeddability in l2, which contains some deeply non-intuitive results (e.g. large graph classes like expanders being non-embeddable). I think that a quick survey on that citing the most important results would make the seriousness of this issue apparent to the reader.  
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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.
review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: This paper shows how to enforce and learn non-Euclidean
(semi-)norms with neural networks.
This is a promising direction for the community as part
of a larger direction of understanding how to do better
modeling in domains that naturally have non-Euclidean
geometries.
This paper shows convincing experiments for modeling
graph distances and in the multi-goal reinforcement
learning setting.

One clarification I would like is related to some
tasks inherantly not having a Euclidean embedding.
Are there works that theoretically/empirically characterize
how bad this assumption can be for some problem classes?
Even though some tasks are impossible to embed exactly
into a Euclidean space, are there sometimes properties
that, given a high enough latent dimensionality,
they can be reasonably approximated?
And in the table of Figure 1, whta dimension n was used
for the Euclidean norm?
review_title: Official Blind Review #1

Meta-review: This paper proposes a neural network approach to approximate distances, based on a representation of norms in terms of convex homogeneous functions. The authors show universal approximation of norm-induced metrics and present applications to value-function approximation in RL and graph distance problems. 

Reviewers were in general agreement that this is a solid paper, well-written and with compelling results. The AC shares this positive assessment and therefore recommends acceptance. 
Decision: Accept (Poster)